[發明專利]基于FPGA的高級綜合實現擬牛頓算法加速的方法

在審

• 申請號: 201611035499.5
• 申請日: 2016-11-19
• 公開（公告）號: CN106775905A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 劉強;馬磊
• 申請（專利權）人: 天津大學
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 天津市北洋有限責任專利代理事務所12201
• 代理人: 程小艷

技術領域

本發明涉及擬牛頓算法(Quasi-Newton，QN)加速技術,具體涉及一種基于現場可編程門陣列(Field Programmable Gate Arrays，FPGA)的高層次綜合(High Level Synthesis，HLS)工具優化加速擬牛頓算法的方法。

背景技術

擬牛頓算法是一種求解非線性優化最有效的方法，被廣泛應用于各種領域，如：隨機優化，集成電路布局和電力系統的加載頻率控制。這些應用的關鍵性因素是在有限的時間內獲得最優的解決方案。然而擬牛頓算法由于內部含有大量的迭代算法導致耗時嚴重。所以，對擬牛頓算法的加速是一個重要的研究方向。

隨著FPGA的快速發展，現在的FPGA平臺擁有更多的資源，操作頻率能夠達到上百MHz。FPGA器件具有可重配置，高并行度，設計靈活(相對與專用集成電路)的特性(見文獻[1])，更適合應用于嵌入式場合，FPGA被認為是加速計算量大的應用的最佳選擇，例如人工神經網絡和圖譜計算(見文獻[2]及[3])。與其他普適性的計算架構相比，FPGA允許定制化的計算架構和針對特定應用算法的內存子系統。在FPGA內部進行復雜的時序設計一般需要狀態機進行開發，這需要花費較多的時間進行分析與設計，而且軟件工程師在利用高層次語言C，C++進行開發與硬件工程師利用RTL設計語言設計電路的背景知識存在一定的差距。這導致了FPGA的開發比傳統的單片機開發有很大的不同，開發比較困難(見文獻[4])。

高層次綜合是一種將高層次語言有效地轉化為滿足設計約束的寄存器傳輸級(Register Transfer Level，RTL)描述的工具。HLS提高了硬件設計的抽象層次，具有以下突出優點(見文獻[5])：1)硬件工程師可以減少設計時間，縮短產品上市周期；2)軟件工程師能完成硬件系統設計；3)溝通了軟件設計和硬件設計兩個領域，展現了一種軟硬件聯合設計的方法，HLS被認為是下一代半導體工業中的核心角色，在企業界和學術界受到越來越多的關注。

發明內容

本發明的目的在于克服上述現有技術的不足，從加速擬牛頓算法出發，利用高層次綜合實現擬牛頓算法，通過FPGA實現對擬牛頓算法加速,降低了FPGA的開發難度。

本發明的技術方案：基于FPGA的高級綜合實現擬牛頓算法加速的方法,包括以下步驟：

(1)、分析擬牛頓算法的功能，劃分出擬牛頓算法的主要計算模塊；

(2)、利用高級語言C，C++實現上述步驟(1)中的各個模塊，并且驗證算法功能的正確性；

(3)、將上述步驟(2)功能驗證正確的擬牛頓算法作為輸入文件，利用高層次綜合工具，將高級語言轉化為RTL級語言，驗證生成的RTL代碼；

(4)、將生成的RTL代碼制作成比特流文件，下載配置到FPGA的可配置邏輯部分。

所述步驟(1)分析擬牛頓算法的功能，將算法劃分成三個主要計算模塊，分別是梯度計算模塊Compute_grad，矩陣更新模塊QN_formula和線性搜索模塊Line_search；矩陣更新模塊以BFGS方式更新矩陣并決定搜索方向，線性搜索模塊采用黃金分割法在搜索方向上確定搜索步長，梯度計算模塊完成目標函數梯度的計算；另外目標函數Object_function是擬牛頓算法需要求解的目標函數；片外存儲單元Off-chip DRAM是用來存儲計算工程中需要的計算信息；計算控制單元Computation Scheduling controller是來安排上述幾個模塊的操作順序及內存與相對應模塊的數據傳遞。

所述步驟(2)設計的算法考慮到擬牛頓算法的通用性，將不同的算法結構參數化。

所述步驟(2)利用visual studio 2013運行實現的算法，以驗證算法功能的正確性。

所述步驟(3)利用高層次綜合工具的優化方法來對算法進行優化，優化結果滿足設計約束，不僅RTL代碼正確，而且運行速度達到預期，其中優化包括代碼轉換和指令優化，并利用高級綜合工具自帶的軟硬件聯合仿真驗證生成的RTL代碼的正確性。

所述步驟(4)FPGA型號為Net-FPGA SUME(xc7vx690t)，對算法的資源利用和運行時間分別作性能測試。

本發明相對于現有技術有以下有益效果：本發明通過高層次綜合工具將C，C++設計的擬牛頓算法轉化為RTL代碼，并在Net-FPGA SUME(xc7vx690t)開發板上綜合實現。本發明可達到的有益效果為：