JPH0444983B2 - - Google Patents

Description

【発明の詳細な説明】

［産業上の利用分野］ 本発明はコンピユータエイデツド・デザイン
（コンピユータによる設計支援）に関するもので
あり、更に具体的には複数の異なつたサイズの素
子を素子位置アレイ中の素子位置に最適割当てす
ることに関するものである。 ［従来技術］ コンピユータエイデツド・デザイン技術が電子
装置の設計の種々の段階で利用されている。コン
ピユータエイデツド・デザインは電子装置の１つ
又はそれ以上の素子を設計するためにも利用でき
る。そして素子配置プログラムを用いて異なつた
サイズの素子を予定の相互接続条件に従つて次レ
ベル・パツケージ上に配置することができる。次
レベル・パツケージはその上の素子配置可能位置
のアレイを規定するものと見ることができる。他
のコンピユータエイデツド・デザイン・プログラ
ムを用いて次レベル・パツケージ上の素子間の特
有の配線経路をデザインすることができる。 素子配置プログラムは夫々の次レベル・パツケ
ージ上に全ての素子を最適に配置するため利用さ
れる。配置されるべき素子はマクロ素子、即ち第
１レベル・パツケージ上に配置される所定の機能
を達成するための関連回路群、例えば大規模集積
（LSI）回路チツプ又は半導体ウエハでもよい。
そればかりでなく、素子は、第２レベル・パツケ
ージ、例えば印刷回路板又は多層セラミツク基板
上に配置される複数の異なつたサイズの電子的構
成要素（コンポーネント）、例えば大規模集積回
路、抵抗器、キヤパシタ等でもよい。又、配置さ
れる素子は第３レベル・パツケージ、例えばマザ
ーボード上に載置される印刷回路板でもよい。素
子配置プログラムは次レベル・パツケージ上の素
子相互接続の配線を簡単化し、しかも種々の物理
的、技術的、及び他の制約に従う素子レイアウト
を実現するものでなければならない。物理的制約
とは、全ての素子は相互に重なつたり、又は次レ
ベル・パツケージの側方に掩いかぶさつたりして
はならないことを指す。技術的制約とは、素子間
に多数の相互接続をなしうる限られた配線スペー
スを指す。他の制約は、予め割当てられた入出力
コネクタ、テスト・ポイント等の位置、及びシス
テム設計者が強制する他の制約に関する。 数多くの素子配置プログラム及び技術が従来知
られているが、それらは配置上の制約を満足しつ
つ複数の異なつたサイズの素子の複雑な配置を正
しく処理することができない。素子の数及び複雑
さが増し且つ素子実装密度が増すにつれて、従来
周知の自動素子配置プログラムに必要なコンピユ
ータ処理時間が増加して事実上実施不能となる。
そればかりか結果の配置は構成素子の割付け及び
ルール違反の点で最適とはいえないことが多い。 従来技術の１例は米国特許第3654615号である。
そこに開示された素子配置方式では、第２レベ
ル・パツケージ上に配置されるべき他の素子に対
する関連の程度に従つて全ての素子を先ず配列す
る。最も関連度の高い素子を第２レベル・パツケ
ージの中央部分に割当てた後、次の素子を最初の
素子に並べて割当てる。このようにして全ての素
子が割当てられるまで１つ宛素子の割当てを続け
る。 他の従来技術の例が米国特許第3981782号に開
示されている。それは全ての素子を２構成要素、
３構成要素、等を有するネツトに分割しそれに続
いて全てのネツトが配置され終るまで次レベル・
パツケージ上にネツトを配置する素子配置プログ
ラムを開示している。 素子配置技術のあらましが「Design
Automation of Digital Systems−Theory and
Techniques」第１巻、M.Hanan及びJ.M.
Kurtzberg共著、M.A Breur編（Prentice Hall
社1972年刊）の第５章に述べられている。上述の
従来技術は、素子を配置する高度に複雑な問題を
解決できる更に融通性のある配置プログラム（即
ち複数の異なつたサイズの素子を自動的且つ効率
良く配置するプログラム）が現存していないこと
を示す。 ［発明が解決しようとする問題点］ 相互に予定の関係を有する複数の異なつたサイ
ズの素子に対して素子位置のアレイ中の素子位置
を割当てるための従来の素子配置プログラムは全
て要因を１度に考慮に入れて処理したため複雑で
あり、従つてコンピユータ処理に長時間を要して
効率的でなかつた。本発明はこの問題点を解決し
ようとするものである。 ［問題点を解決するための手段］ 上記の問題点は複数段階のプロセス例えば３段
階プロセスで素子の最適配置を決定することによ
り効率をよくする素子配置プログラムによつて達
成される。第１の段階では全ての素子をあたかも
同一のサイズ（単位サイズ）であるかのようにし
て取扱う。そして単位サイズに対する最適配置
を、相互の間の予定の相互接続に従つて素子位置
のアレイにおける素子位置に対して単位サイズ素
子を割当てることにより決定する。その後、最適
配置された単位サイズ素子は、実際の素子サイズ
に対する大まかな近似サイズを有するマクロ・サ
イズ素子と置換される。全てのマクロ・サイズ素
子はそれらのサイズ及び形状を考慮に入れて最適
配置の目的で再配列される。最適配置されたマク
ロ・サイズ素子は最後に実際のサイズの素子と置
換され、その配置は正確なサイズを考慮に入れる
ため再び最適化される。 ３段階（単位サイズ、マクロサイズ、及び実サ
イズ）プロセスで素子配置を最適化することによ
り、本発明の配置プログラムは極めて能率的にな
る。なぜならば、このプログラムは素子の全ての
寸法的な特徴を一度に考慮に入れる必要がないか
らである。そればかりか、単位サイズ、マクロサ
イズ及び実サイズと素子をモデル化するこの反復
方法は、得られた最終的配置が本当に最適化され
ていることを保証する。 本発明を実施するために具体的な方法を以下に
述べるが、配置されるべき素子は種々のサイズ、
形状及び複雑性を有する電子的構成要素、例えば
大規模集積回路、個別的なキヤパシタ、及び抵抗
器パツク等である。電子的構成要素は、それらを
電気的に接続するための配線面を有する回路板で
ある第２レベル・パツケージ上の構成要素装着位
置に割振される。しかしこの方法は次レベル電子
パツケージ上に異なつたサイズの電子的構成要素
を配置するのにも同様に適用できるばかりか、複
数の異なつたサイズの相互関連素子を予定のアレ
イの範囲内に構造パターン化する数多くの商業上
及び産業上の要請に対しても適用できることは当
業者なら了解できるであろう。 本発明によれば、構成要素及びカード（回路
板）の実サイズ・モデル、マクロサイズ・モデ
ル、単位サイズ・モデルが形成される。構成要素
及び回路板の実サイズ・モデルは、素子配置プロ
グラムに対する入力情報から形成される。回路板
に対する実サイズ・モデルは回路板の寸法、基盤
目状の入出力バイヤホールの場所を含む。バイヤ
ホールの基盤目が回路板上の素子配置位置のアレ
イを限定する。各構成要素に対して寸法、ピン数
及びピン位置が与えられるばかりか、構成要素間
になされるべき相互接続を限定するネツト・リス
トが与えられる。 構成要素及び回路板に対して単位サイズ・モデ
ル及びマクロ・サイズ・モデルが形成される。単
位モデル化については、各構成要素は水平及び垂
直方向に１つの単位として限定された同一のサイ
ズ及び形状を持つ。単位モデル回路板のサイズは
全ての単位サイズ構成要素に適合するのに十分な
大きさのものであり、実サイズ回路板の高さ及び
幅を実サイズ構成要素の平均高さ及び幅で割るこ
とによつて得られる。マクロ・モデル化について
は、各構成要素は、各構成要素のサイズはその実
サイズに大体比例し、実サイズを尺度係数で割る
ことによつて得られる。尺度係数は最も普通の構
成要素の高さ又は幅である。マクロ・モデル回路
板のサイズは全てのマクロサイズ構成要素に適合
するのに十分な大きさのものであつて、単位回路
板寸法にマクロ・サイズ構成要素の平均の高さ及
び幅を乗じることによつて得られる。単位及びマ
クロ・モデルを形成するのに先立つて、単位及び
マクロ・モデルにおける配置を簡単化するため小
さな構成要素が構成要素の組から除外されてもよ
い。これらの小さな構成要素はその後、実モデル
配置ステツプ中に再挿入できる。 本発明によれば単位サイズ構成要素は単位サイ
ズ回路板上に最適配置される。既知の配置最適化
方法を利用してもよい。本発明で採用した方法は
最も接続度の高い構成要素が最先に単位サイズ回
路板上に配置されるように、全ての構成要素を他
の構成要素に対する接続度の関数として分類す
る。分類は種子となる構成要素からクラスタ（即
ち相互接続度の高い構成要素のグループ）を形成
することにより達成される。種子構成要素はクラ
スタ形成に際して核として働らく。次に全てのグ
ループの順序づけを行なつて、グループの相互接
続度に基づいて全ての構成要素の序列を作る。 次に単位サイズ構成要素は、構築的な配置方法
を用いて上述で作られた序列で１つ宛単位サイズ
回路板上に先ず配置される。構築的な配置方法で
は、他のものよりも高い接続度を有する構成要素
が単位回路板上の予定の出発位置に配置される。
以後の各構成要素に対してはそれらを種々の場所
に配置するコストを計算し、最少コストの場所を
選ぶ。最初配置された単位サイズ構成要素は、既
に配置された構成要素と未配置構成要素との接続
を考慮して、種々の場所に構成要素を配置するコ
ストを評価するための重ね合わせ技法を用いて再
配列される。その後で配置を更に最適化するため
周知の１対式入替反復改善技法を利用する。 次にマクロサイズ構成要素を単位サイズ回路板
上の単位サイズ構成要素に対応する最適化した配
置位置に相当する素子位置において、マクロ・サ
イズ・モデル回路板上に配置する。配置された構
成要素は次に水平方向及び垂直方向にずらして重
ならないようにする。マクロ・サイズ構成要素の
最初の配置は次に、単位サイズ構成要素に対して
行なつたように重ね合わせ技法及びペアワイズ
（１対）入替反復改善技法により最適化される。 実サイズ構成要素は次に実サイズ・モデル回路
板上の、マクロ・サイズ回路板上の対応するマク
ロ・サイズ構成要素の最適配置位置に相当する素
子位置に配置される。配置された構成要素は次に
水平方向及び垂直方向にずらして重ならないよう
にする。単位モデル時及びマクロ・モデル時に取
除いた全ての小さい構成要素を再導入して配置す
る。然る後それらの構成要素を分散して不使用ス
ペースに分布するようにする。実サイズ構成要素
の最初の配置は次に、マクロサイズ構成要素に対
して行なつたように１対入替反復改善技法により
最適化される。 次に最終的な実サイズ構成要素配置データを構
成要素自動配置機に送つて、最適化されたモデル
に従つて回路板上に構成要素を配置させてもよ
い。それに代えて、最終的な配置データは、回路
板上の最適配置された構成要素間の実際の配線径
路を計算する自動配線プログラムへ送られてもよ
い。 ［実施例］ コンピユータエイデツド・デザインシステム 第２図は本発明に従う素子配置プログラムを含
んだコンピユータエイデツド・デザインシステム
の全体的概念図である。電子的システムを設計す
るためにその各素子が割当てられ又は特定化され
る。設計には例えば素子の相互接続を規定するよ
うな種々の設計上の制約がある。次レベル・パツ
ケージも又割当てられ又は特定化される。次レベ
ル・パツケージの設計にも、例えば入出力端子の
ために予定するスペースのような種々の設計上の
制約がある。第２図のコンピユータエイデツド・
デザインシステムにおいて、素子設計１１、素子
設計制約条件１２及び次レベル・パツケージ設
計・制約条件１３が全てチエツク・解析プログラ
ムへ入力され、後者が設計及び制約条件１１〜１
３が予定の設計ルールに違反せず、相互に両立す
ることを保証する。 機能的設計の存在が一旦保証されたなら、本発
明に従う素子配置プログラム１６（第１図で詳細
に示す）が次レベル・パツケージ上への最適化さ
れた素子配置を自動的に決定するために使用され
る。素子配置が最適化された後、配線プログラム
１７が次レベル・パツケージ上の最適配置された
素子間の実際の配線相互接続径路を決定する。配
線が決定された後、次レベル・パツケージ上に素
子を手で配置し且つ素子に配線するため、素子配
置データ及び配線データが用いられてもよい。そ
れに代えて、素子配置データ及び配線データをコ
ンピユータエイデツド製造システム１８へ供給さ
れてもよい。後者は素子配置プログラム１６によ
つて導出された最適配置に従つて次レベル・パツ
ケージ上に必要な素子を自動的に配置し、且つ配
線プログラム１７によつて導出された配線データ
に従つて配線回路網を自動的に作り上げる。 本発明の素子配置プログラムのあらまし 第１図は第２図中のブロツク16の詳細図であつ
て本発明に従う素子配置プログラムによつて実行
される方法のあらましを示す。前述の通り配置さ
れるべき素子を構成要素と呼ぶが、それは集積回
路及び個別的デバイスを含んでもよい。第２レベ
ル・パツケージを回路板と呼ぶ。素子配置プログ
ラム１６は各構成要素の寸法、構成要素間の入出
力相互接続配列、回路板の寸法及びその上の素子
受入れ許容位置、素子相互接続、構成要素及び回
路板に対する他の制約条件に関する入力情報（ブ
ロツク19）を受入れる。その入力情報は構成要素
及び回路板の実サイズ・モデルに対するものであ
る。実サイズ・モデルから構成要素及び回路板の
単位モデル及びマクロモデルが形成される（ブロ
ツク21）。次に構成要素がクラスタ化され且つ並
べかえられる（ブロツク22）。クラスタ化とは相
互接続度の高い構成要素を識別してそれら構成要
素のグループを形成する手順である。並べかえと
はグループ内での個々の構成要素の相対的位置を
決めることである。クラスタ化及び並べかえによ
つて、最も接続度の高い構成要素が単位サイズ回
路板上で相互に近接配置されるようになる。 次に単位サイズ構成要素は単位サイズ回路板上
に最適配置される（ブロツク23）。最適配置され
た単位サイズ構成要素及び単位サイズ回路板は同
等なマクロ・サイズ構成要素及びマクロ・サイズ
回路板と置換され、そして配置が再び最適化され
る（ブロツク24）。最後に、最適配置されたマク
ロ・サイズ構成要素及び回路板が同等の実サイズ
構成要素及び回路板と置換されて、配置が再び最
適化される（ブロツク26）。配置データが配線プ
ログラム１７（第２図）又は製造システム１８
（第２図）へ供給されて、素子配置プログラムに
よつて決定される通り回路板上に構成要素をレイ
アウトするように働らく。 本明細書の以下の部分で第１図の各ブロツクを
当業者が実施可能な程度に詳述する。 入力情報 再び第１図において、回路板及びその上に配置
されるべき構成要素に関する全ての必要情報が集
められ、そして入力情報ブロツク19によつて記憶
装置へ書込まれる。入力情報は構成要素及び回路
板の実サイズ・モデルを形成する。必要な入力情
報及びその実例を下記に示す。 入力情報の１つの部分は回路板、及びその上に
置きうる素子配置位置の記述である。第３図は回
路板２７及びその上の複数の構成要素位置を配置
できる入出力バイヤホール２８の格子を示す。入
出力バイヤホール１８は回路板上の複数の構成要
素位置を規定する。格子の寸法及びバイヤホール
２８のＸ−Ｙ位置が供給される。回路板２７上に
配置されるべき各構成要素の寸法も供給される。
格子項目及び素子寸法項目が第４図に示されたよ
うな古典的な「タイル貼合せ問題」即ち複数の異
なつた形状のタイル３１を予定の面積３２に最適
貼合わせする問題を規定する。しかし回路板上に
構成要素を配置する問題は相互接続のリスト（ネ
ツト・リストと呼ぶ）も与えられる点で、古典的
なタイル貼合せ問題よりも更に複雑である。ネツ
ト・リストは構成要素間になされるべき相互接続
を規定する。構成要素は結果の配置に基づく接続
の配線の確率が最適化されるように配置されなけ
ればならない。第５図は回路板２７、構成要素２
９及び構成要素間の相互接続条件を略示する。第
６図及び第１表はネツト・リストに貯えられる情
報を示す。

