JP3556260B2 - LSI element arrangement method and apparatus - Google Patents

Description

１つの解候補は、前記配置対象の部分回路に含まれる１９個の素子にそれぞれ対応する１９個のｙ座標の候補値を有し、この数列の左側からＲ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３、Ｒ４、Ｑ３、Ｒ５、…というように対応している。セミコロンは、単にブランチの区切りを説明するために便宜上付した記号であり、解候補に含まれる文字データではない。
【００５８】
この場合において、ｙ座標の生成は、素子の配置可能領域６０の他に、各素子の種類、サイズ或いはデザインルール等を考慮した許容範囲以内で発生されたランダム値より実施されるようにしてもよい。
【００５９】
上記のようにして、初回における解候補群の生成が行われる。次に、初回以降の動作を説明する。
部分回路データ抽出部２０は、配置対象の部分回路をブランチｎ個分だけ右に移動して得られる新たな配置対象の部分回路に含まれる素子のデータを初期解候補群生成部３１に与える。初期解候補群生成部３１は、所定数の解候補からなる集合を初期世代の解候補群とする。
【００６０】
この場合において、初期解候補群生成部３１は、初回の動作のように関連するすべての素子に関してランダムに解候補群を生成するのではなく、現在対象としている配置対象の部分回路と前回対象とした配置対象の部分回路の間で重畳している（ｍ−ｎ）個のブランチに属する素子のｙ座標は、前回の自動素子配置ステップＡ５の最終回目で得られた解候補群におけるｙ座標の値をそのまま継承することによって解候補群を生成する。この値の継承は、同一番号を有する新旧の解候補の間で行われる。新しく追加されたｎ個のブランチの部分については、初回の動作と同様の手法でｙ座標の値を生成する。
【００６１】
以下、図２を用いて初期解候補群生成部３１の２回目以降の初期解候補群生成の動作を具体的に説明する。
２回目の配置対象の部分回路の初期解候補群を生成する場合、自動配置の対象となるのは第３ブランチＢ３〜第７ブランチＢ７からなる配置対象の部分回路であり、初回に自動配置の対象となったのは第１ブランチＢ１〜第５ブランチＢ５からなる配置対象の部分回路であるので、新旧の配置対象の部分回路間で重畳する３個のブランチは、第３ブランチＢ３〜第５ブランチＢ５である。従って、今回の解候補の第３ブランチＢ３〜第５ブランチＢ５の部分に含まれる素子のｙ座標の候補値については、初回の解候補の該当部分の値をそのまま継承し、新たに加えられた第６のブランチＢ６〜第７ブランチＢ７については、前述の初回の動作と同様の手法で生成する。
【００６２】

となる。ここで、各解候補の上部の符号は該当するブランチを示す。
【００６３】
Ｘ座標決定部３２は、ステップＢ１では未定であった各素子のＸ座標をコンパクションによって決定する（ステップＢ２）。ここでは、コンパクション方法として、例えば、佐々木等の文献に記載されているような、いわゆる１次元コンパクションを用いて説明する。コンパクションは、当該配置対象の部分回路内の左側に位置するブランチから順次的に、ブランチ内で下に位置する素子から逐次的に、或いは左側の素子に接続を持つ素子を優先させて、素子を１つずつ−Ｘ方向すなわち水平に左の方向に移動して詰めるように配置する手法であり、コンパクトな配置面積を与えるＸ軸方向の配置手法である。なお、素子を左に平行移動した際に、上下に少しずらすだけで更に左に移動できる場合は、そのような移動を行うことによって、更にコンパクトな配置をすることが可能となる。
【００６４】
このコンパクションによって配置できる範囲は、前記配置結果ファイルに記憶されている配置済みの素子の座標、素子の配置可能領域及びデザインルール等により決定されてもよい。
【００６５】
コンパクションに関する制約として、移動中のブランチに属する素子は、１つ（又は２つ）前の既に配置されたブランチに属する最も左に位置する素子のＸ座標より左側にならない範囲で、左側に詰めるようにして配置するという条件を付加してもよい。この場合には、回路図上の素子の位置関係が良好に保存される。
【００６６】
適応度評価部３３により、所定の評価関数に従って、各解候補の適応度が算出される（ステップＢ３）。評価関数については、例えば、当該配置対象の部分回路に属する全素子のコンパクションの最右の素子（最も右側の領域を占めている素子）の右端の座標をコストとして考えると、この値は、各解候補の面積の大きさの１つの評価指標として評価関数に採用できる。そこで、例えば、解候補ｗの適応度ｆ（ｗ）を、
ｆ（ｗ）＝（現世代の全解候補の面積に関するコストの最大値）−（解放補ｗの面積に関するコスト）
のように定義してもよい。
【００６７】
面積に関するコストの他に、ブランチにおける素子の上下関係をなるべく保存するために用いるオーダーコスト等が必要であるが、それらについては第２実施例で詳述することにし、ここでは割愛する。
【００６８】
ステップＢ４において、処理ループ回数が図３のステップＡ２で設定された所定の回数以下であれば、ステップＢ５〜ステップＢ７を繰り返して新たな解候補群を生成する。
【００６９】
ステップＢ５において、選択部３６は、各解候補毎に適応度に基づいて決定される選択確率に従って、全解候補のうちから交叉すべき２つの解候補を選択し、選択された２つの解候補を、親１及び親２とする。
【００７０】
この場合において、例えば、解候補ｗの選択確率Ｐ（ｗ）を、
Ｐ（ｗ）＝ｆ（ｗ）／（全ｆの総和）
により与えてもよい。
【００７１】
選択の手法として実数区間［０，１）を、各解候補の選択確率に応じた数値範囲に分割し（例えば、［０，０．１）、［０．１，０．３）、…、［０．９７，１））、［０，１）間で一様に発生させた乱数が含まれる数値範囲に対応する解候補を選択するようにしても良い（例えば、乱数が０．１５ならば、第２番目の解候補を選択する）。
【００７２】
この場合には、所定の乱数により、まず解候補１が選択され、次に解候補４が選択されたとすると、次のように、解候補１が親１、解候補２が親２とされる。

ステップＢ６において、交叉部３７は、選択された親１及び親２に対して互いの成分を交換する交叉を施し、新たな解候補である子１及び子２を生成する。
【００７３】
交叉は選択された２つの解候補に含まれる各ブランチ毎に以下のように実施される。
まず、ブランチ毎に予め設定された交叉率に従って、交叉が施されるか施されないかが決定される。ここで、各ブランチの交叉率は、例えば、０．２、０．２、０．５、０．５、０．８、のように、左に位置するブランチに対するものほど低い値であってもよい。
【００７４】
次に、交叉が施されることが決定したブランチ間でのみ交叉が実施される。
交叉には種々の方法があるが、一様交叉を施す場合を説明する。一様交叉は、“０”又は“１”を等しい確率で発生する手段を用いて、該当するブランチの素子数と等しい長さを有するマスクパターンを生成し、マスクパターン上の“１”を示す位置に対応する成分に関して、親１及び親２の間での交換を行う。
【００７５】
以下に、左から２番目のブランチ、４番目のブランチ、５番目のブランチに対して一様交叉が施される例を示す。このとき生成されたマスクパターンは、“０１０”、“１１０１”、“００１１”とする。

突然変異部３８は、生成された子１及び子２に対してそれぞれ、突然変異操作すなわち算術的操作を施す（ステップＢ７）。
【００７６】
この突然変異は各解候補に含まれる各ブランチ毎に以下のように実施される。まず、ブランチ毎に予め設定された突然変異率に従って、突然変異が施されるか施されないかが決定される。各ブランチの突然変異は、交叉と同様に、０．１、０．１、０．３、０．３、０．５のように、左に位置するブランチに対するものほど低い値であってもよい。
【００７７】
次に、突然変異が施されることが決定したブランチにおいてのみ突然変異が実施される。
突然変異には種々の方法が考えられるが、ブランチ内からランダムに選んだ１つの成分の値に小さな値αを加えるという方法を用いても良い。ここではαは突然変異を行う都度、例えば｛＋３、＋２、＋１、−１、−２、−３｝の中からランダムに選択されるものとする。但し、この場合に、例えば＋３することによって配置可能領域をはみ出るような場合は、他の値の中から選択し直すことにする。
【００７８】
子１の左から３番目と５番目のブランチに対して突然変異が発生したときの例を示す（３番目のブランチに対しては、第１成分に−２を加え、５番目のブランチに対しては、第４成分に＋１を加えている）。
【００７９】
子１については、

である。
【００８０】
突然変異率は初期値を与えて、世代を経る毎にその値を徐々に減少させ、最終世代では０に近い値となるように設定してもよい。
解候補の数と同数の子が生成されるまで、ステップＢ５〜ステップＢ７、すなわち選択、交叉及び突然変異を繰り返す。そして、子の集団を、新世代の解候補群とする（ステップＢ８）。
【００８１】
以上の新世代の解候補群の生成（所定回数のステップＢ５〜ステップＢ７のループ）、この解候補群に対するコンパクション（ステップＢ２）及びその適応度の評価（ステップＢ３）の処理ループが繰り返され、より良い解候補に収束されていく。
【００８２】
そして、処理ループ回数が図３のステップＡ２において設定された回数に達した場合、処理ループを脱出して、ステップＢ９に移る（ステップＢ４）。
ステップＢ９において、最適解選定部３５により、その最終世代の解候補のうちから適応度が最大すなわちコストが最小の解候補を最良の解として選定し、その解候補に関連するデータを出力する。
【００８３】
上記の動作において、図６のステップＢ４の後に、ステップＢ８からステップＢ５に制御が移る前に、適応度のスケーリングをしてもよい。スケーリングは決定された適応度を何らかの関数により拡大或いは縮小することである。スケーリングとして、
ｆ´＝ａｆ＋ｂ
とする線形スケーリングを用いてもよいし、
ｆ´＝ｆ^ｋ
とするべき乗スケーリングを用いてもよい。
【００８４】
上記の第１実施例において、前記部分回路データ抽出部２０が、その都度、対象となる配置対象の部分回路に含まれる全ｍ個のブランチに関連するデータを抽出して前記素子配置部３０に与えているが、前記素子配置部３０が、その回に対象とする配置対象の部分回路に含まれるブランチに関連するデータのうち、次回に対象となる配置対象の部分回路との間で重畳する（ｍ−ｎ）個のブランチに関連する必要なデータを保持しておき、前記部分回路データ抽出部２０は、次回に対象となる配置対象の部分回路に新たに付け加えられるｎ個のブランチに関連するデータのみを抽出して前記素子配置部３０に与えても良い。
【００８５】
上記のように、第１実施例によれば、回路全体を配置対象の部分回路により重畳部分を持って走査しながら素子配置していくので、従来と異なり、局所的な最適化の連続という意味で回路全体を考慮した配置ができ、例えば、配置された素子が占める面積をコスト関数に用いた場合には、素子面積の高密度化を実現することができる。更に本発明によれば、配置対象の部分回路の自動素子配置にブランチの特徴を生かした遺伝アルゴリズムによる配置手法を用いているので、効率的な素子配置が可能となる。
【００８６】
以下、図面を参照しながら第２実施例を説明する。
第２実施例において、装置構成及び適用する回路例は第１実施例と同様であるので、図面と詳細な説明は省略する。
【００８７】
第２実施例の詳細な動作手順を、図７及び図８のフローチャートを用いて説明する。ここで、図３及び図６と同じ動作については同じ符号を付し、詳細な説明は省略する。
【００８８】
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータを入力部１０から読み込む（ステップＡ１）。
入力部１０を介してユーザは、本発明に係るＬＳＩの素子配置システムを用いて実施した図２の回路図の自動配置結果の一例を示す図９に外枠として示されている素子の配置可能領域６０の高さや詳細は後述するパラメータａ、ｂ、ｎ或いは素子配置部３０に関するパラメータ等を設定する（ステップＡ２）
初期解候補群生成部３１は、初期世代の解候補群を作成する（ステップＢ１）。本第２実施例において生成された解候補群の例を以下に示す。

