An optimized bitonic sorting strategy with midpoint-based dynamic communication

摘要

This paper proposes an optimized Bitonic sorting {OBS) strategy with midpoint-based dynamic communication. Our OBS strategy uses the midpoint-weight list ranking to improve complexity and reduce time of sorting on parallel and distributed systems. Applying a better key in the PE-list ranking can find the right place of (P., P,) and improve communication time significantly (i.e., fewer iterations, better synchronization in each iteration, faster convergence to the result), while most of coarse-grain parallel sorting (P ＜ N) approaches improve only a large amount of data exchange (N/P) in each of static (s(s +1)/2) iterations. Theoretically, the OBS method can reduce fixed (s(s+1)/2) iterations to 1,2,3,..., ors = log_2 P iterations, which are improved over those (≤s(s +1)/2 iterations) of the dynamicDCES method. In performance evaluation, sorting was accomplished on multicore machines. Experimental results showed that our optimized OBS outperforms those of the dynamic DCES about 35%-40% and those of the static IBM about 51%-54% (forN = 10 to 100 million elements on an S-multicore computer).