This course focuses on
solving computational problems in parallel,
beginning with a brief study of the fundamental
limits of parallelism. We will cover parallel
algorithms from a variety of domains, including:
linear algebra (e.g., solving linear equations,
performing FFT transforms), graph theory (e.g.,
message routing), combinatorics (e.g., sorting
and searching, a-b search, generating permutations,
and bin-packing), and synchronization (e.g.,
systolic pipelines, barriers, shared memory
read/write). |
A theme of the course will be the high sensitivity
of algorithms and their performance to architectural
variation in machines. Another theme will be
the ties between parallel and distributed computing
that enable the efficient distributed execution
of some parallel algorithms. Algorithm performance
will be analyzed mathematically, and a selection
of algorithms will be programmed and analyzed
experimentally. Thus, students will be able
to empirically evaluate the validity of insights
obtained from the theoretical study of parallel
algorithms. At the same time, the programming
activity will introduce students to the tools
of parallel computing, from programming languages
to debuggers, to data visualization aids.
|
