하이퍼큐브 구조에서의 대용량 데이터 정렬을 위한 병렬 Bitonic 정렬 알고리즘 연구

Abstract

데이터 정렬은 다양한 데이터 조작 응용 프로그램의 핵심 요소로 널리 활용되어, 효율 적인 정렬 알고리즘 개발을 위한 연구가 다각도에서 수행되고 있다. Bitonic 정렬 알고리즘은 단계별로 전체 데이터가 데이터 쌍을 형성하고 상호 비교 정렬을 반복하는 특성이 있어, 알고리즘의 병렬화가 용이하고, 대상 병렬 시스템의 상호 연결망 특성에 따라 효과적인 데이터 정렬을 실행할 수 있다. 본 연구에서는 하이퍼규브구조의 상호 연결망이 Bitonic 정렬의 단계별 비교 패턴과 일치하는 점에 착안, 먼저 하이퍼규브 시스템에 Bitonic 정렬 알고리즘을 적용하고, 알고리즘 수행에 소요되는 시간을 분석, 계산하였다. 나아가서 프로세서 개수가 한정된 시스템에서 다량의 데이터를 정렬할 경우 네트워크 내부의 데이터 충돌을 피하고 전체 프로세서 이용률을 최대화시키는 두가지 병렬 Bitonic 정렬 알고리즘(High-Order Interleaving(HOI) 정렬 기법과 Low-Order Interleaving(LOI)정렬기법)을 제안하고, 이들 알고리즘 수행에 소요되는 시간을 구하였다. HOI 방식은 알고리즘이 비교적 단순할 뿐 아니라, 알고리즘 수행에 수요되는 시간도 경제적인 것으로 나타나 성능 면에서 우수한 방식으로 판명되었으나, 응용 분야에서 요구하는 정렬 후 데이터 배열 상태에 따라 정렬 기법이 선택되어야 한다.

Data sorting is well known as an elementary process of the various data manipulation problems. Bitonic sorting algorithm is an efficient method to be parallelled due its systematic repetition characteristic of the partial comparison and rearrangement. The comparison pattern of Bitonic sorting is completely match with the Hypercube interconnection. This provides the motivation of this research. Mapping technique of the Bitonic sorting algorithm on a Hypercube system and its time complexity are discussed and calculated. A comparative study is conducted to show the effectiveness of the Hypercube architecture to support the Bitonic sorting algorithm. Two parallel Bitonic algorithms are proposed and analyzed to sort a large data under the limited number of Hypercube connected processors. These are High-Order Interleaving(HOI) Bitonic sorting algorithm and Low-Order interleaving(LOI)Bitonic sorting algorithm. Both algorithms are designed not only to avoid the data collision on the Hypercube network but also to maximize the processor utilization. It is shown that the HOI technique is simple to apply and takes less time to execute the sorting. The selection of algorithm, however, can be determined according to the requirement of the application problems.

Data sorting is well known as an elementary process of the various data manipulation problems. Bitonic sorting algorithm is an efficient method to be parallelled due its systematic repetition characteristic of the partial comparison and rearrangement. The comparison pattern of Bitonic sorting is completely match with the Hypercube interconnection. This provides the motivation of this research. Mapping technique of the Bitonic sorting algorithm on a Hypercube system and its time complexity are discussed and calculated. A comparative study is conducted to show the effectiveness of the Hypercube architecture to support the Bitonic sorting algorithm. Two parallel Bitonic algorithms are proposed and analyzed to sort a large data under the limited number of Hypercube connected processors. These are High-Order Interleaving(HOI) Bitonic sorting algorithm and Low-Order interleaving(LOI)Bitonic sorting algorithm. Both algorithms are designed not only to avoid the data collision on the Hypercube network but also to maximize the processor utilization. It is shown that the HOI technique is simple to apply and takes less time to execute the sorting. The selection of algorithm, however, can be determined according to the requirement of the application problems.