JPH0334444A - 電子的に連結される対象の相互接続費用を最小化する方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の分野〕 本発明は、電子的に連結される対象を複数の集合に区分
けすることによって電子システムの物理的設計を遂行す
る方法に関し、より特定的には相互接続の伝播遅延を最
小にするために連結される対象を区分けすることに関す
る。

〔発明の背景〕

複雑な電子回路は伝統的に２段階、即ち論理的設計及び
物理的設計によって設計されて来た。論理的設計は回路
の正しい動作とこの動作を達成するための必要成分を限
定するためのプロセスである。物理的設計はハードウェ
アの物理的制約に合致させるための論理的設計の配置或
はレイアウトを含む。

近代電子システムのためのこの設計プロセスの主問題は
、半導体チップの物理的レイアウトの際に設計性能、即
ち速度が最大になるように成分或はモデルを位置決めし
、それらの接続を経路指定することであった。半導体チ
ップは、モデルを保持するための一集合の配置スロット
を受入れる固定された面積しか有していない。また、半
導体チップは、その上に位置しているモデルを他の半導
体チップに結合できるようにするための固定された数の
外部端子即ちピンしか有していない。チノブの電子物理
的設計上考慮しなければならない池の制約は、特定のモ
デルの集合を同一チップ上に配置しなければならないこ
と、或は若干のモデルは異なるチップ上に配置しなけれ
ばならないことを指令する操作上の或は機械的な配慮を
含む。

超大規模集積回路（ＶＬＳＩ）の出現、及びそれらの大
量生産に伴って、限定された面積内に配置できる配置ス
ロットの数は劇的に増加した。半導体チ１ブ上の論理的
設計の配置は、チップの寸法、設計性能に対する制約、
及びレイアウト設計を解くために必要な時間に関して達
成されなければならない。従ってレイアウトを効率的な
設計としなければならないだけではなく、レイアウトの
開発も効率的に遂行しなければならない。

本発明の分野の完全な理解のためｋ、以下の用語を明細
書を通して使用する。

モデル　　：例えばＡＮＤゲート、ＯＲゲート、ＥＸＯ
Ｒゲート等のような不可分 の論理機能ブロック。

；モデルの何等かの人力式１ま出力。

；−組の電気的に共通のポート。

：モデルへの入力ポート。

：モデルからの出力ポート。

：信号の２つのポート間の単一経路。

：電気信号が走行する接続、ポート 及びモデルの順番。

設　計　　：名付けられたモデル、ポート及び信号の収
集。

区　分　　：以下の説明においては、例えば「−組のモ
デルを更なる区分に区 分けし、これらの更なる区分をは ずしてまとめて使い尽くす」のよ うに名詞と動詞とに使い分ける。

：異なる区分に割当てられたモデル を連結する一組の接続。

切断集合 ポート 信号 ロード ドライバ 接続 経路 費　用　　二区分の“費用”とは、その切断集合におけ
る接続の費用の重み付き 和である。

位　置　　：ポート或はモデルの“位置”とは、サブス
トレート上のそのポート或 はモデルの位置を固定する独特な （ｘ、　　ｙ）座標である。

遅　延　　：モデル或は信号接続の“遅延”とは、その
モデル或は接続を通る信 号を通過させるために必要な時間 量である。経路遅延とはある経路 に沿うモデル遅延及び信号遅延の 和である。

タイミング制約：ある経路に沿う最大許容遅延。最大許
容遅延には信号接続遅延及び モデル遅延を含むことができる。

タイミング負債：経路遅延が最悪例タイミング制約を超
えた時間単位の数。

延を有する切断集合内のドライバ 或は負荷。

配置スロット スワップ 部分利得 い遅延を有する切断集合内のドラ イバ或は負荷。

：サブストレート上のモデルを配置 できる位置。

＝２つの異なる配置スロットの内容 を交換する動作。

：２つのモデルのスワップの合計 “利得”とは、古い位置における その接続の費用の和マイナス（−） 新しい位置におけるその接続の費 用の和である。利得は負或は正で あることができる。

：モデルの″′部分利得”とは１つの モデルを別の区分へ移動させるこ とによって生ずる合計利得の一部。

て順序付けるために各区分毎に存 在する連結されたりストデータ構 造。

累積利得　：スワップの順番の利得の和。従って累積利
得は正或は負の何れかで あり得る。

区分けによって電気成分或はモデルを配置する従来の周
知の一方法は、特定のモデルをチップ上の他のモデルに
接続する費用を定義する費用行列を使用する。この方法
は、先ず論理的設計中にモデルの任意の区分を定義する
。次でこの費用行列を使用して区分の集合間の接続の合
計費用を計算する。各集合は支持構造を表わす。即ち各
集合自体はモデルの相互接続を含むことができる。合計
相互接続費用を低下させるためｋ、各集合内の特定の部
分集合の一連の交換が企てられる。それ以上の改善が不
可能になると、結果として得られた区分が記録され、プ
ロセスは無作為に異なる初期区分を用いて繰り返される
。得られた各区分は潜在的に改善された解であり、どの
特定区分もモジュールを半導体チップ上の位置に割当て
るために使用することができる。

従来の周知の区分は方法に伴う問題は、区分けがモデル
間の接続の重要な電気特性を無視していることである。

若干の従来の方法は、時間・臨界ドライバとモデルの負
荷（１つのモデルは別のモデルの人力ポートを駆動する
出力ポートを有する）との間の関係を考慮することがな
いか、或は非効率的にしか考慮していない。現存区分は
方法は、３ポートより多い信号を完全に無視するか或は
信号の全ての接続を均等に考える（即ち信号の接続間に
差別は存在しない）。その結果、臨界接続を切断集合内
に配置する悪い解を、それらをある区分内に含む良い解
と同等であるとしてしまう。

〔発明の概要〕

本発明は、電子的に連結される対象の区分間の重み付き
相互接続費用を最小にする新規方法を提唱することによ
って上述の方法に伴う諸問題を解消する。本方法は、従
来技術のようにモデル間の個々の信号を最適化するので
はなく、モデルを喰切る経路遅延を最適化する。従って
本発明は、システムの論理的及び物理的設計を遂行する
ために必要な時間を短縮しながら、電子的設計を高速で
操作可能ならしめる。

本発明は、特有な基準で臨界ドライバ／負荷接続を正確
に考慮するグラフ区分方法によって達成される。設計全
体の区分けは、設計内のポートの数に対して線形の段階
数しか必要としない。

更に本発明は、接続或はモデルのポートの順序付けを明
確に表わすことなく、あるポートが総合信号長に及ぼす
効果を評価する第２の対による交換方法を提供する。こ
れによって対による交換方法に使用される高速且つ高度
に正確なスワツピング手順がもたらされる。

区分は方法と対による交換方法との組合せが、設計の解
の質及び方法を逐行するために必要な時間の両者を改善
する。

本発明は更ｋ、電子設計をより高速で操作可能ならしめ
、設計プロセスを完了するために必要な時間を短縮させ
得るようにする論理的設計プロセスと物理的設計プロセ
スとの統合をも提供する。

物理的設計は、先ず論理的設計から誘導されたタイミン
グ情報に基いて構成される。論理的再設計は、物理的設
計中に得られる配置情報に基いて遂行される。

〔実施例〕

