基于指令流水線的CUDA核函數(shù)時間預(yù)測模型

關(guān)鍵詞：CUDA;時間預(yù)測;靜態(tài);PTX;流水線

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

0 引言（Introduction）

GPU（Graphics Processing Unit）通過單指令多線程的模式執(zhí)行程序，在處理大運(yùn)算量的計算需求時，具有較好的加速性能。在學(xué)術(shù)界，針對CUDA程序的優(yōu)化是一項常見且重要的任務(wù)，例如對拼圖算法的并行研究[1]就是一個典型的例子。然而，GPU計算處理的任務(wù)具有計算復(fù)雜、時間成本高等特點，這給代碼優(yōu)化或任務(wù)調(diào)度帶來了不小的挑戰(zhàn)。因此，通過對CUDA核函數(shù)執(zhí)行時間的準(zhǔn)確預(yù)測，可以進(jìn)一步優(yōu)化任務(wù)調(diào)度，提高整體的計算效率，這一研究具有重要意義。

MOOLCHANDANI[2]提出用訪存指令和計算指令的線程束并行關(guān)系揭示延遲隱藏，但沒有很好地解決如何預(yù)測時間的問題。BARAI等[3]提出了一種詳細(xì)提取特征的模型，但需要獲取的特征過于龐大，無法靜態(tài)收集。鑒于機(jī)器學(xué)習(xí)在預(yù)測方面的顯著優(yōu)勢，其在這一領(lǐng)域的應(yīng)用受到了廣泛關(guān)注，但它需要一個大型數(shù)據(jù)集表征可能影響實際 GPU 執(zhí)行的大多數(shù)特征。AMARIS等[4]對3種不同的機(jī)器學(xué)習(xí)方法進(jìn)行了比較，以預(yù)測 CUDA核函數(shù)的執(zhí)行時間，結(jié)果發(fā)現(xiàn)分析模型與機(jī)器學(xué)習(xí)方法在預(yù)測性能上各有優(yōu)勢。

本研究采用了一種創(chuàng)新方法，將分析建模與機(jī)器學(xué)習(xí)兩者結(jié)合應(yīng)用。首先，通過流水線模擬線程的運(yùn)行情況，得到未考慮內(nèi)存離散程度和分支分歧的核函數(shù)執(zhí)行時鐘周期。其次，使用內(nèi)存離散模型分析程序的未合并全局訪存程度。最后，將流水線模擬的時鐘周期和未合并全局訪存程度，結(jié)合程序的基本塊執(zhí)行路徑作為工作流網(wǎng)絡(luò)的輸入，最終準(zhǔn)確地預(yù)測出CUDA核函數(shù)的執(zhí)行時間。

1 相關(guān)理論（Related theory）

1.1 GPU架構(gòu)

GPU是一種高吞吐量處理器，其核心結(jié)構(gòu)由多個并行運(yùn)行的流式多處理器（Streaming Multiprocessor，SM）陣列組成。不同架構(gòu)的GPU包含的SM的數(shù)量會有所變化。每個SM內(nèi)部都配備有多個ALU（Arithmetic And Logic Unit）內(nèi)核，這些ALU內(nèi)核擁有專用的計算單元，例如單精度單元（SinglePrecision Unit，SP）、雙精度單元（Double Precision Unit，DP）和特殊功能單元（Special Function Unit，SFU）。每個SM都有一個專用的1級緩存，用于緩存全局內(nèi)存;而2級緩存由所有SM共享，此外每個SM都有一個專用的共享內(nèi)存。除了計算單元，每個SM還有一定數(shù)量的warp調(diào)度器，負(fù)責(zé)選擇調(diào)度和執(zhí)行warp。

1.2 并行執(zhí)行及編程

本文專注于探討NVIDIA 架構(gòu)下的GPU 程序，特別是CUDA程序。在CUDA編程模型中，運(yùn)行在GPU上的部分稱為核函數(shù)（kernel）。CUDA的術(shù)語中，從同一核函數(shù)生成的所有線程都被分到一個網(wǎng)格（grid）中，grid由許多線程塊（block）組成。每個block由多個線程組成，同一個block下的線程可以通過共享內(nèi)存進(jìn)行通信，不同block之間的線程則無法通信。因此，塊與塊之間是高度并行的。每32個線程組成一個warp。GPU使用單指令多線程模型命令warp中的線程以鎖步方式執(zhí)行相同的指令。當(dāng)指令是對DRAM（DynamicRandom Access Memory）或全局內(nèi)存進(jìn)行加載或存儲時，如果warp中線程的訪問地址在內(nèi)存中彼此相鄰，GPU 內(nèi)存子系統(tǒng)可以將線程合并或分組到幾個DRAM 事務(wù)中，從而減少訪問延遲，這種優(yōu)化方式就是合并的訪存（Coalesced MemoryAccess）。否則，若訪問在內(nèi)存中是分散的，則需要更多的DRAM事務(wù)，此類訪存方式稱為未合并訪存（UncoalescedMemory Access）。

