워크스테이션 네트웍에서의 휴리스틱 태스크 스케줄링 알고리즘 = A Heuristic Task Scheduling Algorithm in Workstation Networks

국문 초록 (Abstract)

본 논문에서는 워크스테이션 네트웍 (Network of Workstations) 환경에서 태스크 스케줄링문제를 해결하기 위하여 태스크 중복을 기반으로 하는 휴리스틱 스케줄링 알고리즘을 제안한다. 제안된 알고리즘에서는 NoW에서 통신할 때 발생되는 충돌을 방지하기 위하여 네트웍 통신 자원을 우선 할당하고, 스케줄링 길이를 단축하고 병렬처리 시간을 줄이기 위한 중복 태스크를 선택할 때 휴리스틱을 사용한다. 제안된 알고리즘은 태스크 그래프를 입력으로 받아 NoW 환경의 워크스테이션으로 스케줄링하며, 태스크 그래프에서 노드수가 V일 때 최악의 경우 알고리즘의 시간 복잡도는 O(V²)이다. 제안한 알고리즘을 실제 응용 프로그램의 태스크 그래프에 적용하였다. 시뮬레이션을 통하여 제안된 알고리즘이 스케줄링 길이와 알고리즘에서 요구하는 워크스테이션의 수 관점에서 성능이 향상되었음을 보여준다.

다국어 초록 (Multilingual Abstract)

In this paper, a task duplication based heuristic scheduling algorithm is proposed to solve the problem of task scheduling on network of workstations (NoW). The proposed algorithm pre-allocates network resources so as to avoid potential communication conflict, and the algorithm uses heuristics to select duplication tasks so as to reduce schedule length and parallel processing time. The algorithm schedules the task of a task graph on to the workstations of a NoW, and worst case time complexity is O(V²), where V is the number of nodes in a task graph. The proposed algorithm has been applied to some practical application DAGs. Simulation results show that the proposed algorithm achieves performance improvement in respect of schedule length and number of workstations required by the algorithm

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 문제 정의 및 관련 연구
• 3. 휴리스틱 태스크 스케줄링 알고리즘
• 4. 알고리즘의 성능 비교
• 5. 결론
• 참고문헌
• 저자소개