面向DCU 的LDS 訪(fǎng)存向量化優(yōu)化

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

（1.鄭州大學(xué)計(jì)算機(jī)與人工智能學(xué)院，河南 鄭州 450000；2.國(guó)家超級(jí)計(jì)算鄭州中心，河南 鄭州 450000）

0 引言

通用計(jì)算單元CPU 加專(zhuān)用計(jì)算單元GPU 構(gòu)建的異構(gòu)系統(tǒng)架構(gòu)（HSA）如今已廣泛應(yīng)用于實(shí)現(xiàn)高性能計(jì)算、機(jī)器學(xué)習(xí)和圖形處理等領(lǐng)域來(lái)完成各種計(jì)算密集 型任務(wù)［1］。深度計(jì)算器（DCU）是運(yùn)行 在ROCm 環(huán)境下的國(guó)產(chǎn)通用加速器，它具有用于邏輯判斷、分支跳轉(zhuǎn)和中斷處理等功能的控制單元，在芯片上設(shè)計(jì)了數(shù)量眾多的算術(shù)運(yùn)算單元［2］，這讓DCU設(shè)備在面向多數(shù)據(jù)并行計(jì)算的問(wèn)題和具有高算術(shù)密集度類(lèi)型的應(yīng)用上有著很強(qiáng)的算力［3］。本文的實(shí)現(xiàn)面向DCU 所組成的異構(gòu)平臺(tái)，該平臺(tái)主要使用HIP編程實(shí)現(xiàn)異構(gòu)程序［4］。

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

隨著異構(gòu)計(jì)算平臺(tái)的廣泛應(yīng)用，如何提升并行程序的運(yùn)行性能依舊是需要解決的主要問(wèn)題，而其中訪(fǎng)存性能的提升往往會(huì)成為系統(tǒng)性能提升的關(guān)鍵［12］。對(duì)此，本文從面向DCU 的異構(gòu)平臺(tái)中數(shù)據(jù)的訪(fǎng)存性能優(yōu)化方面入手，研究在本地?cái)?shù)據(jù)共享（LDS）中數(shù)據(jù)的訪(fǎng)存向量化方法，實(shí)現(xiàn)對(duì)LDS 的訪(fǎng)問(wèn)向量化。在對(duì)程序中的連續(xù)內(nèi)存地址進(jìn)行向量化實(shí)現(xiàn)之后，數(shù)據(jù)重疊的訪(fǎng)存特征與數(shù)據(jù)讀取向量化之間因?yàn)橛蠰DS 中特殊的沖突特性存在，可能發(fā)生數(shù)據(jù)讀取延遲的問(wèn)題。基于此，完成向量化算法的關(guān)鍵是在訪(fǎng)存向量化實(shí)現(xiàn)的同時(shí)解決向量化過(guò)程中的訪(fǎng)存延遲問(wèn)題。本文通過(guò)研究該類(lèi)訪(fǎng)存特征下訪(fǎng)存效率低下的問(wèn)題，提出一種面向DCU 的LCD 訪(fǎng)存向量化優(yōu)化方法，實(shí)現(xiàn)向量化所帶來(lái)的最佳效率提升。

1 共享內(nèi)存訪(fǎng)問(wèn)向量化基礎(chǔ)

1.1 向量化實(shí)現(xiàn)可行性

DCU 的存儲(chǔ)結(jié)構(gòu)中包含復(fù)雜的硬件層次，其中主要包括全局內(nèi)存、緩存、共享內(nèi)存、寄存器。DCU中的存儲(chǔ)器結(jié)構(gòu)如圖1 所示。LDS 是DCU 中的一個(gè)關(guān)鍵存儲(chǔ)部件，在DCU 中，全局內(nèi)存的所有加載和存儲(chǔ)請(qǐng)求都要經(jīng)過(guò)二級(jí)緩存，這是DCU 中，計(jì)算單元（CU）之間數(shù)據(jù)統(tǒng)一的基本點(diǎn)。相較于二級(jí)緩存和全局內(nèi)存，LDS 和L1 一級(jí)緩存在物理上位于CU內(nèi)，可以被同一block（由多個(gè)線(xiàn)程組成的線(xiàn)程塊）中的所有線(xiàn)程訪(fǎng)問(wèn)，具有更低的訪(fǎng)問(wèn)延遲［13］。

圖1 DCU 存儲(chǔ)器示意圖Fig.1 DCU memory structure

