AN OPTIMAL SORTING ALGORITHM ON RECONFIGURABLE MESH

This paper shows nontrivial ways to use the Reconfigurable Mesh to sol ve several basic arithmetic problems in constant time. These solutions are obtained by novel ways to represent numbers and by exploiting the reconfigurability of the architecture. In particular, a constant time algorithm to add nk-bit numbers using an n x nk bit model of Reconfig urable Mesh is shown. Using these techniques, an optimal sorting algor ithm on the Reconfigurable Mesh is derived. The algorithm sorts n numb ers in constant time using n x n processors. Our algorithm uses optima l size-of the mesh to sort n numbers in constant time and satisfies th e AT(2) lower bound of Omega(n(2)) for sorting n numbers in a variatio n of the word model of VLSI. The sorting algorithm runs on all known v ariations of the Reconfigurable Mesh model. (C) 1995 Academic Press, I nc