3.3.1 SIMT堆棧

SIMT堆棧用于在Warp前處理SIMT架構(gòu)的分支分化的執(zhí)行。一般采用后支配堆棧重收斂機(jī)制來(lái)減少分支分化對(duì)計(jì)算效率的負(fù)面影響。

SIMT 堆棧的條目代表不同的分化級(jí)別，每個(gè)條目存儲(chǔ)新分支的目標(biāo) PC、后繼的直接主要再收斂 PC 和分布到該分支的線程的活動(dòng)掩碼。在每個(gè)新的分化分支，一個(gè)新條目被推到棧頂；而當(dāng) Warp 到達(dá)其再收斂點(diǎn)時(shí)，棧頂條目則被彈出。每個(gè) Warp 的 SIMT 堆棧在該 Warp 的每個(gè)指令發(fā)出后更新。

線程束分化

從功能角度來(lái)看，雖然SIMT架構(gòu)下每個(gè)線程獨(dú)立執(zhí)行，但在實(shí)際的計(jì)算過(guò)程中會(huì)遇到一些分支的處理，即有些線程執(zhí)行一個(gè)分支，而另外的線程則執(zhí)行其他分支。如果在同一個(gè)Warp內(nèi)不同的線程執(zhí)行不同的分支，就會(huì)造成線程束分化，導(dǎo)致后繼SIMD計(jì)算的效率降低。因此應(yīng)盡量避免線程束的分化。

圖 3-6 線程束分化與重聚合

SIMT堆棧功能

SIMT堆棧模塊可有效改善線程束分化引起的GPGPU執(zhí)行單元利用率下降的問(wèn)題。

SIMT堆棧重點(diǎn)解決：

控制流嵌套問(wèn)題（Nested Control Flow）

在控制流嵌套中，一個(gè)分支嚴(yán)重地依賴另一個(gè)分支，這極大影響了線程的獨(dú)立性。

如何跳過(guò)計(jì)算過(guò)程（Skip Computation）

由于線程束分支的存在，導(dǎo)致同一個(gè)Warp內(nèi)的有些線程并不必要執(zhí)行某些計(jì)算指令。

3. SIMT掩碼

SIMT堆棧中使用了SIMT掩碼（SIMT Mask）來(lái)處理線程束分化問(wèn)題，以下例來(lái)說(shuō)明掩碼如何控制整個(gè)Warp的執(zhí)行。

4. SIMT 掩碼引起的死鎖問(wèn)題

SIMT 掩碼可以解決Warp內(nèi)分支執(zhí)行問(wèn)題，通過(guò)串行執(zhí)行完畢分支之后，線程在Reconverge Point（重合點(diǎn)）又重新聚合在一起以便最大提高其并行能力。

