Writing Parallel Programs

To write a parallel program, we fundamentally need to subdivide (partition) the work to be done among the various available cores. There are two main approaches to doing this: Data-parallelism and Task-parallelism.

2.1 Partitioning Paradigms

To understand the difference, suppose a professor has to grade 100 exams, each consisting of 5 questions. She is helped by 4 teaching assistants (TAs). Together they form 5 “cores”.

Task-Parallelism

We subdivide the type of operation (the task) to be performed. The professor grades question 1 of all 100 exams, TA A grades question 2, TA B grades question 3, etc. In computer science, this means that different cores execute different instructions on distinct (or even identical) parts of the data.

Data-Parallelism

We subdivide the set of data. The 100 exams are divided into 5 stacks of 20 exams each. Each “core” takes a stack and grades all 5 questions of those 20 exams. In computer science, this means that all cores execute the same instructions, but applied to different portions of data.

2.2 The Coordination Problem

When cores are not entirely independent, they must coordinate their operations. Coordination falls into three macro-categories:

1. Communication: The exchange of data between cores. In our tree-based global sum example, one core communicates its partial result to another core so that the latter can add it to its total.
2. Load Balancing: If we divide the work poorly and one core receives 90% of the operations to do, the other cores will finish early and remain idle (wasting computing power) while waiting for the overloaded core. It is crucial that the work is distributed evenly.
3. Synchronization: Preventing cores from desynchronizing and compromising the result. If the master core reads an array of data from the keyboard (stdin), the other cores must wait for the reading to finish before starting their own computation on that array. Functions called “Barriers” (e.g., Synchronize_cores()) are often used to force all cores to wait for each other at a specific point in the code.

2.3 Hardware Architectures (Partial Flynn’s Taxonomy)

When programming, we need to know what type of hardware our code will run on. There are two main classifications for parallel systems:

Classification 1: Memory

• Shared-memory: All cores share access to a single large physical central memory. They can coordinate by reading and writing to the same shared variables (e.g., standard multi-core systems, programmable with Pthreads or OpenMP).
• Distributed-memory: Each core has its own private memory inaccessible to others. Cores are often separate computers connected by a network. Coordination happens explicitly by sending messages over the network (programmable with MPI - Message Passing Interface).

Classification 2: Instructions (SIMD vs MIMD)

This classification draws from the famous Flynn’s Taxonomy:

• MIMD (Multiple-Instruction Multiple-Data): Each core has its own control unit. It is an independent processor capable of executing a different instruction stream from the others. (e.g., core 0 does an addition while core 1 prints to the screen).
• SIMD (Single-Instruction Multiple-Data): There is a single control unit that commands all cores simultaneously. At each clock cycle, all cores execute the exact same instruction (or remain idle), applied however to different data.

Advantage of SIMD: It is highly efficient hardware for executing highly data-parallel calculations, like vector sums. Modern graphics cards (GPUs), programmable for example via CUDA, rely heavily on SIMD principles.

2.4 Vocabulary: Concurrent, Parallel, or Distributed?

Although often used as synonyms, academic literature makes some formal distinctions:

• Concurrent Computing: A program in which multiple tasks can be in progress at the same time. Even an operating system on an old single-core processor is concurrent (via context-switching it gives the illusion of simultaneity).
• Parallel Computing: A program in which multiple tasks cooperate closely and simultaneously to solve a problem. They often run on tightly coupled hardware (multicore, shared memory).
• Distributed Computing: Programs cooperate with each other, but are “loosely coupled”. They can reside on geographically distant computers, run by independently created software (e.g., a query on a web search engine).

All parallel and distributed programs are concurrent, but not all concurrent programs are parallel!