Information
| Class Meetings | Mon 5:10-7:00pm in CIWW 317 |
| First Lecture | Jan 27, 2014 |
| Last Lecture | May 12, 2014 |
| Final Exam | May 16, 2014, 5:10-7:00pm in CIWW 317 |
| Instructor | Thomas Wies |
| Office | CIWW 407 |
| Office Hours | Tue 3:00-4:00pm, or by appointment. |
Overview
The spread of multicore architectures has a pervasive effect on how we develop software. In this course, we focus on programming techniques for modern multicore machines. We will explore how to write programs using major paradigms for managing concurrency and how to reason about the correctness and performance of such programs. Topics include multiprocessor architecture, mutual exclusion, wait-free and lock-free synchronization, load balancing, concurrent data structures, transactional memories, and message passing. The course will involve extensive programming exercises in Java and related languages.
Prerequisites
Participants should have previously taken the course Programming Languages (CSCI-GA 2110). This course will be open to MS and PhD students.
Course Material
Required Reading
- The Art of Multiprocessor Programming, Revised Reprint by Maurice Herlihy and Nir Shavit, Morgan Kaufmann, 2012
Recommended Reading
- Programming in Scala, Second Edition by Martin Odersky, Lex Spoon and Bill Venners, Artima, 2010
Scala Resources
Syllabus
| Week | Date | Topics | Materials and Homework |
|---|---|---|---|
| 1 | 01/27 | Introduction, Mutual Exclusion, Producer/Consumer, Readers/Writers, Amdahl's Law | Slides; Read Ch. 1 and App. A.2 of AMP; Homework 1; Sample solution: Part 1 (starving); Part 1 (nonstarving); Part 2,3 |
| 2 | 02/03 | Mutual Exclusion: Peterson's Algorithm, Filter Algorithm, Bakery Algorithm, Impossibility | Slides; Read Ch. 2 of AMP; Homework 2; Sample solution |
| 3 | 02/10 | Concurrent Objects: Linearizability, Sequential Consistency, Progress Properties | Slides; Read Ch. 3 of AMP (you may skip Sec. 3.6); Homework 3; Sample solution |
| 4 | 02/17 | No class (Presidents Day) | |
| 5 | 02/24 | Spin Locks: TASLock, TTASLock, CLHLock, MCSLock | Slides; Code; Read App. B and Ch. 7 of AMP (you may skip Sec. 7.7 and 7.8); Homework 4; Sample solution |
| 6 | 03/03 | Monitors and Blocking Synchronization | Slides; Read Ch. 8 of AMP; Homework 5; Sample solution: PDF and source code |
| 7 | 03/10 | Synchronization of Concurrent Objects: coarse-grained, fine-grained, optimistic, lazy, lock-free | Slides; Read Ch. 9 of AMP; Homework 6; Sample solution |
| 8 | 03/17 | No class (Spring Recess) | |
| 9 | 03/24 | Concurrent Queues and Stacks | Slides; Read Ch. 10 and 11 of AMP; Homework 7; Sample solution: PDF and source code |
| 10 | 03/31 | Transactional Memories; Intro to Scala | Slides; Scala Intro; Read Ch. 18 of AMP |
| 11 | 04/07 | Scala STM; Hardware Transactional Memories | Slides; Homework 8; Sample solution: PDF and source code |
| 12 | 04/14 | Actors; Intro to Akka | Slides; Bank account code; Link checker code |
| 13 | 04/21 | Intro to Akka | Homework 9; Scala templates; Sample Solution |
| 14 | 04/28 | Concurrent Merge Sort with Actors | Scala code |
| 15 | 05/05 | Failure Handling with Actors; Project Presentations | Slides |
| 16 | 05/12 | Project Presentations |
Mailing List
All course-related announcements will be sent to the course mailing list. You may also use this list to ask questions and discuss issues related to the course. If you have enrolled before the start of the term, you are automatically subscribed to the list. Otherwise, use the above link to subscribe manually.
Grading
Homework (30%), project (30%), final exam (40%).
Projects
You may either choose from one of the projects that I have suggested or define your own project. Your project may either be seminar-based or implementation-based. For the seminar-based projects you will survey a set of coherent research papers. For the implementation-based projects you will solve a specific problem related to concurrent programming in a group of up to two students. In both cases you will write a short report (6 pages for seminar-based projects and 4 pages for implementation-based projects), and present your project at the end of the semester.
Seminar topics include:- Automatic bug detection and localization in concurrent programs:
- Automatic parallelization:
- Software Transactional memory:
- Concurrent Data Structures:
- Data Parallelism and Cloud Computing:
| Choose project | March 28 |
| Presentations | May 5 and May 12 |
| Final reports due | May 19 |
Academic Integrity
Please review the departmental academic integrity policy. In this course, you may discuss homework problems and assignments with other students, but the work you turn in must be your own. Do not copy another student's work. Also, you should consult the instructor before using materials or code other than that provided in class. Copying code or other work without giving appropriate acknowledgment is a serious offense with consequences ranging from no credit to potential expulsion.