；ｉ、相互接続費用の最小化 第１図は、本発明による物理的設計中にチップ上に配置
可能な論理回路設計の例を示す。この論理回路は第１レ
ベルのＡＮＤゲートモデルｌＯ〜３２を含み、これらは
あるレベルのＯＲゲートモデル３０〜４０に接続されて
いる。更にこれらのＯＲゲートモデルは第２レベルのＡ
ＮＤゲートモデル４２〜４８に接続されている。各モデ
ルｌＯ〜４８は少なくとも１つの入力ポート及び１つの
出力ポートを有する。信号５０及び５１はそれぞれモデ
ル２２，３６．４０及び１８．　３４．　３６の電気的
に共通のポートを接続するように示しである。あるモデ
ルの出力ポートは信号のドライバである。あるモデルの
人力ポートは信号の負荷である。信号は種々のモデルの
出力ポートと入力ポートとを結合する。Ａ　Ｎ　Ｄゲー
トモデル２２の出力ポートと○Ｒアゲ−モデル３６の入
力ポートとの間、或はＡＮＤゲート２２の出力ポートと
○Ｒアゲ−モデル４０との間のような、信号５０゜５１
の何れか２つのポート間の何れかの経路は、接続の例で
ある。

第２図は、例として、ｘ、　　ｙ＊ＰＡによって指定さ
れる複数の配置スロットを有する半導体チップを示す。

各配置スロットは、モデルの１つを物理的に配置できる
位置である。これらの位置はチップ６０上にそれらの位
置を固定するためのｘ−ｙ座標系を使用して限定される
。従って第１図に示す各モデルｌＯ〜４８は、第２図の
チップ６０上の配置スロット内に位置決めすることがで
きる。

次で、チップ６０は破線６４で示すように区分Ａ及びＢ
に区分けされる。

第１図に戻って、チップ６０の区分けが破線６４で示す
ように論理的設計を分割するものとする。第１図から、
切断集合は第１Ａ図に示すように区分Ａのモデル１０〜
２４．３８及び４０を区分Ｂに割当てられているモデル
３４．　３６．　４６及び４８に連結する接続を含むこ
とが解る。次で、区分Ａ及びＢを懲戒する費用は切断集
合内の接続の費用の重み付き和に基いて決定することが
できる。

この費用は、ある切断集合内の臨界負荷／ドライバポー
ト接続と非臨界負荷／ドライバポート接続との間を区別
する重み付は手順を使用して決定される。

ポートが臨界であるか非臨界であるかは３段階手順を使
用して決定することができる。第１ｋ、所定のタイミン
グ制約を論理回路の出力に対して供給する。これらのタ
イミング制約から、モデル及びワイヤ遅延が差引かれる
。回路を通して後方へ作業することによって、タイミン
グ制約を満たすために必要な到着時間が決定される。第
２ｋ、逆操作を逐行する。即ち、人力信号の到着時間か
らモデルの遅延が回路を通して前方へ向う到着時間に付
加される。これは信号の実際の出力時間を決定する。第
３ｋ、決定された到着時間及び出力時間を実際の値と比
較してタイミング負債を求める。タイミング負債は、接
続のポートが臨界であるか、非臨界であるかを表わす。

即ち臨界ポートはタイミング制約よりも大きい決定され
た時間を有し、非臨界ポートは実際の時間よりも小さい
決定された時間を有する。

例えば、第１Ａ図は第１図の論理的設計の区分けによっ
て懲戒された切断集合を示す。ＡＮＤゲートｌＯ〜２４
及びＯＲゲート３８はこの切断集合内にドライバを有す
る。○Ｒアゲ−３４，３６及びＡＮＤゲー）４６．４８
はその切断集合の一部である負荷を有する。ＯＲゲート
４０はＡＮＤゲート２２によって駆動されている信号５
０上の負荷を有し、またＡＮＤゲート４８上の単一負荷
を有する信号を駆動する。臨界負荷及びドライバは第１
Ａ図に太線で示しである。非臨界ドライバ／負荷接続に
はＷｌｌの重みが割当てられ、臨界ドライバ／負荷接続
にはＷｃの重みが割当てられる。

設計を区分Ａ及びＢに区分けする費用は、この切断集合
内の接続の費用の重み付き和である。第１Ａ図の例では
、区分の費用“Ｃ”は Ｃ＝８Ｗｓ＋２ｗｃに等しい。

もしあるポートを１つの区分から別の区分へ移動させて
も、区分の両側の信号の２或はそれ以上のポートで発生
するような、切断集合を横切る信号には影響を与えず、
このポートの部分利得は０に等しく、例えば第１Ａ図に
示すようにＷ′に＝０に等しいことも理解されよう。

第２図からスワップが、分離した区分内に位置する２つ
の異なる配置スロットの内容を交換する動作であること
が解る。例えば、区分Ａ内に位置する配置スロットＪ及
び区分Ｂ内に位置する配置スロットには、互にスワップ
されるそれらの内容を有することができる。

第３図は、区分は方法に使用される順序付けられたパケ
ットベクトル６８のブロック線図である。

順序付けられたパケットベクトル６８は、メモリ内の構
成、即ちデータ構造である。このデータ構造は、物理的
設計プロセス中のモデルの部分利得を記憶するための連
結されたリスト７０〜７４を形成する。順序付けられた
パケットベクトル６８は、ある区分内のモデルを最小部
分利得（Ｎ）を有するモデルから最高部分利得（十Ｎ）
を有するモデルまで順序付ける。連結されたリスト７０
゜７２．７４及び７６は同一の部分利得（即ち−Ｎから
十Ｎまで）を有するモデルの各集合毎に形成される。順
序付けられたパケットベクトル６８は、本発明を遂行す
る際に発生するスワツピング動作中に連結されたリスト
７０〜７４ヘモデノνを高速挿入し、或はリストから削
除することを可能ならしめる。順序付けられたパケット
ベクトルは、１９８２年の第１９回設計自動化会議の議
事録“ネットワーク区分を改善するための線形・時間発
見的方法”に記載されているように周知である。

第４図は区分は方法に使用されるスワップ活動記録ベク
トルの例を、ベクトル９０に対する部分利得の考え得る
累積和のグラフ例と共に示す。スワップ活動記録ベクト
ル９０の動作に関しては、本発明の詳細な説明と共に後
述する。

時間・臨界接続の設計及びハンドリングを連続的に且つ
再帰的に区分けすることによって、モデル間の接続の伝
播遅延を最小化する方法及び装置を以下に説明する。

本方法の適正操作には、区分は手順として連続した複数
のパスを実施する必要がある。これらの連続パスは、最
良の或は局部的最小解を得るために論理的設計の無作為
初期解を求めるのに使用される。次でこの解が受入れら
れ、得られた各区分Ａ及びＢに対して区分は手順が再び
適用される。

最初のバス中に無作為ｋ、或はモデルを配置スロットに
割当てる別の方法によって、初期配置即ち解が生成され
る。例えば、第１図に対する初期解は、第２図に示すよ
うにモデルを配置スロット内に配置する。

次で、初期割当て即ち解は、第２図の例に破線６４で示
すように２つの区分に部分される。次に連結されたリス
トデータ構造（図示せず）が各区分Ａ及びＢ毎にプロセ
ッサによって構成される。

データ構造は各区分Ａ及びＢ内に存在する配置スロット
を含む。次で各配置スロット毎に部分利得が計算され、
それぞれのデータ構造内に記憶される。

次で、プロセッサは各区分Ａ及びＢ毎に順序付けられた
パケットベクトル６８　（第５図参照）を作成する。順
序付けられたパケットベクトル６８は、特定の順序付け
られたパケットベクトル６８に割当てられた配置スロッ
トの部分利得に従って配置スロットを順序付ける。もし
何れかの配置スロットが空であれば、その部分利得はＯ
であると定義される。

