JPH04102177A - 配線経路探索方法及び装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は情報処理装置を利用した電子回路設計のうち、
特にプリント基板や大規模集積回路の配線パタンを自動
設計するための配線経路探索方法、及び装置に関する。

〔従来の技術〕

従来より、配線経路探索方法の一つとして迷路法とその
改良手法が広く利用されている。迷路法は配線領域を格
子に分割し、結線すべき２点の一方を出発点とし、その
点から配線が通過可能な隣接格子点へ情報を展開してゆ
くことにより目的点までの経路を発見する手法である。

迷路法は経路が存在すれば必ず最短経路を発見するが、
例えば、第１９回デザイン　オートメーション　カンフ
ァレンス（１９８２）、第４２５頁から第４３１頁（１
９ｔｈ　Ｄｅｓｉｇｎ　Ａｕｔｏｍａｔｉｏｎ　Ｃｏｎ
ｆｅｒｅｎｃｅＰｒｏｃｅｅｄｉｎｇ（１９８２）、　
ＰＰ、４２５−ＰＰ、４３１　）に示されるように展開
の際にコストを考慮することにより経路の質（曲がり数
等）を改善する方法が知られている。これは■常に最小
のコストを持つウェーブフロント上の格子点から展開し
、■既にコストが付いている格子点により小さいコスト
が展開された場合には小さいコストに更新することによ
り、最小コストの経路を発見する方法である。展開時の
コストを考慮した迷路法の例を第２図（１）に示す。こ
の図で格子点１２，１３゜１４．２２．５６は配線通過
禁止格子点を表し、その周囲の格子点１１，１５，２１
，２３，２４゜２５．３１，３２，３３，４５，４６，
５５゜６５．６６からの展開コストが周囲に配線通過禁
止格子点が存在しない場合よりも大きい例である。

第２図（１）はコスト値４の格子点からの展開処理を示
す。例えば、格子点３４には下方向からコスト値７、右
方向からコスト値５が展開されるが、上記■の条件によ
りコスト値としては小さい方の５がこの格子点に付加さ
れる。

一方、並列処理により経路を高速に探索する方法も知ら
れている。これには例えば第２４回デザイン　オートメ
ーション　カンファレンス（１９８７）、第８００頁か
ら第８０６頁（Ｄｅｓｉｇｎ　Ａｕｔｏｗｔａｔｉｏｎ
Ｃｏｎｆｅｒｅｎｃｅ　Ｐｒｏｃｅｅｄｉｎｇ（１９８
７Ｌ　ｐｐ、　８００−ＰＰ、８０６）に示されるよう
に展開の処理をパイプラインにより並列に行う方法が知
られている。

しかし並列に処理を行う場合、複数の処理機構の共有す
る情報が同時に参照、更新される場合に正しい値が保た
れない（情報の完全性が保証されない）可能性がある１
例えば第２図（１）では格子点３４には格子点３３から
７、格子点４４から５が展開される。この時、格子点３
４の情報を参照し更新する期間が第２図（３）のように
衝突すると正しい値が付加されない。

この問題に対して１例えばデータベースの管理に用いら
れるように、複数の処理装置からある格子点のデータが
同時に参照される際に、一方の参照のみを許可し、もう
一方の参照は、最初の参照が終了するまで待たせる（ロ
ックする）方法が考えられる。また上記文献によるパイ
プライン型の迷路法処理装置は３段３並列のパイプライ
ンを持つが、パイプラインの各段が同時に同一格子点の
データを参照できるように情報を分割して格納してあり
、並列に行われる部分についてもひとつの格子点に隣接
する格子点に関する処理を並列に行うため同一の格子点
に関する処理が同時に行なわれることは無い。また特開
昭６３−１５３６７に示される様に、展開する方向毎に
並列に処理を行うことにより、情報の完全性を保つ方法
も知られている。

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

上記のように並列に迷路法の処理を行う場合に情報の完
全性を保証する方法はいくつかあるが、ロック機構を設
ける方法では、膨大な量の格子点の各々に対してこのよ
うな処理手段を設けるのは実用的でない。また、上記文
献にあるパイプライン型の迷路法処理装置は処理の並列
性が低いため高速化に限度がある。

特開昭６３−１５３６７に示される方法は、完全性を保
つための特別な機構を持たない並列処理装置においても
実現することができるが、本来並列に処理を行うことが
可能な隣接格子点への処理を分割するため、パイプライ
ン段数は短くなり、入力データ数は４倍に増加するため
並列性が損なわれる。

第３図（１）に示す装置は、入力データ列３１１゜上方
向展開回路３１２．右方向展開回路３１３゜下方向展開
回路３１４．左方向展開回路３１５゜配線領域記憶メモ
リ３１６により構成される。これはデータの完全性の保
証の無い装置の例である。

