3.3.1 SIMT堆棧

SIMT堆棧用于在Warp前處理SIMT架構的分支分化的執行。一般采用后支配堆棧重收斂機制來減少分支分化對計算效率的負面影響。

SIMT 堆棧的條目代表不同的分化級別，每個條目存儲新分支的目標 PC、后繼的直接主要再收斂 PC 和分布到該分支的線程的活動掩碼。在每個新的分化分支，一個新條目被推到棧頂；而當 Warp 到達其再收斂點時，棧頂條目則被彈出。每個 Warp 的 SIMT 堆棧在該 Warp 的每個指令發出后更新。

線程束分化

從功能角度來看，雖然SIMT架構下每個線程獨立執行，但在實際的計算過程中會遇到一些分支的處理，即有些線程執行一個分支，而另外的線程則執行其他分支。如果在同一個Warp內不同的線程執行不同的分支，就會造成線程束分化，導致后繼SIMD計算的效率降低。因此應盡量避免線程束的分化。

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

SIMT堆棧功能

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

SIMT堆棧重點解決：

控制流嵌套問題（Nested Control Flow）

在控制流嵌套中，一個分支嚴重地依賴另一個分支，這極大影響了線程的獨立性。

如何跳過計算過程（Skip Computation）

由于線程束分支的存在，導致同一個Warp內的有些線程并不必要執行某些計算指令。

3. SIMT掩碼

SIMT堆棧中使用了SIMT掩碼（SIMT Mask）來處理線程束分化問題，以下例來說明掩碼如何控制整個Warp的執行。

4. SIMT 掩碼引起的死鎖問題

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

但對于一個程序來說，如果出現分支就表明每個分支的指令和處理是不一致的，容易使一些共享數據失去一致性。如果在同一個Warp內如果存在分支，則線程之間可能不能夠交互或者進行數據交換，在一些實際算法中可能使用鎖定（Lock）機制來進行數據交換。但掩碼恰恰可能因為調度失衡，造成鎖定一直不能被解除，造成死鎖問題。

5. GPGPU解決死鎖的方法

圖 3-8 V100 Warp調度對比圖[2]

解決死鎖的方法如下：

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

為避免細粒度的PC指針和堆棧與GPU的SIMT執行模型產生沖突，硬件仍以Warp為單位來進行線程調度。

使用了Schedule Optimizer（調度優化器）硬件模塊來決定哪些線程可以在一個Warp內進行調度，將相同的指令重新進行組織排布到一個Warp內，并執行SIMD模型，以保證利用效率最大化[2]。

3.3.2 線程束調度與記分牌

進行線程束（Warp）調度的目的是充分利用內存等待時間，選擇合適的線程束來發射，提升執行單元計算效率。

在理想的計算情況下，GPU內每個Warp內的線程訪問內存延遲都相等，那么可以通過在Warp內不斷切換線程來隱藏內存訪問的延遲。

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

在理想狀態下，可以通過這種循環調用方式完全隱藏掉內存延遲。但在實際計算流程中，內存延遲還取決于內核訪問的內存位置，以及每個線程對內存的訪問數量。

內存延遲問題影響著Warp調度，需要通過合理的Warp調度來隱藏掉內存延遲問題。

1. 指令順序調整的原因

在同一個Warp的單個線程中，調整發送到ALU將要執行的指令順序，可以隱藏掉一部分內存延遲問題。例如讀取指令和加法指令使用的是不同的硬件單元，在第一個時鐘周期執行內存讀取指令之后，下一個時鐘周期不必等待讀取內存指令，而是可以直接執行加法指令，從而實現一邊計算一邊讀取，來提高整個運行效率。

但在實際情況中，后一個指令有可能是依賴于前一個指令的讀取結果。要解決該問題就需要GPU提前對指令之間的依賴關系進行預測，解析出指令之間的獨立性和依賴關系。

圖 3-11動態線程束示例（來源：WILSON W. L. FUNG等）

2. 記分牌與指令順序調整的方法

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

對于單線程束情況，

1. 每個寄存器在記分牌中都對應一個標志位，用于表示該寄存器是否已被寫入數據，如果置1則表示該寄存器已經被寫入。
2. 此時如果另外一個指令想要讀或者寫該寄存器，則會處于一直等待狀態，一直到該寄存器的標志位被清零（表明之前寫寄存器操作完成）。這樣就可以阻止Read-After-Write和Write-After-Write的問題。
3. 當順序記分牌和順序指令（In-Order Instruction）結合時，能避免Write-After-Read的問題。

圖 3-11數據沖突與流水線結構相關

對于多線程束情況，將上述方法應用到GPU時，還需要解決兩個問題：

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

對于多線程束情況，可通過動態記分牌解決上面的兩個問題：

圖 3-9 記分牌Entry流程

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