Relaxed min-max 힙에 대한 병렬 병합 알고리즘

• 영문명: Parallel Merging Algorithm for Relaxed Min-Max Heaps
• 발행기관: 호서대학교 공업기술연구소
• 저자명: 민용식
• 간행물 정보: 『공업기술연구 논문집』제16권 제1호, 339~353쪽, 전체 15쪽
• 주제분류: 공학 > 공학일반
• 파일형태: PDF
• 발행일자: 1997.12.30

국문 초록

본 논문은 relaxed min-max heap 을 병합시키기 위하여 이용된 새로운 자료 구조인 개선된relaxed min-max-pair 힙으로서 ， 두개의 relaxed min-max 힙 즉 ，크기가 n 인 relaxed min-max nheap 과 크기가 노인 relaxed min-max kheap으로 구성된 우선 순위 큐를 병합시키기 위한 순차적 알고리즘을 제시하고자한다 . 본 논문에서 제시된 방법은 [8 ] 에 제시된 방법에서 relaxed min-max 힙 을 병 합 시키기 위해서 이 용 된 bloss 이 ned tree 와 lazying 방법을 제거하여 도병합이 되 는 새로운 기법을 제시하였다 . 결과적으로 본 논문에서 제시된 방법은 max(2i_1, 「 (m + l)/4 l ) 개의 프 로 세 서 를 이용한 경우 ， 시간 복잡도가 O(log(log(n/k)) *log(k ) ) 임을 볼 수가 있다 . 그리고 서로 크기가 다른 두개의 relaxed min-max heap으로 구성이 된 8 백만개의 데 이 터 를 병 합 시키기 위해서 MasPar 머쉰에서 64 개의 프로세서를 이용하여 실행시킨 결과가 속도 (Speedup ) 가 35.205 를 얻음을 보았다 .

목차

1 . introduction

n . Merging Relaxed Heaps m Parallel

HI. Experimental Results

IV. Conclusion