JPH04316151A

JPH04316151A - パス遅延を最小化しマシン・サイクル・タイムを最適化する方法

Info

Publication number: JPH04316151A
Application number: JP3350669A
Authority: JP
Inventors: James J Curtin; ジェームス・ジョセフ・カーティン
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1990-12-21
Filing date: 1991-12-12
Publication date: 1992-11-06
Also published as: EP0493294A3; US5237514A; EP0493294A2

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は集積回路パッケージ内に
おける回路間のパス遅延の最小化に関し、更に詳しくは
、パッケージ内における回路の配置をパス遅延臨界関数
として最適化することにより回路間のパス遅延を最小化
し、マシンのサイクル・タイム及び性能を改善するもの
である。

【０００２】

【従来の技術】複雑なマシンのスピードは一般的に電子
部品間を渡る電気信号の時間遅延により決定される。あ
るスピードのマシンの設計プロセスにおいては、臨界パ
ス（クリティカル・パス）に特に注意が払われる。なぜ
なら、これらはマシン・サイクルを決定し、マシンの実
行スピードを定義するからである。回路の性能を改善す
ることによりマシン・サイクルを最小化する試みは、そ
れだけではより高速なマシンを保証しない。レイアウト
に関する他の考慮（関数的な回路遅延とは独立）、例え
ば、チップ或いはフロア設計、パーティショニング（区
分）、配置及び配線手順などがマシン設計の重要な役割
を演ずる。その結果、コンピュータのマシン・サイクル
を制限する大きな要素である過度な遅延を有する少ない
数のデータ・パスを発見することは珍しくはない。配線
容量及び抵抗及び信号の伝搬距離を減少するようにデー
タ・パス長を最小化し、データ・パスを最適化するため
に、これまで設計者による相当な努力が払われてきた。

【０００３】複数の相互接続されたブロックにより構成
される論理関数がどのように構成パス、例えば信号パス
、マシン・パスなどに分解され、また各パスにおける相
対的パス遅延の極値の決定がなされるかの例は、米国特
許第４２６３６５１号で述べられている。

【０００４】別の例、例えば米国特許第４５６４９４３
号では、設計の特徴付けを支援するために遅延パスが極
値により強調され、設計が硬直化する。しかし、全体的
なタイミングの最適化のための試みは取られていない。

【０００５】米国特許第４６９８７６０号では、実際に
異なる論理ブロック・タイプの選択を通じて回路ブロッ
クを変更することにより、信号タイミング遅延の最適化
に至っている。この方法は配置及び区分方法によるタイ
ミングの最適化にはふれていない。

【０００６】全ての可能なブロック配置の置換スペース
を開拓する発見的（ｈｅｕｒｉｓｔｉｃ）技術は、“コ
スト”（ｃｏｓｔ）或いは“目的　”（ｏｂｊｅｃｔｉ
ｖｅ）関数と称されるガイド或いは目的指向メカニズム
を使用することにより、試作及びエラー調査を行わなけ
ればならない。これまでに“コスト”関数を最小化した
いくつかの出版物が発行された。

【０００７】例えば、Ｓ．Ｋｉｒｋｐａｔｒｉｃｋ、Ｃ
．Ｄ．Ｇｅｌａｔｔ、及びＭ．Ｐ．Ｖｅｃｃｈｉによる
“Ｏｐｔｉｍｉｚａｔｉｏｎｂｙ　Ｓｉｍｕｌａｔｅｄ
　Ａｎｎｅａｌｉｎｇ”Ｓｃｉｅｎｃｅ、Ｖｏｌ．２２
０、Ｎｏ．４５９８、ｐｐ．６７１−６８０　がある。ここでは統計的なメカニクスと組み合わせ的最適化の間
の関係に着目している。ここでは固体へのアニーリング
（ａｎｎｅａｌｉｎｇ　：焼きなまし）との強い類似に
ついて述べており、非常に大きく複雑なシステムの特性
を最適化するためのフレームワークを提供する。このア
プローチでは初期配置に対する組立て配置アルゴリズム
（Ｃｏｎｓｔｒｕｃｔｉｖｅ　Ｐｌａｃｅｍｅｎｔ　ａ
ｌｇｏｒｉｔｈｍ）を公式化しておらず、また特定の臨
界パスのタイミングの最適化及びパス・セグメントの幾
何学的制限について述べていない。更に、初期条件、例
えば区分境界、最終マシンのモデル化及び最適化などに
要求される仮定を定義するための相互的ガイダンスを提
供しない。

【０００８】Ｒ．Ｍ．Ｋｌｉｎｇ及びＰ．Ｂａｎｅｒｊ
ｅｅによる“ＥＳＰ：　　Ｐｌａｃｅｍｅｎｔ　ｂｙ　
Ｓｉｍｕｌａｔｅｄ　Ｅｖｏｌｕｔｉｏｎ”ＩＥＥＥ　
Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒ−
Ａｉｄｅｄ　Ｄｅｓｉｇｎ　ｏｆ　Ｉｎｔｅｇｒａｔｅ
ｄ　Ｃｉｒｃｕｉｔｓ　＆Ｓｙｓｔｅｍｓ、１９８９、
Ｖｏｌ　８、Ｎｏ．３、ｐｐ．２４５−２５６では、前
に参照したものと同様な方法を開示しているが、ここで
は異なる発見的（ｈｅｕｒｉｓｔｉｃ）アルゴリズムを
使用している。これはペア・スワッピング（Ｐａｉｒ　Ｓｗａｐｐｉｎ
ｇ）　に対立する複数ブロックの再配置である。これは
セルの相互接続長を効果的に最小化する進歩的なプロセ
スをシミュレートする方法ではあるが、前述のアプロー
チと同様な制限を含む。

【０００９】Ｊ．Ｐ．Ｃｏｈｏｏｎ及びＷ．Ｄ．Ｐａｒ
ｉｓによる“Ｇｅｎｅｔｉｃ　Ｐｌａｃｅｍｅｎｔ”Ｉ
ＥＥＥ　Ｉｎｔｌ．Ｃｏｎｆｅｒｅｎｃｅｏｎ　Ｃｏｍ
ｐｕｔｅｒ　Ａｉｄｅｄ　Ｄｅｓｉｇｎ、１９８６、ｐ
ｐ．４２２−４２５　では、前述の２つのアプローチと
同様であり、やはり制限を有する。

【００１０】Ｋ．Ｊ．Ａｎｔｒｅｉｃｈ、Ｆ．Ｍ．Ｊｏ
ｈａｎｎｅｓ及びＦ．Ｈ．Ｋｉｒｓｃｈ　による回路及
びシステムに関するＩＥＥＥ国際シンポジウムにおける
“Ａ　ｎｅｗ　Ａｐｐｒｏａｃｈ　ｆｏｒ　Ｓｏｌｖｉ
ｎｇ　ｔｈｅＰｌａｃｅｍｅｎｔ　Ｐｒｏｂｌｅｍ　ｕ
ｓｉｎｇ　Ｆｏｒｃｅ　Ｍｏｄｅｌｓ”、Ｊｕｎｅ　１
９８２、ｐｐ．４８１−４８６　では、シミュレート・
アニーリング法（　Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌ
ｉｎｇ）においてペア・スワッピングを使用するＦｏｒ
ｃｅ　モデルを開示しているが、前述の全てのケースを
繰り返す結果に至っている。コスト関数は、相互接続関
係を平衡が達成されるまでのブロック間の引斥力関数と
してモデル化することに基づいている。ここでも同様な
制限が見い出される。

【００１１】Ｙ．Ｇ．Ｓａａｂ及びＶ．Ｂ．Ｒａｏによ
る第２７回　Ｄｅｓｉｇｎ　Ａｕｔｏｍａｔｉｏｎ　Ｃ
ｏｎｆｅｒｅｎｃｅ、１９９０、ｐｐ．２６−３１“Ｓ
ｔｏｃｈａｓｔｉｃ　Ｅｖｏｌｕｔｉｏｎ：　ＡＦａｓ
ｔ　Ｅｆｆｅｃｔｉｖｅ　Ｈｅｕｒｉｓｔｉｃ　ｆｏｒ
　ｓｏｍｅＧｅｎｅｒｉｃ　Ｌａｙｏｕｔ　Ｐｒｏｂｌ
ｅｍｓ”　はシミュレート・アニーリング法の場合より
もより早い解決結果及びより良い品質を求めている。こ
れはコスト関数による評価を基本とするサバイバルにと
って適切と見なされる状態において原則的に作用する。このアルゴリズムは、変更がサバイバルにとって不適切
と見なされると、提案されるブロック移動のバックトラ
ッキング（ｂａｃｋ　ｔｒａｃｋｉｎｇ）　を含む。再
びここで前述同様の制限が発見される。

