**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.