An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes

[摘要] An algorithm is presented to merge two subfiles of size n/2 each, stored in the left and the right halves of a linearly-connected processor array, in 3n/2 route steps and log n compare-exchange steps. This algorithm is extended to merge two horizontally adjacent subfiles of size mXn/2 each, stored in an mXn mesh-connected processor array in row-major order, in m+2n route steps and log mn compare-exchange steps. These algorithms are faster than their counterparts proposed so far. Next, an algorithm is presented to merge two vertically aligned subfiles, stored in a mesh-connected processor array in row-major order. Finally, a sorting scheme is proposed that requires lln route steps and 2 log n compare-exchange steps to sort n elements stored in an nXn mesh-connected processor array. The previous best sorting algorithm requires 14 n route steps ( for practical values of n, 4 < n 512 ).

[发布机构] Rice University