跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/02 22:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林建豪
研究生(外文):Chien-Hao Lin
論文名稱:相依性平行工作排班之研究
論文名稱(外文):A Study of Parallel Jobs Scheduling with Dependence
指導教授:蔡英德蔡英德引用關係陳武林陳武林引用關係
指導教授(外文):Yin-Te TsaiWu-Lin Chen
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊管理學系研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2008
畢業學年度:97
語文別:中文
論文頁數:45
中文關鍵詞:相依性工作排程叢集電腦拓樸排序
外文關鍵詞:ClusterJob schedulingDdependenceTopological sortMakespan
相關次數:
  • 被引用被引用:1
  • 點閱點閱:258
  • 評分評分:
  • 下載下載:47
  • 收藏至我的研究室書目清單書目收藏:0
隨著電腦科技的發展,叢集電腦漸漸變成高效能電腦的趨勢,當需要執行大量運算的應用程式時,叢集電腦分工往往會比昂貴的超級電腦要符合經濟效益,各式各樣的工作的排程方法也因此而產生。在先前的研究中,較簡單的排班法像是FCFS (First-Come-First-Service, FCFS),未能有效的運用系統資源以及縮短系統執行時間,為了解決這些問題,發展出一些工作的排程方法,像是注重space-sharing的回填法則 (backfilling)以及time-sharing的Gang Scheduling 方法。

因為先前的工作排程研究比較少考量到工作之間的相依性,因此我們的研究也就著重於工作之間先後關係的考量,也就是說我們針對每兩個工作之間可能存在著先後關係,來進行排程。本研究提出工作先後順序的一相依性回填排程策略,且同時符合工作之間的相依性,來達到有效運用系統資源以及縮短系統執行時間的效果,我們將工作先後順序以一有向無迴圈圖來表示,然而在所有符合工作先後順序的拓樸排序中,會存在一相依性回填排程makespan最短的排列順序,因此在拓樸排序過程中,當圖中有兩個以上頂點的indegree為0時,我們以頂點的outdegree數目來決定拓樸排序一輸出的先後順序,我們分別以outdegree的最大值、最小值、以及隨機值跟所有拓樸排序作相依性回填排程後的最小值做個比較,發現當以outdegree最大值為優先輸出的拓樸排序,其相依性回填排程後的makespan,會比較接近所有拓樸排序去做相依性回填排程所得到makespan的最小值。
With the development of computer technology, clusters have become one of the trends in high performance computing. When large-scale jobs are to be executed, clusters usually have better performance than super computers, various types of scheduling policies have been implemented. In previous studies, simple batch scheduling algorithms like First Come First Serve (FCFS) may waste waiting time when longer jobs run, and system utilization is lower. In order to solve the problems, the space-sharing policy like backfill and the time-sharing policy like Gang scheduling have been provided to improve system utilization , and to overcome the problem of response time.
Generally, most of jobs scheduling policies focus on time-sharing and space-sharing. In our study, we discuss the dependent jobs. There may be a relation that some jobs must have to be executed before the other. In order to schedule those jobs in parallel system, we provide a policy with the backfill strategy to schedule dependent jobs to decrease total execution times. We use a directed acyclic graph to express the dependence between jobs. There must be one of topological sequences that can be scheduled with backfill strategy and the makespan is minimum. We call it the smallest topological sequence. When topological sort begins, if the number of vertex’s indegree is 0, the vertex will be outputted. If there are over one vertexes whose indegree is 0, the one which will be outputted dependent on their outdegree numbers. First, we decide the vertex with maximal outdegrees will be outputted first . The result is called maximum outdegree topological sort. Second, we decide the vertex with minimal outdegrees will be outputted first. The result is called minimum outdegree topological sort. Third, we output vertex randomly and the result is named random outdegree topological sort. Then, we schedule the three topological sequences by the backfill strategy. Finally, we find that the makespan of the maximum outdegree topological sequence is very close to the makespan of the smallest topological sequence.
中文摘要 ……………………………………………………………………… I
英文摘要 ……………………………………………………………………… II
誌謝 ……………………………………………………………………… III
目錄 ……………………………………………………………………… IV
表目錄 ……………………………………………………………………… V
圖目錄 ……………………………………………………………………… VI
第一章、 緒論 ……………………………………………………………… 1
1.1 研究背景 ………………………………………………………… 1
1.2 研究動機與目的…………………………………………………… 1
1.3 研究流程 ………………………………………………………… 2
1.4 論文架構 ………………………………………………………… 4
第二章、 文獻探討 ………………………………………………………… 5
2.1 叢集電腦 ………………………………………………………… 5
2.2 拓樸排序 ………………………………………………………… 7
2.3 平行工作排程 …………………………………………………… 10
第三章、 研究方法…………………………………………………………… 15
3.1 研究架構 ………………………………………………………… 15
3.2 相依性aggressive backfill排程法 ………………………… 16
3.3 三種拓樸排序法 ………………………………………………… 18
第四章、 實驗方法與結果 ………………………………………………… 20
4.1 實驗方法與設計 ………………………………………………… 20
4.2 實驗結果與分析 ………………………………………………… 20
第五章、 結論與建議………………………………………………………… 42
5.1 研究結論 ………………………………………………………… 42
5.2 後續研究與建議…………………………………………………… 43
參考文獻 ……………………………………………………………………… 45
[1] Zhang, Y., H. Franke, J. Moreira,. and A. Sivasubramaniam, “An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration”, IEEE Transactions on Parallel and Distributed Systems. VOL. 14, NO. 3, pp. 236-247, March 2003.
[2] Srinivasan, S., R. Kettimuthu, V. Subramani, and P. Sadayappan, “Characterization of Backfilling Strategies for Parallel Job Scheduling”, In proceedings of IEEE International Conference on Parallel Processing Workshops, pp. 514-519, 2002.
[3] Tomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.
[4] Dror G. Feitelson, Larry Rudolph, “Parallel Job Scheduling --- A Status Report”, 10th Workshop on Job Scheduling Strategies for Parallel Processing, pp. 1-16, June 2004.
[5] Hassan Rajaei, Mohammad Dadfar, Pankaj Joshi, “SIMULATION OF JOB SCHEDULING FOR SMALL SCALE CLUSTERS”, IEEE Proceedings of the 2006 Winter Simulation Conference, pp.1195-1200, 2006
[6] Dror Feitelson and A.M. Weil, “Utilization, predicatibility, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling’’, IEEE Transactions onParallel and Distributed Systems, volume 12, issue 6, pp. 529-543, June 2001.
[7] H. Franke, P. Pattnaik, and L. Rudolph, “Gang Scheduling for Highly Efficient Multiprocessors,” Six Symp. Fronties of Massively Parallel Computation,1996.
[8] U. Schwiegelshohn and R. Yahyapour, “Improving Fiest-Come-First-Serve Job Schedulling by Gang Scheduling,” Int’l Parallel and Distributed Processing Symp. Work shop Scheduling Strategies for Parallel Processing, Mar. 1998.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top