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