본 논문에서는 병렬컴퓨터의 하이퍼큐브, 메쉬, 트리 위상에서 부하를 재분배할 때 소요되는 계산비용을 줄이기 위한 기법을 제안하였다. 기본 개념은 두가지이다. 첫 번째는 부하를 재분배할 때 각단계마다 발생하는 idle한 링크를 겹쳐서 사용하여 전송하는 방법이며, 두 번째는 이전의 방법에 파이프라인 형태로 부하의 이동을 수행하여 링크를 최대한 사용함으로써 보다 효과적으로 계산비용을 줄이는 방법이다. 즉, idle한 링크가 가능한 발생하지 못하게 부하의 전송에 링크가 적극 참여하도록 함으로써 계산비용을 은닉하는 방법이다. 실험을 통하여 병렬컴퓨터의 위상(하이퍼큐브, 메쉬, 트리)에 따라 기존의 기법들에 두 방법을 적용한 결과, 기존의 기법보다 최소 20%에서 최대 50%의 계산비용이 감소됨을 알 수 있었다.
In this paper, we introduce new methods for hiding computation overheads involved in load redistributing for parallel computer of hypercube, mesh and tree topologies. The basic idea is either coalescing some phases of load redistributing to overlap the transfer on different links or dividing each phase into steps to pipeline the transfer of load unit by unit for maximum utilization of links. They proved effective in making links busy transmitting load as soon as possible, hence reducing the computation overheads involved in balancing. Proposed techniques experimented on hypercube, mesh or tree topologies reduce communication overheads by 20% to 50% compared with known methods.
