隨著電腦硬體的性能不斷地提升，個人電腦已經可以完成許多複雜的運算。但是在高科技的產業和研究中，都必須仰賴電腦來完成精密且大量的計算；雖然電腦硬體的性能進步飛快，在面對如此龐大的計算需求量時仍無法在短時間內完成所交付的計算工作。而在一般的企業或是研究單位中，礙於經費的限制無法購入具有強大計算能力的超級電腦；因此格網計算成為提供高速運算和大量資料處理的新選擇。透過網路將數台個人電腦連接成一個個電腦叢集所形成的格網環境，能以較低的成本提供強大的計算能力，以滿足目前高科技龐大的計算量需求。

本研究使用4台P4 2.8GHz的個人電腦，透過交換機的連接，建立了一個簡單的格網環境，並採用Globus Toolkit作為中介軟體，搭配MPICH-G2的函式庫，在此環境下針對一核子醫學影像重建演算法：COSEM-ML進行平行演算法的開發。由於核子醫學之疊代影像重建演算法非常的費時，恰好該演算法與格網計算的特性相符合，因此本研究選定的這個新興的COSEM-ML演算法作為研究對象。對於不同資料量的欲重建影像和使用不同數量的處理器進行一連串的實驗，並將實驗結果進行加速與效率上的分析。更進一步的參考Amdahl’s Law，建立出一個適合本研究的分析模型，進而探討理論加速與實驗結果的加速之間的差異。最後再利用實驗的結果來推估使用超過4個處理器的加速，利用這樣一個推估的結果可以大略估計在多大的資料量下，使用多少個處理器所組成的格網環境就可能到達一個加速飽和的狀態。例如在重建128張1024^2的影像時，本研究預測使用6個處理器就會到達最佳的加速值(4.26)。這個推估方式可提供未來的格網環境建置者在考慮所需使用的格網環境規模時作為一個參考。

With the improvement of computer’s hardware in recent years, lots of complicated computing tasks have been processed by personal computers (PCs). Although the capability of PCs improves very fast, it still can’t finish complicated computing works in a short time. It is difficult to buy a supercomputer for general enterprises or research centers due to the confinement of outlay. Therefore, “Grid Computing” becomes a new choice to provide high-performance computing and mass data processing. The Grid environment constructed by PC clusters could provide high-performance computing power with much lower costs to satisfy the mass computing demand from high technology companies and research centers.

This research uses 4 PCs connected by network switch to construct a simple local grid environment with Globus Toolkit and the library of MPICH-G2 as the middleware to develop a parallel version of the nuclear medical iterative image reconstruction algorithm: COSEM-ML. This algorithm is time-consuming and its iterative computing characteristics can be easily adapted into grid computing environment. We take experiments with different sizes of image to perform reconstruction under different number of processors, and analyze the speedup and the efficiency based on our experimental results. Further, we refer to Amdahl’s Law to propose an analytic model, and compare the speedup of experimental results with the theoretical speedup derived from our model. Then, we use the theoretical speedup to estimate the speedup when more than 4 processors are used to execute this algorithm. For example, we could predict the peak speedup performance 4.26 is shown when 6 processors are used to process 128 slices of 1024^2 size of image. This estimation of speedup, or we could consider it as the estimation of the reasonable scale of grid environment, could provide a reference for those who want to construct a grid environment to do some heavy computing works.

中文摘要I
英文摘要III
誌謝V
目錄VI
圖目錄VIII
表目錄X
第一章 序論1
第一節 研究背景與動機1
第二節 研究對象5
第三節 研究目的6
第四節 研究架構6
第二章 文獻探討8
第一節 核子醫學影像處理8
第二節 統計性疊代影像重建法10
第三節 格網計算(Grid Computing)17
第四節 Globus Toolkit18
第五節 MPI (Message-Passing Interface)20
第六節 醫學影像重建之平行演算法23
第三章 研究方法24
第一節 研究假設24
第二節 系統架構24
第三節 資料分割方式26
第四節 COSEM-ML演算法27
第五節 COSEM-ML平行演算法34
第六節 實驗參數37
第七節 分析模型38
第四章 實驗結果41
第一節 加速(Speedup)與效率(Efficiency)分析41
第二節 理論加速與實驗結果之比較56
第三節 格網規模推估分析63
第五章 結論69
第一節 研究結論69
第二節 研究貢獻71
第三節 未來展望72
參考文獻74
附錄A78

