JP4871168B2 - 集積回路の配線経路探索方法、集積回路の自動配線装置およびプログラム - Google Patents

Description

本発明は、集積回路の配線経路探索方法、集積回路の自動配線装置および集積回路の配線設計装置を動作させるプログラムに関し、特に複数の配線層を有する集積回路の自動配線レイアウトを行う方法、装置およびプログラムに関する。

半導体集積回路は高集積化および多層化が進められており、半導体集積回路の設計では、ＣＡＤ装置の集積回路配線設計機能を使用して自動配線レイアウト処理が行われる。自動配線レイアウト処理は、レイアウト面において始点ノードから終点ノードへの最適な経路を探索する処理である。

図１は、レイアウト処理の例を示す図である。図１は、始点ノード１から終点ノード２への最適な経路を探索したものであり、始点ノード１と終点ノード２の間には障害物３が設けられており、これらを避けて経路を形成する。ここでは３つの経路があり、第１の経路は、始点ノード１から、第１層の配線４と、第２層の配線５と、第１層の配線６を経由して終点ノード２に至る経路であり、第２の経路は、始点ノード１から、第１層の配線７と、第２層の配線８と、第１層の配線９を経由して終点ノード２に至る経路であり、第３の経路は、始点ノード１から、第２層の配線１０と、第１層の配線１１と、第２層の配線１２と、第１層の配線１３と、第２層の配線１４と、第１層の配線１５と、第２層の配線１６と、を経由して終点ノード２に至る経路である。異なる層の配線を接続するにはビア（カット（Ｉ０１））が使用される。第１および第２の経路では、ビアは少ない（カット2個）が、配線長が長くなる。一方、第３の経路では、配線長は短いがビアは多く（カット8個）なる。

どのような経路を選択するかは、選択されるノードに応じて異なる負荷（コスト）がかかるように設定し、取り得る経路ごとにコストを計算し、もっともコストの低い経路を選択する。図２は、コスト系列とコスト計算式の例を示す図である。図２の例では、コスト要素として、主方向距離、従方向距離、標準ビア数、冗長ビア数、配線ルール違反などが規定され、それぞれのコスト係数はＤｍ、Ｄｓ、ｖＣ、ｒｖＣ、Ｅｃｏｓｔである。始点ノード１から終点ノード２への各配線ＣＳｎについて各要素値を求め、計算式（１）に従ってコスト（ｃｏｓｔ）を計算する。例えば、目標ノードと逆方向のノードを選択すると、配線長が長くなりコストが増加し、図示していないが配線を曲げる回数などもコスト要素になり配線を曲げる回数が増加するとコストが増加する。さらに、既に占有されているノードに割り込む時などにはコストが高くなるように設定する。複数の配線層を有する場合には、異なる層の配線をビアで接続するが、図示のようにビア数もコスト要素になりビア数が増加すりとコストが増加する。ビアには、所定の大きさのビアを１個設ける標準ビアと、後述する冗長ビアがあり、コスト係数が異なる。

図３は、同層の始点ノードＳから終点（目標）ノードＴまでの経路探索方法を説明する図である。始点Ｓに隣接するノードは、Ｎ１とＮ４の主方向ｍＤの２ノード、Ｎ２とＮ３の従方向ｓＤの２ノード、およびＮｖ１のビア方向ｖＣの１ノードであり、進路としていずれかが選択できる。各進路についてはそれぞれ負荷（コスト）係数が決められており、図では主方向ｍＤの進路がコスト係数１であり、従方向ｓＤの進路がコスト係数３であり、ビア方向ｖＣの進路がコスト係数２であり、他に迂回（逆方向の進路選択）および曲がり（進路方向の変更）にコスト係数１が加算される。以上のようなコスト係数の条件で、始点ノードＳから目標ノードＴまでのとり得る経路について、コスト係数の合計（コスト）を求め、最小コストの経路を選択する。図３では、対象領域を格子状に分割してノードを設定したが、実際には格子状である必要はなく、障害物に当たる直前に次のノードを設定するといったことが行われ、これにより処理時間を短縮できる。

実際に経路探索の計算を行う場合には、始点Ｓからいろいろな方向に順次経路を伸ばす。上記のようなコスト係数に従って、各経路が伸びるのに応じて各経路のコストが計算され、それがラベル値で表される。複数の経路のうち最小のラベル値の経路が選択されて伸ばされ、伸びるに従ってコストが増大するので、各経路は多少の前後はあってもそれぞれ順次伸ばされ、最初に終点（ターゲット）ノードに到達した経路が最小コストの経路ということになる。経路探索の方法については、特許文献１などに記載されているので、詳しい説明は省略する。

集積回路におけるビアを使用した配線では、ストレスマイグレーションと呼ばれる現象が発生してビア配線の断線が発生することが、特許文献２および３などに記載されている。ストレスマイグレーション（ＳＭｉｇ（ＳＭ））は、高温放置試験や熱サイクル試験あるいはプロセス中の熱で、ビア内（底）の銅が消失し、ボイドが成長する銅配線特有の現象である。図４は、ストレスマイグレーションを説明する図であり、図４の（Ａ）に示すように、異なる層に設けられた配線２１と２２をカット２３で接続した構造で熱を印加すると、図４の（Ｂ）に示すように、カット２３と配線２１の接触部分にボイド２４が成長する。ストレスマイグレーションは、熱応力の特異性（駆動力）によるｖａｃａｎｃｙの拡散によると考えられ、太い配線に小さな径のカットの組合せで発生し易い。