１つの解候補は、第１実施例と同様に、前記配置対象の部分回路（本第２実施例では図２の回路全体を１つの部分回路とみなして説明する）に含まれる２５個の素子にそれぞれ対応する２５個のｙ座標の値を有し、この数列の左側からＲ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３、Ｒ４、Ｑ３、Ｒ５、…というように対応している。ここで、各世代における解候補の個数ｎには、通常、３０〜１００の値を用いるのが効果的である。本第２実施例では、ｎ＝５０として説明する。
【００８９】
Ｘ座標決定部３２は、ステップＢ１では未定であった各素子のＸ座標を決定する（ステップＢ２）。
適応度評価部３３により、所定のコスト関数に従って、各解候補のコストが評価される（ステップＣ１）。コスト関数は、数種類のものを定義し、おのおのについて評価が実施される。
【００９０】
コストは各解候補の評価値であり、本第２実施例においては、値の小さい評価値を有するものほど良い解候補であるものと仮定して説明する。ここでは、コストの例として、素子の隣接性に関するコスト（以下、「ペアコスト」と称する）、配置面積に関するコスト、仮想配線長に関するコスト、及びブランチにおける素子の上下関係に関するコスト（以下、「オーダーコスト」と称する）の４種類のコストを用いて説明する。
【００９１】
ペアコストは、ステップＡ２において入力される素子の隣接性に関する制約条件によって計算される。素子の隣接性に関する制約条件とは、例えば、
１．素子Ｒ２と素子Ｒ４はなるべく隣接するように配置する
２．素子Ｑ８と素子Ｑ９はなるべく隣接するように配置する
というような条件であり、優先的に隣接させたい２素子に対して予め配置許容範囲を設定しておき、例えば、その許容範囲から外れた部分の面積を、その２素子に係わるコストとする。そして、すべての優先的に隣接させたい２素子に係わるコストを算出して総和を求め、その値をコストとする。
【００９２】
配置面積に関するコストは、第１実施例と同様である。
仮想配線長に関するコストは、例えば、ネット毎に、そのネットに関連する全端子を含む最小長方形の周囲の長さの１／２（但し、関連する全端子を含む最小図形が１線分の場合は、その長さ）と定義し、すべてのネットに対する総和をそのコストとする。
【００９３】
オーダーコストは、ブランチにおける素子の上下関係をなるべく保存するために用いられ、例えば、同じブランチ上で上下に隣合う２素子の基準点のｙ座標の大小関係が逆転している場合に、そのずれをコストとする。
【００９４】
コスト関数により算出されるコストには、それらの重要性に従って順位付けがされており、その順位は後述の選択操作において用いられる。ここでは、配置面積に関するコスト（コスト１とする）、仮想配線長に関するコスト（コスト２とする）、ペアコスト及びオーダーコスト（コスト３とする）の順に、重要性が高いものとする。ペアコストとオーダーコストの重要性は同程度と仮定する。
【００９５】
選択部３６により、解候補群に対して、各解候補の有するコストに基づいた確率を用いて選択操作が施される（ステップＣ２）。選択操作を図８を参照して説明する。
【００９６】
最も重要性の高いコスト１すなわち配置面積に関するコストを用いてａ個の解候補からなる集合Ａを生成する（ステップＤ１）。この場合において、ａ＞ｎとし、ここでは、ａ＝７０とする。
【００９７】
まず、各解候補毎に、その解候補のコスト１を用いて適応度を算出する。適応度については、例えば、解候補ｗの適応度ｆ（ｗ）を、
ｆ（ｗ）＝（現世代の全解候補のコスト１のうちのの最大値）−（解候補ｗのコスト１）
のように定義してもよい。
【００９８】
全ｎ個の解候補について適応度が算出されたら、この適応度に基づいて、各解候補が選択される確率を決定する。例えば、解候補ｗの選択確率Ｐ（ｗ）を、
Ｐ（ｗ）＝ｆ（ｗ）／（全ｆの総和）
により与えてもよい。
【００９９】
次に、解候補ｗの選択確率Ｐ（ｗ）を用いて、ｎ個の解候補のうちからａ個の解候補を選択する。この場合において、もとの解候補の集合の要素数ｎより、集合Ａの要素数ａの方が大きいので、集合Ａには必ず重複する解候補が存在する。
【０１００】
この選択の手法については、第１実施例の中で述べた選択の手法と同様の手法により、解候補を選択するようにしてもよい。そして、乱数をａ回発生させて、該当するａ個の解候補からなる集合Ａを生成する。
【０１０１】
２番目に重要性の高いコスト２すなわち仮想配線長に関するコストを用いて同様の操作を施して、ａ個の解候補からなる集合Ａから、ｂ個の解候補からなる集合Ｂを生成する（ステップＤ２）。ここで、ｂ＜ａ、かつ、ｂ＞ｎとし、この場合には、ｂ＝６０とする。
【０１０２】
コスト３すなわちペアコスト及びオーダーコストを用いて同様の操作を施す。このように重要度が同程度のコストが数種類ある場合は、それぞれのコストを、例えば、０以上１以下の実数値に換算して、その和をコスト３と考え、適応度を定義する。この適応度に基づく選択確率によって、ｂ個の解候補からなる集合Ｂから、ｎ個の解候補からなる集合Ｃを生成して、この選択操作を完了する（ステップＤ３）。そして、このｎ個の解候補を含む集合Ｃを、次の交叉操作のための親の集合Ｚとする。
【０１０３】
ここでは、前述のコスト１〜コスト３を用いて、交叉操作について説明したがコストが２種類の場合は、ステップＤ２を省けばよい。
重要性の異なるコストが４種類以上の場合は、ステップＤ２に該当するステップを適宜挿入すればよい。その際、前述の操作は高い重要性を有するコストから順に実施する。この場合、第ｓ番目に重要性の高いコストｓを用いて選択される解候補の数Ｕ（ｓ）は、
Ｕ（１）＞ … Ｕ（ｓ−１）＞Ｕ（ｓ）＞Ｕ（ｓ＋１） … ＞ｎ
の関係を満たせばよい。
【０１０４】
また、予め相対的な重み付けが容易にできる複数のコストに対しては、それらを１つのコストとみなしても良い。例えば、ペアコストとオーダーコストの相対的な重み付けが４：３となるように与えることができる問題（配置対象）に対しては、まずそれぞれのコストを例えば０以上１以下の実数値に換算して、換算されたペアコストの４倍と、換算されたオーダーコストの３倍との和を１つのコストとみなしても良い。
【０１０５】
交叉部３７は、選択操作により生成された集合Ｚに含まれるｎ個の親すなわち解候補に対して互いの成分を交換する交叉を施し、新たな解候補であるｎ個の子を生成する（ステップＢ６）。
【０１０６】
まず、集合Ｚに含まれる親を２個ずつ組にして、ｎ／２組のペアを生成する。その際、どの親同士をペアにするかは任意或いはランダムとする。これら親のペアを、
（親１、親２）、（親３、親４）、…、（親ｎ−１、親ｎ）
で表す。第２実施例ではｎ＝５０としたので、２５組の親のペアすなわち
（親１、親２）…（親４９、親５０）
が生成される。
【０１０７】
次に、各親のペアに対して第１実施例と同様に、予め設定された交叉率に基づいて、交叉操作を行う。
上記のようにして、各親のペアから２個の子を生成し、合計ｎ個の子が生成される。第２実施例では、子１〜子５０が生成される。
【０１０８】
突然変異部３８は、交叉が施されて生成されたｎ個の子に対して、第１実施例と同様に、突然変異操作を施す（ステップＢ７）。
ステップＢ２からステップＢ７に至る一連の操作からなる処理ループの繰り返し回数が所定の回数に達したかを判断し、達しない場合はステップＢ２のコンパクションに移って処理ループを繰り返し、達した場合にはステップＣ３の終了処理に移る（ステップＢ４）。
【０１０９】
上記処理ループが一巡する毎に新しい解候補群が生成され、より良い解候補が探索されて、最適解もしくは近似最適解に収束していく。
終了処理を施す（ステップＣ３）。具体的には、ステップＢ２からステップＣ２までの操作と同一の操作を実施し、選択操作によって得られるｎ個の解候補の中から最小のコストを有する解候補を解として選定する。
【０１１０】
出力部５０は、前記配置結果ファイルの内容を所定のデバイスに出力する（ステップＡ１０）。
上記のように、本発明の第２実施例によれば、最適化手法として遺伝アルゴリズムを採用し、各世代における解候補の選択の際にコスト関数をその重要度に応じた順番で適用することにより、解候補をふるいにかけて絞り込む手法を用いるので、すべてのコスト関数に関し最適もしくは近似最適な解を効率よく求めることが可能となる。
【０１１１】
図９には、本発明に係るＬＳＩの素子配置システムを用いて実施した図２の回路図の自動配置結果の一例を示す。
以下、図面を参照しながら第３実施例を説明する。
【０１１２】
第３実施例において、装置構成及び適用する回路例は第１実施例と同様であるので、図面と詳細な説明は省略する。
図１０は本発明の第３実施例の概略動作を示すフローチャートであり、図１１は図１０のフローチャートの中の遺伝アルゴリズムの概略を示すフローチャートであり、基本的には、図６と同じ動作を示す。図１２は図１０のフローチャートを用いた図２の回路図に対する１つの配置結果を示す図である。
【０１１３】
以下、図１０及び図１１を参照して第３実施例の概略動作を説明する。
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータ、素子配置部３０に関すパラメータ、及びステップＥ５で用いる終了条件等を入力する（ステップＥ１）。終了条件は、本実施例においては、ステップＥ３に示すように、任意の配置対象の部分回路に対する遺伝アルゴリズムの世代数の合計が総世代数ｋ以下か否かであるとする。
【０１１４】
全体の回路図を複数個のブランチから成る配置対象の部分回路に分割する（ステップＥ２）。以下の説明では、簡単のため配置対象の部分回路は全て３ブランチから成るとする。従って図２の回路では、（Ｒ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３）、（Ｒ４、Ｑ３、Ｒ５）、（Ｒ６、Ｑ４、Ｒ７）の３ブランチ、（Ｒ８、Ｑ５、Ｒ９、Ｑ６）、（Ｒ１０、Ｑ７、Ｑ８、Ｒ１１）、（Ｑ９、Ｒ１２）の３ブランチ及び、（Ｒ１３、Ｑ１０、Ｒ１４、Ｑ１１）から始まる３ブランチ、の３つの配置対象の部分回路に分割する。３番目の配置対象の部分回路については一般性を失わずに、（Ｒ１３、Ｑ１０、Ｒ１４、Ｑ１１）の右側にも回路が続いているものとして、３ブランチから成るものと仮定する。最右端の配置対象の部分回路については１又は２ブランチから成ることがあるが、そのような例外的なケースについて述べることは本質的ではないのでここでは省略する。
【０１１５】
上記のようにして分割された各配置対象の部分回路に対して、それぞれ、遺伝アルゴリズムが起動され、図１１の概略フローチャートに従って配置改善を行う（ステップＥ３）。ステップＥ３における遺伝アルゴリズムは配置対象の部分回路の総数（ｑとする）だけあり、それぞれ別個のプロセッサで並列に実行される。尚、各遺伝アルゴリズムは予め指定された数ｊだけ世代交代を行う。ここではｊ＝１０とする。図１１に示す遺伝アルゴリズムの処理の具体的な説明は後述する。
【０１１６】
第３実施例は、各遺伝アルゴリズムをそれぞれ別個に実行する間に、例えば、ｊ＝１０世代毎に隣の部分回路の配置結果の情報を参照する実施例である。これによって、回路全体の配置の性能を考慮することを目的とする。すなわち、
（ｉ）各部分回路に対して、それぞれ遺伝アルゴリズムをｊ＝１０世代実行する（ステップＥ３）。
（ｉｉ）各部分回路に対する最後の世代（すなわち１０ｘ_ｉ 世代目、但し、ｉ＝１、２、…）の最良の配置結果をそれぞれ共有メモリにコピーする（ステップＥ４）。ここで、コピーとは、以前のデータに新しいデータを上書きするという操作である。
上記のステップＥ３及びステップＥ４を最後の世代が総世代になるまで繰り返す（ステップＥ５）。すなわち、ステップＥ５では、最後の世代が総世代数ｋ以下か否かを判定し、もし総世代数ｋ以下ならばステップＥ３へ、さもなくば、ステップＥ６の出力へと進む（ステップＥ５）。ここではｋ＝ｊ×１００＝１０×１００＝１０００とする。つまりステップＥ３からステップＥ５に至るループは計１００回繰り返されることになる。
【０１１７】
ステップＥ３の遺伝アルゴリズムがステップＥ５に続く処理として実行される場合は、ｉ番目（２≦ｉ≦ｑ）の配置対象の部分回路に対する遺伝アルゴリズムは、共有メモリにコピーされている（ｉ−１）番目の配置対象の部分回路の配置結果の情報を参照する。
【０１１８】
ステップＥ５の判定がＮＯの場合は、その時点の各配置対象の部分回路に対する最良解、即ち、共有メモリに最後にコピーされた各配置対象の部分回路に対する配置結果の情報をそれぞれ出力する（ステップＥ６）。これによって回路の全ての素子に対する最終的な配置座標が決定される。
【０１１９】
ステップＥ３の遺伝アルゴリズムについて図１１の概略フローに従って説明する。以下の説明において、第１実施例と全く同じ動作内容については、詳細な説明は省略する。
【０１２０】
ステップＥ３は、ステップＥ２で決定される配置対象の部分回路の総数ｑだけあり、それぞれが図１１の概略フローに従って第３実施例では並列に実行されることを特徴とする。
【０１２１】
第１実施例と同様に、配置対象の部分回路に属す各ブランチ毎に素子の並び順に従い、そのｙ座標を並べて表現した複数個の解候補から成る初期世代を生成する（ステップＢ１）。
【０１２２】
ステップＢ１の初期世代生成は、ステップＥ３の処理が初めて適用されるときだけ必要となるものであり、２回目以降のステップＥ３〜Ｅ５の処理ループにおいては使用されない。
【０１２３】
各解候補に対してｘ座標を決定するために第１実施例と同様のコンパクションを行う（ステップＢ２）。この場合において、本第３実施例では、１番目の配置対象の部分回路に属するブランチのコンパクションに関しては、図１２のように配置領域の左縁を越えてはならないという条件を付加する。２番目以降の配置対象の部分回路のブランチのコンパクションについては、ステップＥ３の処理が初めて適用されるときは前記の１番目の配置対象の部分回路に対する場合と同様の条件を付加し、ステップＥ５の処理の後、再びステップＥ３の処理が適用される場合は、共有メモリにコピーされている左隣の配置対象の部分回路、すなわち（ｉ−１）番目の配置対象の部分回路の配置結果に対して素子をコンパクションで詰めていく。
【０１２４】
所定のコスト関数から定義される適応度関数に従って、第１実施例又は第２実施例と同様に、各解候補の適応度が算出される（ステップＢ３）。第３実施例においては、仮想配線長に関するコスト、配置面積に関するコスト、オーダーコスト、ペアコスト等を、例えば各コストに重みを付けて和をとり、その総和を解候補のコストとする。
【０１２５】
コストは小さいほど良いので例えば、解候補ｗの適応度ｆ（ｗ）を、
ｆ（ｗ）＝（現世代の全解候補のコストのうちの最大値）−（解候補ｗのコスト）
のように定義する。ｉ（ｉ≧２）番目の配置対象の部分回路に対するコスト計算の際に、ｉ番目と（ｉ−１）番目の配置対象の部分回路間の接続関係によるコストも考慮することとする。例えば、仮想配線長に関しては、ｉ番目と（ｉ−１）番目の配置対象の部分回路を接続しているネットの長さも加算することとする。ここで参照する（ｉ−１）番目の配置対象の部分回路の配置結果の情報は、共有メモリにコピーされているものを使用する。
【０１２６】
以下、ステップＢ５〜ステップＢ８を繰り返して新たな解候補群を生成する。ステップＢ３で算出された適応度に基づいて決定される選択確率に従って、全解候補の中から交叉すべき２つの解候補を選択する（ステップＢ５）。
【０１２７】
ステップＢ５で選択された親１、親２に対して予め設定された交叉率に基づいて交叉を施し、子を２つ生成する。それらの子を子１、子２とする（ステップＢ６）。
【０１２８】
ステップＢ６で生成された子１、子２に対してそれぞれ、予め設定された突然変異率に基づいて突然変異を施す（ステップＢ７）。
解候補の数と同数の子が生成されるまで、ステップＢ５〜ステップＢ７すなわち選択・交叉・突然変異を繰り返す（ステップＢ８）。子の集団を、新世代の解候補群とする。
【０１２９】
ステップＢ３、Ｂ５、Ｂ６及びＢ７を第２実施例のステップＣ１、Ｃ２、Ｂ６及びＢ７に置き換えて、ステップＢ４の判断操作を選択操作の後に位置させても良い。
【０１３０】
以上の新世代の解候補群の生成、この解候補群に対するコンパクション及びその適応度の評価の処理ループ（世代）がｊ回繰り返され、より良い解候補に収束されていく。そして、現在対象としているｉ番目の配置対象の部分回路に対する世代数の合計、すなわちステップＥ３の処理が初めてｉ番目の配置対象の部分回路に適用されてからの処理ループ回数の合計が前述の指定数ｊの倍数、即ちｊ、２ｊ、３ｊ、…、１００ｊの何れかに達した場合、処理ループを脱出して、ステップＢ９の処理に移る。ステップＢ４ではそのための判定を行う。
【０１３１】
ステップＢ９では、そこまでのｊ回の処理ループの最後の世代の適応度最大の、即ちコスト最小の解候補を最良解とし、その解候補に関するデータを出力する。
【０１３２】
上記のステップＥ３の遺伝アルゴリズムが全ての配置対象の部分回路に対して並列に実行される。
上記のように、第３実施例によれば、回路全体を複数個のブランチからなる配置対象の部分回路に分割し、それぞれの配置対象の部分回路の素子配置に対しては直前の配置対象の部分回路の、予め指定された世代数ｊ毎の最良解の配置結果の情報をも参照することによって、隣合う配置対象の部分回路の間の相対的な関係を考慮しつつ、各配置対象の部分回路の素子配置に対して遺伝アルゴリズムを並列的に適用するので、回路全体を考慮した質の高い配置結果を高速に求めることが可能となる。
【０１３３】
以下、図面を参照しながら第４実施例を説明する。
第４実施例において、装置構成及び適用する回路例は第１実施例と同様であるので、図面と詳細な説明は省略する。
【０１３４】
図１３は本発明の第４実施例の動作を示すフローチャートであり、図１４は図１３のフローチャートの中のｙ座標の調整の概略を示すフローチャートであり、図１５は図１３のフローチャートを用いた、図２の回路図に対する１つの配置結果の例を示す図である。
【０１３５】
第４実施例の動作を図１３及び図１４を参照して説明する。図１３において図３及び図６と同じ動作には同じ符号を付し、詳細な説明は省略する。
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータや素子配置部３０に関するパラメータ及びステップＦで用いるパラメータ等を、第１実施例と同様に、入力部１０から読み込む（ステップＡ１）。
【０１３６】
第１実施例と同様に、配置対象の回路図に属する各ブランチ毎に、素子の並び順に従い、そのｙ座標を並べて表現した複数の解候補からなる初期世代を生成する（ステップＢ１）。
【０１３７】
第１実施例と同様に、各解候補に対してｘ座標を決定するためにコンパクションを行う（ステップＢ２）。
所定のコスト関数から定義される適応度関数に従って、第１実施例と同様に、各解候補に対する適応度が算出される（ステップＢ３）。コスト関数については、第１〜第３実施例と同様である。
【０１３８】
以下、ステップＢ５〜ステップＢ８を繰り返して新たな解候補群を生成する。ステップＢ５〜ステップＢ８（ステップＦを除く）は、第１実施例と同じであるので、詳細な説明は省略する。
【０１３９】
ステップＢ３で算出された適応度に基づいて決定される選択確率に従って、全解候補の中から交叉すべき２つの解候補（親１、親２）を選択する（ステップＢ５）。
【０１４０】
ステップＢ５で選択された親１、親２に対して予め設定された交叉率に従って交叉を施し、子１及び子２を生成する（ステップＢ６）。
ステップＢ６で生成された子１、子２に対してそれぞれ、予め指定された突然変異率によって突然変異が施され、子１’、子２’が生成される（ステップＢ７）。
【０１４１】
ステップＢ７で生成された子１’、子２’に対してそれぞれ、予め指定された確率δに従い、隣合うブランチ内でｙ座標が近接している素子のペアを探し、もしそのようなペアがあればその２素子のｙ座標を同一の値とする（ｙ座標調整する）、という操作を行う（ステップＦ）。
【０１４２】
解候補の数と同数の子が生成されるまで、ステップＢ５〜ステップＦすなわち選択・交叉・突然変異・ｙ座標調整を繰り返す（ステップＢ８）。子の集団を、新世代の解候補群とする。
【０１４３】
以上の新世代の解候補群の生成、この解候補群に対するコンパクション及びその適応度の計算の処理ループ（世代）が予め設定された世代数だけ繰り返され、より良い解候補に収束されていく。ここでこの処理ループの脱出条件として、「予め設定された世代数に達した場合」という条件の他に、「全ての個体が同じ適応度を持った場合」という条件を付加してもよい。
【０１４４】
最終世代における最良解の配置結果の情報、即ち各素子の配置座標を出力する（ステップＢ９）。
以下、図１４に従ってステップＦのｙ座標の調整につき具体的に説明する。
【０１４５】
ループ回数として用いるパラメータｉの値を１に設定する（ステップＦ１）。
０以上１以下の実数の一様乱数値ｒを発生させる（ステップＦ２）。
ｒが、予め指定されたｙ座標調整に関する確率δよりも小さい場合はステップＦ４へ、さもなくば、ステップＦ６へ進む（ステップＦ３）。この場合において、例えば、ｒ＝０．４、δ＝０．７ならばステップＦ４に進む。δの値は図１３の遺伝アルゴリズムの全世代に亙って定数としても良いし、或いは世代が進む毎に少しずつ増大させていく等、動的に変化させても良い。増大させると、一般に、後半の世代に行くほどｘ方向の整列度の度合いが高まることになる。
【０１４６】
ｉ番目と（ｉ＋１）番目のブランチのコードを比較してｙ座標の差の絶対値が１以上ｐ以下であるペアｙ（ｉ，ｋ）、ｙ（ｉ＋１，ｈ）を１組探す。複数組あるときはランダムに１組を選択する（ステップＦ４）。
【０１４７】
ここで、ｙ（ｊ，ｍ）はｊ番目のブランチのｍ番目の要素を意味する記号である。ｐの値はｙ座標の近接の度合いを反映し、本実施例では、ｐ＝２として説明する。即ち、
｜ｙ（ｉ，ｋ）−ｙ（ｉ＋１，ｈ）｜＝１又は＝２
であれば、ｉ番目のブランチのｋ番目の素子と、（ｉ＋１）番目のブランチのｈ番目の素子が近接していると判断する。
【０１４８】
例えば、ｉ＝１のとき、子１’において１番目のブランチのコードが、
０ １０ １５ ２７ ３７
であり、２番目のブランチのコードが
０ ２６ ３０
である場合に、１番目と２番目のブランチのコードを比較すると、｜ｙ（１，４）−ｙ（２，２）｜＝｜２７−２６｜＝１であるので、１番目のブランチの４番目の素子と、２番目のブランチの２番目の素子は近接していることが分かる。
【０１４９】
上記のような近接ペアｙ（ｉ、ｋ）、ｙ（ｉ＋１、ｈ）の探し方は、例えば、ｉ番目のブランチの要素ｙ（ｉ、ａ）と（ｉ＋１）番目のブランチの要素ｙ（ｉ＋１、ｂ）をランダムに選択し、それら２要素の差の絶対値が１以上ｐ以下であるか否かという条件をチェックする、という操作を例えば高々１０回繰り返し、その途中過程で１組でも条件を満たすものがあれば、そのペアを近接ペアとして採用する、という方法を採用しても良い。或いは、チェック時間は増えるが、考え得る全てのペアをチェックして、条件に合うペアを１つ選択するという方法を採用しても良い。
【０１５０】
ステップＦ４において近接しているペアｙ（ｉ，ｋ）、ｙ（ｉ＋１，ｈ）が探索された場合は、それらのうちの一方の値を他方にコピー（上書き）する（ステップＦ５）。即ち、
（ａ）ｙ（ｉ，ｋ）の値をｙ（ｉ＋１，ｈ）にコピーするか、又は
（ｂ）ｙ（ｉ＋１，ｈ）の値をｙ（ｉ，ｋ）にコピーする。
（ａ）、（ｂ）のどちらを実行するかはランダムとする。例えばステップＦ４の説明で用いたペアｙ（１，４）、ｙ（２，２）に対して、（ａ）を実行すると、子１’の２番目のブランチのコードは
０ ２７ ３０
となり、１番目のブランチの４番目の素子と、２番目のブランチの２番目の素子が、互いの基準点が同一の水平線（ｙ＝２７）上に位置しているという意味で、横に隣合うことになる。
【０１５１】
上記のようにして、ｙ座標調整の対象になった２個の素子のｙ座標の値は、ステップＦ２〜ステップＦ７のループを抜けでるまでは、再び変更されることはないものとする。従って、上記の（ａ）、（ｂ）の選択の例外として、もしｙ（ｉ、ｋ）が値の変更を許されていない場合は、（ａ）を選択することになる。
【０１５２】
このように、一旦ｙ座標調整の対象となった２素子のｙ座標は、ｉがブランチの総数未満の間は、再変更しないことにより、例えば隣合うブランチのコードが
０ ２５ ４０； ０ ２６ ３６； ５ ２６
の場合、まず「ｉ＝１の時」２番目のブランチの２番目の値が一旦２５に調整され、次に「ｉ＝２の時」再びその値が２６に戻るという無駄な操作は回避されることになる。例えば、次のようにブランチのコードが変化する。
０ ２５ ４０； ０ ２６ ３６； ５ ２６ （ｉ＝１；（ａ）を実行）
→ ０ ２５ ４０； ０ ２５ ３６； ５ ２６ （ｉ＝２；（ｂ）を実行）
→ ０ ２５ ４０； ０ ２６ ３６； ５ ２６
ステップＦ４において近接しているペアが探索されなかった場合は、ステップＦ５においては何も実行しない。
【０１５３】
パラメータｉの値に１を加える（ステップＦ６）。
以上のステップＦ２〜ステップＦ６の操作を、（ブランチの総数−１）回繰り返す（ステップＦ７）。図２の例では７−１＝６回繰り返す。
【０１５４】
図１４に記載の方法では、パラメータｉを初期値１から１ずつ増加させることにより、ブランチの左側から順次、ｙ座標調整を施しているが、それとは逆に、ｉの初期値を（ブランチの総数−１）として１ずつ減少させることによって、ブランチの右側から順次、ｙ座標調整を施すという方法を用いても良い。更には、１以上、（ブランチの総数−１）以下のｉの値をランダムに「ブランチの総数×δ」個選び、ステップＦ４、ステップＦ５の操作を行うという方法を用いても良い。
【０１５５】
上記のように、第４実施例によれば、ブランチの特徴を生かした遺伝アルゴリズムを適用する際に、遺伝的操作の１つとして、ｙ座標の調整を行うことにより、横に隣合うことによって面積の縮小と配線のし易さを増すような素子のペアが徐々にｘ方向に整列していくので、最終的にｘ方向への整列性に優れた質の高い配置結果を効率よく求めることが可能となる。
【０１５６】
本発明は上述した実施例に限定されない。
実施例においては、左側のブランチに属する素子から順に配置する場合について説明したが、もちろんその反対に右側から配置する場合でも、本発明は同様に適用でき、同様の効果が得られる。
【０１５７】
図７において、ステップＢ４の判断操作をステップＣ２の選択操作とステップＢ６の交叉操作との間に移動し、ステップＣ３の終了処理を最良解の選定処理とし、ステップＢ４の判断操作における所定回数を１増加しても、等価なフローチャートとなる。
【０１５８】
図６、図７、図１１及び図１３で用いた遺伝アルゴリズムの手法は非常に基本的なものであり、他の種々の遺伝アルゴリズムの手法が適用可能である。例えば前世代の最良解を無条件で次世代に残すというエリート戦略や、初期の世代で局所解に陥ることを防ぐためのスケーリングや期待値戦略などの各種の技法を盛り込めることは勿論のことである。第１〜第４実施例では新しい世代を生成する際に親の数（例えば５０）から、親と同数（５０）の子を生成し、そうして得られた子の集団を新世代の解候補群としているが、この方法の代わりに子を例えば２０個生成し、それらを親の集団に追加して得られる７０個の解候補からなる集団から適応度の高い順に５０個の個体を選出し、それらを新世代の解候補群としてもよいことは勿論のことである。
【０１５９】
また、上記実施例では、個別に説明したが、これに限らず、例えば、第１実施例と第２実施例、第１実施例及び第２実施例と第４実施例、第３実施例と第４実施例、或いは、第１実施例と第４実施例、と云ったように自由に組み合わせて適用することができる。他には、第２実施例と第３実施例、或いは、第２実施例及び第３実施例と第４実施例という組合せも可能である。
更に、本発明は上述した実施例に限定されるものではなく、その要旨を逸脱しない範囲で、種々変形して実施することができる。
【０１６０】
【発明の効果】
本発明によれば次のような効果が得られる。
本発明の第１局面に係るＬＳＩの素子配置方法及び装置によれば、回路全体を所定数（例えば、ｍ個）のブランチから構成される配置対象の部分回路に対して、ｍ個より少ない個数（例えば、（ｍ−ｎ）個）のブランチの重畳部分を持って素子を配置する。従って、本発明の第１局面に係るＬＳＩの素子配置方法及び装置によれば、局所的な最適化を連続して行うので、回路全体を考慮した素子配置が可能であり、更に、ブランチの特徴を生かした遺伝アルゴリズムを用いた素子配置方法と相俟って、例えば、配置された素子が占める面積をコスト関数に用いた場合は素子面積が高密度化された、質の高い素子配置結果を効率よく求めることができる。
【０１６１】
上記のＬＳＩの素子配置方法及び装置によれば、最適化手法として遺伝アルゴリズムを採用し、各解候補毎のコストが評価された後の各世代における解候補の選択をする場合に、コスト関数をその重要度に応じた順番で適用することにより、解候補をふるいにかけて絞り込んでいくので、すべてのコスト関数に対して最適もしくは近似最適な解を効率よく求めることが可能となる。
【０１６３】
本発明の第２局面に係るＬＳＩの素子配置方法及び装置によれば、ＬＳＩにおける素子の自動配置において、ブランチの特徴を生かした遺伝アルゴリズムを適用する際に、遺伝的操作の１つとして、各世代の各解候補のコード（染色体）に対して、予め指定された確率に従い、隣合うブランチ内でｙ座標が近接している素子のペアを探し、もしそのようなペアがあればその２素子のｙ座標を同一の値とするという操作を行う。この操作によって、横に隣合うことにより面積の縮小や配線のし易さ等に貢献するような素子のペアが徐々にｘ方向に整列していくので、最終的にｘ方向への整列性に優れた質の高い配置結果を効率良く求めることが可能となる。
【図面の簡単な説明】
【図１】本発明の第１実施例に係るＬＳＩ素子配置装置の構成を示すブロック図。
【図２】本発明に係るＬＳＩ素子配置装置を適用する回路図の一例。
【図３】図１に示す素子配置装置の動作を示すフローチャート。
【図４】本発明に係るＬＳＩ素子配置装置を用いて実施した図２の回路図の自動配置結果の一例。
【図５】素子配置部３０の概略構成を示す図。
【図６】図１に示すＬＳＩ素子配置装置の素子配置手段の動作を詳しく示すフローチャート。
【図７】本発明の第２実施例に係るＬＳＩ素子配置装置の動作を示すフローチャート。
【図８】第２実施例の選択手段の動作を示すフローチャート。
【図９】本発明に係るＬＳＩ素子配置装置を用いて実施した図２の回路図の自動配置結果の一例。
【図１０】本発明の第３実施例の処理工程を示すフローチャート。
【図１１】図１０のフローチャートの中の遺伝アルゴリズムの概略を示すフローチャート。
【図１２】図１０のフローチャートを用いた図２の回路図に対する１つの配置結果を示す図。
【図１３】本発明の第４実施例の処理工程を示すフローチャート。
【図１４】図１３のフローチャートの中のｙ座標の調整の概略を示すフローチャート。
【図１５】図１３のフローチャートを用いた図２の回路図に対する１つの配置結果。
【符号の説明】
１０…入力部、２０…部分回路データ抽出部、３０…素子配置部、
３１…初期解候補群生成部、３２…Ｘ座標決定部、３３…適応度評価部、
３４…解候補群更新部、３５…（近似）最適解選定部、３６…選択部、
３７…交叉部、３８…突然変異部、４０…配置結果ファイル作成部、
５０…出力部。[0001]
[Industrial applications]
The present invention relates to a system for automatically arranging elements in an LSI design, and more particularly to an element arranging method and an element arranging apparatus in which the positional relationship of elements on a circuit diagram is stored.
[0002]
[Prior art]
In LSI design, it is very important to place all elements in a small area region after preserving the positional relationship of elements on a circuit diagram (schematic) to some extent. Conventional element placement by hand achieves such high density placement, but requires skill and a large amount of work time.
[0003]
Therefore, in recent years, research and development of an automatic element placement apparatus have been activated in order to realize optimum or approximate optimum element placement in a short time, and various automatic element placement methods such as a simulated annealing method have been proposed. For example, Sasaki, Susa, "Element placement method in analog cell generation", IEICE Technical Report, VLD90-94, 1990, the procedure of automatic placement was disclosed, and many other methods applying genetic algorithms. Has been proposed.
[0004]
A genetic algorithm is a method of stochastic search proposed based on the genetic mechanism of living organisms. After generating an initial solution candidate group, evaluating the fitness of each solution candidate and evaluating the next solution candidate group It is known as an algorithm for sequentially generating / evaluating a new solution candidate group by selection / crossover / mutation for generation and searching for a solution candidate having higher fitness.
[0005]
However, since the number of elements included in a circuit is enormous, from several thousand to tens of thousands or more, the element arrangement in an LSI requires an approximate (approximate) element arrangement by processing in consideration of the entire circuit configuration in these automatic arrangement systems. Optimization is difficult. Therefore, in the related art, a method is used in which the entire circuit is divided into small partial circuits to be placed and placement processing is performed for each partial circuit to be placed. This method is, for example, a method in which the entire circuit is divided into small placement target partial circuits, and placement processing is performed for each placement target partial circuit in order from the left or right in the circuit diagram. How to divide the entire circuit into partial circuits to be arranged has a great effect on the final result of circuit arrangement, but the division method is not always established, and it is based on trial and error or rules obtained empirically. However, when the circuit diagram is composed of small partial circuits having independent functions, a division method is established. Further, it has not been solved how to efficiently connect the placement results corresponding to the respective partial circuits to be placed obtained by dividing and improve the performance of the placement results for the entire circuit.
[0006]
Therefore, the element placement result provided by the conventional automatic placement system is at a low level of accuracy (approximately) and is not always satisfactory compared to the conventional manual design. Although there is a method that can finally achieve a result similar to that of manual design in terms of the degree of integration, it requires trial and error operations instead of fully automatic operation, and it takes a long time to process until a solution is obtained. It costs.
[0007]
Sasaki et al. Describe an evaluation value relating to constraint conditions such as element adjacency (hereinafter, an evaluation value of an element arrangement result is referred to as “cost”), a cost relating to an area occupied by arranged elements, or a wiring length of element-to-element wiring. And several kinds of evaluation functions (hereinafter referred to as "cost functions") for defining costs and the like, and applying a simulated annealing method to a placement result that minimizes the cost calculated by the cost functions as much as possible. It discloses a method to obtain the same. At that time, Sasaki et al. Adopt a method of multiplying by a weighting factor according to the importance of each cost function to obtain a sum and treat the sum as one cost function.
[0008]
However, Sasaki et al., Although it is possible to assign an order to each cost function according to importance, never disclose a method or guideline for quantifying the importance as a weighting factor. The fact is that it is empirically set / corrected.
[0009]
Further, in the method to which the genetic algorithm is applied, the problem is how to use only an evaluation value of fitness calculated based on a cost function related to one constraint condition and how to incorporate several types of constraint conditions. .
[0010]
As described above, in the conventional LSI element placement method, it is not possible to obtain an optimum or approximate optimum placement result for all of several types of cost functions related to various constraints.
[0011]
One criterion for judging the quality of the arrangement result is whether or not the elements are aligned in the horizontal direction (that is, the x direction) as much as possible. This is because, when the elements are arranged in the horizontal direction, wiring is easier, and a useless area is reduced. However, a specific method of aligning the elements in the horizontal direction as much as possible is not disclosed.
[0012]
[Problems to be solved by the invention]
As described above, the conventional method of arranging the elements of the LSI has many problems in order to obtain a high-quality arrangement result.
SUMMARY OF THE INVENTION An object of the present invention is to provide a method and an apparatus for arranging LSI elements, which provide a high-speed element arrangement result in consideration of the entire circuit at high speed.
[0013]
In particular,
(A) providing an optimal or approximate optimal arrangement result with respect to all cost functions related to constraints on element arrangement;
(B) Applying a genetic algorithm in parallel to the element arrangement of each placement target partial circuit while considering the relative relationship such as the connection relationship or the positional relationship between adjacent placement target partial circuits. ,
(C) The element pairs that contribute to the reduction of the area and the ease of wiring by being adjacent in the horizontal direction are gradually aligned in the horizontal direction during the processing of the algorithm, and the alignment in the horizontal direction is improved. Efficiently seeking excellent and high quality placement results,
Accordingly, it is an object of the present invention to provide a method and an apparatus for arranging an LSI, which provide a high-quality element arrangement result in consideration of the entire circuit at a high speed.
[0014]
[Means for Solving the Problems]
The present invention has taken the following measures in order to solve the above problems.
An LSI element arranging method according to a first aspect of the present invention is directed to an LSI element arranging method for arranging elements according to an arrangement order of branches including element arrays included in a circuit diagram,Inputting the circuit diagram and storing it in a storage unit; and storing the circuit diagram in the storage unit.The data of a predetermined number of branches included in the circuit diagram isIncluding the partial circuit,Of the circuit diagramPredetermined end sideA first step of reading from the storage means in order from the first, and performing an element arrangement operation using a genetic algorithm on the read data of the branch.Calculating the element arrangement in the branch, and determining the element arrangement coordinate data in a smaller number of branches than the number of branches included in the partial circuit based on the operation result.A second step toSaidA third step of obtaining a next partial circuit from a branch whose element arrangement is not determined in the second step and a branch whose element arrangement is read from the storage means and added and whose element arrangement is not determined,The second step and the third step are repeated to sequentially determine the element arrangement coordinate data of the branch.It is characterized by the following.
[0015]
An LSI element placement apparatus according to a first aspect of the present invention is an LSI element placement apparatus that places elements in accordance with the order of branches composed of element rows included in a circuit diagram, and includes a predetermined number of branches included in the circuit diagram. DataIncluding the partial circuit,Of the circuit diagramPredetermined end sideA partial circuit data extracting means for sequentially extracting the data from the branch, and performing an element arrangement operation using a genetic algorithm on the data of the branch extracted by the partial circuit data extracting means.The arrangement coordinate data of the branches is sequentially recorded while determining the arrangement of branches smaller than the branches included in the partial circuit by calculation.Device arrangement means for generating an element arrangement result including arrangement coordinate data of all elements included in the data of the branch.If the partial circuit data extracting means reads the partial circuit after the second time, the partial circuit data extracting means extracts the partial circuit including the branch whose arrangement has not been determined by the element arranging means.Characterized by
In the LSI element placement method according to the first aspect of the present invention, the second step uses the data of the branch extracted in the first step to determine a predetermined number of all elements included in the data of the branch. An initial solution candidate group generating step of generating a first solution candidate group including a plurality of first solution candidates consisting of candidate values of the first coordinates, and for each of the first solution candidates, a first cost relating to at least an element arrangement area. An evaluation step of evaluating a plurality of costs including a second cost relating to a positional relationship between elements, and a predetermined function based on a first cost for each of the first solution candidates from the first solution candidate group. A first generation step of calculating a selection probability, selecting a plurality of second solution candidates larger than a predetermined number, and generating a second solution candidate group including the second solution candidate; and , Each of the second solution candidates Calculating a selection probability by a predetermined function based on the second cost, and selecting a plurality of third solution candidates larger than the number of the first solution candidates and smaller than the number of the second solution candidates; A second generation step of generating a third solution candidate group including solution candidates; and a third generation step of repeating the second generation step until a last solution candidate group is generated for all costs. I do.
[0016]
In the LSI element placement device according to the first aspect of the present invention, the element placement unit uses the data of the branch extracted by the extraction unit to determine predetermined first coordinates of all the elements included in the data of the branch. Initial solution candidate group generating means for generating a first solution candidate group including a plurality of first solution candidates consisting of the following candidate values, and for each of the first solution candidates, at least a first cost relating to an element arrangement area and an element position An evaluation means for evaluating a plurality of costs including a second cost relating to the relationship; and calculating a selection probability by a predetermined function from the first solution candidate group based on a first cost for each of the first solution candidates. A first generation unit for selecting a plurality of second solution candidates larger than a predetermined number and generating a second solution candidate group including the second solution candidates; Based on the second cost for each solution candidate A selection probability is calculated by a predetermined function, a plurality of third solution candidates larger than the number of the first solution candidates and smaller than the number of the second solution candidates are selected, and a third solution including the third solution candidates is selected. A second generation unit for generating a candidate group, and a unit for repeating the second generation unit until a final solution candidate group is generated for all costs.
[0019]
Of the present invention2nd phaseAccording to the LSI element arrangement method according to the first aspect, the second step according to the first aspect uses the data of the branch extracted in the first step to determine a predetermined first one of all the elements included in the data of the branch. A solution candidate group generating step of generating a solution candidate group including a plurality of solution candidates consisting of candidate values of one coordinate, and a vertical direction with respect to a first coordinate axis corresponding to the first coordinates of all elements related to the solution candidate group A second coordinate determination step of determining a second coordinate of a suitable second coordinate axis for each solution candidate by a compaction operation, and, in accordance with a predetermined probability, each solution candidate of the solution candidate group is included in the adjacent branch. A search step of searching for a pair of elements whose first coordinates are close to each other among the elements, and an adjusting step of adjusting the first coordinate value of the element to the same value when the pair of close elements is found. To And wherein the Mukoto.
[0020]
Of the present invention2nd phaseThe device placement device for an LSI according to the first aspect, wherein the device placement unit according to the first aspect uses the data of the branch extracted by the partial circuit data extraction unit to determine a predetermined number of devices included in the data of the branch. Solution candidate group generation means for generating a solution candidate group including a plurality of solution candidates each consisting of a candidate value of one coordinate, and a solution candidate group generating means for generating a solution candidate group that is perpendicular to a first coordinate axis corresponding to the first coordinates of all elements related to the solution candidate group A second coordinate determining means for determining a second coordinate of the second coordinate axis by a compaction operation for each solution candidate, and a branch included in the branch adjacent to each solution candidate of the solution candidate group according to a predetermined probability. Searching means for searching for a pair of elements whose first coordinates are close to each other among the elements; and adjusting means for adjusting the first coordinate value of the element to the same value when the pair of adjacent elements is found. Including And butterflies.
[0021]
[Action]
As a result of taking the above-described measures, the following operation occurs.
According to the method and the device for arranging elements of an LSI according to the first aspect of the present invention, the number of sub-circuits less than m is determined for the partial circuit to be arranged composed of a predetermined number (for example, m) of branches. The elements are arranged with overlapping portions of (for example, (mn) branches). Therefore, according to the method and apparatus for arranging elements of an LSI according to the first aspect of the present invention, local optimization is continuously performed, so that element arranging in consideration of the entire circuit is possible. Combined with the element placement method using a genetic algorithm that takes advantage of, for example, when the area occupied by the placed elements is used for a cost function, the element area is increased in density, and a high-quality element placement result is obtained. It can be obtained efficiently.
[0022]
According to the above-described LSI element placement method and apparatus, when a genetic algorithm is adopted as an optimization method and a solution candidate in each generation is selected after the cost of each solution candidate has been evaluated, a cost function is selected. By applying the solutions in order according to their importance, the solution candidates are sieved and narrowed down, so that optimal or approximate optimal solutions can be efficiently obtained for all cost functions.
[0024]
Of the present invention2nd phaseAccording to the method and apparatus for arranging elements of an LSI according to the present invention, when applying a genetic algorithm taking advantage of the characteristics of a branch in the automatic arrangement of elements in an LSI, one of the genetic operations is performed as one of the genetic operations. For a code (chromosome), according to a predetermined probability, a pair of elements whose y coordinates are close to each other in an adjacent branch is searched, and if there is such a pair, the y coordinates of the two elements are determined to be the same. Perform the operation of setting the value. By this operation, the element pairs that are adjacent to each other and contribute to the reduction of the area and the ease of wiring are gradually aligned in the x direction, and finally the alignment in the x direction is improved. It is possible to efficiently obtain an excellent quality placement result.
[0025]
【Example】
An embodiment of the present invention will be described with reference to the drawings.
FIG. 1 is a block diagram showing a schematic configuration of an LSI element placement apparatus according to a first embodiment of the present invention.
[0026]
Schematically, this LSI element placement apparatus includes an input unit 10 having a storage unit (not shown) for inputting a placement target and storing the input placement target, a partial circuit data extraction unit 20 capable of accessing the storage unit, An element arranging unit 30 connected to the subsequent stage of the partial circuit data extracting unit 20, an arrangement result file creating unit 40 connected to a stage subsequent to the element arranging unit 30, and an arrangement result created by the arrangement result file creating unit 40; An output unit 50 that outputs the contents of the file.
[0027]
The operation of the LSI element placement device shown in FIG. 1 will be described. In this case, the circuit diagram of FIG. 2 is used as an example of an element arrangement target.
In the following description, “branch” refers to an element row formed from several elements connected between a power supply line and a ground line in a circuit diagram. This branch is the smallest unit handled in automatic element placement.
[0028]
For example, in the circuit diagram of FIG. 2, the first branch B1 to the seventh branch B7 generated by dividing the circuit by the curves 11 to 16 are shown. A first branch B1 including five elements R1-Q1-R2-Q2-R3 forming a current path between the power supply line 62 and the ground line 64, and a second branch including R4-Q3-R5 that does not reach the ground. B2, a seventh branch B7 composed of R13-Q10-R14-Q11 in which R14 is branched and connected to the path between the power supply line and the ground line.
[0029]
A schematic operation procedure of the LSI device arrangement device of FIG. 1 will be described. The LSI element placement device shown in FIG. 1 is based on a placement target partial circuit composed of m branches at the left end of the circuit diagram, and uses the genetic algorithm described later in detail to obtain n (<< The arrangement coordinates of the elements belonging to the branch m) are determined. Next, the partial circuit to be arranged is slid to the right by n branches, and the arrangement coordinates of the elements belonging to the next n branches are similarly determined. By repeating this operation and scanning the entire circuit with the partial circuit to be arranged, the arrangement of all elements is performed.
[0030]
A specific operation procedure will be described with reference to FIG.
Data relating to a circuit diagram to be placed, such as element size and type, netlist, branch information, and the like, are read from the input unit 10 (step A1). In this case, the branch information may be manually specified in the circuit diagram by the designer in advance, or may be set by the partial circuit data extraction unit 20 after step A2.
[0031]
Through the input unit 10, the user can place an element shown as an outer frame in FIG. 4 showing an example of an automatic placement result of the circuit diagram of FIG. 2 implemented using the LSI element placement system according to the present invention. The height (the width is not particularly specified) of the region 60, the parameters m and n described later in detail, the parameters related to the element placement unit 30, and the like are set (step A2).
Next, the partial circuit data extraction unit 20 determines a circuit including a predetermined number (in this case, m) branches at the left end of the circuit diagram as a partial circuit to be arranged (step A3). In this embodiment, m = 5 for convenience of explanation. For example, in the circuit of FIG. 2, a circuit including the first branch B1 to the fifth branch B5 is determined as a partial circuit to be arranged.
The partial circuit data extraction unit 20 inputs data related to the partial circuit to be arranged determined in step A3 from the input unit 10 (step A4).
[0032]
Based on the data on the partial circuit to be arranged extracted in step A4, the element arranging unit 30 performs automatic element arranging using a genetic algorithm, which will be described in detail later, based on the data for all the elements included in the partial circuit to be arranged. An arrangement is performed (step A5).
[0033]
The placement result file creator 40 determines, among the solutions obtained in step A5, that is, the placement coordinates of the elements included in the partial circuit to be placed, of the elements belonging to the n branches on the left side of the partial circuit to be placed. Only the arrangement coordinates are recorded in the arrangement result file as final arrangement coordinates (step A6).
[0034]
That is, if n = 2 in the present embodiment, in the circuit of FIG. 2, the element R1 included in the first branch B1 of the first branch B1 to the fifth branch B5 constituting the partial circuit to be arranged is used. , Q1, R2, Q2, R3 and only the coordinates of the elements R4, Q3, R5 included in the second branch B2 are determined as the final coordinates of these elements. The coordinates of the elements belonging to the third branch B3 to the fifth branch B5 are not determined here.
[0035]
If the unprocessed branch that has never undergone the placement processing in step A5 is not “0”, steps A4 to A6 are repeated, and if the number of unprocessed branches is “0”, the operation is moved to step A9 (step A7).
[0036]
The partial circuit data extraction unit 20 removes the n branches whose coordinates have been determined in step A6 from the partial circuit to be placed, and retains the remaining portions (that is, the branch coordinates are not determined in step A6 and are reserved). (Mn) branches, add n branches from the left among unprocessed branches that have not yet undergone the processing of step A5, and arrange them with new m branches It is determined as a target partial circuit (step A8).
[0037]
In step A8, for example, the sixth branch B6 and the seventh branch B7 which are unprocessed branches are added to the third branch B3 to the fifth branch B5 reserved in step A6, and the third branch B3 to the seventh branch B7 are added. Is determined as the next placement target.
[0038]
The steps from the update of the partial circuit to be arranged in step A8 to the determination of the element arrangement coordinates in step A6 are repeated, and the arrangement coordinates of the elements belonging to the new n branches are determined each time this process is performed. .
[0039]
When the number of unprocessed branches is “0” in step A7, the arrangement result file creating unit 40 determines the arrangement coordinates of all the remaining elements that have been reserved without being determined in step A6. Is determined as final arrangement coordinates, and related data is recorded in an arrangement result file (step A9). By this procedure, the arrangement coordinates of all the elements included in the circuit to be arranged are determined, and the arrangement result file is completed.
[0040]
In step A9, for example, in FIG. 2, in the second step A6, the third and fourth branches B3 to B4 of the third to seventh branches B7 included in the partial circuit to be arranged at this time are The coordinates of the arrangement results of the included elements are determined as the final coordinates, and the coordinates of the arrangement results of the elements included in the three branches from the fifth branch B5 to the seventh branch B7 are not determined as the final coordinates. Have been. Then, the coordinates of the placement results of the elements included in the fifth branch B5 to the seventh branch B7 for which the determination is suspended are determined as the final placement coordinates in this step.
[0041]
The output unit 50 outputs the contents of the arrangement result file to a predetermined device (Step A10). The output unit 50 may be any of a monitor screen, a printer, a data communication network, or an information storage medium.
[0042]
In step A8 of the predetermined number of loops of the processing loop, that is, in the last step A8, when the number of unprocessed branches is not n and the number of branches included in the partial circuit to be newly placed is not m, The processing may be performed with the number.
[0043]
Here, it is also possible to change some or all of the parameters set in step A2 using the data stored in the storage unit of the input unit 10 and re-execute. In this case, step A1 is unnecessary. Further, the parameters m and n may not be always constant but may be locally and appropriately varied according to the characteristics of the circuit diagram.
[0044]
In addition, the operation of the first embodiment shown in FIG. 3 is an example, and can be appropriately modified. For example, step A7 is brought before step A6, and when the condition is "Yes", the operation of combining step A6 and step A9, that is, the arrangement result for all the elements given in step A5 is recorded. The same effect can be obtained even if the above configuration is adopted.
[0045]
As described above, according to the first embodiment of the present invention, elements are arranged while scanning the entire circuit with a partial circuit to be arranged with a superimposed portion. The arrangement can be performed in consideration of the entire circuit in the sense of continuity.
[0046]
FIG. 5 is a diagram illustrating a schematic configuration of the element arrangement unit 30.
The element placement unit 30 is connected to the initial solution candidate group generation unit 31 relating to the partial circuit to be placed, an X coordinate determination unit 32 connected to a stage subsequent to the initial solution candidate group generation unit 31, and the X coordinate determination unit 32. A fitness evaluation unit 33, a solution candidate group update unit 34 connected to the fitness evaluation unit 33 and providing data to the X coordinate determination unit 32, and an optimal solution or an approximate optimal solution connected to the fitness evaluation unit 33. And an (approximate) optimal solution selecting unit 35 for selecting and outputting a solution. The solution candidate group update unit 34 includes a selection unit 36, a crossover unit 37, and a mutation unit 38.
[0047]
Prior to the description of the operation of the element arrangement unit 30, terms used in the following description will be defined. "Genetic algorithm" is a method of probabilistic search proposed inspired by the genetic mechanism of living organisms. After generating an initial solution candidate group, evaluating the fitness of each solution candidate, and evaluating the next solution candidate group Is an algorithm that successively generates / evaluates a new solution candidate group by selection, crossover, or mutation to generate a solution, and searches for a solution with higher fitness.
[0048]
The “solution candidate” is a solution candidate for a given problem, and is composed of, for example, a sequence or data sequence such as [1, 0, 0, 0] or [A, B, C, D]. In the case of the first embodiment, it is a sequence of y-coordinate candidate values of elements to be arranged. Specifically, each solution candidate calculates the candidate value of the y coordinate of the reference point (for example, the lower left point of the element) of each element included in the circuit diagram in the order of arrangement from the left side on the circuit diagram of the branch, And a numerical sequence (referred to as a chromosome or a code of a solution candidate) coded in accordance with the arrangement order of the elements in the branch from the bottom of the circuit diagram. As the y coordinate, a grid coordinate obtained by dividing the height of the allocable area into a plurality of equal parts (for example, 50 equal parts) is used. In the following, the lower left point of the element is used as the reference point of each element, and the y coordinate uses an integer of 0 or more and 49 or less.
[0049]
“Solution candidate group” is a set of solution candidates.
“Initial solution candidate” is an initial value of a solution candidate.
The “fitness” is an evaluation value as a solution for each solution candidate calculated by a predetermined evaluation function based on cost or the like (hereinafter, referred to as “fitness function”). The higher the fitness, the better the solution candidate. The fitness may be relatively defined for each generation among solution candidates of that generation.
[0050]
“Selection” is to select two solution candidates from all solution candidates based on the probability determined by the fitness.
"Crossover" is to exchange some components of two selected solution candidates with each other based on a predetermined rule. By this crossover, two new solution candidates are generated.
[0051]
“Mutation” means performing a predetermined arithmetic operation only on a certain component of a certain solution candidate based on a predetermined probability. This mutation prevents the search range from being limited by the initial solution candidate group.
[0052]
A schematic operation procedure of the element arrangement unit 30 will be described.
The element arrangement unit 30 generates a solution candidate group of an initial generation composed of a plurality of solution candidates by a method described later, evaluates each solution candidate, and, based on the solution candidate group, generates the same number of solutions by a procedure described later. A new solution candidate group, that is, a new generation solution candidate group, is generated, the new generation solution candidate group is evaluated, and a further new generation solution candidate group is generated based on the new solution candidate group. As described above, such a procedure is repeatedly executed until a certain condition is satisfied, and one solution candidate is finally selected as a solution of this element arrangement problem.
[0053]
The detailed element arrangement procedure of the element arrangement unit 30 using the genetic algorithm (that is, step A5) will be described with reference to FIG.
The initial solution candidate group generation unit 31 creates an initial generation solution candidate group (step B1). However, since the initial solution candidate group generation unit 31 performs different operations between the first time and the first time when creating the initial generation solution candidate group, the first operation will be described first.
[0054]
In the first time, the partial circuit data extracting unit 20 gives the extracted element data relating to the partial circuit to be placed to the initial solution candidate group generating unit 31 for the first time. The initial solution candidate group generation unit 31 determines the order of the branches belonging to the partial circuit to be arranged from the left side on the circuit diagram, and further according to the order of the elements in the branch from the bottom of the circuit diagram. A predetermined number of solution candidates are generated by arranging the candidate values of the y coordinate of. The set of a plurality of solution candidates generated in this manner is a solution candidate group of the initial generation.
[0055]
The above operation will be specifically described with reference to FIG.
The initial solution candidate group generation unit 31 firstly arranges the element R1 located below the first branch B1 located to the left of the partial circuit to be arranged including the first branch B1 to the fifth branch B5 to be automatically arranged. The y-coordinates are randomly generated in ascending order from the element R3 to the element R3 located above (for example, 11, 14, 23, 28, and 37), and the same processing is performed up to the fifth branch B5. Then, the initial solution candidate group generation unit 31 generates one solution candidate by connecting all the generated y coordinate candidate values in the order of occurrence.
[0056]
As described above, the value of the y coordinate to be generated uses an integer of 0 or more and 49 or less here, but in consideration of a case where the value exceeds the arrangeable area in advance, for example, only an integer of 0 or more and 41 or less is used. (In the example of FIG. 2, an element having a y-coordinate value of 2 or more protrudes from the arrangeable area.) However, even in this case, for example, in the case of an element having a large height such as the element R7 in FIG. 2, the element may protrude from the arrangeable area. (Actually, the value of the y coordinate that R7 can take is 0 or more and 28 or less). In such a case, the correction may be made so as to be barely within the area (for example, when 35 is assigned to R7, the correction is made to 28).
[0057]
An example of the solution candidate group generated by the initial solution candidate group generation unit 31 is shown below.

