Schedule

This schedule is tentative and subject to change.

The following acronyms refer to course references, all of which are available through "Reserves" in Blackboard (Materials on Reserve at the library) or at the Carlson Library

  • PCA: Parallel Computer Architecture: A Hardware/Software Approach, Culler, Singh and Gupta.
  • AK: Optimizing Compilers for Modern Architectures, Allen and Kennedy
  • MLS: Shared-memory Synchronization, Michael L. Scott
  • HS: The Art of Multiprocessor Programming, Herlihy and Shavit.
  • vST3: Distributed Systems, 3rd Edition (2017), van Steen and Tanenbaum.
Date Lecture Notes References
Jan 18, 2018

Introduction

Take the survey! (now closed)

PCA Chapter 1

Jan 23, 2018

[Parallel] Machines and Models

M. J. Flynn, Very high-speed computing systems, in Proceedings of the IEEE, vol. 54, no. 12, pp. 1901-1909, Dec. 1966.

Jan 25, 2018

Automatic Parallelization in Hardware

PCA, Chapter 1

AK, Chapter 1

Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro 16, 2 (April 1996), 28-40.

Jan 30, 2018

Automatic Parallelization in Software

AK, Chapter 2, Dependence: Theory and Practice, for an introduction on dependence-based loop vectorization

AK, Chapter 10, Scheduling, for more on instruction scheduling

Feb 01, 2018

Automatic Parallelization in Software (contd.)

Feb 06, 2018

Parallel Memory Systems: Coherence

PCA, Chapters 5, 6, 7 and 8

Feb 08, 2018

Parallel Memory Systems: Consistency

PCA, Chapter 9

Adve and Gharachorloo, Shared Memory Consistency Models: A Tutorial, WRL Research Report 95/7

Feb 13, 2018

Parallel Programming Models and their Implementation: Basic Building Blocks

Blaise Barney, POSIX Threads Programming

Blaise Barney, OpenMP

Feb 15, 2018

PPMI: Synchronization Preliminaries

MLS, Chapter 4, `Practical Synchronization'

Feb 20, 2018

PPMI: Scalable Synchronization

MLS, Chapters 4 and 5 (`Busy-wait Synchronization with Conditions')

Feb 22, 2018

PPMI: Parallel Data Structures - I

MLS, Chapter 3, `Essential Theory'

HS, Chapters 3 (upto 3.7)

Feb 27, 2018

PPMI: Parallel Data Structures - II

Moir and Shavit, Concurrent Data Structures

Mar 01, 2018

PPMI: Parallel Data Structures - III

MLS, Chapter 8, `Nonblocking Algorithms', specifically the M&S queue

Mar 06, 2018

High-level Parallel Programming Models

Structured Patterns: An Overview, a nice collection of high-level parallel programming patterns

OpenMP, see the Resources/Tutorials page

Introduction to OpenMP, from LLNL

Blumofe and Leiserson, Scheduling Multithreaded Computations by Work Stealing

Blumofe et al., Cilk: an efficient multithreaded runtime system, PPoPP 1995

Mar 08, 2018

IrGL Case Study

Mar 13, 2018

Spring Break

Mar 15, 2018

Spring Break

Mar 20, 2018

Distributed Systems (DS): Background

vST3: Chapters 1--4

Mar 22, 2018

DS: Clocks

Project Proposal Due

vST3: Chapter 6 (Coordination), Section 6.1 (Clock Synchronization) and 6.2 (Logical Clocks)

Mar 27, 2018

More Clocks and Mutual Exclusion

VST3: Chapter 6, Sections 6.2 (Logical Clocks) and 6.3 (Mutual Exclusion)

Mar 29, 2018

Mutual Exclusion and Leader Elections

VST3: Chapter 6, 6.3 (Mutual Exclusion) and 6.4 (Election algorithms)

Jayadev Misra, Detecting Termination of Distributed Computations Using Markers. PODC 1983

Apr 03, 2018

Distributed Systems -- Other Programming Models

Apr 05, 2018

Cancelled

Apr 10, 2018

Consensus and Failure

Fischer, Lynch and Patterson, Impossibility of Distributed Consensus with one faulty process, JACM 32(2), 1985

Apr 12, 2018

Termination Detection

Dijkstra, Feijen and van Gasteren, Derivation of a termination detection algorithm for distributed computations, Information Processing Letters 16:217-219, 1983

Jayadev Misra, Detecting Termination of Distributed Computations Using Markers. PODC 1983

Apr 17, 2018

Checkpointing and Recovery

vST3, Chapter 8, Fault Tolerance

Apr 19, 2018

Paxos

Leslie Lamport, Paxos Made Simple

Leslie Lamport, The Part-time parliament, ACM TOCS 16(2), 1998

Fred B. Schneider, Implementing Fault-Tolerant Services using State machine replication, ACM Computing Surveys 22(4)

Gafni and Lamport, Disk Paxos, 2002

Apr 24, 2018

Parallel and Distributed Systems in Machine Learning (Haichuan Yang)

Apr 26, 2018

Wrap up

May 01, 2018

Project presentations