臺灣博碩士論文加值系統

在網格計算環境下，執行有效率的工作排程來增進整體系統效能是非常重要的。為了解決網路頻寬與大量的數據計算的工作排程問題，透過主從式架構應用於網格計算平台設計一個有效率的演算法，並且期望擁有最佳效能已經成為一個重要的課題。在本論文中，我們設計的演算法改善了過去在主從式架構下異質性計算的工作排程方法，有別於先前同質性的傳輸頻寬，新的演算法主要考量異質性的網路頻寬來進行模擬，以利應用於網格計算環境下工作排程的改善。演算法的主要排程步驟是針對工作執行時間與工作傳輸時間的比例做排序，分散與減少處理器閒置時間，讓處理器提早執行運算。為了評估所提出演算法的效能，我們實作了Smallest Communication Ratio (SCR) 方法，與Beaumont的演算法。實驗數據顯示SCR有三個優點；一、縮短單一工作執行的平均時間，二、提高系統整體的執行產能，三、提高處理器使用效率與減少處理器的閒置時間。整體而言，SCR演算法可以縮短工作執行時間，其主要原因歸於該演算法讓整體系統的等待時間與閒置時間縮短。

Efficient task scheduling is an important issue to system performance in computational grid. To investigate this problem, the master slave paradigm is a good vehicle for developing tasking technologies of centralized grid system. In this thesis, we extend and improve Beaumont’s scheduling strategies for dispatching tasks to heterogeneous processors in master slave environment. The main extension of this study is the consideration of heterogeneous communication overheads in grid system. One significant improvement of our approach is that average turnaround time could be minimized. The other advantage of the proposed method is that system throughput can be increased by dispersing processor idle time. Our proposed model can be applied on heterogeneous cluster systems within a grid environment in which the communication costs are various from clusters. To evaluate performance of the proposed techniques, we have implemented the proposed algorithms along with Beaumont’s method. The experimental results show that our techniques outperform Beaumont’s algorithm in terms of lower average turnaround time, higher average throughput, less processor idle time and higher processors’ utilization.

Chinese Abstract I
English Abstract II
Acknowledgements III
Table of Contents IV
List of Figures V
1 Introduction
2 Related Work
3 Preliminaries
3.1 Research Architecture
3.2 Definitions
3.3 Master Slave Task Scheduling
4 The Smallest Communication Ratio (SCR) Scheduling with Identical
Communication
4.1 Scheduling Without Processor Idle
4.2 Scheduling With Dispersed Processor Idle
5 Smallest Communication Ratio (SCR) Scheduling with Heterogeneous Communication
5.1 Scheduling Without Processor Idle
5.2 Scheduling With Dispersed Processor Idle
6 Performance Evaluation
6.1 Simulation Results for HPIC
6.2 Simulation Results for HPHC
6.3 Miscellaneous Comparison
7 Conclusions and Future Work
Reference