為了得到一個(gè)高效的HIP 程序，需要合理地利用DCU 中不同種類(lèi)的存儲(chǔ)空間。不同的存儲(chǔ)空間對(duì)訪(fǎng)問(wèn)模式有著不同的要求，例如顯存訪(fǎng)問(wèn)需要滿(mǎn)足合并訪(fǎng)問(wèn)規(guī)則才能達(dá)到最大帶寬，緩存則要求訪(fǎng)問(wèn)的數(shù)據(jù)有重用性才能得到高效的利用等［14］。在LDS 的訪(fǎng)存過(guò)程中，如果在訪(fǎng)問(wèn)多個(gè)數(shù)據(jù)時(shí)訪(fǎng)存指令的訪(fǎng)存地址連續(xù)，就能夠?qū)⒍鄠€(gè)數(shù)據(jù)的訪(fǎng)存通過(guò)向量化“vector load/store”的方式實(shí)現(xiàn)讀取［15］。實(shí)際上是將多條地址連續(xù)的訪(fǎng)存指令進(jìn)行合并，使用一條向量化指令去實(shí)現(xiàn)多個(gè)數(shù)據(jù)的同時(shí)存取［16］。

對(duì)于數(shù)據(jù)讀取的load 指令而言，當(dāng)實(shí)現(xiàn)向量化數(shù)據(jù)讀取“vector load/store”指令后，還需要從該指令所獲取到的數(shù)據(jù)中提取出單個(gè)load 指令的各個(gè)元素［17］。在CPU 中，這種向量化對(duì)程序性能通常表現(xiàn)不佳，因?yàn)樵诖蠖鄶?shù)架構(gòu)上，提取出向量寄存器中的元素會(huì)造成很大的程序消耗。此時(shí)，對(duì)CPU 來(lái)說(shuō)更好的做法是將每個(gè)元素單獨(dú)讀取到它自己的標(biāo)量寄存器中。然而在DCU 的硬件設(shè)備中，向量化方法的實(shí)現(xiàn)是通過(guò)“vector load/store”的向量化指令將數(shù)據(jù)直接加載到VGPR 中。VGPR 是DCU 中的一種寄存器類(lèi)型，用于存儲(chǔ)多個(gè)線(xiàn)程同時(shí)運(yùn)行時(shí)所需要的數(shù)據(jù)。與CPU 中的向量寄存器不同的是，VGPR 由多個(gè)標(biāo)量寄存器組成來(lái)存儲(chǔ)向量化讀取后的多個(gè)數(shù)據(jù)，對(duì)于DCU 硬件設(shè)備來(lái)說(shuō)，并不需要從VGPR 中提取向量元素。因此，該方法的實(shí)現(xiàn)是不會(huì)加重程序負(fù)擔(dān)的。

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

圖2 向量化的具體實(shí)現(xiàn)Fig.2 Concrete implementation of vectorization

1.2 訪(fǎng)存方式及bank 沖突

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

圖3 無(wú)bank 沖突讀取4 Byte 數(shù)據(jù)示意圖Fig.3 Schematic diagram of reading 4 Byte data without bank conflict

其他情況如圖4 所示，如果多個(gè)線(xiàn)程在讀取8 Byte 的數(shù)據(jù)時(shí)，線(xiàn)程需要對(duì)2 個(gè)bank 中的數(shù)據(jù)進(jìn)行訪(fǎng)問(wèn)，將前16 個(gè)線(xiàn)程放于一個(gè)wavefront 中，后16 個(gè)線(xiàn)程放入另一個(gè)wavefront 中，也不會(huì)在LDS 中引發(fā)bank 沖突。

圖4 無(wú)bank 沖突讀取8 Byte 數(shù)據(jù)示意圖Fig.4 Schematic diagram of reading 8 Byte data without bank conflict

