JPH06110978A - 電子部品のレイアウト設計支援装置 - Google Patents

Abstract

(57)【要約】 【目的】レイアウト制約条件の矛盾情報を詳しく、かつ
判り易く設計者に提供できる電子部品のレイアウト設計
支援装置を提供する。 【構成】レイアウト制約条件、レイアウト設計規則条
件、レイアウト設計データ等を入力するための入力装置
１を介して与えられたレイアウト制約条件は、有向グラ
フを用いる検証手段２によって検証され、続いて線形計
画問題を用いる検証手段３によって検証される。それぞ
れの検証結果は、矛盾表示ルール記憶部５に記憶されて
いるルールにしたがい矛盾した制約条件に関係している
図形パタ−ンを制約条件の種類に合わせ、かつ種類毎に
関連付けて表示装置８に表示される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、プリント基板やＬＳＩ
のレイアウト設計を行うときなどにおいて利用される、
いわゆる電子部品のレイアウト設計支援装置に関する。

【０００２】

【従来の技術】従来、プリント基板やＬＳＩのレイアウ
ト設計等を容易化するためにレイアウト設計支援装置が
広く使われている。このレイアウト設計支援装置は、幾
つかの機能を備えている。レイアウトされた図形パタ−
ン間の無駄な隙間を詰めて配置配線面積を小さくするた
めの、いわゆるコンパクションと呼ばれる処理機能もそ
の１つである。

【０００３】最近では、単に面積を小さくするだけでは
なく、さらに高性能の電気回路を実現するために、様々
なレイアウト制約条件を守ってコンパクションを行う手
法が提案されている（文献１：奥田亮輔、佐藤寿倫、小
野寺秀俊、田丸啓吉、「対称性保持の制約を扱えるレイ
アウトコンパクションアルゴリズム」、電子情報通信学
会論文誌Ａ，Ｖｏｌ．Ｊ７３−Ａ，Ｎｏ．３ｐｐ．５３
６−５４３，１９９０年３月、文献２：小野沢晃、「高
品質レイアウト設計のためのコンパクション手法」、信
学技法ＣＡＳ８９−３０，ｐｐ．５７−６４，１９８９
年６月）。このようなコンパクション手法を、以後、高
品質レイアウトコンパクションと呼ぶことにする。

【０００４】このように、レイアウト設計支援装置は、
いわゆる電子部品の設計の容易化に寄与している。しか
し、コンパクション処理に際して入力されるレイアウト
制約条件やレイアウト設計データに誤りがあると、コン
パクションが行えなかったり、所望の結果とは異なる誤
ったコンパクション結果を得てしまう場合がある。

【０００５】したがって、入力されるデータに対して、
前もって設計規則等の検証を行い、誤りを取り除いてお
く必要がある。これは文献１に述べられているような高
品質レイアウトコンパクションの場合も同じで、レイア
ウト制約条件間に矛盾のないことを検証し、もし矛盾が
あった場合にはレイアウト設計データにおいて矛盾の存
在する箇所などの情報を設計者に提供することが必要で
ある。

【０００６】誤りを見つけ出す方法としては、従来、有
向グラフ中の矛盾を表す正のサイクルを見つけ出す手法
が用いられている。この手法については、文献３：石間
邦彦、築山修治「レイアウトコンパクションにおける制
約矛盾の検出に関する一考察」、電子情報通信学会春季
全国大会（１９９０年）Ａ−１３３に詳しく説明されて
いる。

【０００７】ところで、コンパクション処理を行うに
は、上記のように前もって設計規則違反やレイアウト制
約条件の矛盾を検証し、その情報を設計者に提示する必
要があるが、この提示に際しては表示画面上で行うのが
何かと都合がよい。このようなことから、従来、設計規
則違反については、違反している図形パタ−ンを違反で
あることを示す特別の色で画面上に表示して設計者に知
らせる手法が採用されている。

【０００８】しかしながら、レイアウト制約条件の検証
結果を表示するに際し、設計規則違反の場合と同様に、
矛盾した制約条件に関係している１グル−プの図形パタ
−ンを矛盾を表す特別な色で表示した場合には次のよう
な問題がある。すなわち、ある矛盾している制約条件に
関係している１グル−プの図形パタ−ン同士が互いに離
れていると、特別の色で表示しても判り難いものとな
る。また、複数の矛盾した制約条件を一度に表示しよう
とすると、それぞれの制約条件に関係したグル−プの図
形パタ−ンが交じり合って識別できなくこともある。ま
た、異なった制約条件の矛盾を同じ色で表示すると、あ
る同一の図形パタ−ンのグル−プが複数の制約条件に関
係している場合、どの制約条件が矛盾しているのか識別
できないことになる。また、矛盾し合っている複数の制
約条件に対しては、それらの制約条件が矛盾し合ってい
ることが判っても、それらの制約条件がどのように関係
し合って矛盾しているのかを判別できない。このよう
に、現在においてもレイアウト制約条件の検証結果を表
示する手法が確立されていない。

