一種基於混合qr分解的最小二乘fpga求解裝置的製作方法
2023-06-27 03:34:26
專利名稱：：一種基於混合qr分解的最小二乘fpga求解裝置的製作方法
技術領域：
：本發明涉及數值計算與集成電路
技術領域：
，特別是涉及一種基於混合QR分解的最小二乘FPGA求解裝置。
背景技術：
：最小二乘法(又稱最小平方法)是一種數學優化技術，是數值計算中最基礎也是最常用的計算方法之一，它通過最小化誤差的平方和尋找數據的最佳函數匹配。利用最小二乘法可以簡便地求得未知的數據，並使得這些求得的數據與實際數據之間誤差的平方和為最小。通常，最小二乘法包括基於QR分解、基於逆QR分解和基於混合QR分解這三類算法。例如，基於QR分解的脈動陣列實現方法，在脈動陣列中引入吉文斯(Givens)旋轉操作，使得脈動陣列中兩類運算單元具有相似的結構。該算法在完成Givens旋轉之後還要做一個三角陣求逆運算(回代步驟)，計算量較大，並且，整個脈動陣列需要矩陣階數平方量級的運算單元，對於硬體資源的消耗較大。又如，基於QR分解算法的IP核實現方法，採用模塊復用的思想，用較少的運算單元來實現整個脈動陣列的功能。該方法通過一系列的旋轉、摺疊操作，將上三角陣轉化為具有規則形狀(矩形或平行四邊形)的陣列，然後再將陣列進行壓縮復用，達到了很高復用效率。此外，由於變換後陣列是規則的，因此對陣列的壓縮復用具有一定的任意性，即可以根據最小二乘問題的規模和實現器件的硬體資源來選定橫向和縱向的壓縮比例。模塊復用的思想很好的解決了脈動陣列資源消耗大的問題，使得最小二乘在FPGA上實現成為可能。但是由於該IP核的實現方法是基於QR分解算法，因此在完成旋轉操作後仍具要進行回代步驟，計算量很大。再如，基於QR分解的線性陣列實現方法，使用CORDIC模塊在FPGA上實現了線性陣列，將回代步驟放在Altera公司的NIOS軟處理器上實現。其缺點是並沒有完全避免回代步驟，而且不同平臺的處理使得數據的交互變得複雜，也會影響計算性能。此外，基於逆QR分解和基於混合QR分解的實現方法，巧妙的避免了QR分解算法中的回代步驟，減少了計算量。但是在現有技術中，上述算法中對應的脈動陣列與QR分解的脈動陣列一樣，需要消耗較大的硬體資源；並且，由於逆QR分解算法非常的複雜，在硬體實現中有一定的難度。總之，需要本領域技術人員迫切解決的一個技術問題就是如何能夠提供一種最小二乘的FPGA實現方法，減少計算量，並且避免消耗較大的硬體資源。
發明內容本發明所要解決的技術問題是提供一種基於混合QR分解的最小二乘FPGA求解裝置，減少計算量，並且避免消耗較大的硬體資源。為了解決上述問題，本發明公開了一種一種基於混合QR分解的最小二乘FPGA求解裝置，針對Ax=b的混合求解，A為MXN維矩陣，b為M維向量，所述裝置包括求角單元和N+1個旋轉單元；求角單元，用於將脈動陣列上三角陣列的對角線元素作為實部，將矩陣A的第K行轉置的第一個元素或者該對角線元素上一行元素通過旋轉單元更新後得到的虛部作為虛部，組成複數，通過計算該複數的幅角和模，將模更新為當前對角線元素，並將幅角同時輸入至各個旋轉單元進行該行元素的更新；N+1個旋轉單元，用於分別將脈動陣列中同一行的上三角陣列的非對角線元素、下三角陣列的元素和線性陣列元素作為N+1個實部，將矩陣A的第K行轉置的第二至第N個元素、0、向量b的第K個元素或者實部元素的上一行元素通過旋轉單元更新得到的虛部作為N+1個虛部，組成N+1個複數，根據求角單元獲得的幅角同時對各個複數進行角度旋轉，將實部更新為當前元素，並將虛部輸入至該元素對應下一行的元素的更新中；其中，所述求角單元和旋轉單元依次對脈動陣列的各行元素執行操作，直到各個元素更新完成。優選的，所述求角單元包括第一實部輸入端，用於輸入數據1或者第一實部輸出端回傳的數據；第一虛部輸入端，用於輸入矩陣A的第K行轉置的第一個元素或者第一個旋轉單元回傳的數據；求角子單元，用於計算第一實部輸入端和第一虛部輸入端輸入數據組成的複數的幅角以及當前複數的模，並將所述幅角同時輸入至N+1個旋轉單元中；第一實部輸出端，用於輸出當前複數的模，以及將輸出的模保存在求角寄存器中並回傳更新至該求角單元的第一實部輸入端。優選的，所述旋轉單元包括第二實部輸入端，用於輸入數據0、1或者該旋轉單元的第二實部輸出端回傳的數據；第二虛部輸入端，用於針對第L個旋轉單元輸入矩陣A的第K行轉置的第L+1個元素或者輸入第L+1個旋轉單元的第二虛部輸出端回傳的數據，L=1，2，...，N-I；其中，第N個旋轉單元的第二虛部輸入端輸入0；第N+1個旋轉單元的第二虛部輸入端輸入向量b的第K個元素或者該旋轉單元的第二虛部輸出端回傳的數據；旋轉子單元，用於根據求角單元獲得的幅角對第二實部輸入端和第二虛部輸入端輸入數據組成的複數進行角度旋轉運算操作；第二實部輸出端，用於輸出複數轉旋後得到的實部，並將輸出的實部保存在旋轉寄存器中並回傳更新至該旋轉單元的第二實部輸入端；第二虛部輸出端，用於輸出複數轉旋轉後得到的虛部，並將輸出的虛部回傳更新至前一個旋轉單元的第二虛部輸入端；其中，第一個旋轉單元的第二虛部輸出端輸出的虛部回傳更新至求角單元的第一虛部輸入端；第N+1個旋轉單元的第二虛部輸入端輸出的虛部回傳更新至該旋轉單元的第二虛部輸入端。優選的，所述第二虛部輸入端設置有延遲器，用於控制進行輸入數據的時間延遲，所述輸入數據的時間延遲為求角子單元進行求角運算的時間。進一步，所述求角寄存器中保存的各個數據更新為脈動陣列上三角陣列的對角線元素。進一步，與N+1個旋轉單元對應的旋轉寄存器中保存的數據分別更新為與上三角陣列更新後的對角線元素同一行的N+1個元素。優選的，所述裝置還包括信號控制單元，用於在第一實部輸入端、第一虛部輸入端、第二實部輸入端和第二實部輸入端施加選擇控制信號，進行數據的選擇輸入。優選的，所述信號控制單元施加的選擇控制信號具體為當t=i(2Tcoe+1),i=0,1,...,N-I時，第一實部輸入端的選擇控制信號為1，此夕卜，該選擇控制信號為0;當t=i(TC0E+1)，i=0，1，...，M-I時，第一虛部輸入端的選擇控制信號為1，此夕卜，該選擇控制信號為0;第二實部輸入端的選擇控制信號比第一實部輸入端的選擇控制信號延遲Ttok個周期；第二虛部輸入端的選擇控制信號與第一虛部輸入端的選擇控制信號的輸入相同；其中，選擇控制信號的時間延遲為1，求角子單元和旋轉子單元進行運算操作的時間均為TroK。優選的，所述信號控制單元控制數據的輸入具體為第一實部輸入端的選擇控制信號為1時，控制輸入數據1；第一實部輸入端的選擇控制信號為0時，控制輸入第一實部輸出端回傳的數據；第一虛部輸入端的選擇控制信號為1時，控制輸入矩陣A的第K行轉置的第一個元素；第一虛部輸入端的選擇控制信號為0時，控制輸入第一個旋轉單元的第二虛部輸出端回傳的數據；第二實部輸入端的選擇控制信號為1時，控制輸入數據0，其中，僅針對第N個旋轉單元的第二實部輸入端，控制輸入數據1；第二實部輸入端的選擇控制信號為0時，控制輸入該旋轉單元的第二實部輸出端回傳的數據；針對第L個旋轉單元，第二虛部輸入端的選擇控制信號為1時，控制輸入矩陣A的第K行轉置的第L+1元素；第二虛部輸入端的選擇控制信號為0時，控制輸入第L+1個旋轉單元的第二虛部輸出端回傳的數據；針對第N個旋轉單元，第二虛部輸入端的選擇控制信號為0或1時，均控制輸入數據0；針對第N+1個旋轉單元，第二實部輸入端的選擇控制信號為1時，控制輸入向量b的第K個元素；第二虛部輸入端的選擇控制信號為0時，控制輸入該旋轉單元的第二虛部輸出端回傳的數據。優選的，所述信號控制單元還用於對求角子單元和旋轉子單元施加使能控制信號，控制進行求角或者角度旋轉的運算操作。優選的，所述信號控制單元施加的使能信號具體為當t=i(TC0E+l)+j(2TC0E+l)+l,i=0，1，···，M-l，j=0，1，···，N-I時，求角子單元的使能控制信號為1，此外，求角子單元的使能控制信號為0；其中，旋轉子單元的使能控制信號比求角單元的使能控制信號延遲Τωκ個周期。與現有技術相比，本發明具有以下優點(1)減少了計算量。本發明使用混合QR分解算法，避免了回代步驟，大大減少了最小二乘中的計算量。對於一個MXN維的計算問題，只需要麗(Ν+2)次基本操作，求角或旋轉操作，其複雜度與乘法操作同級。同時，本發明在FPGA中引入了大量的並行化操作和深度流水線技術，使得完成整個最小二乘計算僅需要Μ+2Ν個基本操作時間。(2)節省了硬體資源。實現本發明所需的FPGA內的邏門輯資源要求不高，對比傳統的脈動陣列的實現方法，本發明提出的線性陣列結構，不但與之擁有完全一樣的計算性能，而且邏輯資源僅為脈動陣列的N分之一，減少了硬體成本。(3)實現簡單。由於本發明使用混合QR分解，在脈動陣列實現上擁有比QR分解和逆QR分解更加整齊的結構，因此在向線性陣列結構轉化過程中，省去了很多映射和摺疊的操作，而在數據流向的控制上也要簡單很多。圖1是本發明一種基於混合QR分解的最小二乘FPGA求解裝置實施例的示意圖；圖2是一個4階的脈動陣列示意圖；圖3是脈動陣列的工作時序示意圖；圖4是本發明一種基於混合QR分解的最小二乘FPGA求解裝置優選實施例的結構示意圖。具體實施例方式為使本發明的上述目的、特徵和優點能夠更加明顯易懂，下面結合附圖和具體實施方式對本發明作進一步詳細的說明。本發明的核心構思之一在於採用混合QR分解的迭代方法來實現最小二乘，在傳統的脈動陣列的基礎上提出了線性陣列結構，使得最小二乘能夠以較少的邏輯資源在FPGA上高效的實現。對於一個最小二乘問題，數學上表現為一個過定方程組Ax=b；其中，A為MXN維的矩陣，M>N，x是要求的N維未知向量，b為M維向量。記τ為矩陣A的第i行數據，其中，上標T表示對向量或矩陣的轉置；記h為向量b的第i個元素。則混合QR分解算法如表1所示表1混合QR分解算法tableseeoriginaldocumentpage9本發明基於上述算法，以脈動陣列實現方法為基礎，結合模塊復用的思想，將脈動陣列壓縮為線性陣列結構，實現最小二乘的功能，在FPGA晶片上依次按以下步驟實現步驟一，使用坐標旋轉數字計算(CORDIC，CoordinateRotationDigitalComputer)模塊生成兩類基本運算單元，分別為求角單元(或稱為邊界單元，BoundaryCell)和旋轉單元(或稱為內部單元,InternalCell)，簡稱為BC和IC。其中BC實現複數(x+jy)的求角運算操作，IC實現複數(x+jy)的旋轉運算操作。步驟二，使用這兩類基本運算單元組成一個脈動陣列。在脈動陣列中用一個上三角陣列來保存和更新Rk，其中對角線位置為IC，其他位置為BC;用一個下三角陣列和一個線性陣列來保存和更新Λ和zk，其中所有位置都為BC。對於每一步輸入的akT和bk，脈動陣列實現下式的功能formulaseeoriginaldocumentpage9其中Qk內的角度參數是由IC計算得到的。步驟三，將脈動陣列轉化為線性陣列。由於脈動陣列對硬體資源的消耗非常大，無法直接在FPGA上實現。通過分析脈動陣列的工作時序，發現在整個流水線中，有很多的時間處於不工作狀態，即使用效率非常低，這就使得在對脈動陣列採用模塊復用後仍然可以維持相同的計算性能。根據脈動陣列的結構特點(上三角陣列加下三角陣列為一個平行四邊形陣列)，每一行運算單元(求角單元和旋轉單元)都有相同的內部結構和外部接口，因此，本發明復用一行的運算單元，將流向下一行的數據重新引回這一行，這樣就可以只用一行的運算單元來實現整個脈動陣列的功能，稱之為線性陣列。參照圖1，示出了本發明一種基於混合QR分解的最小二乘FPGA求解裝置實施例的示意圖，針對Ax=b的混合求解，A為MXN維矩陣，b為M維向量，所述裝置包括求角單元和N+1個旋轉單元；求角單元101，用於將脈動陣列上三角陣列的對角線元素作為實部，將矩陣A的第K行轉置的第一個元素或者該對角線元素上一行元素通過旋轉單元更新後得到的虛部作為虛部，組成複數，通過計算該複數的幅角和模，將模更新為當前對角線元素，並將幅角同時輸入至各個旋轉單元進行該行元素的更新；N+1個旋轉單元102，用於分別將脈動陣列中同一行的上三角陣列的非對角線元素、下三角陣列的元素和線性陣列元素作為N+1個實部，將矩陣A的第K行轉置的第二至第N個元素、0、向量b的第K個元素或者實部元素的上一行元素通過旋轉單元更新得到的虛部作為N+1個虛部，組成N+1個複數，根據求角單元獲得的幅角同時對各個複數進行角度旋轉，將實部更新為當前元素，並將虛部輸入至該元素對應下一行的元素的更新中；其中，所述求角單元和旋轉單元依次對脈動陣列的各行元素執行操作，直到各個元素更新完成。下面，對本發明實施例進行具體說明。本發明實施例提出的求解裝置是由兩類基本運算單元構成，求角單元(或BC)和旋轉單元(或IC)。formulaseeoriginaldocumentpage10如上述左邊所示，圓形求角單元BC中保存有數據X，對於輸入的數據y，將計算複數(x+jy)的幅角θ=31~(^￡111(7/^)，並更新乂為比080+75^119，最後肌將幅角θ輸出給IC。實際上，BC是將複數(x+jy)旋轉至實數軸，其旋轉的角度就是幅角θ，而旋轉後得到的實數即為元複數的模，其作為更新後的X。如上述右邊所示，方形旋轉單元IC中保存有數據χ，對於輸入的數據y和由求角單元得到的幅角9，將更新1為比080+75^119，並計算7』=yC0Se-xsine，最後IC將幅角θ和計算結果y』輸出。實際上，IC是將複數(x+jy)旋轉角度θ，旋轉後的複數，其實部即為更新後的χ，虛部則為輸出的r。因此，BC和IC都是實現等幅旋轉功能，前者為旋轉求角，後者為已知角度做旋轉。這兩個單元在實際應用中可以用CORDIC模塊來實現。例如，在Xilinx公司出品的開發軟體ISE中集成了具有CORDIC功能的IPcore，可以直接用於實現上述兩個運算單元。脈動陣列結構實現有了上述兩個基本運算單元，就可以組成實現混合QR分解的脈動陣列結構，如圖2所示，為一個4(N=4)階的脈動陣列示意圖。脈動陣列由一個上三角陣，一個下三角陣和右邊的一個線性陣列組成，分別用於保存和更新每一步遞推過程中的Rk，&和zk。在脈動陣列的一行中，有1個BC和5個IC。對於輸入這行的6個數據(其中1個為0)，BC將本身保存的數據(如U與第1個輸入數據(如Au)組成的複數做等幅旋轉操作，直至輸入數據旋轉為0，而保存的數據則更新為兩者的模(如iRu+jAul)。而旋轉的角度θ將向右同時傳遞給這一行的5個IC，並使這5個IC對自身保存的數據與對應輸入數據做同樣角度的旋轉操作，這樣輸入數據旋轉後的結果將向下一行傳遞，而保存數據則更新後繼續保存。當矩陣A的第k行數據的轉置akT輸入脈動陣列時，陣列中保存的數據為Rk+ig和Zk+而在akT依次經過4行運算單元的更新的同時，陣列中保存的數據亦被更新為Rk，&和zk。整個過程完成了混合QR分解的一步操作。脈動陣列結構分析儘管脈動陣列可以高效的在FPGA上實現混合QR分解算法，但是它需要消耗巨大的邏輯資源。對於一個N階的最小二乘問題，它需要N(N+2)個基本運算單元，這對於實現來說是個很大的瓶頸。如圖3所示，為脈動陣列的工作時序示意圖，其中a/1)，a/2)，L分別表示輸入數據經過第1、2、...行運算單元之後的臨時數據。從時序圖中看到輸入數據在每一行上，從BC輸入到BC輸入角度θ，再到IC向下一層輸出數據的過程，並標識了基本運算單元的延遲，每一行的延遲和輸入數據的間隔。可以發現，脈動陣列的流水線使用率很低，即在整個BC/IC延遲中，只做一次基本操作(求角或旋轉)，而其餘的時鐘周期都是處於空閒狀態，這對於邏輯資源是很大的浪費。本發明根據脈動陣列的原理，提出了線性陣列結構，很好的解決了上述兩個問題。線性陣列結構實現觀察圖2所示的脈動陣列結構，可以看出陣列中的每一行運算單元都擁有相同的內部結構和外部接口，因此本發明實施例復用一行的運算單元，將流向下一行的數據重新引回這一行，這樣就可以只用一行的運算單元來實現整個脈動陣列的功能，稱之為線性陣列。具體的，所述求角單元包括第一實部輸入端，用於輸入數據1或者第一實部輸出端回傳的數據，本發明實施例以「Xinl」進行標註；第一虛部輸入端，用於輸入矩陣A的第K行轉置的第一個元素或者第一個旋轉單元回傳的數據，以「Yinl」進行標註；求角子單元，用於計算第一實部輸入端和第一虛部輸入端輸入數據組成的複數的幅角以及當前複數的模，並將所述幅角同時輸入至N+1個旋轉單元中；第一實部輸出端，用於輸出當前複數的模，以及將輸出的模保存在求角寄存器中並回傳更新至該求角單元的第一實部輸入端，以「Xoutl」進行標註。所述旋轉單元包括第二實部輸入端，用於輸入數據0、1或者該旋轉單元的第二實部輸出端回傳的數據，以「Xin2」進行標註；第二虛部輸入端，用於針對第L個旋轉單元輸入矩陣A的第K行轉置的第L+1個元素或者輸入第L+1個旋轉單元的第二虛部輸出端回傳的數據，L=1,2,...，N-1，以「Yin2」進行標註；其中，第N個旋轉單元的第二虛部輸入端輸入0；第N+1個旋轉單元的第二虛部輸入端輸入向量b的第K個元素或者該旋轉單元的第二虛部輸出端回傳的數據；旋轉子單元，用於根據求角單元獲得的幅角對第二實部輸入端和第二虛部輸入端輸入數據組成的複數進行角度旋轉運算操作；第二實部輸出端，用於輸出複數轉旋後得到的實部，並將輸出的實部保存在旋轉寄存器中並回傳更新至該旋轉單元的第二實部輸入端，以「Xout2」進行標註；第二虛部輸出端，用於輸出複數轉旋轉後得到的虛部，並將輸出的虛部回傳更新至前一個旋轉單元的第二虛部輸入端，以「Yout2」進行標註；其中，第一個旋轉單元的第二虛部輸出端輸出的虛部回傳更新至求角單元的第一虛部輸入端；第N+1個旋轉單元的第二虛部輸入端輸出的虛部回傳更新至該旋轉單元的第二虛部輸入端。進一步，所述求角寄存器中保存的各個數據更新為脈動陣列上三角陣列的對角線元素。與N+1個旋轉單元對應的旋轉寄存器中保存的數據分別更新為，與上三角陣列更新後的對角線元素同一行的N+1個元素。進一步，所述裝置還包括信號控制單元，用於在第一實部輸入端、第一虛部輸入端、第二實部輸入端和第二實部輸入端施加選擇控制信號，進行數據的選擇輸入。進一步，所述信號控制單元還用於對求角子單元和旋轉子單元施加使能控制信號，控制進行求角或者角度旋轉的運算操作。參見圖4，示出了本發明一種基於混合QR分解的最小二乘FPGA求解裝置優選實施例的結構示意圖，在本發明實施例中N取4。所述求解裝置包括求角單元41、五個旋轉單元42和信號控制單元43；其中，求角單元41包括求角子單元411、兩個輸入端Xinl(即第一實部輸入端)412和Yinl(即第一虛部輸入端)413、一個輸出端Xoutl(即第一實部輸出端)414；旋轉單元42包括旋轉子單元421、兩個輸入端Xin2(即第二實部輸入端)422和Yin2(即第二虛部輸入端)423，兩個輸出端Xout2(即第二實部輸出端)424和Yout2(即第二虛部輸出端)425。在求角單元和旋轉單元的實部輸入端和虛部輸入端各有一個選擇器，由信號控制單元進行輸入數據的選擇控制。第一實部輸入端、第一虛部輸入端、第二實部輸入端和第二實部輸入端的控制信號分別標記為BC_selO，BC_sell，IC_selO和IC_sell。求角和角度旋轉運算操作的使能信號標記為BC_En和IC_En。此外，在各個輸出端Xout處各有4個寄存器，用於保存每次運算後輸出的數據，更新為脈動陣列上的各個元素。在旋轉子單元的輸入端Yin2處有一個延遲器426，用於控制進行輸入數據的時間延遲，所述時間延遲為求角子單元進行求角運算的時間。每個運算單元中有X、Y兩路數據。X路是原脈動陣列中保存數據的通路，也就是混合QR分解算法每一步中Rk，&和Zk的數據通路，可以發現X路數據通過求角或是旋轉運算之後又重新回到該運算單元的輸入端Xin處。而Y路是輸入數據和通過每一層運算單元更新後的臨時數據的通路，由於求角運算後y路數據變為零，因此BC沒有輸出端Yout，而Y路數據經過IC的旋轉操作後得到的結果要作為新的輸入數據傳到下一層，因此IClIC4的輸出端Yout要輸出到前一個運算單元(分別對應為BC，IClIC3)的輸入端Yin，而IC5的輸出端Yout則輸出回自身的輸入端Yin。為了使線性陣列能夠正常的工作，我們必須對每個運算單元產生相應的控制信號，如圖4所示，主要是輸入端的選擇控制信號，以及使能控制信號。所有的IC在通道選擇和運算使能的控制上是一樣的。首先要確定各個模塊的時鐘延遲。BC和IC中的選擇器選擇控制信號的延遲時間為1；而本發明實施例中求角子單元和旋轉子單元都是由CORDIC的IPcore實現，因此具有相同的時鐘延遲，記為Trai;IC中的延遲器是為了等待BC中計算出來的角度θ，因此延遲器的時鐘延遲也為TroK。Τωκ的具體數值是由CORDIC的IPcore決定的，它與運算的字長成線性關係，字長越大，延遲則越大。在混合QR分解算法中，初始化時有Rci，瓦為單位陣，Ztl為零向量，因此在對第一組數據進行運算時，X路數據的通路要選擇初始化數據，即selO=1，在其他情況下selO=O。對於N階的最小二乘問題，數據aTk需要通過運算單元N次，每次需要通過一個選擇器、一個求角子子單元和一個旋轉子單元，因此每兩次之間的間隔為1+Τα^+Τ·=2Τ·+1。若令t為當前的時鐘周期數，則當t=i(2Tcoe+1),i=0，1，...，N-I時，BC_selO=1，其他時候BC_selO=O；IC_selO為BC_selO延遲Τωκ個周期。在Y路數據中，當外部的新數據到達時，sell=1，在其他情況下sell=0，即選擇回傳的數據。對於行數為M的數據矩陣A，共有M組新數據。當一組數據通過一個選擇器和一個求角子單元後，新的一組數據即可輸入，因此兩組數據間的間隔為l+TroK。則當t=i(Tc0E+I)『i=0，1，···，M_1時，BC_sell=1，其他時候BC_sell=O；IC_sell與BC_sell相同。S卩，所述信號控制單元施加的控制信號具體為當t=i(2TroK+l)，i=0,1,...,N-I時，第一實部輸入端的控制信號為1，此外，第一實部輸入端的控制信號為O；當t=i(TroK+l)，i=0,1,...,M-I時，第一虛部輸入端的控制信號為1，此外，第一虛部輸入端的控制信號為O；第二實部輸入端的控制信號比第一實部輸入端的控制信號延遲Τωκ個周期；第二虛部輸入端的控制信號與第一虛部輸入端的控制信號的輸入相同；其中，選擇控制信號的時間延遲為1，求角子單元和旋轉子單元進行運算操作的時間均為TroK。具體的，所述信號控制單元控制數據的輸入具體為第一實部輸入端的控制信號為1時，控制輸入數據1；第一實部輸入端控制信號為O時，控制輸入第一實部輸出端回傳的數據；第一虛部輸入端的控制信號為1時，控制輸入矩陣A的第K行轉置的第一個元素；第一虛部輸入端的控制信號為O時，控制輸入第一個旋轉單元的第二虛部輸出端回傳的數據；第二實部輸入端的控制信號為1時，控制輸入數據0，其中，僅針對第N個旋轉單元的第二實部輸入端，控制輸入數據1；第二實部輸入端控制信號為O時，控制輸入該旋轉單元的第二實部輸出端回傳的數據；針對第L個旋轉單元，第二虛部輸入端的控制信號為1時，控制輸入矩陣A的第K行轉置的第L+1元素；第二虛部輸入端的控制信號為0時，控制輸入第L+1個旋轉單元的第二虛部輸出端回傳的數據；針對第N個旋轉單元，第二虛部輸入端的控制信號為0或1時，均控制輸入數據0；針對第N+1個旋轉單元，第二實部輸入端的控制信號為1時，控制輸入向量b的第K個元素；第二虛部輸入端控制信號為0時，控制輸入該旋轉單元的第二虛部輸出端回傳的數據。進一步，當新數據或是回傳數據到達求角單元和旋轉單元時，運算使能信號為1，在其他情況下為0。對於一組新輸入的數據，運算單元需要使能N次，每次間隔為2TroK+l，而每組新數據的間隔為TCQK+1，共有M組。因此當t=i(TC0E+l)+j(2TC0E+l)+l,i=0,1,...,M-l，j=0，1，···，N-I時，BC_En=1，其他時候BC_En=0；IC_En為BC_En延遲Tcok個周期。S卩，所述信號控制單元施加的使能信號具體為當t=i(TC0E+l)+j(2TC0E+l)+l,i=0，1，···，M-I,j=0，1，···，N-I時，求角子單元的運算使能信號為1，此外，求角子單元的運算使能信號為0；其中，旋轉子單元的運算使能信號比求角單元的運算使能信號延遲Ttok個周期。下面，舉一個具體例子對選擇控制信號和使能控制信號的輸入進行說明。本實施例中取M=5，N=4，Tcoe=4，則完成一次最小二乘運算的控制信號如表2所示。表2選擇控制信號和使能控制信號輸時間表tableseeoriginaldocumentpage15tableseeoriginaldocumentpage16即，當t=0，9，18，...，27時，第一實部輸入端的控制信號BC_selO=1，此外，BC_selO=0；當t=0，5，10，...，20時，第一虛部輸入端的控制信號BC_sell=1，此外，BC_sell=0；第二實部輸入端的控制信號IC_selO比第一實部輸入端的控制信號BC_selO延遲Tcor個周期，則t=4，13，22，···，31時，IC_selO=1，此外，IC_selO=0；第二虛部輸入端的控制信號與第一虛部輸入端的控制信號的輸入相同則，當t=0,5,10,...,20時，IC_sell=1，此外，IC_sell=0；當t=i5+j9+l=1，6，10，11，···，43，48，i=0，1，···，4，戶0，1，···，3時，求角子單元的運算使能信號BC_En=1，此外，BC_En=0；其中，旋轉子單元的運算使能信號比求角單元的運算使能信號延遲Trai個周期，則t=5，10，14，···，47，52時，IC_En=1，此外，IC_En=0。本發明實施例使用混合QR分解算法，避免了回代步驟，大大減少了最小二乘中的計算量。對於一個MXN維的計算問題，數據akT需要通過運算單元N次，一次需要經過N+2個單元(一個求角單元和N+1個旋轉單元)的運算操作，進一步，需要輸入M次數據akT(k=1,1,...，M)，則總共需要MN(N+2)次基本操作(求角或旋轉操作，其複雜度與乘法操作同級)。同時，在FPGA中本發明引入了大量的並行化操作和深度流水線技術，使得完成整個最小二乘計算的時間為N(2Tcoe+1)+M(Tcoe+1)=(M+2N)Tcoe+(M+N)，則當忽略尾數(M+N)時，僅需要M+2N個基本操作時間(即TeQK)。進一步，儘管本發明計算性能非常強勁，但實現本發明所需的FPGA內的邏輯資源卻要求不高。對比傳統的脈動陣列的實現方法，本發明提出的線性陣列結構，不但與之擁有完全一樣的計算性能，而且邏輯門資源僅為脈動陣列的N分之一，節省可成本，這使得在小型FPGA上實現高階最小二乘成為可能。此外，由於本發明使用混合QR分解，在脈動陣列實現上擁有比QR分解和逆QR分解更加整齊的結構，因此在向線性陣列結構轉化過程中，省去了很多映射和摺疊的操作，而在數據流向的控制上也要簡單很多。本說明書中的各個實施例均採用遞進的方式描述，每個實施例重點說明的都是與其他實施例的不同之處，各個實施例之間相同相似的部分互相參見即可。以上對本發明所提供的一種基於混合QR分解的最小二乘FPGA求解裝置，進行了詳細介紹，本文中應用了具體個例對本發明的原理及實施方式進行了闡述，以上實施例的說明只是用於幫助理解本發明的方法及其核心思想；同時，對於本領域的一般技術人員，依據本發明的思想，在具體實施方式及應用範圍上均會有改變之處，綜上所述，本說明書內容不應理解為對本發明的限制。權利要求一種基於混合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個複數，根據求角單元獲得的幅角同時對各個複數進行角度旋轉，將實部更新為當前元素，並將虛部輸入至該元素對應下一行的元素的更新中；其中，所述求角單元和旋轉單元依次對脈動陣列的各行元素執行操作，直到各個元素更新完成。2.如權利要求1所述的裝置，其特徵在於，所述求角單元包括第一實部輸入端，用於輸入數據1或者第一實部輸出端回傳的數據；第一虛部輸入端，用於輸入矩陣A的第K行轉置的第一個元素或者第一個旋轉單元回傳的數據；求角子單元，用於計算第一實部輸入端和第一虛部輸入端輸入數據組成的複數的幅角以及當前複數的模，並將所述幅角同時輸入至N+1個旋轉單元中；第一實部輸出端，用於輸出當前複數的模，以及將輸出的模保存在求角寄存器中並回傳更新至該求角單元的第一實部輸入端。3.如權利要求2所述的裝置，其特徵在於，所述旋轉單元包括第二實部輸入端，用於輸入數據0、1或者該旋轉單元的第二實部輸出端回傳的數據；第二虛部輸入端，用於針對第L個旋轉單元輸入矩陣A的第K行轉置的第L+1個元素或者輸入第L+1個旋轉單元的第二虛部輸出端回傳的數據，L=1，2，...，N-1；其中，第N個旋轉單元的第二虛部輸入端輸入0；第N+1個旋轉單元的第二虛部輸入端輸入向量b的第K個元素或者該旋轉單元的第二虛部輸出端回傳的數據；旋轉子單元，用於根據求角單元獲得的幅角對第二實部輸入端和第二虛部輸入端輸入數據組成的複數進行角度旋轉運算操作；第二實部輸出端，用於輸出複數轉旋後得到的實部，並將輸出的實部保存在旋轉寄存器中並回傳更新至該旋轉單元的第二實部輸入端；第二虛部輸出端，用於輸出複數轉旋轉後得到的虛部，並將輸出的虛部回傳更新至前一個旋轉單元的第二虛部輸入端；其中，第一個旋轉單元的第二虛部輸出端輸出的虛部回傳更新至求角單元的第一虛部輸入端；第N+1個旋轉單元的第二虛部輸入端輸出的虛部回傳更新至該旋轉單元的第二虛部輸入端。4.如權利要求3所述的裝置，其特徵在於，所述第二虛部輸入端設置有延遲器，用於控制進行輸入數據的時間延遲，所述輸入數據的時間延遲為求角子單元進行求角運算的時間。5.如權利要求2所述的裝置，其特徵在於，所述求角寄存器中保存的各個數據更新為脈動陣列上三角陣列的對角線元素。6.如權利要求4所述的裝置，其特徵在於，與N+1個旋轉單元對應的旋轉寄存器中保存的數據分別更新為與上三角陣列更新後的對角線元素同一行的N+1個元素。7.如權利要求3所述的裝置，其特徵在於，所述裝置還包括信號控制單元，用於在第一實部輸入端、第一虛部輸入端、第二實部輸入端和第二實部輸入端施加選擇控制信號，進行數據的選擇輸入。8.如權利要求7所述的裝置，其特徵在於，所述信號控制單元施加的選擇控制信號具體為當t=i(2Tcoe+1),i=0,1,...,N-l時，第一實部輸入端的選擇控制信號為1，此外，該選擇控制信號為0；當t=i(Tcoe+1)，i=0，1，...，M-1時，第一虛部輸入端的選擇控制信號為1，此外，該選擇控制信號為0；第二實部輸入端的選擇控制信號比第一實部輸入端的選擇控制信號延遲TroK個周期；第二虛部輸入端的選擇控制信號與第一虛部輸入端的選擇控制信號的輸入相同；其中，選擇控制信號的時間延遲為1，求角子單元和旋轉子單元進行運算操作的時間均為TC0ro9.如權利要求8所述的裝置，其特徵在於，所述信號控制單元控制數據的輸入具體為第一實部輸入端的選擇控制信號為1時，控制輸入數據1；第一實部輸入端的選擇控制信號為0時，控制輸入第一實部輸出端回傳的數據；第一虛部輸入端的選擇控制信號為1時，控制輸入矩陣A的第K行轉置的第一個元素；第一虛部輸入端的選擇控制信號為0時，控制輸入第一個旋轉單元的第二虛部輸出端回傳的數據；第二實部輸入端的選擇控制信號為1時，控制輸入數據0，其中，僅針對第N個旋轉單元的第二實部輸入端，控制輸入數據1；第二實部輸入端的選擇控制信號為0時，控制輸入該旋轉單元的第二實部輸出端回傳的數據；針對第L個旋轉單元，第二虛部輸入端的選擇控制信號為1時，控制輸入矩陣A的第K行轉置的第L+1元素；第二虛部輸入端的選擇控制信號為0時，控制輸入第L+1個旋轉單元的第二虛部輸出端回傳的數據；針對第N個旋轉單元，第二虛部輸入端的選擇控制信號為0或1時，均控制輸入數據0；針對第N+1個旋轉單元，第二實部輸入端的選擇控制信號為1時，控制輸入向量b的第K個元素；第二虛部輸入端的選擇控制信號為0時，控制輸入該旋轉單元的第二虛部輸出端回傳的數據。10.如權利要求9所述的裝置，其特徵在於，所述信號控制單元還用於對求角子單元和旋轉子單元施加使能控制信號，控制進行求角或者角度旋轉的運算操作。11.如權利要求10所述的裝置，其特徵在於，所述信號控制單元施加的使能信號具體為當t=i(TC0E+l)+j(2TC0E+l)+l,i=0，1，，M-l，j=0，1，，N-1時，求角子單元的使能控制信號為1，此外，求角子單元的使能控制信號為0；其中，旋轉子單元的使能控制信號比求角單元的使能控制信號延遲TCQR個周期。全文摘要本發明提供了一種基於混合QR分解的最小二乘FPGA求解裝置，包括求角單元，用於將上三角陣列的對角線元素作為實部，將矩陣A的第K行轉置的第一個元素或該元素上一行元素更新得到的虛部作為虛部，通過計算複數的幅角和模，將模更新為當前元素並將幅角輸入各旋轉單元；N+1個旋轉單元，用於將脈動陣列中同一行的非對角線元素作為實部，將矩陣A的第K行轉置的第二至第N個元素、0、向量b的第K個元素或者實部元素上一行元素更新得到的虛部作為N+1個虛部，根據所得幅角對各個複數進行角度旋轉，將實部更新為當前元素並將虛部輸入至下一行元素的更新；依次對脈動陣列的各行元素執行操作直到元素更新完成。通過本發明，減少了計算量並且節省了硬體資源。文檔編號H04L25/02GK101827044SQ20101013974公開日2010年9月8日申請日期2010年4月1日優先權日2010年4月1日發明者孟華東,張顥,李剛,王希勤,陸繼承申請人:清華大學