> [!abstract] 概要(原文 abstract の和訳) > 過去 10 年、グラフィックス処理ユニット(GPU)はハイパフォーマンスコンピューティング分野で重要な役割を果たし、IoT・自律走行車・エクサスケールコンピューティングなどの新分野においても発展を続けている。これらのプロセッサから性能を引き出す方法を理解することは重要であるが、それは自明ではない。本サーベイは過去 14 年間に発表された 450 本の論文から見出された様々な最適化技術を論じる。異なる視点から最適化を分析した結果、各種最適化が高度に相互依存していることが示され、auto-tuning のような技術の必要性が説明される。 ## 論文情報 - **タイトル**: Optimization Techniques for GPU Programming - **著者**: [[Pieter Hijma]]（[[Vrije Universiteit Amsterdam]]）、[[Stijn Heldens]]・[[Alessio Sclocco]]・[[Ben van Werkhoven]]（[[Netherlands eScience Center]]）、[[Henri E. Bal]]（[[Vrije Universiteit Amsterdam]]） - **媒体**: ACM Computing Surveys (CSUR), Vol. 55, No. 11, Article 239 - **発表年**: 2023 年 3 月（受理 2022-10-17） - **DOI**: 10.1145/3570638 - **ページ数**: 81 - **ライセンス**: CC-BY - **資金**: Dutch Research Council (NWO) NWA-ORC NWA.1160.18.316 (CORTEX)、Netherlands eScience Center 027.016.G06 ## 概要 本論文は GPU プログラミングにおける最適化技術を体系的に整理した包括的サーベイである。Scopus データベースから選出した 450 本の論文を 5 フェーズで処理し、28 種の最適化技術を 4 テーマ(メモリアクセス・不規則性・バランシング・ホストインタラクション)に分類。さらに複数の視点(アプリケーション特性・ボトルネック種別・アーキテクチャ進化・性能ポテンシャル)から分析し、最適化間の相互依存性と auto-tuning の不可欠性を論じる。 ## 問題設定 - **入力**: GPU カーネルのソースコード(CUDA または OpenCL を主対象) - **目的**: ソフトウェアレベルの手動適用可能な最適化技術の性能向上 - **対象外**: マルチ GPU クラスタ最適化・ハードウェアレベル最適化・コンパイラのみが適用可能な最適化・アルゴリズムレベルの変更 - **スコープ**: 2007〜2021 年の HPC・並列処理系トップ会議/論文誌(IPDPS・SC・PPoPP・CPE・TPDS 等) ## 提案手法:28 種の最適化技術の分類体系 ### テーマ 1: メモリアクセス(Section 6.1) **オンチップ最適化**: - **専用メモリの使用(Use Dedicated Memories)**: コンスタントメモリ(最大 64 KiB、read-only・ブロードキャスト向け)、テクスチャメモリ(2D 空間局所性・境界値処理)、シェアードメモリ(SM 内スクラッチパッド、バンクコンフリクト対策に padding/reorder が必要) - **ワープ関数の使用(Use Warp Functions)**: warp vote 関数(Fermi 2010〜)・warp shuffle 関数(Kepler 2012〜)でシェアードメモリ非経由のスレッド間通信。reduction・prefix-sum への応用が主 - **レジスタブロッキング(Register Blocking)**: レジスタ(最高速)への頻用値キャッシュ。loop unrolling と密接に連携。3D ステンシルの Z 方向で顕著 - **レジスタ使用削減(Reduce Register Usage)**: オキュパンシー向上のため一時変数をシェアードメモリに移動、型パッキング、再計算等 - **再計算(Recompute)**: 通信回避のために計算済み値を再計算。プリコンピュートの逆で、演算が豊富な現代 GPU に有利 **オフチップ最適化**: - **コアレスドアクセス(Coalesced Access)**: 2 位の人気技術(66 論文がグローバルメモリ帯域幅をボトルネックと報告)。1 ワープ 32 スレッドのメモリアクセスが連続 128 バイト境界整列で 1 トランザクション化。スレッド再配置・タイリング・AoS→SoA 変換・padding が主手法 - **空間的ブロッキング/ループタイリング(Spatial Blocking)**: データを 1 ブロック単位で処理、L1/L2 キャッシュ・テクスチャキャッシュ・レジスタ・シェアードメモリのデータ再利用を促進。Stratton らは 12〜6x の性能向上を報告 - **カーネルフュージョン(Kernel Fusion)**: 3 位の性能技術(10〜17%)。同一データを扱う複数カーネルを統合してグローバルメモリアクセスを削減。レジスタ/シェアードメモリ圧力が増すトレードオフあり - **ソフトウェアプリフェッチング(Software Prefetching)**: 次タイルを現タイル処理中にプリフェッチ。メモリ遅延を隠蔽。double buffering とも呼ばれる(20〜40% の性能向上例あり) - **データ圧縮(Compress Data)**: 疎行列インデックスや転送データのフットプリント削減(1.27〜5x) - **プリコンピュート(Precompute)**: 計算をオフラインに行い再利用。時間と空間のトレードオフ ### テーマ 2: 不規則性(Section 6.2) GPU は高度に規則的なアーキテクチャだが、アプリケーションはしばしば不規則であり、この不一致への対処が以下の技術群の目的である。 - **ループアンローリング(Loop Unrolling)**: ループ本体を明示的に繰り返し展開。ILP 向上・ループオーバーヘッド削減・コンパイラ最適化促進。ただし過剰な展開はレジスタ圧力増・キャッシュ圧迫で逆効果(最大 25% 改善) - **分岐発散削減(Reduce Branch Divergence)**: warp 内スレッドが異なる分岐を取るとシリアル実行となる問題への対処。枝除去・枝削減・predicated instructions・スレッド/データ再マッピング・ストリームコンパクションが主手法(3.45x の例あり) - **疎行列フォーマット(Sparse Matrix Format)**: SpMV 向け多数のフォーマット提案(ELL・CSR・HYB・SELL-C-σ 等)。アクセスの規則性・コアレッシング・分岐削減が設計指針 - **カーネル分割(Kernel Fission)**: 単一カーネルを複数に分割してリソース利用効率を向上。カーネルフュージョンの逆方向(70% の性能向上例あり) - **冗長計算削減(Reduce Redundant Work)**: 冗長とみなされる処理を回避。グラフ・動的計画法・線形代数の不規則データ構造での採用が多い ### テーマ 3: バランシング(Section 6.3) - **ベクトル化(Vectorization)**: ベクトル型を用いたスカラー変数の置き換え。メモリ帯域幅向上・コアレッシング支援(2.3〜6.1x の例あり) - **高速数学関数(Fast Math Functions)**: 近似数学関数で SFU を活用。精度犠牲のトレードオフ(3.3〜4.8x の例あり) - **ワープ中心プログラミング(Warp-Centric Programming)**: warp を計算単位として扱うコード構造化。同期オーバーヘッド削減に寄与(4〜8x の例あり) - **スレッド毎ワーク変化(Varying Work per Thread)**: 各スレッドの処理量を調整してデータ再利用・ILP 向上(2〜12x の例あり) - **スレッドブロックリサイズ(Resize Thread Blocks)**: スレッド数とブロック数のパラメータ調整。SM のオキュパンシーとレジスタ使用量のバランスをとる(30x の例あり、CFD ソルバ) - **Auto-tuning**: 最適設定を自動探索(詳細は [[Auto-tuning]])。12x の例あり。CLTune・PADL・Kernel Tuner・OpenTuner 等のフレームワークが存在 - **負荷分散(Load Balancing)**: warp 内・ブロック内・ブロック間・CPU-GPU 間の多層で不均衡を解消。グラフ・疎行列処理で特に重要(40〜60% の例あり) - **同期削減(Reduce Synchronization)**: バリアのオーバーヘッドを削減。Cooley-Tukey FFT の同期不要版等(35〜50% の例あり) - **アトミック削減(Reduce Atomics)**: アトミック操作の競合コストを削減。warp level で集約してからグローバル更新する手法等(35% の例あり) - **ブロック間同期(Inter-Block Synchronization)**: CUDA 9.0 以前はカーネル起動が唯一のグローバルバリアだったが、グローバルメモリを利用した実装が提案された(11〜60% の例あり) ### テーマ 4: ホストインタラクション(Section 6.4) - **ホスト通信(Host Communication)**: PCIe バス帯域幅の最適化。ピンメモリ・ストリーム・double buffering による転送とカーネル実行の重複(18.9% の例あり) - **CPU/GPU 計算分担(CPU/GPU Computation)**: CPU と GPU の計算分担最適化。k-means で 15〜20% ## 新規性 先行サーベイ(Ryoo et al. 2008、Stratton et al. 2012、Brodtkorb et al. 2012)は著者の経験則ベースで体系的文献調査に基づかない。本論文は Scopus を用いた系統的文献レビュー(SLR)手法で 450 本を処理し、(1)技術の頻度・相互依存性の定量化、(2)ボトルネックと最適化の対応関係の明示、(3)アーキテクチャ進化との関係分析、(4)性能ポテンシャルの定量的概観(Table 11)、という 4 点で先行研究を超える。 ## 実験設定 - **調査対象**: Scopus データベース、クエリ実行 2019-11-29・2021-05-27 更新 - **規模**: 最初クエリで 3,973 件 → 5 フェーズ選択で 450 件(401 件 + 49 件の高被引用論文) - **分析**: litstudy パッケージによるデータベース管理と分析 - **評価**: GPU 毎の最適化頻度、ボトルネック種別集計、性能向上の代表的数値収集 ## 実験結果 **採用頻度(Fig. 3)の上位最適化**: 1. コアレスドアクセス(最多) 2. 専用メモリの使用(2 位) 3. 分岐発散削減(3 位) 4. auto-tuning(4 位) 5. ホスト通信(5 位) **主要ボトルネック(Table 7〜10)**: - グローバルメモリ帯域幅: 66 論文 - グローバルメモリ遅延: 24 論文 - アンコアレスドアクセス: 22 論文 - 不規則アクセス: 19 論文 - PCIe 帯域幅: 34 論文 **性能ポテンシャル(Table 11)の代表値**: | 最適化 | スピードアップ | アーキテクチャ | |---|---|---| | シェアードメモリ使用 | 2 桁 | Tesla (2008) | | ループタイリング | 3〜6x | Tesla (2008) | | レジスタブロッキング | 2〜7x | Volta (2017) | | 空間的ブロッキング | 3〜6x | Tesla (2008) | | Auto-tuning | 12x | AMD Tahiti (2009) | | スレッド毎ワーク変化 | 2〜12x | AMD Tahiti (2011) | | カーネル分割 | 70% | AMD Cypress (2009) | | カーネルフュージョン | 10〜17% | Kepler (2012) | | 負荷分散 | 40〜60% | Turing (2018) | ## 考察 **最適化の相互依存性**: 最適化はテーマで分類できるが実際には高度に相互依存している。たとえばカーネルフュージョンはメモリアクセス削減だけでなくブロック間同期を可能にしてプリフェッチングを実現する。 **アーキテクチャ依存性**: Fermi(2010)の L1/L2 キャッシュ導入でコアレッシングの重要性が相対的に低下した。Maxwell(2014)はシェアードメモリとテクスチャキャッシュを統合し、Turing(2018)は L1 との統合でテクスチャメモリの効果が激減した。Volta(2017)の Tensor Core は MMA 命令で深層学習向け最適化の文脈を一変させた。 **利用率の複雑さ**: Volkov のパフォーマンスモデル(数式: utilization = min(1, TLP × ILP × BLP / parallelism_min))が示すように、TLP(スレッドレベル並列性)と ILP(命令レベル並列性)はトレードオフ関係にあり、TLP 増加が ILP 機会を減らすこともある。これが auto-tuning の必要性を生む根本原因の一つである。 ## 強み - 系統的文献レビュー手法による再現可能な論文選択プロセス - 450 本という大規模な一次文献の網羅的分析 - 技術間の相互依存性を多面的視点(アプリ特性・ボトルネック・アーキテクチャ)で明示 - Table 11 による性能ポテンシャルの比較参照表 ## 弱点・課題 - NVIDIA GPU の論文が圧倒的多数(AMD は 10% 超)であり、Intel GPU はほぼ対象外 - 2021 年以降(Ampere・CDNA・RDNA・Hopper)のアーキテクチャは分析範囲外 - 性能数値は文脈依存で Table 11 の数値間の直接比較は無意味 - アルゴリズムレベルの最適化を除外しているため、実際の最適化の全体像ではない - NLP・LLM 時代の Transformer カーネル最適化(Flash Attention 等)は対象外