Concurrent Programming (Spring 2017)

ECEN 4313, CSCI4830-010

Instructor Pavol Cerny
Lectures TTh 5.00-6.15 in DUAN G2B47
Office hours Wed 4-5pm in ECEE 120, and by appointment
TA
Aniruddha Phatak
email: aniruddha.phatak at colorado.edu

Course Moodle site

Course schedule, slides, homework assignments, and project suggestions are on the Moodle site.

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).

Course Topics

  • Introduction: Mutual Exclusion, Concurrency in Java.
    • Mutual Exclusion: Peterson's algorithm, Bakery Algorithm
    • Reasoning about concurrency, Lower Bound for Mutual Exclusion
    • Concurrency in Java: Java memory model; thread local variables.
  • Foundations of Shared Memory Concurrent Programming
    • Case Study: Concurrent Lists
    • Correctness of Concurrent Objects; Linearizabillity
    • Power of Synchronization Operations
    • Concurrent Registers
  • Practical Synchronization Algorithms.
    • Spin Locks.
    • Monitors and Blocking Synchronization.
  • Concurrent Data Structures.
    • Concurrent Queues and the ABA problem
    • Concurrent Stacks and Elimination
    • Concurrent Hashing and Natural Parallelism
  • Advanced Topics.
    • Futures, Scheduling, and Work Distribution.
    • Transactional Memory.

Note: Slides are available on Moodle.

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 suggestions are available on Moodle.

Preliminary project deadlines:
  • February 24: project proposal (2 pages)
  • March 24: checkpoint (project works on motivating examples, performance testing can begin (4 pages))
  • May 1: project submission deadline (submit source code, examples, project report (6 pages))
  • week of May 1: project presentations, demos

Tests

Preliminary test dates.
  • February 16: Test 1
  • March 21: Test 2
  • April 27: Test 3

Textbook


Grading

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

Syllabus statement

A statement of class policies is available here.