(57)【特許請求の範囲】
【請求項１】
チップを分割し、分割したそれぞれのブロックにセルを割り当てるパーティショニング処理を繰り返すことによりセル位置を決定するＬＳＩ配置方法であって、
上記パーティショニングを行う前に、セルや外部端子等の位置制約条件から、ネットがカットされたときに増加する線長を見積もり、
見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出し、抽出されたパスに対してマッピングを行い、その結果位置によってネットがカットされたときのコストを決定し、コストの合計量が最小になるようにパーティショニング処理を行う
ことを特徴とする遅延制約を考慮したＬＳＩ配置方法。
【請求項２】
クリティカルパスに属するセルが多すぎたため、カット数が一定の値を越えるとき、マッピング結果位置に基づいてネットがカットされたときのコストを下げる
ことを特徴とする請求項１の遅延制約を考慮したＬＳＩ配置方法。
【請求項３】
１ブロックに割り当てなければならないセル数またはセルの面積が一定の値を越えたとき、マッピング結果位置に基づいてネットがカットされたときのコストを下げる
ことを特徴とする請求項１または請求項２の遅延制約を考慮したＬＳＩ配置方法。
【請求項４】
見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出するに際し、あるネットの中で、そのネットを駆動するピンにおけるスラックよりも大きいスラックを待つピンを無視してクリティカルパスを抽出する
ことを特徴とする請求項１，２または請求項３の遅延制約を考慮したＬＳＩ配置方法。
【請求項５】
チップを分割し、分割したそれぞれのブロックにセルを割り当てるパーティショニング処理を繰り返すことによりセル位置を決定するＬＳＩ配置システムであって、
位置制約に接続されたクリティカルパスを抽出するクリティカルパス抽出手段と、
位置制約に接続されたクリティカルネットのマッピングを行い、ネットの重みを決定するマッピング・重み決定手段とを備え、
上記パーティショニングを行う前に、上記クリティカルパス抽出手段は、セルや外部端子等の位置制約条件から、ネットがカットされたときに増加する線長を見積もり、見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出し、
上記マッピング・重み決定手段は、上記クリティカルパス抽出手段により抽出されたパスに対してマッピングを行いネットの重みを決定し、
上記マッピング・重み決定手段により決定した結果位置および重みによってネットがカットされたときのコストを決定し、コストの合計量が最小になるようにパーティショニング処理を行う
ことを特徴とする遅延制約を考慮したＬＳＩ配置システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
ＬＳＩの設計では、まず、ＡＮＤ，ＯＲなどのセルと、セル間の接続（ネット）を決定し（論理設計）、次にセルのチップ上の位置を決定し（配置）  、最後に、セル間のネットをどう引くかを決定する（配線）。ＬＳＩがある周波数で動作するためには、信号の到達時間がある一定の範囲内になければならないがこの遅延は論理設計・配置・配線のそれぞれによって影響を受けるので、設計の各フェーズにおいて、信号の伝搬にかかる遅延が制約条件を満たすような結果を出力することが要求される。
本発明は、上記した遅延制約を満たすようなＬＳＩ上のセル配置を求める方法およびシステム関する。
【０００２】
【従来の技術】
ＬＳＩの配置においてよく使用される方式としてパーティショニングベースと呼ばれる方式が存在する。この方式では、チップを分割して、分割したそれぞれのブロックにセルを割り当てることを繰り返す。最終的に、各ブロックが１つ程度のセルしか含まない程度まで細かく分割されたところで、セルの位置が決定される。
【０００３】
図１５にパーティショニングベース配置方式の基本的な考え方を示す。同図（ａ）に示すようにチップ全体を最初に２分割する。分割する線をカットラインと呼ぶ。そして、全セルを２つの領域のそれぞれに振り分ける。
セルを振り分ける基準は、セルを２つの領域にわけた結果、２つの領域にまたがって存在するネットの数をコストとし、このコストが最小になるようなグループ分けを採用する方法（ｍｉｎ−ｃｕｔ）がよく用いられる。そのような処理を行うアルゴリズムとしては、ＦＭ法などが知られている。
このとき、２つの領域に振り分けるセルの面積の合計値が一定の範囲内におさまることを条件にすることにより、セルがどちらかの領域に片寄らないように操作する。
【０００４】
例えば領域１，２の面積をそれぞれＳ１，Ｓ２、領域１，２に割り当てられたセルの面積の合計をｓ１，ｓ２とすると、次の式（１）が満たされていることを条件とする。
｜ｓ１／Ｓ１−ｓ２／Ｓ２｜≦α…（１）
（αはある正の定数）
上記と同様に、図１５（ｂ）〜（ｄ）に示すように、横、次に縦、という順序で分割を繰り返していくことにより、セルの位置を決定する。
【０００５】
パーティショニングベースの配置方式で、遅延制約を満たす配置結果を得るためには、以下のような手法が用いられる。
図１６において、セルＡからセルＢまで信号がある定められた時間内に到達しなければならないとする。ここで、セルＡ〜Ｂまでの信号の実際の到達時間が制約時間ぎりぎり、あるいはすでに制約を越えていて、遅延制約を満たすために、可能な限り配線長を縮めて遅延を短くしなければならないときに、セルＡ〜Ｂの間のパスをクリティカルパスと呼ぶ。
【０００６】
クリティカルパスに属するネットがカットされたときのコストを通常よりも増加させてパーティショニングを行うことにより、結果的に、クリティカルパスに属するネットはカットされにくくなるため、その線長が短くなり、遅延が制約を越えにくくなる。クリティカルパスを見つけるためには、スラックを使用する。パス上の各点におけるスラックは、以下の計算式（２）で計算される。
0003544893.tif 000002
例えば、図１６において、〔ネット＋セルの遅延時間〕が、同図に示すようにそれぞれ１，２，１，３，１ナノ秒であるとすると、出発点からの遅延時間の累計は、同図に示すように０，１，３，４，７，８ナノ秒となる。ここで、遅延制約を満たすに必要な到達時間が同図に示すように１，２，４，５，８，９ナノ秒であるとすると、スラックは、このパス上ではどこでも１ナノ秒となる。
【０００７】
なお、分岐が存在すると、図１７に示すようにスラックはパスの途中で変化する。すなわち、同図に示すように、セルＦの到達時間が８ナノ秒で要求時間が９ナノ秒の場合、セルＡ〜Ｂ〜Ｆのパルのスラックは１ナノ秒であるが、セルＣの到達時間が７ナノ秒で要求時間が９ナノ秒の場合、セルＢからセルＣまでの部分のスラックは２ナノ秒となる。また、セルＥにおける要求時間と到達時間の差が５ナノ秒の場合には、セルＤからセルＥまでのパスのスラックは、５ナノ秒となる。
スラックの値が正であればそのパスの遅延は、スラックの値まで増加しても制約条件を満たすことになる。もし、スラックの値が負であればそのパスはもっと縮めなければならないことがわかる。あるネットを駆動しているピンにおけるスラックの値がある一定の値εを下回っていたとき、そのネットはクリティカルパスに入っているとみなされる。
【０００８】
従来システムのパーティショニングベース配置方式においては、図１８に示すように処理を行っていた。なお従来システムについては、例えば、Ｍ．Ｂｕｒｓｔｅｉｎ，Ｍ．Ｎ．Ｙｏｕｓｓｅｆ．”ＴｉｍｉｎｇＩｎｆｌｕｅｎｃｅｄ  Ｌａｙｏｕｔ  Ｄｅｓｉｇｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｃｅ，ｐｐ１２４−１３０，１９８５．  〔参考文献１〕を参照されたい。
同図に示すように、まず、ネットリスト、初期スラック、タイミング制約を与えて、最初に各ネットにおけるスラックを計算して、スラックの値に基づいて、ネットのコストを計算する（ステップＳ１）。
そして、コストが最小になるようにパーティンョニング処理を実行する（ステップＳ２）。パーティショニングが終了すると、分割が十分細かくなったかを調べ（ステップＳ３）、分割が十分細かくなれば処理を終了する。
【０００９】
分割が十分細かくなっていない場合には、次のパーティショニングのために、ネットの概略配線を行う（ステップＳ４）。
ここで概略配線を行う理由は、遅延が配線の形状に依存するためである。ネットが混んでいる領域があって、配線するためには迂回しなければならない場合は、その分、線長が伸びることになり、遅延も増加することになる。
概略配線を行うことにより、各ネットの配線パターン、線長を見積もり、その結果に基づいて、ステップＳ５のように各ネットにおける遅延を計算し、スラックを計算することができる。
ステップＳ５において、上記のように遅延・スラック計算を行ったのち、ステップＳ１に戻り、求めた新しいスラックを次段のパーティショニングで用い、上記処理を繰り返す。
【００１０】
パーティショニングベースで遅延制約を満たす配置を求めるシステムに応用できる手法としては、例えば、「Ｒ−Ｓ  Ｔｓａｙ，Ｊ．Ｋｏｅｈｌ．”Ａｎ  Ａｎａｌｙｔｉｃ  Ｎｅｔ  Ｗｅｉｇｈｔｉｎｇ  Ａｐｐｒｏａｃｈ  ｆｏｒ  Ｐｅｒｆｏｍａｎｃｅ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ｉｎ  Ｃｉｒｃｕｉｔ  Ｐｌａｃｅｍｅｎｔ”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ２８ｔｈＤｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，ｐｐ  ６２０−６２５，１９９１．  」〔参考文献２〕で述べられている手法もある。しかし、近年、ｍｉｎ−ｃｕｔアルゴリズムの性能が飛躍的に向上したため、上記手法で得られる配置結果は、ｍｉｎ−ｃｕｔアルゴリズムによって得られるものと比較して、配線がしにくくなっているという問題が存在している。
【００１１】
【発明が解決しようとする課題】
ＬＳＩの配置では、外部入力端子の位置、フロアプラン、マクロセルの配置、あるいは前回までのパーティショニングによってすでにカットされているネットなどにより、位置の制約が存在する。
位置の制約が存在する場合とは、例えば、図１９に示すように、固定セルがある場合、フロアプランにより配置できる位置に制約がある場合、あるいは、外部端子等である。
さらに、図２０に示すように、前段までのパーティショニングによって分割されているネットは、分割点を通過しなければならないので位置制約が生ずる。
【００１２】
しかしながら、従来のｍｉｎ−ｃｕｔアルゴリズムベースの手法では、これらの存在が考慮されない。
例えば、図２１に示すように、同じスラックを持つネットでも、同図ａ，ｂに示すようにカットラインからの距離が遠い位置におかなければならないセルに接続している場合と、同図ｃに示すように、そのような制約がない場合では、そのネットがカットされたときの遅延の増加量が異なる。
したがって、ネットがカットされたときのコストを決定するために、スラックだけでなく、上記位置の制約も考慮する必要がある。
前記した参考文献２でのべられている手法では、位置制約の存在は考慮できるが、ｍｉｎ−ｃｕｔアルゴリズムの性能を活用することができず、配線性が悪くなるという問題点が存在する
本発明は上記した位置制約がある場合でも、配線性を確保しながら遅延制約を満たしやすい配置を定めることができるＬＳＩの配置方法およびシステムを提供することである。
【００１３】
【課題を解決するための手段】
図１は本発明の概要を説明する図である。同図に示すように、本発明では以下のようにして、前記課題を解決する。
（１）チップを分割し、分割したそれぞれのブロックにセルを割り当てるパーティショニング処理を繰り返すことによりセル位置を決定するＬＳＩ配置方法において、上記パーティショニングを行う前に、セルや外部端子等の位置制約条件から、ネットがカットされたときに増加する線長を見積もり、見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出し、抽出されたパスに対してマッピングを行い、その結果位置によってネットがカットされたときのコストを決定し、コストの合計量が最小になるようにパーティショニング処理を行う。
（２）上記（１）において、クリティカルパスに属するセルが多すぎたため、カット数が一定の値を越えるとき、マッピング結果位置に基づいてネットがカットされたときのコストを下げる。
（３）上記（１）または（２）において、１ブロックに割り当てなければならないセル数またはセルの面積が一定の値を越えたとき、マッピング結果位置に基づいてネットがカットされたときのコストを下げる。
（４）上記（１）（２）または（３）において、見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出するに際し、あるネットの中で、そのネットを駆動するピンにおけるスラックよりも大きいスラックを待つピンを無視してクリティカルパスを抽出する。
【００１４】
以上のように、本発明においては、従来システムの処理のパーティショニング処理を行う直前に、位置制約接続について、ネットがカットされたときの線長増加量見積もり処理、クリティカルパス抽出処理、クリティカルパスマッピング処理を追加し、これを使用してネットのコストを変更する（図１の点線部分）。
これにより、位置制約からの距離を考慮してクリティカルパスを抽出することができ、遅延制約を満たした配置を得ることが容易になる。
また、上記（２）（３）のようにコストを下げることにより、カットラインをまたぐネットが大量に発生し、最終的に配線ができない配置になってしまうような場合や、ひとつのブロックに入る可能性が高いセルが多量に存在している場合にも柔軟に対応することができ、配線性を確保することができる。
さらに、上記（４）のようにすることにより、遅延の増加を最小限におさえたパーティショニングを行うことができる。
【００１５】
【発明の実施の形態】
図２は本発明の実施例のシステムの機能構成を示すブロック図であり、同図において二重線で示した部分は、本発明において追加された部分、点線で囲んだ部分は初期入力として与えられるデータである。
図２において、１は遅延・スラック計算部であり、ネットリスト格納部１１に格納されたネットリスト、タイミング制約格納部１２に格納されたタイミング制約、概略配線格納部１３に格納された概略配線結果等に基づき、前記したように遅延・スラックを計算する。２はパーティショニングのための重み決定部であり、重み決定部２は前記したように位置制約接続していないネットについて、パーティショニングのための重みを決定する。
【００１６】
３は本発明に係わる位置制約に接続したクリティカルネット抽出部であり、後述するように位置制約に接続したクリティカルネットを抽出する。４は本発明に係わる位置制約に接続したクリティカルネット・マッピング・重み決定部であり、後述するように位置制約に接続したクリティカルパスのマッピング処理を行い、マッピング結果に基づきクリティカルパスの重みを計算する。
５はパーティショニング実行部であり、前記したように、上記重み決定部２、クリティカルネットマッピング・重み決定部４で決定された重みに基づきコストを計算し、パーティショニング処理を実行する。パーティショニング実行部５により求まったセル位置はセル位置格納部１４に格納される。また、６は概略配線実行部であり、前記したように次のパーティショニングのために、ネットの概略配線を行う。概略配線実行部６で得た配線結果は、概略配線格納部１３に格納され、遅延・スラック計算に用いられる。
【００１７】
図３は本発明の実施例のパーティショニングベース配置処理を示すフローチャートである。なお、ステップＳ２，ステップＳ４からステップＳ７の処理は前記図１８に示した処理と同じであり、本実施例においては、ステップＳ８〜Ｓ１０の位置制約接続の場合の処理を追加したものである。
同図において、まず、ステップＳ１において、着目している接続が前記図１９、図２０に示したような位置制約のあるセルに接続している位置制約接続であるかを調べる。位置制約接続でない場合には、ステップＳ２に行き、スラックに基づいて前記したように通常のコスト計算を行う。
【００１８】
一方、位置制約接続の場合には、ステップＳ８において、クリティカルパス抽出処理を行い、ステップＳ９において抽出されたクリティカルパスについてマッピング処理を行う。ついで、ステップＳ１０において、クリティカルパスのコスト計算を行う。
そして、全てのネットについての処理が終了したかを調べ（ステップＳ３）、終了していなければステップＳ１に戻る。
全てのネットについての処理が終了すると、ステップＳ４に行き、コストが最小になるようにパーティンョニング処理を実行する。パーティショニングが終了すると、分割が十分細かくなったかを調べ（ステップＳ５）、分割が十分細かくなれば処理を終了する。
分割が十分細かくなっていない場合には、次のパーティショニングのために、ネットの概略配線を行い（ステップＳ６）、パーティショニングの結果に対して遅延、スラックを計算し、ステップＳ１に戻る。
【００１９】
すなわち、本実施例では、位置制約接続の場合、従来システムの処理のパーティショニング処理を行う前に、セルや外部端子等の位置制約条件から、ネットがカットされたときに増加する線長を見積もり、見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出し、抽出されたパスに対してマッピングを行い、その結果位置によってネットがカットされたときのコストを決定する。
【００２０】
上記線長増加量見積もり処理は、現在パーティションを行おうとしているブロックに存在する位置制約を見てそれによる遅延の増加を見積もる処理である。
位置制約を発生させる要因の例としては、前記図１９、図２０に示したように以下のようなものがある。
▲１▼  あらかじめ位置が決まっているセル（固定セル）
▲２▼  フロアプランによる制約により、どちらかのブロックに入ることが決まってしまうセル
▲３▼  外部端子
▲４▼  前回までのパーティショニングの結果により、ブロック外とのつながりを持っているネット
【００２１】
次に上記した線長を見積もり、見積もった線長の増加量に基づいて遅延の増加量を計算してクリティカルパスを抽出し、マッピングを行う処理について説明する。
図４、図５はクリティカルパス抽出処理を示すフローチャートであり、まず図４、図５によりクリティカルパス抽出の処理から説明する。
図４のステップＳ１において、現在パーティショニングしようとしているブロックの中に存在する位置制約を位置制約リストＣＬに格納する。すなわち、上記▲１▼〜▲３▼の位置制約のあるセルの位置、▲４▼におけるネットカットの位置を位置制約リストに格納する。
【００２２】
次に、ステップＳ２において、位置制約リストＣＬからもっともカットラインから遠い位置にある一つ位置制約Ｃをとりだす。そして、取り出した位置制約Ｃを位置制約リストＣＬから取り除く。
なお、位置制約リストはヒープ（最大もしくは最小のものを取り出しやすいデータ構造）として実現することにより、カットラインからもっとも遠い位置制約を効率よく取り出すことができる。
ステップＳ３において、上記位置制約Ｃに直接接続している各ネットｎに対して、次の図５に示す処理を行う。
【００２３】
図５のステップＴ１，Ｔ２において、〔位置制約Ｃからカットラインまでの距離〕をＬｎ、〔ネットｎの線長増加許容量〕をαとしたとき、Ｌｎ＞αであるかを調べる。
上記αは次のように計算される。
取り出された位置制約Ｃにつながっているネットｎのスラックを見て、遅延の制約を満たしている範囲内で、線長を伸ばすことができる量αを次の式（３）により計算する。
α＝Ａ×Ｌ…（３）
ここで、Ｌ＝スラックから計算される線長の増加の上限（線長がＬ伸びたとき、遅延がスラックと同じ値だけ増加する）、Ａは０＜Ａ≦１を満たす実数である。なお、係数Ａをかける理由は、スラックから許容される線長の伸びをすべて使いきってしまうと、今後のパーティショニングで自由度が少なくなり、弊害が大きいためである。
【００２４】
上記ネットの長さの増加による遅延の増加の計算は、例えば、以下のモデルにより行うことができる。
ここで、
・Ｓ：ネットを駆動しているピンにおけるスラック
・Ｃ：配線の単位長さあたりの容量
・ＫＣＬ：容量あたりの遅延の増加係数（  つまり、ネットが長さＬのびたとき、ネットの負荷による遅延はＫＣＬ＊Ｃ＊Ｌだけ増加する）
・Ａ＝０．５
とすると、スラックｓから計算される線長の増加の上限αは次の式（４）で計算される。
α＝Ａ＊ｓ／（ＫＣＬ＊Ｃ）…（４）
なお、α＜０になったときは、α＝０として扱う。
【００２５】
図５に戻り、Ｌｎ＞αでない場合には、図４のステップＳ４に戻る。
また、Ｌｎ＞αの場合には、図６に示すようにネットをαだけ伸ばしてもカットラインまで届かないので、そのネット全体は位置制約と同じブロック内に入っていなければならないと判断し、そのネットに接続しているセルは、クリティカルパスに入っているものとみなす。そして、ステップＴ３において、Ｌｎ＞αであるネットをクリティカルパスに登録し、そのネットにつながっているセルを、位置制約からαだけカットラインに近い場所に固定されているとみなすことにする。
【００２６】
ただし、そのセルがすでに他の位置制約を持っているセルで、新しい位置制約の方がカットラインから遠い場合には、セルの位置制約を新しいものに変更する。すなわち、そのセルがすでに他の位置制約を持っているセルだった場合は、新しい制約と古い制約のうち、カットラインから遠いものを採用する。
そして、セルが位置制約を持っていなかった場合には、セルの位置制約を位置制約リストＣＬに登録し、図４のステップＳ４に戻り、位置制約リストＣＬが空であるかを調べ、空でない場合には、ステップＳ２に戻って、次に最もカットラインから遠い位置にある位置制約を取りだす。
【００２７】
上記Ｌｎ＞αの場合の処理を、図７のネット例について図８〜図１２により説明する。
まず、図８に示すように、固定セルＣｅ１に接続しているネットＡを処理対象とし、ネットＡがどこまで伸びるかを求める。
すなわち、図９に示すように、固定セルＣｅ１からαだけカットラインに近い位置に、他のセルＣｅ２が固定されたと見なし、そのセルＣｅ２を位置制約リストＣＬに入れる。
次に、図１０に示すように、新たに位置制約リストＣＬに加わったセルＣｅ２に接続しているネットＢに対して上記と同じ操作を繰り返し、図１１に示すように、カットラインに到達するまでこの処理を繰り返す。これにより、位置制約に接続しているクリティカルネットが抽出される。
ここで、場合によっては、図１２に示すように反対側のブロックの位置制約までつながってしまうことがある。その場合には、マッピング処理で仮の位置を決めることとなる。
【００２８】
次に、上記の処理で抽出された位置制約に接続したクリティカルパスのマッピングを行う。この処理では、セルの面積は無視して、クリティカルパスの線長が最小になるようなセルの位置を求める。このような処理を行うアルゴリズムとしては、前記した参考文献２で示されているものなどが知られている。
上記クリティカルパスマッピング処理によりセル位置が定まると、マッピングの結果得られた各ネットの位置によって、ネットがカットされたときのコストを修正し、位置制約接続の場合のクリティカルパスのコストを計算する。
ここでは、カットラインから遠いところにおかれたネットがカットされたときと、近いところにおかれたネットがカットされたときでは、遅延の増加量は前者の方が大きいと考えて、カットラインから遠いところにおかれたネットに対して、より大きなコストを与えることにする。
【００２９】
例えば、カットラインから距離Ｒ内に少しでも入っているネットについてはコスト３を使用し、その範囲内に存在しないネットについてはコスト無限大とするような方法が考えられる。
このように、距離Ｒ以内に入らないもののコストを無限大とすることにより、距離Ｒ以内に入らないものはすべて同じブロックに存在しなければならないこととなる。また、距離Ｒ以内に入っているネットのコストを小さくすれば、カットラインに近いセルはカットラインで分割された領域のどちらの領域に入ってもよいこととなる。
なお、位置制約に接続していないクリティカルパスについては、前記したように従来方法と同じスラックを与え、あとは従来のパーティショニング手法を使用する。
【００３０】
ここで、遅延による制約を加えたため、従来のパーティショニング処理を行った結果、カットラインをまたぐネットが大量に発生し、最終的に配線ができない配置になってしまう可能性がある。
このような場合を避けるため、カット数が一定の限度を越える場合は、マッピング結果位置に基づいてネットに与えられたスラックを減少させる。
例えば、先にあげた例で距離Ｒ内に存在しないネットにコスト無限大を与えていたのを修正し、Ｒ＋ΔＲ内に存在しないネットにコスト無限大を与えることにして、再度パーティショニングを行う。この場合は、例えば、カット数が閾値を下回るまでΔＲを加え、処理を繰り返すという処理を行う。
【００３１】
同様に、ひとつのブロックに入る可能性が高いセルが多量に存在している場合は、パーティンョニング処理により最適化がうまくいかない可能性がある。
このような場合も、マッピング結果位置によってネットのコストを下げることにより、配線性を確保する方法を採ることができる。
たとえば先にあげた例で距離Ｒ内に存在しないネットにコスト無限大を与えたために、どちらかのブロックに必ず入るセルの面積の合計量がそのブロックの面積のＸ％を越えた場合は、上記したように、Ｒ→Ｒ＋ΔＲと置き換え、セル面積の合計量がＸ％を下回るまでこの処理を繰り返す、というような実装が考えられる。
【００３２】
ところで、ネットに接続しているセルはすべてクリティカルであるとは限らない。例えば、図１３では、ネットｎに接続しているセルは、すべてクリティカルパスのセルに属しているが、ネットｎがセルｃに接続しているピンｃｎ  においてはスラックが大きい（同図ではスラック４ナノ秒）ため、セルａ→ｃ間の遅延についてはかなりの余裕がある。
ここで、図１４に示すように、仮にセルａ，ｂがブロック１に、セルｃがブロック２に配置されたとする。
このままでは、ネットｎの線長は長くなり、全体の静電容量が増加するため、セルａ→ｂ間の遅延も増加するという悪影響がある。
【００３３】
そこで、分岐点Ｘにバッファを挿入する。これによりセルｃへの分岐による静電容量は、セルａ→ｂ間の配線とは切断される。このような操作により、セルａ→ｂ間の遅延の増加は最小限に防ぐことができる。
したがって、ネットを駆動するピンにおけるスラックをｓｄとしたとき、そのネットに属しているあるピンのスラックｓがｓ≦ｓｄ＋ΔＳ（ΔＳはあらかじめ定められた定数）  を満たさないときは、上記のようにバッファを挿入することを前提として、そのピンはクリティカルとみなさず、前記図３に示したクリティカルパス抽出処理において、そのピンにおける接続を無視してクリティカルパスを抽出する。これにより、遅延の増加を最小限に抑えるパーティショニングが得られる。
【００３４】
【発明の効果】
以上説明したように、本発明においては、位置制約による配線長の増加を見積もりながら、性能の高いｍｉｎ−ｃｕｔアルゴリズムを活用しパーティショニング処理を行っているので、配線性を確保しながら遅延制約をみたしやすい配置システムを構成することができる。
【図面の簡単な説明】
【図１】本発明の概要を説明する図である。
【図２】本発明の実施例のシステムの機能ブロック図である。
【図３】本発明の実施例の処理を示すフローチャートである。
【図４】クリティカルパス抽出処理を示すフローチャート（１）である。
【図５】クリティカルパス抽出処理を示すフローチャート（２）である。
【図６】クリティカルとみなされるネットの説明図である。
【図７】クリティカルパス抽出処理を説明するためのネットの例を示す図である。
【図８】クリティカルパス抽出処理を説明する図（１）である。
【図９】クリティカルパス抽出処理を説明する図（２）である。
【図１０】クリティカルパス抽出処理を説明する図（３）である。
【図１１】クリティカルパス抽出処理を説明する図（４）である。
【図１２】クリティカルパス抽出処理を説明する図（５）である。
【図１３】ネットを駆動しているピンがクリティカルであっても、ネットの中にクリティカルでないピンが存在している場合を説明する図である。
【図１４】図１３の例において、ピンにおける接続を無視してクリティカルパスを抽出する場合を説明する図である。
【図１５】パーティショニングベース配置方式の基本的な考え方を示す図である。
【図１６】クリティカルパス・スラックを説明する図である。
【図１７】分岐が存在することによりスラックがパスの途中で変化する場合を説明する図である。
【図１８】従来システムにおける処理を説明する図である。
【図１９】位置制約の例（１）を示す図である。
【図２０】位置制約の例（２）を示す図である。
【図２１】配置における位置制約による遅延の増加の違いの例を示す図である。
【符号の説明】
１    遅延・スラック計算部
２    パーティショニングのための重み決定部
３    クリティカルネット抽出部
４    クリティカルネット・マッピング・重み決定部
５    パーティショニング実行部
６    概略配線実行部
１１  ネットリスト格納部
１２  タイミング制約格納部
１３  概略配線格納部
１４  セル位置格納部
【図１】
0003544893.tif 000003
【図２】
0003544893.tif 000004
【図３】
0003544893.tif 000005
【図４】
0003544893.tif 000006
【図５】
0003544893.tif 000007
【図６】
0003544893.tif 000008
【図７】
0003544893.tif 000009
【図８】
0003544893.tif 000010
【図９】
0003544893.tif 000011
【図１０】
0003544893.tif 000012
【図１１】
0003544893.tif 000013
【図１２】
0003544893.tif 000014
【図１３】
0003544893.tif 000015
【図１４】
0003544893.tif 000016
【図１５】
0003544893.tif 000017
【図１６】
0003544893.tif 000018
【図１７】
0003544893.tif 000019
【図１８】
0003544893.tif 000020
【図１９】
0003544893.tif 000021
【図２０】
0003544893.tif 000022
【図２１】
0003544893.tif 000023