論理合成と最適化（テクノロジマッピング）

論理合成は「2段の変換」である

RTL（レジスタ転送レベルの記述）からゲートのネットリストを人手で書き起こすのは、数億ゲート規模では不可能です。論理合成（logic synthesis） はこの変換を自動化する工程で、デジタル設計フロー（/semiconductor/asic-design-flow/）の入口に位置します。重要なのは、合成が単一の処理ではなく 2つの段 に明確に分かれていることです。

第一段は 技術非依存の最適化（technology-independent optimization） です。RTL を AND/OR/NOT のような抽象的なブール論理網に落とし、特定のセルライブラリやプロセスを一切意識せずに、論理そのものを簡約します。第二段が テクノロジマッピング（technology mapping） で、簡約済みの抽象論理を、ファウンドリが提供する 標準セルライブラリ の実セル（具体的な遅延・面積・電力の値を持つ）へ写像します。前半は「論理を小さく良くする」、後半は「良くした論理を現実の部品に割り当てる」── 役割が異なるため分離します。

技術非依存の最適化 ── ブール簡約と構造化

第一段の目的は、論理を表す中間表現（多くは AIG, And-Inverter Graph などの2入力グラフ）を、機能を保ったまま小さく・浅くすることです。代表的な操作は次の3系統です。

• 冗長性除去（redundancy removal）: 出力に影響しない論理や、恒等的に決まる信号を削る。たとえば常に同じ値を取るノードは定数へ畳み込む。
• 因数分解と分配（factoring）: 積和形を共通項でくくり、リテラル数（信号の出現回数）を減らす。ab+ac を a(b+c) にする操作がこれで、面積に直結するリテラル数が減る。
• 構造化と再構築（restructuring）: 論理網のトポロジを組み替える。共通部分式を抽出して1か所に集約する 抽出・構造化（extraction / structuring） と、逆に共有や深い段を一度ほどいてから組み直す 崩し・再分解（collapse & re-decompose） を、目的（面積優先か遅延優先か）に応じて使い分ける。既存ノードを除数として他ノードの式を書き換える 再代入（resubstitution） も、共有を増やして面積を削る代表的な手筋。

これらは機能等価を保つ変換であり、各ステップで形式的に等価性が保証されます。面積を狙うなら共有を増やしてリテラル数を最小化し、遅延を狙うなら論理段数（クリティカルパス上のレベル数）を浅くする ── 同じ論理でも、どちらを重視するかで全く違う構造に収束します。

テクノロジマッピング ── 被覆問題として解く

簡約済みの抽象論理を実セルへ割り当てるのがマッピングです。これは 被覆（covering）問題 として定式化されます。抽象論理網を DAG（有向非巡回グラフ） とみなし、ライブラリの各セルが表現できる小さな論理パターン（マッチ）でグラフ全体を重なりなく覆い、被覆全体のコスト（面積や遅延の総和）を最小化します。

テクノロジマッピングの骨子

  入力 : 技術非依存の論理DAG（2入力プリミティブで正規化済み）
         標準セルライブラリ（各セルのパターン・遅延・面積・電力）

  手順 :
    1. マッチング  各ノードを根とする部分グラフに、
                   どのライブラリセルが合致するか列挙する
    2. 被覆        DAG全体をマッチの集合で覆い、
                   コスト最小の被覆を動的計画法で選ぶ

  コスト : 面積モード … 被覆に使うセル面積の総和
           遅延モード … 各ノードでの到着時刻 = 入力到着 + セル遅延
                         の最大値（クリティカルパス）を最小化

木に分解すれば動的計画法で最適被覆が多項式時間で求まりますが、実際の論理は再収束（信号が分岐して再合流する）を含む DAG なので、厳密最適は NP 困難になります。実装では DAG を木の集合に切り出して各木で最適被覆を解き、それを貼り合わせるヒューリスティックが用いられます。ここで初めて実セルの物理値が効きます ── 同じ論理でも、ライブラリにどんな複合セル（AOI/OAI など）があるか、各セルの遅延・面積・電力がいくつかによって、選ばれる被覆が変わります。

制約駆動の最適化 ── 面積・遅延・電力のトレードオフ

合成は無目的に小さくするのではなく、設計者が与える 制約（constraints） に従って最適化します。中心となるのはクロック周期（目標周波数）、入出力の到着・要求時刻、駆動するセルの負荷、最大トランジション時間などです。合成器はこれらを満たすことを最優先に、満たした上で面積や電力を削ります。

