REDUCING COMMUNICATION COSTS FOR SORTING ON MESH-CONNECTED AND LINEARLY CONNECTED PARALLEL COMPUTERS

Most sorting algorithms for linearly connected and mesh-connected parallel computers have been developed assuming that the number of processors equals the number of elements to be sorted. This assumption has simplified analysis of the problem, however, it causes unnecessary communication costs because elements must be permuted across large numbers of processors. It also underutilizes processors because comparison operations involve two data elements for each processor. By modifying parallel sorting algorithms to use fewer processors, we are able to improve processor utilization and decrease communication costs. This leads to constant factor improvements in the best parallel sorting bounds for both mesh-connected and linearly connected SIMD parallel computers. (Previous bounds are within a constant factor of optimal.). © 1990.