Randomized routing, selection, and sorting on the OTIS-mesh
Sanguthevar Rajasekaran, Sartaj K. Sahni · IEEE Transactions on Parallel and Distributed Systems · 1998
The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. In this paper we present efficient algorithms for packet routing, sorting, and selection on the OTIS-Mesh. The diameter of an N/sup 2/-processor OTIS-Mesh is 4/spl radic/N-3. We present an algorithm for routing any partial permutation in 4/spl radic/N+o(/spl radic/N) time. Our selection algorithm runs in time 6/spl radic/N+o(/spl radic/N) and our sorting algorithm runs in 8/spl radic/N+o(/spl radic/N) time. All these algorithms are randomized and the stated time bounds hold with high probability. Also, the queue size needed for these algorithms is O(1) with high probability.