PPLS: Previously Recorded Lectures

Introduction to the course, and a whistlestop tour of the world of parallel computer architecture, covering some of the nasty issues presented by the shared memory model, including weak consistency models and false sharing in the cache, and some architectural issues for the multicomputer model.

Overheads 1-12.

Reading: "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software", by Herb Sutter, link from the materials section).

An introduction to the "co", < > and "await" notation, and sequential consistency, with examples.

Overheads 13-23.

Reading: same as lecture 1, and also you can look at the materials section for a sheet of further "co" examples with solutions.

The Bag-of-Tasks, Pipeline and Interacting Peers patterns.

Overheads 24-42.

Reading: Non-examinable material on the growing importance of patterns in parallel programming at "Parallel Computing with Patterns and Frameworks", Catanzaro & Keutzer and/or "Structured Parallel Programming with Deterministic Patterns", McCool (links to both in the materials section).

Specification of the critical section problem, solution with locks. Implementation of locks with spinning "read-and-write" atomic primitives (in our case "Test-and-Set", and "Test-and-Test-and-Set").

Overheads 43-54.

Reading: See section 2.1 of the paper by Mellor-Crummey and Scott, linked to from the materials section, for more on test-and-test-and-set.

Lamport's "bakery" algorithm for critical sections.

Overheads 55-66.

Reading: Wikipedia is good and the materials section has a link to Lamport's original paper.

Barriers and barrier implementations: shared counter implementation with sense reversal. Symmetric Barriers. Dissemination Barriers. The main source of difficulty is the need to ensure reusability.

Overheads 67-76.

Reading: See the paper by Mellor-Crummey and Scott, linked to from the materials section, for more on various barrier implementations, including sense-reversing (3.1) and dissemination (3.3) and/or also the paper by Hensgen, Finkel and Manber, which discusses symmetric barriers (where they are called "Brooks Barrier" in section 2.2) and dissemination barriers (in section 2.4). NB you don't need to read the whole papers!

Semaphores and their application to mutual exclusion, barrier synchronisation and producer-consumer scenarios.

Overheads 77-89.

Reading: See the materials section for a link to a nice tutorial on semaphores. The wikipedia page is good too.

The monitor concept, and its use in programming producers-consumers. The key test here is whether you understand why the "while" loop is necessary (in the buffer example) as a safety check on the "wait" calls. We also began to look at the material on pthreads.

Overheads 90-101.

Reading: The wikepedia page on monitors is good.One of the original papers on monitors, by Hoare, is in the materials section.

More Pthreads API and examples, including semaphores, locks monitors, and an implementation of a counter barrier.

Overheads 102-114.

Reading: See the Pthreads tutorial guide linked to from the materials section. The Pthreads programs are there too. Why not mess around with them?

Java's model of concurrency, with the Thread class, and its built-in support for monitors.

Overheads 115-129.

Reading: There are many Java threads tutorials on the web, or you could browse the "threads" section of pretty much any good Java textbook. The examples are in the materials section, together with links to the (not examinable) material on the Java memory model.

Principles and issues in message passing programming. Introduction to MPI, focusing on communicators. Sketch of the task farm example, details to come next time.

Overheads 130-148.

Reading: The chapter on MPI in Foster's on-line textbook (link in the materials section), particularly 8.1 and 8.2. The program sources are all there too.

MPI, the task farm example, communication modes.

Overheads 149-159.

Reading: Foster (on-line, see materials) section 8.4, and a wealth of online examples by Googling "MPI communication modes".

MPI probing. MPI collective operations including the Jacobi and prime sieve examples.

Overheads 160-167.

Reading: Foster (on-line, see materials) sections 8.3, 8.4 and 8.5.

MPI material on splitting communicators. Introduction to Threading Building Blocks, the parallel_for template, Range and Body concepts. Game of Life example.

Overheads 168-187.

Reading: Foster 8.5 for MPI communicator splitting,  and the TBB tutorial (available in the materials), sections 1.2, 3.1 and 3.2 (some of this may only make sense after the next lecture).

TBB parallel_reduce and building your own Range. Building TBB task graphs directly. The work depth-first, steal breadth-first scheduling strategy.

Overheads 188-203.

Reading: TBB tutorial sections 3.2 - 3.3 and 11.1 - 11.4. The Fibonacci Range example is from a paper by Gonzalez and Fraguela. Also see the ProTBB book (Voss et al) for lots more detail if you are interested.

Parallel programming with content addressable memory, as provided by the Linda abstraction. Operations and examples, and a few words on implementation challenges.

Overheads 204-214.

Reading: (both in the materials section) Carriero & Gelernter, Linda in Context, Communications of the ACM, 32(4), pages 444-458, 1989. Carriero, Gelernter, Mattson, Sherman, The Linda alternative to message-passing systems, Parallel Computing 20, pages 633-655, 1993, contains quite a lot on implementation matters (not examinable).