520-428 Introduction to Algorithms for Parallel Computers

Meeting Times: Monday, Wednesday 4-5:15, Barton 225
Instructor: Dr. Louis J. Podrazik, e-mail: podrazik@super.org
Office Hours: by appointment

Synopsis: The ultimate goal of using parallel systems is to achieve a computational speedup factor of p with p processors. This course concentrates on examining why this ideal cannot often be practically achieved, and describes methods that exhibit varying degrees of speedup by using multiple processors in a concurrent (parallel or distributed) system. The actual speed gain depends on the quality of mapping the parallel algorithm with the system architecture. This course focuses on the crucial interdependence of architectural and algorithmic speedup techniques. More specifically, the problem of algorithm selection and tuning for parallel systems and the reverse problem, the incorporation of architectural features to help improve algorithm efficiency are presented.

Prerequisite: Basic computer architecture and a course in computer programming.

Curriculum

Course Grading

Homework Assignments

Curriculum

• Week 1. Introduction to parallel computation, motivation & some basic concepts
• Week 2. Parallel architectures & programming models of parallel processing
• Week 3. Some basic parallel algorithms & their complexity
• Week 4. Algorithms & architectures: parallel synthesis, syntax, mapping
• Week 5. Matrix multiplication, memory and data structures
• Week 6. Matrix Algorithms I: linear recurrence and banded systems
• Week 7. Review & Mid Term Exam
• Week 8. Some specific parallel architectures (SP, Cray, SGI, Tera, JHU lab)
• Week 9. Parallel programming overview (Message passing systems -MPI, OpenMP, Shemem)
• Week 10. Numerical algorithms: tridiagonal system solvers
• Week 11. Matrix Algorithms II: dense linear systems
• Week 12. Matrix Algorithms III: factorization methods (LU, QR)
• Week 13. Optimization and signal processing primitives; structures (FFT, etc)

Course Grading

Evaluation: Students will be evaluated on the basis of the following three components:

• 25% One-week homeworks, including programming assignments
• 25% Closed-book midterm - 10 October 2001 (in class)
• 50% Open-book final exam – 17 December 2001

References

• Required text:
  
  

(1) Behrooz Parhami (1999), Introduction to Parallel Processing: Algorithms and Architectures, QA76.58.P3798 1999, ISBN 0-306-45970-1.

• Optional books:

(1) Schonauer (2000), Scientific Supercomputing: Architecture and Use of Shared and Distributed Memory Parallel Computers, Self-Edition

(2) Lakshmivarahan & Dhall (1990), Analysis and Design of Parallel Computers: Arithmetic and Matrix Problems, McGraw-Hill

(3) Leighton (1992), Introduction to Parallel Algorithms and Architectures: Arrays . Trees . Hypercubes, Morgan Kaufmann.

(4) Jagdish J. Modi, (1988), Parallel Algorithms and Matrix Computations

(5) Akl (1997), Parallel Computation: Models & Methods, Prentice Hall

(6) Geoffrey Fox, et al. (1988), Solving Problems on Concurrent Computers

• Some web sites of interest:

(1) http://www.uni-karlsruhe.de/Uni/RZ/Personen/rz03/book/

(2) http://www-unix.mcs.anl.gov/mpi/

• Journals: IEEE Trans. on Computers, IEEE Trans. on Parallel & Distributed Systems, Journal of Parallel & Distributed Computing, and Parallel Computing.
• Conferences: Int'l Symp. Computer Architecture (ISCA, since 1973), Int'l Conf. Parallel Processing (ICPP, since 1972), Int'l Parallel Processing Symp. (IPPS, since 1987), IEEE Symp. Parallel and Distributed Processing (SPDP, since 1989), and ACM Symp. Parallel Algorithms and Architectures (SPAA, since 1988).