[發(fā)明專利]一種基于混合QR分解的最小二乘FPGA求解裝置

有效

• 申請?zhí)枺?/td>: 201010139742.4
• 申請日: 2010-04-01
• 公開（公告）號: CN101827044A
• 公開（公告）日: 2010-09-08
• 發(fā)明（設計）人: 張顥;陸繼承;李剛;孟華東;王希勤
• 申請（專利權）人: 清華大學
• 主分類號: H04L25/02
• 分類號: H04L25/02
• 代理公司: 北京潤澤恒知識產權代理有限公司 11319
• 代理人: 蘇培華

技術領域

本發(fā)明涉及數值計算與集成電路技術領域，特別是涉及一種基于混合QR分解的最小二乘FPGA求解裝置。?

背景技術

最小二乘法(又稱最小平方法)是一種數學優(yōu)化技術，是數值計算中最基礎也是最常用的計算方法之一，它通過最小化誤差的平方和尋找數據的最佳函數匹配。利用最小二乘法可以簡便地求得未知的數據，并使得這些求得的數據與實際數據之間誤差的平方和為最小。?

通常，最小二乘法包括基于QR分解、基于逆QR分解和基于混合QR分解這三類算法。?

例如，基于QR分解的脈動陣列實現方法，在脈動陣列中引入吉文斯(Givens)旋轉操作，使得脈動陣列中兩類運算單元具有相似的結構。該算法在完成Givens旋轉之后還要做一個三角陣求逆運算(回代步驟)，計算量較大，并且，整個脈動陣列需要矩陣階數平方量級的運算單元，對于硬件資源的消耗較大。?

又如，基于QR分解算法的IP核實現方法，采用模塊復用的思想，用較少的運算單元來實現整個脈動陣列的功能。該方法通過一系列的旋轉、折疊操作，將上三角陣轉化為具有規(guī)則形狀(矩形或平行四邊形)的陣列，然后再將陣列進行壓縮復用，達到了很高復用效率。此外，由于變換后陣列是規(guī)則的，因此對陣列的壓縮復用具有一定的任意性，即可以根據最小二乘問題的規(guī)模和實現器件的硬件資源來選定橫向和縱向的壓縮比例。模塊復用的思想很好的解決了脈動陣列資源消耗大的問題，使得最小二乘在FPGA上實現成為可能。但是由于該IP核的實現方法是基于QR分解算法，因此在完成旋轉操作后仍具要進行回代步驟，計算量很大。?

再如，基于QR分解的線性陣列實現方法，使用CORDIC模塊在FPGA上實現了線性陣列，將回代步驟放在Altera公司的NIOS軟處理器上實現。?其缺點是并沒有完全避免回代步驟，而且不同平臺的處理使得數據的交互變得復雜，也會影響計算性能。?

此外，基于逆QR分解和基于混合QR分解的實現方法，巧妙的避免了QR分解算法中的回代步驟，減少了計算量。但是在現有技術中，上述算法中對應的脈動陣列與QR分解的脈動陣列一樣，需要消耗較大的硬件資源；并且，由于逆QR分解算法非常的復雜，在硬件實現中有一定的難度。?

總之，需要本領域技術人員迫切解決的一個技術問題就是：如何能夠提供一種最小二乘的FPGA實現方法，減少計算量，并且避免消耗較大的硬件資源。?

發(fā)明內容

本發(fā)明所要解決的技術問題是提供一種基于混合QR分解的最小二乘FPGA求解裝置，減少計算量，并且避免消耗較大的硬件資源。?

為了解決上述問題，本發(fā)明公開了一種一種基于混合QR分解的最小二乘FPGA求解裝置，針對Ax＝b的混合求解，A為M×N維矩陣，b為M維向量，所述裝置包括求角單元和N+1個旋轉單元；?

求角單元，用于將脈動陣列上三角陣列的對角線元素作為實部，將矩陣A的第K行轉置的第一個元素或者該對角線元素上一行元素通過旋轉單元更新后得到的虛部作為虛部，組成復數，通過計算該復數的幅角和模，將模更新為當前對角線元素，并將幅角同時輸入至各個旋轉單元進行該行元素的更新；?

N+1個旋轉單元，用于分別將脈動陣列中同一行的上三角陣列的非對角線元素、下三角陣列的元素和線性陣列元素作為N+1個實部，將矩陣A的第K行轉置的第二至第N個元素、0、向量b的第K個元素或者實部元素的上一行元素通過旋轉單元更新得到的虛部作為N+1個虛部，組成N+1個復數，根據求角單元獲得的幅角同時對各個復數進行角度旋轉，將實部更新為當前元素，并將虛部輸入至該元素對應下一行的元素的更新中；?

其中，所述求角單元和旋轉單元依次對脈動陣列的各行元素執(zhí)行操作，?直到各個元素更新完成。?

優(yōu)選的，所述求角單元包括：?

第一實部輸入端，用于輸入數據1或者第一實部輸出端回傳的數據；?

第一虛部輸入端，用于輸入矩陣A的第K行轉置的第一個元素或者第一個旋轉單元回傳的數據；?

求角子單元，用于計算第一實部輸入端和第一虛部輸入端輸入數據組成的復數的幅角以及當前復數的模，并將所述幅角同時輸入至N+1個旋轉單元中；?

第一實部輸出端，用于輸出當前復數的模，以及將輸出的模保存在求角寄存器中并回傳更新至該求角單元的第一實部輸入端。?

優(yōu)選的，所述旋轉單元包括：?

第二實部輸入端，用于輸入數據0、1或者該旋轉單元的第二實部輸出端回傳的數據；?