(3.236.100.6) 您好!臺灣時間:2021/04/24 02:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:鄭仰評
研究生(外文):Yang-Ping Cheng
論文名稱:應用於異質計算以工作複製為基礎的高效能排程演算法
論文名稱(外文):A Performance-Efficient Task Duplication-Based Scheduling Algorithm for Heterogeneous Computing
指導教授:鍾葉青鍾葉青引用關係
指導教授(外文):Yeh-Ching Chung
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:94
語文別:英文
論文頁數:36
中文關鍵詞:平行處理排程異質系統工作複製工作圖形
外文關鍵詞:parallel processingschedulingheterogeneous systemstask duplicationtask graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:127
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:9
  • 收藏至我的研究室書目清單書目收藏:0
利用高速網路連接不同的資源提供了一個新的計算平台,稱為異質計算系統,異質計算系統可以提供執行平行和分散式的密集計算。為了在異質系統中達到高效能,有效率的排程是非常關鍵性的。雖然已經有許多排程演算法在文獻中被提出,但大部分主要是針對同質系統。在這篇論文中,我們提出了一個可以達到高效能,運用在有限異質運算元環境中的神奇演算法,此演算法稱為異質工作複製排程 (heterogeneous task duplication scheduling (HTDS))。HTDS利用工作複製的方法來減少資料傳送的負擔,進而達到最小化排程長度。為了評價HTDS演算法的效能,我們製作了一個模擬器,這個模擬器包含了一個可以產生不同特性加權的有向無回圈圖形(DAG)的參數化圖形產生器。在這個模擬器上,我們嵌入了HTDS,HEFT,LDBS1 和LDBS2四個演算法。模擬結果顯示我們的排程演算法在效能方面優於其他演算法。
Diverse sets of resources interconnected with a high-speed network provide a new computing platform, called the heterogeneous computing system, which can support the execution of computationally intensive parallel and distributed application programs. Efficient task scheduling algorithm is critical for application programs to achieve high performance in heterogeneous computing systems. Although a large number of scheduling heuristics have been presented in the literature, most of them are mainly for the systems with homogeneous processors. In this thesis, we present a novel task scheduling algorithm, heterogeneous task duplication scheduling (HTDS), for a bounded number of heterogeneous processors with an objective to meet high performance. The HTDS algorithm uses task duplication method to decrease the communication overhead and to minimize the schedule length of application programs. To evaluate the performance of the proposed task scheduling algorithm, we have developed a simulator that contains a parametric graph generator for generating weighted directed acyclic graphs with various characteristics. We have implemented the HTDS along with three task scheduling algorithms, HEFT, LDBS1, and LDBS2, on the simulator. The simulation results show that our task scheduling algorithm outperforms other algorithms in terms of speedup.
1 Introduction
2 Related Work
2.1 The Heterogeneous Earliest Finish Time (HEFT) Algorithm
2.2 The Levelized Duplication Based Scheduling (LDBS) Algorithm
3 The Computational and the Architectural Model
4 The HTDS Algorithm
4.1 Definitions and Rule used by HTDS
4.2 HTDS Algorithm
5 Performance Evaluation and Simulation Results
5.1 GPP < 1
5.2 GPP = 1
5.3 GPP > 1
5.4 Comparisons of Execution Time of Scheduling Algorithms
6 Conclusions
References
Appendix
[1] T.L. Adam, K.M. Chandy, and J.R. Diskson, “A Comparison of List Schedules for Processing Systems,“ Communication of ACM, Vol.17 , No. 12, pp. 685-690, 1974.
[2] I. Ahmad and Y.-K. Kwok, “On Exploiting Task Duplication in Parallel Program Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 9 September 1998.
[3] Y.C. Chung and S. Ranka, “Applications and Performance Analysis of a Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed Memory Multiprocessors,” Proc. Supercomputing, pp. 512-521, Nov. 1992.
[4] Atakan Dogan and Fusun Ozguner, “LDBS: A Duplication Based Scheduling Algorithm for Heterogeneous Computing Systems,” Proceedings of the International Conference on Parallel Processing (ICPP’02), 2002.
[5] H. El-Rewini and T.G. Lewis, “Scheduling Parallel Program Tasks onto Arbitrary Target Machines,” Journal of Parallel and Distributed Computing, Vol. 9, pp.138-153, 1990.
[6] A. Gerasoulis and T. Yang, “A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessor,” J. Parallel and Distributed Computing, Vol. 16, No. 4, pp. 276-291, December 1992.
[7] T. Hagras, J. Janecek, “A High Performance Low Complexity Algorithm for Compile-Time Task Scheduling in Heterogeneous Systems,” Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), 2004.
[8] J.J. Hwang Y.C Chou, F.D. Anger, and C.Y. Lee, “Scheduling Precedence Graphs in Systems with Interprocessor Communication Times,” SIAM Journal of Computing, Vol. 18. pp. 244-257, 1989.
[9] M. Iverson, F. Ozguner, and G. Follen, “Parallelizing Existing Applications in a Distributed Heterogeneous Environment,” Proc. Heterogeneous Computing Workshop, pp. 93-100, 1995.
[10] S.J. Kim and J.C. Browne, “A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures,“ Proc. Int’l Conf. Parallel Processing, Vol. 2, pp. 1-8,1998.
[11] B. Kruatrachue and T.G. Lewis, “Grain Size Determination for Parallel Processing,” IEEE Software, pp. 23-32, Jan. 1988
[12] Y.-K. Kwok and I. Ahmad, “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors,” ACM Computing Surveys, Vol. 31, No. 4, December 1999.
[13] Y.-K. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 5, pp. 506-521, May 1996.
[14] G.-L. Park, B. Shirazi, and J. Marquis, “DFRN: A new approach for duplication based scheduling for distributed memory multiprocessor systems,” Proc. Int’l Conf. Parallel Processing Symposium, pp. 157-166, 1997.
[15] A. Radulescu and A.J.C. Van Gemund, “Fast and Effective Task Scheduling in Heterogeneous Systems,” Proc. Of HCW, pp. 229-238, MAY 2000.
[16] S. Ranaweera and D.P. Agrawal, “A Task Duplication based Algorithm for Heterogeneous Systems,” Proc. Of IPDPS, pp. 445-450, May 2000.
[17] R. Sakellariou, H. Zhao, “A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems,” Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), 2004.
[18] G.C. Sih and E.A. Lee, “Scheduling to Account for Interprocessor Communication within Interconnection-Constrained Processor Networks,” ICPP, Vol. 1, pp. 9-16, 1990.
[19] G.C. Sih and E.A. Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 2, pp. 175-186, Feb. 1993.
[20] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, March 2002.
[21] M. Wu and D. Gajski, “Hypertool: A Programming Aid for Message Passing Systems,” IEEE Transactions on Parallel and Distributed Systems, Vol. 1, pp. 330-343, July 1990.
[22] T. Yang and A. Gerasoulis, “DSC: Scheduling Parallel Tasks on an unbounded Number of Processors,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 9, pp.951-967, Sept. 1994.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