One solution candidate has 19 candidate y-coordinate values respectively corresponding to the 19 elements included in the partial circuit to be arranged, and R1, Q1, R2, Q2, R3, R4, Q3, R5,... The semicolon is simply a symbol added for the sake of convenience to explain the branch delimiter, and is not character data included in the solution candidate.
[0058]
In this case, the y-coordinate may be generated from a random value generated within an allowable range in consideration of the type, size, design rule, and the like of each element, in addition to the element allocable area 60. Good.
[0059]
As described above, the first generation of the solution candidate group is performed. Next, the operation after the first time will be described.
The partial circuit data extraction unit 20 provides the initial solution candidate group generation unit 31 with element data included in a new partial circuit to be arranged obtained by moving the partial circuit to be arranged to the right by n branches. The initial solution candidate group generation unit 31 sets a set including a predetermined number of solution candidates as an initial generation solution candidate group.
[0060]
In this case, the initial solution candidate group generation unit 31 does not randomly generate the solution candidate group for all the related elements as in the first operation, but instead of the partial circuit of the current placement target and the previous target, The y-coordinates of the elements belonging to the (m−n) branches superimposed between the partial circuits to be arranged are the y-coordinates of the y-coordinates in the solution candidate group obtained in the last time of the previous automatic element arrangement step A5. A solution candidate group is generated by inheriting the value as it is. The inheritance of this value is performed between new and old solution candidates having the same number. For the newly added n branches, the y-coordinate value is generated in the same manner as in the first operation.
[0061]
Hereinafter, the operation of the initial solution candidate group generation unit 31 for generating the initial solution candidate group for the second time and thereafter will be specifically described with reference to FIG.
When generating the initial solution candidate group of the partial circuit to be placed for the second time, the target of automatic placement is the partial circuit to be placed consisting of the third branch B3 to the seventh branch B7, Since the target is the partial circuit to be arranged including the first branch B1 to the fifth branch B5, the three branches superimposed between the new and old partial circuits to be arranged are the third branch B3 to the fifth branch B5. Branch B5. Therefore, as for the candidate value of the y coordinate of the element included in the third branch B3 to the fifth branch B5 of the current solution candidate, the value of the corresponding portion of the first solution candidate is inherited as it is and newly added. The sixth to seventh branches B6 to B7 are generated in the same manner as in the first operation described above.
[0062]

