跳到主要內容

臺灣博碩士論文加值系統

(18.205.192.201) 您好!臺灣時間:2021/08/06 04:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:王文孝
研究生(外文):Wen-Shiao Wang
論文名稱:OpenMP、Cilk及UPC所建置之位元反轉之效能評估
論文名稱(外文):Design and Performance Evaluation of Parallel Bit-reversal with OpenMP, Cilk and UPC
指導教授:翁添雄
指導教授(外文):Tien-Hsiung Weng
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊工程學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:41
中文關鍵詞:位元反轉Cilk快速傅利葉轉換Single Program Multiple Data (SPMD)
外文關鍵詞:Bit-ReversalFast Fourier TransformCilkSingle Program Multiple Data (SPMD)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:278
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來隨著CPU開發技術的進步,多核心的CPU技術已取代傳統的單核CPU,然而目前許多應用程式及演算法都還停留在單核CPU的循序運算(非平行)為主的階段。在本論文中,我們設計的平行演算法以OpenMP、Cilk和UPC平行語言,將現有循序的位元反轉(Bit-Reversal)演算法改寫成平行程式。
位元反轉演算法是快速傅利葉轉換(Fast Fourier Transform; FFT)裡的一個部分,其在執行的時候,會佔快速傅利葉轉換總執行時間的10-30% [12],所以我們的研究是以Rodriguez [13]針對快速傅利葉轉換所設計的改良式位元反轉演算法為基礎,以SPMD (Single Program Multiple Data)的架構將它改寫成可以平行處理的平行程式。
除了確保能夠在多核心CPU電腦正確執行之外,因此也試著將程式最佳化、分析其效能,並設法改善,希望能夠進一步提升執行效能以及平行程式設計的經驗。
Most commonly used hardware architecture was a multi-core machine, but most of the application programs were written in sequential one. In this thesis, to fully utilize the multi-core machine, we design a parallel Bit-Reversal algorithm for Fast Fourier Transform (FFT) program. The algorithm is based on Rodriguez’s serial code [13]. It must be carefully designed for developing FFT code, because it may take about 10-30% [12] of total execution time. We implemented it as SPMD style using OpenMP, Cilk, and UPC to run on multi-core CPU machine. We try to analyze, evaluate, and improve its performance, as well as accumulate our experience of parallel programming.
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章、 動機 1
第二章、 背景 2
2.1 Cilk介紹 2
2.1.1 一般Cilk常用的指令 2
2.1.2 如何評估Cilk程式的效能 3
2.1.4 Cilk排程器 [2] 3
2.2 OpenMP介紹 6
2.2.1 變數的初始方式 [19] 6
2.2.2 排程指令句 6
2.3 UPC介紹 8
2.4 位元反轉(Bit-Reversal)演算法 9
第三章、 實驗方法 10
3.1 位元反轉的循序版本 10
3.2 位元反轉的平行版本 12
第四章、 實験結果 21
4.1實驗數據 21
第五章、 結論與未來研究方向 39
參考文獻 40
1. Bahn, J. H., Yang, J. S., Hu, W. H. and Bagherzadeh, Nade. “Parallel FFT Algorithms on Network-on-Chips”, Journal of Circuits, Systems, and Computers 18(2), pp. 255-269, 2009.
2. Bender, M. A., and Rabin, M. O., “Scheduling Cilk Multithreaded Parallel Programs on Processors of Different Speeds”, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, pp. 13–21, July 2000.
3. Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H. and Zhou, Y. “Cilk: An Efficient Multithreaded Runtime System”, Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 207–216, 1995.
4. Bollman, D., Seguel, J. and Feo, J. “Fast Digit-Index Permutations”, Scientific Progress, vol. 5, no. 2, pp. 137-146, 1996.
5. Cooley, J. W. and Tukey, J. W. “An algorithm for the machine calculation of complex Fourier series”, In Math. Comput. 19, 297–301 (1965).
6. El-Ghazawi, T., Carlson, W., Sterling, T. and Yelick, K.“UPC Distributed Shared Memory Programming”, Wiley Series on Parallel and Distributed Computing.
7. Frigo, M. “Multithreaded programming in Cilk”, In Proceedings of the 2007 international workshop on parallel symbolic computation (2007).
8. Frigo, M., Leiserson, C. E. and Randall, K. H. “The Implementation of the Cilk-5 Multithreaded Language”, In: ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pp. 212–223 (1998).
9. Karp, A. H. “Bit Reversal on Uniprocessors”, SIAM Review, Vol. 38,pp. 289-307, 1996.
10. Koole, M. L. “Practical issues in mobile education”, Proc. IEEE Int. Workshop on Wireless, Mobile and Ubiquitous Technology in Education, pp. 142-146, Nov. 2006.
11. Leiserson, C. E. “Multithreaded Programming in Cilk”, http://supertech.lcs.mit.edu/cilk LECTURE 1”.
12. Lokhmotov, A. and Mycroft, A. “Optimal bit-reversal using vector permutations”, In proceedings of ACM Symposium on the 19th Parallel Algorithms and Architectures, pp. 198–199, 2007.
13. Rodriguez, J. J. “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.
14. Rubio, M., Gómez, P. and Drouiche, K. “A new superfast bit reversal algorithm”, International Journal of Adaptive Control and Signal Processing 16(10), 703–707 (2002).
15. 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 11(7), 625–635 (2000).
16. Supercomputing Technologies Group MIT Laboratory for Computer Science. “Cilk 5.4.6 Reference Manual”, http://supertech.lcs.mit.edu/cilk.
17. 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.
18. “The MIT Cilk Project”, http://supertech.csail.mit.edu/cilk.
19. Wikipedia. "OpenMP", http://en.wikipedia.org/wiki/OpenMP.
20. Wikipedia. "Cilk", http://en.wikipedia.org/wiki/Cilk.
21. Wikipedia. "Unified Parallel C", http://en.wikipedia.org/wiki.
Unified_Parallel_C.
22. Zhang, Z., Zhang, X. “Fast Bit-Reversals on Uniprocessors and Shared-Memory Multiprocessors”, SIAM Journal on Scientific Computing 22(6), 2113–2134 (2000).
23. 鄭芳真,「以Unified Parallel C平行程式語言建置快速傅利葉轉換之位元反轉」,靜宜大學,碩士論文,民國98年7月。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top