在如圖3 所示的多個(gè)線(xiàn)程同時(shí)對(duì)LDS 的訪(fǎng)問(wèn)過(guò)程中，同時(shí)讀取數(shù)據(jù)時(shí)并沒(méi)有發(fā)生需要重復(fù)讀取同一bank 的情況。如果程序線(xiàn)程間需要同時(shí)訪(fǎng)問(wèn)相同的bank，如圖5 所示，各個(gè)線(xiàn)程在對(duì)每個(gè)數(shù)組中的數(shù)據(jù)讀取時(shí)，當(dāng)線(xiàn)程0 去訪(fǎng)問(wèn)數(shù)組中的第1 個(gè)數(shù)據(jù)時(shí)，它需要訪(fǎng)問(wèn)LDS 中的bank-0，與此同時(shí)，線(xiàn)程1 訪(fǎng)問(wèn)了bank-1。在這種情況下，由于線(xiàn)程間同時(shí)訪(fǎng)問(wèn)存在一個(gè)bank 的差距，在后續(xù)讀取第2 個(gè)數(shù)據(jù)時(shí)同樣避免了訪(fǎng)問(wèn)同一個(gè)bank，這種方式也不會(huì)導(dǎo)致bank沖突，線(xiàn)程間不會(huì)發(fā)生多個(gè)線(xiàn)程請(qǐng)求的內(nèi)存地址被映射到同一個(gè)bank 上的情況，這些請(qǐng)求也不會(huì)因此而變成串行執(zhí)行。

圖5 12 Byte 數(shù)據(jù)重疊訪(fǎng)問(wèn)的情況Fig.5 The situation of 12 Byte data overlay access

圖5 所示的這種數(shù)據(jù)重疊訪(fǎng)問(wèn)的情況在LDS 的使用案例中也比較常見(jiàn)。對(duì)該案例中LDS 數(shù)據(jù)訪(fǎng)問(wèn)的不同訪(fǎng)存特征來(lái)說(shuō)，當(dāng)數(shù)組中的數(shù)據(jù)發(fā)生重疊時(shí)，也可以避免bank 沖突發(fā)生，同樣滿(mǎn)足了程序?qū)DS的最大帶寬的使用要求，使訪(fǎng)存效率更高。本文1.1節(jié)中提出，可以通過(guò)向量化將LDS 中地址連續(xù)的訪(fǎng)存指令進(jìn)行合并來(lái)實(shí)現(xiàn)進(jìn)一步優(yōu)化，并在對(duì)數(shù)據(jù)訪(fǎng)存地址進(jìn)行研究分析時(shí)，發(fā)現(xiàn)使用向量化技術(shù)確實(shí)可以將一些連續(xù)訪(fǎng)問(wèn)地址的指令進(jìn)行合并。最后值得注意的是，它所支持的合并方式在HIP 程序中并不能很好地兼顧LDS 所具有的bank 沖突特性所帶來(lái)的問(wèn)題，因此不完全具有通用性。

2 共享內(nèi)存訪(fǎng)問(wèn)向量化及優(yōu)化方法

對(duì)LDS 的訪(fǎng)問(wèn)向量化及其優(yōu)化方法主要對(duì)數(shù)組在LDS 訪(fǎng)存地址順序性和線(xiàn)程間的數(shù)據(jù)訪(fǎng)存特征2 個(gè)方面進(jìn)行分析。在異構(gòu)程序中，當(dāng)數(shù)據(jù)的訪(fǎng)存地址具有順序性時(shí)，可以通過(guò)向量化的方法提升訪(fǎng)存效率。與此同時(shí)，需要注意線(xiàn)程間的數(shù)據(jù)重疊的訪(fǎng)存特征，避免發(fā)生LDS 沖突等待。圖6 展示了一段使用LDS 的HIP 程序，利用此代碼分析LLVM IR 中對(duì)2 種訪(fǎng)存特征的檢測(cè)和優(yōu)化方法。在該實(shí)例中，將從LDS 中連續(xù)讀取3 組數(shù)據(jù)，其中每組數(shù)據(jù)中包含3 個(gè)連續(xù)的float 類(lèi)型數(shù)據(jù)，此過(guò)程中編譯器會(huì)判斷3 個(gè)float 類(lèi)型的數(shù)據(jù)讀取地址是否連續(xù)，可以完成向量化。

圖6 HIP 程序?qū)嵗鼺ig.6 Example of HIP program

2.1 向量化方法實(shí)現(xiàn)

本文所提出的向量化方法，旨在處理LDS 中的訪(fǎng)存指令的合并。LDS 訪(fǎng)存方式在對(duì)多個(gè)連續(xù)的float 數(shù)據(jù)進(jìn)行訪(fǎng)存時(shí)，需要使用多條訪(fǎng)存指令分別實(shí)現(xiàn)數(shù)據(jù)存取［23］。該方法通過(guò)對(duì)程序中LDS 訪(fǎng)存指令的訪(fǎng)存地址進(jìn)行連續(xù)性判斷，將多條LDS 訪(fǎng)存指令合并，進(jìn)而提升訪(fǎng)存效率。