ストレスマイグレーションによる断線発生を回避するために、集積回路の配線設計を行う場合には、ｍｉｎｉｍｕｍＣｕｔルールと呼ばれるルールを設けている。具体的には、太い導体（ワイヤ（配線）、ビアメタル、端子）から一定距離の範囲内でビアを設けて異層間接続する場合には、通常使用される最小ビアを複数個設けるなどにより、最小ビアよりも冗長な接続を行う。図５は、ｍｉｎｉｍｕｍＣｕｔルールによる冗長ビアの例を説明する図である。太い導体（ワイヤ（配線）、ビアメタル、端子）４１から細い配線４２を伸ばし、別の層の配線４３とカット４５で接続する場合、太い導体４１からカットまでの距離Ｄが所定距離より短い時には、配線４３の端部にビアメタル拡張部４４を設けて、カット４６を追加し、冗長ビアを設ける。これによりストレスマイグレーションによる断線発生を低減できる。冗長ビアとは、カット部分を複数持つビア、あるいは通常の１カットビアを２つ以上並べた構造を意味する。

多層のＬＳＩ配線層構成では、通常下側の層が微細ピッチで上層にいくほど粗くなる。また、隣接配線同士の最小配線幅、配線トラックピッチは高々２倍程度の違いであるのが普通である。しかし、設計によっては、隣接層の標準配線幅が４倍違うような場合も生じる。そのような時には、連続３配線層間を接続するビアのカットサイズが上２層間と下２層間で４倍ほど違うことが起き、それに伴ってビアのカットを覆う蓋（＝ビアメタル）のサイズにも４倍ほどギャップが生じる。

例えば、Ｍ１からＭ６の６層の配線層で構成するＬＳＩを仮定し、Ｍ１からＭ５までの標準配線幅を１とした時に、Ｍ６の標準配線幅が４であると、仮定する。配線層間をつなぐビアのカット径は太幅配線層側に合わせて決めており、Ｍ５−Ｍ６間のカット径はＭ６の配線幅４と同じ程度の大きいカットで、Ｍ４−Ｍ５間が径の小さい幅１程度のカットで接続される状態となる。ここでＭ５に注目すると、標準幅１の配線と太い幅４の蓋（＝ビアメタル）が連続の導体上に存在する形状となる。ここで、ｍｉｎｉｍｕｍＣｕｔルールの幅ギャップの閾値≧３、太幅位置からの制約適用範囲距離を無限大とすると、上記のような形状には冗長ビア制約が発生する。

特開平１−１３７３７３号公報 特開２００３−１９７６２３ 米国特許第６７３７３５１号

ｍｉｎｉｍｕｍＣｕｔルールは、従来の自動配線方式にも適用されている。自動配線方式は、ノードからノードへコスト（評価値）を伝播させる手順において、各ノードをどのような配線やビアで埋めて通過するか決めてノードの評価値を計算し、次へ進むが、ｍｉｎｉｍｕｍＣｕｔルールを適用する場合、大径ビアを使用したまたは太い導体に探索が到達して接続した時点になって、それ以前に最小ビアで経由して評価したノードが、本来冗長ビアで経由して評価しなければならなかったことが判明するということである。言い換えれば、既に処理が進められて確定したと考えられていた部分について十分でなく、「エラー」であることが判明するということである。従来の自動配線方式では、このようなエラーが生じた部分を自動で回復できるようになっておらず、経路コストを過小評価したまま探索を続けると、その区間の最小コスト経路が求まらず、相互の配線経路の最適化を進めることができない。

図１に戻ってこの問題点を説明する。図１では、始点ノード１から、第１層の配線４と、第２層の配線５と、第１層の配線６を経由して終点ノード２に至る第１の経路が、配線長が短く小さいコストの経路であるため、通常であれば選択される。第１の経路において、配線１１と配線１２を接続する部分１７は標準ビアとして形成されたが、配線１２と配線１３を接続する部分１８を太いビアとした場合、部分１７は冗長ビアで形成するという制約が後で発生する。ここで、部分１７を冗長ビアに変更できれば問題ないが、図１のように部分１７に隣接して障害物３が存在する場合には、冗長ビアを割り込ませるとショートしてしまう。従来の自動配線方式では、このような状況だとしても、部分１７通過時のコストを過小評価（ショートは考慮外）により、そのまま最小コスト経路として誤認定してしまう。このように、ｍｉｎｉｍｕｍＣｕｔルールを適用した場合には、冗長ビア作成箇所で配線エラーを生じるような本来選択されるべきでない第３の経路が残り、本来選択されるべき第1または第2の経路が選択されずに棄却されることになる。

