請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46014完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 劉邦鋒(Pangfeng Liu) | |
| dc.contributor.author | Chih-Wei Weng | en |
| dc.contributor.author | 翁志瑋 | zh_TW |
| dc.date.accessioned | 2021-06-15T04:51:20Z | - |
| dc.date.available | 2012-08-05 | |
| dc.date.copyright | 2010-08-05 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-08-02 | |
| dc.identifier.citation | [1] Folding@home. http://folding.stanford.edu/.
[2] Lcg: Lhc computing grid. http://lcg.web.cern.ch/LCG/. [3] Birn: The biomedical informatics research network. http://www.nbirn.net/. [4] H. Casanova, G. Obertelli, F. Berman, and R. Wolski. The apples parameter sweep template: user-level middleware for the grid. In Proceedings of the ACM/IEEE conference on Supercomputing, pages 75–76, 2000. [5] Mapreduce. http://www.google.com/. [6] Storage resource broker. http://www.sdsc.edu/srb/. [7] Globus toolkit. http://www.globus.org/toolkit/. [8] Taiwan unigrid. http://www.unigrid.org.tw/. [9] J. D. Ullman. Np-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384–393, 1975. [10] 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. [11] T. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen, and R. Freund. A comparison 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. [12] C. Chekuri, R. Motwani, B. Natarajan, and C. Stien. Approximation techniques for average completion time scheduling. In SODA, pages 609–618, 1997. [13] L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In SODA, pages 142–151, 1996. [14] N.N. Pisaruk. A fully combinatorial 2-approximation algorithm for precedenceconstrained scheduling a single machine to minimize average weighted completion time. Discrete Appl. Math., 131(3):655–663, 2003. [15] M. Scharbrodt, T. Schickinger, and A. Steger. A new average case analysis for completion time scheduling. J. ACM, 53(1):121–146, 2006. [16] G.J Woeginger. On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math., 131(1):237–252, 2003. [17] Y. Guan,W. Xiao, R. K. Cheung, and C. Li. A multiprocessor task schedulingmodel for berth allocation: heuristic and worst-case analysis. Operations Research Letters, 30(5):343–350, 2002. [18] W. Lee, C. Wu, Y. Chung, and H. Liu. Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates. Comput. Oper. Res., 36(6):2111–2121, 2009. [19] M. Liu, C. Chu, Y. Xu, and F. Zheng. Online scheduling on m uniform machines to minimize total (weighted) completion time. Theor. Comput. Sci., 410(38-40):3875– 3881, 2009. [20] L. Su and Y. Lee. The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time. Comput. Oper. Res., 35(9):2952– 2963, 2008. [21] S. Albers. Better bounds for online scheduling. In STOC, pages 130–139, 1997. [22] M. Dell’Amico,M. Iori, and S. Martello. Heuristic algorithms and scatter search for the cardinality constrained p | |
| dc.identifier.citation | cmax problem. Journal of Heuristics, 10(2):169–204,
2004. [23] R. Fu, J. Tian, and J. Yuan. On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs. J. of Scheduling, 12(1):91– 97, 2009. [24] M. R. Garey and R. L. Graham. Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4(2):187–200, 1975. [25] E. Naroska and U. Schwiegelshohn. On an on-line scheduling problem for parallel jobs. Information Processing Letters, 81(6):297–304, 2002. [26] 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. [27] H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman. Using simulation to evaluate scheduling heuristics for a class of applications in grid environments. Technical Report RR-1999-46, LIP, ENS, 1999. [28] H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman. Heuristics for scheduling parameter sweep applications in grid environments. In Proceedings of Heterogeneous Computing Workshop, pages 349–363, 2000. [29] C. Chen, C. Hsu, J.Wu, and P. Liu. Gfs: A distributed file system with multi-source data access and replication for grid computing. In GPC ’09: Proceedings of the 4th International Conference on Advances in Grid and Pervasive Computing, pages 119–130, Berlin, Heidelberg, 2009. Springer-Verlag. [30] F. Garc´ıa, A. Calder´on, J. Carretero, J. P´erez, and J. Fern´andez. An expandable parallel file system using nfs servers. In VECPAR’02: Proceedings of the 5th international conference on High performance computing for computational science, pages 565–578, Berlin, Heidelberg, 2003. Springer-Verlag. [31] M. Burger, T. Kielmann, and H. Bal. Balanced multicasting: High-throughput communication for grid applications. In SC ’05: Proceedings of the 2005 ACM/IEEE conference on Supercomputing, page 46, Washington, DC, USA, 2005. IEEE Computer Society. [32] C. Wang, C. Hsu, H. Chen, and J. Wu. Efficient multi-source data transfer in data grids. In CCGRID ’06: Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid, pages 421–424, Washington, DC, USA, 2006. IEEE Computer Society. [33] J. Zhang, B. Lee, X. Tang, and C. Yeo. Impact of parallel download on job scheduling in data grid environment. In GCC ’08: Proceedings of the 2008 Seventh International Conference on Grid and Cooperative Computing, pages 102–109, Washington, DC, USA, 2008. IEEE Computer Society. [34] A. Amoroso and K. Marzullo. Multiple job scheduling in a connection-limited data parallel system. IEEE Trans. Parallel Distrib. Syst., 17(2):125–134, 2006. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46014 | - |
| dc.description.abstract | This paper proposes a heuristic scheduling algorithm that considers job execution time
and data transfer time while scheduling jobs in distributed systems, and studies the overall effect under single-source and multi-source data transfer strategy. The experimental results indicate that multi-source data transfer strategy is an useful technique to improve data transfer efficiency and therefore ca reduce the makespan on each computing node in distributed systems. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T04:51:20Z (GMT). No. of bitstreams: 1 ntu-99-R97922132-1.pdf: 514672 bytes, checksum: ce2979f47ac0594a5164cd97c11e832b (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | Certification i
Acknowledgement ii Chinese Abstract iii Abstract iv 1 Introduction 1 2 RelatedWorks 3 3 System Model 5 3.1 Jobs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.4 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.5 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4 Algorithm 9 4.1 Estimated Data Available Time . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 Estimated Job Ready Time . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Estimated Job Completion Time . . . . . . . . . . . . . . . . . . . . . . 11 4.4 Job Selection and Assignment . . . . . . . . . . . . . . . . . . . . . . . 11 4.5 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Experiment 14 5.1 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.1.1 System Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.1.2 Job Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.1.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1.4 Lower Bound Comparison . . . . . . . . . . . . . . . . . . . . . 17 5.2 Real System Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2.1 Real Job Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2.2 Real System Configuration . . . . . . . . . . . . . . . . . . . . . 20 5.2.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 20 6 Conclusion 24 Bibliography 25 | |
| dc.language.iso | en | |
| dc.subject | 分散式系統 | zh_TW |
| dc.subject | 啟發式演算法 | zh_TW |
| dc.subject | NP完備 | zh_TW |
| dc.subject | 完工時間 | zh_TW |
| dc.subject | 排程 | zh_TW |
| dc.subject | 多點傳輸 | zh_TW |
| dc.title | 分散式系統下之多點資料傳輸排程 | zh_TW |
| dc.title | Multi-source data aware scheduling in distributed systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王大為(Da-wei Wang),吳真貞(Jan-Jan Wu) | |
| dc.subject.keyword | 分散式系統,多點傳輸,排程,完工時間,NP完備,啟發式演算法, | zh_TW |
| dc.subject.keyword | distributed system,schedule,makespan,greedy heuristic,NP-complete, | en |
| dc.relation.page | 27 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-08-02 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf 未授權公開取用 | 502.61 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。