臺灣博碩士論文加值系統

雲端計算為現今重要的科技之一，應用範圍極廣，而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.