1.3 指令集架構(gòu)

NVIDIA提供了獨(dú)立于機(jī)器的虛擬匯編指令集，稱為并行執(zhí)行線程（Parallel Thread Execution）。PTX被認(rèn)為是源代碼的中間表示，類似于LLVM IR（LLVM Intermediate Representation），并且它不會在設(shè)備上被直接執(zhí)行。因此，當(dāng)用作跨不同GPU架構(gòu)進(jìn)行性能建模的基礎(chǔ)時，PTX指令集展現(xiàn)出顯著的優(yōu)勢——相同的PTX指令集可用于任何GPU。

2 時間預(yù)測模型架構(gòu)（Architecture of timeprediction model）

本文所提時間預(yù)測模型架構(gòu)圖如圖1所示。首先，該模型將CUDA程序轉(zhuǎn)換為PTX代碼，根據(jù)PTX代碼可以分析得到指令的具體類型和指令順序，并將其組成任務(wù)列表。其次，將任務(wù)列表對應(yīng)的具體硬件配置和指令延遲放入流水線模擬器，得到流水線預(yù)測時間，同時內(nèi)存離散模型根據(jù)任務(wù)列表得到不同分支分歧下的未合并次數(shù)。這些未合并訪問次數(shù)、流水線預(yù)測時間及核函數(shù)啟動開銷一起作為預(yù)測執(zhí)行時間的輸入。最后，預(yù)測執(zhí)行時間通過工作流網(wǎng)絡(luò)，將之前的輸入及PTX的節(jié)點路徑作為特征，預(yù)測最終的核函數(shù)執(zhí)行時間。

2.1PTX分析

每一條PTX語句都包含一個命令，命令內(nèi)包含該指令的執(zhí)行方式以及使用的寄存器的數(shù)據(jù)大小。值得注意的是，每一條PTX語句的地址數(shù)量不等，首地址為數(shù)據(jù)放入的寄存器名稱，之后的地址為數(shù)據(jù)讀取的寄存器名稱。一個PTX內(nèi)部由一個或多個指令塊組成，每個指令塊代表一個CUDA程序中的一個核函數(shù)，指令塊之間由大括號分隔。每個指令塊可以進(jìn)一步細(xì)分為基本塊，基本塊是在SM 上串行的一組指令。即每個基本塊只能從塊中的第一條指令進(jìn)入，并從塊中的最后一條指令退出。在PTX中，基本塊有兩種流出分支：一種是順序執(zhí)行完當(dāng)前塊后流出到緊鄰的下一個基本塊;另一種是執(zhí)行完當(dāng)前塊后跳轉(zhuǎn)到另一個特定標(biāo)記的基本塊。為了獲取PTX的正確指令流程，通常需要借助控制流程圖。官方提供了一種獲取控制流程圖的方式，但是該方式只能得到基本塊的大致分支，無法了解一個基本塊是否被執(zhí)行了多次，即是否存在循環(huán)的情況。對此，本研究使用LLVM提供的工具在靜態(tài)編譯狀態(tài)下，幫助判斷基本塊的循環(huán)次數(shù)。由于PTX代碼是基于單線程的視角，實際上每個線程的具體執(zhí)行情況可能會因分支分歧而有所不同。為了簡化分析，本研究選擇采用大部分線程會執(zhí)行的順序作為任務(wù)列表的輸入[5]。CUDA程序提供了支持PTX的內(nèi)聯(lián)匯編，通過內(nèi)聯(lián)匯編進(jìn)行微基準(zhǔn)測試，可以對每種PTX指令進(jìn)行計時，進(jìn)而得出每種指令具體的延遲。不同的架構(gòu)有不同的硬件配置，導(dǎo)致在不同架構(gòu)下，每種指令的延遲會有所不同，程序的執(zhí)行時間也會隨著硬件不同而發(fā)生變化，因此每當(dāng)更換硬件環(huán)境時，都需要對單指令的延遲進(jìn)行一次額外的測試。

2.2 任務(wù)列表

