JPH0325942A - 配線パターン決定方法及びそのシステム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、プリント基板，集積回路等を配線するための
プリントパターンを決定する方法及びそのシステムに係
り、特に，電気的および製造上の問題の少ない質の高い
配線パターンの生成、および短時間での配線パターンの
決定に好適な配線パターン決定方法及びそのシステムに
関する。

〔従来の技術〕

大形計算機等の大規模・高密度なプリント基板，集積回
路の配線に対しては、下記の如き要求が与えられる６ （１）夕ロス１・−ク等の電気的な問題が生じない配線
パターンを決定すること。

（２）不良率を低く抑えるために、製造上の問題のない
配線パターンを決定すること。

（３）多種類の大規模なプリント基板等の配線パターン
決定処理を一定の設計期間内で行う必要があるため、１
つのプリント基板等に関して、短時間で配線パターンを
決定すること。

この要求は、設計変更，配線遅延チェック，物理配線条
件チェック等によるフィードバックが多い場合には特に
大きい。

本発明は、特に上記要求の（１）〜（３）に関する。

（１），　（２）に関しては、電気的に、および製造上
問題の生じないパターンを生成するためには、これらの
問題に精通した配線パターン設計者が、問題の生じない
配線パターン形状を「配線パターン仕様」として定め、
配線パターン決定システムがその仕様に沿った配線パタ
ーンを生成する必要がある。すなわち、配線パターン決
定システムは、配線パターン形状を制御する手段を有す
る必要がある。

配線パターン形状を制御する手段として、従来第ｌ９回
デザイン・オートメーション・コンファレンス・プロシ
ーデイングス（１９８２）第４２５頁から第４３１頁（
　１　９　ｔｈ　Ｄｅｓｉｇｎ　Ａｕｔｏｍａｔｉｏｎ
Ｃｏｎｆｅｒｅｎｃｅ　Ｐｒｏｃｅｅｄｉｎｇｓ（１　
９　８　２），　ｐ　ｐ　．４　２　５−４　３　１）
に記載の如く、迷路法による配線パターン決定処理にお
いて探索方向に対して一定のコストあるいはペナルティ
を与えることにより，パターン形状の制御を行う方法が
知られている。たとえば、配線層における主走行方向す
なわち配線パターンが主として走行する方向に対して直
交する方向に配線パターンが走ることを抑えるために，
直交する方向に対して特に大きなコストを与える。

これにより、主走行方向に対して直交するパターンの数
を減小させることができる。

（３）の要求に関して，従来、第６回デザイン・オート
メーション・ワークショップ・プロシーデイングス（１
　９　６　９）第１頁から第２４頁（６ｔｈＤｅｓｉｇ
ｎ　Ａｕｔｏｍａｔｉｏｎ　Ｗｏｒｋｓｈｏｐ　Ｐｒｏ
ｃｅｅｄｉｎｇｓ（１９６９），Ｐｐ．１−２４）に記
載の如き「線分探索法」や、第１９回デザイン・オート
メーション・コンファレンス・プロシーデイングス（１
　９　８　２）第４１１頁から第４１７頁（　１　９　
ｔｈ　Ｄｅｓｉｇｎ　ＡｕｔｏｍａｔｉｏｎＣｏｎｆｅ
ｒｅｎｃｅ　Ｐｒｏｃｅｅｄｉｎｇｓ（１９８２），　
ｐ　ｐ　．　４　１　１　−４１７）に記載の如き「パ
ターン限定法」などが知られている。線分探索法は直線
的に経路探索を行うため、迷路法に比べて高速に配線パ
ターン決定を行うことができる。また、パターン限定法
は、始点と終点との位置関係に応じて予めＬ字型などの
簡易パターンを用意し，簡易パターンにより配線を試み
るため、配線領域が混雑していない場合は、非常に高速
に配線パターンの決定を行うことができる。

以下、第２８図および第２９図を用いて、線分探索法に
よる配線パターン決定方法を説明する。

第２８図（ａ）は線分探索法による経路探索の過程を示
し、第２８図（ｂ）は経路探索の結果として得られた配
線パターンを表す。第２８図（ａ）に示す如く、線分探
索法においては、始点Ｆより仮線分６を発生させ、さら
に仮線分６上の仮ビア７から新たに仮線分を発生させる
という処理を、仮線分が終点Ｔに到達するまで繰り返す
。「仮ビア」７は仮線分を発生させる基となる格子点で
ある．「仮腺分」６は、第２９図に示される如く，チャ
ネル２上の空き線分８に並行して主格子１上を走る仮想
的な線分である．ここで，主格子とはピン３およびビア
ホール１０が設置される格子である．配線パターン４は
主格子およびチャネル上を走行する。また，空き線分と
は、空格子を連ねて成る線分である。仮線分６は、空き
線分８が途切れる格子点まで伸びる。

なお、本明細書では格子（主格子またはチャネル）が交
わる点を格子点と呼ぶ。

〔発明が解決しようとする課題〕

上記従来のコストによる配線パターン形状制御技術、す
なわち探索方向にコストを与えることにより配線パター
ン形状を制御する方法によれば、配線領域が配線パター
ンによって混雑するに従って配線パターン仕様を満たさ
ない形状の配線パターンを生或する可能性が高くなる。

この理山を、第３図を用いて説明する。第３図は、従来
のパターン形状制御方法により、ピンＡとピンＢの間の
配線パターンを、Ｘ方向配線層とｙ方向配線層とを用い
て決定した結果を示す。配線パターンのうち、Ｘ方向配
線層上にあるものを太い実線で、ｙ方向配線層上にある
ものを太い破線でそれぞれ表してある．もし、配線領域
が混雑していなければ、第３図（ａ）における配線パタ
ーン４の如き単純な形状の配線パターンを生或するが、
配線領域が混雑してくると，第３図（ｂ）における配線
パターン４の如き折れ曲がりの多い複雑な形状の配線パ
ターンを生成するようになり、配線パターン仕様を満た
さない形状の配線パターンを生成する機会が増大する。

