基于申威1621處理器的BLAS一級函數優化①

李浩然,王 磊

1(中原工學院 計算機學院,鄭州 450007)

2(中原工學院 前沿信息技術研究院,鄭州 450007)

1 引言

BLAS (Basic Linear Algebra Subprograms)基礎線性代數庫是一個基本線性代數操作的數學函數標準,支撐著許多計算機應用領域的數值線性代數計算,BLAS一般分為三級,一級主要完成向量與向量之間的操作;二級主要完成向量與矩陣之間的操作;三級主要完成向量與向量之間的操作.其不僅被廣泛應用于科學計算領域,并且在深度學習方面,底層調用BLAS 庫進行加速運算已經十分常見了.例如基于矩陣類的深度學習有90%或更多的時間是通過BLAS來進行計算的,因此一個高性能的BLAS 庫具有十分重要的意義.目前各大主流處理器廠商都對其硬件平臺做了深度優化工作,例如Intel的MKL (Math Kernel Library,數學核心庫)、AMD的ACML (AMD Core Math Library)、以及在Nvidia 上使用的CuBLAS 等.

申威1621 處理器基于第三代“申威64”核心的國產高性能多核處理器,主要面向高性能計算和中高端服務器應用.設計目標主頻為2.0 GHz,單芯片集成了16個64 位申威處理器核心,雙精度浮點性能可達512 Gflpos.申威1621 處理器具有16 核心共享32 MB的三級Cache,支持256 位SIMD 指令,可以在最大程度上提升系統的數據級并行.

目前來說,BLAS 三級函數的研究已經較為成熟[1],因此本文的研究內容主要在于優化工作相對較少的BLAS一級函數上.首先BLAS 一級函數屬于訪存密集型函數,性能主要受限制于處理器本身的緩存大小和訪存帶寬,對這些函數優化難度較大[2];其次在于計算數據規模和排布的不確定性,又給優化工作帶來新的難題.目前對于BLAS 一級函數的優化方法較為單一,大多集中在使用指令優化方面,通過利用數據預取以及向量化來提升訪存性能,而在使用多線程優化方面,僅僅開啟多線程進行計算,但是對于多線程使用的線程數量并沒有加以調控,而是把這項任務交給了用戶來決定[3],這對于用戶來說使用較為不便,因此需要一套完成的優化方案來有效提升BLAS 一級函數性能,提高用戶的便捷性.目前GotoBLAS 僅僅對AXPY,SWAP,SCAL 三個主要函數實現了多線程并行化,本文選取了其中較為復雜的函數AXPY為例進行優化分析.

本文主要針對申威1621 處理器進行BLAS 一級函數的優化研究工作.其中第1 節是引言,介紹了平臺信息與本文工作的意義;第2 節以BLAS 一級函數中的典型函數AXPY為例,介紹一級函數特點;第3 節介紹了基于單核的AXPY 函數優化方法;第4 節介紹了多線程AXPY 優化設計;第5 節為實驗,與開源的GotoBLAS[4]進行性能比較;最后是總結與展望.

2 BLAS 一級函數AXPY 概述

BLAS 一級函數主要完成了標量與向量,向量與向量之間的操作.由于BLAS 一級函數之間的相似性,我們以函數AXPY(向量乘加)為例,來說明一級函數的特點.AXPY 函數實現了式(1)中的功能:

其中,alpha為標量,X,Y為向量.AXPY的計算復雜度為O(N),從公式中可以看出,在每個計算周期內,有3 次訪存內存和2 次計算操作,計算訪存比高達2:3[5].即使進行循環展開和指令重排等優化,也無法將訪存開銷隱藏在計算過程中,因此要盡可能地提高內存帶寬的利用率,由此來提高函數性能.

AXPY 函數的計算訪存比高達2:3,能否達到訪存帶寬的上限將會是衡量BLAS 一級函數優化效果的一個重要指標.根據計算機組成結構,訪存帶寬可以分為兩部分,高速緩存帶寬即L2 Cache,和內存帶寬.當數據規模小于L2 Cache 時,可以達到一個較高的性能水平.當數據規模大于L2 Cache 時,訪存性能會產生一個急劇下降,此時函數性能較差.