It becomes. Here, the symbol above each solution candidate indicates the corresponding branch.
[0063]
The X coordinate determination unit 32 determines the X coordinate of each element that has not been determined in step B1 by compaction (step B2). Here, as the compaction method, for example, a so-called one-dimensional compaction described in a document by Sasaki et al. Will be described. The compaction is performed sequentially from the branch located on the left side in the partial circuit to be arranged, sequentially from the element located lower in the branch, or by giving priority to the element having connection to the element on the left side, and This is a method of arranging one unit at a time in the −X direction, that is, moving leftward in the horizontal direction, and is an arrangement method in the X-axis direction that provides a compact arrangement area. If the element can be moved to the left only by slightly shifting it up and down when it is translated to the left, such a movement makes it possible to achieve a more compact arrangement.
[0064]
The range that can be arranged by this compaction may be determined based on the coordinates of the arranged elements, the area where the elements can be arranged, the design rules, and the like stored in the arrangement result file.
[0065]
As a restriction on compaction, elements belonging to the moving branch are packed to the left within a range not to the left of the X coordinate of the leftmost element belonging to the immediately preceding (or two) previously arranged branch. The condition of disposition may be added. In this case, the positional relationship of the elements on the circuit diagram is well preserved.
[0066]
The fitness evaluation unit 33 calculates the fitness of each solution candidate according to a predetermined evaluation function (step B3). For the evaluation function, for example, considering the rightmost coordinates of the rightmost element (element occupying the rightmost region) of the compaction of all elements belonging to the partial circuit to be arranged as a cost, this value is The evaluation function can be adopted as one evaluation index of the size of the area of the solution candidate. Therefore, for example, the fitness f (w) of the solution candidate w is
f (w) = (maximum cost related to area of all solution candidates in the current generation) − (cost related to area of open complement w)
May be defined as follows.
[0067]
In addition to the cost related to the area, an order cost and the like used for preserving the vertical relationship of the elements in the branch as much as possible are necessary. These will be described in detail in the second embodiment, and are omitted here.
[0068]
In step B4, if the number of processing loops is equal to or less than the predetermined number set in step A2 of FIG. 3, steps B5 to B7 are repeated to generate a new solution candidate group.
[0069]
In step B5, the selection unit 36 selects two solution candidates to be crossed out of all the solution candidates according to the selection probability determined based on the fitness for each solution candidate, and selects the two selected solution candidates. Are parent 1 and parent 2.
[0070]
In this case, for example, the selection probability P (w) of the solution candidate w is
P (w) = f (w) / (sum of all f)
May be given by
[0071]
As a selection method, the real number section [0, 1) is divided into numerical ranges according to the selection probability of each solution candidate (for example, [0, 0.1), [0.1, 0.3),. A solution candidate corresponding to a numerical range including a random number uniformly generated between [0.97, 1)) and [0, 1) may be selected (for example, if the random number is 0.15, If so, the second solution candidate is selected).
[0072]
In this case, assuming that solution candidate 1 is selected first and solution candidate 4 is selected next by a predetermined random number, solution candidate 1 is set as parent 1 and solution candidate 2 is set as parent 2 as follows. .

