cfry@watdcsu.waterloo.edu (C.Fry - Inst. Computer Research) (01/06/88)
Lower Bounds for Synchronous Models
of Parallel Computation
by
Dr. Prabhakar Ragde
of
Department of Computer Science
University of Toronto
Abstract
The parallel random access machine (PRAM), in which many proces-
sors co-operate to solve problems by communicating via shared
memory, is a natural and important model for parallel algorithm
design. Variations of this model differ in the extent to which
simultaneous access is allowed to a shared memory cell; in the
case where full concurrent read/write access is permitted, a
method of write-conflict resolution must also be specified.
Differences in power between these models will be shown by demon-
strating problems that are easy for some models and hard for oth-
ers. Several lower-bound techniques will be sketched and their
applicability discussed.
DATE: Wednesday January 13, 1988
TIME: 3:30 p.m.
PLACE: MC 5158
Everyone is welcome. Refreshments served.