また、上記従来の高速に配線パターンを決定する方法（
線分探索法，パターン限定法など）は下記の如き問題が
ある。まず、線分探索法は迷路法よりは高速であるが、
大規模なプリント基板等への適用において必ずしても十
分に高速であるとはいえない。また、パターン限定法は
非常に高速ではあるが，低い配線率しか得られない、と
いう問題がある。

本発明の第１の目的は、配線領域が配線パターンにより
混雑している状況にあっても、配線パターン設計者が電
気的および製造上の問題を勘案して定めた配線パターン
仕様を満足する配線パターンを生成する配線パターン決
定方法を与えることにある。

また、本発明の第２の目的は、線分探索法が達成する程
度の比較的高い配線率を達成できる、高速な配線パター
ン決定方法を与えることにある。

本発明の第３の目的は、上記各方法を用いて質が高く、
かつ高速に配線パターンを決定するシステムを提供する
ことにある。

〔課題を解決するための手段〕

上記第１の目的は、迷路法を用いた配線パターン決定方
法において、波面（すなわち、経路探索の最前面にあり
経路探索を進める基点となる格子点の集合）に属する格
子点から探索できる格子点の位置を決定するベクトルを
、配線パターン仕様が満足されるように定め、このベク
トル（以下、探索ベクトルと呼ぶ）に沿って経路探索を
行うことにより達成される。ここで，格子点を「探索す
る」とは，基本的には、格子点が空格子点かつ未探索な
らば、その格子点を新たに探索基点として登録すること
である。

以下、第１図を用いて簡単な例を示す。いま、異種信号
間の短絡（ショート）を回避するために、「斜め方向に
走行するパターンは、主格子交点Ｍとチャネル交点Ｃと
を結ぶパターンのみ許容し、他の斜めパターンは禁止す
る」というパターン仕様を定めたとする。ここで、主格
子交点Ｍとは主格子ｌが互いに交わる点を指し、チャネ
ル交点Ｃとはチャネル２が互いに交わる点を指す。主格
子交点およびチャネル交点は「格子点」の１種である。

このパターン仕様を満たすためには、第ｌ図の（ａ）〜
（ｄ）に示す探索ベクトルを定義すれば十分である。（
ａ）および（ｄ）は，「主格子交点Ｍおよびチャネル交
点Ｃからは、隣接した８っの格子点べ探索を進めること
が許されること」を示す。また、（ｂ）および（ｃ）は
、「主格子交点でもチャネル交点でもない格子点から、
斜め方向を除く４つの隣接格子点へ探索を進めることが
許される」ことを示す。上記探索ベクトルを定義するこ
とにより、異種信号間の短絡を巧みに回避することがで
きる。第１図（ｅ）に上記探索ベクトルを用いた経路探
索の途中の状態を示す。

上記第２の目的は，線分探索法の中にパターン限定法の
処理を組み込むことにより達成される。

すなわち、線分探索法に基づく配線パターン決定処理に
おいて、．始点若しくは仮ビア（以下、始点等と呼ぶ）
から仮線分を発生させる処理に先立ち，始点等と終点と
の位置関係に応じて略Ｌ字型等の形状を成す簡易パター
ンを幾つか用意し、この簡易パターンにより始点等と終
点とが未使用配線領域上で接続可能であるか否かを調べ
、接続可能な簡易パターンがあれば、接続可能な簡易パ
ターンの１つを始点等と終点とを接続する配線パターン
として採用することにより達或される。

以下、第２図を用いて簡単な例を示す。まず、同図（ａ
）に示す如く、始点Ｆと終点Ｔの間の配線領域が未使用
であれば，略Ｌ字型の簡易パターンＫを配線パターンと
して採用する。一方、第２図（ｂ）に示す如く障害物９
が存在し、始点Ｆと終点Ｔとを結ぶ簡易パターンによっ
て配線できない場合は、始点Ｆから仮腺分６を発生させ
、仮線分６上の格子点（仮ビアと呼ぶ）から終点までを
、簡易パターンＫによって配線することを試みる。

第２図（ｂ）に示す例では、簡易パターンによる配線に
或功する。もし，（ｂ）に示す例よりも多くの障害物が
存在し、始点Ｆから発生した仮線分６上の仮ビア７から
、簡易パターンＫによって配線できない場合は、仮ビア
７から更に仮線分を発生させ、この仮線分上の格子点か
ら簡易パターンによる配線を試みる。

このように、簡易パターンによる配線試行と仮線分発生
とを繰り返し行うことにより終点Ｔまでの配線パターン
を決定する。

上記第３の目的は、第１の目的を達戊する上記パターン
形状制御迷路法と第２の目的を達成する上記高速線分探
索法とを組合せることにより達成される。

〔作用〕

上記パターン形状制御迷路法は、上記探索ベクトルに沿
って経路探索を行うため、探索した格子点を連ねた経路
は自然に配線パターン仕様を満たし、経路登録部が決定
する配線パターンは当然の結果として配線パターン仕様
を｝蘭たす。

また，上記の「パターン限定法を組み込んだ高速線分探
索法」に基づく配線パターン決定方法は、もし、始点と
終点の間に略Ｌ字型の配線パターンが存在する場合は、
即座に配線パターンを決定することができ、また始点と
終点の間に略Ｌ字型の配線パターンが存在しない場合で
は、仮線分上の各仮ビアから逐一仮線分を発生させる前
に，１つの仮ビアから即座に接続することのできる略Ｌ
字型の簡易パターンによる配線を試みるため、従来の線
分探索法より高速に配線パターンを決定することができ
る。また、従来の線分探索法と同程度の深さまで探索を
行うため、従来の線分探索法と同程度の配線率を達成す
ることができる。

