CSE 524, Parallel Algorithms
Spring 1995

General Information

Meets: TTh 9:00-10:30, Sieg 225
Instructor: Richard Anderson
Office Hours: By appointment
E-mail address: anderson@cs
Office: Sieg 410
Homework and Exams

Catalog Description

Design and analysis of parallel algorithms: fundamental parallel algorithms for sorting, arithmetic, matrix and graph problems, and additional selected topics. Emphasis on general techniques and approaches used for developing fast and efficient parallel algorithms and on limitations to their efficacy. Prerequisite: CSE 521 (or equivalent). CSE Majors only.

Homework Assignments and Notes

Syllabus

Homework 1 Due Thursday, April 6.

Homework 2 plus some rambling comments about the course. Due Thursday, April 20.

Lecture Transparencies, April 11 Code and analysis for list ranking.

Old lecture notes on connected components (this algorithm is simpler and correcter than Section 5.1.3.) LaTeX version

Pointers to papers about pointers References for EREW and CREW Connectivity and the Ullman-Yannakakis paper.

Homework 3 Due Tuesday, May 2.

Union-Find Paper .ps or .dvi

Homework 4 Due Thursday, May 18.

Certified Write-All Paper .ps or .dvi This implies the existence of a more efficient consensus algorithm based upon swap - although it is not likely something you are going to see inside your next supercomputer.

Homework 5 Due Thursday, May 25.

Asynchronous P-RAM references - Martel et al. FOCS 1990, and Buss et al. (Manuscript) .

Notes on memory models .

Real Description

As a special topics course, the content is up to the whim of the instructor. A more descriptive title for this year's course would be: A theory of shared memory parallel computing, or maybe, topics in the theory of SMPC. The course will start with a collection of basic algorithms, and then we will spend some time on models of computation. The syllabus gives a list of topics which could be covered.

My use of the term "shared memory" is to indicate that we will not be looking at topics which pertain to specific interconnection topologies. We will consider some situations where the cost of memory access is non-uniform.

The course will be a theory course in the sense that we will not consider particular real machines, we will prove some theorems, and you will not be expected to log on to a parallel machine. However, topics may be motivated by practical considerations. Our goal in developing parallel algorithms will be to come up with algorithms which could conceivably be efficient on some parallel machines.

I am expecting that there will be three or four problem sets, containing a mix of routine and challenging problems. I am not going to require a project, (but I will be happy if students do outside work on course related topics).

The text for the course will be "An Introduction to Parallel Algorithms" by Ja Ja. This is a nice book, although I will not be following it very closely. If you are feeling exceptionally cheap, you could probably get by without purchasing a copy. My original plan, when I volunteered to teach the course a year ago, was that the text would be "A Theory of Shared Memory Parallel Computing" by Anderson. However, this book is progressing about as fast as Volume 7 of the Art of Computer Programming, so I chose the Ja Ja book instead.

I am going to be quite flexible on how this course is taught. My choice of topics will be influenced by what is considered interesting or uninteresting. There is also a choice as to teach this course as either a traditional lecture course, or to work in some research content. I have a number of open problems in mind which could turn into very nice research results. I could present my half baked ideas on some of these, provided that others have the interest and energy to think about them.







anderson@cs.washington.edu