跳到主要內容

臺灣博碩士論文加值系統

(44.213.60.33) 您好!臺灣時間:2024/07/20 06:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳裕吉
研究生(外文):Yu-Chi Chen
論文名稱:以SPMD風格之OpenMP實作平行化快速傅立葉轉換
論文名稱(外文):Implementation of Parallel Fast Fourier Transform usingSPMD Style of OpenMP
指導教授:翁添雄
指導教授(外文):Tien-Hsiung Weng
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊碩士在職專班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:33
中文關鍵詞:OpenMPSPMD分享式記憶體平行程式設計快速傅立葉轉換
外文關鍵詞:OpenMPFFTSPMDShared-memory parallel programming
相關次數:
  • 被引用被引用:2
  • 點閱點閱:543
  • 評分評分:
  • 下載下載:53
  • 收藏至我的研究室書目清單書目收藏:0
本論文使用SPMD風格的OpenMP實作平行化的快速傅立葉轉換程式,程式以Cooley-Tukey的演算法為基礎並使用C語言撰寫。首先將該演算法改寫成非遞迴的SPMD版本,再使用OpenMP專屬指令加以平行化。快速傅立葉轉換程式主要分為兩大部分。第一部分是「位元反轉」的運算;第二部分是「蝶式運算」。以SPMD風格來設計平行程式,對程式效能之提升有很大助益,因而平行化快速傅立葉轉換程式在多核心機器執行時,效能也發揮得淋漓盡致。本研究在AMD-Opteron8200的平台進行實作,此機器擁有四顆雙核心的中央處理器。我們的平行程式在此8核心的機器上執行,結果驗證了SPMD風格之平行程式效能的確較佳。
In this thesis, we introduce a parallel version of the Fast Fourier Transform that was created using OpenMP in SPMD style. Our implementation is non-recursive and is based on the conventional Cooley-Tukey algorithm written in C. The aim of this work is show the potential benefit of writing our FFT algorithm in SPMD style which enabled an efficient use of multi-core machines. Our experimental results are based on FFT code running on an AMD OpteronTM8200 with four 2-core CPUs. The experimental results show that the performance of our new parallel code on an 8-core shared-memory machine are promising.
中文摘要 --------------------------------------i
英文摘要 -------------------------------------ii
誌 謝 ---------------------------------------iii
目 錄 ----------------------------------------iv
表目錄 ----------------------------------------v
圖目錄 ---------------------------------------vi
第一章 緒論 -----------------------------------1
1.1簡介「快速傅立葉轉換」--------------------- 1
1.2研究動機及目的 -----------------------------2
1.3論文架構 -----------------------------------4
第二章 文獻探討 -------------------------------5
2.1 快速傅立葉轉換 ----------------------------5
2.2 SPMD風格 ----------------------------------6
2.3 OpenMP ------------------------------------7
第三章 實作 ----------------------------------10
3.1 OpenMP版本的位元反轉 ---------------------11
3.2 nthroots的前置計算 -----------------------15
3.3 蝶式運算 ---------------------------------16
3.4 Omega運算 --------------------------------21
第四章 實驗結果 ------------------------------23
第五章 結論與未來研究方向 --------------------31
參考文獻 -------------------------------------32
Lin, C.C. and Segel, L.A. Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc. New York, 1974

Landau,Rubin. Multicore Processors for Science and Engineering, Computing in Science & Egineering, Copublished by the IEEE CS and the AIP, March/April 2007

Barney,Blaise. Introduction to OpenMP Tutorial, At computing.llnl.gov/tutorials/openMP

OpenMP C and C++ Application Program Interface, Version 2.0, March 2002.

Bader, David A. and Agarwal,Virat. FFTC: Fastest Fourier Transform for the IBM Cell Broadband Engine, High Performance Computing – HiPC 2007, 172-184, 2007.

Wallcraft, A. J. SPMD OpenMP vs. MPI for Ocean Models, Proceedings of First European Workshops on OpenMP (EWOMP’99), Lund, Sweden, 1999.

Cooley, J. W. and Tukey, J. W. An algorithm for the machine calculation of complex Fourier series, In Math. Comput, 19:297–301, 1965.

Bollman, D., Seguel,J. and Feo,J. Fast Digit-Index Permutations, Scientific Progress, vol. 5, no. 2, pp. 137-146, 1996.

Karp, A. H. Bit Reversal on Uniprocessors, SIAM Review, Vol. 38,pp. 289-307, 1996.

Liu, Z., Chapman, B., Wen, Y., Huang L., Weng, T.H. and Hernandez, O. Analyses for the Translation of OpenMP Codes into SPMD Style with Array Privatization, In Proceedings of International Workshop on OpenMP Applications and Tools (WOMPAT), pp. 244-259, 2003.

Lokhmotov, A., Mycroft, A. Optimal bit-reversal using vector permutations, ACM Symposium on the 19th Parallel Algorithms and Architectures, pp.198–199, 2007.

OpenMP Architecture Review Board. Fortran 2.0 and C/C++ 2.0 Specifications, At www.openmp.org

Rodriguez, J. Jeffrey. An improved Bit-reversal algorithm for the fast Fourier transform, In proceedings of International Conference on Acoustics, Speech, and Signal Processing, vol.3, pp.1407-1410, 1988.

Rubio, M., Gómez, P. and Drouiche, K. A new superfast bit reversal algorithm, International Journal of Adaptive Control and Signal Processing, vol. 16, issue 10, pp.703-707, 2002.

Seguel, J., Bollman, D. and Feo, J. A Framework for the Design and Implementation of FFT Permutation Algorithms, IEEE Transactions on Parallel and Distributed Systems, vol.11, no.7, pp.625-635, 2000.

Zhang, Z. and Zhang, X. Fast Bit-Reversals on Uniprocessors and Shared-Memory Multi-processors, SIAM Journal on Scientific Computing, vol.22, no.6, pp.2113-2134, 2000.

Takahashi, D., Sato, M., and Boku, T. An OpenMP Implementation of Parallel FFT and Its Performance on IA-64 Processors, WOMPAT 2003, LNCS 2716, pp. 99-108, 2003.

Weng, T.H., Huang, S.W., Perng, R.K., Hsu, C.H. and Li, K.C. A Practical OpenMP Implementation of Bit-reversal for Fast Fourier Transform, In Proceeding of the 4th ICST 2009, Hong Kong, June, 2009.

Pacheco, P.S. Parallel Programming with MPI, Morgan Kaufmann Publishers, 1997.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top