【０００９】さらに、従来の検証では、単に設計規則違
反や制約条件の矛盾が起こっていることを設計者に知ら
せるだけで、どうすれば違反や矛盾を解消することがで
きるかといった情報を設計者に与えてはいない。このた
め、設計規則違反や制約条件の矛盾を解消するために、
設計者が自分でどうすれば解消できるのかを模索しなけ
ればならず、熟練と試行錯誤が必要であった。また、１
つの設計規則違反あるいは制約条件の矛盾を解消しよう
とすると、新たな違反あるいは矛盾が起きてしまうこと
も少なくない。レイアウト制約条件の場合には、複数の
種類の制約条件が関連し合うので、設計者によって矛盾
を解消することが益々困難になる。また、矛盾を解消す
る場合、レイアウトの変更だけでは対処できず、優先順
位の低い制約条件を諦めて優先順位の高い制約条件だけ
を満すようにしなければならないことが往々にしてあ
る。このような場合、従来は設計者が満たされるべき制
約条件を決め、そのために諦めるべき制約条件を探して
決定しているのが実情である。

【００１０】

【発明が解決しようとする課題】上述の如く、高品質レ
イアウトコンパクションを実行させるには、それに先だ
って制約条件間に矛盾がないか否かを検証することが重
要である。また、制約条件間に矛盾が存在する場合、矛
盾している制約条件を見つけ出し、設計者に知らせるこ
とも重要である。そして、一組の図形パタ−ンが複数の
制約条件に関係しているときには、どの制約条件が矛盾
しているのかを、また矛盾し合っている複数の制約条件
に対しては、それらの制約条件がどのように関係し合っ
ているのかを判断し易いように設計者に知らせることも
重要である。さらに、矛盾を解消するにはどこを直せば
よいか、また矛盾し合っている複数の制約条件に対し
て、優先順位の低い制約条件を諦めることによって優先
順位の高い制約条件を満足させるにはどのようにすれば
よいか、ということを設計者に知らせることも重要であ
る。

【００１１】そこで本発明は、上述した要望を満たすこ
とができ、たとえば高品質レイアウトコンパクションの
制約条件を検証する場合であっても、最善の図形パタ−
ンの配置解を設計者に与え得る電子部品のレイアウト設
計支援装置を提供することを目的としている。

【００１２】

【課題を解決するための手段】上記目的を達成するため
に、本発明に係る電子部品のレイアウト設計支援装置で
は、少なくともレイアウト制約条件、レイアウト設計規
則条件、レイアウト設計データを入力するための入力装
置と、この入力装置を介して与えられたレイアウト制約
条件中の矛盾した制約条件を見つけ出す制約条件検証手
段と、前記入力装置を介して与えられた前記レイアウト
設計データを図形パターンで表示するとともに前記制約
条件検証手段の出力を導入して矛盾した制約条件に関係
している図形パタ−ンを制約条件の種類に合わせ、かつ
種類毎に関連付けて表示する表示手段とを備えている。

【００１３】さらに詳しく説明すると、表示手段として
は、矛盾した制約条件に関係している１グル−プの図形
パタ−ン間を制約条件の種類に合わせて、種類毎に異な
った繋ぎ方で繋いで表示する表示方式の採用が好まし
い。

【００１４】また、レイアウト制約条件に矛盾がないか
否かを調べる制約条件検証手段としては、有向グラフ中
にある正のサイクルを検出する手法と最適化問題を解く
手法とを組み合わせて用いることが好ましい。この組み
合わせによって全ての矛盾を見つけ出すことができ、最
適化問題を解く手法のみを用いて調べる場合よりも、よ
り高速に調べることができる。なお、ここでいう最適化
問題を解く手法とは、元のレイアウト制約条件に人為変
数の項を加えた式を条件式として持ち、人為変数の項が
あることによって必ず問題が解けるようにした最適化問
題で、かつ人為変数が０に近づくほど値が０に近づくよ
うな人為変数の多項式を目的関数として持った最適化問
題を目的関数の項の係数を変化させながら、繰り返し解
くことによって矛盾のある制約条件を探していく手法で
ある。

【００１５】さらに、最適化問題を繰り返し解いて矛盾
を見つけ出していく過程で得られた最適化問題の解を一
部の制約条件が守られていない図形パタ−ンの配置解と
して、少なくとも１つ以上表示することも好ましい。最
適化問題を繰り返し解いて、矛盾を見つけ出していく過
程で得られた最適化問題の解では、矛盾し合った制約条
件のうち、一部は満たされているが他の一部は満たされ
ておらず、また満たされている条件と満たされていない
条件の組み合わせが解毎に異なっている。これらの解の
配置をレイアウト画面上に表示させることにより、レイ
アウト上の、どの部分の、どのような制約条件が、どの
ように矛盾しているのかを判断させ易く、どのようにレ
イアウトや制約条件を変更すればよいかを理解させる助
けにもなる。

