JPH06162146A - 配線処理方式 - Google Patents

Abstract

(57)【要約】 【目的】 迷路法により配線経路を探索する際の処理時
間を短縮する。 【構成】 作業領域５２には前回の探索時に探索された
被探索点が、累積配線コストが小さい順に格納されてい
る。探索手段１は作業領域５２に格納されている各点を
今回の探索開始点とし、累積配線コストが小さいものか
ら順番に、隣接する未探索の点であって、制約条件を満
たす点を探索し、更に被探索点への探索方向を求める。
配線コスト算出手段２は探索手段１が今回探索した各点
の累積配線コストを求める。ソート手段３は探索手段１
が今回探索した被探索点累積配線コストの小さい順にソ
ートし、作業領域５２に格納する。また、ソート手段３
は探索結果テーブル５１に探索手段１が今回探索した点
及びその探索方向を追加する。トレース手段４は探索結
果テーブル５１に格納されている各被探索点及び探索方
向を示す情報に基づいてターゲット点からスタート点へ
の配線経路をトレースする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はＬＳＩ，プリント基板等
の実装設計に於ける配線処理方式に関し、特に、迷路法
により２地点間を接続する配線処理方式に関する。

【０００２】

【従来の技術】従来、ＬＳＩ，プリント基板等に配線を
行なう場合に使用されていた迷路法を、図１６を参照し
て説明する。尚、図１６に於いて網かけ部は配線禁止領
域を示している。

【０００３】先ず、スタート点Ｓにラベル「０」を与え
る。次に、スタート点Ｓと隣接し、且つラベルが付与さ
れていない点ａ，ｂ，ｃ，ｄにラベル「１」を付与す
る。更に、ラベル「１」を付与した点ａ，ｂ，ｃ，ｄと
隣接し、且つラベルが付与されていない点ｅ，ｆ，ｇ，
ｈにラベル「２」を与える。以下、ターゲット点Ｔにラ
ベルを付けるまで、同様の処理を繰り返し行なう。ター
ゲット点Ｔにラベル「９」を付けることにより前進探索
が終了する。この前進探索により、スタート点Ｓとター
ゲット点Ｔとの間に存在する最短経路を全て探索したこ
とになる。

【０００４】前方探索が終了すると、ターゲット点Ｔか
らスタート点Ｓに向かって後退探索を行なう。

【０００５】後退探索に於いては、先ず、ターゲット点
Ｔに隣接するラベル「８」の点であって、制約条件を満
足させる点の内の１点を選択する。今、例えば、制約条
件として連続して曲がることができないという条件が与
えられているとすると、点ｘ，ｙ，ｚは全て制約条件を
満足させているので、点ｘ，ｙ，ｚの内の１つ（例え
ば、点ｙ）が選択されることになる。

【０００６】次いで、点ｙに隣接するラベル「７」の点
であって、制約条件を満たしている点ｔ，ｕの内の１つ
（例えば点ｔ）を選択する。

【０００７】次いで、点ｔに隣接するラベル「６」の点
であって、制約条件を満たしている点の内の１つを選択
する。この例の場合、点ｔに隣接するラベル「６」の点
は２点（点ｑ，ｒ）存在するが、点ｒを選択すると、点
ｙでの曲がりと点ｔでの曲がりとが連続し、制約条件を
満たさないので、点ｑが選択される。

【０００８】次いで、点ｑに隣接するラベル「５」の点
であって、制約条件を満たしている点の内の１つを選択
する。この例の場合、点ｔに隣接するラベル「５」の点
は点ｏだけであり、制約条件を満たしているので、点ｏ
が選択される。

【０００９】次いで、点ｏに隣接するラベル「４」の点
であって、制約条件を満たしている点の内の１つを選択
する。この例の場合、点ｏに隣接するラベル「４」の点
は点ｍだけであるが、点ｍを選択すると、点ｑでの曲が
りと点ｏでの曲がりとが連続してしまい、制約条件を満
たさないので、点ｍを選択することはできない。

【００１０】従って、分岐点ｔまで戻り、前回選択した
点ｑと異なる点ｒを選択することが必要になる。しか
し、点ｒを選択すると、点ｙでの曲がりと点ｔでの曲が
りとが連続してしまうため、点ｒを選択することはでき
ず、更に分岐点ｙまで戻ることが必要になる。

【００１１】点ｙでは前回点ｔを選択したので、今回は
点ｕが選択される。以下、制約条件を満足させるラベル
「６」，「５」，「４」，「３」，「２」，「１」，
「０」の点を順次選択することにより、点ｒ，ｏ，ｍ，
ｊ，ｅ，ａ，Ｓが順次選択される。即ち、スタート点Ｓ
とターゲット点Ｔとを結ぶ経路としてａ，ｅ，ｊ，ｍ，
ｏ，ｒ，ｕ，ｙが選択される。

【００１２】

【発明が解決しようとする課題】上述した従来の迷路法
は前進探索時、スタート点Ｓからターゲット点Ｔまでの
最短経路を可能な限り探索し、後退探索時には分岐点に
於いて１つの経路を選択し、選択した経路が行き詰まっ
た場合、再び分岐点に戻って別の経路を選択するという
無駄な処理を行なうので、処理時間が非常に長くなると
いう問題があった。

【００１３】本発明の目的は処理時間を短縮させること
ができる配線処理方式を提供することにある。

【００１４】

【課題を解決するための手段】本発明は上記目的を達成
するため、（Ａ）前回の被探索点群に含まれる各点を今
回の探索開始点とし、累積配線コストが小さい探索開始
点から順番に、隣接する未探索の点であって、制約条件
を満足させる点を探索すると共に被探索点への探索方向
を求める探索手段と、該探索手段が求めた今回の被探索
点の累積配線コストを算出する配線コスト算出手段と、
前記探索手段が求めた被探索点及び探索方向に基づいて
ターゲット点からスタート点に向かって配線経路をトレ
ースするトレース手段とを設けたものである。

