基于線程隊(duì)列動(dòng)態(tài)規(guī)劃法的GPU性能優(yōu)化

魏雄 胡倩 王秋嫻 閆坤 許萍萍

關(guān)鍵詞：線程隊(duì)列;線程動(dòng)態(tài)規(guī)劃;加速比;線程調(diào)度;并行計(jì)算

0 引言

GPU 在大數(shù)據(jù)和人工智能領(lǐng)域表現(xiàn)出驚人的計(jì)算能力，隨著GPU 的普及，在生命科學(xué)、航空航天和國(guó)防中提供了較強(qiáng)的計(jì)算能力，特別是在2020 年新冠肺炎基因序列測(cè)序和疫情傳播預(yù)測(cè)等方面表現(xiàn)突出。

大數(shù)據(jù)和AI時(shí)代的到來(lái)使計(jì)算任務(wù)加重，面對(duì)應(yīng)用的不同資源需求，GPU的資源單核未充分利用[1]。為了解決GPU資源利用率不足的問(wèn)題，國(guó)內(nèi)外學(xué)者提出一些方法，例如JustinLuitjens[1]提出了并發(fā)內(nèi)核執(zhí)行（CKE）來(lái)支持在GPU 上并發(fā)運(yùn)行多個(gè)內(nèi)核，并且GPU 自身架構(gòu)也支持線程級(jí)并行性（Thread-level Parallelism，TLP）[2]，但大量并發(fā)線程會(huì)導(dǎo)致嚴(yán)重的帶寬問(wèn)題，內(nèi)存延遲而無(wú)法及時(shí)處理的內(nèi)存請(qǐng)求有可能會(huì)導(dǎo)致流水線暫停，降低整體性能。

為了更好地提升性能，利用GPU 的資源，本文提出了線程隊(duì)列動(dòng)態(tài)規(guī)劃法TQDP，從線程角度出發(fā)，通過(guò)提高線程的執(zhí)行次數(shù)和提升系統(tǒng)吞吐量，從而提高系統(tǒng)性能。

1 GPU

新一代GPU 體系架構(gòu)集成的計(jì)算資源越來(lái)越多，同時(shí)由于GPU 缺乏適當(dāng)?shù)捏w系架構(gòu)來(lái)支持共享，需要軟件、硬件或者軟硬件協(xié)同的方法來(lái)使用計(jì)算資源，因其復(fù)雜性導(dǎo)致GPU資源利用不足，影響整體性能。

1.1 GPU體系架構(gòu)

NVIDIA 第8 代GPUTuring 第一次使用GDDR6 DRAM內(nèi)存，并引入了新的SM 體系架構(gòu)，采用了可加速光線追蹤的RT Core，以及可用于AI推理的全新Tensor Core[3]。雖然GPU架構(gòu)經(jīng)過(guò)一代代的變化，但是大致架構(gòu)改動(dòng)不大。

圖1 是一個(gè)基線GPU 架構(gòu)圖，GPU 有多個(gè)流多處理器（Streaming Multiprocessor，SM），在每個(gè)SM 中，計(jì)算資源包括算術(shù)邏輯單元（ALU）、特殊函數(shù)單元（SFU）以及寄存器，片上內(nèi)存資源包括只讀紋理緩存和常量緩存、L1 數(shù)據(jù)緩存（D-cache）和共享內(nèi)存。在多個(gè)SMs之間共享統(tǒng)一的一個(gè)L2緩存[1]。GPU 中有多個(gè)處理器核SP，在一個(gè)時(shí)刻可以并行處理多個(gè)數(shù)據(jù)。寄存器（Reg File）是GPU 內(nèi)部的存儲(chǔ)單元，是有限存儲(chǔ)容量的高速存儲(chǔ)部件，用來(lái)暫存指令、數(shù)據(jù)和位址。線程束調(diào)度程序（Warp Scheduler）負(fù)責(zé)調(diào)度一個(gè)SM 中的Warp。Warp 是GPU 執(zhí)行程序時(shí)的調(diào)度單位，Warp 大小為32，32 個(gè)thread組織成一個(gè)Warp。

1.2 線程調(diào)度算法