【００１６】また、矛盾を解消するために優先順位の低
い制約条件を諦め、優先順位の高い制約条件が満たされ
るようにするために、設計者によって矛盾した制約条件
に優先順位を付けることができるように構成し、最適化
問題の解の中から優先順位の低い制約条件が満たされて
いない代わりに優先順位の高い制約条件が満たされた解
が選び出されるようにし、最善の図形パタ−ンの配置解
が示されるようにすることも好ましい。

【００１７】

【作用】上記のように構成されているので、高品質レイ
アウトコンパクションを行うに先だって、制約条件に矛
盾がないか否かの検証が行われると、矛盾がある場合に
はレイアウト上のどの部分の、どの制約条件同士が、ど
のように矛盾し合っているのかを知ることができ、矛盾
がなくなるように制約条件やレイアウトを修正し易くな
る。さらに、優先順位の低い制約条件が満たされていな
い代わりに優先順位の高い制約条件が満たされた最善の
図形パタ−ンの配置解を得ることも可能である。

【００１８】

【実施例】以下、図面を参照しながら実施例を説明す
る。

【００１９】図１には本発明の一実施例に係る電子部品
のレイアウト設計支援装置のブロック構成図が示されて
いる。

【００２０】同図において、１は入力装置を示してい
る。この入力装置１はレイアウト制約条件、レイアウト
設計規則条件、元のレイアウト設計デ−タ、設計者の指
示などを入力するためのものである。２は検証手段で、
この検証手段２は入力装置１を介して入力されたレイア
ウト制約条件を有向グラフ中にある正のサイクルを見つ
け出す手法を用いて検証する。この検証結果は、後述す
る矛盾検証結果処理部６へ送られる。３は同じく検証手
段で、この検証手段３は最適化問題の１つである線形計
画問題を解くことによって入力されたレイアウト制約条
件の検証を行う。この検証結果は解記憶部４に送られて
記憶される。

【００２１】矛盾表示ル−ル記憶部５は、矛盾している
レイアウト制約条件の種類毎の表示形式などを矛盾表示
ル−ルとして予め記憶している。矛盾検証結果処理部６
は、検証手段２および検証手段３で見つけ出した矛盾し
ているレイアウト制約条件を矛盾表示ル−ル記憶部５の
矛盾表示ル−ルにしたがって出力装置７を介して表示装
置８に表示させたり、あるいは検証手段３で矛盾したレ
イアウト制約条件を見つけ出したときの線形計画問題の
解を解記憶部４から読み出し、これを出力装置７を介し
て表示装置８に表示させる。

【００２２】一方、解選択部９は設計者の指示にしたが
って解記憶部４に記憶されている解の中から優先順位の
低いレイアウト制約条件が満たされていない代わりに優
先順位の高いレイアウト制約条件が満たされた最善の解
を選び出し、これを出力装置７を介して表示装置８に表
示させる機能を備えている。

【００２３】次に、上記のように構成されたレイアウト
設計支援装置を使ってレイアウト制約条件の検証を行う
例を図２および図３に示される流れ図を参照しながら説
明する。

【００２４】ここでは、図４、図５、図６に模式的に示
されるレイアウト例を対象にして制約条件の検証を行う
ものとし、水平方向の高品質レイアウトコンパクション
を想定した場合について話を進める。なお、図４は１２
個の部品１０〜２１をレイアウトした全体図を示し、図
５、図６は図４の部分図を示している。

【００２５】図４の例では、従来の設計規則からくる条
件の他に、図形Ａおよび図形Ｂが図形Ｃに対して対称な
水平距離（ｘ_c −ｘ_a ＝ｘ_b −ｘ_c 、ここで、ｘ_a 、ｘ
_b 、ｘ_c はそれぞれ図形Ａ、Ｂ、Ｃの中心のレイアウト
上の位置を表すｘ座標）に、図形Ｄおよび図形Ｅが図形
Ｆに対して対称な水平距離に、図形Ｇおよび図形Ｈが図
形Ｉに対して対称な水平距離に、図形Ｊおよび図形Ｋが
図形Ｌに対して対称な水平距離になるように配置され
る、対称配置制約条件が課せられ、さらに図形Ｇおよび
図形Ｈには図形Ｇと図形Ｈとがある距離以上離れてはな
らないという、近接配置制約条件が課せられているもの
とする。

