Communication-Space Efficient Parallel Bitonic Sorting on Symmetric Multiprocessors

T. Thanakulwarapas and J. Werapun (Thailand)


Communication-space efficient parallel sorting, Parallel Bitonic sorting, Parallel Odd-Even sorting, SMP (Symmetric Multiprocessor).


This paper presents a new efficient data-exchange process in parallel sorting, which improves both communication time and memory space. In this communication-space efficient strategy, we proposed two new parallel sorting algorithms: 1) CSEBS (Communication-Space Efficient Bitonic Sort) algorithm and 2) CSEOE (Communication Space Efficient Odd-Even MergeSort) algorithm. In addition, to evaluate the performance, we have implemented the CSEBS and the CSEOE algorithms on the SGI Origin2000. Investigated experimental results have been compared to those of the best of existing algorithm (CEBS: Communication Efficient Bitonic Sort). In the experiments, the proposed CSEBS algorithm yielded the improved results over those of the best of existing algorithm (CEBS) at least 11% on the system of size P = 4 and at least 31% on the system of size P = 8. Moreover our approach can save memory space up to 50%.

Important Links:

Go Back