【００１２】ここで今まで参照された全ての発行物は、
全体的に、マシン・アーキテクチャ内のネットの統合的
な配線或いは容量を最小化することにより、より高速な
マシン結果を達成しようと試みている点が重要である。従って、ある信号パスがいかに臨界的であるか、或いは
これら“ネット・セグメント”の幾何学的構造に基づい
て、ブロック配置の優先性を決定するための系統的な処
置は取られていない。また、前述のアプローチはどれも
、人間による決定のプロセスを支援するための初期配置
戦略或いはガイダンスを提供しない。すなわち、同プロ
セスにおいて、区分及び入出力制限を含む判断は、配置
方法が取れる範囲外に存在する初期条件を強要する。従って、最適化を実行するアルゴリズムが総合配線、総
合容量、或いはその他の総合的パラメータに基づく場合
には、より高速なマシンを保証することはできない。あ
るものは総合配線或いは容量が最小となる配置シナリオ
に到達するであろうが、結局これはより多くの配線或い
は容量を有する他の配置よりも更に遅いものに終わって
しまうことであろう。これはマシンスピードが配線或い
は容量の最大量によってではなく、最長のパスにより制
限される場合に発生する。

【００１３】現在、最も発見的な配置アルゴリズムは、
前述されたシミュレート・アニーリング法及びジェネテ
ィック配置方法（Ｇｅｎｅｔｉｃ　Ｐｌａｃｅｍｅｎｔ
）　において見られる種々の“コスト”及び“目的”関
数と共に作用する。 “Ｍｉｎ−Ｃｕｔ”　などでは、知能化配置により配線
の込み合い及びチャネル競争を最小化する試みをしてい
る。その他の例、例えば“Ｂｏｕｎｄｅｄ　Ｒｅｃｔａ
ｎｇｌｅ”、“Ｃｏｎｃｅｎｔｒｉｃ　Ｃｉｒｃｌｅ”
及び“Ｐｏｓｉｔｉｏｎ　Ｏｒｉｅｎｔｅｄ”　では、
総合配線或いは容量を最小化することによりマシン・サ
イクル及び性能を改善する試みが行われている。これら
のタイミング指向関数は、全てがネット指向であり、任
意のネットの全セグメントを１つのネット・エンティテ
ィとして取り扱う点で共通ファクタを共用する。

【００１４】

【発明が解決しようとする課題】本発明の第１の目的は
、効率的且つ経済的にコンピュータの全ての機能ブロッ
クを配置し、最小サイクル・タイムを達成し、マシンＭ
ＩＰＳを改善或いは卓越することである。好適には、こ
れらブロックは非常に多くのブロックを含む。

【００１５】本発明の別の目的は、ロング・パス及びシ
ョート・パスの制限範囲内においてパス遅延を最適化し
サイクル・タイムを最小化するための“組立て初期配置
法のシード”（Ｃｏｎｓｔｒｕｃｔｉｖｅ　Ｉｎｉｔｉ
ａｌ　Ｐｌａｃｅｍｅｎｔ　Ｓｅｅｄ）を生成する方法
を提供する。

【００１６】本発明の別の目的は“機能作用”（ｆａｃ
ｔｉｏｎａｌ　ｗｏｒｋ）遅延（例えば、論理ブロック
遅延）と“通信”遅延（例えば配置、配線等により指定
されるブロック間の配線接続遅延）との組み合わせ結果
を最適化することにより、サイクル・タイムを改善する
方法を提供する。

【００１７】更に本発明の目的は、臨界パス（クリティ
カル・パス）及びマシン・サイクル・タイムの最小化を
重視する複合臨界パスを通じてネット評価を実施するこ
とにより、“パス・バンドリング”（Ｐａｔｈ　Ｂｕｎ
ｄｌｉｎｇ）　を避ける“コスト”関数を生成すること
である。

【００１８】更に本発明の特定の目的は、前述のシミュ
レート・アニーリング法、ジェネティック配置方法（Ｇ
ｅｎｅｔｉｃ　Ｐｌａｃｅｍｅｎｔ）、及びシミュレー
ト発展法（ＳｉｍｕｌａｔｅｄＥｖｏｌｕｔｉｏｎ）　
と同様に、改善された発見的配置アルゴリズムを提供し
、最適論理ブロック配置を達成することである。

【００１９】更に本発明の目的は、設計の最適化プロセ
スにおけるより良い人間の理解（ｈｕｍａｎ　ｕｎｄｅ
ｒｓｔａｎｄｉｎｇ）及び反復改良（ｉｎｔｅｒａｃｔ
ｉｖｅ）への参加を促進することである。更に詳しくは
、配置手順の範囲外に存在する初期条件に関する知能的
決定を促進するものである。

【００２０】

【課題を解決するための手段】本発明は、パスの臨界及
び各パスにおけるスラック（ｓｌａｃｋ）、　及びセグ
メント数（すなわちブロック間の相互接続）により規定
される制限自由度を同時に指定するブロック配置を特別
に優先化することにより、マシンスピードを最適化する
。本発明はブロック配置を優先化する決定論的プロセス
を使用し、初期ブロック配置戦略及びタイミング要求を
基本とする回路グループの“階層的ネスティング”を提
供する。この階層的ネスティングは、任意の入出力制限
内に区分境界を設定するために要求される人間の決定プ
ロセスを支援する。

【００２１】更に、本発明は各ネット・セグメント・メ
ンバをパス重み付けエンティティ（ｐａｔｈ−ｗｅｉｇ
ｈｔｅｄ　ｅｎｔｉｔｙ）として扱うことにより新たな
“コスト”関数を提供し、ブロック配置を移動すること
による優先化されるパス効果に基づいて判断を下す。

【００２２】本発明は、マシンを構成する全ての“ネッ
ト・セグメント”を識別し、これらの相対的重要性に基
づきこれらを優先化することにより、パス遅延を最小化
しマシン・サイクルを最適化するものである。すなわち
、相対的なネット・セグメントの臨界に基づき、最終的
な最適構成に近い初期構成を達成する方法；事前に決定
された相対的なネットセグメントの臨界に基づき、これ
らネット・セグメントに対してコスト関数を割り当てる
ことにより、初期の構成を最終的な最適構成に改善する
方法；コスト関数の使用により、発見的方法による改善
された構成を達成する方法を含む。

【００２３】

【実施例】コンピュータのサイクル・タイム及び性能を
改善するために、回路間のパス遅延を最小化する概略的
概念は提案される方法論を大きく２つに細分化すること
によりよく理解される。すなわち、１）パス定義の初期
近似（ｉｎｉｔｉａｌａｐｐｒｏｘｉｍａｔｉｏｎ）、
及び２）定義されるパスの最適化である。

【００２４】初期近似単一のデータ・パスの過度な遅延はマシンのサイクル・
タイムを制限する。その結果、総計的（Ａｇｇｒｅｇａ
ｔｅ）　“コスト”或いは“目的”関数（例えば、“総
合配線”の最小化）の解を最適化するための組み合わせ
的最適化技術は、サイクル・タイムを最小化する問題を
直接的には指摘しない。低い総和値及び低い平均値を有
し、特有でない２或いは３個のシグマ・メンバを有する
パス遅延分布は、高い総和値及び公称値を有し、より小
さな偏差及びより短い“最長パス”を有する分布よりも
非効果的であるため、“総合パス遅延”などの目的関数
では不適当となる可能性がある。一般的には、“総合配
線”長、従って“平均パス遅延”を同時に最小化するこ
とにより、より早いサイクル・タイムが得られ、また知
能的変更によりこの規則に違反することによって、より
高速なサイクルが生成できる可能性がある。

【００２５】論理ブロック遅延（例えば、パスの“機能
作用”遅延を与えるための設計）を変更することはでき
ないものと仮定すると、設計の柔軟性に関する残りの領
域は、配置及びルーティング（ｒｏｕｔｉｎｇ）等によ
り指定される“ネット・セグメント”遅延（“通信遅延
”とも称される）である。従って、配線長の柔軟性は次
のように表現できる。サイクル・タイム　−　機能作用遅延　＝　パス・スラ
ック従って、臨界パスに対しては、配線遅延　≧　パス・スラックとなり、また高速パスに対しては、配線遅延　≧　レース・タイム要求となる。

【００２６】“平均化”技術はパス全体の統合的或いは
累積的な振舞いを測定し、この問題に対し推論的に関与
するに過ぎない。総計的なパスの振舞いはサイクル・ス
ピードを指定せず、最も遅いパスだけがこれに関与する
。従って、選択される組み合わせ的最適化技術、例えば
シミュレート・アニーリング法、ジェネティック配置法
、シミュレート発展法などのいずれであるにしろ、最適
化“目的パラメータ”（ｔａｒｇｅｔ　ｐａｒａｍｅｔ
ｅｒ）の慎重な定義を必要とする。

【００２７】最適化設計に至る優先ブロック配置の処理
フローを図１に示す。ブロック１００の“パス定義の初
期化”は各マシン・パスに対する方程式の定義を含む。これにおいて、パス遅延は全ての機能ブロック・メンバ
遅延及び全ての“ネット・セグメント”遅延の総和に等
しい（図２Ａ）。パス定義にリストされる各機能ブロッ
ク・メンバに対し、適切なブロック遅延フィールドが検
索される。各“ネット・セグメント”メンバに対し、対
応するソース名及び宛先名（それぞれ“到来元”（ｃｏ
ｍｅ　ｆｒｏｍ）及び“行き先”（ｇｏ　ｔｏ）とも称
される）が変数としてリストされる。

【００２８】初期配置“シード”（ｓｅｅｄ）手順は最
終的な最適化の徹底的な、或いは複雑な、或いは高精度
な近似を要求しない。こうしたアルゴリズムは時間を費
やしまたコストを抑制しなければならないため、実際に
実施するには非現実的である。実施可能な“シード”解
法は、マシン・パス遅延目標に適合するブロック・ロケ
ーション調整に対し、目標のネット・スラックを達成す
る強力且つ単純な規則が考案されたときにおいてのみ成
功する。従って、計算が簡単であり、ブロックの配置及
び区分において、パスの相互作用要求及びネット・スラ
ック調整の複雑性を適切に反映する強力な規則が発見さ
れなければならない。

【００２９】従って、最終的目標はプロセスにおける最
も遅いパスの寄与を最小化し、配置補正（ｐｌａｃｅｍ
ｅｎｔ　ｃｏｍｐｅｎｓｔａｔｉｏｎ）によりパス全体
のスラック分布を引き締めることである。これはパスに
対するネット・スラックの寄与度に関するパス・スラッ
ク表現をするように、各パスに対する方程式を生成する
ことにより達成される。パス方程式のセットは“ネット
・セグメント”のスラック値に対して解かれ、これらの
値はシミュレート・アニーリング法、シミュレート発展
法、及びジェネティック配置方法などの方程式に対する
初期配置シード位置を構成するために使用される。この
方程式は“目的パラメータ”すなわち臨界パス上の最小
スラックを強調するパラメータを慎重にモニタする。パ
ス方程式は次のようになる。ｙ１＝ｋｘ１＋ｋｘ２＋ｋｘ３＋……＋ｋｘｎここで、
ｙはパス・スラック、ｘはネット・セグメント・スラッ
ク、ｋは寄与或いは存在ファクタである。

【００３０】従って、方程式のセットは全てのパスを表
現するように生成される。ｙ１＝ｋｘ１＋ｋｘ２＋ｋｘ３＋……＋ｋｘｎｙ２＝ｋ
ｘ１＋ｋｘ２＋ｋｘ３＋……＋ｋｘｎｙ３＝ｋｘ１＋ｋ
ｘ２＋ｋｘ３＋……＋ｋｘｎ：ｙｎ＝ｋｘ１＋ｋｘ２＋ｋｘ３＋……＋ｋｘｎ

【００３
１】ここで各パス・スラックは“ネット・セグメント”
メンバ長の関数として表現される。Ｓ１＝ｆ（ＮＳ１＋ＮＳ３＋ＮＳ７＋ＮＳ８＋ＮＳ１２
）ここでＳ１はパス１に対するパス・スラックであり、
ＮＳ１は“ネット・セグメント”１などであり、以下に
示すように各“ネット・セグメント”をそのソース・ブ
ロック及び宛先ブロックに関し表現することにより与え
られる。ＮＳ１＝Ａ／Ｂ、ＮＳ２＝Ｂ／Ｇ、ＮＳ３＝Ｇ／Ｆ、Ｎ
Ｓ４＝Ｆ／Ｎ、ＮＳ５＝Ｎ／Ｒ従って、Ｓ１はＳ１＝Ａ／Ｂ＋Ｂ／Ｇ＋Ｇ／Ｆ＋Ｆ／Ｎ＋Ｎ／Ｒとなる
。

【００３２】この方程式のセットの解はネット・セグメ
ント当たりの遅延或いはスラック寄与度を提供し、これ
は全てのパス遅延を目標値に近づけるように調整する。ネット・セグメント当たりの遅延ファクタは、シミュレ
ート・アニーリング配置アルゴリズムのためのブロック
配置タグ（ｔａｇ）　に変換されうる。連立方程式のマ
トリクスは、そのｘ次元がマシンのブロック数に等しく
、ｙ次元がマシンのパス数に等しいという点で大きなも
のとなる。一般的にはこれらの数値は非常に大きい。

【００３３】Ｒｅｎｔの規則は、典型的システムにおけ
る回路が２次元或いは３次元の空間に組み込まれる場合
は、これらはショート・レンジの相互接続により接続さ
れることを示している。

【００３４】Ｒｅｎｔの規則によれば、マトリクスはパ
ス・スラックの総計遅延だけにより制限を受ける個々の
自由度を有する多くのネット・セグメントを含み（パス
内におけるネット・セグメント遅延の総和はスラック以
下である）、１つ或いはそれ以上の同一のセグメントの
相互的共用により他のパスをピンニング（ｐｉｎｎｉｎ
ｇ）　するような相互作用が発生することは明らかであ
る。ピンニングが生じない場合は、相互作用を有さない
独立方程式のリストとなる。全てのパスが全てのネット
・セグメントを共用すれば、このマトリクスはフル（ｆ
ｕｌｌ）の状態となり、当業者により知られるところの
重複決定される回帰技法により解くことが可能となる。

【００３５】方程式のマトリクスは通常、特定の或いは
重複決定される近似解空間を生むことはできない。なぜ
なら、パスを結合する部分的ピンニングにも関わらず、
ネット・セグメントの配置において“作用自由度”（ｆ
ｒｅｅｄｏｍ　ｏｆ　ａｃｔｉｏｎ）　がさほど存在し
ないからである。しかし、スーパーコンピュータのアル
ゴリズムによりマトリクスのステップを操作しなくても
、“等区分”（ｅｑｕｉｐａｒｔｉｔｉｏｎ）　及び代
用となる技術により、配置シードを生成することは可能
である。

【００３６】ネット・セグメント遅延のみを残して全て
の“機能作用”遅延を消去すると（図１のブロック１０
１）、パス・スラックの目的が次に定義される。前述の
ように、パス・スラックはサイクル・タイムと全てのパ
ス・メンバ・ブロック遅延の総和との差として定義され
る。

【００３７】次のステップでは、リスト内の各パスに対
するパス・スラック定義に含まれるネット・セグメント
総数を決定することにより、“等区分”リストが作成さ
れ（ブロック１０２）、各パス・スラックをこの数に分
割する。他の分割方式も有効であり、例えば、非線形幾
何の制限を反映させＮ２／３　で割る方法なども考えら
れる。次に各ネット・セグメント及び等区分値に対する
フィールドを有するファイルが作成される。また、複数
のパスがブロック間の任意のネット・セグメントを通過
することができる。“等区分”期間中に各パスが独立に
分析されると、マルチパス・ネット・セグメントを通過
する各個別のパスのタイミング要求に基づき、このセグ
メントに対して異なる値が生ずる。次に、同じ名前を有
するネット・セグメントの複数の値に対して比較が行わ
れる。この比較は多重発生に対するリストを検索し、こ
れらの値を比較し、最も小さな値を受け入れることによ
って行われる。

