(57)【要約】【課題】計算量の多さを招くことなく不正確さを被ることのない、遅延許容量割り当てのためのシステムおよび方法を提供する。【解決手段】集積回路内のエッジについての遅延許容量割り当てを決定するための方法であって、集積回路設計においてタイミング・エッジおよび対応するタイミング経路を定義することを含む。１つまたは複数のエッジについて、以下が行なわれる。エッジにおいて開始するまたは終了するタイミング経路を特徴付ける最小／最大到着時刻および設計ゆとり（Ｓ，Ｔ）ペアの組が割り出される。１つまたは複数のタイミング経路が、関連する（Ｓ，Ｔ）ペアに基づいて切り取られる。切り取られていないタイミング経路に関する（Ｓ，Ｔ）ペアに基づいてエッジに関連する倍率が決定される。エッジに関連する倍率をエッジに関連する初期遅延によって乗算してエッジに関連する遅延許容量割り当てが生成される。【選択図】図７
2008262562.tif 000002
【特許請求の範囲】
【請求項１】
集積回路内のエッジについての遅延許容量割り当てを決定するための方法であって、
集積回路設計においてタイミング・エッジおよび対応するタイミング経路を定義し、
１つまたは複数のエッジについて、
前記エッジにおいて開始するまたは終了するタイミング経路を特徴付ける最小／最大到着時刻および設計ゆとり（Ｓ，Ｔ）ペアの組を割り出し、
１つまたは複数のタイミング経路を、関連する（Ｓ，Ｔ）ペアに基づいて切り取り、
切り取られていないタイミング経路に関する前記（Ｓ，Ｔ）ペアに基づいて前記エッジに関連する倍率を決定し、
前記エッジに関連する前記倍率を前記エッジに関連する初期遅延によって乗算して前記エッジに関連する遅延許容量割り当てを生成する、
ことを具備する方法。
【請求項２】
前記（Ｓ，Ｔ）ペアの組を決定することは、
前記エッジにおいて終了する後向きタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組を割り出し、
１つまたは複数の後向きタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取り、
前記エッジにおいて開始する前向きタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組を割り出し、
１つまたは複数の前向きタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取る、
ことを具備する、請求項１の方法。
【請求項３】
前記エッジに関連する倍率を決定することは、
前記後向きタイミング経路に関連する前記（Ｓ，Ｔ）ペアの１つと前記前向きタイミング経路に関連する前記（Ｓ，Ｔ）ペアの１つとの組合せの各々について、対応する倍率を決定し、
前記（Ｓ，Ｔ）ペアの組合せに対応する前記倍率の最小のものを前記エッジに関連する倍率として選択する、
ことを具備する、請求項１の方法。
【請求項４】
前記タイミング経路の選択された１つを切り取ることは、
前記選択されたタイミング経路が１つまたは複数の切り取り基準を満たすかを判断し、
前記切り取り基準が満たされている場合、前記選択されたタイミング経路を切り取る、
ことを具備する、請求項１の方法。
【請求項５】
前記集積回路のエッジに隣接する複数のノードの各々について、前記ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことをさらに具備する、請求項１の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広く集積回路の設計に関し、より詳しくは回路のタイミング制約を満たす遅延許容量を割り当てるためのシステムおよび方法に関する。
【背景技術】
【０００２】
デジタル装置（例えば集積回路）がより複雑になり、一層多くの電子部品をその中に含むことになったに連れ、より優れたツールがこれらの装置を設計するために必要とされる。特に、設計の問題が絶えず大きくなっていることに対処するだけのために、ツールの効率が改良されることが必要とされている。
【０００３】
デジタル装置を設計する課題の一部は、装置の回路についてのタイミングを決定することである。装置は、データおよび制御信号が、必要とされているときに利用可能になっている場合にのみ、適切に動作する。例えば、ある時刻ｔ１においてあるデータを受信する回路は、このデータを処理するとともに、対応する出力信号を、この信号が装置の別の部分で用いられることができるように時刻ｔ２までに生成しなければならない。よって、この回路に対して提案される設計は、この回路を通る経路に沿った遅延がｔ２−ｔ１（遅延許容量）以下であるという制約を満たさなければならない。装置の性能も、この遅延許容量を経路に沿った回路の副構成要素への割り当て方によって影響され得る。遅延許容量の割り当ては、集積回路設計の重要な部分である。あるタイミング経路上でのタイミングゆとり（利用可能な余剰時間）が、配線、セル、ネット等のこの経路の構成要素に分配される。これは、すべての時間制約（これは通常、たくさんある）が満たされるように行なわれる。
【０００４】
以前は、このことは、ある構成要素を通過する経路の各々についてのタイミングを計算するとともにこの構成要素についてのこのタイミングを最も厳しい時間制約に従ってスケーリングする（倍率をかける）ことを必要とするやり方を用いて達成されていた。このやり方を用いると、まず、回路内の各構成要素に初期遅延が割り当てられる。そして、各構成要素について、この構成要素をその中に含む全ての経路が割り出される。これらの経路の各々について、経路遅延（この経路内の全ての構成要素遅延の合計）およびこの経路についての総遅延許容量（最大遅延）を割り出すことが必要であった。これらの値から、倍率が決定される。この倍率は１以下であり、すなわち許容量が現在の経路遅延によって除される。よって、検討対象となっている構成要素は、自身に関連する複数の倍率（この構成要素を通過する遅延経路の各々に対して１つ）を有する。この構成要素について、最小の倍率が選択され、選択された倍率と構成要素に最初に割り当てられた遅延（または構成要素の遅延の最小値とのうちの大きい方）との積を得ることによって遅延許容量が決定される。
【０００５】
しかしながら、回路の複雑さが増すに連れて、このやり方は、ますます高価且つ非実用的になっている。なぜなら、回路内の経路の全てを評価することが求められるからである。このやり方の計算量が大きいことによって、最小の倍率の正確な算出値を概数で置き換える別のやり方を用いることにつながった。構成要素を通過する各経路についての倍率を計算するのではなく全ての経路についての要求される経路遅延の最小のものを経路の全てについての現在の経路遅延の最大のもので除することによって、倍率が概算される。検討中の構成要素を通過する相違する経路は、遅延が大きく相違し得るので、この概算は非常に不正確であり得る。例えば、全ての経路が既に自身のタイミング制約を満たしている（すなわち、現在の経路遅延が要求される経路遅延以下である）としても、経路内の全体の遅延が相違すれば、１未満の倍率を選択する結果となる（これは、１つまたは複数の経路が対応する時間制約に違反することを意味する）。
【０００６】
この出願の発明に関連する先行技術文献情報としては次のものがある。
【非特許文献１】H. Youssef、E. Shragowitz、Timing Constraints for Correct Performance、International Conference on Computer-Aided Design、１９９０年、ｐ．２４乃至２７
【発明の開示】
【発明が解決しようとする課題】
【０００７】
よって、１つ目のやり方の計算量の多さを招くことなく且つ２つ目のやり方の不正確さを被ることのない、遅延許容量割り当てのためのシステムおよび方法を提供することが望ましい。
【課題を解決するための手段】
【０００８】
本発明の一態様による方法は、集積回路内のエッジについての遅延許容量割り当てを決定するための方法であって、集積回路設計においてタイミング・エッジおよび対応するタイミング経路を定義し、１つまたは複数のエッジについて、前記エッジにおいて開始するまたは終了するタイミング経路を特徴付ける最小／最大到着時刻および設計ゆとり（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数のタイミング経路を、関連する（Ｓ，Ｔ）ペアに基づいて切り取り、切り取られていないタイミング経路に関する前記（Ｓ，Ｔ）ペアに基づいて前記エッジに関連する倍率を決定し、前記エッジに関連する前記倍率を前記エッジに関連する初期遅延によって乗算して前記エッジに関連する遅延許容量割り当てを生成する、ことを具備する。
【発明を実施するための最良の形態】
【０００９】
上に概説した１つ以上の問題は、本発明の様々な実施形態によって解決され得る。概して、本発明は、集積回路（IＣ）の改良された設計のためのシステムおよび方法を含み、より具体的には、回路の様々な部分について遅延許容量を決定することに関する。
【００１０】
一実施形態は、集積回路内での遅延許容量を割り当てるための方法を具備する。この方法は、集積回路設計においてタイミング・エッジおよび対応するタイミング経路を定義することを含み、相違するタイミング経路に関連する到着時刻およびタイミングゆとり（Ｓ，Ｔ）ペアに基づいて各エッジについての遅延許容量割り当てを決定することを含む。Ｓは、後向き経路に対して用いられると最小実現可能到着時刻を表し、前向き経路に対して用いられると最大許容到着時刻を表す。Ｔは、設計ゆとりを表す。設計ゆとりは、検討対象となっている後向きまたは前向き経路に関連する遅延におけるゆとり（最速で実現された場合に比べた余剰時間）である。幾つかのタイミング経路に関連する（Ｓ，Ｔ）ペアは廃棄され（すなわち、対応するタイミング経路が切り取られ）て、遅延許容量割り当て計算が簡略化される。各エッジについて、このエッジにおいて開始するまたは終了するタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組が決定される。（Ｓ，Ｔ）ペアの幾つかは、このエッジにおいて開始する前向き経路と関連しており、（Ｓ，Ｔ）ペアの幾つかは、このエッジにおいて終了する後向き経路に関連している。切り取られたタイミング経路に関連する（Ｓ，Ｔ）ペアは、この組の中に含まれない。次いで、倍率が前向き経路に関連する（Ｓ，Ｔ）ペアと後向き経路に関連する（Ｓ，Ｔ）ペアとの各組合せについて決定される。最小の倍率がエッジに関連する初期遅延によって乗算されて、このエッジに関連する遅延許容量割り当てが生成されることが可能である。
【００１１】
一実施形態では、（Ｓ，Ｔ）ペアは、検討対象となっているエッジからの前向きおよび後向きタイミング経路について決定される。（Ｓ，Ｔ）ペアおよび対応するタイミング経路は、前向きおよび後向きタイミング経路の両方の検査中に切り取られる。（Ｓ，Ｔ）ペアおよび対応するタイミング経路は、切り取り基準に従って切り取られる。選択された後向きタイミング経路については、後向きタイミング経路に関連する最小到着時刻（Ｓ）および選択された設計ゆとり（Ｔ）がそれぞれ第２の後向きタイミング経路に関連する最小到着時刻（Ｓ´）および設計ゆとり（Ｔ´）以下である場合、および積Ｓ×Ｔ´が積Ｓ´×Ｔ以下である場合、選択された後向きタイミング経路は切り取られる。反対に、前向きタイミング経路については、選択された前向きタイミング経路に関連する最大到着時刻（Ｓ）および設計ゆとり（Ｔ）がそれぞれ第２前向きタイミング経路に関連する最大到着時刻（Ｓ´）および設計ゆとり（Ｔ´）以上である場合、および積Ｓ×Ｔ´がＳ´×Ｔ以上である場合、選択された前向きタイミング経路は切り取られる。
【００１２】
一実施形態では、集積回路内の各ノードに関連する（Ｓ，Ｔ）ペアの組は、集積回路内のエッジについての倍率が決定される前に、決定されることが可能である。各後向きタイミング経路における最初のノードについては、Ｓは最初のノードにおける定義された到着時刻と等しく設定され、Ｔは０に等しく設定される。後向きタイミング経路内の後続のノードについては、Ｓは先行するノードのＳに介在するエッジの最小遅延を加えたものに等しく設定される。Ｔは先行するノードのＴに介在するエッジの現在の遅延を加えて介在するエッジの最小遅延を減じたものに等しく設定される。各前向きタイミング経路の最後のノードについては、Ｓは最後のノードにおける要求される到着時刻（これは規定されているタイミング制約である）に等しく設定され、Ｔは０に等しく設定される。前向きタイミング経路内の先行するノードについては、Ｓは、後続のノードのＳから介在するエッジの最小遅延を減じたものと等しく設定される。Ｔは、後続のノードのＴに介在するエッジの現在の遅延を加えて介在するエッジの最小遅延を減じたものに等しく設定される。
【００１３】
代替的な実施形態は、ソフトウェア・プログラム製品を具備する。この製品は、コンピュータ読み取り可能な媒体であって、この媒体は、上記の方法をコンピュータに実行させるプログラム命令を含んでいる。この方法は、集積回路を特徴付けるデータを回収および保存し、結果得られるデータ（例えば、遅延許容量割り当て）を保存することおよび使用者に提示することを含む。このコンピュータ読み取り可能媒体は、命令を保存するのに適切なあらゆる媒体であり得、ＣＤ、フロッピー（登録商標）・ディスク、フラッシュ・ドライブ等のようなリムーバブル媒体を含む。または、コンピュータ読み取り可能媒体は、永久保存媒体または装置、例としてコンピュータ内のメモリ・チップ、ディスク・ドライブ等からなる。その他の媒体も適切である。
【００１４】
多くのさらなる実施形態もまた可能である。
【００１５】
本発明のその他の目的および利点は、以下の詳細な説明を読み、添付の図面を参照することによって明らかとなり得る。
【００１６】
本発明は、様々な変形体および代替的な形態の対象であるが、本発明の具体的な実施形態が、図面および添付の詳細な説明において例として示される。図面および詳細な説明は、本発明を、説明されている具体的な実施形態に限定することを意図されていないことが理解されるべきである。代わりに、本開示は、添付の請求項によって定義されるような本発明の範疇に属する変形物、等価物、代替物の全てを網羅することが意図されている。
【００１７】
本発明の１つまたは複数の実施形態が以下に説明される。以下に記載のこれら実施形態および他のあらゆる実施形態は、例示的であって本発明を限定するのではなく説明用に示すものであることを意図されていることに留意されたい。
【００１８】
本明細書に記載されるように、本発明の様々な実施形態は、集積回路（ＩＣ）の至る所の様々な部分を介して伝送される信号のタイミングを管理および／または設計するための、ＩＣに関連するシステムおよび方法を具備する。より具体的には、本発明の実施形態は、ＩＣ内のタイミング経路に沿ったエッジへの遅延許容量割り当てを決定するのに必要な計算力を減じるためのシステムおよび方法を含む。
【００１９】
一実施形態では、回路デザインは、多数のタイミング経路を含んでいる。各タイミング経路は、様々な配線および回路構成要素を通過し、また、関連する制約、例として経路内の終端および／または中間ノードにおける最小または最大到着時刻、を有している。初期の設計において、遅延は、配線および回路構成要素または他のセル（これらの全ては、回路のノード・エッジ表現におけるエッジとして称される）の各々に割り当てられる。しかしながら、これらの遅延は、タイミング制約を満たさないかもしれないので、各エッジに割り当て可能な総タイミング経路遅延がどの程度であるかを割り出すために遅延許容量割り当てを行なうことが必要である。
【００２０】
ある特定のエッジへの遅延許容量割り当てを決定する際に、エッジを通過する全てのタイミング経路についての倍率を計算するよりむしろ、割り当てに影響を与えないと判定されることが可能な経路が切り取られる。ある経路が割り当てに影響するかの判定は、この経路が他の経路よりも大きなまたは小さな倍率であるという結果に基づく。ある経路が同じエッジを通過する他の経路よりも大きな倍率に帰結すると判定された場合、この経路は切り取られることが可能である（最小の倍率を見つけることが望まれるからである）。
【００２１】
本方法は、検討するエッジを選択することと、このエッジを通過する各経路を後向き経路、経路自身、前向き経路へと分解することと、を含む。エッジに先行する後向き経路の組が検査されて、どの後向き経路が（または対応する特性のいずれが）切り取られることが可能かまたは無視されることが可能かが決定される。同様に、エッジに後続する前向き経路の組が検査されてどの前向き経路が切り取られることが可能かが決定される。次いで、切り取られていない後向きおよび前向き経路の取り得る組合せが検査されて、どの組合せの倍率が最小になるかが割り出される。次いで、この倍率が用いられて、このエッジについての遅延許容量割り当てが決定される。より具体的には、遅延許容量割り当ては、特定された倍率とエッジに関連する初期遅延との積を得て、（この積が最小のあり得る遅延以下でない限り（この場合、最小遅延が遅延許容量として用いられる））この積をこのエッジについての遅延許容量割り当てとすることによって、決定される。
【００２２】
本発明の実施形態によって、従来のシステムに対する多くの利点が提供される。第１に、本システムおよび方法によって、所望の最小倍率を得るために単なる概算ではなく正確な解を決定するのに、従来の方法よりも実質的に少ない計算資源で済むと思われる。
【００２３】
本発明の様々な実施形態が以下に説明される。この説明は、主として、最小倍率およびその結果得る遅延許容量割り当てを決定するために経路切り取りを用いる１つの例示的な方法に焦点を当てている。倍率ｘが用いられて、エッジｅのそれを包含する経路ｐのタイミング要求を満たすタイミング遅延にスケーリングされる。この方法は、エッジの遅延許容量割り当てを決定する際にタイミング・エッジの全てが重要であるわけではないという認識から、その利点を引き出している。重要でない経路を除去することによって、計算の回数を劇的に減少することができる。
【００２４】
以下の説明において用いられる幾つかの文言、例として遅延、遅延許容量等は、時間に関わることが留意されるべきである。これらの文言についての値は、以下の幾つかの例において提示されるが、これらの値の単位は、説明に無関係であるので、特定されない。２つの終点を結ぶ回路素子の集合は、経路と称されることも留意されるべきである。回路素子は、配線、構成要素、配線および構成要素の集合等を含む。配線の集合はネットと称される。素子またはネットはセルとも称されることがある。回路は、ピンにおいて相互に接続され得る複数の素子へと分解され得る。これらの素子は、エッジによって表されるかエッジと称されることがあり、ピンまたは素子間の接続はノードによって表されるかノードと称されることがある。
【００２５】
本発明の例示的な実施形態を説明する前に、以前のやり方をより詳細に説明するのが有用であろう。図１ａ、図１ｂは、遅延許容量割り当ての例を示す図である。図１ａは、配線および構成要素の各々に関連する遅延の最初の組を伴った回路デザインを説明用に示している。図１ｂは、タイミング制約を満たすように変更された、配線および構成要素についての遅延を有する回路を説明用に示している。
【００２６】
各経路は、開始点および終端点を有する。経路は、様々な要素を具備する。経路は、例えば、経路が通過するノードまたは素子によって指し示され得る。経路を通過するための総時間は、この経路に沿って遭遇する遅延を加算することによって計算される。制約が終端において要求される到着時刻を指定しているとともに経路を通過するための時間が要求されるものを下回っているとき、タイミングには（正の）「ゆとり」が存在する。ゆとりが負の場合、タイミング制約が守られていない。
【００２７】
図１ａにおいて、１０の到着時刻（ＡＴ）が開始ピン１０１について指定されており、５０および３０の要求到着時刻（ＲＡＴ）が終了ピン１０４、１０５について指定されている。現在の経路到着時刻は、（開始到着時刻および後続の経路遅延を加算することによって算出されて）それぞれ６０、５０である。よって、この経路についてのタイミングゆとりは、それぞれ−１０、−２０である。ゆとりの両方の算出値が負なので、タイミング制約（例えば、要求到着時刻）は、この特定された遅延では満たされなかった。
【００２８】
このような場合、タイミング制約を満たすために、遅延が調整されねばならない。タイミング制約が満たされる遅延許容量が決定／特定される必要がある。例えば、遅延は、図１ｂに示されるように調整され得る。図１ｂにおいて、様々な副経路についての遅延許容量は、４、６、３０、１０である。両方の経路についてのタイミングゆとりは、今度は０であることに留意されたい。構成要素１２３についての遅延許容量は、今度は６であり、初期の１２から減少している。構成要素１２３は、再設計されるか、要求遅延許容量に合致する類似の構成要素で置換される必要がある。例えば、ある特定の構成要素についての新たな遅延許容量を実現するために、内部遅延が適切な装置が、構成要素の選択肢から選択されることが可能である。この置換構成要素は、代替的な構造、異なるワイヤ幅、他のデザイン要素を採用して、最初に選択された構成要素と異なる遅延を実現してもよい。
【００２９】
上記の例では、所与の回路についての遅延許容量をどのように決定するかが示されていない。遅延許容量を割り当てるのに用いられる最も良く知られた手法の１つは、１９９０年のInternational Conference on Computer-Aided Designでの"Timing Constraints for Correct Performance"において、H. YoussefとE. Shragowitzによって説明された。この文書は、以下、［ＹＳ９０］と称される。
【００３０】
文書［ＹＳ９０］は、経路に基づいた遅延のスケーリングを説明する。このことが、図１ａからのデータを用いて示され、図７においてグラフの形態で後に図式化される。図１ａにおいて、ピン１０１における到着時刻（ＡＴ）は１０であり、ピン１０１からピン１０４への第１経路についての経路遅延は和８＋１２＋３０＝５０である。そして、ピン１０４での到着時刻は、１０＋５０＝６０である。これは、ピン１０４での要求到着時刻（ＲＡＴ）である５０よりも１０大きい。すなわち、ピン１０１から１０４への経路についてのタイミングゆとりは、−１０である。要求到着時刻に合致する（または克服する）ために、この経路遅延は、１０、減少されねばならない。すなわち、この経路についてタイミングゆとりを非負にするために、経路遅延は要求される経路遅延以下でなければならない。この場合、経路遅延は、５０−１０＝４０以下でなければならない。現在の経路遅延に対する要求経路遅延の比は、４０／５０＝０．８である。この比は、「遅延倍率」と呼ばれる。経路に沿った各遅延が遅延倍率によってスケーリングされると、タイミングゆとりは０になる。０．８によって経路遅延８、１２、３０をこのようにスケーリングした結果は、それぞれ、６．４、９．６、２４である。すると、ピン１０１からピン１０４への第１経路の新たなタイミングゆとりは、５０−（１０＋６．４＋９．６＋２４）＝０である。次に、第２経路について検討される。
【００３１】
ピン１０１からピン１０５までの第２経路も検討されねばならない。第２経路の遅延倍率は、２０／４０＝０．５である。なぜなら、現在の経路遅延は、８＋１２＋２０＝４０であり、（タイミングゆとりを０にするための）要求経路遅延は、３０−１０＝２０であるからである。第２経路についての遅延倍率である０．５を用いると、経路遅延８、１２、２０は、それぞれ、４、６、１０になる。
【００３２】
ある経路の（副経路、ネット、エッジとして知られる）幾つかの部分について相違する遅延許容量が算出され得ることに留意されたい。例えば、第１、第２経路の（ピン１０１からピン１０２までに）共通部分が存在する。この共通部分についての遅延は、ピン１０４で終わる第１経路の遅延倍率を用いると、６．４であった。一方、ピン１０５で終わる第２経路の遅延倍率を用いると、４であった。両方の経路についてのタイミング制約を満足するために、最小の遅延が選択されねばならない。よって、ピン１０１からピン１０２への遅延許容量は、ｍｉｎ（６．４，４）＝４である。図１ｂにおいて、ピン１０１からピン１０２への遅延許容量は、このようにして算出された。同様に、ピン１０２からピン１０３（構成要素１２３）への遅延許容量は、ｍｉｎ（９．６，６）＝６であり、以下同様である。上記の説明を一般化すると、タイミング・エッジｅについての遅延許容量は、以下のように表現される。
【００３３】
Ｂ（ｅ）＝Ｄ（ｅ）×Ｘ（ｅ）                                                式１
【数１】
2008262562.tif 000003
【００３４】
ここで、Ｂ（ｅ）は、タイミング・エッジｅについての遅延許容量であり、Ｄ（ｅ）はタイミング・エッジｅの現在の遅延であり、Ｐ（ｅ）はタイミング・エッジを通過する経路の組であり、Ｓ（ｐ）は経路ｐの要求経路遅延であり、Ｔ（ｐ）は経路ｐの現在の経路遅延である。式１および式２は、以下に説明される式の特殊なケースである。
【００３５】
上の例で示されるように、［ＹＳ９０］の基本的なアイデアは、非常に単純である。しかしながら、実際には、利用するのが難しい。なぜなら、各タイミング・エッジを通過する全ての経路が、このタイミング・エッジについての遅延許容量を決定するために検討されねばならず、全てのタイミング・エッジが検討されねばならず、１つのタイミング・エッジを通過する経路の数は莫大であり得るからである。図２は、経路の数が論理ステージの数の指数関数である場合の例を説明用に示している。ピン２０１はノードＶ１に対応し、ピン２０２はノードＶ２に対応し、以下、同様である。構成要素２１１を通過するエッジは、Ｖ１（２０１）をＶ２（２０２）へと接続する。ピン２０１から２１０まで、ステージ１、２、３があり、各ステージは２つの副経路を有している。例えば、ステージ１は、副経路（Ｖ１、Ｖ２、Ｖ４）および副経路（Ｖ１、Ｖ３、Ｖ４）を有している。これらの各々はステージ２の２つの副経路に接続され、これらの各々はステージ３の２つの副経路に接続されている。２×２×２＝８個の取り得る組合せがある。この組み合わせのうちの１つ（Ｖ１、Ｖ２、Ｖ４、Ｖ５、Ｖ７、Ｖ８、Ｖ１０）が経路である。
【００３６】
この問題を克服するために、［ＹＳ９０］は、エッジについての最小の要求経路遅延および最大の現在の経路遅延を用いて式２を以下のように近似させることを提案した。
【数２】
2008262562.tif 000004
【００３７】
式３により定義される近似Ｘ´（ｅ）は、常に式２により定義されるＸ（ｅ）以下であることに留意されたい。よって、タイミング制約も、式３によって定義されるＸ´（ｅ）によって満足される。式３によって定義されるＸ´（ｅ）を計算するための時間計算量は、ネット／エッジの数に比例するが、経路の数には比例しない。よって、式３によって定義されるＸ´（ｅ）を算出することは、式２によって定義されるＸ（ｅ）を算出するよりも速い。しかしながら、式３によって得られる近似は、式２によって得られる値とかけ離れていることがある。例えば、図１において、式２によって定義されるＸ（ｅ）は、ピン１０１からピン１０２へのタイミング・エッジについてＸ（ｅ）＝０．５を与え、他方、式３によって定義されるＸ´（ｅ）は、悲観的な結果Ｘ´（ｅ）＝２０／５０＝０．４を与える。
【００３８】
以前の研究［ＹＳ９０］についての詳細および注釈を次に述べる。
【００３９】
Ｇ＝（Ｖ，Ｅ）が方向付けされた非繰り返しのグラフを指すとする。ここで、Ｖはタイミング・ノード（頂点）の組を表し、Ｅはタイミング・エッジの組を表す。タイミング・エッジｅは、ｅ＝（ｕ，ｖ）とする２つのタイミング・ノードの順序付けされたペアによって示される。ここで、ｕはエッジｅの「先頭」（開始ノード）であり、ｖはエッジｅの「末尾」（終端ノード）である。タイミング経路ｐは、ｐ＝（ｖ０，ｖ１，…，ｖｎ）のような一連のタイミング・ノードによって特定される。ここで、ｖ０，ｖ１，…，ｖｎは、タイミング・ノードである。ノードｖ０は、経路ｐの開始ノードであり、ｖｎは経路ｐの終端ノードであり、ｖ１，ｖ２，…，ｖｎ−１のようなその他のノードは、経路ｐの中間ノードである。１つの経路は、ｐ＝（ｅ０，ｅ１，…，ｅｎ）のような対応する一連のタイミング・エッジでも特定され得る。ここで、ｐは経路であり、ｅ０、ｅ１、…、ｅｎはタイミング・エッジである。
【００４０】
到着時刻および要求到着時刻のようなタイミング・パラメータはノードに割り当てられており、遅延時間はタイミング・エッジに割り当てられている。Ａ（ｖ）がノードｖでの到着時刻を指し、Ｒ（ｖ）がノードｖでの要求到着時刻を指し、Ｄ（ｅ）がエッジｅの遅延時間を指すとする。これらのタイミング・パラメータに加えて、エッジｅの最小遅延が導入され、Ｄｍｉｎ（ｅ）によって示される。最小遅延は、最も可能性の低い遅延である。例えば、タイミング・エッジｅが入力ピンから出力ピンまでのセル内部経路を表しているとすると、Ｄｍｉｎ（ｅ）は構成要素のリスト内の全ての論理的に同じ装置のうちで最小のセル内部遅延を表す。タイミング・エッジｅが配線を表しているとすると、Ｄｍｉｎ（ｅ）はワイヤ幅、ワイヤ間隔、接続層等の配線パラメータを調整することによって得られる全ての取り得る配線実現形態の中の最小の配線遅延を表す。Ｄ（ｅ）とＤｍｉｎ（ｅ）との間の差、すなわちＤ（ｅ）−Ｄｍｉｎ（ｅ）は、「設計ゆとり」を表す。設計ゆとりは、タイミング制約を満たすために遅延を調整する自由を意味する。タイミング・エッジ遅延への調整を提供するために、「パラメータ化された遅延」Ｄ（ｅ，ｘ）が導入される。これは、以下のように定義される。
【００４１】
Ｄ（ｅ，ｘ）＝Ｄｍｉｎ（ｅ）＋ｘ×（Ｄ（ｅ）−Ｄｍｉｎ（ｅ））                  式４
ここで、ｘは、調節可能なパラメータであって、以下において決定される遅延倍率を表す。ｘが非負であると仮定すると、Ｄ（ｅ，ｘ）がＤｍｉｎ（ｅ）未満たりえないことが保証される。後に示すように、Ｄ（ｅ，ｘ）は、ｘ＝１のとき、Ｄ（ｅ）に等しいことにも留意されたい。後に示されるように、Ｄ（ｅ，ｘ）は、ｘがＸ（ｅ）に等しいとき、遅延許容量Ｂ（ｅ）となる。
【００４２】
同様に、「パラメータ化された経路遅延」Ｄｐａｔｈ（ｐ，ｘ）が、以下のように導入される。
【数３】
2008262562.tif 000005
【００４３】
ここで、ｐ＝（ｖ０，ｖ１，…，Ｖｎ）はタイミング経路であり、Ｅ（ｐ）はタイミング経路ｐ上のタイミング・エッジの組である。なお、Ｅ（ｐ）＝｛ｅ１，ｅ２，…，ｅｎ｝であり、ｅ１＝（ｖ０，ｖ１）、ｅ２＝（ｖ１，ｖ２）、以下同様、である。Ｄｐａｔｈ（ｐ，ｘ）は、経路ｐ上のタイミング・エッジの「パラメータ化された遅延」の和である。なお、タイミング・ノードＶｎでの到着時刻は、Ａ（ｖ０）＋Ｄｐａｔｈ（ｐ，ｘ）である。この到着時刻は、タイミング・ノードＶｎでの要求到着時刻以下でなければならない。よって、経路ｐについてのタイミング制約は、以下の通りである。
【００４４】
Ｄｐａｔｈ（ｐ，ｘ）≦Ｒ（ｖｎ）−Ａ（ｖ０）                                    式６
式６によって、パラメータｘについての制約が提供される。式４、式５、式６を用いると、パラメータｘについての制約は、以下のようにはっきりと表現されることが可能である。
【数４】
2008262562.tif 000006
【００４５】
ここで、Ｓ（ｐ）は経路の最大の許容可能な付加的伝播遅延であり、Ｔ（ｐ）は、現在実現されている、エッジに対応する素子の「設計ゆとり」である。よって、式７は、経路のタイミング目標を満たすために（すなわち、経路の最大の許容可能な付加的伝播遅延以下となるために）現在の実現形態が達成せねばならない改善の程度をｘが表していることを意味している。（式２で導入されたＳ（ｐ）およびＴ（ｐ）は、全てのＤｍｉｎ（ｅ）が簡略化のために０であると仮定された特殊なケースであることに留意されたい。）今までの説明を要約すると、経路ｐ上の各タイミング・エッジｅの遅延が式７を満たすｘを有するＤ（ｅ，ｘ）以下である場合、経路ｐについてのタイミング制約が満足される。
【００４６】
次に、関数が、経路ではなくエッジの関数として表現される。Ｐ（ｅ）がタイミング・エッジｅを通る経路の組を指すものとする。Ｐ（ｅ）内の各タイミング経路ｐについて、パラメータｘについての制約は、式７によって与えられる。Ｐ（ｅ）内の全てのタイミング経路に対するタイミング制約を満たすために、最小のｘが選択されねばならない。Ｘ（ｅ）がタイミング・エッジｅについての最小のｘを指すものとする。式７を用いると、Ｘ（ｅ）は以下のように表現される。
【数５】
2008262562.tif 000007
【００４７】
エッジｅの遅延許容量は、Ｂ（ｅ）により示され、以下のように定義される。
【００４８】
Ｂ（ｅ）＝Ｄ（ｅ，Ｘ（ｅ））                                              式１１
式１０により定義されるＸ（ｅ）を算出するためには、全ての経路が検査されねばならないことに留意されたい。これは、経路の数が論理ステージの数の指数関数であり得る故に、問題である。この時間計算量の問題を回避するために、［ＹＳ９０］は、式１０により定義される解法に代えて以下の近似を提案した。
【数６】
2008262562.tif 000008
【００４９】
式１２によって定義されるＸ´（ｅ）は、常に、式１０によって定義されるＸ（ｅ）以下であることに留意されたい。このことは、式１２によって定義されるＸ´（ｅ）によって、タイミング制約も満足されることを意味する。式１２によって定義されるＸ´（ｅ）を算出するためのアルゴリズムの時間計算量は、ネット／エッジの数に比例する。なぜなら、同じアルゴリズムが、タイミングゆとりおよび到着時刻を算出するために、Ｓ（ｐ）およびＴ（ｐ）に適用されることが可能であり、またこれらのアルゴリズムはネット／エッジの数に関して線形の時間計算量を有していることが良く知られているからである。式１２にまつわる問題は、この式によって、上記のように悲観的な結果が多くの場合、もたらされることである。（過剰に保守的な）近似に頼ることのないタイミング値を、効率のよい計算での割り出し方を提供することが望ましい。
【００５０】
この［ＹＳ９０］による近似の問題、および全ての経路を計算する方法の計算上の負担を緩和するために、より効率的な方法が（式２により定義されるＸ（ｅ）を割り出すために）必要である。解を算出するために全ての経路が必要なわけではないということに基づいた方法が次に説明される。
【００５１】
最終的な解に貢献しない経路は検討される必要がない。これらを切り取る、すなわち関連する計算から排除する方法は、付加されたオーバーヘッドのいずれよりも「貯蓄」が大きければ、より効率的であることが分かるであろう。このような方法が、以下に説明され。実際に、この方法は、経路の切り取りについてのオーバーヘッドが付加されたとしても、経路を切り取らないアルゴリズムよりも速い。本発明の様々な実施形態によって、本発明の当業者にとって明らかな他の多くの利点が提供される。
【００５２】
式１２によって定義される近似のＸ´（ｅ）を算出する代わりに、式１０によって定義されるＸ（ｅ）を算出するより効率的な方法が用いられることが可能である。上で触れた時間計算量の問題を克服するために、経路を切り取る手法が用いられる。要求経路遅延Ｓ（ｐ）および現在の経路遅延Ｔ（ｐ）を計算するために、前向きおよび後向き（副）経路が各タイミング・エッジから追跡される。経路の追跡の間、Ｓ（ｐ）およびＴ（ｐ）の一部が、対応する副経路について算出される。式２２および式２５の条件が検査されて、その一部が算出されたＳ（ｐ）およびＴ（ｐ）が必要か否かが判断される。これらが必要ではないと判断されると、これらは除去され、動作時間が減少する。
【００５３】
図３は、一実施形態に従った方法を説明用に示すフローチャートである。集積回路のエッジによる表現が作製され（３１０）、タイミング遅延が初期デザインに従って割り当てられる（３２０）。次いで、エッジは、あらゆる設計タイミング制約を満足するタイミング遅延許容量を決定するために処理される（３３０乃至３６０）。次いで、各エッジについて、現在のエッジ（これは現在のエッジをその中に含んだ経路を構成する）の後向きの副経路（３４０）および前向きの副経路（３５０）が追跡されてタイミング決定的経路に関連する遅延が割り出される。
【００５４】
現在のエッジに先行する（後向きの）副経路を構成するエッジ（ノード）が、先頭再帰関数によって処理される（３４０）。これらは追跡されて、この副経路に関連する遅延が、経路の基点ノードから累積され且つ切り取りが行なわれる。この切り取りによって、重要でない経路に関連する情報が除去され、ひいては計算の総量が減少する。同様に、現在のエッジに続く（前向きの）副経路を構成するノード／エッジが、先頭再帰関数によって処理される（３５０）。これらは追跡され、副経路エッジに関連する遅延が経路の終端ノードから累積され、また切り取りが行なわれる。これを経て、最小の遅延乗数が選択されること、この遅延乗数を用いて現在のエッジについての遅延許容量が決定されることが可能である。各エッジについてのゆとりが割り出されて、承認するか集積回路の再設計が必要であるかが評価される。
【００５５】
Ｘ（ｅ）についての別の式
Ｘ（ｅ）についての別の式が導かれ得る。Ｐ（ｅ）内の各経路ｐは、以下の３つの部分へと分解可能である。
【００５６】
（１）ｐＢ：経路ｐの開始ノードからエッジｅの先頭までの経路
（２）ｅ：エッジｅ自身
（３）ｐＦ：エッジｅの末尾から経路ｐの終端ノードまでの経路
ここで、ｐ＝（ｖ０，ｖ１，…，Ｖｉ，Ｖｉ＋１，・・・Ｖｎ）、ｅ＝（ｖｉ，ｖｉ＋１）、ｐＢ＝（ｖ０，ｖ１，…、Ｖｉ）である。以下では、ｐＢはノードＶｉへの「後向き経路」と呼ばれ、ｐＦはノードＶｉ＋１からの「前向き経路」と呼ばれる。経路をこのように分割することを用いて、式８により定義されるＳ（ｐ）および式９により定義されるＴ（ｐ）も以下のように分割される。
【数７】
2008262562.tif 000009
【００５７】
ここで、ＳＢ（ｐＢ）は経路ｐＢの終端ノード（ｖｉ）での最小到着時刻とみなされ、ＳＦ（ｐＦ）は経路ｐＦの開始ノード（Ｖｉ＋１）での最大要求到着時刻とみなされ、ＴＢ（ｐＢ）は経路ｐＢに沿った「設計ゆとり」とみなされ、ＴＦ（ｐＦ）は経路ｐＦに沿った「設計ゆとり」とみなされる。
【００５８】
式１３および式１６を用いて、式１０は、以下のように表現されることが可能である。
【数８】
2008262562.tif 000010
【００５９】
ここで、ＰＢ（ｅ）はエッジｅの先頭への後向き経路の組であり、ＰＦ（ｅ）はエッジｅの末尾からの前向き経路の組である。式１９、Ｘ（ｅ）の計算は、前向きおよび後向き経路の中の最小値を探すことに等しい。よって、後向きまたは前向き経路は、これらが最小の値を提供しない場合は、除去されて構わない。
【００６０】
経路を切り取るための条件
後向き経路が除去されて構わない条件を見つけるために、２つの後向き経路ｐＢとｐＢ´とを比較してみる。式１９内の「ｍｉｎ」演算故に、ｐＢ´は、以下の不等式が各前向き経路ｐＦについて、およびある後向き経路ｐＢについて成り立っているとすると、最小値をもたらさない。
【数９】
2008262562.tif 000011
【００６１】
式２０は、以下のように簡略化されることが可能である。
【数１０】
2008262562.tif 000012
【００６２】
ここで、ａ＝ＳＦ（ｐＦ）−Ｄｍｉｎ（ｅ）であり、ｂ＝（Ｄ（ｅ）−Ｄｍｉｎ（ｅ））＋ＴＦ（ｐＦ）である。設計ゆとりｂは、常に、非負であることに留意されたい。なぜなら、ある実現形態は、最も良くても、最小の遅延実現形態だからである。ａもまた非負であると想定される。
【００６３】
これは、以下のように説明される。もしａが負であるとすると、エッジｅの末尾における要求到着時刻は、式１５によれば、早くも負になってしまう。よって、ｐＦを副経路として含むあらゆる経路は、この経路上の各タイミング・エッジについて最小遅延Ｄｍｉｎ（ｅ）であったとしても、常にゆとりが負である。換言すれば、ａが負であると、この経路は、最小の遅延で実現したとしてもタイミング目標を達成できず、また、経路（この経路を基礎とする回路）が設計し直される必要がある。このような状況は、目印を付されている必要がある。残りの説明が複雑になることを回避するために、これらの経路を知らせるための例外的な手続は省略され、本説明はより根本的な方法に焦点を合わせる。よって、ａは、非負であるとみなされる。
【００６４】
式２１が、非負の数ａおよびｂについて成り立つとすると、ｐＢ´は、式１９の右辺に対して最小の値を付与しないので、除去されても構わない。式２１が非負の数ａおよびｂについて成り立つための十分条件は、以下の通りである。
【００６５】
ＳＢ（ｐＢ´）≦ＳＢ（ｐＢ）、ＴＢ（ｐＢ´）≦ＴＢ（ｐＢ）、
ＳＢ（ｐＢ´）×ＴＢ（ｐＢ）≦ＳＢ（ｐＢ）×ＴＢ（ｐＢ´）                      式２２
同様に、ＰＦ（ｅ）内の２つの経路ｐＦとｐＦ´とが比較されると、ｐＦ´が削除されて構わない条件は、以下の通りである。
【数１１】
2008262562.tif 000013
【００６６】
式２３は、以下のように簡略化可能である。
【数１２】
2008262562.tif 000014
【００６７】
ここで、ａ＝Ｄｍｉｎ（ｅ）＋ＳＢ（ｐＢ）であり、ｂ＝ＴＢ（ｐＢ）＋（Ｄ（ｅ）−Ｄｍｉｎ（ｅ））である。ａおよびｂは、非負であることに留意されたい。式２４があらゆる非負の数ａおよびｂについて成り立つとすると、ｐＦ´は、式１９の右辺に対して最小の値を付与しないので、削除されて構わない。式２４があらゆる非負の数ａおよびｂについて成り立つための十分条件は、以下の通りである。
【００６８】
ＳＦ（ｐＦ）≦ＳＦ（ｐＦ´）、ＴＦ（ｐＦ）≦ＴＦ（ｐＦ´）、
ＳＦ（ｐＦ）×ＴＦ（ｐＦ´）≦ＳＦ（ｐＦ´）×ＴＦ（ｐＦ）                      式２５
式２２および式２５は、この実施形態において経路切り取り手法を実行するために用いられる条件である（そして、遅延許容量計算において時間計算量が減少する結果になる）。例えば、後向き経路追跡の間、ＰＢ（ｅ）が、各タイミング・エッジについて算出される。ＰＢ（ｅ）が算出されているとき、ＰＦ（ｅ）は未知であるが、このことは重要でない。なぜなら、ＰＦ（ｅ）は、ＰＢ（ｅ）およびＰＢ（ｅ）´にとって、これらが比較されるとき、共通だからである。前向き経路についての情報、式１９内のＳＦ（ｐＦ）−Ｄｍｉｎ（ｅ）および（Ｄ（ｅ）−Ｄｍｉｎ（ｅ））＋ＴＦ（ｐＦ）は、非負である。この情報に基づいて、ＰＢ（ｅ）内のＰＢ´は、式２２を満たす場合、削除されて構わない。このようなＰＢ´が削除されて構わない理由は、前向き経路の値が、非負である限りどんな値であったとしても、このようなＰＢ´が式１９内で最小値を付与することがないからである。この経路切り取り手法によって、ＰＢ（ｅ）内の要素の数が減少し、実行されるべき演算の数が減少する。同様に、ＰＦ（ｅ）についての経路切り取りによって、演算の数が減少する。全てのＰＢ（ｅ）は、ＰＦ（ｅ）と独立して比較され、その逆も同様であるので、計算の数は、後向きおよび前向き経路の総数に線形に比例している。この数は、タイミング・エッジを通過する経路の総数より少ない。タイミング・エッジを通過する経路の総数は、後向き経路の数と前向き経路の数との積である。経路切り取り手法のさらなる詳細は、後に説明される。
【００６９】
経路切り取りを用いたＸ（ｅ）を算出するためのアルゴリズム
経路切り取りを用いたＸ（ｅ）の算出について、ソフトウェアによる実現として次に説明される。図４、図５、図６は、一実施形態に従った擬似コードを含んでいる。
【００７０】
図４の行［４００］において、手続「Backward」が、各タイミング・ノードについて呼び出される。手続Backwardによって、組Ｂｓｅｔ（ｖ）が作製される。組Ｂｓｅｔ（ｖ）は、Ｘ（ｅ）に寄与するペア（ＳＢ（ｐＢ），ＴＢ（ｐＢ））の組である。Ｘ（ｅ）に寄与しない経路は、行［４００］の後、組Ｂｓｅｔ（ｖ）から削除される。手続Backwardは、図５に示されている。
【００７１】
同様に、図４の行［４０１］で呼び出される手続「Forward」によって、組Ｆｓｅｔ（ｖ）が作製される。組Ｆｓｅｔ（ｖ）は、Ｘ（ｅ）に寄与するペア（ＳＦ（ｐＦ），ＴＦ（ｐＦ））の組である。Ｘ（ｅ）に寄与しない経路は、行［４０１］の後、組Ｆｓｅｔ（ｖ）から削除される。手続Forwardは、図６に示されている。
【００７２】
行［４０４］は、２つの場合の一方への分岐である。一方は、Ｄ（ｅ）がＤｍｉｎ（ｅ）に等しい場合であり（行［４０４］から行［４０７］まで）、他方は、Ｄ（ｅ）がＤｍｉｎ（ｅ）より大きい場合である（行［４０８］から行［４２１］まで）。Ｄ（ｅ）がＤｍｉｎ（ｅ）に等しい場合、遅延許容量Ｂ（ｅ）は式４および式１１に従って、Ｘ（ｅ）の値によらず、Ｄｍｉｎ（ｅ）に常に等しい。よって、Ｘ（ｅ）の算出は省略されることが可能であって、Ｘ（ｅ）は単に１に設定される（行［４０６］）。行［４１０］から行［４２０］までは、式１９の「ｍｉｎ」の算出を表している。
【００７３】
図５は、組Ｂｓｅｔ（ｖ）を得るために用いられる手続Backwardを示している。Ｂｓｅｔ（ｖ）は、式１９を用いてＸ（ｅ）に寄与し得るペア（ＳＢ（ｐＢ），ＳＦ（ｐＢ））の組である。Ｘ（ｅ）に寄与しない経路は、後に詳述するように、経路切り取り処理（行［５１３］乃至［５２７］）によって組Ｂｓｅｔ（ｖ）から削除される。
【００７４】
各ノードは、１回のみ処理されればよい。図５内の行［５００］は、ノードが１回を超えて処理されることを防止する。
【００７５】
行［５０１］は、組Ｂｓｅｔ（ｖ）を初期化する。ノードｖが経路の開始ノードである場合、ノードｖへの後向き経路ｐＢは、ｖ自体であって、何らのエッジも有さない。この場合、ＳＢ（ｐＢ）は、式１４に従ってノードｖでの到着時刻に等しく、ＴＢ（ｐＢ）は、式１７に従って０である。ノードｖが経路の開始ノードでない場合、ノードｖへの進入エッジが存在し、行［５０２］乃至行［５１２］が実行されてＢｓｅｔ（ｖ）が算出される。この場合、Ｂｓｅｔ（ｖ）は、各進入エッジの先頭ｕのＢｓｅｔ（ｕ）に基づいて作製される。
【００７６】
行［５０５］において、進入エッジｅの先頭のＢｓｅｔ（ｕ）が作製される。手続Backwardは、この手続のために再帰的に呼び出される。
【００７７】
行［５０６］乃至［５１１］は、ｕ（各進入エッジの先頭）のＢｓｅｔ（ｕ）に基づいて、ＳＢ（ｐＢ）およびＴＢ（ｐＢ）を算出する。ノードｕへの後向き経路からの情報はＢｓｅｔ（ｕ）内に既に保存されているので、ノードｕとノードｖとの間の遅延情報、すなわち、エッジｅが付加される（行［５０８］、［５０９］）。この計算は、式１４および式１７に基づいている。
【００７８】
行［５１３］乃至［５２７］は、非常に重要である。これらのステップによって、Ｘ（ｅ）に寄与しない経路が切り取られる。経路を切り取るための条件は、式２２によって与えられる。これらの経路切り取りステップ故に、組Ｂｓｅｔ（ｖ）内の要素の数が減少可能である。結果、行［５０６］から［５１２］までのループの繰り返しの回数が減少可能である。さらに、行［４１３］から行［４２０］までのループの必要な処理が減少可能である。このことは、全ての経路が組Ｂｓｅｔ（ｖ）内に含まれている場合と比べて、実行時間が減少可能であることを意味する。
【００７９】
図６に示す手続「Forward」の説明は、手続Backwardと同様であるため、省略される。
【００８０】
次に、２つの例が詳しく説明される。図７は、図１ａに示される回路をグラフで表現したものである。丸は、タイミング・ノードを表し、また（頂点を意味する）接頭辞「Ｖ」を付されたラベルを有している。矢印は、タイミング・エッジを表し、また接頭辞「Ｅ」を付されたラベルを有している。タイミング・ノードＶ１（７０１）は図１のピン１０１に対応し、タイミング・ノードＶ２（７０２）はピン１０２に対応し、以下、同様である。ノードＶ１からノードＶ２へのエッジＥ１２（７１２）は図１の配線１１２に対応し、ノードＶ２からノードＶ３へのエッジＥ２３（７２３）は構成要素１２３に対応し、以下、同様である。タイミング遅延「Ｄ（ｅ）」およびタイミング許容量「Ｂ（ｅ）」が、エッジおよび経路について特定される。タイミングゆとりも、経路について特定される。例えば、経路＝（Ｖ１，Ｖ２，Ｖ３，Ｖ４）は、図７ａにおいて、６０の初期遅延およびー１０のゆとりを有しており、図７ｂでは許容量＝４４およびゆとり＝＋６になる。
【００８１】
例１
図７は、一実施形態に従った例の遅延「Ｄ（ｅ）」および遅延許容量Ｂ（ｅ）を含んでいる。この例では、各タイミング・エッジｅについて、Ｄｍｉｎ（ｅ）＝０であるとされる。
【００８２】
まず、処理Backwardが、各タイミング・ノードについて実行される（行［４００］）。ｖ＝Ｖ１のとき、進入エッジはない。よって、Ｂｓｅｔ（Ｖ１）＝｛（１０，０）｝である。ｖ＝Ｖ２のとき、Ｂｓｅｔ（Ｖ２）の初期値は、進入エッジｅ＝（Ｖ１，Ｖ２）＝Ｅ１２が存在するので、０である。ｕがこのエッジの先頭（これはノードＶ１である）を指すとする（行［５０４］）。Backward（Ｖ１）が実行される（行［５０５］）。ノードＶ１は検討済みなので、何もせずに単に戻る（行［５００］）。（ＳＢ，ＴＢ）＝（１０，０）にセットされる（行［５０６］）。これは、Ｂｓｅｔ（Ｖ１）内の唯一の要素である。Ｄｍｉｎ（ｅ）＝０であるので、ＳＢは更新されず、１０に留まる（行［５０８］）。Ｄ（Ｅ１２）＝８であるので、ＴＦは０＋（８−０）＝８になる（行［５０９］）。Ｂｓｅｔ（Ｖ２）は、今では、｛（１０，８）｝である（行［５１０］）。Ｂｓｅｔ（Ｖ２）内には１つの要素があるのみなので、行［５１３］からは行［５２７］までは何も行なわれない。同様に、Backward手続によって、Ｂｓｅｔ（Ｖ３）＝｛（１０，２０）｝、Ｂｓｅｔ（Ｖ４）＝｛（１０，５０）｝、Ｂｓｅｔ（Ｖ５）＝｛（１０，４０）｝が与えられる。
【００８３】
第２に、処理Forwardが、各タイミング・ノードについて実行される（行［４０１］）。この結果は、Ｆｓｅｔ（Ｖ１）＝｛（３０，４０）｝、Ｆｓｅｔ（Ｖ２）＝｛（３０，３２）｝、Ｆｓｅｔ（Ｖ３）＝｛（３０，２０）｝、Ｆｓｅｔ（Ｖ４）＝｛（５０，０）｝、Ｆｓｅｔ（Ｖ５）＝｛（３０，０）｝である。Ｆｓｅｔ（Ｖ３）が得られたとき、タイミング処理（行［６１３］乃至行［６２７］）が実行される。行［６１３］の直前では、Ｆｓｅｔ（Ｖ３）は｛（３０，２０）、（５０，３０）｝であった。３０≦５０、２０≦３０、３０−３０≦５０−２０であるので、行［６２４］において（５０，３０）はＦｓｅｔ（Ｖ３）から削除される。
【００８４】
第３に、Ｘ（ｅ）が、各タイミング・エッジについて算出される（行［４０２］から行［４２２］まで）。ｅ＝（Ｖ１，Ｖ２）＝Ｅ１２のとき、Ｘ（Ｅ１２）は（３０−０−１０）／（０＋８−０＋３２）＝０．５に等しい（行［４１７］および行［４１８］）。同様に、Ｘ（Ｅ２３）＝０．５、Ｘ（Ｅ３４）＝０．８、Ｘ（Ｅ３５）＝０．５である。
【００８５】
例２
【数１３】
2008262562.tif 000015
【００８６】
切り取りの計算に関するオーバーヘッドは、エッジがさらに検査されると（この情報が保存されている場合）さらに償却される。例えば、エッジｅ＝（Ｖ１１，Ｖ０４）を検討するとき、末尾ノードＶ０４からの前向き追跡は、実行済みである。
【００８７】
実行時間の解析
以下は、一実施形態に従った、実行時間の例示的な解析である。最悪の場合、この発明の時間計算量は、各タイミング・エッジについてＯ（Ｎ２）である。ここで、Ｎは、タイミング・エッジを通る経路の数である。一方、経路切り取り無しのアルゴリズムの時間計算量は、各タイミング・エッジについてＯ（Ｎ）であり、［ＹＳ９０］ではＯ（１）である。最悪の時間計算量は、経路切り取り（図５内の行［５１３］乃至行［５２７］および図６内の行［６１３］乃至行［６２７］）に由来する。最悪のケースでは、どの経路も切り取られず、また、Ｂｓｅｔ（ｖ）またはＦｓｅｔ（ｕ）内の要素の数は、経路の数、すなわちＮに等しいことがある。図５内の行［５１３］乃至行［５２７］および図６内の行［６１３］乃至行［６２７］は組Ｂｓｅｔ（ｖ）またはＦｓｅｔ（ｕ）内の全てのペアを通るループである。組Ｂｓｅｔ（ｖ）またはＦｓｅｔ（ｕ）内のペアの数は、Ｎ個の要素のうちの２つの要素の組み合わせの数、すなわちＮ（Ｎ−１）／２に等しい。よって、これらのループの時間計算量は、Ｏ（Ｎ２）であり、これは、経路切り取りステップ無しのアルゴリズムよりも遅い。
【００８８】
しかしながら、実際には、実現されたり実際の設計に適用されたりすると、経路切り取りを採用する方法は、経路切り取り無しのアルゴリズムよりもずっと高速であった。その理由が、以下に説明される。
【００８９】
まず、最悪のケースを検討する。最悪のケースでは、経路切り取りステップによっていかなる経路も削除されない。これは、経路切り取りステップによってＢｓｅｔ（ｖ）およびＦｓｅｔ（ｕ）内のいかなる要素も削除されないときに発生する。Ｆｓｅｔ（ｕ）内にＮ個の要素があるとする。この数は、最悪のケースにおける経路の数に等しい。経路切り取りステップによってＦｓｅｔ（ｕ）内のいかなる要素も削除されない可能性は、（１−ｐ）Ｎ（Ｎ−１）／２である。ここで、ｐは、所与の２つの要素のうちの一方が検査式２５によって切り取られる可能性である。よって、１−ｐは、所与の２つの要素が切り取られずに残る可能性である。そして、（１−ｐ）Ｎ（Ｎ−１）／２は、Ｆｓｅｔ（ｕ）内のいかなる要素も切り取られない可能性である。これは、Ｆｓｅｔ（ｕ）内のペアの数がＮ（Ｎ−１）／２であり、各ペアが切り取られない可能性が１−ｐであるためである。ｐの値は０．２５である。これは、以下のように算出される。あるペア（ＳＦ（ｐＦ），ＴＦ（ｐＦ））および（ＳＦ（ｐＦ´），ＴＦ（ｐＦ´））について式２５が成り立つ条件は、（ＳＦ（ｐＦ），ＴＦ（ｐＦ））および（ＳＦ（ｐＦ´），ＴＦ（ｐＦ´））がランダムに生成されるならば、０．１２５である。これは、式２５が３つの不等式からなっており、各々が成り立つ可能性は１／２であり、１／２×１／２×１／２＝１／８＝０．１２５であるからである。式２５は、（ＳＦ（ｐＦ´），ＴＦ（ｐＦ´））が（ＳＦ（ｐＦ），ＴＦ（ｐＦ））によって削除される場合を表している。（ＳＦ（ｐＦ），ＴＦ（ｐＦ））が（ＳＦ（ｐＦ´），ＴＦ（ｐＦ´））によって削除されることもあり得、その可能性はやはり０．１２５である。よって、（ＳＦ（ｐＦ），ＴＦ（ｐＦ））または（ＳＦ（ｐＦ´），ＴＦ（ｐＦ´））が削除される全可能性は、ｐ＝０．１２５＋０．１２５＝０．２５である。タイミング・ノードｕが３２ビットのマルチプレクサに選択信号を送信する経路上にある場合、ノードｕを通過する経路の数は少なくとも３２である。この場合、Ｆｓｅｔ（ｕ）内のいかなるペアも削除されない最悪のケースの可能性は、多くても（１−ｐ）Ｎ（Ｎ−１）／２＝（１−０．２５）３２（３２−１）／２＝１．０７×１０−６２である。Ｎが大きくなるほど、最悪のケースの可能性は小さくなる。Ｎが十分に大きい場合、最悪のケースの可能性は無視可能である。最悪のケースは起こらないとしても、経路切り取り後に多数の経路がまだ残っている。残存する経路の数の確率分布が次に説明される。
【００９０】
数的なシミュレーションを考えてみる。残存経路の数の確率分布が、Ｎ＝１０、５０、１００について、それぞれ図９、図１０、図１１に示されている。ここで、Ｎは、経路切り取り前の経路の数である。Ｎ個のペア（ＳＦ（ｐＦ），ＴＦ（ｐＦ））がランダムに生成されてＦｓｅｔ（ｕ）が形成され、経路切り取りが行なわれ、残存（非切り取り）経路が計数される。これらのステップは、Ｎ＝１０、５０、１００の各々について１０００回実行されて残存経路の数の確率分布が得られる。図９は、Ｎ＝１０についての結果を示している。図９によれば、１０個のうち４または５個のペアが経路切り取り後に残存する可能性が最も高い。図１０は、Ｎ＝５０についての結果を示している。残存する経路は平均すると８個であり、２０個を超えない。図１１は、Ｎ＝１００についての結果を示している。残存する経路の数は平均すると９個であり、２０個を超えない。これらの実験から、それほど多くの経路が経路切り取り後に残存せず、また残存経路の数はＮが増えてもそれほど増えないと結論できる。そうであるなら、Ｎと残存経路の数との間の関係は何であろうか。
【００９１】
図１２は、元の経路の数（Ｎ）と経路切り取りステップ後の残存経路の平均数との間の関係を示している。１から２００の範囲のＮの各々について、（ＳＦ（ｐＦ），ＴＦ（ｐＦ））のＮ個のペアがランダムに生成されて、Ｆｓｅｔ（ｕ）が形成され、経路切り取りが適用されて、残存（非切り取り）経路が計数される。これらのステップは、１乃至２００の範囲のＮの各々について１００回繰り返されて、各Ｎについての残存経路の平均数が得られた。図１２によれば、対数関数が良く当てはまり、残存経路の平均数はＮが２００に達する場合でさえ、１１を超えない。
【００９２】
上記の実験、特に図１２によれば、経路切り取りを用いる本方法の平均時間計算量は、Ｏ（ｌｏｇＮ）２）である（ここで、Ｎは、タイミング・エッジを通過する経路の数である）と結論できる。なぜなら、別の先行するタイミング・ノードにおいて経路切り取りステップが実行済みである故にＢｓｅｔ（ｖ）またはＦｓｅｔ（ｕ）内の要素の数がＯ（ｌｏｇＮ）のオーダーまで切り取られ済みであるからである。よって、ループ（図５内の行［５１３］乃至［５２７］、図６内の行［６１３］乃至行［６２７］、図４内の行［４１３］乃至行［４２０］）の繰り返し回数は、Ｏ（（ｌｏｇＮ）２）のオーダーである。この時間計算量は、経路切り取り無しでＸ(ｅ）を算出するためのアルゴリズムの時間計算量Ｏ（Ｎ）よりずっと小さい。
【００９３】
直感的に言えば、タイミング・エッジを通過する多くの経路があり得るものの、１つの決定的な経路がこのエッジについての時間許容量を決定する。切り取り処理によって、これらの決定的な経路が選別され、そうするために必要な計算の総数が減少する。
【００９４】
この方法は、遅延倍率を算出して、より効率的なやり方で（経路切り取り手法を用いて）遅延許容量を算出する。以前の作業では、実行時間を犠牲にすることなく遅延倍率を算出することができなかった。実行時間を減じるために、この方法は、式２２および式２５、または図５内の行［５１３］乃至［５２７］および図６内の行［６１３］乃至行［６２７］に基づいてタイミング非重要経路を削除することによってタイミング重要経路を効率的に選別する。
【００９５】
経路切り取りによって、遅延倍率を計算する実行時間が、以前の作業よりも大幅に短くなり、実際の設計への適用について実現可能になる。
【００９６】
上の説明は、本発明の方法の実施形態に焦点を当てているが、代替的な実施形態はソフトウェア・プログラム製品を具備することに留意されるべきである。この製品は、上記のような方法をコンピュータに実行させるように構成されたプログラム命令をその中に含んだコンピュータ読み取り可能記憶媒体からなる。このコンピュータ読み取り可能記憶媒体は、多くのあらゆる記憶媒体、例として、ＲＡＭ、ＲＯＭ、フラッシュ・メモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハード・ディスク、リムーバブル・ディスク、ＣＤ−ＲＯＭ、光学メディア等を含んでいる。この記憶媒体に格納されている命令は、データ・プロセッサのあらゆるタイプによって実行可能であって、パーソナルまたは汎用コンピュータで実行される命令に限定されない。
【００９７】
上の説明は、幾つかの具体的な例示的な実施形態を提示するが、代替的な実施形態には、説明した特徴および構成要素の多くの変形体が存在する。例えば、別の実施形態では、副経路の評価の結果として生成された中間値が、保存されるとともに他のネットの評価の間に利用可能にされる。これらの値は、例えば、適切に構築されたツリー構造で保存され得る。別の実施形態では、ＩＣが「タイミング独立」のブロックへと分けられて、例えば設計問題の大きさ／範囲が減じられる。別の実施形態では、ネットはグループ化され、各グループは相違する処理によって検査される（マルチ・タスキング、並列処理として知られている）。その他の多くの変形体も、本開示内容を読むことによって、当業者にとって明らかとなるであろう。
【００９８】
上に説明した方法は、回路中の特定のエッジをその中に含んでいる全てのタイミング経路の最小倍率を決定する（および各エッジについてこれを繰り返す）問題に対する厳密な解決策を提供するように設計されていることが留意されるべきである。しかしながら、代替的な実施形態では、この問題に対して、厳密ではなく大体の解決手段を提供するように設計された切り取り基準および／または方法ステップが実行され得る。
【００９９】
当業者は、様々な異なる技術および技法のあらゆるものを用いて、情報および信号が表現され得ることを理解するであろう。例えば、上の説明を通じて言及されるデータ、命令、コマンド、情報、信号、ビット、シンボルは、電圧、電流、電磁波、磁場または磁性粒子、光学場または光学粒子、またはこれらのあらゆる組合せによって表現され得る。この情報および信号は、ワイヤ、金属配線、ビア、光ファイバ等を含むあらゆる適切な転送媒体を用いて、開示されたシステムの構成要素間で通信され得る。
【０１００】
当業者は、さらに、本明細書に開示の実施形態との関連で説明された様々な説明用の論理ブロック、モジュール、回路、アルゴリズム・ステップが、電子ハードウェア、コンピュータ・ソフトウェア、またはこれらの組合せとして実現され得ることを理解するであろう。この、ハードウェアおよびソフトウェアが可換であることを明確に示すために、様々な説明用の構成要素、ブロック、モジュール、回路、およびステップは、これらの機能として上で説明された。このような機能がハードウェアまたはソフトウェアのいずれとして実現されるかは、具体的な適用例およびシステム全体に課される設計制約に依存する。当業者は、説明されている機能を各具体的な適用例について様々な形で実現することが可能であるが、このような実現を決定することは、本発明の範疇からの逸脱を引き起こすものと解釈されるべきでない。
【０１０１】
本明細書に開示の実施形態との関連で説明された様々な説明用の論理ブロック、モジュール、回路は、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）またはその他の論理デバイス、ディスクリー・ゲートまたはトランジスタ・ロジック、ディスクリート・ハードウェア部品、または本明細書において説明されている機能を実行するように設計されたこれらのあらゆる組合せとともに実現および実行されることが可能である。
【０１０２】
本明細書に開示の実施形態との関連で説明された方法およびアルゴリズムのステップは、直接ハードウェアにおいて、プロセッサまたは他のコントローラによって実行されるソフトウェア（プログラム命令）において、またはこれら２つの組合せにおいて具現化されることができる。ソフトウェアは、ＲＡＭメモリ、フラッシュ・メモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハード・ディスク、リムーバブル・ディスク、ＣＤ−ＲＯＭ、本分野で知られている他のあらゆる適切な記憶媒体に保存されることが可能である。本方法の１つを具現化するプログラム命令をその中に含んでいるこのような記憶媒体は、それ自体が本発明の代替的な実施形態である。１つの例示的な記憶媒体が、プロセッサがこの記憶媒体から情報を読み出し、またこの記憶媒体に情報を書き込むことができるようにプロセッサに接続され得る。または、記憶媒体は、プロセッサに組み込まれていてもよい。プロセッサおよび記憶媒体は、例えばＩＣ内に位置し得る。
【０１０３】
本発明によってもたらされる利益および利点は、具体的な実施形態に関して上に記載された。これらの利益および利点、およびこれらの利益および利点を生み出すまたはよりはっきりしたものとする要素および限定事項は、いずれも、請求項のいずれかまたは全ての限定的な、必要な、必須の特徴と解釈されるべきではない。本明細書で用いられているように、「具備する」という文言またはその変形体は、これらの文言に先行する要素および限定事項を非排他的に含むものとして解釈されることが意図されている。よって、要素の組を具備するシステム、方法または他の実施形態は、これらの要素のみに限定されるのではなく、明白に列挙されていないまたは請求項に記載の実施形態に本来備わっている他の要素を含み得る。
【０１０４】
開示された実施形態のここまでの説明は、当業者が本発明を実行および使用することを可能にするために提供される。これらの実施形態に対する様々な変形は、当業者にとって容易に明らかとなり、本明細書で定義されている包括的な原理は、本発明の思想および範疇から逸脱することなく他の実施形態に適用されてよい。よって、本発明は、本明細書に示す実施形態に限定されることが意図されるのではなく、本明細書に開示されまた請求項内で列挙される原理および新規な特徴に従った最も広い範疇に一致するべきである。
【０１０５】
また、この発明は以下の実施態様を取り得る。
【０１０６】
（１）集積回路内のエッジについての遅延許容量割り当てを決定するため）の方法であって、集積回路設計においてタイミング・エッジおよび対応するタイミング経路を定義し、１つまたは複数のエッジについて、前記エッジにおいて開始するまたは終了するタイミング経路を特徴付ける最小／最大到着時刻および設計ゆとり（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数のタイミング経路を、関連する（Ｓ，Ｔ）ペアに基づいて切り取り、切り取られていないタイミング経路に関する前記（Ｓ，Ｔ）ペアに基づいて前記エッジに関連する倍率を決定し、前記エッジに関連する前記倍率を前記エッジに関連する初期遅延によって乗算して前記エッジに関連する遅延許容量割り当てを生成する、ことを具備する方法。
【０１０７】
（２）前記（Ｓ，Ｔ）ペアの組を決定することは、前記エッジにおいて終了する後向きタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数の後向きタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取り、前記エッジにおいて開始する前向きタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数の前向きタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取る、ことを具備する、（１）の方法。
【０１０８】
（３）前記エッジに関連する倍率を決定することは、前記後向きタイミング経路に関連する前記（Ｓ，Ｔ）ペアの１つと前記前向きタイミング経路に関連する前記（Ｓ，Ｔ）ペアの１つとの組合せの各々について、対応する倍率を決定し、前記（Ｓ，Ｔ）ペアの組合せに対応する前記倍率の最小のものを前記エッジに関連する倍率として選択する、ことを具備する、（１）の方法。
【０１０９】
（４）前記タイミング経路の選択された１つを切り取ることは、前記選択されたタイミング経路が１つまたは複数の切り取り基準を満たすかを判断し、前記切り取り基準が満たされている場合、前記選択されたタイミング経路を切り取る、ことを具備する、（１）の方法。
【０１１０】
（５）前記選択されたタイミング経路は、後向きタイミング経路を具備し、前記選択された後向きタイミング経路についての切り取り基準は、前記選択された後向きタイミング経路に関連する最小到着時刻（Ｓ）が第２後向きタイミング経路に関連する前記最小到着時刻（Ｓ´）以下である、と、前記選択された後向きタイミング経路に関連する前記設計ゆとり（Ｔ）が前記第２後向きタイミング経路に関連する前記設計ゆとり（Ｔ´）以下である、と、前記選択された後向き経路に関連する前記最小到着時刻と前記第２後向きタイミング経路に関連する前記設計ゆとりの値との積（Ｓ×Ｔ´）が前記第２後向きタイミング経路に関連する前記最小到着時刻と前記選択された後向きタイミング経路に関連する前記設計ゆとりの値との積（Ｓ´×Ｔ）以下である、と、を具備する、（４）の方法。
【０１１１】
（６）前記選択されたタイミング経路は、前向きタイミング経路を具備し、前記選択された前向きタイミング経路についての切り取り基準は、前記選択された前向きタイミング経路に関連する最大到着時刻（Ｓ）が第２前向きタイミング経路に関連する前記最大到着時刻（Ｓ´）以上である、と、前記選択された前向きタイミング経路に関連する前記設計ゆとり（Ｔ）が前記第２前向きタイミング経路に関連する前記設計ゆとり（Ｔ´）以上である、と、前記選択された前向き経路に関連する前記最大到着時刻と前記第２前向きタイミング経路に関連する前記設計ゆとりの値との積（Ｓ×Ｔ´）が前記第２前向きタイミング経路に関連する前記最大到着時刻と前記選択された前向きタイミング経路と関連する前記設計ゆとりの値との積（Ｓ´×Ｔ）以上である、と、を具備する、（４）の方法。
【０１１２】
（７）前記集積回路のエッジに隣接する複数のノードの各々について、前記ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことをさらに具備する、（１）の方法。
【０１１３】
（８）後向きタイミング経路内の各ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことは、前記後向きタイミング経路内の最初のノードについて、Ｓを前記最初のノードについて規定された到着時刻に等しく設定するとともにＴをゼロに等しく設定し、前記後向きタイミング経路内の１つまたは複数の後続のノードについて、Ｓを先行するノードのＳに介在するエッジの最小の遅延を加えたものに設定するとともにＴを前記先行するノードのＴに介在するエッジの現在の遅延を加え且つ介在するエッジの最小の遅延を引いたものに等しく設定する、ことを具備する、（７）の方法。
【０１１４】
（９）前向きタイミング経路内の各ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことは、前記前向きタイミング経路内の最後のノードについて、Ｓを前記最後のノードについて規定された到着時刻に等しく設定するとともにＴをゼロに等しく設定し、前記前向きタイミング経路内の１つまたは複数の先行する先行するノードについて、Ｓを後続のノードのＳから介在するエッジの最小の遅延を減じたものに設定するとともにＴを前記後続のノードのＴに介在するエッジの現在の遅延を加え且つ介在するエッジの最小の遅延を減じたものに等しく設定する、ことを具備する、（７）の方法。
【０１１５】
（１０）コンピュータ読み取り可能媒体内で体現される１つ以上のプログラム命令を具備するソフトウェア・プログラム製品であって、前記命令は、コンピュータに、集積回路設計においてタイミング・エッジおよび対応するタイミング経路を定義するデータを読み出し、１つまたは複数のエッジについて、前記エッジにおいて開始するまたは終了するタイミング経路を特徴付ける最小／最大到着時刻および設計ゆとり（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数のタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取り、切り取られていないタイミング経路に関する前記（Ｓ，Ｔ）ペアに基づいて前記エッジに関連する倍率を決定し、前記エッジに関連する倍率を前記エッジに関連する初期遅延によって乗算して前記エッジに関連する遅延許容量割り当てを生成し、前記遅延許容量割り当てを保存する、ことを具備する方法を実行させるように設計された、ソフトウェア・プログラム製品。
【０１１６】
（１１）前記（Ｓ，Ｔ）ペアの組を決定することは、前記エッジにおいて終了する後向きタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数の後向きタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取り、前記エッジにおいて開始する前向きタイミング経路を特徴付ける（Ｓ，Ｔ）ペアの組を割り出し、１つまたは複数の前向きタイミング経路を、関連する前記（Ｓ，Ｔ）ペアに基づいて切り取る、ことを具備する、（１０）のソフトウェア・プログラム製品。
【０１１７】
（１２）前記エッジに関連する倍率を決定することは、前記後向きタイミング経路に関連する前記（Ｓ，Ｔ）ペアの１つと前記前向きタイミング経路に関連する前記（Ｓ，Ｔ）ペアの１つとの組合せの各々について、対応する倍率を決定し、前記（Ｓ，Ｔ）ペアの組合せに対応する前記倍率の最小のものを前記エッジに関連する倍率として選択する、ことを具備する、（１０）のソフトウェア・プログラム製品。
【０１１８】
（１３）前記タイミング経路の選択された１つを切り取ることは、前記選択されたタイミング経路が１つまたは複数の切り取り基準を満たすかを判断し、前記切り取り基準が満たされている場合、前記選択されたタイミング経路を切り取る、ことを具備する、（１０）のソフトウェア・プログラム製品。
【０１１９】
（１４）前記選択されたタイミング経路は、後向きタイミング経路を具備し、前記選択された後向きタイミング経路についての切り取り基準は、前記選択された後向きタイミング経路に関連する最小到着時刻（Ｓ）が第２後向きタイミング経路に関連する前記最小到着時刻（Ｓ´）以下である、と、前記選択された後向きタイミング経路に関連する前記設計ゆとり（Ｔ）が前記第２後向きタイミング経路に関連する前記設計ゆとり（Ｔ´）以下である、と、前記選択された後向き経路に関連する前記最小到着時刻と前記第２後向きタイミング経路に関連する前記設計ゆとりの値との積（Ｓ×Ｔ´）が前記第２後向きタイミング経路に関連する前記最小到着時刻と前記選択された後向きタイミング経路に関連する前記設計ゆとりの値との積（Ｓ´×Ｔ）以下である、と、を具備する、（１３）のソフトウェア・プログラム製品。
【０１２０】
（１５）前記選択されたタイミング経路は、前向きタイミング経路を具備し、前記選択された前向きタイミング経路についての切り取り基準は、前記選択された前向きタイミング経路に関連する最大到着時刻（Ｓ）が第２前向きタイミング経路に関連する前記最大到着時刻（Ｓ´）以上である、と、前記選択された前向きタイミング経路に関連する前記設計ゆとり（Ｔ）が前記第２前向きタイミング経路に関連する前記設計ゆとり（Ｔ´）以上である、と、前記選択された前向き経路に関連する前記最大到着時刻と前記第２前向きタイミング経路に関連する前記設計ゆとりの値との積（Ｓ×Ｔ´）が前記第２前向きタイミング経路に関連する前記最大到着時刻と前記選択された前向きタイミング経路と関連する前記設計ゆとりの値との積（Ｓ´×Ｔ）以上である、と、を具備する、（１３）のソフトウェア・プログラム製品。
【０１２１】
（１６）前記集積回路のエッジに隣接する複数のノードの各々について、前記ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことをさらに具備する、（１０）のソフトウェア・プログラム製品。
【０１２２】
（１７）後向きタイミング経路内の各ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことは、前記後向きタイミング経路内の最初のノードについて、Ｓを前記最初のノードについて規定された到着時刻に等しく設定するとともにＴをゼロに等しく設定し、前記後向きタイミング経路内の１つまたは複数の後続のノードについて、Ｓを先行するノードのＳに介在するエッジの最小の遅延を加えたものに設定するとともにＴを前記先行するノードのＴに介在するエッジの現在の遅延を加え且つ介在するエッジの最小の遅延を引いたものに等しく設定する、ことを具備する、（１０）のソフトウェア・プログラム製品。
【０１２３】
（１８）前向きタイミング経路内の各ノードに関連する（Ｓ，Ｔ）ペアの組を割り出すことは、前記前向きタイミング経路内の最後のノードについて、Ｓを前記最後のノードについて規定された到着時刻に等しく設定するとともにＴをゼロに等しく設定し、前記前向きタイミング経路内の１つまたは複数の先行する先行するノードについて、Ｓを後続のノードのＳから介在するエッジの最小の遅延を減じたものに設定するとともにＴを前記後続のノードのＴに介在するエッジの現在の遅延を加え且つ介在するエッジの最小の遅延を減じたものに等しく設定する、ことを具備する、（１０）のソフトウェア・プログラム製品。
【０１２４】
（１９）各エッジに関連する前記遅延許容量割り当てを使用者に提示することをさらに具備する、（１０）のソフトウェア・プログラム製品。
【図面の簡単な説明】
【０１２５】
【図１ａ】一実施形態に従った、簡便なシステムを示す機能ブロック図である。
【図１ｂ】一実施形態に従った、簡便なシステムを示す機能ブロック図である。
【図２】回路の複雑さが増すに連れてタイミング経路の数が増えることを示す機能ブロック図である。
【図３】一実施形態に従った、経路切り取りを含んだ遅延乗数決定方法を示すフローチャートである。
【図４】一実施形態に従った、ドライバを実現する擬似コードのブロックである。
【図５】一実施形態に従った、後向きタイミング経路の部分を追跡するための機能を実現する擬似コードのブロックである。
【図６】一実施形態に従った、前向きタイミング経路の部分を追跡するための機能を実現する擬似コードのブロックである。
【図７】一実施形態に従った、簡便なシステムのグラフによる表現を示す図である。
【図８ａ】一実施形態に従ったシステムのグラフによる表現を示す図である。
【図８ｂ】一実施形態に従ったシステムのグラフによる表現を示す図である。
【図８ｃ】一実施形態に従ったシステムのグラフによる表現を示す図である。
【図９】一例における、残存経路の数の確率分布のプロットである。
【図１０】一例における、残存経路の数の確率分布のプロットである。
【図１１】一例における、残存経路の数の確率分布のプロットである。
【図１２】一例における、残存経路の数の確率分布のプロットである。
【図１ａ】
2008262562.tif 000016
【図１ｂ】
2008262562.tif 000017
【図２】
2008262562.tif 000018
【図３】
2008262562.tif 000019
【図４】
2008262562.tif 000020
【図５】
2008262562.tif 000021
【図６】
2008262562.tif 000022
【図７】
2008262562.tif 000023
【図８ａ】
2008262562.tif 000024
【図８ｂ】
2008262562.tif 000025
【図８ｃ】
2008262562.tif 000026
【図９】
2008262562.tif 000027
【図１０】
2008262562.tif 000028
【図１１】
2008262562.tif 000029
【図１２】
2008262562.tif 000030