CSE590o Autumn 2006: Parallel Programming

 

Notice:

A brief version of Chapter 7 is included in the Chapter 7 & 8 link below. It’s short; we’ll discuss it this week.

 

The Announcement:

CSE590o Parallel Programming
Larry Snyder
Wednesday 2:30-3:20  Allen 503


Parallel programming is different from standard sequential programming: The preferred algorithms are different, the resources being optimized are different, algorithm analysis is different and much more complex, etc. In the past parallel programming was an "enrichment" class, but now because multi-core chips are standard on consumer platforms, parallel programming is essential. As Sutter and Larus wrote in Queue

http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=332

programs that cannot exploit concurrency will fall off of the performance curve. The free lunch is over.

Fall 590o, which usually treats advanced research topics, will instead teach basic parallel programming. The main resource for the class is a draft of a textbook I'm writing with Calvin Lin (UT Austin prof and UW CSE alum) on parallel programming. The class will be largely independent study using the book; students will write and run parallel programs in the standard languages; students will be asked to anonymously critique the book.

 

The Book: Fundamentals of Parallel Programming, Calvin Lin and Larry Snyder, Addison Wesley, DRAFT

 

The Deal: Students will learn the basics of parallel programming and practical parallel algorithm design; the authors will receive the thoughtful feedback of the students. An anonymous email link has been set up for this purpose. Please use the link whenever anything comes to your notice. Your feedback is most useful if

(a)    It ignores, typos, poor grammar, formatting bugs, etc. Editors will sweep the document.

(b)   It focuses on the clarity of the explanations, the accuracy of the diagrams and code segments, organization, topic selection, etc.

(a)    Refers to specific pages in the document: Fundamentals

Your comments cannot be acknowledged specifically, of course, it’s anonymous! But at the end of the term, all participants who sent one or more critiques (honor system) can add their names to a list to allow the authors to give proper credit and thanks in the Acknowledgments of the published book. 

 

The Schedule (to be adjusted incrementally):

Week 1: Overview

            Prep: Read Sutter and Larus

            Resources: Draft Chapters 1 & 2

Week 2: Parallel Model of Computation

            Prep: Read Chapters 1 & 2

            Resources: Draft Chapters 3 & 4

Week 3: Terminology and Concepts

            Prep: Read Chapter 3

Week 4: Algorithms & Techniques 1

            Prep: Read Chapter 4

            Resources: Draft Chapters 5 & 6

Week 5: Algorithms & Techniques 2

            Prep: Read Chapter 5

Week 6: Threading

            Prep: Read Chapter 6

            Resources Draft Chapters 7 & 8

Week 7: Message Passing

            Prep: Read Chapter 7

Week 8: ZPL

            Prep: Read Chapter 8

Week ~: Thanksgiving, no class

Week 9: Realities of Achieving Performance

Week A: Textbook Critique and Discussion

 

The Assignments

1) For the threading assignment, you are given an annotated radix sort program.  The task is to create a multithreaded version of this program. The annotations show where threading code must be added to make the program multithreaded.

 

2) For the ZPL assignment, there are two problems.  You can grab a copy of the software from the ZPL page, and for purposes of working through the assignment, it suffices to use the sequential version.