A computational grid, or simply Grid, is a new way of cost-effective and high performance parallel computing. It can solve large problems by combing computing resources across the network but traditional components for parallel computing need to be midified. This thesis studies the collective communication under the Grid environment, which can be represented by the combination of heterogeneous networks.
To generate a schedule for collective communication, scheduling algorithms use network information, but network information service in the grid provides erratic information. The proposed approach, called $\emph{TTCC(Two-Tree Collective Communication)}$, generated efficient schedule which can tolerate this unfavorable condition.
This thesis also studies the collective communication primitives of modified MPI under the Grid environment, such as multilevel broadcast, and identifies the increased overhead of multilevel broadcast. The second proposed approach, called $\emph{SRT(Send and Receive Table)}$, alleviate the overhead of multilevel broadcast but it does not increase the network cost since the proposed method has the same network access pattern as the conventional method. Benefit of the proposed methods are quantified via simulations and experiments on a cluster system.
본 논문은 분산된 이질적인 시스템으로 대변되는 그리드 컴퓨팅을 배경으로 하고 있으며, 특히 병렬컴퓨팅에서 다수 프로세서간 통신에 유용하게 사용되는 집합 통신(Collective Communication)을 그리드 컴퓨팅에 적용 시 발생하는 문제에 대해 살펴보고, 이에 대한 대안을 제시한다.
집합 통신은 기존의 메시지 전달 방식에 기반을 둔 병렬 프로그래밍 기법에서 전체 시스템 성능에 크게 영향을 미치는 중요한 메세지 전달 기법이다. 그러나 기존의 많은 방법들은 동질적인 시스템을 기반으로 하고 있으며, 최근에서야 그리드 컴퓨팅의 중요성이 대두되면서, 이질적인 시스템상에서의 집합 통신에 대한 연구가 진행되고 있으며, 실례로 다중 레벨 트리 기반의 브로드캐스트, 휴리스틱한 해결 방안을 이용한 ECEF 알고리즘 등을 들 수 있다. 본 논문에서는 기존의 연구에 대한 문제점과 더불어, 이를 해결하기 위한 다음과 같은 두 가지 기법을 제시한다.
\bf{1. 이중 트리를 이용한 집합 통신(TTCC).}
기존의 ECEF알고리즘은 이질적인 네트워크의 집합에서 효율적인 통신 트리(Communication Tree)를 생성을 보장한다. 그러나 이를 실제 상황인 그리드 컴퓨팅에 적용하는 데는 문제가 발생할 수 있다. 즉, ECEF는 정확한 네트워크 정보 획득을 전제 조건으로 하고 있으나, 현재 많은 그리드 프로젝트에서 사용되는 네트워크 정보 모니터링 툴인 NWS(Network Weather Service)는 완벽한 네트워크 정보를 제공하지 못하고 있다. 이는 네트워크 상황을 실시간으로 모니터링 할 수 없다는 제약과 100% 정확한 예측기법을 만들 수 없다는 점에서 기인한다. 따라서 이러한 상황을 무시한 해, ECEF를 그리드 컴퓨팅에서 사용할 때는, 부정확한 정보로 인한 급격한 성능 저하가 발생할 수 있다.
본 논문에서 제시한 이중 트리 기법은, 기존의 ECEF가 생성한 트리에 보조적인 중복 트리를 추가로 생성하여, 집합 통신 수행 시, 실제 상황에서 성능이 우수한 경로를 부분적으로 선택하는 알고리즘으로, 부정확한 정보로 인한 부작용을 최소화한 기법이다. NWS가 제공하는 정보가 일반적으로 정규분포와 같은 형태의 오차율을 가지고 있다는 점에 감안하여 네트워크 정보에 표준편차를 달리한 정규분포형태의 오차율을 추가한 뒤 실험하였고, 시뮬레이션 결과, 이중 트리 기법이 기존의 ECEF에 비해 오차로 인한 성능 저하가 적음을 확인할 수 있었다.
\bf{2. 송수신표(SRT)를 이용한 다중 레벨 브로드케스트.}
다중 레벨 트리 기반의 브로드캐스트는 전송능력이 취약한 네트워크의 접근을 최소화 하기 위하여, 제안된 효과적인 브로드캐스트 기법이며, 그리드 컴퓨팅의 대표적인 프로젝트라 할 수 있는 Globus시스템에서 사용된 MPICH-G2에 채택되어질 계획이다. 그러나 실제로 이를 구현함에 있어서, 가장 많이 사용되는 MPI함수(MPI_Comm_spilt)가 실제 성능에 비해 오버헤드가 상대적으로 높으므로 시스템의 성능을 저하시키는 요인으로 작용할 수 있다. 이는 실제로 여러 시스템에서 MPI함수들의 수행시간을 테스트 함으로써 확인할 수 있었다.
이러한 문제를 최소화하기 위하여, 기존의 방식과 동일한 네트워크 접근 패턴을 제공하되, 오버해드가 적은 MPI 함수들로 구성된 송수신표 기법을 제시하였고, 실제 테스트 결과, 기존의 방식보다 성능이 향상됨을 알 수 있었고, 특히 SMP 클러스터 상에서의 성능이 크게 증대 되었다.
이상의 시뮬레이션 결과와 실험 결과치를 기반으로, 두 가지 방법을 동시에 적용했을 때의 성능 향상을 살펴 보았다. 일반적으로 이질적인 시스템상에서 집합통신의 전체 수행 시간은 성능이 가장 저조한 시스템에 의해서 결정되어 진다고 볼 수 있다. 따라서 Cray 시스템부터 클러스터 시스템까지를 하나의 시스템으로 구성했다고 가정하면, 전체 수행 시간은 클러스터 시스템에 의하여 결정되어진다고 볼 수 있으므로 클러스터상에서 측정한 송수신표 기법의 결과를 바탕으로 이중 트리 기법을 시뮬레이션 한 결과, 두 가지 방법을 이용 함으로서, 전체시스템의 성능이 개선됨을 확인 할 수 있었다.
