Analysis of Concurrent Programs

CSE 636, IIT Kanpur, Semester 2018-2019-II

Instructor Information

Name	Swarnendu Biswas
Email	swarnendu AT cse.iitk.ac.in
Class hours	MonWed 3:30 - 4:45 PM in KD 101
Office hours	Tue 4-5 PM, Fri 11-12 PM in KD 302

TA Information

Name	Prafulla Saxena
Email	prafulla AT cse.iitk.ac.in

Course Description

This course will discuss the needs and challenges in developing correct and scalable concurrent programs. We will learn about common type 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, locks and other synchronization primitives. We will also discuss how to analyze performance of concurrent programs, and ideas to avoid common performance bottlenecks.

Pre-requisites

Basic courses on compilers, operating systems, and computer architecture would be a bonus.
Programming maturity
Good knowledge in C/C++ and Java

Should I register? The intended audience is senior UG and PG students. I expect this course will be useful to students who are working or are interested in working in the general area of systems and large-scale software development.

Feel free to discuss with me if you are unsure about the scope.

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

Course Policies and Syllabus

Policies

Remember that clarifying every question and doubt is important. There is nothing like a trivial or a foolish question.
Please be on time to class, it is distracting for everyone when impunctual students keep trickling in late to 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.
Submitting your assignments late will mean losing points automatically. You will lose 10% for each day that you miss, for up to three days. You might be excused only under extreme circumstances, but let me now at the earliest.

Syllabus

The following is a tentative list of topics that we will cover during the course. We might add new, drop existing, or reorder topics depending on progress and class feedback.

Recent trends in hardware and software
Concurrent programming - philosophy, benefits and challenges
Review of concurrent programming paradigms: shared-memory, message-passing, partitioned global address space
Review of architecture basics - shared memory architectures, cache coherence
Concurrency bugs - data races, atomicity violations, deadlocks
Testing concurrent programs
Synchronization primitives: locks, monitors, semaphores, flags, barriers, condition variables
Memory consistency
Performance challenges - false sharing, cache miss analysis

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

Feedback

I am open (I hope!) to constructive feedback about the course content and presentation. I will distribute unofficial feedback forms a few weeks into the semester, and you will have the option of remaining anonymous.

Academic Integrity

You may discuss concepts with classmates, but all assignments 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 automatically fail the course and will be reported to the institute.

Evaluation Scheme

You have two choices, choose the one which better suits you. Let me know by Jan 14th 2019.

Choice 1

Class/piazza participation - 10%
Paper reading and critiques - 20%
Assignments - 50%
Final exam - 20%

Choice 2

Class/piazza participation - 10%
Paper reading and critiques - 20%
Project - 50%
Final exam - 20%

Resources

We will use Piazza as the discussion forum. Click here to register for the course on Piazza.
We will use Canvas for course submissions.

Date	Topic	Resources	Supplementary reading
07/01/19 - 09/01/19	Course Details, Review of Systems Basics	Course Details Systems Basics
09/01/19 - 12/01/19	Shared Memory Programming and Pthreads	Slides	LLNL Pthreads Tutorial
12/01/19 - 14/01/19	Parallel Prefix Scan	Slides	Guy E. Blelloch's note
14/01/19 - 28/01/19	Concurrency Bugs	Slides	References to relevant papers are included in the slides
28/01/19 - 04/02/19	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
06/02/19 - 25/02/19	Transactional Memory	Slides	TM 2.1, 2.2, 4.1, 4.2
25/02/19 - 06/03/19	Memory Consistency Models	Slides	Shared Memory Consistency Models: A Tutorial MC Chapters 3,4,5
11/03/19 - 25/03/19	Concurrent Data Structures	Slides	MP Chapters 9, 10
27/03/19 - 03/04/19	Testing Concurrent Programs	Slides	References to relevant papers are included in the slides
08/04/19 - 10/04/19	Performance of Concurrent Programs	Slides	References to relevant papers are included in the slides

References

I have listed references (NOT in any particular order) that I think are good reads and would be useful at some stage while working on concurrent programming and related areas. You are NOT required to buy these books for this course.

[MP] The Art of Multiprocessor Programming - Maurice Herlihy and Nir Shavit
[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.

In addition, we will read and discuss several research papers which we will announce in class.

Analysis of Concurrent Programs

CSE 636, IIT Kanpur, Semester 2018-2019-II

Instructor Information

TA Information

Course Description

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

Course Policies and Syllabus

Policies

Syllabus

Feedback

Academic Integrity

Evaluation Scheme

Choice 1

Choice 2

Resources

Date

Topic

Resources

Supplementary reading

References