On the Power of Segmenting and Fusing Buses

✍ Scribed by Jerry L. Trahan; Ramachandran Vaidyanathan; Ratnapuri K. Thiruchelvan

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 328 KB
• Volume: 34
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0047

✦ Synopsis

Reconfigurable bus-based models of parallel computation have been shown to be extremely powerful, capable of solving several problems in constant time that require nonconstant 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 roles 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.