RANDOMIZED ROUTING, SELECTION, AND SORTING ON THE OTIS-MESH

The Optical Transpose Interconnection System (OTIS) is a recently prop osed model of computing that exploits the special features of both ele ctronic and optical technologies. in this paper we present efficient a lgorithms for packet routing, sorting, and selection on the OTIS-Mesh. The diameter of an N-2-processor OTIS-Mesh is 4 root N - 3. We presen t an algorithm for routing any partial permutation in 4 root N + o(roo t N) time. Our selection algorithm runs in time 6 root N + o(root N) a nd our sorting algorithm runs in 8 root N + o(root N) time. All these algorithms are randomized and the stated time bounds hold with high pr obability. Also, the queue size needed for these algorithms is O(1) wi th high probability.