JPH0414244A - 回路レイアウト方法およびシステム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はＬＳＩ等の回路の配置・配線を行なうレイアラ
１〜方法およびシステムに関する。

〔従来の技術〕

ＬＳＩの配置・配線を行なうレイアウト方法は枚挙にい
とまが無い程多様で、例えば、■　―、　Ｋ、　Ｌｕｋ
、　ｅｔ　ａｌ、　”ＨｉｅｒａｒｃｈｉｃａｌＧｌｏ
ｂａｌ　Ｗｉｒｉｎｇ　ｆｏｒ　Ｃｕｓｔｏｍ　Ｃｈｉ
ｐ　Ｄｅｓｉｇｎ”、　Ｐｒｏｃ。

２３ｒｄ　ＤＡＣ，、ｐｐ、４８１−４８９（１９８６
）。

■　Ｒ，０ｔｔｅｎ、　”Ａｕｔｏｍａｔｉｃ　ｆｌｏ
ｏｒｐｌａｎ　ｄｅｓｉｇｎ”。

Ｐｒｏｃ、　１９ｔｈ　ＤＡＣ，ｐｐ、２６１−２６７
（１９８２）。

が知られている。上記公知例の内■は、配置に関し、■
は配線に関するものである。公知例■は、配置のために
本構造を用いることを提案している。

二こでは、ＬＳＩ全体の配置は、平面分割の繰り返し構
造（Ｓｌｉｃｉｎｇ　５ｔｒｕｃｔｕｒｅ　Ｔｒｅｅ）
として表現される。ブロック間配線は配線チャネルを用
いることとしてあり、かつ逐次処理方法である。配線方
法の詳細は与えられていない。公知例■は配線にパター
ンを用いる方法を示している。

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

公知例■では、ブロック間の配線引き回し計画結果を、
互いのブロック内での、引続く配線計画処理に引き継ぐ
メカニズムが無い。このため、階層記述された回路木の
各親ノード（親ブロックと呼ぶ）において、子ノード（
子ブロックと呼ぶ）間を配線パターンで結ぶという配線
計画を、木の全ノードについて実施する際に、子ブロッ
ク間での配線接続端子位置の正確な同一化が困難となる
。

結果として、配線接続端子位置が同一化できなくなり、
端子間を接続するための配線エリアである、配線チャネ
ルが必要となるか、別途特別の方法を用意して端子位置
整合化をおこなう必要が生じる。

次に、配置・配線を実行するプログラムを開発する立場
から見ると、プログラムの規模が草大になるため、プロ
グラム開発にきわめて多くの労力がかかるという問題が
ある。さらに、ＬＳＩを例に取った場合、対象とするデ
バイスがバイポーラ（Ｂｉｐｏｌａｒ）系であるか、Ｍ
ＯＳ系であるかによって基本素子形状やレイアウトルー
ルが異るために別個のプログラムを開発しなくてはなら
ないといった問題もあった。

さらに、従来のレイアウトシステムでは、プログラムの
開発性の問題がある。一般にレイアウトプログラムは、
特定のレイアウトモデル（配置・配線の基本規則）を定
めて、これに専用のものとすることが多い。それにもか
かわらず、プログラム規模はきわめて大きく、１０４ス
テツプ以上となることが多い。特定のレイアウトモデル
を定めることから、ＬＳＩ製造プロセスやバイポーラ、
ＣＭＯ５といったデバイスの多様性に対応することがむ
つかしく、それら各々に応じたレイアウトモデルに、ひ
いてはレイアウトプログラムを開発することも多い。

逐次処理によるＬＳＩの配置配線アルゴリズムは数多く
提案されてきた。並列処理方法については、例えば、複
数個の端点間を配線する際に必要となる、平面上の配線
可能格子点の探索を、専用の並列ハードウェアで実施す
る方法が提案されているが、単に格子点の探索を並列に
実施して高速化を図っているに留まっており、配置・配
線双方を互いに協調しながら並列処理することによって
、ブロックの形状や相互間の動線引出し位置を整合化す
る方法は、未だ提案されていない。

本発明の目的は、ＬＳＩの配置配線の並列協調処理を行
なうレイアウト方法を提供することにある。具体的には
、並列処理によって処理速度が向上することは当然のこ
とであるが、それ以外に、問題全体を階層的に分割とし
て処理する場合に、分割後の各部分問題の間の相互干渉
の調整を実施する協調機能によって、逐次処理した場合
には解決不可能な異ブロック間の配線不要な屈曲防止（
従って屈曲部分の配線チャネルの発生防止）などが可能
となる。すなわち、大規模回路への対応のだめに、階層
的に問題を解いているにもかかわらず、非階層的に（平
盤的に）異ブロックの配置状況を同時に考慮しつつ配線
したのと同様の結果を得ることが可能となる。

本発明の他の目的は、少い規模のプログラムで複雑なレ
イアウト問題を解けるレイアウト方法を提供することに
ある。

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

上記目的を達成するために、本発明の概要は下言己の通
りである。

（１）システム構成 回路ネットデータ（回路を構成する素子と素子間の配線
データ、以下原データとよぶ）、状態メモリ、入出力プ
ロセス、問題解決推論プロセス、レイアウト基本プロセ
スからなる。

（２）動作概要 原データは、入出力プロセスによって階層化されて、状
態メモリに格納される。この時、配置配線の制約条件を
考慮した回路の階層化をおこなう。

原データがもともと階層化されている場合には、レイア
ウトに都合の良いものに変更する。問題解決推論プロセ
スは、階層回路を配置・配線する。

各々は再帰形式のプログラムとして実現されている。レ
イアウト基本プロセスでは、回路階層水の親ブロックの
配置配線問題を子ブロックの部分問題に分割したり、逆
に完成した子ブロックのレイアウトを統合して親ブロッ
クのレイアウトを作成する。問題解決推論プロセスでは
、適当なものを自動的に選んで問題分割や統合に使用す
る。生成された部分問題に対応するプロセスは、互いに
並列に実行される。得られるレイアウト結果は状態メモ
リに随時記入され、必要に応じて種々のプロセスから参
照されたり、更新されたりする。親ブロックを複数の子
ブロックに分割した結果、各子ブロックの外形状や配線
端子位置が目標値として得られるので、これらのデータ
を状態メモリ中に保持しておき、子プロセス間で互いに
参照し合いながらレイアウト作成処理をすすめる。すな
わち、情報共有による協調処理をおこなう。

〔作用〕

本発明では、親ブロックが分割されて複数の子ブロック
のレイアウトを分担処理するプロセス群は互いに並列に
走行する。各子ブロックがレイアウトを完了したのち親
ブロックが確定する。以上のように並列処理が実現され
る。

この場合、並列走行する子ブロック同士は、状態メモリ
中の外形状や配線引き出し端子位置を情報的に共有し合
って各自の問題解決をすすめる。

すなわち、協調処理をおこなう。これにより、形状や端
子位置不整合による不要チャネルの発生が防止でき、チ
ップ面積が小さくなる。

また、問題解決推論プロセスは、配置・配線いずれも再
帰形アルゴリズムとして構成されているため、同一プロ
グラムが、入力回路水の全ブロックに共通に使用できる
ことになり、レイアウトプログラムの規模は著るしく縮
少できる。これによって、プログラム開発労力が著るし
く縮少可能となる。

レイアウト基本プロセスは親ブロックの分割様相に応じ
た形状テンプレートや各種の基本部品（トランジスタや
抵抗など）の形状生成機能を有するモジュール化された
プログラムライブラリである。この内容を取り替えるこ
とによって、各種のデバイスや製造プロセスに対応した
レイアウトプログラムを実現でき、バイポーラやＣＭＯ
５といった回路実現用デバイスに応じて個別のプログラ
ムを開発する必要が無くなり、全体としての汎用性を高
めることが可能となっている。

〔実施例〕

以下、並列論理言語ＧＨＣに類似のプログラム仕様記述
を併用しつつ、本発明を実現する実施例を示す。アルゴ
リズム記述のために並列論理型言語様式を用いるが、こ
の種の言語にも多様なものがあるので、事前に記述規則
は概説する。

なお、上述した並列論理言語ＧＨＣについては、例えば
、Ｌｌｅｄａ、　Ｋ、、　Ｇｕａｒｄｅｄ　Ｈｏｒｎ　
Ｃ１ａｕｓｅｓ。

Ｌｏｇｉｃ　Ｐｒｏｇｒａｍｍｊ、ｎｇ、　ＬＮＣ５２
２１，ｐｐ、１６８−１７９゜（Ｓｐｒｉｎｇｅｒ　−
Ｖｅｒｌａｇ、　１９８６）に詳細に示されている。

１、本発明のシステム機能構成 並列論理言語による電子回路レイアウト問題解決システ
ム（本発明の実現例）のシステム機能構成を第１図に示
す。レイアウト基本プロセス（１５００）を用いて階層
問題解決を行う問題解決推論プロセス（１４００）が、
双方向ストリーム（１６００）を介して状態メモリ（１
２００）に接続されている。

原データ（１１００）は入出力プロセス（１３００）に
よって回路水（１２１０）に変換された後、問題解決推
論プロセス（１４００）によってレイアウトされ、状態
メモリ内に結果がレイアウト本等の形式のデータ（１２
２０）として格納される。この結果を入出力プロセス（
１３００）でデイスプレィ上に出力描画する構成として
いる。

２、本発明の階層再帰並列協調レイアウトモデル（以下
、ＨＲＣＴ　Ｌ　：　ＨｉｅｒａｒｃｈｊｃａｌＲｅｃ
ｕｒｓｉｖｅ　Ｃｏｎｃｕｒｒｅｎｔ　Ｔｈｅｏｒｅｍ
　ｐｒｏｖｅｒ　ｆｏｒＬａｙｏｕｔと呼ぶ） ２．１　モデルの概要 ＨＲＣＴＬは、第１図システムの基本計算モデルである
本図等を用いてモデルの概要を述べる。

後に述べるＧＨＣ形式によるモデル記述の中で使用する
諸定義も、ここで併せて示しておく。

１）原データ（１１００）：第２図に示すように、本モ
デルへの入力である回路ネットデータＣ１ｒＮｅｔ　（
１１１０）すなわち素子群ｏｂｊｅｃｔ（−）（１１１
１）と素子間の接続関係データ群ｎｏｄｅ（・・・）（
１１１２）、及びそれらの配置・配線上の制約条件のり
ストＣｏｎ５ｔｒ　（１１２０）とから成る。Ｃｏｎ５
ｔｒの内容は１１２１に例示したような配置・配線上の
制約記述項である。

２）状態メモリ（１２００）：第３図に示すように、レ
イアウト対象回路データＣ１ｒＮｅｔ　を階層化した回
路木Ｃ１ｒＴｒｅｅ　（１２１０）　、これを平面上に
レイアウトした結果である配置・配線図の階層木ＬＴｒ
ｅｅ　（１２２１）　、配線用コネクタＣｏｎＬａｙｏ
ｕｔ　（１２２３）　、コネクタ間の配線ＬｉｎｅＬａ
ｙｏｕｔ　（１２２４）などが記憶される。状態モメリ
の内容は、以下の諸プロセスによって書き替えられ、最
終レイアウトとなる。各データの内容詳細は後述する。

３）入出力プロセス（１３００）：第４図に示すように
、入力機能の一部に、原データ内のＣ１ｒＮｅｔ　（１
１１０）をＣｏｎ５ｔｒ　（１１２０）や他の情報を用
いてＣ１ｒＴｒｅｅ　（１２１０）に変換する等の機能
ｐｒｅｐａｒｅ−ｐｌａｃｅｍｅｎｔ　（１３１０）が
ある。

出力機能の一部に、ＬＴｒｅｅ　（１２２１）、Ｃｏｎ
Ｌａｙｏｕｔ　（１２２３）　、　ＬｉｎｅＬａｙｏｕ
ｔ　（１２２４）を出力描画する機能ｄｒａｗ−１ａｙ
ｏｕｔ　（１３２０）がある。

４）問題解決推論プロセス（１４００）：第５図に示す
ように、Ｃ１ｒＴｒｅｅ　（１２１０）をＬＴｒｅｅ（
１２２１）に変換することによってレイアウトを生成す
る機能ｐｌａｃｅ−ａｎｄ−ｒｏｕｔｅである。オブジ
ェクトの配置処理ｐｌａｃｅ　ｂｙ、−ｑｔｒｅｅ　（
１４１０）のあと、配線前処理ｐｒｅｐａｒｅ　ｒｏｕ
ｔｉｎｇ　（図示略）を実行して、各オブジェクト（１
２３２のｇｏ３など）の配置位置（左上点の座標値。局
所座標系で配置するため、（０，０）となっている）を
チップ（１２３０）の世界座標系に変換する。続いて配
線処理ｒｏｕｔｅ−ｂｙ−ｑｔｒｅｅ　（１４３０）を
行う。

配置処理では、配線の概略を計画し、配線を無視した配
置とならぬようにする。Ｃ１ｒＴｒｅｅ（１２１０）に
配置データが追加されてＬＴｒｅｅ（１２２１）が作ら
れる。配線処理ではＬＴｒｅｅ（１２２１）の各階層ノ
ードにおいて、子回路間の配線ネットの引き回し計画を
立てる。当階層ノードの配置計画に使用したｌａｙｏｕ
ｔｆｒａｍｅ（１５２０）に付随して定義しである配線
パターネクタ名称等を配線リストＬｉｎｅＬａｙｏｕｔ
（１２２４）に記入する。

配置・配線いずれの処理も、Ｃ１ｒＴｒｅｅ及びＬ　Ｔ
　ｒ　ｅ　ｅの非終端部を下降方向にたどる問題分割フ
ェイズ（１４１２，１４３２）、木の終端部でのセル処
理フェイズ（１４１４，１４３４）、木を上昇方向にた
どる統合フェイズ（１４１６゜１４３６）を備えた階層
問題解決を行う。雨水とも木の非終端ノードはブロック
（１４４０）、終端ノードはセル（１４５０）と呼んで
いる。

５）レイアウト基本プロセス（１５００）：第６図に示
すように、問題解決推論プロセスｐｌａｃｅａｎｄ　ｒ
ｏｕｔｅが使用する各種のプログラム群から成る。配線
幅、間隔等の制限事項であるプロセス制約を製造プロセ
ス名ごとに記述したレイアウトルール１ａｙｏｕｔｒｕ
ｌｅ群（１５３０）、ブロックやセルレベルでの配置形
状や配線形状のパラメタラ二７−− ”°−イズされたテンプレート群であるレイアウトフレ
ーム１ａｙｏｕ　ｔｆｒａｍｅ群（１５２０）、及びこ
れらのテンプレートを用いてＬＴｒｅｅの各ノードにお
ける問題分割や統合処理を行うプランフレームｐｌａｎ
ｆｔａｍｅ群（１５１０）とから成る。

