Concurrent Programming

ECEN 5033, CSCI7000-007

Instructor Pavol Cerny
Lectures Tue, Thu 5.00-6.15 in ECCR 1B51
Office hours Thu 2-3pm in ECOT 349, and by appointment
TA
Gowtham Ramkumar
email: gora740 at colorado.edu
office hours: Monday 2-3:30 pm and Monday 6-8pm. ECEE 287.

Course description

This course focuses on the theory and practice of multicore programming. Our ability to effectively harness the computational power of the current and the next generation of multicore architectures is based on advances in programming languages and tools for developing concurrent software. The first part of the course presents foundations of concurrent programming: mutual exclusion, wait-free and lock-free synchronization, spin locks, monitors, memory consistency models. In the second part, we will see a sequence of concurrent data structures, and techniques used in their implementations (coarse-grained, fine-grained, optimistic, and lock-free synchronization).

Schedule

  • January 14: Gentle Introduction (Chapter 1).
  • January 16, 21, 23: Mutual Exclusion (Chapter 2).
  • January 28, 30: Correctness of Concurrent Objects; Linearizabillity (Chapter 3). HW1 posted on D2L. Due 2/11, before class.
  • February 4, 6, 11: Concurrent Data Structures (part I): Linked Lists (Chapter 9).
  • February 13, 18: Foundations of Shared Memory (Chapter 4). HW2 posted on D2L. Due 3/4, before class.
  • February 20, 25, 27: Relative Power of Synchronization Operations (Chapter 5).
  • March 4: Universality of Consensus (Chapter 6).
  • March 6: Review.
  • March 11: Midterm 1.
  • March 13, 18, 20: Spin Locks and Contention (Chapter 7). HW3 posted on D2L. Due 4/8, before class.
  • March 25, 27: Spring break. (Chapter 7).
  • April 1: Monitors and Blocking Synchronization (Chapter 8).
  • April 3: Concurrent Queues and the ABA problem (Chapter 10).
  • April 8: Concurrent Stacks and Elimination (Chapter 11). HW4 posted on D2L. Due 4/22, before class.
  • April 10: Concurrent Hashing and Natural Parallelism (Chapter 13).
  • April 15, 17: Futures, Scheduling, and Work Distribution (Chapter 16).
  • April 22: Review.
  • April 24: Midterm 2.
  • April 29, May 1: Project presentations.

Note: Slides are available on D2L.

Course project

The goal of your project is to write a larger concurrent program, and test its performance. Performance study will be an integral part of the project: if applicable, compare the performance of different versions of your program (sequential, naive concurrent data structures, optimized concurrent data structures). Perhaps a different version will work best for different various inputs, workloads, and environments. Work on your own or in pairs.

Note: Project ideas are available on D2L.

Project deadlines:
  • February 10: project proposal (2 pages)
  • March 31: checkpoint (project works on motivating examples, performance testing can begin (3 pages)
  • April 28: project submission deadline (submit source code, examples, project report (6 pages))
  • week of April 28: project presentations, demos

Relevant links


Grading

The course will be graded based on a course project (40% of the course grade), homework (30%), exams (20%), and in-class participation (10%).

Syllabus statement

A statement of class policies is available here.