LDS 訪(fǎng)問(wèn)向量化算法流程如圖7 所示，以下以load 指令為例說(shuō)明算法流程。首先，分別對(duì)LLVM IR基本塊中地址空間指向LDS 內(nèi)存空間的所有l(wèi)oad 指令進(jìn)行遍歷，同時(shí)為了防止load 指令過(guò)多而導(dǎo)致的處理延遲過(guò)長(zhǎng)，該方法將所有的load 指令分組為多個(gè)指令塊，每個(gè)指令塊中的指令數(shù)最多為64 條；然后，遍歷指令塊中的所有指令，循環(huán)執(zhí)行并選出地址連續(xù)的多個(gè)指令保存在指定的集合中，等待完成最終向量化的實(shí)現(xiàn)；當(dāng)指令集合中完成了訪(fǎng)存地址連續(xù)的幾條指令收集后，獲取到連續(xù)數(shù)據(jù)的首地址，即可完成一次訪(fǎng)存指令的合并從LDS 中讀取多個(gè)數(shù)據(jù)存儲(chǔ)在連續(xù)的VGPR 中，完成指令塊中其中一部分的指令向量化，而后該方法將繼續(xù)遍歷后續(xù)指令，選擇符合向量化標(biāo)準(zhǔn)的指令放入集合，最終實(shí)現(xiàn)一個(gè)指令塊中所有可向量化指令的合并。

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

算法在實(shí)現(xiàn)訪(fǎng)存向量化之前，需要對(duì)每條LDS 訪(fǎng)存指令的訪(fǎng)存地址進(jìn)行分析，判斷其是否符合向量化條件并存儲(chǔ)于指令集合Instrs 中。針對(duì)上文所給出的程序?qū)嵗瑘D8展示了在LLVM IR 中，使用算法所遍歷到的其中一組最終放入集合Instrs中的load指令，而后檢查指令集合Instrs 中哪些指令的訪(fǎng)存地址具有連續(xù)性，采取索引鏈表的形式來(lái)表示程序中存在的可向量化訪(fǎng)存指令序列，并按照鏈表序列完成向量化。

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

對(duì)于每一個(gè)指令塊，如算法1 所示，使用并查集方法建立連續(xù)指令鏈表。算法首先對(duì)指令塊中的指令進(jìn)行順序重排操作，按順序?yàn)榭上蛄炕噶罱⑺饕湵恚罄m(xù)對(duì)鏈表中的指令完成最終向量化。具體實(shí)現(xiàn)時(shí)，算法使用一個(gè)csct 索引鏈表來(lái)表示指令序號(hào)及所指向的下一條連續(xù)指令的序號(hào)，并將這2 條連續(xù)指令在指令塊中的索引分別存入2 個(gè)數(shù)組：Heads 和Tails，它們分別是存儲(chǔ)連續(xù)訪(fǎng)問(wèn)的指令序號(hào)的頭序號(hào)和尾序號(hào)。這樣就實(shí)現(xiàn)了使用索引鏈表的方式存儲(chǔ)幾條訪(fǎng)存地址連續(xù)的指令。當(dāng)遍歷到連續(xù)地址的最后一條指令時(shí)，將該指令對(duì)應(yīng)的csct 數(shù)組值定義為-1，表示該向量化指令集合已結(jié)束。

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

圖9 可向量化指令集合最終實(shí)現(xiàn)結(jié)果Fig.9 Final implementation result of vectorizable instruction set

2.2 數(shù)據(jù)訪(fǎng)問(wèn)重疊問(wèn)題優(yōu)化

針對(duì)LDS 的訪(fǎng)問(wèn)向量化能夠在大部分程序中產(chǎn)生性能提升效果，但是其中有部分程序具有線(xiàn)程間數(shù)據(jù)訪(fǎng)問(wèn)重疊的訪(fǎng)存特征，這類(lèi)程序在實(shí)現(xiàn)向量化之后存在性能大幅下降的異常情況，并且其在使用LDS的程序中也并不罕見(jiàn)。為了實(shí)現(xiàn)向量化后程序性能的完全提升，在向量化實(shí)現(xiàn)前必須要明確的是程序所具有的訪(fǎng)存特征。本文通過(guò)實(shí)現(xiàn)對(duì)LDS 的訪(fǎng)存特征的判斷，使其最終獲得有效的性能提升。

