Two Versions of Bitonic Sorting Algorithms on the Connection Machine

摘要

Communication is a major cost item for many algorithms on today's parallel computers. Therefore, reducing the communication requirements in an algorithm often results in an improvement to the original algorithm. In this paper, we show two versions of bitonic sorting algorithms on the Connection Machine obtained this way. The first is a version of bitonic sort modified from a standard implementation for hypercube machines. The modified version requires one less routing step in each comparison-exchange operation, and thus saves 30 or more of the Connection Machine time. The second is a modification of Nassimi and Sahni's mesh bitonic sorting algorithm. By taking advantage of the hypercube links on the Connection Machine, this algorithm reduces the time complexity and is faster. This improvement can also be applied to mesh architectures with other kinds of fast buses.