2nd module

Prof. ALAN A. BERTOSSI

A.A. 1998/99

The main topic of the course is the introduction to the design and analysis
of "parallel" algorithms, with particular emphasis on parallel synchronous
multiprocessors, concurrent asyncronous multicomputers, and distributed
computer networks.

FOUNDATIONS. Classifications of Flynn and Schwartz. Bounded-degree
interconnection networks: tree, mesh, shuffle, hypercube, butterfly,
cube-connected-cycles. Speedup and processor utilization. Parallel
Computation Thesis. The NC and LOG-SPACE-COMPLETE classes.

THE PARALLEL RANDOM ACCESS MACHINE (PRAM). Shared memory. EREW, CREW, and
CRCW models. Pointer jumping and parallel prefix computations. Parallel
algorithms for sorting, scheduling, matrix multiplication, and all-pairs
shortest paths.

SYNCHRONOUS MULTIPROCESSORS WITH BOUNDED-DEGREE INTERCONNECTION. Batcher's
and Stone's networks for bitonic sorting. Parallel sorting algorithms on
meshes, shuffles, and hypercubes. The Discrete Fourier Transform. The
parallel Fast Fourier Transform algorithm on a butterfly.

VERY LARGE SCALE INTEGRATION (VLSI) CIRCUITS. The grid model. When- and
where-determinate circuits. Complexity measures and lower bounds. Layouts
for bounded-degree networks: tree, mesh, butterfly, shuffle, and mesh of
trees. Preparata-Vuillemin optimal circuit for matrix multiplication.

ASYNCHRONOUS MULTICOMPUTERS. Shared resources. Synchronization primitives
and deadlock. Scheduling and load balancing. Concurrent algorithms for
sorting, matrix multiplication, and all-pairs shortest paths.  Concurrent
branch-&-bound for the Travelling Salesperson Problem.

COMPUTER NETWORKS. Distributed computations and message complexity. Network
topologies: bus, ring, star. Distributed algorithms for mutual exclusion,
leader election, and minimum spanning tree.