一般來(lái)說(shuō)，LDS 的訪(fǎng)存特征都是基于程序中的多條內(nèi)存訪(fǎng)問(wèn)指令間所涉及的內(nèi)存位置關(guān)系來(lái)確定的，但是程序的運(yùn)行不僅僅要考慮到程序中不同訪(fǎng)存指令間的訪(fǎng)存位置導(dǎo)致的沖突，對(duì)于DCU 內(nèi)部的多線(xiàn)程并行過(guò)程，同一訪(fǎng)存指令中也有可能因?yàn)閿?shù)據(jù)重疊的訪(fǎng)存特征存在沖突。尤其在完成該訪(fǎng)存向量化之后，向量化實(shí)現(xiàn)了多條數(shù)據(jù)的合并訪(fǎng)問(wèn)，使得在訪(fǎng)問(wèn)向量化后的多個(gè)線(xiàn)程間，由于LDS 中具有bank 沖突的特性而產(chǎn)生數(shù)據(jù)讀取的延遲，因此對(duì)向量化方法實(shí)現(xiàn)的關(guān)鍵在于如何規(guī)避同一訪(fǎng)存指令在同時(shí)執(zhí)行的線(xiàn)程間存在的數(shù)據(jù)重疊而導(dǎo)致的延遲情況。

2.2.1 訪(fǎng)存特征檢測(cè)方法

如圖5 所示，如果實(shí)現(xiàn)了向量化訪(fǎng)問(wèn)，線(xiàn)程0 可以同時(shí)訪(fǎng)問(wèn)位于bank-0～bank-2 的3 個(gè)32 位的數(shù)據(jù)，而并行執(zhí)行的線(xiàn)程1 也要去完成3 個(gè)數(shù)據(jù)的訪(fǎng)問(wèn)，位于bank-1～bank-3，此時(shí)就產(chǎn)生了多個(gè)線(xiàn)程間的數(shù)據(jù)讀取重疊。為了避免發(fā)生bank 沖突，線(xiàn)程1 需要等待線(xiàn)程0 完成3 個(gè)數(shù)據(jù)讀取后，才可以對(duì)數(shù)據(jù)所在的bank 進(jìn)行訪(fǎng)問(wèn)讀取，這種等待造成了程序性能的嚴(yán)重下降。

在DCU 中檢測(cè)同一訪(fǎng)存指令中的訪(fǎng)存特征較為復(fù)雜，本文提出一種針對(duì)線(xiàn)程間存在的訪(fǎng)存特征的判斷方法。在第2 節(jié)所提出的HIP 程序?qū)嵗校Z(yǔ)句1 讀取了3 個(gè)連續(xù)的float 類(lèi)型數(shù)據(jù)，對(duì)語(yǔ)句1 中的連續(xù)數(shù)據(jù)讀取首地址的指令為%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。指令訪(fǎng)存地址的分析結(jié)果為（（4*%44）+（4*（1+%43）*（2+%8））+@sh_float），+，（16+（8*%8））。通過(guò)簡(jiǎn)化式子可以得出First_address=@sh_float+（%44+（%43+1+2）（2+%8））*4。其 中：@sh_float 是 該HIP 程序?qū)嵗暾?qǐng)LDS 空 間的首地址標(biāo)識(shí)符；%43 和%44 代表寄存器中分別存儲(chǔ)的threadidx.x 和threadidx.y（二維并行程序線(xiàn)程號(hào)）的值，共同完成首地址的計(jì)算；指令%add3.i184 地址分析所給出的地址計(jì)算樹(shù)如圖10 所示。

圖10 %add3.i184 指令地址計(jì)算樹(shù)Fig.10 %add3.i184 instruction address calculation tree

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

2.2.2 向量化方法優(yōu)化實(shí)現(xiàn)

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

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

3 性能分析

本文進(jìn)行LDS 訪(fǎng)存向量化的功能和性能測(cè)試，測(cè)試環(huán)境基于開(kāi)源編譯器LLVM（版本LLVM 13.0.0）搭建，其中，clang 版本為13.0.0，rocm 版本為4.5.2［24］。硬件采 用CPU+DCU 的異構(gòu)平臺(tái)，其 中，CPU 型號(hào)為Hygon C86 7185 32-core Processor，加速器為海光一號(hào)DCU。

3.1 向量化方法測(cè)試分析

