Dan Grossman Teaching Materials
A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (pdf)
This document is for students and instructors. It covers the same material as the slides and homeworks in more detail. It is something between lecture notes and a draft of textbook chapters.
Instructors can make variants/extracts using the LaTeX
source and several image files:
sophomoricParallelismAndConcurrency.tex
zip file of images
The materials on this page offer a 2-3 week unit introducing parallelism and concurrency in a lower-level data structures course. They have been used since Spring 2010 as part of this full data-structures course and have also been adapted for CS2 courses and for introductions in more advanced courses (see "Other Users"). All materials are free and questions/feedback/suggestions are encouraged.
For motivation on incorporating this material in lower-level data structures and a short overview of the approach, see:
All the materials on this page use Java, including Java's ForkJoin Framework, when a particular language or code example is needed. Some of the materials, including the reading notes, have been ported to C++.
In PowerPoint 2007 and pdf
The breakdown into "lectures" does not exactly map to 1-hour segments; overall there is about 7-8 hours of material divided into 6 lectures.
These instructions are essential for writing and running real parallel programs using the ForkJoin library, as in the project and some of the homework exercises.
Please do not post solutions to these exercises
Homework problems (short paper-and-pencil or simple programming exercises): pdf LaTeX source
Java parallel-programming project:
html
Compute U.S. population densities with real data. Includes a simple, optional, fun GUI.
pdf without solutions pdf with solutions LaTeX source
Exam problems used in Spring 2010 or Spring 2012. By design, some of the questions were fairly difficult. Note solutions are posted. The full exams (2010, 2012) also had questions on sorting and graphs, with a 110-minute time limit.
I ran a 3-hour workshop at SIGCSE 2011. The workshop materials are below. They are self-contained with some original content (e.g., new lab exercises) but also substantial overlap with other materials.
Workshop abstract: Multithreading (Pretty) Early for
Everyone: Parallelism and Concurrency in Second-Year Data-Structures
There is wide interest in introducing students to
threads earlier, but how? This workshop gives an answer: a 3-week unit
in data structures. It should appeal to data-structure instructors
and those tasked with curriculum revision. The presenter wrote/used
the course materials and advised later instructors. A key approach is
to distinguish parallelism (using more resources to solve problems
faster) and concurrency (managing shared access to resources). The
material is taught via core data-structure topics (asymptotic
complexity, sorting, queues, etc.) and using Java and its ForkJoin
Framework. Participants will write parallel programs, find concurrency
errors, and discuss how the material can fit their needs. Those with
or without knowledge of threads and fork-join programming are welcome.
Installation instructions (to be completed in advance)
Exercises: pdf
LaTeX
Java maps
reductions
test output maps
reductions
The Java files have blank spaces for completing the exercises; testing code is provided. Solutions are available on request.
Please let me know how you are using these materials and how they can be improved. Even typos are helpful.
spac at cs.washington.edu is a low-traffic mailing list for announcing updates and occasional discussions among users. You can subscribe here or just ask me to subscribe you.
We gratefully acknowledge gifts from Intel Labs University Collaborations and grants from the U.S. National Science Foundation that provided financial resources to develop these materials.
Last updated: February 2017
