CS342: Algorithms for Parallel and Distributed Systems

Prerequisites: CS341 is certainly sufficient. CS212 is a must and CS202 would be useful as well; you must at least be taking CS202 as a co-requisite.

Course Requirements: In this course we will experiment with a new approach to teaching; my goal is to replace the traditional lecture approach with a more active approach to learning, in which you figure out much of the material yourselves (with faculty assistance). This necessitates a somewhat different approach to the evaluation of your work; we will discuss the details in the first lecture.

Textbook: Parallel Computing: Theory and Practice, by Michael J. Quinn. 2nd Edition, McGraw Hill.

The goal of this course is to teach you to design efficient (fast!) algorithms for parallel and distributed systems. Much of the course will be focused on implementing the algorithms on the network of workstations in LC020, our Parallel and Distributed Laboratory, but we will also spend time evaluating the algorithms theoretically; one subgoal of the course is to integrate the theory and practice in a meaningful fashion.

The following is a rough outline of the topics we will cover; it is to some extent subject to change.

I. Fundamentals. Review of Asymptotic Analysis. Shared Memory vs. Distributed Memory. Speedup/Efficiency. (.5 weeks)

II. The fixed-connection model. Algorithms for linear arrays and meshes. (1.5 weeks).

III. The PRAM model. The logP model. Simple PRAM algorithms and logP model algorithms. Introduction to Programming in MPI. (2 weeks)

IV. Scheduling and Load Balancing (1 week)

V. Elementary Distributed Algorithms (2 weeks)

VI. Building a Parallel Database (4 weeks)

VII. Numerical Algorithms (2 weeks)

Joel Wein
Office: LC230
Phone: x3376
E-mail: wein@mem.poly.edu

CS342 || Introduction || Laboratory || Syllbus || Homeworks || Active Assignments || Polytechnic || CIS Dept.
webmaster@ebbets.poly.edu