【表】

【表】 構成要素及びそれらのピンに番号が付けられ、
全てのピンからピンへの接続が構成要素出所に関
連した各構成要素上の各ピンの位置として記述さ
れる。入出力点（Ａ〜Ｋ）が回路板出所に関連し
て特定される。物理的及び電気的制約により或る
ネツトは他のネツトよりも臨界的であつて出来る
だけ短くしなければならない。この場合には設計
者は、どのネツトが最も重要であるかを、第１表
に示すように優先度番号をネツトに与えることに
より特定してもよい。もしも或るネツトが臨界的
でないと考えられるならネツト優先度０が与えら
れ、最大値まで臨界的なネツトであればあるだけ
高い値が与えられる。ネツト優先度の用法の詳細
は後述のクラスタ化および並びかえの項で説明す
る。 配置問題を更に複雑化する他の入力情報があ
る。例えば第７図を参照すると、構成要素を配置
できる格子は次レベル・パツケージの特性に起因
して制限される。或る種の構成要素は正当な電圧
供給源が与えられている場所にのみ配置できるの
で、電圧供給源の場所が特定化されなければなら
ない。第７図において複数の電圧供給地点が２種
の供給電圧（Ｏ及びＸ）で特定化されている。Ｏ
は例えば０ボルトで、Ｘは例えば５ボルトであ
る。第８図は各格子位置２８間の配線チヤネル４
４の個数及び場所に関する情報も素子配置プログ
ラムに与えられることを示す。この情報は以下で
詳述する通り結果の配置の配線可能性を解析し且
つ最適化するためネツト・リストと関連して用い
られる。第２表 配線チヤネル情報（第８図参照） チヤネルの合計＃、（Ｘ／＃）マクロ・イメージ
単位 （Ｘ＝134/16＝8.38） チヤネルの合計＃、（Ｙ／＃）マクロ・イメージ
単位 （Ｘ＝82/10＝8.2） チヤネルの合計＃、（Ｘ／＃）単位イメージ単位
（Ｘ＝134/15＝8.93） チヤネルの合計＃、（Ｙ／＃）単位イメージ単位
（Ｙ＝82/4＝20.5） 回路板２７は第９図に示すように予定数の予め
割当てられた入出力（Ｉ／Ｏ）点を含んでもよ
い。予め割当てられたＩ／Ｏ情報は、Ｉ／Ｏ点の
近傍の他の回路板への相互接続を必要とする構成
要素を配置するための配置プログラムが使用す
る。回路板２７は構成要素配置のためには利用で
きない留保領域を含んでもよい。そのような留保
領域は回路板の穴又は回路板用の機械的装着点で
あつてもよい。回路板２７はテスト・ポイントを
含んでもよい。テスト・ポイントは或る種の設計
では配置用に利用できない付加的な領域であつて
もよく、又は他の設計では入出力点として利用さ
れてもよい。最後に、設計者は素子配置プログラ
ムにより残りの構成要素を配置できるようにしつ
つ、或る種の構成要素（例えば予め配置された構
成要素）に対しては最終的配置を特定化する必要
に迫られることがある。この情報は全てブロツク
19（第１図）の入力情報の１部分として自動配置
アルゴリズムに伝えられる。この情報はコンピユ
ータ端末の対話型データ入力装置によつて与えら
れてもよく、又はデータ・ベースの形態でコンピ
ユータエイデツド・デザインシステムにより与え
られてもよい。 単位モデル及びマクロモデル形成 第１０図は構成要素及び回路板の単位モデル及
びマクロモデルを形成するステツプ（第１図のブ
ロツク21）の詳細なステツプを示す。単位モデル
及びマクロモデルは処理のこの時点で形成される
には及ばないが、むしろそれらの最適化の直前に
形成されてもよい（第１図のブロツク23，24）こ
とは当業者に明らかである。 単位及びマクロのモデル化は第１１図に略示さ
れる。この例では、特定された回路板に対して規
定された格子座標における構成要素の実サイズが
14×７（即ちＸ方向に14格子単位で、Ｙ方向に７
格子単位）、そして４×12（即ちＸ方向に４格子単
位で、Ｙ方向に12格子単位）である。単位モデル
については、これらの構成要素の両方が１×１
（即ちＸ及びＹ方向に１格子単位）である。マク
ロ・モデル化目的に対するサイズは４なる尺度係
数で夫々４×２及び１×３である。マクロモデ
ル・サイズ及び尺度係数を算出する要領は以下に
説明する。 再び第１０図を参照すると、単位及びマクロモ
デル形成の最初のステツプは尺度係数を発生する
ために構成要素サイズ情報を処理することである
（ブロツク34）。このステツプ及び後続のステツプ
で生じる処理を図示するため、構成要素及び回路
板の代表的な混合体を例示するデータを第３表に
示す。

【表】 第３表はＸ方向に67格子点を、Ｙ方向に41格子
点を有する格子上に配置されるべき構成要素の混
合物を示す。配置されるべき構成要素の数は66、
構成要素は８個の異なつたサイズのものであり、
その分布も又第３表に示した。ブロツク34（第１
０図）はＸ又はＹの何れかの方向の最大共通構成
要素サイズとなるべき尺度係数をセツトする。第
３表の例の構成要素混合物に対しては４なる尺度
係数を用いたことがわかる。もしも構成要素混合
物が２又はそれ以上の最大共通寸法を含むなら
ば、最低の値を使う。又もしも構成要素混合物の
サイズが大きくばらついているならば（例えば同
一サイズの構成要素が20％未満しかないならば）、
４なる省略尺度係数を使用する。 再び第１０図を見ると、このプログラムは次に
配置に使用できるイメージ・サイズを発生する
（ブロツク36）。もしも格子位置の横行又は縦欄の
何れも配置のために利用できないならば、配置の
ために利用する横行及び縦欄の合計数をそれに従
つて減らす。第９図に示された留保領域は単位及
びマクロ・モデル化ステツプのあいだ念頭におい
て、回路板イメージ上の適当に尺度を決めた領域
を留保し且つこの領域を配置に使わないようにす
る。 再度第１０図において、小さい構成要素は取除
かれて単位サイズ・モデルが発生される（ブロツ
ク37）。小さい構成要素は単位及びマクロ・モデ
ル化ステツプでは処理から除外される。これは配
置問題全体を単純化するためと、より大きい構成
要素の接続度に基づいて相対的配置をするための
初期最適化のあいだ重要でない配置問題を除外す
るために行なわれる。除外された構成要素は、単
位又はマクロ・モデル化が実行される前には１な
るＸ又はＹ格子寸法を有するものである。 第４表は小さい構成要素の除去及び回路板に対
する単位サイズ・モデルの計算を示す。

【表】

【表】 小さい構成要素を除外した後で（第４表におい
て＊印で示した部分を除外する）、平均の高さ及
び幅を計算した夫々4.41及び10.15格子単位にな
ることがわかつた。格子の実サイズ（67×41）構
成要素の平均サイズに基づくと、Ｘ方向に配置で
きる構成要素の数は15であること及びＹ方向に配
置できる構成要素の数は４である（最寄りの整数
に丸めた）。従つて単位イメージ・サイズは15×
４である。各構成要素の単位サイズを１×１にで
きること勿論である。もしも任意の構成要素を或
る程度回転された状態に置くように指定したとき
は、この回転を考慮に入れることにも注意された
い。ΔX値及びΔY値は、90゜または270゜回転した
構成要素の回転を考慮して変更されなければなら
ない。 次に第１０図のブロツク38においてマクロサイ
ズ・モデル情報が発生される。第５表は第４表の
例に対するマクロサイズ・モデル発生を示す。

【表】 構成要素のマクロ・サイズは、実サイズを尺度
係数で割ることにより算出し且つ最寄りの整数に
丸めることにより得られる。マクロ・サイズ・モ
デルの平均Ｘ及びＹ寸法を次に計算する。マク
ロ・サイズの合計（即ちNΔX及びNΔY）を構成
要素(N)の総数で割ることにより夫々1.13及び2.43
を得る。マクロ回路板サイズは単位サイズ寸法に
マクロ・サイズ構成要素の平均寸法を掛けて最寄
りの整数に丸めることによつて算出される。かく
てマクロ・イメージ・サイズは16×10と算出され
る。第１２図は実サイズ・モデル、マクロ・サイ
ズ・モデル、及び単位サイズ・モデルの回路板イ
メージを要約して示す。 第１０図の次のステツプは外部コネクタ位置を
単位サイズ及びマクロ・サイズに変換するステツ
プである（ブロツク39）。元の回路板の外部コネ
クタ位置（即ちＩ／Ｏ接続位置）は、イメージの
Ｘ及びＹ寸法比に基づいて回路板の単位イメージ
及びマクロ・イメージ上の相対的位置に変換され
る。若干のＩ／Ｏ位置は正当な電圧供給点におい
てマザーボードにプラグ差込みされなければなら
ないので、設計者が指定してもよい（予め指定さ
れたＩ／Ｏ位置）。Ｉ／Ｏに対する構成要素接続
は電線が発生されなければならないことを意味す
るので、この接続はモデル化配置時点で考慮に入
れなければならない。次のブロツク41において、
予め配置された構成要素の情報及び留保された領
域の情報がマクロ・サイズ回路板及び単位サイズ
回路板用に発生される。かくてもしも任意の構成
要素が予め配置されて実回路板上の予め割当てら
れた場所に保持されなければならないならば、こ
れらの場所は単位及びマクロ・モデル化回路板イ
メージ上の相対的位置に変換される。同様に任意
の留保された領域（第７図に略示されている）も
モデル化イメージ中の利用できない領域に変換さ
れる。もしも留保された領域又は予め割当てられ
た領域が１単位のモデルよりも小さいならば、こ
の留保された又は予め割当てられた領域は単位及
びマクロ・モデル化のあいだは無視され、実サイ
ズ構成要素の配置のあいだは考慮される（第１図
のブロツク26）。実サイズ配置中は留保領域が重
複しないように何れの構成要素も置かれない。 処理がブロツク42（第１０図）へと進んで個別
的で比較的小さい構成要素がネツト・リストから
取除かれる。単位及びマクロ・モデル化セツトか
ら消された構成要素（第４表、第５表）は原ネツ
ト・リストから一時的に取除かれて新たなネツ
ト・リストが発生される。もしも消されている構
成要素が１つのネツトの入出力接続に接続される
なら、消されるべき構成要素は第１のネツトの中
の接続された構成要素と置換される。同様にもし
も消されるべき構成要素に対して１つよりも多い
構成要素が接続されるなら、最大Ｉ／Ｏ接続度を
有する構成要素がＩ／Ｏネツト中の交換構成要素
として選ばれる。これは消されるべき構成要素が
Ｉ／Ｏのみに接続されたネツトに対して実行され
る。第６表は小さい構成要素を取除いて適当な修
正を施した後（第１３図）の第１表（及び第６
図）のネツト・リストを示す。

【表】 次に第１０図のブロツク43において、原格子位
置２８の間で利用できる水平及び垂直配線チヤネ
ル（配線を通すことができる径路）の数が回路板
２７の高さ及び幅について合計される。第８図
（及び第１表）は参照番号３５で代表的な配線径
路を示し、参照番号４４で代表的な配線チヤネル
を示す。マクロ及び単位チヤネル供給情報を発生
するために、イメージの単位Ｘ寸法及び単位Ｙ寸
法当りの水平及び垂直配線チヤネルの数が、Ｘ及
びＹのチヤネルの合計数を各方向におけるイメー
ジ単位の数（マクロ及び単位サイズ）で割ること
により算出される。 これで本発明の単位及びマクロ・モデル形成部
分の説明を終る（第１図、ブロツク21）。単位サ
イズについては、46個の構成要素を配置するため
に60個の場所が利用可能である（第４表及び第１
２図参照）。マクロ・モデル区域については構成
要素が必要とする領域は140個で利用可能な領域
は160個である。規定された格子点の総数は160個
である。かくて利用可能な領域は単位モデル化に
必要な領域数よりも約10％多く、しかも配置され
るべき構成要素に対して実際に必要とされる領域
に基づいたマクロ・モデル化に対して必要とされ
るよりも約15％多い。この余分な領域は以下に述
べるように適合問題の助けとなる。 一旦単位及びマクロ・モデルが形成されると、
通常の配置最適化技法を使つて、単位回路板上に
単位構成要素を最適配置し、その最適配置された
単位構成要素を対応するマクロ構成要素と置換
し、マクロ回路板上にマクロ構成要素を最適配置
し、最適配置されたマクロ構成要素を対応する実
際の構成要素と置換し、そして実際の構成要素を
実際の回路板上に最適配置できることは当業者に
明らかである。以下に示す配置最適化技法は３径
路技法と共に良好な配置を与える。 クラスタ化及び並べかえ 第１４図は回路板上に配置されるべき構成要素
をクラスタ化し且つ並べかえるステツプ（第１図
のブロツク22）の詳細を示す。回路板上に対応す
る単位、マクロ、及び実サイズ構成要素を配置す
る（第１図のブロツク23〜26）のに先立つて、構
成要素間の相互接続が解析されて相互接続度の高
い構成要素のグループが形成される。接続度マト
リツクスから種子が形成されて、構成要素のクラ
スタ又はグループが形成される。これらのクラス
タ又はグループは接続度に基づいて序列づけされ
る。次に全ての構成要素はその既に取上げられた
グループに対する接続度に基づいてグループ内で
並べかえられる。この並べかえられた順序は単位
サイズ・イメージ上に単位サイズ構成要素を配置
するのに使用される。接続度の高い構成要素をク
ラスタ化し且つ並べかえるプロセスは、これらの
構成要素が一緒に配置されたときそれらの信号ネ
ツトを接続するのに必要な配線の量を減少させ
る。しかし配置順序は他の周知のクラスタ化技法
により発生することができ、或はランダムに行な
つてもよいことは当業者に明らかである。 第１４図はクラスタ化及び並びかえを実行する
ステツプを示す。任意の数でもよいが図示の都合
上、12個の構成要素が回路板上に配置されなけれ
ばならないものと仮定する。何れの計算も下記の
ように行なわれる。第６表（及び第１３図）に例
示されたようなネツト・リストを形成して12個の
構成要素間の電気的接続を示す。クラスタ化及び
並べかえは、ネツト・リストを解析し且つ構成要
素に対して接続度マトリツクスを発生することに
よつて開始される（ブロツク46）。 第７表は12個の構成要素に対する接続度マトリ
ツクスの例を示す。