２．２　モデル記述規約 階層並列レイアウトモデルＨＲＣＴＬの記述を与える。

モデルの機能的性質、並列処理を含めた計算量、メモリ
量等の計算論的性質、デバイスやプロセス変化への適合
性という適応的性質等を同時に表象可能とするために、
並列論理言語ＧＨＣ様式を用いて、モデル記述を行う。

（定義１）述語ｆ　（ｓ（Ｓｏｌｄ）、　ｓ（ＳＮｅｗ
）、　Ｅｎｖ、　Ｃｏｍｐ）によって、処理ｆが、パラ
メタＥｎｖのもとで状態５Ｏ１ｄを５Ｎｅｔｙに変換す
ること、及びその計算複雑度がＣｏｍｐであることを表
わす。

（定義２）変数に↑、↓↑を後付けすることにより各出
力、入出力変数であることを表わす。

入力変数は無印とする。

（定義３）ｐ　ニーＧｌ、Ｇ２．　・−、Ｇｒ　ｌ　Ｇ
ｒ十１．Ｇｒ＋２．・・・、Ｇｎ、によって、ヘッド述
語Ｐ、ボディ述語Ｇ１〜Ｇｎの節を表わす。Ｇ１〜Ｇｒ
は逐次処理されるガード、Ｇｒ＋１〜Ｏｎは並列処理さ
れるゴールである。１はコミットバーである。Ｐ＝（空
）の場合にはゴール節を表わす。

２．３　モデルＨＲＣＴＬの記述 （Ｇｏａｌ）　ＨＲＣＴ　Ｌの解く最上位ゴール節（第
８図参照） ：　−ｇｅｊｉｎｉｔｉａｌ−ｄａｔａ（Ｃ１ｒＮｅｔ
↑、　ＴｏｐＣｉｒｃｕｉｔ↑。

Ｐｌａｙｏｕｔ↑、ＣｏｎＬａｙｏｕｔ↑、　Ｐｒｏｃ
↑、Ｃｏｎ５ｔｒ↑）ｓｏｌｖｅ、−ａ−１ａｙｏｕｔ
ｐｒｏｂｌｅｍ　（ＴｏｐＣｉｒｃｕｉｔ　、　Ｃ１ｒ
Ｎｅｔ　。

ＰＬａｙｏｕｔ、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、Ｃｏｍｐｌ
ｅｘｉｔｙ↑）。

ｇｅｔ−ｉｎｉｔｉａｌ−ｄａｔａ　（第７図２０００
）は、レイアウト対象回路ネットＣ１ｒＮｅｔ、これを
階層水化した時の最上位ノードの名称ＴｏｐＣｉｒｃｕ
ｉｔ、及びその計画レイアウトＰＬａｙｏｕｔ、外端子
の計画位置ＣｏｎＬａｙｏｕｔ　（第７図２０１０）、
使用プロセス名Ｐｒｏｃ、レイアウト制御条件リストＣ
ｏｎ５ｔｒを読み出す。ｓｏｌｖｅ−ａ−１ａｙｏｕｔ
ｐｒｏｂｌｅｍ　（第７図２０１０）は、これらの情報
を用いてＣ１ｒＮｅｔのレイアウトを計算複雑度Ｃｏｍ
ｐｌｅｘｉｔｙのオーダで作成する。

各変数の詳細定義例を示す。

Ｃ１ｒＮｅｔ　　＝　　［［０ｂｊｅｃｔｌＯｂｊＴａ
ｉｌコ。

［ＮｏｄｅｌＮｏｄｅＴａｉｌココ。

０ｂｊｅｃｔ　＝　ｏｂｊｅｃｔ（ＯｂｊＮｅｍｅ、０
ｂｊＴｙｐｅ。

Ｒｅ１ａｔｅｄＮｏｄｅｓ、０ｔｈｅｒｐｒｏｐｓ）。

第２図の名ではｏｂｊｅｃｔ（ｇｏｌ、ｔｒ（ｎｐｎ）
、　［ｉｎ、ｎ３ｗｖｅｅ］、ｊ、　（第２図中１１１
１）Ｎｏｄｅ　＝　ｎｏｄｅ（ＮｏｄｅＮａｒｎｅ＋Ｎ
ｏｃＪｅＴｙｐｅ。

Ｒｅ１ａｔｅｄＯｂｊｅｃｔｓ、０ｔｈｅｒｐｒｏｐｓ
）。

第２図の例ではｎｏｄｅ（ｉｎ、ｓｉｇｎａｌ。

［ｃｉｎ、ｇＯ１コ、−）、　（第３図中１２１２）Ｔ
ｏｐＣｉｒｃｕｉｔ　＝　ｃｉｒｃｕｉｔ（Ｎａｍｅ、
Ｌｅｖｅｌ、５ｔａｔｕｓ）。

Ｎａｍｅは名称、Ｌｅｖｅｌは階層レベル、５ｔａｔｕ
ｓは形状可変状況。

第３図のｇｏではｃｉｒｃｕｉｔ（ｇＯ，ｂｌｏｃｋ、
ｆｒｅｅ）　。

（第３図中１２１１） ＰＬａｙｏｕｔ　＝　［ＰｌａｎｎｅｄＳｈａｐｅ、Ｎ
ｏｒｔｈＣｏｎｓ。

ＷｅｓｔＣｏｎｓ、５ｏｕｔｈＣｏｎｓ、ＥａｓｔＣｏ
ｎｓコ。

ＰｌａｎｎｅｄＳｈａｐｅ　＝　［Ｗｐ、Ｈｐｌ、ｗｈ
ｅｒｅ　１ｌｌｐ　＝ＰｌａｎｎｅｄＷｉｄｔｈ、Ｈｐ
　＝　ＰｌａｎｎｅｄＨｅｉｇｈｔ、長方形状のみ許す
。

ＷｅｓｔＣｏｎｓ　＝ｃｏｎ（Ｎａｍｅ、ＮｏｄｅＮａ
ｍｅ）ＩＴａｉｌコ２図の例ではｃｏｎ（ｃｉｎ、ｉｎ
）、　（第３図中１２３３）。

ＣｏｎＬａｙｏｕｔ　＝　　［ｃｏｎ（Ｎａｍｅ、Ｅｘ
ｉｓｔＲａｎｇｅ、Ｔｙｐｅ。

ＣｏｎｎｅｃｔｅｄＬａｙｅｒｓ、Ｃｏｎｎｅｃｔｅｄ
Ｌｉｎｅｒｓ。

ｏｔｈｅｒｐｒｏｐｓ）ｌ　Ｔａ１ｌコ。

Ｐｒｏｃ　＝　”ｐｒｏｃｅｓｌｏｏ”等のチップ製造
プロセス名称。

Ｃｏｎ５ｔｒ　　＝　　［Ｃｏｎ５ｔｒａｉｎｔＩＣｏ
ｎｓｔｒＴａｉｌ］。

Ｃｏｎ５ｔｒａｉｎｔ　＝　ｃｏｎｓｔｒ（Ｔｙｐｅ、
Ｌｅｖｅｌ、ａｍｏｎｇ（ＯｂｊｅｃｔｓＬｉｓｔｌ　
、０ｂｊｅｃｔｓＬｉｓｔ２）　＋Ｎａｍｅｏｆｔｈｉ
ｓＣｏｎｓｔｒａｉｎｔ）　＋第２図の例ではｃｏｎｓ
ｔｒ（ｐａｉｒ、ａ、ａｍｏｎｇ（［ｇＯ１コ＋　［ｇ
０４］＋ｐａｉｒ−ｔｒｓｏｏｌ）、（第２中１１２１
）６ Ｃｏｍｐｌｅｘｉｔｙ　＝［ＴｉｍｅＣｏｍｐｌｅｘｉ
ｔｙ。

ＳｐｃｅＣｏｍｐｌｅｘｉｔｙ］。

（Ｐｒｏｇ、１）ＨＲＣＴ　Ｌの最上位の推論側である
５ｏｌｖｅ−ａ　］−ａｙｏｕｔｐｒｏｂｌ−ａｒｒＩ
定義節（第８図参照）ｓｏｌｖｅ−ａ　Ｉａｙｏｕｔｐ
ｒｏｂｌｅｍ（Ｔｏｐｃｉｒｃｕｉｔ、Ｃ１ｒＮｅｔ。

ＰＬａｙｏｕｔ、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［ａｄｄ
　（Ｔｃｌ、ａｄｄ　（Ｔｃ２゜Ｔｃ３））、ｍａｘ（
Ｓｃ２，５ｃ３））］↑：　ｔｒｕｅｐｒｅｐａｒｅ　
ｐｌａｃｅｍｅｎｔ（ＴｏｐＣｉｕｃｕｉｔ、Ｃ１ｒＮ
ｅｔ。

ＰＬａｙｏｕｔ、Ｃｏｎ５ｔｒ、Ｃ１ｒＴｒｅｅ↑、Ｌ
Ｔｒｅｅ↑ｒ　［Ｔ　ｅ　ｌ　ｒＳｃｌ］↑、ｅｎｄ、
Ｅｌ↑）。

ｐｌａｃｅ−ａｎｄ−ｒｏｕｔｅ（ｓ（ＣｉｒＴｒｅｅ
、ＬＴｒｅｅ、ＣｏｎＬａｙｏｕｔ。

［］）。

５（ＣｉｒＴｒｅｅｌ、ＬＴｒｅｅ、ＣｏｎＬａｙｏｕ
ｔ。

ＬｉｎｅＬａｙｏｕｔｌ）↑、Ｐｒｏｃ、Ｃｏｎ５ｔｒ
、　［Ｔｃ２．Ｓｃ２］↑。

Ｅｌ、Ｅ２］↑、Ｅｌ、Ｅ２↑）。

ｄｒａｗ　１ａｙｏｕｔ（ｓ（ＣｉｒＴｒｅｅｌ、ＬＴ
ｒｅｅｌ、ＣｏｎＬａｙｏｕｔｌ。

ＬｉｎｅＬａｙｏｕｔｌ）、−、Ｐｒｏｃ、−、［Ｔｃ
３．Ｓｃ３コ、ｅｎｄ、−）。

ｐｒｅｐａｒｅ−ｐｌａｃｅｍｅｎｔ　　（第８図２０
２０）は、回路木Ｃ１ｒＴｒｅｅとレイアウト木ＬＴｒ
ｅｅを、入力されるＣ１ｒＮｅｔ等より作成する。ＬＴ
ｒｅｅはＣ１ｒＴｒｅｅと同型の木であり、Ｃ１ｒＴｒ
ｅｅの各ノード（ブロックやセル）のレイアウト形状デ
ータ５ｈａｐｅを保持させる。

原則として第６図に示した平面の４分割スライス５ｏｎ
ｓＣｉｒＴｒｅｅｓ）　、−は回路特性記入用である。

ＬＴｒｅｅ　＝　　１ａｙｏｕｔ（ＴｏｐＣｉｒｃｕｉ
ｔ、−，５ｈａｐｅ。

ＰｅｒｉＣｏｎｎｓ、ＰｅｒｉＣｏｎｓ、５ｏｎｓＬＴ
ｒｅｅｓ）　、−はｌａｙｏｕｔｆｒａｍｅ名記入用。

ＭｙＮｏｄｅｓ　＝　ＴｏｐＣｉｒｃｕｉｔの周辺ノー
ド名。第３図ではＴｏｐＣｉｒｃｕｉｔはｇｏ（第３図
１２１１）であり ＭｙＮｏｄｅ　　＝　　［ｉｎ、ｏｕｔ、ｖｃｃ、ｖｅ
ｅ］。

５ｏｎｓＣｉｒＴｒｅｅｓ　＝子の回路本のリスト。第
３図ではｇｏ１〜ｇ０４の回路木リスト（第３図１２１
２など）。

５ｈａｐｅ　＝　［Ｗｐ、Ｈｐ、−、−，０，］Ｔａ１
ｌコ、　ＴｏｐＣｉｒｃｕｊ　ｔである回路モジュール
ｇｏの目標形状１’Ｐ　＋　ＨＰ−後での実形状記入用
変数−９−、レイアウト長方形状の左上原点（第３象限
系を利用。この段階では長方形毎の局所座標系に変更す
る （ｐｒｅｐａｒｅ　ｒｏｕｔｉｎｇによる））。Ｔａ１
ｌは長方形状を子回路のレイアウトに分割した際の、分
割点の座標を記入する部分。

ＰｅｒｉＣｏｎｎｓ　　＝　　［ＮｏｒｔｈＣｏｎｓ、
ＷｅｓｔＣｏｎｓ、ＥａｓｔＣｏｎｓコ。

周辺端子群。

第３図の例では（第３図１２３３） ＩｊｅｓｔＣｏｎｓ　　＝　　　　　［ｃｏｎ（ｃｉｎ
、ｉｎ）コ等。

ｅｎｄ、Ｅｌ　＝終了フラグである。ｐｒｅｐａｒｅｐ
ｌａｃｅｍｅｎｔ終了時にＥｌ　＝　ｅｎｄとなる。

５ｏｎｓＬＴｒｅｅｓ　＝子のレイアウト木のリスト。

この段階では未定義（−）となっている。

Ｐｌａｃｅ　ａｎｄ　ｒｏｕｔ（第８図２０３０）は、
状態５（ＣｉｒＴｒｅｅ　、　ＬＴｒｅｅ　、　Ｃｏｎ
Ｌａｙｏｕｔ　ｒ　［］　）を５（ＣｉｒＴｒｅｅｌ。

ＬＴｒｅｅｌ、ＣｏｎＬａｙｏｕｔ、ＬｉｎｅＬａｙｏ
ｕｔｌ）に変換する処理ｉにより、回路木Ｃ１ｒＴｒｅ
ｅのレイアウトを生成する。

態メモリの内容を陽に表現したものである。

５（ＣｉｒＴｒｅｅ、ＬＴｒｅｅ、ＣｏｎＬａｙｏｕｔ
、　［コ）＝レイアウト開始時点の状態であり、ｐｒｅ
ｐａｒｅ−ｐｌａｃｅｍｅｎｔによって作成されたＣ１
ｒＴｒｅｅ、最上位のみに計画レイアウトを持ったＬＴ
ｒｅｅ、コネクタのレイアウトＣｏｎＬａｙｏｕｔ　（
外周分のみ）、配線データ無しく［］）の組みで定義さ
れている。