中文部分：
[1]林文俊、許靖涵，「疊代影像重建法在正子斷層造影之應用」， Chinese Journal of Radiologic Technology, Vol. 27, No. 1, pp.1-10, 2003.
[2]許靖涵，「疊代影像重建法簡介」，核醫會訊，第7卷 第10期 2001年10月1日。
[3]黃圳柏、邱基峰、黃文祥、謝錫堃，「以Web-Based之平行計算環境之設計與實作」，第十四屆物件導向技術及應用研討會，pp.53-56。
[4]柯智凱，「從1到2500個亞卓鎮－系統架構部署與運作機制」，國立中央大學網路學習科技研究所碩士論文，中華民國93年6月。
英文部分：
[5]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.
[6]H. Malcolm Hudson and Richard S. Larkin, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Transactions on Medical Imaging, Vol. 13, No. 4, pp.601-609, Dec. 1994.
[7]J. A. Fessler and A. O. Hero, “Space-alternating generalized expectation maximization algorithm,” IEEE. Trans. Signal Processing, vol. 42, pp.2664-2676, 1994.
[8]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.
[9]Ian Foster, “Building the Grid: An Integrated Services and Toolkit Architecture for Next Generation Networked Applications,” http://www.gridforum.org/, July 1999.
[10]Global Grid Forum web page, 2004, http://www.ggf.org/.
[11]Nicholas T. Karonis, Brian Toonen, and Ian Foster, “MPICH-G2: AGrid-Enabled Implementation of the Message Passing Interface,” Journal of Parallel and Distributed Computing, Vol.63, No. 5, pp.551-563, May 2003.
[12]Hudson H M and Larkin R S, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Trans. Med. Imag. 13(4): pp.601-609, 1994.
[13]C. M. Chen, S.-Y. Lee, and Z. H. Cho, “Parallelization of the EM Algorithm for 3-D PET Image Reconstruction,” IEEE Transactions on Medical Imaging, vol.10, no.4 pp.513-522, Dec. 1991.
[14]Y. Picard, V. Selivanov, M. Verreault, and R. Lecomte, “Optimizing Communications for Parallel ML-EM Image Reconstruction on Large Clusters of Processors,” 1998 IEEE Nuclear Science Symposium & Medical Imaging Conf. Record, Vol.III, pp.1574-1580, 1999.
[15]Benoit Desjardins and Roger Lecomte, “Parallel Approach to Iterative Tomographic Reconstruction for High Resolution PET Imaging,” 1997 IEEE Nuclear Science Symposium & Medical Imaging Conf. Record, Vol.II, pp.1551-1555, 1998.
[16]James B. White III and P. Sadayappan, “On Improving the Performance of Sparse Matrix-Vector Multiplication,” High Performance Computing, Fourth International Conference Proceedings, pp.66-71 on 18-21 Dec. 1997.
[17]C. Laurent, F. Peyrin, C. Girerd, and J.-M. Chassery, “Parallel Performances of Three 3D Reconstruction Methods on MIMD Computers: Feldkamp, Block ART and SIRT Algorithms,” IEEE Nuclear Science Symposium & Medical Imaging Conf. Record, pp.1762-1766, 1997.
[18]The globus project web page, 2003. http://www.globus.org/.
[19]I. Foster, C. Kesselman, J. Nick, and S. Tuecke, “Grid Services for Distributed System Integration,” Computer, 35(6), 2002.
[20]K. Keahey, T. Fredian, Q. Peng, D.P. Schissel, M. Thompson, I. Foster, M. Greenwald, and D. McCune, “Computational Grids in Action: The National Fusion Collaboratory,” Future Generation Computer Systems, 18:8, pp.1005-1015, October 2002.
[21]M. Russel, G. Allen, G, Daues, I. Foster, E. Seidel, J. Novotny, J. Shalf, G, von Laszewski, “The Astrophysics Simulation Collaboratory: A Science Portal Enabling Community Software Development,” Cluster Computing, 5(3): pp.297-304, 2002.
[22]M. Ripeanu, A. Iamnitchi, and I. Foster, “Cactus Application: Performance Predictions in Grid Environments,” EuroPar 2001, Manchester, UK, August 2001.
[23]GridForge web page, 2004, http://forge.gridforum.org/projects/ogsi-wg.
[24]M. Phelps, J. Mazziotta, and H. Schelbert, editors. “Positron Emission Tomography and Autoradiography: Principle and Applications for the Brain and Heart,” Raven Press, New York, 1986.
[25]NASA information power grid web page, 2003, http://www.ipg.nasa.gov/.
[26]Oracle grid computing web page, 2003, http://www.oracle.com/solutions/grid/.
[27]R. Siddon, “Fast Caculation of the Exact Radiological Path for a 3D CT Array,” Med. Phys., 12, pp.252-255, 1985.
[28]http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/beowulf_book/node1.html
[29]GENE H. GOLUB, CHARLES F. VAN LOAN, “MATRIX COMPUTATIONS THIRD EDITION”.
[30]http://www-128.ibm.com/developerworks/cn/grid/gr-ogsi/index.html
[31]Message Passing Interface Forum, “MPI: A Message-Passing Interface Standard,” June 12, 1995.