초록

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

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.

주제어

#매핑   #병렬처리   #시뮬레이티드 어닐링   #평균장 어닐링   #유전자 알고리즘  

저자의 다른 논문

참고문헌 (8)

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 
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 
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 
6. 홍철의, '분산 시뮬레이티드 어닐링을 이용한 복합 재료 재단', 한국정보과학회 논문지 B, 제29권 1호, pp 20-29, 2000년 2월  원문보기 상세보기
7. 홍철의, 박경모, '병렬처리에서 평균장 어닐링과 유전자 알고리즘을 이용한 부하균형', 한국정보과학회 2003 가을학술발표논문집(I), 제30권 2호, pp. 364-366, 2003 년 10월 24-25일 
8. 박경모, 멀티프로세서 태스크 할당을 위한 유전자 알고리즘과 시뮬레이티드 어닐링 비교', 한국정보처리학회 논문지, 제6권, 9호, pp. 2311-2319, 1999년 9월  원문보기 상세보기

이 논문을 인용한 문헌 (1)

1. Hong, Chul-Eui 2010. "Distributed Mean Field Genetic Algorithm for Channel Routing" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences, 14(2): 287~295  원문보기 상세보기