探究GPGPU體系結構優化策略

最近讀了 GPGPU Architectural Survey[1]，這篇survey很長，這里簡要的介紹內容，將我理解的方向和重點的論文介紹一下。

相關的論文我只介紹縮寫的名字，大致介紹文章的內容，具體的內容還是要看survey和原文。

GPGPU的優化方向主要包括以下五點：

控制分支分叉優化

control flow divergence

Memory帶寬優化

Efficient utilization of memory bandwidth

提高并行度和優化流水線

Increasing parallelism and improving execution pipelining

增強GPGPU可編程性

Enhancing GPGPU programmability

CPU GPU異構架構優化

CPU–GPU heterogeneous architecture

上圖為近幾年各個方向文章發表的比例

優化方向的前兩點在這篇文章中介紹，后三點將會在下一篇文章介紹。

文末附有總結，也可以直接拉到文末。

文中baseline即指默認的GPGPU的配置。

控制分支分叉優化

GPU Warp內，32個線程（NVIDIA）鎖步lock step執行時，如果遇到每個分支走上了不同分支，比如20個線程if，12個執行else，那么20個線程會先執行，mask調另外的12個。20個線程執行到分支合并點之后，另外12個再執行，直到這12個線程也進行到分支合并點。

如下圖左側所示。

這樣的缺點：

不同的分支順序執行

warp本應執行32個，這樣導致單元利用率不高

分支divergence可能進一步導致memory divergence

具體優化的子方向如下圖所示：

Dynamic Regrouping Divergent Warps即為不同warp的分支合并為新的warp。

Large Warp/CTA compaction中的Thread Block Compaction，將thread block 內的thread共享分支mask棧(baseline 每個warp單獨有自己的分支mask棧)。

Multi path execution即為if 和 else分支兩路同時執行。

Dynamickernels/threads比如在圖形應用中，可能會動態的創建kernel，在[3]中提出了在irregular benchmark中怎么減少創建的開銷.

Memory帶寬優化

Two-level warp scheduling

baseline將所有的warp按照輪詢的方式調度，但是如果程序是一致的，那么可能會所有的warp同時遇到cache miss的指令，導致很長的延遲。

TPRR(Two-Level Warp Scheduling)：如果將warp分成兩個level的warp。將32個warp組成了細粒度的4個fetch group，每個fetch group內部8個warp。直到一個fetch warp執行阻塞時，再執行另一組warp可以提高效率。

Coarse-grained CTA throttling

baseline將在一個GPU core上盡量執行最多的CTA以增加線程并行度。

但是這樣可能會導致大量的線程競爭memory，因此也有優化方案DYNCTA提出調度最佳而不是最多的CTA。

Fine-grained warp throttling

baseline將在一個warp內的memory優化。不同的warp之間可能也會競爭共享的資源，比如一個warp訪問的cache反復的被另一個warp競爭出去，即thrashing?？梢酝ㄟ^將被thrashing的 warp優先執行，進行優化，即為PCAL（Priority-based cache allocation in throughput processors）。

Critical warp awareness

baseline對各個warp無感，但是實際上warp中也會有critical warp，執行的最慢成為關鍵路徑，以下的情況可能會產生critical warp。

warp執行的workload比較重

warp執行了另外的控制分支

競爭memory。執行最慢的warp持續的刷LRU，導致這個warp占用了最多的cache

warp如果按照輪詢調度，那么N個warp ready了之后，需要等待N個周期才能再次被調度

CAWA(Coordinated Warp Scheduling and Cache Prioritization for Critical WarpAcceleration of GPGPU Workloads)通過識別critical warp，優先調度并且優先cache 分配到這些warp上，來加速執行。

Cache management and bypassing

baseline 的cache之間沒有配合。GCache(Adaptive Cache Bypass and Insertion for Many-core Accelerators)通過在L2 tag array中增加額外的標記來給L1 cache提供這個hot line在之前被evict出來，L1 Cache通過自適應的方法來鎖定這些hot cacheline，防止thrashing，cache抖動。

Ordering buffers

如果不同的warp以interleave的方式發送memory的請求，這樣memory footprint是所有warp整體的總和，如果能夠一個warp先執行完，另一個warp再執行，那么memory footprint只是一個warp的memory footprint。

比如下圖，將W3聚合在一起，可以減少footprint。即為ordering buffer, 詳見MRPB: Memory request prioritization for massively parallel processors。

Mitigating off-chip bandwidth bottleneck

LAMAR(local-aware memory hierarchy)注意到對于規范的GPGPU workload，每次memory 訪問，進行粗粒度的內存訪問可以利用空間局部性，也可以提高帶寬。但是對于不規則的workload，細粒度的內存訪問則更好，因此它對于不同的workload進行不同粒度的內存訪問。

CABA(Core-Assised Bottleneck Acceleartion)如果存在帶寬瓶頸，那么會使用空閑的計算單元，創建warp壓縮內存，以避免帶寬瓶頸。

Memory divergence normalization

baseline的prefetcher會根據當前的warp對下一個warp的內存進行預取，但是這樣可能會late prefetch或者不準確產生useless prefetch。 Orchestrated Scheduling and Prefetching for GPGPUs 論文比對了之前的TPRR，認為使用當前的fetch group預測下一個fetch group進行預測是不準確的，因為從使用warp1-warp4的訪問去預測warp5-warp8的訪問可能不準確，因此它細粒度的先執行warp 1/3/5/7，使用產生的地址去預測warp2/4/6/8. 下圖中的D1-D7即為warp產生的訪問內存的請求，黃色和紅色的即為TPRR中不同的fetch group，在之前的TPRR fetch group中包含8個warp。

Main memory scheduling

baseline的linux page placement主要處理CPU-only NUMA系統，致力于減少memory latency。但是GPU對bandwidth更加敏感，因此論文Page Placement Strategies for GPUswithin Heterogeneous Memory Systems通過平衡page placement來最大化memory bandwidth。

CPU–GPU memory transfer overhead

baseline的GPGPU啟動時，需要等待CPU將數據完全將內存拷貝到GPU內存，才能開始計算。

Reducing GPU Offload Latency via Fine-Grained CPU-GPU Synchronization通過增加full-empty bists,來追蹤已經傳輸完成的page。如果GPGPU計算所依賴的數據已經傳輸完畢，就可以直接執行。這樣可以overlap 執行和數據搬運的時間。

總結

1.Control Divergence

因為warp內可能存在不同的分支執行路徑，因此合并不同warp的相同分支，產生新的warp，也可以在整個CTA的范圍內合并warp。

也可以同時執行分支的不同路徑。

因為CUDA后面支持kernel執行時自己產生新的kernel，但是產生新的kernel開銷很大，所以可以減少開銷。

2. Memory 帶寬和利用率優化

不是簡單的輪詢調度warp，而是將其切割成fetch group。后面的優化方案又結合了fetch group和prefetch

可以在CTA的粒度上節流線程的執行，以減少memory競爭。同樣，也可以在warp的力度上進行節流，防止warp之間的競爭。

可以優化cache，防止cache的抖動，thrashing問題。也可以bypass

識別關鍵的warp，優先執行關鍵warp

對訪問內存的請求進行ordering，減少memory footprint

利用空閑的執行單元進行壓縮，避免bandwidth bottleneck

針對GPU memory系統設計bandwidth有限的page placement 策略

審核編輯：黃飛