JPS6145364A - 自動レイアウト方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の利用分野〕 本発明は電子回路等の自動レイアウトシステムに係り、
特に階層記述された大規模回路の自動レイアウト方式に
関する。

〔発明の背景〕

従来のデジタル系の電子回路自動レイアウトシステム等
においては、あらかじめ形状の確定した配置物を相互の
間の配線距離が短かくなるように配置し、それらの間の
自動配線をおこなっている。

配置物が多くなった場合、それらの配置に関する可能な
代替案の数はきわめて多くなるため、計算機を用いても
良好な計画を得ることがむつがしい。

なお、この種の従来技術については、例えばＪＩＲＩ　
５ＯＵＫＵＰ、”Ｃ１ｒｃｕｉｔ　Ｌａｙｏｕｔ”、Ｐ
ｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ　ＩＩＥ’、Ｖｏｌ
、　６９　ｅ　Ｎａ　１０　ｅ　０ｃｔｏｂｅｒ　１９
８１゜等がある。

〔発明の目的〕

本発明の目的は、大規模かつ配置物同志の間に複雑な制
約の存在するレイアウト問題を解決するためのひとつの
方式を実現する自動レイアラ・ト方式を提供することで
ある。

〔発明の概要〕

本発明レイアウト方式においては、あらかじめ物体の配
置・配線状況を記憶した可変構造のレイアウトパターン
を用意しておき、レイアウト対象回路を、このパターン
の中に埋め込むという操作をおこなうことにより、階層
構造を持った回路等のレイアウト計画を作成する。

パターンを使用するため、そうでない場合に比較して、
レイアウト計画として許容できないような代替案を生成
・評価することを防止でき、効率的に、大規模・複雑な
条件を持つ回路のレイアウトを作成することができる。

〔発明の実施例〕

以下、本発明の一実施例を第１図以下を用いて説明する
。

第１図は、レイアウト対象を概念的に描いたものである
。１００は名称がｄｏで１面積予想値が７５０の配置対
象（ブロック）を表わしている。

このブロックｄＯの中には３個のサブブロックｄｏｌ　
（１１０）、ｄｏ２　（１２０）＝　ｄｏ３（１３０）
が存在している。サブブロック間には結線が存在してお
り、ｄｏｌとｄｏ２の間には５単位の結線がある（１３
２）、ｄｏ２とｄｏ３の間には３単位の結線がある。

ブロックｄｏｌ　（１４０）等は各々階層構造を持って
おり例えば予想面積４５０であり、ブロックｄｏｌｌ　
（１４２）等から成り、ブロック間に結線が存在する。

ブロックｄｏｌｌ　（１５０）は予想面積１５０であり
、ブロックｄｏｌｌｌ、ｄｏｌ１２．ｄ。

１１３から成っている。

ブロックｄｏ１．１１（１６０）は、要素としてブロッ
クｂ１５　（１６２）、ｂ１６　（１６４）等から成っ
ており、ブロックｂ１５　（１７０）は図示のように４
×６の確定サイズを持つ基本回路である０本実施例では
、第１図に示す階層記述された回路をレイアウトする方
式を説明する。説明を簡単化するために１本実施例では
配置機能のみを取りあげ、配線機能については略す。

第２図（ａ）は本発明を実施する際のハードウェア環境
を示す図である。結線データの入力はキーボード１２．
ライトペン１３、タブレット１４などにより行われる。

知識ベース、データベース等はメモリ装置１６．磁気デ
ィスクファイル１５などにより実現される。レイアウト
結果や、中間結果は出力装置であるディスプレイ１７１
作図機１８、プリンタ１９などにより実現される。

第２図（ｂ）は、本発明のソフトウェア機能植成図であ
る。計算機システム２００には、第１図に示した階層系
のデータファイル２１０、階層レイアウトプログラム２
２０．パターンライブラリ２３０、レイアウト結果の出
力データファイルが接続されている。

第３図はレイアウト処理の流れを示すフローチャートで
ある。

先ず、レイアウト対象ブロック名（通常は第１図でｄｏ
に相当する最上位階層ブロック名）と、絶対座標系での
対象ブロックのレイアウト目標形状を与える（３００）
。

次に、当該ブロックの面積予想値及びサブブロック名称
、その他の情報を調べる（３０４．）。

