請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34535
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳俊杉(Chuin-Shan Chen) | |
dc.contributor.author | Chiu-Fen Ting | en |
dc.contributor.author | 丁久棻 | zh_TW |
dc.date.accessioned | 2021-06-13T06:13:47Z | - |
dc.date.available | 2006-02-09 | |
dc.date.copyright | 2006-02-09 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-02-07 | |
dc.identifier.citation | Fithian, W. S., Brown, S., Singleterry, R. C., and Storaasli, O. O. (2002), “Iterative Matrix Equation Solver for a Reconfigurable FPGA-Based Hypercomputer®,” NASA/CR-2002-000000.
Grama, A., Gupta, A., Karypis, G. and Kumar, V. (2003). Introduction to Parallel Computing, Addison Wesley, pp. 352-366. Lopez, J. C., Hermida, R., Geisselhardt, W.(1998), Advanced Techniques for Embedded Systems Design and Test, Kluwer Academic Publishers, pp. 1-30. Lynch, J. P. (2005), “Design of a Wireless Active Sensing Unit for Localized Structural Health Monitoring,” Journal of Structural Control and Health Monitoring, 12(3-4): 405-423. Memec Design (2004), “Memec Spartan-3 LC User’s Guide v2.0”. McGuire, W., Grallagher, R. H., and Ziemian, R. D. (2000). Matrix Structural Analysis, John Wiley & Sons, pp. 326-329. Niemann, R. (1998), Hardware/Software Co-Design for Data Flow Dominated Embedded Systems, Kluwer Academic Publishers Press, W. H., Teukolsky, S. A., Vetterling, W. T., Flannery, B. P. (2002). Numerical Recipies in C++ The Art of Scientific Computing, Cambridge University Press, pp. 39-45. Rajsuman, R. (2000), System-on-a-chip : design and test, Advantest America R&D Center, Inc., pp. 3-55, pp. 106. Singleterry, R. C. Jr., Sobieszczanski-Sobieski, J., and Brown, S. (2002), “Field-Programmable Gate Array Computer in Structural Analysis : an Initial Exploration,” 43rd American Institute of Aeronautics and Astronautics (AIAA) Structures, Structural Dynamics, and Materials Conference. April 22-25, AIAA-2002-1761. Wilson, G. R. (2002), Embedded Systems & Computer Architecture, Newnes, pp. 1-67, pp. 145-147. Wolf, W. (2001), Computers as Components: Principles of Embedded Computing System Design, Morgan Kaufmann publishers, pp. 2-10. Wolf, W. (2002), Modern VLSI Design System-on-Chip Design, Prentice Hall, pp. 400-422. Xilinx (2004), “MicroBlaze Example design”. 范逸之、江文賢、陳立元 (2001), C++ Builder與RS-232串列通訊控制, 文魁資訊, pp. 1-2 - 1-41 許博堯 (2000), “平行稀疏矩陣求解法在有限元素結構分析之應用研究”, 碩士論文, 國立臺灣大學土木工程學研究所, 台北。 韓志成(2000), “以丘列斯基分解法實現通道等化器之設計”, 碩士論文, 雲林科技大學電子工程與資訊工程技術研究所, 雲林。 鄭信源 (2003), VHDL數位電路設計-進階篇, 儒林, pp. 14-2 - 14-41 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34535 | - |
dc.description.abstract | 本研究提出兩種以FPGA實作矩陣解法器方法,分為以VHDL直接設計硬體解法器,和編程軟核處理器MicroBlaze設計解法器嵌入式系統。為發揮FPGA的平行特性,我們根據迭代式演算法Jacobi Iteration平行特性設計管線式連乘加器架構,並探討序列式演算法Gauss-Jordan Elimination的問題複雜度與演算法平行限制。矩陣資料I/O方面,本研究採取序列式傳輸協定,由個人電腦端應用程式透過RS232埠傳送矩陣數據並接收FPGA回傳數據。硬體解法器與嵌入式系統之軟體解法器皆採用序列式演算法,可求解不固定維度之32位元浮點數矩陣,並且計算時間都呈現符合n3問題複雜度。受到記憶體容量限制,硬體解法器驗證之最大矩陣維度為63,可在16.15毫秒內求解完畢,軟體解法器最大驗證維度則為50,所需時間為0.18秒。
序列式演算法之硬體解法器與解法器嵌入式系統成功地提供了在CPU以外求解矩陣的兩種解決方案,硬體解法器可獲得較好的計算效率,而解法器嵌入式系統方案則有較短的開發流程。本研究所提出之迭代演算法硬體平行架構雖未加以驗證,但希望在未來修正適當的記憶體元件規劃,求得此演算法之平行效率。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T06:13:47Z (GMT). No. of bitstreams: 1 ntu-95-R92521607-1.pdf: 1588887 bytes, checksum: bff235b20b77ddada09218a1f631ba49 (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | 誌 謝 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燒錄檔下載與測試 83 | |
dc.language.iso | zh-TW | |
dc.title | 以可程式化邏輯閘陣列開發矩陣解法器 | zh_TW |
dc.title | Development of Matrix Solver on Field Programmable Gate Array | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 謝尚賢(Shang-Hsien Hsieh),羅俊雄(Chin-Hsiung Loh) | |
dc.subject.keyword | 線性代數,FPGA,VHDL,平行計算,嵌入式系統,軟核處理器, | zh_TW |
dc.subject.keyword | linear algebra,FPGA,VHDL,parallel computing,embedded system,soft core processor, | en |
dc.relation.page | 85 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-02-07 | |
dc.contributor.author-college | 工學院 | zh_TW |
dc.contributor.author-dept | 土木工程學研究所 | zh_TW |
顯示於系所單位: | 土木工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 1.55 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。