本発明は、上記のような問題を解決するもので、設計を進めた後で判明する既に探索済みの経路の冗長ビアへの変更を容易に行え、冗長ビアへの変更が行われても経路の最適解が容易に得られる集積回路の配線経路探索方法、集積回路の配線設計装置およびプログラムの実現を目的とする。

上記目的を実現するため、本発明は、経路探索中の経由点では、最小ビアを使用してきたと仮定した時のコストと、冗長ビアを使用してきたと仮定した時のコストを両方保持することにより、過小評価状態を解消する。そして、経路探索中に大径ビアを使用した時は、もし直前に使用したビアが冗長でなければならないことが判明したならば、冗長ビアの使用を仮定した側の経路コストを採用する。これにより、通過ノードのコストは適正値で評価でき、過小値とならない。

図６は、本発明の集積回路の自動配線装置の構成を示すブロック図である。図６に示すように、本発明の集積回路の自動配線装置は、記憶装置５０に記憶された設計ルール、配線指示およびコスト系列などに基づいて、始点ノードから終点ノードへの複数の配線経路についてそれぞれ評価値を計算する評価値計算回路５１と、計算した評価値に基づいて、前記始点ノードから前記終点ノードへの配線経路を決定する決定回路５２と、配線の線幅の差に応じて、使用するビアタイプを選択するビアタイプ選択回路５３と、を備える集積回路の自動配線装置であって、前記評価値計算回路５１は、ビアを設ける配線経路について、ビアを設けた以後の前記評価値を、異なるビアタイプを使用する場合の複数の前記評価値と同時に計算する、ことを特徴とする。

更に、ストレスマイグレーション（ＳＭ）対策の範囲を限定して設計効率をよくするために、太幅の導体から一定の道のりだけ離れれば、冗長ビア接続の制約対象外になるというルールを設けることがある。このルールに対処するには、探索時点の（現在の）着目ノードに伝播するまでに、最後に配線幅が変化したり、ビアで伝播したノードからの道のりでどれだけ離れたかの情報を保持するようにする。あるいは一定の道のりだけ離れたかどうか示すフラグを使用してもよい。

本発明によれば、経路探索中に大径ビアを使用した時には、ｍｉｎｉｍｕｍＣｕｔルールに該当する距離範囲内に冗長ビアコストでの評価が必要な箇所があるかどうかと、採用すべき評価値が決定できる。または、大径ビアから一定以上離れたことを示すフラグを各ノードが持つことにより、次の伝播先がビア発生を伴うノードである際に、冗長ビア制約の対象になるか否かが判明し、採用すべきコスト（評価値）が決定できる。

また、経路コストをこのように伝播させてターゲット（終点）ノードに到達したら、到達先のターゲットノードから逆に伝播元をたどって経路を作成していく。遡る際のノード間で、冗長ビア接続が必要な箇所をチェックしながら経路を作成すれば、ｍｉｎｉｍｕｍＣｕｔルールを守った最適配線経路が実現できる。

本発明によれば、ストレスマイグレーション（ＳＭ）による断線の発生を低減するｍｉｎｉｍｕｍＣｕｔルールを守って、最適配線経路が得られる集積回路の配線経路探索方法、集積回路の配線設計装置およびプログラムが実現される。

本発明は、ＬＳＩ設計ＣＡＤ装置の形で実現され、ＣＡＤ装置を利用しての本発明の集積回路の配線経路探索方法、本発明の方法を実行できるようにしたＣＡＤ装置、すなわち集積回路の配線設計装置や、本発明の設計方法を行うようにＣＡＤ装置にインストールされるプログラムを対象とする。

図７は、本発明の実施例の集積回路の配線経路探索処理の全体フローを示す図である。配線経路探索処理は、記憶装置１０１に記憶された設計ルール、配線指示、コスト系列などに基づいて行われる。ステップＳ１０では、図２に示したようなコスト系列を設定し、図示のコスト計算式に基づいて経路探索のコストが計算される。ステップＳ１１は、ステップＳ２０−Ｓ２５を有し、そこでは集積回路の全対象領域についての配線経路の探索が行われる。ステップＳ１２では、ステップＳ１１の探索結果に基づいてコスト系列が更新され、ステップＳ１３ですべてのコスト系列について処理が終了したか判定され、終了するまでステップＳ１１からＳ１３が繰り返され、終了するとステップＳ１４に進んで、処理結果である配線レイアウトを記憶装置１０２に記憶して処理を終了する。

ステップＳ２０では、配線区間の始点ノードＳと、終点（ターゲット）ノードＴを選択する。ステップＳ２１では、始点ノードＳと終点ノードＴの間が未結線であるか、またはＳとＴの間に設計ルール違反があるかを判定する。ＳとＴの間が結線済みかつルール違反無しの場合には経路の変更の必要がないため、ステップＳ２０にいって、次の配線対象区間の設定へと進む。S21でS20の設定区間が未結線判定となった場合はステップＳ２２に進む。S21でS20の設定区間がルール違反ありの経路と判定された場合は、其の経路を一旦破棄してS22に進む。

ステップＳ２２では、ＳとＴの間の最小コストの経路を探索する。ステップＳ２３では、探索方向とは逆方向に、Ｔから親ノードをたどってＳに至る配線経路を作成する。ステップＳ２４では、作成した配線経路を配線領域に登録する。ステップＳ２５では、全区間について配線が終了したかを判定し、終了していなければステップＳ２０に戻り、全区間についての配線が終了するまでステップＳ１１を繰り返す。

本発明の実施例のフローは、ステップＳ２２の最小コスト経路探索処理が従来例と異なり、他の処理は従来例とほぼ同じである。

本発明の実施例のフローにおけるステップＳ２２の最小コスト経路探索処理を説明する前に、比較のために従来例の最小コスト経路探索処理を説明する。

図８は、従来例の最小コスト経路探索処理を示すフローチャートである。ステップＳＰ３０では探索ノードの初期化を行い、ステップＳＰ３１では始点Ｓを探索リストＭに入れる。これにより、始点ノードＳから伸びる経路を記憶するメモリ領域が確保され、親ノード（Ｐノード）に対する子ノードの形でつながる経路情報が生成できるようになる。ステップＳＰ３２ではＭが空（Ｉ０２）であるか判定する。Ｍが空であれば、探索は終了なのでステップＳＰ４８に進んで探索を終了する。Ｍが空でなければステップＳＰ３３に進んで、リストＭにある最小ラベル値（Ｌ）のノードＰを１つ取り出す。前述のように、始点ノードＳから複数の経路が伸ばされ、それぞれの経路の先端がノードＰであり、各ノードＰにはコストに関係するラベル値Ｌが設定されており、最小ラベル値のＰが取り出される。ラベル値は経路が伸びるに従って増加するので、最小ラベル値のノードＰを選択することにより、各経路が順次選択されることになる。ステップＳＰ３４では、ＰがNULLでなく（Ｐが存在し）且つラベル値Ｌが目標（ターゲット）ラベル以下であるかを判定する。これによりノードTのラベル値以上にコストの大きな経路探索が回避される。もしＰがNULLもしくはPのラベル値ＬがターゲットノードTのラベルより大きい時には、それ以上の探索は必要ないのでステップＳＰ４８に進んで探索を終了し、それ以外の時には、ステップＳＰ３５に進む。

ステップＳＰ３５では、ノードＰから伸びることが可能なノードでＭに未登録のＮｉを１つ選択する。ノードＰから伸びることが可能なノードは、ノードＰに対して主方向または従方向に離れた位置にあるノードか、ビアを介して異なる層にあるノードＰと同じ平面位置のノードである。なお、これらを組み合わせて、主方向にある距離進んで従方向にある距離進んだノードも選択可能とする。ここでは、ノードＰから伸びることが可能なノードをＰの隣接ノードと称する。ステップＳＰ３６では、ＮｉがNULLであるか、すなわち選択できる隣接ノードがないかを判定し、ＮｉがNULLであればステップＳＰ３２に戻り、ＮｉがNULLでなければステップＳＰ３７に進む。

ステップＳＰ３７では、ノードＮｉとノードＰが同層であるか判定し、同層の場合にはステップＳＰ３８に進み、異なる層の場合にはステップＳＰ４０に進む。ステップＳＰ３８で同じ層内を伝播する時のコストＣｌｉを計算し、ステップＳＰ３９でノードＰまでのラベル値ＬにＣｌｉを加えて、その経路がノードＮｉに到達した時点でのラベル値（現ラベル）を計算し、ステップＳＰ４２に進む。

ステップＳＰ４０では、ビアを経由して異層間を伝播するので、ビア伝播コストＣｖｉを計算し、ステップＳＰ４１でノードＰまでのラベル値ＬにＣｖｉを加えて、その経路がノードＮｉに到達した時点でのラベル値（現ラベル）を計算し、ステップＳＰ４２に進む。

ステップＳＰ４２では、現ラベルがＮｉで予定されたラベルの閾値ＮｉＬより小さいかを判定し、閾値ＮｉＬより小さければステップＳＰ４３に進み、閾値ＮｉＬ以上であれば、そのような経路を選択するのは好ましくなく、それ以上経路探索を行う必要はないので、ステップＳＰ３５に戻る。ここで、閾値NiLとは、ノードNiのラベル初期値（∞）もしくは別の伝播経路が先にNiを通過したときに付けたラベル値のこと。

ステップＳＰ４３では、Ｎｉまで到達した経路のラベル値を現ラベルに更新し、ステップＳＰ４４でNiの親ノードをＰに更新する。ステップＳＰ４５では、現ノードNiがターゲットノードＴであるかを判定し、ＴでなければステップＳＰ４６に進んでノードＮｉを探索リストＭに追加してステップＳＰ３５に戻り、ＮｉがターゲットノードＴになるまでステップＳＰ３５からＳＰ４６を繰り返す。ＮｉがＴであれば、経路探索は終点ノードＴに到達したことを意味するので、ステップＳＰ４７でターゲットノードＴのラベル値を更新し、再びＳＰ３５に戻る。Pの隣接ノードのうち、Mに登録されていないものが存在すれば、SP35でNiとして伝播候補にし、SP37の判定に進むが、NiがNULLのときにはSP32、SP33と進み新たな伝播の起点になるノードPを取り出す。このとき、ノードPの取り出し条件として、前出のターゲットTに先に到達したときのラベル値より小さいラベル値のノードであることを要求するので、其の条件に合うノードが探索リストMにもうないならばSP34で否決されてSP48へ行き、探索終了となる。以上の処理により、コストを計算しながらいろいろな経路が伸ばされ、最小コストの経路がターゲットノードＴに到達するので、コストが最小になる経路が決定される。

