臺灣博碩士論文加值系統

本篇論文的研究主要是用圖形處理單元(GPU)改善Dynamic programming(DP)中的Nonserial polyadic dynamic programming (NPDP)問題。由於NPDP 的問題在不同階段的計算會有不一樣的平行度，這使的我們難以充分利用 GPU 所擁有的計算能力，所以在先前的研究中我們題出了自動調整對應的演算法，來解決這個問題，並且有效的改善NPDP 這類問題的效能。
在這次的研究中我們著重於優化 GPU 的記憶體使用，我們利用Tile 的技術將子問題與資料切塊，讓適量的子問題與資料存入Shared Memory中，並重覆的利用這些資料，透過這個方式來減少對 Global Memory 的存取。但是我們發現由於 NPDP 問題在每個階段都需要調用 Kernel，這種反覆調用 Kernel 的方式會讓 SharedMemory中的資料被釋放掉，導致新調用的 Kernel 無法使用之前Shared Memory的資料。所幸的是Inter-Block Synchronization可以使我們只調用一次 Kernel，但它的限制是Blocks 的數量最多只能與 Stream Multi-processors 相同，這個方式除了能夠讓我們的資料可以重新使用，也使的我們可以將下個階段所需的資料預先存入 Shared Memory 中，實驗的結果証明了這個方式比先前研究所提出的方式效能改善的更多。

Our study is focused on improving an important category of Dynamic programming (DP) problems called Nonserial polyadic dynamic programming (NPDP) on a graphics processing unit (GPU).Because NPDP in different stages of the computation has different degree of parallelism, so it is hard for us to use GPU computation ability fully. In previous studies, we proposed an algorithm that can adaptively adjust the thread-level parallelism to solve this problem and improve the effectiveness of the NPDP such problems. In this research, we focused on the memory used of GPU optimization. We used the Tiling technique to divide subproblems and data. Subproblems and data are tiled to make it possible to fit small data regions into shared memory and reuse the buffered data for each tile of subproblems, thus reducing the amount of global memory access. However, we found invoking the same kernel many times, due to data consistency enforcement across different stages, this makes it impossible to reuse the tiled data in shared memory after the kernel is re-invoked. Fortunately, the inter-block synchronization technique allows us to invoke the kernel exactly one time with the restriction that the maximum number of blocks is equal to the total number of streaming multiprocessors. In addition to data reuse, invoking the kernel only one time also enables us to prefetch data to shared memory across inter-block synchronization point, which improves the performance more than data reuse. Experimental results demonstrate that our method can achieve a speedup of 3.2 over the previously published GPU algorithm.

目錄
中文摘要 I
英文摘要 II
致謝 III
目錄 IV
圖目錄 V
表目錄 VII

第一章 緒論 1
第二章 相關資訊 4
第一節 圖形處理單元（GPU） 4
第二節 CUDA 5
第三節 OPTIMAL MATRIX PARENTHESIZATION PROBLEM 9

第三章 執行緒區塊間之同步 12
第一節 GPU KERNEL的執行時間模型 12
第二節 GPU LOCK-FREE SYNCHRONIZATION 14
第三節 採用INTER-BLOCK SYNCHRONIZE產生的特性 15

第四章 資料切割之平行化方法 17
第一節 OMP問題與TILING技術 17
第二節 SHARED MEMORY的設計 19
第三節 TILING後的資料相依性 20
第四節 資料相依性轉換 20
第五節 DUMMY ZERO 22
第六節 DATA REUSE和DATA PREFETCH 23
第七節 實作 26

第五章 實驗結果 30
第六章 結論與未來展望 38
參考文獻 39

