Title page for 965202103


[Back to Results | New Search]

Student Number 965202103
Author Cheng-hui Wu(吳政暉)
Author's Email Address 965202103@cc.ncu.edu.tw
Statistics This thesis had been viewed 1336 times. Download 1115 times.
Department Computer Science and Information Engineering
Year 2008
Semester 2
Degree Master
Type of Document Master's Thesis
Language zh-TW.Big5 Chinese
Title A Dynamic Load-Balancing Maximum Likelihood Evaluation Framework
Date of Defense 2009-07-24
Page Count 55
Keyword
  • distributed system
  • dynamic load-balancing
  • maximum likelihood evaluation
  • MPI
  • scientific computing
  • Abstract 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.
    Table of Content 目錄
    摘要i
    Abstractii
    誌謝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
    Reference [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.
    Advisor
  • Wei-jen Wang(王尉任)
  • Files
  • 965202103.pdf
  • approve immediately
    Date of Submission 2009-07-26

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.