〔実施例〕

まず、本発明の第１の実施例を、第４図から第９図まで
の図面を用いて説明する。第４図は本発明の第１の実施
例を示す配線パターン決定システムの構成を示すブロッ
ク図であり、第５図，第６図，第７図は、それぞれ配線
パターン決定システム内のコンピュータ４１内に設けら
れた探索ベクトルテーブル，探索基点テーブル，格子点
情報テーブルのデータ構造を示す図であり、第８図およ
び第９図はコンピュータ４工内の経路探索部の処理手順
を示すフローチャートである。

探索ベクトルテーブルとは、上述した探索ベクトルを格
納するテーブルであり，第５図に示す如く，配線層と格
子点相対位置の組み合わせ毎に探索ベクトルを定義する
。ここで、格子点相対位置とは、第５図（ｂ）に示す如
く、主格子ｌの交点（主格子交点と呼ぶ）についての相
対位置を示す。

探索ベクトルは、第５図（ｃ）に示す↓Ｏ通りのベクｈ
ルのいずれかで定義する。（］）から（８）は、配線層
において、隣接格子点へ向かうベク１・ルであり、（９
）は配線層に直交し、」二方の層へ向かうベクトル、（
１０）は（９）の逆ベクトルである。

探索基点テーブルとは、探索基点（すなわち、探索を進
める基点となる格子点）を管理するテーブルであり、第
６図の如きデータ構造をとる。第６図で、各々の探索基
点は配線層とこの配線層における座標とを蓄える。探索
基点はポインタで順序づけられ、チェーンを成す。格子
点情報テーブルとは、第７図に示す如く、各配線層上の
各格子点の情報を格納するテーブルであり，Ｘ座標，ｙ
座標，配線層番サｚについての３次元配列として定義す
る。

第４図において、コンピュータ４１は，探索ベク１−ル
を格納した探索ベク１−ルファイル４０１と，配線パタ
ーン決定処理が施されるべきネットの情報が格納された
ネット情報ファイル４０２と、既に作成された配線パタ
ーンが登録された配線パターンファイル４０３と，配線
禁止情報，穴明禁止情報を格納した配線禁止・穴明禁止
ファイル４０４とを参照して、配線パターン決定処理を
行い、決定した配線パターンを配線パターンファイル４
０３に格納する。

まず既設配線パターン展開部４０５が既作成の配線パタ
ーンおよび配線禁止・穴明禁止を格子点情報テーブル４
１１上に展開する。次に探索ベクトル入力部４０６が探
索ベクトルファイル４０１を参照し、探索ベク１−ルテ
ーブル４０９を作成する。その後各ネットの各接続点対
に対して配線パターン決定処理を施す。配線パターン決
定処理においては，経路探索部４０７が探索ベクトルテ
ーブル４０９，探索基点テーブル４１０，格子点情報テ
ーブル４１］−を適宜参照して経路探索を行い、もし経
路が発見されたなら、経路登録部４０８がこの経路を配
線パターンとして配線パターンファイル４０３に登録す
る。

次に，経路探索部４０７の処理手順を第８図と第９図と
を用いて詳細に説明する。第８図において、まず経路発
見フラグをＯ（すなわち経路未発見）に設定する（８０
１）。経路発見フラグは、以下の処理で経路が発見され
たときに１に設定される。次に、探索基点テーブル４１
０および格子点情報テーブル４１１を初期設定する（８
０２）。

すなわち，格子点情報テーブル４１１の探索フラグ，終
点フラグ，ラベルおよび探索基点テーブル４１０を零ク
リアした後、始点に対応する格子点を探索基点として探
索基点テーブル４１０に設定する。さらに、終点につい
て格子点情報テーブルの終点フラグを１とする。テーブ
ルの初期設定（ステップ８０２）後は、経路探索を繰り
返し行う。まず、探索基点テーブル４１０に探索基点が
定義されているか否かを調べ（ステップ８０３）、もし
１つの探索基点も定義されていない場合は経路未発見と
なる。探索基点が定義されている場合は、定義されてい
る探索基点の中から１つを選択し、探索基点から経路探
索（ステップ８０４）を行う。ここで、選択する探索基
点は，探索基点テーブル４１０においてチェーンの先頭
にあるものである。次に、該探索基点を探索基点テーブ
ル４１０から削除する（ステップ８０５）。経路発見フ
ラグが１となっていれば該当接続点対の経路探索処理を
終了し、そうでなければステップ８０３に戻る（ステッ
プ８０６）。

次にステップ８０４のｒ探索基点の１つからの経路探索
」の処理手順を第９図を用いて説明する。

はじめに探索基点（以下、Ｂという記号を用いて参照す
る）の存在する配線層と格子点相対σ１．置を求める（
９００）。ここで、格子点相対位１ｄは第５図（ｂ）に
示す様な、主格子１で区切られる格子点の相対位置とし
て＜１＞，＜２＞，＜３＞，く４〉のどとくｌ次元配列
された番号として定義する。

次に、ステップ９００で求めた配線層および格子点相対
位置の組み合わせに対応した探索ベクｌ一ルがあるか否
かを調べ（９０１）．もし、あれば探索ベクトルを１つ
ずつ取り出し，取り出した探索ベクトルに沿った探索処
理を行う。すなわち、探索先の格子点の配線層と座標を
求め（９０４．）、格子点情報テーブル４１１を参照し
て探索先の格子点の属性を求める（９０５）．探索先の
格子点が終点であれば経路が発見されたことになり、経
路発見フラグに１を設定する（９１３）．探索先の格子
点が終点でなければ、この格子点が探索基点テーブル４
１０に登録されるための条件を満足するか否かを調べ（
９０７），満足すれば登録処理（９０８，９０９，９１
０）を行い、満足しなけば次の探索ベクトルによる探索
処理に進む．，登録処理では、格子点情報テーブル４１
１内の探索フラグとラベルとに値を設定し、探索先の格
子点を探索基点テー．ブル４１０におけるチェーンの末
尾に登録する。ここで、「ラベル』は、始点から何格子
の探索を経てこの格子点に到達したを格納する数値（探
索距離と呼ぶ）である。

