''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


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.