이질 프로세서를 위한 정적인 스케줄링 휴리스틱

Abstract

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