【表】 マトリツクス中の各内容は下記の式(1)及び(2)か
ら得られる。 C_ij＝_k 〓¹ （1.5／（ｎ−１）＋1.0 ＊NPR／（ｎ−１）） (1) C_ij＝C_ij＋0.5^*（ｋ／m_i＋ｋ／m_j） ＋0.5^*（Ioi／m_i＋Ioj／m_j） C_ij：構成要素ｉ及びｊ間の接続度値その接続
度値はｉ及びｊが１から12まで変化したときの第
７表に示す接続マトリツクスの内容を形成する。 Ｋ：構成要素ｉ及びｊを接続するネツトの数。
この値はネツト・リストを走査すること、及びど
のネツト番号が構成要素ｉ及びｊの両方からのピ
ンを含むかを考慮することによつて得られる。 ｎ：全ネツトＫ中の接続点の数（例えば第１３
図の構成に対する第６表において、ネツト１は３
つの接続点を持ち、ネツト２は唯２つの接続点を
持つ）。この数は計算されているネツトと同じネ
ツト数を有するネツト・リスト中の内容の数を計
数することによつて得られる。 m_i、m_j：構成要素ｉ（又はｊ）が出現するネツ
トの総数（例えば第１３図及び第６表において、
構成要素３は１つのネツトのみに出現し、構成要
素１は３つのネツトに出現する）。この値はネツ
ト・リストを走査し、そして構成要素ｉ（又はｊ）
が接続点を有する異なつたネツト数の計数値を保
持することにより得られる。 I_pi：構成要素ｉに接続されるＩ／Ｏの数（例え
ば第１３図及び第６表において、構成要素１は
Ｉ／Ｏを全く持たない）。 I_pj：構成要素ｊに接続されるＩ／Ｏの数（例え
ば第１３図及び第６表において、構成要素２には
２つのＩ／Ｏが接続される）。 NPR：一緒に配置されるべき構成要素に対す
る臨界的なネツトのユーザー（利用者）によつて
割当てられたネツト優先度フラグ（第１３図及び
第６表のネツトに対する優先度リストは、最高で
ある優先度２と優先度なしの０とを含む）。 倍率値1.5、1.0、及び0.5が実験的に決定される
が、これらの値が最善の実験結果を与えた。しか
し異なつた値でも比較的良い結果を与えることは
当業者に明らかである。 接続マトリツクス中の各内容に対する接続度値
C_ij（第７表）は前記の式(1)によつて計算される。
式(1)は構成要素ｉ及びｊ間の全ての共通ネツトの
重みづけされた和を表わすことは当業者に明らか
である。もしも構成要素ｉ及びｊ間に共通ネツト
が存在しないならば、即ち式(1)中のC_ijの値が０
であるならば、式(2)は、評価されずC_ijはマトリ
ツクス内容に対して０となつて構成要素が不接続
であることを表わす。他方もしも、式(1)で計算さ
れたC_ijが０でなければ、式(2)の計算が式(1)で計
算された接続度値に対して加えられる。式(1)にお
いて構成要素ｉ及びｊ間の共通ネツトの数が評価
された。式(2)は構成要素ｉ及びｊ間の総接続度を
得るために、各構成要素に対するＩ／Ｏの数及び
各構成要素に関連した総ネツトとの比を加味す
る。この計算はネツト・リスト中の全ての構成要
素に対して実行され、第７表に示すような接続度
マトリツクスが作られる。 第１４図に戻つて、一旦接続度マトリツクスが
作られると（ブロツク46）、接続度値に基づいて
分類が行なわれる（ブロツク47）。分類は以下の
ように行なわれる。接続度マトリツクス（第７
表）の各横行を調べることにより、最大接続度値
が得られる。第７表の「最大接続度値」欄（58）
は12個の構成要素サンプルに対する調べの結果を
示す。最大接続度値に対する関連構成要素の個数
が第７表の「最多接続構成要素」欄（59）として
発生される。最後に、各横行にまたがる全ての接
続度値の和が第７表の「合計値」欄（61）に示さ
れたように発生される。次に最大接続度値（58）
は大きい接続度値の順に分類され、第８表に示す
表を発生する。

【表】 第８表は各構成要素に対する最大接続度値及び
それに対する高接続度の構成要素をリストしてい
る。分類された値（66）は大きい順に最大接続度
値（58）を分類することによつて得られる。C_ij
は常にC_ijに等しいので（２つの構成要素ｉ及び
ｊは常に相互に相等しく接続されるので）、分類
された値の欄に同じ接続度値が２度現われること
がある。第８表において構成要素ｉ及びｊのリス
トは構成要素の数ｉ及びｊを示し、そのリストか
らその横列に対する最大接続度値（58）が得られ
る。 再び第１４図において、分類が終つた後に（ブ
ロツク47）、構成要素クラスタのための種子が発
生される（ブロツク48）。種子は下記のように相
互に高度に接続された２つ以上の要成要素のグル
ープである。他の要成要素に対する接続度の低い
残りの構成要素がブロツク48で発生された種子と
併合され、それに対して最も高度に接続されて
（ブロツク49）構成要素のグループを形成する。
グループ間の接続度が発生され、最高接続度から
最低接続度へ向うこれらのグループの序列が作ら
れる（ブロツク51）。最後に各グループ内の個々
の構成要素が接続度に基づいて順序づけされる
（ブロツク52）。 かくて例えば分類された接続度値（第８表）を
解析すると、構成要素１及び２が高度に相互接続
され、そしてもしもそれらが一緒に配置されるな
ら、それらを接続するのに必要な配線の量は最少
となることを示す。かくして分類された値（66）
から２つの最も高度に接続される構成要素（構成
要素１及び２）が第１の種子として取出される。
分類されたリスト中の次の構成要素は８である。
その接続度マトリツクス横列（第７表）の最も高
い値を調べて最も高度に接続される構成要素を見
つける。この解析により構成要素８は構成要素５
に対して最も高度に接続されることがわかるの
で、構成要素の横列を同様に調べてその最高接続
度値を見つける。構成要素５は構成要素１及び２
と最も高度に相互接続されるので、新たな種子が
構成要素５及び８に対して形成される。第８表中
の次のものは構成要素７である。第１の種子（構
成要素１，２）及び第２の種子（構成要素５，
８）の構成要素に対するその接続度が解析され
る。構成要素７に対する接続度横列を調べてその
最高接続度は構成要素５に対するものであること
を見つける。従つて構成要素７は構成要素５を含
んだ種子と併合されなければならない。かくて第
２の種子は構成要素５，７，８より成る。 分類されたリストから次の候補を拾い上げ、そ
れを現存の種子と併合するか又は新たな種子を作
るかの何れかの上述のプロセスは、（66）におけ
る分類された値が2.8に達するまで続けられる。
この値は式(1)及び(2)で使用される特定の定数であ
り、もしも異なつた定数が使用されるなら変更可
能である。第７表の例で発生された種子は第９表
の（62）で示される。

【表】 接続度値の上述のカツトオフ点の後ではもはや
種子は発生されない。カツトオフ点は、残りの構
成要素が任意の１つの構成要素に対して余り高度
に相互接続されないことを指示する。かくて残り
の構成要素は現存する種子と併合可能である。も
しも全ての構成要素が非常に軽度にしか相互接続
されないという理由で種子が形成されないなら
ば、グループの順序づけのための下記の方法を用
いて全ての構成要素を順序づけし、構成要素はグ
ループ内の構成要素の順序づけの処理を介するこ
となく、その順序で配置される。 再度第１４図において、残りの構成要素はグル
ープを形成するため種子と併合される（ブロツク
49）。前のステツプ（ブロツク48）において種子
が発生された。今や残りの各構成要素に対してそ
れらの間の接続度値の和が計算される。例えば構
成要素４及び種子Ａの構成要素は2.5及び2.5なる
接続度値C₁₄（又はC₄₁）及びC₂₄（又はC₄₂）を持
つ。これらの値の和は5.0であり、種子Ａに対す
る構成要素４の相互接続性を表わす。同様に種子
Ｂ、Ｃ、Ｄに対する構成要素４の相互接続度値が
計算される。次に構成要素４が最も高度に相互接
続されるグループ（この例では種子Ａ）に併合さ
れる。このプロセスは他の構成要素に対する接続
度の順序で全ての残りの構成要素［第８表の
（66）］に対して実行される。もしも接続度値が同
じなら、グループ内の最少の構成要素を拾い上げ
るような選択がなされる。もしもそれでも同じで
あるなら、任意の選択がなされる。第９表の
（63）で示すようにグループＡ、Ｂ、Ｃ、Ｄは種
子Ａ、Ｂ、Ｃ、Ｄから形成されており、各グルー
プ中の構成要素のリストが発生される。第１５図
はグループ及び構成要素を示す。 再び第１４図において、グループの接続度が発
生され、接続度に基づいてグループの順序が発生
される（ブロツク51）。第10表クラスタ化段階で
形成されたグループに対する接続度マトリツクス
を示す。

【表】 ネツト接続グループＡ、Ｂ、Ｃ、Ｄが第１６図
及び第12表に示される。 第11表（第１６図参照） １ 接続度に基づいたグループの順序 グループ順序 Ｂ、Ｄ、Ａ、Ｃ←77 ２ グループの順序に基づいた構成要素の順序 構成要素順序 Ｂ Ｄ Ａ Ｃ ８，５，７，３ 11，12 １，２，４ 10，9.6 ３ グループ内の構成要素の並べかえ 新たな順序 Ｂ Ｄ Ａ ８，５，７，３ 12，11 ４，２，１ Ｃ ６，９，10←79 計算は構成要素対構成要素接続度マトリツクス
のために行なつた計算と同じであるが、このマト
リツクスの計算はグループ間の相互接続度に対し
て行なわれる点が相異する。その計算値は第12表
に示すように分類される。第10表ではグループＢ
及びＤは最高の合計値を有するグループＢと相互
に対する最高の相互接続度を持つように示された
ので、先ずＢが拾い上げられた後Ｄを拾い上げる
（第12表参照）。

【表】 次に既に拾い上げられたグループに対する残り
のグループの接続度を、既に選択されたグループ
に相当する横列の値を合計することにより計算す
る。第１６図及び第12表の例では、残りのグルー
プＡ及びＣの値は、横列Ａ、縦欄Ｂ＋横列Ａ、縦
欄Ｄの値を加え合わせることによつて算出される
（3.39＋1.73＝5.12）。同様にＣに対しては横列Ｃ、
縦欄＋横列Ｃ、縦欄Ｄの値で算出される（3.39＋
1.73＝5.12）。これらの値は等しいので任意に行
なつたＡの選択は第１６図及び第11表（77）で示
すグループの最終的な順序を形成する。 グループの順序が決つた後で各グループ内の構
成要素を接続度に基づいて並べかえる（第１４図
のブロツク52）。グループの順序づけについて概
説されたような合計アルゴリズムが今やグループ
内の個々の構成要素に適用されて第１６図及び第
11表の（79）で示す最終順序を作る。第１グルー
プであるグループＢに対しては、種子化及び併合
プロセスの間はそれが発生されたままの順序に保
たれる。何故ならば最も高度に相互接続される構
成要素が原併合プロセスにおいて拾い上げられた
からである。次に、既に拾い上げられた構成要素
に対する最も高度に相互接続される構成要素が決
定される。グループＤ及びグループＢ中の構成要
素間の接続度は、構成要素１２がグループＢ中の
構成要素に対して高度に接続されることと、構成
要素１１よりも先に配置されなければならないこ
とを示す。かくてグループ内の構成要素の並べか
えは、既に選ばれたものに対する夫々の接続度に
基づいて行なわれる。 構成要素の順序づけは種子及びクラスタ又はグ
ループを作らないでも実施可能であることは当業
者に明らかである。異なつたクラスタ化技法又は
順序づけ技法を用いて上述の順序を発生すること
もできる。異なつたクラスタ化及び順序づけ技法
は前述のDesign Automation of Digital
Systems Theory And Techniquesの第５章に
示されている。単位イメージ上に配置するため下
記のようにランダム順序を用いることさえでき
る。品質及び最適化するための所要時間は採用し
た順序づけ及びクラスタ化技法によつて変化する
が、下記にあらまし述べるステツプを最適化配置
に後続してもよい。今やクラスタ化及び並べかえ
のステツプが達成されたので、クラスタ化され且
つ並べかえられた構成要素が単位イメージ上に配
置される（第１図の２３）。 配置最適化：単位サイズ 第１７図を参照して、単位サイズ回路板上へ単
位サイズ構成要素を配置する詳細なステツプを説
明する。第１７図は単位サイズ配置及び最適化の
処理ステツプを要約したものである。単位サイズ
配置及び最適化は一般に４つの主要ステツプ、即
ち初期配置を発生するステツプ（ブロツク81）、
重ね合わせることにより配置を改善するステツプ
（ブロツク82）、繰返し改善ステツプ（ブロツク
83）、及びマクロモデル初期配置のための場所を
発生するステツプ（ブロツク84）を含む。これら
の各ステツプのプロセスを以下で詳述する。 次に第１８図を参照して初期配置の詳細なステ
ツプを説明する。プロセスは単位サイズ・モデル
で始まる。その簡単な例が第４表に示された。単
位サイズ配置の最適化に含まれるプロセスをわか
りやすく説明するため、第７表乃至第12表の12個
の構成要素の例についての単位サイズ・モデルを
採用する。第13表は第７表乃至第12表の12個の構
成要素に対する単位及びマクロ・サイズ・モデル
を示す。構成要素の単位サイズ及びマクロモデ
ル・サイズと単位及びマクロイメージ・サイズと
が上記の「単位及びマクロモデル形成」の部で説
明されたように計算される。 再び第１８図を参照すると、最初のステツプは
単位サイズ回路板のＸ及びＹ寸法を２倍にするこ
と、及び２倍のサイズの単位回路板上にＩ／Ｏ場
所を記入することである（ブロツク86）。単位サ
イズ回路板の２倍化は、その相互接続度に基づく
初期配置のあいだ相互接続された構成要素を自由
に配置できるようにするために行なわれる。これ
は相互に対して正しい位置関係で全ての構成要素
の配置を作るが、歪んだ実際の単位イメージと違
つて来る可能性がある。この初期配置プロセスは
２倍サイズ化した単位イメージの真中で開始し、
単位イメージ上の出発点として「種子」場所を決
定する必要がないようにする。２倍サイズ化した
単位サイズ回路板及びその上に記入されたＩ／Ｏ
場所83は第13表の12構成要素に対する第１９図に
示す。

【表】

【表】 単位イメージに対するＩ／Ｏ場所を第２０図に
示す。単位イメージ９２のＩ／Ｏ場所は、第１９
図に示すように単位イメージの横列及び縦欄の数
を1/2にすることにより２倍イメージの中央に向
つてシフトして２倍の単位サイズ回路板上に記入
される。実例において単位サイズ・イメージは３
単位Ｘ及び６単位Ｙなので、各Ｉ／Ｏは３×1/2
＝1.5だけＸ方向に、そして６×1/2＝３だけＹ方
向にシフトされる。Ｉ／Ｏの記入は、下記のよう
に構成要素を配置するための重みづけ距離計算中
にＩ／Ｏに対する接続が考慮されるので実行され
る。 再び第１８図を参照して構築的配置技法により
構成要素を配置する次ステツプ（ブロツク87）を
説明する。構成要素を配置する順序はクラスタ化
及び順序づけのあいだに先に発生された（第１６
図及び第11表ブロツク79）。もしも原イメージ上
に何か予め配置された構成要素があるならば、そ
れに相当する場所が単位イメージ上に発生され、
次にＩ／Ｏ場所のために前に述べた要領で場所が
シフトされる。もしも単位イメージに変換され終
えたブロツク化された領域があるならば、それも
又２倍イメージ回路板上の場所に変換されて、そ
れらの場所が構成要素の配置のために利用されな
いようにフラグ（目印し）される。もしも何か予
め割当てられた構成要素があるならば、次の未配
置の候補構成要素を配置するためのコストが評価
され、そしてこの候補構成要素は以下に詳述され
るように最少コストで特定場所に配置される。 順序づけられた構成要素はクラスタ化及び並べ
かえプロセスで発生された順序で２倍の単位イメ
ージ上に１つ宛配置される。最初のグループ中の
最も高度に接続される構成要素、即ち第１６図
（第11表）の例ではグループＢの第８番目の構成
要素が２倍イメージの中央に配置される（第２１
図及び第14表参照）。

