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

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

GPGPU的優(yōu)化方向主要包括以下五點：

控制分支分叉優(yōu)化

control flow divergence

Memory帶寬優(yōu)化

Efficient utilization of memory bandwidth

提高并行度和優(yōu)化流水線

Increasing parallelism and improving execution pipelining

增強GPGPU可編程性

Enhancing GPGPU programmability

CPU GPU異構(gòu)架構(gòu)優(yōu)化

CPU–GPU heterogeneous architecture

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

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

文末附有總結(jié)，也可以直接拉到文末。

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

控制分支分叉優(yōu)化

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

如下圖左側(cè)所示。

這樣的缺點：

不同的分支順序執(zhí)行

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

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

具體優(yōu)化的子方向如下圖所示：

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

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

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

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

Memory帶寬優(yōu)化

Two-level warp scheduling

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

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

Coarse-grained CTA throttling

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

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

Fine-grained warp throttling

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

Critical warp awareness

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

warp執(zhí)行的workload比較重

warp執(zhí)行了另外的控制分支

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

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

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

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的方式發(fā)送memory的請求，這樣memory footprint是所有warp整體的總和，如果能夠一個warp先執(zhí)行完，另一個warp再執(zhí)行，那么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)注意到對于規(guī)范的GPGPU workload，每次memory 訪問，進行粗粒度的內(nèi)存訪問可以利用空間局部性，也可以提高帶寬。但是對于不規(guī)則的workload，細粒度的內(nèi)存訪問則更好，因此它對于不同的workload進行不同粒度的內(nèi)存訪問。

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

Memory divergence normalization

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

Main memory scheduling

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

CPU–GPU memory transfer overhead

baseline的GPGPU啟動時，需要等待CPU將數(shù)據(jù)完全將內(nèi)存拷貝到GPU內(nèi)存，才能開始計算。

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

總結(jié)

1.Control Divergence

因為warp內(nèi)可能存在不同的分支執(zhí)行路徑，因此合并不同warp的相同分支，產(chǎn)生新的warp，也可以在整個CTA的范圍內(nèi)合并warp。

也可以同時執(zhí)行分支的不同路徑。

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

2. Memory 帶寬和利用率優(yōu)化

不是簡單的輪詢調(diào)度warp，而是將其切割成fetch group。后面的優(yōu)化方案又結(jié)合了fetch group和prefetch

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

可以優(yōu)化cache，防止cache的抖動，thrashing問題。也可以bypass

識別關(guān)鍵的warp，優(yōu)先執(zhí)行關(guān)鍵warp

對訪問內(nèi)存的請求進行ordering，減少memory footprint

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

針對GPU memory系統(tǒng)設(shè)計bandwidth有限的page placement 策略

審核編輯：黃飛