目前的GPU架構(gòu)一般由多個SM 組成，每個SM 都有自己的指令緩沖區(qū)、調(diào)度器和調(diào)度單元。而且，每個SM 還擁有豐富的計算資源，能夠處理不同的ALU 操作。具體來說，每個SM包含數(shù)個warp調(diào)度器，它們嘗試在數(shù)個時鐘周期內(nèi)向給定的warp發(fā)出一個或多個指令，如果指令之間不存在依賴性，那么后續(xù)指令可以在前一個指令之前就被發(fā)出。為了更準(zhǔn)確地模擬這種并行處理環(huán)境，本文設(shè)計了任務(wù)列表數(shù)據(jù)結(jié)構(gòu)作為流水線模擬器的輸入，每個任務(wù)列表代表一個線程的指令順序。任務(wù)列表由眾多任務(wù)組成，每個任務(wù)代表一條指令，包含指令編號、任務(wù)列表編號、計算單元索引、指令延遲、模擬的寄存器名稱、所屬的基本塊等。其中，計算單元索引是根據(jù)SM的資源進(jìn)行分類的，可能包括單精度處理單元（SP）、雙精度處理單元（DP）及特殊功能單元（SFU）等。模擬的寄存器名稱來源于對應(yīng)的PTX。根據(jù)PTX的命令，每個線程讀取寫入的寄存器可能不同，在任務(wù)列表中，這些寄存器通過加上線程本身的索引進(jìn)行區(qū)分。在PTX代碼中，由于無法體現(xiàn)緩存命中、訪存合并等信息，因此假設(shè)所有數(shù)據(jù)已經(jīng)被保存在寄存器中。這意味著，在PTX語句的執(zhí)行過程中，每當(dāng)遇到一個新的寄存器，可以認(rèn)為實際上執(zhí)行了一次訪問全局內(nèi)存的命令。為了簡化流水線的模擬，任務(wù)列表默認(rèn)程序的訪存是合并的。

考慮到GPU核函數(shù)的計算性能與硬件環(huán)境之間存在強(qiáng)相關(guān)性，若分析模型中的硬件環(huán)境發(fā)生改變，則對應(yīng)模型的參數(shù)也需要進(jìn)行微調(diào)整。本文在評估中使用了GeForce RTX 2080Ti顯卡，即圖靈架構(gòu)。

3 模擬器及模型（Simulator and models）

3.1 核函數(shù)啟動開銷

初始的核函數(shù)執(zhí)行時間是在流水線模型運(yùn)行完成后得到的。然而實驗發(fā)現(xiàn)，對于一些指令數(shù)量很少的核函數(shù)來說，實際執(zhí)行時間超出了模擬時間。即使是無指令的核函數(shù)，隨著線程數(shù)量的增加，核函數(shù)的執(zhí)行時間也會逐漸增加。通過對空核函數(shù)執(zhí)行時間與線程分配數(shù)量進(jìn)行記錄發(fā)現(xiàn)，空核函數(shù)執(zhí)行時間與啟動參數(shù)之間呈線性關(guān)系。圖靈架構(gòu)下的核函數(shù)啟動時延公式為

l=3.824×10^-6·n_t+2.882 （1）

其中：l 是空指令核函數(shù)的執(zhí)行時間，n_t 為核函數(shù)設(shè)置的總線程數(shù)。得到的核函數(shù)啟動開銷將作為預(yù)測執(zhí)行時間的輸入。

3.2 指令流水線模擬器

指令流水線模擬器是基于SM 資源進(jìn)行建模的超標(biāo)量流水線，它有兩個子系統(tǒng)，分別為計算子系統(tǒng)和存儲子系統(tǒng)。計算子系統(tǒng)又分為DP、SP和SFU三個子管道，分別用于處理不同的指令類型。三個不同的子管道之間可以并行運(yùn)行，由warp調(diào)度器亂序派遣指令進(jìn)入。線程束調(diào)度器的數(shù)量以及子管道的容量由對應(yīng)的硬件配置決定。亂序調(diào)度的目的是延遲隱藏，使得在同一時間內(nèi)，各個子管道內(nèi)部的指令數(shù)量盡可能最大化。

模型主要由兩個參數(shù)表征：發(fā)出兩個獨(dú)立指令之間所需的周期數(shù)（發(fā)射延遲），以及指令進(jìn)入管道后需要執(zhí)行的周期數(shù)（這里稱為單指令延遲）。由于warp采用了單指令多線程的執(zhí)行方式，而流水線模型通常是針對計算或內(nèi)存指令進(jìn)行調(diào)度的，因此在這個模型中，warp被視為基本的調(diào)度單元。

