2026__MLSys2026__Automated Algorithm Design for Auto-Tuning Optimizers

# Automated Algorithm Design for Auto-Tuning Optimizers > [!info] Talk metadata > - **会議:** [[MLSys2026]] Day 3 (May 20 / Wed)、Research Track Oral "LLM Serving 3 & ML for Systems" セッション（13:30 PDT 開始、個別時刻は不明） > - **論文タイトル:** Automated Algorithm Design for Auto-Tuning Optimizers > - **著者（論文表紙）:** Floris-Jan Willemsen¹、Niki van Stein¹、Ben van Werkhoven¹（¹LIACS, Leiden University, the Netherlands）。Correspondence: Floris-Jan Willemsen（[email protected]） > - **登壇者:** 文字起こしが無いため発表者個人は断定できない。スライド表紙では筆頭著者 Floris-Jan Willemsen が記載され、所属ロゴは Universiteit Leiden（The Netherlands） > - **コード/データ:** https://github.com/XAI-liacs/BLADE/tree/paper/auto-tuning （論文 §1・§5）。Kernel Tuner: https://github.com/KernelTuner/kernel_tuner 、LLaMEA: https://github.com/XAI-liacs/LLaMEA > - **会議情報（論文表紙）:** Proceedings of the 9th MLSys Conference, Seattle, WA, USA, 2026 > [!abstract] 概要（論文 PDF アブストラクト・忠実日本語訳） > 自動性能チューニング（auto-tuning）は高性能アプリケーションを最適化するうえで不可欠であり、広大で不規則な探索空間が手動探索を実行不可能にする。auto-tuner は伝統的に進化的・焼きなまし・サロゲートベースなどの古典的手法に依拠してきたが、多様なタスクにわたって near-optimal な構成を頑健かつ効率的に見つけるアルゴリズムを設計するのは難しい。我々は新しいパラダイムを提案する。すなわち、大規模言語モデル（LLM）を用いて auto-tuning 問題に適合した最適化アルゴリズムを自動生成するというものである。我々は、問題記述と探索空間の特性を LLM にプロンプトとして与え、専用 optimizer を合成・テスト・反復的に改良するフレームワークを導入する。生成されたアルゴリズムは、2 つの現代的 auto-tuning フレームワーク上で 6 種のハードウェアプラットフォームにわたる 4 つの実世界 auto-tuning アプリケーションで評価し、SOTA と比較する。評価により、生成段階で追加のアプリケーション固有・探索空間固有の情報を与えると平均で **30.7%** および **14.6%** の性能改善が得られることが示される。さらに、LLM 生成 optimizer は既存の人手設計アルゴリズムに匹敵し、多くの場合凌駕することを示し、最良の生成最適化アルゴリズムは auto-tuning 向け SOTA optimizer に対して平均 **72.4%** の改善を達成する。 > [!note] 出典に関する注記 > 本ノートは**論文 PDF と発表スライド PDF のみに基づく**。音声文字起こしは無いため、発表者個人は特定できず、Q&A も省略する（論文筆頭著者 Floris-Jan Willemsen を仮の登壇者として扱う）。**スライドは導入部分（auto-tuning の動機・Kernel Tuner 紹介・最適化アルゴリズムの必要性の問題提起、p1-9）のみで、提案手法・実験結果はスライドに含まれない。** したがって手法・数値はすべて論文 PDF の記載に由来する。本文中の数値・固有名・式・図構造はすべて論文またはスライドの記載に由来する。 ## 問題設定: なぜ auto-tuning に専用 optimizer が要るか - **auto-tuning とは（スライド p1）:** 「特定アーキテクチャ上で特定問題を解くために、適応可能なパラメータを自動最適化すること」（引用 [1] Pallarés et al., 2023）。典型的な目的は performance / energy efficiency / accuracy。 - **持続可能性・生産性の問題（スライド p2-5）:** ハードウェアの寿命は短い。スーパーコンピュータは平均 **5.2 年**で後継機に置き換わり（Jaguar 2009 → … → El Capitan 2024）、GPU アーキテクチャの平均寿命は **1.96 年**。一方でアプリケーション（VASP, LAMMPS, cp2k, GROMACS, NEMO）の平均年齢は **30.2 年**と長寿命。「アプリケーションが 1〜5 年ごとの新ハードへどう適応するか」が課題で、ソースに `#if __CUDA_ARCH__ == 700 …` のようなハードコードで対応するのは悪手（スライド p5）。 - **解＝tunable code（スライド p6）:** スレッド/ブロックへのマッピング、メモリ上のデータ配置、work-per-thread、loop unrolling、計算と通信のオーバラップなどを、定数をハードコードせず実装選択としてパラメータ化し、auto-tuning フレームワークに任せる。 - **Kernel Tuner（スライド p7、論文 §3.1）:** 2016 年開始の Python 製 OSS auto-tuning フレームワーク（GitHub Star 394、スライド p7 表示）。CUDA/HIP/OpenCL/OpenACC/C/Fortran 対応、verification・accuracy tuning・energy tuning・observers をサポート。20 以上の最適化アルゴリズムを内蔵。 - **auto-tuning の効果と難しさ（スライド p8-9、論文 §1・§3.3）:** Convolution の探索空間（AMD W6600 / MI250X / NVIDIA A4000 / A100）では正規化 GFLOP/s の分布が極端に偏り（スライド p8、出典 [2] Lurati et al., EuroPAR 2024）、良い構成は稀。探索空間は **large・discontinuous・irregular**。**Research gap（スライド p9）:** 「なぜ auto-tuning 問題向けに設計された optimizer が存在しないのか」。理由は (1) アプリ・ハード横断の汎化が難しい、(2) アルゴリズム設計に時間がかかる、(3) 代表的なアプリ・ハード集合での反復 auto-tuning が実行不可能。 ## 提案手法: LLM による最適化アルゴリズムの自動生成論文は、auto-tuning 向け optimizer を**人手で設計せず LLM に自動生成・適応・進化させる**初の閉ループフレームワークを提案する（論文 §1・§3）。**LLM が生成するのは最適化アルゴリズムのロジックのみ**であり、チューニング対象のアプリケーション本体・カーネルコード・データ・実行・数値精度には一切干渉しない（論文 §3.2）。生成アルゴリズムが正しく動かなくても、進化的アルゴリズムの選択段階で淘汰されるため、高品質なものだけが残る。 ### Kernel Tuner × LLaMEA の統合（論文 §3.1-3.2、Figure 1・2・3） - **対象フレームワーク Kernel Tuner（論文 §3.1）:** ユーザがカーネル実装とチューナブルパラメータ・制約を記す Python スクリプトを与えると、Kernel Tuner は妥当な全構成からなる探索空間 $\mathcal{X}$ を構築し、optimizer が候補 $x\in\mathcal{X}$ を選んでコンパイル・実行・計測する。目的は最適構成 $x^\star = \arg\min_{x\in\mathcal{X}} f_{G_j,I_k}(K_{i,x})$（カーネル $K_i$、ターゲットシステム $G_j$、入力 $I_k$）。外部定義の optimizer を使えるよう `OptAlg` ラッパクラスを実装した。 - **生成器 LLaMEA（論文 §3.2、van Stein & Bäck, 2025）:** Large Language Model Evolutionary Algorithm。LLM の生成能力で最適化アルゴリズムを合成する。進化的アルゴリズム（EA）をメタ戦略とする閉ループ（論文 §3、Figure 1）: 1. LLM が生成した候補 optimizer の population を初期化（**parent 4 個**から開始）。 2. 各候補を Kernel Tuner 上で auto-tuning methodology の性能スコア $\mathcal{P}$ により training set で評価。 3. 高スコアのものを再生産に選択、低スコアは破棄（**elitism: parent 4 + offspring 12/世代**）。 4. LLM 駆動の mutation operator（計 12 種、diversity 重視を含む）で新候補を生成。 - 2-4 を予算が尽きるまで反復。生成コードのタイムアウト・エラーはスタックトレースを LLM へ feed-back して自己デバッグさせる。 - **プロンプト構成（論文 §3.2、Figure 3・4）:** Task Prompt はコード形式仕様・（任意の）探索空間仕様（JSON）・最小動作例・出力形式を含む。Mutation Prompt は「戦略を洗練」「過去と異なる新アルゴリズム生成」「洗練して単純化」など。`SearchSpace` オブジェクトの interface（初期 population 生成・近傍取得・制約違反の repair）を LLM に提示し、探索空間情報を任意で注入する。 ### 生成アルゴリズムの評価指標（論文 §3.3、Eq. 2・3） - コミュニティ標準の auto-tuning methodology（Willemsen et al., 2024）に従い、性能スコア $\mathcal{P}$ は**ランダム探索ベースライン**に対する性能-時間曲線下面積として定義。$\mathcal{P}=0$ がベースライン同等、$\mathcal{P}=1$ が即座に最適解到達。 - 単一探索空間: $\mathcal{P}(\mathcal{F},G_j,K_i,I_k)_t = \dfrac{\mathcal{S}_{\text{baseline}}(t) - \mathcal{F}(G_j,K_i,I_k)_t}{\mathcal{S}_{\text{baseline}}(t) - \mathcal{S}_{\text{opt}}}$（Eq. 2）。budget はベースラインが median と optimum の間の所定パーセンタイル（典型 95%）に達する時刻で打ち切る。 - 集約スコア: 全カーネル $K$・システム $G$・入力 $I$・時間サンプル $\mathcal{T}$ で平均（Eq. 3）。これにより構成品質と所要時間の両方を捉えた頑健な比較が可能。 ## 実験 ### セットアップ（論文 §4.1、Table 1） - **ベンチマーク（論文 §4.1.1、BAT benchmark suite, Tørring et al., 2023）:** 4 つの実世界 GPU カーネル。 - **Dedispersion**（天文・単一パルス過渡現象検出、AMBER パイプライン由来）: Cartesian 探索空間 **22272**、制約後 **11130**、次元 **8**。一般に bandwidth-bound。 - **2D Convolution**（画像処理、van Werkhoven et al. 2014）: Cartesian **10240**、制約後 **4362**、次元 **10**。compute-bound。 - **Hotspot**（熱シミュレーション、Rodinia 由来）: Cartesian **22200000**、制約後 **349853**、次元 **11**。bandwidth-bound。 - **GEMM**（密行列積、CLBlast 由来）: Cartesian **663552**、制約後 **116928**、次元 **17**。compute-bound。 - **ハードウェアと実行（論文 §4.1.2）:** DAS-6 と LUMI スーパーコンピュータの **6 種 GPU** で **24 の auto-tuning 探索空間**を構成。**training set は 4 アプリ × 3 GPU（AMD MI250X / NVIDIA A100 / NVIDIA A4000）の 12 探索空間**、**test set は 4 アプリ × 別 3 GPU（AMD W6600 / AMD W7800 / NVIDIA A6000）の 12 探索空間**。optimizer 生成は DAS-6 の A4000 ノード（24-core AMD EPYC-2 7402P, 128 GB RAM）で実施。事前探索済みの探索空間を使い再コンパイル/実行を回避、評価を数時間〜数日でなく数秒〜数分に短縮。 - **ソフトウェア（論文 §4.1.3）:** Rocky Linux 8（kernel 4.18）、Python 3.11.7、**Kernel Tuner 1.3.0**、PyATF 0.0.9、**LLaMEA 1.0.6**。LLM は **GPT o4-mini**（デフォルトハイパラ）。gemini-2.0-flash も試したが o4-mini が優位。 - **生成コスト（論文 §4.1.4-4.1.5、Figure 5）:** optimizer 生成は **100 LLM calls/run × 5 独立 run/カーネル・手法 = 計 4000 LLM calls**。5 run のうち最良を採用。各候補の評価は wall-clock **最大 5 分**で打ち切り。生成 optimizer の **約 25% が失敗**（無効コード・実行時エラー・時間超過）するが進化ループで淘汰される。トークン総数は手法ごとに約 30 万〜45 万トークン/run（Figure 5）。 ### 結果 - **追加情報の効果（論文 §4.2、Table 2・Figure 6）:** 各アプリで「探索空間情報なし」と「あり」の 2 種を生成。探索空間情報の追加で平均スコアが **0.404 → 0.463（+0.057、14.6% 改善）**。特に **dedispersion（0.383 → 0.515、+0.132）** と **GEMM（0.432 → 0.516、+0.084）** で大きく改善。convolution は微減（0.429 → 0.426、-0.003）、hotspot は微増（0.373 → 0.388、+0.015）。 - **ターゲット特化の効果（論文 §4.2、Table 3・Figure 7）:** あるアプリ向けに生成したアルゴリズムを、そのアプリで非ターゲット生成と比べると平均 **30.7% 改善**（target score 平均 0.475 vs non-target 平均 0.419、+0.055）。ただし全ケースで効くわけではなく、hotspot ターゲットと convolution（extra info あり）は非ターゲット版に劣る。それ以外 5 つのアルゴリズムは特化で大きく改善。 - **2 つの最良生成アルゴリズム（論文 §4.3、Algorithm 1・2）:** - **HybridVNDX**（target: dedispersion, extra info）: Variable Neighborhood Descent（VND）に (i) 動的近傍重み付け、(ii) k-NN サロゲートによる事前スクリーニング、(iii) elite 組換え、(iv) tabu search ＋ simulated annealing を組み合わせる。デフォルト: $k=5$、pool size 8、100 非改善ステップで restart、tabu size 300、$T_0=1.0$、cooling 0.995。 - **AdaptiveTabuGreyWolf**（target: GEMM, extra info）: 妥当構成の小集団を保持し、各ステップで非リーダー候補を 3 つの best 解または自身から各パラメータ独立に混合して提案、light "shaking" で摂動（探索初期は粗く後期は厳密）、tabu list で重複防止、SA 基準で受理（budget 減衰温度＋停滞時 mild reheating）、停滞時は最悪個体の一部を再初期化。$p=8$、$L=3p$、$s=0.2$、$q=0.15$、$\tau=80$、$\rho=0.3$、$T_0=1.0$、$\lambda=5.0$、$T_{\min}=10^{-4}$。 - 共通の良特性（論文 §4.3）: (1) どちらも評価時間が支配的で追加制御ロジックは軽量、(2) 近傍 API がアーキ非依存に制約を尊重しつつ動ける（large irregular 探索空間に必須）。 - **人手設計アルゴリズムとの比較（論文 §4.4、Figure 8・9）:** 上記 best 2 つ（extra info あり）を、Kernel Tuner の **Genetic Algorithm (GA)**・**Simulated Annealing (SA)**（いずれも同条件で 7 日間ハイパラチューニング済み）と、別フレームワーク pyATF の **Differential Evolution (DE)** と全 24 探索空間で比較。LLM 生成アルゴリズムは性能スコアで **GA 比 +0.126、SA 比 +0.282、pyATF DE 比 +0.274** 上回り、**平均 72.4% 改善**。GA は hotspot のみで上回るがそれ以外では劣る。探索空間間の性能安定性も高い（Figure 9）。 ## 結論 - アーキテクチャの複雑化が続くなか、auto-tuning は高性能達成に不可欠であり続け、その中核は探索効率を左右する最適化アルゴリズムの選択にある（論文 §5）。 - 本研究は **LLM を用いて auto-tuning 問題に特化した最適化アルゴリズムを自動生成する**新パラダイムを提示。フレームワークの構成要素は既存だが、閉ループ・メタ最適化システムへの統合により、既存にない新規最適化アルゴリズムを発見する創発的挙動を生む。 - LLM 生成 optimizer は人手設計に匹敵・凌駕し、アプリ・探索空間固有情報を与えるとさらに性能が向上する。強い汎化（学習に使っていない GPU・アプリ外）も示す。 - 最良アルゴリズムは Kernel Tuner に取り込み済み（`pip install kernel-tuner`）。LLaMEA は `pip install llamea`、実験は BLADE benchmarking suite で実装。 - **将来課題（論文 §5）:** 生成性能は基盤 LLM（o4-mini / gemini-2.0-flash 等）に依存。固定のアプリ・GPU 集合での評価のため、より広いアーキ・ドメインでの検証が今後必要。optimizer 生成は大規模 auto-tuning インフラ・コンパイラ・ML 展開システムにおける基盤的能力になりうる。