(57)【特許請求の範囲】
【請求項１】
集積回路にカットラインを設定し、該カットラインにより切断される配線数であるカット数が最小となるように該カットラインによって分割された領域間でセルを移動する操作を階層的に繰り返しながら該集積回路を構成するセルの初期配置を決定する集積回路の初期配置決定装置において、
各セルの端子が各セルが属するブロックの中心に位置するものと仮定して、各ネットにつながっているセル間を配線する概略配線手段と、
上記概略配線手段によって得られた概略配線情報を基に、各ネットの概略配線長（論理配線長）を求める配線長算出手段と、
上記配線長算出手段によって算出された各ネットの概略配線長を基に、その現在の概略配線長が予め制約された配線長を越えているネットをヴァイオレーションネットとして検出するヴァイオレーションネット検出手段と、
上記ヴァイオレーションネット検出手段によって検出されたヴァイオレーションネットに属するブロックがカットラインによって分割される際に、上記概略配線手段によって得られた概略配線情報を基に、そのブロックに属しているヴァイオレーションネットにつながっているセルを、該カットラインに対していずれの側にある分割ブロックに移動すれば、該ヴァイオレーションネットの概略配線長が減少するかを予測する配線長増減予測手段と、
上記配線長増減予測手段によってその配線長が減少または増加しないと予測された分割ブロックの方に、上記ヴァイオレーションネットにつながっているセルを移動させた後、該セルを固定セルに設定し、その後、上記ブロックに対してミニカット法を実行するミニカット法実行手段と、
を備えたことを特徴とする集積回路の初期配置決定装置。
【請求項２】
さらに、上記配線長算出手段によって算出された各ネットの概略配線長を基に、その現在の概略配線長が予め制約された配線長のα％を越えているネットをクリティカルネットとして検出するクリティカルネット検出手段と、
ミニカット法の実行開始前にカットラインによりカットされていると共に、該実行開始後にも該カットラインによりカットされているネットをステーブルネットとして検出するステーブルネット検出手段と、
上記クリティカルネット検出手段の検出結果と上記ステーブルネット検出手段の検出結果とを基に、ステーブルネットとなっており、かつクリティカルネットともなっているネットにつながっている全てのセルを同一のブロックに移動させ、移動した全セルを固定セルに設定するセル移動手段と、
を備え、
上記ミニカット法実行手段は、上記セル移動手段の処理により得られたセル配置を初期配置としてミニカット法を実行することを特徴とする請求項１記載の集積回路の初期配置決定装置。
【請求項３】
上記αは、７０≦α≦８０の範囲内の値であることを、特徴とする請求項２記載の集積回路の初期配置決定装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＬＳＩ、ＶＬＳＩおよびＵＬＳＩなどの集積回路のレイアウト設計におけるセルの自動配置方式に係わり、特に、ミニカット（ｍｉｎ−ｃｕｔ）法を用いて集積回路のセル配置を最適化する概略配線長増減予測装置及び集積回路の初期配置決定装置に関する。
【０００２】
最近の製造技術の進歩に伴い、集積回路の集積度の向上及び回路規模の増大には目ざましいものがあり、集積回路チップに含まれるセルの数も増加の一途をたどっている。これに伴い、回路の性能を決定する要因は、ゲートの遅延よりも、配線の遅延の比重のほうが高くなってきている。
【０００３】
【従来の技術】
集積回路のセルの初期配置決定方法の一手法としてパーティショニングが知られている。このパーティショニングは、与えられた回路をＫ個（Ｋは自然数）の部分回路（ブロック）に分割して、各ブロック間をまたがるネットの本数、すなわちカット数を最小化することを目的とした手法である。このパーティショニングの代表的なアルゴリズムとしてミニカット法が知られている。
【０００４】
このミニカット法では、チップを水平、垂直に切断するカットラインとその処理順序を定めておき、カットライン１本ずつについて論理二分割を順次行うことによって配置が決定される。このとき、カットラインは全ブロックの境界に定めておけばよい。
【０００５】
カットラインの処理順序を決定すると、それぞれのカットラインについてチップ上の領域（ブロックの集合）が定まる。さらに、カットラインの場所によって、分割におけるセル数の条件（セル集合ＭをＭ１，Ｍ２  に分割するとき、Ｍ１，Ｍ２  それぞれのセル数の上限）も定まる。論理二分割はカットライン上を通過する配線（ネット）の数を最小にするように行われるが、そのとき、このセル数の条件を満足するような分割でなければならない。
【０００６】
このようにミニカット法の基本は、あるブロックに配置されたセルを他のブロックに移動させて、カットラインを横切るネット数を減少させることである。
図２７は、従来のミニカット法を説明するフローチャートである。
【０００７】
まず、セルの初期配置とカットラインを決定する（Ｓ１）。次に、各セル毎にセルゲインｇを求める（Ｓ２）。該セルゲインｇは、あるセルを他のブロックに移動したときに減少するカット数である。
【０００８】
続いて、各ブロック毎にセルゲインｇを大きい順にソートする（Ｓ３）。続いて、最もセルサイズが大きいブロックから、セルゲインｇの最も大きいセルを選択し、このセルを他のブロックに移動する（Ｓ４）。
【０００９】
次に、該移動したセルと、そのセルとネットによる接続関係にあるセルのセルゲインｇを更新し、各ブロック毎にセルゲインｇをソートしなおす（Ｓ５）。そして、セルゲインｇが正のセルが存在するか否かを判別し（Ｓ６），存在すれば（Ｓ６，ＹＥＳ）、再び上記ステップＳ４〜Ｓ５の処理を繰り返す。そして、セルゲインｇが正のセルが存在しなくなったと判別すると（Ｓ６、ＮＯ），処理を終了する。
【００１０】
以上の処理により、セルの初期配置が最適化される。
上記ミニカット法を、図３２を参照しながらより具体的に説明する。
同図において、破線で示された垂線１がカットラインである。また、編みかけで示したセル２が正のセルゲインｇを有するセルであり、編みかけされていないセル３が”０”のセルゲインｇを有するセルである。
【００１１】
図３２（ａ），（ｂ），（ｃ）に示すセルの配置状態においては、いずれも、編みかけのセル２をカットライン１の向こう側の他方のブロックに移動することにより、カット数を減少することができる。また、実際のセルの移動に際しては、それぞれのブロックにおいて、ブロックの面積とブロック内に含まれるセルの総和の面積との比がバランスがとられるような配慮がなされる。
【００１２】
【発明が解決しようとする課題】
上述した従来のミニカット法では、各分割ブロックに含まれるセルの集合間のネットの接続数、すなわち、カット数を最小化する操作を階層的に行うことにより、セルの配置位置を決定し、より最適なセルの配置を求めるようにしている。
【００１３】
しかしながら、ミニカット法では、階層的に分割された領域内の情報（セルの総和面積やセル数など）のみを用いてセルの配置を決定しているため、集積回路全体での配線長を制御することができないという問題があった。
【００１４】
このため、あるネットの長さが必要以上に長くなってしまい、この結果として、信号の伝播遅延など集積回路全体の性能が低下してしまうという問題があった図３３は、ミニカット法における一般的な概略配線の方法を説明する図である。この概略配線では、実際の端子ではなく、分割されたブロックの中心に端子が存在するものと仮定して、配線を実行する。そして、この実行結果を基に、仮想的な配線長（概略配線長）を求めている。同図において、ｎｅｔ１，ｎｅｔ２，ｎｅｔ３がネットであり、１〜６の白丸が仮想的な端子である。しかしながら、この方法では、ＲＡＭ，ＲＯＭ、Ｉ／Ｏバッファセルなどのような固定セルに接続されているネットの長さは、実際よりも、短めに算出されてしまう場合がありうる。このため、予め指定されたネットの線長制約を守ってセルの配置を行うためには、より、正確にネットの配線長を予測することが重要になってくる。
【００１５】
また、ミニカット法において、階層化が進み、各ブロックがより小さく分割されていくと、沢山のセルを含むブロックでは実際の配線長は長くなり易くなり、概略配線を用いて算出される配線長と実際の配線長との間に差異が生じてくる。すなわち、概略配線情報を基に算出される概略配線長は、実際の配線長よりも短めに算出され易くなる。
【００１６】
したがって、この場合においても、指定されたネットの線長制約を守ってセルの配置を行うためには、より、正確にネットの配線長を予測することが重要になってくる。
【００１７】
本発明は、ミニカット法において、分割ブロック間の概略配線を行う際、ネットのセルを分割ブロックに移動する際の該ネットの概略配線長の増減を、より正確に予測できるようにすることを目的とする。また、上記のようにして、ネットのセルを分割ブロックに移動する際の該ネットの概略配線長の増減を正確に予測しながら、ネットの指定配線長の制約が守れるようなセルの配置を行うことを目的とする。
【００１８】
【課題を解決するための手段】
図１は、本発明（第一の発明）の原理を説明する図である。
この第一の発明は、以下の手段を備える。
【００１９】
概略配線手段４１は、各セルの端子が各セルが属するブロックの中心に位置するものと仮定して、各ネットにつながっているセル間を配線する。
配線長増減予測手段４２は、該概略配線手段４１によって得られた概略配線情報を基に、あるブロックをカットラインによって分割する際に、そのブロックに属しているセルを該カットラインに対していずれの側にある分割ブロックに移動すれば、そのセルにつながっているネットの概略配線長が増減するかを予測する。
【００２０】
したがって、あるブロックをカットラインによって分割する際に、そのブロックに属しているセルをいずれの分割ブロックに移動すれば、そのセルが接続されているネットの概略配線長が減少または増加しないかを判断することが可能になる。
【００２１】
図２は、本発明（第二の発明）の原理を説明する図である。
この第二の発明は、集積回路の領域にカットラインを設定して、該カットラインにより切断される配線数であるカット数が最小となるように該カットラインによって分割された領域間でセルを移動する操作を繰り返しながら該集積回路を構成するセルの初期配置を決定する集積回路の初期配置決定装置を前提とし、以下の手段を備える。
【００２２】
概略配線手段５１は、各セルの端子が各セルが属するブロックの中心に位置するものと仮定して、各ネットにつながっているセル間を配線する。
配線長算出手段５２は、該概略配線手段５１によって得られた概略配線情報を基に、各ネットの概略配線長（論理配線長）を求める。
【００２３】
ヴァイオレーションネット検出手段５３は、該配線長算出手段５２によって算出された各ネットの概略配線長を基に、その現在の概略配線長が予め制約された配線長を越えているネットをヴァイオレーションネットとして検出する。
【００２４】
配線長増減予測手段５４は、該ヴァイオレーションネット検出手段５３によって検出されたヴァイオレーションネットに属するブロックがカットラインによって分割される際に、上記概略配線手段５１によって得られた概略配線情報を基に、そのブロックに属しているヴァイオレーションネットにつながっているセルを、いずれの分割ブロックに移動すれば該ヴァイオレーションネットの概略配線長が増減するかを予測する。
【００２５】
ミニカット法実行手段５５は、該配線長減少予測手段５４によってその配線長が減少または増加しないと予測された分割ブロックの方に、上記ヴァイオレーションネットにつながっているセルを移動させた後、該セルを固定セルに設定し、その後、上記ブロックに対してミニカット法を実行する。
【００２６】
この第二の発明によれば、ヴァイオレーションネットに接続されているセルが属するブロックに対してミニカット法を実行する前に、そのセルを上記ヴァイオレーションネットの配線長が減少または増加しない方の分割ブロックに移動させるので、階層的にミニカット法を実行していく過程で、上記ヴァイオレーションネットの配線長を確実に減少させることが可能になり、この結果として、ヴァイオレーションネットの数を減少させることができる。
図三は、本発明（第三の発明）の原理を説明する図である。
【００２７】
この第三の発明は、集積回路の領域にカットラインを設定して、該カットラインにより切断される配線数であるカット数が最小となるように該カットラインによって分割された領域間でセルを移動する操作を繰り返しながら該集積回路を構成するセルの初期配置を決定する集積回路の初期配置決定装置を前提とし、以下の手段を備える。
【００２８】
概略配線手段６１は、各セルの端子が各セルが属するブロックの中心に位置するものと仮定して、各ネットにつながっているセル間を配線する。
配線長算出手段６２は、該概略配線手段６１によって得られた概略配線情報を基に、各ネットの概略配線長（論理配線長）を求める。
【００２９】
クリティカルネット検出手段６３は、該配線長算出手段６２によって算出された各ネットの概略配線長を基に、その現在の概略配線長が予め制約された配線長のα％を越えているネットをクリティカルネットとして検出する。
【００３０】
ステーブルネット検出手段６４は、ミニカット法の実行開始前にカットラインによりカットされていると共に、該実行開始後にも該カットラインによりカットされているネットをステーブルネットとして検出する。
【００３１】
セル移動手段６５は、上記クリティカルネット検出手段６３の検出結果と上記ステーブルネット検出手段６４との検出結果とを基に、ステーブルネットとなっており、かつクリティカルネットとともなっているネットにつながっている全てのセルを、同一のブロックに移動させる。
【００３２】
ミニカット法実行手段６６は、該セル移動手段の処理６５により得られたセル配置を初期配置としてミニカット法を実行する。
上記αは、例えば、７０≦α≦８０の範囲内の値である。
【００３３】
上記第三の発明では、ステーブルネットとなっているクリティカルネットについて、そのクリティカルネットに接続されている全てのセルを同一のブロックに移動させてからミニカット法を実行させるので、クリティカルネットがカットされないセルの最終配置が得られ易くなる。したがって、クリティカルネットがヴァイオレーションネットに変化する確率を減少できると共に、階層的にミニカット法を実行していく過程で、クリティカルネットの配線長を、次第に短くしていくことが可能となり、そのネットの配線長を最終的に短くできる。
【００３４】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施例を説明する。
本発明の第一の実施例は、ミニカット法において概略配線を行う際、あるネットに固定セルがつながっている場合、その固定セルとその固定セルが属するブロックの中心座標との間の距離を求め、この距離をネットの線長に加味することにより、概略配線長をより正確に求めるものである。
【００３５】
図４は、固定セルが存在する集積回路１４０のセルの配置状態を示す図である。
同図において、水平方向にｘ軸が、垂直方向にｙ軸が設定されている。また、同図に示す、ｘ軸、ｙ軸方向の”１”〜”５”の数字は、それぞれ、ｘ軸、ｙ軸方向のブロック座標の値である。
【００３６】
上記集積回路１４０の各ブロックは、ブロックＩＤ（ｂｌｏｃｋ  ＩＤ；ブロック識別子）によって識別される。このブロック  ＩＤは、（ｘ，ｙ）によって表現される。ｘ，ｙは、それぞれ、ブロックのｘ軸方向、ｙ軸方向のブロック座標の値である。また、”１”〜”５”の数字が付与された白丸は、集積回路１４０の概略配線において設定される５個のセル（Ｃｅｌｌ１〜５）の仮想端子である。また、”６”の数字が付与された黒丸は、固定セルＣｅｌｌ６の端子である。さらに、ｎｅｔ１、２、３は、ネットを表す。
【００３７】
図５は、上記集積回路１４０において、６個の各セル（Ｃｅｌｌ１〜６）が、どのネットに接続されているのかを示すネットリストを示す図である。
また、図６は、上記各ネット（ｎｅｔ１〜ｎ３）につながれているセルの情報を示すセルリストを示す図である。同図に示すように、ｎｅｔ１には、Ｃｅｌｌ１とＣｅｌｌ６がつながれている情報が連結リストによって示されている。これを、
ｎｅｔ１＝｛Ｃｅｌｌ１，Ｃｅｌｌ６｝
で表現する。同様ににして、
ｎｅｔ２＝｛Ｃｅｌｌ２，Ｃｅｌｌ５｝
ｎｅｔ３＝｛Ｃｅｌｌ３，Ｃｅｌｌ４｝
と表現する。
【００３８】
また、上記ｎｅｔ１，ｎｅｔ２，ｎｅｔ３を要素（ｏｂｊｅｃｔ；オブジェクト）とするリストをｎｅｔ２ｃｅｌｌと表現する。すなわち、
ｎｅｔ２ｃｅｌｌ＝｛ｎｅｔ１，ｎｅｔ２，ｎｅｔ３｝
と表現する。
【００３９】
さらに、図７は、上記６個の各セル（Ｃｅｌｌ１〜６）について、どのブロックに属しているか、固定セルであるか否かなどの情報を記憶しているセルテーブル１５０の構成を示す図である。
【００４０】
同図において、Ｃｅｌｌ  ＩＤ（セルＩＤ）の値「ｉ」は、Ｃｅｌｌｉの識別子となる番号である。また、Ｃｅｌｌ  ｐｏｓｉｔｉｏｎ（ｘ，ｙ）は、固定セルの座標値である。さらに、ｆｉｘｅｄ  Ｆｌａｇは、各セルＣｅｌｌｉ（ｉ＝１〜６）が、固定セルであるか否かを示すフラグであり、「１」であれば固定セルであることを示す。
【００４１】
図７に示すセルテーブル１５０には、セルＩＤの値が「６」のＣｅｌｌ６が、固定セルであり、その座標値が（３０、４０）であることを示す情報が格納されている。また、Ｃｅｌｌ６以外のＣｅｌｌ１〜５が、固定セルでないことを示す情報も格納されている。
【００４２】
図８は、上記集積回路１４０の各ブロックの中心座標の値を格納しているブロックテーブル（ｂｌｏｃｋ  Ｔａｂｌｅ）１６０の構成を示す図である。
このテーブル１６０においては、上記各ブロックはブロックＩＤによって示され、その中心位置（ｃｅｎｔｅｒ  ｐｏｓｉｔｉｏｎ）の座標（ｘ，ｙ）が、該ブロックＩＤに対応して格納されている。すなわち、例えば、ブロックＩＤが（１、１）であるブロックの中心座標として、（５、５）が格納されている。また、ブロックＩＤが（３、５）であるブロックの中心座標として、（２５、４５）が格納されている。
【００４３】
図９は、第一実施例において、各ネットの概略配線長を求める処理を説明するフローチャートである。
まず、ｎｅｔ２ｃｅｌｌから先頭のオブジェクト（ｏｂｊｅｃｔ）を取り出し、これを変数ｎｅｔに代入する（Ｓ１０１）。
【００４４】
これにより、図６に示すｎｅｔ２ｃｅｌｌの場合、まず、ｎｅｔ１が変数ｎｅｔに代入される。
次に、変数ｎｅｔが「ＮＵＬＬ」（空）であるか否かを判別し（Ｓ１０２）、「ＮＵＬＬ」でなければ（Ｓ１０２、ｎｏ），該変数ｎｅｔに代入されているネットに対してブロック（ｂｌｏｃｋ）単位で概略配線を行う。そして、この概略配線により得られた概略配線情報を基に、従来の方法により各ネットの概略配線長を算出する（Ｓ１０３）。
【００４５】
この概略配線により、ネットｎｅｔ１に対して図４に示すような概略配線が行われると、図１０（ａ）に示す概略配線のリストが作成される。同図（ａ）において、ｇｒｎｅｔ１は、ネットｎｅｔ１の概略配線のリストであり、（ｉ，ｊ）｛ｉ＝１〜５；ｊ＝１〜５｝は、その概略配線のルーティングに属しているブロックのブロックＩＤ（ｂｌｏｃｋ  ＩＤ）である。
【００４６】
次に、変数ｎｅｔに設定されているネットの概略配線リストから先頭のブロックＩＤ（ｉ，ｊ）を取り出し、そのｉ，ｊを、それぞれ、変数ｂｌｏｃｋ．ｘ，ｂｌｏｃｋ．ｙに代入する（Ｓ１０４）。
【００４７】
続いて、上記概略配線リストに未処理のブロックＩＤが有るか否か，すなわち、上記概略配線リストから新たなブロックＩＤを取り出せたか否かを判別する（Ｓ１０５）。そして、未処理のブロックＩＤを取り出したならば（Ｓ１０５、ｙｅｓ）、該ブロックＩＤを有するブロックに属するセルが有るか否か調べ、セルが有ればそのセルが固定セル（ｆｉｘｅｄ  Ｃｅｌｌ）であるか否かを判別する（Ｓ１０６）。
【００４８】
そして、固定セルであれば（Ｓ１０６、ｙｅｓ）、該固定セルとその固定セルが存在するブロックの中心座標との間の距離を算出し、この距離を既に求められている概略配線長に加算する（Ｓ１０７）。該距離は、例えば、固定セルと上記ブロックの中心座標のｘ軸方向の距離ｄｘ  （両者のｘ座標の差の絶対値）と固定セルと上記ブロックの中心座標のｙ軸方向の距離ｄｙ  （両者のｙ座標の差の絶対値）との和である（図４参照）。
【００４９】
次に、上記概略配線リストから次のブロックＩＤ（ｉ，ｊ）を取り出し、そのｉ，ｊを、それぞれ、変数ｂｌｏｃｋ．ｘ，ｂｌｏｃｋ．ｙに代入する（Ｓ１０８）。そして、再び、ステップＳ１０５に戻る。
【００５０】
一方ステップＳ１０６でセルが固定セルでないと判別すると（Ｓ１０６，ｎｏ）、ステップＳ１０７の処理は行わず、ステップＳ１０８に移る。
上記ステップＳ１０５〜Ｓ１０８の処理は、ステップＳ１０５で上記概略配線リストから取り出すブロックＩＤが無いと判別されるまで（Ｓ１０５，ｎｏ）、繰り返される。
【００５１】
以上の処理により、ネットｎｅｔ１において、ブロックＩＤ（３、５）に属する固定セルＣｅｌｌ６が検出され、該ブロックＩＤ（３、５）を有するブロックの中心座標（２５、４５）と該固定セルＣｅｌｌ６の座標（３０、５０）との間の距離が上記ステップＳ１０７で概略配線に加算される。尚、上記ブロックの中心座標（２５、４５）は図８のブロックテーブル１６０から、上記固定セルＣｅｌｌ６の座標（３０、５０）は図７のセルテーブル１５０から読みだされる。
【００５２】
ステップＳ１０５で、ｎｅｔ２ｃｅｌｌから取り出した先頭のネット（ｏｂｊｅｃｔ）の概略配線リストの全てのブロックＩＤについて上記ステップＳ１０５〜Ｓ１０８の処理を終了したと判別すると（Ｓ１０５，ｙｅｓ），ｎｅｔ２ｃｅｌｌから次のｏｂｊｅｃｔを取り出し（Ｓ１０９）、再び、上述したステップＳ１０２〜Ｓ１０８の処理を、上記ｏｂｊｅｃｔとなっているネットに対して行う。
【００５３】
これにより、図６に示すｎｅｔ２ｃｅｌｌの場合、次にｎｅｔ２に対して  ステップＳ１０３で概略配線が行われ、図１０（ｂ）に示す概略配線リストｇｒｎｅｔ２が作成される。ｎｅｔ２には固定セルがつながっていないので、上記ステップＳ１０７の処理は実行されない。したがって、概略配線長は増加しない。
【００５４】
また、続いて、ステップＳ１０９でｎｅｔ２ｃｅｌｌから次のｏｂｊｅｃｔとしてｎｅｔ３が取り出され、このｎｅｔ３に対しても、ステップ１０３で概略配線が行われる。そして、図１０（ｃ）に示す概略配線リストｇｒｎｅｔ３が作成される。ｎｅｔ３も、ｎｅｔ２と同様に固定セルがつながっていないので、上記ステップＳ１０７の処理は実行されない。したがって、概略配線長は増加しない。
【００５５】
次に、ステップ１０２で、ｎｅｔ２ｃｅｌｌから取り出したｏｂｊｅｃｔが「ＮＵＬＬ」であると判別され（Ｓ１０２，ｙｅｓ），図９のフローチャートの処理が終了する。
【００５６】
次に、本発明の第二の実施例について説明する。
この第二の実施例は、あるネットにおいて、そのネットにつながっているセルが同一のブロック内に複数存在する場合、そのセル数によりそれらのセルがどの程度分散するかを確率的に求め、その分散確率をネットの線長に加味することにより、概略配線長をより正確に求めるものである。
【００５７】
図１１は、このようなネットを有する集積回路２００を示す図である。
同図において、ネットｎｅｔ３には、ブロックＩＤが（２、２）のブロックに存在する５個のセルＣｅｌｌ３、７、８、９，１０がつながっている。
【００５８】
この集積回路２００のネットリストを図１２に、セルリストを図１３に示す。また、図１４は、上記集積回路２００の各セルがどのブロックに属しているかを管理しているセルテーブル２１０の構成図である。例えば、図１２のセルリストと図１４のセルテーブル２１０を参照することにより、ネットｎｅｔ３に属する５個のセル（Ｃｅｌｌ３、７、８、９、１０）がブロックＩＤが（２、２）のブロックに属していることを知ることができる。
【００５９】
第二実施例では、あるネットが属するブロックにおいて、そのネットに接続していて、かつ、そのブロックに属するセルの数をｃｅｌｌＮｕｍと定義する。そして、そのブロックの内部内での上記ネットの配線長ｗを、
ｗ＝Ｋｌｏｇ（ｃｅｌｌＮｕｍ）        （１）
として求める。
【００６０】
このとき、Ｋは任意の定数である。このＫの値としては、例えば、ブロックの周囲長をＬとした場合、
Ｋ＝０．７Ｌ                          （２）
とする。
【００６１】
図１５は、第二実施例において、ネットの概略配線長を求める処理を説明するフローチャートである。
まず、ｎｅｔ２ｃｅｌｌから先頭のオブジェクト（ｏｂｊｅｃｔ）を取り出し、これを変数ｎｅｔに代入する（Ｓ２０１）。
【００６２】
次に、変数ｎｅｔが「ＮＵＬＬ」（空）であるか否かを判別し（Ｓ２０２）、「ＮＵＬＬ」でなければ（Ｓ２０２、ｎｏ），該変数ｎｅｔに代入されているネットに対してブロック（ｂｌｏｃｋ）単位で概略配線を行う。そして、この概略配線により得られた概略配線情報を基に、従来の方法により、各ネットの概略配線長を算出する（Ｓ２０３）。
【００６３】
次に、変数ｎｅｔに設定されているネットの概略配線リストから先頭のブロックＩＤ（ｉ，ｊ）を取り出し、そのｉ，ｊを、それぞれ、変数ｂｌｏｃｋ．ｘ，ｂｌｏｃｋ．ｙに代入する（Ｓ２０４）。
【００６４】
続いて、上記概略配線リストに未処理のブロックＩＤが有るか否か，すなわち、上記概略配線リストから新たなブロックＩＤを取り出せたか否かを判別する（Ｓ２０５）。そして、未処理のブロックＩＤを取り出したならば（Ｓ２０５、ｙｅｓ）、該ブロックＩＤを有するブロックに属するセルが有るか否か調べ、セルが有れば、そのセルの個数を求め、これを変数ｃｅｌｌＮｕｍに代入する（Ｓ２０６）。
【００６５】
そして、上記式（１）により上記ブロック内の配線長ｗを算出する。そして、このｗを既に求められている概略配線長に加算する（Ｓ２０７）。
次に、上記概略配線リストから次のブロックＩＤ（ｉ，ｊ）を取り出し、そのｉ，ｊを、それぞれ、変数ｂｌｏｃｋ．ｘ，ｂｌｏｃｋ．ｙに代入する（Ｓ２０８）。そして、再び、ステップＳ２０５に戻る。
【００６６】
上記ステップＳ２０５〜Ｓ２０８の処理は、ステップＳ２０５で上記概略配線リストから取り出すブロックＩＤが無いと判別されるまで（Ｓ２０５，ｎｏ）、繰り返される。
【００６７】
上記処理により、図１１に示す集積回路２００のネットｎｅｔ３の場合、最初のステップＳ２０４でブロックＩＤとして（２、２）が取り出され、ｂｌｏｃｋ．ｘに”２”がｂｌｏｃｋ．ｙに”２”が代入される。そして、ステップＳ２０６でブロックＩＤが（２、２）のブロックに属するネットｎｅｔ３につながっているセルの個数（＝５）が算出される。そして、変数ｃｅｌｌＮｕｍに”５”が代入される。続いて、ステップＳ２０７で上記式（１）の計算が実行され、その計算結果ｗが、それまでの概略配線長に加えられる。
【００６８】
次のステップＳ２０４でブロックＩＤとして（２、３）が取り出され、ｂｌｏｃｋ．ｘに”２”がｂｌｏｃｋ．ｙに”３”が代入される。そして、ステップＳ２０６でブロックＩＤが（２、３）のブロックに属するネットｎｅｔ３につながっているセルの個数（＝１）が算出される。そして、変数ｃｅｌｌＮｕｍに”１”が代入される。続いて、ステップＳ２０７で上記式（１）の計算が実行され、その計算結果ｗ（＝０）が、それまでの概略配線長に加えられる。
【００６９】
また、図１１に示す集積回路２００のネットｎｅｔ１の場合、ブロックＩＤが（１、１）と（３、５）のブロックについて、上記ステップＳ２０７で上記式（１）の計算が実行される。そして、ブロックＩＤが（１、１）と（３、５）であるブロックのブロック数は”１”であるので、ブロック内配線長ｗは”０”となり、上記ステップ２０３で算出した概略配線長は変化しない。したがって、この場合には、従来と同一の概略配線長が得られる。
【００７０】
また、図１１に示す集積回路２００のネットｎｅｔ２の場合、ブロックＩＤが（５、１）と（２、４）のブロックについて、上記ステップＳ２０７で上記式（１）の計算が実行される。そして、この場合も、ブロックＩＤが（５、１）と（２、４）であるブロックのブロック数は”１”であるので、上記ネットｎｅｔ２と同様に、従来と同一の概略配線長が得られる。
【００７１】
このように、あるネットの概略配線長を算出する際、そのネットのセルが属するブロックについては、該ブロック内に属するそのネットのセルの個数を基にした該ブロック内でのセルの分散確率を考慮した上記式（１）を用いて、そのブロック内配線長ｗを算出し、これを、従来の方法で算出した概略配線長に加算するので、同一ブロック内に属する複数のセルが接続されているネットの概略配線長を、従来よりも、正確に算出できる。
【００７２】
次に、本発明の第三実施例について説明する。
この第三実施例は、ミニカット法において、あるブロックをカットする際、そのブロックに含まれるセルを、どちらの分割ブロックに配置すれば、どの程度、配線長が増減するかを、概略配線の配線情報を基にして予測するものである。
【００７３】
図１６は、この第三実施例の手法を説明する模式図である。
同図は、集積回路３００において、ネットｎｅｔ２につながっているセルＣｅｌｌ２が属しているブロック３０２を、カットライン３０４によってカットしようとする場合を示している。この場合、上記ブロック３０２をカットライン３０４によって垂直方向にカットすることにより、該ブロック３０２は、同図に示す２つの分割ブロック３０２Ｌと３０２Ｒに分割される。
【００７４】
このとき、セルＣｅｌｌ２を上記２つの分割ブロック３０２Ｌと３０２Ｒの配置した場合における配線長の増減を、概略配線情報を基にして予測する。この場合には、セルＣｅｌｌ２を分割ブロック３０２Ｌの方に配置すれば、概略配線長が減少するようになることが予測される。
【００７５】
図１７〜図２０は、ブロックをカットラインによって垂直方向にカットする際に、そのブロックに属しているセル（以後、ｓｏｕｒｃｅセルと呼ぶことにする）をどちらの分割ブロックに配置すれば、概略配線長が増加するかを予測する手法を説明する図である。また、該ｓｏｕｒｃｅセルとネットでつながっているセルをｔａｒｇｅｔセルと呼ぶ。
【００７６】
図２０は、ｓｏｕｒｃｅセル４１１が上側のブロックに属しているｔａｒｇｅｔセル４２１と配線される場合、該ｓｏｕｒｃｅセル４１１が属しているブロック４１０が垂直方向にカットされる際の、概略配線長の増加を予測する方法を説明する図である。尚、ｔａｒｇｅｔセル４２１は、ｓｏｕｒｃｅセル４１１と直接接続されるセルである。
【００７７】
この場合、ｔａｒｇｅｔセル４２１が属するブロック４２０は、既に分割されており、ｔａｒｇｅｔセル４２１は、分割ブロック４２０Ｒ，４２０Ｌのいずれかに属する。また、ｓｏｕｒｃｅセル４１１は、ブロック４１０が垂直方向にカットされることにより、右側の分割ブロック４１０Ｒまたは左側の分割ブロック４１０Ｌのいずれかに配置されることになる。
【００７８】
同図（ａ）に示すように、ｔａｒｇｅｔセル４２１に接続されている配線が、該ｔａｒｇｅｔセル４２１の属する分割ブロックのみならず、他方の分割ブロックも通過する場合には、ｓｏｕｒｃｅセル４１１を右側の分割ブロック４１０Ｒまたは左側の分割ブロック４１０Ｌのいずれに移動させても、概略配線長は増加しない。
【００７９】
これに対して、同図（ｂ），（ｃ）に示すように、ｔａｒｇｅｔセル４２１に接続されている配線が、該ｔａｒｇｅｔセル４２１の属する分割ブロック内のみを通過する場合には、ｓｏｕｒｃｅセル４１１をｔａｒｇｅｔセル４２１と反対側の分割ブロックに移動すると概略配線長は長さβだけ増加する。
【００８０】
また、ｔａｒｇｅｔセル４２１の配線パターンが、同図（ａ），（ｂ），（ｃ）以外の場合には、概略配線長の増加は”０”である。
次に、図１８は、ｓｏｕｒｃｅセル４１１の配線パターンを基に、概略配線長の増加を予測する方法を説明する図である。
【００８１】
同図に示すように、ｓｏｕｒｃｅセル４１１に接続されている配線が、右側の分割ブロック４１０Ｒまたは左側の分割ブロック４１０Ｌのいずれか一方のみを通過している場合、この配線が通過している分割ブロックとは別の分割ブロックに移動すると、概略配線長は長さβだけ増加する。すなわち、この場合、概略配線を、新たに長さβだけ延ばす必要がある。
【００８２】
上記以外の場合には、ｓｏｕｒｃｅセル４１１をいずれの分割ブロックの方に移動しても概略配線長は増加しない。例えば、ｓｏｕｒｃｅセル４１１の概略配線がブロック４１０全体を水平方向に通過している場合には、概略配線長は増加しない。
【００８３】
続いて、図１９は、ｓｏｕｒｃｅセル４１１が上側のブロックに属し、ｔａｒｇｅｔセル４２１が下側のブロックに属している下側ｔａｒｇｅｔセルである場合の、概略配線長の増加を予測する方法を説明する図である。
【００８４】
このとき、ｔａｒｇｅｔセル４２１が属するブロック４２０は、まだ分割されていない。この場合、ｔａｒｇｅｔセル４２１に接続している概略配線のパターンが、ブロック４２０を、将来、垂直方向にカットした場合に生成される２つの分割ブロック４２１Ｒ，４２１Ｌのいずれか一方の分割ブロックのみを通過するようなパターンとなっているとすると、ｓｏｕｒｃｅセル４１１をその分割ブロックとは逆の側の分割ブロックに移動すると、概略配線長がβだけ増加する。このような場合以外は、概略配線長は増加しない。
【００８５】
図２０は、図１９の予測方法をより詳細に説明する図である。
同図（ａ）に示すように、ｓｏｕｒｃｅセル４１１の属するブロック４１０を垂直方向に分割する前に、該ｓｏｕｒｃｅセル４１１に接続された概略配線は垂直方向に下側に延びており、下側ｔａｒｇｅｔセル４２１に接続された概略配線は垂直方向の上下と水平方向の右側に延びていたとする。
【００８６】
この場合、同図（ｂ）に示すように、上記ｓｏｕｒｃｅセル４１１を左側の分割ブロック４１０Ｌの方に移動すると、概略配線長は長さβだけ増加する。一方、同図（ｃ）に示すように、上記ｓｏｕｒｃｅセル４１１を右側の分割ブロック４１０Ｒの方に移動した場合には、概略配線長は増加しない。
【００８７】
また、同図（ｄ）に示すように、ｓｏｕｒｃｅセル４１１の属するブロック４１０を垂直方向に分割する前に、該ｓｏｕｒｃｅセル４１１に接続された概略配線は垂直方向下側と水平方向の両側に延びており、下側ｔａｒｇｅｔセル４２１に接続された概略配線は垂直方向の上下と水平方向の右側に延びていたとする。
【００８８】
この場合、同図（ｅ）に示すように、上記ｓｏｕｒｃｅセル４１１を左側の分割ブロック４１０Ｌの方に移動すると、概略配線長は長さβだけ増加する。一方、同図（ｆ）に示すように、上記ｓｏｕｒｃｅセル４１１を右側の分割ブロック４１０Ｒの方に移動した場合には、概略配線長は増加しない。
【００８９】
以上は、ｓｏｕｒｃｅセル４１１が属するブロック４１０が垂直方向にカットされる場合に、ｓｏｕｒｃｅセル４１１とｔａｒｇｅｔセル４２１の概略配線パターン情報に基づいて、ｓｏｕｒｃｅセル４１１を分割ブロック４１１Ｒまたは分割ブロック４１１Ｌのいずれの方に移動すれば、概略配線長が増加または増加しないかを予測する方法について述べたが、ｓｏｕｒｃｅセル４１１とｔａｒｇｅｔセル４２１が水平方向に概略配線によって接続される場合についても、基本的に同様の方法によって概略配線長が増加または増加しないかを予測することができる。
【００９０】
また、概略配線長が”増加”または”増加しない”の２つの場合のみならず、概略配線長が減少する場合についても予測することが可能である。すなわち、上記図１７〜図２０に示されている以外のパターンを考慮して、基本的にｓｏｕｒｃｅセル４１１とｔａｒｇｅｔセル４２１の距離が短くなるように、ｓｏｕｒｃｅセル４１１を移動させる位置を決定すればよい。
【００９１】
次に、本発明の第四の実施例について説明する。
この第四の実施例は、予め指定された線長制約を守れないネットをｖｉｏｌａｔｉｏｎ  ｎｅｔ（ヴァイオレーションネット）と定義し、このヴァイオレーションネットにつながっているセルが属するブロックが分割される際に、上記第三の実施例の方法を用いて、該セルを概略配線長が減少する分割ブロックの方に移動させ（概略配線長が減少する分割ブロックに移動できない場合には、概略配線長が増加しない分割ブロックの方に移動させる）、該移動後にそのセルを固定セルとして取り扱うものである。
【００９２】
このように固定セルに設定されたヴァイオレーションネットは、ミニカット法の実行時において、移動対象のセルとして取り扱われないため、ヴァイオレーションネットの概略配線長はミニカット法の実行によって増加することはない。そして、階層的に実行される各ミニカット法の実行前に上記の処理をヴァイオレーションネットにつながっているセルに対して施すことにより、そのヴァイオレーションネットの概略配線長を確実に減少させていくことが可能となり、最終的にヴァイオレーションネットを解消することが可能になる。
【００９３】
以下、図２１に示す集積回路４００を例にして説明する。
該集積回路４００における３個のネットｎｅｔ１、２、３に対して、それぞれ、”６０”、”６０”及び”８０”の配線長が、予め線長制約（指定配線長）として指定されているものとする。したがって、ネットｎｅｔ１は、その論理配線長が”６０”を越えた場合ヴァイオレーションネットとなる。同様にして、ネットｎｅｔ２の場合には”６０”、ネットｎｅｔ３の場合には”８０”を越えた場合にバイオレーションネットとなる。上記論理配線長は、例えば、上記概略配線長が該当する。尚、上記論理配線長及び上記概略配線長の長さの単位は、例えば、グリッド（ｇｒｉｄ）の間隔の長さである。
【００９４】
図２２は、上記集積回路４００の各ネットがヴァイオレーションネットとなっているか否かを管理している管理テーブル４５０の構成を示す図である。
同図に示すように、この管理テーブル４５０には、各ネットｎｅｔ１、２、３に対応して、指定配線長、論理配線長、ｖｉｏｌａｔｉｏｎ  Ｆｌａｇ（ヴァイオレーションフラグ）及びｃｒｉｔｉｃａｌ  Ｆｌａｇ（クリティカルフラグ）が格納されている。
【００９５】
上記ヴァイオレーションフラグは、対応するネットがヴァイオレーションネットとなった場合に”ＴＲＵＥ”に設定される。また、ヴァイオレーションネットとなっていない場合には”ＦＡＬＳＥ”に設定される。
【００９６】
また、本実施例では、論理配線長が指定配線長のα％を越えたネットを、ｃｒｉｔｉｃａｌ  ｎｅｔ（クリティカルネット）と定義する。上記αの値としては、例えば、”７０”〜”８０”の範囲の値が使用される。上記クリティカルフラグは、対応するネットがクリティカルネットとなった場合に”ＴＲＵＥ”に設定され、クリティカルネットとなっていない場合には”ＦＡＬＳＥ”に設定される。
【００９７】
また、上記集積回路４００に対して、図２３、図２４に示すネットリスト、セルリストが作成される。
図２２に示す管理テーブル４５０においては、ネットｎｅｔ１がヴァイオレーションネットとなっていることがヴァイオレーションフラグにより記憶されている。また、ネットｎｅｔ３がクリティカルネットとなっていることがクリティカルフラグにより記憶されている。また、ネットｎｅｔ２は、ヴァイオレーションネットでもクリティカルネットでもないことが、ヴァイオレーションフラグとクリティカルフラグにより記憶されている。
【００９８】
図２５は、第四実施例におけるミニカット法の実行方法を説明するフローチャートである。
まず、ｎｅｔ２ｃｅｌｌから先頭のｏｂｊｅｃｔを取り出し、これを変数ｎｅｔに代入する（Ｓ４０１）。
【００９９】
続いて、該変数ｎｅｔが「ＮＵＬＬ」であるか否かを判別する（Ｓ４０２）。この判別は、ｎｅｔ２ｃｅｌｌに連結されている全てのネットについてヴァイオレーションネットの判別が終了したか否かを判別する処理である。
【０１００】
上記ステップＳ４０２で、変数ｎｅｔに設定されているネットがヴァイオレーションネットであるか否かを、上記管理テーブル４５０を参照することにより判別する（Ｓ４０３）。
【０１０１】
この判別により、ネットｎｅｔ１がヴァイオレーションネットであると判別される。
上記ステップ４０３で、変数ｎｅｔに設定されているネットがヴァイオレーションネットであると判別すると（Ｓ４０３，ｙｅｓ）、そのヴァイオレーションネットにつながっていて、かつ、現在、カット対象となっているブロックに属するセルを、概略配線長が減少する分割ブロックの方に移動させて固定化するクラスター化（ｃｌｕｓｔｅｒ化）の処理を行った後、該クラスター化の対象となったセルを固定セルに設定する（Ｓ４０４）。
【０１０２】
上記固定セルの設定処理は、例えば、各セル毎に用意される特定のフラグを用いて行う。上記処理により、例えば、現在、ブロックＩＤが（２、５）のブロックがカット対象のブロックである場合、セルＣｅｌｌ６に対して上記ステップＳ４０４の処理が施され、該セルＣｅｌｌ６は、上記ブロックを垂直方向にカットした際に生成される図２１に示す分割ブロック４２５Ｌの方に移動される。
【０１０３】
次に、ｎｅｔ２ｃｅｌｌから次のｏｂｊｅｃｔを取り出し、これを変数ｎｅｔに代入し（Ｓ４０５），再び、ステップＳ４０２、Ｓ４０３の処理を行う。
これにより、ステップＳ４０３でネットｎｅｔ２がヴァイオレーションネットでないと判別され（Ｓ４０３，ｎｏ）、次に、ステップＳ４０５の処理に移る。
【０１０４】
そして、ステップＳ４０５でｎｅｔ２ｃｅｌｌからネットｎｅｔ３が取り出され、該ネットｎｅｔ３が変数ｎｅｔに代入され、ステップＳ４０２に戻る。続いて、ステップ４０３で該ネットｎｅｔ３がヴァイオレーションネットでないと判別され（Ｓ４０３，ｎｏ），ステップＳ４０５に移る。
【０１０５】
このステップＳ４０５で、ｎｅｔ２ｃｅｌｌからはｏｂｊｅｃｔは取り出されず、変数ｎｅｔには「ＮＵＬＬ」が設定される。そして、再び、ステップＳ４０２に戻り、変数ｎｅｔが「ＮＵＬＬ」であると判別され（Ｓ４０２，ｙｅｓ）、ステップ４０６でミニカット法を実行する。
【０１０６】
上記ミニカット法は、固定セル以外のセルに対して実行される。したがって、上記ヴァイオレーションネットにつながっていると判別されたネットｎｅｔ１のセルＣｅｌｌ６は、固定セルに設定されたために移動されない。
【０１０７】
次に、本発明の第五の実施例を説明する。
この第五の実施例は、本出願人が、以前、出願した、特開平７−１４１４１５号公報の発明において提案した、ミニカット法実行時のステーブルネット（ｓｔａｂｌｅ  ｎｅｔ）に対する取り扱いを、上記クリティカルネットに適用するものである。
【０１０８】
上記先の発明では、ミニカット法の実行前にカットされていて、かつ該ミニカット法の実行後にもカットされているネットを、ステーブルネットと定義し、このステーブルネットにつながっている全てのセルを、強制的に片方のブロックに移動させることにより、セルの最適な配置を求めるものである。また、このようにして、移動させたセルは、以後、固定セルとみなして、ミニカット法の実行により、再度、移動させられることを禁止させる。
【０１０９】
第五の実施例では、ステーブルネットの中から、クリティカルネットとなっているネットを優先的に選択し、そのクリティカルネットにつながっている全てのセルを、片方のブロックに移動させる。
【０１１０】
クリティカルネットは、ヴァイオレーションネットの予備軍であると考えることができ、ミニカット法の実行により該クリティカルネットにつながっているあるセルが他方のブロックに移動することにより、その配線長が増加してヴァイオレーションネットとなってしまう可能性がある。したがって、クリティカルネットとなったネットについては、一つのブロックにまとめて、より配線長が短くなるような操作を施す必要がある。また、ステーブルネットは、ミニカット法の実行後にもカットされたままの状態にある確率が高いことが知られている。したがって、ミニカット法の実行前に与えるセルの初期配置（初期解）において、なるべく、ステーブルネットとなっているクリティカルネットの数を少なくしておくことが、クリティカルネットの配線長を短くする上で望ましい。
【０１１１】
第五の実施例は、基本的に、以上のような考えに基づくものである。
図２６は、ミニカット法を繰り返し実行する際、その各実行前にステーブルネットとなっているクリティカルネットを、非ステーブルネット化する処理を説明するフローチャートである。尚、このフローチャートで、クリティカルネットを検出する際には、上記図２１に示す管理テーブル４５０と同様なテーブルを参照する。
【０１１２】
ミニカット法の実行が終了すると、まず、集積回路内の全てのセルのムーブドフラグ（ｍｏｖｅｄ  Ｆｌａｇ）を”０”にセットする（Ｓ５０１）。
上記ムーブドフラグは、集積回路内の全てのセルに個別に設けられているフラグであり、対応するセルがミニカット法の実行により、一度、移動させられたか否かを示すフラグである。そして、移動させられていれば”１”に、まだ、移動させられていなければ”０”に設定される。
【０１１３】
次に、上記ミニカット法の実行前にステーブルネットとして登録されており、かつ、該ミニカット法実行後にもカットされているネットを、ステーブルネットとして選びだし、そのネットをステーブルネットテーブルに登録する（Ｓ５０２）。
【０１１４】
このステーブルネットテーブルは、上記先の発明の明細書の図１３に示すような構成となっており、フラグ（ｓｔａｂｌｅＮｅｔＴａｂｌｅ［ｉ］．Ｆｌａｇ）により、ステーブルネットを管理している。尚，ｉは、ネットの番号である。このフラグは、対応するステーブルネットが以下に述べるステップＳ５０５〜Ｓ５０７の処理を施されたかか否かを記憶するフラグであり、未処理であれば”０”がセットされる。
【０１１５】
続いて、上記ステーブルネットテーブルのフラグを全て”０”にクリアする（Ｓ５０３）。
すなわち、全てのステーブルネットが未処理であることを、ステーブルネットテーブルに登録する。
【０１１６】
次に、上記ステーブルネットテーブルのフラグが全て”１”になるまで、以下のステップＳ５０５〜Ｓ５０７の処理を繰り返す。
ステップＳ５０５では、ステーブルネットテーブルに登録されているフラグが”０”のステーブルネットの中からクリティカルネットを優先的に選択する。複数のクリティカルネットがある場合には、それらの中からランダムにクリティカルネットを選択する。また、クリティカルネットが無くなった場合には、残りのステーブルネットの中からランダムに選択する（Ｓ５０５）。
【０１１７】
次のステップＳ５０６では、上記選択したネットにつながっている全てのセルを、一つのブロックの方に移動させる。この場合、移動するブロックの選択は、例えば、上記先の発明の明細書の図１０または図１１のフローチャートに示すアルゴリズムによって決定する。すなわち、例えば、上記図１０のフローチャートに示すように、上記選択したネットにつながっている全てのセルのムーブドフラグを調べ、該全てのセルのムーブドフラグが”０”であれば、どちらのブロックに移動先するかは、ランダムに選択する。一方、ムーブドフラグが”１”であるセルが片側のブロックのみに集まっているならば、そのブロックの方に他方の側のブロックに属しているセルを移動させる。
【０１１８】
続くステップＳ５０７では、上記セルの移動を行ったステーブルネットについて、ステーブルネットテーブルのフラグを”１”にセットする。また、該ステーブルネットにつながっている全てのセルのムーブドフラグを”１”にセットする。
【０１１９】
これにより、一つのブロックに全てのセルが移動させられたステーブルネットの全てのセルは固定セルとして取り扱われるので、以後のステップＳ５０５〜Ｓ５０６の処理において、移動させられることはないので、一度、移動したステーブルネットの処理が無効となってしまう事態を防止できる。
【０１２０】
以上述べた図２６のフローチャートに示す処理の結果を、初期解（初期配置）としてミニカット法に与えて、該ミニカット法を実行することにより、クリティカルネットがカットされない最終解が得られる易くなり、この結果として、そのクリティカルネットの配線長を短くすることができる。
【０１２１】
上記第一〜第五の実施例は、組み合わせることも可能である。
すなわち、第一、第三及び第四の実施例を組み合わせる第六の実施例により、ヴァイオレーションネットの概略配線長をより正確に求めることが可能になると共に、ヴァイオレーションネットの数を減少させることができる。
【０１２２】
また、第一、第二、第三及び第四の実施例を組み合わせる第七の実施例により、ヴァイオレーションネットの概略配線長を、上記第六の実施例よりも、さらに、正確に求めることが可能になると共に、ヴァイオレーションネットの数を減少させることができる。
【０１２３】
また、さらに、第一、第三、第四及び第五の実施例を組み合わせる第八の実施例により、ヴァイオレーションネットの概略配線長を、より正確に求めることが可能になると共に、クリティカルネットがヴァイオレーションネットに変化する確率を減少させて、よりヴァイオレーションネットの数を減少させることができる。
【０１２４】
また、さらに、第一、第二、第三、第四及び第五の実施例を組み合わせる第九の実施例により、ヴァイオレーションネットの概略配線長を、上記第八の実施例よりも正確に求めることが可能になると共に、クリティカルネットがヴァイオレーションネットに変化する確率を減少させて、よりヴァイオレーションネットの数を減少させることができる。
【０１２５】
【発明の効果】
以上、説明したように、本発明によれば、集積回路のセル配置において、分割ブロックに移動する際のネットのセルの概略配線長の増減をより正確に予測することが可能になると共に、指定された配線長を越えるネットの数を減少させることが可能になる。したがって、各ネットの配線長制約を守るようにすることが可能になる。そして、このことにより、配線による遅延を指定された範囲内に抑えることが可能になり、回路の性能を高めることができるようになる。
【図面の簡単な説明】
【図１】本発明の原理を説明する図（その１）である。
【図２】本発明の原理を説明する図（その２）である。
【図３】本発明の原理を説明する図（その３）である。
【図４】集積回路において、固定セルがつながっているネットの配線長を求める方法を説明する図である。
【図５】図４に示す集積回路におけるネットリストを示す図である。
【図６】図４に示す集積回路におけるセルリストを示す図である。
【図７】図４に示す集積回路におけるセルテーブルの構成を示す図である。
【図８】図４に示す集積回路の各ブロックの中心座標の値を格納しているブロックテーブルの構成を示す図である。
【図９】第一実施例における、各ネットの概略配線長を求める処理を説明するフローチャートである。
【図１０】図９のフローチャートの概略配線処理で作成される概略配線リストを示す図である。
【図１１】あるブロックに、一つのネットにつながっているセルが複数存在する集積回路の例を示す図である。
【図１２】図１１に示す集積回路のネットリストを示す図である。
【図１３】図１１に示す集積回路のセルリストを示す図である。
【図１４】図１１に示す集積回路の各セルがどのブロックに属しているかを管理しているセルテーブルの構成図である。
【図１５】第二実施例において、各ネットの概略配線長を求める処理を説明するフローチャートである。
【図１６】第三実施例における、概略配線の配線情報を基にした、配線長の増減を予測する手法を説明する模式図である。
【図１７】ブロックをカットラインによって垂直方向にカットする際に、そのブロックに属しているセルをどちらの分割ブロックに配置すれば、概略配線長が増加するかを予測する手法を説明する図（その１）である。
【図１８】ブロックをカットラインによって垂直方向にカットする際に、そのブロックに属しているセルをどちらの分割ブロックに配置すれば、概略配線長が増加するかを予測する手法を説明する図（その２）である。
【図１９】ブロックをカットラインによって垂直方向にカットする際に、そのブロックに属しているセルをどちらの分割ブロックに配置すれば、概略配線長が増加するかを予測する手法を説明する図（その３）である。
【図２０】ブロックをカットラインによって垂直方向にカットする際に、そのブロックに属しているセルをどちらの分割ブロックに配置すれば、概略配線長が増加するかを予測する手法を説明する図（その４）である。
【図２１】第四実施例の説明に使用する集積回路の構成を示す図である。
【図２２】ヴァイオレーションネットとクリティカルネットが登録される管理テーブルの構成を示す図である。
【図２３】図２１に示す集積回路のネットリストを示す図である。
【図２４】図２１に示す集積回路のセルリストを示す図である。
【図２５】第四実施例におけるヴァイオレーションネットを固定セルとして取り扱う処理を説明するフローチャートである。
【図２６】第五実施例におけるクリティカルネットに対する移動処理を説明するフローチャートである。
【図２７】ミニカット法を説明するフローチャートである。
【図２８】ミニカット法によるセルの移動操作の方法を説明する図である。
【図２９】ミニカット法における集積回路の一般的な概略配線データを示す図である。
【符号の説明】
４１、５１、６１  概略配線手段
４２、５２、６２  第一の配線長算出手段
５３、６３        ヴァイオレーションネット検出手段
５４              配線長増減予測手段
５５              ミニカット法実行手段
６３              クリティカルネット検出手段
６４              ステーブルネット検出手段
６５              セル移動手段
【図１】
0003629006.tif 000002
【図２】
0003629006.tif 000003
【図３】
0003629006.tif 000004
【図４】
0003629006.tif 000005
【図５】
0003629006.tif 000006
【図６】
0003629006.tif 000007
【図７】
0003629006.tif 000008
【図８】
0003629006.tif 000009
【図９】
0003629006.tif 000010
【図１０】
0003629006.tif 000011
【図１１】
0003629006.tif 000012
【図１２】
0003629006.tif 000013
【図１３】
0003629006.tif 000014
【図１４】
0003629006.tif 000015
【図１５】
0003629006.tif 000016
【図１６】
0003629006.tif 000017
【図１７】
0003629006.tif 000018
【図１８】
0003629006.tif 000019
【図１９】
0003629006.tif 000020
【図２０】
0003629006.tif 000021
【図２１】
0003629006.tif 000022
【図２２】
0003629006.tif 000023
【図２３】
0003629006.tif 000024
【図２４】
0003629006.tif 000025
【図２５】
0003629006.tif 000026
【図２６】
0003629006.tif 000027
【図２７】
0003629006.tif 000028
【図２８】
0003629006.tif 000029
【図２９】
0003629006.tif 000030