mwang (03/01/83)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR
- Monday, March 7, 1983.
Mr. A. Wigderson of Princeton University will speak on
``Trade-offs Between Depth and Width in Parallel Computa-
tion''.
TIME: 3.30 PM
ROOM: MC 5158
ABSTRACT
A new technique for proving lower bounds for parallel compu-
tation is introduced. This technique enables us to obtain,
for the first time, tight lower bounds for models of paral-
lel computation that allow several processors to have simul-
taneous access to the same memory location. Specifically,
we use a concurrent-read concurrent-write model of parallel
computation. It has p processors, each has access to a
common memory of size m (also called communication width or
width in short). The input to the problem is located in an
additional read-only portion of the common memory.
For a wide variety of problems (including parity, majority
and summation) we show that the time complexity T (depth)
and the communication width
m are related by the trade-off curve
m T sub 2 = OMEGA (n) , (where n is the size of the in-
put), regardless of the number of processors. Moreover, for
every point on this curve with
m = O ( n / log sup 2 n ) we give a matching upper
bound with the optimal number of processors.
March 1, 1983