【００１５】また、本発明は上記目的を達成するため、
（Ｂ）前回の被探索点群に含まれる各点を累積配線コス
トの小さい順にソートするソート手段と、前回の被探索
点群に含まれる各点を今回の探索開始点とし、前記ソー
ト手段がソートした順番で、隣接する未探索の点であっ
て、制約条件を満足させる点を探索すると共に被探索点
への探索方向を求める探索手段と、該探索手段が求めた
今回の被探索点の累積配線コストを算出する配線コスト
算出手段と、前記探索手段が求めた被探索点及び探索方
向に基づいてターゲット点からスタート点に向かって配
線経路をトレースするトレース手段とを設けたものであ
る。

【００１６】更に、本発明は上記目的を達成するため、
（Ｃ）前回の被探索点群に含まれる各点の累積配線コス
トと各方向の配線コストとに基づいて前回の被探索点群
に含まれる各点を探索開始点にした時に被探索点がとる
ことができる累積配線コストの範囲を予測し、予測結果
と記憶手段に設けられている部分領域の個数とに基づい
て前記各部分領域に割り当てる累積配線コストを決定す
る配線コスト分割手段と、前記複数の部分領域に格納さ
れている前回の被探索点を今回の探索開始点とし、小さ
い累積配線コストが割り当てられている部分領域に格納
されている点から順番に、隣接する未探索の点であっ
て、制約条件を満足させる点を探索すると共に被探索点
への探索方向を求める探索手段と、該探索手段が今回探
索した被探索点の累積配線コストを算出し、算出した累
積配線コストと前記配線コスト分割手段が決定した前記
各部分領域に割り当てる累積配線コストとによって決ま
る前記部分領域に被探索点を示す情報を格納する配線コ
スト算出手段と、前記探索手段が求めた被探索点及び探
索方向に基づいてターゲット点からスタート点に向かっ
て配線経路をトレースするトレース手段とを設けたもの
である。

【００１７】

【作用】（Ａ）の構成に於いては、探索手段は探索時、
前回探索した被探索点群の各点を探索開始点とする。そ
して、累積配線コストの小さいものから順番に、隣接す
る未探索の点であって、制約条件を満足させる点を探索
する。また、被探索点への探索方向も求める。

【００１８】探索手段が今回探索した被探索点の累積配
線コストが配線コスト算出手段によって算出され、次回
の探索時に使用される。

【００１９】トレース手段は探索手段が求めた被探索点
及び探索方向に基づいてターゲット点からスタート点に
向かって配線経路をトレースする。

【００２０】また、（Ｂ）の構成に於いては、探索時、
累積配線コストの小さい探索開始点から順番に探索処理
を行なうようにするため、探索手段が今回探索した被探
索点を累積配線コストが小さい順にソート手段でソート
しておく。そして、探索手段は次回の探索処理をソート
された順番で行なう。

【００２１】また、（Ｃ）の構成に於いては、探索時、
累積配線コストの小さい探索開始点から順番に探索処理
を行なうために、記憶手段に複数の部分領域を設けてお
く。また、配線コスト分割手段によって、各部分領域に
割り当てる累積配線コストを決定しておき、配線コスト
算出手段は探索手段が探索した被探索点を示す情報を、
その累積配線コストと配線コスト分割手段が決定した各
部分領域に割り当てる累積配線コストに従って該当する
部分領域に格納しておく。

【００２２】そして、探索手段は次回の探索処理を割り
当てられている累積配線コストが小さい部分領域に格納
されている探索開始点から順番に行なう。

【００２３】

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

【００２４】図１は本発明の一実施例のブロック図であ
り、探索手段１と、配線コスト算出手段２と、ソート手
段３と、トレース手段４と、記憶手段５とから構成され
ている。

【００２５】記憶手段５は探索結果テーブル５１と、第
１，第２の作業領域５２，５３とを含んでいる。探索結
果テーブル５１には、図２に示すように、点を示す情報
と、その点が探索されてきた方向を示す情報とが格納さ
れる。

【００２６】探索手段１に入力されている配線情報６に
は配線を行なうプリント基板等に対応した格子の大き
さ，格子上のスタート点Ｓの座標値，格子上のターゲッ
ト点Ｔの座標値，格子上の配線禁止領域の座標値等が含
まれている。また、制約条件７は連続した曲がりを禁止
する等の配線上の制約を指示する情報である。

【００２７】配線コスト算出手段２に入力されている配
線コスト情報８はＸ軸方向の配線の進みにくさ及びＹ軸
方向の配線の進みにくさを示す情報であり、Ｘ軸方向の
配線コストをＸ：αで、Ｙ軸方向の配線コストをＹ：β
で表す。ここで、α，βの値が大きい程、Ｘ，Ｙ軸方向
の配線は進みにくい。

【００２８】次に、配線情報６が図１６に示す情報を表
し、制約条件７が連続して曲がることを禁止し、配線コ
スト情報８がＸ：１，Ｙ：２となっている場合を例にと
って本実施例の動作を説明する。

【００２９】探索手段１は配線情報６，制約条件７が入
力されると、先ず、図２に示す探索結果テーブル５１の
先頭領域にスタート点Ｓを示す情報を書き込む。

【００３０】次いで、探索手段１は第１の作業領域５２
に探索開始点を示す情報としてスタート点Ｓを示す情報
を書込み、更に、スタート点Ｓの累積配線コストが
「０」であることを示す情報及びフラグが「０」である
ことを示す情報を書き込む。この結果、第１の作業領域
５２の内容は図３に示すものとなる。尚、フラグはその
点が探索されてきた方向と、その点の探索開始点が探索
されてきた方向とが等しい場合は「０」、異なる場合は
「１」にされるものである。

【００３１】その後、探索手段１は第１の作業領域５２
に格納されている探索開始点を示す情報の内、未選択の
ものであって最も前に格納されているものを選択する。
この例の場合、第１の作業領域５２には図３に示すよう
に探索開始点を示す情報としてスタート点Ｓを示す情報
しか格納されていないので、探索手段１はスタート点Ｓ
を選択することになる。