区分Ａの順序付けられたパケットベクトル６８から１つ
、区分Ｂの順序付けられたパケットベクトル６９から１
つの一対の配置スロットが、スロットのスワツピングが
最大利得をもたらすように選択される。選択可能な配置
スロットの最大利得対を決定するためには若干の周知の
方法を使用することが可能である。好ましい方法は、最
高部分利得を有する各順序付けられたパケットベクトル
からの配置スロットを先ず考える。それらのスワップか
ら得られた総合利得は、スワップされる配置スロットの
最良対の探索を制限するための束縛用基準として使用さ
れる。

第５図及び表Ａは、本発明の臨界ドライバ／負荷重み付
けを取り入れた配置スロット選択の簡易例を示す。順序
付けられたパケットベクトル６８及び６９がそれぞれ各
区分Ａ及びＢ毎に示されている。また、配置スロッ）１
〜３及び４〜７がそれぞれ区分Ａ及びＢ内に示されてい
る。説明の目的から配置スロット１〜６間の接続を示す
。

表　　　Ａ 表Ａは、何等かのスワツピングを行う前の各配置スロッ
ト１〜７毎に費用を示す。区分Ａの順序付けられたパケ
ットベクトル６８は、配置スロットの費用の関数である
それらの部分利得に依存する配置スロット１〜３の連結
されたリストを形成する。配置スロット５の人力ポート
は非臨界であって切断集合に影響を与え得ないためにそ
の重みが０であることに注目されたい。また配置スロッ
ト４の人力ポート（同一信号５２上〉がタイミング解析
の結果に基いてＷｃの重みを有していることにも注目さ
れたい。これも同一信号５２上にある配置スロット１は
、それが臨界経路及び切断集合の大きさに影響するため
ｋ、ＷＣ＋Ｗイの費用を有する。第５図から明らかなよ
うｋ、配置スロッ）ｌは（ＷＣ＋Ｗ１１　）即ちその接
続の重み付き費用に等価な最高部分利得を有する。従っ
て、順序付けられたパケットベクトル６８は配置スロッ
ト１のみを含む第１の連結されたリストを有する。

同様に配置スロット２はＷＮの部分利得を有し、空配置
スロットであるスロット３は０に等しい部分利得を有す
る。従って順序付けられたパケットベクトル６８はｌ配
置スロットずつを含む３つの連結されたリストを有する
。区分Ｂのための順序付けられたパケットベクトル６９
も同様に３つの連結されたリストを有する。

従って、例えば配置スロット１及び４のような最高部分
利得を有する配置スロットが、それらの内容をスワップ
するために先ず選択される。理論的に考え得る最良合計
利得はスロットｌ及び４の部分利得の和即ち２Ｗｃ＋Ｗ
、ｌに等しい。しかし実際にはスロット１と４とのスワ
ツピングは０の利得をもたらすに過ぎない。これは、ス
ロット１を区分Ｂに移動させるとＷｃ＋ＷＮの部分利得
が発生するが、スロット４を区分Ａに移動させると−Ｗ
。−Ｗ、Ｉの部分利得をもたらすようｋ、配置スロット
が互に結合されているからである。これらの部分利得を
加算すると合計利得は０になる。

従って、以後のスワップのための初期束縛用基準は０に
なる。

区分Ｂのための連結されたりストロ９内には他にＷ。の
部分利得を有する配置スロットは存在しないから、次に
最高の部分利得を有する配置スロット（この場合ＷＮの
部分利得を有するスロット５）が配置スロッ）１とのス
ワップのために選択される。これはＷｏの合計利得をも
たらし、新しい束縛用基準となる。

次ｋ、配置スロット６がスロットｌとのスワツピングの
ために選択され、これはＷｃ＋ＷＮの利得をもたらす。

これが、以後のスワップが最大利得対を見出すための比
較を必要としないことを決定するための新束縛用基準と
なる。本例においてはＷ。＋Ｗ、ｌの束縛用基準は、ス
ロッ）１と７のスワツピングがＷ。＋Ｗ８よりも良い利
得を発生することができないので、考え得る最良の合計
利得であることが解る。従って探索はこの解を以て終了
する。

最大利得対、即ちスロットｌとスロット６はスワップさ
れ、後に処理するためにスワップ活動記録ベクトル９０
上に配置される。スワップが発生した後、プロセッサは
順序付けられたバケットベクトル６８．６９からこの特
定のスワップに関係した配置スロット（１及び６）を除
去し、モデルに対して残余のパスに関しては非油ｖＪ（
固定）であるものとしてマークする。このプロセスは、
活動であるとマークされている残余の配置スロットに関
して繰り返される。

以上の如く、スワップ活動記録ベクトル９０は、各スワ
ップが発生する度にスワップされた対をスワップ活動記
録ベクトル９０の位置９４〜１０５へ連続的に配置する
ことによって、区分の漸進的変化の履歴を記録する。更
ｋ、このパスの始めからの累積和も、第４図のグラフ１
０６によって示しであるようｋ、スワップ活動記録ベク
トル９０上に配置される。累積利得は０に始まり、若干
の点においては正ｋ、また他の点においては負になり得
る。

各スワップ後、各区分Ａ、　　Ｂ内の順序付（すられた
パケットベクトル６８．６９は更新される。信号及び区
分には信号カウンタが対応付けられており、種々の信号
及び区分パラメタの軌跡を保持する。これらのパラメタ
は、区分Ａ及びＢの自由モデル（未だｋ、固定されてい
ないモデル）カウント、区分Ａ及びＢの固定されたモデ
ルカウント、区分Ａ及びＢの臨界負荷カウント、区分Ａ
及びＢの自由臨界モデル負荷カウント、区分Ａ及びＢの
固定された臨界モデルドライバカウント、及び区分Ａ及
びＢの自由臨界モデルドライバカウントを含む。信号カ
ウンタも各スワップを反映するように更新される。更新
された部分利得を有するモデルを含む配置スロットは除
去し、順序付けられたパケットベクトル６８．６９内の
正しい位置に再挿入しなければならない。

全ての、或は少なくとも所望数のスワップが試みされて
しまうと、これらのスワップから決定された設計の最良
解は、スワップ活動記録ベクトル９０をその逆の順序に
再生することによって最大累積利得９２の最終点まで戻
されて復元される。

スワップを再生した後に信号カウントは再度更新しなけ
ればならず、若干のモデルはそれらの部分利得を変える
必要があるかも知れないので、順序付けられたパケット
ベクトル６８．６９内のモデルの配置スロットの除去及
び再挿入が必要となる。

局部的な最適条件に到達する、即ち最良解を見出すため
に必要なスワップの数は、継続する各パスと共に減小す
ることが実験的に解っている。局部的最適条件に到達す
るために必要なスワップの合計数の好ましいパーセンテ
ージは、第１バスで約５５％、第２パスで５５％、４０
％、２０％、１０％等々であることが解った。従って各
パスに関して考慮されるスワップの数の減小と共にスワ
ップ活動記録ベクトル９０の再生はプロセッサが必要と
する時間及び努力を減小させ、解はポート数に対して線
形的な時間内に得ることができるようになる。モデル間
の接続に個々に重みを付けつつポートの数に対して線形
時間内に動作する能力は、論理的及び物理的の両設計を
遂行するために必要な時間を短縮させる。

正の累積利得をもたらすスワップの順番が見出されない
場合は、本方法はその局部的最小に達したのである。し
かし局部的最小は常に入城最小ではない。即ち異なる初
期解が異なる局部的最小を発生し得る。従ってユーザが
指定する回数の無作為始動、即ち無作為な初期配置が行
われ、見出された最良解が復元される。

