JPH0754532B2

JPH0754532B2 - 多層同時配線方法

Info

Publication number: JPH0754532B2
Application number: JP1041864A
Authority: JP
Inventors: 頼子奥村; 治郎楠原; 一彦飯島; 康行藤原
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1989-02-23
Filing date: 1989-02-23
Publication date: 1995-06-07
Anticipated expiration: 2010-06-07
Also published as: JPH02222072A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、多層プリント基板、多層集積回路等の配線パ
ターンの配線情報を自動決定する方法に係り、特に、最
短配線が必要なパターン、配線長制約の厳しいパターン
等を決定するために用いて好適な多層自動配線方法に関
する。

〔従来の技術〕

従来一般に、多層プリント基板、多層集積回路等は、Ｘ
軸,Y軸の２方向にパターンの走る配線層を１組のペア層
とし、このペアによる配線パターンを形成後、複数のペ
ア層相互間に絶縁層をはさんで積層するという方法によ
つて製造されていた。

以下、この種従来技術を図面により説明する。

第18図は従来技術によるプリント基板の配線層の構成の
一例を示す図、第19図はその配線パターン例を示す図で
ある。第18図，第19図において、１はｘ軸方向層、２は
ｙ軸方向層、３は絶縁層、４は基板上の障害物、５はパ
ターン始点、６はパターン目的点である。

従来技術によるプリント基板は、第18図に示すように、
ｘ軸方向層1,y軸方向層２の２枚の配線層をペアとし、
このペアの層に所要の配線を行つた後、複数のペア層を
絶縁層３を介して積層するものである。

このように構成される基板に対して自動配線を行う場合
に、一般的に用いられているアルゴリズムの基本的な考
え方は、Ｘ軸,Y軸の２方向を用い、平面上で配線パター
ンを探査していくというものである。第19図に示すパタ
ーン例は、基板上に配線を通すことができない障害物４
がある場合の例で、パターン始点５及びパターン目的点
６より、発生させた配線パターンが接触するまで、配線
パターンを伸ばしていくという方法により作成される。
この場合、第19図のように基板上に障害物４があれば、
配線パターンの配線層を変更しパターンの走行方向を変
化させて、パターンの生成が継続的に行われる。

一方、年々、プリント基板，集積回路等が大規模化，高
密度実装化されてきており、多層化による対応が進んで
きている。また、大規模化に伴い、配線デイレイに対す
る考慮も重要な問題となり、斜め方向の配線パターンを
用いた最短配線による対処が不可欠となつている。

このような斜め配線パターン層を用いたペア層による配
線パターン生成の従来技術として、例えば、特開昭58−
56500号公報等に記載された技術が知られている。

第20図はこの従来技術による層選択を説明する図、第21
図は中継点の選定を説明する図、第22図，第23図はその
配線パターン例を示す図である。第21図〜第23図におい
て、７は中継点候補、８は配線パターンであり、他の符
号は、第19図の場合と同一である。

この従来技術は、まず、配線対象区間を結ぶ線分がｘ軸
となす角度により、１層または組み合わせによる２層を
決定する。例えば、配線方向として、ｘ軸方向、ｙ軸方
向、ｘ軸,y軸からそれぞれ45゜時計回りに傾いたΔｘ軸
方向、Δｙ軸方向が使用可能であるとすれば、これらの
方向の配線層の２つがペアとして選択される。第20〜22
図の例では、Δｙ軸方向とｘ軸方向とを選択している。

次に、配線対象区間の形状により、複数の中継点候補７
を選定する。

最後に、選定された中継点候補７を用いて設定した複数
種の配線パターンのうち実現可能な最短パターンを決定
する。

前述の従来技術による配線方法は、配線パターン探査前
に、予め配線層の配線方向を限定してしまうので、例え
ば、第22図に示すように、開始点５と目的点６との間の
配線区間付近に障害物４がある場合、決められた配線方
向のパターンを用いなければならず、かえつて、配線パ
ターン８の迂回を生じ、配線長が長くなつてしまう場合
を生じてしまう。この例の場合、例えば、ｙ軸方向のパ
ターンも使用可能であれば、第23図に示すように、配線
パターン８を決定でき、配線パターンの迂回を回避する
ことが可能であるが、前記従来技術では、このような配
線パターンの迂回の回避を行うことが不可能である。

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

