Cormac Flanagan     UCSC School of Engineering

CMPS 253: Advanced Programming Languages

Concurrent Programming and Transactional Memory

---

• Instructor: Cormac Flanagan

• Class time: 12-1:45pm, Tuesdays and Thursdays

• Class location: NEW: E2-392

• Discussion group: http://groups-beta.google.com/group/ucsc-cmps-253-spring-2007 (request membership, and I will approve it).

---

Course Overview

The free lunch is over. It lasted fifty years.

During that time, Moore's law meant that our programs go faster when we buy a next-generation processor. Moving forward, while next-generation chips will have more CPUs, each individual CPU will be no faster than the previous year's model. If we want our program to run faster, we must learn to write parallel programs.

Parallel programs execute in a non-deterministic way, so they are hard to test, and bugs can be almost impossible to detect, reproduce, or fix. Many years of experience has shown that writing a correct parallel programs is typically substantially harder than writing an equivalent sequential program.

In this course, we will survey the state-of-the-art in parallel programming, and the programming languages that support these efforts. We will pay particular attention to the emerging and active field of transactional memory, which adapts many ideas from database transactions to general purpose programming languages. We will also review more traditional lock-based programming, as well as alternative techniques based on functional programming, speculative execution, etc.

---

Course Materials

Textbook: Transactional Memory, James R. Larus and Ravi Rajwar (preview copy). In addition, we will study a number of research papers on this topic, according to the schedule below.

---

Prerequisites

CMPS203 Programming Languages, or a similarly semantics-oriented course in programming languages.

---

Course Expectations and Requirements

1. Class Participation (30% of total grade) Discussions will be a key part of the class learning experience, and will help you internalize the technical material and understand important connections. Students are expected to (a) complete and take notes on assigned readings before attending class, (b) arrive punctually, and (c) engage actively in class discussions. In this class we will all share responsibility for teaching and learning.

2. Class Presentations (20% of total grade) Each student will give oral presentations during class on a particular topic, mostly chosen from the textbook. These presentations should highlight the key points – main definitions, theorems, properties, design choices, etc – and should include clear motivation for the topic. Either blackboard or powerpoint presentations are acceptable. Students are encouraged to engage the audience as much as possible, by asking questions and inciting discussion. Each class will consist of one student presentation on a particular topic, followed by (or preferably co-mingled with) a discussion of that topic. If you have little experience giving presentations, please consult Norman Ramsey's advice on How to give a talk.

3. Presentation Buddy (5% of total grade) Each student presenter will be helped by a corresponding “buddy”, who will listen to and provide constructive feedback on a trial run of the presentation, with the goal of improving the classroom presentation. (You might find two trial runs, one short and one a bit longer, to be helpful.) The buddy grade will correspond to the grade for the resulting classroom presentation.

4. Scribe (10% of total grade) The “buddy” for each presentation will also function as a “scribe” who documents the classroom discussion. This write-up should not be a repetition of the corresponding book chapters, but an addendum that documents the key insights of the discussion and emphasizes the key points. It should be a PDF file 2-3 pages long and emailed to the Professor before the next class for posting on the web page.

5. Homework (15% of total grade) Homeworks will be assigned during the quarter, and are expected to be completed on time, before the start of the class when they are due. Late homeworks will be deducted 10% for each day (or fraction of day) late.

6. Project (20% of total grade) Students will complete a class project, either individually or in pairs. The project will offer each student broad latitude to tailor a project to his or her own interests; possibilities include a design project, a programming (application) project, an implementation project, or a theory project. Oral and written presentations of each project are expected.

There will be no examinations.

---

Class Schedule

This schedule is quite tentative, and will certainly change as the quarter progresses. In particular, you should be prepared to present one class before your scheduled slot, in case the discussion of the preceeding topic finishes early.

---

Homeworks

• CMPS 253 Spring 2007 Homework 1

• CMPS 253 Spring 2007 Homework 2

---

Project plans

• Implement a highly-concurrent queue (Jaeheon, Caitlin, Esteban)

• Implement a concurrent SAT solver with lemma sharing (Kenn, Aaron)

• Implement a software transactional memory system (Alamelu, Sangeeta, ...)

• Implement CML primitives in Concurrent Haskell (Avik)

• Automatic parallelization (Karl)

• STM (Bogdan)

• STM (David)

---

Possible project ideas

• Use some existing concurrent or transactional language to implement a modest application of some kind.

• Implement some small application in a variety of concurrent languages, for comparison purposes. Could be done as a team project.

• Implement some transactional memory subsystem, perhaps via an API and possibly leveraging reflection mechanisms, such as in Java.

• Investigate new language constructs to support concurrency.

• Concurrent ML and Concurrent Haskell both garbage collect threads. You could imagine doing this in (say) Java, if a thread is waiting on a lock that is otherwise garbage, it could be killed. One stretch project idea is to implement this inside some existing JVM, and to see its effect on performance.

• Implement the Concurrent ML concurrency abstractions in terms of the MVars of Concurrent Haskell.

• MapReduce and Sawzall are really functional programming languages, and provide opportunities for cross-pollination between these domains

  • You could implement the Sawzall aggregators in a functional language, and see how nicely they fit. (This might be a bit small, though).

  • You could imagine supporting more general functional computations that are distributed over a grid in a manner like MapReduce. This could express multiple MapReduce passes (necessary for rebuilding indexes, etc) as a single computation, which could enable different or better distribution techniques. You could experiment with query optimization techniques, analogous to in SQL databases.

---

Useful resources

• http://research.microsoft.com/~simonpj/papers/stm/index.htm

• http://en.wikipedia.org/wiki/Software_transactional_memory

• http://www.cs.wisc.edu/trans-memory/biblio/index.html

• http://supertech.csail.mit.edu/cilk/

• http://weblogs.mozillazine.org/roadmap/archives/2007/02/threads_suck.html

• The Landscape of Parallel Computing Research: A View from Berkeley

---

• SiteMeter