以上説明した従来の最小コスト経路探索処理では、ビアを経由する場合のコストはステップＳＰ４０およびＳＰ４１で計算されるが、冗長ビアについては考慮されていなかった。

図９から図１２は、本発明の実施例のステップＳ２２の最小コスト経路探索処理を示すフローチャートである。図８に示した従来の処理と特に異なるのは、ノードＮｉとノードＰが異なる層のノードであると判定された後の処理である。

ステップＳ３０では、探索ノードの初期化を行う。図１３は、初期化処理を説明する図である。初期化処理では、すべての探索ノードＮｉの構造体メンバについて、属性ＳＴＦ、ラベル値Ｌ１、Ｌ２、線幅Ｗ、道のりＣＤを初期値に設定する。実施例では、標準ビアを使用する場合と冗長ビアを使用する場合のために、２つのラベル値が使用される。具体的には、Ｎｉが始点ノード１につながる導体上にあれば、ＳＴＦを始点を示す値”Ｓ”に、Ｌ１とＬ２を０に設定し、その上で標準線幅より太い導体上であればＷを太い幅に、ＣＤを０に設定し、標準線幅の導体上であればＷを標準線幅に、ＣＤを太いところからの道のりに設定する。Ｎｉが終点ノード２につながる導体上にあれば、ＳＴＦをターゲット（終点）を示す値”Ｔ”に、Ｌ１とＬ２を最大値に設定し、その上で標準線幅より太い導体上であればＷを太い幅に、ＣＤを０に設定し、標準線幅の導体上であればＷを標準線幅に、ＣＤを太いところからの道のりに設定する。Ｎｉが始点ノード１の導体および終点ノード２の導体のいずれの上にもない場合には、ＳＴＦをデフォルト値に、Ｌ１とＬ２を最大値に設定し、Ｗをその層の標準配線幅に、ＣＤ（ＮｉＣＤ）を０に設定する。

ステップＳ３１では始点Ｓを探索リストＭに入れる。これにより、始点Ｓから伸びる経路を記憶するための記憶領域が確保され、親ノード（Ｐノード）に対する子ノードの形でつながる経路情報が生成できるようになる。子ノードは、親ノードＰに隣接するノードである。経路情報には、各経路のラベル値Ｌも合わせて記憶され、本実施例では標準ビアを使用する場合のラベル値Ｌ１と、冗長ビアを使用する場合のラベル値Ｌ２の２つが記憶される。

ステップＳ３２ではＭが空であるか判定する。Ｍが空であればステップＳＰ４５に進んで探索を終了し、Ｍが空でなければステップＳ３３に進む。ステップＳ３３では、リストＭにある最小ラベル値（Ｌ）のノードＰを１つ取り出す。ステップＳ３４では、ＰがNULLでなく（Ｐが存在し）且つラベル値Ｌが目標（ターゲット）ラベル以下であるかを判定し、もしＰがNULLで且つラベル値Ｌがターゲットラベルより大きい時には、それ以上の探索は必要ないのでステップＳ４５に進んで探索を終了し、それ以外の時には、ステップＳ３５に進む。ステップＳ３５では、ノードＰの隣接ノードで、Ｍに未登録のＮｉを１つ選択する。ステップＳ３６では、ＮｉがNULLであるかを判定し、ＮｉがNULLであればステップＳ３２に戻り、ＮｉがNULLでなければステップＳ３７に進む。

以上のステップＳ３０からＳ３６は、ラベル値として標準ビアを使用する場合のラベル値Ｌ１と、冗長ビアを使用する場合のラベル値Ｌ２の２つが使用される点を除けば、図８の従来のステップＳＰ３０からＳＰ３６とほぼ同じ処理内容である。

ステップＳ３７では、ノードＮｉとノードＰが同層であるか判定し、同層の場合にはステップＳ３８に進み、異なる層の場合にはステップＳ５０に進む。

ステップＳ３８では、同じ層内を伝播する時のコストＣｌｉを計算する。この計算は、ノードＰとノードＮｉ間の主方向距離ａと従方向距離ｂを求め、ノードＰとノードＮｉ間を標準配線幅で接続すると仮定した時に発生する配線ルール違反数ｅをカウントし、図２に示したコスト計算式に基づく次の式で計算される。

Ｃｌｉ＝ａ×Ｄｍ＋ｂ×Ｄｓ＋ｅ×Ｅｃｏｓｔ
ステップＳ３９では、ノードＰまでのラベル値Ｌ１とＬ２にＣｌｉをそれぞれ加えて、その経路がノードＮｉに到達した時点でのラベル値（現ラベル）Ｌ１とＬ２を計算する。そして、ノードＮｉがターゲットノードＴに到達し、かつノードＮｉの配線幅と標準配線幅の差が冗長ビア制約を受ける配線幅差の所定の閾値ΔＷｔｈより大きく、かつ配線幅が太い部分から細い部分に変化する位置までの道のりが冗長ビア制約を受ける道のりの所定の閾値Ｄｔｈより小さい場合に、ノードＰのラベル値としてＬ２（冗長ビアラベル値）を採用し、それ以外であればノードＰのラベル値としてＬ１（標準ビアラベル値）を採用する。

ステップＳ４０では、現ラベルがＮｉで予定されたラベルの閾値ＮｉＬ１とＮｉＬ２のいずれよりも小さいかを判定し、小さければステップＳ４１に進み、大きければそれ以上経路探索を行う必要はないので、ステップＳ３５に戻る。

ステップＳ４１では、Ｎｉのラベル値を現ラベルに更新し、ステップＳ４２でNiの親ノードをPに更新する。ステップＳ４３では、NiがターゲットノードＴであるかを判定し、Ｔでなければ図１０のステップＳ６０に進み、ＮｉがＴであれば、経路探索は終点ノードＴに到達したことを意味するので、目標ラベル値をNiのラベル値L1,L2の小さい方で更新する。また、このときのNiは複数あるターゲットノード（STF==Tの属性を持つ）のうち、最小ラベルが伝播したノードとして記憶し、Ｓ３５に戻る。ここで記憶したノードはS90におけるｃNに相当する。

図１０のステップＳ６０では、ノードＰとノードＮｉの道のり（距離）Ｄを計算する。ステップＳ６１では、ノードＮｉの情報であるＷ（配線幅）、ＣＤ（太い部分からの道のり（距離））を更新する。具体的には、ノードＰまでの道のりにノードＰからノードＮｉまでの道のりを加えてＣＤを算出する。また、計算したＣＤ（ノードＮｉまでの道のり）が閾値Ｄｔｈより大きければ、ノードＮｉの配線幅を、ノードＮｉの設けられる層の標準配線幅とし、そうでなければノードＰの配線幅とする。

ステップＳ６２では、ノードＮｉを探索リストＭに追加して（ラベルが伝播したノードとして記憶して）、ステップＳ３５に戻る。ノードＮｉの探索リストＭへの追加は、始点Ｓの追加と同じである。

ステップＳ３７でノードＮｉとノードＰが異なる層のノードであると判定された時には、図１１に示すステップＳ５０に進む。ステップＳ５０では、冗長ビアルールを考慮してノードＰのラベル値Ｌを決定する。図１４は、ステップＳ５０におけるラベル値Ｌの決定処理を示すフローチャートであり、図１５はビアタイプの決定処理を説明する図である。ステップＳ８０では、ノードＰとノードＮｉ間に使用する標準ビアの、ノードＰを設けた層側のビアメタル幅Ｖｗを求める。ステップＳ８２では、ＶｗとノードＰが設けられる層の標準配線幅Ｐｗとの差が所定の閾値ΔＷｔｈより大きく、かつノードＰを含む配線長ＰＣＤが所定の閾値Ｄｔｈ以下であるか、を判定する。この条件を満たす場合には、ステップＳ８３に進み、ノードＰのラベル値ＬとしてＬ２の値を採用し、この条件を満たさない場合には、ステップＳ８４に進み、ノードＰのラベル値ＬとしてＬ１の値を採用する。図１５の（Ａ）は、ノードＰを含む配線長ＰＣＤが所定の閾値Ｄｔより大きいために、この条件を満たさない場合を示し、ノードＰを含む経路と前の層とのビアとして標準ビアが使用される。一方、図１５の（Ｂ）はこの条件を満たす場合を示し、ノードＰを含む経路と前の層とのビアとして冗長ビアが使用される。

ステップＳ５１では、ノードＰとノードＮｉ間に標準ビアを使用したと仮定した時の違反コストＮＶｅと、ノードＰとノードＮｉ間に冗長ビアを使用したと仮定した時の違反コストＲＶｅと、を計算する。具体的には、標準ビアを使用したと仮定した時に発生するエラー数ｅｎと、冗長ビアを使用したと仮定した時に発生するエラー数ｅｒと、をカウントし、次の式に従ってＮＶｅとＲＶｅとを計算する。

ＮＶｅ＝ｅｎ×Ｅｃｏｓｔ
ＲＶｅ＝ｅｒ×Ｅｃｏｓｔ
ステップＳ５２では、ノードＰとノードＮｉ間のビアタイプを決定し、ビア伝播コストＣｖｉ１とＣｖｉ２を計算する。具体的には、ノードＮｉ側の配線幅Ｗｎを、ノードＮｉがターゲットノードであれば、既に説明した図9のS30の初期化処理で設定したターゲットノードの幅Ｗとし、そうでなければNiの存在する層の標準配線幅ＮＷとする。その上で、ノードＰ側の配線幅ＰＷがＷｎ以下でその差が閾値ΔＷｔｈ以上で、かつノードＮｉ側のビアメタルの最小幅ＶｎがノードＰの幅以下であるかまたはＷｎとＶｎの差が閾値ΔＷｔｈ以上の時、冗長ビアを使用する。
また、ノードP側の配線幅PWがWnより大きく、かつその差が閾値ΔWth以上かつ標準ビアのP層側ビアメタルの最小幅VpがWn以下のときと、PWとVpの差がΔWth以上のときには冗長ビアを使用する。
それ以外は標準ビアを使用する。

