Development of Matrix Solver on Field Programmable Gate Array

本研究提出兩種以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.