次て各区分Ａ及びＢは、更なる部分を侍ａする区分の連
結されたリストデータ構造上に配置される。各区分Ａ及
びＢは引続き選択され、上述の方法が再び適用される。

区分は、全ての区分の大きさが均一となるようｋ、また
誘導される何等かのタイミング推定誤差も区分間で均一
となるように巾優先で部分される。

上述の方法は、区分がユーザー指定数より少ない配置ス
ロットを含むようになるまで遂行される。

この時点で、上述の結果を改善するために対による交換
位置スワツピング方法が実施される。対による交換方法
はポートに伴う信号遅延を効果的に計算し、それにより
２つの配置スロットの内容のスワンピングが有益か否か
を決定する。上述の型の解の正確さを期すため従来の方
法は、本発明の対による交換方法よりも遥かに計算量が
多いか、或は遥かに正確さに欠けるかの何れかである。

対による交換方法の例を第６図及び第７図を参照して説
明する。第６図はある信号を懲戒している７ポー）Ａ−
Ｆを含む区分を示す。任意のポートＡを例にとれば、本
方法はポートＡと同−信号内の最寄りの２つのポート、
即ちポー）Ｂ、Ｃを捜し出す。本方法は、三角形の全て
の頂点間の遅延（Ａ’、　Ｂ）、（Ａ、　Ｃ）　、及び
（ＢＣ）を計算する。３つの辺ＡＢ、ＡＣ，ＢＣの中で
最長の辺ＢＣは破棄される。ＡからＢまでの経路に伴う
信号遅延“ｄ”、即ち（ｄＡＢ）プラスＡからＣまでの
遅延（ｄＡｃ）が破棄された接続の遅延即ちｄＢＣと比
較される。ＤｌｆｆＡ＝　（ｄＡｌ＋ｄＡｃ）　　ｄａ
ｃに相当する差”Ｄ＋ｆｆＡ’がポートＡの位置におけ
る信号遅延に対するポー）Ａの寄与の値として戻される
。この差値はポー１−Ａの１つの位置に関して、及びポ
ートＡのスワップされる位置に関して計算される。第７
図にはＡのスワップされた位置を位置Ａ′として示しで
ある。信号内に２つのポートしか存在しない場合には、
本方法は遅延“ｄ”をポートＡから単一の最寄リポート
までの遅延、例えばｄＡＸとして戻す。

位置Ａ′に関してプロセスを繰り返し、三角形Ａ’　Ｄ
Ｅの頂点は各接続Ａ’　Ｄ、ＤＥ、Ａ’　Ｅ毎に計算さ
れた信号遅延が求められる。第７図から、最長辺Ａ’　
Ｅが破棄され、得られた経路接続Ａ’　Ｄ＋ＤＥからの
遅延が計算され、破棄された信号遅延接続Ａ’　Ｅに対
して比較されることは明白であろう。差ＤｉｆｆＡ’は
スワップ前の差ＤｉｆｆＡと比較される。更ｋ、スワッ
プされたモデルの各ポート毎の差がスワップの前後の面
位置に関して計算される。もしモデルからの遅延に対す
る総合的な寄与がスワップ前よりもスワップ後の方が小
さければ、このスワップは改善である。

上記の対による交換方法は、ユーザー指定の回数で作動
して区分は方法で遠戚された物理的設計への総合解を改
善する。

区分は及び対による交換の両方法を含む物理的配置プロ
セスの詳細設計を表Ｂ、　Ｃ及びＤに示すルーチン呼出
し階層を参照して説明する。