In step B6, the crossover unit 37 performs crossover for exchanging the components of the selected parent 1 and parent 2 to generate child 1 and child 2, which are new solution candidates.
[0073]
The crossover is performed as follows for each branch included in the two selected solution candidates.
First, it is determined whether crossover is performed or not according to a crossover rate preset for each branch. Here, the crossover rate of each branch is lower, such as 0.2, 0.2, 0.5, 0.5, 0.8, for the branch located on the left, for example. Good.
[0074]
Next, crossover is performed only between branches that are determined to be crossed.
There are various methods for crossover, and a case where uniform crossover is performed will be described. Uniform crossing generates a mask pattern having a length equal to the number of elements in the corresponding branch by using a means for generating “0” or “1” with equal probability, and indicates “1” on the mask pattern. The component corresponding to the position is exchanged between parent 1 and parent 2.
[0075]
The following shows an example in which the second branch, the fourth branch, and the fifth branch from the left are uniformly crossed. The mask patterns generated at this time are “010”, “1101”, and “0011”.

The mutation unit 38 performs a mutation operation, that is, an arithmetic operation, on each of the generated child 1 and child 2 (step B7).
[0076]
This mutation is performed as follows for each branch included in each solution candidate. First, it is determined whether a mutation is performed or not according to a mutation rate preset for each branch. The mutation for each branch may be lower for the branch located to the left, such as 0.1, 0.1, 0.3, 0.3, 0.5, similar to crossover .
[0077]
Next, the mutation is performed only in the branch that has been determined to be mutated.
Although various methods can be considered for the mutation, a method of adding a small value α to the value of one component randomly selected from within the branch may be used. Here, it is assumed that α is randomly selected from, for example, {+3, +2, +1, −1, −2, −3} each time a mutation is performed. However, in this case, in the case where the area that can be arranged is protruded by, for example, +3, the value is selected again from other values.
[0078]
Here is an example in which mutations have occurred in the third and fifth branches from the left of child 1 (for the third branch, -2 is added to the first component, and for the fifth branch, +1 is added to the fourth component).
[0079]
About child 1,

