跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/28 18:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:徐君毅
研究生(外文):Jun-YiHsu
論文名稱:雲端計算環境中映射化簡模式之公平資源分配節能工作排程法
論文名稱(外文):A Job Scheduling of Fair Resource Allocation with Energy-Saving for MapReduce Architecture in Cloud Computing
指導教授:朱治平朱治平引用關係
指導教授(外文):Chih-Ping Chu
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:63
中文關鍵詞:雲端計算映射還原工作排程節能排程
外文關鍵詞:Cloud ComputingMapReduceJob SchedulingEnergy-Saving Scheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:166
  • 評分評分:
  • 下載下載:3
  • 收藏至我的研究室書目清單書目收藏:1
雲端計算為現今重要的科技之一,應用範圍極廣,而hadoop為雲端計算中最常使用之平台,於hadoop核心中,工作排程之方法為公平排程,此法易於實現並能公平分配環境中之各項工作,但未考慮節能的概念並和最佳解有段差距,若能在雲端計算環境中亦加上節能的概念,將能獲得更大的利益。

於本篇文章中,將映射還原之模式映射到數學模型中,並以線性規劃的方法尋求資源分配的組合,但以線性規劃的方式尋求資源分配的組合,其時間複雜度為指數成長,因此提出一演算法來取得資源分配的組合以降低時間複雜度。於異質環境中,同一工作中各資源執行工作時間相異卻需於同時結束以便彙整計算結果,其差異將使擁有較佳運算能力之資源閒置,若此時調降較佳資源運算時脈延長運算時間不會影響任務完成之時間,但卻能有效降低能源消耗。在on-line的環境中並不能夠得知工作進來的時間,因此只能調整運算時脈以便降低耗能,但若能調整I/O裝置能省下更多能源,因此在已知工作到達時間的情形下,可使用on-line排程演算法來調整I/O裝置之運作,以期能夠降低更多能源消耗。實驗結果顯示本篇文章提出的方法能夠有效的降低完成時間以及所耗能源。
Cloud computing is one of the most important technological and has a broad range of application. Hadoop is most commonly used in the cloud computing platform. The method of the task scheduler is fairly scheduling at hadoop. Fairly scheduling is easy to implement and distribute tasks fairly in the work environment, but has a multiplicative gap from optimal assignment. On the other hand, the method does not consider about the concept of energy saving. If adding the concept of energy saving in cloud computing, we will be able to gain some benefits.