表　　　Ｂ ＣＯＮＴＲＯＬ　　ＦＬＯＷ： ＰＬＡＣＥ　　Ｄ巳５ＩＧＮ ＳＥＴ　　ＬＯＣＡＴＩＯＮ　　ＯＦ　　ＰＡＲＴＩＴ
ＩＯＮＣＬＥＡＲＡＬＬ　　ＷＩＲＥＤＥＬＡＹＳＳε
Ｔ　ＴＩＭＩＮＧ　ＰＡＲＡＭＥＴεＲ３ＲＥＣＩＪＲ
３ＩＶＥＬＹ　ＤＩＶＩＤＩＥ　ＰＡＲＴＩＴＩＯＮＤ
ＩＶＩＤＥ　ＰＡＲＴＩＯＮ ＳＥＴ　ＬＯＣＡＴＩＯＮ　ＯＦ　ＰＡＲＴＩＴＩＯＮ
ＳＥＴ　　５ＬＯＴＳ　　ＯＦ　　ＰＡＲＴＩＴＩＯＮ
ＳＥＴ　ＬＯＣＡＴＩＯＮ　ＯＦ　ＭＯＤＥＬＭＩＮ　
ＣＬＩＴ ＲＥＳＴＯＲＥ　ＢＥＳＴ　ＭＵＤεＬＳεＴ　　８Ｓ
ＴＩＭＡＴＥＤ　　ＷＩＲＥ［ｌεしＡＹＳＳＥＴ　Ｔ
ＩＭＩＮＧ　ＰＡＲＡＭＥＴＥＲ３ＰＡＩＲＷＩＳεＩ
ＮＴＥＲＣＨＡＮＧＥ表　　　Ｃ 關ＩＮ　ＣＵＴ ＣＬＥＡＲＭＡＲＫＳ　ＡＮＤ　ｃ、ＵＮＴＳ　ＯＦ　
ＰＡＲＴＩＴＩＯＮＣＬＥＡＲ５ＩＧＮＡＬ　ｃ、ＵＮ
ＴＳＳＥＴ　　ＰＡＲＴＩＡＬ　　ＧＡＩＮ　　ｃ、Ｕ
ＮＴＳＩＮＣＲｃ、ＵＮＴＳ　ＯＦ　５ＩＧＮＡＬＩＮ
ＣＲｃ、ＬＩＮＴＳ　ＯＦ　５ＩＧＮＡＬ　ＦＯＲＤＲ
ＩＶＥＲＰＲＯＪ８ＣＴＳ　０ＮＴＯＰＡＲＴＩＴＩＯ
ＮＬＯＣＡＴＩＯＮ　　Ｉｓ　　ＩＮ　　ＢＯＸＰＯＲ
Ｔ　　ＷＯＵＬＤ　　ＢＥ　　ＣＲＩＴＩＣＡＬＩＮＣ
Ｒｃ、ＵＮＴＳ　ＯＦ　５ＩＧＮＡＬ　ＦＯＲＬＯＡＤ
ＰＲＯＪＥＣＴ　０ＮＴＯＰＡＲＴＩＴＩＯＮＬＯＣＡ
ＴＩＯＮ　　Ｉｓ　　ＩＮ　　ＢＯＸＰＯＲＴ　ＷＯＵ
ＬＤ　ＢＩＥ　ＣＲＩＴＩＣＡＬＡＤＤ　５ＬＯＴＳ　
ＴＯ０ＲＤＥＲＥＤＢＩＩＣＫＥＴＶＥＣＴＯＲＣＡＬ
ＣＰＡＲＴＩＡＬ　　ＧＡＩＮ　　ＯＦ　　ＭＯＤＥし
ＰＯＲＴ　　ＷＯＵＬＤ　　ＢＥ　　ＣＲ［ＴＩＣＡＬ
ＰＡＲＴＩＡＬ　ＧＡＩＮ　ＯＦ　ＣＲＩＴＩＣＡＬ　
５ＩＧＮＡＬ　ＬＯＡＬＦＩＸＥＤ　ＣＲＩＴ　ＤＲＩ
ＶＥＲｃ、ｔｌＮＴＦＲＥＥ　ＣＲＩＴ　ＤＲＩＶＥＲ
ＣＯＵＮＴＰＡＲＴＩＡＬ　　ＧＡＩＮ　　ＯＦ　　Ｎ
ＱＮＣＲＩＴ＋ＣＡＲ３ＩＧＮＡＬ Ｆｌ’＜ＥＤ　ＣＤｔｌＮＴ　ＯＦ　ＰＡＲＴＩＴＩＯ
ＮＦＲＥ巳ｃ、ＵＮＴ　ＯＦ　ＰＡＲＴＩＴ［０ＮＰＡ
ＲＴＩＡＬ　　ＧＡＩＮ　　ＯＦ　　ＣＲＩＴＩＣＡＬ
　　５ＩＧＮＡＬＲＩＶＥＲ Ｆ［ＸＢＤ　　ＣＲＩＴ　　ＬＯＡＤ ＦＲＥＥ　　ＣＲＩＴ　　ＬＯＡＤ　　ｃ、ＵＮＴＰＡ
ＲＴＩＡＬ　ＧＡＩＮ　ＯＦ　Ｎ０ＮＣＲ［ＴＩＣＡＬ
ＩＧＮＡＬ ＩＮＳＥＲＴ　５ＬＯＴ　ＩＮＴＯ０ＲＤＥＲＥＤＢ［
ＪＣＫＥＴＶ［ＥＣＴ０ＲＢ［ＩＣＫＩＥＴ　ＯＦ　５
ＬＯＴ ＦＩＮＤ　ＭＡＸ　ＧＡＩＮ　ＳＷＡＰＭＡＸ　　ＧＡ
ＩＮ　　ＯＦ　　　０ＲＤＥＲ［ＥＤＢＵＣＫ［ＥＴＶ
ＥＣＴＯＲＩｓ　Ａ　ＬＥＧＡＬ　５ＷＡＰ ＰＡＲＴＩＡＬ　ＧＡＩＮ　ＯＦ　ＩＮＴ［ＥＲＮＡＬ
　ｃ、ＮＮＥＣＴｌ０ＮＳＰＯＲＴ　ＷＯＵＬＤ　　Ｂ
Ｅ　ＣＲＩＴＩＣＡＬＰＡＲＴＩＡＬ　　ＧＡＩＮ　　
ＯＦ　　ＣＲＩＴＩＣＡＬ　　５ＩＧＮＡＬ　　ＬＯＡ
ＬＰＡｆｌＴＩＡＬ　　ＧＡＩＮ　　ＯＦ　　ＣＲｉＴ
Ｉ（：ＡＬ　　５ＩＧＮＡＬＲＩＶＥＲ ＰＡＲＴＩＡＬ　　ＧＡＩＮ　　ＯＦ　　ＮｏＮＣＲＩ
ＴＩＣ人し　５ＩＧＮ八しＦＩＮＤ　　ＰＯＲＴ　ＯＮ
　５ＩＧＮＡＬＦＩＮＤ　ＰＯＲＴ　ＯＮ　ＣＲＩＴＩ
ＣＡＬ　５ＩＧＮＡＬＦＩＮＤ　　ＮＥＸＴ　　ＬＯＷ
ＥＲＮＯＮ８ＭＰＴＹ　　ＢＵＣＫεＴＲＥＭＯＶＢ　
５ＬＯＴ　ＦＲＯＭ　０ＲＤＥＲ［ＥＤＢＵＣＫＥＴＶ
ＥＣＴＯＲＢＵＣＫＥＴ　ＯＦ　　５ＬＯＴ ＦＩＮＤ　ＮＥＸＴ　）ＩＩＧＨＢＲＮＯＮ　ＥＭＰＴ
Ｙ　ＢＵＣＫＥＴＦＩＮＤ　　ＮＥＸＴ　　ＬＯＷＥＲ
ＮＵＮ　　ＥＭＰＴＹ　　ＢｔｌＣＫεＴＲε０ＲＧＡ
ＮＩＺ［Ｅ　ＯＲＤ［ＥＲＥＤＢＵＣＫＩＥＴＶ８ＣＴ
ＯＲｔｌＰＤＡＴＢ　　ＬＯＡＤＳ　　ＯＦ　　Ｍ［１
ＤＥＬＩＮＣＲＰＡＲＴＩＡＬ　ＧＡＩＮ　　ＯＦ　Ａ
ＬＬ　　ＦＲＥＩＥ　ＣＲＩＴＤＲ［ＶＥＳ　　ＩＮ ＵＰＤＡＴＥ　ＣｔｌＴＳＥＴ　　ｃ、ＵＮＴＳＦＲＥ
Ｅ　ｃ、ＵＮＴ　ＯＦ　ＰＡＲＴＩＴＩＯＮＦＩＸＥＤ
　ｃ、ＵＮＴ　ＯＦ　ＰＡＲＴＩＴＩＯＮＩＮＣＲＰＡ
ＲＴＩＡＬ　ＧＡＩＮＳ　　ＯＦ　ＡＬＬ　　ＦＲＥＥ
ＭＯＯεＬ　　ＩＮ ＩＮＣＲＰＡＲＴＩＡＬ　　ＧＡＩＮ　ＯＦ　ＡＬＬＰ
［］ＲＴ　　ＩＮ ＵＰＤＡＴＥ　　ＤＲＩＶ８Ｓ　ＯＦ　ＭＯＤＥＬＩＮ
ＣＲＰＡＲＴＩＡＬ　　ＧＡＩＮ　　ＯＦ　　ＡＬＬＬ
ＯＡＤ　　ＩＮ ＵＰＤＡＴ［Ｅ　Ｃ［ＩＴＳＥＴ　ｃ、ＵＮＴＳＲＥＳ
ＴＯＲＥ　ＢＥＳＴ　５ＯＬＵＴＩＯＮＰＥＲＦ［）Ｒ
Ｍ　　Ｔ）ＩＥ　　Ｓｔ！ＩＡＰＰＬＡＣＥ　　ＭＯＤ
ＥＬ　　ＩＮ　　５ＬＯＴＳＥＴ　ＬＯＣＡＴ［ＯＮ　
ＯＦ　ＭＯＤＥＬＲＥＥ ＣＲＩＴ 表　　　Ｄ ＰＡＩＲＷＩＳＥ　　ＩＮＴＥＲＣＨＡＮＧＢＩｓ　　
Ａ　　ＬＥＧＡＬ　　ＳＩＩＩＡＰＰＬＡＣＥＭεＮＴ
　ｃ、３Ｔ　ＯＦ　ＭＯＤＥＬＤＩＦＦＥＲＥＮＣＥ　
　ＩＮ　　５ＩＧＮ八Ｌ　　ＬＥＮＧＴＨＧＥＴ　ＣＬ
Ｏ３ＥＳＴ　ＴＲＩＡＮＧＬＥＤＥＬＡＹ　ＦＵＮＣＴ
ＩＯＮ ＰＥＲＦＯＲＭ　ＴＭ１１５ＷＡＰ ＳＥＴ　　ＬＯＣＡＴＩＯＮ　　ＯＦ　　ＭＯＤＥＬＴ
ＯＴＡＬ　ＰＬＡＣＥＭＥＮＴ　ＣＯ３Ｔｃ、３ＴＰＬ
ＡＣＥ　ｃ、３Ｔ　ＯＰ　ＭＯＯＢＬ表Ｂは高レベル関
数ルーチンである“場所設計”ルーチンを示す。場所設
計は配置スロットへのモデルの無作為割当てから始める
。場所設計ルーチンは、区分のｘ、　　ｙ座標を定義す
る“区分の位置をセットせよ”、ルーチンにどのワイヤ
遅延が臨界であるかを決定可能ならしめる“全ワイヤ遅
延をクリヤせよ″、論理設計に対するタイミング解析を
遂行させる“タイミングパラメタをセットせよ”、及び
特定区分を更に２つの区分に分割させる（これらの区分
は再帰的に再び分割される）“区分を再帰的に分割せよ
”を呼び出す。

