JPS648875B2 - - Google Patents
Info
- Publication number
- JPS648875B2 JPS648875B2 JP58062204A JP6220483A JPS648875B2 JP S648875 B2 JPS648875 B2 JP S648875B2 JP 58062204 A JP58062204 A JP 58062204A JP 6220483 A JP6220483 A JP 6220483A JP S648875 B2 JPS648875 B2 JP S648875B2
- Authority
- JP
- Japan
- Prior art keywords
- route
- area
- section
- wiring
- grid
- 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.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/394—Routing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
Description
【発明の詳細な説明】
発明の属する技術分野
本発明は、プリント板、LSI等の配線設計に際
し、配線経路を決定するために使用される経路探
索処理方式に関する。
し、配線経路を決定するために使用される経路探
索処理方式に関する。
従来技術
従来のこの種経路探索は、大容量のメモリを有
する汎用コンピユータ上で線路探索用プログラム
を実行させることによつて行なつている。この方
法は、一般にプリント板、LSI等の配線領域を直
交座標で格子状に分割して、接続すべき両端の格
子対（複数対ある）のそれぞれに対して順次経路
探索を行なうので多大の処理時間を要する。１つ
の格子対の経路探索においても、例えば一方の格
子から出発して隣接する４方向の格子に対して線
路の有無を調べて、順次経路を延長して行くため
多量のコンピユータ時間を要し、さらには、求め
られた複数の経路の中から最短経路を求めるため
には、いわゆる“しらみつぶし”の経路探索を行
なわなければならない。ソフトウエアの融通性を
利用して、少ない探索回数で近似的に最短経路を
求めるアルゴリズムも開発されている（C.Y.
LEE、“An Algorithm for Path Connections
and Its Applications”、IRE Trans.Volume
EC−10 September、1961参照）。しかし、複数
の格子対のすべてに対して順次経路探索を行なう
ためには、やはり相当の長時間を要する。
する汎用コンピユータ上で線路探索用プログラム
を実行させることによつて行なつている。この方
法は、一般にプリント板、LSI等の配線領域を直
交座標で格子状に分割して、接続すべき両端の格
子対（複数対ある）のそれぞれに対して順次経路
探索を行なうので多大の処理時間を要する。１つ
の格子対の経路探索においても、例えば一方の格
子から出発して隣接する４方向の格子に対して線
路の有無を調べて、順次経路を延長して行くため
多量のコンピユータ時間を要し、さらには、求め
られた複数の経路の中から最短経路を求めるため
には、いわゆる“しらみつぶし”の経路探索を行
なわなければならない。ソフトウエアの融通性を
利用して、少ない探索回数で近似的に最短経路を
求めるアルゴリズムも開発されている（C.Y.
LEE、“An Algorithm for Path Connections
and Its Applications”、IRE Trans.Volume
EC−10 September、1961参照）。しかし、複数
の格子対のすべてに対して順次経路探索を行なう
ためには、やはり相当の長時間を要する。
発明の目的
本発明の目的は、上述の従来の欠点を解決し、
基板を複数個の領域に分割して、それぞれの領域
内の配線に対して１個ずつのプロセツサを割当
て、各領域内の経路探索は同時に並行して行なう
ことにより処理時間を短縮することができる経路
探索処理方式を提供することにある。
基板を複数個の領域に分割して、それぞれの領域
内の配線に対して１個ずつのプロセツサを割当
て、各領域内の経路探索は同時に並行して行なう
ことにより処理時間を短縮することができる経路
探索処理方式を提供することにある。
発明の構成
本発明の経路探索処理方式は、プリント板、
LSI等の配線領域を直交座標で格子状に分割し、
接続すべき経路のそれぞれの両端の格子対を探索
して配線経路を求める経路探索処理方式におい
て、探索すべき配線領域を複数の領域に分割して
その分割された各領域をその領域内の接続経路を
探索するプロセツサに割当てて経路を探索し、順
次探索すべき配線領域の分割領域を拡大して経路
を探索することを特徴とする。
LSI等の配線領域を直交座標で格子状に分割し、
接続すべき経路のそれぞれの両端の格子対を探索
して配線経路を求める経路探索処理方式におい
て、探索すべき配線領域を複数の領域に分割して
その分割された各領域をその領域内の接続経路を
探索するプロセツサに割当てて経路を探索し、順
次探索すべき配線領域の分割領域を拡大して経路
を探索することを特徴とする。
本発明の経路探索処理方式に使用する処理装置
は、プリント板、LSI等の配線基板を直交座標で
格子状に分割し接続すべき経路のそれぞれの両端
の格子対を区間データとして記憶する区間データ
記憶部と、基板全体の格子の使用状態を記憶する
格子マツプ記憶部と、基板全体の格子を複数個の
領域に分割し前記区間データ記憶部の記憶する区
間データのうち経路両端の格子が上記分割した領
域のいずれか１つの領域に属する区間データに対
してそれぞれ対応する領域番号を付与し領域の分
割管理を行なう領域制御部と、前記分割されたそ
れぞれの領域に属する区間データを入力し格子対
間の接続経路を探索する複数個のプロセツサと、
前記分割された領域のそれぞれに対して上記複数
個のプロセツサを割当て前記区間データ記憶部か
ら読み出した格子データをそれぞれ対応する前記
プロセツサへ入力させ各プロセツサの実行を制御
する配線制御部と、前記複数のプロセツサがそれ
ぞれ探索した経路情報を記憶する経路データ記憶
部とを備えたことを特徴とする。
は、プリント板、LSI等の配線基板を直交座標で
格子状に分割し接続すべき経路のそれぞれの両端
の格子対を区間データとして記憶する区間データ
記憶部と、基板全体の格子の使用状態を記憶する
格子マツプ記憶部と、基板全体の格子を複数個の
領域に分割し前記区間データ記憶部の記憶する区
間データのうち経路両端の格子が上記分割した領
域のいずれか１つの領域に属する区間データに対
してそれぞれ対応する領域番号を付与し領域の分
割管理を行なう領域制御部と、前記分割されたそ
れぞれの領域に属する区間データを入力し格子対
間の接続経路を探索する複数個のプロセツサと、
前記分割された領域のそれぞれに対して上記複数
個のプロセツサを割当て前記区間データ記憶部か
ら読み出した格子データをそれぞれ対応する前記
プロセツサへ入力させ各プロセツサの実行を制御
する配線制御部と、前記複数のプロセツサがそれ
ぞれ探索した経路情報を記憶する経路データ記憶
部とを備えたことを特徴とする。
発明の実施例
次に、本発明について、図面を参照して詳細に
説明する。
説明する。
第１図は、本発明の一実施例を示すブロツク図
である。すなわち、プリント基板、LSI等の配線
領域を直交座標によつて格子状に分割し、接続す
べき経路の両端の格子対（一般に複数対ある）を
区間データとして記憶する区間データ記憶部１
と、配線領域上の各格子の使用状態を記憶するた
めの格子マツプ記憶部２と、配線領域の格子マツ
プを複数個の領域に分割してそれぞれの分割領域
内に両端の格子を有する区間データに対して対応
する領域の番号を付与して領域の分割管理を行な
う領域制御部３と、該領域制御部３により分割さ
れた複数の領域にそれぞれ複数のプロセツサ６ａ
〜６ｉを１個ずつ割当て前記区間データ記憶部か
ら読み出した両端部が同一の分割領域内にある区
間データを対応するプロセツサへ供給し各プロセ
ツサの動作を制御する配線制御部５と、与えられ
た区間データの両端格子間の経路を探索する複数
のプロセツサ６ａ〜６ｉを含む配線処理部７と、
配線処理部７の各プロセツサの探索した経路デー
タにより前記格子マツプ記憶部２の内容を更新し
かつ前記区間データ記憶部１に配線ずみまたは未
了を通知する経路データ出力部８と、経路データ
出力部８の出力データにより経路データを記憶す
る経路データ記憶部４とから構成されている。
である。すなわち、プリント基板、LSI等の配線
領域を直交座標によつて格子状に分割し、接続す
べき経路の両端の格子対（一般に複数対ある）を
区間データとして記憶する区間データ記憶部１
と、配線領域上の各格子の使用状態を記憶するた
めの格子マツプ記憶部２と、配線領域の格子マツ
プを複数個の領域に分割してそれぞれの分割領域
内に両端の格子を有する区間データに対して対応
する領域の番号を付与して領域の分割管理を行な
う領域制御部３と、該領域制御部３により分割さ
れた複数の領域にそれぞれ複数のプロセツサ６ａ
〜６ｉを１個ずつ割当て前記区間データ記憶部か
ら読み出した両端部が同一の分割領域内にある区
間データを対応するプロセツサへ供給し各プロセ
ツサの動作を制御する配線制御部５と、与えられ
た区間データの両端格子間の経路を探索する複数
のプロセツサ６ａ〜６ｉを含む配線処理部７と、
配線処理部７の各プロセツサの探索した経路デー
タにより前記格子マツプ記憶部２の内容を更新し
かつ前記区間データ記憶部１に配線ずみまたは未
了を通知する経路データ出力部８と、経路データ
出力部８の出力データにより経路データを記憶す
る経路データ記憶部４とから構成されている。
領域制御部３は、例えば第２図に示すように、
配線領域全体の格子マツプ１０を９個の領域９ａ
〜９ｉに分割し、各領域にそれぞれ領域番号（例
えば９ａ〜９ｉ）を付与し、その領域の各格子の
座標と共に保存する。そして、区間データ記憶部
１から区間データを順次入力し、該区間データの
両端の格子が前記分割されたいずれか１つの領域
内に含まれるか否かを判定し、含まれる場合はそ
の領域番号を区間データ記憶部１の対応する区間
データに付与して区間データ記憶部１へ書込む。
配線領域全体の格子マツプ１０を９個の領域９ａ
〜９ｉに分割し、各領域にそれぞれ領域番号（例
えば９ａ〜９ｉ）を付与し、その領域の各格子の
座標と共に保存する。そして、区間データ記憶部
１から区間データを順次入力し、該区間データの
両端の格子が前記分割されたいずれか１つの領域
内に含まれるか否かを判定し、含まれる場合はそ
の領域番号を区間データ記憶部１の対応する区間
データに付与して区間データ記憶部１へ書込む。
配線制御部５は、区間データ記憶部１に格納さ
れた区間データのうち、それぞれ異なる領域番号
が付与された区間データを１個ずつ読出して、各
区間データをそれぞれ９個のプロセツサ６ａ〜６
ｉに１対１に割当て、各プロセツサにそれぞれ区
間データとその領域番号を入力する。
れた区間データのうち、それぞれ異なる領域番号
が付与された区間データを１個ずつ読出して、各
区間データをそれぞれ９個のプロセツサ６ａ〜６
ｉに１対１に割当て、各プロセツサにそれぞれ区
間データとその領域番号を入力する。
各プロセツサは、それぞれ格子マツプ記憶部２
から割当て領域内の格子マツプを入力し、該格子
マツプと上記区間データから一定のアルゴリズム
により両端点格子間の経路探索を行ない、最適ル
ートの経路情報を経路データ出力部８へ渡す。経
路探索のアルゴリズムは従来と同様な方法を使用
することができるが、領域が小さいから最適ルー
トの選定は容易である。経路データ出力部８は、
経路がみつかつた場合は、その経路データによつ
て格子マツプ記憶部２を更新し、かつ区間データ
記憶部１の対応する区間データに対して配線済み
であることが示すマークを書込む。なお、経路デ
ータ記憶部４には探索された経路が記憶される。
経路が見つからなかつた場合は、区間データ記憶
部１の対応する区間データに対して未配線である
ことを示すマークを書込む。上述の各領域内にお
ける経路探索は、複数のプロセツサ６ａ〜６ｉに
よつて同時に平行して行なわれるから、探索に要
する時間は大幅に短縮される。
から割当て領域内の格子マツプを入力し、該格子
マツプと上記区間データから一定のアルゴリズム
により両端点格子間の経路探索を行ない、最適ル
ートの経路情報を経路データ出力部８へ渡す。経
路探索のアルゴリズムは従来と同様な方法を使用
することができるが、領域が小さいから最適ルー
トの選定は容易である。経路データ出力部８は、
経路がみつかつた場合は、その経路データによつ
て格子マツプ記憶部２を更新し、かつ区間データ
記憶部１の対応する区間データに対して配線済み
であることが示すマークを書込む。なお、経路デ
ータ記憶部４には探索された経路が記憶される。
経路が見つからなかつた場合は、区間データ記憶
部１の対応する区間データに対して未配線である
ことを示すマークを書込む。上述の各領域内にお
ける経路探索は、複数のプロセツサ６ａ〜６ｉに
よつて同時に平行して行なわれるから、探索に要
する時間は大幅に短縮される。
区間データ記憶部１に格納された区間データの
うち、領域番号の付されたもの（同一領域内に両
端点があるもの）については、同様にして複数の
プロセツサによつて平行的に処理され、配線経路
の見つかつたものに対しては、それぞれ格子マツ
プ記憶部２が更新され、経路データ記憶部４に格
納される。また区間データ記憶部１に配線済みの
マークが格納される。上述の動作によつて、各領
域内で配線可能なものについての経路が決定され
る。
うち、領域番号の付されたもの（同一領域内に両
端点があるもの）については、同様にして複数の
プロセツサによつて平行的に処理され、配線経路
の見つかつたものに対しては、それぞれ格子マツ
プ記憶部２が更新され、経路データ記憶部４に格
納される。また区間データ記憶部１に配線済みの
マークが格納される。上述の動作によつて、各領
域内で配線可能なものについての経路が決定され
る。
両端点が同一領域内に存在するが、領域内の経
路によつては接続されなかつたもの（未配線のマ
ークが付されている）および領域間にまたがる区
間データについての経路を探索するために、領域
制御部３は、格子マツプを以前よりも拡大した領
域に再分割する。例えば、第３図に示すように、
格子マツプ１０を領域１１ａ〜１１ｄに４分割す
る。そして、前記未配線のマークの付された区間
データおよび上記新しく分割された領域内に両端
点を有する区間データに対して上記新しい領域番
号を付与する。配線制御部５は、上記４分割され
た領域に対して、それぞれ例えばプロセツサ６ａ
〜６ｄを割当て、各プロセツサに対して対応する
区間データを与える。各プロセツサは、格子マツ
プ記憶部２から対応する領域の格子マツプを入力
し、区間データ両端点間の経路を探索する。見つ
かつた経路は、前述と同様に経路データ出力部８
を介して経路データ記憶部４に記憶させ、また格
子マツプ記憶部２の更新および区間データ記憶部
１への配線済みマークの書込みが行なわれる。経
路が見つからかなかつ区間データに対しては、区
間データ記憶部１に未配線を示すマークが書込ま
れる。
路によつては接続されなかつたもの（未配線のマ
ークが付されている）および領域間にまたがる区
間データについての経路を探索するために、領域
制御部３は、格子マツプを以前よりも拡大した領
域に再分割する。例えば、第３図に示すように、
格子マツプ１０を領域１１ａ〜１１ｄに４分割す
る。そして、前記未配線のマークの付された区間
データおよび上記新しく分割された領域内に両端
点を有する区間データに対して上記新しい領域番
号を付与する。配線制御部５は、上記４分割され
た領域に対して、それぞれ例えばプロセツサ６ａ
〜６ｄを割当て、各プロセツサに対して対応する
区間データを与える。各プロセツサは、格子マツ
プ記憶部２から対応する領域の格子マツプを入力
し、区間データ両端点間の経路を探索する。見つ
かつた経路は、前述と同様に経路データ出力部８
を介して経路データ記憶部４に記憶させ、また格
子マツプ記憶部２の更新および区間データ記憶部
１への配線済みマークの書込みが行なわれる。経
路が見つからかなかつ区間データに対しては、区
間データ記憶部１に未配線を示すマークが書込ま
れる。
次に領域制御部３は、格子マツプをさらに拡大
した領域に分割して同様な処理を行ない、最後に
全配線領域について同様な処理を行なうことによ
り全部の区間データについて経路探索が完了す
る。
した領域に分割して同様な処理を行ない、最後に
全配線領域について同様な処理を行なうことによ
り全部の区間データについて経路探索が完了す
る。
以上のように、本発明においては、配線領域を
複数の領域に分割し、複数の分割された領域に対
してそれぞれ１個のプロセツサを割当てて、各領
域内に両端点を有する区間データについての経路
探索を上記複数のプロセツサによつて同時に平行
して行なうように構成したから、処理時間が従来
に比して大幅に短縮される効果がある。上記分割
された領域内で経路の見つからなかつたものおよ
び上記分割された領域間にまたがる配線について
は、分割領域を逐次拡大して行くことによつて経
路探索が可能である。全体として、経路探索のコ
ンピュータ時間を従来より大幅に削減することが
できる。
複数の領域に分割し、複数の分割された領域に対
してそれぞれ１個のプロセツサを割当てて、各領
域内に両端点を有する区間データについての経路
探索を上記複数のプロセツサによつて同時に平行
して行なうように構成したから、処理時間が従来
に比して大幅に短縮される効果がある。上記分割
された領域内で経路の見つからなかつたものおよ
び上記分割された領域間にまたがる配線について
は、分割領域を逐次拡大して行くことによつて経
路探索が可能である。全体として、経路探索のコ
ンピュータ時間を従来より大幅に削減することが
できる。
第１図は、本発明の一実施例を示すブロツク
図、第２図は上記実施例において９分割された格
子マツプを示す図、第３図は上記実施例において
４分割された格子マツプを示す図である。 図において、１……区間データ記憶部、２……
格子マツプ記憶部、３……領域制御部、４……経
路データ記憶部、５……配線制御部、６ａ〜６ｉ
……プロセツサ、７……配線処理部、８……経路
データ出力部、９ａ〜９ｉ……９分割された格子
マツプの領域、１０……格子マツプ、１１ａ〜１
１ｄ……４分割された格子マツプの領域。
図、第２図は上記実施例において９分割された格
子マツプを示す図、第３図は上記実施例において
４分割された格子マツプを示す図である。 図において、１……区間データ記憶部、２……
格子マツプ記憶部、３……領域制御部、４……経
路データ記憶部、５……配線制御部、６ａ〜６ｉ
……プロセツサ、７……配線処理部、８……経路
データ出力部、９ａ〜９ｉ……９分割された格子
マツプの領域、１０……格子マツプ、１１ａ〜１
１ｄ……４分割された格子マツプの領域。
Claims (1)
- 【特許請求の範囲】 １ プリント板、LSI等の配線領域を直交座標に
基づき格子状に分割し、接続すべき経路のそれぞ
れの両端の格子対をプロセツサで探索して配線経
路を求める経路探索処理方式において、 分割された接続すべき経路のそれぞれの両端の
格子対を領域番号とともに区間データとして記憶
する区間データ記憶部と、 配線領域上の各格子の使用状態情報を記憶する
格子マツプ記憶部と、 全体の格子を複数領域に分割しこの分割された
領域に領域番号を付与し、その領域内の接続経路
の探索を複数のプロセツサのそれぞれに割当てる
領域制御部と、 この領域制御部で分割された領域のそれぞれに
ついて上記区間データ記憶部から読み出した区間
データおよび領域番号を割当てられたプロセツサ
に入力する配線制御部と、 上記配線制御部から入力され上記領域制御部で
割当てられたそれぞれの領域に属する区間デー
タ、および上記格子マツプ記憶部に記憶された格
子の使用状態情報から格子対間の接続経路を探索
する複数のプロセツサを含む配線処理部と、 経路情報を記憶する経路データ記憶部と、 上記配線制御部で探索された結果を出力してそ
の結果により、上記格子マツプ記憶部の格子の使
用状態情報を変更し、上記区間データ記憶部に配
線済であるか否かの情報を記憶させ、上記経路デ
ータ記憶部に探索された経路を記憶させる経路デ
ータ出力部と を備え、 上記領域制御部は、 順次探索すべき分割領域を拡大して再分割する
手段と、 この再分割された領域内の区間データに領域番
号を付与する手段と、 この新たな領域番号を付与した各領域に新たに
プロセツサに割当てる手段と を含むことを特徴とする経路探索処理方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58062204A JPS59188772A (ja) | 1983-04-11 | 1983-04-11 | 経路探索処理方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58062204A JPS59188772A (ja) | 1983-04-11 | 1983-04-11 | 経路探索処理方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS59188772A JPS59188772A (ja) | 1984-10-26 |
| JPS648875B2 true JPS648875B2 (ja) | 1989-02-15 |
Family
ID=13193379
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58062204A Granted JPS59188772A (ja) | 1983-04-11 | 1983-04-11 | 経路探索処理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS59188772A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02224182A (ja) * | 1989-02-27 | 1990-09-06 | Nec Corp | 配線編集処理方式 |
-
1983
- 1983-04-11 JP JP58062204A patent/JPS59188772A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS59188772A (ja) | 1984-10-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0612023A2 (en) | Net diagram routing method | |
| US6496968B1 (en) | Hierarchical wiring method for a semiconductor integrated circuit | |
| JPS648875B2 (ja) | ||
| US5394337A (en) | Method for wire routing of a semiconductor integrated circuit and apparatus for implementing the same | |
| CN118966140A (zh) | 一种fpc区域识别和布线通道划分方法 | |
| CN120722647B (zh) | 基于分组合并的空间块汇聚方法、装置、存储介质及电子设备 | |
| JP2536640B2 (ja) | 配線処理方式 | |
| JP2751199B2 (ja) | 配線経路探索方式及び装置 | |
| JP3304445B2 (ja) | プログラム生成処理装置 | |
| JP3293640B2 (ja) | 回路データ接続追跡システム | |
| CN121390341A (zh) | 量子芯片版图的引脚关联方法、系统、介质及设备 | |
| JP2557368B2 (ja) | 配線基板設計支援方法 | |
| JPH0645446A (ja) | 配置配線方法 | |
| JP2656344B2 (ja) | 自動配線方法 | |
| JPS61260345A (ja) | マルチプロセサ間のバス制御方式 | |
| JPH0327589A (ja) | 多層配線方法 | |
| JPS62212882A (ja) | 並列計算機システム | |
| JPS59176866A (ja) | プリント板の自動配線方法 | |
| JPH0494151A (ja) | 集積回路の並列配線処理方法 | |
| Krishnamurthy | On designing parallel algorithms with applications to VLSI routing | |
| JPH07202000A (ja) | 並列処理によるｌｓｉ配線方式 | |
| JPH04359377A (ja) | 配線層割付方式 | |
| JPS6325779A (ja) | 配線決定処理方式 | |
| JPH0450627B2 (ja) | ||
| JPH01293472A (ja) | Ｃａｄによる回路基板の配線経路探索方法 |