BPC Permutations on the OTIS-Hypercube Optoelectronic Computer.
Sartaj K. Sahni, Chih-Fang Wang · 1998
We show that the diameter of an N 2 processor OTIS-Hypercube computer ( N = 2 d ) is 2d + 1. OTIS-Hypercube algorithms for some commonly performed permutations -- transpose, bit reversal, vector reversal, perfect shuffle, unshuffle, shuffled row-major, and bit shuffle -- are developed. We also propose an algorithm for general BPC permutations. 1 Introduction Electronic interconnects are superior to optical interconnects when the interconnect distance is up to a few millimeters [1, 3]. However, for longer interconnects, optics ( and in particular, free space optics ) provides power, speed, and bandwidth advantages over electronics. With this in mind, Marsden et al.[5], Hendrick et al.[2], and Zane et al.[9] have proposed a hybrid computer architecture in which the processors are divided into groups; intra-group connects are electronic, and inter-group interconnects are optical. Krishnamoorthy et al.[4] have demonstrated that bandwidth and power consumption are minimized when the nu...