CS 412/512

From CS Wiki
Jump to: navigation, search

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