JP3070679B2 - 図形レイアウト圧縮システム及び図形レイアウト圧縮方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、図形レイアウト圧
縮システム及び図形レイアウト圧縮方法に関する。

【０００２】

【従来の技術】大規模半導体集積回路のレイアウトや印
刷配線板のレイアウトの設計には自動レイアウトシステ
ムが利用されている。そして、この種の自動レイアウト
システムに関し、部品を連動して移動する各種のコンパ
クション技術が、従来から提案されている。

【０００３】従来の図形圧縮システムの一例が、特開平
９−２０４４６１号公報「コンパクション装置」（以
下、第１の従来例と呼ぶ）に記載されている。このシス
テムは部品の相対位置関係を保持して部品をコンパクシ
ョンしている。しかしながら、このシステムは、印刷配
線板において部品端子間を配線する前の段階において部
品のみを配置し、その配置をコンパクションしているの
で、部品端子間に配線を有するパターンを圧縮すること
ができないという欠点がある。

【０００４】又、他の従来の図形圧縮システムの例が、
特開平１−２７９７３７４号公報「ＬＳＩレイアウト圧
縮装置」（以下、第２の従来例と呼ぶ）として知られて
いる。これは、集積回路設計においてセルの端子間を配
線した後の段階においてセルと配線とをともにコンパク
ションしている。

【０００５】また、特開昭６２−７８６８１号公報（以
下、第３の従来例と呼ぶ）、特開昭６３−２１４８８０
号公報（以下、第４の従来例と呼ぶ）等の様に、配線を
半導体セルあるいは部品と共にコンパクションする従来
のコンパクション処理には、制約グラフを使った手法を
利用したものが多い。この制約グラフを使ったコンパク
ション手法については配線にジョグと呼ばれる曲げを挿
入することで制約グラフの構造を変更し、これによって
レイアウト面積をより縮小したり、設計規則違反箇所を
修正できるジョグ挿入コンパクション手法が提案されて
いる（文献(1)：山元渉、粟島亭、佐藤政生、大附辰夫
「制約グラフを用いたチップコンパクション手法とその
評価」、信学技報ＶＬＤ91-43pp41-48 １９９１年、文
献(2)：山元渉、粟島亭、佐藤政生、大附辰夫「設計規
則違反を含むレイアウトに対するチップ・スペーサ」、
信学技報ＶＬＤ91-120pp37-44 １９９２年２月７日、
文献(3)：山元渉、粟島亭、佐藤政生、大附辰夫「斜め
配線自動生成機能を持ったチップ・スペーサ」、信学技
報ＶＬＤ91-123pp17-24 １９９２年）。

【０００６】図２８に従来のレイアウト圧縮装置を示
す。図２８に示すように、従来のレイアウト圧縮装置
は、セル配置処理部７１０と、セル間配線処理部７２０
と、最長経路探索手段７３０と、レイアウト拡大手段７
４０と、レイアウト修正指定手段７５０と、レイアウト
自動圧縮手段（コンパクション手段）７６０と、レイア
ウトデータ記憶部７７０と、レイアウト結果表示部７８
０とを有する。

【０００７】このような構成を有する従来のレイアウト
圧縮装置はつぎのように動作する。

【０００８】セル配置処理部７１０は、周知のように、
セル配置の処理を行い、セルのレイアウトを示すレイア
ウトデータをレイアウトデータ記憶部７７０に記憶す
る。

【０００９】セル間配線処理部７２０は、周知のよう
に、セル間配線の処理を行い、配線のレイアウトを示す
レイアウトデータをレイアウトデータ記憶部７７０に記
憶する。

【００１０】最長経路探索手段７３０は、ＬＳＩチップ
上の各セルと配線のレイアウトとをより小さな領域に圧
縮するために、レイアウトデータ記憶部７７０に記憶さ
れているレイアウトにおける最長の図形要素の序列を探
索し、それを図２９（ａ）に斜線で示す様に、レイアウ
ト結果表示部７８０に表示する。

【００１１】レイアウト拡大手段７４０は、図２９
（ｂ）に示す様に、その制約グラフの最長経路を路横切
る空間をレイアウトに挿入する。

【００１２】レイアウト修正指定手段７５０は、操作者
の指令を受けて最長の経路を短くするように、図２９
（ａ）の下から２番目の部品を図２９（ｂ）のように右
に移動する例を示したが、その様に制約グラフの最長経
路から部品を移動させる。

【００１３】そして、コンパクション手段７６０は、修
正した結果のレイアウトを（図２９（ｂ）では上下に）
圧縮する。

【００１４】

【発明が解決しようとする課題】しかし、この従来のコ
ンパクション手段７６０は、レイアウトを縦と横と両方
とも縮小するコンパクションを行なう場合に、先ずどち
らか一方（例えば縦）に縮小し、その後に他方（横）に
縮小するという様に２段階にわたってレイアウトを縮小
する。そのため、先にある方向に（例えば縦に）縮小し
た場合は、その方向に部品が密集し、それが次に垂直方
向に（横に）部品配置と配線レイアウトを縮小する際に
配置の縮小が妨げられるという欠点がある。

【００１５】また、ダイクストラ法を拡張し、縦方向の
移動距離と横方向の移動距離を一緒に評価し、その移動
距離が最短の部品から順にその方向に移動して部品を配
置する手法も考えられる。しかしながら、その場合も、
縦方向あるいは横方向に密集した部品配置が、その後の
過程で部品をその方向に垂直な方向に移動する妨げにな
る欠点がある。

【００１６】この欠点を生じる理由は、次のとおりであ
る。すなわち、従来のコンパクションシステムでは、全
部品を縦方向に基板端に押し当て移動し、その後に全部
品を横方向に基板端に押し当て移動させて圧縮を行なっ
ている。そのため、圧縮後のレイアウトに最初の半導体
セルあるいは部品の配置結果が反映されず、最初の方向
へのコンパクションにより部品配置のバランスがくずれ
る。その結果、次の方向への半導体セルあるいは部品の
コンパクションが妨げられていたためである。

【００１７】この欠点を改善するため、特開昭６３−１
８１３４９号公報「ＬＳＩのレイアウト設計装置」（以
下、第５の従来例と呼ぶ）では、ＬＳＩの配線前に半導
体セルをチップのレイアウトの中心に対して対称な方向
に移動させ、セルがチップの中心方向に集まる様に圧縮
させ、その後にセル間を配線する様にしている。

【００１８】しかし、この第５の従来例は、チップの中
心でレイアウト領域を４分割し、それぞれの領域でコン
パクションするが、それぞれの領域に関しては、その領
域毎にセルを第１の方向にコンパクションした後にそれ
に垂直方向に第２のコンパクションするものであり、そ
の第１のコンパクションの結果がセルを第２のコンパク
ション方向への移動の妨げになる欠点がある。

【００１９】この欠点を生じる理由は、次のとおりであ
る。すなわち、従来のコンパクションシステムでは部品
を縦方向あるいは横方向いずれに移動するにしろ、予め
定まった指定方向へレイアウトを移動するコンパクショ
ンである。その為、部品の移動の指定方向に障害がある
と、部品の移動が妨げられたためである。

【００２０】この欠点を改善するため、２方向を同時に
移動する方法が２次元コンパクションとして提案されて
いる。それは、（文献(4)：Hyunchul Shin, Alberto L.
Sangiovanni-Vincentelli, Carlo H. Sequin,「Two-Di
mensional Compaction by 'Zone Refining'」、Proc.
of 23rd Design Automation Conference,1986,pp115-12
2） で、上下の制約グラフと左右の制約グラフを作成
し、上から下に半導体セルを順次に移動させる。その際
にセルを直下に移動すると同時に左右にも移動させ、セ
ルを適正な位置に配置する。そして、配線には折り目
（ジョグ）を発生させ、下に寄せて配線する。

【００２１】また、特開平５−２７４３９２号公報「レ
イアウト・コンパクション方法」（以下、第６の従来例
と呼ぶ）では、配線を境界とした部分領域に基板を分割
し、その部分領域の部分パターン圧縮部を有し、左の基
板端から基板の部分領域の形を左右に圧縮しつつ、上の
基板端から基板の部分領域の形を上下に圧縮している。
これにより領域の上下左右の関係を維持しつつ基板の全
領域を一様にコンパクションしている。

【００２２】また、ＢＳＧ（Bounded Sliceline-Grid）
で部品を囲む矩形の領域を指定し、この領域の寸法を変
える事で縦横方向を同時にコンパクションする手法が提
案されている（文献(4):坂主圭史、倉澤剛、高島康裕、
中武繁寿、梶谷洋司「ＢＳＧ構造に基づく配置・概略配
線同時最適化手法の提案」、信学技報ＶＬＤ97-40pp175
-182 １９９７年６月）。

【００２３】しかし、これらの従来例は、２次元コンパ
クションあるいは部分コンパクションにより基板の部分
領域を圧縮できるが、配線形状は縦横配線を前提にし、
配線の縦横への伸縮により部分領域の伸縮を行なうもの
であり、斜め配線を扱えない欠点がある。

【００２４】また、特開平１０−３４９１号公報「コン
パクション方泡コンパクション装置、配線方泡配線装
置、概略配線方法及び概略配線装置」（以下、第７の従
来例と呼ぶ）では、元からあるすべての配線をいったん
消去し、配線を新規に行ないつつコンパクションを同時
に実行する事により斜め配線も行なえる様にしている。

【００２５】しかし、この第７の従来例では、配線をコ
ンパクション方向に寄せるため配線の位置が偏り、配線
間のクロストークを軽減するために必要な配線間の間隙
を十分広く取る条件を満たせないという欠点がある。

【００２６】また、いずれの従来例も、プリント配線板
の場合に対して多数の部品端子間に配線が縦横に通るレ
イアウトのコンパクションにおいて、多端子部品の全端
子を間に配線を抱えて移動させる事が困難である。

【００２７】したがって、本発明の目的は、配線、端
子、ビアホール及び多角形導体形状を有する少なくとも
１層のパターンをコンパクションする際に発生する、コ
ンパクション方向に対して垂直方向への部品のコンパク
ションの障害を防止することができる、図形レイアウト
圧縮システムおよび図形レイアウト圧縮方法を提供する
ことにある。

【００２８】本発明の別の目的は、コンパクションの障
害の原因となる部品の配置を変更し、配置の圧縮領域を
小さくできる、図形レイアウト圧縮システムおよび図形
レイアウト圧縮方法を提供することにある。

【００２９】本発明のさらに他の目的は、コンパクショ
ンし部品を移動する距離を部品の配置を一様に圧縮する
目標距離を定め、部品同士の前後左右関係を保つコンパ
クションを行う、図形レイアウト圧縮システムおよび図
形レイアウト圧縮方法を提供することにある。

【００３０】

【課題を解決するための手段】本発明は、上記の目的を
達成するために次のような技術的構成を採用する。

【００３１】すなわち、本発明は、配線、端子、ビアホ
ール及び多角形導体形状を有する少なくとも１層のパタ
ーンをコンパクションする図形レイアウト圧縮システム
および図形レイアウト圧縮方法であって、レイアウトデ
ータを入力して部品端子及びビアホールを層毎の素片デ
ータに分割し、この配線、多角形導体形状を曲がり点及
び分岐点毎の素片データに分割し、連結する素片データ
に共通の部品番号を付す。ここで、個々のビアホール毎
に部品番号を指定する（以後、ビアホールを部品と呼
ぶ）。図形レイアウト圧縮システムは、この各層面毎に
上下、左右の部品端子が、間に挟む配線と必要間隙から
なる配線帯を介して接近し得る距離を記憶する端子制約
グラフデータと部品制約グラフデータを作成する端子制
約グラフ作成手段と、この各部品を部品制約グラフデー
タによりコンパクションする部品コンパクション手段
と、その後に、配線を整形し再配線する再配線手段とを
有する。

【００３２】

【作用】コンパクション方向に垂直方向へ部品のコンパ
クションの障害が生じる対策として、その原因となる部
品の配置を変更し、配置の圧縮領域を小さくできるよう
にした。

