Routing and Sorting on OTIS-Hyper Hexa-Cell (International Journal of Engineering and Computer Science, 2014)
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 px, 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 (2dh+3). The time complexity of algorithm proposed for parallel sparse enumeration sort is 4(dh+1) electronic moves + 4 OTIS moves for case I and 4(dh+1) electronic moves + 3 OTIS moves for case II.