GPU具有高效并行性和靈活的可編程性等特點(diǎn)，在處理數(shù)據(jù)方面有極大的優(yōu)勢(shì)。面對(duì)不同的應(yīng)用和資源需求，為了更好地管理計(jì)算資源，為線程分配資源，目前主要有先到先服務(wù)（FCFS）[4]、輪詢（RR）[5]、優(yōu)先級(jí)調(diào)度（PSA）[6]和最短線程優(yōu)先（SJF）[7]調(diào)度算法。

在出現(xiàn)長(zhǎng)線程時(shí)，從另一方面說(shuō)，盡可能地提高線程的執(zhí)行數(shù)，也可提高系統(tǒng)的吞吐量。因此，對(duì)線程進(jìn)行預(yù)處理，預(yù)估線程的執(zhí)行時(shí)間變得極為重要。另一方面，由于SJF算法本身的缺陷，導(dǎo)致執(zhí)行時(shí)間較長(zhǎng)的線程長(zhǎng)時(shí)間得不到響應(yīng)，降低了系統(tǒng)吞吐量和整體性能。

因此，從線程調(diào)度的角度，提出了TQDP，難點(diǎn)在于線程的預(yù)處理上，根據(jù)線程的執(zhí)行時(shí)間進(jìn)行排序，以及需要考慮執(zhí)行時(shí)間較長(zhǎng)線程的調(diào)度。

2 TQDP

隊(duì)列線程是按照一定的管理策略分配計(jì)算資源，通過(guò)科學(xué)合理的方法提高線程的響應(yīng)率和系統(tǒng)的性能。

2.1 TDQP

按照線程預(yù)處理獲得的執(zhí)行時(shí)間從短到長(zhǎng)加入到等待隊(duì)列，按照隊(duì)列中優(yōu)化后的順序執(zhí)行線程能更好地提升系統(tǒng)的吞吐量和性能。在對(duì)線程進(jìn)行預(yù)處理時(shí)，其中隊(duì)列中線程的執(zhí)行順序需要比較線程的執(zhí)行時(shí)間和到達(dá)時(shí)間。如果某一兩個(gè)線程執(zhí)行時(shí)間均是0.01 ms，那么就比較線程的到達(dá)時(shí)間。

TQDP 算法流程如圖2所示，通過(guò)獲取待執(zhí)行線程的相關(guān)信息，線程執(zhí)行時(shí)間和等待時(shí)間，在隊(duì)列中按從小到大排序。在執(zhí)行過(guò)程中有新的線程請(qǐng)求加入隊(duì)列，隊(duì)列中線程執(zhí)行時(shí)間乘以算子（ <1， 的取值會(huì)在實(shí)驗(yàn)部分說(shuō)明）， '= * 計(jì)算，再根據(jù)新線程-1的大小插入等待隊(duì)列中，隊(duì)列中出現(xiàn)相同，則比較不同線程的等待時(shí)間的大小，較大線程的順序有較大的優(yōu)先級(jí)。

2.2 TQDP算法模型

TQDP 方法中， 為所有線程執(zhí)行時(shí)間之和， 為線程的到達(dá)時(shí)間（提交時(shí)間）， 為線程的服務(wù)時(shí)間（執(zhí)行時(shí)間）， 為線程的周轉(zhuǎn)時(shí)間， 為線程的等待時(shí)間。線程個(gè)數(shù)為， 為當(dāng)前系統(tǒng)時(shí)間。用三參數(shù)法，表示為，在一個(gè)GPU 中多個(gè)SM 上，到達(dá)時(shí)間各不相同的線程，獲取總的最小執(zhí)行時(shí)間，即：

2.3 TQDP的實(shí)現(xiàn)

TQDP的具體方案為：

①對(duì)于待執(zhí)行的kernel進(jìn)行預(yù)處理，獲取線程執(zhí)行時(shí)間、到達(dá)時(shí)間、等待時(shí)間等相關(guān)參數(shù)信息，存儲(chǔ)在不同的數(shù)組中，將獲取的執(zhí)行時(shí)間在待執(zhí)行隊(duì)列中進(jìn)行排序，更新線程的執(zhí)行隊(duì)列。

②新加入的線程，在插入到執(zhí)行隊(duì)列中之前，執(zhí)行時(shí)間數(shù)組中對(duì)執(zhí)行時(shí)間設(shè)置算子，然后將新線程插入到隊(duì)列中，并更新執(zhí)行隊(duì)列。