５（ＣｉｒＴｒｅｅ、ＬＴｒｅｅ、ＣｏｎＬａｙｏｕｔ
、ＬｉｎｅＬａｙｏｕｔｌ）　＝レイアウト完了時点で
の状態であり、 Ｃ１ｒＴｒｅｅにレイアウト起因の寄生効果等を追加し
たＣ１ｒＴｒｅｅｌ　、最上位のみが計画レイアウトを
持っていたＬＴｒｅｅに対して全階層のノートに回路モ
ジュールの実配置データ（長方形の分割データとなって
いる）を記入したＬＴｒｅｅ、配線用全コネクタ群の配
置を表わす ＣｏｎＬａｙｏｕｔｌ　、全配線データＬｉｎｅＬａｙ
ｏｕｔｌの組みで定義される。

ｃｌｒａｗ−１ａｙｏｕｔ　（第８図２０４０）はレイ
アウト完了時点での状態の内のＬＴｒｅｅ、　ＣｏｎＬ
ａｙｏｕｔ。

Ｌｊ　ｎｅＬａｙｏｕｔを外部描画装置に出力表示する
。

ボディ部の３ゴールは逐次実行されるべきものであり、
終了フラグｅｎｄ、Ｅｌ、Ｅ２によってこれを突合して
いる。よって各ゴールの計算及びエリア複雑度を各々［
Ｔｃｉ、Ｓｃｉ］、ＣＩ＋２．３とするとき、５ｏｌｖ
ｅａ　ｌａｙｏｕｔｐｒｏｂｌｅｍ全体の複雑度は上記
定式に記入したごとく次のようになる。

［ａｄｄ（Ｔｅｌ、ａｄｄ（Ｔｃ２．Ｔｃ３））、ｍａ
ｘ（Ｓｃｌ。

ａａｘ（Ｓｃ２，５ｃ３））］。

ここに項ａｄｄ（Ａ、Ｂ）、ｍａｘ（Ａ、Ｂ）は各１項
Ａ、Ｂに加算。

ｍａｘ算を適用した結果を示す計算量である。

（Ｐｒｏｇ、２）配置配線用述語ｐｌａｃｅ−ａｎｄ　
ｒｏｕｔｅの定義ｎ（第９図参照） ｐｌａｃｅ−ａｎｄ−ｒｏｕｔｅ（ｓ（ＣＴＩ、ＬＴＩ
、ＣＬＩ、ＬＬＩ）　、５（ＣＴ４゜ＬＴ４．Ｃｌ３．
ＬＬ４）↑、Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［ａｄｄ（Ｔｅｌ、Ｔｃ２）、ｌｌ１ａｘ（Ｓｃｌ、５
ｃ２）コ↑、ｅｎｄ、Ｏｕｔ↑）：ｔｒｕｅ ｐｒｏｃｅｓｓｏｒ−ｍａｔｒｉｘ　（Ｍａｔｒｉｘ↑
）。

Ｐｌａｃｅ−ｂｙ−ｑｔｒｅｅ（ｓ（ＣＴＩ、ＬＴＩ、
ＣＬＩ、ＬＬＩ）、５（ＣＴ２゜ＬＴ２．Ｃｌ３．ＬＬ
２）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［丁ｃｌ、Ｓｃｌ］、Ｍａｔ
ｒｉｘ、ｅｎｄ、Ｅｌ　↑）。

ｐｒｅｐａｒｅ−ｒｏｕｔｉｎｇ（ｓ（ＣＴ２．ＬＴ２
．Ｃｌ３．ＬＬ２）、５（ＣＴ３゜ＬＴ３．Ｃｌ３．Ｃ
ｌ３．ＬＬ３）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒｙ　［−＋−コ、Ｅｌ、Ｅ２　
　↑　）。

ｒｏｕｔｅＪｙ−ｑｔｒｅｅ　（ｓ　（ＣＴ３　、　Ｌ
Ｔ３　、　Ｃｌ３　、　ＬＬ３）　、　ｓ　（ＣＴ４　
。

ＬＴ４．Ｃｌ３．ＬＬ４）↑。

Ｐｒｐｃ、Ｃｏｎ５ｔｒ、　［Ｔｃ２．Ｓｃ２］、Ｍａ
ｔｒｉｘ、Ｅ２．Ｏｕｔ↑）。

Ｐｒｏｃｅｓｓｏｒ−ｍｉｔｒｉｘ　（第９図２０５０
）は、負荷分散の目的で用いるＰＥ格子を変数ｍａｔｒ
ｉｘに読み出す。

ｐｌａｃｅ−ａｎｄ−ｒｏｕｔｅは＋ｐｌａｃｅ−ｂｙ
−ｑｔｒｅｅ　（第９図２０８０）を実行する。４分木
処理を主体とするアルゴリズムであるため述語名にｂｙ
−（ｌｔｒｅｅをつけた。ボディ部３ゴールによって、
　ｐｌａｃｅ　ａｎｄｒｏｕｔｅの初期状態５（ＣＴＩ
、ＬＴＩ、ＣＬＩ、ＬＬＩ）は、レイアウトが完了した
最終状態５（ＣＴ４．ＬＴ４．Ｃｌ３．ＬＬ４）に変換
される（表現簡略化のためにＣ１ｒＴｒｅｅ１等と略記
した）。３ゴールの実行は逐次であり、　ｐｒｅｐａｒ
ｅｒｏｕｔｉｎｇの計算量は他に比較して微小であり、
メモリ量はＰｌａｃｅＪｙ−ｑｔｒｅｅと同量であるの
で［−、−］として無視している。よって全体の複雑度
は［ａｄｄ（Ｔｅｌ、Ｔｃ２）、ｗａｘ（Ｓｃｌ、５ｃ
２）］となる。

（Ｐｒｏｇ、３）配置述語ｐｌａｃｅＪｙ−ｑｔｒｅｅ
の定義節（第１０図参照） ｐｌａｃｅＪｙ−ｑｔｒｅｅ（Ｓｏｌｄ、ＳＮｅｗ↑、
Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［ａｄｄ（Ｔｅｌ、ａｄｄ（Ｔｅｌ、ａｄｄ（Ｔｃ２．
ａｄｄ（Ｔｃ３．Ｔｃ４）））。

ｒｎａｘ（Ｓｃｌ、ｍａｘ（Ｓｃ２．ｍａｘ（Ｓｃ３，
５ｃ４）））］↑、Ｍａｔｒｉｘ。

ｅｎｄ、Ｏｕｔ↑）ニー ５ｏｌｄ　”　Ｓ（ＣＴＩ−１−１−）１ｇｅｔｊｏｐ
ｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ　（ＣＴ　＋　［ｂ
ｌｏｃｋ　、　ｆｒｅｅ］↑） ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ↑、ｃｈｏｏｓ＋、
ａ　ｌａｙｏｕｔｆｒａｍｅ。

５Ｏ１ｄ、Ｓｌ↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｃｌ　、Ｓｃｌコ↑、ｅ
ｎｄ、Ｅｌ　↑）。

Ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ｇｅｎｅｒａｔｅ
−ｓｕｂｐｒｏｂｌｅｍｓ、Ｓｌ、　。

Ｓ２↑、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［Ｔｃ２．Ｓｃ２
］↑、Ｅｌ、Ｅ２↑）。

Ｐｌａｃｅ−ａｌｌ−ｓｏｎｓ（ＬＦＮａｍｅ、Ｓ２．
Ｓ３↑、　ｐｒＯｃ　。

Ｃｏｎ５ｔｒ、［Ｔｃ３．Ｓｃ３コ　↑　、Ｍａｔｒｉ
ｘ、Ｅ２．Ｅ３　↑　）。

Ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ａｇｇｒｅｇａｔ
ｅ−Ｐｌａｃｅｍｅｎｔ、Ｓ３゜５Ｎｅ１１↑、Ｐｒｏ
ｃ、Ｃｏｎ５ｔｒ、［Ｔｃ４．Ｓｃ４］↑、Ｅ３．Ｏｕ
ｔ↑）。

ｐｌａｃｅＪｙ−ｑｔｒｅｅ（ＳＯｌｄ、ＳＮｅ！１↑
、Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［ａｄｄ（Ｔｅｌ　、Ｔｃ２）、ｍａｘ（Ｓｃｌ、５ｃ
２）コ↑、Ｍａｔｒｉｘ。

ｅｎｄ、Ｏｕｔ↑）ニー ５ｏｌｄ　”　５（ＣＴ、−＋−＋−）＋５ＮｅＷ　”
　Ｓ（−＋ＬＴ＋−＋−）＋ｇｅｔＪｏｐＣｉｒｃｕｉ
ｔ　　ｐｒｏｐｅｒｔｙ（ＣＴ、［ｃｅｌｌ。

ｆｒｅｅコ　↑　）、ｐｕｔｊｆｎａｍｅ（ＬＴ　↓　
↑　、ＬＦＮａｍｅ　↑　）ｐｌａｆｒａｍｅ　（ＬＦ
Ｎａｍｅ↑、　ｃｈｏｏｓｅ−ａ−１ａｙｏｕｔｆｒａ
ｍｅ　。

５ｏｌｄ、−、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［Ｔｃｌ、
Ｓｃｌ］↑、ｅｎｄ、Ｅｌ↑）。

ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ｇｅｎｅｒａｔｅ
−ａ−ｃｅｌｌ、Ｓｌ　、５Ｎｅｖ↑、　Ｐｒｏｃ↓、
Ｃｏｎ５ｔｒ、　［ＴＸ２．ＳＣ２］↑、Ｅｌ、Ｏｕｔ
↑）。

Ｐｌａｃｅ−ｂｙ−ｑｔｒｅｅ（Ｓｏｌｄ、ＳＮｗｅｗ
↑、Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［Ｔｅｌ、Ｓｃｌ］↑、Ｍａｔｒｉｘ、ｅｎｄ、Ｏｕｔ
↑）ニー５ｏｌｄ　＝　５（ＣＴ、−＋−＋−）＋ｇｅ
ｔ−ｔｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ（ＣＴ、
　［−、ｆｉｘ］↑）ｐｌａｆｒａｍｅ（ｆｉｘｅｄｍ
ｏｄｕｌｅ、ｔａｋｅ−ａ−１ａｙｏｕｔ、５ｏｌｄ。

ＳＮｅｗ　↑　、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｃｌ、
Ｓｃｌコ↑　ｔｅｎｄ、ｏｕｔ↑）。

ｐｌａｃｅ、、−ａｌｌ−ｓｏｎｓ（ＬＦＮａｍｅ、５
（ＣＴＩ、ＬＴＩ、ＣＬＩ　、ＬＬＩ）。

５（ＣＴＩ、ＬＴＩ、ＣＬＩ、ＬＬＩ）↑、Ｐｒｏｃ、
Ｃｏｎ５ｔｒ。

［ｍａｘ（Ｔｅｌ、ｍａｘ（Ｔｃ２．ｍａｘ（Ｔｃ３．
Ｔｃ４）））　、ａｄｄ（Ｓｃｌ。

ａｄｄ（Ｓｃ２．ａｄｄ（Ｓｃ３，５ｃ４）））コ↑　
、Ｍａｔｒｉｘ、ｅｎｄ、Ｏｕｔ↑）ニー ｇｅｔ−ｓｏｎｓ−ｔｒｅｅｓ　（ＣＴ　１　、　［Ｓ
Ｃｔ　１　、　ＳＣｔ　２　、５Ｃｔ３　。

５ｅｔ４］↑）。

ｇｅｔ−ｓｏｎｓ−ｔｒｅｅｓ（ＬＴＩ、［５Ｌｔｌ、
５Ｌｔ２，５Ｌｔ３゜５Ｌｔ４コ　↑　）。

ｇｅｔ−ｓｏｎｓ−ｔｒｅｅｓ（ＬＴ２．［５Ｌｔｎｌ
、５Ｌｔｎ２，５Ｌｔｎ３゜５Ｌｔｎ４］↓↑） ａｓｓｉｇｎ−ｍａｔｒｉｘ（ＬＦＮａｍｅ、Ｍａｔｒ
ｉｘ、　［ＬｕＭ、ＬｖＭ、ＲｂＭ。

ＲｕＭコ　↑　、［ＬｕｐＥ、ＬｂＰＥ、ＲｂＰＥ、Ｒ
ｕＰＥコ　↑　）。

ｐｌａｃｅ−ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣｔｌ、５Ｌｔ
ｌ、ＣＬＩ、ＬＬＩ）。

５（ＳＣｔｌ、５Ｌｔｎｌ、Ｃｌ３．ＬＬＩ）↑。

ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｅｌ、Ｓｃｌ］↑、Ｌｎ
Ｍ、ｅｎｄ、Ｅｌ↑）＠ｐｒｏｃｅｓｓｏｒ　（ＬｕＰ
Ｅ）　＋ｐｌａｃｅ−ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣｔ２
，５Ｌｔ２．Ｃｌ３．ＬＬＩ）　。

５（ＳＣｔ２，５Ｌｔｎ２．Ｃｌ３．ＬＬＩ）↑。

ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［Ｔｃ２．Ｓｃ２］↑、Ｌ
ｂＭ、ｅｎｄ、Ｅ２↑）＠ｐｒｏｃｅｓｓｏｒ　（Ｌｂ
ＰＥ）　。

ｐｌａｃｅ−ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣｔ３，５Ｌｔ
３．Ｃｌ３．ＬＬＩ）。

５（ＳＣｔ３，５Ｌｔｎ３．Ｃｌ３．ＬＬＩ）↑。

ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［Ｔｃ３．Ｓｃ３］↑、Ｒ
ｂＭ、ｅｎｄ、Ｅ３↑）＠ｐｒｏｃｅｓｓｏｒ　（Ｒｂ
ＰＥ）　。

ｐｌａｃｅ　ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣｔ４，５Ｌｔ
４．Ｃｌ３．ＬＬＩ）。

５（ＳＣｔ４，５Ｌｔｎ４．Ｃｌ３．ＬＬＩ）↑。

ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［Ｔｃ４．Ｓｃ４］↑、Ｒ
ｂＭ、ｅｎｄ、Ｅ４↑）＠ｐｒｏｃｅｓｓｏｒ　（Ｒｂ
ＰＥ）　。

ｊｕｄｇｅ−ｅｎｄ　（［Ｅｌ　、Ｅ２．Ｅ３．Ｅ４］
　、Ｏｕｔ↑）。

