''On the Power of Segmenting and Fusing Buses''
Jerry L. Trahan
Ramachandran Vaidyanathan
Ratnapuri K. Thiruchelvan
Journal of Parallel and Distributed Computing, vol. 34, no. 1, pp. 82-94, April 1996
Abstract:
Reconfigurable bus-based models of parallel computation have
been shown to be extremely powerful, capable of
solving several problems in constant time that require non-constant time
on conventional models such as the PRAM. The primary source of the
power of reconfigurable bus-based models is their ability to
dynamically alter the connections between processors by
manipulating the communication medium.
This can be viewed as the models' ability to
(i) segment a bus into two or more bus segments, and
(ii) fuse two or more buses or bus segments together.
In this paper we investigate the contribution of the abilities of
a reconfigurable bus-based model to segment and fuse buses.
We show that the ability to fuse buses is the more crucial of the two.
The ability to segment buses enhances the power of the model under
certain circumstances. We also study the role of concurrent reading
and writing in the context of reconfigurable bus-based models.
These results establish a hierarchy of powers of the PRAM and
reconfigurable bus-based models.