Browse

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

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
오현옥; 하순회
Issue Date
1998-12
Publisher
한국정보과학회 = Korea Informaion Science Society
Citation
Journal of KIISE : computer systems and theory , vol.25, no.12, pp.1339-1347, Dec. 1998
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.
ISSN
1598-5164
Language
Korean
URI
http://uci.or.kr/G300-j12262315.v25n12p1339

http://hdl.handle.net/10371/8901
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Journal Papers (저널논문_컴퓨터공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse