ENEE459P/CMSC498M/ENEE699*: Parallel Algorithms, Fall 2014
* To take the course as ENEE699 (Section 3201) please contact the instructor at vishkin@umd.edu.
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 multicores, and other
chipmultiprocessing approaches are being deployed.
Much of the core of the computing field is being reinvented for manycore 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
generalpurpose parallelism,
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 lowlevel 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:0012:15. ITV 1100.
Instructor Dr. U. Vishkin.
Instructor's Email and Office Hours
vishkin@umd.edu, M 5:006:00 and Thu 5:006:00 (by appointment) at AVW 2365.
Grader TBA
Dry Homework
Homework 1: Exercises 15. Due: October 1.
Homework 2: Exercises 610. Due: October 13.
Homework 3: Exercises 11,12,14 and 15. Due: October 20.
Homework 4: Exercises 2125. Due: November 17.
Homework 5: Exercises 2631. 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
Programming Assignments, Tutorial, Manual, Software Tools and Other
Information
Course Teaching Goals
 Introduction to the theory of parallel algorithms.
The course will highlight parallel algorithmic thinking for obtaining
good speedups with respect to serial algorithms.
 Introduction to parallel programming, including validation of speedups with respect to serial algorithms.
Prerequisite Topics
 Elementary understanding of algorithms and data structures
and computing systems.
 For formal prerequisites, please see the Testudo course listing
Course readings:
 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)
Reference books:
 V. Kumar , A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms. BenjaminCummings 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,
1999
 J.L. Hennessy and D.A. Patterson. Computer Architecture a Quantitative
Approach, 4th Edition. MorganKaufmann, San Francisco, 2007
 W. Gropp, E. Lusk, and A. Skjellum Using MPI (2nd Ed.): Portable Parallel Programming with the MessagePassing 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, DivideandConquer,
Partitioning, Pipelining, Accelerated Cascading,
Breaking Symmetry
 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%  Midterm 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.