Simulation of Priority-Concurrent Write Buses by Separable Buses with Fewer Switches

概要

論文の詳細を見る
Processor arrays with priority-concurrent write buses have been shown to be equal in computational power to processor arrays with separable buses. The separable bus can be dynamically segmented into smaller bus portions of any length by turning off some switches in the bus. The concurrent write bus permits two or more processors to send a datum simultaneously. In this paper, we show that switches as asymptotically many as processors involved are required for the separable bus to ensure the equivalency in power. This indicates that propagation delays caused by the switches may increase gradually as the size of a processor array is enlarged. We, then, introduce a concurrent write rule, which permits two or more processors each to send the value 1 to an arbitrary bit of a bus simultaneously, into the separable bus in order to decrease the complexity of the bus. Our results show that a processor array with such separable buses can simulate a priority-concurrent write operation to the bus in constant time even though the number of switches involved is reduced to O(1/log^α N), where N is the number of processors and α is a constant.
神戸大学の論文
2006-07-31