JPH05205011A - 回路基板の配線パターン決定方法及び回路基板 - Google Patents

Abstract

(57)【要約】 【目的】 局所的な特定方向の混雑を緩和すること、短
い配線長にすること、高い配線率で配線パターンを決定
すること。 【構成】 配線領域を複数の領域に分割し（９２）、各
々の分割領域においてｘ方向およびｙ方向の通過本数を
算出し局所的な混雑を認識する（９３１）。いずれの方
向も混雑しない領域ではｘｙ原則に従い、例えばｘ方向
が混雑する領域ではｘｙ原則を崩して両層ともｘ方向に
配線する（９３２）。この場合、ｘｙ原則を崩したこと
により新たに通過可能となる本数（”効能”）が、ｘｙ
原則を崩したことによりｙ方向に通過不能となる本
数（”副作用”）よりも大きいときのみ、ｘｙ原則を崩
すことにする。これにより決定された各分割領域ごとの
配線方向に従って、迷走法により配線パターンを決定す
る（９５）。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、プリント配線板、マル
チチップモジュール、半導体集積回路装置などの回路基
板に定義されたネットの配線パターンを決定する回路基
板の配線パターン決定方法に関し、特に、局所的な配線
混雑を解消し、短い配線長で高密度の配線パターンを自
動決定するのに好適な配線パターン決定方法に関する。

【０００２】

【従来の技術】回路基板上に定義される所定のピンを電
気的に接続するネットを、効率的に配線するための技術
として、従来から、「ｘｙ原則」と呼ばれる手法が広く
用いられている。ここで、ｘｙ原則とは、直交する２つ
の方向ｘ，ｙをそれぞれ２つの配線層に割り当て、各配
線層では主としてその方向に配線パターンを形成すると
いう原則である。例えば、第１層ではｘ方向に配線し、
第２層ではｙ方向に配線し、第１層上を走行する配線パ
ターンと第２層上を走行する配線パターンの接続はビア
ホールにより行う。

【０００３】このようなｘｙ原則が広く用いられてきた
理由の１つは、配線パターンを整然と収容することがで
き、配線率を高めることができるからである。仮りに、
ｘｙ原則を用いず、各々の層において全方向へ自由に配
線させたとすると、先に決めた配線パターンが後続の配
線パターンの障害となり、配線不能が多発することにな
る。

【０００４】しかし、高密度の配線に有効なｘｙ原則を
用いる場合にあっても、次に述べるような問題がある。

【０００５】まず第１に、特定の同一方向の配線要求本
数が非常に多い場合、又はｘ方向とｙ方向の配線要求本
数に偏りがある場合は、要求される配線パターンの全部
を収容しきれず、配線不能が生じるという問題がある。
つまり、図３０（ａ）に示す配線パターン例のように、
配線領域２におけるｘ方向の配線要求本数が非常に多
く、ｘ方向の配線トラックをすべて使用しても、一部の
ネット（Ｐ1-Ｐ1'、Ｐ2-Ｐ2'、Ｐ3-Ｐ3'）が配線不能と
なる。

【０００６】第２に、配線領域全体としてはｘ方向とｙ
方向の配線要求本数のバランスがとれていても、局所的
に特定の同一方向の配線が集中すると、一部の配線パタ
ーンを迂回して形成しなければならない問題がある。つ
まり、図３０（ｂ）に示す例のように、ｘ方向の配線が
配線領域２の中央部に集中しているため、一部のネット
（Ｐ1-Ｐ1'、Ｐ2-Ｐ2'、Ｐ3-Ｐ3'）の配線パターンを、
その領域を迂回させて形成しなければならない。

【０００７】このような問題を解決するため、従来いく
つかの手法が提案されている。まず第１の手法として
は、各々のネットの両端のピンを結ぶ直線の角度を求
め、その角度分布に応じて、回路基板の各配線層の配線
方向を決定するものである。例えば、特開昭５４−７９
４７２公報に記載された手法では、配線層をｘｙｘｙと
いうようにｘ方向層とｙ方向層とを交互に積層すること
に代えて、ネットの角度分布に応じて各配線層の配線方
向を任意に決定するようにしている。例えば、ｘ方向に
近い角度のネットが多い場合、ｘ方向層の数を多くし、
配線層をｘｘｘｙとする。逆に、ｙ方向に近い角度のネ
ットが多い場合は、ｙ方向層の数を多くし、配線層をｘ
ｙｙｙとする。

【０００８】また、特開平２−１２７７７２公報にも上
記公報と同様、ネットの角度分布に応じて回路基板にお
ける各配線層の配線方向を決定するようにすることが記
載されている。ただ、配線領域を複数の領域に分割し、
各分割領域毎に適当な配線方向を決定するようにしてい
る点で、上記公報に記載された手法と異なるが、各分割
領域における配線方向の決定は、上記公報に類似した方
法を用いている。すなわち、各分割領域に両端のピン
が”含まれる”ようなネットについて、ピンを結ぶ直線
の角度を求め、その角度分布に応じて配線方向を決定す
る。例えば、回路基板の左半分の領域にはｘ方向に近い
角度のネットが多く、右半分の領域には４５°方向に近
い角度のネットが多い場合、回路基板の左半分の領域で
は、２つの配線層のうち一方の層の配線方向をｘ方向と
定め、右半分の領域では、２つの配線層のうち一方の層
の配線方向を４５°方向と定め、それぞれ他の一方の層
の配線方向は任意とするものである。この手法は、ピン
を含めてネット全体が完全に含まれ、かつ他のネットの
配線を含まない分割領域が設定できる場合のみ有効であ
る。つまり、あたかも複数の回路基板が単純に接続され
ているかのように、分割領域の各々が独立しており、領
域間をまたがるネットが少ない回路基板の配線パターン
決定には有効な方法であると考える。

【０００９】第２の手法としては、全方向へ自由に配線
する手法を高度化したものである。この手法は、単に全
方向へ自由に配線するだけではかえって配線能力が低下
する事実に鑑み、取り外し再配線による繰り返し改良処
理を付加して高配線率の達成を図るものである。例え
ば、文献（R. Linsker, "An Iterative-Improvement Pe
nalty-Function Driven Wire Routing System", IBM J.
Res. Develop. , vol. 28, no. 5, pp. 613-624, 198
4.）に記載されているフリー・フォーム・ワイヤリング
（Free-form wiring）と呼ばれている手法（同文献のp
p. 615-616参照）は、ｘｙ原則に束縛されずに全方向の
配線を行い、１つの配線パターンを取り外してはそれを
再配線するという処理を繰り返すことにより、高配線率
の達成を図るものである。

【００１０】その他、関連のある従来技術として、特開
平２−９０３６８公報に記載された手法がある。この手
法は、ネットの端子（ピン）が表面実装形部品に属する
ものである場合、その部品の辺の近傍において配線方向
を縦方向すなわち辺に垂直な方向に定めるようにしてい
る。

【００１１】

【発明が解決しようとする課題】上記従来技術は、いず
れもｘｙ原則に従って配線パターンを決定する方法の問
題を解決するために提案されたのである。しかし、上記
従来技術には、次に述べるような問題が残る。以下、図
３１を参照しながら説明する。図３１は、配線パターン
決定方法の対象となる回路基板の例を示すものである。
同図において、回路基板１は２つの配線層を有する回路
基板であり、回路基板１上に配線パターンの形成が許さ
れる配線領域２が設定される。また、回路基板１には接
続すべき所定のピン３と３’を結ぶネット４が複数定義
されている。図は、配線パターン決定処理を実行する前
の状態を表しており、各々のネット４はピン３，３’を
結ぶ曲線として表されている。配線領域２の右上の領域
Ａではｘ方向の配線要求量が多いので、ｘ方向が混雑す
ると予想される。一方、左下の領域Ｂではｙ方向の配線
要求量が多いので、ｙ方向が混雑すると予想される。

【００１２】このような局所的に配線の混雑が予想され
る場合は、前記特開昭５４−７９４７２公報に記載され
たような方法、つまり、ネットの角度分布に応じて回路
基板における各配線層の配線方向を決定する方法は、有
効に対応できないという問題がある。すなわち、図３１
に示す例のように、領域Ａではｘ方向の配線要求量が多
く、別の領域Ｂではｙ方向の配線要求量が多いが、配線
領域２の全体としてはｘ方向の配線要求量とｙ方向の配
線要求量との間に偏りがない場合、通常のｘｙ原則に従
って配線可能であるという結論が導かれてしまう。しか
し、図３１の例をｘｙ原則に従って配線すれば、領域Ａ
でｘ方向の配線トラックが不足し、左下の領域Ｂではｙ
方向の配線トラックが不足する場合があるから、そのよ
うな結論は妥当でない。

【００１３】また、前記特開平２−１２７７７２公報に
記載された方法によれば、図３１に示された回路基板の
ように、領域間をまたがるネットが少なくなるよう明確
に領域分割できない回路基板に対しては、各々の領域に
対して適切な配線方向を定めることが難しいという問題
がある。また、仮に、回路基板を独立した領域に分割で
きた場合でも、それら領域の内部に存在する局所的に配
線混雑には対処できないという問題がある。

【００１４】したがって、ネットの角度分布に応じて回
路基板における各配線層の配線方向を決定する従来の方
法は、いずれも全体的な配線混雑を緩和することが可能
であるが、局所的な配線混雑は解消することができない
という問題がある。

【００１５】一方、前記従来技術のうち、全方向へ自由
に配線する手法に、取り外し再配線による繰り返し改良
処理を付加した手法によれば、許される有限の時間内に
最適解が得られるとは限らないという問題を有する。こ
れは、改良処理の過程において不適当な局所解に陥る可
能性をもつことによる。この局所解に陥るという問題
は、上記文献（R. Linsker）の619ページの"Comments o
n simulated annealingand related methods"において
論じられているように、シミュレーテッド・アニーリン
グ法などの確率論的手法を用いれば解決可能と言われて
いる。しかし、許される有限時間内に最適解が得られる
保証はない。なぜなら、このアプローチによれば、最適
解つまり高密度の配線パターンを得るためには一時的に
大きくポテンシャルを増加させなければならないからで
ある。これを示す例として、ある初期解を確率論的手法
により改良することを考える。最適解を得るには、例え
ば、ある領域をｘ方向に通る数１０本の配線パターンを
別の領域に移動した後、その領域に他の数１０本の配線
パターンをｙ方向に通過させる、といった処理が実行さ
れなければない。ところが、この数１０本の配線パター
ンが完全に移動されるまでは、この領域にｙ方向の配線
パターンを通せないわけであるから、一般には処理が完
結するまでポテンシャルが増加し続ける。つまり、最適
な状態に導くには大きなポテンシャル増加が必要であ
り、これは計算量を増大させる。

【００１６】本発明は、上記従来技術の問題点を解決す
ることを課題とするものであり、その第１の目的とする
ところは、局所的に特定の配線方向が混雑する場合に、
その混雑を緩和して、高配線率で配線パターンを決定で
きる回路基板の配線パターン決定方法を提供することに
ある。

【００１７】また、本発明の第２の目的は、上記第１の
目的に加え、短い配線長の配線パターンを決定できる回
路基板の配線パターン決定方法を提供することにある。

【００１８】本発明の第３の目的は、上記本発明の方法
により決定された高い密度の配線パターンを有する回路
基板を提供することにある。

【００１９】

【課題を解決するための手段】上記目的を達成するた
め、本発明の配線パターン決定方法は、複数の配線層を
有する回路基板に定義された複数のネットの配線経路を
決定するにあたり、前記回路基板に設定された配線領域
を複数の領域に分割し、該各分割領域における同一配線
方向の混雑の程度に応じて、前記各分割領域ごとに前記
各配線層の配線方向を決定し、該決定に従って前記各ネ
ットの配線経路を決定することを特徴とする。

【００２０】この場合において、配線の混雑の程度を判
断する手順として、各配線層の標準配線方向をそれぞれ
設定し、該標準配線方向に従って各ネットの仮想経路を
設定し、該仮想経路に基づいて各分割領域を通る配線の
要求本数を配線方向ごとに予測し、該予測に基づいて各
分割領域における同一配線方向の混雑の程度を求めるよ
うにすることができる。

【００２１】また、配線の混雑の程度に応じて、各分割
領域ごとに各配線層の配線方向を決定する手順として
は、前記各分割領域における同一配線方向の混雑度を求
め、前記各分割領域ごとに混雑度の低い配線方向の配線
層を混雑度の高い配線方向の配線層に変更して、前記混
雑を緩和するようにすることができる。この場合におい
て、変更すると寧ろ混雑度の低い配線層の混雑度の方が
高くなる場合は変更しないことが好ましい。

【００２２】また、配線の混雑の程度に応じて、各分割
領域ごとに各配線層の配線方向を決定する他の手順とし
ては、各分割領域を通る同一配線方向の配線要求本数の
予測値と、当該分割領域の標準配線方向に従った配線容
量とを比較し、予測値が配線容量を超過する本数に応じ
て、当該分割領域の他の配線方向の配線層を、配線容量
を超過する配線の配線方向に変更して、混雑を緩和する
ようにすることができる。この場合において、変更する
と寧ろ他の配線方向の配線層の配線要求本数の予測値が
当該配線層の配線容量を超過する本数の方が大きくなる
場合は変更しないことが好ましい。

【００２３】また、前記分割領域は矩形が好ましく、こ
の場合の標準配線方向は矩形の分割領域の辺に平行な直
交２軸方向ｘ，ｙに設定するのが好ましいが、これに限
らず前記直交２軸を含む対称な４軸方向に設定して、辺
に対して斜めの配線方向を含めることもできる。

