面向DCU 的LDS 訪存向量化優化

楊思馳，趙榮彩，，韓林，，王洪生

（1.鄭州大學計算機與人工智能學院，河南 鄭州 450000；2.國家超級計算鄭州中心，河南 鄭州 450000）

0 引言

通用計算單元CPU 加專用計算單元GPU 構建的異構系統架構（HSA）如今已廣泛應用于實現高性能計算、機器學習和圖形處理等領域來完成各種計算密集 型任務［1］。深度計算器（DCU）是運行 在ROCm 環境下的國產通用加速器，它具有用于邏輯判斷、分支跳轉和中斷處理等功能的控制單元，在芯片上設計了數量眾多的算術運算單元［2］，這讓DCU設備在面向多數據并行計算的問題和具有高算術密集度類型的應用上有著很強的算力［3］。本文的實現面向DCU 所組成的異構平臺，該平臺主要使用HIP編程實現異構程序［4］。

如今已經出現了很多面向向量化的分析方法，CPU 實現了一些依據數據的依賴關系來尋找可并行的語句，然后將并行語句用向量的方式來并行執行［5］。近年來，GPU 中的訪存向量化技術也得到了廣泛的研究和探索，其中現有的訪存優化技術可以有效實現向量化計算，例如通過共享內存［6］、統一計算設備架構（CUDA）中的向量類型和內置向量函數［7］等技術來提高訪存效率。王細凱［8］針對異構內存訪存管理機制提出了基于bank 劃分的機制。該機制利用了存儲器中bank 的并行性和并行通道的特性，實現了高效的內存訪問和管理。也有研究者致力于改進現有的訪存技術，例如：楊世偉等［9］在對GPU 的優化研究中引入了新的向量類型、優化內存訪問模式等方法；YANG 等［10］通過研究GPGPU 編譯器的內存優化和并行管理分析內存帶寬和延遲的影響，提出了一種數據布局和并行管理的策略，在減少內存訪問次數和優化訪問模式的同時提高了并行性能；王琦等［11］實現了基于單指令多數據流（SIMD）的自動向量識別及調優方法來改進訪存向量化技術。這些技術可以實現高效的訪存優化，進一步提高計算性能和能源效率。

隨著異構計算平臺的廣泛應用，如何提升并行程序的運行性能依舊是需要解決的主要問題，而其中訪存性能的提升往往會成為系統性能提升的關鍵［12］。對此，本文從面向DCU 的異構平臺中數據的訪存性能優化方面入手，研究在本地數據共享（LDS）中數據的訪存向量化方法，實現對LDS 的訪問向量化。在對程序中的連續內存地址進行向量化實現之后，數據重疊的訪存特征與數據讀取向量化之間因為有LDS 中特殊的沖突特性存在，可能發生數據讀取延遲的問題?；诖?，完成向量化算法的關鍵是在訪存向量化實現的同時解決向量化過程中的訪存延遲問題。本文通過研究該類訪存特征下訪存效率低下的問題，提出一種面向DCU 的LCD 訪存向量化優化方法，實現向量化所帶來的最佳效率提升。

1 共享內存訪問向量化基礎

1.1 向量化實現可行性

DCU 的存儲結構中包含復雜的硬件層次，其中主要包括全局內存、緩存、共享內存、寄存器。DCU中的存儲器結構如圖1 所示。LDS 是DCU 中的一個關鍵存儲部件，在DCU 中，全局內存的所有加載和存儲請求都要經過二級緩存，這是DCU 中，計算單元（CU）之間數據統一的基本點。相較于二級緩存和全局內存，LDS 和L1 一級緩存在物理上位于CU內，可以被同一block（由多個線程組成的線程塊）中的所有線程訪問，具有更低的訪問延遲［13］。

圖1 DCU 存儲器示意圖Fig.1 DCU memory structure