代表的な調整手段は次の通りです。

電力には2成分があります。動的電力 はスイッチング時の充放電で生じ（クロックゲーティングやトグル率の低減で削る）、漏れ電力（リーク） は静止時にも流れます。低 Vt セルは速い反面リークが大きいため、合成器は クリティカルパスにだけ低 Vt を使い、余裕のあるパスは高 Vt のまま残す という配り方をします。これは多 Vt（multi-Vt）最適化と呼ばれ、リーク支配のプロセスでパワーウォール（/semiconductor/power-wall/）と戦う基本手筋です。

リタイミング ── レジスタを動かして周期を縮める

ここまでは組み合わせ論理の最適化でしたが、リタイミング（retiming） はフリップフロップ（FF）の位置そのものを動かす、より大域的な最適化です。原理は単純で、機能を保ったまま FF を論理境界を越えて前後に移動させ、段間の遅延を均す ことでクリティカルパスを縮めます。

たとえば、ある FF の手前（入力側）に重い論理が、後ろ（出力側）に軽い論理が偏っているとき、FF を入力側へ少し動かせば手前の重い論理の一部が FF の後ろ（次段）へ移り、最長段が短くなります。FF の出力側にある全パスから FF を1つずつ取り去って入力側へまとめて足す（あるいはその逆）操作は、論理の機能を変えずにレイテンシ分布だけを組み替えるため、周波数を底上げできます。

リタイミングの直観

  改善前 :  IN ─[重い論理 5ns]─ FF ─[軽い論理 1ns]─ OUT
            最長段 = 5ns  →  周期は 5ns 以上必要

  FF を境界を越えて前へ移動（機能等価を保つ）

  改善後 :  IN ─[論理 3ns]─ FF ─[論理 3ns]─ OUT
            最長段 = 3ns  →  周期 3ns まで詰められる

  ※ FFの総数や入出力の機能は変えない。各サイクル境界の
    位置だけを動かして段ごとの遅延を均等化する。

リタイミングは FF の数を増やさずに（時に減らして）周期を縮められる強力な手段ですが、制約があります。FF を動かすと内部信号の意味が変わるため、デバッグ用のスキャンや初期値リセットの扱いが複雑化し、形式検証で等価性を別途保証する必要があります。

物理合成 ── 配線の現実を合成へ取り込む

古典的な論理合成は配線を知りません。被覆の遅延計算で「セルからセルへ信号が伝わる時間」を見積もる際、配線長がまだ決まっていないため、扇出数から負荷を推定する ワイヤロードモデル に頼ります。微細プロセスでは配線の RC 遅延（/semiconductor/interconnect-rc-delay/）がゲート遅延に匹敵するほど大きくなり、この推定が外れると、合成では合格していたパスが配置配線後に制約を割る ── いわゆる タイミングクロージャの破綻 が起きます。

物理合成（physical synthesis） はこの予測ずれを潰すために、合成と配置を融合します。論理合成の途中で粗い配置を行い、実際のセル座標から配線長と RC を見積もって、その負荷を被覆・セルサイジング・バッファ挿入へ反映します。配線が長いと分かれば、論理段階でバッファを挿し、駆動力の大きいセルへ置き換え、必要なら論理を複製して経路を短くします。

まとめ

• 論理合成は 技術非依存のブール最適化（冗長性除去・因数分解・構造化でリテラル数と論理段数を削る）と テクノロジマッピング（実セルへの割り当て）の2段からなり、前者は論理を理想化して小さくし、後者で現実のライブラリへ落とす。
• テクノロジマッピングは論理 DAG をライブラリセルのパターンで覆う 被覆問題 で、面積モードはセル面積総和、遅延モードは到着時刻の最大値を最小化する。実セルの物理値がここで初めて効く。
• 最適化は 制約駆動 で、クロック周期や負荷の制約を満たした上で面積・電力を削る。セルサイジング・バッファ挿入・論理複製・多 Vt 配分・クロックゲーティングを使い分け、面積/遅延/電力のトレードオフを取る。
• リタイミング は FF を機能等価のまま移動して段遅延を均し周期を縮める直交手段、物理合成 は配置情報を合成へ取り込みワイヤロードモデルの誤差を潰してタイミングクロージャを守る。