陳俊杉臺灣大學：土木工程學研究所丁久棻Ting, Chiu-FenChiu-FenTing2007-11-252018-07-092007-11-252018-07-092006http://ntur.lib.ntu.edu.tw//handle/246246/50516本研究提出兩種以FPGA實作矩陣解法器方法，分為以VHDL直接設計硬體解法器，和編程軟核處理器MicroBlaze設計解法器嵌入式系統。為發揮FPGA的平行特性，我們根據迭代式演算法Jacobi Iteration平行特性設計管線式連乘加器架構，並探討序列式演算法Gauss-Jordan Elimination的問題複雜度與演算法平行限制。矩陣資料I/O方面，本研究採取序列式傳輸協定，由個人電腦端應用程式透過RS232埠傳送矩陣數據並接收FPGA回傳數據。硬體解法器與嵌入式系統之軟體解法器皆採用序列式演算法，可求解不固定維度之32位元浮點數矩陣，並且計算時間都呈現符合n3問題複雜度。受到記憶體容量限制，硬體解法器驗證之最大矩陣維度為63，可在16.15毫秒內求解完畢，軟體解法器最大驗證維度則為50，所需時間為0.18秒。 序列式演算法之硬體解法器與解法器嵌入式系統成功地提供了在CPU以外求解矩陣的兩種解決方案，硬體解法器可獲得較好的計算效率，而解法器嵌入式系統方案則有較短的開發流程。本研究所提出之迭代演算法硬體平行架構雖未加以驗證，但希望在未來修正適當的記憶體元件規劃，求得此演算法之平行效率。This research introduces two ways to implement a matrix solver on FPGA: one way is to design a hardware solver with VHDL, the other to develop a embedded solver system by programming soft core processor MicroBlaze. To utilize parallel advantage of FPGA, we design a pipeline architecture according to the parallelism of Jacobi Iteration, and discuss the computing complexity and limits on parallelism of the sequential algorithm Gauss-Jordan Elimination. We adopt serial handshake protocols for matrix data I/O, where a terminal program on PC transmit data through RS232 port and receive data returned by FPGA. We implement the sequential algorithm on both hardware solver and embedded solver system. Both solvers can solve a 32bit float number matrix of free dimension, with computing time correspond with the complexity of order n3. With limited on-board RAM, the max matrix dimension we can exam in this study is 63 on hardware solver, which takes 16.15ms for solving, and 50 on embedded solver system, which takes 0.18s for solving. This study successfully provides two solutions to solve matrix without CPU. The hardware solver shows better computing performance, and the embedded solver system takes shorter development process. Although we do not exam our parallel architecture for the iterative algorithm, it is hope that the task can be achieved in the future with proper RAM module planning.誌 謝 I 摘 要 II ABSTRACT III 第一章 緒論 1 1.1 研究動機 1 1.1.1 線性代數運算加速之可行方案 1 1.1.2 利用晶片設計求解線性代數之發展狀況 2 1.2 研究目的 4 1.3 論文架構 4 第二章 以FPGA為驗證平台之嵌入式系統開發環境 6 2.1 可程式化邏輯閘陣列(FPGA)與VHDL 6 2.1.1 FPGA簡介 6 2.1.2 VHDL背景 7 2.2 嵌入式系統開發環境 9 2.2.1 嵌入式系統與處理器應用簡介 9 2.2.2 Xilnx 嵌入式系統開發環境工具 10 2.2.3 MicroBlazeTM與周邊連結架構 11 2.3 小結 13 第三章 迭代演算法與序列式矩陣解法器 15 3.1 迭代演算法矩陣解法器 15 3.1.1 Jacobi Iteration 15 3.1.2 迭代演算法的平行策略與架構 16 3.1.3 使用連乘加器的平行策略與架構 19 3.2 序列式矩陣解法器 24 3.2.1 Gauss-Jordan Elimination 24 3.2.2 序列式解法器狀態控制分析 25 3.2.3 元件規劃與演算法平行特性 28 3.3 解法器元件架構與運算時間 30 3.3.1 不同架構之效率及所需資源比較 30 3.3.2 記憶體管理 33 第四章 系統架構設計與實作 37 4.1 PC端傳輸接收之應用程式設計 37 4.1.1 數據傳輸時序 37 4.1.2 RS232傳輸協定 37 4.1.3 Com Port物件設計 39 4.2 以VHDL開發之硬體矩陣解法器設計 42 4.2.1 32位元浮點數運算 42 4.2.2 32位元浮點數乘法器 43 4.2.3 32位元浮點數加法器 45 4.2.4 32位元浮點數除法器 46 4.2.5 UART模組 47 4.2.6 RAM元件 50 4.2.7 演算法狀態管理與實作 50 4.3 在MicroBlaze上開發之軟體矩陣解法器系統設計 55 4.3.1 MicroBlaze的物件型別與函式 55 4.3.2 接收與傳輸函式 56 4.3.3 系統設計 58 第五章 測試數據與效率 59 5.1 解法器之測試方法 59 5.1.1 解法器正確性 59 5.1.2 解法器之效率實測方法 60 5.2 解法器之測試結果 61 5.2.1 解法器效率測試結果分析 61 5.2.2 軟體與硬體解法器演算法以外效率比較與分析 67 5.3 小結 69 第六章 結論與未來展望 71 6.1 結論與貢獻 71 6.2 未來工作 73 參考文獻 76 附錄 A 程式碼摘錄 78 附錄 B FPGA燒錄檔下載與測試 831588887 bytesapplication/pdfen-US線性代數FPGAVHDL平行計算嵌入式系統軟核處理器linear algebraparallel computingembedded systemsoft core processorthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/50516/1/ntu-95-R92521607-1.pdf