ENEE759K/CMSC751: Parallel Algorithmics, Spring 2009

Time and Location

Video recording of all lectures Video recording of all lectures

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.

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).

Basic knowledge and understanding of algorithms and data structures and computing systems.

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.

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?

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.