第１．２．３節は各々階層非終端部ｂｌｏｃｋで配置形
状が可変ｆｒｅｅの時（第１０図２０９０）、階層終端
部ｃｅｌｌで形状可変の時（第１ｏ図２１３０）、階層
レベルを間合ずスタンダードセルのような既存の形状固
定物ｆｉｘの利用が可能な時（第１０図２１６０）の処
理を表わしている。ｐｌａｎｆｒａｍｅは、配置形状テ
ンプレートｌａｙｏｕｔｆｒａｍｅの依存の階層本のノ
ード処理述語であり、第６図のレイアウト基本プロセス
（１５００）の一部（１５１０）を成している。メツセ
ージによって異なる働きをする。第１節は、テンプレー
ト群の中から適切な形って子供の計画レイアウトを作成
する（第１０図’７Ｈ１ｏ５）、次のｐｌａｃｅ−ａ、
１ｌ−ｓｏｎｓの節（第１０図２１２０、。）−、、各
１供。配置２再帰ゎ１ｏ実施ｔお。

゛各子供は並列に実行される。最後にａｇｇｒｅｇａｔ
ｅ″ｐｌａｃｅｍｅｎｔのＷＪ（第１０図２１２０）で
子の実形状から親の実形状を求める。実形状が当初予定
のＬＦＮａｍｅのテンプレート定義に合致せぬ場合には
ＬＦＮａｍｅを合致するものに変更する。第２節では、
使用すべきテンプレートを決定したのち（第１０図２１
４０）当テンプレートによってレイアウトを生成して記
憶する（第１０図２１５０）。第３節では生成済のレイ
アウトデータを取り込むのみである（第１０図２１７０
）。

配置処理再帰述語ｐｌａｃｅ−ａｌｌ−ｓｏｎｓは、親
ノードの各子供（４個）に対してｐｌａｃｅＪｙ−ｑｔ
ｒｅｅを再帰的に実施する（第１１図）。各々の子供は
終結フラグｅｎｄを同時に与えられ、−斉に動作する（
第１１図、２２００，２２１０，２２２０゜２２３０）
。各子供のＴｒｅｅについてはレイアウトデータ（ＳＬ
ｔｉ；ｉ＝１〜４）とコネクタデータ（ＣＬｉ　　；　
ｉ＝　１〜４）とが変化する。回路や配線−は資化しな
い。計算オーダは子供の内の最大値、メモリーオーダは
子供の合計となる。ＰＥ格子を示すＭａｔｒｉｘは、ｐ
ｌａｃｅ−ａｌｌ−ｓｏｎｓ内でａｓｓｉｇｎ−ｍａｔ
ｒｉｘ述廃によって、使用中のテンプレート名ＬＦＮａ
ｍｅに依存した分割処理をうける（第１１図２１９０）
。結果として、各子供に下降させるへき部分マトリクス
［ＬｕＭ、ＬｂＭ、ＲｂＭ、ＲｕＭコと、各部分マトリ
クスからの代表ＰＥのリスト［ＬｕＰＥ、ＬｂＰＥ。

ＲｂＰＥ、ＰｕＰＥ］が作成される。各子供は、それぞ
れ”’：ＬｕＰＥ、ＬｂＰＥ等に割り当てられる。再帰
の途中で−Ｍａｔｒｉｘが単一ＰＥに縮退して、それ以
上の分割が１、−不可能となった時点以降では、分割は
中止され、−各子供には同−Ｍａｔｒｉｘが下降される
。すなわち、負荷分散は自動的に中止される。

（Ｐｒｏｇ、４）配線前処理述語ｐｒｅｐａｒｅ−ｒｏ
ｕｔｉｎｇの定義節（第１２図参照） ｐｒｅｐａｒｅ　ｒｏｕｔｉｎｇ（ｓ（ＣＴＩ、ＬＴＩ
、ＣＬＩ、ＬＬＩ）。

５（ＣＴＩ、ＬＴ３．Ｃｌ３．ｊ↑ｒ　Ｐ　ｒ　ＯＣｐ
　ＣＯｎ　Ｓ　ｉ　ｒ　＋　［０＋　ｍ　ａ　Ｘ（Ｓｃ
ｌ、５ｃ２）ｅｎｄ、Ｏｕｔ↑）ニーｇｅＪｏｒｉｇｉ
ｎ　（ＬＴＩ　↓　ｒ　［Ｘｏｒｇ、Ｙｏｒｇコ　↑　
）ｌｏｃａｌ　ｔｏ−ｇｌｏｂａｌ（ＣＴＩ、ＬＴＩ、
ＬＴ２↑、　Ｘｏｒｇ　、　Ｙｏｒｇ　。

［−、Ｓｃｌ］↑、ｅｎｄ、Ｅｌ↑）。

ｃｈｏｏｓｅ　１ｎｉｔ　ｃｏｎｎｅｃｔｏｒｓ（ＬＴ
２．ＣＬＩ、ＬＴ３↑ＣＬ２↑ＩＣ−１５ｃ２］、Ｅｌ
、Ｏｕｔ↑）。

ＬｏｃａｌＪｏ−ｇｌｏｂａｌ（ＣＴ、Ｌａｙｏｕｔ（
Ｃｉｒｃｕｉｔ、ＬＦＮａｍｅ。

５ｈａｐｅ、ＰｅｒｉＣｏｎｎｅｓ、−）。

１ａｙｏｕｔ（Ｃｉｒｃｕｉｔ、ＬＦＮａｍｅ、５ｈａ
ｐｅ。

ＰｅｒｉＣｏｎｎｓ、ｊ　↑＋ＸＱｒｇｙＹＯｒｇｙ　
［−ｙｏ（１）コ↑。

ｅｎｄ、Ｏｕｔ↑）ニー ｇｅｔＪｏｐｃｉｕｃｕｉｔ−ｐｒｏｐｅｒｔｙ（ＣＴ
、［ｃｅｌｌ、−コ　↑）。

ａｄＪｖｅｃｔｏｒ　（Ｓｈａｐｅ＊　［Ｘｏｒｇ、Ｙ
ｏｒｇコ、ＮｅｗＳｈａｐｅ　↑）ｌｔｒｕｅ。

１ｏｃａｌＪｏ−ｇｌｏｂａｌ（ＣＴ、１ａｙｏｕｔ（
Ｃｉｒｃｕｉｔ、ＬＦＮａｍｅ。

５ｈａｐｅ、ＰｅｒｉＣｏｎｎｓ。

［Ｌｕ５ｏｎ、ＬｂＳｏｎ、Ｒｂ５ｏｎコ）。

Ｌａｙｏｕｔ　（Ｃｉｒｃｕｉｔ　、　ＬＦＮａｍｅ　
、　ＮｅｗＳｈａｐｅ　、　ＰｅｒｉＣｏｎｎｓ　。

［ＮＬｕ５．ＮＬｂｓ、ＮＲｂ５．ＮＲｕ５］）↑、Ｘ
ｏｒｇｙＹｏｒｇｙ［−＋ａｄｄ（Ｓｃｌ、ａｄｄ（Ｓ
ｃ２．ａｄｄ（Ｓｃ３，５ｃ４）））コ↑、ｅｎｄ。

Ｏｕｔ↑）ニー ｇｅｔ−ｔｏｐｃｉｒｃｉｕｔ−ｐｒｏｐｅｒｔｙ（Ｃ
Ｔ、　［ｂｌｏｃｋ、−］↑）。

ａｄｃｊｖｅｃｔｏｒ　（Ｓｈａｐｅ　、［Ｘｏｒｇ、
ＹｏｒｇコツＮｅｗＳｈａｐｅ↑） ｇｅｔ−ｓｏｎｓ−ｏｒｉｇｉｎｓ（ＮｅｗＳｈａｐｅ
、　［Ｘｌｕ、Ｙｌｕ、Ｘｌｂ。

Ｙｌｂ、Ｘｒｂ、Ｙｒｂ　、Ｘｒｕ　、Ｙｒｕコ　↑　
）。

１ｏｃａｌｊｏ−ｇｌｏｂａｌ　（ＬｕＳｏｎ　、　Ｎ
Ｌｕ５↑、Ｘｌｕ、Ｙ］、ｕ、［Ｓｃｌコ　↑　、ｅｎ
ｄ、Ｅｌ　↑）。

１ｏｃａｌ　ｔｏ−ｇｌｏｂａｌ、（ＬｂＳｏｎ、ＮＬ
ｂｓ↑、Ｘｌｂ、Ｙｌｂ、　ｃｊＳｃ２］↑、ｅｎｄ、
Ｅ２↑）。

１ｏｃａ１−ｔｏ−ｇｌｏｂａｌ（ＲｂＳｏｎ、ＮＲｂ
５↑、Ｘｌｂ、Ｙｌｂ、　Ｅ−。

Ｓｃ３コ↑　、ｅｎｄ、Ｅ２　↑）。

１ｏｃａＪｔｏ−ｇｌｏｂａｌ（ＲｕＳｏｎ、ＮＲｕ５
↑、Ｘｒｕ、Ｙｒｕ＋［−＋Ｓｃ４コ↑　、ｅｎｄ　、
Ｅ４　↑）、ｊｕｄｇｅ−ｅｎｄ（［Ｅｌ、Ｅ２．Ｅ３
．Ｅ４コ。

Ｏｕｔ↑）。

ｐｒｅｐａｒｅ、ｒｏｕｔｉｎｇではｌｏｃａｌ−ｔｏ
−ｇｌｏｂａｌ述語（第１２図２２６０）によって配置
済オブジェクトの、左上原点位置をチップの世界座標に
変換すると共伜こ、ｃｈｏｏｓ＋、１ｎｉｔ−ｃｏｎｎ
ｅｃｔｏｒｓ　（第１２図２２７０）」； −によって外周部に初期計画したコネクタ以外のコーネ
クタ（配置処理中に生成されたもの）を全て消去する。

これらは、配置計画のｔｏｐＪｏｗｎ相であるｇｅｎｅ
ｒａｔｅ−ｓｕｂｐｒｏｂｌｅｍｓ中での概略配線計画
の際に生成したものであり、計画位置の妥当性が低いた
めである。

］、ｏｃａｌｊｏ−ｇｌｏｂａｌは、配置物の位置座標
をチップ全体の世界座標に変換する。ａｄｃｊｖｅｃｔ
ｏｒによって世界座標上での親の長方形の左上点［Ｘｏ
ｒｇ　、　Ｙｏｒｇ］の示すベクトル分だけ親のフロア
ランプの座標を移動させ、各子供の左上点の世界座４ｍ
　（［Ｘｌｕ、Ｙｌｕｌなど）を取り出して子ノードに
伝えて再帰処理する。各プロセスは一斉にｅｎｄフラグ
を受は取って並列に実行される。このため全体のメモリ
量は各プロセスでの所要量の合計となる。

（Ｐｒｏｇ、５）配線処理述語ｒｏｕｔｅＪｙ−ｑｔｒ
ｅｅの定義節（第１３図参照） ｒｏｕｔｅＪｙ−ｑｔｒｅｅ（Ｓｏｌｄ、ＳＮｅｗ↑、
Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［ａｄｄ（Ｔｅｌ、ａｄｄ（Ｔｃ２．Ｔｃ３））　、ｍ
ａｘ（Ｓｃｌ、ｍａｘ（Ｓｃ２゜５ｃ３））］、Ｍａｔ
ｒｉｘ、ｅｎｄ、Ｏｕｔ↑）ニー５ｏｌｄ　　＝　ｓ（
ＣＴ、ＬＴ、−、−）。

ｇｅｔ−ｔｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ（Ｃ
Ｔ、［ｂｌｏｃｋ、ｆｒｅｅコ↑）、ｇｅｔ　ｌｆｎａ
ｍｅ（ＬＴ、ＬＦＮａｍｅ↑月ｐ１ａｎｆｒａｍｅ　（
ＬＦＮｅｒｎｅ　、　ｇｅｎｅｒａｔｅ−ｓｕｂｐｒｏ
ｂｌｅｍｓｓ　。

５０１ｄ、Ｓｌ↑、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｅｌ
、Ｓｃｌ］＋ｅｎｄ＋Ｅ１↑）。

ｒｏｕｔｅ−ａｌｌ−ｓｏｎｓ（ＬＦＮａｍｅ、５２，
５２↑、　Ｐｒｏｃ　。

Ｃｏｎ５ｔｒＴｃ２．Ｓｃ２コ、Ｍａｔｒｉｘ、Ｅｌ、
Ｅ２　↑　）。

ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ａｇｇｒｅｇａｔ
ｅ−ｒｏｕｔｅｓ、Ｓ２゜ＳＮｅｗ↑＋Ｐｒｏｃ、Ｃｏ
ｎ５ｔｒ、　［Ｔｃ３．Ｓｃ３］、Ｅ２．Ｅ３↑）。

ｒｏｕｔｅ　ｂｙ−ｑｔｒｅｅ（Ｓｏｌｄ、ＳＮｅｗ↑
、Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［ａｄｄ（Ｔｃｌ　、Ｔｃ２）、ｒｎａｘ　（Ｓｃｌ、
５ｃ２）コ、Ｍａｔｒｉｘ、ｅｎｄ。

Ｏｕｔ↑）ニー ５ｏｌｄ　＝ｓ（ＣＴＩ、ＬＴＩ、ＣＬＩ、ＬＬＩ）、
ＳＮｅｗ　＝ｓ（ＣＴＩ。

ＬＴＩ、Ｃ１０，ＬＬ２）↑。

ｇｅｔｊｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ　（Ｃ
ＴＩ　、［ｃｅｌｌ　、ｆｒｅｅコ↑）、ｇｅｔｊｆｎ
ａｍｅ（ＬＴＩ、ＬＦＮａｍｅ↑）ｐｌａｎｆｒａｍｅ
　（ＬＦＮａｍｅ　、ａｄｄ−ｑｔｒｅｅｓ　、Ｓｏコ
ｄ、５（ＣＴ２゜ＬＴ２．ＣＬＩ　、ＬＬＩ）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｅｌ　、Ｓｃｌコ、ｅｎ
ｄ、Ｅｌ　↑）。

ｒｏｕｔｅ−ｂｙ−ｑｔｒｅｅ（ｓ（ＣＴ２．ＬＴ２．
ＣＬＩ、ＬＬＩ）↓、５（ＣＴ２．ＬＴ２．Ｃ１０，Ｌ
Ｌ２）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｃ２．Ｓｃ２］、Ｍａｔ
ｒｉｘ、Ｅｌ、Ｏｕｔ↑）。

