Principles of Multiprocessor Systems

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



Instructor: Prof. Smruti R. Sarangi

Lectures: 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:

Date
 Lecture
 References
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
 Exchangers
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
 Paper

Term Papers:
Student
 Paper
Himani Raina
 Concurrent Data Structures for Near-Memory Computing, SPAA 2017
Sapna
 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