【００３３】また、コンパクションし部品を移動する距
離を部品の配置を一様に圧縮する目標距離を定め、部品
同士の前後左右の関係を保つコンパクションを行なう事
でコンパクションの障害の発生を防止する事もできる。

【００３４】端子制約グラフ作成手段は、部品端子（配
線を除く）を節とする端子制約グラフデータを作り、そ
の端子制約グラフデータの節が他端の節に近づく移動量
を、端子制約グラフデータの両端の節の素片番号の間に
挟まれる配線の幅と必要間隙を加えた配線帯を介して部
品の移動方向から接近し得る移動の限界距離を計算し、
部品相対移動限界長として記憶する。そして、端子制約
グラフ作成手段は、同じ部品端子同士の部品相対移動限
界長の最小値をグラフ長として記録する部品制約グラフ
データを作成し、これを用いて部品コンパクション手段
が部品の配置をコンパクションする。

【００３５】

【発明の実施の形態】以下、本発明の実施の形態につい
て図面を参照して詳細に説明する。

【００３６】図１を参照すると、本発明の第１の実施の
形態による図形レイアウト圧縮システムは、プログラム
制御により動作するコンピュータ１００と、表示部１０
１と、操作部とから構成されている。コンピュータ１０
０としては、中央処理装置やプロセッサ或いはデータ処
理装置を使用できる。また、表示部１０１は、例えば、
ＣＲＴディスプレイあるいは液晶ディスプレイ等を使用
できる。さらに、操作部１０２としては、キーボードと
マウスあるいはタブレット等を使用できる。

【００３７】コンピュータ１００は、レイアウトデータ
変換手段１１１、操作指令入力手段１１０、制約グラフ
作成手段１０３、端子制約グラフ作成手段１０４、順位
データ作成手段１０５、部品コンパクション手段１０
７、再配線手段１０９、レイアウトデータ記憶部２０、
素片データ記憶部３０、制約グラフデータ記憶部４０、
端子制約グラフデータ記憶部５０、及び部品制約グラフ
データ記憶部６０とを含む。これらの手段はそれぞれ概
略つぎのように動作する。

【００３８】レイアウトデータ変換手段１１１は、レイ
アウトデータ記憶部２０に記憶されているレイアウトデ
ータの各形状を素片に分解した素片データを作成して、
それを素片データ記憶部３０に記憶する。

【００３９】制約グラフ作成手段１０３は、部品端子、
ビアホール、あるいは配線がＹ方向あるいはＸ方向で隣
接する部品端子あるいは配線の素片データを素片データ
記憶部３０から抽出し、隣接する素片番号３１同士を結
ぶＹ方向あるいはＸ方向の制約グラフデータを作成し
て、それを制約グラフデータ記憶部４０に記憶する。ま
た、本明細書においては、以後、ビアホールを部品と呼
び、基板端も部品と呼ぶことにする。

【００４０】端子制約グラフ作成手段１０４は、部品端
子あるいは部品外形同士を両端の節として記録し、この
一端の節が他端の節に最接近し得る移動の限界を表わし
た部品相対移動限界長６２を記録する端子制約グラフデ
ータを作成して、それを端子制約グラフデータ記憶部４
０に記憶する。また、端子制約グラフ作成手段１０４
は、部品番号３２同士を両端の節として記録し、部品相
対移動限界長６２と端子制約グラフ番号５１を記録する
部品制約グラフデータを作成して、それを部品制約グラ
フデータ記憶部６０に記憶する。

【００４１】順位データ作成手段１０５は、部品制約グ
ラフデータ記憶部６０に記憶されている部品制約グラフ
データのなかから、最短経路の部品制約グラフデータを
選択する。

【００４２】部品コンパクション手段１０７は、部品を
Ｘ方向、あるいはＹ方向（量子化方向）に最短経路長で
移動し配置する。

【００４３】配線コンパクション手段１０８は、配線に
関して、その配線を挟む端子制約グラフデータで表され
る一方の端の部品端子の形に添って配線を寄せて折り曲
げた八角形形状の配線限界位置データを作成し、それを
配線限界位置データ記憶部８０に記憶する。

【００４４】再配線手段１０９は、配線を斜め配線を含
む形状に整形して再配線し、結果として得られるレイア
ウトデータをレイアウトデータ記憶部２０に記憶する。

【００４５】次に、図２および図３のフローチャートを
参照して、本第１の実施の形態に係る図形レイアウト圧
縮システムの全体の動作について詳細に説明する。ま
た、図７から図１１は第１の実施の形態の動作を説明す
るための絵柄を示す平面図であり、図７は本第１の実施
の形態の処理の対象となる印刷配線板の初期のレイアウ
トを示し、図１１は最終結果のレイアウトを示す。

【００４６】先ず、レイアウトデータ変換手段１１１
は、図７に示すようなレイアウトデータを、レイアウト
パターンを構成する部品端子、ビアホール、配線、多角
形導体形状および部品外形、基板外形線、マーキングパ
ターン文字等を層面ごとに分解し、各々を１つの素片デ
ータとし、その形状を八角形に近似した形状で表した素
片データを、図４（ａ）および（ｂ）に示すデータ構造
で記憶する（ステップＳ１００）。

【００４７】詳述すると、レイアウトデータ変換手段１
１１は、部品端子、配線等を信号層、電源グランド層面
に配置するが、部品外形を部品外形層面に配置する。ま
た、レイアウトデータ変換手段１１１は、マーキングと
文字とそれらに干渉する加工穴位置等のマーキング禁止
領域パターンをマーキング層面に配置する。さらに、レ
イアウトデータ変換手段１１１は、信号層面、電源グラ
ンド層面毎に、配線を曲がり角、分岐点、部品端子との
交差点ごとに分解し、多角形導体形状をその辺に分解し
た素片データを作成する。ここで、レイアウトデータ変
換手段１１１は、層面毎に分解した部品の素片データに
個々の部品番号３２を付し、また、ビアホールもビアホ
ール毎に個々の部品番号３２を指定して記録し、各辺の
基板外形線にもそれらに共通な部品番号３２を付して記
録する。以後、本明細書では、基板外形およびビアホー
ルも部品と呼ぶ。

【００４８】図４（ａ）、（ｂ）は、レイアウトデータ
変換手段１１１によって作成された素片データのデータ
構造を示す図である。図４（ａ）に、端子１及びビアホ
ール３の素片データのデータ構造を示し、図４（ｂ）に
配線２及び多角形導体形状の素片データのデータ構造を
示す。

【００４９】図４（ａ）に示すように、部品端子あるい
はビアホールの素片データでは、１つの部品に係わる端
子の全素片に同じ部品番号３２を記録し、１つのビアホ
ール３の全層面の素片データに同じ部品番号３２を記録
する。また、部品端子あるいはビアホールの素片データ
には、素片の形状を記録する形状データ３５（図４
（ｄ））の形状番号３６が記録される。部品端子１ある
いはビアホール３に接続される配線２の素片データに
は、配線の位置に対して、配線の端が接続される端子１
あるいはビアホール３あるいは他の配線２の端と同じ位
置番号３３が記録され、また、配線の幅を表わす図形の
形状番号３６が記録される。

【００５０】また、図４（ｃ）に示されるように、位置
データ３４には座標値と層面番号が記録され、その位置
番号３３が結びついている部品番号３２が記録される。

【００５１】一方、図形の各形状は、図４（ｄ）に示す
図形の形状データ３５で記述し記憶し、図形の形状番号
３６と、図形の上下の幅と、左右の幅と、右上がり斜め
４５度方向の幅と、右下がり斜め４５度の幅とを記憶
し、図形を八角形状で表わす。

【００５２】また、多角形導体形状４の素片データは、
多角形導体形状４の各片を固定形状と記録した線分の素
片データとし、図４（ｂ）のデータ構造で記憶する。

【００５３】ここで、この印刷配線板の初期のレイアウ
トは、隣接する配線２及び端子１及びビアホール３及び
多角形導体形状４の間隙が設計ルールの最小間隙を守ら
ず配置された場合であっても適用可能である。設計ルー
ルの最小寸法以下の間隙は、後に説明する様に、本第１
の実施の形態による処理の過程において、是正されるか
らである。

【００５４】次に、ステップＳ１０１では、最初に、コ
ンパクション方向をＹ方向に定め、以下のステップＳ１
０２からステップＳ１１２の処理を行なう。その後に、
ステップＳ１０１では、コンパクション方向をＸ方向に
定め、同様に処理し、両方向へコンパクションを終えた
時に処理を終える。

【００５５】ステップＳ１０１に続くステップＳ１０２
では、制約グラフ作成手段１０３が、層面毎に、素片デ
ータ記憶部３０から素片データを層面内のＸ座標値の順
で読み出し、その素片番号３１をＹ座標値の順でＹ方向
に並べる順位を定め、素片番号３１がＹ方向（コンパク
ション方向）で隣接する素片番号３１とのＹ方向の順を
得、図５（ａ）に示す様に、その順の素片番号３１の一
対を記録するＹ方向の制約グラフデータを作成する。こ
の制約グラフデータでは、同じ信号名３７の素片番号３
１同士はお互いに透明とし、それらの同じ信号名３７の
素片番号３１は他の信号名３７の素片番号３１から並列
に接続される。そして、制約グラフ作成手段１０３は、
制約グラフデータをその記録する（Ｙ方向で下側の）素
片番号３１の順に並べる順位を計算し、Ｙ方向制約グラ
フ順位データ（図示せず）にその制約グラフ番号の順を
記録する。

【００５６】次に、端子制約グラフ作成手段１０４は、
図３に示す以下のステップＳ１０３１からＳ１０３６に
おいて、制約グラフデータで隣接関係を記憶した素片デ
ータを連結した経路を計算し、両端に部品端子を持つ経
路を得、図５（ｂ）にデータ構造を示す端子制約グラフ
データを作成する。

【００５７】まず、ステップＳ１０３１では、端子制約
グラフ作成手段１０４は、制約グラフデータ記憶部４０
から、Ｙ方向の全ての制約グラフデータを、下の基板端
から上の基板端まで、Ｙ方向制約グラフ順位データが記
憶する順に読み出し、その節の素片番号３１（下側を第
１の素片と呼び、上側を第２の素片と呼ぶ）を得る。

【００５８】次に、端子制約グラフ作成手段１０４は、
図５（ｃ）に示されるような、第１の素片を記録する種
端子グラフデータ５３（後述するステップＳ１０３２で
作成する）を抽出し、該当する種端子グラフデータ５３
がない場合であって、かつ第１の素片が部品端子の場合
はステップＳ１０３２に進む。一方、第１の素片を記録
した種端子グラフデータ５３が存在する場合において、
第２の素片が配線の場合はステップＳ１０３４に進み、
第２の素片が部品端子の場合はステップＳ１０３５に進
む。そして、Ｙ方向制約グラフ順位データの全ての制約
グラフデータを処理した場合はステップＳ１０４に進
む。

【００５９】ステップＳ１０３２では、端子制約グラフ
作成手段１０４は、第１の素片が部品端子の場合には、
その部品端子の素片番号３１（下素片）を下端とする種
端子グラフデータ５３を作成し、また、種端子グラフデ
ータ５３に、その制約グラフデータの上の配線素片番号
３１を、間に挟む配線素片番号３１として記録する。そ
して、端子制約グラフ作成手段１０４は、この種端子グ
ラフデータ５３に関して、その配線の幅と配線の上下の
必要間隙の幅を加えた値を配線帯幅５２として計算して
種端子グラフデータ５３に記録し、下側の部品端子の横
方向（Ｘ方向）の幅に配線帯幅５２を加えた配線抑制領
域幅を計算し、それを種端子グラフデータ５２に記憶す
る。そして、ステップＳ１０３１に戻る。

【００６０】ステップＳ１０３４では、端子制約グラフ
作成手段１０４は、第２の素片が配線の場合には、第１
の素片を記録する種端子グラフデータ５３を抽出し、種
端子グラフデータ５３毎に以下の処理を行なう。