前述した、ｘ軸方向及びｙ軸方向のみの配線層を用いる
従来技術は、回路の大規模化に伴う配線デイレイに対す
る配慮がなされておらず、最短配線による配線デイレイ
の減少が困難であるという問題点を有している。

また、前記公報に記載された従来技術は、斜め配線方向
層を用いることができ、配線デイレイの減少を図ること
が可能であるが、予め配線層の方向を決定しているの
で、障害物等がある場合に、パターンの迂回を生じさせ
てしまい、かえつて、配線デイレイを増加させてしまう
ことがあるという問題点を有している。さらに、この従
来技術は、配線層決定時に、配線対象区間に最適なペア
層を選択するために、パターンの走行方向による全種類
の組み合わせの中から選択する必要があり、パターン走
行方向の種類が多様化するに伴い、必要な配線層の総数
が膨大になり、選択が困難になるという問題点がある。
その上、配線対象区間のパターン方向の傾きにばらつき
があるので、各ペア層の配線パターンの混雑度に不均一
が生じ、非効率的であり、結線率をある程度以上に大き
くすることができないという問題点を有している。

本発明の目的は、前記従来技術の問題点を解決し、複数
層を配線層とした配線処理により、作成可能な配線パタ
ーン形状を多様化することにより、高結線率と最短配線
を可能とし、配線長の決められた配線区間の配線長精度
を向上することができ、かつ、配線パターン決定時に、
各配線層の混雑度を考慮することにより、各層の混雑度
の平均化を図ることを可能とした多層同時配線方法を提
供することにある。

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

本発明によれば、前記目的は、配線層を異なるパターン
走行方向を有する３層以上の配線層とし、配線対象区間
毎に、次の（１）〜（４）の処理をこの順序で実行して
配線パターンを決定することにより達成される。

（１）各層毎の混雑度算出各層毎に、（ａ）既に決定された配線情報フアイルよ
り、既配線パターンを取り出し、そのパターン長を算出
する。（ｂ）基板情報フアイルより使用可能な配線領域
の大きさ、使用可能最大チヤネル数（配線格子間に作成
可能なパターン本数）及びパターンの走行方向を取り出
し、作成可能パターン長を算出する。（Ｃ）前述の既配
線パターン長及び作成可能パターン長より、層別混雑度
を算出する。

（２）各層毎の得点算出設計情報フアイルより、配線対象区間の始点と目的点と
を結ぶ線分の角度を算出し、配線対象区間の配線長に関
する制約条件を取り出し、これらを基に、使用可能であ
るパターン走行方向のそれぞれの優先順位を決定し、こ
の優先順位と前記層別混雑度及び各配線層のパターン方
向により、使用可能配線層のそれぞれに対して使用得点
を算出する。

（３）配線パターン生成当該配線対象区間の始点より、全方向に対する配線パタ
ーン作成可能な格子点（パターン作成可能点）上に配線
パターンを作成し、その先端を試行端点とする。次に、
この試行端点より次の試行端点までの配線パターンの作
成を前述と同様に実行し、試行端点が目的点に達するま
で繰り返す。この結果、候補となる複数の配線パターン
候補が生成される。なお、生成される配線パターン候補
の走行方向は、第16図に示すようなｘ軸方向、ｙ軸方
向、Δｘ軸方向、Δｙ軸方向からなる平面方向９及びこ
れら平面方向パターン用の配線層相互間を接続する垂直
方向10を用いる。これにより、複数層を配線層とした配
線パターン候補を生成することができる。

（４）配線パターン決定前述した配線パターン候補生成時に、各配線パターン候
補の配線長さ、配線対象区間に対する各配線パターン候
補の走行方向、V.H.（ViaHole:配線パターンが層を変更
する場合に、それらの層間を接続するために作成される
経由穴）の要否、及び前述で求めた層別使用得点によ
り、各試行端点における試行得点を算出する。次に、各
配線パターン候補のそれぞれについて、全ての試行端点
における試行得点を合計することにより、各配線パター
ン候補の得点を求め、その得点の大小により最適な配線
パターンを決定する。但し、配線パターン長の指定ある
配線対象区間については、指定長に最も近い長さを持つ
配線パターン候補を最適な配線パターンとして決定す
る。

