# CS 412/512

From CS Wiki

### Parallel Algorithms

**Catalog Description:**

Parallel algorithm design; formal analysis of parallel algorithmic complexity; measures of parallel efficiency; relationship between algorithmic structure and parallel mapping strategies; the consequences of spatial- and temporal-locality. Additional projects/assignments required for graduate credit.

**Total Credits:** 3

**Course Coordinator**: Robert Hiromoto

**URL:** None.

**Sullabus:** CS 412/512 Syllabus

**Prereq:** CS 395 Analysis of Algorithms or permission of instructor.

**Textbook:** *Introduction to Parallel Computing (2nd Edition)*, A. Grama, G. Karypis, V. Kumar and A. Gupta, Addison-Wesley, 2003, ISBN 978-0201648652.

### Major Topics Covered

- Interconnection networks: Clusters, hypercube, butterfly, omega, etc.
- Measures of parallel performance: speedup, efficiency, isoefficiency, work function.
- Complexity of parallel computing and communication
- Ring network routing
- Worm-hole routing
- Hypercube routing

- Analysis of parallel complexity on different networks.
- Bitonic sorting
- Algebraic algorithms
- Fast Fourier transform
- Multigrid iterative techniques
- Data and task decomposition