【００３８】このようにして作成されるネット・セグメ
ントのリストには、各ネット・セグメントの名前が１度
だけ現れる。受け入れられた値は対応するネット・セグ
メント名と関連するフィールドに設定される。

【００３９】次のステップ（ステップ１０３）すなわち
“ネット・セグメント長階層の作成”では、“昇順”（
ａｓｃｅｎｄｅｎｃｙ）手順に従い、ネット・セグメン
ト・タイミング昇順リストを作成する。その際、ネット
・セグメントは個々の遅延値及び潜在的な長さの関数と
して優先順に並べられる。

【００４０】この手順の実行の間に、無関係或いは結合
関係の乏しいペアを互いに隣接して配置することを回避
するために、特別な注意が払われねばならない。更に、
“結合性”（ａｓｓｏｃｉａｔｉｖｉｔｙ）　を考慮せ
ずに、最初に全ての短遅延ネット・セグメントを配置す
るのは単純すぎる。これは互いに疎遠な相互接続関係し
か有さない短ネットを並置することにより、貴重な固定
資源を費やすことになる。従って、最初に密接関係にあ
るものをまとめ、“成長中心”（ｃｅｎｔｅｒ−ｏｆ−
ｇｒｏｗｔｈ）を設定することによりレイアウトを優先
化し、この中心の周囲の配置の広がりを定めることが有
利であるとされてきた。成長中心のための密接関係を設
定する“ブロック間距離”に基づく階層においては、元
来、知能性或いは可能性は存在しない。更に、階層的配
置に関する技術は、配置及び配線に対する単一の成長源
を意味する傾向がある。このようなアプローチが単一チ
ップにおける最適な解を提供できる可能性はなく、また
こうしたアプローチはマルチチップ区分関数にとっては
不十分である。以上により、単一の成長源ではなく、た
くさんのチップ、或いはチップ内におけるたくさんの成
長領域を表す複数の成長源を表現する配置シードが要求
される。この“スラック・ネット階層”はこうしたシー
ドを生成するために使用される。

【００４１】結合性による階層の変更ネット・セグメント・タイミングを適切に優先化した後
、多重ネスト化ネット・セグメントのリストが次のステ
ップ“ソリテア”（ｓｏｌｉｔａｉｒｅ）処理（図１の
ブロック１０４）で作成される。ここでは“結合性”の
観点から配置階層を変更する。ソリテア処理はネットの
“凝固”（ｃｏａｇｕｌａｔｉｏｎ）　を基本とする。 “ブロック間距離”階層における最短のネットからスタ
ートすると、ソリテア処理と類似の要領によりグループ
がコラム（ｃｏｌｕｍｎ）化される。２つのブロック（
ソース及び宛先）により構成される全てのネット接続は
１対の文字或いはシンボル（ｘ、ｙなど）により表され
る。各連続する入力と共に、次に示す質問が問われる。最初のシンボルがリストに現れているか？２番目のシン
ボルがリストに現れているか？

【００４２】これに対す
る答が（ｎｏ、ｎｏ）であれば、このペアは新たなリス
トにおける最初の入力となる。答が（ｙｅｓ、ｎｏ）或
いは（ｎｏ、ｙｅｓ）であれば、このペアは存在する照
合リストに追加される。答が（ｙｅｓ、ｙｅｓ）の場合
は、このペアは照合リストの中の１つに追加され、これ
ら照合リストは組み合わされる。

【００４３】この処理はネット・セグメント・ペアの（
ｙｅｓ、ｙｅｓ）判断を介して到来するネット長に至る
まで、互いに独立な複数のリストを生成する傾向がある
。いくつかのアプリケーションでは、リストが等しい長
さ或いは適切な数ではないかもしれない。このことはお
およそ同等なサイズ（チップなど）で複数の区分を要求
するケースにおいては特にあてはまる。こうした例では
、単純なネット凝固では不十分であり、更に知能性が要
求される。リストの知能的操作はブロック“格付け規則
”（ｒａｔｉｎｇ　ｒｕｌｅ）と同様、リストの組み合
わせ規則　（ｍｅｒｇｉｎｇ　ｒｕｌｅ）により達成さ
れる。これらは全て、当業者には容易に理解され使用さ
れよう。

【００４４】ソリテア処理における成長中心の急なリン
ク・アップは、“昇順”規則により調和される。成長中
心が回路数を計算するとき、これらはその半径が永久に
延長されて永久に拡大するポピュレーション領域として
視覚化される。グループ内のある部分とのネット接続に
よるこうしたグループの急なリンク・アップは、新たな
ネット・セグメントを要求し、このネット・セグメント
長は１つのユニットの半径範囲とグループＡ及びグルー
プＢの半径範囲の和との中間の値を取る（この地点では
、他のリンクはこれらの間に存在していないことを主張
しておく）。ネットがリストされ、それらのネット長に
関してランダムに処理されたとすると、２つの成長中心
の間の短いネット・セグメントは、これら２つの半径で
は不可能な地点で非常に小さなネット接続を要求する。昇順規則を使用することにより、ネット接続のリンク・
アップは幾何学的に要求されるより長い接続を同一順序
で提供する。

【００４５】範例これまでに定義された方法論を更に説明するために、図
２から図６が参照される。

【００４６】図２Ａは１３の相互接続されるブロックに
より構成される簡単な論理配置を示し、入力としてＩ１
、Ｉ２及びＩ３を、また出力としてＯ１、Ｏ２及びＯ３
を有する。各総合パス遅延はパス・メンバ・ブロック遅
延（機能遅延）とネット・セグメント遅延を含む。発明
的方法論の第１ステップである“パス定義の初期化”（
図１のブロック１００）では、クロック・サイクルにお
いて任意の作用機能を達成する全てのパスのリストを要
求する。入力及び出力は、示されるパスのサイクル開始
点及び終了点を表す。

【００４７】図２Ｂを参照すると、各パスの右にはこの
パスのブロック数が示されている。一定のサイクルにお
いて、各パスはパス内の各ブロックに関して単一のブロ
ック遅延で表されており、事前に定義されたスラックは
サイクル・タイムのバランスを取るために残されている
（図２Ｃ）。次のステップでは“機能遅延の除去”を要
求し（図１のブロック１０１）、図２Ｄで示されるよう
にネット・セグメント遅延だけを残す。ここでソース及
び宛先の変数により表される各ネット・セグメントに特
に注意を払う必要がある。

【００４８】“等区分”規則をより理解し評価するする
ために（図１のブロック１０２）、マトリクスはその行
数はパス数に等しく、また列数はネット・セグメント数
に等しく構成されている。このマトリクスの帰属要素は
、各“ピン・ネット・セグメント”（ｐｉｎｎｅｄ　ｎ
ｅｔ　ｓｅｇｍｅｎｔ）に対しては“Ｐ”が、また各“
フリー・ネット・セグメント”に対しては“Ｘ”が与え
られている（図２Ｅ）。等区分規則によれば、各スラッ
クを相当するネット・セグメント数で除算し（図２Ｆ）
、次に各ネット・セグメントは個々に結果として得られ
るネット・セグメント値を割り当てられる。

【００４９】等区分規則により得られる複数のネット・
セグメント遅延値は、次にこれらの中の最小の計算値が
各ピン・ネット・セグメントに対してセットされ、この
セグメントが現れる所は全てこの値が代用される（図２
Ｇ）。

【００５０】図２Ｈには各ネット・セグメントに対する
スラックがリストされている。

【００５１】ネット・セグメントは次に“昇順”規則に
より優先化される（図１のブロック１０３）。ここでは
ネット・スラック・シーケンスは値の低いものから順に
並べられる（図２Ｉ）。ブロックの実際の配置が全く同
一のネット・セグメント・スラック値となる場合には、
図２Ｊに示すパス遅延が生ずる。

【００５２】昇順規則に関する議論から、当業者にとっ
て重要な点は、予測されるパス遅延値ではなく、“等区
分”規則を理解すること、すなわちピン・ネット・セグ
メントに対して最小値を割当て、ネット・セグメント・
リストに対し昇順規則を適用することにより、最も臨界
的なネット・セグメント（すなわちブロック配置）を最
初に扱うように保証することを理解することである。こ
れはまた、パスが配置優先性及びそれぞれのタイミング
臨界に比例する注目を受けることを保証する。従って、
最も臨界的なネットに影響する中枢的ブロック配置は最
も優先される。