【表】 １つの構成要素によつて占められた場所は他の
構成要素を配置するために使用することができな
い。配置されるべき次の構成要素は同じグループ
Ｂからの５番目のものである。 降補構成要素に対する重力の零中心（重心）
が、既に配置された構成要素に対するその接続度
に基づいて計算される。重心の詳細な計算方法が
式(10)及び(11)と第２７図及び第16表と関連して下記
に説明される。使用可能な場所のリストは、最少
20場所が得られるまで、又はもはやそれ以上の場
所が得られなくなるまで、１度に１単位宛−Ｘ、
−Ｙ、＋Ｘ、＋Ｙ方向に重心から拡張することによ
つて作られる。使用可能な場所のこのリストを候
補場所と呼ぶ。 構成要素＃５を配置するコストが下記の式(3)及
び(4)を用いて候補場所のリストから計算される。 コスト＝_p 〓 〓¹ ［Hwt×ABS（Xi−Xc）＋Vwt×ABS（Yi−Yc）］／各ネ
ツト中の全ての配置構成 要素及びＩ／Ｏに対する接続
の数(3) コスト＝コスト＋場所コスト (4) Ｐ＝既に配置された構成要素又は既に割当てられ
たＩ／Ｏに対する接続を含む侯補構成要素と関
連した全てのネツト。 Xi＝もしも候補構成要素が予め割当てられなか
つたＩ／Ｏに対する接続を有するならば、候補
場所に対する既に配置された構成要素又は予め
割当てられたＩ／Ｏ又は最も近いＩ／Ｏの縦欄
場所。 Yi＝もしも候補構成要素が予め割当てられなか
つたＩ／Ｏに対する接続を有するならば、候補
場所に対する既に配置された構成要素又はあら
かじめ割当てられたＩ／Ｏ又は最も近いＩ／Ｏ
の横列場所。 Xc＝コストが評価されようとしている候補構成
要素の配置のための候補縦欄場所。 Yc＝コストが評価されようとしている候補構成
要素の配置のための候補横列場所。 Hwt、Vwt＝バイヤ（貫通孔）長に対する夫々
水平及び垂直重み。これらは初期配置がなされ
た後に決定される。その説明は初期配置ステツ
プの説明の後の配線可能性解析のときに行な
う。それらは両方共初期プロセスでは1.0にセ
ツトされるので、ここで行なうコストの計算に
は無関係である。それらは初期配置の後一旦チ
ヤネル需要利用度がわかると、水平及び垂直方
向にバイヤホール配置をするために使用され
る。 場所コスト＝場所の占有に関連したコスト。これ
も初期配置後に決定されるものであつて、配線
可能性解析の後で説明される。それはこの初期
配置プロセスにおいて0.0にセツトされるので、
最初のプロセスに対するコストの計算に影響を
与えない。場所を占有するコストは、その場所
が構成要素によつて占有されるべきでないこと
を望むとき合計コストに加算される。 留保された領域又は予め配置された構成要素に
よつて占有された領域はどれも使用できない場所
であつて、候補場所リスト中にあつてはなならな
い。最少コストの場所が、配置されるべき構成要
素に対する候補場所として拾い上げられる。もし
もコストの等しい場所があるならば何れを勝手に
選んでもよい。候補構成要素＃５のために選んだ
場所が第２１図（及び第14表）に示される。 １度に１つの構成要素を配置する上述のプロセ
スはクラスタ化及び並びかえプロセスで発生され
た順序で行なわれる。全ての構成要素がこの要領
で処理され、それらの全てに対する場所が発生さ
れる。この方法は推定（コンストラクテイブ）配
置として知られており、前述のDesign Auto−
mation of Digital Systems−Theory and
TechniquesのVol.5等に表示されている。このプ
ロセスによつて発生された初期配置が第２１図及
び第14表に示されている。第２１図を参照する
と、その配置は所望の６×３単位イメージとは異
なつた形を取ることがわかる。もしも構成要素８
が単位イメージの種子場所に配置されたならば、
この構築的プロセスを介して発生された解は一般
的に低品質のものとなろう。単位回路板の２倍化
によりこの欠点が除去され、その接続度に従つて
構成要素を配置できるようにする。 再び第１８図のブロツク87において、２倍の単
位サイズ回路板上に構成要素を配置した後、空の
横列及び縦欄が除去されて配置は左上角へシフト
される（ブロツク88）。イメージの左角からの空
の縦欄の合計数を決定する。第２１図及び第14表
に示す例では４つの縦欄が参照番号98で示すよう
に空である。各構成要素の場所はその配置に基づ
いて存続する。各場所はそれと関連した横列及び
縦欄を有する。新たな場所は下記の式に従つて発
生される。 新縦欄＝旧縦欄−空縦欄 (5) 新横列＝旧横列−空横列 (6) 空横列及び空縦欄は左上角からの数であり、こ
れらの横列及び縦欄における場所には全く構成要
素が配置されない。旧横列及び旧縦欄は移動前の
構成要素場所の横列及び縦欄を指し新横列及び新
縦欄は移動後の場所を指す。 かくて第２１図及び第14表の例では、全ての構
成要素場所を夫々のＸ（縦欄）値から４を減算す
ることにより左へ４縦欄だけシフトする。もしも
左上角から全く空の横列があるならば、空横列の
数を各構成要素場所のＹ（横列）値から減算する。
未シフト構成要素及びそれらの場所を第２１図に
示し、シフト後の相当する配置を第２２図に示
す。このステツプは、単位サイズ・プロセスの最
終目的が単位イメージ上に最適配置を発生するも
のであるという理由で実行され、左上角からの領
域６×３がこの例の単位イメージを表わす。 空の横列及び縦欄が除去された後に（第１８図
のブロツク88，89）、この配置に対する水平方向
及び垂直方向のチヤネル交差及び合計チヤネル交
差の利用度が評価される（ブロツク89）。このス
テツプも配線可能度評価と呼ばれる。 チヤネル供給量は配線のために利用可能なトラ
ツクの数である。第８図及び第２表に示され且つ
以前の単位モデル及びマクロモデルのためのデー
タ処理で説明された入力例では、考察中のイメー
ジの各格子点に対する配線に利用できる水平及び
垂直のトラツクの数が利用できる。各横列又は各
縦欄を横切る利用可能なトラツクの総数は、各横
列を水平方向に横切る利用可能トラツクの数及び
各縦欄を垂直方向に横切る利用可能トラツクの数
を加え合わせることによつて得られる。第２３図
の１０２及び１０３を参照されたい。第２３図に
示された例は図示の目的でサイズを小さくして示
す。図中＝印は合計40個の利用可能な水平交差
を、‖印は合計36個の利用可能な垂直交差を夫々
示す。 第２３図に示すように水平方向の合計チヤネル
供給量（即ち配線のために利用できるトラツク）
は各横列で利用できるトラツクの数（前述で計算
された）を加え合わせることによつて得られる。
同様に垂直方向の合計チヤネル供給量は各縦欄の
トラツク数（前述で計算された）を加え合わせる
ことによつて得られる。 ネツト・リスト（第１３図及び第６表）は構成
要素間の接続を規定する。今や全ての構成要素が
配置されたので、それらを電線で接続するのに必
要な径路を見積ることができる。各構成要素はそ
れが占有する場所の横列及び縦欄を有する。径路
はイメージ上の各ネツトに対して発生される。こ
れらの径路が通らなければならないルートは一般
的に技術上の制約によつて決まる。或る種の技術
ではステーナー・トリーを使うことができ、或る
ものは最少スパン・トリーを必要とし、又別のも
のはシンク型のトリーの源を必要とする。これら
のトリーは製造準備中に使用される一般的規則及
びプロセスに依存する。これらのトリーは前述の
Digital Systems−Theory and Techniquesの
Vol.5に開示されている。 最少スパン・トリーの例を示す。２点間のマン
ハツタン距離は下記のように計算される。 距離＝ABS（X₁−X₂）＋ABS（Y₁−Y₂） (7) 但しX₁、Y₁は構成要素１の場所の縦欄及び横
列であり、X₂、Y₂は構成要素２の場所の縦欄及
び横列であり、ABSは絶対値関数である。 ネツトに接続される構成要素の横列及び縦欄場
所はリストの形で与えられる。これらの各点の横
列及び縦欄座標が合計される。横列及び縦欄の座
標の最低の和を有する構成要素が出発点として選
ばれる。マンハツタン距離は式(7)を用いてリスト
中のこの点から全ての他の点へと計算され、選ば
れる次の接続点は出発点から最短のマツハツタン
距離を有する接続点である。長さの総合計は計算
された各マンハツタン距離を加え合わせることに
よつて維持される。リストの残り部分はネツト中
の全ての点を接続する最少スパン距離を作るため
に処理される。各接続毎にＸ及びＹ方向に必要と
される単位の数も又、各接続毎に計算されたマン
ハツタン距離に基づいて知ることができる。上述
の処理の例が第２４図に示される。上記のステツ
プは全ての構成要素を接続するネツトに対して行
なわれる。これらの径路は、配置の品質を評価す
るための、及び以下に概説する残りのステツプを
導くための、仮の径路に過ぎない。 第２４図は最少スパン・トリーのための幾つか
の接続を示す。構成要素Ｘ及びＹは第２４図中の
１０４で示す径路で接続される。この径路は縦欄
１、横列１で交差する１単位の水平チヤネル需要
を必要とする（第２５図の１０６）。それは更に
縦欄２、横列１で交差する１単位の垂直チヤネル
需要を必要とする（第２５図の１０７，１０８）。
これは全ての構成要素に接続する全てのネツトに
対してなされる。径路Ｃ、Ｒ、Ｄ、Ｅ；Ｆ、Ｇ；
Ａ、Ｂ、等の別の接続が第２４図に示される。こ
れらの径路に対応するチヤネル需要が第２５図に
示される。第２５図には合計９個の利用可能水平
交差と、合計10個の利用可能垂直交差を含む。 第２４図に示されたような接続トリーを用い
て、なされる全ての接続に対する各格子点境界の
水平及び垂直交差が発生される（第２５図の１０
６）。各横列の全ての交差１０９及び縦欄の全て
の交差１１１の合計が各横列及び縦欄にまたがる
値を加え合合わせることによつて算出される。全
ての水平交差及び垂直交差の合計も算出される。
利用可能な水平及び垂直交差の合計値が夫々チヤ
ネルの合計利用可能供給量に基づいて合計水平及
び垂直チヤネル交差利用度を算出するのに使用さ
れる。それはチヤネルの需要量／供給量の比率を
発生し且つ水平及び垂直方向における利用度のパ
ーセンテージを得るため100を乗じることにより
算出される。第２３図乃至第２５図の例の合計水
平交差利用度は全ての水平交差（２＋０＋３＋４
＋０）＝９を利用可能な合計水平交差で割算する
ことによつて算出される。（即ち9/40＝0.23）。同
様に合計垂直交差利用度が計算される（10/36＝
0.288）。 合計水平及び垂直チヤネル交差利用度はHwt
及びVwt（バイヤホール長のための水平及び垂直
重み）を計算するために使用される。Hwt及び
Vwtは更に以下述べるように配置を最適化する
ために使用される。 もしも水平利用度が比較的高いならば式(8)を使
用する。もしも垂直利用度が比較的高いならば式
(9)を使用する。もしも水平及び垂直利用度が相等
しいならばHwt及びVwtは両方共再び1.0にセツ
トされる Hwt＝Hwt＋Rmultp×ABS （利用度の差） Vwt＝1.0 (8) Hwt＝Hwt＋Rmultp×ABS （利用度の差） Vwt＝1.0 (9) 式中Rmultpは実験的に0.02にセツトされた。
その値は0.01〜0.3の範囲なら他の値でも良好な
配置結果を得ることができる。Hwt及びVwtは、
以下に述べるように重なり改善プロセス及び繰返
しプロセスのあいだ水平及び垂直方向にバイヤホ
ールを配置するためのコスト関数［式(3)］におい
て使用する。 所望の単位イメージの周辺の場所（第２２図の
９９，１０１）は比較的高いコストを割当てる。
５単位の追加コストが単位イメージの境界の外側
及び隣接した横列および縦欄場所に対して付加さ
れる。単位イメージの境界の外側の場所に対する
コストは単位境界からの場所のマンハツタン距離
に等しい量だけ増加される。この追加コストが式
(4)に加えられる。単位境界内のすべての場所の
Loccost（場所コスト）は0.0である。これらのコ
スト値は以下で述べるように重なり及び繰返し改
善ステツプで使用される。 再び第１７図において、単位サイズに対する初
期配置が完了すると（ブロツク81）、重なり改善
のステツプが実行される（ブロツク82）。このス
テツプは構築的配置プロセス中は（ブロツク81）
各構成要素が１時に１場所に割当てられるという
理由で実行される。かくて構成要素のコストは、
既に配置された構成要素に対する接続のみを考慮
して算出される。構成要素接続のうちの半分以上
が非配置構成要素へのものであることがあり、そ
の場所それらは勘定に入れない。重ねステツプは
この欠点に打勝つ。配置が既に発生され終えてい
るので、前に発生された重みづけ係数（即ち
Hwt及びVwt）を使つて、配置を偏移しかくて
よりよい解を得るためにコスト算式(3)の計算を行
なうことができる。 重ねステツプは第２２図で例示したような初期
配置ステツプ（ブロツク81）で発生された配置で
出発する。第２６図の１１６は初期配置を示し、
重ねステツプで発生された改善済み配置は１１７
で示す。重ねアルゴリズムを以下に示す。 他のイメージ（第２６図１１７）は同じ寸法で
初期配置イメージ（第２６図１１６）の上に置く
ものと仮定した。初めからイメージ上に構成要素
が配置されることはない。重ねステツプはクラス
タ化及び並べかえ中に発生された構成要素の順序
リストから順に候補を拾い出すこと、拾い出され
た構成要素の重心を見積ること、ウインドウ中の
場所のリストを作ること、式(3)及び(4)に基づいて
これらの場所に構成要素を配置するコストを計算
すること、そして最少コストを有する場所を拾い
出すことを含む。詳細な例を第２７図に示す。 第２７図においてネツト１（119）は構成要素
Ａ、Ｂ、Ｃ、Ｙを接続し、ネツト２（121）は構
成要素Ｄ、Ｅ、Ｙを接続する。ネツトにより接続
される他の構成要素に対する各構成要素の重心１
１３の計算がなされる。何故ならばもしも構成要
素がその重心の近くに配置されるならばその配置
は最適化するからである。第１３図及び第６表に
示されたネツト・リストは候補構成要素に接続さ
れた全てのネツト、及び各ネツト内の全ての構成
要素を識別するために使用する。この情報を知つ
たとき重心が２つのステツプで計算される。 ステツプ１：下記の式を用いて候補構成要素に
対する接続を有する各ネツトの重心を計算する： CG_X＝（X₁＋X₂＋…Xn）／ｎ CG_Y＝（Y₁＋Y₂＋…Yn）／ｎ (10) 但し、 CC_X＝ネツトに対する重心の横列座標 CG_Y＝ネツトに対する重心の縦欄座標 Xi＝候補構成要素に接続されたｉ番目の構成
要素の横列座標 Yi＝候補構成要素に接続されたｉ番目の構成
要素の縦欄座標 ｎ＝ネツト中の接続の数 ステツプ２：下記の式を用いて候補構成要素に
対する重心を計算する： ZCG_X＝［CG_X(1)＋CG_X(2) ＋…CG_X（ｍ）］／ｍ ZCG_Y＝［CG_Y(1)＋CG_Y(2) ＋…CG（ｍ）］／ｍ (11) 但し、 ZCG_X＝重心の横列座標 ZCG_Y＝重心の縦欄座標 ｍ＝候補構成要素が出現するネツトの数 重心１１３は第２７図に示すように構成要素Ｙ
に対して計算される。今構成要素Ｙと構成要素
Ａ、Ｂ、Ｃとを接続するネツト１（１１９）を考
える。構成要素Ｙと構成要素Ｄ及びＥとを接続す
るネツト２（１２１）を考える。構成要素Ａ、
Ｂ、Ｃを結ぶ重心１１４は構成要素Ａ、Ｂ、Ｃの
横列及び縦欄座標を合計して３で割ることにより
算出できる。同様にネツト２の重心１２２も計算
される。今重心を計算するためにネツト１及びネ
ツト２の重心の横列及び縦欄座標を合算して２で
割る（２つのネツトが関係するから）。重心から
のウインドウ即ち矩形領域（５×５）内の場所を
目標場所として選び、その目標場所に候補構成要
素を配置するコストを計算する。もしもウインド
ウ内には利用できる場所がないならば、ウインド
ウが１時に１単位だけ、−Ｘ、−Ｙ、＋Ｘ、＋Ｙ方向
に拡大される。その拡大は少なくとも10場所が利
用できるようになるまで又は全ての場所が調べら
れるまで行なわれる。 12構成要素の問題（第２６図１１６）に対して
は、リスト順の最初の構成要素（即ち構成要素
８）が候補として拾い出される。その重心が計算
され、イメージ１１７を重ねる目標場所にそれを
配置するコストが式(3)を用いて計算される。前に
計算されたHwt及びVwtの値（第１８図、ブロ
ツク91）が配置を偏移するために使用される。前
に割当てられた場所を占有するのに関連したコス
トを加算するために式(4)を計算する。最少コスト
を有する場所が拾い出され、構成要素がその場所
に割当てられる。最少コスト場所と関連したコス
トの等しいものがあつた場合には、任意に選んで
よい。構成要素８に対する結果が第２６図の１１
８で示される。 ここでリストから次の構成要素（即ち構成要素
５）が拾い出される。その重心は前述のように計
算される。構成要素８に対する接続のため、重ね
ステツプ中それに割当てられる新たな場所を使用
する。再び構成要素５を配置するためのコストが
式(3)及び(4)を使つて計算される。重ねイメージ上
に既に配置されている構成要素に対しては、コス
ト計算中新たな場所が使用される。さもなければ
元のイメージに関する古い場所が使用される。再
び最少コストを有する場所が構成要素５に割当て
られる。 上述の手順は順序づけされたリストからの全て
の構成要素が重ねイメージ上に配置されるまで続
けられる。この新たな配置は一般に遥かにバラン
スしたチヤネル利用度を持つ。何故ならば元の配
置に基づくHwt及びVwtの値が配置中コストを
偏移するために使用されるからである。配置の品
質も又良好となる。何故ならば或る構成要素に対
する全ての接続がこのステツプ中考慮されるから
である。 利用可能な合計水平及び垂直交差、水平及び垂
直利用度（第２５図）、重み係数Hwt、Vwt［式
(8)及び(9)］が前述のようにして新たな配置に対し
て計算される。これらは以下に説明する繰返し改
善ステツプのあいだ使用される。 再び第１７図において、重ね改善（ブロツク
82）が達成された後に、ペアワイズ（１対式）互
換技法（第２８図）を用いて繰返し改善を得る
（ブロツク83）。ペアワイズ互換技法は周知であ
る。例えば前述の文献を参照されたい。ペアワイ
ズ互換技法は２つの構成要素の現在の場所におけ
る配置のコストを計算すること、及びそれらの場
所を交換した後のコストを再計算することを含
む。もしも新たな場所に重みづけされた利得があ
るならば、交換がなされて新たな場所が２つの構
成要素に割当てられる。これは全ての場所の全て
の構成要素に対して行なわれる。第２８図はペア
ワイズ互換のステツプを示す。 第２８図は重心近くのウインドウ即ち矩形領域
（５×５）を使用する。先ず構成要素の重心が前
述のようにして計算される。次にウインドウの目
標場所におけるペアワイズ互換のコストが下記の
式(13)に従つて計算される。最善の利得を有するも
のとの交換が行なわれる。このプロセスは全ての
構成要素に対して１度実行される。これは下記に
述べるようなコスト関数として式(3)及び(4)を持つ
互換型式１と呼ばれる（ブロツク251）。 この点までは配置は単位サイズ構成要素でのみ
行なわれ、しかもモデル化ステツプにおいて以前
に計算されたような平均寸法の構成要素に基づい
て行なわれた。今や適合関数の確率と呼ばれる付
加的な関数を加味して複数の構成要素のうちのサ
イズのばらつきを償い、且つマクロモデル及び実
サイズ・イメージへの拡張が行なわれるとき各横
列又は縦欄にまたがる全ての構成要素に適合する
確率を増大させる。 先ず合計スペース利用度（構成要素が占有する
回路板の面積）が下記のように計算される。各構
成要素の幅及び高さ（Ｘ及びＹ寸法）を乗算して
加え合わせることにより、構成要素によつて占有
されるイメージ上の合計面積が計算される。この
合計面積を回路板上の利用可能な合計面積（第13
表）で割ることにより、合計面積利用度が計算さ
れる。12構成要素の例ではそれは54.24％になる
（第13表）。今や配線可能性を増すために構成要素
間に空きスペースを残すのが望ましいので、使用
される領域の値、即ち最大可能領域と実際に使用
される領域との間の中間が目標点として算出され
る。 横列又は縦欄にまたがる所望の占有度＝実際の占有度
＋完全占有度／２＝0.77即ち77％ 適合コスト関数の確率は下記のとおりである。
基本的にはそれは横列又は縦欄にまたがる構成要
素の実寸法を合計することと、もしも横列又は縦
欄を占有する構成要素の寸法の合計が上記で計算
されたような所望の占有度目標点を越えるなら場
所を占有する比較的高いコストを割当てることと
を含む。この関数は余り動揺することなく他のイ
メージへの拡張を容易化する。 かくて重ねステツプの後の構成要素の配置（第
２６図の１１７で示す）に基づいて各横列にまた
がつて必要とされる合計幅が、その横列に配置さ
れた構成要素の個々の幅を加算することにより得
られる。例えば横列２では構成要素10、６、８、
５、７の実際の幅が加算される。合計は46であ
る。実イメージの合計寸法は48で、依然として制
限内にある。所望のパーセンテージ値は使用する
各方向の単位の最大数を決定するため回路板の実
際のＸ及びＹ寸法だけ乗算される。 0.77×48（Ｘ寸法）＝Ｘ方向最大37単位 0.77×28（Ｙ寸法）＝Ｙ方向最大22単位 これらの値はXLIMIT及びYLIMITとして知
られている。 適合コスト関数の確率はここで実イメージ上の
構成要素の実サイズを勘定に入れて導出される。 Cost_o＝コスト［式(3)＋(4)］ ＋DWT1×（ROWSUM−XLIMIT） ＋DWT2×（COLSUM−YLIMIT） (13) 但し Cost＝実回路板イメージ上の構成要素サイズ
及び全ての構成要素によつて利用される合計領域
を考慮に入れた目標場所のコスト。 DWT1、DWT2＝密度の高い横列に対しコス
トを偏移するために使う寸法重み。それらの値は
もしも、 ROWSUM／COLSUM＜目標場所を含んだ横
列／縦欄に対する制限ならば０である。もしも、 ROWSUM／COLSUM＞目標場所を含んだ横
列／縦欄に対する制限ならば1.5である。もしも、 ROWSUM／COLSUM＞回路板の寸法（Ｘ又
はＹ）ならば5.0である。 ROWSUM、COLSUM＝目標場所に対する横
列又は縦欄にまたがる実寸法の和。 この付加されるコスト関数はそれらの寸法に基
づいて構成要素を分布するのに役立ち、又配置が
横列又は縦欄にまたがるＸ又はＹ寸法を越えない
ように阻止し、且つマクロモデル及び実イメージ
に記入（マツプ）されたとき回路板上に構成要素
を適合する確率を増す。その間モデル化の低いレ
ベルにおいては最適化した配置を依然として維持
している。 上述の交換１径路が完成したとき、利用可能な
合計水平及び垂直交差、水平及び垂直利用度（第
２５図）がこの配置について前述した通り計算さ
れる（第２８図２５２）。これらは以下に述べる
ように交換径路２において使用される。 この点において交換型式２径路（第２８図、ブ
ロツク253）が実行される。以前のように幾つか
の形状のトリー構造（ステイナー、最少スパン、
半周囲、等）がなされるべき接続を特定するため
に使用される。交換型式１径路の場合のように、
各構成要素に対する重心のまわりのウインドウ
が、構成要素交換のための調査領域として使用さ
れる。この径路の差は以下に特定化されているよ
うにコスト関数の部分変更である。最少スパン・
トリーがこの例で使用されることに注意された
い。コストは下記のように計算される。 Cost_c＝_o 〓¹ MST長 (14) Cost_c＝Cost_c＋_o 〓¹ （Ｘ交差 −Ｘ上方値）×Cwt＋_o 〓¹ （Ｙ交差−Ｙ上方値）
×Cwt (14) 次に実イメージ上の構成要素の実サイズが、式
(13)で以前に説明した適合関数の確率を用いること
により考慮に入れられる。 Cost_c＝Cost_c＋DWT1×（SUMROW−YLIMIT）＋DWT2＋（SU
MROW−XLIMIT）(16) 但し、 ｎ＝１つの構成要素に対するネツトの数 MST長＝前の述べたように計算された最少ス
パン長。 Cwt＝交差カツト偏移のための重み係数。実験
に基づいて2.0なる値を用いる。 Ｘ上方値＝配線可能性計算において説明したの
と同様な要領で得られるＸ方向の最大交差カツト
の90％。 Ｙ上方値＝配線可能性計算において説明したの
と同様な要領で得られるＹ方向の最大交差カツト
の90％。 Ｘ交差＝構成要素の場所と関連した縦欄境界に
おける実際の交差カツト（配線可能性計算で説明
されたように計算される）。 Ｙ交差＝構成要素の場所と関連した横列境界に
おける実際の交差カツト（配線可能性計算で説明
されたように計算される）。 適合関数の確率は型式１の交換に対して以前に
既に説明された。 型式２の交換中に、式(16)で規定されるコストが
それらの現在の場所において交換されるべき２つ
の構成要素に対して計算される（第４０Ｃ図参
照）。 次に適合関数の確率のコストがコストに加算さ
れる。次に現在の場所に基づいたコスト及び交換
された場所に基づいたコストを比較して、もしも
正味の利得があるならば、構成要素は交換されそ
してチヤネル交差カツトはそれらの交換を反映す
るように更新される。かくて第４０Ｃ図の交差カ
ツトは、候補の次の交換のために使用されるべき
ものとなる。 型式２の交換に関連したステツプは型式１の交
換径路において説明したのと同様である。即ち重
心を計算し、ウインドウ内の場所のリストを発生
し、この新たな関数によりコストを計算し、最大
利得を有するものを拾い出し、次に境界を横切る
交差カツトを更新する。 この型式２の交換はその径路において１度全て
の構成要素に対して実行される。この交差最適化
は各境界を横切る需要を平均化するように働ら
き、かくて配線可能性を向上させる。 ２つの交換型式は相互に混合される。配線可能
性計算、交差利用度、及びHw、Vwttはは各交
換が行なわれた後に再計算される（第２８図の２
５２、２５４参照）。最少４つの径路が作られ、
もしもチヤネル利用度が50％を越えるならば、追
加の２つの径路が作られる（第２８図のブロツク
255）。チヤネル交差利用度が50％を越えるとき、
自動配線が成功する確率が減少することが実験的
に観察された。従つて配置を改善するため追加の
相互交換径路が加えられる。単位レベルにおいて
２つ以上の追加径路を作ることは一般的に配置品
質を著しく改善することにつながらないこともわ
かつている。 上述の繰返し改善プロセスの後に、交差カツト
の点で、適合の確率の点で、空スペースの分布の
点で最適化された最終的配置が単位レベルで得ら
れる（第２９図）。このレベルでのモデル化の利
点は全ての構成要素の寸法が違つていたとしても
それらは互換性があることである。その狙いは最
適化された最終的配置を発生するために使用でき
る良好な相対的配置を得ることである。もしも構
成要素のサイズが各方向で20％以上違わないなら
ば、最終的イメージ上に実際の配置が発生された
ときこの相対的配置と同じになる高い確率で極め
て良好な最適配置が既に得られている。 再び第１７図において、単位サイズ配置最適化
の最終ステツプはマクロ・モデル初期配置のため
の場所を発生することである（ブロツク84）。マ
クロ・モデル・イメージ・サイズは以前の計算か
ら入手できる（第１９図、第２０図参照）。第３
０図に示されたように、マクロ・モデル・イメー
ジ１２１のサイズは123で示されたサイズに倍増
されている。それは単位イメージに対して行なわ
れたのと同じ要領（第１８図のブロツク86）でマ
クロ・モデル構成要素の初期配置を行なう目的で
なされた。２倍イメージは２倍の横列及び縦欄を
有し、構成要素を配置するため利用できる格子位
置の数が４倍ある。Ｉ／Ｏ場所は単位イメージに
対して行なつたものと同じ要領（第１８図のブロ
ツク86）で、マクロ・モデル境界上の場所に変換
される（第３０図の１２２）。 第３１図はマクロ・モデル処理のための初期配
置を発生するステツプのあらましを示す。初期配
置は単位サイズからマクロ・モデル・サイズ・イ
メージへの場所拡大（スケール・アツプ）と（ブ
ロツク126参照）、マクロ・モデル・サイズに対す
る重なり状態の解析と、重なりを解消し仮の場所
を発生するためのＸ及びＹ方向へのずらし（ブロ
ツク127、128）と、構成要素の仮の場所の近くに
ウインドウを発生することによりマクロ・モデル
構成要素を２次元的に記入すること、及びその上
に構成要素を配置すること（ブロツク131）とを
含む。第３１図に示されたステツプは最終的最適
化されたマクロ・モデル配置から実イメージ上に
初期解を発生するのにも利用されることに注入さ
れたい。実イメージの最適化に対する相異点を以
下に述べる。 第３１図は単位イメージからマクロ・モデル・
イメージへの場所の拡大（スケール・アツプ）が
示されている（ブロツク126）。第３２図は12構成
要素の例について、単位イメージ上の全ての構成
要素の場所を示す。以前に計算されたように尺度
係数は横列方向及び縦欄方向に２であるので（第
13表参照）、各構成要素に対する全ての場所が２
の係数により拡大される。構成要素１に対する使
用数式および計算例が第15表に示される。

