A Parallel Algorithm for Merging Heaps on MasPar Machine


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 2, No. 4, pp. 554-560, Jul. 1995
10.3745/KIPSTE.1995.2.4.554,   PDF Download:

Abstract

In this paper, we suggest a parallel algorithm to merge priority queues organized in two heaps, kheap and nheap of sizes k and n, correspondingly. Employing max(2i-1, (m 1)/4 )''s processors, this algorithm requires O(log(n/k)*log(n)) on an EREW-PRAM, where i is the height of the heap and m is the summation of sizes n and k. Also, when we run it on the MasPar machine, this method achieves a 33.934-fold speedup with 64 processors to merge 8 million data items which consist of two heaps of different sizes. So, our parallel algorithm''s EPU is close to = 1, which is considered as an optimal speedup ratio.


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]
M. Y. Sik, "A Parallel Algorithm for Merging Heaps on MasPar Machine," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 2, no. 4, pp. 554-560, 1995. DOI: 10.3745/KIPSTE.1995.2.4.554.

[ACM Style]
Min Yong Sik. 1995. A Parallel Algorithm for Merging Heaps on MasPar Machine. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 2, 4, (1995), 554-560. DOI: 10.3745/KIPSTE.1995.2.4.554.