JPS6286463A - 多層自動配線処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 コンピュータを利用したプリント基板、集積回路等に関
する自動配線処理方式において、チャネル内でフローテ
ィング状態のまま配線処理を行う際に、各々主配線方向
が異なる全層の容量を合計し、この合計された容量をも
つ仮想的な１組の層ペアについて、径路探索を行うこと
により、形式的な容量不足による探索失敗を解消し、配
線層が３層以上存在する場合における効果的な配線を可
能にしている。

〔産業上の利用分野〕

本発明は、コンピュータを利用したプリント基板、集積
回路等のレイアウト設計における自動配線システムに係
り、特にチャネル内で配線済径路をフローティングで扱
う従来の２要用自動配線プログラムに、若干の修正を加
えるだけで、効果的な多層配線を可能とした多層自動配
線処理方式に関するものである。

〔従来の技術〕

第４図は従来の２層配線方式の説明図、第５図は従来方
式の説明図を示す。

従来の自動配線システムは、いわゆる２層配線処理が中
心であり、近年の集積回路の大規模化。

高集積化や、プリント基板における実装密度の向上によ
る多層データの処理のために２例えば第４図に示すよう
に、第１層と第４層、第２層と第３層等というような適
当な２層の組からなる層ペアを選択して、２層毎に配線
する方式がとられている。この層ペアは、Ｘ方向とＹ方
向というように主配線方向が異なるものが組合わされる
ようになっており、１つの層ペアにおいて、縦・横の配
線が互いに邪魔しあうことが少ないため、ランダムな層
選択による配線よりも、配線しやすくなっている。眉間
の結線は、ビア１．即ち、スルーホールを介して行われ
る。

また、配線率を向上させるために、配線径路の探索時に
は、チャネル内で実トレースを決定せずに、配線径路の
探索処理終了後にトレース・アサインするデータフロー
ティングの方式がとられている。

第５図において、２は配線の基準となる基本格子を表し
ている。例えば、１つの基本格子２の幅に関連するチャ
ネルに、２本の配線が設定可能であれば、その容量は「
２」であるとされる。データフローティングの方式では
、まず、各格子点に初期容量（例えば「２」）を割り当
てておき、第５図（Ａ）において１図示Ａ点とＤ点とを
結線するとき、その点間における容量を１ずつ減算する
。

同様に図示Ｂ点と０点とを結線する場合にも、容量を１
ずつ減算し、容量がｒＯＪになった点については、配線
不可とする。このようにして１チヤネルの容量に基づき
結線を保証し、配線処理終了後に、第５図（Ｂ）図示の
ように、実際の配線位置を固定化する実トレースへのア
サイン処理を行う。

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

第６図は従来方式の問題点を説明するための図である。

従来、多層の配線を行う場合に、第４図で説明したよう
な層ペアによる配線を行っているが、従来方式によれば
、配線すべき区間のすべての径路が、対象としている層
で決定されなければ、径路探索に失敗したことになる。

即ち９例えば第６図（Ａ）図示のように、配線対象層が
第１と第２の層であって、Ａｌ　　（Ａ２）点からＣ１
（Ｃ２）点までの配線が必要である場合に、第２層にお
けるＢ２点から０２点までの径路がなければ、この径路
探索は失敗となる。

しかし、このとき、径路の一部を他の層で配線すること
により、全体として、より効果的な径路決定が可能であ
る場合がある。即ち、第６図（Ｂ）図示のように、第１
番目の層におけるＢｉ点とＣｉ点とを介して、効果的に
結線できる場合がある。

従来の２層配線方式では、第６図（Ｂ）図示のような配
線がなされないため、効果的な配線ができないという問
題があった。しかしながら、２層配線方式をとらずに、
多層について一度に配線を行う処理方式では、探索空間
が膨大になり、径路探索が困難になると共に、従来の既
存の自動配線プログラムを活用できないという問題があ
る。

本発明は上記問題点の解決を図り、従来の自動配線シス
テムに若干の修正を加えるだけで、多層データの処理に
より、効果的な配線を行うことができる方式を提供する
ことを目的としている。

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

第１図は本発明の基本構成図を示す。

第１図において、１０は配線に関する基礎データを記憶
する設計ルール記憶部、１１は主配線方向が同し層のも
のをグループ化して、仮想的な１組（ＤＨ層ペア想定し
、この層ペアにおける各主配線方向が同じ全層の容量を
合計する全層容量合計部、１２は上記仮想的な層ペアに
ついて、全層容量合計部１１が算出した容量に基づいて
配線の径路を探索する径路探索部、１３は径路探索部１
２が探索した径路情報を登録する径路登録部、１４は径
路登録部１３により登録された径路情報に基づき、２層
１組の元の層ペアに対して実トレースへのアサインを行
い、アサインできない径路については、順次、残りの層
にアサインしていく処理を実行する実トレースアサイン
部を表す。

本発明の場合、設計ルール記憶部１０から結線の座標情
報等を入力すると、全層容量合計部１１は、各層ペアに
おける主配線方向が同じものの容量を合計して、あたか
も１組の層ペアだけがあるかのように容量を初期設定す
る。径路探索部Ｉ２は、この仮想的な層ペアについて、
従来と同様なデータフローティングによる２層配線方式
で、配線径路を探索し、成功した径路を径路登録部１３
に通知する。径路登録部１３は２通知された径路を所定
のテーブルに登録する。

