ルーティング（電子設計自動化）

電子設計 において、配線（一般的には単に配線とも呼ばれる）は、プリント回路基板（PCB）および集積回路（IC）の設計におけるステップです。配線は、ICの各能動素子またはコンポーネントのPCB上の位置を決定する配置と呼ばれる先行ステップに基づいて行われます。配置の後、配線ステップでは、ICのすべての設計ルールに従いながら、配置されたコンポーネントを適切に接続するために必要な配線を追加します。IC設計における配置ステップと配線ステップは、合わせて配置配線と呼ばれます。

すべてのルーターのタスクは同じです。ルーターには、セル上のピン (端子とも呼ばれる) で構成される既存のポリゴン、配線できない障害物、およびオプションでプレルートと呼ばれる既存の配線が与えられます。各ピンは、通常名前または番号でネットに関連付けられます。ルーターの主なタスクは、同じネットに割り当てられたすべての端子が接続され、異なるネットに割り当てられた端子は接続されず、すべての設計ルールが遵守されるようなジオメトリを作成することです。ルーターは、接続すべき端子を接続しない (オープン)、接続すべきでない 2 つの端子を誤って接続する (ショート)、または設計ルール違反を作成することで失敗する可能性があります。ネットを正しく接続することに加えて、ルーターには、設計がタイミングを満たしていること、クロストークの問題がないこと、金属密度の要件を満たしていること、アンテナ効果の影響を受けないことなどを確認することも求められる場合があります。この、しばしば矛盾する目的の長いリストが、ルーティングを非常に困難にしています。

ルーティングの複雑さ

配線に関連するほぼすべての問題は解決困難であることが知られています。最も単純な配線問題はシュタイナー木問題と呼ばれ、障害物や設計ルールのない1つの層にある1つのネットの最短経路を見つけるものですが、これはすべての角度が許容される場合と、配線が水平と垂直の配線のみに制限される場合の両方においてNP完全であることが知られています。 [ 1 ]チャネル配線 の変種もNP完全であることが示されています。 [ 2 ]クロストークやビア数などを削減する配線も同様です。配線問題がNP完全であることが証明される以前から、最適な解を見つけることの難しさは明らかでした。そのため、ほぼすべてのアルゴリズムはヒューリスティックに基づいています。ヒューリスティックは最適な解を求めるのではなく、「十分に良い」解を求めます。[ 3 ]

設計ルールは層ごとに大きく異なることがあります。例えば、複数の金属層を持つ集積回路では、下層で許容される幅と間隔が、上層で許容される幅と間隔の4分の1以上になることがあります。これは、プリント基板やマルチチップモジュール設計などの他の用途のルーターでは発生しない多くの複雑な問題を引き起こします。ルールが互いの単純な倍数でない場合、またビアが異なるルールを持つ層間を通過する必要がある場合、特に困難が生じます。

コンピュータ上で設計したPCB（左）と、部品を搭載した基板アセンブリ（右）です。基板は両面基板で、スルーホールめっき、緑色のソルダーレジスト、白い銘板が付いています。表面実装部品とスルーホール部品の両方が使用されています。

全体的なルーティング戦略

初期のEDAルーターは「手動ルーター」で、設計者は各ネットの各線分の終点をマウスでクリックしていました。現代のPCB設計ソフトウェアは通常、「インタラクティブルーター」を提供しています。設計者はパッドを選択し、数箇所をクリックしてEDAツールに配線位置を指示すると、EDAツールはデザインルールチェック（DRC）に違反することなく、その経路にできるだけ近い位置に配線を配置しようとします。より高度なインタラクティブルーターの中には、「押し退け」（別名「押し退け」または「自動移動」）機能を備えたものもあります。EDAツールは、可能であれば他のネットを押し退け、設計者が希望する場所に新しい配線を配置し、DRCに違反しないようにします。現代のPCB設計ソフトウェアは通常、「自動ルーター」も提供しており、これにより、未配線の残りの接続を人間の介入なしに配線できます。

現代の集積回路では、手作業で配線するにはネット数が多すぎるため、通常は完全自動配線が使用されます。自動配線で完全に配線されたソリューションが得られない場合、一般的な解決策としては、不足している配線を手作業で完成させるのではなく、配線のためのスペースを確保するために配置を変更することが挙げられます。

オートルーターの主な種類

ルーターの仕組み

多くのルータは次のような全体的なアルゴリズムを実行します。

  • まず、各ネットのおおよその経路を決定します。通常は粗いグリッド上で配線を行います。このステップはグローバル配線[ 22 ]と呼ばれ、オプションでレイヤー割り当てを行うこともあります。グローバル配線は、グリッドごとに実行できる後続の詳細な配線ステップのサイズと複雑さを制限します。

