S. Rajasekaran et S. Sahni, RANDOMIZED ROUTING, SELECTION, AND SORTING ON THE OTIS-MESH, IEEE transactions on parallel and distributed systems, 9(9), 1998, pp. 833-840
Citations number
13
Categorie Soggetti
Computer Science Theory & Methods","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
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.