A New Fast Parallel Computation Model for Setting Benes Rearrangeable Interconnection Network

Issam A. HAMID, Norio SHIRATORI, Shoichi NOGUCHI

Summary :

We have pressented here, for the Control Unit (CU) of Benes Interconnection Network (IN), a new fast parallel computational model named as; Cyclic Cube Engine (CCE), which depends on the Cyclic Cube topology, where the total number of processing elements is φ such that φN^(11/h), h is an arbitrary integer, such that 2hlog N. N is number of the data items consisting the permutation. We have presented on this model parallel algorithm for parallel settings of Benes IN in order to realize arbitrary permutation with a setting time of O(h log₂ N); (assuming N is base 2) using φN^(11/h) processors (i.e., φN). This bound could be achieved by accelerating the parallel setting algorithm by function call of another very fast algorithm named as the accelerator. We have also, proven in the appendix of this paper, that our construction is within the lower bound of setting Benes IN for arbitrary permutation for general nonshared model when φN. Using these algorithms we have constracted a fast parallel setting algorithm to set the switches of Benes IN for arbitrary permutation in parallel time of O(h log₂ N) where is hlog₂ N. The parallel setting algorithm has been constructed depending on the CCE as the main computational structure suitable for setting Benes IN in parallel.

• Publication: IEICE TRANSACTIONS on transactions Vol.E72-E No.4 pp.393-405
• Publication Date: 1989/04/25
• Type of Manuscript: PAPER
• Category: Computer Hardware and Design

Authors

Issam A. HAMID
Norio SHIRATORI
Shoichi NOGUCHI

Keyword