완전 이진 트리와 PARALLEL 정렬 알고리즘 = Complete Bibary Tree And Parallel Sort Algorithm

국문 초록 (Abstract)

병렬컴퓨터로 n개의 합을 구하는데는 트리가 사용되고 있다. 트리는 동일한 레벨의 병렬처리가 가능하므로 트리의 높이가 병렬처리 시간이며, 트리의 높이가 가장 작은 트리는 완전이진 트리이다.
본 논문은 완전이진트리와 관련된 병렬합 알고리즘에 관해서 살펴보고 완전이진트리를 이용하여 Preparata, Nath, Hsias, Snyder[5,8,22]등이 제안하고 구현한 Enumeration 알고리즘의 프로세서 수를 줄인 알고리즘을 제안하는데 목적이 있다. 제시된 알고리즘은 충돌을 허용하지 않는 SIMD EREW-PRAM 모델 병렬컴퓨터에 적용 할 수 있으며 제시된 알고리즘을 분석한 결과 최악의 경우는 O(n/p*log n)이며, 비용은 O(nlog n)이다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 완전 이진 트리
• 3. PARALLEL 정렬 알고리즘
• 4. PARALLEL 정렬 알고리즘 분석
• 5. 결론
• 참고문헌