CoEvoP&R: Co-Evolving Placement Objectives with Routing Feedback via Large Language Models

技術概要: CoEvoP&R

問題提起
DREAMPlaceのような現代的な解析型配置ツールは、グローバル配置を導くために微分可能な目的関数に依存しています。これらの目的関数は通常、半周長ワイヤ長（HPWL）の平滑近似やセル密度ペナルティといった、中間的なサロゲート（代理）指標を組み合わせたものです。しかし、配置段階のサロゲートと、最悪負のスラック（WNS）や合計負のスラック（TNS）といったタイミング指標を含む最終的な配線後の設計品質との間には、重大な乖離が存在します。

このギャップを埋めるための先行研究は2つのカテゴリーに分類されますが、いずれも限界があります：

1. 人間が設計した項: RUDY（Rectangular Uniform wire DensitY）のような手法は、配線需要の推定値を取り入れていますが、これらは専門家による近似に依存しており、異なる設計やテクノロジーごとに再チューニングが必要になることがよくあります。
2. 学習されたブラックボックス・サロゲート: LaMPlace、GOALPlace、RoutePlacerなどのアプローチは、学習された予測器や微分可能な配線性サロゲートを使用しています。これらは効果的ですが、これらの「ブラックボックス」コンポーネントは、記号的かつ微分可能な目的関数を必要とする既存の解析型配置フロー内において、説明性、デバッグ性、あるいは展開のしやすさに欠けています。

手法
CoEvoP&R（Co-Evolving Placement Objectives with Routing Feedback：配線フィードバックを用いた配置目的関数の共進化）は、読み取り可能で微分可能な解析型配置目的関数を自動的に進化させる、大規模言語モデル（LLM）ベースのフレームワークを導入することで、これらの限界に対処します。本システムは、以下の3つの主要なステージからなるクローズドループ型の進化プロセスとして動作します。

1. アーカイブ条件付きプロポーザル:
   各世代において、システムはLLM用のプロンプトを組み立てます。このプロンプトには以下が含まれます：

   • 許容される構文とコンポーネントを定義する制限付き目的関数インターフェース。
   • ベースラインのコンテキストと、前世代の親となる目的関数。
   • 過去の候補、その挙動指標、および失敗からの教訓を含むアーカイブ。
   • 配置、タイミング・プロキシ、および配線ツールから測定されたフィードバック。
     LLMは、初期化マップ、スケール変数用の更新マップ、および損失関数を定義する、候補となる記号的プログラム（Pythonに似たスクリプト）を生成します。

2. 候補の検証と埋め込み:
   提案された記号的プログラムは、即座に実行されるわけではありません。これらは、DREAMPlaceフレームワーク内で微分可能であり、有界であり、かつ実行可能であることを保証するための検証プロセスを経ます。検証された候補は配置器に埋め込まれ、ネイティブの目的関数と置き換えられます。システムは、生成された目的関数が勾配ベースの最適化と互換性を維持することを保証します。

3. コストスケール評価とアーカイブ更新:
   計算コストを管理するために、CoEvoP&Rは階層的な評価戦略を採用しています：

   • ティアA: すべての検証済み候補に対して解析型配置を実行し、HPWL、オーバーフロー、および収束のトレースを記録します。
   • ティアB: 選択された候補に対してタイミング・プロキシを適用し、WNS/TNSの改善を推定します。
   • ティアC: 高ポテンシャルの候補のサブセットに対して実際の配線ツールを実行し、配線後のワイヤ長、混雑度、およびタイミングを測定します。

   システムは、成功した候補を保存するためにMAP-Elitesアーカイブを使用します。各候補は、その複雑さ、メカニズムの系統、および挙動指標（HPWL、オーバーフロー、タイミング）に基づいた特徴セルにマッピングされます。アーカイブは、利用可能な指標に対するパレート優位性を用いて更新され、異なる挙動のニッチ間での多様性を維持します。負のメモリ（Negative memory）は、失敗した候補とその失敗理由を保存し、将来のプロンプトにおいてLLMが無効なメカニズムを繰り返すことを防ぎます。

主な貢献
本論文は、4つの新しい貢献を主張しています：

• LLMによる目的関数の進化: 静的な、あるいは人間が設計した項を超え、実際の配置および配線ツールと統合された、解析型配置目的関数を自動的に進化させる初のフレームワークです。
• 自動検証: 制限付きインターフェースにより、LLMが生成した目的関数が、DREAMPlaceのような解析型配置フロー内で微分可能、有界、かつ実行可能であることを保証します。
• 配線認識フィードバック: 探索は、ダウンストリームの配線およびタイミングのフィードバックによって導かれ、これにより目的関数が配置段階のサロゲートだけでなく、実際の配線品質に適応できるようになります。
• アーカイブ誘導型イテレーション: システムは、測定されたフィードバック（配置、配線、タイミング、および失敗データ）と対になった目的関数のアーカイブを保持し、この履歴を使用して将来のLLMプロンプトを条件付け、多様で高性能な解への進化を導きます。

実験結果
本フレームワークは、3つのランダムシードを用いて、8つのChiPBench Nangate45設計および8つのICCAD 2015 Superblue設計に対して評価されました。

• ChiPBench Nangate45: ネイティブのDREAMPlaceと比較して、CoEvoP&Rは配線後のワイヤ長を16.9%削減し、混雑度を36.7%削減しました。また、タイミング面では、WNSで0.70 ns、TNSで912 nsの改善を実現しました。これらの結果は、ワイヤ長に関しては競争力のある値を維持しつつ、混雑度とタイミングの面で他の自動探索手法（EvoPlace、AutoDMPなど）や学習されたサロゲート（LaMPlace）を上回りました。
• ICCAD 2015 Superblue: 本フレームワークは、ベースラインに対して配線後のワイヤ長を5.4%、混雑度を23.2%削減しました。
• 汎用性: Nangate45で進化させた目的関数を、再進化なしでSuperblueおよびASAP7の設計に適用するゼロショット転移実験（CoEvoP&R-T）では、プラスの効果が示され、進化された目的関数が汎用的な設計原理を捉えていることが示唆されました。
• アブレーション研究: 実験により、アーカイブ条件付きのイテレーションとコストスケール評価の階層構造が極めて重要であることが確認されました。アーカイブを削除したり、ティアA（配置のみ）の評価のみを使用したりすると、性能が著しく低下しました。

意義
本論文は、CoEvoP&Rを、微分可能な配置とダウンストリームの物理設計フローとのインターフェースを、検査可能かつ自動化されたものにするための重要なステップとして位置付けています。ブラックボックスモデルではなく、読み取り可能な記号的目的関数を進化させることで、本手法は、PPA（電力、性能、面積）指標を最適化しつつ、産業用EDAフローに求められるデバッグ可能性と統合能力を損なわない道筋を提供します。著者らは、このアプローチが、物理法則やツールの要件によって制約された複雑なエンジニアリング目的を最適化するための、LLMによるプログラム進化の有効な手法であることを実証していると述べています。