PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimization

技術要約：PrefixAgent

問題提起
プレフィックス加算器（Prefix adders）は、デジタルシステムにおける基本的な算術回路であるが、その設計空間はビット幅とともに指数関数的に増大するため、網羅的な探索は実用的ではない。従来の設計手法は、規則的な構造（Kogge–StoneやBrent–Kungなど）や手動による最適化に依存しているが、これらは多様なタイミング制約や非一様な入力到着時刻の下で、面積、遅延、および電力をバランスさせることに失敗することが多い。機械学習のアプローチ（RL、VAE、MCTS）も自動化のために提案されているが、これらは汎化性能の低さ、新しいシナリオに対する再学習要件によるスケーラビリティの問題、および広大なアクション空間の探索における非効率性に苦しんでいる。さらに、回路設計における大規模言語モデル（LLM）の応用には、2つの決定的な制限がある。(1) 20ノードを超える複雑なグラフを効率的に推論できないこと、(2) 特定の最適化タスクに対してモデルを微調整するための高品質で解釈可能なトレーニングデータの欠如である。

手法
本論文では、2段階の分解とツール統合型推論（TIR）パラダイムを通じてこれらの課題に対処する、LLMを活用した設計フレームワークであるPrefixAgentを提案する。

1. 2段階の分解:

   • フェーズI（バックボーン最適化）: プレフィックスグラフを直接生成する代わりに、本フレームワークは問題を「バックボーン合成」と「ローカル構造の洗練」に分解する。バックボーンは、最上位ビット（MSB）のキャリーを計算する部分グラフとして定義される。これにより、設計空間をカタラン数の積から単一のカタラン数へと削減し、複雑さを大幅に簡素化する。LLMは、グループ化のパターンを最適化するために「リグループ（regroup）」操作（サブツリーの再編成）を行うことで、初期の直列バックボーン構造を反復的に洗練させる。
   • フェーズII（ローカル構造の洗練）: 最適化されたバックボーンが確立された後、補助ノードを追加することで完全なプレフィックス加算器を構築する。その後、LLMは、タイミング違反を解決するために、物理実装ツールからのフィードバックに基づいたローカルな構造的洗練（レベル最適化、ファンアウト削減、ノード・クローニングなど）を実行する。

2. ツール統合型推論 (TIR):
   PrefixAgentは、大規模推論モデル（LRM）が外部ツールに精密な構造変更を委譲できるように、ファンクション・コーリングを採用している。LLMは高レベルの意思決定（「何を」最適化し「どこを」最適化するか）に集中し、外部ツールがその変更を実行し、フィードバック（タイミング情報が付与されたS式、物理的メトリクスなど）を提供する。これにより、高レベルの推論とアルゴリズムの精密さの間のギャップを埋める。

3. E-Graphベースのデータ生成:
   高品質なトレーニングデータの不足に対処するため、著者らはe-graphと等価飽和（equality saturation）を利用している。彼らは、バックボーン構造をS式として表現するためにドメイン固有の中間言語（BackboneLang）を定義している。e-graph内で結合律に基づく書き換えルールを適用することで、解空間を体系的に探索する。本フレームワークは、タイミングを考慮したコスト関数を用いて最適化されたバックボーンの候補を抽出し、e-graphエクスプレイナーを利用して解釈可能な書き換え軌跡を生成する。これらの軌跡は、LRMを微調整するために使用されるChain-of-Thought（CoT）推論を合成するためのグラウンドトゥルース（正解）として機能する。

主な貢献

• PrefixAgentフレームワーク: プレフィックス加算器の最適化を64ビット設計までスケールさせ、商用ツールを凌駕することができる、初のLLMベースのアプローチ。
• 新しい設計観点: バックボーン生成とローカルな洗練を分離する分解戦略により、効率的な推論と欠陥のない加算器合成を可能にする。
• データ生成パラダイム: e-graphを用いて、LRMの微調整のための大規模かつ高品質で解釈可能な最適化軌跡を生成する体系的な手法。これにより、回路設計におけるデータの希少性を克服する。
• ツール統合型推論: LLMが実行のために外部ツールを呼び出すコントローラーとして機能するアーキテクチャであり、構造的な妥当性と物理的な実現可能性を保証する。

実験結果
実験は、生成されたデータセットで微調整されたQwQ-32Bモデルを用いて、NanGate45ライブラリおよびOpenROADフローの下で、一様および非一様な入力到着時刻プロファイルの双方で実施された。

• 性能: PrefixAgentは、ほぼすべての構成において、ベースライン手法（DP、MCTS、RL、VAE、およびPrefixGPTを含む）よりも小さな面積を持つプレフィックス加算器を合成する。面積の優位性は、大きなビット幅において顕著になり（例：64ビット時において最良のベースラインと比較して最大11.3%の削減）、拡大する。
• 汎化性能: 本フレームワークは強力な汎化性能を示し、訓練セットに含まれていない未知のビット幅（例：54ビット）や非一様な到着プロファイルにおいても優れた結果を達成している。
• 効率性: PrefixAgentは、検索ベースのベースライン（MCTS、RL、VAE）と比較して10倍以上の高速化を実現している。これは、新しいシナリオごとに再学習を行う必要がなく、LRMによるターゲットを絞った最適化を行うためである。
• 商用フロー: 32nmテクノロジーを用いた商用の物理設計フローの下で評価した際、PrefixAgentが生成した加算器は、商用の合成ツールと比較してより小さな面積を維持した。
• アブレーション研究: フェーズIIの洗練の必要性、グリッド/隣接リスト・エンコーディングに対するEnhanced Prefix Representation (EPR) の優位性、および高品質な結果を達成するためのCoT推論の決定的な役割を、結果が裏付けている。

意義
本論文は、PrefixAgentが算術回路設計の自動化における重要な前進であることを主張している。複雑な設計タスクを管理可能なサブ問題に分解し、高品質なデータ生成のためにe-graphを活用することで、従来の機械学習ベースの手法におけるスケーラビリティと汎化の限界を克服している。本フレームワークは、ツール統合と解釈可能な推論軌跡による微調整によって適切に導かれた場合、LLMが複雑な設計空間を効果的にナビゲートし、特に大規模設計において、従来のヒューリスティックや商用EDAツールを凌駕できることを示している。著者らは、このデータ生成パラダイムと分解戦略が、乗算器の最適化などの他のデータパス最適化タスクにも拡張可能であると考えている。