JPH04107683A - 配線経路探索方式および装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、回路配線設計を支援するための配線経路探索
方式およびその装置に関し、特に、電気＠Ｎを実装する
プリント板、ＬＳＩ素子間などの配線経路を決定するた
めの配線経路探索方式およびその装置に関する。

（従来の技術） 従来、配線経路探索方式の一つとして迷路法がよく知ら
れている。この３！！路法では、配ｖＡ禁止の情報を、
ビット・マツプに展開し、マツプ画像データとして、イ
メージ・メモリに記憶し、与えられた配線の始点、終点
のピン・ペア情報を用い、１ピン・ペア毎に始点からマ
ツプ上で４方向、例えば東西南北の４方向に対し、配線
が引けるかどうか即ち既配線と衝突するかどうかまたは
配線禁止領域かどうかをマツプ情報を参照して更新し、
配線の始点からの探索した順にラベル付けする拡散処理
を施し、配線の終点まで到達したら拡散処理を終了し、
逆に終点から始点の方向にラベルをたど４ことにより配
線経路を決定する。

イメージ・メモリには、各セルにおける情報としてマツ
プ情報の他にピン・ペア情報が記憶し、保持されている
。１セル分のマツプ情報のみを示すと第６図のようにな
っている。

第６図において、４０１はスルー・ホール配線に関する
いわゆるビアに関する情報であり、該情報は、異なる配
線層間を接続するビアが使えるときに“１′°であり、
使えないときに“０”である。

４０２は配線禁止に関する情報であり、該情報は、配線
禁止のときに“１”であり、配線層のときに“Ｏ”であ
る、４０３は配線経路に関する情報であり、該情報は、
配線経路が発見できたときに“１″となり、そうでない
ときに“０”となる。

４０４は始点からの波の伝搬距離をあられすラベルが格
納される。このラベルには距離に対応するように、例え
ば、１，２．・・・ｎのように前後関係がわかる数また
は記号が用いられる。

実際には上で述べたピン・ペア・アドレス計算、拡散、
バック・トレースの他に次のピン・ペアに対する処理を
行うための準備として、マツダ情報の一部であるラベル
を初期状態に戻すクリア処理が必要であり、これらの一
連の処理をピン・ペアの本数たけ峰り返す。

上述の拡散処理において、第７図（ａ）に示すように、
始点を中心として隣接する４方内への探索が行われる。

次に、第７図（ｂ）を参照するに、その４方向のうち配
線が可能なセルを新たに始点として、更にその隣接４近
傍へと波が広がるように探索する処理が行われる。

第７図において矢印は波の拡散方向を示す。斜線部分は
拡散における波の広がりのそれぞれのステップでの波頭
（以下、「ウェーブ・フロント」と称す。ンを示す。こ
の波が隣接セルに対し１回拡散する処理は１ウエーブ・
フロント処理と呼ばれ、障害物がなければ、１つのウェ
ーブ・フロントに含まれるセルの数は始点から数えて１
，４８．１２，１６．・・・のように増大する。このと
き第ｎ番目のウェーブ・フロントは始点からの距離ｎの
セルを探索することになる。

このようにして、波が終点に到達したとすると、その波
の通ったところを逆にたどって得られる経路は、始点と
終点を結ぶ最短経路である。従って、迷路法によれば、
始点と終点を結ぶ経路が存在すれば、該経路を必ず発見
することができ、また、最短な経路を得ることができる
。

（発明が解決しようとする課題） しかし、ウェーブ・フロント中の複数のセルについて拡
散処理を並列に実行しようとした場合、第７図（ｂ）の
７０の様に、拡散した先のセル同志が衝突する可能性が
あるから、拡散処理を並列に実行することは困難である
。

本発明の目的は、ウェーブ・フロント中の複数のセルに
ついて拡散処理を並列に実行することができる配線経路
探索方式および装置を提供することにある。