【００３２】その後、探索手段１は選択した探索開始点
（スタート点Ｓ）と隣接する未探索の点であって、且つ
制約条件７を満足させる点を探索し、被探索点を示す情
報，被探索点が＋Ｘ，−Ｘ，＋Ｙ，−Ｙの何れの方向か
ら探索されたのかを示す情報，被探索点に対応する探索
開始点を示す情報及び被探索点の探索方向が探索開始点
の探索方向と同じか否かを示すフラグを第２の作業領域
５３に格納する。尚、探索手段１は探索開始点のフラグ
が「０」の場合は、探索開始点と隣接する全ての未探索
の点を制約条件７を満足させる点と判断し、「１」の場
合は探索開始点と隣接する未探索の点の内、探索方向が
探索開始点の探索方向と同じ点のみを制約条件７を満足
させる点と判断するものである。

【００３３】図１６の例の場合、スタート点Ｓと隣接す
る未探索の被探索点は点ａ，ｂ，ｃ，ｄであり、また、
スタート点Ｓのフラグは図３に示すように「０」となっ
ているので、探索手段１は点ａ，ｂ，ｃ，ｄを示す情報
を被探索点を示す情報として第２の作業領域５３に格納
する。また、点ａ，ｂ，ｃ，ｄはそれぞれ−Ｘ，＋Ｘ，
−Ｙ，＋Ｙ方向から探索された点であるので、探索手段
１は点ａ，ｂ，ｃ，ｄを示す情報に対応付けて−Ｘ，＋
Ｘ，−Ｙ，＋Ｙ方向を示す情報を第２の作業領域５３に
格納する。また、被探索点ａ，ｂ，ｃ，ｄに対応する探
索開始点はスタート点Ｓであるので、探索手段１は点
ａ，ｂ，ｃ，ｄを示す情報に対応付けてスタート点Ｓを
示す情報を第２の作業領域５３に格納する。更に、スタ
ート点Ｓは最初の探索開始点であるので、探索手段１は
点ａ，ｂ，ｃ，ｄを示す情報に対応付けてフラグが
「０」であることを示す情報を第２の作業領域５３に格
納する。この結果、第２の作業領域５３の内容は図４に
示すものとなる。

【００３４】上記した処理が終了すると、探索手段１は
第１の作業領域５２を探索し、未探索の探索開始点を探
すが、第１の作業領域５２には既に探索したスタート点
Ｓに関する情報しか格納されていないので、配線コスト
算出手段２を呼び出すことになる。

【００３５】配線コスト算出手段２は探索手段１から呼
び出されると、先ず、第１の作業領域５２を参照し、第
１の作業領域５２の最も前に格納されている探索開始点
を示す情報を選択し、その累積配線コストを取得する。
今、第１の作業領域５２には図３に示すように、探索開
始点を示す情報としてスタート点Ｓを示す情報しか格納
されていないので、配線コスト算出手段２はスタート点
Ｓを示す情報を選択し、その累積配線コスト「０」を取
得する。

【００３６】次いで、配線コスト算出手段２は第２の作
業領域５３を参照し、そこに格納されている被探索点を
示す情報の中から上記選択した探索開始点（スタート点
Ｓ）と対応付けられている情報を選択する。今、第２の
作業領域５３には図４に示すように上記選択されたスタ
ート点Ｓを示す情報と点ａ，ｂ，ｃ，ｄを示す情報とが
対応付けて格納されているので、配線コスト算出手段２
は点ａ，ｂ，ｃ，ｄを示す情報を選択することになる。

【００３７】その後、配線コスト算出手段２は上記取得
した探索開始点（スタート点Ｓ）の累積配線コスト
「０」と各点ａ，ｂ，ｃ，ｄの探索方向に対応する配線
コストとをそれぞれ加算することにより、各点ａ，ｂ，
ｃ，ｄの累積配線コストを算出し、算出した各点ａ，
ｂ，ｃ，ｄの累積配線コストを点ａ，ｂ，ｃ，ｄを示す
情報に対応付けて第２の作業領域５３に格納する。

【００３８】点ａ，ｂの場合、探索方向はそれぞれ−
Ｘ，＋Ｘであり、Ｘ方向の配線コストは「１」である。
また、点ａ，ｂに対応する探索開始点（スタート点Ｓ）
の累積配線コストは上記したように「０」である。従っ
て、点ａ，ｂの累積配線コストは１＋０により共に
「１」となり、第２の作業領域５３に格納される。ま
た、点ｃ，ｄの場合、探索方向はそれぞれ−Ｙ，＋Ｙで
あり、Ｙ方向の配線コストは「２」である。また、点
ｃ，ｄに対応する探索開始点（スタート点Ｓ）の累積配
線コストは上記したように「０」である。従って、点
ｃ，ｄの累積配線コストは２＋０により共に「２」とな
り、第２の作業領域５３に格納される。この結果、第２
の作業領域５３の内容は図５に示すものとなる。

【００３９】点ａ，ｂ，ｃ，ｄの累積配線コストを第２
の作業領域５３に格納すると、配線コスト算出手段２は
第１の作業領域５２に未選択の探索開始点が存在するか
否かを判断する。そして、存在すると判断した場合は、
未選択の探索開始点の内の最も前のものを１つを選択し
て前述したと同様の処理を行ない、存在しないと判断し
た場合はソート手段３を呼び出す。この例の場合、第１
の作業領域５２には探索開始点としてスタート点Ｓしか
格納されておらず、スタート点Ｓは既に選択済みである
ので、配線コスト算出手段２はソート手段３を呼び出す
ことになる。

【００４０】ソート手段３は配線コスト算出手段２から
呼び出されると、図５に示す第２の作業領域５３の内容
を累積配線コストに基づいて昇順にソートする。この例
の場合、ソート後の内容も図５と同じになる。