目前GotoBLAS 在申威1621 上的BLAS 一級函數實現方式是最基礎的版本,除了編譯器優化外,沒有進行任何的其他形式優化,該版本在1621 平臺上所取得的性能僅為8014 Mflops,遠遠不能滿足應用對于程序性能的需求,因此要根據函數特定設計一套高效的優化方案來提升函數性能.

3 AXPY 函數單核串行優化

針對1621 平臺,本節描述了AXPY 函數單核高性能優化方案,該方案基于AXPY 函數訪存密集型函數的特點,再結合申威1621 處理器平臺特性,實現了該平臺的上高性能AXPY 函數.

3.1 256 位的SIMD 向量指令

申威1621 處理器提供了256 位SIMD 向量拓展指令.針對AXPY 函數訪存密集型特點,能夠最大程度發揮該平臺訪存能力.為實現高性能的AXPY 函數,我們選擇使用SIMD 向量乘加指令、SIMD 向量訪存指令以及SIMD 向量復制指令來進行優化,提高數據并行程度.基于AXPY 函數,任務數據可以分為兩類,一類是計算步長為1 時的連續數據另一類是計算步長不為1 時的離散數據,針對這兩種不同的數據,處理方式也有所不同.

在計算步長為1的情況下,SIMD 拓展指令能夠將內存地址連續的數據多次裝載,轉變為一次全部裝在到向量寄存器.只用一條SIMD 拓展指令能夠實現并行處理SIMD 向量寄存器中的所有數據.以雙精度為例,每個數據元素為8 字節、64 位,配合申威1621 處理器提供的長度為256 位SIMD 訪存指令使用時,可以如圖1所示,每次從內存空間順序讀取4個X向量元素或Y向量元素放入浮點向量寄存器中去.針對標量元素alpha則使用向量復制指令,將其拓展成4 份再存入浮點向量寄存器中,這樣即可完成對所需計算數據進行向量打包,便于下一步利用向量運算指令展開計算.

圖1 連續數組向量化示意圖

申威1621 平臺提供256 位的SIMD 乘加指令,可以在1.5個時鐘周期內同時完成乘法和加法操作.經過上一步將數據打包為向量塊之后,我們可以直接使用乘加指令來完成整個計算操作.這樣相對比與原本的計算方式,計算相同數據量的情況下,可以減少12 計算條指令執行時間,從而提升函數性能.

當默認步長不為1 時,任務數據并不連續,無法直接使用SIMD 向量化指令進行運算.對于此類不連續數據訪問方式,姚金陽等人[6]提出了一種間接數組索引的向量化方法,該方案通過引入一個間接數組的方式對數據進行重排序,重排方法如圖2所示,經過重排打包之后,利用向量乘加指令進行運算.如果使用此方案進行向量化優化,我們對其進行收益進行評估.

圖2 間接數組向量化示意圖

Step 1.載入數據時,要對數據進行一次“預處理”,每次訪存都會引入一條新的載入指令,把需要計算的X和Y數據全部載入共計引入了新的8 條載入語句.

Step 2.計算時,由于數據已經打包成向量塊,使用一條向量乘加指令即可完成數據的計算,共計減少了7 條計算指令.

Step 3.存儲數據時,要對數據再次進行一次“尾處理”,將已經打包的向量塊拆分存儲并存儲到數據原本的位置,共計引入4 條拆分指令.

綜上,對于原本串行執行,使用向量化指令進行計算會多引入5 條指令.向量化優化收益為負,因此對于步長不為1的情況,仍選擇使用串行執行即可.

3.2 訪存優化

