フロアプラン（マイクロエレクトロニクス）

電子設計自動化において、集積回路のフロアプランは、チップ領域上の主要な機能ブロックの概略的な配置と、アスペクト比やコア使用率などの高レベルのパラメータの仕様から構成されます。^[1]

フロアプランを作成する設計ステップはフロアプランニングと呼ばれ、集積回路設計の設計フローの初期段階です。^[1]

この問題については様々な数学的抽象化が研究されてきた。^[2]

フロアプラン設計段階

フロアプラン設計段階は、タイミングがクリーンな配線を可能にし、チップ全体に電力消費を分散させるフロアプランを見つけることを目的としたさまざまなステップで構成されています。

チップ面積の見積り：チップ面積の寸法とアスペクト比を決定します。見積りでは、マクロ、スタンダードセル、I/Oポートを配置するために必要なスペースを考慮しつつ、配置配線設計フローを成功させるために必要な配線リソースのためのスペースも確保します。通常、コア使用率は60%～70%を目標とします。^[3] $U={\frac {A_{マクロ}+A_{std\_cells}}{A_{コア}}}$

I/Oパッドの配置：入出力パッドは通常、チップの周辺部に配置する必要があります。遅延と信号劣化を最小限に抑えるため、I/Oパッドの近くにはラインドライバ用のスペースを確保する必要があります。^[4]
マクロ配置：マクロ配置では、メモリアレイ、クロックジェネレータ、カスタムコンポーネントなど、固定サイズと固定ピンを持つ大規模な機能ブロックをフロアプランのアウトライン内に配置する必要があります。効果的なマクロ配置は、タイミングクリティカルパスの長さを最小限に抑え、配線の混雑を回避し、熱バランスを確保します。^[4]
スタンダードセル列の作成：スタンダードセルを配置する領域が決定され、スタンダードセル列に分割されます。配置段階では、スタンダードセルは複数列の高さを持つ場合でも、スタンダードセル列に合わせて配置されます^[5]。スタンダードセル列の高さは、1列あたりの利用可能な配線リソースを決定し、消費電力にも影響を与えます^{[6] 。}

電源/グランド構造：電源/グランドネットワークの構築は、必ずしもフロアプランニング段階に含まれるわけではありません。しかしながら、マクロとI/Oパッドが固定されていれば電源グリッド解析が可能になるという考えに基づき、フロアプランとP/Gネットワークを共合成するアプローチがあります。 ^[7]

数学モデルと最適化問題

数学において、フロアプランニングとは、固定または不固定の向きを持つ小さな長方形を、大きな長方形に詰め込む問題を指します。大きな長方形と小さな長方形の寸法は、固定されている場合（ハード制約）と、最適化が必要な場合（ソフト制約）があります。さらに、フロアプランによって許容される配線の品質をモデル化する尺度を最適化することもできます。

長方形パッキングの様々なバリエーションは NP困難であるため、一般的なフロアプランニング問題に対する多項式時間アルゴリズムの存在は、を意味する。^[8] $P=NP$

整数計画法
固定サイズと固定方向の長方形パッキング問題は、整数線形計画法としてモデル化できます。さらに、制約条件と変数を追加して、バウンディングボックスのネット長を最小化することもできます。幅、高さ、ネット長の小さな長方形と、幅と高さの大きな長方形が与えられた場合、整数計画法は次のようになります。 $R_{1},...R_{n}$ $w_{1},...,w_{n}$ $h_{1},...,h_{n}$ ${\mathcal {N}}_{1},...,{\mathcal {N}}_{n}$ $W$ $H$

境界ボックスのネット長を最小化する目的

\min \sum _{N\in \cup _{i=1}^{n}{\mathcal {N}}_{i}}y_{N,t}-y_{N,b}+x_{N,r}-x_{N,l}

重複しない制約

{\begin{matrix}x_{i}+w_{i}\leq x_{j}+W(1-R_{j,i})\\y_{i}+h_{i}\leq y_{j}+H(1-A_{j,i})\end{matrix}}\quad \forall \ 1\leq i\neq j\leq n

