Harvey Mudd College
Parallel and Real-Time Computation
Spring 2011
Robert
Keller
253 Olin, x 18483, keller at cs hmc edu
Prerequisites: CS 105, or permission of
instructor. Note: In the spring semester 2011, I am relaxing the former requirement
of CS 140.
Trailer:
It is a thrill to
make a computer solve an interesting problem. It is a bigger thrill to get a
large number of processors to cooperate in solving a single problem. As the
speed of processors is now reaching an ultimate brick-wall (as determined by
the speed of light), it is increasingly important to be able to use multiple
computers, or multiple processors (ÒcoresÓ) 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 and run them on parallel processors. Speed is
not the only use of parallel computing, however. Some problems just naturally
decompose into parallel components. An example is a web service, where an
arbitrary number of clients be accessing the site at the same time. There will
be typically be some shared resources that need to be managed. Then we discuss a
related issue: models and languages for computation in real-time, where
deadlines are important.
á
Computational
and Programming Paradigms:
o
SIMD,
MIMD, SPMD, Vector/Array Processing
o
Multi-threading
o
Clusters
and message-passing
o
GPU
(Graphics Processing Unit) computing
o
Grid/Cloud/Crowd
computing, virtual supercomputers
o
Map/Reduce
paradigm
á
Computational
Models:
o
PRAM
o
Work-Depth
Model
o
Dataflow
o
Swarm
Intelligence
o
Cellular
Automata
o
Petri-Net-like
Models with Timing
o
Rate-Monotonic
Scheduling
o
Model-Checking
á
Languages
and Libraries
o
Java
o
Cilk++
o
MPI
o
NESL
o
Erlang
o
CUDA,
Open CL
á
Algorithms
o
Simulations
o
Iterative
Linear Solvers
o
Searching
o
Sorting
o
N-Body
Problems
o
Graph
Problems
á
System
Issues
o
Processor-Memory
Access
o
Memory
Models
o
Granularity
o
Communication
Structure
o
Load
Balancing
We will be using
a ÒCommunity of ScholarsÓ model. This assumes that you are in the course
primarily to learn, and thus you will be a regular and diligent participant.
You will take part in discussions, give presentations, and bring in new
discoveries and questions. Students who participate fully will receive a grade
of ÒAÓ. Students who participate less will receive a lesser grade. There might
be an exam about 2/3 of the way through, but if all is going well, maybe we can
do without it. Activities will include:
Only one text is required to start. It This
does not cover all topics, but will be a useful source for the multithreading
aspect.
Brian Goetz, et al., Java
Concurrency in Practice
(paperback)
Addison-Wesley Professional (May 19, 2006)
ISBN-10: 0321349601, ISBN-13: 978-0321349606
Other possible may be referenced as we go,
such as:
Thomas Rauber and Gudula RŸnger
á
Springer;
1st Edition (March 10, 2010)
á
ISBN-10: 364204817X, ISBN-13: 978-3642048173
David B. Kirk
and Wen-mei W. Hwu
Programming
Massively Parallel Processors: A Hands-on Approach (paperback)
á
Publisher: Morgan Kaufmann; 1 edition (February
5, 2010)
á
ISBN-10: 0123814723, ISBN-13: 978-0123814722