ENEE459P/CMSC498V: Parallel Algorithms, Spring 2008
Time and Location
- MW 10:00-11:15. CHE 2110.
Instructor: Dr. U. Vishkin
- E-mail: vishkin@umd.edu
- Office hours: MW 11:15-12:15 (by appointment) at AVW 2365.
Grader: TBD
Dry Homework
Homework 1: Exercises 1-5. Due: Feb 25.
Homework 2: Exercises 6-10. Due: March 3.
Homework 3: Exercises 11-15. Due: March 10.
Homework 4: Exercises 16-20. Due: March 24.
Homework 5: Exercises 21-25. Due: March 31.
Homework 6: Exercises 26-30. Due: April 7.
Homework 7: Exercises 31-36. Due: April 16.
Homework 8: Exercises 37-41. Due: April 28.
Homework 9: Exercises 42-46. Due: May 7.
Programming Assignments
Tutorial, Manual, Software Tools and Other
Information
Motivation
The motivation for this new undergraduate course on parallel algorithms is that parallel algorithmic thinking and programming is in increasing demands as multi-cores, and other
chip-multi-processing approaches are being deployed. These approaches are in line with the roadmap charted by industry vendors, such as Intel, AMD, IBM and SUN.
In the past only the very top undergraduate students were able to learn this material by taking the graduate class.
The increasing need implied the broader access provided by this course.
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 current ``Billion-transistor-per-chip'' era provide a way for
building a truly parallel computer system on-chip?
Of Special Interest
- Around 5 parallel programming assignments will be given.
- To be run on the new XMT 64-processor computer that was invented and built at UMD.
See http://www.umiacs.umd.edu/users/vishkin/XMT/index.shtml
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, 3rd Edition. Morgan-Kaufmann, San Francisco, 2002.
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) 4-6 orders-of-magnitute of potential improvement over the CPU of the first PC.
(ii) Large on-chip memories and interconnection networks 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
- 15% - Written homework.
- 25% - Programming projects. You must submit all programming projects
to get a grade.
- 25% - Mid-term exam. Exam date: April 2, in class.
- 35% - Final exam.