marina@ai (Marina Haloulos) (09/13/89)
FLASH ANNOUNCEMENT
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB119, at 3:00 p.m., Friday 15 September 1989
Professor Kazuo Iwama
Kyoto Sangyo University
An 0(log n) Parallel Connectivity Algorithm on the Mesh of Buses
An 0(log n) parallel randomized algorithm for obtaining connected
components of an undirected graph is presented. The model is not the common
parallel random access machine (PRAM) but the mesh of buses (MB) which
consists of n sup 2 RAMs on the two dimensional mesh of communication
buses. Unlike PRAMs, MBs are considered to be current realizable in a
similar degree as the mesh computer. Their computation power, however,
appears to be much less than PRAMs; an obvious lower bound of sqrt N steps
exists to simulate PRAM's one step (`N` processors). Nevertheless, our
achievement of the 0(log n) depth for this fundamental graph problem, which
is believed to be the best possible achieved only using PRAMs, demonstrates
that the unrealistically idealized communication scheme of PRAMs is
sometimes needlessly excessive for natural problems.