相対配置の分離

R_{j,i}+R_{i,j}+A_{j,i}+A_{i,j}\geq 1\quad \forall \ 1\leq i\neq j\leq n

ネット境界ボックスのカバレッジ制約

{\begin{matrix}x_{N,r}\geq x_{i}+w_{i}\\x_{N,l}\leq x_{i}\\y_{N,t}\geq y_{i}+h_{i}\\y_{N,b}\leq y_{i}\end{matrix}}\quad \forall \ i\in {1,\ldots ,n},\ N\in {\mathcal {N}}_{i}

バイナリ変数

{\begin{matrix}R_{i,j}\in {0,1}\\A_{i,j}\in {0,1}\end{matrix}}\quad \forall \ 1\leq i\neq j\leq n

長方形の位置変数

{\begin{matrix}x_{i}\in {0,\ldots ,W-w_{i}}\\y_{i}\in {0,\ldots ,H-h_{i}}\end{matrix}}\quad \forall \ i\in {1,\ldots ,n}

ネット境界ボックス変数

{\begin{matrix}x_{N,l},\ x_{N,r}\in {0,\ldots ,W}\\y_{N,b},\ y_{N,t}\in {0,\ldots ,H}\end{matrix}}\quad \forall N\in \cup _{i=1}^{n}{\mathcal {N}}_{i}

固定関係の場合、上記の整数計画問題は最大フロー問題の双対問題であり、したがって多項式時間で解くことができる。^[8] $R_{i,j},A_{i,j}$

これらの空間関係変数のすべての選択肢が、実現可能な配置に対応するわけではない。実現可能な配置をすべて含む関係集合は完全関係と呼ばれる。完全な関係集合の大きさに関する最もよく知られた上限は、シルヴァヌスとヴィゲンによって証明され、空間関係が十分であることを示した。彼らはまた、空間関係が十分であることを示した [ ^9]。 $O\left(n!\cdot C^{n}/n^{6}\right)$ $C=(11+5{\sqrt {5}})/{2}$ $O\left(n!\cdot c^{n}/n^{6}\right)$ $c=4+2{\sqrt {2}}.$

ヒューリスティック長方形間の空間関係を表現する
O木^[10] 、 B*木^[11]、シーケンスペア^{[12]などの様々な表現を用いて、フロアプランニングの実例を解決するための様々な}ヒューリスティックアルゴリズムが提案されている。これらのアルゴリズムの中には、スライス可能なフロアプランのみを考慮することで解空間を制限するものもある。

スライス可能なフロアプランとスライス不可能なフロアプラン

スライス可能なフロアプランとは、以下に説明するように再帰的に定義できるフロアプランである。^[13]

単一の長方形ブロックで構成されるフロアプランはスライス可能です。
スライス可能なフロアプランのブロックを垂直線または水平線で 2 つにカット (「スライス」) すると、結果として得られるフロアプランはスライス可能になります。

スライス可能なフロアプランは、初期の電子設計自動化ツール^[13]において、様々な理由から用いられてきました。スライス可能なフロアプランは、スライスの順序に対応する二分木（より具体的にはk -d木）で表現できるため、簡便です。さらに重要なのは、フロアプランに関するNP困難な問題の多くは、スライス可能なフロアプランに限定すれば多項式時間アルゴリズムが実現できることです。^[14]

スライス可能なフロアプラン
スライスできないフロアプラン

さらに読む

PLAYOUTシステムのチッププランナー
VLSI物理設計：グラフ分割からタイミングクロージャまで、Kahng、Lienig、Markov、Hu著、doi :10.1007/978-3-030-96415-3 ISBN 978-3-030-96414-6, 2022
電子回路レイアウト設計の基礎、Lienig、Scheible著、Springer、doi :10.1007/978-3-030-39284-0 ISBN 978-3-030-39284-0, 2020

参考文献

