(57)【要約】【課題】本発明は、配線変更によるタイミング修正におけるダミーメタル変更の影響を低減し、効率的なレイアウト修正方法を提供することを目的とする。【解決手段】ダミーメタルを含む回路のタイミング検証を行い、タイミング検証によりタイミング違反が検出された場合に回路のレイアウトを修正するレイアウト修正方法は、ダミーメタルにコストを設定し、コストを考慮しながらダミーメタルを含む回路の配線の配置を変更する各段階を含むことを特徴とする。【選択図】  図３
2008226136.tif 000002
【特許請求の範囲】
【請求項１】
ダミーメタルを含む回路のタイミング検証を行い、該タイミング検証によりタイミング違反が検出された場合に該回路のレイアウトを修正するレイアウト修正方法であって、
該ダミーメタルにコストを設定し、
該コストに基づいて該ダミーメタルを含む該回路の配線の配置を変更する
各段階を含むことを特徴とするレイアウト修正方法。
【請求項２】
該コストは、該ダミーメタルを削除することによる該回路のタイミングへの影響の度合いに応じて決定されることを特徴とする請求項１記載のレイアウト修正方法。
【請求項３】
該コストは、該ダミーメタルを他のダミーメタルに置換することによる該回路のタイミングへの影響の度合いに応じて決定されることを特徴とする請求項１記載のレイアウト修正方法。
【請求項４】
ダミーメタルを含む回路のタイミング検証を行い、該タイミング検証によりタイミング違反が検出された場合に該回路のレイアウトを修正するレイアウト修正装置であって、
プログラムを格納するメモリと、
該メモリに格納されるプログラムを実行するプロセッサ
を含み、該プロセッサが該プログラムを実行することにより、
該ダミーメタルにコストを設定し、
該コストに基づいて該ダミーメタルを含む該回路の配線の配置を変更する
各段階を実行することを特徴とするレイアウト修正装置。
【請求項５】
ダミーメタルを含む回路のタイミング検証を行い、該タイミング検証によりタイミング違反が検出された場合に該回路のレイアウトを修正するレイアウト修正プログラムであって、
該ダミーメタルにコストを設定し、
該コストに基づいて該ダミーメタルを含む該回路の配線の配置を変更する
各段階を含むことを特徴とするレイアウト修正プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に計算機利用設計に関し、詳しくは計算機利用設計におけるレイアウトの修正に関する。
【背景技術】
【０００２】
ＬＳＩ回路のレイアウト設計においては、まずセルをチップ上の各位置に配置しセル間を配線することで、設計対象の論理回路のレイアウト（配置・配線）を作成する。次に、配線の容量及び抵抗を抽出し、この配線容量及び抵抗の情報に基づいてタイミング検証を行う。タイミング検証で問題が発見されると、タイミングに問題がある回路部分のレイアウトを変更する。レイアウト変更後に再び容量及び抵抗の抽出及びタイミング検証を行い、このタイミング検証でまた問題が発見されれば、問題がある回路部分のレイアウトを変更する。このようにタイミング検証及びレイアウト変更を繰り返すことによって、タイミング違反がなくなるようにする。
【０００３】
上記の容量及び抵抗の抽出処理においては、ダミーメタルの存在を考慮する必要がある。ここでダミーメタルとは、Ｃｕ（銅）の配線メッキ密度をウエハ上で均一にすることを目的とし、回路動作には寄与しないＣｕ部材である。Ｃｕの配線プロセスでは、ウエハ上のＣｕメッキを研磨して平坦化する作業が行われる。このＣｕメッキの研磨作業においては、ウエハ上でＣｕメッキの密度差が存在すると、研磨の度合いにばらつきが発生してウエハ表面が凹凸になってしまう。ウエハ表面の凹凸は所定の基準値以内であることが必要とされるので、Ｃｕメッキ密度を均一にするためにダミーメタルが挿入される。各配線とダミーメタルとの間には容量成分が存在するので、配線の容量を正確に抽出するためには、容量抽出処理をダミーメタルの挿入後に行うこととなる。
【０００４】
図１は、従来のレイアウト設計及び修正処理の流れを示すフローチャートである。ステップＳ１で回路を配置し、ステップＳ２で配線を行う。即ち、回路記述に基づきセルをチップ上の各位置に配置しセル間を配線することで、設計対象の論理回路のレイアウト（配置・配線）を作成する。
【０００５】
ステップＳ３でダミーメタルを挿入する。この際、配線メタルとダミーメタルとを含めたＣｕ密度がレイアウト平面上で均一となるように、ダミーメタルを挿入することになる。
【０００６】
ステップＳ４で、配線容量及び抵抗を抽出する。即ち、各回路配線について、容量成分と抵抗成分を抽出する。この際、各配線とダミーメタルとの間に存在する容量成分についても考慮される。
【０００７】
ステップＳ５で、各配線（セル出力からセル入力までの一段分）について遅延を計算する。ステップＳ６で、上記遅延計算で求めた遅延量に基づいて回路全体の動作のタイミング検証を行う。
【０００８】
タイミング検証の結果、タイミングに問題がある（タイミング違反がある）場合には、ステップＳ７でダミーメタルを削除する。これは、既存の回路変更・配線変更ツールを使用する場合、ダミーメタルが挿入されたままの状態では、配線が通過できない障害物がレイアウト平面上に配置されていることになり、回路変更及び配線変更を行うことができないからである。
【０００９】
ダミーメタル削除後に、ステップＳ８で回路を変更し、ステップＳ９で配線を変更する。即ち、タイミング違反が解消するようにセルを追加・削除・変更するとともに、セル間の配線を変更する。この後ステップＳ３に戻り、再度ダミーメタルを挿入して、再度のタイミング検証を実行する。タイミング検証の結果、問題が無ければレイアウト設計を終了する。
【００１０】
上記のようなレイアウト設計及び修正処理では、ダミーメタルの削除及び再挿入がタイミング修正処理に影響をもたらすという問題がある。即ち、ダミーメタルの削除、配線変更、及び再挿入という手順の実行により、ダミーメタル削除前には存在していたダミーメタルが、配線変更及びダミーメタル再挿入後には消滅している可能性がある。またこの逆に、ダミーメタル削除前には存在していなかったダミーメタルが、配線変更及びダミーメタル再挿入後には新たに設けられている可能性がある。これは、ダミーメタルの挿入処理が、一般にＣｕ密度を均一にすることを目的とするものであり、タイミング修正を目的とする配線変更とは独立に行われるからである。
【００１１】
この結果、ダミーメタルに変化無ければタイミングを満たす筈の回路部分において、ダミーメタルの消滅又は新たな発生により、タイミングを満たせなくなる場合がある。即ち、ダミーメタルの削除・再挿入が、タイミング修正処理の繰り返し回数を増やしたり、タイミング違反を解消できなくなったりする原因となる。
【特許文献１】特開２００３−２８２５６９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
以上を鑑みて、本発明は、配線変更によるタイミング修正におけるダミーメタル変更の影響を低減し、効率的なレイアウト修正方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
ダミーメタルを含む回路のタイミング検証を行い、該タイミング検証によりタイミング違反が検出された場合に該回路のレイアウトを修正するレイアウト修正方法は、該ダミーメタルにコストを設定し、該コストを考慮しながら該ダミーメタルを含む該回路の配線の配置を変更する各段階を含むことを特徴とする。
【００１４】
ダミーメタルを含む回路のタイミング検証を行い、該タイミング検証によりタイミング違反が検出された場合に該回路のレイアウトを修正するレイアウト修正装置は、プログラムを格納するメモリと、該メモリに格納されるプログラムを実行するプロセッサを含み、該プロセッサが該プログラムを実行することにより、該ダミーメタルにコストを設定し、該コストを考慮しながら該ダミーメタルを含む該回路の配線の配置を変更する各段階を実行することを特徴とする。
【００１５】
ダミーメタルを含む回路のタイミング検証を行い、該タイミング検証によりタイミング違反が検出された場合に該回路のレイアウトを修正するレイアウト修正プログラムは、該ダミーメタルにコストを設定し、該コストを考慮しながら該ダミーメタルを含む該回路の配線の配置を変更する各段階を含むことを特徴とする。
【発明の効果】
【００１６】
本発明の少なくとも１つの実施例によるレイアウト設計方法においては、ダミーメタルにコストを設定し、このコストを考慮しながら、ダミーメタルを含むままの回路の配線の配置を変更する。即ち、ダミーメタルの存在をその配置位置におけるコストに置換えて、コストが各位置に割り当てられた平面上で、コストを考慮しながら配線の配置を決定することになる。従来のように配線が通過不能な障害物としてダミーメタルを取り扱うのではなく、配線の通過し難さを示すコストとしてダミーメタルを取り扱うので、ダミーメタルを含むままの回路において、配線経路及び配置を変更することが可能となる。
【００１７】
また従来技術と異なりダミーメタルの削除及び再挿入を行わないので、ダミーメタルは、その大部分が変化せず、配線が変更された局所部分でのみ変化する。これにより、配線変更していない配線パターンに隣接していたダミーメタルが変化することが少なくなり、配線変更していない配線パターンとダミーメタルとの間で容量が変化する頻度が小さくなる。従って、配線パターンの遅延変動を従来手法に比べて小さくすることができる。また配線変更した配線についても、配線経路が変化しなかった部分のダミーメタルとの隣接状態は変化しないので、ダミーメタルに起因する遅延変動量を小さく抑えることができる。また更に、ダミーメタルを削除することによる回路のタイミングへの影響の度合いに応じてコストを決定し、コストを考慮しながら回路の配線の配置を変更するよう構成すれば、配線を変更した部分についても、ダミーメタル削除による遅延変動量を小さく抑えることができる。
【発明を実施するための最良の形態】
【００１８】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【００１９】
図２は、本発明によるレイアウト設計処理の流れを示すフローチャートである。ステップＳ１で回路を配置し、ステップＳ２で配線を行う。即ち、回路記述に基づきセルをチップ上の各位置に配置しセル間を配線することで、設計対象の論理回路のレイアウト（配置・配線）を作成する。
【００２０】
ステップＳ３でダミーメタルを挿入する。この際、配線メタルとダミーメタルとを含めたＣｕ密度がレイアウト平面上で均一となるように、ダミーメタルを挿入することになる。
【００２１】
ステップＳ４で、配線容量及び抵抗を抽出する。即ち、各回路配線について、容量成分と抵抗成分を抽出する。この際、各配線とダミーメタルとの間に存在する容量成分についても考慮される。
【００２２】
ステップＳ５で、各配線（セル出力からセル入力までの一段分）について遅延を計算する。ステップＳ６で、上記遅延計算で求めた遅延量に基づいて回路全体の動作のタイミング検証を行う。
【００２３】
タイミング検証の結果、タイミングに問題がある（タイミング違反がある）場合には、ステップＳ７で回路を変更する。即ち、タイミング違反が解消するようにセルを追加・削除・変更する。
【００２４】
次にステップＳ８で、ダミーメタルを考慮した配線変更を行う。即ち、図１の従来技術の場合のようにダミーメタルを削除してから配線変更するのではなく、ダミーメタルを含むままの回路の配線の配置を変更する。この際、ダミーメタルにコストを割り当てて、このコストを考慮しながら、ダミーメタルを含むままの回路の配線の配置を変更するようにする。即ち、ダミーメタルの存在をその配置位置におけるコストに置換えて、コストが各位置に割り当てられた平面上で、コストを考慮しながら配線の配置を決定することになる。従来のように配線が通過不能な障害物としてダミーメタルを取り扱うのではなく、配線の通過し難さを示すコストとしてダミーメタルを取り扱うので、ダミーメタルを含むままの回路において、配線経路及び配置を変更することが可能となる。なおコストについては、ダミーメタルを削除することによる回路のタイミングへの影響の度合い等に応じて決定するようにする。この処理の詳細については後ほど説明する。
【００２５】
ステップＳ９で、ダミーメタルを変更する。これはステップＳ８での回路変更により必要となるダミーメタル変更を行う段階である。
【００２６】
以上のように、本発明によるレイアウト設計方法においては、配線変更する際に、ダミーメタルを削除してから配線を変更するのではなく、ダミーメタルを含むままの回路の配線を変更する。この際、ダミーメタルにコストを設定し、このコストを考慮しながら、ダミーメタルを含むままの回路の配線の配置を変更する。更に、回路配線の変更によりダミーメタルの変更が必要になった部分に対してのみ、ダミーメタルの変更を実行する。
【００２７】
このように従来技術と異なりダミーメタルの削除及び再挿入を行わないので、ダミーメタルは、その大部分が変化せず、配線が変更された局所部分でのみ変化する。これにより、配線変更していない配線パターンに隣接していたダミーメタルが変化することが少なくなり、配線変更していない配線パターンとダミーメタルとの間で容量が変化する頻度が小さくなる。従って、配線パターンの遅延変動を従来手法に比べて小さくすることができる。また配線変更した配線についても、配線経路が変化しなかった部分のダミーメタルとの隣接状態は変化しないので、ダミーメタルに起因する遅延変動量を小さく抑えることができる。また更に、ダミーメタルを削除することによる回路のタイミングへの影響の度合いに応じてコストを決定し、コストを考慮しながら回路の配線の配置を変更するので、配線を変更した部分についても、ダミーメタル削除による遅延変動量を小さく抑えることができる。
【００２８】
図３は、ダミーメタルを考慮した配線変更処理の流れを示すフローチャートである。ステップＳ１で、ダミーメタルにコストを設定する。その際、ダミーメタルの削除可能性をコストに反映させる。このコストは、後ほど説明する配線経路探索処理において、所定のアルゴリズムにより配線経路を選択する際の配線経路選択のコストとして用いられる。例えば、ダミーメタルのコストが大きいほど、そのダミーメタルを削除するような配線経路は選択され難くなる。
【００２９】
具体的には、設計データ中に存在するダミーメタルについて、それを削除することによりＣｕメッキ研磨及びタイミングに与える影響が大きいものについては、大きなコストを割り当てる。逆に設計データ中に存在するダミーメタルについて、削除してもＣｕメッキ研磨及びタイミングに与える影響が小さいものについては、小さなコストを割り当てる。またＣｕメッキ研磨及びタイミングに与える影響が小さいように他のダミーメタルに置換できるような場合、即ち代替手段が存在する場合については、小さなコストを割り当てる。この場合のコストは、ダミーメタルを代替手段のダミーメタルに置換することによる回路のタイミングへの影響の度合い等に応じて決定される。
【００３０】
大きなコストを割り当てた場合には、そのダミーメタルが容易には削除又は置換されないことになる。また小さなコストを割り当てた場合には、そのダミーメタルが削除又は置換され易くなる。なお各ダミーメタルには、コストを設定するとともに、代替手段がある場合にはその代替手段を登録しておく。代替手段は一つ又は複数登録できる。
【００３１】
図４は、タイミングへの影響と代替手段の有無とに基づいたコストの一例を示す図である。図４の表に示すように、同一のタイミング条件のダミーメタル同士で比較した場合、代替手段が存在するダミーメタルは、代替手段が存在しないダミーメタルよりもコスト（表の右端の数値）が大きくなっている。また代替手段の有無の条件が同一であれば、タイミングに与える影響が大きいほどコストが大きくなる。なお表中の「・・・」で示す欄は、他の条件（例えばメッキ研磨に与える影響等）を規定する欄である。具体的には、メッキ研磨に与える影響が大きいほど、コストを大きく設定してよい。
【００３２】
図３に戻り、ステップＳ２で、ダミーメタルのコストを配線領域のコストとして設定する。即ち、ダミーメタルに設定したコストを、配線経路探索処理で使用する配線基本区画に対して、配線施設コストとして設定する。このとき、ダミーメタルに対して評価・設定したコストをそのまま配線基本区画に設定してもよいし、或いは配線経路探索処理のアルゴリズムに合わせて変換してから配線基本区画に設定してもよい。
【００３３】
なおダミーメタルのコストは、ダミーメタルが占有する配線経路探索処理の配線基本区画単位に評価・設定してよい。或いは、ダミーメタル全体で一つだけコストを評価・設定し、ダミーメタルが占有する配線基本区画の全てに同一のコストを設定してもよい。
【００３４】
ステップＳ３で、配線基本区画に設定されたコストを参照しながら、配線経路探索処理を行う。この配線経路探索処理のアルゴリズムとしては、ＭＡＺＥ法等の一般的なアルゴリズムを使用してよい。この配線経路探索の結果得られた配線経路が、ダミーメタルを考慮して配線変更された新たな配線経路となる。
【００３５】
上記の配線経路探索処理により決定された新たな配線パターンとダミーメタルとがオーバーラップするときは、ダミーメタルを削除又は変更する必要がある。これは図２のステップＳ９の処理に相当する。ダミーメタルに代替手段が登録されている場合には、この代替手段を用いてダミーメタルを変更する。この際の代替手段としては、配線とダミーメタルとの間隔基準等の設計規則に違反しないものを選択する。選択可能な代替手段が存在しないときは、ダミーメタルを削除する。
【００３６】
以下に、図３に示す配線変更処理について具体的な例を用いて説明する。図５は、配線変更の対象となるレイアウトの一例を示す図である。図５のレイアウトは、配線１１乃至１３、ダミーメタル１４乃至１９、及びダミーメタル２６乃至２８を含む。配線基本区画１０は、図示されるように、配線を配置する際の区画を示すマス目である。始点（セル出力端）Ａから終点（セル入力端）Ｂまで、配線経路を探索して配線を再配置する場合を考える。例えば図２のステップＳ７の回路変更により始点Ａ及び／又は終点Ｂの位置が変更され、変更後の始点Ａ及び終点Ｂに対して新たに配線経路を探索することが必要になった場合などが、この場合に相当する。
【００３７】
まず図３のステップＳ１で説明したように、ダミーメタルにコストを設定する。コストは、平坦性や遅延変動への影響の有無等の観点から、配線経路探索とは独立に決定される。図５の例においては、例えばダミーメタル１４乃至１９に対してコストが設定される。なおダミーメタル２６乃至２８については、再配線の配線が追加する経路上に位置しないので、コストの割り当てを行う必要はない。次に、図３のステップＳ２で説明したように、ダミーメタルのコストを配線基本区画に割り当てる。
【００３８】
図６は、図５のダミーメタルに割り当てられたコストを配線基本区画に設定した例を示す図である。図６に示されるように、図５のダミーメタル１４乃至１９の位置にある配線基本区画に、ダミーメタル１４乃至１９に割り当てられたコストが設定されている。
【００３９】
例えば、ダミーメタル１４、１５、及び１７には代替手段が無く、タイミングに与える影響が大きいので、各ダミーメタルにコストとして１つの値∞（無限大）が設定される。またダミーメタル１６には代替手段が無いが、タイミングに与える影響が比較的小さいので、コストとして１つの値２０が設定される。タイミングに与える影響の大小は、隣接する配線（例えば配線１１や１２）の有無、隣接する配線との距離、隣接する配線のタイミング余裕等に依存して決定することができる。
【００４０】
またダミーメタル１８については、３つの配線基本区画に対応した３つのセグメント２０乃至２２に分ける。セグメント２０については、代替手段が無く、タイミングに与える影響が比較的大きいので、コストとして１つの値１００が設定される。またセグメント２１及び２２については、代替手段が有り、タイミングに与える影響が比較的小さいので、各セグメントにコストとして１つの値５が設定される。
【００４１】
図７は、代替手段の例を示す図である。（ａ）及び（ｂ）はそれぞれ、異なるパターンの代替手段を示す。図５のセグメント２１に対して（ａ）の代替手段で置換するときには、セグメント２１を含む周囲３×４の配線基本区画のダミーメタルを、セグメント２１の位置が位置３０になるように、（ａ）のダミーメタルパターンで置換することになる。また図５のセグメント２１に対して（ｂ）の代替手段で置換するときには、セグメント２１を含む周囲３×４の配線基本区画のダミーメタルを、セグメント２１の位置が位置３１になるように、（ｂ）のダミーメタルパターンで置換することになる。図５のセグメント２２に対して置換するときも同様である。
【００４２】
図５及び図６に戻り、ダミーメタル１９については、３つの配線基本区画に対応した３つのセグメント２３乃至２５に分ける。セグメント２３については、代替手段が無く、タイミングに与える影響が比較的大きいので、コストとして１つの値１００が設定される。またセグメント２４及び２５については、代替手段が有り、タイミングに与える影響が比較的小さいので、各セグメントにコストとして１つの値５が設定される。
【００４３】
図６に示すようにダミーメタルに割り当てられたコストを配線基本区画に設定する処理（図３のステップＳ２の処理）を終了すると、図３のステップＳ３で説明した配線経路探索処理を実行する。まず配線経路探索処理の準備処理として、再探索対象となる配線１３以外の他の配線１１及び１２が存在する基本配線区画に対して、コストとして最も大きい∞を設定する。これは、経路探索対象となる配線１３が、他の配線１１及び１２に交差して配置されることがないようにするためである。
【００４４】
図８は、経路探索対象となる配線以外の配線の位置に∞を設定した様子を示す図である。図８に示すように、図５又は図６において配線１１及び１２の位置する配線基本区画に対して、∞のコストが割り当てられている。
【００４５】
配線経路探索処理において、次に、探索時の移動コストを設定する。例えば、着目配線基本区画から別の配線基本区画に移動する際には、着目配線基本区画に隣接する上下左右の配線基本区画へのみ移動可能とする。その際の一区画分の移動コストは１０であるとする。配線探索対象となる配線１３について、Ａ又はＢの何れか一方を始点とし、始点からの移動コスト、即ち始点からの移動距離×１０の値を、各配線基本区画に設定していく。この際、ダミーメタルのコストが設定されている配線基本区画では、ダミーメタルのコストに対して上記移動コストを加算することにより、その配線基本区画のトータルなコストを求める。
【００４６】
なお、ある１つの配線基本区画に対して複数の異なる経路から異なる値の移動コストが伝播されてくる場合、そのうちで最小のコストを選択して、その配線基本区画の移動コストとする。また既にコストとして∞が設定されている場合には、コストは∞のままとすればよい。
【００４７】
図９は、始点Ａからの移動コストを各配線基本区画に割り当てた図である。配線基本区画に数値が１つしか示されていない場合、その数値は始点Ａからの移動コストである。配線基本区画に数値が２つ示されている場合、左上に示す数値がダミーメタル及び他の配線のコスト（図８に示すコスト）であり、下側に示す数値がそのコストと移動コストとの和である。
【００４８】
配線経路探索処理において、次に、上記のようにして求められたコストに基づいて配線経路を探索する。具体的には、先ほどの始点Ａとは反対側の点Ｂを開始点として、配線基本区画に設定されたコストを参照しながら、コストが単調減少するように経路を選択していく。
【００４９】
図１０は、開始点Ｂからコストが単調減少するように選択した経路を示す図である。なお着目配線基本区画から上下左右の配線基本区画に移動する際に、コストが最も大きく減少するような経路を選択する。コストが同じ経路が複数存在する場合、図１０に示す例では説明を簡単にするために、図面上方に進む経路を優先的に選択している。
【００５０】
このようにして配線経路が探索されると、この探索された配線経路を、配線パターンとして確定する。図１１は、探索された配線経路を配線パターンとして確定した様子を示す図である。図１１に示すように、図１０で求めた配線経路が配線１３Ａとして確定されている。
【００５１】
上記のようにして配線パターンが決定されると、ダミーメタルと配線パターンとがオーバーラップしている部分を検出する。図１１の例では、配線１３Ａとダミーメタル１８及び１９とがオーバーラップしている。当該ダミーメタルの当該オーバーラップ箇所に代替手段が存在する場合には、代替手段の一つを選択し、選択された代替手段でダミーメタルを置換する。代替手段が存在しない場合には、当該ダミーメタルの当該重複箇所を削除する。この処理は、図２のステップＳ９の処理に相当する。
【００５２】
図１２は、オーバーラップ箇所を代替手段で置換した後のレイアウトを示す図である。この例では、図７（ａ）に示す代替手段で、ダミーメタル１８及び１９のオーバーラップ部分を置換えることにより、ダミーメタル４０乃至４３が設けられている。この際、代替手段としては、ウエハ表面の平坦性及び配線遅延変動に与える影響が小さいものを選択すればよい。この例では、既存のダミーメタルと比較し、変更量が小さいパターンを選んでいる。
【００５３】
以下に、再配線対象となった配線の配線パターンの保存による遅延変動の抑制について説明する。
【００５４】
図１３は、配線パターンの配線経路の変更により、他の配線の配線目標が影響を受ける場合について説明するための図である。図１３の左側に示すレイアウトが、本発明によるレイアウト修正処理により、右側に示すレイアウトに修正された場合を考える。配線５１が配線５１Ａに変更されることにより、配線５２の容量が大きく変動してしまう。これはダミーメタルの挿入及び削除による容量変動と同じ現象である。
【００５５】
図１４は、配線経路の変更後に不要となった配線パターンを削除せずに残す処理について説明するための図である。図１４においては、図１３と同様に左側に示すレイアウトが右側に示すレイアウトに修正されるが、配線５１が配線５１Ａに変更される際に、配線変更により不要となった配線５１の一部である配線パターン５１Ｂをそのまま残してある。このように不要となった配線パターン５１Ｂを削除せずに残すことで、配線５２の容量変動を小さくすることができる。この場合、配線パターン５１Ｂはダミーメタルとして取り扱われる。
【００５６】
図１５は、配線経路の変更後に不要となった配線パターンを削除せずに残す処理の詳細について説明するための図である。図１５の（ａ）に示すレイアウトが（ｂ）に示すレイアウトに変更される。この際、再配線により不要となった配線パターン６１及び６２について、その配線パターンが再配線パターンと接続をもたないように分離し、配線パターンを残す。但し、配線パターンが外部から与えられる一定値（長さ）より短く細分化される場合には、不要となった配線パターンを残さない。例えば、配線配置の１グリッドの大きさを１として、長さが３未満の不要配線パターンを残さない等の規定を設けることが考えられる。図１５（ｃ）には、長さが３未満の不要配線パターンを残さないとの規定に従い、配線パターン６１のみ残し、配線パターン６２を削除したレイアウトを示す。
【００５７】
このように配線パターンが一定値以下のものを残さないのは、ある一定値以下の短い配線パターンは、平坦性確保への影響及び遅延変動への影響の度合いが比較的小さいこと等を理由とする。
【００５８】
図１６は、本発明によるレイアウト設計処理及びレイアウト修正処理を実行する装置の構成を示す図である。
【００５９】
図１６に示されるように、本発明によるレイアウト設計処理及びレイアウト修正処理を実行する装置は、例えばパーソナルコンピュータやエンジニアリングワークステーション等のコンピュータにより実現される。図１６の装置は、コンピュータ５１０と、コンピュータ５１０に接続されるディスプレイ装置５２０、通信装置５２３、及び入力装置よりなる。入力装置は、例えばキーボード５２１及びマウス５２２を含む。コンピュータ５１０は、ＣＰＵ５１１、ＲＡＭ５１２、ＲＯＭ５１３、ハードディスク等の二次記憶装置５１４、可換媒体記憶装置５１５、及びインターフェース５１６を含む。
【００６０】
キーボード５２１及びマウス５２２は、ユーザとのインターフェースを提供するものであり、コンピュータ５１０を操作するための各種コマンドや要求されたデータに対するユーザ応答等が入力される。ディスプレイ装置５２０は、コンピュータ５１０で処理された結果等を表示すると共に、コンピュータ５１０を操作する際にユーザとの対話を可能にするために様々なデータ表示を行う。通信装置５２３は、遠隔地との通信を行なうためのものであり、例えばモデムやネットワークインターフェース等よりなる。
【００６１】
本発明によるレイアウト設計処理及びレイアウト修正処理は、コンピュータ５１０が実行可能なコンピュータプログラムとして提供される。このコンピュータプログラムは、可換媒体記憶装置５１５に装着可能な記憶媒体Ｍに記憶されており、記憶媒体Ｍから可換媒体記憶装置５１５を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。或いは、このコンピュータプログラムは、遠隔地にある記憶媒体（図示せず）に記憶されており、この記憶媒体から通信装置５２３及びインターフェース５１６を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。
【００６２】
キーボード５２１及び／又はマウス５２２を介してユーザからプログラム実行指示があると、ＣＰＵ５１１は、記憶媒体Ｍ、遠隔地記憶媒体、或いは二次記憶装置５１４からプログラムをＲＡＭ５１２にロードする。ＣＰＵ５１１は、ＲＡＭ５１２の空き記憶空間をワークエリアとして使用して、ＲＡＭ５１２にロードされたプログラムを実行し、適宜ユーザと対話しながら処理を進める。なおＲＯＭ５１３は、コンピュータ５１０の基本動作を制御するための制御プログラムが格納されている。
【００６３】
上記コンピュータプログラムを実行することにより、コンピュータ５１０が、上記各実施例で説明されたようにレイアウト設計処理及びレイアウト修正処理を実行する。
【００６４】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【図面の簡単な説明】
【００６５】
【図１】従来のレイアウト設計及び修正処理の流れを示すフローチャートである。
【図２】本発明によるレイアウト設計処理の流れを示すフローチャートである。
【図３】ダミーメタルを考慮した配線変更処理の流れを示すフローチャートである。
【図４】タイミングへの影響と代替手段の有無とに基づいたコストの一例を示す図である。
【図５】配線変更の対象となるレイアウトの一例を示す図である。
【図６】図５のダミーメタルに割り当てられたコストを配線基本区画に設定した例を示す図である。
【図７】代替手段の例を示す図である。
【図８】経路探索対象となる配線以外の配線の位置に∞を設定した様子を示す図である。
【図９】始点Ａからの移動コストを各配線基本区画に割り当てた図である。
【図１０】開始点Ｂからコストが単調減少するように選択した経路を示す図である。
【図１１】探索された配線経路を配線パターンとして確定した様子を示す図である。
【図１２】オーバーラップ箇所を代替手段で置換した後のレイアウトを示す図である。
【図１３】配線パターンの配線経路の変更により、他の配線の配線目標が影響を受ける場合について説明するための図である。
【図１４】配線経路の変更後に不要となった配線パターンを削除せずに残す処理について説明するための図である。
【図１５】配線経路の変更後に不要となった配線パターンを削除せずに残す処理の詳細について説明するための図である。
【図１６】本発明によるレイアウト設計処理及びレイアウト修正処理を実行する装置の構成を示す図である。
【符号の説明】
【００６６】
１１〜１３  配線
１４〜１９  ダミーメタル
２６〜２８  ダミーメタル
５１０  コンピュータ
５１１  ＣＰＵ
５１２  ＲＡＭ
５１３  ＲＯＭ
５１４  二次記憶装置
５１５  可換媒体記憶装置
５１６  インターフェース
５２０  ディスプレイ装置
５２１  キーボード
５２２  マウス
５２３  通信装置
【図１】
2008226136.tif 000003
【図２】
2008226136.tif 000004
【図３】
2008226136.tif 000005
【図４】
2008226136.tif 000006
【図５】
2008226136.tif 000007
【図６】
2008226136.tif 000008
【図７】
2008226136.tif 000009
【図８】
2008226136.tif 000010
【図９】
2008226136.tif 000011
【図１０】
2008226136.tif 000012
【図１１】
2008226136.tif 000013
【図１２】
2008226136.tif 000014
【図１３】
2008226136.tif 000015
【図１４】
2008226136.tif 000016
【図１５】
2008226136.tif 000017
【図１６】
2008226136.tif 000018