圖目錄
圖 1. 用來解多層級問題的兩種不同的KERNEL調用方式 2
圖 2.GPU與CPU硬體架構的差異 4
圖 3.CUDA資料傳輸模型 5
圖 4.CUDA執行流程 6
圖 5.KERNEL的兩層式架構 7
圖 6.SM與SP的架構 7
圖 7.多層記憶體架構 8
圖 8. MATRIX PARENTHESIZATION PROBLEM的資料相依性 10
圖 9. 調用多次KERNEL的PSEUDO CODE 12
圖 10.反覆呼叫KERNEL計算所需要的時間 12
圖 11. 只調用一次KERNEL的PSEUDO CODE 13
圖 12.改良後KERNEL計算所需要的時間 13
圖 13. GPU LOCK-FREE SYNCHRONIZATION 14
圖 14.每次執行KERNEL ，SHARED MEMORY必須重新讀取 15
圖 15.由於KERNEL只會執行一次，所以SHARED MEMORY可以重覆利用 16
圖 16.TILING後的OMP問題 17
圖 17.分析TILE之間的資料相依性的範例，假設TILE PHASE N-1時要計算TILE0,3，需要用到的TILE為TILE0,0、TILE0,1和TILE0,2，TILE PHASE N時，要計算TILE0,4，需要用到的TILE為TILE0,0、TILE0,1和TILE0,2與TILE0,3。 19
圖 18.SHARED MEMORY的分頁方式 19
圖 19.多個TILE之間的資料相依性 20
圖 20.重新調整後的TILES與PSEUDO NODE 21
圖 21.插入VIRTUAL SUBPROBLEMS 22
圖 22.在輸入資料前面補上DUMMY ZERO 22
圖 23.INSET DUMMY ZERO的PSEUDO CODE 23
圖 24. BLOCK和STREAM MULTIPROCESSOR的關係 23
圖 25.透過記憶體管理方式達到DATA REUSE的效果 24
圖 26.(A) WITHOUT DATA PREFECH，(B) DATA PREFECH的時間軸示意圖 25
圖 27. WITHOUT DATA PREFECH與DATA PREFECH的PSEUDO CODE 26
圖 28.三種不同的計算模式 26
圖 29. KERNEL基本流程圖與PSEUDO CODE 27
圖 30.TRIANGULAR的資料相依性 28
圖 31. R2R的資料相依性 29
圖 32. T2T的資料相依性 29
圖 33.三種不同的MATRIX PARENTHESIZATION ALGORITHM比較 31
圖 34.不同調用KERNEL次數對效能的影響 32
圖 35.DATA REUSE AND PREFETCH對效能的影響 33
圖 36.DUMMY ZEROS對演算法效能的影響 33
圖 37.TILE為4X4時記憶體空間的額外使用量 34
圖 38. TILE為8X8時記憶體空間的額外使用量 34
圖 39. TILE為16X16時記憶體空間的額外使用量 35
圖 40. TILE為32X32時記憶體空間的額外使用量 35
圖 41.TILE大小對效能的影響 36
圖 42.資料大小非冪次方的比較 37

表目錄
表 1.記憶體的特性 8
表 2.OMP問題的INPUT DATA 9
表 3.OMP問題的所有解 9
表 4. (A)為CPU的硬體結構，(B)為GPU的硬體結構 30

[1]A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, Second Edition, Addison-Wesley, 2003.
[2]K. Asanovic, R. Bodik, B.C. Catanzaro, J.J. Gebis, P. Husbands, K. Keutzer, D.A. Patterson, W.L. Plishker, J. Shalf, S.W. Williams, K.A. Yelick, “The landscape of parallel computing research : a view from Berkeley”, Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley , pp.1-54, 2006.
[3]T. Smith, M. Waterman, “Identication of common molecularsubsequences”,Journal of Molecular Biology, pp. 195-197, 1981.
[4]M. Hafeez, M. Younus, “An effectivesolution for matrix parenthesization problemthrough parallelization”, International Journal of Computers,pp. 1-9, 2007.
[5]H.Lee, J.Kim, S.J. Hong, S. Lee,“Processor allocation and task scheduling of matrixchain products on parallel systems”, IEEE Transactions on Parallel and DistributedSystems,pp. 394-407,2003.
[6]R.B. Lyngso, M. Zuker, “Fast evaluation of internal loops in RNA secondary structure prediction”, Bioinformatics,pp. 440-445, 1999.
[7]G. Tan, N. Sun, G.R. Gao, “Improving performance of dynamic programming via parallelism and locality on multicore architectures”, IEEE Transactions on Parallel and Distributed System,pp. 261-274, 2009.
[8]V. Boyer, D. El Baz, M. Elkihel, “Dense dynamic programming on multi GPU”, Proceedings of the 19th Euromicro International Conference on Parallel, Distributedand Network-Based Processing, pp. 545-551, 2011.
[9]S. Solomon, P. Thulasiraman, “Performance study of mapping irregular computationson GPUs”, IEEE International Symposium on Parallel &; Distributed Processing, Workshops and Phd Forum, pp. 1-8,2010.
[10] N. Deshmukh, H. Rivaz, P. Stolka, H.-J. Kang, G. Hager, M. Alaf, E. Boctor, “Real-time GPU-based analytic minimization/dynamic programming elastography”, Proceedings of the 2nd International Workshop on High-Performance Medical ImageComputing for Image-Assisted Clinical Intervention and Decision-Making, pp.1-10, 2010.
[11]G. Rizk, D. Lavenier, “GPU accelerated RNA folding algorithm”, the 9th International Conference on Computational Science: Part I, pp. 1014-1023, 2009.
[12]P. Steffen, R. Giegerich, M. Giraud, “GPU parallelization of algebraic dynamicprogramming”, Proc. of the 8th International Conference on Parallel Processing andApplied Mathematics: Part II, pp. 290-299, 2009.
[13]C.-H. Sin, C.-M. Cheng, S.-H. Lai, S.-Y. Yang, “Geodesic tree-based dynamic programming for fast stereo reconstruction”, IEEE 12th International Conference on Computer Vision Workshops, pp. 801-807, 2009.
[14]J. Congote, J. Barandiaran, I. Barandiaran, O. Ruiz, “Realtime dense stereo matchingwith dynamic programming in CUDA”, XIX Spanish Congress of Graphical Informatics, pp. 231-234, 2009.

