00517757

open access

Version of Record

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

Review of the Faculty of Maritime Sciences, Kobe University

3

63-69

神戸大学海事科学部

2006-07-31

2007-03-13

本文ファイルは、国立情報学研究所CiNiiより提供されたものです。

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.

紀要論文