Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

A Load Balancing Technique Combined with Mean-Field Annealing and Genetic Algorithms

평균장 어닐링과 유전자 알고리즘을 결합한 부하균형기법

  • 홍철의 (상명대학교 소프트웨어학부) ;
  • 박경모 (가톨릭대학교 컴퓨터정보공학부)
  • Published : 2006.08.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we introduce a new solution for the load balancing problem, an important issue in parallel processing. Our heuristic load balancing technique called MGA effectively combines the benefit of both mean-field annealing (MFA) and genetic algorithms (GA). We compare the proposed MGA algorithm with other mapping algorithms (MFA, GA-l, and GA-2). A multiprocessor mapping algorithm simulation has been developed to measure performance improvement ratio of these algorithms. Our experimental results show that our new technique, the composition of heuristic mapping methods improves performance over the conventional ones, in terms of solution quality with a longer run time.

본 논문에서는 병렬처리에서 중요한 이슈인 부하균형 문제에 대한 새로운 솔루션을 소개한다. 솔루션으로 제안하는 MGA 기법은 평균장 어닐링 (MFA)과 유전자 알고리즘 (GA)의 장점을 효과적으로 결합한 휴리스틱 부하균형기법이다. 제안된 MGA을 다른 매핑 알고리즘 (MFA, GA-l, GA-2) 들과의 성능 향상비를 측정하는 멀티프로세서 매핑 시뮬레이션을 개발하였다. 휴리스틱 매핑 기법의 합성을 통하여 기존의 방법보다 수행시간은 오래 걸리는 대신 솔루션 품질, 즉 최대종료시간 및 통신부하에서 개선된 실험 결과를 얻을 수 있다는 것을 보였다.

Keywords

References

  1. Bultan, T. and C. Aykanat, 'A New Mapping Heuristic Based on mean-field Annealing,' Journal of Parallel & Distributed Computing, 16, pp.292-305, 1992 https://doi.org/10.1016/0743-7315(92)90013-D
  2. Heiss, H.-U. and M. Dormanns, 'Mapping Tasks to Processors with the Aid of Kohonen Network,' Proc. High Performance Computing Conference, Singapore, pp. 133-143, Sep. 29-30, 1994
  3. 박경모, 홍철의, 'Performance of Heuristic Task Allocation Algorithms,' CUK Journal of Natural Science, Vol. 18, pp. 145-155, December 1998
  4. Salleh, S. and A. Y. Zomaya, 'Multiprocessor Scheduling Using Mean-Field Annealing,' Proc. of the First Workshop on Biologically Inspired Solutions to Parallel Processing Problems (BioSP3), pp. 288-296, March 30, Orlando, Florida, 1998 https://doi.org/10.1007/3-540-64359-1_699
  5. Zomaya, A.Y. and Teh Y.-W., 'Observations on Using Genetic Algorithms for Dynamic Load-Balancing,' IEEE Transactions on Parallel and Distributed Systems, Vol. 12, No.9, pp. 899 - 911, Sept. 2001 https://doi.org/10.1109/71.954620
  6. 박경모, 멀티프로세서 태스크 할당을 위한 유전자 알고리즘과 시뮬레이티드 어닐링 비교', 한국정보처리학회 논문지, 제6권, 9호, pp. 2311-2319, 1999년 9월
  7. 홍철의, '분산 시뮬레이티드 어닐링을 이용한 복합 재료 재단', 한국정보과학회 논문지 B, 제29권 1호, pp 20-29, 2000년 2월
  8. 홍철의, 박경모, '병렬처리에서 평균장 어닐링과 유전자 알고리즘을 이용한 부하균형', 한국정보과학회 2003 가을학술발표논문집(I), 제30권 2호, pp. 364-366, 2003 년 10월 24-25일