本実施例によれば，探索ベクトルが配線層と格子点相対
位置との組み合わせ毎に定義されているため、複雑なパ
ターン形状制御を行えるという効果がある。

次に，本発明の第２の実施例を第１０図から第１９図ま
での図面を用いて説明する。

第１０図は、本実施例に係る配線パターン決定システム
の構或を示すブロック図である。第１１図は、この配線
パターン決定システムの１適用例である、斜め方向配線
層を含む実装系を表す図である．第１２図および第１３
図はそれぞれこの実装系におけるＸ方向配線層および斜
め４５゜方向配線層に対する探索ベクトルの定義例を示
す図である。第１４図から第１７図までの図は、それぞ
れ上記配線パターン決定システム内のコンピュータ１０
１内に設けられた探索ベクトルテーブル，コストテーブ
ル，探索基点テーブル，格子点情報テーブルのデータ構
造を示す図である。第ｌ８図および第１９図はコンピュ
ータ１０１内の経路探索部の処理手順を示すフローチャ
ートである。

第１０図に示す配線パターン決定システムは、上記第ｌ
の実施例の中で述べた配線パターン決定システム（第４
図参照）に近い構或をとっている。

主な相違点は次の通りである。

１）探索ベクトルテーブル１０１１は，第１４図に示さ
れる如く、配線層と格子点相対位置と入力ベクトルとの
組み合わせ毎に探索ベクトルを格納している。ここで、
入力ベクトルとは，探索基点に探索が到達する直前の格
子点から探索基点へ向かうベクトルであり、第１２図お
よび第１３図において太い矢印Ｎで示される，２）探索
ベクトルに対してコストを定義し，経路探索部１００９
は探索ベクトルおよびコストを用いて経路探索を行う。

コス１・とは．各探索ベクトルに対して「ａ！索しにく
さ」を与える役割をもつ。コンピュータ１０１内にコス
トテーブル１０１２を設け，またテーブルを設定するた
めの処理ブロックであるコスト入力部１００８を設けて
いる。探索基点テーブル１０１３においては、第１６図
に示す如く、探索基点は累積コストの値ごとにチェーン
を成す。ここで、累積コストとは，始点から探索基点に
至るまでのコストを積算した値である。格子点情報テー
ブル１０１４においては、第１７図に示す如く．格子点
ごとに累積コストと入力ベクトルを蓄える。

以下、配線パターン決定システムの処理内容を、上記第
１の実施例とは異なる点を中心に詳細に説明する。

第１０図において、まず既配線パターン展開部１００６
が既作成の配線パターンおよび配線禁止・穴明禁止を格
子点情報テーブル１ｏ１４上に展開する。次に，探索ベ
クトル設定部１００７が探索ベクトルファイル１００１
を参照して探索ベクトルテーブル１０１１を設定する。

第１１図に示される如き実装系、すなわちＸ方向配線層
１１０１，ｙ方向配線層１１０２，斜め４５゜方向配線
層１１０３，斜め１３５″方向配線層１１０４（７）４
つの配線層から成る実装系の場合、探索ベクトルテーブ
ル１０１１には、第１２図および第１３図に示される如
き内容の探索ベクトルが設定される。

ここで、第１２図はＸ方向配線ｒｌｌｏ１における探索
ベクトルの一部を表しており、第ｌ３図は斜め４５″方
向配線層１１０３における探索ベクトルの一部゛を表し
ている。第１２図および第１３図において，探索基点５
に入る太い矢印は入力ベクトルＮを表す。次に、コスト
入力部１００８がコストファイル１００２を参照して、
コストテーブル１０１２を設定する。上述したように、
コストは，探索ベクトルを補助する役割を有する。すな
わち、あまり望ましくない、探索ベクトルに対してはコ
ストとして大きい値を与え、逆に大いに望ましい探索ベ
クトル、たとえばチャネル上を主走行方向に沿って直進
させる探索ベクトルに対しては小さい値を与える。第１
５図に示される如く、コストは配線層と格子点相対位置
と探索ベクトルとの組み合わせ毎に定義される。さて、
探索ベクトルテーブル１０１１およびコストテーブル１
０１２を定義した後、各ネットの各接続点対に対して配
線パターン決定処理を施す。この配線パターン決定処理
は、経路探索部１００９による経路探索処理と経路登録
部１０１０による経路登録処理から成る。

次に、経路探索部１００９の処理手順を第１８図および
第１９図を用いて説明する。概略手順を表す＠１８図に
おいて、第１の実施例に比へて特徴的な点は経路探索を
進める探索基点の選択処理である。本実施例では、コス
１へが最小の探索基点の中でチェーンの先頭にあるもの
を選択する。次に、探索基点からの経路探索の処理手順
を、第１９図を用いて説明する。大きな処理の流れは前
記第１の実施例と同様である。本実施例の特徴的な点は
，探索先の格子点を探索基点テーブル１０１３に登録す
る処理（１　９　０　８から１９１２まで）である。探
索先の格子点を探索基点テーブル１０ｌ３に登録する処
理では、探索先の格子点の探索フラグを１とし（１９０
８）．ステップ１９０９からステップ１９１０で計算し
た累積コストＣの値と、ステップ１９００で求めた入力
ベクトルを探索先の格子点に設定し（１９１１）．探索
基点を探索基点テーブル１０１３における、コストＣの
チェーンの先頭に登録する（１　９　１　２）。