【００２４】また、前記仮想経路に基づいて各分割領域
の配線混雑度を求めて、その分割領域の配線方向を決定
するにあたり、各ネットの仮想経路を複数設定するとと
もに、該各仮想経路が採用される確率を設定し、各仮想
経路が通る各分割領域ごとに、当該分割領域を通る全部
の仮想経路の確率を合計して配線方向ごとの配線要求本
数として予測し、混雑の程度を判断するにあたり、各分
割領域ごとに前記複数の配線層の配線方向の組合せ候補
を列挙し、該各組合せ候補について予測した配線要求本
数を用いて当該分割領域における各配線方向の混雑の程
度を求め、該求めた混雑の程度が最も小さい前記組合せ
候補を各分割領域ごとに前記各配線層の配線方向として
決定するようにすることができる。この場合、仮想経路
の確率は、想定できる最短距離の仮想経路の数に基づい
て設定するものとし、仮想経路が直線の場合は確率を
「１」とし、仮想経路が折線であってかつ許容する曲が
り数をｎ箇（だだし、ｎは自然数）に設定する場合は、
各曲がり数ｎごとに想定される仮想経路の群に対してそ
れぞれ群確率を配分し、さらに各群内の同一曲がり数の
仮想経路の数で前記群確率を割った確率を各仮想経路の
確率に設定する。例えば、最短距離の仮想経路が直線の
ときは確率「１」とし、折れ曲がり数を２まで許容する
場合、折れ曲がりが１つのときは仮想経路群に対して確
率「０．５」を、折れ曲がりが２つの仮想経路群に対し
て「０．５」を配分し、それぞれの群内の各仮想経路の
確率は、群内全体の仮想経路の数で群確率「０．５」を
割った値に設定する。

【００２５】更に、上記仮想経路の確率に基づいて配線
方向を決定するにあたり、各分割領域の配線方向ごとの
要求配線本数のばらつきを示す標準偏差を求め、該標準
偏差を小さくするように仮想経路の確率を変更する処理
を繰返すことが好ましい。

【００２６】また、上記第２の目的を達成する本発明の
配線パターン決定方法は、配線層ごとに配線領域を配線
単位領域（配線トラックに相当する）に格子状に区分し
てなる格子点テーブルを作成し、該各格子点テーブルの
格子点ごとに、上記いずれかの方法で決定された分割領
域ごとの各配線層の配線方向に従って配線方向を設定す
るとともに、各ネットのピンの位置及び既配線済み等の
使用済みフラグを設定し、各ネットに属する一のピンの
格子点から各格子点に設定されている配線方向に従っ
て、他の配線層にかかる格子点を含め隣接する格子点を
順次経由して当該ネットに属する他のピンに至る経路を
複数求め、該求めた複数の経路のうち最短の経路を当該
ネットの配線経路として決定し、該決定された配線経路
が通る前記格子点テーブルの格子点に使用済みフラグを
立てるようにして、配線パターンを決定することを特徴
とする。この場合において、最短の経路か否かを判断す
るにあたり、他の配線層に属する隣接格子点に移行する
場合は、同一の配線層の隣接格子点に進む場合の経路よ
りも長く評価することが好ましい。

【００２７】また、上記第３の目的を達成する本発明の
回路基板は、層状に形成された複数の配線層を有し、一
の配線層に周囲の配線方向と異なる配線方向の配線パタ
ーンが形成された少なくとも１つの矩形領域が認識さ
れ、該矩形領域を細かな矩形領域に細分したとき、各細
分矩形領域に全てのピンが含まれるネットの数よりも、
当該細分矩形領域の境界を通過する配線パターンの数を
多く形成したのである。この場合において、複数の配線
層の相互に隣接する層間にあって、少なくとも配線方向
が同一の領域に導電性を有する層が挿入することが好ま
しい。

【００２８】

【作用】このように構成されることから、本発明の配線
パターン決定方法によれば、次に説明するように上記本
発明の目的を達成することができる。まず、本発明は、
回路基板に設定された配線領域を複数の領域に分割し、
該各分割領域における同一配線方向の混雑の程度に応じ
て、前記各分割領域ごとに前記各配線層の配線方向を決
定し、該決定に従って前記各ネットの配線経路を決定す
るようにしていることから、局所的に特定の配線方向が
混雑する場合に、その混雑を緩和して、高配線率で配線
パターンを決定できる。

【００２９】このことについて、図２乃至図７に示した
具体例を参照しながら説明する。まず、本発明の配線パ
ターン決定方法は、配線パターン決定処理に先立って配
線領域のどの部分がどの方向に混雑しているかを認識す
るため、図２に示したように配線領域２を辺に平行な直
交２軸方向ｘ，ｙに沿って縦横に分割し、各々の分割領
域５において、その領域をｘ方向に通過すると予想され
る本数（ｘ方向要求本数）、およびｙ方向に通過すると
予想される本数（ｙ方向要求本数）とを見積もる。そし
て、各々の分割領域において、要求本数の値からｘｙ原
則を崩すか否かを決定する。図２では、領域Ｒ１におい
てｘ方向が混雑するので、領域Ｒ１に属する２つの分割
領域では両方の配線層でｘ方向に配線すると定める。ま
た、領域Ｒ２ではｙ方向が混雑するので、領域Ｒ２に属
する４つの分割領域では、両方の配線層でｙ方向に配線
すると定める。このように、分割領域毎に各配線層の配
線方向を決定した後、定められた配線方向に従って各ネ
ットの配線パターンを決定する。すなわち、定められた
配線方向とは異なる方向に走行する配線パターンの発生
を抑制しながら配線パターン決定を行う。

【００３０】図３乃至図５は、本発明の配線パターン決
定方法により得られた配線パターンの具体例を示してい
る。図３は、第１の配線層（以下、第１層という）上の
配線７Ｘを実線で、第２の配線層（以下、第２層とい
う）上の配線７Ｙを破線で示している。ビアホール８
は、第１層上の配線７Ｘと第２層上の配線７とを接続す
るために設けられている。図４と図５は、それぞれ第１
層上の配線と第２層上の配線を別々に示したものであ
る。図４から判るように、ｙ方向の混雑した領域Ｒ２で
は、ｘｙ原則に従わずにｙ方向に配線パターンが形成さ
れている。また、図５から判るように、ｘ方向の混雑し
た領域Ｒ１では、ｘｙ原則に従わずにｘ方向に配線パタ
ーンが形成されている。

【００３１】次に、図６と図７を用いて、分割領域５毎
に各配線層の配線方向を決定するための基準について説
明する。つまり、ｘｙ原則を崩すか否かを決定するため
の基準を説明する。説明を具体的にするために、ある分
割領域５においてｘ方向が混雑する場合を考える。この
とき、ｘｙ原則を崩してｘ方向の配線容量を増加させる
ことにより、ｘｙ原則に従えば通過できなかった配線が
新たに通過可能となる。これを、ｘｙ原則を崩したこと
による”効能”と呼ぶ。しかし、一方では、ｘｙ原則を
崩すことにより、一部の配線パターンが分割領域をｙ方
向に通過できなくなる。これを、ｘｙ原則を崩したこと
による”副作用”と呼ぶ。本発明の配線パターン決定方
法は、上記の”効能”が”副作用”よりも大きい場合の
みｘｙ原則を崩すのを基本とする。

【００３２】図６（ａ）は、ある分割領域５において、
ｘｙ原則を用いて配線した場合の配線パターン決定結果
を示し、図６（ｂ）は、ｘｙ原則を崩し、両方の配線層
でｘ方向に配線した場合の配線パターン決定結果を示
す。図６（ａ）に示すように、分割領域５はｘ方向の配
線要求量が非常に多い領域である。この場合に、ｘｙ原
則に従って配線処理を行うと、この分割領域５を通過で
きないネット（Ｐ1−Ｐ1’、Ｐ2−Ｐ2’、Ｐ3−Ｐ3’）
が生じる。この場合、図６（ｂ）に示すように、ｘｙ原
則を崩して両方の配線層でｘ方向に配線すると、それら
３つのネットＰ1−Ｐ1’、Ｐ2−Ｐ2’、Ｐ3−Ｐ3’も、
その領域をｘ方向に通過できるようになるという”効
能”がある。しかし、これに対し、ネットＰ4−Ｐ4’が
その領域をｙ方向に通過できなくなるという”副作用”
がある。この例によると、”効能”（３本）が”副作
用”（１本）よりも大きいので、この分割領域５では両
方の配線層でｘ方向に配線すると定める。

【００３３】これに対し、”副作用”が大きい場合の例
を図７に示す。図７（ａ）に示すように、分割領域５は
ｘ方向の配線要求量が非常に多い領域である。この場
合、ｘｙ原則に従って配線処理を行うと、この分割領域
５を通過できないネット（Ｐ1−Ｐ1’、Ｐ2−Ｐ2’、Ｐ
3−Ｐ3’）が生じる。この場合、図７（ｂ）に示すよう
に、ｘｙ原則を崩して両方の配線層でｘ方向に配線する
と、３つのネットＰ1−Ｐ1’、Ｐ2−Ｐ2’、Ｐ3−Ｐ3’
がこの領域をｘ方向に通過できるという”効能”が得ら
れるが、５つのネットＰ4−Ｐ4’、Ｐ5−Ｐ5’、Ｐ6−
Ｐ6’、Ｐ7−Ｐ7’、Ｐ8−Ｐ8’が、その領域をｙ方向
に通過できなくなるという”副作用”が生ずる。この例
によると、”副作用”（５本）が”効能”（３本）より
も大きいので、この分割領域ではｘｙ原則に従って配線
すると定める。

【００３４】以上の例は、２つの配線層を有する回路基
板について説明したものであるが、以下に、２つ以上の
任意の数の配線層を有する回路基板に、本発明の配線パ
ターン決定方法を適用する場合の具体例について説明す
る。まず、２つの配線層を有する回路基板に対する処理
と同様に、配線領域を縦横に分割し、分割領域毎にｘ方
向要求本数とｙ方向要求本数を算出する。そして、これ
ら要求本数を用いて分割領域毎に各配線層の配線方向を
決定し、その配線方向に従って配線パターンを決定す
る。配線方向の決定においては、まず、考えられる複数
の候補を列挙し、その中から最適な候補をひとつ選択す
る。例えば、４層回路基板の場合、候補として １）ｘｘｘｘ（全層ともｘ方向）、 ２）ｘｘｘｙ（第１層、第２層、第３層はｘ方向、第４
層はｙ方向）、 ３）ｘｙｘｙ、 ４）ｘｙｙｙ、 ５）ｙｙｙｙ、 の５つを列挙し、この中から最適な候補を選択する。す
なわち、各候補についてｘ方向通過本数の増加量（”効
能”）とｙ方向通過本数の減少量（”副作用”）を調
べ、これらの差が最も大きい候補を採用する。すなわ
ち、 Ａ＝（当該候補のｘ方向通過本数−ｘｙ原則のｘ方向通過本数）− （ｘｙ原則のｙ方向通過本数−当該候補のｙ方向通過本数） ＝（当該候補のｘ方向通過本数＋当該候補のｙ方向通過本数）− （ｘｙ原則のｘ方向通過本数＋ｘｙ原則のｙ方向通過本数） で計算されるＡの値が最大となる候補を採用する。この
式で（ｘｙ原則のｘ方向通過本数＋ｘｙ原則のｙ方向通
過本数）の値は、候補によらず一定であるから、Ａが最
大である候補を採用するすることは、 Ａ’＝当該候補のｘ方向通過本数＋当該候補のｙ方向通
過本数 で計算されるＡ’の値が最大となる候補を採用すること
と同等である。さらに、当該分割領域を通過できない本
数を「超過本数」と呼ぶことにすると、 ｘ方向超過本数＝ｘ方向要求本数−ｘ方向通過本数、 ｙ方向超過本数＝ｙ方向要求本数−ｙ方向通過本数、 であるから、 Ａ’＝（ｘ方向要求本数＋ｙ方向要求本数）−（ｘ方向
超過本数＋ｙ方向超過本数） が成り立つ。この式で、（ｘ方向要求本数＋ｙ方向要求
本数）は候補によらず一定であるから、Ａが最大の候補
を採用するすることは、 Ａ”＝ｘ方向超過本数＋ｙ方向超過本数、 で計算されるＡ”の値が最小となる候補を採用すること
と同等である。

【００３５】以上説明したように、本発明の配線パター
ン決定方法によれば、局所的に特定の同一方向の配線要
求量が非常に多く、もしｘｙ原則に従って配線すれば配
線不能が生じるような場合にあっても、その局所を含む
分割領域の各配線層の配線方向が配線要求量の多い方向
に合わせて決定されるから高い配線率が達成できる。

【００３６】また、上記第２の目的を達成する本発明の
配線パターン決定方法によれば、配線層ごとに用意した
格子点テーブルの格子点ごとに、上記いずれかの方法で
決定された分割領域ごとの配線方向を設定し、この格子
点テーブルに従って各ネットに属する一のピンの格子点
から当該ネットに属する他のピンに至る経路を複数求
め、該求めた複数の経路のうち最短の経路を当該ネット
の配線経路として決定していることから、短い配線長で
配線パターンを自動的に決定できる。

【００３７】また、本発明の配線パターン決定方法によ
れば、配線経路探索処理に先立って最適な配線方向を決
定し、配線経路探索の処理では繰り返し改良処理の援用
を受けるまでもなく満足な配線結果が得られるので、コ
ンピュータにおいて常に実用的な計算時間で配線パター
ンの決定を行うことができる。

【００３８】また、本発明の配線パターン決定方法によ
れば、高い配線密度の配線パターンを有する回路基板が
実現できる。