次に、当該ブロックのレイアウト初期案を記憶しく３０
２）、後の処理で良好なレイアウト案を選択するための
初期案とする。

次に、パターンライブラリをひとつ選択する（３０６）
。

次に選択したパターンに対して、サブブロックの割り当
て方をひとつ仮定し、この場合の当該ブロックの推定形
状を計算する（３０８）。

次に選択したパターンの回転角を仮定する（３１０）。

次にパターン回転後の当該ブロックの絶対座標系での推
定形状を計算する（３１２）。

次に当該ブロックの推定形状が、目標形状と合致するま
で試行鎖誤し、結果を記憶する（３１４）。

次に３１６に示すように当該ブロックのサブブロック全
体についてそれぞれをレイアウトする（この部分は再帰
的に実施される。言い換えれば、第３図会体の処理機能
を繰り返し利用してシイアウトを実施する）。

次に、各サブブロックのレイアウト結果の形状より、当
ブロックの形状を計算する（３１８）。

次に３２０に示すように当ブロックの目標形状と上記で
述めた実形状とを比較し、実形状が目標形状を満足する
まで当ブロックのレイアウトを試行鎖誤的に作成する。

プログラムリスト（１）は第１図の系を記述したもので
あり、第２図２１０の内容である。本実施例では人工知
能言語として著名なＰｒｏ、ｌｏｇ言語を用いた説明を
おこなう。

４００は、ブロックｄｏが、サブブロックｄ０１゜ｄｏ
２．ｄｏ３とから成り、ｄｏの面積予想値が７５０であ
ることを示している。

４１０はｄｏｌが、サブブロックｄｏｌｌ。

ｄｏｌ２．ｄｏｌ３から成り、面積予想値が４５０であ
ることを示す。

４２０．４３０はｄｏｌｌ、ｄｏｌｌｌについての同様
のデータである。

４４０は、最下位のブロックｂ１５のデータであり１面
積が２４．実形状が４Ｘ６であることを示している。

４５０．４６０は、同様にｂ１６．ｂ１７についての形
状を示している。

プログラムリスト（１） ／−ｄａｔａ　ｏｆ　　１ａｙｏｕｔ　　傘／ｂ（ｄＯ
，［ｄｏｌ、ｄＯ２，ｄ０３］、７５０．−、ｊ、　　
　　　　　　　　４００ｂ（ｄｏｌ、　［ｄｏｌｌ、ｄ
ｏｌ２．ｄｏ１３］　、４５０．−、Ｊ、　　　　　　
　　４１０ｂ（ｄｏｌｌ、［ｄｏｌｌｌ、ｄｏｌｌ２．
ｄ０１１３］、１５０．、ｊ、　−４２０ｂ（ｄｏｌｌ
ｌ、［ｂ１５．ｂ１６．ｂ１７コ、５９．−、−）、　
　　　　　　　　　　　　　　　　　　　４３０ｂ（ｂ
１５．［コ、２４．［４，６］、ｊ、　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　４４
０ｂ（ｂ１６．［コ、１５．［３，５］、−）、　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　４５０ｂ（ｂ１７．［コ、１５．［：３．５］、
−）、　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　４６０ｂ（ｄｏｌｌ２．［ｂ１８．
ｂｌｆｌｌ］、４２．−、Ｊ。

ｂ（ｂ１８．［コ、２４　、［４，６］　、−）。

ｂ（ｂ１９．［１，１８，［３，６］、ｊ。

ｂ（ｄｏｌｌ３．　［ｂ２０．ｂ２１．ｂ２２］、５４
．、ｊ。

ｂ（ｂ２０．［］、１８．［３，６］、ｊ。

ｂ（ｂ２１．［：］、１８．［３，６］、ｊ。

ｂ（ｂ２２．［１，１８，［３，６］、ｊ。

ｂ　（ｄＯ１２，［ｄＯ１２１、ｄ０１２２］　、　１
６８．、ｊ。

ｂ（ｄｏｌ２１．［：ｄＯ１２１１，ｄｏｌ２１２コ、
９８．−、−）。

ｂ（ｄＯ１２１１，［ｂ４．ｂ５］、５６．、ｊ。

ｂ　（ｂ４．［コ、２４．［３，８］、−）。

ｂ（ｂ５．［１，３２，［４，８コ、−）。

