You are here

Rationale for Programming Topics

The material is organized into three subtopics: Paradigms and notations, correctness, and performance. We discuss these in separate sections below. A prerequisite for coverage of much of this material is some background in conventional programming. Even though we advocate earlier introduction of parallelism in a student's programming experience, basic algorithmic problem solving skills must still be developed, and we recognize that it may be easier to begin with sequential models. Coverage of parallel algorithms prior to this material would allow the focus to be exclusively on the practical aspects of parallel programming, but they can also be covered at the same time as necessary and appropriate.

Paradigms and Notations: There are different approaches to parallel programming. These can be classified in many different ways. Here we have used two different ways of classifying the models. First, we classify the paradigms by the target machine model: SIMD (single instruction multiple data) is the paradigm in which the parallelism is confined to operations on (corresponding) elements of arrays. This linguistic paradigm is at the basis of Streaming SIMD Extension (SSE) or Altivec macros, some database operations, some operations in data structure libraries, and the languages constructs used for vector machines. Shared-memory is the paradigm of OpenMP and Intel’s Thread Building Blocks, among other examples. Distributed memory is the paradigm underlying message passing and the MPI standard. A hybrid model is when any of the previous three paradigms co-exist in a single program. The logical target machine does not have to be identical to the physical machine. For example, a program written according to the distributed memory paradigm can be executed on a shared-memory machine and programs written in the shared-memory paradigm can be executed on a distributed memory machine with appropriate software support (e.g., Intel’s Cluster OpenMP). A second way to classify programming approaches is according to the mechanisms that control parallelism. These are (mostly) orthogonal to the first classification. For example, programs in the SPMD (single program multiple data) paradigm can follow a distributed-memory, shared-memory and even the SIMD model from the first classification. The same is true of programs following the data parallel model. The task spawning model can work within a distributed or shared-memory paradigm. The parallel loop form seems to be mainly used with the shared-memory paradigm, but High-Performance Fortran merged the loop model with the distributed memory paradigm. The students are expected to be familiar with several notations (not languages since in many cases support comes from libraries such as MPI and BSPlib). Not all notations need to be covered, but at least one per main paradigm should be. An example collection that provides this coverage would be Java threads, SSE macros, OpenMP, and MPI. Parallel functional languages are optional.

Correctness and semantics: This set of topics presents the material needed to understand the behavior of parallel programs other than the fact that there are activities that take place (or could take place) simultaneously. Material covers:

  1. Tasking, including ways to create parallel tasks and the relationship between implicit tasking and explicit tasking (e.g., OpenMP vs. POSIX threads).
  2. Synchronization, including critical sections and producer consumer relations.
  3. Memory models. This is an extensive topic and several programming languages have their own model. Only the basic ideas are expected to be covered.
  4. Concurrency defects and tools to detect them (e.g. Intel’s thread checker).

Performance: The final group of topics is about performance - how to organize the computation and the data for the different classes of machines. The topics here are self-explanatory.