【００３９】

【実施例】以下、本発明の配線パターン決定方法の実施
例を図を用いて説明する。 １．第１実施例 ここで、本発明の第１実施例を図１乃至図２３を用いて
詳細に説明する。

【００４０】（１）配線パターン決定システムの全体構
成 図１は、本発明が適用されてなる配線パターン決定シス
テムの全体構成図を示す。このシステムは、２層あるい
はそれ以上の配線層を有する回路基板を対象とした配線
パターン自動決定システムである。ここで、配線層上に
形成される配線パターンは、主として回路基板の横辺に
平行な方向（以下ｘ方向と呼ぶ）あるいは縦辺に平行な
方向（以下ｙ方向と呼ぶ）に走行するものとする。ま
た、配線領域内に配線格子が定義され、配線パターンは
この配線格子の上を走行するものとする。

【００４１】まず、図１を用いて本システムの全体構成
を説明する。本実施例の配線パターン決定方法は、コン
ピュータ９０に実装されたプログラムによって実現され
る。コンピュータ９０は、設計マスタファイル９６から
配線パターン決定に必要な情報を読み込み、配線パター
ンの決定処理をした後、その結果をファイル９６に返す
ようになっている。すなわち、設計マスタファイル９６
には、予め設計者によって作成された配線パターンを定
義した「配線パターン情報」、回路基板上で配線パター
ンの形成が禁止される領域（禁止領域）を定義した「禁
止情報」、配線パターン決定処理の対象となるネットを
定義した「ネット情報」、回路基板における配線領域や
配線層数などの仕様を定義した「基板情報」が格納され
ている。コンピュータ９０はそれらのうちの必要な情報
を読み込み、プログラムに従って配線パターン決定処理
を実行する。このプログラムにより、配線処理制御手段
９１、配線領域分割手段９２、配線方向決定手段９３、
及び配線パターン決定手段９４が構成される。

【００４２】配線処理制御手段９１は、配線領域分割手
段９２と、配線方向決定手段９３と、配線パターン決定
手段９４とを起動し、配線処理全体の制御を行う。

【００４３】配線領域分割手段９２は、配線領域を縦横
に分割し複数の分割領域を定義する。

【００４４】配線方向決定手段９３は、分割領域毎の各
配線層の配線方向を決定するもので、大きく分けて次の
処理を実行する処理９３１と処理９３２を含んで構成さ
れる。 処理９３１：各ネットを最短に配線するという仮定条件
の下で、各々の分割領域をｘ方向に通過すると予想され
る配線パターンの本数（ｘ方向要求本数）およびｙ方向
に通過する予想される配線パターンの本数（ｙ方向要求
本数）を算出する。 処理９３２：処理９３１で算出した要求本数を用いて、
分割領域毎に各配線層の配線方向を定める。

【００４５】配線パターン決定手段９４は、配線方向決
定手段９３によって定められた配線方向に基づき、各ネ
ットに対して迷路法による配線パターン決定処理を行う
ものであり、大きく分けて次の処理を実行する処理９４
１〜９４４と、格子点テーブル９４５及びコスト関数テ
ーブル９４６とを含んで構成されている。

【００４６】処理９４１：配線領域の全格子点を表現し
たテーブルである格子点テーブル９４５上に既配線パタ
ーン情報と禁止情報を展開する。つまり、既配線パター
ンの通過する全格子点および禁止領域の範囲内にある全
格子点に”使用済み”フラグを立てる。使用済みフラグ
の立った格子点は、新たに配線パターンとして使用する
ことが禁止される。

【００４７】処理９４２：迷路法による配線経路探索処
理で使用するコスト関数を格子点毎に定義する。コスト
関数とは、１つの格子点から順次隣接格子点を探索して
目的の格子点へ至る配線経路の長短及び適否を判断する
ための指標として定義したものであり、各格子点から隣
接格子点への探索に対して与えるコストを、探索方向の
関数として定義したものである。言い換えれば、定義さ
れたコストは、第１に配線経路の長さに相当する指標で
あり、探索格子点を１つ進むごとに所定のコストを加算
して長さを認識する。また、第２に配線層に設定された
分割領域ごとの配線方向に配線を走行させないようにす
るため、その方向の探索に対しては大きいコストを定義
することにより、自動的に不適切な配線経路であること
を認識させる。つまり、東方向（ｘの正方向）の隣接格
子点への探索、西方向（ｘの負方向）の隣接格子点への
探索、・・・、のそれぞれに対してコストの値を定義す
る。このコスト関数は、定められた配線方向を遮るよう
な方向の探索に対して大きなコストを与えるように定義
される。このために、たとえば、配線方向がｘ方向であ
る分割領域に含まれる格子点に対しては、ｘ方向の探索
には小さなコスト、ｙ方向の探索には大きなコストを与
ええるようにコスト関数を定義する。このようなコスト
関数を定義することにより、格子点毎にコスト関数を定
義するために、本実施例では、コスト関数の内容をコス
ト関数テーブル９４６に格納し、格子点テーブル９４５
の各格子点にはコスト関数の識別子を格納する。こうす
ることによりメモリ使用量が節約される。 処理９４３：コスト関数を用い、各ネットに対して迷路
法による配線経路探索処理を実行する。前述のように、
各々の格子点に対してコスト関数が定義されており、配
線経路探索処理では、格子点を通過する毎にこのコスト
関数の値を加算する処理を繰り返す。

【００４８】処理９４４：配線経路探索処理９４３が発
見した配線経路を配線パターンとして設計マスタファイ
ル９６に登録する。また、後続のネットの配線経路探索
処理のため、登録した配線パターンの通過する格子点
に”使用済み”フラグを立てる。

【００４９】次に、上記各手段９１，９２，９３，９４
の処理手順を具体的に説明する。 （２）配線処理制御手段９１ 図８に、配線処理制御手段９１の処理手順のフローチャ
ートを示し、各ステップ１０１〜１０７の処理内容を次
に説明する。

【００５０】ステップ１０１：配線領域分割手段９２を
起動し、配線領域の分割処理を実行させる。

【００５１】ステップ１０２：配線方向決定手段９３を
起動し、分割領域毎の各配線層の配線方向決定の処理を
実行させる。

【００５２】ステップ１０３：配線処理対象の配線層の
層ペアの番号ｉを初期値＝１とする。ここで、「層ペ
ア」とは、一体的に配線方向決定の対象となる隣接した
複数の配線層の組みをいい、例えば隣接した２つの配線
層の他、隣接した３つ又はそれ以上の配線層の組みを指
すものとする。

【００５３】ステップ１０４：配線パターン決定手段９
４を起動し、第ｉ層ペアにおいて、すべての未配線ネッ
トに対して配線パターン決定処理を試行させる。

【００５４】ステップ１０５：全ネットが結線されたな
ら配線処理を終了する。

【００５５】ステップ１０６：ｉを１だけ増加させる。

【００５６】ステップ１０７：ｉが層ペア数を越えない
ならば、ステップ１０４に戻る。そうでなければ配線処
理を終了する。

【００５７】（３）配線領域分割手段９２ 配線領域をｘ方向およびｙ方向に等分割する。分割の幅
は任意であるが、例えば両方向について２０の領域に等
分割する。このとき、分割して得られた領域はほぼ同面
積の矩形となる。

【００５８】（４）配線方向決定手段９３ この手段は前述したように、分割領域ごとに各配線方向
ｘ，ｙの要求本数を算出する処理９３１と、分割領域ご
とに各配線層の配線方向を決定する処理９３２とを含
む。これらの処理手順について、図９〜図１５を用いて
詳細に説明する。

【００５９】（４．１）分割領域毎に要求本数を算出す
る処理９３１ 本実施例における各配線方向ｘ，ｙの要求本数の算出の
基本的手順は、各ネットについて配線の仮想経路を定義
し、通過する仮想経路の本数を分割領域毎に計数するこ
とにより行う。しかし、配線経路の探索を実行する前に
正確に経路を予測するは困難であるから、最短距離を前
提条件として複数の仮想経路を準備し、それぞれの仮想
経路の実現可能性に相当する確率を付加することにす
る。なお、複数の仮想経路の確率の合計は１となる。し
たがって、各分割領域における要求本数は、仮想経路の
確率を加算した値として算出される。

【００６０】図９（ａ）、（ｂ）は上述した確率付き仮
想経路の例を示している。同図（ａ）はｘ方向あるいは
ｙ方向に平行なネットの仮想経路である。このようなネ
ットにの場合、始点ピンと終点ピンを結ぶ直線が最短の
仮想経路であり、この経路は１つのみであるから、確率
＝１を与える。同図（ｂ）と（ｃ）は、ｘ方向、ｙ方向
のいずれにも平行でないネットの仮想経路の例である。
本実施例では、折れ曲がり数が２以下の仮想経路に絞
り、それらをすべて仮想経路として列挙する。そして、
同図（ｂ）のように折れ曲がり数が１の場合と、同図
（ｃ）のように折れ曲がり数が２の場合とに、確率をそ
れぞれ０．５づづ配分する。したがって、同図（ｂ）の
折れ曲がり数が１である２つの仮想経路は２つ考えられ
るから、それぞれに０．２５の確率を与える。また、同
図（ｃ）の折れ曲がり数が２である仮想経路の採りうる
数は、ピン間の配線格子の数によって変わるが、図示例
では１０経路ある場合を示し、各仮想経路に対して残り
の確率０．５を均等配分して、それぞれに確率０．０５
を与える。

【００６１】図１０は、上記の確率に基づいて要求本数
の具体的な算出例を説明する図であり、折れ曲がり数が
２である仮想経路の１つが、どのように各分割領域の要
求本数に計数されるかを示している。前述したように、
この仮想経路の確率は０．０５であるから、仮想経路が
ｘ方向に通過する分割領域についてｘ方向要求本数に
０．０５が加算され、仮想経路がｙ方向に通過する分割
領域についてｙ方向要求本数に０．０５が加算される。
ここで、仮想経路がある分割領域をｘ方向に通過すると
は、仮想経路のｘ方向セグメントの少なくとも一部が、
その分割領域の内部あるいは境界の上に存在することで
あると定義する。また、仮想経路がある分割領域をｙ方
向に通過するとは、仮想経路のｙ方向セグメントの少な
くとも一部が、その分割領域の内部あるいは境界の上に
存在することと定義する。

【００６２】以上の要求本数の定義を数式で表せば次の
数１のようになる。つまり、分割領域（Ｉ，Ｊ）(但
し、Ｉ，Ｊはそれぞれ自然数である。)におけるｘ方向
要求本数Ｎx（Ｉ，Ｊ），ｙ方向要求本数Ｎy（Ｉ，Ｊ）
は、

【００６３】

【数１】 で定義される。ここで、 ｋ：ネット、 ｒ：ネットｋの仮想経路、 ｐr：仮想経路ｒの確率、 αr（Ｉ，Ｊ）：仮想経路ｒが分割領域（Ｉ，Ｊ）をｘ
方向に通過する場合は１、そうでない場合は０、 βr（Ｉ，Ｊ）：仮想経路ｒが分割領域（Ｉ，Ｊ）をｙ
方向に通過する場合は１、そうでない場合は０。

【００６４】以下、図１１のフローチャートを用いて、
上述した要求本数算出処理９３１の詳細手順を説明す
る。なお、本実施例では、要求本数を一旦算出した後、
配線混雑を平準化する改良処理を繰り返し行う。配線混
雑を平準化するとは、要求本数の多い領域を通過する仮
想経路の確率を小さくし、そうでない仮想経路の確率を
大きくすることにより、後述の実際の配線パターン決定
処理において、配線混雑の大きい領域を避けるように経
路が選択され、自然に配線混雑が平準化されるためであ
る。配線混雑を平準化する改良処理を繰り返すことによ
り、配線混雑の領域によるばらつきが次第に小さくな
る。もし改良処理を行ってもばらつきが変化がしなくな
ったら、改良処理の繰り返しを停止する。

【００６５】ステップ１２１：各ネットについて考えら
れる仮想経路を仮想経路群として求める。

【００６６】ステップ１２２：各分割領域ごとに、ｘ方
向要求本数およびｙ方向要求本数を算出する。

【００６７】ステップ１２３：ｘ方向要求本数の分割領
域間のばらつきσx（０）、およびｙ方向要求本数の分
割領域間のばらつきσy（０）を計算する。なお、この
ばらつきは標準偏差を意味するものである。

【００６８】ステップ１２４：何回目の改良処理かを示
す値ｊを１とする。

【００６９】ステップ１２５：第ｊ回目の改良処理を行
う。

【００７０】ステップ１２６：もし、要求本数のばらつ
きの変化が、予め定めた値よりも小さければ改良処理の
繰り返しを終了する。そうでなければステップ１２７へ
進む。

【００７１】ステップ１２７：ｊを１だけ増加させる。

【００７２】ステップ１２８：予め定めた上限値をｊの
値が越えなければステップ１２５に戻る。越えるならば
改良処理の繰り返しを終了する。

【００７３】ステップ１２５の詳細は下記の通りであ
る。

【００７４】ステップ１２５１：ネットを１つ選択す
る。

