收斂性與一致性¶
簡介¶
在某些環境中，執行緒組會並行執行相同的程式，其中組內的有效通訊是使用稱為 收斂操作 的特殊基元來建立的。收斂操作的結果會受到參與其中的執行緒集的影響。
收斂性 的直觀概念是圍繞著以「鎖步」執行的執行緒建立的 — 如果一組執行緒都「一起執行相同的指令序列」，則認為它們是 收斂的。這些執行緒可能會在 發散分支 處 發散，並且稍後可能會在某個共同的程式點 重新收斂。
在這種直觀概念中，當收斂的執行緒執行指令時，如果結果值在這些執行緒中相同，則稱該值是 一致的，否則稱為 發散的。相應地，如果分支的條件是一致的，則稱該分支是一致分支，否則稱為發散分支。
但是，鎖步執行的假設對於描述收斂操作時的通訊並不是必要的。它還通過過度指定執行緒在這種並行環境中的執行方式來限制實作（編譯器和硬體）。為了消除這種假設
我們將收斂性定義為不同執行緒執行每條指令之間的關係，而不是執行緒本身之間的關係。這個定義對於已知的目標是合理的，並且與 LLVM IR 中 收斂操作 的語義相容。
我們還根據這種收斂性來定義一致性。只有當指令的對應執行是收斂的，才能檢查多個執行緒中指令輸出的 一致性。
本文檔描述了一種靜態分析方法，用於確定函數中每條指令的收斂性。該分析方法擴展了先前關於發散分析的研究成果 [DivergenceSPMD]，以涵蓋不可化簡的控制流程。LLVM 中使用了所描述的分析方法來實作一致性分析，該分析確定 LLVM IR 或 MIR 函數中每條指令計算出的值的 一致性。
Julian Rosemann、Simon Moll 和 Sebastian Hack。2021。針對可化簡控制流程圖的 SPMD 發散的抽象解釋。Proc. ACM Program. Lang. 5, POPL, Article 31 (2021 年 1 月), 35 頁。 https://doi.org/10.1145/3434312
動機¶
發散分支會限制程式轉換，例如變更 CFG 或將聚合操作移至 CFG 的不同點。跨發散分支執行這些轉換可能會改變聚合執行聚合操作的執行緒集。雖然這些限制不在本文檔的討論範圍內，但一致性分析允許這些轉換識別這些限制不適用的均勻分支。
在以共享執行資源（例如 waves、warps 或 subgroups）的群組執行執行緒的目標上，一致性本身也很有用。
一致性輸出可能可以在共享資源上計算或儲存。
這些目標必須「線性化」發散分支，以確保分支的每一側都由同一群組中的相應執行緒遵循。但在均勻分支處不需要線性化，因為整個執行緒群組遵循分支的一側或另一側。
術語¶
執行緒和動態實例¶
程式原始碼中每次出現的指令稱為*靜態實例*。當執行緒執行程式時，每次執行靜態實例都會產生該指令的不同*動態實例*。
每個執行緒都會產生唯一的動態實例序列。
該序列是沿著分支決策和循環遍歷生成的。
從「第一個」指令的動態實例開始。
繼續執行後續「下一個」指令的動態實例。
執行緒是獨立的；某些目標可能會選擇以群組方式執行它們，以便在可能的情況下共享資源。
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||
執行緒 1 |
Entry1 |
H1 |
B1 |
L1 |
H3 |
L3 |
Exit |
||||
執行緒 2 |
Entry1 |
H2 |
L2 |
H4 |
B2 |
L4 |
H5 |
B3 |
L5 |
Exit |
在上表中，每一行都是一個不同的執行緒，從左到右列出該執行緒產生的動態實例。每個執行緒都執行相同的程式，從 Entry 節點開始，到 Exit 節點結束，但不同的執行緒可能會採用不同的路徑通過程式的控制流程。列出的動態實例在同一欄中表示已聚合。
聚合¶
*聚合前*是動態實例上的嚴格偏序關係，定義為以下關係的遞移閉包：
如果動態實例
P在同一個執行緒中嚴格地在Q之前執行，則P*聚合前*Q。如果動態執行個體
P在同一個執行緒中嚴格地在Q1之前執行，且Q1與Q2收斂相關，則P在Q2收斂之前。如果動態執行個體
P1與P2收斂相關，且P2在同一個執行緒中嚴格地在Q之前執行，則P1在Q收斂之前。
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
執行緒 1 |
項目 |
… |
S2 |
T |
… |
Exit |
|||
執行緒 2 |
項目 |
… |
Q2 |
R |
S1 |
… |
Exit |
||
執行緒 3 |
項目 |
… |
P |
Q1 |
… |
上表顯示了來自不同執行緒的動態執行個體的部分序列。假設同一欄中的動態執行個體是收斂的（即，在收斂相關關係中彼此相關）。產生的收斂順序包括邊 P -> Q2、Q1 -> R、P -> R、P -> T 等等。
收斂相關 是由 不同執行緒 為 相同靜態執行個體 生成的動態執行個體上的遞移對稱關係。
為 收斂相關 關係提供任何一個定義是不切實際的，因為不同的環境可能希望以不同的方式關聯動態執行個體。收斂之前 是嚴格偏序這一事實是對 收斂相關 關係的約束。如果不同的動態執行個體從不收斂，則可以輕鬆滿足此條件。在下文中，我們提供了一個稱為 最大收斂相關 的關係，它滿足 收斂之前 並且適用於已知目標。
備註
收斂之前關係不能直接觀察到。程式轉換通常可以自由地更改指令的順序，即使這顯然會更改收斂之前關係。
收斂的動態執行個體不需要同時執行，甚至不需要在同一個資源上執行。收斂操作的收斂動態執行個體可能會出現這種情況，但這是一個實現細節。
P在Q收斂之前這一事實並不自動意味著P在記憶體模型意義上發生在Q之前。
最大收斂¶
本節定義了一個約束，可用於在不違反嚴格 收斂之前 順序的情況下產生 最大收斂相關 關係。這種最大收斂相關關係對於真實目標是合理的，並且與收斂操作相容。
最大收斂關係是根據循環標頭定義的，並假設執行緒在每個循環「迭代」時都會在標頭處收斂。非正式地說，如果兩個執行緒在進入循環後都執行了相同次數的循環標頭，則它們會執行循環的相同迭代。一般來說，這也需要考慮父循環的迭代。
最大收斂
如果且僅當滿足以下條件時，由不同執行緒針對同一個靜態實例
X生成的動態實例X1和X2在最大收斂關係中收斂：
X未包含在任何循環中，或者對於每個包含
X且標頭為H的循環C
在各自的執行緒中，
H的每個先於X1的動態實例H1都收斂於X2之前，並且在各自的執行緒中，
H的每個先於X2的動態實例H2都收斂於X1之前不假設
X1與X2收斂。
備註
如果 CFG 不可約，則循環標頭在給定的 CFG 中可能不是唯一的。相同 CFG 的每個循環階層都會產生不同的最大收斂關係。
為簡潔起見，本文檔的其餘部分將術語「收斂」限制為表示「在給定循環階層的最大收斂關係下相關」。
現在，可以在前面的範例中證明最大收斂，如下所示
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||
執行緒 1 |
Entry1 |
H1 |
B1 |
L1 |
H3 |
L3 |
Exit |
||||
執行緒 2 |
Entry2 |
H2 |
L2 |
H4 |
B2 |
L4 |
H5 |
B3 |
L5 |
Exit |
Entry1和Entry2已收斂。H1和H2已收斂。B1和B2未收斂，因為H4不收斂於B1之前。H3和H4已收斂。H3未與H5收斂，因為H4不收斂於H3之前。L1和L2已收斂。L3和L4已收斂。L3未與L5收斂，因為H5不收斂於L3之前。
循環標頭的依賴關係¶
僅當兩個節點位於某個循環內時，才有可能在 convergence-before 中出現矛盾。這些節點的動態實例可能會在同一個線程中交錯出現，並且這種交錯方式在不同的線程中可能有所不同。
當一個線程執行一次節點 X 然後再次執行它時，它一定遵循了 CFG 中包含 X 的封閉路徑。這樣的路徑必須至少通過一個循環的標頭——包含整個封閉路徑的最小循環。在給定的線程中，X 的兩個動態實例要麼由至少一個循環標頭的執行分隔，要麼 X 本身就是一個循環標頭。
在可簡化循環（自然循環）中，標頭的每次執行都等效於循環的新迭代的開始。但是，在存在對 converged-with 關係的顯式約束的情況下，這種類比就會失效，例如 未來工作 中描述的那些約束。相反，循環標頭應被視為最大 converged-with 關係中的隱式 收斂點。
考慮一系列嵌套循環 C1、C2、…、Ck，其中 C1 是最外層循環，Ck 是最內層循環，其標頭分別為 H1、H2、…、Hk。當一個線程進入循環 Ck 時，可能會發生以下任何一種情況：
線程直接進入循環
Ck，而沒有執行任何標頭H1到Hk。線程執行了一些或所有嵌套標頭一次或多次。
最大 converged-with 關係捕獲了關於循環的以下直覺：
當兩個線程進入頂級循環
C1時，它們會執行C1的每個 子 節點的收斂動態實例。當兩個線程進入嵌套循環
Ck時，它們會執行Ck的每個子節點的收斂動態實例，直到任何一個線程退出Ck，前提是它們執行了任一線程遇到的最後一個嵌套標頭的收斂動態實例。請注意，當一個線程退出嵌套循環
Ck時，它必須遵循Ck之外的封閉路徑才能重新進入它。這需要執行某個外部循環的標頭，如前所述。
考慮由執行緒 T1 和 T2 生成的兩個動態實例 X1 和 X2，用於嵌套循環 Ck 的子節點 X。最大收斂關係將 X1 和 X2 關聯如下：
如果兩個執行緒都沒有執行從
H1到Hk的任何標頭，則X1和X2會收斂。否則，如果從
H1到Hk的任何標頭Q（其中Q可能與X相同）沒有收斂的動態實例Q1和Q2，使得Q1在各自的執行緒中位於X1之前，而Q2位於X2之前，則X1和X2不會收斂。否則，請考慮從
H1到Hk的標頭Q的一對收斂動態實例Q1和Q2，它們在各自執行緒中分別出現在X1和X2之前最近的位置。然後，當且僅當在執行緒T1中Q1和X1之間，或在執行緒T2中Q2和X2之間沒有出現從H1到Hk的任何標頭的動態實例時，X1和X2才會收斂。換句話說，Q1和Q2代表最後的收斂點，在執行X之前沒有執行其他標頭。
範例
上圖顯示了兩個嵌套的不可約循環，標頭分別為 R 和 S。節點 Entry 和 Q 具有發散分支。下表顯示了通過 CFG 採用不同路徑的三個執行緒之間的收斂性。列在同一欄中的動態實例已收斂。
1
2
3
4
5
6
7
8
10
執行緒 1
項目
P1
Q1
S1
P3
Q3
R1
S2
Exit
執行緒 2
項目
P2
Q2
R2
S3
Exit
執行緒 3
項目
R3
S4
Exit
由於
S1的緣故，P2和P3沒有收斂。Q2和Q3由於S1而未收斂S1和S3由於R2而未收斂S1和S4由於R3而未收斂
非正式地說，T1 和 T2 執行內部循環的次數不同，而沒有執行外部循環的標頭。所有線程在第一次執行外部循環的標頭時，會在外部循環中收斂。
一致性¶
如果兩個收斂的動態實例的輸出對這兩個動態實例進行比較時相等，則它們是一致的。
如果靜態實例
X的輸出對於那些線程產生的每一對收斂的動態實例X都是一致的，則該輸出對於*給定的一組線程*來說是一致的。
非一致的值稱為*發散的*。
對於一組線程 S，靜態實例的每個輸出一致性確定如下
指令的語義可以指定輸出為一致的。
否則，如果靜態實例不是 m-收斂的，則輸出是發散的。
否則，如果靜態實例是 m-收斂的
如果它是一個 PHI 節點，則當且僅當對於
S中所有線程產生的每一對收斂的動態實例，它的輸出是一致的兩個實例都從收斂的動態實例中選擇相同的輸出，並且
該輸出對於
S中的所有線程都是一致的。
否則，當且僅當輸入運算元對於
S中的所有線程都是一致的時，輸出才是一致的。
發散循環出口¶
當循環內發生發散分支時，發散路徑可能會繼續到循環的出口。這稱為發散循環出口。如果循環是不可約的，則發散路徑可能會重新進入並最終到達循環內的聯接點。應檢查此類聯接點是否符合 發散入口 標準。
當兩個線程在循環內一致地執行並產生一致的值，但在執行標頭不同次數（非正式地說，在循環的不同迭代中）後沿著相同的發散路徑退出循環時，位於循環外部的發散路徑上的節點會經歷*時間發散*。對於循環內的節點 N，兩個線程的輸出可能是一致的，但循環外的任何使用 U 都會從 N 的非收斂動態實例接收值。 U 的輸出可能是發散的，具體取決於指令的語義。
靜態一致性分析¶
不可簡化的控制流程會根據在深度優先遍歷期間標頭的選擇，產生不同的循環層次結構。 因此，靜態分析無法始終確定不可簡化循環中節點的收斂性，並且任何一致性分析都僅限於那些收斂性與循環層次結構無關的靜態實例。
m 收斂靜態實例
當且僅當在其動態實例的最大收斂關係在可以為該 CFG 構造的每個循環層次結構中都相同時，靜態實例
X對於給定的 CFG 才是 *m 收斂* 的。備註
換句話說，如果 m 收斂靜態實例
X的兩個動態實例X1和X2在某個循環層次結構中收斂，則當且僅當它們在相同 CFG 的每個其他循環層次結構中也收斂。如前所述，為簡潔起見，我們將術語 *收斂* 限制為表示「在給定循環層次結構的最大收斂關係下相關」。
當且僅當包含 X 的每個循環都滿足以下必要條件時，才會報告給定 CFG 中的每個節點 X 為 m 收斂的：
備註
可簡化循環 顯然滿足 上述條件。 特別是，如果整個 CFG 是可簡化的，則 CFG 中的所有節點都是 m 收斂的。
使用 前面描述的 準則確定靜態實例的每個輸出的均勻性。 發散輸出的發現可能會導致它們的使用（包括分支）也變得發散。 分析會傳播這種發散，直到達到固定點。
使用這些準則推斷的收斂性是任何循環層次結構的最大收斂關係的安全子集。 特別是，它足以確定靜態實例對於給定的循環層次結構 T 是否為 m 收斂的，即使在檢查某些其他循環層次結構 T' 時沒有檢測到該事實。
此屬性允許編譯器轉換使用一致性分析，而不受基礎循環分析中做出的 DFS 選擇的影響。 當兩個轉換對同一個 CFG 使用不同的一致性分析實例時，一個分析實例中的「發散值」結果不能與另一個分析實例中的「一致值」結果相矛盾。
諸如 SimplifyCFG、CSE 和循環轉換之類的通用轉換通常會以改變最大收斂關係的方式改變程序。 這也意味著先前一致的值在這樣的轉換後可能會變得發散。 在進行此類轉換後，必須重新計算一致性。
循環內的發散分支¶
上圖顯示了不可簡化循環區域內的發散分支 Q。 當兩個線程在 Q 處發散時，循環區域內動態實例的收斂性取決於所選的循環層次結構。
在偵測到單一迴圈
C且其標頭為P的實現中，迴圈內部的收斂是由P決定的。在偵測到兩個巢狀迴圈，其標頭分別為
R和S的實現中，這些迴圈內部的收斂是由它們各自的標頭決定的。
一種保守的做法是簡單地將不可約迴圈內的所有節點都報告為具有發散輸出。但是，為了最大限度地提高一致性，希望能夠識別 CFG 中的 m-收斂節點。本節描述了一種從「閉合路徑」衍生而來的節點模式，它是 CFG 的屬性，不依賴於迴圈層次結構。
發散進入準則
閉合路徑
P中所有節點的動態實例僅在以下情況下才是 m-收斂的：對於位於P上的每個發散分支B及其連接節點J，不存在位於從B到J的發散路徑上的P的進入點。
考慮上圖中的閉合路徑 P -> Q -> R -> S。 P 和 R 是閉合路徑的進入點。 Q 是一個發散分支，S 是該分支的連接點，具有發散路徑 Q -> R -> S 和 Q -> S。
如果存在發散進入點
R，則在某些迴圈層次結構中，R是包含閉合路徑的最小迴圈C的標頭，並且在集合C - R中存在子迴圈C'，其中包含分支Q和連接點S。當線程在Q處發散時，一個子集M繼續在迴圈C'內部，而其補集N退出C'並到達R。由於R的存在，由集合M中的線程執行的S的動態實例與由集合N中的線程執行的實例不收斂。非正式地說，在Q處發散的線程在外部迴圈C的同一迭代中重新收斂，但它們可能以不同的方式執行了內部迴圈C'。1
2
3
4
5
6
7
8
9
10
11
執行緒 1
項目
P1
Q1
R1
S1
P3
…
Exit
執行緒 2
項目
P2
Q2
S2
P4
Q4
R2
S4
Exit
在上方的表格中，由於
R1的存在，S2未與S1收斂。
如果
R不存在，或者如果C的標頭是除了R以外的任何節點，則不會偵測到此類子循環C'。在Q發散的執行緒會執行S的收斂動態實例，因為它們在從Q到S的任何路徑上都沒有遇到循環標頭。非正式地說，在Q發散的執行緒會在C的相同迭代中在S重新收斂。1
2
3
4
5
6
7
8
9
10
執行緒 1
項目
P1
Q1
R1
S1
P3
Q3
R3
S3
Exit
執行緒 2
項目
P2
Q2
S2
P4
Q4
R2
S4
Exit
備註
一般來說，上述陳述中的循環
C並不預期對於不同的標頭是相同的循環。循環及其標頭緊密耦合；對於相同最外層循環中的不同標頭，偵測到的子循環可能不同。與上述範例相關的屬性是，對於每個封閉路徑，都有一個包含該路徑且其標頭位於該路徑上的循環C。
必須針對通過發散分支 B 及其聯集 J 的每個封閉路徑檢查發散進入準則。由於 每個封閉路徑都通過某個循環的標頭，因此這相當於檢查包含 B 和 J 的每個循環 C。當 C 的標頭支配聯集 J 時，就沒有從標頭到 J 的任何路徑的入口，這包含從 B 到 J 的任何發散路徑。對於通過包含 C 的外部循環的標頭的任何封閉路徑，也是如此。
因此，發散進入準則可以保守地簡化如下
對於發散分支
B及其聯集節點J，僅當滿足以下條件時，包含B和J的循環C中的節點才為 m 收斂：
B嚴格支配J，或
C的標頭H嚴格支配J，或遞迴地，
C內部存在滿足相同條件的循環C'。
當 J 等於 H 或 B 時，單靠支配關係不足以判斷分支路徑中各節點的收斂性。
分支路徑匯聚到循環¶
下圖顯示了兩個循環層級，其中分支點位於 Entry 而不是 Q。對於分別從 P 和 R 進入封閉路徑 P -> Q -> R -> S 的兩條線程，沿路徑生成的動態實例的收斂性取決於 P 或 R 是否為首節點。
當
P為首節點時的收斂性。1
2
3
4
5
6
7
8
9
10
11
12
13
執行緒 1
項目
P1
Q1
R1
S1
P3
Q3
S3
Exit
執行緒 2
項目
R2
S2
P2
Q2
S2
P4
Q4
R3
S4
Exit
當
R為首節點時的收斂性。1
2
3
4
5
6
7
8
9
10
11
12
執行緒 1
項目
P1
Q1
R1
S1
P3
Q3
S3
Exit
執行緒 2
項目
R2
S2
P2
Q2
S2
P4
…
Exit
因此，當分支路徑從循環外部到達不可約循環的不同入口時，靜態分析會保守地將循環中的每個節點報告為非 m-收斂。
可約循環¶
如果 C 是一個以 H 為首節點的可約循環，那麼在任何 DFS 中，H 必定是包含 C 的某個循環 C' 的首節點。與 DFS 無關，子圖 C 除了 H 本身之外沒有其他入口。因此，我們有以下結論：
對於分支點和其匯合點都在子圖
C內部的分支，分支入口準則顯然成立。當分支路徑從外部到達子圖
C時，它們的收斂性始終由同一個首節點H決定。
顯然，這只能在循環層級 T 中確定，其中 C 被檢測為可約循環。在不同的循環層級 T' 中無法得出這樣的結論，其中 C 是具有相同首節點的較大循環 C' 的一部分，但这與在 T 中的結論並不矛盾。
受控收斂¶
透過收斂控制令牌（Convergence control tokens），可以明確判斷在程式的特定時間點哪些執行緒已完成收斂。這個機制會影響動態執行個體的受控最大收斂關聯（controlled maximal converged-with）關係，以及靜態執行個體的受控 m-收斂（controlled m-converged）屬性。LLVM 中實作的一致性分析（uniformity analysis）針對支援收斂控制令牌的目標平台納入了這些特性。