但對(duì)于一個(gè)程序來(lái)說(shuō)，如果出現(xiàn)分支就表明每個(gè)分支的指令和處理是不一致的，容易使一些共享數(shù)據(jù)失去一致性。如果在同一個(gè)Warp內(nèi)如果存在分支，則線程之間可能不能夠交互或者進(jìn)行數(shù)據(jù)交換，在一些實(shí)際算法中可能使用鎖定（Lock）機(jī)制來(lái)進(jìn)行數(shù)據(jù)交換。但掩碼恰恰可能因?yàn)檎{(diào)度失衡，造成鎖定一直不能被解除，造成死鎖問(wèn)題。

5. GPGPU解決死鎖的方法

圖 3-8 V100 Warp調(diào)度對(duì)比圖[2]

解決死鎖的方法如下：

NVIDIA為V100 中Warp內(nèi)的每個(gè)線程都分配了一個(gè)PC指針和堆棧，將PC指針的顆粒度細(xì)化到每一個(gè)線程中去，保障數(shù)據(jù)交換避免死鎖。（圖3-5）

為避免細(xì)粒度的PC指針和堆棧與GPU的SIMT執(zhí)行模型產(chǎn)生沖突，硬件仍以Warp為單位來(lái)進(jìn)行線程調(diào)度。

使用了Schedule Optimizer（調(diào)度優(yōu)化器）硬件模塊來(lái)決定哪些線程可以在一個(gè)Warp內(nèi)進(jìn)行調(diào)度，將相同的指令重新進(jìn)行組織排布到一個(gè)Warp內(nèi)，并執(zhí)行SIMD模型，以保證利用效率最大化[2]。

3.3.2 線程束調(diào)度與記分牌

進(jìn)行線程束（Warp）調(diào)度的目的是充分利用內(nèi)存等待時(shí)間，選擇合適的線程束來(lái)發(fā)射，提升執(zhí)行單元計(jì)算效率。

在理想的計(jì)算情況下，GPU內(nèi)每個(gè)Warp內(nèi)的線程訪問(wèn)內(nèi)存延遲都相等，那么可以通過(guò)在Warp內(nèi)不斷切換線程來(lái)隱藏內(nèi)存訪問(wèn)的延遲。

GPU將不同類型的指令分配給不同的單元執(zhí)行，LD/ST硬件單元用于讀取內(nèi)存，而執(zhí)行計(jì)算指令可能使用INT32或者FP32硬件單元，且不同硬件單元的執(zhí)行周期數(shù)一般不同。這樣，在同一個(gè)Warp內(nèi)，執(zhí)行的內(nèi)存讀取指令可以采用異步執(zhí)行的方式，即在讀取內(nèi)存等待期間，下一刻切換線程其他指令做并行執(zhí)行，使得GPU可以一邊進(jìn)行讀取內(nèi)存指令，一邊執(zhí)行計(jì)算指令動(dòng)作，通過(guò)循環(huán)調(diào)用（Round Robin）隱藏內(nèi)存延遲問(wèn)題，提升計(jì)算效率。

在理想狀態(tài)下，可以通過(guò)這種循環(huán)調(diào)用方式完全隱藏掉內(nèi)存延遲。但在實(shí)際計(jì)算流程中，內(nèi)存延遲還取決于內(nèi)核訪問(wèn)的內(nèi)存位置，以及每個(gè)線程對(duì)內(nèi)存的訪問(wèn)數(shù)量。

內(nèi)存延遲問(wèn)題影響著Warp調(diào)度，需要通過(guò)合理的Warp調(diào)度來(lái)隱藏掉內(nèi)存延遲問(wèn)題。

1. 指令順序調(diào)整的原因

在同一個(gè)Warp的單個(gè)線程中，調(diào)整發(fā)送到ALU將要執(zhí)行的指令順序，可以隱藏掉一部分內(nèi)存延遲問(wèn)題。例如讀取指令和加法指令使用的是不同的硬件單元，在第一個(gè)時(shí)鐘周期執(zhí)行內(nèi)存讀取指令之后，下一個(gè)時(shí)鐘周期不必等待讀取內(nèi)存指令，而是可以直接執(zhí)行加法指令，從而實(shí)現(xiàn)一邊計(jì)算一邊讀取，來(lái)提高整個(gè)運(yùn)行效率。

但在實(shí)際情況中，后一個(gè)指令有可能是依賴于前一個(gè)指令的讀取結(jié)果。要解決該問(wèn)題就需要GPU提前對(duì)指令之間的依賴關(guān)系進(jìn)行預(yù)測(cè)，解析出指令之間的獨(dú)立性和依賴關(guān)系。

圖 3-11動(dòng)態(tài)線程束示例（來(lái)源：WILSON W. L. FUNG等）

2. 記分牌與指令順序調(diào)整的方法

GPU在這里參考了CPU設(shè)計(jì)，為了解析指令之間的獨(dú)立性，采用順序記分牌（In-Order Scoreboard）。

對(duì)于單線程束情況，

1. 每個(gè)寄存器在記分牌中都對(duì)應(yīng)一個(gè)標(biāo)志位，用于表示該寄存器是否已被寫入數(shù)據(jù)，如果置1則表示該寄存器已經(jīng)被寫入。
2. 此時(shí)如果另外一個(gè)指令想要讀或者寫該寄存器，則會(huì)處于一直等待狀態(tài)，一直到該寄存器的標(biāo)志位被清零（表明之前寫寄存器操作完成）。這樣就可以阻止Read-After-Write和Write-After-Write的問(wèn)題。
3. 當(dāng)順序記分牌和順序指令（In-Order Instruction）結(jié)合時(shí)，能避免Write-After-Read的問(wèn)題。

圖 3-11數(shù)據(jù)沖突與流水線結(jié)構(gòu)相關(guān)

對(duì)于多線程束情況，將上述方法應(yīng)用到GPU時(shí)，還需要解決兩個(gè)問(wèn)題：

1. 由于有大量寄存器GPU，在每組寄存器中增加一個(gè)標(biāo)志位將需要占用更多額外的寄存器。
2. 在GPU中，一般會(huì)有很多個(gè)線程同時(shí)執(zhí)行同一指令，一旦其執(zhí)行的指令被打斷，會(huì)有很多線程同時(shí)訪問(wèn)Scoreboard造成讀取阻塞。

對(duì)于多線程束情況，可通過(guò)動(dòng)態(tài)記分牌解決上面的兩個(gè)問(wèn)題：

圖 3-9 記分牌Entry流程

1. 為每個(gè)Warp創(chuàng)建幾個(gè)入口（Entry），每個(gè)入口與一個(gè)即將被寫但操作尚未完成的寄存器相對(duì)應(yīng)。記分牌在指令進(jìn)入指令緩沖區(qū)（Instruction buffer，I-Buffer）和寫操作完成結(jié)果存入Register File時(shí)能被訪問(wèn)（圖3-6）
2. 當(dāng)一個(gè)指令從內(nèi)存中讀取出來(lái)放入到I-Buffer時(shí)，將該指令中的源寄存器和目的寄存器與Entry做比較，看是否有其他指令集已經(jīng)對(duì)該寄存器在做寫操作，如果有則返回一個(gè)bit Vector，與該寄存器一起寫入到I-Buffer中。如果該指令集的寫操作完成了，將會(huì)刷新I-Buffer中的該指令集寄存器的bit Vector，將bit Vector清除掉。
3. 如果一個(gè)指令做寫操作，并需要將該寄存器放入Entry中，但是此Entry已經(jīng)滿了，那么該指令將會(huì)一直等待，或者被丟棄過(guò)一定時(shí)鐘周期后被重新獲取再次查看Entry是否滿[3]。