【００２６】図４の例に課せられている条件を式で表す
と、第１式および第２式のようになる。 （第１式） ｘ_c −ｘ_a ＝ｘ_b −ｘ_c （対称配置制約条件） ｘ_f −ｘ_d ＝ｘ_e −ｘ_f （対称配置制約条件） ｘ_i −ｘ_g ＝ｘ_h −ｘ_i （対称配置制約条件） ｘ_l −ｘ_j ＝ｘ_k −ｘ_l （対称配置制約条件） ｘ_h −ｘ_g ≦ｄ₁ （近接配置制約条件） ｘ_b −ｘ_a ≧ｄ₂ （設計規則条件） ｘ_d −ｘ_b ≧ｄ₃ （設計規則条件） ｘ_e −ｘ_d ≧ｄ₄ （設計規則条件） ｘ_c −ｘ_f ≧ｄ₅ （設計規則条件） ｘ_j −ｘ_g ≧ｄ₆ （設計規則条件） ｘ_k −ｘ_j ≧ｄ₇ （設計規則条件） ｘ_h −ｘ_k ≧ｄ₈ （設計規則条件） ｘ_l −ｘ_i ≧ｄ₉ （設計規則条件） ｘ_a 〜ｘ_l ：図形Ａ〜Ｌの中心のｘ座標 ｄ₂ 〜ｄ₉ ：設計規則で許されている各図形間の最小の
距離 ｄ₁ ：近接配置制約で許されている図形Ｇと図形Ｈとの
間の最大距離 （第２式） ｄ₆ ＋ｄ₇ ＋ｄ₈ ＜ｄ₁ ＜ｄ₇ ＋２×ｄ₈ ＋２×ｄ₉ そこで、まず上記の配置制約条件、設計規則条件および
レイアウト設計データを入力装置１を介して入力する。

【００２７】入力終了後、スタートさせる（Ｓ₁ ）と、
まず検証手段２が有向グラフ中にある正のサイクルを見
つけ出す手法を用いて制約条件の検証を行う（Ｓ₂ ）。

【００２８】検証の結果、矛盾した制約条件のあるとき
には（Ｓ₃ ）、表示装置８に写し出されているレイアウ
ト画面上の矛盾した制約条件に関係している図形パタ−
ン間を繋ぐことで表示する（Ｓ₄ ）。この表示に基づ
き、設計者によって各条件やレイアウトが変更されて矛
盾が解消される（Ｓ₅ ）。

【００２９】次に、検証手段３が線形計画問題を利用し
て制約条件の検証を行う（Ｓ₆ ）。この検証結果は、レ
イアウト画面上の図形パタ−ン間を繋ぐことによって表
示されたり、検証手段３で解いた線形計画法の解を表示
することで表示される（Ｓ₈）。この表示に基づき、設
計者によって各条件やレイアウトが変更されて矛盾が解
消される（Ｓ₁₀）。

【００３０】ここで、検証手段３は線形計画問題を利用
しているので、全ての矛盾を見つけ出すことができる
が、検証手段２よりも時間が掛る。逆に、検証手段２は
高速ではあるが、見つけ出すことのできない矛盾があ
る。そこで、この例では制約条件検証に要する時間を短
縮するために、先ず、検証手段２で矛盾を見つけ出し、
残りの矛盾だけを検証手段３で見つけ出すようにしてい
る。

【００３１】有向グラフ中にある手法を用いた検証手段
２は、従来のコンパクション手法で用いられているよう
な、一般に制約グラフと呼ばれる有向グラフに、高品質
レイアウトコンパクション特有の制約条件を表す辺を付
け加えた有向グラフを用いて矛盾を探す。

【００３２】図７が図４の例に対する有向グラフで、対
称配置制約条件を表す辺が太く描かれている。辺の重み
ｄｓ₁ 〜ｄｓ₄ としては０を与えればよい。この例で
は、上記有向グラフに、従来同様、矛盾を表す正のサイ
クルを見つけ出す手法を用いている。図７では矢印３
５、４１、３７、３９によってＢ→Ｄ→Ｆ→Ｃ→Ｂとい
うサイクルができているので、第３式に示した２条件が
矛盾していることが判る。

【００３３】一方、矢印４２と矢印４７、４８、４９、
５０のいずれかを含むサイクルは、ｄ₁ がｄ₆ ＋ｄ₈ 、
ｄ₈ ＋ｄ₉ よりも大きければ正のサイクルではない。 （第３式） ｘ_c −ｘ_a ＝ｘ_b −ｘ_c （対称配置制約条件） ｘ_f −ｘ_d ＝ｘ_e −ｘ_f （対称配置制約条件） こうして見つけ出された矛盾している制約条件は、矛盾
表示ル−ル記憶部５に記憶されている矛盾表示ル−ルに
したがって表示装置８に表示される。この例において、
矛盾表示ル−ルとして、予め決められた制約条件の種類
毎に図形パターン間を異なった繋ぎ方で繋ぐ方式が採用
されている。なお、矛盾表示ル−ル毎に異なった色や異
なった色の組み合わせを用いて表示してもよい。

【００３４】図８には図４のレイアウト例の矛盾した制
約条件を矛盾表示ル−ルにしたがって画面上に表示した
例が示されている。この例では、対称配置制約条件が矛
盾している場合、対称の中心を根元とするＶ字型に図形
パタ−ンを繋いで表示するという矛盾表示ル−ルが採用
されており、この矛盾表示ル−ルにしたがって図形Ａ、
Ｂ、ＣがＣを根元とするＶ字型５１に、図形Ｄ、Ｅ、Ｆ
がＦを根元とするＶ字型５２に繋がれている。

