(57)【要約】【課題】レジスティブネットワーク方式を用いて品質のよい配置結果を得られるようにすること。【解決手段】コンピュータに、チップ上に設けられる複数のセルそれぞれの配置位置を示す情報と、前記複数のセルにおけるセル間の接続関係を示す情報とに基づいて、前記複数のセルそれぞれに対して前記複数のセルそれぞれに対応する前記配置位置から引力が生じるとして、レジスティブネットワーク方式により前記複数のセルの再配置位置を求める処理を実行させる。【選択図】        図１
2010165365.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
チップ上に設けられる複数のセルそれぞれの配置位置を示す情報と、前記複数のセルにおけるセル間の接続関係を示す情報とに基づいて、前記複数のセルそれぞれに対して前記複数のセルそれぞれに対応する前記配置位置から引力が生じるとして、レジスティブネットワーク方式により前記複数のセルの再配置位置を求める処理
を実行させることを含むＬＳＩのセル配置位置情報変更プログラム。
【請求項２】
コンピュータに、
チップ上に設けられる複数のセルそれぞれの配置位置を示す情報と、前記複数のセルにおけるセル間の接続関係を示す情報とに基づいて、前記接続関係に応じて設けられる配線の数が所定数以上である領域を抽出し、
前記複数のセルのうち、前記複数のセルそれぞれに対して前記複数のセルそれぞれに対応する前記配置位置から引力が生じ、前記抽出された領域に含まれるセル同士に反発力が生じるとして、レジスティブネットワーク方式により前記抽出された領域に含まれるセルを含む複数のセルについての再配置位置を求める処理
を実行させることを含むＬＳＩのセル配置位置情報変更プログラム。
【請求項３】
コンピュータを用いて、
チップ上に設けられる複数のセルそれぞれの配置位置を示す情報と、前記複数のセルにおけるセル間の接続関係を示す情報とに基づいて、前記複数のセルそれぞれに対して前記複数のセルそれぞれに対応する前記配置位置から引力が生じるとして、レジスティブネットワーク方式により前記複数のセルの再配置位置を求めること
を特徴とするＬＳＩのセル配置位置情報変更方法。
【請求項４】
コンピュータを用いて、
チップ上に設けられる複数のセルそれぞれの配置位置を示す情報と、前記複数のセルにおけるセル間の接続関係を示す情報とに基づいて、前記接続関係に応じて設けられる配線数が所定数以上である領域を抽出し、
前記複数のセルのうち、前記複数のセルそれぞれに対して前記複数のセルそれぞれに対応する前記配置位置から引力が生じ、前記抽出された領域に含まれるセル同士に反発力が生じるとして、レジスティブネットワーク方式により前記抽出された領域に含まれるセルを含む複数のセルについての再配置位置を求めること
を特徴とするＬＳＩのセル配置位置情報変更方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＳＩ（大規模集積回路）上のセル配置の改善を行うＬＳＩのセル配置位置情報変更プログラム及び方法に関する。
【０００２】
ＬＳＩの設計では、先ず、アンド（ＡＮＤ）回路、オア（ＯＲ）回路などのセルと、セル間の接続（ネット）を決定し（論理設計）、次に、セルのチップ上の位置を決定し（配置）、最後に、セル間のネットをどう引くかを決定（配線）するものである。なお、１つのセルは、通常２個から４個等の複数のトランジスタを含むものである。
【背景技術】
【０００３】
ＬＳＩのセルの配置において、よく使用される方式として、パーティショニングベースと呼ばれる方式があり、またもう一つ、ＬＳＩのセルの配置に使える方式として、レジスティブネットワーク方式と呼ばれるものが存在する。以下、これらの方式を説明する。
【０００４】
（１）：パーティショニングベース配置方式の説明
パーティショニングベースと呼ばれる方式では、チップを分割して、分割したそれぞれのブロック（領域）にセルを割り当てることを繰り返す。最終的に、各ブロックが１つ程度のセルしか含まない程度まで細かく分割されたところで、セルの位置が決定されるものであった。
【０００５】
図６は従来のパーティショニングベース配置方式の説明図である。図６において、１回目のカットとして、チップ全体を最初に２分割する。分割する線をカットラインと呼ぶ。そして、全セルを２つの領域（ブロック）（丸１、丸２）のそれぞれに振り分ける。このセルを振り分ける基準であるが、セルを２つの領域に分けた結果、２つの領域にまたがって存在するネットの数をコストとし、このコストが最小になるようなグループ分けを採用する方法（min-cut 法）がよく用いられる。そのような処理を行うアルゴリズムとしては、ＦＭ法などが知られている。
【０００６】
このとき、２つの領域に振り分けるセルの面積の合計値が、一定の範囲内におさまることを条件とすることにより、セルがどちらかの領域に片寄らないように操作する。
【０００７】
例えば、２つの領域（丸１、丸２）の面積をＳ１、Ｓ２、領域（丸１、丸２）割り当てられたセルの面積の合計値をそれぞれｓ１、ｓ２とすると、次の式が満たされていることを条件とするものである。
【０００８】
｜ｓ１／Ｓ１−ｓ２／Ｓ２｜≦α  （αはある正の定数）
同様に、次に２回目のカットとして横、次に縦、という順序で分割を繰り返していくことにより、セルの位置を決定するものであった。
【０００９】
（２）：レジスティブネットワーク方式の説明
もう一つのＬＳＩのセルの配置に使える方式として、レジスティブネットワーク方式と呼ばれるものが存在する（例えば、非特許文献１、２参照）。この方式では、ネットをバネと考え、バネの力学的エネルギーを最小にするセル位置を求める。図７は従来のレジスティブネットワーク方式の説明図であり、図７（ａ）はレジスティブネットワーク方式の説明である。図７（ａ）において、外部端子１１とセルＡ間のネットをバネ２１とみなし、外部端子１２とセルＢ間のネットをバネ２２とみなし、セルＡとセルＢ間のネットをバネ２３とみなし、セルＢとその他のネットをバネ２４、２５、２６とみなしてある。
【００１０】
しかし、これだけでは、セルの面積が考慮されておらず（セルは点と仮定されている）、重なりが生じるので、セルが重なっている部分では、反発力が発生していると考えて、反発力が加わった状態で、バネの力学的エネルギーを最小にする配置を求める。図７（ｂ）はセル面積を考慮する手法の説明である。図７（ｂ）において、レジスティブネットワーク方式でセル面積を考慮する手法であり、セルＡのネットが引く力をＦ２１、セルＢのネットが引く力をＦ２２、Ｆ２３とし、セルＡとセルＢが重なったことにより生じる反発力をそれぞれＦ１、Ｆ２とする。この状態で、バネの力学的エネルギーを最小にする配置を求めるものである。
【００１１】
また、ネットが混雑していて配線が困難なエリアが生じたときも、同様にそのエリア内のセルに反発力を仮定することにより、セルをその領域から追い出して配線性を高めることができる。
【００１２】
（３）：パーティショニングベース方式とレジスティブネットワーク方式の比較
・パーティショニングベース方式とレジスティブネットワーク方式の両者にはそれぞれ利点と欠点がある。パーティショニングベース方式の利点は、処理を速く行えること、最近のパーティショニングアルゴリズムの改良により、最終的なネットの線長が短いものが得られる点である。欠点は、チップを分割する初期段階で、セルの最終的な配置結果を予想することが困難で、このまま処理を進めたとき配線性が良くなるか悪くなるかを判定しにくい点である。
【００１３】
例えば、図８は従来のパーティショニングベース方式の問題点の説明図である。図８において、分割を進めていくうちに、ネット数が他の領域より多い領域（丸３）が生じてしまうと、その領域（丸３）は配線しにくくなってしまう。しかし、分割の初期段階では、ネット数が他よりも多い領域ができるかどうかを知ることができない。このため、配線が困難な領域が生じてしまうことがあった。
【００１４】
・レジスティブネットワーク方式の利点は、処理の高速性と最終的なセルの配置結果を予想できる点である。欠点は、ネットを２つのセル間のバネとして近似しているため配線長が見積もりにくい点である。ＬＳＩでは、配線は垂直及び水平方向にしか引けず、斜め方向の配線はできないので、ネットの長さは、｜ｘ｜＋｜ｙ｜で表されることになる。
【００１５】
図９は従来のレジスティブネットワーク方式の線長見積もりの説明図である。図９において、ネットＡとネットＢの配線の長さは、どちらも２Ｌで等しい。しかし、レジスティブネットワーク方式でバネの伸びとして計算するときは、square-root(ｘ2 ＋ｙ2)を長さとするため、ネットＢの線長の方が長くなってしまう。
【００１６】
また、３つ以上のセルにつながっているネットがあったとき、これを２つのセル間のバネの組み合わせで近似表現することになるため、力学的エネルギー最小の解が、必ずしも線長最小の解を与えることにはならなかった。
【００１７】
図１０は従来のレジスティブネットワーク方式で３つ以上のセルに接続するネットの説明図である。図１０において、セルＡは、セルＢを突き抜けてセルＣと１つのネットで接続されている。これをレジスティブネットワーク方式では、複数のバネ３１、３２、３３で置き換えるが、これらのバネの強さの調整が複雑となり、しかも、力学的エネルギー最小の解が、必ずしも線長最小の解を与えることにはならない。
【００１８】
・このようにパーティショニングベース方式とレジスティブネットワーク方式には、それぞれ長所と短所があるので、パーティショニングベース方式とレジスティブネットワーク方式を組み合わせ、それぞれの長所を生かす方式が考えられる。
【００１９】
例えば、レジスティブネットワーク方式でおおよその位置を決め、その解をパーティショニングアルゴリズムの初期解として与えるなどの手法が知られている。しかし、最近のパーティショニングアルゴリズムは、最適解を求めるために、初期解から大きく異なる解まで探索するように作られているので、初期解をレジスティブネットワーク方式で与えても、得られる分割は全く異なるものになってしまう。これを避けるために解の探索範囲をせばめると、最適化能力が低くなり、線長が伸びるという欠点が残ってしまっていた。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Chung-Kuan Cheng and Ernest S. Kuh. Module Placement Based on Resistive Network Optimization.IEEE Trans. On Computer-Aided Design, 3(3):218-225, July 1984.
【非特許文献２】H.Eisenmann and F.M.Johannes. Generic Global Placement and Floorplanning. ACM/IEEE Design Automation Conference,Vol.35,pp.269-274,1998.
【発明の概要】
【発明が解決しようとする課題】
【００２１】
前記従来のものは、次のような課題があった。
【００２２】
（１）：パーティショニングベース方式は、チップを分割する初期段階で、セルの最終的な配置結果を予想することが困難で、処理を進めたとき、配線の困難な領域が生じてしまうことがあった。
【００２３】
（２）：レジスティブネットワーク方式は、ネットを２つのセル間のバネとして近似しているため配線長が見積もりにくい問題があった。
【００２４】
（３）：レジスティブネットワーク方式でおおよその位置を決め、その解をパーティショニングアルゴリズムの初期解として与える手法は、初期解から大きく異ならないようにするため、解の探索範囲をせばめると、最適化能力が低くなり、線長が伸びるという欠点が残ってしまっていた。
【００２５】
本発明は、このような従来の課題を解決し、パーティショニングベース方式とレジスティブネットワーク方式を組み合わせ、それぞれの欠点を補うことによって品質のよい配置結果を得られるようにすることを目的とする。
【課題を解決するための手段】
【００２６】
図１は本発明の装置構成図である。図１中、１は入力手段、２はパーティショニングベースの配置処理手段、３は抽出手段、４はレジスティブネットワーク方式の配置処理手段である。
【００２７】
本発明は、上記従来の課題を解決するため次のように構成した。
【００２８】
（１）：チップを分割した領域に各セルを振り分け、各セルの暫定配置を決めるパーティショニングベースの配置処理手段２と、該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段４とを備える。
【００２９】
（２）：セルの配置結果を入力する入力手段１と、該入力された配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段４とを備える。
【００３０】
（３）：局所的にネットが混雑している領域、又は、信号伝達の遅延が大きいネットを抽出する抽出手段３を備え、該抽出したその領域だけを前記（２）記載のレジスティブネットワーク方式の配置処理手段４で配置処理を行う。
【００３１】
（作用）
前記構成に基づく作用を説明する。
【００３２】
パーティショニングベースの配置処理手段２でチップを分割した領域に各セルを振り分けて各セルの暫定配置を決め、レジスティブネットワーク方式の配置処理手段４で該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決める。このため、パーティショニングベース方式でネットが集中している領域が生じてしまっても、レジスティブネットワーク方式で配置結果を改善することができ、品質のよい配置結果を高速に得ることができる。
【００３３】
また、入力手段１でセルの配置結果を入力し、該入力された配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、レジスティブネットワーク方式の配置処理手段４でネットをバネと考えてセルの配置を決める。このため、任意の配置位置を入力して、レジスティブネットワーク方式で配置結果を改善することができ、品質のよい配置結果を高速に得ることができる。
【００３４】
さらに、抽出手段３で局所的にネットが混雑している領域、又は、信号伝達の遅延が大きいネットの領域を抽出し、該抽出したその領域だけをレジスティブネットワーク方式の配置処理手段４で配置処理を行う。このため、処理領域が少なく、品質のよい配置結果をより高速に得ることができる。
【発明の効果】
【００３５】
以上説明したように、本発明によれば次のような効果がある。
【００３６】
（１）：パーティショニングベースの配置処理手段でチップを分割した領域に各セルを振り分けてセルの暫定配置を行い、レジスティブネットワーク方式の配置処理手段で該暫定配置位置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるため、パーティショニングベース方式でネットが集中している領域が生じてしまっても、レジスティブネットワーク方式で配置結果を改善することができ、品質のよい配置結果を高速に得ることができる。
【００３７】
（２）：入力手段でセルの配置結果を入力し、該入力された配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、レジスティブネットワーク方式の配置処理手段でネットをバネと考えてセルの配置を決めるため、任意の配置位置を入力して、レジスティブネットワーク方式で配置結果を改善することができ、品質のよい配置結果を高速に得ることができる。
【００３８】
（３）：抽出手段で局所的にネットが混雑している領域、又は、信号伝達の遅延が大きいネットの領域を抽出し、該抽出したその領域だけをレジスティブネットワーク方式の配置処理手段で配置処理を行うため、処理領域が少なく、品質のよい配置結果をより高速に得ることができる。
【００３９】
（４）：チップを分割した領域に各セルを振り分け、各セルの暫定配置を決めるパーティショニングベースの配置処理手段と、該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段として、コンピュータを機能させるためのプログラム又はプログラムを記録したコンピュータ読み取り可能な記録媒体とするため、このプログラムをコンピュータにインストールすることで品質のよい配置結果を高速に得ることができるＬＳＩのセル配置方法及び装置を容易に提供することができる。
【図面の簡単な説明】
【００４０】
【図１】本発明の装置構成図である。
【図２】実施の形態におけるＬＳＩのセル配置処理の説明図である。
【図３】実施の形態におけるパーティショニングベース方式による配置フェーズの説明図である。
【図４】実施の形態における仮想ネット発生フェーズの説明図である。
【図５】実施の形態におけるレジスティブネットワーク方式による改善フェーズの説明図である。
【図６】従来のパーティショニングベース配置方式の説明図である。
【図７】従来のレジスティブネットワーク方式の説明図である。
【図８】従来のパーティショニングベース方式の問題点の説明図である。
【図９】従来のレジスティブネットワーク方式の線長見積もりの説明図である。
【図１０】従来のレジスティブネットワーク方式で３つ以上のセルに接続するネットの説明図である。
【発明を実施するための形態】
【００４１】
本発明は、セルの暫定配置位置とそのセル間とをつなぐネット（仮想ネット）があるものとみなして、レジスティブネットワーク方式でＬＳＩのセル配置を求めるものである。
【００４２】
以下、本発明の実施の形態を図面に基づいて説明する。
【００４３】
（１）：ＬＳＩのセル配置装置の説明
図１は本発明の装置構成図である。図１において、ＬＳＩのセル配置装置には、入力手段１、パーティショニングベースの配置処理手段２、抽出手段３、レジスティブネットワーク方式の配置処理手段４が設けてある。
【００４４】
入力手段１は、セルの任意の配置位置等を入力するものである。パーティショニングベースの配置処理手段２は、パーティショニングベース方式によるセルの配置処理を行うものである。抽出手段３は、ネットの数が一定値を越える領域（配線が混雑しているエリア）、信号伝達の遅延が大きいネットの領域等を抽出するものである。レジスティブネットワーク方式の配置処理手段４は、仮想ネット発生手段を有し、レジスティブネットワーク方式によるセルの配置処理を行うものである。
【００４５】
（２）：ＬＳＩのセル配置処理の説明
(1) パーティショニングベース方式で暫定配置を求める場合の説明
図２はＬＳＩのセル配置処理の説明図である。以下、図２の処理Ｓ１〜処理Ｓ３に従って説明する。
【００４６】
Ｓ１：最初に、パーティショニングベースの配置処理手段２は、パーティショニングベース方式で、セルの暫定配置を求め、セルの暫定位置を決定し、処理Ｓ２に移る。
【００４７】
Ｓ２：次に、仮想ネット発生手段は、それぞれのセルから、そのセルの暫定位置の間をつなぐネットがあるものとみなし（仮想ネットを発生）、処理Ｓ３に移る。
【００４８】
Ｓ３：レジスティブネットワーク方式の配置処理手段４は、レジスティブネットワーク方式でセルの配置を求める。
【００４９】
このように仮想ネットを追加したことにより、セルは暫定位置に引きつけられるので、配置位置が大きく変わることはない。もし、仮想ネットが存在しないときは、最初からレジスティブネットワーク方式を使ったのと同じ結果になり、セルは全く違った位置に置かれてしまうことになる。
【００５０】
また、ネット数がある一定値を越える領域があって、配線が困難だと思われる領域に対して、従来のレジスティブネットワーク方式と同様、反発力を発生させることにより、セルをその領域から追い出すことができる。このようにして、パーティショニングベース配置でネットが集中している領域が生じてしまっても、配置結果を改善することが可能となる。
【００５１】
このように、パーティショニングベース方式で得られた結果をレジスティブネットワーク方式を使って改善することにより、それぞれの欠点を補って、品質のよいセルの配置結果を得ることができる。
【００５２】
(2) 任意の配置位置を入力する場合の説明
レジスティブネットワーク方式によるセルの配置の改善部（レジスティブネットワーク方式の配置処理手段４）は、配置システムの一部として動く必要はなく、改善部分だけを独立して動作させることもできる。この場合、任意のセルの配置位置（例えば、パーティショニングベース方式以外の配置処理手段で求めた位置）を入力として、仮想ネットを追加してレジスティブネットワーク方式を適用する。このようにして、レジスティブネットワーク方式を用いたセル配置改善システムを作ることができる。
【００５３】
(3) 必要部分だけのセルの配置を改善する場合の説明
全データに対して、レジスティブネットワーク方式によるセル配置の改善を行う必要はない。局所的（チップの一部）に配線が混雑しているエリアがあったときは、そのエリアを抽出手段３で抽出し、そのエリアだけをレジスティブネットワーク方式の配置処理手段４へ入力し、レジスティブネットワーク方式によるセル配置の改善を行うことができる。
【００５４】
同様に、一部のネットが長すぎて遅延が大きくなっているものを改善したいときは、抽出手段３でスラックの値が一定値以下の部分を抽出して、その部分だけをレジスティブネットワーク方式の配置処理手段４へ入力し、レジスティブネットワーク方式によるセル配置の改善を行うことができる。
【００５５】
ここでスラックとは、あるネットの遅延を、タイミング制約の範囲内でどれだけ増加させられるかという余裕を示す値である。すなわち、信号が最悪でもこの時間で届かなければならない時間（目標遅延）から、信号が実際に到達する時間（実際の遅延）を引いたものである（スラック＝目標遅延−実際の遅延）。
【００５６】
（３）：min-cut 方式を使った処理の説明
パーティショニングアルゴリズムとしてmin-cut 方式を使った場合において、レジスティブネットワーク方式によるセル配置の改善を行うフェーズでは、配線混雑度が基準値よりも高い領域に入っているセルに対して、反発力を生成する。そして、仮想ネットのバネの強さを通常ネットよりも大きくすることにより、ネットが混雑して配線できない領域以外では、パーティショニングベース配置の結果を尊重し、配線が困難な領域ではレジスティブネットワーク方式によって、セルの密度を減らすことが可能になる。
【００５７】
次に、図面に基づいて、パーティショニングアルゴリズムとしてmin-cut 方式を使った場合の処理の説明をする。図３はパーティショニングベース方式による配置フェーズの説明図、図４は仮想ネット発生フェーズの説明図、図５はレジスティブネットワーク方式による改善フェーズの説明図である。以下、図３〜図５の処理Ｓ１１〜処理Ｓ２３に従って説明する。
【００５８】
(1) パーティショニングベース方式（パーティショニングベースの配置処理手段２）による配置フェーズの説明
Ｓ１１：全ブロック（領域）を分割し、処理Ｓ１２に移る。
【００５９】
Ｓ１２：全てのブロックにＦＭアルゴリズムを適用し、ブロック内部のセルが、分割したブロックのどちらに入るか決定し、処理Ｓ１３に移る。
【００６０】
Ｓ１３：ブロックは十分小さくなった（例えば、１ブロックのセルの数が１〜２）か判断する。この判断で、ブロックが十分小さくなった場合は次のフェーズ（処理Ｓ１４）に移り、もし、十分小さくなっていない場合は処理Ｓ１１に戻る。
【００６１】
(2) 仮想ネット（仮想ネット発生手段による）発生フェーズの説明
Ｓ１４：変数「ｉ」を１として、処理Ｓ１５に移る。
【００６２】
Ｓ１５：ｉ番目のセルを取り出し、処理Ｓ１６に移る。
【００６３】
Ｓ１６：セルｉと、セルｉが置かれているブロックの中心点の間にネット（仮想ネット）を発生し、処理Ｓ１７に移る。
【００６４】
Ｓ１７：変数「ｉ」をｉ＋１とし、処理Ｓ１８に移る。
【００６５】
Ｓ１８：ｉがセル数より大きいかどうか判断する。この判断で、ｉがセル数より大きい場合は次のフェーズ（処理Ｓ１９）に移り、もし、大きくない場合は処理Ｓ１５に戻る。
【００６６】
(3) レジスティブネットワーク方式（レジスティブネットワーク方式の配置処理手段４）による改善フェーズの説明
Ｓ１９：ネットの重み（バネの強さ）を決定（仮想ネットの強さは通常のネットの１０倍に）し、処理Ｓ２０に移る。
【００６７】
Ｓ２０：配線混雑度を計算し、処理Ｓ２１に移る。
【００６８】
Ｓ２１：配線混雑度が基準値よりも高い領域が存在するかどうか判断する。この判断で、配線混雑度が基準値よりも高い領域が存在する場合は処理Ｓ２２に移り、存在しない場合はこの処理を終了する。
【００６９】
Ｓ２２：配線混雑による反発力を計算（反発力を強く）し、処理Ｓ２３に移る。
【００７０】
Ｓ２３：バネの力学的エネルギーを最小にするセルの配置を求め、処理Ｓ２０に戻る。
【００７１】
（４）：プログラムのインストールの説明
入力手段１、パーティショニングベースの配置処理手段２、抽出手段３、レジスティブネットワーク方式の配置処理手段４等は、プログラムで構成でき、主制御部（ＣＰＵ）が実行するものであり、主記憶に格納されているものである。このプログラムは、一般的な、コンピュータで処理されるものである。このコンピュータは、主制御部、主記憶、ファイル装置、表示装置、キーボード等の入力手段である入力装置などのハードウェアで構成されている。
【００７２】
このコンピュータに、本発明のプログラムをインストールする。このインストールは、フロッピィ、光磁気ディスク等の可搬型の記録（記憶）媒体に、これらのプログラムを記憶させておき、コンピュータが備えている記録媒体に対して、アクセスするためのドライブ装置を介して、或いは、ＬＡＮ等のネットワークを介して、コンピュータに設けられたファイル装置にインストールされる。そして、このファイル装置から処理に必要なプログラムステップを主記憶に読み出し、主制御部が実行するものである。
【００７３】
〔以下、付記を記載する〕
（付記１）チップを分割した領域に各セルを振り分けるパーティショニングベースの配置処理を行って、各セルの暫定配置を決め、
該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理を行うことを特徴としたＬＳＩのセル配置方法。
【００７４】
（付記２）セルの配置結果を入力し、該入力された配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理を行うことを特徴としたＬＳＩのセル配置方法。
【００７５】
（付記３）チップを分割した領域に各セルを振り分け、各セルの暫定配置を決めるパーティショニングベースの配置処理手段と、
該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段とを備えることを特徴としたＬＳＩのセル配置装置。
【００７６】
（付記４）セルの配置結果を入力する入力手段と、
該入力された配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段とを備えることを特徴としたＬＳＩのセル配置装置。
【００７７】
（付記５）局所的にネットが混雑している領域を抽出する抽出手段を備え、
該抽出したその領域だけを前記レジスティブネットワーク方式の配置処理手段で配置処理を行うことを特徴とした付記４記載のＬＳＩのセル配置装置。
【００７８】
（付記６）信号伝達の遅延が大きいネットを抽出する抽出手段を備え、
該抽出したその領域だけを前記レジスティブネットワーク方式の配置処理手段で配置処理を行うことを特徴とした付記４記載のＬＳＩのセル配置装置。
【００７９】
（付記７）チップを分割した領域に各セルを振り分け、各セルの暫定配置を決めるパーティショニングベースの配置処理手段と、
該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段として、
コンピュータを機能させるためのプログラム又はプログラムを記録したコンピュータ読み取り可能な記録媒体。
【００８０】
（付記８）セルの配置結果を入力する入力手段と、
該入力された配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えてセルの配置を決めるレジスティブネットワーク方式の配置処理手段として、
コンピュータを機能させるためのプログラム又はプログラムを記録したコンピュータ読み取り可能な記録媒体。
【符号の説明】
【００８１】
１  入力手段
２  パーティショニングベースの配置処理手段
３  抽出手段
４  レジスティブネットワーク方式の配置処理手段
【図１】
2010165365.tif 000003
【図２】
2010165365.tif 000004
【図３】
2010165365.tif 000005
【図４】
2010165365.tif 000006
【図５】
2010165365.tif 000007
【図６】
2010165365.tif 000008
【図７】
2010165365.tif 000009
【図８】
2010165365.tif 000010
【図９】
2010165365.tif 000011
【図１０】
2010165365.tif 000012