更に、ビア伝播コストＣｖｉ１とＣｖｉ２は、冗長ビアを使用する場合には、Ｃｖｉ１は冗長ビアコストと冗長ビアを使用することによる違反コストの和であり、Ｃｖｉ２はＣｖｉ１と同じであり、標準ビアを使用する場合には、Ｃｖｉ１は標準ビアコストと標準ビアを使用することによる違反コストの和であり、Ｃｖｉ２は冗長ビアコストと冗長ビアを使用することによる違反コストの和である。

ステップＳ５３では、ノードＰまでのラベル値ＬにＣｖｉ１とＣｖｉ２の小さい方の値を加えて、その経路がノードＮｉに到達した時点でのラベル値（現ラベル）を計算し、ステップＳ５４に進む。

ステップＳ５４では、現ラベルがＮｉのラベル初期値か別の経路で伝播したときにつけられた既存のラベル値であるＮｉＬ１とＮｉＬ２の小さい方より小さいかを判定し、小さければステップＳ５５に進み、大きければNiに伝播する必要はないのでステップＳ３５に戻る。

ステップＳ５５では、Ｎｉまで到達した経路のラベル値Ｌ１とＬ２を現ラベルに更新し、ステップＳ５６でNiの親ノードをPに更新する。ステップＳ５７では、いまPからラベル伝播したNiがターゲットノードＴであるかを判定し、Ｔでなければ図１２のステップＳ７０に進み、ＮｉがＴであれば、経路探索は終点ノードＴに到達したことを意味するので、ステップＳ４４へ進む。

図１２のステップＳ７０では、ノードＰとノードＮｉ間のビアタイプを記録し、ステップＳ７１では、ノードＮｉとビア方向に伝播したところからの道のりＮｉＣＤを更新する（０にする）。PからNiのところでビア方向に伝播しているので道のりは０である。ステップＳ７２では、ノードＰとノードＮｉ間で標準ビアとして使用するビアのノードＮｉのある層側のビアメタル最小幅Ｖｗを求める。

ステップＳ７３では、ノードＮｉのある層の標準配線幅ＮＷとＶｗを比較して、太い方をノードＮｉの配線幅として記録する。

ステップＳ７４では、ノードＮｉを探索リストＭに追加して（ラベルが伝播したノードとして記憶して）、ステップＳ３５に戻る。ノードＮｉの探索リストＭへの追加は、始点Ｓの追加と同じである。

以上、実施例における最小コスト経路探索処理について説明したが、上記のような最小コスト経路探索処理により得られた最小コスト経路情報に基づいて図７のステップＳ２３で、ターゲットノードＴから親ノードＰを順番にたどって始点Ｓに至る配線経路を形成する処理を行う。図１６は、この処理を示すフローチャートである。

探索経路がターゲットノードＴに到達した時のノードをｃＮとする。ステップＳ９０では、現在のノード位置ｃＮの配線幅を現配線幅として記録し、標準配線幅と異なる位置からの道のりをＣＤとして記録する。

ステップＳ９１では、ノードｃＮがNULLでなく、かつノードｃＮの親ノードｐＮがNULLでないかを判定し、一方でもNULLであれば終了し、両方共NULLでなければステップＳ９２に進む。

ステップＳ９２では、ノードｃＮと親ノードｐＮが同層であるか異なる層であるかにより処理が異なる。同層であれば、ノードｃＮから親ノードｐＮまでの同層経路を作成し、ノードｃＮと親ノードｐＮ間の道のりをＣＤに加算し、ＣＤが冗長制約の範囲を超えたら、現配線幅を標準配線幅に更新する。ｃＮとｐＮが異なる層である場合には、ｃＮに冗長ビア接続確定のマークがあるかを判定し、あれば冗長ビアを使用する。そのようなマークがなければ、ｃＮとｐＮの間の標準ビアのｃＮ側のビアメタル幅Ｖｃと現配線幅のギャップ（差）を求めてΔＷとし、ΔＷが冗長ビアルール閾値ΔＷｔｈ以上で現配線幅がビアメタル幅Ｖｃ以上であるか判定し、この条件を満たせば冗長ビアを作成し、それ以外であれば標準ビアを作成する。そして、作成したビアのノードｐＮの層の側の幅と、ｐＮの層の標準配線幅を比較して、太い方を現配線幅として記録し、ＣＤを０にするように更新する。

ステップＳ９３では、ノードｐＮが始点ノードであるか判定して、始点ノードでなければステップＳ９４に進んでｃＮをｐＮに更新してステップＳ９１に戻る。ノードｐＮが始点ノードであれば終了する。

本発明は、多層集積回路の最小コスト経路探索処理を自動で行う方法、それを実現するコンピュータープログラムを記録した媒体、およびそのプログラムを動作させるコンピューター装置に適用される。

