Sorting on Reconfigurable Meshes: An Irregular Decomposition Approach

Most algorithms for reconfigurable meshes (R-meshes) are based on the divide-and-conquer(DAC) strategy. Although the strategy per se does not require the subproblemsto be equal in size, existing DAC algorithms for R-meshes do divide the problemapproximately evenly. This paper demonstrates that dividing a problem evenly is notnecessarily a good way to decompose a problem. There are occasions on which anirregular decomposition scheme may be preferable. We take this approach and obtain anew sorting algorithm. Our sorting algorithm has several strengths: it is simple, scalable,and as broadcast-efficient as the best known result