探索が終了すると、実トレースアサイン部１４が起動さ
れ、実トレースアサイン部１４は、径路登録部１３によ
る登録情報に基づいて、実トレースへのアサインを行う
。このとき、実トレースアサイン部１４は、適当な２層
１組の層ペアを選択してアサインを行い、アサインがで
きなくなった場合に、他の層にアサインし、同様にアサ
インができなくなる毎に、順次、残りの他の層にアサイ
ンしていく。

〔作用〕

第２図は本発明の詳細な説明するための図を示す。

全層容量合計部１１は１例えば第２図（Ａ）に示した容
量を、第２図（Ｂ）に示すようにＸ方向のものとＹ方向
のものとにまとめる。そして、径路探索は、これらの増
加した容量に基づいて行う。

従って５例えば第６図（Ａ）図示のような状態でも、探
索結果が、容量不足から「径路なし」となることはな（
、第６図（Ｂ）図示のように、他の第１層における配線
の可能性があれば、径路探索成功となる。

実トレースへのアサインでは、第２図（Ｃ）図示のよう
に９元の層を対象とし２選択された２層でアサインでき
ない径路は、残りの層でアサインする。残りの層に存在
する容量分の配線が予め保証されているので、必ず残り
の層にアサイン可能となっている。

〔実施例〕

第３図は本発明の一実施例処理を説明するためのフロー
チャートである。以下、第３図に示す番号■ないし＠に
従って説明する。

■　設計ルールを入力する。即ち１層数や各層の主配線
方向情報、格子数等の領域情報、チャネル間本数、クリ
アランス、線幅、ワイヤ数とワイヤの始点・終点の位置
情報等を入力する。

■　処理■で入力した設計ルールに基づき、上記線方向
がＸ方向のものと、Ｙ方向のものとに分けて、各々全層
分の容量を加算する。

■　径路探索のため、順次、ワイヤを選択する。

なお、ワイヤは等電位となるべき線である。すべてのワ
イヤについての探索が終了した場合。

処理■へ制御を移す。

■　いわゆる格子ラベリングにより、容量チェックおよ
び既存端点の方向チェックを行いつつ。

径路を探索する。格子ラベリングは２周知のように、始
点および終点の各々から、到達可能点にそれぞれ印を順
次付与していくことにより。

接続径路を見つけ出す処理である。

■　径路があるかないかの判定により、径路がある場合
には、処理■へ移る。径路がない場合。

処理■を実行する。

■　径路探索に必要な全格子ラベリングが終了したかど
うかを判定し、まだ終了していない場合には、処理■に
戻って、同様に処理を繰り返す。

全格子ラベリングが終了していれば、探索不成功であり
、処理■に戻って、他のワイヤを選択する。

■　径路探索が成功した場合、その径路の線分データを
作成し、登録する。

■　発生した線分データに関連する格子に対応する部分
の容量を１ずつ減算し、処理■に制御を戻して９次のワ
イヤにつき同様に処理を繰り返す。

■　すべてのワイヤについての探索処理が終了したなら
ば、処理■において登録した線分データを順次取り出す
。線分データがなくなった場合に、自動配線処理終了と
する。

［相］　取り出した線分データについて、アサインすべ
き層を選択する。

■　実トレースへのアサインを実行する。

［相］　現在の層についてアサインできたか否かを判定
し、アサインできない場合、処理［相］へ制御を戻し１
次の層を選択する。アザインができた場合、処理■へ制
御を戻し１次の線分データを選択する。

以上の処理において、従来の２層用自動配線処理と異な
る部分は１例えば上記処理■、処理［相］。

処理＠の部分であり、既存の自動配線プログラムに若干
の修正を加えるだけで１本発明を実施することが可能で
ある。

〔発明の効果〕

以上説明したように１本発明によれば、２層１組の層ペ
アに基づ（多層自動配線を行うにあたって、実質的に配
線可能なものを容量不足として扱うことがなくなり、３
層以上の多層データについて効果的な配線が可能になる
。

【図面の簡単な説明】

第１図は本発明の基本構成図、第２図は本発明の作用説
明図、第３図は本発明の一実施例処理説明図、第４図は
従来の２層配線方式の説明図、第５図は従来方式の説明
図、第６図は従来方式の問題点説明図を示す。 図中、１０は設計ルール記憶部、１１ば全層容量合計部
、１２は径路探索部、１３は径路登録部。 １４は実トレースアサイン部を表す。 特許出願人　　　富士通株式会社 代理人弁理士　　森１）寛（外１名） 梃来ネへ・ 第 ９間卸、鰍説明口 ６図

Claims (1)

1. 【特許請求の範囲】 各チャネルに予め与えられた容量に基づき、主配線方向
   が異なる２層の組からなる層ペアに対して、データフロ
   ーティングにより配線の径路を探索し、径路探索後に実
   トレースへのアサインを行って自動配線する多層自動配
   線処理方式において、主配線方向が同じ層のものをグル
   ープ化して、仮想的な１組の層ペアを想定し、この層ペ
   アにおける各主配線方向が同じ全層の容量を合計する全
   層容量合計部（１１）と、 上記仮想的な層ペアについて、上記全層容量合計部（１
   １）が算出した容量に基づいて配線の径路を探索する径
   路探索部（１２）と、 該径路探索部（１２）が探索した径路情報を登録する径
   路登録部（１３）と、 該径路登録部（１３）により登録された径路情報に基づ
   き、２層１組の層ペアに対して実トレースへのアサイン
   を行い、アサインできない径路については、順次、残り
   の層にアサインする実トレースアサイン部（１４）とを
   備えたことを特徴とする多層自動配線処理方式。