^ ab 「VLSI物理設計におけるフロアプラン」iVLSI Technologies . 2025年6月12日閲覧。
^ Kahng, Andrew B. (2000). 「古典的フロアプランニングは有害か？」. 2000年国際物理設計シンポジウム議事録. ISPD '00. 計算機協会. pp. 207– 213. doi :10.1145/332357.332401. ISBN 1-58113-191-7. 2025年6月12日閲覧。
^ Liu, Chen-Wei、Chang, Yao-Wen (2024-09-01). 「物理設計：方法論と開発」. arXiv : 2409.04726 [eess.SY].{{cite arXiv}}: CS1 maint: 複数の名前: 著者リスト (リンク)
^ ab VLSIPD4 (2023-04-23). 「物理設計におけるフロアプランニング」. Medium . 2025年6月6日閲覧。{{cite web}}: CS1 maint: 数値名: 著者リスト (リンク)
^ VLSI-Talks (2023年1月). 「FLOORPLAN - VLSI TALKS」. VLSI TALKS . 2025年6月12日閲覧。
^ Lin, Ruei-Bin; Chiang, Yi-Xiu (2019). ダブルロウハイトスタンダードセルの配置配線への影響. 第20回国際品質電子設計シンポジウム (ISQED). サンタクララ、カリフォルニア州、米国: IEEE. pp. 317– 322. doi :10.1109/ISQED.2019.8697712 . 2025年6月12日閲覧。
^ Liu, Chen-Wei; Chang, Yao-Wen (2006). フロアプランと電源／グラウンドネットワークの協調合成による高速設計収束．2006 International Symposium on Physical Design. ISPD '06. サンノゼ、カリフォルニア州、米国：Association for Computing Machinery. pp. 86– 93. doi :10.1145/1123008.1123026 . 2025年6月12日閲覧。
^ ab Funke, Julia; Hougardy, Stefan; Schneider, Jan (2016). 「VLSI設計における配線長最適配置のための正確なアルゴリズム」. Integration: The VLSI Journal . 52 : 355–366 . doi :10.1016/j.vlsi.2015.07.001 . 2025年6月12日閲覧。
^ Silvanus, Jannik; Vygen, Jens (2017). 「Few Sequence Pairs Suffice: Representing All Rectangle Placements」. SIAM Journal on Discrete Mathematics . 34 : 2017–2032 . doi :10.1137/16M1095880 (2025年7月1日非アクティブ).{{cite journal}}: CS1 maint: DOIは2025年7月時点で非アクティブです（リンク）
^ Tang, M.; Sebastian, A. (2005). 「O-Tree表現を用いたVLSIフロアプランニングのための遺伝的アルゴリズム」.進化的コンピューティングの応用. コンピュータサイエンス講義ノート. 第3449巻. Springer Berlin Heidelberg. pp. 215– 224. doi :10.1007/978-3-540-32003-6_22.
^ Fernando, J.; Katkoori, S. (2008). 「VLSIフロアプランニングにおける面積と配線長の同時最小化のためのエリート主義的非支配ソートに基づく遺伝的アルゴリズム」.第21回国際VLSI設計会議議事録. IEEE. pp. 337– 342. doi :10.1109/VLSI.2008.56.
^ Lin, P.-H.; Chang, Y.-W.; Lin, S.-C. (2009). 「対称島定式化に基づくアナログ配置」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 28 (6). IEEE: 791– 804. doi :10.1109/TCAD.2009.2015708 (2025年7月1日非アクティブ).{{cite journal}}: CS1 maint: DOIは2025年7月時点で非アクティブです（リンク）
^ ab 「電気工学ハンドブック」リチャード・C・ドーフ（1997年）ISBN 0-8493-8574-1
^ Sarrafzadeh, M、「任意のフロアプランをスライス可能なフロアプランに変換する」、Proc. 1993 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-93)、pp. 386-389。

[ivlsi-floorplan-1] 「VLSI物理設計におけるフロアプラン」iVLSI Technologies . 2025年6月12日閲覧。