指令流水線模型如圖2所示。在圖靈架構(gòu)下，每個SM 配備了4個warp調(diào)度器，即流水線模型可以同時調(diào)度4個warp。本研究進(jìn)一步結(jié)合了計分板策略，用于優(yōu)化調(diào)度過程。當(dāng)功能部件存在可用于處理指令的資源時，調(diào)度器會根據(jù)對應(yīng)的任務(wù)列表發(fā)出對應(yīng)的新指令。如果調(diào)度器沒有找到可用的指令，那么調(diào)度器會在下一個時鐘周期選擇新的warp。指令將根據(jù)其類型，請求進(jìn)入對應(yīng)的子管道。每個子管道根據(jù)配置可以并行處理一定數(shù)量的指令。若子管道無法接受任何新指令，則該指令進(jìn)入等待狀態(tài)，直到子管道出現(xiàn)空閑并可以接受下一指令。然后，該指令將在給定的延遲時間內(nèi)占用該資源。

本研究使用流水線模擬單個SM 下的核函數(shù)運(yùn)行情況。為實現(xiàn)這一目標(biāo)，研究人員采用了并行編程，構(gòu)建了4個線程，分別模擬4個warp調(diào)度器的行為。研究假設(shè)所有子工作負(fù)載都能在SM上均勻地劃分，并進(jìn)行并行處理。模擬器首先需要初始化寄存器狀態(tài)表和功能部件表，寄存器狀態(tài)表用來記錄每個寄存器是否在等待某一功能部件的運(yùn)算結(jié)果，功能部件表用來記錄當(dāng)前各個資源的占用情況。

每個指令在模擬器中有4種狀態(tài)，即流出、讀操作、執(zhí)行、寫回。為了確保指令能夠按照正確的順序和時機(jī)執(zhí)行，同時避免資源競爭和沖突，每次指令狀態(tài)的切換需要根據(jù)功能部件狀態(tài)、寄存器狀態(tài)以及指令自身狀態(tài)進(jìn)行條件檢驗。當(dāng)warp調(diào)度器在某一時鐘周期內(nèi)因為無可執(zhí)行命令而暫停自身時，它會被掛起，直至下一個時鐘周期的到來。全局時鐘周期用來記錄模擬器下的執(zhí)行時間。在每次循環(huán)中，全局時鐘周期會根據(jù)模擬情況增加，增加的量從1至功能部件內(nèi)部最小剩余執(zhí)行周期不等，這取決于模擬器的具體運(yùn)行情況。模擬器會一直運(yùn)行，直至SM內(nèi)所有warp的任務(wù)列表清空為止。最終，指令流水線模擬器返回全局時鐘周期作為預(yù)測執(zhí)行時間的輸入。

3.3 內(nèi)存離散模型

在流水線模型使用任務(wù)列表時，程序的內(nèi)存訪問被假設(shè)為合并的，但在實際情況下，內(nèi)存訪問可能是非合并的，這會導(dǎo)致執(zhí)行時間的延長。有研究人員發(fā)現(xiàn)，可以通過對線程索引追蹤來判斷指令是否存在非合并訪存[6]。合并的全局內(nèi)存訪問通常具有兩個主要特點：一是指令對于線程索引值的依賴性，其中依賴關(guān)系可以表示為對線程索引值的常數(shù)波動;二是指令獨(dú)立于線程索引且一般為常數(shù)。因此，本研究通過對指令與線程索引的關(guān)系來判斷程序的非合并訪存程度，并作為預(yù)測執(zhí)行時間的輸入。

3.4 預(yù)測執(zhí)行時間

在PTX代碼分析中，因為問題的復(fù)雜性，分支分歧的影響通常被忽略。然而，機(jī)器學(xué)習(xí)方法可以通過監(jiān)督學(xué)習(xí)捕獲分支特征。本研究使用了工作流性能預(yù)測網(wǎng)絡(luò)[7]，通過PTX的控制流程圖獲取分支分歧對執(zhí)行時間的影響。控制流程圖的節(jié)點數(shù)量設(shè)置為27個，這個數(shù)量基本能夠滿足大部分核函數(shù)的基本塊數(shù)量。若核函數(shù)的基本塊數(shù)量超過了27個，則需要對部分基本塊進(jìn)行縮略。若基本塊只有一種流出分支且分支是緊接著的下一個基本塊，則這兩個基本塊可以算作同一個節(jié)點。

本研究將核函數(shù)啟動開銷、流水線模擬器的全局時鐘周期、非合并訪存的次數(shù)及基本塊路徑代表的控制流程圖作為特征，通過工作流網(wǎng)絡(luò)，對CUDA 核函數(shù)的運(yùn)行時間進(jìn)行精準(zhǔn)預(yù)測。