【００４１】その後、ソート手段３はソート後の第２の
作業領域５３に格納されている点ａ，ｂ，ｃ，ｄを示す
情報、探索方向−Ｘ，＋Ｘ，−Ｙ，＋Ｙ、累積配線コス
ト「１」，「１」，「２」，「２」及びフラグ「０」，
「０」，「０」，「０」を先頭領域から順番に読み出
し、読み出した情報を第１の作業領域５２の先頭領域か
ら順番に書き込む。この結果、第１の作業領域５２の内
容は図６に示すものとなる。

【００４２】また、ソート手段３は第２の作業領域５３
に格納されている点ａ，ｂ，ｃ，ｄを示す情報及び探索
方向−Ｘ，＋Ｘ，−Ｙ，＋Ｙを先頭領域から読み出し、
読み出した情報を探索結果テーブル５１に追加する。

【００４３】上記した処理が終了すると、ソート手段３
は探索手段１を呼び出す。

【００４４】探索手段１はソート手段３から呼び出され
ると、第１の作業領域５２に格納されている探索開始点
を示す情報の内、未選択のものであって最も前に格納さ
れているものを選択する。今、第１の作業領域５２の内
容は図６に示すものになっているので、探索手段１は探
索開始点を示す情報として点ａを示す情報を選択するこ
とになる。

【００４５】その後、探索手段１は選択した探索開始点
（点ａ）と隣接する未探索の点であって、制約条件７を
満足させる点を探索し、被探索点を示す情報，探索方
向，対応する探索開始点を示す情報，フラグを第２の作
業領域５３に格納する。

【００４６】図１６の場合、点ａと隣接する未探索の点
は点ｅ，ｆであり、また、点ａのフラグは図６に示すよ
うに「０」となっており、点ｅ，ｆは共に制約条件７を
満足させているので、探索手段１は点ｅ，ｆを示す情報
を第２の作業領域５３に格納する。また、点ｅ，ｆの探
索方向はそれぞれ−Ｘ，−Ｙであるので、点ｅ，ｆを示
す情報に対応付けて−Ｘ，−Ｙを第２の作業領域５３に
格納する。また、点ｅ，ｆに対応する探索開始点は点ａ
であるので、点ｅ，ｆに対応付けて点ａを示す情報を第
２の作業領域５３に格納する。更に、点ｅ，ｆの探索方
向が−Ｘ，−Ｙ、探索開始点である点ａの探索方向が−
Ｘであるので、点ｅ，ｆのフラグをそれぞれ「０」，
「１」にする。この結果、第２の作業領域５３の内容は
図７に示すものになる。

【００４７】点ａについての処理が終了すると、探索手
段１は第１の作業領域５２に格納されている探索点を示
す情報の内、未選択のものであって最も前に格納されて
いる点ｂを選択する。

【００４８】その後、探索手段１は点ｂと隣接する未探
索の点であって、制約条件７を満足させる点ｇ，ｈを選
択し、その点ｇ，ｈを示す情報、点ｇ，ｈの探索方向が
＋Ｘ，−Ｙであることを示す情報、点ｇ，ｈに対応する
探索開始点が点ｂであること示す情報及び点ｇ，ｈのフ
ラグが「０」，「１」であることを示す情報を第２の作
業領域５３に格納する。この結果、第２の作業領域５３
の内容は図８に示すものとなる。

【００４９】点ｂについての処理が終了すると、探索手
段１は点ｃについて同様の処理を行なう。点ｃの場合、
３つの隣接点Ｓ，ｆ，ｈが存在するが、これらは全て探
索済みであるので、選択手段１は第１の作業領域５２を
参照し、次の点ｄについて処理を行なうことになる。点
ｄの場合は隣接点Ｓが存在するが、これは探索済みであ
るので、探索手段１は第１の作業領域５２を参照するこ
とになる。この時、第１の作業領域５２には未処理の点
が存在しないので、探索手段１は配線コスト算出手段２
を呼び出す。

【００５０】配線コスト算出手段２は探索手段１から呼
び出されると、前述したと同様の処理を行ない、第２の
作業領域５３に格納されている各点ｅ，ｆ，ｇ，ｈの累
積配線コストを算出し、算出した各点ｅ，ｆ，ｇ，ｈの
累積配線コストを第２の作業領域５３に格納する。

【００５１】点ｅの場合、探索方向は−Ｘ、Ｘ方向の配
線コストは「１」、探索開始点（点ａ）の累積配線コス
トは「１」であるので、点ｅの累積配線コストは１＋１
により「２」となる。点ｆの場合、探索方向は−Ｙ、Ｙ
方向の配線コストは「２」、探索開始点（点ａ）の累積
配線コストは「１」であるので、点ｆの累積配線コスト
は２＋１により「３」となる。点ｇの場合、探索方向は
＋Ｘ、Ｘ方向の配線コストは「１」、探索開始点（点
ｂ）の累積配線コストは「１」であるので、点ｇの累積
配線コストは１＋１により「２」となる。点ｈの場合、
探索方向は−Ｙ、Ｙ方向の配線コストは「２」、探索開
始点（点ｂ）の累積配線コストは「１」であるので、点
ｈの累積配線コストは２＋１により「３」となる。この
結果、第２の作業領域５３の内容は図９に示すものとな
る。

【００５２】上記した処理が終了すると、配線コスト算
出手段２はソート手段３を呼び出す。

【００５３】ソート手段３は配線コスト算出手段２から
呼び出されると、図９に示す第２の作業領域５３の内容
を累積配線コストに基づいて昇順にソートする。この結
果、第２の作業領域５３の内容は図１０に示すものとな
る。