【００７５】ステップ１２５２：そのネットの仮想経路
の確率を変更する。この変更手順は、まず各仮想経路ｒ
について、通過する分割領域の要求本数の合計値Ｓrを
算出する。つまり、仮想経路ｒがある分割領域をｘ方向
に通過するなら、その分割領域のｘ方向要求本数を加算
し、一方、ｙ方向に通過するならｙ方向要求本数を加算
する。次に、各仮想経路についてθr／Ｓr の値を求め
る。ここで、θr は、仮想経路ｒの折れ曲がり数が２の
とき１の値をとり、折れ曲がり数が１のとき１より大き
い値をとる。最後に、θr／Ｓr の値に関して各仮想経
路に確率を比例配分する。この処理により、折れ曲がり
数が同一の仮想経路であれば、要求本数の合計Ｓr の値
が大きい仮想経路、すなわち混雑した分割領域を通過す
る仮想経路の確率が、そうでない仮想経路よりも小さく
定義される。つまり、θr はいわば重み係数であり、実
際に値を設定するにあたっては、繰返し処理を実行して
適切な値を選択することが望ましい。

【００７６】ステップ１２５３：ステップ１２５２で求
めた仮想経路の確率を用いて、各分割領域の要求本数を
前記数１により再計算する。

【００７７】ステップ１２５４：当該改良処理で未だ仮
想経路の確率の変更処理を行っていないネットがあるな
らばステップ１２５１にもどり、そうでなければ当該改
良処理を終了する。

【００７８】ステップ１２６の詳細は下記の通りであ
る。

【００７９】ステップ１２６１：ｘ方向要求本数の分割
領域間のばらつきσx（ｊ）、およびｙ方向要求本数の
分割領域間のばらつきσy（ｊ）を計算する。

【００８０】ステップ１２６２：もし、前回の改良処理
を終了した後の要求本数のばらつきσx（ｊ−１）およ
びσy（ｊ−１）と、σx（ｊ）およびσy（ｊ）の差が
いずれも予め定めた値δよりも小さければ改良処理を終
了する。そうでなければステップ１２７へ進む。

【００８１】（４．２）分割領域毎に各配線層の配線方
向を決定する処理９３２ ここで、図１２〜図１５を参照して、配線方向の決定処
理９３２を詳細に説明する。まず、基本的に、配線方向
の決定は、可能な考えられる候補を列挙した後、その中
から最適なもの採用する、という手順を踏んで行う。こ
れらの処理を順に述べる。

【００８２】図１２は、各配線層の配線方向の組合せ候
補を説明する図である。本実施例ではｘ方向とｙ方向の
配線のみを考えているから、分割領域における各層の配
線方向はｘ方向あるいはｙ方向のいずれかを採りうる。
本実施例では、特定方向の配線混雑がなければｘｙ原則
による配線を崩さないという考え方に基づき、ｘｙ原則
に従った配線方向を”標準配線方向”に定める。そし
て、この標準配線方向をベースにその他の配線方向の候
補を列挙する。

【００８３】図１２（ａ）、（ｂ）は、２層回路基板の
場合の配線方向の候補を示している。図（ａ）は、第１
層の標準配線方向をｘ方向、第２層の標準配線方向をｙ
方向と定めたときの３つの候補ｘｘ、ｘｙ、ｙｙを表し
ており、図（ｂ）は、第１層の標準配線方向をｙ方向、
第２層の標準配線方向をｘ方向と定めたときの３つの候
補ｘｘ、ｙｘ、ｙｙを表している。図１２（ｃ），
（ｄ）は、３層回路基板の場合の配線方向の候補を示し
ている。図（ｃ）２列目の候補ｘｙｘは、ｘ方向の配線
層が２つ、ｙ方向の配線層が１つであるような配線方向
ｘｘｙ、ｘｙｘ、ｙｘｘを代表するものであり、図
（ｄ）の候補ｘｙｙは、ｘ方向の配線層が１つ、ｙ方向
の配線層が２つであるような配線方向を代表している。
図１２（ｅ）、（ｆ）は４層回路基板の場合の配線方向
の組合せ候補を示している。

【００８４】次に、図１３を用いて、列挙した候補の中
から最適な配線方向を採用する方法を説明する。同図
（ａ）、（ｂ）は、５つの候補ｘｘｘｘ、ｘｘｘｙ、ｘ
ｙｘｙ、ｘｙｙｙ、ｙｙｙｙの中から最適な候補を選択
し、それを分割領域の配線方向として採用した例を示し
ている。本実施例の配線パターン決定システムでは、下
式で計算されるｘ方向超過本数とｙ方向超過本数の和が
最小の候補を採用する： ｘ方向要求本数≦ｘ方向配線容量ならば、 ｘ方向超過本数＝０、 ｘ方向要求本数＞ｘ方向配線容量ならば、 ｘ方向超過本数＝ｘ方向要求本数―ｘ方向配線容量、 ｙ方向要求本数≦ｙ方向配線容量ならば、 ｙ方向超過本数＝０、 ｙ方向要求本数＞ｙ方向配線容量ならば、 ｙ方向超過本数＝ｙ方向要求本数―ｙ方向配線容量． 但し、もし標準配線方向（この例ではｘｙｘｙ）のｘ方
向超過本数とｙ方向超過本数が共に０であれば、無条件
に標準配線方向を採用する。

【００８５】「配線容量」は、配線方向の候補毎に計算
する。分割領域をｘ方向に通過できる本数およびｙ方向
に通過できる本数が共に１層当たり５本であるとする
と、たとえば、図１３（ａ）の２番目の候補は、ｘ方向
の配線層を３つ、ｙ方向の配線層を１つ含むから、ｘ方
向配線容量＝５本×３＝１５本、ｙ方向配線容量＝５本
×１＝５本、と計算される。なお、もし当該分割領域に
既配線パターンあるいは禁止領域が存在する場合は、そ
れらにより配線パターンの通過が妨げられる本数を差し
引いた値を配線容量とする。

【００８６】図１３（ａ）に示される例では、候補ｘｘ
ｘｙが最小の超過本数を与えるので、これを当該分割領
域の配線方向として採用する。この配線方向ｘｘｘｙを
標準配線方向ｘｙｘｙと比較すると、ｘ方向通過本数が
１０本から１５本に増加しているので、ｘｙ原則を崩し
たことによる”効能”は５本である。一方、ｙ方向通過
本数は７本から５本に減少しているので、ｘｙ原則を崩
したことによる”副作用”は２本である。したがって、
差し引き３本の改善が得られている。図１３（ｂ）に示
される例では、標準配線方向ｘｙｘｙが最小の超過本数
を与えるので、これを配線方向として採用する。このと
き、ｘ方向について２本の超過が生じているが、それに
もかかわらず、ｘ方向の配線層が多い候補ｘｘｘｙ、ｘ
ｘｘｘが採用されないのは、ｘｙ原則を崩すことによ
る”副作用”が大きいためである。つまり、候補ｘｘｘ
ｙを採用すればｘ方向通過本数が１０本から１２本に増
加するが、ｙ方向通過本数が９本から５本に減少する。
また、候補ｘｘｘｙを採用すればｘ方向通過本数が１０
本から１２本に増加するが、ｙ方向通過本数が９本から
０本に減少する。

【００８７】次に、図１４のフローチャートに従って上
述の配線方向決定処理９３２の詳細手順を説明する。

【００８８】ステップ１５１：ｘｙ原則に従った配線方
向を標準配線方向と定める。４層板の場合、ｘｙｘｙあ
るいはｙｘｙｘを標準配線方向と定める。

【００８９】ステップ１５２：配線方向の候補を列挙す
る。

【００９０】ステップ１５３：分割領域を１つ選択す
る。

【００９１】ステップ１５４：各候補について、その分
割領域のｘ方向配線容量とｙ方向配線容量を算出する。

【００９２】ステップ１５５：各候補について、ｘ方向
超過本数とｙ方向超過本数を算出する。

【００９３】ステップ１５６：もし、標準配線方向のｘ
方向超過本数とｙ方向超過本数が共に０であればステッ
プ１５８へ進む。そうでなければステップ１５７へ進
む。

【００９４】ステップ１５７：ｘ方向超過本数とｙ方向
超過本数の和が最小である候補を、当該分割領域の配線
方向として採用する。

【００９５】ステップ１５８：当該分割領域の配線方向
として標準配線方向を採用する。

【００９６】ステップ１５９：配線方向が未決定である
分割領域があるならば、ステップ１５３に戻る。

【００９７】図１５は、２層回路基板に対して配線方向
の決定を行った例を示している。同図（ａ）は要求本数
の算出結果を表す。各分割領域５に対して、ｘ方向要求
本数（上段の数字）およびｙ方向要求本数（下段の数
字）が示されている。同図（ｂ）、（ｃ）、（ｄ）は、
それぞれ３つの候補について超過本数（ｘ方向超過本数
とｙ方向超過本数の和）を示している。すなわち、
（ｂ）標準配線方向（ｘｙ原則；第１層はｘ方向、第２
層はｙ方向）を採用した場合の超過本数、（ｃ）候補ｘ
ｘ（第１層、第２層ともｘ方向）を採用した場合の超過
本数、（ｄ）候補ｙｙ（第１層、第２層ともｙ方向）採
用した場合の超過本数。なお、分割領域をｘ方向に通過
できる本数およびｙ方向に通過できる本数は、共に１配
線層当たり５本である。

【００９８】図１５（ｂ）で超過本数が０と示された分
割領域については、配線方向を無条件に標準配線方向と
する。一方、図１５（ｂ）で超過本数が正の値を持つ７
つの分割領域については、どの候補が最適かを評価した
上で配線方向を決定する。たとえば、領域（４，２）に
おける超過本数は、標準配線方向のとき３．０、候補ｘ
ｘのとき１．４、候補ｙｙのとき８．０であり、候補ｘ
ｘのときの超過本数が最小であるから、候補ｘｘを採用
する。また、領域（４，３）における超過本数は、標準
配線方向のとき０．８、候補ｘｘのとき２．６、候補ｙ
ｙのとき５．８であり、標準配線方向のときの超過本数
が最小であるから、標準配線方向を採用する。他の５つ
の分割領域についても同様に配線方向を決定する。

【００９９】図１５（ｅ）、（ｆ）は、それぞれ決定さ
れた第１層６Ｘと第２層６Ｙの配線方向を示した図であ
り、図中太枠で囲まれた領域は、標準配線方向とは異な
る配線方向が割り当てられた領域を表す。

【０１００】（５）配線パターン決定手段９４ 配線パターン決定手段９４は、前記処理９３によって分
割領域毎に決定された配線方向を用いて、各々のネット
に対して迷路法による配線パターン決定処理を実行す
る。このとき、配線方向とは異なる方向へ走行する配線
パターンの発生を抑制しなければならない。このため、
本実施例の配線パターン決定システムでは、格子点毎に
コスト関数を定義し、このコスト関数を用いて配線経路
探索を行う。

【０１０１】以下、図１６〜図２５を用いて、配線パタ
ーン決定処理を詳細に説明する。

【０１０２】（５．１）格子点テーブル上に既配線パタ
ーンと禁止を展開する処理９４１ まず、配線領域の全格子点を表現したテーブルである図
１７の格子点テーブル９４５上に、図２１に示す具体例
のように、既配線パターン情報と禁止情報を展開する。
つまり、配線パターンの通過する全格子点および禁止領
域の範囲内にある全格子点に”使用済み”フラグを立て
る。

【０１０３】（５．２）格子点毎にコスト関数を定義す
る処理９４２ 次に、格子点テーブル９４５上の各格子点にコスト関数
を定義する。以下、この処理について図１６、図１７、
図１８、図１９を用いて説明する。

【０１０４】図１６は、コスト関数の定義方法の概念を
説明する図である。この図は、配線方向決定手段９３に
よって決定された配線方向（図１５（ｅ、ｆ））に従っ
てコスト関数を定義する方法を模式的に示している。コ
スト関数とは、隣接格子点への経路探索に対して与える
コストを定義するものであり、探索方向の関数として定
義され、図１６ではコストの小さい方向（すなわち配線
経路の探索をしやすい方向）のみを、一部の格子点につ
いて矢印で示すものである。

【０１０５】同図（ａ）に示すように、第１層６Ｘにお
ける領域Ａの配線方向はｙ方向であるから、ｙ方向の探
索に対して小さなコストを与える。ただし、領域Ａの上
辺および下辺の格子点Ｐ1、Ｐ2、Ｐ3、Ｐ4、Ｐ5、Ｐ6で
は、領域Ａの中へ向かう探索のみに小さなコストを与え
る。これは、もし、領域Ａの外へ向かう探索にも小さな
コストを与えると、領域Ａ外の領域におけるｘ方向の配
線が阻害されるためである。第１層における領域Ａ外の
領域の配線方向はｘ方向であるから、ｘ方向の探索に対
して小さなコストを与える。ただし、領域Ａに接する格
子点Ｐ7、Ｐ8、Ｐ9では、領域Ａから離れる方向のみに
小さなコストを与える。これは、もし、領域Ａの中へ向
かう探索にも小さなコストを与えると、領域Ａ内でのｙ
方向配線が阻害されるためである。

【０１０６】一方、同図（ｂ）に示すように、第２層６
Ｙにおける領域Ｂの配線方向はｘ方向であるから、ｘ方
向の探索に対して小さなコストを与える。ただし、領域
Ｂの左辺および右辺の格子点Ｐ10、Ｐ11、Ｐ12、Ｐ13で
は、領域Ｂの中へ向かう探索のみに小さなコストを与え
る。これは、もし、領域Ｂ外へ向かう探索にも小さなコ
ストを与えると、領域Ｂ外の領域でのｙ方向の配線が阻
害されるためである。第２層における領域Ｂ外の領域の
配線方向はｙ方向であるから、ｙ方向の探索に対して小
さなコストを与える。ただし、領域Ｂに接する格子点Ｐ
14、Ｐ15、Ｐ16、Ｐ17、Ｐ18、Ｐ19では、領域Ｂから離
れる方向のみに小さなコストを与えている。これは、も
し、領域Ｂの中へ向かう方向にも小さなコストを与える
と、領域Ｂ内でのｘ方向の配線が阻害されるためであ
る。