It is.
[0080]
The mutation rate may be set so that an initial value is given, the value is gradually reduced every generation, and the value is close to 0 in the final generation.
Steps B5 to B7, that is, selection, crossover, and mutation are repeated until the same number of children as the number of solution candidates are generated. Then, the child group is set as a new generation solution candidate group (step B8).
[0081]
The above-described processing loop of generating a new generation solution candidate group (a loop of a predetermined number of steps B5 to B7), compacting the solution candidate group (step B2), and evaluating the fitness (step B3) is repeated. It is converged to a better solution candidate.
[0082]
Then, when the number of processing loops reaches the number set in step A2 in FIG. 3, the process exits the processing loop and proceeds to step B9 (step B4).
In step B9, the optimal solution selecting unit 35 selects a solution candidate having the highest fitness, that is, the lowest cost, from the solution candidates of the final generation as the best solution, and outputs data related to the solution candidate.
[0083]
In the above operation, after step B4 in FIG. 6, the fitness may be scaled before control is transferred from step B8 to step B5. Scaling is scaling up or down the determined fitness by some function. As scaling,
f '= af + b
Linear scaling may be used, or
f '= f^k
Power scaling may be used.
[0084]
In the first embodiment, the partial circuit data extracting unit 20 extracts data relating to all m branches included in the target partial circuit to be placed each time, and sends the data to the element placement unit 30. As described above, the element placement unit 30 superimposes the data related to the branch included in the partial circuit to be placed at that time with the partial circuit to be placed next time. Necessary data related to (mn) branches is held, and the partial circuit data extraction unit 20 associates the n new branches with the n additional branches to be added to the next target partial circuit to be placed. Only the data to be processed may be extracted and provided to the element placement unit 30.
[0085]
As described above, according to the first embodiment, elements are arranged while scanning the entire circuit with a partial circuit to be arranged with a superimposed portion. Thus, for example, when the area occupied by the arranged elements is used for a cost function, it is possible to realize a high-density element area. Further, according to the present invention, an automatic element arrangement of a partial circuit to be arranged uses an arrangement method based on a genetic algorithm utilizing characteristics of branches, so that efficient element arrangement is possible.
[0086]
Hereinafter, a second embodiment will be described with reference to the drawings.
In the second embodiment, since the device configuration and an example of a circuit to be applied are the same as those in the first embodiment, the drawings and detailed description are omitted.
[0087]
The detailed operation procedure of the second embodiment will be described with reference to the flowcharts of FIGS. Here, the same operations as those in FIG. 3 and FIG.
[0088]
Data relating to a circuit diagram to be placed, such as element size and type, netlist, branch information, and the like, are read from the input unit 10 (step A1).
Through the input unit 10, the user can place an element shown as an outer frame in FIG. 9 showing an example of an automatic placement result of the circuit diagram of FIG. 2 implemented using the LSI element placement system according to the present invention. For the height and details of the region 60, parameters a, b, and n, which will be described later, or parameters related to the element placement unit 30 are set (step A2).
The initial solution candidate group generation unit 31 creates an initial generation solution candidate group (step B1). An example of the solution candidate group generated in the second embodiment is shown below.

