(57)【要約】  【課題】  ＥＭＩ対策用の容量素子を半導体集積回路のフロアの空き箇所に最適に配置できるようにする。  【解決手段】  半導体集積回路のフロアからＥＭＩ対策用の容量素子の配置可能な複数の空き箇所を抽出し、該抽出した複数の空き箇所について、前記容量素子を配置する／しないで区別する遺伝子を配列した遺伝子列からなる個体を得、前記遺伝子列が異なる複数の個体を作成し、遺伝的アルゴリズムを適用し各個体について所定の指標で表される適応度を評価して進化させ、最も適応度の高い個体を最適解として得、該最適解の個体の遺伝子列で表された空き箇所に前記容量素子を配置する。【選択図】  図２
2006268576.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路のフロアからＥＭＩ対策用の容量素子の配置可能な複数の空き箇所を抽出する第１ステップと、
該抽出した複数の空き箇所について、前記容量素子を配置する／しないで区別する遺伝子を配列した遺伝子列からなる個体を得る第２ステップと、
前記遺伝子列が異なる複数の個体を作成し、遺伝的アルゴリズムを適用し各個体について所定の指標で表される適応度を評価して進化させ、最も適応度の高い個体を最適解として得る第３ステップとを具備し、
該最適解の個体の遺伝子列で表された空き箇所に前記容量素子を配置することを特徴とする容量素子の配置方法。
【請求項２】
請求項１に記載の容量素子の配置方法において、
前記第３ステップにおける前記指標は、必要とされる合計容量値に対する充足率、配置する容量素子の分布／分散等であることを特徴とする容量素子の配置方法。
【請求項３】
請求項１又は２に記載の容量素子の配置方法において、
前記第１のステップは、前記配置可能な空き箇所に存在する既存の配線の変更に伴うコストも評価し、
前記第３のステップおける前記指標は、該コストも含むことを特徴とする容量素子の配置方法。
【請求項４】
前記半導体集積回路のフロアを、電源配線により複数の回路ブロックに分割した分割領域として、該各分割領域毎に請求項１、２又は３に記載の方法により、空き箇所に前記容量素子を配置することを特徴とする容量素子の配置方法。
【請求項５】
請求項４に記載の容量素子の配置方法において、
前記各分割領域毎に得た複数の前記個体について、異なる分割領域の個体間でその一部の遺伝子を移住させて進化させ、これを世代交代毎に繰り返し、チップ全体のバランスを考慮した最適解をもつ個体を前記各分割領域毎に得ることを特徴とする容量素子の配置方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＥＭＩ（Electro Magnetic Interference）対策用の容量素子を半導体集積回路のフロアの空き箇所に最適に配置する方法に関するものである。
【背景技術】
【０００２】
従来から、ＥＭＩによって半導体集積回路が誤動作することを防止するために、容量素子を配置することが提案されている。例えば、特許文献１には電源系パッドと内部回路の電源系配線との間にインピーダンス素子を接続する手法が提案されている。また、回路自身が発生するＥＭＩを抑制するために、回路コア内部に容量素子を配置する手法が特許文献２，３に記載されている。
【０００３】
コア内部にＥＭＩ対策用の容量素子を配置する際の配置時期は回路設計フロー中のセル配置ステップが想定されている。この場合、大別して、（１）各セルに対応した容量値の容量素子を各セルの近傍に配置する、（２）空いた場所（マクロセルや標準セルが配置されていない場所）に配置する、に分かれる。
【特許文献１】特開２００２−９３９９８号公報
【特許文献２】特開２０００−２７７６１８号公報
【特許文献３】特開２００１−１８５６２４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところが、（１）の手法は、チップサイズが変更されることがあり、また各セルについては最適値の容量を配置することになってもチップ全体としては過剰な容量を配置することになる場合、つまり部分最適は実現できるかもしれないが全体としては最適化されない恐れがあり、消費電力の増大を招く。
【０００５】
一方、（２）の手法は、空いた場所のうち、どこに、どれだけ配置するかの基準が示されていないので、過剰に配置することにより消費電力増大を招いたり、容量素子を必要とするセルや回路ブロックから過度に離れた箇所に配置することにより配線長の増加を招き電圧降下が生じたり、必要な場所ではなく空いた場所に配置するために回路全体でバランスの悪い配置となり局所的な電圧降下を招いたり、さらに配置配線工程終了後に容量素子を配置する場合には既存配線を再配置することになり遅延値が変更されるという問題がある。
【０００６】
本発明の目的は、ＥＭＩ対策用の容量素子を半導体集積回路のフロアの空き箇所に最適に配置できるようにして、上記した問題を解決した容量素子配置方法を提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明は、半導体集積回路のフロアからＥＭＩ対策用の容量素子の配置可能な複数の空き箇所を抽出する第１ステップと、該抽出した複数の空き箇所について、前記容量素子を配置する／しないで区別する遺伝子を配列した遺伝子列からなる個体を得る第２ステップと、前記遺伝子列が異なる複数の個体を作成し、遺伝的アルゴリズムを適用し各個体について所定の指標で表される適応度を評価して進化させ、最も適応度の高い個体を最適解として得る第３ステップとを具備し、該最適解の個体の遺伝子列で表された空き箇所に前記容量素子を配置することを特徴とする。
【０００８】
ここで、前記第３ステップにおける前記指標は、必要とされる合計容量値に対する充足率、配置する容量素子の分布／分散等であることが望ましい。
【０００９】
また、前記第１のステップは、前記配置可能な空き箇所に存在する既存の配線の変更に伴うコストも評価し、前記第３のステップおける前記指標は、該コストも含むことが望ましい。
【００１０】
また、前記半導体集積回路のフロアを、電源配線により複数の回路ブロックに分割した分割領域として、該各分割領域毎に請求項１、２又は３に記載の方法により、空き箇所に前記容量素子を配置することも望ましい。
【００１１】
さらに、前記各分割領域毎に得た複数の前記個体について、異なる分割領域の個体間でその一部の遺伝子を移住させて進化させ、これを世代交代毎に繰り返し、チップ全体のバランスを考慮した最適解をもつ個体を前記各分割領域毎に得ることも望ましい。
【発明の効果】
【００１２】
本発明によれば、半導体集積回路について、空いた箇所に容量素子を配置するのでチップサイズが変更されることはない。また、容量素子配置の最適解を得るための適応度を示す指標として合計容量値に対する充足率や配置する容量素子の分布／分散等を用いることにより、バランスのとれた容量素子配置の最適解を得ることができ、消費電力増大、部分的な電圧降下増大等を回避することができる。また、空き箇所に容量素子用の配線と同一配線層のメタルが既存配線として存在している場合には、そこに容量素子を配置しなければ遅延変更の問題は生ぜず、また配置する場合でも遅延変更を伴わないようにすれば、問題は生じない。さらに、半導体集積回路のフロアを複数の領域に分割して各分割領域について容量素子の最適な配置解を得るようにすれば、そのための処理時間を短縮できる。さらに、このようにして各分割領域について容量素子配置の最適解候補（評価上位の遺伝子列）を複数得ておけば、異なる分割領域に渡ってその一部の遺伝子を移住させて、世代交代毎にこれを繰り返すことにより、チップ全体のバランスを考慮したより高度の最適解を示す容量素子配置を得ることができる。このようなことから、時間に余裕がないときにＥＭＩ対策用容量素子を配置する場合に、極めて好適となる。
【発明を実施するための最良の形態】
【００１３】
本発明の実施例では、ＥＭＩ対策用の容量素子を下地（半導体基板上の拡散層）と第１層メタルＭ１（一番下面のメタル配線）との間で構成する。容量素子の誘電体としてはゲート酸化膜等を使用する。このとき、(a)その容量素子をチップサイズの変更を伴わずに配置するためには、コア内部の空き領域に配置する必要がある。また、(b)遅延を変更することなく配置するためには、第１層メタル配線Ｍ１が既に使用されていない空き領域を使用するか、あるいは遅延に影響しないように既存の第１層メタル配線を変更できる空き領域を使用する必要がある。なお、容量素子の過剰な配置と容量素子配置のバランスの悪さを解消するには、どれくらいの容量値の容量素子をどこの空き領域に配置するかという観点を考慮する必要がある。
【００１４】
以上から、本発明では、「半導体集積回路上の配置可能な空き箇所を抽出して、その箇所に容量素子を配置した場合と配置しなかった場合を所定の指標の適応値で評価し、容量素子配置の最適解を求める」ことにより、容量素子の配置を行う。
【００１５】
これは、ナップザック問題の変形であるといえる。ナップザック問題は、一定の容積をもったナップザックに複数個の荷物の中からいくつかを任意に選んで詰め込むとき、ナップザックの容積に最大限に詰め込める荷物の組合せを求めるものである。パラレルなＣＰＵへの計算量割り当て問題、金融ポートフォリオ／限られた資金量の中での最小リスク最大リターンを狙う組合せ等が良く知られている。
【００１６】
ただし、上記した容量素子の配置箇所と配置個数の組合せを総当たりで評価しようとすると計算爆発が起こるため、算出に時間がかかり実用的でない。例えば、配置箇所が３箇所の場合、配置する／しないの取り得る組合せは３であるから２3＝８通りである。同様に、配置可能な空き箇所がｎ箇所の場合は、取り得る組合せは２n通りとなる。組合せの１つの評価を１０ns（＝１００MHｚ）で行うとしても、例えばｎ＝８１のときは、２81＝１８０億年と莫大な時間がかかることになる。
【００１７】
そこで本実施例では、遺伝的アルゴリズム（Genetic Algorithm）を適用することにより、実用的な時間内で容量素子の最適な配置解もしくはそれに近い配置解を得る。
【００１８】
ＥＭＩの発生源は、回路全体というよりは、特定のマクロや特定の回路ブロックであることが多い。また、電源配線はチップの周囲のみに配線されるのではなく、電源供給が必要なマクロの周囲に配線されたり、特定の回路を複数の回路ブロックに分割するように配線されたりする。したがって、最初からチップ全体について容量素子配置の最適解を得るよりも、電源配線で分割される分割領域毎に容量素子配置の最適解を求め、その上でチップ全体について最適解を得る方が、最適解を得るための時間が少なくて済むことが予想される。このような観点から、本実施例では、以下のような手法により、容量素子配置の最適解を求める。
【実施例】
【００１９】
(I)．容量素子の配置可能な空き箇所の抽出
ここでは、半導体集積回路のフロアから容量素子の配置可能な空き箇所（他のセルのない領域）を抽出（Pick up)する。抽出したとき、既存の配線を変更する必要のある箇所については、そのコスト（マイナス点）も記録しておく。図１はこれを説明するための図であり、配置領域Ａ１〜Ａ６、配線領域Ｂ１〜Ｂ３を有するフロアについての例である。
【００２０】
図１(a)は、配置領域Ａ１、Ａ３，Ａ５、配線領域Ｂ１，Ｂ２に第２層メタルＭ２が配線されているときに、配置領域Ａ３を第１層メタルＭ１を使用した容量素子の配置箇所とて候補にあげた場合である。この場合は、配置領域Ａ３に容量素子をそのまま配置できるので、配線変更等のコストを払う必要がない。よって、この場合の配置領域Ａ３のコストは例えば「０」とする。
【００２１】
図１(b)は、配置領域Ａ１、Ａ３，Ａ５、配線領域Ｂ１，Ｂ２に第１層メタルＭ１が配線されているときに、配置領域Ａ３を第１層メタルＭ１を使用した容量素子の配置領域とて候補にあげた場合である。この場合は、ここに容量素子を配置するには配置領域Ａ３の既存の第１層メタルＭ１を別の例えば第２層メタルＭ２に変更するというレイアウト変更のコストを払う必要がある。このときは、既存の第１層メタルＭ１の配線を迂回させるほどではないので、そのコストは例えば「−２」とする。
【００２２】
図１(c)は、配置領域Ａ１、Ａ３，Ａ５、配線領域Ｂ１，Ｂ２に第１層メタルＭ１が配線されているときに、配置領域Ａ３を第１層メタルＭ１を使用した容量素子の配置領域とて候補にあげた場合であって、且つここに容量素子を配置するには配置領域Ａ３の既存の第１層メタルＭ１を第１層メタルＭ１以外の別の配線には変更できない場合である。この場合は、その既存の第１層メタルＭ１の配線を配置領域Ａ４に迂回させなければならないという大きなデメリットがあるので、そのコストは例えば「−１０」とする。
【００２３】
（II)．電源配線で分割された個々の領域毎に遺伝子を作成
ここでは、電源配線で分割された個々の分割領域毎に遺伝子を作成する。このとき、分割領域内の１ヶの容量の配置可能な空き箇所を１ビットとし、複数の空き箇所に応じた複数ビットによる遺伝子列を定義する。この遺伝子の長さ（総ビット数）は分割された領域内の容量素子の配置可能な空き箇所の最大数である。
【００２４】
（III)．各分割領域での遺伝子列の進化
ここでは、各分割領域における遺伝子を操作して進化を行わせる。分割領域内の容量素子の配置可能な空き箇所を遺伝子座フロアとして、容量素子を配置した遺伝子座フロアにはビットとして“１”をたて、配置しなかった遺伝子座フロアには“０”をたてた遺伝子列を作成する。たとえば、容量素子の配置可能な空き箇所が８個ある場合には、図３の上段のように遺伝子座フロアをａ〜ｈの８個とした８ビットの遺伝子列を作成して、これを１個の個体とする。この個体は当該分割領域において最終的に求めるべき容量素子の配列の１つの解に相当する。図３の親Ｐ１，Ｐ２，子Ｑ１〜Ｑ３はすべて個体である。
【００２５】
図２は遺伝子操作のフローチャートである。まず、初期集団を設定する（Ｓ１）。初期集団としては、遺伝子座フロアに任意に“１”又は“０”を立てた遺伝子列をもつ上記した個体の複数個を使用する。
【００２６】
次に、初期集団をなす複数の個体のそれぞれについて、その適応度を評価する（Ｓ２）。各遺伝子座フロアについては、図１で説明した手法によりコストを得ているので、このコストも使用して、各個体の適応度を評価する。適応度の算出には、そのほかに、必要とされる容量（合計値）に対する充足率（過不足を数値化したもの）、分割領域内における容量素子の分布／分散度等も考慮する。
【００２７】
次に、淘汰（Ｓ３）の処理を行う。この淘汰では、適応度の低い個体を削除する。例えば、複数の個体の内から適応度が下位のｍ％（あるいはｍ個）を削除する。このｍは任意に設定する。
【００２８】
次に、適応度が高い個体の数を増殖させる（Ｓ４）。例えば、淘汰により残った個体について、適応度が上位のｋ％（あるいはｋ個）の個体の数を２倍にする。これにより、個体の数を淘汰する以前の全個体数と同数に復帰させる。
【００２９】
次に、各個体について、進化により世代交代を行う（Ｓ５）。この進化の処理としては、交差と突然変異がある。交差は図３(a)に示すように、例えば親Ｐ１と親Ｐ２の２つの個体がある場合、それら親Ｐ１と親Ｐ２から、その遺伝子座フロアａ、ｅ〜ｈのビットを互いに入れ替えた子Ｑ１，子Ｑ２を得る処理である。処理手順としては、交差の対象となる個体（親Ｐ１と親Ｐ２）を選択し、交差位置をランダムに決定（ここではａ−ｂ間とｄ−ｅ間）し、親Ｐ１のａの遺伝子を子Ｑ２のａに、親Ｐ２のａの遺伝子を子Ｑ１のａにコピーする。また、ｂｃｄについては、親Ｐ１は子Ｑ１に、親Ｐ２は子Ｐ２にぞれぞれコピーする。さらに、ｅｆｇｈについては、親Ｐ１は子Ｑ２に、親Ｐ２は子Ｑ１にぞれぞれコピーする。一方、突然変異は、図３(b)に示すように、例えば親Ｐ１から子Ｑ３への世代交代でみると、親Ｐ１のｄとｇの遺伝子を互いに交換した子Ｑ３を得る処理である。
【００３０】
以上のようにして進化により得られた各個体について再度評価（Ｓ２）を行い、このループを複数回数に亘って繰り返すことにより、適応度の高い複数（初期集団の数と同じ数）の個体が残ることになるので、ここで遺伝子進化の処理を一旦終了する。
【００３１】
(IV)．移住（又は渡り）の操作
ここでは、複数の分割領域に残った適応度の高い複数の個体について、図４に示すように、ある分割領域の個体の遺伝子列の遺伝子を他の分割領域の個体の遺伝子列に移住させこれを順次各分割領域間で繰り返して進化させ、さらにこれを世代交代毎に繰り返す。すなわち、特定の分割領域の任意の個体の任意の遺伝子座の遺伝子を、別の分割領域の任意の個体の任意の遺伝子座に移し替え、これを順次各分割領域間で繰り返して、各固体について図２のフローチャートと同様な遺伝的アルゴリズムの処理（ただし、評価では適応度としてチップ全体の配置バランスも指標とする）で進化させ、これを世代交代毎に繰り返す。
【００３２】
(V)．終了
これにより、チップ全体の配置バランスの面でも最適解を示す個体を各分割領域毎に得ることができるので、最終的にはこの個体が示す遺伝子列を最適解として、各分割領域毎の容量素子配置箇所に、第１層メタルＭ１により容量素子を配置する。
【図面の簡単な説明】
【００３３】
【図１】容量素子の配置候補箇所の評価の説明図である。
【図２】遺伝的アルゴリズムのフローチャートである。
【図３】交差と突然変異の説明図である。
【図４】移住の説明図である。
【符号の説明】
【００３４】
Ａ１〜Ａ６：配置領域
Ｂ１〜Ｂ３：配線領域
Ｍ１：第１層メタル
Ｍ２：第２層メタル
Ｐ１，Ｐ２：親
Ｑ１〜Ｑ３：子
【図１】
2006268576.tif 000003
【図２】
2006268576.tif 000004
【図３】
2006268576.tif 000005
【図４】
2006268576.tif 000006