【表】 構成要素１に対する場所は元のように左上角を
使つて横列＝１、縦欄＝２である（第３２図の
135）。かくて構成要素１は横列＝１、縦欄＝３な
る相当した出発場所にスケール・アツプされ（第
３３図の138）、そしてマクロ・モデル・イメージ
上での２×２なる面積を占める。同じ要領で仮の
出発場所が、第３４図及び第16表に図示されたよ
うに全ての構成要素について計算する。

【表】 再び第３１図を見ると、これらの仮の場所のず
らし（ブロツク127）は構成要素のマクロサイズ
を考慮して行なわれる。ずらしは構成要素の重な
りを除くためにマクロサイズ構成要素の新たな格
子位置を上下左右に移動させるプロセスである。
（その重なりは、相対的場所がマクロ及び単位モ
デルのサイズの比率に基づいて変換されるのに反
して個々の構成要素はそれらの寸法に基づいて異
なつた比率を有するので生じることがある）。構
成要素のＸ寸法に対し１度に１横列の解析を行な
つて（第16表の132参照）、構成要素の重なりがあ
るかどうかを判断し、且つ横列方向のどれかの空
スペースを構成要素のずらしに利用できないかど
うかを判断する。全ての構成要素のマクロモデ
ル・サイズがＸ寸法でわかり、それらの出発位置
のＸ座標もわかる。各構成要素によつて占有され
る終端場所はかくて出発場所にＸ寸法を加えて、
結果から１を引くことにより算出される。 ずらしプロセスはイメージ上の左上角で始ま
る。最初の横列にまたがる走査は最初の構成要素
が探知されるまで行なわれる。そのサイズはＸ単
位であり、構成要素の反対側を見付けるために出
発場所に加えられる。次にその走査は次の構成要
素が探知されるまで続く。もしもそれが最初の構
成要素と重なるならば、重なりの量を覚えてお
く。走査は横列全部について続けられ、重なりの
総量が得られる。もしも総量が０であるなら、ず
らしは行なわれない。０でなければ最左端の構成
要素から出発してずらしが行なわれる。もしも左
の回路板端と最初の構成要素との間に余地がある
ならば、最初の構成要素を左端へずらす。横列の
残りの部分に対しても（もしも必要なら）左又は
右へずらすことにより重なりを除くプロセスを続
ける。この場合もしも右へずらすと重なりが生じ
る。縦欄に対するずらしも同様に行なわれる。 第３４図及び第16表の12構成要素の例に対する
上述の計算は最初の横列方向に構成要素２は構成
要素３と重なることを示す。横列１方向のスペー
スは解析すると、全ての構成要素のＸ方向の和は
９で、利用可能な合計スロツト数は12であるの
で、マクロモデル・イメージ内には構成要素をず
らすための空スペースが存在する。空スペースを
更に解析すると構成要素１の前に利用可能な２つ
のスロツトがあり、且つ構成要素４を５に向つて
ずらす１つのスロツトがある。スペースはイメー
ジの端に向つて利用可能である。最初のステツプ
は、構成要素２と３の重なりが１スロツト分だけ
あるので構成要素１を１スロツト分だけずらすこ
とである。かくて構成要素１及び２は第３５図の
147、148で示すように新たな仮の場所を持つ。横
列１中にはもはや重なりがなくなつた（第３５
図）。 第２の横列を解析すると、構成要素８はマク
ロ・モデル回路板の端を越えて伸びていること、
及びその横列は利用可能な空スペースを有するこ
とがわかる。かくて最初のステツプは構成要素８
を内側に２スロツトだけ動かすことである。する
と構成要素８は構成要素１１と重なるので、構成
要素１１を２スロツトだけ左へ動かす。今や構成
要素１１は構成要素７と重なるので、後者を左へ
２スロツト動かす。これによりその横列のＸ方向
の全ての重なりを除去して、新たな仮の場所が
夫々構成要素７，１１及び８に対して第３５図の
１４９，１５０，１５１で示すように作られる。
次に横列に対する同様な解析によりもはや動かす
必要がないことがわかる。 もしも全ての構成要素をはめ込むための空スペ
ースが横列又は縦欄にないならば、マクロモデル
回路板イメージの外側に仮の場所が位置するのを
許容する。これは構成要素に対するマクロ・モデ
ル・サイズを発生するときの丸め誤差に起因して
極めて密度の高い回路板に対して生じることがあ
る。はめ込みのための確率関数［即ち式(13)］は、
横列又は縦欄を横切る全ての構成要素の実寸法の
和が横列又は縦欄を横切る利用可能な合計スペー
スよりも小であることを保証する。 再び第３１図においてＹ方向にずらすステツプ
（ブロツク128）がＸ方向にずらしたのと同様な要
領で行なわれる。左上の角から開始して１度に１
つの縦欄の解析が行なわれる。12構成要素の実例
において、構成要素４の縦欄までの全ての縦欄で
問題がない。構成要素４は構成要素８と１スロツ
トだけ重なり、構成要素４を縁に向つて上方に移
動する余地がない。かくて構成要素８が１スロツ
トだけ下方に動かされる。今やＹ方向の重なりは
存在しなくなつた。構成要素８の仮の場所を第３
６図の153で示す。 Ｙ方向の移動によりＸ方向の重なりが生じたか
も知れないので、Ｘ方向及びＹ方向にずらす追加
の回が行なわれる。もしもＸ及びＹずらしステツ
プのどの回でも移動が行なわれないならば、次回
は行なわれない。Ｘ及びＹ方向にずらす最大３回
の処理がマクロモデルに対し仮の場所を発生する
ために行なわれる（ブロツク129）。もしも３回の
終りにおいて依然として重なりがあるらば、２次
元モデルの実際の記入（マツピング）が実行され
る次のステツプで処理される。 もしも何か予め配置された又は固定された構成
要素が存在するなら、それらの構成要素はずらし
処理中動かされず他の構成要素がそれらをまたい
でずらすことができることにも注意されたい。例
えば第３５図及び第３６図において、もしも構成
要素７が予め配置されて固定されていたならば、
構成要素１１のＸ方向の動きは構成要素７をまた
いで動き、構成要素７は現在占有している場所
（第３５図の１４９）を占有する。 再び第３１図において、構成要素はマクロ・モ
デル上に記入（マツプ）される（ブロツク130）。
全ての予め配置された構成要素が先にマクロ・モ
デル・イメージ上に記入される。例えばもしも構
成要素１２が予め配置されているならば、第３７
図の１５６で示すようにその場所から記入され
る。然る後左上角から構成要素が以前に発生され
た仮の場所（第３６図）に基づいて１度に１つ宛
記入（マツピング）される。記入（マツピング）
の初期配置はずらしステツプ後に作られた仮の場
所から行なわれる。かくて構成要素１は横列＝
１、縦欄＝２なる仮の出発場所と、２×２なるサ
イズとを持つ。その記入状況を第３７図の１５４
で示す。もしもその仮の場所に基づいて構成要素
を配置するに際して、記入済みの構成要素が既に
占有している領域をその構成要素が占有するなら
ば、仮の場所の近くのウインドウ内が調べられ
る。仮の場所から全ての方向に１単位加えること
によりウインドウが形成され、他の構成要素によ
つて既に占有されてはいないウインドウ内の場所
に対する調べがなされる。もしも調べが不調であ
つたなら、ウインドウを全ての方向に１単位だけ
拡張して、場所が見付かるまで調べを続ける。例
えば構成要素２の出発場所が横列＝１、縦欄＝３
であつたと仮定すると、構成要素１によつて既に
占有された領域の１部を占有することになる。そ
のとき仮の場所から１単位だけ−Ｘ、−Ｙ、＋Ｘ、
＋Ｙの調べがなされて、構成要素２を第３７図の
１５７で示すように配置するのが可能になる。も
しも第１回目の調べで場所が見付からないなら
ば、ウインドウを１度に１単位だけ更に拡張し
て、場所が見付かるまで調べを続ける。以前に説
明したように、調べは所望のマクロ・モデル・イ
メージの外側にマクロ・イメージを２倍にするこ
とが許される。何故ならばマクロ・モデル化に際
して丸め誤差がマクロ・モデル単位を半分にする
ことにより構成要素のサイズを増すことがあるか
らである。 出発点（左上角）から全ての構成要素が１度に
１つ宛配置される。先ず全ての予備配置済み構成
要素が配置される。次に全ての構成要素が最初の
横列に配置された後、第２の横列が左端から配置
される。次の横列が１度に１つ宛、全ての構成要
素が配置されて初期の解が発生されるまで記入さ
れる（第３１図のブロツク131参照）。構成要素に
対する初期配置解を第３８図に示す。 当業者なら第３１図に略示されたステツプの代
りに、重なりによる吸引力及び反発力を利用した
技法を用いてマクロ・モデルのための初期配置を
発生できることに注意されたい。 更に当業者なら、第３１図のブロツク131で発
生されたマクロ・モデル配置は単位サイズ配置の
終り（第１７図のブロツク84）で発生された最適
最終関連解から動揺したことがわかるだろう。こ
の動揺はマクロ・イメージの中心へ向う構成要素
７の動きにおいて例証される。構成要素のサイズ
の変動幅が向くなればなるほど、大きな動揺を生
じる。 配置最適化−マクロ・サイズ 再び第１図において、マクロ・モデルのための
初期解が最適化される（ブロツク24）。マクロ・
モデルのための最適化プロセスは単位サイズ配置
最適化（第１７図）と同じステツプを沢山含む。
具体的にいうと、初期配置の一部として（第１７
図のブロツク81）、第１８図のブロツク89におい
て単位モデルのために行なわれた水平及び垂直交
差利用とチヤネル交差利用とがマクロ・モデルに
対しても行なわれる。第１８図のブロツク91にお
いて単位モデルのために計算された重みづけ係数
がマクロ・モデルのためにも計算される。次に単
位モデルに対して説明したのと同じ要領で、マク
ロ・モデルのための最適配置を得るため重ね（第
１７図のブロツク82）及び繰返し改善（第１７図
のブロツク83）を介して配置が最適化される。こ
れらの各ステツプを再度説明することは避けて、
単位モデル最適化とマクロ・モデル最適化との間
の相異のみについて説明する。 単位モデルに対して第１８図のブロツク89及び
91でなされたように、配線可能性、水平及び垂直
チヤネル利用度、交差カツト、水平及び垂直重み
がマクロ配置のために計算される。構成要素のマ
クロ・モデルの中心を距離計算の開始点として選
ぶ。実際の構成要素上のピン場所がマクロ・モデ
ル上のピン位置に変換され、これらのピン位置は
距離の計算及び配線可能性情報の発生に使用され
る。周囲の場所には単位モデル化について前述し
たように重みが割当てられる。然る後重ね合わせ
による改善が前述（第１７図のブロツク82）と同
じ要領で実行される。重ね合わせによる改善はマ
クロ・モデル・レベルでは一層重要である。何故
ならば等しくないサイズの２つの構成要素の交換
が位置の交換によつて生じる重なりに起因して複
雑化するからである。例えば、もしも構成要素２
（第３７図の１５７）が構成要素１１の占有して
いる領域、及び構成要素７の占有している領域の
１部、を占有することを希望するならば、それら
の交換は非常に複雑となる。例えば構成要素７を
左へずらし、次に構成要素１１と２を入れ換える
等のことは、入れ換えるべき構成要素のサイズが
広範に変換するにつれて益々複雑化する。重ね合
せステツプは、構成要素の交換によつてなされる
移動を容易化する。何故ならば位置づけはコスト
に基づいてなされ、構成要素はブランク・イメー
ジ上に配置されるので重ね合わせ中は重なりが生
じる筈がないからである。 単位モデルのために記憶された配線可能性情報
（水平及び垂直チヤネル交差の総数）が、各ステ
ツプ毎に２つの値の和を比較することによりマク
ロ・モデル配置の情報と比較される。もしもマク
ロ・モデル・イメージへの変換に際して解が動揺
し、そしてチヤネル交差総数が10％以上増加した
ならば、更にもう１つの重ね改善ステツプが実行
される。 重ね合せの後、前述の交換技法（第１７図のブ
ロツク83）を、ネツトと関連した距離の計算の開
始点として使用される構成要素のマクロ・モデル
の中心と共に使用する。式(8)及び(9)中の定数に尺
度係数が乗算される。何故ならば距離はその係数
分だけ長いからである。回路板の周囲の場所の重
みづけは単位イメージに関するものと同様に実行
されて、拡大された重み（この実例では尺度係数
は２であるので、元の値の２倍）を割当てる。適
合のための確率関数［式(16)］において、重みは尺
度係数により比例的に拡大される。 マクロ構成要素のサイズは可成り変化するの
で、ペアワイズ交換プロセスは単位モデル最適化
で説明したのとは下記の点で相異する。コストは
前述のように、即ち式(3)で計算される。各ペア毎
に現在の場所に対して計算され、その後各構成要
素をイメージから取除いて両構成要素を他のもの
の場所に記入（マツピング）する。これらの新た
な場所のコストを計算し、もしも重みづけされた
距離で改善が認められたなら、交換を実行する。
もしもこの交換ステツプ中に構成要素が他の構成
要素と重なるならば、その交換は実行されない。
例えば第３７図において構成要素２を構成要素９
と交換しようと試みる。しかし構成要素２を構成
要素９の場所に記入（マツピング）すると、構成
要素１０と重なる。したがつてこの交換は実行さ
れない。 第２の例として構成要素２と構成要素１は上述
のプロセスにより交換可能である。構成要素１及
び２によつて占有された両領域はブランクにさ
れ、そして構成要素２及び１が他の何れの構成要
素と重なることなく同じ領域に置換できる。かく
てこの交換は実行される。 交換プロセスの１部として、コスト低減効果が
得られるか否かを知るためにウインドウ内の自由
領域（もしもそれがあるならば）と構成要素が
「交換」される。もしも効果が得られるならば構
成要素はその新たな場所に配置される。例えば構
成要素７はは１単位左にも適合し又は１単位下に
も適合するので、これらの２つの場所のコストを
計算する。そして３つの場所のうちの最少コスト
の場所を選ぶ。 要約すると、マクロ・モデルのためのペアワイ
ズ交換は、或る構成要素の現在場所のコストを計
算するステツプと、その重心を計算するステツプ
と、候補場所領域を調べるステツプと、その領域
にもしも存在するならその構成要素を拾い出すス
テツプと、両構成要素の現在場所をブランクにす
るステツプと、もしも交換が可能なら交換のコス
トを計算するステツプと、もしも重みづけされた
コストが改善されるなら交換するステツプとを含
む。重みづけされたコストは前述のように式(3)で
計算される。 マクロ・モデルのための交換アルゴリズムは、
同一サイズのマクロ構成要素を迅速に交換できる
ようにするため修正されてもよいことに注意され
たい。例えば構成要素１，７，１１，１０，１２
のマクロ・モデルは同一サイズであるので、記入
（マツピング）ステツプのブランク化部分及び交
換が可能か否かを調べる部分がなくても交換でき
る。配置問題のサイズの低減は別として、マク
ロ・モデル化の他の利点は、構成要素１，７，１
０，１１，１２の実際の寸法が僅かに相異したと
しても、それらのマクロ・モデル寸法は同一であ
つて、これらの構成要素の何れを相互に交換する
こともマクロモデル・レベルで容易に実現できる
ことである。 単位サイズ最適化（第２８図）に対して前述し
た要領でペアワイズ交換の幾つかのステツプが実
行されて最終的な配置が得られる。12構成要素に
対する最終的配置が第３９図に示される。 繰返し改善の後、実サイズ初期配置の場所がマ
クロ・モデルのため第１７図のブロツク84で述べ
たのと同じ要領で発生される。第４１図は実モデ
ル初期配置のための場所発生ステツプを示す。第
４１図は実イメージに拡大（スケール・アツプ）
するステツプと、Ｘ及びＹ方向にずらすステツプ
（ブロツク166）と、実サイズ・イメージ上への２
次元マツピング（ブロツク167）と、未配置構成
要素の挿入ステツプと、未配置構成要素の適合化
（ブロツク169）と、初期解の発生ステツプ（ブロ
ツク171）とを含む。第４１図のステツプはマク
ロ・モデル初期配置のための場所発生中に行なわ
れたステツプ（第３１図）と多くの点で共通して
いるので、相異点のみについて説明する。 マクロ・モデル・ステツプにおけるＸ−Ｙ方向
のずらしの間は、構成要素は所望のマクロ・モデ
ル・イメージの外側にはみ出す仮の場所を持つこ
とが許される。しかし実イメージ・ステツプにお
けるＸ−Ｙ方向のずらしの間は（第４１図のブロ
ツク166）、構成要素は実イメージの外側の場所を
持つことが許されず、重なりを持つことが許され
る。この重なりは、夫々ブロツク167，168，169
と関連して以下に説明されるマツピング中、又は
挿入及び適合又は圧縮ステツプ中に処理される。 実イメージ上の仮の場所はマクロ・モデルに対
する前述の要領と同様に発生される。先ずマク
ロ・モデルから実イメージへの拡大（スケール・
アツプ）が実行される（ブロツク166）。結果を第
17表に示し、その場所を第42に図示する。

