 |
Anil Maheshwari
School of Computer Science
95.574: Introduction To Parallel Algorithms
|
Course
Outline and Home Page
This is the 95.574 home page "http://www.scs.carleton.ca/~maheshwa/95574.html".
Check it regularly for new information.
Instructor: Anil Maheshwari,
Office: School of Computer Science, Carleton University, Ottawa,
Canada K1S 5B6, room 5364, Herzberg Physics Building,
Phone: (613) 520-4333, Fax: (613) 520-4334,
OFFICE HOURS: by e-mail appointments.
E-mail: maheshwa@scs.carleton.ca,
WWW:http://www.scs.carleton.ca/~maheshwa.
Term: Winter 2000, Class Hours: Monday 11:30 to 2:30PM
Classroom: 304 DT
Course-TA: None
Course Objectives
-
Understanding parallel models of computations (PRAM, BSP and Fixed Connection
Networks).
-
Design, Analysis and Implementation of parallel algorithms (Sorting,
Graph, Computational Geometry).
Reference Materials
-
(CLR) Cormen, Leiserson and Rivest: "Introduction to Algorithms", McGraw
Hill.
-
(Reif) John Reif, "Synthesis of Parallel Algorithms", Morgan Kaufman.
-
(JaJa) Joseph JaJa, "Introduction to Parallel Algorithms", Addison-Weseley.
-
(Leighton) F.T. Leighton, "Introduction to parallel architectures and
algorithms", Morgan Kaufman.
-
(Knuth) D.E. Knuth, "The art of computer programming", Vol. 3 (Searching
and Sorting), Addison-Weseley.
-
Raghavan and Motwani, "Randomized Algorithms", Cambridge University
Press.
-
ACM-SPAA Proceedings of 1999, 1998 and 1997.
-
Several Journal Articles.
Contents
-
BSP: Model, Deterministic Sorting, and Introduction to MPI Library.
(Valiant's CACM 33, August 1990)
-
CGM: Model, Computational Geometry and Graph Algorithms. (www.scs.carleton.ca/~dehne)
-
Coarse Grained Models
-
PRAM: Model and Fundamental Techniques (JaJa's Book, Chapter 2)
-
PRAM: List Ranking, Sorting (JaJa's Book, Chapter 3 and 4)
-
PRAM: Graph Algorithms (JaJa's Book, Chapter 5).
-
Fixed Connection Networks: Linear Array, Mesh, Hypercubes. 0-1 Sorting
Lemma, Sorting Networks, Sorting on linear array - mesh - hypercube, Lower
Bounds on Sorting. (Leighton)
-
Sorting and Routing in Fixed Connection Networks (Leighton and Raghvan-Motwani)
-
Simulation among different models.
-
Parallel Complexity Theory
MPI: A MESSAGE PASSING INTERFACE STANDARD: MPI is a standard message
passing library for parallel C programming on the Intel iPSC/860, Intel
Paragon, CM/5, UNIX networks, and many other architectures. We will use
it for the parallel programming assignments in this course. A complete
MPI documention is available on the web.
Course evaluation (to be decided)
1. Project (Implementation Based in Algorithmic Engineering Style) 50%.
2. Seminar and a 4-page report on a recent research article 25%.
3. Mid-Term Assignment 25%.
http://www.scs.carleton.ca/~maheshwa