回路のジッタを計算する方法、論理装置及びシステム並びに回路のクロックツリーを合成する方法、論理装置及びシステム
【課題】チップレベルの設計に関する問題に対処し、クロストークカップリングが存在する場合でも正確な経路遅延を計算すること。
【解決手段】一実施例でのクロックツリーにてジッタを計算する方法は、クロックツリーを複数のステージに分割し、クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出する。モデルは回路のジッタのソース各々の表現を含む。本方法は、クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップを含む。一実施例では、ジッタを効率的に計算し且つクロックスキューゼロを達成するため、モデルは回路の対称的なクロックツリーを合成し、そのツリーでは区六浮くツリーのルートからクロックツリーのシンクに至る全てのパス中の関連するステージは、近似的に電気的に互いに等価な性質を示す。
【解決手段】一実施例でのクロックツリーにてジッタを計算する方法は、クロックツリーを複数のステージに分割し、クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出する。モデルは回路のジッタのソース各々の表現を含む。本方法は、クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップを含む。一実施例では、ジッタを効率的に計算し且つクロックスキューゼロを達成するため、モデルは回路の対称的なクロックツリーを合成し、そのツリーでは区六浮くツリーのルートからクロックツリーのシンクに至る全てのパス中の関連するステージは、近似的に電気的に互いに等価な性質を示す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に回路設計に関連し、特にディジタル回路のクロックツリーにおけるジッタを評価すること並びにスキュー及びジッタ認識クロックツリーを合成することに関連する。
【背景技術】
【０００２】
集積回路のスケールが増加するにつれて、プロセス及び環境（例えば、電圧、温度及びクロストーク等）の影響はそのような回路全体を通じた遅延変動を増やす傾向にある。そのような変動は回路のクロックジッタ（又はフリップフロップのクロック到着時間の不確定性）を増やす。ジッタの増加は、一定のクロックサイクルに関する回路のクリティカルパスでの最大許容遅延を減らし、より強引な最適化及びより多くのターンアラウンドタイム(turn around time)を更なる重要事項にする。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
図１はクロストークを例示する図である。ディープサブミクロン回路設計では、ワイヤはより高く且つより狭くなっている一方、それらを互いに分離する距離は減っているので、隣接する相互接続間のカップリングキャパシタンスはかなり重要な問題になっている。その結果、物理的に隣接するネット（又は相互接続部）間のクロストークはかなりの問題となっている。影響を受けるネットはビクティム(v: victim)である。犠牲側又はビクティムｖに影響するノイズを引き起こす隣接するスイッチングネットは、攻撃側又はアグレッサ(a: aggressor)である。アグレッサａに関するものは適切ならばそのようなネットの１以上を含む。図１に示されるように、アグレッサａがビクティムｖと反対向きにスイッチする場合に、クロストークはビクティムｖでの到着時間を増やすかもしれない。アグレッサａがビクティムｖと同じ方向にスイッチする場合には、クロストークはビクティムｖでの到着時間を減らすかもしれない。ｖ及びａ間の分布結合容量はCciとして示される。クロストークは論理ハザード及び回路不具合にもなるおそれがある。例えば遅延変動がクロックサイクルより遅いクリティカルパスを変える程度に（及びタイミングバイオレーションを引き起こす程度に）十分大きかった場合、又はアグレッサａとの容量カップリングに起因してビクティムｖで発生した大きなスパイクが、ターゲットフリップフロップ（ＦＦ）で不適切な値をクロックエッジでラッチするのに十分近接していた場合に、回路は不具合をおこす。クロストークに起因する遅延変化の正確な計算は回路設計で重要になりつつある。
【０００４】
本発明の課題は、チップレベルの設計に関するこの問題に対処し、クロストークカップリングが存在する場合に正確な経路遅延を計算することである。
【課題を解決するための手段】
【０００５】
本発明では、クロックツリーにてジッタを計算する方法が使用される。本方法は、クロックツリーを複数のステージに分割するステップと、クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップとを有する。
【発明を実施するための最良の形態】
【０００６】
本発明並びに本発明の特徴及び利点についての理解を更に完全にするため、添付図面に関連する以下の説明が参照される。
【０００７】
以下、本発明の実施例によるシステム、方法及び論理装置が説明される。この場合において、論理装置なる語は、ソフトウエアで構成される論理プログラムや、ハードウエアで構成される論理回路を含む概念である。
【０００８】
従来の設計法及びスタティックタイミング分析(STA: static timing analysis)ツールは、クロックツリーの各バッファについて悲観的(pessimistic)遅延マージンを確保することでクロックジッタを取り扱う。ワーストケース分析のように、これらはクロックツリーのパスにバッファのこれらのマージンを積み上げる。そしてクロック経路がソースＦＦであるかターゲットＦＦであるかに依存して、マージン合計は公称パス遅延の分だけ加算される或いは減算される。そのようなワーストケース分析は過剰に悲観的である；なぜなら、１つのクロック経路でのバッファ全てについて最小遅延状態（即ち、最低温度、最大供給電圧、最小チャネル長及び最低閾値）を及び他のクロック経路でのバッファについて最大遅延状態（即ち、最大温度、最小供給電圧、最大チャネル長及び最大閾値）を仮定しているからである。そのような極めて不適切なシナリオを利用することは、不必要に過剰な回路設計となってしまう。不具合のあるチップの大半はそのツールで予測されるものより高い（３０％よりも高い）パフォーマンスを示す。
【０００９】
統計的スタティックタイミング分析(SSTA)はより現実的なタイミング検査の代替的なパラダイムである。概してSSTAに関して２種類の手法が提案されている：分析的なものとサンプリングベースのものである。分析的手法は、（例えば、ガウス型確率密度関数の形式で）統計的ゲート遅延モデル及び統計的プロセス変動モデルを入力として採用し、回路又は経路遅延の確率密度関数（PDF）を構築する。包含される数学的複雑さ（例えば、PDFの最大及び最小を導出すること）に起因して、これらは依然として研究テーマである。サンプリングベース又はモンテカルロ（MC）ベースの手法は入力パラメータの値を生成し、そのパラメータは或る分布（例えば、一様であったり、又はガウス型）を満たすことを仮定する。回路遅延はこれらの値の下で計算される。遅延分布曲線に関して充分な遅延値が得られるまで、手順は何百回も何千回も反復される。MCベースの手法は高精度であるが、演算負担が大きい。これらを実際の工業的設計に直接的に適用することは困難かもしれない。
【００１０】
特定の実施例でのクロックツリージッタ分析の方法論は、分析的手法及びモンテカルロ法を結合する。特定の実施例では、ツリー合成法がゼロスキューツリー(zero-skew tree)を生成する。このツリーでのジッタ分析は、従来のMCベースの手法よりも効率的であり且つ従来のSTAより悲観的ではない。特定の実施例での方法論は、プロセス、温度、電圧及びクロストークの変動の下で、イーサーネットチップの分析及びクロックツリー合成に適用可能である。
【００１１】
所与のクロックツリー及びソース，ターゲットFFの下で、特定の実施例はクロックジッタを計算するために、統計的且つ（最悪事態の方法論と比較して）悲観の度合いの少ない手法を使用する。この手法では、クロックツリーの各バッファ段の遅延変動（又はジッタ）は、モンテカルロシミュレーションを用いるスパイス（SPICE）で正確に計算される。そしてステージのジッタは統計的に結合され、（従来のSTAツールでなされるように）単にジッタを加算するのではなく、完全なクロック経路（又は一対のパス）についてジッタを生み出す。特定の実施例はクロックツリーを合成し、そのクロックツリーで上記のステージジッタ計算及びツリージッタ分析が効率的に実行される。
【００１２】
特定の実施例では、クロックジッタ分析アルゴリズムは、データパスのソース及びターゲットFF間のジッタを分析する。特定の実施例では、ポストプロセシング法が、クロックツリーに関する統計的ジッタ計算を利用して、従来のSTAツールにより報告されたデザインのクリティカルパスを再分析する。
【００１３】
所与の固定されたサイクルタイムの下で、クロックスキュー及びジッタは共に設計回路のクリティカルパスの最大許容遅延を減らす。スキューは所与の２つのフリップフロップFFi及びFFj間に関するクロック到着時間ti及びtjの確定的な差分(deterministic difference)である。スキューは、如何なるプロセス、電圧又は温度変化もなく且つ全てのノイズ源がゼロである場合のクロック分散ネットワークでの不整合（不完全な又は計画的な）を追跡可能である。クロック分布ネットワークの正確なモデルを構築すること、そして一定の温度及びVddでクロックツリー上のクロックソースから全てのFFまでSPICE又はSTAを実行すること、及びクロックソースで５０％のVddから各FFで５０％のVddに至るまでの公称クロック遅延ｔを測定することで、スキューは計算されてよい。従ってクロックスキューを計算することは、クロック遅延及び到着時間を計算し、差分を計算することと等価であるかもしれない。
【００１４】
ジッタは対象のパラメータの不確定性又は時間変動である。クロックに関し、対象のパラメータはフリップフロップのクロック到着時間である。クロックサイクルがτである場合に、どの２つの連続するサイクルの上昇（及び下降）クロックエッジも理想的にはFFでτ時間単位離れている。しかしながら実際にはこのタイムギャップは以下の理由で変わることが間々ある。
【００１５】
１．時間の関数のようなゲートでの供給ノイズ又はVdd-Vss変動。供給ノイズは異なるクロックサイクルでスイッチングする異なるゲート群に起因する。これはVdd及びVssラインでの時間変化する電流をもたらし、従ってIR及びLdi/dtの低下を招く。ゲートの遅延はVddに依存するので、クロックバッファの供給電圧の如何なる変化もそのFFでのクロック到着時間を変える。
【００１６】
２．ゲートでの及びダイにわたる温度変化。パワー及び温度は特にリーケージドミナント法で(leakage-dominant technologies)互いに強く関連するので温度変化が生じる。高速スイッチングの障害は多くの電力を劇的に散逸させ、より高い局所的な温度を招く。そしてこれは漏れ電力散逸を増やし、全体の電力を更に増やす。これはそのチップに関する大きな温度勾配を導入する。ゲートの温度変化は異なるサイクルでの異なるスイッチング動作にも起因する。高温でのゲート動作はキャリア移動度の減少に起因してより多くの遅延を招く。
【００１７】
３．クロストークノイズ。図１に示されるように、ｖに物理的に近く且つスイッチングしているアグレッサａが有ったならば、クロックワイヤの遅延は変化するかもしれない。アグレッサのスイッチング挙動は或るサイクルと次のサイクルで異なるかもしれないので、それはビクティムでジッタを招くおそれがある。設計で最も重要な信号の１つはクロックである。そのようなクロストークの影響を減らすためにクロックの両側でVdd/Vssシールディング(shielding)が行われるのが一般的である。しかしながらワイヤバスがクロックラインを超えて進む場合には、そのシールティングは上位及び下位レイヤからのクロストークを防げない。
【００１８】
４．PLLジッタ。PLLから生成されたクロックは或る固有のジッタを有する。
【００１９】
５．ダイに関するプロセス変動。プロセス変動の具体例は、MOSFETのチャネル領域におけるランダムなドーパント揺らぎのような本質的な変動と、チャネル長や酸化物厚みの変動のような非本質的な変動とを含む。また、化学機械平坦化（CMP）プロセスでは、相互接続の幅、厚さ、間隔及び高さが所望値からかなり変化するかもしれない。これらの変動はゲート又はワイヤ遅延を所望値から逸脱させる。正確な変動の大きさ（従って製造後のワイヤ及びゲート遅延の正確な値）を予測することは困難である。この現象はスキューでは捕らえられない。チップ製造後のトランジスタ又は相互接続の寸法に顕著な時間依存する変化がない場合でさえ、それをジッタとしてモデル化することが更に有利である。
【００２０】
図２に示されるようにフリップフロップFFsから出発し、組み合わせ論理を通じてFFeに至るデータパスを仮定する。as及びaeをそれぞれFFs及びFFeでのクロック到着時間とする。これらの到着時間は公称（名目）遅延及びジッタを含む。τをPLLクロックサイクル時間とする。特定の実施例ではSTAの２つの基本機能は、ロングパスを検出すること及びレース(race)を検出することである。
【００２１】
１．ロングパスの検出。この分析では所与の開始及び終端のFFs及びFFe各々の下で、dmaxが組み合わせ論理（FFsを介する遅延を含む）の最大パス遅延であったならば、適切に動作する回路に関し、以下の不等式が満たされるべきである。
【００２２】
as+dmax≦ae+τ−tset-up （１）
STAツールはτavail(s,e)、２つのFFs間の最小利用可能サイクルを見出す：
τavail(s,e)=τ+ae-as （２）
簡明化のため、数式（２）でFFeに関する設定時間(set-up)はゼロであるとする。そしてSTAはdmaxが高々τavail(s,e)であるか否かを判定する。この分析では受信フリップフロップ捕捉クロックエッジは、送信フリップフロップクロックエッジ後の１サイクルである。従ってPLL（又は他のクロック源）サイクルジッタはこの分析に包含されるべきである。
【００２３】
２．レース検出。この分析ではSTAツールはFFs及びFFe間での同一クロックエッジの最大クロック到着時間差を見出す。dmin（フリップフロップ間の最小論理遅延）が受信フリップフロップのホールド時間に合わない程度に短い（クロック到着時間差より短い）か否かを判定する。言い換えれば適切な動作については次式が成立する：
as+dmin≧ae+thold （３）
プライムタイム(Prime Time)のような従来のSTAツールは、クロックツリー中のバッファ各々について悲観的な遅延を確保することでクロックジッタを取り扱う。このマージンは技法、プロセス、その設計でのスイッチング動作、Vdd、レイアウト等に依存する。例えばバッファの公称遅延を１００ｐｓとし、変動を収容するためのマージンが１５％であったとする。この場合バッファの最小遅延は８５ｐｓになり、最大遅延は１１５ｐｓになる。ロングパス分析の間にSTAツールは、クロックソースclkからFFeに至る経路上のバッファについてこれらのマージンを公称遅延から減算し、clkからFFsに至る経路上のバッファにこれらのマージンを加算する。図２はこれらの遅延を示す。２つのクロック経路でスキューがゼロであるように設計されていたならば全体的なジッタマージンは６０ｐｓになることが分かる。そのような最悪状況分析は過剰に悲観的である。なぜならclkからFFsへ至るパスの各バッファについて最大遅延状態（例えば、最大温度、最小供給電圧、最大チャネル長及び最大しきい電圧）を仮定し、clkからFFeに至るパスのバッファについて最小遅延状態（例えば、最小温度、最大供給電圧、最小チャネル長及び最小しきい電圧）を仮定しているからである。
【００２４】
特定の実施例は過剰に悲観的な最悪状況分析を統計的分析で置換する。また、特定の実施例は悲観的なマージンを用いる代わりにSPICE及びモンテカルロ分析を用いて、ツリーステージのジッタを計算する。
【００２５】
図３はクロックツリーステージジッタのシミュレーションモデル１０を例示する。特定の実施例では反転バッファ１２はワイヤを通じてインバータ１４を駆動する。
【００２６】
１．供給ノイズＶ：独立している供給電源を設計回路の各バッファに供給し、ノイズモデルに従ってそれらがランダムに変化できるようにすることで、供給ノイズはモデル化される。変動量はユーザ入力パラメータsupply_toleranceで制御される。
【００２７】
２．温度変化Ｔ：温度上昇はCMOS回路の動作を低速化し、配線抵抗を増やす。回路全体について前提とする温度を指定し、クロックバッファ及び相互接続各々でランダムなローカルな温度変化を適用することで、トランジスタの温度変化がモデル化される。適用する変動はユーザ入力パラメータmax_deltempで与えられる。
【００２８】
３．クロストークノイズＸ：図３のワイヤモデルに外部ノイズソースを取り付け、何らかの確率分布に基づいてこれらのソースでランダム入力を適用することで、クロストークノイズはモデル化される。この例に関連するクロストーク因子はワイヤが具体化される毎に規定されるべきである。クロストーク因子はデザイン各々に固有の特性であり、従ってパラメータxtfactorを用いてユーザにより与えられる。
【００２９】
４．PLLジッタ：特定の実施例は３σPLLの最大PLLジッタを仮定する。
【００３０】
５．プロセス変動Ｙ：図３に示されるように、トランジスタのプロセス変動はチャネル長（PMOS及びNMOSトランジスタそれぞれについてlp及びln）及び閾値（delvtn及びdelvtp）だけを用いてモデル化されてよい。酸化膜厚及びドーパント濃度のような他の変動は、しきい電圧を変える全体的な影響を及ぼし、モデル１０に含まれてよい。閾値及びチャネル長の変動はバッファ副回路モデルの各場合に伝達される。配線のプロセス変動は、ワイヤモデルの配線容量及び抵抗（pfc及びpfr）にランダムなプロセス因子を適用することでモデル化される。プロセス変動量は、使用されるプロセスの特性であり、従ってユーザによって変更可能ではない。
【００３１】
実際のチップでは、互いに接近して位置する要素の供給電圧（更には温度）が相関するおそれがある。例えば２つのバッファが物理的に互いに隣接し、同じ電源供給ラインに接続されていた場合に、それらのVdd及び温度変化はほとんど同じである。モデル１０ではそのような関連性を組み入れることができる。例えば１つ手法はVdd/Vss分布アーキテクチャ及びレイアウトに基づいてチップを抵抗Riに分割することである。各領域Riは平均電圧値Vddiを有し、平均電圧値はパワーアーキテクチャ及びその領域でのスイッチング動作から計算される。各シミュレーションでの領域中心についてΔVddiを計算するためにランダム変数が使用される。距離ベースの相関関数ｆを用いてその領域の各バッファの電圧を計算する(f(Vddi+ΔVddi,l))。ここでｌはRiの中心からのバッファの距離である。特定の実施例はワーストケースパラダイムを使用せず、より現実的なものになる。ユーザはそのようなモデルを自由に用意でき、モデルはその手法に組み入れられる。
【００３２】
PVTX変動を組み入れるこの統合された統計的モデルの下で、特定の実施例はSPICEと共にモンテカルロシミュレーション（MCS）を利用し、遅延に関する平均時間ｔ及び標準偏差σを生成する。MCSがチップレベルの設計でのクロックツリー全体について実行されるならば、そのモデルはメモリに適合しないかもしれないし又はMCSは終了するまでにかなりの長時間を要するかもしれない。特定の実施例は、ツリーの小さな部分又はステージについてMCSが実行される手法を使用する。図３に示されるように、ツリーステージ（又はセクション）の或る自然な定義は、別のバッファを駆動するツリー上のクロックバッファ又はワイヤを介したFFである。図３に示されてはいないが、次のレベルのバッファ又はFFに沿うワイヤ上の如何なる分岐点もそのステージに含まれてよい。かくてクロックツリーはステージ（複数）に分割され、MCSはSPICEを用いて各ステージで実行される。Δvtni, Δvtpi,lpi,lni,Vddi,Ti(i=1,2),T,pfc,pfrの各パラメータ及びクロストーク電圧源自身（図３）は各シミュレーションでガウシアン分布関数からランダムに選択されてよい。遅延は駆動バッファ１２の入力から駆動バッファ１３の入力で計算される。シミュレーションは要求される制度に依存して約１００−１０００回反復されてよい。これらのシミュレーションから、SPICEは各ステージの標準偏差σ及び平均時間ｔを自動的に計算する。或るステージのジッタは３σのように決定される。
【００３３】
クロックツリーの全てのステージについて平均遅延及びジッタ値を計算することで、クロックツリーの或るパス又はパスのペアについてジッタ値が計算されてもよい。そのために、図４に示されるクロックツリーの例が考察される。３つのデータパスがある：FF1名乃至FF2、FF1乃至FF3及びFF4乃至FF5である。各クロックインバータステージにはその公称遅延ti及び標準偏差σiがラベル付けされている。各σiは４つのソース全てを考慮する：プロセス（P）、供給電圧（V）、温度（T）及びクロストーク（X）である。別のジッタ要素σiVXは、供給電圧及びクロストークだけの変動に起因する遅延の標準偏差である。PLLサイクル時間をτとし、そのジッタを３σPLLとする。特定の実施例は、各ステージについて、遅延が他の如何なるステージとも非相関（又は独立）であること及び遅延が連続するサイクルの間にそれ自身とも非相関であることを仮定する。この仮定は、図５に示されるパラメータ変動と共に、２つの連続するステージ遅延の標準偏差σ1及びσ2だけでなく、それら２つのステージで構成される連鎖遅延のσをも計算することによって確認される。特定の実施例ではσ1=0.73ps/mm,σ2=0.7ps/mm及びσ=1.17ps/mmである。従ってσ12=√(σ12＋σ22)=1.01である。σに対するσ12の誤差割合は１４％であるが、絶対的なσ値（例えば、0.16ps/mm）での差分は平均遅延（83.38ps/mm）の0.19％しかない。PVTX変動が増えると、このエラーは更に悪化し、その仮定を確からしくする。或る経路を構成するステージの標準偏差は次のように結合される。S1乃至Snが経路（パス）上のステージであり、それぞれ標準偏差σ1乃至σnを有していたとすると、その経路のジッタは次式で与えられる：
【００３４】
【数１】
従来のSTAは
【００３５】
【数２】
のように経路ジッタを計算したであろう。これは
【００３６】
【数３】
よりもかなり大きい。例えば、クロック経路が１０個の同じステージを有し、その各々でσ=10psであったと仮定する。従来のSTAはその経路ジッタとして300psを算出するが、特定の実施例での統計的手法は３×√(10×100)=94.87psのようにそれを算出する。
【００３７】
特定の実施例は例えばロングパス及びレース分析のようなタイミング分析に統計的ジッタ手法を適用する。ロングパス分析τavail(s,e)に関し、図４のデータパス(FFs,FFe)各々に対応するロングパス分析に利用可能な最小サイクル時間が計算されてもよい。τavail(s,e)は(FFs,FFe)経路の組み合わせ論理の最大遅延の上限である。図６はその計算の様子を示す。所与の開始及び終了フロップについて、τavail(s,e)は数式２を用いて算出され、即ちその計算は、開始フリップフロップに対して公称(平均)クロックツリー遅延を減算し、終了フリップフロップのクロックツリー遅延を公称クロックサイクル時間τに加算し、その後に経路に含まれる要素全ての二乗和ジッタの平方根を減算することでなされる。利用可能なサイクルタイムの最小値を計算するためにジッタは減算されてもよい。平方根記号の前にある因子３はジッタの分析に３σを利用することを意味する。スタート及びエンドのFF間のクロック経路に共通のバッファ（例えば、スタートフロップFF1及びエンドフロップFF2に関するバッファ１２，１４）があった場合には、それらの平均遅延の合計(t1+t2)が双方の経路に現れ、相殺することに留意を要する。しかしながらバッファ１２，１４のジッタへの寄与はそれぞれ3×(2σ1vx2)及び3×(2σ2vx2)である。共有バッファのジッタ寄与はゼロではない。これは、ロングパス分析では、各共有バッファ（シェアドバッファ）が或るサイクルでasに及び次のクロックサイクルでaeに遅延をもたらすことに起因する。これら２つの遅延は時間と共に変化するパラメータに起因して変化してもよい。共有バッファに関し、特定の実施例はV,Xに起因する変動のみを包含してもよい。なぜなら所与のバッファに関し、何らのプロセス変動もなく且つ或るサイクルと次のサイクルで温度は変化すべきでないからである。更に共通バッファは２回登場する：１つはスタートフロップに関してであり、もう１つはエンドフロップに関してである。従ってそれらの二乗ジッタ要素には２が乗算される。PLLジッタ３σPLLも包含されてよい。逆に、プライムタイムのようなSTAツールは開始フリップフロップFF1及び終了フリップフロップFF2に関してτ−3(2σPLL+2σ1+2σ2+σ3+σ4)のようにτavailを計算する。
【００３８】
レース分析に関し、同一エッジクロックにおける終了フリップフロップ及び開始フリップフロップ間の到着時間の最大差分が、図４の各経路について計算される。図７はその計算を示す。それらは、開始フリップフロップに対する非共有クロックツリーステージの公称クロック遅延を、終了フリップフロップに対する非共有クロックツリーステージのクロック遅延から減算し、２つの経路で全ての非共有クロックツリーステージのジッタの二乗和平方根を加算することで計算される。レース分析では、共有バッファのジッタ寄与はゼロである。なぜなら唯１つのクロックサイクルしか分析に含まれていないからである。所与のクロックツリーＱの下で、上記の手法は、Ｑの全てのステージの確認を必要とし、スパイスと共にモンテカルロシミュレーションを行うことで各ステージについてのジッタ遅延値及び平均値を計算する。非常に高精度であるが、この手法はしばしば演算負担が重くなる傾向がある。典型的な設計では、何十万ものFF及びバッファがクロックツリー上にある。バッファの各々が１つのステージに対応する。演算負担の観点からは、数千ステージについてMCS計算を実行することは実現不可能かもしれない。特定の実施例では或るツリー合成法がこの問題を解決する。
【００３９】
図８はクロックツリー合成及び分析の方法例を示す。本方法はジッタ及びスキューを意識する。本方法は１以上のチップ仕様（例えば、チップ寸法等）、FF配置及び１以上の変動モデルを利用する。図８に示される方は特定の順序で生じるように特定のステップが示され且つ説明されているが、図８に示される方法の中で適切などのステップも適切な如何なる順序で行われてもよい。１以上のコンピュータシステムは図８に示される方法の１以上のステップの実行を促進してもよい。概して従前の手法を用いるクロックツリーQのジッタ分析は演算負担が大きい。しかしながらQが完全に対称的であったならば、その分析はより効率的であるかもしれない。そのようなツリーでは、クロックソースからFFへのどの２つの経路も、バッファサイズ及びそれらの間の配線長の観点からは、実質的に同じである。それは、平均値及びシグマ遅延に関し、唯１つのツリー経路でバッファステージを特徴付けるのに充分である。特定の実施例は、PVTXパラメータの変動はチップ内の位置の関数ではないことを仮定する。これは特定の変動モデルに関して成立する。或る変動モデルの場合にこの仮定が成立しなかったならば、そのクロックツリーの中で１パスより多くの経路でバッファのステージジッタ分析が実行される。かくてツリー全体について何千ものステージでMCSを実行する代わりに、問題は近似的に高々２０乃至３０ステージ（パスの中の最大ステージ数）のMCSにまで減る。完全に対称的なツリーの別の利点はスキューがゼロになることである。従って特定の実施例は、対称的なツリーが生成される合成法を採用する。特定の実施例は次のように対称的クロックツリーを合成するためのアルゴリズムを使用する。
【００４０】
チップ上で（空間的に）非一様な分布のフリップフロップは、クロック分布の非対称性を引き起こすかもしれない。特定の実施例は、チップ中心のクロック源で駆動される対称的なグローバルHツリーを生成し、続いてHツリーのシンクからFFへの等価的な長い接続を行うことでこの非一様性に対処する。特定の実施例は高々１つのFFを各シンクに割り当てる。これはHツリーのレベル数λを決定する。例えば図９はクロックソースからFFまでのパスのステージ例を示す。より具体的には図９は１６個のシンクを備えた２レベルツリーを示す。設計中のFF数がｎであったとすると、４λ≧ｎである。４λはHツリーのシンク数である。FF−シンク割当の目的は何らかのシンクｓとｓに割り当てられるFFとの間の最大距離を最小化することである。最大距離をDとする。最終的に各シンクは長さDの相互接続によって、割り当てられたFFに接続される。或るFFのシンクに至る距離がDより短かったならば、特定の実施例は相互接続長Dを形成するために迂回させる又は曲げる。FFの割り当てられていないシンクがあったならば、長さDのダミーワイヤがそこに接続され、ダミー容量cfが相互接続の終端に取り付けられ、ここでcfはFFのクロックピンの入力容量である。簡明化のため、特定の実施例はcfが各FFに関して同じであることを仮定する。シンク及び割り当てられたFF間の最大距離を最小化することで、シンクからFFまでの相互接続長の合計も最小化される。
【００４１】
特定の実施例では、高々１つのFFを各シンクに割り当てることで及び割り当てられたFFに至る各シンクからのワイヤ長を等しくすることで、全てのHツリーシンクは同様なダウンストリームトポロジ（キャパシタンスcfに接続された長さDのワイヤ）を見ることになる。これはツリー上で同じセクションを生成可能にする、即ち所与のどの２つのHツリーシンクsi,sjでも、クロックソースからsi,sjに至るパス（バッファ及びリピータの数、位置及びサイズを含む）は等しい。
【００４２】
特定の実施例ではFF及びHツリーシンクの位置は事前に既知である。FFの位置は配置データから読み取られる。Hツリーシンクの位置はチップ寸法（高さ及び幅）及びツリーのレベル数λから容易に計算可能である。トップレベルのHはチップの中心に設けられ、その幅及び高さは、それぞれチップ高さ及び幅の或る分数αである。低レベルでのHは、親レベルの幅及び高さのα倍に等しい幅及び高さを有する。典型的にはα=0.5である。
【００４３】
特定の実施例ではHツリーシンクへのFFの正確な割当は、２分グラフ(bipartite graph)Gで完全な(perfect)ボトルネックマッチング問題を解決することで決定されてよい。２分グラフは２つの分離した頂点の集合F及びGを含み、F及びG間に頂点しかないようにする。各エッジeは高さw(e)を有する。マッチング(matching)は、どれもエンドポイントを共有しないようなグラフエッジの部分集合である。完全なマッチングは、グラフの各頂点がそのマッチングの或るエッジのエンドポイントになるところのマッチングである。言い換えれば完全なマッチングは全ての頂点をカバーする。或るグラフで完全なマッチングの存在する条件は、２つの集合F及びSが同じ濃度（集合の要素数）を有することである。ボトルネックマッチング問題の目的は、マッチングの最大重みが最小になるところのマッチングを生成することである。図１０は重みと共にエッジ及び２つの集合F,Sを有する完全な二部グラフGを例示する。マッチングはボールド体で示されている。それは３つのエッジ(f1,s1),(f2,s2),(f3,s3)より成り、それぞれ1,2,3のウエイトを有する。このマッチングはたまたまボトルネックマッチング問題の解にもなる。このマッチングの最大ウエイトエッジの重みは３である。このグラフにおける他の如何なる完全マッチングも３より小さなウエイトを有する最大ウエイトエッジを備えることはできない。ボトルネックマッチング問題は、完全マッチングアルゴリズムを反復的に呼び出すことで正確に解けるかもしれない。ｉ番目の反復で、Wi-1より大きなウエイトを有するグラフ中の全てのエッジが除去され、Wi-1は(i-1)番目の反復で得られたマッチングの最大ウエイトエッジである。完全マッチングは新たなグラフで得られるかもしれない。特定の実施例では、完全マッチングが発見できなかった場合にアルゴリズムは終了する：最終的な完全マッチングはボトルネックマッチング問題の解を与える。エッジウエイトについてのバイナリサーチがリニアサーチに加えて又は代替的に使用されてもよい。
【００４４】
特定の実施例では、FF及びHツリーシンクペアリング問題の場合に、集合F,S勝木のように定義されてよい。集合Fは全てのFFに対応し、集合SはHツリーシンクに対応する。ダミーFF頂点は、同じ濃度を有する２つの集合を作るためにFに加えられ、完全マッチング問題の解が存在するようにする。所与のHツリーのFF f及びシンクsの下で、ｆ及びｓの間にエッジが存在し、そのウエイトはｆ及びｓの間のマンハッタン距離である。ダミーFFでのエッジインシデント(edge incident)は重みゼロを有する。Gでのボトルネックマッチング問題の解は所望のFF及びシンクペアリングを生み出す。
【００４５】
大きなサイズのGに起因して、エッジを格納するのに要するメモリはワークステーションのメモリ限界を超える。実際のデザインでは、Sは１００万個より多くの頂点を含むかもしれない。これはGの中で１兆個より多くのエッジを必要とする。従って特定の実施例は、グラフのエッジを明示的に格納しない発見的手法を使用する。この発見的手法は、全てのFFについて（或る順序で）反復し且つFFを最も近いペアになってないシンクとペアにすることで、初期マッチングを作成する。そして反復的な改善フェーズに入り、そのフェーズではマッチングにおける最大ウエイトエッジe1=(f1,s1)を置換しようとする。これは、エッジe3=(f1,s2)及びe4=(f2,s1)のウエイトがe1のものより小さくなるように、マッチングに所属する他のエッジe2=(f2,s2)を設けることでなされる。そのようなエッジe2が発見されたならば、e1,e2はマッチングから除去され、e3,e4が付加される。
【００４６】
特定の実施例は、ツリーのリピータに挿入するHツリー生成プログラムを使用する。プログラムは対称的なツリーを生成するように修正され、クロックソースからFFに至る各経路が、相対的な位置、サイズ、バッファ数及びリピータ数だけでなく相互接続長の観点からも等しくなるようにする。
【００４７】
特定の実施例では、ジッタ分析アルゴリズムは、上述のアルゴリズムで生成された対称的クロックツリーQ上で動作する。Qで統計的に計算されたジッタを用いるデザインの（従来のSTAで報告される）クリティカルパスを再分析するためにポストプロセシング法が、以下の第４及び第５ステップでの分析に組み込まれてもよい。
【００４８】
１．全てのFFのクロックピンでの遷移時間を決定するため、Tのスパイス分析を実行する。
【００４９】
２．上述したようにクロックツリーQは対称的である。従ってジッタ分析に関しQの中の一方の経路Pだけを考察すればよい。Pはクロックソースから出発し、任意に選択されたFFで終端する。Pはステージ（複数）又はセクション（複数）に分解される。ステージSiはPでのリピータ又はバッファの入力ピンpiから始まり、P上の最初の下流のバッファ、リピータ又はFFpi+1で終端する。これは最初のバッファ／リピータ／FFに至るまでのpi及びpi+1間の分岐（もしあれば）も含む。図９はパスPのステージを示し、クロックソースpiで始まり、FFp5で終端する。簡明化のためFFはHツリーシンクに一致するよう示されている。Pは４段（ステージ）である。１乃至４の各iについて、ステージSiはpiから始まり、pi+1で終端し、pi+1に至るまでのファンアウトブランチも含む。所与のクロックツリーの下で、経路に関する判定ステージSiは、各SiにおけるMCSを実行し、平均値及びシグマ遅延(ti,σi)を判定する。Siがバッファのない分岐ノードｎを有していたならば、Si中の全てのサブステージの遅延（駆動バッファからｎに至るまでの遅延、及びｎからそのファンアウトまでの遅延も含む）が計算される。ステージSiの遅延はpi+1での容量負荷及びpiでの入力スキューの関数である。スキュー変動は無視される。各ステージについて、MCSの間にスキュー分布が（まさに遅延分布のように）計算され、（ちょうどPVTX変動のように）入力として使用され、次のステージが遅延及びスキューに関して特徴付けられる。スキュー分布を広めるため、クロック源からシンクに至るトポロジ的な順序でステージが横断(traverse)され特徴付けられる。２種類のMCSが各Siについて実行されてよい：一方は全てのPVTX変動を含み、他方はVX変動のみを含む。
【００５０】
３．(ti,σi)を用いて、Si乃至ti-k*σiの最小遅延及びti+k*σiの最大遅延を設定する（ｋは通常的には３乃至６の間である。）全てのＦＦクロックピンでの最小及び最大待ち時間を決定するために、そのツリーについてミンマックス(min-max)分析を実行する。これは各経路についてステージ遅延を加算することでなされてもよい。これは擬似的なプライムタイム遅延計算である。特定の実施例はk=3を使用するかもしれない。
【００５１】
４．先行する３つのステップで計算された、最小，最大待ち時間及びクロックピンでの遷移時間を利用して（プライムタイムのような）スタティックタイミング分析ツールを起動する。全てのクリティカルデータパスを生成する。
【００５２】
５．或るFFから始まり或るFFで終わるクリティカルパスの各々について、上述のジッタ手法を用いてソース及びターゲットFFに対応するクロック経路を分析し直す。この手法は２つのFFのクロックピンでの到着時間を計算するために（プライムタイムのようなツールにおけるワーストケース分析の代わりに）統計的分析法を使用する。新たな到着時間を利用してそのパスが依然としてクリティカルであったならば再評価し、そうでなければ考察対象からそれを除去する。
【００５３】
特定の実施例ではオールペア(all-pair)ジッタ分析プログラムはクロックツリーQで全てのFF対について３σのジッタ値を算出する。所与のデータパスP（FFsから始まり、FFeで終わるパス）の下で、クロックルートからFFs及びFFeにそれぞれ至るQにおける2つの経路Ps及びPeを特定する。クロック源から始まることで、Ps及びPeはいくつものステージを共有し、従って分かれる。Qは対称的であり、非共有パス（複数）は、インバータ数、対応するラインセグメントのサイズ及び長さの観点から同じである。図6に示されるものと同様な表現で各ステージについてσの値を入力することで、特定の実施例はPについてトータルのクロックジッタを計算する。Qの中の経路でのステージ数がｑであったとすると、（q+1）個の異なるジッタ値しか存在しない。これらはｉステージを共有するPs及びPeに対応する（i=０〜q）。Qの対称性及び使用されるロケーション依存性の変動に起因して、最初のｉステージを共有する全てのFFペアは同じジッタ値を有する。このユーティリティはQの対称性に起因して比較的速やかに実行される。同様なユーティリティがレース分析に使用されてもよい。
【００５４】
特定の実施例はクロックツリー分析手法をもたらし、その手法はVdd、温度、プロセス及びクロストークノイズのようなジッタ原因の影響も考慮する。特定の実施例は、スパイスを用いるモンテカルロ分析を使用し、包含される全てのジッタソースモデルを使用し、平均値及びジッタについて各バッファステージを正確に分析することを前提にする。特定の実施例は、最悪ケースとは異なり統計的であり、個々のステージのジッタを（STAツールでなされているように単にそれらを加算するのでなく）二乗和平方根として合成する。特定の実施例は、完全に対称的なツリーを生成する合成アルゴリズムを提案し、ツリーに関するステージ及びパスジッタは極めて効率的に算出可能である。
【００５５】
P,V,T変動の更に現実的なモデルが特定の実施例に導入される。V及びTのモデル化を改善する手法は説明済みである。プロセス変動は先ず組織的かつランダムに分割され、その後に近似的にモデル化される。
【００５６】
特定の実施例は或るFFを各Hツリーシンクに割り当てる。未割当シンク数が多ければ、かなりの配線リソース及びパワーが浪費される。或る手法はグループ化を行い、複数のFFを１つのシンクに割り当てるが、依然としてほとんど対称的なツリーを生成する。
【００５７】
特定の実施例では、対称的なツリーは、低度のスキュー及び効率的なジッタ分析には良好であるが、配線及び電力を消費するかもしれない。また、例えばRAM及び第三者のIPのような障害物が存在する場合には、完全に対称的なツリーを生成することは困難かもしれない。更にPVTX変動がたとえあったとしてもチップ上のデバイスの場所の関数であったならば（例えば、クロストークノイズ）、特定の実施例はそのような変動にも適合する。広範なPVTX変動モデルの下で一般的なクロックツリーについてのジッタ分析を効率的且つ正確に行う手法が使用される。
【００５８】
以上本発明を説明するために特定の実施例が使用されてきたが、添付の特許請求の範囲内で変更、置換、変形、代替又は修正の1以上を当業者は理解するであろう。本発明はそのような変更、置換、変形、代替及び修正の全てを包含する。
【００５９】
以下、本発明により教示される手段が例示的に列挙される。
【００６０】
（付記１）
クロックツリーにてジッタを計算する方法であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
を有することを特徴とする方法。
（付記２）
クロックツリー中の経路又は経路対に関するジッタを用いて、クロックツリーにおける長い経路及び短い経路のタイミング分析を実行するステップ
を更に有することを特徴とする付記１記載の方法。
【００６１】
（付記３）
クロックツリーの２以上のステージが近似的に電気的に互いに等価であり、
近似的に電気的に等価なステージのジッタを算出するステップが、近似的に電気的に等価なステージ１つのみにおけるジッタを算出するステップを有し、前記近似的に電気的に等価なステージ各々におけるジッタは、近似的な電気的な均衡の結果として、近似的に互いに等しい
を特徴とする付記１記載の方法。
【００６２】
（付記４）
算出されたジッタは、クロックツリーの全ての経路又は経路の全ての対に関する最悪ケースのジッタである
ことを特徴とする付記３記載の方法。
【００６３】
（付記５）
前記回路におけるクリティカルパスの第１数の第１リストを生成するスタティックタイミング分析（STA）を前記回路で実行するステップと、
前記STAの出力を利用して、前記クロックツリー中の経路又は経路対に関して算出されたジッタに従って、前記回路の１以上のフリップフロップにおける１以上のクロック到着時間を収集するステップと、
前記回路におけるクリティカルパスの前記第１数以下の第２数の第２リストを生成するステップと、
を更に有することを特徴とする付記１記載の方法。
【００６４】
（付記６）
回路のクロックツリーを合成する方法であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該方法は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
を有することを特徴とする方法。
（付記７）
回路のジッタを推定する方法であって、
前記回路中のジッタ源各々の表現を含む、回路の少なくとも一部分のモデルを生成するステップと、
前記モデルを利用して、前記回路におけるジッタを推定するステップと、
を有することを特徴とする方法。
【００６５】
（付記８）
実行用に媒体中にエンコードされ、クロックツリーにてジッタを計算するための論理装置であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
をコンピュータに実行させる論理装置。
（付記９）
クロックツリー中の経路又は経路対に関するジッタを用いて、クロックツリーにおける長い経路及び短い経路のタイミング分析を実行するステップ
を更に有することを特徴とする付記８記載の論理装置。
（付記１０）
クロックツリーの２以上のステージが近似的に電気的に互いに等価であり、
近似的に電気的に等価なステージのジッタを算出するステップが、近似的に電気的に等価なステージ１つのみにおけるジッタを算出するステップを有し、前記近似的に電気的に等価なステージ各々におけるジッタは、近似的な電気的な均衡の結果として、近似的に互いに等しい
を特徴とする付記７記載の論理装置。
（付記１１）
算出されたジッタは、クロックツリーの全ての経路又は経路の全ての対に関する最悪ケースのジッタである
ことを特徴とする付記１０記載の論理装置。
（付記１２）
前記回路におけるクリティカルパスの第１数の第１リストを生成するスタティックタイミング分析（STA）を前記回路で実行するステップと、
前記STAの出力を利用して、前記クロックツリー中の経路又は経路対に関して算出されたジッタに従って、前記回路の１以上のフリップフロップにおける１以上のクロック到着時間を収集するステップと、
前記回路におけるクリティカルパスの前記第１数以下の第２数の第２リストを生成するステップと、
を更に実行させることを特徴とする付記８記載の論理装置。
（付記１３）
実行用に媒体中にエンコードされる、回路のクロックツリーを合成するための論理装置であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該論理装置は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
をコンピュータに実行させる論理装置。
（付記１４）
実行用に媒体中にエンコードされる、回路のジッタを推定するための論理装置であって、
前記回路中のジッタ源各々の表現を含む、回路の少なくとも一部分のモデルを生成するステップと、
前記モデルを利用して、前記回路におけるジッタを推定するステップと、
をコンピュータに実行させる論理装置。
【００６６】
（付記１５）
クロックツリーにてジッタを計算するシステムであって、
クロックツリーを複数のステージに分割する手段と、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出する手段であって、前記モデルは前記回路のジッタのソース各々の表現を含むところの手段と、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成する手段と、
を有することを特徴とするシステム。
（付記１６）
回路のクロックツリーを合成するシステムであって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該システムは、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定する手段と、
前記クロックツリーのルーティング法を決定する手段と、
前記クロックツリー中のシンクに各フリップフロップを割り当てる手段であって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところの手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合する手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合する手段と、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入する手段と、
を有することを特徴とするシステム。
（付記１７）
回路のジッタを推定するシステムであって、
前記回路中のジッタ源各々の表現を含む、回路の少なくとも一部分のモデルを生成する手段と、
前記モデルを利用して、前記回路におけるジッタを推定する手段と、
を有することを特徴とするシステム。
【図面の簡単な説明】
【００６７】
【図１】クロストークを例示する図である。
【図２】データパス及びデータパスに関するクロックツリーを例示する図である。
【図３】クロックツリーステージジッタのシミュレーションモデルを例示する図である。
【図４】クロックツリーを例示する図である。
【図５】ジッタ変動のパラメータ例を示す図である。
【図６】ロングパス分析例の計算例を示す図である。
【図７】レース分析例の計算例を示す図である。
【図８】クロックツリー合成及び分析の方法例を示す図である。
【図９】クロックソースからフリップフロップ（FF）までのパスのステージ例を示す図である。
【図１０】完全な二部グラフを例示する図である。
【技術分野】
【０００１】
本発明は一般に回路設計に関連し、特にディジタル回路のクロックツリーにおけるジッタを評価すること並びにスキュー及びジッタ認識クロックツリーを合成することに関連する。
【背景技術】
【０００２】
集積回路のスケールが増加するにつれて、プロセス及び環境（例えば、電圧、温度及びクロストーク等）の影響はそのような回路全体を通じた遅延変動を増やす傾向にある。そのような変動は回路のクロックジッタ（又はフリップフロップのクロック到着時間の不確定性）を増やす。ジッタの増加は、一定のクロックサイクルに関する回路のクリティカルパスでの最大許容遅延を減らし、より強引な最適化及びより多くのターンアラウンドタイム(turn around time)を更なる重要事項にする。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
図１はクロストークを例示する図である。ディープサブミクロン回路設計では、ワイヤはより高く且つより狭くなっている一方、それらを互いに分離する距離は減っているので、隣接する相互接続間のカップリングキャパシタンスはかなり重要な問題になっている。その結果、物理的に隣接するネット（又は相互接続部）間のクロストークはかなりの問題となっている。影響を受けるネットはビクティム(v: victim)である。犠牲側又はビクティムｖに影響するノイズを引き起こす隣接するスイッチングネットは、攻撃側又はアグレッサ(a: aggressor)である。アグレッサａに関するものは適切ならばそのようなネットの１以上を含む。図１に示されるように、アグレッサａがビクティムｖと反対向きにスイッチする場合に、クロストークはビクティムｖでの到着時間を増やすかもしれない。アグレッサａがビクティムｖと同じ方向にスイッチする場合には、クロストークはビクティムｖでの到着時間を減らすかもしれない。ｖ及びａ間の分布結合容量はCciとして示される。クロストークは論理ハザード及び回路不具合にもなるおそれがある。例えば遅延変動がクロックサイクルより遅いクリティカルパスを変える程度に（及びタイミングバイオレーションを引き起こす程度に）十分大きかった場合、又はアグレッサａとの容量カップリングに起因してビクティムｖで発生した大きなスパイクが、ターゲットフリップフロップ（ＦＦ）で不適切な値をクロックエッジでラッチするのに十分近接していた場合に、回路は不具合をおこす。クロストークに起因する遅延変化の正確な計算は回路設計で重要になりつつある。
【０００４】
本発明の課題は、チップレベルの設計に関するこの問題に対処し、クロストークカップリングが存在する場合に正確な経路遅延を計算することである。
【課題を解決するための手段】
【０００５】
本発明では、クロックツリーにてジッタを計算する方法が使用される。本方法は、クロックツリーを複数のステージに分割するステップと、クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップとを有する。
【発明を実施するための最良の形態】
【０００６】
本発明並びに本発明の特徴及び利点についての理解を更に完全にするため、添付図面に関連する以下の説明が参照される。
【０００７】
以下、本発明の実施例によるシステム、方法及び論理装置が説明される。この場合において、論理装置なる語は、ソフトウエアで構成される論理プログラムや、ハードウエアで構成される論理回路を含む概念である。
【０００８】
従来の設計法及びスタティックタイミング分析(STA: static timing analysis)ツールは、クロックツリーの各バッファについて悲観的(pessimistic)遅延マージンを確保することでクロックジッタを取り扱う。ワーストケース分析のように、これらはクロックツリーのパスにバッファのこれらのマージンを積み上げる。そしてクロック経路がソースＦＦであるかターゲットＦＦであるかに依存して、マージン合計は公称パス遅延の分だけ加算される或いは減算される。そのようなワーストケース分析は過剰に悲観的である；なぜなら、１つのクロック経路でのバッファ全てについて最小遅延状態（即ち、最低温度、最大供給電圧、最小チャネル長及び最低閾値）を及び他のクロック経路でのバッファについて最大遅延状態（即ち、最大温度、最小供給電圧、最大チャネル長及び最大閾値）を仮定しているからである。そのような極めて不適切なシナリオを利用することは、不必要に過剰な回路設計となってしまう。不具合のあるチップの大半はそのツールで予測されるものより高い（３０％よりも高い）パフォーマンスを示す。
【０００９】
統計的スタティックタイミング分析(SSTA)はより現実的なタイミング検査の代替的なパラダイムである。概してSSTAに関して２種類の手法が提案されている：分析的なものとサンプリングベースのものである。分析的手法は、（例えば、ガウス型確率密度関数の形式で）統計的ゲート遅延モデル及び統計的プロセス変動モデルを入力として採用し、回路又は経路遅延の確率密度関数（PDF）を構築する。包含される数学的複雑さ（例えば、PDFの最大及び最小を導出すること）に起因して、これらは依然として研究テーマである。サンプリングベース又はモンテカルロ（MC）ベースの手法は入力パラメータの値を生成し、そのパラメータは或る分布（例えば、一様であったり、又はガウス型）を満たすことを仮定する。回路遅延はこれらの値の下で計算される。遅延分布曲線に関して充分な遅延値が得られるまで、手順は何百回も何千回も反復される。MCベースの手法は高精度であるが、演算負担が大きい。これらを実際の工業的設計に直接的に適用することは困難かもしれない。
【００１０】
特定の実施例でのクロックツリージッタ分析の方法論は、分析的手法及びモンテカルロ法を結合する。特定の実施例では、ツリー合成法がゼロスキューツリー(zero-skew tree)を生成する。このツリーでのジッタ分析は、従来のMCベースの手法よりも効率的であり且つ従来のSTAより悲観的ではない。特定の実施例での方法論は、プロセス、温度、電圧及びクロストークの変動の下で、イーサーネットチップの分析及びクロックツリー合成に適用可能である。
【００１１】
所与のクロックツリー及びソース，ターゲットFFの下で、特定の実施例はクロックジッタを計算するために、統計的且つ（最悪事態の方法論と比較して）悲観の度合いの少ない手法を使用する。この手法では、クロックツリーの各バッファ段の遅延変動（又はジッタ）は、モンテカルロシミュレーションを用いるスパイス（SPICE）で正確に計算される。そしてステージのジッタは統計的に結合され、（従来のSTAツールでなされるように）単にジッタを加算するのではなく、完全なクロック経路（又は一対のパス）についてジッタを生み出す。特定の実施例はクロックツリーを合成し、そのクロックツリーで上記のステージジッタ計算及びツリージッタ分析が効率的に実行される。
【００１２】
特定の実施例では、クロックジッタ分析アルゴリズムは、データパスのソース及びターゲットFF間のジッタを分析する。特定の実施例では、ポストプロセシング法が、クロックツリーに関する統計的ジッタ計算を利用して、従来のSTAツールにより報告されたデザインのクリティカルパスを再分析する。
【００１３】
所与の固定されたサイクルタイムの下で、クロックスキュー及びジッタは共に設計回路のクリティカルパスの最大許容遅延を減らす。スキューは所与の２つのフリップフロップFFi及びFFj間に関するクロック到着時間ti及びtjの確定的な差分(deterministic difference)である。スキューは、如何なるプロセス、電圧又は温度変化もなく且つ全てのノイズ源がゼロである場合のクロック分散ネットワークでの不整合（不完全な又は計画的な）を追跡可能である。クロック分布ネットワークの正確なモデルを構築すること、そして一定の温度及びVddでクロックツリー上のクロックソースから全てのFFまでSPICE又はSTAを実行すること、及びクロックソースで５０％のVddから各FFで５０％のVddに至るまでの公称クロック遅延ｔを測定することで、スキューは計算されてよい。従ってクロックスキューを計算することは、クロック遅延及び到着時間を計算し、差分を計算することと等価であるかもしれない。
【００１４】
ジッタは対象のパラメータの不確定性又は時間変動である。クロックに関し、対象のパラメータはフリップフロップのクロック到着時間である。クロックサイクルがτである場合に、どの２つの連続するサイクルの上昇（及び下降）クロックエッジも理想的にはFFでτ時間単位離れている。しかしながら実際にはこのタイムギャップは以下の理由で変わることが間々ある。
【００１５】
１．時間の関数のようなゲートでの供給ノイズ又はVdd-Vss変動。供給ノイズは異なるクロックサイクルでスイッチングする異なるゲート群に起因する。これはVdd及びVssラインでの時間変化する電流をもたらし、従ってIR及びLdi/dtの低下を招く。ゲートの遅延はVddに依存するので、クロックバッファの供給電圧の如何なる変化もそのFFでのクロック到着時間を変える。
【００１６】
２．ゲートでの及びダイにわたる温度変化。パワー及び温度は特にリーケージドミナント法で(leakage-dominant technologies)互いに強く関連するので温度変化が生じる。高速スイッチングの障害は多くの電力を劇的に散逸させ、より高い局所的な温度を招く。そしてこれは漏れ電力散逸を増やし、全体の電力を更に増やす。これはそのチップに関する大きな温度勾配を導入する。ゲートの温度変化は異なるサイクルでの異なるスイッチング動作にも起因する。高温でのゲート動作はキャリア移動度の減少に起因してより多くの遅延を招く。
【００１７】
３．クロストークノイズ。図１に示されるように、ｖに物理的に近く且つスイッチングしているアグレッサａが有ったならば、クロックワイヤの遅延は変化するかもしれない。アグレッサのスイッチング挙動は或るサイクルと次のサイクルで異なるかもしれないので、それはビクティムでジッタを招くおそれがある。設計で最も重要な信号の１つはクロックである。そのようなクロストークの影響を減らすためにクロックの両側でVdd/Vssシールディング(shielding)が行われるのが一般的である。しかしながらワイヤバスがクロックラインを超えて進む場合には、そのシールティングは上位及び下位レイヤからのクロストークを防げない。
【００１８】
４．PLLジッタ。PLLから生成されたクロックは或る固有のジッタを有する。
【００１９】
５．ダイに関するプロセス変動。プロセス変動の具体例は、MOSFETのチャネル領域におけるランダムなドーパント揺らぎのような本質的な変動と、チャネル長や酸化物厚みの変動のような非本質的な変動とを含む。また、化学機械平坦化（CMP）プロセスでは、相互接続の幅、厚さ、間隔及び高さが所望値からかなり変化するかもしれない。これらの変動はゲート又はワイヤ遅延を所望値から逸脱させる。正確な変動の大きさ（従って製造後のワイヤ及びゲート遅延の正確な値）を予測することは困難である。この現象はスキューでは捕らえられない。チップ製造後のトランジスタ又は相互接続の寸法に顕著な時間依存する変化がない場合でさえ、それをジッタとしてモデル化することが更に有利である。
【００２０】
図２に示されるようにフリップフロップFFsから出発し、組み合わせ論理を通じてFFeに至るデータパスを仮定する。as及びaeをそれぞれFFs及びFFeでのクロック到着時間とする。これらの到着時間は公称（名目）遅延及びジッタを含む。τをPLLクロックサイクル時間とする。特定の実施例ではSTAの２つの基本機能は、ロングパスを検出すること及びレース(race)を検出することである。
【００２１】
１．ロングパスの検出。この分析では所与の開始及び終端のFFs及びFFe各々の下で、dmaxが組み合わせ論理（FFsを介する遅延を含む）の最大パス遅延であったならば、適切に動作する回路に関し、以下の不等式が満たされるべきである。
【００２２】
as+dmax≦ae+τ−tset-up （１）
STAツールはτavail(s,e)、２つのFFs間の最小利用可能サイクルを見出す：
τavail(s,e)=τ+ae-as （２）
簡明化のため、数式（２）でFFeに関する設定時間(set-up)はゼロであるとする。そしてSTAはdmaxが高々τavail(s,e)であるか否かを判定する。この分析では受信フリップフロップ捕捉クロックエッジは、送信フリップフロップクロックエッジ後の１サイクルである。従ってPLL（又は他のクロック源）サイクルジッタはこの分析に包含されるべきである。
【００２３】
２．レース検出。この分析ではSTAツールはFFs及びFFe間での同一クロックエッジの最大クロック到着時間差を見出す。dmin（フリップフロップ間の最小論理遅延）が受信フリップフロップのホールド時間に合わない程度に短い（クロック到着時間差より短い）か否かを判定する。言い換えれば適切な動作については次式が成立する：
as+dmin≧ae+thold （３）
プライムタイム(Prime Time)のような従来のSTAツールは、クロックツリー中のバッファ各々について悲観的な遅延を確保することでクロックジッタを取り扱う。このマージンは技法、プロセス、その設計でのスイッチング動作、Vdd、レイアウト等に依存する。例えばバッファの公称遅延を１００ｐｓとし、変動を収容するためのマージンが１５％であったとする。この場合バッファの最小遅延は８５ｐｓになり、最大遅延は１１５ｐｓになる。ロングパス分析の間にSTAツールは、クロックソースclkからFFeに至る経路上のバッファについてこれらのマージンを公称遅延から減算し、clkからFFsに至る経路上のバッファにこれらのマージンを加算する。図２はこれらの遅延を示す。２つのクロック経路でスキューがゼロであるように設計されていたならば全体的なジッタマージンは６０ｐｓになることが分かる。そのような最悪状況分析は過剰に悲観的である。なぜならclkからFFsへ至るパスの各バッファについて最大遅延状態（例えば、最大温度、最小供給電圧、最大チャネル長及び最大しきい電圧）を仮定し、clkからFFeに至るパスのバッファについて最小遅延状態（例えば、最小温度、最大供給電圧、最小チャネル長及び最小しきい電圧）を仮定しているからである。
【００２４】
特定の実施例は過剰に悲観的な最悪状況分析を統計的分析で置換する。また、特定の実施例は悲観的なマージンを用いる代わりにSPICE及びモンテカルロ分析を用いて、ツリーステージのジッタを計算する。
【００２５】
図３はクロックツリーステージジッタのシミュレーションモデル１０を例示する。特定の実施例では反転バッファ１２はワイヤを通じてインバータ１４を駆動する。
【００２６】
１．供給ノイズＶ：独立している供給電源を設計回路の各バッファに供給し、ノイズモデルに従ってそれらがランダムに変化できるようにすることで、供給ノイズはモデル化される。変動量はユーザ入力パラメータsupply_toleranceで制御される。
【００２７】
２．温度変化Ｔ：温度上昇はCMOS回路の動作を低速化し、配線抵抗を増やす。回路全体について前提とする温度を指定し、クロックバッファ及び相互接続各々でランダムなローカルな温度変化を適用することで、トランジスタの温度変化がモデル化される。適用する変動はユーザ入力パラメータmax_deltempで与えられる。
【００２８】
３．クロストークノイズＸ：図３のワイヤモデルに外部ノイズソースを取り付け、何らかの確率分布に基づいてこれらのソースでランダム入力を適用することで、クロストークノイズはモデル化される。この例に関連するクロストーク因子はワイヤが具体化される毎に規定されるべきである。クロストーク因子はデザイン各々に固有の特性であり、従ってパラメータxtfactorを用いてユーザにより与えられる。
【００２９】
４．PLLジッタ：特定の実施例は３σPLLの最大PLLジッタを仮定する。
【００３０】
５．プロセス変動Ｙ：図３に示されるように、トランジスタのプロセス変動はチャネル長（PMOS及びNMOSトランジスタそれぞれについてlp及びln）及び閾値（delvtn及びdelvtp）だけを用いてモデル化されてよい。酸化膜厚及びドーパント濃度のような他の変動は、しきい電圧を変える全体的な影響を及ぼし、モデル１０に含まれてよい。閾値及びチャネル長の変動はバッファ副回路モデルの各場合に伝達される。配線のプロセス変動は、ワイヤモデルの配線容量及び抵抗（pfc及びpfr）にランダムなプロセス因子を適用することでモデル化される。プロセス変動量は、使用されるプロセスの特性であり、従ってユーザによって変更可能ではない。
【００３１】
実際のチップでは、互いに接近して位置する要素の供給電圧（更には温度）が相関するおそれがある。例えば２つのバッファが物理的に互いに隣接し、同じ電源供給ラインに接続されていた場合に、それらのVdd及び温度変化はほとんど同じである。モデル１０ではそのような関連性を組み入れることができる。例えば１つ手法はVdd/Vss分布アーキテクチャ及びレイアウトに基づいてチップを抵抗Riに分割することである。各領域Riは平均電圧値Vddiを有し、平均電圧値はパワーアーキテクチャ及びその領域でのスイッチング動作から計算される。各シミュレーションでの領域中心についてΔVddiを計算するためにランダム変数が使用される。距離ベースの相関関数ｆを用いてその領域の各バッファの電圧を計算する(f(Vddi+ΔVddi,l))。ここでｌはRiの中心からのバッファの距離である。特定の実施例はワーストケースパラダイムを使用せず、より現実的なものになる。ユーザはそのようなモデルを自由に用意でき、モデルはその手法に組み入れられる。
【００３２】
PVTX変動を組み入れるこの統合された統計的モデルの下で、特定の実施例はSPICEと共にモンテカルロシミュレーション（MCS）を利用し、遅延に関する平均時間ｔ及び標準偏差σを生成する。MCSがチップレベルの設計でのクロックツリー全体について実行されるならば、そのモデルはメモリに適合しないかもしれないし又はMCSは終了するまでにかなりの長時間を要するかもしれない。特定の実施例は、ツリーの小さな部分又はステージについてMCSが実行される手法を使用する。図３に示されるように、ツリーステージ（又はセクション）の或る自然な定義は、別のバッファを駆動するツリー上のクロックバッファ又はワイヤを介したFFである。図３に示されてはいないが、次のレベルのバッファ又はFFに沿うワイヤ上の如何なる分岐点もそのステージに含まれてよい。かくてクロックツリーはステージ（複数）に分割され、MCSはSPICEを用いて各ステージで実行される。Δvtni, Δvtpi,lpi,lni,Vddi,Ti(i=1,2),T,pfc,pfrの各パラメータ及びクロストーク電圧源自身（図３）は各シミュレーションでガウシアン分布関数からランダムに選択されてよい。遅延は駆動バッファ１２の入力から駆動バッファ１３の入力で計算される。シミュレーションは要求される制度に依存して約１００−１０００回反復されてよい。これらのシミュレーションから、SPICEは各ステージの標準偏差σ及び平均時間ｔを自動的に計算する。或るステージのジッタは３σのように決定される。
【００３３】
クロックツリーの全てのステージについて平均遅延及びジッタ値を計算することで、クロックツリーの或るパス又はパスのペアについてジッタ値が計算されてもよい。そのために、図４に示されるクロックツリーの例が考察される。３つのデータパスがある：FF1名乃至FF2、FF1乃至FF3及びFF4乃至FF5である。各クロックインバータステージにはその公称遅延ti及び標準偏差σiがラベル付けされている。各σiは４つのソース全てを考慮する：プロセス（P）、供給電圧（V）、温度（T）及びクロストーク（X）である。別のジッタ要素σiVXは、供給電圧及びクロストークだけの変動に起因する遅延の標準偏差である。PLLサイクル時間をτとし、そのジッタを３σPLLとする。特定の実施例は、各ステージについて、遅延が他の如何なるステージとも非相関（又は独立）であること及び遅延が連続するサイクルの間にそれ自身とも非相関であることを仮定する。この仮定は、図５に示されるパラメータ変動と共に、２つの連続するステージ遅延の標準偏差σ1及びσ2だけでなく、それら２つのステージで構成される連鎖遅延のσをも計算することによって確認される。特定の実施例ではσ1=0.73ps/mm,σ2=0.7ps/mm及びσ=1.17ps/mmである。従ってσ12=√(σ12＋σ22)=1.01である。σに対するσ12の誤差割合は１４％であるが、絶対的なσ値（例えば、0.16ps/mm）での差分は平均遅延（83.38ps/mm）の0.19％しかない。PVTX変動が増えると、このエラーは更に悪化し、その仮定を確からしくする。或る経路を構成するステージの標準偏差は次のように結合される。S1乃至Snが経路（パス）上のステージであり、それぞれ標準偏差σ1乃至σnを有していたとすると、その経路のジッタは次式で与えられる：
【００３４】
【数１】
従来のSTAは
【００３５】
【数２】
のように経路ジッタを計算したであろう。これは
【００３６】
【数３】
よりもかなり大きい。例えば、クロック経路が１０個の同じステージを有し、その各々でσ=10psであったと仮定する。従来のSTAはその経路ジッタとして300psを算出するが、特定の実施例での統計的手法は３×√(10×100)=94.87psのようにそれを算出する。
【００３７】
特定の実施例は例えばロングパス及びレース分析のようなタイミング分析に統計的ジッタ手法を適用する。ロングパス分析τavail(s,e)に関し、図４のデータパス(FFs,FFe)各々に対応するロングパス分析に利用可能な最小サイクル時間が計算されてもよい。τavail(s,e)は(FFs,FFe)経路の組み合わせ論理の最大遅延の上限である。図６はその計算の様子を示す。所与の開始及び終了フロップについて、τavail(s,e)は数式２を用いて算出され、即ちその計算は、開始フリップフロップに対して公称(平均)クロックツリー遅延を減算し、終了フリップフロップのクロックツリー遅延を公称クロックサイクル時間τに加算し、その後に経路に含まれる要素全ての二乗和ジッタの平方根を減算することでなされる。利用可能なサイクルタイムの最小値を計算するためにジッタは減算されてもよい。平方根記号の前にある因子３はジッタの分析に３σを利用することを意味する。スタート及びエンドのFF間のクロック経路に共通のバッファ（例えば、スタートフロップFF1及びエンドフロップFF2に関するバッファ１２，１４）があった場合には、それらの平均遅延の合計(t1+t2)が双方の経路に現れ、相殺することに留意を要する。しかしながらバッファ１２，１４のジッタへの寄与はそれぞれ3×(2σ1vx2)及び3×(2σ2vx2)である。共有バッファのジッタ寄与はゼロではない。これは、ロングパス分析では、各共有バッファ（シェアドバッファ）が或るサイクルでasに及び次のクロックサイクルでaeに遅延をもたらすことに起因する。これら２つの遅延は時間と共に変化するパラメータに起因して変化してもよい。共有バッファに関し、特定の実施例はV,Xに起因する変動のみを包含してもよい。なぜなら所与のバッファに関し、何らのプロセス変動もなく且つ或るサイクルと次のサイクルで温度は変化すべきでないからである。更に共通バッファは２回登場する：１つはスタートフロップに関してであり、もう１つはエンドフロップに関してである。従ってそれらの二乗ジッタ要素には２が乗算される。PLLジッタ３σPLLも包含されてよい。逆に、プライムタイムのようなSTAツールは開始フリップフロップFF1及び終了フリップフロップFF2に関してτ−3(2σPLL+2σ1+2σ2+σ3+σ4)のようにτavailを計算する。
【００３８】
レース分析に関し、同一エッジクロックにおける終了フリップフロップ及び開始フリップフロップ間の到着時間の最大差分が、図４の各経路について計算される。図７はその計算を示す。それらは、開始フリップフロップに対する非共有クロックツリーステージの公称クロック遅延を、終了フリップフロップに対する非共有クロックツリーステージのクロック遅延から減算し、２つの経路で全ての非共有クロックツリーステージのジッタの二乗和平方根を加算することで計算される。レース分析では、共有バッファのジッタ寄与はゼロである。なぜなら唯１つのクロックサイクルしか分析に含まれていないからである。所与のクロックツリーＱの下で、上記の手法は、Ｑの全てのステージの確認を必要とし、スパイスと共にモンテカルロシミュレーションを行うことで各ステージについてのジッタ遅延値及び平均値を計算する。非常に高精度であるが、この手法はしばしば演算負担が重くなる傾向がある。典型的な設計では、何十万ものFF及びバッファがクロックツリー上にある。バッファの各々が１つのステージに対応する。演算負担の観点からは、数千ステージについてMCS計算を実行することは実現不可能かもしれない。特定の実施例では或るツリー合成法がこの問題を解決する。
【００３９】
図８はクロックツリー合成及び分析の方法例を示す。本方法はジッタ及びスキューを意識する。本方法は１以上のチップ仕様（例えば、チップ寸法等）、FF配置及び１以上の変動モデルを利用する。図８に示される方は特定の順序で生じるように特定のステップが示され且つ説明されているが、図８に示される方法の中で適切などのステップも適切な如何なる順序で行われてもよい。１以上のコンピュータシステムは図８に示される方法の１以上のステップの実行を促進してもよい。概して従前の手法を用いるクロックツリーQのジッタ分析は演算負担が大きい。しかしながらQが完全に対称的であったならば、その分析はより効率的であるかもしれない。そのようなツリーでは、クロックソースからFFへのどの２つの経路も、バッファサイズ及びそれらの間の配線長の観点からは、実質的に同じである。それは、平均値及びシグマ遅延に関し、唯１つのツリー経路でバッファステージを特徴付けるのに充分である。特定の実施例は、PVTXパラメータの変動はチップ内の位置の関数ではないことを仮定する。これは特定の変動モデルに関して成立する。或る変動モデルの場合にこの仮定が成立しなかったならば、そのクロックツリーの中で１パスより多くの経路でバッファのステージジッタ分析が実行される。かくてツリー全体について何千ものステージでMCSを実行する代わりに、問題は近似的に高々２０乃至３０ステージ（パスの中の最大ステージ数）のMCSにまで減る。完全に対称的なツリーの別の利点はスキューがゼロになることである。従って特定の実施例は、対称的なツリーが生成される合成法を採用する。特定の実施例は次のように対称的クロックツリーを合成するためのアルゴリズムを使用する。
【００４０】
チップ上で（空間的に）非一様な分布のフリップフロップは、クロック分布の非対称性を引き起こすかもしれない。特定の実施例は、チップ中心のクロック源で駆動される対称的なグローバルHツリーを生成し、続いてHツリーのシンクからFFへの等価的な長い接続を行うことでこの非一様性に対処する。特定の実施例は高々１つのFFを各シンクに割り当てる。これはHツリーのレベル数λを決定する。例えば図９はクロックソースからFFまでのパスのステージ例を示す。より具体的には図９は１６個のシンクを備えた２レベルツリーを示す。設計中のFF数がｎであったとすると、４λ≧ｎである。４λはHツリーのシンク数である。FF−シンク割当の目的は何らかのシンクｓとｓに割り当てられるFFとの間の最大距離を最小化することである。最大距離をDとする。最終的に各シンクは長さDの相互接続によって、割り当てられたFFに接続される。或るFFのシンクに至る距離がDより短かったならば、特定の実施例は相互接続長Dを形成するために迂回させる又は曲げる。FFの割り当てられていないシンクがあったならば、長さDのダミーワイヤがそこに接続され、ダミー容量cfが相互接続の終端に取り付けられ、ここでcfはFFのクロックピンの入力容量である。簡明化のため、特定の実施例はcfが各FFに関して同じであることを仮定する。シンク及び割り当てられたFF間の最大距離を最小化することで、シンクからFFまでの相互接続長の合計も最小化される。
【００４１】
特定の実施例では、高々１つのFFを各シンクに割り当てることで及び割り当てられたFFに至る各シンクからのワイヤ長を等しくすることで、全てのHツリーシンクは同様なダウンストリームトポロジ（キャパシタンスcfに接続された長さDのワイヤ）を見ることになる。これはツリー上で同じセクションを生成可能にする、即ち所与のどの２つのHツリーシンクsi,sjでも、クロックソースからsi,sjに至るパス（バッファ及びリピータの数、位置及びサイズを含む）は等しい。
【００４２】
特定の実施例ではFF及びHツリーシンクの位置は事前に既知である。FFの位置は配置データから読み取られる。Hツリーシンクの位置はチップ寸法（高さ及び幅）及びツリーのレベル数λから容易に計算可能である。トップレベルのHはチップの中心に設けられ、その幅及び高さは、それぞれチップ高さ及び幅の或る分数αである。低レベルでのHは、親レベルの幅及び高さのα倍に等しい幅及び高さを有する。典型的にはα=0.5である。
【００４３】
特定の実施例ではHツリーシンクへのFFの正確な割当は、２分グラフ(bipartite graph)Gで完全な(perfect)ボトルネックマッチング問題を解決することで決定されてよい。２分グラフは２つの分離した頂点の集合F及びGを含み、F及びG間に頂点しかないようにする。各エッジeは高さw(e)を有する。マッチング(matching)は、どれもエンドポイントを共有しないようなグラフエッジの部分集合である。完全なマッチングは、グラフの各頂点がそのマッチングの或るエッジのエンドポイントになるところのマッチングである。言い換えれば完全なマッチングは全ての頂点をカバーする。或るグラフで完全なマッチングの存在する条件は、２つの集合F及びSが同じ濃度（集合の要素数）を有することである。ボトルネックマッチング問題の目的は、マッチングの最大重みが最小になるところのマッチングを生成することである。図１０は重みと共にエッジ及び２つの集合F,Sを有する完全な二部グラフGを例示する。マッチングはボールド体で示されている。それは３つのエッジ(f1,s1),(f2,s2),(f3,s3)より成り、それぞれ1,2,3のウエイトを有する。このマッチングはたまたまボトルネックマッチング問題の解にもなる。このマッチングの最大ウエイトエッジの重みは３である。このグラフにおける他の如何なる完全マッチングも３より小さなウエイトを有する最大ウエイトエッジを備えることはできない。ボトルネックマッチング問題は、完全マッチングアルゴリズムを反復的に呼び出すことで正確に解けるかもしれない。ｉ番目の反復で、Wi-1より大きなウエイトを有するグラフ中の全てのエッジが除去され、Wi-1は(i-1)番目の反復で得られたマッチングの最大ウエイトエッジである。完全マッチングは新たなグラフで得られるかもしれない。特定の実施例では、完全マッチングが発見できなかった場合にアルゴリズムは終了する：最終的な完全マッチングはボトルネックマッチング問題の解を与える。エッジウエイトについてのバイナリサーチがリニアサーチに加えて又は代替的に使用されてもよい。
【００４４】
特定の実施例では、FF及びHツリーシンクペアリング問題の場合に、集合F,S勝木のように定義されてよい。集合Fは全てのFFに対応し、集合SはHツリーシンクに対応する。ダミーFF頂点は、同じ濃度を有する２つの集合を作るためにFに加えられ、完全マッチング問題の解が存在するようにする。所与のHツリーのFF f及びシンクsの下で、ｆ及びｓの間にエッジが存在し、そのウエイトはｆ及びｓの間のマンハッタン距離である。ダミーFFでのエッジインシデント(edge incident)は重みゼロを有する。Gでのボトルネックマッチング問題の解は所望のFF及びシンクペアリングを生み出す。
【００４５】
大きなサイズのGに起因して、エッジを格納するのに要するメモリはワークステーションのメモリ限界を超える。実際のデザインでは、Sは１００万個より多くの頂点を含むかもしれない。これはGの中で１兆個より多くのエッジを必要とする。従って特定の実施例は、グラフのエッジを明示的に格納しない発見的手法を使用する。この発見的手法は、全てのFFについて（或る順序で）反復し且つFFを最も近いペアになってないシンクとペアにすることで、初期マッチングを作成する。そして反復的な改善フェーズに入り、そのフェーズではマッチングにおける最大ウエイトエッジe1=(f1,s1)を置換しようとする。これは、エッジe3=(f1,s2)及びe4=(f2,s1)のウエイトがe1のものより小さくなるように、マッチングに所属する他のエッジe2=(f2,s2)を設けることでなされる。そのようなエッジe2が発見されたならば、e1,e2はマッチングから除去され、e3,e4が付加される。
【００４６】
特定の実施例は、ツリーのリピータに挿入するHツリー生成プログラムを使用する。プログラムは対称的なツリーを生成するように修正され、クロックソースからFFに至る各経路が、相対的な位置、サイズ、バッファ数及びリピータ数だけでなく相互接続長の観点からも等しくなるようにする。
【００４７】
特定の実施例では、ジッタ分析アルゴリズムは、上述のアルゴリズムで生成された対称的クロックツリーQ上で動作する。Qで統計的に計算されたジッタを用いるデザインの（従来のSTAで報告される）クリティカルパスを再分析するためにポストプロセシング法が、以下の第４及び第５ステップでの分析に組み込まれてもよい。
【００４８】
１．全てのFFのクロックピンでの遷移時間を決定するため、Tのスパイス分析を実行する。
【００４９】
２．上述したようにクロックツリーQは対称的である。従ってジッタ分析に関しQの中の一方の経路Pだけを考察すればよい。Pはクロックソースから出発し、任意に選択されたFFで終端する。Pはステージ（複数）又はセクション（複数）に分解される。ステージSiはPでのリピータ又はバッファの入力ピンpiから始まり、P上の最初の下流のバッファ、リピータ又はFFpi+1で終端する。これは最初のバッファ／リピータ／FFに至るまでのpi及びpi+1間の分岐（もしあれば）も含む。図９はパスPのステージを示し、クロックソースpiで始まり、FFp5で終端する。簡明化のためFFはHツリーシンクに一致するよう示されている。Pは４段（ステージ）である。１乃至４の各iについて、ステージSiはpiから始まり、pi+1で終端し、pi+1に至るまでのファンアウトブランチも含む。所与のクロックツリーの下で、経路に関する判定ステージSiは、各SiにおけるMCSを実行し、平均値及びシグマ遅延(ti,σi)を判定する。Siがバッファのない分岐ノードｎを有していたならば、Si中の全てのサブステージの遅延（駆動バッファからｎに至るまでの遅延、及びｎからそのファンアウトまでの遅延も含む）が計算される。ステージSiの遅延はpi+1での容量負荷及びpiでの入力スキューの関数である。スキュー変動は無視される。各ステージについて、MCSの間にスキュー分布が（まさに遅延分布のように）計算され、（ちょうどPVTX変動のように）入力として使用され、次のステージが遅延及びスキューに関して特徴付けられる。スキュー分布を広めるため、クロック源からシンクに至るトポロジ的な順序でステージが横断(traverse)され特徴付けられる。２種類のMCSが各Siについて実行されてよい：一方は全てのPVTX変動を含み、他方はVX変動のみを含む。
【００５０】
３．(ti,σi)を用いて、Si乃至ti-k*σiの最小遅延及びti+k*σiの最大遅延を設定する（ｋは通常的には３乃至６の間である。）全てのＦＦクロックピンでの最小及び最大待ち時間を決定するために、そのツリーについてミンマックス(min-max)分析を実行する。これは各経路についてステージ遅延を加算することでなされてもよい。これは擬似的なプライムタイム遅延計算である。特定の実施例はk=3を使用するかもしれない。
【００５１】
４．先行する３つのステップで計算された、最小，最大待ち時間及びクロックピンでの遷移時間を利用して（プライムタイムのような）スタティックタイミング分析ツールを起動する。全てのクリティカルデータパスを生成する。
【００５２】
５．或るFFから始まり或るFFで終わるクリティカルパスの各々について、上述のジッタ手法を用いてソース及びターゲットFFに対応するクロック経路を分析し直す。この手法は２つのFFのクロックピンでの到着時間を計算するために（プライムタイムのようなツールにおけるワーストケース分析の代わりに）統計的分析法を使用する。新たな到着時間を利用してそのパスが依然としてクリティカルであったならば再評価し、そうでなければ考察対象からそれを除去する。
【００５３】
特定の実施例ではオールペア(all-pair)ジッタ分析プログラムはクロックツリーQで全てのFF対について３σのジッタ値を算出する。所与のデータパスP（FFsから始まり、FFeで終わるパス）の下で、クロックルートからFFs及びFFeにそれぞれ至るQにおける2つの経路Ps及びPeを特定する。クロック源から始まることで、Ps及びPeはいくつものステージを共有し、従って分かれる。Qは対称的であり、非共有パス（複数）は、インバータ数、対応するラインセグメントのサイズ及び長さの観点から同じである。図6に示されるものと同様な表現で各ステージについてσの値を入力することで、特定の実施例はPについてトータルのクロックジッタを計算する。Qの中の経路でのステージ数がｑであったとすると、（q+1）個の異なるジッタ値しか存在しない。これらはｉステージを共有するPs及びPeに対応する（i=０〜q）。Qの対称性及び使用されるロケーション依存性の変動に起因して、最初のｉステージを共有する全てのFFペアは同じジッタ値を有する。このユーティリティはQの対称性に起因して比較的速やかに実行される。同様なユーティリティがレース分析に使用されてもよい。
【００５４】
特定の実施例はクロックツリー分析手法をもたらし、その手法はVdd、温度、プロセス及びクロストークノイズのようなジッタ原因の影響も考慮する。特定の実施例は、スパイスを用いるモンテカルロ分析を使用し、包含される全てのジッタソースモデルを使用し、平均値及びジッタについて各バッファステージを正確に分析することを前提にする。特定の実施例は、最悪ケースとは異なり統計的であり、個々のステージのジッタを（STAツールでなされているように単にそれらを加算するのでなく）二乗和平方根として合成する。特定の実施例は、完全に対称的なツリーを生成する合成アルゴリズムを提案し、ツリーに関するステージ及びパスジッタは極めて効率的に算出可能である。
【００５５】
P,V,T変動の更に現実的なモデルが特定の実施例に導入される。V及びTのモデル化を改善する手法は説明済みである。プロセス変動は先ず組織的かつランダムに分割され、その後に近似的にモデル化される。
【００５６】
特定の実施例は或るFFを各Hツリーシンクに割り当てる。未割当シンク数が多ければ、かなりの配線リソース及びパワーが浪費される。或る手法はグループ化を行い、複数のFFを１つのシンクに割り当てるが、依然としてほとんど対称的なツリーを生成する。
【００５７】
特定の実施例では、対称的なツリーは、低度のスキュー及び効率的なジッタ分析には良好であるが、配線及び電力を消費するかもしれない。また、例えばRAM及び第三者のIPのような障害物が存在する場合には、完全に対称的なツリーを生成することは困難かもしれない。更にPVTX変動がたとえあったとしてもチップ上のデバイスの場所の関数であったならば（例えば、クロストークノイズ）、特定の実施例はそのような変動にも適合する。広範なPVTX変動モデルの下で一般的なクロックツリーについてのジッタ分析を効率的且つ正確に行う手法が使用される。
【００５８】
以上本発明を説明するために特定の実施例が使用されてきたが、添付の特許請求の範囲内で変更、置換、変形、代替又は修正の1以上を当業者は理解するであろう。本発明はそのような変更、置換、変形、代替及び修正の全てを包含する。
【００５９】
以下、本発明により教示される手段が例示的に列挙される。
【００６０】
（付記１）
クロックツリーにてジッタを計算する方法であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
を有することを特徴とする方法。
（付記２）
クロックツリー中の経路又は経路対に関するジッタを用いて、クロックツリーにおける長い経路及び短い経路のタイミング分析を実行するステップ
を更に有することを特徴とする付記１記載の方法。
【００６１】
（付記３）
クロックツリーの２以上のステージが近似的に電気的に互いに等価であり、
近似的に電気的に等価なステージのジッタを算出するステップが、近似的に電気的に等価なステージ１つのみにおけるジッタを算出するステップを有し、前記近似的に電気的に等価なステージ各々におけるジッタは、近似的な電気的な均衡の結果として、近似的に互いに等しい
を特徴とする付記１記載の方法。
【００６２】
（付記４）
算出されたジッタは、クロックツリーの全ての経路又は経路の全ての対に関する最悪ケースのジッタである
ことを特徴とする付記３記載の方法。
【００６３】
（付記５）
前記回路におけるクリティカルパスの第１数の第１リストを生成するスタティックタイミング分析（STA）を前記回路で実行するステップと、
前記STAの出力を利用して、前記クロックツリー中の経路又は経路対に関して算出されたジッタに従って、前記回路の１以上のフリップフロップにおける１以上のクロック到着時間を収集するステップと、
前記回路におけるクリティカルパスの前記第１数以下の第２数の第２リストを生成するステップと、
を更に有することを特徴とする付記１記載の方法。
【００６４】
（付記６）
回路のクロックツリーを合成する方法であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該方法は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
を有することを特徴とする方法。
（付記７）
回路のジッタを推定する方法であって、
前記回路中のジッタ源各々の表現を含む、回路の少なくとも一部分のモデルを生成するステップと、
前記モデルを利用して、前記回路におけるジッタを推定するステップと、
を有することを特徴とする方法。
【００６５】
（付記８）
実行用に媒体中にエンコードされ、クロックツリーにてジッタを計算するための論理装置であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
をコンピュータに実行させる論理装置。
（付記９）
クロックツリー中の経路又は経路対に関するジッタを用いて、クロックツリーにおける長い経路及び短い経路のタイミング分析を実行するステップ
を更に有することを特徴とする付記８記載の論理装置。
（付記１０）
クロックツリーの２以上のステージが近似的に電気的に互いに等価であり、
近似的に電気的に等価なステージのジッタを算出するステップが、近似的に電気的に等価なステージ１つのみにおけるジッタを算出するステップを有し、前記近似的に電気的に等価なステージ各々におけるジッタは、近似的な電気的な均衡の結果として、近似的に互いに等しい
を特徴とする付記７記載の論理装置。
（付記１１）
算出されたジッタは、クロックツリーの全ての経路又は経路の全ての対に関する最悪ケースのジッタである
ことを特徴とする付記１０記載の論理装置。
（付記１２）
前記回路におけるクリティカルパスの第１数の第１リストを生成するスタティックタイミング分析（STA）を前記回路で実行するステップと、
前記STAの出力を利用して、前記クロックツリー中の経路又は経路対に関して算出されたジッタに従って、前記回路の１以上のフリップフロップにおける１以上のクロック到着時間を収集するステップと、
前記回路におけるクリティカルパスの前記第１数以下の第２数の第２リストを生成するステップと、
を更に実行させることを特徴とする付記８記載の論理装置。
（付記１３）
実行用に媒体中にエンコードされる、回路のクロックツリーを合成するための論理装置であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該論理装置は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
をコンピュータに実行させる論理装置。
（付記１４）
実行用に媒体中にエンコードされる、回路のジッタを推定するための論理装置であって、
前記回路中のジッタ源各々の表現を含む、回路の少なくとも一部分のモデルを生成するステップと、
前記モデルを利用して、前記回路におけるジッタを推定するステップと、
をコンピュータに実行させる論理装置。
【００６６】
（付記１５）
クロックツリーにてジッタを計算するシステムであって、
クロックツリーを複数のステージに分割する手段と、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出する手段であって、前記モデルは前記回路のジッタのソース各々の表現を含むところの手段と、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成する手段と、
を有することを特徴とするシステム。
（付記１６）
回路のクロックツリーを合成するシステムであって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該システムは、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定する手段と、
前記クロックツリーのルーティング法を決定する手段と、
前記クロックツリー中のシンクに各フリップフロップを割り当てる手段であって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところの手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合する手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合する手段と、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入する手段と、
を有することを特徴とするシステム。
（付記１７）
回路のジッタを推定するシステムであって、
前記回路中のジッタ源各々の表現を含む、回路の少なくとも一部分のモデルを生成する手段と、
前記モデルを利用して、前記回路におけるジッタを推定する手段と、
を有することを特徴とするシステム。
【図面の簡単な説明】
【００６７】
【図１】クロストークを例示する図である。
【図２】データパス及びデータパスに関するクロックツリーを例示する図である。
【図３】クロックツリーステージジッタのシミュレーションモデルを例示する図である。
【図４】クロックツリーを例示する図である。
【図５】ジッタ変動のパラメータ例を示す図である。
【図６】ロングパス分析例の計算例を示す図である。
【図７】レース分析例の計算例を示す図である。
【図８】クロックツリー合成及び分析の方法例を示す図である。
【図９】クロックソースからフリップフロップ（FF）までのパスのステージ例を示す図である。
【図１０】完全な二部グラフを例示する図である。
【特許請求の範囲】
【請求項１】
クロックツリーにてジッタを計算する方法であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
を有することを特徴とする方法。
【請求項２】
回路のクロックツリーを合成する方法であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該方法は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
を有することを特徴とする方法。
【請求項３】
実行用に媒体中にエンコードされ、クロックツリーにてジッタを計算するための論理装置であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
をコンピュータに実行させる論理装置。
【請求項４】
クロックツリー中の経路又は経路対に関するジッタを用いて、クロックツリーにおける長い経路及び短い経路のタイミング分析を実行するステップ
を更に有することを特徴とする請求項３記載の論理装置。
【請求項５】
クロックツリーの２以上のステージが近似的に電気的に互いに等価であり、
近似的に電気的に等価なステージのジッタを算出するステップが、近似的に電気的に等価なステージ１つのみにおけるジッタを算出するステップを有し、前記近似的に電気的に等価なステージ各々におけるジッタは、近似的な電気的な均衡の結果として、近似的に互いに等しい
を特徴とする請求項４記載の論理装置。
【請求項６】
算出されたジッタは、クロックツリーの全ての経路又は経路の全ての対に関する最悪ケースのジッタである
ことを特徴とする請求項５記載の論理装置。
【請求項７】
前記回路におけるクリティカルパスの第１数の第１リストを生成するスタティックタイミング分析（STA）を前記回路で実行するステップと、
前記STAの出力を利用して、前記クロックツリー中の経路又は経路対に関して算出されたジッタに従って、前記回路の１以上のフリップフロップにおける１以上のクロック到着時間を収集するステップと、
前記回路におけるクリティカルパスの前記第１数以下の第２数の第２リストを生成するステップと、
を更に実行させることを特徴とする請求項３記載の論理装置。
【請求項８】
実行用に媒体中にエンコードされる、回路のクロックツリーを合成するための論理装置であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該論理装置は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
をコンピュータに実行させる論理装置。
【請求項９】
クロックツリーにてジッタを計算するシステムであって、
クロックツリーを複数のステージに分割する手段と、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出する手段であって、前記モデルは前記回路のジッタのソース各々の表現を含むところの手段と、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成する手段と、
を有することを特徴とするシステム。
【請求項１０】
回路のクロックツリーを合成するシステムであって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該システムは、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定する手段と、
前記クロックツリーのルーティング法を決定する手段と、
前記クロックツリー中のシンクに各フリップフロップを割り当てる手段であって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところの手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合する手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合する手段と、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入する手段と、
を有することを特徴とするシステム。
【請求項１】
クロックツリーにてジッタを計算する方法であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
を有することを特徴とする方法。
【請求項２】
回路のクロックツリーを合成する方法であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該方法は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
を有することを特徴とする方法。
【請求項３】
実行用に媒体中にエンコードされ、クロックツリーにてジッタを計算するための論理装置であって、
クロックツリーを複数のステージに分割するステップと、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出するステップであって、前記モデルは前記回路のジッタのソース各々の表現を含むところのステップと、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成するステップと、
をコンピュータに実行させる論理装置。
【請求項４】
クロックツリー中の経路又は経路対に関するジッタを用いて、クロックツリーにおける長い経路及び短い経路のタイミング分析を実行するステップ
を更に有することを特徴とする請求項３記載の論理装置。
【請求項５】
クロックツリーの２以上のステージが近似的に電気的に互いに等価であり、
近似的に電気的に等価なステージのジッタを算出するステップが、近似的に電気的に等価なステージ１つのみにおけるジッタを算出するステップを有し、前記近似的に電気的に等価なステージ各々におけるジッタは、近似的な電気的な均衡の結果として、近似的に互いに等しい
を特徴とする請求項４記載の論理装置。
【請求項６】
算出されたジッタは、クロックツリーの全ての経路又は経路の全ての対に関する最悪ケースのジッタである
ことを特徴とする請求項５記載の論理装置。
【請求項７】
前記回路におけるクリティカルパスの第１数の第１リストを生成するスタティックタイミング分析（STA）を前記回路で実行するステップと、
前記STAの出力を利用して、前記クロックツリー中の経路又は経路対に関して算出されたジッタに従って、前記回路の１以上のフリップフロップにおける１以上のクロック到着時間を収集するステップと、
前記回路におけるクリティカルパスの前記第１数以下の第２数の第２リストを生成するステップと、
を更に実行させることを特徴とする請求項３記載の論理装置。
【請求項８】
実行用に媒体中にエンコードされる、回路のクロックツリーを合成するための論理装置であって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該論理装置は、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定するステップと、
前記クロックツリーのルーティング法を決定するステップと、
前記クロックツリー中のシンクに各フリップフロップを割り当てるステップであって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところのステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合するステップと、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合するステップと、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入するステップと、
をコンピュータに実行させる論理装置。
【請求項９】
クロックツリーにてジッタを計算するシステムであって、
クロックツリーを複数のステージに分割する手段と、
クロックツリーに関連する回路の少なくとも一部分のモデルに従って、１以上のステージのジッタを算出する手段であって、前記モデルは前記回路のジッタのソース各々の表現を含むところの手段と、
クロックツリー中の経路又は経路対に関するジッタを計算するため、クロックツリー中の経路又は経路対の各ステージのジッタを互いに統計的に合成する手段と、
を有することを特徴とするシステム。
【請求項１０】
回路のクロックツリーを合成するシステムであって、前記クロックツリーは全て互いに近似的な電気的な等価性を示すステージを有し、当該システムは、
前記回路中の多数のフリップフロップから、前記クロックツリーのレベル数を判定する手段と、
前記クロックツリーのルーティング法を決定する手段と、
前記クロックツリー中のシンクに各フリップフロップを割り当てる手段であって、該割当は如何なるフリップフロップの１つでも該フリップフロップに割り当てられたシンクまでの最大距離を最小化するものであるところの手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられたシンクに各フリップフロップを結合する手段と、
最大距離に近似的に等しい長さのワイヤを用いて、フリップフロップに割り当てられていないクロックツリー中の如何なるシンクでも、フリップフロップピンキャパシタンスに対する擬似的なキャパシタンスに結合する手段と、
バッファ及びリピータによって駆動される容量負荷に依存して、クロックツリーのシンクからルートに至るクロックツリーの経路に従って、バッファ及びリピータをクロックツリーに挿入する手段と、
を有することを特徴とするシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００６−３４４２２２（Ｐ２００６−３４４２２２Ａ）
【公開日】平成１８年１２月２１日（２００６．１２．２１）
【国際特許分類】
【出願番号】特願２００６−１５７３７４（Ｐ２００６−１５７３７４）
【出願日】平成１８年６月６日（２００６．６．６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成１８年１２月２１日（２００６．１２．２１）
【国際特許分類】
【出願日】平成１８年６月６日（２００６．６．６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]