ENEE459P/CMSC498M/ENEE699*: Parallel Algorithms, Fall 2014
* To take the course as ENEE699 (Section 3201) please contact the instructor at firstname.lastname@example.org.
Why is it a good idea to take this course?
Serial computers are passe, as practically all computers are becoming increasingly parallel machines.
Parallel algorithmic thinking and programming is in increasing demand as parallel machines such as multi-cores, and other
chip-multi-processing approaches are being deployed.
Much of the core of the computing field is being reinvented for many-core parallelism. However, this is not without problems: the productivity of parallel
programming has long been recognized as a limiting factor for parallel computing.
While major vendors urge rising mainstream programmers (e.g., every Computer Science and Computer Engineering major) to embrace
the history of parallel computing has taught us that:
1. parallel programming of many parallel machines tends to be quite challenging, and
2. especially when it comes to performance, teaching low-level details of parallel programming is a moving target as machine architecture keeps changing.
The traditional computer science and engineering curriculum tends to put its primary emphasis on
robust concepts and ideas. We will do the same in the lecture part of the course; the lectures will be devoted to such robust knowledge.
However, to ensure that these concepts and ideas are properly understood and put in context, this teaching will be complemented
with programming assignments and with discussion of the state of the art.
Time and Venue
Time and Location MW 11:00-12:15. ITV 1100.
Instructor Dr. U. Vishkin.
Instructor's E-mail and Office Hours
email@example.com, M 5:00-6:00 and Thu 5:00-6:00 (by appointment) at AVW 2365.
Homework 1: Exercises 1-5. Due: October 1.
Homework 2: Exercises 6-10. Due: October 13.
Homework 3: Exercises 11,12,14 and 15. Due: October 20.
Homework 4: Exercises 21-25. Due: November 17.
Homework 5: Exercises 26-31. Due: November 24.
Homework 6: Exercises 32,33,35,36 and 37. Due: December 1. Addition only for ENEE699 students: Exercise 34.
Homework 7: Exercises 38,41,42,43,44 and 47. Due: December 8.
Programming Assignments, Tutorial, Manual, Software Tools and Other
Course Teaching 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.
- Introduction to parallel programming, including validation of speed-ups with respect to serial algorithms.
- Elementary understanding of algorithms and data structures
and computing systems.
- For formal prerequisites, please see the Testudo course listing
- Class notes will be available for all the material covered during the semester.
Some of the material will be drawn from these
class notes (104 pages)
- V. Kumar , A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin-Cummings Publishing Co. 1994
J. JaJa, An Introduction to Parallel Algorithms, Addison Wesley, 1992
D.E. Culler and J.P. Singh, Parallel Computer Architecture, Morgan Kaufmann,
- J.L. Hennessy and D.A. Patterson. Computer Architecture a Quantitative
Approach, 4th Edition. Morgan-Kaufmann, San Francisco, 2007
- W. Gropp, E. Lusk, and A. Skjellum Using MPI (2nd Ed.): Portable Parallel Programming with the Message-Passing Interface, MIT Press, 1999
Some Core Topics:
- Introduction to Parallel Algorithms:
Performance of Parallel Algorithms, Optimality Notions, Key Abstractions
- Basic Techniques: Balanced Trees, Pointer Jumping, Divide-and-Conquer,
Partitioning, Pipelining, Accelerated Cascading,
- Trees and Lists: List Ranking, The Euler Tour Techniques,
Tree Contraction, Evaluation of Arithmetic Expressions
- Searching, Merging and Sorting
- Graphs: Connected Components, Transitive Closure, Paths Problems
Grading (applies only to ENEE459P/CMSC498M; not to ENEE699)
- 10% - Written homework
- 40% - Programming projects
- 20% - Mid-term exam, October 22, in class
- 30% - Final exam (comprehensive), 8am to 10am, Wednesday, December 17, in the same classroom as the lectures; this time is set by the UMD Final Exams schedule.