(57)【要約】  集積回路をリタイミングするための方法および装置について説明する。本発明のいくつかの実施形態によれば、リタイミングは、集積回路内の１つまたは複数のパスについてタイミング解析を実行してスラック値を取得するステップと、取得したスラック値に基づいてパスの１つを選択するステップと、選択したパス沿いのリタイミング可能カットを決定するステップとを含む。これらの例示的な実施形態におけるリタイミング可能カットは、集積回路内の１つまたは複数の論理インスタンスの一組の入力ピンを含み、選択したパスのスラック値を改善するため、それらのピンに１つまたは複数のリタイミングした順序素子を結合することができる。具体的な実施形態では、リタイミング可能カットは、選択したパス沿いの複数の可能なカットから自動的に選択される。集積回路をリタイミングするためのその他の実施形態、ならびに開示の方法によってリタイミングされる集積回路、および回路設計データベースも開示される。開示の方法を実行するための命令を保存するコンピュータ実行可能媒体も開示される。
2007524891.tif 000002
【特許請求の範囲】
【請求項１】
ＥＤＡ（コンピュータによる電子回路の設計自動化）環境において集積回路をリタイミングするための方法であって、
前記集積回路内の１つまたは複数のパスについてタイミング解析を実行して、前記パスに沿って伝播する信号の遅延時間を取得するステップと、
前記取得した遅延時間に基づいてタイミング制約を満たさない遅延時間を有するパスを選択するステップであって、前記選択したパスは、始点順序素子で始まり、終点順序素子で終り、前記選択したパスは、２つまたはより多くの論理インスタンスをさらに含む、ステップと、
前記タイミング制約を満たすように前記始点順序素子または前記終点順序素子の一方を再配置できる前記選択したパス沿いのリタイミング・ロケーションを決定するステップであって、前記リタイミング・ロケーションは、前記始点順序素子または前記終点順序素子の前記一方からの少なくとも２つの論理インスタンスである、ステップと、
前記集積回路の設計データベースを更新して、前記始点順序素子または前記終点順序素子の前記一方を前記リタイミング・ロケーションに再配置するステップと、
を含む方法。
【請求項２】
請求項１に記載の方法であって、前記タイミング解析を実行するステップは、前記取得した遅延時間と前記タイミング制約を用いてスラック値を決定するステップをさらに含み、前記パスを選択するステップは、前記スラック値を評価するステップをさらに含む、方法。
【請求項３】
請求項１に記載の方法であって、前記リタイミング・ロケーションを決定するステップは、回路機能を維持するため、１つまたは複数の追加の順序素子が、前記リタイミング・ロケーションあるいは１つまたは複数の追加のリタイミング・ロケーションに再配置する必要があるかどうか判定するステップを含む、方法。
【請求項４】
請求項３に記載の方法であって、前記リタイミング・ロケーションおよび前記１つまたは複数の追加のリタイミング・ロケーションは、リタイミング可能カットを含む、方法。
【請求項５】
請求項１に記載の方法であって、前記リタイミング・ロケーションを決定するステップは、
論理インスタンスの１つまたは複数の出力ピンから少なくとも１つのフォワード・トレースを実行するステップであって、前記論理インスタンスを越えて前記始点順序素子または前記終点順序素子の前記一方を再配置することができる、ステップと、
論理インスタンスの１つまたは複数の入力ピンから少なくとも１つのバックワード・トレースを実行するステップであって、前記論理インスタンスを越えて前記始点順序素子または前記終点順序素子の前記一方を再配置することができる、ステップと、
を含む、方法。
【請求項６】
請求項１に記載の方法であって、
前記始点順序素子または前記終点順序素子の前記一方のリタイミング後の初期状態を決定するステップを、
さらに含む方法。
【請求項７】
請求項１に記載の方法であって、
前記始点順序素子または前記終点順序素子の前記一方の構成上の制約を緩和するステップを、
さらに含む方法。
【請求項８】
請求項７に記載の方法であって、前記構成上の制約を緩和するステップは、前記始点順序素子または前記終点順序素子の前記一方から１つまたは複数の制御信号を分離するステップを含む、方法。
【請求項９】
請求項１に記載の方法であって、前記リタイミング・ロケーションを決定するステップは、
前記選択したパス内の複数の可能なリタイミング・ロケーションに関連するスラック値を比較するステップと、
前記スラック値に基づいて前記複数の可能なリタイミング・ロケーションから前記リタイミング・ロケーションを選択するステップと、
を含む、方法。
【請求項１０】
請求項９に記載の方法であって、前記選択したリタイミング・ロケーションは、前記選択したパスのスラック値に最も優れた改善をもたらす、方法。
【請求項１１】
請求項１に記載の方法であって、前記集積回路は、フィールド・プログラマブル・ゲート・アレイである、方法。
【請求項１２】
請求項１に記載の方法によってリタイミングされる集積回路。
【請求項１３】
請求項１に記載の方法をコンピュータシステムに実行させるコンピュータ実行可能命令を保存するコンピュータ可読媒体。
【請求項１４】
請求項１に記載の方法によってリタイミングされた集積回路の設計情報を含む設計データベースを保存するコンピュータ可読媒体。
【請求項１５】
ＥＤＡ（コンピュータによる電子回路の設計自動化）環境において集積回路をリタイミングするための方法であって、
タイミング制約を満たさない遅延時間を有する前記集積回路内のフェイリング信号パスを特定するステップであって、前記フェイリング信号パスは、始点順序素子で始まり、論理コーンの１つまたは複数の論理インスタンスを通過して延び、終点順序素子で終る、ステップと、
前記フェイリング信号パスの前記遅延時間を改善するために前記始点順序素子または前記終点順序素子の一方を再配置できる前記フェイリング信号パス沿いのロケーションを選択するステップであって、前記選択したロケーションは、前記論理インスタンスのうちの関連する１つの論理インスタンスの入力に結合される、ステップと、
前記選択したロケーションから、前記関連する論理インスタンスの出力パスと入力パスをサーチして、回路機能を維持するために再配置する１つまたは複数の追加の順序素子を特定するステップと、
を含む方法。
【請求項１６】
請求項１５に記載の方法であって、前記出力パスと入力パスをサーチするステップは、回路機能を維持するために前記１つまたは複数の追加の順序素子を再配置する前記集積回路内の１つまたは複数の追加のロケーションを特定するステップを含む、方法。
【請求項１７】
請求項１６に記載の方法であって、前記選択したロケーションおよび前記１つまたは複数の特定した追加のロケーションは、リタイミング可能カットを含む、方法。
【請求項１８】
請求項１５に記載の方法であって、前記選択したロケーションは、バックワード・リタイミング可能カットの一部であり、前記出力パスと入力パスをサーチするステップは、前記関連する論理インスタンスが１つまたは複数の順序素子を駆動することを確認するステップを含む、方法。
【請求項１９】
請求項１５に記載の方法であって、前記選択したロケーションは、フォワード・リタイミング可能カットの一部であり、前記出力パスと入力パスをサーチするステップは、前記関連する論理インスタンスが、１つまたは複数の順序素子によって、または１つまたは複数の定常入力／出力ピンによって、駆動されることを確認するステップを含む、方法。
【請求項２０】
請求項１５に記載の方法であって、前記選択したロケーションは、前記始点順序素子または前記終点順序素子の前記一方を再配置する複数の可能なロケーションの１つであり、前記選択したロケーションは、前記フェイリング信号パスのスラック時間に最も優れた改善をもたらす、方法。
【請求項２１】
請求項１５に記載の方法であって、
再配置できる前記始点順序素子または前記終点順序素子の前記一方のリタイミング後の初期状態、あるいは１つまたは複数の前記特定した追加の順序素子のリタイミング後の初期状態を決定するステップを、
さらに含む方法。
【請求項２２】
請求項１５に記載の方法であって、
再配置できる前記始点順序素子または前記終点順序素子の前記一方の構成上の制約、あるいは１つまたは複数の前記特定した追加の順序素子の構成上の制約を緩和するステップを、
さらに含む方法。
【請求項２３】
請求項１５に記載の方法であって、前記集積回路が、フィールド・プログラマブル・ゲート・アレイである、方法。
【請求項２４】
請求項１５に記載の方法によってリタイミングされる集積回路。
【請求項２５】
請求項１５に記載の方法をコンピュータシステムに実行させるコンピュータ実行可能命令を保存するコンピュータ可読媒体。
【請求項２６】
請求項１５に記載の方法によってリタイミングされた集積回路の設計情報を含む設計データベースを保存するコンピュータ可読媒体。
【請求項２７】
集積回路内でリタイミング可能カットを特定するための方法であって、
リタイミングする信号パスを選択するステップであって、前記信号パスは、始点順序素子で始まり、１つまたは複数の論理インスタンスを通過して延び、終点順序素子で終る、ステップと、
前記信号パス沿いにリタイミング可能カットを発見するステップであって、
前記信号パス内の選択した論理インスタンスの１つまたは複数の出力ピンからフォワード・トレースを実行するステップと、
前記信号パス内の選択した論理インスタンスの１つまたは複数の入力ピンからバックワード・トレースを実行するステップと、
を含むステップと、
前記リタイミング可能カットに関連する遅延時間を決定するために前記リタイミング可能カットを用いてタイミング評価を実行するステップと、
を含む方法。
【請求項２８】
請求項２７に記載の方法であって、
前記遅延時間が関連するタイミング制約に違反していない場合、前記リタイミング可能カットをセーブするステップを、
さらに含む方法。
【請求項２９】
請求項２７に記載の方法であって、前記リタイミング可能カットは、第１のリタイミング可能カットであり、該方法は、
リタイミングする前記信号パス沿いに第２のリタイミング可能カットを発見するステップと、
前記第２のリタイミング可能カットを用いてタイミング評価を実行して、前記第２のリタイミング可能カットに関連する遅延時間を決定するステップと、
前記第１のリタイミング可能カットに関連する前記遅延時間と前記第２のリタイミング可能カットに関連する前記遅延時間を比較して、最善のリタイミング可能カットを決定するステップと、
をさらに含む方法。
【請求項３０】
請求項２７に記載の方法であって、前記最善のリタイミング可能カットは、リタイミングする前記信号パスのスラック値に全体として最も優れた改善をもたらす、方法。
【請求項３１】
請求項２７に記載の方法であって、前記リタイミング可能カットは、フォワード・リタイミング可能カットである、方法。
【請求項３２】
請求項２７に記載の方法であって、前記リタイミング可能カットは、バックワード・リタイミング可能カットである、方法。
【請求項３３】
請求項２７に記載の方法であって、
前記リタイミング可能カットに含まれる少なくとも１つの順序素子のリタイミング後の初期状態を決定するステップを、
さらに含む方法。
【請求項３４】
請求項２７に記載の方法であって、
前記リタイミング可能カットに含まれる少なくとも１つの順序素子の１つまたは複数の制御信号を分離するステップを、
さらに含む方法。
【請求項３５】
請求項２７に記載の方法であって、前記集積回路が、フィールド・プログラマブル・ゲート・アレイである、方法。
【請求項３６】
請求項２７に記載の方法によってリタイミングされる集積回路。
【請求項３７】
請求項２７に記載の方法をコンピュータシステムに実行させるコンピュータ実行可能命令を保存するコンピュータ可読媒体。
【請求項３８】
請求項２７に記載の方法によってリタイミングされた集積回路の設計情報を含む設計データベースを保存するコンピュータ可読媒体。
【請求項３９】
ＥＤＡ（コンピュータによる電子回路の設計自動化）環境において集積回路をリタイミングするための方法であって、
前記集積回路内の１つまたは複数のパスについてタイミング解析を実行して、スラック値を取得するステップと、
前記取得したスラック値に基づいて前記パスの１つを選択するステップと、
前記選択したパス沿いのリタイミング可能カットを決定するステップであって、前記リタイミング可能カットは、前記集積回路内の１つまたは複数の論理インスタンスの一組の入力ピンを含み、前記選択されたパスのスラック値を改善するため、前記入力ピンに１つまたは複数のリタイミングした順序素子をそれぞれ結合することができ、前記リタイミング可能カットは、前記選択したパス沿いの２つまたはより多くの可能なカットから自動的に選択される、ステップと、
を含む方法。
【請求項４０】
請求項３９に記載の方法であって、前記一組の入力ピンは、前記リタイミングした順序素子の少なくとも１つから少なくとも論理インスタンス２つ離して配置された論理インスタンスに関連付けられる、方法。
【請求項４１】
請求項３９に記載の方法であって、
前記リタイミング後の順序素子の少なくとも１つの初期状態を決定するステップを、
さらに含む方法。
【請求項４２】
請求項３９に記載の方法であって、
前記リタイミング後の順序素子の少なくとも１つの構成上の制約を緩和するステップを、
さらに含む方法。
【請求項４３】
請求項３９に記載の方法であって、
前記リタイミング可能カット内に入力ピンを有する論理インスタンスからフォワード・トレースおよびバックワード・トレースを実行するステップを、
さらに含む方法。
【請求項４４】
請求項３９に記載の方法であって、前記リタイミング可能カットは、バックワード・リタイミング可能カットである、方法。
【請求項４５】
請求項３９に記載の方法であって、前記リタイミング可能カットは、フォワード・リタイミング可能カットである、方法。
【請求項４６】
請求項３９に記載の方法によってリタイミングされる集積回路。
【請求項４７】
請求項３９に記載の方法をコンピュータシステムに実行させるコンピュータ実行可能命令を保存するコンピュータ可読媒体。
【請求項４８】
請求項３９に記載の方法によってリタイミングされた集積回路の設計情報を含む設計データベースを保存するコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、２００３年３月１９日に出願された米国仮出願第６０／４５６３０６号の恩典を主張し、また２００３年１１月２１日に出願された米国仮出願第６０／５２４３００号の恩典を主張する。両出願を参照により本明細書に組み込む。
【０００２】
（技術分野）
本出願は、例えばフィールド・プログラマブル・ゲート・アレイなどの集積回路のリタイミングに関する。
【背景技術】
【０００３】
ＥＤＡ（コンピュータによる電子回路の設計自動化、ｅｌｅｃｔｒｏｎｉｃ  ｄｅｓｉｇｎ  ａｕｔｏｍａｔｉｏｎ）の出現によって、複雑なハードウェアシステムの設計が、ハードウェア回路図から始められることはもはやなくなった。それに代って、回路設計は一般に、ハードウェアシステムの挙動や機能を記述するソフトウェアプログラムから始められるようになった。例示的な一手法では、電子回路デザインの挙動または機能を、（例えば、ＶＨＤＬ、Ｖｅｒｉｌｏｇ、または他の同種の言語などの）ハードウェア記述言語（ＨＤＬ、ｈａｒｄｗａｒｅ−ｄｅｓｃｒｉｐｔｉｏｎ  ｌａｎｇｕａｇｅ）を用いて記述することができる。回路設計者は、ＥＤＡ論理合成ツールを用いて、回路内の素子および素子間の相互接続のリストから成るネットリストを生成することができる。論理合成ステージで、設計者は、何らかの設計制約（例えば、クロック、データパス素子の数およびタイプ、および／またはある機能を実行するのに望ましいクロックサイクル数など）を変更することによって、集積回路の代替構成を生成することができる。物理設計ステージでは、ネットリストと回路レイアウトについての情報を用いて、回路の様々な素子の配置および配線を決定することができる。その後、設計を具現した物理回路を作成することができる。
【０００４】
ＥＤＡ工程の一環として、回路デザインのタイミング特性が一般に評価される。これは、論理合成ステージの最中、回路の詳細な配置および配線を行う前に実施することができる。タイミング解析はまた、詳細な配置および配線を行った後の、ＥＤＡ工程の物理合成ステージの最中に実行することもできる。タイミング解析は一般に、回路デザインがそのデザインに内在する信号遅延を許容できるかどうかの評価を含む。例えば、あるクロック速度が与えられた場合、ある特定の回路デザインでは、適切に機能するために、信号がある一定の時間内に回路パスまたは回路素子を伝播する必要があるかもしれない。タイミング解析の間に、ある特定のパスまたは素子の実際の遅延時間が決定され、そのパスまたは素子で要求される時間と比較される。この比較によって、パスを伝わる信号の遅延時間（パス遅延）が、そのパスで要求される時間遅延を満たしているかどうかを決定することができる。実際の遅延時間と要求される遅延時間の相違量は、一般に「スラック（ｓｌａｃｋ）」と呼ばれる。本明細書で用いられるように、スラックは正数値をとることができ、これは、信号が要求されるよりも早く（すなわち、短い時間で）伝播し、タイミングにいくらかの余分な時間を盛り込めることを示している。スラックは負数値をとることもでき、これは、信号が回路のタイミング要件を満たすのに十分な時間で伝播しないことを示している。あるいは、スラックはゼロ値をとることができ、これは、信号が要求される時間遅延を満たすのに十分な時間で伝播するが、余分な時間は残っていないことを示している。したがって、ゼロ値または正数値のスラックは、パスまたは素子がタイミング要件を満たすことを示し、負数値のスラックは、回路を動作させたいクロック速度では、回路パスまたは素子がタイミング要件を満たすことができないことを示す。
【０００５】
総括的に「リタイミング」と呼ばれる技法では、回路素子を再配置し、再設定し、場合によっては回路デザインから取り除いて、ある特定の回路パスの遅延を減らしたり増やしたりすることができる。リタイミングは望ましくは、回路の機能が変化しないように実行される。すなわち、リタイミング後の回路の観察可能な挙動は、リタイミング前の回路の挙動と同一であるべきである。通常、リタイミングは、論理インスタンス（例えば、組合せロジック、参照用テーブル（ＬＵＴ）など）を越えての順序素子（例えば、フリップフロップ、ラッチ、レジスタ、または他のクロック駆動素子）の移動を含む。リタイミングは、例えば、回路を動作させるのに必要なクロック周期を最小にするため、回路内のレジスタ数を減らすため、かつ／または回路で消費される電力を削減するために実行することができる。例えば、クロック周期を最小にするためにリタイミングを実行する場合、１つまたは複数の順序素子を回路内で再配置して、すべての回路パスがゼロ値または正数値のスラックをもつようにすることができる。代替的に、クロック速度を遅くして、要求される遅延時間を増やし、回路内のすべての回路パスがゼロ値または正数値のスラックをもつようにすることもできる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
効果的であるためには、リタイミング技法はできるだけ正確であり、集積回路の実際の性能を確実に予測すべきである。しかし、多くの従来のリタイミング技法は、相互接続で発生する回路遅延を正確に把握していない。より小さなフィーチャサイズおよびより速いクロック速度へと向かい続ける趨勢の中にあって、回路の相互接続で発生する遅延は主要な問題となっている。実際、回路内の遅延の７０％ほどが、相互接続で発生する場合もある。したがって、相互接続遅延を解析し把握することのできる効果的なリタイミング操作は、有効な回路デザインにとって重要である。さらに、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）のますますの普及に伴い、ＦＰＧＡデザインに内在する構成および構造上の制約を把握することのできるリタイミング技法が望まれる。
【課題を解決するための手段】
【０００７】
集積回路をリタイミングするための様々な新規かつ非自明な例示的方法を、関連する装置と共に開示する。これらの方法は、例えば、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）または他の同種のプログラム可能論理デバイスをリタイミングし、あるいはリタイミング可能順序素子を有する集積回路をリタイミングするのに使用することができる。開示の例示的な方法は、いかなる点においても、限定的なものと解釈すべきではない。本開示はむしろ、様々な開示の実施形態の新規かつ非自明な特徴および態様に向けられており、それらの特徴および態様は、単独であることもあり、互いの様々な組合せおよび部分組合せであることもある。これらの方法は、どのような特定の態様または特徴、あるいはそれらの組合せにも限定されず、開示の方法は、１つまたは複数の具体的な利点が存在せず、あるいは問題が解決されなくてもかまわない。
【０００８】
開示の方法の１つは、集積回路をリタイミングするための例示的な方法である。この方法によれば、集積回路内の１つまたは複数のパスを伝播する信号の遅延時間を取得するために、それらのパスについてタイミング解析が実行される。取得した遅延時間に基づいて、パスの１つが選択される。選択されたパスは、タイミング制約を満たさない遅延時間を有しており、始点順序素子から始まり、終点順序素子で終る。選択されたパスはさらに、２またはより多くの論理インスタンスを含む。選択されたパス沿いのリタイミング・ロケーションが決定される。リタイミング・ロケーションは、タイミング制約を満たすように、始点順序素子または終点順序素子の一方を再配置することのできるロケーションである。さらに、この例示的な実施形態では、リタイミング・ロケーションは、再配置することのできる始点順序素子または終点順序素子の一方からの少なくとも２つの論理インスタンスである。始点順序素子または終点順序素子の一方をリタイミング・ロケーションに再配置するために、集積回路の設計データベースを更新する。本発明のいくつかの実施形態では、タイミング解析を実行する動作はさらに、取得した遅延時間とタイミング制約を用いて行われるスラック値の決定を含む。パスを選択する動作の間に、スラック値を評価することができる。いくつかの実施形態では、リタイミング・ロケーションを決定する動作は、回路機能を維持するために、さらに１つまたは複数の順序素子を、リタイミング・ロケーションあるいは１つまたは複数の追加のロケーションに再配置する必要があるかどうかについての決定を含む。リタイミング・ロケーションおよび１つまたは複数の追加のロケーションは、リタイミング可能カット（ｒｅｔｉｍｅａｂｌｅ  ｃｕｔ）を含むことができる。いくつかの実施形態では、リタイミング・ロケーションを決定する動作は、論理インスタンスの１つまたは複数の出力ピンからの少なくとも１つのフォワード・トレースの実行を含むことができ、その論理インスタンス越えて始点順序素子または終点順序素子の一方を再配置することができる。リタイミング・ロケーションを決定する動作は、論理インスタンスの１つまたは複数の入力ピンからの少なくとも１つのバックワード・トレースの実行をさらに含むことができ、その論理インスタンス越えて始点順序素子または終点順序素子の一方を再配置することができる。開示の方法はさらに、始点順序素子または終点順序素子の一方のリタイミング後の初期状態を決定する動作を含むことができる。この方法はまた、（例えば、１つまたは複数の制御信号を個々の順序素子から分離するなど）始点順序素子または終点順序素子の一方の構成上の制約の緩和を含むことができる。
【０００９】
集積回路をリタイミングするための別の開示の方法では、集積回路内のフェイリング（ｆａｉｌｉｎｇ）信号パスが特定される。フェイリング信号パスは、始点順序素子から始まり、論理コーンの１つまたは複数の論理インスタンスを通過して延び、終点順序素子で終る。フェイリング信号パスは、タイミング制約を満たすことのできない遅延時間を有する。フェイリング信号パスの遅延時間を改善するために始点順序素子または終点順序素子の一方を再配置することのできるフェイリング信号パス沿いのロケーションが選択される。この例示的な実施形態によれば、選択されたロケーションは、フェイリング信号パス沿いの論理インスタンスの１つに関連する。回路機能を維持するため、選択されたロケーションから、関連する論理インスタンスの出力パスおよび入力パスをサーチして、再配置する１つまたは複数の追加の順序素子を特定する。いくつかの実施形態では、出力パスおよび入力パスをサーチする動作は、回路機能を維持するために１つまたは複数の追加の順序回路を再配置する集積回路内の１つまたは複数の追加のロケーションの特定を含む。フェイリングパス内のロケーションおよび１つまたは複数の追加のロケーションは共に、リタイミング可能カットを含むことができる。フェイリング信号パス内のロケーションは、フォワード・リタイミング可能カットの一部を含み、出力パスおよび入力パスをサーチする動作は、論理インスタンスのうちの選択された１つが、１つまたは複数の順序素子または定常入力／出力ピンによって駆動されることの確認を含むことができる。代替的に、フェイリング信号パス内のロケーションは、バックワード・リタイミング可能カットの一部を含み、出力パスおよび入力パスをサーチする動作は、論理インスタンスのうちの選択された１つが、１つまたは複数の順序素子によって駆動されることの確認を含むことができる。本発明の一実施形態では、フェイリング信号パス沿いのロケーションは、始点順序素子または終点順序素子の一方を再配置するための複数のロケーションのうちの１つであり、始点順序素子または終点順序素子の一方のために選択されたロケーションは、フェイリング信号パスのスラック時間に最も優れた改善をもたらす。いくつかの実施形態では、この方法は、再配置することのできる始点順序素子または終点順序素子の一方、あるいは特定された１つまたは複数の追加の順序素子のリタイミング後の初期状態の決定を含むことができる。この方法はまた、（例えば、１つまたは複数の制御信号を個々の順序素子から分離するなど）再配置することのできる始点順序素子または終点順序素子の一方、あるいは特定された１つまたは複数の追加の順序素子の構成上の制約の緩和を含むことができる。
【００１０】
集積回路内のリタイミング可能カットを特定するための例示的な一方法も開示される。この実施形態では、リタイミングされる信号パスが選択される。信号パスは、始点順序素子から始まり、１つまたは複数の論理インスタンスを通過して延び、終点順序素子で終る。信号パス沿いのリタイミング可能カットが見つけられる。リタイミング可能カットを見つける動作は、信号パス内の選択された論理インスタンスの１つまたは複数の出力ピンからのフォワード・トレースの実行と、信号パス内の選択された論理インスタンスの１つまたは複数の入力ピンからのバックワード・トレースの実行を含むことができる。リタイミング可能カットに関連する遅延時間を決定するために、リタイミング可能カットを用いてタイミング評価が実行される。本発明のいくつかの実施形態では、遅延時間がタイミング制約に違反していない場合は、そのリタイミング可能カットをセーブすることができる。いくつかの実施形態では、前記リタイミング可能カットは、第１のリタイミング可能カットであり、この方法はさらに、信号パス沿いの第２のリタイミング可能カットの発見を含み、第２のリタイミング可能カットに関連する遅延時間を決定するために、第２のリタイミング可能カットを用いてタイミング評価が実行され、第１のリタイミング可能カットに関するスラック時間と第２のリタイミング可能カットに関するスラック時間を比較して、最善のリタイミング可能カットを決定する。最善のリタイミング可能カットは、リタイミングされた信号パスのスラック値が全体として最もよく改善されるリタイミング可能カットとすることができる。いくつかの実施形態では、リタイミング可能カットは、フォワード・リタイミング可能カットであり、別の実施形態では、リタイミング可能カットは、バックワード・リタイミング可能カットである。この方法はさらに、リタイミング可能カット内に含まれる１つまたは複数の順序素子のリタイミング後の初期状態の決定を含むことができ、あるいはリタイミング可能カット内に含まれる１つまたは複数の順序素子の制御信号の分離を含むことができる。
【００１１】
集積回路をリタイミングするための別の開示の方法は、集積回路内の１つまたは複数のパスのタイミング解析を実行してスラック値を取得するステップと、取得したスラック値に基づいて１つまたは複数のパスを選択するステップと、選択されたパス沿いのリタイミング可能カットを決定するステップとを含む。この実施形態によるリタイミング可能カットは、集積回路内の１つまたは複数の論理インスタンスの一組の入力ピンを含み、選択されたパスのスラック値を改善するため、これらのピンに、１つまたは複数のリタイミングされた順序素子をそれぞれ結合することができる。この実施形態では、リタイミング可能カットは、選択されたパス沿いの複数の可能なカットから自動的に選択される。具体的な一実施では、一組の入力ピンは、少なくとも１つのリタイミングされる順序素子からの少なくとも２つの論理インスタンスの論理インスタンスに関連付けられる。いくつかの実施形態では、この方法は、少なくとも１つのリタイミングされた順序素子の初期状態を決定するステップ、または少なくとも１つのリタイミングされる順序素子の構成上の制約を緩和するステップをさらに含む。いくつかの実施形態では、この方法は、リタイミング可能カットに関係する論理インスタンスからのフォワード・トレースおよびバックワード・トレースを実行するステップをさらに含む。リタイミング可能カットは、フォワード・リタイミング可能カットまたはバックワード・リタイミング可能カットとすることができる。
【００１２】
開示の実施形態はいずれも、コンピュータ可読媒体に保存されるコンピュータ実行可能命令でプログラムされたコンピュータによって実行することができる。これらの実施形態では、コンピュータ可読命令が、開示の実施形態のいずれかをコンピュータに実行させる。さらに、開示の実施形態のいずれかを使用して、コンピュータ可読媒体に保存された回路設計情報を更新または修正することができる。したがって、本明細書に記載の方法によってリタイミングされた回路デザインを保存する、修正された設計データベースも開示される。そのような方法は、例えば、スタンドアロン・ワークステーションで、またはネットワークを介して実行することができる。さらに、開示の方法によってリタイミングされた集積回路（例えば、開示の方法のいずれかによってリタイミングされたＦＰＧＡ）も開示される。
【００１３】
上記およびその他の特徴について、添付の図面を参照しながら以下に記載する。
【発明を実施するための最良の形態】
【００１４】
回路デザインを解析し、リタイミングするための方法の代表的な実施形態を、以下に開示する。開示の方法を、いかなる点においても、限定的なものと解釈すべきではない。本開示はむしろ、様々な開示の実施形態の新規かつ非自明な特徴および態様に向けられており、それらの特徴および態様は、単独であることもあり、互いの様々な組合せおよび部分組合せであることもある。これらの方法は、どのような特定の態様または特徴、あるいはそれらの組合せにも限定されず、開示の方法は、１つまたは複数の具体的な利点が存在せず、あるいは問題が解決されなくてもかまわない。
【００１５】
提示の都合から、いくつかの開示の方法における操作を特定の順序で説明したが、以下の説明で具体的な順序が、明示的な言葉によって要求されていない限り、この説明の仕方が別の順序も包含することを理解されたい。例えば、順番に説明される操作は、いくつかの場合では、順序を変更することができ、または同時に実行することができる。さらに、説明を簡潔にするため、添付の図面には、開示の方法を他の方法と共に使用できるようにする様々な手段を示していない。さらに、開示の方法を説明するのに、「決定する」、「評価する」などの語が説明中で使用されることがある。これらの語は、実行される実際の操作を高いレベルで抽象化したものである。これらの語に対応する実際の操作は、具体的な実施に応じて変化するが、当業者であれば容易に理解できるであろう。
【００１６】
開示の実施形態は、多種多様な順序集積回路に適用することができる。順序集積回路（または順序回路）とは、その出力が現在の入力に依存するだけでなく、過去の入力の順序、場合によっては任意の過去からの入力の順序にも依存する回路のことである。順序回路の例として、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）などのプログラム可能論理デバイス（ＰＬＤ）、特定用途向け集積回路（ＡＳＩＣ）、およびシステムオンチップ（ＳｏＣ）を挙げることができる。順序回路は、フリップフロップ、同期ＲＡＭ素子、またはラッチなど、少なくとも１つの順序回路素子を含む。一般に順序回路素子（または順序素子）とは、その出力状態の変化が自走クロック信号によって指定された時間に発生する任意の回路素子のことである。
【００１７】
開示の方法はいずれも、コンピュータ可読媒体に保存され、コンピュータ上で実行されるソフトウェアを用いて実行することができる。そのようなソフトウェアとして、例えば、論理または物理合成に利用されるＥＤＡ（コンピュータによる電子回路の設計自動化）ソフトウェアツールを挙げることができる。そのようなソフトウェアは、単一のコンピュータ上で、あるいは（例えば、インターネット、ワイドエリアネットワーク、ローカルエリアネットワーク、クライアント／サーバネットワーク、または他のネットワークを介して）ネットワーク接続されたコンピュータ上で実行することができる。説明を明瞭にするため、ソフトウェアベースの実施のうちいくつかの態様だけを選択して説明する。当技術分野で周知のその他の詳細は省略する。例えば、開示の技法が、特定のコンピュータ言語、プログラム、またはコンピュータに限定されるものではないことを理解されたい。同じ理由から、コンピュータハードウェアについては詳細に説明しない。
【００１８】
開示の方法は、全体的な合成方式の１つまたは複数のステージで用いることができる。例えば、開示のリタイミング方法はいずれも、論理合成後のデザインを最適化し、あるいは改良するのに利用することができる。開示のリタイミング方法は、実施されたデザインを改良するため、配置および配線を行った後に、使用することもできる。このステージでは、相互接続遅延など追加の物理的情報が一般には利用でき、遅延時間をより正確に計算することができる。
【００１９】
一般に、リタイミングは、特定の回路パスの遅延を減らしたり増やしたりするための、回路素子の再配置、再設定、場合によっては、回路デザインからの回路素子の除去を含む。本明細書で開示する集積回路をリタイミングするための方法は、フリップフロップ、ラッチ、または他のクロック駆動素子などの順序素子の再配置を含む。「レジスタ」という語は、本明細書では、ＦＰＧＡ内のフリップフロップまたは等価な順序素子を指すのにしばしば用いられる。
【００２０】
一般に、集積回路内のパスは、特定の始点順序素子の出力で始まり、複数の論理インスタンスを通過する相互接続に沿って延び、特定の終点順序素子の入力で終る。始点順序素子の出力は、その出力が２以上の終点順序素子の入力に接続される場合、２またはより多くのパスを駆動することがあり、終点順序素子の入力は、その入力が論理コーンを通過する２以上の始点順序素子の出力によって駆動される場合、２またはより多くのパスの終点から構成されることがある。この開示では、パスの「パス遅延」または「遅延時間」という語は、信号がパスの始点順序素子から終点順序素子まで１つまたは複数の論理インスタンスを通過して伝播するのに要する時間を指す。パス遅延は通常、（始点および終点順序素子を除く）パス沿いの回路素子の内部遅延と、パス沿いの相互接続の遅延の両方を含む。しかし、本発明の代替実施形態では、パス遅延は、始点順序素子と終点順序素子の一方または両方を含むことができ、かつ／または中間論理インスタンスを除外することもできる。
【００２１】
図１〜図３には、リタイミングの一例が示されている。この例では、図示の順序素子は、遅延なしで動作すると仮定される。図１には、順序素子（例えば、フリップフロップ）から成るバンク２０で始まり、順序素子から成る中間バンク２２を経由して、順序素子から成るバンク２４で終る、パイプライン１０が示されている。動作中、バンク２０の値が、組合せロジック４０（例えば、参照用テーブル（ＬＵＴ）、または１つまたは複数の論理ゲート）を通過するパス群３０に出力され、中間バンク２２に到達する。ロジック４０を通過するパス群３０の様々なパスにおける遅延は、パス毎に変化し得る。この例では、パス群３０の少なくとも１つのパスにおける最も長い遅延が１０ｎｓであるとする。組合せロジック４０で識別される遅延は、（２以上のパスが１０ｎｓの遅延を有することがあるので）最も遅いパスまたはパス群に等しい。次のクロックサイクルで、中間バンク２２からの値が、少なくとも１つのパスが最長遅延１４ｎｓを有する、組合せロジック４２を通過するパス群３２の様々なパスに出力され、バンク２４に到達する。図１に見られるように、図示のパイプライン１０を駆動するクロックは、クロック周期１２ｎｓを有する。したがって、パス群３２の少なくとも１つのパスが最長遅延１４ｎｓを有するので、パス群３２上の少なくとも１つの値は、次のクロックサイクルまでにバンク２４の入力に到達しない。したがって、パイプライン１０は、このタイミングの不一致を補正するか、クロック周期を遅くするかしないうちは、適切に機能しない。図１に示す状況では、パス群３２は、スラック値「−２」を有すると言われる。より具体的には、パス群３２のうちの最も遅いパスがスラック値「−２」を有し、これは、パス群３２の少なくとも１つのパスが２ｎｓだけタイミング要件を満たせていないことを示す。
【００２２】
図２には、「フォワード・リタイミング」と称されるリタイミングの１タイプが示されている。フォワード・リタイミングでは、１つまたは複数の順序素子を前方に移動させることによって、リタイミング対象のパスまたはパス群３２を短くする。図２に見られるように、例えば、組合せロジック４２の一部分４４を中間バンク２２’の入力側に再配置することによって、中間バンク２２’を２ｎｓだけ前方に移動させる。その結果、組合せロジック４２の最大遅延は１２ｎｓに短縮し、クロックのタイミング要件が満たされる。具体的には、リタイミングの後、バンク２０と中間バンク２２’の間のパス群、および中間バンク２２’とレジスタバンク２４の間のパス群は各々、最大遅延１２ｎｓを有し、クロックのタイミング要件を満足する。
【００２３】
図３には、「バックワード・リタイミング」と称されるリタイミングの第２のタイプが示されている。バックワード・リタイミングでは、１つまたは複数の順序素子をパイプラインの中で後方に移動させることによって、リタイミング対象のパスまたはパス群を短くする。図３に見られるように、例えば、組合せロジック４２の一部分４６をレジスタバンク２４’の出力側に再配置することによって、レジスタバンク２４’を後方に移動させて、ロジック４２を通過するパス群の最大遅延を１２ｎｓに短縮する。その結果、クロックのリタイミング要件が満たされる。フォワード・リタイミングおよびバックワード・リタイミングは共に他の信号パスにも影響を与えるので、隣接パスがタイミング要件を依然として満たしていることを保証するように、リタイミング対象パスは一般に検査される。
【００２４】
リタイミング操作中、再配置される順序素子の初期状態を再設定する必要が起こる場合がある。例えば、リタイミング対象の順序素子がフリップフロップである場合、リタイミングされる回路の機能を適切に維持するため、フリップフロップの初期状態をＲＥＳＥＴからＳＥＴに、またはＰＲＥＳＥＴからＣＬＥＡＲに変更しなければならない場合がある。リタイミングされた順序素子を再設定する必要があるかどうかは、順序素子がそれを越えて移動する１つまたは複数の論理インスタンスの機能を評価することによって決定される。さらに、リタイミング操作が何らかの設計規則に違反するため、それ以外の点では有効なリタイミング操作を実行すべきではない場合がある。以下でさらに詳しく説明するように、例えば、多くのＦＰＧＡデザインは、分割できない、または違反できないＦＰＧＡ構成設計規則を含んだ組合せロジックのブロックを含む。
【００２５】
リタイミングは、回路を一度に１論理インスタンスずつ解析し、インスタンス単位で順序素子を再配置することによって実行することができる。しかし、この技法は、時間がかかり、集中的な計算を要することがある。対照的に、多くの場合、回路の１つまたは複数の順序素子を組合せ構成要素のグループ（すなわち２つまたはより多くの論理インスタンス）を越えて移動させることができ、その結果、より効率的なリタイミングが可能となる。この開示では、順序素子を再配置またはリタイミングできる回路内の場所または位置を「カット」と称する。より具体的には、カットは、リタイミング対象の順序素子を挿入できる（例えば、ＦＰＧＡ内のＬＵＴといった論理インスタンスの）一組のインスタンス・ピンから構成される。これに対応して、カット内の各インスタンス・ピンは「カット・ピン（ｃｕｔ  ｐｉｎ）」と呼ばれる。以下で説明する例示的な実施形態では、カット・ピンは一般に、論理インスタンスの入力ピンから構成される。しかし、この慣習を限定的なものと解釈すべきではなく、カット・ピンが論理インスタンスの出力ピンから、または出力ピンと入力ピンの組合せから構成されるように、記載の実施形態を容易に変更することができる。どのようなデバイス構成規則にも違反することなく、あるカットにリタイミング対象の順序素子を挿入できるならば、そのカットは「有効カット」と称される（例えば、レジスタをカットに配置した際に、どのようなＦＰＧＡデバイス構成規則にも違反しないカット）。さらに、回路機能を変化させることなく、リタイミング対象の順序素子を配置できる有効カットは、「リタイミング可能カット」と称され、回路内の他の順序素子を再配置する必要がある追加のインスタンス・ピンを含むことがある。
【００２６】
リタイミング可能カットの例示的な一形態は一般に、集積回路内の論理コーン（ｃｏｎｅ）を第１（または左側）の区画と第２（または右側）の区画に分割し、リタイミングされた素子の一方の側にファンアウトなし（ｆａｎ−ｏｕｔ−ｆｒｅｅ）の論理コーンを生成するものとして特徴付けることができる。具体的な一実施形態では、フォワード・リタイミング可能カットは、論理コーンの第１（または左側）の区画から、カット自体へのものを除いて、ファンアウトがなく、第１（または左側）の区画が、互換順序素子（例えば、等価な順序素子）または定常ピン（定常入力／出力ピン）のどちらかによって駆動される、リタイミング可能カットから構成される。同様に、この実施形態によれば、バックワード・リタイミング可能カットは、論理コーンの第２（または右側）の区画への、カット自体からのものを除いて、ファンインがなく、第２（または右側）の区画が、１つまたは複数の順序素子を駆動する、リタイミング可能カットから構成される。リタイミング可能カットが、論理コーンへの入力とならない１つまたは複数のファンアウトを有する順序素子によって駆動される場合、そのカットは依然としてリタイミング可能であることができる。しかし、このような場合、回路機能を維持するため、リタイミング後に順序素子を回路内に残す必要がある場合もある。
【００２７】
図４Ａ〜図４Ｂは、集積回路の論理コーンにおけるカットベース・リタイミングの例を示した概略ブロック図である。具体的には、図４Ａには、論理コーン５４を駆動するレジスタ群５２から成る第１のバンクを含む、ＦＰＧＡの例示的な一部分５０が示されている。一般に、論理コーン５４は、レジスタ群５６から成る第２のバンクを駆動する１つまたは複数の論理インスタンス（例えば、１つまたは複数のＬＵＴ）を含む。レジスタ群５２から成る第１のバンクは、様々な他の回路構成要素５８によって駆動される。レジスタ群５２から成る第１のバンクまたは様々な他の回路構成要素５８は、論理コーン５４の外部の他の回路構成要素を駆動する１つまたは複数の出力パスを含むことができる。しかし、論理コーン５４は、第２のバンクのレジスタ群５６を除き、レジスタへのファンアウトを有しない点で特徴付けられる。
【００２８】
図４Ａには、論理コーン５４を第１（または左側）の区画６４と第２（または右側）の区画６６に分割するリタイミング可能カット６０が概略的に示されている。図示の例では、カット６０はフォワード・リタイミング可能カットである。したがって、図４Ｂに示すように、第１のバンクのレジスタ群５２の一部分６２が、リタイミング可能カット６０に再配置される。リタイミングされたレジスタ群６２は、左側の区画６４によって駆動され、右側の区画６６を駆動して、リタイミングされたレジスタ群６２とレジスタ群５６から成る第２のバンクの間のスラックを効果的に減少させる。
【００２９】
図５は、例示的な回路における様々なタイプのカットを示した概略ブロック図である。具体的には、回路７０は、ＦＰＧＡなどの回路の一部分であり、７つのレジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄ、Ｒｅ、Ｒｆ、Ｒｇと、５つの参照用テーブルＬＵＴ１、ＬＵＴ２、ＬＵＴ３、ＬＵＴ４、ＬＵＴ５を含む。図示の回路では、信号は、図の左側の第１の組のレジスタ（Ｒａ、Ｒｂ、Ｒｃ、Ｒｄ）から、ＬＵＴを経由して、図の右側の第２の組のレジスタ（Ｒｅ、Ｒｆ、Ｒｇ）に伝播する。図５のＬＵＴは、レジスタの第１の組と第２の組の間に論理コーンを形成する。（カット「Ａ」と名づけられた）第１のカット８０は、ＬＵＴ１、ＬＵＴ２、ＬＵＴ３、ＬＵＴ４を越える、Ｒａ、Ｒｂ、Ｒｃ、Ｒｄのフォワード・リタイミングを可能とする。具体的には、この例のカット８０は、カットとレジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄの間にファンアウトがないため、リタイミング可能である（レジスタ群が、その出力信号が第１のＬＵＴで論理コーンに入る前にファンアウトをもつとしても、リタイミングを達成できることに留意されたい。しかし、このような状況では、回路機能を維持するため、リタイミング後に順序素子を回路内に残す必要がある場合もある）。図６は、レジスタＲａ、Ｒｂ、Ｒｃ、Ｒｄをリタイミング可能カット８０に再配置した後の、回路７０の概略ブロック図である。リタイミングされたレジスタＲｒｅｔｉｍ．１、Ｒｒｅｔｉｍ．２が、（「Ａ」で示す）カット８０のところに示されている。図６から分かるように、フォワード・リタイミング可能カット８０を用いて回路７０をリタイミングする場合、論理コーンを駆動するのに使用されるレジスタの数が４から２に減少している。ＬＵＴ１、ＬＵＴ２、ＬＵＴ３、ＬＵＴ４の機能に応じて、回路７０内で機能的等価性を維持するため、リタイミングされた２つのレジスタの初期状態を調整しなければならない場合もある。
【００３０】
図５に戻ると、（カット「Ｂ」と名づけられた）第２のカット８２は、ＬＵＴ３、ＬＵＴ５を越える、Ｒｅ、Ｒｆのバックワード・リタイミングを可能とする。具体的には、カット８２は、カットとレジスタＲｅ、Ｒｆの間に論理コーンへのファンインがないため、リタイミング可能である。図７は、レジスタＲｅ、Ｒｆをリタイミング可能カット８２に再配置した後の、回路７０の概略ブロック図である。図７に見られるように、レジスタＲｅ、Ｒｆは、（図７において「Ｂ」で示す）カット８２沿いに配置された３つのリタイミングされたレジスタＲｒｅｔｉｍ．１、Ｒｒｅｔｉｍ．２、Ｒｒｅｔｉｍ．３によって置き換えられている。ＬＵＴ３、ＬＵＴ５の機能に応じて、回路７０内で機能的等価性を維持するため、リタイミングされたレジスタの初期状態を調整しなければならない場合もある。
【００３１】
図５に戻ると、（カット「Ｃ」と名づけられた）第３のカット８４は、この例ではフォワード・リタイミングについての無効カットを表す。すなわち、第３のカット８４は、カットとリタイミング対象レジスタの間にファンアウトがあるため、容認されない。具体的には、レジスタＲｂはＬＵＴ１にファンアウトし、ＬＵＴ２はＬＵＴ３にファンアウトするが、それらは、第３のカット８４に含まれない信号である。
【００３２】
（カット「Ｄ」と名づけられた）第４のカット８６は、この例ではバックワード・リタイミングについての無効カットを表す。第４のカット８６は、カットとリタイミング対象レジスタの間のロジックへのファンインがあるため、容認されない。具体的には、ＬＵＴ２はＲｂからの入力パスを有し、ＬＵＴ５はＬＵＴ３からの入力パスを有するが、それらは、カットに含まれないレジスタＲａ、Ｒｂからの信号によって駆動される。
【００３３】
一般に、開示のリタイミング操作の最中に考慮され得る複数のタイプの制約が存在する。考慮される制約には、タイミング制約、構成上の制約、構造上の制約がある。タイミング制約は、デザイン中のパスに最大および／または最小の遅延をもつように要求する設計制約を含む。要求される遅延は、関連するクロック信号のサイクル周期によって指示することができ、または設計者が明示的に定義することもできる。パスは、タイミング制約をもたないことがあり（「疑似パス」と呼ばれることがある）、またはある特定のパスが複数のクロックドメインに結合されるような場合、重複する制約をもつことがある。別のタイプのタイミング制約として、リタイミング操作を実行するのに使用される順序素子の数は、元のレジスタの数より少ないか、あるいは等しいという要件を挙げることができる。例えば、デザイン中の順序素子によるオーバヘッドを減らすためにリタイミング操作が利用される場合などに、この制約は、望ましいものとなり得る。
【００３４】
構成上の制約とは、リタイミング対象の集積デバイスに固有のデザインによって提示される制約である。例えば、ＦＰＧＡの場合、レジスタは一般に、事前に製造され、あるロケーションに配置される。したがって、リタイミングのために、レジスタをすでに決定されたロケーション以外のロケーションに移動させることはできない。さらに、あるパスまたは回路構成要素は、事前に製造され、リタイミング中に分割することはできない。例えば、Ｘｉｌｉｎｘ（登録商標）が製造するＶｉｒｔｅｘ−ＩＩ（登録商標）ＦＰＧＡでは、構成可能論理ブロック（ＣＬＢ）が、いくつかのＬＵＴと２つの２入力１出力マルチプレクサ（ＭＵＸＦ５、ＭＵＸＦ６）を使用して、８入力１出力マルチプレクサを実装する。この構成では、マルチプレクサＭＵＸＦ５とＭＵＸＦ６の間にレジスタを挿入することは許可されない。図８には、リタイミングできないＶｉｒｔｅｘ−ＩＩ（登録商標）構成の一部分の別の例が示されている。具体的には、図８には、２つの２入力１出力マルチプレクサ１０２（ＭＵＸＣＹ）を用いて実装された加算器回路の桁上げチェーン１００が示されており、これらのマルチプレクサは、高速１ビット桁上げ伝播機能を実行するのに使用される。図８には、Ｖｉｒｔｅｘ−ＩＩ（登録商標）ＦＰＧＡの構成規則に従えば、リタイミングされたレジスタを配置すると規則違反になるロケーション１０４も示されている。レジスタを違反となるロケーションに配置した場合、桁上げチェーンがレジスタによって分断され、高速ローカル接続が使用できなくなるので、遅延が著しく増大する。
【００３５】
いくつかの制約は、論理および／または配置転換によって緩和することができる。例えば、上述した第１の例に関して、ＭＵＸＦ６マルチプレクサを、ＦＰＧＡの別個のスライスにＬＵＴとして実装することができ、そうすることによって、ＭＵＸＦ５とＬＵＴの間にレジスタを挿入することが可能になる。このタイプの転換は、リタイミング可能性の改善を図ることができるが、回路構成要素の全体的な配置を混乱させることがあり、タイミング性能に全体として負の影響を及ぼすことがある。したがって、開示の技法のいくつかの実施形態では、論理および／または配置転換は、リタイミング可能カットの既存の有効ロケーションを用いて回路をリタイミングできない場合のみ考察される。そのような転換を行った後、物理タイミング解析ツール（例えば、増分タイミング解析ツール）を用いて、回路の動作を確認するのがしばしば望ましい。上述の例は、説明のためのものに過ぎず、いかなる点においても限定的なものと解釈すべきではない。実際、構成上の制約のタイプおよび質は、リタイミングのために解析される具体的な回路に応じて変化する。
【００３６】
構造上の制約は一般に、回路内に実装された際にリタイミング可能性を制限する回路構成要素を生成する場合がある、ネットリスト構造に起因する。例えば、レジスタが不等価な制御信号を有する場合、リタイミング操作は阻害される。しかし、そのような制約を克服するため、制御信号をレジスタから分離することができる場合があり、そうすることによって、レジスタを等価にし、リタイミング可能にする。制御信号分離のいくつかの例を、図９〜図１２に関して以下で説明する。しかし、これらの例を限定的なものと解釈すべきではなく、以下の説明で例示される原理のいずれかを利用する、信号分割のさらに別の方法も可能である。
【００３７】
最初に、図９Ａに示すようなＦＰＧＡの２つのレジスタについて考察する。第１のレジスタ１１０は、クロック信号（図示せず）によって駆動される通常のＤ型フリップフロップである。第２のレジスタ１１２は、クロック有効信号（ＣＥ）を含むＤ型フリップフロップである。第１のレジスタ１１０は制御信号をもたず、第２のレジスタ１１２はもつので、２つのレジスタは等価ではない。図９Ｂに見られるように、第２のレジスタ１１２に関して、クロック有効信号を第２のレジスタから分離する転換を実行することができる。具体的には、クロック有効信号をもたない通常のＤ型フリップフロップで構成されるレジスタ１１４からＱ信号をループバックするのに、クロック有効信号によって制御されるマルチプレクサ１１８を使用し、元のレジスタ１１２と機能的に等価なレジスタ構造を生成することができる。この転換が実行された後、この例では、レジスタをリタイミングすることができる。リタイミングを行った結果の回路が図９Ｃに示されており、マルチプレクサ１１８へのフィードバックパスを有する、リタイミングされたレジスタ１２０を１つ含む。
【００３８】
次に、図１０Ａに示すようなＦＰＧＡの２つのレジスタについて考察する。レジスタ１３０は、同期セット入力を有する単一のＤ型フリップフロップ（例えば、Ｘｉｌｉｎｘ（登録商標）のＦＤＳレジスタ）であり、レジスタ１３２は、同期リセット入力を有する単一のＤ型フリップフロップ（例えば、Ｘｉｌｉｎｘ（登録商標）のＦＤＲレジスタ）である。図１０Ａでは、レジスタ１３０、１３２は、同一クロック（図示せず）によって駆動される。２つの等価なレジスタ１３４、１３５をレジスタ１３０、１３２の代りに使用できるように、レジスタ１３０、１３２のセットおよびリセット信号を、図１０Ｂに示すように分離することができる。具体的には、レジスタ１３０からのセット信号の分離は、入力信号Ｄ１およびＳに関して論理関数Ｄ１＋Ｓを実行する論理インスタンス１４０（例えば、論理ゲート、または図示するようなＬＵＴ）を、レジスタ１３４の上流に実装することによって達成することができる。結果として得られる論理インスタンス１４０からの出力は、レジスタ１３０の動作と等価であり、レジスタを通常のＤ型フリップフロップ（例えば、Ｘｉｌｉｎｘ（登録商標）のＦＤレジスタ）として再実装することができる。同様に、レジスタ１３２からのリセット信号は、入力信号Ｄ２およびＲに関して論理関数
【００３９】
【数１】
2007524891.tif 000003
を実行する論理インスタンス１４２を実装することによって分離することができる。図１０Ｃに示すように、結果として得られる等価なレジスタ１３４、１３５は、リタイミングされたレジスタ１３６として、論理インスタンス１４４を越えてリタイミングすることができる。
【００４０】
状況によっては、デザイン中のレジスタから制御信号を分離する必要がない場合もある。例えば、レジスタ１３０、１３２のセットおよびリセット信号が同じであれば、論理インスタンス１４４の機能に関して適切なレジスタの初期状態を計算することによって、２つのレジスタをフォワード・リタイミングすることができる。例えば、論理インスタンスがＯＲ関数を実行する場合、レジスタ１３０、１３２の初期状態が、それぞれ１および０であれば、リタイミングされたレジスタ１３６の初期状態は１とすべきである。
【００４１】
次に、図１１Ａに示すようなＦＰＧＡのレジスタについて考察する。レジスタ１５０は、Ｄ型フリップフロップから構成され、レジスタ１５２は、クロック有効信号（ＣＥ）と同期セット信号（Ｓ）を有するＤ型フリップフロップ（例えば、Ｘｉｌｉｎｘ（登録商標）のＦＤＳＥレジスタ）から構成される。図１１Ｂに示すように、クロック有効信号と同期セット信号は共に、Ｄ型フリップフロップ１５４と４入力論理インスタンス１６２（例えば、４入力ＬＵＴ）によって置き換えることができる。具体的には、４入力論理インスタンス１６２は、論理関数
【００４２】
【数２】
2007524891.tif 000004
を実行する。ただし、Ｑはレジスタ１５４からの出力とする。図１１Ｃに示すように、レジ１５０、１５４は、リタイミングされたレジスタ１５６として、論理インスタンス１６０を越えてリタイミングすることができる。先に述べたように、これらの転換は、カットをリタイミング可能にする必要がある場合に用いることができる。本発明の一実施形態では、転換は、配置が可能であり、タイミングへの影響が肯定的なものである場合のみ用いることができる。
【００４３】
構造上の制約は、他の方法を用いても同じように緩和することがしばしば可能である。例えば、レジスタを駆動する１つの出力と駆動しない別の出力を有する論理インスタンスを越えて、レジスタをバックワード・リタイミングすることが望ましい場合、論理インスタンスの複製を作成して、複製にレジスタを駆動しない出力をもたせることができる。したがって、元の論理インスタンスは、レジスタを駆動する出力だけを有し、この例では、リタイミングすることができる。しかし、そのような転換は、組合せロジックのネットリストを変更し、全体的な回路デザインに負の影響を及ぼすことがある。したがって、本明細書で開示するいずれの実施形態でも、そのような転換は、肯定的な影響をもつことが確認された場合にのみ実行することができる。
【００４４】
図１２のフローチャートは、リタイミング可能カットを用いて回路をリタイミングするための例示的な方法２００を示している。必ずしも必要ではないが、例示的な方法２００は望ましくは、初期配置および配線を行った後に実行される。ＦＰＧＡについて言及するが、図１２に示す例示的な方法は、任意の適切な回路（例えば、ＡＳＩＣ、ＳＯＣ、またはリタイミング可能順序素子を含み、類似のタイミング制約を有する他のデバイス）をリタイミングするのに用いることができる。さらに、図１２に示す例示的な方法は、レジスタのリタイミングに関して説明されるが、この方法は一般に、回路のどのようなリタイミング可能順序素子（例えば、ラッチなど）にも適用することができる。
【００４５】
手順ブロック２０２で、遅延時間を取得するため、集積回路の１つまたは複数のパスについてタイミング解析が実行される。このタイミング解析は望ましくは、実際の回路デザインに存在するタイミング制約を取り扱うことができる多用途タイミング解析エンジンを用いて実行される。例えば、本発明の例示的な一実施形態では、メンターグラフィックスコーポレーション（登録商標）から入手できるＳＳＴ  Ｖｅｌｏｃｉｔｙ（登録商標）タイミング解析エンジンが使用される。具体的な一実施形態では、タイミング解析エンジンは、設計者または使用者が、回路全体のタイミングを計算しなくても、回路デザインの特定領域（例えば、特定の論理コーン）に対するタイミング変化を解析し評価できるようにする増分解析を実行することができる。本発明の一実施形態では、タイミング解析は、１つまたは複数のパスについて計算されたスラック値を含む。
【００４６】
手順ブロック２０４で、手順ブロック２０２で取得した遅延時間に基づいて、回路のレジスタ群をソートする。本発明の一実施形態では、レジスタ群をソートするのにパスのスラック値が用いられる。具体的な一実施形態では、例えば、レジスタに関連するスラック値は、そのレジスタによって駆動されるパスにおける最悪のスラック時間に対応する。この実施形態によれば、例えば、レジスタがスラック値−３、−１、および２ｎｓを有する３つのパスを駆動する場合、そのレジスタは、スラック値−３を有すると見なされる。いくつかの実施形態では、手順ブロック２０４は実行されない。
【００４７】
手順ブロック２０６で、手順ブロック２０４でソートしたレジスタ群から１つのレジスタを選択する。この選択は、複数の異なる基準に基づいて行うことができる。本発明の例示的な一実施形態では、例えば、最大の負のスラック値を有するレジスタが選択される。このレジスタは、ソートされたレジスタ群のリスト中の第１のレジスタに対応することができる。
【００４８】
手順ブロック２０８で、選択されたレジスタにとって最善のリタイミング可能カットが見つけられる。最善のリタイミング可能カットを見つけるため、フォワード・リタイミング可能カット、バックワード・リタイミング可能カット、または両方の組合せについてサーチを実行することができる。最善のフォワード・リタイミング可能カットを見つけるための例示的な方法が、図１４および図１５に示されており、以下でより詳しく説明する。最善のバックワード・リタイミング可能カットを見つけるための例示的な方法が、図１８に示されており、以下でより詳しく説明する。
【００４９】
手順ブロック２１０で、最善のリタイミング可能カットを含むように、回路デザインが更新（または変更）される。具体的には、更新された回路デザインでは、選択されたレジスタおよび最善のリタイミング可能カットに含まれる他のレジスタが再配置される。本発明のいくつかの実施形態では、手順ブロック２１２に示すように、この更新手順は、回路機能を維持するため、リタイミングされたレジスタの初期状態の決定および再設定を含むことができる。例えば、図１３には、リタイミングされる前の３つのレジスタ２４０、２４２、２４４の初期状態が示されている。レジスタ２４０（Ｒａ）は初期状態がｓｅｔであり、レジスタ２４２（Ｒｂ）はｒｅｓｅｔであり、レジスタ２４４（Ｒｃ）はｓｅｔである。図１３には、論理関数
【００５０】
【数３】
2007524891.tif 000005
を実行する例示的な論理インスタンス２４６（例えば、ＬＵＴ）も示されている。レジスタが初期状態にあるとき、論理インスタンス２４６の出力はハイとなる。リタイミング後、３つのレジスタは取り除かれ、１つのフォワード・リタイミングレジスタ２４８（Ｒｒｅｔｉｍ．）に置き換えられる。論理インスタンス２４６の出力側に配置されるリタイミングされたレジスタ２４８は、リタイミング前に伝播していたのと同じ値が論理インスタンス２４６の下流に伝播するように、初期状態「ｓｅｔ」を有するように設定すべきである。Ｖ．シンガル（Ｓｉｎｇｈａｌ）、Ｍ．シャラド（Ｓｈａｒａｄ）、Ｒ．ブライトン（Ｂｒａｙｔｏｎ）、「明示的リセット回路を用いたリタイミングの事例（Ｔｈｅ  Ｃａｓｅ  ｆｏｒ  Ｒｅｔｉｍｉｎｇ  ｗｉｔｈ  Ｅｘｐｌｉｃｉｔ  Ｒｅｓｅｔ  Ｃｉｒｃｕｉｔｒｙ）」、コンピュータ援用設計国際会議会報（Ｐｒｏｃ．  ｏｆ  Ｉｎｔｌ．  Ｃｏｎｆ．  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ）（１９９６年１１月）に記載の例示的な技法を、初期状態を計算するのに用いることができ、同文献を参照により本明細書に組み込む。
【００５１】
図１２に戻ると、手順ブロック２１４に示すように、回路デザインを更新するステップは、構成／構造上の制約を緩和するステップをさらに含むことができる。上でより詳しく説明したように、構成／構造上の制約を緩和するステップは、いくつかの順序素子から制御信号を分離して、それらを等価にし、その結果、リタイミング可能にするステップを含むことができる。
【００５２】
手順ブロック２１６で、増分配置（ｉｎｃｒｅｍｅｎｔａｌ  ｐｌａｃｅｍｅｎｔ）および物理的リタイミングが実行される。リタイミングは望ましくは、できるだけ元の配置を混乱させないように行うべきである。本発明のいくつかの実施形態では、リタイミング中、同じ物理ロケーションでのインスタンスの重複を許容することができる。これらの実施形態では、リタイミング後、タイミング駆動増分配置を用いて、すべての重複を取り除くことができる。増分配置を行う際、必ずしも必要ではないが、予期せぬ長い相互接続遅延を回避するため、リタイミングされたレジスタをカット・ピンの近くに配置するのが望ましい。本発明の例示的な一実施形態では、相互接続遅延を把握でき、ワイヤロード遅延モデルではなく物理遅延モデルを構築できるタイミングアナライザが、物理リタイミングを行う際に使用される。
【００５３】
増分配置を行う際、リタイミング対象のレジスタが「配置可能」であるかどうか判定することができる。すなわち、リタイミング対象の順序素子を特定のロケーションに配置した場合、集積回路（例えば、ＦＰＧＡ）の構成規則のいずれかに違反するかどうか判定することができる。例えば、特定のＦＰＧＡ構成の単一スライスは、２つ以上のレジスタを保有することができるかもしれないが、クロック有効ピンを外部接続に接続する信号線は１本しかもたないかもしれない。したがって、クロック有効信号を有するレジスタがスライス内にすでに１つ配置されており、クロック有効信号を有する新しいレジスタを同じスライス内にさらに配置する場合、２つのレジスタのクロック有効信号は同じでなければならない。同じでない場合は、配置および配線はできないかもしれない。
【００５４】
増分配置を行う際、リタイミング操作に起因する全体的な密集を評価することもできる。例えば、バックワード・リタイミング中に大きなリタイミング可能カットが見つかった場合、多数の新しいレジスタを生成し、カットロケーションの周辺に配置する必要が起こるかもしれない。多数の新しいレジスタは回路内に激しい密集を生むため、（例えば、ＦＰＧＡのデザイン、許容可能なレジスタの事前設定された数、またはその他の基準に基づいて）カットでのリタイミングは拒否されるかもしれない。
【００５５】
図１２の手順ブロック２１８で、考察すべきレジスタ（例えば、負のスラック時間を有する別のレジスタ）がまだ他にも存在するかどうか判定される。存在する場合、手順２００は望ましくは、（ソートされたレジスタ群からの、または手順ブロック２１６の物理リタイミング中に特定された）次のレジスタについて、手順ブロック２０６から繰り返される。存在しない場合、リタイミング手順２００は、手順ブロック２２０で終了する。
【００５６】
図１４には、最善のフォワード・リタイミング可能カットを見つけるための例示的な手順２５０が示されている。この手順は、例えば、図１２の手順ブロック２０８における最善のリタイミング可能カットを見つける手順の少なくとも一部として用いることができる。図示の実施形態によれば、手順２５０は、最大の負のスラック時間を有する、選択されたレジスタからのパスについて実行される。本明細書では、このパスを「フェイリングパス」と呼ぶことがある。手順ブロック２５２で、フェイリングパス沿いの論理インスタンスの第１のピンが選択される。本発明の一実施形態によれば、第１のピンは、選択されたレジスタで始まるフェイリングパス沿いの最初の論理インスタンスの入力ピンである。手順ブロック２５４で、選択されたピンを用いて、フォワード・リタイミング可能カットが見つけられる。フォワード・リタイミング可能カットを見つける例示的な方法について、図１５を参照しながら以下で説明する。手順ブロック２５６で、見つけられたフォワード・リタイミング可能カットについて増分タイミング評価を実行して、カットの結果である新しい遅延時間および／またはスラック値を決定する。手順ブロック２５８で、そのカットが、方法２５０で最初に見つけられたカットであるかどうかが判定される。カットが最初に見つけられたカットである場合、手順ブロック２６０で、そのカットがセーブされる。カットが最初に見つけられたカットでない場合、手順ブロック２６２で、現在のカットの遅延時間および／またはスラック値が、セーブされたカットの遅延時間および／またはスラック値と比較される。現在のカットの時間のほうがセーブされたカットの時間より優れている場合（例えば、フェイリングパス沿いの全体的な時間短縮によって決定される）、手順ブロック２６３で、現在のカットがセーブされて、それまでセーブされていたカットと置き換えられる。代替的に、後の評価のために、複数のカットをセーブしてもよい。例えば、２またはより多くのカットによって、申し分のないスラック値の改善がもたらされる場合がある。しかし、スラック値の改善はさほど大きくはないにしても、カットを１つにしたほうが、実装はより簡単になるであろう。この場合、最善のカットが最も良いタイミング性能を達成しなくても、それを最も望ましいカットと見なすことができる。しかし、大概は、最善のカットが、最大のタイミング改善を提供するカットであると見なされる。手順ブロック２６４で、フェイリングパス沿いにまだ考察する入力ピンがあるかどうか判断される。例えば、本発明の一実施形態では、フェイリングパス沿いのインスタンス・ピンは、パスの始点順序素子から終点順序素子へ順番に考察される。考察するピンがまだある場合、手順ブロック２６６で、次のピンが選択され、方法２５０が手順ブロック２５４から繰り返される。考察するピンがもうない場合、方法２５０は手順ブロック２６８で終了し、最善のフォワード・リタイミング可能カットが返される。最善のバックワード・リタイミング可能カットを見つける手順も、バックワード・リタイミング可能カットを見つけ（手順ブロック２５４）、評価する（手順ブロック２５６から２６４）点を除いて、上述した手順と類似している。本発明の例示的な一実施形態では、最善のバックワード・リタイミング可能カットを見つける手順は、フェイリングパス沿いの最後の論理インスタンスの入力ピンで始まり、フェイリングパス沿いの最初の論理インスタンスに向かって順番に進められる。バックワード・リタイミング可能カットを見つけるための例示的な方法については、図１８に関して以下で説明する。
【００５７】
図１５には、図１４の手順ブロック２５４で用いることのできるフォワード・リタイミング可能カットを見つけるための例示的な方法３００が示されている。一般に、方法３００は、選択された入力ピンに関連する論理インスタンスから、論理コーンのパスを前方および後方にトレースする。フォワードおよびバックワード・トレースを行うこの手順は、回路機能を維持するためにリタイミングする必要がある他の順序素子を特定し、評価するのに役立つ。この手順は、見つかったカットが有効であることを保証するのにも役立つ。例えば、フォワード・リタイミング可能カットの場合、バックワード・トレースを行う手順は、論理コーンの第１（または左側）の区画からファンアウトがないこと、またリタイミング可能カットの第１（または左側）の区画が互換順序素子または定常出力ピンによって駆動されることを確認するのに有用である。
【００５８】
図１５の手順ブロック３０２で、選択された入力ピンに関連する論理インスタンスの出力ピンから、フォワード・トレースが実行される。例えば、ＡＮＤ関数を実行するＬＵＴの入力ピンが選択された場合、そのＬＵＴの出力ピンによって駆動されるすべてのパスがトレースされる。一般に、「フォワード・トレース」とは、特定の出力ピンによって駆動される入力ピンを特定する手順のことである。関連する入力ピンは、例えば、ネットリストまたは回路デザインを保存する他の設計データベース（例えば、ＶＨＤＬまたはＶｅｒｉｌｏｇファイル）から特定することができる。手順ブロック３０４で、手順ブロック３０２で特定された入力ピンがカットに追加される。手順ブロック３０６で、バックワード・トレースが実行される。本発明の一実施形態では、バックワード・トレースは、選択された入力ピン自体を含む、選択された入力ピンに関連する論理インスタンスのすべての入力ピンから実行される。フォワード・トレースに類似して、「バックワード・トレース」とは、特定の入力ピンを駆動する出力ピンを特定すると共に、特定されたそれらの出力ピンによって駆動される他の入力ピンを特定する手順のことである。バックワード・トレースの間に特定された出力ピン（すなわち、ドライバ）の各々について、手順ブロック３０８で、ドライバがリタイミング可能であるかどうかが決定される。本発明の一実施形態では、例えば、ドライバは、それが順序素子、定常入力／出力ピン、または別の論理インスタンスである場合に限り、リタイミング可能である。ドライバが順序素子である場合、順序素子を評価して、それが関連するリタイミングされるレジスタと等価であるか、または（例えば、上述したように制御信号を除去することによって）等価になるように再構成できるかどうかが決定される。ドライバが論理インスタンスである場合、評価を実行して、論理インスタンスのドライバがリタイミング可能であるかどうかを決定することができる。ドライバがリタイミング可能でない場合、方法３００は、手順ブロック３１２で、現在のカットが無効であることを通知する。手順ブロック３１０で、バックワード・トレースの間に特定された他の入力ピンについて、トレース手順が繰り返される。本発明の例示的な一実施形態では、例えば、方法３００は、各バックワードサーチで特定された新しい入力ピン毎に反復して実行される。その結果、新しい入力ピンがカットに追加され、そのドライバがリタイミング目的のため評価される。手順ブロック３１０で特定された他の入力ピンは、選択されたレジスタ以外のレジスタによって駆動することができるので、リタイミングされる追加のレジスタをリタイミング可能カットに含めることができる。関連する入力ピンと出力ピンがすべて考察された後、カットのピンが返される。これらのピンは、図１４の手順ブロック２５４におけるフォワード・リタイミング可能カットを構成する。
【００５９】
図１６および図１７には、フォワード・リタイミングの一例が示されている。図示の例は、図１２、図１４、および図１５に関して上述した例示的方法を利用する。この例では、レジスタＲａからＬＵＴ１およびＬＵＴ３を経由してレジスタＲｅに至る信号パス沿いで、レジスタＲａが最悪のスラック値を有することが、タイミング解析（図１２の手順ブロック２０２）によって示され、そのためレジスタＲａがリタイミングされるために選択される（図１２の手順ブロック２０６）と仮定する。また、この例では、方法２５０は、フェイリングパス沿いの各入力ピンについて順番に実行されると仮定する。この例示的な方法によれば、入力ピンｉ１が、フォワード・リタイミングのために最初に選択されるピンである（図１４の手順ブロック２５２）。入力ピンｉ１から始めるので、フォワード・トレースは、入力ピンｉ１に関連する論理インスタンスの出力ピンから実行される（図１５の手順ブロック３０２）。したがって、フォワード・トレースは、関連するＬＵＴ１の出力ピンｏ１から実行される。フォワード・トレースによって、ｏ１で始まるパス部分の終点として、入力ピンｉ５が特定され、カットに追加される（図１５の手順ブロック３０４）。バックワード・トレースが、入力ピンｉ１とＬＵＴ１の他の入力ピンから実行される（図１５の手順ブロック３０６）。入力ピンｉ１からバックワード・トレースを行うことによって、パスのドライバとしてレジスタＲａが特定され、レジスタＲａからの他のファンアウトがないことが分かる。入力ピンｉ２からバックワード・トレースを行うことによって、レジスタＲｂとレジスタＲｂからのファンアウト中に入力ピンｉ３が特定される。レジスタＲｂが評価されて、それがリタイミング可能ドライバであるかどうかが決定される（図１５の手順ブロック３０８）。この場合、レジスタＲｂはレジスタＲａと等価であり、したがって、リタイミング可能である。フォワード・リタイミング手順３００が、新たに特定された入力ピンｉ３から繰り返される（図１５の手順ブロック３１０）。ＬＵＴ２の唯一の出力ピンである出力ピンｏ２からのフォワード・トレースによって、入力ピンｉ６とｉ７が特定される（図１５の手順ブロック３０２）。入力ピンｉ６とｉ７が、カットに追加される（図１５の手順ブロック３０４）。バックワード・トレースが、入力ピンｉ３とｉ４から実行される（図１５の手順ブロック３０６）。レジスタＲｂからｉ２およびｉ３に至るパス部分はすでに考察されているので、いくつかの実施形態では、入力ピンｉ３からのバックワード・トレースは実行されない。入力ピンｉ４からのバックワード・トレースによって、レジスタＲｃが特定され、リタイミング目的のため評価される（図１５の手順ブロック３０８）。この例では、レジスタＲｃはレジスタＲａと等価であり、したがって、リタイミング可能である。他に考察する入力ピンがないので、カットのピンが有効リタイミング可能カットとして返される。具体的には、入力ピンｉ５、ｉ６、およびｉ７を含むカットが返される（図１５の手順ブロック３１２）。このカットは、図１６にカット「ＡＡ」として示されている。見つかったカットを用いてタイミング評価が実行され、カットの遅延および／またはスラックが決定される（図１５の手順ブロック３１２）。この例では、計算されたカットのスラックが、フェイリングパスについての元のスラック時間に対して改善（例えば、−２から１ｎｓ）を示すと仮定する。カットは第１のカットとしてセーブされ（図１４の手順ブロック２５８、２６０）、次の入力ピンについて考察が行われる（図１４の手順ブロック２６４、２６６）。
【００６０】
図１７には、同じ例示的な方法を用いて次のフォワード・リタイミング可能カットを見つける手順が示されている。この例示的な方法によれば、次の入力ピンは、フェイリングパス沿いの次の入力ピン、すなわち、入力ピンｉ５である。入力ピンｉ５から始めるので、フォワード・トレースは、ＬＵＴ３の出力ピンｏ３から実行される（図１５の手順ブロック３０２）。フォワードサーチによって、レジスタＲｅの入力ピンＤ１とＬＵＴ５の入力ピンｉ９が特定され、それらがカットに追加される（図１５の手順ブロック３０４）。バックワード・トレースが、入力ピンｉ５とｉ６から実行される（図１５の手順ブロック３０６）。入力ピンｉ５からのバックワード・トレースによって、ＬＵＴ１から出力ピンｏ１が特定され、出力ピンｏ１からのファンアウトに他の入力ピンはないことが分かる。いくつかの実施形態では、出力ピンｏ１が、リタイミング可能レジスタであるレジスタＲａ、Ｒｂから駆動されるかどうかを決定するため、評価が実行される（図１５の手順ブロック３０８）。入力ピンｉ６からのバックワード・トレースによって、ドライバとしての出力ピンｏ２と、出力ピンｏ２からのファンアウト内の別の入力ピンとしての入力ピンｉ７が特定される。出力ピンｏ２が、リタイミング可能レジスタであるレジスタＲｂ、Ｒｃから駆動されるかどうかを決定するため、評価が実行されるが（図１５の手順ブロック３０８）、この情報は、上述したカット「ＡＡ」を見つける手順でセーブされている場合もある。フォワード・トレースおよびバックワード・トレース手順が、入力ピンｉ６からのバックワード・トレースによって特定された他のピンである入力ピンｉ７から実行される（図１５の手順ブロック３１０）。ＬＵＴ４の出力ピンｏ４からのフォワード・トレースによって、入力ピンｉ１０とレジスタＲｇの入力ピンＤ３が特定される（図１５の手順ブロック３０２）。入力ピンｉ１０とレジスタＲｇの入力ピンＤ３が、カットに追加される（図１５の手順ブロック３０４）。ＬＵＴ４の入力ピンｉ８からのバックワード・トレースによって、ドライバとしてのレジスタＲｄが特定され（図１５の手順ブロック３０６）、それがリタイミング可能レジスタであることが確認される（図１５の手順ブロック３０８）。他に考察する入力ピンがないので、方法３００は終了し、レジスタＲｅの入力ピンＤ１、レジスタＲｇの入力ピンＤ３、および入力ピンｉ９、ｉ１０を含むリタイミング可能カットが返される（図１５の手順ブロック３１２）。このリタイミング可能カットは、図１７にカット「ＢＢ」として示されている。見つかったカットを用いてタイミング評価が実行され、カットの遅延および／またはスラックが決定される（図１４の手順ブロック２５６）。この例では、計算されたカットのスラックが、セーブされた第１のカットの時間に対して改善（例えば、１から２ｎｓ）を示すと仮定する。したがって、カット「ＢＢ」がセーブされる（図１４の手順ブロック２６２、２６３）。フェイリングパス沿いには他に考察する入力ピンがないので、カット「ＢＢ」が最善のフォワード・リタイミング可能カットとして返される（図１４の手順ブロック２４０）。
【００６１】
図１８には、バックワード・リタイミング可能カットを見つけるための例示的な方法３５０が示されている。方法３５０は、バックワード・リタイミング可能カットに適用するために変更することができる図１４に示す方法など、リタイミング可能カットを見つけ、評価するより一般的な方法の一環として実施することができる。フォワード・リタイミング可能カットを見つけるのと類似して、方法３５０は、回路機能を維持するためにリタイミングする必要がある他のインスタンスを特定し、評価するために、論理コーンのパスを前方および後方にトレースする。この手順は、見つかったカットが有効であることを保証するのにも役立つ。例えば、バックワード・リタイミング可能カットの場合、フォワード・トレースを行う手順は、論理コーンの第２（または右側）の区画へのファンインがないこと、またリタイミング可能カットの第２（または右側）の区画が順序素子（例えば、ＦＰＧＡのレジスタ）を駆動することを確認するのに有用である。
【００６２】
本発明の一実施形態の例示的な手順３５０は、フェイリングパス沿いの論理インスタンスの入力ピン（例えば、フェイリングパス沿いの最後の論理インスタンスの入力ピン）から始まる。図１８の手順ブロック３５２で、選択された入力ピンと論理インスタンスの関連する入力ピンがカットに追加される。関連する入力ピンは、例えば、ネットリストまたは回路デザインを保存する他の設計データベースから特定される。手順ブロック３５４で、フォワード・トレースが、選択された入力ピンに関連する論理インスタンスの出力から実行される。本発明の一実施形態では、例えば、フォワード・トレースは、論理インスタンスのすべての出力ピンから実行される。フォワード・トレースを行う手順によって、特定の出力によって駆動される入力ピン（すなわち、特定の出力からの信号の終点）が特定される。フォワード・トレースの間に特定された入力ピンの各々について、手順ブロック３５６で、入力ピンがリタイミング可能素子に結合されているかどうかが決定される。本発明の一実施形態では、例えば、回路素子は、それが順序素子、または別の論理インスタンスである場合に限り、リタイミング可能である。回路素子が論理インスタンスである場合、評価を実行して、論理インスタンスがリタイミング可能順序素子であるかどうかを決定することができる。出力ピンによって駆動される順序素子を評価して、それが関連するレジスタ（例えば、リタイミングされるレジスタ、または関連するリタイミングされたレジスタ）と等価であるか、または等価になるように再構成できるかどうかを決定することができる。どの順序素子もリタイミング可能でない場合、方法３５０は、手順ブロック３６０で、現在のカットが無効であることを通知する。手順ブロック３５８で、フォワード・トレースの間に特定された他の入力ピンについて、手順３５０が繰り返される。本発明の例示的な一実施形態では、例えば、方法３５０は、フォワード・トレースで特定された新しい論理インスタンス毎に反復して実行される。その結果、新しい入力ピンがカットに追加され、新しい出力ピンとそれが駆動する順序素子が評価される。反復手順の間、本発明の具体的な一実施では、入力ピンがバックワード・リタイミング可能カットに追加された論理インスタンスによって駆動される入力ピンは、カットに追加されない。関連する入力ピンと出力ピンがすべて考察された後、手順ブロック３６０で、カットのピンが返される。これらのピンは、バックワード・リタイミング可能カットを構成する。
【００６３】
図１９および図２０には、バックワード・リタイミングの一例が示されている。図１６および図１７に示した例のように、レジスタＲａからＬＵＴ１およびＬＵＴ３を経由してレジスタＲｅに至る信号パス沿いで、レジスタＲａが最悪のスラック値を有し、そのためレジスタＲａがリタイミングされるために選択される（図１２の手順ブロック２０６）と仮定する。また、この例では、方法３５０は、最後の論理インスタンスから始めて、フェイリングパス沿いの各入力ピンについて順番に実行されると仮定する。この例示的な方法によれば、入力ピンｉ５が、バックワード・リタイミングのために最初に選択されるピンである（図１８の手順ブロック３５２）。入力ピンｉ５から始めるので、入力ピンｉ５とｉ６がカットに追加される（図１８の手順ブロック３５２）。フォワード・トレースが、ＬＵＴ３の出力ピンｏ３から実行される（図１８の手順ブロック３５４）。フォワード・トレースによって、ｏ３で始まる信号の終点としての入力ピンＤ１と入力ピンｉ９が特定される。レジスタＲｅが評価されて、それがリタイミング可能素子であるかどうかが決定される（図１８の手順ブロック３５６）。この場合、レジスタＲｅはリタイミング可能であると仮定する。ＬＵＴ５も評価されて、それがリタイミング可能回路素子であるかどうかが決定される。この場合、ＬＵＴ５は、リタイミング可能であると仮定するレジスタＲｆを駆動する。手順３５０が、新たに特定された入力ピンｉ９とＬＵＴ５から繰り返される（図１８の手順ブロック３５８）。反復された手順において、入力ピンｉ１０がカットに追加される（図１８の手順ブロック３５２）。この具体的な例では、入力ピンｉ９は、入力ピンがすでにカットに含まれている論理インスタンスによって駆動される（すなわち、入力ピンｉ９はＬＵＴ３によって駆動され、ＬＵＴ３の入力ピンｉ５とｉ６はすでにカットに含まれている）ので、カットに追加されない。ＬＵＴ５の唯一の出力ピンである出力ピンｏ５からのフォワード・トレースによって、すでにリタイミング可能であると決定されているレジスタＲｆの入力ピンＤ２が特定される（図１８の手順ブロック３５４、３５６）。他に考察する論理インスタンスがないので、カットのピンが有効リタイミング可能カットとして返される。具体的には、入力ピンｉ５、ｉ６、およびｉ１０を含むカットが、有効バックワード・リタイミング可能カットとして返される（図１８の手順ブロック３６０）。このカットは、図１９にカット「ＣＣ」として示されている。見つかったカットを用いてタイミング評価が実行され、カットのスラックが決定され（図１４の手順ブロック２５６）、カットは第１のカットとしてセーブされ（図１４の手順ブロック２５８、２６０）、次の入力ピンについて考察が行われる（図１４の手順ブロック２６４、２６６）。
【００６４】
図２０には、同じ例示的な方法を用いて、次のバックワード・リタイミング可能カットを見つける手順が示されている。この例示的な方法によれば、次の入力ピンは、フェイリングパス沿いの直前の入力ピン、すなわち、入力ピンｉ１である。入力ピンｉ１とｉ２がカットに追加される（図１８の手順ブロック３５２）。フォワード・トレースが、ＬＵＴ１の出力ピンｏ１から実行される（図１８の手順ブロック３５４）。フォワードサーチによって、ＬＵＴ３の入力ピンが特定される。ＬＵＴ３がリタイミング可能順序素子を駆動するかどうかを決定するために評価が実行される。レジスタＲｅとＬＵＴ５の入力ピンｉ９が特定され、評価される。レジスタＲｅはリタイミング可能であり、ＬＵＴ５はやはりリタイミング可能なレジスタＲｆを駆動するので、方法は進められる。手順３５０は、新たに特定された入力ピンｉ５とＬＵＴ３から第１の反復を繰り返す（図１８の手順ブロック３５８）。入力ピンｉ６がカットに追加される（図１８の手順ブロック３５２）。しかし、この例では、入力ピンｉ５は、入力ピンがすでにカットに含まれている論理インスタンスによって駆動される（すなわち、入力ピンｉ５はＬＵＴ１によって駆動され、ＬＵＴ１の入力ピンｉ１とｉ２はすでにカットに含まれている）ので、カットに追加されない。ＬＵＴ３の唯一の出力ピンである出力ピンｏ３からのフォワード・トレースによって、すでにリタイミング可能であると決定されているレジスタＲｅとＬＵＴ５の入力ピンｉ９が特定される（図１８の手順ブロック３５４、３５６）。手順３５０は次に、入力ピンｉ９とＬＵＴ５から第２の反復を繰り返す（図１８の手順ブロック３５８）。入力ピンｉ１０がカットに追加されるが（図１８の手順ブロック３５２）、入力ピンｉ９は、入力ピンがすでにカットに含まれている論理インスタンスによって駆動されるので、追加されない。出力ピンｏ５からのフォワード・トレースによって、すでにリタイミング可能であると決定されているレジスタＲｆが特定される（図１８の手順ブロック３５４、３５６）。他に考察する論理インスタンスがないので、カットのピン（ｉ１、ｉ２、ｉ６、およびｉ１０）が有効リタイミング可能カットとして返される。このリタイミング可能カットは、図２０にカット「ＤＤ」として示されている。見つかったカットを用いてタイミング評価が実行され、カットの遅延および／またはスラックが決定される（図１４の手順ブロック２５６）。この例では、カットのスラックが計算され、セーブされた第１のカットの時間に対して改善（例えば、２ｎｓから１ｎｓ）を示すと仮定する。したがって、カット「ＤＤ」がセーブされる（図１４の手順ブロック２６２、２６３）。フェイリングパス沿いには他に考察する入力ピンがないので、カット「ＤＤ」が最善のバックワード・リタイミング可能カットとして返される（図１４の手順ブロック２４０）。
【００６５】
図１２、図１４、図１５に示した最善のフォワード・リタイミング可能カットを見つけるための例示的な方法の実施形態を用いて、いくつかの実験を行った。具体的には、例示的な方法の実施形態を使用して、Ｘｉｌｉｎｘ（登録商標）Ｖｉｒｔｅｘ−ＩＩ（登録商標）ＦＰＧＡに実装されたデザインをリタイミングした。表１には、８００から８０００スライス（Ｘｉｌｉｎｘ（登録商標）デバイスの基本構成ユニット）を有するＦＰＧＡデザインに関する実験結果が示されている。複数のクロックドメインを有するデザインの場合、表に示すクロックドメインは、最悪のタイミング違反を犯すクロックドメインとする。表１に示す結果はすべて、最終的な配置および配線を行った後に取得された。したがって、図示のクロック時間は、実クロックサイクル時間である。第１欄には、事例１から１０として１０のデザインが掲げてあり、さらに各事例の平均も含まれている。「スライス」と記された第２欄には、各デザイン毎のスライスの数が示してある。「合成」と記された第３欄には、リタイミングを行わない論理合成の後に取得されたクロックサイクル時間が示してある。「リタイミング１」と記された第４欄には、図１２、図１４、図１５に示し、上で概略を説明した方法の第１版を用いて取得したクロックサイクル時間が示してある。具体的には、第１版の方法は、物理遅延モデル、配置制約（例えば、配置中にレジスタの密集を防止するのに使用される基準）、制御信号分離技法を使用し、スラックが最もよく改善されるように最善のフォワード・リタイミング可能カットを探索した。第４欄の括弧内の値は、リタイミングを行ったことで追加されたレジスタと除去されたレジスタの数をそれぞれ表す。「改善１」と記された第５欄には、論理合成後に得られた回路に対する、例示的な方法を用いてリタイミングした回路の改善率が示してある。「リタイミング２」と記された第６欄には、リタイミングアルゴリズムの第２版の結果が示してあり、括弧内にはリタイミングプログラムの実行に要した分数が含まれている。「改善２」と記された第７欄には、論理合成後に得られた回路に対する、例示的な方法の第２版を用いてリタイミングした回路の改善率が示してある。第６欄および第７欄に示された第２版のリタイミングアルゴリズム「リタイミング２」では、より正確な物理遅延モデルの代りにワイヤロード遅延モデルを使用した。さらに、第２版では、どのような形式の配置制約も使用しなかった。物理情報の欠落のため精度の低いタイミング評価の下でリタイミングが行われ、タイミング精度が低下したことで、全体的な結果は第１版の方法ほど良好なものではない。結果的に、改善率は平均で８．２％である。しかし、いくつかのケースでは、論理合成によって達成されたタイミングよりも悪いタイミングが得られた。「リタイミング３」と記された第８欄には、リタイミングアルゴリズムの第３版のタイミング結果が示してある。追加されたレジスタと除去されたレジスタの数が、括弧内にそれぞれ示してある。「改善３」と記された第９欄には、論理合成後に得られた回路に対する、例示的な方法の第３版を用いてリタイミングした回路の改善率が示してある。リタイミング方法の第３版では、第１版で使用した構造上の制約を緩和するのに使用される制御信号分離手続きが省略された。第９欄に示すように、第３版を用いた際の改善率は７．１４％である。さらに、第８欄に示すように、除去されたレジスタと追加されたレジスタの数は、第１版と比べて著しく少ない。最後に、「改善４」と記された第１０欄には、リタイミングアルゴリズムの第４版の結果が示してある。リタイミング手順の実行に要した分数が括弧内に示してある。「改善４」と記された第１１欄には、論理合成後に得られた回路に対する、例示的な方法の第４版を用いてリタイミングした回路の改善率が示してある。第４版のアルゴリズムでは、物理配置の考察、制御信号の分離、および最善カットの探索を除外する変更を第１版に施した。これらの変更の結果、第１１欄に示すように、平均改善率は１．９％となり、アルゴリズムによる全体的タイミング利得はほとんど失われ、第１０欄に示すように、むしろ悪化したケースも多く見られる。第４版の実行時間を第６欄に示す第２版と比較することから分かるように、カット探索手順を含むカットベース・リタイミングは、リタイミングアルゴリズムの実行時間を大幅に短縮することができる。実際、第２版の方法では、第４版に比べて平均実行時間が６８．３％改善している。
【００６６】
【表１】
2007524891.tif 000006
上述した技法の態様はどれも、分散コンピュータネットワークを用いて実行または設計することができる。図２１には、そのような例示的なネットワークの１つが示されている。サーバコンピュータ４００は、（サーバコンピュータの内部または外部に）関連する記憶装置４０２を有することができる。例えば、サーバコンピュータ４００は、（例えば、ＥＤＡソフトウェアツールの一部として）上述した実施形態のいずれかを用いて回路デザインをリタイミングできるように構成することができる。サーバコンピュータ４００は、例えば、ワイドエリアネットワーク、ローカルエリアネットワーク、クライアント／サーバネットワーク、インターネット、またはその他のネットワークを含む、全体として４０４で示されるネットワークに結合することができる。１つまたは複数の４０６、４０８で示されるようなクライアントコンピュータは、ネットワークプロトコルを用いてネットワーク４０４に結合することができる。
【００６７】
図２２には、設計情報（例えば、ネットリスト）を含むデータベースが本明細書に開示した実施形態のいずれかに従ってリタイミングされた回路の設計情報を含むように、データベースを図２１に示すサーバコンピュータ４００などのリモートサーバコンピュータを使用して更新（または変更）できることが示されている。手順ブロック４５０で、例えば、クライアントコンピュータが、リタイミングされる回路に関する設計データを送信する。例えば、クライアントコンピュータは、ネットリストまたはその他のＥＤＡ設計データベースを送信することができる。手順ブロック４５２で、データはサーバコンピュータによって受信され、ロードされる。手順ブロック４５４で、データベースによって定義された回路が、開示の実施形態のいずれかに従ってリタイミングされる。リタイミング後のデザインを表す新しいデータベースを作成することができる。この新しい設計データは、設計データベースの更新（または変更）版として、または１つまたは複数の独立のデータベースとして保存することができる。手順ブロック４５６で、サーバコンピュータは、更新データベースまたはその他のデータベースをクライアントコンピュータに送信し、手順ブロック４５８で、クライアントコンピュータはそのデータベースを受信する。図２２に示す例が関連する設計データを含む設計データベースを更新するための唯一の方法でないことは、当業者には明らかであろう。例えば、設計データは、ネットワークに接続されておらず、サーバに単独で送付されるコンピュータ可読媒体に保存することができる。あるいは。サーバコンピュータは、設計手続きの一部だけを実行することができる。
【００６８】
いくつかの実施形態によって本発明の原理を例示し、説明してきたが、本発明の原理から逸脱することなく、それらの実施形態を構成および詳細について変更できることは明らかであろう。説明した実施形態は例示的なものに過ぎず、本発明の範囲を限定するものと解釈すべきではない。例えば、本開示は、説明した方法、ならびに開示の方法によってリタイミングされた集積回路（例えば、開示の方法のいずれかによってリタイミングされたＦＰＧＡ）を包含する。本発明は、添付の特許請求の範囲およびその均等物の範囲および主旨の中に収まるすべての実施形態を包含する。
【図面の簡単な説明】
【００６９】
【図１】順序素子および論理インスタンスを含む例示的なパイプラインを示したブロック図である。
【図２】図１の例示的なパイプラインを用いるフォワード・リタイミングの一例を示したブロック図である。
【図３】図１の例示的なパイプラインを用いるバックワード・リタイミングの一例を示したブロック図である。
【図４−Ａ】フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）の論理コーン内のリタイミング可能カットにレジスタを再配置する手順の一例を示したブロック図である。
【図４−Ｂ】フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）の論理コーン内のリタイミング可能カットにレジスタを再配置する手順の一例を示したブロック図である。
【図５】ＦＰＧＡ内の例示的な論理コーンおよび論理コーン内の４つの例示的なカットのブロック図である。
【図６】例示的なフォワード・リタイミング可能カットにリタイミングされたレジスタを有する図５の論理コーンのブロック図である。
【図７】例示的なバックワード・リタイミング可能カットにリタイミングされたレジスタを有する図５の論理コーンのブロック図である。
【図８】ＦＰＧＡ内の例示的な構成上の制約を示したブロック図である。
【図９−Ａ】リタイミング中に使用できる制御信号を分離する第１の例示的な手順を示したブロック図である。
【図９−Ｂ】リタイミング中に使用できる制御信号を分離する第１の例示的な手順を示したブロック図である。
【図９−Ｃ】リタイミング中に使用できる制御信号を分離する第１の例示的な手順を示したブロック図である。
【図１０−Ａ】リタイミング中に使用できる制御信号を分離する第２の例示的な手順を示したブロック図である。
【図１０−Ｂ】リタイミング中に使用できる制御信号を分離する第２の例示的な手順を示したブロック図である。
【図１０−Ｃ】は、リタイミング中に使用できる制御信号を分離する第２の例示的な手順を示したブロック図である。
【図１１−Ａ】リタイミング中に使用できる制御信号を分離する第３の例示的な手順を示したブロック図である。
【図１１−Ｂ】リタイミング中に使用できる制御信号を分離する第３の例示的な手順を示したブロック図である。
【図１１−Ｃ】リタイミング中に使用できる制御信号を分離する第３の例示的な手順を示したブロック図である。
【図１２】集積回路をリタイミングするための例示的な方法を示したフローチャートである。
【図１３】リタイミングされた３つのレジスタのリタイミング後の初期状態を見つける例示的な手順を示したブロック図である。
【図１４】図１２に示した方法で使用できる最善のフォワード・リタイミング可能カットを決定する例示的な方法を示したフローチャートである。
【図１５】選択した入力ピンからのフォワード・トレースおよびバックワード・トレースによってフォワード・リタイミング可能カットを見つける例示的な手順を示したフローチャートである。
【図１６】図１５に示した例示的な方法に従ってＦＰＧＡの論理コーン内の第１のフォワード・リタイミング可能カットを見つける手順を示したブロック図である。
【図１７】図１５に示した例示的な方法に従ってＦＰＧＡの論理コーン内の第２のフォワード・リタイミング可能カットを見つける手順を示したブロック図である。
【図１８】選択した入力ピンからのフォワード・トレースおよびバックワード・トレースによってバックワード・リタイミング可能カットを見つける例示的な手順を示したフローチャートである。
【図１９】図１８に示した例示的な方法に従ってＦＰＧＡの論理コーン内の第１のバックワード・リタイミング可能カットを見つける手順を示したブロック図である。
【図２０】図１８に示した例示的な方法に従ってＦＰＧＡの論理コーン内の第２のバックワード・リタイミング可能カットを見つける手順を示したブロック図である。
【図２１】開示のリタイミング方法を実行する際に使用することができるクライアント／サーバネットワークのシステム図である。
【図２２】例えば、図２１のネットワークを使用するデータベース作成を示したフローチャートである。
【図１】
2007524891.tif 000007
【図２】
2007524891.tif 000008
【図３】
2007524891.tif 000009
2007524891.tif 000010
【図５】
2007524891.tif 000011
【図６】
2007524891.tif 000012
【図７】
2007524891.tif 000013
【図８】
2007524891.tif 000014
2007524891.tif 000015
2007524891.tif 000016
2007524891.tif 000017
【図１２】
2007524891.tif 000018
【図１３】
2007524891.tif 000019
【図１４】
2007524891.tif 000020
【図１５】
2007524891.tif 000021
【図１６】
2007524891.tif 000022
【図１７】
2007524891.tif 000023
【図１８】
2007524891.tif 000024
【図１９】
2007524891.tif 000025
【図２０】
2007524891.tif 000026
【図２１】
2007524891.tif 000027
【図２２】
2007524891.tif 000028