異質計算環境中相依性任務排程之研究

AN EFFICIENT SCHEDULING SCHEME FOR INTER-DEPENDENT TASKS IN HETEROGENEOUS COMPUTING ENVIRONMENTS

潘昆祺(Kun-Chi Pan)

指導教授 ： 李良德

大同大學/電機資訊學院/資訊工程學系所/碩士(2008年)

摘要

在高效能計算應用及研究領域中，平行與分散式計算已被廣泛地認為能勝任日益龐大的計算量之應用的方法，各種不同的計算單元透過不同的連接方式形成一個新的計算平台，稱之為異質計算系統，雖然異質計算系統能提供強大的計算能力，但必須有效率的管理及使用各個計算單元，因此需要有一個良好的排程器來實現高效能的平行運算，在此一研究方面先前已有許多文獻，大多是針對關鍵任務優先進行排程，以得到較短的排程長度，但對於異質計算系統中，此種作法會造成其它任務的延遲進而影響到關鍵任務的執行，由於上述問題，使得以前已提出的一些排程演算法必須做一些修改，以期得到較好的效能。本篇論文中我們提出一個以串列排程為基礎的有向無迴路圖的排程演算法。經由理論分析與數個模擬測試相驗證，結果顯示我們所提出之串列排程為基礎的有向無迴路圖的排程演算法能有良好的效能。

關鍵字

有向無迴路圖 ； 關鍵任務 ； 異質計算系統

並列摘要

For the high-performance computing applications and researches, parallel-and-distributive computing has been widely considered the way to process the gradual increasing amount of data generated from applications. The heterogeneous computing system is build up by connecting various computing units to obtain a higher system performance. In order to meet the requirements of managing each computing unit and shortening the execution time of applications efficiently in the heterogeneous computing system, an adequate scheduler for implementing high-performance parallel computing is required. In past years, many scheduling methods had been proposed. Those methods aimed to execute scheduling process at the critical task to obtain a shorter scheduling length. However, for heterogeneous computing systems, such methods may lead to lengthen the execution of other non-critical tasks, which results in affecting the execution of the critical task. In this thesis, a priority-based DAG scheduling algorithm for heterogeneous computing systems has been proposed to eliminate the mentioned problem. According to the theoretical analysis and several simulation results, the proposed method is proven to be a quite effective scheduling technique in the heterogeneous computing environment.

並列關鍵字

critical task ； heterogeneous computing system ； DAG

參考文獻

[3] Qiangsheng Hua and Zhigang Chen, “A new method for independent task scheduling in nonlinearly DAG clustering,” Proceedings of 7th International Symposium on Parallel Architectures, Algorithms and Networks, Page(s):187 – 192, May 2004 .

[4] Ligang He, Stephen A. Jarvis, Daniel P. Spooner, and Graham R. Nudd, “Performance Evaluation of Scheduling Applications with DAG Topologies on Multiclusters with Independent Local Schedulers,” Proceedings of IEEE International on Parallel and Distributed processing Symposium, April 2006.

[6] Mingsheng Shang, Shixin Sun, and Qingxian Wang, “An Efficient Parallel Scheduling Algorithm of Dependent Task Graphs,” Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Application and Technologies(PDCAT 2003), Page(s):595-598, August 2003.

[8] Sang Cheol Kim, Sunggu Lee, and Jaegyoon Hahm, “Push-Pull:Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster,” IEEE Transactions on Parallel and Distributed Systems, VOL. 18, Issue 11, Page(s):1489-1502, 2007.

[11] Yu-Kwong Kwok, Ishfag Ahmad, ”Dynamic Critical-Path Scheduling: A Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Transactions on Parallel and Distributed Systems, VOL. 7, Issue 5, Page(s):506-521, May 1996.