ｂ（ｄＯ２，［ｄＯ２１，ｄＯ２２，ｄ０２３］、１２
０．−、ｊ。

ｂ（ｄＯ２１，［ｂ２３．ｂ２４．ｂ２５コ、４０．、
ｊ。

ｂ（ｂ２３．［コ、１２．［３，４］、ｊ。

ｂ（ｂ２４．［コ、１６．［４，４］、ｊ。

ｂ（ｂ２５．［コ、１２．［３，４］、ｊ。

ｂ（ｄＯ２２，［ｂ２６．ｂ２７．ｂ２８］、３２．、
ｊ。

ｂ（ｂ２６．［］、１２．［３，４コ、−）。

ｂ（ｂ２７．［１，８，［２，４コ、−）。

ｂ（ｂ２８．［１，１２，［３，４コ、−）。

ｂ（ｄＯ２３，［ｄＯ２３１，ｂ３２．ｂ３３］、４８
．、ｊ。

ｂ（ｄＯ２３１，［ｂ２９．ｂ３０．ｂ３１］、２４．
−、ｊ。

ｂ（ｂ２９．［コ、８．［２，４］、ｊ。

ｂ（ｂ３ｏ、［１，８，［ｚ、４１．、−）。

ｂ（ｂ３１．［コ、８．［２，４］、−）。

ｂ（ｂ３２．［１，１２，［３，４］、ｊ。

プログラムリスト（２）は第１図回路のブロック間の結
線データである。５００Ｉ±、ブロックｄｏ２１とｄｏ
２３の間に３本の結線力１存在していることを示し、５
１０はｄＯ２２とｄＯ２３の間に３本の結線が存在して
いることを示してを）る。

プログラムリスト（２） ｃ（ｂ２６．ｂ２７，２）。

ｃ（ｂ２７．ｂ２８，２）。

ｃ（ｄＯ２３１，ｂ３２，２）。

ｃ（ｄＯ２３１，ｂ３３，２）。

ｃ（ｂ３２．ｂ３３，１）。

ｃ（ｂ２９．ｂ３０，１）。

ｃ（ｂ３０．ｂ３１，１）。

ｃ（ｄＯ３１，ｄＯ３２，１）。

ｃ（ｄＯ３１，ｄＯ３３，４）。

ｃ（ｄＯ３２，ｄＯ３３，２）　− ｃ（ｂ４１．ｂ４２，２）。

ｃ（ｂ４２．ｂ４３，１）。

ｃ（ｄｏ３２１．ｂ３３２，１）。

ｃ（ｂ４６．ｂ４７，１）。

ｃ（ｄｏ３３２．ｄｏ３３３，３）。

ｃ（ｂ３４．ｂ３５，２）。

ｃ（ｂ３６．ｂ３７，１）− ｃ（ｂ３７．ｂ３８，２）。

ｃ（ｂ３９．ｂ４０，１）。

プログラムリスト（３）は第２図２２０の階層レイアウ
トプログラムである。６００はＬａｙｏｕｔという名称
のプログラムの頭部である（記号ニーより左側は頭部、
右は本体部とよばれる）。本プログラムの名称は１ａｙ
ｏｕｔであり、第１変数ＢＬＯＣＫはレイアラ、ト対象
ブロック、第２変数ＦＬＯＯにはＢＬＯＣＫで指定する
ブロックをレイアウトする際のパターンの名称を指示し
、第３変数ＲＯＴＡＴＩＯＮはパターンの配置角度、第
４変数［：ＧＸ、ＧＹ］はレイアウトするブロックの配
置形状目標値、第５変数［ＲＸ、ＲＹ］は実形状を表わ
す。

６１０は第３図３０２に対応し、配置物間の配線長や、
配置形状の目標とのギャップがきわめて大きい悪いレイ
アウト案を初期記憶する。

６２０は第３図３０４に対応し、第４図中から変数ＢＬ
ＯＣＫの指示するブロックのサブブロックや面積予想値
を取り出す、６３０は第３図中の３０６〜３２０に対応
するものであり、パターンを用いてレイアウトをおこな
い、目標形状［ＧＸ、ＧＹＩを満たす、実形状［ＲＸ、
ＲＹＥを持つレイアウトを作成する。

６４０は得たレイアウトを出力表示する（第２図２４０
に書き出す）。

