配置配線（Place & Route）の原理とアルゴリズム

配置配線は「巨大な最適化問題」である

論理合成が出力するのは、どのセルがどう繋がるかというネットリストだけで、各セルがチップ上のどこに置かれ、配線がどの層をどう通るかはまだ何も決まっていません。配置配線（P&R, Place and Route）は、この論理を物理座標へ写像する工程であり、その実体は数億変数の組合せ最適化です。目的関数は配線長・タイミング・消費電力・配線混雑であり、制約は重なり禁止・配線可能性・設計ルールです。人手で数億セルを並べることは不可能で、なぜ自動化できるかは「問題を解ける形に定式化し、近似アルゴリズムで段階的に解く」点に尽きます。論理から物理へ至る全体像は/semiconductor/asic-design-flow/を前提とします。

P&Rの主要ステージ（上流→下流）:

  フロアプラン → 配置(Placement) → クロックツリー合成(CTS)
    → 配線(Routing: グローバル→詳細) → 寄生抽出 → STA
    → タイミング/DRC違反のECO修正 → サインオフ

配置 ── 解析配置による2段最適化

配置の目標は、総配線長を最小化しつつセルを重ねず、かつ過密領域を作らないことです。総配線長の代表的近似が**HPWL（Half-Perimeter Wire Length、各ネットを囲む最小矩形の半周長の総和）**で、これを目的関数に取ります。

かつては焼きなまし法で離散的に動かしていましたが、数億セル規模では現実的でなく、現在は解析配置（Analytical Placement）が主流です。発想は、ネットの接続を仮想バネとみなし、バネが縮もうとする力の釣り合い点を求めることです。配線長を各セル座標の2乗で近似すると、目的関数は凸2次形式になり、力の釣り合い（勾配ゼロ）は連立1次方程式に帰着します。

2次配置の構造:

  目的: Σ (接続セル間距離)^2 を最小化  ← 凸2次関数
  最小条件: 各座標で偏微分=0 → 疎な線形システム Q x = b
  解法: 共役勾配法など反復ソルバ（行列Qは疎・対称正定値）

この素朴な2次配置だけでは、全セルが少数の重心へ吸い寄せられ、中央が極端に過密になります。配置可能性を確保するには、過密を解消する仕組みが要ります。

解析配置で得るのは連続座標の概形（グローバル配置）です。最後に詳細配置で、セルを標準セル行（row）のトラックへスナップし、隙間を詰め、局所入れ替えで残る重なりとはみ出しを解消して合法化（legalization）します。

タイミング駆動とは ── 配線長最小では足りない

総配線長を最小化しても、遅い経路（クリティカルパス）上のネットが長ければタイミングは破綻します。そこでタイミングに効くネットの仮想バネを重くし、優先的に短く保つのがタイミング駆動配置です。STAが各ネットの余裕（スラック）を返し、負スラックのネットほど重み付けを上げる、という連携で動きます。STAの原理は/semiconductor/static-timing-analysis/を参照してください。

配線 ── グローバルと詳細の2段構成

配置が終わると、ネットの端子を実際のメタル配線で繋ぎます。チップ全体を一気に最短経路で配ろうとすると探索空間が爆発するため、配線は計算量を抑える2段構成を取ります。

まずグローバル配線で、チップをGCell（格子状のタイル）に分割し、各ネットがどのGCell列を、おおよそ何層目を通るかを粗く決めます。ここで各GCell境界の**容量（通せる配線本数）**を超えないよう経路を割り当て、混雑（congestion）を均します。容量超過は詳細配線で物理的に通せないことを意味するため、この段で混雑マップを見て解消するのが要点です。

次に詳細配線で、グローバルの大枠に従い、各層のトラック上に実際の配線パターンと、層間を繋ぐビアを敷きます。最小線幅・最小間隔といった設計ルール（DRC）をここで満たします。

配線の2段構成:

  グローバル配線: GCell格子で経路と層を粗割り当て（容量・混雑が主目的）
        ↓ 大枠を渡す
  詳細配線: トラック上に実配線とビアを敷き、DRCを満たす

ルーティングの基盤 ── 最短路グラフ探索

配線アルゴリズムの土台はグラフ上の最短路探索です。配線可能な格子点をノード、隣接移動をエッジとし、端子間の最小コスト経路を求めます。古典は**Lee法（迷路法）**で、始点から幅優先で波を広げ各格子に距離ラベルを振り、終点から逆にたどって経路を確定します。確実に最短路を見つけますが、探索が全方位に広がり遅い。

実用ソルバはA*（ゴール方向のヒューリスティックで探索を絞る）を用い、層・ビア・混雑をエッジコストに織り込みます。多端子ネットは最短路の繰り返しでは最適にならず、シュタイナー木（端子以外の分岐点を許す最小木）の近似で配ります。

レイヤ割り当て ── 太い層・細い層の使い分け

多層配線（BEOL）は層ごとに線幅・厚み・抵抗が異なります。下層（M1付近）は細く抵抗が高く短距離向き、上層は太く低抵抗・低容量で長距離やクロック・電源向きです。配線の遅延は抵抗と容量の積（RC遅延）に支配されるため、長く速度が要るネットを上層へ上げると遅延を抑えられます。原理は/semiconductor/interconnect-rc-delay/を参照してください。一方、上層へ上げるにはビアを積む必要があり、ビアは抵抗源かつ信頼性の弱点です。大電流を流す電源・クロックでは、配線幅とビア本数がエレクトロマイグレーション寿命を左右し、/semiconductor/electromigration-beol-limits/で扱う電流密度上限が層・幅の選択を縛ります。

タイミング収束とECO ── 局所修正で締める

配線が終わって初めて、実際の配線形状から**寄生抵抗・容量を抽出（RC抽出）**でき、遅延の実値が確定します。配置段の見積りは概算なので、抽出後のSTAでは必ずスラックがずれ、新たな違反が出ます。ここで全体を作り直すのは非現実的なので、**ECO（Engineering Change Order）**で局所修正します。

タイミング収束ループ:

  詳細配線 → RC抽出 → サインオフSTA
    → 違反パスを抽出（負スラック）
    → ECO: バッファ挿入 / セルのサイズ調整 / ゲート複製 / 配置微調整
    → 影響範囲だけ再配線・再抽出・再STA
    → 違反ゼロ（全コーナーでスラック非負）まで反復

最終的に、全パスのスラックが全モード・全コーナーで非負（例 余裕 0ns未満が一つもない）になり、DRC・LVSも通って初めてサインオフです。タイミング収束は単独では完結せず、消費電力や電源網の電圧降下との綱引き（/semiconductor/power-wall/）も同時に満たす多目的最適化として閉じます。

まとめ

• 配置配線は論理を物理座標へ写す数億変数の最適化問題で、目的関数は配線長・タイミング・混雑、制約は重なり禁止・配線可能性・DRCである。
• 現代の配置は解析配置が主流で、凸2次形式を疎な線形システムとして解く段と、過密をペナルティ項で散らす密度均しの段を交互反復して合法化する。
• 配線はグローバル（GCell格子で粗割り当て・混雑解消）と詳細（トラックに実配線とビア）の2段構成で、基盤は最短路グラフ探索（Lee法・A*）とリップアップ＆リルートである。
• レイヤ割り当ては層ごとのRC特性とビア制約・電流密度上限を踏まえ、長く速いネットを上層へ上げる判断である。
• 配線後のRC抽出で初めて遅延が確定し、残る違反は全体再設計せずECOで局所修正して、全コーナーでスラック非負へ収束させる。