【００６１】すなわち、端子制約グラフ作成手段１０４
は、第２の素片の配線の両端のＸ座標の幅が種端子グラ
フデータ５３の配線抑制領域のＸ座標の幅と重なる場合
には、種端子グラフデータ５３を新たな種端子グラフデ
ータ５３に複写し、その新データに第２の素片の素片番
号３１を加えて記録する。また、端子制約グラフ作成手
段１０４は、加えた配線の幅と必要間隙を旧データの配
線抑制領域幅に加えた配線抑制領域幅を計算して種端子
グラフデータ５３に記録し、旧データの遮蔽領域の幅も
上素片の配線の幅と必要間隔を加えた値を種端子グラフ
データ５３に記録する。そして、端子制約グラフ作成手
段１０４は、旧データには、第２の素片のＸ座標の幅を
遮蔽領域幅として種端子グラフデータ５３に記録する。
種端子グラフデータ５３の配線抑制領域が遮蔽領域で完
全に覆われた場合には、端子制約グラフ作成手段１０４
は、種端子グラフデータ５３を消去する。

【００６２】ステップＳ１０３５では、端子制約グラフ
作成手段１０４は、第２の素片が部品端子の場合には、
第１の素片を記録する種端子グラフデータ５３を抽出
し、種端子グラフデータ５３毎に以下の処理を行なう。
また、全ての種端子グラフデータ５３を処理した場合は
ステップＳ１０３１に戻る。

【００６３】すなわち、端子制約グラフ作成手段１０４
は、第２の素片のＸ座標の幅が種端子グラフデータ５３
の配線抑制領域のＸ座標の幅と重なる場合（以下の式１
が成り立つ場合）に、図４（ｂ）の様に、第２の素片の
部品端子素片番号３１を上端の部品端子として記録し、
種端子グラフデータ５３の下端の端子素片番号３１を記
録し、両者をグラフの節とし、また、種端子グラフデー
タ５３の配線帯幅５２をその間の配線帯幅５２として記
録する端子制約グラフデータを作成する。また、端子制
約グラフ作成手段１０４は、その種端子グラフデータ５
３に、上素片の部品端子に係る素片データのＸ座標の幅
を遮蔽領域幅として記録する。そして、端子制約グラフ
作成手段１０４は、種端子グラフデータ５３の配線抑制
領域が遮蔽領域で完全に覆われた場合に種端子グラフデ
ータ５３を消去する。そして、次のステップＳ１０３６
に進む。

【００６４】また、このステップＳ１０３５において
は、端子制約グラフ作成手段１０４は、上素片の素片デ
ータのＸ座標の幅を所定距離で拡大した範囲で計算する
事で、上素片と下素片がＸ方向で所定距離隔たっている
場合にもそれらを両端とする端子制約グラフデータを作
成する事もできる。更に、端子制約グラフ作成手段１０
４は、下素片による配線抑制領域を長方形とし、下素片
のＸ方向とＹ方向の幅に配線帯幅５２を加算した幅を配
線抑制領域のＸ方向とＹ方向の幅として以上のＳ１０３
以降の処理を行なう事もできる。

【００６５】ステップＳ１０３６では、端子制約グラフ
作成手段１０４は、以下のようにして図６に示すＹ方向
の部品相対移動限界長６２を計算する。すなわち、端子
制約グラフ作成手段１０４は、以下の様にして、上素片
と下素片の間に自由に斜めに曲げられる配線帯を介して
部品が移動方向（図示せず）に移動し得る部品相対移動
限界長６２（Ｍ）を計算する。詳述すると、図６に示す
様にＹ方向の座標軸をＱ軸とし、それに垂直方向をＶ軸
とすると、図６の上下の部品端子の相対座標を（Ｖ，
Ｑ）とし、両端子のＶ方向の半径の和と配線帯幅５２の
和をＢvと表わし、両端子のＱ方向の半径の和と配線帯
幅５２の和をＢqと表わし、両端子を座標Ｖ＋Ｑに投影
した、端子の中心から他端の端子まで計った半径の和と
配線帯幅５２の和をＢzと表わし、両端子を座標Ｑ−Ｖ
に投影した、端子の中心から他端の端子まで計った半径
の和と配線帯幅５２の和をＢwと表わし、以下の式でＭ
の最小値を求め、それを部品相対移動限界長６２とす
る。

【００６６】 −Ｂv＜Ｖ＜Ｂv ・・・（式１） Ｕ＜＝Ｂq ・・・（式２） Ｕ＜＝Ｂz−Ｖ ・・・（式３） Ｕ＜＝Ｂw＋Ｖ ・・・（式４） Ｍ＝Ｑ−Ｕ ・・・（式５）。

【００６７】端子制約グラフ作成手段１０４は、このＹ
方向の部品相対移動限界長６２をグラフの長さとした端
子制約グラフデータを端子制約グラフデータ記憶部５０
に記憶する。

【００６８】更に、図５（ｄ）にデータ構造を示す様
に、端子制約グラフ作成手段１０４は、Ｙ方向の端子制
約グラフデータの両端の端子の部品番号３２を節として
記録し、Ｙ方向の部品相対移動限界長６２を記録し、端
子制約グラフ番号５１を記録した部品制約グラフデータ
（図７に点線で示す）を作成し、それを部品制約グラフ
データ記憶部６０に記憶する。ここで、既存のこの部品
制約グラフデータが部品制約グラフデータ記憶部６０に
ある場合には、端子制約グラフ作成手段１０４は、その
Ｙ方向の部品相対移動限界長６２をより少ない値に更新
して記録する。次に、他の種端子グラフデータ５３に対
してステップＳ１０３５を繰り返す。

【００６９】引き続くステップＳ１０４では、以下の様
にして、順位データ作成手段１０５はＹ方向の最短経路
を計算する。すなわち、順位データ作成手段１０５は、
ダイクストラ法によるコンパクション手法により、基板
端からＹ方向の部品制約グラフデータの最短経路を核と
し、その最短経路の節の部品端子に接続するＹ方向の部
品制約グラフデータを抽出する。そして、順位データ作
成手段１０５は、その接続する部品の最短経路長に部品
制約グラフデータの部品相対移動限界長６２を加えた値
を他端の部品番号３２のＹ方向の経路長とする。順位デ
ータ作成手段１０５は、このうち経路長が一番短い部品
制約グラフデータ（選択グラフ）を選び、その経路長を
その端の部品番号３２の最短経路長とし、この部品制約
グラフデータを最短経路に加える。なお、本明細書で
は、その節（枝側節）の部品番号３２を選択部品と呼
ぶ。

【００７０】次に、ステップＳ１０５では、部品コンパ
クション手段１０７は、選択部品に対して、その各端子
（選択端子）を抽出し、順次に選択端子をＹ方向にその
最短経路長で移動させ配置する。また、選択部品の全て
の選択端子を処理した場合はステップＳ１０４に戻る。

【００７１】以上のステップＳ１０４からステップＳ１
０５の処理を繰り返して、部品制約グラフデータ６０を
順次、最短経路に登録し、部品レイアウトをコンパクシ
ョンする。この際に、印刷配線板の初期のレイアウトに
おいて、隣接する配線２及び端子１及びビアホール３及
び多角形導体形状４の間隙が設計ルールの最小間隙を守
らず配置された場合であっても、設計ルールの最小寸法
以下の間隙は、以上の処理の過程において、是正され
る。

【００７２】次に、ステップＳ１１１では、配線コンパ
クション手段１０８は、Ｙ方向制約グラフ順位データに
記録した順に配線の素片番号３１（処理配線素片）を読
み出し、その配線素片番号３１を記録する端子制約グラ
フデータを端子制約グラフデータ記憶部５０から抽出す
る。そして、配線コンパクション手段１０８は、抽出し
た端子制約グラフデータの両端の部品端子側に、その間
に存在する他の配線と必要間隔と処理配線素片の幅の半
径を合わせた配線帯幅５２を計算し、その部品端子の縦
横斜めの八方向の幅に配線帯幅５２を加えた八角形形状
の配線抑制領域の形状データ３５を作成する。ただし、
既に位置が確定した配線が間に存在する場合には、配線
コンパクション手段１０３は、その配線を固定形状と
し、その固定形状の周りに変形自由な配線束を自由に折
り曲げ固定形状を包む八角形形状の配線抑制領域の形状
データ３５を作成する。そして、配線コンパクション手
段１０８は、図４（ｅ）にデータ構造を示す配線限界位
置データに、その形状番号３６を記録し、処理配線素片
番号３１を記録し、その部品端子の素片番号３１を記録
し、部品端子の位置番号３３を記録する。

【００７３】次に、ステップＳ１１２では、再配線手段
１０９は、処理配線を配線限界位置データの配線抑制領
域外に斜めの配線形状を含む整った形状に再配線する。

【００７４】次に、ステップＳ１０１に戻り、Ｘ方向に
対して、同様の処理を繰り返してＸ方向にコンパクショ
ンする。

【００７５】この様にステップＳ１０１からステップＳ
１１２の処理でＹ方向にコンパクションし、同様に繰り
返してＸ方向にコンパクションする。

【００７６】次に、図７、図８〜図１１を参照して、本
発明の第１の実施の形態に係る図形レイアウト圧縮シス
テムの具体的な動作例について、更に説明する。

【００７７】図７は印刷配線板のレイアウトの初期配置
状態を示す。最初に、コンパクション方向をＹ方向に定
め、部品コンパクション手段１０７が、この部品を下に
コンパクションして図８を得る。次に、配線コンパクシ
ョン手段１０８が、図８に点線で示す様に、配線限界位
置データを計算する。そして、再配線手段１０９が、図
９に示す様に、配線を斜めの配線形状を含む整った形状
に再配線する。

【００７８】次に、コンパクション方向をＸ方向に定
め、端子制約グラフ作成手段１０４が、図１０に示す様
に、部品制約グラフデータを作成する。そして、部品コ
ンパクション手段１０７が、部品を左にコンパクション
して図１１を得、配線コンパクション手段１０８及び再
配線手段１０９により、図１１に示す様に、配線を斜め
の配線形状を含む整った形状に再配線する。

【００７９】次に、上述した第１の実施の形態に係る図
形レイアウト圧縮システムの効果について説明する。

【００８０】第１の効果は、配線をコンパクション方向
に偏りを持たない、周囲の部品端子及び配線との間隙を
保った自由な形状に配線できることである。その理由
は、先ず、配線領域を確実に確保した部品の部品のコン
パクション配置を行ない、その後に配線限界位置データ
を計算し、その制限範囲内で配線を自由な形に配線する
ためである。

【００８１】第２の効果は、同一信号名３７の配線が初
期の互いの相対関係に束縛されず、お互いの位置に影響
されずに自由に配線出来ることである。その理由は、同
一信号名３７の配線をお互いに透明とする制約グラフデ
ータを作成するためである。

【００８２】図１２を参照すると、本発明の第２の実施
の形態による図形レイアウト圧縮システムは、上記第１
の実施の形態と同様に、プログラム制御により動作する
コンピュータ１００と、表示部１０１と、操作部１０２
とから構成されている。コンピュータ１００としては、
中央処理装置、プロセッサ、およびデータ処理装置のい
ずれを使用しても良い。表示部１０１は、例えば、ＣＲ
Ｔディスプレイあるいは液晶ディスプレイ等などであ
る。また、操作部１０２としては、キーボードとマウス
あるいはタブレット等を使用できる。

【００８３】第２の実施の形態に係る図形レイアウト圧
縮システムは、コンピュータ１００が、第１の実施例の
各手段に加え、制約グラフ更新手段１１２を有する。

【００８４】この制約グラフ更新手段１１２の概略動作
は、部品とそれに接続する配線の移動による制約グラフ
の変更を計算し、制約グラフデータを更新する。