“区分を再帰的に分割せよ”ルーチンは更ｋ、“区分を
分割せよ”を呼び出し、これが更ｋ、“区分の位置をセ
ットせよ”を呼び出して、区分内の全ての配置スロット
を含む最小包囲矩形のＸ。

ｙ座標が２座標〈横軸〉或はｙ座標（縦軸）の何れかに
沿って半分に分割されるような“束縛用箱”方法を使用
して区分を実際に分割する。これが２つの区分を形式す
る。

次で”区分を分割せよ”ルーチンは“区分のスロフトを
セットせよ”をも呼び出し、これが更に“モデルの位置
をセットせよ″を呼び出して各区分内にある配置スロッ
トの連結されたリストを決定し、またモデルの位置をそ
の区分の中心にあるものとして限定する。

“区分を再帰的に分割せよ”ルーチンは、区分の最良配
置スロットの連結されたリストを記憶する（これは爾後
のパスが配置スロットを無作為化するであろうことから
行われる）“最良モデルをクリヤせよ”、スワップを決
定する作業（後述）を実際に遂行する“Ｍ　Ｉ　Ｎ　Ｃ
Ｕ　Ｔ”　、ＭＩＮ　ＣＬＩＴ　中に見出された最良解
を復元する“最良モデルを復元せよ”、ワイヤ遅延を再
推定することによってモデルのスワツピングが原因で誘
導される新遅延を考慮に入れる“推定ワイヤ遅延をセッ
トせよ”タイミング解析を再度遂行する“タイミングパ
ラメタをセットせよ”、及び区分は方法かＳ得た解の正
確さを期すために対による交換を遂行する“対による交
換“をも呼び出す。

ＭＩＮ　　ＣＵＴ階層ルーチンは表Ｃに示され、以下に
説明する。ＭＩＮ　　ＣＵＴルーチンは、マーク及び信
号カウントを０にセットする“区分のマーク及びカウン
トをクリヤせよ”　（マークはモデルが自由か或は固定
かを、即ち活動か或は非活動かを表わす）、及び信号及
び区分のカウントを４に備するために他のルーチンを呼
び出す“部分利得カウントをセットせよ”を呼び出す。

信号及び区分に対応付けられたカウントパラメタは、区
分Ａ及びＢの自由カウント、区分Ａ及びＢの固定カウン
ト、区分Ａ及びＢの固定臨界負荷カウント、区分Ａ及び
Ｂの自由臨界負荷カウント、区分Ａ及びＢの固定臨界ド
ライバカウント、及び区分Ａ及びＢの自由臨界ドライバ
カウントを含む。

ＭＥＮ　　ＣＵＴルーチンは更ｋ、モデルの部分利得を
計算してそれらの配置スロットを順序付けられたパケッ
トベクトル内の適切なスロット内へ挿入する（即ち、配
置スロットがそれらの部分利得によって順序付けられた
パケットベクトル内へ索引付けられる）“スロットをｊ
頃序付けられたパケットベクトルへ付加せよ”を呼び出
す。これは、モデル上に存在する信号において個々の人
力及び出力の部分利得を加算することによって（これは
臨界及び非臨界利得の和である）行われる。

ＭＩＮ　　ＣＵＴルーチンはまた、スワップされた配置
スロットの最大利得対を臨界ドライバ／負荷接続を考慮
に入れて決定する“最大利得のスワップを見出せ”、最
大利得スロットを順序付けられたパケットベクトルから
除去する“スロットを順序付けられたパケットベクトル
から除去せよ”、スワツピングによって生じた部分利得
の変化に基いてベクトルを認識する“順序付けられたパ
ケットベクトルを認識せよ”をも呼び出す。順序付けら
れたパケットベクトルの認識は、順序付けられたパケッ
トベクトルを始めに作成するプロセスに類似する。

最後ｋ、ＭＩＮ　　ＣＵＴルーチンは、最良の解を復元
するためにスワップ活動記録ベクトル内に記憶されてい
るスワップを逆の順序で遂行する“最良解を復元せよ”
を呼び出す。

“区分を再帰的に分割せよ″はユーザー指定回数遂行さ
れ、“対による交換ルーチン（表Ｄ）を呼び出すことが
できるようになるまで巾優先で区分を更に分割する。“
対による交換”ルーチンは前述のようｋ、三角形を形成
する最寄りの配置スー口７）の信号長の差を決定するこ
とによりモデルの配置費用を見出すことによって遂行さ
れる。スワップが遂行され、遅延に改善がもたらされた
か否かが決定される。もし改善が遠戚されていれば、そ
のスワップが逐行される。対による交換が各区分内の全
ての配置スロットに関して遂行される。

この点において、区分の大きさが比較的小さいことに注
目されたい。

■、論理的設計と物理的設計との統合 前記方法は半導体チップの物理的設計に関連する。しか
し、電子的ハードウェア設計の総合目的は、特定機能を
遂行し、またハードウェアに実現された時に特定の速度
範囲内で動作する電子装置を構成することである。ハー
ドウェア設計は２つの明確な域、即ち論理的設計と物理
的設計とに分離することができる。論理的設計は、装置
機能及びハードウェアを適切に動作させるために満たさ
れなければならない装置タイミングに対する制約を含む
。物理的設計は、前述のように論理的に設計された回路
を半導体チップ上に物理的に実現することである。始め
は、各タスクが複雑であるためｋ、論理的設計は物理的
設計から分離される。

物理的設計は論理の再設計によってのみ解決できるタイ
ミング問題を創成するから、物理的設計と論理的設計と
の間には典型的に繰り返しプロセスが要求される。設計
が技術の性能限界に近づくにつれて両設計相聞の相互作
用はより大きくなり、より多くの繰り返し時間が必要と
なる。

解消すべき問題の例を第８図乃至第１１図に示す。第８
図は出力を○Ｒアゲ−８１に結合された２つのＡＮＤゲ
ー）８０．８２からなる簡易な論理機能である。これら
３つのモデルは、後述するように技術セル内に写像すべ
き機能を形成する。

この機能はＡＮＤゲー）８０．８２の入力からＯＲゲー
ト８１の出力（Ｚ）まで１０ナノ秒（ｎＳ）（第８図）
のタイミング制約があるものとする。

更ｋ、信号１．及び１２はそれぞれＡＮＤゲート８０．
８２の出力からＯＲゲート８１の人力ポートまでの経路
を表わす。各信号ｉ、、ｉ、はｌｎｓに等しい遅延を有
するものとして示しである。

第９図は、第８図に示す機能を実現するために使用可能
な３つの技術セルＯＡ２．ＡＮ２及び○Ｒ２の簡易例を
示す。技術セルは、その入力ポートからその出力ポート
まである変換を遂行する名付けられたモデルとして定義
される。技術セルは製造者によって特定される各技術に
対する“基本”である。製造者は爾後にこれらの基本を
使用して特定設計を構築する。

