확장된 그래디언트 모델에 의한 동적 부하균형 기법 = Dynamic Load Balancing Schemes Using Extended Gradient Model

국문 초록 (Abstract)

다중프로세서 시스템에서의 부하균형은 시스템의 처리율, 프로세서 이용율과 밀접한 관련이 있는 중요한 문제 중의 하나이다. 본고에서는 기존에 개발된 부하균형 알고리즘 가운데 Lin이 제안한 Gradient Model에서의 부하이동이 이웃 처리소자간의 인접도와 모든 처리소자에 적용되는 정적 임계치에 의해서 결정되므로 인해 발생하는 결점을 분석하고, 이를 보완한 동적 부하균형 기법으로서 demand-driven 방식을 사용하는 Extended Gradient Model을 제안한다.
제안된 모델에서는 이용율이 낮은 처리소자와 높은 처리소자간의 이동할 태스크 단위가 정적 임계치가 아닌 동적 임계치인 Dt에 의해서 결정되므로써, 시스템내 처리소자의 부하를 좀더 정확히 반영할 수 있으며, 이로부터 보다 효과적인 지역적, 광역적 부하균형을 이룰 수 있다.
EGM을 따르는 세가지의 부하균형 기법으로 부터 얻어진 시뮬레이션 결과는 여기서 제안한 모델이 GM에 비해서 Dt를 계산하기 위한 여분의 시간이 필요하다는 점을 제외하고는, 처리소자들간의 현실적인 부하상황 표현, 처리소자의 이용율, 지역과 광역 부하균형 측면에서 보다 많은 장점이 있음을 시사해주고 있다.

다국어 초록 (Multilingual Abstract)

The load balancing in multiprocessor systems has been one of the critical issues closely related to the system throughputs and the processor utilization We analysed the defects of Lin's Gradient Model for extension, in which load migration would be determined by the proximities between neighboring processing elements and the static threshold of each processing element, and proposed a demand-driven dynamic load balancing model, the Extended Gradient Model.
In our proposed model, migratable task units between the underutilized and overutilized processors can be calculated not by the static threshold but by the dynamic threshold, Dt, so the workloads of PEs in a system can be more accurately described and this results in more effective local and global load balancing.
The simulation results for three kinds of load balancing schemes falling into the EGM show that our proposed model has far too many advantages in description of the real workload situation between PEs, and in the processor utilization, and in local and global load balancing except the fact that the extra overheads may be required for the calculation of the dynamic threshold, Dt, over the GM.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 관련 부하균형 기법
• 3. EXTENDED GRADIENT MODEL
• 4. SANTCHING SCHEME에 따른 EGM 모델
• 5. 결론
• 참고문헌
• 저자소개