MET CS 786 Parallel and Distributed Computation
Week 2: R 01/20 Parallel Programs: parallel vs. sequential
programming. Case studies: Fixed size problems with regular grid (Oceans,
partial differential equations) and irregular grid (galaxies simulation,
Ray Tracing); Variable size problems (transaction processing). Stages in
the parallelization process (decomposition , assignment, orchestration,
mapping) and their dependence from problem and machine. Identifying
concurrency analytically and through concurrency profiles. Limits of parallelization:
Amdahl's law. A closer look at Oceans: Decomposition versions depending
on loop paralleliztion and/or restructuring of the sequential algorithm,
and using problem knowledge to devise a new parallel algorithm. Implementations
in the date parallel, shared address address space and message passing
Readings: Culler/Singh, Ch. 2
Week 3: R 01/27 Parallelization. Performance measures: speed
up, time complexity, efficiency, communication cost, machine dependent
Case study: Parallel Search: Shared memory search of a) sorted ( EREW search, CREW binary and (N+1)-ary search) and b) random sequence (SIMD search, fixed interconnection search in a tree and mesh).
Readings: handout, Akl Ch.5
Case study: SGI/Cray Origin: architecture overview and programming paradigms. ( Introduction to the PCA and O2K)
Readings: handout, Information for new Origin and 2K users, SGI PCA and SGI Documentation
Week 4: R 02/03 Parallel Programming: Shared Memory - the SGI MIPSpro C/C++ Parallelizing Pragmas, OpenMP Pragmas.
Week 5: R 02/10 Parallel Programming: Message Passing MPI
Week 6: R 02/17 Case study: Parallelization of matrix operations: transposition (mesh, shuffle, EREW), multiplication (mesh)
Readings: handout, Akl. Ch.7.1, 7.2, 7.3
Week 7: R 02/24 Case study: Systems of linear
equations: direct and iterative methods, backsubstitution, Gauss-Jordan
elimination, Gauss-Seidel elimination, modified Gauss-Seidel elimination
Readings: handout, Akl. Ch. 8.1, 8.2
Week 8: R 03/02 class cancelled
03/09 No Class. Spring Recess
Week 9: R 03/16 Cash coherence and Memory Consistency
Readings: Culler/Singh Ch. Ch.5.1, 5.2
Week 10: R 03/23 Embedding. Routing: store & forward; cut-through.
Communication patterns: one-to all, all-to-all
broadcast, one-to all, all-to-all personalized communication. Shortest path, minimum spanning trees.
Readings: Kumar, Grama, Gupta, Kapyris, Ch.2.5-2.8, 3.1-3.2
Review for Test 1.
Week 11: R 03/30 Test 1.
Communication patterns (continued): one-to all, all-to-all personalized communication.
Shortest path, minimum spanning trees.
Readings: Kumar, Grama, Gupta, Kapyris, 3.3-3.8
Week 12: R 04/06 Scalable multiprocessors.
Readings: Culler/Singh Ch. 7
Week 13: R 04/13
Week 14: R 04/20
Week 15: R 04/27 Test 2
Week 16: R 05/04 Student Presentations
Week 17: R 05/11 Student Presentations