Loading article…
電子設計 において、配線ルーティング（一般的には単にルーティングと呼ばれる）は、プリント回路基板（PCB）および集積回路（IC）の設計におけるステップです。これは、 IC または PCB 上のコンポーネントの各アクティブ要素の位置を決定する、配置と呼ばれる先行ステップに基づいています。配置の後、ルーティング ステップでは、IC のすべての設計ルールに従いながら、配置されたコンポーネントを適切に接続するために必要な配線を追加します。IC 設計の配置ステップとルーティング ステップを合わせて、配置と配線と呼びます。
すべてのルーターのタスクは同じです。ルーターには、セル上のピン(ターミナルとも呼ばれる) で構成される既存のポリゴンがいくつか与えられ、オプションでプレルートと呼ばれる既存の配線がいくつか与えられます。これらの各ポリゴンは、通常、名前または番号によってネットに関連付けられます。ルーターの主なタスクは、同じネットに割り当てられたすべてのターミナルが接続され、異なるネットに割り当てられたどのターミナルも接続されず、すべての設計ルールが遵守されるようなジオメトリを作成することです。ルーターは、接続すべきターミナルを接続しなかったり (オープン)、接続すべきでない 2 つのターミナルを誤って接続したり (ショート)、設計ルール違反を作成したりすることで失敗する可能性があります。さらに、ネットを正しく接続するために、ルーターは、設計がタイミングを満たしていること、クロストークの問題がないこと、金属密度の要件を満たしていること、アンテナ効果の影響を受けないことなどを確認することも求められます。このしばしば矛盾する目的の長いリストが、ルーティングを極めて困難にしています。
配線に関連するほぼすべての問題は解決困難であることが知られています。最も単純な配線問題はシュタイナー木問題と呼ばれ、障害物や設計ルールのない 1 つのレイヤーにある 1 つのネットの最短経路を見つけるというものです。これは、すべての角度が許可されている場合と、配線が水平および垂直のワイヤのみに制限されている場合の両方でNP 完全であることが知られています。 [1]チャネル配線 のバリアントも NP 完全であることが示されています[2] 。また、クロストーク、ビアの数などを削減する配線も同様です。したがって、配線では最適な結果を見つけようとすることはほとんどありません。代わりに、ほぼすべての配線は、十分に良いソリューションを見つけようとする ヒューリスティックに基づいています。
設計ルールは、レイヤーごとに大幅に異なることがあります。たとえば、下層で許容される幅と間隔は、上層で許容される幅と間隔の 4 分の 1 以上小さくなることがあります。これにより、プリント回路基板やマルチチップ モジュール設計などの他の用途のルーターでは発生しない多くの追加の複雑さが生じます。ルールが互いの単純な倍数でない場合や、ビアが異なるルールを持つレイヤー間を移動する必要がある場合は、特に困難が生じます。
ルーターの種類
最も初期のタイプの EDA ルーターは「手動ルーター」でした。つまり、製図者は各ネットの各ライン セグメントのエンドポイントをマウスでクリックしていました。現代の PCB 設計ソフトウェアは、通常「インタラクティブ ルーター」を提供します。製図者はパッドを選択し、いくつかの場所をクリックして EDA ツールにどこに行くべきかを伝え、EDA ツールは設計ルール チェック(DRC) に違反することなく、そのパスにできるだけ近い場所に配線を配置しようとします。より高度なインタラクティブ ルーターには、インタラクティブ ルーターに「押し退け」(別名「押し退け」または「自動移動」) 機能があります。EDA ツールは、可能であれば他のネットを押し退けて、製図者が希望する場所に新しい配線を配置し、DRC に違反しないようにします。現代の PCB 設計ソフトウェアは、通常「自動ルーター」も提供し、これは、残りのすべての未配線接続を人間の介入なしに配線します。
オートルーターの主なタイプは次のとおりです。
- 迷路ルーター[3] [4]
- リールーター[5] [3] [6]
- ハドロックルーター[7]
- フラッドルーター[3]
- ラインプローブルーター
- 三上・田淵ルーター[8]
- ハイタワールーター[9] [6] [10] [3]
- パターンルーター[6] [10]
- チャネルルーター[11] [10] [6] [12]
- スイッチボックスルーター[12]
- リバールーター[12]
- 背とステッチルーター[13]
- グリッドレスルーター[14] [10] [6] [15]
- エリアルーター
- グラフ理論に基づくルーター[16]
- Bloodhoundルータ[17] [18] [19] ( Racal-Redac /図研によるCADSTAR )
- Specctra [19]（別名Allegro PCB Router）（バージョン10以降はグリッドレス）
- トポロジカルルーター
- FreeStyle Router (別名SpeedWay、P-CAD用のDOSベースの自動ルーター)
- TopoR ( Eremexの Delta Designでも使用されているWindowsベースの自動配線ツール)
- Toporouter (Anthony Blake のgEDA スイートのPCB内のオープンソース ルーター)
- TopRouter ( CadSoft / AutodeskのEAGLE 7.0以降のトポロジ プレルーター)
- SimplifyPCB（バンドル配線と手動配線結果に重点を置いたトポロジカルルーター）[20]
ルーターの仕組み
多くのルータは、次の全体的なアルゴリズムを実行します。
- まず、各ネットのおおよその経路を決定します。通常は粗いグリッド上で配線します。このステップはグローバル配線と呼ばれ、[21]オプションでレイヤーの割り当てが含まれる場合があります。グローバル配線は、グリッドごとに実行できる後続の詳細な配線ステップのサイズと複雑さを制限します。
詳細なルーティングの場合、最も一般的な手法は、リップアップと再ルーティング、別名リップアップと再試行です。[3]
- ネットを配線する順序を選択します。
- 各ネットを順番に配線する
- すべてのネットを正常に配線できない場合は、さまざまな「クリーンアップ」方法のいずれかを適用します。この方法では、選択した配線が削除され、配線する残りのネットの順序が変更され、残りの配線が再度試行されます。
このプロセスは、すべてのネットが配線されるか、プログラム (またはユーザー) が諦めるまで繰り返されます。
代替アプローチは、ショート、設計ルール違反、障害物などを、余分な配線長と同様に扱うことです。つまり、回避すべき絶対的なコストではなく、削減すべき有限のコストとして（最初は）扱うことです。このマルチパス「反復改善」ルーティング方法[22]は、次のアルゴリズムで説明されます。
- 複数の反復パスごとに:
- 「目的関数」の重みパラメータを規定または調整します (余分な配線長の各単位と違反の種類ごとに重みパラメータ値を持ちます)。たとえば、最初のパスでは、余分な配線長には通常高いコストが与えられ、ショートや隣接などの設計違反には低いコストが与えられます。後のパスでは、コストの相対的な順序が変更され、違反が高コストになるか、または完全に禁止される可能性があります。
- このパス中にネットをルーティングするシーケンスを選択（またはランダムに選択）します。
- 各ネットを (以前に配線されている場合は) 「引き剥がし」、順番に再配線して、そのネットの目的関数の値を最小化します。 (配線の一部には、一般にショートやその他の設計違反があります。)
- ルーティングが完了して正しくなり、それ以上改善されなくなるか、またはその他の終了基準が満たされるまで、次の反復パスに進みます。
ほとんどのルーターは、主に「x」または「y」方向の配線を行うために配線層を割り当てますが、そのような割り当てを回避または軽減するルーターもあります。[23]それぞれのアプローチには長所と短所があります。方向を制限すると、電源設計と層間クロストークの制御が容易になりますが、任意のルートを許可すると、ビアの必要性が減り、必要な配線層の数を減らすことができます。
参照
参考文献
- ^ Garey, MR; Johnson, DS (1977). 「直線シュタイナー木問題はNP完全である」. SIAM Journal on Applied Mathematics . 32 (4): 826–834. doi :10.1137/0132071. ISSN 0036-1399.
- ^ Szymanski, Thomas G. (1985). 「Dogleg チャネル ルーティングは NP 完全です」。IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (1): 31–41. doi :10.1109/tcad.1985.1270096. S2CID 17511882.
- ^ abcde Byers, TJ (1991-08-01). マイクロコンピュータによるプリント回路基板の設計 (第 1 版). ニューヨーク、米国: Intertext Publications/Multiscience Press, Inc.、McGraw-Hill Book Company . pp. 99–101. ISBN 978-0-07-009558-8LCCN 91-72187 。
- ^ Ritchey, Lee W. (1999 年 12 月). 「PCB ルーターとルーティング方法」(PDF) . PC Design Magazine (1999 年 2 月). Speeding Edge. 2018 年 10 月 22 日時点のオリジナルよりアーカイブ(PDF) . 2018 年 10 月 22 日閲覧。
- ^ Lee, Chester Y. (1961 年 9 月)。「パス接続のアルゴリズムとその応用」。IRE Transactions on Electronic Computers。EC -10 (3): 346–365。doi : 10.1109 /TEC.1961.5219222。S2CID 40700386 。
- ^ abcde 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日閲覧。
- ^ Hadlock, Frank O. (1977-12-01). 「グリッドグラフの最短経路アルゴリズム」.ネットワーク. 7 (4): 323–334. doi :10.1002/net.3230070404.
- ^ 三上 浩一; 田淵 欽也 (1968)。プリント回路コネクタの最適配線のためのコンピュータプログラム。IFIPS Proceedings。Vol . H47。pp. 1745–1478。
- ^ 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 つが含まれています。)
- ^ abcd Minges, Merrill L. (1989). 電子材料ハンドブック :パッケージング。第 1 巻。ASM International。ISBN 978-0-87170-285-2. 2017年9月27日閲覧。
- ^ 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. doi :10.1109/TCAD.1985.1270117. S2CID 17065773.[1]
- ^ abc 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日閲覧。
- ^ McLellan, Paul (2012-04-23). 「Channel Routing Memories」。2021年5月18日時点のオリジナルよりアーカイブ。2022年1月1日閲覧。
- ^ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, GJ; Symonds, G. (1985-06-23). プリント基板のグリッドレス配線方法(PDF) . 22nd ACM/IEEE Design Automation Conference、米国ネバダ州ラスベガス。Design Automation Conference、2009。Dac '09。46th ACM/IEEE。ニュータウン、テュークスベリー、グロスターシャー、英国: 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日閲覧。
- ^ Webb, Darrell (2012-12-20). 「グリッドレス自動ルーティングの父、アラン・フィンチへのトリビュート」。2018年10月22日時点のオリジナルよりアーカイブ。2018年10月22日閲覧。
- ^ Wu, Bo (1992年4月). グラフ理論ベースのルーティングアルゴリズム(PDF) (論文).ウェスタンミシガン大学. S2CID 3357923. 2018年10月22日時点の オリジナル(PDF)からアーカイブ。 2018年10月22日閲覧。
- ^ “Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen".コンピューターウォッチェ(ドイツ語)。 1992年3月13日。 2018年10月21日のオリジナルからアーカイブ。2018年10月20日に取得。
- ^ Pfeil, Charles (2017-11-02). 「A life designing PCBs: From design to software」EDN Network . 2018-10-21 時点のオリジナルよりアーカイブ。 2018-10-20閲覧。
- ^ ab レドリッヒ、デトレフ。 「1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung」(PDF)。Schaltungsdesign (ドイツ語)。エルンスト・アッベ・イエナ大学(EAH)。2018-10-21 のオリジナル(PDF)からアーカイブ。2018年10月20日に取得。
- ^ 「設計自動化の簡素化 - 次世代の設計方法論」。
- ^ Soukup, Jirí (1979). 「Global Router」.第 16 回デザインオートメーション会議の議事録. 米国カリフォルニア州サンディエゴ: IEEE プレス. pp. 481–489.
- ^ Rubin, Frank (1974)。「プリント配線配線の反復手法」。第 11 回デザインオートメーションワークショップ議事録。pp. 308–13。
- ^ 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 章:ルーティング」。集積回路の電子設計自動化ハンドブック。第 II 巻。米国フロリダ州ボカラトン: CRC Press / Taylor & Francis。ISBN 978-0-8493-3096-4。
外部リンク
- http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf
- http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf