(57)【要約】  トランジスタ等の部品や配線の遅延のばらつきの相関を考慮して、正確に組合せ回路の最大遅延を削減する。設計対象回路を表す回路情報(100)、設計対象プロセスに基づいた素子および/または配線の特性分布を表すテクノロジ情報(200)、設計対象回路における遅延の分布を表す遅延分布情報(300)、設計対象回路における遅延のばらつきの相関を表す遅延相関情報(400)に基づいて、設計対象回路の遅延の改善のための回路修正候補を表す回路修正候補情報(500)を生成する(ST200)。
2010092825.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路の解析を行う方法であって、
設計対象回路を表す回路情報(100)を取得するステップと、
設計対象プロセスに基づいた素子および/または配線の特性分布を表すテクノロジ情報(200)を取得するステップと、
前記設計対象回路における遅延の分布を表す遅延分布情報(300)を取得するステップと、
前記設計対象回路における遅延のばらつきの相関を表す遅延相関情報(400)を取得するステップと、
前記回路情報(100)，前記テクノロジ情報(200)，前記遅延分布情報(300)，前記遅延相関情報(400)に基づいて、前記設計対象回路の遅延の改善のための回路修正候補を表す回路修正候補情報(500)を生成する回路修正候補抽出ステップ(ST200)と、
を備える回路解析方法。
【請求項２】
前記回路修正候補抽出ステップ(ST200)は、
前記回路情報(100)から前記設計対象回路を点と枝で表現するグラフを生成するグラフ作成ステップ(ST210)と、
前記グラフ作成ステップ(ST210)で生成されたグラフの各枝についてその枝がクリティカルエッジとなる確率を計算するクリティカルエッジ計算ステップ(ST220)と、
前記グラフ作成ステップ(ST210)で生成されたグラフの各点，各枝についてその点，その枝がクリティカルパス上の点，枝となる確率を計算するクリティカルパス率計算ステップ(ST230)と、
前記クリティカルエッジ計算ステップ(ST220)，前記クリティカルパス率計算ステップ(ST230)における計算結果に基づいて前記回路修正候補情報(500)を生成する回路修正候補決定ステップ(ST240)とを含む
請求項１に記載の回路解析方法。
【請求項３】
前記回路修正候補情報(500)に基づいて前記回路情報(100)の修正を行う回路改善ステップ(ST300)をさらに備える
請求項１に記載の回路解析方法。
【請求項４】
前記回路情報(100)に記述された接続関係からパスを解析し、当該パス解析結果と前記テクノロジ情報(200)に記述された遅延情報とから、前記設計対象回路を解析した結果として前記遅延分布情報(300)と前記遅延相関情報(400)とを出力する遅延分布計算ステップ(ST100)をさらに備える
請求項１に記載の回路解析方法。
【請求項５】
前記遅延の改善は、
前記設計対象回路の遅延違反の削減，もしくは，前記設計対象回路の最大遅延の削減を含む
請求項１に記載の回路解析方法。
【請求項６】
前記回路修正候補情報(500)は、
少なくとも１つのセルまたは配線を含む
請求項１に記載の回路解析方法。
【請求項７】
前記遅延は、
クロックもしくはフリップフロップの信号変化から当該信号変化の影響による回路中の他の地点の信号変化までにかかる時間を含む
請求項１に記載の回路解析方法。
【請求項８】
前記回路修正候補抽出ステップ(ST200)では、
前記遅延分布情報(300)と前記遅延相関情報(400)を考慮して、クリティカルパスになる確率の高い候補を抽出することにより前記回路修正候補情報(500)を生成する
請求項１に記載の回路解析方法。
【請求項９】
前記遅延相関情報(400)は、
少なくとも１対の遅延のばらつきの相関係数を表した情報を含む
請求項１に記載の回路解析方法。
【請求項１０】
前記回路情報(100)は、
半導体集積回路の論理設計工程での論理合成によって生成された論理回路情報(100a)である
請求項１に記載の回路解析方法。
【請求項１１】
前記回路情報(100)は、
半導体集積回路の配置設計工程での配置設計後に生成される配置済み回路情報(100b)である
請求項１に記載の回路解析方法。
【請求項１２】
前記回路情報(100)は、
半導体集積回路の配線設計工程での配線設計後に生成される配線済み回路情報(100c)である
請求項１に記載の回路解析方法。
【請求項１３】
請求項１に記載の回路解析方法をコンピュータに実行させるための回路解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は半導体集積回路設計において、計算機を用いてプロセス情報等に基づいて回路の特性をシミュレーションし性能改善する方法に関するものである。
【背景技術】
【０００２】
半導体集積回路設計において、微細化により、プロセスばらつきの回路特性への影響が増大している。そのため、半導体集積回路を構成する各素子の遅延のばらつきを正規分布で表し、統計的演算を用いて回路全体の遅延分布を見積もる技術(以下、統計的遅延解析手法)があった。【０００３】
統計的遅延解析手法として[特許文献1]の手法が提案されている。[特許文献1]では、CMOS組み合わせ回路に対し、素子・配線・パス間の遅延の相関を考慮して静的に最大遅延の分布を計算することができる。【０００４】
図3は設計対象回路の例であり、図4は図3の回路をアサイクリックグラフG＝{V,E}で表現した例である。ここで、Vはグラフの点集合、Eはグラフの枝集合を表している。[特許文献1]に示す様に、回路の各端子v(21,22)に値0を伝搬させるのに要する真の最大遅延をd0(v)、値1を伝搬させるのに要する真の最大遅延をd1(v)として、回路全体の出力端子に対するこれらの値の最大値を見出すという方法があった。【０００５】
ここで、回路全体の入出力，論理ゲートの入出力の各端子は、グラフの点vに対応し、グラフの2つの点v0,v1に対応する。図4においては、これら1対の点(v0,v1)を点線の楕円(21,22)で囲み、v0は白抜きの点(23)で、v1は黒点(24)で表している。v0,v1は、それぞれ対応する端子vが信号値0,1をとることを示し、以下では、v0をvの0点、v1をvの1点と呼ぶ。【０００６】
回路全体の入力端子に対応する点は、入ってくる枝のないソースであり、回路全体の出力端子に対応する点は出ていく枝の無いシンクである。以下では、ソースの集合(25)をS、シンクの集合(26)をTとする。また、グラフGのソースからシンクに至る有向道をパスとする。図4において、各矩形(27)は回路を構成する論理ゲートを示し、1つの矩形内の左側の点(21)は対応する論理ゲートの入力端子を、右側の点(22)は出力端子に対応する。矩形内の枝(28)は、論理ゲートの入力を表す点から出て出力を表す点に入り、矩形がNANDゲートやNORゲートである場合には、そのゲート内のpMOSあるいはnMOSに対応する。異なる矩形に属す点を結ぶ枝は配線に対応し、0点から出た枝e0は0点に入り、1点から出た枝e1は1点に入る。【０００７】
回路の各端子vに対する最大遅延d0(v),d1(v)を、それぞれグラフG上の点vの0点(v0),1点(v1)へのあるシンクからの最大パス長d(v0),d(v1)に対応させる。そのため、u,vをそれぞれ枝の始点,終点とすると、各枝e＝(u,w)に対して、信号値をuからwに伝達するのに要する遅延を枝eの重みt(e)として与える。【０００８】
このようなアサイクリックグラフを用いてシミュレーションすることにより、比較的簡単な処理で論理回路の遅延解析を行なうことが可能であった。【０００９】
一方、[特許文献2]では、各セルに入力される遅延時間及び遷移時間の確率分布に相関関係があることに着目し、遅延分布計算手段によって遅延情報を計算し、遅延情報に基づきタイミング解析を行い、回路を改善する方法があった。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開2002-279012号公報
【特許文献２】特開2007-304957号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、LSIの設計性能を向上させるためには、クリティカルパス遅延に影響を与える素子や配線を精度よく発見し、改善する必要がある。そのためには、各素子や配線がクリティカルパスの一部となる確率を精度よく見積もる必要がある。【００１２】
また、図3に示されるような回路で信号fを計算しようとする際に、信号dと信号eの信号伝達時間(遅延)が信号bの遅延に大きく依存するような場合、信号dの遅延と信号eの遅延の間には大きな相関がある。また、配線遅延にもばらつきがあるような場合、信号bのファンアウトの信号伝達遅延にも相関がある。従って、相関を考慮しない統計的遅延解析手法は正確さを欠く可能性が高い。遅延分布見積もりの精度が悪い場合、半導体集積回路の設計においては、実際には確率的にほとんど起こり得ないいくつもの最悪条件が重なった場合においての正常動作を保証せねばならず、オーバーマージンを含んだ設計にならざるを得ない。このため、設計された半導体集積回路においては、必要以上に面積や消費電力等のコストを増大させてしまう。【００１３】
一方、[特許文献2]の方法では、遅延と入力遷移時間の間の相関情報等を用いて遅延分布計算を精度良く行う方法が開示されているが、回路改善候補を選択する際にパス遅延の相関を考慮することはできなかった。すなわち、遅延分布解析でいくら精度を向上させても、回路改善を精度よく行うことができず、回路修正後の遅延分布計算において、見積り以下の遅延改善効果しか得られないことになる。回路修正と遅延分布計算の工程を必要以上に繰り返すことにより設計期間を増大させてしまうか,あるいは,過剰に回路修正してしまうことにより、半導体集積回路面積や消費電力を必要以上に増大させてしまう。【００１４】
本発明は、トランジスタ等の部品や配線の遅延のばらつきの相関を考慮して、正確に組合せ回路の最大遅延を削減することを課題とする。
【課題を解決するための手段】
【００１５】
本発明のある実施形態による回路解析方法は、半導体集積回路の解析を行う方法であって、設計対象回路を表す回路情報(100)を取得するステップと、設計対象プロセスに基づいた素子および/または配線の特性分布を表すテクノロジ情報(200)を取得するステップと、前記設計対象回路における遅延の分布を表す遅延分布情報(300)を取得するステップと、前記設計対象回路における遅延のばらつきの相関を表す遅延相関情報(400)を取得するステップと、前記回路情報(100)，前記テクノロジ情報(200)，前記遅延分布情報(300)，前記遅延相関情報(400)に基づいて、前記設計対象回路の遅延の改善のための回路修正候補を表す回路修正候補情報(500)を生成する回路修正候補抽出ステップ(ST200)とを備えることを特徴とする。【００１６】
上記回路解析方法によれば、設計対象回路の遅延の改善のための回路修正候補を精度よく見積もることができ、面積や消費電力等のコストを削減することができる。
【発明の効果】
【００１７】
本発明によれば、最大遅延削減あるいは遅延制約違反解消のために、遅延相関情報を考慮して回路改善箇所を抽出することにより、より精度よく改善候補を見積もることが可能となる。すなわち、遅延制約違反解消に至る回路改善回数の削減効果、あるいは、回路改善終了時点での半導体集積回路において、面積や消費電力等のコストをより削減することできるという効果がある。
【図面の簡単な説明】
【００１８】
【図１】図１は回路解析プログラムに従って行われる処理の流れを示す図である。
【図２】図２は半導体集積回路の設計フローを示す図である。
【図３】図３は設計対象回路の回路情報100の例を示す図である。
【図４】図４は図３の回路をアサイクリックグラフで表現した図である。
【図５】図５は図３の回路をアサイクリックグラフで表現した図である。
【図６】図６は図３の回路をアサイクリックグラフで表現した図である。
【図７】図７はテクノロジ情報200の例を示す図である。
【図８】図８は遅延分布情報300の例を示す図である。
【図９】図９は遅延分布情報300の例を示す図である。
【図１０】図１０は遅延相関情報400の例を示す図である。
【図１１】図１１は遅延相関情報400の例を示す図である。
【図１２】図１２は回路修正候補情報500の例を示す図である。
【図１３】図１３は回路修正候補情報500の例を示す図である。
【図１４】図１４は回路修正候補抽出処理ST200において行われる処理の流れを示す図である。
【図１５】図１５は回路改善処理ST300による修正が行われた後の回路情報100の例を示す図である。
【図１６】図１６は回路改善処理ST300による修正が行われた後の回路情報100の例を示す図である。
【図１７】図１７は回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図１８】図１８は回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図１９】図１９は回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図２０】図２０は回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図２１】図２１は回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図２２】図２２は回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【発明を実施するための形態】
【００１９】
以下、好ましい実施形態について図面を参照して説明する。
【００２０】
本実施形態による回路解析プログラムは、PC等の情報処理装置，ネットワークを介して端末装置から利用可能な形態で設定されたサーバ装置に保持されうる。また、CD-ROM，DVD-ROM，フラッシュメモリ等の各種記録媒体に当該プログラムを記録して流通させることもできる。そしてPC等の情報処理装置に上記の記録媒体を装着して当該プログラムを読み出す,あるいは,情報処理装置が備えている記憶媒体に当該プログラムを記憶させておき必要に応じて読み出すことにより、当該プログラムに関わる機能を実現することができる。以下、当該プログラムに従って行われる処理の流れを説明する。
【００２１】
本実施形態の回路解析プログラムに従って行われる処理の流れを図1に示す。回路解析プログラムを実行するコンピュータ(計算機)は、データベースとして回路情報100，テクノロジ情報200，遅延分布情報300，遅延相関情報400，回路修正候補情報500を有しており、これらを利用して遅延分布計算処理ST100，回路修正候補抽出処理ST200，回路改善処理ST300を行い、もとの回路情報100を修正する。
【００２２】
図2は半導体集積回路の設計フローである。本実施形態では、図1の回路情報100として、図2の論理設計工程での論理合成によって生成された論理回路情報100aを用いてもよいし、配置設計工程での配置設計後に生成される配置済み回路情報100b,あるいは,配線設計工程での配線設計後に生成される配線済み回路情報100cなどレイアウトの情報を用いてもよい。配置済み回路情報100bを用いる場合には、回路改善処理ST300に基づいてもとの配置済み回路情報100bを修正するだけでなく、もとの論理回路情報100aを修正することもできる。配線済み回路情報100cを用いる場合には、回路改善処理ST300に基づいてもとの配線済み回路情報100cを修正するだけでなく、もとの論理回路情報100a,配置済み回路情報100bを修正することもできる。
【００２３】
図3は設計対象回路の回路情報100の例である。図3(a)は回路図、図3(b)は図3(a)の回路を表したネットリストである。
【００２４】
図1のテクノロジ情報200には、設計対象プロセスに基づいた遅延や電流などの素子の特性の情報が含まれる。図7はテクノロジ情報200の例であり、半導体集積回路を構成する論理セルの遅延特性を表している。図7において、Cell1はnandの論理を持っており、入力端子Aから出力端子Yに至る遅延は平均3.0,標準偏差0.2であり、入力端子Bから出力端子Yに至る遅延は平均2.8,標準偏差0.2であることを示している。Cell3についても同様である。Cell2はorの論理を持っており、入力端子Aから出力端子Yに至る遅延は平均4.0,標準偏差0.2であり、入力端子Bから出力端子Yに至る遅延は平均3.8,標準偏差0.3であることを示している。Cell4についても同様である。Cell5はbufferの論理を持っており、入力端子Aから出力端子Yに至る遅延は平均0.3,標準偏差0.1であることを示している。
【００２５】
遅延分布計算(ST100)
図1の遅延分布計算処理ST100では、回路情報100とテクノロジ情報200とを入力とし、回路情報100に記述された接続関係からパスを解析し、またテクノロジ情報200に記述された遅延情報とから、対象とする回路を解析した結果として遅延分布情報300と遅延相関情報400とを出力する。遅延分布計算処理ST100は、例えば[特許文献1]に開示された方法で行うことができる。
【００２６】
図8は、遅延分布情報300の例である。図8の例は、
Instance1の入力端子Aの遅延は平均0,標準偏差0、
Instance1の入力端子Bの遅延は平均0,標準偏差0、
Instance2の入力端子Aの遅延は平均0.5,標準偏差0.1、
Instance2の入力端子Bの遅延は平均0.6,標準偏差0.1、
Instance3の入力端子Aの遅延は平均3.0,標準偏差0.2、
Instance3の入力端子Bの遅延は平均4.0,標準偏差0.3、
であることを表している。
【００２７】
図9は遅延分布情報300の別の形態である。図9の例は、
遅延の最小値(Min)は、
Instance1の入力端子Aは0、
Instance1の入力端子Bは0、
Instance2の入力端子Aは0.2、
Instance2の入力端子Bは0.3、
Instance3の入力端子Aは2.4、
Instance3の入力端子Bは2.8、
遅延の代表値(Typ)は、
Instance1の入力端子Aは0、
Instance1の入力端子Bは0、
Instance2の入力端子Aは0.5、
Instance2の入力端子Bは0.6、
Instance3の入力端子Aは3.0、
Instance3の入力端子Bは4.0、
遅延の最大値(Max)は、
Instance1の入力端子Aは0、
Instance1の入力端子Bは0、
Instance2の入力端子Aは0.8、
Instance2の入力端子Bは0.9、
Instance3の入力端子Aは3.6、
Instance3の入力端子Bは5.2、
であることを表している。
【００２８】
一般的に、遅延の平均値をμ,遅延の標準偏差をσとすると、遅延の最大値(Max)および最小値(Min)をμ±3σと仮定し遅延計算に用いることが多いが、異なる定義を用いてもよい。また、代表値(Typ)は平均値であってもよいし、プロセスの目標値,あるいは,確率の最も高い値であってもよい。
【００２９】
図10は、遅延相関情報400の例である。図10の例は、
Instance1の入力端子Aの遅延とInstance1の入力端子Bの遅延との相関係数は0.3、
Instance1の入力端子Aの遅延とInstance2の入力端子Aの遅延との相関係数は0.3、
Instance1の入力端子Bの遅延とInstance2の入力端子Aの遅延との相関係数は1、
Instance1の入力端子Aの遅延とInstance3の入力端子Aの遅延との相関係数は0.5、
Instance2の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0.2、
Instance2の入力端子Bの遅延とInstance3の入力端子Bの遅延との相関係数は0.6、
であることを表している。また、上記以外は、相関係数は0である,または,相関関係は無視してよいということを表している。
【００３０】
図11は遅延相関情報400の別の形態である。図11の例は、
Instance1の入力端子Aの遅延とInstance1の入力端子Bの遅延との相関係数は0.3、
Instance1の入力端子Aの遅延とInstance2の入力端子Aの遅延との相関係数は0.3、
Instance1の入力端子Aの遅延とInstance2の入力端子Bの遅延との相関係数は0、
Instance1の入力端子Aの遅延とInstance3の入力端子Aの遅延との相関係数は0.5、
Instance1の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0、
Instance1の入力端子Bの遅延とInstance2の入力端子Aの遅延との相関係数は1、
Instance1の入力端子Bの遅延とInstance2の入力端子Bの遅延との相関係数は0、
Instance1の入力端子Bの遅延とInstance3の入力端子Aの遅延との相関係数は0、
Instance1の入力端子Bの遅延とInstance3の入力端子Bの遅延との相関係数は0、
Instance2の入力端子Aの遅延とInstance2の入力端子Bの遅延との相関係数は0、
Instance2の入力端子Aの遅延とInstance3の入力端子Aの遅延との相関係数は0、
Instance2の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0.2、
Instance2の入力端子Bの遅延とInstance3の入力端子Aの遅延との相関係数は0、
Instance2の入力端子Bの遅延とInstance3の入力端子Bの遅延との相関係数は0.6、
Instance3の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0
であることを表している。
【００３１】
図8および図9の情報と同様に、図10および図11の情報は同値である。
【００３２】
回路修正候補抽出(ST200)
図1の回路修正候補抽出処理ST200において行われる処理の流れを図14に示す。
【００３３】
グラフ生成(ST210)
グラフ生成処理ST210では、読み込んだ回路情報100からグラフを生成し、計算機内部あるいは記録媒体に保存する。
【００３４】
図4〜6は、図3の論理回路を表すアサイクリックグラフの例である。図5では簡単のため、立ち上がりのパスと立下りのパスを共通の枝eおよび点vで表現している。さらに図6では、セル遅延を表す枝と配線遅延を表す枝を1つの枝で表現している。
【００３５】
アサイクリックグラフG＝{V,E}において、ある枝e(e∈E)の遅延をt(e)と表現する。t(e)はテクノロジ情報200に記述される。
【００３６】
回路の任意の点における遅延をxとし、xの分布の平均μおよび分散σ２、2枝e1,e2(e1,e2∈E)の遅延をそれぞれx1＝t(e1),x2＝t(e2)とする。このとき、任意の2枝x1,x2の間の相関係数ρ(x1,x2)は、遅延分布計算処理ST100により計算される。
【００３７】
ソースvsは、フリップフロップの出力端子としてもよいし、クロックとしてもよい。ソースvsから任意の点v(v∈V)への遅延の最大値を点vにおける遅延といい、d(v)で表す。d(v)も同様に[特許文献1]などの方法により計算され、遅延分布情報300として表される。また、点uからvへの枝e＝(u,v)(e∈E)に対してd(e)＝d(u)＋t(e)を枝eの終点における遅延といい、d(e)と表す。これらの遅延d(v),d(e)の確率密度関数をそれぞれjv(x),je(x)とする。jv(x),je(x)は、一般的に[数1],[数2]に示すような正規分布と近似できることが知られている。
【００３８】
【数１】
2010092825.tif 000003
【００３９】
【数２】
2010092825.tif 000004
【００４０】
ここでμv,σv2はd(vi)の平均,分散であり、μe,σe2はd(e)の平均,分散である。
【００４１】
クリティカルエッジ計算(ST220)
次に、クリティカルエッジ計算処理ST220では、多入力セルなど複数の信号が合流する点において、それぞれの信号がクリティカルとなる確率を計算する。
【００４２】
(条件付き確率密度関数)
d(v)＝xのときにある条件condが成立する確率をPv[cond](x)とする。点vにおける遅延d(v)の正規分布確率密度関数をjv(x)とし、d(v)＝xであるときの確率密度jv(x)とそのときにcondが成立する確率Pv[cond](x)との積を、condとなるxの条件付き確率密度関数と呼びφv[cond](x)で表す。このとき定義より[数3]が成立する。
【００４３】
【数３】
2010092825.tif 000005
【００４４】
したがって、d(v)＝xの確率密度関数jv(x),および,condとなるd(v)＝xの条件付き確率密度関数φv[cond](x)が既知である場合、d(v)＝xであるときに条件condが成立する確率Pv[cond](x)は[数4]で求めることができる。
【００４５】
【数４】
2010092825.tif 000006
【００４６】
条件condが成立する確率P[cond]は、d(v)＝xであるときにcondが成立する確率Pv[cond](x)とd(v)＝xの確率密度jv(x)との積を全領域にわたって積分すればよいので[数5]の関係が成立する。一方、通常の確率密度関数を全領域にわたって積分した場合、その値は1となる。
【００４７】
【数５】
2010092825.tif 000007
【００４８】
ここで、条件condの否定を/condとする。d(v)＝xであるときにcondが成立する確率Pv[cond](x)と、d(v)＝xであるときにcondが成立しない確率Pv[/cond](x)との和は1となる[数6]。
【００４９】
【数６】
2010092825.tif 000008
【００５０】
また[数6]を用いると[数7][数8]が成立する。
【００５１】
【数７】
2010092825.tif 000009
【００５２】
【数８】
2010092825.tif 000010
【００５３】
ここで、x＞c(cは定数)なる条件を考える。このとき、xのステップ関数をu(x)とすると、d(v)＝xであるときに条件x＞cが成立する確率Pv[x＞c](x)は[数9]で表すことができる。
【００５４】
【数９】
2010092825.tif 000011
【００５５】
したがって、x＞cとなるd(v)＝xの条件付き確率密度関数φv[x＞c](x)は[数10]で表される。
【００５６】
【数１０】
2010092825.tif 000012
【００５７】
また、d(v)＝xであるときにx＞cが成立しない確率をPv[/(x＞c)](x)とすると、
【００５８】
【数１１】
2010092825.tif 000013
【００５９】
であるので[数12][数13][数14]が成立する。
【００６０】
【数１２】
2010092825.tif 000014
【００６１】
【数１３】
2010092825.tif 000015
【００６２】
【数１４】
2010092825.tif 000016
【００６３】
ここで、2つの独立な条件をそれぞれcond1,cond2とすると、cond1でありかつcond2である確率Pv[cond1&cond2](x)はPv[cond1](x)とPv[cond2](x)との積で表される[数15]。
【００６４】
【数１５】
2010092825.tif 000017
【００６５】
また、cond1でありかつcond2であるxの条件付き確率密度関数φv[cond1&cond2](x)は[数16]で表される。
【００６６】
【数１６】
2010092825.tif 000018
【００６７】
クリティカルエッジ計算(ST220)
ある点vにおいて、vへ入る枝の集合をev＝{e1,…,ek,…,en}とする。点vへ入る枝の終点における遅延d(e1),…,d(en)のうち遅延が最大となる枝をクリティカルエッジと呼ぶ。すなわち、点vに入る枝ek＝(u,v)がクリティカルエッジであるとは、ekの終点における遅延d(ek)がvに入る他の枝e'＝(u',v)の遅延d(e')より大きいことを意味する。またこのとき、クリティカルエッジの終点における遅延は点vにおける遅延に等しい。
【００６８】
今、点vに入る枝ekがクリティカルエッジであるという条件をek∈Eceと表す。ある枝ekの遅延がxk＝d(ek)のとき、枝ekがクリティカルエッジである確率P[ek∈Ece](xk)は、x＝{x1,…,xn}＝{d(e1),…,d(en)}においてek以外の枝ej(j＝1,…,n、j≠k)における遅延xj＝d(ej)がすべてxk以下である確率と考えることができる。従って[数17]のように表すことができる。
【００６９】
【数１７】
2010092825.tif 000019
【００７０】
ここで、jn(x)はn変量x＝{x1,…,xn}に関する確率密度関数であり、一般に正規分布関数と近似できることが知られている。
【００７１】
n＝1の場合、枝e1の遅延がx1＝d(e1)のとき、枝e1がクリティカルエッジである確率P[e1∈Ece](x1)は[数18]で表される。すなわち、点vに入る枝e1がクリティカルエッジとなる。
【００７２】
【数１８】
2010092825.tif 000020
【００７３】
また、ek∈Eceとなるxk＝d(ek)の条件付き確率密度関数φek[ek∈Ece](xk)は[数17]と同様に[数19]で表される。
【００７４】
【数１９】
2010092825.tif 000021
【００７５】
ここで、n変量の正規分布関数jn(x)は[数20]であらわされる。
【００７６】
【数２０】
2010092825.tif 000022
【００７７】
また、(x−μ)T＝(x1-μ1 x2-μ2 … xN-μN)は(x−μ)の転置行列である。ここでσijは、[数21]で定義される行列σijの逆行列(σij＝(σij)-1)である。
【００７８】
【数２１】
2010092825.tif 000023
【００７９】
なお、n＝1の場合、e1∈Eceとなるx1＝d(e1)の条件付き確率密度関数φe1[e1∈Ece](x1)は[数22]で表される。このときj1(x1)は、x1＝d(e1)の確率密度関数である。
【００８０】
【数２２】
2010092825.tif 000024
【００８１】
[数19]の計算には積分が含まれているが、[数23]に示す近似を用いれば簡単に計算することもできる。
【００８２】
【数２３】
2010092825.tif 000025
【００８３】
ここでF(Fは自然数)は積分計算の分割数であり、a,b(a＜b)はそれぞれ近似計算領域の下限,上限である。d(＞0)は積分計算の分割幅であり[数24]で定義する。a→−∞およびb,F→∞のとき近似誤差は0となる。
【００８４】
【数２４】
2010092825.tif 000026
【００８５】
グラフGに含まれるすべての枝ekに対し、クリティカルエッジとなる条件付き確率密度関数φek[ek∈Ece](xk)は、以下に示す[アルゴリズム1]で求めることができる。
【００８６】
[アルゴリズム1]
(1)…アサイクリックグラフG＝{V,E}において、すべての点v(v∈V)およびすべての枝e(e∈E)の終点における遅延の確率密度関数jv(x)およびje(x)を[特許文献1]の手法により計算する。
(2)…グラフ中から1つの点v(v∈V)を選択する。
(3)…選択された点vに入ってくる各枝ekに対し、[数19]を適用し、枝ekがクリティカルエッジとなるときの枝ekの終点における遅延の条件付き確率密度関数φek[ek∈Ece](xk)を計算する。
(4)…すべての点に対し上記(2)〜(3)を適用する。
【００８７】
[数20][数21]よりn変量の確率密度関数jn(x1,…,xn)の計算の複雑度はＯ(n2)である。したがって、φek[ek∈Ece](xk)の計算の複雑度は[数19][数23]よりＯ(n3×F)となる。グラフGに含まれる全枝数すなわち回路規模をN、枝ekの終点に入る枝の数をn(ek)とすると、グラフGに含まれるすべての枝ekに対し、クリティカルエッジとなるxkの条件付き確率密度関数φek[ek∈Ece](xk)を求める計算の複雑度は、
【００８８】
【数２５】
2010092825.tif 000027
【００８９】
である。ただし、回路規模が大きい,すなわち,N≫n(ek)およびN≫Fのとき、φek[ek∈Ece](xk)の計算の複雑度はＯ(N)となるので、十分実用的な計算時間で計算することができる。
【００９０】
クリティカルパス率計算(ST230)
次に、クリティカルパス率計算処理ST230において、グラフ中の点や枝がクリティカルパス上の点や枝となる確率を計算する。なお、クリティカルパス上の点や枝は、設計対象回路におけるクリティカルパス上の素子や配線に対応している。
【００９１】
(クリティカルパス定義)
アサイックリックグラフG＝{V,E}において、ソースに対応する点vsを始点,シンクに対応する点vtを終点とする経路をパスpと呼び、p＝{Ep,Vp}と表す。ここで、Ep＝{ep1,…,epj,…,epm}はパスp上の枝の集合、Vp＝{vp0,…,vpj,…,vpm}はパスp上の点の集合であり、vp0はシンクvtに対応する点,vpmはソースvsに対応する点であり、各点はシンクからソースへの順にソートされているとする。すなわち、枝epjの始点,終点はそれぞれvpj,vp(j-1)に対応する。また、グラフGにおけるすべてのパスの集合をp＝{p1,…,pj,…,pn}とし、各パスpjに対して、pjに含まれる全ての枝eの遅延t(e)の総和をpjのパス遅延と呼び、t(pj)と表す。パス遅延t(pj)が最大のパスをクリティカルパスと呼び、点v,枝eがクリティカルパス上の点,枝であるという条件をそれぞれv∈Vcp,e∈Ecpと表す。
【００９２】
ここで、枝e＝(u,v)がクリティカルパスに含まれる(e∈Ecp)ということは、枝eの始点u,終点vが共にクリティカルパスに含まれ(u,v∈Vcp),かつ,枝eがクリティカルエッジである(e∈Ece)ことを意味する。一方、点vがクリティカルパスに含まれる(v∈Vcp)ということは、点vに入ってくる枝ei＝(u,v)のうち少なくとも1つがクリティカルパスに含まれ,かつ,点vから出て行く枝eo＝(v,w)のうち少なくとも1つがクリティカルパスに含まれることを意味する。
【００９３】
このとき、ある点vにおいて、点vから出る枝の集合をeo＝{eo1,…,eoj,…,eom},点vに入る枝の集合をei＝{ei1,…,eik,…,ein}とする。点vから出る枝eojがクリティカルパス上の枝となる確率P[eoj∈Ecp]の総和
【００９４】
【数２６】
2010092825.tif 000028
【００９５】
および点vに入る各枝eikがクリティカルパス上の枝となる確率P[eik∈Ecp]の総和
【００９６】
【数２７】
2010092825.tif 000029
【００９７】
は、どちらも点vがクリティカルパス上の点となる確率P[v∈Vcp]に等しくなる[数28]。
【００９８】
【数２８】
2010092825.tif 000030
【００９９】
また、点v(v∈V)がクリティカルパス上の点となるときの点vにおける遅延d(v)の条件付き確率密度関数をφv[v∈Vcp](x)とし、点vから出る枝eojがクリティカルパス上の枝となるときの点vにおける遅延の条件付き確率密度関数をφv[eoj∈Ecp](x)とする。点vがクリティカルパス上の点となるときのd(v)＝xの条件付き確率密度関数φv[v∈Vcp](x)は、点vから出る各枝eojがクリティカルパス上の枝となるときの条件付き確率密度φv[eoj∈Ecp](x)の総和
【０１００】
【数２９】
2010092825.tif 000031
【０１０１】
および点vへ入る各枝eikがクリティカルパス上の枝となるときの条件付き確率密度φv[eik∈Ecp](x)の総和
【０１０２】
【数３０】
2010092825.tif 000032
【０１０３】
に等しくなる[数31]。
【０１０４】
【数３１】
2010092825.tif 000033
【０１０５】
(条件付き確率密度分布の継承)
点vにおける遅延d(v)がxであるときに点vがクリティカルパス上の点である確率をPv[v∈Vcp](x)と表し、d(v)＝xであるときに枝eがクリティカルエッジである確率をPv[e∈Ece](x)と表す。今、点vに入る枝eがクリティカルエッジであるか否かは、ソースvsからvに到るパスで決まるのに対して、点vがクリティカルパス上の点であるか否かはソースvsからシンクvtに到る全てのパスによって決まる。したがって、ソースvsに近い点v(すなわち、vsからvに到るパスに含まれる枝の個数の最小値が、vsからvtに到るパスに含まれる枝の個数の最小値に比べて小さいような点)に対しては「d(v)＝xであるときにv∈Vcpであること」および「d(v)＝xであるときにe∈Eceであること」はほぼ独立であると考えることができる。
【０１０６】
そのため、[数15]より、枝eの終点vへの遅延がd(v)＝xであるとき枝eがクリティカルパス上の枝である確率Pv[e∈Ece](x)は、v∈Vcpでありかつe∈Eceである確率であるから、[数32]で表される。
【０１０７】
【数３２】
2010092825.tif 000034
【０１０８】
e∈Ecpあるいはe∈Eceのとき、枝eの終点における遅延d(e)が点vの遅延d(v)となる。それゆえ、e∈Ecpあるいはe∈Eceの条件下では、枝eの終点における遅延d(e)がxであるとき点vがクリティカルパス上の点である確率をPe[v∈Vce](x)とし、枝eの終点における遅延d(e)がxであるとき枝eがクリティカルエッジである確率をPe[e∈Ece](x)とすると、[数33]が成り立つ。
【０１０９】
【数３３】
2010092825.tif 000035
【０１１０】
したがって[数32]は[数34]のようになる。
【０１１１】
【数３４】
2010092825.tif 000036
【０１１２】
ここで、枝eの始点uにおける遅延をx＝d(u),枝eの終点vにおける遅延をz＝d(v),枝eの遅延をy＝t(e)とし、x＝d(u)とy＝t(e)の2変量確率密度関数をju,t(e)(x,y)とすると、z＝x+yであるから、[数3]より、e∈Ecpとなるx,yの条件付き確率密度関数φu,t(e)[e∈Ecp](x,y)は、x,yの2変量確率密度関数ju,t(e)(x,y)と、e∈Ecpとなる確率Pe[e∈Ecp](z)(＝Pe[e∈Ecp](x＋y))との積で表される[数35]。
【０１１３】
【数３５】
2010092825.tif 000037
【０１１４】
ここで、P[e∈Ecp](x,y)は、枝eの始点uの遅延がx＝d(u)、枝eの遅延がy＝t(e)のときに、e∈Ecpとなる確率である。従って、e∈Ecpとなるxの条件付き確率密度関数φu[e∈Ecp](x)は、φu,t(e)[e∈Ecp](x,y)を枝ekの遅延yで積分することにより得られるから、
【０１１５】
【数３６】
2010092825.tif 000038
【０１１６】
となる。
【０１１７】
ここで、[数4]より、
【０１１８】
【数３７】
2010092825.tif 000039
【０１１９】
である。
【０１２０】
ここで、ju,t(e)(x,y),je(x),jv(x)は[特許文献1]の手法により、またφe[e∈Ece](x)は[数19]によりあらかじめ計算可能であるから、点vがクリティカルパス上の点となる点vの条件付き確率密度関数φv[v∈Vcp](x)が既知であれば、点vに入る各枝ekがクリティカルパス上の枝となる枝ekの始点uにおける遅延の条件付き確率密度関数φu[e∈Ecp](x)を得ることができる。
【０１２１】
(各枝のクリティカルパス率計算)
シンクに対応する点vt(＝vp0)はすべてのパスに含まれる点である。したがって、シンクvtがクリティカルパス上の点となるvtの条件付き確率密度関数φvt[vt∈Vcp](x)は、vtの確率密度関数jvt(x)に等しい（[数38]および[数39]）。
【０１２２】
【数３８】
2010092825.tif 000040
【０１２３】
【数３９】
2010092825.tif 000041
【０１２４】
したがって、アサイクリックグラフG＝{V,E}において、グラフ中の任意の点vがクリティカルパス上の点となる点vにおける遅延の条件付き確率密度関数φvt[vt∈Vcp](x)、および、回路中の任意の枝eがクリティカルパス上の枝となる枝eの始点uにおける遅延の条件付き確率密度関数φu[e∈Ecp](x)は、以下に示す[アルゴリズム2]で計算することができる。
【０１２５】
[アルゴリズム2]
(1)…すべての枝eに対し、クリティカルエッジとなる条件付き確率密度関数φe[e∈Ece](x)を[数19]により計算する。
(2)…シンクに対応する点vtに[数39]で示す初期値を設定する。
(3)…アサイクリックグラフにおいて逆トポロジカル順に枝eを選択する。
(4)…選択した枝eがクリティカルパス上の点となる枝eの始点uにおける遅延の条件付き確率密度関数φu[e∈Ecp](x)を[数36]〜[数37]により計算する。
(5)…点uから出る枝eojのすべてに対してφu[eoj∈Ecp](x)が計算済みの場合、[数31]により、点uがクリティカルパス上の点となる点uの遅延の条件付き確率密度関数φu[u∈Vcp](x)を計算する。
(6)…すべての枝および点に対し上記(3)〜(5)の処理を繰り返す。
【０１２６】
設計対象回路に遅延制約としてDが課せられている場合は、パスpがクリティカルパスであり,かつ,パス遅延値がD以上となる確率を求めればよい。したがって、[数39]の代わりに[数40]を初期値として用いることにより求めることができる。ここで、u(x)はステップ関数である。
【０１２７】
【数４０】
2010092825.tif 000042
【０１２８】
枝eがクリティカルパス上の枝となる確率P[e∈Ecp]および点vがクリティカルパス上の点となる確率P[v∈Vcp]は、点vおよび枝eがクリティカルパス上となる条件付き確率密度関数φv[v∈Vcp](x)およびφu[e∈Ecp](x)を積分することにより得ることができる[数41]。
【０１２９】
【数４１】
2010092825.tif 000043
【０１３０】
回路規模をN,積分計算の分割数をFとすると、グラフGに含まれるすべての点についてその点がクリティカルパス上の点となる確率P[v∈Vcp]およびすべての枝についてその枝がクリティカルパス上の枝となる確率P[e∈Ecp]を求める計算の複雑度は、N≫FのときＯ(N)となる。したがって、本方法の計算処理時間は十分実用的であると言える。
【０１３１】
回路修正候補決定(ST240)
次に回路修正候補決定処理ST240では、遅延改善のための回路修正候補情報500を出力する。回路修正候補情報500は、クリティカルパス率の高い枝でもよいし、回路修正による面積あるいは消費電力増などのコストに対する遅延改善率等の感度を表す係数をクリティカルパス率に乗じてもよい。抽出する改善候補の数は、あらかじめ指定された数としてもよいし、クリティカルパス率がある確率を超えるものだけを抽出してもよい。遅延制約Dが与えられている場合は[数40]の値が正となる枝をすべて抽出すればよい。
【０１３２】
図12は、回路修正候補決定処理ST240の結果抽出される回路修正候補情報500の例である。図12では、Instance2,Instance3,配線eが回路修正候補であることを示している。
【０１３３】
図13は回路修正候補情報500の別の形態の例である。図13では、図12に示す修正候補に対する具体的修正内容を示している。図13では、修正候補であるInstance2をCell3に置き換え,Instance3をCell4に置き換え、また、Cell5をInstance4として挿入し、ネットeをInstance2の出力端子Yから切断してInstance4の出力端子Yへ接続し、さらにIncetance2の出力端子YとInstance4の入力端子Aとをネットgで接続することを意味している。
【０１３４】
回路改善(ST300)
最後に図1の回路改善処理ST300では、回路修正候補情報500に基づいて回路情報100の修正を行う。
【０１３５】
たとえば、図12の回路修正候補情報500を用いる場合、入力端子Bを通るパスの遅延削減となる様、Instance2およびInstance3をより高速なセルに置換すればよい。また、他の配線を迂回させるなどして配線eをより優先的に引きなおすことにより配線eの遅延を削減することができる。
【０１３６】
図16は、回路情報100がレイアウト情報(図2の配置済み回路情報100b,配線済み回路情報100c)である場合の設計対象回路の回路情報100の例である。
【０１３７】
図16(a)は、回路改善処理ST300による修正が行われる前の回路情報100の例であり、図3の回路情報100のレイアウト情報である。Instance1,Instance2,Instance3にそれぞれCell1,Cell1,Cell2が配置され、b,d,eのネットがそれぞれ配線されている。
【０１３８】
図16(b)は、図16(a)の回路情報100に対して回路改善処理ST300による修正が図12の回路修正候補情報500に基づいて行われた後の回路情報100の例である。回路修正候補情報500としてネットeが抽出された場合の修正例を表している。ネットbの配線を迂回させることにより、クリティカルパス率の高いネットeを優先的に配線して遅延を削減することで、同じ面積で遅延改善効果を得ることができる。
【０１３９】
また、図13の回路修正候補情報500を用いる場合、Instance2,Instance3をそれぞれCell1,Cell2から能力のより高いCell3,Cell4へ置き換え、ネットeへバッファ(Cell5)を挿入することにより遅延を削減することができる。
【０１４０】
図15は、図3の回路情報100に対して回路改善処理ST300による修正が図13の回路修正候補情報500に基づいて行われた後の回路情報100の例である。図15では、新たにInstance4としてCell5が挿入され、Instance4の入力端子AがInstance2の出力端子Yと接続されている。また、Instance2,Instance3がそれぞれCell1,Cell2からCell3,Cell4に置き換えられ、Instance3の入力端子Bの接続先がInstance2からInstance4に修正されている。
【０１４１】
図16(c)は、図16(a)の回路情報100に対して回路改善処理ST300による修正が図13の回路修正候補情報500に基づいて行われた後の回路情報100の例を表しており、図15の回路情報100に対応したレイアウトである。クリティカルパス率の高いInstance2,Instance3のセルをより遅延の少ないセルに置き換え、また、ネットbを迂回させることにより、クリティカルパス率の高いネットeを優先的に配線し、さらにネットeに対しCell5のバッファ挿入を行うことで、遅延改善効果を得ることができる。
【０１４２】
以上、本実施形態によれば、遅延分布および遅延相関を精度よく考慮して、設計対象回路の遅延を削減することが可能である。
【０１４３】
上記実施形態にはさまざまな変形例がある。それらのいくつかを以下に説明する。
【０１４４】
図17は、図1に示す実施形態による処理から回路改善処理ST300を省略した変形例を示す。回路改善処理ST300を省略しても、最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。回路改善を、必要に応じて市販のレイアウトツールや設計者自身の回路修正作業と組み合わせて行うことにより、より柔軟に設計フローを選択することが可能になる。
【０１４５】
図18は、図1に示す実施形態による処理から遅延分布計算ST100を省略した変形例を示す。遅延分布計算ST100を省略しても、最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。遅延分布計算を、必要に応じて市販の遅延解析ツールや設計者自身の計算と組み合わせて行うことにより、より柔軟に設計フローを選択することが可能になる。
【０１４６】
図19は、図1に示す実施形態による処理から回路改善処理ST300および遅延分布計算ST100を省略した変形例を示す。回路改善処理ST300および遅延分布計算ST100を省略しても、最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。遅延分布計算および回路改善を、必要に応じて市販の遅延解析ツールまたはレイアウトツールや設計者自身の計算または回路修正作業と組み合わせて行うことにより、より柔軟に設計フローを選択することが可能になる。
【０１４７】
図20は、図1に示す実施形態による処理から遅延相関情報400を省略した変形例を示す。遅延相関情報400を省略しても、回路によっては精度は低下するものの最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。例えば計算時間が増大する等の理由で遅延相間情報の出力が困難な場合でも、本発明の効果を得ることが可能である。
【０１４８】
図21は、図1に示す実施形態による処理において、回路修正候補抽出処理ST200と、回路改善処理ST300とを、同じ計算機を用いて同じプログラム内で連続して処理ST400として実行する変形例を示す。回路修正候補情報500は、計算機のメモリ上に内部データとして保持していればよく、データファイルとして出力する必要はない。内部データとして保持する場合、特に、回路修正候補決定処理ST240と回路改善処理ST300とが、同じ計算機を用いて同じプログラム内で連続実行される場合は、ファイルの読み書きにかかる時間を短縮することができる。一方、異なるプログラムを用いる場合には、回路修正候補情報500をデータファイルとして出力したほうが好ましい。
【０１４９】
図22は、図21に示す実施形態による処理から遅延分布計算ST100を省略した変形例を示す。図22の変形例は、図21の変形例の持つ効果に加えて、図18の変形例の持つ効果を有する。
【産業上の利用可能性】
【０１５０】
本発明は、半導体集積回路設計において、計算機を用いてプロセス情報等に基づいて回路の特性をシミュレーションし性能改善するのに有用である。
【符号の説明】
【０１５１】
100…回路情報
200…テクノロジ情報
300…遅延分布情報
400…遅延相関情報
500…回路修正候補情報
ST100…遅延分布計算処理
ST200…回路修正候補抽出処理
ST300…回路改善処理
【図１】
2010092825.tif 000044
【図２】
2010092825.tif 000045
【図３】
2010092825.tif 000046
【図４】
2010092825.tif 000047
【図５】
2010092825.tif 000048
【図６】
2010092825.tif 000049
【図７】
2010092825.tif 000050
【図８】
2010092825.tif 000051
【図９】
2010092825.tif 000052
【図１０】
2010092825.tif 000053
【図１１】
2010092825.tif 000054
【図１２】
2010092825.tif 000055
【図１３】
2010092825.tif 000056
【図１４】
2010092825.tif 000057
【図１５】
2010092825.tif 000058
【図１６】
2010092825.tif 000059
【図１７】
2010092825.tif 000060
【図１８】
2010092825.tif 000061
【図１９】
2010092825.tif 000062
【図２０】
2010092825.tif 000063
【図２１】
2010092825.tif 000064
【図２２】
2010092825.tif 000065
【手続補正書】
【提出日】平成23年4月27日(2011.4.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
半導体集積回路の解析を行う方法であって、
設計対象回路を表す回路情報(100)を取得するステップと、
設計対象プロセスに基づいた素子および/または配線の特性分布を表すテクノロジ情報(200)を取得するステップと、
前記設計対象回路における遅延の分布を表す遅延分布情報(300)を取得するステップと、
前記設計対象回路における遅延のばらつきの相関を表す遅延相関情報(400)を取得するステップと、
前記回路情報(100)，前記テクノロジ情報(200)，前記遅延分布情報(300)，前記遅延相関情報(400)に基づいて、前記設計対象回路の遅延の改善のための回路修正候補を表す回路修正候補情報(500)を生成する回路修正候補抽出ステップ(ST200)と、
を備える回路解析方法。
【請求項２】
前記回路修正候補抽出ステップ(ST200)は、
前記回路情報(100)から前記設計対象回路を点と枝で表現するグラフを生成するグラフ作成ステップ(ST210)と、
前記グラフ作成ステップ(ST210)で生成されたグラフの各枝についてその枝がクリティカルエッジとなる確率を計算するクリティカルエッジ計算ステップ(ST220)と、
前記グラフ作成ステップ(ST210)で生成されたグラフの各点，各枝についてその点，その枝がクリティカルパス上の点，枝となる確率を計算するクリティカルパス率計算ステップ(ST230)と、
前記クリティカルエッジ計算ステップ(ST220)，前記クリティカルパス率計算ステップ(ST230)における計算結果に基づいて前記回路修正候補情報(500)を生成する回路修正候補決定ステップ(ST240)とを含む
請求項１に記載の回路解析方法。
【請求項３】
前記回路修正候補情報(500)に基づいて前記回路情報(100)の修正を行う回路改善ステップ(ST300)をさらに備える
請求項１に記載の回路解析方法。
【請求項４】
前記回路情報(100)に記述された接続関係からパスを解析し、当該パス解析結果と前記テクノロジ情報(200)に記述された遅延情報とから、前記設計対象回路を解析した結果として前記遅延分布情報(300)と前記遅延相関情報(400)とを出力する遅延分布計算ステップ(ST100)をさらに備える
請求項１に記載の回路解析方法。
【請求項５】
前記遅延の改善は、
前記設計対象回路の遅延違反の削減，もしくは，前記設計対象回路の最大遅延の削減を含む
請求項１に記載の回路解析方法。
【請求項６】
前記回路修正候補情報(500)は、
少なくとも１つのセルまたは配線を含む
請求項１に記載の回路解析方法。
【請求項７】
前記遅延は、
クロックもしくはフリップフロップの信号変化から当該信号変化の影響による回路中の他の地点の信号変化までにかかる時間を含む
請求項１に記載の回路解析方法。
【請求項８】
前記回路修正候補抽出ステップ(ST200)では、
前記遅延分布情報(300)と前記遅延相関情報(400)を考慮して、クリティカルパスになる確率の高い候補を抽出することにより前記回路修正候補情報(500)を生成する
請求項１に記載の回路解析方法。
【請求項９】
前記遅延相関情報(400)は、
少なくとも１対の遅延のばらつきの相関係数を表した情報を含む
請求項１に記載の回路解析方法。
【請求項１０】
前記回路情報(100)は、
半導体集積回路の論理設計工程での論理合成によって生成された論理回路情報(100a)である
請求項１に記載の回路解析方法。
【請求項１１】
前記回路情報(100)は、
半導体集積回路の配置設計工程での配置設計後に生成される配置済み回路情報(100b)である
請求項１に記載の回路解析方法。
【請求項１２】
前記回路情報(100)は、
半導体集積回路の配線設計工程での配線設計後に生成される配線済み回路情報(100c)である
請求項１に記載の回路解析方法。
【請求項１３】
請求項１に記載の回路解析方法をコンピュータに実行させるための回路解析プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は半導体集積回路設計において、計算機を用いてプロセス情報等に基づいて回路の特性をシミュレーションし性能改善する方法に関するものである。
【背景技術】
【０００２】
半導体集積回路設計において、微細化により、プロセスばらつきの回路特性への影響が増大している。そのため、半導体集積回路を構成する各素子の遅延のばらつきを正規分布で表し、統計的演算を用いて回路全体の遅延分布を見積もる技術(以下、統計的遅延解析手法)があった。
【０００３】
統計的遅延解析手法として[特許文献1]の手法が提案されている。[特許文献1]では、CMOS組み合わせ回路に対し、素子・配線・パス間の遅延の相関を考慮して静的に最大遅延の分布を計算することができる。
【０００４】
図3は設計対象回路の例であり、図4は図3の回路をアサイクリックグラフG＝{V,E}で表現した例である。ここで、Vはグラフの点集合、Eはグラフの枝集合を表している。[特許文献1]に示す様に、回路の各端子v(21,22)に値0を伝搬させるのに要する真の最大遅延をd0(v)、値1を伝搬させるのに要する真の最大遅延をd1(v)として、回路全体の出力端子に対するこれらの値の最大値を見出すという方法があった。
【０００５】
ここで、回路全体の入出力，論理ゲートの入出力の各端子は、グラフの点vに対応し、グラフの2つの点v0,v1に対応する。図4においては、これら1対の点(v0,v1)を点線の楕円(21,22)で囲み、v0は白抜きの点(23)で、v1は黒点(24)で表している。v0,v1は、それぞれ対応する端子vが信号値0,1をとることを示し、以下では、v0をvの0点、v1をvの1点と呼ぶ。
【０００６】
回路全体の入力端子に対応する点は、入ってくる枝のないソースであり、回路全体の出力端子に対応する点は出ていく枝の無いシンクである。以下では、ソースの集合(25)をS、シンクの集合(26)をTとする。また、グラフGのソースからシンクに至る有向道をパスとする。図4において、各矩形(27)は回路を構成する論理ゲートを示し、1つの矩形内の左側の点(21)は対応する論理ゲートの入力端子を、右側の点(22)は出力端子に対応する。矩形内の枝(28)は、論理ゲートの入力を表す点から出て出力を表す点に入り、矩形がNANDゲートやNORゲートである場合には、そのゲート内のpMOSあるいはnMOSに対応する。異なる矩形に属す点を結ぶ枝は配線に対応し、0点から出た枝e0は0点に入り、1点から出た枝e1は1点に入る。
【０００７】
回路の各端子vに対する最大遅延d0(v),d1(v)を、それぞれグラフG上の点vの0点(v0),1点(v1)へのあるシンクからの最大パス長d(v0),d(v1)に対応させる。そのため、u,vをそれぞれ枝の始点,終点とすると、各枝e＝(u,w)に対して、信号値をuからwに伝達するのに要する遅延を枝eの重みt(e)として与える。
【０００８】
このようなアサイクリックグラフを用いてシミュレーションすることにより、比較的簡単な処理で論理回路の遅延解析を行なうことが可能であった。
【０００９】
一方、[特許文献2]では、各セルに入力される遅延時間及び遷移時間の確率分布に相関関係があることに着目し、遅延分布計算手段によって遅延情報を計算し、遅延情報に基づきタイミング解析を行い、回路を改善する方法があった。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開2002-279012号公報
【特許文献２】特開2007-304957号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、LSIの設計性能を向上させるためには、クリティカルパス遅延に影響を与える素子や配線を精度よく発見し、改善する必要がある。そのためには、各素子や配線がクリティカルパスの一部となる確率を精度よく見積もる必要がある。
【００１２】
また、図3に示されるような回路で信号fを計算しようとする際に、信号dと信号eの信号伝達時間(遅延)が信号bの遅延に大きく依存するような場合、信号dの遅延と信号eの遅延の間には大きな相関がある。また、配線遅延にもばらつきがあるような場合、信号bのファンアウトの信号伝達遅延にも相関がある。従って、相関を考慮しない統計的遅延解析手法は正確さを欠く可能性が高い。遅延分布見積もりの精度が悪い場合、半導体集積回路の設計においては、実際には確率的にほとんど起こり得ないいくつもの最悪条件が重なった場合においての正常動作を保証せねばならず、オーバーマージンを含んだ設計にならざるを得ない。このため、設計された半導体集積回路においては、必要以上に面積や消費電力等のコストを増大させてしまう。
【００１３】
一方、[特許文献2]の方法では、遅延と入力遷移時間の間の相関情報等を用いて遅延分布計算を精度良く行う方法が開示されているが、回路改善候補を選択する際にパス遅延の相関を考慮することはできなかった。すなわち、遅延分布解析でいくら精度を向上させても、回路改善を精度よく行うことができず、回路修正後の遅延分布計算において、見積り以下の遅延改善効果しか得られないことになる。回路修正と遅延分布計算の工程を必要以上に繰り返すことにより設計期間を増大させてしまうか,あるいは,過剰に回路修正してしまうことにより、半導体集積回路面積や消費電力を必要以上に増大させてしまう。
【００１４】
本発明は、トランジスタ等の部品や配線の遅延のばらつきの相関を考慮して、正確に組合せ回路の最大遅延を削減することを課題とする。
【課題を解決するための手段】
【００１５】
本発明のある実施形態による回路解析方法は、半導体集積回路の解析を行う方法であって、設計対象回路を表す回路情報(100)を取得するステップと、設計対象プロセスに基づいた素子および/または配線の特性分布を表すテクノロジ情報(200)を取得するステップと、前記設計対象回路における遅延の分布を表す遅延分布情報(300)を取得するステップと、前記設計対象回路における遅延のばらつきの相関を表す遅延相関情報(400)を取得するステップと、前記回路情報(100)，前記テクノロジ情報(200)，前記遅延分布情報(300)，前記遅延相関情報(400)に基づいて、前記設計対象回路の遅延の改善のための回路修正候補を表す回路修正候補情報(500)を生成する回路修正候補抽出ステップ(ST200)とを備えることを特徴とする。
【００１６】
上記回路解析方法によれば、設計対象回路の遅延の改善のための回路修正候補を精度よく見積もることができ、面積や消費電力等のコストを削減することができる。
【発明の効果】
【００１７】
本発明によれば、最大遅延削減あるいは遅延制約違反解消のために、遅延相関情報を考慮して回路改善箇所を抽出することにより、より精度よく改善候補を見積もることが可能となる。すなわち、遅延制約違反解消に至る回路改善回数の削減効果、あるいは、回路改善終了時点での半導体集積回路において、面積や消費電力等のコストをより削減することできるという効果がある。
【図面の簡単な説明】
【００１８】
【図１】回路解析プログラムに従って行われる処理の流れを示す図である。
【図２】半導体集積回路の設計フローを示す図である。
【図３】設計対象回路の回路情報100の例を示す図である。
【図４】図３の回路をアサイクリックグラフで表現した図である。
【図５】図３の回路をアサイクリックグラフで表現した図である。
【図６】図３の回路をアサイクリックグラフで表現した図である。
【図７】テクノロジ情報200の例を示す図である。
【図８】遅延分布情報300の例を示す図である。
【図９】遅延分布情報300の例を示す図である。
【図１０】遅延相関情報400の例を示す図である。
【図１１】遅延相関情報400の例を示す図である。
【図１２】回路修正候補情報500の例を示す図である。
【図１３】回路修正候補情報500の例を示す図である。
【図１４】回路修正候補抽出処理ST200において行われる処理の流れを示す図である。
【図１５】回路改善処理ST300による修正が行われた後の回路情報100の例を示す図である。
【図１６】回路改善処理ST300による修正が行われた後の回路情報100の例を示す図である。
【図１７】回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図１８】回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図１９】回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図２０】回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図２１】回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【図２２】回路解析プログラムに従って行われる処理の流れの変形例を示す図である。
【発明を実施するための形態】
【００１９】
以下、好ましい実施形態について図面を参照して説明する。
【００２０】
本実施形態による回路解析プログラムは、PC等の情報処理装置，ネットワークを介して端末装置から利用可能な形態で設定されたサーバ装置に保持されうる。また、CD-ROM，DVD-ROM，フラッシュメモリ等の各種記録媒体に当該プログラムを記録して流通させることもできる。そしてPC等の情報処理装置に上記の記録媒体を装着して当該プログラムを読み出す,あるいは,情報処理装置が備えている記憶媒体に当該プログラムを記憶させておき必要に応じて読み出すことにより、当該プログラムに関わる機能を実現することができる。以下、当該プログラムに従って行われる処理の流れを説明する。
【００２１】
本実施形態の回路解析プログラムに従って行われる処理の流れを図1に示す。回路解析プログラムを実行するコンピュータ(計算機)は、データベースとして回路情報100，テクノロジ情報200，遅延分布情報300，遅延相関情報400，回路修正候補情報500を有しており、これらを利用して遅延分布計算処理ST100，回路修正候補抽出処理ST200，回路改善処理ST300を行い、もとの回路情報100を修正する。
【００２２】
図2は半導体集積回路の設計フローである。本実施形態では、図1の回路情報100として、図2の論理設計工程での論理合成によって生成された論理回路情報100aを用いてもよいし、配置設計工程での配置設計後に生成される配置済み回路情報100b,あるいは,配線設計工程での配線設計後に生成される配線済み回路情報100cなどレイアウトの情報を用いてもよい。配置済み回路情報100bを用いる場合には、回路改善処理ST300に基づいてもとの配置済み回路情報100bを修正するだけでなく、もとの論理回路情報100aを修正することもできる。配線済み回路情報100cを用いる場合には、回路改善処理ST300に基づいてもとの配線済み回路情報100cを修正するだけでなく、もとの論理回路情報100a,配置済み回路情報100bを修正することもできる。
【００２３】
図3は設計対象回路の回路情報100の例である。図3(a)は回路図、図3(b)は図3(a)の回路を表したネットリストである。
【００２４】
図1のテクノロジ情報200には、設計対象プロセスに基づいた遅延や電流などの素子の特性の情報が含まれる。図7はテクノロジ情報200の例であり、半導体集積回路を構成する論理セルの遅延特性を表している。図7において、Cell1はnandの論理を持っており、入力端子Aから出力端子Yに至る遅延は平均3.0,標準偏差0.2であり、入力端子Bから出力端子Yに至る遅延は平均2.8,標準偏差0.2であることを示している。Cell3についても同様である。Cell2はorの論理を持っており、入力端子Aから出力端子Yに至る遅延は平均4.0,標準偏差0.2であり、入力端子Bから出力端子Yに至る遅延は平均3.8,標準偏差0.3であることを示している。Cell4についても同様である。Cell5はbufferの論理を持っており、入力端子Aから出力端子Yに至る遅延は平均0.3,標準偏差0.1であることを示している。
【００２５】
遅延分布計算(ST100)
図1の遅延分布計算処理ST100では、回路情報100とテクノロジ情報200とを入力とし、回路情報100に記述された接続関係からパスを解析し、またテクノロジ情報200に記述された遅延情報とから、対象とする回路を解析した結果として遅延分布情報300と遅延相関情報400とを出力する。遅延分布計算処理ST100は、例えば[特許文献1]に開示された方法で行うことができる。
【００２６】
図8は、遅延分布情報300の例である。図8の例は、
Instance1の入力端子Aの遅延は平均0,標準偏差0、
Instance1の入力端子Bの遅延は平均0,標準偏差0、
Instance2の入力端子Aの遅延は平均0.5,標準偏差0.1、
Instance2の入力端子Bの遅延は平均0.6,標準偏差0.1、
Instance3の入力端子Aの遅延は平均3.0,標準偏差0.2、
Instance3の入力端子Bの遅延は平均4.0,標準偏差0.3、
であることを表している。
【００２７】
図9は遅延分布情報300の別の形態である。図9の例は、
遅延の最小値(Min)は、
Instance1の入力端子Aは0、
Instance1の入力端子Bは0、
Instance2の入力端子Aは0.2、
Instance2の入力端子Bは0.3、
Instance3の入力端子Aは2.4、
Instance3の入力端子Bは2.8、
遅延の代表値(Typ)は、
Instance1の入力端子Aは0、
Instance1の入力端子Bは0、
Instance2の入力端子Aは0.5、
Instance2の入力端子Bは0.6、
Instance3の入力端子Aは3.0、
Instance3の入力端子Bは4.0、
遅延の最大値(Max)は、
Instance1の入力端子Aは0、
Instance1の入力端子Bは0、
Instance2の入力端子Aは0.8、
Instance2の入力端子Bは0.9、
Instance3の入力端子Aは3.6、
Instance3の入力端子Bは5.2、
であることを表している。
【００２８】
一般的に、遅延の平均値をμ,遅延の標準偏差をσとすると、遅延の最大値(Max)および最小値(Min)をμ±3σと仮定し遅延計算に用いることが多いが、異なる定義を用いてもよい。また、代表値(Typ)は平均値であってもよいし、プロセスの目標値,あるいは,確率の最も高い値であってもよい。
【００２９】
図10は、遅延相関情報400の例である。図10の例は、
Instance1の入力端子Aの遅延とInstance1の入力端子Bの遅延との相関係数は0.3、
Instance1の入力端子Aの遅延とInstance2の入力端子Aの遅延との相関係数は0.3、
Instance1の入力端子Bの遅延とInstance2の入力端子Aの遅延との相関係数は1、
Instance1の入力端子Aの遅延とInstance3の入力端子Aの遅延との相関係数は0.5、
Instance2の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0.2、
Instance2の入力端子Bの遅延とInstance3の入力端子Bの遅延との相関係数は0.6、
であることを表している。また、上記以外は、相関係数は0である,または,相関関係は無視してよいということを表している。
【００３０】
図11は遅延相関情報400の別の形態である。図11の例は、
Instance1の入力端子Aの遅延とInstance1の入力端子Bの遅延との相関係数は0.3、
Instance1の入力端子Aの遅延とInstance2の入力端子Aの遅延との相関係数は0.3、
Instance1の入力端子Aの遅延とInstance2の入力端子Bの遅延との相関係数は0、
Instance1の入力端子Aの遅延とInstance3の入力端子Aの遅延との相関係数は0.5、
Instance1の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0、
Instance1の入力端子Bの遅延とInstance2の入力端子Aの遅延との相関係数は1、
Instance1の入力端子Bの遅延とInstance2の入力端子Bの遅延との相関係数は0、
Instance1の入力端子Bの遅延とInstance3の入力端子Aの遅延との相関係数は0、
Instance1の入力端子Bの遅延とInstance3の入力端子Bの遅延との相関係数は0、
Instance2の入力端子Aの遅延とInstance2の入力端子Bの遅延との相関係数は0、
Instance2の入力端子Aの遅延とInstance3の入力端子Aの遅延との相関係数は0、
Instance2の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0.2、
Instance2の入力端子Bの遅延とInstance3の入力端子Aの遅延との相関係数は0、
Instance2の入力端子Bの遅延とInstance3の入力端子Bの遅延との相関係数は0.6、
Instance3の入力端子Aの遅延とInstance3の入力端子Bの遅延との相関係数は0
であることを表している。
【００３１】
図8および図9の情報と同様に、図10および図11の情報は同値である。
【００３２】
回路修正候補抽出(ST200)
図1の回路修正候補抽出処理ST200において行われる処理の流れを図14に示す。
【００３３】
グラフ生成(ST210)
グラフ生成処理ST210では、読み込んだ回路情報100からグラフを生成し、計算機内部あるいは記録媒体に保存する。
【００３４】
図4〜6は、図3の論理回路を表すアサイクリックグラフの例である。図5では簡単のため、立ち上がりのパスと立下りのパスを共通の枝eおよび点vで表現している。さらに図6では、セル遅延を表す枝と配線遅延を表す枝を1つの枝で表現している。
【００３５】
アサイクリックグラフG＝{V,E}において、ある枝e(e∈E)の遅延をt(e)と表現する。t(e)はテクノロジ情報200に記述される。
【００３６】
回路の任意の点における遅延をxとし、xの分布の平均μおよび分散σ２、2枝e1,e2(e1,e2∈E)の遅延をそれぞれx1＝t(e1),x2＝t(e2)とする。このとき、任意の2枝x1,x2の間の相関係数ρ(x1,x2)は、遅延分布計算処理ST100により計算される。
【００３７】
ソースvsは、フリップフロップの出力端子としてもよいし、クロックとしてもよい。ソースvsから任意の点v(v∈V)への遅延の最大値を点vにおける遅延といい、d(v)で表す。d(v)も同様に[特許文献1]などの方法により計算され、遅延分布情報300として表される。また、点uからvへの枝e＝(u,v)(e∈E)に対してd(e)＝d(u)＋t(e)を枝eの終点における遅延といい、d(e)と表す。これらの遅延d(v),d(e)の確率密度関数をそれぞれjv(x),je(x)とする。jv(x),je(x)は、一般的に[数1],[数2]に示すような正規分布と近似できることが知られている。
【００３８】
【数１】
2010092825.tif 000066
【００３９】
【数２】
2010092825.tif 000067
【００４０】
ここでμv,σv2はd(vi)の平均,分散であり、μe,σe2はd(e)の平均,分散である。
【００４１】
クリティカルエッジ計算(ST220)
次に、クリティカルエッジ計算処理ST220では、多入力セルなど複数の信号が合流する点において、それぞれの信号がクリティカルとなる確率を計算する。
【００４２】
(条件付き確率密度関数)
d(v)＝xのときにある条件condが成立する確率をPv[cond](x)とする。点vにおける遅延d(v)の正規分布確率密度関数をjv(x)とし、d(v)＝xであるときの確率密度jv(x)とそのときにcondが成立する確率Pv[cond](x)との積を、condとなるxの条件付き確率密度関数と呼びφv[cond](x)で表す。このとき定義より[数3]が成立する。
【００４３】
【数３】
2010092825.tif 000068
【００４４】
したがって、d(v)＝xの確率密度関数jv(x),および,condとなるd(v)＝xの条件付き確率密度関数φv[cond](x)が既知である場合、d(v)＝xであるときに条件condが成立する確率Pv[cond](x)は[数4]で求めることができる。
【００４５】
【数４】
2010092825.tif 000069
【００４６】
条件condが成立する確率P[cond]は、d(v)＝xであるときにcondが成立する確率Pv[cond](x)とd(v)＝xの確率密度jv(x)との積を全領域にわたって積分すればよいので[数5]の関係が成立する。一方、通常の確率密度関数を全領域にわたって積分した場合、その値は1となる。
【００４７】
【数５】
2010092825.tif 000070
【００４８】
ここで、条件condの否定を/condとする。d(v)＝xであるときにcondが成立する確率Pv[cond](x)と、d(v)＝xであるときにcondが成立しない確率Pv[/cond](x)との和は1となる[数6]。
【００４９】
【数６】
2010092825.tif 000071
【００５０】
また[数6]を用いると[数7][数8]が成立する。
【００５１】
【数７】
2010092825.tif 000072
【００５２】
【数８】
2010092825.tif 000073
【００５３】
ここで、x＞c(cは定数)なる条件を考える。このとき、xのステップ関数をu(x)とすると、d(v)＝xであるときに条件x＞cが成立する確率Pv[x＞c](x)は[数9]で表すことができる。
【００５４】
【数９】
2010092825.tif 000074
【００５５】
したがって、x＞cとなるd(v)＝xの条件付き確率密度関数φv[x＞c](x)は[数10]で表される。
【００５６】
【数１０】
2010092825.tif 000075
【００５７】
また、d(v)＝xであるときにx＞cが成立しない確率をPv[/(x＞c)](x)とすると、
【００５８】
【数１１】
2010092825.tif 000076
【００５９】
であるので[数12][数13][数14]が成立する。
【００６０】
【数１２】
2010092825.tif 000077
【００６１】
【数１３】
2010092825.tif 000078
【００６２】
【数１４】
2010092825.tif 000079
【００６３】
ここで、2つの独立な条件をそれぞれcond1,cond2とすると、cond1でありかつcond2である確率Pv[cond1&cond2](x)はPv[cond1](x)とPv[cond2](x)との積で表される[数15]。
【００６４】
【数１５】
2010092825.tif 000080
【００６５】
また、cond1でありかつcond2であるxの条件付き確率密度関数φv[cond1&cond2](x)は[数16]で表される。
【００６６】
【数１６】
2010092825.tif 000081
【００６７】
クリティカルエッジ計算(ST220)
ある点vにおいて、vへ入る枝の集合をev＝{e1,…,ek,…,en}とする。点vへ入る枝の終点における遅延d(e1),…,d(en)のうち遅延が最大となる枝をクリティカルエッジと呼ぶ。すなわち、点vに入る枝ek＝(u,v)がクリティカルエッジであるとは、ekの終点における遅延d(ek)がvに入る他の枝e'＝(u',v)の遅延d(e')より大きいことを意味する。またこのとき、クリティカルエッジの終点における遅延は点vにおける遅延に等しい。
【００６８】
今、点vに入る枝ekがクリティカルエッジであるという条件をek∈Eceと表す。ある枝ekの遅延がxk＝d(ek)のとき、枝ekがクリティカルエッジである確率P[ek∈Ece](xk)は、x＝{x1,…,xn}＝{d(e1),…,d(en)}においてek以外の枝ej(j＝1,…,n、j≠k)における遅延xj＝d(ej)がすべてxk以下である確率と考えることができる。従って[数17]のように表すことができる。
【００６９】
【数１７】
2010092825.tif 000082
【００７０】
ここで、jn(x)はn変量x＝{x1,…,xn}に関する確率密度関数であり、一般に正規分布関数と近似できることが知られている。
【００７１】
n＝1の場合、枝e1の遅延がx1＝d(e1)のとき、枝e1がクリティカルエッジである確率P[e1∈Ece](x1)は[数18]で表される。すなわち、点vに入る枝e1がクリティカルエッジとなる。
【００７２】
【数１８】
2010092825.tif 000083
【００７３】
また、ek∈Eceとなるxk＝d(ek)の条件付き確率密度関数φek[ek∈Ece](xk)は[数17]と同様に[数19]で表される。
【００７４】
【数１９】
2010092825.tif 000084
【００７５】
ここで、n変量の正規分布関数jn(x)は[数20]であらわされる。
【００７６】
【数２０】
2010092825.tif 000085
【００７７】
また、(x−μ)T＝(x1-μ1 x2-μ2 … xN-μN)は(x−μ)の転置行列である。ここでσijは、[数21]で定義される行列σijの逆行列(σij＝(σij)-1)である。
【００７８】
【数２１】
2010092825.tif 000086
【００７９】
なお、n＝1の場合、e1∈Eceとなるx1＝d(e1)の条件付き確率密度関数φe1[e1∈Ece](x1)は[数22]で表される。このときj1(x1)は、x1＝d(e1)の確率密度関数である。
【００８０】
【数２２】
2010092825.tif 000087
【００８１】
[数19]の計算には積分が含まれているが、[数23]に示す近似を用いれば簡単に計算することもできる。
【００８２】
【数２３】
2010092825.tif 000088
【００８３】
ここでF(Fは自然数)は積分計算の分割数であり、a,b(a＜b)はそれぞれ近似計算領域の下限,上限である。d(＞0)は積分計算の分割幅であり[数24]で定義する。a→−∞およびb,F→∞のとき近似誤差は0となる。
【００８４】
【数２４】
2010092825.tif 000089
【００８５】
グラフGに含まれるすべての枝ekに対し、クリティカルエッジとなる条件付き確率密度関数φek[ek∈Ece](xk)は、以下に示す[アルゴリズム1]で求めることができる。
【００８６】
[アルゴリズム1]
(1)…アサイクリックグラフG＝{V,E}において、すべての点v(v∈V)およびすべての枝e(e∈E)の終点における遅延の確率密度関数jv(x)およびje(x)を[特許文献1]の手法により計算する。
(2)…グラフ中から1つの点v(v∈V)を選択する。
(3)…選択された点vに入ってくる各枝ekに対し、[数19]を適用し、枝ekがクリティカルエッジとなるときの枝ekの終点における遅延の条件付き確率密度関数φek[ek∈Ece](xk)を計算する。
(4)…すべての点に対し上記(2)〜(3)を適用する。
【００８７】
[数20][数21]よりn変量の確率密度関数jn(x1,…,xn)の計算の複雑度はＯ(n2)である。したがって、φek[ek∈Ece](xk)の計算の複雑度は[数19][数23]よりＯ(n3×F)となる。グラフGに含まれる全枝数すなわち回路規模をN、枝ekの終点に入る枝の数をn(ek)とすると、グラフGに含まれるすべての枝ekに対し、クリティカルエッジとなるxkの条件付き確率密度関数φek[ek∈Ece](xk)を求める計算の複雑度は、
【００８８】
【数２５】
2010092825.tif 000090
【００８９】
である。ただし、回路規模が大きい,すなわち,N≫n(ek)およびN≫Fのとき、φek[ek∈Ece](xk)の計算の複雑度はＯ(N)となるので、十分実用的な計算時間で計算することができる。
【００９０】
クリティカルパス率計算(ST230)
次に、クリティカルパス率計算処理ST230において、グラフ中の点や枝がクリティカルパス上の点や枝となる確率を計算する。なお、クリティカルパス上の点や枝は、設計対象回路におけるクリティカルパス上の素子や配線に対応している。
【００９１】
(クリティカルパス定義)
アサイックリックグラフG＝{V,E}において、ソースに対応する点vsを始点,シンクに対応する点vtを終点とする経路をパスpと呼び、p＝{Ep,Vp}と表す。ここで、Ep＝{ep1,…,epj,…,epm}はパスp上の枝の集合、Vp＝{vp0,…,vpj,…,vpm}はパスp上の点の集合であり、vp0はシンクvtに対応する点,vpmはソースvsに対応する点であり、各点はシンクからソースへの順にソートされているとする。すなわち、枝epjの始点,終点はそれぞれvpj,vp(j-1)に対応する。また、グラフGにおけるすべてのパスの集合をp＝{p1,…,pj,…,pn}とし、各パスpjに対して、pjに含まれる全ての枝eの遅延t(e)の総和をpjのパス遅延と呼び、t(pj)と表す。パス遅延t(pj)が最大のパスをクリティカルパスと呼び、点v,枝eがクリティカルパス上の点,枝であるという条件をそれぞれv∈Vcp,e∈Ecpと表す。
【００９２】
ここで、枝e＝(u,v)がクリティカルパスに含まれる(e∈Ecp)ということは、枝eの始点u,終点vが共にクリティカルパスに含まれ(u,v∈Vcp),かつ,枝eがクリティカルエッジである(e∈Ece)ことを意味する。一方、点vがクリティカルパスに含まれる(v∈Vcp)ということは、点vに入ってくる枝ei＝(u,v)のうち少なくとも1つがクリティカルパスに含まれ,かつ,点vから出て行く枝eo＝(v,w)のうち少なくとも1つがクリティカルパスに含まれることを意味する。
【００９３】
このとき、ある点vにおいて、点vから出る枝の集合をeo＝{eo1,…,eoj,…,eom},点vに入る枝の集合をei＝{ei1,…,eik,…,ein}とする。点vから出る枝eojがクリティカルパス上の枝となる確率P[eoj∈Ecp]の総和
【００９４】
【数２６】
2010092825.tif 000091
【００９５】
および点vに入る各枝eikがクリティカルパス上の枝となる確率P[eik∈Ecp]の総和
【００９６】
【数２７】
2010092825.tif 000092
【００９７】
は、どちらも点vがクリティカルパス上の点となる確率P[v∈Vcp]に等しくなる[数28]。
【００９８】
【数２８】
2010092825.tif 000093
【００９９】
また、点v(v∈V)がクリティカルパス上の点となるときの点vにおける遅延d(v)の条件付き確率密度関数をφv[v∈Vcp](x)とし、点vから出る枝eojがクリティカルパス上の枝となるときの点vにおける遅延の条件付き確率密度関数をφv[eoj∈Ecp](x)とする。点vがクリティカルパス上の点となるときのd(v)＝xの条件付き確率密度関数φv[v∈Vcp](x)は、点vから出る各枝eojがクリティカルパス上の枝となるときの条件付き確率密度φv[eoj∈Ecp](x)の総和
【０１００】
【数２９】
2010092825.tif 000094
【０１０１】
および点vへ入る各枝eikがクリティカルパス上の枝となるときの条件付き確率密度φv[eik∈Ecp](x)の総和
【０１０２】
【数３０】
2010092825.tif 000095
【０１０３】
に等しくなる[数31]。
【０１０４】
【数３１】
2010092825.tif 000096
【０１０５】
(条件付き確率密度分布の継承)
点vにおける遅延d(v)がxであるときに点vがクリティカルパス上の点である確率をPv[v∈Vcp](x)と表し、d(v)＝xであるときに枝eがクリティカルエッジである確率をPv[e∈Ece](x)と表す。今、点vに入る枝eがクリティカルエッジであるか否かは、ソースvsからvに到るパスで決まるのに対して、点vがクリティカルパス上の点であるか否かはソースvsからシンクvtに到る全てのパスによって決まる。したがって、ソースvsに近い点v(すなわち、vsからvに到るパスに含まれる枝の個数の最小値が、vsからvtに到るパスに含まれる枝の個数の最小値に比べて小さいような点)に対しては「d(v)＝xであるときにv∈Vcpであること」および「d(v)＝xであるときにe∈Eceであること」はほぼ独立であると考えることができる。
【０１０６】
そのため、[数15]より、枝eの終点vへの遅延がd(v)＝xであるとき枝eがクリティカルパス上の枝である確率Pv[e∈Ece](x)は、v∈Vcpでありかつe∈Eceである確率であるから、[数32]で表される。
【０１０７】
【数３２】
2010092825.tif 000097
【０１０８】
e∈Ecpあるいはe∈Eceのとき、枝eの終点における遅延d(e)が点vの遅延d(v)となる。それゆえ、e∈Ecpあるいはe∈Eceの条件下では、枝eの終点における遅延d(e)がxであるとき点vがクリティカルパス上の点である確率をPe[v∈Vce](x)とし、枝eの終点における遅延d(e)がxであるとき枝eがクリティカルエッジである確率をPe[e∈Ece](x)とすると、[数33]が成り立つ。
【０１０９】
【数３３】
2010092825.tif 000098
【０１１０】
したがって[数32]は[数34]のようになる。
【０１１１】
【数３４】
2010092825.tif 000099
【０１１２】
ここで、枝eの始点uにおける遅延をx＝d(u),枝eの終点vにおける遅延をz＝d(v),枝eの遅延をy＝t(e)とし、x＝d(u)とy＝t(e)の2変量確率密度関数をju,t(e)(x,y)とすると、z＝x+yであるから、[数3]より、e∈Ecpとなるx,yの条件付き確率密度関数φu,t(e)[e∈Ecp](x,y)は、x,yの2変量確率密度関数ju,t(e)(x,y)と、e∈Ecpとなる確率Pe[e∈Ecp](z)(＝Pe[e∈Ecp](x＋y))との積で表される[数35]。
【０１１３】
【数３５】
2010092825.tif 000100
【０１１４】
ここで、P[e∈Ecp](x,y)は、枝eの始点uの遅延がx＝d(u)、枝eの遅延がy＝t(e)のときに、e∈Ecpとなる確率である。従って、e∈Ecpとなるxの条件付き確率密度関数φu[e∈Ecp](x)は、φu,t(e)[e∈Ecp](x,y)を枝ekの遅延yで積分することにより得られるから、
【０１１５】
【数３６】
2010092825.tif 000101
【０１１６】
となる。
【０１１７】
ここで、[数4]より、
【０１１８】
【数３７】
2010092825.tif 000102
【０１１９】
である。
【０１２０】
ここで、ju,t(e)(x,y),je(x),jv(x)は[特許文献1]の手法により、またφe[e∈Ece](x)は[数19]によりあらかじめ計算可能であるから、点vがクリティカルパス上の点となる点vの条件付き確率密度関数φv[v∈Vcp](x)が既知であれば、点vに入る各枝ekがクリティカルパス上の枝となる枝ekの始点uにおける遅延の条件付き確率密度関数φu[e∈Ecp](x)を得ることができる。
【０１２１】
(各枝のクリティカルパス率計算)
シンクに対応する点vt(＝vp0)はすべてのパスに含まれる点である。したがって、シンクvtがクリティカルパス上の点となるvtの条件付き確率密度関数φvt[vt∈Vcp](x)は、vtの確率密度関数jvt(x)に等しい（[数38]および[数39]）。
【０１２２】
【数３８】
2010092825.tif 000103
【０１２３】
【数３９】
2010092825.tif 000104
【０１２４】
したがって、アサイクリックグラフG＝{V,E}において、グラフ中の任意の点vがクリティカルパス上の点となる点vにおける遅延の条件付き確率密度関数φvt[vt∈Vcp](x)、および、回路中の任意の枝eがクリティカルパス上の枝となる枝eの始点uにおける遅延の条件付き確率密度関数φu[e∈Ecp](x)は、以下に示す[アルゴリズム2]で計算することができる。
【０１２５】
[アルゴリズム2]
(1)…すべての枝eに対し、クリティカルエッジとなる条件付き確率密度関数φe[e∈Ece](x)を[数19]により計算する。
(2)…シンクに対応する点vtに[数39]で示す初期値を設定する。
(3)…アサイクリックグラフにおいて逆トポロジカル順に枝eを選択する。
(4)…選択した枝eがクリティカルパス上の点となる枝eの始点uにおける遅延の条件付き確率密度関数φu[e∈Ecp](x)を[数36]〜[数37]により計算する。
(5)…点uから出る枝eojのすべてに対してφu[eoj∈Ecp](x)が計算済みの場合、[数31]により、点uがクリティカルパス上の点となる点uの遅延の条件付き確率密度関数φu[u∈Vcp](x)を計算する。
(6)…すべての枝および点に対し上記(3)〜(5)の処理を繰り返す。
【０１２６】
設計対象回路に遅延制約としてDが課せられている場合は、パスpがクリティカルパスであり,かつ,パス遅延値がD以上となる確率を求めればよい。したがって、[数39]の代わりに[数40]を初期値として用いることにより求めることができる。ここで、u(x)はステップ関数である。
【０１２７】
【数４０】
2010092825.tif 000105
【０１２８】
枝eがクリティカルパス上の枝となる確率P[e∈Ecp]および点vがクリティカルパス上の点となる確率P[v∈Vcp]は、点vおよび枝eがクリティカルパス上となる条件付き確率密度関数φv[v∈Vcp](x)およびφu[e∈Ecp](x)を積分することにより得ることができる[数41]。
【０１２９】
【数４１】
2010092825.tif 000106
【０１３０】
回路規模をN,積分計算の分割数をFとすると、グラフGに含まれるすべての点についてその点がクリティカルパス上の点となる確率P[v∈Vcp]およびすべての枝についてその枝がクリティカルパス上の枝となる確率P[e∈Ecp]を求める計算の複雑度は、N≫FのときＯ(N)となる。したがって、本方法の計算処理時間は十分実用的であると言える。
【０１３１】
回路修正候補決定(ST240)
次に回路修正候補決定処理ST240では、遅延改善のための回路修正候補情報500を出力する。回路修正候補情報500は、クリティカルパス率の高い枝でもよいし、回路修正による面積あるいは消費電力増などのコストに対する遅延改善率等の感度を表す係数をクリティカルパス率に乗じてもよい。抽出する改善候補の数は、あらかじめ指定された数としてもよいし、クリティカルパス率がある確率を超えるものだけを抽出してもよい。遅延制約Dが与えられている場合は[数40]の値が正となる枝をすべて抽出すればよい。
【０１３２】
図12は、回路修正候補決定処理ST240の結果抽出される回路修正候補情報500の例である。図12では、Instance2,Instance3,配線eが回路修正候補であることを示している。
【０１３３】
図13は回路修正候補情報500の別の形態の例である。図13では、図12に示す修正候補に対する具体的修正内容を示している。図13では、修正候補であるInstance2をCell3に置き換え,Instance3をCell4に置き換え、また、Cell5をInstance4として挿入し、ネットeをInstance2の出力端子Yから切断してInstance4の出力端子Yへ接続し、さらにIncetance2の出力端子YとInstance4の入力端子Aとをネットgで接続することを意味している。
【０１３４】
回路改善(ST300)
最後に図1の回路改善処理ST300では、回路修正候補情報500に基づいて回路情報100の修正を行う。
【０１３５】
たとえば、図12の回路修正候補情報500を用いる場合、入力端子Bを通るパスの遅延削減となる様、Instance2およびInstance3をより高速なセルに置換すればよい。また、他の配線を迂回させるなどして配線eをより優先的に引きなおすことにより配線eの遅延を削減することができる。
【０１３６】
図16は、回路情報100がレイアウト情報(図2の配置済み回路情報100b,配線済み回路情報100c)である場合の設計対象回路の回路情報100の例である。
【０１３７】
図16(a)は、回路改善処理ST300による修正が行われる前の回路情報100の例であり、図3の回路情報100のレイアウト情報である。Instance1,Instance2,Instance3にそれぞれCell1,Cell1,Cell2が配置され、b,d,eのネットがそれぞれ配線されている。
【０１３８】
図16(b)は、図16(a)の回路情報100に対して回路改善処理ST300による修正が図12の回路修正候補情報500に基づいて行われた後の回路情報100の例である。回路修正候補情報500としてネットeが抽出された場合の修正例を表している。ネットbの配線を迂回させることにより、クリティカルパス率の高いネットeを優先的に配線して遅延を削減することで、同じ面積で遅延改善効果を得ることができる。
【０１３９】
また、図13の回路修正候補情報500を用いる場合、Instance2,Instance3をそれぞれCell1,Cell2から能力のより高いCell3,Cell4へ置き換え、ネットeへバッファ(Cell5)を挿入することにより遅延を削減することができる。
【０１４０】
図15は、図3の回路情報100に対して回路改善処理ST300による修正が図13の回路修正候補情報500に基づいて行われた後の回路情報100の例である。図15では、新たにInstance4としてCell5が挿入され、Instance4の入力端子AがInstance2の出力端子Yと接続されている。また、Instance2,Instance3がそれぞれCell1,Cell2からCell3,Cell4に置き換えられ、Instance3の入力端子Bの接続先がInstance2からInstance4に修正されている。
【０１４１】
図16(c)は、図16(a)の回路情報100に対して回路改善処理ST300による修正が図13の回路修正候補情報500に基づいて行われた後の回路情報100の例を表しており、図15の回路情報100に対応したレイアウトである。クリティカルパス率の高いInstance2,Instance3のセルをより遅延の少ないセルに置き換え、また、ネットbを迂回させることにより、クリティカルパス率の高いネットeを優先的に配線し、さらにネットeに対しCell5のバッファ挿入を行うことで、遅延改善効果を得ることができる。
【０１４２】
以上、本実施形態によれば、遅延分布および遅延相関を精度よく考慮して、設計対象回路の遅延を削減することが可能である。
【０１４３】
上記実施形態にはさまざまな変形例がある。それらのいくつかを以下に説明する。
【０１４４】
図17は、図1に示す実施形態による処理から回路改善処理ST300を省略した変形例を示す。回路改善処理ST300を省略しても、最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。回路改善を、必要に応じて市販のレイアウトツールや設計者自身の回路修正作業と組み合わせて行うことにより、より柔軟に設計フローを選択することが可能になる。
【０１４５】
図18は、図1に示す実施形態による処理から遅延分布計算ST100を省略した変形例を示す。遅延分布計算ST100を省略しても、最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。遅延分布計算を、必要に応じて市販の遅延解析ツールや設計者自身の計算と組み合わせて行うことにより、より柔軟に設計フローを選択することが可能になる。
【０１４６】
図19は、図1に示す実施形態による処理から回路改善処理ST300および遅延分布計算ST100を省略した変形例を示す。回路改善処理ST300および遅延分布計算ST100を省略しても、最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。遅延分布計算および回路改善を、必要に応じて市販の遅延解析ツールまたはレイアウトツールや設計者自身の計算または回路修正作業と組み合わせて行うことにより、より柔軟に設計フローを選択することが可能になる。
【０１４７】
図20は、図1に示す実施形態による処理から遅延相関情報400を省略した変形例を示す。遅延相関情報400を省略しても、回路によっては精度は低下するものの最大遅延削減または遅延制約違反解消のために修正すべき回路の箇所の抽出が可能であるという効果がある。例えば計算時間が増大する等の理由で遅延相間情報の出力が困難な場合でも、本発明の効果を得ることが可能である。
【０１４８】
図21は、図1に示す実施形態による処理において、回路修正候補抽出処理ST200と、回路改善処理ST300とを、同じ計算機を用いて同じプログラム内で連続して処理ST400として実行する変形例を示す。回路修正候補情報500は、計算機のメモリ上に内部データとして保持していればよく、データファイルとして出力する必要はない。内部データとして保持する場合、特に、回路修正候補決定処理ST240と回路改善処理ST300とが、同じ計算機を用いて同じプログラム内で連続実行される場合は、ファイルの読み書きにかかる時間を短縮することができる。一方、異なるプログラムを用いる場合には、回路修正候補情報500をデータファイルとして出力したほうが好ましい。
【０１４９】
図22は、図21に示す実施形態による処理から遅延分布計算ST100を省略した変形例を示す。図22の変形例は、図21の変形例の持つ効果に加えて、図18の変形例の持つ効果を有する。
【産業上の利用可能性】
【０１５０】
本発明は、半導体集積回路設計において、計算機を用いてプロセス情報等に基づいて回路の特性をシミュレーションし性能改善するのに有用である。
【符号の説明】
【０１５１】
100…回路情報
200…テクノロジ情報
300…遅延分布情報
400…遅延相関情報
500…回路修正候補情報
ST100…遅延分布計算処理
ST200…回路修正候補抽出処理
ST300…回路改善処理
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2010092825.tif 000107
【図２】
2010092825.tif 000108
【図３】
2010092825.tif 000109
【図４】
2010092825.tif 000110
【図５】
2010092825.tif 000111
【図６】
2010092825.tif 000112
【図７】
2010092825.tif 000113
【図８】
2010092825.tif 000114
【図９】
2010092825.tif 000115
【図１０】
2010092825.tif 000116
【図１１】
2010092825.tif 000117
【図１２】
2010092825.tif 000118
【図１３】
2010092825.tif 000119
【図１４】
2010092825.tif 000120
【図１５】
2010092825.tif 000121
【図１６】
2010092825.tif 000122
【図１７】
2010092825.tif 000123
【図１８】
2010092825.tif 000124
【図１９】
2010092825.tif 000125
【図２０】
2010092825.tif 000126
【図２１】
2010092825.tif 000127
【図２２】
2010092825.tif 000128
【国際調査報告】
2010092825.tif 000129
2010092825.tif 000130
2010092825.tif 000131
2010092825.tif 000132