JPH04324581A - 配線経路探索方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は配線経路探索方式に関し
、特に大規模集積回路及びプリント配線基板等の設計に
おいて、結線を要する端子間を自動配線するための配線
経路探索方式に関する。

【０００２】

【従来の技術】従来、この種の配線経路探索方式は、与
えられた導体間隙を保証しながら、かつ曲り点が少なく
なるように配線経路を探索するようになっていた。

【０００３】なお、参考文献としては、樹下行三編，論
理装置のＣＡＤ，第４３頁〜第５２頁，情報処理学会（
昭和５６年）がある。

【０００４】

【発明が解決しようとする課題】上述した従来の配線経
路探索方式は、与えられた導体間隙を保証しながら、か
つ曲り点が少なくなるように配線経路を探索するので、
配線密度の高い基板では、ビアのサイズが配線の線幅よ
り極端に大きくなり、配線が混雑してくると、配線は通
せるがビアが作れないデッドスペースがいたるところに
生成され、配線領域を有効に使用することができないと
いう欠点を有していた。

【０００５】本発明の目的は、配線層に散在するデッド
スペースを有効に利用できる配線経路探索方式を提供す
ることにある。

【０００６】

【課題を解決するための手段】本発明の配線経路探索方
式は、結線を要する端子対である未結線ピンペアについ
て、端子間の配線経路を、複数の配線層上で、配線層間
を接続する中継孔であるビアを使用して配線層を乗り換
えながら探索する配線経路探索方式において、（Ａ）各
前記未結線ピンペアに対し、前記既配線経路中のビア及
び配線経路探索時に使用するビアが大きさを持たないと
仮定して従来手法により仮の配線経路を探索する手順、
（Ｂ）前記仮の配線経路を発見した場合、ビアを本来の
大きさに戻したときに、前記仮の配線経路の周囲で配線
とビアとが接触あるいは接近し過ぎている箇所を検出し
、前記配線とビアとが接触あるいは接近し過ぎないよう
にある制約の範囲内で前記既配線経路及び仮の配線経路
を変更する手順、（Ｃ）前記配線とビアとが接触あるい
は接近し過ぎている箇所の経路変更に成功したとき、前
記仮の配線経路を既配線経路として登録する手順、（Ｄ
）前記配線とビアとが接触あるいは接近し過ぎている箇
所の経路変更に失敗したときに、既配線経路を変更する
前の状態に戻し、仮の配線経路を除去する手順、を備え
て構成されている。

【０００７】

【実施例】次に、本発明の実施例について図面を参照し
て説明する。

【０００８】図１は本発明の配線経路探索方式の一実施
例を示す流れ図である。また、図２は図１のステップ２
３での処理内容を説明するためのパターン図であり、図
３は図１のステップ２５での処理内容を説明するための
パターン図である。

【０００９】次に、動作を説明する。

【００１０】図１において、まず、ステップ２１では、
与えられた未結線ピンペア群の中から未結線ピンペアを
１つ取り出して、ステップ２２へ進む。ステップ２２で
は、未処理の未結線ピンペアが有るか否かを判定し、有
る場合はステップ２３へ進み、無い場合は処理を終了す
る。

【００１１】ステップ２３へ進んだ場合、ステップ２３
では取り出された未結線ピンペアに対して既配線経路中
のビア及び配線経路探索時に使用するビアが大きさを持
たないと仮定して、従来の手法により仮の配線経路を探
索する。なお、従来の手法の例としては、線分探索法等
がある。

【００１２】次に、ステップ２４では、ステップ２３に
おいて、配線経路を発見したか否かを判定し、発見した
場合は、ステップ２５へ、発見できなかった場合は、ス
テップ２１へ戻る。続いてステップ２５では、ビアを本
来の大きさに戻したとき、仮の配線経路の周囲で配線と
ビアとが干渉している箇所を検出し、干渉しないように
、ある制約の範囲内で、配線経路及び発見した仮の配線
経路を変更する。