【００３５】したがって、上記表示に基づいて、設計者
は図形Ａ、Ｂ、Ｃ間にＣを対称の中心とする対称配置制
約条件が、また図形Ｄ、Ｅ、Ｆ間にＦを対称の中心とす
る対称配置制約条件が課せられていることを知ることが
でき、さらに２つのＶ字型５１と５２とが交差している
ことから、この２つの対称配置制約条件が矛盾し合って
いることを知ることができる。

【００３６】図９には設計者によって図形Ｃ、Ｆの位置
が入れ替えられ、２つのＶ字型の交差が解かれ、矛盾の
解消された例が示されている。図９に矛盾はないが、矛
盾が解消されたことがはっきりするように図形をＶ字型
に繋いである。

【００３７】このように矛盾した制約条件に関係した図
形パタ−ン間を制約条件の種類毎に決められた繋ぎ方で
繋いで表示するようにしている。したがって、レイアウ
ト画面上の繋がれた図形パタ−ンを見てどの部分に矛盾
があるのかを知り、図形パタ−ンの繋がれ方からそれが
どのような制約条件かを知り、さらに繋がれた図形パタ
−ンのグル−プ同士の関連の仕方から制約条件同士がど
のように関係し合って矛盾を引き起こしているのかを知
ることができる。

【００３８】有向グラフの手法を用いた検証手段２で
は、全ての矛盾を見つけ出すことができないので、次に
線形計画問題を用いた検証手段３が実行される。そのよ
うな矛盾の例が図６に示される例である。

【００３９】線形計画問題を用いた検証手段３では、与
えられた条件、第１式から第４式、第５式、第６式、第
７式の線形計画問題を作成し、これを用いて矛盾を見つ
け出していく。なお、ここでは検証手段２で見つけ出さ
れた矛盾は図９のように配置を変更して解消してあるも
のとする。 （第４式） 目的関数：ａ₁ ×（ｘ₁ ＋ｘ₂ ）＋ａ₂ ×（ｘ₃ ＋
ｘ₄ ）＋ａ₃ ×（ｘ₅ ＋ｘ₆ ）＋ａ₄ ×（ｘ₇ ＋ｘ₈ ）
＋ａ₅ ×ｘ₉ （第５式） ２×ｘ_c −ｘ_a −ｘ_b ＋ｘ₁ −ｘ₂ ＝０ ２×ｘ_f −ｘ_d −ｘ_e ＋ｘ₃ −ｘ₄ ＝０ ２×ｘ_i −ｘ_g −ｘ_h ＋ｘ₅ −ｘ₆ ＝０ ２×ｘ_l −ｘ_j −ｘ_k ＋ｘ₇ −ｘ₈ ＝０ ｘ_h −ｘ_g −ｘ₉ ≦ｄ₁ ｘ_b −ｘ_a ≧ｄ₂ ｘ_d −ｘ_b ≧ｄ₃ ｘ_e −ｘ_d ≧ｄ₄ ｘ_f −ｘ_c ≧ｄ₅ ｘ_j −ｘ_g ≧ｄ₆ ｘ_k −ｘ_j ≧ｄ₇ ｘ_h −ｘ_k ≧ｄ₈ ｘ_l −ｘ_i ≧ｄ₉ （第６式） Ｌ_a ≦ｘ_a ≦Ｍ_a ，Ｌ_b ≦ｘ_b ≦Ｍ_b ，… ，Ｌ₁ ≦ｘ
₁ ≦Ｍ₁ ，０≦ｘ₁ 〜ｘ₉ ≦Ｍ （第７式） ａ₁ 〜ａ₅ ＝１ （初期値） 第４式〜第６式中のｘ₁ 〜ｘ₉ は人為変数で、第６式中
のＬ_a 〜Ｌ_l ，Ｍ_a 〜Ｍ_l はレイアウト上決められてい
るｘ_a 〜ｘ_l の最小値と最大値、Ｍは適当な大きな値で
あればよい。

【００４０】第１式における下二つの対称配置制約条件
を満たす配置では、図形Ｇ、Ｈ間はｘ_h −ｘ_g ＝ｄ₇ ＋
２ｄ₈ ＋２ｄ₉ となるが、第２式のｄ₁ ＜ｄ₇ ＋２ｄ₈
＋２ｄ₉ の条件があるために、２つの対称配置制約条件
と近接配置制約条件とを同時に満たすことができなくな
っている。

【００４１】矛盾した条件を見つけ出すには、第４式の
目的関数を最小にするという線形計画問題を解く。こう
して得られた解では、元の第１式に矛盾がなければ第４
式の目的関数の値が０になり、人為変数ｘ₁ 〜ｘ₉ の値
も０になる。

【００４２】しかし、矛盾がある場合、目的関数は０に
はならず、人為変数ｘ₁ 〜ｘ₉ の中で矛盾した式に加え
た人為変数も０にはならないので、その式が矛盾してい
る式である言える。

