為解決大量運算問題時，常會利用平行運算透過多台計算節點分配計算量，以節省運算時間，而當平行計算採取回合計算有個問題，那就是每個節點必需等待所有節點運算結束後，才能夠繼續下一個步驟的運算，因此當某個節點的運算能力較其他節點弱時，便會發生等待的問題；因此在一般的叢集運算時，會儘量要求硬體資源一致，但是在網格計算上便難以達到一致性。某些研究利用相關的效能指標，如CPU使用度來解決硬體不一致問題，但仍無法解決資源佔用問題，例如當開始平行計算時，某節點有可能被其他的執行序佔用，因此造成該節點的運算能力下降，該節點依然在計算，但執行的時間會比其他的節點長，也會發生等待的問題。
本研究利用每個節點運算的執行時間當成各節點的運算能力，不同的運算問題會有不同的資源需求，利用執行時間可簡單有效的代表各節點對其運算問題的能力，以此來動態分配各節點的工作量。實驗利用核子醫學影像重建演算法OSEM及COSEM-ML測試研究結果。

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
AbstractII
AcknowledgmentIII
ContentsIV
List of FiguresV
List of TablesVI
1. Introduction1
1.1 Background and Motivation1
1.2 Objectives4
2. Related Work6
2.1 Nuclear Medical Image Reconstruction Algorithms6
2.2 Grid Computing Environment8
2.2.1 Globus Toolkit8
2.2.2 MPI (Message-Passing Interface)9
2.3 Literature Review10
3. Parallel Workload Partition Method12
3.1 Test Cases13
3.2 Workload Partition Schemes18
3.2.1 Prediction Scheme18
3.2.2 Dynamic Workload Partition Algorithm20
4. Experimental Results26
4.1 Experimental Environment26
4.1.1 Environment Specifications26
4.1.2 Experiment Parameters27
4.2 Evaluation of 3D OSEM in a Grid29
4.2.1 Experimental Result on DWP29
4.2.2 Experimental Result on DWP with Prediction Module 32
4.3 Evaluation of 3D COSEM-ML in a Grid33
4.3.1 Experimental Results on DWP33
4.3.2 Experimental Result on DWP with Prediction Module 35
5. Discussion36
5.1 Turnaround Time Analysis36
5.2 Prediction scheme versus DWP scheme39
5.3 Cost Analysis of DWP Scheme39
5.4 Effect on Image Reconstruction Algorithm Structure40
6. Conclusions 41
7. Future Work42
8. References45

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, http://www.nas.nasa.gov/Resources/Software/npb.html
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, http://www.globus.org
8.MPI Forum,http://www3.niu.edu/mpi/
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.