【００８５】次に、図１３、図１４、および図１５のフ
ローチャートを参照して、第２の実施の形態に係る図形
レイアウト圧縮システムの全体の動作について詳細に説
明する。また、図１６は第２の実施の形態の動作を説明
するための絵柄を示す平面図である。第２の実施の形態
の処理の対象となる印刷配線板の初期のレイアウトは、
第１の実施の形態と同様に図７とする。

【００８６】先ず、レイアウトデータ変換手段１１１
は、第１の実施の形態と同様に、レイアウトデータから
素片データを作成する（ステップＳ１００）。

【００８７】次に、ステップＳ２０２において、制約グ
ラフ作成手段１０３は、層面毎に、素片データ記憶部３
０から素片データを層面内のＸ座標値の順で読み出し、
その素片データをＹ座標値の順でＹ方向に並べる順位を
定め、素片番号３１がＹ方向（コンパクション方向）で
隣接する素片番号３１とのＹ方向の順を得、図５（ａ）
に示す様に、その順の素片番号３１の一対を記録するＹ
方向の制約グラフデータを作成する。そして、制約グラ
フ作成手段１０３は、制約グラフデータをその記録する
（Ｙ方向で下側の）素片番号３１の順に並べる順位を計
算し、Ｙ方向制約グラフ順位データにその制約グラフ番
号４１の順を記録する。また、第２の実施の形態では、
制約グラフ作成手段１０３は、、Ｘ方向に対しても制約
グラフデータとＸ方向制約グラフ順位データを作成して
おく。

【００８８】次に、端子制約グラフ作成手段１０４は、
第１の実施例と同様にして、図３に示すステップＳ１０
３１からＳ１０３６において、Ｙ方向制約グラフデータ
で隣接関係を記憶した素片データを連結した経路を計算
し、両端に部品端子を持つ経路を得、図５（ｂ）にデー
タ構造を示すＹ方向の端子制約グラフデータを作成す
る。

【００８９】次にのステップＳ２０４では、順位データ
作成手段１０５は、ダイクストラ法によるコンパクショ
ン手法により、基板端からＹ方向の部品制約グラフデー
タの最短経路を核とし、その最短経路の節の部品端子に
接続するＹ方向の部品制約グラフデータを部品制約グラ
フデータ記憶部４０から抽出する。そして、順位データ
作成手段１０５は、その接続する部品の最短経路長に部
品制約グラフデータの部品相対移動限界長６２を加えた
値を他端の部品番号３２のＹ方向の経路長とする。順位
データ作成手段１０５は、このうち経路長が一番短い部
品制約グラフデータ（選択グラフ）を選び、その経路長
をその端の部品番号３２の最短経路長とし、この部品制
約グラフデータを最短経路に加える。尚、本明細書で
は、その節（枝側節）の部品番号３２を選択部品と呼
ぶ。順位データ作成手段１０５は、ここで、選択グラフ
を選び最短経路長を計算する以前のデータ状態を後のス
テップＳ２１６で復元するのに必要なデータ一式を記憶
する。

【００９０】図１４に移って、次に、ステップＳ２０５
では、部品コンパクション手段１０７は、選択部品に対
して、その各端子（選択端子）を抽出し、順次に選択端
子をＹ方向にその最短経路長で移動させ配置し、次のス
テップＳ２０６に進む。また、選択部品の全ての選択端
子を処理した場合はステップＳ２１０に進む。

【００９１】次に、ステップＳ２０６では、制約グラフ
更新手段１１２は、図１７（ａ）の端子１に配線３が接
続する様に、移動以前の選択端子に配線素片番号３１
（変更配線素片）が配線の上端で接続する場合には以下
の処理を行ない、それ以外の場合にはステップＳ２０７
に進む。すなわち、制約グラフ更新手段１１２は、移動
以前の変更配線素片にＸ方向制約グラフデータで左右に
接続する素片番号３１同士に関して、変更配線素片のＹ
方向下への移動（選択端子の移動が変更配線素片の両端
の上下関係を逆転させない範囲の移動で）の結果、Ｘ方
向で干渉する隣接関係の解消の有無を計算する。例え
ば、図１７（ａ）のレイアウトから端子１が移動する結
果、図１７（ｂ）の様に、配線３と配線７、配線３と配
線４、配線３と配線８を結ぶＸ方向制約グラフデータの
隣接関係が消える。そして、制約グラフ更新手段１１２
は、この様に隣接関係が消えたＸ方向制約グラフデータ
を消去する。また、図１７（ｂ）で配線４と配線８の隣
接関係が新たに生じるが、制約グラフ更新手段１１２
は、消去した制約グラフデータの外側の素片番号３１同
士の隣接関係を計算し、新たに生じた隣接関係を表わす
制約グラフデータを新たに作成する。

【００９２】そして、制約グラフ更新手段１１２は、変
更配線素片番号３１を記録するＸ方向端子制約グラフデ
ータに対して、変更配線素片の変形結果を用いて端子制
約グラフデータの両端の配線帯の幅を計算し記録する値
を更新し、その左側端子にＸ方向に配線帯を重ねて計算
した配線抑制領域のＹ座標の幅と右側端子のＹ座標の幅
の重なりを計算する。その重なりが解消した場合に、制
約グラフ更新手段１１２は、そのＸ方向端子制約グラフ
データを削除し、削除されない場合も、Ｘ方向の相対移
動限界長６２を更新して記録する。次に、ステップＳ２
０７に進む。

【００９３】次に、ステップＳ２０７では、更新グラフ
更新手段１１２は、図１７（ａ）の端子１及び配線３等
の選択端子及び変更配線素片に、図１７（ａ）の配線
７、配線４、配線８等の様に、Ｘ方向制約グラフデータ
で接続する素片番号３１（隣接素片）を抽出し、それら
の隣接素片のうち、図１７（ｂ）の配線４、配線８の様
に、その素片の下端が選択端子及び変更配線素片の下端
よりも下にある素片番号３１を抽出し、それを最初の抽
出素片とする。

【００９４】次に、ステップＳ２０８は、制約グラフ更
新手段１１２は、抽出素片に接続するＸ方向制約グラフ
データのうち、図１７（ａ）の配線４と配線８の様に、
Ｘ方向制約グラフデータで、その記録する両端の素片番
号３１（第３の素片）のＸ座標が選択端子のＸ座標を間
に挟み、かつ、両端の素片の最上端がともに選択端子の
Ｙ方向下への移動後の最下端よりも上にあり、選択端子
の移動する軌跡の範囲と重なるＸ方向制約グラフデータ
を抽出する。これを抽出グラフと呼ぶ。また、制約グラ
フ更新手段１１２は、先の抽出素片（複数）のうち抽出
グラフが接続しない抽出素片を削除する。

【００９５】次に、図１７（ａ）の配線５が抽出素片の
配線４に接続する様に、制約グラフ更新手段１１２は、
抽出素片にＸ方向制約グラフデータで接続する素片番号
３１を抽出し（既に一端抽出素片とされた素片を除
く）、その上端がその接続する抽出素片の上端よりも下
にある素片を新たに抽出素片に加える。こうして、制約
グラフ更新手段１１２は、新たに加えた抽出素片に接続
する抽出グラフを、配線５と配線９、配線６と配線１０
の様に順次抽出する。この際に、制約グラフ更新手段１
１２は、図１７（ｃ）の端子１に配線３の下端が接続す
る様に、選択端子の移動により変更配線素片の下端が選
択端子に接続し移動する場合には、この抽出グラフを分
割グラフ配列（図示せず）に記憶する。こうして、順次
抽出素片と抽出グラフを抽出し、新たに加わる抽出素片
が無くなった場合はステップＳ２０９に進む。

【００９６】ステップＳ２０９では、制約グラフ更新手
段１１２は、分割グラフ配列から、抽出グラフを読み出
し、その両端の素片番号３１と変更配線素片を記録する
Ｘ方向制約グラフデータを作成する。また、制約グラフ
更新手段１１２は、移動以後の位置の選択端子と抽出グ
ラフの素片番号３１のＸ方向の隣接関係を計算し、隣接
関係が存在する場合には、両者を記録するＸ方向制約グ
ラフデータを作成する。

【００９７】そして、制約グラフ更新手段１１２は、抽
出グラフの両端の素片番号３１のＸ方向の隣接関係が変
更配線素片の挿入により妨げられる場合には、その制約
グラフデータを消去する。

【００９８】そして、制約グラフ更新手段１１２は、Ｘ
方向制約グラフ順位データを変更配線素片の変更により
更新する。次に、ステップＳ２０５に戻る。

【００９９】図１５に図示した、以下に説明するステッ
プＳ２１０からＳ２１３では、端子制約グラフ作成手段
１０４は、Ｙ方向に移動した選択端子毎にそれとＸ方向
で接続する端子制約グラフデータと部品制約グラフデー
タを作成する。

【０１００】まず、ステップＳ２１０では、端子制約グ
ラフ作成手段１０４は、選択端子を左端として記録する
（左）種端子グラフデータ５３を作成し、選択端子を右
端として記録する（右）種端子グラフデータ５３を作成
する。また、端子制約グラフ作成手段１０４は、選択端
子の縦横斜めの八方向の幅に必要間隙を加えた八角形形
状の配線抑制領域のＹ座標の幅を計算し種端子グラフデ
ータ５３に記憶する。

【０１０１】次に、ステップＳ２１１では、端子制約グ
ラフ作成手段１０４は、（左右の）種端子グラフデータ
５３毎に、選択端子に接続する制約グラフデータを、Ｘ
方向制約グラフ順位データが左右の順を記憶する順に
（右左に）読み出し、制約グラフデータの記録する素片
番号３１（選択端子に近い側を第１の素片と呼び、遠い
側を第２の素片と呼ぶ）を得る。第１の素片が種端子グ
ラフデータ５３に記録されている場合において、第２の
素片が配線の場合にはステップＳ２１２に進み、第２の
素片が部品端子の場合にはステップＳ２１３に進む。第
１の素片が種端子グラフデータ５３に記録されていない
場合には、端子制約グラフ作成手段１０４は、更にＸ方
向制約グラフ順位データを読み出し同様に処理する。ま
た、全ての種端子グラフデータ５３を処理し終えた場合
はステップＳ２１４に進む。

【０１０２】ステップＳ２１２では、端子制約グラフ作
成手段１０４は、第２の素片が配線の場合には、その配
線の両端のＹ座標の幅が種端子グラフデータ５３の配線
抑制領域のＹ座標の幅と重なる場合に、種端子グラフデ
ータ５３を新たな種端子グラフデータ５３に複写し、更
に、その新データに第２の素片の素片番号３１を加えて
記録し、また、第２の素片の配線幅と必要間隙を旧デー
タの配線抑制領域幅に加えた配線抑制領域幅を計算して
記録し、旧データの遮蔽領域幅に第２の素片の配線幅と
必要間隙を加えて記録する。そして、端子制約グラフ作
成手段１０４は、旧データには、第２の素片のＹ座標の
幅を遮蔽領域幅として記録し、種端子グラフデータ５３
の配線抑制領域が遮蔽領域で完全に覆われた場合に種端
子グラフデータ５３を消去する。次に、ステップＳ２１
１に戻る。

【０１０３】ステップＳ２１３では、端子制約グラフ作
成手段１０４は、第２の素片が部品端子の場合におい
て、その第２の素片のＹ座標の幅が種端子グラフデータ
５３の配線抑制領域のＹ座標の幅と重なる場合には、第
２の素片を選択端子とともに両端の節として記録する。
また、図３に示すステップＳ１０３５と同様にして、端
子制約グラフ作成手段１０４は、Ｘ方向の部品相対移動
限界長６２を計算し、それを記録するＸ方向の端子制約
グラフデータと部品制約グラフデータを作成する。そし
て、端子制約グラフ作成手段１０４は、その種端子グラ
フデータ５３に、上素片の部品端子素片データのＹ座標
の幅を遮蔽領域幅として記録する。そして、種端子グラ
フデータ５３の配線抑制領域が遮蔽領域で完全に覆われ
た場合には、端子制約グラフ作成手段１０４は、種端子
グラフデータ５３を消去する。次に、ステップＳ２１１
に戻り、次の種端子グラフデータ５３を処理する。