We map the scheduling model of cloud computing into a mathematical model in this thesis, and then find an assignment based on linear programming. However, such an assignment process causes a long, exponential complexity of time, we thus propose an algorithm which is polynomial time for obtaining the assignment. On the other hand, if the resources are distinct in the environment, the execution time for each resource is different but the completion time is same because of the same task. The situation results that the better resource idles. We are able to reduce the clock rate for extending execution time and do not affect the overall time, but it is able to save energy. Since we do not know when the tasks come for on-line scheduling, so we are only able to reduce the clock rate for energy-saving. If we are able to control the state for I/O device, the more energy consumption is reducing, so we present an I/O device scheduling algorithm for reducing more energy consumption when the arrival time of tasks is known. The experiment result shows the function of our proposed strategy is better than that of Hadoop on the completion time and energy consumption.
摘要 i
Abstract ii
Acknowledgement iv
Contents v
List of Figures vi
Chapter 1 Introduction 1
Chapter 2 Cloud Computing Work 4
2.1 Cloud Computing Platform 4
2.2 The MapReduce Framework 13
Chapter 3 Algorithm for Resource Allocation 22
3.1 Computing Architecture 22
3.2 New Architecture 25
Chapter 4 Scheduling for Energy Reducing 31
4.1 Adjust Voltage of Resource 31
4.2 Adjust I/O Mode of Resource 35
Chapter 5 Experiment 43
5.1 Experimental Environment 43
5.2 Experimental Results 43
Chapter 6 Conclusions and Future Work 58
6.1 Conclusions 58
6.2 Future Work 59
References 60
[1]J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, vol. 51, pp. 107-113, 2008.
[2]M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, and I. Stoica, Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling, presented at the Proceedings of the 5th European conference on Computer systems, Paris, France, 2010.
[3]E. Bortnikov, Open-source grid technologies for web-scale computing, ACM SIGACT News, vol. 40, pp. 87-93, 2009.
[4]C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis, Evaluating mapreduce for multi-core and multiprocessor systems, in Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, 2007, pp. 13-24.
[5]M. K. K. Sankaralingam, MapReduce for the Cell BE Architecture, University of Wisconsin Computer Sciences Technical Report, 2007.
[6]B. He, W. Fang, Q. Luo, N. K. Govindaraju, and T. Wang, Mars: a MapReduce framework on graphics processors, in Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, 2008, pp. 260-269.
[7]G. Bell, J. Gray, and A. Szalay, Petascale computational systems, IEEE Computer, vol. 39, pp. 110-112, 2006.
[8]Y. El-khatib and C. Edwards, A survey-based study of grid traffic, in GridNets, 2007, pp. 4:1-4:8.
[9]D. M. Batista, L. J. Chaves, N. L. S. da Fonseca, and A. Ziviani, Performance analysis of available bandwidth estimation tools for grid networks, The Journal of Supercomputing, vol. 53, pp. 103-121, 2010.
[10]A. Fox and R. Griffith, Above the clouds: A Berkeley view of cloud computing, Dept. Electrical Eng. and Comput. Sciences, University of California, Berkeley, Rep. UCB/EECS, vol. 28, 2009.
[11]L. M. Vaquero, L. Rodero-Merino, J. Caceres, and M. Lindner, A break in the clouds: towards a cloud definition, SIGCOMM Comput. Commun. Rev., vol. 39, pp. 50-55, 2008.
[12]J. Staten, S. Yates, F. E. Gillett, W. Saleh, and R. A. Dines, Is cloud computing ready for the enterprise, Forrester Research, March, vol. 7, 2008.
[13]P. M. a. T. Grance, Definition of cloud computing, Technical report, National Institute of Standard and Technology (NIST), July 2009.
[14]D. F. Parkhill, The challenge of the computer utility: Addison-Wesley Reading, MA, 1966.
[15]L. C. Q. Zhang, and R. Boutaba, Cloud computing: state-of-theart and research challenges, J. Internet Services and Applications, 2010.
[16]I. W. Habib, Q. Song, Z. Li, and N. S. V. Rao, Deployment of the GMPLS control plane for grid applications in experimental high-performance networks, Communications Magazine, IEEE, vol. 44, pp. 65-73, 2006.
[17]T. Lehman, J. Sobieski, and B. Jabbari, DRAGON: a framework for service provisioning in heterogeneous grid networks, Communications Magazine, IEEE, vol. 44, pp. 84-90, 2006.
[18]W. Guo, W. Sun, Y. Jin, W. Hu, and C. Qiao, Demonstration of joint resource scheduling in an optical network integrated computing environment [topics in optical communications], Communications Magazine, IEEE, vol. 48, pp. 76-83, 2010.
[19]I. Foster, Y. Zhao, I. Raicu, and S. Lu, Cloud computing and grid computing 360-degree compared, in Grid Computing Environments Workshop, 2008, pp. 1-10.
[20]D. Batista and N. da Fonseca, A survey of self-adaptive grids, Communications Magazine, IEEE, vol. 48, pp. 94-100, 2010.
[21]H.-c. Yang, A. Dasdan, R.-L. Hsiao, and D. S. Parker, Map-reduce-merge: simplified relational data processing on large clusters, in Proceedings of the 2007 ACM SIGMOD international conference on Management of data, 2007, pp. 1029-1040.
[22]M. Stonebraker, The case for shared nothing, Database Engineering Bulletin, vol. 9, pp. 4-9, 1986.
[23]J. Dean and S. Ghemawat, MapReduce: a flexible data processing tool, Commun. ACM, vol. 53, pp. 72-77, 2010.
[24]T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy, and R. Sears, MapReduce online, presented at the Proceedings of the 7th USENIX conference on Networked systems design and implementation, San Jose, California, 2010.
[25]Y. Gu and R. L. Grossman, Lessons learned from a year's worth of benchmarks of large data clouds, presented at the Proceedings of the 2nd Workshop on Many-Task Computing on Grids and Supercomputers, Portland, Oregon, 2009.
[26]H. W. Kuhn, The Hungarian method for the assignment problem, Naval research logistics quarterly, vol. 2, pp. 83-97, 1955.
[27]R. Burkard, Assignment problems: Recent solution methods and applications, System Modelling and Optimization, pp. 153-169, 1986.
[28]D. S. Johnson and M. R. Garey, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman&Co, San Francisco, 1979.
[29]R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, vol. 45, pp. 1563-1581, 1966.
[30]R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics, vol. 17, pp. 416-429, 1969.
[31]J. K. Lenstra, D. B. Shmoys, and E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical programming, vol. 46, pp. 259-271, 1990.
[32]J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), vol. 44, pp. 486-504, 1997.
[33]K. Birman, G. Chockler, and R. van Renesse, Toward a cloud computing research agenda, SIGACT News, vol. 40, pp. 68-80, 2009.
[34]M. Zaharia, A. Konwinski, A. D. Joseph, R. Katz, and I. Stoica, Improving mapreduce performance in heterogeneous environments, 2008, pp. 29-42.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