(57)【要約】【課題】本発明は、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようにするＬＳＩフロアプラン決定装置の提供を目的とする。【解決手段】ＬＳＩのフロアプランとなるＬＳＩブロックの配置関係をツリー構造で記述する配置関係記述文の初期解を入力あるいは生成する手段と、配置関係記述文を操作し、その操作による配置関係記述文の規定するＬＳＩのフロアプランでは固定形状のＬＳＩブロックが配置不可能である場合には、その配置が可能となるようにと、その固定形状ＬＳＩブロックを１つ又は複数の他のＬＳＩブロックとマージしてそこにパッキングし、その評価を求めて、それに従って配置関係記述文を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定する手段とを備えるように構成する。【選択図】図１
2007193832.tif 000002
【特許請求の範囲】
【請求項１】
ＬＳＩのフロアプランとなるＬＳＩブロックの配置関係をツリー構造で記述する配置関係記述文の初期解を入力あるいは生成する実行手段と、
上記配置関係記述文を操作し、その操作による上記配置関係記述文の規定するＬＳＩのフロアプランでは固定形状のＬＳＩブロックが配置不可能である場合には、その配置が可能となるようにと、該固定形状ＬＳＩブロックを１つ又は複数の他のＬＳＩブロックとマージしてそこにパッキングし、その評価を求めて、それに従って上記配置関係記述文を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定する決定手段とを備えることを、
特徴とするＬＳＩフロアプラン決定装置。
【請求項２】
請求項１に記載のＬＳＩフロアプラン決定装置において、
上記決定手段は、配置不可能な固定形状ＬＳＩブロックの指定するツリーレベルから上位層に向かう順番に従って、マージ対象となるＬＳＩブロックを選択していくことを、
特徴とするＬＳＩフロアプラン決定装置。
【請求項３】
請求項１又は２に記載のＬＳＩフロアプラン決定装置において、
上記決定手段は、マージしたＬＳＩブロックの指定するツリーレベルから下位層側となる配置関係記述文部分を、上位層側となる配置関係記述文部分よりも大きな確率でもって操作対象として選択していくことを、
特徴とするＬＳＩフロアプラン決定装置。
【請求項４】
請求項１ないし３のいずれか１項に記載のＬＳＩフロアプラン決定装置において、
固定形状のＬＳＩブロックに対して、ＬＳＩブロックの姿勢となる回転コードの初期値を割り付ける割付手段を備え、
上記決定手段は、上記回転コードを操作対象に含めつつ、配置関係記述文を操作し、その評価値を求めて、それに従って配置関係記述文及び／又は上記回転コードを変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定することを、
特徴とするＬＳＩフロアプラン決定装置。
【請求項５】
請求項１ないし３のいずれか１項に記載のＬＳＩフロアプラン決定装置において、
固定形状のＬＳＩブロックに対して、ＬＳＩブロック間のパッキングの実行順序となるパッキング優先順位の初期値を割り付ける割付手段を備え、
上記決定手段は、上記パッキング優先順位を操作対象に含めつつ、配置関係記述文を操作し、その評価値を求めて、それに従って配置関係記述文及び／又は上記パッキング優先順位を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定することを、
特徴とするＬＳＩフロアプラン決定装置。
【請求項６】
請求項１ないし３のいずれか１項に記載のＬＳＩフロアプラン決定装置において、
固定形状のＬＳＩブロックに対して、ＬＳＩブロックのパッキング方向の実行順序となるパッキング優先方向の初期値を割り付ける割付手段を備え、
上記決定手段は、上記パッキング優先方向を操作対象に含めつつ、配置関係記述文を操作し、その評価値を求めて、それに従って配置関係記述文及び／又は上記パッキング優先方向を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定することを、
特徴とするＬＳＩフロアプラン決定装置。
【請求項７】
ＬＳＩのフロアプランとなるＬＳＩブロックの配置関係をツリー構造で記述する配置関係記述文の初期解を入力あるいは生成する処理過程と、
上記配置関係記述文を操作し、その操作による上記配置関係記述文の規定するＬＳＩのフロアプランでは固定形状のＬＳＩブロックが配置不可能である場合には、その配置が可能となるようにと、該固定形状ＬＳＩブロックを１つ又は複数の他のＬＳＩブロックとマージしてそこにパッキングし、その評価を求めて、それに従って上記配置関係記述文を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定する処理過程とを備えることを、
特徴とするＬＳＩフロアプラン決定方法。
【請求項８】
ＬＳＩのフロアプランとなるＬＳＩブロックの配置関係をツリー構造で記述する配置関係記述文の初期解を入力あるいは生成する実行処理と、
上記配置関係記述文を操作し、その操作による上記配置関係記述文の規定するＬＳＩのフロアプランでは固定形状のＬＳＩブロックが配置不可能である場合には、その配置が可能となるようにと、該固定形状ＬＳＩブロックを１つ又は複数の他のＬＳＩブロックとマージしてそこにパッキングし、その評価を求めて、それに従って上記配置関係記述文を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定する決定処理とをコンピュータに実行させるプログラムが記録されることを、
特徴とするプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＳＩのフロアプランを決定するＬＳＩフロアプラン決定装置及び方法と、その装置の実現に用いられるプログラムを記録したプログラム記録媒体とに関し、特に、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようにするＬＳＩフロアプラン決定装置及び方法と、その装置の実現に用いられるプログラムを記録したプログラム記録媒体とに関する。
【０００２】
最近の回路技術の進歩に伴って、ＬＳＩ（特にＶＬＳＩ）の集積度の向上と回路規模の増大には目覚ましいものがある。集積度の向上、回路規模の増大に伴い、１つのＬＳＩチップに含まれるブロックやＲＡＭの個数が増大し、人手でフロアプランをレイアウトすると必ずしも最適なレイアウトが求まらず、しかも時間がかかる。そこで、最適なフロアプランを短い処理時間で求め、そのＴＡＴを上上げていく技術の構築が叫ばれている。
【背景技術】
【０００３】
ＬＳＩを自動レイアウトする場合、先ず最初に、ＬＳＩの持つ機能などを分割して、それを実現するためのチップ面積を求め、それらのチップ面積に応じて、ＬＳＩチップを複数の四角形の領域に分割することでＬＳＩのフロアプランを決定するという処理を行う。
【０００４】
このＬＳＩのフロアプランの決定方法として、slicing treeによるフロアプランの最適化方法が広く用いられている。
【０００５】
slicing treeによるフロアプランでは、階層的に繰り返し分割を行って、個々のＬＳＩブロックの四角形の形状とその位置とを求めることになる。この階層構造は、Ｐolish expressionという文字列で表現されることになる。
【０００６】
例えば、図２２（ａ）に示すフロアプランは、縦に分割するカットラインを「＊」、横に分割するカットラインを「＋」で表すならば、図２２（ｂ）に示すように、
１６＋３５＊２＋７４＋＊＊
というＰolish expressionで表現されることになる。ここで、この「＊」や「＋」はオペレータ（operator）と呼ばれ、数字の部分はオペランド（operand ）と呼ばれている。
【０００７】
slicing treeによるフロアプランでは、このＰolish expressionを変形することによりslicing treeのツリー構造を変形することで最適化を行う。
【０００８】
最適化のアルゴリズムとしては、例えば、Ｓimulated  Ａnnealing（以下、ＳＡと略記する）が用いられる。
【０００９】
このＳＡでは、図２３に示すように、Ｐolish expressionの初期解Ｓ0 と初期温度Ｔ0 とを設定し、温度が規定の終了温度Ｔx に到達するまでの間、設定された各温度Ｔにおいて、Ｐolish expressionにオペレーションを施すことで、Ｐolish expressionをＳからＳ’に変形することを想定して、そのときのＳのコストCost(S) とＳ’のコストCost(S')とを算出し、それから、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）
を算出して、その値が０〜１の間で発生するランダム値よりも大きいときにはＳをＳ’に変形し、小さいときには変形しないことを繰り返していって、その繰り返し回数が規定回数MaxCountに到達するときに、温度ＴをＴx に向けて減少させていくことで、Ｐolish expressionの最適解を求めていくという方法である。
【００１０】
Ｐolish expressionの変形のオペレーションとしては、Ｐolish expressionの持つ２つの隣接するオペランドを交換するとか、Ｐolish expressionの中からある部分を取り出して、そこに含まれるオペレータの補集合（「＊」→「＋」、「＋」→「＊」に変換する）を取るといったものが用意されている。
【００１１】
ＳＡでは、「Cost(S')＜Cost(S) 」のときには、
ｅ-[Cost(S')-Cost(S)]/T ＞１
となるので、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）＝１
となり、これから、０〜１の間で発生するランダム値よりも必ず大きくなることで、ＳはＳ’に必ず変形されることになる。すなわち、コストが小さくなる（高い評価値になる）ときには、ＳはＳ’に必ず変形されることになる。
【００１２】
これに対して、「Cost(S')＞Cost(S) 」のときには、
ｅ-[Cost(S')-Cost(S)]/T ＝ｍ＜１
但し、ｍは温度Ｔが高いほど１に近づく
となるので、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）＜１
となり、これから、０〜１の間で発生するランダム値に応じて、ＳはＳ’に変形されたり変形されなかったりする。このとき、温度が高いときほど、ＳはＳ’に変形される確率が高くなる。
【００１３】
すなわち、ＳＡでは、温度が高い初期の状態にあるときには、コストが悪くなっても、ＳはＳ’に変形されていくことがある。このことにより、初期解にとらわれることがなくなり、他の最適化のアルゴリズムに比べて、よりよい解が得られる可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来技術に従うslicing treeによるＬＳＩのフロアプランでは、Ｐolish expressionの規定する分割形態に従い、各ＬＳＩブロックの面積に応じて最終的なカットラインを線引きするというように、各ＬＳＩブロックの面積だけを考慮して分割を行っており、その形状については考慮していないことから、形状の規定されたＬＳＩブロックを配置する必要がある場合に、それらのＬＳＩブロックの配置が可能となるフロアプランを生成できないという問題点がある。
【００１５】
すなわち、ＬＳＩチップには固定形状のＲＡＭなどを実装することがあるが、従来技術に従うslicing treeによるＬＳＩのフロアプランでは、ＬＳＩブロックの形状については考慮していないことから、ＲＡＭなどのような固定形状のＬＳＩブロックを配置する必要がある場合に、それらのＬＳＩブロックの配置が可能となるフロアプランを生成できないという問題点がある。
【００１６】
本発明はかかる事情を鑑みてなされたものであって、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようにする新たなＬＳＩフロアプラン決定装置及び方法の提供と、その装置の実現に用いられるプログラムを記録した新たなプログラム記録媒体の提供とを目的とする。
【課題を解決するための手段】
【００１７】
図１に本発明の原理構成を図示する。
【００１８】
図中、１は本発明を具備するＬＳＩフロアプラン決定装置であって、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定するものである。
【００１９】
本発明のＬＳＩフロアプラン決定装置１は、ブロック情報管理手段１０と、ネットリスト管理手段１１と、実行手段１２と、割付手段１３と、決定手段１４とを備える。
【００２０】
ブロック情報管理手段１０は、フロアプランの処理対象となるＬＳＩブロックのＩＤに対応付けて、そのＬＳＩブロックの面積と、そのＬＳＩブロックが固定形状を有するのか有しないかの情報と、そのＬＳＩブロック内に配線されるネット数などの情報を管理する。
【００２１】
ネットリスト管理手段１１は、複数のＬＳＩブロックに接続されるネットのＩＤに対応付けて、そのネットに接続されるＬＳＩブロックのＩＤを管理する。
【００２２】
実行手段１２は、ＬＳＩのフロアプランとなるＬＳＩブロックの配置関係をツリー構造で記述する配置関係記述文の初期解を入力あるいは生成する。
【００２３】
割付手段１３は、固定形状のＬＳＩブロックに対して、ＬＳＩブロックの姿勢となる回転コードの初期値を割り付けたり、固定形状のＬＳＩブロックに対して、ＬＳＩブロック間のパッキングの実行順序となるパッキング優先順位の初期値を割り付けたり、固定形状のＬＳＩブロックに対して、ＬＳＩブロックのパッキング方向の実行順序となるパッキング優先方向の初期値を割り付ける。
【００２４】
決定手段１４は、配置関係記述文などを操作し、その評価値を求めて、それに従って配置関係記述文などを変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定する。
【００２５】
ここで、本発明のＬＳＩフロアプラン決定装置１の持つ機能は具体的にはプログラムで実現されるものであり、このプログラムは、フロッピィディスクなどに格納されたり、サーバなどのディスクなどに格納され、それらから本発明のＬＳＩフロアプラン決定装置１にインストールされてメモリ上で動作することで、本発明を実現することになる。
【００２６】
このように構成される本発明のＬＳＩフロアプラン決定装置１では、実行手段１２は、ＬＳＩのフロアプランとなるＬＳＩブロックの配置関係をツリー構造で記述する配置関係記述文の初期解を入力あるいは生成し、これを受けて、決定手段１４は、配置関係記述文を操作し、その操作による配置関係記述文の規定するＬＳＩのフロアプランでは固定形状のＬＳＩブロックが配置不可能である場合には、その配置が可能となるようにと、その固定形状ＬＳＩブロックを１つ又は複数の他のＬＳＩブロックとマージしてそこにパッキングし、その評価を求めて、それに従って配置関係記述文を変更するのか否かを決定することを繰り返していくことで、ＬＳＩのフロアプランを決定する。
【００２７】
このとき、決定手段１４は、配置不可能な固定形状ＬＳＩブロックのパッキングを可能にするために、配置不可能な固定形状ＬＳＩブロックの指定するツリーレベルから上位層に向かう順番に従って、マージ対象となるＬＳＩブロックを選択していくことがある。
【００２８】
また、決定手段１４は、配置不可能な固定形状ＬＳＩブロックの配置が可能となる位置を積極的に探索していくために、マージしたＬＳＩブロックの指定するツリーレベルから下位層側となる配置関係記述文部分を、上位層側となる配置関係記述文部分よりも大きな確率に従って操作対象として選択していくことがある。
【００２９】
更に、このとき、割付手段１３が機能して、固定形状のＬＳＩブロックに対して、ＬＳＩブロックの姿勢となる回転コードの初期値を割り付けたり、固定形状のＬＳＩブロックに対して、ＬＳＩブロック間のパッキングの実行順序となるパッキング優先順位の初期値を割り付けたり、固定形状のＬＳＩブロックに対して、ＬＳＩブロックのパッキング方向の実行順序となるパッキング優先方向の初期値を割り付けることがあり、これを受けて、決定手段１４は、回転コードやパッキング優先順位やパッキング優先方向を操作対象に含めつつ、配置関係記述文を操作することで、ＬＳＩのフロアプランを決定することがある。
【００３０】
このようにして、本発明のＬＳＩフロアプラン決定装置１によれば、固定形状を持つＬＳＩブロックがその固定形状を保持したまま配置されることに対して高いコストが与えられるような形態で、ＬＳＩのフロアプランを決定できるようになる。
【００３１】
これにより、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようになる。
【発明の効果】
【００３２】
本発明によれば、固定形状を持つＬＳＩブロックがその固定形状を保持したまま配置されることに対して高いコストが与えられる形態で、ＬＳＩのフロアプランを決定できるようになる。
【００３３】
これにより、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようになる。
【発明を実施するための最良の形態】
【００３４】
以下、実施の形態に従って本発明を詳細に説明する。
【００３５】
図２に、本発明のＬＳＩフロアプラン決定装置１の一実施形態例を図示する。
【００３６】
この実施形態例に従う本発明のＬＳＩフロアプラン決定装置１は、ブロックテーブル２０と、ネットリストテーブル２１と、ＳＡの最適化アルゴリズムに従ってＬＳＩのフロアプランを決定するＬＳＩフロアプラン決定プログラム２２と、ＬＳＩフロアプラン決定プログラム２２の処理に必要となる初期化処理を実行する初期化処理実行プログラム２３とを備える。
【００３７】
ここで、ＬＳＩフロアプラン決定プログラム２２や初期化処理実行プログラム２３は、計算機が読み取り可能な適当な記録媒体に格納することができる。
【００３８】
図３に、ブロックテーブル２０のテーブルデータの一例を図示し、図４に、ネットリストテーブル２１のテーブルデータの一例を図示する。
【００３９】
図３に示すブロックテーブル２０は、ＬＳＩフロアプラン決定プログラム２２の処理対象となるＬＳＩブロックのＩＤに対応付けて、そのＬＳＩブロックの面積と、そのＬＳＩブロック内に配線されるネット数と、そのＬＳＩブロックが固定形状であるのか否か示すフラグ（固定形状フラグ）と、固定形状のＬＳＩブロックについてはその大きさ（ｘ，ｙ）と、固定形状のＬＳＩブロックについてはその姿勢となる回転コード（どういう向きで固定形状ＬＳＩブロックを配置するのかを指示するコード）とを管理する。
【００４０】
一方、ネットリストテーブル２１は、図４に示すように、複数のＬＳＩブロックに接続されるネットのＩＤに対応付けて、そのネットに接続されるＬＳＩブロックのＩＤを管理する。例えば、「１」というネットＩＤのネットに接続されるＬＳＩブロックは、「１」と「３」と「６」と「７」というＬＳＩブロックであるということを管理するのである。
【００４１】
図５に、初期化処理実行プログラム２３の実行する処理フローの一例を図示し、図６及び図７に、ＬＳＩフロアプラン決定プログラム２２の実行する処理フローの一例を図示する。
【００４２】
次に、これらの処理フローに従って、本発明に関連するＬＳＩフロアプランの決定処理（以下、本発明に関連する第１のＬＳＩフロアプランの決定処理と称する）について説明する。
【００４３】
初期化処理実行プログラム２３は、起動されると、図５の処理フローに示すように、先ず最初に、ステップ１で、ブロックテーブル２０に格納される固定形状のＬＳＩブロックを処理対象として、乱数を使って、それらの固定形状ＬＳＩブロックに割り付ける回転コードの初期値を生成して、ブロックテーブル２０の対応する回転コードのエントリー域に書き込む。
【００４４】
例えば、図３に示すように、「１」という固定形状ＬＳＩブロックに対しては、「１」という回転コードの初期値を割り付け、「５」という固定形状ＬＳＩブロックに対しては、「３」という回転コードの初期値を割り付けるのである。
【００４５】
続いて、ステップ２で、ブロックテーブル２０に格納されるＬＳＩブロックのＩＤを用いて、乱数を使って、ＬＳＩフロアプランの初期解となるＰolish expressionの初期解を生成する。
【００４６】
例えば、図２２（ｂ）に示したような、
１６＋３５＊２＋７４＋＊＊
というＰolish expressionの初期解を生成するのである。
【００４７】
このようにして、初期化処理実行プログラム２３は、起動されると、ＬＳＩフロアプランの初期解となるＰolish expressionの初期解を生成するとともに、そのＰolish expressionに記述される固定形状ＬＳＩブロックに対して、それの姿勢となる回転コードの初期値を割り付けるのである。
【００４８】
この初期化処理実行プログラム２３の実行する初期化処理を受けて、ＬＳＩフロアプラン決定プログラム２２は、図６の処理フローに従って、最適なＬＳＩのフロアプランの決定する。
【００４９】
すなわち、ＬＳＩフロアプラン決定プログラム２２は、起動されると、図６の処理フローに示すように、先ず最初に、ステップ１で、ＳＡで定義される初期温度Ｔを設定する。続いて、ステップ２で、温度Ｔが規定の終了温度Ｔx よりも小さくなったのか否かを判断して、小さくなったことを判断するときには、Ｐolish expressionの最適解が求まったことに対応して、処理を終了する。
【００５０】
一方、温度Ｔが規定の終了温度Ｔx よりも大きいことを判断するときには、ステップ３に進んで、カウンタの値Ｃを０にセットする。続いて、ステップ４で、カウンタ値Ｃが規定の最大値を越えたのか否かを判断して、越えていないことを判断するときには、ステップ５に進んで、Ｐolish expressionあるいは固定形状ＬＳＩブロックに割り付けられる回転コードに対してオペレーションを施す。
【００５１】
例えば、図７の処理フローに示すように、０，１，２の値を取る乱数を発生して、その乱数値が０を取るときには、Ｐolish expressionの持つ隣接する２つのオペランド（どのオペランドを選択するのかについては別途乱数などを使って決定する）を交換し、その乱数値が１を取るときには、Ｐolish expressionの持つある部分のオペレータ（どの部分を処理するのかについては別途乱数などを使って決定する）の補集合を取り、その乱数値が２を取るときには、固定形状ＬＳＩブロック（どの固定形状ＬＳＩブロックを選択するのかについては別途乱数などを使って決定する）に割り付けられる回転コードを変更（どの値に変更するのかについては別途乱数などを使って決定する）するというオペレーションを施すのである。
【００５２】
ここで、オペランドを交換する処理や、オペレータの補集合を取る処理や、回転コードを変更する処理は、それぞれその処理を行う関数が用意されていて、それを呼び出すことで実行される。
【００５３】
また、図７の処理フローでは、オペランドを交換するか、オペレータの補集合を取るか、回転コードを変更するというオペレーションを施しているが、オペランドを交換するとともに回転コードを変更したり、オペレータの補集合を取るとともに回転コードを変更するといったようなオペレーションを施すことも可能である。
【００５４】
続いて、ステップ６で、そのステップ５での操作により変形されたＰolish expressionの規定するＬＳＩフロアプランで、固定形状ＬＳＩブロックの配置が可能であるのか否かを判断（大きさと回転コードの指定する姿勢とで判断する）して、その配置が不可能であることを判断するときには、ステップ５に戻っていくことで、Ｐolish expressionあるいは固定形状ＬＳＩブロックに割り付けられる回転コードに対して次のオペレーションを施していく。
【００５５】
すなわち、ＬＳＩブロックの面積だけを考慮する従来技術と異なって、本発明に関連する第１のＬＳＩフロアプランの決定処理では、固定形状ＬＳＩブロックに対して、その姿勢となる回転コードを割り付ける構成を採っているので、Ｐolish expressionの規定するＬＳＩフロアプランでは、固定形状ＬＳＩブロックの配置が不可能となることが起こる。これから、オペレーションを施すことでＰolish expressionを変形すると、固定形状ＬＳＩブロックの配置が可能であるのか否かを判断して、配置が不可能であると判断するときには、そのＰolish expressionについては採用せずに、ステップ５に戻って、次のＰolish expressionを生成していくように処理するのである。
【００５６】
一方、ステップ６で、固定形状ＬＳＩブロックの配置が可能であることを判断するときには、ステップ７に進んで、オペレーションを施す前のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S) と、オペレーションを施した後のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S')とを算出し、それから、評価関数値
ｅ-[Cost(S')-Cost(S)]/T 
を算出して、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）
で定義されるmin 値を決定する。
【００５７】
このコストとして、例えば、各ＬＳＩブロックの持つブロック内配線長の総和と、ＬＳＩブロック間を配線する各ネットの持つブロック間配線長の総和との合計値で定義される配線コストを用いることが可能である。
【００５８】
この各ＬＳＩブロックの持つブロック内配線長の総和として定義される配線コスト（COST１）は、例えば、
COST１＝Σhalf-perimeter-intra-block(i) ×ｐ×block-intra-net(i)
の式に従って算出する。
【００５９】
ここで、「half-perimeter-intra-block(i) 」はＬＳＩブロックｉの内部に配線される１つのネットの配線長、ｐは重み、「block-intra-net(i)」はＬＳＩブロックｉの内部に配線されるネットの本数（ブロックテーブル２０に登録されるブロック内ネット本数）である。
【００６０】
「half-perimeter-intra-block(i) 」は、例えば、図８（ａ）に示すように、Ｐolish expressionの規定するＬＳＩフロアプランで配置されるＬＳＩブロックｉの持つ縦の長さと横の長さとの合計値で算出する。言うまでもなく、固定形状ＬＳＩブロックについては、ブロックテーブル２０に登録される縦の長さと横の長さとの合計値となる。
【００６１】
一方、ＬＳＩブロック間を配線する各ネットの持つブロック間配線長の総和として定義される配線コスト（COST２）は、例えば、
COST２＝Σhalf-perimeter-inter-block(j) 
の式に従って算出する。
【００６２】
ここで、「half-perimeter-inter-block(j) 」はネットｊの配線長であって、例えば、図８（ｂ）に示すように、ネットｊと接続されているＬＳＩブロックの中心を完全に含む四角形の持つ縦の長さと横の長さとの合計値で算出する。このとき、ネットｊが固定形状ＬＳＩブロックの端子と接続される場合には、ＬＳＩブロックの中心に代えて、その実際の端子位置を使って上記の四角形を決定していくことが好ましい。なお、各ネットがどのＬＳＩブロックと接続されているのかについては、ネットリストテーブル２１を参照することで入手する。
【００６３】
更に、配線コストとして、上述した配線コスト（COST１）と配線コスト（COST２）との合計値に加えて、「half-perimeter-inter-block(j) 」で求めたネットｊの配線長がユーザの指定する「net-length(j) 」を越えていたら１、越えていなかったら０を割り当てることで定義されるペナルティ値の総和
COST３＝Σlength-violation(j) ×ｑ
但し、ｑは重み
を加えることも可能である。
【００６４】
すなわち、ユーザと対話することで、図９に示すような「net-length(j) 」を管理するネットテーブルを作成して、「half-perimeter-inter-block(j) 」で求めたネットｊの配線長がこの「net-length(j) 」を越えていたら１、越えていなかったら０を割り当てることで定義されるペナルティ値の総和を配線コストに加えることも可能である。
【００６５】
このペナルティ値の総和として定義される配線コスト（COST３）を用いると、タイミングがクリティカルなネットが、指定された配線長に入る場合に高いコストが与えられることで、できるだけ指定された配線長に入るようにと、ＬＳＩのフロアプランの最適化が制御されることになる。
【００６６】
ここで、ブロック内配線長の総和で定義される配線コスト（COST１）と、ブロック間配線長の総和で定義される配線コスト（COST２）と、ペナルティ値の総和として定義される配線コスト（COST３）との合計値を最終的な配線コストとして用いるではなくて、ペナルティ値の総和として定義される配線コスト（COST３）のみを最終的な配線コストとして用いることも可能である。
【００６７】
図６の処理フローの説明に戻るならば、ステップ７で、オペレーションを施す前のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S) と、オペレーションを施した後のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S')とを算出し、それから、評価関数値
ｅ-[Cost(S')-Cost(S)]/T 
を算出して、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）                        で定義されるmin 値を決定すると、続いて、ステップ８で、０〜１の間に入る乱数値を発生する。
【００６８】
続いて、ステップ９で、その発生した乱数値がステップ７で決定したmin 値よりも小さいのか否かを判断して、小さいことを判断するときには、ステップ１０に進んで、オペレーションを施した後のＰolish expression（回転コード）を新たなＰolish expression（回転コード）とすることで、Ｐolish expression（回転コード）を変更し、一方、大きいことを判断するときには、ステップ１０の処理を行うことなく、オペレーションを施す前のＰolish expression（回転コード）を有効とすることで、Ｐolish expression（回転コード）を変更しないように処理する。
【００６９】
続いて、ステップ１１で、カウンタ値Ｃの値を１つインクリメントしてから、ステップ４に戻っていく。
【００７０】
ステップ４ないしステップ１１の処理を繰り返していくことで、設定される温度ＴでＰolish expressionの変更を繰り返していくときに、ステップ４で、その繰り返し処理を所定の回数分行ったことを判断すると、ステップ１２に進んで、温度Ｔを所定の温度だけ低くして、ステップ２に戻っていくことで、前回よりも低い温度で、Ｐolish expressionの変更を繰り返していく。
【００７１】
そして、この繰り返し処理を実行していくときに、ステップ２で、温度Ｔが規定の終了温度Ｔx よりも小さくなったことを判断するときには、Ｐolish expressionの最適解が求まったことを判断して、処理を終了する。
【００７２】
このようにして、ＬＳＩフロアプラン決定プログラム２２は、本発明に関連する第１のＬＳＩフロアプランの決定処理を実現する場合には、固定形状のＬＳＩブロックについては、その固定形状がくずれないように制御しつつ、その配置の姿勢も制御しながら、ＳＡの最適化アルゴリズムに従って、ＬＳＩフロアプランを決定するように処理するのである。
【００７３】
次に、本発明に関連するＬＳＩフロアプランの他の決定処理（以下、本発明に関連する第２のＬＳＩフロアプランの決定処理と称する）について説明する。
【００７４】
本発明に関連する第２のＬＳＩフロアプランの決定処理では、図１０に示すように、固定形状ＬＳＩブロック（図中の「１」と「５」）を、固定形状を持たないいずれかのＬＳＩブロックに内包させつつ、その親となるＬＳＩブロックについても操作対象としながらＳＡを実行することで、ＬＳＩのフロアプランを決定するように処理する。
【００７５】
本発明に関連する第２のＬＳＩフロアプランの決定処理では、固定形状ＬＳＩブロックは、決定されたＬＳＩフロアプランの中で、必ずしもその形状が保証される訳ではないが、固定形状を持たないいずれかのＬＳＩブロックとマージされることになるので、そのマージされた大きな面積の中でその形状が保証される可能性は高く、従って、有効なＬＳＩのフロアプランを決定できる可能性は極めて高い。
【００７６】
図１１に、本発明に関連する第２のＬＳＩフロアプランの決定処理で用いられるブロックテーブル２のテーブルデータの一例を図示する。
【００７７】
この図１１に示すブロックテーブル２０は、ＬＳＩフロアプラン決定プログラム２２の処理対象となるＬＳＩブロックのＩＤに対応付けて、そのＬＳＩブロックの面積と、そのＬＳＩブロック内に配線されるネット数と、そのＬＳＩブロックが固定形状であるのか否か示すフラグ（固定形状フラグ）と、固定形状のＬＳＩブロックについてはそれが所属する親ＬＳＩブロックのＩＤとを管理する。
【００７８】
図１２に、本発明に関連する第２のＬＳＩフロアプランの決定処理を実現する初期化処理実行プログラム２３の実行する処理フローの一例を図示し、図１３及び図１４に、この決定処理を実現するＬＳＩフロアプラン決定プログラム２２の実行する処理フローの一例を図示する。
【００７９】
次に、これらの処理フローに従って、本発明に関連する第２のＬＳＩフロアプランの決定処理について説明する。
【００８０】
初期化処理実行プログラム２３は、起動されると、図１２の処理フローに示すように、先ず最初に、ステップ１で、ブロックテーブル２０に格納される固定形状のＬＳＩブロックを処理対象として、乱数を使って、それらの固定形状ＬＳＩブロックに割り付ける親ＬＳＩブロックのＩＤの初期値（重複しないようにすることが好ましい）を生成して、ブロックテーブル２０の対応する親ＬＳＩブロックＩＤのエントリー域に書き込む。
【００８１】
例えば、図１１に示すように、「１」という固定形状ＬＳＩブロックに対しては、「６」という親ＬＳＩブロックＩＤの初期値を割り付け、「５」という固定形状ＬＳＩブロックに対しては、「３」という親ＬＳＩブロックＩＤの初期値を割り付けるのである。
【００８２】
続いて、ステップ２で、固定形状ＬＳＩブロックを処理対象から外しつつ、ブロックテーブル２０に格納されるＬＳＩブロックのＩＤを用いて、乱数を使って、ＬＳＩフロアプランの初期解となるＰolish expressionの初期解を生成する。例えば、図１０に示したＬＳＩフロアプランを規定する
６３２＋＊７４＋＊
というＰolish expressionの初期解を生成するのである。
【００８３】
このとき、「６」というＬＳＩブロックの面積は、「６」というＬＳＩブロック自身の面積と、その配下となる「１」という固定形状ＬＳＩブロックの面積との合計値となる。また、「３」というＬＳＩブロックの面積は、「３」というＬＳＩブロック自身の面積と、その配下となる「５」という固定形状ＬＳＩブロックの面積の合計値となる。
【００８４】
更に、「６」というＬＳＩブロックの持つブロック内ネット本数は、「６」というＬＳＩブロック自身の持つブロック内ネット本数と、その配下となる「１」という固定形状ＬＳＩブロックの持つブロック内ネット本数と、「６」と「１」という固定形状ＬＳＩブロックとの間を接続するネット本数との合計値となる。また、「３」というＬＳＩブロックの持つブロック内ネット本数は、「３」というＬＳＩブロック自身の持つブロック内ネット本数と、その配下となる「５」という固定形状ＬＳＩブロックの持つブロック内ネット本数と、「３」と「５」という固定形状ＬＳＩブロックとの間を接続するネット本数との合計値となる。
【００８５】
このようにして、初期化処理実行プログラム２３は、起動されると、固定形状ＬＳＩブロックに対して、それを包含する親ＬＳＩブロックのＩＤを割り付けるとともに、それらの固定形状ＬＳＩブロックを処理対象から外しつつ、ＬＳＩフロアプランの初期解となるＰolish expressionの初期解を生成するのである。
【００８６】
この初期化処理実行プログラム２３の実行する初期化処理を受けて、ＬＳＩフロアプラン決定プログラム２２は、図１３の処理フローに従って、最適なＬＳＩフロアプランの決定する。
【００８７】
すなわち、ＬＳＩフロアプラン決定プログラム２２は、起動されると、図１３の処理フローに示すように、先ず最初に、ステップ１で、ＳＡで定義される初期温度Ｔを設定する。続いて、ステップ２で、温度Ｔが規定の終了温度Ｔx よりも小さくなったのか否かを判断して、小さくなったことを判断するときには、Ｐolish expressionの最適解が求まったことに対応して、処理を終了する。
【００８８】
一方、温度Ｔが規定の終了温度Ｔx よりも大きいことを判断するときには、ステップ３に進んで、カウンタの値Ｃを０にセットする。続いて、ステップ４で、カウンタ値Ｃが規定の最大値を越えたのか否かを判断して、越えていないことを判断するときには、ステップ５に進んで、Ｐolish expressionあるいは固定形状ＬＳＩブロックが所属する親ＬＳＩブロックのＩＤに対してオペレーションを施す。
【００８９】
例えば、図１４の処理フローに示すように、０，１，２の値を取る乱数を発生して、その乱数値が０を取るときには、Ｐolish expressionの持つ隣接する２つのオペランド（どのオペランドを選択するのかについては別途乱数などを使って決定する）を交換し、その乱数値が１を取るときには、Ｐolish expressionの持つある部分のオペレータ（どの部分を処理するのかについては別途乱数などを使って決定する）の補集合を取り、その乱数値が２を取るときには、固定形状ＬＳＩブロック（どの固定形状ＬＳＩブロックを選択するのかについては別途乱数などを使って決定する）に割り付けられる親ＬＳＩブロックのＩＤ（どの値に変更するのかについては別途乱数などを使って決定する）を変更するというオペレーションを施すのである。
【００９０】
ここで、親ＬＳＩブロックのＩＤが変更されるときには、それまで親であったＬＳＩブロックの面積／ブロック内ネット本数と、新たに親となったＬＳＩブロックの面積／ブロック内ネット本数とが変更されることになる。
【００９１】
また、オペランドを交換する処理や、オペレータの補集合を取る処理や、親ＬＳＩブロックのＩＤを変更する処理は、それぞれその処理を行う関数が用意されていて、それを呼び出すことで実行される。
【００９２】
また、図１４の処理フローでは、オペランドを交換するか、オペレータの補集合を取るか、親ＬＳＩブロックのＩＤを変更するというオペレーションを施しているが、オペランドを交換するとともに親ＬＳＩブロックのＩＤを変更したり、オペレータの補集合を取るとともに親ＬＳＩブロックのＩＤを変更するといったようなオペレーションを施すことも可能である。
【００９３】
続いて、ステップ６で、オペレーションを施す前のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S) と、オペレーションを施した後のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S')とを算出し、それから、評価関数値
ｅ-[Cost(S')-Cost(S)]/T 
を算出して、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）
で定義されるmin 値を決定する。
【００９４】
ここで、このとき用いるコストとしては、例えば、上述したように、ＬＳＩブロック内配線長の総和で定義される配線コスト（COST１）と、ＬＳＩブロック間配線長の総和で定義される配線コスト（COST２）との合計値を用いる。
【００９５】
続いて、ステップ７で、０〜１の間に入る乱数値を発生し、続くステップ８で、その発生した乱数値が決定したmin 値よりも小さいのか否かを判断する。
【００９６】
この判断処理により、発生した乱数値が決定したmin 値よりも小さいことを判断するときには、ステップ９に進んで、オペレーションを施した後のＰolish expression（親ＬＳＩブロックＩＤ）を新たなＰolish expression（親ＬＳＩブロックＩＤ）とすることで、Ｐolish expression（親ＬＳＩブロックＩＤ）を変更し、一方、大きいことを判断するときには、ステップ９の処理を行うことなく、オペレーションを施す前のＰolish expression（親ＬＳＩブロックＩＤ）を有効とすることで、Ｐolish expression（親ＬＳＩブロックＩＤ）を変更しないように処理する。
【００９７】
続いて、ステップ１０で、カウンタ値Ｃの値を１つインクリメントしてから、ステップ４に戻っていく。
【００９８】
ステップ４ないしステップ１０の処理を繰り返していくことで、設定される温度ＴでＰolish expressionの変更を繰り返していくときに、ステップ４で、その繰り返し処理を所定の回数分行ったことを判断すると、ステップ１１に進んで、温度Ｔを所定の温度だけ低くして、ステップ２に戻っていくことで、前回よりも低い温度で、Ｐolish expressionの変更を繰り返していく。
【００９９】
そして、この繰り返し処理を実行していくときに、ステップ２で、温度Ｔが規定の終了温度Ｔx よりも小さくなったことを判断するときには、Ｐolish expressionの最適解が求まったことを判断して、処理を終了する。
【０１００】
このようにして、ＬＳＩフロアプラン決定プログラム２２は、本発明に関連する第２のＬＳＩフロアプランの決定処理を実現する場合には、固定形状のＬＳＩブロックについては、固定形状を持たないＬＳＩブロックにマージするように制御しつつ、ＳＡの最適化アルゴリズムに従ってＬＳＩフロアプランを決定するように処理するのである。
【０１０１】
次に、本発明の一実施形態例について説明する。
【０１０２】
本実施形態例では、図１５に示すように、ＳＡを実行するにあたって、固定形状ＬＳＩブロックの固定形状を考慮しない形でＬＳＩのフロアプランを決定し、そのフロアプランのコストを算出するときに、固定形状ＬＳＩブロックがパッキングできることになるようにとカットラインをブレークして、その状態でコストを算出していくように処理している。
【０１０３】
これにより、本実施形態例に従うと、固定形状ＬＳＩブロックがその固定形状を保持したままパッキングされることに対して高いコストが与えられることで、固定形状ＬＳＩブロックができる限りその固定形状を保持したまま配置されることになるようにと、ＬＳＩのフロアプランの最適化が制御されることになる。
【０１０４】
図１６に、本実施形態例で用いられるブロックテーブル２のテーブルデータの一例を図示する。
【０１０５】
この図１６に示すブロックテーブル２０は、ＬＳＩフロアプラン決定プログラム２２の処理対象となるＬＳＩブロックのＩＤに対応付けて、そのＬＳＩブロックの面積と、そのＬＳＩブロック内に配線されるネット数と、そのＬＳＩブロックが固定形状であるのか否か示すフラグ（固定形状フラグ）と、固定形状のＬＳＩブロックについてはその大きさ（ｘ，ｙ）と、固定形状のＬＳＩブロックについてはその姿勢となる回転コードと、固定形状のＬＳＩブロックについてはパッキング優先順位と、固定形状のＬＳＩブロックについてはパッキング優先方向とを管理する。
【０１０６】
このパッキング優先順位は、どういう順番に従って、固定形状ＬＳＩブロックのパッキングを実行していくのかを規定している。図１６の例で説明するならば、先ず最初に、「１」という固定形状ＬＳＩブロックについてパッキングを行い、次に、「５」という固定形状ＬＳＩブロックについてパッキングを行うことになる。
【０１０７】
一方、このパッキング優先方向は、どういう方向を優先してパッキングを実行していくのかを規定している。図１６の例で説明するならば、「１」という固定形状ＬＳＩブロックについては、「ＵＬＲＤ（上方向→左方向→右方向→下方向）」という順に方向を優先させてパッキングを行い、「５」という固定形状ＬＳＩブロックについては、「ＤＬＲＵ（下方向→左方向→右方向→上方向）」という順に方向を優先させてパッキングを行うことになる。
【０１０８】
図１７に、本実施形態例を実現する初期化処理実行プログラム２３の実行する処理フローの一例を図示し、図１８ないし図２０に、本実施形態例を実現するＬＳＩフロアプラン決定プログラム２２の実行する処理フローの一例を図示する。
【０１０９】
次に、これらの処理フローに従って、本実施形態例によるＬＳＩフロアプランの決定処理について詳細に説明する。
【０１１０】
初期化処理実行プログラム２３は、起動されると、図１７の処理フローに示すように、先ず最初に、ステップ１で、ブロックテーブル２０に格納される固定形状のＬＳＩブロックを処理対象として、乱数を使って、それらの固定形状ＬＳＩブロックに割り付ける回転コードの初期値を生成して、ブロックテーブル２０の対応する回転コードのエントリー域に書き込む。
【０１１１】
例えば、図１６に示すように、「１」という固定形状ＬＳＩブロックに対しては、「１」という回転コードの初期値を割り付け、「５」という固定形状ＬＳＩブロックに対しては、「３」という回転コードの初期値を割り付けるのである。
【０１１２】
続いて、ステップ２で、ブロックテーブル２０に格納される固定形状のＬＳＩブロックを処理対象として、乱数を使って、それらの固定形状ＬＳＩブロックに割り付けるパッキング優先順位の初期値を生成して、ブロックテーブル２０の対応するパッキング優先順位のエントリー域に書き込む。
【０１１３】
例えば、図１６に示すように、「１」という固定形状ＬＳＩブロックに対しては、第１順位というパッキング優先順位の初期値を割り付け、「５」という固定形状ＬＳＩブロックに対しては、第２順位というパッキング優先順位の初期値を割り付けるのである。
【０１１４】
続いて、ステップ３で、ブロックテーブル２０に格納される固定形状のＬＳＩブロックを処理対象として、乱数を使って、それらの固定形状ＬＳＩブロックに割り付けるパッキング優先方向の初期値を生成して、ブロックテーブル２０の対応するパッキング優先方向のエントリー域に書き込む。
【０１１５】
例えば、図１６に示すように、「１」という固定形状ＬＳＩブロックに対しては、「ＵＬＲＤ」というパッキング優先方向の初期値を割り付け、「５」という固定形状ＬＳＩブロックに対しては、「ＤＬＲＵ」というパッキング優先方向の初期値を割り付けるのである。
【０１１６】
続いて、ステップ４で、ブロックテーブル２０に格納されるＬＳＩブロックのＩＤを用いて、乱数を使って、ＬＳＩフロアプランの初期解となるＰolish expressionの初期解を生成する。
【０１１７】
例えば、図２２（ｂ）に示したような、
１６＋３５＊２＋７４＋＊＊
というＰolish expressionの初期解を生成するのである。
【０１１８】
このようにして、初期化処理実行プログラム２３は、起動されると、ＬＳＩフロアプランの初期解となるＰolish expressionの初期解を生成するとともに、そのＰolish expressionに記述される固定形状ＬＳＩブロックに対して、回転コード／パッキング優先順位／パッキング優先方向の初期値を割り付けるのである。
【０１１９】
この初期化処理実行プログラム２３の実行する初期化処理を受けて、ＬＳＩフロアプラン決定プログラム２２は、図１８の処理フローに従って、最適なＬＳＩのフロアプランを決定する。
【０１２０】
すなわち、ＬＳＩフロアプラン決定プログラム２２は、起動されると、図１８の処理フローに示すように、先ず最初に、ステップ１で、ＳＡで定義される初期温度Ｔを設定する。続いて、ステップ２で、温度Ｔが規定の終了温度Ｔx よりも小さくなったのか否かを判断して、小さくなったことを判断するときには、Ｐolish expressionの最適解が求まったことに対応して、処理を終了する。
【０１２１】
一方、温度Ｔが規定の終了温度Ｔx よりも大きいことを判断するときには、ステップ３に進んで、カウンタの値Ｃを０にセットする。続いて、ステップ４で、カウンタ値Ｃが規定の最大値を越えたのか否かを判断して、越えていないことを判断するときには、ステップ５に進んで、Ｐolish expressionあるいは固定形状ＬＳＩブロックに割り付けられる回転コードやパッキング優先順位やパッキング優先方向に対してオペレーションを施す。
【０１２２】
例えば、図１９の処理フローに示すように、０，１，２，３，４の値を取る乱数を発生して、その乱数値が０を取るときには、Ｐolish expressionの持つ隣接する２つのオペランド（どのオペランドを選択するのかについては別途乱数などを使って決定する）を交換し、その乱数値が１を取るときには、Ｐolish expressionの持つある部分のオペレータ（どの部分を処理するのかについては別途乱数などを使って決定する）の補集合を取り、その乱数値が２を取るときには、固定形状ＬＳＩブロック（どの固定形状ＬＳＩブロックを選択するのかについては別途乱数などを使って決定する）に割り付けられる回転コードを変更（どの値に変更するのかについては別途乱数などを使って決定する）し、その乱数値が３を取るときには、固定形状ＬＳＩブロック（どの固定形状ＬＳＩブロックを選択するのかについては別途乱数などを使って決定する）に割り付けられるパッキング優先順位を変更（どの値に変更するのかについては別途乱数などを使って決定する）し、その乱数値が４を取るときには、固定形状ＬＳＩブロック（どの固定形状ＬＳＩブロックを選択するのかについては別途乱数などを使って決定する）に割り付けられるパッキング優先方向を変更（どの値に変更するのかについては別途乱数などを使って決定する）するというオペレーションを施すのである。
【０１２３】
ここで、オペランドを交換する処理や、オペレータの補集合を取る処理や、回転コードを変更する処理や、パッキング優先順位を変更する処理や、パッキング優先方向を変更する処理は、それぞれその処理を行う関数が用意されていて、それを呼び出すことで実行される。
【０１２４】
また、図１９の処理フローでは、オペランドを交換するか、オペレータの補集合を取るか、回転コードを変更するか、パッキング優先順位を変更するか、パッキング優先方向を変更するというオペレーションを施しているが、これらのオペレーションを組み合わせたものを施すことも可能である。
【０１２５】
続いて、ステップ６で、オペレーションを施す前のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S) と、オペレーションを施した後のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S')とを算出し、それから、評価関数値
ｅ-[Cost(S')-Cost(S)]/T 
を算出して、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）
で定義されるmin 値を決定する。
【０１２６】
ここで、このとき用いるコストとしては、例えば、上述したように、ＬＳＩブロック内配線長の総和で定義される配線コスト（COST１）と、ＬＳＩブロック間配線長の総和で定義される配線コスト（COST２）との合計値を用いる。
【０１２７】
このコストの算出にあたって、固定形状ＬＳＩブロックについては、オペレーションを施した後のＰolish expressionの規定する領域にパッキングできるのか否かを判定して、パッキングできないときにはＬＳＩブロックを区切るカットラインをブレークさせることでそのパッキングを実現して、その状態でコストを算出していくように処理する。
【０１２８】
すなわち、ステップ５で、Ｐolish expressionにオペレーションを施した後、ステップ６に進むと、図２０の処理フローに示すように、先ず最初に、ステップ６０で、全ての固定形状ＬＳＩブロックを選択したのか否かを判断して、全ての固定形状ＬＳＩブロックを選択していないことを判断するときには、ステップ６１に進んで、割り付けられるパッキング優先順位に従って、未選択の固定形状ＬＳＩブロックの中から優先順位の最も高いものを１つ選択する。
【０１２９】
続いて、ステップ６２で、その選択した固定形状ＬＳＩブロックに割り付けられる回転コード及びパッキング優先方向に従って、オペレーションの施したＰolish expressionの規定する領域に、その選択した固定形状ＬＳＩブロックをパッキングすることを試みる。
【０１３０】
続いて、ステップ６３で、そのパッキング処理により固定形状ＬＳＩブロックがパッキングできたのか否かを判断して、パッキングできないことを判断するときには、ステップ６４に進んで、パッキングができるまで、未ブレーク（break)のカットライン（ＬＳＩブロックを区画するライン）の内の最下位レベルのものをブレークさせていく。
【０１３１】
例えば、図１５に示す例で説明するならば、「１」という固定形状ＬＳＩブロックがＰolish expressionの規定する領域にパッキングできないときには、「６」という非固定形状のＬＳＩブロックとの間を区切るカットライン1)をブレークさせていくことで、「１」という固定形状ＬＳＩブロックのパッキングを実現するのである。また、「５」という固定形状ＬＳＩブロックがＰolish expressionの規定する領域にパッキングできないときには、「３」という非固定形状のＬＳＩブロックとの間を区切るカットライン2)をブレークさせていくことで、「５」という固定形状ＬＳＩブロックのパッキングを実現するのである。
【０１３２】
ここで、最下位レベルのカットラインからブレークさせていくのは、Ｐolish expressionの規定するＬＳＩフロアプランの配置形態をできる限り崩さないようにすることに、その理由がある。
【０１３３】
そして、ステップ６４の処理を終了すると、ステップ６０に戻る。また、ステップ６３でパッキングできたことを判断するときには、ステップ６４の処理を行うことなく、そのままステップ６０に戻る。
【０１３４】
一方、ステップ６０で、全ての固定形状ＬＳＩブロックを選択したことを判断すると、ステップ６５に進んで、オペレーションを施す前のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S) と、オペレーションを施した後のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S')とを算出する。
【０１３５】
そして、この後、図１８の処理フローのステップ６では、上述したように、評価関数値
ｅ-[Cost(S')-Cost(S)]/T 
を算出して、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）
で定義されるmin 値を決定する処理を行う。
【０１３６】
ここで、図１５の下段に示す図から分かるように、カットラインをブレークさせると、そのブレークさせたカットラインにより区切られるＬＳＩブロックの形状が四角形でなくなることになるので、その非四角形のＬＳＩブロックについては、例えば適当なアルゴリズムに従って四角形に変形することで、上述した配線コストのCOST１，２を求めたり、例えば非四角形の重心を求めて、その重心を上述した四角形の中心の代わりに用いることで、上述した配線コストのCOST２を求めることなどにより、配線コストを算出していくように処理することになる。
【０１３７】
図１８の処理フローの説明に戻るならば、ステップ６で、オペレーションを施す前のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S) と、オペレーションを施した後のＰolish expressionの規定するＬＳＩフロアプランのコストCost(S')とを算出し、それから、評価関数値
ｅ-[Cost(S')-Cost(S)]/T 
を算出して、
ｍｉｎ（１，ｅ-[Cost(S')-Cost(S)]/T ）
で定義されるmin 値を決定すると、続いて、ステップ７で、０〜１の間に入る乱数値を発生する。
【０１３８】
続いて、ステップ８で、その発生した乱数値がステップ６で決定したmin 値よりも小さいのか否かを判断して、小さいことを判断するときには、ステップ９に進んで、オペレーションを施した後のＰolish expression（回転コード／パッキング優先順位／パッキング優先方向）を新たなＰolish expression（回転コード／パッキング優先順位／パッキング優先方向）とすることで、Ｐolish expression（回転コード／パッキング優先順位／パッキング優先方向）を変更し、一方、大きいことを判断するときには、ステップ１０の処理を行うことなく、オペレーションを施す前のＰolish expression（回転コード／パッキング優先順位／パッキング優先方向）を有効とすることで、Ｐolish expression（回転コード／パッキング優先順位／パッキング優先方向）を変更しないように処理する。
【０１３９】
続いて、ステップ１０で、カウンタ値Ｃの値を１つインクリメントしてから、ステップ４に戻っていく。
【０１４０】
ステップ４ないしステップ１０の処理を繰り返していくことで、設定される温度ＴでＰolish expressionの変更を繰り返していくときに、ステップ４で、その繰り返し処理を所定の回数分行ったことを判断すると、ステップ１１に進んで、温度Ｔを所定の温度だけ低くして、ステップ２に戻っていくことで、前回よりも低い温度で、Ｐolish expressionの変更を繰り返していく。
【０１４１】
そして、この繰り返し処理を実行していくときに、ステップ２で、温度Ｔが規定の終了温度Ｔx よりも小さくなったことを判断するときには、Ｐolish expressionの最適解が求まったことを判断して、処理を終了する。
【０１４２】
このようにして、ＬＳＩフロアプラン決定プログラム２２は、本実施形態例によるＬＳＩフロアプランの決定処理を実現する場合には、ＳＡを実行するにあたって、固定形状ＬＳＩブロックの固定形状を考慮しない形でＬＳＩのフロアプランを決定して、そのフロアプランのコストを算出するときに、固定形状ＬＳＩブロックがパッキングできることになるようにとカットラインをブレークさせて、その状態でコストを算出していく。
【０１４３】
これにより、本実施形態例に従うと、固定形状ＬＳＩブロックがその固定形状を保持したままパッキングされることに対して高いコストが与えられることで、固定形状ＬＳＩブロックができる限りその固定形状を保持したまま配置されることになるようにと、ＬＳＩのフロアプランの最適化が制御されることになる。
【０１４４】
この処理を実行していくあたって、ＬＳＩフロアプラン決定プログラム２２は、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックに対して重点的にオペレーションを施していくことで、固定形状ＬＳＩブロックができる限りその固定形状を保持したまま配置されることになるようにと制御する構成を採ることがある。
【０１４５】
この構成を採る場合には、例えば、図２１に示すように、第１回目として、０，１，２，３，４，５の値を取る乱数を発生して、その乱数値が０を取るときには、Ｐolish expressionの持つ隣接する２つのオペランドを交換するというオペレーションを施し、その乱数値が１を取るときには、Ｐolish expressionの持つある部分のオペレータの補集合を取るというオペレーションを施し、その乱数値が２を取るときには、固定形状ＬＳＩブロックに割り付けられる回転コードを変更するというオペレーションを施し、その乱数値が３を取るときには、固定形状ＬＳＩブロックに割り付けられるパッキング優先順位を変更するというオペレーションを施し、その乱数値が４を取るときには、固定形状ＬＳＩブロックに割り付けられるパッキング優先方向を変更するというオペレーションを施すとともに、その乱数値が５を取るときには、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックを処理対象として設定する処理を行う。
【０１４６】
そして、第１回目の乱数発生で、乱数値５が発生した場合には、続いて、第２回目として、０，１，２，３，４の値を取る乱数を発生して、その乱数値が０を取るときには、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックを処理対象として、Ｐolish expressionの持つ隣接する２つのオペランドを交換するというオペレーションを施し、その乱数値が１を取るときには、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックを処理対象として、Ｐolish expressionの持つある部分のオペレータの補集合を取るというオペレーションを施し、その乱数値が２を取るときには、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックを処理対象として、固定形状ＬＳＩブロックに割り付けられる回転コードを変更するというオペレーションを施し、その乱数値が３を取るときには、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックを処理対象として、固定形状ＬＳＩブロックに割り付けられるパッキング優先順位を変更するというオペレーションを施し、その乱数値が４を取るときには、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックを処理対象として、固定形状ＬＳＩブロックに割り付けられるパッキング優先方向を変更するというオペレーションを施す処理を行う。
【０１４７】
この第１回目に発生する乱数によりオペレーションの施されるＬＳＩブロックは、ブレークさせたカットラインよりも上位のツリーレベルに位置するＬＳＩブロックと、下位のツリーレベルに位置するＬＳＩブロックとの両方であるのに対して、この第２回目に発生する乱数によりオペレーションの施されるＬＳＩブロックは、ブレークさせたカットラインよりも下位のツリーレベルに位置するＬＳＩブロックのみである。
【０１４８】
これにより、ＬＳＩフロアプラン決定プログラム２２は、ブレークさせたカットラインよりも下位のツリーレベルのＬＳＩブロックに対して重点的にオペレーションを施していくことができるようになる。
【０１４９】
図示実施形態例に従って本発明を説明したが、これに限定されるものではない。例えば、実施形態例では、最適化のアルゴリズムとしてＳＡを用いる構成を採ったが、本発明は、その他の最適化アルゴリズムを用いる場合にも、そのまま適用できる。
【０１５０】
また、実施形態例では、Ｐolish expressionの初期解を自動生成する構成を採ったが、ユーザにより作成されたＰolish expressionの初期解を入力していくようにする構成を採ってもよい。
【０１５１】
次に、本発明および本発明に関連する発明により実現される効果について記載する。
【０１５２】
以上説明したように、本発明および本発明に関連する発明によれば、固定形状を持つＬＳＩブロックについては、その固定形状がくずれない形態で、ＬＳＩのフロアプランを決定できるようになる。
【０１５３】
これにより、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようになる。
【０１５４】
そして、本発明および本発明に関連する発明によれば、固定形状を持つＬＳＩブロックについては、固定形状を持たないＬＳＩブロックにマージする形態で、ＬＳＩのフロアプランを決定できるようになる。
【０１５５】
これにより、固定形状を持つＬＳＩブロックは、固定形状を持たないＬＳＩブロックとマージされることになることで、その固定形状を保持できる可能性が高くなり、従って、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようになる。
【０１５６】
そして、本発明および本発明に関連する発明によれば、固定形状を持つＬＳＩブロックがその固定形状を保持したまま配置されることに対して高いコストが与えられる形態で、ＬＳＩのフロアプランを決定できるようになる。
【０１５７】
これにより、固定形状を持つＬＳＩブロックについても、その配置位置を指定できるようになるＬＳＩのフロアプランを決定できるようになる。
【０１５８】
そして、本発明および本発明に関連する発明によれば、固定形状を持つＬＳＩブロックの配置位置を指定できるようにするＬＳＩのフロアプランを決定するときにあって、配線長がなるべく短くなる形態で、そのフロアプランを決定できるようになる。
【０１５９】
そして、本発明および本発明に関連する発明によれば、固定形状を持つＬＳＩブロックの配置位置を指定できるようにするＬＳＩのフロアプランを決定するときにあって、タイミングがクリティカルな配線については、その配線が指定された配線長に入る形態で、そのフロアプランを決定できるようになる。
【図面の簡単な説明】
【０１６０】
【図１】本発明の原理構成図である。
【図２】本発明の一実施形態例である。
【図３】ブロックテーブルの一例である。
【図４】ネットリストテーブルの一例である。
【図５】初期化処理実行プログラムの処理フローである。
【図６】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図７】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図８】コスト計算の説明図である。
【図９】ネットテーブルの説明図である。
【図１０】本発明に関連する発明の説明図である。
【図１１】ブロックテーブルの一例である。
【図１２】初期化処理実行プログラムの処理フローである。
【図１３】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図１４】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図１５】本発明の実施形態例の説明図である。
【図１６】ブロックテーブルの一例である。
【図１７】初期化処理実行プログラムの処理フローである。
【図１８】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図１９】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図２０】ＬＳＩフロアプラン決定プログラムの処理フローである。
【図２１】本発明の他の実施形態例の説明図である。
【図２２】Ｐolish expressionの説明図である。
【図２３】Ｓimulated  Ａnnealingの説明図である。
【符号の説明】
【０１６１】
１    ＬＳＩフロアプラン決定装置
１０  ブロック情報管理手段
１１  ネットリスト管理手段
１２  実行手段
１３  割付手段
１４  決定手段
【図１】
2007193832.tif 000003
【図２】
2007193832.tif 000004
【図３】
2007193832.tif 000005
【図４】
2007193832.tif 000006
【図５】
2007193832.tif 000007
【図６】
2007193832.tif 000008
【図７】
2007193832.tif 000009
【図８】
2007193832.tif 000010
【図９】
2007193832.tif 000011
【図１０】
2007193832.tif 000012
【図１１】
2007193832.tif 000013
【図１２】
2007193832.tif 000014
【図１３】
2007193832.tif 000015
【図１４】
2007193832.tif 000016
【図１５】
2007193832.tif 000017
【図１６】
2007193832.tif 000018
【図１７】
2007193832.tif 000019
【図１８】
2007193832.tif 000020
【図１９】
2007193832.tif 000021
【図２０】
2007193832.tif 000022
【図２１】
2007193832.tif 000023
【図２２】
2007193832.tif 000024
【図２３】
2007193832.tif 000025