반복적인 부하 이동에 의한 휴리스틱 부하 평형 알고리즘 = A Heuristic Load Balancing Algorithm by using Iterative Load Transfer

국문 초록 (Abstract)

본 논문에서는 다중 프로세서 시스템을 위한 휴리스틱 부하 평형 알고리즘을 제안한다. 제안 알고리즘은 부하이동을 여러 링크로 분산시켜 사용하지 않는 링크의 수를 최소화시키고 그에 따라 통신비용을 감소시킨다. 각각의 프로세서는 모든 이웃한 프로세서에게 단위부하를 보내거나 받는 과정을 반복적으로 시도한다. 그러나 실제의 부하 이동은 모든 부하평형 계산이 이루어진 후 수행된다. 이는 불필요한 부하 이동을 최소화시킨다. 제안된 알고리즘은 약간의 수정만으로 다양한 연결 구조를 갖는 다중 프로세서 시스템에 적용할 수 있다. 본 논문에서는 하이퍼큐브 구조와 메쉬 구조에 제안 알고리즘을 적용해 보았다. 알고리즘의 성능평가를 위하여 모의실험을 하였다. 제안된 알고리즘과 잘 알려진 두 가지 종류의 알고리즘의 성능을 비교하였다. 그 결과 제안된 알고리즘은 모든 경우에서 부하평형의 목적을 달성하였다. 또한 기존의 알고리즘과 비교하여 하이퍼큐브 구조에서는 통신비용을 70～90% 감소시켰다. 메쉬 구조에서도 통신비용은 약 75% 감소되었다.

다국어 초록 (Multilingual Abstract)

This paper proposes a heuristic load balancing algorithm for multiprocessor systems. The algorithm minimizes the number of idle links to distribute load traffic and reduces its communication cost. Each processor iteratively tries to transfer unit load to/from every neighbor processors. However, real load transfer is collectively done after complete load traffic calculation to minimize useless traffic. The proposed algorithm can be employed in various interconnection topologies with slight modifications. In this paper, it is applied to both hypercube and mesh environments. For performance evaluation, simulation studies are performed. The performance of proposed algorithm is compared to those of two well-known algorithms. The results show that the proposed algorithm always balances the loads perfectly. Furthermore, it reduces the communication costs by 70～90% in the hypercube；and it reduces the cost by 75% in the mesh, compared to existing algorithms.

참고문헌 (Reference)

• 1 임화경, "신속한 부하균등화를 위한 휴지링크의 최대활용방법" 28 (28): 632-641, 2001
• 2 Kyungwan Nam, "Synchronous Load Balancing in Hypercube Multicomputers with Fault Nodes" 58 : 26-43, 1999
• 3 S. Ranka, "Programming a Hypercube Multicomputer" 69-77, 1988.
• 4 Leonid Oliker, "PLUM：Parallel Load Balancing for Adaptive Unstructured Meshed" 52 : 150-177, 1998
• 5 M. Y. Wu, "On Runtime Parallel Scheduling for Processor Load Balancing" 8 (8): 173-185, Feb.1997
• 6 I. Ahnad,, "On Parallelizing the Multiprocessor Scheduling Problem" 10 (10): 414-432, 1999
• 7 Marlin H. Mickle, "Loading Balancing Using Heterogeneous Processors for Continuum Problems on a Mesh" 39 : 66-73, 1996
• 8 M. Y. Wu, "Hypertool" 1 (1): 330-343, July,1992.
• 9 C. Hui,S. Chanson, "Hydrodynamic Load Balancing" 10 (10): 1118-1137, 1999
• 10 M. Mitzenmacher, "How useful Is Old Information" 4 (4): 979-993, 1993.
• 11 G. Cybenko, "Dynamic Load Balancing for Distributed Memory Multiprocessors" 7 : 279-301, 1989.
• 12 Min-You Wu, "DDE：A Modified Dimension Exchange Method for Load Balancing in k-ary n-cube" 44 : 88-98, 1997