【０１０４】ステップＳ２１４では、端子制約グラフ作
成手段１０４は、選択部品の部品端子に接続する変更配
線素片の素片番号３１を左側に記録するＸ方向制約グラ
フデータを抽出し、その右側の素片番号３１（右素片）
を得る。そして、端子制約グラフ作成手段１０４は、そ
の右素片を記録するＸ方向端子制約グラフデータを抽出
し、その右端の部品端子の素片番号３１（右端子）を抽
出し、抽出した端子制約グラフ番号５１と右端子の素片
番号３１を右端子配列（図示せず）に記録する。同様に
端子制約グラフ作成手段１０４は、変更配線素片を右側
に記録するＸ方向制約グラフデータを抽出し、その左側
の素片番号３１（左素片）を得る。そして、端子制約グ
ラフ作成手段１０４は、その左素片を記録するＸ方向端
子制約グラフデータを抽出し、その左端の部品端子の素
片番号３１（左端子）を抽出し、抽出した端子制約グラ
フ番号５１と左端子の素片番号３１を左端子配列（図示
せず）に記録する。

【０１０５】そして、端子制約グラフ作成手段１０４
は、左端子配列と右端子配列とを組み合わせ、左端子制
約グラフデータの左端子から変更配線素片まで至る配線
の素片番号３１を読み出す。また、端子制約グラフ作成
手段１０４は、右端子制約グラフデータの右端子から変
更配線素片まで至る配線の素片番号３１を読み出す。そ
して、端子制約グラフ作成手段１０４は、この左端子か
ら右端子までの素片番号３１の配線と変更配線素片の配
線幅と必要間隙の総和を配線帯幅５２として計算する。
また、端子制約グラフ作成手段１０４は、その値と左端
子と右端子のＹ方向の（互いに向き合う側の）半径の和
の値が両端子のＹ方向の間隔以上の場合には、両端子を
両端とするＸ方向の端子制約グラフデータを作成する。
そして、（第１の実施の形態で詳述した）図３に示すス
テップＳ１０３６と同様の手順で、端子制約グラフ作成
手段１０４は、Ｘ方向の部品相対移動限界長６２を計算
し、その値をＸ方向の端子制約グラフデータに記録し、
部品制約グラフデータに記録する。これを全ての右端子
配列７２と左端子配列７３の組み合わせに対して処理し
た後に、ステップＳ２１５に進む。

【０１０６】ステップＳ２１５では、端子制約グラフ作
成手段１０４は、新規に作成したＸ方向の部品制約グラ
フデータを含む全部品制約グラフデータを、ダイクスト
ラ法により基板の最左端からＸ方向まで最短経路の部品
制約グラフデータを順次連結し、右端の板端まで結ぶ部
品制約グラフデータの最短経路を求める。その最短経路
長は右端の板端が左端の板端に向けて移動する移動距離
を意味する。端子制約グラフ作成手段１０４は、それを
コンパクションによる基板端の必要縮小距離と比較し、
この最短経路長がＸ方向の必要縮小距離に満たない場合
には、Ｘ方向のコンパクションネックが検出される。そ
の場合は、以下のステップＳ２１６に進む。そうで無い
場合はステップＳ２０４に戻り処理を繰り返す。

【０１０７】図１３に戻って、ステップＳ２１６では、
端子制約グラフ作成手段１０４は、選択部品の端子とＸ
方向の端子制約グラフデータで連結する相手の部品の端
子をグラフの両端の節とする端子制約グラフデータを計
算し、両端の端子をＹ方向に投影した場合にその影がそ
の間の配線帯を介して最接近し得る位置までのＹ方向の
移動距離を計算し、それをＹ方向部品相対移動限界長６
２とするＹ方向の部品制約グラフデータ（端子排除グラ
フ４３）を作成追加する。また、端子制約グラフ作成手
段１０４は、部品制約グラフデータのＹ方向の最短経路
の記録をステップＳ１０４の選択部品の選択以前に戻
す。

【０１０８】このようにして、Ｘ方向の部品レイアウト
が制限範囲を逸脱しないようにコンパクションを制御す
る、図１４および図１５に示す以上のステップＳ２０４
からステップＳ２１６の処理を繰り返し、部品制約グラ
フデータを順次登録する。

【０１０９】次に、部品コンパクション手段１０７は、
Ｘ方向に部品をその最短経路長で移動し配置する（ステ
ップＳ２１７）。

【０１１０】次に、配線コンパクション手段１０８は、
第１の実施の形態のステップＳ１１１と同様に、配線限
界位置データを作成する（ステップＳ１１１）。

【０１１１】最後に、再配線手段１０９は、第１の実施
の形態のステップＳ１１２と同様に、処理配線を配線限
界位置データの配線抑制領域外に斜めの配線形状を含む
整った形状に再配線する（ステップＳ１１２）。

【０１１２】次に、図１８を参照して、本発明の第２の
実施の形態に係る図形レイアウト圧縮システムの具体的
な動作例について更に説明する。

【０１１３】図１８（ａ）は初期配置状態のレイアウト
を示す図である。これを下にコンパクションして、図１
８（ｂ）を得るが、部品のＸ方向の制約グラフデータの
経路長を４部品までに制限する。そのため、部品１から
部品４までは下に移動するが、部品５をこの行に加える
とＸ方向の部品列による制約グラフデータの経路長が制
限を超えるため、部品５はこの下の行まで降ろさず、次
の行に配置する。部品５に続いて部品６から部品８まで
を下に移動して、次の行に配置する。部品９をこの行に
加えるとＸ方向の制約グラフデータの経路長が制限を超
えるため、部品９はこの行まで降ろさず次の行に配置す
る。次の行は、部品９に続いて部品１０から部品１２ま
でを配置し、部品１３はその上の行に配置する。上の行
には部品１４から部品１６が配置できる。

【０１１４】こうして下に部品をコンパクションしたレ
イアウト（図１８（ｂ））から、部品を左にコンパクシ
ョンして、図１８（ｃ）を得る。

【０１１５】次に、本発明の第２の実施の形態に係る図
形レイアウト圧縮システムの効果について説明する。

【０１１６】その効果は、Ｙ方向のコンパクションによ
り形成するレイアウトのＸ方向の最長経路長が限界値以
内におさえられるので、後に行なうＸ方向のコンパクシ
ョンによるＸ方向の基板寸法を制限範囲におさめる事が
できることである。

【０１１７】その理由は、次に述べる２つの機能を有す
るためのである。第１の機能は、部品番号３２同士を結
ぶグラフの長さを両端の部品の部品相対移動限界長６２
とした部品制約グラフデータを作り、基板端からグラフ
の節の部品に至る最短経路長をその部品のコンパクショ
ン移動量として計算する事により、部品のコンパクショ
ン移動位置を自動的に計算できる機能である。第２の機
能は、コンパクション方向に垂直方向の基板端のコンパ
クション移動可能な距離が必要距離に満たない原因の部
品を検出し、その部品と隣接する部品同士をコンパクシ
ョン方向に結ぶ端子排除グラフ４３を部品制約グラフデ
ータで作成する事で、コンパクション方向に垂直方向の
部品の密度を制御する機能である。

【０１１８】本発明の第３の実施の形態による図形レイ
アウト圧縮システムは、第１の実施の形態と同じ図１の
構成を持つ。第３の実施の形態では、最短経路解消手段
（図示せず）を有し、これは、部品コンパクション手段
１０７が部品制約グラフデータの最短経路を計算した後
に、最短経路のビアホールを最短経路を解消する方向に
移動して最短経路を解消し、コンパクションの障害を除
去する。

【０１１９】次に、図１９のフローチャートを参照し
て、第３の実施の形態に係る図形レイアウト圧縮システ
ムの全体の動作について詳細に説明する。

【０１２０】先ず、レイアウトデータ変換手段１１１
は、第１の実施の形態のステップＳ１００と同様に、レ
イアウトデータから素片データを作成する（ステップＳ
１００）。

【０１２１】次に、制約グラフ作成手段１０３は、第２
の実施の形態と同様に、Ｙ方向及びＸ方向の制約グラフ
データを作成する（ステップＳ２０２）。

【０１２２】次に、端子制約グラフ作成手段１０４は、
第１の実施の形態における図３に示したステップＳ１０
３１からステップＳ１０３６と同様に、Ｙ方向の端子制
約グラフデータと部品制約グラフデータとを作成する
（ステップＳ１０３１〜Ｓ１０３６）。

【０１２３】次に、順位データ作成手段１０５は、第２
の実施の形態におけるステップＳ２０４と同様に、Ｙ方
向の最短経路の部品制約グラフデータ（選択グラフ）と
その端の部品（選択部品）とを選ぶ。（ステップＳ２０
４）。

【０１２４】次に、第２の実施の形態における図１４お
よび図１５に示すステップＳ２０５からステップＳ２１
５の処理と同様の処理により、選択部品をＹ方向に最短
経路長で移動し、Ｘ方向の部品制約グラフデータを計算
し、板端間のその最短経路長を計算し、許容範囲と比較
する。最短経路長がＸ方向の必要縮小距離以上ある場合
はステップＳ２０４に戻り処理を続行し、必要縮小距離
に満たない場合は、以下のステップＳ３１６に進む。

【０１２５】ステップＳ３１６では、最短経路解消手段
は、Ｘ方向の最短経路の節の部品のうちビアホールある
いは少数部品端子部品を抽出し、それがＹ方向の部品制
約グラフの最短経路の節とはならない部品（変位部品）
を選び、以下の様にして、変位部品をそのＸ方向のコン
パクションの最短経路から外す。

【０１２６】すなわち、最短経路解消手段は、変位部品
がそのＸ方向部品制約グラフデータで連結する相手の部
品番号３２との間を接続するＹ方向端子排除グラフ４３
（部品制約グラフデータ６０）を第１の実施の形態と同
様に作成する。

【０１２７】次に、最短経路解消手段は、その変位部品
に接続するＹ方向端子排除グラフ４３を部品制約グラフ
データに追加し、この追加により部品制約グラフデータ
の最短経路探索をやり直し、部品の移動距離の変更にと
もないＸ方向の部品制約グラフデータの最短経路も更新
すべくステップＳ２０４に戻り処理する。

【０１２８】こうしてＸ方向の部品レイアウトが制限範
囲を逸脱しないようにコンパクションを制御する、以上
のステップＳ２０４からステップＳ３１６の処理を繰り
返し、部品制約グラフデータを順次登録する。

【０１２９】次に、部品コンパクション手段１０７は、
各部品をＸ方向にその部品制約グラフデータの最短経路
長で移動し配置する（ステップＳ２１７）。

【０１３０】次に、配線コンパクション手段１０８は、
第１の実施の形態におけるステップＳ１１１と同様に、
配線限界位置データを作成する（ステップＳ１１１）。

【０１３１】最後に、再配線手段１０９は、第１の実施
の形態におけるステップＳ１１２と同様に、配線を斜め
配線を含む形状に整形して再配線する（ステップＳ１１
２）。

【０１３２】次に、本発明の第３の実施の形態に係る図
形レイアウト圧縮システムの効果について説明する。

【０１３３】上述したように、第３の実施の形態では、
部品の移動方向で移動の障害となっているビアホールを
部品の移動方向に垂直方向に移動させ障害を解消する事
で、部品移動の障害を自動的に解消して部品を移動でき
る。その理由は、最短経路解消手段がＹ方向のコンパク
ションでＸ方向の障害となるビアホールを検出し、その
ビアホールをＹ方向に移動する機能を有するためであ
る。

【０１３４】本発明の第４の実施の形態による図形レイ
アウト圧縮システムは、第１の実施の形態と同じく、図
１に示すプログラム制御により動作するコンピュータ１
００と、表示部１０１と、操作部１０２とから構成され
ている。コンピュータ１００は、第１の実施の形態の構
成に加え、部品移動指定手段（図示せず）を有し、これ
は、各部品の移動方向を指定する部品移動目標ベクトル
データ６３（図２１）をレイアウトの任意の位置に向け
て設定する。