ｒｏｕｔｅＪｙ−ｑｔｒｅｅ（ＳＯｌｄ、Ｓｎｅｗ↑、
Ｐｒｏｃ、Ｃｏｎ５ｔｒ。

［Ｔｃｌ、Ｓｃｌコ、阿ａｔｒｉｘ、ｅｎｄ、Ｏｕｔ　
↑）二一５ｏｌｄ　　＝　　５（ＣＴ、ＬＴ、、−）。

ｇｅｔ−ｔｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ　（
ＣＴ　、　［１ｅａｆ−ｉｎ−ｃｅｌ　１−、ｆｒｅｅ
コ　↑　）。

ｇｅｔｊｆｎａｍｅ（ＬＴ、ＬＦＮａｍｅ↑）ｐｌａｎ
ｆｒａｍｅ（ＬＦＮａｍｅ、ｒｏｕｔｅ−ａ−１ｅａｆ
−ｉｎ−ｃｅｌｌ。

５ｏｌｄ、５Ｎｅｔｉ↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［Ｔｅｌ　、Ｓｃｌ］　、
ｅｎｄ、Ｏｕｔ↑）。

ｒｏｕｔｅ−ｂｙ−ｑｔｒｅｅ　（Ｓｏｌｄ　、　Ｓｎ
ｅｗ↑、Ｐｒｏｃ、Ｃｏｎ５ｔｒｓ［Ｔｅｌ、Ｓｃｌコ
、Ｍａｔｒｉｘ、ｅｎｄ、Ｏｕｔ　↑）ニー５ｏｌｄ　
＝　５（ＣＴ、ＬＴ、、−）。

ｇｅｔＪｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ　（Ｃ
Ｔ　、　［−ｆｉｘ］↑）ｐｌａｎｆｒａｍｅ（ｆｉｘ
ｅｄｍｏｄｕｌｅ、ｔａｋｅ−ｒｏｕｔｅｓ、５ｏｌｄ
。

ＳＮｅｗ　↑　、Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［Ｔｅｌ、
Ｓｃｌコ、ｅｎｄ、Ｏｕｔ　↑　）。

［ｍａｘ（Ｔｅｌ、ｍａｘ（Ｔｃ２．ｍａｘ（Ｔｃ３．
Ｔｃ４）））、ａｄｄ（Ｓｃｌ。

ａｄｄ（Ｓｃ２．ａｄｄ（Ｓｃ３，５ｃ４）））コ↑、
Ｍａｔｒｉｘ、ｅｎｄ。

Ｏｕｔ↑）ニー ｇｅｔ−ｓｏｎｓ−ｔｒｅｅｓ（ＣＴ１［５ＣＴ１　＋
５ＣＴ２，５ＣＴ３゜５ＣＴ４コ　↑）。

ｇｅｔ−ｓｏｎｓ−ｔｒｅｅｓ（ＬＴＩ　［５ＬＴ１．
５ＬＴ２，５ＬＴ３゜５ＬＴ４］↑）。

ｇｅＪｓｏｎｓ　ｔｒｅｅｓ（ＣＴ２［５ＣＴｎｌ、５
ＣＴｎ２，５ＣＴｎ３゜５ＣＴｎ４コ↑） ａｓｓｉｇｎ−ｍａｔｒｉｘ（ＬＦＮａｍｅ、Ｍａｔｒ
ｉｘ、［ＬｕＭ、ＬｂＭ、ＲｂＭ。

Ｒｕｂ］、［ＬｕＰＥ、ＬｂＰＥ、ＲｂＰＥ、ＲｕＰＥ
コ）。

ｒｏｕｔｅＪｙ−ｑｔｒｅｅ（ｓ（ＳＣＴＩ、５ＬＴＩ
、ＣＬＩ、ＬＬＩ）。

５（ＳＣＴｎｌ、５ＬＴＩ、Ｃ１０，Ｌ１２）↑ｐｒｏ
ｃ、Ｃｏｎ５ｔｒ、ＬｕＭ、ｅｎｄ、Ｅｌ↑）＠ｐｒｏ
ｃｅｓｓｏｒ（’ＬｕＰＥ）。

ｒｏｕｔｙ−ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣＴ２，５ＬＴ
２．Ｃ１０，Ｌ１２）　。

５（ＳＣＴｎ２，５ＬＴ２．Ｃｌ３．ＬＬ３）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、ＬｂＭ、ｅｎｄ、Ｅ２↑）＠
ｐｒｏｃｅｓｓｏｒ　（ＬｂＰＥ）　。

ｒｏｕｔｙ−ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣＴ３，５ＬＴ
３．Ｃｌ３．ＬＬ３）。

５（ＳＣＴｎ３，５ＬＴ３．Ｃ１０，Ｌ１２）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、ＲｂＭ、ｅｎｄ、Ｅ３↑）＠
ｐｒｏｃｅｓｓｏｒ（ＲｂＰＥ）。

ｒｏｕｔｙ　ｂｙ−ｑｔｒｅｅ（ｓ（ＳＣＴ４，５ＬＴ
４．Ｃ１０，Ｌ１２）。

５（ＳＣＴｎ４，５ＬＴ４．Ｃｌ３．ＬＬ５）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、ＲｂＭ、ｅｎｄ、Ｅ４↑）＠
ｐｒｏｃｅｓｓｏｒ　（ＲｕＰＥ）　。

ｊｕｄｇｅ−ｅｎｄ　（［Ｗｌ　、Ｅ２．Ｅ３．Ｅ４］
　、Ｏｕｔ↑）。

配線も配置と同様に再帰処理を行う。配置においては、
セルは分割不可能な配置単位であり階層終端ノートとな
るが、配線はセル内のコネクタ、例えばトランジスタの
ベースのコンタクト等が終点となる点が異なっている。

そこでセル内のコネクタが階層終端部となるような局所
４分本（及び対応する局所回路水）を作成し、再帰処理
をさらに二界上に配線ネット名付きのコネクタを作成し
た後、力３れを子供に与えて各子供の配線の再帰処理に
移る（第１３図２３５０）。各子供の処理が完了した後
ａｇｇｒｅｇａｔｅ−ｒｏｕｔｅｓによって配線の電気
特性分析のように統合処理を行う（第１３図２３６０）
。

以上の各ステップで、初期状態５Ｏ１ｄは、Ｓｌ、Ｓ２
゜ＳＮｅｗに逐次変換される。

第２節は上述したセルの細分による配線を行う（第１３
図２３１０）。本節起動時には、状態５Ｏ１ｄ中の回路
水ＣＴＩとレイアウト木ＬＴＩは終端となっている。こ
れらを上記の局所４分本で置き換え（第１３図２３７０
）だ断状態を（ａｄｄ−ｑｔｒｅｅｓメツセージでｐｌ
ａｎｆｒａｍｅを起動し５ｏｌｄを５（ＣＴ２．ＬＴ２
゜ＣＬＩ、ＬＬＩ）に変換。ここでＣＬＩとＬＬＩはブ
ロックや他のセルも含めた配線データ）、ｒｏｕｔｅ　
ｂｙ−ｑｔｒｅｅによる配線（第１３図（２３８０）に
よって、５（ＣＴ２．ＬＴ２．Ｃ１０，Ｌ１２）に変換
する。得られた配線データＣＬ２．ＬＬ２と、もとのＣ
ＴＩ、ＬＴＩとで断状態ＳＮｅｗを定義することにより
、２つの局所水を消去して、セル内配線データのみを残
す。

第３節は、セル内配線における局所水の終端部上ｅａｆ
−ｉｎ−ｃｅｌｌでの配線処理を行う（第１３図２３２
０．２３９０）。第５図１４３４部のセル−〒 ：ｌｌ内線線おいて、セル内の最小区画内での配線を…
へ１第４節は形状固定モジュール配線用である（第１３
図（２３３０）。単に外部ファイルから配線データを取
り込む（第１３図２４００）。

配線処理再帰述語ｒｏｕｔｅ−ａｌｌ−ｓｏｎｓは、各
子供についてｒｏｕｔｅＪｙ−ｑｔｒｅｅを用いて、再
帰的に配線を行う。後述の配線統合処理ａｇｇｒｅｇａ
ｔｅ、、−ｒｏｕｔｅｓによって配線の寄生インピーダ
ンスを求めて回路水上に付記することによりＣＴＩはＣ
Ｔ２に変化するが、配置データＬＴＩは変化しない。配
線によって、コネクタデータがＣＬＩからＣ１０に、配
線データがＬＬＩからＬＬ２に各々変化する。

負荷分散については配置の場合と同様の方式で良い。

（Ｐｅｏｇ、６）描画出力述語ｄｔａｗ−１ａｙｏｕｔ
の定義節（第１４図参照） ｄｒａｗ　１ａｙｐｕｔ（ｓ（Ｃｉｒｔｒｅｅ、Ｌｔｒ
ｅｅ、ＣｏｎＬａｙｏｕｔ）、。

Ｐｒｏｃ、−。

［ｍａｘ（Ｔｅｌ、ｍａｘ（Ｔｃ２．Ｔｃ３））、ａｄ
ｄ（Ｓｃ２，５ｃ３））コ。

ｅｎｄ、−）ニー　ｔｒｕｅ ｄｒａｗ−ｐｌａｃｅｍｅｎｔｓ（ＬＴｒｅｅ、Ｐｒｏ
ｃ、［Ｔｅｌ、Ｓｅ２コ。

ｅｎｄ　ｒ　−）　＋ ｄｒａｗ−ｃｏｎｎｅｃｔｏｒｓ　（ＣｏｎＬａｙｏｕ
ｒ　＋　Ｐｒｏｃ　、　［Ｔｃ２　、　Ｓｃ２］　。

ｅｎｄ　、〜〕。

ｄｒａｉｉ−１ｉｎｅｓ（ＬｉｎｅＬａｙｏｕｒ＋Ｃｏ
ｎＬａｙｏｕｔ、Ｐｒｏｃ。

［Ｔｃ３．Ｓｃ３］、ｅｎｄ、−）− 配置・配線処理が終了した時の内部状態を出力表示する
。ＬＴｒｅｅ内の配置データ（第１４図２４１０）及び
ＣｏｎＬａｙｏｕｔ、ＬｉｎｅＬａｙｏｕｔ内のコネク
タ（第１４図２４２０）及び線分データ（第１４図２４
３０）を並列に出力する。セルやコネクタや線分の形状
はデータ削減のために内部状態に記憶せず、それらのタ
イプ名や場所のみを記憶しているａ　Ｐｒｏｃを与えて
いるのは、タイプ名で形状テンプレートｌａｙｐｕｔｆ
ｒａｍｅを検索し、プロセス名Ｐｒｏｃと場所データと
から実形状を生成しつつ描画させるためである。

（Ｐｒｏｇ、７）階層水のノード処理用ｐｌａｎｆｒａ
ｍｅ述語群回路木やレイアウト本を用いた階層処理にお
いて、木の名ノードでの問題分割や統合等の様々の機能
が必要となるにれらの機能を実現するための述語群を一
括して定義する。各述語の形式及びその−船釣機能は次
の通りである。

ｐｌａｎｆ’ｒａｍｅ（ＬＦＮａｍｅ、Ｍｅｓｓａｇｅ
、５ｏｌｄ　、ＳＮｅｗ↑、　Ｐｒｏｃ　。

Ｃｏｎ５ｔｒ、Ｃｏｍｐｌｅｘｉｔｙ、ＥＩＥ２↑）ニ
ー名称がＬＦＮａｍｅの形状テンプレートｌａｙｏｕｔ
ｆｒａｍｅを用いて、与えられたＭｅｓｓａｇｅのもと
に、状態５Ｏ１ｄをＳＮｅｗに変換する。

以下、Ｍｅｓｓａｇｅの内容毎にｐｌａｎｆｒａｍｅの
定義を示す。

（Ｐｒｏｇ、７．１）形状テンプレートｌａｙｏｕｔｆ
ｒａｍｅ選択用ｐｌａｎｆｒａｍｅの定義（第１５図参
照）ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ→、ｃｈｏｏｓ
ｅ−ａ−１ａｙｏｕｔｆｒａｍｅ。

５（ＣＴＩ、ＬＴＩ、ＣＬｌ、ＬＬＩ）、ｓ（ＣＴ１．
Ｌｉ２．ＣＬＩ、ＬＬＩ）↑　。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［ｏ（ｎｏ、ｏｆｌａｙｏ
ｕｔｆｒａｍｅｓ）］↑。

ｅｎｄ　、　Ｏｕｔ↑）ニー ｇｅｔｊｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ　（Ｃ
Ｔ　１　＋　［ｃｅｌ　１、−］↑）。

ｇｅｔＪｏｐｃｉｒｃｕｉｔ−ｔｙｐｅ　（ＣＴ１．［
Ｋｉｎｄ、５ｐｅｃコ　↑）。

ｇｅＪｓｈａｐｅ（ＬＴＩ、５ｈａｐｅ↓↑）ｕｓａｂ
ｌｅ−１ａｙｏｕｔｆｒａｍｓ（にｉｎｄ、５ｐｅｃ、
５ｈａｐｅ、Ｐｒｏｃ。

Ｌａｙｏｕｔｆｒａｍｅｓ↑）。

ｃｈｏｏｓｅ−ａ−ｂｅｓｔ−１ｆｒａｍｅ（Ｌａｙｏ
ｕｔｆｒａｍｅｓ、Ｃｏｎ５ｔｒ。

ＬＦＮａｍｅ↑）。

ｌａｙｏｕｔｆｒａｍｅ（ＬＦＮａｍｅ、Ｂｌｏｃｋｓ
↑ｌ−１−１１−１−１−Ｌｇｅｎｅｒａｔｅ−ｒｅａ
ｌ−ｓｈａｐｌ−１−１−Ｌｉ、Ｂｌｏｃｋｓ）　、ａ
ｄｄｒｅａｌ−ｓｈａｐｅ（ＬＴＩ、Ｌｉ２↑、５ｈａ
ｐｅ、ｅｎｄ、Ｏｕｔ↑）。

ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ｃｈｏｏｓｅ−ａ
−１，ａｙｏｕｔｆｒａｍｅ。

５（ＣＴＩ、ＬＴＩ、ＣＬＩ、ＬＬＩ）、５（ＣＴ２．
Ｌｉ２．ＣＬｌ、ＬＬＩ）↑。

