臺灣博碩士論文加值系統

在異質性分散式計算系統中，對於可利用有向非循環圖來表示的平行化應用程式，提供一個有效的工作排程方法來獲取高效能的結果是不可或缺的。由於在工作排程問題當中找尋一個最佳解的演算法已經被證明是個NP-complete的問題；因此，近年來有許多啟發式演算法被提出來解決在異質性分散式計算系統中的工作排程。然而，在這些演算法中皆沒有考慮到各個計算單元中的記憶體限制，此限制使得作業系統無法在計算單元上安裝以提供記憶體管理。每件工作都必須從特定的實體記憶體位置開始存放且在需要的時候才載入至計算單元中；亦即，在此系統中的工作排程，除了要考量到不同計算單元之間的異質性和溝通成本，也需要考量到與工作程式大小相關的載入時間。為了區別不同程式的工作，在有向非循環圖中的節點皆以顏色來表示相對應的程式功能，稱為著色的有向非循環圖。此篇論文提出一個新的靜態列舉式工作排程演算法，稱為Heterogeneous Loading Time Aware (HLTA)，此演算法擁有三項特點。首先，利用著色的有向非循環圖之階層將優先權工作列劃分群組。其次，使用貪婪機制根據節點顏色來調整優先權，盡量讓相同顏色的節點能夠排程到同一計算單元上。最後，提供一個煞車機制，使得當節點間擁有較高相同顏色比例時，貪婪機制能夠更完善的運用。根據隨機產生圖中的實驗研究比較，HLTA演算法在排程品質以及平均SLR改善率皆顯著地優於Heterogeneous Earliest-Finish-Time (HEFT)演算法。

Effective task scheduling of parallel applications represented by directed acyclic graph (DAG) is critical for obtaining high performance in heterogeneous distributed computing systems (HDCSs). As the problem of finding optimal scheduling algorithm has been shown to be NP-complete in general cases, many heuristic algorithms for scheduling on HDCSs have been proposed recently. However, none of them consider the case where processing elements (PEs) have memory constraints which prevent operating system from being installed on PEs to provide memory management. Tasks have to be stored on a specific physical memory address and loaded on demand, which means that task schedule in such computing systems requires the consideration of the loading time of tasks associated with their code size besides the heterogeneity of PEs and the inter-PE communication overhead. For identifying different code size of tasks, the nodes of DAG are colored with different color types according to their functionalities, called colored-DAG. This thesis presents a new static list-based scheduling algorithm, called the Heterogeneous Loading Time Aware (HLTA) algorithm, which has three distinctive features. First, the algorithm partitions the priority list by layer heuristic of colored-DAG. Second, the algorithm uses novel greedy mechanism to reorder and schedule the identical color of nodes to the same PE as could as possible. Finally, a braking mechanism is used to refine the greedy reordering when scheduling a high color ratio colored-DAG. The comparison study, based on randomly generated graphs, shows that HLTA algorithm significantly surpasses the Heterogeneous Earliest-Finish-Time (HEFT) algorithm in terms of quality of schedules and average schedule length ratio improvement.

Chapter 1 Introduction ....................................1
Chapter 2 Problem Definition ..............................3
2.1 Task Graph ............................................3
2.2 Target Computing Environment ..........................5
2.3 Attributes Definition .................................7
Chapter 3 Related Work ...................................10
Chapter 4 Proposed Task Scheduling Algorithm .............13
4.1 Greedy Mode with Braking Mechanism ...................13
4.2 Define Attributes Used by HLTA Algorithm .............15
4.3 HLTA Task Scheduling Algorithm .......................16
4.3.1 Phase One: Build Task Prioritizing Queue ...........16
4.3.2 Phase Two: Grouping According Layer Heuristic Information ..............................................16
4.3.3 Phase Three: Reorder Task and Processing Element Selection ................................................16
4.4 Numerical Example ....................................19
Chapter 5 Experimental Results and Discussion ............22
5.1 Performance Metrics ..................................22
5.2 Randomly Generated Application Graphs ................24
5.2.1 Random DAG Generator ...............................24
5.2.2 Random Color Generator .............................26
5.3 Performance Results ..................................27
Chapter 6 Conclusion and Future Work .....................37
References ...............................................38

