Routing and Sorting on OTIS-Hyper Hexa-Cell

Abstract

In the recent years, the Optical Transpose Interconnection System (OTIS) has attracted researchers for solving computational and communicational intensive problems. OTIS is a hybrid interconnection network that exploits the advantages of electronic link as well as optical links for connecting processors in the network. Many variants of OTIS model and several parallel algorithms for different problems have been proposed on those models. In this paper, we have proposed shortest path routing and sparse enumeration sort on OTIS hyper hexa-cell. In the sparse enumeration sort, the number of keys to be sorted is p^x, for some constant x≤½ and for our proposed algorithm x=2. The proposed shortest path routing on OTIS-HHC is optimal as the number of steps required is equal to its diameter (2d_h+3). The time complexity of algorithm proposed for parallel sparse enumeration sort is 4(d_h+1) electronic moves + 4 OTIS moves for case I and 4(d_h+1) electronic moves + 3 OTIS moves for case II.