Ｐｒ０ｃ、Ｃｏｎ５ｔｒ、　［ｏ（１）、ｏ（ｎｏ、ｏ
ｆｌａｙｏｕｔｆｒａｍｅｓ）］↑、ｅｎｄ、Ｏｕｔ↑
）ニー ｇｅｔ−ｔｏｐｃｉｒｃｕｉｔ−ｐｒｏｐｅｒｔｙ　（
ＣＴ　１　、　［ｂｌ　ｏｃｋ　、−］↑）。

ｇｅｔ−ｓｏｎｓ−ｗｉｔｈ−ｎｏｄｅｓ（ＣＴＩ、［
［５ｏｎｌ、ＮＳＩ］＋［５ｏｎ２．ＮＳ２コｙ　［５
ｏｎ３．ＮＳ３コ、［５ｏｎ４．ＮＳ４コ］　↑）。

ｇｅｔ−ｓｏｎｓ−１ａｙｏｕｔ−ｔｒｅｅｓ（ＬＴＩ
、［５ｏｎｌ、ＮＳ２，５ｏｎ３゜５ｏｎ４］、［ＬＴ
ＳＩ、ＬＴＳ２．ＬＴＳ３．ＬＴＳ４コ↑）。

ｇｅＪｐｌａｎｎｅｄ−１ａｙｏｕｔ　（ＬＴ　１　＋
　［［Ｗｐ　＋　ＨＰ　ｌ　−］　ｒ　Ｎｃｏｎ　。

Ｗｃｏｎ　、　５ｃａｎ　、　Ｅｃｏｎ　］］↑月ｍｉ
ｎ１−ｗｉｒｅ−ｐｌａｃｅｍｅｎｔ（［Ｎｃｏｎ　、
　ＩＩＩｃｏｎ　、　５ｃｏｎ　。

Ｅｃｏｎコ、［［ＮＳ１．ＬＴＳｌｌ、［ＮＳ２．ＬＴ
Ｓ２］、［ＮＳ３．ＬＴＳ３コ。

［ＮＳ４　、ＬＴＳ４ココ、［Ｌｕｓ、Ｌｂｓ、Ｒｂｓ
、Ｒｕｓコ　↑　、Ｃｏｎ５ｔｒ）。

ｇｅｎｅｒａｔｅ−ｐｌａｃｅ−ｍｅｓｓａｇｅ−ｔｏ
−ａ　１．１１ａｙｏｕｔｆｒａｍｅｓ　（［Ｌｕｓ　
、　Ｌｂｓ　、　Ｒｂｓ　、　Ｒｕｓ］　＋Ｍｅｓａｇ
ｅＬｉｓｔ↑）。

ｆｉｎｄＪｅｓｔ−１ａｙｏｕｔｆｒａｍｅ　（［Ｗｐ
、Ｈｐコ！ＭｅｓｓａｇｅＬｉｓｔ、Ｂｅ５ｔＳｈａｒ
ｅｐｌａｎ↑、ＬＦＮａｍｅ↑）。

ｐｕｔ−ｐｌａｎｎｅｄ−１ａｙｏｕｔ　（ＬＴＩ　、
　ＬＴ２↑Ｂｅ５ｔＳｈａｒｅｐｌａｎ、ｅｎｄ、Ｏｕ
ｔ↑）。

第１節はセルのレイアウトフレーム（形状テンプレート
）を選択する（第１５図２４５０）。回路木ＣＴＩ内に
与えられたモジュールのタイプやスぺＪｌｌ、４９０）
。第２節はブロックレベル用であるＬｌ−７第１５図２
４５　Ｑ　）　。ｇｅｔ＝ｐｌａｎｎｅｄ−１ａｙｏｕ
ｔ　（第ン、１５図２５００）によって親の計画形状［
υｐ　＋　Ｈｐ］計と北、西、南、東辺上の配線ノード
名付きコネクタＮｅｏｎ−Ｅｃｏｎを得る。これと各子
供が持つ配線ノードとの配線長が短くなるように、ｍｉ
ｎ、ｊｗｉｒｅｐｌａｃｅｍｅｎｔ　（第１５図２５１
０）によりレイアウト木ＬＴＩの子供に子回路を配置す
る（第１子〜第４子は平面の４分スライスの左上部分か
ら始めて反時計回りに配置すると約束）　、　［Ｌｕｓ
、Ｌｂｓ、Ｒｂｓ、Ｒｕｓコは配置結果である。この計
画は全てのテンプレートにＭｅｓｓａｇｅＬｉｓｔとし
て伝達される。各テンプレートは外形状［Ｗｐ、Ｈｐ］
平面内に各自の平面分割トポロジーに従って各子供を配
置し、全体形状、アスペクト比、デッドスペースを算呂
する（第１５図２５２０）。最も良好な計画を作れるテ
ンプレート名称ＬＦＮａｍｅと平面分割計画Ｂｅ５ｔＳ
ｈａｒｅｐｌａｎがｆｉｎｄＪｅｓｔ−１ａｙｏｕｔｆ
ｒａｍｅによって選出される□結果はｐｕＪｐｌａｎｎ
ｅ−１ａｙｏｕｔによってＬＴＩの親と子レベルとに記
憶される（第１５図２５３０）。並列にＲ）１６図参照
） ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ｇｅｎｅｒａｔｅ
−ｓｕｂｐｒｏｂｌｅｍｓ。

５（ＣＴＩ、ＬＴＩ　、ＣＬＩ　、ＬＬＩ）、５（ＣＴ
Ｉ　、ＬＴ２．Ｃｌ３．ＬＬＩ）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、　［ｏ（ｎｏ、ｏｆｎｏｄｅ
ｓｉｎｔｈｉｓｂｌｏｃｋ）。

ｏ（ｎｏ、ｏｆｎｏｄｅｓｉｎｔｈｉｓｂｌｏｃｋ）］
、ｅｎｄ、Ｏｕｔ↑）ニーｒｕｅ ｇｅｔ　ｐｌａｎｎｅｄ−１ａｙｏｕｔ（ＬＴＩ、［Ｐ
ｌａｎｎｅｄＳｈａｐｅ、Ｎｅｏｎ。

Ｗｃｏｎ、Ｓｃｏ、Ｅｃｏｎコ↑）。

ｇｅｔ−ｓｏｎｓ−ｎｏｄｅｓ（ＣＴＩ、［Ｎ５ｏｎｌ
、Ｎ５ｏｎ２．Ｎ５ｏｎ３゜Ｎ５ｏｎ４コ↑　）。

ｇｅｎｅｒａｔｅ−ｎｏｄｅｐｒｏｆｉｌｅｓ　（ＬＦ
Ｎａｍｅ　、　［Ｎｃｏｎ　、　Ｗｃｏｎ　。

５ｃｏｎ　、Ｅｃｏｎコ。

［Ｎ５ｏｎｌ、Ｎ５ｏｎ２．Ｎ５ｏｎ３．Ｎ５ｏｎ４］
、ＣＬＩ。

ＮｏｄｅＰｒｏｆｉｌｅＬｉｓｔ↑）。

ｌａｙｏｕｔｆｒａｍｅ（ＬＦＮａｍｅ、−、−、−、
−、ＲｏｕｔｅＰａｔｔｅｒｎｓ↑。

ＧｏａｌＶｅｃｔ↑、−）。

ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ｇｅｎｅｒａｔｅ
−ｇｏａｌ−ｖｅｃｔｏｒ。

ＧｏａｌＶｅｃｔ↓↑。

Ｉｎ１ｔＶｅｃｔ↑、Ｉｎ１ｔＣｏｓｔ↑、Ｐｌａｎｎ
ｅｄＳｈａｐｅ、Ｐｒｏｃ）。

ｇｅｎ、−ｓｕｂｐｒｏｂｌｅｍｓ−ｂｙ−ｒｏｕｔｉ
ｎｇ　（ＮｏｄｅＰｒｏｆｉｌｅＬｉｓｔ　。

ＧｏａｌＶｅｃｔ、Ｉｎ１ｔＶｅｃｔ、Ｉｎ１ｔＣｏｒ
ｓ、ＲｏｕｔｅＰａｔｔｅｒｎｓ。

ＣＬＩ、ＣＬ２↑　、Ｅｌ、Ｏｕｔ↑）。

ｐｒｏｐａｇａ　ｔｅ−ｐ　１ａｎｓ　（ＬＦＮａｍｅ
　、　ＲｏｕｔｅｄＮｏｄｅＰｒｏｆ　ｓ　、　ＬＴ　
ｌ　。

ＫＴ２↑、Ｅｌ、Ｏｕｔ↑）。

子回路の配置と各々の形状とが親平面内に決定さ九た状
態のＬＴＩを用いて、ｇｅｎｅｒａｔｅ−ｎｏｄｅｐｒ
ｏｆｉｌｅｓまでで（第１６図２５５０．２５６０．２
５７０）親の外周コネクタ（Ｎｅｏｎ等）の存在辺、各
ノードのネットの４分画上のバラツキ具合 ＮｏｄｅＰｒｏｆｉｌｅＬｉｓｔを分析する。次にテン
プレート名称ＬＦＮａｍｅのｌａｙｏｕｔｆｒａｍｅか
ら、４分画間を結ぶ配線パターンテンプレート群Ｒｏｕ
ｔｅｐａｔｔｅｒｎｓを呼び出すと共に配線が通過し得
る各子供の外周境界線分数を次元数とする変数ベクトル
ＧｏａｌＶｅｃｔを作成する（第１６図２５８０）、次
のｐｌａｎｆｒａｍｅは親平面の分画形状を表わすｐｌ
ａｎｎｅｄｓｈｏｐｅを用いて各境界線長を計算し、配
線可能本数を求めてＧｏａｌＶｅｃｔの各要素に記入す
る（第６図２５９０）。

配線間隔や配線幅はプロセス依存のレイアウトルールで
あるので、プロセス名Ｐｒｏｃも引数としておき、　１
ａｙｏｕｔｒｕｌｅ（後述）を検索できるようにしであ
る。Ｉｎ１ｔＶｅｃｔは配線可能路を障害する固定セル
の影響などを事前考慮するためのベクトルである。

２差分ＧｏａｌＶｅｃｔ−ＩｎｉｔＶｅｃｔが実配線可
能容量ペクト２局辺境界上に存在する配線コネクタの旧
存在範囲データ（ＣＬＩ内にある）が内部の４分区画の
いずれ）１１かの境界辺上に来るまでに充分縮小されて
いるが否かを調査する。否の場合には縮小可能が否かを
調査し、可能の場合には縮小する。これでも不可能な配
線ノードについては、配線処理を先送りし、隣りのブロ
ックが該コネクタの存在範囲を縮小するのを待つ。すな
わち、並列走行ブロック同士は、共有コネクタをめぐっ
て協調動作する。最終的に各ノード毎に配線テンプレー
ト名称や子回路間の境界上の新コネクタの属性（名称及
び、存在域など）が作成され、ＣＬＩに記入されてＣｌ
３に変更される。最後にｐｒｏｐａｇｅｔｅ−ｐｌａｎ
ｓ　（第１６図２６１Ｑ）によって親レベルで求めた新
コネクタ名称４個の子供の外周辺Ｎ、ｌｉ、Ｓ、Ｅに下
降させる（ＬＴＩはＬＴ２）となる。時間は、親ブロッ
ク内で配線すべきノートを逐次処理するのでｏ（ｎｏ、
ｏｆｎｏｄｅｓｉｎｔｈｉｓｂｌｏｃｋ）、メモリは、
各ノードについての配線を蓄積するためｏ（ｎｏ、ｏｆ
ｎｏｄｅｓｉｎｔｈｉｓｂｌｏｋ）となる。

（Ｐｒｏｇ、７．３）配置部分問題統合用ｐｌａｎｆｒ
ａｍｅの定義節（第１７図参照） ｐｌａｎｆｒａｍｅ（ＬＦＮａｍｅ、ａｇｇｒｅｇａｔ
ｅ−ｐｌａｃｅｎ＋ｅｎｔ。

５（ｓ（ＣＴＩ、ＬＴＩ、ＣＬＩ、ＬＬＩ）、５（ＣＴ
Ｉ、ＬＴ２．ＣＬＩ、ＬＬＩ）↑。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［ｏ（ｎｏ、ｏｆｓｏｎｓ）
コｏ（ｎｏ、ｏｆｓｏｎｓ）］、ｅｎｄ、Ｏｕｔ↑）ニ
ー　ｔｒｕｅｇｅｔ　　５ｏｎｓ−ｓｈａｐｅｓ（ＬＴ
Ｉ、［ＬｂＳｈａｐｅ、Ｒｕ５ｈａｐｅコ　↑）。

ａｇｇｒａｔｅ−ｓｏｎｓ−ｓｈａｐｅｒｓ　（ＬｕＳ
ｈａｐｅ　、　ＬｂＳｈａｐｅ　。

Ｒｂ５ｈａｐｅ、Ｒｕ５ｈａｐｅコ、ＭｙＳｈａｐｅ　
↑　、ＮｅｗＬＦＮａｍｅ　↑　）。

ｒｅｎｅｔｇ−１ｔｒｅｅ（ＭｙＳｈａｐｅ、ＮｅｗＬ
ＦＮａｍｅ、ＬＴＩ、ＬＴ２→＋ｅｎｄ、Ｏｕｔ↑）。

ｇｅｔ　５ｏｎｓ−ｓｈａｏｅｓ　（第１７図２６３０
）によって子供の外周形状を調べ、ａｇｇｒｅｇａｔｅ
、５ｏｎｓ−ｓｈｏａｐｅｓ（第１７図２６４０）でＬ
ＦＮａｍｅ依存の形状統合演算法によって全体形状（外
形と分割点座標からなるＭｙＳｈａｐｅ）を求める。Ｍ
ｙＳｈａｐｅ内の区画形状がＬＦＮａｍｅの定義する形
状トポロジーと異なる場合には、合致するＮｅ＋ｙＬＦ
Ｎａｍｅを求める。最後にＭｙＳｈａｐｅとＮｅ吐ＦＮ
ａｍｅとでＬＴＩを更新しＬＴ２とする（第１７図２６
５０）、計算量、メモリ共にａｇｇｒｅｇａｔｅｓｏｎ
ｓ　５ｈａｐｅｓが主体であり招う子供の数に比例する
のでｏ（ｎｏ、ｏｆｓｏｎｓ）となる。

ｔｕｒｅ　　１ ｇｅｔ−ｐｌａｎｎｅｄ−１ａｙｏｕｔ　（ＬＴＩ　、
　［Ｐ１ａｎｎｅｄＳｈａｏｅＰｅｒｉＣｏｎｎｓコ　
↑　）。