As in the first embodiment, one solution candidate includes 25 elements included in the partial circuit to be arranged (in the second embodiment, the entire circuit of FIG. 2 is described as one partial circuit). , Respectively, and from the left side of the sequence, R1, Q1, R2, Q2, R3, R4, Q3, R5,... Here, it is generally effective to use a value of 30 to 100 as the number n of solution candidates in each generation. In the second embodiment, the description will be made on the assumption that n = 50.
[0089]
The X coordinate determination unit 32 determines the X coordinate of each element that has not been determined in step B1 (step B2).
The fitness evaluation unit 33 evaluates the cost of each solution candidate according to a predetermined cost function (Step C1). Several types of cost functions are defined, and each is evaluated.
[0090]
The cost is the evaluation value of each solution candidate, and in the second embodiment, the description will be made on the assumption that the smaller the evaluation value, the better the solution candidate. Here, as examples of costs, costs related to the adjacency of elements (hereinafter, referred to as “pair costs”), costs related to the layout area, costs related to the virtual wiring length, and costs related to the vertical relationship of the elements in the branch (hereinafter, “order”) This is described using four types of costs.
[0091]
The pair cost is calculated based on the constraint condition regarding the adjacency of the elements input in step A2. The constraints on the adjacency of elements are, for example,
1. The element R2 and the element R4 are arranged as adjacent as possible.
2. The element Q8 and the element Q9 are arranged as adjacent as possible.
In such a condition, an arrangement allowable range is set in advance for two elements to be preferentially adjacent to each other, and, for example, an area of a portion outside the allowable range is set as a cost related to the two elements. Then, the costs relating to all the two elements to be preferentially adjacent to each other are calculated to obtain the sum, and that value is used as the cost.
[0092]
The cost related to the layout area is the same as in the first embodiment.
The cost related to the virtual wiring length is, for example, for each net, １ ／ of the circumference of the smallest rectangle including all the terminals related to the net (however, when the minimum figure including all the related terminals is one line segment) Is its length), and its sum is the cost for all nets.
[0093]
The order cost is used to preserve the vertical relationship of the elements in the branch as much as possible. For example, when the magnitude relationship of the y-coordinates of the reference points of two vertically adjacent elements on the same branch is reversed, the order cost is shifted. Is the cost.
[0094]
The costs calculated by the cost function are ranked according to their importance, and the ranking is used in a selection operation described later. Here, it is assumed that the cost related to the layout area (cost 1), the cost related to the virtual wiring length (cost 2), the pair cost, and the order cost (cost 3) are in order of importance. It is assumed that pair costs and order costs are equally important.
[0095]
The selecting unit 36 performs a selecting operation on the solution candidate group using a probability based on the cost of each solution candidate (step C2). The selection operation will be described with reference to FIG.
[0096]
A set A consisting of a solution candidates is generated using the most important cost 1, that is, the cost related to the layout area (step D1). In this case, a> n, and here, a = 70.
[0097]
First, the fitness is calculated for each solution candidate using the cost 1 of the solution candidate. For the fitness, for example, the fitness f (w) of the solution candidate w is
f (w) = (the maximum value among the costs 1 of all solution candidates of the current generation) − (cost 1 of solution candidate w)
May be defined as follows.
[0098]
After the fitness is calculated for all n solution candidates, the probability of selecting each solution candidate is determined based on the fitness. For example, the selection probability P (w) of the solution candidate w is
P (w) = f (w) / (sum of all f)
May be given by
[0099]
Next, a solution candidates are selected from the n solution candidates using the selection probability P (w) of the solution candidate w. In this case, since the number a of elements in the set A is larger than the number n of elements in the original set of solution candidates, the set A always includes duplicate solution candidates.
[0100]
As for this selection method, a solution candidate may be selected by the same method as the selection method described in the first embodiment. Then, a random number is generated a times, and a set A including a corresponding solution candidates is generated.
[0101]
A similar operation is performed using the second most important cost 2, that is, the cost related to the virtual wiring length, to generate a set B including b solution candidates from a set A including a solution candidates (step). D2). Here, b <a and b> n, and in this case, b = 60.
[0102]
The same operation is performed using the cost 3, that is, the pair cost and the order cost. When there are several types of costs having the same degree of importance as described above, each cost is converted into a real value of, for example, 0 or more and 1 or less, and the sum is considered as cost 3, and the fitness is defined. Based on the selection probability based on the fitness, a set C including n solution candidates is generated from a set B including b solution candidates, and the selection operation is completed (step D3). Then, the set C including the n solution candidates is set as a parent set Z for the next crossover operation.
[0103]
Here, the crossover operation has been described using the costs 1 to 3 described above, but if there are two types of costs, step D2 may be omitted.
When there are four or more types of costs having different importance, a step corresponding to step D2 may be appropriately inserted. At this time, the above-mentioned operations are performed in order from the one having the highest importance. In this case, the number U (s) of solution candidates selected using the s-th most significant cost s is:
U (1)> ... U (s-1)> U (s)> U (s + 1) ...> n
What is necessary is to satisfy the relationship.
[0104]
Also, a plurality of costs for which relative weighting can be easily performed in advance may be regarded as one cost. For example, for a problem (arrangement target) that can be given so that the relative weight between the pair cost and the order cost is 4: 3, first, each cost is converted into a real value of 0 or more and 1 or less. The sum of four times the converted pair cost and three times the converted order cost may be regarded as one cost.
[0105]
The crossover unit 37 crosses the n parents, that is, the solution candidates included in the set Z generated by the selection operation, to exchange their components with each other, and generates n children as new solution candidates ( Step B6).
[0106]
First, n / 2 pairs are generated by grouping two parents included in the set Z. At this time, which parents are paired is arbitrary or random. These parent pairs
(Parent 1, parent 2), (parent 3, parent 4), ..., (parent n-1, parent n)
Expressed by In the second embodiment, since n = 50, 25 parent pairs, that is,
(Parent 1, parent 2) ... (parent 49, parent 50)
Is generated.
[0107]
Next, as in the first embodiment, a crossover operation is performed on each parent pair based on a preset crossover rate.
As described above, two children are generated from each parent pair, and a total of n children are generated. In the second embodiment, children 1 to 50 are generated.
[0108]
The mutation unit 38 performs a mutation operation on the n children generated by the crossover, as in the first embodiment (step B7).
It is determined whether the number of repetitions of a processing loop including a series of operations from step B2 to step B7 has reached a predetermined number. If not, the process proceeds to compaction in step B2 and the processing loop is repeated. The process moves to the end process of step C3 (step B4).
[0109]
A new solution candidate group is generated each time the processing loop makes a round, a better solution candidate is searched for, and the solution solution converges to an optimal solution or an approximate optimal solution.
A termination process is performed (step C3). Specifically, the same operation as the operation from step B2 to step C2 is performed, and a solution candidate having the minimum cost is selected as a solution from n solution candidates obtained by the selection operation.
[0110]
The output unit 50 outputs the contents of the arrangement result file to a predetermined device (Step A10).
As described above, according to the second embodiment of the present invention, a genetic algorithm is adopted as an optimization method, and a cost function is applied in an order according to its importance when selecting a solution candidate in each generation. Accordingly, since a method of sifting and narrowing down solution candidates is used, it is possible to efficiently obtain an optimal or approximate optimal solution for all cost functions.
[0111]
FIG. 9 shows an example of an automatic placement result of the circuit diagram of FIG. 2 implemented using the LSI element placement system according to the present invention.
Hereinafter, a third embodiment will be described with reference to the drawings.
[0112]
In the third embodiment, the device configuration and an example of a circuit to be applied are the same as those in the first embodiment, and thus the drawings and detailed description are omitted.
FIG. 10 is a flowchart showing a schematic operation of the third embodiment of the present invention, and FIG. 11 is a flowchart showing an outline of the genetic algorithm in the flowchart of FIG. 10. Basically, the same operation as FIG. Show. FIG. 12 is a diagram showing one arrangement result for the circuit diagram of FIG. 2 using the flowchart of FIG.
[0113]
Hereinafter, the schematic operation of the third embodiment will be described with reference to FIGS.
Data on a circuit diagram to be placed, such as element size and type, netlist, branch information, etc., parameters related to the element placement unit 30, and termination conditions used in step E5 are input (step E1). In this embodiment, the termination condition is, as shown in step E3, whether or not the total number of generations of the genetic algorithm for an arbitrary partial circuit to be arranged is equal to or less than the total number of generations k.
[0114]
The entire circuit diagram is divided into partial circuits to be arranged, each of which includes a plurality of branches (step E2). In the following description, for the sake of simplicity, it is assumed that all of the partial circuits to be arranged include three branches. Therefore, in the circuit of FIG. 2, three branches (R1, Q1, R2, Q2, R3), (R4, Q3, R5), (R6, Q4, R7), (R8, Q5, R9, Q6), (R10 , Q7, Q8, R11) and (Q9, R12) and three branches starting from (R13, Q10, R14, Q11). Without loss of generality, the third partial circuit to be placed is assumed to have three branches, assuming that the circuit continues on the right side of (R13, Q10, R14, Q11). The partial circuit to be arranged at the rightmost end may be composed of one or two branches, but it is not essential to describe such an exceptional case, so that it is omitted here.
[0115]
The genetic algorithm is activated for each of the partial circuits to be arranged divided as described above, and the arrangement is improved according to the schematic flowchart of FIG. 11 (step E3). The genetic algorithm in step E3 has the same number as the total number (q) of partial circuits to be arranged, and is executed in parallel by separate processors. Note that each genetic algorithm performs generation alternation by a predetermined number j. Here, j = 10. A specific description of the processing of the genetic algorithm shown in FIG. 11 will be described later.
[0116]
The third embodiment is an embodiment in which the information of the arrangement result of the adjacent partial circuit is referred to, for example, every j = 10 generations while each genetic algorithm is executed separately. This aims to consider the performance of the arrangement of the entire circuit. That is,
(I) Execute the genetic algorithm j = 10 generations for each partial circuit (step E3).
(Ii) The last generation for each subcircuit (ie, 10x_i  The best allocation result of the generation (i = 1, 2,...) Is copied to the shared memory (step E4). Here, copying is an operation of overwriting previous data with new data.
The above steps E3 and E4 are repeated until the last generation becomes the total generation (step E5). That is, in step E5, it is determined whether or not the last generation is less than or equal to the total number of generations k. If it is less than or equal to the total number of generations k, the process proceeds to step E3, otherwise the process proceeds to the output of step E6 (step E5). Here, it is assumed that k = j × 100 = 10 × 100 = 1000. That is, the loop from step E3 to step E5 is repeated 100 times in total.
[0117]
When the genetic algorithm of step E3 is executed as a process following step E5, the genetic algorithm for the i-th (2 ≦ i ≦ q) placement target partial circuit is copied to the shared memory (i−1). The information of the placement result of the second partial circuit to be placed is referred to.
[0118]
If the determination in step E5 is NO, the best solution for each placement target partial circuit at that time, that is, information on the placement result for each placement target partial circuit that was last copied to the shared memory is output (step S5). E6). This determines the final layout coordinates for all elements of the circuit.
[0119]
The genetic algorithm of step E3 will be described according to the schematic flow of FIG. In the following description, a detailed description of the same operation contents as in the first embodiment will be omitted.
[0120]
Step E3 is characterized by the total number q of the partial circuits to be placed determined in step E2, and each is executed in parallel in the third embodiment according to the schematic flow of FIG.
[0121]
As in the first embodiment, an initial generation consisting of a plurality of solution candidates in which the y-coordinates are arranged is generated in accordance with the arrangement order of the elements for each branch belonging to the partial circuit to be arranged (step B1).
[0122]
The generation of the initial generation in step B1 is necessary only when the processing of step E3 is applied for the first time, and is not used in the processing loop of steps E3 to E5 after the first time.
[0123]
The same compaction as in the first embodiment is performed for each solution candidate to determine the x coordinate (step B2). In this case, in the third embodiment, a condition is added that compaction of a branch belonging to the first partial circuit to be placed must not exceed the left edge of the placement area as shown in FIG. For the compaction of the branches of the partial circuits to be placed after the second, when the processing of step E3 is applied for the first time, the same conditions as those for the first partial circuit to be placed are added. After the process, if the process of step E3 is applied again, the placement result of the left-side placement target partial circuit copied to the shared memory, that is, the (i−1) -th placement target partial circuit is compared with the placement result. The element is packed by compaction.
[0124]
According to the fitness function defined from the predetermined cost function, the fitness of each solution candidate is calculated in the same manner as in the first embodiment or the second embodiment (step B3). In the third embodiment, the cost relating to the virtual wiring length, the cost relating to the layout area, the order cost, the pair cost, and the like are summed up by, for example, weighting each cost, and the sum thereof is set as the cost of the solution candidate.
[0125]
The smaller the cost, the better. For example, the fitness f (w) of the solution candidate w is
f (w) = (maximum value of the costs of all solution candidates of the current generation) − (cost of solution candidate w)
Is defined as In the cost calculation for the i-th (i ≧ 2) placement target partial circuit, the cost due to the connection relationship between the i-th and (i−1) -th placement target partial circuit is also taken into consideration. For example, regarding the virtual wiring length, the length of the net connecting the i-th and (i-1) -th placement target partial circuits is also added. The information of the placement result of the (i-1) -th placement target partial circuit referred to here uses the information copied to the shared memory.
[0126]
Hereinafter, steps B5 to B8 are repeated to generate a new solution candidate group. According to the selection probability determined based on the fitness calculated in step B3, two solution candidates to be crossed are selected from all solution candidates (step B5).
[0127]
Crossover is performed on the parent 1 and parent 2 selected in step B5 based on a preset crossover rate to generate two children. These children are designated as child 1 and child 2 (step B6).
[0128]
The child 1 and the child 2 generated in step B6 are mutated based on a preset mutation rate (step B7).
Steps B5 to B7, that is, selection, crossover, and mutation are repeated until the same number of children as the number of solution candidates are generated (step B8). The group of offspring is defined as a new generation solution candidate group.
[0129]
Steps B3, B5, B6, and B7 may be replaced with steps C1, C2, B6, and B7 of the second embodiment, and the determination operation of step B4 may be located after the selection operation.
[0130]
The processing loop (generation) of generation of the new generation solution candidate group, compaction of the solution candidate group, and evaluation of the fitness is repeated j times to converge to a better solution candidate. The total number of generations for the i-th placement target partial circuit that is currently targeted, that is, the total number of processing loops since the processing in step E3 is first applied to the i-th placement target partial circuit is the above-mentioned designation. If the number reaches a multiple of the number j, that is, any of j, 2j, 3j,..., 100j, the process exits the processing loop and proceeds to the process of step B9. At step B4, a determination for that is made.
[0131]
In step B9, the solution candidate with the highest fitness, that is, the lowest cost in the last generation of the j processing loops up to that point is set as the best solution, and data on the solution candidate is output.
[0132]
The genetic algorithm of the above step E3 is executed in parallel for all the partial circuits to be arranged.
As described above, according to the third embodiment, the entire circuit is divided into partial circuits to be arranged, each of which includes a plurality of branches. By also referring to the information of the placement result of the best solution for each of the predetermined number of generations j of the partial circuits, each placement target of each placement target is considered while considering the relative relationship between the adjacent placement target partial circuits. Since the genetic algorithm is applied in parallel to the element arrangement of the partial circuit, a high-quality arrangement result considering the entire circuit can be obtained at high speed.
[0133]
Hereinafter, a fourth embodiment will be described with reference to the drawings.
In the fourth embodiment, the configuration of the device and an example of a circuit to be applied are the same as those in the first embodiment, and thus the drawings and detailed description are omitted.
[0134]
FIG. 13 is a flowchart showing the operation of the fourth embodiment of the present invention, FIG. 14 is a flowchart showing an outline of the adjustment of the y coordinate in the flowchart of FIG. 13, and FIG. 15 is a flowchart using the flowchart of FIG. 3 is a diagram showing an example of one arrangement result with respect to the circuit diagram of FIG.
[0135]
The operation of the fourth embodiment will be described with reference to FIGS. In FIG. 13, the same operations as those in FIGS. 3 and 6 are denoted by the same reference numerals, and the detailed description will be omitted.
As with the first embodiment, data on a circuit diagram to be placed, parameters relating to the element placement unit 30, parameters used in step F, and the like, such as element size and type, net list, branch information, etc., are input from the input unit 10 as in the first embodiment. Read (step A1).
[0136]
As in the first embodiment, for each branch belonging to the circuit diagram to be arranged, an initial generation including a plurality of solution candidates in which the y-coordinates are arranged and expressed in accordance with the arrangement order of the elements is generated (step B1).
[0137]
As in the first embodiment, compaction is performed for each solution candidate to determine the x coordinate (step B2).
According to the fitness function defined from the predetermined cost function, the fitness for each solution candidate is calculated as in the first embodiment (step B3). The cost function is the same as in the first to third embodiments.
[0138]
Hereinafter, steps B5 to B8 are repeated to generate a new solution candidate group. Steps B5 to B8 (except for step F) are the same as those in the first embodiment, and a detailed description thereof will be omitted.
[0139]
According to the selection probability determined based on the fitness calculated in step B3, two solution candidates (parent 1 and parent 2) to be crossed are selected from all solution candidates (step B5).
[0140]
The parent 1 and the parent 2 selected in step B5 are crossed in accordance with a preset crossover rate to generate children 1 and 2 (step B6).
The child 1 and the child 2 generated in Step B6 are mutated according to a mutation rate specified in advance, and a child 1 'and a child 2' are generated (Step B7).
[0141]
For each of the child 1 'and the child 2' generated in step B7, according to a predetermined probability δ, a pair of elements whose y coordinates are close to each other in an adjacent branch is searched. If there is, the operation of setting the y coordinate of the two elements to the same value (adjusting the y coordinate) is performed (step F).
[0142]
Steps B5 to F, ie, selection, crossover, mutation, and y coordinate adjustment are repeated until the same number of children as the number of solution candidates are generated (step B8). The group of offspring is a new generation solution candidate group.
[0143]
The processing loop (generation) of generation of the new generation solution candidate group, compaction of this solution candidate group, and calculation of the fitness thereof is repeated by a preset number of generations, and converges to a better solution candidate. Here, as a condition for exiting this processing loop, a condition that “all individuals have the same fitness” may be added in addition to the condition “when the number of generations reaches a preset number”.
[0144]
The information of the arrangement result of the best solution in the last generation, that is, the arrangement coordinates of each element is output (step B9).
Hereinafter, the adjustment of the y coordinate in step F will be specifically described with reference to FIG.
[0145]
The value of the parameter i used as the number of loops is set to 1 (step F1).
A real random number r of 0 or more and 1 or less is generated (step F2).
If r is smaller than the probability δ relating to the y-coordinate adjustment specified in advance, the process proceeds to step F4; otherwise, the process proceeds to step F6 (step F3). In this case, for example, if r = 0.4 and δ = 0.7, the process proceeds to step F4. The value of δ may be a constant over the entire generation of the genetic algorithm of FIG. 13 or may be dynamically changed, for example, it is gradually increased with each generation. When the number is increased, generally, the degree of alignment in the x direction increases toward the latter generation.
[0146]
The code of the i-th branch and the code of the (i + 1) -th branch are compared, and a pair y (i, k) and y (i + 1, h) whose absolute value of the difference between the y coordinates is 1 or more and p or less is searched for. When there are a plurality of sets, one set is selected at random (step F4).
[0147]
Here, y (j, m) is a symbol meaning the m-th element of the j-th branch. The value of p reflects the degree of proximity of the y coordinate, and in the present embodiment, p = 2 will be described. That is,
| Y (i, k) -y (i + 1, h) | = 1 or = 2
If, the k-th element in the i-th branch and the h-th element in the (i + 1) -th branch are determined to be close to each other.
[0148]
For example, when i = 1, the code of the first branch in child 1 'is
0 10 15 27 37
And the code on the second branch is
0 26 30
, When comparing the codes of the first and second branches, | y (1,4) −y (2,2) | = | 27−26 | = 1, so that It can be seen that the fourth element is close to the second element of the second branch.
[0149]
The method of searching for the adjacent pairs y (i, k) and y (i + 1, h) as described above is performed by, for example, the element y (i, a) of the i-th branch and the element y (i + 1) of the (i + 1) -th branch. , B) is randomly selected, and the operation of checking whether the absolute value of the difference between these two elements is not less than 1 and not more than p is repeated, for example, at most 10 times. If there is one that satisfies the condition, a method of adopting the pair as a close pair may be adopted. Alternatively, a method of checking all conceivable pairs and selecting one pair that satisfies the condition may be adopted although the check time increases.
[0150]
If the adjacent pairs y (i, k) and y (i + 1, h) are found in step F4, one of them is copied (overwritten) to the other (step F5). That is,
(A) copy the value of y (i, k) to y (i + 1, h), or
(B) Copy the value of y (i + 1, h) to y (i, k).
Which of (a) and (b) is executed is random. For example, when (a) is executed on the pair y (1,4) and y (2,2) used in the description of step F4, the code of the second branch of the child 1 'becomes
0 27 30
The fourth element of the first branch and the second element of the second branch are adjacent to each other in the sense that their reference points are located on the same horizontal line (y = 27). Will fit.
[0151]
As described above, it is assumed that the y-coordinate values of the two elements subjected to the y-coordinate adjustment are not changed again until the processing exits the loop of steps F2 to F7. Therefore, as an exception to the above selections (a) and (b), if y (i, k) is not allowed to change the value, (a) will be selected.
[0152]
As described above, the y-coordinate of the two elements once subjected to the y-coordinate adjustment is not changed again while i is less than the total number of branches, so that, for example, the code of the adjacent branch is
0 25 40; 0 26 36; 526
In the case of, useless operation of first adjusting the second value of the second branch "when i = 1" to 25 and then returning the value to "26 when i = 2" is avoided. Will be. For example, the code of the branch changes as follows.
0 25 40; 0 26 36; 5 26 (i = 1; execute (a))
→ 0 25 40; 0 25 36; 526 (i = 2; execute (b))
→ 0 25 40; 0 26 36; 526
If no adjacent pair is found in step F4, nothing is executed in step F5.
[0153]
One is added to the value of the parameter i (step F6).
The above operations of steps F2 to F6 are repeated (total number of branches -1) times (step F7). In the example of FIG. 2, 7-1 = 6 repetitions.
[0154]
In the method described in FIG. 14, the y-coordinate adjustment is sequentially performed from the left side of the branch by increasing the parameter i by one from the initial value 1. On the contrary, the initial value of i is set to ( A method of sequentially performing y-coordinate adjustment from the right side of the branch by reducing the number by 1 as the total number-1) may be used. Furthermore, a method of randomly selecting “the total number of branches × δ” i values of 1 or more and (total number of branches−1) or less, and performing the operations of step F4 and step F5 may be used.
[0155]
As described above, according to the fourth embodiment, when applying a genetic algorithm that takes advantage of the characteristics of a branch, by adjusting the y coordinate as one of the genetic operations, Since the element pairs that reduce the area and increase the ease of wiring gradually align in the x direction, it is necessary to efficiently obtain high-quality placement results with excellent alignment in the x direction. Becomes possible.
[0156]
The invention is not limited to the embodiments described above.
In the embodiment, the case of arranging the elements in order from the branch on the left side has been described. However, of course, the present invention can be similarly applied to the case of arranging the elements from the right side, and the same effects can be obtained.
[0157]
In FIG. 7, the judgment operation in step B4 is moved between the selection operation in step C2 and the crossover operation in step B6, and the end process in step C3 is set as the best solution selection process. Even if it is increased by 1, an equivalent flowchart is obtained.
[0158]
The genetic algorithm methods used in FIGS. 6, 7, 11 and 13 are very basic, and various other genetic algorithm methods are applicable. For example, it is possible to incorporate various techniques such as an elite strategy that leaves the best solution of the previous generation unconditionally in the next generation, scaling and expectation strategy to prevent falling into a local solution in the early generation. is there. In the first to fourth embodiments, when a new generation is generated, the same number (50) of children as the parent are generated from the number of parents (for example, 50), and a group of obtained children is obtained as a solution of the new generation. A candidate group is used. Instead of this method, for example, 20 children are generated and added to the parent group, and 50 individuals are selected in descending order of fitness from a group consisting of 70 solution candidates obtained. Of course, they may be used as a new generation solution candidate group.
[0159]
Further, the above embodiments have been described individually, but are not limited thereto. For example, the first and second embodiments, the first and second embodiments, the fourth embodiment, the third embodiment, and the like. The fourth embodiment, or the first and fourth embodiments can be freely combined and applied. In addition, a combination of the second embodiment and the third embodiment, or a combination of the second embodiment and the third and fourth embodiments is also possible.
Furthermore, the present invention is not limited to the above-described embodiments, and can be implemented with various modifications without departing from the scope of the invention.
[0160]
【The invention's effect】
According to the present invention, the following effects can be obtained.
According to the method and the device for arranging elements of an LSI according to the first aspect of the present invention, the number of sub-circuits less than m is determined for the partial circuit to be arranged composed of a predetermined number (for example, m) of branches. The elements are arranged with overlapping portions of (for example, (mn) branches). Therefore, according to the method and apparatus for arranging elements of an LSI according to the first aspect of the present invention, local optimization is continuously performed, so that element arranging in consideration of the entire circuit is possible. Combined with the element placement method using a genetic algorithm that takes advantage of, for example, when the area occupied by the placed elements is used for a cost function, the element area is increased in density, and a high-quality element placement result is obtained. It can be obtained efficiently.
[0161]
According to the above-described LSI element placement method and apparatus, when a genetic algorithm is adopted as an optimization method and a solution candidate in each generation is selected after the cost of each solution candidate has been evaluated, a cost function is selected. By applying the solutions in order according to their importance, the solution candidates are sieved and narrowed down, so that optimal or approximate optimal solutions can be efficiently obtained for all cost functions.
[0163]
Of the present invention2nd phaseAccording to the method and apparatus for arranging elements of an LSI according to the present invention, when applying a genetic algorithm taking advantage of the characteristics of a branch in the automatic arrangement of elements in an LSI, one of the genetic operations is performed as one of the genetic operations. For a code (chromosome), according to a predetermined probability, a pair of elements whose y coordinates are close to each other in an adjacent branch is searched, and if there is such a pair, the y coordinates of the two elements are determined to be the same. Perform the operation of setting the value. By this operation, the element pairs that are adjacent to each other and contribute to the reduction of the area and the ease of wiring are gradually aligned in the x direction, and finally the alignment in the x direction is improved. It is possible to efficiently obtain an excellent quality placement result.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of an LSI element placement device according to a first embodiment of the present invention.
FIG. 2 is an example of a circuit diagram to which an LSI element placement device according to the present invention is applied.
FIG. 3 is a flowchart showing an operation of the element arrangement device shown in FIG. 1;
FIG. 4 is an example of an automatic arrangement result of the circuit diagram of FIG. 2 implemented using the LSI element arrangement apparatus according to the present invention.
FIG. 5 is a diagram showing a schematic configuration of an element arrangement unit 30.
FIG. 6 is a flowchart showing in detail the operation of an element arrangement unit of the LSI element arrangement apparatus shown in FIG.
FIG. 7 is a flowchart showing the operation of the LSI device placement apparatus according to the second embodiment of the present invention.
FIG. 8 is a flowchart showing the operation of the selection means of the second embodiment.
FIG. 9 is an example of a result of automatic placement of the circuit diagram of FIG. 2 performed using the LSI element placement apparatus according to the present invention.
FIG. 10 is a flowchart showing processing steps according to a third embodiment of the present invention.
FIG. 11 is a flowchart showing an outline of a genetic algorithm in the flowchart of FIG. 10;
FIG. 12 is a diagram showing one arrangement result for the circuit diagram of FIG. 2 using the flowchart of FIG. 10;
FIG. 13 is a flowchart showing processing steps according to a fourth embodiment of the present invention.
FIG. 14 is a flowchart showing an outline of adjustment of ay coordinate in the flowchart of FIG. 13;
15 shows one arrangement result for the circuit diagram of FIG. 2 using the flowchart of FIG. 13;
[Explanation of symbols]
10 input unit, 20 partial circuit data extraction unit, 30 element placement unit,
31: initial solution candidate group generation unit, 32: X coordinate determination unit, 33: fitness evaluation unit
34: solution candidate group updating unit, 35: (approximate) optimal solution selecting unit, 36: selecting unit,
37 crossover part, 38 mutation part, 40 arrangement result file creation part,
50 ... output unit.

