(57)【要約】【課題】集積回路の遅延分布の計算において、配線または素子間の性能の相関関係を考慮して、推定精度を向上させる。【解決手段】回路情報１１と、集積回路内の配線または素子の性能分布情報１２と、配線または素子間の性能の相関関係情報１３とを入力する（Ｓ１１）。計算点を選択し（Ｓ１２）、性能分布情報１２および相関関係情報１３に基づいて、選択した計算点における遅延分布と、この計算点を含む部分回路における遅延分布の相関関係とを計算する（Ｓ１３）。【選択図】図１
2006155644.tif 000002
【特許請求の範囲】
【請求項１】
入力部と遅延分布計算部を備えた計算機において、設計対象の素子及び配線から構成されている集積回路について、遅延分布を計算する方法であって、
前記入力部が、前記集積回路内の各素子の接続関係を表す回路情報を基にして、回路情報から各素子の接続関係を認識する工程と、
前記遅延分布計算部が前記集積回路に含まれた配線同士、または素子同士の性能の相関関係を表す相関関係情報と前記集積回路に含まれた配線および素子の性能分布を表す性能分布情報と上記各素子の接続関係とを参照して、前記集積回路における各素子の入出力端子及び配線の分岐からなるパスについて遅延分布を計算する工程とを備えた
ことを特徴とする遅延分布計算方法。
【請求項２】
請求項１において、
前記相関関係情報は、前記性能の相関関係として、遅延の相関関係を表すものである
ことを特徴とする遅延分布計算方法。
【請求項３】
請求項１において、
前記相関関係情報は、性能分布における相関係数によって表されたものであることを特徴とする遅延分布計算方法。
【請求項４】
請求項１において、
前記計算する工程は、
前記各素子の接続関係から、すでに遅延分布が計算された点からなる集合に属さない点を、計算点として選択する第１の工程と、
前記第１の工程によって選択された計算点について、前記性能分布情報および相関関係情報に基づいて、遅延分布と、前記集合に属する各点との性能の相関関
係とを計算する第２の工程とを備え、
前記第１および第２の工程を、遅延分布を計算した計算点を前記集合に追加しつつ、繰り返し行うものである
ことを特徴とする遅延分布計算方法。
【請求項５】
請求項１において、
上記計算機は、さらに相関情報計算部を備えたものであって、
前記相関情報計算部が配線同士または素子同士の性能の相関関係とレイアウト上の特徴との関係を表す相関特性情報を用い、前記集積回路のレイアウトを参照して、前記相関関係情報を生成する工程を備えている
ことを特徴とする遅延分布計算方法。
【請求項６】
請求項５において、
前記相関特性情報は、少なくとも、素子間の距離と、性能の相関関係との関係を表したものである
ことを特徴とする遅延分布計算方法。
【請求項７】
請求項５において、
前記相関特性情報は、少なくとも、素子の向きと、性能の相関関係との関係を表したものである
ことを特徴とする遅延分布計算方法。
【請求項８】
請求項５において、
前記相関特性情報は、少なくとも、２本の配線における共通部分の有無または長さと、性能の相関関係との関係を表したものである
ことを特徴とする遅延分布計算方法。
【請求項９】
請求項５において、
前記相関情報計算部が特性評価用集積回路について、各配線または素子の特性を評価し、この評価結果と、前記特性評価用集積回路のレイアウトとを基にして、前記相関特性情報を生成する工程を備えている
ことを特徴とする遅延分布計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＣＭＯＳ・ＬＳＩ等の集積回路の設計において、その性能を評価する技術に関するものであり、特に、遅延分布の計算や、フォールスパスの除去や抽出に関する技術に属する。
【背景技術】
【０００２】
ディープサブミクロン時代におけるＶＬＳＩ設計では、要求された性能を持つ回路が歩留まり良く作成されるように、予め製造プロセスのばらつきを考慮しておく必要が生じている。さらに、ＯＰＣ（Optical Proximity Correction）等の技術に象徴されるように、マスク形状の修正によるばらつきの制御も可能になり、また必要となってきた。したがって、これからのＶＬＳＩ物理設計では、設計時に製造ばらつきを考慮し、各トランジスタに適正な設計マージンを設定して、より高集積・高性能な回路を設計する技術が必要となる。
【０００３】
このような設計技術では、製造ばらつきに起因するクリティカルパス遅延等の回路性能のばらつきを見積もる手法が不可欠となる。クリティカルパス遅延の分布は入力に依存しないので、そのばらつきを見積もる手法は、統計的（Statistical）な静的遅延解析（Static Timing Analysis）手法と言える。
【０００４】
統計的な静的遅延解析手法の１つとして、信号の伝達時間のばらつきに相関がないものとして、最大遅延を見積もるものがある（M.Hashimoto and H.Onodera, "A performance optimization method by gate resizing based on statistical static timing analysis," Proc. Workshop on Synthesis And System Integration of Mixed Technology (SASIMI 2000), pp.77-82, 2000.に開示）。
【０００５】
一方、ＣＭＯＳ論理ゲートで構成された組合せ回路の静的遅延解析手法としては、図９に示すようなある与えられた回路１００を、図１０に示すようなアサイクリックグラフＧ＝（Ｖ，Ｅ）２００によって表現し、このグラフＧ２００において、各出力端子ｖについて、値“０”または“１”を伝搬させるために要する最大遅延を求めるという方法があった。
【０００６】
図１０において、破線の楕円２１１は、回路の主入力端子、主出力端子および論理ゲートの入出力端子に、それぞれ相当する。端子ｖに対応する楕円２１１で囲まれた白抜きの点２１１はｖの０点ｖ０であり、黒点２１２はｖの１点ｖ１である。ｖ０およびｖ１は、それぞれ、対応する端子ｖが信号値“０”および“１”をとることを示す。
【０００７】
また、Ｓは入ってくる枝のないソースの集合であり、Ｔは出て行く枝のないシンクの集合である。ソースは主入力端子に対応する点であり、シンクは主出力端子に対応する点である。また、グラフＧにおけるソースからシンクに至る有向道をパスとする。図１０では各枝の向きは示していないが、全ての枝は左側の点から出て、右側の点に入る有向枝とする。
【０００８】
また図１０において、各矩形２２１，２２２，２２３は回路１００を構成する論理ゲートを表している。矩形内の左側の点は対応する論理ゲートの入力端子に対応し、右側の点は出力端子に対応する。また矩形内の枝は、その論理ゲートの入力を表す点から出て出力を表す点に入る。矩形がＮＡＮＤゲートやＮＯＲゲートを表す場合には、その枝は、ゲート内のｐＭＯＳまたはｎＭＯＳに対応する。枝の付け方は論理ゲートの種類に応じて定まる。また異なる矩形に属する点を結ぶ枝は配線に対応し、ある端子の０点から出た枝ｅ０は他の端子の０点に入り、ある端子の１点から出た枝ｅ１は他の端子の１点に入る。
【０００９】
端子ｖに値“０”を伝搬させるために要する真の最大遅延をｄ０（ｖ）、値“１”を伝搬させるために要する真の最大遅延をｄ１（ｖ）とする。回路の各端子ｖに対するｄ０（ｖ），ｄ１（ｖ）を、グラフＧ上のあるシンクからｖ０，ｖ１までの最大パス長ｄ（ｖ０），ｄ（ｖ１）にそれぞれ対応させる。このため、各枝ｅ＝（ｖ，ｗ）に対して、信号値を端子ｖから端子ｗに伝達するのに要する遅延を、重みｔ（ｅ）として与える。
【００１０】
このようなアサイクリックグラフを用いてシミュレーションを行うことによって、論理回路の遅延解析を比較的簡単な処理によって行うことが可能であった。
【非特許文献１】M.Hashimoto and H.Onodera, "A performance optimization method by gate resizing based on statistical static timing analysis," Proc. Workshop on Synthesis And System Integration of Mixed Technology (SASIMI 2000), pp.77-82, 2000.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、図９に示されるような回路１００において、信号ｚの遅延を計算する際に、信号ｘと信号ｙの遅延が信号ｂの遅延に大きく依存する場合、信号ｘとｙの遅延の間には大きな相関がある。また、配線遅延にばらつきがある場合、信号ｂのファンアウトの信号伝達遅延にも相関がある。したがって、相関を考慮しない統計的解析手法は正確さを欠く可能性が高い。
【００１２】
遅延分布見積もりの精度が悪い場合、実際には確率的にほとんど起こり得ないような，複数の最悪条件が重なった場合であっても、集積回路の正常動作を保証しなければならないので、この結果、オーバーマージンを含んだ設計にならざるを得ない。このため、設計された集積回路について、面積や消費電力等のコストを必要以上に増大させてしまうという問題があった。
【００１３】
前記の問題に鑑み、本発明は、集積回路の遅延分布を計算する方法として、実際の回路に即して、より正確な遅延分布を計算可能にすることを課題とする。
【００１４】
また、従来の技術では、他の問題もある。
【００１５】
従来の方法では、実際にはシミュレーションの対象となり得ないパス（フォールスパス）を含んでいる。このため、必要以上に計算時間がかかる、または、遅延見積もり精度が低下する等の問題点があった。
【００１６】
フォールスパスには、論理的にそのパスに信号を伝搬させるような入力が存在せず、実際には活性化されることがない論理的フォールスパスと、そのパスを活性化する入力が存在するが、実際にはそのような入力は生じないため活性化されることのない機能的フォールスパスとがある。例えば、図１１において、相反する信号ｚ，／ｚで制御される２個のＡＮＤゲートＧ１，Ｇ６を通るようなパスにおいて、Ｇ１のｚ以外の入力ｘを“１”にし、Ｇ６の出力ｙを“１”にするようなパスが、論理的フォールスパスに相当する。また、例えば（Ｘ，Ｍ，Ｙ）という演算器の系列と（Ａ，Ｍ，Ｂ）という演算器の系列の演算が必要な場合に、乗算器Ｍを共有化すると、（Ａ，Ｍ，Ｙ）または（Ｘ，Ｍ，Ｂ）という演算器の系列が生まれる。ところが、演算器を同時に動作させないような仕様であるとき、これらの系列が機能的フォールスパスに相当する。
【００１７】
また、論理的フォールスパスを、人間によって発見するのは、回路規模が大きいことからみて実際上不可能であり、計算機を用いて自動的に発見する方法が不可欠である。
【００１８】
前記の課題に鑑み、本発明は、集積回路を評価する方法として、フォールスパスの影響を回避し、評価精度をより向上させることを課題とする。また、設計対象の集積回路から、フォールスパスを抽出する手法を提案する。
【課題を解決するための手段】
【００１９】
前記の課題を解決するために、請求項１の発明が講じた解決手段は、入力部と遅延分布計算部を備えた計算機において、設計対象の素子及び配線から構成されている集積回路について、遅延分布を計算する方法であって、前記入力部が、前記集積回路内の各素子の接続関係を表す回路情報を基にして、回路情報から各素子の接続関係を認識し、前記遅延分布計算部が前記集積回路に含まれた配線同士、または素子同士の性能の相関関係を表す相関関係情報と前記集積回路に含まれた配線および素子の性能分布を表す性能分布情報と上記各素子の接続関係とを参照して、前記集積回路における各素子の入出力端子及び配線の分岐からなるパスについて遅延分布を計算するものである。
【００２０】
請求項１の発明によると、集積回路の遅延分布を計算する際に、この集積回路に含まれた配線同士、または素子同士の性能の相関関係を表す相関関係情報が参照される。これにより、集積回路の遅延分布を、精度良く計算することができる。
【００２１】
そして、請求項２の発明では、前記請求項１の発明における相関関係情報は、前記性能の相関関係として、遅延の相関関係を表すものとする。
【００２２】
また、請求項３の発明では、前記請求項１の発明における相関関係情報は、性能分布における相関係数によって表されたものとする。
【００２３】
そして、請求項４の発明では、前記請求項１の発明における計算工程は、前記グラフからすでに遅延分布が計算された点からなる集合に属さない点を計算点として選択する第１の工程と、前記第１の工程によって選択された計算点について、前記性能分布情報および相関関係情報に基づいて遅延分布と前記集合に属する各点との性能の相関関係とを計算する第２の工程とを備え、前記第１および第２の工程を、遅延分布を計算した計算点を前記集合に追加しつつ、繰り返し行うものとする。
【００２４】
また、請求項５の発明では、前記請求項１の発明において、配線同士または素子同士の性能の相関関係とレイアウト上の特徴との関係を表す相関特性情報を用い、前記集積回路のレイアウトを参照して、前記相関関係情報を生成する工程を備えているものとする。
【００２５】
そして、請求項６の発明では、前記請求項５の発明における相関特性情報は、少なくとも、素子間の距離と、性能の相関関係との関係を表したものとする。
【００２６】
また、請求項７の発明では、前記請求項５の発明における相関特性情報は、少なくとも、素子の向きと、性能の相関関係との関係を表したものとする。
【００２７】
また、請求項８の発明では、前記請求項５の発明における相関特性情報は、少なくとも、２本の配線における共通部分の有無または長さと、性能の相関関係との関係を表したものとする。
【００２８】
また、請求項９の発明では、前記請求項５の発明において、特性評価用集積回路について、各配線または素子の特性を評価し、この評価結果と、前記特性評価用集積回路のレイアウトとを基にして、前記相関特性情報を生成する工程を備えているものとする。
【発明の効果】
【００２９】
以上のように本発明によると、集積回路の遅延分布の計算において、配線または素子間の性能の相関関係が考慮されるので、遅延見積もり精度が向上する。これにより、設計する集積回路について、過剰なマージンを除去することができ、不要な面積や消費電力等を削減することができる。
【００３０】
また、集積回路の評価において、フォールスパスを除去することによって、計算時間の短縮と、遅延見積もり精度の向上という効果が得られる。
【発明を実施するための最良の形態】
【００３１】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００３２】
（第１の実施形態）
本発明の第１の実施形態では、回路の各端子ｖにおける最大遅延値の分布の計算を行う方法について、説明する。以下の説明では、端子ｖに値“０”を伝搬させるために要する真の最大遅延をｄ０（ｖ）、値“１”を伝搬させるために要する真の最大遅延をｄ１（ｖ）とする。
【００３３】
まず最初に、与えられた回路を、図１０に示すようなアサイクリックグラフＧ＝（Ｖ，Ｅ）によって表現する。各枝ｅ＝（ｖ，ｗ）に対して、信号値を端子ｖから端子ｗに伝達するために要する遅延（枝ｅの重み）ｔ（ｅ）を、確率変量として扱う。その分布は正規分布Ｎ（μ，σ2）であるものとし、遅延ｔ（ｅ）の平均μおよび分散σ2をそれぞれμ（ｅ）および分散σ2（ｅ）と表す。すなわち、遅延ｔ（ｅ）の確率密度関数ｆ（ｔ（ｅ））は、
【００３４】
【数１】
2006155644.tif 000003
【００３５】
で与えられる。
【００３６】
次に、配線に対応した枝ｅの遅延ｔ（ｅ）について説明する。ここでは、配線遅延ｔ（ｅ）も正規分布で示されるばらつきを持つものとする。
【００３７】
いま、配線に対応した枝が点ｖ，ｗの０点同士を結ぶ枝ｅ０＝（ｖ０，ｗ０）である場合、点ｖ，ｗの１点同士を結ぶ枝ｅ１＝（ｖ１，ｗ１）が存在するが、その遅延ｔ（ｅ１）のばらつきは遅延ｔ（ｅ０）のばらつきと独立とはいえない。また、点ｖから２本以上の枝ｅ’＝（ｖ，ｗ’），ｅ”＝（ｖ，ｗ”）が出る場合（すなわちファンアウトを持つ場合）も、枝ｅ’，ｅ”の遅延ｔ（ｅ’），ｔ（ｅ”）のばらつきは独立ではない。そこで、このような同一ネットに対応する枝の組（ｅ’，ｅ”）に対して、相関係数ｒ（ｅ’，ｅ”）≠０を導入する。配線に対応する枝ｅ’の遅延と、異なるネットの配線に対応する枝または配線に対応しない（論理ゲートに含まれる）枝ｅ”の遅延とは独立であり、相関係数ｒ（ｅ’，ｅ”）＝０とする。
【００３８】
次に、論理ゲートに対応した枝とその遅延について説明する。論理ゲートの出力端子ｗに“０”または“１”を伝搬するために要する最大遅延を、グラフＧ上の点ｗの０点ｗ０または１点ｗ１への最大パス長ｄ（ｗ０）およびｄ（ｗ１）に対応させるために、どのように枝を作成すればよいかを考える。
【００３９】
まず、論理ゲートがＡＮＤゲートの場合を考える。ＡＮＤゲートの入力端子をｖi （１≦ｉ≦ｋ）とし、出力端子をｗとする。出力ｗを“１”にするために要する遅延ｄ（ｗ１）は、全ての入力ｖi が“１”になってからの時間であるから、全ての入力ｖi が“１”という条件の下で、
ｄ（ｗ１）＝ｍａｘ［ｄ（ｖi１）＋ｔ（ｅi１）｜１≦ｉ≦ｋ］……（２）
によって計算できる。そこで、各入力ｖi の１点ｖi１からｗの１点ｗ１に枝ｅi１＝（ｖi１，ｗ１）を付し、枝ｅi１の遅延ｔ（ｅi１）は入力ｖiが“１”になってから出力ｗが“１”になるまでの時間とする。
【００４０】
一方、ＡＮＤゲートの出力ｗを“０”にするために要する遅延ｄ（ｗ０）は、一つの入力が“０”になる時間によって決まる。したがって、ｖi以外の各入力ｖj（ｊ≠ｉ，１≦ｊ≦ｋ）が“０”であり、ｄ（ｖi０）＋ｔ（ｅi０）≦ｄ（ｖj０）＋ｔ（ｅj０）であるとき、
ｄ（ｗ０）＝ｄ（ｖi０）＋ｔ（ｅi０）
となるから、ｄ（ｗ０）は、
ｍｉｎ［ｄ（ｖi０）＋ｔ（ｅi０）｜１≦ｉ≦ｋ  ］  ……（３）
で与えられるようにみえる。
【００４１】
しかし、ｖi以外の全ての入力ｖjが１の場合にも、
ｄ（ｗ０）＝ｄ（ｖi０）＋ｔ（ｅi０）
となるから、各１≦ｉ≦ｋに対して、ｖi以外の全ての入力ｖjが“１”という条件が成り立つ場合には、ｗを“０”にするために要する遅延の中で最大のものｄ（ｗ０）は、
ｄ（ｗ０）＝ｍａｘ［ｄ（ｖi０）＋ｔ（ｅi０）｜１≦ｉ≦ｋ］……（４）
で得られる。
【００４２】
そこで、各入力ｖiの０点ｖi０から出力ｗの０点ｗ０に枝ｅi０＝（ｖi０，ｗ０）を付し、枝ｅi０の遅延ｔ（ｅi０）は入力ｖiが“０”になってから出力ｗが“０”になるまでの時間とする。
【００４３】
このようにしてＡＮＤゲート内部に枝を付加し、その遅延を定めることによって、遅延ｄ（ｗ１），ｄ（ｗ０）のいずれも最大値演算を用いて計算することができる。
【００４４】
次に、論理ゲートがＮＡＮＤゲートの場合について、具体的に説明する。この場合、上述の式（２），（４）において、出力ｗを“１”にする場合と“０”にする場合とを入れ替えるだけなので、遅延ｄ（ｗ１），ｄ（ｗ０）は、
ｄ（ｗ１）＝ｍａｘ［ｄ（ｖi０）＋ｔ（ｅi０）｜１≦ｉ≦ｋ］……（５）
ｄ（ｗ０）＝ｍａｘ［ｄ（ｖi１）＋ｔ（ｅi１）｜１≦ｉ≦ｋ］……（６）
で計算できることが分かる。
【００４５】
したがって、各入力ｖiの０点ｖi０から出力ｗの１点ｗ１に枝ｅi０＝（ｖi０，ｗ１）を付し、各入力ｖiの１点ｖi１から出力ｗの０点ｗ０に枝ｅi１＝（ｖi１，ｗ０）を付ける。枝ｅi０の遅延ｔ（ｅi０）およびｅi１の遅延ｔ（ｅi１）は、それぞれ入力ｖiが“０”になってから出力ｗが“１”になるまでの時間、および、入力ｖiが“１”になってから出力ｗが“０”になるまでの時間である。論理ゲートがインバータの場合は、ｋ＝１とすればよい。
【００４６】
論理ゲートがＯＲ（またはＮＯＲ）ゲートの場合も、同様の議論から、ｄ（ｗ０）（ＮＯＲゲートの場合はｄ（ｗ１））およびｄ（ｗ１）（ＮＯＲゲートの場合はｄ（ｗ０））は、
ｄ（ｗ０）＝ｍａｘ［ｄ（ｖi０）＋ｔ（ｅi０）｜１≦ｉ≦ｋ］……（７）
ｄ（ｗ１）＝ｍａｘ［ｄ（ｖi１）＋ｔ（ｅi１）｜１≦ｉ≦ｋ］……（８）
によって計算できる。
【００４７】
したがって、ＯＲゲートに対する枝の付け方は、ＡＮＤゲートの場合と同様であり、ＮＯＲゲートに対する枝の付け方は、ＮＡＮＤゲートの場合と同様である。ＣＭＯＳ複合ゲートの場合も、ＮＡＮＤ（ＮＯＲ）ゲートの場合と同様に枝を付せばよい。
【００４８】
しかしながら、ＸＯＲゲートの場合には、入力ｖiの値“０”が出力ｗの値を“０”にすることもあれば“１”にすることもある。また、入力ｖiの値“１”が出力ｗの値を“０”にすることもあれば“１”にすることもある。このため、入力ｖiの０点ｖi０から出力ｗの０点ｗ０および１点ｗ１に、枝ｅi００＝（ｖi０，ｗ０）およびｅi０１＝（ｖi０，ｗ１）をそれぞれ付し、入力ｖiの１点ｖi１から出力ｗの０点ｗ０および１点ｗ１に、枝ｅi１０＝（ｖi１，ｗ０）およびｅi１１＝（ｖi１，ｗ１）をそれぞれ付す。これらの枝ｅiｂｂ’＝（ｖiｂ，ｗｂ’）の遅延ｔ（ｅiｂｂ’）は、入力ｖiがｂになってから出力ｗがｂ’になるまでの時間である。ここで、ｂ，ｂ’はいずれも、“０”または“１”のいずれかを表す。
【００４９】
このようにして論理ゲート内部の枝を生成すれば、アサイクリックグラフＧ＝（Ｖ，Ｅ）において各シンクへの最大パス長を求めたとき、これがクリティカルパス遅延の候補となる。
【００５０】
次に、論理ゲート内の遅延のばらつきについて説明する。
【００５１】
ＮＡＮＤゲート、ＮＯＲゲートまたはＣＭＯＳ複合ゲートの場合、枝の遅延ｔ（ｅi０）およびｔ（ｅi１）は、そのゲートの入力ｖi が接続するｐＭＯＳおよびｎＭＯＳに付随したスイッチング遅延と考えれば良い。このようなスイッチング遅延は、トランジスタが飽和領域にある時間であり、飽和ドレイン電流Ｉdsat、駆動すべき負荷容量Ｃ、およびゲート電圧の立ち上がり速度などによって決まる。飽和ドレイン電流Ｉdsat はばらつきを持ち、それはゲート長Ｌのばらつきに最も依存する。このゲート長Ｌのばらつきは、しきい値電圧Ｖthの場合と同様、ほぼ正規分布で表されるので、スイッチング遅延ｔ（ｅiｂ）も正規分布Ｎ（μ，σ2）となるものとする。
【００５２】
ゲート長Ｌのばらつきは、隣り合うポリシリコンゲートの間隔Ｐ、トランジスタゲート幅Ｗ、拡散領域の長さＬDIFなどに影響される。したがって、これらの値とゲート長Ｌのばらつきとの関係が見いだせたら、レイアウトパターンから間隔Ｐ，ゲート幅Ｗ，拡散領域長ＬDIFの値を求め、ゲート長Ｌのばらつきを予測することができ、それからスイッチング遅延のばらつきを見積もることができる。
【００５３】
このような遅延のばらつきは、隣り合うポリシリコンゲートの間隔に影響されるため、隣り合うトランジスタに対応する枝の遅延のばらつきは独立ではなくなる。そこで、同一論理ゲートに含まれる枝の組（ｅ’，ｅ”）に対して、相関係数ｒ（ｅ’，ｅ”）≠０を導入する。ＮＡＮＤゲートやＮＯＲゲート以外の論理ゲートにも、このような相関を考える。相関がない場合には、相関係数ｒ（ｅ’，ｅ”）＝０としておけばよい。
【００５４】
相関があるのは同じ論理ゲート内に含まれる枝同士だけなので、異なるゲートに含まれる枝ｅ’，ｅ”の遅延は独立であり、ｒ（ｅ’，ｅ”）＝０とする。また、ＮＡＮＤゲートやＮＯＲゲートの場合には、異なる種類のＭＯＳに対応した枝ｅ’，ｅ”の遅延も独立である。
【００５５】
遅延のばらつきに相関があるのは、同一ネットの配線に対応した枝間ならびに一つの論理ゲート内の枝間だけであるから、遅延に相関のある枝を通るような（有向）パスは存在しない。したがって、一つのパス上のどのような枝に対しても、それらの遅延は独立である。
【００５６】
次に、論理ゲートおよび配線の遅延分布およびそれらの相関関係を用いて、対象とする回路の遅延の最大値の分布計算について記述する。
【００５７】
相関係数Ｒ［ｘ，ｙ］＝ρを持つ確率変数ｘおよびｙが、それぞれ正規分布Ｎ（μ1，σ12）およびＮ（μ2，σ22）をしているとき、ｔ（＝ｍａｘ［ｘ，ｙ］）の平均Ｅｘｐ［ｔ］と分散Ｖａｒ［ｔ］は、ｔが２変数の正規分布をすると近似すると、σ1−σ2＝ρ−１＝０でないという条件で、
Ｅｘｐ［ｔ］＝μ1・Φ（β）＋μ2・Φ（−β）＋α・φ（β）……（９）
Ｖａｒ［ｔ］＝（μ12＋σ12）・Φ（β）＋（μ22＋σ22）・Φ（−β）
＋（μ1＋μ2）・α・φ（β）−Ｅｘｐ［ｔ］2……（１０）
で求められる。ここで、
【００５８】
【数２】
2006155644.tif 000004
【００５９】
とする（C.E. Clark, "The greatest of a finite set of random variables" Operations Research, vol.9, pp.145-152, 1961. に開示）。
【００６０】
さらに、ｔと、正規分布する確率変数ｚとの相関係数Ｒ［ｔ，ｚ］は、ｚとｘおよびｚとｙとの相関係数が、それぞれＲ［ｘ，ｚ］＝ρ１，Ｒ［ｙ，ｚ］＝ρ２であるとき、３変数ｘ，ｙ，ｚの正規分布を用いて、
【００６１】
【数３】
2006155644.tif 000005
【００６２】
で与えられる。
【００６３】
これらを利用する上で、確率に関する以下の式が必要となる。２変量ｘ1，ｘ2の確率密度関数をｆ（ｘ1，ｘ2）としたとき、ｘ1＋ｘ2の平均Ｅｘｐ［ｘ1＋ｘ2］と分散Ｖａｒ［ｘ1＋ｘ2 ］は、
【００６４】
【数４】
2006155644.tif 000006
【００６５】
から、下に示す式（１８），（１９）によって求められる。
【００６６】
Ｅｘｐ［ｘ1＋ｘ2］＝Ｅｘｐ［ｘ1］＋Ｅｘｐ［ｘ2］……（１８）
Ｖａｒ［ｘ1＋ｘ2］＝Ｖａｒ［ｘ1］＋Ｖａｒ［ｘ2］＋２Ｃｏｖ［ｘ1，ｘ2］                                                  ……（１９）
ここで、Ｃｏｖ［ｘ1，ｘ2］は共分散であり、相関係数をＲ［ｘ1，ｘ2］とすると、次式（２０）で定義されている。
【００６７】
Ｃｏｖ［ｘ1，ｘ2］＝ＳＱＲＴ［Ｖａｒ［ｘ1］Ｖａｒ［ｘ2］］・Ｒ［ｘ1，ｘ2］……（２０）
３変量ｘ1，ｘ2，ｘ3の確率密度関数をｆ（ｘ1，ｘ2，ｘ3）とすると、ｘ1＋ｘ2とｘ3の共分散Ｃｏｖ［ｘ1＋ｘ2，ｘ3］は、
【００６８】
【数５】
2006155644.tif 000007
【００６９】
から、次式（２２）で計算することができる。
【００７０】
Ｃｏｖ［ｘ1＋ｘ2，ｘ3 ］＝Ｃｏｖ［ｘ1，ｘ3］＋Ｃｏｖ［ｘ2，ｘ3］
……（２２）
与えられたグラフには、直列枝が複数存在する。そこでここでは、上述した式を利用して、２本の直列枝ｅ’＝（ｕ，ｖ），ｅ”＝（ｖ，ｗ）を１本の枝ｅ＊＝（ｕ，ｗ）に縮約する手順を示す。
【００７１】
グラフの作り方から明らかに、遅延ｔ（ｅ’）とｔ（ｅ”）は独立であり、ｔ（ｅ＊）＝ｔ（ｅ’）＋ｔ（ｅ”）とすれば良いから、次の式（２３），（２４）が成り立つ。
【００７２】
μ（ｅ＊）＝μ（ｅ’）＋μ（ｅ”）      ……（２３）
σ2（ｅ＊）＝σ2（ｅ’）＋σ2（ｅ”）  ……（２４）
さらに、上述の式（２０），（２２）から、ｔ（ｅ＊）と他の枝ｅの遅延ｔ（ｅ）との相関係数ρ（ｅ＊，ｅ）は、
【００７３】
【数６】
2006155644.tif 000008
【００７４】
で得られる。これは、
【００７５】
【数７】
2006155644.tif 000009
【００７６】
で確かめられる。このようにして直列枝の縮約を行っても、パス上の枝の遅延の独立性は変化しない。すなわち、ｅとｅ＊を同時に通るようなパスがある場合には、ρ（ｅ＊，ｅ）＝０  である。
【００７７】
ｎ変量正規分布の確率密度関数ｆ（ｘ1，ｘ2，．．．，ｘn）は、
【００７８】
【数８】
2006155644.tif 000010
【００７９】
で与えられる。ここで、（ｘ−μ）はベクトル、（ｘ−μ）τ は（ｘ−μ）の転置ベクトルであり、（ｘ−μ）τ ＝（ｘ1−μ1  ｘ2−μ2  ．．．  ｘn−μn）である。また、σijは、
【００８０】
【数９】
2006155644.tif 000011
【００８１】
で示される対称行列であり、σij＝（σij）-1である。また｜σij｜はその行列式である。ここで、μ，σ2，ρはそれぞれ平均値、分散、相関係数に相当する。
【００８２】
相関係数ρの２変量正規分布の確率密度関数ｆ（ｘ1，ｘ2）は、
【００８３】
【数１０】
2006155644.tif 000012
【００８４】
で与えられ、相関係数ρ＝１のとき、２変量ｘ1，ｘ2 の間には、
【００８５】
【数１１】
2006155644.tif 000013
【００８６】
なる関係がある。
【００８７】
そして、ｎ変量の確率密度関数をｆ（ｘ1，ｘ2，．．．，ｘn）とすると、全ての変量がＤ以下である確率Ｐｒｏ［ｍａｘ［ｘ1，ｘ2，．．．，ｘn ］≦Ｄ］は、
【００８８】
【数１２】
2006155644.tif 000014
【００８９】
で与えられる。また、確率Ｐｒｏ［ｍａｘ［ｘ1，ｘ2，．．．，ｘn］≦Ｄ］が指定された値Ｙ以下になるようなＤの値は、
【００９０】
【数１３】
2006155644.tif 000015
【００９１】
で示される積分方程式を解くことによって、求められる。
【００９２】
＜遅延分布計算＞
次に、上述した関係を用いて集積回路の遅延分布を求める方法について説明する。
【００９３】
すなわち、シンク集合Ｔの点ｖ（ｖ∈Ｔ）への最大遅延ｄ（ｖ）の分布（すなわち平均Ｅｘｐ［ｄ（ｖ）］と分散Ｖａｒ［ｄ（ｖ）］）と、シンク集合Ｔの点ｖ，ｗ（ｖ，ｗ∈Ｔ）間の遅延の相関係数Ｒ［ｄ（ｖ），ｄ（ｗ）］を求める。これらが求められれば、クリティカルパス遅延ｍａｘ［ｄ（ｖ）｜ｖ∈Ｔ］がＤ以下である確率は、全てのｄ（ｖ）が、｜Ｔ｜変量の正規分布をするものとして、式（３１）から求められる。また、その分布を調べる場合には、式（３１）をＤで微分し、
【００９４】
【数１４】
2006155644.tif 000016
【００９５】
で求めることができる。
【００９６】
これらは数値計算によって求めることができるが、この場合、非常に計算時間がかかる。これに対して、式（３３）を正規分布で近似すれば、以下に述べる手法（式（９）〜式（１５））を繰り返し用いて、その分布を高速に計算することができる。
【００９７】
以下では、各点ｖへの最大遅延（あるソースｕ（ｕ∈Ｓ）からｖへの最長パス長）をｄ（ｖ）、その平均および分散をそれぞれｍ（ｖ）（＝Ｅｘｐ［ｄ（ｖ）］），ｓ（ｖ）（＝Ｖａｒ［ｄ（ｖ）］）と表す。さらに、２点ｖ，ｗへの最大遅延ｄ（ｖ），ｄ（ｗ）の間の相関係数をｒ（ｖ，ｗ）（＝Ｒ［ｄ（ｖ），ｄ（ｗ）］と表す。また、点ｖへの最大遅延ｄ（ｖ）と枝ｅの遅延ｔ（ｅ）との間の相関係数をｃ（ｖ，ｅ）（＝Ｒ［ｄ（ｖ），ｔ（ｅ）］）と表す。
【００９８】
図１は本発明の第１の実施形態に係る遅延分布計算方法を示すフローチャートである。本実施形態では、アサイクリックグラフＧ＝（Ｖ，Ｅ）において、位相幾何学的順序（topological order ）で、ソースから各点ｖ（ｖ∈Ｖ）への最大遅延ｄ（ｖ）の分布を計算する。このために、以下の条件（Ａ）（Ｂ）（Ｃ）が常に成り立つような点の集合Ｆｒｏｎｔを考える。
【００９９】
（Ａ）各点ｖ（ｖ∈Ｆｒｏｎｔ）について、最大遅延ｄ（ｖ）の平均ｍ（ｖ）と分散ｓ（ｖ）が既知である。
【０１００】
（Ｂ）任意の２点ｖ，ｕ（ｖ，ｕ∈Ｆｒｏｎｔ）に対して、最大遅延ｄ（ｖ），ｄ（ｕ）の相関係数ｒ（ｖ，ｕ）が既知である。
【０１０１】
（Ｃ）各点ｖ（ｖ∈Ｆｒｏｎｔ）に対して、最大遅延ｄ（ｖ）と任意の枝ｅ（ｅ∈Ｅ）の遅延ｔ（ｅ）との相関係数ｃ（ｖ，ｅ）が既知である。
なお、直列枝は、すでに述べた手法によって、１本の枝に縮約されているものとする。
【０１０２】
まず、入力工程Ｓ１１において、集積回路内の各素子の接続関係を表す回路情報１１、集積回路に含まれた配線や論理ゲート等各素子の性能分布を表す性能分布情報１２、および配線および素子の遅延分布の相関関係を表す相関関係情報１３を入力する。回路情報１１を基にして、当該集積回路を表すアサイクリックグラフが生成される。
【０１０３】
次に、計算点選択工程Ｓ１２において、遅延分布計算を行う対象となる計算点の選択を行う。当初は、Ｆｒｏｎｔ＝Ｓ（ソースの集合）とし、各点ｕ（ｕ∈Ｓ）に対して、ｍ（ｕ）＝ｓ（ｕ）＝０とする。このとき、集合Ｆｒｏｎｔの異なる点間の相関係数は全て０としておけば良いので、上記の条件は成立する。なお、主入力の信号伝達時刻のズレやばらつきがあるような場合には、それらを予めここに組み込むこともできる。その後の繰り返しでは、位相幾何学的順序に基づいて、アサイクリックグラフから１点を選択する。
【０１０４】
次に、部分回路遅延分布計算工程Ｓ１３において、計算点選択工程Ｓ１２において選択された計算点における遅延分布と、すでに選択された点との相関関係の計算を行う。そして、上の条件（Ａ）（Ｂ）（Ｃ）を満たしつつ、新たな点ｗを集合Ｆｒｏｎｔに入れる。
【０１０５】
いま、集合Ｆｒｏｎｔの点をｖi（ｉ＝１，２，…，ｋ，…，ｈ）とし、入ってくる枝は全て集合Ｆｒｏｎｔから来るような点ｗを考える。記述を簡単化するため、点ｗに入ってくる枝をｅi＝（ｖi，ｗ）（ｉ＝１，２，…，ｋ）とする。また、出ていく枝（ｖi，ｕ）の終点ｕが全てＦｒｏｎｔ∪［ｗ］に含まれてしまうような点ｖi（ｖi∈Ｆｒｏｎｔ）の集合をＥｌｉｍｉｎａｔｅと記す。
【０１０６】
あるソースから枝ｅi＝（ｖi，ｗ）を通って点ｗに至るパスの最大遅延をｄ’i（ｗ）と表すと、
ｄ’i（ｗ）＝ｄ（ｖi）＋ｔ（ｅi）  ……（３４）
であるから、式（１８）〜（２０）を用いて、ｄ’i（ｗ）の平均ｍ’i（ｗ）と分散ｓ’i（ｗ）を、
【０１０７】
【数１５】
2006155644.tif 000017
【０１０８】
を用いて求めることができる。
【０１０９】
ここで、枝ｅiの遅延は、ｖiに至るどのようなパス上の枝の遅延とも独立であるから、ｄ（ｖi）とｔ（ｅi）も独立であり、ｃ（ｖi，ｅi）＝０  である。したがって、
ｓ’i（ｗ）＝Ｖａｒ［ｄi（ｗ）］
＝ｓ（ｖi）＋σ2 （ｅi）……（３６）
の関係が成立する。
【０１１０】
また、式（２０），（２２）から、ｓ（ｕ）≠０なる任意の点ｕ（ｕ∈Ｆｒｏｎｔ）および任意の枝ｅ（ｅ∈Ｅ）に対して、
【０１１１】
【数１６】
2006155644.tif 000018
【０１１２】
であるから、
【０１１３】
【数１７】
2006155644.tif 000019
【０１１４】
の関係が成立する。ここでｓ（ｕ）＝０の場合には、ｒ’i（ｗ，ｕ）＝０としておく。
【０１１５】
次に、ソースｖ０から枝ｅj ＝（ｖj ，ｗ）（ｊ＝１，２，…，ｉ）のいずれかを通って点ｗに至るパスの最大遅延をｄi（ｗ）とする。すなわち、
ｄi（ｗ）＝ｍａｘ［ｄj’（ｗ）｜１≦ｊ≦ｉ］……（４１）
とする。
【０１１６】
明らかに、ｄ1 （ｗ）＝ｄ’1 （ｗ）である。そこで、ｄi-1（ｗ）に関する分布が求まっているとき、すなわち、
ｍi-1（ｗ）＝Ｅｘｐ［ｄi-1（ｗ）］……（４２）
ｓi-1（ｗ）＝Ｖａｒ［ｄi-1（ｗ）］……（４３）
ｒi-1（ｗ，ｕ）＝Ｒ［ｄi-1（ｗ），ｄ（ｕ）］……（４４）
ｃi-1（ｗ，ｅ）＝Ｒ［ｄi-1（ｗ），ｔ（ｅ）］……（４５）
が既知のとき、次式（４６）〜（４９）を求めることを考える。
【０１１７】
ｍi（ｗ）＝Ｅｘｐ［ｄi（ｗ）］……（４６）
ｓi（ｗ）＝Ｖａｒ［ｄi（ｗ）］……（４７）
ｒi（ｗ，ｕ）＝Ｒ［ｄi（ｗ），ｄ（ｕ）］……（４８）
ｃi（ｗ，ｅ）＝Ｒ［ｄi（ｗ），ｔ（ｅ）］……（４９）
このため、式（５０）を用いる。
【０１１８】
ｄi（ｗ）＝ｍａｘ［ｄi-1（ｗ），ｄ’i（ｗ）］……（５０）
ｉ＝２の場合から順にｉ＝ｋまで計算し、ｄ（ｗ）の分布が求まれば、点ｗを集合Ｆｒｏｎｔに入れることができる。点ｗを集合Ｆｒｏｎｔに入れたとき、新たな集合Ｆｒｏｎｔ＝（Ｆｒｏｎｔ−Ｅｌｉｍｉｎａｔｅ）∪［ｗ］に対して上の条件（Ａ）（Ｂ）（Ｃ）が成立することが分かる。
【０１１９】
ｄi（ｗ）  の分布は、式（９）〜  式（１５）、すなわち、
α＝ＳＱＲＴ［ｓi-1（ｗ）＋ｓ’i（ｗ）−２ＳＱＲＴ［ｓi-1（ｗ）ｓ’i（ｗ）］・ｒ’i （ｗ，ｗ）］……（５１）
を用いて計算する。ここで、ｒ’i（ｗ，ｗ）＝Ｒ［ｄi-1（ｗ），ｄ’i（ｗ）］は、
【０１２０】
【数１８】
2006155644.tif 000020
【０１２１】
から計算できる。したがって、
【０１２２】
【数１９】
2006155644.tif 000021
【０１２３】
とすれば、
【０１２４】
【数２０】
2006155644.tif 000022
【０１２５】
によって、ｄi（ｗ）の分布を計算することができる。したがって、回路内の点ｗを集合Ｆｒｏｎｔに入れるという操作を繰り返すことにより、回路のすべての点を集合Ｆｒｏｎｔに入れることができ、相関を考慮した回路の遅延分布を計算することができる。
【０１２６】
このように、集合Ｅｌｉｍｉｎａｔｅを集合Ｆｒｏｎｔから除去し、点ｗを集合Ｆｒｏｎｔに入れるという操作を繰り返し、最終的にＦｒｏｎｔ＝Ｔが成立すれば、処理は終了である。この判断は、終了条件判断工程Ｓ１４において行う。
【０１２７】
すべての点の遅延分布計算が終了したとき、出力工程Ｓ１５において、出力端子の遅延分布情報１４、すなわちシンクＴの各点の遅延の平均および分散を出力し、処理を終了する。そうでない場合は、計算点選択工程Ｓ１２に戻って処理を続ける。
【０１２８】
なお、本実施形態では、相関関係情報は、遅延分布における相関係数によって表すものとしたが、遅延分布の代わりに遅延値そのものの相関度によって表すようにしてもよい。また、遅延以外の性能に関する相関関係を用いて、遅延分布の計算を行うことも可能である。
【０１２９】
例えば、相関特性情報を用いて、設計対象の集積回路のレイアウトを参照して、相関関係情報を生成するようにしてもよい。ここで、「相関特性情報」とは、配線または素子の性能の相関関係と、レイアウト上の特徴との関係を表すものである。図１２は相関関係情報を生成する方法を示すフローチャートである。
【０１３０】
素子の特性情報としては、遅延をはじめ、トランジスタのゲート幅、ゲート長、酸化膜厚、イオン注入濃度、ソースドレイン間の飽和電流、しきい値電圧等がある。これらのプロセスばらつきには、全くランダムな要因と、形状、位置、向き等のレイアウト情報に依存して変化する要因がある。例えば、トランジスタ拡散層のイオン注入濃度は、製造時の注入装置の方向に依存するので、同じ向きに配置した方が同じ特性が得られやすい。また、イオン注入濃度や酸化膜厚等は配置位置に依存して連続的に変化する傾向があるので、２つの素子の特性を比較した場合、近くに配置するほど類似した特性を示す確率が高い。さらに、ゲート幅やゲート長は、例えば他のゲートとの距離等周囲のレイアウト形状に依存して変化しやすい。また、同じ論理ゲートに対する異なるパスの遅延や、共通配線が途中で分岐する場合の配線遅延は、そのばらつきの相関関係は強いと考えられる。
【０１３１】
相関特性情報の例を示す。
（１）２つの素子間の距離Ｄと２つの素子の遅延分布の相関係数Ｒとの間に、
Ｒ＝ａ・ｅｘｐ（−Ｄ／ｂ）という関係を持つ場合（ａ，ｂは定数）
（２）２つの素子が同じ向きに配置されている場合の相関係数はｃであるが異なる向きの場合はｅである場合（ｃ，ｅは定数）
（３）配線が途中で分岐している場合、全配線長に占める共通部分の割合をｗとしたとき、互いの配線遅延の相関関係は、Ｒ＝ｆ・ｗである場合（ｆは定数）
（４）同じ素子に起因する素子遅延の相関係数はｇであるが、別素子のであればｈである場合（ｇ，ｈは定数）
等である。これらの関係式の一部を用いてもよいし、組み合わせた式として用いてもよい。
【０１３２】
相関特性情報は、測定により得ることができる。例えば、向きや周囲のレイアウト形状、素子間の距離の異なるようなサンプル素子を多数含んだ特性評価用集積回路を製造し、各素子の特性を測定し、素子特性の平均値や分散を計算により求めればよい。図１３は相関特性情報を生成する方法を示すフローチャートである。また、遅延分布の相関関係が直接得られなくとも、トランジスタの飽和電流は遅延にほぼ比例することがわかっており、またゲート長は飽和電流に反比例、ゲート幅は飽和電流に比例することがわかっているので、レイアウト条件と、これらゲート長、ゲート幅、飽和電流等との相関関係を得ることができれば、遅延の相関関係として用いることも可能である。
【０１３３】
このように、相関特性情報は、集積回路設計の前に、プロセスに応じてあらかじめ求めておけばよい。そして、実際の集積回路設計においては、相関特性情報から実際のレイアウト等の情報に基づいて、各素子間の相関関係情報を求めればよい。
【０１３４】
例えば、素子間の距離がＤ、同じ向きに配置されている２つの素子の遅延分布の相関係数Ｒは、Ｒ＝ｆ（Ｄ，ｃ，ｈ）で得られる。ここで、ｆ（ｘ，ｙ，ｚ）は任意の関数であり、例えば、ｆ（ｘ，ｙ，ｚ）＝Ｋｙｚ／ｘという関数である（Ｋは定数）。
【０１３５】
（第２の実施形態）
本発明の第２の実施形態は、与えられた回路について、フォールスパスを除去して回路を評価する方法に関するものである。
【０１３６】
「論理的フォールスパス」は、回路の接続構造に関する情報を用いて特徴付けることができる。すなわち、アサイクリックグラフＧ＝（Ｖ，Ｅ）において、２つの点ｘ，ｙを同時に通るパスとして定義できる。また、「機能的フォールスパス」は、原因部分パスを含むパスとして指定でき、原因部分パスは、点集合の対（Ｘ，Ｙ）を用いて、Ｘの点ｘからＹの点ｙに至るパスとして定義できる（H.C. Chen and D.H. Du, "Path sensitization in critical path problem," IEEE Trans. Computer-Aided Design of ICs and Systems, vo.12, no.2, pp.196-207, 1993  に開示）。
【０１３７】
すなわち、図２において、フォールスパスは、点集合の対（Ｘ，Ｙ）を指定し、Ｘの点４１とＹの点４２を同時に通るパスとして定義できるから、これらのパスを、グラフＧ４００から除去できれば、クリティカルパス遅延の精度を上げることができる。
【０１３８】
ここでは、点集合の対（Ｘ，Ｙ）によって指定できるフォールスパスの除去手法について、説明する。ただし、Ｘに含まれる異なる２点ｘ’，ｘ”間には有向道は存在せず、Ｙに含まれる異なる２点間にも有向道は存在しないものとする。論理回路において、ｘ∈Ｘおよびｙ∈Ｙはそれぞれゲートの入力および出力に対応しているから、この仮定は不自然なものではない。Ｘのある点ｘからの有向道と、Ｙのある点ｙへの有向道の両方が存在するような点の集合をＵ’とし、Ｕ’からＸとＹを取り除いた集合をＵ（＝Ｕ’−Ｘ−Ｙ）とする。集合ＵによるグラフＧの点セクショングラフ４３を、Ｇ［Ｕ］＝（Ｕ，Ｅ［Ｕ］）とする。ここで、Ｅ［Ｕ］＝［（ｖ，ｗ）∈Ｅ｜ｖ∈Ｕ，ｗ∈Ｕ］である。
【０１３９】
さらに、図３において、集合Ｇ［Ｕ］から出ていく枝の終点であって、Ｙの点４２以外の点の集合５２をＯｕｔ、集合Ｇ［Ｕ］に入ってくる枝の始点であって、Ｘの点４１以外の点の集合５１をＩｎとする。すなわち、
【０１４０】
【数２１】
2006155644.tif 000023
【０１４１】
【数２２】
2006155644.tif 000024
【０１４２】
このとき、明らかに、次の性質がある。
【０１４３】
ｉ．ＯｕｔとＩｎは共通要素を持たず、Ｏｕｔの点ｖからＩｎの点ｗに至るパスは存在しない。なぜなら、点ｖから点ｗに至る有向道が存在すると仮定すると、このような点ｖまたは点ｗに対して、Ｘの点からの有向道とＹの点への有向道が同時に存在することになり、集合Ｕの仮定に反する。
【０１４４】
ｉｉ．Ｏｕｔの点ｖからＹの点ｙに至るパスも存在しない。
【０１４５】
ｉｉｉ．Ｘの点ｘからＩｎの点ｖに至るパスも存在しない。もし、このようなパスが存在するとすると、点ｖはＵに含まれなければならず、集合Ｕの仮定に反する。
【０１４６】
図４は本発明の回路評価方法のフローチャートを表している。図４において、まず入力工程Ｓ２１によって、評価対象である回路の接続関係や性能等を表す回路情報２１と、フォールスパス情報２２とを入力する。フォールスパス情報２２では、各フォールスパスが、集積回路を表すグラフ上の２点の組によって表現されている。
【０１４７】
次に等価回路生成工程Ｓ２２において、入力された回路情報２１から、フォールスパスを含まない等価回路の生成を行う。フォールスパスが複数ある場合は、この等価回路生成を繰り返し行えばよい。そして、等価回路評価工程Ｓ２３において、フォールスパスを含まない等価回路情報２３を用いて、遅延や消費電力等の回路評価を行う。
【０１４８】
図５は等価回路生成工程Ｓ２２の処理を示すフローチャートである。ここでは、点集合の対（Ｘ，Ｙ）に対して、アサイクリックグラフＧ＝（Ｖ，Ｅ）の変形操作を行うことによって、等価回路を生成する。
【０１４９】
まず部分回路抽出工程Ｓ２２ａにおいて、図３に示すように、部分回路Ｇ［Ｕ］４３を抽出する。次に図６に示すように、部分回路複製工程Ｓ２２ｂにおいて、部分回路Ｇ［Ｕ］４３を複製して第２の部分回路に相当するグラフＧ”６２を作り、元の部分回路Ｇ［Ｕ］４３を第１の部分回路に相当するグラフＧ’６１とする。次に部分回路接続変更工程Ｓ２２ｃにおいて、グラフＧ’６１の点からｙ４２への枝を全て取り除き、代わりにグラフＧ”６２の対応する点からｙ４２への枝ＥＧ１を付ける。さらに、Ｉｎ５１の点からグラフＧ’６１の点に入る枝ＥＧ２の複製ＥＧ３を、Ｉｎ５１の点と対応するグラフＧ”６２の点との間に付ける。なお、グラフＧ’６１の点からＯｕｔ５２の点に入る枝ＥＧ４はそのまま残しておく。
【０１５０】
さらに、グラフＧ’６１において新たなシンクが生まれたり、グラフＧ”６２において新たなソースが生まれたりしたときは、そのような点とこれに接続する枝をともに取り除く、という操作を繰り返し、グラフＧ’６１およびＧ”６２の中にシンクやソースが存在しないようにする。このようにして生成されたアサイクリックグラフを、Ｇ＜（Ｘ，Ｙ）＞と表す。
【０１５１】
このグラフＧ＜（Ｘ，Ｙ）＞に対して、以下の性質が成り立つ。
【０１５２】
（ｉ）Ｇ＜（Ｘ，Ｙ）＞には、Ｘの点ｘとＹの点ｙを同時に通るパスは存在しない。
【０１５３】
（ii）元のグラフＧにおけるパスで、Ｘの点とＹの点を同時に通らないものは、全てＧ＜（Ｘ，Ｙ）＞に存在する。
【０１５４】
（iii）Ｇ＜（Ｘ，Ｙ）＞に存在するどのパスも、これに対応するパス（通る点と枝が同一）が元のグラフＧに存在する。
【０１５５】
したがって、Ｇ＜（Ｘ，Ｙ）＞においてクリティカル遅延のばらつきを求めたとき、元のグラフＧにおいて、Ｘの点とＹの点を同時に通らないパスの最大遅延のばらつきを求めたことになる。
【０１５６】
図７は上述した性質を満たす等価回路を生成するグラフ変形処理の他の例を示す図である。すなわち、部分回路接続変更工程Ｓ２２ｃにおいて、第１の部分回路に相当するグラフＧ’６１の点からＹの点４２への枝を全て取り除き、代わりに第２の部分回路に相当するグラフＧ”６２の対応する点からＹの点４２に枝ＥＧ５を付け替える。そして、Ｇ”６２をＧ’６１に付加した後、Ｇ’６１の点からＯｕｔ５２の点に入る枝ＥＧ６の複製ＥＧ７を、対応するＧ”６２の点からＯｕｔ５２の点に付ける。また、Ｉｎ５１の点からＧ’６１の点に入る枝を全て取り除き、代わりにＩｎ５１からＧ”６２の、対応する点に枝ＥＧ８に付け替える。
【０１５７】
図６の例では、第１の部分回路に相当するグラフＧ’６１は、第１の点４１並びにＩｎ５１およびＯｕｔ５２と接続されており、かつ、第２の点４２とは接続されていない。一方、第２の部分回路に相当するグラフＧ”６２は、第２の点４２およびＩｎ５１と接続されており、かつ、第１の点４１およびＯｕｔ５２とは接続されていない。この結果、第１の点４１から第２の点４２に向かうパスが存在しない。
【０１５８】
また図７の例では、第１の部分回路に相当するグラフＧ’６１は、第１の点４１およびＯｕｔ５２と接続されており、かつ、第２の点４２およびＩｎ５１と接続されていない。一方、第２の部分回路に相当するグラフＧ”６２は、第２の点４２並びにＩｎ５１およびＯｕｔ５２と接続されており、かつ、第１の点４１とは接続されていない。この結果、第１の点４１から第２の点４２に向かうパスが存在しない。
【０１５９】
以下、本実施形態に係る等価回路生成方法を、一般化して記述する。
【０１６０】
除去すべき全てのフォールスパスの集合は、点集合の対の集合Ｆ＝［（Ｘｉ，Ｙｉ）｜ｉ＝１，２，…，ｆ］によって表される。そこで、Ｇからこれら全てのフォールスパスを除去するために、上述の変形操作を各対（Ｘ，Ｙ）（∈Ｆ）に対して繰り返す。このとき、Ｇを変形してＧ＜Ｘ，Ｙ＞を作る際に、Ｕの点が複製されているから、（Ｘ，Ｙ）以外の対（Ｘ’，Ｙ’）（∈Ｆ−［（Ｘ，Ｙ）］）を、Ｕを用いて次のように修正する。
【０１６１】
Ｉ．Ｘ’∩Ｕ≠ｆのとき：
Ｘ’∩Ｕの点で、複製が新たなシンクやソースにならずにＧ＜Ｘ，Ｙ＞に残っているとき、その複製をＸ’に入れる。
【０１６２】
II．Ｙ’∩Ｕ≠ｆのとき：
Ｙ’∩Ｕの点で、複製が新たなシンクやソースにならずにＧ＜Ｘ，Ｙ＞に残っているとき、その複製をＹ’に入れる。
【０１６３】
いま、更新される前の対を（Ｘ’，Ｙ’）、更新された対を（Ｘ”，Ｙ”）と表す。明らかに、Ｇ＜Ｘ，Ｙ＞  において、Ｘ”の点間を結ぶ有向道はないし、Ｙ”の点間を結ぶ有向道もない。さらに、Ｇにおいて、Ｘの点とＹの点を同時に通るパスの集合をＰ（Ｘ，Ｙ）、Ｘ’の点とＹ’の点を同時に通るパスの集合をＰ（Ｘ’，Ｙ’）と表し、Ｇ＜Ｘ，Ｙ＞において、Ｘ”の点とＹ”の点を同時に通るパスの集合をＰ’（Ｘ”，Ｙ”）と表す。このとき、Ｐ’（Ｘ”，Ｙ”）に含まれるどのパスも、Ｐ（Ｘ’，Ｙ’）のどれかのパスに対応する。すなわち、Ｐ（Ｘ’，Ｙ’）のパスに対応するパスで、Ｇ＜Ｘ，Ｙ＞に存在するものは、Ｐ’（Ｘ”，Ｙ”）  に含まれる。それゆえ、Ｐ（Ｘ’，Ｙ’）以外のＧのパスで、Ｐ’（Ｘ”，Ｙ”）に含まれるものはない。
【０１６４】
したがって、Ｇ＜（Ｘ，Ｙ）＞に対して（Ｘ’，Ｙ’）に関する変形操作を行って得られるグラフをＧ”と表すと、Ｇ”では、Ｐ’（Ｘ”，Ｙ”）のパスが全て除去されているから、ＧからＰ（Ｘ’，Ｙ’）のパスが全て除去されたことになる。すなわち、次のような性質が成り立つ。
【０１６５】
（ｉ）Ｇ”には、Ｐ（Ｘ，Ｙ）に対応するパスも、Ｐ（Ｘ’，Ｙ’）に対応するパスも存在しない。
【０１６６】
（ii）Ｇ＜Ｘ，Ｙ＞におけるパスでＰ’（Ｘ”，Ｙ”）以外のパスは、全てＧ”に存在する。したがって、ＧにおけるＰ（Ｘ，Ｙ），Ｐ（Ｘ’，Ｙ’）以外のパスは、全てＧ”に存在する。
【０１６７】
（iii）Ｇ”に存在するどのパスも、これに対応するものがＧ＜Ｘ，Ｙ＞に存在し、したがって、Ｇにも存在する。
【０１６８】
このことから、上述したグラフの変形操作と点集合対の更新操作とを繰り返して、Ｆで指定される全てのフォールスパスを除去したグラフをＧ＊＝（Ｖ＊，Ｅ＊）とすると、Ｇ＊＝（Ｖ＊，Ｅ＊）上のパスと、元のグラフＧ＝（Ｖ，Ｅ）のパスとの間には、次のような関係が成り立つ。
【０１６９】
（ｉ）どの対（Ｘ，Ｙ）∈Ｆに対しても、Ｇ＊上には、Ｘの点ｘとＹの点ｙを同時に通るパスは存在しない。
【０１７０】
（ii）Ｆで指定されるフォールスパス以外の全てのＧのパスは、Ｇ＊に存在する。
【０１７１】
（iii）Ｇ＊に存在するどのパスも、それに対応するものがＧに存在する。
【０１７２】
この操作は、次のように、表すことができる。
【０１７３】
Ｆ＝［（Ｘi，Ｙi）｜ｉ＝１，２，…，ｆ］に対して、Ｇ＿（１）＝Ｇ＜Ｘ＿（１），Ｙ＿（１）＞、Ｇi＝Ｇi-1＜Ｘii-1，  Ｙii-1＞（ｉ＝２，…，ｆ）とする。ここで、Ｇi-1＜Ｘii-1，Ｙii-1＞（ｉ＝２，…，ｆ）は、グラフＧi-1に対して、（Ｘii-1，Ｙii-1）に関する変形操作を行って得られるグラフであり、（Ｘii-1，Ｙii-1）（ｉ＝２，…，ｆ）は、（Ｘii-2，Ｙii-2）に対して、（Ｘi-1i-2，Ｙi-1i-2）で定められるＵi-1を用いた更新操作を行って得られる対である。
【０１７４】
このＵi-1は、Ｇi-1＝Ｇ＿（ｉ−２）＜Ｘi-1i-2，Ｙi-1i-2＞上で、Ｘi-1i-2の点からの有向道とＹi-1i-2の点への有向道の両方が存在する点の集合から、Ｘi-1i-2の点とＹi-1i-2の点を取り除いたものである。
【０１７５】
Ｇ＿（０）＝Ｇ，Ｘ＿（１）＾（０）＝Ｘ＿（１），Ｙ＿（１）＾（０）＝Ｙ＿（１）からはじめて、各（Ｘi，Ｙi）（ｉ＝１，２，…，ｆ）に対して、Ｇi  ＝Ｇi-1＜Ｘii-1，Ｙii-1＞を生成する操作を繰り返し、Ｇfが得られる。これにより、Ｆで指定されるＧ上の全てのパスの集合をＰ（Ｆ）＝∪ｉＰ（Ｘi，Ｙi）とすれば、Ｇf上にはＰ（Ｆ）に対応するパスは存在せず、ＧのＰ（Ｆ）以外のパスは、対応するものがＧf上に存在する。
【０１７６】
（第３の実施形態）
本発明の第３の実施形態は、設計対象の回路から、フォールスパスを抽出する方法に係るものである。抽出されたフォールスパスは、先の第２の実施形態に開示した方法を用いて、削除することができる。
【０１７７】
第２の実施形態ですでに述べたように、「論理的フォールスパス」は、回路の接続構造に関する情報を用いて特徴付けることができる。すなわち、アサイクリックグラフＧ＝（Ｖ，Ｅ）において、２つの点ｘ，ｙを同時に通るパスとして定義できる。
【０１７８】
いま、ＡＮＤゲートにおける信号値“０”のように、論理ゲートの一の入力にその値が与えられたとき出力が決定するような信号値のことを「制御信号」と呼び、ＡＮＤゲートにおける信号値“１”のように、論理ゲートの一の入力にその値が与えられても出力が決定しないような信号値のことを「非制御信号」と呼ぶ。ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲの各ゲートには、制御信号および非制御信号が存在し、それらは互いに否定の関係にある。これに対して、インバータでは“０”“１”のいずれも制御信号であり、ＸＯＲゲートでは“０”“１”のいずれも非制御信号である。すなわち、ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲの各ゲート、およびインバータでは、一の入力に制御信号が与えられると、その出力が決定する。
【０１７９】
そこで、これらの各ゲートに関して、制御信号の伝播操作を定める。例えば図１１において、ｚ＝“１”のときは、インバータＧ４の出力が“０”になり、ＡＮＤゲートＧ５の出力ｃが“０”になる。このため、伝播操作により、ｚ＝１はｃ＝０を導く。したがって、ｃ＝１のときはｚ＝０である。なお、この関係は、逆伝播操作によって導くこともできる。
【０１８０】
ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲの各ゲートにおいて、非制御信号が通るパスが活性化されるためには、他のすべての入力が非制御信号でなければならない。これに対して、制御信号が通るパスが活性化されるためには、そのパスが通る入力ｖ以外の各入力に、非制御信号が入るか、ｖに制御信号が到達した後に制御信号が入るかのいずれかとなる。したがって、制御信号が通るパスが活性化されるか否かを判定するには、必然的に遅延量が必要となる。それに対して、非制御信号が通るパスの方は、時間的要素に無関係に、接続関係とゲートの種類だけで活性化されるか否かが判定できる。
【０１８１】
そこで、グラフＧ＝（Ｖ，Ｅ）において、非制御信号が通過する論理ゲート内の各枝ｅ＝（ｖ，ｗ）に対して、その枝が活性化するための条件、すなわちｗに入る他のすべての枝を非制御信号が通過する、という条件を与える。これを、「非制御信号枝ｅの活性化条件」と呼ぶ。ｗに入る他の枝ｅ’＝（ｕ，ｗ）に非制御信号ｓが入るという条件を、Ｇのｕに付随するネット（信号）をＮｅｔ（ｕ）として、Ｎｅｔ（ｕ）＝ｓと表す。
【０１８２】
Ｎｅｔ（ｕ）の信号ｓが、ｕ以外にもファンアウトを持ち、それが制御信号として別の論理ゲートＬに入っているとき、Ｌの出力は伝播操作によって値が決定する。そこで、非制御信号枝の活性化条件に挙げられた論理値を、伝搬操作を用いて伝播させる。例えば図１１において、第１のゲートしてのゲートＧ１内の（ｖ１，ｗ１）の活性化条件は、ｚ＝１すなわちＮｅｔ（ｕ）＝１であるが、これはゲートＧ４の入力ａ＝１、ゲートＧ６の入力ｃ＝０に伝播させることができる。そうすると、ｃ＝１ならばｚ＝０であるから、第２のゲートとしてのＡＮＤゲートＧ６内の枝（ｂ１，ｙ１）の活性化条件ｃ＝１とｚ＝１とは両立せず、矛盾が生じることが分かる。すなわち、枝（ｖ１，ｗ１）と枝（ｂ１、ｙ１）とを同時に活性化させることはできないので、これらの枝を同時に通るようなパスは，フォールスパスであると判断できる。このようなフォールスパスは、点対（ｖ１，ｂ１）によって指定できる。
【０１８３】
図８は本発明の第３の実施形態に係るフォールスパス抽出方法を示すフローチャートである。図８に示すように、まず入力工程Ｓ３１において、回路情報３１の入力を行う。次に必要条件決定工程Ｓ３２において、各ゲートにおける非制御信号を活性化する信号の必要条件を決定する。Ｅｎｃ＝（ｕｎｃ，ｗｎｃ）をゲート内の枝で入力が非制御信号ｎｃｓに対応するものとし、Ｎｅｔ（ｕ）＝ｎｃｓを活性化条件とする枝の集合をＲＥ（ｅｎｃ）＝［（ｖｎｃ，ｗｎｃ）∈Ｅ］と表す。Ｎｅｔ（ｕ）＝ｎｃｓは、伝播操作によって、各ネットの値を定めていくことも可能である。
【０１８４】
そして信号変化矛盾抽出工程Ｓ３３において、必要条件決定工程Ｓ３２によって決定された必要条件から、同時に活性化しないゲートの信号変化を抽出する。あるゲートＧの入力ｃの値をＧの制御信号ｃｓにしたとし、Ｇにはｃ以外の入力ｂがあるとする。このとき、ゲートＧ内のｃが制御信号ｎｃｓに対応する枝をｅｎｃ’＝（ｃｎｃ，ｙｎｃ）とすると、ＲＥ（ｅｎｃ’）＝［（ｂｎｃ，ｙｎｃ∈Ｅ）］の各枝（ｂｎｃ，ｙｎｃ）はＮｅｔ（ｃ）＝ｎｃｓを活性化条件とするから、枝（ｖｎｃ，ｗｎｃ）（∈ＲＥ（ｅｎｃ））と枝（ｂｎｃ，ｙｎｃ）（∈ＲＥ（ｅｎｃ’））は同時に活性化しない．したがって、ゲートＧにおいて、点ｖから有向道によって到達可能な点の集合をｓｕｃ（ｖ）とすると、点対（ｖｎｃ，ｂｎｃ）はフォールスパスを指定する点対である。
【０１８５】
また、１つの枝ｅｎｃに対して、このような点対をすべて見出すことは、グラフの枝数をｍとするとＯ（ｍ）の計算量でできるから、すべての点対を見出すことは、Ｏ（ｍ2）の計算量でできる。
【産業上の利用可能性】
【０１８６】
本発明に係る遅延分布計算方法は、集積回路の遅延分布の計算において、配線または素子間の性能の相関関係が考慮されるので、遅延見積もり精度が向上し、これにより、設計する集積回路について、過剰なマージンを除去することができ、不要な面積や消費電力等を削減することができるという効果を有し、例えば、ＣＭＯＳ・ＬＳＩ等の集積回路の設計において、その性能を評価する技術に関するもの、特に、遅延分布の計算や、フォールスパスの除去や抽出に関する技術等として有用である。
【図面の簡単な説明】
【０１８７】
【図１】本発明の第１の実施形態に係る遅延分布計算方法を示すフローチャートである。
【図２】フォールスパスの指定表現を表す図である。
【図３】変更前のグラフを表す図である。
【図４】本発明の第２の実施形態に係る回路評価方法を示すフローチャートである。
【図５】図４の回路評価方法における等価回路生成処理のフローチャートである。
【図６】変更後のグラフを表す図である。
【図７】変更後のグラフの他の例を表す図である。
【図８】本発明の第３の実施形態に係るフォールスパス抽出方法を示すフローチャートである。
【図９】論理回路の一例を表す図である。
【図１０】図９の回路を表すアサイクリックグラフを表す図である。
【図１１】フォールスパスを含む論理回路を示す図である。
【図１２】相関関係情報を生成する方法を示すフローチャートである。
【図１３】相関特性情報を生成する方法を示すフローチャートである。
【符号の説明】
【０１８８】
１１  回路情報
１２  性能分布情報
１３  相関関係情報
２２  フォールスパス情報
４１  第１の点
４２  第２の点
４３  第１の部分回路
５１  集合Ｉｎ
５２  集合Ｏｕｔ
６１  第１の部分回路に相当するグラフ
６２  第２の部分回路に相当するグラフ
２００  アサイクリックグラフ
Ｇ１  第１のゲート
Ｇ６  第２のゲート
【図１】
2006155644.tif 000025
【図２】
2006155644.tif 000026
【図３】
2006155644.tif 000027
【図４】
2006155644.tif 000028
【図５】
2006155644.tif 000029
【図６】
2006155644.tif 000030
【図７】
2006155644.tif 000031
【図８】
2006155644.tif 000032
【図９】
2006155644.tif 000033
【図１０】
2006155644.tif 000034
【図１１】
2006155644.tif 000035
【図１２】
2006155644.tif 000036
【図１３】
2006155644.tif 000037