Title :
Why shared memory matters to VLSI design: The BSR is as powerful as reconfiguration
Author :
Bruda, Stefan D. ; Zhang, Yuanqiao
Author_Institution :
Dept. of Comput. Sci., Bishop´´s Univ., Sherbrooke, QC
Abstract :
We investigate the relative computational power of parallel models with directed reconfigurable buses and the most powerful shared memory model, the broadcast with selective reduction (BSR). We show that these two models have the same computational power in a strong sense. We also show that the Collision write conflict resolution rule is universal on models with directed reconfigurable buses (meaning that complex conflict resolution rules such as priority or even combining can be simulated by collision with constant-time overhead). Consequences of these finding, including some real time consideration, are discussed.
Keywords :
VLSI; integrated circuit design; reconfigurable architectures; shared memory systems; VLSI design; broadcast with selective reduction; constant-time overhead; shared memory systems; Algorithm design and analysis; Broadcasting; Computational modeling; Computer networks; Computer science; Concurrent computing; Councils; Parallel machines; Polynomials; Very large scale integration; broadcast with selective reduction; concurrent-read concurrent-write conflict resolution rules; parallel computation; real time; reconfigurable buses; reconfigurable multiple bus machine; reconfigurable network;
Conference_Titel :
Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on
Conference_Location :
Miami, FL
Print_ISBN :
978-1-4244-1693-6
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2008.4536122