초록 close

병렬 외부정렬을 클러스터형 분산 컴퓨터에서 실행하는 경우에는 순수하게 주메모리에서 부분적인 정렬과 머지를 위해 실행되는 과정(순수 계산)뿐만 아니라 디스크로부터의 입출력 과정 및 각 노드들 간의 데이타 교환에 따르는 통신과정을 적절히 배치, 설계함이 필요하다. 그 주된 이유는 전체 수행시간이 순수 계산시간보다는 디스크 입출력에 소요되는 시간 및 통신의 소요시간의 비중이 크기 때문이다. 본 연구에서는 저속 네트웍 PC 클러스터를 계산도구로 하여 단위시간당 정렬 자료규모를 최대화함을 목표로 하여, 알고리즘적인 최적화를 통해서, 즉, 정렬 도중 통신과정에서 발생하는 지체시간을 최소화하여 전체적인 통신 성능을 높이고, 디스크 입출력 작업은 전송 규모와 횟수를 조절하여 계산과 통신작업등과의 중첩정도를 극대화시켜 외부정렬의 성능을 개선하였다. 실험 결과 새 알고리즘이 기존의 NOW-sort 알고리즘 1 에 비해서 동일한 PC 클러스터 환경에서 최대 45% 정도까지 실행시간을 단축시킬 수 있고, 확장성 면에 있어서도 더 우수한 것을 확인하였다.


External sort on cluster computers requires not only fast internal sorting computation but also careful scheduling of disk input and output and interprocessor communication through networks. This is because the overall time for the execution is determined by reflecting the times for all the jobs involved, and the portion for interprocessor communication and disk I/O operations is significant. In this paper, we improve the sorting performance (sorting throughput) on a cluster of PCs with a low-speed network by developing a new algorithm that enables even distribution of load among processors, and optimizes the disk read and write operations with other computation/ communication activities during the sort. Experimental results support the effectiveness of the algorithm. We observe the algorithm reduces the sort time by 45% compared to the previous NOW-sort 1 , and provides more scalability in the expansion of the computing nodes of the cluster as well.