Parallel Programming

Prof. Christoph von Praun - Winter 2011/2012

Fachwissenschaftliches Wahlpflichtfach Date and Place Monday 8:00-11:15 Room Q305 News Feed The oral exams will be on February 10, 2012.

Outline

Follow these guidelines to install the X10 Development Toolkit as plugin of your eclipse platform.

You can import the solutions of the programming assignments into your eclipse workspace as follows:
(1) Start eclipse, (2) Menu File-Import, (3) Select General-Existing Project into Workspace, (4) Specify archive file, (5) Finish.

X10 Resources

Examples and programming exercises in this course will be based on the programming language X10. Philippe Charles, Christopher Donawa, Kemal Ebcioglu, Christian Grothoff, Allan Kielstra, Christoph von Praun Vijay Sarsawat and Vivek Sarkar. X10: An Object-Oriented Approach to Non-Uniform Cluster Computing, Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), October 2005. Overview paper and motivation for a new parallel programming language. Vijay Saraswat at al.: Report on the Programming Language X10 - Version 2.0.2, Draft, February 2010. X10 Website Sample X10 programs

Literature

Introduction, the Era of Multicore Programming

• David Patterson et al.: The Landscape of Parallel Computing Research: A View From Berkeley. August 2007 [www]
  Related Google Tech Talk "The Parallel Revolution Has Started: Are You Part of the Solution or Part of the Problem?" [youtube]
• Hadi Esmaeilzadehm, Emily Blem, Renee St. Amant, Karthikeyan Sankaralingam, Doug Burger: Dark Silicon and the End of Multicore Scaling, International Symposium on Computer Architecture (ISCA), 2011. [pdf]

Models for Parallel Computation

• Maurice Herlihy and Nir Shavit: The Art of Multiprocessor Programming, Elsevier/Morgan Kaufmann 2008.
  For our course, chapter 3 on concurrent objects is of particular interest. This book is available online.
  
• Leslie Lamport: Time, Clocks and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7), 558-565, 1978. [pdf]
  Original article that defines the happened-before relation.

Scalability and Performance Analysis

• Maged Michael, Jose Moreira, Doron Shiloach, Robert Wisniewski: Scale-up x Scale-out: A Case Study using Nutch/Lucene. Parallel and Distributed Processing Symposium (IPDPS), 2007. [pdf]
• S. Chen, P. B. Gibbons, M. Kozuch, V. Liaskovitis, A. Ailamaki, G. E. 
 Blelloch, B. Falsafi, L. Fix, N. Hardavellas, T. C. Mowry, and C. 
 Wilkerson. Scheduling threads for constructive cache sharing on 
 CMPs. Symposium on Parallel Algorithms and Architectures (SPAA), 
 2007. [pdf]

Higher-Level Parallel Programming Models

• John Nickolls, Ian Buck, Michael Garland, Kevin Skadron: Scalable Parallel Programming with CUDA, ACM QUEUE March/April 2008 [pdf]
• James Reinders: Intel Threading Building Blocks. O’Reilly, 2007.
  This book is available online.
  Arch Robison gave a keynote talk about Generic Parallel Algorithms in Intel® Threading Building Blocks at LCPC 2008. [pdf]
  Intel TBB Website [www].
• Philipp Haller and Martin Odersky: Scala Actors: Unifying thread-based and event-based programming, Theoretical Computer Science, Volume 410, Issues 2-3, February 2009. [pdf]
• Jeffrey Dean, Sanjay Ghemawat: MapReduce: Simplified Data Processing on Large Clusters, OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004. [www]
  A brief video interview with the authors is available. [www]

Recommended Books

• Timothy G. Mattson, Beverly A. Sanders and Berna L. Massingill: Patterns for Parallel Programming, Addison-Wesley, 2006.
  This book is available online.
• Brian Goetz, Joshua Bloch, Joseph Bowbeer, Doug Lea, David Holmes, Tim Peierls, Java Concurrency in Practice Addison-Wesley, 2006.
  This book is available online.

Grading

30% class participation and projects, 70% oral exam.

Last change: 18-Jan-2012.