GPU の warp(SIMT アーキテクチャ)において、同一 warp 内の複数スレッドが条件分岐で異なる実行パスを取る現象。分岐した両パスがシリアルに実行されるため、使用率と性能が低下する。 ## 定義 NVIDIA GPU は SIMT(Single Instruction, Multiple Thread)モデルを採用し、1 warp の 32 スレッドが同一命令を同時実行する。分岐命令でスレッドが異なるパスに分かれると、両パスが順次実行される—片方のパスを実行中、もう一方のパスに属するスレッドはマスクされて待機する。双方のパスの実行時間が加算されるため、最悪ケースでは warp の有効実行率が 50% 以下になる。 **例**: スレッド ID が偶奇で異なる処理を行う場合、warp の半数が「偶数」ブランチ実行中に待機し、次に逆が起きる。 ## 削減手法 1. **枝除去**: 条件分岐を算術命令に置換(例: `if a>0: c=a*a+b else c=a*a-b` → `flag=a>0; c=a*a+(2*flag-1)*b`) 2. **predicated instructions**: 分岐が単純な場合、条件フラグ付き命令に変換。無効スレッドは命令を実行するが結果を書き出さない 3. **スレッド/データ再マッピング**: 同じ分岐パスを取るスレッドを同一 warp に集約(sorting・stream compaction) 4. **ループアンローリング**: ループ変数に依存する分岐をコンパイル時定数に置換 5. **カーネル分割**: 分岐条件に基づき複数カーネルに分割し、各カーネル内では分岐なし 6. **アルゴリズム再設計**: データ構造を規則的にして分岐を根本的に排除 ## 横断的知見 - **3 番目に多く採用される最適化(Fig. 3)**: 分岐発散は GPU アーキテクチャの基本制約であり、不規則アルゴリズムを GPU で実行する際の主要なボトルネックとなる。21 論文が branch divergence を明示的なボトルネックとして報告([[@2023__CSUR__Optimization Techniques for GPU Programming]] Table 8) - **Volta(2017)の独立スレッドスケジューリング以前は特に深刻**: Pascal 以前の GPU は SIMT のロックステップを厳格に守っており、implicit warp-level 同期への依存が多かった。Volta で independent thread scheduling が導入されたが、これは発散のシリアル化を解消するものではなく、むしろ同期要件を変化させた - **疎行列・グラフ処理が主要なユースケース**: SpMV や BFS などの不規則アルゴリズムでは、各スレッドが処理するデータの長さや隣接数が異なるため warp 内の発散が起きやすい。多くの疎行列フォーマット(ELL・SELL-C-σ 等)は、列方向の均一性を高めて発散を減らすことを設計指針の一つとしている ## 未解決の問い - AMX・RDNA など AMD アーキテクチャの wavefront(64 スレッド幅)では分岐発散の影響はどう異なるか。RDNA2 で 32 スレッド幅に変更されたが、これは最適化指針をどう変えるか - 機械学習アクセラレータ(Tensor Core・MMA 命令)の利用では分岐発散はどの程度問題になるか - Cooperative Groups (CUDA 9.0+) は発散削減にどのような新たな手法を開くか