【０１３５】次に、図２０のフローチャートを参照し
て、第４の実施の形態に係る図形レイアウト圧縮システ
ムの全体の動作について詳細に説明する。

【０１３６】先ず、レイアウトデータ変換手段１１１
は、第１の実施の形態におけるステップＳ１００と同様
に、レイアウトデータから素片データを作成する（ステ
ップＳ１００）。

【０１３７】次に、部品移動指定手段が、各部品それぞ
れをレイアウトの任意の位置の移動目標位置６３０に向
けた部品移動目標ベクトルデータ６３を以下の様にして
設定する。部品移動指定手段は、操作指令入力手段１１
０が操作者から管面でのマウス操作、あるいはキーボー
ド操作等により指示を受け取り、各部品毎に、その初期
の位置から移動目標位置６３０まで張ったベクトルをそ
の部品移動目標ベクトルデータ６３とする。また、部品
移動指定手段は、複数の部品の部品移動目標ベクトルデ
ータ６３の群を通信回線を通じ読み込み、あるいは磁気
記録媒体から読み込む事が出来る。

【０１３８】本第４の実施形態では、部品制約グラフの
節として移動目標起点とする不動点を記録する。そし
て、部品のＹ方向（下方向）の移動目標距離をグラフの
長さとし、移動目標起点を第１の節とし部品番号３２を
第２の節とするＹ方向の部品制約グラフデータを作成す
る。同様に、部品のＸ方向（左方向）の移動目標距離を
グラフの長さとするＸ方向の部品制約グラフデータを作
成する。この様に移動目標起点と部品とを結ぶ部品制約
グラフデータを作成する事により、部品を移動目標ベク
トルデータ６３に合わせて移動する事ができる。

【０１３９】また、本第４の実施の形態では、全部品の
移動方向を任意のレイアウト位置に向けた部品移動目標
ベクトルデータ６３を一括して設定する事で部品レイア
ウトを収束でき、あるいはその逆方向に向けて一括して
設定する事で部品レイアウトを拡大する様に、部品移動
目標ベクトルデータ６３を一括して設定する事もできる
（ステップＳ３０１）。

【０１４０】次に、第１の実施の形態のステップＳ１０
１からステップＳ１０３６の処理と同様の処理により、
移動目標起点と部品番号３２を結ぶ部品制約グラフデー
タにその他の部品制約グラフデータを加え、ステップＳ
１０４からステップＳ１０５の処理により、その部品制
約グラフデータを用い、部品レイアウトをコンパクショ
ンする。

【０１４１】次に、ステップＳ１１１からステップＳ１
１２において、配線限界位置データを計算し、その限界
位置以内の空間に配線を斜め線を有する自由な形状に再
配線する。

【０１４２】また、この第４の実施の実施の形態は、部
品移動指定手段が部品移動目標ベクトルデータ６３を設
定し、その後に、第２の実施の形態の動作あるいは第３
の実施の形態の動作によりレイアウトをコンパクション
する事もできる。

【０１４３】次に、図２０、図２１から図２３を参照し
て、第４の実施の形態に係る図形レイアウト圧縮システ
ムの具体的な動作について説明する。図２０は第４の実
施の形態の動作を示すフローチャートである。図２１か
ら図２３は第４の実施の形態の処理動作を説明するため
の絵柄を示す平面図である。図２１は本第４の実施の形
態の処理の対象となる印刷配線板の初期のレイアウトと
部品の移動目標グラフを示す。また、図２３は、本実施
例による処理を終了した状態のレイアウトを示す平面図
である。

【０１４４】以下に、図２１に示すレイアウトを本発明
の図形レイアウト圧縮装置がコンパクション処理する動
作を、図２０の処理手順の流れ図に添って説明する。

【０１４５】部品移動指定手段が操作者の指令により、
図２１に示すように個々の部品の部品移動目標ベクトル
データ６３を指定する。また、新たに挿入する配線を指
定する（ステップＳ３０１）。

【０１４６】次に、部品コンパクション手段１０７は、
図２２に示す様に、部品端子毎にＸ方向あるいはＹ方向
に移動制約長が最小の端子の部品から順に部品を移動目
標ベクトルの移動目標位置６３０に向かうＸ方向あるい
はＹ方向の量子化方向に順次移動するコンパクション配
置を行なう。図２２には配線イメージを表示している
が、この段階では配線は未だ具体的配置位置が定まって
いない。

【０１４７】次に、配線コンパクション手段１０８は、
配線に関して、その配線を挟む端子制約グラフデータの
一方の端の部品端子の形に添って配線を寄せて折り曲げ
た八角形形状の配線限界位置データを作成し、それを配
線限界位置データ記憶部８０に記憶する（ステップＳ１
１１）。

【０１４８】最後に、再配線手段１０９は、配線を斜め
配線を含む形状に整形して再配線摺る（ステップＳ１１
２）。その結果を図２３に示す。

【０１４９】次に、第４の実施の形態に係る図形レイア
ウト圧縮システムにおける主な効果について説明する。

【０１５０】上述したように、本発明の第４の実施の形
態では、任意の位置に部品を移動でき、例えば、部品レ
イアウトを広げる事もできるようなコンパクションを行
なう。その理由は、本第４の実施の形態は、部品の移動
方向を移動目標で指定する部品移動指定手段を有し、ま
た、その部品の移動目標に向けて部品を移動する部品コ
ンパクション手段１０７を有するためである。

【０１５１】本発明の第５の実施の形態に係る図形レイ
アウト圧縮システムは、第４の実施の形態の部品移動指
定手段が、部品移動指定手段が設定する部品移動目標ベ
クトルデータ６３を、全部品を各々の部品の位置のレイ
アウト中心からの距離を相似な距離に拡大する位置に設
定する。

【０１５２】そして、第４の実施の形態におけるコンパ
クション処理を行ない、部品配置を拡大した位置にレイ
アウトする。これにより、本第５の実施の形態における
コンパクションは、部品のレイアウトを上下の順および
左右の順を保った位置に拡大し配置する事ができる。

【０１５３】次に、各部品の端子間の未結線部分をメイ
ズルータあるいはチャンネルルータ等の通常の自動配線
手段で配線する。あるいは、拡大した配置において管面
操作で部品を変更しあるいは結線を変更修正する。

【０１５４】次に、第４の実施の形態の部品移動指定手
段が、部品移動指定手段が設定する部品移動目標ベクト
ルデータ６３を、全部品を各々の部品の位置のレイアウ
ト中心からの距離を相似な距離に縮小する位置に設定す
る。

【０１５５】そして、第４の実施の形態におけるコンパ
クション処理を行ない、部品を縮小した位置にレイアウ
トする。

【０１５６】次に、第５の実施の形態に係る図形レイア
ウト圧縮システムにおける主な効果について説明する。

【０１５７】本第５の実施の形態は、部品間の配線ある
いは設計変更するのに十分余裕のある広い空間で行な
い、その後に部品と配線をコンパクションする事によ
り、高密度配線を容易に実現できる効果がある。また、
本第５の実施の形態におけるコンパクションは、部品を
上下の順および左右の順を保った位置に配置するため、
ある方向へのコンパクションがそれと垂直方向へのコン
パクションの障害を生じる事が少ない。

【０１５８】その理由は、本発明の部品コンパクション
手段１０７が部品と配線の間隔を広げる部品移動を行な
うためであり、また、レイアウトを縮小するコンパクシ
ョン処理は、部品同士の上限左右の関係を保つ様に部品
移動目標ベクトルデータ６３を指定するためであるから
である。

【０１５９】本発明の第６の実施の形態に係る図形レイ
アウト圧縮システムは、基本的には第１の実施の形態と
同じ構成である。本第６の実施の形態は、コンピュータ
１００が、配線更新手段（図示せず）を更に含む事を特
徴とする。この手段は概略つぎのように動作する。配線
更新手段は、指定した配線と指定した部品端子及び配線
との順序を入れ替える。

【０１６０】次に、図２４を参照して、第６の実施の形
態に係る図形レイアウト圧縮システムにおける全体の動
作について詳細に説明する。

【０１６１】先ず、レイアウトデータ変換手段１１１
は、第１の実施の形態におけるステップＳ１００と同様
に、レイアウトデータから素片データを作成する（ステ
ップＳ１００）。

【０１６２】次に、第２の実施の形態におけるステップ
Ｓ２０２と同様の処理により、制約グラフ作成手段１０
３は、Ｙ方向制約グラフデータとＸ方向制約グラフデー
タとを作成する。

【０１６３】次に、操作指令入力手段１１０は、配線の
レイアウトを表示し、操作者の指令を受け、ビアホール
Ｄ（指定ビアホール）と、それに隣接する配線を、図２
１（ａ）に示すように指定する（ステップＳ５０４）。

【０１６４】次に、配線更新手段は、図２５（ｂ）に示
す様に、配線（第１の配線）を指定ビアホールに添って
迂回させる。

【０１６５】すなわち、配線更新手段は、第１の配線が
存在する層面において指定ビアホールと、制約グラフデ
ータで接続する素片番号３１とを抽出し、更に、第１の
配線が制約グラフデータで接続する素片番号３１を抽出
する。そして、配線更新手段は、こうして抽出した素片
の間の空間で、必ずしも周囲の素片との必要間隙を満た
さずに、図２５（ｂ）に示す様に第１の配線を、指定ビ
アホールの周りを迂回する配線に変更し、配線の素片デ
ータを更新する。そして、制約グラフ作成手段１０３
は、その経路の配線の素片番号３１とＸ方向あるいはＹ
方向で隣接する周囲の素片番号３１を記録する制約グラ
フデータを更新し作成する（ステップＳ５０５）。

【０１６６】次に、以下の様にして、配線更新手段は、
配線のループを除去する。すなわち、配線更新手段は、
この迂回路の配線を示す素片データで表される一方の位
置番号３３が、制約グラフデータで隣り合う配線素片
（隣接素片）とだけ共有される場合には、その位置番号
３３（共有位置）をそれに接続する素片データの他端の
位置番号３３に変更する。そして、配線更新手段は、片
端の位置番号３３を変更した配線素片番号３１と他の素
片番号３１とを記録した既存の制約グラフデータで、両
素片番号３１におけるＹ方向の干渉の有無を計算する。
両者が干渉しない状態に変化した場合には、配線更新手
段は、その制約グラフデータを削除する（ステップＳ５
０６）。

【０１６７】こうして、図２６（ａ）の様に、ビアホー
ルを迂回する配線が形成される。

【０１６８】また、図２７（ａ）に示すビアホールＡの
様に、第１の配線と相対位置を交換する指定ビアホール
に、第１の配線の存在する層面の配線（第２の配線）が
接続されている場合であって、第２の配線が第１の配線
にＸ方向に並行して走行する範囲においては、第１の配
線も第２の配線もそれぞれ１つながりで分岐が無く、配
線が互いに並行する領域の端の配線端がビアホールに接
続する場合においては、配線更新手段は、以下の様にし
て第１の配線と第２の配線を入れ替える。

【０１６９】すなわち、配線更新手段は、第１の配線の
素片番号３１を記録する制約グラフデータ（第１の制約
グラフ）を抽出し、この制約グラフ番号４１を、指定ビ
アホールＡから第１の配線の終端の部品端子（ビアホー
ルＢ）まで順に並べ第１の配線配列（図示せず）に記憶
する。また、配線更新手段は、第１の配線が連結する終
端の部品端子（ビアホールＢ）の素片番号３１を記憶す
る。

【０１７０】そして、配線更新手段は、第２の配線の素
片番号３１が記録されている制約グラフデータ（第２の
制約グラフ）を抽出し、この制約グラフ番号４１を第２
の配線の先端の指定ビアホール（ビアホールＡ）から終
端のビアホール（部品端子Ｃ）まで順に並ベ第２の配線
配列（図示せず）に記憶する。また、配線更新手段は、
第２の配線の終端を表す位置番号３３で示されるビアホ
ール（部品端子Ｃ）の素片番号３１を記憶する（ステッ
プＳ５０７）。