この装置の場合、第３図（２）に示すように入力データ
数ｎ、各展開回路のパイプライン段数ｐとすると、処理
時間Ｔ１はＴ１＝ｎ＋４ｐで与えられる。これに対し、
特開昭６３−１５３６７に示される方向別展開を第３図
（３）に示す構成の装置で行うと、処理時間Ｔ２はＴ２
＝４ｎ＋４ｐで与えられ、入力データ数ｎが大きくなる
に従い、完全性を保証しない場合に比べて効率が悪くな
る。

本発明の目的は、完全性を保つための特別な機構を持た
ない並列処理装置においても容易に実現が可能で、入力
データ数が多い場合でも効率が悪くならない処理方式、
及びその方式登用いた装置を提供することにある。

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

正しいコストが付かない原因は並列処理における格子点
情報への同時参照、更新にある。本発明では、迷路法の
ウェーブフロントの展開処理では情報が２次元状に配置
されている点と、ウェーブフロント上の格子点の隣接路
−そ点に対してのみ行われる、という処理の規則性に着
目し格子点を一定規則により同一グループ内の格子点同
志が共通の隣接格子点を持たないようなグループに分類
し、グループ毎に並列展開処理を行うことによりコスト
情報の完全性を保証する。

〔作用〕

上記のように迷路法で扱う格子点のグループ分けを行う
と、同じグループに属するどの格子点も互いに同じ隣接
点を共有しないため、ウェーブフロント上の格子点から
それらの隣接格子点に対してのみ行われるコスト展開処
理において、同一グループ内の格子点からの隣接格子点
情報の参照、更新が並列に行われても、任意の隣接格子
点情報に対する参照、更新処理が同時に行われることば
無くなる。これにより並列処理においても最小コスト経
路の探索が保証される。

第３図（５）に示すようにグループ分配回路３５１を設
け、グループ別データ３５２を作成し、グループ毎に処
理することにより、第３図（６）に示すように処理時間
Ｔ３はＴ３＝２ｎ＋２０ｐ＋ｐ′で与えられる。ここで
ｐ′はグループ分配回路のパイプライン段数かつ、ｎ：
ｎｌ＋ｎ２＋ｎ３＋ｎ４＋ｎ５である。このグループ分
は処理によりｐ及びＰ′に対してｎが大きい場合には第
３図（３）に示す方向別展開方式よりも高速に処理する
ことができる。

〔実施例〕

本発明の実施例を第１図、第２図及び第４図。

第５図までを用いて説明する。第２図に示すウェーブフ
ロントの例では前述したように展開処理を並列に行う場
合、コスト値の完全性が保証されない。

コスト情報の完全性を保つためにウェーブフロント上の
格子点を次に示す方法によりグループ分けし、グループ
毎にコスト展開処理を並列に行う。

配線領域が平面格子の場合、第１図のように隣接格子点
を互いに共有しない５つのグループに格子点を分ける。

格子点の座標値（ｘ、ｙ）とグループ番号ＧＲ（０〜４
）の関係は数式で与えられる。

その−例を次に示す。

ＧＲ＝（Ｘ−２Ｙ）　　ｍａｄ　　５ ここでＡ　　ｍｏｄ　　ＢはＡをＢで割った剰余である
。

配線格子が立体の場合は、格子点を７つのグループに分
ける。この場合、グループ番号ＧＲは座標値（Ｘ、Ｙ、
Ｚ）に対して、 ＧＲ＝（Ｘ−４Ｙ＋２Ｚ）　　ｍｏｄ　　７　　で与え
られる。

第２図（２）はウェーブフロント上の格子点のグループ
番号を示した図である。同じグループ番号を持つ格子点
は互いに共通の隣接格子点を持たないことから、グルー
プ別のコスト展開処理ではある格子点に対して、複数の
方向から同時にコスト値の参照、更新が行われることは
無く、コスト情報の完全性を保証できる。

経路探索処理の流れを第４図を用いて説明する。

処理において格子点の情報を保持する格子点情報メモリ
と第５図に示すようにコスト別バッファ５１とグループ
別バッファ５２を用いる。経路探索を開始するに当たり
、配線領域の情報を予め各格子点に格納し、結線すべき
２点のうちの一方を出発点としくもう一方は目標点）、
その座標をコスト値１としてコスト別バッファ５１に保
持する。

また現在の展開格子点のコストを１とし、これを現コス
トと呼ぶ、また各格子点の初期値は無限大とする（第４
図７１）。

格子の座標の中で現コストと同じコスト値を持つ格子点
の情報をグループ分けする（第４図７２）。

第２図に示す例をグループ分けした結果を第５図に示す
。コスト値４のコスト別バッファ内には格子点３１，３
３，４４，５５．６４の座標が入っている。これをグル
ープ分けし、グループ別バッファに入れる。グループＯ
に３１．４４、グループ１に３３．グループ２に６４、
グループ４に５５が入る。

