(3.236.214.19) 您好!臺灣時間:2021/05/06 22:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:潘昆祺
研究生(外文):Kun-Chi Pan
論文名稱:異質計算環境中相依性任務排程之研究
論文名稱(外文):AN EFFICIENT SCHEDULING SCHEME FOR INTER-DEPENDENT TASKS IN HETEROGENEOUS COMPUTING ENVIRONMENTS
指導教授:李良德李良德引用關係
指導教授(外文):Liang-Teh Lee
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊工程學系(所)
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:44
中文關鍵詞:有向無迴路圖關鍵任務異質計算系統
外文關鍵詞:critical taskheterogeneous computing systemDAG
相關次數:
  • 被引用被引用:0
  • 點閱點閱:91
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
在高效能計算應用及研究領域中,平行與分散式計算已被廣泛地認為能勝任日益龐大的計算量之應用的方法,各種不同的計算單元透過不同的連接方式形成一個新的計算平台,稱之為異質計算系統,雖然異質計算系統能提供強大的計算能力,但必須有效率的管理及使用各個計算單元,因此需要有一個良好的排程器來實現高效能的平行運算,在此一研究方面先前已有許多文獻,大多是針對關鍵任務優先進行排程,以得到較短的排程長度,但對於異質計算系統中,此種作法會造成其它任務的延遲進而影響到關鍵任務的執行,由於上述問題,使得以前已提出的一些排程演算法必須做一些修改,以期得到較好的效能。本篇論文中我們提出一個以串列排程為基礎的有向無迴路圖的排程演算法。經由理論分析與數個模擬測試相驗證,結果顯示我們所提出之串列排程為基礎的有向無迴路圖的排程演算法能有良好的效能。
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.
ACKNOWLEDGEMENT ii
ABSTRACT iii
摘要 iv
TABLE OF CONTENTS v
LIST OF FIGURES vii
LIST OF TABLES viii
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 BACKGROUND 5
2.1 DAG Scheduling Problem 5
2.2 Classification of Scheduling Methods 9
2.2.1 List Scheduling Algorithms 9
2.2.2 Clustering Algorithms 10
2.2.3 Task Duplication Based Algorithms 11
2.3 The Critical-Path-on-a-Processor (CPOP) Algorithm 13
2.3.1 Assignment Phase 15
2.3.2 Processor Selection Phase 15
CHAPTER 3 NON-CRITICAL PATH EARLIEST-FINISH ALGORITHM 16
3.1 The Property of DAG in NPEF Algorithm 16
3.2 Non-critical Path Earliest-Finish (NPEF) ALGORITHM 17
3.2.1 Task Priority Phase 18
3.2.2 Processor Selection Phase 19
CHAPTER 4 AN EXAMPLE 20
CHAPTER 5 EXPERIMENTAL RESULTS 26
5.1 DAG Generator 26
5.2 Comparison and Results 28
CHAPTER 6 CONCLUSIONS AND FUTURE WORK 31
REFERENCES 32
Babak Hamidzadeh, Lau Ying Kit, and David J. Lilja, “Dynamic task scheduling using online optimization,” IEEE Transactions on Parallel and Distributed Systems, VOL. 11, Issue 11, Page(s):1151-1163, Nov 2000.
[2]Erik Saule, Pierre-Francois Dutot, and Gregory Mounie, “Scheduling with Storage Constraints,” Proceedings of International Parallel and Distributed Processing Symposium (IPDPS 2008), Page(s):1 - 8, April 2008.
[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.
[5]J. Barbosa, C. Morais, R. Nobrega, and A.P. Monteiro, “Static scheduling of dependent parallel tasks on heterogeneous clusters,” Proceedings of 2005 IEEE International Conference on Cluster Computing, Page(s):1 – 8 , Sept. 2005.
[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.
[7]Hui Jin, Yanxiang He, Weidong Wen, Haowen Liu, “A Run-Time Scheduling Policy for Dependent Tasks in Grid Computing Systems,” Proceedings of the Sixth International Conference on Parallel and Distributed Computing, Application and Technologies(PDCAT 2005), Page(s):521-523, December 2005.
[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.
[9]Ligang He, Stephen A. Jarvis, Daniel P. Spooner, David Bacigalupo, Guang Tan and Graham R. Nudd, “Mapping DAG-based applications to multiclusters with background workload,” Proceedings of 2005 IEEE International Symposium on Cluster Computing and the Grid, (2005. CCGrid), Volume 2, Page(s):855-862, May 2005.
[10]Min-You Wu, Daniel D. Gajski, “Hypertool: A Programming Aid for Message-Passing Systems,” IEEE Transactions on Parallel and Distributed Systems, VOL. 1, Issue 3, Page(s):330-343, July 1990.
[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.
[12]Haluk Topcuoglu, Salim Hariri, and Min-You Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, VOL. 13, Issue 3, Page(s):360-274, March 2002.
[13]Rizos Sakellariou, Henan Zhao, “A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems,” Proceedings of 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), April 2004.
[14]Tao Yang, Apostolos Gerasoulis, “DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors” IEEE Transactions on Parallel and Distributed Systems, VOL. 5, Issue 9, Page(s):951-967, September 1994.
[15]Santosh Pande, Dharma P. Agrawal, Jon Mauney, “A Scalable Scheduling Method for Functional Parallelism on Distributed Memory Multiprocessors,” IEEE Transactions on Parallel and Distributed Systems, VOL. 6, Issue 4, Page(s):388-399, April 1995.
[16]Yu-Kwong Kwok, Ishfaq Ahmad, “A Static Scheduling Algorithm Using Dynamic Critical Path for Assigning Parallel Algorithms onto Multiprocessors,” Proceedings of 1994 International Conference on Parallel Processing, (1994. ICPP), Volume 2, Page(s):155-159,August 1994.
[17]Rashmi Bajaj and Dharma P. Agrawal, “Improving scheduling of tasks in a heterogeneous environment,” IEEE Transactions on Parallel and Distributed Systems, VOL. 15, Issue 2, Page(s):107-118, Feb. 2004.
[18]Kun He and Yong Zhao, “A New Task Duplication Based Multitask Scheduling Method,” Proceedings of the Fifth International Conference on Grid and Cooperative Computing (GCC’06), Page(s):221 – 227, Oct. 2006.
[19]Sekhar Darbha, Dharma P. Agrawal, “Optimal Scheduling Algorithm for Distributed-Memory Machines,“ IEEE Transactions and Distributed Systems, VOL. 9, Issue 1, Page(s):87-95, January 1998.
[20]Chun-Hsien Liu, Chia-Feng Li, Kuan-Chou Lai, Chao-Chin Wu, “A Dynamic Critical Path Duplication Task Scheduling Algorithm for Distributed Heterogeneous Computing Systems,” Proceedings of the 12th International Conference on Parallel and Distributed Systems,(ICPADS 2006), July 2006.
[21]T. N'Takpe, F. Suter, “Critical path and area based scheduling of parallel task graphs on heterogeneous platforms,” Proceedings of the 12th International Conference on Parallel and Distributed Systems, (ICPADS 2006), July 2006.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