第17図はこのようにして決定された配線パターン候補の
一例を示す図であり、11はV.H.である。

第17図において、a₁〜a₆は各試行端点における試行得点
であり、この例の配線パターン候補の得点は、となる。

〔作用〕

本発明による配線パターンの決定は、配線対象区間毎
に、既配線パターン長に基づいて層別混雑度を算出し、
これを考慮して配線パターンを決定しているので、各層
の使用率を詳細に制御することができる。また、配線パ
ターン作成時に、同時に複数層を対象とした配線パター
ンを作成するため、始点及び各試行端点で使用可能な走
行方向全てのパターンを考慮することにより、多様な配
線パターン候補を生成することができ、結線率の向上を
図ることが可能である。さらに、配線パターン決定時
に、当該配線対象区間の既配線パターンの長さや迂回に
応じて、多様な配線パターン候補の中から最適なものを
選択することができ、最短配線や、指定された配線長に
よる配線において、高精度な結果を得ることができる。

〔実施例〕

以下、本発明による多層同時配線方法の一実施例を図面
により詳細に説明する。

第１図は本発明の一実施例における処理を説明するフロ
ーチヤート、第２図は本発明の一実施例のハードウエア
構成図、第３図は本発明の一実施例の配線層の構成を示
す図、第４図は既配線パターン長を説明する図、第５図
は混雑度に応じた各層の得点算出を説明する図、第６図
は得点算出を説明するための配線パターン例を示す図、
第７図（ａ），（ｂ）は配線パターン候補例を示す斜視
図、第８図は配線パターン候補例を示す平面図、第９図
〜第11図は配線長指定による配線パターン例を示す図、
第12図，第13図は配線パターン得点算出法を説明するた
めの配線パターン例を示す図、第14図は得点算出に使用
するパラメータと得点の関係を説明する図、第15図は配
線パターン候補の得点例を示す図である。第２図〜第４
図，第６図〜第13図において、21はコンピユータ、22は
設計情報フアイル、23は基本情報フアイル、24は配線情
報フアイル、25〜28は方向別の各配線層であり、他の符
号は第18図〜第23図の場合と同一である。

本発明の一実施例は、第２図に示すように、自動配線処
理を行うコンピユータ21、配線対象区間の座標及び当該
配線区間の配線時の制約条件等を持つ設計情報フアイル
22、配線パターンが印刷される基板についての情報を持
つ基板情報フアイル23、自動配線処理により決定された
配線パターン情報を保持する配線情報フアイル24を備え
て構成されている。

このように構成される本発明の一実施例は、第１図に示
すような、配線対象区間抽出S1、各層毎の混雑度算出S
2、各層毎の得点算出S3、配線パターン候補生成S4、配
線パターン決定S5、配線パターン格納S6の６つの処理段
階を順次実行することにより、配線パターンを決定す
る。

以下、各段階毎の処理について、通常の配線区間と最短
配線区間との配線処理を説明する。なお、以下に説明す
る本発明の実施例では、最適配線パターンは、得点が最
小となるパターンであるとする。また、本発明の一実施
例の層構成は、第３図に示すように、ｘ軸方向層（Ａ
層）、ｙ層方向層（Ｂ層）、ｘ軸に対して45゜方向層
（Ｃ層）、135゜方向層（Ｄ層）の４層の配線層により
構成されるものとし、これらの配線層を貫通するV.H.11
を自由に設け、各配線層上の配線パターン相互間を接続
できるものとする。

段階I:配線対象区間抽出（ステツプS1）設計情報フアイル22から、配線対象区間を構成する配線
パターンの始点及び目的点の各座標と、当該区間を配線
する際の制約条件（配線パターン長、配線パターン形状
等）を読み出し、コンピユータ21に入力する。

段階II:各層毎の混雑度算出（ステツプS2）コンピユー
タ21は、次の計算式により、層別混雑度を算出する。

