MET CS 786 Parallel and Distributed Computation

                                              Course Calendar - SPRING 2000

Week 1: R 01/13 Administrative.
    Introduction: Why concurrency? Large problems, their parallelization and granularity. Parallel vs. distributed computations. Network topologies (static/dynamic); Examples of fixed network topologies: arrays, trees, hypercubes, shuffle exchange; Example of simple parallelism: prefix computation, adding in a tree.
    Trends in parallel computing: applications, technology, architecture, system design, supercmputers. Parallel programming models: shared address space, message passing, data parallel.
    Readings: handout, Culler/Singh Ch.1

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 style.
    Readings: Culler/Singh, Ch. 2

Week 3: R 01/27 Parallelization. Performance measures: speed up, time complexity, efficiency, communication cost, machine dependent measures.
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

 Readings: handout,
 I. Foster.  Designing and Building Parallel Programs. Addison Wesley Publishing Company, 1994.
Message Passing Interface(MPI) Tutorial

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