Textbook: An Introduction to Parllal Algorithms, by Joseph JaJa
Lecutre: Tues-Th, 10:30-11:50 pm, 80 Socical Sciences
Office Hours:Mon 4-5 pm, Wds 1-2, 2123 Kemper Hall
Prerequisites: ECS 222A. This can be waived with the consent of instructor; a good grounding in undergraduate algorithms should be sufficient,
especially for someone with parallel programming experience.
Our main focus will be the analysis of algorithms, that is, proving upper and lower bounds on running time, total work, and/or communication. This requires the definition of models of computing: mainly the PRAM and its extensions, but also circuit depth and and communications complexity models.
We will critique both algorithms and models by considering how well they reflect real parallel computing platforms and the programming models presented by languages such as CUDA, MPI, or Hadoop/MapReduce.
|
|
|
We will run this like a seminar course. There will be a reading assignment due before most class meetings. The class meetings will focus on discussion of the reading material. For all the readings, there will be short-answer questions which have to be answered in writing, in class on the day that the reading is due. This is to ensure that everyone does the reading. For each class, we will assign two discussants, who will be responsible for understanding the material completely before class. This will ensure that everyone participates at some point.
There will be three problem sets, to provide practice in algorithm design and analysis, as well as writing. These homework problems, like the reading questions, will be due in class.
There will be an in-class midterm towards the end of the quarter. There will not be a final.
While you are encourged to discuss the homework with each other, you must a) write up your own solutions, in your own words, and b) report, in your solutions, who you discussed the problems with and what other sources (papers, Web, books, etc) you used to arrive at the solution. This is to ensure that you understand the solutions.