【００４３】ここで用いる最適化問題は、元の各制約条
件式にそれぞれ少なくとも１つ以上の人為変数を付け加
えることによって問題が解けるようにし、全ての人為変
数が０になったとき、目的関数が最小となるような最適
化問題であればよく、たとえば目的関数が人為変数の２
次式である２次計画問題を用いることもできる。

【００４４】したがって、第４式〜第７式の線形計画問
題の代わりに２次計画問題として （第８式） 目的関数：ａ₁ ×ｘ₁ ×ｘ₁ ＋ａ₂ ×ｘ₂ ×ｘ₂ ＋ａ₃
×ｘ₃ ×ｘ₃＋ａ₄ ×ｘ₄ ×ｘ₄ ＋ａ₅ ×ｘ₅ ×ｘ₅ （第９式） ２×ｘ_c −ｘ_a −ｘ_b ＋ｘ₁ ＝０ ２×ｘ_f −ｘ_d −ｘ_e ＋ｘ₂ ＝０ ２×ｘ_i −ｘ_g −ｘ_h ＋ｘ₃ ＝０ ２×ｘ_l −ｘ_j −ｘ_k ＋ｘ₄ ＝０ ｘ_h −ｘ_g −ｘ₅ ≦ｄ₁ ｘ_b −ｘ_a ≧ｄ₂ ｘ_d −ｘ_b ≧ｄ₃ ｘ_e −ｘ_d ≧ｄ₄ ｘ_f −ｘ_c ≧ｄ₅ ｘ_j −ｘ_g ≧ｄ₆ ｘ_k −ｘ_j ≧ｄ₇ ｘ_h −ｘ_k ≧ｄ₈ ｘ_l −ｘ_i ≧ｄ₉ （第１０式） Ｌ_a ≦ｘ_a ≦Ｍ_a ，Ｌ_b ≦ｘ_b ≦Ｍ_b ，… ，Ｌ_l ≦ｘ
_l ≦Ｍ_l ，−Ｍ≦ｘ₁ 〜ｘ₅ ≦Ｍ （第１１式） ａ₁ 〜ａ₅ ＝１（初期値） を用いても同様に矛盾を求めることができる。

【００４５】第４式〜第７式を第１２式のように、ｄ₁
＝１６，ｄ₂ 〜ｄ₉ ＝４である場合について解いてみる
と、ｘ₅ が正になり、この式が矛盾していることが判
る。 （第１２式） 目的関数：ａ₁ ×（ｘ₁ ＋ｘ₂ ）＋ａ₂ ×（ｘ₃ ＋
ｘ₄ ）＋ａ₃ ×（ｘ₅ ＋ｘ₆ ）＋ａ₄ ×（ｘ₇ ＋ｘ₈ ）
＋ａ₅ ×ｘ₉ ２×ｘ_c −ｘ_a −ｘ_b ＋ｘ₁ −ｘ₂ ＝０ ２×ｘ_f −ｘ_d −ｘ_e ＋ｘ₃ −ｘ₄ ＝０ ２×ｘ_i −ｘ_g −ｘ_h ＋ｘ₅ −ｘ₆ ＝０ ２×ｘ_l −ｘ_j −ｘ_k ＋ｘ₇ −ｘ₈ ＝０ ｘ_h −ｘ_g −ｘ₉ ≦１６ ｘ_b −ｘ_a ≧４ ｘ_d −ｘ_b ≧４ ｘ_e −ｘ_d ≧４ ｘ_f −ｘ_c ≧４ ｘ_j −ｘ_g ≧４ ｘ_k −ｘ_j ≧４ ｘ_h −ｘ_k ≧４ ｘ_l −ｘ_i ≧４ ０≦ｘ_g 〜ｘ_l ≦１００，０≦ｘ₁ 〜ｘ₉ ≦１００ ａ₁ 〜ａ₃ ＝１ （初期値） 矛盾している式をさらにに見つけ出すために、ａ₃ の値
を１よりも十分大きな値に変えて再び問題を解く。ａ₃
＝１０とおいて解いてみると、今度はｘ₇ が正になり、
ｘ₇ を含んだ式も矛盾していることが判る。さらに、ａ
₂ もａ₂ ＝１０として再び解くと、今度はｘ₂ が正にな
り、ｘ₂ を含んだ式も矛盾していることが判る。さら
に、ａ₁ もａ₁ ＝１０として再び解くと、今度は再びｘ
₅ が正になるので、ここで探索を終了する。

【００４６】こうして、第１３式、第１４式、第１５式
に示した３条件が矛盾し合っていることが判る。 （第１３式） ２×ｘ_i −ｘ_g −ｘ_h ＝０ （第１４式） ２×ｘ_l −ｘ_j −ｘ_k ＝０ （第１５式） ｘ_h −ｘ_g ≦１６ これらの矛盾も矛盾表示ル−ルにしたがって図８と同様
に表示される。

