15-849C: Parallel Computing

Credit: 1 Graduate Core Unit or 12 University units

Time and place: M-W 10:30-11:50, Wean 4615A

This course will cover various topics in parallel computing including parallel languages and parallel algorithms. The class will look at both theoretical and practical issues, and will include programming assignments on various parallel machines. The course should be appropriate for graduate students in all areas and for advanced undergraduates.

Topics to be covered:

• Algorithms
  • Models
  • Techniques
  • Sorting and Searching
  • Graph algorithms
  • Numerical algorithms
  • Computational geometry
• Programming Models
  • Shared memory
  • Message Passing
  • Data Parallel
  • Automatic parallelization
• Applications (case studies)
  • Protein folding
  • Earthquake simulation

Assignments:

Some links:

• Machine pointers for assignment 1
  • Sun HPC 10000 Server (Starfire)
  • SGI/Cray Origin 2000
  • SGI/Cray T3E
• Resources on parallel computing
  • Parascope
  • List of top 500 supercomputer sites (an explanation)
• Information on Pthreads (shared memory programming)
  • Sun's Multithreaded Programming Guide
  • You can find a complete list of pthread functions here
  • Threads FAQ
  • Code samples from Programming with POSIX® Threads, D. R. Butenhof, Addison-Wesley.
  • How to Program with Threads: An introduction to multithreaded programming by Lewis and Berg.
  • parallel multithreaded quicksortprsort.c
• Information on MPI
  • The MPI Resource Center
  • Mississippi state MPI page including an MPI FAQ with a good list of pointers
  • Argone MPI page
• Information on PSC (and using the T3E)
  • PSC User's guideand specifics on the T3E (jaromir.psc.edu)
  • Software available on the T3E
  • MPI for the Cray T3E
  • To get started the following should work:

      telnet jaromir.psc.edu
    
      cc -o prog prog.c   (should compile files with mpi in them
                           this assumes "module load mpt" is in your default .login file)
      mpprun -nx prog     (will run your program on x processors, for x <= 32)
    

    To run on more than 32 processors you need to use the job queue.

Schedule:

Readings

• Parallel Algorithms. Guy Blelloch and Bruce Maggs. In the Computer Science and Engineering Handbook. CRC Press, 1996.
• Introduction to Parallel Algorithms: Arrays, Trees and Hypecubes. Tom Leighton. Morgan Kaufmann, 1992.
  3.2, The Butterfly, Cube-Connected-Cycles, and Benes Network (439-456)
  3.4, Packet Routing Algorithms (511-520)
  3.6, Simulating a Parallel Random Access Machine (697-703)
• BSP Machine parameters
• Cray T3E overview
• List Ranking and List Scan on the CRAY C-90. Margaret Reid-Miller. Journal of Computer and System Sciences, December 1996.
• Chapters 3 (Merging) and 4 (Sorting) from "The Design and Analysis of Parallel Algorithms" by Selim Akl. Prentice-Hall, 1989.
• Fast Parallel Sorting under LogP: Experiences with the CM5. A. C. Dusseau, D. Culler, K. Schauser, R. Martin.
• Numerical Algorithms
• Chapter 3 (pages 108--119) of "An Introduction to Parallel Algorithms" by Joseph Jaja. This is a reading on the Euler Tour technique.
• Getting Started with Posix Threads. Here is a local poscript version (since the link can be quite slow).
• Space-Efficient Implementation of Nested Parallelism
• A User's Guide to MPI, by Peter Pacheco --- this paper is a draft and has some bugs. After reading it I would suggest The Design of a Standard Message-Passing Interface for Distributed Memory Concurrent Computers instead (or in addition).
• Simulating Physical Phenomena (the finite-volume method and itterative solutions to linear systems of equations).

Grading