図１はレイアウト処理例を示す図である。 図２は最小コスト経路探索処理におけるコスト系列とコスト計算式を説明する図である。 図３は最小コスト経路探索を説明する図である。 図４はストレスマイグレーションを説明する図である。 図５は冗長ビアの設定を説明する図である。 図６は本発明の集積回路の自動配線装置の構成を示すブロック図である。 図７は本発明の実施例の自動配線処理の全体フローである。 図８は従来の最小コスト経路探索処理フローである。 図９は本発明の実施例の最小コスト経路探索処理フローである（その１）。 図１０は本発明の実施例の最小コスト経路探索処理フローである（その２）。 図１１は本発明の実施例の最小コスト経路探索処理フローである（その３）。 図１２は本発明の実施例の最小コスト経路探索処理フローである（その４）。 図１３は初期化処理を説明する図である。 図１４はラベル決定処理フローである。 図１５はビアタイプ決定処理を説明する図である。 図１６はターゲットノードから親ノードをたどって始点ノードに至る配線経路を作成する処理フローである。

符号の説明

１ 始点
２ 終点（ターゲット）
３ 障害物
４−１６ 配線
５０ 記憶装置
５１ 評価値計算回路
５２ 決定回路
５３ ビアタイプ選択回路

Claims (10)

1. コンピュータによる集積回路の配線経路探索方法であって、
   ビアタイプ選択部が、配線の線幅の差に応じて、使用するビアタイプを選択し、
   評価値計算部が、始点ノードから終点ノードへの複数の配線経路についてそれぞれ評価値を計算し、
   決定部が、計算した評価値に基づいて、前記始点ノードから前記終点ノードへの配線経路を決定する集積回路の配線経路探索方法において、
   前記評価値計算部が、ビアを設ける配線経路について、ビアから終点ノードへの配線経路において異なるビアタイプを使用する場合の複数の前記評価値を計算して保持し、
   前記決定部が、保持した前記複数の評価値のうちから、ｍｉｎｉｍｕｍＣｕｔルールを満たすビアタイプを決定する、ことを特徴とする集積回路の配線経路探索方法。
2. 前記ビアタイプ選択部が、ビアからの配線幅の変化点までの距離および配線幅の変化量に応じて、前記ビアタイプを選択する請求項１に記載の集積回路の配線経路探索方法。
3. 前記決定部が、ビアから終点ノードへの配線経路において配線幅が一定である配線長が所定値を超えた時には、前記ビアのビアタイプを決定する請求項２に記載の集積回路の配線経路探索方法。
4. 前記ビアタイプ選択部が、ビアの大きさ及び冗長ビア数に応じて複数の異なるビアタイプが選択する請求項１に記載の集積回路の配線経路探索方法。
5. 始点ノードから終点ノードへの複数の配線経路についてそれぞれ評価値を計算する評価値計算回路と、
   計算した評価値に基づいて、前記始点ノードから前記終点ノードへの配線経路を決定する決定回路と、
   配線の線幅の差に応じて、使用するビアタイプを選択するビアタイプ選択回路と、を備える集積回路の自動配線装置であって、
   前記評価値計算回路は、ビアを設ける配線経路について、ビアから終点ノードへの配線経路において異なるビアタイプを使用する場合の複数の前記評価値を計算して保持し、
   前記決定回路が、保持した前記複数の評価値のうちから、ｍｉｎｉｍｕｍＣｕｔルールを満たすビアタイプを決定する、ことを特徴とする集積回路の自動配線装置。
6. 前記ビアタイプ選択回路は、ビアからの配線幅の変化点までの距離および配線幅の変化量に応じて、前記ビアタイプを選択する請求項５に記載の集積回路の自動配線装置。
7. 前記決定回路は、ビアから終点ノードへの配線経路において配線幅が一定である配線長が所定値を超えた時には、前記ビアのビアタイプを決定する請求項６に記載の集積回路の自動配線装置。
8. 配線の線幅の差に応じて、使用するビアタイプを変える集積回路の配線設計装置を動作させるプログラムであって、
   評価値計算部が、始点ノードから終点ノードへの複数の配線経路についてそれぞれ評価値を計算し、
   決定部が、計算した評価値に基づいて、前記始点ノードから前記終点ノードへの配線経路を決定し、
   前記評価値計算部が、ビアを設ける配線経路について、ビアを設けた以後の前記評価値を、異なるビアタイプを使用する場合の複数の前記評価値を計算して保持し、
   前記決定部が、保持した前記複数の評価値のうちから、ｍｉｎｉｍｕｍＣｕｔルールを満たすビアタイプを決定するように動作させる、ことを特徴とするプログラム。
9. ビアタイプ選択部が、ビアからの配線幅の変化点までの距離および配線幅の変化量に応じて、前記ビアタイプを選択するように動作させる請求項８に記載のプログラム。
10. 前記決定部が、ビアから終点ノードへの配線経路において配線幅が一定である配線長が所定値を超えた時には、前記ビアのビアタイプを決定する請求項９に記載のプログラム。

Images