A photo-illustration from sources (c) Disney Corporation.
The Sorcerer’s Apprentice, Fantasia, 1940.

CSCI 361: Spring 2025

Parallelism and Concurrency

……………………. . . . . . . . . . . . . . . . .

This course investigates the theory of algorithms and of system support for high performance multiprocessor systems. It is also an introduction to implementing these algorithms in executable code. Throughout the semester, students will be asked to demonstrate the ideas on current multiprocessor hardware and on GPU hardware.

The first two-thirds of the course develop the theory of parallel algorithms, surveying some classic results including prefix scans and sorting, and also their applications to graphs and sequence analysis. This dovetails with actual implementation on a variety of parallel languages and concurrency libraries (e.g. POSIX threads, CUDA).

In the last third of the course we look at scheduler and runtime support for executing parallel and concurrent programs, surveying recent research. Students also spend this last third researching and developing code for an independent project.

Prerequisites: CSCI 221 and MATH/CSCI 382.
Instructor: Jim Fix <jimfix@reed.edu>
Meets: MW 2:40-4pm in Library 340.

……………………. . . . . . . . . . . . . . . . .

Resources

We will be working from excerpts of texts, tutorials, and notes, as well as research papers and articles. I will provide the readings, there is no required textbook (as of yet), and I will work to link those within the weekly schedule below as the semester progresses.

Below also is a list of classic resources on parallel algorithm theory, on concurrency, and on parallel hardware that we’ve used in a past version of this course.

Introduction to Algorithms
by Cormen, Leiserson, Rivest (and Stein)
• Selected chapters from various editions address parallel algorithms:
  Chapter 27 (3e) on Multithreaded Algorithms
  Chapter 27 (2e) or Chapter 28 (1e) on Sorting Networks
  Chapter 29 (1e) on Arithmetic Circuits
  Chapter 30 (1e) on Algorithms for Parallel Computers

Synthesis of Parallel Algorithms (1993)
edited by J. Reif.
• PRAM algorithm compendium. Several chapters are available on-line.

Parallel Algorithms and Architectures: Arrays.Trees.Hypercubes (1992)
by F. T. Leighton.
• Algorithms for specific hardware interconnect topologies.

The Art of Multiprocessor Programming (2e, 2021)
by Herlihy, Shavit, Luchango, and Spear.
• Concurrency mechanisms and concurrent data structures, scheduling.

Computer Architecture: a Quantitative Approach (5e, 2012)
by Hennessey and Patterson.
• Chapter 4 on Data-Level Parallelism, including GPU architectures.
• Chapter 5 on Thread-Level Parallelism, shared memory multi-processors.

Limits to Parallel Computation (1995)
by Greenlaw, Hoover, and Ruzzo.
• PRAM and circuit models, the NC complexity class, P-completeness.

An Introduction to Parallel Programming (2012)
by P. Pacheco.
• Introduces parallel programming using MPI, OpenMP, and POSIX threads.

……………………. . . . . . . . . . . . . . . . .

Hardware & Software

You will all have access to patty.reed.edu, a Ubuntu 20.04 linux machine with several cores and a GPU. Specs:
• 32 AMD Ryzen “thread ripper” cores with 2 hyperthreads each.
• NVidia GeForce RTX 2080 SUPER, with 3072 CUDA cores (192 MTUs).

You can also configure your own machine to develop using any of
• POSIX threads for C,
• NVidia’s CUDA,
• OpenMPI for C/C++, OpenMP for C/C++ (might need Intel’s TBB),
• Go, Rust, Cilk, and other language systems.

……………………. . . . . . . . . . . . . . . . .

Responsibilities

The course is a hybrid of theory and (prototyped) implementations, building off the skills you learned in MATH/CSCI 382 and CSCI 221. As such, there will be a mix of written problem sets and coded programs. There will also be a final, independent project assigned after the 8th week. This will ask you to either carry a homework assignment assignment further than just from pseudocode or from prototype, perhaps trying several techniques to get good practical performance. Alternatively, you can seek to attack a problem we do not cover in class, survey it, and implement a working solution (or solutions).

• • • • • • • • • • • • • • • • • • • • • 

• • • • • • • • • • • • • • • • • • • • • 

• • • • • • • • • • • • • • • • • • • • • 

• • • • • • • • • • • • • • • • • • • • •