22C:177 (22M:178) Parallel and High Performance Algorithms  in Scientific Computing

Professor: Dr. Suely Oliveira
Office: MacLean Hall 101H - phone: 335-0731

Syllabus


PREREQUISITES

Any CS  or mathematics (numerical or linear algebra) course.
Knowledge of one  Programming language (C, Fortran, C++, Java, Pascal, etc...)


LECTURE HANDOUTS & HOMEWORKS
 
  • Week 1 :  Introduction to Parallel Computers and Programming.

    • Handout 1 (ps)       Handout 1 (pdf)   --  Using the SGI Power Challenge
    Handout 2 (ps):      Handout 2 (pdf)   --  Parallel Architectures.
    Handout 3 (ps)      Handout 3 (pdf)   -- Introduction to Parallel Programming; Welcome!
    Reading:   Chapters 2 and 3 ( Reference [1] ) and Chapters 1 and 2  (Reference [2])
    Article to read: "The Recent Revolution in High-Performance Computing" (by Horst D. Simon)
     
  • Week  2 :  Programming in Parallel Basics.

    • An example: trapezoidal rule.
    Reading:  Chapters  4  ( Reference [1])  and   4.1-4.2 (Reference [3])
     
  • Week 3 : More about Parallel Programming.

    • Handout 4 (ps)    Handoutt 4 (pdf) :  Collective Communication.
    Assignment 1 due date: February 16th.
    Reading: Chapter 5 ( Reference [1]).
     
  • Week 4 :  Performance, Speed-up,  Efficiency,

    • Overhead,  Scalability. Performance modeling.
     
  • Week 5  : Matrix-matrix product. Communicators.

    • Reading: Chapter 7 (Reference [1]).
    Handout 5 (ps)    Handout 5 (pdf): Comm. and Topologies
     
  • Week 6: Sequential and Paralllel algorithms for solving

    • Triangular systems of equations. Fan-in and Fan-out algorithms.
    Handout 6 (ps)    Handout 6 (pdf):  Backward Substitution
     
  • Week 7 :   Cholesky Factorization, fan-in and fan-out

    • algorithms, elimination trees, Sparse matrices algorithms, Parallel
    fine-grain and coarse grain algorithms, multifrontal methods.
    Assignment 2 due  date:  March 21st.
     
  • Week  8:  More about MPI.

    • Handout 7 (ps)    Handout 7 (pdf): Dealing with I/O.
     Handout 8 (ps)     Handout 8 (pdf): Grouping Data .
     
  • Week 9 :  Spring Break

    •  
  • Week 10 : LU factorization in parallel.

    • Assignment 3 due date:  April 6th
     
  •  Week  11:   Iterative Methods for Linear Systems.

    • Handout 9 (ps)    Handout 9 (pdf):  Classical Iterative Methods.
    Application: Laplace Equation in Parallel.
    Assignment 4  due date:   ???
     
  • Week 12 : Iterative Methods (Sequential Algorihtms

    • and Parallelization Issues).
    Handout 10 (ps)  Handout 10(pdf): Krylov Subspace Methods.
     
  • Week 13 (04/9-04/13):  Other topics on parallel programming.

    •  
  • Week 14 (04/16-04/20):  Multigrid and Parallelism (papers)

    •  
  • Week 15 (04/23-04/27): Graph Partitioning and Parallelism (papers)

    •  
  • Week  16 (04/30-05/4):  Parallelism and Applications (papers)

    •  

     

    Final Exam:  Thursday May 10th (7:30 am). Room MLH B13).
    Note: Most of our Final exam will be take home; bring that part
    with you to the classroom on May 10th at 7:30 am.

    COURSE DESCRIPTION: This is a graduate class on Parallel Algorithms, but advanced undergraduate students will be able to take this class without any problems. All the material  is covered starting from  sequential implementation. We will teach how to program in parallel in the first four weeks of the course; afterwards we will concentrate on parallel ideas and algorithms, and the homeworks will cover parallel implementations for those algorithms. I first programmed in parallel in 1986; ten years later,  I taught a parallel algorithms class at Texas A&M University.  Because this is an active area of research  I always  cover different  topics. Depending on the interest of the class we may change the syllabus slightly.

    TOPICS:  In this class we aim to cover parallel methods useful in various areas of applications. For example Direct Methods and Iterative Methods for solving systems, and the diverse issues related to matrix factorizations in the parallel computing context (elimination trees for example). Some of the systems of equations we solve  represent discretizations of differential equations from Science and Engineering problems, but no background in differential equations is necessary for this course. We also cover other topics which are useful in the understanding of parallel algorithm design.

    PROJECT: Your grade will be 60% from assignments, 20% from your project and 20% from a final exam. The project is an important part of this course. We will be working in groups and have presentations in the classroom about some of the projects.

    TEXTBOOK:   Parallel Programming with MPI (Peter Pacheco) available at the IMU bookstore.

    OTHER  READING MATERIAL
     

  • "The Recent Revolution in High-Performance Computing" (by Horst D. Simon)

    •  
  • Parallel Numerical Linear Algebra ( by James W. Demmel, Michael  T. Heath and Henk A. van der Vorst)

    •  
  • MPI The Complete Reference  (by Snier, Otto, Huss-Lederman, Walker, Dongarra)


    • SIMILAR COURSES ELSEWHERE

    MIT
    U. California, Berkeley (1998)
    U. California, Berkeley (1999)
    U. Colorado, Boulder
    U. of Illinois
    Cornell University
    U. Tennessee, Knoxville

    BOOKS ON RESERVE:  For sequential algorithms we will we will use various books, a few papers, and also my own handouts . The books below are on reserve at the Division of Mathematical Sciences Library ( first level of MacLean Hall). Most of the books listed below are only reference books and you are not required to buy them for this course.  I will mention in class when you should consult these books.

    1
    P. Pacheco.

    Parallel Programming with MPI.
    Morgan Kaufmann Publishers, Inc, San Francisco, 1997.
    2
    J. Dongarra, I. Duff, Sorensen, D., and H. Van der Vorst.

    Numerical Linear Algebra for High-Performance Computers.
    SIAM, Philadelphia, PA, 1998.
    3
    V. Kumar, A. Grama, A. Gupta, and G. Karypis.

    Introduction to Parallel Computing.
    Benjamin/Cummings, 1994.
    4
    M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra.

    MPI:The Complete Reference.
    MIT Press, Boston, 1996.
    5
    James W. Demmel.

    Applied Numerical Linear Algebra.
    SIAM Publ., Philadelphia, PA, 1997.
    6
    G. W. Stewart.

    Afternotes on numerical analysis.
    Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996.
    7
    L. N. Trefethen and D. Bau, III.

    Numerical Linear Algebra.
    SIAM, Philadelphia, 1997.

    OTHER LINKS:

    Notes on SGI power Challenge
    to login :  telnet silicon.weeg.uiowa.edu
    support staff: http://www.uiowa.edu/~itsarcs/staff.html

    How to Submit your programs electronically

    Matlab can be used for plots or sequential programming:
        Matlab
        Matlab Help Desk (local access file: file:/usr/apps/matlab/=/help/helpdesk.html )                                          ):

    Programming Languages you can use for homeworks:
    F77,     Fortran 90  ,        C    and       C++:

    We will cover some MPI commands during the course.
    For more information about MPI check:   Argonne


    I need to hear from anyone who has a disability which may require some modification of seating, testing or other class requirements so that appropriate arrangements may be made. Please see me after class or during my office hours