【００５４】その後、ソート手段３はソート後の第２の
作業領域５３に格納されている点ｅ，ｇ，ｆ，ｈを示す
情報、探索方向−Ｘ，＋Ｘ，−Ｙ，−Ｙ、累積配線コス
ト「２」，「２」，「３」，「３」及びフラグ「０」，
「０」，「０」，「０」を先頭領域から順番に読み出
し、読み出した情報を第１の作業領域５２の先頭領域か
ら順番に書き込む。この結果、第１の作業領域５２の内
容は図１１に示すものとなる。

【００５５】また、ソート手段３は第２の作業領域５３
に格納されている点ｅ，ｇ，ｆ，ｈを示す情報及び探索
方向−Ｘ，＋Ｘ，−Ｙ，−Ｙを先頭領域から読み出し、
読み出した情報を探索結果テーブル５１に追加する。

【００５６】上記した処理が終了すると、ソート手段３
は探索手段１を呼び出す。

【００５７】以下、ターゲット点Ｔに到達するまで、探
索手段１，配線コスト算出手段２，ソート手段３により
前述したと同様の処理が行なわれ、探索結果テーブル５
１の内容が図２に示すものとなる。また、ターゲット点
Ｔに到達すると、探索手段１はトレース手段４を呼び出
す。

【００５８】トレース手段４は探索手段１から呼び出さ
れると、図２に示す内容を有する探索結果テーブル５１
に基づいてターゲット点Ｔからスタート点Ｓに向かって
経路をトレースする。

【００５９】ターゲット点Ｔの探索方向は＋Ｙであるの
で、点ｘから探索されてきたことが判る。点ｘの探索方
向は＋Ｘであるので、点ｔから探索されてきたことが判
る。点ｔの探索方向は＋Ｘであるので、点ｒから探索さ
れてきたことが判る。点ｒの探索方向は＋Ｙであるの
で、点ｏから探索されてきたことが判る。点ｏの探索方
向は＋Ｙであるので、点ｍから探索されてきたことが判
る。点ｍの探索方向は＋ｍであるので、点ｊから探索さ
れてきたことが判る。点ｊの探索方向は＋Ｙであるの
で、点ｅから探索されてきたことが判る。点ｅの探索方
向は−Ｘであるので、点ａから探索されてきたことが判
る。点ａの探索方向は−Ｘであるので、スタート点Ｓか
ら探索されてきたことが判る。このようにして、トレー
ス手段４はスタート点Ｓ→点ａ→点ｅ→点ｊ→点ｍ→点
ｏ→点ｒ→点ｔ→点ｘ→ターゲット点Ｔという経路を発
見する。本実施例では２次元座標を用いて１層配線の場
合を示したが、これを３次元座標に拡張すれば、多層配
線にも適用することが可能である。

【００６０】図１２は本発明の他の実施例のブロック図
であり、配線コスト分割手段２１と、探索手段２２と、
配線コスト算出手段２３と、トレース手段２４と、記憶
手段２５とから構成されている。

【００６１】記憶手段２５には探索結果テーブル５１
と、第１，第２の作業領域２５２，２５３とが設けられ
ている。探索結果テーブル５１には、図２に示すよう
に、点を示す情報と、その点が探索されてきた方向を示
す情報とが格納される。また、第１の作業領域２５２は
４つの部分領域２５２ａ〜２５２ｄから構成され、第２
の作業領域２５３も４つの部分領域２５３ａ〜２５３ｄ
から構成されている。

【００６２】配線情報２６，制約条件２７，配線コスト
情報２８は図１の配線情報６，制約条件７，配線コスト
情報８と同様のものである。

【００６３】次に、配線情報２６が図１６に示す情報を
表し、制約条件２７が連続して曲がることを禁止し、配
線コスト情報２８がＸ：１，Ｙ：２となっている場合を
例にとって本実施例の動作を説明する。

【００６４】配線コスト分割手段２１は配線情報２６が
入力されると、先ず、図２に示す探索結果テーブル５１
の先頭領域にスタート点Ｓを示す情報を書き込む。

【００６５】次いで、配線コスト分割手段２１は第１の
作業領域２５２の部分領域２５２ａに探索開始点を示す
情報としてスタート点Ｓを示す情報，スタート点Ｓの累
積配線コストが「０」であることを示す情報及びフラグ
が「０」であることを示す情報を書き込む。この結果、
第１の作業領域２５２の内容は図１３に示すものとな
る。

【００６６】その後、配線コスト分割手段２１は第１の
作業領域２５２に格納されている探索開始点の累積配線
コストの内、最小値と最大値とを取得する。尚、第１の
作業領域２５２に格納されている探索開始点の累積配線
コストが全て同じである場合は、その値を最小値，最大
値として取得する。この時、第１の作業領域２５２には
図１３に示すように、部分領域２５２ａにスタート点Ｓ
の累積配線コスト「０」しか格納されていないので、配
線コスト分割手段２１はスタート点Ｓの累積配線コスト
「０」を最小値，最大値として取得する。

【００６７】スタート点Ｓの累積配線コスト「０」を最
小値，最大値として取得すると、配線コスト分割手段２
１は取得したスタート点Ｓの累積配線コスト「０」と配
線コスト情報２８とに基づいて、スタート点Ｓを探索開
始点とした時に被探索点がとることができる累積配線コ
ストの最小値，最大値を予測する。この例の場合、探索
開始点（スタート点Ｓ）の累積配線コストの最小値，最
大値は「０」であり、配線コスト情報２８が示す配線コ
ストの最小値，最大値はそれぞれ「１」，「２」である
ので、被探索点がとることができる累積配線コストの最
小値，最大値は０＋１＝１，０＋２＝２となる。

【００６８】その後、配線コスト分割手段２１は予測し
た最大値から予測した最小値を減算した値に「１」を加
算し、更に、加算結果を部分領域２５３ａ〜２５３ｄの
個数４で除算する。そして、除算結果に余りがない場合
は商を、除算結果に余りがある場合は商に「１」を加算
した値を各部分領域２５３ａ〜２５３ｄに割り当てる累
積配線コストの範囲とする。