【００５３】更に詳しくは、各ネット・セグメントはそ
れに付随する遅延ファクタを有し、これは配置シードを
生成する“ブロック間距離”階層を生成するために使用
される。これにより典型的なブロックが図２Ｋのように
表され、ここで図中に示された番号は長さの単位或いは
遅延の単位を示す。

【００５４】シード配置は全ての短ネット・セグメント
遅延を最初に配置することからスタートする。従って、
これらのネットにより接続されるブロックは最初にロー
カルにシードされる。より長い長さのセグメント・メン
バ・ブロックが次に配置される。単一ブロックに対する
長短要求間で発生する衝突は、最小エネルギを達成する
ためのアニーリング・アルゴリズムにより指摘される。この場合目標ネット遅延と実際の配置遅延との差が最小
エネルギ達成の対象である。

【００５５】図３Ａは前述の昇順規則によりスラック値
の増加順にネット・セグメントを配置した新たな縮小リ
ストである。ここから複数の成長中心のフォーメーショ
ンを導く自然な区分を定義するためにソリテア処理が適
用される（図３Ｂ）。

【００５６】この処理の実行完了に基づき、ネスト化階
層構造を有する“優先配置”が形成される。

【００５７】これによりＣＰＵ論理集団の成長と共に、
増大（ａｃｃｒｅｔｉｏｎ）成長及び集合（ａｇｇｒｅ
ｇａｔｉｏｎ）　の全ての処理が再構築及び分析される
（図４）。ネスト化階層は自然的境界選択の成長へのガ
イドとなり、同時に入出力数及び任意の区分選択の集積
サイズに関する必要な情報を提供する。

【００５８】成長中心での増大及び成長中心間での集合
に関するダイナミックなシーケンスが得られ、コード化
構造により維持される。成長中心が帰属化され、組み合
わせオペレーションがインデックス化階層に分類される
と、ロード・マップ或いは成長過程にある論理集団のツ
リー構造が現れる。

【００５９】昇順階層内のネスト化グルーピング（すな
わち成長中心）は成長過程の論理集団の進化の側面を明
らかにする。これは、特定のグループはこれらがセット
に組み合わされる最初の接続が完了するまで互いに独立
に成長する、という事実に基づく、ダイナミックな区分
化を象徴するものである。この点で、組み合わされたグ
ループは１つの大きなグループとして扱われる（図４）
。

【００６０】“昇順”シーケンス・リストはグループが
組み合わされる順序を提供する。ネスティング及びリス
ト・シーケンスは集合及び増大の履歴を提供する。

【００６１】インデックス化は２つの領域における“タ
イミング補正配置”（ｔｉｍｉｎｇｃｏｍｐｅｎｓａｔ
ｉｏｎ　ｐｌａｃｅｍｅｎｔ：ＴＣＰ）処理を支援する
。すなわち、１）区分。ツリー構造を有する階層レベル
が異なる区分戦略及び集積サイズに対するＩ／Ｏの相互
接続評価を行う。区分が変更されると、Ｉ／Ｏ相互接続
は自動的に変更され、境界の移動を反映する。全ての区
分されたエンティティの間の相互接続数は、チップ区分
及び配置に対する相互接続遅延要求と同様、Ｉ／Ｏ要求
信号を評価する上でも有効である。２）配置。グループ間配置の優先化は“ソリテア”及び
リンク・アップ処理により提供される。

【００６２】“ネスト化シーケンス”は図５を参照する
ことにより最も理解される。この図では成長順に区分さ
れるネット・セグメント階層の例が示されている（図５
Ａ）。これはインデックス化成長履歴（図５Ｂ）へと導
かれ、更にこれから多重ネスト化レベル（図５Ｃ）へ、
そして最終的に多重レベル及びこれらのレベルに対応す
るサブセットの表示へと展開される（図５Ｄ）。

【００６３】“成長中心”と呼ばれる長方形のブロック
は、パスの臨界タイミング要求及び結合性に基づく複数
の論理ブロック接続（すなわちネット・セグメント）の
セットを含む。

【００６４】“集合”はネット・セグメントが前述した
２つの独立な成長中心グループ内の論理ブロック・メン
バをリンクするとき発生する。この新たなネット・セグ
メントにより、２つのグループは突然リンクされ、ネス
ト化階層に組み合わされる。図５で示されるように、新
たなネット・セグメントはグループ１のブロックをグル
ープ４のブロックへリンクする。その結果、グループ４
はグループ１と組み合わされる。最後に、“増大”すな
わち存在する成長中心に新たにネット・セグメント・メ
ンバを付加する方法は、図４において長方形（成長中心
）で表されるブロック６及びブロック８の成長により、
象徴的に示されている。

【００６５】従って、図１のブロック１０６についてこ
れまで述べられてきたステップを基本とする、適切な初
期配置の開始方法が形成される。フロー図が示すように
、優先配置処理は最適な区分境界の選択に関する予備設
計評価を伴う。これらの選択はモデル及び新たに形成さ
れた優先配置階層に挿入される。

【００６６】次に、図１のブロック１０５について説明
すると、優先配置処理は最適な区分境界の選択に関する
予備評価を伴う。これらの選択は、ブロックの物理的配
置に頼ることなく新たな配置階層を形成することにより
考慮される。なぜなら昇順／ネスト化階層は幾何的配置
の決定に関わらずに、第１パスの控除を許可するからで
ある。これにより区分境界を欠く理想的な配置のモデル
化が可能となる。これは設計プロセスの分析のためのス
タート点としては特に適している。更に詳しくは、設計
者は２次元（平面）空間の制限内における配置の影響を
おおよそ評価することができる。予め定義されたｘ、ｙ
座標システムにおけるブロックのマスタ・グリッドの配
置は、ブロックに接続される各セグメントの遅延ファク
タを生む。これらのネット・セグメント遅延はパス遅延
につながる。従って、設計者はパス遅延分布のおおよそ
の感じをつかむことができ、平面的距離に関連する“フ
ライト時間”（ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ）違反を
評価できる。こうして、種々の区分境界の選択によるパ
ス遅延への影響を評価することができる。また、平面設
計の影響はこれらの区分から分離される。配置処理の完
了に際し、ネット・セグメント値が配置ファイルから検
索され、パス方程式に挿入され、実際の遅延を予測する
。

【００６７】図１のブロック１０９、１１０及び１１１
においてフィードバック・パスを参照すると、配置評価
（ブロック１０５或いは１０８）の結果により実際に取
られる手順の方向付けに依存して、種々の別の例を実施
することができる。区分が許可されると、一定のスラッ
クの縮小が以下に示す処理の結果起こる。１）区分境界選択であるブロックの各セットに対する、
特定な区分出力ドライバ遅延値の割り当て（注：ブロッ
クはチップ、モジュール、カードなどを表す。遅延特性
はドライバ或いはレシーバとして選択されるブロックを
考慮して変更される。）２）区分を次のレベルにリンクするネット・セグメント
に対する特定値の割り当て

【００６８】非区分パスの場合は、パス・スラックはセ
グメント・メンバ間で等分化され、配置に関する第１パ
ス優先近似を実施する。これは“等区分”近似と称され
、区分化パスの場合に対し変更を要求する。全てのネッ
ト・セグメント遅延はブロック間距離の関数ではあるが
、区分内のネット・セグメント分布と区分間のネット・
セグメント分布とは根本的に異なる。

【００６９】区分選択が内部ブロックを区分ドライバに
、またこれらのブロック遅延をドライバ遅延に自動的に
変更する手段が可能である。選択されるドライバ・ブロ
ックの変更遅延値は、新たなパス・スラック計算及び新
たなネット・セグメント昇順階層を許可する。新たなネ
ット・セグメント・リスト・シーケンスはソリテア処理
結果を変更し、新たな配置を招く。

【００７０】入出力ネット・セグメントにとって、新た
な遅延値が区分位置及び到来元／宛先マスタ・グリッド
座標結果に基づき計算される。この長さはモジュール・
ネット遅延乗算器に結合され、各パスの全てのメンバの
ネット・セグメント遅延及びブロック遅延に基づき、新
たなパス遅延値の生成を可能とする。

