A Study in Allocating Task Graphs onto a Heterogeneous Cluster-Computing System

分派工作於異質性叢集運算系統之研究

江傳文(Chuan-Wen Chiang) ； 李宗南(Chung-Nan Lee)

《大葉學報》 11卷1期 (2002/06) Pp. 103-110

https://doi.org/10.7119/JDYU.200206.0103

摘要

異質性叢集運算已被認為是極具發展潛力的方法，用以解決需要大量運算的科學問題。吾人可將某一平行程式分解為數個工作，並將這些工作以並行的方式指派給不同的處理單元來執行。一般而言，這些工作可以用工作圖來加以特徵化，並且以一個有向非循環圖來表示。本論文中，我們提出一個動態排程演算法，用以將工作圖中的工作分派於異質性叢集運算的系統之中。此一演算法稱之為「動態群組排程」演算法，簡稱為DGS。DGS與傳統方法有以下兩點不同：第一、其以一種工作群組的策略來決定一個工作的初始計算成本。第二、在排程過程中的每一步驟，DGS會針對所有未被排程的工作來估算所有處理單元的勝任度。實驗結果顯示，DGS確實優於其它用於評比的演算法。

關鍵字

叢集運算 ； 工作排程 ； 有向非循環圖

並列摘要

Heterogeneous cluster computing is regarded as a promising approach to solve CPU-intensive problems at a low cost. One can decompose a composite parallel program into constituent tasks so that these tasks can be assigned to different process elements (PEs) for concurrent execution. These tasks generally can be characterized by a task graph, which is represented as a directed acyclic graph (DAG). In this study, a dynamic scheduling heuristic is proposed for allocating task graphs onto a heterogeneous cluster-computing system. The proposed algorithm, called the Dynamic Grouping Scheduling (DGS) algorithm, differs from conventional algorithms in two respects. First, DGS employs a task-grouping strategy to determine the initial computation cost of a task. Second, this algorithm estimates the competence of PEs for unscheduled tasks at each scheduling step. The performance of DGS is demonstrated by comparing it with other existing algorithms in terms of the schedule length. Experimental results show that the proposed DGS performs better than the competing scheduling heuristics under the effects of varying power weights of PEs.

並列關鍵字

cluster computing ； task scheduling ； directed acyclic graph