Bitonic sort on a chained-cubic tree interconnection network

• We map bitonic sort to a chained-cubic tree interconnection network, calling the result BSCCT.
• BSCCT’s computation time is O((n/p)×log(np))O((n/p)×log(np)), for input size nn and pp processors.
• BSCCT costs O(plog2p)O(plog2p) communication steps, for input size nn and pp processors.
• BSCCT’s relative speedup is 12-fold with p=1024p=1024 processors and n=32n=32M keys.
• BSCCT’s communication cost is less than the tree and metacube networks costs.

Bitonic sort is one of the fastest oblivious parallel sorting algorithms known so far. Due to its high modularity, bitonic sort can be mapped to different interconnection networks. In this paper, the bitonic sort algorithm is mapped to the chained-cubic tree (CCT) interconnection network. It is shown that the computation time of the bitonic sort on a CCT (BSCCT) algorithm is O((n/p)×log(np))O((n/p)×log(np)) and that the communication cost is O(plog2p)O(plog2p), assuming that nn keys are evenly distributed among pp processors that comprise a given CCT network. Simulation is implemented and used to assess the performance of the BSCCT algorithm in terms of computation time, communication cost, message delay, and key comparisons. Simulation results showed that the BSCCT algorithm achieves a speedup that is almost 12-fold relative to a bitonic sort on a single processor, when 1024 processors were used to sort 32M keys.