Designing a Bitonic Sorting Algorithm for Shared - Memory Parallel Computers and an Efficient Implementation of its Communication


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 4, No. 11, pp. 2690-2700, Nov. 1997
10.3745/KIPSTE.1997.4.11.2690,   PDF Download:

Abstract

This paper presents parallel sorting algorithms, SHARED-MEMORY-BS and REDUCED-BS, which are implemented on shared-memory parallel computers. These algorithm sort N keys in O(log2N) time. REDUCED-BS uses a parity strategy which gives an idea for the efficient usage of the local memory associated with each processor. By taking advantage of the local memory associated with each processor, the communication of REDUCED-BS is decreased by approximately half that of SHARED-MEMORY-BS. On this basis of alleviating the communication, the algorithm REDUCED-BS results in a significant improvement of performance.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
L. J. Dong, K. K. Dong, P. Y. B, "Designing a Bitonic Sorting Algorithm for Shared - Memory Parallel Computers and an Efficient Implementation of its Communication," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 4, no. 11, pp. 2690-2700, 1997. DOI: 10.3745/KIPSTE.1997.4.11.2690.

[ACM Style]
Lee Jae Dong, Kwon Kyung Dong, and Park Young B. 1997. Designing a Bitonic Sorting Algorithm for Shared - Memory Parallel Computers and an Efficient Implementation of its Communication. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 4, 11, (1997), 2690-2700. DOI: 10.3745/KIPSTE.1997.4.11.2690.