Advanced Topics in Multi-Core Architecture and Software Systems
Spring 2017

Lecturer: Adam Morrison
When: Wed, 16:00-19:00
Room: Schreiber 008

Overview

Writing fast and scalable multi-core programs is hard. Multi-core programming models fail to abstract away the details of the underlying computer architecture, partly because of limitations in the hardware/software interfaces (such as instruction sets and memory models). We must thus understand the multi-core architecture, both to design efficient algorithms and systems, and to find better abstractions and interfaces.

This course covers the state of the art in multi-core programming and architecture. A main objective is to introduce students to open research problems in multi-core research.

NOTE: We will consider hardware only at the microarchitecture level, not at the logic/gate level; for an example of microarchitectural material, see the book A Primer on Memory Consistency and Cache Coherence.


NEWS

Requirements and grading


Schedule

Date Lecture Papers
Mar 15

Introduction (slides on moodle)
Overview
Administrative details
Taste of topics

The Implementation of the Cilk-5 Multithreaded Language

Idempotent Work Stealing

Laws of Order: Synchronization in Concurrent Algorithms

Fence-Free Work Stealing on Bounded TSO Processors

Mar 22

Background material
Reasoning about concurrency (linearizability)
Architecture basics (cache coherence, etc.)

Linearizability: A Correctness Condition for Concurrent Objects

A Primer on Memory Consistency and Cache Coherence (Chapters 2, 6-8)

Mar 29

Serializing efficiently
Spin locks and local spinning
Delegation
Lock-free synchronization and CAS failures

Apr 19

Optimistic concurrency control

Apr 26

Safe memory reclamation

May 3

Memory consistency models (hardware)

May 10

Memory consistency models (programming language)

May 17

Cache coherence protocols

May 24

Concurrency control in databases

Jun 7

Advanced issues in hardware transactional memory

Jun 14

Ordered parallelism and relaxed data structures (1/2)

Jun 21

Ordered parallelism and relaxed data structures (2/2)

Jun 28

Non-volatile memory and its relation to concurrency

Projects

The main requirement is for the project to make a new (even if small) contribution to our knowledge. You can try attacking a research problem shown in class, do something based on your own research, or implement and try to reproduce the results of prior papers.

The project may be done individually or in a group of 2 to 3.

Most projects will require programming, e.g., for experiments and evaluation. Programming language depends on the project, but projects reproducing prior work will likely be in C/C++.

Proposal: Submit a writeup (PDF, max 2 pages, in English) describing the problem, why it is interesting, the state of the art, and what you plan to do. Each group needs to submit only one copy (include the names and IDs of all members). We may need to iterate on the proposal; don't start working on the project before the proposal is approved.

Final report: Submit a writeup (PDF, English) describing the problem and what you did. Submit your code as well (preferably as a link to a repository on Github or Bitbucket). Unless otherwise agreed, your code must be runnable on the school's Linux machines. Each group needs to submit only one copy.