Course Summary

Learning how to program parallel computers (multi-core, clusters) productively and efficiently is a critical skill in this era of concurrency. The course will provide an introduction to modern parallel systems and their performance characteristics. It will cover the fundamentals of data-structure design, analysis and implementation for efficient parallel execution; programming abstractions for concurrency; and techniques for reasoning about the behavior and performance of parallel programs. Particular topics to be covered include: data parallelism, fine-grained concurrency, locality, load-balancing, overlapping computation with communication, reasoning about deadlock-freedom, determinacy, safe parallelization, implementing frameworks for concurrency (such as Hadoop Map/Reduce), debugging for correctness and performance. Students will study many parallel programs drawn from a variety of application domains (including high-performance computing, large-scale graph analyses, machine learning, game playing) Students will be expected to complete a series of parallel programming homework assignments. The center-piece of the course will be a semester-long team project focussed on implementing a challenging programming problem with good performance on a cluster of multi-cores, using a modern parallel language, X10.

Pre-requisites: Experience in Java, basic understanding of analysis of algorithms. COMS W1004 and COMS W3137 (or equivalent).

Fall 2010 Course Number: COMS W4995, section 1
Call Number: 81248
Points: 3

Lectures: MW 1:10-2:25 pm, 253 Engineering Terrace

Late Policy: You have one late day to use throughout the semester.  You may use it however you choose.  No other extensions will be granted.

Collaboration Policy:  We take academic honesty extremely seriously, and expect the same of you.  In this course, you are free to discuss homework problems with your classmates. However, each student is to write up his or her own solution and is expected to be able to explain and reproduce the work she or she submits.  Please note the names of your collaborators at the top of your homework submission.   Apart from these exceptions, the Computer Science Department's Academic Honesty policy is in effect.

Grade Breakdown
  • Homework (30%)
  • Midterm Exam (20%)
  • Final Exam (20%)
  • Project (30%)
Instructors:
  • Vijay Saraswat 
    • Email: vs2345@columbia.edu
    • Office Hours: MW 2:30-4:00, CSB 468
  • Martha Kim
    • Email: martha@cs.columbia.edu
    • Office Hours: TuTh 3:30-5:00, CSB 469
  • TA: Karthik Srivatsa
    • Email: kks2128@columbia.edu
    • Office Hours: Fri 10am - 12 noon, Mudd 122A
Outline:
  • Unit 1: Introduction and Motivation
  • Unit 2: X10
  • Unit 3: Performance Debugging
  • Unit 4: Safe Parallelization
  • Unit 5: Indeterminacy
  • Unit 6: Blocking Synchronization