ｒｅｎｅｗ−ｃｏｎｔ−ｒａｎｇｅｆｌａｇ（ｓｔｏｐ
−ｎａｒｒｏｗ−ｄｏｗｎ。

ＰｅｒｉＣｏｎｎｓ、ＣＬＩ、ＣＬ２↑、Ｏｕｔ↑）。

本節以前のｃｈｏｏｓｅ−ａ−１ａｙｏｕｔｆｒａｍｅ
によってレイアウト木ＬＴＩ内にセルの外形状は作成さ
れているので、ここでは当セルの周辺コネクタ上の状態
フラグに・メツセージｓｔｏｐ−ｎａｒｒｏｔｙ−ｄｏ
ｗｎを記入して、周辺コネクタ位置をこれ以上絞り込め
ない旨が隣接ブロックに判るようにしてやる。

（Ｐｒｏｇ、７．５　）セル内配線における終端部処理
ｐｌａｎｆｒａｍｅの定義節（第１８図参照）ｐｌａｎ
ｆｒａｍｅ（ＬＦＮａｍｅ、ｒｏｕｔｅ−ａ　１ｅａｆ
−ｉｎ−ｃｅｌｌ、５（ＣＴＩ、ＬＴＩ、ＣＬＩ、ＬＬ
Ｉ）、５（ＬＴ２，１丁１．Ｃ１０，ＬＬ２ン　↑　。

Ｐｒｏｃ、Ｃｏｎ５ｔｒ、［ｏ（１）、ｏ（］）コ↑　
、ｅｎｄ、Ｏｕｔ↑）＝ｇｅＪｐ　１ａｎｎｅｄ−１ａ
ｙｏｕｔ　（ＬＴ　１　、　［Ｐ　１ａｎｎｅｄｓｈａ
ｏｒ　。

Ｎｃｏｎ、Ｗｃｏｎ、５ｃｏｎ、Ｅｃｏｎ］↑）。

ｇｅｔ−ｍｙ−ｎｏｄｅ（ＣＴＩ、ＩｎＮｏｄｅ）ｇｅ
ｎｅｒａ　ｔｅ−ｎｏｄｅｐｒｏｆｉ　ｌｅｓ　（ＬＦ
Ｎａｍｅ　、　［Ｎｃｏｎ　、　Ｗｃｏｎ　。

５ｃｏｎ、Ｅｃｏｎ］　、ＩｎＮｏｄｅ、ＣＬＩ、Ｎｏ
ｄｅＰｒｏｆｊ　１ｅＬｉｓｔ↑）。

Ｌａｙｏｕｔｆｒａｍｅ（ＬＦＮａｌＩｌｅ、−、−、
−、−、ＲｏｕｔｅＰａｔｔｅｒｎｓ→、ＧｏａｌＶｅ
ｃｔ↑、−）。

ｐｌａｎｆｒａｍｅ　（ＬＦＮａｍｅ　、　ｇｅｎｅｒ
ａｔ＋、ｇｏａ　１．−ｖｅｃｔｏｒ　。

ＧｏａｌＶｅｃｔ↓↑。

Ｉｎ１ｔＶｅｃｔ↑、　Ｉｎ１ｔＣｏｓｔ↑、５ｈａｐ
ｅ、Ｐｒｏｃ）　。

ｇｅｎ、、−ｒｏｕｔｅｓ　（ＮｏｄｅＰｒｏｆｉｌｅ
Ｌｉｓｔ　［１＋　［１ｒＲｏｕｔｅｄＮｏｄｅｓ↑、
ＧｏａｌＶｅｃｔ、Ｉｎ１ｔＶｅｃｔ、Ｉｎ１ｔＣｏｓ
ｔ。

ＲｏｕｔｅＰａｔｔｅｒｎｓ、、−、ＣＬＩ、ＣＬ２↑
、Ｅｌ↑）。

ｍａｋｅ　　１ｉｎｅｓ（ＲｏｕｔｅｄＮｏｄｅｓ↑、
Ｃｌ３．ＣＬ３↑、ＬＬＩ。

ＫＫ２↑、Ｅｌ、Ｏｕｔ↑）。

セルの最小分画内での配線を行う。配線コネクタの分画
周辺及び内部での存在状況を表わすＮｏｄｅＰｒｏｆｉ
ｌｅＬｉｓｔを作成しく第１８図２９７０゜２６８０．
２６９０）、配線パターンを用いて配線する（第１８図
２７００．２７１０．２７２０）。

配線結果はＲｏｕｔｅｄＮｏｄｅｓとなる。これをもと
にｎ＋ａｋｅ　１ｉｎｅｓで配線を作成する（第１８図
２７３０＞。

（Ｐｒｏｇ、７．６）分画境界辺の配線容量算出ｐｌａ
ｎｆｒａｍｅの定義節（第１９図参照） ｐａｎｆｒａｍｅ　（ＬＦＮａｍｅ　、　ｇｒｎｅｒａ
ｔｅ−ｇｏａｌ−ｖｅｃｔｏｒ　。

ＧｏａｌＶｅｃｔ↑ｌ　Ｉｎ１ｔＶｅｃｔ↑、　Ｉｎ１
ｔＣｏｓｔ↑、５ｈａｐｅ。

Ｐｒｏｃ）ニー ｔｒｕｅ ｌａｙｏｕｔｒｕｌｅ（ｕｓａｂｌｅｊａｙｒｓ、Ｐｒ
ｏｃ、Ｌａｙｅｒｓ↑）。

ｌａｙｏｕｔｒｕｌｅ（ｍｉｎｉ−１ｉｎｅ−ｗｉｄｈ
ｔ、Ｐｒ０ｃ、−、−、−。

す１ｄｔｈ↑−２−）。

ｌａｙｏｕｔｒｕｌｅ（ｍｉｎｉ　　１ｉｎｅ　ｄｉｓ
ｔａｎｃｅ、Ｐｒｏｃ、−、−、−。

−ｔｌ）１ｓｔ↑）。

ｇｅｎ−ｖｅｃｔｏｒｓ−ｆｏｒ−ｒｏｕｔｅ　（ＬＦ
Ｎａｍｅ　、　５ｈａｐｅ　。

Ｌａｙｅｒｓ　、　Ｗｉｄｔｈ　、　Ｄｉｓｔ　、　Ｇ
ｏａｌＶｅｃｔ↑、　Ｉｎ１ｔＶｅｃｔ↑。

Ｉｎ１ｔＣｏｓｔ↑）。

ｌａｙｏｕｔｆｒａｍ上に配置された子回路及び外部間
の全境界線上を通過し得る配線本数を要素としたベクト
ルＧｏａｌＶｅｃｔを作る（第１９図２７８０）、プロ
セスＰｒｏｃ依存の１ａｙｏｕｔｒｕｌｅを参照して（
第１９図２７５０．２７６０．２７７０）可能本数が求
められる。

（Ｐｒｏｇ、７．７）配線統合用ｐｌａｎｆｒａｍｅの
定義節ｐｌａｎｆｒａｍｅ　（ＬＦＮａｍｅ　、　ａｇ
ｇｒｅｇａｔｅ、、−ｒｏｕｔｅｓ　、　ｓ　（ＣＴ　
ｌ　。

ＬＴＩ、ＣＬＩ、ＬＬＩ）、５（ＣＴ２．ＬＴＩ、ＣＬ
Ｉ、ＬＬＩ）↑。

Ｐｒ０Ｃ，Ｃｏｎ５ｔｒｙ［−＋−］ｔｅｎｄ＋ｏｕｉ
↑）ニー　ｔｒｕｅＢｏｄｙ。

配線電気特性分析や不具合の改良用。

（Ｐｒｏｇ、８）形状テンプレートｌａｙｏｕｔｆｒａ
ｍｅの定義節１ａｙｏｕｔｆｒａＩＩｌｅ（ｔｙｐｅ（
ｔｒ、Ｐｒｏｃ、５ｐｅｃ）　、Ｂｌｏｃｋｓ↑。

Ｃｏｎｎｅｃｔｏｒｓ↑、　Ｌｉｎｅｒｓ↑、Ｐｒｏｐ
ｓ↑ｌ−１−１０ｂｓｔａｃｌｅｓ↑）ニー　ｔｒｕｅ
　ｌ　Ｂｏｄｙ。

ｌａｙｏｕｔｆｒａｍｅ（ｔｙｐｅ（ｒｅｓ、Ｐｒｏｃ
、５ｐｅｃ）　、Ｂｌｏｃｋｓ↑。

Ｃｏｎｎｅｃｔｏｒｓ↑、Ｌｉｎｅｓ↑、Ｐｒｏｐｓ↑
ｔ−１−１０ｂｓｔａｃｌｅｓ↑）ニー　ｔｒｕｅ　ｌ
　Ｂｏｄｙ。

ｌａｙｏｕｔｆｒａｍｅ　（ｔｙｐｅ　（ｂｌｏｃｋ　
、　Ｐｒｏｃ　＋　５ｐｅｃ）　、　Ｂｌｏｃｋｓ↑。

Ｃｏｎｎｅｃｔｏｒｓ↑、　Ｌｉｎｅｓ↑、　Ｐｒｏｐ
ｓ↑。

ＲｏｕｔｅＰａｔｔｅｒｎｓ↑、　Ｇｏａ　ＩＶｅｃｔ
ｏｒ↑。

０ｂｓｔａｃｌｅｓ↑）ニーｔｒｕｅ　　Ｂｏｄｙ。

トランジスタや抵抗などのセル、あるいはブロックなど
の形状テンプレートである。上記はその代表例である。

プロセスＰｒｏｃや仕様５ｐｅｃに応じて種々定義して
おく。出力は形状構成要素Ｂｌｏｃｋｓ。

Ｃｏｎｎｅｃｔｏｒｓ　、　Ｌｉｎｅｓ等、電気特性Ｐ
ｒｏｐｓ、配線障害物形状０ｂｓｔａｃｌｅｓ等である
。左辺のこれらはＢｏｄｙ部に定義文が与えである。ｂ
ｌｏｃｋについては配線パターンＲｏｕｔｅＰａｔｔｅ
ｒｎｓや配線容量定義ベクトルＧｏａｌＶｅｃｔも出力
できるようになっている。

（Ｐｒｏｇ、９）プロセス制約１ａｙｏｕｔｒｕｌｅの
定義部１ａｙｏｕｔｌｅ（ｕｓａｂｌｅ　１ａｙｅｒｓ
、Ｐｒｏｃ、Ｌａｙｅｒｓ↑）ニーｔｒｕｅ　　Ｂｏｄ
ｙ。

ｌａｙｏｕｔｌｅ（ｍｉｎｉ−１ｉｎｅ−ｄｉｓｔａｎ
ｃｅ、Ｐｒｏｃｔ−＋−＋−ｙ−＋Ｄｉｓｔ↑）ニー　
ｔｒｕｅ　ｌ　Ｂｏｄｙ。

ｌａｙｏｕｔｌｅ（ｍｉｎｉＪｉｎｅ−ｅｗｉｄｔｈ、
Ｐｒｏｃ、−、−、−、Ｗｉｄｔｈ２．３　　ＨＲＣＴ
Ｌの評価 ＨＲＣＴＬの評価をアルゴリズム面、機能面から行う。

２．３．１　　アルゴリズムの時間・空間複雑度ＨＲＣ
ＴＬの時間・空間複雑度について考察する。

（定義１）Ｂ　（ｄ、ｒ）によって深さｄ−１のバラン
スｒ分水を表わす。ｒは木の各ノードの持つ枝の数、ｄ
は木の頂点ノードから終端ノードまでのノードの数であ
る。

（定理１）Ｂ　（ｄ、ｒ）の総ノード数は、１＋ｒ＋＝
−＋ｒ’−’＝（ｒ’−１）／（ｒ　　１）である。

（定理２）総終端ノード数ＮＬ、技末ｒのＢ　（ｄ。

ｒ）の深さはｄ　”　ｌｏｇｒ　Ｎ　Ｌ　＋　１である
。（＋４−１＝ＮＬより） （定義２）−Ｂ　（ｄ、ｒ）をＨＲＣＴＬによって充分
多量のプロセッサ上でレイアウトする時の時間複雑度、
領域複雑度を各々ｔｃｏｍｐ（ｄ、ｒ）　、ｓｃｏｍｐ
（ｄ、ｒ）で表わす。

ｒｏｕｔｅの複雑詞は主として、ｐｌａｃｅ−ｂｙ−ｑ
ｔｒｅｅ（Ｐｒｏｇ。

３）とｒｏｕｔｅＪｙ−ｑｔｒｅｅ　（Ｐｒｏｇ、　５
）によって決まり、かつ双方は類似の雑複度項を有する
。そこでｐｌａｃｅｂｙ−ｑｔｒｅｅを考察する。帰納
法を用いる。

ｄ＝１　（セルのレイアウト）の時：　（Ｐｒｏｇ、７
．４）よりｔｃｏｍｐ（１＋ｒ）＝ｏ（１）＋５ｃｏｎ
＋（Ｌｒ）−ｏ（１）。

ｄ＝ｄ（ブロックのレイアウト）の時：　（Ｐｒｏｇ、
３）（ＰｒＯｇ、７．１〜７．３）を用いて次を得る。

ｔｃｏｍｐ　（ｄ　、　ｒ　）＝ａｄｄ　（０（１）　
ｙａｄｄ　（ｏ　（ｎｏ、ｏｆｎｏｄｅｓｉｎｔｈｓｂ
ｌｏｃ）　。

ａｄｄ（ｗａｘ（Ａ）　、ｏ（ｎｏ、ｏｆｓｏｎｓ））
）　。

ｓｃｏｍｐ（ｄ、ｒ）：ｍａｘ（ｏ（ｎｏ、ｏｆｌ、ａ
ｙｏｕｔｆｒａｒｎｅｓ）、ｒｎａｘ（。

（ｎｏ、ｏｆｎｏｄｅｓｉｎｔｈｉｓｂｌｏｃｋ）、ｍ
ａｘ（ａｄｄ（Ｂ）　＋０（ｎｏ。

ｏｆｓｏｎｓ）））　。

