Computer Science 156: Parallel and Real-Time Computation
What this course is about
It is a thrill to get computers to solve problems. It is a bigger thrill to
get N > 1 computers to cooperate in solving a single problem, especially a big
problem. As the speed of processing elements heads toward an ultimate
brick-wall (as determined by the speed of light), it becomes increasingly
important to be able to use multiple computers, or multiple processors within a
single computer, to work together effectively, for purposes of speedup and
reliability. We study this issue from three angles: algorithms, architecture,
and programming languages. We will construct some programs on actual parallel
processors. Then we discuss a loosely-related issue: models and languages for
computation in real-time.
Instructor
Robert Keller 242 Olin (office hours 4-5 p.m. Tu, 3-4 MW, or whenever), keller@cs.hmc.edu, x 18483
Catalog Description
Characteristics and applications of parallel and real-time systems. Specification techniques, architectures, languages, design, and implementation. 3 credit hours.
Prerequisites: Prerequisites: CS 110 and 140 (131 recommended).
Requirements and Grading
There are three parts, conducted roughly in sequence, although there may be some overlap:
- Tutorial part: Problems (including programming, intended to be individual)
- Reporting part: Students will give talks on topics or papers (teamwork is acceptable)
- Project part: Development of a substantial parallel or real-time computing application or system component (teamwork is acceptable)
Textbooks
For the parallel computation part (about 80% of the course):
("PP") Barry Wilkinson and Michael Allen, Parallel Programming, Prentice-Hall, 1999, ISBN 0-13-671710-1.
For the real-time part (about 20%):
No specific text will be required for the real-time part.
Outline (tentative, approximate, subject to reordering)
- (1 day) Basic ideas and vocabulary of parallel computing (PP chapter 1)
- (2 days) Message-passing computation, MPI (PP chapter 2)
- (1 day) Embarassingly-parallel problems (PP chapter 3)
- (2 days) Partitioning (PP chapter 4)
- (1 day) Pipelining (PP chapter 5)
- (1 day) Synchronous computations (PP chapter 6)
- (1 day) PRAM model (PP appendix D)
- (1 day) Load balancing and termination detection (PP chapter 7)
- (2 days) Programming with shared memory (PP chapter 8)
- (2 days) Sorting algorithms (PP chapter 9)
- (2 days) Numerical algorithms (PP chapter 10)
- (1 day) Image processing (PP chapter 11)
- (2 days) Searching and optimization, genetic algorithms (PP chapter 12)
- (1 day) ZPL language, Fortran-based languages
- (1 day) Functional language approach; Linda, Javaspaces
- (1 day) NESL model and language
- (1 day) Scheduling algorithms
- (1 day) Rate-Monotonic scheduling
- (1 day) Real-time languages
- (1 day) Real-time operating systems
- (1 day) Temporal logic and specifications