【００６９】この例の場合、２÷４＝０余り２となるの
で、各部分領域２５３ａ〜２５３ｄに割り当てる累積配
線コストの範囲は「１」となる。

【００７０】その後、配線コスト分割手段２１は各部分
領域２５３ａ〜２５３ｄに割り当てる累積配線コスト
を、上記した累積配線コストの範囲と予測した累積配線
コストの最小値，最大値とに基づいて求める。即ち、各
部分領域２５３ａ〜２５３ｄに割り当てる累積配線コス
トの範囲は「１」であり、予測した累積配線コストの最
小値が「１」であることから、第１番目の部分領域２５
３ａには累積配線コスト「１」を割り当て、第２番目の
部分領域２５３ｂには累積配線コスト「２」を割り当て
る。第３番目，第４番目の部分領域２５３ｃ，２５３ｄ
は、第１番目，第２番目の部分領域２５３ａ，２５３ｂ
だけで累積配線コストの割り当てが終了しているので、
未使用とする。

【００７１】配線コスト分割手段２１は各部分領域２５
３ａ〜２５３ｄに割り当てる累積配線コストを決定する
と、そのことを示すコスト割り当て情報（部分領域２５
３ａに割り当てる累積配線コストを「１」にし、部分領
域２５３ｂに割り当てる累積配線コストを「２」にし、
部分領域２５３ｃ，２５３ｄを未使用にする）を配線コ
スト算出手段２３に送ると共に、探索手段２２を呼び出
し、探索開始点に関する情報が第１の作業領域２５２に
格納されていることを示す情報を渡す。

【００７２】探索手段２２は上記情報が渡されると、第
１の作業領域２５２に格納されている探索開始点を示す
情報の内、未選択のものであって、最も前に格納されて
いるものを選択する。この時、第１の作業領域２５２に
は、図１３に示すように、探索開始点を示す情報として
スタート点Ｓの情報しか格納されていないので、探索手
段２２はスタート点Ｓを選択することになる。

【００７３】その後、探索手段２２は選択した探索開始
点（スタート点Ｓ）と隣接する未探索の点であって、且
つ制約条件２７を満足させる点を探索し、被探索点を示
す情報，被探索点が＋Ｘ，−Ｘ，＋Ｙ，−Ｙの何れの方
向から探索されてきたのかを示す情報，被探索点に対応
する探索開始点を示す情報及び被探索点の探索方向が探
索開始点の探索方向と同じか否かを示すフラグを配線コ
スト算出手段２３に渡す。

【００７４】図１６の例に於いては、スタート点Ｓと隣
接する未探索の点は点ａ，ｂ，ｃ，ｄであり、また、ス
タート点Ｓのフラグは図１３に示すように「０」となっ
ているので、探索手段２２は点ａ，ｂ，ｃ，ｄを被探索
点とし、それらを示す情報を配線コスト算出手段２３に
渡す。また、点ａ，ｂ，ｃ，ｄはそれぞれ−Ｘ，＋Ｘ，
−Ｙ，＋Ｙ方向から探索されてきた点であるので、探索
手段２２は点ａ，ｂ，ｃ，ｄを示す情報に対応付けて−
Ｘ，＋Ｘ，−Ｙ，＋Ｙを示す情報を配線コスト算出手段
２３に渡す。また、点ａ，ｂ，ｃ，ｄに対応する探索開
始点はスタート点Ｓであるので、探索手段２２は点ａ，
ｂ，ｃ，ｄを示す情報に対応付けてスタート点Ｓを示す
情報を配線コスト算出手段２３に渡す。更に、スタート
点Ｓは最初の探索開始点であるので、探索手段２２は点
ａ，ｂ，ｃ，ｄを示す情報に対応付けてフラグが「０」
であることを示す情報を配線コスト算出手段２３に渡
す。

【００７５】上記した処理が終了すると、探索手段２２
は第１の作業領域２５２を探索し、未探索の探索開始点
を探すが、この時、第１の作業領域２５２には、図１３
に示すように、探索済みのスタート点Ｓに関する情報し
か格納されていないので、配線コスト算出手段２３に情
報の転送が終了したことを通知する。

【００７６】配線コスト算出手段２３は探索手段２２か
ら被探索点を示す情報，被探索点の探索方向を示す情
報，被探索点に対応する探索開始点を示す情報及び被探
索点のフラグを示す情報が送られてくると、先ず、上記
各情報と配線コスト情報２８とに基づいて被探索点の累
積配線コストを求め、次いで求めた累積配線コストの値
と配線コスト分割手段２１から送られてきている第２の
作業領域２５３に対するコスト割り当て情報とに基づい
て上記各情報を部分領域２５３ａ〜２５３ｄの何れかに
格納する。

【００７７】点ａの場合は、探索方向が−Ｘ、Ｘ方向の
配線コストが「１」、対応する探索開始点（スタート点
Ｓ）の累積配線コストが「０」であるので、１＋０＝１
により、点ａの累積配線コストは「１」となる。また、
配線コスト分割手段２１から送られてきているコスト割
り当て情報は部分領域２５３ａに累積配線コスト「１」
を割り当てることを指示しているので、配線コスト算出
手段２３は点ａを示す情報に対応付けて累積配線コスト
「１」，探索方向−Ｘ，探索開始点（スタート点Ｓ），
フラグ「０」を示す情報を部分領域２５３ａに格納する
ことになる。また、点ｂの場合も累積配線コストが
「１」となるので、配線コスト算出手段２３は点ｂに関
する情報を部分領域２５３ａに格納する。

