- MW 2:00-3:15. JMP 2202

- E-mail: vishkin@umd.edu
- Office hours: M 5:00-6:00 (by appointment) at AVW 2365

- James Edwards, jedward5@umd.edu

- Introduction to the theory of parallel algorithms.
The course will highlight parallel algorithmic thinking for obtaining
good speed-ups with respect to serial algorithms.

The main objective of the class presentations and the written homework will be to study the main theory of parallel algorithms. This includes the design and analysis of parallel algorithms--primarily standard asymptotic analysis. The main objective of the programming assignments will be to reduce this knowledge to practice for improved understandin. One highlight will be achieving hard speedups for the more advanced parallel algorithms studied, demonstrating to students that they can do it even within the limited scope of course programming assignments. The programs will run on real parallel hardware whose design objectives included cost-effective support for the parallel algorithms theory studied. - Close examination of one of the most exciting applied research questions facing computer science and engineering: Will the emerging ``Billion-transistor-per-chip'' era provide a way for building a truly general-purpose parallel computer system on-chip?

- 4-6 parallel programming assignments will be given.
- To be run on the Paraleap, the UMD XMT 64-processor computer.

- 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
- Introduction to state-of-the-art expectations from the emerging "Billion-transistor-per-chip" era. 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.
- 25% - Programming projects. You must submit all programming projects to get a grade.
- 25% - 1st mid-term exam. Exam date: March 7, in class.
- 40% - 2nd mid-term exam. Exam date: May 2, in class.
- There will not be a final exam.

- 5:00-7:00, Thursday, February 16. Place: TBD.