JPS6140674A - 経路探索処理システム - Google Patents
経路探索処理システムInfo
- Publication number
- JPS6140674A JPS6140674A JP16307384A JP16307384A JPS6140674A JP S6140674 A JPS6140674 A JP S6140674A JP 16307384 A JP16307384 A JP 16307384A JP 16307384 A JP16307384 A JP 16307384A JP S6140674 A JPS6140674 A JP S6140674A
- Authority
- JP
- Japan
- Prior art keywords
- route
- retrieval
- search
- grid
- point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000013500 data storage Methods 0.000 claims description 15
- 230000002093 peripheral effect Effects 0.000 abstract description 2
- 238000003491 array Methods 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 9
- 101150064138 MAP1 gene Proteins 0.000 description 3
- 230000000694 effects Effects 0.000 description 2
- 238000000034 method Methods 0.000 description 2
- 238000004904 shortening Methods 0.000 description 1
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（技術分野）
本発明はプリント板、ＬＳＩ等における配線設計を行う
経路探索処理システムに関する。・（従来技術） 配線経路の従来の探索は、大容量のメモリを有する汎用
コンピュータで、経路探索用プログラムを動作させるこ
とにより実現されている。
経路探索処理システムに関する。・（従来技術） 配線経路の従来の探索は、大容量のメモリを有する汎用
コンピュータで、経路探索用プログラムを動作させるこ
とにより実現されている。
汎用コンピュータは１つの経路探索において逐次的に順
次４方向に経路の有無を調べるので多量のコンピュータ
時間を要し、比較的に高速なラインサーチ法を利用して
も順次ＸおよびＹ方向へ交互に多数のラインを発生させ
るためかなシのコンピュータ時間を要するという欠点が
ある。
次４方向に経路の有無を調べるので多量のコンピュータ
時間を要し、比較的に高速なラインサーチ法を利用して
も順次ＸおよびＹ方向へ交互に多数のラインを発生させ
るためかなシのコンピュータ時間を要するという欠点が
ある。
（発明の目的）
本発明の目的は、Ｘ方向およびＹ方向の１次元アレー状
の格子からの経路探索を同時並列に行えるようにして経
路探索処理時間を格段に短縮できる経路探索処理システ
ムを提供することにある。
の格子からの経路探索を同時並列に行えるようにして経
路探索処理時間を格段に短縮できる経路探索処理システ
ムを提供することにある。
（発明の構成）
本発明の装置は、Ｘ、Ｙ直交方向に格子が設けられた配
線基板における接続すべき格子点の対からなる区間デー
タを記憶する区間データ記憶部と、前記配線基板全体の
格子の探索使用情報を記憶する格子マツプ記憶部と、前
記Ｙ方向に１次元アレー状に並んだ各格子のそれぞれに
設けられ前記区間データまたは中間経路データに基づき
前記Ｘ方方向に経路を探索するＸ方向経路探索プロセッ
サーと、前記Ｘ方向に１次元アレー状に並んだ各格子の
それぞれに設けられ前記区間データまたは中間経路デー
タに基づき前記Ｙ方向に経路を探索するＹ方向経路探索
プロセッサーと、前記各プロセッサーの経路探索の実行
を少なくとも同時並列に制御する経路探索制御部と、Ｘ
方向およびＹ方向に探索された途中の中間経路データを
記憶する中間経路データ記憶部と、前記Ｘ方向経路探索
プロセッサと前記Ｙ方向経路探索プロセッサーとの両方
により探索された格子から探索された経路を逆トレース
して経路データを決定する経路トレース部と、前記決定
された経路データを記憶する経路データ記憶部と、前記
経路データ記憶部および前記格子マツプ記憶部に経路デ
ータを出力する経路データ出力部とを含んて゛磯戚プれ
る；４一番緋格某素第刈ミとｔテツセ （実施例） 次に本発明について図面を参照して詳細に説明する。
線基板における接続すべき格子点の対からなる区間デー
タを記憶する区間データ記憶部と、前記配線基板全体の
格子の探索使用情報を記憶する格子マツプ記憶部と、前
記Ｙ方向に１次元アレー状に並んだ各格子のそれぞれに
設けられ前記区間データまたは中間経路データに基づき
前記Ｘ方方向に経路を探索するＸ方向経路探索プロセッ
サーと、前記Ｘ方向に１次元アレー状に並んだ各格子の
それぞれに設けられ前記区間データまたは中間経路デー
タに基づき前記Ｙ方向に経路を探索するＹ方向経路探索
プロセッサーと、前記各プロセッサーの経路探索の実行
を少なくとも同時並列に制御する経路探索制御部と、Ｘ
方向およびＹ方向に探索された途中の中間経路データを
記憶する中間経路データ記憶部と、前記Ｘ方向経路探索
プロセッサと前記Ｙ方向経路探索プロセッサーとの両方
により探索された格子から探索された経路を逆トレース
して経路データを決定する経路トレース部と、前記決定
された経路データを記憶する経路データ記憶部と、前記
経路データ記憶部および前記格子マツプ記憶部に経路デ
ータを出力する経路データ出力部とを含んて゛磯戚プれ
る；４一番緋格某素第刈ミとｔテツセ （実施例） 次に本発明について図面を参照して詳細に説明する。
第１図は配線格子を説明するための格子マツプ図である
。格子は１例として１０行８列のものを示しである。以
下性をＹ方向、列をＸ方向とと夛図の左下を原点とする
。各格子を示すのに座標を用い左下の格子を（１，１）
とする。第１図の格子マツプ１上には、配線区間の始点
２ （２，７）を含むＸ方向ライン４、終点３（８，２
）を含むＹ方向ライン５、配線の禁止領域６が存在す不
。Ｘ方向ライン４は１次元アレー状に並んだ格子点（１
，７）、（２，７）〜（１０，７）からなり、Ｙ方向ラ
イン５は１次元アレー状の格子点（９，：ｔ）、（ｇ、
２）〜（官。
。格子は１例として１０行８列のものを示しである。以
下性をＹ方向、列をＸ方向とと夛図の左下を原点とする
。各格子を示すのに座標を用い左下の格子を（１，１）
とする。第１図の格子マツプ１上には、配線区間の始点
２ （２，７）を含むＸ方向ライン４、終点３（８，２
）を含むＹ方向ライン５、配線の禁止領域６が存在す不
。Ｘ方向ライン４は１次元アレー状に並んだ格子点（１
，７）、（２，７）〜（１０，７）からなり、Ｙ方向ラ
イン５は１次元アレー状の格子点（９，：ｔ）、（ｇ、
２）〜（官。
４）からなる。
第２図は本発明の基本的な動作を説明する図である。Ｘ
方向ライン４上の１次元アレー状の格子点（１，７）、
（２，７）〜（１０，７）にＹ方向経路探索プロセッサ
ー８−１．８−２〜８−１０を割当て、同様にＹ方向ラ
イン５上の１次元アレー状の格子点（宮、１）、（宮、
２）〜（宮、４）にＸ方向経路探索プロセッサー７−１
．７−２〜７−４を割当てる。 ゛プロセッサー８−
１．８−２〜８−１０は同時並列に〜−５− Ｙ方向の経路を探索しその結果は見つかったＹ方向の経
路９で表現され、格子マツプ１に保存される。同様にプ
ロセッサー７−１．７−２〜７−４は同時並列にＸ方向
の経路を探索し、その結果はＸ方向の経路１０で表現さ
れ格子マツプ１に保存される。
方向ライン４上の１次元アレー状の格子点（１，７）、
（２，７）〜（１０，７）にＹ方向経路探索プロセッサ
ー８−１．８−２〜８−１０を割当て、同様にＹ方向ラ
イン５上の１次元アレー状の格子点（宮、１）、（宮、
２）〜（宮、４）にＸ方向経路探索プロセッサー７−１
．７−２〜７−４を割当てる。 ゛プロセッサー８−
１．８−２〜８−１０は同時並列に〜−５− Ｙ方向の経路を探索しその結果は見つかったＹ方向の経
路９で表現され、格子マツプ１に保存される。同様にプ
ロセッサー７−１．７−２〜７−４は同時並列にＸ方向
の経路を探索し、その結果はＸ方向の経路１０で表現さ
れ格子マツプ１に保存される。
この時、プロセッサー８−１．８−２〜８−１０とプロ
セッサー７−１．７−２〜７−４は同時並列に動作し、
経路を探索する。
セッサー７−１．７−２〜７−４は同時並列に動作し、
経路を探索する。
Ｙ方向の経路とＸ方向の経路とが同じ格子点１１（６１
４）に到達した時点で、経路探索が終了する。
４）に到達した時点で、経路探索が終了する。
経路の探索は最初の段階として始点２を含むライン４と
、終点３を含むライン５に対しプロセッサーを割当てる
が、経路がさらに複雑になる場合は、始点側から探索さ
れた途中段階でのラインおよび終点側から探索された途
中段階でのラインを保存して多段階に経路探索を行う。
、終点３を含むライン５に対しプロセッサーを割当てる
が、経路がさらに複雑になる場合は、始点側から探索さ
れた途中段階でのラインおよび終点側から探索された途
中段階でのラインを保存して多段階に経路探索を行う。
第３図において、゛前記の多段階の探索の動作を説明す
る。゛始点２を含む２イン４から探索されたＹ方向ライ
ン１２、および終点３を含むライン５から探索されたＸ
方向ライン１３を保存し次の段６一 階でライン１２．１３にそれぞれＸ方向、Ｙ方向探索の
プロセッサーを割当てることによ多経路探索を行いＸ方
向の経路とＹ方向の経路とが同じ格子点１４（６，５）
に到達する迄続けられる。このように途中段階でのライ
ンを保存し、次の段階でこのラインにプロセッサーを割
当て経路を探索するといった一連の動作を順次繰返すこ
とによって多段階に経路探索を行うことができる。
る。゛始点２を含む２イン４から探索されたＹ方向ライ
ン１２、および終点３を含むライン５から探索されたＸ
方向ライン１３を保存し次の段６一 階でライン１２．１３にそれぞれＸ方向、Ｙ方向探索の
プロセッサーを割当てることによ多経路探索を行いＸ方
向の経路とＹ方向の経路とが同じ格子点１４（６，５）
に到達する迄続けられる。このように途中段階でのライ
ンを保存し、次の段階でこのラインにプロセッサーを割
当て経路を探索するといった一連の動作を順次繰返すこ
とによって多段階に経路探索を行うことができる。
第４図は本発明の一実施例を示すブロック図である。
第４図の経路探索処理システムは、接続すべき区間の始
めおよび終シの格子点データ（座標データ）を記憶する
区間データ記憶部１５と、本実施例の各部を制御する経
路探索制御部１６と、配線基板の配線格子に対応して各
配線格子の探索使用情報を記憶する格子マツプ記憶部２
１と、格子マツプ記憶部２１の各列（Ｘ方向）にそれぞ
れ設けられＸ方向の経路を探索するＸ方向経路探索プロ
セッサー７−１〜７−８ からなるＸ方向経路探索処理
部１７と、格子マツプ記憶部２１の各行（Ｙ方向）Ｋそ
れぞれ設けられＹ方向の経路を探索するＹ方向経路探索
プロセッサ８−１〜８−１０からなるＹ方向経路探索処
理部１９と、格子マツプ記憶部２１とＸ方向経路探索処
理部１７とのデータの入出力を制御するＸ方向格子マツ
プ入出力制御部１Ｂと、格子マツプ記憶部２１とＹ方向
経路探索処理部１９とのデータの入出力を制御するＹ方
向格子マツプ入出力制御部２０と、探索されて未だ始点
と終点とを結んでいない中間の経路を記憶する中間経路
記憶部２２と、始点と終点とを接続した経路を発見した
ときにその経路を始点および終点−向って逆にたどって
いく制御をする経路トレース部２３と、経路トレース部
２３によりたどられた各格子点の座標データを出力する
経路データ出力部２４と、経路データ出力部２４からの
経路データを格納する経路データ記憶部２５とから構成
される。
めおよび終シの格子点データ（座標データ）を記憶する
区間データ記憶部１５と、本実施例の各部を制御する経
路探索制御部１６と、配線基板の配線格子に対応して各
配線格子の探索使用情報を記憶する格子マツプ記憶部２
１と、格子マツプ記憶部２１の各列（Ｘ方向）にそれぞ
れ設けられＸ方向の経路を探索するＸ方向経路探索プロ
セッサー７−１〜７−８ からなるＸ方向経路探索処理
部１７と、格子マツプ記憶部２１の各行（Ｙ方向）Ｋそ
れぞれ設けられＹ方向の経路を探索するＹ方向経路探索
プロセッサ８−１〜８−１０からなるＹ方向経路探索処
理部１９と、格子マツプ記憶部２１とＸ方向経路探索処
理部１７とのデータの入出力を制御するＸ方向格子マツ
プ入出力制御部１Ｂと、格子マツプ記憶部２１とＹ方向
経路探索処理部１９とのデータの入出力を制御するＹ方
向格子マツプ入出力制御部２０と、探索されて未だ始点
と終点とを結んでいない中間の経路を記憶する中間経路
記憶部２２と、始点と終点とを接続した経路を発見した
ときにその経路を始点および終点−向って逆にたどって
いく制御をする経路トレース部２３と、経路トレース部
２３によりたどられた各格子点の座標データを出力する
経路データ出力部２４と、経路データ出力部２４からの
経路データを格納する経路データ記憶部２５とから構成
される。
格子マツプ記憶部２１の記憶する探索使用情報としては
、対応する格子点が既に配線経路として使用されたか否
かを示す使用情報（例えば１ビツト）と、探索された方
向を示す（当該格子点の上にある格子点、下にある格子
点、右にある格子点、左にある格子点のいづれから探索
されたかを示す）探索方向情報（例えば２ビツト）と、
探索の原点となった格子点が始点であったのか終点であ
ったのか当該格子点が始点または終点なのかまたは朱だ
探索されていないかを示す格子点属性情報と。
、対応する格子点が既に配線経路として使用されたか否
かを示す使用情報（例えば１ビツト）と、探索された方
向を示す（当該格子点の上にある格子点、下にある格子
点、右にある格子点、左にある格子点のいづれから探索
されたかを示す）探索方向情報（例えば２ビツト）と、
探索の原点となった格子点が始点であったのか終点であ
ったのか当該格子点が始点または終点なのかまたは朱だ
探索されていないかを示す格子点属性情報と。
を含む。
各経路探索プロセッサの経路探索動作としては、先づプ
ロセッサに探索の始点となる格子点データが与えられ（
終点から探索を出発させるときには終点が与えられる）
、この格子点を始点として規定されている方向（Ｘ方向
経路探索プロセッサについていえばＸ方向）に順次探索
を開始する。以下Ｘ方向経路探索プロセッサについて説
明する。
ロセッサに探索の始点となる格子点データが与えられ（
終点から探索を出発させるときには終点が与えられる）
、この格子点を始点として規定されている方向（Ｘ方向
経路探索プロセッサについていえばＸ方向）に順次探索
を開始する。以下Ｘ方向経路探索プロセッサについて説
明する。
すなわちＸ方向経路探索プロセッサはＸ方向について始
点となる格子点に隣接する格子点の探索使用情報を格子
マツプ記憶部２１からＸ方向格子マツプ入出力制御部１
８を介して読みとり、先ず使用情報をチェックし前記隣
接する格子点が使用済みであればその方向の探索を終了
し新たに始点から−Ｘ方向への探索を開始する。使用情
報が未使用を示すときには格子点属性情報をチェックし
該情報が未探索を示す以外はその方向の探索を終了する
。未探索の場合には格子点属性情報を探索の原点が始点
（終点から探索されたときには終点）であることを示す
ようにかつ探索方向情報を左から探索された（第１〜３
図では→で示しである）ことを示すようにＸ方向格子マ
ツプ入出力制御部 、１８を介して格子マツ
プ記憶部２１の尚該格子点位置に書き込む。次いで更に
Ｘ方向において隣接する格子点へと探索を続行する。勿
論格子点が配線基板の周辺位置に到達したときはそれよ
シ後のその方向の探索は終了する。Ｘ方向の探索を終了
したならば−Ｘ方向の探索を開始させることは前述の通
シである。
点となる格子点に隣接する格子点の探索使用情報を格子
マツプ記憶部２１からＸ方向格子マツプ入出力制御部１
８を介して読みとり、先ず使用情報をチェックし前記隣
接する格子点が使用済みであればその方向の探索を終了
し新たに始点から−Ｘ方向への探索を開始する。使用情
報が未使用を示すときには格子点属性情報をチェックし
該情報が未探索を示す以外はその方向の探索を終了する
。未探索の場合には格子点属性情報を探索の原点が始点
（終点から探索されたときには終点）であることを示す
ようにかつ探索方向情報を左から探索された（第１〜３
図では→で示しである）ことを示すようにＸ方向格子マ
ツプ入出力制御部 、１８を介して格子マツ
プ記憶部２１の尚該格子点位置に書き込む。次いで更に
Ｘ方向において隣接する格子点へと探索を続行する。勿
論格子点が配線基板の周辺位置に到達したときはそれよ
シ後のその方向の探索は終了する。Ｘ方向の探索を終了
したならば−Ｘ方向の探索を開始させることは前述の通
シである。
本実施例の動作について説明する。
経路探索制御部１６は、区間データ記憶部１５よシ１区
間データを入力し、第１図の始点２（２，７）を含むＸ
方向ラインの探索をＸ方向経路探索処理部１７に指示し
、同様に終点３（８，２）を含むＹ方向ラインの探索を
Ｙ方向経路探索処理部１９に指示することによってＸ方
向ライン４、Ｙ方向ライン５をまず求める。これはＸ方
向経路探索プロセッサ７−７が始点（２，７）から、Ｙ
方向経路探索プロセッサ８−３が終点（８，２）から探
索して求められる。結果゛は中間経路記憶部２２に記憶
される。
間データを入力し、第１図の始点２（２，７）を含むＸ
方向ラインの探索をＸ方向経路探索処理部１７に指示し
、同様に終点３（８，２）を含むＹ方向ラインの探索を
Ｙ方向経路探索処理部１９に指示することによってＸ方
向ライン４、Ｙ方向ライン５をまず求める。これはＸ方
向経路探索プロセッサ７−７が始点（２，７）から、Ｙ
方向経路探索プロセッサ８−３が終点（８，２）から探
索して求められる。結果゛は中間経路記憶部２２に記憶
される。
次に線路探索制御部１６は中間経路記憶部２２に格納さ
れている前記の探索結果にもとずきＸ方向ライン４．Ｙ
方向ライン５から探索を開始することをそれぞれＹ方向
経路探索処理部１９．Ｘ方向経路探索処理部１７に指示
する。プロセッサー８−１〜８−１０はライン４に含ま
れる１次元アレー状の格子点（１，７）、（２，７）〜
（１０，７）を始点とし、プロセッサー７−１．７−２
〜７−４はライン５の格子点（８，１）、（８，２）〜
（８，４） を終点として探索を始める。
れている前記の探索結果にもとずきＸ方向ライン４．Ｙ
方向ライン５から探索を開始することをそれぞれＹ方向
経路探索処理部１９．Ｘ方向経路探索処理部１７に指示
する。プロセッサー８−１〜８−１０はライン４に含ま
れる１次元アレー状の格子点（１，７）、（２，７）〜
（１０，７）を始点とし、プロセッサー７−１．７−２
〜７−４はライン５の格子点（８，１）、（８，２）〜
（８，４） を終点として探索を始める。
プロセッサー８−１．８−２〜８−１０はＹ方向格子マ
ツプ入出力制御部２０を介して格子マツプ記憶部２１か
ら格子の探索使用情報を入力し経路を探索する。同様に
プロセッサー７−１．７−２〜７−４はＸ方向格子マツ
プ入出力制御部１８を介して格子マツプ記憶部２１から
格子の探索使用情報を入力し経路を探索する。このとき
プロセッサー７−１゜７−２〜７−４および８−１．８
−２〜８−１０は全て同時並列に動作する。
ツプ入出力制御部２０を介して格子マツプ記憶部２１か
ら格子の探索使用情報を入力し経路を探索する。同様に
プロセッサー７−１．７−２〜７−４はＸ方向格子マツ
プ入出力制御部１８を介して格子マツプ記憶部２１から
格子の探索使用情報を入力し経路を探索する。このとき
プロセッサー７−１゜７−２〜７−４および８−１．８
−２〜８−１０は全て同時並列に動作する。
見つかった経路の方向を探索方向情報として格子マツプ
記憶部２１の対応する格子点に格納する。
記憶部２１の対応する格子点に格納する。
Ｘ方向およびＹ方向の探索が同じ格子点１１（６，４）
に到達する迄経路探索が続けられる。同じ格子点に到達
したことは格子点属性情報のチェックでわかる。１段階
の探索で同じ格子点に到達しガい場合は、途中段階のラ
インを再度中間経路記憶部２２に格納することによって
前述した通シの多段階の処理によって経路探索が行なわ
れる。
に到達する迄経路探索が続けられる。同じ格子点に到達
したことは格子点属性情報のチェックでわかる。１段階
の探索で同じ格子点に到達しガい場合は、途中段階のラ
インを再度中間経路記憶部２２に格納することによって
前述した通シの多段階の処理によって経路探索が行なわ
れる。
同じ格子点１１に経路が到達した時点で線路探索制御部
１６は線路トレース部２３にバックトレースを指示する
。経路トレース部２３は格子マツプ記憶部２１に格納さ
れている格子点の座標と探索方向情報とに基づいて始点
２から終点３までバックトレースし最終的な１本の経路
を決定し経路データ出力部２４に経路データを出力する
。経路データ出力部２４は決定された経路データを経路
データ記憶部２５に格納すると同時に格子マツプ記憶部
２１へ該経路の格子に対し使用済状態をセットし、今回
の律索中に付けられた探索方向情報を消去する。
１６は線路トレース部２３にバックトレースを指示する
。経路トレース部２３は格子マツプ記憶部２１に格納さ
れている格子点の座標と探索方向情報とに基づいて始点
２から終点３までバックトレースし最終的な１本の経路
を決定し経路データ出力部２４に経路データを出力する
。経路データ出力部２４は決定された経路データを経路
データ記憶部２５に格納すると同時に格子マツプ記憶部
２１へ該経路の格子に対し使用済状態をセットし、今回
の律索中に付けられた探索方向情報を消去する。
上記の動作を全ての区間データに対し繰返し実行する。
以上のようにして本実施例では配線基板の配線経路を迅
速に確定することができる。
速に確定することができる。
なお配線層が２つ以上の多層のプリント板、ＬＳＩ等に
対しては、各配線層での探索方向が変る格子点にスルー
ホールを設けることによって容易に対応できる。
対しては、各配線層での探索方向が変る格子点にスルー
ホールを設けることによって容易に対応できる。
（発明の効果）
本発明には、Ｘ方向およびＹ方向の１次元アレー状の格
子からの経路探索を同時並列に行うことによ島経路探索
のコンピュータ時間を大幅に削減できるという効果があ
る。
子からの経路探索を同時並列に行うことによ島経路探索
のコンピュータ時間を大幅に削減できるという効果があ
る。
第１図は配線格子を説明するための格子マツプ図、第２
図は、本発明の基本動作を説明するための図、第３図は
、多段階の経路探索を説明するための図、第４図は、本
発明の一実施例を示すブロック図である。 １・・・・・・格子マツプ、２・・・・・・配線区間の
始点、３ ′・・・・・・配線区間の終点、４・・・・
・・Ｘ方向ライン、５・・・・・・Ｙ方向２４７％６・
・・・・・配線の禁止領域、７−１゜７−２〜７−８・
・・・・・Ｘ方向経路探索プロセッサー、８−１．８−
２〜８−１０・・・・・・Ｙ方向経路探索プロセッサー
、９・・・・・・Ｙ方向の経路を示す矢印、１０・・・
・・・Ｘ方向の経路を示す矢印、１１・・・・・・探索
終了の格子、１２・・・・・・Ｙ方向ライン、１３・・
・・・・Ｘ方向ライン、１４・・・・・・探索終了の格
子、１５・・・・・・区間データ記憶部、１６・・・・
・・経路探索制御部、１７・旧・・Ｘ方向経路探索処理
部、１８・・・・・・Ｘ方向格子マツプ入出力制御部、
１９・・・・・・Ｙ方向経路探索処理部、２〇・・・・
・Ｙ方向格子マツプ入出力制御部、２１・・・・・・格
子マツプ記憶部、２２・・・・・・中間経路記憶部、２
３・・・・・・経路トレース部、２４・・・・・・経路
データ出力部、２５・・・・・・経路データ記憶部。 区 。 楡
図は、本発明の基本動作を説明するための図、第３図は
、多段階の経路探索を説明するための図、第４図は、本
発明の一実施例を示すブロック図である。 １・・・・・・格子マツプ、２・・・・・・配線区間の
始点、３ ′・・・・・・配線区間の終点、４・・・・
・・Ｘ方向ライン、５・・・・・・Ｙ方向２４７％６・
・・・・・配線の禁止領域、７−１゜７−２〜７−８・
・・・・・Ｘ方向経路探索プロセッサー、８−１．８−
２〜８−１０・・・・・・Ｙ方向経路探索プロセッサー
、９・・・・・・Ｙ方向の経路を示す矢印、１０・・・
・・・Ｘ方向の経路を示す矢印、１１・・・・・・探索
終了の格子、１２・・・・・・Ｙ方向ライン、１３・・
・・・・Ｘ方向ライン、１４・・・・・・探索終了の格
子、１５・・・・・・区間データ記憶部、１６・・・・
・・経路探索制御部、１７・旧・・Ｘ方向経路探索処理
部、１８・・・・・・Ｘ方向格子マツプ入出力制御部、
１９・・・・・・Ｙ方向経路探索処理部、２〇・・・・
・Ｙ方向格子マツプ入出力制御部、２１・・・・・・格
子マツプ記憶部、２２・・・・・・中間経路記憶部、２
３・・・・・・経路トレース部、２４・・・・・・経路
データ出力部、２５・・・・・・経路データ記憶部。 区 。 楡
Claims (1)
- 【特許請求の範囲】 Ｘ、Ｙ直交方向に格子が設けられた配線基板における接
続すべき格子点の対からなる区間データを記憶する区間
データ記憶部と、 前記配線基板全体の格子の探索使用情報を記憶する格子
マップ記憶部と、 前記Ｙ方向に１次元アレー状に並んだ各格子のそれぞれ
に設けられ前記区間データまたは中間経路データに基づ
き前記Ｘ方向に経路を探索するＸ方向経路探索プロセッ
サーと、 前記Ｘ方向に１次元アレー状に並んだ各格子のそれぞれ
に設けられ前記区間データまたは中間経路データに基づ
き前記Ｙ方向に経路を探索するＹ方向経路探索プロセッ
サーと、 前記各プロセッサーの経路探索の実行を少なくとも同時
並列に制御する経路探索制御部と、Ｘ方向およびＹ方向
に探索された途中の中間経路データを記憶する中間経路
データ記憶部と、前記Ｘ方向経路探索プロセッサと前記
Ｙ方向経路探索プロセッサとの両方により探索された格
子から探索された経路を逆トレースして経路データを決
定する経路トレース部と、 前記決定された経路データを記憶する経路データ記憶部
と、 前記経路データ記憶部および前記格子マップ記憶部に経
路データを出力する経路データ出力部とを含むことを特
徴とする経路探索処理システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16307384A JPS6140674A (ja) | 1984-08-02 | 1984-08-02 | 経路探索処理システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16307384A JPS6140674A (ja) | 1984-08-02 | 1984-08-02 | 経路探索処理システム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6140674A true JPS6140674A (ja) | 1986-02-26 |
Family
ID=15766666
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16307384A Pending JPS6140674A (ja) | 1984-08-02 | 1984-08-02 | 経路探索処理システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6140674A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61218582A (ja) * | 1985-03-23 | 1986-09-29 | Kaken Pharmaceut Co Ltd | ベンゾフラン誘導体、その製法およびそれを有効成分とする降圧剤 |
-
1984
- 1984-08-02 JP JP16307384A patent/JPS6140674A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61218582A (ja) * | 1985-03-23 | 1986-09-29 | Kaken Pharmaceut Co Ltd | ベンゾフラン誘導体、その製法およびそれを有効成分とする降圧剤 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPS63225869A (ja) | 配線経路探索方式 | |
| WO2001024111A1 (en) | Automatic routing system for pc board design | |
| WO1991006061A1 (en) | Improved routing system and method for integrated circuits | |
| JPS63245940A (ja) | ブロック配置処理方式 | |
| JPS6140674A (ja) | 経路探索処理システム | |
| US5394337A (en) | Method for wire routing of a semiconductor integrated circuit and apparatus for implementing the same | |
| US5825659A (en) | Method for local rip-up and reroute of signal paths in an IC design | |
| JPS63308676A (ja) | 木構造を用いたフロアプラン処理方式 | |
| JPS59188772A (ja) | 経路探索処理方式 | |
| JPH01293472A (ja) | Ｃａｄによる回路基板の配線経路探索方法 | |
| JPS59189471A (ja) | 配線経路探索システム | |
| JPS62139342A (ja) | Ｌｓｉ設計方法 | |
| JPH02126368A (ja) | 接続経路探索方法 | |
| JP2713969B2 (ja) | 自動配線パターン設定方式 | |
| JPH0645446A (ja) | 配置配線方法 | |
| JPS62203278A (ja) | 並列式自動配線方式 | |
| JPS6172364A (ja) | 配線自動設計方式 | |
| JPS62115574A (ja) | 並列配線方式 | |
| JPS63239963A (ja) | 配線径路決定方法 | |
| JPH0645443A (ja) | 階層化配線方法 | |
| CN116127902A (zh) | 基于二分图匹配的电路示意图垂直轨道分配系统 | |
| JP2536119B2 (ja) | 配線処理方式 | |
| JPS61120279A (ja) | 半導体集積回路のレイアウト方式 | |
| JPS62212882A (ja) | 並列計算機システム | |
| JPS63225868A (ja) | グリツドレス配線経路決定方式 |