【００７８】これに対して、点ｃの場合は、探索方向が
−Ｙ、Ｙ方向の配線コストが「２」、対応する探索開始
点（スタート点Ｓ）の累積配線コストが「０」であるの
で、２＋０＝２により、点ｃの累積配線コストは「２」
となる。また、配線コスト分割手段２１から送られてき
ているコスト割り当て情報は部分領域２５３ｂに累積配
線コスト「２」を割り当てることを指示しているので、
配線コスト算出手段２３は点ｃを示す情報に対応付けて
累積配線コスト「２」，探索方向−Ｙ，探索開始点（ス
タート点Ｓ），フラグ「０」を示す情報を部分領域２５
３ｂに格納することになる。また、点ｄの場合も累積配
線コストが「２」となるので、配線コスト算出手段２３
は点ｄに関する情報を部分領域２５３ｂに格納すること
になる。この結果、第２の作業領域２５３の内容は図１
４に示すものとなる。

【００７９】配線コスト算出手段２３は上記した処理が
終了し、且つ探索手段２２から情報転送が終了したこと
を通知されると、第２の作業領域２５３の内容の内、点
を示す情報と探索方向を示す情報とを作業領域２５３に
格納されている順番で探索結果テーブル５１に追加す
る。その後、配線コスト算出手段２３は配線コスト分割
手段２１を呼び出す。

【００８０】配線コスト分割手段２１は配線コスト算出
手段２３から呼び出されると、今回は第２の作業領域２
５３に格納されている各点を探索開始点として前述した
と同様の処理を行なう。

【００８１】まず、配線コスト分割手段２１は第２の作
業領域２５３に格納されている累積配線コストの最小
値，最大値を取得する。今、第２の作業領域２５３の内
容は図１４に示すものになっているので、最小値，最大
値はそれぞれ「１」，「２」となる。

【００８２】次に、第２の作業領域２５３に格納されて
いる各点ａ，ｂ，ｃ，ｄを探索開始点とした場合に被探
索点がとることができる累積配線コストの最小値，最大
値を予測する。これは配線コスト情報２８の最小値，最
大値がそれぞれ「１」，「２」であり、また、第２の作
業領域２５３に格納されている探索開始点の累積配線コ
ストの最小値，最大値がそれぞれ「１」，「２」である
ことから、被探索点がとることができる累積配線コスト
の最小値，最大値をそれぞれ１＋１＝２，２＋２＝４と
予測する。

【００８３】次に、第１の作業領域２５２の各部分領域
２５２ａ〜２５２ｄに割り当てる累積配線コストを前述
したと同様にして求める。この場合、部分領域２５２ａ
には累積配線コスト「２」が、部分領域２５２ｂには累
積配線コスト「３」が、部分領域２５２ｃには累積配線
コスト「４」が割り当てられ、部分領域２５２ｄは未使
用にされる。

【００８４】その後、配線コスト分割手段２１は部分領
域２５２ａ，２５２ｂ，２５２ｃにそれぞれ累積配線コ
スト「２」，「３」，「４」を割り当て、部分領域２５
２ｄを未使用にすることを示すコスト割り当て情報を配
線コスト算出手段２３に渡し、更に、探索手段２２を呼
び出し、探索開始点に関する情報が第２の作業領域２５
３に格納されていることを通知する。

【００８５】探索手段２２は上記情報が渡されると、第
２の作業領域２５３に格納されている探索開始点に関す
る情報の内、未選択のものであって、最も前に格納され
ているものを選択する。この時、第２の作業領域２５３
の内容は図１４に示すものとなっているので、探索手段
２２は点ａに関する情報を探索開始点として選択するこ
とになる。

【００８６】その後、探索手段２２は選択した探索開始
点（点ａ）と隣接する未探索の点であって、且つ制約条
件２７を満足させる点ｅ，ｆを探し、その点ｅ，ｆを示
す情報、点ｅ，ｆの探索方向−Ｘ，−Ｙ、点ｅ，ｆの探
索開始点（点ａ）、点ｅ，ｆのフラグ「０」を配線コス
ト算出手段２３に渡す。

【００８７】点ａについての処理が終了すると、探索手
段２２は点ｂについて同様の処理を行ない、点ｇ，ｈを
示す情報、点ｇ，ｈの探索方向＋Ｘ，−Ｙ、点ｇ，ｈの
探索開始点（点ｂ）、点ｅ，ｆのフラグ「０」を配線コ
スト算出手段２３に渡す。

【００８８】点ｂについての処理が終了すると、探索手
段２２は点ｃについて同様の処理を行なうが、点ｃに隣
接する未探索の点は存在しないので、点ｄについての処
理を開始することになる。点ｄにも隣接する未探索の点
は存在しないので、探索手段２２は未探索の点を選択し
ようとするが、第２の作業領域２５３に格納されている
点ａ，ｂ，ｃ，ｄは全て選択済みなので、探索手段２２
は情報の転送が終了したことを配線コスト算出手段２３
に通知することになる。

【００８９】配線コスト算出手段２３は探索手段２２か
ら点ｅに関する情報が渡されると、点ｅの累積配線コス
トを求める。点ｅの場合、探索方向が−Ｘ、配線コスト
情報２８によって示されるＸ方向の配線コストが
「１」、点ｅに対応する探索開始点ａの累積配線コスト
が「１」であるので、点ｅの累積配線コストは１＋１＝
２となる。

【００９０】更に、配線コスト算出手段２３は配線コス
ト分割手段２１から送られてきているコスト割り当て情
報によって累積配線コスト「２」を部分領域２５２ａに
割り当てることが指示されているので、点ｅを示す情
報、点ｅの探索方向−Ｘを示す情報、点ｅの累積配線コ
スト「２」を示す情報、点ｅの探索開始点（点ａ）を示
す情報及び点ｅのフラグ「０」を示す情報を部分領域２
５２ａに格納する。

【００９１】その後、配線コスト算出手段２３は探索手
段２２から渡された点ｆに関する情報についても同様の
処理を行なう。点ｆの累積配線コストは「３」となり、
配線コスト分割手段２１から送られてきているコスト割
り当て情報は累積配線コスト「３」を部分領域２５２ｂ
に割り当てることを指示しているので、配線コスト算出
手段２３は点ｆを示す情報、点ｆの累積配線コスト
「３」を示す情報、点ｆの探索開始点（点ａ）を示す情
報、点ｆの探索方向−Ｙを示す情報、点ｆのフラグ
「０」を示す情報を部分領域２５２ｂに格納する。

