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

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

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

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

control flow divergence

Memory帶寬優(yōu)化

Efficient utilization of memory bandwidth

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

Increasing parallelism and improving execution pipelining

增強(qiáng)GPGPU可編程性

Enhancing GPGPU programmability

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

CPU–GPU heterogeneous architecture

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

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

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

文中baseline即指默認(rèn)的GPGPU的配置。

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

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

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

這樣的缺點(diǎn)：

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

warp本應(yīng)執(zhí)行32個(gè)，這樣導(dǎo)致單元利用率不高

分支divergence可能進(jìn)一步導(dǎo)致memory divergence

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

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

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

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

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

Memory帶寬優(yōu)化

Two-level warp scheduling

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

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

Coarse-grained CTA throttling

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

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

Fine-grained warp throttling

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

Critical warp awareness

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

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

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

競(jìng)爭(zhēng)memory。執(zhí)行最慢的warp持續(xù)的刷LRU，導(dǎo)致這個(gè)warp占用了最多的cache

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

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

Cache management and bypassing

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

Ordering buffers

如果不同的warp以interleave的方式發(fā)送memory的請(qǐng)求，這樣memory footprint是所有warp整體的總和，如果能夠一個(gè)warp先執(zhí)行完，另一個(gè)warp再執(zhí)行，那么memory footprint只是一個(gè)warp的memory footprint。

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

Mitigating off-chip bandwidth bottleneck

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

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

Memory divergence normalization

baseline的prefetcher會(huì)根據(jù)當(dāng)前的warp對(duì)下一個(gè)warp的內(nèi)存進(jìn)行預(yù)取，但是這樣可能會(huì)late prefetch或者不準(zhǔn)確產(chǎn)生useless prefetch。 Orchestrated Scheduling and Prefetching for GPGPUs 論文比對(duì)了之前的TPRR，認(rèn)為使用當(dāng)前的fetch group預(yù)測(cè)下一個(gè)fetch group進(jìn)行預(yù)測(cè)是不準(zhǔn)確的，因?yàn)閺氖褂脀arp1-warp4的訪問(wèn)去預(yù)測(cè)warp5-warp8的訪問(wèn)可能不準(zhǔn)確，因此它細(xì)粒度的先執(zhí)行warp 1/3/5/7，使用產(chǎn)生的地址去預(yù)測(cè)warp2/4/6/8. 下圖中的D1-D7即為warp產(chǎn)生的訪問(wèn)內(nèi)存的請(qǐng)求，黃色和紅色的即為T(mén)PRR中不同的fetch group，在之前的TPRR fetch group中包含8個(gè)warp。

Main memory scheduling

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

CPU–GPU memory transfer overhead

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

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

總結(jié)

1.Control Divergence

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

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

因?yàn)镃UDA后面支持kernel執(zhí)行時(shí)自己產(chǎn)生新的kernel，但是產(chǎn)生新的kernel開(kāi)銷(xiāo)很大，所以可以減少開(kāi)銷(xiāo)。

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

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

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

可以?xún)?yōu)化cache，防止cache的抖動(dòng)，thrashing問(wèn)題。也可以bypass

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

對(duì)訪問(wèn)內(nèi)存的請(qǐng)求進(jìn)行ordering，減少memory footprint

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

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

審核編輯：黃飛