【０１７１】次に、配線更新手段は、この順の第１の配
線配列と、第２の配線配列とを比較する。このとき、第
２の配線配列の最初の制約グラフ番号４１と最後の制約
グラフ番号がともに第１の配線配列に記録されている場
合は、第２の配線の始端と終端を第１の配線が覆う場合
である。その場合には、配線更新手段は、以下の様にし
て第１の配線と第２の配線の順番を入れ替える。

【０１７２】すなわち、配線更新手段は、第２の配線の
うち、両端のビアホールと直結する第２の配線の素片デ
ータを削除し、配線形状をビアホールから分断する。そ
して、配線更新手段は、第１の配線から両ビアホールと
Ｙ方向で隣接する部分を削除し、配線形状を分断する。
そして、配線更新手段は、両ビアホール間の第１の配線
の部分を、第２の両ビアホールに連結する配線形状を作
成する。また、配線更新手段は、両ビアホールの外の両
側に残った第１の配線の部分を、両ビアホール間に残っ
た第２の配線部分と連結する配線形状を作成する。そし
て、配線更新手段は、それらの配線の素片番号３１とＸ
方向あるいはＹ方向で隣接するその周囲の素片番号３１
との制約グラフデータを更新し作成する。次に、配線更
新手段は、第１の配線に対してステップＳ５０６を行な
い配線のループを除去する（ステップＳ５０８）。

【０１７３】また、第２の配線配列の最初の制約グラフ
番号が第１の配線配列に記録され、第１の配線配列の最
後の制約グラフ番号が第２の配線配列に記録されている
場合は、図２７（ａ）に示す様に、第２の配線と第１の
配線がそれぞれ一部で並行して走行する場合である。こ
の場合には、配線更新手段は、以下の様にして、図２７
（ｂ）に示す様に第２の配線と第１の配線の順番を入れ
替える。

【０１７４】すなわち、配線更新手段は、指定ビアホー
ルと結合する第２配線を指定ビアホールとの結合部分を
除去し、配線形状を分断する。また、配線更新手段は、
第１の配線を右側の終端ビアホールとの結合部分を除去
し、配線形状を分断する。そして、配線更新手段は、第
１および第２の配線から両ビアホールとＹ方向で隣接す
る部分を除去し、配線形状を分断する。そして、配線更
新手段は、両ビアホール間の第１の配線の部分の左端を
指定ビアホールに接続し、右端を終端のビアホールの右
側に分断された第２の配線に接続する。また、配線更新
手段は、両ビアホール間に分断された第２の配線の部分
の左端を指定ビアホールの左側に分断された第１の配線
の部分と連結し、第２の配線の部分の右端を終端ビアホ
ールに接続する。そして、配線更新手段は、それらの配
線の素片番号３１とＸ方向あるいはＹ方向で隣接するそ
の周囲の素片番号３１との制約グラフデータを更新し作
成する。次に、配線更新手段は、第１の配線に対してス
テップＳ５０６を行ない、配線のループを除去する（ス
テップＳ５０９）。

【０１７５】こうして、第１の配線と第２の配線の順番
を入れ替える。

【０１７６】次に、端子制約グラフ作成手段１０４は、
第２の実施の形態における図３に示すステップＳ１０３
１からステップＳ１０３６と同様の処理により、部品制
約グラフデータを作成する。

【０１７７】次に、部品コンパクション手段１０７は、
第２の実施の形態における図１３乃至図１５に示すステ
ップＳ２０４からステップＳ２１６と同様の処理によ
り、その部品制約グラフデータに基づいて、部品レイア
ウトをＹ方向にコンパクションし、ステップＳ２１７に
おいてＸ方向にコンパクションする。

【０１７８】次に、配線コンパクション手段１０８およ
び再配線手段１０９は、第１の実施の形態におけるステ
ップＳ１１１からステップＳ１１２と同様の処理によ
り、配線限界位置データを計算し、配線を斜め線を有す
る自由な形状に再配線する。

【０１７９】こうして、図２６（ａ）に示されるレイア
ウトをＹ方向とＸ方向にコンパクションし、図２６
（ｂ）の様に、配線の間隙がデザインルールを満足する
レイアウトを得る。

【０１８０】尚、以上のステップＳ１０３１からの処理
は、以下の様に行なう事もできる。すなわち、第１の実
施の形態におけるステップＳ１０１からステップＳ１０
３６と同様の処理により、端子制約グラフ作成手段１０
４は、部品制約グラフデータを作成し、ステップＳ１０
４からステップＳ１０５と同様の処理により、部品コン
パクション手段１０７は、その部品制約グラフデータに
基づいて部品レイアウトをコンパクションし、次に、第
１の実施の形態におけるステップＳ１１１からステップ
Ｓ１１２と同様の処理により、配線コンパクション手段
１０８は配線限界位置データを計算し、再は配線手段１
０９は配線を斜め線を有する自由な形状に再配線する。

【０１８１】こうして、図２６（ａ）に示されたレイア
ウトをＹ方向にコンパクションし、更にステップＳ１０
１からの処理を繰り返してＸ方向にコンパクションし、
配線の間隙がデザインルールを満足するレイアウトを得
る事もできる。

【０１８２】次に、本発明の第６の実施の形態に係る図
形レイアウト圧縮システムにおける主な効果について説
明する。

【０１８３】本第６の実施の形態は、配線に部品端子を
迂回する、また、配線同士の相対関係（順）を入れ替え
るレイアウト変更を行ない、それをコンパクションし配
線が整形されデザインルールを守ったレイアウトを形成
できる。

【０１８４】尚、本発明は、上述した実施の形態に限定
されず、本発明の要旨を逸脱しない範囲内で種々の変更
が可能なのはいうまでもない。例えば、上述した実施の
形態におけるコンピュータ１００における各手段を実現
するプログラムは、図１で破線で示すような記録媒体１
１５に記録されていても良い。ここで、「記録媒体」と
は、プログラムを記録したコンピュータ読み取り可能な
記録媒体のことをいい、具体的には、ＣＤ−ＲＯＭ，フ
レキシブルディスクなどの磁気ディスク、半導体メモリ
などを含む。さらに、記録媒体１１５はプログラムを記
録した磁気テープ、紙テープ、用紙でも良い。記録媒体
１１５が用紙の場合には、コンピュータはＯＣＲ（光学
的文字読取装置）のような読取装置と、この読取装置で
読み取った文字（コード）をコンピュータが認識できる
機械言語に翻訳するコンパイラとを備えていれば良い。

【０１８５】

【発明の効果】以上説明したように、本発明では、配
線、端子、ビアホール及び多角形導体形状を有する少な
くとも１層のパターンをコンパクションする場合に、レ
イアウトデータを入力して部品端子及びビアホールを層
毎の素片データに分割し、この配線、多角形導体形状を
曲がり点及び分岐点毎の素片データに分割し、連結する
素片データに共通の部品番号を付し、個々のビアホール
毎に部品番号を指定し、この各層面毎に上下、左右の部
品端子が、間に挟む配線と必要間隔からなる配線帯を介
して接近し得る距離を記憶する端子制約グラフデータと
部品制約グラフデータを作成し、この各部品を部品制約
グラフデータによりコンパクションし、その後に、配線
を整形し再配線しているので、コンパクション方向に垂
直方向へ部品のコンパクションの障害が生じる対策とし
て、その原因となる部品の配置を変更し、配置の圧縮領
域を小さくできるという効果を奏する。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態による図形レイアウ
ト圧縮システムの構成を示すブロック図である。

【図２】図１に示した図形レイアウト圧縮システムの全
体の動作を説明するためのフローチャートである。

【図３】図２中のステップＳ１０３１〜Ｓ１０３６のフ
ローチャートである。

【図４】図１に示した図形レイアウト圧縮システムで使
用される各種のデータ（素片データ、位置データ、形状
データ、配線限界位置データ）を示す図である。

【図５】図１に示した図形レイアウト圧縮システムで使
用される他の各種のデータ（制約グラフデータ、端子制
約グラフデータ、種端子グラフデータ、部品制約グラフ
データ）を示す図である。

【図６】図１に示した図形レイアウト圧縮システムで使
用されるレイアウトの一例を示す図である。

【図７】図１に示した図形レイアウト圧縮システムの全
体の動作を説明するために使用されるレイアウトの初期
配置状態を示す図である。

【図８】図１に示した図形レイアウト圧縮システムの全
体の動作を説明するために使用される、図７に示すレイ
アウトをＹ方向にコンパクションした状態を示す図であ
る。

【図９】図１に示した図形レイアウト圧縮システムの全
体の動作を説明するために使用される、図８に示すレイ
アウトを再配線した状態を示す図である。

【図１０】図１に示した図形レイアウト圧縮システムの
全体の動作を説明するために使用される、図９に示すレ
イアウトに対して部品制約グラフを作成した状態を示す
図である。

【図１１】図１に示した図形レイアウト圧縮システムの
全体の動作を説明するために使用される、図１０に示す
レイアウトをＸ方向にコンパクションし、再配線した状
態を示す図である。

【図１２】本発明の第２の実施の形態による図形レイア
ウト圧縮システムの構成を示すブロック図である。

【図１３】図１２に示した図形レイアウト圧縮システム
の全体の動作を説明するためのフローチャートである。

【図１４】図１３中のステップＳ２０５〜Ｓ２０９のフ
ローチャートである。

【図１５】図１３中のステップＳ２１０〜Ｓ２１５のフ
ローチャートである。

【図１６】図１２に示した図形レイアウト圧縮システム
の動作を説明するための絵柄を示す平面図である。

【図１７】図１２に示した図形レイアウト圧縮システム
の動作を説明するために使用されるレイアウトを示す図
である。

【図１８】図１２に示した図形レイアウト圧縮システム
の具体的な動作例を説明するために使用される図であ
る。

【図１９】本発明の第３の実施の形態による図形レイア
ウト圧縮方法の動作を説明するためのフローチャートで
ある。

【図２０】本発明の第４の実施の形態による図形レイア
ウト圧縮方法の動作を説明するためのフローチャートで
ある。

【図２１】図２０に示した図形レイアウト圧縮方法の処
理動作を説明するための絵柄を示す平面図である。

【図２２】図２０に示した図形レイアウト圧縮方法の全
体の動作を説明するために使用される、図２１に示すレ
イアウトに対してコンパクション配置をした状態を示す
平面図である。

【図２３】図２０に示した図形レイアウト圧縮方法によ
る処理を終了した状態のレイアウトを示す平面図であ
る。

【図２４】本発明の第６の実施の形態による図形レイア
ウト圧縮方法の動作を説明するためのフローチャートで
ある。

【図２５】図２４に示した図形レイアウト圧縮方法の動
作を説明するために使用されるレイアウトを示す図であ
る。

【図２６】図２４に示した図形レイアウト圧縮方法の動
作を説明するために使用されるレイアウトを示す図であ
る。

【図２７】図２４に示した図形レイアウト圧縮方法の動
作を説明するために使用されるレイアウトを示す図であ
る。

【図２８】従来のレイアウト圧縮装置の構成を示すブロ
ック図である。

【図２９】図２８に示したレイアウト圧縮装置の動作を
説明するための配置を示す図である。

【符号の説明】

２０ レイアウトデータ記憶部 ３０ 素片データ記憶部 ４０ 制約グラフデータ記憶部 ５０ 端子制約グラフデータ記憶部 ６０ 部品制約グラフデータ記憶部 ８０ 配線限界位置データ記憶部 １００ コンピュータ １０１ 表示部 １０２ 操作部 １０３ 制約グラフ作成手段 １０４ 端子制約グラフ作成手段 １０５ 順位データ作成手段 １０７ 部品コンパクション手段 １０８ 配線コンパクション手段 １０９ 再配線手段 １１１ レイアウトデータ変換手段 １１２ 制約グラフ更新手段 １１５ 記録媒体

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 17/50 H01L 21/82 H05K 3/00

