B673: Advanced Scientific Computing

Parallel Programming - Spring 2009

B673

Contents

• General information
• Course description
• Tentative course outline
• Assignments
• Grading policies
• Course Notes
• RSS feed for the class Web Board

Instructor:

• Randall Bramley / bramley@cs.indiana.edu
• email: bramley.cs.indiana.edu
• 301A Lindley Hall

Class meets in LH115, Mon-Wed 4-5PM. Later we'll just do it on Mondays, once you get up to speed.

Prerequisites:

• A working knowledge of C, C++, or Fortran. Enough UNIX to write, manage, and run multifile programs, and to time algorithms and codes
• Linear algebra, sufficient to understand and code operations such as the product of two matrices, dotproducts, and matrix-vector products

This course is primarily on practical aspects and modeling for parallel computing. Another course, B524, covers the programming languages aspects of parallelism, and is taught in alternating semesters with B673. B673 concentrates more on applications, performance engineering of parallel codes, and emerging issues in high-performance computing: file systems, data management, and access to online data systems, instruments, and sensors.

Textbooks:
Much of the course material is on the Web and covered in class. There are some outstanding books on the area of parallel computing, generally concentrating on one aspect or another. If you want to buy one, my recommendation is to wait until after the course is over, when you know what material is most useful to you. Do not print off the books listed below It is a major waste of paper to do so, our use of them will be negligible, and the online versions are often updated and better curated.

MPI: The Complete Reference by Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack Dongarra is the most useful one for looking up MPI functions and their calling sequences. This covers MPI-1.

Using MPI-2: Advanced Features of the Message Passing Interface by William Gropp, Ewing Lusk and Rajeev Thakur. This covers the MPI-2 standard, with some extensions that are not fully implemented yet by any supplier. It is likely that most of MPI-2 will be available by mid-November 2004.

Parallel Computing Works! by Geoffrey C. Fox, Roy D. Williams, and Paul C. Messina is now somewhat dated but its description of applications is still excellent. Unfortunately the Web version is not very readable.

Designing and Building Parallel Programs, by Ian Foster is another book that concentrates on the programming aspects of parallel machines.

Sourcebook of Parallel Computing by Jack Dongarra et al has more sophisticated applications than we will implement in this class, but the chapters on parallel I/O, graph partitioning, and numerical linear algebra are relevant.

Course Description

Course Outline

1. Hardware taxonomies and architecture
   1. Memory organization
      1. Shared memory machines
      2. Distributed memory machines and interconnection networks.
      3. Hybrid memory machines; CC-NUMA
   2. Vector processing
   3. Parallel programming models: SIMD, SPMD, MIMD
2. Performance modeling and analysis
   1. The n_1/2-r_infinity vector model
   2. Speedups and parallel efficiency; Amdahl's Law; isoefficiency curves
   3. Message passing models
   4. Scalability definitions and models
3. Model problems and parallel algorithms
   1. Dense matrix operations
   2. Fast Fourier Transforms
   3. Sparse matrix operations
   4. N-body problems
   5. PDE solvers and domain decomposition
4. Software and tools for parallelism
   1. Compilation techniques.
   2. Parallel languages
   3. Message passing interface
   4. Pthreads and OpenMP
   5. Performance evaluation
5. Parallel I/O

• Coding Projects: Grades are based on projects. A final exam is required by the university. It will be a project like the others, due on or before the date/time of the last final of the semester.

• Cheating Policy: Don't.

• Hand ins: Since the class is small enough go ahead and create a tar file of your assigment and mail it to me. Be sure to mail it from an indiana.edu domain, and delete all object files (.o), executable files, and other binary files. You can create a tar file of a directory called dir by

      cd dir
      cd ..
      tar cvf dir.tar dir
  

  and then mail me the resulting dir.tar file. Be sure to not include any object files (.o files), compiled executable files, or other large binary files; that would clog up the email system. Until announced otherwise, we'll do this for all projects.