本実施例によれば、探索ベクトルが配線層と格子点相対
位置と入力ベクトルとの組み合わせ毎に定義されている
ため、非常にきめの細かい配線パターン形状制御を行え
るという効果がある。

次に、本発明の第３の実施例を、第２０図から第２５図
までの図面を用いて説明する。

上記本発明の第１および第２の実施例では、すべての接
続点対について共通の探索ベクトル群を用いているが、
本実施例では複数種の探索ベクトル群を用意しておき、
接続点対毎に適切な探索ベクトル群を選択する。すなわ
ち、配線パターンの「線幅』の大小に応じた、複数種の
探索ベクトル群を用意しておき、接続点対に対して配線
処理を行う際、接続点対に対して指定された＃！櫂に応
じて適切な探索ベクトル群を選択する。ここで、線幅に
応じて探索ベクトルを変えるのは、線幅が広い場合、他
の配線パターンとの間隔を十分に保つために，生成する
配線パターンの形状にｆｊＩ１限を設ける必要があるか
らである．第２０図（ａ），（ｂ）はそれぞれ、線幅が
広い場合の配線パターン例，線幅が狭い場合の配線パタ
ーン例を表している。

なお、同図では、Ｘ層上の配線パターンのみ示している
。同図（＆）を見てわかるように、線幅が広い場合は主
格子間に敷かれた２本のチャネルのうち１本だけを使用
し、配線パターン間の距離を十分に大きく保つようにし
ている。このように、１本のチャネルだけでを使用する
ように制御することは、本発明を用いれば容易に実施で
きる。すなわち、第２０図（．）に示す配線パターンを
得るためには．主格子交点からの探索ベクトルを片側だ
けに限定し、かつポンドを禁止すれば良い。

さて、以下第２１図から第２５図までの図面を用いて，
線幅から適切な探索ベクトルを選択する処理を説明する
。

第２１図は、本実施例に係る配線パターン決定システム
の構成を示すブロック図であり、第２２図は、配線処理
制御部２１０６の処理手順を示すフローチャートである
。第２３図はネット情報ファイル２１０３のデータ構造
を示す図である。ネット情報ファイル２１０３は，１レ
コードに１つの接続点対を定義している。ある接続点対
がどのネットに属するかは、先頭フィールドの「ネッ１
一番号」を参照することにより求めることができる。

第２４図｛士線輻・探索ベクトル対応ファイル２１０１
のデータ構造を示す図である。線幅・探索ベクトル対応
ファイル２１０１は、線幅下限値と線幅上限値との組合
せに対して探索ベクトル群番号を定義する。第２５図は
探索ベクトルファイル２１０２のデータ構造を示す図で
ある。探索ベクトルファイル２１０２はＮ種類の探索ベ
クトル群を格納している。

第２１図において、配線処理制御部２１０６は配線処理
の制御を行う部位であり、既設配線パターン展開部２１
０７，探索ベクトル設定部２１０８，経路探索部２　１
’０　９　，経路登録部２１１０を起動する。第２１図
における破線は「起動するＪことを示す。

第２２図において、まず既設配線パターン展開部２１０
７を起動することにより既設配線パターンを格子点情報
テーブル２ｌ１３上に展開し、以下ネット情報ファイル
２１０３に定義された接続点対のそれぞれに対して、ス
テップ２２０４からステップ２２０９までの処理を行う
。次に．ネツト情報ファイル２１０３から、接続点対ｊ
に対して指定された「線幅」を求め（２２０４）．次い
で線幅・探索ベクトル対応ファイル２２０１を参照して
該線幅に対応する探索ベクトル群の番号ｋを求める（２
２０５）．ステップ２２０６では，ステップ２２０５で
求めた番号ｋに対応した探索ベクトル群を探索ベクトル
テーブル２１１１に設定する。

本実施例によれば、接続点対に対して指定された線幅に
応じて配線パターン形状を変えることができるため、配
線領域内のチャネルを有効に使用できるという効果があ
る。というのは、全ての接続点対に対して同一の探索ベ
クトルを定義した場合、広い線幅用の探索ベクトルを採
用せざるを得ないため，配線領域内のチャネルの多くが
むだになるからである。

上記実施例は、線幅に応じて複数の探索ベクトル群を定
義し、接続点対毎に適切な探索ベクトル群を選択する、
というものであるが、下記の如く領域毎に探索ベクトル
群を定義しても良い。たとえば、配線領域のある部分が
バス配線に使用されることが予め決められている場合、
配線領域全体を「バス配線領域」とそれ以外の領域とに
分割し、各々の領域に対して探索ベクトル群を定義する
ことにより、バス配線およびそれ以外の配線のそれぞれ
において適切な形状の配線パターンを生成することがで
きる。

以上述べたように、複数種の探索ベクトル群を用意して
おき，状況に応じて適切な探索ベクトル群を選択するこ
とが本発明により可能である。

以上述べた実施例および変形例では、探索ベクトルを隣
接格子点へ向かうベクトルとして定義しているが、本発
明は，探索ベクトルが隣接格子点へ向かうことに限定す
るものでない。例えば、第２６図に示す如く、探索ベク
トルが複数格子だけ離れた位置へ向かうベクトルであっ
ても良い。第２６図に示す探索ベクトルを定めた場合．
第２７図に示す如く、概ね２格子ずつ探索を進めるため
、配線処理を高速に行えるという効果がある。

次に、本発明の第４の実施例を第３０図から第３３図ま
での図面を用いて説明する。

第３０図は、本実施例に係る配線パターン決定システム
の構成を示すブロック図である。配線パターン決定シス
テムは、ネット情報ファイル３００ｌと配線パターンフ
ァイル３００２と配線禁止・穴明禁止ファイル３００３
とコンピュータ３００４とから成る。コンピュータ３０
０４はオペレーティングシステムと本発明の配線パター
ン決定方法に係る配線パターン決定プログラムとを搭載
する。

