Parallel Algorithms and Architectures
Razvan Andonie, Professor
Daniel Grosu, Assist. Lecturer
Overview
| Contents | Labs | Prerequisites | Bibliography
| Links
Overview:
The course will start by studying various models of parallel computation. It will then cover algorithms for merging, sorting, searching and FFT. Assignments will be based on programming the algorithms on PVM.
Contents:
Introduction:
The need for
parallel computers
Models of
computation
Analyzing parallel
algorithms
Expressing parallel
algorithms
The Computational
Power of The PRAM model:
Comparison between
RAM and PRAM models
Graph coloring on
PRAM
Parallel computation
thesis
NC and P-complete
classes
Selection:
Sequential
algorithms
Desirable properties
for parallel algorithms
An EREW algorithm for
parallel selection
Merging:
A network for
merging
Merging on the CREW
model
Merging on the EREW
model
A better algorithm
for the EREW model
Parallel
Algorithms for Neural Networks
Sorting:
A network for
sorting
Sorting on a linear
array
Sorting on the CRCW
model
Sorting on the CREW
model
Sorting on the EREW
model
Searching:
Searching a sorted
sequence (EREW, CREW, CRCW)
Searching a random
sequence (EREW, CREW, CRCW, Tree, Mesh)
Fourier
Transforms:
DFT and convolution
theorem
Algorithms for FFT
Inverse DFT
Computing the DFT in
parallel
Decision and
Optimization
Labs (homeworks):
Batcher's network
Graphical
representation for Batcher network
CREW merge
Multiple broadcast
EREW merge
A network for
sorting
Odd-Even transposition
Merge split
CRCW sort
Prerequisites:
Programming
Computer
Architecture
Operating Systems
Bibliography:
R. Greenlaw, H.J.
Hoover, W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory,
V. Kumar, A. Grama,
A. Gupta, G. Karypis, Introduction to Parallel Computing, The
Benjamin/Cummings Publishing Company, Redwood City, California, 1994.
T. Cormen, C.
Leiserson, R. Rivest, Introduction to Algorithms, The MIT Press,
S. G. Akl, The
Design and Analysis of Parallel Algorithms, Prentice Hall, 1989.
M. J. Quinn, Parallel
Computing, McGraw Hill, 1994.
F.T. Leighton, Introduction
to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan
Kaufmann Publishers,
D.P. Bovet, P.
Crescenzi, Introduction to The Theory of Complexity, Prentice Hall,
N.Y., 1994.
Al Geist, et al., PVM:
Parallel Virtual Machine - a User's Guide and Tutorial for Networked Parallel
Computing, The MIT Press,
B. Wilkinson, M.
Allen. Parallel Programming –
Techniques and Applications Using Networked Workstations and Parallel Computers,
Prentice Hall, 1999.
S. G. Akl, Parallel Computation – Models and Methods,
Prentice Hall, 1997.
P. S. Pacheco, Parallel Programming with MPI, Morgan
Kaufman,