図示の例において、各技術セルは次のようなタイミング
値を有するものとする。経路Ｐｉを通る場合のセル○Ａ
２＝７ｎＳ、経路Ｐ２を通る場合は３ｎＳであり、セル
０Ｒ２＝５ｎＳであり、セル０Ｒ２＝５ｎＳである。各
技術セルの既知のタイミング遅延は、タイミング制約（
即ち第８図に示す論理機能の１０ｎＳ）を満たすために
は重要である。

例えば、第８図の論理機能は２つのＡＮ２セル及び１つ
の○Ｒ２セルを使用して実現できる。しかし、この機能
を実現するためのタイミング遅延は、セルのタイミング
遅延とセルを相互接続する経路ｉ、及び１２のタイミン
グ遅延との和である。

従って、ＡＮＤゲート８０の人力ポートＡ及びＢからＯ
Ｒゲート８１の出力ポートｚまでの経路は、セル穴Ｎ２
の６ｎＳ遅延十信号１１の１ｎＳ遅延＋セル○Ｒ２の５
ｎＳ遅延に等しい遅延を有する。合計遅延は１２ｎＳに
等しく、これはこの機能のための１０ｎＳのタイミング
制約を犯すことになる。同様ｋ、入力ポートＣ及びＤか
ら出力ポー）Ｚまでの遅延も１２ｎＳに等しい。

第８図の機能を実現するための変形方策は、１つのＯＡ
２技術セルと１つのＡＮ２セルとを使用する。この構造
によれば、ゲート８０及び８１のタイミング遅延は、技
術セルＯＡ２内に含まれるＡＮＤゲート及びＯＲゲート
の７ｎＳ遅延に等しい。

ゲート８２からゲート８１を通る遅延は、セル穴Ｎ２の
遅延（６ｎＳ）及びセル○Ａ２内のＯＲゲート経路の遅
延（３ｎＳ）に等しい。従って第８図の機能の一方の経
路を通る時の合計遅延は１Ｏｎｓであり、他方の経路の
場合には６ｎＳ遅延プラス１２の１ｎＳ遅延＋セル○Ａ
２内の３ｎＳ遅延に等しく合計１０ｎｓとなる。従って
両タイミング経路共第８図に与えられた１０ｎＳのタイ
ミング制約内にある。

第１Ｏ図は、従来の論理的及び物理的設計プロセスをど
のように分離し、繰り返したかを示す。

第８図の論理機能は、既知のタイミング制約を満たすよ
うに論理的設計段階中に上述の技術セル（○Ａ２及びＡ
Ｎ２）を使用するように設計されている。回路図は、チ
ップ上に配置する物理的設計段階に送られる。しかし技
術セルをチップのある領域上に配置する時ｋ、論理的設
計が物理的設計に接続形態の複雑さをもたらし、その結
果ワイヤが長くなって遅延を付加したり或はドライバが
信号上に広く離間した負荷め全てを駆動し得ない場合に
発生するように非効率的な負荷分割を生ずることが屡々
である。分割或はクラスタ化は論理的設計及び物理的設
計が、それぞれ他方に影響を与えるように密に結合して
いる域である。最良の区分けは、物理的設計のワイヤ遅
延を低く抑え、また論理的設計に最適の電気的性能をも
たらすような良好な負荷のクラスタ化を達成する。

第１Ｏ図はチップ或はサブストレート６０上への技術セ
ルの初期配置を示す。外部ピンＡ、　　Ｂ。

Ｃ，Ｄ及び２の位置のためｋ、ＡＮＤ１０Ｒゲート経路
の１つを通る場合の遅延は、セル○Ａ２の７ｎＳ遅延十
点８４から８６までの１ｎＳの出力遅延に等しい。ビン
Ｃ，ＤからＡ　Ｎ　Ｄ　／　ＯＲゲート組合せを通る他
の経路は、セルＡＮ２の６ｎＳ遅延＋２ｎＳ経路遅延＋
セル○Ａ２の３ｎＳ遅延＋出力ピンまでの１ｎＳ遅延を
受ける。従ってポー）Ｃ及びＤから出力Ｚまでの合計遅
延は１２ｎＳに等しく、第８図に与えられている１０ｎ
Ｓの制約を犯すことになる。プロセスのこの段階で物理
設計者はこの論理機能を論理設計者に戻してサブストレ
ート６０上のピン配置に従って再設計させる。

論理設計者はポートＣ及びＤから出力Ｚまでの経路に対
する合計タイミング制約を例えば１０ｎＳから７ｎＳ　
（１０ｎＳ　−（ピン配置から２ｎＳ！延＋１１ｔｓ）
　〕に短縮しなければならない。この制約を得て論理設
計者はポートＣ及びＤから出力Ｚまでの経路を７ｎＳよ
り大きくしてはならず、従ってＡＮＤゲート及びＯＲゲ
ートを通る時に７ｎＳの遅延を有するセルＯＡ２をモデ
ル８２及び８１（１８図）の配置の際に使用しなければ
ならないことを知る。この点で総合設計プロセスの制御
は再び物理設計者に引渡される。

物理設計者は与えられた全てのタイミング制約に合致さ
せるためｋ、セルＡＮ２及びセル○Ａ２を使用して第１
１図に示す配置を実現する。ポートＡ及びＢから出力ピ
ンＺ（点８６）までの遅延は、セルＡＮ２の６ｎＳ遅延
＋セルＯＡ２の３ｎＳ＋ピンＺ（８６）までの１ｎＳの
経路通過時間に等しい。同様ｋ、ポートＣ及びＤから点
８６までの遅延は１０ｎＳ、即ちビンＤからセルＯＡ２
までの２ｎＳ＋セル○Ａ２の７ｎＳ＋出力ピンＺまでの
１ｎＳに等しい。

従って論理的設計と物理的設計とを分離して遂行するこ
の繰り返しプロセスが時間を消費し且つ退屈なプロセス
であることが理解できよう。設計が技術の性能限界に近
づくにつれて２つの設計相聞の相互作用が大きくなり、
より多くの繰り返しが必要となる。本発明の方法は論理
的及び物理的設計を連帯して自動的に解くので、プロセ
スを高速化し、より効率的に遂行する。

更に本発明は論理的設計と物理的設計との間の複雑さを
打解する方法をも提供する。本方法は、タイミング情報
に基いて物理的設計を、また配置情報に基いて論理的再
設計を構成する。

第１図に示すような設計は、モデルの相互接続、１組の
性能目的（例えばタイミング制約）、及び技術を記述す
るパラメタ（例えばモデル遅延、最大駆動能力、信号遅
延等）からなる。

論理的設計に関するタイミング解析はソフトウェアアル
ゴリズムによって遂行される。タイミング解析を遂行す
る１つの好ましい方法は、１９８６年１０月１２日付で
出願された合衆国特許出願Ｓ、　Ｎ、　９０７．５１４
号“論理回路設計の合成にタイミングパラメタを組み入
れる手順に記載されている。タイミング解析の結果はあ
るモデルの各ポートの“タイミング負債”の量を決定す
る（このタイミング負債は経路のタイミング遅延マイナ
ス（−）その経路に対するタイミング制約に等しい）。

経路のタイミング負債を最適化することは、本方法が個
々のドライバ／負荷対を信号上の全てのポートにではな
く別個に重み付けることを可能ならしめるので、有利で
ある。従って、設計の正のタイミング負債を最小化する
ことによって性能の改善が達成される。