Claims (15)

In an LSI element placement device for arranging elements according to the order of branches composed of element rows included in a circuit diagram,
Partial circuit data extraction means for sequentially extracting a partial circuit including data of a predetermined number of branches included in the circuit diagram from a predetermined end side of the circuit diagram,
While performing an element arrangement operation using a genetic algorithm on the data of the branch extracted by the partial circuit data extraction means, the arrangement coordinates of the branches are determined by calculation to determine the arrangement of the branches having fewer branches than the branches included in the partial circuit. Element arrangement means for sequentially recording data to generate an element arrangement result including arrangement coordinate data of all elements included in the data of the branch,
An LSI element placement device, wherein the partial circuit data extracting means extracts a partial circuit including a branch whose placement has not been determined by the element placing means when reading out the second and subsequent partial circuits. 2. The LSI element arrangement apparatus according to claim 1, further comprising an arrangement result file creating means for creating an arrangement result file based on said element arrangement result by said element arrangement means. Further comprising setting means for presetting a predetermined first positive integer m and a second positive integer n smaller than the first positive integer,
When extracting the branch data first, the partial circuit data extracting means continuously extracts m pieces of the branch data from the end of the circuit diagram. Means for continuously extracting data of m branches including the data of the branch extracted from the end portion except for n branches from the data of the branch extracted immediately before; and, in the final extraction, the data of the branch. Is less than m, means for extracting all data,
The arrangement result file creating unit may include, among the data of the branches included in the element arrangement result generated by the element arrangement unit, the elements included in the data of the n consecutive branches closest to the end. The apparatus includes means for recording only the relevant element arrangement result, and the last time includes means for recording the element arrangement result relating to all the elements included in the element arrangement result generated by the element arrangement means. 3. The LSI element arrangement device according to claim 2, wherein Further comprising setting means for presetting a predetermined first positive integer m and a second positive integer n smaller than the first positive integer,
When extracting the branch data first, the partial circuit data extracting means continuously extracts m pieces of the branch data from the end of the circuit diagram. Means for extracting data of the next n branches on the end side of the data of the branch extracted immediately before, and, if the number of branches is less than n in the last extraction, all data Means for extracting
The arrangement result file creating unit may include, among the data of the branches included in the element arrangement result generated by the element arrangement unit, the elements included in the data of the n consecutive branches closest to the end. The apparatus includes means for recording only the relevant element arrangement result, and the last time includes means for recording the element arrangement result relating to all the elements included in the element arrangement result generated by the element arrangement means. 3. The LSI element arrangement device according to claim 2, wherein The element arranging unit includes a plurality of solution candidates including candidate values of predetermined first coordinates of all elements included in the branch data, using the data of the branch extracted by the partial circuit data extracting unit. Solution candidate group generating means for generating a solution candidate group; and a second coordinate of a second coordinate axis perpendicular to a first coordinate axis corresponding to the first coordinate of all elements related to the solution candidate group for each solution candidate. A second coordinate determining means, a fitness evaluation means for evaluating the fitness of the solution of each solution candidate for which the second coordinates have been determined, and a solution candidate having the best fitness from the solution candidate group. 5. The LSI element placement apparatus according to claim 1, further comprising an approximate optimum solution selection unit that outputs a result of element placement related to a branch included in the circuit diagram. The solution candidate group generation unit includes a selection unit that selects two solution candidates based on the solution candidate group whose fitness is evaluated and a fitness value related to the solution candidate group. 6. The LSI according to claim 5, further comprising crossover means for exchanging a predetermined number of components with each other, and mutation means for performing a predetermined arithmetic operation on a predetermined number of components of said exchanged solution candidates. Element placement device. The solution candidate group generating means may include, among the data of the branch extracted by the partial circuit data extracting means, a branch overlapping with an element related to the data of the branch on which the previous element placement operation has been performed. 6. The LSI element placement apparatus according to claim 5, further comprising means for generating the solution candidate group by inheriting a value of the first coordinate of an element related to data as it is. The element arranging unit includes a plurality of solution candidates including candidate values of predetermined first coordinates of all elements included in the branch data, using the data of the branch extracted by the partial circuit data extracting unit. Solution candidate group generating means for generating a solution candidate group; and a second coordinate of a second coordinate axis perpendicular to a first coordinate axis corresponding to the first coordinate of all elements related to the solution candidate group for each solution candidate. A second coordinate determining means for determining by a compaction operation, and, according to a predetermined probability, for each solution candidate of the solution candidate group, an element of which the first coordinates are close to each other among elements included in the adjacent branch. 4. The apparatus according to claim 1, further comprising: a search unit that searches for a pair, and an adjustment unit that adjusts a first coordinate value of the element to the same value when the pair of adjacent elements is found. LS described in 4 Element arrangement device. 9. The method according to claim 8, wherein the adjusting unit includes a unit that holds the adjusted first coordinate value until the first coordinate of a new solution candidate group is adjusted. An LSI element arrangement device as described in the above. The element arrangement means codes candidate values of the first coordinates corresponding to each element included in the partial circuit to be arranged in accordance with the order of the branches from the one end and the order of the elements in the branch. Means for setting a numerical sequence as the solution candidate,
The selecting means includes means for performing according to the probability determined for each solution candidate based on the fitness associated with the solution candidate,
The crossover means includes, for each branch, means for performing the branch in accordance with a crossover rate determined based on the order in which the branch is newly added to the partial circuit to be arranged by the partial circuit data extraction means to be arranged,
2. The LSI element placement apparatus according to claim 1, wherein said mutation means includes means for performing, for each branch, a mutation rate determined based on the order. The element arranging unit uses the data of the branch extracted by the extracting unit to include a plurality of first solution candidates including predetermined first coordinate candidate values of all elements included in the branch data. Initial solution candidate group generating means for generating one solution candidate group; and evaluating, for each of the first solution candidates, a plurality of costs including at least a first cost relating to an element arrangement area and a second cost relating to a positional relationship between elements. An evaluation means for calculating a selection probability from the first solution candidate group by a predetermined function based on a first cost for each of the first solution candidates, and selecting a plurality of second solution candidates larger than a predetermined number. A first generation unit configured to generate a second solution candidate group including the second solution candidate; and a predetermined function based on a second cost for each of the second solution candidates from the second solution candidate group. Calculate the selection probability and calculate the first solution candidate A second generation unit that selects a plurality of third solution candidates larger than the number of second solution candidates and generates a third solution candidate group including the third solution candidates; Means for repeating until the last solution candidate group is generated for all costs. A second coordinate determining unit configured to determine second coordinates of all elements related to the first solution candidate group by a compaction operation for each first solution candidate before execution of the evaluation unit; 3 After execution of the generating means, one-half solution candidate pairs of the number of solution candidates included in the last solution candidate group are selectively formed, and some of the solution candidate pairs forming each of the solution candidate pairs are selected. Crossover means for exchanging components of each other, a mutation means for performing a predetermined arithmetic operation on a predetermined component of each of the solution candidates subjected to the exchange to generate a new solution candidate group, and the mutation means 12. The LSI element placement apparatus according to claim 11, further comprising: means for repeating the mutation means from the second coordinate determination means a predetermined number of times for the new solution candidate group generated in the step (c). 13. The LSI according to claim 11, wherein the evaluation unit includes a unit that evaluates a cost further including a cost related to an element adjacency, a cost related to an element area, and a cost related to a virtual wiring length. Element placement device. 6. The LSI element placement apparatus according to claim 5, wherein said second coordinate determination means includes means for determining, by compaction operation, second coordinates of each element related to said solution candidate. 5. The apparatus according to claim 3, wherein said first positive integer m and said second positive integer n set by said setting means include means for setting as a locally fluctuating value. LSI device placement device.

Images