選取GEMM 矩陣乘作為測(cè)試用例，在高性能計(jì)算領(lǐng)域，對(duì)矩陣乘的優(yōu)化是一個(gè)非常重要的課題。GEMM 廣泛應(yīng)用于航空航天、流體力學(xué)等科學(xué)計(jì)算領(lǐng)域，這也是高性能計(jì)算（HPC）實(shí)現(xiàn)的主要應(yīng)用場(chǎng)景。根據(jù)測(cè)試需要對(duì)劃塊實(shí)現(xiàn)的GEMM 用例作使用LDS 的調(diào)整［25］，同時(shí)選取SHOC 測(cè)試集中符合條件的測(cè)試用例——快速傅里葉變換（FFT），它在信號(hào)分析和處理領(lǐng)域有著廣泛的應(yīng)用，是實(shí)現(xiàn)眾多復(fù)雜功能的基礎(chǔ)算法。

利用上述測(cè)試用例對(duì)本文提出的LDS 訪(fǎng)存向量化方法進(jìn)行測(cè)試，得到的功能驗(yàn)證結(jié)果如表1所示。

表1 功能驗(yàn)證結(jié)果 Table 1 Functional verification results

功能驗(yàn)證結(jié)果顯示，優(yōu)化前后性能（GFlops）得到了平均1.203 的加速比，該結(jié)果表明本文方法能夠完成上文提到的LDS 連續(xù)訪(fǎng)問(wèn)向量化，且與未經(jīng)過(guò)向量化處理得到的代碼相比，經(jīng)過(guò)本文方法處理的代碼總體性能平均提升了22.6%，達(dá)到了預(yù)期的目標(biāo)。GEMM 程序在向量化前后實(shí)現(xiàn)的IR 代碼對(duì)比如圖12 所示。

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

3.2 數(shù)據(jù)訪(fǎng)問(wèn)重疊問(wèn)題測(cè)試分析

對(duì)程序中具有數(shù)據(jù)重疊訪(fǎng)存特征的向量化方法的優(yōu)化，選取具備該訪(fǎng)存特征的測(cè)試用例Stencil2D算法完成測(cè)試。

Stencil2D 算法是一種基于二維矩陣的迭代計(jì)算方法，常用于模擬物理現(xiàn)象或圖像處理等應(yīng)用場(chǎng)景。在Stencil2D 中，每個(gè)元素的值都由其周?chē)南噜徳赜?jì)算得出，這種計(jì)算方式類(lèi)似于模板，因此被稱(chēng)為Stencil。Stencil 通常需要對(duì)大型矩陣進(jìn)行高效并行計(jì)算，以提高運(yùn)算效率和速度，是一種常用的并行計(jì)算方法，可以應(yīng)用于各種領(lǐng)域的計(jì)算任務(wù)，其并行實(shí)現(xiàn)也涉及到多種技術(shù)和工具，需要根據(jù)具體情況進(jìn)行選擇和優(yōu)化。

在該測(cè)試用例的并行實(shí)現(xiàn)中，需要使用到共享內(nèi)存來(lái)加速計(jì)算。Stencil2D 算法將矩陣數(shù)據(jù)分配給多個(gè)線(xiàn)程，并將相鄰線(xiàn)程所處理的數(shù)據(jù)區(qū)域進(jìn)行重疊，以便在計(jì)算時(shí)共享一些數(shù)據(jù)，減少內(nèi)存訪(fǎng)問(wèn)和數(shù)據(jù)傳輸?shù)拈_(kāi)銷(xiāo)，具有LDS 中的存取連續(xù)數(shù)據(jù)的特征且數(shù)據(jù)具有線(xiàn)程間重疊讀取的特征［26］。

在對(duì)該測(cè)試用例實(shí)現(xiàn)了向量化優(yōu)化方法之后，再次對(duì)程序進(jìn)行性能測(cè)試，以比較優(yōu)化前后的性能差異。ALUStalledByLDS 是rocprof 中的一項(xiàng)性能指標(biāo)，代表ALU 因等待LDS 數(shù)據(jù)而被阻塞的時(shí)間比例。當(dāng)異構(gòu)程序在執(zhí)行Kernel 時(shí)，如果ALU 需要訪(fǎng)問(wèn)LDS 中的數(shù)據(jù)，而該數(shù)據(jù)還未被載入LDS，則ALU 會(huì)被阻塞，等待LDS 中的數(shù)據(jù)準(zhǔn)備好。此時(shí)，ALUStalledByLDS 指標(biāo)會(huì)統(tǒng)計(jì)ALU 被阻塞的時(shí)間占總時(shí)間的比例，反映LDS 訪(fǎng)問(wèn)延遲對(duì)異構(gòu)程序性能的影響。對(duì)Stencil2D 算法進(jìn)行性能測(cè)試，ALUStalledByLDS 指標(biāo)如表2 所示。