為了得到一個高效的HIP 程序，需要合理地利用DCU 中不同種類的存儲空間。不同的存儲空間對訪問模式有著不同的要求，例如顯存訪問需要滿足合并訪問規則才能達到最大帶寬，緩存則要求訪問的數據有重用性才能得到高效的利用等［14］。在LDS 的訪存過程中，如果在訪問多個數據時訪存指令的訪存地址連續，就能夠將多個數據的訪存通過向量化“vector load/store”的方式實現讀?。?5］。實際上是將多條地址連續的訪存指令進行合并，使用一條向量化指令去實現多個數據的同時存?。?6］。

對于數據讀取的load 指令而言，當實現向量化數據讀取“vector load/store”指令后，還需要從該指令所獲取到的數據中提取出單個load 指令的各個元素［17］。在CPU 中，這種向量化對程序性能通常表現不佳，因為在大多數架構上，提取出向量寄存器中的元素會造成很大的程序消耗。此時，對CPU 來說更好的做法是將每個元素單獨讀取到它自己的標量寄存器中。然而在DCU 的硬件設備中，向量化方法的實現是通過“vector load/store”的向量化指令將數據直接加載到VGPR 中。VGPR 是DCU 中的一種寄存器類型，用于存儲多個線程同時運行時所需要的數據。與CPU 中的向量寄存器不同的是，VGPR 由多個標量寄存器組成來存儲向量化讀取后的多個數據，對于DCU 硬件設備來說，并不需要從VGPR 中提取向量元素。因此，該方法的實現是不會加重程序負擔的。

本文中所提到的向量化，可以稱之為合并，訪存指令可以對DCU 內核產生巨大的性能影響，隨著如今程序中對LDS 的使用越來越頻繁，這種向量化的機會在HIP 異構編程中也屢見不鮮。圖2（a）所示為程序從LDS 中讀取float 類型數據的一系列過程：原匯編指令表示出需要從v15 寄存器所存儲的數據地址指向的LDS 中讀取3 個數據并存入寄存器v24、v25、v26，該匯編指令中的3 條數據讀取的偏移量為4 Byte，可知3 條指令所讀取的數據連續。因此，該方法即可完成圖2（b）所示向量化后的結果：使用1 條指令訪存1 次讀取連續數據之后存入3 個連續的VGPR 中。顯而易見的是，優化實現后，程序減少了連續數據存取中訪問LDS 的次數，對異構程序的性能提升具有較大優勢［18］。

圖2 向量化的具體實現Fig.2 Concrete implementation of vectorization

1.2 訪存方式及bank 沖突

為了實現異構程序高帶寬運行，LDS 被劃分為大小相等的內存模塊，稱為banks，允許同時訪問［19］。因此，任何由n個地址組成的內存加載或存儲請求都可以同時提供服務，從而產生比單個模塊帶寬高n倍的總帶寬。但是，如果程序wavefront（由多個線程組成的線程束）內多個線程對LDS 請求數據位于同一個bank 中，則會引起bank 沖突，此時對LDS 必須序列化訪問。硬件將具有bank 沖突的內存請求拆分為根據需要盡可能多的單獨的無沖突請求［20］，從而降低吞吐量。如果請求數為n，則初始內存請求稱為導 致n路bank 沖 突［21］。由于DCU 在 運行程序時會有大量線程同時運行，對LDS 的訪問要求同一個block 中的線程之間沒有bank 沖突才能達到最大帶寬，因此在完成HIP 程序的編寫中，使用LDS 的程序訪存應盡量避免bank 沖突［22］，如圖3 所示，當多個線程在讀取4 Byte 的數據時，每個線程都沒有對同一個bank 進行訪問，這是最好的避免bank 沖突、高效利用LDS 的方法。

圖3 無bank 沖突讀取4 Byte 數據示意圖Fig.3 Schematic diagram of reading 4 Byte data without bank conflict

其他情況如圖4 所示，如果多個線程在讀取8 Byte 的數據時，線程需要對2 個bank 中的數據進行訪問，將前16 個線程放于一個wavefront 中，后16 個線程放入另一個wavefront 中，也不會在LDS 中引發bank 沖突。