【０１０７】以上から、各格子点のコスト関数は、下記
６通りのいずれかとなる。

【０１０８】（１）Ｅ方向およびＷ方向がコスト小 （２）Ｎ方向およびＳ方向がコスト小 （３）Ｅ方向のみがコスト小 （４）Ｎ方向のみがコスト小 （５）Ｗ方向のみがコスト小 （６）Ｓ方向のみがコスト小 この６通りに基づいてコスト関数を定義した例を図１７
（ａ）に示す。同図に示すように、コスト関数テーブル
は、コスト関数の定義内容を格納するテーブルである。
６種類のコスト関数はコスト関数識別子１〜６によって
区別される。図１７（ｂ）は、コスト関数テーブル９４
６の中で用いられている方向の定義を示している。方向
Ｅ、Ｎ、Ｗ、Ｓ、ＮＥ、ＮＷ、ＳＷ、ＳＥは配線層６に
平行な方向であり、方向ＵおよびＤは配線層６に垂直な
方向である。方向Ｕは、配線層６に隣接した上方の配線
層へ向かう方向であり、方向Ｄは、配線層６に隣接した
下方の配線層へ向かう方向である。

【０１０９】識別子１のコスト関数は、ｘ方向が割り当
てられた領域の内部で使用するコスト関数である。ｘ方
向（Ｅ、Ｗ）に対するコストとしては小さな値が定義さ
れ、ｙ方向の成分をもつ方向（Ｎ、Ｓ、ＮＥ、ＮＷ、Ｓ
Ｗ、ＳＥ）に対するコストとしては大きな値が定義され
ている。このため、ｘ方向の領域の内部では、ｘ方向に
走行する配線パターンが形成されやすくなる。

【０１１０】識別子２のコスト関数は、ｙ方向の配線方
向が割り当てられた領域の内部で使用するコスト関数で
ある。ｙ方向（Ｎ、Ｓ）に対するコストとしては小さな
値が定義され、ｘ方向の成分をもつ方向（Ｎ、Ｓ、Ｎ
Ｅ、ＮＷ、ＳＷ、ＳＥ）に対するコストとしては大きな
値が定義されている。このため、ｙ方向の領域の内部で
は、ｙ方向に走行する配線パターンが形成されやすくな
る。

【０１１１】識別子３、４、５、６のコスト関数は、配
線方向の変化する境界で使用されるコスト関数である。
それぞれ、方向Ｅ、Ｎ、Ｗ、Ｓに対するコストのみが小
さな値を与えられている。

【０１１２】これらコスト関数識別子は、図１８に示し
たコスト関数定義処理９４２のフローチャートに従って
定義され、格子点テーブル９４５における各々の格子点
に設定される。以下、図１８の各ステップの処理につい
て説明する。

【０１１３】ステップ２８０１：配線層を１つ選択す
る。

【０１１４】ステップ２８０２：該配線層上の格子点を
１つ選択する。

【０１１５】ステップ２８０３：該格子点がｘ方向領域
内にあるならば、ステップ２８０４へ進む。一方、ｙ方
向領域内にあるならば、ステップ２８０５へ進む。

【０１１６】ステップ２８０４：該格子点のＥ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２８０６
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
８１２へ進む。

【０１１７】ステップ２８０５：該格子点のＮ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２８１３
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
８０７へ進む。

【０１１８】ステップ２８０６：該格子点のＷ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２８１０
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
８１１へ進む。

【０１１９】ステップ２８０７：該格子点のＳ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２８１４
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
８１５へ進む。

【０１２０】ステップ２８１０：識別子「１」のコスト
関数を該格子点のコスト関数とする。すなわち、格子点
テーブル９４５における該格子点の記憶領域にコスト関
数識別子「１」を設定する。

【０１２１】ステップ２８１１：識別子「３」のコスト
関数を該格子点のコスト関数とする。すなわち、格子点
テーブル９４５における該格子点の記憶領域にコスト関
数識別子「３」を設定する。

【０１２２】ステップ２８１２：識別子「５」のコスト
関数を該格子点のコスト関数とする。すなわち、格子点
テーブル９４５における該格子点の記憶領域にコスト関
数識別子「５」を設定する。

【０１２３】ステップ２８１３：識別子「６」のコスト
関数を該格子点のコスト関数とする。すなわち、格子点
テーブル９４５における該格子点の記憶領域にコスト関
数識別子「６」を設定する。

【０１２４】ステップ２８１４：識別子「４」のコスト
関数を該格子点のコスト関数とする。すなわち、格子点
テーブル９４５における該格子点の記憶領域にコスト関
数識別子「４」を設定する。

【０１２５】ステップ２８１５：識別子「２」のコスト
関数を該格子点のコスト関数とする。すなわち、格子点
テーブル９４５における該格子点の記憶領域にコスト関
数識別子「２」を設定する。

【０１２６】ステップ２８１６：コスト関数が未定義の
格子点が該配線層上にあるならば、ステップ２８０２に
戻る。そうでなければ、ステップ２８１７へ進む。

【０１２７】ステップ２８１７：コスト関数が未定義の
配線層があるならば、ステップ２８０１に戻る。そうで
なければ、コスト関数定義処理を終了する。

【０１２８】図１９（ａ）、（ｂ）は、それぞれ図１５
（ｅ）、（ｆ）に示された配線方向に基づき、図１８の
手順に従って格子点テーブル９４５にコスト関数識別子
を設定した結果を表している。同図（ａ）は、第１層６
Ｘに対応する格子点テーブルの記憶域の内容を示し、同
図（ｂ）は、第２層６Ｙに対応する格子点テーブルの記
憶域の内容を示している。それらの図において、小さな
枡目がそれぞれ１つの格子点に対応する記憶域を表す。
また、同図で太枠で囲まれた領域は標準配線方向（つま
りｘｙ原則に従った配線方向）とは異なる配線方向が割
り当てられた領域を表す。コスト関数識別子１は、ｘ方
向の領域に含まれる格子点に設定されている。識別子２
は、ｙ方向の領域に含まれる格子点に設定されている。
識別子３、４、５、６は、ｘ方向の領域とｙ方向の領域
の境界にある格子点に設定されている。

【０１２９】識別子３のコスト関数は、ｘ方向の領域か
らｙ方向の領域へ経路が進入するのを防止するために用
いられる。たとえば、第１層９４５Ｘにおいて太枠で囲
まれた領域はｙ方向の領域であるが、この領域に隣接し
てＥの方向にある格子点に識別子３が設定されている。
また、第２層９４５Ｙにおいて太枠で囲まれた領域はｘ
方向の領域であるが、この領域中で最もＷの方向にある
格子点に識別子３が設定されている。このように識別子
３を境界に設定することにより、方向Ｗ、すなわちｘ方
向の領域からｙ方向の領域へ向かう方向の探索が行われ
にくくなる。識別子５のコスト関数も、ｘ方向の領域か
らｙ方向の領域へ経路が進入するのを防止するために用
いられるが、識別子３のコスト関数と異なり、方向Ｅの
進入を防止する機能を持つ。一方、識別子４および６の
コスト関数は、ｙ方向の領域からｘ方向の領域へ経路が
進入するのを防止するために用いられ、それぞれ方向Ｓ
および方向Ｎに経路が進入することを防止する機能を持
つ。

【０１３０】（５．３）配線経路探索処理９４３ 設定されたコスト関数を用いて各ネットに対する配線経
路探索を行う。以下、図２０により配線経路探索処理９
４３の詳細手順を説明する。後述の説明から明らかにな
るように、本実施例の配線経路探索処理は、通常の迷路
法に比較し、格子点毎にコスト関数を切り替えるという
特徴を有する。

【０１３１】格子点テーブルにおける各格子点の記憶域
は、 1) 使用済みフラグ（格子点が使用済みか否かを示
す）、2) 探索フラグ（格子点が探索済みか否かを示
す）、3) 始点フラグ（始点ピン上の格子点か否かを示
す）、4) 終点フラグ（終点ピン上の格子点か否かを示
す）、5) 累積コスト、6) 入射方向（どの方向から当該
格子点へ探索が達したかを示す）、7) コスト関数識別
子、の各情報を有する。

【０１３２】「使用済みフラグ」は、その格子点上に配
線パターンが既に存在する格子点、および禁止領域に含
まれる格子点に設定する。「探索フラグ」は、既に探索
が達した格子点に設定する。「累積コスト」とは、隣接
格子点への探索に対するコストを始点から累積した値で
ある。隣接格子点への探索に対するコストの値はコスト
関数により定義される。「入射方向」は、配線経路探索
処理の”足跡”を示すものであり、後述する配線経路登
録におけるバックトレース処理で使用される。「コスト
関数識別子」は、（５．２）で述べた通り、当該格子点
からの探索に対するコスト関数を定義する。

【０１３３】本実施例の配線経路探索処理においては波
面リストを使用する。「波面」とは探索の最前面を意味
し、波面リストとは波面に属する格子点を格納するリス
トである。配線経路探索処理は、このテーブルから最小
の累積コストをもつ格子点を１つ取り出し、その格子点
から隣接格子点へ探索を広げるという処理を繰り返すこ
とにより行われる。

【０１３４】ステップ１９１：始点の格子点を波面リス
トに登録する。

【０１３５】ステップ１９２：波面リストから最小の累
積コストをもつ格子点を１つ取り出す。

【０１３６】ステップ１９３：方向を１つ選択し、それ
をｄとする。

【０１３７】ステップ１９４：方向ｄへの探索が許され
るか否かにより、次に行う処理が分かれる。すなわち、
ステップ１９４１：方向ｄの探索の行き先が配線領域か
らはみ出すならば、方向ｄへの探索１９５をスキップす
る（ステップ１９６へ進む）。そうでなければ、ステッ
プ１９４２へ進む。

【０１３８】ステップ１９４２：方向ｄがＵまたはＤで
あるならば、ステップ１９４３へ進む。そうでなけれ
ば、ステップ１９５１へ進む。

【０１３９】ステップ１９４３：現格子点（ステップ１
９２で取り出した格子点）がビアホール設置不可なら
ば、方向ｄへの探索１９５をスキップする（ステップ１
９６へ進む）。そうでなければ、ステップ１９５１へ進
む。

【０１４０】ステップ１９５：方向ｄにある隣接格子点
への探索処理を行う。

【０１４１】ステップ１９５の詳細手順は下記の通りで
ある。

【０１４２】ステップ１９５１：探索先格子点（すなわ
ち方向ｄにある隣接格子点）が終点でなく、かつ使用済
みならば、ステップ１９６へ進む。使用済みでなければ
ステップ１９５２へ進む。

【０１４３】ステップ１９５２：方向ｄの隣接格子点へ
の探索に対するコストの値ΔＣを求める。すなわち、格
子点テーブルを参照してコスト関数識別子を求めた後、
コスト関数テーブルを参照してΔＣの値を求める。

【０１４４】ステップ１９５３：現格子点に格納されて
いる累積コストにΔＣを加えた値を計算し、その値をＣ
とする。

【０１４５】ステップ１９５４：探索先格子点が未探索
ならばステップ１９５５へ進む。そうでなければステッ
プ１９５７へ進む。

【０１４６】ステップ１９５５：探索先格子点に累積コ
ストとしてＣの値を設定する。また、入射方向としてｄ
を設定する。

【０１４７】ステップ１９５６：探索先格子点を波面リ
ストに登録する。但し、探索格子点が終点である場合は
登録しない。

【０１４８】ステップ１９５７：探索先格子点に設定さ
れている累積コストの値よりもＣの値が小さければ、ス
テップ１９５８へ進む。そうでなければステップ１９６
へ進む。

【０１４９】ステップ１９５８：探索先格子点に累積コ
ストとしてＣの値を設定する。また、入射方向としてｄ
を設定する。

【０１５０】ステップ１９６：未探索の方向があれば、
ステップ１９３に戻る。そうでなければ、当該格子点か
らの探索処理を終了しステップ１９７へ進む。

【０１５１】ステップ１９７：波面リストに格子点が存
在すればステップ１９２に戻る。そうでなければ配線経
路探索処理を終了する。

【０１５２】（５．４）配線経路登録処理９４４ 前述の配線経路探索処理９４３の結果を用いて配線経路
の登録処理を行う。すなわち、格子点テーブル９４５に
設定されている入射方向を逆向きにトレースことによ
り、終点から始点までの配線経路を確定し、それを設計
マスタファイルに登録する。以下、図２１により配線経
路登録処理９４４の詳細手順を説明する。

【０１５３】ステップ２０１：終点の格子点のうち、最
小の累積コストをもつ格子点を選択する。

【０１５４】ステップ２０２：その格子点の座標を記録
する。

【０１５５】ステップ２０３：その格子点に使用済みフ
ラグを立てる。

【０１５６】ステップ２０４：その格子点が始点である
ならばステップ２０６へ進む。そうでないならばステッ
プ２０５へ進む。

【０１５７】ステップ２０５：その格子点に設定されて
いる方向の逆方向にある隣接格子点を求め、ステップ２
０２に戻る。

【０１５８】ステップ２０６：記録した格子点の列を線
分データに変換する。

【０１５９】ステップ２０７：配線パターンとして、そ
の線分データを設計マスタファイルファイル９６に登録
する。

