臺灣博碩士論文加值系統

平行處理（Parallel Computing）是利用多處理器系統，將一個複雜龐大的數值運算工作加以切割分配到多個處理器上，藉由多個處理器同時負責該計算，以降低工作時間。在醫學影像處理中，常把影像視為矩陣型態的資料，並以矩陣的運算方式來達成影像處理的目的。要將醫學影像作平行化處理，可以藉由矩陣運算的平行化處理，檢視平行處理中將會遭遇到的問題如：工作的獨立性、工作的切割方式、以及資料的同步化問題等，並針對上述問題提出較合適於醫學影像的平行處理方式。
本研究的重點在於利用共享記憶體多處理器系統（Shared Memory Multiprocessor System）對迭代式影像重建法的平行處理。迭代式影像處理需要不斷重複的正反向投影計算才能得到結果，但其結果較濾波反投影正確，有效地將正反向投影運算子作平行處理，可以得到良好的工作時間表現。將迭代式影像重建法平行化處理後，其快速的運算，使其非常適合臨床上的使用。一個好的平行處理方式可以大幅降低工作所需要的時間；但是若是所採用的平行處理方式並不適合該工作型態，平行處理後所需的工作時間不但可能毫無改善，甚至有可能比原工作時間長。

Parallel computing performs more than one independent computation for single event at the same time. Therefore, parallel computing must be executed on multiprocessor system. By partitioning task onto multiple processors, we could increase the computing rate. In medical image processing, the data structure of images is the same as that of matrices, and we usually process the image data as matrices. There is some problems about parallel computing: data independence, task partition, and data synchronization etc.. We''ll try to solve them by parallelizing the matrix multiplication problem, and find out an appropriate way to parallelize medical image processing. Iterative image reconstruction method, MLEM (Maximum Likelihood Expectation Maximization), could get better image quality than FBP, but iterative image reconstruction needs to implement forward and backward projection for many times. If we can parallelize the forward and backward projector efficiently, we will greatly decrease the execution time in MLEM. This faster iterative image reconstruction method will help us dealing with the clinical data. A suitable way for parallel computing will decrease the execution time of a process. If we chose an unsuitable way for parallel computing, it may cost more time than non-parallel computing program.

第 1 章、 前言 1
第 2 章、 平行處理 4
第 1 節、 多處理器系統 4
A. 共享記憶體多處理器系統 4
B. 分散式記憶體多處理器系統 8
C. 叢集式系統 10
D. 多處理器系統的幾何結構 11
I 完全連接（Fully Connected） 12
II 線狀排列（Linear） 12
III 網狀排列（Mesh） 12
IV 環狀排列（Ring） 13
V 立體晶格狀結構（Grid） 13
VI 立體結構（Cube） 13
第 2 節、 作業系統 14
A. 多工批次系統（Multi-Tasking System） 14
B. 分時系統（Time-Sharing System） 15
第 3 節、 平行處理 16
A. 平行處理的定義 16
B. 效率的提升（Speedup） 16
C. 平行化處理的挑戰 17
I 額外的計算 17
II 嚴格的程式設計規範 18
III 程式除錯的困難 18
第 4 節、 處理程序（Process）與執行緒（Thread） 18
A. 處理程序與執行緒的關係 19
B. 執行緒的特性 19
C. 平行處理上使用執行緒的優點 20
第 3 章、 工作分配與矩陣相乘 22
第 1 節、 工作的獨立性 22
第 2 節、 執行工作的分配 23
A. 每個執行緒負責單一向量內積計算 24
B. 固定執行緒數目，輪流執行子工作單元 25
C. 互斥器之使用 27
第 3 節、 合適的平行處理方式 32
第 4 章、 實驗與結果 35
第 1 節、 二維快速傅立葉轉換（2D FFT） 35
A. 連續函數的傅立葉轉換（Fourier Transform） 35
B. 離散傅立葉轉換（Discrete Fourier Transform） 37
C. 快速傅立葉轉換（Fast Fourier Transform） 39
D. 二維快速傅立葉轉換的平行處理 41
I 二維傅立葉轉換 41
II 二維傅立葉轉換的平行處理 42
第 2 節、 濾波反投影(FBP) 47
A. 濾波反投影 47
B. 濾波反投影的平行處理 52
第 3 節、 迭代式影像重建法 56
A. MLEM（Maximum Likelihood Expectation Maximization） 56
B. MLEM的執行 60
C. 工作的獨立性 62
D. 平行處理上工作的分配與執行 66
I 正向投影 67
II 反向投影 70
E. 平行處理結果 72
第 5 章、 結論與未來方向 74
參考文獻 76

1. David R. Butenhof, Programming with POSIX Threads, Addision-Wesley, 1997.
2. Chao-Tung Yang, Clustering System.http://aho.cis.nctu.edu.tw/~ctyang
3. William Stallings, Operating Systems: Internals and Design Principles, 3rd ed, Prentice-Hall Inc., 1998.
4. Scott J. Norton and Mark D. Dipasquale, Thread Time :The Multithreaded Programming Guide, Hewlett-Packard Company, 1997.
5. L. A. Shepp and Y.vardi, Maximum likelihood reconstruction for emission tomography, IEEE Transactions on Medical Imaging, Vol. MI-1, No. 2, p. 113-122, October 1982.
6. Jia-Lien Wang, System Geometric Modeling in Statistical PET Image Reconstruction.Master thesis, National Tsing Hua University, 2002.
7. L. Kaufman, Maximum likelihood, least squares, and penalized least squares for PET, IEEE Transactions on Medical Imaging, Vol.12, No. 2, p. 200-214, June 1993.
8. Rafael C. Gonzalez and Richard E.Woods, Digital Image Processing, Addison Wesley, 1992.
9. James A. Sorenson and Michael E. Phelps, Physics in Nuclear Medicine, 2nd ed, W.B. Saunders Company, 1987.
10. Zang-Hee Cho, Joie P. Jones, and Manbir Singh, Foundations of Medical Imaging, John Wiley & Sons, Inc., 1993.
11. Timothy G. Turkington, Introduction to PET Instrumentation, Journal of Nuclear Medcine Technology, Vol. 29, No. 1 , p. 4-11, March 2001.
12. Avinash C. Kak and Malcolm Slaney, Priciples of Computerized Tomographic Imaging, IEEE Press, 1988.
13. Athanasios Papoulis, Probability, Random Variables, and Stochastic Processes, McFraw-Hill, Inc., 1991.
14. Chung-Ming Chen and Soo-Young Lee, On Parallelizing the EM Algorithm for PET Image Reconstruction, IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 8, p. 860-873, August 1994.
15. 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, p. 513-522, December 1991.
16. Miranda E. Barrows, Dawn E. Gregory, Lixin Gao, Arnold L. Rosenberg, and Paul R. Cohen, An empirical study of dynamic scheduling on rings of processors, Parallel Computing, Vol. 25, p. 1063-1079, 1999.