（課題を解決するための手段） 本発明は、配線の間隔を単位とする格子状に分割された
配線領域を示すマツプ上で、波状に配線経路を探索する
ことによって回路配線経路を求める配置経路探索方式で
あって、配線の始点、終点を示すピン・ペア情報、マツ
プ情報、及びウェーブ・フロント・アドレスを記憶し、
保持する手段と、 配線の始点、終点の情報からマツプの実アドレスを生成
する手段と、 マツプの実アドレスに基づき、４方位の各方向近傍のセ
ル・アドレスを生成し、マツプ情報の参照、更新等の拡
散処理を行う手段と、 拡散に成功したセルのアドレスを、次の拡散処理が並列
に実行できるもの毎に分類しながら、複数のウェーブ・
フロントに書き込む手段と、複数のウェーブ・フロント
を、１つずつ順に処理する手段と、 １つのウェーブ・フロント内の各セルについて並列に拡
散処理を行う手段と を備えることを特徴とする。

本発明の配線経路探索装置は、すくなく・とも、配線の
始点、終点を示すピン・ペア情報、マツプ情報、ウェー
ブ・フロント・アドレスを記憶し、保持する碑メージ・
メモリと、 配線の始点、終点の情報から該イメージ・メモリのマツ
プの実アドレスを生成するピン・ペア・アドレス処理部
と、 該ピン・ペア・アドレス処理部、またはウェーブ・フロ
ントから得られるマツダの実アドレスに基づき、４方位
の各近傍のセル・アドレスを生成し　イメージ・メモリ
のマツプ情報を参照し、波が拡散可能なセルについてマ
ツプ情報を更新する拡散処理と共に、該セルのアドレス
を次回の拡散時に同時に処理できるもの毎に分類しなが
ら複数のウェーブ・フロントに書き込む分類処理を各ウ
ェーブ・フロント毎に順次に行い、かつ各ウェーブ・フ
ロント内のセルについて並列に拡散処理を行い、ウェー
ブ・フロントが空になるか、終点に到達するまで各処理
を繰り返す拡散処理部と、該拡散処理部での１ピン・ペ
ア処理終了後、マツプに付与されたラベルを参照して経
路を定めるバック・トレース処理部と、 該バック・トレース処理部でのバック・トレース処理終
了後、次のピン・ペア処理に備えてマツプ情報の一部で
ある既配線やラベルを初期状態に戻すクリア処理部と、 全体の制御を行うプロセッサと、 前記イメージ・メモリ、前記ピン・ペア・アドレス処理
部、前記拡散処理部、前記バック・トレース処理部、前
記クリア処理部および前記プロセッサの間のデータ転送
を制御するインタフェース回路と を備えることを特徴とする。

（作用） 本発明の方式では、多数のウェーブ・フロントを予め準
備し、例えば、１６個用意した場合、それらを８個ずつ
２つのグループに分け、交互に入れ換えながら使用する
ことにより処理を進める。

今回処理すべき８個のウェーブ・フロントの処理は、並
列には実行せず、１つずつ順に処理する。

１個のウェーブ・フロント内の複数のセルの処理は、並
列に実行される。

拡散できたセルのアドレスは、次回に処理する８個のウ
ェーブ・フロントに登録されるが、ある１つのウェーブ
・フロントから複数のセルを取り出し、同時に拡散した
ときに、拡散した先のセルが衝突しないように、近傍の
セルは異なるウェーブ・フロントに入れられる。

（実施例） 以下に、本発明の実施例について図面を参照しながら説
明する。

第３図は本発明の配線経路探索方式の原理を示す説明図
である。第３図において１０はメモリ上にあるマツプで
あり、矩形で示されるセル１１゜１２．１３．１４，１
５．１６はイメージ・メモリ上にあるマツプ１０のセル
に対応する。

いま、ウェーブ・フロントにはセル１１のアドレスがセ
ットされているとし、このセル１１から拡散する場合に
ついて述べる。

まず、セル１１を中心に隣接する４つのセルのアドレス
を発生し、拡散処理を行う０次にセル１２〜１５の処理
を行う場合、例えば、セル１２、セル１４は共にセル１
６へ拡散するから、セル１２とセル１４とからの拡散処
理を同時に実行することはできない。