６５０は、第３図３００の具体例を示すものであり、ブ
ロックｄＯを目標形状［２５，３０１のもとてレイアウ
トすることを指示している。

プログラムリスト（３） ／傘ｐｒｏｇｒａｍ拳／ １ａｙｏｕｔ（［１ＬＯＣＫ、ＦＬＯＯＲ，ＲＯＴＡＴ
ＩＯＮ、［ＧＸ、ＧＹＩ、［ＲＸ、ＲＹＥ）ニー　　−
６００ａｓｓｅｒｔｌ（ｆｌｏｏｒｐｌａｎ（−、ＢＬ
ＯＣＫ、−＋−ｙ−＋−ｔ−＊−ｔｌｉｎｅｌｅｎｇｔ
ｈ（９９９９）、５ｈａｐｅＨａｐ−ｖａｌｕａ（９９
９９）））、　−６１０ｂ　（ＢＬＯＣＫ　、５ＵＢＢ
ＬＯＣＫ　、ＡＲＥＡ　、ＲＤＺＭ　、−）、　　　　
　　　　６２０ｆｌｏｏｒ（ＦＬＯＯＩ＋、［１ＬＯＣ
Ｋ、ＲＯＴＡＴＩＯＮ、ＳＵ［ｌ［３ＬＯＣＫ。

［ＧＸ、ＧＹＩ、［ＲＸ、ＩＩＹＩ、ＧＤＺＭ、ＲＤＺ
Ｍ　　　　　　　　　　　　６３０ｗｒｉｔｅ　（ｆｌ
ｏｏｒ　（ＦＬＯＯＲ、ＢＬＯＣＫ　、ＲＯＴＡＴＩＯ
Ｎ　、５ＵＢＢＬＯＣＫ　。

［ＧＸ、ＧＹＩ、［ＲＸ、ＲＹＥ、ＧＤＺＭ、ＲＤＺＭ
　　　　　　　　　　　　６４０？　−１ａｙｏｕｔ　
（ｄｏ、ＦＬＯＯＲ、ＲＯＴＡＴＩＯＮ、　［２５，３
０１，［ＲＸ、ＲＹＥ）、　−６５０第３図３０６〜３
２０はライブラリパターンへの回路の割り当て処理であ
る。これを説明する前に、第４図でレイアウトパターン
の説明をおこなう。

７００は、プログラムリスト（１）のステップ４４０の
ｂ１５のように、サブブロックを持たないブロックのレ
イアウトパターンであり、横Ｘ、縦Ｙの長方形状である
。ここでＸ、Ｙは未知数である。

７１０は３個のサブブロックからなるブロックをレイア
ウトするためのパターンであり、Ｂｌ。

Ｂ２．Ｂ３は各々の部々に割り当てたブロックの名称を
記憶する変数、Ｘ１１〜Ｙ３１は形状を表わす変数であ
る。

７２０は２個のサブブロックを持つブロックをレイアウ
トするためのパターン、７３０は３個のサブブロックを
持つブロックをレイアウトするための７１０と別のパタ
ーンである。

レイアウトにあたっては、これらのパターンの中から適
当なものを選択し、レイアウト対象回路をこのパターン
に埋め込み、例えば７１０のパターンでは形状変数Ｘｌ
ｌ、Ｙｌｌなどについて各サブブロックの面積予想値等
を考慮して目標値を定め、この目標値のもとに各々のサ
ブブロックをレイアウトする（再帰処理）。

第５図は絶対空間に対するパターンの回転角を示すもの
であり、８００は第４図７１０のパターンを角度Ｏでレ
イアウトしたもの、８５０は角度９０”でレイアウトし
たものである。角度自身もレイアウト計画の対象となる
。

プログラムリスト（４）〜（７）は、第２図２３０の内
容例であり第４図７００〜７３０のパターンに対してレ
イアウトを作成するものである。

プログラムリスト（４）のステップ９００はプログラム
の頭部であり、パターン名称ｆｌｏｏｒ　Ｏ、レイアウ
ト対象ブロックを示す変数ＢＬＯＣＫ　、パターン回転
角を示す変数ＲＯＴＡＴＩＯＮ、サブブロックは空（［
］で示している）、絶対座標系での目標形状［ＧＸ、Ｇ
ＹＩ、同レイアウト実形状［ＲＸ。

