Efficient parallel computation on a processor array with pipelined TDM optical buses

Constructing parallel computing systems using multiple optical buses is a new approach for alleviating the communication bottleneck problem in parallel computing. Various processor arrays connected by reconfigurable optical buses have been proposed. Bus reconfigurability has given rise to new parallel computing models. In this paper, we introduce a new parallel architecture called Array Connected by Pipelined Optical Buses with conditional delays (ACPOB). An ACPOB is simpler than previously proposed processor arrays with optical buses; its optical buses are not reconfigurable. We show that computing prefix sums pf n binary values on an n ½ x n ½ ACPOB can be carried out in 0 (1) computation steps and O (1) bus cycles. We then present efficient algorithms for a set of fundamental problems which include data compaction, data partition, permutation routing, searching, sorting and selection. Our results indicate that an ACPOB is a powerful and realistic parallel computation model.