Principles of Multiprocessor Systems

Course: COL818
Semester I, 2017-18
Credits: 4 (3-0-2)

Instructor: Prof. Smruti R. Sarangi

: Tuesday and Thursday: 3:30 to 5 PM, Presentation Room, SIT Building

Course Description: This course will give an introduction to some advanced aspects of multiprocessor  systems.

Course Load: Minor 1, Minor 2, End term, 3 programming assignments

Evaluation: 25% (Minor 1), 25% (Minor 2), 30% (Major), 20% (Assignments)

Teaching Assistant: Hameedah Sultan

Reference Books
[Textbook] The art of Mulitprocessor Programming, Herlihy and Shavit, 2012 Revised Edition, Elsevier

Lectures and Slides:

July 28th
Course Overview

Aug 1st
Flag Based Synchronization

Aug 3rd
Peterson Lock and Filter Lock

Aug 8th
Bakery Lock and Quiescent Consistency

Aug 10th
Sequential Consistency and Linearizability
Term Papers: Problem Set 1
Aug 17th
Atomic, Regular and Safe Registers

Aug 22nd
Register Constructions

Aug 24th
Wait-free atomic snapshot

Sept. 2nd
Consensus number of atomic registers and queues

Sept. 5th
Consensus number of multi-write objects, Common-2 operations, and CAS

Sept. 8th
Universal Constructions

Sept. 12th
TAS, TTAS, Array and CLH locks

Sept. 14th
MCS lock, and Time-out Lock

Sept. 19th
Composite Lock

Sept. 21st
Fast Path Lock, and Reader-Writer lock (simple and fair)

Sept. 26th
Linked lists: coarse grained, fine grained, optimistic

Sept. 28th
Linked Lists: Lazy and Lock-free

Oct 3rd
Lock-free linked list (contain method), Bounded queues, Lock-free queues

Oct 5th
Lock-free stack

Oct 10th

Oct 24th
Combining Tree

Oct 31st
Diffracting Trees and Bitonic Networks

Nov 2nd
Concurrent Hash Tables

Nov 4th
Concurrent Skip Lists

Nov 7th
Concurrent Priority Queues

Nov 9th
Work Stealing and Concurrent DeQueues

Nov 15th
Barriers and Transactional memory
Slides , TL2, Bartok STM
Self Study
Paper on Slot Scheduling

Term Papers:
Himani Raina
Concurrent Data Structures for Near-Memory Computing, SPAA 2017
Extending TM Primitives using Low Level Semantics, SPAA 2016
Shantanu Agarwal
Just Join for Parallel Ordered Sets, SPAA 2016
Ruchir Dhiman
Parallel Approaches to the String Matching Problem on the GPU, SPAA 2016
Sandeep Kumar
Investigating the Performance of Hardware Transactions on a Multi-Socket Machine, SPAA 2016
Sahil Jain
Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free, SPAA 2016
N S Sreenivasalu
Fast and Robust Memory Reclamation for Concurrent Data Structures, SPAA 2016