進行訪存優化的方法主要有兩種:一是加快訪存速度,二是隱藏訪存延遲,數據局部性優化,例如循環展開,數據預取,指令重排等方式.1621 處理器的平臺的訪存速度是由硬件平臺所決定的,我們無法對其做出更改,因此本文選擇從軟件優化的方式出發,利用循環展開、數據預取和指令重排的方式并結合申威1621平臺特點進行優化.

循環展開是編譯器優化的基本方法之一,循環展開之后,可以增加最內層循環的單次循環指令數目.這樣做的優勢有兩方面,一方面從硬件看,單次循環內,指令數目的增加,可以更好地利用硬件資源,更多的指令便于硬件流水線發揮作用,同時CPU 保留棧等硬件資源也可以得到充分的利用;另一方面從軟件的角度看,更多的指令便于將指令進行重排,避免出現訪問和計算同時使用相同的寄存器,從而出現流水線停頓[7].考慮訪存延遲、計算指令的排布以及寄存器的數量,將循環展開4 次即可.

數據預取是將取數據和用數據人為的分開,使它們能夠充分的并行執行,而不會因為等待數據停止流水.針對AXPY 函數的計算特點,每兩次訪問進行一次乘加計算,乘加計算需要等待這兩次訪問完全結束才能開始執行

數據的依賴關系并不利于流水線的充分使用.訪存與計算之間,數據存在依賴關系,要先將數據存放在寄存器中之后才能再參與運算.因此如果在核心計算開始時,再進行數據載入時,會因為計算指令等待訪存指令完成再進行執行,因而引發了流水線的停頓.為解決流水線停頓的問題,本文在核心計算開始之前進行一次數據提前載入,這樣當核心計算開始時,本輪計算所用數據已經完全載入到寄存器之中,計算所用數據不會因為訪存而產生依賴關系,同時我們在計算本輪結果時,載入下一輪計算所需數據,這樣將計算數據與訪存數據分開,解除計算與訪存數據之間的依賴關系.

即使進行了循環展開和數據預取的優化,但核心計算循環內,訪存指令數量仍然遠大于計算指令數量,計算延遲無法掩蓋訪存延時,因此在指令重排的時候,可以考慮另外一種排布方式,將計算時間隱藏在訪存之中,這樣可以達到函數的理論性能上限.申威1621處理器提供了2 條浮點流水線,可同時并行指令兩條浮點指令,同時提供了F0—F32 共32個向量寄存器.基于以上條件,本文重新設計了核心函數的指令排布.

在核心函數的設計中,應當遵循以下幾條原則:(1)最內層循環應當展開夠一定次數,訪存指令可以充分掩蓋計算指令,防止計算延遲的出現;(2)硬件提供了兩條流水線,避免將當前指令的目的寄存器作為下一條指令的源寄存器,避免出現流水線停頓的情況;(3)盡可能地利用指令之間的間隙,通過對1621 平臺的指令周期測試,根據不同執行需要指令的指令周期來進行合理排布,減少的總的指令周期時長[8].

BLAS 一級函數AXPY 完成操作較為簡單,在核心計算函數的編寫中,需要用到的指令種類較少,通過對其測試得到了表1中的結果.從表1中可以看出,每條訪存執行周期內,可以完成兩條計算指令的執行.由于AXPY 函數計算指令遠遠少于訪存指令,如果正常執行一條計算指令和一條存儲指令,則會由于數據的依賴關系需要等待計算指令結束之后,再進行存儲指令的執行,不利于兩條執行并行執行.因此我們選擇如圖3的指令重排方式,在執行計算指令的時候,同時執行數據載入指令,載入下一輪計算所需數據.這時由于計算指令執行所需時間僅為1.5個CPU 周期,但訪存指令需要3個CPU 執行周期,計算執行會比訪存指令更早的結束執行.為了避免當前指令的目的地址作為下一條指令源地址情況的出現,我們在排布第3 條指令的時候仍進行數據載入操作,這時流水中同時執行的是兩條數據載入指令,之后再執行數據存儲操作.這樣的指令排布保證了一條計算指令所需時間完全隱藏在了訪存指令執行時間之中,并且兩條流水線可以得到充分的利用.