Claims (21)

(57)【特許請求の範囲】
1. 【請求項１】 二次元空間に配置した配線、端子、ビア
   ホール及び多角形導体形状を有する少なくとも１層のパ
   ターンと、印刷配線板の部品あるいは半導体セルのレイ
   アウトデータを読み込み、該レイアウトをコンパクショ
   ンする図形レイアウト圧縮システムであって、 該レイアウトデータから、部品端子と前記ビアホール、
   前記半導体セル、前記配線、および部品外形同士のいず
   れかを結ぶ制約グラフデータを作成する制約グラフデー
   タ作成手段と、 前記部品端子と前記ビアホール、前記半導体セル（配線
   を除く）、および前記部品外形同士のいずれかを両端の
   節として持つ端子制約グラフデータを作成すると共に、
   前記端子制約グラフデータで連結した各端子とビアホー
   ルが、前記端子制約グラフデータの両端の節の間に挟ま
   れる配線の幅と必要間隙を加えた配線帯を介して、一端
   の節が他端の節にコンパクション方向で接近し得る移動
   の限界距離を計算する端子制約グラフ作成手段と、 該移動の限界距離以内で、他端の節の部品とビアホール
   （配線を除く）を移動することより、部品をコンパクシ
   ョンする部品コンパクション手段と、 前記配線を前記部品と前記ビアホールの間の間隔に斜め
   配線を有する配線形状に整形して再配線する手段とを有
   すること、を特徴とする図形レイアウト圧縮システム。
2. 【請求項２】 前記制約グラフデータ作成手段が、同じ
   信号名の素片同士をお互いに透明として、他の信号名の
   素片から並列に接続される関係の制約グラフデータを作
   成すること、を特徴とする請求項１に記載の図形レイア
   ウト圧縮システム。
3. 【請求項３】 前記部品コンパクション手段は、前記移
   動の限界距離以内で部品を移動する距離を計算する際
   に、部品をコンパクション方向に移動させる場合に、該
   コンパクション方向に垂直方向（Ｘ方向）の部品制約グ
   ラフデータの最短経路長がＸ方向のコンパクションの必
   要移動距離以上ある場合に部品を移動し、一方、必要移
   動距離未満の場合に該最短経路上の部品を該最短経路か
   ら外す部品制約グラフデータを作成追加し、それにより
   部品をコンパクションし、それによって、板端間の最短
   経路を必要移動距離以上に保つようにしたこと、を特徴
   とする請求項１又は請求項２に記載の図形レイアウト圧
   縮システム。
4. 【請求項４】 部品のコンパクション方向への移動の都
   度、コンパクション方向に垂直方向の制約グラフデータ
   を更新する制約グラフ更新手段を更に有すること、を特
   徴とする請求項３に記載の図形レイアウト圧縮システ
   ム。
5. 【請求項５】 ビアホール、部品端子あるいは半導体セ
   ルを表示して、個々の部品とビアホールの移動目標方向
   と距離目標を指定する部品移動指定手段と、 前記部品移動指定手段によって該移動を指定した部品番
   号と移動目標起点番号を記録する部品制約グラフデータ
   を作成する部品制約グラフデータ作成手段とを更に有
   し、 前記部品コンパクション手段は、全部品とビアホールと
   を、前記部品移動指定手段による移動目標の指定に従っ
   て移動すること、を特徴とする請求項１から４のいずれ
   か１つに記載の図形レイアウト圧縮システム。
6. 【請求項６】 前記部品移動指定手段は、操作者の指令
   を受けて、部品あるいは半導体セル及びビアホールの移
   動目標方向を自由に設定する手段を有し、 前記部品コンパクション手段は、その設定を部品の移動
   目標として部品を移動すること、を特徴とする請求項５
   に記載の図形レイアウト圧縮システム。
7. 【請求項７】 前記部品コンパクション手段は、全部品
   のレイアウト中心からの距離を相似な距離に拡大し、次
   に再配線、部品変更等によりレイアウトを修正し、次に
   全部品と配線をレイウアト中心に向けてコンパクション
   すること、を特徴とする請求項５又は請求項６に記載の
   図形レイアウト圧縮システム。
8. 【請求項８】 二次元空間に配置した配線、端子、ビア
   ホール及び多角形導体形状を有する少なくとも１層のパ
   ターンと、印刷配線板の部品あるいは半導体セルのレイ
   アウトデータを読み込み、該レイアウトをコンパクショ
   ンする図形レイアウト圧縮方法であって、 該レイアウトデータから、部品端子と前記ビアホール、
   前記半導体セル、前記配線、および部品外形同士のいず
   れかを結ぶ制約グラフデータを作成し、 前記部品端子と前記ビアホール、前記半導体セル（配線
   を除く）、および前記部品外形同士のいずれかを両端の
   節として持つ端子制約グラフデータを作成し、 前記端子制約グラフデータで連結した各端子とビアホー
   ルが、前記端子制約グラフデータの両端の節の間に挟ま
   れる配線の幅と必要間隙を加えた配線帯を介して端の節
   が他端の節にコンパクション方向で接近し得る移動の限
   界距離を計算し、 該移動の限界距離以内で、他端の節の部品とビアホール
   （配線を除く）を移動して部品をコンパクションし、 前記配線を前記部品と前記ビアホールの間の間隔に斜め
   配線を有する配線形状に整形して再配線するステップを
   含むこと、を特徴とする図形レイアウト圧縮方法。
9. 【請求項９】 前記制約グラフデータを作成するステッ
   プが、同じ信号名の素片同士をお互いに透明として、他
   の信号名の素片から並列に接続される関係の制約グラフ
   データを作成すること、を特徴とする請求項８に記載の
   図形レイアウト圧縮方法。
10. 【請求項１０】 前記部品をコンパクションするステッ
    プは、前記移動の限界距離以内で部品を移動する距離を
    計算する際に、部品をコンパクション方向に移動させる
    場合に、該コンパクション方向に垂直方向（Ｘ方向）の
    部品制約グラフデータの最短経路長がＸ方向のコンパク
    ションの必要移動距離以上ある場合に部品を移動し、一
    方、必要移動距離未満の場合に該最短経路上の部品を該
    最短経路から外す部品制約グラフデータを作成追加し、
    それにより部品をコンパクションし、それによって、板
    端間の最短経路を必要移動距離以上に保つようにしたこ
    と、を特徴とする請求項８又は請求項９に記載の図形レ
    イアウト圧縮方法。
11. 【請求項１１】 部品のコンパクション方向への移動の
    都度、コンパクション方向に垂直方向の制約グラフデー
    タを更新するステップを更に含むこと、を特徴とする請
    求項１0に記載の図形レイアウト圧縮方法。
12. 【請求項１２】 ビアホール、部品端子あるいは半導体
    セルを表示して、個々の部品とビアホールの移動目標方
    向と距離目標を指定し、 該移動を指定した部品番号と移動目標起点番号を記録す
    る部品制約グラフデータを作成するステップを更に含
    み、 前記部品をコンパクションするステップは、全部品とビ
    アホールとを、移動目標の指定に従って移動すること、
    を特徴とする請求項８から１１のいずれか１つに記載の
    図形レイアウト圧縮方法。
13. 【請求項１３】 前記部品の移動を指定するステップ
    は、操作者の指令を受けて、部品あるいは半導体セル及
    びビアホールの移動目標方向を自由に設定し、 前記部品をコンパクションするステップは、その設定を
    部品の移動目標として部品を移動すること、を特徴とす
    る請求項１２に記載の図形レイアウト圧縮方法。
14. 【請求項１４】 前記部品コンパクション手段は、全部
    品のレイアウト中心からの距離を相似な距離に拡大し、
    次に再配線、部品変更等によりレイアウトを修正し、次
    に全部品と配線をレイウアト中心に向けてコンパクショ
    ンすること、を特徴とする請求項１２又は請求項１３に
    記載の図形レイアウト圧縮方法。
15. 【請求項１５】 二次元空間に配置した配線、端子、ビ
    アホール及び多角形導体形状を有する少なくとも１層の
    パターンと、印刷配線板の部品あるいは半導体セルのレ
    イアウトデータを読み込み、該レイアウトをコンパクシ
    ョンする処理を、コンピュータで実行させるためのプロ
    グラムを記録した記録媒体において、 該レイアウトデータから、部品端子と前記ビアホール、
    前記半導体セル、前記配線、および部品外形同士のいず
    れかを結ぶ制約グラフデータを作成する第１の処理と、 前記部品端子と前記ビアホール、前記半導体セル（配線
    を除く）、および前記部品外形同士のいずれかを両端の
    節として持つ端子制約グラフデータを作成する第２の処
    理と、 前記端子制約グラフデータで連結した各端子とビアホー
    ルが、前記端子制約グラフデータの両端の節の間に挟ま
    れる配線の幅と必要間隙を加えた配線帯を介して端の節
    が他端の節にコンパクション方向で接近し得る移動の限
    界距離を計算する第３の処理と、 該移動の限界距離以内で、他端の節の部品とビアホール
    （配線を除く）を移動して部品をコンパクションする第
    ４の処理と、 前記配線を前記部品と前記ビアホールの間の間隔に斜め
    配線を有する配線形状に整形して再配線する第５の処理
    と、 を前記コンピュータに実行させるプログラムを記録し
    た、前記コンピュータが読取可能な記録媒体。
16. 【請求項１６】 前記第１の処理が、同じ信号名の素片
    同士をお互いに透明として、他の信号名の素片から並列
    に接続される関係の制約グラフデータを作成する処理で
    あること、を特徴とする請求項１５に記載の前記コンピ
    ュータが読取可能な記録媒体。
17. 【請求項１７】 前記第４の処理は、前記移動の限界距
    離以内で部品を移動する距離を計算する際に、部品をコ
    ンパクション方向に移動させる場合に、該コンパクショ
    ン方向に垂直方向（Ｘ方向）の部品制約グラフデータの
    最短経路長がＸ方向のコンパクションの必要移動距離以
    上ある場合に部品を移動し、一方、必要移動距離未満の
    場合に該最短経路上の部品を該最短経路から外す部品制
    約グラフデータを作成追加し、それにより部品をコンパ
    クションする処理であり、それによって、板端間の最短
    経路を必要移動距離以上に保つようにしたこと、を特徴
    とする請求項１５又は請求項１６に記載の前記コンピュ
    ータが読取可能な記録媒体。
18. 【請求項１８】 部品のコンパクション方向への移動の
    都度、コンパクション方向に垂直方向の制約グラフデー
    タを更新する第６の処理を更に含むこと、を特徴とする
    請求項１７に記載の前記コンピュータが読取可能な記録
    媒体。
19. 【請求項１９】 ビアホール、部品端子あるいは半導体
    セルを表示して、個々の部品とビアホールの移動目標方
    向と距離目標を指定する第７の処理と、 該移動を指定した部品番号と移動目標起点番号を記録す
    る部品制約グラフデータを作成する第８の処理とを更に
    含み、 前記第４の処理は、全部品とビアホールとを、移動目標
    の指定に従って移動する処理を含むこと、を特徴とする
    請求項１５から１８のいずれか１つに記載の前記コンピ
    ュータが読取可能な記録媒体。
20. 【請求項２０】 前記第７の処理は、操作者の指令を受
    けて、部品あるいは半導体セル及びビアホールの移動目
    標方向を自由に設定する処理を含み、 前記第４の処理は、その設定を部品の移動目標として部
    品を移動する処理を含むこと、を特徴とする請求項１９
    に記載の前記コンピュータが読取可能な記録媒体。
21. 【請求項２１】 前記第４の処理は、全部品のレイアウ
    ト中心からの距離を相似な距離に拡大し、次に再配線、
    部品変更等によりレイアウトを修正し、次に全部品と配
    線をレイウアト中心に向けてコンパクションする処理を
    含むこと、を特徴とする請求項１９又は請求項２０に記
    載の前記コンピュータが読取可能な記録媒体。