Description: The course will approach concurrent programming from two directions. In the first part of the course, the abstractions used in concurrent programming are explored. This part will build the student's intuition on understanding and reasoning about concurrency. The second part of the course will focus on performance. It is imperative for programmers who write concurrent code to understand the fundamentals and the limitations of the underlying architectures. Different implementation models of concurrency will be explored.

Course Content: 

Introduction: Shared objects and synchronization; parallel programming; Threads and monitors, sleeping; Interconnect, memory, caches, cache-conscious programming; Multicore and multithreaded architectures, hardware synchronization instructions.

Abstractions: 
1. Mutual exclusion: solutions to two- thread problems; locks, fairness and timestamps; 
2. Concurrent objects: different forms of consistency, linearizability, progress and memory models of modern programming languages; 
3. Foundations of shared memory, correctness arguments; 
4. Synchronization primitives including consensus, atomic registers, compare_and_set; 
5. Lock-free and wait-free construction, universality of consensus.

Implementation: 
1. Spin locks and contention, test-and-set locks, exponential backoff, composite and hierarchical locks; 
2. Monitors, locks and conditions, readers-writers locks; reentrant locks, semaphores.

Efficiency in parallel programs:
1. Ideal Vs Useful programming.
2. Reducing communication overheads.
3. Optimizing Recursive task parallel programs.
4. Optimizing Irregular task parallel programs.

Design patterns for multicore systems:
1. to express concurrency.
2. to express algorithm structure.
3. to express supporting structures.
3. to express implementation mechanisms.

Text Books: The Art of Multiprocessor Programming, by Maurice Herlihy and Nir Shavit, Morgan Kaufmman Publishers, 1st Edition, Indian Reprint 2012.

The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications by O' Reilly Media, 1st Edition, 2009

Reference Books: Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Block, Joseph Bowbeer, David Holmes and Doug Lea, Addison Wesley, 1st Edition, 2006