Tuesday, Thursday 11:00-12:20, Room 302
The purpose of the course is to compare and contrast different techniques for developing high-performance applications in today and tomorrow's computational environment where parallelism is ubiquitous. Topics discussed in the course will include the basics of modern parallel hardware architectures, low-level parallel programming with threads, locks and explicit synchronization, high-level programming in modern functional and data-parallel languages, functional reactive programming, software transactional memory, semi-automatic and fully-automatic parallelization. Both language design considerations and compiler implementation considerations will be studied. Not only will students get to study a wide range of existing parallel programming and implementation techniques, but they will also generate some new ideas for research and have an opportunity to help teach and develop course materials. A resume-builder for sure!
This course is co-taught by the Davids (August and Walker). Office hours are by appointment.
David August, CS 209, firstname.lastname@example.org
David Walker, CS 211, email@example.com
All students must subscribe to this list. See here:
To post a message to all the list members, send email to firstname.lastname@example.org
The course will be arranged as a series of modules. For each module, several students in the course will volunteer/be assigned to work on preparing content for each module. For each module, some students will be Leaders (L) and some students will be Developers (D). Every student should be a leader once and a developer once (see the schedule below). The leader will give a lecture on the topic and lead development of an exercise or assignment. The developer will help pretest the assignment and/or help develop infrastructure for it. Deadlines (except for the first 2 weeks of class):
At least 7 days before the first lecture of the module, the student group will email the professors and specify (i) which leader is lecturing on which day, (ii) what materials are being used as sources for the lecture (send links/documents), (iii) what the teaching goals are for each lecture, (iv) what the tentative plans for an assignment are, and (v) what the role of the developers will be. The tentative plans for an assignment are allowed to change as are the role of the developers. However, the professors want to ensure that a reasonable plan is in place. Keep in mind that in general, the leaders will carry the burden of the work. Student groups will be penalized for missing this deadline.
At 9:30am in the morning of the preceeding lecture (ie: Tuesday for a Thursday lecture; Thursday for a Tuesday lecture), the student giving the lecture will give a practice lecture to the Primary Professor guiding that lecture (see below). The professor will give feedback on your lecture, which you will then use to improve it.
In class, on the day of the last lecture in the module, the assignment will be handed out. The module leaders may declare that an assignment is to be done in groups or individually. All assignments will be due 1 week from when they are handed out.
All students associated with a module will help grade the assignment on a scale of Pass+/Pass/Fail. Pass+ is intended to be rare -- a student has a particularly cool insight or an utterly amazing implementation. Pass is the norm -- a student demonstrates that they have put in effort and tried to do the work, even if they are not entirely successful. Fail is the grade given to a student who puts in little or no effort on an assignment.
One of the tools we will be using in the class is the F# programming language. You can run F# on your own Windows, Linux or Mac machine. We are having it installed on some of the department linux machines. To install it on Windows, simply download the latest version of Visual Studio and set the installations defaults to prefer F#. Princeton students can download and use Visual Studio for academic purposes for free:
Once you have downloaded and installed F#, you will also need to download and install the F# powerpack:
To run F# on Linux or a Mac, you must first install mono -- the open source version of the .NET libraries. Here are Nick Johnson's instructions for installing it on Ubuntu Linux.
If you have difficulties with F# installation, please send email to the mailing list. If you successfully install F# on some other version of Linux and would like to post the instructions, please send them to David Walker.
A preliminary course schedule follows. The schedule will likely change and evolve to meet student interests in the course.
|Week||Module||Prof||Students||Links & Resources||Assignments|
|Sep 16||Introduction||Assignment 0 [Due: Saturday, midnight]: Email dpw@cs and august@cs names of two modules you would like to participate in developing: one that you think you know the best and one that you would like to learn more about|
|Sep 21, 23||History, EPIC, Vector Parallelism||August||Oh (L), Prabhu (L)||
Goals: Learn about the history of parallel computing and the evolution of parallel hardware architectures; Learn about vector architectures, SIMD, pipelining and instruction level parallelism.
|Assignment #1: Due Sept 30; A1.tar.gz; A2.tar.gz|
|Sep 28, 30, Oct 5, 7||Thread Parallelism, Memory Models, Properties, Debugging Techniques||August/Walker||Ghosh (L), Beard (L), Zhang (L), Divjyot Sethi (L), Raman (D), Sinha (D)||Threads
Intro Lecture; Threads 2
Goals: understand pitfalls of threads and locks; understand weak memory models; understand desirable properties of concurrent programs; understand selected bug-finding and bug-prevention technologies
|Assignment #2: Due Oct 14|
|Oct 12, 14, 19||Asynchronous, Reactive
Programming & Applications
(Routers, Robots & Animation)
|Walker||Dodds (L), Monsanto (L), Bell (L), Jablin (D), Huang (D), Prabhu (D)||F# Asynch
Lecture; asynch demo code;
asynch program code
Goals: understand problems solved and the difficulties involved in programming reactive programs without asynchs, understand how to program with asynchs, resources, exceptions & cancellation, understand the underlying implementation in F#
Goals: Understand the concept of behaviors and how to program with them, understand one application domain (GUIs, Animation, Robots) for FRP with behaviors, understand the basics of how to implement FRP with behaviors
|Assignment #3: Due Oct 28|
|Oct 21||Functional Message Passing||Walker||Sinha (L)||Erlang
Message Passing Lecture
Goals: Understand how to program concurrent and distributed applications using purely functional message passing techniques
|Oct 26, 28||Haskell, Parallelism and Transactional Memory||Walker||Xi (L), Drutskoy (L), Johnson (D)||
F# STM library,
Goals: Understand problem solved, pros and cons of using STMs, understand how to program with STM in F# or Haskell
|Nov 9, 11||Transactional Memory
|August||Raman (L), Schwartz-Narbonne (L), Liu (D)||
Transactional Memory Lecture 1
Goals: Understand how hard can support transactional memory; Understand the fight between hardware designers (speed) vs language designers (semantics) in the transactional memory space
|Assignment #5: Transactional Memory|
|Nov 16, 18||Languages: StreamIt, Cilk||August||Liu (L), Pondicherry (L), Oh (D), Beard (D), Schlesinger (D)||StreamIt Lecture||Cilk and StreamIt Assignment (Due: Dec 14, 11:59PM)|
|Nov 23||Imperative Message Passing Parallelism||August||Kim (L), Drutskoy (D), Schwartz-Narbonne (D)||MPI Lecture||MPI Assignment (Due: Sat Dec 7, 11:59PM)|
|Nov 30, Dec 2, 7||Parallelism on GPUs and Auto-Parallelization||August||Jablin (L), Johnson (L), Huang (L), Ghosh (D), Bell (D)||
|Dec 9||Nested Data Parallelism
|Walker||Zoufaly (L), Kim (D), Dodds (D),||
Goals: understand the pros and cons of nested data parallel programming; understand the complexity model (work, depth, latency, relation to real machines), understand what computational problems can be solved, gain experience programming with it
|Dec 14, 16||Languages: Massively Parallel Systems (Map-Reduce, Dryad, Azure)||Walker||Schlesinger (L), Xi (D), Zhang (D), Zoufaly (D)||Map-Reduce, FlumeJava, Dryad|
Grades will be assigned based on student participation in class and their contribution to larger group projects and completion of short individual assignments.