CPE
561
Parallel Computing
Introduction to theoretical issues in parallel computation. Topics: Parallel machine models. Design and analysis of algorithms for systolic arrays: arithmetic operations, simple graph algorithms. Algorithms for hypercube-related networks: sorting, routing. PRAM model of computation. Basic PRAM algorithms: prefix computation, sorting, shortest paths, minimum- weight spanning tree. Reducing the processor-time product. simulation of stronger PRAM models by weaker ones. Complexity issues: definition of NC and P-completeness; some simple lower bounds.
Prerequisites:
0612-468 or Consent of Instructor
0612561
(3-0-3)