ＲＹＥ、パターン実形状［ＲＸｌｌ、ＲＹＩＩ］等を持
っている。

９１０で、先ず回転角を求め、９２０ではパターン実形
状ＲＸＩＩ、ＲＹＩＩを回転角に応じて修正して絶対座
標系でのレイアウト実形状ＲＸ。

ＲＹを求める。

９３０では目標形状ＧＸ、ＧＹと実形状ＲＸ。

ＲＹをくらべて、ソノ差を５）ＩＡＰＥＧＡＰＶＡＬＵ
Ｅに入れる。

９４０では、当該ブロックに関して、過去に作成して記
憶しているレイアウト計画の目標形状と実形状のギャッ
プＳＧ■を調べる。

９５０で現在作成中の計画のものと比較し、改善されて
おれば過去の記憶を消去しく９６０）。

今回の試行結果を新たに記憶する。

９８０では、目標形状ＧＸ、ＧＹと実形状ＲＸ。

ＲＹを比較して結果が良か否かを判定し、良の場合はプ
ログラム９００の処理を終え、否の場合逆戻りして試行
をくりかえす。

９１０〜９８０の処理は、第３図３０６〜３２０の部分
と対応しているが１本パターンは構造が簡単なため第３
図中の一部の処理は不要となるため、プログラムリスト
（４）中に存在しないものもある。

プログラムリスト（４） ／中ｆｌｏｒｐＬａｎ　−−−ｆｌｏｏｒＯ＊／ｆ１ｏ
ｏｒ（ｆｌｏｏｒｏ、ＢＬＯＣＫ、ＲＯＴＡＴＩＯＮ、
［コ、［ＧＸ、ＧＹ］。

［ＲＸ、ＲＹＩ、［ＧＸｌｌ、ＧＹＩＩＩ、［ＲＸｌｌ
、ＲＹｌｌｌ）　ニー　−９００ｒｏｔａｔｉｏｎ　（
ＲＯＴＡＴＩＯＮ）　、　　　　　　　　　　　９１０
ｃｈａｎｇｅ（ＲＸＩＩ、ＲＹＩＩ、ＲＯＴＡＴＩＯＮ
、ＲＸ、ＲＹ　−９２０ｓｈａｐｅ−ｇａｐ−ｖａｌｕ
ｅ （ＧＸ、ＧＹ、ＲＸ、ＲＹ、５）ＩＡＰＥＧＡＰＶＡＬ
ＵＥ）、　−９３０ｆｌｏｏｒｐｌａｎ（−２ＢＬＯＣ
Ｋ＋−＋−ｐ−＋−ｔ−＋−ｙ−＋ｓｈａｐｅｇａｐ−
ｖａｌｕｅ（ＳＧＶ）　　　　　　　　　　９４０Ｓｔ
（ＡＰＥＧＡＰＶＡＬＵ　　＜　　ＳＧＶ、　　　　　
　　　　　　　　　　　　　　９５０ｒｅｔｒａｃｔｌ
　（ｆｌｏｏｒｐｌａｎ（−、ＢＬＯＣに、−、−、−
、−、−、−、−、−））、　−９６０ａｓｓｅｒｔｌ
（ｆｌｏｏｒｐｌａｎ（ｆｌｏｏｒＯ，［１ＬＯＣＫ、
ｌｌ０ＴＡＴＩＯＮ。

［］、［ＧＸ、ＧＹＩ、［ＲＸ、ＲＹＩ、［ＧＸｌｌ、
ＧＹＩＩＩ。

［ＲＸｌｌ、ＲＹｌｌｌ、−、ｓｈａｐｅｇａｐ−ｖａ
ｌｕｅ（ＳＩＩＡＰＥＧＡＰＶＡＬＵ）　））　、　　
　　　　　　　　　　　９７０ｓｈａｐｅ　　ｏｋ（Ｇ
Ｘ、ＧＹ、ＲＸ、ＲＹ）、　　　　　　　　　　　　９
８０プログラムリスト（５）は第４図７１０のパターン
に対応している。

１０００はプログラムの頭部であり、プログラムリスト
（３）の６３０とのマツチングによって、プログラムが
第３図３０６で選択される６１０１０、１０２０は第３
図３０８に対応する。

