Programming Paradigms for Concurrency

CSCI-GA 3033-014

NYU, Graduate Division, Computer Science Course - Spring 2014

Information

Class MeetingsMon 5:10-7:00pm in CIWW 317
First LectureJan 27, 2014
Last LectureMay 12, 2014
Final ExamMay 16, 2014, 5:10-7:00pm in CIWW 317
InstructorThomas Wies
OfficeCIWW 407
Office HoursTue 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

Recommended Reading

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: Important Dates:
Choose projectMarch 28
PresentationsMay 5 and May 12
Final reports dueMay 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.