An Efficient Parallel Sorting Algorithm on OTIS Mesh of Trees
Keny T. Lucas, Prasanta K. Jana · 2009
OTIS (Optical Transpose Interconnection System) is popular model of optoelectronic parallel computers. This is a hybrid interconnection network using electronic and optical communication channels. In the recent years, many parallel algorithms for various numeric and non-numeric computations have been developed on these networks. In this paper, we propose a parallel algorithm for sorting N (=n2) data elements on an OTIS model of parallel computers, called OTIS-mesh of trees. Our algorithm is based on sparse enumeration sort (Horowitz et al., 2002) and shown to run in 4.5 log N electronic moves + 5 OTIS moves.