配置（電子設計自動化）

配置は、電子設計自動化における重要なステップです 。これは、チップのコア領域内のさまざまな回路コンポーネントの正確な位置を割り当てる物理設計フローの一部です。配置割り当てが不十分だと、チップのパフォーマンスに影響するだけでなく、配線リソースを超える過剰な配線長が生成されて製造不能になる可能性もあります。したがって、配置者は、回路がパフォーマンス要件を満たすように、いくつかの目標を最適化しながら割り当てを実行する必要があります。IC 設計の配置ステップと配線ステップを合わせて、配置と配線と呼びます。

配置ツールは、与えられた合成回路ネットリストとテクノロジ ライブラリを一緒に受け取り、有効な配置レイアウトを生成します。レイアウトは前述の目的に従って最適化され、セルのサイズ変更とバッファリングの準備が整います。これは、タイミングと信号の整合性を満たすために不可欠なステップです。次にクロック ツリー合成と配線が行われ、物理設計プロセスが完了します。多くの場合、物理設計フローの一部または全体が、設計が完了するまで何度も繰り返されます。

特定用途向け集積回路（ASIC）の場合、チップのコアレイアウト領域は、高さが固定された多数の行で構成され、行間にはスペースが多少あるか、またはスペースがありません。各行は、回路部品が占有できる多数のサイトで構成されています。空きサイトとは、どの部品も占有していないサイトです。回路部品は、標準セル、マクロブロック、またはI/Oパッドのいずれかです。^[1] 標準セルの高さは行の高さに等しく固定されていますが、幅は可変です。セルの幅はサイトの整数倍です。

一方、ブロックは一般的にセルよりも大きく、高さが可変で、複数の行にまたがることができます。^[1]一部のブロックには、たとえば以前のフロアプランニングプロセスから事前に割り当てられた位置があり、配置者のタスクはセルの位置のみの割り当てに制限されます。この場合、ブロックは通常、固定ブロックによって参照されます。または、一部またはすべてのブロックに事前に割り当てられた位置がない場合があります。この場合、ブロックは一般に混合モード配置と呼ばれる方法でセルと一緒に配置する必要があります。

ASIC に加えて、フィールドプログラマブルゲートアレイ(FPGA) などのゲートアレイ構造でも配置は依然として非常に重要です。ここでは、事前に製造されたトランジスタが通常、ルーティングチャネルによって分離された行 (または「アレイ」) に配置されます。^[2]配置は、回路のサブ回路をプログラム可能な FPGA ロジックブロックにマッピングし、後続のルーティング段階の完了を保証します。

配置は、制約付き最適化として定式化されます。特に、チップのクロックサイクルは、通常クリティカル パスと呼ばれる最長パスの遅延によって決まります。パフォーマンス仕様が与えられた場合、配置者は、指定された最大遅延を超える遅延を持つパスが存在しないようにする必要があります。

その他の主な制約としては、

• 回路コンポーネント（ネットリスト内のインスタンス）間の重複を避ける
• 回路部品を所定の「場所」に配置する

通常、最適化の目標は複数あり、次のようなものがあります。

• 総配線長: 設計内のすべての配線の長さの合計
• ルーティングの混雑: ローカル混雑は、領域内のワイヤの長さとその領域で使用可能なルーティング トラックの長さの差です。ローカル値は、上位 10% の最大値を追加するなど、いくつかの方法で集計できます。
• 電力: 動的スイッチング電力はワイヤの長さに依存し、ワイヤの長さはコンポーネントの位置に依存します。

さらに、配置プロセスを迅速に完了することが望ましいです。

総配線長は、通常、ほとんどの既存の配置ツールの主な目的であり、電力や遅延が配線長とともに増加する傾向があるため、他の最適化の前段階として機能します。総配線長によって、配線需要と、利用可能な配線トラックによって定義される配線供給でそれを満たすことができるかどうかが決まります。ただし、配線を非常に短くすると、ローカル配線需要がローカル配線供給を上回ることがあります。このような状況では、配線の迂回が必要になることが多く、配線長と信号遅延が増加します。したがって、総配線長を事前に最適化した後は、配線の混雑に対処することも重要です。