【０１６０】（配線経路探索を実行した具体例）ここ
で、配線経路探索処理９４３に従って配線経路探索を実
行した具体例を、図２２〜図２４により説明する。図２
２（ａ）、（ｂ）は、配線経路探索処理９４３を実行す
る前の第１層６Ｘと第２層６Ｙの状態を示している。第
１層６Ｘでは、始点ピン３Ｓと終点ピン３Ｔ間に禁止領
域１０が存在する。これに合わせて、図２３に示す格子
点テーブル９４５には、始点フラグＳ、終点フラグＴ、
使用済みフラグ＊、コスト関数識別子が設定格納されて
いる。図２３（ａ）は第１層６Ｘに対応する記憶域であ
り、図２３（ｂ）は第２層６Ｙに対応する記憶域であ
る。小さい枡目は、１つの格子点に対応する記憶域を表
す。第１層６Ｘの配線方向は全領域ｘ方向であり、第２
層６Ｙの配線方向は、太枠で囲まれた領域Ｒ１を除いて
ｙ方向である。領域Ｒ１の配線方向はｘ方向である。

【０１６１】図２４は、配線経路探索処理を実行した後
に、格子点テーブルの各格子点に設定されている累積コ
スト（上段の数字）および入射方向（下段の矢印及び
Ｕ，Ｄ。探索がこの入射方向の方向から当該格子点へ達
したことを意味する）を示している。この例では、簡単
のため直交方向（Ｅ、Ｎ、Ｗ、Ｓ）および垂直方向
（Ｕ、Ｄ）のみを使用して配線経路を探索した結果が示
されている。この図から、終点に累積コストが１５であ
るような配線経路が到達したことが判る。

【０１６２】（配線経路登録処理の実行例）ここで、配
線経路登録処理９４４に従って配線経路登録処理を実行
した具体例を、図２４および図２５を用いて説明する。

【０１６３】図２４に示した配線経路探索処理９４３の
結果に対して、終点を起点としてトレース処理を行う。
まず、終点には入射方向Ｅが設定されているから、Ｅの
逆方向すなわち方向Ｗにある隣接格子点を求める。この
結果、累積コストが１４である格子点にトレースが達す
る。次に、この格子点に設定されている入射方向を求め
（Ｅ）、この逆方向Ｗにある隣接格子点を求める。この
結果、累積コストが１３である格子点にトレースが達す
る。以下、同様にして始点に達するまでトレースを続け
ることにより、終点から始点に至る格子点の列、１５、
１４、１３、１２（以上、第１層）、９、８、７、６、
５（以上、第２層）、２、１、０（以上、第１層）を得
る。

【０１６４】図２５に、上記トレース処理の結果得られ
た配線パターンを示す。図から判るように、第１層６Ｘ
と第２層６Ｙの配線７Ｘと配線７Ｙを接続するために、
ビアホール８が設けられている。

【０１６５】上述した本実施例によれば、次のような効
果がある。まず、基本的に、配線領域を複数の分割領域
に分け、それぞれの分割領域ごとに配線要求の混雑の程
度を判断して、分割領域ごとに複数の配線層の配線方向
を決定し、これに基づいて各ネットの配線経路を決定す
るようにしていることから、局所的に特定の配線方向が
混雑する場合に、その混雑を効果的に緩和して、高配線
率で配線パターンを決定できる。

【０１６６】また、配線パターン決定を迷路法に基づて
行うので、高い配線率が達成できるという効果がある。
しかも、迷路法を適用するにあたり、格子点テーブルを
設け、コスト関数を定義して探索処理を実行するように
していることから、短い配線長の配線経路を探索できる
とともに、コンピュータによる現実的な処理を容易に実
現できる。

【０１６７】また、本実施例によれば、分割領域毎の配
線方向を決定する際、まず標準配線方向を設定し、標準
配線方向からの変更の極力少ない配線方向を列挙し、そ
の中から配線方向を採用するので、例えば、ある分割領
域の配線方向はｘｙ、ある分割領域の配線方向はｙｘと
いうように定義されることが防止される。同様に、ある
分割領域の配線方向はｘｘｘｙ、ある分割領域の配線方
向はｘｙｘｘというように定義されることが防止され
る。よって、各々の配線層においては配線方向の変化が
少ないので、きれいな配線パターンが得られるという効
果がある。

【０１６８】また、各分割領域における要求本数を算出
する際、繰り返し改良処理により精度良く配線混雑状況
を予測し、真にｘｙ原則を崩す必要のある領域のみｘｙ
原則を崩すことにするので、異なる配線層上を平行に配
線パターンが走行することが最小限に抑制され、層間ク
ロストークノイズの発生が防止されるという効果があ
る。

【０１６９】また、本実施例の配線パターン決定システ
ムによって決定された配線パターンは、下記の特徴を有
する。

【０１７０】（ａ）配線領域を縦横に分割するので、各
々の分割領域は矩形となる。各々の矩形の分割領域につ
いて配線方向が定められるので、回路基板に配線パター
ンが形成されたとき、同一の配線層でありながら、周囲
の領域とは配線の走行方向が異なる矩形の領域が認識さ
れる。

【０１７１】（ｂ）配線領域を十分に細かく分割すれ
ば、矩形内にすべてのピンが含まれるネットの数よりも
該矩形の成す境界を通過する配線パターンの数の方が大
きくなる。

【０１７２】なお、上記実施例により決定された配線パ
ターンを有する回路基板を形成すると、上下に重なる配
線層間で、同一方向に平行に配線が走行する領域が生ず
る。このような平行配線は層間クロストーク等によるノ
イズが問題になる。そこで、このような問題を解決する
ため、図２６に示すように、隣合う配線層６の間にグラ
ンド層Ｇおよび電源層Ｖ等の導電性を有する層を挿入す
ることが好ましい。これによれば、グランド層Ｇ又は電
源層Ｖ等によりり、異なる配線層の上を平行して走行す
る配線パターン相互が遮蔽されるため、それらの間で誘
導されるノイズ（層間クロストーク）を低減することが
できる。なお、グランド層Ｇおよび電源層Ｖは、ピン
３、ビアホール８が貫く部分を除いて、全面に導電性の
パターンを形成している。また、ピン３は全ての層を貫
通し、ビアホール８は、グランド層あるいは電源層をは
さんで隣接する２つの配線層６を貫通する。

【０１７３】２．他の実施例 （２．１）第１の変形例 上記第１実施例では、各分割領域の配線方向を決定する
処理９３２において、要求本数から配線容量を引いた値
を「超過本数」と定義しているが、現実には物理的な配
線容量をすべて配線パターンとして使用することは困難
である。このため、超過本数を下式のように定義して用
いてもよい。

【０１７４】 ｘ方向要求本数≦ｋ1×ｘ方向配線容量ならば、 ｘ方向超過本数＝０、 ｘ方向要求本数＞ｋ1×ｘ方向配線容量ならば、 ｘ方向超過本数＝ｘ方向要求本数―ｋ1×ｘ方向配線容
量、 ｙ方向要求本数≦ｋ2×ｙ方向配線容量ならば、 ｙ方向超過本数＝０、 ｙ方向要求本数＞ｋ2×ｙ方向配線容量ならば、 ｙ方向超過本数＝ｙ方向要求本数―ｋ2×ｙ方向配線容
量．（ｋ1およびｋ2は定数）ｋ1およびｋ2 の値とし
て、たとえば０．８を用いる。

【０１７５】このように超過本数を定義することによ
り、配線混雑度を精度良く予想できるので、より短い配
線長の配線パターンを決定でき、また、より高い配線率
を達成できるという効果がある。

【０１７６】（２．２）第２の変形例 上記第１実施例では、分割領域毎に超過本数を計算して
いるが、超過した配線パターンは、その分割領域を迂回
して配線されるかあるいは未配線となる。しかし、ネッ
トにより、信号伝播時間の余裕が小さいため配線パター
ンの迂回が許されないものがあるから、上記実施例のよ
うに”本数”という形で全ネットを同列に扱わずに、ネ
ットの重要度により重みを与えることは有用である。た
とえば、信号伝播時間の余裕の大小などから許容迂回長
をネット毎に定め、許容迂回長の小さい順序で配線処理
が行われると仮定して、超過すると予想されるネットを
求める。そして、これらのネットを、それぞれ許容迂回
長の大小に応じてｑ本（ｑは１に等しいか１より大）と
計数することにより、重み付けられた超過本数を算出す
る。

【０１７７】このように超過本数を定義することによ
り、信号伝播時間や電気的特性などの観点から重要と考
えられるネットを短い配線長で結線できるので、信号伝
播特性あるいは電気的特性の優れた配線パターンが得ら
れるという効果がある。

【０１７８】（２．３）第３の変形例 上記第１実施例では、回路基板の横辺に平行な方向（ｘ
方向）あるいは縦辺に平行な方向（ｙ方向）に配線パタ
ーンが走行するものと仮定しているが、配線パターンの
走行する方向として斜め方向を含むような回路基板であ
ってもよい。

【０１７９】図２７は、４つの配線層を有する回路基板
において、斜め方向をも含む４つの方向を用いて最適な
配線方向を決定する方法を示している。同図（ａ）は、
その４つの方向の定義を示している。同図（ｂ）は、配
線方向の候補の一部を示している。上述の実施例と同様
の処理により、これらの候補の中から最適な配線方向を
求め、さらにその配線方向に基づいてコスト関数を適切
に定義した後、コスト関数に従って各ネットの配線パタ
ーンを決定する。

【０１８０】この変形例によれば、直交方向のみならず
斜め方向も使用できるので、配線長をより短縮できると
いう効果がある。

【０１８１】（２．４）第４の変形例 上記第１実施例では、ネットを２つのピンからなるもの
と仮定して説明したが、３つ以上のピンから成るネット
についても、要求本数算出処理９３１に若干の変更を加
えることにより扱える。つまり、ネットに対する配線条
件（たとえば、一筆書き、スタイナ木、スパンニング木
等）に応じてにいくつかの仮想経路を定め、それぞれの
仮想経路に適当な確率を与えることにすれば、上記実施
例に示した処理手順によって要求本数を算出できる。

【０１８２】（２．５）第５の変形例 上記第１実施例では、要求本数の算出処理９３１におい
て配線混雑の平準化が行われるが、配線方向の決定に伴
う配線容量の変化が考慮されていない。つまり、上記実
施例の要求本数算出処理では、配線混雑の平準化のため
に各仮想経路の確率を変更するとき、どの程度混雑した
領域を各仮想経路が通過するかを示す指標として、分割
領域の要求本数を用いているが、厳密に言えば、配線層
の配線方向により配線混雑の度合いは異なるはずであ
る。たとえば、配線方向がｘｙｘｙである分割領域と、
配線方向がｘｘｘｙである分割領域とでは、たとえ要求
本数が等しくても配線混雑の度合いが異なる。

【０１８３】そこで、配線方向決定処理９３２の実行
後、その結果を用いて要求本数の算出処理９３１を再度
行うことにすれば、より高い精度の要求本数を算出でき
る。すなわち、各仮想経路の確率を変更するとき、どの
程度混雑した領域を各仮想経路が通過するかを示す指標
として、たとえば要求本数から配線容量を減じた値を用
いればよい。

【０１８４】このように、配線方向決定結果を要求本数
算出処理にフィードバックさせることにより、配線混雑
をより精度よく見積り、最適に配線方向を決定すること
を可能とするので、より短い配線長の配線パターンを決
定でき、また、より高い配線率が達成できるという効果
がある。

【０１８５】（２．６）第６の変形例 上述したように、本発明は、局所混雑を考慮して領域毎
に配線方向を決定する処理と、その決定された配線方向
に従って配線パターンを決定する処理とから成ってい
る。このうち、配線パターン決定処理について、前記各
実施例では、配線経路探索処理における”コスト関数”
を適切に定めることにより実現している。すなわち、決
定された配線方向に平行な方向に小さなコストを与え、
その方向の配線をしやすくすることにより、適切な配線
パターンの決定を実現している。しかし、この配線パタ
ーン決定処理は、”探索方向”を適切に制限することに
よっても実現できる。すなわち、ｘ方向配線領域内の格
子点についてはｙ方向の探索を禁止し、ｙ方向配線領域
内の格子点についてはｘ方向の探索を禁止するようにす
ることによっても実現できる。

【０１８６】図２８は、各配線層の各格子点について、
それぞれ探索禁止方向を定義する処理を示している。以
下に示すように、定義した探索禁止方向は、識別子の形
で格子点テーブルに格納する。配線経路探索処理におい
ては、この識別子を参照して探索禁止方向を認識し、探
索可能な方向のみに対して探索を行う。

【０１８７】ステップ２９０１：配線層を１つ選択す
る。

【０１８８】ステップ２９０２：該配線層上の格子点を
１つ選択する。

【０１８９】ステップ２９０３：該格子点がｘ方向領域
内にあるならば、ステップ２９０４へ進む。一方、ｙ方
向領域内にあるならば、ステップ２９０５へ進む。

【０１９０】ステップ２９０４：該格子点のＥ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２９０６
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
９１２へ進む。

【０１９１】ステップ２９０５：該格子点のＮ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２９１３
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
９０７へ進む。

【０１９２】ステップ２９０６：該格子点のＷ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２９１０
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
９１１へ進む。

【０１９３】ステップ２９０７：該格子点のＳ方向隣接
格子点がｘ方向領域内にあるならば、ステップ２９１４
へ進む。一方、ｙ方向領域内にあるならば、ステップ２
９１５へ進む。

【０１９４】ステップ２９１０：Ｎ、Ｓ方向を探索禁止
とする。格子点テーブル９４５における該格子点の記憶
領域に識別子「１」を設定する。

【０１９５】ステップ２９１１：Ｎ、ＮＷ、Ｗ、ＳＷ、
Ｓ方向を探索禁止とする。格子点テーブル９４５におけ
る該格子点の記憶領域に識別子「３」を設定する。