【００７１】図６Ａは非区分化パスを表し、機能ブロッ
クは互いに等しくセットされ、パス・スラックはいずれ
の区分にも無関係である。

【００７２】同じパスが図６Ｂに示されており、ここで
はスラック・パスが区分の結果縮小されている。追加の
遅延が区分ドライバに相当する機能ブロックに付加され
ており、この分パス・スラックは縮小される。

【００７３】オンチップ・ネット・セグメント分布の平
均距離はセル・ピッチにより測定される。また、チップ
間ネット・セグメント分布の平均距離はチップ・ピッチ
により測定される。

【００７４】図６Ｃは長さ（例えば伝達時間）の関数と
してのネット・セグメントの変化分布を示す。この曲線
は２つの集合を示し、一方はチップ内分布に相当するＭ
ｉ　を中心としており、他方はチップ相互間分布に相当
するＭｅを中心とする。

【００７５】図６Ｄを参照すると、非区分パスの場合に
、パス・スラックは（等区分規則適用の結果）全てのネ
ット・セグメント間で等分される。従って、総合ネット
・セグメント・スラックはまさにネット・セグメント数
により分割された総合スラックである。一方、区分パス
の場合は、（特別な回路に関連する遅延に相当する量だ
け総合パス・スラックが短縮された後）変更された等区
分化スラックはチップ間のことを考慮に加えて適切に変
更される。従って、より現実的なネット・セグメントの
トポロジを提供する。区分により種々のネット・セグメ
ントに割り当てられる過度なチップ間遅延の例において
は、許容不可能なほど小さい縮小スラックが残され、こ
れをパス上に残されたネット・セグメント間で分割され
なければならない。これは設計を無効なものとする。これは設計者が最適な分布を求めることにおいて非常に
効果的なツールになり得る。

【００７６】この点で、ネット・セグメントの優先性を
再計算するための要求が必要になり、“変更等区分”（
ａｌｔｅｒｅｄ　ｅｑｕｉｐａｒｔｉｔｉｏｎ）により
達成される。

【００７７】内部と外部のネット・セグメントの違いを
説明するための手段は、対応する内部ネット・セグメン
トの長さ（時間遅延）を概算する、外部ネット・セグメ
ントのための表現法を生成することである。従って、区
分境界ネット・セグメントは、内部ネット・セグメント
相当数として再表現される。これにより初期等区分処理
はより現実的なパス・スラック分配により実施される（
図６Ｄ）。こうして優先化される配置にとって、新たな
昇順階層が形成される。この優先化される配置はブロッ
クの物理的配置を伴わずに達成される。物理的配置が取
られていないときには、物理的配置のｘ、ｙ座標情報か
らその長さを決定する方程式により、実際のネット・セ
グメント遅延が計算される。

【００７８】再びブロック１１１を参照すると、ｘ、ｙ
非区分配置は区分によるほとんどの影響を含んでいる。非区分レイアウトのｘ、ｙ配置及び距離は、区分される
外部ネットが有するのと同一の距離に対応させることが
可能である。遅延の変更は主に次に示す要因による。１）有効パス・スラックを減少させるドライバ・ブロッ
クの遅延の増加２）チップがモジュール上において“ブリック−ウォー
ルド”（ｂｒｉｃｋ−ｗａｌｌｅｄ）されていない時の
チップ境界の追加距離これらは次のように表現される。境界　＝　チップ・ピッチ　−　チップ・サイズ

【００
７９】当業者にとっては明らかなように、区分化境界な
しで理想化配置をモデル化することが可能である。非現
実的ではあるが、設計過程を分析するにはすばらしいス
タート点である。これにより設計者は２次元（すなわち
平面的）空間の制限内において配置の影響をおおよそ評
価することができる。

【００８０】任意のｘ、ｙ座標システム内におけるブロ
ックの“マスタ・グリッド”配置は、これらブロックに
接続される各ネット・セグメントのタイミング遅延ファ
クタを生成する。これらのネット・セグメント遅延はパ
ス遅延を生成する。設計者はパス遅延分布のおおよその
感じをつかむことができ、平面的距離に関連する“フラ
イト時間”（ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ）違反を評
価できる。これにより、種々の区分境界の選択によるパ
ス遅延への影響を評価できる。このようにして、平面設
計の効果を区分の効果から分離することが可能となる。

【００８１】最適化：パス・スラック依存型コスト関数
前述のステップ（ブロック１００から１０６）による初
期物理的配置の完了により、フローは発明的方法論の最
適化の要求へと移行する。

【００８２】従来より組み合わせ的最適化の発見的な技
術が、設計空間内を探求する種々の“コスト”或いは“
目的”関数の使用により開発されてきた。多くの反復改
良技術は、“ダウンヒル”（ｄｏｗｎｈｉｌｌ）を導く
、すなわちコスト関数を改善する再配置だけを受け入れ
る評価基準を使用した。こうした探求は通常、局所的な
最適化に集中化され、大域的な最適化を達成することは
稀である。コスト関数の引き続く洗練によって、“ダウ
ンヒル”移動同様に“アップヒル”（ｕｐｈｉｌｌ）移
動を確率的に許容するようになり、局所的最小に固執し
ないアルゴリズム的処理を認めた。

【００８３】この技術の従事者はボルツマン（Ｂｏｌｔ
ｚｍａｎｎ）の統計的メカニクスにおけるアナログの容
認によるエネルギ概念を有利に使用した。こうして組み
合わせ的最適化及び統計的メカニクスを使用する通常の
反復改良技術では、任意の温度における全ての配置に対
し、ボルツマンの温度ファクタを均等に適用する。これ
により全てのブロック配置に対し均等な自由度を与える
ことができる。この自由度は温度が下がると次第に減少
し、配置は安定化する。

【００８４】この方法論の目的は、最長パスの自由度を
不均衡に制限し、同時により広い設計空間において非臨
界的ネットを操ることにより全体的な配置の自由度を最
大化する。これにより変更された基準が形成され、これ
においてはボルツマン比較はネット臨界に依存する。こ
うした基準においては、エネルギを減らす配置が容認さ
れるが、もしも取られた配置がエネルギを増加する場合
は、この容認はｅｘｐ（−Ｅ／ｋＳ）の形式をもつボル
ツマン関数の値よりも小さなランダム数の確率に基づく
。ここで新たな変数Ｓはパスに依存し、パスのスラック
の関数である。例えば、Ｓ　＝　Ｔ　ｘ　（ｃｙｃｌｅ　ｔｉｍｅ／ｓｌａｃｋ
）ここでＴは温度変数である。

【００８５】従って、更に制限されたネット、すなわち
より長い臨界的ネットに対してパス遅延を増加する配置
はおおよそ除去され、一方制限の緩いネットに対してパ
ス遅延を増加する配置はより高い確率で容認される。な
ぜなら、（臨界的ネットによりセットされる）サイクル
・タイムに影響を及ぼすことなく、これらの遅延を物理
的配置要求を収容する点まで増加させることは可能だか
らである。

【００８６】臨界に基づくこの優先方法論は平均パス遅
延（すなわち総合配線或いは総合容量）ではなく最長パ
ス遅延を最小化することを目的とする。一般的には、ロ
ング・パスは非常に数多くの機能ブロックを含むため、
パス定義は多くのネット・セグメントにより分割される
最小のスラック・タイムを生む結果となる。結果的に、
これらのパスは制限されたネット・セグメント長、及び
互いに近接するネット・セグメント数のために制限度の
高い配置自由度を有することになる。更に、配置自由度
は均等でないため、拡張は縮小よりも高い率で成功する
。従って、最小スラックを有する最長パスには配置上の
最も高い優先度が与えられる。

【００８７】この技術は、配置の相対的自由度（或いは
容認）がマシンを構成する全ての回路の全てのパス、ネ
ット・セグメントなどの臨界を基本とするため、大域的
（ｇｌｏｂａｌ）と見なされる（或いはマシン・ワイド
と称される）。

【００８８】パス・バンドリングの存在における最適化
ネットを本質的に検査されるエンティティとして扱うコ
スト関数の適用はパス・バンドリングを生成し、その時
パスのネット・セグメントはグループ化され、集合で分
析される。この変形は個別のパス識別されるネット・セ
グメントのセットを“ネット”と称される擬似遅延変数
に変換する。このアプローチの欠点は、特定のパス分析
能力を遅延の平均化技術へと変換してしまう点にある。

