Enumeration Sort on OTIS k-Ary n-Cube Architecture (International Journal of Engineering and Computer Science, 2014)
Many researchers have been motivated to propose parallel algorithm on Optical Transpose Interconnection System (OTIS) because of its hybrid nature. OTIS exploits both the electronic links as well as free space optical links for connecting processing nodes of interconnection network. In this paper, we have proposed a parallel algorithm for sparse enumeration sort on OTIS k-ary n-cube parallel computer with on a network size of k2n.. In this sorting, the number of keys to be sorted is pα, for some constant α≤½ and we have assumed α=½ for our proposed algorithm. The algorithm has two variants based on data population techniques. The time complexity of the algorithm has been observed to be 4n(k-1) electronic moves + 3 OTIS moves for the first case. In the second case also it requires the same number of electronic moves but needs only two OTIS moves.