[Kahng2000-2] Kahng, Andrew B. (2000). 「古典的フロアプランニングは有害か？」. 2000年国際物理設計シンポジウム議事録. ISPD '00. 計算機協会. pp. 207– 213. doi :10.1145/332357.332401. ISBN 1-58113-191-7. 2025年6月12日閲覧。

[arXivCoreUtil-3] Liu, Chen-Wei、Chang, Yao-Wen (2024-09-01). 「物理設計：方法論と開発」. arXiv : 2409.04726 [eess.SY].{{cite arXiv}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[VLSIPD_Floorplanning-4] VLSIPD4 (2023-04-23). 「物理設計におけるフロアプランニング」. Medium . 2025年6月6日閲覧。{{cite web}}: CS1 maint: 数値名: 著者リスト (リンク)

[VlsitalksRows-5] VLSI-Talks (2023年1月). 「FLOORPLAN - VLSI TALKS」. VLSI TALKS . 2025年6月12日閲覧。

[LinChiang2019-6] Lin, Ruei-Bin; Chiang, Yi-Xiu (2019). ダブルロウハイトスタンダードセルの配置配線への影響. 第20回国際品質電子設計シンポジウム (ISQED). サンタクララ、カリフォルニア州、米国: IEEE. pp. 317– 322. doi :10.1109/ISQED.2019.8697712 . 2025年6月12日閲覧。

[LiuChang2006-7] Liu, Chen-Wei; Chang, Yao-Wen (2006). フロアプランと電源／グラウンドネットワークの協調合成による高速設計収束．2006 International Symposium on Physical Design. ISPD '06. サンノゼ、カリフォルニア州、米国：Association for Computing Machinery. pp. 86– 93. doi :10.1145/1123008.1123026 . 2025年6月12日閲覧。

[Funke2016-8] Funke, Julia; Hougardy, Stefan; Schneider, Jan (2016). 「VLSI設計における配線長最適配置のための正確なアルゴリズム」. Integration: The VLSI Journal . 52 : 355–366 . doi :10.1016/j.vlsi.2015.07.001 . 2025年6月12日閲覧。

[Silvanus2017-9] Silvanus, Jannik; Vygen, Jens (2017). 「Few Sequence Pairs Suffice: Representing All Rectangle Placements」. SIAM Journal on Discrete Mathematics . 34 : 2017–2032 . doi :10.1137/16M1095880 (2025年7月1日非アクティブ).{{cite journal}}: CS1 maint: DOIは2025年7月時点で非アクティブです（リンク）

[Tang2005-10] Tang, M.; Sebastian, A. (2005). 「O-Tree表現を用いたVLSIフロアプランニングのための遺伝的アルゴリズム」.進化的コンピューティングの応用. コンピュータサイエンス講義ノート. 第3449巻. Springer Berlin Heidelberg. pp. 215– 224. doi :10.1007/978-3-540-32003-6_22.

[Fernando2008-11] Fernando, J.; Katkoori, S. (2008). 「VLSIフロアプランニングにおける面積と配線長の同時最小化のためのエリート主義的非支配ソートに基づく遺伝的アルゴリズム」.第21回国際VLSI設計会議議事録. IEEE. pp. 337– 342. doi :10.1109/VLSI.2008.56.

[Lin2009-12] Lin, P.-H.; Chang, Y.-W.; Lin, S.-C. (2009). 「対称島定式化に基づくアナログ配置」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 28 (6). IEEE: 791– 804. doi :10.1109/TCAD.2009.2015708 (2025年7月1日非アクティブ).{{cite journal}}: CS1 maint: DOIは2025年7月時点で非アクティブです（リンク）

[dorf-13] 「電気工学ハンドブック」リチャード・C・ドーフ（1997年）ISBN 0-8493-8574-1

[14] Sarrafzadeh, M、「任意のフロアプランをスライス可能なフロアプランに変換する」、Proc. 1993 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-93)、pp. 386-389。