但し、 l_x＝既配線パターンのｘ方向格子数 l_y＝既配線パターンのｙ方向格子数である。

すなわち、既配線パターン長は、第４図に示すように、
パターンの始点５の位置と目的点６の位置とにより、格
子点距離を単位として、両位置の直線距離として求めら
れる。

作成可能パターン長Ｌ（例）（１）ｘ軸方向層、ｙ軸方向層の場合Ｌ＝（基板のｘ軸方向格子数） ×（基板のｙ軸方向の格子数） ×（格子間に作成可能なパターン数の最大値） −（基板上の配線不可領域の格子数）（２）45゜方向層、135゜方向層の場合段階III:各層毎の得点算出（ステツプS3）（ａ）前述で求めた層別混雑度に基づいて、各層の使い
やすさの指標となる得点を決定する。例えば、各層にお
ける配線の混雑度が、第５図に示されたような値をもつ
ている場合、各混雑度に応じた得点を与える。この得点
は、各層の得点の合計が100点となるように、前述の混
雑度の値と層間の比率が変わらないように決定するもの
である。

（ｂ）配線対象区間の形状及び配線時の制約条件に基づ
いて、前述した各層の得点に修正を加え、層別使用得点
を算出する。この層別使用得点について、第６図に示す
配線パターンの例により説明する。第６図に示す配線パ
ターン８の配線対象区間は、始点５と目的点６との間で
あり、この場合にｘ軸方向層（Ａ層）と45゜方向層（Ｂ
層）の２つの配線層を用いた配線パターン８は最短とな
る。そこで、通常配線区間に対しては、ｘ軸方向層（Ａ
層）と45゜方向層（Ｃ層）とを使いやすくするため、例
えば、第５図におけるこれらの対応層であるＡ層とＣ層
の混雑度による得点から５を引き、これを通常配線の場
合の層別使用得点とする。また、135゜方向層（Ｄ層）
は、第６図における配線対象区間と反対方向となるの
で、この層よりＹ軸方向層（Ｂ層）を使いやすくするた
め、例えば、第５図におけるＹ軸方向層（Ｂ層）の混雑
度による得点から３を引き、これを通常配線の場合のＢ
層すなわちＹ軸方向層の層別使用得点とする。この結
果、各層の混雑度及び配線対象区間の始点５と目的点６
との間の角度による最短配線を考慮した通常配線区間用
層別使用得点は、第５図に示すように決定される。ま
た、最短配線指定区間に対しては、層の混雑度より最短
経路を重視する必要があるので、層の混雑度を無視し、
ｘ軸方向層25、45゜方向層が使いやすくなるように、例
えば、第５図に示すように使用得点を定める。

段階IV:配線パターン候補生成（ステツプS4）いま、第８図に示すような位置にある始点５及び目的点
６の間にパターンを生成するものとする。この場合、始
点５より目的点６まで、障害物４を避け、全方向に配線
パターン候補を生成する。第７図、第８図において、
R_x,R₄₅,R₁₃₅,R_yは、配線パターン候補の例であり、第７
図（ａ）には、配線パターン候補R_x,R₄₅の層間配線され
た斜視の、また、第７図（ｂ）には、配線パターン候補
R₁₃₅,R_yの層間配線された斜視の様子が示されている。

配線パターン候補R_xは、始点５よりｘ軸方向にパターン
を生成した場合であり、障害物４を避ける位置までｘ軸
方向パターンを伸ばし、V.H.11を作成してＢ層に移行し
てｙ軸方向にパターンを生成し、さらに、目的点へ最短
結線を行うために、V.H.11を介してＤ層に移り、135゜
方向パターンにより目的点６に直接結線したものであ
る。

配線パターン候補R₄₅は、最短パターンであり、障害物
４により、始点５から直接45゜方向にはパターンの生成
を行うことができないので、一旦ｙ軸方向パターンを生
成して障害物４を避けて最短としたものである。

配線パターン候補R₁₃₅は、始点５より135゜方向にパタ
ーンを生成した場合の最短パターンである。

また、配線パターン候補R_yは、通常配線区間での層別使
用得点の低いｘ軸方向層及び_ｙ軸方向層のみを使用した
場合の最短パターンである。