詳細なルーティングでは、最も一般的な手法は、リップアップと再ルーティング、またはリップアップと再試行です。[ 4 ]

  • ネットを配線する順序を選択します。
  • 各ネットを順番に配線する
  • すべてのネットを正常に配線できない場合は、選択した配線を削除し、配線する残りのネットの順序を変更して、残りの配線を再度試行する、さまざまな「クリーンアップ」方法のいずれかを適用します。

このプロセスは、すべてのネットが配線されるか、プログラム (またはユーザー) が諦めるまで繰り返されます。

代替的なアプローチとして、ショート、設計ルール違反、障害物などを配線長超過と同様に扱う方法があります。つまり、回避すべき絶対的なコストではなく、（最初は）削減すべき有限のコストとして扱うのです。この複数パスの「反復改善」配線法[ 23 ]は、以下のアルゴリズムで説明されます。

  • 複数の反復パスごとに次の処理が実行されます。
  • 「目的関数」の重みパラメータを規定または調整します（重みパラメータは、超過配線長の単位ごとに、また違反の種類ごとに設定されます）。例えば、最初のパスでは、超過配線長には通常高いコストが与えられ、短絡や隣接関係などの設計違反には低いコストが与えられます。後のパスでは、コストの相対的な順序が変更され、違反は高コストとなるか、あるいは完全に禁止されるようになります。
  • このパス中にネットを配線するシーケンスを選択（またはランダムに選択）します。
  • 各ネットを（以前に配線されている場合は）「剥ぎ取り」、順番に再配線することで、そのネットの目的関数の値が最小になるようにします。（配線の一部には、通常、ショートやその他の設計違反が発生します。）
  • ルーティングが完了して正しくなり、それ以上改善されなくなるか、またはその他の終了基準が満たされるまで、次の反復パスに進みます。

ほとんどのルーターは、配線層を主に「x」方向または「y」方向の配線に割り当てるが、そのような割り当てを回避または軽減するルーターも存在する。[ 24 ]それぞれのアプローチには長所と短所がある。方向を制限することで電源設計や層間クロストークの制御が容易になるが、任意の配線経路を許可するとビアの必要性が減り、必要な配線層数も減る。

参照

