Maspar 머쉰상의 병합 알고리즘

• 영문명: Parallel Merging Algorithm on MasPar Machine
• 발행기관: 호서대학교 중앙도서관
• 저자명: 민용식(Yong sik Min)
• 간행물 정보: 『호서대학교 논문집』제2권, 107~121쪽, 전체 15쪽
• 주제분류: 사회과학 > 무역학
• 파일형태: PDF
• 발행일자: 1994.12.30

영문 초록

In th is 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⁻¹, (m+l)/4) s processors, this algorithm requires O(log(n/k)*log(n)). 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.

목차

ABSTRACT

Ⅰ. Introduction

Ⅱ. Merging heaps in parallel

Ⅲ. Experimental Results

Ⅳ. Conclusion

References