【表】 次のステツプはＸ方向にずらすことである（ブ
ロツク166）。マクロ・モデルのずらしのために第
３１図のブロツク127で行なつたように、横列を
横切る構成要素のリストが発生され、もしもある
なら空スペース及び重なり状態が発生され、そし
てＸ方向のずらしが実行される。例えば第１の横
列を横切る構成要素５の出発場所はＸ方向の４１
である（第17表）。その実寸法が10単位なので
（第１９図、第２０図、および第18表参照）、その
１部がイメージの外に出る。従つて内側へのずら
しを行なう。新たな場所が第18表に示すように発
生される。然る後次の横列が解析され、構成要素
が必要に応じて移動される。

【表】 次にＹ方向のずらしが行なわれる。この例では
Ｙ方向の重なりがないので、ずらしプロセスは打
切られる。重なりがあるならば、マクロ・モデル
Ｙ方向ずらしについて説明されたのと同様なステ
ツプ（第３１図、ブロツク128）が実行される。
最終的な仮の場所を第18表に示す。 再び第４１図において、次のステツプは実イメ
ージ上の構成要素の２次元的マツピングである
（ブロツク167）。このマツピングは第３１図のブ
ロツク129について説明したマクロ・モデル・マ
ツピングと類似している。このマツピング中は、
テスト・ポイント領域及び留保領域（第９図）は
配置のために利用できなくされる。予め配置され
た構成要素（第９図）及びイメージ上の電圧ポツ
プアツプ・ポイント（第７図）に関する制約を下
記に述べるように考慮に入れる。更に入力情報の
１部としてユーザーは、格子上の特定の場所で始
まる特定サイズの構成要素を配置できるに過ぎな
いことを特定化してもよい（第３図及び第４３
図）。この制約を処理するためのアルゴリズムを
以下に説明する。 第３図に示した各格子点には、各ペアの格子点
間の中途に線を引くことによりそれを取囲む領域
が割当てられる（第４３図参照）、約1/4のイメー
ジしか第４３図に示されていない。構成要素のサ
イズが１×１であるとき、それは第４３図の１７
２で示すような領域を占有する。同様にサイズ４
×１の構成要素は第４３図の１７３で示す領域
（４縦欄×１横列）を占有する。 １つの構成要素に対してユーザーは特定サイズ
の構成要素が配置されなければならない場所（第
４３図の１７６，１７７，１７８参照）を指定し
てもよい。異なつたサイズの構成要素に対しては
回路板上の場所（複数）を指定することができ
る。この場所は他のサイズの構成要素の場所と重
なつてもよいようしてもよい（例えば第４３図の
179、181、182）。マツピングは構成要素が配置さ
れたとき重なりが生じないことを保証する。 マツピングに関連したステツプを以下に述べ
る。マツピングはマクロ・モデル・イメージ上の
横列位置に基づいて構成要素の順序を発生するこ
とと、もしも必要なら境界内で移動することによ
り配置の制約を破ることなく実イメージ上に構成
要素をマツピングすることとを含む。 先ず、配置されるべき構成要素の順序が発生さ
れる。これはマクロ・モデル・イメージの各横列
を左上角から開始して走査し、１つ宛リストに構
成要素を加えることにより行なわれる。構成要素
は走査されつつある横列の上側又は下側に１つ又
はそれ以上の横列を占有することがあるので、構
成要素はリストに唯１度だけ（即ち横列の走査中
に出合つた最初のときだけ）加えられる。例えば
第３９図において、構成要素１，２，３，４，５
は第１番目の横列で拾い出され、次に２番目の横
列は新たな構成要素が現われず、第３番目の横列
で構成要素６，７が加えられ、第４番目の横列で
構成要素８が加えられ、第５番目の横列で構成要
素９，１０，１１，１２が加えられ、第６番目か
らは新たな構成要素が加えられない。 もしも入力の１部として指定された留保領域が
あるならば、イメージ上のその領域は利用不能領
域としてマークされる。同様にテスト・ポイント
横列および縦欄が利用不能領域としてマークされ
る。 マツピングについて述べると、全ての予め配置
された構成要素が夫々の特定の出発場所及びＸ−
Ｙ寸法に基づいてイメージ上に初期的にマツプさ
れる。予め配置された構成要素が占有する全ての
格子点はその構成要素の番号に従つてフラグ（標
識）が立てられる。構成要素１についてそのサイ
ズに基づいて格子上にマツピングする例を第４４
図に示す。この２次元マツピングは次に構成要素
の４つの側面に何があるかを探すためのコンピユ
ータ時間を節約するのを助け、下記のような挿入
ステツプ及び適合ステツプに大いに役立つ。 今や構成要素は上述で発生された配置されるべ
き構成要素順のリストから１度に１つ宛選ばれ
る。各構成要素には、前に発生された仮の場所に
基づいて実際の格子上の場所が与えられる。もし
もその構成要素を配置すると何らかの制約（予め
配置された構成要素、電圧ポツプアツプ、留保さ
れた領域、テスト・ポイント等）に違反しないか
否かを調べるためのチエツクが行なわれる。もし
も違反が生じるならば、ウインドウ内の有効な場
所を探すための調査が行なわれる。もしも有効な
場所が発見されないならば、その構成要素は下記
のように挿入及び適合のときに配置される。 かくて上記に概説した順次リストから、構成要
素１は以前に発生された仮の場所に基づいて実際
の格子上の場所に割当てられることになる（第18
表参照）。その左上角は5.1であり、右下角は11、
９である。これら２つの対向した角の間のイメー
ジ上の領域を構成要素を配置するために使用しな
ければならない。禁止領域及び予め配置された構
成要素を除く全ての格子上の点が最初は利用可能
である。利用度を上げるために占有すべき全ての
格子点をチエツクするための調査が、出発点から
行なわれる。 もしも電圧ポツプアツプ点があるならば下記の
ステツプが実行される。先ず、構成要素に対する
全ての点の場所がその構成要素のための所望の出
発点に基づいて作られる。次にこれらの全ての場
所を、電圧ポツプアツプ点に関連した場所のリス
トに対してチエツクする。もしも格子場所と関連
した電圧値の間に不釣合いが生じるならば、その
構成要素は仮の目標場所に基づいて配置できな
い。もしも禁止領域が出て来たならば構成要素を
仮の目標場所に配置できない。 もしも希望場所のリストがユーザー入力情報の
１部として特定されているならば、最寄りの利用
可能場所がウインドウ内にあるか否かのチエツク
がなされる（後述）。もしもウインドウ内に利用
可能な余分の場所があるならば仮の場所に最寄り
の場所を拾い出す。もしもウインドウ内に利用可
能な場所がないならば、構成要素は配置されずに
残り、後述の挿入及び適合ステツプ中に配置され
る（第４１図のブロツク168、169）。 もしも目標場所に基づく利用可能領域が十分に
ないならば、又は構成要素が電圧ポツプアツプ制
限に違反するならば、構成要素のＸ及びＹ寸法よ
り各方向に1/2だけ広いウインドウ内で調査が行
なわれる。ウインドウは１度に１単位だけ−Ｘ、
−−Ｙ、＋Ｘ、＋Ｙに拡大され、もしもその場所に
配置されたなら何かの制限に違反しないか否かを
調べるためのチエツクがなされる。もしも有効な
場所が発見されたならば、それが構成要素をマツ
プする場所である。発見されなかつたならば、そ
の構成要素は下記の挿入及び適合ステツプ中に配
置される。 上述のステツプは全ての構成要素に対してその
順序に基づいて繰返される。全ての未配置構成要
素は、下記のように挿入及び適合ステツプ中に配
置される。 12構成要素問題の例では、全ての構成要素は上
述のステツプに基づいて夫々の仮の場所に配置さ
れる。３構成要素の２次元マツピングを第４４図
に示す。実イメージの凡そ1/4だけを示す。実イ
メージ上の全ての構成要素の格子無関係配置を第
４５図に示す。12構成要素問題に対する初期配置
を第４６図に示す。第４６図は構成要素の実サイ
ズを正確に表わしている。 第４１図のブロツク168、169と関連して説明さ
れる挿入及び適合ステツプは夫々、上述のマツピ
ング・ステツプ（第４１図のブロツク167）の後
に未配置構成要素がある場合にのみ使用される。
挿入及び適合ステツプは構成要素混合物から最初
に取除かれた比較的小さい構成要素の配置のため
にも使用される。挿入及び適合ステツプ中は２次
元マツピング中に見られた全ての制約が見られ
る。例えば全ての予め配置された構成要素は固定
状態に保たれ、動かされない。下記のようなコス
ト計算が構成要素のピン位置に基づいて行なわれ
る。この計算のために式(3)が使用される。そして
前述のように既に配置された構成要素又はＩ／Ｏ
に対する接続を含むネツトのみが考慮される。 第４８図において、挿入は未配置構成要素の目
標場所のまわりのウインドウ中の利用可能スペー
スを探し、そして他の構成要素を目標場所からウ
インドウの境界の方へ移動させ、構成要素を配置
するためのスペースを作ることである。境界へ向
つて構成要素を移動するコストは特定の構成要素
を移動するか否かを選ぶために決められる。もし
も構成要素の挿入に失敗すると、第４１図のブロ
ツク169の適合又は詰込みのステツプが使用され
る。 未配置構成要素を配置のために選択する順序
（第４８図のブロツク230）は、マクロ・モデル配
置から実イメージ配置への拡大中に作られた原順
序である。挿入の最初のステツプは未配置構成要
素をその目標場所に配置するコストを見積ること
である（ブロツク231）。構成要素は実際に配置さ
れずそのコストのみが計算される。 上述の最初のステツプを図解するため、７×７
のサイズを有する構成要素を上述の初期マツピン
グ・ステツプ中に、目標場所第36欄第９列に配置
できなかつたものと仮定する（第４６図の１９１
参照）。その目標場所に構成要素を配置するコス
トが既配置構成要素に対するその接続に基づいて
計算される。その目標場所（第４７Ａ図の１９
３）からＸ−Ｙ方向に構成要素のサイズの２倍の
ウインドウが発生される。かくて上述の例ではウ
インドウの左上角は第22欄、第１列にあり、右下
角は第48欄、第23列にある。このウインドウは第
４７Ａ図の１９２で示される。 第４８図において、ウインドウ内の全ての利用
可能な場所を数えて（ブロツク232）、もしもウイ
ンドウ内の利用可能な場所の総数が構成要素配置
のために必要な数よりも少ないならば、構成要素
の寸法を３倍にするようにウインドウを拡大する
（ブロツク233）。もしも依然としてスペースが不
足するならば（ブロツク234）、構成要素はその時
点では未配置に留まり（それは後述の適合ステツ
プ中に配置される）、リスト中の次の構成要素が
処理のために選択される（ブロツク230）。 ２倍又は３倍サイズのウインドウ内に構成要素
を配置するために利用可能な十分なスペースが数
えられなかつたならば、構成要素を配置するため
に必要な隣接領域が利用できるか否かを見分ける
ための調べが行なわれる。もしもそれだけの隣接
領域が利用できないならば、構成要素を境界に向
けて移動させるための次節の始めに概説するステ
ツプ（ブロツク236）が実行される。もしも隣接
領域が利用可能で、しかももしも構成要素を何の
制限に違反することなく配置可能であるならば、
その場所に構成要素を配置するコストが計算され
る（ブロツク238）。もしもこのコストが目標場所
について計算されたコストの110％よりも少ない
ならば、構成要素はそこに配置され（ブロツク
242）、そして第４８図に示すステツプが次の未配
置構成要素のために続行される。もしもコストが
目標場所のコストの110％よりも大であるならば、
ウインドウ内の他の場所を同様に処理する。これ
は全部の場所について行なわれる（ブロツク
241）。もしも未配置の構成要素がまだあるなら
ば、構成要素を境界に向けて移動するための下記
のステツプが実行される。 ウインドウ内で構成要素を１度に１方向に、四
方の境界へ向けて移動して構成要素を配置すべき
スペースを作る（ブロツク236）。最初の移動は左
境界へ向い、次に右境界、上側境界、最後に下側
境界へなされる。構成要素の挿入を容易化するた
めの２つのリストが下記のようにして作られる。 左境界へ向う移動において（第４７Ａ図の１９
７）、目標点（第36欄）の左に配置される構成要
素のリストが発生される。もしも構成要素の領域
の半分がその境界内に入るならば、それはリスト
に含められる。例えば第４７Ａ図の１９８から１
９３の境界内では構成要素３，４，７が移動のた
めの候補である。構成要素Ａもこのリストに加え
られる。このリストを以後リストＱと呼ぶ。 左側移動に対する境界間で、最初の処理中に移
動されるべき構成要素のリストを作るため各横列
が調べられる。この処理中に移動されない最初の
構成要素が出現したとき、その横列に対する調べ
が打切られ、その構成要素はリストＰと呼ばれる
別のリストに加えられる。このリストは先ず左境
界に向けて移動されるべき構成要素のリストであ
る。かくて上述の例では構成要素３及び７がリス
トＰに入る。それらの現在の配置のコストを計算
して後述の比較のために記憶しておく。それらが
占有した領域はブランクにされるので、リストＱ
の構成要素は何れもこれらの位置を占有すること
ができる（第４７Ａ図の194、195参照）。 ウインドウの最左境界から最初の利用可能な位
置に構成要素を配置するコストがリストＱの構成
要素のために計算される（ブロツク238）。式(3)を
用い、且つマツピング後の配置について全ての場
所を用いる。利用可能領域に基づいて配置できる
構成要素のコストを計算する。他の構成要素には
目標場所コストの２倍が割当てられる。式(3)から
のこのコストに対して、目標場所及び新たな場所
のピン位置間のマンハツタン距離コストが加算さ
れる。このマンハツタン距離コストを加算する目
的は構成要素をその元来の場所に出来るだけ接近
させることである。何故ならば最適化は既に終つ
ているからである。これらの両コストの合計を以
後移動（ムービング）コストと呼ぶ。これらのコ
ストは移動前に既に計算された構成要素の元のコ
ストで割算される。最低値を有する構成要素がそ
の位置を占有する候補として拾い出される。もし
もコスト増加が10％より大きいならば（ブロツク
238）、移動は取止めて、リストＱ中の構成要素に
対する次の利用可能な場所に対して上記ステツプ
を繰返す（ブロツク239）。もしもある構成要素に
対して有効な場所をコストに基づいて発見したな
らば、構成要素を配置する。上記のステツプは目
標場所（第36欄）に到達するまで（又はもしも全
ての構成要素が配置され終えたならばそれより早
い時点まで）繰返される。もしもリストＰにある
以外の構成要素が配置されたなら、それを以前の
場所から取除く。 上述のプロセスにより構成要素７は第４７Ｂ図
の１９５で示す位置を占める。それをリストＱ及
びリストＰから取除く。リストＱの残りの構成要
素に対するコストを構成要素７の新たな位置に基
づいて再計算する。 これらのステツプをリストＱ中の構成要素に対
して繰返す。構成要素３は同様なステツプにより
第４７Ｂ図の１９６で示す場所に配置された。そ
れをリストＱ及びリストＰから取除く。今やリス
トＰ中に構成要素が存在しなくなつた。 リストＰを再び作る。構成要素４が左へ向つて
移動させる唯一の候補である。リストＱから（構
成要素４及びＡ）、上述のステツプを繰返す。構
成要素４を第４７Ｂ図の１９７で示す新たな場所
へ移す。この移動により構成要素Ａに対する十分
なスペースが作られる。利用可能な場所にそれを
配置するためのコストを計算し、そしてもしもそ
の仮の場所に基づいて計算されたコストの110％
以内であるならば構成要素はその場所に配置され
る。そのために選ばれた場所を第４７Ｂ図の１９
９で示す。 構成要素Ａは依然として未配置であると仮定す
る。そのときは右境界へ向う移動を開始する。左
境界へ向う移動についての前述のステツプと同様
なステツプを実行する。もしもその構成要素が依
然として未配置であるならば、上側及び下側境界
へ向う移動を必要に応じて同様に実行する。 上述の四方向への移動が終つたときもしも或る
構成要素が依然として未配置であるならば、ウイ
ンドウを構成要素サイズの３倍に拡大する。構成
要素はそれらに許容される回転を行なつてもよ
く、その場合は最低コストの回転コストを使用す
る。移動のコストの増加は15％までは許される。
上述の全てのステツプをこの拡大されたウインド
ウで１度繰返す。もしも全ての構成要素が上述の
プロセス中に配置され終えたならば、適合のため
の次のステツプは行なわない。 再び第４１図において、適合（ブロツク169）
は回路板上の全イメージがウインドウ内にあるこ
とを除き挿入（ブロツク168）と同様である。回
転が行なわれ、構成要素当りのコスト増加は20％
までは許される。この処理はもしも必要ならば２
回行なう。大抵の場合は挿入と適合の組合せによ
り全ての構成要素が配置されるようになる。もし
も配置されなかつたならばマツピングからのステ
ツプ（ブロツク167）を先ず最大の構成要素に基
づいて繰返し、次にはそれより小さい構成要素に
基づいて繰返す（以下同様）。上述のステツプを
繰返して一般に全ての構成要素をこの手順によつ
て配置する。もしも未配置構成要素が残存するな
らば、それは以下の実サイズ最適化の最終ステツ
プ中に処理することになる。 第４１図に示すステツプが完了し、その結果を
第４６図に示す。モデル化を介して考察した全て
の構成要素の初期配置が実イメージ上で達成され
た（ブロツク171）。 配置最適化−実サイズ 第１図のブロツク26で、実サイズ・モデルの初
期解が最適化された。第４９図は実サイズ配置最
適化中に行なわれる各ステツプを示す。これらの
ステツプは構成要素の分散（ブロツク206）、構成
要素の交換（ブロツク207）、比較的小さい構成要
素を配置するための原ネツト・リストの導出（ブ
ロツク208）、配置済み構成要素に対する接続度に
基づくそれらの順序の発生（ブロツク209及び
211）、コストに基づくもし必要なら挿入及び適合
を用いての配置（ブロツク212）、及びＩ／Ｏの割
当て（ブロツク214）を含む。各ステツプについ
て以下に詳述する。 構成要素の分散（ブロツク206）はＸ及びＹ方
向にずらすのに関連した説明したステツプと同様
である（第３１図のブロツク127、128）。ずらし
によつて重なりを除くのに代えるここでの狙い
は、構成要素のサイズ及びずらしに基づいて構成
要素間に空スペースを分散すること、又は移動コ
ストに基づいて構成要素の場所を再配置すること
である。このステツプを２回繰返す。マツピング
中に観察される全ての制約はここでも観察され
る。移動コストは現在の場所でのコストの115％
より大きくできない。分散は２つの方法で役立
つ。これは必要なスペースを用意することにより
最終ステツプにおける全体的書込みに役立ち、更
に余裕を与えることにより比較的小さい構成要素
の配置中にも役立つ。最初の方向は横列方向であ
り、Ｘ方向のスペースが分散される。次の方向は
縦欄方向であり、Ｙ方向のスペースが分散され
る。 更に具体的にいえば、分散は横列を横切つて利
用できる自由スロツトの数、及びその横列中の構
成要素の数を決定することにより達成される。例
えば第４６図には12スロツトと５構成要素とがあ
る。 次にそれらのＸサイズの和を計算する（第19表
の204）。