配線パターン決定プログラムは、従来の線分探索法に基
づく配線パターン決定プログラムに対して、本実施例に
係る変更を施すことにより作或した。

第３０図において、コンピュータ３００４は、ネット情
報ファイル３００１と、配線パターンファイル３００２
と、配線禁止・穴明禁止ファイル３００３とを参照し、
配線パターン決定処理を行い、結果を配線パターンファ
イル３００３に格納する。第３１図は、コンピュータ３
００４における配線パターン決定処理の処理手順を示す
フローチャートである。

以下第３１図を用いて、配線パターン決定処理を詳細に
説明する。

第３１図において、まず配線の対象である接続点対に対
する略Ｌ字型の簡易パターンを求める（３１０１）。こ
こで略Ｌ字型の簡易パターンとは、第３２図に示す如く
、始点Ｆと終点Ｔとを接続する配線パターンである。第
３２図（ａ）に示すとおり、始点Ｆと終点Ｔとが水平あ
るいは垂直に並んでいない場合は、簡易パターンとして
４通りの配線パターンを用意する。また、始点Ｆと終点
Ｔとが水平あるいは垂直に並んでいる場合は，それぞれ
第３２図（ｂ），（Ｃ）に示すとおり，簡易パターンと
して２通りの配線パターンを用意する。さて、次にステ
ップ３１０１で求めた各簡易パターンについて、簡易パ
ターンにより接続点対が未使用配線領域上で接続できる
か否かを調尺る（３　１　０　２）。ここで、「未使用
配線領域上で接続する」とは、既に設けられた配線パタ
ーン，ピン，ビアホールおよび配線禁止，穴明禁止に重
なること無しに接続することを表わす。もし、接続点対
を接続できる簡易パターンがあれば、それらの簡易パタ
ーンの中で，最短の配線長を有する簡易パターンを、接
続点対に対する配線パターンとして登録する（３　１　
Ｌ　５）。なお、ここまでの処理はパターン限定法によ
る配線処理と同一である。

一方、接続点対を接続できる簡易パターンがなければ、
通常の線分探索法の処理を行う。まず、始点Ｆから仮線
分を発生させる（３　１　０　３）。ここで，仮線分は
第３４図に示す如く，主格子王をはさみポインタによっ
て連なる空き線分８に並行して主格子１上を走る仮想的
な線分である。ここで空き線分８とは、空き格子点を連
ねた線分である。

このように仮線分を定羞することによりベンドが可能と
なる。さて、ステップ３　〕−　０　３の後、このステ
ップで発生させた仮線分が終点に到達するかどうかを調
べる（３↓０４）。もし、終点に到達する仮線分があれ
ば、発見した配線経路すなわち、始点Ｆから終点Ｔに至
るまでの仮線分に沿った空き線分の連なりを、接続点対
に対する配線パターンとして登録する（３１↓８）。一
方、終点に到達する仮線分がなければ、発生した仮線分
を基にして、パターン限定法による配線処理と線分探索
法による配線処理を続ける。すなわち、仮線分選択回数
ｉを初期化した後（３１０５），まず基とすべき仮線分
を１つを選択する（３１０８）．このとき、下式で計算
される値Ｃが最も小さい仮線分を選択する。

Ｃ　”　ｋ　１・確定配線長＋ｋｚ・確定ビアホール数
十ｋｇ・確定ベンド数十ｋ４・予想配線長ここで、確定
配線長，確定ビアホール数，確定ベンド数はそれぞれ、
仮線分を発生させた基点までの配線長，ビアホール数，
ベンド数である。ベンドとは、走行チャネル変更による
折れ曲がりを指す。予想配線長は、仮ビアから終点まで
のマンハッタン距離等で計算される値である。もし、基
点が始点であれば，確定配線長，確定ビアホール数，確
定ベンド数はそれぞれ零となる。さて、仮線分を選択し
た後、選択した仮線分上の主格子交点（主格子が交わる
位置）の中から１点を選択する。格子点は，ＷＩ易パタ
ーンおよび仮線分を発生させる基となる点である。線分
探索法の用語にならい、以後、該格子点を仮ビアと呼ぶ
ことにする。

仮線分から仮ビアを選択する順序を，第３３図を用いて
説明する。同図において、メＬ括弧で囲われた数字が仮
線分を選択する順序を表わす。すなわち，まず（１）で
示される格子点を仮ビアとして選択し、次に、該仮ビア
から終点までの配線処理が達成できなければ（２）で示
される格子点を選択する。仮ビアは配線経路が配線パタ
ーンとして登録される時にビアホールとなる。このため
、仮ビアの位置がビアホールを設定できる位置であるか
否かを調べる（３１０８）。ビアホールを設定どきない
位置であれば、ステップ３１１３を経て他の未だ選択し
ていない格子点を仮ビアとして選択する。もし、ビアホ
ールを設定できる位置であればこの位置から経路探索を
進める。まず、仮ビアと終１’，′ｊ．とが成す区間に
対するｌｌｌ８Ｌ字型の簡易パターンを求める。簡易パ
ターンを求める方法は、接続点対に対する簡易パターン
を求める方法（第３０図）と同様である。もし、選択し
た仮線分上に未だ選択していない格子点がなければ、仮
線分を基とする配線処理を止め、別の仮線分を選択する
。次に簡易パターンの各々についてこの簡易パターンに
より接続点対が未使用配線領域上で接続できるか否かを
調べる（３　１　１　０）。もし、仮線分と終点とを接
続できる簡易パターンがあれば、その中で最も配線長の
短い簡易パターンを、配線パターンとして登録する（３
１１６）、さらに、始点から仮ビアに至るまでの仮線分
を，始点，仮ビア間の配線パターンとして登録する（３
　１　１　７）．一方、接続できる簡易パターンがなけ
れば，仮ビアから仮線分を．発生させる（３１１１）。