[15] Y. Liu, B. Schmidt, D.L. Maskell, “CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD Abstractions”, BMC Research Notes, 3(1) 93, 2010.
[16]K. Dohi, K. Benkridt, C. Ling, T. Hamada, Y. Shibata, “Highly efficient mapping of theSmith-Waterman algorithm on CUDA-compatible GPUs”, Proc. 21st IEEE International Conference on Application-specific Systems Architectures and Processors, pp. 29-36, 2010.
[17]D. Razmyslovich, G. Marcus, M. Gipp, M. Zapatka, A. Szillus, Implementation of Smith-Waterman algorithm in OpenCL for GPUs, Second International Workshop on High Performance Computational Systems Biology, pp. 48-56, 2010.
[18]S. Xiao, A.M. Aji, W. Feng, “On the robust mapping of dynamic programming onto a graphics processing unit”, 15th International Conference on Parallel and Distributed Systems, pp. 26-33, 2009.
[19]L. Ligowski, W. Rudnicki, “An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases”, IEEE International Symposium on Parallel and Distributed Processing, pp.1-8, 2009.
[20]C. Ling, K. Benkrid, T. Hamada, “A parameterisable and scalable Smith-Waterman algorithm implementation on CUDA-compatible GPUs”, IEEE 7th Symposium on Application Specific Processors, pp. 94-100, 2009.
[21]G.M. Striemer and A. Akoglu, “Sequence alignment with GPU: performance and design challenges”, IPDPS, pp.1-10, 2009.
[22]S.A. Manavski, G. Valle, “CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment”, BMC Bioinformatics, 9(Suppl 2):S10, 2008.
[23]Y. Munekawa, F. Ino, K. Hagihara, “Design and implementation of the Smith-Waterman algorithm on the CUDA-compatible GPU”, 8th IEEE International Conference on BioInformatics and BioEngineering, pp. 1-6, 2008.
[24]W. Liu, B. Schmidt, G. Voss, W. Muller-Wittig, “Streaming algorithms for biological sequence alignment on GPUs”, IEEE Transactions on Parallel and Distributed Systems, pp. 1270-1281,2007.
[25]Y. Liu, W. Huang, J. Johnson, S. Vaidya, “GPU accelerated Smith-Waterman”, Proc. Int'l Conf. Computational Science, pp. 188-195, 2006.
[26]J. Nickolls, W.J. Dally, “The GPU computing era”, IEEE Micro, pp. 56-69, 2010.
[27]CUDAZone [Online].Available http://www.nvidia.com/object/cuda_home_new.html.
[28]M. Harris, S. Sengupta, J.D. Owens, Parallel prefix sum (scan) with CUDA, GPU Gems, 2007.
[29]Chao-Chin Wu, Jenn-Yang Ke, Heshan Lin, and Wu-chunFeng, “Optimizing Dynamic Programming on Graphics Processing Units via Adaptive Thread-Level Parallelism,” IEEE ICPADS 2011, pp96-103. , 2011.
[30]Shucai Xiao, Wu-chunFeng,” “Inter-block GPU communication via fast barrier synchronization”, IEEE IPDPS 2010, pp.1-12, 2010.