【表】 ペース
次に上記第19表の式を使い、各構成要素と関連
させる必要がある空スペースがそれらのサイズに
基づいて計算される（第19表の216）。次に２つの
構成要素間の境界に対して空スペースを残すため
の平均所望スペース（第19表の217）を空スペー
ス値に基づいて計算する（第19表の216）。これら
の平均値を合計する。もしもその合計が合計利用
可能値よりも小であるならば、先ず最も小さい値
に対してそれを加算することにより１度に一１つ
宛、残りの空スペースが分配される。そしてそれ
でもなお同一値に過ぎないならば、Ｘ方向の和が
大である１対の構成要素に割振られそれでも同じ
ならば任意に選択する。上記のステツプに基づく
最終的な所望の分布を第19表の218で示す。 所望の方向への移動コストは上述の要領で計算
する。もしも移動コストが現在場所におけるコス
ト［式(3)］の115％よりも大であるならば移動を
拒否して、Ｘ方向の次の場所について試みて、コ
ストが所望の限度内に納まるまで続ける。然る後
その移動を承認する。 かくて12構成要素の例（第４６図）を参照する
と、構成要素１は移動コストに基づいて角へ移動
し、構成要素２，３はそれらの間に所望のスペー
スを与えるように再配置される。構成要素４は左
へ４場所だけ移動しなければならなかつたものと
仮定する。そのとき構成要素７がその進路に存在
するので構成要素４は移動できない。構成要素４
は左へ１場所だけ移動し、構成要素７が後続のス
テツプで左へ移動した後のステツプで更に移動す
ることになる。１つのステツプ中に移動した構成
要素はそのステツプで再び移動されない。 １度に１つの横列を処理すると移動されない構
成要素６及び７に出合う。その横列を横切る４つ
の構成要素があり、上述のステツプが実行され
る。構成要素７は移動コストに基づいて４スロツ
トしか移動できない。次に構成要素９，１０，１
１，１２が解析されて、移動コストに基づいて再
配置される。この移動後の仮の配置を第５０図に
示す。 同様にＹ方向の移動を行なう。然る後にＸ及び
Ｙ方向の移動を繰返す。これらのステツプの後の
最終的配置を第５１図に示す。 次にこの配置の配線可能性の評価を行なう。交
差カツト、合計長、水平及び垂直利用度、Hwt
及びVwtを前述のように計算する。これは配置
の品質を評価するために行なう。前述のように構
成要素と関連した全てのピン位置を使用する。 第４９図において繰返し技法により改善を行な
う（ブロツク207）。マクロ・モデルのための上述
の技法を使用する。型式１の式をコスト評価のた
めに使用する。この配置を最適化するため１回だ
け実行する。もしもマツピング、挿入、適合及び
分散のあいだに動揺が配線可能性解析中に評価さ
れた値の10％より多くチヤネル交差利用度を増加
したならば、型式２交換を有する追加ステツプを
実行する。 再び第４９図において、以前に除去された比較
的小さい構成要素（第１０図３７）を持込むため
ネツト・リストを更新する（ブロツク208）。この
原ネツト・リストに基づいて接続度マトリツクス
（第７表、第８表）が全ての構成要素に対するの
と同様な態様で発生される（第４９図２０９）。
配置済みの構成要素に対する接続度マトリツクス
の横列が拾てられる。未配置構成要素に対する横
列が解析され、最大値（第７表の58）及びその高
度に接続される構成要素（第７表の59）が発生さ
れる。この最大値（第７表の58）に対して、構成
要素のサイズに基づいた或る値を付加して、最初
に配置されるべき大きいサイズを有する構成要素
に対する選択を与えるようにする。何故ならば領
域の大部分が既に他の構成要素によつて使用され
てしまつているからである。この値は構成要素の
マクロ・モデル（第５表）を発生するのに使用さ
れた尺度係数（この場合は４）により構成要素の
サイズを割算することにより計算される（第５
表）。次に第４９図のブロツク211の順序づけステ
ツプを行なうため第10表、第12表に示すようにリ
ストを分類する。 ブロツク211において１度に１つの構成要素を
順序リストから拾い出す。その重心（第２７図）
を前述のように計算する。構成要素を重心に配置
するコストが最少スパン・トリーを用いて計算さ
れる。ウインドウ内（５×５）の利用可能な位置
のリストが発生され、もしも必要なら前述のよう
に拡大する。この場所のリスト中の全ての可能な
回転により構成要素を配置するコストを計算す
る。最少コストを有する場所が目標場所として拾
い出される。この最少コストを上記で計算した重
心場所コストと比較する。もしもこのコストが25
％以上大であるならば、その構成要素に対するよ
り良いスポツトを発見するため必要に応じて挿入
及び適合のステツプを使用する。 上記の技法を用いて、順に並べた全ての比較的
小さい構成要素を配置する（第４９図、ブロツク
212）。これは全ての構成要素が配置された初期配
置を与える（第４９図、ブロツク213）。これを第
５２図に示す。 今やＩ／Ｏ割当ての次のステツプ（第４９図、
ブロツク214）を実行する。リニヤ割当て技法を
使用する。原理裏付けリニヤ割当ては、合計コス
ト（即ち個々の各割当てのコストの和）が最小に
なるように割当て問題に対する解を見出すことで
ある。 或るネツトは電圧Ｉ／Ｏ（次レベル・パツケー
ジ上に電圧をプラグインするＩ／Ｏ）に接続され
る必要がある。そのようなＩ／Ｏのグループが形
成され、電圧Ｉ／Ｏを必要とする各ネツトにこれ
らのグループからのＩ／Ｏが割当てられる。１つ
のネツトに１つのＩ／Ｏが割当てられているとき
は、そのＩ／Ｏは配線可能を決定するため全ての
コスト計算［式(3)参照］で使用される。 これは第４９図で概説したステツプを完了させ
る。実サイズ・モデルのための配置最適化を第５
３図に示すステツプで続ける。そのステツプは分
散（ブロツク221）、繰返し改善（ブロツク222）、
最終的配置のための情報発生（ブロツク226）を
含む。これらの各ステツプは以下に詳述する。 第５３図において、空スペースを分散するため
の構成要素の分散（ブロツク221）は適合手順を
使用する場合にのみ実行される。この分散技法は
上記で説明した。配線可能性解析を行なつて交差
カツト等を評価する。リニヤ割当て中に割当てら
れたＩ／Ｏ場所を使用する。 次に繰返し改善を使用する（ブロツク222）。型
式１及び型式２の交換を１度マクロ・モデル最適
化中に使用する。これは比較的小さい構成要素が
以前のステツプで導出され（第４９図）、配置は
拡張されたネツト・リスト及びＩ／Ｏ割当てに基
いて最適化されなければならないので実行され
る。各回の交換の後Ｉ／Ｏがリニヤに割当てられ
る。 再び第５３図を参照すると、最終ステツプ（ブ
ロツク226）は第１図で説明された後続ステツプ
で使用されるべき最終的出力データ・セツトに関
する情報を発生するステツプである。出力フアイ
ルは横列及び縦欄場所、各構成要素に対する回転
コード、Ｉ／Ｏを必要とする各ネツトに関連した
物理的Ｉ／Ｏ場所より成る。この情報は配置に基
づく回路板配線のために、及び回路板上に構成要
素を配置するのに使用される自動又は手動挿入に
使用される。 ［発明の効果］ 以上の通り、次レベルの電子的パツケージ上に
複数の異なつたサイズの電子的素子の最終的配置
を形成する素子配置プログラムについて説明し
た。本発明の素子配置プログラムは、得られる最
終的配置が構成要素適合性及びデザイン・ルール
に対する順応性の点で最適であり、それと同時に
素子の数が多いにもかかわらず最終的配置がコン
ピユータ稼動時間に関して効率的に得られる点で
従来の素子配置プログラムよりも優れている。最
適配置及びコンピユータの使用効率の両者が上述
の多重ステツプ方式の結果として得られる。何故
ならばこの素子配置プログラムは素子の全ての寸
法的な特徴を１度に好慮する必要がないからであ
る。つまり３段階技法の例では３度に分けて先ず
単位モデル段階で素子の寸法的特徴を無視し、次
にマクロ・モデル段階で寸法的特徴を大まかに考
慮に入れ、最後に正確な寸法的特徴を最終的モデ
ル段階で考慮に入れた。 全ての要因を１度に考慮に入れて処理しない
で、複数の段階に分けて逐次的に最適化するとい
う本発明の基本的な考え方からすれば、上記実例
の３段階技法ばかりでなく、２段階技法でも配置
の改善及びコンピユータ利用効率の改善の点で同
様な効果が得られることになる。かくて、例え
ば、寸法的特徴を大まかに考慮するマクロ・モデ
ル段階と実サイズ・モデル段階の２段階、又は寸
法的特徴を無視する単位モデル段階と実サイズ・
モデル段階の２段階を採用しただけでも、３段階
技法ほど効果的ではないがそれでも複数の段階に
分けたことにより従来の一段階技法よりも著しい
改善効果が得られる。 本発明は異なつたサイズの電子的素子を次レベ
ル電子パツケージ上に配置する例を使つて説明さ
れたが、複数個の相互に関連した素子を予定のア
レイの枠内で構造的パターンにまとめることを必
要とする種々の分野で応用可能であり、同様な効
果を期待することができる。

