CS 412/512: Parallel Algorithms
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.
Type: CS 412 is a technical elective for CS majors. CS 512 is a graduate course.
Total Credits: 3
Course Coordinator: Robert Hiromoto
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