A Parallel Algorithm for Merging Heaps on MasPar Machine
Min Yong Sik · The Transactions of the Korea Information Processing Society · 1995
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(2, (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.eedup ratio.