【０１９６】ステップ２９１２：Ｎ、ＮＥ、Ｅ、ＳＥ、
Ｓ方向を探索禁止とする。格子点テーブル９４５におけ
る該格子点の記憶領域に識別子「５」を設定する。

【０１９７】ステップ２９１３：Ｗ、ＮＷ、Ｎ、ＮＥ、
Ｅ方向を探索禁止とする。格子点テーブル９４５におけ
る該格子点の記憶領域に識別子「６」を設定する。

【０１９８】ステップ２９１４：Ｗ、ＳＷ、Ｓ、ＳＥ、
Ｅ方向を探索禁止とする。格子点テーブル９４５におけ
る該格子点の記憶領域に識別子「４」を設定する。

【０１９９】ステップ２９１５：Ｗ、Ｅ方向を探索禁止
とする。格子点テーブル９４５における該格子点の記憶
領域に識別子「２」を設定する。

【０２００】ステップ２９１６：探索禁止方向が未定義
の格子点が該配線層上にあるならば、ステップ２９０２
に戻る。そうでなければ、ステップ２９１７へ進む。

【０２０１】ステップ２９１７：探索禁止方向が未定義
の配線層があるならば、ステップ２８０１に戻る。そう
でなければ、探索禁止方向の定義処理を終了する。

【０２０２】さて、配線経路探索では、探索を進める毎
に、各探索に定義されたコストを積算していく。本変形
例では、ｘ方向およびｙ方向に同一の値を定義したコス
ト関数、例えばＥ方向：１、Ｎ方向：１、Ｗ方向：１、
Ｓ方向：１、ＮＥ方向：６、ＮＷ方向：６、ＳＷ方向：
６、ＳＥ方向：６、Ｕ方向：３、Ｄ方向：３として定義
する。

【０２０３】以下、図２９により配線経路探索処理の詳
細手順を説明する。本手順は、先に説明した図１８のフ
ローチャートとほぼ同一であるが、探索禁止方向を参照
する処理（ステップ３０４４）が追加されている点が異
なる。以下、各ステップの処理内容を説明する。

【０２０４】ステップ３０１：始点の格子点を波面リス
トに登録する。

【０２０５】ステップ３０２：波面リストから最小の累
積コストをもつ格子点を１つ取り出す。

【０２０６】ステップ３０３：方向を１つ選択し、それ
をｄとする。

【０２０７】ステップ３０４１：方向ｄの探索の行き先
が配線領域からはみ出すならば、方向ｄへの探索３０５
をスキップする（ステップ３０６へ進む）。そうでなけ
れば、ステップ３０４２へ進む。

【０２０８】ステップ３０４２：方向ｄがＵまたはＤで
あるならば、ステップ３０４３へ進む。そうでなけれ
ば、ステップ３０４４へ進む。

【０２０９】ステップ３０４３：現格子点（ステップ３
０２で取り出した格子点）がビアホール設置不可なら
ば、方向ｄへの探索３０５をスキップする（ステップ３
０６へ進む）。そうでなければ、ステップ３０４４へ進
む。

【０２１０】ステップ３０４４：方向ｄが探索禁止なら
ば、方向ｄへの探索３０５をスキップする（ステップ３
０６へ進む）。そうでなければ、ステップ３０５１へ進
む。

【０２１１】ステップ３０５：方向ｄにある隣接格子点
への探索処理を行う。

【０２１２】ステップ３０６：未探索の方向があれば、
ステップ３０３に戻る。そうでなければ、当該格子点か
らの探索処理を終了しステップ３０７へ進む。

【０２１３】ステップ３０７：波面リストに格子点が存
在すればステップ３０２に戻る。そうでなければ配線経
路探索処理を終了する。

【０２１４】ステップ３０５の詳細手順は下記の通りで
ある。

【０２１５】ステップ３０５１：探索先格子点（すなわ
ち方向ｄにある隣接格子点）が終点でなく、かつ使用済
みならば、ステップ３０６へ進む。使用済みでなければ
ステップ３０５２へ進む。

【０２１６】ステップ３０５２：方向ｄの隣接格子点へ
の探索に対するコストの値ΔＣを求める。すなわち、格
子点テーブルを参照してコスト関数識別子を求めた後、
コスト関数テーブルを参照してΔＣの値を求める。

【０２１７】ステップ３０５３：現格子点に格納されて
いる累積コストにΔＣを加えた値を計算し、その値をＣ
とする。

【０２１８】ステップ３０５４：探索先格子点が未探索
ならばステップ３０５５へ進む。そうでなければステッ
プ３０５７へ進む。

【０２１９】ステップ３０５５：探索先格子点に累積コ
ストとしてＣの値を設定する。また、入射方向としてｄ
を設定する。

【０２２０】ステップ３０５６：探索先格子点を波面リ
ストに登録する。但し、探索格子点が終点である場合は
登録しない。

【０２２１】ステップ３０５７：探索先格子点に設定さ
れている累積コストの値よりもＣの値が小さければ、ス
テップ３０５８へ進む。そうでなければステップ３０６
へ進む。

【０２２２】ステップ３０５８：探索先格子点に累積コ
ストとしてＣの値を設定する。また、入射方向としてｄ
を設定する。

【０２２３】本変形例によれば、配線方向を横切る方向
の探索を禁止するので、配線方向を横切るパターンの発
生を完全に防止できるという効果がある。

【０２２４】

【発明の効果】以上説明したように、本発明の配線パタ
ーン決定方法によれば、特定方向の配線要求量が多く、
ｘｙ原則に従って配線すれば未配線が生じるような場合
にあっても、分割領域の各々において、できるだけ多く
の配線を収容できるように各配線層の配線方向を決定す
るので、高い配線率を達成できるという効果がある。

【０２２５】また、本発明の配線パターン決定方法によ
れば、ある領域に特定方向の配線要求が集中し、ｘｙ原
則に従って配線すれば一部の配線が迂回しなければなら
ない場合であっても、その領域に含まれる分割領域の各
々において、できるだけ多くの配線が通過できるように
各配線層の配線方向を決定するので、短い配線長の配線
パターンを決定できるという効果がある。

【０２２６】また、本発明の配線パターン決定方法によ
れば、配線経路探索処理に先だって最適に配線方向を決
定するため、配線経路探索の処理では繰り返し改良処理
の援用を受けるまでもなく満足な配線結果が得られるの
で、コンピュータにおいて常に実用的な計算時間で配線
パターンの決定を行うことができるという効果がある。

【図面の簡単な説明】

【図１】本発明の第１実施例に係る配線パターン決定シ
ステムの全体構成を示すブロック図である。

【図２】本発明の配線パターン決定方法により局所混雑
が緩和されるネットの具体例を示す図である。

【図３】本発明の配線パターン決定方法により定められ
た配線方向に従って決定された配線パターンの一例を示
す図であり、図２の局所混雑が緩和されることを示して
いる。

【図４】図３の第１層の配線パターンを示す図である。

【図５】図３の第２層の配線パターンを示す図である。

【図６】配線方向を決定するための基準である効能の方
が副作用よりも大きい場合の例を説明する図であり、同
図（ａ）はｘｙ原則に従って配線する場合を示し、同図
（ｂ）は分割領域の２つの配線層で共にｘ方向に配線し
た場合を示す図である。

【図７】配線方向を決定するための基準である副作用の
方が効能よりも大きい場合の例を説明する図であり、同
図（ａ）はｘｙ原則に従って配線する場合を示し、同図
（ｂ）は分割領域の２つの配線層で共にｘ方向に配線し
た場合を示す図である。

【図８】配線処理制御手段の処理手順を示すフローチャ
ートである。

【図９】要求本数の算出処理に係る仮想経路の確率を説
明するための図であり、同図（ａ）は一組みのピンを結
ぶ線が標準配線方向に平行な場合の例、同図（ｂ）と
（ｃ）は折れ曲がり数が２以下である経路をすべて仮想
経路と定め、各々の確率の付与を説明する図である。

【図１０】図９で説明した仮想経路の確率の定義に従っ
て仮想経路に係る要求本数を算出する具体例を説明する
図であり、同図（ａ）はｘ方向の要求本数、同図（ｂ）
はｙ方向の要求本数の算出方法をそれぞれ示す図であ
る。

【図１１】要求本数の算出処理の詳細手順を示すフロー
チャートである。

【図１２】標準配線方向を含む各配線層の配線方向の組
合せ候補の具体例を説明する図であり、同図（ａ），
（ｂ）は配線層が２つの場合の例、同図（ｃ），（ｄ）
は配線層が３つの場合の例、同図（ｅ），（ｆ）は配線
層が４つの場合の例をそれぞれ示す。

【図１３】要求本数に基づいて、各配線層の配線方向の
組合せ候補の中から最適な配線方向の候補を決定する方
法を説明する図であり、同図（ａ）はある分割領域にお
ける候補の決定法を示し、同図（ｂ）は他の分割領域に
おける候補の決定方法を示す図である。

【図１４】配線方向の決定処理の詳細手順を示すフロー
チャートである。

【図１５】要求本数に基づいて２層回路基板に対する配
線方向決定の具体例を説明する図であり、同図（ａ）は
要求本数の算出結果、同図（ｂ）、（ｃ）、（ｄ）は３
つの候補についてそれぞれ分割領域毎に超過本数を計算
した結果、同図（ｅ），（ｆ）はそれぞれ第１層と第２
層について決定された各分割領域の配線方向の結果を示
す図である。

【図１６】コスト関数の定義方法の概念を説明する図で
あり、同図（ａ）は第１層、同図（ｂ）は第２層につい
て説明する図である。

【図１７】コスト関数の定義を説明する図であり、同図
（ａ）はコスト関数テーブルの構成と定義内容を示す図
であり、同図（ｂ）は方向の定義を説明する図である。

【図１８】コスト関数定義処理の手順を示すフローチャ
ートである。

【図１９】コスト関数を定義した結果の格子点テーブル
の内容を示す図であり、同図（ａ）は第１層に対応する
格子点テーブル、同図（ｂ）は第２層に対応する格子点
テーブルである。

【図２０】配線経路探索処理の詳細手順を示すフローチ
ャートである。

【図２１】配線経路登録処理の詳細手順を示すフローチ
ャートである。

【図２２】配線経路探索処理の具体的な実行例を説明す
る図であり、配線経路探索処理を実行する前提条件の配
線層の状態を示す図であり、同図（ａ）は第１層を、同
図（ｂ）は第２層を示す。

【図２３】配線経路探索処理の具体的な実行例を説明す
る図であり、配線経路探索処理を実行する際の格子点テ
ーブルの内容を示す図であり、同図（ａ）は第１層を、
同図（ｂ）は第２層を示す。

【図２４】配線経路探索処理の具体的な実行例を説明す
る図であり、配線経路探索処理を実行した後の格子点テ
ーブルを示す図であり、同図（ａ）は第１層を、同図
（ｂ）は第２層を示す。

【図２５】配線経路登録処理の具体的な実行結果例を示
す図であり、同図（ａ）は第１層を、同図（ｂ）は第２
層を示す。

【図２６】配線層６の間にグランド層あるいは電源層を
配することにより、層間クロストークノイズの発生を抑
制してなる一実施例の回路基板の断面図である。

【図２７】辺に対して斜め方向の配線方向を含めた場合
の配線方向の決定を説明する図であり、同図（ａ）は配
線方向を定義した図、同図（ｂ）は配線方向の組合せ候
補の一例図である。

【図２８】配線パターン決定処理に係る変形例の探索方
向禁止方向定義処理の手順を示すフローチャートであ
る。

【図２９】図２８変形例を用いた配線経路探索処理の手
順を示すフローチャートである。

【図３０】本発明の解決課題を説明するための図であ
り、同図（ａ）は特定の方向の配線要求量が多いために
配線不可能が発生する場合を示し、同図（ｂ）は特定の
方向の配線要求が局所的に集中する場合の問題を説明す
る図である。

【図３１】配線パターン決定方法の対象となる回路基板
の例を示す図である。

【符号の説明】

１ 回路基板、 ２ 配線領域、 ３ ピン、 ４ ネット、 ５ 分割領域、 ６ 配線層、６Ｘ 第１層、６Ｙ 第２層、 ７ 配線、７Ｘ 第１層上の配線、７Ｙ 第２層上の配
線、 ８ ビアホール、 ９ 仮想経路、 １０ 禁止領域、 Ｇ グランド層、 Ｖ 電源層。

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成４年１２月２２日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】０２２６

【補正方法】変更

【補正内容】

【０２２６】また、本発明の配線パターン決定方法によ
れば、配線経路探索処理に先だって最適に配線方向を決
定するため、配線経路探索の処理では繰り返し改良処理
の援用を受けるまでもなく満足な配線結果が得られるの
で、コンピュータにおいて常に実用的な計算時間で配線
パターンの決定を行うことができるという効果がある。

【手続補正２】

【補正対象書類名】明細書

【補正対象項目名】図面の簡単な説明

【補正方法】変更

【補正内容】

【図面の簡単な説明】

【図１】本発明の第１実施例に係る配線パターン決定シ
ステムの全体構成を示すブロック図である。

【図２】本発明の配線パターン決定方法により局所混雑
が緩和されるネットの具体例を示す図である。

【図３】本発明の配線パターン決定方法により定められ
た配線方向に従って決定された配線パターンの一例を示
す図であり、図２の局所混雑が緩和されることを示して
いる。

【図４】図３の第１層の配線パターンを示す図である。

【図５】図３の第２層の配線パターンを示す図である。

【図６】配線方向を決定するための基準である効能の方
が副作用よりも大きい場合の例を説明する図であり、同
図（ａ）はｘｙ原則に従って配線する場合を示し、同図
（ｂ）は分割領域の２つの配線層で共にｘ方向に配線し
た場合を示す図である。