もし、発生した仮線分が終点に到達すれば、ステップ３
１１８へ飛び、始点Ｆから終点Ｔに至るまでの仮線分を
、接続点対に対する配線パターンとして登録する。終点
に到達する仮線分がなければ、仮ビアからの経路探索を
終了し、ステップ３工１３を経て他の格子点からの配線
処理へ移る。ステップ３１１３において、もし選択され
た仮線分上に未だ選択されていない格子点がなければ、
仮線分を基とする配線処理を終了し，他の仮線分を基と
する配線処理へ移る。ただし，仮線分を選択した回数ｉ
が許容最大値に達した場合は，配線処理を終了し、接続
点対は未配線とする。

本実施例によれば、ベンドが可能であり、また仮線分の
定義において、処理時間の節約のため空き線分間をポイ
ンタで連結しているため、ビアホールの少ないパターン
を高速に生成できる、という効果がある。また、仮線分
の選択に際して確定配線長や確定ビアホール数等を考慮
しているため、折り曲がりや迂回の少ない配線パターン
を決定できる、という効果がある。更に、仮線分の選択
に際して予想配線長を考慮し，終点から遠い仮線分の選
択を難しくしているため、無駄な配線処理を行わずに，
高速に配線パターンを生威できる、という効果がある。

上記実施例を勘案し、総合的に性能を発揮できる配線パ
ターン決定システムの一実施例を第５の実施例として第
３５図および第３６図を用いて説明する．第３５図は配
線パターン決定システム内のコンピュータに搭載した配
線パターン決定プログラムの構成を示すブロック図、第
３６図は配線制御部３５０１の処理手順を示すフローチ
ャートである。第３５図において、配線パターン決定プ
ログラムは、第４の実施例として記載した配線パターン
決定方法により配線パターンの決定を行う高速線分探索
法配線パターン決定部３５０２と、第２の実施例として
記載した配線パターン決定方法により配線パターンの決
定を行うパターン形状制御迷路法配線パターン決定部３
５０３と、上記２つの配線パターン決定部の起動を制御
する配線制御部３５０１とから戊る．第３６図を用いて
配線制御部３５０１の処理手順を説明する。配線パター
ン決定部の起動は、高速線分探索法（３６０２）　，パ
ターン形状制御迷路法（３６０４）の順で行う。

但し、各配線パターン決定部の起動の前で、未配線の接
続点対の有無を調べ、接続点対が無ければ・処理を終了
する（３６０１．３６０３）。

本実施例によれば、配線パターンが混雑していない状態
で単純な形状の配線パターンを高速に生或する配線パタ
ーン決定方法を用い、配線パターンが混雑してからはパ
ターン形状を制御できる配線パターン決定方法を用いる
ので，配線パターン設計者が定めるパターン仕様を満た
す配線パターンを高速に発生させることができるという
効果がある。

〔発明の効果〕

第１の本発明によれば、探索基点から探索できる格子点
の位置を決定するベクトルを記憶しておき，経路探索部
が該探索ベクトルに沿って経路探索を行うので、配線パ
ターン設計者が定めるパターン仕様を満たす配線パター
ンを生或できる、という効果がある． 第２の本発明によれば、始点若しくは仮線分上の各仮ビ
アから逐一仮線分を発生させる前に，始点若しくは仮ビ
アから即座に接続することのできる略Ｌ字型の簡易パタ
ーンにより配線を試み，また、従来の線分探索法と同程
度の深さまで探索を行うため、従来の線分探索法と同程
度の配線率を短時間で達或することができる，という効
果がある。

第３の本発明によれば、電気的および製造しの問題を解
決しつつ、高速に配線パターンが決定できるシステムを
提供することが可能となる。

【図面の簡単な説明】