表1 向量指令執行所需周期數

圖3 指令重排示意圖

為了減少數據之間的依賴,本文選擇了預先載入計算數據,并在計算的時候載入下一次計算所用數據,這種方式雖然解除了計算與訪存之間數據的依賴關系,但是引入了更多了臨時寄存器[9],由原本每次計算僅需2個寄存器增加到每次計算需要4個寄存器.這時候可用寄存器的數量就限制了可以循環擴展的最大次數.申威1621 處理器提供了32個向量寄存器,可自由使用向量寄存器為31個,在寄存器的限制下,循環展開的最大次數被限制7 次以內.為了減少邊際數據的處理,我們選擇將循環展開次數定為4 次.

由于對核心計算進行了4 次循環展開,因此每次內層循環中由6 條計算指令和12 條訪存指令組成.根據上述原則對循環進行指令重排,如圖3所示為指令重排前后的指令流水.進行指令重排之后,充分發揮了申威1621 處理器浮點雙流水的特點,將6 條計算指令耗時隱藏在12 條訪存指令之中,從原本的每次核心循環執行完成需要的15個時鐘周期縮減到11個時鐘周期,此時函數性能完全由訪存性能決定,基本達到了函數的理論峰值.

4 AXPY 函數多核優化設計

4.1 并行化

多線程并行是一種常見的優化方式[10],在沒有數據依賴以及不超過總線帶寬的基礎上,可以有效地提高函數的訪存性能,AXPY 函數主要進行向量-向量之間的運算,理論上線程之間沒有數據依賴,因此AXPY函數具有天然的負載均衡.對于函數AXPY來說,進行并行化的優化并不復雜,由于向量數據之間沒有關聯性,我們可以使每個計算核心運行一個線程,每個線程的函數優化設計沿用上一章單核函數優化設計的方案即可.

對于需要計算任務數據的劃分,根據AXPY 函數多為向量數據,易于分段且數據規模較為規整的特點.不需要對數據進行前期處理,在并行區開始之前主線程執行靜態任務調度,即可保證各線程之間的負載均衡[11].由于AXPY 函數性能的瓶頸在于內存帶寬,當達到帶寬極限時再增加線程只能導致資源沖突,反而會使AXPY 函數性能下降.為此本文專門設計了線程自動分配函數來保證不會因為線程數量而影響到函數的性能.

4.2 線程分配

考慮到AXPY 函數的性能主要受限于訪存帶寬,在訪存帶寬允許的情況下,盡可能多的開啟線程會一定程度上提升函數的性能.當性能達到帶寬上限時,再增加線程的數量只會造成數據的爭奪[12],從而影響函數性能.因此,開啟線程數量主要取決于1621 處理器能達到的最大帶寬.

根據任務規模,我們可以將帶寬分為兩類,一類當任務數據規模小于L2 Cache 時的高速緩存帶寬,另一類是任務規模大于L2 Cache的內存帶寬[13].為了幫助分析開啟不同任務規模需要開啟線程的數量,利用Stream 帶寬測試工具對1621 處理器進行帶寬測試[14],根據測試結果進行合理的線程分配.

利用Stream 帶寬測試工具,我們測試了在大頁緩存范圍內,不同線程的訪存帶寬能力.通過圖4的測試結果,分析可得,在高速緩存內,隨著線程數量的增加,訪存能力逐漸提升,直到開啟到12 線程的時候,訪存帶寬達到頂峰,再增加線程數量,只會增加線程之間帶寬的爭奪,降低了訪存的性能.因此根據上文對緩存方式的分類再結合Stream 帶寬測試結果,我們對線程進行如下劃分.

圖4 線程帶寬測試

