Analysis of Concurrent Programs

CS 636, Semester 2020-2021-II, IIT Kanpur

Instructor Information

Name	Swarnendu Biswas
Email	swarnendu AT cse.iitk.ac.in
Class hours	MonWed 5:10-6:25 PM (online, synchronous)

TA Information

Name	Email (AT cse.iitk.ac.in)
Arun KP	kparun
Priyanka Talwar	talwarp
Randeep Kumar Sahu	randeeps
Sharwari Samdekar	sharwari
Vipin Patel	vipinpat

Course Description

This course will focus on the challenges in developing correct and scalable concurrent programs. We will discuss the types of errors that we make while writing concurrent programs, and techniques and tools to debug them. We will learn about techniques and abstractions that help write correct concurrent programs, for example, synchronization primitives and transactional memory. We will also discuss testing of concurrent programs, and ideas to avoid common performance bottlenecks.

The course will include programming assignments and a course project.

Prerequisites

Exposure to the following courses (or equivalent) is desirable: CS 330 (Operating Systems), CS 335 (Compilers), and CS 422 (Computer Architecture).
Programming maturity with popular programming languages like C, C++, and Java.

Course Syllabus and Policies | Academic Integrity | Evaluation Scheme | Resources | References

Course Syllabus and Policies

Syllabus

The course will primarily focus on the following topics.

Concurrency Bugs: data races, atomicity violations, and deadlocks
Shared Memory Synchronization: locks, monitors, semaphores, flags, barriers, condition variables
Concurrent programming paradigms: shared-memory, message-passing, partitioned global address space
Transactional Memory
Memory Consistency Models
Concurrent Data Structures
Testing of Concurrent Programs
Performance Challenges: PAPI counters, performance analysis tools, false sharing

We might add new, drop existing, or reorder topics depending on progress and class feedback.
The course may also involve reading and critiquing related research papers.

Policies

Please be on time for the lectures.
You are allowed up to two late days to submit your assignment, with a 25% penalty for each day.

Feedback

I am open to constructive feedback about the course content. Feel free to provide suggestions for improvements.

Academic Integrity

You may discuss concepts with classmates, but all submissions must be your own or your team's work when teamwork is permitted.
You may not search online for existing solutions related to the assignments, even as a reference.
Students caught cheating or plagiarizing will be severely penalized. The penalty includes the possibility of failing the course and being reported to the Institute.

Evaluation Scheme

Class participation/quizzes - 10%
Assignments/paper critiques - 30%
Term Project - 35%
End semester exam - 25%

Resources

Date	Topic	Resources	Recommended Reading
13/01	Course Overview	Slides First Course Handout
13/01, 18/01, 20/01, 25/01, 27/01	Concurrency Bugs	Slides	References to relevant papers are included in the slides
30/01, 01/02, 03/02	Shared Memory Synchronization	Slides	MP 2.3, 2.4, 2.6, 7.1-7.5, 8.3 SMS 4.1, 4.2, 4.3.1, 6.1
08/02, 10/02, 15/02, 17/02	Transactional Memory	Slides	TM 2.1, 2.2, 4.1, 4.2
08/03, 10/03, 15/03, 17/03	Memory Consistency Models	Slides	Shared Memory Consistency Models: A Tutorial MC Chapters 3,4,5
22/03, 24/03, 31/03	Concurrent Data Structures	Slides	MP Chapters 9,10
05/04, 07/04, 12/04	Testing Concurrent Programs	Slides	References to relevant papers are included in the slides
19/04, 26/04, 28/04	Performance of Concurrent Programs	Slides	References to relevant papers are included in the slides

References

I have listed (NOT in any particular order) a few popular references.

[MP] The Art of Multiprocessor Programming - Maurice Herlihy et al. (either one of editions 1 and 2 should do)
[MC] A Primer on Memory Consistency and Cache Coherence - Daniel J. Sorin et al.
[SMS] Shared Memory Synchronization - Michael S. Scott
[TM] Transactional Memory 2nd edition - Tim Harris et al.