4 實驗與結(jié)果（Experiment and result）

4.1 實驗數(shù)據(jù)集

本研究使用了Rodinia基準(zhǔn)測試套件中的7個應(yīng)用程序及其包含的12個核函數(shù)，同時選用了Polybench基準(zhǔn)測試套件中的15個應(yīng)用程序及其包含的34個核函數(shù)。為了全面評估核函數(shù)的性能，研究人員測試了不同線程總數(shù)下，相同核函數(shù)的執(zhí)行時間。每個核函數(shù)的實際執(zhí)行時間使用Nsight在GeForce RTX 2080 Ti上運(yùn)行獲得。

4.2 預(yù)測結(jié)果

本研究采用平均絕對百分比誤差（Mean Absolute PercentageError，MAPE）作為評估指標(biāo)，該指標(biāo)常用于評估時間序列預(yù)測。MAPE值越小，代表結(jié)果越準(zhǔn)確，其公式為

其中：A_t 為實際的核函數(shù)執(zhí)行時間，F(xiàn)_t 為預(yù)測的執(zhí)行時間。實驗獲得的平均絕對百分比誤差為22.87%。

圖3展示了實際執(zhí)行時間與預(yù)測執(zhí)行時間的比較結(jié)果，其中橫坐標(biāo)為預(yù)測執(zhí)行時間，縱坐標(biāo)為實際執(zhí)行時間。從圖3中可以看出，大部分的預(yù)測結(jié)果是接近真實值的。在執(zhí)行時間較長的樣本上，預(yù)測結(jié)果要相對差一些。這主要是因為實驗沒有考慮訪存的命中率這一因素。隨著執(zhí)行時間的增長，訪存命中率對結(jié)果的影響越大。

圖4展示了樣本的誤差分布，大約有81%的樣本在真實值的0%～25%，而大約15%的樣本在真實值的26%～50%，只有少部分樣本超過了真實值的50%。

表1顯示了模型在不同模塊下的誤差情況。通過對比可以發(fā)現(xiàn)，對PTX代碼中的基本塊進(jìn)行循環(huán)分析的模型相較于單純使用流水線的模型，其效果提升顯著。這一提升的主要原因在于，基本塊的循環(huán)復(fù)用改變了原有的指令依賴，擴(kuò)展了線程的任務(wù)列表。這對流水線模擬器產(chǎn)生了巨大的影響，所以對基本塊的循環(huán)分析是必要的。內(nèi)存離散模塊對整體模型的提升在于考慮了程序的離散程度和分支分歧。

4.3 相關(guān)結(jié)果比較

使用相同的架構(gòu)，從Polybench基準(zhǔn)測試中選擇部分核函數(shù)在多個線程總數(shù)下進(jìn)行對比，對比結(jié)果如表2所示。采用機(jī)器學(xué)習(xí)的模型1[8]的MAPE值要高于本文模型的MAPE值，達(dá)到了52%。機(jī)器學(xué)習(xí)的MAPE值分布比較分散，表明程序間差異性較大，機(jī)器學(xué)習(xí)并未完全提取特征，比如指令的依賴性。與采用靜態(tài)分析的模型2[9]相比，本文模型的MAPE值要更好一些，并且本文模型在預(yù)測執(zhí)行時間較長的核函數(shù)時，結(jié)果更貼近實際執(zhí)行時間。

5 結(jié)論（Conclusion）

本研究對PTX代碼進(jìn)行了深入分析，旨在實現(xiàn)模型在不同的架構(gòu)下的遷移。模型充分考慮了并行性與資源限制等因素，更好地捕捉到了核函數(shù)中的延遲隱藏。同時，模型也考慮了離散程度以及分支分歧對時間的影響，符合核函數(shù)的實際執(zhí)行情況。實驗結(jié)果表明，本文模型對核函數(shù)執(zhí)行時間的預(yù)測結(jié)果具有較高的準(zhǔn)確性?？傮w而言，本文模型在靜態(tài)分析下能夠達(dá)到較好的預(yù)測效果，這不僅有助于任務(wù)調(diào)度的優(yōu)化，還能為開發(fā)人員提供有力的支持，助力其進(jìn)行更為高效的代碼優(yōu)化工作。

作者簡介：

張建定（1998-），男，碩士生。研究領(lǐng)域：并行計算。

陳根浪（1978-），男，博士，教授。研究領(lǐng)域：大數(shù)據(jù)及人工智能，并行計算，生命健康。

明宗禹（1999-），男，碩士生。研究領(lǐng)域：并行計算。