520-429 Principles of Parallel Programming

Department:               Dept. of Electrical and Computer Engineering
Meeting Times:            Tuesday, Wednesday 4-5:15, Barton 225
Instructor:                  Dr. Louis J. Podrazik, e-mail: podrazik@super.org
Office Hours:             by appointment
Credits:                       3

Synopsis: Programming models and languages for current computing platforms. Computational models include shared and distributed memory multiprocessors. Essential techniques of message-passing parallel programming will be based upon MPI (Message Passing Interface); shared memory programming will use the OpenMP standard. Other parallel language extensions will be studied, including Split-C and UPC (unified parallel C). Programming projects will be given for the IBM SP parallel computer and other available departmental multicomputers.

Prerequisite: 520.428 or equivalent and a course in C programming.

Curriculum:

Course Grading

Homework Assignments

Course Projects

Curriculum:

Week 1. Overview of parallel computation and programming
Week 2. JHU computing platforms
Week 3. MPI: overview (ch. 3, 4)
Week 4. MPI: communication & data (ch. 5, 6)
Week 5. MPI: communicators, topologies, advanced communication (ch. 7, 13)
Week 6. MPI: I/O, debugging, parallel program coding (ch. 8, 9,10)
Week 7. MPI: Performance (ch. 11, 12)
Week 8. Spring break
Week 9. Final project problems (ch. 14, others)
Week 10. OpenMP: overview (ch. 2, 3)
Week 11. OpenMP: Parallel regions, synchronization (ch 4, 5)
Week 12. OpenMP: Performance, parallel program coding (ch 6)
Week 13. Combined applications
Week 14. Other programming models: split-C, UPC, HPC

References

Required text:

(1) Pacheco, Peter S., Parallel Programming with MPI, Morgan Kaufman Publishers, 2001, ISBN 1-55860-339-5.

(2) Chandra, Rohit, et. al., Parallel Programming in OpenMP, Morgan Kaufman Publishers, 1997, ISBN 1-55860-671-8.

Optional books:

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

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

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

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

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

Some web sites of interest:

(1) http://www.erc.msstate.edu/mpi/mpi-faq.html

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

(3) ftp://info.mcs.anl.gov/pub/mpi

(4) http://www.mpi.nd.edu/lam/download

IBM SP Architecture:

(1) http://www-1.ibm.com/servers/eserver/pseries/hardware/largescale/sp.html

(2) http://www.uni-karlsruhe.de/~SP/sp-workshop/PAPERS/talk_1_2.pdf

(3) http://www.research.ibm.com/actc/

(4) http://hpcf.nersc.gov/computers/SP/

IBM SP Software and Libraries:

(1) http://www-3.ibm.com/software/data/bi/osl/index.html

(2) http://publib.boulder.ibm.com/doc_link/en_US/a_doc_lib/sp34/pe/html/am104mst02.html

JHU CIS IBM SP Documentation:

(1) http://128.220.137.161:8080

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).

Course Grading

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

30% Biweekly homeworks, mostly programming assignments
30% Final programming project – Due last day of classes: 01 May 2002
40% Open-book final exam – Thursday, 09 May 2002, 1-4 PM, Barton 225

Parallel Programming Project Topics

Listed below are some candidate projects. Other topics can be chosen with the permission of the instructor.

(1) Matrix-Matrix Multiplication
Investigate various parallel methods for both MxV and MxM of large matrices

(2) Parallel Assignment Problem
Auction problem formulated as dual.

(3) Parallel Linear Systems Solver
Candidate algorithms include interative: SOR, Jacobi, Gauss-Seidel
direct: QR, LU, Gaussian Elimination, wave front

(4) Parallel prefix, linear recurrences and semi-group algorithms
Both scalar and blocked versions of the problems.
Parametrized for various degrees of parallelism.

(5) Parallel methods to compute the connected components of a given graph
Include both weakly and strongly connected components.

(6) Eigenvalue problems.
Finding the max/min eigenvalue of a given matrix.