１０３０は目標形状変数が全て正かどうかをたしかめて
いる。

１０４０は、　１０１０でのパターンへのサブブロック
割り当てに伴うブロック間総配線長の概算値の計算。

１０５０は第３図３１０に対応する回転角の仮定。

１０５２は第３図３１２　、１０５４．　ＬＯ５６ｔ、
　３１４に対応する。

１０５８〜１０６２はサブブロックＢｌ、Ｂ２．Ｂ３の
レイアウト処理であり第３図３１６に対応する再帰処理
であり、プログラムリスト（４）のプログラムをよび出
している。

１０６４は、第３図３１８．１０６６は３２０に対応す
る。

プログラムリスト（５） ／申　ｆｌｏｒｐｌａｎ　　−−−ｆｌｏｏｒｌ　　傘
／ｆｌｏｏｒ（ｆｌｏｏｒｌ　、ＢＬＯＣＫ　、ＲＯＴ
ＡＴＩＯＮ　、［Ｂ１　、Ｂ２．Ｂ１１　、［ＧＸ　、
ＧＹ］　。

［ＲＸ、ＲＹコ、［ＧＸｌｌ、ＧＹｌｌ、ＧＸ２１．Ｇ
Ｙ２１．ＧＸ３１．ＧＹ３１］。

ＧＸＩＩ　＞　Ｏ，ＧＹＩＩ　＞　Ｏ，ＧＸ２１　＞　
Ｏ，ＧＹ２１　＞　０゜ＧＸ３１　＞　０．　ＧＹ３１
　＞　Ｑ、　　　　　　　　　　　１０３０ｍａｘ（Ｇ
Ｙ２１−１０３Ｏ，ＧＹＹ）＊ＧＧＹＹ　ｉｓ　ＧＹ１
１＋ＧＹＹ。

ｒｏｔａｔｉｏｎ（ＲＯＴＡＴＩＯＮ）　、　　　　　
　　　　　　　１０５０ｃｈａ１０５０ｃｈａｎ、ＧＧ
ＹＹ、ｌｌ０ＴＡＴＩＯＮ、ＧＧＸＩＩ、ＧＧＧＹＹ）
、　−１０５２ｓｈａｐｅ−ｇａｐ−ｖａｌｕｅ （ＧＸ、ＧＹ、ＧＧＸＩＩ、ＧＧＧＹＹ、５ＩＩＡＰＥ
ＧＡＰＶＡＬＵＥ）、　−１０５４プログラムリスト（
６） ／傘　ｆｌｏｒｐｌａｎ　　−−−ｆｌｏｏｒ２　　拳
／ｆｌｏｏｒ（ｆｌｏｏｒ２．ＢＬＯＣＫ、ＲＯＴＡＴ
ＩＯＮ、［Ｂ１．Ｂ１１．［ＧＸ、ＧＹＩ、［ＲＸ、Ｒ
Ｙコ。

［ＧＸｌｌ、ＧＹｌｌ、ＧＸ２１．ＧＹ２１］、［ＲＸ
ｌｌ、ＲＹＩＩ、ＲＸ２１゜ｃｈａｎｇｅ（ＧＸＩＩ、
ＧＧＹＹ、ＲＩＴＡＴＩＯＮ、ＧＧＸＩＩ、ＧＧＧＹＹ
）、　−１１５２ｓｈａｐｅ、、ｇａｐ−ｖａｌｕａ （ＧＸ、ＧＹ、ＧＧＸＩＩ、ＧＧＧＹＹ、５ＨＡＰＨＧ
ＡＰＶＡＬＵＥ）、　−１１５４ｓｈａｐｅ−ｏｋ（Ｇ
Ｘ、ＧＹ、ＲＸ、ＲＹ）、　　　　　　　　　　　　　
１１６６プログラムリスト（６）は第４図７２０のパタ
ーンに対応するもので１１００〜１１６６はリスト（５
）の説明内容と似ているので説明は略す。

プログラムリスト（７）は第４図７３０に対応しており
、１２００〜１２６６も第４図と類似するので説明は略
す。

プログラムリスト（８）は、プログラムリスト（７）ま
でのプログラムで利用された関数の実体であり、　１３
００は回転角としてＯ”　、９０”が可能であること、
１３１０は、ベクトル（Ｘ、Ｙ）が回転角により変更さ
れる法則の記述、　１３２０は最大値計算、　１３３０
は目標形状と実形状の間のギャップ値の計算、１３４０
は目標形状と実形状の近さの判定。