圖4 無bank 沖突讀取8 Byte 數據示意圖Fig.4 Schematic diagram of reading 8 Byte data without bank conflict

在如圖3 所示的多個線程同時對LDS 的訪問過程中，同時讀取數據時并沒有發生需要重復讀取同一bank 的情況。如果程序線程間需要同時訪問相同的bank，如圖5 所示，各個線程在對每個數組中的數據讀取時，當線程0 去訪問數組中的第1 個數據時，它需要訪問LDS 中的bank-0，與此同時，線程1 訪問了bank-1。在這種情況下，由于線程間同時訪問存在一個bank 的差距，在后續讀取第2 個數據時同樣避免了訪問同一個bank，這種方式也不會導致bank沖突，線程間不會發生多個線程請求的內存地址被映射到同一個bank 上的情況，這些請求也不會因此而變成串行執行。

圖5 12 Byte 數據重疊訪問的情況Fig.5 The situation of 12 Byte data overlay access

圖5 所示的這種數據重疊訪問的情況在LDS 的使用案例中也比較常見。對該案例中LDS 數據訪問的不同訪存特征來說，當數組中的數據發生重疊時，也可以避免bank 沖突發生，同樣滿足了程序對LDS的最大帶寬的使用要求，使訪存效率更高。本文1.1節中提出，可以通過向量化將LDS 中地址連續的訪存指令進行合并來實現進一步優化，并在對數據訪存地址進行研究分析時，發現使用向量化技術確實可以將一些連續訪問地址的指令進行合并。最后值得注意的是，它所支持的合并方式在HIP 程序中并不能很好地兼顧LDS 所具有的bank 沖突特性所帶來的問題，因此不完全具有通用性。

2 共享內存訪問向量化及優化方法

對LDS 的訪問向量化及其優化方法主要對數組在LDS 訪存地址順序性和線程間的數據訪存特征2 個方面進行分析。在異構程序中，當數據的訪存地址具有順序性時，可以通過向量化的方法提升訪存效率。與此同時，需要注意線程間的數據重疊的訪存特征，避免發生LDS 沖突等待。圖6 展示了一段使用LDS 的HIP 程序，利用此代碼分析LLVM IR 中對2 種訪存特征的檢測和優化方法。在該實例中，將從LDS 中連續讀取3 組數據，其中每組數據中包含3 個連續的float 類型數據，此過程中編譯器會判斷3 個float 類型的數據讀取地址是否連續，可以完成向量化。

圖6 HIP 程序實例Fig.6 Example of HIP program

2.1 向量化方法實現

本文所提出的向量化方法，旨在處理LDS 中的訪存指令的合并。LDS 訪存方式在對多個連續的float 數據進行訪存時，需要使用多條訪存指令分別實現數據存?。?3］。該方法通過對程序中LDS 訪存指令的訪存地址進行連續性判斷，將多條LDS 訪存指令合并，進而提升訪存效率。

LDS 訪問向量化算法流程如圖7 所示，以下以load 指令為例說明算法流程。首先，分別對LLVM IR基本塊中地址空間指向LDS 內存空間的所有load 指令進行遍歷，同時為了防止load 指令過多而導致的處理延遲過長，該方法將所有的load 指令分組為多個指令塊，每個指令塊中的指令數最多為64 條；然后，遍歷指令塊中的所有指令，循環執行并選出地址連續的多個指令保存在指定的集合中，等待完成最終向量化的實現；當指令集合中完成了訪存地址連續的幾條指令收集后，獲取到連續數據的首地址，即可完成一次訪存指令的合并從LDS 中讀取多個數據存儲在連續的VGPR 中，完成指令塊中其中一部分的指令向量化，而后該方法將繼續遍歷后續指令，選擇符合向量化標準的指令放入集合，最終實現一個指令塊中所有可向量化指令的合并。

圖7 LDS 訪存指令向量化算法流程Fig.7 Procedure of LDS memory access instruction vectorization algorithm

