Parallel and Distributed Algorithms

CS 6/76105

Spring 2007

Reading Assignments:

Problem Assignments:

Set Number	Date Assigned	Problems	Presentation Date
1	2/09	Chapter 1 (Introduction) Problems & Selected Solutions*	2/16
2	2/26	PRAM Problems & Selected Solutions*	3/21
3	3/13	Linear Array & 2-D Mesh Problems & Selected Solutions*
4	4/09	Hypercube and Bus-Based Problems & Selected Solutions*
5		Associative & Asynchronous Models Problems
6

* These solutions were prepared by an earlier grader for this class. They are posted "as is" (i.e., without being checked for accuracy),

Presentation Slides:

Title	Main References	Last Update
Course Syllabus & Overview	Slides
Introduction and General Concepts	Ch 1-2 of Akl Text, Ch. 7 of Quinn	1/23
The PRAM Model	Ch 2, 4-6 of Akl Text & Akl Book Chapter	2/2
PRAM Search Algorithm	Chapter 5 Akl Text
Linear Arrays	Ch 7 of Akl Text, &Akl Book Chpt, Also, enhanced Figures 7.4, 7.6, 7.11	2/13
Mesh Model	Chapter 8 of Akl Text & Akl Book Chpt & Leighton	2/21
End of Material covered on Midterm
Hypercube Model	Ch 9 Akl Text & Akl Book Chapter	2/28
Models using Buses	Ch 10 of Akl Text & Akl Book Chpt	3/21
Midterm (Covers through Mesh Model)	Study Guide (comments added to original)	4/06
SIMD & Associative Models: Part I -SIMD	See References in Slides	3/23
SIMD & Associative Models: Part II - ASC/MASC Models	See Reading Assignments. You can print a copy of each paper from website given on slide 6	4/15
Associative String Matching Algorithms by Shannon Steinfadt	Thesis & cited paper by Mary Esenwein	4/23
IS Control Structure for MASC Model by Wittaya Chantamas	Cited papers co-authored by Wittaya	4/24
Multi-Tasking Models I: General Concepts	Chapter 3, "Intro to Parallel Computing" (Grama, Gupta, Karypis, Kumar )	5/15
Multi-Tasking Models II: Task/Channel Model; Communications Model; Isoefficiency Metric	Chapter 3 & 7 of Quinn Textbook; Section 2.5 of "Intro to Parallel Computing" textbook (Grama, Gupta, Karypis, Kumar)	5/15
Multi-Tasking Models III: The BSP model	Slides	4/15
Final Exam	Study Guide for Final	5/11

Textbook References:

1. Selim Akl, Parallel Computation: Models and Methods, Prentice Hall, 1997.
   • An updated ONLINE VERSION of this textbook will be provided for this class, but requires a password to access.
2. Michael Quinn, Parallel Programming in C with MPI and OpenMP, McGraw Hill, 2004.
   • This textbook was ordered by bookstore for class.

Other Primary References:

1. Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar, Introduction to Parallel Computing, 2nd Edition, Addison Wesley, 2003.
   • Copies of needed reference material will be made available or posted on website
2. Selim Akl, The Design of Efficient Parallel Algorithms, Chapter 2 in “Handbook on Parallel and Distributed Processing” edited by J. Blazewicz, K. Ecker, B. Plateau, and D. Trystram, Springer Verlag, 2000, pg 18-91,
   • SELECTED READINGS from Chapter 2 (password required).
   • This lengthy book chapter contains a lot of the material that will be covered from Akl's textbook.

My Reference List for Course: (May expand during course. Key addition listed below. )

• R. Vaidyanathan and J. L. Trahan, Dynamic Reconfiguration: Architectures and Algorithms, Kluwer
  Academic/Plenum Publishers, New York, 2003.
  • Contains material that is related to Chapter 10 in Akl Textbook (on Bus-Based Models).