【００１３】次に、ステップ２６では、ステップ２５に
おいて、配線経路及び仮の配線経路の変更に成功したか
否かを判定して、成功したときには、ステップ２７へ行
って変更後の仮の配線経路を既配線経路として登録後、
ステップ２１へ戻り、失敗したときには、ステップ２８
へ行き、ステップ１０５で変更された既配線経路を変更
前の状態に戻すとともに、仮の配線経路を除去してステ
ップ２１へ戻る。

【００１４】このようにして、すべての未結線ピンペア
に対する処理が終了するまで、前記一連の処理を繰り返
す。

【００１５】次に、図２を使用してステップ２３での配
線経路探索について説明する。

【００１６】図２において、配線経路探索中は、既存ビ
ア４，５ａ，６及び配線経路探索時に使用する探索ビア
８は、大きさを持たないと仮定して配線経路を探索する
と、既配線１ａ，２ａ，３と探索ビア８との間及び仮の
配線７と既存ビア４，５ａ，６との間に干渉箇所９，１
０，１１が発生するが、後で干渉箇所９，１０，１１は
修正できるという仮定のもとに配線経路を探索していく
。

【００１７】次に、図３を使用してステップ２５での配
線経路変更について説明する。

【００１８】図３では、図２に示した干渉箇所９，１０
，１１を除去するため、探索ビア８に隣接する２本の既
配線１ａ，２ａの経路を変更し、かつ既存ビア５ａを移
動させて、既配線１ｂ，２ｂとし既存ビア５ｂとするこ
とによって、干渉箇所９，１０，１１を除去している。 なお、上記の説明では、仮の配線７及び探索ビア８の変
更は行われなかったが、必要に応じて変更してもよい。

【００１９】

【発明の効果】以上説明したように、本発明の配線経路
探索方式は、未結線ピンペアに対する配線経路探索時、
ビアが大きさを持たないと仮定して配線経路を探索し、
経路を発見したら、配線とビアとが干渉している箇所に
ついて、既配線及び発見した仮の経路を変更して干渉し
ないようにすることにより、配線層に散在するデッドス
ペースを有効に利用できるという効果を有している。

【図面の簡単な説明】

【図１】本発明の配線経路探索方式の一実施例を示す流
れ図である。

【図２】図１のステップ２３での処理内容を説明するた
めのパターン図である。

【図３】図１のステップ２５での処理内容を説明するた
めのパターン図である。

【符号の説明】

１ａ，１ｂ　　　　既配線 ２ａ，２ｂ　　　　既配線 ３　　　　既配線 ４　　　　既存ビア ５ａ，５ｂ　　　　既存ビア ６　　　　既存ビア ７　　　　仮の配線 ８　　　　探索ビア ９〜１１　　　　干渉箇所

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　結線を要する端子対である未結線ピン
   ペアについて、端子間の配線経路を、複数の配線層上で
   、配線層間を接続する中継孔であるビアを使用して配線
   層を乗り換えながら探索する配線経路探索方式において
   、（Ａ）各前記未結線ピンペアに対し、前記既配線経路
   中のビア及び配線経路探索時に使用するビアが大きさを
   持たないと仮定して従来手法により仮の配線経路を探索
   する手順、（Ｂ）前記仮の配線経路を発見した場合、ビ
   アを本来の大きさに戻したときに、前記仮の配線経路の
   周囲で配線とビアとが接触あるいは接近し過ぎている箇
   所を検出し、前記配線とビアとが接触あるいは接近し過
   ぎないようにある制約の範囲内で前記既配線経路及び仮
   の配線経路を変更する手順、（Ｃ）前記配線とビアとが
   接触あるいは接近し過ぎている箇所の経路変更に成功し
   たとき、前記仮の配線経路を既配線経路として登録する
   手順、（Ｄ）前記配線とビアとが接触あるいは接近し過
   ぎている箇所の経路変更に失敗したときに、既配線経路
   を変更する前の状態に戻し、仮の配線経路を除去する手
   順、を備えたことを特徴とする配線経路探索方式。