Basic Search / Detailed Display

Author: 余乾揚
Chien-Yang Yu
Thesis Title: 網格計算下的平行化醫學影像重建動態工作分配
Dynamic Workload Partition on Parallel Medical Image Reconstruction Algorithm in Computational Grid Environments
Advisor: 羅乃維
Nai-Wei Lo
Committee: 楊傳凱
Chuan-Kai Yang
I.T. Hsiao
Degree: 碩士
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2007
Graduation Academic Year: 95
Language: 英文
Pages: 46
Keywords (in Chinese): 網格運算平行運算閒置等待問題效能評估動態分配核子醫學影像
Keywords (in other languages): Grid computing, parallel computing, idle waiting issue, performance evaluation, dynamic scheduling, Medical Image Reconstruction
Reference times: Clicks: 52Downloads: 1
School Collection Retrieve National Library Collection Retrieve Error Report
  • 為解決大量運算問題時,常會利用平行運算透過多台計算節點分配計算量,以節省運算時間,而當平行計算採取回合計算有個問題,那就是每個節點必需等待所有節點運算結束後,才能夠繼續下一個步驟的運算,因此當某個節點的運算能力較其他節點弱時,便會發生等待的問題;因此在一般的叢集運算時,會儘量要求硬體資源一致,但是在網格計算上便難以達到一致性。某些研究利用相關的效能指標,如CPU使用度來解決硬體不一致問題,但仍無法解決資源佔用問題,例如當開始平行計算時,某節點有可能被其他的執行序佔用,因此造成該節點的運算能力下降,該節點依然在計算,但執行的時間會比其他的節點長,也會發生等待的問題。

    Parallel computing has an issue that every computing node starts to execute an iteration round at the same time until every node is done at that round. Ideally in a cluster computing environment, the hardware of all nodes are the same; however, there are different resources which form a Grid. Therefore, if users want to execute parallel program in Grid, the work loads become more important regarding to the distribution of task amount. For instance, a task is divided into several smaller tasks, and three smaller tasks will be executed on different computational resources. Because of inequality in computing power and/or network bandwidth, some resources may finish the tasks sooner than the others. The fastest finished node has to wait until the other nodes also finished
    The issue in parallel computing as previously mentioned is that computing nodes need to wait each other in every execution round. The purpose of this study is to find the best workload distribution for each node, and distribute the suitable amount of tasks during the execution period of each round.
    In this research, OSEM and COSEM-ML were chosen for experiments. Both of them are algorithms of medical image reconstruction.

    Contents 中文摘要 I Abstract II Acknowledgment III Contents IV List of Figures V List of Tables VI 1. Introduction 1 1.1 Background and Motivation 1 1.2 Objectives 4 2. Related Work 6 2.1 Nuclear Medical Image Reconstruction Algorithms 6 2.2 Grid Computing Environment 8 2.2.1 Globus Toolkit 8 2.2.2 MPI (Message-Passing Interface) 9 2.3 Literature Review 10 3. Parallel Workload Partition Method 12 3.1 Test Cases 13 3.2 Workload Partition Schemes 18 3.2.1 Prediction Scheme 18 3.2.2 Dynamic Workload Partition Algorithm 20 4. Experimental Results 26 4.1 Experimental Environment 26 4.1.1 Environment Specifications 26 4.1.2 Experiment Parameters 27 4.2 Evaluation of 3D OSEM in a Grid 29 4.2.1 Experimental Result on DWP 29 4.2.2 Experimental Result on DWP with Prediction Module 32 4.3 Evaluation of 3D COSEM-ML in a Grid 33 4.3.1 Experimental Results on DWP 33 4.3.2 Experimental Result on DWP with Prediction Module 35 5. Discussion 36 5.1 Turnaround Time Analysis 36 5.2 Prediction scheme versus DWP scheme 39 5.3 Cost Analysis of DWP Scheme 39 5.4 Effect on Image Reconstruction Algorithm Structure 40 6. Conclusions 41 7. Future Work 42 8. References 45

    1.Liang Peng, Simon See, Yueqin Jiang, Jie Song, Appie Stoelwinder, and Hoon Kang Neo, “Performance Evaluation in Computational Grid Environments”, Proceedings, High Performance Computing and Grid in Asia Pacific Region, pp.54- 62, 20-22 July 2004.
    2.NASA Grid Benchmark, 2006,
    3.I.T. Hsiao, Y. Chang, K.J. Lin, and W.J. Huang, “Fast Statistical Image Reconstruction for Emission Tomography: Application to SPECT,” Journal of Medical and Biological Engineering, 24(2): pp.93-98, 2004.
    4.L.A. Shepp and Y. Vardi, “Maximum likelihood reconstruction for emission tomography”, in IEEE Trans. Med. Imaging. vol. MI-1, pp.113-122. 1982.
    5.Hudson, H.M. Larkin, and R.S., “Accelerated image reconstruction using ordered subsets of projection data”, IEEE Trans. Med. Image. 13(4): pp.601-609, 1994
    6.I.T. Hsiao, A. Rangarajan, and G. Gindi, “A Provably Convergent OS-EM Like Reconstruction Algorithm for Emission Tomography”, Proc. SPIE, 4684, pp.10-19, Feb 2002
    7.GLOBUS tookit,
    8.MPI Forum,
    9.Dror G. Feitelson and Larry Rudolph, “Parallel Job Scheduling: Issues and Approaches”, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, IPPS Workshop, pp.1-18, 1995.
    10.Sharath Babu Musunoori, “Quality Aware Service Planning in Computational Grid”, ACM 2005
    11.C. Lee. “On Quality of Service Management”, PhD thesis, Carnegie Mellon University, 1999
    12.Anja Feldmann, Ming-Yang Kao, Jiri Sgall, and Shang-Hua Teng, “Optimal Online Scheduling of Parallel Jobs with Dependencies”, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing STOC '93, June 1993.
    13.Shun-Yuen Chung, “The Computing Analysis of Medical Image Processing in Grid Environment”, master thesis, Dept. Information Management of NTUST, 2006
    14.Yin-Chiao Tsai, “Mean Curvature Diffusion Method for PET Image Processing”, master thesis, Dept. Electrical Engineering of CYCU, 2001.
    15.Robert D.Nowak and Michael J. Thul , “Wavelet-Vaguelette Restoration in Photon-Limited Imaging”, Acoustics, Speech, and Signal Processing, Proceedings of the IEEE International Conference on ICASSP, 1998.
    16.Michael Resch, Holger Berger, Thomas Boenisch Dirk Sihling, “Performance of MPI on a Cray T3E-512”, Third European CRAY-SGI MPP Workshop, Paris, September, 1997.
    17.Y. Picard, V. Selivanov, Mverreault, and R. Lecomte, “Optimizing Communications for Parallel ML-EM Image Reconstruction on Large Clusters of Processors”, IEEE Nuclear Science Symposium & Medical Imaging Conf. Record, Vol.III, pp.1574-1580, 1999.