[1]Oliver Beaumont, Arnaud Legrand and Yves Robert, “The Master-Slave Paradigm with Heterogeneous Processors,” IEEE Trans. on parallel and distributed systems, Vol. 14, No.9, pp. 897-908, September 2003.
[2]Olivier Beaumont, Cyril Banino, Larry Carter, Fellow, Jeanne Ferrante, Senior Member, Arnaud Legrand and Yves Robert, ”Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms,” IEEE Trans. on parallel and distributed systems, Vol. 15, No.4, pp.319-330, April 2004.
[3]Oliver Beaumont, Arnaud Legrand and Yves Robert, “Pipelining Broadcasts on Heterogeneous Platforms,” IEEE Trans. on parallel and distributed systems, Vol. 16, No.4, pp. 300-313 April 2005.
[4]Oliver Beaumont, V. Boudet, A. Petitet, F. Rastello and Y. Robert, “A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers),” IEEE Trans. Computers, Vol. 50, No. 10, pp. 1052-1070, Oct. 2001.
[5]Oliver Beaumont, V. Boudet, F. Rastello and Y. Robert, “Matrix-Matrix Multiplication on Heterogeneous Platforms,” Proc. Int'l Conf. Parallel Processing, Vol. 12, No. 10, pp. 1033-1051, Oct. 2001.
[6]Francine Berman, Richard Wolski, Hernri Casanova, Walfredo Cirne, Holly Dail, Marcio Faerman, Silvia Figueira, Jim Hayes, Graziano Obertelli, Jennifer Schopf, Gary Shao, Shava Smallen, Neil Spring, Alan Su, and Dmitrii Zagorodnov, ”Adaptive Computing on the Grid Using AppLeS,” IEEE Trans. on parallel and distributed systems, Vol. 14, No. 4, pp.369-379, April 2003.
[7]S. Bataineh, T.Y. Hsiung and T.G. Robertazzi, “Closed Form Solutions for Bus and Tree Networks of Processors Load Sharing a Divisible Job,” IEEE Trans. Computers, Vol. 43, No. 10, pp. 1184-1196, Oct. 1994.
[8]T. D. Braun, H. J. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys and B. Yao, “A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems,” Proceedings of the IEEE Workshop on Advances in Parallel and Distributed Systems, pp. 330-335, Oct. 1998.
[9]A.T. Chronopoulos and S. Jagannathan, “A Distributed Discrete-Time Neural Network Architecture for Pattern Allocation and Control,” Proc. IPDPS Workshop Bioinspired Solutions to Parallel Processing Problems, pp.15-19, Apr. 2002.
[10]S. Charcranoon, T.G. Robertazzi and S. Luryi, “Optimizing Computing Costs Using Divisible Load Analysis,” IEEE Trans. Computers, Vol. 49, No. 9, pp. 987-991, Sept. 2000.
[11]K. Cooper, A. Dasgupta, K. Kennedy, C. Koelbel, A. Mandal, G. Marin, M. Mazina, J. Mellor-Crummey, F. Berman, H. Casanova, A. Chien, H. Dail, X. Liu, A. Olugbile, O. Sievert, H. Xia, L. Johnsson, B. Liu, M. Patel, D. Reed, W. Deng, C. Mendes, Z. Shi, A. YarKhan, J. Dongarra, ”New Grid Scheduling and Rescheduling Methods in the GrADS Project,” Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), pp.209-229, April 2004..
[12]Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov and Francine Berman, “Heuristics for Scheduling Parameter Sweep applications in Grid environments,” Proceedings of the 9th Heterogeneous Computing workshop (HCW'2000), pp. 349-363, 2000.
[13]Atakan Dogan, Fusun Ozguner, ”Matching and Scheduling Algorithms for Failure Probability of Applications in Heterogeneous Computing,” IEEE Trans. on parallel and distributed systems, Vol. 13, No. 3, pp. 308-323, March 2002.
[14]Ching-Chin Han, Kang G. Shin, Jian Wu, ”A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults,” IEEE Trans. on computers, Vol. 52, No. 3, pp.362-372, March 2003.
[15]Tarek Hagras, Jan 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), pp. 653-670, 2004.
[16]Jennifer M. Schopf, “A General Architecture for Scheduling on the Grid,” TR-ANL/MCS-P1000-1002, special issue of JPDC on Grid Computing, April, 2002.
[17]Rui Min and Muthucumaru Maheswaran, “Scheduling Co-Reservations with priorities in grid computing systems,” Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID’02), pp. 250-251, May 2002.
[18]M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen and R. Freund, ``Dynamic mapping of a class of independent tasks onto heterogeneous computing systems,'' Proceeding of the 8th IEEE Heterogeneous Computing Workshop (HCW '99), pp. 30-44, April 1999.
[19]Muhammad K. Dhodhi, Imtiaz Ahmad Anwar Yatama, Anwar Yatama and Ishfaq Ahmad, “An integrated technique for task matching and scheduling onto distributed heterogeneous computing systems,” Journal of Parallel and DistributedComputing, Vol. 62, No. 9, pp. 1338–1361, 2002.
[20]Santhanam Srinivasan and Niraj K. Jha, “Safety and reliability driven task scheduling allocation in distributed systems,” IEEE Trans. on parallel and distributed systems, Vol. 10, No. 3, pp. 238-251, March 1999.
[21]Thyagaraj Thanalapati and Sivarama Dandamudi, ”An Efficient Adaptive Scheduling Scheme for Distributed Memory Multicomputers,” IEEE Trans. on parallel and distributed systems, Vol. 12, No. 7, pp.758-767, July 2001.