請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41607
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 劉邦鋒(Pangfeng Liu) | |
dc.contributor.author | Wei-Cheng Liao | en |
dc.contributor.author | 廖尉呈 | zh_TW |
dc.date.accessioned | 2021-06-15T00:24:37Z | - |
dc.date.available | 2009-02-10 | |
dc.date.copyright | 2009-02-10 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-01-23 | |
dc.identifier.citation | [1] S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman. Basic
local alignment search tool. Journal of Molecular Biology, 215(3):403– 410, 1990. [2] O. Beaumont, A. Legrand, L. Marchal, and Y. Robert. Pipelining broad- casts on heterogeneous platforms. IEEE Transactions on Parallel and Distributed Systems, 16(4):300–313, 2005. [3] BIRN: The Biomedical Informatics Research Network. http://www.nbirn.net/. [4] T. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen, and R. Freund. A compar- ison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810–837, 2001. [5] C. Hsu C. Chen, J. Wu, and P. Liu. Gfs: A distributed file system with multi-source data access and replication for grid computing. In The 5th Workshop on Grid Technologies and Applications, 2008. [6] H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman. Heuristics for scheduling parameter sweep applications in grid environments. In Pro- ceedings of Heterogeneous Computing Workshop, pages 349–363, 2000. [7] H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman. Using simu- lation to evaluate scheduling heuristics for a class of applications in grid environments. Technical Report RR-1999-46, LIP, ENS, 2000. [8] H. Casanova, G. Obertelli, F. Berman, and R. Wolski. The apples pa- rameter sweep template: user-level middleware for the grid. In Pro- ceedings of the ACM/IEEE conference on Supercomputing, pages 75–76, 2000. [9] A. Chakrabarti, R.A. Dheepak, and S. Sengupta. Integration of schedul- ing and replication in data grids. In International Conference on High Performance Computing 2004, pages 375–385, 2004. [10] F. Desprez and A. Vernois. Simultaneous scheduling of replication and computation for data-intensive applications on the grid. Journal of Grid Computing, 4(1):19–31, 2006. [11] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman and Co. New York, NY, USA., 1979. [12] Globus Toolkit. http://www.globus.org/toolkit/. [13] LCG: LHC Computing Grid. http://lcg.web.cern.ch/LCG/. [14] K. Ranganathan and I. Foster. Simulation studies of computation and data scheduling algorithms for data grids. Journal of Grid Computing, 1:53–62(10), 2003. [15] Storage Resource Broker. http://www.sdsc.edu/srb/. [16] Taiwan Unigrid. http://www.unigrid.org.tw/. [17] M. Tang, B. Lee, X. Tang, and C. Yeo. Combining data replication algorithms and job scheduling heuristics in the data grid. In 11th Inter- national Euro-Par Conference, pages 381–390, 2005. [18] Ubench. http://www.phystech.com/download/ubench.html. [19] J. D. Ullman. Np-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384–393, 1975. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41607 | - |
dc.description.abstract | 我們提出了一個在格網系統中可以善用獨立工作間的檔案分享及資料複本以提昇效能的排程演算法。這個演算法不只會考量系統運算時間的負載平衡,還會考量檔案及資料複本的存放位置。實驗模擬的結果顯示我們的演算法在各種不同大小規模的系統中皆比隨機選擇演算法的效能表現穩定,並且多數的情況下與理論值的相對效能差異在 50% 之內。模擬的結果也顯示我們的演算法在自行生成的系統參數或是實際量測取得的系統參數下都有良好的效能表現。 | zh_TW |
dc.description.abstract | We proposes a heuristic algorithm that explores the advantage of file sharing and replication while executing independent jobs in a grid environment. The proposed scheduling algorithm not only consider execution time load balancing, but also consider the location of data and replica these jobs require. The simulation results indicate that the proposed algorithm is more scalable than a random heuristic algorithm. In addition, in most cases the relative performance of our heuristic algorithm is within 50% of a conservative theoretical lower bound. The simulation results also indicate that the heuristic performs well in our synthesis environment, as well as in real grid system like Taiwan Unigrid. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T00:24:37Z (GMT). No. of bitstreams: 1 ntu-98-R95922134-1.pdf: 397771 bytes, checksum: 166b61d66c2ea74a20353d28999b8c6d (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | 1 Introduction 1
2 Related Works 4 3 System Model 7 3.1 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . .7 3.2 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 A Scheduling problem . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Heuristic Algorithm 13 4.1 Evaluation of Completion Time of Jobs . . . . . . . . . . . . . 14 4.1.1 Estimated Finish Time . . . . . . . . . . . . . . . . . . 15 4.2 Job Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Experimental Results 21 5.1 Environment Settings . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Reference Metrics for Comparison . . . . . . . . . . . . . . . . 22 5.2.1 Theoretical Lower Bounds . . . . . . . . . . . . . . . . 22 5.2.2 Random Job Selection . . . . . . . . . . . . . . . . . . 24 5.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 24 5.3.1 Synthetic Simulation Parameters . . . . . . . . . . . . 25 5.3.2 Real Grid Parameters . . . . . . . . . . . . . . . . . . 30 6 Conclusions and Future Work 33 Bibliography 35 | |
dc.language.iso | en | |
dc.title | 格網系統中考量資料複製之工作排程方法 | zh_TW |
dc.title | Replica Aware Job Scheduling in Grid Environments | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王大為(Da-Wei Wang),薛智文(Steven C.W. Hsueh) | |
dc.subject.keyword | 格網,排程,複本, | zh_TW |
dc.subject.keyword | grid,scheduling,replication, | en |
dc.relation.page | 37 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-01-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 388.45 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。