次にグループ毎に展開処理を行う（第４図７３）。

展開処理では、グループ別バッファ内の各座標値につい
て現コストとその座標の示す格子点のコストが等しい格
子点について現コストの格子点に隣接する格子点を求め
、その格子点が展開可能であれば展開時のコストを現コ
ストに加算し、値別にその格子点の座標をコスト別バッ
ファに保持する。

第２図の例では展開処理により第５図に示すようにコス
ト別バッファのコスト値５に３４．４５゜６５、コスト
値７に２１，２３が入る。

展開処理のあと現コストよりも大きいコストを持つ座標
値の数を調べこれが０であれば経路探索処理を終了する
（第４図７４）。この時経路は存在しない。

更に現コストを次に／ＩＸさい値で、かつコスト別バッ
ファ内の要素数が０でない値とする（第４図７５）。

ここで目標点のコストを調べその値が現コストと等しい
かそれより小さければ処理を終了する（第４図７６）。

それ以外の場合は７２以降の処理を繰り返す。

以上の方法により、コスト値の完全性を保証した経路探
索を行うことができる。

次に本発明を実現する装置の例を第６図に示す。

この装置は第６図（１）に示されるように、制御回路１
１．格子点情報メモリ１２．並列コスト展開処理回路１
３．グループ化回路１４．プライオリティキュー構成回
路１５により構成される。

制御回路１１は１３〜ＩＳの各回路の同期を取る他、プ
ライオリティキュー１５に現コストを与え、格子点情報
メモリ１２を参照して目的点のコスト情報を調べ（１６
）その値が現コストと等しいか小さい場合、あるいはプ
ライオリティキュー１５に存在する格子点の座標値の数
を調べ（１７）、その値が０の場合は探索処理を終了す
る。

格子点情報メモリ１２は、配線領域を構成する各格子点
毎に第６図（２）に示す形式で情報を保持する。これら
は展開コスト値１２１．展開方向１２２、配線通過禁止
フラグ１２３．目標点フラグ１２４．配線通過制約条件
１２５により構成される。

並列コスト展開処理回路１３は第６図（３）に示すよう
に展開処理分配回路１３１．展開処理回路群１３２．新
ウェーブフロント収集回路１３３により構成される。展
開処理分配回路１３１はグループ化回路１４より入力さ
れるウェーブフロント上の格子点の座標を展開処理回路
群１３２の各回路に分配する。展開処理回路群１３２の
各回路は格子点の座標からそれに隣接する格子点の位置
を算出し、隣接格子点が展開可能であれば、その座標を
新ウェーブフロント収集回路１３３に出力し、更に格子
点情報のうちの展開コスト値１２１と展開方向１２２を
更新する。展開処理分配回路１３３は各展開処理回路か
ら出力された格子点の座標を順にプライオリティキュー
構成手段１５に出力する。

グループ化回路１４は第６図（４）に示すようにグルー
プ分配回路１４１．グループ番号算出回路１４２．グル
ープ別バッファ１４３．グループ選択回路１４４により
構成される。クループ番号算出回路］２４２によりプラ
イオリテイーキュー構成回路１５より入力される格子点
の座標のグループ番号を求め、その番号によりグループ
分配回路１４１を用いてグループ番号別のバッファ１４
３へ座標を格納する。さらにグループ選択回路１４４は
座標を並列コスト展開回路群１３に出力する。

グループ番号の種類は実施例１に示したように配線領域
が平面の場合は５、立体格子の場合は７である。

プライオリティキュー構成手段１５は第６図（５）に示
すようにコスト分類回路１５１．コスト副バツフア１５
２．コスト選択回路１５３．要素数カウンタ１５４によ
り構成される。コスト分類回路１５１はコスト展開処理
回路１３より入力される座標をコストにより分類しコス
ト別バッファ１５２に格納する。コスト選択回路１５３
は制御回路１１より与えられる現コスト（１，５５）の
値と等しいコスト値の座標をグループ化回路〕４に出力
する。要素数カウンタ１，５４はコスト分類回路１５１
に入力される座標値の数とコスト選択回路１５３から出
力される座標値の数の差を累計することによりコスＩへ
別バッファ１５２に格納されている座標値の数をカラン
１へし、、その値がＯであるか否かを示す信号１５６を
制御回路１１に出力する。

経路探索は、格子点情報に予め配線通過禁止フラグ］２
３．目標点フラグ１２４．配線通過制約条件１２５が付
加され、出発点の座標値がコスト別バッファ１５２に格
納された状態から、要素数カウンタ値を１、現コス１−
を１として開始する。

