Course Number: CS5300
Pre-requisite: Data Structures, Operating Systems
Course Goal: Nowadays, all computing machines (cell phones, laptops, computation servers) have multi-core chips in them. These multi-core processors can be seen as parallel processors. Now, in order to harness the power of the multi-core hardware, the software applications being developed also have to be parallelized. This makes parallel programming a very important paradigm of computing.
Parallelization is commonly achieved using multi-threading. The multi-threaded application, would normally have to synchronize while accessing shared data. Hence, synchronization of shared data also known as concurrency control becomes very important. This course will provide an introduction to parallel and concurrent programming. It will focus both on correctness and efficiency of multi-threaded programs.
The classes will cover theoretical aspects. The corresponding lab/projects will focus on the programming aspects of the course.
Tentative Syllabus (subject to change):
Introduction; Mutual Exclusion; Concurrent Objects; Foundations of Shared Memory; Consistency condition for concurrent objects: Sequential consistency, Linearizability; Consensus; Universality; Spin Locks; Multi-thread Linked Lists; Queues and Stacks; Counting; Hash Sets; Futures and Work-Stealing; Barriers; Transactional Memory; Parallel Graph and Marix Algorithms
Texts:
The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit
References:
Multithreaded, Parallel, and Distributed Programming. Gregory R. Andrews
Introduction to Parallel Computing (2nd Edition). Ananth Grama , George Karypis, Vipin Kumar, Anshul Gupta
An Introduction to Parallel Programming. Peter Pacheco