１３５０、１３６０はブロック間の配線本数のリスト（
２）のデータからよみ出し、１３７０．１３８０はレイ
アウト結果の記憶と削除、１３９ｏは１３４ｏ内で使用
するＭＡＸの値が５００であることを示している。

プログラムリスト（７） ／拳　ｆｌｏｒｐｌａｎ　　−−−ｆｌｏｏｒ３　　串
／ｆ１ｏｏｒ（ｆ１ｏｏｒ３．［１ＬＯＣＫ、ＲＯＴＡ
ＴＩＯＮ、（：Ｉ］１．Ｂ２．Ｂ３コ、［ＧＸ、ＧＹＩ
。

［ＲＸ、ＲＹ］、　［ＧＸｌｌ、ＧＹｌｌ、ＧＸ１２．
ＧＹＩ２．ＧＸ１３．ＧＹ１３］。

［ＲＸｌｌ、ＲＹｌｌ、ＲＸ１２．ＲＹ１２．ＲＸ１３
．ｌ１ｌＹ１３］）ニー　−１２００ｃｈａｎｇｅ（Ｇ
Ｘｌｌ、ＧＹＩＩ、ＲＯＴＡＴＩＯＮ、ＧＧＸＩＩ、Ｇ
ＧＧＹＹ）＋　−１２５２ｓｈａｐｅ−ｇａｐ−ｖａｌ
ｕｅ （ＧＸ、ＧＹ、ＧＧＸＩＩ、ＧＧＧＹＹ、５ＨＡＰＥＧ
ＡＰＶＡＬＵＥ）、　−１２５４プログラムリスト・（
８） ａｓｓｅｒｔｌ　（Ｘ）　：　−ａｓｓｅｒｔ　（Ｘ）
　ｔ　１．　　　　　　　　　　　　　　　１３７０ｒ
ｅｔｒａｃｔｌ（Ｘ）；−ｒｅｔｒａｃｔ（Ｘ）、！、
　　　　　　　　　　１３８０ｍａｘ−５ｈａｐｅ−５
ａｐ−ｖａｌｕｅ　（５００）、　　　　　　　　　　
　　　　　　１３９０第１図の回路をプログラムリスト
（１）、（２）のように表現してリスト（３）のプログ
ラムを、６５０の命令を与えて実行されると、リスト（
４）〜（８）のパターンライブラリがくり返し利用され
、結果として第２図２４０内に、レイアウト計画を得る
ことができる。

第６図は得られるレイアウト計画を図示したものである
。全体がｄｏに相当し、ｄｏｌは１５００の部分、ｄｏ
２が１５１０部、ｄｏｌ２が１５２０．　ｂ　１が１５
３０等に配置されている。

なお、１５４０はｂ４１とｂ４２の間の配線が２本ある
ことを示している。

以上演算処理を大型計算機等で行なう場合の一実施例を
示したが、本発明の処理をブロック分割して夫々複数の
マイクロプロセッサによる場合、専用計算機を使用する
場合等の変形も可能である。

〔発明の効果〕

以上説明した通り本発明によれば、大規模で、配置物同
志の間に複雑な制約条件の存在するレイアウト問題を効
率的に解くことができる。

【図面の簡単な説明】

第１図は本発明の対象とする電子回路の階層構造説明の
ための概、念図、第２図（ａ）は本発明の一実施例のハ
ードウェア環境を示すブロック図、第２図（ｂ）は、本
発明方式のソフトウェア機能構成図、第３図は１本発明
方式の処理流れ図、第４図。 第５図は本発明におけるレイアウトパターンの概念図、
第６図は本発明により得られるし・ｒアウト葛　ｌ　図 第　２Ｉ￥１ （α）

Claims (1)

【特許請求の範囲】
1. 配置物と配置物同志の間の結線とからなる系を自動レイ
   アウトする方式において、該配置物の配置場所と配置物
   間の結線経路を保持した配置形状パターンを記憶し、該
   パターンを使用してその上の配置場所や結線経路に、配
   置対象とする系を割り当てることを特徴とする自動レイ
   アウト方式。