【００８９】臨界的パスのネット・セグメント要求は、
同一ネットの非臨界的ネット・セグメント・メンバの結
合された統計と共に分析される。こうして分析は更に理
論的に行われ、総合配線、ネット容量などは少なく維持
される。

【００９０】以前に紹介された好適な配置はパス依存型
であり、パス・スラック値に基づいて容認或いは妥当性
（ｇｏｏｄｎｅｓｓ）を測定した。これを成功に導くた
めに、ブロック配置を最適化するプロセスにおいて、分
析は複数パスにおける変更を含むことが必要である。組
合せ初期配置処理及びブロック配置階層において、これ
は問題ではなかった。なぜなら、配置臨界順序を指示す
る昇順リストはネット・セグメントに基づいたからであ
る。従って、ブロック配置処理中にパス効果を互いに分
離することは可能であった。

【００９１】配置最適化処理は最適化以前に、全ての試
験的ブロック及びネット・セグメント接続が既に配置さ
れているという点で異なる。従って、ブロック配置の変
更及び評価は移動されるブロックに接続される全てのネ
ット・セグメント（すなわち全ネット）に影響する。そ
の結果、単一のブロックの移動により多くのパス遅延が
同時に影響される。従って、ブロックの再配置の結果生
ずる正及び負のパス遅延インパクトの複合妥当性を分析
するための基準作りが必要となる。

【００９２】妥当性は下記に示す内容の組み合わせによ
り測定できる。１）最長パス及びサイクル・タイムの前回値に基づく比
較基準２）臨界に基づくパス依存の優先化

【００９３】妥当性は次に示すステップを取ることによ
り測量される。１）ネット・セグメント及びパスの観点からネット及び
ブロック変更を定義する。２）昇順リスト優先順すなわち昇順に基づく位置により
割り当てられるパス・スラック或いはネット・セグメン
ト臨界に基づく種々のリストの各パス及びネット・セグ
メントに対し、臨界値を割り当てる。３）最も臨界的なパスに最も重要なデジットが割り当て
られる２進数による重みインデックス（例えば２０、２
１、２２‥‥２ｎなど）により事前に定義された臨界値
をコーディングする。例えば、最も臨界的なネットはイ
ンデックス化重み２ｎを有し、最も臨界的でないネット
・セグメントはインデックス化重み２０を有する。４）２進数、例えば（１として定義される）“＋”は改
善された妥当性（すなわちより短いパスなど）を示し、
（０として定義される）“−”は妥当性の悪化（例えば
、より長いパスなど）を示すようにシンボル化する。５）複合パス結果を昇順２進数にコーディングし、２進
数変換の複合重みに基づき容認する。

【００９４】この技術は局所的と見られる可能性がある
。なぜなら、配置（或いは容認）の相対的自由度は、考
察中のネットに加わっているネット・セグメントだけに
基づく臨界（パス・スラック／ネット・セグメント・ス
ラック）に依存するからである。

【００９５】例として、３つのネット・セグメントによ
り構成されるネットを図７Ａに示す。ここでＮＥＴ１＝
ＮＳ（Ａ）＋ＮＳ（Ｂ）＋ＮＳ（Ｃ）

【００９６】３つ
の可能なパスが図７Ｂに示され、それぞれスラック、臨
界及び割り当てられるインデックス重みを有し、各パス
及び配置結果に対して“複合容認重み付け”を保証する
（図７Ｃ）。

【００９７】要約すると、タイミング補償配置及び区分
を提供し、有利に以下のことを生成する手段及び方法に
ついて述べてきた。１）“発見的”最適化技術のための組合せ初期配置２）
ネット・セグメントのタイミング臨界に基づき最小化さ
れるサイクル・タイムのための改善された“コスト”関
数３）マシン区分、ブロック配置、チップ幾何、パッケー
ジ構成などに対してなされる反復改善、干渉、及び意志
決定の容認による高速マシンの解法プロセスにおける知
能化手段

【００９８】本発明は特定の実施例を参照して述べられ
てきたが、当業者には理解されるように、前述の変更或
いは他の変更、例えばアニーリング及びジェネティック
処理におけるコスト関数定義の変更なども可能である。

【００９９】

【発明の効果】以上説明したように、本発明によれば、
マシンのサイクル・タイムを最小化しマシン性能を改善
することができる。

【図面の簡単な説明】

【図１】パス遅延を最小化しマシンのサイクル・タイム
を最適化するために、“組合せ初期配置のシード”を創
造し、“パス・スラック依存型コスト”関数を生成する
プロセスのフロー図である。

【図２Ａ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｂ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｃ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｄ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｅ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｆ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｇ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｈ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｉ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｊ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図２Ｋ】パス定義から始まり“ネット・セグメント”
階層（“昇順”規則）を形成する種々のステップの図解
例である。

【図３Ａ】“ソリテア”手順を介する“ネット凝固”例
を示す図である。

【図３Ｂ】“ソリテア”手順を介する“ネット凝固”例
を示す図である。

【図４】ネスト化レベルに至る成長順により区分される
レベル・サブセットを含むネット・セグメントの図例で
ある。

【図５Ａ】“集合”及び“増大”シーケンスを示す図で
ある。

【図５Ｂ】“集合”及び“増大”シーケンスを示す図で
ある。

【図５Ｃ】“集合”及び“増大”シーケンスを示す図で
ある。

【図５Ｄ】“集合”及び“増大”シーケンスを示す図で
ある。

【図６Ａ】区分化がスラック関数計算のファクタとなる
様子、及び別の任意の設計においてより効果的な評価を
提供することを示す図である。

【図６Ｂ】区分化がスラック関数計算のファクタとなる
様子、及び別の任意の設計においてより効果的な評価を
提供することを示す図である。

【図６Ｃ】区分化がスラック関数計算のファクタとなる
様子、及び別の任意の設計においてより効果的な評価を
提供することを示す図である。

【図６Ｄ】区分化がスラック関数計算のファクタとなる
様子、及び別の任意の設計においてより効果的な評価を
提供することを示す図である。

【図７Ａ】“パス・バンドリング”が存在する場合の最
適化プロセスにおける“妥当性”の測定方法例を示す図
である。

【図７Ｂ】“パス・バンドリング”が存在する場合の最
適化プロセスにおける“妥当性”の測定方法例を示す図
である。

【図７Ｃ】“パス・バンドリング”が存在する場合の最
適化プロセスにおける“妥当性”の測定方法例を示す図
である。

Claims

【特許請求の範囲】

