(57)【特許請求の範囲】
【請求項１】
セルの配置にパーティショニングを用いる自動配置配線装置において、パーティショニング配置の各カットレベルでブロックに割り当てられたセルを高速な配置手法で仮配置する手段と、
隣接ブロックとの境界を通過できる線分本数Ｎｃを算出する手段と、
ブロック内に置くことのできる所定長さ以上の線分数Ｎｂを算出する手段と、
前記所定長さ以上の線分数の平均長Ｌｂを算出する手段と、
前記境界を通過できる線分本数Ｎｃと、所定長さ以上の線分数Ｎｂと、平均長Ｌｂにもとづき配線混雑度を算出する手段とを具備し、
配線混雑度を見積り、概略配線を行うことを特徴とする自動配置配線装置。
【請求項２】
セルの配置にパーティショニングを用いる自動配置配線装置において、
パーティショニング配置の各カットレベルで、ネットの概略配線経路を保存する手段と、
このネットの配線の接続関係を示す配線木を作成する手段と、
この配線木の端子またはスタイナーポイントを結ぶ部分配線経路を得る手段と、
各部分配線経路について、その配線経路が属していたブロックの領域内で現在のカットレべルでその端子と接続するように経路を配線し直す手段と、
各セルをどのブロックに置くのかを決める手段とを有し、
カットレベルを変更する指示を受信すると、
現在のカットレベルで得られた配線経路を前のカットレベルの配線経路として保持する手段、
前記変更内容に基づき次のカットレベルに変更する際に、保持していた前のレベルの配線経路をもとにして概略配線を行い、配線混雑度と、保持していた経路が通過したブロックの領域内を通る経路を保持するように概略配線経路を次のカットレベルに継承する手段、
とから構成されることを特徴とする自動配置配線装置。
【請求項３】
セルの配置にパーティショニングを用いる自動配置配線装置において、
パーティショニング配置の各カットレベルで、ネットの概略配線経路を保存する手段と、
このネットの配線の接続関係を示す配線木を作成する手段と、
この配線木の端子またはスタイナーポイントを結ぶ部分経路を得る手段と、
各部分配線経路について、その配線経路が属していたブロックの領域内で現在のカットレベルでその端子と接続するように配線経路を配線し直す手段、
タイミングクリティカル・ネットを検出する手段とを有し、
カットレベルを変更する指示を受信すると、
現在のカットレベルで得られた配線経路を前のカットレベルとして保持する手段、
前記変更内容に基づき次のカットレベルに変更するとともに、前のカットレベルの配線結果からタイミングクリティカル・ネットを検出し、そのネットについて配線長を短くするように各セルをどのブロックに置くのか決めるとともに、タイミングクリティカル・ネットに対してはバッファを挿入し、パーティショニングの途中で回路のタイミングを考慮した概略配線経路を次のカットレベルに継承する手段、
とから構成されることを特徴とする自動配置配線装置。
【請求項４】
請求項２において、
概略配置配線を行いその配線結果を保持する手段と、
詳細配線を行う手段を具備し、
概略配置配線を行い、その配線結果を継承して詳細配線を行うことを特徴とする自動配置配線装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＬＳＩの自動配置配線装置に係り、何度も手戻りの生じないように、短ＴＡＴ（Ｔｕｒｎ  Ａｒｏｕｎｄ  Ｔｉｍｅ）でタイミング制約を守ることのできるものに関する。
【０００２】
【従来の技術】
最近ではＬＳＩチップすなわちセルを基板上に位置決めするとき自動配置配線装置を使用して自動的に位置決め及び配線を行っている。ところで近年では回路の集積度の著しい向上により、従来の手法ではタイミング制約を守ることが難しく、何度も手戻りが起るためにＴＡＴが長くなるという問題が生じている。
【０００３】
従来の一般的な自動配置配線方式では、図１６に示す如く、基板上にセルを配置して概略配線、詳細配線を行い、それからタイミング解析つまり配線が長すぎて信号が所定時間以内に伝達されるか否かチェックし、タイミングが長すぎる場合は配置、配線を再度行っていた。
【０００４】
すなわち従来の手法では、セルの位置を細かくきめる配置フェーズと、配線（概略の接続経路を決める概略配線、隣接ブロック間に接続線の通過できる本数や、三次元配線状態を決める詳細配線）フェーズに分かれ、配置が終了してから配線を行う。そして配線が完了してから公知のタイミング解析ツールによりタイミングを解析し、規定時間以内に信号が伝達されない状態となるタイミング制約を違反する場合つまり図１６のタイミングＮｏのときは配置や配線をやり直すという手戻りが起る。
【０００５】
最近のように、回路の集積度が向上し、配線遅延による回路のタイミングへの影響が支配的になっている。そのため、前記図１６に示す場合では、配置配線の初期段階からタイミングを最適化することが必須となっている。
【０００６】
配置フェーズでのタイミング最適化としては、指定されたネットや、配置途中の概略配線長からタイミングクリティカル即ち信号の遅延時間が規定時間を超えるものと判断したネットに対して、そのネットの端子が属するセルを近くに配置したり、ゲートサイジングやバッファ挿入などの処理を行う方法が一般的であった。
【０００７】
また概略・詳細配線フェーズにおいても、タイミング制約を違反するタイミングクリティカル・ネットに対して遅延が最小になるようなトポロジーを生成すなわち接続関係を変更したり、バッファ挿入を行うなどの手法がとられている。
【０００８】
【発明が解決しようとする課題】
ところで、前記図１６に示す如き、従来の自動配置配線方式で、タイミングドリブン配置配線を行う場合、すなわち、タイミングを考慮して配置配線の方向性を決める場合、配置フェーズでは、正確な配線混雑度を見積ることができないため、配線フェーズで得られる経路と異なる経路を出力する場合がある。
【０００９】
例えば図１７に示す如く、端子Ｔ1 −Ｔ2 間に配線する場合、ブロック内ではＲＡＭなどの制約により配線することのできない配線不能領域Ｒ1 、Ｒ2 、Ｒ3 が存在し、配線フェーズでは迂回が避けられないネットがある場合について、配置フェーズの概略配線で点線に示す如く、端子Ｔ1 −Ｔ2 間で最短経路ＬＢを引いてしまうので、この最短経路ＬＢはクリティカルネットとして認識されず、タイミング最適化は行われない。
【００１０】
ところが配線フェーズでの経路は、図１７の実線に示す経路ＬＡとなり、迂回するため長くなる。もしこの経路ＬＡがタイミング違反していれば、バッファ挿入などの手段が必要となるが、配置が完了していて、他の配線も存在するという制約でのバッファ挿入は難しい問題となり、配置まで手戻りが起きる場合がある。
【００１１】
しかし配置フェーズにおいて、上記のようなネットをタイミングクリティカルなネットとして認識し、バッファ挿入を行えば、配線フェーズから配置フェーズでの手戻りを減らせる可能性がある。
【００１２】
従って本発明の目的は、前記の如き問題点を改善するための自動配置配線装置を提供することである。
【００１３】
【課題を解決するための手段】
本発明の原理図を図１に示す。図１において、１は自動配置配線手段、２はネットリスト、３は配置配線出力保持部、４は概略配置配線手段、５は詳細配置配線手段、６は切換手段である。
【００１４】
本発明の前記目的は下記（１）〜（４）により達成することができる。
【００１５】
（１）セルの配置にパーティショニングを用いる自動配置配線装置において、パーティショニング配置の各カットレベルでブロックに割り当てられたセルを高速な配置手法で仮配置する手段と、隣接ブロックとの境界を通過できる線分本数Ｎｃを算出する手段と、ブロック内に置くことのできる所定長さ以上の線分数Ｎｂを算出する手段と、前記所定長さ以上の線分数の平均長Ｌｂを算出する手段と、前記境界を通過できる線分本数Ｎｃと、所定長さ以上の線分数Ｎｂと、平均長Ｌｂにもとづき配線混雑度を算出する手段とを具備し、配線混雑度を見積り、概略配線を行うことを特徴とする。
【００１６】
（２）セルの配置にパーティショニングを用いる自動配置配線装置において、パーティショニング配置の各カットレベルで、ネットの概略配線経路を保存する手段と、このネットの配線の接続関係を示す配線木を作成する手段と、この配線木の端子またはスタイナーポイントを結ぶ部分配線経路を得る手段と、各部分配線経路について、その配線経路が属していたブロックの領域内で現在のカットレべルでその端子と接続するように経路を配線し直す手段と、各セルをどのブロックに置くのかを決める手段とを有し、カットレベルを変更する指示を受信すると、現在のカットレベルで得られた配線経路を前のカットレベルの配線経路として保持する手段、前記変更内容に基づき次のカットレベルに変更する際に、保持していた前のレベルの配線経路をもとにして概略配線を行い、配線混雑度と、保持していた経路が通過したブロックの領域内を通る経路を保持するように概略配線経路を次のカットレベルに継承する手段、とから構成されることを特徴とする。
【００１７】
（３）セルの配置にパーティショニングを用いる自動配置配線装置において、
パーティショニング配置の各カットレベルで、ネットの概略配線経路を保存する手段と、このネットの配線の接続関係を示す配線木を作成する手段と、この配線木の端子またはスタイナーポイントを結ぶ部分経路を得る手段と、各部分配線経路について、その配線経路が属していたブロックの領域内で現在のカットレベルでその端子と接続するように配線経路を配線し直す手段、タイミングクリティカル・ネットを検出する手段とを有し、カットレベルを変更する指示を受信すると、現在のカットレベルで得られた配線経路を前のカットレベルとして保持する手段、前記変更内容に基づき次のカットレベルに変更するとともに、前のカットレベルの配線結果からタイミングクリティカル・ネットを検出し、そのネットについて配線長を短くするように各セルをどのブロックに置くのか決めるとともに、タイミングクリティカル・ネットに対してはバッファを挿入し、パーティショニングの途中で回路のタイミングを考慮した概略配線経路を次のカットレベルに継承する手段、とから構成されることを特徴とする。
【００１８】
（４）前記（２）において、概略配置配線を行いその配線結果を保持する手段と、詳細配線を行う手段を具備し、概略配置配線を行い、その配線結果を継承して詳細配線を行うことを特徴とする。
【００２０】
これにより下記の作用効果を奏する。
【００２１】
（１）隣接ブロックとの境界を通過できる線分本数Ｎｃと、ブロック内に置くことのできる所定長さ以上の線分数Ｎｂと、この所定長さ以上の線分数の平均長Ｌｂにもとづき配線混雑度を求めてこれにもとづき概略配線を行うので、概略配線を精度よく行うことができる。
【００２２】
（２）ネットの配線の接続関係を示す配線木を使用し、その接続関係を継承して部分経路を得るので、接続関係を正確に示すとともに、その端子がドライバであるのかを正確に認識できるので、タイミング制約の対処が正しくできる。
【００２３】
（３）ブロックの分割レベルを＋１したときパーティショニングの途中で前のレベルの配線経路をもとに、配線混雑度を考慮して概略配線を行うことができるので、配線混雑度の大きい領域を避けて概略配線経路を定めることができるので、配線手戻りを避けることができる。
【００２４】
（４）前のレベルの配線結果からタイミングクリティカル・ネットを検出し、このネットについては配線長を短くするようにセルの位置を決めたり、バッファの挿入を行うことができるので、配線手戻りを避けることができる。
【００２５】
（５）配線混雑度や前回の経路の属していたブロックの領域内に現在のレベルでの端子接続をもとにして概略配線し、詳細配線するので、配線手戻りを避けて、短時間で自動配置配線可能なものを提供することができる。
【００２６】
【発明の実施の形態】
本発明の実施の形態を図１を参照し、図２〜図１５にもとづき詳述する。図１は本発明の概略構成図、図２は本発明を適用した自動配置配線装置の動作説明図、図３は本発明の配線混雑度算出状態説明図、図４はブロックの境界を通過できる線分の本数説明図、図５は長さがＬ以上の線分が置かれる領域説明図、図６は配線混雑度を使用した配線状態説明図、図７は本発明の概略配線経路配線手順説明図、図８は本発明の概略配線経路手順の具体的説明図、図９は概略配線経路配線手順を使用した配線状態説明図、図１０は本発明の概略配線経路継承手順説明図、図１１は配線混雑度を考慮した概略配線経路継承作成状態説明図、図１２は本発明のタイミングを考慮した概略配線経路継承手順説明図、図１３はタイミング考慮概略配線経路継承作成状態説明図、図１４は本発明の詳細配線手順説明図、図１５は詳細配線作成状態説明図である。
【００２７】
図１において、１は自動配置配線手段、２はネットリスト、３は配置配線出力保持部、４は概略配置配線手段、５は詳細配置配線手段、６は切換手段である。
【００２８】
自動配置配線手段１はネットリスト２から入力されたセルサイズ、ブロックサイズ、セルの接続状態、タイミング制約情報等によりブロックに割り当てられたセルを高速な配置による仮配置したり、セルの配置やセル間の接続経路を概略配置したり、バッファを挿入したり、概略配置配線結果から詳細配線を行うものである。自動配置配線手段１は、概略配置配線手段４、詳細配置配線手段５、切換手段６等を具備し、プロセッサにより構成される。
【００２９】
ネットリスト２は、基板サイズ、複数のセル毎の物理情報（縦・横のサイズ）、各セルの接続情報、電源やＲＡＭ等の配置位置の物理的制約情報、タイミング制約情報等のネットリスト情報を自動配置配線手段１に入力するものである。
【００３０】
配置配線出力保持部３は、自動配置配線手段１から出力される詳細配線情報あるいは概略配置配線情報を保持するものである。
【００３１】
概略配置配線手段４は、ネットリスト２から入力されたデータにもとづき配線混雑度を算出したり、概略配線経路を算出したり、配線混雑度を考慮した概略配線経路を次のカットレベルに継承したり、回路のタイミングを考慮した概略配線経路を次のカットレベルに継承したりするものである。
【００３２】
詳細配置配線手段５は、概略配置配線経路にもとづき詳細配置配線を行うものである。
【００３３】
切換手段６は、概略配置配線手段４の出力を、詳細配置配線手段５に出力するのか、配置配線出力保持部３に出力するのか選択切換するものである。
【００３４】
図１に示す本発明の自動配置配線装置の動作を図２にもとづき他図を参照して詳述する。
【００３５】
本発明の自動配置配線装置は、図２に示す如く、ネットリスト入力ステップ（ＳＡ）、配線混雑度算出ステップ（ＳＢ）、概略配線経路算出ステップ（ＳＣ）、パーティショニングの途中で配線混雑度を考慮した概略配線経路を次のカットレベルに継承するステップ（ＳＤ）、パーティショニングの途中で回路のタイミングを考慮した概略配線経路を次のカットレベルに継承するステップ（ＳＥ）、配置終了後、配置フェーズで得られた概略配線結果から詳細配線するステップ（ＳＦ）等の動作を行う。
【００３６】
（１）配線混雑度算出ステップについて、
ネットリスト保持部２よりネットリストが入力される。概略配置手段４では、セルの配置で公知のパーティショニング手法を使用し、配置領域を２、４、８・・・と分割し、それぞれの分割フェーズつまりカットレベルで分割された各ブロックに置くセルを決定し、セルの詳細位置を決めるため、セルを仮配置する。
【００３７】
仮配置の手法としては、タイミングの許す範囲で配置移動可能であるという配置制約は守るが最適化を緩めて高速に配置するパーティショニング配置する、例えばミニカット法を使用する。
【００３８】
この高速な配置手法によりセルの仮配置が決定したら、配線層毎に各ブロックの配線混雑度を計算する。配線混雑度は次の４つの値の組で表す。
【００３９】
▲１▼Ｎｃ1 ：ブロックの境界（左あるいは上）を通過できる線分の本数
▲２▼Ｎｃ2 ：ブロックの境界（右あるいは下）を通過できる線分の本数
▲３▼Ｎｂ  ：ブロック内に置ける長さＬ以上の線分数
▲４▼Ｌｂ  ：ブロック内に置ける長さＬ以上の線分の平均長
ただし各層で置ける線分の方向は水平／垂直のどちらか一方だけとする。
【００４０】
図４に示す如く、配線混雑度を計算する対象となる着目ブロックをＢ0 とし、隣接ブロックをＢ1 、Ｂ2 とするとき、ブロックの境界からＤの領域を見てその領域内で置ける線分数を、前記▲１▼、▲２▼のブロックの境界を通過できる線分の本数Ｎｃ1 、Ｎｃ2 とする。
【００４１】
すなわち、ブロックＢ0 とＢ1 の境界には、セルＣ1 〜Ｃ5 、Ｃ6 〜Ｃ10が配置されており、これらの配置関係により得られる通過可能領域の大きさと通過できる線分の幅より、Ｎｃ1 ＝４となる。同様にＮｃ2 ＝６となる。このようにして、ブロックＢ0 とＢ1 の間にはｌ1 〜ｌ4 の配線線分を置くことが可能であり、ブロックＢ0 とＢ2 の間にはｌ5 〜ｌ10の配線線分を置くことが可能であることがわかる。またブロックに例えば電源の如き配線不能の領域が存在する場合、当然のことながらこれを除いて通過可能領域を判断する。
【００４２】
また図５に示す如く、ブロックＢ内にセルＣ1 〜Ｃ18が配置されているとき、このブロックＢの中で長さＬ以上の線分ｌ1 〜ｌ12の置ける空き領域を求めて、これに置ける前記線分の数をカウントし、前記▲３▼のＮｂを求める。図５の例はＮｂ＝１２である。
【００４３】
また、このとき、線分ｌ1 〜ｌ12のそれぞれの長さを調べ、その平均を計算することにより前記▲４▼のＬｂを求めることができる。
【００４４】
以上の４つの値を用いて、配線混雑度を考慮した概略配線（主にブロック間のこと）を行う。概略配線は、配線が混雑しているときには迂回経路も探せるように、迷路法、ラインサーチ法などの既知の配線手法を使用して行う。
【００４５】
このとき前記Ｎｃ1 、Ｎｃ2 、Ｎｂ、Ｌｂを用いて次のコスト計算を行う。
【００４６】
Ａ．ブロック間の線分を引くコスト
あるブロックから上下、または左右に隣接するブロックに長さｌ（英字の小文字のエル）の線分を引くコスト、例えば、右に隣接するブロックに水平で長さｌ（英字の小文字のエル）の線分を引くコストＣｂは下記の式により得られる。
【００４７】
【数１】
0003766278.tif 000002
【００４８】
ただし、Ｎｃ1 、Ｎｂ、Ｌｂは右の隣接ブロックの値、α、βは定数、ｌ（英字の小文字のエル）は概略配線のとき、実際に与えられる値である。
【００４９】
ここでＣｂ＜０なら配線可能であり、絶対値が大きいほど配線コストは低い。一方Ｃｂ＞０又はＣｂ＝０なら配線できないと判断する。
【００５０】
Ｂ．ブロック内の線分を引くコスト
あるブロック内で長さｌ（英字の小文字のエル）の線分を引くコストＣｉｎは下記の式により得られる。
【００５１】
【数２】
0003766278.tif 000003
【００５２】
ただし、Ｎｂ、Ｌｂはこのブロックの値、γは定数である。
【００５３】
ここでＣｉｎ＜０なら配線可能であり、絶対値が大きいほど配線コストは低い。一方Ｃｉｎ＞０又はＣｉｎ＝０なら配線できないと判断する。
【００５４】
迷路法やラインサーチ法の中でこれらのコストを用いて、より配線コストの低い経路を決定する。
【００５５】
図６は、図２の配線混雑度算出ステップ（ＳＢ）において、８分割されたブロックｂ0 〜ｂ7 のブロックｂ1 、ｂ5 、ｂ3 に配置されたセルＡ、Ｂ、Ｃについて、セルＡ−Ｂ、セルＢ−Ｃ間に配線するとき、セルＡ−Ｂに点線で示す如く、最短距離で配線しようとしたとき、斜線領域で示す配線混雑度の高い領域がブロックｂ1 、ｂ5 間に存在するため、実線の如く、配線した例を示す。セルＢ−Ｃ間の実線も配線混雑度の高い領域が、斜線領域で示す如く、ブロックｂ1 、ｂ2 間に存在したことを考慮して実線の如く配線した例を示す。
【００５６】
このように配置の初期の段階から、なるべく正確な配線混雑度を見積り、迂回が避けられないネットを予測できる。
【００５７】
実際に、図３に示すフローにより、図１の自動配置配線手段１の動作状態を図２の配線混雑度算出ステップ（ＳＢ）について説明する。
【００５８】
ネットリストとしては、前記の如く、セルサイズ、ブロックサイズ、セルの接続情報、タイミング制約情報等が入力される。これにより、セルがブロックに高速配置され、このセルの接続情報であるネット（セルＡの端子Ｏｕｔ、セルＢの端子Ｉｎ）・・・の如く、接続関係が得られる。また配線経路Ｐとしてはこれを構成するセグメント（Ｓｅｇ）で示され、配線経路Ｐが複数のｍ本の線分で構成されているときは、
Ｐ＝｛Ｓｅｇ１、Ｓｅｇ２・・・Ｓｅｇｍ｝
の如く示される。
【００５９】
Ｓ１．まずネットリスト２よりネットリストが入力される。
【００６０】
Ｓ２．概略配置配線手段４では、これにより、例えばミニカット法によりブロックに割り当てられたセルを高速配置する。これにより前記セルの接続関係、配線経路Ｐ等が得られる。
【００６１】
Ｓ３．概略配置配線手段４は、ネットｉ＝０を選ぶ
Ｓ４．これによりネットｉ＝０を構成する配線経路の候補Ｐ0 が選ばれ、Ｐ0 を構成する。
【００６２】
Ｓ５．この配線経路Ｐ0 を構成するセグメントＳｅｇ0 が選ばれる。
【００６３】
Ｓ６．このセグメントＳｅｇ0 の長さｌ（英字の小文字のエル）と、その通過ブロックｂが抽出される。
【００６４】
Ｓ７．この通過ブロックに対し、前記▲１▼のブロックの境界（左あるいは上）を通過できる線分本数Ｎｃ1 を算出する。
【００６５】
Ｓ８．同じくこの通過ブロックに対し、前記▲２▼のブロックの境界（右あるいは下）を通過できる線分本数Ｎｃ2 を算出する。
【００６６】
Ｓ９．次にこの通過ブロックに対し、前記▲３▼のブロック内に置ける長さＬ以上の線分数Ｎｂを算出する。
【００６７】
Ｓ１０．そして前記▲４▼のこの通過ブロック内に置ける長さＬ以上の前記各線分の平均長Ｌｂを算出する。
【００６８】
Ｓ１１．それから前記Ｎｃ1 、Ｎｃ2 、Ｎｂ、Ｌｂを用い、
右に隣接するブロックに水平で長さｌ（英字の小文字のエル）の線分を引くコストＣｂ0 は
【００６９】
【数３】
0003766278.tif 000004
【００７０】
で示され、
左に隣接するブロックに水平で長さｌ（英字の小文字のエル）の線分を引くコストＣｂ1 は
【００７１】
【数４】
0003766278.tif 000005
【００７２】
で示される。
【００７３】
Ｓ１２．そして前記Ｃｂ0 、Ｃｂ1 がいずれも負であれば、配線可能であると判断する。そして次のＳ１３に移行する。しかもその絶対値が大きい程配線コストは低い。しかし前記Ｃｂ0 、Ｃｂ1 の少なくとも一方が正または０であれば、その正または０のものに対しては配線できないと判断する。そして前記Ｓ４に戻り、他の配線経路の候補Ｐを選ぶことになる。
【００７４】
Ｓ１３．前記Ｓ１２において、Ｃｂ0 、Ｃｂ1 がいずれも負であれば、両隣りのブロックに対し配線可能であると判断し、セグメントの番号を＋１して次のセグメントを抽出する。
【００７５】
Ｓ１４．このように各セグメントに対して同様の処理を行う。そして１セグメントに対する処理が終了したとき、全セグメント（セグメント数＝ｍ）に対して処理を行ったか否かを判断する。全セグメントに対して処理が終了すれば、そのネットに対する処理が終了したものと判断し、次のネットを抽出する。
【００７６】
Ｓ１５．このようにして配線可能と判断されると、これにもとづきネットの配線が行われる。そして配線情報としてブロックに入るセルと、ネットτがどのブロックを通過するのかを示す配置、配線情報が得られる。
【００７７】
Ｓ１６．このようにして全ネットに対する処理が終了したか否か判断し、処理すべきネットが残っていれば前記Ｓ３に戻る。このようにして全ネットに対する処理が終了すれば、図２に示す配線混雑度算出ステップ（Ｓ１３）が終了する。
【００７８】
迷路法やラインサーチ法の中で前記のコストを用いてより配線コストの低い経路を決定することができる。
【００７９】
（２）概略配線経路算出ステップについて
パーティショニング配置の各カットレベルで、セルの位置は割り当てられたブロックの中心にあると仮定して、前記の如く、前記（１）の配線混雑度算出ステップにより概略配線する。
【００８０】
そしてこの経路を次のカットレベルまで保存する。次のカットレベルでは、前回よりもブロックが細かくなっており、セルの位置が違うので、概略経路を配線し直す必要がある。このとき保存していた経路を用いて次の手順で配線する。
【００８１】
ａ．図８（Ａ）で示す、保存していた前回のカットレベルでの経路を、同（Ｂ）に示す如く、ドライバ（図８の例ではＡがドライバ）をルートとする配線木で見て、端子あるいはスタイナーポイント（Ｓ）間を結ぶ経路に分割する。
【００８２】
ｂ．前記ａで求めた各経路について、その経路が属していた前回のカットレベルでのブロックの領域内で経路を引き直し、図８（Ｃ）に示す如き配線を行う。
【００８３】
すなわち図８（Ａ）に対してカットレベルを＋１して各ブロックを２分割したとき、同（Ａ）のブロックｂ1 は同（Ｃ）のブロックｂ11、ｂ12に分割され、同様にブロックｂ2 はブロックｂ21、ｂ22に、ブロックｂ5 はブロックｂ51、ｂ52に、ブロックｂ7 はブロックｂ71、ｂ72に、ブロックｂ8 はブロックｂ81、ｂ82に分割される。
【００８４】
このとき端子Ａがドライバなので、これをルートとして、図８（Ｂ）に示す如き配線木を得る。なお図８（Ｂ）でＳはスタイナーポイントである。そしてこの配線木で得られた各経路について、図８（Ｃ）に示す次のカットレベルのブロックに端子やスタイナーポイントの配置、配線経路等が引き直されるが、このとき前回のカットレベルのブロック内で、これらが行われる。
【００８５】
すなわち、図８（Ａ）に示す如く、前回のカットレベルでは端子Ａはブロックｂ2 に位置し、端子Ｂはブロックｂ8 に位置していたので、この関係は継承され、次のカットレベルでは端子Ａはブロックｂ21、ｂ22のいずれかに位置され、同様に端子Ｂはブロックｂ81、ｂ82のいずれかに位置されるものとなる。
【００８６】
同様に、図８（Ａ）に示すブロックｂ1 、ｂ5 、ｂ7 を通る配線は、ブロックｂ11、ｂ12、ｂ51、ｂ52、ｂ71、ｂ72のいずれかを通過することになる。これらのブロック領域の継承や、最短距離の配線ということから、図８（Ｃ）の如く、端子Ａ、Ｂとその間の配線が引き直されることになる。
【００８７】
実際に動作するときは、図８（Ｂ）に示す配線木は出力されないので、図９（Ａ）→（Ｂ）に示す如く、出力される。すなわち、図９（Ａ）に示す如く、前回のカットレベルでは、部分経路Ａ〜Ｂ、Ａ〜Ｓ、Ｓ〜Ｃ、Ｓ〜Ｄが存在するが、次のカットレベルでは、この配線の接続関係を保つのみならず、ブロック関係も継承された新しい端子、配線の位置で、同（Ｂ）に示す如く、配線されることになる。
【００８８】
次に図７に示すフローにより、図１の自動配置配線手段１の動作状態を、図２の概略配線経路算出ステップ（ＳＣ）について説明する。
【００８９】
Ｓ２１．最初にネット抽出用のカウンタを初期化し、カウント値を「０」にする。
【００９０】
Ｓ２２．そしてこれにより、前記図２の配線混雑度算出ステップにもとづき得られた概略配置配線情報の最初のネットを選ぶ、これにより例えば図８（Ａ）に示す如き、概略配置配線図が得られ、これを保持する。
【００９１】
Ｓ２３．このようにして保持した前回のカットレベルの経路を、図８（Ｂ）に示す如く、そのネットのドライバ（この図の例では端子Ａ）をルートとする配線木として復元する。
【００９２】
Ｓ２４．この配線木の端子Ａ、Ｂ、Ｃ、ＤまたはスタイナーポイントＳを結ぶ部分経路を、図８（Ｂ）の点線で示す如く得る。
【００９３】
Ｓ２５．各部分経路について、その経路が属していたブロックの領域内で、現在のレベルでの端子と接続するように経路を配線し直す。そして次のネットを選ぶ。
【００９４】
Ｓ２６．そして選ばれたネットに対し前記Ｓ２３以下の処理が行われる。全ネットに対しこのような経路配線が行われたとき、このステップは終了する。
【００９５】
（３）パーティショニングの途中で配線混雑度を考慮した概略配線経路を次のカットレベルに継承するステップについて
前記（１）、（２）を用いて、パーティショニングの各カットレベルで、配線混雑度を考慮した概略配線経路を次のカットレベルに継承させ自動配置配線を行う。
【００９６】
図１１は、図２のパーティショニングの途中で配線混雑度を考慮した概略配線経路を次のカットレベルに継承した実施例である。すなわち図１１（Ａ）に示す如く、ブロックｂ1 、ｂ2 、ｂ3 、ｂ4 、ｂ5 にセルＡ、Ｃ、Ｂ及び配線経路が位置するとき、図１１（Ｂ）に示す如く、カットレベルを上げて２分割したとき、ブロックｂ52の配線混雑度が大きく、これを迂回することが必要と判断されると、セルＡはブロックｂ1 に位置し、セルＣはブロックｂ2 に位置し、セルＢはブロックｂ3 に位置したこと、ブロックｂ1 はブロックｂ11、ｂ12に、ブロックｂ2 はブロックｂ21、ｂ22、ブロックｂ3 はブロックｂ31、ｂ32に分割されたこと、及び配線経路がブロックｂ1 −ｂ3 及びブロックｂ3 −ｂ4 −ｂ5 −ｂ2 に位置したこと、ブロックｂ4 はブロックｂ41、ｂ42に、ブロックｂ5 はブロックｂ51、ｂ52に分割されたこと等が継承され、またブロックｂ52の配線混雑度が大きくこれを迂回することが必要なこと等が判断されて、図１１（Ａ）に示す概略配置配線が同（Ｂ）に示す状態となる。各セルの位置決めでも前記継承が行われる。
【００９７】
次に図１０に示すフローにより、図１の自動配置配線手段１の動作状態を、図２のパーティショニングの途中で配線混雑度を考慮した概略配線経路を次のカットレベルに継承するステップ（ＳＤ）について説明する。
【００９８】
Ｓ３１．例えば図１１（Ａ）に示す概略配置配線状態を保持しているとき、分割つまりカットレベルを１レベル進める。
【００９９】
Ｓ３２．各セル（又は端子）Ａ、Ｂ、Ｃをどのブロックに置くのか決める。これによりセルＡはブロックｂ12に、セルＢはブロックｂ32に、セルＣはブロックｂ22に位置決めされる。
【０１００】
Ｓ３３．ネット毎に、保持していた前のレベルの配線経路をもとに、概略配線を行い得られた経路を保持する。例えば初めセルＡ−Ｂ間の配線経路はブロックｂ1 −ｂ3 であり、セルＢ−Ｃ間の経路はブロックｂ3 −ｂ4 −ｂ5 −ｂ2 であったことをもとに、ブロックｂ1 がブロックｂ11、ｂ12に分割されたこと、ブロックｂ2 がブロックｂ21、ｂ22に分割されたこと、ブロックｂ3 ブロックｂ31、ｂ32に分割されたこと、ブロックｂ4 がブロックｂ41、ｂ42に分割されたこと、ブロックｂ5 がブロックｂ51、ｂ52に分割されたことが継承される。この継承により元のブロックｂ1 の配線経路は分割後のブロックｂ11、ｂ12の一方または双方を通過することが必要であり、ブロックｂ2 の配線経路はブロックｂ21、ｂ22の一方または双方を通過するこが必要であり、ブロックｂ3 の配線経路はブロックｂ31、ｂ32の一方または双方を通過するこが必要である。他のブロックについても同様である。またブロックｂ52においては配線混雑度が大きく、迂回が必要と判断される。この結果、図１１（Ａ）に対しては次のカットレベルで同（Ｂ）に示す概略配線経路が得られ、これが保持される。
【０１０１】
Ｓ３４．このとき、規定の分割回数は終了していなかったので、再び前記Ｓ３１に戻り、図１１（Ｂ）に示す概略配線経路に対し、カットレベルが＋１された同様の処理が行われ、図１１（Ｃ）に示す概略配線経路が得られる。なお、図１１（Ｃ）ではブロックｂ321 に大きな配線混雑度が存在したので、これを迂回した状態となる。このような処理があらかじめ規定された分割回数行われたのち終了となる。
【０１０２】
（４）パーティショニングの途中で回路のタイミングを考慮した概略配線経路を次のカットレベルに継承するステップについて、
前記（１）、（２）、（３）を用いて、パーティショニングの各カットレベルで回路のタイミングを考慮した概略配線経路を次のカットレベルに継承させて自動配置配線を行う。
【０１０３】
図１３は、図２のパーティショニングの途中で回路のタイミングを考慮した概略配線経路を次のカットレベルに継承した実施例である。図１３（Ａ）はカットが８分割のときセル（端子）ＢからセルＣへの経路が長くなり、配線遅延が大きくなりタイミング制約に違反するのでこれを防止するために同（Ｂ）に示す如く、バッファＢＦが挿入される。
【０１０４】
このバッファＢＦの挿入経路は、８分割以降のカットレベルでも、バッファＢＦとの接続関係を保つように概略配線される。図１３（Ｃ）は３２分割されたときの概略配線経路を示している。
【０１０５】
次に図１２に示すフローにより、図１の自動配置配線手段１の動作状態を、図２のパーティショニングの途中で回路のタイミングを考慮した概略配線経路を次のカットレベルに継承するステップ（ＳＥ）について説明する。
【０１０６】
Ｓ４１．分割を１レベル進める。
【０１０７】
Ｓ４２．前のカットレベルで、ネットの長さによりタイミングクリティカルと認識されたネットの配線長が短くなるように、各セルを分割されたどのブロックに置くのか決める。
【０１０８】
Ｓ４３．ネット毎に保持していた前のレベルの配線経路をもとに、概略配線を行い、得られた経路を保持する。
【０１０９】
Ｓ４４．この得られた概略経路からタイミングのクリティカルなネットを認識し、タイミングのクリティカルなネットに対してはバッファを挿入する。
【０１１０】
Ｓ４５．このとき規定の分割回数が終了しているか否かを判断し、終了していなければ前記Ｓ４１に戻り、規定回数に達していれば終了する。
【０１１１】
（５）配置終了後、配置フェーズで得られた概略配置配線結果から詳細配線するステップについて
前記（１）、（２）、（３）、（４）を用いて得られた概略配置配線結果より詳細配線を行う。例えば図１５（Ａ）に示す如く、配置フェーズ終了時点で得られた概略配線に対し、例えば迷路法等の手法により詳細配線を行い、同（Ｂ）に示す如き、詳細配線経路を得るものである。
【０１１２】
次に図１４に示すフローにより、図１の自動配置配線手段１の動作状態を、図２の配置終了後、配置フェーズで得られた概略配線結果から詳細配線を行うステップ（ＳＦ）について説明する。
【０１１３】
Ｓ５１．前記（１）、（２）、（３）、（４）の手法によりセル（端子）を配置し、概略配線する。これにより、例えば図１５（Ａ）に示す如き概略配置配線経路が得られる。
【０１１４】
Ｓ５２．次にこの概略配置配線経路に対し、例えば迷路法により詳細配線を行い、図１５（Ｂ）に示す如き、詳細配線経路を得る。
【０１１５】
Ｓ５３．それから各ネットに対してタイミング解析を行う。
【０１１６】
Ｓ５４．タイミング解析の結果がタイミング制約を満たすものでなければ前記Ｓ５１、Ｓ５２に戻り概略配置配線あるいは詳細配線を再び行うことになる。そしてタイミング制約を満たすものであれば、本発明にかかる配置配線処理が終了する。
【０１１７】
このように本発明によれば、従来の方式でみられた配置フェーズで生成される配線パターンと、配線フェーズで生成される配線パターンが異なるために配置フェーズにおけるタイミング最適化が効率よく行われないという問題点が解決される。
【０１１８】
また配線経路を継承するために、最適化の方向が安定し、配置配線フローの収束性を高めることができる。
【０１１９】
本発明では、配置フェーズで行う概略配線において、仮配置を行うことにより混雑度の見積り精度を上げ、また配置初期段階の経路を継承することにより、実際の配線結果とより近いものになるようにする。また、配置の段階でクリティカルネットと認識した場合には、配置の工夫でクリティカルネットの配線長を短くするようにする。これらの処理により、従来方式で問題となっている、詳細配線後のタイミング解析から配線あるいは配置フェーズへの手戻りを減らすことができる。
【０１２０】
本発明の実施の態様を下記に付記する。
【０１２１】
（付記１）セルの配置にパーティショニングを用いる自動配置配線装置において、パーティショニング配置の各カットレベルでブロックに割り当てられたセルを高速な配置手法で仮配置する手段と、隣接ブロックとの境界を通過できる線分本数Ｎｃを算出する手段と、ブロック内に置くことのできる所定長さ以上の線分数Ｎｂを算出する手段と、前記所定長さ以上の線分数の平均長Ｌｂを算出する手段と、前記境界を通過できる線分本数Ｎｃと、所定長さ以上の線分数Ｎｂと、平均長Ｌｂにもとづき配線混雑度を算出する手段とを具備し、配線混雑度を見積り、概略配線を行うことを特徴とする。
【０１２２】
（付記２）セルの配置にパーティショニングを用いる自動配置配線装置において、パーティショニング配置の各レベルで、ネットの概略配線経路を保存する手段と、このネットの配線の接続関係を示す配線木を作成する手段と、この配線木の端子またはスタイナーポイントを結ぶ部分経路を得る手段と、各部分経路について、その経路が属していたブロックの領域内で現在のカットレべルでその端子と接続するように経路を配線し直す手段とを具備し、保存していた経路が通過したブロックの領域内で概略配線を行うことを特徴とする。
【０１２３】
（付記３）セルの配置にパーティショニングを用いる自動配置配線装置において、前の分割レベルで得られた経路を保持する手段と、分割レベルを＋１する手段と、各セルをどのブロックに置くのかを決める手段を具備し、ネット毎に、保持していた前のレベルの配線経路をもとにして概略配線を行い、配線混雑度と、保持していた経路が通過したブロックの領域内を通る経路を保持することを特徴とする。
【０１２４】
（付記４）セルの配置にパーティショニングを用いる自動配置配線装置において、前の分割レベルで得られた経路を保持する手段と、タイミングクリティカル・ネットを検出する手段と、分割レベルを＋１する手段と、前のレベルの配線結果からタイミングクリティカル・ネットを検出し、そのネットについて配線長を短くするように各セルをどのブロックに置くのか決めるとともに、タイミングクリティカル・ネットに対してはバッファを挿入する手段を具備し、ネット毎に、保持していた前のレベルの配線経路をもとに概略配線を行い、配線混雑度と、保持していた経路が通過したブロックの領域内を通る経路を保持することを特徴とする。
【０１２５】
（付記５）前記（付記３）において、概略配置配線を行いその配線結果を保持する手段と、詳細配線を行う手段を具備し、概略配置配線を行い、その配線結果を継承して詳細配線を行うことを特徴とする。
【０１２６】
（付記６）前記（付記３）、（付記４）により概略配置配線を行いその結果を保持する手段と、詳細配線を行う手段を具備し、この概略配置配線を継承して詳細配線を行うことを特徴とする。
【０１２７】
【発明の効果】
本発明により、下記の効果を奏することができる。
【０１２８】
（１）隣接ブロックとの境界を通過できる線分本数Ｎｃと、ブロック内に置くことのできる所定長さ以上の線分数Ｎｂと、この所定長さ以上の線分数の平均長Ｌｂにもとづき配線混雑度を求めてこれにもとづき概略配線を行うので、概略配線を精度よく行うことができる。
【０１２９】
（２）ネットの配線の接続関係を示す配線木を使用し、その接続関係を継承して部分経路を得るので、接続関係を正確に示すとともに、その端子がドライバであるのかを正確に認識できるので、タイミング制約の対処が正しくできる。
【０１３０】
（３）ブロックの分割レベルを＋１したときパーティショニングの途中で前のレベルの配線経路をもとに、配線混雑度を考慮して概略配線を行うことができるので、配線混雑度の大きい領域を避けて概略配線経路を定めることができるので、配線手戻りを避けることができる。
【０１３１】
（４）前のレベルの配線結果からタイミングクリティカル・ネットを検出し、このネットについては配線長を短くするようにセルの位置を決めたり、バッファの挿入を行うことができるので、配線手戻りを避けることができる。
【０１３２】
（５）配線混雑度や前回の経路の属していたブロックの領域内に現在のレベルでの端子接続をもとにして概略配線し、詳細配線するので、配線手戻りを避けて、短時間で自動配置配線可能なものを提供することができる。
【図面の簡単な説明】
【図１】本発明の概略構成図である。
【図２】本発明を適用した自動配置配線装置の動作説明図である。
【図３】本発明の配線混雑度算出状態説明図である。
【図４】ブロックの境界を通過できる線分の本数説明図である。
【図５】長さＬ以上の線分が置かれる領域説明図である。
【図６】配線混雑度を使用した配線状態説明図である。
【図７】本発明の概略配線経路配線手順説明図である。
【図８】概略配線経路手順の具体的説明図である。
【図９】概略配線経路配線手順を使用した配線状態説明図である。
【図１０】本発明の概略配線経路継承手順説明図である。
【図１１】配線混雑度を考慮した概略配線経路継承作成状態説明図である。
【図１２】本発明のタイミングを考慮した概略配線経路継承手順説明図である。
【図１３】タイミング考慮概略配線経路継承作成状態説明図である。
【図１４】詳細配線手順説明図である。
【図１５】詳細配線作成状態説明図である。
【図１６】従来の自動配置配線方式説明図である。
【図１７】迂回発生状態説明図である。
【符号の説明】
１  自動配置配線手段
２  ネットリスト
３  配置配線出力保持部
４  概略配置配線手段
５  詳細配置配線手段
６  切換手段
【図１】
0003766278.tif 000006
【図２】
0003766278.tif 000007
【図３】
0003766278.tif 000008
【図４】
0003766278.tif 000009
【図５】
0003766278.tif 000010
【図６】
0003766278.tif 000011
【図７】
0003766278.tif 000012
【図８】
0003766278.tif 000013
【図９】
0003766278.tif 000014
【図１０】
0003766278.tif 000015
【図１１】
0003766278.tif 000016
【図１２】
0003766278.tif 000017
【図１３】
0003766278.tif 000018
【図１４】
0003766278.tif 000019
【図１５】
0003766278.tif 000020
【図１６】
0003766278.tif 000021
【図１７】
0003766278.tif 000022