【００４７】検証手段３を用いた場合では、矛盾した制
約条件を見つけ出すために解いた線形計画問題の解が画
面上に表示される（Ｓ₈ ）ことによって、設計者は矛盾
した複数の制約条件間の関係をより詳しく知ることがで
きる。

【００４８】また、設計者が矛盾を解消するために、優
先順位の低い制約条件を諦め、優先順位の高い制約条件
が満たされるようにする場合、矛盾表示ル−ルによる表
示ではどの制約条件を変更すればどの制約条件を満たす
ことができるかを設計者自信が判断しなければならな
い。しかし、線形計画問題の解から、どの制約条件を変
更すればどの制約条件を満たすことができるかを知るこ
とができる。

【００４９】例として、第１２式の場合が図１０、図１
１、図１２に示されている。

【００５０】図１０、図１１、図１２は、第１２式の問
題を繰り返し解いて、第１３〜１５式の矛盾した３条件
を求めたときの最適化問題の解を表示したもので、順番
に、第１５式を求めたときの解が図１０、第１４式を求
めたときの解が図１１、第１３式を求めたときの解が図
１２である。

【００５１】図１０は２つの対称配置制約条件が満たさ
れ、第１５式の近接配置制約条件が満たされていない場
合の図形パタ−ンの配置、図１１は第１３式の対称配置
制約条件と第１５式の近接配置制約条件が満たされ、第
１４式の対称配置制約条件が満たされていない場合の図
形パタ−ンの配置、図１２は第１４式の対称配置制約条
件と第１５式の近接配置制約条件が満たされ、第１３式
の対称配置制約条件が満たされていない場合の図形パタ
−ンの配置を示している。それぞれ３つの制約条件を図
８と同様に図形パターンを繋いだ形で表示されている。

【００５２】Ｖ字型５３と５４とは対称配置制約条件、
図形ＧとＨに書かれて向き合った三角形の間を繋いだ表
示５５が近接配置制約条件を示す表示である。向き合っ
た三角形の間の繋いだ線の上に書かれた１６という数字
５６は、近接配置制約条件で許された図形ＧとＨとの間
の最大距離が１６であることを意味している。図１０で
線の下に書かれている２０という数字５７は、近接が満
たされていないために、図形ＧとＨとの間が２０になっ
ていることを意味している。図１０、図１１、図１２で
は、満たされている制約条件と満たされていない制約条
件とが一緒に表示されているので、各々異なった色で区
別して表示される。

【００５３】図１０〜１２によって、設計者は、２つの
対称配置制約条件と近接配置制約条件とが両立しないこ
と、矛盾を解消するにはレイアウトを変更するか、２つ
の対称配置制約条件のうちの１つを諦めるか、近接配置
制約条件を緩めて２０以内とすればよいことが判る。

【００５４】このように、検証手段３で矛盾した制約条
件を見つけ出すために解いた線形計画問題の解を表示す
ることによって、矛盾した複数の制約条件間のより詳し
い関係や、どの制約条件を変更すればどの制約条件を満
たすことができるかという点を設計者に知らせることが
できる。

【００５５】さらに、矛盾を解消するために、優先順位
の低い制約条件を諦め、優先順位の高い制約条件が満た
されるようにする場合、設計者が制約条件の優先順位を
与えることによって、解選択部９を介して解記憶部４に
記憶された解の中から、優先順位の低い制約条件が満た
されていない代わりに優先順位の高い制約条件の満たさ
れいる解を選び出して表示させることができる
（Ｓ₁₁）。

【００５６】先の例で説明すると、設計者が近接配置制
約条件５５を最優先、次に対称配置制約条件５３、最後
に対称配置制約条件５４と順位を付けると、解選択部９
は図１０〜１２に示した解の中から、優先順位の低い対
称配置制約条件５４が満たされていない代わりに近接配
置制約条件５５と対称配置制約条件５３の満たされた図
１１の解を選び出して表示する。優先順位の与え方、解
の選び方は、優先順位が高い条件ほど重い重み付けを行
い、各解毎に評価関数の値を計算し、評価関数の値が最
も大きな解を選択する。選択する解は１つだけではな
く、最大値の解が複数あるときはそれらを全て表示す
る。また、評価関数の値が大きい解を大きいものから複
数個表示し、設計者がさらにその中から都合の良い解を
選べるようにしてもよい。

【００５７】以上のようにして、制約条件検証を繰り返
し行い、制約条件の中から矛盾を見つけ出し、矛盾が解
消するよう制約条件や元のレイアウトを変更すればよい
ことになる。

【００５８】検証が終了したとき、矛盾した制約条件を
見つけ出すために解いた矛盾のない最適化問題の解、あ
るいは選択した優先順位の高い制約条件の満たされた解
を高品質レイアウトコンパクション工程にデ−タとして
送り、高品質レイアウトコンパクションに利用すること
ができる。