Ａはｒ個の子供の各々のｔｃｏｍｐ（ｄ　−１、ｒ’）
、Ｂは同じ＜ｓｃｏｍｐ　（ｃｌ　−１＋　　ｒ）に渡
る。考察中の木が完全バランス木Ｂ　（ｄ、ｒ）である
ので、ｍａｘ一般のｒについて考察する。Ｐｌａｃｅ　
ａｎｄ平均ノード数）、ｎｏ、ｏｆｓｏｎｓ　＝＝　ｒ
として、ｔｃｏｍｐ　（ｄ　、　ｒ）：ｏ　（１）＋ｏ
　（ｎ）＋５ｃｏｎ＋　（ｄ−１ｒ　ｒ）＋ｏ　（ｒ）
＝ｄ　：（ｏ（１）＋ｏ（ｎ）＋ｏ（ｒ）９＝ｏ（ｄ）
。

５ｃｏＩＩｌｐ（ｄ、ｒ）＝ｒ＊ｓｃｏｍｐ（ｄ−１，
ｒ）＝ｒ’−”ｏ（１）＝ｏ（ｒ”）。

但し、上記ｔｃｏｍｐ　（１、ｒ　）＝ｏ　（１）　、
　ｓｃｏｍｐ　（１、ｒ　）＝ｏ　（１）を再帰の終結
部で使用した。

（Ｃｏｎｓｉｄｅｒａｔｉｏｎｓ）充分なメモリがあれ
ば、ＨＲＣＴＬは木の深さｄのオーダの時間で、（素子
シンボル数で言うと、（Ｔｈｅｏｒｅｍ、２）よりｌｏ
ｇｒＮＬオーダ）で、ｒ′−１のサイズメモリを用いて
解ける。

但し、並列プロセス間のコミュケーションコストはここ
では無視した。並列論理言語の筒形式中に複雑度項を加
えることによって、アルゴリズムの意味、構文、複雑度
を同時に記述し解析し得ることを示した。

２．３．２　　レイアウトの特性向上 ＨＲＣＴＬは計画（Ｐｒｏｇ、７．１．７．２）と統合
（Ｐｒｏｇ、７．３）の両相を持つ。計画時に概略計画
を適切に立案し、統合時に不具合を修正させることによ
りレイアウトの特性向上を図れる。

２．３．３　　プログラムの汎用性 プロセスやデバイスに依存する（Ｐｒｏｇ、８．９）を
差し替えることにより、各種の対象に適用できる構造と
なっている。なお、第６図内のプロセス制約（１５３０
）、形状テンプレート（１５２０）、；分割統合機能（
１５１０）は、本実施例では２次−し元手面内でのレイ
アウトを対象としたが、これらニーを３次元空間内での
レイアウトを対象とするもの二に拡張することは非常に
容易である。すなわち、平面の４分割方式を用いるかわ
りに、空間の８分割方式を用いれば良い。この変更に対
応するには、主として形状テンプレート（１５２０）を
直方体の８分画パターンとすると共に、分割統合機能（
１５１０）を、この３次元直方体に対する分割・統合操
作を行うものに変更すればよい。

さらに、付言すると、上記実施例では平面の４分割を基
本として説明したが、これを縮退させることによって３
分割、２分割等の場合も扱えることは自明である。

２．３．４　　プログラムの開発性 再帰式の定式化により一般のレイアウトプログラムに比
べて記述量は大きく圧縮されている。

３、レイアウト実験 ｑ５の固定ベース電位をｑ６＊　ｑ’７＋ｑ８等のベー
スに伝えて、それらのコレクター電流を一定化し、回路
の動作点を固定化する。差動アンプは電圧入力電圧出力
増幅器、出力ｔｒ　（ｑ３．ｑ４）はレベルシフタであ
り、継続段の差動アンプのベース入力に直接接続できる
よう電圧レベルを下降させている。

（２）レイアウト時の考慮制約二本発明の電子回路の並
列処理による配置配線機能を実現することが本実験の目
標であるため、各素子の形状はほぼ同一化した。配置配
線時のペア条件、素子のアイソレーション、配線層、レ
イアウトルール等につ、請イポーラアナログ回路（２１
０００）（ｔｒ＝１、・１．１個、ｒｅＳ：８個、ｃａ
ｐａ＝ｏ個、信号入出力端子＝各２個、ｖｃｃ、ｇｎｄ
端子端子側１個本回路は入力（ｉｎｌ、１ｎ２）（２２
１００）を差動アンプ（ｑｌ、ｑ２系）で増幅し、端子
（ｏｕｔｌ、ｏｕｔ２）（２２２００）に出力する。電
圧源（ｑ５＋　　ｒ　１　ｇ　ｒ　５　）はダイオード
ｉＪ−，（３）入力データ作成：実験１では、第２０図
′ＩＬｉＩＡ）のアンプ回路を階層化して回路水とした
。

階層図を図中（Ｂ）に示す（２２０００）。

（４）確認事項： Ｔｌ装機能：並列処理によって配置が作成されること。

制約条件として考慮した配線長が短くなること。面積の
少ない配置が得られること。

−１線機能：並列処理によって配線が作成されること。

ネット端点が接続されること。

３．１．２　　実験結果 チップの左辺に入力コネクタ、右辺に出力コネクタを指
定して自動レイアウトした結果および入出力コネクタを
これと左右逆にした時のレイアウト結果、並列推論マシ
ンマルチＰＳｌ上で約２０秒を要した。

３．２　実験結果の評価 ３．２．２　　配置機能 素子形状がほぼ同一である回路を、デッドスペース無く
配置できたことで、面積縮小機能が確認できた。配線長
をできるだけ短くする配置を作る機能は、入出力端子位
置変更に対して素子配置が自動的に適応したことで確認
できた。

３．２．３　　配線機能 一部の配線が混み合っているケースもあるが、配線すべ
きコネクタ間をできるだけ直線で結ぶ機能があることが
目視確認できた。内部では階層的に分割して処理してい
るにもかかわらず素子の間の配線が不要に屈曲せず、従
った配線専用のチャネルを必要としていない。

〔発明の効果〕

周知の如く、ＬＳＩ開発において、レイアウト自動化は
古くから重要な問題であり、数多くの方式が開発、実用
化されてきた。しかしながら、従来の方式では、特に階
層処理において顕著に出てくる。異ブロック間の形状や
配線端子位置の不整合によるチップ面積増加やプログラ
ム規模の太きさ、汎用性の低さ等が問題であった。従来
技術に対する本発明方式の特徴を次にまとめる。

（１）レイアウト方式としての特徴：著名なものとして
、配置・配線が不要であるＰＬＡ、配線のみを必要とす
るゲートアレイ、固定かつ形状のは属する。

プロセス内のレイアウトルールやレイアウトフレームの
差し替えによって種々のデバイスやプロセスに適用でき
るソフトウェア構成となっている。

（４）プログラム規模：回路水をレイアウト木に変換す
る上記の過程は、再帰アルゴリズムとして実現している
。第１０図２１１０に示すように、同一のプログラムの
繰り返し利用によって大規模問題を処理しているため、
レイアウトプログラムの規模は、従来の方式（１０４〜
１０５オーダ）にために大規模なメモリや並列プロセッ
サが必要となるが、応分の処理スピード向上は期待でき
る。

レイアウト面積の縮小、配線率の向上、配置・配線にお
ける電気特性の考慮等の問題については、問題分割フェ
イズ（第１０図２１００．２１０５等）に種々の制約を
考慮する機能を追加することで対応できる。

（３）汎用性：第１図１５００のレイアウト基本環に従
って階層処理が行われる。階層処理においｉ〒 −では本来ならば分割せずに解きたい原問題（本例では
原回路ネットリスト）を無理に分割処理する。

二；分割結果生じる各部分問題が相互関係の調整（本例
では隣り合う子回路のレイアウト形状の整合や、子回路
間境界線上の配線コネクタ位置の整合）を要する場合が
一般的である。逐次処理によってこの問題を解く場合に
は、禁止的な時間を要するバックトラックによるか、収
束計算によって解を漸近的に改良する方式をとる。本発
明の並動処理によって解く場合には、並列走行するプロ
セスに、各自が動作可能となるだけの情報が充分に集ま
るまで待つという遅延機能を持たせることで効率的に解
を求めることができた。すなわち、階層処理を部分問題
間の相互関係を自動調整しつつ並列モードで高速処理す
ることが可能となった。この機能を持たない通常の並列
処理では、部分問題間でコミュニケーション不足のため
にブロック形状や境界上の配線コネクタ位置のずれのた
め、ブロック間にデッドスペースや配線用チャネルが必
要と一図、第６図は、レイアウト基本プロセス説明図、
第７図は、最上位プログラムの流れ図、第８図は、入力
、配置・配線、出力プログラムの流れ図、第一９図は、
配置・配線プログラムの流れ図、第１０図は、配置プロ
グラムの全体流れ図、第１１図は、配置における再帰処
理部の流れ図、第１２図は、配線前処理プログラムの流
れ図、第１３図は、配線プログラムの全体流れ図、第１
４図は、出力表示プログラム流れ図、第１５図は、配置
問題分割プログラムの流れ図、第１６図は、配線プログ
ラム流れ図、第１７図は、形状統合プログラム流れ図、
第１８図は、セル内末端区画内の配線プログラム流れ図
、第１９図は、配線可能本数ベクトル算出プログラム流
れ図、第２０図は、実験結果説明図である。

１１００：原データ、］−２００：状態メモリ、ニ態メ
モリの内容説明図、第４図は、入出力プロセ”Ａｆｊ；
６　ｎｆｉ　＠　、第、４よ、□８ヶ決プ。ヤニ内容読
。

色１；ノｒンｊ 〒ｌｌ−図 不乙閑 条Ｓ図 を７ 図 半２（２） ″”ｆ＝ｔλ図 ）ｒ　ノＳ二　図 穿ノｂ図 第７ｒ図 質Ｄ 第２θ図 （峻捗未 （、Ａ）　入力回路体ットヘ〆、２（ｏｏ。

（Ｆ３）静ロト〜ｘｘｏｏ。

Claims (1)

1. 【特許請求の範囲】 １、配置物とそれらの間の接続関係を与える回路データ
   、及び該回路データをレイアウトする際のチップの外形
   状と外端子位置とが与えられたもとで、チップ全体をレ
   イアウトする方法において、 （ａ）目標の形状と外端子位置とを利用して回路間題全
   体を複数個の部分問題に分割する ステップと、 （ｂ）各部分問題を互いに共有した制約条件を守りなが
   ら、互いに並列に処理するステッ プと、 （ｃ）処理を終了した部分問題を統合して親のレイアウ
   トを生成するステップと、 からなることを特徴とする回路レイアウト方法。 ２、部分問題の構造を、チップの外形状と外端子位置と
   することを特徴とする請求項１記載の回路レイアウト方
   法。 ３、上記処理ステップは、並列処理する各部分問題を有
   限個の計算機の上に負荷分散するステップを有すること
   を特徴とする請求項１記載の回路レイアウト方法。 ４、各部分問題のレイアウト外形状と、外端子位置を互
   いのレイアウト作成上の制約条件とすることを特徴とす
   る請求項１記載の回路レイアウト方法。 ５、制約条件を満足させるために、外形状と外端子位置
   からなる制約データを状態メモリに記憶しておき、並列
   走行中のプログラムからアクセスするようにしたことを
   特徴とする請求項４記載の回路レイアウト方法。 ６、外端子位置を存在許容範囲形式のデータで保持する
   ことを特徴とする請求項４記載の回路レイアウト方法。 ７、外端子存在範囲を、自ブロックの内部の配線ネット
   のトポロジーに応じてメインテナンスするステップを有
   することを特徴とする請求項６記載の回路レイアウト方
   法。 ８、上記分割ステップあるいは上記生成ステップを実現
   するために、空間の複数部分空間への分割代替案と、各
   代替案に依存して定まる部分空間の間の配線引き回し方
   式の代替案とを少くとも要素として持つプログラムライ
   ブラリを用いることを特徴とする請求項１記載の回路レ
   イアウト方法。 ９、上記ライブラリを用いて、上記分割又は生成ステッ
   プの動的手続きを行うことを特徴とする請求項８記載の
   回路レイアウト方法。 １０、上記分割ステップにおいて、上記ライブラリの中
   から適切なものを選び出すステップを持つことを特徴と
   する請求項８記載の回路レイアウト方法。 １、上記生成ステップの処理の結果、選んだライブラリ
   が不適切なものと判明した場合に、適切なものに変更す
   るステップを有することを特徴とする請求項１０記載の
   回路レイアウト方法。 １２、階層の親ブロックがさらに上位から伝達された使
   用可能な計算機の集合を部分集合に分割し、各部分集合
   を各子ブロックに伝達すると共に、各部分集合の中から
   ひとつの代表計算機を選んで、これに当該部分集合を受
   理する子ブロックを割り当てることを特徴とする請求項
   ３記載の回路レイアウト方法。 １３、階層非終端部では、上記分割、処理、生成ステッ
   プを繰り返し適用すると共に、階層終端部では終端部処
   理を行なうことを特徴とする請求項１記載の回路レイア
   ウト方法。 １４、階層内の各ブロックの配置形状とブロック代表点
   の局所座標系での位置を決め、次に配置位置を全体座標
   系に変換したのち、階層内の各ブロックの配線をおこな
   うことを特徴とする請求項１３記載の回路レイアウト方
   法。 １５、子ブロックの面積と形状に応じて親ブロックの目
   標形状を分割して子ブロックの目標形状を生成すること
   を特徴とする請求項９記載の回路レイアウト方法。 １６、子ブロック間の配線用き回しに採用したパターン
   が、各子ブロック間の境界辺上を横切る点に仮想端子を
   設けて、これを子ブロックの目標外端子とすることを特
   徴とする請求項９記載の回路レイアウト方法。 １７、空間分割ライブラリとして、平面の複数部分平面
   への分割パターンと共に、分画間配線パターンを保有さ
   せることにより２次元レイアウトを並列実施することを
   特徴とする請求項８記載の回路レイアウト方法。 １８、空間分割ライブラリとして空間の複数部分空間へ
   の分割パターンと共に、分画間配線パターンを保有させ
   ることにより３次元レイアウトを並列実施することを特
   徴とする請求項８記載の回路レイアウト方法。 １９、原回路データファイル、これを階層化するととも
   に出力描画を行う入出力プロセスと、回路階層データと
   レイアウト階層データ及び各ブロックの外端子と配線デ
   ータを記憶する状態メモリと、該メモリを用いて階層問
   題解決を行なう問題解決推論プロセスと、問題解決推論
   中に使用するプロセス制約、形状テンプレート、問題分
   割、統合機能を要素とするレイアウト基本プロセスとを
   備え、上記各プロセスと状態メモリとを双方向ストリー
   ムで接続した構成の回路レイアウトシステム。