表2 向量化優(yōu)化前后ALUStalledByLDS 指標(biāo)對(duì)比 Table 2 Comparison of ALUStalledByLDS metrics before and after vectorization optimization

當(dāng)ALUStalledByLDS 指標(biāo)較高時(shí)，說(shuō)明異構(gòu)程序在執(zhí)行Kernel 時(shí)，ALU 被LDS 訪(fǎng)問(wèn)延遲所阻塞的時(shí)間較長(zhǎng)。測(cè)試用例ALUStalledByLDS 指標(biāo)向量化后明顯升高的情況表明，向量化方法的實(shí)現(xiàn)使存在數(shù)據(jù)訪(fǎng)存重疊的特征的程序在數(shù)據(jù)連續(xù)讀取的過(guò)程中產(chǎn)生延遲，從而向量化優(yōu)化方法實(shí)現(xiàn)之后的程序訪(fǎng)存效率降低。通過(guò)對(duì)Stencil2D 算法的分析和測(cè)試表明，使用本文提出的優(yōu)化方法能夠檢測(cè)到數(shù)據(jù)重疊的訪(fǎng)存特征，并根據(jù)訪(fǎng)存特征選取向量化實(shí)現(xiàn)方案，避免具有數(shù)據(jù)重疊訪(fǎng)存特征的程序?qū)崿F(xiàn)LDS訪(fǎng)存向量化，使向量化方法盡可能發(fā)揮優(yōu)勢(shì)。對(duì)于數(shù)據(jù)訪(fǎng)問(wèn)重疊問(wèn)題的優(yōu)化測(cè)試結(jié)果如表3 所示，可見(jiàn)經(jīng)過(guò)優(yōu)化后的程序性能提升了33%。

表3 向量化優(yōu)化前后Stencil2D 測(cè)試用例性能對(duì)比 Table 3 Comparison of Stencil2D test case performance before and after vectorization optimization

表3 結(jié)果顯示，對(duì)于共享內(nèi)存LDS 向量化的判斷方法能夠?qū)崿F(xiàn)程序性能的較大提升。此外，該優(yōu)化能夠充分將DCU 的計(jì)算能力更好地發(fā)揮出來(lái)，減少了DCU 計(jì)算部件等待LDS 訪(fǎng)問(wèn)的時(shí)間。總體來(lái)說(shuō)，通過(guò)使用合適的向量化優(yōu)化方法可以很好地提高程序性能，對(duì)于共享內(nèi)存LDS 中數(shù)據(jù)的向量化訪(fǎng)問(wèn)能夠達(dá)到充分發(fā)揮DCU 的計(jì)算能力的目的。

4 結(jié)束語(yǔ)

本文主要研究面向DCU 的共享內(nèi)存訪(fǎng)存優(yōu)化方法，實(shí)現(xiàn)針對(duì)LDS 的連續(xù)訪(fǎng)問(wèn)向量化，解決在向量化過(guò)程中由于LDS 沖突特性導(dǎo)致的具有數(shù)據(jù)訪(fǎng)問(wèn)重疊的向量化數(shù)據(jù)訪(fǎng)問(wèn)延遲問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文提出的向量化優(yōu)化方法能夠有效提高程序?qū)DS的訪(fǎng)問(wèn)效率，形成一種面向國(guó)產(chǎn)通用加速器的高效訪(fǎng)存技術(shù)。在共享內(nèi)存LDS 中的連續(xù)訪(fǎng)存向量化實(shí)現(xiàn)中，LLVM 后端實(shí)現(xiàn)指令選擇存在2 種不同形式，為進(jìn)一步優(yōu)化DCU 的訪(fǎng)存性能，后續(xù)工作將通過(guò)指令選擇確定最優(yōu)指令形式來(lái)實(shí)現(xiàn)減少訪(fǎng)存次數(shù)的優(yōu)化方案，進(jìn)一步提高程序的執(zhí)行效率。