③如果執(zhí)行時(shí)間數(shù)組中對(duì)應(yīng)線程出現(xiàn)相同數(shù)值，則在等待時(shí)間數(shù)組中尋找對(duì)應(yīng)線程的等待時(shí)間，比較2 個(gè)線程的等待時(shí)間，并將等待時(shí)間較長(zhǎng)的線程優(yōu)先級(jí)提高。

④按照更新的執(zhí)行隊(duì)列中的線程順序，系統(tǒng)執(zhí)行kernel。

3 實(shí)驗(yàn)

本文的實(shí)驗(yàn)環(huán)境為GPGPU-Sim3.2.2 [8]，算法的框架為OpenCL，配置的參數(shù)如表1 所示。實(shí)驗(yàn)中的取值對(duì)執(zhí)行隊(duì)列中線程執(zhí)行順序優(yōu)化的影響以及對(duì)于系統(tǒng)執(zhí)行算法的影響，根據(jù)執(zhí)行隊(duì)列中線程執(zhí)行時(shí)間大小、線程等待時(shí)間長(zhǎng)短以及提高線程優(yōu)先級(jí)等因素考慮后將取值設(shè)定為0.75。實(shí)驗(yàn)比較的性能相關(guān)參數(shù)有加權(quán)加速比（Weighted Speedup）、系統(tǒng)吞吐量（System Throughput，STP）、平均標(biāo)準(zhǔn)化周轉(zhuǎn)時(shí)間（Average Normalized Turnaround Time，ANTT）等，主要使用Weighted Speedup 和ANTT 評(píng)估，Weighted Speedup 是運(yùn)行kernel的加速比之和，將其定義為并行執(zhí)行中的規(guī)范化IPC，而非獨(dú)立執(zhí)行中的IPC，并納入了公平性（Fairness）。測(cè)試的基準(zhǔn)程序集為Parboil及Rodinia等。

圖3 顯示了不同方法對(duì)10 個(gè)不同基準(zhǔn)測(cè)試的WeightedSpeedup 的影響。整體而言，與參考文獻(xiàn)[9] 中的方法++DynCTAT，Mod+Bypass，PBS，BF，opt相比，本文所提出的方法TQDP 明顯優(yōu)于其他方法。就平均結(jié)果，++DynCTAT，Mod+Bypass，PBS，BF，opt 與TQDP 分別為1.087，1.095，1.098，1.204，1.235，1.245，TQDP比其他方法分別提高了14%，13.7%，13.3% ，3.4% ，8.8% 。TQDP 在BLK_ BFS2、FWT_TRD、JPEG_CFD、SCP_TRD 等基準(zhǔn)測(cè)試中表現(xiàn)的Weighted Speedup較于其他方法有明顯提升。TQDP 一開(kāi)始對(duì)于線程進(jìn)行了預(yù)處理，獲取了很多需要的參數(shù)信息，在之后的執(zhí)行過(guò)程中，大大減少了系統(tǒng)對(duì)于線程的處理過(guò)程。

與++DynCTAT、Mod+Bypass，PBS，BF，opt 相比，本文所提出的方法TQDP 在BFS2_FFT，F(xiàn)FT_TRD，F(xiàn)WT_TRD，JPEG_CFD，JPEG_LIB等基準(zhǔn)測(cè)試表現(xiàn)出的Fairness 明顯優(yōu)于其他方法，如圖4 所示。正如之前介紹的，TQDP 對(duì)于長(zhǎng)短線程都有考慮到，特別是對(duì)于長(zhǎng)線程在執(zhí)行過(guò)程中長(zhǎng)時(shí)間得不到響應(yīng)的情況，通過(guò)TQDP 算法，可以大大降低發(fā)生的概率，正是由于考慮到了長(zhǎng)線程的調(diào)度情況，因此TQDP 的Fairness 參數(shù)表現(xiàn)結(jié)果好。

由于基準(zhǔn)測(cè)試程序集數(shù)量過(guò)多，本文將所用的基準(zhǔn)測(cè)試分為了2 類：計(jì)算密集型和內(nèi)存密集型，分別表示為C 和M，然后排列了3 種組合：C+M，C+C，M+M。如圖5 所示，對(duì)于STP，TQDP、SMK、SMK-（P+W）分別為1.28，1.38，1.40，與文獻(xiàn)[11]中的方法SMK、SMK-（P+W）相比，TQDP 分別提高了8.5%和1.4%。對(duì)于C+C、M+M，TQDP都有明顯的改進(jìn)，目的就是通過(guò)提升系統(tǒng)吞吐量來(lái)提高系統(tǒng)性能，從實(shí)驗(yàn)結(jié)果來(lái)說(shuō)，這一目的是達(dá)到了。TQDP 算法本身是從提高線程執(zhí)行數(shù)、提升系統(tǒng)吞吐量的角度對(duì)隊(duì)列中線程執(zhí)行順序進(jìn)行優(yōu)化。

ANTT平均標(biāo)準(zhǔn)化周轉(zhuǎn)時(shí)間越低越好，意味著響應(yīng)時(shí)間更接近于獨(dú)立執(zhí)行。吞吐量STP很好，那么ANTT 也應(yīng)該很好。正如之前所說(shuō)，對(duì)于STP，與SMK 和SMK-（P+W）相比，TQDP分別提高了8.5%和1.4%，而且對(duì)于ANTT，如圖6 所示，分別為1.85，1.60，1.50，與SMK和SMK-（P+W）相比，TQDP 分別提高了18.9%和6.3%。因?yàn)?，TQDP 對(duì)于吞吐量和公平性都是好的，所以它的ANTT 值是最低的。另一方面，SMK在STP 方面很弱，因此在ANTT方面也很弱。結(jié)合之前的實(shí)驗(yàn)結(jié)果，圖5中TQDP表現(xiàn)的結(jié)果優(yōu)于其他2種方法，因此在圖6中，TQDP 的實(shí)驗(yàn)結(jié)果也優(yōu)于其他方法，符合預(yù)期。

總之，實(shí)驗(yàn)結(jié)果表明本文提出的方法TQDP優(yōu)化了系統(tǒng)性能。實(shí)驗(yàn)結(jié)果證明，TQDP 與++DynCTAT，Mod+Bypass，PBS，BF，opt 相比，Weighted Speedup 比其他方法分別提高了14%，13.7%，13.3%，3.4%，8.8%，TQDP 在預(yù)處理時(shí)減少了后面系統(tǒng)對(duì)線程的處理過(guò)程。與SMK 和SMK-（P+W）相比，STP 分別提高了8.5%和1.4%，TQDP 主要的目標(biāo)是對(duì)線程隊(duì)列中線程執(zhí)行順序的優(yōu)化，提高線程執(zhí)行數(shù)，提升系統(tǒng)吞吐量，優(yōu)化系統(tǒng)性能。

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

本文證明了提出的方法TQDP 確實(shí)可以優(yōu)化系統(tǒng)性能。在測(cè)試的大部分基準(zhǔn)測(cè)試中，TQDP 表現(xiàn)優(yōu)秀，實(shí)驗(yàn)結(jié)果表現(xiàn)基本與預(yù)期一致，實(shí)驗(yàn)?zāi)康幕緦?shí)現(xiàn)，從線程角度出發(fā)，通過(guò)優(yōu)化線程執(zhí)行隊(duì)列的執(zhí)行順序，提高線程的執(zhí)行次數(shù)，縮減程序執(zhí)行時(shí)間，提升系統(tǒng)性能。就測(cè)試的相關(guān)參數(shù)平均而言，TQDP 相比其他方法都得到了很大的提升，但仍有不足之處，比如算法中對(duì)于算子數(shù)值的設(shè)置，簡(jiǎn)單考慮了算子的取值范圍，粗略設(shè)定了數(shù)值，并沒(méi)有深入研究設(shè)置不同數(shù)值對(duì)于算法的影響，以及不同程度大小算子對(duì)于線程執(zhí)行隊(duì)列的優(yōu)化效果如何。在之后的工作中，將會(huì)從這一方面進(jìn)行考慮，對(duì)算子的數(shù)值進(jìn)行優(yōu)化，探究算子的不同取值對(duì)于本算法優(yōu)化效果影響。