資料層級平行:SIMD、向量與 GPU

分支發散(branch divergence)

想像一隊 32 人的賽艇隊,因為共用一個鼓點,必須在同一瞬間全划同一槳。現在給他們一道指令,有些人理解為「往左划」、有些理解為「往右划」。他們無法用單一共用節拍同時做兩者,於是舵手得喊:「左划手動,右划手凍住」——再喊「右划手動,左划手凍住」。本該一拍完成的工作現在要兩拍,每次有一半的人閒著。這在 GPU 上就是分支發散:當一個 warp 裡的執行緒走分支的不同邊時,硬體必須一前一後執行那些路徑。

具體說,一個 warp 裡所有執行緒共用一個程式計數器與指令提取單元,所以每一步都必須執行同一條指令。當程式說 if (x > 0) 做 A 否則做 B,而一個 warp 裡有些執行緒 x > 0、有些不是,硬體就無法同時跑 A 與 B。它先跑路徑 A,用遮罩停掉 else 那些執行緒(它們閒置),再跑路徑 B,用遮罩停掉 if 那些執行緒。兩條路徑被序列化;該區域 warp 的有效吞吐量,就按被遮掉的執行緒比例下降。深層巢狀或依資料而定的分支會把這個懲罰疊起來。

這是 GPU 初學者必須牢記的最重要效能陷阱,也是為什麼誠實地說 GPU 不擅長多分支的程式。注意分支發散不是什麼:一個 warp 裡 32 個執行緒全都一致的分支(全走 if,或全走 else)不會多花成本——warp 就單純跑一條路徑,無人閒置。懲罰只來自一個 warp 內的分歧;在較粗粒度上的分支,整個 warp 走同一邊,沒問題。所以好的 GPU 程式會試著安排資料,讓相鄰的執行緒(同一 warp 裡的)傾向走同一條路——例如依分支結果把工作排序——把發散變回一致。

if (a[id] > 0) y[id] = sqrt(a[id]); else y[id] = 0; 在一個半數元素為正、半數不是的 warp 裡,warp 先跑 sqrt 路徑、讓負元素的執行緒閒置,再跑歸零路徑、讓正元素的執行緒閒置——約為不發散 warp 的 2 倍時間。若 32 個元素全為正,就沒有發散也沒有懲罰。

warp 內的發散把分支路徑序列化;warp 內的一致則不額外花成本。

發散只有在同一 warp 裡的執行緒分歧時才傷人。32 個全走同一邊的分支是免費的。所以解法不是「移除所有分支」,而是「安排資料讓一個 warp 的執行緒傾向一致」。

又称
warp divergencethread divergencewarp 發散執行緒發散