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

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

0 引言

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

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

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

1 GPU

新一代GPU 體系架構(gòu)集成的計算資源越來越多，同時由于GPU 缺乏適當(dāng)?shù)捏w系架構(gòu)來支持共享，需要軟件、硬件或者軟硬件協(xié)同的方法來使用計算資源，因其復(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)過一代代的變化，但是大致架構(gòu)改動不大。

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

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

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

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

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

2 TQDP

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

2.1 TDQP

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

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

2.2 TQDP算法模型

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

2.3 TQDP的實現(xiàn)

TQDP的具體方案為：

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

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

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

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

3 實驗

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

圖3 顯示了不同方法對10 個不同基準(zhǔn)測試的WeightedSpeedup 的影響。整體而言，與參考文獻[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)測試中表現(xiàn)的Weighted Speedup較于其他方法有明顯提升。TQDP 一開始對于線程進行了預(yù)處理，獲取了很多需要的參數(shù)信息，在之后的執(zhí)行過程中，大大減少了系統(tǒng)對于線程的處理過程。

與++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)測試表現(xiàn)出的Fairness 明顯優(yōu)于其他方法，如圖4 所示。正如之前介紹的，TQDP 對于長短線程都有考慮到，特別是對于長線程在執(zhí)行過程中長時間得不到響應(yīng)的情況，通過TQDP 算法，可以大大降低發(fā)生的概率，正是由于考慮到了長線程的調(diào)度情況，因此TQDP 的Fairness 參數(shù)表現(xiàn)結(jié)果好。

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

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

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

4結(jié)束語

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