Analysis of Concurrent Programs

CS 636, Semester 2024-2025-II, IIT Kanpur

Instructor Information

Name	Swarnendu Biswas
Email	swarnendu AT cse.iitk.ac.in
Class hours	Mon 11:00-12:00 PM ThuFri 10:00-11:00 AM in KD 102

TA Information

Name	Email (AT cse.iitk.ac.in)
Binong Kiri Bey	binong
Srinjoy Sarkar	srinjoy

Course Description

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

The course may include programming assignments and a course project.

Prerequisites

Exposure to CS 220 (Computer Organization) and CS 330 (Operating Systems) (or equivalent non-IITK courses) is desirable
Programming maturity (primarily C/C++/Java) is desirable

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

Course Syllabus and Policies

Syllabus

The course will focus on a subset of 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
Memory Consistency Models
Transactional Memory
Concurrent Data Structures
Performance Challenges: PAPI counters, performance analysis tools, false sharing
Testing of Concurrent Programs

We may add new, drop existing, or reorder topics depending on progress and class feedback.

The course may also involve reading and critiquing related research papers.

The recommended reading material is part of the course.

Policies

Please be on time for class.
Please try to avoid using laptops and/or mobile devices in class, they are distracting for both the instructor and other students who want to concentrate.
You are allowed up to two late days to submit your assignment (if applicable), with a 25% penalty for each day.

Feedback

I am open to feedback about the course content and presentation. 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 should not search online for existing solutions related to the assignments, even as a reference.
Students caught cheating or plagiarizing will receive penalties, automatically fail the course, and will be reported to the Institute.

Evaluation Scheme

Class participation (quizzes, interaction)	5%
Assignments (2-3)	15%
Midsem	25%
Term Project (with periodic evaluation)	25%
Endsem	30%

Resources

Date	Topic	Resources	Recommended Reading
		First Course Handout
06/01, 09/01, 10/01, 13/01, 16/01	Concurrency Bugs	Slides	OSTEP Chapters 26, 32
17/01, 20/01, 23/01, 24/01, 25/01, 27/01	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
30/01, 06/02, 07/02, 08/02, 10/02, 13/02	Memory Consistency Models	Slides	Shared Memory Consistency Models: A Tutorial MC Chapters 1-5
14/02, 17/02, 20/02, 03/03, 06/03, 07/03, 17/03	Transactional Memory	Slides	TM 1, 2.1-2.2, 4.1-4.2, 5.1 Intel SDM Volume 1: Basic Architecture, Chapter 17
20/03, 21/03, 22/03, 24/03, 27/03, 03/04	Concurrent Data Structures	Slides	MP Chapters 3, 9, 10, 11, 13 OSTEP Chapter 29
04/04, 05/04, 07/04, 11/04, 12/04, 14/04	Testing Concurrent Programs

References

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

[MP] The Art of Multiprocessor Programming, 2^nd edition - M. Herlihy et al.
[MC] A Primer on Memory Consistency and Cache Coherence, 2^nd - V. Nagarajan et al.
[SMS] Shared-Memory Synchronization, 2^nd - M. Scott and T. Brown.
[TM] Transactional Memory, 2^nd edition - T. Harris et al.
[PCA] Parallel Computer Architecture: A Hardware/Software Approach - D. Culler et. al
[JCIP] Java Concurrency In Practice - B. Goetz et. al
[OSTEP] Operating Systems: Three Easy Pieces - Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau