COMP 322: Fundamentals of Parallel Programming (Spring 2013)

...

Course Objectives

The goal of COMP 322 is to introduce you to the fundamentals of parallel programming and parallel algorithms, using a pedagogical pedagogic approach that exposes you to the intellectual challenges in parallel software without enmeshing you in lowthe jargon and lower-level details of different today's parallel systems.  A strong grasp of the course fundamentals will enable you to quickly pick up any specific parallel programming model that you may encounter in the future, and also prepare you for studying advanced topics related to parallelism and concurrency in more advanced courses such as COMP 422.

To ensure that students get a strong grasp of parallel programming foundations, the classes and homeworks will place equal emphasis on advancing both theoretical and practical knowledge. The programming component of the course work will initially use a simple parallel extension to the Java language called Habanero-Java (HJ), developed in the Habanero Multicore Software Research project at Rice University.  Later in the course, we will introduce you to some real-world parallel programming models including Java Concurrency, .Net Task Parallel Library, MapReduce, CUDA and MPI. The use of Java will be confined to a subset of the Java language that should also be accessible to C programmers --- advanced Java features (e.g., wildcards in generics) will not be used. An important goal is that, at the end of COMP 322, you should feel comfortable programming in any parallel language for which you are familiar with the underlying sequential language; any parallel programming primitives should be easily recognizable based on the primitives studied in COMP 322.

Course Overview 

COMP 322 provides the student with a comprehensive introduction to the building blocks of parallel software, which includes the following concepts that end, the main pre-requisite course requirement is COMP 215 or equivalent.  This course should be accessible to anyone familiar with the foundations of sequential algorithms and data structures, and with basic Java programming.  COMP 221 is also recommended as a co-requisite.The pedagogical approach will introduce you to the following foundations of parallel programming:

• Primitive constructs for task creation & termination, collective & point-to-point synchronization, task and data distribution, and data parallelism
• Abstract models of : parallel computations and , computation graphs, Flynn's taxonomy (instruction vs. data parallelism), PRAM model
• Parallel algorithms and for data structures including that include arrays, lists, strings, trees, graphs, matricesand key-value pairs
• Common parallel programming patterns including task parallelism, undirected and directed synchronizationpipeline parallelism, data parallelism, divide-and-conquer parallelism, map-reduce, concurrent event processing including graphical user interfaces. 

These concepts will be introduced in four modules: 

1. Deterministic Shared-Memory Parallelism: creation and coordination of parallelism, collective & point-to-point synchronization (phasers, barriers), abstract performance metrics (work, span, critical paths), Amdahl's Law, weak vs. strong scaling, data races and determinism, data race avoidance (immutability, futures, accumulators, dataflow), deadlock avoidance, abstract vs. real performance (granularity, scalability), parallel sorting algorithms.
2. Nondeterministic Shared-Memory Parallelism and Concurrency: critical sections, atomicity, isolation, high level data races, nondeterminism, linearizability, liveness/progress guarantees, actors, request-response parallelism
3. Distributed-Memory Parallelism and Locality: memory hierarchies, cache affinity, false sharing, message-passing (MPI), communication overheads (bandwidth, latency), MapReduce, systolic arrays, accelerators, GPGPUs.
4. Current Practice — today's Parallel Programming Models and Challenges: Java Concurrency, locks, condition variables, semaphores, memory consistency models, comparison of parallel programming models (.Net Task Parallel Library, OpenMP, CUDA, OpenCL); energy efficiency, data movement, resilience.

Prerequisite 

The prerequisite course requirement is COMP 215 or equivalent.  This course should be accessible to anyone familiar with the foundations of sequential algorithms and data structures, and with basic Java programming.  COMP 221 is also recommended as a co-requisiteLaboratory assignments will explore these topics through a simple parallel extension to the Java language called Habanero-Java (HJ), developed in the Habanero Multicore Software Research project at Rice University.  The use of Java will be confined to a subset of the Java 1.4 language that should also be accessible to C programmers --- no advanced Java features (e.g., generics) will be used.  An abstract performance model for HJ programs will be available to aid you in complexity analysis of parallel programs before you embark on performance evaluations on real parallel machines.  We will conclude the course by introducing you to some real-world parallel programming models including the Java Concurrency Utilities, Google's MapReduce, CUDA and MPI.  The foundations gained in this course will prepare you for advanced courses on Parallel Computing offered at Rice (COMP 422, COMP 522). 
 
Since the aim of the course is for you to gain both theoretical and practical knowledge of the foundations of parallel programming, the weightage for course work will be balanced across homeworks, exams, and lab attendance.  

Textbooks

There are no required textbooks for the class. Instead, lecture handouts are provided for each module as follows:

• Module 1 handout (Deterministic Shared-Memory Parallelism)
• Module 2 handout (Nondeterministic Shared-Memory Parallelism and Concurrency)
• Module 3 handout (Distributed-Memory Parallelism and Locality)
• Module 4 handout (Current Practice — today's Parallel Programming Models and Challenges)

You are expected to read the relevant sections in You will be expected to read each lecture handout before coming to the lecture.  We will also provide a number of references in the slides and handouts.

However, there There are also a few optional textbooks that we will draw from quite heavily.  You are encouraged to get copies of any or all of these books.  They will serve as useful references both during and after this course:

...