【図面の簡単な説明】

第１図は本発明に従う素子配置プログラムのあ
らましを示す図、第２図は本発明の方法をブロツ
ク16として含んだコンピユータ・エイデツド・デ
ザイン・システムの全体図、第３図は回路板及び
その上の素子位置を示す図、第４図はタイル割付
けを示す図、第５図は回路板上の相互接続を示す
図、第６図は本文中の第１表と共にネツト・リス
トを示す図、第７図は予定の電圧供給点を有する
回路板の図、第８図は第２表と共に配線チヤネル
の数及び場所を示す図、第９図は予め割当てられ
た入出力点、予め配置された構成要素、テスト・
ポイント列、及び留保領域を有する回路板の図、
第１０図は単位及びマクロ・モデルを形成するた
めの詳細ステツプ図、第１１図は単位及びマクロ
のモデル化概念を示す図、第１２図は第４表及び
第５表の例に対する単位及びマクロ・モデル回路
板を示す図、第１３図は小さい構成要素を取除い
た第６図のネツト・リストの図、第１４図はクラ
スタ化及び並べかえの詳細ステツプ図、第１５図
は相互接続された構成要素のグループを示す図、
第１６図は第11表と共に構成要素のグループを接
続するネツトを示す図、第１７図は第１図のブロ
ツク23のステツプの詳細図、第１８図は第１７図
のブロツク81のステツプの詳細図、第１９図及び
第２０図は２倍にされた単位サイズ回路板の図、
第２１図は第14表と共に単位サイズ構成要素の初
期配置を示す図、第２２図は単位サイズ構成要素
のずらされた配置の図、第２３図、第２４図、第
２５図はチヤネル供給量の計算を示す図、第２６
図は重ねの概念図、第２７図は重心の計算を示す
図、第２８図は繰返し改善のための交換プロセス
を示す図、第２９図は単位モデルの最終最適化配
置図、第３０図は２倍サイズ・マクロ・モデル・
イメージの図、第３１図はマクロ・モデル初期配
置の場合発生詳細図、第３２図、第３３図は第15
表と共に単位モデルからマクロ・モデルへの拡大
を示す図、第３４図は第16表と共にマクロ・モデ
ル構成要素の仮の出発場所を示す図、第３５図、
第３６図は重なりを除くための構成要素のずらし
を示す図、第３７図、第３８図はマクロ・イメー
ジ上への構成要素のマツピングを示す図、第３９
図はマクロ・モデル構成要素の最終的配置を示す
図、第４０Ａ図、第４０Ｂ図、第４０Ｃ図は繰返
し改善時のコスト、チヤネル交差、交差カツト総
数の計算を示す図、第４１図は実モデル初期配置
のための場所発生を示す図、第４２図は第17表と
共にマクロ・モデルの実サイズ・モデルへの拡大
を示す図、第４３図は回路板上の格子点に対する
領域割当てを示す図、第４４図、第４５図、第４
６図は実サイズ構成要素の２次元マツピングを示
す図、第４７Ａ図、第４７Ｂ図は構成要素の挿入
図、第４８図は構成要素の挿入を行なうステツプ
を示す図、第４９図は実サイズ・モデルの最適配
置のためのステツプ図、第５０図は実サイズ構成
要素の仮の配置を示す図、第５１図は実サイズ構
成要素の最終的配置図、第５２図は全ての構成要
素を配置した仮の配置図、第５３図は第４９図の
後続ステツプを示す図である。 ２１……構成要素及び回路板の単位モデル及び
マクロ・モデルを形成、２３，２４……配置最適
化（単位サイズ及びマクロ・サイズ）、２６……
配置最適化（実サイズ）。

Claims (1)

1. 【特許請求の範囲】 １ 予定の相互接続条件を有する複数個の異つた
   サイズの素子を素子位置アレイ中の素子位置にコ
   ンピユータを用いて情報処理することにより割当
   てるための、下記(イ)〜(ニ)のステツプより成る素子
   位置割当て方法。 (イ) 上記複数個の異つたサイズの素子及び上記素
   子位置アレイの夫々縮小サイズ・モデル（例え
   ば単位サイズ・モデル、マクロ・サイズ・モデ
   ル）及び実サイズ・モデルを形成するステツ
   プ。各縮小サイズ・モデル素子は縮小されたサ
   イズを有し、各実サイズ・モデル素子は上記複
   数個の異つたサイズの素子のうちの相当する素
   子と同じサイズを有し、縮小サイズ・モデル・
   アレイはすべての縮小サイズ・モデル素子を受
   入れるのに十分な大きさを有し、実サイズ・モ
   デル・アレイは上記素子位置アレイのサイズと
   同じサイズを有する。 (ロ) 上記予定の相互接続条件に従つて、縮小サイ
   ズ・モデル・アレイ上の素子位置に上記縮小サ
   イズ・モデル素子を割当てるステツプ。 (ハ) 割当てられた縮小サイズ・モデル素子を、上
   記実サイズ・モデル・アレイ上の相当する位置
   に割当てられる相当した実サイズ・モデル素子
   と置換するステツプ。 (ニ) 上記実サイズ・モデル・アレイ上の上記実サ
   イズ・モデル素子に割当てられた位置を、実サ
   イズ受入れのため再整理するステツプ。