【図７】配線方向を決定するための基準である副作用の
方が効能よりも大きい場合の例を説明する図であり、同
図（ａ）はｘｙ原則に従って配線する場合を示し、同図
（ｂ）は分割領域の２つの配線層で共にｘ方向に配線し
た場合を示す図である。

【図８】配線処理制御手段の処理手順を示すフローチャ
ートである。

【図９】要求本数の算出処理に係る仮想経路の確率を説
明するための図であり、同図（ａ）は一組みのピンを結
ぶ線が標準配線方向に平行な場合の例、同図（ｂ）と
（ｃ）は折れ曲がり数が２以下である経路をすべて仮想
経路と定め、各々の確率の付与を説明する図である。

【図１０】図９で説明した仮想経路の確率の定義に従っ
て仮想経路に係る要求本数を算出する具体例を説明する
図であり、同図（ａ）はｘ方向の要求本数、同図（ｂ）
はｙ方向の要求本数の算出方法をそれぞれ示す図であ
る。

【図１１】要求本数の算出処理の詳細手順を示すフロー
チャートである。

【図１２】標準配線方向を含む各配線層の配線方向の組
合せ候補の具体例を説明する図であり、同図（ａ），
（ｂ）は配線層が２つの場合の例、同図（ｃ），（ｄ）
は配線層が３つの場合の例、同図（ｅ），（ｆ）は配線
層が４つの場合の例をそれぞれ示す。

【図１３】要求本数に基づいて、各配線層の配線方向の
組合せ候補の中から最適な配線方向の候補を決定する方
法を説明する図であり、同図（ａ）はある分割領域にお
ける候補の決定法を示し、同図（ｂ）は他の分割領域に
おける候補の決定方法を示す図である。

【図１４】配線方向の決定処理の詳細手順を示すフロー
チャートである。

【図１５】要求本数に基づいて２層回路基板に対する配
線方向決定の具体例を説明する図であり、同図（ａ）は
要求本数の算出結果、同図（ｂ）、（ｃ）、（ｄ）は３
つの候補についてそれぞれ分割領域毎に超過本数を計算
した結果、同図（ｅ），（ｆ）はそれぞれ第１層と第２
層について決定された各分割領域の配線方向の結果を示
す図である。

【図１６】コスト関数の定義方法の概念を説明する図で
あり、同図（ａ）は第１層、同図（ｂ）は第２層につい
て説明する図である。

【図１７】コスト関数の定義を説明する図であり、同図
（ａ）はコスト関数テーブルの構成と定義内容を示す図
であり、同図（ｂ）は方向の定義を説明する図である。

【図１８】コスト関数定義処理の手順を示すフローチャ
ートである。

【図１９】コスト関数を定義した結果の格子点テーブル
の内容を示す図であり、同図（ａ）は第１層に対応する
格子点テーブル、同図（ｂ）は第２層に対応する格子点
テーブルである。

【図２０】配線経路探索処理の詳細手順を示すフローチ
ャートである。

【図２１】配線経路登録処理の詳細手順を示すフローチ
ャートである。

【図２２】配線経路探索処理の具体的な実行例を説明す
る図であり、配線経路探索処理を実行する前提条件の配
線層の状態を示す図であり、同図（ａ）は第１層を、同
図（ｂ）は第２層を示す。

【図２３】配線経路探索処理の具体的な実行例を説明す
る図であり、配線経路探索処理を実行する際の格子点テ
ーブルの内容を示す図であり、同図（ａ）は第１層を、
同図（ｂ）は第２層を示す。

【図２４】配線経路探索処理の具体的な実行例を説明す
る図であり、配線経路探索処理を実行した後の格子点テ
ーブルを示す図であり、同図（ａ）は第１層を、同図
（ｂ）は第２層を示す。

【図２５】配線経路登録処理の具体的な実行結果例を示
す図であり、同図（ａ）は第１層を、同図（ｂ）は第２
層を示す。

【図２６】配線層６の間にグランド層あるいは電源層を
配することにより、層間クロストークノイズの発生を抑
制してなる一実施例の回路基板の断面図である。

【図２７】辺に対して斜め方向の配線方向を含めた場合
の配線方向の決定を説明する図であり、同図（ａ）は配
線方向を定義した図、同図（ｂ）は配線方向の組合せ候
補の一例図である。

【図２８】配線パターン決定処理に係る変形例の探索方
向禁止方向定義処理の手順を示すフローチャートであ
る。

【図２９】図２８変形例を用いた配線経路探索処理の手
順を示すフローチャートである。

【図３０】本発明の解決課題を説明するための図であ
り、同図（ａ）は特定の方向の配線要求量が多いために
配線不可能が発生する場合を示し、同図（ｂ）は特定の
方向の配線要求が局所的に集中する場合の問題を説明す
る図である。

【図３１】配線パターン決定方法の対象となる回路基板
の例を示す図である。

【符号の説明】 １ 回路基板、 ２ 配線領域、 ３ ピン、 ４ ネット、 ５ 分割領域、 ６ 配線層、６Ｘ 第１層、６Ｙ 第２層、 ７ 配線、７Ｘ 第１層上の配線、７Ｙ 第２層上の配
線、 ８ ビアホール、 ９ 仮想経路、 １０ 禁止領域、 Ｇ グランド層、 Ｖ 電源層。

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁵ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０５Ｋ 3/00 Ｄ 6921−4Ｅ 3/46 Ｚ 6921−4Ｅ (72)発明者 田中 宏美 茨城県日立市久慈町4026番地 株式会社日 立製作所日立研究所内 (72)発明者 楠原 治郎 神奈川県秦野市堀山下１番地 株式会社日 立製作所神奈川工場内

Claims (16)

【特許請求の範囲】
1. 【請求項１】 複数の配線層を有する回路基板に定義さ
   れた複数のネットの配線経路を決定する回路基板の配線
   パターン決定方法において、 前記回路基板に設定された配線領域を複数の領域に分割
   し、 該各分割領域における同一配線方向の混雑の程度に応じ
   て、前記各分割領域ごとに前記各配線層の配線方向を決
   定し、 該決定に従って前記各ネットの配線経路を決定すること
   を特徴とする回路基板の配線パターン決定方法。
2. 【請求項２】 複数の配線層を有する回路基板に定義さ
   れた複数のネットの配線経路を決定する回路基板の配線
   パターン決定方法において、 前記回路基板に設定された配線領域を分割して複数の分
   割領域を設定する第１ステップと、 前記各配線層の標準配線方向をそれぞれ設定する第２ス
   テップと、 該標準配線方向に従って前記各ネットの仮想経路を設定
   する第３ステップと、 該仮想経路に基づいて前記各分割領域を通る配線の要求
   本数を配線方向ごとに予測する第４ステップと、 該予測に基づいて前記各分割領域における同一配線方向
   の混雑の程度を求める第５ステップと、 該求めた混雑の程度を緩和すべく前記各分割領域ごとに
   前記各配線層の配線方向を決定する第６ステップと、 該決定された前記各分割領域ごとの各配線層の配線方向
   に従って、前記各ネットの配線経路を決定する第７ステ
   ップとを、含んでなることを特徴とする回路基板の配線
   パターン決定方法。
3. 【請求項３】 請求項２において、前記第６ステップ
   が、前記各分割領域における同一配線方向の混雑度を求
   め、前記各分割領域ごとに混雑度の低い配線方向の配線
   層を混雑度の高い配線方向に変更して、前記混雑を緩和
   することを特徴とする回路基板の配線パターン決定方
   法。
4. 【請求項４】 請求項３において、混雑度の低い配線方
   向の配線層の配線方向を混雑度の高い配線方向に変更す
   るにあたり、変更すると当該配線層の変更後の混雑度が
   変更前の高い配線方向の混雑度よりも高くなる場合は変
   更しないことを特徴とする回路基板の配線パターン決定
   方法。
5. 【請求項５】 請求項２において、前記第６ステップ
   が、前記各分割領域を通る同一配線方向の配線要求本数
   の予測値と、当該分割領域の前記標準配線方向に従った
   配線容量とを比較し、前記予測値が前記配線容量を超過
   する本数に応じて、当該分割領域の他の配線方向の配線
   層を、配線容量を超過する配線の配線方向に変更して、
   前記混雑を緩和することを特徴とする回路基板の配線パ
   ターン決定方法。
6. 【請求項６】 請求項５において、前記配線層の配線方
   向を変更するにあたり、変更すると変更前の当該配線層
   の超過本数よりも、前記他の配線方向の配線層の超過本
   数の方が大きくなる場合は変更しないことを特徴とする
   回路基板の配線パターン決定方法。
7. 【請求項７】 請求項１乃至６のいずれかにおいて、前
   記分割領域が矩形に設定され、前記標準配線方向が矩形
   の分割領域の辺に平行な直交２軸方向に設定されたこと
   を特徴とする回路基板の配線パターン決定方法。
8. 【請求項８】 請求項１乃至６のいずれかにおいて、前
   記分割領域が矩形に設定され、前記標準配線方向が矩形
   の分割領域の辺に平行な直交２軸を含む対称な４軸方向
   に設定されたことを特徴とする回路基板の配線パターン
   決定方法。
9. 【請求項９】 複数の配線層を有する回路基板に定義さ
   れた複数のネットの配線経路を決定する回路基板の配線
   パターン決定方法において、 前記回路基板に設定された配線領域を分割して複数の分
   割領域を設定する第１ステップと、 前記各配線層の標準配線方向をそれぞれ設定する第２ス
   テップと、 該標準配線方向に従って前記各ネットの仮想経路を複数
   設定するとともに、該各仮想経路が採用される確率を設
   定する第３ステップと、 前記各仮想経路が通る前記各分割領域ごとに、当該分割
   領域を通る全部の仮想経路の前記確率を合計して配線方
   向ごとの配線要求本数として予測する第４ステップと、 前記各分割領域ごとに前記複数の配線層の配線方向の組
   合せ候補を列挙し、該各組合せ候補について前記第４ス
   テップで予測した配線要求本数を用いて当該分割領域に
   おける各配線方向の混雑の程度を求める第５ステップ
   と、 該求めた混雑の程度が最も小さい前記組合せ候補を採用
   して前記各分割領域ごとに前記各配線層の配線方向を決
   定する第６ステップと、 該決定された前記各分割領域ごとの各配線層の配線方向
   に従って、前記各ネットの配線経路を決定する第７ステ
   ップとを、含んでなることを特徴とする回路基板の配線
   パターン決定方法。
10. 【請求項１０】 請求項９において、前記仮想経路の確
    率は、想定できる最短距離の仮想経路の数に基づいて設
    定するものとし、仮想経路が直線の場合は確率を「１」
    とし、仮想経路が折線であってかつ許容する曲がり数を
    ｎ箇（だだし、ｎは自然数）に設定する場合は、各曲が
    り数ｎごとに想定される仮想経路の群に対してそれぞれ
    群確率を配分し、さらに各群内の同一曲がり数の仮想経
    路の数で前記群確率を割った確率を各仮想経路の確率に
    設定することを特徴とする回路基板の配線パターン決定
    方法。
11. 【請求項１１】 請求項９において、前記第４ステップ
    は、前記求めた各分割領域の配線方向ごとの要求配線本
    数のばらつきを示す標準偏差を求め、該標準偏差を小さ
    くするように前記仮想経路の確率を変更する処理を繰返
    すことを特徴とする回路基板の配線パターン決定方法。
12. 【請求項１２】 請求項９において、前記第５ステップ
    で求める混雑の程度を当該組合せ候補に関して各配線方
    向ごとの超過本数とし、 前記第６ステップは前記各配線方向ごとの超過本数の和
    が最小の組合せ候補を混雑の程度が最小とすることを特
    徴とする回路基板の配線パターン決定方法。
13. 【請求項１３】 請求項９において、前記第７ステップ
    は、前記配線層ごとに配線領域を配線単位領域に格子状
    に区分してなる格子点テーブルを作成し、該各格子点テ
    ーブルの格子点ごとに前記第６ステップで決定された前
    記分割領域ごとの各配線層の配線方向に従って配線方向
    を設定するとともに、前記各ネットのピンの位置及び既
    配線済み等の使用済みフラグを設定し、前記各ネットに
    属する一のピンの格子点から各格子点に設定されている
    配線方向に従って、他の配線層にかかる格子点を含め隣
    接する格子点を順次経由して当該ネットに属する他のピ
    ンに至る経路を複数求め、該求めた複数の経路のうち最
    短の経路を当該ネットの配線経路として決定し、該決定
    された配線経路が通る前記格子点テーブルの格子点に使
    用済みフラグを立てることを特徴とする回路基板の配線
    パターン決定方法。
14. 【請求項１４】 請求項１３において、前記最短の経路
    か否かを判断するにあたり、他の配線層に属する隣接格
    子点に移行する場合は、同一の配線層の隣接格子点に進
    む場合の経路よりも長く評価することを特徴とする回路
    基板の配線パターン決定方法。
15. 【請求項１５】 層状に形成された複数の配線層を有
    し、 前記一の配線層に周囲の配線方向と異なる配線方向の配
    線パターンが形成された少なくとも１つの矩形領域が認
    識され、 該矩形領域を細かな矩形領域に細分したとき、各細分矩
    形領域に全てのピンが含まれるネットの数よりも、当該
    細分矩形領域の境界を通過する配線パターンの数が多く
    形成されてなる回路基板。
16. 【請求項１６】 請求項１５において、前記複数の配線
    層の相互に隣接する層間にあって、少なくとも配線方向
    が同一の領域に導電性を有する層が挿入形成されてなる
    ことを特徴とする回路基板。