そこで、複数のウェーブ・フロントは第４図に示すよう
に、２つのグループに分けられる０本実施例では、例え
ば１６個のウェーブ、フロントをＡ、Ｂの２つのグルー
プに分け、グループＡのウェーブ・フロントを拡散処理
して得られたセル・アドレスを、グループＢのウェーブ
・フロントに格納する。また、グループＢのウェーブ・
フロントを拡散処理して得られたセル・アドレスは、グ
ループＡのウェーブ・フロントに格納される。

１つのグループには、８個のウェーブ・フロントがある
が、次回に拡散処理を行うセルは、同時に拡散処理をし
ても衝突の起らない物同志に分類され、各ウェーブ・フ
ロントに格納される。

この分類の仕方を第５図に示す。第５図の５０〜５７の
８つの図の中にある１６進数で書かれたセルが、各ウェ
ーブ・フロント５０〜５７に格納されるセルである０図
におけるマツプの横方向をＸ方向、縦方向をＸ方向とし
、図中の１６進数の上位の数がＸ座標を、下位の数がＸ
座標を示すとするやマツプの左上のセルを００とする。

このとき、アドレスＸＹを持つセルは、例えば、次のよ
うに計算することによって、８個のウェーブ・フｒｒン
トに分配することができる。

（Ｘ十Ｙ）を４で割ったときの余りをＡ、Ｘを２で割っ
たときの余りをＢとすると、Ａは０〜４、Ｂは０または
１となる。これらの組合せによってセルを８通りに分類
することができる。このように分類することにより、マ
ツダ上の全てのセルを、８個のウェーブ・フロントの内
の１つに割り当てることができ、また、１つのウェーブ
・フロント内の全てのセルが、図中の矢印で示したよう
に、同時に４近傍に拡散処理を行っても、衝突は起こら
ないことが分かる。

従って、８個のウェーブ・フロントを順に処理すること
により、各ウェーブ・フロント内の全てのセルを同時に
拡散処理することができる。

第１図は本発明の配線経路探索装置の一実施例を示すブ
ロック図である。

配線経路探索装置は、第１図に示すように、イメージ・
メモリ６１と、インタフェース凹銘６２と、マイクロプ
ロセッサ６３と、データフロー・パイプライン・プロセ
ッサ（以下、「プロセッサ」と称す、）６４〜６７から
成る。

イメージ・メモリ６１は、配線の始点、終点を示すピン
・ペア情報と、とア、配線禁止、配線経路、始点からの
経路を表すラベルを示す情報等のマツプ情報と、ウェー
ブ・フロント・アドレス情報とを記憶し、保持するメモ
リである。

各プロセッサ６４〜６７はピン・ペア・アドレス処理部
、拡散処理部、バック・トレース処理部、及びクリア処
理部を構成する。

ピン・ペア・アドレス処理部は、配線の始点、終点の情
報からイメージ・メモリ６１のマツプの実アドレスを生
成する。

拡散処理部は、ピン・ペア・アドレス処理部またはウェ
ーブ・フロントから与えられるマツプの実アドレスに基
づき、東西南北４近傍のウェーブ・フロント・アドレス
を生成し、イメージ・メモリ６Ｉのマ・ｙグ情報を参照
、更新すると共に、拡散が成功したセルのアドレスを、
複数のウェーブ・フロントに分類し、書き込む処理を行
う、前記処理は、ウェーブ・フロントが空になるか、配
線の終点に到達するまで繰り返し行われる。

バック・トレース処理部は、拡散処理部での１ピン・ペ
ア処理終了後、マツプに付与されたラベルを参照して経
路を定める。クリア処理部は、バック・トレース処理終
了後、次のピン・ペア処理に備えてマツプ情報の一部で
あるラベル等を初期状態に戻す。

マイクロプロセッサ６３は、全体の制御を行う。

