Communication-space efficient parallel Bitonic sorting on Symmetric Multiprocessors
Tipraporn Thanakulwarapas, Jeeraporn Werapun · 2008
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%.