算法在實現訪存向量化之前，需要對每條LDS 訪存指令的訪存地址進行分析，判斷其是否符合向量化條件并存儲于指令集合Instrs 中。針對上文所給出的程序實例，圖8展示了在LLVM IR 中，使用算法所遍歷到的其中一組最終放入集合Instrs中的load指令，而后檢查指令集合Instrs 中哪些指令的訪存地址具有連續性，采取索引鏈表的形式來表示程序中存在的可向量化訪存指令序列，并按照鏈表序列完成向量化。

圖8 可向量化指令集合中保存的指令Fig.8 Saved instructions on vectorizable instruction set

對于每一個指令塊，如算法1 所示，使用并查集方法建立連續指令鏈表。算法首先對指令塊中的指令進行順序重排操作，按順序為可向量化指令建立索引鏈表，后續對鏈表中的指令完成最終向量化。具體實現時，算法使用一個csct 索引鏈表來表示指令序號及所指向的下一條連續指令的序號，并將這2 條連續指令在指令塊中的索引分別存入2 個數組：Heads 和Tails，它們分別是存儲連續訪問的指令序號的頭序號和尾序號。這樣就實現了使用索引鏈表的方式存儲幾條訪存地址連續的指令。當遍歷到連續地址的最后一條指令時，將該指令對應的csct 數組值定義為-1，表示該向量化指令集合已結束。

將該訪存地址連續的指令按照索引鏈表中所給出的先后順序放入可向量化指令集合中，并實現向量化指令。之后算法將繼續查找下一組指令集合，直至索引鏈表中指令全部完成向量化。LLVM IR 中向量化后的指令如圖9 所示。

圖9 可向量化指令集合最終實現結果Fig.9 Final implementation result of vectorizable instruction set

2.2 數據訪問重疊問題優化

針對LDS 的訪問向量化能夠在大部分程序中產生性能提升效果，但是其中有部分程序具有線程間數據訪問重疊的訪存特征，這類程序在實現向量化之后存在性能大幅下降的異常情況，并且其在使用LDS的程序中也并不罕見。為了實現向量化后程序性能的完全提升，在向量化實現前必須要明確的是程序所具有的訪存特征。本文通過實現對LDS 的訪存特征的判斷，使其最終獲得有效的性能提升。

一般來說，LDS 的訪存特征都是基于程序中的多條內存訪問指令間所涉及的內存位置關系來確定的，但是程序的運行不僅僅要考慮到程序中不同訪存指令間的訪存位置導致的沖突，對于DCU 內部的多線程并行過程，同一訪存指令中也有可能因為數據重疊的訪存特征存在沖突。尤其在完成該訪存向量化之后，向量化實現了多條數據的合并訪問，使得在訪問向量化后的多個線程間，由于LDS 中具有bank 沖突的特性而產生數據讀取的延遲，因此對向量化方法實現的關鍵在于如何規避同一訪存指令在同時執行的線程間存在的數據重疊而導致的延遲情況。

2.2.1 訪存特征檢測方法

如圖5 所示，如果實現了向量化訪問，線程0 可以同時訪問位于bank-0～bank-2 的3 個32 位的數據，而并行執行的線程1 也要去完成3 個數據的訪問，位于bank-1～bank-3，此時就產生了多個線程間的數據讀取重疊。為了避免發生bank 沖突，線程1 需要等待線程0 完成3 個數據讀取后，才可以對數據所在的bank 進行訪問讀取，這種等待造成了程序性能的嚴重下降。

在DCU 中檢測同一訪存指令中的訪存特征較為復雜，本文提出一種針對線程間存在的訪存特征的判斷方法。在第2 節所提出的HIP 程序實例中，語句1 讀取了3 個連續的float 類型數據，對語句1 中的連續數據讀取首地址的指令為%322=getelementptr ［0 x float］，［0 x float］addrspace（3）*@sh_float，i32 0，i32%add3.i184.epil357，該地址可以表示為First_address=@sh_float+%add3.i184.epil357。指令訪存地址的分析結果為（（4*%44）+（4*（1+%43）*（2+%8））+@sh_float），+，（16+（8*%8））。通過簡化式子可以得出First_address=@sh_float+（%44+（%43+1+2）（2+%8））*4。其 中：@sh_float 是 該HIP 程序實例所申請LDS 空 間的首地址標識符；%43 和%44 代表寄存器中分別存儲的threadidx.x 和threadidx.y（二維并行程序線程號）的值，共同完成首地址的計算；指令%add3.i184 地址分析所給出的地址計算樹如圖10 所示。

