CPE612 Parallel Algorithms
Spring 2003

Description: Introduction to metrics describing the performance and scalability of parallel algorithms. Performance analysis of parallel algorithms for performing sorting, matrix multiplication, solving linear equations, and FFT.

Text book: Kenneth Berman, Jerome Paul, Fundamentals of Sequential and Parallel Algorithms, PWS Publishing Company, New York, 1997.
Other recommended books:

• V. Kumar, A. Grama, A. Gupta, G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms, The Benjamin/Cummings Publishing Company, Inc., 1994.
• Barry Wilkinson, Michael Allen, Parallel Programming: techniques and applications using networked workstations and parallel computers, Prentice Hall, 1999.
• Peter Pacheco, Parallel Programming with MPI, Morgan Kaufmann Publishers, Inc. 1997.
• David E. Culler, Jaswinder Pal Singh, Anoop Gupta, Parallel Computer Architecture: A Hardware Software Approach, Morgan Kaufmann Publishers, 1999.

Grading Policy:

• Homeworks - 20%
• Midterm exam - 20%
• Graduate project - 20%
• Final exam - 35%
• Discretion - 5%

Important Dates

• Midterm exam: Monday, March 10, 2003.
• Project proposal: Monday, February 5, 2003.
• Final project report: Monday, April 21, 2003.
• Last day of Class: Monday, April 21, 2003.
• Final exam: Monday, April 28, 2003, 11:30-2 PM.

Course Outline

• Introduction and Background
  • Parallel Processing systems
  • Idealized Parallel Computer Systems
  • Message Passing architectures
  • Network Topologies
  • Network Routing techniques
  • Communication operations
• Parallel Algorithms and Architectures
• Performance Measurement
• Complexity, Speed Up measures, Scalability measures.
• Simple Linear Algorithms
• Simple Sorting and searching algorithms
• Simple graph algorithms
• Matrix related problems
• Parallel Sorting and Searching algorithms
• Probability and Average Complexity
• Special Topics
• Heuristic Search, Hashing, Probabilistic Algorithms, Graph Algorithms
• Parallel Matrix Algorithms, Parallel Graph Algorithms
• Distributed Algorithms
• Midterm and Project Presentations

Lecture notes

Homework

Homework #1 due on Monday, February 10, 2003 in class. No late homework will be accepted.

• Homework #1 solution.

Homework #2 due on Wednesday, February 26, 2003 in class. No late homework will be accepted. MS Word version of the homework.

Cover page for a homework.

Homework #3&4 due on Thursday, April 17. No late homework will be accepted.