インタフェース回路６２は、イメージ・メモリ６１、各
処理部、マイクロプロセッサ６３等の間のデータ転送を
制御する。

Ｊ述の各プロセッサ６４〜６７は、例えば日本電気株式
会社（ＮＥＣ）の製造に係るイメージ処理プロセッサμ
ＰＤ７２８１からなる。各プロセッサ６４〜６７はリン
グ上のパイプライン・バスによって縦続に接続されてい
る。

各プロセッサ間のデータの授受は非同期ハンドシェーク
信号によって行われる。受は渡されるデータは、データ
の行き先プロセッサ番号を示すフィールド、機能識別フ
ィールド、制御フィールド、データ値フィールドから構
成される。各プロセッサには各々自分固有のプロセッサ
番号が予め設定されている。各プロセッサはそのプロセ
ッサ番号と入力データの持つ行き先プロセッサ番号とが
一致した場合に入力データをプロセッサ内部に取り込み
、機能識別フィールドに応じた処理を施し、新しく行き
先プロセッサ番号を付は変えて外部へ送り出す。プロセ
ッサ内部は、パイプライン構成を取っており、複数のデ
ータを並列に処理することができる。該プロセッサの詳
細は、特開昭５８７０３６０号公報に記載されている。

インタフェース回路６２はプロセッサ６７からの入力デ
ータの内行き先のプロセッサ番号を参照し、データの行
き先をメモリ６１、プロセッサ６４〜６７、マイクロプ
ロセッサ６３へ振り分けるスイッチとして機能する。イ
ンタフェース回路６２からメモリ６１へは、データ識別
番号、メモリ・アドレス値、データ値、制御信号か出力
され、逆にメモリ６１からインタフェース回路６２へは
読みだしデータ、制御信号が返される。マイクロプロセ
ッサ６３はプロセッサ６４〜６７、メモリ６１、インタ
フェース回路６２の初期設定、実行制御を行う、マイク
ロプロセッサ６３としては市販の汎用プロセッサが用い
られる。

第１図の構成においてマイクロプロセッサ６３から初期
設定を行った後、プロセッサ６４〜６７に起動をかける
と処理が開始され、メモリ６１の内容が更新される。処
理が終了すると、終了道知がプロセッサ６４〜６７から
マイクロプロセッサ６３に発行される。

次に、第２図のフローチャートをも用いて動作を説明す
る。

既述したごとく、イメージ・メモリ６１には、マツプ情
報、ピン・ペア情報、ウェーブ・フロント情報、拡散の
速度を変化させるパラメータ情報等が格納されている。

プロセッサ６４は、ピン・ペアのアドレス計算を行い、
イメージ・メモリ６１のマツプ上に始点及び終点のマー
クをつける（第２図のステップ１０１）。

始点のアドレスは拡散処理を行うプロセッサ６５に受は
渡され、プロセッサ６５はその始点のアドレス、もしく
は拡散処理中にはウェーブ・フロントから得られるセル
、アドレスをもとに、東西南北に対応する４隣接のマツ
プ・アドレスを求め、配線可能であるかどうかのチエツ
クを行い、可能であればマツプ上に経路情報とラベルと
を書き込み、そのアドレス値に基づき複数のウェーブ・
フロントの内の１つを選択し書き込む。このとき、複数
のセルの処理は、プロセッサ６５内部のパイプラインで
並列に行われる０以上の処理は、ウェーブ・フロントが
空になるか、終点に到達するまで、繰り返し行われる（
第２図のステップ１０２）。

１ピン・ペアの処理が終了すると、バック・トレース処
理を行うプロセッサ６６は起動される。

プロセッサ６６は、マツプ上のラベルを終点から順に拡
散の進んだ方向と逆向きにたどり、終点から始点までの
経路を決定する（第２図のステップ１０３）。

プロセッサ６７は、プロセッサ６６での処理が終了する
と、マツプ上の経路情報やラベル等を消去しく第２図の
ステップ１０４）、次のピン・ペアの処理の準備をする
。

以上の処理は全てのピン・ペアについて繰り返される（
第２図のステップ１０５）。