次で設計の物理的配置が、前述あ方法を使用して限定さ
れた区分は深度まで遂行される。この粗区分けがモデル
に関する相関集約情報（例えば論理的設計はモデルを群
に分割することによって所与の信号の負荷を平衡させる
必要があるかも知れず、区分けはモデルの好ましい集約
を行う）によって論理的設計に制約を付課する。

更ｋ、遂行された配置から得られた改善されたタイミン
グ情報に基いて、臨界経路をより良く構戊するために論
理を局部的に再設計することができる。

論理的再設計から、前述と同一区分は方法を使用して最
終配置が遂行される。即ち、物理的及び論理的側設計か
ら使用可能な情報を使用することによってプロセスの各
部分が向上させられ、システムの総合効率及び経済性が
改善される。

従って、論理的設計も物理的設計もある程度の集約或は
クラスタ化を必要とする。従って、論理的及び物理的の
両設計には当然の集約を選択することによって、全ての
制約を満足する最終ハードウェア設計が従来の繰り返し
方策よりも迅速且つ効率的に達成される。

上述の本発明は、回路成分即ちモデルを半導体チップ或
はサブストレートのような支持構造に割当てるために開
発されているが、本方法はこの用途に限定されるもので
はないことを理解されたい。

本方法は、区分間の接続を最小にするように何等かの接
続されたアイテムを区分に分割することにも適用可能で
ある。

【図面の簡単な説明】

第１図は本発明によって操作される論理回路の回路例で
あり、 第１Ａ図は第１図の切断集合の例であり、第２図は半導
体チップ上のモデルの配置を示すブロック線図であり、 第３図は本発明に使用される連結されたりストデータ構
造を示し、 第４図は本発明に使用される連結されたりストデータ構
造を示し、 第５図は区分は方法の動作を説明するために使用される
例であり、 第６図は本発明の対による交換方法を説明するために使
用される例であり、 第７図は本発明の対による交換方法を説明するために使
用される例であり、 第８図は本発明の動作を示すために１吏用される論理回
路の例であり、 第９図は３つの技術セルのブロック線図であり、第１０
図は本発明の動作を示すブロック線図であり、 第１ ある。 １〜７・・・・・・配置スロット、 ｌＯ〜３２．４２〜４８゜ １図は本発明の動作を示すブロック線図で８０．８２・
・・・・・ ＡＮＤゲートモデル、 ３４〜４０．８１・・・・・・ＯＲゲートモデル、５０
、　５１．　５２・・・・・・信号、６０・・・・・・
チップ（サブストレート）、６８．６９・・・・・・順
序付けられたパケットベクトル、７０〜７６・・・・・
・連結されたリスト、９０・・・・・・スワップ活動記
録ベクトル、９２・・・・・・最大累積利得点、 ９４〜１０５・・・・・・スワップ活動記録位置、１０
６・・・・・・累積利得グラフ。 茅６０ 子７■ 筈８ｒｆ１ 牛９因

Claims (1)

1. 【特許請求の範囲】 １、複数の配置スロットを有する支持構造上に配置され
   る論理的設計を形成する複数のモデルのポート間の相互
   接続費用を最小化する方法であって： ａ、支持構造上の複数の配置スロットへのモデルの初期
   割当てを二分して第１及び第２区分を作り； ｂ、前記モデルの電気的特性、及び前記相互接続に対応
   付けられた臨界及び非臨界遅延に基いて前記各モデルの
   部分利得を計算し； ｃ、第１区分内のモデルの部分利得を第１データ構造内
   に、及び第２区分内のモデルの部分利得を第２データ構
   造内に順序付け； ｄ、第１及び第２データ構造の各々から１つ宛の１対の
   配置スロットをスワップして合計最大利得を求め； ｅ、スワップした対及び論理的設計の累積利得を第３デ
   ータ構造上に記憶し、スワップした対をそれらの関連第
   １及び第２データ構造から除去し； ｆ、所定数の配置スロットに関して段階（ｂ）〜（ｅ）
   を繰り返し； ｇ、第３データ構造内に記憶したスワップを再生して最
   大累積利得点に論理的設計の解を回復する 諸段階を含む方法。 ２、ｈ、配置スロットへの初期割当てを無作為化し；ｉ
   、段階（ａ）〜（ｈ）を設定された回数繰り返してこれ
   らの段階を通る各パスに伴う新論理的設計解を決定する 諸段階をも含む請求項１記載の方法。 ３、ｊ、各論理的設計解を記憶し； ｋ、記憶した論理的設計解の所定の選択基準を実現する 諸段階をも含む請求項２記載の方法。 ４、ｊ、各区分毎に段階（ａ）〜（ｉ）を繰り返して第
   １及び第２区分を更に二分する 段階をも含む請求項２記載の方法。 ５、ｋ、各区分が所定数よりも少ない配置スロットを含
   むようになるまで巾優先方式で段階（ａ）〜（ｊ）を繰
   り返す 段階をも含む請求項４記載の方法。 ６、第３データ構造内に記憶したスワップを再生する段
   階が逆順序で遂行される請求項２記載の方法。 ７、プロセッサの動作時間がモデルのポート数に対して
   線形関数である請求項１記載の方法。 ８、スワップ段階が更に； ａ、第１及び第２データ構造から１つ宛各々のデータ構
   造内において最高の部分利得を有する配置スロットを対
   として選択してそれらの合計利得が最大になるか否かを
   決定し； ｂ、前記配置スロット対のスワッピングにより発生する
   相互接続費用の変化を決定することによってスワップし
   た利得を計算し； ｃ、最大合計利得を達成する配置スロット対を選択する
   ための束縛用限界として前記スワップした利得を設定し
   ； ｄ、同一の或は次に最高の部分利得を有する別の配置ス
   ロット対に関して段階（ａ）〜（ｂ）を繰り返し； ｅ、新しいスワップした利得が古い束縛用限界よりも大
   きければ、その束縛用限界をリセットし； ｆ、配置スロット対の部分利得の和が前記束縛用限界よ
   り小さいかまたは等しくなるまで段階（ａ）〜（ｅ）を
   繰り返し、次で現束縛用限界を発生した前記対を最大合
   計利得を有するものとして選択する 諸段階をも含む請求項１記載の方法。 ９、空配置スロットが所定数に等しい部分利得を有する
   請求項１記載の方法。 １０、ｈ、複数の信号を準備し； ｉ、段階（ａ）〜（ｇ）によって遂行されたスワップを
   前記複数の信号カウンタを用いて追跡する 諸段階をも含む請求項１記載の方法。 １１、臨界遅延の相互接続には非臨界遅延よりも大きい
   重みが与えられる請求項１記載の方法。 １２、得られた各区分が所定数よりも少ない配置スロッ
   トを有し、更に； ｌ、ある信号内の信号ポートを区分内に位置決めし； ｍ、前記信号内の最寄りの２つのポートを決定して前記
   信号ポートと前記２つの最寄りポートとの間の各接続毎
   に信号遅延を計算し； ｎ、段階（ｍ）から得られた２つのより小さい信号遅延
   の和からより大きい信号遅延を差引いた差として単一ポ
   ートの遅延寄与を計算し；ｏ、前記単一ポートの無作為
   に異なる初期位置に関して段階（ｍ）及び（ｎ）を繰り
   返し；ｐ、前記単一ポートの遅延に対する寄与が最小と
   なるように前記単一ポートをその配置スロット内へ配置
   する 諸段階をも含む請求項５記載の方法。 １３、モデル上の全てのポートに関して段階（ｍ）〜（
   ｏ）を繰り返し、前記モデルの遅延に対する寄与が最小
   化される配置スロット内に前記モデルを配置する請求項
   １２記載の方法。