1)當任務規模小于L2 Cache 時,數據可以全部載入到L2 Cache中,此時的訪存帶寬遠遠高于架構本身的真實帶寬,單線程優化后的訪存帶寬不足以達到此時的訪存帶寬,在此階段開啟多線程,可以最大的提升函數性能.當數據規模較小時,開啟線程的花銷會大于本身線程計算所用花銷,這樣不利于性能的提升此時我們選擇開啟較小的線程數,使用單線程進行計算.隨著數據規模的逐漸增大,開啟更多的線程數量來獲取更多的性能,根據帶寬測試結果,最大使用線程數量限制在12 線程即可.

2)當任務規模大于L2 Cache 時,此時訪存帶寬為架構本身真實帶寬,帶寬較小,只需將帶寬全部跑滿即可達到此時的最佳性能,如果再增加線程數量,只會降低函數性能.根據Stream 帶寬測試結果表明,使用SIMD 優化之后開啟雙線程即可跑滿帶寬,再增加線程數量只會降低函數性能.因此在這種情況下,開啟雙線程即可獲得最優的性能.

綜合以上限制條件,針對線程開啟情況設計了圖5所示的多線程使用方案,通過此方式來調節線程數量,提升多線程對函數的優化性能.

圖5 線程自動分配流程

5 性能測試與分析

申威1621 處理器作為新一代的國產高性能多核平臺,性能指標較為優異,作為本文的實驗平臺,其各項參數指標如表2所示.

表2 實驗環境

針對AXPY 函數的特點,本文進行了一系列的對比測試,首先利用Stream 帶寬測試工具,測試了訪存帶寬測試,以檢測到的帶寬作為對比參考.其次為了更好地測得單線程與多線程的優化效果,我們選擇了不同的測試數據集來進行分別進行測試.

針對單核單線程的測試來說,我們選取了數據規模從1000 到10000,步長為1000的共計10 組數據進行測試.實驗結果如圖6所示,使用向量化技術優化之后,相對原GotoBLAS 實現平均2.73 倍性能提升,經過循環拓展和指令重排之后,性能提升從原本的2.73 倍提升至4.36 倍.

圖6 單核優化性能測試結果

對于多核多線程的優化測試,相對于單線程的測試不同,多線程我們選擇更大范圍和規模的數據來進行測試,并和單線程測試結果進行對比.實驗結果如圖7所示,相對比于申威平臺單線程優化方案而言,多線程最高加速比可達3.91,平均加速比為2.18.

圖7 多線程優化測試對比結果圖

圖8為原版單線程與原版使用多線程的性能對比圖,從圖中數據可以看出,原版多線程相較于原版單線程最高加速比為3.29,平均加速為1.8.加速效果低于我們針對多線程進行線程分配之后的優化效果,結合上面我們使用線程分配函數之后的優化結果可以得出結論,我們設計的線程自動分配函數優化了因為線程爭奪對性能產生的影響,一定程度上提升了函數的性能.

圖8 原版單核與多核性能對比圖

6 總結與展望

本文首先說明了BLAS 一級函數的作為訪存密集型函數的特點,并針對其特點,結合國產申威1621 多核平臺的架構特征,設計了一套基于該平臺的BLAS一級函數優化方案.本方案首先分析了單核單線程的優化方法,運用了循環展開,指令重排等基于該平臺的優化技術,接著分析了基于多核多線程的優化方法,提出了負載均衡和線程自動分配機制.在性能測試中,基于申威1621 平臺上經過優化的AXPY 函數性能,在單核情況下,對比原GotoBLAS,實現了平均加速比4.36,多核12 線程方案的平均加速比為9.5,達到預期優化效果.

本文主要考慮了自動線程分配機制在申威平臺的實現方案,因此在普適性應用時,其他機器的L2 Cache 可以直接獲取到,但是Cache中訪存最大帶寬無法直接得到,需要通過Stream 帶寬測試,但目前通用的Stream 提供的帶寬測試并沒有使用SIMD 指令來提高數據吞吐量,如果編譯器在編譯時,無法進行自動向量化優化,那么這樣測試所得的數據與實際應用中有較大差別,因此仍需要一個專用帶寬測試工具來測試出實際帶寬,在此基礎上進行數據填充,后續工作中將對這些做進一步研究.