Parallel Programming

Prof. Christoph von Praun

Summary

This is an undergraduate (3rd year) introductory class for parallel programming. The course is organized along the tiers of parallelism. The tiers categorize abstractions and concepts that a software developer can choose when crafting a parallel program. The tiers are from higher to lower abstraction levels:
  1. automatic or implicit parallelism, e.g., parallel libraries;
  2. deterministic parallelism, e.g., at the level of independent loops;
  3. explicitly synchronized, e.g., shared memory with locks;
  4. low-level concurrent programming with data races, e.g., lock-free data structures.
The goal of the class is to introduce fundamental principles of parallel systems and to expose students to all tiers in the architecture of a parallel system. Within the undergraduate curriculum, the course serves as a platform for further exploration in specialized classes. This course puts emphasis on code examples and thus has a significant share of lab sessions and programming projects. We chose the programming language X10 as the core technology since it facilitates learning and rapid application of concepts at different abstraction layers and programming models. The language permits to specify common forms of parallelism, data sharing, distribution, and synchronization with succinct syntax and support for an eclipse-based IDE.

The structure and principles underlying this course have been presented at the X10 Workshop associated with the SIGPLAN Conference on Programming Languages Design and Implementation (PLDI) 2011. [paper pdf] [talk pdf].


News

Lecture materials and exercises have been update to X10 Version 2.2.1.


Outline

Topic Lecture Materials Assignments

1 Introduction [pdf] Scaling, Amdahl's Law and Prime Number Testing [pdf]
Solution [PrimePrinterX10.zip] [PrimePrinterJava.zip] [PrimePrinterJavaExecutor.zip] [PrimePrinterScala.zip]
2 Simple Model for Parallel Programs and Program Executions (Tier 4) [pdf] Numerical Integration [pdf]
Solution [NumericalIntegration.zip]
3 Tiers of Parallelism [pdf]

 Concurrent Objects, Linearizability, Race Conditions [pdf]
4 Tier 1: Automatic / Implicit Parallelism [pdf]
5 Tier 2: Deterministic Parallelism [pdf]
6 Patterns for Parallel Programming [pdf]
7 Tier 2: Data Parallelism [pdf] Geometric Decomposition [pdf]
HeatTransfer Fragment [HeatTransfer_fragment.zip]
HeatTransfer Solution [HeatTransfer.zip]
Recursive Data [pdf]
Reduction and Scan [ParallelSum.zip]

8 Tier 2: Task Parallelism [pdf]
 MapReduce [pdf]
MapReduce Fragment [MapReduceFragment.zip]
MapReduce Solution [MapReduce.zip]
Merge Sort [pdf]
MergeSort Solution [MergeSort.zip]
Traveling Salesman [pdf]
Traveling Salesman (simple sequential and parallel with dynamic programming) [Tsp.zip]
9 Tier 2/3: Pipeline Parallelism [pdf]

10 Tier 3: Explicitly Synchronized Data-Race Free Parallelism [pdf] [ConcurrentQueue.zip]
11 Tier 4: Low-Level Parallelism with Race Conditions [pdf]

 [NonBlockingQueue.zip]
12 Tier 4: Low-Level Programming with Shared Memory [pdf] Producer-Consumer [pdf]

13 Concluding Remarks: Topics we have not addressed ... [pdf]




Lecture materials are available in source format (Apple Keynote) on request.
The example codes and solutions to the exercises are based on X10 v2.2.1.
You can import the solutions of the programming assignments into your eclipse workspace as follows:
(1) Start eclipse, (2) Menu File-Import, (3) Select General-Existing Project into Workspace, (4) Specify archive file, (5) Finish.

X10 Tutorial

Literature

Introduction, the era of multicore programming

Models for parallel computation

Scalability and performance analysis

Higher-level parallel programming models

Books


X10 Resources

Examples and programming exercises in this course will be based on the programming language X10.

Last change: June 21, 2011.