第１図は本発明に係る探索ベクトルの概念を示す図，第
２図は本発明の配線パターン決定システムによる配線処
理の例を示す図、第３図は従来の配線パターン形状制御
技術の問題点を示す図、第４図は本発明の第１の実施例
を示す配線パターン決定システムの構成を示すブロック
図、第５図は第４図記載のコンピュータ４１内に設けた
探索ベクトルテーブル４０９のデータ構造を示す図、第
６図はコンピュータ４１内に設けた探索基点テーブル４
１０のデータ構造を示す図、第７図はコンピュータ４１
内に設けた格子点情報テーブル４１１のデータ構造を示
す図．第８図はコンピュータ４１内に設けた経路探索部
４０７の処理手順を示すフローチャート、第９図は第８
図記載のフローチャート内の処理「探索基点の１つから
の経路探索」の許細を示すフローチャ−１−、第上○図
は本発明の第２の実施例を示す配線パターン決定システ
ムの構成を示すブロック図、第１１図は第１０図記載の
配線パターン決定システムの一適用例である、斜め方向
配線層を含む実装系を示す図，第↓２図は第１１図記載
の実装系におけるＸ方向配線層工↓０１に対する探索ベ
ク１〜ルの定義例を示す図、第】−３図は第１１図記栽
の実装系における斜め４５゜方向配線層１１０３に対す
る探索ベクトルの定義例を示す図、第１４図はコンピュ
ータ１０１内に設けた探索ベクトルテーブル１０１１の
データ構造を示す図，第１５図はコンピュータ１０１内
に設けたコストテーブル１０１２のデータ構造を示す図
、第１６図はコンピュータ１０ｌ内に設けた探索基点テ
ーブル１０１３のデータ構造を示す図、第工７図はコン
ピュータ１０１内に設けた格子点情報テーブル１　０　
．１−　４のデータ構逍を示す図、第１８図はコンピュ
ータ１０１内に設けた経路探索部１００９の処理手順を
示すフローチャート、第１９図は第１８図記載のフロー
チャ一ト内の処理「コストが最小の探索基点の１つから
の経路探索」の詳細を示すフローチャート、第２０図は
本発明の第３の実施例を示す配線パターン決定システム
（第２１図記載）が生成した配線パターンを表わす図，
第２１図は本発明の第３の実施例を示す配線パターン決
定システムの構或を示すブロック図、第２２図はコンピ
ュータ２１．１内に設けた配線処理制御部２１０６の処
裡手順を示すフローチャート、第２３図は第２１図記載
のネット情報ファイル２１０３のデータ構造を示す図、
第２４図は第２１図記載の線幅・探索ベク１・ル対応フ
ァイル２ｌ０１のデータ構造を示す図、第２５図は第２
１図記載の探索ベクトルファイル２１０２のデータ構造
を示す図、第２６図は本発明の配線パターン決定方法に
係る探索ベクトルの一例を示す図、第２７図は第２６図
記載の探索ベクトルに沿った経路探索の例を示す図，第
２８図は従来技術である線分探索法による配線処理を示
す図、第２９図は従来技術である線分探索法において用
いる仮線分の定義を示す図、第３０図は本発明の第４の
実施例を示す配線パターン決定システムの構成を示すブ
ロック図、第３１図は第３０図記載のコンピュータ３０
０４における配線パターン決定処理の処理手順を示すフ
ローチャート、４レ 第３２は本発明において用いる簡易パターンを示す図、
第３３図は第３１−図記載のフローチャート中のステッ
プ３１０７を説明するための図、第３４図は本発明にお
いて用いる仮線分の定義を示す図，第３５図は本発明の
第５の実施例を示す配線パターン決定システム内のコン
ピュータに搭載した配線パターン決定プログラムの構或
を示すブロック図，第３６図は第３５図記載の配線パタ
ーン決定プログラム内の配線制御部３　５　０　］．の
処理手順を示す図である。 １・・・主格子，２・・・チャネル、３・・・ピン、４
・・・配線パターン，５・・・探索基点、６・・仮線分
、７・・・仮ビア、８・・・空き線分、９・・・障害物
、】−０・・・ビアホール、■・・・探索ベク１−ル、
Ｎ・・・人カベク１−ル、Ｆ・・始点，Ｔ・・・終点，
Ｋ・・・簡易パターン、Ｐ・・・格子点、Ａ・・・配線
領域、Ｍ・・・主格子交＋’ｔ−ｘ　＋　Ｃ・・・チャ
ネル交第 ２ 図 （ａ） Ｋ 第 １ 図 第 ３ 図 （ａ） 第 ４ 図 第 ６ 図 探累基点テ 第 ７ 図 格子点情報テーブル ４１ 第 ５ 図 （ａ）探索ベクトルテ フル （ｂ）格子屯相対位置 （Ｃ）探索ベクトル 第 ８ 図 第 第１１図 （ａ） １ｌ０１　・・ １ｌ０２・・・ １１０３・・・ １１０４　・・・ Ｘ方向配線層 ｙ方向配線層 斜め４５°方向配線層 斜め１３５°方向配線層 第 １４ 図 第 １６ 図 第 １７ 図 第 １５ 図 第 １８ 図 第 １９ 図 第 ２１ 図 第 ２０ 図 （ａ） 第 ２２ 図 第 ２３ 図 第 ２４ 図 ２１０１ ／ 第 ２７ 図 第 ２６ 図 （ｃ） （ｄ） 第 ２８ 図 （ω （ｂ） ９ 第 ２９ 図 第 ３０ 第 ３２ 図 （ａ） 図 （ａ） 第 ３３ 図 第 ３＋ 図 （ｂ） Ｔ 第 ３５ 図 ３５０ｌ 第 ３６ 図

Claims (7)

【特許請求の範囲】
1. １．複数の接続点を接続するための配線パターンを決定
   する配線パターン決定方法において、ある格子点から探
   索できる他の格子点の位置を決定するベクトルを記憶し
   、上記ベクトルに沿つて経路探索を行うことを特徴とす
   る配線パターン決定方法。
2. ２．特許請求の範囲第１項記載の配線パターン決定方法
   において、上記ベクトルは、探索基点の位置情報をもつ
   ことを特徴とする配線パターン決定方法。
3. ３．特許請求の範囲第１項記載の配線パターン決定方法
   において、上記ベクトルは、探索基点の位置情報と、探
   索基点に経路探索が到達するまでの来歴とをもつことを
   特徴とする配線パターン決定方法。
4. ４．特許請求の範囲第３項記載の配線パターン決定方法
   において、探索基点に探索が到達するまでの来歴として
   、探索基点に到達する直前の格子点から探索基点へ向か
   うベクトルを用いることを特徴とする配線パターン決定
   方法。
5. ５．特許請求の範囲第１項記載の配線パターン決定方法
   において、接続点間の配線パターンを零個以上の斜め方
   向配線層を含む複数の配線層を用いて決定することを特
   徴とする配線パターン決定方法。
6. ６．複数の接続点を接続するための配線パターンを決定
   する配線パターン決定方法において、始点若しくは仮ビ
   アから仮線分を発生させる処理に先立ち、仮ビアと終点
   との位置関係に応じて略Ｌ字型等の形状を成す簡易パタ
   ーンを発生させ、この簡易パターンにより仮ビアと終点
   とが未使用配線領域上で接続可能であるか否かを調べ、
   接続可能な簡易パターンがあれば、接続可能な簡易パタ
   ーンの１つを、仮ビアと終点とを接続する配線パターン
   として採用することを特徴とする配線パターン決定方法
   。
7. ７．複数の接続点を接続するための配線パターンを決定
   する配線パターン決定システムにおいて、特許請求の範
   囲第１項記載の配線パターン決定方法を用いて配線パタ
   ーンを決定する手段と、特許請求の範囲第６項記載の配
   線パターン決定方法を用いて配線パターンを決定する手
   段とを備えたことを特徴とする配線パターン決定システ
   ム。