一個動態負載平衡之最大可能性估算計算架構

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：7

、訪客IP：3.129.39.55

姓名

吳政暉(Cheng-hui Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

一個動態負載平衡之最大可能性估算計算架構
(A Dynamic Load-Balancing Maximum Likelihood Evaluation Framework)

相關論文

★ 以伸展樹為基礎的Android Binder Driver	★ 應用增量式學習於多種農作物判釋之研究
★ 應用分類重建學習偵測航照圖幅中的新穎坵塊	★ 一個建立在平行工作系統上的動態全球計算平台
★ 用權重參照計數演算法執行主動物件垃圾收集	★ 利用多項系統負載資訊進行動態P2P系統重組的策略研究
★ 基於Hadoop系統的雲端應用程式特徵擷取與計算監測架構	★ 適用於大型動態分散式系統的調適性計算模型
★ 一個提供彈性虛擬資料中心的雲端服務平台	★ 雲端彈性虛擬機房服務平台之資源控管中心
★ 一個適用於自動供應雲端系統的動態調適計算架構	★ 線性相關工作與非相關工作的探索式排程策略
★ 適用於大資料集高效率的分散式階層分群演算法	★ 混合雲端環境上的多重代理人動態調適計算管理架構
★ 基於圖形的平行化最小生成樹分群演算法	★ 基於密度的超立方體覆蓋之啟發式演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

Maximum Likelihood Evaluation (MLE)，是科學家與工程師常用來解決資料分析相關問題的一種方法。為了開發一個分散式的MLE應用程式，科學家與工程師往往需要耗費許多時間與心力去學習分散式程式語言的語法，甚至包括了偵測分散式系統的狀態、動態的調節工作的負載等問題。站在軟體工程的觀點來看，若要發展一個大型的分散式系統軟體，還要分心去設計或偵測系統的組態，這對程式設計師將是一件非常大的負擔，因此非常不利於系統軟體的發展。若是能讓需要使用MLE計算方法的科學家與工程師，在只需要提供最少資訊的情況下就能夠開發出合用的程式，那麼便能大大的降低開發分散式MLE程式的門檻。
本研究利用在高速平行程式上被廣泛使用的Message Passing Interface (MPI) library發展出一個可以動態偵測並調節工作量負載的MLE程式，利用本研究所提出的計算架構，程式設計師可以很快速的建立一個分散式MLE應用程式，不必重複撰寫演算法，也不需要考慮如何讓各節點工作量負載平衡的問題，簡化了分散式科學計算應用程式的發展過程，而且不需要另外安裝任何中介服務軟體便能直接使用。實驗數據顯示，本研究所提出之混和靜態與動態負載平衡的計算架構確實改善了分散式MLE應用程式的效能。

摘要(英)

Many scientific disciplines use maximum likelihood evaluation (MLE) to solve problems. As the data to be analyzed grows with the improvement of observation equipment, MLE demands parallelism to improve analysis efficiency. Unfortunately, it is very hard for scientists and engineers to study distributed programming languages, to learn distributed computing environments, and to develop their own distributed MLE applications. It is even harder to develop an MLE application to monitor the distributed system status and to use the information as feedback to adapt to the computing environment. From the view of software engineering, this is a painstaking task for application developers.
In this thesis, we present a dynamic load-balancing MLE framework. The framework is based on a widely used parallel programming library, the message passing interface (MPI) library. Programmers can easily build their own adaptive distributed MLE applications based on our framework. Our approach does not use any extra middleware services to support system monitoring and load-balancing decision. Experimental results indicate that our framework can adapt to the change of computing environment. The results also show that our approach has very low overhead in stable computing environments.

關鍵字(中)

★ 分散式系統
★ 科學計算
★ 動態負載平衡
★ 最大似然估計
★ 最大可能性估算

關鍵字(英)

★ distributed system
★ dynamic load-balancing
★ maximum likelihood evaluation
★ MPI
★ scientific computing

論文目次

目錄
摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
一、緒論 1
1-1 計算網格之背景與發展 1
1-2 最大可能性估算 3
1-3 Message Passing Interface (MPI) 5
1-4 研究目標 6
1-5 研究貢獻 7
1-6 論文架構 7
二、相關研究 9
2-1 負載平衡策略與相關工具 9
2-2 MPICH2提供之負載平衡策略 11
2-3 Nelder-Mead Simplex計算方法 13
三、系統架構 17
3-1 靜態負載平衡策略 17
3-2 動態負載平衡策略 20
3-3 混合靜態與動態負載平衡之分散式MLE程式架構 21
3-3-1 程式架構與重新分配演算法 23
3-3-2 執行範例 24
3-4 程式使用說明 28
四、實驗環境與實驗結果 30
4-1 實驗環境 30
4-2 實驗結果與分析 32
4-2-1 靜態平衡策略 32
4-2-2 混合動態與靜態負載平衡之MLE程式與純靜態負載平衡MLE程式執行時間比較 33
五、結論 40
六、未來展望 41
參考文獻 42

參考文獻

[1] I. Foster, C. Kesselman, and S. Tuecke., The Anatomy of the Grid: Enabling Scalable Virtual Organizations., International J. Supercomputer Applications, 15(3), 2001.
[2] I. Foster and C. Kesselman., The Grid 2: Blueprint for a New Computing Infrastructure., Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.
[3] BOINC, Available: http://boinc.berkeley.edu/.
[4] NVIDIA CUDA, Available: http://www.nvidia.com/object/cuda_home.html.
[5] David P. Anderson, Jeff Cobb, Eric Korpela, Matt Lebofsky, and Dan Werthimer, SETI@home: an experiment in public-resource computing., Communications of the ACM, v.45 n.11, p.56-61, November 2002
[6] D. Jewitt., Project Pan-STARRS and the Outer Solar System., Earth, Moon and Planets, 92, 465-476, 2004.
[7] J. Kubica, et al., Efficient intra- and inter-night linking of asteroid detections using kd-trees. , Icarus, Vol.189, pp. 151-168, 2007.
[8] Bentley, J.L., Multidimensional binary search trees used for associative searching. , Commun. ACM 18 (9), 509-517, 1975.
[9] 國家圖書館全國博碩士論文資訊網，Available: http://etds.ncl.edu.tw/theabs/index.html.
[10] ISI Web of Knowledge, Available: http://apps.isiknowledge.com/.
[11] Message Passing Interface Forum., MPI: A Message-Passing Interface Standard Version 2.1., June, 2008. [Online]. Available: http://www.mpi-forum.org/docs/mpi21-report.pdf. [Accessed: July 21, 2009].
[12] MPICH2, Available: http://www.mcs.anl.gov/research/projects/mpich2/.
[13] Open MPI, Available: http://www.open-mpi.org/.
[14] LAM/MPI, Available: http://www.lam-mpi.org/.
[15] J. A. Nelder and R. Mead., A simplex method for function minimization., Computer Journal, 7:308–313, 1965.
[16] J. A. Snyman., Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms., Springer Publishing, 2005.
[17] E. Falkenauer., Genetic Algorithms and Grouping Problems., John Wiley and Sons Ltd, Chichester, England, 1998.
[18] W. Wang, K. E. Maghraoui, J. Cummings, J. Napolitano, B. Szymanski, and C. Varela., A middleware framework for maximum likelihood evaluation over dynamic grids., In Second IEEE International Conference on e-Science and Grid Computing, page 8 pp, Amsterdam, Netherlands, December 2006.
[19] Travis Desell, Nathan Cole, Malik Magdon-Ismail, Heidi Newberg, Boleslaw Szymanski, and Carlos Varela., Distributed and Generic Maximum Likelihood Evaluation., In 3rd IEEE International Conference on e-Science and Grid Computing (eScience2007), Bangalore, India, pages 8pp, December 2007.
[20] Globus. Available: http://www.globus.org/.
[21] Condor, Available: http://www.cs.wisc.edu/condor/.
[22] James Frey, Todd Tannenbaum, Miron Livny, Ian Foster, Steven Tuecke, Condor-G: A Computation Management Agent for Multi-Institutional Grids., Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.55, August 07-09, 2001.
[23] Cirne, W., Brasileiro, F., Andrade, N., Costa, L., Andrade, A., Novaes, R. and Mowbray, M., Labs of the world, unite!!!., J. Grid Comput. 4(3), p.225-246, 2006.
[24] Françoise Baude, Denis Caromel, Fabrice Huet, Lionel Mestre, Julien Vayssière, Interactive and Descriptor-Based Deployment of Object-Oriented Grid Applications, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, p.93, July 24-26, 2002.
[25] Denis Caromel, Alexandre di Costanzo, Clément Mathieu, Peer-to-peer for computational grids: mixing clusters and desktop machines, Parallel Computing, v.33 n.4-5, p.275-288, May, 2007
[26] K. E. Maghraoui, T. J. Desell, B. K. Szymanski, and C. A. Varela., The internet operating system: Middleware for adaptive distributed computing., International Journal of High Performance Computing Applications (IJHPCA), Special Issue on Scheduling Techniques for Large-Scale Distributed Platforms, 10(4):467–480, 2006.
[27] K. E. Maghraoui., A Framework for the Dynamic Reconfiguration of Scientific Applications in Grid Environments., Rensselaer Polytechnic Institute, PhD thesis, 2007.
[28] G. Allen, T. Dramlitsch, I. Foster, N. Karonis, M. Ripeanu, E. Seidel, and Toonen., Supporting efficient execution in heterogeneous distributed computing environments with Cactus and Globus., In Supercomputing 2001 (SC 2001), Denver, November 2001.
[29] H. Casanova and J. Dongarra., NetSolve: A networkenabled server for solving computational science problems., The International Journal of Supercomputer Applications and High Performance Computing, 11(3):212–223, Fall 1997.
[30] A. YarKhan, K. Seymour, K. Sagi, Z. Shi, and J. Dongarra., Recent developments in gridsolve., International Journal of High Performance Computing Applications (IJHPCA), 20(1):131–141, 2006.
[31] Particle Physics Data Grid (PPDG) project. Available: http://www.ppdg.net.
[32] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery., Numerical Recipes in C: The Art of Scientific Computing., 2nd ed., Cambridge University Press, Cambridge, New York, 1992.
[33] D. Lee and M. Wiswall., A Parallel Implementation of the Simplex Function Minimization Routine., Computational Economics, Vol. 30, pp. 171-187, 2007.

指導教授

王尉任(Wei-jen Wang)

審核日期

2009-7-26

推文