電力の最小化では、通常、スイッチング アクティビティ係数が大きい配線に注目し、それらの配線を短くすることを優先します。多くの「ホット」コンポーネントが近くに配置されている場合、ホット スポットが発生し、有害な温度勾配が発生する可能性があります。このような場合は、コンポーネントを分散させることができます。

配置は、グローバル配置と詳細配置に分かれています。グローバル配置では、すべてのインスタンスをグローバル スケールの適切な場所に分散し、わずかな重複を許容することで劇的な変化をもたらします。詳細配置では、各インスタンスを近くの適切な場所に移動し、レイアウトをわずかに変更します。配置と全体的な設計品質は、グローバル配置のパフォーマンスに最も依存します。

集積回路の配置に関する初期の技術は、組み合わせ最適化に分類できます。数千または数万のコンポーネントを持つIC設計の場合、 TimberWolf ^[4]などのシミュレーテッドアニーリング^[3]手法が最良の結果を示します。IC設計が数百万のコンポーネントにまで拡大すると、配置ではCapo ^[6 ]などのネストされたパーティションフレームワークを使用したハイパーグラフパーティション^[5]が活用されました。組み合わせ法はコンポーネントの重複を直接防ぎますが、大規模な相互接続の最適化は困難です。これらは通常確率的であり、複数回実行すると、同じ入力に対して非常に異なる結果を生成する可能性があります。

グローバル配置の解析手法では、相互接続長を連続関数でモデル化し、コンポーネント密度の制約を直接受けてこの関数を最小化します。これらの手法は、組み合わせ手法よりも高速で拡張性に優れていますが、コンポーネントの重複を防ぐことはできず、詳細な配置のために組み合わせ手法で後処理する必要があります。 二次配置は、相互接続長を二次関数でモデル化し、高性能な二次最適化手法を使用する初期の解析手法です。開発された当時、組み合わせ手法とは異なり、競争力のある結果品質と安定性を示しました。GORDIAN ^{[7] は}、再帰分割によってセルを分散させながら、配線長コストを二次関数として定式化します。アルゴリズム^[8]は、配置密度を二次コスト関数の線形項としてモデル化し、純粋な二次計画法によって配置問題を解決します。一般的な拡張機能は、各ネットを前回の反復での長さの逆数で重み付けすることです。プロセスが収束する場合、これにより配線長の目的線形が最小化されます。 ^[9]現代の二次方程式配置システムの大多数（KraftWerk、^[10] FastPlace、^[11] SimPL ^[12]）はこのフレームワークに従っており、それぞれ線密度力を決定する方法について異なるヒューリスティックを持っています。

非線形配置モデルでは、配線長を指数関数（非線形）で、密度を局所的な区分的二次関数でモデル化することで、精度を向上させ、品質を向上させます。^[13]その後の学術研究には、APlace ^[14]とNTUplace ^{[15]があります。}

ePlace ^[16]は最先端のグローバル配置アルゴリズムです。静電場をシミュレートすることでインスタンスを分散させ、品質のオーバーヘッドを最小限に抑えて優れたパフォーマンスを実現します。

2021年、Google Brainは配置問題に対するAI技術（特に強化学習）の使用から良好な結果が得られたことを報告しました。^[17] しかし、この結果は非常に物議を醸しています。^{[18] [19] [20]}この論文には既存の配置者との直接比較が含まれていないこと、独自のコンテンツのため再現が難しいことなどです。少なくとも1つの当初好意的なコメントは、さらなるレビューにより撤回されました。^[21]

• 電子設計自動化
• 設計フロー（EDA）
• 集積回路設計
• フロアプラン（マイクロエレクトロニクス）
• 場所とルート

• IEEE コンピュータ支援集積回路およびシステム設計(TCAD)トランザクション
• ACM 電子システムの設計自動化トランザクション (TODAES)
• IEEE 大規模統合システム (TVLSI) トランザクション