基于線程隊列動態規劃法的GPU性能優化

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

關鍵詞：線程隊列;線程動態規劃;加速比;線程調度;并行計算

0 引言

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

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

為了更好地提升性能，利用GPU 的資源，本文提出了線程隊列動態規劃法TQDP，從線程角度出發，通過提高線程的執行次數和提升系統吞吐量，從而提高系統性能。

1 GPU

新一代GPU 體系架構集成的計算資源越來越多，同時由于GPU 缺乏適當的體系架構來支持共享，需要軟件、硬件或者軟硬件協同的方法來使用計算資源，因其復雜性導致GPU資源利用不足，影響整體性能。

1.1 GPU體系架構

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

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

1.2 線程調度算法

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

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

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

2 TQDP

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

2.1 TDQP

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

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

2.2 TQDP算法模型

TQDP 方法中， 為所有線程執行時間之和， 為線程的到達時間（提交時間）， 為線程的服務時間（執行時間）， 為線程的周轉時間， 為線程的等待時間。線程個數為， 為當前系統時間。用三參數法，表示為，在一個GPU 中多個SM 上，到達時間各不相同的線程，獲取總的最小執行時間，即：

2.3 TQDP的實現

TQDP的具體方案為：

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

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

③如果執行時間數組中對應線程出現相同數值，則在等待時間數組中尋找對應線程的等待時間，比較2 個線程的等待時間，并將等待時間較長的線程優先級提高。

④按照更新的執行隊列中的線程順序，系統執行kernel。

3 實驗

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

圖3 顯示了不同方法對10 個不同基準測試的WeightedSpeedup 的影響。整體而言，與參考文獻[9] 中的方法++DynCTAT，Mod+Bypass，PBS，BF，opt相比，本文所提出的方法TQDP 明顯優于其他方法。就平均結果，++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 等基準測試中表現的Weighted Speedup較于其他方法有明顯提升。TQDP 一開始對于線程進行了預處理，獲取了很多需要的參數信息，在之后的執行過程中，大大減少了系統對于線程的處理過程。

與++DynCTAT、Mod+Bypass，PBS，BF，opt 相比，本文所提出的方法TQDP 在BFS2_FFT，FFT_TRD，FWT_TRD，JPEG_CFD，JPEG_LIB等基準測試表現出的Fairness 明顯優于其他方法，如圖4 所示。正如之前介紹的，TQDP 對于長短線程都有考慮到，特別是對于長線程在執行過程中長時間得不到響應的情況，通過TQDP 算法，可以大大降低發生的概率，正是由于考慮到了長線程的調度情況，因此TQDP 的Fairness 參數表現結果好。

由于基準測試程序集數量過多，本文將所用的基準測試分為了2 類：計算密集型和內存密集型，分別表示為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都有明顯的改進，目的就是通過提升系統吞吐量來提高系統性能，從實驗結果來說，這一目的是達到了。TQDP 算法本身是從提高線程執行數、提升系統吞吐量的角度對隊列中線程執行順序進行優化。

ANTT平均標準化周轉時間越低越好，意味著響應時間更接近于獨立執行。吞吐量STP很好，那么ANTT 也應該很好。正如之前所說，對于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方面也很弱。結合之前的實驗結果，圖5中TQDP表現的結果優于其他2種方法，因此在圖6中，TQDP 的實驗結果也優于其他方法，符合預期。

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

4結束語

本文證明了提出的方法TQDP 確實可以優化系統性能。在測試的大部分基準測試中，TQDP 表現優秀，實驗結果表現基本與預期一致，實驗目的基本實現，從線程角度出發，通過優化線程執行隊列的執行順序，提高線程的執行次數，縮減程序執行時間，提升系統性能。就測試的相關參數平均而言，TQDP 相比其他方法都得到了很大的提升，但仍有不足之處，比如算法中對于算子數值的設置，簡單考慮了算子的取值范圍，粗略設定了數值，并沒有深入研究設置不同數值對于算法的影響，以及不同程度大小算子對于線程執行隊列的優化效果如何。在之后的工作中，將會從這一方面進行考慮，對算子的數值進行優化，探究算子的不同取值對于本算法優化效果影響。