通常の動作では、現コスト値についてそのコスト値の座
標値をプライオリティキュー構成手段１５からグループ
化回路１４に送りグループ分けし、さらにグループ毎に
並列コスト展開処理回路１３でコスト展開処理を行う。

以上の処理を現コストを順に増やしながら、目標点のコ
ストが現コストと等しいか小さくなる、あるいは、プラ
イオリティキュー構成手段の要素数カウンタの値がＯに
なるまで繰り返す。

本実施例で示した装置において、グループ毎のコスト展
開処理を行うことによりコスト値の完全性を保証した経
路探索を行うことができる。

〔発明の効果〕

本発明で示すように、コスト展開の処理を並列に行う迷
路法で、扱う格子点をグループ分けし、グループ毎のコ
スト展開処理を行うことにより、任意の格子点情報に対
する参照、更新処理が同時に行われることが回避され、
格子点情報の完全性を保証し、かつ最小コスト経路を探
索できる。これにより集積回路やプリント基板などの実
装設計における経路探索処理を並列処理により高速に行
うことができる。また本発明は格子点情報の保持するメ
モリに、同時アクセスを防ぐための特別な機能を持たな
い並列計算装置にも適用ができる。

【図面の簡単な説明】

第１図は本発明によりグループ分は処理を施した格子点
を示す図、第２図（１）はウェーブフロントからの展開
コストの例、（２）はウェーブフロント上の格子点のグ
ループ番号、（３）はコスト値の完全性が保たれない例
、第３図は本発明が解決する課題点について説明した図
、第４図は本発明の実施例の動作を示す図、第５図は本
発明の実施例におけるコスト別バッファとグループ別バ
ッファの例、第６図は本発明を適用した並列迷路性配線
装置の概略図である。 １１・・・制御回路、１２・・・格子点情報メモリ、１
３・・並列コスト展開処理回路、１４・・・グループ化
回路、１５・・・プライオリティキュー構成回路、１６
・・コスト値、１７・・・要素数、３１１・・・入力デ
ータ列、３１２・・・上方向展開回路、３１３・・・右
方向展開回路、３１４・・・下方向展開回路、３］、５
・・・左方向展開回路、３１６・・・配線領域記憶メモ
リ、３５１・・・グループ分配回路、３５２・・・グル
ープ別データ、５１・・・コスト別バッファ、５２・・
・グループ別バッファ、１２〕・・・展開コスト値、１
２２・・・展開方向、１２３・・・配線通過禁止フラグ
、１２４・・・目的点フラグ、１２５・・・配線通過制
約条件。１３１・・・展開処理分配回路、１．３２・・
・展開処理回路群、１．３３−・・新ウェーブフロント
収集回路、１４４・・・グループ分配回路、１４２・・
グループ番号算出回路、１４３・・グループ別バッファ
、１４４・・グループ選択回路、１５１・・コスト分類
回路、１５２・コスト別バッファ、１５３・コスト選択
回路、１５４・・要素数カウンタ、１５５・・・現コス
ト値、１５６要素数カウンタ出力。

Claims (1)

1. 【特許請求の範囲】 １、電気回路の配線経路を探索する方法において、ａ）
   格子状に分割した配線領域の状態を配線領域記憶手段に
   保持し、 ｂ）格子点の座標値を状態別に状態別記憶手段に保持し
   、 ｃ）上記座標値の状態別記憶手段から格子点の座標値を
   取り出し、隣接格子点を互いに共有しないグループに分
   類し、 ｄ）上記分類されたグループ毎に、座標値が示す格子点
   とそれに隣接する格子点の状態を上記配線領域記憶手段
   から取り出し、 ｅ）これらと隣接方向をもとに隣接格子点の次の状態を
   求め、 ｆ）その情報を配線領域記憶手段に格納し、ｇ）隣接格
   子点の座標値を上記状態別記憶手段に格納して格子状態
   を更新し、 ｈ）結線すべき格子点の一方を出発点とし、その点に隣
   接する格子点へ、グループ毎に上記ステップｄ）からｇ
   ）を順次適用することにより目標点までの経路を発見す
   ることを特徴とする配線経路探索方法。 ２、電気回路の配線経路を探索する装置において、格子
   状に分割した配線領域の状態を保持する配線領域メモリ
   と、 格子点の座標値を状態別に保持する状態別メモリと、 上記状態別メモリ内の座標値を取り出し、隣接格子点を
   互いに共有しない格子点のグループに分類する分類機構
   と、 上記分類機構により分けられたグループ毎に座標値が示
   す格子点情報と、それに隣接する格子点の状態を上記配
   線領域メモリから取り出し、これと格子の隣接方向をも
   とに、隣接格子点の次の状態を求め、その情報を配線領
   域メモリに、隣接格子点の座標を上記状態別メモリに挿
   入する処理を行う格子状態更新機構を有することを特徴
   とする配線経路探索装置。