圖10 %add3.i184 指令地址計算樹Fig.10 %add3.i184 instruction address calculation tree

以二維的線程組織的并行程序為例，LDS 訪存地址的基本計算公式為：Address_L0=First_shared+（ax+by）×4（x=0，1，…，y=0，1，…），其中：Address_L0為上文中向量化中指令的首條數據的地址；First_shared 表示程序在訪問LDS 時所需地址；x、y分別表示程序的二維線程號。程序在同一條指令的線程間可能存在的沖突主要與可向量化數據讀取的首地址在線程間的地址差距長度min｛a，b｝有關。如果在一個block 中，min｛a，b｝小于向量化方法所實現的向量化的數據長度，也就意味著在線程間存在數據重疊的訪存特征，那么在向量化之后就會發生因為數據合并讀取導致另一個線程的數據讀取延遲，致使程序LDS 訪存向量化優化效率低下。

2.2.2 向量化方法優化實現

為避免程序在向量化過程中線程間數據的訪存特征出現重疊而導致LDS 訪問延遲的問題，在向量化之前，要通過訪存特征檢測方法來終止指令向量化的實現。因此，在LDS 訪存向量化方法實現之前，必須判斷程序中是否具有線程間數據訪問重疊的訪存特征。得到程序的線程維度以及找到min｛a，b｝是進行訪存向量化的重要判斷條件。判斷算法流程如圖11 所示，首先需要獲取向量化指令集的首條指令的訪存地址計算GEP 指令，對該GEP 指令中的操作數進行遍歷查找，重要的是需要查找操作數指令中所包含的乘法指令，以便于判斷出哪些乘法指令中包含程序線程維度參數。然后使用數組WID 分別保存各維度所對應的乘數，選擇最小值與向量化指令集長度進行比較，從而判斷是否符合向量化條件。如果存在數據重疊的訪存情況，程序應立即終止向量化。

圖11 可向量化條件判斷算法流程Fig.11 Procedure of vectorizable condition judgment algorithm

3 性能分析

本文進行LDS 訪存向量化的功能和性能測試，測試環境基于開源編譯器LLVM（版本LLVM 13.0.0）搭建，其中，clang 版本為13.0.0，rocm 版本為4.5.2［24］。硬件采 用CPU+DCU 的異構平臺，其 中，CPU 型號為Hygon C86 7185 32-core Processor，加速器為海光一號DCU。

3.1 向量化方法測試分析

選取GEMM 矩陣乘作為測試用例，在高性能計算領域，對矩陣乘的優化是一個非常重要的課題。GEMM 廣泛應用于航空航天、流體力學等科學計算領域，這也是高性能計算（HPC）實現的主要應用場景。根據測試需要對劃塊實現的GEMM 用例作使用LDS 的調整［25］，同時選取SHOC 測試集中符合條件的測試用例——快速傅里葉變換（FFT），它在信號分析和處理領域有著廣泛的應用，是實現眾多復雜功能的基礎算法。

利用上述測試用例對本文提出的LDS 訪存向量化方法進行測試，得到的功能驗證結果如表1所示。

表1 功能驗證結果 Table 1 Functional verification results

功能驗證結果顯示，優化前后性能（GFlops）得到了平均1.203 的加速比，該結果表明本文方法能夠完成上文提到的LDS 連續訪問向量化，且與未經過向量化處理得到的代碼相比，經過本文方法處理的代碼總體性能平均提升了22.6%，達到了預期的目標。GEMM 程序在向量化前后實現的IR 代碼對比如圖12 所示。

圖12 向量化前后IR 指令對比Fig.12 Comparison of IR instructions before and after vectorization

