回路設計およびリタイミングの方法および装置
回路を階層的にリタイミングする方法と装置。本発明の少なくとも１つの実施形態では、（例えばモジュール・レベルでのリタイミングを介して）異なる複数の最小クロック周期を有するように異なる複数のレイテンシを備える回路のモジュールが設計される。一例では、モジュールの配置配線の後、詳細なタイミング分析から最小クロック周期が決定され、モジュールを含む回路のリタイミングの際に、回路の目的のクロック周期、とレイテンシと最小クロック周期との間の相関に基づいてモジュールのデータ・フロー・グラフ表現が構築される。本発明の少なくとも１つの実施形態では、階層的なリタイミングが実行される。これは、回路の一部分がリタイミングされて（例えば異なるレイテンシについての）結果が生成され、その結果が目的のクロック周期に基づく回路全体のリタイミングに選択的に使用されるものである。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路設計に関し、より詳細には回路設計における回路モデルのタイミング動作のモデリングに関する。
【背景技術】
【０００２】
デジタル回路の設計（例えば超大規模集積回路（ＶＬＳＩ）技術の規模など）では、設計者はコンピュータ支援技術を使用することが多い。複雑なデジタル回路の設計やシミュレーションを助けるためにデジタル回路を記述するハードウェア記述言語（ＨＤＬ）などの標準言語が開発されている。ＶＨＤＬやＶｅｒｉｌｏｇなどいくつかのハードウェア記述言語は、業界標準として発展している。ＶＨＤＬとＶｅｒｉｌｏｇは、抽象データ型を使用して、ゲート・レベル、レジスタ転送レベル（ＲＴＬ）、または動作レベルでハードウェア・モデルを定義する汎用ハードウェア記述言語である。デバイス技術の継続的な進歩に伴い、ＨＤＬをより新しいデバイスや設計様式とともに使用できるようにするための様々な製品設計ツールが開発されている。
【０００３】
ＨＤＬコードによる集積回路の設計の際、コードは、まず書き込まれ、次にＨＤＬコンパイラによってコンパイルされる。ＨＤＬソース・コードは、何らかのレベルで回路素子を記述し、コンパイラは、このコンパイルからＲＴＬネットリストを生成する。ＲＴＬネットリストは、一般に、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）や特定用途向け集積回路（ＡＳＩＣ）など、特定のベンダーの集積回路の技術／アーキテクチャに依存しないという点で、技術非依存型ネットリストである。ＲＴＬネットリストは、（動作表現に対して）回路素子の概略図に対応している。次いで、技術非依存型ＲＴＬネットリストから、ベンダーの技術／アーキテクチャでの回路の作成に使用できる技術固有のネットリストに変換されるように、マッピング・オペレーションが行われる。ＦＰＧＡベンダーが異なる技術／アーキテクチャを使用して集積回路内に論理回路を実装することはよく知られている。したがって、技術非依存型ＲＴＬネットリストがマッピングされて、特定のベンダーの技術／アーキテクチャに固有のネットリストが作成される。
【０００４】
このプロセスにおいてしばしば望ましい１つのオペレーションは、特定の集積回路のレイアウトを計画し、タイミング問題を制御し、集積回路の領域間の相互接続を管理することである。これは、時として「フロア・プランニング」と呼ばれることもある。一般のフロア・プランニング・オペレーションは、集積回路の回路エリアを時として「ブロック」と呼ばれる領域に分割し、ロジックをブロック内に存在するよう割り当てる。これらの領域は、四角形でも四角形でなくてもよい。このオペレーションには、ロジックの位置の推定誤差が集積回路のサイズからブロックのサイズに低減される（タイミング推定値(timing estimates)の誤差を低減する傾向がある）、また、配置配線が非常に大きい問題からより簡単な一連の問題に軽減されているので一般により早く稼動するという２つの効果がある。
【０００５】
リタイミング・アルゴリズムは、回路の設計を最適化するために使用されている。一般に、同期回路は、信号が、指定された数のブロック・サイクル以内（例えば１クロック周期内など）に、組み合わせパス、すなわちメモリ・セル、フリップフロップ、遅延素子などのレジスタを含まないパスに沿って、あるレジスタから別のレジスタに伝わるときのみ、適切に動作する。したがって、レジスタ間のパスにおける最大信号遅延（例えばパス上の組み合わせ演算素子の演算時間や配線遅延のためなど）は、回路が適切に働くことができる最小クロック周期を決定する。レジスタは、回路のパスに配置または再配置されて、パスにおける最大信号遅延を低減し、回路のクロック周期を低減させる。一般のリタイミング・アルゴリズムを使用して、回路のタイミング・モデルに基づいて回路内のレジスタのうちのいくつかを分配し直して、クロック周期を最低限に抑えることができる。
【０００６】
一般に、回路のタイミング・モデルは、組み合わせ演算ユニットと、遅延（レジスタによるなど）と、回路を構成する相互接続とのタイミング・モデルをひとまとめにすることによって取得される。相互接続遅延は、モデル化するのが難しく、したがってしばしば無視される。１つまたは複数の回路モジュールを含む回路システムの一般のタイミング・モデルは、モジュールの組み合わせ演算ユニットのタイミング・モデルの集約から生成される。
【０００７】
一般のリタイミング・アルゴリズム（例えば「ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．９１−１１８，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９に記載）は、データ・フロー・グラフに基づいて策定される。データ・フロー・グラフは、組み合わせ演算ユニットを表すノードと、それらを相互接続するエッジから成る。遅延（レジスタなど）は、エッジの重さとして表される。各ノードには、それに関連付けられている実行時間がある。
【０００８】
例えば、図２〜３は、リタイミング用のデータ・フロー・グラフを構築する従来技術の方法を示している。図２の組み合わせ演算ユニット（加算器２０５、乗算器２０７、２０９）は、演算ノード（例えば図３のノード２２５、２２７、２２９）として表される。組み合わせ演算ユニットでの実行時間は、ノードの演算時間によって表される。例えば、ノード２２５は２ｎｓの演算時間を有しており、この演算時間は加算器２０５によって必要とされ、ノード２２７、２２９のそれぞれは４ｎｓの演算時間を有しており、この演算時間は１つの乗算器（例えば２０９または２０７）によって必要とされる。エッジ２３１は、乗算器２０７と加算器２０５との間の接続を表す。エッジ２３１は、１の重さを有し、この重さはレジスタ２１７（またはレジスタ２１７による１クロック・サイクルのレイテンシ）を表す。同様に、エッジ２３３は、レジスタ２１５を表す１遅延を有する。エッジ２３５は、乗算器２０９と２０７との間の接続を表し、エッジ２３５に関連付けられている遅延はない。
【０００９】
データ・フロー・グラフにおけるクリティカル・パスとは、ゼロ遅延エッジ（組み合わせパス）を含むすべてのパスの中で最長の演算時間を有するパスである。例えば、図３で、ノード２２９からノード２２７へのパスは、ゼロ遅延を有するエッジ２３５を含み、ノード２２９からノード２２７へのパスは、演算時間が最も長くかかる（例えば８ｎｓなど。そのうちの４ｎｓはノード２２９、４ｎｓはノード２２７）。したがって、図２の回路の最小クロック周期は８ｎｓである。図３で、エッジ２３３における遅延をエッジ２３５に移動し、したがってクリティカル・パスがノード２２５と２２９との間のパスになり、演算時間がわずか６ｎｓで済むようにすることができる。したがって、遅延をエッジ２３３からエッジ２３５に移動させることは、レジスタ２１５を加算器２０５と乗算器２０９との間から乗算器２０９と２０７との間に移動させることによって実施することができ、これによって、変更された（リタイミングされた）回路は、低減されたクロック周期６ｎｓで動作することができる。
【００１０】
回路モジュールのタイミング・モデルを取得するための従来の手法は、モジュールを実際に構成するレジスタと組み合わせ演算素子とにモジュールを分解し、１つのノードを各組み合わせ演算素子に割り当てることである。一般に、ある設計における回路モジュールは、モジュールにおける組み合わせユニットと、それを接続するネットに対応する１組のノードとエッジに変換される。言い換えれば、各ハードウェア・モジュールのタイミング・モデルは、一般に、組み合わせ演算ユニットと、遅延と、ハードウェア・モジュールを構成する相互接続とのタイミング・モデルをひとまとめにすることによって構築される。特定のハードウェア・モジュールの変換で使用されるノードとエッジとの組の集約が、事実上そのハードウェア・モジュールのタイミング・モデル（データ・フロー・グラフ）となる。
【００１１】
リタイミング・アルゴリズムは、カットセットのリタイミングとパイプライニングを含む。さらに、データ・フロー・グラフを使用したクロック周期最小化のためのリタイミング・アルゴリズムが存在する。カットセットのリタイミング、パイプライニング、クロック周期最小化のためのリタイミングについてのこれ以上の詳細については、文献（“ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．９７−１０６，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９など）に記載されている。
【発明の開示】
【課題を解決するための手段】
【００１２】
ここでは、回路の階層的なリタイミングを行うための方法と装置について説明する。このセクションでは、本発明の一部の実施態様の要約について述べる。
【００１３】
本発明の少なくとも１つの実施態様では、（例えばモジュール・レベルでのリタイミングを介して）異なる複数の最小クロック周期を有するように異なる複数のレイテンシを備える回路のモジュールが設計される。一例では、モジュールの配置配線の後、詳細なタイミング分析から最小クロック周期が決定され、モジュールを含む回路のリタイミングの際に、回路の目的のクロック周期、および、レイテンシと最小クロック周期との間の相関に基づいてモジュールのデータ・フロー・グラフ表現が構築される。本発明の少なくとも１つの実施態様では、階層的なリタイミングが実行される。これは、回路の一部分がリタイミングされて（例えば異なるレイテンシについての）結果が生成され、その結果が目的のクロック周期に基づく回路全体のリタイミングに選択的に使用されるものである。
【００１４】
本発明の一実施態様では、回路モジュールを設計する方法は、異なる複数のレイテンシを備えるモジュールに対応する、モジュールの複数の回路設計を生成するステップと、複数の回路設計の実行可能なクロック周期を表すように、複数の回路設計の複数の許容できるクロック（例えば最小クロック周期など）を決定するステップと、複数の許容できるクロックを異なる複数のレイテンシに関連付けるための設計データを生成するステップとを含む。一例では、複数の回路設計のそれぞれを生成するために配置配線が実行され、設計レイアウトに基づく詳細なタイミング分析から、許容できるクロックが決定される。一例では、複数の回路設計のうちの第１のものが生成された後、パイプライン・レジスタ・セットが複数の回路設計のうちの第１のものに挿入されて、複数の回路設計のうちの第２のものが生成され、さらに、複数の回路設計の第２のものを生成するためにリタイミングが実行される。一例では、複数の回路設計のうちの第１のものと複数の回路設計のうちの第２のものは（例えば異なる処理ロジックまたは異なるロジック処理要素を有するなど）異なるアーキテクチャを有する。一例では、設計データは、さらに、複数の許容できるクロックに基づいて、異なる複数のレイテンシを、複数の回路設計の１つまたは複数のデータ・フロー・グラフ表現に関連付ける。一例では、モジュールの１つまたは複数のデータ・フロー・グラフ表現は、複数の許容できるクロックに基づいて、複数の回路設計を表すように生成される。例えば、複数の回路設計のうちの第１のものが非レジスタード入力(non-registered input)を含んでいる場合、１つまたは複数のデータ・フロー・グラフ表現は、複数の回路設計のうちの第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、この場合第１のパスは、レジスタを含んでおらず、非レジスタード入力に接続されており、例えば、演算ノードは、レジスタを含んでおらず、複数の回路設計のうちの第１のものの非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である第１のパスにおける信号遅延を表す。同様に、例えば、複数の回路設計のうちの第１のものが非レジスタード出力を含んでいる場合、１つまたは複数のデータ・フロー・グラフ表現は、複数の回路設計のうちの第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、この場合第１のパスは、レジスタを含んでおらず、非レジスタード出力に接続されており、例えば、演算ノードは、レジスタを含んでおらず、複数の回路設計のうちの第１のものの非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である第１のパスにおける信号遅延を表す。また、演算ノードは、レジスタを含んでおらず、複数の回路設計のうちの第１のものにおける非レジスタード入力と出力との間を接続する任意のパスにおける信号遅延以上である第１のパスにおける信号遅延を表すために使用することもできる。一例では、１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現は、複数の回路設計のうちの第１のものに対応しており、第１のグラフ表現は、複数の回路設計のうちの第１のもののレジスタから始まり、第１のもののレジスタで終わるすべての第１のパスを表すエッジを含んでおり、そのエッジにおける遅延は、複数の回路設計のうちの第１のもののレイテンシに関連する。一例では、エッジは、第１のノードと第２のノードとを接続して第１のパスを表す。この場合第１のノードと第２のノードは信号遅延をもたらさない。
【００１５】
本発明の一実施態様では、回路を設計する方法は、回路の設計の目的のクロックを選択するステップと、目的のクロックに基づいて、回路の一部分のデータ・フロー・グラフの表現を決定するステップと、データ・フロー・グラフの表現を使用して目的のクロックの設計をリタイミングするステップとを含む。一例では、データ・フロー・グラフの表現を決定する際に、目的のクロックに基づいて、データ・フロー・グラフのエッジにおいて必要な追加の遅延数が決定される。一例では、エッジは、データ・フロー・グラフの第１のノードと第２のノードとを接続し、エッジによって接続されている第１と第２のノードは、回路の一部分のレジスタから始まり、回路の一部分のレジスタで終了するパスを表す。第１のノードは、レジスタを含んでおらず、回路の一部分の第１の入力と回路の一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続され、第２のノードは、レジスタを含んでおらず、回路の一部分の第１の出力と回路の一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続され、データ・フロー・グラフは、レジスタを含んでおらず、回路の一部分の１つの入力を回路の一部分の１つの出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む。一例では、追加の遅延数を決定する際に、目的のクロックに従って回路の一部分に対してリタイミングが実行される。一例では、追加の遅延数は、追加の遅延数を回路の一部分の許容できるクロックに相関させる設計データから決定される。
【００１６】
本発明の一実施態様では、回路を設計する方法は、回路の設計の目的のクロックを選択するステップと、目的のクロックの回路の設計の一部分をリタイミングして第１の結果を生成するステップと、第１の結果を使用して目的のクロックの設計をリタイミングするステップとを含む。一例では、回路の設計の一部分をリタイミングするステップは、設計の一部分が目的のクロックで稼働できるように、いくつかのパイプライン・レジスタ・セットを設計の一部分に追加する（または削除する）ステップを含み、目的のクロックの設計をリタイミングするステップは、接続を使用して、リタイミングされる設計の一部分のレジスタ間のすべてのパスを表すステップを含む。この場合接続は、設計の一部分に追加されたパイプライン・レジスタ・セットの数を表すいくつかの追加の遅延を必要とする。一例では、接続は、第１のノードと第２のノードとを接続する。この場合第１のノードと第２のノードは信号遅延をもたらさない。一例では、目的のクロックの設計をリタイミングするステップは、入力演算ノードを使用して、レジスタを含んでおらず、設計の一部分の第１の入力と設計の一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、入力演算ノードが遅延のない接続を介して第１のノードに接続されるステップと、出力演算ノードを使用して、レジスタを含んでおらず、設計の一部分の第１の出力と設計の一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、出力演算ノードが遅延にない接続を介して第２のノードに接続されるステップと、第１の演算ノードを使用して、レジスタを含んでおらず、設計の一部分の第２の入力と設計の一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表すステップとをさらに含む。
【００１７】
本発明は、これらの方法を実行するデータ処理システムや、データ処理システム上で実行されるとシステムにこれらの方法を実行させるコンピュータ可読媒体を含めて、これらの方法を実行する方法と装置を含む。
【００１８】
本発明の他の特徴は、添付の図面や以下の詳細な説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１９】
本発明は、例示として示されており、添付の図面に限定されるものではない。図中、同様の参照番号は同様の要素を示す。
【００２０】
以下の説明と図面は、本発明の実例であり、本発明を限定するものと解釈されるべきではない。本発明を完全に理解できるようにするために、特定の詳細が多数記述されている。しかし、いくつかの場合、本発明の説明を不明瞭にするのを避けるために、よく知られている詳細、または従来の詳細は記述していない。本開示において一実施形態への言及は、必ずしも同じ実施形態を指すのではなく、こうした言及は少なくとも１つを意味する。
【００２１】
本発明の少なくとも１つの実施形態は、回路の一部分（例えば回路モジュールまたは回路ブロック）がクロック周期最小化のためにリタイミングされ、回路の一部分のリタイミングの結果に基づいて回路全体がリタイミングされる階層的方法を使用して回路設計のリタイミングを行おうとするものである。本発明の一実施形態では、モジュールのパラメトリック設計を取得してモジュールのタイミング・モデルを確立し、タイミング・モデルを使用して回路全体のリタイミングを行う。
【００２２】
本説明および特許請求の範囲では、レジスタとは、一般に順次素子（遅延素子、メモリ・セル、フリップフロップなど）を指す。レジスタは、回路のクロックとの同期の際に出力することができるように、入力信号をサンプリングし、保持（格納）する。さらに、データ・フロー・グラフのエッジにおける１遅延は、一般に対応するパス上のレジスタの存在によってもたらされるレイテンシの単位を表すことを理解されたい。しかし、レイテンシの単位は、メモリ・セルを読み取るための様々な制御信号など、他の手段を介して実装することもできる。
【００２３】
本発明の方法の多くは、従来の汎用コンピュータ・システムなど、デジタル処理システムで実行することができる。１つの機能のみを実行するように設計され、またはプログラムされている専用コンピュータを使用することもできる。
【００２４】
図１は、本発明とともに使用することができる一般のコンピュータ・システムの一例を示している。図１は、コンピュータ・システムの様々な構成要素を示しているが、こうした詳細は本発明と密接な関係はないので、構成要素を相互接続する任意の特定のアーキテクチャまたは方法を表すためのものではないことに留意されたい。また、構成要素が少ない、または場合によっては多いネットワーク・コンピュータや他のデータ処理システムも本発明とともに使用できることを理解されたい。図１のコンピュータ・システムは、例えば、Ｓｕｎワークステーション、あるいはＷｉｎｄｏｗｓ（登録商標）オペレーティング・システムまたはＡｐｐｌｅ Ｍａｃｉｎｔｏｓｈコンピュータを稼働させるパーソナル・コンピュータ（ＰＣ）とすることができる。
【００２５】
図１に示すように、データ処理システムの形態をしているコンピュータ・システム１０１はバス１０２を含んでいる。バスは、マイクロプロセッサ１０３、ＲＯＭ１０７、揮発性ＲＡＭ１０５、不揮発性メモリ１０６に結合されている。マイクロプロセッサ１０３は、図１の例に示すように、キャッシュ・メモリ１０４に結合されている。バス１０２は、これらの様々な構成要素をいっしょに相互接続し、また、これらの構成要素１０３、１０７、１０５、１０６は、表示コントローラと表示デバイス１０８に接続され、かつ、マウス、キーボード、モデム、ネットワーク・インターフェイス、プリンタ、スキャナ、ビデオ・カメラ、当分野でよく知られている他のデバイスなどの入力／出力（Ｉ／Ｏ）デバイスなどの周辺デバイスに相互接続される。一般に、入力／出力デバイス１１０は、入力／出力コントローラ１０９を介してシステムに結合される。揮発性ＲＡＭ１０５は、一般に、メモリ内のデータを最新の状態したり維持したりするために連続的に電力を必要とする動的ＲＡＭ（ＤＲＡＭ）として実装される。不揮発性メモリ１０６は、一般に磁気ハード・ドライブ、磁気光ドライブ、光ドライブ、ＤＶＤ ＲＡＭ、または電力がシステムから取り除かれた後もデータを維持する他のタイプのメモリ・システムである。また、一般に、不揮発性メモリは、ランダム・アクセス・メモリであるが、これは必須ではない。図１は、不揮発性メモリがデータ処理システムの構成要素の残りに直接結合されているローカル・デバイスであることを示しているが、本発明では、例えばモデムやＥｔｈｅｒｎｅｔ（登録商標）インターフェイスなどのネットワーク・インターフェイスを介してデータ処理システムに結合されているネットワーク記憶デバイスなどのシステムから離れている不揮発性メモリを使用してもよいことを理解されたい。バス１０２は、当分野で知られているような様々なブリッジ、コントローラ、および／またはアダプタを介して互いに接続されている１つまたは複数のバスをも含む。一実施形態では、Ｉ／Ｏコントローラ１０９は、ＵＳＢ周辺装置を制御するＵＳＢ（ユニバーサル・シリアル・バス）アダプタ、および／またはＩＥＥＥ−１３９４周辺装置を制御するＩＥＥＥ−１３９４バス・アダプタを含む。
【００２６】
本発明の形態を少なくとも一部にはソフトウェアに組み込むことができることがこの説明から明らかである。つまり、技術は、ＲＯＭ１０７、揮発性ＲＡＭ１０５、不揮発性メモリ１０６、キャッシュ１０４、またはリモート記憶デバイスなどのメモリに含まれる命令のシーケンスを実行するマイクロプロセッサなどのそのプロセッサに応答してコンピュータ・システムまたは他のデータ処理システムで実行することができる。様々な実施形態では、配線回路を、本発明を実施するためのソフトウェア命令との組み合わせで使用することができる。したがって、技術は、ハードウェア回路とソフトウェアとの任意の特定の組み合わせに限定されるものではなく、また、データ処理システムによって実行される命令の任意の特定のソースに限定されるものでもない。さらに、説明を簡潔にするために、この説明を通じて、様々な機能およびオペレーションは、ソフトウェア・コードによって実行される、またはソフトウェア・コードによってもたらされるものとして説明される。しかし、こうした表現が意味することは、こうした機能はマイクロプロセッサ１０３などのプロセッサによるコードの実行から生まれるということであることを当業者は理解されよう。
【００２７】
機械可読媒体を使用して、データ処理システムによって実行されるとシステムに本発明の様々な方法を実行させるソフトウェアとデータを格納することができる。この実行可能ソフトウェアとデータは、図１に示すように、例えばＲＯＭ１０７、揮発性ＲＡＭ１０５、不揮発性メモリ１０６、および／またはキャッシュ１０４を含む様々な場所に格納することができる。このソフトウェアおよび／またはデータの一部分は、これらの記憶デバイスのうちの任意のものに格納することができる。
【００２８】
したがって、機械可読媒体は、機械（コンピュータ、ネットワーク・デバイス、ＰＤＡ、製造ツール、１組の１つまたは複数のプロセッサを備える任意のデバイスなど）によってアクセス可能な形式で情報を提供（すなわち格納および／または送信）する任意の機構を含む。例えば、機械可読媒体は、書き込み可能／書き込み禁止媒体（読み取り専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ・デバイスなど）、および電気、光、音響または他の形式の伝搬信号（搬送波、赤外線信号、デジタル信号など）などを含む。
【００２９】
回路の一般のタイミング・モデルは、組み合わせ演算素子のタイミング・モデルの集合である。組み合わせ演算素子のタイミング・モデルは回路のクロック周期に依存しない。従来の方法は、回路モジュールの組み合わせ演算素子のタイミング・モデルを集約して、回路のクロック周期に依存しない回路のタイミング・モデルを生成する。
【００３０】
タイミング・モデルが組み合わせ演算素子のタイミング・モデルの集約から構築されるとき、結果として得られたデータ・フロー・グラフにおける組み合わせ演算素子を表すノードの数は非常に多い。また、この種のタイミング・モデルは不正確であることが多い。というのは、モジュール内相互接続遅延（配線遅延など）は一般に無視されるからである。また、組み合わせ演算素子のタイミング・モデルは遅延の実装前推定値を使用するため、不正確である。
【００３１】
一般のリタイミング・アルゴリズムは、Ｏ（ｎ3）の複雑さを有している。この場合、ｎは、従来の方法における組み合わせ演算素子の数に対応するデータ・フロー・グラフでのノードの数である。したがって、ゲート・レベルのタイミング・モデルの使用によって、システム・レベルのリタイミングでの演算の法外な複雑さがもたらされることが多く、一方で、モジュール内相互接続遅延などが無視されるため、また実装前推定値を使用するため、依然として回路のタイミング動作の不正確なモデルが生み出される可能性がある。
【００３２】
本発明の一実施形態では、事前に設計されたハードウェア・モジュールの結合によってシステム・レベルの回路を生成し、リタイミングを改善し、加速するために、タイミング・モデルをこうしたモジュールごとに構成する。本発明の実施形態によるタイミング・モデルは、リタイミングの目的でモジュールのタイミング動作を正確に表しながら、データ・フロー・グラフで使用されるノードの数を最低限に抑える。所与のハードウェア・モジュールの簡単だが有効なタイミング・モデルがシステマチックな方法で構築される。一般に、回路（サブ回路、または回路の１ブロックなど）の一部分を、類似のやり方で回路モジュールとして扱うこともでき、その簡略化されたタイミング・モデルを、本発明の実施形態に従って構成することができる。したがって、クロック周期最小化のための回路のリタイミングは、本発明の実施形態に従って、階層的なやり方で実行することができる。従来の手法では、回路システムのクロック周期最小化は、予め定められている設計とロジック（例えば予め定められているレイテンシおよび予め定められている最大遅延など）をそれぞれ有する組み合わせ演算素子に対応するノードを備えるデータ・フロー・グラフを使用する。本発明の少なくとも１つの実施形態による階層的な手法では、クロック周期最小化は、回路システムの１つまたは複数のモジュール（またはサブ回路）のタイミング・モデルに基づいて実行され、モジュールの各タイミング・モデルは、複数の設計パラメータ（様々なレイテンシ、様々な設計アーキテクチャ、モジュールの様々な最小クロック周期など）を備えるモジュールのクロック周期最小化から取得され、モジュールのタイミング・モデルは、複数の設計パラメータを反映する。一実施形態では、モジュールのタイミング・モデルにおける少なくとも１つのパラメータ（例えば最小レイテンシ）は、回路システムの目的のクロック周期に従って決定される。以下で、本発明の実施形態の詳細についてさらに説明する。
【００３３】
一部のハードウェア・モジュール（ＦＩＲフィルタなど）とサブ回路は一般に、レイテンシを速度と交換することができる。言い換えれば、レジスタをモジュールに「投入」することによってハードウェア・モジュールを加速させ、クロック周期を低減させることができる。
【００３４】
本発明の一実施形態では、ハードウェア・モジュールのタイミング・モデルは、モデルの詳細な実装からデータを使用して構築される。このデータは、モジュールに供給するレジスタの数を増やしていき、ハ―ドウェア・モジュールをリタイミング（および最適化）し、新しいレジスタが追加されるとモジュール内のクリティカル・パスを検出してモジュールの最小クロック周期を決定することによって取得される。本発明の一実施形態では、モジュールの最小クロック周期は、（例えば配置配線後のタイミング分析を使用して）詳細な設計レイアウトから取得される。
【００３５】
出力設計のクロック速度は、例えばクロック周期最小化の既知のリタイミング・アルゴリズムを適用することによって最大化することができる（“ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．１００−１０６，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９）。これらのリタイミング・アルゴリズムは、データ・フロー・グラフ上で策定される。ハードウェア・モジュールは、しばしばレジスタやメモリを含んでおり、単一のノードとして直接適しない。したがって、これらは、そのタイミング動作を十分に表すように、ノードとエッジとの組み合わせに変換される。ノードとエッジが多すぎて最適化アルゴリズムに負担をかけることがないようにするために、本発明の一実施形態による変換／モデリングは、ノードとエッジをできるだけ少なくし、非常に簡単だが十分なタイミング・モデルを提供する。以下で、ハードウェア・モジュール設計からノードとエッジとの組み合わせにシステマチックに変換するための方法を示す詳細な例について説明する。
【００３６】
図４〜図５は、本発明の一実施形態によるレジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。図４は、ｎ個のレジスタード入力とｍ個のレジスタード出力を備えるハードウェア・モジュールを示しており、入力Ｉ1（３０１）、Ｉ2（３０２）、．．．、Ｉn（３０９）は、それぞれレジスタ３１１、３１２、．．．、３１９の直接入力であり、出力Ｏ1（３３１）、Ｏ2（３３２）、．．．、Ｏm（３３９）は、レジスタ３２１、３２２、．．．、３２９からの直接出力である。ロジック３４３は、モジュール３４１の入力３０１〜３０９から出力３３１〜３３９を算出するためのロジック素子のネットワークを表す。追加のｉ組のパイプライン・レジスタが（例えば既知の任意のアルゴリズムを使用してパイプライニングを行う、または設計者によりレジスタを挿入する、またはモジュールの変更された仕様に従って設計者によりモジュールの代替の設計を使用するなど）、ハードウェア・モジュールに「投入」されているとき、ｃjは、モジュール内のクリティカル・パスに沿った遅延を示すと仮定する。１組のパイプライン・レジスタは、モジュールの正方向送りカットセットにある１組のレジスタである。従来のパイプライニング・アルゴリズムを使用して、１組または複数組のパイプライン・レジスタを挿入することができる。値｛ｃ0，ｃ1，．．．，ｃL｝は、任意の既知の方法によって算出することができ、Ｌは、挿入されたパイプライン・レジスタの組の最大数である。パイプライン・レジスタが挿入された後でクリティカル・パス遅延を最低限に抑えるためにリタイミングまたは最適化が行われるため、一般にｃ0＞ｃ1，＞．．．，＞ｃLであると理解されたい。本発明の一実施形態では、クリティカル・パスに沿った遅延は、モジュールが配置され、配線された後でタイミング分析から算出することができる。しかし、遅延は、合成ツールの一般的な方法を使用して推定することもできるが、こうした遅延推定は、一般に、配置配線後のタイミング分析から取得されるものほど正確ではない。本発明の一実施形態によるタイミング・モデルは、１組の値｛ｃ0，ｃ1，．．．，ｃL｝と図５に示すようなデータ・フロー・グラフ表現を含む。
【００３７】
図５では、演算ノードＢi（３５３）とＢ0（３５５）は、ゼロ演算時間を有する。エッジ３５１では少なくとも１つの遅延があり、したがってエッジ３５１は、クリティカル・パスの一部ではあり得ない。この説明から、実行可能性条件(feasibility condition)がシステムの目的のクロックに従って適切に設定されており、エッジ３５１がクリティカル・パスの一部として含まれていない場合、エッジ３５１での遅延回数を任意の数に設定することができることは明らかである。パイプライン・レジスタの追加の組がないモジュールが回路で使用されており、回路のクロックが｛ｃ0，ｃ1，．．．，ｃL｝の値の組からｃ(i-1)＞ｃ＞ｃiとなるような場合、少なくともｉ組のパイプライン・レジスタがモジュールに挿入される場合はモジュールが適切に働くことを理解されたい。したがって、図５のグラフの実行可能性の制約(feasibility constraint)では、エッジ３５１は、適切に働くようにするために、リタイミング・オペレーションに遅延をもうｉ個求めることを示している。こうした制約は、エッジから移動させることができる遅延の最大数を示すデータ・フロー・グラフの一般のエッジに対する実行可能性の制約に非常に似ている。一般のリタイミング・アルゴリズムを使用するには、ｃ(i-1)＞ｃ＞ｃiである場合、エッジ３５１の実行可能性の制約を、エッジから移動させることができる遅延の最大数が−ｉであることとして表すことができる。
【００３８】
したがって、レジスタードＩ／Ｏを備えるモジュール（３４１）データ・フロー・グラフ表現は、２つのノードＢi（３５３）、Ｂ0（３５５）と、これらの２つのノードを接続するエッジ（３５１）を有する。これらのノードの演算時間は０である。エッジの実行可能性の制約は、回路のクロック周期に依存する。モジュールがより大きい設計の構成要素として使用されるとき、タイミング・モデルは、次のようにリタイミングに使用することができる。
【００３９】
１．図５のデータ・フロー・グラフを使用して、設計全体のデータ・フロー・グラフを作成する際のモジュールを表す。
【００４０】
２．ｃは設計全体を対象としたクロック周期と仮定する。（Ｌ＋１）組のパイプライン・レジスタをモジュールに追加することでは、ｃL未満のモジュールの最小クロック周期を低減することができないことを前提として、ｃ＜ｃLである場合、目的のクロック周期ｃは設計に適していないという結論に達する。
【００４１】
３．ｃ≦ｃLの場合、エッジ３５１の実行可能条件を決定する。例えば、ｉ＝１，２，．．．，Ｌであるときにｃi＜ｃ＜ｃ(i-1)の場合、エッジには追加の遅延が少なくともｉ個必要である。ｃ＞ｃ0である場合、エッジには追加の遅延は必要ない。次いで既知のアルゴリズムを使用して、データ・フロー・グラフを使用した設計全体のリタイミングを行うことができる。例えば、“ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．９１−１１８，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９のリタイミング・アルゴリズムでは、値ｒ（Ｂi）とｒ（Ｂ0）は、ノードＢi、Ｂ0について解かれ、したがってリタイミングした後、エッジ３５１での遅延数がｗからｗr＝ｗ＋ｒ（Ｂ0）ｒ（Ｂi）に変わる。したがって、エッジ３５１の実行可能性条件は、ｃi＜ｃ＜ｃ(i-1)の場合はｒ（Ｂi）−ｒ（Ｂo）＜−ｉ、ｃ＞ｃ0の場合はｒ（Ｂi）−ｒ（Ｂ0）＜０となり、またｃ＜ｃLの場合は実行できない。
【００４２】
４．実行可能なリタイミングの解が見つかった場合、モジュールのインスタンス化の間にｒ（Ｂ0）−ｒ（Ｂi）組のパイプライン・レジスタをモジュールに追加する。
【００４３】
図４、図５に示した例は、モジュールのすべての入力ライン（またはすべての出力ライン）を介して１組または複数組のパイプライン・レジスタがモジュールに「投入」される状況を示している。しかし、モジュールのクロック周期は、モジュールの入力（または出力）ラインのうちの１つまたは一部分を介してレジスタに「投入」することによって最低限に抑えることもできることを理解されたい。例えば、図４のモジュールのクロック周期は、１つのレジスタを入力Ｉ1（３０１）に追加し、変更されたモジュールをリタイミングしてクロック周期を最低限に抑えることによって低減させることができる。入力および／または出力ラインの一部分のリタイミングによるこうしたレイテンシの変化を反映させるために、レジスタードＩ／Ｏを備えるモジュールのより全体的なデータ・フロー・グラフは、入力Ｉ1，Ｉ2，．．．，ＩnとＢiとの間、および出力Ｏ1，Ｏ2，．．．，ＯmとＢoとの間を接続するゼロ処理時間ノードを含むことができる。これらのゼロ処理時間ノードをＢi、Ｂoに接続する各エッジは、少なくとも１つの遅延を有しており、モジュールの対応する入力ラインまたは出力ラインを介して「投入」されたレジスタに対応する数を示すために、追加の遅延をいくつか必要とする。あるいは、同じ数のレジスタが入力ラインの一部分に「投入」されるとき、これらの入力ラインは、単一のゼロ処理時間ノードに接続される。これは次いで、システム全体のリタイミングの際に少なくとも同じ数の遅延を必要とするエッジを介してノードＢiに接続される。独立してリタイミングすることができる入力と出力の部分は、タイミング・モデル・トポロジを決定する。さらに独立性を許容することによって、結果的により複雑なモデルが得られる。さらに、同じ数のレジスタに「投入」するために、様々なモデルを構築することができる。この説明から、異なるレイテンシを備えるモジュールのリタイミングに基づいて、簡略化されたデータ・フロー・グラフの多くの変形を構築することができることを理解されたい。実行可能性条件は、回路システムの目的のクロックに従って設定される。
【００４４】
モジュールの入力および／または出力がレジスタードではないとき、本発明の一実施形態によるリタイミング・モデルは、１）非レジスタード入力ごとの入力から任意のモジュール内レジスタへの最大遅延、２）非レジスタード出力ごとの任意のモジュール内レジスタから出力への最大遅延、３）入力−出力対ごとの任意の純粋な組み合わせパスにおける最大入力対出力遅延を考慮に入れる。純粋な組み合わせパスは、クロックト・レジスタ(clocked register)を含まないことを理解されたい。
【００４５】
これらの最大遅延値は、パイプライン・レジスタの追加の組の数に依存する可能性があり、したがって、実行可能性条件がそうであると同様に、目的のクロック周期に依存する可能性があることに留意されたい。
【００４６】
図６〜図７は、本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。図６では、入力４０１、４０２はレジスタードではなく、出力４３１はレジスタードではなく、入力４０１から出力４３１への少なくとも１つの純粋な組み合わせパスがある。ネットワーク４４５、４４７、４４９は、レジスタを有してない純粋な組み合わせネットワークを表す。
【００４７】
図７は、本発明の一実施形態によるモジュール４４１のデータ・フロー・グラフの一例を示している。図７では、ノード４５３、４５５とエッジ４５１は、モジュール４４１のレジスタード部分を表しており、これには、ネットワーク４４３を介したレジスタ４１１〜４１９、およびレジスタ４２１〜４２９の間のすべてのパスが含まれている。ノードＡ2i（４６１）は、入力Ｉ2（４０２）とレジスタ４１２との間のパスを表し、ノ―ドＡ1i（４６３）は、入力Ｉ1（４０１）とレジスタ４１１との間のパスを表し、ノードＡ1o（４７１）は、レジスタ４２１と出力Ｏ1（４３１）との間のパスを表し、ノードＡ1l（４５７）は、ネット４４０を介した入力Ｉ1（４０１）と出力Ｏ1（４３１）との間のパスを表す。ノードＢ1i（４６５）は、ノードＡ1i（４６３）とＡ1l（４５７）の入力Ｉ1への適切な接続を容易にする。同様に、ノ―ドＢ1o（４７３）は、ノードＡ1l（４５７）とＡ1o（４７１）を出力Ｏ1に接続する。図７では、ノードＢ1i、Ｂ1o、Ｂi、Ｂoは、接続を容易にするために使用されるため、ゼロの処理時間を有し、ノードＡ2i、Ａ1i、Ａ1l、Ａ1oは純粋な組み合わせパスを表すため、ノードによって表されるすべてのパスの中の最大遅延に等しい処理時間を有する。例えば、Ａ1i（４６３）は、入力Ｉ1（４０１）からレジスタ４１１への最大遅延に等しい処理時間を有し、Ａ2i（４６１）は、入力Ｉ2（４０２）からレジスタ４１２への最大遅延に等しい処理時間を有し、Ａ1o（４７１）は、レジスタ４２１から出力Ｏ1（４３１）への最大遅延に等しい処理時間を有し、Ａ1l（４５７）は、（ネットワーク４４０を介して）入力Ｉ1（４０１）から出力Ｏ1（４３１）への最大組み合わせ遅延に等しい処理時間を有する。
【００４８】
一般に、モジュールのレジスタへの入力は、モジュールの１つまたは複数の入力からの結果とすることができることを理解されたい。同様に、モジュールのレジスタからの出力は、モジュールの複数の出力に関与し得る。図８〜図９は、本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する別の例を示す図である。図８では、入力Ｉ1（５０１）とＩ2（５０２）は、レジスタ５１１に至る１つまたは複数の純粋な組み合わせパスを有している。ネットワーク５４５は、レジスタを含んでいない。入力Ｉ1（５０１）とレジスタ５１１との間のすべての組み合わせパスは、図９のノードＡ1i（５６３）によって表されており、入力Ｉ2（５０２）とレジスタ５１１との間のすべての組み合わせパスは、図９のノードＡ2i（５６１）によって示されている。図９では、Ａ1i（５６３）Ａ2i（５６１）の処理時間は、組み合わせネットワーク５４５を介したそれぞれ入力Ｉ1（５０１）とＩ2（５０２）からレジスタ５１１への最大遅延である。
【００４９】
レジスタードＩ／Ｏを備えるモジュールと同様に、非レジスタードＩ／Ｏを備えるモジュールのクロック周期を、入力ラインと出力ラインの一部分を介してレジスタに「投入」することによって低減することもできる。入力ラインと出力ラインの一部分のこうしたレイテンシの追加は、レジスタードＩ／Ｏを備えるモジュールについて上述したものに似た方法で、モジュールのレジスタード部分（例えばノードＢi５３３とＢo５５５）を表すノードに接続されているエッジ上で指定することができる。
【００５０】
さらに、一般に、モジュールの入力は、異なるレジスタへの組み合わせパスを有していてもよく、モジュールの出力は、純粋な組み合わせパスを介して複数のレジスタからの関与を得ることができることを理解されたい。一般に、単一ノードを使用して、レジスタを有しておらず、モジュールの１つの入力からモジュールの任意のレジスタにそれぞれ向かうすべてのパスを表すことができ、単一ノードの演算時間は、ノードによって表されるすべてのパスの中の最大遅延である。同様に、単一ノードを使用して、レジスタを有しておらず、モジュールの任意のレジスタからモジュールの１つの出力にそれぞれ向かうすべてのパスを表すことができる。さらに、単一ノードを使用して、レジスタを有しておらず、モジュールの１つの入力からモジュールの１つの出力にそれぞれ向かうすべてのパスを表すことができる。
【００５１】
図１０〜１６は、本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【００５２】
図１０は、最小レイテンシを有するモジュールを示す図であり、図１１は、本発明の一実施形態による図１０のモジュールのデータ・フロー・グラフを示している。図１１では、ノードＢi（７０３）、エッジ７０１、ノードＢo（７０５）は、図１０のレジスタ間のすべてのパス（例えば加算器６３５を経由する図１０のレジスタ６３１からレジスタ６３３まで）を表している。ノード７１１は乗算器６２１を表し、ノード７１３、７１５は乗算器６２３と加算器６３５を表し、ノード７１７、７１９は乗算器６２５と加算器６３７を表す。図１１では、入力Ｉからノード７０３への２つのパスがあり、これは、図１０の入力Ｉ（６０１）から内部レジスタ６３１、６３３のモジュールへの異なる組み合わせパスを表していることに留意されたい。これらのパスは、パスにおける最長遅延に等しい処理時間を有する単一ノードによって表すことができる。図１２は、データ・フロー・グラフのこうした表現を示しており、ノードＡi（７２１）は、図１０における入力Ｉから任意の内部レジスタのモジュールへの最長の組み合わせ遅延を表している。一実施形態例では、データ・フロー・グラフの表現は、ノード（ロジックを表す）と、ノード間のリンクを含む。さらに、ノード７２３は、乗算器６２５と加算器６３７を通るパスにおける遅延である、任意の組み合わせパスを通る入力Ｉ（６０１）から出力Ｏ（６０３）への最長遅延を表す。ノードＡｏ（７２５）は、加算器６３７を通るレジスタ６３３から出力Ｏ（６０３）へのパスを表す。ノード７０３、７０５は、ゼロ処理時間を有し、ノード７２１と７０３との間と、ノード７０５、７２５との間のエッジは遅延がなく、したがってノード７０３、７０５は、ノード７２１、７２５にそれぞれマージされる（この例では図１２におけるノードＢi（７０３）とＢo（７０５）が冗長であるため）ことに留意されたい。図１０のモジュールのクリティカル・パスを識別した後、モジュールの最小クロック周期Ｃoが決定される。
【００５３】
図１０のモジュールにもう１つ分のクロック・サイクルのレイテンシが許可されているとき、パイプライン・レジスタ・セット（例えば図１３のレジスタ６４１、６４３、６４５など）を追加することができる。（例えば図１３の設計を生成するために）もう１つ分のクロック・サイクルのレイテンシを備えるモジュールのクロック周期を最低限に抑えるために、リタイミングや最適化を実行することができる。次いで図１４に示したようなデータ・フロー・グラフを、図１３のモジュールのために構築することができる。図１４では、ノード７３１は、入力６０１から乗算器６２１、６２３、６２５を通るパスを表し、ノード７３５は、加算器６３７を通るレジスタ６３３、６４５から出力６０３へのパスを表している。図１０のモジュールに対して、図１３のモジュールは、もう１組のパイプライン・レジスタ（もう１つ分のクロック・サイクルの遅延時間）を必要とし、したがって、図１４のデータ・フロー・グラフにおけるエッジ７０１は、図１２のデータ・フロー・グラフにおけるエッジ７０１に対して１つ多くの遅延を必要とする。図１３のモジュールのクリティカル・パスを識別した後、もう１つ分のクロック・サイクルのレイテンシを含むモジュールの最小クロック周期Ｃ1が決定される。図１４のノードＢi（７０３）、Ｂo（７０５）は、この例では冗長であり、取り除くこともできることに留意されたい。
【００５４】
レジスタ６５１、６５３とレジスタ６４１、６４３、６４５が図１５のようにモジュールに追加されると、モジュールは、レジスタードＩ／Ｏを備えるモジュールになる。したがって、図１５のモジュールは、図１６のデータ・フロー・グラフによって表すことができる。図１６のエッジ７０１は、図１２のエッジ７０１に対して３つ多い遅延を必要とする。同様に、図１５のモジュールのクリティカル・パスを識別した後、もう３つ分のクロック・サイクルのレイテンシを含むモジュールの最小クロック周期Ｃ3が決定される。
【００５５】
図１２、図１４、図１６のデータ・フロー・グラフは、モジュールを含む回路のリタイミングの際に、目的のクロック周期ｃに従って選択的に使用することができる。例えば、ある回路で図１０のモジュールが使用されており、Ｃ1＜Ｃ＜Ｃ0であるとき、少なくとももう１つ分のクロック・サイクルのレイテンシがモジュールに「投入」されることが求められ、したがって、図１４のデータ・フロー・グラフは、回路全体のクロック最小化のためのリタイミングに使用され、図１４のエッジ７０１の実行可能性条件は、エッジ７０１には１つ多い遅延が必要（またはエッジ７０１から取り除くことができる最大遅延は−１）であることであることを理解されたい。しかし、この回路で図１３のモジュールが使用されており、Ｃ＞Ｃ0である場合、追加の１つ分のレイテンシをモジュールから移動させることができ、したがって図１２のデータ・フロー・グラフを使用することができ、図１２のエッジ７０１の実行可能性条件は、最大１つの遅延をエッジ７０１から移動させることができることであることを理解されたい。
【００５６】
ＩＰモジュールが設計で使用されるとき、ユーザは、ＩＰモジュールで使用すべきレイテンシの量を指定することができる。したがって、リタイミング最適化エンジンに入力される設計は、そのＩＰモジュールの最低必要レイテンシより長いレイテンシを有するＩＰモジュールを有することができる。例えば、入力された設計が２つのパイプライン・レジスタを有するＦＩＲフィルタ・モジュールを含んでいてもよい。モジュールの元の指定されたレイテンシが考え得る最小レイテンシより長いとき、モジュールのデータ・フロー・グラフの制約の構築で、追加のレイテンシが考慮される。例えば、実行可能性条件は、必要に応じて回路の別の部分に移すことができる追加のレイテンシを示すように調整することができる。代替の手法を使用することもできることに留意されたい。例えば、追加のレイテンシは、モジュールの出力（または入力）ポートから始まるエッジにおける移動可能な重さ（遅延）として指定することができる。
【００５７】
図１７は、本発明の一実施形態による回路をリタイミングする方法を示す図である。オペレーション８０１が回路の一部分（ブロックやモジュールなど）を受信した後、オペレーション８０３は、回路の一部分の複数の変形の複数の許容できるクロック（例えば最小クロック周期または最大クロック周波数など）を決定する。回路の一部分の複数の変形のそれぞれは、その回路の一部分の少なくとも一部の入力と出力のタイミングがその回路の一部分とは異なる。例えば、回路の一部分の１つの変形は、１つまたは複数のレジスタ（正または負のレイテンシを備える）を、回路の一部分の入力ラインと出力ラインの少なくとも一部分に追加し、回路の一部分のリタイミングを実行することに等しい。オペレーション８０５は、複数の許容できるクロックを使用して回路をリタイミングする。例えば、（例えば入力ラインと出力ラインの一部分を介して）モジュールに「投入」する必要のある最低数のレイテンシ（遅延）は、複数の許容できるクロックと、回路の目的のクロックから決定される。
【００５８】
図１８は、本発明の一実施形態による回路モジュールを設計する方法を示す図である。オペレーション８１１は、回路（モジュールまたはブロックなど）の許容クロック（最小クロック周期または最大クロック周波数など）を決定する。オペレーション８１３は、パイプライン・レジスタ・セットを回路に追加することによって回路を変更する。代わりに、１組のレジスタは、モジュールの入力ラインと出力ラインの一部分を介してモジュールに「投入」することができる（例えば入力ラインと出力ラインの一部分にレジスタを追加し、追加されたレジスタを備えるモジュールを最適化するようリタイミングする）。オペレーション８１５は、変更された回路の許容クロックを決定する。オペレーション８１７が、モジュールのクロックを低減するためにパイプライン・レジスタをもう１組追加すべきである（または、モジュールのクロック周期を最低限に抑えるためにより多くのレジスタをモジュールに「投入」することができる）と決定すると、オペレーション８１３、８１５は、モジュールの異なる変形を得るために繰り返される。オペレーション８１９は、所与のクロックが回路に許容可能になるように回路に追加することができるパイプライン・レジスタ・セットの数を決定するために、追加されたパイプライン・レジスタ・セットの数を許容クロックに関連付ける。したがって、モデルが設計に使用されているとき、目的のクロックを実行可能にするために回路に追加することができる最低数のパイプライン・レジスタ・セットを決定することができる。あるいは、モジュールの入力ラインと出力ラインの一部分を介してモジュールに「投入」することができるレジスタの最低数は、モジュールの変形と対応する最小クロック周期との間の関係から決定することができる。クロック最小化のために、異なる数のレジスタを、モジュールの入力ラインと出力ラインの異なる部分を介してモジュールに「投入」することができ、次いで、回路の目的のクロックを達成するためにモジュールに「投入」することができる最低数のレジスタを、モジュールに「投入」されたレジスタの数と対応する最小クロック周期との間の相関から決定することができる。
【００５９】
図１９は、本発明の一実施形態によるレジスタードＩ／Ｏを備えるモジュールを備える回路をリタイミングする方法を示す図である。オペレーション８３１は、レジスタード入力と出力を備える回路の一部分を決定する。回路の一部分への各入力は、レジスタに対する直接入力であり、回路の一部分の各出力は、レジスタからの直接出力である。オペレーション８３３は、回路のデータ・フロー・グラフにおけるエッジによって接続された２つのノードを備える回路の一部分を表し、２つのノードのそれぞれは、ゼロ演算時間を必要とし、エッジにおいて必要な追加の遅延数は、回路の様々な許容クロックと回路に挿入された様々な遅延数との間の関係に従って、回路の目的のクロックによって決定される。回路の様々な許容クロックと様々な遅延数との間の関係は、システム・レベルでの回路のリタイミングの開始前、またはシステム・レベルでの回路のリタイミングのプロセス中に決定することができる。オペレーション８３５は、データ・フロー・グラフを使用して回路をリタイミングする。
【００６０】
図２０は、本発明の一実施形態による回路を設計する詳細な方法を示す図である。オペレーション９０１は、追加の遅延のない回路モジュールを生成する。オペレーション９０３は、モジュールに挿入される追加の遅延数をゼロに設定する。オペレーション９０５は、モジュールの配置配線を行う。オペレーション９０７は、（例えば静的タイミング分析またはタイミング・シミュレーションなどから）モジュールの最小クロック周期を決定する。オペレーション９０９は、モジュールのデータ・フロー・グラフの生成を開始する。モジュールの入力ごとに、オペレーション９１１は、モジュールの任意の純粋な組み合わせパスにおける入力と任意のレジスタとの間の最大入力遅延を決定し、（最大入力遅延がゼロでない場合）最大入力遅延に等しい演算時間を有する入力演算ノードによる最大入力遅延をモジュールのデータ・フロー・グラフに表す。モジュールの出力ごとに、オペレーション９１３は、モジュールの任意の純粋な組み合わせパスにおける出力と任意のレジスタとの間の最大出力遅延を決定し、（最大出力遅延がゼロでない場合）最大出力遅延に等しい演算時間を有する出力演算ノードによる最大出力遅延をデータ・フロー・グラフに表す。オペレーション９１５は、遅延無しのエッジを使用して、モジュールへの入力を、入力演算ノードを介してデータ・フロー・グラフにおける第１のノードに接続する（対応する最大入力遅延がゼロではない場合。そうでない場合は、第１のノードに直接接続する）。オペレーション９１７は、遅延無しのエッジを使用して、モジュールの出力を、出力演算ノードを介してデータ・フロー・グラフにおける第２のノードに接続する（対応する最大出力遅延がゼロではない場合。そうでない場合は、第２のノードに直接接続する）。オペレーション９１９は、第１と第２のノードを、遅延のあるエッジに接続する。エッジが必要とする追加の遅延数は、データ・フロー・グラフに挿入されるパイプライン・レジスタの少なくとも追加の組の数である。オペレーション９２１は、入力と出力の対ごとに、レジスタを含んでおらず、入力と出力の対を接続するモジュールにおける任意のパスの最大遅延を決定し、（こうしたパスが存在する場合）入力と出力の対を、データ・フロー・グラフにおける遅延のないエッジに直接接続する演算ノードとして最大遅延を表す。オペレーション９２３は、回路のデータ・フロー・グラフを最小クロック周期と、回路に挿入された追加の遅延数に関連付ける。オペレーション９２５が（例えばパイプライン・レジスタ・セットを挿入することによって）追加の遅延を追加することを決定した場合、オペレーション９４１は、モジュールに挿入される追加の遅延数を１つずつ増やし、オペレーション９４３は、（例えばパイプライン・レジスタ・セットを挿入し、最適化を実行することによって）回路モジュールを変更する。追加のレイテンシ（または遅延）は、入力ラインと出力ラインの一部分を介してモジュールに「投入」することもできることに留意されたい。
【００６１】
異なるレイテンシを備えるモジュールの変形の様々な設計が取得された後、オペレーション９２７は、回路においてモジュールを使用する。オペレーション９２９は、回路のクロック周期を選択する。オペレーション９３１は、モジュールの最小クロック周期と追加の遅延数との間の関係に従って、選択されたクロック周期を達成するために、モジュールによって必要とされる最小余分遅延を決定する。オペレーション９３３は、最小余分遅延がモジュールに挿入されたとき、モジュールのデータ・フロー・グラフを使用して回路のデータ・フロー・グラフにモジュールを表す。オペレーション９３５は、回路のデータ・フロー・グラフを使用して、リタイミング・オペレーションを実行する。この場合、制約は、挿入された最小余分遅延を示す。モジュールの最小余分遅延数は、制約の形式で、リタイミング・オペレーション全体に組み込まれる。例えば、データ・フロー・グラフのエッジの実行可能性の制約は、少なくとも最小余分遅延がリタイミング・オペレーションでエッジに移動されることを求める（またはエッジのリタイミング・オペレーションで移動させることができる遅延の数は、挿入された最小余分遅延に等しい大きさの負の数である）。オペレーション９３７は、回路に異なるクロック周期を選択するかどうかを決定する。例えば、選択されたクロック周期がリタイミングの後に実行可能である場合、クロック周期の低減を選択することができ、回路に選択されたクロック周期に使用できる実行可能な解がない場合、目的のクロック周期は増える。オペレーション９２９〜９３５は、回路のクロックが最低になるまで繰り返すことができる。
【００６２】
本発明の一実施形態において、モジュールは、異なるレイテンシと最小クロック周期（異なるレイテンシと速度）を備える複数の設計を有する。異なるレイテンシと速度を備えるモジュール設計を取得するために、レジスタが１つのモジュール設計の入力（または出力）ラインの少なくとも一部分に追加された後、リタイミングと最適化を実行することができる。一般に、リタイミングと最適化は、モジュール設計のアーキテクチャを変更しないことを理解されたい。しかし、異なる設計アーキテクチャを使用して異なる方法でモジュールを実施して、異なるレイテンシと速度を備えるモジュール設計を生成することができ、必要な速度とレイテンシ（および存在する場合は他の要件）に基づいて、システム・レベル・アルゴリズムを、異なるアーキテクチャのこれらの異なる設計の中から選択することができる。異なるアーキテクチャが使用される場合、異なる設計は、異なるロジック・オペレーション素子を含み、異なる設計は、異なる処理ロジックを有し得る。例えば、図２１は、８ビットの加算器（１０１１、１０１３）を含む１６ビットの加算器（１００１）の設計例を示している。入力Ｘ（１００３）とＹ（１００５）の最下位８ビット（ＸLおよびＹL）の合計の桁上げ出力ビット(carry out bit)は、ライン１０１５を介して加算器１０１３に入力され、加算器１０１３は、入力Ｘ（１００３）とＹ（１００５）の最上位８ビット（ＸM、ＹM）と加算器１０１１からの桁上げ出力ビットを合計する。図２２は、加算器１０１１の桁上げ出力ビットが加算器１０２１、１０２３の結果から１つを選択する桁上げ選択(carry-select)と呼ばれる異なるアーキテクチャを備える１６ビット加算器の異なる設計を示している。加算器１０２１は、加算器１０１１の桁上げ出力ビットが１であると仮定して最上位８ビット（ＸM、ＹM）を合計し、加算器１０２３は、加算器１０１１の桁上げ出力ビットがゼロであると仮定して最上位８ビット（ＸM、ＹM）を合計する。桁上げ選択アーキテクチャは、追加の８ビット加算器桁上げ付き、および乗算器（１０２５）を使用することによってクリティカル・パスを速める。図２１と図２２の設計は、同じレイテンシを有しているが、異なる速度を有している。図２３は、図２１の設計のパイプライン式バージョンを示している。パイプライン・レジスタ１０５１〜１０５７では、図２１の設計に対して、図２３の設計のレイテンシが１ずつ増える。しかし、図２３の設計（１０４１）は、図２１と図２２の設計（１００１、１０２１）より速い。本発明の一実施形態では、システム・レベルの最適化は、目的のクロック周期に従って、設計１００１、１０４１（同じアーキテクチャを有する）から１つを選択するステップ、または設計１０２１、１０４１（異なるアーキテクチャを有する）から１つを選択するステップ、または設計１００１、１０２１、１０４１から１つを選択するステップを伴う。代替の設計が選択されると、本発明の様々な方法を使用して選択された設計のタイミング・モデルを構築して、モジュールのタイミング動作を簡略化し、レジスタ可用性条件を提示することができる。
【００６３】
本発明の一実施形態では、（例えばレジスタの前または後ろの組み合わせパス、またはクリティカル・パスにおける）信号遅延は、（例えば配置配線後）モジュールの全実装から取得される。したがって、モジュール内の接続遅延は、簡略化されたタイミング・モデルに含まれる。これは、モジュールのタイミング動作を正確に反映する。これらのタイミング・モデルは、最低限の複雑さで最適なリタイミングの解決策をもたらし得る。こうしたモデルは、実際の組み合わせ構成要素モデルよりかなり簡単であるが、タイミング動作をより現実的に表している。というのは、モジュール内タイミング動作の正確な遅延データ（例えば相互接続の遅延などのモジュール内遅延など）が考慮に入れられるからである。結果として、こうしたタイミング・モデルは、あまり複雑ではなく、より高い精度をもたらす。タイミングにおけるよりよいモデリング精度は、より質の高い最終解決策をもたらす。
【００６４】
従来の方法とは異なり、本発明の実施形態によるタイミング・モデルは、単純、有効、かつ正確にシステム・レベルの回路をリタイミングすることができる。単純なタイミング・モデルでは、データ・フロー・グラフにおいて使用するノードがより少ないので、システム・レベルのリタイミングの演算の複雑さがより低減される。したがって、本発明の実施形態による単純なタイミング・モデルは、より高質の結果をもたらしながら、システム・レベルのリタイミングの演算の複雑さを大幅に低減することができる。
【００６５】
さらに、本発明の一実施形態では、レジスタの「投入」は、特定のハードウェア・モジュール向けのアルゴリズムで実行することができる。こうしたカスタム・アルゴリズムを使用すると、ハードウェア・モジュールのアーキテクチャは、レイテンシによって劇的に変わり、既存の一般のアルゴリズムを介して達成することができるものよりはるかによい結果を生成することができる。特性値(characterization value)｛ｃ0，ｃ1，．．．，ｃL｝は、カスタム・アルゴリズムのこの挙動を捕捉する。
【００６６】
回路モジュールを表す簡略化されたモデルの上記の例は、クロック周期を最低限に抑えるためのシステム・レベルのリタイミングについて示されているが、この手法は、システムのエリアと消費電力（または他の設計の目的）を伴う最適化のために使用することもできることを理解されたい。例えば、回路の消費電力またはエリアなどの他の属性を、回路モジュールの簡略化されたモデルに追加して、回路モジュールの対応する特性（例えば回路モジュールの設計の変更による消費電力の変化）を表すことができ、システム・レベルの最適化は、（タイミングの制約に加えて）これらの属性を伴う。例えば、図２１〜２３の設計１００１、１０２１、１０４１の消費電力とモジュール・エリアを決定することができる。したがって、設計の変更による消費電力とモジュール・エリアの変化を評価することができ、これは、消費電力、回路エリア、クロック速度の制約、これらの制約の組み合わせを伴うシステム・レベルの最適化に使用することができる。
【００６７】
上記の明細書では、本発明は、その特定の実施形態例を参照して説明してきた。頭記の特許請求の範囲に記載した本発明の意図および範囲から逸脱することなく、様々な変更をそれに加えることができることは明らかである。したがって本明細書および図面は、制約の意味ではなく例示の意味と見なされるものとする。
【図面の簡単な説明】
【００６８】
【図１】本発明とともに使用することができるデータ処理システムを示すブロック図例である。
【図２】リタイミング用のデータ・フロー・グラフを構築する従来技術の方法を示す図である。
【図３】リタイミング用のデータ・フロー・グラフを構築する従来技術の方法を示す図である。
【図４】本発明の一実施形態によるレジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図５】本発明の一実施形態によるレジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図６】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図７】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図８】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する別の例を示す図である。
【図９】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する別の例を示す図である。
【図１０】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１１】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１２】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１３】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１４】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１５】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１６】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１７】本発明の一実施形態による回路をリタイミングする方法を示す図である。
【図１８】本発明の一実施形態による回路モジュールを設計する方法を示す図である。
【図１９】本発明の一実施形態によるレジスタードＩ／Ｏを備えるモジュールを備える回路をリタイミングする方法を示す図である。
【図２０】本発明の一実施形態による回路を設計する詳細な方法を示す図である。
【図２１】本発明の一実施形態に従って使用することができる、異なるレイテンシおよび最小クロック周期についての異なる設計を備えるモジュールの例を示す図である。
【図２２】本発明の一実施形態に従って使用することができる、異なるレイテンシおよび最小クロック周期についての異なる設計を備えるモジュールの例を示す図である。
【図２３】本発明の一実施形態に従って使用することができる、異なるレイテンシおよび最小クロック周期についての異なる設計を備えるモジュールの例を示す図である。
【技術分野】
【０００１】
本発明は、回路設計に関し、より詳細には回路設計における回路モデルのタイミング動作のモデリングに関する。
【背景技術】
【０００２】
デジタル回路の設計（例えば超大規模集積回路（ＶＬＳＩ）技術の規模など）では、設計者はコンピュータ支援技術を使用することが多い。複雑なデジタル回路の設計やシミュレーションを助けるためにデジタル回路を記述するハードウェア記述言語（ＨＤＬ）などの標準言語が開発されている。ＶＨＤＬやＶｅｒｉｌｏｇなどいくつかのハードウェア記述言語は、業界標準として発展している。ＶＨＤＬとＶｅｒｉｌｏｇは、抽象データ型を使用して、ゲート・レベル、レジスタ転送レベル（ＲＴＬ）、または動作レベルでハードウェア・モデルを定義する汎用ハードウェア記述言語である。デバイス技術の継続的な進歩に伴い、ＨＤＬをより新しいデバイスや設計様式とともに使用できるようにするための様々な製品設計ツールが開発されている。
【０００３】
ＨＤＬコードによる集積回路の設計の際、コードは、まず書き込まれ、次にＨＤＬコンパイラによってコンパイルされる。ＨＤＬソース・コードは、何らかのレベルで回路素子を記述し、コンパイラは、このコンパイルからＲＴＬネットリストを生成する。ＲＴＬネットリストは、一般に、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）や特定用途向け集積回路（ＡＳＩＣ）など、特定のベンダーの集積回路の技術／アーキテクチャに依存しないという点で、技術非依存型ネットリストである。ＲＴＬネットリストは、（動作表現に対して）回路素子の概略図に対応している。次いで、技術非依存型ＲＴＬネットリストから、ベンダーの技術／アーキテクチャでの回路の作成に使用できる技術固有のネットリストに変換されるように、マッピング・オペレーションが行われる。ＦＰＧＡベンダーが異なる技術／アーキテクチャを使用して集積回路内に論理回路を実装することはよく知られている。したがって、技術非依存型ＲＴＬネットリストがマッピングされて、特定のベンダーの技術／アーキテクチャに固有のネットリストが作成される。
【０００４】
このプロセスにおいてしばしば望ましい１つのオペレーションは、特定の集積回路のレイアウトを計画し、タイミング問題を制御し、集積回路の領域間の相互接続を管理することである。これは、時として「フロア・プランニング」と呼ばれることもある。一般のフロア・プランニング・オペレーションは、集積回路の回路エリアを時として「ブロック」と呼ばれる領域に分割し、ロジックをブロック内に存在するよう割り当てる。これらの領域は、四角形でも四角形でなくてもよい。このオペレーションには、ロジックの位置の推定誤差が集積回路のサイズからブロックのサイズに低減される（タイミング推定値(timing estimates)の誤差を低減する傾向がある）、また、配置配線が非常に大きい問題からより簡単な一連の問題に軽減されているので一般により早く稼動するという２つの効果がある。
【０００５】
リタイミング・アルゴリズムは、回路の設計を最適化するために使用されている。一般に、同期回路は、信号が、指定された数のブロック・サイクル以内（例えば１クロック周期内など）に、組み合わせパス、すなわちメモリ・セル、フリップフロップ、遅延素子などのレジスタを含まないパスに沿って、あるレジスタから別のレジスタに伝わるときのみ、適切に動作する。したがって、レジスタ間のパスにおける最大信号遅延（例えばパス上の組み合わせ演算素子の演算時間や配線遅延のためなど）は、回路が適切に働くことができる最小クロック周期を決定する。レジスタは、回路のパスに配置または再配置されて、パスにおける最大信号遅延を低減し、回路のクロック周期を低減させる。一般のリタイミング・アルゴリズムを使用して、回路のタイミング・モデルに基づいて回路内のレジスタのうちのいくつかを分配し直して、クロック周期を最低限に抑えることができる。
【０００６】
一般に、回路のタイミング・モデルは、組み合わせ演算ユニットと、遅延（レジスタによるなど）と、回路を構成する相互接続とのタイミング・モデルをひとまとめにすることによって取得される。相互接続遅延は、モデル化するのが難しく、したがってしばしば無視される。１つまたは複数の回路モジュールを含む回路システムの一般のタイミング・モデルは、モジュールの組み合わせ演算ユニットのタイミング・モデルの集約から生成される。
【０００７】
一般のリタイミング・アルゴリズム（例えば「ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．９１−１１８，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９に記載）は、データ・フロー・グラフに基づいて策定される。データ・フロー・グラフは、組み合わせ演算ユニットを表すノードと、それらを相互接続するエッジから成る。遅延（レジスタなど）は、エッジの重さとして表される。各ノードには、それに関連付けられている実行時間がある。
【０００８】
例えば、図２〜３は、リタイミング用のデータ・フロー・グラフを構築する従来技術の方法を示している。図２の組み合わせ演算ユニット（加算器２０５、乗算器２０７、２０９）は、演算ノード（例えば図３のノード２２５、２２７、２２９）として表される。組み合わせ演算ユニットでの実行時間は、ノードの演算時間によって表される。例えば、ノード２２５は２ｎｓの演算時間を有しており、この演算時間は加算器２０５によって必要とされ、ノード２２７、２２９のそれぞれは４ｎｓの演算時間を有しており、この演算時間は１つの乗算器（例えば２０９または２０７）によって必要とされる。エッジ２３１は、乗算器２０７と加算器２０５との間の接続を表す。エッジ２３１は、１の重さを有し、この重さはレジスタ２１７（またはレジスタ２１７による１クロック・サイクルのレイテンシ）を表す。同様に、エッジ２３３は、レジスタ２１５を表す１遅延を有する。エッジ２３５は、乗算器２０９と２０７との間の接続を表し、エッジ２３５に関連付けられている遅延はない。
【０００９】
データ・フロー・グラフにおけるクリティカル・パスとは、ゼロ遅延エッジ（組み合わせパス）を含むすべてのパスの中で最長の演算時間を有するパスである。例えば、図３で、ノード２２９からノード２２７へのパスは、ゼロ遅延を有するエッジ２３５を含み、ノード２２９からノード２２７へのパスは、演算時間が最も長くかかる（例えば８ｎｓなど。そのうちの４ｎｓはノード２２９、４ｎｓはノード２２７）。したがって、図２の回路の最小クロック周期は８ｎｓである。図３で、エッジ２３３における遅延をエッジ２３５に移動し、したがってクリティカル・パスがノード２２５と２２９との間のパスになり、演算時間がわずか６ｎｓで済むようにすることができる。したがって、遅延をエッジ２３３からエッジ２３５に移動させることは、レジスタ２１５を加算器２０５と乗算器２０９との間から乗算器２０９と２０７との間に移動させることによって実施することができ、これによって、変更された（リタイミングされた）回路は、低減されたクロック周期６ｎｓで動作することができる。
【００１０】
回路モジュールのタイミング・モデルを取得するための従来の手法は、モジュールを実際に構成するレジスタと組み合わせ演算素子とにモジュールを分解し、１つのノードを各組み合わせ演算素子に割り当てることである。一般に、ある設計における回路モジュールは、モジュールにおける組み合わせユニットと、それを接続するネットに対応する１組のノードとエッジに変換される。言い換えれば、各ハードウェア・モジュールのタイミング・モデルは、一般に、組み合わせ演算ユニットと、遅延と、ハードウェア・モジュールを構成する相互接続とのタイミング・モデルをひとまとめにすることによって構築される。特定のハードウェア・モジュールの変換で使用されるノードとエッジとの組の集約が、事実上そのハードウェア・モジュールのタイミング・モデル（データ・フロー・グラフ）となる。
【００１１】
リタイミング・アルゴリズムは、カットセットのリタイミングとパイプライニングを含む。さらに、データ・フロー・グラフを使用したクロック周期最小化のためのリタイミング・アルゴリズムが存在する。カットセットのリタイミング、パイプライニング、クロック周期最小化のためのリタイミングについてのこれ以上の詳細については、文献（“ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．９７−１０６，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９など）に記載されている。
【発明の開示】
【課題を解決するための手段】
【００１２】
ここでは、回路の階層的なリタイミングを行うための方法と装置について説明する。このセクションでは、本発明の一部の実施態様の要約について述べる。
【００１３】
本発明の少なくとも１つの実施態様では、（例えばモジュール・レベルでのリタイミングを介して）異なる複数の最小クロック周期を有するように異なる複数のレイテンシを備える回路のモジュールが設計される。一例では、モジュールの配置配線の後、詳細なタイミング分析から最小クロック周期が決定され、モジュールを含む回路のリタイミングの際に、回路の目的のクロック周期、および、レイテンシと最小クロック周期との間の相関に基づいてモジュールのデータ・フロー・グラフ表現が構築される。本発明の少なくとも１つの実施態様では、階層的なリタイミングが実行される。これは、回路の一部分がリタイミングされて（例えば異なるレイテンシについての）結果が生成され、その結果が目的のクロック周期に基づく回路全体のリタイミングに選択的に使用されるものである。
【００１４】
本発明の一実施態様では、回路モジュールを設計する方法は、異なる複数のレイテンシを備えるモジュールに対応する、モジュールの複数の回路設計を生成するステップと、複数の回路設計の実行可能なクロック周期を表すように、複数の回路設計の複数の許容できるクロック（例えば最小クロック周期など）を決定するステップと、複数の許容できるクロックを異なる複数のレイテンシに関連付けるための設計データを生成するステップとを含む。一例では、複数の回路設計のそれぞれを生成するために配置配線が実行され、設計レイアウトに基づく詳細なタイミング分析から、許容できるクロックが決定される。一例では、複数の回路設計のうちの第１のものが生成された後、パイプライン・レジスタ・セットが複数の回路設計のうちの第１のものに挿入されて、複数の回路設計のうちの第２のものが生成され、さらに、複数の回路設計の第２のものを生成するためにリタイミングが実行される。一例では、複数の回路設計のうちの第１のものと複数の回路設計のうちの第２のものは（例えば異なる処理ロジックまたは異なるロジック処理要素を有するなど）異なるアーキテクチャを有する。一例では、設計データは、さらに、複数の許容できるクロックに基づいて、異なる複数のレイテンシを、複数の回路設計の１つまたは複数のデータ・フロー・グラフ表現に関連付ける。一例では、モジュールの１つまたは複数のデータ・フロー・グラフ表現は、複数の許容できるクロックに基づいて、複数の回路設計を表すように生成される。例えば、複数の回路設計のうちの第１のものが非レジスタード入力(non-registered input)を含んでいる場合、１つまたは複数のデータ・フロー・グラフ表現は、複数の回路設計のうちの第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、この場合第１のパスは、レジスタを含んでおらず、非レジスタード入力に接続されており、例えば、演算ノードは、レジスタを含んでおらず、複数の回路設計のうちの第１のものの非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である第１のパスにおける信号遅延を表す。同様に、例えば、複数の回路設計のうちの第１のものが非レジスタード出力を含んでいる場合、１つまたは複数のデータ・フロー・グラフ表現は、複数の回路設計のうちの第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、この場合第１のパスは、レジスタを含んでおらず、非レジスタード出力に接続されており、例えば、演算ノードは、レジスタを含んでおらず、複数の回路設計のうちの第１のものの非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である第１のパスにおける信号遅延を表す。また、演算ノードは、レジスタを含んでおらず、複数の回路設計のうちの第１のものにおける非レジスタード入力と出力との間を接続する任意のパスにおける信号遅延以上である第１のパスにおける信号遅延を表すために使用することもできる。一例では、１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現は、複数の回路設計のうちの第１のものに対応しており、第１のグラフ表現は、複数の回路設計のうちの第１のもののレジスタから始まり、第１のもののレジスタで終わるすべての第１のパスを表すエッジを含んでおり、そのエッジにおける遅延は、複数の回路設計のうちの第１のもののレイテンシに関連する。一例では、エッジは、第１のノードと第２のノードとを接続して第１のパスを表す。この場合第１のノードと第２のノードは信号遅延をもたらさない。
【００１５】
本発明の一実施態様では、回路を設計する方法は、回路の設計の目的のクロックを選択するステップと、目的のクロックに基づいて、回路の一部分のデータ・フロー・グラフの表現を決定するステップと、データ・フロー・グラフの表現を使用して目的のクロックの設計をリタイミングするステップとを含む。一例では、データ・フロー・グラフの表現を決定する際に、目的のクロックに基づいて、データ・フロー・グラフのエッジにおいて必要な追加の遅延数が決定される。一例では、エッジは、データ・フロー・グラフの第１のノードと第２のノードとを接続し、エッジによって接続されている第１と第２のノードは、回路の一部分のレジスタから始まり、回路の一部分のレジスタで終了するパスを表す。第１のノードは、レジスタを含んでおらず、回路の一部分の第１の入力と回路の一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続され、第２のノードは、レジスタを含んでおらず、回路の一部分の第１の出力と回路の一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続され、データ・フロー・グラフは、レジスタを含んでおらず、回路の一部分の１つの入力を回路の一部分の１つの出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む。一例では、追加の遅延数を決定する際に、目的のクロックに従って回路の一部分に対してリタイミングが実行される。一例では、追加の遅延数は、追加の遅延数を回路の一部分の許容できるクロックに相関させる設計データから決定される。
【００１６】
本発明の一実施態様では、回路を設計する方法は、回路の設計の目的のクロックを選択するステップと、目的のクロックの回路の設計の一部分をリタイミングして第１の結果を生成するステップと、第１の結果を使用して目的のクロックの設計をリタイミングするステップとを含む。一例では、回路の設計の一部分をリタイミングするステップは、設計の一部分が目的のクロックで稼働できるように、いくつかのパイプライン・レジスタ・セットを設計の一部分に追加する（または削除する）ステップを含み、目的のクロックの設計をリタイミングするステップは、接続を使用して、リタイミングされる設計の一部分のレジスタ間のすべてのパスを表すステップを含む。この場合接続は、設計の一部分に追加されたパイプライン・レジスタ・セットの数を表すいくつかの追加の遅延を必要とする。一例では、接続は、第１のノードと第２のノードとを接続する。この場合第１のノードと第２のノードは信号遅延をもたらさない。一例では、目的のクロックの設計をリタイミングするステップは、入力演算ノードを使用して、レジスタを含んでおらず、設計の一部分の第１の入力と設計の一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、入力演算ノードが遅延のない接続を介して第１のノードに接続されるステップと、出力演算ノードを使用して、レジスタを含んでおらず、設計の一部分の第１の出力と設計の一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、出力演算ノードが遅延にない接続を介して第２のノードに接続されるステップと、第１の演算ノードを使用して、レジスタを含んでおらず、設計の一部分の第２の入力と設計の一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表すステップとをさらに含む。
【００１７】
本発明は、これらの方法を実行するデータ処理システムや、データ処理システム上で実行されるとシステムにこれらの方法を実行させるコンピュータ可読媒体を含めて、これらの方法を実行する方法と装置を含む。
【００１８】
本発明の他の特徴は、添付の図面や以下の詳細な説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１９】
本発明は、例示として示されており、添付の図面に限定されるものではない。図中、同様の参照番号は同様の要素を示す。
【００２０】
以下の説明と図面は、本発明の実例であり、本発明を限定するものと解釈されるべきではない。本発明を完全に理解できるようにするために、特定の詳細が多数記述されている。しかし、いくつかの場合、本発明の説明を不明瞭にするのを避けるために、よく知られている詳細、または従来の詳細は記述していない。本開示において一実施形態への言及は、必ずしも同じ実施形態を指すのではなく、こうした言及は少なくとも１つを意味する。
【００２１】
本発明の少なくとも１つの実施形態は、回路の一部分（例えば回路モジュールまたは回路ブロック）がクロック周期最小化のためにリタイミングされ、回路の一部分のリタイミングの結果に基づいて回路全体がリタイミングされる階層的方法を使用して回路設計のリタイミングを行おうとするものである。本発明の一実施形態では、モジュールのパラメトリック設計を取得してモジュールのタイミング・モデルを確立し、タイミング・モデルを使用して回路全体のリタイミングを行う。
【００２２】
本説明および特許請求の範囲では、レジスタとは、一般に順次素子（遅延素子、メモリ・セル、フリップフロップなど）を指す。レジスタは、回路のクロックとの同期の際に出力することができるように、入力信号をサンプリングし、保持（格納）する。さらに、データ・フロー・グラフのエッジにおける１遅延は、一般に対応するパス上のレジスタの存在によってもたらされるレイテンシの単位を表すことを理解されたい。しかし、レイテンシの単位は、メモリ・セルを読み取るための様々な制御信号など、他の手段を介して実装することもできる。
【００２３】
本発明の方法の多くは、従来の汎用コンピュータ・システムなど、デジタル処理システムで実行することができる。１つの機能のみを実行するように設計され、またはプログラムされている専用コンピュータを使用することもできる。
【００２４】
図１は、本発明とともに使用することができる一般のコンピュータ・システムの一例を示している。図１は、コンピュータ・システムの様々な構成要素を示しているが、こうした詳細は本発明と密接な関係はないので、構成要素を相互接続する任意の特定のアーキテクチャまたは方法を表すためのものではないことに留意されたい。また、構成要素が少ない、または場合によっては多いネットワーク・コンピュータや他のデータ処理システムも本発明とともに使用できることを理解されたい。図１のコンピュータ・システムは、例えば、Ｓｕｎワークステーション、あるいはＷｉｎｄｏｗｓ（登録商標）オペレーティング・システムまたはＡｐｐｌｅ Ｍａｃｉｎｔｏｓｈコンピュータを稼働させるパーソナル・コンピュータ（ＰＣ）とすることができる。
【００２５】
図１に示すように、データ処理システムの形態をしているコンピュータ・システム１０１はバス１０２を含んでいる。バスは、マイクロプロセッサ１０３、ＲＯＭ１０７、揮発性ＲＡＭ１０５、不揮発性メモリ１０６に結合されている。マイクロプロセッサ１０３は、図１の例に示すように、キャッシュ・メモリ１０４に結合されている。バス１０２は、これらの様々な構成要素をいっしょに相互接続し、また、これらの構成要素１０３、１０７、１０５、１０６は、表示コントローラと表示デバイス１０８に接続され、かつ、マウス、キーボード、モデム、ネットワーク・インターフェイス、プリンタ、スキャナ、ビデオ・カメラ、当分野でよく知られている他のデバイスなどの入力／出力（Ｉ／Ｏ）デバイスなどの周辺デバイスに相互接続される。一般に、入力／出力デバイス１１０は、入力／出力コントローラ１０９を介してシステムに結合される。揮発性ＲＡＭ１０５は、一般に、メモリ内のデータを最新の状態したり維持したりするために連続的に電力を必要とする動的ＲＡＭ（ＤＲＡＭ）として実装される。不揮発性メモリ１０６は、一般に磁気ハード・ドライブ、磁気光ドライブ、光ドライブ、ＤＶＤ ＲＡＭ、または電力がシステムから取り除かれた後もデータを維持する他のタイプのメモリ・システムである。また、一般に、不揮発性メモリは、ランダム・アクセス・メモリであるが、これは必須ではない。図１は、不揮発性メモリがデータ処理システムの構成要素の残りに直接結合されているローカル・デバイスであることを示しているが、本発明では、例えばモデムやＥｔｈｅｒｎｅｔ（登録商標）インターフェイスなどのネットワーク・インターフェイスを介してデータ処理システムに結合されているネットワーク記憶デバイスなどのシステムから離れている不揮発性メモリを使用してもよいことを理解されたい。バス１０２は、当分野で知られているような様々なブリッジ、コントローラ、および／またはアダプタを介して互いに接続されている１つまたは複数のバスをも含む。一実施形態では、Ｉ／Ｏコントローラ１０９は、ＵＳＢ周辺装置を制御するＵＳＢ（ユニバーサル・シリアル・バス）アダプタ、および／またはＩＥＥＥ−１３９４周辺装置を制御するＩＥＥＥ−１３９４バス・アダプタを含む。
【００２６】
本発明の形態を少なくとも一部にはソフトウェアに組み込むことができることがこの説明から明らかである。つまり、技術は、ＲＯＭ１０７、揮発性ＲＡＭ１０５、不揮発性メモリ１０６、キャッシュ１０４、またはリモート記憶デバイスなどのメモリに含まれる命令のシーケンスを実行するマイクロプロセッサなどのそのプロセッサに応答してコンピュータ・システムまたは他のデータ処理システムで実行することができる。様々な実施形態では、配線回路を、本発明を実施するためのソフトウェア命令との組み合わせで使用することができる。したがって、技術は、ハードウェア回路とソフトウェアとの任意の特定の組み合わせに限定されるものではなく、また、データ処理システムによって実行される命令の任意の特定のソースに限定されるものでもない。さらに、説明を簡潔にするために、この説明を通じて、様々な機能およびオペレーションは、ソフトウェア・コードによって実行される、またはソフトウェア・コードによってもたらされるものとして説明される。しかし、こうした表現が意味することは、こうした機能はマイクロプロセッサ１０３などのプロセッサによるコードの実行から生まれるということであることを当業者は理解されよう。
【００２７】
機械可読媒体を使用して、データ処理システムによって実行されるとシステムに本発明の様々な方法を実行させるソフトウェアとデータを格納することができる。この実行可能ソフトウェアとデータは、図１に示すように、例えばＲＯＭ１０７、揮発性ＲＡＭ１０５、不揮発性メモリ１０６、および／またはキャッシュ１０４を含む様々な場所に格納することができる。このソフトウェアおよび／またはデータの一部分は、これらの記憶デバイスのうちの任意のものに格納することができる。
【００２８】
したがって、機械可読媒体は、機械（コンピュータ、ネットワーク・デバイス、ＰＤＡ、製造ツール、１組の１つまたは複数のプロセッサを備える任意のデバイスなど）によってアクセス可能な形式で情報を提供（すなわち格納および／または送信）する任意の機構を含む。例えば、機械可読媒体は、書き込み可能／書き込み禁止媒体（読み取り専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ・デバイスなど）、および電気、光、音響または他の形式の伝搬信号（搬送波、赤外線信号、デジタル信号など）などを含む。
【００２９】
回路の一般のタイミング・モデルは、組み合わせ演算素子のタイミング・モデルの集合である。組み合わせ演算素子のタイミング・モデルは回路のクロック周期に依存しない。従来の方法は、回路モジュールの組み合わせ演算素子のタイミング・モデルを集約して、回路のクロック周期に依存しない回路のタイミング・モデルを生成する。
【００３０】
タイミング・モデルが組み合わせ演算素子のタイミング・モデルの集約から構築されるとき、結果として得られたデータ・フロー・グラフにおける組み合わせ演算素子を表すノードの数は非常に多い。また、この種のタイミング・モデルは不正確であることが多い。というのは、モジュール内相互接続遅延（配線遅延など）は一般に無視されるからである。また、組み合わせ演算素子のタイミング・モデルは遅延の実装前推定値を使用するため、不正確である。
【００３１】
一般のリタイミング・アルゴリズムは、Ｏ（ｎ3）の複雑さを有している。この場合、ｎは、従来の方法における組み合わせ演算素子の数に対応するデータ・フロー・グラフでのノードの数である。したがって、ゲート・レベルのタイミング・モデルの使用によって、システム・レベルのリタイミングでの演算の法外な複雑さがもたらされることが多く、一方で、モジュール内相互接続遅延などが無視されるため、また実装前推定値を使用するため、依然として回路のタイミング動作の不正確なモデルが生み出される可能性がある。
【００３２】
本発明の一実施形態では、事前に設計されたハードウェア・モジュールの結合によってシステム・レベルの回路を生成し、リタイミングを改善し、加速するために、タイミング・モデルをこうしたモジュールごとに構成する。本発明の実施形態によるタイミング・モデルは、リタイミングの目的でモジュールのタイミング動作を正確に表しながら、データ・フロー・グラフで使用されるノードの数を最低限に抑える。所与のハードウェア・モジュールの簡単だが有効なタイミング・モデルがシステマチックな方法で構築される。一般に、回路（サブ回路、または回路の１ブロックなど）の一部分を、類似のやり方で回路モジュールとして扱うこともでき、その簡略化されたタイミング・モデルを、本発明の実施形態に従って構成することができる。したがって、クロック周期最小化のための回路のリタイミングは、本発明の実施形態に従って、階層的なやり方で実行することができる。従来の手法では、回路システムのクロック周期最小化は、予め定められている設計とロジック（例えば予め定められているレイテンシおよび予め定められている最大遅延など）をそれぞれ有する組み合わせ演算素子に対応するノードを備えるデータ・フロー・グラフを使用する。本発明の少なくとも１つの実施形態による階層的な手法では、クロック周期最小化は、回路システムの１つまたは複数のモジュール（またはサブ回路）のタイミング・モデルに基づいて実行され、モジュールの各タイミング・モデルは、複数の設計パラメータ（様々なレイテンシ、様々な設計アーキテクチャ、モジュールの様々な最小クロック周期など）を備えるモジュールのクロック周期最小化から取得され、モジュールのタイミング・モデルは、複数の設計パラメータを反映する。一実施形態では、モジュールのタイミング・モデルにおける少なくとも１つのパラメータ（例えば最小レイテンシ）は、回路システムの目的のクロック周期に従って決定される。以下で、本発明の実施形態の詳細についてさらに説明する。
【００３３】
一部のハードウェア・モジュール（ＦＩＲフィルタなど）とサブ回路は一般に、レイテンシを速度と交換することができる。言い換えれば、レジスタをモジュールに「投入」することによってハードウェア・モジュールを加速させ、クロック周期を低減させることができる。
【００３４】
本発明の一実施形態では、ハードウェア・モジュールのタイミング・モデルは、モデルの詳細な実装からデータを使用して構築される。このデータは、モジュールに供給するレジスタの数を増やしていき、ハ―ドウェア・モジュールをリタイミング（および最適化）し、新しいレジスタが追加されるとモジュール内のクリティカル・パスを検出してモジュールの最小クロック周期を決定することによって取得される。本発明の一実施形態では、モジュールの最小クロック周期は、（例えば配置配線後のタイミング分析を使用して）詳細な設計レイアウトから取得される。
【００３５】
出力設計のクロック速度は、例えばクロック周期最小化の既知のリタイミング・アルゴリズムを適用することによって最大化することができる（“ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．１００−１０６，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９）。これらのリタイミング・アルゴリズムは、データ・フロー・グラフ上で策定される。ハードウェア・モジュールは、しばしばレジスタやメモリを含んでおり、単一のノードとして直接適しない。したがって、これらは、そのタイミング動作を十分に表すように、ノードとエッジとの組み合わせに変換される。ノードとエッジが多すぎて最適化アルゴリズムに負担をかけることがないようにするために、本発明の一実施形態による変換／モデリングは、ノードとエッジをできるだけ少なくし、非常に簡単だが十分なタイミング・モデルを提供する。以下で、ハードウェア・モジュール設計からノードとエッジとの組み合わせにシステマチックに変換するための方法を示す詳細な例について説明する。
【００３６】
図４〜図５は、本発明の一実施形態によるレジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。図４は、ｎ個のレジスタード入力とｍ個のレジスタード出力を備えるハードウェア・モジュールを示しており、入力Ｉ1（３０１）、Ｉ2（３０２）、．．．、Ｉn（３０９）は、それぞれレジスタ３１１、３１２、．．．、３１９の直接入力であり、出力Ｏ1（３３１）、Ｏ2（３３２）、．．．、Ｏm（３３９）は、レジスタ３２１、３２２、．．．、３２９からの直接出力である。ロジック３４３は、モジュール３４１の入力３０１〜３０９から出力３３１〜３３９を算出するためのロジック素子のネットワークを表す。追加のｉ組のパイプライン・レジスタが（例えば既知の任意のアルゴリズムを使用してパイプライニングを行う、または設計者によりレジスタを挿入する、またはモジュールの変更された仕様に従って設計者によりモジュールの代替の設計を使用するなど）、ハードウェア・モジュールに「投入」されているとき、ｃjは、モジュール内のクリティカル・パスに沿った遅延を示すと仮定する。１組のパイプライン・レジスタは、モジュールの正方向送りカットセットにある１組のレジスタである。従来のパイプライニング・アルゴリズムを使用して、１組または複数組のパイプライン・レジスタを挿入することができる。値｛ｃ0，ｃ1，．．．，ｃL｝は、任意の既知の方法によって算出することができ、Ｌは、挿入されたパイプライン・レジスタの組の最大数である。パイプライン・レジスタが挿入された後でクリティカル・パス遅延を最低限に抑えるためにリタイミングまたは最適化が行われるため、一般にｃ0＞ｃ1，＞．．．，＞ｃLであると理解されたい。本発明の一実施形態では、クリティカル・パスに沿った遅延は、モジュールが配置され、配線された後でタイミング分析から算出することができる。しかし、遅延は、合成ツールの一般的な方法を使用して推定することもできるが、こうした遅延推定は、一般に、配置配線後のタイミング分析から取得されるものほど正確ではない。本発明の一実施形態によるタイミング・モデルは、１組の値｛ｃ0，ｃ1，．．．，ｃL｝と図５に示すようなデータ・フロー・グラフ表現を含む。
【００３７】
図５では、演算ノードＢi（３５３）とＢ0（３５５）は、ゼロ演算時間を有する。エッジ３５１では少なくとも１つの遅延があり、したがってエッジ３５１は、クリティカル・パスの一部ではあり得ない。この説明から、実行可能性条件(feasibility condition)がシステムの目的のクロックに従って適切に設定されており、エッジ３５１がクリティカル・パスの一部として含まれていない場合、エッジ３５１での遅延回数を任意の数に設定することができることは明らかである。パイプライン・レジスタの追加の組がないモジュールが回路で使用されており、回路のクロックが｛ｃ0，ｃ1，．．．，ｃL｝の値の組からｃ(i-1)＞ｃ＞ｃiとなるような場合、少なくともｉ組のパイプライン・レジスタがモジュールに挿入される場合はモジュールが適切に働くことを理解されたい。したがって、図５のグラフの実行可能性の制約(feasibility constraint)では、エッジ３５１は、適切に働くようにするために、リタイミング・オペレーションに遅延をもうｉ個求めることを示している。こうした制約は、エッジから移動させることができる遅延の最大数を示すデータ・フロー・グラフの一般のエッジに対する実行可能性の制約に非常に似ている。一般のリタイミング・アルゴリズムを使用するには、ｃ(i-1)＞ｃ＞ｃiである場合、エッジ３５１の実行可能性の制約を、エッジから移動させることができる遅延の最大数が−ｉであることとして表すことができる。
【００３８】
したがって、レジスタードＩ／Ｏを備えるモジュール（３４１）データ・フロー・グラフ表現は、２つのノードＢi（３５３）、Ｂ0（３５５）と、これらの２つのノードを接続するエッジ（３５１）を有する。これらのノードの演算時間は０である。エッジの実行可能性の制約は、回路のクロック周期に依存する。モジュールがより大きい設計の構成要素として使用されるとき、タイミング・モデルは、次のようにリタイミングに使用することができる。
【００３９】
１．図５のデータ・フロー・グラフを使用して、設計全体のデータ・フロー・グラフを作成する際のモジュールを表す。
【００４０】
２．ｃは設計全体を対象としたクロック周期と仮定する。（Ｌ＋１）組のパイプライン・レジスタをモジュールに追加することでは、ｃL未満のモジュールの最小クロック周期を低減することができないことを前提として、ｃ＜ｃLである場合、目的のクロック周期ｃは設計に適していないという結論に達する。
【００４１】
３．ｃ≦ｃLの場合、エッジ３５１の実行可能条件を決定する。例えば、ｉ＝１，２，．．．，Ｌであるときにｃi＜ｃ＜ｃ(i-1)の場合、エッジには追加の遅延が少なくともｉ個必要である。ｃ＞ｃ0である場合、エッジには追加の遅延は必要ない。次いで既知のアルゴリズムを使用して、データ・フロー・グラフを使用した設計全体のリタイミングを行うことができる。例えば、“ＶＬＳＩ Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ：Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”ｂｙ Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ，ｐｐ．９１−１１８，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９９のリタイミング・アルゴリズムでは、値ｒ（Ｂi）とｒ（Ｂ0）は、ノードＢi、Ｂ0について解かれ、したがってリタイミングした後、エッジ３５１での遅延数がｗからｗr＝ｗ＋ｒ（Ｂ0）ｒ（Ｂi）に変わる。したがって、エッジ３５１の実行可能性条件は、ｃi＜ｃ＜ｃ(i-1)の場合はｒ（Ｂi）−ｒ（Ｂo）＜−ｉ、ｃ＞ｃ0の場合はｒ（Ｂi）−ｒ（Ｂ0）＜０となり、またｃ＜ｃLの場合は実行できない。
【００４２】
４．実行可能なリタイミングの解が見つかった場合、モジュールのインスタンス化の間にｒ（Ｂ0）−ｒ（Ｂi）組のパイプライン・レジスタをモジュールに追加する。
【００４３】
図４、図５に示した例は、モジュールのすべての入力ライン（またはすべての出力ライン）を介して１組または複数組のパイプライン・レジスタがモジュールに「投入」される状況を示している。しかし、モジュールのクロック周期は、モジュールの入力（または出力）ラインのうちの１つまたは一部分を介してレジスタに「投入」することによって最低限に抑えることもできることを理解されたい。例えば、図４のモジュールのクロック周期は、１つのレジスタを入力Ｉ1（３０１）に追加し、変更されたモジュールをリタイミングしてクロック周期を最低限に抑えることによって低減させることができる。入力および／または出力ラインの一部分のリタイミングによるこうしたレイテンシの変化を反映させるために、レジスタードＩ／Ｏを備えるモジュールのより全体的なデータ・フロー・グラフは、入力Ｉ1，Ｉ2，．．．，ＩnとＢiとの間、および出力Ｏ1，Ｏ2，．．．，ＯmとＢoとの間を接続するゼロ処理時間ノードを含むことができる。これらのゼロ処理時間ノードをＢi、Ｂoに接続する各エッジは、少なくとも１つの遅延を有しており、モジュールの対応する入力ラインまたは出力ラインを介して「投入」されたレジスタに対応する数を示すために、追加の遅延をいくつか必要とする。あるいは、同じ数のレジスタが入力ラインの一部分に「投入」されるとき、これらの入力ラインは、単一のゼロ処理時間ノードに接続される。これは次いで、システム全体のリタイミングの際に少なくとも同じ数の遅延を必要とするエッジを介してノードＢiに接続される。独立してリタイミングすることができる入力と出力の部分は、タイミング・モデル・トポロジを決定する。さらに独立性を許容することによって、結果的により複雑なモデルが得られる。さらに、同じ数のレジスタに「投入」するために、様々なモデルを構築することができる。この説明から、異なるレイテンシを備えるモジュールのリタイミングに基づいて、簡略化されたデータ・フロー・グラフの多くの変形を構築することができることを理解されたい。実行可能性条件は、回路システムの目的のクロックに従って設定される。
【００４４】
モジュールの入力および／または出力がレジスタードではないとき、本発明の一実施形態によるリタイミング・モデルは、１）非レジスタード入力ごとの入力から任意のモジュール内レジスタへの最大遅延、２）非レジスタード出力ごとの任意のモジュール内レジスタから出力への最大遅延、３）入力−出力対ごとの任意の純粋な組み合わせパスにおける最大入力対出力遅延を考慮に入れる。純粋な組み合わせパスは、クロックト・レジスタ(clocked register)を含まないことを理解されたい。
【００４５】
これらの最大遅延値は、パイプライン・レジスタの追加の組の数に依存する可能性があり、したがって、実行可能性条件がそうであると同様に、目的のクロック周期に依存する可能性があることに留意されたい。
【００４６】
図６〜図７は、本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。図６では、入力４０１、４０２はレジスタードではなく、出力４３１はレジスタードではなく、入力４０１から出力４３１への少なくとも１つの純粋な組み合わせパスがある。ネットワーク４４５、４４７、４４９は、レジスタを有してない純粋な組み合わせネットワークを表す。
【００４７】
図７は、本発明の一実施形態によるモジュール４４１のデータ・フロー・グラフの一例を示している。図７では、ノード４５３、４５５とエッジ４５１は、モジュール４４１のレジスタード部分を表しており、これには、ネットワーク４４３を介したレジスタ４１１〜４１９、およびレジスタ４２１〜４２９の間のすべてのパスが含まれている。ノードＡ2i（４６１）は、入力Ｉ2（４０２）とレジスタ４１２との間のパスを表し、ノ―ドＡ1i（４６３）は、入力Ｉ1（４０１）とレジスタ４１１との間のパスを表し、ノードＡ1o（４７１）は、レジスタ４２１と出力Ｏ1（４３１）との間のパスを表し、ノードＡ1l（４５７）は、ネット４４０を介した入力Ｉ1（４０１）と出力Ｏ1（４３１）との間のパスを表す。ノードＢ1i（４６５）は、ノードＡ1i（４６３）とＡ1l（４５７）の入力Ｉ1への適切な接続を容易にする。同様に、ノ―ドＢ1o（４７３）は、ノードＡ1l（４５７）とＡ1o（４７１）を出力Ｏ1に接続する。図７では、ノードＢ1i、Ｂ1o、Ｂi、Ｂoは、接続を容易にするために使用されるため、ゼロの処理時間を有し、ノードＡ2i、Ａ1i、Ａ1l、Ａ1oは純粋な組み合わせパスを表すため、ノードによって表されるすべてのパスの中の最大遅延に等しい処理時間を有する。例えば、Ａ1i（４６３）は、入力Ｉ1（４０１）からレジスタ４１１への最大遅延に等しい処理時間を有し、Ａ2i（４６１）は、入力Ｉ2（４０２）からレジスタ４１２への最大遅延に等しい処理時間を有し、Ａ1o（４７１）は、レジスタ４２１から出力Ｏ1（４３１）への最大遅延に等しい処理時間を有し、Ａ1l（４５７）は、（ネットワーク４４０を介して）入力Ｉ1（４０１）から出力Ｏ1（４３１）への最大組み合わせ遅延に等しい処理時間を有する。
【００４８】
一般に、モジュールのレジスタへの入力は、モジュールの１つまたは複数の入力からの結果とすることができることを理解されたい。同様に、モジュールのレジスタからの出力は、モジュールの複数の出力に関与し得る。図８〜図９は、本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する別の例を示す図である。図８では、入力Ｉ1（５０１）とＩ2（５０２）は、レジスタ５１１に至る１つまたは複数の純粋な組み合わせパスを有している。ネットワーク５４５は、レジスタを含んでいない。入力Ｉ1（５０１）とレジスタ５１１との間のすべての組み合わせパスは、図９のノードＡ1i（５６３）によって表されており、入力Ｉ2（５０２）とレジスタ５１１との間のすべての組み合わせパスは、図９のノードＡ2i（５６１）によって示されている。図９では、Ａ1i（５６３）Ａ2i（５６１）の処理時間は、組み合わせネットワーク５４５を介したそれぞれ入力Ｉ1（５０１）とＩ2（５０２）からレジスタ５１１への最大遅延である。
【００４９】
レジスタードＩ／Ｏを備えるモジュールと同様に、非レジスタードＩ／Ｏを備えるモジュールのクロック周期を、入力ラインと出力ラインの一部分を介してレジスタに「投入」することによって低減することもできる。入力ラインと出力ラインの一部分のこうしたレイテンシの追加は、レジスタードＩ／Ｏを備えるモジュールについて上述したものに似た方法で、モジュールのレジスタード部分（例えばノードＢi５３３とＢo５５５）を表すノードに接続されているエッジ上で指定することができる。
【００５０】
さらに、一般に、モジュールの入力は、異なるレジスタへの組み合わせパスを有していてもよく、モジュールの出力は、純粋な組み合わせパスを介して複数のレジスタからの関与を得ることができることを理解されたい。一般に、単一ノードを使用して、レジスタを有しておらず、モジュールの１つの入力からモジュールの任意のレジスタにそれぞれ向かうすべてのパスを表すことができ、単一ノードの演算時間は、ノードによって表されるすべてのパスの中の最大遅延である。同様に、単一ノードを使用して、レジスタを有しておらず、モジュールの任意のレジスタからモジュールの１つの出力にそれぞれ向かうすべてのパスを表すことができる。さらに、単一ノードを使用して、レジスタを有しておらず、モジュールの１つの入力からモジュールの１つの出力にそれぞれ向かうすべてのパスを表すことができる。
【００５１】
図１０〜１６は、本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【００５２】
図１０は、最小レイテンシを有するモジュールを示す図であり、図１１は、本発明の一実施形態による図１０のモジュールのデータ・フロー・グラフを示している。図１１では、ノードＢi（７０３）、エッジ７０１、ノードＢo（７０５）は、図１０のレジスタ間のすべてのパス（例えば加算器６３５を経由する図１０のレジスタ６３１からレジスタ６３３まで）を表している。ノード７１１は乗算器６２１を表し、ノード７１３、７１５は乗算器６２３と加算器６３５を表し、ノード７１７、７１９は乗算器６２５と加算器６３７を表す。図１１では、入力Ｉからノード７０３への２つのパスがあり、これは、図１０の入力Ｉ（６０１）から内部レジスタ６３１、６３３のモジュールへの異なる組み合わせパスを表していることに留意されたい。これらのパスは、パスにおける最長遅延に等しい処理時間を有する単一ノードによって表すことができる。図１２は、データ・フロー・グラフのこうした表現を示しており、ノードＡi（７２１）は、図１０における入力Ｉから任意の内部レジスタのモジュールへの最長の組み合わせ遅延を表している。一実施形態例では、データ・フロー・グラフの表現は、ノード（ロジックを表す）と、ノード間のリンクを含む。さらに、ノード７２３は、乗算器６２５と加算器６３７を通るパスにおける遅延である、任意の組み合わせパスを通る入力Ｉ（６０１）から出力Ｏ（６０３）への最長遅延を表す。ノードＡｏ（７２５）は、加算器６３７を通るレジスタ６３３から出力Ｏ（６０３）へのパスを表す。ノード７０３、７０５は、ゼロ処理時間を有し、ノード７２１と７０３との間と、ノード７０５、７２５との間のエッジは遅延がなく、したがってノード７０３、７０５は、ノード７２１、７２５にそれぞれマージされる（この例では図１２におけるノードＢi（７０３）とＢo（７０５）が冗長であるため）ことに留意されたい。図１０のモジュールのクリティカル・パスを識別した後、モジュールの最小クロック周期Ｃoが決定される。
【００５３】
図１０のモジュールにもう１つ分のクロック・サイクルのレイテンシが許可されているとき、パイプライン・レジスタ・セット（例えば図１３のレジスタ６４１、６４３、６４５など）を追加することができる。（例えば図１３の設計を生成するために）もう１つ分のクロック・サイクルのレイテンシを備えるモジュールのクロック周期を最低限に抑えるために、リタイミングや最適化を実行することができる。次いで図１４に示したようなデータ・フロー・グラフを、図１３のモジュールのために構築することができる。図１４では、ノード７３１は、入力６０１から乗算器６２１、６２３、６２５を通るパスを表し、ノード７３５は、加算器６３７を通るレジスタ６３３、６４５から出力６０３へのパスを表している。図１０のモジュールに対して、図１３のモジュールは、もう１組のパイプライン・レジスタ（もう１つ分のクロック・サイクルの遅延時間）を必要とし、したがって、図１４のデータ・フロー・グラフにおけるエッジ７０１は、図１２のデータ・フロー・グラフにおけるエッジ７０１に対して１つ多くの遅延を必要とする。図１３のモジュールのクリティカル・パスを識別した後、もう１つ分のクロック・サイクルのレイテンシを含むモジュールの最小クロック周期Ｃ1が決定される。図１４のノードＢi（７０３）、Ｂo（７０５）は、この例では冗長であり、取り除くこともできることに留意されたい。
【００５４】
レジスタ６５１、６５３とレジスタ６４１、６４３、６４５が図１５のようにモジュールに追加されると、モジュールは、レジスタードＩ／Ｏを備えるモジュールになる。したがって、図１５のモジュールは、図１６のデータ・フロー・グラフによって表すことができる。図１６のエッジ７０１は、図１２のエッジ７０１に対して３つ多い遅延を必要とする。同様に、図１５のモジュールのクリティカル・パスを識別した後、もう３つ分のクロック・サイクルのレイテンシを含むモジュールの最小クロック周期Ｃ3が決定される。
【００５５】
図１２、図１４、図１６のデータ・フロー・グラフは、モジュールを含む回路のリタイミングの際に、目的のクロック周期ｃに従って選択的に使用することができる。例えば、ある回路で図１０のモジュールが使用されており、Ｃ1＜Ｃ＜Ｃ0であるとき、少なくとももう１つ分のクロック・サイクルのレイテンシがモジュールに「投入」されることが求められ、したがって、図１４のデータ・フロー・グラフは、回路全体のクロック最小化のためのリタイミングに使用され、図１４のエッジ７０１の実行可能性条件は、エッジ７０１には１つ多い遅延が必要（またはエッジ７０１から取り除くことができる最大遅延は−１）であることであることを理解されたい。しかし、この回路で図１３のモジュールが使用されており、Ｃ＞Ｃ0である場合、追加の１つ分のレイテンシをモジュールから移動させることができ、したがって図１２のデータ・フロー・グラフを使用することができ、図１２のエッジ７０１の実行可能性条件は、最大１つの遅延をエッジ７０１から移動させることができることであることを理解されたい。
【００５６】
ＩＰモジュールが設計で使用されるとき、ユーザは、ＩＰモジュールで使用すべきレイテンシの量を指定することができる。したがって、リタイミング最適化エンジンに入力される設計は、そのＩＰモジュールの最低必要レイテンシより長いレイテンシを有するＩＰモジュールを有することができる。例えば、入力された設計が２つのパイプライン・レジスタを有するＦＩＲフィルタ・モジュールを含んでいてもよい。モジュールの元の指定されたレイテンシが考え得る最小レイテンシより長いとき、モジュールのデータ・フロー・グラフの制約の構築で、追加のレイテンシが考慮される。例えば、実行可能性条件は、必要に応じて回路の別の部分に移すことができる追加のレイテンシを示すように調整することができる。代替の手法を使用することもできることに留意されたい。例えば、追加のレイテンシは、モジュールの出力（または入力）ポートから始まるエッジにおける移動可能な重さ（遅延）として指定することができる。
【００５７】
図１７は、本発明の一実施形態による回路をリタイミングする方法を示す図である。オペレーション８０１が回路の一部分（ブロックやモジュールなど）を受信した後、オペレーション８０３は、回路の一部分の複数の変形の複数の許容できるクロック（例えば最小クロック周期または最大クロック周波数など）を決定する。回路の一部分の複数の変形のそれぞれは、その回路の一部分の少なくとも一部の入力と出力のタイミングがその回路の一部分とは異なる。例えば、回路の一部分の１つの変形は、１つまたは複数のレジスタ（正または負のレイテンシを備える）を、回路の一部分の入力ラインと出力ラインの少なくとも一部分に追加し、回路の一部分のリタイミングを実行することに等しい。オペレーション８０５は、複数の許容できるクロックを使用して回路をリタイミングする。例えば、（例えば入力ラインと出力ラインの一部分を介して）モジュールに「投入」する必要のある最低数のレイテンシ（遅延）は、複数の許容できるクロックと、回路の目的のクロックから決定される。
【００５８】
図１８は、本発明の一実施形態による回路モジュールを設計する方法を示す図である。オペレーション８１１は、回路（モジュールまたはブロックなど）の許容クロック（最小クロック周期または最大クロック周波数など）を決定する。オペレーション８１３は、パイプライン・レジスタ・セットを回路に追加することによって回路を変更する。代わりに、１組のレジスタは、モジュールの入力ラインと出力ラインの一部分を介してモジュールに「投入」することができる（例えば入力ラインと出力ラインの一部分にレジスタを追加し、追加されたレジスタを備えるモジュールを最適化するようリタイミングする）。オペレーション８１５は、変更された回路の許容クロックを決定する。オペレーション８１７が、モジュールのクロックを低減するためにパイプライン・レジスタをもう１組追加すべきである（または、モジュールのクロック周期を最低限に抑えるためにより多くのレジスタをモジュールに「投入」することができる）と決定すると、オペレーション８１３、８１５は、モジュールの異なる変形を得るために繰り返される。オペレーション８１９は、所与のクロックが回路に許容可能になるように回路に追加することができるパイプライン・レジスタ・セットの数を決定するために、追加されたパイプライン・レジスタ・セットの数を許容クロックに関連付ける。したがって、モデルが設計に使用されているとき、目的のクロックを実行可能にするために回路に追加することができる最低数のパイプライン・レジスタ・セットを決定することができる。あるいは、モジュールの入力ラインと出力ラインの一部分を介してモジュールに「投入」することができるレジスタの最低数は、モジュールの変形と対応する最小クロック周期との間の関係から決定することができる。クロック最小化のために、異なる数のレジスタを、モジュールの入力ラインと出力ラインの異なる部分を介してモジュールに「投入」することができ、次いで、回路の目的のクロックを達成するためにモジュールに「投入」することができる最低数のレジスタを、モジュールに「投入」されたレジスタの数と対応する最小クロック周期との間の相関から決定することができる。
【００５９】
図１９は、本発明の一実施形態によるレジスタードＩ／Ｏを備えるモジュールを備える回路をリタイミングする方法を示す図である。オペレーション８３１は、レジスタード入力と出力を備える回路の一部分を決定する。回路の一部分への各入力は、レジスタに対する直接入力であり、回路の一部分の各出力は、レジスタからの直接出力である。オペレーション８３３は、回路のデータ・フロー・グラフにおけるエッジによって接続された２つのノードを備える回路の一部分を表し、２つのノードのそれぞれは、ゼロ演算時間を必要とし、エッジにおいて必要な追加の遅延数は、回路の様々な許容クロックと回路に挿入された様々な遅延数との間の関係に従って、回路の目的のクロックによって決定される。回路の様々な許容クロックと様々な遅延数との間の関係は、システム・レベルでの回路のリタイミングの開始前、またはシステム・レベルでの回路のリタイミングのプロセス中に決定することができる。オペレーション８３５は、データ・フロー・グラフを使用して回路をリタイミングする。
【００６０】
図２０は、本発明の一実施形態による回路を設計する詳細な方法を示す図である。オペレーション９０１は、追加の遅延のない回路モジュールを生成する。オペレーション９０３は、モジュールに挿入される追加の遅延数をゼロに設定する。オペレーション９０５は、モジュールの配置配線を行う。オペレーション９０７は、（例えば静的タイミング分析またはタイミング・シミュレーションなどから）モジュールの最小クロック周期を決定する。オペレーション９０９は、モジュールのデータ・フロー・グラフの生成を開始する。モジュールの入力ごとに、オペレーション９１１は、モジュールの任意の純粋な組み合わせパスにおける入力と任意のレジスタとの間の最大入力遅延を決定し、（最大入力遅延がゼロでない場合）最大入力遅延に等しい演算時間を有する入力演算ノードによる最大入力遅延をモジュールのデータ・フロー・グラフに表す。モジュールの出力ごとに、オペレーション９１３は、モジュールの任意の純粋な組み合わせパスにおける出力と任意のレジスタとの間の最大出力遅延を決定し、（最大出力遅延がゼロでない場合）最大出力遅延に等しい演算時間を有する出力演算ノードによる最大出力遅延をデータ・フロー・グラフに表す。オペレーション９１５は、遅延無しのエッジを使用して、モジュールへの入力を、入力演算ノードを介してデータ・フロー・グラフにおける第１のノードに接続する（対応する最大入力遅延がゼロではない場合。そうでない場合は、第１のノードに直接接続する）。オペレーション９１７は、遅延無しのエッジを使用して、モジュールの出力を、出力演算ノードを介してデータ・フロー・グラフにおける第２のノードに接続する（対応する最大出力遅延がゼロではない場合。そうでない場合は、第２のノードに直接接続する）。オペレーション９１９は、第１と第２のノードを、遅延のあるエッジに接続する。エッジが必要とする追加の遅延数は、データ・フロー・グラフに挿入されるパイプライン・レジスタの少なくとも追加の組の数である。オペレーション９２１は、入力と出力の対ごとに、レジスタを含んでおらず、入力と出力の対を接続するモジュールにおける任意のパスの最大遅延を決定し、（こうしたパスが存在する場合）入力と出力の対を、データ・フロー・グラフにおける遅延のないエッジに直接接続する演算ノードとして最大遅延を表す。オペレーション９２３は、回路のデータ・フロー・グラフを最小クロック周期と、回路に挿入された追加の遅延数に関連付ける。オペレーション９２５が（例えばパイプライン・レジスタ・セットを挿入することによって）追加の遅延を追加することを決定した場合、オペレーション９４１は、モジュールに挿入される追加の遅延数を１つずつ増やし、オペレーション９４３は、（例えばパイプライン・レジスタ・セットを挿入し、最適化を実行することによって）回路モジュールを変更する。追加のレイテンシ（または遅延）は、入力ラインと出力ラインの一部分を介してモジュールに「投入」することもできることに留意されたい。
【００６１】
異なるレイテンシを備えるモジュールの変形の様々な設計が取得された後、オペレーション９２７は、回路においてモジュールを使用する。オペレーション９２９は、回路のクロック周期を選択する。オペレーション９３１は、モジュールの最小クロック周期と追加の遅延数との間の関係に従って、選択されたクロック周期を達成するために、モジュールによって必要とされる最小余分遅延を決定する。オペレーション９３３は、最小余分遅延がモジュールに挿入されたとき、モジュールのデータ・フロー・グラフを使用して回路のデータ・フロー・グラフにモジュールを表す。オペレーション９３５は、回路のデータ・フロー・グラフを使用して、リタイミング・オペレーションを実行する。この場合、制約は、挿入された最小余分遅延を示す。モジュールの最小余分遅延数は、制約の形式で、リタイミング・オペレーション全体に組み込まれる。例えば、データ・フロー・グラフのエッジの実行可能性の制約は、少なくとも最小余分遅延がリタイミング・オペレーションでエッジに移動されることを求める（またはエッジのリタイミング・オペレーションで移動させることができる遅延の数は、挿入された最小余分遅延に等しい大きさの負の数である）。オペレーション９３７は、回路に異なるクロック周期を選択するかどうかを決定する。例えば、選択されたクロック周期がリタイミングの後に実行可能である場合、クロック周期の低減を選択することができ、回路に選択されたクロック周期に使用できる実行可能な解がない場合、目的のクロック周期は増える。オペレーション９２９〜９３５は、回路のクロックが最低になるまで繰り返すことができる。
【００６２】
本発明の一実施形態において、モジュールは、異なるレイテンシと最小クロック周期（異なるレイテンシと速度）を備える複数の設計を有する。異なるレイテンシと速度を備えるモジュール設計を取得するために、レジスタが１つのモジュール設計の入力（または出力）ラインの少なくとも一部分に追加された後、リタイミングと最適化を実行することができる。一般に、リタイミングと最適化は、モジュール設計のアーキテクチャを変更しないことを理解されたい。しかし、異なる設計アーキテクチャを使用して異なる方法でモジュールを実施して、異なるレイテンシと速度を備えるモジュール設計を生成することができ、必要な速度とレイテンシ（および存在する場合は他の要件）に基づいて、システム・レベル・アルゴリズムを、異なるアーキテクチャのこれらの異なる設計の中から選択することができる。異なるアーキテクチャが使用される場合、異なる設計は、異なるロジック・オペレーション素子を含み、異なる設計は、異なる処理ロジックを有し得る。例えば、図２１は、８ビットの加算器（１０１１、１０１３）を含む１６ビットの加算器（１００１）の設計例を示している。入力Ｘ（１００３）とＹ（１００５）の最下位８ビット（ＸLおよびＹL）の合計の桁上げ出力ビット(carry out bit)は、ライン１０１５を介して加算器１０１３に入力され、加算器１０１３は、入力Ｘ（１００３）とＹ（１００５）の最上位８ビット（ＸM、ＹM）と加算器１０１１からの桁上げ出力ビットを合計する。図２２は、加算器１０１１の桁上げ出力ビットが加算器１０２１、１０２３の結果から１つを選択する桁上げ選択(carry-select)と呼ばれる異なるアーキテクチャを備える１６ビット加算器の異なる設計を示している。加算器１０２１は、加算器１０１１の桁上げ出力ビットが１であると仮定して最上位８ビット（ＸM、ＹM）を合計し、加算器１０２３は、加算器１０１１の桁上げ出力ビットがゼロであると仮定して最上位８ビット（ＸM、ＹM）を合計する。桁上げ選択アーキテクチャは、追加の８ビット加算器桁上げ付き、および乗算器（１０２５）を使用することによってクリティカル・パスを速める。図２１と図２２の設計は、同じレイテンシを有しているが、異なる速度を有している。図２３は、図２１の設計のパイプライン式バージョンを示している。パイプライン・レジスタ１０５１〜１０５７では、図２１の設計に対して、図２３の設計のレイテンシが１ずつ増える。しかし、図２３の設計（１０４１）は、図２１と図２２の設計（１００１、１０２１）より速い。本発明の一実施形態では、システム・レベルの最適化は、目的のクロック周期に従って、設計１００１、１０４１（同じアーキテクチャを有する）から１つを選択するステップ、または設計１０２１、１０４１（異なるアーキテクチャを有する）から１つを選択するステップ、または設計１００１、１０２１、１０４１から１つを選択するステップを伴う。代替の設計が選択されると、本発明の様々な方法を使用して選択された設計のタイミング・モデルを構築して、モジュールのタイミング動作を簡略化し、レジスタ可用性条件を提示することができる。
【００６３】
本発明の一実施形態では、（例えばレジスタの前または後ろの組み合わせパス、またはクリティカル・パスにおける）信号遅延は、（例えば配置配線後）モジュールの全実装から取得される。したがって、モジュール内の接続遅延は、簡略化されたタイミング・モデルに含まれる。これは、モジュールのタイミング動作を正確に反映する。これらのタイミング・モデルは、最低限の複雑さで最適なリタイミングの解決策をもたらし得る。こうしたモデルは、実際の組み合わせ構成要素モデルよりかなり簡単であるが、タイミング動作をより現実的に表している。というのは、モジュール内タイミング動作の正確な遅延データ（例えば相互接続の遅延などのモジュール内遅延など）が考慮に入れられるからである。結果として、こうしたタイミング・モデルは、あまり複雑ではなく、より高い精度をもたらす。タイミングにおけるよりよいモデリング精度は、より質の高い最終解決策をもたらす。
【００６４】
従来の方法とは異なり、本発明の実施形態によるタイミング・モデルは、単純、有効、かつ正確にシステム・レベルの回路をリタイミングすることができる。単純なタイミング・モデルでは、データ・フロー・グラフにおいて使用するノードがより少ないので、システム・レベルのリタイミングの演算の複雑さがより低減される。したがって、本発明の実施形態による単純なタイミング・モデルは、より高質の結果をもたらしながら、システム・レベルのリタイミングの演算の複雑さを大幅に低減することができる。
【００６５】
さらに、本発明の一実施形態では、レジスタの「投入」は、特定のハードウェア・モジュール向けのアルゴリズムで実行することができる。こうしたカスタム・アルゴリズムを使用すると、ハードウェア・モジュールのアーキテクチャは、レイテンシによって劇的に変わり、既存の一般のアルゴリズムを介して達成することができるものよりはるかによい結果を生成することができる。特性値(characterization value)｛ｃ0，ｃ1，．．．，ｃL｝は、カスタム・アルゴリズムのこの挙動を捕捉する。
【００６６】
回路モジュールを表す簡略化されたモデルの上記の例は、クロック周期を最低限に抑えるためのシステム・レベルのリタイミングについて示されているが、この手法は、システムのエリアと消費電力（または他の設計の目的）を伴う最適化のために使用することもできることを理解されたい。例えば、回路の消費電力またはエリアなどの他の属性を、回路モジュールの簡略化されたモデルに追加して、回路モジュールの対応する特性（例えば回路モジュールの設計の変更による消費電力の変化）を表すことができ、システム・レベルの最適化は、（タイミングの制約に加えて）これらの属性を伴う。例えば、図２１〜２３の設計１００１、１０２１、１０４１の消費電力とモジュール・エリアを決定することができる。したがって、設計の変更による消費電力とモジュール・エリアの変化を評価することができ、これは、消費電力、回路エリア、クロック速度の制約、これらの制約の組み合わせを伴うシステム・レベルの最適化に使用することができる。
【００６７】
上記の明細書では、本発明は、その特定の実施形態例を参照して説明してきた。頭記の特許請求の範囲に記載した本発明の意図および範囲から逸脱することなく、様々な変更をそれに加えることができることは明らかである。したがって本明細書および図面は、制約の意味ではなく例示の意味と見なされるものとする。
【図面の簡単な説明】
【００６８】
【図１】本発明とともに使用することができるデータ処理システムを示すブロック図例である。
【図２】リタイミング用のデータ・フロー・グラフを構築する従来技術の方法を示す図である。
【図３】リタイミング用のデータ・フロー・グラフを構築する従来技術の方法を示す図である。
【図４】本発明の一実施形態によるレジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図５】本発明の一実施形態によるレジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図６】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図７】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する例を示す図である。
【図８】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する別の例を示す図である。
【図９】本発明の一実施形態による非レジスタードＩ／Ｏを備える回路モジュールのデータ・フロー・グラフを構築する別の例を示す図である。
【図１０】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１１】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１２】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１３】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１４】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１５】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１６】本発明の一実施形態による回路モジュールを設計する詳細な例を示す図である。
【図１７】本発明の一実施形態による回路をリタイミングする方法を示す図である。
【図１８】本発明の一実施形態による回路モジュールを設計する方法を示す図である。
【図１９】本発明の一実施形態によるレジスタードＩ／Ｏを備えるモジュールを備える回路をリタイミングする方法を示す図である。
【図２０】本発明の一実施形態による回路を設計する詳細な方法を示す図である。
【図２１】本発明の一実施形態に従って使用することができる、異なるレイテンシおよび最小クロック周期についての異なる設計を備えるモジュールの例を示す図である。
【図２２】本発明の一実施形態に従って使用することができる、異なるレイテンシおよび最小クロック周期についての異なる設計を備えるモジュールの例を示す図である。
【図２３】本発明の一実施形態に従って使用することができる、異なるレイテンシおよび最小クロック周期についての異なる設計を備えるモジュールの例を示す図である。
【特許請求の範囲】
【請求項１】
回路モジュールを設計する方法であって、
モジュールの複数の回路設計を生成するステップであって、前記複数の回路設計が異なる複数のレイテンシを備える前記モジュールに対応してるステップと、
前記複数の回路設計の複数の許容できるクロックを決定するステップであって、前記複数の許容できるクロックのそれぞれが前記複数の回路設計のうちの対応する１つの実行可能なクロック周期を表すステップと、
前記複数の許容できるクロックを前記異なる複数のレイテンシに関連付けるための設計データを生成するステップと
を含む方法。
【請求項２】
前記複数の回路設計を生成する前記ステップが
配置配線を行って前記複数の回路設計のそれぞれを生成するステップ
を含む請求項１に記載の方法。
【請求項３】
前記複数の回路設計を生成する前記ステップが
前記複数の回路設計のうちの第１のものを生成するステップと、
前記複数の回路設計のうちの前記第１のものにパイプライン・レジスタ・セットを挿入して、前記複数の回路設計のうちの第２のものを生成するステップと
を含む請求項１に記載の方法。
【請求項４】
前記複数の回路設計を生成する前記ステップが
リタイミングを行って前記複数の回路設計のうちの前記第２のものを生成するステップ
をさらに含む請求項３に記載の方法。
【請求項５】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが異なるアーキテクチャを有する請求項１に記載の方法。
【請求項６】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが
ａ）異なる処理ロジックと
ｂ）異なるロジック処理素子と
のうちの一方を有する請求項５に記載の方法。
【請求項７】
前記実行可能なクロック周期が最小クロック周期を表す請求項１に記載の方法。
【請求項８】
前記設計データがさらに前記異なる複数のレイテンシを前記複数の回路設計のうちの１つまたは複数のデータ・フロー・グラフ表現に関連付ける請求項１に記載の方法。
【請求項９】
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく請求項８に記載の方法。
【請求項１０】
前記設計データを生成する前記ステップが
前記モジュールの１つまたは複数のデータ・フロー・グラフ表現を生成するステップであって、前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づくステップ
を含む請求項１に記載の方法。
【請求項１１】
前記複数の回路設計のうちの第１のものが非レジスタード入力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード入力に接続される
請求項１０に記載の方法。
【請求項１２】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である
請求項１１に記載の方法。
【請求項１３】
前記複数の回路設計のうちの第１のものが非レジスタード出力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード出力に接続される
請求項１０に記載の方法。
【請求項１４】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項１３に記載の方法。
【請求項１５】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスが非レジスタード入力に接続されており、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力と出力とを接続する任意のパスにおける信号遅延以上である請求項１３に記載の方法。
【請求項１６】
前記１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現が前記複数の回路設計のうちの第１のものに対応しており、前記第１のグラフ表現が、前記複数の回路設計のうちの前記第１のものにおけるレジスタから始まり、前記複数の回路設計のうちの前記第１のものにおけるレジスタで終わるすべての第１のパスを表すエッジを含んでおり、前記エッジにおける遅延が前記複数の回路設計のうちの前記第１のもののレイテンシを表す請求項１０に記載の方法。
【請求項１７】
前記エッジが第１のノードと第２のノードとを接続して前記第１のパスを表し、前記第１のノードおよび前記第２のノードが信号遅延をもたらさない請求項１６に記載の方法。
【請求項１８】
回路を設計する方法であって、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックに基づいて前記回路の一部分のデータ・フロー・グラフの表現を決定するステップと、
前記データ・フロー・グラフの前記表現を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む方法。
【請求項１９】
前記データ・フロー・グラフの前記表現を決定する前記ステップが
前記データ・フロー・グラフのエッジにおいて必要な追加の遅延数を決定するステップ
を含む請求項１８に記載の方法。
【請求項２０】
前記エッジが前記データ・フロー・グラフの第１のノードと第２のノードを接続し、前記エッジによって接続されている前記第１と第２のノードが、前記回路の前記一部分のレジスタから始まり、前記回路の前記一部分のレジスタで終わるパスを表す請求項１９に記載の方法。
【請求項２１】
前記第１のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力と前記回路の前記一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項２０に記載の方法。
【請求項２２】
前記第２のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の出力と前記回路の前記一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項２０に記載の方法。
【請求項２３】
前記データ・フロー・グラフが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力を前記回路の前記一部分の第１の出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む請求項２０に記載の方法。
【請求項２４】
前記追加の遅延数を決定する前記ステップが
前記目的のクロックに従って前記回路の前記一部分に対してリタイミングを実行するステップ
を含む請求項１９に記載の方法。
【請求項２５】
前記追加の遅延数を決定する前記ステップが
追加の遅延数を前記回路の前記一部分の許容できるクロックに相関させる設計データから前記追加の遅延数を決定するステップ
を含む請求項１９に記載の方法。
【請求項２６】
回路を設計する方法であって、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックの前記回路の前記設計の一部分をリタイミングして第１の結果を生成するステップと、
前記第１の結果を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む方法。
【請求項２７】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分に追加するステップ
を含む請求項２６に記載の方法。
【請求項２８】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分から削除するステップ
を含む請求項２６に記載の方法。
【請求項２９】
前記目的のクロックの前記設計をリタイミングする前記ステップが
接続を使用して、リタイミングされる前記設計の前記一部分のレジスタ間のすべてのパスを表すステップであって、前記接続が前記設計の前記一部分に追加された前記いくつかのパイプライン・レジスタ・セットを表すいくつかの追加の遅延を必要とするステップ
を含む請求項２７に記載の方法。
【請求項３０】
前記接続が第１のノードと第２のノードとを接続し、前記第１のノードと第２のノードが信号遅延をもたらさない請求項２９に記載の方法。
【請求項３１】
前記目的のクロックの前記設計をリタイミングする前記ステップが
入力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の入力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記入力演算ノードが遅延無しの接続を介して前記第１のノードに接続されるステップ
をさらに含む請求項３０に記載の方法。
【請求項３２】
前記目的のクロックの前記設計をリタイミングする前記ステップが
出力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の出力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記出力演算ノードが遅延無しの接続を介して前記第２のノードに接続されるステップ
をさらに含む請求項３１に記載の方法。
【請求項３３】
前記目的のクロックの前記設計をリタイミングする前記ステップが
第１の演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第２の入力と前記設計の前記一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表すステップ
をさらに含む請求項３２に記載の方法。
【請求項３４】
デジタル処理システムによって実行されると、前記システムに、回路モジュールを設計する方法を実行させる実行可能コンピュータ・プログラム命令を含む機械可読媒体であって、前記方法は、
モジュールの複数の回路設計を生成するステップであって、前記複数の回路設計が異なる複数のレイテンシを備える前記モジュールに対応するステップと、
前記複数の回路設計の複数の許容できるクロックを決定するステップであって、前記複数の許容できるクロックのそれぞれが前記複数の回路設計のうちの対応する１つの実行可能なクロック周期を表すステップと、
前記複数の許容できるクロックを前記異なる複数のレイテンシに関連付けるための設計データを生成するステップと
を含む機械可読媒体。
【請求項３５】
前記複数の回路設計を生成する前記ステップが
配置配線を行って前記複数の回路設計のそれぞれを生成するステップ
を含む請求項３４に記載の媒体。
【請求項３６】
前記複数の回路設計を生成する前記ステップが
前記複数の回路設計のうちの第１のものを生成するステップと、
前記複数の回路設計のうちの前記第１のものにパイプライン・レジスタ・セットを挿入して、前記複数の回路設計のうちの第２のものを生成するステップ
を含む請求項３４に記載の媒体。
【請求項３７】
前記複数の回路設計を生成する前記ステップが
リタイミングを行って前記複数の回路設計のうちの前記第２のものを生成するステップ
をさらに含む請求項３６に記載の媒体。
【請求項３８】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが異なるアーキテクチャを有する請求項３４に記載の媒体。
【請求項３９】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが
ａ）異なる処理ロジックと
ｂ）異なるロジック処理素子と
のうちの一方を有する請求項３８に記載の媒体。
【請求項４０】
前記実行可能なクロック周期が最小クロック周期を表す請求項３４に記載の媒体。
【請求項４１】
前記設計データがさらに前記異なる複数のレイテンシを前記複数の回路設計のうちの１つまたは複数のデータ・フロー・グラフ表現に関連付ける請求項３４に記載の媒体。
【請求項４２】
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく請求項４１に記載の媒体。
【請求項４３】
前記設計データを生成する前記ステップが
前記モジュールの１つまたは複数のデータ・フロー・グラフ表現を生成するステップであって、前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づくステップ
を含む請求項３４に記載の媒体。
【請求項４４】
前記複数の回路設計のうちの第１のものが非レジスタード入力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード入力に接続される
請求項４３に記載の媒体。
【請求項４５】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項４４に記載の媒体。
【請求項４６】
前記複数の回路設計のうちの第１のものが非レジスタード出力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード出力に接続される
請求項４３に記載の媒体。
【請求項４７】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項４６に記載の媒体。
【請求項４８】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスが非レジスタード入力に接続されており、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力と出力とを接続する任意のパスにおける信号遅延以上である請求項４６に記載の媒体。
【請求項４９】
前記１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現が前記複数の回路設計のうちの第１のものに対応しており、前記第１のグラフ表現が、前記複数の回路設計のうちの前記第１のものにおけるレジスタから始まり、前記複数の回路設計のうちの前記第１のものにおけるレジスタで終わるすべての第１のパスを表すエッジを含んでおり、前記エッジにおける遅延が前記複数の回路設計のうちの前記第１のもののレイテンシを表す請求項４３に記載の媒体。
【請求項５０】
前記エッジが第１のノードと第２のノードとを接続して前記第１のパスを表し、前記第１のノードと前記第２のノードが信号遅延をもたらさない請求項４９に記載の媒体。
【請求項５１】
デジタル処理システムによって実行されると、前記システムに、回路を設計する方法を実行させる実行可能コンピュータ・プログラム命令を含む機械可読媒体であって、前記方法は、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックに基づいて前記回路の一部分のデータ・フロー・グラフの表現を決定するステップと、
前記データ・フロー・グラフの前記表現を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む機械可読媒体。
【請求項５２】
前記データ・フロー・グラフの前記表現を決定する前記ステップが
前記データ・フロー・グラフのエッジにおいて必要な追加の遅延数を決定するステップ
を含む請求項５１に記載の媒体。
【請求項５３】
前記エッジが前記データ・フロー・グラフの第１のノードと第２のノードを接続し、前記エッジによって接続されている前記第１と第２のノードが、前記回路の前記一部分のレジスタから始まり、前記一部分のレジスタで終わるパスを表す請求項５２に記載の媒体。
【請求項５４】
前記第１のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力と前記回路の前記一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項５３に記載の媒体。
【請求項５５】
前記第２のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の出力と前記回路の前記一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項５３に記載の媒体。
【請求項５６】
前記データ・フロー・グラフが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力を前記回路の前記一部分の第１の出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む請求項５３に記載の媒体。
【請求項５７】
前記追加の遅延数を決定する前記ステップが
前記目的のクロックに従って前記回路の前記一部分に対してリタイミングを実行するステップ
を含む請求項５２に記載の媒体。
【請求項５８】
前記追加の遅延数を決定する前記ステップが
追加の遅延数を前記回路の前記一部分の許容できるクロックに相関させる設計データから前記追加の遅延数を決定するステップ
を含む請求項５２に記載の媒体。
【請求項５９】
デジタル処理システムによって実行されると、前記システムに、回路を設計する方法を実行させる実行可能コンピュータ・プログラム命令を含む機械可読媒体であって、前記方法は、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックの前記回路の前記設計の一部分をリタイミングして第１の結果を生成するステップと、
前記第１の結果を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む機械可読媒体。
【請求項６０】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分に追加するステップ
を含む請求項５９に記載の媒体。
【請求項６１】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分から削除するステップ
を含む請求項５９に記載の媒体。
【請求項６２】
前記目的のクロックの前記設計をリタイミングする前記ステップが
接続を使用して、リタイミングされる前記設計の前記一部分のレジスタ間のすべてのパスを表すステップであって、前記接続が前記設計の前記一部分に追加された前記いくつかのパイプライン・レジスタ・セットを表すいくつかの追加の遅延を必要とするステップ
を含む請求項６０に記載の媒体。
【請求項６３】
前記接続が第１のノードと第２のノードとを接続し、前記第１のノードと第２のノードが信号遅延をもたらさない請求項６２に記載の媒体。
【請求項６４】
前記目的のクロックの前記設計をリタイミングする前記ステップが
入力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の入力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記入力演算ノードが遅延無しの接続を介して前記第１のノードに接続されるステップ
をさらに含む請求項６３に記載の媒体。
【請求項６５】
前記目的のクロックの前記設計をリタイミングする前記ステップが
出力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の出力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記出力演算ノードが遅延無しの接続を介して前記第２のノードに接続されるステップ
をさらに含む請求項６４に記載の媒体。
【請求項６６】
前記目的のクロックの前記設計をリタイミングする前記ステップが
第１の演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第２の入力と前記設計の前記一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表すステップ
をさらに含む請求項６５に記載の媒体。
【請求項６７】
回路モジュールを設計するデータ処理システムであって、
モジュールの複数の回路設計を生成する手段であって、前記複数の回路設計が異なる複数のレイテンシを備える前記モジュールに対応する手段と、
前記複数の回路設計の複数の許容できるクロックを決定する手段であって、前記複数の許容できるクロックのそれぞれが前記複数の回路設計のうちの対応する１つの実行可能なクロック周期を表す手段と、
前記複数の許容できるクロックを前記異なる複数のレイテンシに関連付けるための設計データを生成する手段と
を含むデータ処理システム。
【請求項６８】
前記複数の回路設計を生成する前記手段が
配置配線を行って前記複数の回路設計のそれぞれを生成する手段
を含む請求項６７に記載のデータ処理システム。
【請求項６９】
前記複数の回路設計を生成する前記手段が
前記複数の回路設計のうちの第１のものを生成する手段と、
前記複数の回路設計のうちの前記第１のものにパイプライン・レジスタ・セットを挿入して、前記複数の回路設計のうちの第２のものを生成する手段と
を含む請求項６７に記載のデータ処理システム。
【請求項７０】
前記複数の回路設計を生成する前記手段が
リタイミングを行って前記複数の回路設計のうちの前記第２のものを生成する手段
をさらに含む請求項６９に記載のデータ処理システム。
【請求項７１】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが異なるアーキテクチャを有する請求項６７に記載のデータ処理システム。
【請求項７２】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが
ａ）異なる処理ロジックと
ｂ）異なるロジック処理素子と
のうちの一方を有する請求項７１に記載のデータ処理システム。
【請求項７３】
前記実行可能なクロック周期が最小クロック周期を表す請求項６７に記載のデータ処理システム。
【請求項７４】
前記設計データがさらに前記異なる複数のレイテンシを前記複数の回路設計のうちの１つまたは複数のデータ・フロー・グラフ表現に関連付ける請求項６７に記載のデータ処理システム。
【請求項７５】
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく請求項７４に記載のデータ処理システム。
【請求項７６】
前記設計データを生成する前記手段が
前記モジュールの１つまたは複数のデータ・フロー・グラフ表現を生成する手段であって、前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく手段
を含む請求項６７に記載のデータ処理システム。
【請求項７７】
前記複数の回路設計のうちの第１のものが非レジスタード入力を含み、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード入力に接続される
請求項７６に記載のデータ処理システム。
【請求項７８】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項７７に記載のデータ処理システム。
【請求項７９】
前記複数の回路設計のうちの第１のものが非レジスタード出力を含み、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード出力に接続される
請求項７６に記載のデータ処理システム。
【請求項８０】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項７９に記載のデータ処理システム。
【請求項８１】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスが非レジスタード入力に接続されており、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力と出力とを接続する任意のパスにおける信号遅延以上である請求項７９に記載のデータ処理システム。
【請求項８２】
前記１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現が前記複数の回路設計のうちの第１のものに対応しており、前記第１のグラフ表現が、前記複数の回路設計のうちの前記第１のものにおけるレジスタから始まり、前記複数の回路設計のうちの前記第１のものにおけるレジスタで終わるすべての第１のパスを表すエッジを含んでおり、前記エッジにおける遅延が前記複数の回路設計のうちの前記第１のもののレイテンシを表す請求項７６に記載のデータ処理システム。
【請求項８３】
前記エッジが第１のノードと第２のノードとを接続して前記第１のパスを表し、前記第１のノードと前記第２のノードが信号遅延をもたらさない請求項８２に記載のデータ処理システム。
【請求項８４】
回路を設計するデータ処理システムであって、
前記回路の設計の目的のクロックを選択する手段と、
前記目的のクロックに基づいて前記回路の一部分のデータ・フロー・グラフの表現を決定する手段と、
前記データ・フロー・グラフの前記表現を使用して前記目的のクロックの前記設計をリタイミングする手段と
を含むデータ処理システム。
【請求項８５】
前記データ・フロー・グラフの前記表現を決定する前記手段が
前記データ・フロー・グラフのエッジにおいて必要な追加の遅延数を決定する手段
を含む請求項８４に記載のデータ処理システム。
【請求項８６】
前記エッジが前記データ・フロー・グラフの第１のノードと第２のノードを接続し、前記エッジによって接続されている前記第１と第２のノードが、前記回路の前記一部分のレジスタから始まり、前記回路の前記一部分のレジスタで終わるパスを表す請求項８５に記載のデータ処理システム。
【請求項８７】
前記第１のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力と前記回路の前記一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項８６に記載のデータ処理システム。
【請求項８８】
前記第２のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の出力と前記回路の前記一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項８６に記載のデータ処理システム。
【請求項８９】
前記データ・フロー・グラフが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力を前記回路の前記一部分の第１の出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む請求項８６に記載のデータ処理システム。
【請求項９０】
前記追加の遅延数を決定する前記手段が
前記目的のクロックに従って前記回路の前記一部分に対してリタイミングを実行する手段
を含む請求項８５に記載のデータ処理システム。
【請求項９１】
前記追加の遅延数を決定する前記手段が
追加の遅延数を前記回路の前記一部分の許容できるクロックに相関させる設計データから前記追加の遅延数を決定する手段
を含む請求項８５に記載のデータ処理システム。
【請求項９２】
回路を設計するデータ処理システムであって、
前記回路の設計の目的のクロックを選択する手段と、
前記目的のクロックの前記回路の前記設計の一部分をリタイミングして第１の結果を生成する手段と、
前記第１の結果を使用して前記目的のクロックの前記設計をリタイミングする手段と
を含むデータ処理システム。
【請求項９３】
前記回路の前記設計の前記一部分をリタイミングする前記手段が
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分に追加する手段
を含む請求項９２に記載のデータ処理システム。
【請求項９４】
前記回路の前記設計の前記一部分をリタイミングする前記手段が
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分から削除する手段
を含む請求項９２に記載のデータ処理システム。
【請求項９５】
前記目的のクロックの前記設計をリタイミングする前記手段が
接続を使用して、リタイミングされる前記設計の前記一部分のレジスタ間のすべてのパスを表す手段であって、前記接続が前記設計の前記一部分に追加された前記いくつかのパイプライン・レジスタ・セットを表すいくつかの追加の遅延を必要とする手段
を含む請求項９３に記載のデータ処理システム。
【請求項９６】
前記接続が第１のノードと第２のノードとを接続し、前記第１のノードと第２のノードが信号遅延をもたらさない請求項９５に記載のデータ処理システム。
【請求項９７】
前記目的のクロックの前記設計をリタイミングする前記手段が
入力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の入力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表す手段であって、前記入力演算ノードが遅延無しの接続を介して前記第１のノードに接続される手段
をさらに含む請求項９６に記載のデータ処理システム。
【請求項９８】
前記目的のクロックの前記設計をリタイミングする前記手段が
出力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の出力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表す手段であって、前記出力演算ノードが遅延無しの接続を介して前記第２のノードに接続される手段
をさらに含む請求項９７に記載のデータ処理システム。
【請求項９９】
前記目的のクロックの前記設計をリタイミングする前記手段が
第１の演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第２の入力と前記設計の前記一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表す手段
をさらに含む請求項９８に記載のデータ処理システム。
【請求項１】
回路モジュールを設計する方法であって、
モジュールの複数の回路設計を生成するステップであって、前記複数の回路設計が異なる複数のレイテンシを備える前記モジュールに対応してるステップと、
前記複数の回路設計の複数の許容できるクロックを決定するステップであって、前記複数の許容できるクロックのそれぞれが前記複数の回路設計のうちの対応する１つの実行可能なクロック周期を表すステップと、
前記複数の許容できるクロックを前記異なる複数のレイテンシに関連付けるための設計データを生成するステップと
を含む方法。
【請求項２】
前記複数の回路設計を生成する前記ステップが
配置配線を行って前記複数の回路設計のそれぞれを生成するステップ
を含む請求項１に記載の方法。
【請求項３】
前記複数の回路設計を生成する前記ステップが
前記複数の回路設計のうちの第１のものを生成するステップと、
前記複数の回路設計のうちの前記第１のものにパイプライン・レジスタ・セットを挿入して、前記複数の回路設計のうちの第２のものを生成するステップと
を含む請求項１に記載の方法。
【請求項４】
前記複数の回路設計を生成する前記ステップが
リタイミングを行って前記複数の回路設計のうちの前記第２のものを生成するステップ
をさらに含む請求項３に記載の方法。
【請求項５】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが異なるアーキテクチャを有する請求項１に記載の方法。
【請求項６】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが
ａ）異なる処理ロジックと
ｂ）異なるロジック処理素子と
のうちの一方を有する請求項５に記載の方法。
【請求項７】
前記実行可能なクロック周期が最小クロック周期を表す請求項１に記載の方法。
【請求項８】
前記設計データがさらに前記異なる複数のレイテンシを前記複数の回路設計のうちの１つまたは複数のデータ・フロー・グラフ表現に関連付ける請求項１に記載の方法。
【請求項９】
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく請求項８に記載の方法。
【請求項１０】
前記設計データを生成する前記ステップが
前記モジュールの１つまたは複数のデータ・フロー・グラフ表現を生成するステップであって、前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づくステップ
を含む請求項１に記載の方法。
【請求項１１】
前記複数の回路設計のうちの第１のものが非レジスタード入力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード入力に接続される
請求項１０に記載の方法。
【請求項１２】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である
請求項１１に記載の方法。
【請求項１３】
前記複数の回路設計のうちの第１のものが非レジスタード出力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード出力に接続される
請求項１０に記載の方法。
【請求項１４】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項１３に記載の方法。
【請求項１５】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスが非レジスタード入力に接続されており、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力と出力とを接続する任意のパスにおける信号遅延以上である請求項１３に記載の方法。
【請求項１６】
前記１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現が前記複数の回路設計のうちの第１のものに対応しており、前記第１のグラフ表現が、前記複数の回路設計のうちの前記第１のものにおけるレジスタから始まり、前記複数の回路設計のうちの前記第１のものにおけるレジスタで終わるすべての第１のパスを表すエッジを含んでおり、前記エッジにおける遅延が前記複数の回路設計のうちの前記第１のもののレイテンシを表す請求項１０に記載の方法。
【請求項１７】
前記エッジが第１のノードと第２のノードとを接続して前記第１のパスを表し、前記第１のノードおよび前記第２のノードが信号遅延をもたらさない請求項１６に記載の方法。
【請求項１８】
回路を設計する方法であって、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックに基づいて前記回路の一部分のデータ・フロー・グラフの表現を決定するステップと、
前記データ・フロー・グラフの前記表現を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む方法。
【請求項１９】
前記データ・フロー・グラフの前記表現を決定する前記ステップが
前記データ・フロー・グラフのエッジにおいて必要な追加の遅延数を決定するステップ
を含む請求項１８に記載の方法。
【請求項２０】
前記エッジが前記データ・フロー・グラフの第１のノードと第２のノードを接続し、前記エッジによって接続されている前記第１と第２のノードが、前記回路の前記一部分のレジスタから始まり、前記回路の前記一部分のレジスタで終わるパスを表す請求項１９に記載の方法。
【請求項２１】
前記第１のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力と前記回路の前記一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項２０に記載の方法。
【請求項２２】
前記第２のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の出力と前記回路の前記一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項２０に記載の方法。
【請求項２３】
前記データ・フロー・グラフが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力を前記回路の前記一部分の第１の出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む請求項２０に記載の方法。
【請求項２４】
前記追加の遅延数を決定する前記ステップが
前記目的のクロックに従って前記回路の前記一部分に対してリタイミングを実行するステップ
を含む請求項１９に記載の方法。
【請求項２５】
前記追加の遅延数を決定する前記ステップが
追加の遅延数を前記回路の前記一部分の許容できるクロックに相関させる設計データから前記追加の遅延数を決定するステップ
を含む請求項１９に記載の方法。
【請求項２６】
回路を設計する方法であって、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックの前記回路の前記設計の一部分をリタイミングして第１の結果を生成するステップと、
前記第１の結果を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む方法。
【請求項２７】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分に追加するステップ
を含む請求項２６に記載の方法。
【請求項２８】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分から削除するステップ
を含む請求項２６に記載の方法。
【請求項２９】
前記目的のクロックの前記設計をリタイミングする前記ステップが
接続を使用して、リタイミングされる前記設計の前記一部分のレジスタ間のすべてのパスを表すステップであって、前記接続が前記設計の前記一部分に追加された前記いくつかのパイプライン・レジスタ・セットを表すいくつかの追加の遅延を必要とするステップ
を含む請求項２７に記載の方法。
【請求項３０】
前記接続が第１のノードと第２のノードとを接続し、前記第１のノードと第２のノードが信号遅延をもたらさない請求項２９に記載の方法。
【請求項３１】
前記目的のクロックの前記設計をリタイミングする前記ステップが
入力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の入力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記入力演算ノードが遅延無しの接続を介して前記第１のノードに接続されるステップ
をさらに含む請求項３０に記載の方法。
【請求項３２】
前記目的のクロックの前記設計をリタイミングする前記ステップが
出力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の出力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記出力演算ノードが遅延無しの接続を介して前記第２のノードに接続されるステップ
をさらに含む請求項３１に記載の方法。
【請求項３３】
前記目的のクロックの前記設計をリタイミングする前記ステップが
第１の演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第２の入力と前記設計の前記一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表すステップ
をさらに含む請求項３２に記載の方法。
【請求項３４】
デジタル処理システムによって実行されると、前記システムに、回路モジュールを設計する方法を実行させる実行可能コンピュータ・プログラム命令を含む機械可読媒体であって、前記方法は、
モジュールの複数の回路設計を生成するステップであって、前記複数の回路設計が異なる複数のレイテンシを備える前記モジュールに対応するステップと、
前記複数の回路設計の複数の許容できるクロックを決定するステップであって、前記複数の許容できるクロックのそれぞれが前記複数の回路設計のうちの対応する１つの実行可能なクロック周期を表すステップと、
前記複数の許容できるクロックを前記異なる複数のレイテンシに関連付けるための設計データを生成するステップと
を含む機械可読媒体。
【請求項３５】
前記複数の回路設計を生成する前記ステップが
配置配線を行って前記複数の回路設計のそれぞれを生成するステップ
を含む請求項３４に記載の媒体。
【請求項３６】
前記複数の回路設計を生成する前記ステップが
前記複数の回路設計のうちの第１のものを生成するステップと、
前記複数の回路設計のうちの前記第１のものにパイプライン・レジスタ・セットを挿入して、前記複数の回路設計のうちの第２のものを生成するステップ
を含む請求項３４に記載の媒体。
【請求項３７】
前記複数の回路設計を生成する前記ステップが
リタイミングを行って前記複数の回路設計のうちの前記第２のものを生成するステップ
をさらに含む請求項３６に記載の媒体。
【請求項３８】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが異なるアーキテクチャを有する請求項３４に記載の媒体。
【請求項３９】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが
ａ）異なる処理ロジックと
ｂ）異なるロジック処理素子と
のうちの一方を有する請求項３８に記載の媒体。
【請求項４０】
前記実行可能なクロック周期が最小クロック周期を表す請求項３４に記載の媒体。
【請求項４１】
前記設計データがさらに前記異なる複数のレイテンシを前記複数の回路設計のうちの１つまたは複数のデータ・フロー・グラフ表現に関連付ける請求項３４に記載の媒体。
【請求項４２】
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく請求項４１に記載の媒体。
【請求項４３】
前記設計データを生成する前記ステップが
前記モジュールの１つまたは複数のデータ・フロー・グラフ表現を生成するステップであって、前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づくステップ
を含む請求項３４に記載の媒体。
【請求項４４】
前記複数の回路設計のうちの第１のものが非レジスタード入力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード入力に接続される
請求項４３に記載の媒体。
【請求項４５】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項４４に記載の媒体。
【請求項４６】
前記複数の回路設計のうちの第１のものが非レジスタード出力を含んでおり、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード出力に接続される
請求項４３に記載の媒体。
【請求項４７】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項４６に記載の媒体。
【請求項４８】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスが非レジスタード入力に接続されており、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力と出力とを接続する任意のパスにおける信号遅延以上である請求項４６に記載の媒体。
【請求項４９】
前記１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現が前記複数の回路設計のうちの第１のものに対応しており、前記第１のグラフ表現が、前記複数の回路設計のうちの前記第１のものにおけるレジスタから始まり、前記複数の回路設計のうちの前記第１のものにおけるレジスタで終わるすべての第１のパスを表すエッジを含んでおり、前記エッジにおける遅延が前記複数の回路設計のうちの前記第１のもののレイテンシを表す請求項４３に記載の媒体。
【請求項５０】
前記エッジが第１のノードと第２のノードとを接続して前記第１のパスを表し、前記第１のノードと前記第２のノードが信号遅延をもたらさない請求項４９に記載の媒体。
【請求項５１】
デジタル処理システムによって実行されると、前記システムに、回路を設計する方法を実行させる実行可能コンピュータ・プログラム命令を含む機械可読媒体であって、前記方法は、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックに基づいて前記回路の一部分のデータ・フロー・グラフの表現を決定するステップと、
前記データ・フロー・グラフの前記表現を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む機械可読媒体。
【請求項５２】
前記データ・フロー・グラフの前記表現を決定する前記ステップが
前記データ・フロー・グラフのエッジにおいて必要な追加の遅延数を決定するステップ
を含む請求項５１に記載の媒体。
【請求項５３】
前記エッジが前記データ・フロー・グラフの第１のノードと第２のノードを接続し、前記エッジによって接続されている前記第１と第２のノードが、前記回路の前記一部分のレジスタから始まり、前記一部分のレジスタで終わるパスを表す請求項５２に記載の媒体。
【請求項５４】
前記第１のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力と前記回路の前記一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項５３に記載の媒体。
【請求項５５】
前記第２のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の出力と前記回路の前記一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項５３に記載の媒体。
【請求項５６】
前記データ・フロー・グラフが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力を前記回路の前記一部分の第１の出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む請求項５３に記載の媒体。
【請求項５７】
前記追加の遅延数を決定する前記ステップが
前記目的のクロックに従って前記回路の前記一部分に対してリタイミングを実行するステップ
を含む請求項５２に記載の媒体。
【請求項５８】
前記追加の遅延数を決定する前記ステップが
追加の遅延数を前記回路の前記一部分の許容できるクロックに相関させる設計データから前記追加の遅延数を決定するステップ
を含む請求項５２に記載の媒体。
【請求項５９】
デジタル処理システムによって実行されると、前記システムに、回路を設計する方法を実行させる実行可能コンピュータ・プログラム命令を含む機械可読媒体であって、前記方法は、
前記回路の設計の目的のクロックを選択するステップと、
前記目的のクロックの前記回路の前記設計の一部分をリタイミングして第１の結果を生成するステップと、
前記第１の結果を使用して前記目的のクロックの前記設計をリタイミングするステップと
を含む機械可読媒体。
【請求項６０】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分に追加するステップ
を含む請求項５９に記載の媒体。
【請求項６１】
前記回路の前記設計の前記一部分をリタイミングする前記ステップが
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分から削除するステップ
を含む請求項５９に記載の媒体。
【請求項６２】
前記目的のクロックの前記設計をリタイミングする前記ステップが
接続を使用して、リタイミングされる前記設計の前記一部分のレジスタ間のすべてのパスを表すステップであって、前記接続が前記設計の前記一部分に追加された前記いくつかのパイプライン・レジスタ・セットを表すいくつかの追加の遅延を必要とするステップ
を含む請求項６０に記載の媒体。
【請求項６３】
前記接続が第１のノードと第２のノードとを接続し、前記第１のノードと第２のノードが信号遅延をもたらさない請求項６２に記載の媒体。
【請求項６４】
前記目的のクロックの前記設計をリタイミングする前記ステップが
入力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の入力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記入力演算ノードが遅延無しの接続を介して前記第１のノードに接続されるステップ
をさらに含む請求項６３に記載の媒体。
【請求項６５】
前記目的のクロックの前記設計をリタイミングする前記ステップが
出力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の出力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表すステップであって、前記出力演算ノードが遅延無しの接続を介して前記第２のノードに接続されるステップ
をさらに含む請求項６４に記載の媒体。
【請求項６６】
前記目的のクロックの前記設計をリタイミングする前記ステップが
第１の演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第２の入力と前記設計の前記一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表すステップ
をさらに含む請求項６５に記載の媒体。
【請求項６７】
回路モジュールを設計するデータ処理システムであって、
モジュールの複数の回路設計を生成する手段であって、前記複数の回路設計が異なる複数のレイテンシを備える前記モジュールに対応する手段と、
前記複数の回路設計の複数の許容できるクロックを決定する手段であって、前記複数の許容できるクロックのそれぞれが前記複数の回路設計のうちの対応する１つの実行可能なクロック周期を表す手段と、
前記複数の許容できるクロックを前記異なる複数のレイテンシに関連付けるための設計データを生成する手段と
を含むデータ処理システム。
【請求項６８】
前記複数の回路設計を生成する前記手段が
配置配線を行って前記複数の回路設計のそれぞれを生成する手段
を含む請求項６７に記載のデータ処理システム。
【請求項６９】
前記複数の回路設計を生成する前記手段が
前記複数の回路設計のうちの第１のものを生成する手段と、
前記複数の回路設計のうちの前記第１のものにパイプライン・レジスタ・セットを挿入して、前記複数の回路設計のうちの第２のものを生成する手段と
を含む請求項６７に記載のデータ処理システム。
【請求項７０】
前記複数の回路設計を生成する前記手段が
リタイミングを行って前記複数の回路設計のうちの前記第２のものを生成する手段
をさらに含む請求項６９に記載のデータ処理システム。
【請求項７１】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが異なるアーキテクチャを有する請求項６７に記載のデータ処理システム。
【請求項７２】
前記複数の回路設計のうちの第１のものと前記複数の回路設計のうちの第２のものが
ａ）異なる処理ロジックと
ｂ）異なるロジック処理素子と
のうちの一方を有する請求項７１に記載のデータ処理システム。
【請求項７３】
前記実行可能なクロック周期が最小クロック周期を表す請求項６７に記載のデータ処理システム。
【請求項７４】
前記設計データがさらに前記異なる複数のレイテンシを前記複数の回路設計のうちの１つまたは複数のデータ・フロー・グラフ表現に関連付ける請求項６７に記載のデータ処理システム。
【請求項７５】
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく請求項７４に記載のデータ処理システム。
【請求項７６】
前記設計データを生成する前記手段が
前記モジュールの１つまたは複数のデータ・フロー・グラフ表現を生成する手段であって、前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の許容できるクロックに基づく手段
を含む請求項６７に記載のデータ処理システム。
【請求項７７】
前記複数の回路設計のうちの第１のものが非レジスタード入力を含み、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード入力に接続される
請求項７６に記載のデータ処理システム。
【請求項７８】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項７７に記載のデータ処理システム。
【請求項７９】
前記複数の回路設計のうちの第１のものが非レジスタード出力を含み、
前記１つまたは複数のデータ・フロー・グラフ表現が前記複数の回路設計のうちの前記第１のものの第１のパスにおける信号遅延の少なくとも一部分を表す演算ノードの表現を含んでおり、前記第１のパスがレジスタを含んでおらず、非レジスタード出力に接続される
請求項７６に記載のデータ処理システム。
【請求項８０】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード出力とレジスタとの間を接続する任意のパスにおける信号遅延以上である請求項７９に記載のデータ処理システム。
【請求項８１】
前記演算ノードが前記第１のパスにおける前記信号遅延を表し、前記第１のパスが非レジスタード入力に接続されており、前記第１のパスにおける前記信号遅延が、レジスタを含んでおらず、かつ前記複数の回路設計のうちの前記第１のものにおける前記非レジスタード入力と出力とを接続する任意のパスにおける信号遅延以上である請求項７９に記載のデータ処理システム。
【請求項８２】
前記１つまたは複数のデータ・フロー・グラフ表現のうちの第１のグラフ表現が前記複数の回路設計のうちの第１のものに対応しており、前記第１のグラフ表現が、前記複数の回路設計のうちの前記第１のものにおけるレジスタから始まり、前記複数の回路設計のうちの前記第１のものにおけるレジスタで終わるすべての第１のパスを表すエッジを含んでおり、前記エッジにおける遅延が前記複数の回路設計のうちの前記第１のもののレイテンシを表す請求項７６に記載のデータ処理システム。
【請求項８３】
前記エッジが第１のノードと第２のノードとを接続して前記第１のパスを表し、前記第１のノードと前記第２のノードが信号遅延をもたらさない請求項８２に記載のデータ処理システム。
【請求項８４】
回路を設計するデータ処理システムであって、
前記回路の設計の目的のクロックを選択する手段と、
前記目的のクロックに基づいて前記回路の一部分のデータ・フロー・グラフの表現を決定する手段と、
前記データ・フロー・グラフの前記表現を使用して前記目的のクロックの前記設計をリタイミングする手段と
を含むデータ処理システム。
【請求項８５】
前記データ・フロー・グラフの前記表現を決定する前記手段が
前記データ・フロー・グラフのエッジにおいて必要な追加の遅延数を決定する手段
を含む請求項８４に記載のデータ処理システム。
【請求項８６】
前記エッジが前記データ・フロー・グラフの第１のノードと第２のノードを接続し、前記エッジによって接続されている前記第１と第２のノードが、前記回路の前記一部分のレジスタから始まり、前記回路の前記一部分のレジスタで終わるパスを表す請求項８５に記載のデータ処理システム。
【請求項８７】
前記第１のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力と前記回路の前記一部分のレジスタの入力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項８６に記載のデータ処理システム。
【請求項８８】
前記第２のノードが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の出力と前記回路の前記一部分のレジスタの出力との間にある任意のパスにおける信号遅延以上である信号遅延を表すノードに接続される請求項８６に記載のデータ処理システム。
【請求項８９】
前記データ・フロー・グラフが、レジスタを含んでおらず、かつ前記回路の前記一部分の第１の入力を前記回路の前記一部分の第１の出力に接続する任意のパスにおける信号遅延以上である信号遅延を表すノードを含む請求項８６に記載のデータ処理システム。
【請求項９０】
前記追加の遅延数を決定する前記手段が
前記目的のクロックに従って前記回路の前記一部分に対してリタイミングを実行する手段
を含む請求項８５に記載のデータ処理システム。
【請求項９１】
前記追加の遅延数を決定する前記手段が
追加の遅延数を前記回路の前記一部分の許容できるクロックに相関させる設計データから前記追加の遅延数を決定する手段
を含む請求項８５に記載のデータ処理システム。
【請求項９２】
回路を設計するデータ処理システムであって、
前記回路の設計の目的のクロックを選択する手段と、
前記目的のクロックの前記回路の前記設計の一部分をリタイミングして第１の結果を生成する手段と、
前記第１の結果を使用して前記目的のクロックの前記設計をリタイミングする手段と
を含むデータ処理システム。
【請求項９３】
前記回路の前記設計の前記一部分をリタイミングする前記手段が
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分に追加する手段
を含む請求項９２に記載のデータ処理システム。
【請求項９４】
前記回路の前記設計の前記一部分をリタイミングする前記手段が
前記設計の前記一部分が前記目的のクロックで稼動することができるように、いくつかのパイプライン・レジスタ・セットを前記設計の前記一部分から削除する手段
を含む請求項９２に記載のデータ処理システム。
【請求項９５】
前記目的のクロックの前記設計をリタイミングする前記手段が
接続を使用して、リタイミングされる前記設計の前記一部分のレジスタ間のすべてのパスを表す手段であって、前記接続が前記設計の前記一部分に追加された前記いくつかのパイプライン・レジスタ・セットを表すいくつかの追加の遅延を必要とする手段
を含む請求項９３に記載のデータ処理システム。
【請求項９６】
前記接続が第１のノードと第２のノードとを接続し、前記第１のノードと第２のノードが信号遅延をもたらさない請求項９５に記載のデータ処理システム。
【請求項９７】
前記目的のクロックの前記設計をリタイミングする前記手段が
入力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の入力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表す手段であって、前記入力演算ノードが遅延無しの接続を介して前記第１のノードに接続される手段
をさらに含む請求項９６に記載のデータ処理システム。
【請求項９８】
前記目的のクロックの前記設計をリタイミングする前記手段が
出力演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第１の出力と前記設計の前記一部分のレジスタとを接続するすべてのパスに沿った最大信号遅延を表す手段であって、前記出力演算ノードが遅延無しの接続を介して前記第２のノードに接続される手段
をさらに含む請求項９７に記載のデータ処理システム。
【請求項９９】
前記目的のクロックの前記設計をリタイミングする前記手段が
第１の演算ノードを使用して、レジスタを含んでおらず、かつ前記設計の前記一部分の第２の入力と前記設計の前記一部分の第２の出力とを接続するすべてのパスに沿った最大信号遅延を表す手段
をさらに含む請求項９８に記載のデータ処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公表番号】特表２００７−５０３６５９（Ｐ２００７−５０３６５９Ａ）
【公表日】平成１９年２月２２日（２００７．２．２２）
【国際特許分類】
【出願番号】特願２００６−５３２８３９（Ｐ２００６−５３２８３９）
【出願日】平成１６年５月６日（２００４．５．６）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１４２２５
【国際公開番号】ＷＯ２００４／１０２４２９
【国際公開日】平成１６年１１月２５日（２００４．１１．２５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｍａｃｉｎｔｏｓｈ
【出願人】（３０００５６４４０）シンプリシティ・インコーポレーテッド (5)
【Ｆターム（参考）】
【公表日】平成１９年２月２２日（２００７．２．２２）
【国際特許分類】
【出願日】平成１６年５月６日（２００４．５．６）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１４２２５
【国際公開番号】ＷＯ２００４／１０２４２９
【国際公開日】平成１６年１１月２５日（２００４．１１．２５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｍａｃｉｎｔｏｓｈ
【出願人】（３０００５６４４０）シンプリシティ・インコーポレーテッド (5)
【Ｆターム（参考）】
[ Back to top ]