CMCS751/ENEE759K: Parallel Algorithms, Spring 2002

Time and Location

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.

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, Second Edition. Morgan-Kaufmann, San Francisco, 1996.

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 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 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 task?