- 전역 이기종 환경에서의 정적 태스크 스케줄링의 비교 연구
- ㆍ 저자명
- 김정환,Kim. Jung-Hwan
- ㆍ 간행물명
- 정보처리학회논문지. The KIPS transactions. Part A. Part A
- ㆍ 권/호정보
- 2006년|2호|pp.163-170 (8 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
DAG(Directed Acyclic Graph) 기반의 스케줄링을 포함한 많은 스케줄링 문제들은 대부분 NP-Complete로 알려져 있으며, 따라서 휴리스틱에 기반한 많은 알고리즘 연구들이 진행되어 왔다. 이 중 HEFT와 CPOP은 이기종 환경에서 효과적인 알고리즘으로 알려져 있다. 본 논문의 이전 연구에서는 이기종 환경이 보다 현실성 있는 전역 네트워크로 구성된 경우에 대해 효과적인 3개의 알고리즘(CPOC, eCPOC, eCPOP)을 제안한 바 있다. 본 논문에서는 이들 총 5개의 알고리즘에서 사용하는 휴리스틱을 체계적으로 분석하고, 다양한 벤치마크를 사용한 실험을 통해 비교 분석하였다. 실험 결과 전역 이기종 환경에서 eCPOC이 가장 우수한 성능을 보여주었고, 또한 제안된 3개의 알고리즘에서 사용하는 휴리스틱들이 전역 이기종 환경에서 효과적임이 확인되었다.
Most scheduling problems including DAG(Directed Acyclic Graph)-based are known to be NP-complete, so many heuristic-based scheduling algorithms have been researched. HEFT and CPOP are such algorithms which have been devised to be effective in heterogeneous environment. We proposed, in the previous research, three scheduling algorithms which are effective in realistic global heterogeneous environment: CPOC, eCPOPC and eCPOP. In this paper, the heuristics which are used in the above five algorithms will be systematically analyzed. Those algorithms will be also studied experimentally using various benchmarks. Experimental results show that the eCPOC generates better schedules than any other algorithms and the heuristics which are used in the proposed algorithms are effective in the global heterogeneous environment.