3.2 數據訪問重疊問題測試分析

對程序中具有數據重疊訪存特征的向量化方法的優化，選取具備該訪存特征的測試用例Stencil2D算法完成測試。

Stencil2D 算法是一種基于二維矩陣的迭代計算方法，常用于模擬物理現象或圖像處理等應用場景。在Stencil2D 中，每個元素的值都由其周圍的相鄰元素計算得出，這種計算方式類似于模板，因此被稱為Stencil。Stencil 通常需要對大型矩陣進行高效并行計算，以提高運算效率和速度，是一種常用的并行計算方法，可以應用于各種領域的計算任務，其并行實現也涉及到多種技術和工具，需要根據具體情況進行選擇和優化。

在該測試用例的并行實現中，需要使用到共享內存來加速計算。Stencil2D 算法將矩陣數據分配給多個線程，并將相鄰線程所處理的數據區域進行重疊，以便在計算時共享一些數據，減少內存訪問和數據傳輸的開銷，具有LDS 中的存取連續數據的特征且數據具有線程間重疊讀取的特征［26］。

在對該測試用例實現了向量化優化方法之后，再次對程序進行性能測試，以比較優化前后的性能差異。ALUStalledByLDS 是rocprof 中的一項性能指標，代表ALU 因等待LDS 數據而被阻塞的時間比例。當異構程序在執行Kernel 時，如果ALU 需要訪問LDS 中的數據，而該數據還未被載入LDS，則ALU 會被阻塞，等待LDS 中的數據準備好。此時，ALUStalledByLDS 指標會統計ALU 被阻塞的時間占總時間的比例，反映LDS 訪問延遲對異構程序性能的影響。對Stencil2D 算法進行性能測試，ALUStalledByLDS 指標如表2 所示。

表2 向量化優化前后ALUStalledByLDS 指標對比 Table 2 Comparison of ALUStalledByLDS metrics before and after vectorization optimization

當ALUStalledByLDS 指標較高時，說明異構程序在執行Kernel 時，ALU 被LDS 訪問延遲所阻塞的時間較長。測試用例ALUStalledByLDS 指標向量化后明顯升高的情況表明，向量化方法的實現使存在數據訪存重疊的特征的程序在數據連續讀取的過程中產生延遲，從而向量化優化方法實現之后的程序訪存效率降低。通過對Stencil2D 算法的分析和測試表明，使用本文提出的優化方法能夠檢測到數據重疊的訪存特征，并根據訪存特征選取向量化實現方案，避免具有數據重疊訪存特征的程序實現LDS訪存向量化，使向量化方法盡可能發揮優勢。對于數據訪問重疊問題的優化測試結果如表3 所示，可見經過優化后的程序性能提升了33%。

表3 向量化優化前后Stencil2D 測試用例性能對比 Table 3 Comparison of Stencil2D test case performance before and after vectorization optimization

表3 結果顯示，對于共享內存LDS 向量化的判斷方法能夠實現程序性能的較大提升。此外，該優化能夠充分將DCU 的計算能力更好地發揮出來，減少了DCU 計算部件等待LDS 訪問的時間?？傮w來說，通過使用合適的向量化優化方法可以很好地提高程序性能，對于共享內存LDS 中數據的向量化訪問能夠達到充分發揮DCU 的計算能力的目的。

4 結束語

本文主要研究面向DCU 的共享內存訪存優化方法，實現針對LDS 的連續訪問向量化，解決在向量化過程中由于LDS 沖突特性導致的具有數據訪問重疊的向量化數據訪問延遲問題。實驗結果表明，本文提出的向量化優化方法能夠有效提高程序對LDS的訪問效率，形成一種面向國產通用加速器的高效訪存技術。在共享內存LDS 中的連續訪存向量化實現中，LLVM 后端實現指令選擇存在2 種不同形式，為進一步優化DCU 的訪存性能，后續工作將通過指令選擇確定最優指令形式來實現減少訪存次數的優化方案，進一步提高程序的執行效率。