ENEE759K/CMSC751: Parallel Algorithmics, Spring 2009
Time and Location
Instructor: Dr. U. Vishkin
- E-mail: vishkin@umd.edu
- Office hours: T 3:30-5:00 (by appointment) at AVW 2365.
Recorded Lectures
Video recording of all lectures
Grader for Dry Homework
Programming Assignments
Tutorial, Manual, Software Tools and Other
Information
Dry Homework
Homework 1: Exercises 1-5. Due: Feb 26.
Homework 2: Exercises 6-10. Due: March 5.
Homework 3: Exercises 11-16. Due: March 12.
Homework 4: Exercises 17-23. Due: March 26.
Homework 5: Exercises 24-28. Due: April 2.
Homework 6: Exercises 29-33. Due: April 14.
Homework 7: Exercises 34-39. Due: April 28.
Homework 8: Exercises 40-46. Due: May 7.
Course Goals
- Introduction to the theory of parallel algorithms.
The course will highlight parallel algorithmic thinking for obtaining
good speed-ups with respect to serial algorithms.
- Close examination of one of the most exciting applied research questions
facing computer science and engineering:
Will the upcoming ``Billion-transistor-per-chip'' era provide a way for
building a truly parallel computer system on-chip?
The examination has 3 parts: (i) operational (i.e., how will the system
work?), (ii) functional (i.e, for what application it will be useful?), and
(iii) facilitating science and technology (e.g., algorithms,
deep-submicron VLSI).
Of Special Interest
- 6 parallel programming assignments will be given.
- To be run on the Paraleap, the UMD XMT 64-processor computer.
Prerequisite Topics
- Basic knowledge and understanding of algorithms and data structures
and computing systems.
Course readings:
- Class notes and research papers will be provided by the instructor.
Please download and print out the first item (104 pages) under
http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/papers.html
Reference books:
-
J. JaJa, An Introduction to Parallel Algorithms, Addison Wesley, 1992.
-
D.E. Culler and J.P. Singh, Parallel Computer Architecture, Morgan Kaufmann,
1999. The following quote appears under the title Potential Breakthroughs:
..."breakthrough may come from architecture" ... "that is,
to truly design a machine that can look to the programmer like a PRAM".
- J.L. Hennessy and D.A. Patterson. Computer Architecture a Quantitative
Approach, 4th Edition. Morgan-Kaufmann, San Francisco, 2007.
Some Core Topics:
- Introduction to Parallel Algorithms:
Performance of Parallel Algorithms, Optimality Notions
- Basic Techniques: Balanced Trees, Pointer Jumping, Divide-and-Conquer,
Partitioning, Pipelining, Accelerated Cascading,
Breaking Symmetry
- Trees and Lists: List Ranking, The Euler Tour Techniques,
Tree Connection, Evaluation of Arithmetic Expressions
- Searching, Merging and Sorting
- Graphs: Connected Components, Transitive Closure, Paths Problems
- Strings: Some string matching algorithms
- Introduction to Parallel Processing:
Principles of available multi-processors, thread-level parallel (TLP) systems and instruction-level
parallel (ILP) systems, and Parallel Models
- Studies on limits of ILP extractable from serial code
- Introduction to published expectations from the upcoming
"Billion-transistor-per-chip" era:
(i) Over 4 orders-of-magnitute of potential improvement over the CPU of the first PC.
(ii) Large on-chip memories will enable high bandwidth and low latency.
(iii) Low overhead hardware/software mechanisms
- Suggestions and possibilities for putting it all together.
Can fine-grained large scale on-chip parallel computing be harnessed
towards faster completion time of a single general-purpose computing
task?
Grading
- 10% - Written homework.
- 30% - Programming projects. You must submit all programming projects
to get a grade.
- 25% - 1st mid-term exam. Exam date: April 7, in class.
- 35% - 2nd mid-term exam. Exam date: May 5, in class.
- There will not be a final exam.