이종 프로세서를 위한 정적인 스케줄링 휴리스틱 = A Static Scheduling Heuristic for Heterogeneous Processors

국문 초록 (Abstract)

본 논문에서는 서로 다른 수행 시간을 가지는 다중 프로세서를 대상으로 한 Best Imaginary Level (BIL) 스케줄링이라는 정적인 비선점 스케줄링 휴리스틱을 제안하였다. 스케줄링의 대상이 되는 입력 그래프는 선후 관계의 제약 조건을 가지는 비순환 그래프이며, 그래프 상의 각 노드는 각각의 프로세서에서 다른 수행 시간을 가진다. 노드의 정적인 레벨(BIL)은 프로세서간의 통신(IPC)을 고려하고 프로세서의 이종성도 고려한다. 제안된 스케줄링 기법이 입력 그래프의 모양이 선형인 경우 최적의 스케줄링 결과를 생성해 내는 것을 증명하였다. BIL 스케줄링은 현존하는 스케줄링 기법인 general dynamic level (GDL) 스케줄링 기법과 비교해서 다양한 형태의 무작위로 만들어낸 입력 그래프에 대해 약 20%의 성능 향상을 가져왔다.

다국어 초록 (Multilingual Abstract)

This paper presents a static scheduling heuristic called Best Imaginary Level (BIL) scheduling for heterogeneous processors. The input graph is an acyclic precedence graph, where a node has different execution times on different processors. The static level of a node, or BIL, incorporates the effect of interprocessor communication (IPC) overhead and processor heterogeneity. The proposed scheduling technique is proven to produce the optimal scheduling result if the topology of the input task graph is linear. The performance of the BIL scheduling is compared with an existing technique called the general dynamic level (GDL) scheduling with various classes of randomly.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. General Dynamic Level Scheduling Technique
• 3. Best Imaginary Level Scheduling
• 4. 모의 실험
• 5. 결론
• 참고문헌
• 부록
• 저자소개