以上により、配線設計において、拡散処理を並列に行う
ことができ、高速性に優れる。

（発明の効果） 以上に説明したように、本発明の配線経路探索方式およ
び装置によれば、従来の迷路法の拡散処理を並列に行う
ことができる。

【図面の簡単な説明】

第１図は本発明の配線経路探索装置の一実施例を示すブ
ロック図、第２図は第１図の配線経路探索装置の処理の
手順を示すフローチャート、第３図は本発明の配線経路
探索方式の原理を説明するための図、第４図は本発明に
用いるウェーブ・フロントの一例を示す図、第５図は本
発明に用いるセル・アドレスに分類方法の一例を示す図
、第６図はイメージ・メモリに格納されているマ・ｙ　
７’　４ｊｆ報のフォーマットを示す図、第７図（ａ）
、（ｂ）はウェーブ・フロントから４方向への拡散を説
明するための図である。 １１．１２．１３，１４．１５　１６・・・セル、６１
・・・イメージ・メモリ、６２・・・インタフェース回
路、６３・・・マイクロプロセッサ、６４，６５゜６６
．６７・・・データフロー・パイプライン・プロセッサ
。

Claims (2)

【特許請求の範囲】
1. （１）配線の間隔を単位とする格子状に分割された配線
   領域を示すマップ上で、波状に配線経路を探索すること
   によって回路配線経路を求める配線経路探索方式におい
   て、 配線の始点、終点を示すピン・ペア情報、マップ情報、
   及びウェーブ・フロント・アドレスを記憶し、保持する
   手段と、 配線の始点、終点の情報からマップの実アドレスを生成
   する手段と、 マップの実アドレスに基づき、４方位の各方向近傍のセ
   ル・アドレスを生成し、マップ情報の参照、更新等の拡
   散処理を行う手段と、 拡散に成功したセルのアドレスを、次の拡散処理が並列
   に実行できるもの毎に分類しながら、複数のウェーブ・
   フロントに書き込む手段と、複数のウェーブ・フロント
   を、１つずつ順に処理する手段と、 １つのウェーブ・フロント内の各セルについて並列に拡
   散処理を行う手段と を備えることを特徴とする配線経路探索方式。
2. （２）すくなくとも、配線の始点、終点を示すピン・ペ
   ア情報、マップ情報、ウェーブ・フロント・アドレスを
   記憶し、保持するイメージ・メモリと、 配線の始点、終点の情報から該イメージ・メモリのマッ
   プの実アドレスを生成するピン・ペア・アドレス処理部
   と、 該ピン・ペア・アドレス処理部、またはウェーブ・フロ
   ントから得られるマップの実アドレスに基づき、４方位
   の各近傍のセル・アドレスを生成し、イメージ・メモリ
   のマップ情報を参照し、波が拡散可能なセルについてマ
   ップ情報を更新する拡散処理と共に、該セルのアドレス
   を次回の拡散時に同時に処理できるもの毎に分類しなが
   ら複数のウェーブ・フロントに書き込む分類処理を各ウ
   ェーブ・フロント毎に順次に行い、かつ各ウェーブ・フ
   ロント内のセルについて並列に拡散処理を行い、ウェー
   ブ・フロントが空になるか、終点に到達するまで各処理
   を繰り返す拡散処理部と、該拡散処理部での１ピン・ペ
   ア処理終了後、マップに付与されたラベルを参照して経
   路を定めるバック・トレース処理部と、 該バック・トレース処理部でのバック・トレース処理終
   了後、次のピン・ペア処理に備えてマップ情報の一部で
   ある既配線やラベルを初期状態に戻すクリア処理部と、 全体の制御を行うプロセッサと、 前記イメージ・メモリ、前記ピン・ペア・アドレス処理
   部、前記拡散処理部、前記バック・トレース処理部、前
   記クリア処理部、および前記プロセッサの間のデータ転
   送を制御するインタフェース回路と を備えることを特徴とする配線経路探索装置。