OUTLINE (Tentative)

1. Asymptotic Analysis: Review
   1. O, Omega, and Theta very briefly
   2. Handouts on notation
      1. Back of M&S text
      2. CLR book or other data structures/algorithms books (reference)
   3. Homework on notation
2. Sorting Networks
   1. Combinational Circuits
      1. Comparator
      2. Wire
   2. Batcher's Bitonic MergeSort
   3. Homework on Sorting Networks
3. Introduction to Parallel Algorithms and Architectures
   1. RAM (A, 36-39)
      1. Memory with m locations
      2. Processor (1)
      3. Memory Access Unit
      4. Each step of an algorithm:
         1. Read phase
         2. Compute phase
         3. Write phase
      5. Discuss time per step
   2. PRAM (A, 39-50)
      1. n identical processors
      2. A common memory with m locations
      3. Memory Access Unit
      4. Memory Access:
         1. Exclusive Read
         2. Concurrent Read
         3. Exclusive Write
         4. Concurrent Write
            1. Priority CW
            2. Common CW
            3. Arbitrary CW
            4. Random CW
            5. Combining CW
      5. Discuss time per step
      6. Simple examples on PRAM
         1. Minimum
         2. Broadcast
         3. Prefix
            1. Finding roots in a forest
            2. Running sum
            3. Running minimum
         4. Search
   3. Distributed Memory vs. Shared Memory
   4. Distributed Address Space vs. Global Address Space
   5. Interconnection Networks
      1. Measures
         1. Maximum degree of a processor
         2. Communication Diameter
         3. Bisection Width
         4. Time to perform basic operations
      2. Models (discuss: measure, searching, semigroup)
         1. PRAM (as means of comparison)
         2. Linear Array and Ring
         3. Mesh
         4. Mesh-of-Trees
         5. Pyramid
         6. Hypercube
   6. SIMD vs. MIMD
   7. Granularity
   8. General Performance Measures
      1. Running time:
      2. Cost:
      3. Work
      4. Speedup:
      5. Efficiency:
      6. Discuss relationship between measures and discuss goals of algorithm development
      7. Amdahl's Law: , where is the fraction of operations that must be performed sequentially.
   9. Homework on models of computation
4. Matrix Multiplication
   1. PRAM
   2. Mesh
5. Parallel Prefix (A, chapt 4)
   1. Review
   2. Problems that can be solved with prefix
      1. Maximum Sum Subsequence
      2. Array Packing
      3. Interval Broadcasting
      4. Computing Cliques of Circular Arcs
      5. Simple Point Domination
   3. Homework on Prefix Problems and their Applications
6. Pointer Jumping
   1. Parallel Prefix
   2. List Ranking
   3. Euler Tour (?)
      1. Depth-First Traversal and Applications
      2. Breadth-First Traversal and Applications
   4. Connected Components (?)
7. Divide-and-Conquer
   1. Define and give generic solution strategy
   2. Fundamental Problems :
      1. Mergesort
         1. Sequential Explanation and Analysis
         2. Mergesort on Linear Array
         3. Reminder of Bitonic Sort (i.e., parallel merge)
            1. Bitonic Sort on Hypercube
            2. Bitonic Sort on Mesh
      2. Quicksort
         1. Generic explanation and solution
         2. Array Implementation
            1. Worst-Case Analysis
            2. Expected-Case Analysis
         3. Medium-/Coarse-Grained Parallel Implementation
      3. Advanced Problems (sequential and parallel implementations):
         1. Image Processing
            1. Component Labeling
            2. Internal Distances
            3. Convex Hull
         2. Computational Geometry
            1. Convex Hull
            2. All-Nearest Neighbors
            3. Line Segment Intersection
      4. Homework problems on D&C
   3. The Greedy Method (B&P, chapt 12)
      1. Define and give generic solution strategy
      2. Examples (discuss sequential and parallel implementations):
         1. Optimal Sequential Storage Order
         2. Knapsack Problem
         3. Minimum Spanning Tree
            1. Kruskal's Algorithm
            2. Prim's Algorithm
         4. Shortest Path Algorithms
      3. Homework problems on Greedy Algorithms
   4. Mesh-of-Trees
      1. Enumeration Sort (n items on MOT of size n2)
      2. Convex Hull (Image)
      3. Convex Hull for planar point data (n items on MOT of size n2)
   5. Bus-Based Models
      1. Meshes with Buses
         1. Sample problems
      2. Reconfigurable Meshes
         1. Sample problems
      3. Homework problems for bus-based models
   6. Dynamic Programming (??)
      1. Sequential
      2. Mesh

   
   

   ---

   Russ Miller (miller@cs.buffalo.edu)
   
   

   ---

   Copyright © 1997-1998 by Russ Miller.

   All rights reserved. No part of this document may be used in any form by any electronic or mechanical means without permission in writing by the author.