参考文献

  1. ^ Garey, MR; Johnson, DS (1977). 「直線シュタイナー木問題はNP完全である」 . SIAM Journal on Applied Mathematics . 32 (4): 826– 834. doi : 10.1137/0132071 . ISSN  0036-1399 .
  2. ^ Szymanski, Thomas G. (1985). 「ドッグレッグチャネルルーティングはNP完全である」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (1): 31– 41. Bibcode : 1985ITCAD...4...31S . doi : 10.1109/tcad.1985.1270096 . S2CID 17511882 . 
  3. ^ Stevens, James Edward, Jr. (1972).プリント基板の配置と配線のための高速ヒューリスティック手法（博士論文）.アーバナ：イリノイ大学アーバナ・シャンペーン校.{{cite thesis}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  4. ^ a b c d e Byers, TJ (1991-08-01).マイクロコンピュータによるプリント回路基板設計（第1版）. ニューヨーク、アメリカ合衆国: Intertext Publications/Multiscience Press, Inc.、McGraw-Hill Book Company . pp.  99– 101. ISBN 978-0-07-009558-8。LCCN  91-72187。
  5. ^ Ritchey, Lee W. (1999年12月). 「PCBルーターと配線方法」(PDF) . PC Design Magazine (1999年2月). Speeding Edge. 2018年10月22日時点のオリジナルよりアーカイブ(PDF) . 2018年10月22日閲覧。
  6. ^ Lee, Chester Y. (1961年9月). 「パス接続のためのアルゴリズムとその応用」. IRE Transactions on Electronic Computers . EC-10 (3): 346– 365. Bibcode : 1961IRTEC..10..346L . doi : 10.1109/TEC.1961.5219222 . S2CID 40700386 . 
  7. ^ a b c d e Kollipara, Ravindranath; Tripathi, Vijai K.; Sergent, Jerry E.; Blackwell, Glenn R.; White, Donald; Staszak, Zbigniew J. (2005). 「11.1.3 電子システムのパッケージング - プリント配線板の設計」(PDF) . Whitaker, Jerry C.; Dorf, Richard C. (編). The Electronics Handbook (第2版). CRC Press , Taylor & Francis Group, LLC . p. 1266. ISBN 978-0-8493-1889-4. LCCN  2004057106 . 2017年9月25日時点のオリジナルよりアーカイブ（PDF） . 2017年9月25日閲覧.
  8. ^ Hadlock, Frank O. (1977-12-01). 「グリッドグラフのための最短経路アルゴリズム」 .ネットワーク. 7 (4): 323– 334. doi : 10.1002/net.3230070404 .
  9. ^三上 公一; 田淵 欽也 (1968).プリント回路コネクタの最適配線のためのコンピュータプログラム. IFIPS Proceedings. Vol. H47. pp.  1745– 1478.
  10. ^ Hightower, David W. (1969). 「連続平面上の配線配線問題の解決策」. DAC'69: Proceedings of the 6th Annual Conference on Design Automation . ACM Press . pp.  1– 24. doi : 10.1145/800260.809014 .(注: これは、「ライン プローブ ルーター」の最初の説明の 1 つが含まれています。)
  11. ^ a b c d Minges, Merrill L. (1989).電子材料ハンドブック：パッケージング. 第1巻. ASM International . ISBN 978-0-87170-285-2. 2017年9月27日閲覧。
  12. ^ Reed, James B.; Sangiovanni-Vincentelli, Alberto; Santamauro, Mauro (1985). 「新しいシンボリックチャネルルータ：YACR2」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (3): 203– 219. Bibcode : 1985ITCAD...4..208R . doi : 10.1109/TCAD.1985.1270117 . S2CID 17065773 . [1]
  13. ^ a b c Shankar, Ravi; Fernandez, Eduardo B. (2014-01-12). Einspruch, Norman G. (ed.). VLSIとコンピュータアーキテクチャ. VLSIエレクトロニクス・マイクロストラクチャー・サイエンス. 第20巻. Academic Press . ISBN 978-1-48321784-0. 2018年10月22日閲覧。
  14. ^ McLellan, Paul (2012年4月23日). 「Channel Routing Memories」 . 2021年5月18日時点のオリジナルよりアーカイブ。2022年1月1日閲覧。
  15. ^ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, GJ; Symonds, G. (1985-06-23). 「プリント基板のグリッドレス配線手法」.第22回ACM/IEEE設計自動化会議(PDF) . 英国グロスターシャー州テュークスベリー、ニュータウン: Racal-Redac Ltd. pp.  509– 515. doi : 10.1109/DAC.1985.1585990 . ISBN 0-8186-0635-5. ISSN  0738-100X . 2018年10月22日時点のオリジナルよりアーカイブ（PDF） . 2018年10月22日閲覧.
  16. ^ Webb, Darrell (2012年12月20日). 「グリッドレス自動ルーティングの父、アラン・フィンチへのトリビュート」 . Zuken Blog . 2018年10月22日時点のオリジナルよりアーカイブ。2018年10月22日閲覧。
  17. ^ Wu, Bo (1992年4月).グラフ理論に基づくルーティングアルゴリズム(PDF) (論文).ウェスタンミシガン大学. S2CID 3357923. 2018年10月22日時点のオリジナル(PDF)からのアーカイブ。 2018年10月22日閲覧。 
  18. ^ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen" .コンピューターウォッチェ(ドイツ語)。 1992年3月13日。2018年10月21日のオリジナルからアーカイブ。2018年10月20日に取得。
  19. ^ Pfeil, Charles (2017年11月2日). 「PCB設計の生涯：設計からソフトウェアまで」 EDNネットワーク. 2018年10月21日時点のオリジナルよりアーカイブ。 2018年10月20日閲覧。
  20. ^ a bレドリッチ、デトレフ。「1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung」(PDF)。Schaltungsdesign (ドイツ語)。エルンスト・アッベ・イエナ大学(EAH)。2018-10-21 のオリジナル(PDF)からアーカイブ。2018年10月20日に取得。
  21. ^ 「設計自動化の簡素化 - 次世代の設計方法論」。
  22. ^ Soukup, Jirí (1979). 「Global Router」 .第16回設計自動化会議議事録. 米国カリフォルニア州サンディエゴ: IEEE Press . pp.  481– 489.
  23. ^ Rubin, Frank (1974). 「プリント配線のための反復的手法」 .第11回デザインオートメーションワークショップ論文集. pp.  308–13 .
  24. ^ Linsker, Ralph (1984). 「反復的改善ペナルティ関数駆動型配線システム」(PDF) . IBM Journal of Research and Development . 28 (5): 613– 624. doi : 10.1147/rd.285.0613 .

さらに読む

  • Scheffer, Louis K.; Lavagno, Luciano; Martin, Grant (2006). 「第8章ルーティング」.集積回路のための電子設計自動化ハンドブック. 第2巻. ボカラトン、フロリダ州、米国: CRC Press / Taylor & Francis . ISBN 978-0-8493-3096-4。
「 https://en.wikipedia.org/w/index.php?title=Routing_(electronic_design_automation)&oldid=1334879979#Grid-less_router」より取得