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
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