CMCS751/ENEE759K: Parallel Algorithms, Spring 2002
Time and Location
- Wednesday 3:30-6PM. CLB0109.
Instructor: Dr. U. Vishkin
- Office hours: MW 11-12, AVW 2365
- E-mail: firstname.lastname@example.org
Teaching Assistant: Ms. Fang Liu
- Office hours: Tue 2:30-3:30, AVW 1151
- E-mail: email@example.com
- 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,
- Basic knowledge and understanding of algorithms and data structures
and computing systems.
- Class notes and research papers will be provided by the instructor.
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, Second Edition. Morgan-Kaufmann, San Francisco, 1996.
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,
- 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 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
(i) Over 4 order 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
- Exam (on May 1, 2002) and homework.
Homework will reflect 20% of the grade.