CSC 2/458
Parallel and Distributed Systems
Spring 2019.
Course Schedule (evolving)
Note: assigned reading must be completed before
class.
Also: most of the links to readings work only from UR IP addresses; if
you’re off campus, you’ll need to extablish a VPN connection
before you can follow them.
- Wed. 16 Jan.
-
First day of class.
Overview, intro (notes).
- Mon. 21 Jan.
-
Martin Luther King, Jr. day; no class.
- Wed. 23 Jan.
-
More overview; the multicore revolution.
To be read before class today: (1) article by
Sutter & Larus;
(2) chapter 1 of Shared
Memory Synchronization.*
Due before class today: assignment 0
- Mon. 28 Jan.
-
Threads in C and C++.
To be read before class today:
(1) C++11 threading tutorial (e.g., this
one—read it carefully) and
(2) Lawrence
Livermore pthreads tutorial (skim this).
Also, if you haven’t taken CSC 2/454 at Rochester, read
(3) PLP sections
9.5 & 13.1–13.2.*
(If you have taken the course, you might still want to review the
material :-)
- Wed. 30 Jan.
-
Snooping cache coherence
(notes, diagrams).
To be read before class today:
(1) chapter 2 of Shared Memory Synchronization*
and
(2) Section 5.4* of Parallel Computer
Organization and Design, by Dubois, Annavaram, and
Stenström.
- Mon. 4 Feb.
-
Memory consistency models.
To be read before class today:
Adve &
Gharachorloo.*
Due last night:
assignment 1
- Wed. 6 Feb.
-
Memory consistency models (continued).
You may want to skim Section 3.4 of
Shared
Memory Synchronization,* but be warned that it
oversimplifies. Specifically: it fails to introduce the
“sequenced with” relation described in the lecture notes. It then
erroneously defines happens-before as the transitive closure of
program order and synchronized-with; it should define
happens-before as the (non-transitive) union of program
order and the transitive closure of sequenced-with and
synchronized-with. (I will be fixing this in a subsequent
revision.)
- Mon. 11 Feb.
-
Spin locks
(notes).
To be read before class today:
chapter 4 of Shared Memory Synchronization.*
- Wed. 13 Feb.
-
Busy-wait condition synchronization.
To be read before class today:
chapter 5 of Shared Memory Synchronization.*
and
Lock
Cohorting, by Dice, Marathe, and Shavit.
(For more details, see the longer
journal version
of this paper.)
- Mon. 18 Feb.
-
Prof. Scott out of town; guest lecture by Prof. Yuhao Zhu: “Beyond
Parallelism: Architectural Specialization and
Customization.”
To be read before class today:
Understanding Sources of Inefficiency in General-Purpose Chips,
by Hameed et al.
and
Dark Silicon and the End of Multicore Scaling,
by Esmaeilzadeh et al.
Due last night:
assignment 2
- Wed. 20 Feb.
-
Prof. Scott out of town; guest lecture by Prof. Chen Ding:
“Compilation for Data Parallelism.”
To be read before class today:
Section 2.2 and Chapter 14 of Optimizing
Compilers for Modern Architectures,* by Allen and Kennedy.
Please also see Kennedy's
lecture
notes for Chapter 14, as well as the
on-line
errata for the text.
- Mon. 25 Feb.
-
Finish coverage of barriers.
New material: speedup
(notes).
To be read before class today:
(1) Gustafson* (scaled speedup)
and (2) Karp &
Flatt* (serial fraction).
- Wed. 27 Feb.
-
Read-mostly synchronization
(notes).
To be read before class today:
(1) chapter 6 of Shared Memory Synchronization* and
(2) McKenney's Structured Deferral.
- Mon. 4 Mar.
-
MPI
(notes) and (if time permits) Map-Reduce
(notes).
To be read before class today:
(1) Victor Eijkhout’s on-line MPI book: read
chapter 1 and skim chapters 2–14 to get a sense of
scope.
- Wed. 6 Mar.
-
Concurrency theory
(notes).
To be read before class today:
chapter 3 of Shared
Memory Synchronization.*
- (Fri. 8 Mar.)
-
Due by 5pm:
assignment 3
- (Mon. 11 Mar. and Wed. 13 Mar.)
-
Spring break; no class.
- Mon. 18 Mar.
-
Guest lecture (remote) by Brad Chamberlain,
Principal Engineer at Cray, Inc., and Technical Lead for the Chapel
programming language.
- Wed. 20 Mar.
-
Nonblocking data structures
(notes).
To be read before class today:
(1) chapter 8 of Shared
Memory Synchronization.*
Due by end of day Saturday:
semester project/presentation
proposals.
- Mon. 25 Mar.
-
In-class presentation of proposals.
- Wed. 27 Mar.
-
(continued)
- Mon. 1 Apr.
-
Presentation of final 2 project proposals;
continued coverage of concurrency theory and nonblocking data
structures.
- Wed. 3 Apr.
-
Finish coverage of nonblocking data structures.
To be read before class today:
(1) Hendler et
al. (flat combining)
and
(2) Morrison & Afek (LCRQs).
Due by end of day Sunday:
assignment 4
- Mon. 8 Apr.
-
Time (notes).
To be read before class today:
Tanenbaum
& van Steen, Sections
6.1–6.2.*
Optional: Lamport’s classic “Time,
Clocks, and the Ordering of Events in a Distributed
System.”
- Wed. 10 Apr.
-
Software Distributed Shared Memory
(notes).
To be read before class today:
Treadmarks
and
Cashmere.
In the latter, focus your attention on Sections 1, 2, 4.1, 5, and 6.
- Mon. 15 Apr.
-
Distributed Consensus
(notes, slides).
To be read before class today:
Coulouris et al. Sec. 15.5* and
Henry Robinson’s blog on FLP impossibility.
- Wed. 17 Apr.
-
Paxos and Raft
(notes).
To be read before class today:
Henry Robinson’s
blog
on Paxos and the
Raft
paper.
If you’re curious, take a peek at the original
Paxos paper and/or Lamport’s Paxos Made Simple.
- Mon. 22 Apr.
-
Transactions
(notes).
To be read before class today: Coulouris
et al. Chap. 16.*
- Wed. 24 Apr.
-
Transactional Memory
(notes).
To be read before class today:
chapter 9 of Shared Memory Synchronization.*
- Mon. 29 Apr.
-
Persistence
(slides).
To be read before class today:
Steve Swanson’s first and second
blog posts on persistence.
Please also skim the Durable
Linearizability
paper.
Please be sure to fill out your on-line course evaluation.
- Wed. 1 May
-
Miscellaneous topics
(notes).
No reading assignment.
Final projects due Sunday by end-of-day.
* Available from UR IP addresses only.
Back to the course home page
Last Change:
01 May 2019 /
