面向雙精度simd部件的矩陣乘實現方法
2023-09-10 04:44:25 1
專利名稱：面向雙精度simd部件的矩陣乘實現方法
技術領域：
本發明涉及通用微處理器中的SIMD(單指令多數據)部件，尤其指面向雙精度 SIMD部件的矩陣乘實現方法。
背景技術：
通用微處理器晶片的集成度越來越大，在處理器中設計實現支持雙精度浮點計算的SIMD部件來支持大規模科學和工程計算是一個重要的發展趨勢。目前，商用微處理器上已經集成了 SIMD部件，如htel的MMX/SSE/AVX以及AMD的3D Now ！技術等，都是面向 SIMD部件的SIMD指令集。SIMD部件利用SIMD指令對向量進行操作，一個向量由多個浮點數據組成，從而實現了同時對多個浮點數據進行操作，加速了計算過程。矩陣乘操作是數值計算中最常用的一類操作，很多應用中都包含矩陣乘的計算過程，利用SIMD部件加速矩陣乘計算過程可以有效提高應用的計算速度。實現面向SIMD部件的高效矩陣乘方法是關係到發揮SIMD部件加速能力的關鍵。否則，難以達到SIMD部件的加速計算的設計目標。矩陣乘法是將被乘數矩陣A的一行和乘數矩陣B的一列相乘得到結果矩陣C中的一個元素。由於訪問A和B的順序不同，要對矩陣A或B進行重排序，傳統的做法是將其中的一個矩陣進行轉置。中國專利200380107095. 7提出了一種使用SIMD寄存器的小矩陣乘法，方法中首先對矩陣數據進行重排序及寄存器加載，隨後，將被乘數矩陣A的對角線乘以乘數矩陣B的列，把結果被加到結果矩陣C的列的結果和上。但是，這種方法只能處理維度較小的兩個矩陣相乘。2001年Douglas和Jonathan提出了一種面向htel SIMD部件的矩陣乘實現方法，但是，這種方法只適用於htel的SIMD部件，而且方法中首先要對輸入矩陣 B進行轉置操作。美國專利US007873812B1提出了一種面向SIMD部件的矩陣乘實現方法， 但是它對矩陣的列數有特殊要求，只能處理輸入矩陣A的列數可以被W (SIMD部件的向量長度)整除的情況，而且需要先對輸入矩陣A進行轉置操作，並要使用選擇部件來選擇向量寄存器中的元素。綜上所述，這些方法中都要求對矩陣數據進行有效的重排序，重排序會導致較大的計算開銷，影響了矩陣乘在SIMD部件上的計算速度。面向SIMD部件，實現無需重排序的矩陣相乘方法仍是本領域技術人員迫切希望解決的技術問題。
發明內容
本發明要解決的技術問題是提出一種面向包含廣播指令IdltoW的雙精度SIMD 部件的矩陣乘實現方法，避免對矩陣數據進行重排序，提高矩陣乘在SIMD部件上的計算速度。廣播指令IdltoW是指將1個雙精度浮點數據從存儲器裝載到向量寄存器的W個位置中。本發明的技術方案為對矩陣A和B進行分塊，使用SIMD對A、B的子矩陣相乘，將子矩陣結果累加到結果矩陣C。
3
具體的技術方案為設A和B為輸入矩陣，且均為雙精度浮點矩陣，結果矩陣為C(C = AXB),A矩陣的大小是M*K，B矩陣為K*N，C大小為M*N。雙精度SIMD部件的向量長度為W，即一個向量包含W個雙精度浮點數。N、W、K全是整數。第一步，增加矩陣B的列數，對增加的列使用0進行數據填充； SIMD部件每次按行讀取矩陣B的W個數據，如果N不是W的整數倍，在對B中每行數據的最後一次讀取時，不能得到和矩陣A相乘的正確數據，這樣就會得到錯誤結果。所以，當N不是W的整數倍時，增加B的列數，將B增加W列，使B的列數為 N+ff-N% W，％表示模運算，增加的列使用0進行數據填充；當N是W的整數倍時，B的列數不變。第二步，增加矩陣C的列數並將矩陣C的內容初始化為全0 ；矩陣乘結果使用向量存指令存儲到矩陣C中，矩陣C的列數必須和矩陣B相同，因此，需要增加矩陣C的列數，使C的列數為N+W-N% W。矩陣C需要存儲計算的中間結果，並對中間結果進行累加，所以需要將矩陣C的初始值初始化為0。第三步，根據SIMD部件的向量寄存器數目VN對矩陣B進行分塊，將K*N的矩陣B
劃分成k*n的子塊B1X
'K'*JW
)，其中η必須是W的整數倍；VN為正整數。 第四步，將Μ*Κ的矩陣A劃分成M*k的子塊Ai ( 1《M
)，「ι表示下取整t當矩陣B的K*N較大時，SIMD部件不可能將B中的所有數據取至SIMD部件的寄存器中，為了提高計算效率，需要對矩陣B進行分塊。這樣可以使每次子矩陣相乘的過程中， 矩陣B的數據在SIMD部件的寄存器中被重複利用，提高SIMD部件的計算效率。子矩陣Bj的大小即η和k值須滿足2+n*(k+l)/W < VN 且 W = 0 和 W = 0，2+n*(k+l)/W為每次子矩陣相乘所需的最少的向量寄存器數目(使用1個向量寄存器存儲矩陣A的一個數據，使用n*k/W個向量寄存器存儲B矩陣的數據，使用1個向量寄存器存儲向量乘結果，使用n/W個向量寄存器存儲每行的最終計算結果)。
~k第五步，子矩陣Ai和Bj在SIMD部件中相乘，並將結果累加到結果矩陣C中；5. 1 令 i = 1，j = 1，u = 1，ν = 1 ；5. 2將n/W個結果向量寄存器Vs的內容初始化為0，1彡s彡n/W ；5. 3使用廣播指令IdltoW將Ai中的一個元素^iuv取至向量寄存器Vtl ；5. 4 令 P = 1 ；5. 5如果u等於1，使用向量訪存指令將Bj中的第ν行元素中從(P-1) *W+1至P*W 的元素取至向量寄存器Vz中，Ι+η/W彡ζ彡n*(k+l)/W，執行第5. 6步；如果u不等於1，則數據已經存放在向量寄存器中，執行第5. 6步；5. 6V0和Vz進行向量乘法操作，將結果存儲在向量寄存器Vt中t = l+n*(k+l)/W ；5. 7Vt和結果向量寄存器Vs進行向量加操作，將結果存放在Vs中；5. 8如果P < n/ff, P = P+1，跳轉至5. 5 ；否則，執行5. 9步；
4
5. 9將n/W個結果向量寄存器Vs中的數據和C的第u行中第(u_l) *n+l+(i_l) *n 列至第u*n+(i-l)*n列的n個數據進行累加，並將結果寫到C中；5. 10如果ν < k, ν = v+1，跳轉至5. 2步；否則，執行5. 11步；5. 11如果u < M，u = u+Ι，跳轉至5. 2步；否則，執行第六步。第六步，如果— , j = j+1，跳轉至第五步。否則，j = j+1，執行第七步。第七步，如果/< f，i = i+Ι，跳轉至第五步。否則，結束。
κ如果SIMD部件包含乘加指令，5. 6和5. 7可以合併為一個步驟。採用本發明可以達到以下技術效果採用本發明可以實現任意維度(第一個輸入矩陣A的列數等於第二個輸入矩陣B 的行數)的兩個矩陣在雙精度SIMD部件上相乘。本發明中5. 3步對Ai是按行進行訪問的 (5. 10步增加v，其後的5. 11步增加u，因此5. 3步的auv是按行訪問的)，5. 5步中對Bj也是按行訪問的，即對輸入矩陣A和B可以按照其在存儲中的相同順序訪問(如果A和B是按列存儲的，將5. 10和5. 11調換順序，5. 5中取Bj每列的W個數據，就可以實現對輸入矩陣A和B都是進行按列訪問)，避免了對其中的一個矩陣進行轉置操作。同時，在子矩陣計算過程中，矩陣B的內容可以被重複利用，減少了訪問矩陣B的時間，提高了雙精度SIMD部件的計算效率。
圖1是本發明總體流程圖；圖2是傳統的面向SIMD部件的矩陣乘方法的一個實例。圖3是使用本發明的方法進行矩陣乘的一個實例。具體實現方式圖1是本發明總體流程圖，本發明的總體過程為第一步，增加矩陣B的列數並進行數據填充；第二步，增加矩陣C的列數，並將C的內容初始化為全0 ；第三步，矩陣B進行分塊；
第四步，矩陣A進行分塊；第五步，子矩陣相乘，並將結果加到矩陣C中的行的結果和上；第六步，是否遍歷了 B的位於同行的分塊，如果是，執行第七步；否則，跳轉至第五
止
少；第七步，是否遍歷了 A的所有分塊，如果是，程序結束；否則，跳轉至第五步。為了檢驗面向SIMD部件的矩陣乘實現效果，使用國防科大飛騰CPU為實現平臺， 飛騰CPU的SIMD部件的向量長度為4，向量寄存器的個數為32。在該平臺上採用C語言實現了 SIMD部件的矩陣乘方法。假設兩個輸入矩陣是64X64的矩陣，根據本發明，B被劃分為 64個子塊B」，每個子塊的大小為16 X 4 ;A被劃分為4個子塊Ai,每個子塊的大小為64X 16。 圖3給出了使用本發明實現兩個64 X 64矩陣乘的方法，子塊Ai (i為從1至4的整數)分別和子塊Bjj為從1+16* (i-Ι)至16*i的整數)進行相乘，將子矩陣相乘結果進行累加得到結果矩陣。因此採用本發明進行A和B相乘是對A和B按相同順序進行訪問，無需對A或B 進行轉置操作。圖2給出了面向SIMD部件的兩個64X64矩陣乘的傳統方法，需要對B進行轉置後進行矩陣乘的計算。在飛騰CPU上，使用傳統方法，轉置B矩陣的時間為0. 002秒，SIMD部件的計算時間為0. 056秒，矩陣乘總共的計算時間為0. 058秒。使用本發明時，面向SIMD部件的矩陣乘計算時間為0. 055秒，性能提升了 5. 2%。同時，對640X640的兩個矩陣乘進行了實驗，使用傳統方法，轉置B矩陣的時間為 0. 033秒，SIMD部件的計算時間為0. 82秒，矩陣乘總共的計算時間為0. 853秒；使用本發明時，矩陣乘計算時間為0. 81秒，性能提升了 5. 04%。
權利要求
1. 一種面向雙精度SIMD部件的矩陣乘實現方法，其特徵在於包括以下步驟 第一步，對於輸入矩陣A和B，當N不是W的整數倍時，增加輸入矩陣B的列數，將B增 加W-N% W列，使B的列數為N+W-N% ff, %表示模運算，增加的列使用O進行數據填充；A 矩陣的大小是M*K,B._* K*N，A、B均為雙精度浮點矩陣為雙精度SIMD部件的向量長 度，即一個向量包含W個雙精度浮點數；N、W、K全是整數；結果矩陣為C，大小為M*N ；第二步，增加結果矩陣C的列數，使C的列數為N+W-N% ff,並將矩陣C的內容初始化為 全0;第三步，根據SIMD部件的向量寄存器數目VN對矩陣B進行分塊，將K*N的矩陣B劃分 ~K~]「ダ成讓紐的子塊Bj
全文摘要
本發明公開了一種面向雙精度SIMD部件的矩陣乘實現方法，目的是提高矩陣乘在SIMD部件上的計算速度。技術方案是先增加矩陣B和矩陣C的列數；然後對矩陣A、B進行分塊；A的每個分塊和對應的B分塊使用SIMD部件進行相乘，並將結果加到矩陣C中相應位置的結果和上；採用本發明避免了對矩陣數據進行重排序，提高了矩陣乘在SIMD部件上的計算速度。
文檔編號G06F17/16GK102446160SQ20111026238
公開日2012年5月9日 申請日期2011年9月6日 優先權日2011年9月6日
發明者左克, 彭林, 易會戰, 李春江, 杜雲飛, 楊燦群, 趙克佳, 陳娟, 黃春 申請人:中國人民解放軍國防科學技術大學