闕志達Chiueh, Tzi-Dar臺灣大學:電子工程學研究所陳語煙Chen, Yu-YenYu-YenChen2010-07-142018-07-102010-07-142018-07-102009U0001-1208200910445600http://ntur.lib.ntu.edu.tw//handle/246246/189204繪圖處理器(Graphics Processing Unit)經過數代的演進，由只具備固定功能的運算單元漸漸發展而具有高度可程式化的能力。由於繪圖處理器通常具有相當高的記憶體頻寬，以及極佳的浮點運算能力，因此開始有利用繪圖處理器來加速一些非圖形處理計算工作的想法，即通用運算繪圖處理器(General Purpose Computing on Graphics Processing Units)。 然而，並非所有運算皆適合使用繪圖處理器加速，於繪圖處理器處理之運算需為重複且低資料相依性，即具備高平行化程度之特性。本論文中，將使用統一計算架構(Compute Unified Device Architecture)，也就是NVIDIA公司通用運算繪圖處理器的模型，平行化地實現正交分頻多工(Orthogonal Frequency-Division Multiplexing)通訊系統中常見的快速傅立葉轉換(Fast Fourier Transform)，以及修正傳送錯誤常用的維特比解碼器(Viterbi Decoder)。同時也將平行化的概念，應用到基頻通道模擬器以及通訊接收機中，將需要耗費大量時間且能夠平行化實現之運算，由中央處理器(CPU)移轉至繪圖處理器(GPU)中處理，而達到加速的目的。於本論文中，除了呈現使用繪圖處理器加速之方法與成果外，也將分享繪圖處理器程式設計(GPU Programming)之經驗。The Graphics Processing Unit (GPU) has been evolving for various generations, from a fixed-funcion graphics pipeline to a programmable parallel processor. Due to the fact that GPU has a high memory bandwidth and a high Giga FLoating points Operations Per Second (GFLOPS) performance, it is used to accelerate the computations of non-graphics data, which is also referred as General Purpose Computing on Graphics Processing Units (GPGPU). However, not all algorithms benefit equally from this technique. The GPU computing is only suitable for algorithms with repeating computation and low data dependency, which means with a high degree of parallel computing characteristics. There are mainly two groups of communication applications analyzed and implemented in this thesis, which are all implemented and simulated using general personal computer under the NVIDIA CUDA environment. First, the method and result of the baseband channel simulation implementation using parallel computing concept is presented in the thesis. Then the parallel computing concepts are being used to implement the communication receiver. Both of the speedup performance and the GPU programming experience will be covered in this thesis.目錄 I目錄 V目錄 IX一章 緒論 1.1. 研究背景 1.2. 研究動機 3.3. 通用計算繪圖處理器簡介 3.3.1. 繪圖處理器之演進 4.3.2. 通用計算繪圖處理器軟體環境(GPGPU Software Environments) 6.4. 論文組織介紹 8二章 統一計算設備架構(COMPUTE UNIFIED DEVICE ARCHITECTURE)介紹 9.1. 本章簡介 9.2. 程式設計模型(PROGRAMMING MODEL) 10.2.1. 執行模型 10.2.2. 執行緒層次架構(Thread Hierarchy) 11.2.3. 記憶體層次架構(Memory Hierarchy) 12.3. 繪圖處理器硬體架構 15.3.1. 繪圖處理器硬體架構簡介 15.3.2. 執行緒排程(Thread Scheduling) 16.4. 應用程式介面(API)簡介 18.4.1. C程式語言的擴展 18.4.1.1. 函式類型限定詞(Function Type Qualifiers) 18.4.1.2. 變數類型限定詞(Variable Type Qualifiers) 19.4.1.3. 內置變數(Built-in Variables) 19.4.2. 常用用法 20.4.2.1. 設備函式(Kernel) 20.4.2.2. 主機呼叫設備函式(Kernel) 21.4.2.3. 設備(Device)記憶體用法 23.5. 程式設計建議(PROGRAMMING GUIDELINE) 26三章 利用繪圖處理器平行運算之實例 29.1. 本章簡介 29.2. 快速傅立葉轉換(FAST FOURIER TRANSFORM)之平行化實現 30.2.1. 快速傅立葉轉換之序列(Serial)實現方法 30.2.2. 快速傅立葉轉換之平行化實現方法 32.2.2.1. Cooley-Tukey 演算法 32.2.2.2. Stockham演算法 34.2.2.3. Large Size FFT 37.2.2.4. Radix-4 FFT 38.2.2.5. Cached-FFT演算法 39.2.3. 平行化實現之加速效果 41.3. 維特比解碼器(VITERBI DECODER)之平行化實現 43.3.1. 維特比解碼器之列(Serial)實現方法 43.3.2. 維特比解碼器之之平行化實現方法 46.3.2.1. Radix-2維特比解碼器 46.3.2.2. Radix-4維特比解碼器 49.3.3. 平行化實現之加速效果與討論 50四章 基頻通道模擬之平行化實現 55.1. 本章簡介 55.2. 基頻通道模擬簡介 55.2.1. 多重路徑瑞雷衰減通道模型 55.2.2. 接收端非理想效應 57.3. 瑞雷衰減模型(RAYLEIGH FADER) 59.3.1. 平行化實現瑞雷衰減模型之架構 59.3.2. Modified Wu’s Model之平行化實現 62.3.3. 萊斯衰減(Rician Fading)通道模型之平行化實現 66.3.4. 矩陣相乘之平行化實現 67.3.5. 平行化實現瑞雷衰減模型之加速效果 69.4. 基頻通道模擬之加速效果 71.4.1. 平行化實現基頻通道模擬之架構 71.4.2. 平行化實現基頻通道模擬之加速效果 72五章 歐規數位電視地面廣播(DVB-T)接收機之平行化實現 75.1. 本章簡介 75.2. 歐規數位電視地面廣播概述 75.2.1. 正交分頻多工(OFDM)調變介紹 75.2.2. DVB-T系統規格簡介 78.2.3. 傳送端(Transmitter)系統架構 81.3. 接收端(RECEIVER)系統架構 84.3.1. 方塊圖(Block Diagram) 84.3.2. 初始擷取(Acquisition)與同步 84.3.3. 追蹤(Tracking)迴路 85.3.4. 資料回復(Data Recovery) 85.4. 接收端(RECEIVER)之平行化實現 88.4.1. 方塊圖(Block Diagram) 88.4.2. 快速傅立葉轉換(FFT) 89.4.3. 相位調整(Phase Modification) 89.4.4. 通道估測與補償 90.4.4.1. 時域內插器(Time-Domain Interpolatior) 91.4.4.2. 頻域等化器(FEQ) 92.4.5. 解映射器(De-Mapper) 92.4.6. 反交錯器(De-interleaver) 93.4.6.1. 反符元交錯器(De-Symbol-Interleaver) 93.4.6.2. 反位元交錯器(De-Bit-Interleaver) 94.4.6.3. 多工器(MUX) 95.4.7. 維特比解碼器(Viterbi Decoder) 95.5. 接收端(RECEIVER)平行化實現之加速效果 97六章 結論與展望 101考資料 1038115836 bytesapplication/pdfen-US通用運算繪圖處理器統一計算設備架構歐規數位電視基頻數位通訊GPGPUCUDADVB-TDigital Baseband Communicationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/189204/1/ntu-98-R96943026-1.pdf