JPH0550780B2 - - Google Patents
Info
- Publication number
- JPH0550780B2 JPH0550780B2 JP87239517A JP23951787A JPH0550780B2 JP H0550780 B2 JPH0550780 B2 JP H0550780B2 JP 87239517 A JP87239517 A JP 87239517A JP 23951787 A JP23951787 A JP 23951787A JP H0550780 B2 JPH0550780 B2 JP H0550780B2
- Authority
- JP
- Japan
- Prior art keywords
- processing module
- wiring
- grid
- grid point
- data
- 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 - Lifetime
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)
- Design And Manufacture Of Integrated Circuits (AREA)
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明はプリント配線板や大規模集積回路
（LSI）チツプ等の配線設計を自動的に行うため
に用いられる配線経路探索方式に関する。
（LSI）チツプ等の配線設計を自動的に行うため
に用いられる配線経路探索方式に関する。
Computer Aided Design（CAD）システム等
で配線の自動設計に用いられる従来の経路探索方
式の一例が特開昭61−199166号公報に示されてい
る。この公報に記載された方式では、配線経路探
索時の配線障害データとして、初期化処理時入力
される固定的な障害データが採用されている。こ
の方式では。さらに、１区間配線完了毎に発見さ
れた配線経路位置の格子点に対して、全面的な配
線禁止データのみがセツトされる。このデータは
該格子点に対して全く配線が進行できないことを
示す。
で配線の自動設計に用いられる従来の経路探索方
式の一例が特開昭61−199166号公報に示されてい
る。この公報に記載された方式では、配線経路探
索時の配線障害データとして、初期化処理時入力
される固定的な障害データが採用されている。こ
の方式では。さらに、１区間配線完了毎に発見さ
れた配線経路位置の格子点に対して、全面的な配
線禁止データのみがセツトされる。このデータは
該格子点に対して全く配線が進行できないことを
示す。
したがつて、２層の配線格子を有するプリント
配線基板やLSIの配線設計時、片側の層における
他の配線が走行している場合でも、もう一方の層
で配線経路探索を全く自由に行なえる。この結
果、片側層における走行配線と他の層における同
じ水平座標を有する走行配線とが、上下で平行し
て走行することにより大きなクロストークが発生
し、回路が誤動作するという欠点がある。
配線基板やLSIの配線設計時、片側の層における
他の配線が走行している場合でも、もう一方の層
で配線経路探索を全く自由に行なえる。この結
果、片側層における走行配線と他の層における同
じ水平座標を有する走行配線とが、上下で平行し
て走行することにより大きなクロストークが発生
し、回路が誤動作するという欠点がある。
本発明の配線経路探索方式は、配線を禁止する
配線禁止データと、特定方向の配線を禁止するト
ラツク禁止データとからなる障害物を、前記多層
平面の各格子点ごとに保持するグリツドマツプ
と、前記障害物を避けて配線経路を探索し、決定
する決定手段と、前記決定手段により決定された
配線経路の各線分について、該線分の真上の隣接
格子点および真下の隣接格子点の少なくとも一方
において該線分データと同一方向の配線が禁止さ
れるように、前記グリツドマツプに前記トラツク
禁止データを設定する発生手段とを有する。
配線禁止データと、特定方向の配線を禁止するト
ラツク禁止データとからなる障害物を、前記多層
平面の各格子点ごとに保持するグリツドマツプ
と、前記障害物を避けて配線経路を探索し、決定
する決定手段と、前記決定手段により決定された
配線経路の各線分について、該線分の真上の隣接
格子点および真下の隣接格子点の少なくとも一方
において該線分データと同一方向の配線が禁止さ
れるように、前記グリツドマツプに前記トラツク
禁止データを設定する発生手段とを有する。
次に本発明の最適な一実施例について図面を参
照して詳細に説明する。
照して詳細に説明する。
第１図を参照すると、本発明の一実施例は、基
板の配線経路を示すための６×６の格子点におけ
る配線禁止データを表示するためのグリツドマツ
プ１１７、このグリツドマツプ１１７を初期化す
るための処理モジユール１０１、フアイルOBS
１１３から入力された部品ピンデータにもとづい
て計算されたグリツドマツプ１１７の位置にフア
イルOBS１１３から与えられる配線禁止データ、
Ｘトラツク禁止データ及びＹトラツク禁止データ
を与える処理モジユール１０２、フアイルPAT1
１１４から与えられる既配線部品として予め確
保しておきたい経路を示す経路データを障害物情
報としてグリツドマツプ１１７にセツトするとと
もに、該経路データの存在する層と反対側の層に
経路データ走行方向と同一方向の配線走行を禁止
するためのＸトラツク禁止データもしくはＹトラ
ツク禁止データをグリツドマツプ１１７にセツト
するための処理モジユール１０３、未処理の配線
区間の存在の有無を判定する処理モジユール１０
４、フアイルCON１１５から始点の格子点位置
情報と終点の格子点位置情報とを含む未処理の配
線区間データの１つを入力し、インタフエーステ
ーブル１１６にセツトする処理モジユール１０
５、インタフエーステーブル１１６からの配線デ
ータに基づきグリツドマツプ１１７を参照して障
害物を避けて配線経路を探索し、配線経路の発見
に応答して発見された配線経路に対する複数の格
子点位置情報からなる経路データをインタフエー
ステーブル１１６に格納する処理モジユール１０
６、この処理モジユール１０６で配線経路を発見
したか否かを判断する処理モジユール１０７、こ
の処理モジユール１０７での配線経路発見の判断
に応答してインタフエーステーブル１１６の配線
データ内で未処理の線分データが存在するか否か
を判断する処理モジユール１０８、この処理モジ
ユール１０８での未処理の線分データ存在の判断
に応答してインタフエーステーブル１１６から未
処理の線分データを取り出す処理モジユール１０
９、線分データを配線経路探索における障害物と
してグリツドマツプ１１７にセツトする処理モジ
ユール１１０、線分データを配線結果としてフア
イルPAT2 １１８に出力する処理モジユール１
１１、及び線分データ存在層と反対の層に線分デ
ータと同一方向の配線を禁止するためのトラツク
禁止データをグリツドマツプ１１７にセツトし処
理モジユール１０８に制御を移す処理モジユール
１１２から構成されている。
板の配線経路を示すための６×６の格子点におけ
る配線禁止データを表示するためのグリツドマツ
プ１１７、このグリツドマツプ１１７を初期化す
るための処理モジユール１０１、フアイルOBS
１１３から入力された部品ピンデータにもとづい
て計算されたグリツドマツプ１１７の位置にフア
イルOBS１１３から与えられる配線禁止データ、
Ｘトラツク禁止データ及びＹトラツク禁止データ
を与える処理モジユール１０２、フアイルPAT1
１１４から与えられる既配線部品として予め確
保しておきたい経路を示す経路データを障害物情
報としてグリツドマツプ１１７にセツトするとと
もに、該経路データの存在する層と反対側の層に
経路データ走行方向と同一方向の配線走行を禁止
するためのＸトラツク禁止データもしくはＹトラ
ツク禁止データをグリツドマツプ１１７にセツト
するための処理モジユール１０３、未処理の配線
区間の存在の有無を判定する処理モジユール１０
４、フアイルCON１１５から始点の格子点位置
情報と終点の格子点位置情報とを含む未処理の配
線区間データの１つを入力し、インタフエーステ
ーブル１１６にセツトする処理モジユール１０
５、インタフエーステーブル１１６からの配線デ
ータに基づきグリツドマツプ１１７を参照して障
害物を避けて配線経路を探索し、配線経路の発見
に応答して発見された配線経路に対する複数の格
子点位置情報からなる経路データをインタフエー
ステーブル１１６に格納する処理モジユール１０
６、この処理モジユール１０６で配線経路を発見
したか否かを判断する処理モジユール１０７、こ
の処理モジユール１０７での配線経路発見の判断
に応答してインタフエーステーブル１１６の配線
データ内で未処理の線分データが存在するか否か
を判断する処理モジユール１０８、この処理モジ
ユール１０８での未処理の線分データ存在の判断
に応答してインタフエーステーブル１１６から未
処理の線分データを取り出す処理モジユール１０
９、線分データを配線経路探索における障害物と
してグリツドマツプ１１７にセツトする処理モジ
ユール１１０、線分データを配線結果としてフア
イルPAT2 １１８に出力する処理モジユール１
１１、及び線分データ存在層と反対の層に線分デ
ータと同一方向の配線を禁止するためのトラツク
禁止データをグリツドマツプ１１７にセツトし処
理モジユール１０８に制御を移す処理モジユール
１１２から構成されている。
次に本発明の一実施例の動作について第１図か
ら第１８図を参照して詳細に説明する。
ら第１８図を参照して詳細に説明する。
第１図を参照すると、実線の矢印は処理の流れ
を、破線の矢印はデータの流れを示している。
を、破線の矢印はデータの流れを示している。
まず、処理モジユール１０１により、グリツド
マツプ１１７に割当てられたメモリ上の記憶領域
の記憶位置が初期設定される。すなわち、第９ａ
図で示される６×６格子の上層のグリツドマツプ
及び第９ｂ図で示される６×６格子の下層のグリ
ツドマツプの格子点を示す四角の上段（すなわち
第５図で示されるLA５０１）及び下段（すなわ
ち第５図で示されるMS５０２）が全て“０”に
設定される。この結果、全ての格子点は空き状態
となる。
マツプ１１７に割当てられたメモリ上の記憶領域
の記憶位置が初期設定される。すなわち、第９ａ
図で示される６×６格子の上層のグリツドマツプ
及び第９ｂ図で示される６×６格子の下層のグリ
ツドマツプの格子点を示す四角の上段（すなわち
第５図で示されるLA５０１）及び下段（すなわ
ち第５図で示されるMS５０２）が全て“０”に
設定される。この結果、全ての格子点は空き状態
となる。
続いて処理モジユール１０２で各種データがフ
アイルOBS１１３から入力される。この各種デ
ータの内、部品ピンデータは格子点の位置情報
（ｍ，ｎ，ｚ）を含み、この格子点位置情報で示
される位置にピンが設けられる。ピンデータの格
子点位置情報によりアドレス｛Ａ＋（ｚ−１）×Ｂ
＋（ｍ−１）×Ｃ＋（ｎ−１）｝が計算される。この
計算結果によりグリツドマツプ１１７内の対応す
る格子点データが指定される。この指定された格
子点データのフイールドLA５０１に値“11”が
設定される。Ｘトラツク禁止データは上述の位置
情報を含み、格子点位置情報により指定された格
子データのフイールドLA５０１に値“01”が設
定される。Ｙトラツク禁止データは上述の位置情
報を含み格子点位置情報により指定された格子点
データのフイールドLA５０１に“10”が設定さ
れる。この処理モジユール１０２によつて配線禁
止データ（１，１，１）（１，１，２）（１，２，
１）（１，２，２）（１，３，１）（１，３，２）
（１，４，１）（１，４，２）（１，５，１）（１，
５，２）（１，６，１）（１，６，２）（２，１，
１）（２，１，２）（３，１，１）（３，１，２）
（４，１，１）（４，１，２）（５，１，１）（５，
１，２）（６，１，１）（６，１，２）（６，２，
１）（６，２，２）（６，３，１）（６，３，２）
（６，４，１）（６，４，２）（６，５，１）（６，
５，２）（６，６，１）（６，６，２）（２，６，
１）（２，６，２）（３，６，１）（３，６，２）
（４，６，１）（４，６，２）（５，６，１）（５，
６，２）及び部品ピンデータ（２，５，１）（２，
４，１）（５，４，１）（５，２，１）（３，２，
２）（４，５，２）が第１０ａ図で示される６×
６格子の上層のグリツドマツプ及び第１０ｂ図で
示される６×６格子の下層のグリツドマツプの各
格子点の表す四角の上段（第５図に示される）
LA５０１に“11”として設定される。また、こ
の処理モジユール１０２により、第７図に示され
る６×６格子のグリツドマツプを表す格子上に第
１０ａ図、第１０ｂ図と同じく配線禁止データ７
０１がセツトされる。ここで、配線禁止データが
セツトされた格子点はすべての方向の配線の走行
を禁止する障害物として働く。Ｘトラツク禁止デ
ータ及びＹトラツク禁止データがセツトされた格
子点はそれぞれＸ方向及びＸ方向と垂直なＹ方向
の配線の走行を禁止する障害物として働く。また
斜め方向すなわちＸ方向と垂直でない方向への配
線も許す場合には、斜め方向の配線の走行を禁止
する障害物を設定することも勿論可能である。し
かし説明を簡単化するため、以後は配線の走行方
向がＸ方向及びＹ方向に限定された場合について
説明する。
アイルOBS１１３から入力される。この各種デ
ータの内、部品ピンデータは格子点の位置情報
（ｍ，ｎ，ｚ）を含み、この格子点位置情報で示
される位置にピンが設けられる。ピンデータの格
子点位置情報によりアドレス｛Ａ＋（ｚ−１）×Ｂ
＋（ｍ−１）×Ｃ＋（ｎ−１）｝が計算される。この
計算結果によりグリツドマツプ１１７内の対応す
る格子点データが指定される。この指定された格
子点データのフイールドLA５０１に値“11”が
設定される。Ｘトラツク禁止データは上述の位置
情報を含み、格子点位置情報により指定された格
子データのフイールドLA５０１に値“01”が設
定される。Ｙトラツク禁止データは上述の位置情
報を含み格子点位置情報により指定された格子点
データのフイールドLA５０１に“10”が設定さ
れる。この処理モジユール１０２によつて配線禁
止データ（１，１，１）（１，１，２）（１，２，
１）（１，２，２）（１，３，１）（１，３，２）
（１，４，１）（１，４，２）（１，５，１）（１，
５，２）（１，６，１）（１，６，２）（２，１，
１）（２，１，２）（３，１，１）（３，１，２）
（４，１，１）（４，１，２）（５，１，１）（５，
１，２）（６，１，１）（６，１，２）（６，２，
１）（６，２，２）（６，３，１）（６，３，２）
（６，４，１）（６，４，２）（６，５，１）（６，
５，２）（６，６，１）（６，６，２）（２，６，
１）（２，６，２）（３，６，１）（３，６，２）
（４，６，１）（４，６，２）（５，６，１）（５，
６，２）及び部品ピンデータ（２，５，１）（２，
４，１）（５，４，１）（５，２，１）（３，２，
２）（４，５，２）が第１０ａ図で示される６×
６格子の上層のグリツドマツプ及び第１０ｂ図で
示される６×６格子の下層のグリツドマツプの各
格子点の表す四角の上段（第５図に示される）
LA５０１に“11”として設定される。また、こ
の処理モジユール１０２により、第７図に示され
る６×６格子のグリツドマツプを表す格子上に第
１０ａ図、第１０ｂ図と同じく配線禁止データ７
０１がセツトされる。ここで、配線禁止データが
セツトされた格子点はすべての方向の配線の走行
を禁止する障害物として働く。Ｘトラツク禁止デ
ータ及びＹトラツク禁止データがセツトされた格
子点はそれぞれＸ方向及びＸ方向と垂直なＹ方向
の配線の走行を禁止する障害物として働く。また
斜め方向すなわちＸ方向と垂直でない方向への配
線も許す場合には、斜め方向の配線の走行を禁止
する障害物を設定することも勿論可能である。し
かし説明を簡単化するため、以後は配線の走行方
向がＸ方向及びＹ方向に限定された場合について
説明する。
処理モジユール１０３では、フアイルPAT1
１１４からの経路データを障害物情報として、グ
リツドマツプ１１７にセツトする。すなわちマツ
プ１１７の対応格子データ部のLA５０１に値
“11”がセツトされる。また、Ｘトラツク禁止デ
ータまたはＹトラツク禁止データが、グリツドマ
ツプ１１７の対応格子データ群のLA５０１に
“01”または“10”としてセツトされる。ここで
セツトされたＸトラツク禁止データ及びＹトラツ
ク禁止データは、経路データの存在層と反対側の
層に経路データ走行方向と同一方向の走行を禁止
させるためのデータである。この処理モジユール
１０３では、経路データとして第１１ａ図に示す
６×６格子の上層のグリツドマツプ及び第１１ｂ
図に示す６×６格子の下層のグリツドマツプの各
格子点の表す四角の上段のLA５０１に（２，４，
１）（３，４，１）（４，４，１）（５，４，１）
では“11”が（２，４，２）（３，４，２）（４，
４，２）（５，４，２）では“01”がセツトされ
る。また、第７図では配線禁止７０４及びＸトラ
ツク禁止７０３がセツトされる。同様にして処理
モジユール１０３により経路データとして、第１
２ａ図に示す６×６格子の上層のグリツドマツプ
及び第１２ｂ図に示す６×６格子の下層のグリツ
ドマツプ各格子点の表す四角の上段のLA５０１
に（４，５，２）（４，４，２）（４，３，２）
（４，２，２）（３，２，２）では“11”がセツト
され、（４，５，１）（４，３，１）（４，２，１）
では“10”を（３，２，１）では“01”がセツト
される。また、第７図では配線禁止７０５及びＸ
トラツク禁止７０６及びＹトラツク禁止７０２が
セツトされる。
１１４からの経路データを障害物情報として、グ
リツドマツプ１１７にセツトする。すなわちマツ
プ１１７の対応格子データ部のLA５０１に値
“11”がセツトされる。また、Ｘトラツク禁止デ
ータまたはＹトラツク禁止データが、グリツドマ
ツプ１１７の対応格子データ群のLA５０１に
“01”または“10”としてセツトされる。ここで
セツトされたＸトラツク禁止データ及びＹトラツ
ク禁止データは、経路データの存在層と反対側の
層に経路データ走行方向と同一方向の走行を禁止
させるためのデータである。この処理モジユール
１０３では、経路データとして第１１ａ図に示す
６×６格子の上層のグリツドマツプ及び第１１ｂ
図に示す６×６格子の下層のグリツドマツプの各
格子点の表す四角の上段のLA５０１に（２，４，
１）（３，４，１）（４，４，１）（５，４，１）
では“11”が（２，４，２）（３，４，２）（４，
４，２）（５，４，２）では“01”がセツトされ
る。また、第７図では配線禁止７０４及びＸトラ
ツク禁止７０３がセツトされる。同様にして処理
モジユール１０３により経路データとして、第１
２ａ図に示す６×６格子の上層のグリツドマツプ
及び第１２ｂ図に示す６×６格子の下層のグリツ
ドマツプ各格子点の表す四角の上段のLA５０１
に（４，５，２）（４，４，２）（４，３，２）
（４，２，２）（３，２，２）では“11”がセツト
され、（４，５，１）（４，３，１）（４，２，１）
では“10”を（３，２，１）では“01”がセツト
される。また、第７図では配線禁止７０５及びＸ
トラツク禁止７０６及びＹトラツク禁止７０２が
セツトされる。
続いて、処理モジユール１０４において、未処
理の配線区間データの存在の有無が判定される。
この未処理の配線区間データの非存在の判定に応
答して処理は終了する。未処理の配線区間データ
の存在の判定に応答して制御が処理モジユール１
０５に移される。
理の配線区間データの存在の有無が判定される。
この未処理の配線区間データの非存在の判定に応
答して処理は終了する。未処理の配線区間データ
の存在の判定に応答して制御が処理モジユール１
０５に移される。
この処理モジユール１０５では、フアイル
CON１１５から始点の格子点位置情報と終点の
格子点位置情報とを含む配線区間データが１つ入
力され、インタフエーステーブル１１６にセツト
される。
CON１１５から始点の格子点位置情報と終点の
格子点位置情報とを含む配線区間データが１つ入
力され、インタフエーステーブル１１６にセツト
される。
次に処理モジユール１０６での詳細な動作を第
２図、第３図及び第４図を参照して詳細に説明す
る。
２図、第３図及び第４図を参照して詳細に説明す
る。
第２図を参照すると、最初に処理モジユール２
０１でインタフエーステーブル１１６から始点格
子点の位置情報が取り出される。次に処理モジユ
ール２０２でワークテーブルWTBL1にこの始点
の位置情報が格納される。ここでワークテーブル
２２２WTBL1は、各ステツプにおいて探索源と
なる格子点の位置情報格納のためのメモリ内に設
けられたテーブルである。結線すべき始点を
（２，５，１）、終点を（５，２，１）と仮定した
時に処理モジユール２０１及び処理モジユール２
０２で始点（２，５，１）が第１７図のようにワ
ークテーブル２２２WTBL1に格納される。
０１でインタフエーステーブル１１６から始点格
子点の位置情報が取り出される。次に処理モジユ
ール２０２でワークテーブルWTBL1にこの始点
の位置情報が格納される。ここでワークテーブル
２２２WTBL1は、各ステツプにおいて探索源と
なる格子点の位置情報格納のためのメモリ内に設
けられたテーブルである。結線すべき始点を
（２，５，１）、終点を（５，２，１）と仮定した
時に処理モジユール２０１及び処理モジユール２
０２で始点（２，５，１）が第１７図のようにワ
ークテーブル２２２WTBL1に格納される。
次に処理モジユール２０３でステツプカウンタ
SCに１がセツトされる。続いて処理モジユール
２０４でワークテーブル２２２WTBL1が空にな
つたか否かが判定される。空の判定に応答して処
理モジユール２１５へ分岐される。更にワークテ
ーブル２２２WTBL2が空になつたか否かが処理
モジユール２１５で判定される。ここでワークテ
ーブル２２２WTBL2は、ワークテーブル２２２
WTBL1に格納された格子点と接続可能な全ての
隣接格子点位置情報を格納するためのテーブルで
ある。
SCに１がセツトされる。続いて処理モジユール
２０４でワークテーブル２２２WTBL1が空にな
つたか否かが判定される。空の判定に応答して処
理モジユール２１５へ分岐される。更にワークテ
ーブル２２２WTBL2が空になつたか否かが処理
モジユール２１５で判定される。ここでワークテ
ーブル２２２WTBL2は、ワークテーブル２２２
WTBL1に格納された格子点と接続可能な全ての
隣接格子点位置情報を格納するためのテーブルで
ある。
処理モジユール２１５におけるワークテーブル
２２２WTBL2の空の判定に応答して処理モジユ
ール２２１へ制御が移される。このモジユール２
２１では経路を発見できなかつた旨のフラグがセ
ツトされ、処理が終了する。これは経路探索が行
き詰まつた状態を意味する。
２２２WTBL2の空の判定に応答して処理モジユ
ール２２１へ制御が移される。このモジユール２
２１では経路を発見できなかつた旨のフラグがセ
ツトされ、処理が終了する。これは経路探索が行
き詰まつた状態を意味する。
処理モジユール２１５におけるワークテーブル
２２２WTBL2の空でない判定に応答して、処理
モジユール２１６でワークテーブル２２２
WTBL2の全ての内容がワークテーブル２２２
WTBL1にコピーされたあと、コピーされた内容
がワークテーブル２２２WTBL1から除去され
る。
２２２WTBL2の空でない判定に応答して、処理
モジユール２１６でワークテーブル２２２
WTBL2の全ての内容がワークテーブル２２２
WTBL1にコピーされたあと、コピーされた内容
がワークテーブル２２２WTBL1から除去され
る。
次に処理モジユール２１７でステツプカウンタ
SCの内容がカウントアツプされて処理モジユー
ル２０４へ分岐される。
SCの内容がカウントアツプされて処理モジユー
ル２０４へ分岐される。
処理モジユール２０４でワークテーブル２２２
WTBL1が空でないとの判定に応答して、処理モ
ジユール２０５でワークテーブル２２２WTBL1
から格子点位置情報が１つ取り出され、その格子
を第４図の格子点CC４０１とする。取り出され
た位置情報はワークテーブル２２２WTBL1から
除去される。
WTBL1が空でないとの判定に応答して、処理モ
ジユール２０５でワークテーブル２２２WTBL1
から格子点位置情報が１つ取り出され、その格子
を第４図の格子点CC４０１とする。取り出され
た位置情報はワークテーブル２２２WTBL1から
除去される。
次に、処理モジユール２０６ではｉに１がセツ
トされる。
トされる。
次に、判断モジユール２０７で第４図の格子点
NC（ｉ）４０２〜４０７の位置情報が終点の格
子点と一致するかどうかが判定される。一致判定
に応答して、処理モジユール２１８で終点格子点
から始点格子点に向かつて経路がトレースされ
る。次に処理モジユール２１９において処理モジ
ユール２１８の処理により得られた配線経路デー
タがインタフエーステーブル２１４にセツトされ
る。第１２ａ図で示す６×６格子の上層のグリツ
ドマツプ及び第１２ｂ図で示す６×16格子の下層
のグリツドマツプにおいて、第４図の格子点CC
４０１が（２，５，１）である時の格子点NC
（１）４０２は（３，５，１）である。この格子
点は、終点（５，２，１）に等しくないので処理
モジユール２０８に制御が移される。一方、第１
５ａ図で示す６×６格子の上層のグリツドマツプ
及び第１５ｂ図で示す６×６格子の下層のグリツ
ドマツプにおいては、第４図の格子点CC４０１
が（５，２，１）である時の格子点NC（４）４
０５（５，２，１）が終点（５，２，１）に等し
い。このため、処理モジユール２１８で終点の格
子点から始点の格子点に向かつてトレースされ
る。すなわちグリツドマツプの格子点を表す四角
の下段のフラグMS５０２の小さくなる方向に経
路が（５，２，１）（５，３，１）（４，３，１）
（３，３，１）（３，３，２）（３，４，２）（３，
５，２）（３，５，１）（２，５，１）の各点をト
レースされる。
NC（ｉ）４０２〜４０７の位置情報が終点の格
子点と一致するかどうかが判定される。一致判定
に応答して、処理モジユール２１８で終点格子点
から始点格子点に向かつて経路がトレースされ
る。次に処理モジユール２１９において処理モジ
ユール２１８の処理により得られた配線経路デー
タがインタフエーステーブル２１４にセツトされ
る。第１２ａ図で示す６×６格子の上層のグリツ
ドマツプ及び第１２ｂ図で示す６×16格子の下層
のグリツドマツプにおいて、第４図の格子点CC
４０１が（２，５，１）である時の格子点NC
（１）４０２は（３，５，１）である。この格子
点は、終点（５，２，１）に等しくないので処理
モジユール２０８に制御が移される。一方、第１
５ａ図で示す６×６格子の上層のグリツドマツプ
及び第１５ｂ図で示す６×６格子の下層のグリツ
ドマツプにおいては、第４図の格子点CC４０１
が（５，２，１）である時の格子点NC（４）４
０５（５，２，１）が終点（５，２，１）に等し
い。このため、処理モジユール２１８で終点の格
子点から始点の格子点に向かつてトレースされ
る。すなわちグリツドマツプの格子点を表す四角
の下段のフラグMS５０２の小さくなる方向に経
路が（５，２，１）（５，３，１）（４，３，１）
（３，３，１）（３，３，２）（３，４，２）（３，
５，２）（３，５，１）（２，５，１）の各点をト
レースされる。
続いて処理モジユール２２０で経路を発見した
旨のフラグがセツトされ処理が終了する。
旨のフラグがセツトされ処理が終了する。
格子点NC（ｉ）４０２〜４０７が終点の格子
点でない場合は、処理モジユール２０８で格子点
NC（ｉ）４０２〜４０７の経路探索済フラグMS
５０２が“０”であるかどうかが判断される。処
理モジユール２０８におけるその格子の探索済判
定に応答して処理モジユール２１２に制御が移さ
れる。処理モジユール２０８における探索済でな
いという判定に応答して処理モジユール２０９に
制御が移される。第１２ａ図に示す６×６格子の
上層のグリツドマツプと第１２ｂ図に示す６×６
格子の下層のグリツドマツプにおいて第４図の格
子点CC４０１が（２，５，１）である時のｉ＝
１、すなわち格子点NC(1)４０２は（３，５，
１）である。しかし、この格子点を表す四角の下
段の経路探索済フラグMS５０２は“０”である
ので処理モジユール２０９に制御が移される。
点でない場合は、処理モジユール２０８で格子点
NC（ｉ）４０２〜４０７の経路探索済フラグMS
５０２が“０”であるかどうかが判断される。処
理モジユール２０８におけるその格子の探索済判
定に応答して処理モジユール２１２に制御が移さ
れる。処理モジユール２０８における探索済でな
いという判定に応答して処理モジユール２０９に
制御が移される。第１２ａ図に示す６×６格子の
上層のグリツドマツプと第１２ｂ図に示す６×６
格子の下層のグリツドマツプにおいて第４図の格
子点CC４０１が（２，５，１）である時のｉ＝
１、すなわち格子点NC(1)４０２は（３，５，
１）である。しかし、この格子点を表す四角の下
段の経路探索済フラグMS５０２は“０”である
ので処理モジユール２０９に制御が移される。
処理モジユール２０９で、第４図の格子点CC
４０１から格子点NC（ｉ）４０２〜４０７へ進
めるかどうか判定される。
４０１から格子点NC（ｉ）４０２〜４０７へ進
めるかどうか判定される。
次にこの判定処理の詳細な動作を第３図、第４
図及び第５図を参照して詳細に説明する。
図及び第５図を参照して詳細に説明する。
まず、この判定処理の前提を第４図及び第５図
を参照して説明する。
を参照して説明する。
第４図参照すると、現在考慮されている格子点
CC４０１とこの格子点CC４０１に隣接する隣接
格子点NC（ｉ）｛ｉ＝１〜６｝４０２〜４０７が
示されている。ｉは方向を指示しておりｉが１，
２，３，４，５及び６のときはそれぞれ右方向、
上方向、左方向、下方向、表方向及び裏方向を指
示している。
CC４０１とこの格子点CC４０１に隣接する隣接
格子点NC（ｉ）｛ｉ＝１〜６｝４０２〜４０７が
示されている。ｉは方向を指示しておりｉが１，
２，３，４，５及び６のときはそれぞれ右方向、
上方向、左方向、下方向、表方向及び裏方向を指
示している。
第５図を参照すると、メモリ上のグリツドマツ
プ１１７の各格子点の状態を表現する格子点デー
タのビツト構成の例が示されている。なお、ここ
ではひとつの格子点データに対して８ビツトが割
り当てられている。格子点データの２ビツトの占
有表示フイールドLA５０１は格子点の占有状態
を表示するのに用いられ、次の４つの状態が表現
される。
プ１１７の各格子点の状態を表現する格子点デー
タのビツト構成の例が示されている。なお、ここ
ではひとつの格子点データに対して８ビツトが割
り当てられている。格子点データの２ビツトの占
有表示フイールドLA５０１は格子点の占有状態
を表示するのに用いられ、次の４つの状態が表現
される。
00←空き
01←Ｘトラツク禁止（Ｘ方向配線は走行不可）
10←Ｙトラツク禁止（Ｙ方向配線は走行不可）
11←既占有（部品ピン、配線禁止、既配線経路
などにより占有されている。） ６ビツトのマーキングフイールドMS５０２は
配線経路探索時に自由に使用できる部分で、配線
方法によつて用途が異なる。
などにより占有されている。） ６ビツトのマーキングフイールドMS５０２は
配線経路探索時に自由に使用できる部分で、配線
方法によつて用途が異なる。
次に現在位置する格子点CC４０１から隣接格
子点NC（ｉ）｛ｉ＝１〜６｝４０２〜４０７へ進
めるかどうかの判定処理について第３図を参照し
て詳細に説明する。
子点NC（ｉ）｛ｉ＝１〜６｝４０２〜４０７へ進
めるかどうかの判定処理について第３図を参照し
て詳細に説明する。
格子点CC４０１から隣接格子点の１つである
NC(1)４０２（すなわちｉ＝１）へ進めるかどう
かの判定を行なう場合に限定してトレースする。
NC(1)４０２（すなわちｉ＝１）へ進めるかどう
かの判定を行なう場合に限定してトレースする。
まず処理モジユール３０１でグリツドマツプ１
１７中の格子点CC４０１対応の格子点が配線格
子の上層にあるか下層にあるかが調べられる。第
１２ａ図が示す６×６格子の上層のグリツドマツ
プ及び第１２ｂ図が示す６×６格子の下層のグリ
ツドマツプにおいて格子点CC４０１が（２，５，
１）の時、格子点CC４０１は上層にあることが
わかる。
１７中の格子点CC４０１対応の格子点が配線格
子の上層にあるか下層にあるかが調べられる。第
１２ａ図が示す６×６格子の上層のグリツドマツ
プ及び第１２ｂ図が示す６×６格子の下層のグリ
ツドマツプにおいて格子点CC４０１が（２，５，
１）の時、格子点CC４０１は上層にあることが
わかる。
次に処理モジユール３０２でｉが５がどうかが
判断され、ｉは５でないという結果を得て、処理
モジユール３０３に制御が移される。
判断され、ｉは５でないという結果を得て、処理
モジユール３０３に制御が移される。
処理モジユール３１３ではｉが６かどうかが判
断され、ｉは６でないという結果を得て処理モジ
ユール３０４に制御が移される。
断され、ｉは６でないという結果を得て処理モジ
ユール３０４に制御が移される。
処理モジユール３０４でグリツドマツプ１１７
中の格子点CC４０１対応の格子点データ中の占
有状態を記憶したフイールドLA５０１の内容が
照会される。第１２ａ図及び第１２ｂ図の状態の
とき、格子点CC４０１（２，５，１）に対応す
る四角の上段LA５０１の値は“11”である。
中の格子点CC４０１対応の格子点データ中の占
有状態を記憶したフイールドLA５０１の内容が
照会される。第１２ａ図及び第１２ｂ図の状態の
とき、格子点CC４０１（２，５，１）に対応す
る四角の上段LA５０１の値は“11”である。
続いてｉ＝１であるため制御は処理モジユール
３０５を経由して処理モジユール３０６へ移され
る。
３０５を経由して処理モジユール３０６へ移され
る。
処理モジユール３０６で格子点CC４０１の格
子点データを示すLA５０１にＸトラツク禁止を
示すコード“01”が格納されている場合には、処
理モジユール３１７へ制御が移され、格子点CC
４０１から隣接格子点NC(1)４０２への進行は不
可能という判定結果を得る。このような状況は、
直前の処理で隣接格子点NC(2)４０３またはNC
(4)４０５から格子点CC４０１へ進行し、格子点
CC４０１上で進行方向を変えた後に現処理で隣
接格子点NC(1)４０２へ進もうとする場合に起こ
る。
子点データを示すLA５０１にＸトラツク禁止を
示すコード“01”が格納されている場合には、処
理モジユール３１７へ制御が移され、格子点CC
４０１から隣接格子点NC(1)４０２への進行は不
可能という判定結果を得る。このような状況は、
直前の処理で隣接格子点NC(2)４０３またはNC
(4)４０５から格子点CC４０１へ進行し、格子点
CC４０１上で進行方向を変えた後に現処理で隣
接格子点NC(1)４０２へ進もうとする場合に起こ
る。
他方、格子点CC４０１の格子点データを示す
LA５０１の内容がＸトラツク禁止を示すコード
でない場合は処理モジユール３０７へ制御が移さ
れる。処理モジユール３０７では、グリツドマツ
プ１１７中の隣接格子点NC(1)４０２の占有状態
を記憶したフイールドLA５０１の内容が照会さ
れて、処理モジユール３０８に制御が移される。
第１２ａ図及び第１２ｂ図の場合、格子点CC４
０１のLA５０１の内容は“11”なので、処理モ
ジユール３０７に制御が移され、隣接格子点NC
(1)４０２（３，５，１）のLA５０１の内容が
“00”となる。
LA５０１の内容がＸトラツク禁止を示すコード
でない場合は処理モジユール３０７へ制御が移さ
れる。処理モジユール３０７では、グリツドマツ
プ１１７中の隣接格子点NC(1)４０２の占有状態
を記憶したフイールドLA５０１の内容が照会さ
れて、処理モジユール３０８に制御が移される。
第１２ａ図及び第１２ｂ図の場合、格子点CC４
０１のLA５０１の内容は“11”なので、処理モ
ジユール３０７に制御が移され、隣接格子点NC
(1)４０２（３，５，１）のLA５０１の内容が
“00”となる。
隣接格子点NC(1)４０２のLA５０１に既占有
を示すコード“11”が格納されている場合は、処
理モジユール３１７へ制御が移され、格子点CC
４０１から隣接格子点NC(1)４０２への進行は不
可能という判定結果を得る。
を示すコード“11”が格納されている場合は、処
理モジユール３１７へ制御が移され、格子点CC
４０１から隣接格子点NC(1)４０２への進行は不
可能という判定結果を得る。
他方、隣接格子点NC(1)４０２のLA５０１の
内容が既占有を示すコードでない場合は、処理モ
ジユール３０９を経由して処理モジユール３１０
へ制御が移される。第１２ａ図及び第１２ｂ図に
示す状態の場合、隣接格子点NC(1)４０２（３，
５，１）のLA５０１の内容は“00”であつて既
占有でないので処理モジユール３１０に制御が移
される。
内容が既占有を示すコードでない場合は、処理モ
ジユール３０９を経由して処理モジユール３１０
へ制御が移される。第１２ａ図及び第１２ｂ図に
示す状態の場合、隣接格子点NC(1)４０２（３，
５，１）のLA５０１の内容は“00”であつて既
占有でないので処理モジユール３１０に制御が移
される。
隣接格子点NC(1)４０２の格子点データ用フイ
ールドLA５０１にＸトラツク禁止を示すコード
“01”が格納されている場合は、処理モジユール
３１７へ制御が移され、格子点CC４０１から隣
接格子点NC(1)４０２への進行は不可能という判
定結果を得る。
ールドLA５０１にＸトラツク禁止を示すコード
“01”が格納されている場合は、処理モジユール
３１７へ制御が移され、格子点CC４０１から隣
接格子点NC(1)４０２への進行は不可能という判
定結果を得る。
他方、隣接格子点NC(1)４０２のフイールド
LA５０１の内容が、Ｘトラツク禁止を示すコー
ドでない場合は、処理モジユール３１１へ制御が
移され、格子点CC４０１から隣接格子点NC(1)４
０２への進行が可能という判定結果を得る。第１
２ａ図、第１２ｂ図の場合、隣接格子点NC(1)４
０２（３，５，１）のLA５０１の値は“00”で
Ｘトラツク禁止を示していない。したがつて格子
点CC４０１（２，５，１）から隣接格子点NC(1)
４０２（３，５，１）への進行は可能という判定
結果を得る。
LA５０１の内容が、Ｘトラツク禁止を示すコー
ドでない場合は、処理モジユール３１１へ制御が
移され、格子点CC４０１から隣接格子点NC(1)４
０２への進行が可能という判定結果を得る。第１
２ａ図、第１２ｂ図の場合、隣接格子点NC(1)４
０２（３，５，１）のLA５０１の値は“00”で
Ｘトラツク禁止を示していない。したがつて格子
点CC４０１（２，５，１）から隣接格子点NC(1)
４０２（３，５，１）への進行は可能という判定
結果を得る。
ここでは、隣接格子点の１つであるNC(1)４０
２へ進めるかどうかについてのみ流れ図のトレー
スを行つたが、他の隣接格子点NC(2)４０３，
NC(3)４０４，NC(4)４０５へ進めるかどうかの
判定も同様に行うことができる。
２へ進めるかどうかについてのみ流れ図のトレー
スを行つたが、他の隣接格子点NC(2)４０３，
NC(3)４０４，NC(4)４０５へ進めるかどうかの
判定も同様に行うことができる。
一方隣接格子点NC(5)及びNC(6)４０７につい
ての判定処理を以下詳細に説明する。
ての判定処理を以下詳細に説明する。
隣接格子点NC(5)４０６の時は、ｉ＝５ゆえ処
理モジユール３０２から処理モジユール３１３に
制御が移される。
理モジユール３０２から処理モジユール３１３に
制御が移される。
格子点CC４０１が上の層に存在する場合は、
処理モジユール３１７で格子点CC４０１から隣
接格子点NC(5)４０６への進行は不可能という判
定結果を得る。
処理モジユール３１７で格子点CC４０１から隣
接格子点NC(5)４０６への進行は不可能という判
定結果を得る。
格子点CC４０１が下の層に存在する場合は処
理モジユール３１４に制御が移り、隣接格子点
NC(5)４０６のLA５０１に既占有を示すコード
“11”が格納されていると判断される場合には、
処理モジユール３１７に制御が移る。この処理モ
ジユール３１７で格子点CC４０１から隣接格子
点NC(5)４０６への進行は不可能という判定結果
を得る。
理モジユール３１４に制御が移り、隣接格子点
NC(5)４０６のLA５０１に既占有を示すコード
“11”が格納されていると判断される場合には、
処理モジユール３１７に制御が移る。この処理モ
ジユール３１７で格子点CC４０１から隣接格子
点NC(5)４０６への進行は不可能という判定結果
を得る。
隣接格子点NC(5)４０６のLA５０１に既占有
を示すコード“11”が格納されていない場合には
処理モジユール３１１に制御が移され、格子点
CC４０１から隣接格子点NC(5)４０６への進行は
可能という判定結果を得る。
を示すコード“11”が格納されていない場合には
処理モジユール３１１に制御が移され、格子点
CC４０１から隣接格子点NC(5)４０６への進行は
可能という判定結果を得る。
隣接格子点NC(6)４０７へ進めるかどうかの判
定も同様に行うことができる。第１２ａ図及び第
１２ｂ図に示す状態において、格子点CC４０１
を（２，５，１）とした場合、隣接格子点NC(5)
４０６へ進めるかどうかは、ｉ＝５でまた格子点
CC４０１が上の層に存在するために格子点CC４
０１から隣接格子点NC(5)４０６への進行は不可
能となる。一方隣接格子点NC(6)４０７について
は、ｉ＝６で格子点CC４０１が上層であり、ま
た隣接格子点NC(6)４０７（２，５，２）のLA
５０１の値が“00”なので格子点CC４０１から
隣接格子点NC(6)４０７への進行は可能となる。
定も同様に行うことができる。第１２ａ図及び第
１２ｂ図に示す状態において、格子点CC４０１
を（２，５，１）とした場合、隣接格子点NC(5)
４０６へ進めるかどうかは、ｉ＝５でまた格子点
CC４０１が上の層に存在するために格子点CC４
０１から隣接格子点NC(5)４０６への進行は不可
能となる。一方隣接格子点NC(6)４０７について
は、ｉ＝６で格子点CC４０１が上層であり、ま
た隣接格子点NC(6)４０７（２，５，２）のLA
５０１の値が“00”なので格子点CC４０１から
隣接格子点NC(6)４０７への進行は可能となる。
したがつて、第１２ａ図に示す６×６格子の上
層のグリツドマツプと第１２ｂ図に示す６×６格
子の下層のグリツドマツプにおいて、格子点CC
４０１が（２，５，１）であり、ｉ＝１の時すな
わち、隣接格子点NC(1)４０２は（３，５，１）
である。この場合上述の説明から、格子点CC４
０１から隣接格子点NC(1)４０２へ進めると判断
される。
層のグリツドマツプと第１２ｂ図に示す６×６格
子の下層のグリツドマツプにおいて、格子点CC
４０１が（２，５，１）であり、ｉ＝１の時すな
わち、隣接格子点NC(1)４０２は（３，５，１）
である。この場合上述の説明から、格子点CC４
０１から隣接格子点NC(1)４０２へ進めると判断
される。
再び第２図を参照すると、隣接格子点NC（ｉ）
４０２〜４０７へ進める時は、処理モジユール２
１０で隣接格子点NC（ｉ）４０２〜４０７の格
子点データの経路探索済フラグMS５０２にステ
ツプカウンタSCの値がセツトされる。処理モジ
ユール２１１により隣接格子点NC（ｉ）４０２
〜４０７の格子点位置情報がワークテーブル
WTBL2に格納される。これは、第１２ａ図に示
す６×６格子の上層のグリツドマツプと第１２ｂ
図に示す６×６格子の下層のグリツドマツプにお
いて格子点CC４０１から隣接格子点NC(1)４０２
に進める。したがつて、隣接格子点NC(1)４０２
（３，５，１）の格子点を表す四角の下段の経路
探索フラグMS５０２に、この場合格子点CC４０
１が始点なのでSC＝１ゆえ“１”がセツトされ
る。セツトされた状態は第１３ａ図及び第１３ｂ
図に示される。さらに隣接格子点NC(1)４０２の
値（３，５，１）がワークテーブル２２２
WTBL2に格納される。この時のワークテーブル
２２２WTBL2の状態は第１７図に示される。隣
接格子点NC（ｉ）４０２〜４０７に進めない時
は処理モジユール２１２に制御が移される。
４０２〜４０７へ進める時は、処理モジユール２
１０で隣接格子点NC（ｉ）４０２〜４０７の格
子点データの経路探索済フラグMS５０２にステ
ツプカウンタSCの値がセツトされる。処理モジ
ユール２１１により隣接格子点NC（ｉ）４０２
〜４０７の格子点位置情報がワークテーブル
WTBL2に格納される。これは、第１２ａ図に示
す６×６格子の上層のグリツドマツプと第１２ｂ
図に示す６×６格子の下層のグリツドマツプにお
いて格子点CC４０１から隣接格子点NC(1)４０２
に進める。したがつて、隣接格子点NC(1)４０２
（３，５，１）の格子点を表す四角の下段の経路
探索フラグMS５０２に、この場合格子点CC４０
１が始点なのでSC＝１ゆえ“１”がセツトされ
る。セツトされた状態は第１３ａ図及び第１３ｂ
図に示される。さらに隣接格子点NC(1)４０２の
値（３，５，１）がワークテーブル２２２
WTBL2に格納される。この時のワークテーブル
２２２WTBL2の状態は第１７図に示される。隣
接格子点NC（ｉ）４０２〜４０７に進めない時
は処理モジユール２１２に制御が移される。
処理モジユール２１２では、ｉの値がカウント
アツプされる。次に処理モジユール２１３でｉの
値が６を越えたかどうかが判定される。６を越え
たと判定された時は、処理モジユール２０４へ制
御が移され、６以下なら処理モジユール２０７に
制御が移される。
アツプされる。次に処理モジユール２１３でｉの
値が６を越えたかどうかが判定される。６を越え
たと判定された時は、処理モジユール２０４へ制
御が移され、６以下なら処理モジユール２０７に
制御が移される。
第１４ａ図が示す６×６格子の上層のグリツド
マツプ及び第１４ｂ図が示す６×６格子の下層の
グリツドマツプは、格子点CC４０１（３，５，
１）に関しワークテーブル２２２WTBL1及び
WTBL2の値が第１８図に示す値の時の各格子点
のフラグMS５０２の状態を示している。
マツプ及び第１４ｂ図が示す６×６格子の下層の
グリツドマツプは、格子点CC４０１（３，５，
１）に関しワークテーブル２２２WTBL1及び
WTBL2の値が第１８図に示す値の時の各格子点
のフラグMS５０２の状態を示している。
処理フロー中で使用されたステツプカウンタ
は、グリツドマツプ１１７にセツトされて、経路
トレース時に使用するが、メモリ節約のため１，
１，２，２，１，１，……としてもその正当性が
失われないことが立証されている。
は、グリツドマツプ１１７にセツトされて、経路
トレース時に使用するが、メモリ節約のため１，
１，２，２，１，１，……としてもその正当性が
失われないことが立証されている。
再び第１図を参照すると、処理モジユール１０
６では上述したようにインタフエーステーブル１
１６からの配線区間データに対してグリツドマツ
プ１１７が参照されて障害物を避けながら配線経
路が探索され、配線経路発見に応答して当該配線
経路に対する複数の格子点位置からなる経路デー
タがインタフエーステーブル１１６に格納され
る。
６では上述したようにインタフエーステーブル１
１６からの配線区間データに対してグリツドマツ
プ１１７が参照されて障害物を避けながら配線経
路が探索され、配線経路発見に応答して当該配線
経路に対する複数の格子点位置からなる経路デー
タがインタフエーステーブル１１６に格納され
る。
処理モジユール１０７では処理モジユール１０
６で配線経路が発見されたか否かが判断される。
発見の判断に応答して、処理モジユール１０８に
制御が移される。発見できないという判断に応答
して、制御は処理モジユール１０４に戻される。
６で配線経路が発見されたか否かが判断される。
発見の判断に応答して、処理モジユール１０８に
制御が移される。発見できないという判断に応答
して、制御は処理モジユール１０４に戻される。
処理モジユール１０８では、インタフエーステ
ーブル１１６の配線経路データの内で未処理の線
分データが存在するか否かが判断される。未処理
の線分データが存在しなくなつたとの判断に応答
して処理モジユール１０４に制御は戻される。未
処理の線分データが存在するとの判断に応答して
処理モジユール１０９に制御が移される。処理モ
ジユール１０９では、インタフエーステーブル１
１６から未処理の線分データが取り出され、処理
モジユール１１０に制御が移される。
ーブル１１６の配線経路データの内で未処理の線
分データが存在するか否かが判断される。未処理
の線分データが存在しなくなつたとの判断に応答
して処理モジユール１０４に制御は戻される。未
処理の線分データが存在するとの判断に応答して
処理モジユール１０９に制御が移される。処理モ
ジユール１０９では、インタフエーステーブル１
１６から未処理の線分データが取り出され、処理
モジユール１１０に制御が移される。
処理モジユール１１０では、線分データは配線
経路探索における障害物としてグリツドマツプ１
１７にセツトされ、処理モジユール１１１に制御
が移される。この処理モジユール１１０の処理に
より第１６ａ図に示す16×16格子の上層のグリツ
ドマツプ及び第１６ｂ図に示す16×16格子の下層
のグリツドマツプの各格子点の示す四角の上段の
LA５０１の（２，５，１）（３，５，１）（３，
３，１）（４，３，１）（５，３，１）（５，２，
１）（３，５，２）（３，４，２）及び（３，３，
２）で示す位置に“11”がセツトされる。同じく
第８図では配線禁止８０６がセツトされる。
経路探索における障害物としてグリツドマツプ１
１７にセツトされ、処理モジユール１１１に制御
が移される。この処理モジユール１１０の処理に
より第１６ａ図に示す16×16格子の上層のグリツ
ドマツプ及び第１６ｂ図に示す16×16格子の下層
のグリツドマツプの各格子点の示す四角の上段の
LA５０１の（２，５，１）（３，５，１）（３，
３，１）（４，３，１）（５，３，１）（５，２，
１）（３，５，２）（３，４，２）及び（３，３，
２）で示す位置に“11”がセツトされる。同じく
第８図では配線禁止８０６がセツトされる。
処理モジユール１１１では、線分データが配線
結果としてPAT2118に出力され処理モジユール
１１２に制御が移される。
結果としてPAT2118に出力され処理モジユール
１１２に制御が移される。
この処理モジユール１１２における処理を第６
図を参照しながら、詳細に説明する。
図を参照しながら、詳細に説明する。
第６図を参照すると、最初に処理モジユール６
０１において、入力された線分を構成する格子点
が配線格子の上層に属するのか、下層に属するの
かが調べられる。上層に属すると判定された層フ
ラグｚに１がセツトされる。下層に属すると判定
された層フラグｚに２がセツトされる。第１１ａ
図及び第１１ｂ図に示す（２，４，１）（３，４，
１）（４，４，１）及び（５，４，１）が入力線
分の場合には、この線分は上層に属するので層フ
ラグｚは１がセツトされる。
０１において、入力された線分を構成する格子点
が配線格子の上層に属するのか、下層に属するの
かが調べられる。上層に属すると判定された層フ
ラグｚに１がセツトされる。下層に属すると判定
された層フラグｚに２がセツトされる。第１１ａ
図及び第１１ｂ図に示す（２，４，１）（３，４，
１）（４，４，１）及び（５，４，１）が入力線
分の場合には、この線分は上層に属するので層フ
ラグｚは１がセツトされる。
次に処理モジユール６０２において、入力線分
の方向が調べられる。処理モジユール６０２は、
入力線分の方向がＸ方向なら、入力線分の方向を
表す方向フラグＤに１をセツトする。処理モジユ
ール６０２は、入力線分の方向がＹ方向なら、入
力線分の方向を表す方向フラグＤに０をセツトす
る。第１１Ｃ図、第１１ｂ図に示す（２，４，
１）（３，４，１）（４，４，１）（５，４，１）
が入力線分の場合には、この線分の方向はＸ方向
なので方向フラグＤには１がセツトされる。
の方向が調べられる。処理モジユール６０２は、
入力線分の方向がＸ方向なら、入力線分の方向を
表す方向フラグＤに１をセツトする。処理モジユ
ール６０２は、入力線分の方向がＹ方向なら、入
力線分の方向を表す方向フラグＤに０をセツトす
る。第１１Ｃ図、第１１ｂ図に示す（２，４，
１）（３，４，１）（４，４，１）（５，４，１）
が入力線分の場合には、この線分の方向はＸ方向
なので方向フラグＤには１がセツトされる。
次に処理モジユール６０３において、入力され
た線分の全ての格子点について、処理モジユール
６０８，６０９，６１０および６１１のいずれの
処理も未だ行われていない入力線分上の格子点の
存在が判断される。未処理の格子点の存在しない
との判断に応答して処理は終了される。未処理の
格子点の存在の判断に応答して処理モジユール６
０４に制御が移される。
た線分の全ての格子点について、処理モジユール
６０８，６０９，６１０および６１１のいずれの
処理も未だ行われていない入力線分上の格子点の
存在が判断される。未処理の格子点の存在しない
との判断に応答して処理は終了される。未処理の
格子点の存在の判断に応答して処理モジユール６
０４に制御が移される。
処理モジユール６０４において入力線分上の未
処理の格子点が１つ取り出され、それを格子点
CC４０１とする。第１１ａ図、第１１ｂ図に示
す（２，４，１）（３，４，１）（４，４，１）及
び（５，４，１）の位置を入力線分とした場合に
（２，４，１）が格子点CC４０１となる。
処理の格子点が１つ取り出され、それを格子点
CC４０１とする。第１１ａ図、第１１ｂ図に示
す（２，４，１）（３，４，１）（４，４，１）及
び（５，４，１）の位置を入力線分とした場合に
（２，４，１）が格子点CC４０１となる。
次に処理モジユール６０５において層フラグｚ
が１かどうかが判断される。層フラグｚの“１”
に応答して、処理モジユール６０６に制御が移さ
れる。層フラグの“０”に応答して処理モジユー
ル６０７に制御が移される。第１１ａ図及び第１
１ｂ図に示す状態の場合、ｚには処理モジユール
６０１で“１”がセツトされているので処理モジ
ユール６０６に制御が移される。
が１かどうかが判断される。層フラグｚの“１”
に応答して、処理モジユール６０６に制御が移さ
れる。層フラグの“０”に応答して処理モジユー
ル６０７に制御が移される。第１１ａ図及び第１
１ｂ図に示す状態の場合、ｚには処理モジユール
６０１で“１”がセツトされているので処理モジ
ユール６０６に制御が移される。
処理モジユール６０６において、方向フラグＤ
が“１”かどうかが判断される。方向フラグＤの
“１”に応答して処理モジユール６０８で隣接格
子点NC(6)４０７のLA５０１にＸトラツク禁止
のコード“01”がセツトされる。方向フラグＤの
“０”に応答して処理モジユール６０９で隣接格
子点NC(6)４０７のLA５０１にＹトラツク禁止
のコード“10”がセツトされる。第１１ａ図及び
第１１ｂ図の状態の場合、方向フラグＤは処理モ
ジユール６０２で“１”がセツトされているの
で、隣接格子点NC(6)４０７（２，４，２）に値
“01”がセツトされる。
が“１”かどうかが判断される。方向フラグＤの
“１”に応答して処理モジユール６０８で隣接格
子点NC(6)４０７のLA５０１にＸトラツク禁止
のコード“01”がセツトされる。方向フラグＤの
“０”に応答して処理モジユール６０９で隣接格
子点NC(6)４０７のLA５０１にＹトラツク禁止
のコード“10”がセツトされる。第１１ａ図及び
第１１ｂ図の状態の場合、方向フラグＤは処理モ
ジユール６０２で“１”がセツトされているの
で、隣接格子点NC(6)４０７（２，４，２）に値
“01”がセツトされる。
次に処理モジユール６０７において、方向フラ
グＤが“１”かどうかが判断される。方向フラグ
Ｄの“１”に応答して、処理モジユール６１０
で、隣接格子点NC(5)４０６のLA５０１にＸト
ラツク禁止のコード“01”がセツトされる。方向
フラグＤの“０”に応答して処理モジユール６１
１で隣接格子点NC(5)４０６のLA５０１にＹト
ラツク禁止のコード“10”がセツトされる。処理
モジユール６０８，６０９，６１０及び６１１は
いずれも処理終了後に処理モジユール６０３に制
御が移される。
グＤが“１”かどうかが判断される。方向フラグ
Ｄの“１”に応答して、処理モジユール６１０
で、隣接格子点NC(5)４０６のLA５０１にＸト
ラツク禁止のコード“01”がセツトされる。方向
フラグＤの“０”に応答して処理モジユール６１
１で隣接格子点NC(5)４０６のLA５０１にＹト
ラツク禁止のコード“10”がセツトされる。処理
モジユール６０８，６０９，６１０及び６１１は
いずれも処理終了後に処理モジユール６０３に制
御が移される。
再び第１図を参照すると、処理モジユール１１
２では、上述のように線分データ存在層と反対側
の層に線分データと同一方向の配線禁止用トラツ
ク禁止データがグリツドマツプ１１７にセツトさ
れ、処理モジユール１０８に制御が移る。この処
理モジユール１１２により、第１６ａ図に示す16
×16格子の上層のグリツドマツプ及び第１６ｂ図
に示す16×16格子の下層のグリツドマツプの各格
子点の表す四角の上段のLA５０１に（２，５，
２）（５，３，２）では“01”を（５，２，２）
では“10”がセツトされ、また第８図ではＸトラ
ツク禁止８０７とＹトラツク禁止８０８がセツト
される。
２では、上述のように線分データ存在層と反対側
の層に線分データと同一方向の配線禁止用トラツ
ク禁止データがグリツドマツプ１１７にセツトさ
れ、処理モジユール１０８に制御が移る。この処
理モジユール１１２により、第１６ａ図に示す16
×16格子の上層のグリツドマツプ及び第１６ｂ図
に示す16×16格子の下層のグリツドマツプの各格
子点の表す四角の上段のLA５０１に（２，５，
２）（５，３，２）では“01”を（５，２，２）
では“10”がセツトされ、また第８図ではＸトラ
ツク禁止８０７とＹトラツク禁止８０８がセツト
される。
このようにして配線設計された配線基板は、プ
リント配線板、セラミツク配線板、集積回路に対
する一般の製造技術を用いて製造される。この製
造技術は1980年C.Mead及びL.Conwayにより
Addison−Wesley社から発行された刊行物
「Introdaction to VLSI Systems」のpp38−45
を参照できる。
リント配線板、セラミツク配線板、集積回路に対
する一般の製造技術を用いて製造される。この製
造技術は1980年C.Mead及びL.Conwayにより
Addison−Wesley社から発行された刊行物
「Introdaction to VLSI Systems」のpp38−45
を参照できる。
以上説明したように本発明では、配線区間の配
線経路が決定される毎に、当該配線経路を構成す
る各線分に対して、配線の対象となる２つの層の
内の当該線分の存在する層と反対側の層における
当該線分と同じ平面座標を持つ線分の位置に、当
該線分と平行した方向の線分のみを禁止する障害
物を発生し、後続する他の配線区間の配線経路を
前記特定方向の線分のみを禁止する障害物を認識
しながら探索することにより、既発生の配線経路
の各線分の真上もしくは真下のその線分の存在す
る層と反対側の層に配線経路が平行して発生する
ことを抑制しクロストークの発生を低減するとい
う効果がある。
線経路が決定される毎に、当該配線経路を構成す
る各線分に対して、配線の対象となる２つの層の
内の当該線分の存在する層と反対側の層における
当該線分と同じ平面座標を持つ線分の位置に、当
該線分と平行した方向の線分のみを禁止する障害
物を発生し、後続する他の配線区間の配線経路を
前記特定方向の線分のみを禁止する障害物を認識
しながら探索することにより、既発生の配線経路
の各線分の真上もしくは真下のその線分の存在す
る層と反対側の層に配線経路が平行して発生する
ことを抑制しクロストークの発生を低減するとい
う効果がある。
第１図は本発明の一実施例を示す図、第２図は
第１図の処理モジユール１０６での処理を示す
図、第３図は第２図の処理モジユール２０９での
処理を示す図、第４図は格子点とこの格子点に隣
接する格子点とを示す図、第５図は格子点データ
の形式を示す図、第６図は処理モジユール１１２
での処理を示す図、第７図及び第８図は禁止デー
タのセツト状態及び配線経路の探索結果を説明す
るための模式配線モデル図、第９ａ図から第１６
ab図はグリツドマツプの状態を示す図、第１７
図は第１３ａ図及び第１３ｂ図に示すグリツドマ
ツプの状態に対応するワークテーブル２２２
WTBL1及びWTBL2の状態を示す図、及び第１
８図は第１４ａ図及び第１４ｂ図に示すグリツド
マツプの状態に対応するワークテーブル２２２
WTBL1及びWTBL2の状態を示す図である。 図面において、１１６……インタフエーステー
ブル、１１７……グリツドマツプ、２２２……ワ
ークテーブル。
第１図の処理モジユール１０６での処理を示す
図、第３図は第２図の処理モジユール２０９での
処理を示す図、第４図は格子点とこの格子点に隣
接する格子点とを示す図、第５図は格子点データ
の形式を示す図、第６図は処理モジユール１１２
での処理を示す図、第７図及び第８図は禁止デー
タのセツト状態及び配線経路の探索結果を説明す
るための模式配線モデル図、第９ａ図から第１６
ab図はグリツドマツプの状態を示す図、第１７
図は第１３ａ図及び第１３ｂ図に示すグリツドマ
ツプの状態に対応するワークテーブル２２２
WTBL1及びWTBL2の状態を示す図、及び第１
８図は第１４ａ図及び第１４ｂ図に示すグリツド
マツプの状態に対応するワークテーブル２２２
WTBL1及びWTBL2の状態を示す図である。 図面において、１１６……インタフエーステー
ブル、１１７……グリツドマツプ、２２２……ワ
ークテーブル。
Claims (1)
- 【特許請求の範囲】 １ 上下方向に積層された多層平面上の配線経路
を決定する配線経路決定方式において、 配線を禁止する配線禁止データと、特定方向の
配線を禁止するトラツク禁止データとからなる障
害物を、前記多層平面の各格子点ごとに保持する
グリツドマツプと、 前記障害物を避けて配線経路を探索し、決定す
る決定手段と、 前記決定手段により決定された配線経路の各線
分について、該線分の直上の隣接格子点および直
下の隣接格子点の少なくとも一方において該線分
データと同一方向の配線が禁止されるように、前
記グリツドマツプに前記トラツク禁止データを設
定する発生手段とを有することを特徴とする配線
経路決定方式。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61-241641 | 1986-10-09 | ||
| JP24164186 | 1986-10-09 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63225869A JPS63225869A (ja) | 1988-09-20 |
| JPH0550780B2 true JPH0550780B2 (ja) | 1993-07-29 |
Family
ID=17077333
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62239517A Granted JPS63225869A (ja) | 1986-10-09 | 1987-09-22 | 配線経路探索方式 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US4855929A (ja) |
| JP (1) | JPS63225869A (ja) |
Families Citing this family (79)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5119317A (en) * | 1988-03-16 | 1992-06-02 | Kabushiki Kaisha Toshiba | Routing method and system |
| JPH0786883B2 (ja) * | 1988-09-09 | 1995-09-20 | 松下電器産業株式会社 | 網図または諭理回路図自動生成方法およびそのシステム |
| JP2680867B2 (ja) * | 1988-12-05 | 1997-11-19 | 株式会社日立製作所 | 径路レイアウト方法 |
| US5224057A (en) * | 1989-02-28 | 1993-06-29 | Kabushiki Kaisha Toshiba | Arrangement method for logic cells in semiconductor IC device |
| JPH03138961A (ja) * | 1989-10-24 | 1991-06-13 | Fujitsu Ltd | 配線パターン決定方式 |
| JP2522420B2 (ja) * | 1989-11-28 | 1996-08-07 | 日本電気株式会社 | 自動配線設計装置 |
| JPH03188650A (ja) * | 1989-12-18 | 1991-08-16 | Hitachi Ltd | 配線経路処理方法、配線経路処理システム、及び半導体集積回路 |
| US5258920A (en) * | 1989-12-26 | 1993-11-02 | General Electric Company | Locally orientation specific routing system |
| US5220512A (en) * | 1990-04-19 | 1993-06-15 | Lsi Logic Corporation | System for simultaneous, interactive presentation of electronic circuit diagrams and simulation data |
| JPH04130968A (ja) * | 1990-09-21 | 1992-05-01 | Toshiba Corp | ニューラルネットワークを用いた配線方式 |
| US5341310A (en) * | 1991-12-17 | 1994-08-23 | International Business Machines Corporation | Wiring layout design method and system for integrated circuits |
| JP3219500B2 (ja) * | 1991-12-27 | 2001-10-15 | 株式会社東芝 | 自動配線方法 |
| FR2690598B1 (fr) * | 1992-04-24 | 1994-06-03 | Sextant Avionique | Ordonnancement de troncons de lignes d'un reseau, notamment pour le calcul de diaphonies entre lignes d'un reseau electrique. |
| US5544088A (en) * | 1993-06-23 | 1996-08-06 | International Business Machines Corporation | Method of I/O pin assignment in a hierarchial packaging system |
| US5491641A (en) * | 1993-10-04 | 1996-02-13 | Lsi Logic Corporation | Towards optical steiner tree routing in the presence of rectilinear obstacles |
| JP3335250B2 (ja) * | 1994-05-27 | 2002-10-15 | 株式会社東芝 | 半導体集積回路の配線方法 |
| JP2833505B2 (ja) * | 1995-01-30 | 1998-12-09 | 日本電気株式会社 | 半導体集積回路の自動配線方法 |
| US5825659A (en) * | 1995-06-16 | 1998-10-20 | Lsi Logic Corporation | Method for local rip-up and reroute of signal paths in an IC design |
| US5677847A (en) * | 1995-12-05 | 1997-10-14 | International Business Machines Corporation | Method and apparatus for designing a module |
| US5777383A (en) * | 1996-05-09 | 1998-07-07 | Lsi Logic Corporation | Semiconductor chip package with interconnect layers and routing and testing methods |
| US6507941B1 (en) * | 1999-04-28 | 2003-01-14 | Magma Design Automation, Inc. | Subgrid detailed routing |
| US6898773B1 (en) | 2002-01-22 | 2005-05-24 | Cadence Design Systems, Inc. | Method and apparatus for producing multi-layer topological routes |
| US6889372B1 (en) | 2000-07-15 | 2005-05-03 | Cadence Design Systems Inc. | Method and apparatus for routing |
| US6957410B2 (en) * | 2000-12-07 | 2005-10-18 | Cadence Design Systems, Inc. | Method and apparatus for adaptively selecting the wiring model for a design region |
| AU2002233977A1 (en) * | 2000-12-06 | 2002-06-18 | Simplex Solutions, Inc. | Method and apparatus for considering diagonal wiring in placement |
| US6826737B2 (en) * | 2000-12-06 | 2004-11-30 | Cadence Design Systems, Inc. | Recursive partitioning placement method and apparatus |
| US7080336B2 (en) * | 2000-12-06 | 2006-07-18 | Cadence Design Systems, Inc. | Method and apparatus for computing placement costs |
| US7055120B2 (en) * | 2000-12-06 | 2006-05-30 | Cadence Design Systems, Inc. | Method and apparatus for placing circuit modules |
| US7024650B2 (en) * | 2000-12-06 | 2006-04-04 | Cadence Design Systems, Inc. | Method and apparatus for considering diagonal wiring in placement |
| US7003754B2 (en) | 2000-12-07 | 2006-02-21 | Cadence Design Systems, Inc. | Routing method and apparatus that use of diagonal routes |
| US6516455B1 (en) * | 2000-12-06 | 2003-02-04 | Cadence Design Systems, Inc. | Partitioning placement method using diagonal cutlines |
| US7441220B2 (en) * | 2000-12-07 | 2008-10-21 | Cadence Design Systems, Inc. | Local preferred direction architecture, tools, and apparatus |
| US7594196B2 (en) * | 2000-12-07 | 2009-09-22 | Cadence Design Systems, Inc. | Block interstitching using local preferred direction architectures, tools, and apparatus |
| US7073150B2 (en) * | 2000-12-07 | 2006-07-04 | Cadence Design Systems, Inc. | Hierarchical routing method and apparatus that use diagonal routes |
| US6915501B2 (en) | 2001-01-19 | 2005-07-05 | Cadence Design Systems, Inc. | LP method and apparatus for identifying routes |
| US6738960B2 (en) | 2001-01-19 | 2004-05-18 | Cadence Design Systems, Inc. | Method and apparatus for producing sub-optimal routes for a net by generating fake configurations |
| JP4451575B2 (ja) * | 2001-05-22 | 2010-04-14 | パナソニック株式会社 | 配線基板の設計支援装置、設計支援方法、プログラム記録媒体、及びプログラム |
| US6829757B1 (en) | 2001-06-03 | 2004-12-07 | Cadence Design Systems, Inc. | Method and apparatus for generating multi-layer routes |
| US6951005B1 (en) | 2001-06-03 | 2005-09-27 | Cadence Design Systems, Inc. | Method and apparatus for selecting a route for a net based on the impact on other nets |
| US7107564B1 (en) | 2001-06-03 | 2006-09-12 | Cadence Design Systems, Inc. | Method and apparatus for routing a set of nets |
| US6957411B1 (en) | 2001-06-03 | 2005-10-18 | Cadence Design Systems, Inc. | Gridless IC layout and method and apparatus for generating such a layout |
| US7069530B1 (en) | 2001-06-03 | 2006-06-27 | Cadence Design Systems, Inc. | Method and apparatus for routing groups of paths |
| US6877146B1 (en) | 2001-06-03 | 2005-04-05 | Cadence Design Systems, Inc. | Method and apparatus for routing a set of nets |
| US6957408B1 (en) | 2002-01-22 | 2005-10-18 | Cadence Design Systems, Inc. | Method and apparatus for routing nets in an integrated circuit layout |
| US6795958B2 (en) * | 2001-08-23 | 2004-09-21 | Cadence Design Systems, Inc. | Method and apparatus for generating routes for groups of related node configurations |
| US6931616B2 (en) * | 2001-08-23 | 2005-08-16 | Cadence Design Systems, Inc. | Routing method and apparatus |
| US7398498B2 (en) | 2001-08-23 | 2008-07-08 | Cadence Design Systems, Inc. | Method and apparatus for storing routes for groups of related net configurations |
| US7143382B2 (en) | 2001-08-23 | 2006-11-28 | Cadence Design Systems, Inc. | Method and apparatus for storing routes |
| US7155697B2 (en) * | 2001-08-23 | 2006-12-26 | Cadence Design Systems, Inc. | Routing method and apparatus |
| US7058913B1 (en) * | 2001-09-06 | 2006-06-06 | Cadence Design Systems, Inc. | Analytical placement method and apparatus |
| US6694502B2 (en) | 2001-11-02 | 2004-02-17 | Sun Microsystems, Inc. | Data structure for fine-grid multi-level VLSI routing and method for storing the data structure in a computer readable medium |
| US7096449B1 (en) | 2002-01-22 | 2006-08-22 | Cadence Design Systems, Inc. | Layouts with routes with different widths in different directions on the same layer, and method and apparatus for generating such layouts |
| US7089524B1 (en) | 2002-01-22 | 2006-08-08 | Cadence Design Systems, Inc. | Topological vias route wherein the topological via does not have a coordinate within the region |
| US7117468B1 (en) | 2002-01-22 | 2006-10-03 | Cadence Design Systems, Inc. | Layouts with routes with different spacings in different directions on the same layer, and method and apparatus for generating such layouts |
| US6938234B1 (en) | 2002-01-22 | 2005-08-30 | Cadence Design Systems, Inc. | Method and apparatus for defining vias |
| US7080329B1 (en) | 2002-01-22 | 2006-07-18 | Cadence Design Systems, Inc. | Method and apparatus for identifying optimized via locations |
| US6944841B1 (en) | 2002-01-22 | 2005-09-13 | Cadence Design Systems, Inc. | Method and apparatus for proportionate costing of vias |
| US7013451B1 (en) | 2002-01-22 | 2006-03-14 | Cadence Design Systems, Inc. | Method and apparatus for performing routability checking |
| US7036105B1 (en) | 2002-01-22 | 2006-04-25 | Cadence Design Systems, Inc. | Integrated circuits with at least one layer that has more than one preferred interconnect direction, and method for manufacturing such IC's |
| US6892371B1 (en) | 2002-01-22 | 2005-05-10 | Cadence Design Systems, Inc. | Method and apparatus for performing geometric routing |
| US6988257B2 (en) * | 2002-11-18 | 2006-01-17 | Cadence Design Systems, Inc. | Method and apparatus for routing |
| US7010771B2 (en) * | 2002-11-18 | 2006-03-07 | Cadence Design Systems, Inc. | Method and apparatus for searching for a global path |
| US7080342B2 (en) * | 2002-11-18 | 2006-07-18 | Cadence Design Systems, Inc | Method and apparatus for computing capacity of a region for non-Manhattan routing |
| US7216308B2 (en) * | 2002-11-18 | 2007-05-08 | Cadence Design Systems, Inc. | Method and apparatus for solving an optimization problem in an integrated circuit layout |
| US7003752B2 (en) * | 2002-11-18 | 2006-02-21 | Cadence Design Systems, Inc. | Method and apparatus for routing |
| US7047513B2 (en) * | 2002-11-18 | 2006-05-16 | Cadence Design Systems, Inc. | Method and apparatus for searching for a three-dimensional global path |
| US6892369B2 (en) * | 2002-11-18 | 2005-05-10 | Cadence Design Systems, Inc. | Method and apparatus for costing routes of nets |
| US7480885B2 (en) * | 2002-11-18 | 2009-01-20 | Cadence Design Systems, Inc. | Method and apparatus for routing with independent goals on different layers |
| US6996789B2 (en) * | 2002-11-18 | 2006-02-07 | Cadence Design Systems, Inc. | Method and apparatus for performing an exponential path search |
| US7093221B2 (en) * | 2002-11-18 | 2006-08-15 | Cadence Design Systems, Inc. | Method and apparatus for identifying a group of routes for a set of nets |
| US7171635B2 (en) * | 2002-11-18 | 2007-01-30 | Cadence Design Systems, Inc. | Method and apparatus for routing |
| US7624367B2 (en) | 2002-11-18 | 2009-11-24 | Cadence Design Systems, Inc. | Method and system for routing |
| US7013445B1 (en) | 2002-12-31 | 2006-03-14 | Cadence Design Systems, Inc. | Post processor for optimizing manhattan integrated circuits placements into non manhattan placements |
| US7506295B1 (en) | 2002-12-31 | 2009-03-17 | Cadence Design Systems, Inc. | Non manhattan floor plan architecture for integrated circuits |
| US7089519B1 (en) | 2002-12-31 | 2006-08-08 | Cadence Design System, Inc. | Method and system for performing placement on non Manhattan semiconductor integrated circuits |
| US7707537B2 (en) * | 2004-06-04 | 2010-04-27 | Cadence Design Systems, Inc. | Method and apparatus for generating layout regions with local preferred directions |
| US7412682B2 (en) * | 2004-06-04 | 2008-08-12 | Cadence Design Systems, Inc | Local preferred direction routing |
| US7340711B2 (en) * | 2004-06-04 | 2008-03-04 | Cadence Design Systems, Inc. | Method and apparatus for local preferred direction routing |
| US8250514B1 (en) | 2006-07-13 | 2012-08-21 | Cadence Design Systems, Inc. | Localized routing direction |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4593351A (en) * | 1981-06-12 | 1986-06-03 | International Business Machines Corporation | High speed machine for the physical design of very large scale integrated circuits |
| JPS59106070A (ja) * | 1982-12-10 | 1984-06-19 | Mitsubishi Electric Corp | 配線クロスト−ク処理装置 |
| JPS608982A (ja) * | 1983-06-29 | 1985-01-17 | Yokogawa Hokushin Electric Corp | 経路の自動探索方法 |
| US4615011A (en) * | 1983-12-19 | 1986-09-30 | Ibm | Iterative method for establishing connections and resulting product |
| US4636965A (en) * | 1984-05-10 | 1987-01-13 | Rca Corporation | Routing method in computer-aided-customization of universal arrays and resulting integrated circuit |
| JPS61199166A (ja) * | 1985-03-01 | 1986-09-03 | Nec Corp | 配線経路探索装置 |
| US4613941A (en) * | 1985-07-02 | 1986-09-23 | The United States Of America As Represented By The Secretary Of The Army | Routing method in computer aided customization of a two level automated universal array |
-
1987
- 1987-09-22 JP JP62239517A patent/JPS63225869A/ja active Granted
- 1987-10-07 US US07/105,247 patent/US4855929A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US4855929A (en) | 1989-08-08 |
| JPS63225869A (ja) | 1988-09-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0550780B2 (ja) | ||
| EP0950966B1 (en) | Automatic routing method for a logic circuit | |
| JP2001274254A (ja) | 半導体集積回路の自動配置配線方法 | |
| JP2000057175A (ja) | 半導体集積回路装置の自動配線方式 | |
| JP2713969B2 (ja) | 自動配線パターン設定方式 | |
| JPH01293472A (ja) | Ｃａｄによる回路基板の配線経路探索方法 | |
| EP0213670A2 (en) | Computer aided design system | |
| JP2566788B2 (ja) | プリント板の配線方式 | |
| JP2523703B2 (ja) | 半導体集積回路の自動配線方法 | |
| JP2607694B2 (ja) | Ｃａｄシステム | |
| JP2536119B2 (ja) | 配線処理方式 | |
| JPH0754532B2 (ja) | 多層同時配線方法 | |
| JPH0476154B2 (ja) | ||
| JP2825928B2 (ja) | チャネルマージ配線法 | |
| JPH08221458A (ja) | 束配線設計装置 | |
| JP3178905B2 (ja) | 自動配線方式 | |
| JPS63239963A (ja) | 配線径路決定方法 | |
| JPS6140674A (ja) | 経路探索処理システム | |
| JP3006156B2 (ja) | 自動配線方式 | |
| JPS63314846A (ja) | 一層配線方式 | |
| JPS63133274A (ja) | 配線処理方式 | |
| JPH05143691A (ja) | 自動配線方式 | |
| JPH077424B2 (ja) | 自動配線方法 | |
| JPH01305474A (ja) | 未配線区間配線支援方法 | |
| JPS62285184A (ja) | Ｌｓｉ設計方法 |