【００５９】文献２で述べられている対称性保持の制約
を扱えるレイアウトコンパクションアルゴリズムでは、
シンプレックス法を利用しているが、シンプレックス法
には二段階法が用いられることが多い。二段階法では第
一段階で実行可能基底解を求め、第二段階で最適解を求
める。制約条件に矛盾のない場合、矛盾した制約条件を
見つけ出すために解いた最適化問題の解では人為変数が
全て０となっている。この解の人為変数以外の元から制
約条件に含まれていた変数の値を実行可能基底解として
用いると、二段階法の第一段階を省略でき、二段階法を
用いた高品質レイアウトコンパクションをより高速に実
行できる。優先順位の高い制約条件が満たされた解を選
ぶことは、低い制約条件を高品質レイアウトコンパクシ
ョンの制約条件から取り除くことである。選んだ解では
残りの優先順位の高い制約条件に対しては人為変数が全
て０となっているので、やはり制約条件を減らした高品
質レイアウトコンパクションに対し二段階法の第一段階
を省略できる。

【００６０】

【発明の効果】以上説明したように、本発明によれば、
高品質レイアウトコンパクションの矛盾した制約条件を
見つけ出すことができると同時に、その制約条件がレイ
アウト上のどの部分にあり、そこでどのような制約条件
が、どのように矛盾を引き起こしているのかという情報
を判り易く設計者に提供することができ、さらに優先順
位の低い制約条件が満たされていない代わりに優先順位
の高い制約条件が満たされた最善の図形パタ−ンの配置
解を設計者に提供することもできる。

【図面の簡単な説明】

【図１】本発明の一実施例に係るレイアウト設計支援装
置のブロック構成図

【図２】同装置の動作を説明するための流れ図

【図３】同装置の動作を説明するための流れ図

【図４】電子部品のレイアウトの一例を示す模式図

【図５】第１の検証手段で見つけ出すことが可能な矛盾
を含むレイアウト部分を示す模式図

【図６】第１の検証手段では見つけ出すことができない
が第２の検証手段では見つけ出すことが可能な矛盾を含
むレイアウト部分を示す模式図

【図７】第１の検証手段で用いられる有向グラフの一例
を示す模式図

【図８】矛盾した制約条件の表示方式の一例を示す模式
図

【図９】矛盾を解消したレイアアウトの一例を示す模式
図

【図１０】第２の検証手段で求めた線形計画問題の解
（ｘ₃ ＞０の場合）の表示例を示す模式図

【図１１】第２の検証手段で求めた線形計画問題の解
（ｘ₂ ＞０の場合）の表示例を示す模式図

【図１２】第２の検証手段で求めた線形計画問題の解
（ｘ₁ ＞０の場合）の表示例を示す模式図

【符号の説明】

１…入力装置 ２…有向グラフを
用いる検証手段 ３…線形計画問題を用いる検証手段 ４…解記憶部 ５…矛盾表示ル−ル記憶部 ６…矛盾検証結果
処理部 ７…出力装置 ８…表示装置 ９…解選択部 １０〜２１…レイ
アウトの図形パタ−ン ２２〜３３…有向グラフの頂点 ３４〜５０…有向
グラフの辺 ５１〜５４…対称配置制約条件の表示形式 ５５…近接配置制約条件の表示形式

Claims (3)

【特許請求の範囲】
1. 【請求項１】電子部品のレイアウト設計を支援するため
   のものであって、少なくともレイアウト制約条件、レイ
   アウト設計規則条件、レイアウト設計データを入力する
   ための入力装置と、この入力装置を介して与えられたレ
   イアウト制約条件中の矛盾した制約条件を見つけ出す制
   約条件検証手段と、前記入力装置を介して与えられた前
   記レイアウト設計データを図形パターンで表示するとと
   もに前記制約条件検証手段の出力を導入して矛盾した制
   約条件に関係している図形パタ−ンを制約条件の種類に
   合わせ、かつ種類毎に関連付けて表示する表示手段とを
   具備してなることを特徴とする電子部品のレイアウト設
   計支援装置。
2. 【請求項２】前記表示手段は、矛盾した制約条件に関係
   している図形パタ−ン間を制約条件の種類に合わせ、か
   つ種類毎に異なった繋ぎ方で繋いで表示するものである
   ことを特徴とする請求項１に記載の電子部品のレイアウ
   ト設計支援装置。
3. 【請求項３】前記制約条件検証手段は制約条件式に人為
   変数の項を付け加えた式を条件式として持ち、人為変数
   が零に近づくほど値が零に近づく人為変数の多項式を目
   的関数として持った最適化問題を上記人為変数の項の係
   数を変化させながら繰り返し解いて矛盾のある制約条件
   を逐次探し出す検証手段を含み、前記表示手段は矛盾を
   見つけ出すために解いた最適化問題の解を矛盾した制約
   条件の中で一部の制約条件が満たされ、他の一部の制約
   条件が満たされていない図形パタ−ンの配置解として少
   なくとも１つ以上表示するものであることを特徴とする
   請求項１に記載の電子部品のレイアウト設計支援装置。