【請求項１】パス遅延を最小化し、マシン・サイクル・
タイムを最適化する方法において、ａ）マシンを構成する全てのネット・セグメントを識別
し、その相対的臨界性により前記ネット・セグメントを
優先化し、ｂ）前記ネット・セグメントの相対的臨界に基づき最終
的最適構成の初期近似を達成し、ｃ）前記マシン内の前記ネット・セグメントに対しコス
ト関数を前記ネット・セグメントの相対的臨界の関数と
して割り当てることにより、前記最終的最適構成の前記
近似を改善し、ｄ）前記コスト関数を使用し、発見的手段により前記初
期近似を改善する構成を達成する、ことを特徴とする方法。
【請求項２】請求項１のステップｃ）において、前記初
期配置は最も臨界的な前記ネット・セグメントの電気的
パラメータを改善することにより実行されることを特徴
とする方法。
【請求項３】請求項１のステップｃ）において、前記初
期配置は最も臨界的な前記ネット・セグメントのタイミ
ング・パラメータを改善することにより実行されること
を特徴とする方法。
【請求項４】請求項１のステップｃ）において、全ての
前記ネット・セグメントの構成は任意のネットを構成す
る全てのパス及びネット・セグメントの階層的な臨界性
を評価することにより達成されることを特徴とする方法
。
【請求項５】請求項１のステップｃ）において、前記初
期配置はランダム手段により達成されることを特徴とす
る方法。
【請求項６】パス遅延を最小化し、マシン・サイクル・
タイムを最適化する方法において、ａ）ブロック遅延及びブロック間ネット・セグメント接
続に関して全てのマシン・パスに対するパス遅延方程式
のセットを生成し、ｂ）サイクル・タイム要求から前記パスの機能ブロック
の総遅延を減算することによりパス遅延スラックを生成
し、ｃ）各前記パス遅延スラックが前記ネット・セグメント
のソースタグ及び宛先タグに関して定義されるネット・
セグメント遅延ファクタの合計から成るように、全ての
マシン・パスに対する前記パス遅延スラックのセットを
表し、ｄ）等区分規則を適用することにより初期ネット・セグ
メント・スラックを概算し、ｅ）全てのマルチユースのピン・ネット・セグメントに
対する複数の値を有するリストから多重パス・ネット・
セグメントの最小遅延値を抽出し、該最小値を前記多重
パス・ネット・セグメントに対する単一値として使用し
、ｆ）全ての前記ネット・セグメントをスラック値の昇順
に並べ、ｇ）前記ネット・セグメントの成長中心を形成すること
により前記ネット・セグメント間の結合性を明確化し、
ネット凝固を達成する、ことを特徴とする方法。
【請求項７】請求項６のステップｂ）において、更にｈ
）パス遅延スラックのセットを、各前記マシン・パスに
対するスラック値の昇順に並べ、ｉ）パス遅延スラックのセットをロング・パスからショ
ート・パスの順に優先化する、ことを特徴とする方法。
【請求項８】請求項６のステップｅ）において、前記多
重パス・ネット・セグメントの前記最小遅延値の抽出は
、その後、前記多重ネット・セグメントの前記新たに計
算される最小値をもって、前記多重パス・ネット・セグ
メントを含む全てのパスの前記方程式へ代入し、前記新
たに計算される最小値を前記パス・スラックから減算す
ることにより前記パスのフリーな前記ネット・セグメン
トを再計算し、等区分規則により前記フリー・ネット・
セグメント間で残りのスラックを再割り当てすることを
特徴とする方法。
【請求項９】請求項６のステップｆ）及びｇ）において
、各前記ネット・セグメントのタイミング要求に関し互
換である区分境界は、ネスト化階層手段により獲得され
ることを特徴とする方法。
【請求項１０】請求項９において、前記ネスト化階層は
前記ネット・セグメントにおける予め独立な２つのグル
ープ間の第１のネット凝固に基づくことを特徴とする方
法。
【請求項１１】請求項１のステップａ）において、ブロ
ック配置の優先化は区分境界として選択されるネット・
セグメントの選択を反映して調整され、その際、パス・
スラックの調整はドライバ或いはレシーバとなる境界区
分のブロック選択により変更され、前記パス・スラック
の再割り当ては、前記区分内のネット・セグメントより
も大きい区分境界ネット・セグメントを補償するように
最初の等区分規則を調整することにより達成されること
を特徴とする方法。
【請求項１２】大域的考慮に基づきマシンにおけるパス
遅延を最小化し、マシン・サイクル・タイムを最適化す
る方法において、ａ）パス・スラックの関数としてパス臨界を測定し、ｂ
）配置されるブロックに接続されたネット内のネット・
セグメントにより構成される前記パスを分類し、選択さ
れるブロック配置により影響を受ける全ての前記パスを
決定し、ｃ）前記ネット内の最も臨界的なパスに基づき容認ファ
クタを展開し、その際、前記パス臨界容認ファクタは前
記マシン・サイクル・タイムに対する前記パス・スラッ
クの比率に基づく、ことを特徴とする方法。
【請求項１３】請求項１２のステップｃ）において、前
記臨界容認ファクタは前記昇順リスト内で定義される前
記パス・スラック臨界内におけるパスの相対的位置に基
づくことを特徴とする方法。
【請求項１４】大域的考慮に基づきマシンにおけるパス
遅延を最小化し、マシン・サイクル・タイムを最適化す
る方法において、ａ）ネット・セグメント・スラックの関数としてネット
・セグメント臨界を測定し、ｂ）配置されるブロックに接続されたネット内のネット
・セグメントを分類し、選択されたブロック配置により
影響を受ける全ての前記ネット・セグメントを決定し、
ｃ）前記ネット内の最も臨界的なネット・セグメントに
基づき容認ファクタを展開し、その際、前記ネット・セ
グメント臨界容認ファクタは前記マシン・サイクル・タ
イムに対する前記ネット・セグメント・スラックの比率
に基づく、ことを特徴とする方法。
【請求項１５】請求項１４のステップｃ）において、前
記臨界容認ファクタは昇順リスト内で定義される前記ネ
ット・セグメント・スラック臨界内におけるネット・セ
グメントの相対的位置に基づくことを特徴とする方法。
【請求項１６】局所的考慮に基づきパス遅延を最小化し
、マシン・サイクル・タイムを最適化する方法において
、ａ）パス・スラックの関数としてパス臨界を測定し、ｂ
）配置されるブロックに接続されたネット内のネット・
セグメントにより構成される前記パスを分類し、選択さ
れたブロック配置により影響を受ける全ての前記パスを
決定し、ｃ）パス臨界に基づくコードにより生成された複合重み
を割り当てることにより、各前記ネット内に含まれる全
ての前記ネット・セグメントをインデックス化し、その
際、前記ネット内の各ネット・セグメントに割り当てら
れる前記インデックス化重みはパス臨界の関数であり、
最上のインデックス化重みが最も臨界的なパスに含まれ
る前記ネット・セグメントに対して割り当てられるよう
になっており、ｄ）前記複合重みに基づき容認ファクタを展開し、その
際、前記複合重みは、前記ネット内の各ネット・セグメ
ントのパス臨界の関数であって、前記ネット内の各前記
ネット・セグメントに対する前記インデックス化重みを
含むコードにより定義される、ことを特徴とする方法。
【請求項１７】局所的考慮に基づきパス遅延を最小化し
、マシン・サイクル・タイムを最適化する方法において
、ａ）ネット・セグメント・スラックの関数としてネット
・セグメント臨界を測定し、ｂ）配置されるブロックに接続されたネット内の前記ネ
ット・セグメントを分類し、選択されたブロック配置に
より影響を受ける全ての前記ネット・セグメントを決定
し、ｃ）ネット・セグメント臨界に基づくコードにより生成
された複合重みを割り当てることにより、各前記ネット
内に含まれる全ての前記ネット・セグメントをインデッ
クス化し、その際、前記ネット内の各ネット・セグメン
トに割り当てられる前記インデックス化重みはネット・
セグメント臨界の関数であり、最上のインデックス化重
みが最も臨界的な前記ネット・セグメントに割り当てら
れるようになっており、ｄ）前記複合重みに基づき容認ファクタを展開し、その
際、前記複合重みは、前記ネット内の各前記ネット・セ
グメント臨界の関数であり、前記ネット内の各前記ネッ
ト・セグメントに対する前記インデックス化重みを含む
コードにより定義される、ことを特徴とする方法。
【請求項１８】請求項１２において、前記コスト関数容
認基準は、大域的臨界と、選択されるブロック配置に影
響される前記ネット内の全ての前記パスの局所的複合重
み付けとを組合わせた結果の関数であることを特徴とす
る方法。
【請求項１９】請求項１８において、前記コスト関数は
、大域的臨界と、選択されるブロック配置に影響される
前記ネット内の全ての前記ネット・セグメントの局所的
複合重み付けとを組合わせた結果であることを特徴とす
る方法。
【請求項２０】請求項１において、前記ネット・セグメ
ントの前記優先化は臨界性と結合性とを組合わせた結果
を基礎とし、その際、前記ネット・セグメントは昇順リ
スト内における臨界的位置の順に考慮され、前記結合性
に基づく複数のサブセットに分離され、該サブセットの
リンケージは、そのソース及び宛先ブロックが予め未接
続である前記サブセットの少なくとも１つに存在する前
記ネット・セグメントが現れた時初めて階層構造におい
て達成されることを特徴とする方法。
【請求項２１】請求項１６において、前記コスト関数容
認基準は、大域的臨界と、選択されるブロック配置に影
響される前記ネット内の全ての前記パスの局所的複合重
み付けとを組合わせた結果の関数であることを特徴とす
る方法。
【請求項２２】請求項２１において、前記コスト関数は
、大域的臨界と、選択されるブロック配置に影響される
前記ネット内の全ての前記ネット・セグメントの局所的
複合重み付けとを組合わせた結果であることを特徴とす
る方法。