【００９２】更に、配線コスト算出手段２３は探索手段
２２から渡された点ｇ，ｈに関する情報についても同様
の処理を行なう。この結果、第１の作業領域２５２の内
容は図１５に示すものとなる。

【００９３】その後、配線コスト算出手段２３は第１の
作業領域２５２の内容の内、点を示す情報と探索方向を
示す情報とを、作業領域２５２に格納されている順番
で、探索結果テーブル５１に追加する。その後、配線コ
スト算出手段２３は配線コスト分割手段２１を呼び出
す。

【００９４】以下、ターゲット点Ｔに到達するまで、配
線コスト分割手段２１，探索手段２２，配線コスト算出
手段２３により前述したと同様の処理が行なわれ、探索
結果テーブル５１の内容が図２に示すものとなる。ま
た、ターゲット点Ｔに到達すると、配線コスト分割手段
２１はトレース手段２４を呼び出す。

【００９５】トレース手段２４は配線コスト分割手段２
１から呼び出されると、図２に示す内容を有する探索結
果テーブル５１に基づいてターゲット点Ｔからスタート
点Ｓに向かって経路をトレースする。そして、スタート
点Ｓ→点ａ→点ｅ→点ｊ→点ｍ→点ｏ→点ｒ→点ｔ→点
ｘ→ターゲット点Ｔという経路を発見する。本実施例で
は２次元座標を用いて１層配線の場合を示したが、これ
を３次元座標に拡張すれば、多層配線にも適用すること
が可能である。

【００９６】

【発明の効果】以上説明したように本発明は、スタート
点からターゲット点に向かって配線経路を探索する際、
制約条件を考慮すると共に、配線コストを利用して複数
存在する配線経路の内の１つだけを求めるので、ターゲ
ット点からスタート点に向かって配線経路をトレースす
る際、従来方式のように行き詰ることがなく、従って処
理時間を短いものにすることができる効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例のブロック図である。

【図２】探索結果テーブル５１の内容例を示す図であ
る。

【図３】第１の作業領域５２の内容例を示す図である。

【図４】第２の作業領域５３の内容例を示す図である。

【図５】第２の作業領域５３の内容例を示す図である。

【図６】第１の作業領域５２の内容例を示す図である。

【図７】第２の作業領域５３の内容例を示す図である。

【図８】第２の作業領域５３の内容例を示す図である。

【図９】第２の作業領域５３の内容例を示す図である。

【図１０】第２の作業領域５３の内容例を示す図であ
る。

【図１１】第１の作業領域５２の内容例を示す図であ
る。

【図１２】本発明の他の実施例のブロック図である。

【図１３】第１の作業領域２５２の内容例を示す図であ
る。

【図１４】第２の作業領域２５３の内容例を示す図であ
る。

【図１５】第１の作業領域２５２の内容例を示す図であ
る。

【図１６】配線を行なう格子を示した図である。

【符号の説明】

１，２２…探索手段 ２，２３…配線コスト算出手段 ３…ソート手段 ４，２４…トレース手段 ５，２５…記憶手段 ５１…探索結果テーブル ５２，５３，２５２，２５３…作業領域 ６，２６…配線情報 ７，２７…制約条件 ８，２８…配線コスト情報 ２１…配線コスト分割手段

Claims (3)

【特許請求の範囲】
1. 【請求項１】 前回の被探索点群に含まれる各点を今回
   の探索開始点とし、累積配線コストが小さい探索開始点
   から順番に、隣接する未探索の点であって、制約条件を
   満足させる点を探索すると共に被探索点への探索方向を
   求める探索手段と、 該探索手段が求めた今回の被探索点の累積配線コストを
   算出する配線コスト算出手段と、 前記探索手段が求めた被探索点及び探索方向に基づいて
   ターゲット点からスタート点に向かって配線経路をトレ
   ースするトレース手段とを備えたことを特徴とする配線
   処理方式。
2. 【請求項２】 前回の被探索点群に含まれる各点を累積
   配線コストの小さい順にソートするソート手段と、 前回の被探索点群に含まれる各点を今回の探索開始点と
   し、前記ソート手段がソートした順番で、隣接する未探
   索の点であって、制約条件を満足させる点を探索すると
   共に被探索点への探索方向を求める探索手段と、 該探索手段が求めた今回の被探索点の累積配線コストを
   算出する配線コスト算出手段と、 前記探索手段が求めた被探索点及び探索方向に基づいて
   ターゲット点からスタート点に向かって配線経路をトレ
   ースするトレース手段とを備えたことを特徴とする配線
   処理方式。
3. 【請求項３】 前回の被探索点群に含まれる各点の累積
   配線コストと各方向の配線コストとに基づいて前回の被
   探索点群に含まれる各点を探索開始点にした時に被探索
   点がとることができる累積配線コストの範囲を予測し、
   予測結果と記憶手段に設けられている部分領域の個数と
   に基づいて前記各部分領域に割り当てる累積配線コスト
   を決定する配線コスト分割手段と、 前記複数の部分領域に格納されている前回の被探索点を
   今回の探索開始点とし、小さい累積配線コストが割り当
   てられている部分領域に格納されている点から順番に、
   隣接する未探索の点であって、制約条件を満足させる点
   を探索すると共に被探索点への探索方向を求める探索手
   段と、 該探索手段が今回探索した被探索点の累積配線コストを
   算出し、算出した累積配線コストと前記配線コスト分割
   手段が決定した前記各部分領域に割り当てる累積配線コ
   ストとによって決まる前記部分領域に被探索点を示す情
   報を格納する配線コスト算出手段と、 前記探索手段が求めた被探索点及び探索方向に基づいて
   ターゲット点からスタート点に向かって配線経路をトレ
   ースするトレース手段とを備えたことを特徴とする配線
   処理方式。