22C:296:002  Seminar on Computer Science:

PARALLEL ALGORITHMS

Classes: MLH 114 or  MLH B5 (computer lab)
Tu-TH 10:55 am - 12:10 pm
Professor: Dr. Suely Oliveira   email: oliveira@cs.uiowa.edu
Office: MLH 101H - phone: 335-0731  
Tentative Office hours: Mondays (1:00-2:30) and Thursdays (9:30-11:00)

TA: Sang-Cheol Seok  email: sseok@cs.uiowa.edu
Office: MLH 101J - phone: 353-2549
Tentative Office hours: Tuesdays and Fridays 1:00-2:30

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 contact me during my office hours.



Textbook: Parallel Computing.  (we will cover parts of this book)
http://www.booksites.net/kumar/

Prerequisites: There are no prerequisites for this course. Knowledge of a  computer  language and an undergraduate course in algorithms or linear algebra will be helpful.

Grades : there will be one written exam (30%) , one project (30%)  and 3-5 programming assignments (40%). The written exam will be in  the middle  of the semester based on the parts of the book we  cover until then. In the last 3 weeks  of the semester we will have project presentations (these can be parallel issues in various  areas of research as mentioned next)

Overview:  Nowadays High Performance Computing has almost become  a synonym for Parallel Computing. In Scientific Computing, clusters have  replaced high-end scientific workstations. In this class we  cover Parallel Algorithms  ideas and implementation issues for parallel computers or network of workstations.  We will work with tools for writing  parallel portable programs. We will  learn theoretical  prediction of performance and verify these with computational results form applications. The parallel algorithms we cover are from Computational Linear Algebra or algorithms.  Both Sequential and Paralell versions are introuced  in this class.  So no prior knowledge  of the algorithms is necessary. Student projects  can include applications in the broad  area of scientific computing (numerical methods, data mining, information retrieval, and  computational biology).

Links/Articles to read or other references:

NCSA IA64 Linux Cluster
 

Parallel Programming with MPI  (by Peter Pacheco)

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

Tutorial on MPI: The Message-Passing Interface (by William Gropp)

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

Course Accounts



Theory:
 
  • Introduction and Parallel Programming Platforms (parts of chapters 1, 2 and 3)

  • Basic Communication Operations (chapter 4)

  • Analytical Modeling of Parallel Programs (chapter 5)

  • Programming using the Message Passing Paradigm and  Shared Address Space Platforms (chapter 6)

  • Dynamic Programming and Graph Algorithms (chapters 10 and 12)

  • Systems of Equations (parts of Chapter 8)



  •  Some MPI Programming handouts:

  •  Introduction to Parallel Computers and Programming
    Handout (pdf)   -- Basics
  • Handout -- Using the cluster
      
  •  More about Parallel Programming.
  • get_data.c     serial.c     trap.c
    Handout  (pdf)
    :  Collective Communication.
     
  • Matrix-matrix product. Communicators.
  • Handout  (pdf): Communicators and Topologies

  • Sequential and Paralllel algorithms for solving
  • Triangular systems of equations. Fan-in and Fan-out algorithms.
      Handout (pdf):  Backward Substitution

  • Handout (pdf):  Grouping Data for Communication
  •  


    Applications:
    In the last few weeks we will concentrate on applications and projects.

    Projects Summaries

    Projects Grades