[1] I. Ahmad, and K. Yu-Kwong, A New Approach to Scheduling Parallel Programs Using Task Duplication, Parallel Processing, 1994. ICPP 1994. International Conference on, 1994, pp. 47-51.
[2] A.H. Alhusaini, V.K. Prasanna, and C.S. Raghavendra, A unified resource scheduling framework for heterogeneous computing environments, Heterogeneous Computing Workshop, 1999. (HCW '99) Proceedings. Eighth, 1999, pp. 156-165.
[3] M.A. Baker, P. Dalale, K.S. Chatha, and S.B.K. Vrudhula, A Scalable Parallel H.264 Decoder on the Cell Broadband Engine Architecture, Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis, ACM, Grenoble, France, 2009, pp. 353-362.
[4] M.I. Daoud, and N. Kharma, A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing 68 (2008) 399-409.
[5] S. Darbha, and D.P. Agrawal, Optimal Scheduling Algorithm for Distributed-Memory Machines. IEEE Transactions on Parallel and Distributed Systems 9 (1998) 87-95.
[6] H. El-Rewini, and T.G. Lewis, Scheduling Parallel Program Tasks onto Arbitrary Target Machines. Journal of Parallel and Distributed Computing 9 (1990) 138-153.
[7] B. Flachs, S. Asano, S.H. Dhong, H.P. Hofstee, G. Gervais, K. Roy, T. Le, L. Peichun, J. Leenstra, J. Liberty, B. Michael, O. Hwa-Joon, S.M. Mueller, O. Takahashi, A. Hatakeyama, Y. Watanabe, N. Yano, D.A. Brokenshire, M. Peyravian, T. Vandung, and E. Iwata, The Microarchitecture of the Synergistic Processor for a Cell Processor. Solid-State Circuits, IEEE Journal of 41 (2006) 63-70.
[8] P. Gyung-Leen, B. Shirazi, and J. Marquis, DFRN: a new approach for duplication based scheduling for distributed memory multiprocessor systems, Parallel Processing Symposium, 1997. Proceedings., 11th International, 1997, pp. 157-166.
[9] T. Hagras, and J. Janecek, A Simple Scheduling Heuristic for Heterogeneous Computing Environments, Parallel and Distributed Computing, 2003. Proceedings. Second International Symposium on, 2003, pp. 104-110.
[10] T. Hagras, and J. Janecek, An Approach to Compile-Time Task Scheduling in Heterogeneous Computing Systems, Proceedings of the 2004 International Conference on Parallel Processing Workshops, IEEE Computer Society, 2004, pp. 182-189.
[11] T. Hagras, and J. Janecek, A High Performance, Low Complexity Algorithm for Compile-TimeTask Scheduling in Heterogeneous Systems, Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, 2004, pp. 107.
[12] T. Hagras, and J. Janecek, A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems, Proceedings of the Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, IEEE Computer Society, 2004, pp. 106-113.
[13] T. Hagras, and J. Janecek, A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems. Parallel Computing 31 (2005) 653-670.
[14] H.P. Hofstee, Introduction to the Cell Broadband Engine, IBM Corporation, , 2005.
[15] H.P. Hofstee, Power Efficient Processor Architecture and The Cell Processor, High-Performance Computer Architecture, 2005. HPCA-11. 11th International Symposium on, 2005, pp. 258-262.
[16] J.-J. Hwang, Y.-C. Chow, F.D. Anger, and C.-Y. Lee, Scheduling Precedence Graphs in Systems with Interprocessor Communication Times. SIAM Journal on Computing 18 (1989) 244-257.
[17] E. Ilavarasan, P. Thambidurai, and R. Mahilmannan, Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System, Parallel and Distributed Computing, 2005. ISPDC 2005. The 4th International Symposium on, 2005, pp. 28-38.
[18] L. Jing-chiou, and A.P. Michael, An Efficient Task Clustering Heuristic for Scheduling DAGs on Multiprocessors, Proc. Symp. Parallel and Distributed Processing, 1996.
[19] B. Kruatrachue, and T. Lewis, Grain Size Determination for Parallel Processing. Software, IEEE 5 (1988) 23-32.
[20] J. Kurzak, and J. Dongarra, QR factorization for the Cell Broadband Engine. Sci. Program. 17 (2009) 31-42.
[21] J. Kurzak, H. Ltaief, J. Dongarra, and R.M. Badia, Scheduling dense linear algebra operations on multicore processors. Concurr. Comput. : Pract. Exper. 22 (2010) 15-44.
[22] G.Q. Liu, K.L. Poh, and M. Xie, Iterative list scheduling for heterogeneous computing. Journal of Parallel and Distributed Computing 65 (2005) 654-665.
[23] J.P. Perez, P. Bellens, R.M. Badia, and J. Labarta, CellSs: Making It Easier to Program the Cell Broadband Engine Processor. IBM J. Res. Dev. 51 (2007) 593-604.
[24] B. Rashmi, and D.P. Agrawal, Improving Scheduling of Tasks in a Heterogeneous Environment. IEEE Transactions on Parallel and Distributed Systems 15 (2004) 107-118.
[25] Z. Shi, and J.J. Dongarra, Scheduling workflow applications on processors with different capabilities. Future Generation Computer Systems 22 (2006) 665-675.
[26] G.C. Sih, and E.A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures. Parallel and Distributed Systems, IEEE Transactions on 4 (1993) 175-187.
[27] X. Tang, K. Li, G. Liao, and R. Li, List scheduling with duplication for heterogeneous computing systems. Journal of Parallel and Distributed Computing 70 (2010) 323-329.
[28] H. Topcuoglu, S. Hariri, and W. Min-You, Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on 13 (2002) 260-274.
[29] H. Topcuoglu, S. Hariri, and M. Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Transactions on Parallel and Distributed Systems 13 (2002) 260-274.
[30] M.Y. Wu, and D.D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems. Parallel and Distributed Systems, IEEE Transactions on 1 (1990) 330-343.
[31] C.-H. Yang, P. Lee, and Y.-C. Chung, Improving Static Task Scheduling in Heterogeneous and Homogeneous Computing Systems, Parallel Processing, 2007. ICPP 2007. International Conference on, 2007, pp. 45-45.
[32] T. Yang, and A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors. IEEE Trans. Parallel Distrib. Syst. 5 (1994) 951-967.
[33] C. Yeh-Ching, and S. Ranka, Applications and Performance Analysis of a Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed Memory Multiprocessors, Supercomputing '92. Proceedings, 1992, pp. 512-521.
[34] K. Yu-Kwong, and I. Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors Parallel and Distributed Systems, IEEE Transactions on 7 (1996) 506-521.
[35] J.-Y.C. Zhong-Ho Chen, Alvin Su ,Ce-Kuen Shieh and Ta-Chun Chen, Exploiting Parallelism of MPEG-4 Decoder with Dataflow Programming on Multicore Processor, International Symposium on Parallel and Distributed Processing with Applications (ISPA10), Taipei, Taiwan, 2010.