次に、設計情報フアイル２により決められたパターン長
で配線を行う。配線長指定配線の例について、第９図〜
第11図により説明する。

第９図は、始点５と目的点６との間を、ｘ軸方向、ｙ軸
方向層上で11格子の指定長で配線した例である。ところ
が、目的点６の近傍に障害物４が存在すると、ｘ軸方向
層及びｙ軸方向層のみを用いた配線パターンは、第10図
に示すように、配線パターンl₁のように、２格子の迂回
が生じてしまう。この場合、斜め方向パターンを利用す
れば、第11図の配線パターンl₂のように、配線長を短縮
して、指定されたパターン長に対する精度を向上させる
ことができる。

段階V:配線パターン決定（ステツプS5）（１）配線パターン得点の算出第７図，第８図により説明した最短配線パターンR₄₅の
通常配線時の配線パターン得点の算出方法を第12図を参
照して説明する。

始点５から目的点６との間の第１の試行端点αにおい
て、始点５から試行端点αまでは、目的点に近づくベク
トルで格子数が１であり、V.H.11を使用していないの
で、第14図により、ベクトル得点ｌ＝５、V.H.得点Ｖ＝
０となる。また、使用配線層がｙ軸方向層であるＢ層で
あるので、第５図より層得点Ｌ＝10となる。同様に、試
行端点βにおいて、試行端点αから試行端点βまでは、
目的点に近づくベクトルで格子数が２で、試行端点αに
おいてＢ−Ｃ層間にV.H.11を使用し、使用配線層として
45゜方向層であるＣ層を使用するので、第14図，第５図
より、ベクトル得点ｌ＝10、V.H.得点Ｖ＝２、Ｌ＝32を
得ることができる。また同様に、目的点６に到達した試
行端点γにおいては、V.H.11を試行端点βでＣ−Ａ層間
に使用し、使用配線層としてｘ軸方向層であるＡ層を使
用しているので、第14図，第５図より、ベクトル得点ｌ
＝10、V.H.得点Ｖ＝２×２＝４、Ｌ＝14を得ることがで
きる。これらの得点の全てを合計したものが、配線パタ
ーンR₄₅の通常配線での配線パターン得点となり、その
値は、87となる。

同様に、第14図及び第５図を用いることにより、配線パ
ターンR₄₅の最短指定配線時の配線パターン得点を求め
ることができる。この場合の、各試行端点における各得
点が第13図に示されている。

前述のようにして、各配線パターン候補についての配線
パターン得点を求めることができ、第７図及び第８図に
より説明した各配線パターン候補についての配線パター
ン得点は、第15図に示すようになる。

（２）配線パターン決定本発明の一実施例では、配線パターン得点の最小のもの
を最適解としているので、通常配線時には、第15図に示
す得点に基づいて配線パターン候補R_yが、また、最短指
定配線時には、同様に配線パターンR₄₅が選択されて、
配線パターンとして決定される。

前述により、同一配線区間に対しても、第５図及び第14
図に基づいて、一般配線時には配線層の混雑度の小さな
ｘ軸方向層、ｙ軸方向層を使用した配線パターンが選択
され、混雑度の平均化を図ることができ、また、最短指
定配線時には、配線層の混雑度に関係なく、最短配線パ
ターンが選択されることになる。

段階VI:配線パターン格納（ステツプS6）段階Ｖで選択された配線パターンについての情報（座
標，配線層名等）を、配線情報フアイル24へ格納する。
以上により、一配線対象区間についての処理を終了す
る。

前述した本発明の一実施例によれば、通常の配線区間に
おいては、既決定配線パターンによる各各配線層の混雑
度を考慮し、全層を対象とした多様な配線パターン候補
を自動生成し、その中から配線対象区間に最適な配線パ
ターンを自動決定することが可能となる。また、最短配
線指定区間においては、配線パターン生成時に、全配線
層を考慮することにより、生成し得る最短配線パターン
を自動決定することが可能となる。さらに、本発明の一
実施例によれば、配線長が事前に指定されている区間に
おいては、配線パターン生成時に、全配線層を考慮する
ことにより、配線パターンの迂回等にも柔軟に対応し
た、配線長精度の高い配線パターンを自動決定すること
が可能となる。

