An optimized bitonic sorting strategy with midpoint-based dynamic communication

Tipraporn Thanakulwarapas

doi:10.1016/j.jpdc.2015.05.008

2015-10-01

PRE

Tipraporn Thanakulwarapas *

Jeeraporn Werapun

DOI：10.1016/j.jpdc.2015.05.008

原文链接

原文求助

摘要

En 中文

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 (Pi, Pi) 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,..., or s = log(2) P iterations, which are improved over those (<= s(s+ 1)/2 iterations) of the dynamic DCES 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 LBM about 51%-54% (for N = 10 to 100 million elements on an 8-multicore computer). (C) 2015 Published by Elsevier Inc.

Keyword:

Optimized Bitonic sorting

Midpoint-based dynamic communication

Midpoint-weight list-ranking