Programming for Clusters and Multi-Core Processors
Introduction to parallel architectures, programming languages and algorithms for processor clusters and multi-core processors. Distributed memory architectures, cluster computing, message passing parallel programming, multi-core processors, shared memory parallel programming, use of thread libraries, parallel performance analysis.
Study notes
Independent, AI-drafted study guide · Public sources linked below · Added November 5, 2026
Original guide aligned to fixed topics in Carleton's public 2026–27 undergraduate calendar. No particular term, instructor, or assessment coverage is claimed; examples and exercises are independently written.
Shared and distributed memory
A parallel program divides work among processing elements. In shared memory, threads communicate through a common address space, requiring synchronization and a memory-model argument. In distributed memory, processes exchange messages and manage local data. Hybrid designs combine both. The program's data decomposition often determines communication and locality more strongly than its syntax. Identify which values are private, shared, replicated, or partitioned before choosing a parallel loop or communication pattern.
References: OpenMP — official API specifications and examples
Speedup, efficiency, and Amdahl's law
Speedup compares a defined serial runtime with parallel runtime on p workers; efficiency is speedup divided by p. Amdahl's law models a fixed workload with serial fraction s: ideal speedup is 1/(s+(1-s)/p). With s=0.1 and p=8, this is 1/0.2125, approximately 4.71, even before overhead. As p grows without bound, speedup approaches 10. State the baseline and workload, because weak scaling grows the problem with resources and answers a different question.
References: OpenMP — official API specifications and examples
Dependencies, scheduling, and locality
A dependency graph exposes which tasks can run concurrently. Work counts total operations; span counts the longest dependency chain, setting a lower bound on parallel completion time. Static scheduling has low coordination overhead when tasks are balanced; dynamic scheduling can handle variable work but adds management cost. Cache locality and false sharing can dominate a seemingly independent loop. Threads updating separate variables on the same cache line can generate coherence traffic despite having no logical data dependence.
References: OpenMP — official API specifications and examples
Races, barriers, and reductions
A race arises when concurrent accesses violate the program's synchronization contract. A barrier coordinates phases; a lock protects a critical invariant; a reduction combines private partial results through a specified operation. Making every update atomic can remove one race while leaving an algorithm incorrect or slow. Floating-point addition is not associative, so parallel reductions may differ numerically from a serial order. Define acceptable error and use stable algorithms when the application requires stronger numerical behavior.
References: OpenMP — official API specifications and examples
Message passing and deadlock
In MPI-style programming, match communication by communicator, source, tag, and datatype/count expectations. A blocking send's completion does not necessarily mean the receiver has finished consuming the message, and buffering assumptions should not be used as a correctness argument. Two processes that each block sending before posting receives can deadlock under some conditions. Nonblocking operations separate initiation from completion, but buffers must remain valid until the relevant operation completes. Collective calls require consistent participation and ordering.
References: MPI Forum — official standard documents
Worked partition and measurement plan
For a vector sum of n values, give each of p workers about n/p contiguous elements, compute private sums, then reduce them. The local arithmetic is O(n/p); reduction cost depends on the communication model and topology. At small n, startup and communication can outweigh useful work. Benchmark several problem sizes and worker counts, include warm-up where relevant, repeat trials, and report variation. Measure correctness as well as runtime, including empty partitions and sizes not divisible by p.
References: OpenMP — official API specifications and examples · MPI Forum — official standard documents
Practice & worked answers
Original exercises for this guide.
1. Why can parallelizing a loop make a program slower?
Show worked answer
Thread startup, synchronization, communication, scheduling, and memory contention may exceed the saved compute time. For a small or memory-bandwidth-limited workload, more workers do not necessarily provide more useful throughput.
2. Why should an MPI nonblocking-send buffer not be overwritten immediately?
Show worked answer
Initiation may return before the implementation has finished reading the buffer. Wait for completion through the appropriate operation before reuse. Otherwise the data transmitted can depend on timing.
Public notes & references
Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.
Prerequisites & course information
Prerequisite(s): COMP 2402 and ( COMP 2404 or SYSC 3010 or SYSC 3110 ) and COMP 2804 . Lectures three hours a week.