前述した本発明の一実施例は、４層の配線層を有する基
板上における配線パターンの作成についてであるが、本
発明は、複数層の配線層を備えるものであれば、配線層
の数は任意であり、プリント基板、LSI等における配線
パターンの作成に適用することができる。

〔発明の効果〕

以上説明したように、本発明によれば、配線パターン作
成時に、プリント基板,LSI等を構成する全ての配線層を
考慮することができるため、幅広い配線パターン候補の
中から、配線対象区間に最適な配線パターンを選択する
ことが可能となるとともに、配線パターン決定時に、既
配線パターンによる各配線層の混雑度を考慮することに
より、各配線層の使用率をより詳細に制御することがで
きる。これにより、本発明は、高結線率，最短長配線，
指定された配線長による配線時の精度向上を図ることが
できる。

【図面の簡単な説明】

第１図は本発明の一実施例における処理を説明するフロ
ーチヤート、第２図は本発明の一実施例のハードウエア
構成図、第３図は本発明の一実施例の配線層の構成を示
す図、第４図は既配線パターン長を説明する図、第５図
は混雑度に応じた各層の得点算出を説明する図、第６図
は得点算出を説明するための配線パターン例を示す図、
第７図（ａ），（ｂ）は配線パターン候補例を示す斜視
図、第８図は配線パターン候補例を示す平面図、第９
図，第10図，第11図は配線長指定による配線パターン例
を示す図、第12図，第13図は配線パターン得点算出法を
説明するための配線パターン例を示す図、第14図は得点
算出に使用するパラメータと得点の関係を説明する図、
第15図は配線パターン候補の得点例を示す図、第16図は
パターン走行方向を説明する図、第17図は配線パターン
候補例を示す図、第18図は従来技術によるプリント基板
の層構成の一例を示す図、第19図はその配線パターン例
を示す図、第20図は従来技術による層選択を説明する
図、第21図は中継点の選定を説明する図、第22図，第23
図はその配線パターン例を示す図である。１……ｘ軸方向層、２……ｙ軸方向層、３……絶縁層、
４……障害物、５……始点、６……目的点、７……中継
点候補、８……配線パターン、９……平面方向、10……
垂直方向、11……V.H.、21……コンピユータ、22……設
計情報フアイル、23……基板情報フアイル、24……配線
情報フアイル。

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号庁内整理番号ＦＩ技術表示箇所Ｈ０５Ｋ 3/46 Ｂ 6921−4Ｅ (72)発明者藤原康行茨城県日立市久慈町4026番地株式会社日立製作所日立研究所内 (56)参考文献特開平２−2467（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】パターン走行方向の異なる複数の配線層を
備える多層配線層による回路の、始点及び目的点から成
る配線対象区間と配線時の制約情報とに基づいて、配線
パターンを自動決定する配線方法において、前記配線対
象区間の始点と目的点とを結ぶ線分の角度及び前記配線
対象区間の配線長に関する制約条件により、前記多層配
線層内の使用可能なパターン走行方向を有する配線層の
それぞれの優先順位を決定し、該優先順次とパターン走
行方向とにより、前記使用可能な配線層のそれぞれの使
用得点を決定するステップと、前記配線対象区間の始点
と目的点間に対し、平面上に進む配線パターンの経路探
査及び複数の配線層間を接続する平面と垂直な層間経由
穴の層変更探査を行い、３層以上の複数層を配線層とす
る複数の配線パターン候補を生成するステップと、前記
配線パターン候補のそれぞれについて、使用する各配線
層の使用得点、配線パターンの長さ，層間経由穴の有無
に基づいて、その得点を決定し、この各パターン候補の
得点に基づいて最適な配線パターンを決定するステップ
とを有することを特徴とする多層同時配線方法。
【請求項２】前記各配線層毎に、作成可能パターン長に
対する既配線パターン長の割合を求め、配線層別混雑度
を算出するステップをさらに有し、前記配線層の使用得
点を決定するステップは、前記配線層の混雑度をも加え
て配線層の使用得点を決定することを特徴とする特許請
求の範囲第１項記載の多層同時配線方法。