Swedish web site
Advanced Parallel Programming: Models, Languages, AlgorithmsFDA125, 2003VT
|
|
Course plan
Lectures
32 hours
Recommended for
Graduate (CUGS, ECSEL, ...) students interested in the areas of parallel
computer architecture, parallel programming, compiler construction, or
algorithms and complexity.
The course is hosted by the CUGS graduate school and classified as an Advanced
Course.
Nevertheless, interested undergraduate students with strong backgrounds in
software engineering are also welcome.
The course was last given
This is a new course. It complements the existing graduate course FDA101 on
Parallel Programming (4p), which is aliased to the undergraduate course TDDB78.
If there is enough interest, this course will be given every second year; it
will alternate with FDA001 Advanced Compiler Construction.
Goals
The course emphasizes fundamental aspects of parallel programming such as parallel architectures and programming models, performance models, parallel complexity classes, parallel algorithmic paradigms, parallelization strategies, and the design and implementation of parallel programming languages. Practical exercises help to apply the theoretical concepts of the course to solve concrete problems in different parallel programming models.
Prerequisites
Data structures and algorithms (e.g. TDDB57) are absolutely required; knowledge
in complexity theory and compiler construction is useful. Processprogramming
(e.g. TDDB63/68/72) and Parallel Programming (e.g. TDDB78 or TANA77) are useful
but not required. Most of the contents of FDA101, i.e. TDDB78, will be
summarized during this course.
Programming in C is necessary for the practical exercises.
Contents
I. General introduction: Parallel computer architectures (*).
II. Basic theory of parallel computation: PRAM model. Time, work, cost. NC.
Speedup and Amdahl's Law (*), Self-simulation and Brent's Theorem, Scalability
and Gustafssons Law (*). Fundamental PRAM algorithms (reduction, parallel
prefix, list ranking). PRAM variants, simulation results and separation
theorems.
III. PRAM emulations on distributed-memory architectures: Hashed address space,
Pipelining and Multithreading. Ranade's Fluent Machine and its cost-effective
massively parallel realization in hardware. Low-level synchronization
mechanisms.
IV. Message passing models: Delay model, classical BSP model of Valiant,
BSP-model of McColl, LogP, LogGP.
V. Distributed shared memory realizations in CC-NUMA architectures and software
DSM emulations. Memory consistency models.
VI. Parallel programming languages and environments: Fork, BSPlib, MPI (*),
OpenMP (*), HPF (*), Split-C, NESL, ZPL, Cilk, Linda, ...
VII. Parallel algorithmic paradigms and programming techniques, with example
problems: Parallel loops, static and dynamic loop scheduling. Data parallelism
(*). Parallel divide-and-conquer, recursive doubling. Synchronization
mechanisms in asynchronous computations and parallel data structures. Parallel
task queues. Synchronous and asynchronous pipelining. Domain decomposition and
irregular parallelism.
VIII. Generic parallel programming with skeletons. Skeleton-based programming
environments.
IX. Compiling for parallel computers: Dependence analysis, loop
transformations, loop parallelization, idiom recognition.
X. Optimization of data layout.
XI. Clustering and scheduling of processes.
Automatic parallelization of Modelica code.
Organization
Lectures, programming exercises, optional theoretical exercises for self-assessment.
Literature
Keller, Kessler, Träff: Practical PRAM Programming. Wiley Interscience, 2000.
ISBN 0-471-35351-5.
Further literature is announced on the course homepage.
Lecturers
Christoph Kessler, Welf Löwe.
Examiner
Christoph Kessler.
Examination
TEN1 Oral examination (4p) - We may switch to a written exam if the number of
participants should be higher than expected.
UPG1 Programming exercise (1p).
Credit
5 credits
Comments
There is a partial overlap in contents with FDA101 Parallel Programming /
TDDB78. Those topics appear in the lectures to make the course self-contained
but will not be taken up in the exam (TEN1). Accordingly, some of the lectures
are optional for those students who already took FDA101/TDDB78; these are
marked by an asterisk (*) in the Contents section above.
A main difference to FDA101 / TDDB78 / TANA77 is not only in depth but also in
scope: While FDA101 emphasizes scientific computing and numerical applications,
this course focuses on theory and non-numerical algorithms.
Course homepage
See the course homepage
http://www.ida.liu.se/~chrke/courses/APP/
for announcements, schedule, and further literature.
Page responsible: Director of Graduate Studies
