🚀 go-pugleaf

Dr. Vishkin is offering a new Theory Course for the Fall semester.
Admission to the course will be by permission of Dr. Vishkin only.
If you are interested in the course, and meet the prerequisites,
you should attend the first class session and then talk to Dr. Vishkin
individually. 

CMSC858V
Parallel Algorithms and Their Implementation Challenge
(A new CMCS graduate course which satisfies the theory area requirements.)

Semester: Fall 1999.
Proposed Time: Thursday 4-7PM.

Instructor: Dr. U. Vishkin.

Course Goals:
  1. Introduction to the theory of parallel algorithms.
     The course will highlight parallel algorithmic thinking for obtaining 
     good speed-ups with respect to serial algorithms.
  2. 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 
     making this theory of parallel algorithms implementable?

Course prerequisites: CMCS420 or CMSC451; and permission of the professor.

Prerequisite topics: Basic knowledge and understanding of algorithms, 
data structures and computing systems.

Course readings:
  Class notes and research papers will be provided by the instructor.
References:
  - 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".
  - D.J. Kuck. High Performance Computing: Challenges for Future Systems,
    Oxford University Press, 1996.
  - J.L. Hennessy and D.A. Patterson.  Computer Architecture a Quantitative 
    Approach, Second Edition.  Morgan-Kaufmann, San Francisco, 1996.


Some Core Topics:
    1. Introduction to Parallel Algorithms:
       Performance of Parallel Algorithms, Optimality Notions 
    2. Basic Techniques: Balanced Trees, Pointer Jumping,
       Divide-and-Conquer, Partitioning, Pipelining, Accelerated Cascading, 
       Breaking Symmetry 
    3. Trees and Lists: List Ranking, The Euler Tour Techniques, 
       Tree Connection, Evaluation of Arithmetic Expressions 
    4. Searching, Merging and Sorting 
    5. Graphs: Connected Components, Transitive Closure, Paths Problems 
    6. Introduction to Parallel Processing: 
       Principles of available multi-processors and
       instruction-level parallel (ILP) systems, and Parallel Models. 
    7. Studies on limits of ILP extractable from serial code.
    8. Introduction to published expectations from the upcoming 
       "Billion-transistor-per-chip" era:
       (i) Orders of magnitude increase in on-chip hardware resources.
       (ii) Large on-chip memories will enable high bandwidth and low latency.
       (iii) Low overhead hardware/software mechanisms.
     9. 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?


Grading method: 
  A midterm and a final exam will be given.
  Credit will be given to  students presenting research papers, and for
  homework.