(57)【特許請求の範囲】
【請求項１】
第１コンビネーションロジックモジュールを含んでいる集積回路の設計のタイミング特性を改良するための、コンピュータにより実行される方法であって、
前記第１コンビネーションロジックモジュールは、複数のモジュール入力と、モジュール出力とを有しており、
前記モジュール入力は、各モジュール入力信号を受信するように構成されており、
前記モジュール出力は、定常状態における前記モジュール入力のコンビネーションロジック機能の結果信号を、供給するとともに、
求められているタイミング進行において、前記モジュール入力の１番「最後」の信号を、決定し、
前記第１コンビネーションロジックモジュールを、第１コンビネーションロジックサブモジュールと第２コンビネーションロジックサブモジュールと２入力マルチプレクサとを有する第２コンビネーションロジックモジュールに変換し、
前記マルチプレクサは、２つのマルチプレクサ信号入力と、マルチプレクサ出力と、制御入力とを有しており、
前記制御入力は、前記１番最後の信号を受信するために接続されており、
前記サブモジュールのそれぞれは、前記１番最後の信号以外の前記モジュール入力信号のそれぞれを受信するために接続された１又は複数の入力のセットを、有しており、
前記サブモジュールのそれぞれは、前記マルチプレクサ信号入力のそれぞれに接続される出力を有しており、
前記サブモジュールのそれぞれは、１番最後の信号の値に基づく決定に従って選択された場合に、その出力が定常状態における前記結果信号を供給するように、設計されており、
前記第２コンビネーションロジックモジュールのタイミング特性が満たされているかどうかを判断し、満たされていない場合には、前記１番最後の信号のタイミングが、少なくとも部分的にでも、失敗となっているかどうかを判断するとともに、
前記第２コンビネーションロジックモジュールのタイミング特性が満たされておらず、それが前記１番最後の信号のタイミングを原因としていない場合には、
求められているタイミング進行において、前記モジュール入力の最後から２番目の信号を、決定して、前記第２コンビネーションロジックモジュールを第３モジュールに変換し、前記第３モジュールは４つのコンビネーションロジックサブモジュールを有しており、前記４つのコンビネーションロジックサブモジュールのそれぞれは、前記１番最後の信号と前記最後から２番目の信号以外の前記入力信号を受信するように構成された入力を有しており、前記サブモジュールはそれぞれの出力を有しており、前記第３モジュールは、前記４つのコンビネーションロジックサブモジュールの前記出力にそれぞれ接続された４つの信号入力のある４入力１ステージマルチプレクサを有しており、前記４入力１ステージマルチプレクサは前記１番最後の信号と前記最後から２番目の信号にそれぞれ接続された制御入力を有しおり、前記４入力１ステージマルチプレクサはマルチプレクサ出力を有しており、前記４つのサブモジュールはそれぞれ、前記１番最後の信号及び前記最後から２番目の信号の値に基づく決定に従って、前記マルチプレクサ出力に接続されたとき、それぞれの出力が定常状態における前記結果信号を出力するように、設計されているとともに、
少なくとも部分的にでも前記１番最後の信号を原因として、前記第３モジュールのタイミング特性が満たされていないかどうかを判断し、
少なくとも部分的にでも前記１番最後の信号を原因として、前記第３モジュールのタイミング特性が満たされない場合には、前記４入力１ステージマルチプレクサを、前記最後から２番目の信号により制御される第１ステージと前記１番最後の信号により制御される第２ステージとを有する２ステージマルチプレクサに変換する、
ことを特徴とする方法。
【請求項２】
前記２ステージマルチプレクサを有する前記第３モジュールのタイミング特性が満たされているかどうかを判断し、満たされていない場合には、その失敗が前記最後から２番目の信号によるものであるかどうかを判断する、ステップをさらに備える請求項１に記載の方法。
【請求項３】
Ｎ＞２である、Ｎ回の繰り返しを備えており、前記Ｎ回の繰り返しは、
Ｎ＞Ｐ−Ｔの場合に終結し、Ｐは前記第１モジュールの入力の数であり、Ｔは０≦Ｔ＜Ｐである所定の繰り返ししきい値である、ステップと、
最後から第Ｎ番目の信号を決定する、ステップと、
Ｍ＜Ｎステージの第Ｎマルチプレクサを有する第Ｎモジュールを、Ｍステージの第（Ｎ＋１）マルチプレクサを有する第（Ｎ＋１）モジュールに変換し、前記最後からＮ番目の信号を、制御信号として、前記第（Ｎ＋１）マルチプレクサの前記第１ステージに供給する、ステップと、
前記第（Ｎ＋１）モジュールのタイミング特性が満たされた場合、又は、前記第（Ｎ＋１）モジュールのタイミング特性が、前記最後からＮ番目の信号の遅延に部分的にでもより、満たされなかった場合に、終結する、ステップと、
前記第（Ｎ＋１）モジュールのタイミング特性が満たされなかったが、それが前記第（Ｎ＋１）マルチプレクサの入力が原因でない場合に、（Ｎ＋１）回目の繰り返しを開始する、ステップと、
前記第（Ｎ＋１）モジュールのタイミング特性が、部分的にでも、前記最後からＮ番目の信号以外の最後の信号のパフォーマンスにより、満たされなかった場合には、前記最後からＮ番目の信号の単独で制御される新たな第１ステージを加えることにより、前記第（Ｎ＋１）マルチプレクサを再設計する、ステップと、
再設計したマルチプレクサを有する前記第（Ｎ＋１）モジュールのタイミング特性が満たされた場合、又は、前記最後からＮ番目の信号により満たされなかった場合に、終結する、ステップと、
前記再設計したマルチプレクサを有する前記第（Ｎ＋１）モジュールのタイミング特性が、満たされなかったが、それがその時点又は前回の遅れた信号によらない場合に、（Ｎ＋１）回目の繰り返しを開始する、ステップと、
を備える請求項２に記載の方法。
【請求項４】
Ｔ≧Ｐ／２である、請求項３に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータに関し、特に、集積回路設計（integrated-circuit design）に関する。本発明の主たる目的は、コンビネーションロジックモジュール（組合せ論理モジュール）を含む集積回路設計のタイミング特性を改良するための方法を提供することである。
【０００２】
【従来の技術】
現代の進歩の多くは、集積回路製造技術の向上により作られるようになったコンピュータの急増に関係している。これらの向上は、集積回路に、絶え間ない回路素子の密度の増加を提供してきており、その結果、高速化が図られ、集積回路あたりの機能性が向上してきている。
【０００３】
ほとんどの集積回路は、識別可能な複数の機能ブロックを備えている。多くのそのような機能ブロックは、コンビネーションロジックを実現しており、換言すれば、ブロックはその時点の値を有する出力を備えており、この値は、定常状態（steady-state condition）における、ブロックへの複数の入力のその時点における値の所定の機能である。「定常状態」とは、入力の将来的な変化に応答する場合を除いて、出力が変化しないであろうとする十分な長さの一定の値を入力が保持することを、意味している（非コンビネーションロジックブロックの１つの例はカウンタである。なぜなら、その時点の出力が、その時点及びそれ以前の入力値に依存しているからである）。
【０００４】
一般に、入力信号における変化の影響が出力信号に現れる時間は、入力毎にばらつく。このばらつき（variance）には、３つの基本的な原因がある。ばらつきの第１の原因は、入力における信号変化の到達時刻が異なっていることである。すべての入力の変化が同じクロックサイクル内で起こる同期式であっても、その変化はそのクロックサイクル内の異なるフェーズで起こることがある。
【０００５】
ばらつきの第２の原因は、「ファンアウト」である。大きなファンアウト信号は、素早く多くのデバイスを駆動するが、少ないデバイスを駆動する小さいファンアウト信号よりも、ゆっくり変化する傾向にある。したがって、２つの変化が同時に始まった場合でも、より多くのデバイスを駆動する方が、その変化の完了までにより長い時間を要する。このため、遅い変化の結果は、出力の遅れをもたらす。
【０００６】
ばらつきの第３の原因は、それぞれの入力とその出力との間におけるレイテンシ（latency）が異なることである。例えば、それぞれの信号は、異なる数のゲートを通過しなければならないであろうし、各ゲートはレイテンシに寄与する遅延を生じさせる。
【０００７】
ばらつきは、クロックサイクルの長さのより低い境界に位置しているので、重要な関心事である。最もゆっくり反映する信号の変化は、次のサイクルの最も素早く反映する信号の変化が出力に反映する前に、出力に反映されなければならない。したがって、ブロック入力の連続する変化は、入力がその出力に反映される時間のばらつきよりも多く、時間的に離れていなければならない。したがって、クロック速度は、相応に制限されなければならず、回路のパフォーマンスを全体的に制限する。
【０００８】
それゆえ、ばらつきを減らすことで、パフォーマンスを改善することができる。出力タイミングの影響を互いに補うように、遅く到達する信号（ＬＡＳ：late-arriving signals）に関係する入力も、短いレイテンシになるようにして、ブロックを設計することが、ときには可能である。この場合、各種入力の変更についての出力への影響は、時間的により近くなり、高速化を促進し、信頼できる読み出しを実現する。
【０００９】
設計サイクルを短くするため、複雑な集積回路は、機能的なライブラリのモジュールから選択したモジュールを組み合わせることにより、一般的に設計されている。よって、コンビネーションロジック機能は、トランジスタレベルからブロックを設計するのではなく、適当なモジュールを単に選択することにより、実現することができる。ライブラリ内のモジュールは、様々な状況に適用されるので、入力信号の到達時間についての差異の先進的な情報なしに、一般に設計されている。したがって、傾向としては、レイテンシが入力にまたがって比較的不均一なモジュールが設計されている。
【００１０】
一旦、モジュールが実際の集積回路の設計に組み入れられると、種々の入力毎の変化の出力の結果が、意に満たない、又は、望まない程度であると気づくかもしれない。モジュールライブラリ内に同等の機能を有するより適切なモジュールを見つけることが、時々ある可能性がある。一方、設計のために特別な変更をする必要があるかもしれないし、要求を満たすために、又は、設計を最適化するために、機能ブロックを取り消して、再設計を行う必要があるかもしれない。
【００１１】
【発明が解決しようとする課題】
モジュールの変更のある種のタイプは、非常に特殊な設計条件により、教示されていた。例えば、いくつかのモジュールライブラリは、あるタイミング条件に適合するようにモジュールを変形するための特別な指令を、含んでいる。例えば、HDL Synthesis: Synthesis Application Note, Synopsys, Inc.,の１９９６年８月、チャプター２の第１１ページ〜第２７ページ（HDL Synthesis: Synthesis Application Note, Synopsys, Inc., August, 1996, Chapter 2, pp. 11-27）を参照されたい。しかし、その変形の範囲は、極めて狭い。
【００１２】
必要とされていることは、個別の入力への個々の信号到達時刻に適合するように、コンビネーションロジックモジュールを再設計するためのコンピュータにより実現される方法であり、また、組み入れた集積回路のタイミング特性を改善する方法である。そのような方法は、一方で、モジュール化された集積回路の設計競争を改善し、他方で、高いパフォーマンスの集積回路に到達するのに要する労力を、削減させる。
【００１３】
【課題を解決するための手段】
本発明は、コンビネーションロジックモジュールを含む集積回路の設計のタイミング特性を、潜在的に改良するためのコンピュータにより実現される方法を、提供する。最後の信号、例えばオリジナルのコンビネーションロジックモジュールの出力で、最も遅く反映された信号が、特定される。オリジナルのモジュールは、２つのロジックサブモジュールと出力マルチプレクサとを有する第２モジュールに変換される。１つのサブモジュールは、最後の信号がハイの場合におけるオリジナルモジュールと同様の結果を供給し、もう１つは、最後の信号がローの場合におけるオリジナルモジュールと同様の結果を供給する。最後の信号は、サブモジュールには入力されないが、変更されたサブモジュールがオリジナルのモジュールと同様のロジック機能を実現するようにマルチプレクサに制御信号として供給される。
【００１４】
一般に、最後の信号のタイミングは、オリジナルのモジュールにおけるロジック入力としてのその位置から、第２モジュールにおける出力マルチプレクサ制御信号としてのその位置までの、移動により進む。最後の信号のタイミングが依然間に合っていない場合には、タイミング規格に合致しないように思われる。しかし、最後の信号のタイミングが間に合っている場合には、タイミング的に問題のある他の信号を、繰り返し手法により、問題を解決することができる。
【００１５】
コンビネーションロジックサブモジュールは、最後の入力信号をそれまで受信していた入力に、一定の信号を供給することにより、オリジナルのモジュールから、容易に得られる。１つのサブモジュールにおいては、最後の入力にそれまで関係したすべての入力は、ハイに維持され、他のサブモジュールにおいては、対応する入力がローに維持される。多くの場合、サブモジュール設計におけるさらなる改良が、より洗練された設計アルゴリズム、及び／又は、オペレータを介入させる利点により、得ることができる。
【００１６】
最後の入力はサブモジュール内のファクタでないので、それらの遅延は、オリジナルのモジュールの遅延よりも、少なくすることができる。しかし、マルチプレクサによる追加の遅延は、モジュールを横切るいくつかの遅延を、増加させるかもしれない。このため、規格に合致したかどうか、又は、改善が実際に達成されたかどうかを判断するために、再設計したモジュールをテストすることが、一般的に望ましい。
【００１７】
本発明は、変更されたモジュールの二股テスト（two-pronged testing）を、提供する。最初の争点は、変更したモジュールが、所定のタイミング規格に合致するかどうかである。もしそうであれば、方法は、変更されたモジュールを実現するために、提供する。択一的に、方法は、タイミングのさらなる改良が可能であるかどうかを判断するために、繰り返すこともできる。
【００１８】
規格に合致しなかった場合、第２の争点が現れ、それは、その失敗が最後の信号のタイミングによるものであるのか、別の信号によるものであるか、である。それが最後の信号によるものである場合、方法のさらなる繰り返しは、改良をもたらすように思われないため、方法は終結することができる。失敗が最後の入力によるものでない場合、さらなる改良は方法の追加の繰り返しにより、達成されるかもしれない。
【００１９】
方法の第Ｎ回目の繰り返しは、最後からＮ番目の信号を決定することを、含んでいる。最後からＮ番目の信号は、方法のそれぞれのＮ回目の繰り返しで、望ましくは決定される。最初の繰り返しの決定においては、最後からＮ番目の信号は必要とされない。
【００２０】
１回目よりも後の方法のすべての繰り返しにおいて、出力マルチプレクサが既に存在する。Ｎ＞１とすると、最後からＮ番目の信号は、それまでの最後の信号とともに、マルチプレクサ制御になり、コンビネーションロジックサブモジュールの数が倍になる。（いくつかのケースでは、いくつかのサブモジュールが、悪化していることが判明し、変更されたモジュールで現す必要がなくなる）。
【００２１】
２回目及びそれに続く繰り返しにおいて、Ｎ番目の最後の信号に、新たなマルチプレクサステージを制御させたり、又は、少なくとも部分的に、最後から（Ｎ−１）番目の信号によりそれまで制御されているステージの制御を分担させたりする、選択がある。好ましい実現化においては、ともに試されてテストされ、それらがともにパスする場合は、より良い１つが実現される。
【００２２】
別の好ましい実現化においては、最後からＮ番目の信号が、予め存在しているマルチプレクサの最初のステージに、加えられる。前回の最後の信号の遅延により、このモジュールが失敗している場合には、ファーストステージの追加の複雑さは、最初のステージを制御している前回の最後の信号を、規格を下回るまで低下させるかもしれないと思われる。したがって、新たなステージは、最後からＮ番目の信号により制御されるべきマルチプレクサに、追加される。これは、前回の最後の信号を、そのタイミングが予め満たされると分かっている状態に、戻す。一方、その時点での遅れた信号は、別のマルチプレクサのステージを通過する。したがって、新しいステージが追加される前に満たされていた場合でも、その時点の最後の信号は失敗するかもしれない。しかし、失敗した場合、方法は停止する。なぜなら、その時点の最後の信号のあるこの後のステージの制御は、満足する結果が得られないであろうことが、既に判断できるからである。
【００２３】
方法が最終的な結論を得た場合、結果は、アドレスラインとしてのモジュール入力と、ロジックオペレーションの予め計算された結果としてのエントリーとを有する、ルックアップテーブルである。実際には、方法は、この結果の前に、うまく終結するであろう。したがって、本発明は、繰り返ししきい値Ｔを、提供する。繰り返ししきい値Ｔは、繰り返しが完了した後に、サブモジュール入力（マルチプレクサ入力でない）として残るであろうモジュール入力の数に、対応している。Ｔは０≦Ｔ＜Ｐのように選択でき、Ｐはモジュール入力の数である。繰り返しの数ＮがＰ−Ｔよりも大きい場合に、本方法は、繰り返しの停止を提供する。
【００２４】
本発明は、遅延を判定する異なる方法を提供する。最も重量なパラメータは、通常、ロジック入力信号の変化がロジック出力に適切に反映される相対的な時間である。一般に、標準的なロジックモジュールにとって最も重要なファクターは、集積回路に組み込まれている上流側のコンポーネントからの入力の到達時刻である。しかし、入力のファンアウト及びモジュールを横切るためのレイテンシは、遅延の定義の中に含ませてしまうこともできる。
【００２５】
本発明の方法の主たる利点は、一般的なコンビネーションロジックモジュールへの適用可能性である。これは、狭い範囲のモジュールタイプにのみ適用される従来の方法と、対照的である。本発明の２番目の主たる利点は、それが直接的であることである。本発明は、判断を含まないモジュールの変更の少なくとも１つの手法を、提供する。一方、方法は、より洗練されたコンピュータ設計原理、又は、人間の案出を用いた、さらなる改良を提供する。なぜなら、方法は直接的であり、それは完全に自動化されており、もし望むなら、効率的に設計を最適化する。これら及び他の特徴、並びに、本発明の利点は、以下の図面を参照した以下の説明により、明らかであろう。
【００２６】
【発明の実施の形態】
本発明の方法Ｍ１は、図１及び図２にフローチャート化されている。最初の繰り返しは、図１にフローチャート化されている。最初の予備ステップＳ０１は、図３に示すように、それぞれ信号Ａ、Ｂ、Ｃ及びＤを受信する４つのモジュール入力と、結果信号Ｚを送信する１つのモジュール出力とを有する、コンビネーションロジックモジュール１０の設計を含んでいる。モジュール１０は、定常状態（steady-state condition）のときに、式Ｚ＝Ｆ（Ａ、Ｂ、Ｃ、Ｄ）のロジック機能を実現する。２番目の予備ステップＳ０２は、タイミング規格が合致しているかどうかを判断するために、モジュール１０のテストを行うことを含んでいる。タイミング規格が合致した場合においては、予備ステップＳ０３は、成功したオリジナルの装置を含んでおり、厳密な意味での方法Ｍ１を実行する必要はない。
【００２７】
一方、予備テストステップＳ０２の結果が否定的である場合（又は、さらなる最適化が望まれる場合）、方法Ｍ１の最初の繰り返しが、最後の入力信号を求めるステップＳ１１から、始まる。この実施形態においては、最後の信号は、最後に到着した信号である。もし、１よりも多い最後の到着信号がある場合には、より大きいファンアウトを持つ１つを、最後の信号とする。２又はそれ以上の信号が最後に到着し、等しいファンアウトを持つ場合には、モジュール１０を通るにあたり、より大きいレイテンシを持つ１つを、最後の信号とする。２つの入力があらゆる点で等しい場合には、１つを任意に最後の信号として選択する。ここのケースでは、入力「Ａ」が最後の信号であると、決定されたとする。
【００２８】
図４に示すように、ステップＳ１２は、オリジナルの設計モジュール１０を、変更した設計モジュール２０に、変換する。変更されたモジュール２０は、第１のコンビネーションロジックサブモジュール２１と、第２のコンビネーションロジックサブモジュール２２と、２：１のマルチプレクサ２５とを、備えている。マルチプレクサ２５は、結果信号Ｚを供給する出力と、サブモジュール２１及び２２のそれぞれの出力に接続する２つの信号入力と、信号Ａを受信する制御入力とを、有している。
【００２９】
サブモジュール２１は、入力Ａがローである場合における、モジュール１０のコンビネーション機能を実現する。サブモジュール２１は、モジュール１０において、信号Ａを受信するすべての入力を接地することにより、モジュール１０から直接的に（オペレータの介在なしで）得ることができる。これとは相補的に、サブモジュール２２は、入力Ａがハイである場合における、モジュール１０のコンビネーション機能を実現する。サブモジュール２２は、モジュール１０において、信号Ａを受信するすべての入力をハイに固定することにより、モジュール１０から直接的に得ることができる。
【００３０】
最も直接的な変更が行われた場合、モジュール１０を通過するレイテンシを越える、サブモジュール２１又は２２を通過する信号レイテンシが、無いようにすべきである。一般に、より洗練された自動設計アルゴリズム、及び／又は、人間の介在する利点を用いることにより、より適切なサブモジュールの設計が、あるかもしれない。
【００３１】
信号Ａの値に依存して、サブモジュール２１及び２２の１つは、モジュール２０の結果信号Ｚとして、望ましい結果を、出力する。したがって、信号Ａは、マルチプレクサ２５の出力用の制御信号として、用いられる。変更されたモジュール２０における信号Ａによるレイテンシは、単に、マルチプレクサの入力から、マルチプレクサの出力までであることに、気づいてほしい。このレイテンシは、オリジナルのレイテンシよりも実質的に小さくなるであろう。問題は、レイテンシの減少が、モジュール１０の規格不足を補うことを満足しているかどうかである。
【００３２】
この充足度は、ステップＳ１３及びＳ１４における２つの部分でそれぞれテストされる。ステップＳ１３は、モジュール２０の全体的なタイミングパフォーマンスを、評価する。もし規格が合致した場合には、方法Ｍ１はステップＳ０３において、成功と結論づけられる。
【００３３】
モジュール２０がステップＳ１３のテストに失敗した場合、ステップＳ１４において、失敗が少なくとも部分的にでも最後の信号Ａの遅延によるものであるかどうかを、決定する。失敗が少なくとも部分的にでも最後の信号Ａの遅延によるものである場合には、方法Ｍ１はステップＳ１５で停止する。方法Ｍ１のさらなる繰り返しは、最後の信号Ａのタイミングを進めるようには、されていない。
【００３４】
しかし、ステップＳ１３における失敗が、信号Ａのタイミングによるものではまったくない場合には、方法Ｍ１は図２でフローチャート化されたさらなる繰り返しを、行う。以下、第２の繰り返しをまず説明するが、図２は続きの繰り返しを一般化したものである。
【００３５】
ステップＳ２０は、繰り返し数をカウントすることを含む、概念的ステップである。Ｐは、モジュール入力信号の数である。Ｎは、現在の繰り返しの数である。繰り返しの始めにおいては、Ｎ−１個のマルチプレクサ制御信号と、Ｐ−Ｎ＋１個のサブモジュール入力信号とが、存在する。サブモジュール入力信号は、次の最後の信号の候補である。一旦、次の最後の信号が選択されると、Ｎ個のマルチプレクサ制御信号と、Ｐ−Ｎ個のサブモジュール入力とになる。モジュール１０のケースでは、Ｐ−Ｎ＋１＝４−１＋１＝４個のモジュール入力と、Ｎ−１＝１−１＝０個のマルチプレクサ入力とが、存在する。１回目の繰り返しの終わりでは、つまり、２回目の繰り返しの始めでは、モジュール２０は、Ｐ−Ｎ＋１＝４−２＋１＝３個のサブモジュール入力信号と、Ｎ−１＝２−１＝１個のマルチプレクサ制御入力信号とを、有することになる。
【００３６】
ステップＳ２０は、埋め込み繰り返しストップ決定を含んでいる。方法Ｍ１は、繰り返し数Ｎが、モジュール入力Ｐの数としきい値Ｔとの差分よりも大きい場合に、ストップする。Ｔは、０からＰ−１の範囲をとり得る、その時点の終了しきい値である。実際には、Ｔは、繰り返し後に維持しなければならない、マルチプレクサ以外のモジュール入力の数の境界値よりも、低く、設定される。Ｔを０に設定することが、許容できる繰り返しの数を最大化する。説明に役立つことを目的として、方法Ｍ１ではＴを０に設定する。一般に、Ｔをより大きくすることにより、より実用的になる。例えば、好ましくは、Ｔは、Ｐ／２とＰ−１との間であろう。モジュール１０のように、４入力のモジュールの場合、Ｔは、１回の繰り返しを許容するために３に設定されるかもしれないし、又は、２回の繰り返しを許容するために２に設定されるかもしれない。ここの記述では、２回の繰り返しを許容するためにＴ＝２に設定する。しかし、一般化された記述では、Ｎ回目の繰り返しにも、提供される。
【００３７】
ステップＳ２１は最初の繰り返しのステップＳ１１に相当しており、最後から２番目の信号を決定することを含んでいる。それ以前に決定された最も最後の信号Ａは、考慮から除外される。したがって、残っている３つの信号Ｂ、Ｃ及びＤが、比較される。このケースでは、最後から２番目の信号は、Ｂである。
【００３８】
ステップＳ２２は最初の繰り返しのステップＳ１２に相当しており、図５に示すように、モジュール２０をモジュール３０に変換することを含んでいる。モジュール３０は、４つのコンビネーションロジックサブモジュール３１、３２、３３及び３４と、１つの４：１マルチプレクサ３５とを、備えている。最初の繰り返しから類推されるように、サブモジュール３１は、Ｂ＝０のサブモジュール２１から得られ、サブモジュール３２は、Ｂ＝１のサブモジュール２１から得られ、サブモジュール３３は、Ｂ＝０のサブモジュール２２から得られ、サブモジュール３４は、Ｂ＝１のサブモジュール２２から得られる。各サブモジュールは、信号Ｃ及びＤを受信する２つの入力を備えている。（一般に、すべてのサブモジュールが、マルチプレクサ制御以外のすべての入力信号を、必要としているわけではない）。各サブモジュールは、マルチプレクサ３５のそれぞれの入力に接続される１つの出力を、備えている。繰り返しになるが、変更されたモジュール３０の導出は、直接的なものであり、完全に自動化されている。また、より洗練された設計アルゴリズムと、オペレータの入力は、サブモジュールを可能な限り最適化することを探求できるようにする。
【００３９】
マルチプレクサ３５は、モジュール３０の出力が、モジュール１０及び２０の出力と、論理的に等価になるように、その出力に結果Ｚを供給する。任意の所定の定常状態において、４つのサブモジュール３１〜３４の１つは、Ｚとして要求されている値を、供給する。これはなぜなら、４つのサブモジュールは、２つの遅れた信号Ａ及びＢに対して、４つのあり得る値のコンビネーションに、相当しているからである。マルチプレクサ３５の制御入力におけるＡ及びＢの値に基づいて、適切なモジュールが選択される。
【００４０】
マルチプレクサ３５を横切る４つのマルチプレクサ入力に関するレイテンシのばらつきをほとんど無視した場合、マルチプレクサ３５は、シングルステートのマルチプレクサである。１つの可能性のある複雑な状態は、モジュール２０（図４）の２：１マルチプレクサ２５と比べて、４：１のマルチプレクサ３５の追加の複雑さが、最も遅い信号Ａのレイテンシを、増加させる可能性があることである。この増加は、ロジックのデコーディング、若しくは、ファンアウトの追加によるものである、可能性がある。いずれのケースでも、この増加は、モジュール３０のタイミングパフォーマンスの評価（ステップＳ２５）において、考慮する必要がある。
【００４１】
モジュール３０のタイミング特性は、ステップＳ２３で評価される。もし規格と合致した場合には、方法Ｍ１は、成功で終結し、モジュール３０の設計を実現することができる。もし規格と合致しない場合において、ステップＳ２４は、失敗がその時点の最後の信号Ｂの遅延に、部分的にでもよるものであるかどうかを判断することを含んでいる。もしそうであれば、方法Ｍ１は規格に合致する設計を見出すことなく、終結する。もしそうでなければ、さらなる再設計が実施される。
【００４２】
再設計の本質は、ステップＳ２５の結果に依存する。ステップＳ２５は、失敗が信号Ａの遅延に、部分的にでもよるものであるかどうかを決定する。もし失敗が信号Ａの遅延によるものでない場合には、方法Ｍ１は、３回目の繰り返しのために、ステップＳ２０に戻る。
【００４３】
もしステップＳ２５において、ステップＳ２３の失敗が少なくとも部分的に信号Ａを原因とするものであると決定した場合には、方法Ｍ１はステップＳ２６に進む。モジュール３０はモジュール４０に変換される。モジュール４０は、モジュール３０と同様のロジックサブモジュールを、備えている。モジュール３０のように、モジュール４０は、４：１の出力マルチプレクサである。しかし、モジュール３０が１ステージのマルチプレクサであるのに対して、モジュール４０の出力マルチプレクサ４５は、２つのステージを有している。したがって、４：１マルチプレクサ４５は、２つの第１ステージ２：１マルチプレクサ４６及び４７と、１つの第２ステージ２：１マルチプレクサ４８とを、備えている。
【００４４】
第１ステージマルチプレクサ４６は、サブモジュール３１及び３２の出力を受信し、第１ステージマルチプレクサ４７は、サブモジュール３３及び３４の出力を受信する。第１ステージ２：１マルチプレクサ４６及び４７の双方は、最後から２番目の信号Ｂにより、制御される。
【００４５】
第１ステージマルチプレクサ４６及び４７の出力は、第２ステージ２：１マルチプレクサ４８に対する入力である。第２ステージマルチプレクサ４８は、最も遅い信号Ａにより制御される。推測できるように、２：１マルチプレクサ２５（図４）を越える複雑さの４：１マルチプレクサ３５（図５）が原因となり、信号ＡはステップＳ２３で問題化されている。図６に示すように、モジュール４０において、信号Ａは２：１マルチプレクサ４８のみを駆動しており、このため、その予め成功するタイミングが、再確立されるであろう。
【００４６】
モジュール４０は、ステップＳ２７でテストされる。もしモジュール４０が規格に合致した場合、方法Ｍ１はステップＳ２７で終結する。そうでなければ、方法Ｍ１は、決定ステップＳ２８に進む。
【００４７】
ステップＳ２８は、最後の信号Ａ及び／又はＢの１つの遅延を、少なくとも一部が原因となって、ステップＳ２７が失敗したかどうかを判断する。それがＡであるということはほとんどあり得ないであろう。なぜなら、そのタイミングは満たされることが予め見出されている位置に、復元されているからである。ほとんどの場合、それとモジュール出力との間に挿入された追加のステージを原因とする問題となるのは、その時点の最後の信号Ｂである。いずれにしても、方法Ｍ１は、ステップＳ２６の結果、マルチプレクサ入力のタイミングを、早くすることを、提供できない。したがって、ステップＳ２７の失敗が、その前の、又は、今回の最後の信号によるものである場合には、方法Ｍ１は、合致する規格が見つからないまま終結する。
【００４８】
ステップＳ２７の失敗が、最後の信号のタイミングを原因とするものであると、ステップＳ２８が判定した場合、方法Ｍ１は、さらなる繰り返しのために、ステップＳ２０に戻る。この場合、タイミングの問題は、サブモジュール入力によるものであり、さらなる再設計により改良が達成されるかもしれない。この繰り返しにおいて、ステップＳ２０は、Ｎを２から３へ、インクリメントする。３回目の繰り返しの始めにおいては、Ｐ−Ｎ＝１である。繰り返ししきい値がＴ＝２に設定されいるので、方法Ｍ１はこの時点で終了する。これに対して、Ｔが０又は１に設定されていた場合には、さらなる繰り返しが、適合する規格の必要性に応じて、行われる。
【００４９】
一般に、Ｐ個の入力を有するオリジナルのモジュールにおいて、Ｎ回の繰り返しが、ステップＳ２０で開始され、さらに進めるために、サブモジュール入力信号の数が、繰り返ししきい値に、合致するかどうかが判断される。Ｎ＞Ｐ−Ｔであれば、方法Ｍ１は停止する。さもなければ、方法Ｍ１はステップＳ２１に進む。
【００５０】
ステップＳ２１は、（Ｎ−１）回目の繰り返しでテストされたモジュールにおいて、サブモジュールで受信された信号のうち、最後の入力を決定することを含んでいる。ステップＳ２２は、最後からＮ番目の信号を、出力マルチプレクサの最初のステージを制御する最後から（Ｎ−１）番目の信号に加えるように、それまでのモジュールを変換することを含んでいる。ステップＳ２３は、テストを行い、規格が合致した場合にはパスさせることを、含んでいる。さもなければ、方法Ｍ１はステップＳ２４に進む。
【００５１】
ステップＳ２４は、ステップＳ２３での失敗が、最後からＮ番目の信号の遅延によるものであるかどうかを判断するために、チェックを行う。もしそうであれば、方法Ｍ１は、合致する規格がないまま、終結する。さもなければ、方法Ｍ１は、失敗がその前の回の最後の信号によるものであるかどうかを判断するために、ステップＳ２５に進む。失敗がその前の回の最後の信号によるものである場合に、それは出力マルチプレクサの最初のステージを制御する信号であると想定することができる。なぜなら、最初のステージだけが、ステップＳ２２で変更されたからである。前回の最後の信号に要求されるすべてのタイミングが、合致している場合には、存在するサブモジュール入力信号の少なくとも１つが、向上を要求しなければならない。したがって、方法Ｍ１は、次の繰り返しのために、ステップＳ２０に戻る。
【００５２】
ステップＳ２３での失敗が、前回の最後の信号が規格外で失敗したことによるものであると、ステップＳ２５で判断された場合には、方法Ｍ１はステップＳ２６に進む。この場合、モジュール変換は、マルチプレクサの再設計に制限され、サブモジュールは変更されない。マルチプレクサは、そのマルチプレクサに追加のステージを生成することにより、変更される。この新しいステージは、最初のステージになり、最後から（Ｎ−１）番目の信号に制御されるステージは、第２ステージになる。新しい最初のステージは、最後からＮ番目の信号により単独で制御される。
【００５３】
この変換は、前回の最後の信号を、ステップＳ２２の変更前の状態に、戻す。したがって、それまでのすべての最後の信号のタイミングは、合致するであろう。もしこれが、すべての規格を満たしている結果をもたらすのであれば、ステップＳ２７で決定したように、方法Ｍ１は成功により終結する。このテストをパスしない場合には、方法Ｍ１は、ステップＳ２８に進む。
【００５４】
ステップＳ２８は、その時点の、又は、前回の最後の信号の遅延に、部分的にでもよるものであるかどうかを、決定する。一般に、失敗はそれまでの最後の信号の１つによらないであろう。なぜなら、それは、それらのタイミングがそれまで満たされた位置に、戻されているからである。しかし、ステップＳ２６は、その時点の最後の信号を、すこしは望ましい位置に移動している。なぜなら、追加のマルチプレクサのステージが、それとマルチプレクサ出力との間に、付け加えられているからである。いずれの場合でも、方法Ｍ１は、ステップＳ２６の結果のモジュールに対して、マルチプレクサ制御入力を駆動する信号のタイミングを進めることを、提供しない。したがって、ステップＳ２７での失敗が、それまでの、又は、その時点の最後の信号のタイミングによるものであると、ステップＳ２８が決定した場合には、方法Ｍ１は、規格に合致することなく、終結する。さもなければ、方法Ｍ１は、（Ｎ＋１）回目の繰り返しを始めるために、ステップＳ２０に戻る。
【００５５】
本発明は、記述した方法について、多くの代替を提供する。図示した方法においては、合致するように試みられた確かなタイミング要求が、存在する。一般に、規格が合致したからといって、単に方法をストップする必要性はない。さらなる改良が要望されるかもしれない。
【００５６】
方法Ｍ１において、一連の決定ステップが存在すればどこでも、フローチャート化されたような決定は、論理的に等価な手法により、混合され、又は、再整理することができる。そのような一連の処理には、３つあり、１）ステップＳ１３、Ｓ１４、２）ステップＳ２３、Ｓ２４、Ｓ２５、３）ステップＳ２７、Ｓ２８を含んでいる。例えば、ステップＳ２７及びＳ２８は、３つの結果による単一のテストにすることができる。別の例としては、方法Ｍ１は、ステップＳ２３として、全体的なタイミングが合致するかどうかを、最初に判断してもよい。もしステップＳ２３が否定的に終わった場合、次のステップでは、その失敗が最後の信号のいずれかを原因とするものであるかどうかを、判断することができる。もし違えば、方法は繰り返される。もしそうであれば、さらに別のステップで、その時点の最後の信号で失敗したのかどうかを、判断するであろう。もしそうであれば、方法は、適合する規格がないまま、終結する。もしそうでなければ、方法はステップＳ２６を続けることができる。
【００５７】
選択的に、方法は、最適化設計の判断を、使用することができる。この場合、方法は、Ｎ＝Ｐまでは、成功であるか失敗であるかに拘わらず、進めることができる。すべてのモジュールのタイミング特性が生成されているので、それらを比較することができる。タイミング特性を進化させて、ロジックにより消費される増加エリアに対して、重み付けをしてもよい。選択的に、回路エリアの機能のいくつかの基準を満たすまで、方法が繰り返されるようにしてもよい。
【００５８】
ロジック入力からマルチプレクサ制御入力に移すべき「最後」の選び方には、多くの選択肢がある。到達時刻、ファンアウト、モジュールを通過する際のレイテンシは、すべて考慮に入れることができ、また、様々に組み合わせることができる。図示したケースでは、これらの基準は、同条件であることを打破するためだけに低い優先順位の基準が用いられて、優先順位付けが行われた。選択的に、例えば、より大きいファンアウトを有する僅かに速い信号が、それよりも小さいファンアウトを有するそれよりも遅い信号を越えて、遅れた信号として、選択されるように、各基準に重み付けをしてもよい。
【００５９】
本発明は、設計変換の範囲を、提供する。最も直接的な再設計は、遅れる入力に割り付けた一定の入力を、ホールディングすることを含んでいる。しかし、さらなる単純化がしばしば達成される。本発明は、全体的に自動化されたそのようなさらなる単純化、又は、オペレータの介入の容易化を、図ることができる。
【００６０】
図示した実施形態においては、最初の繰り返しの後に、すぐにすべてのサブモジュールを変換した。選択的に、各サブモジュールのタイミングは、分離して、試験が行われてもよい。この場合、問題のあるサブモジュールだけを、変更する必要がある。いくつかのケースでは、これは、１つの信号が、コンビネーションロジックサブモジュールと、マルチプレクサ制御との、双方に入力されることを含んでいる。しかし、いくつかの可能性のある設計では、すべてのサブモジュールをすぐに変換しなければならないとすると、見落としになるであろうと考えられる。
【００６１】
これに対して、方法は、１回に１よりも多い入力の移動を許容することにより、より速く実行できるかもしれない。このために、単一の遅れ信号の代わりに、方法は、モジュール入力からマルチプレクサ制御入力に移すべき複数の遅れ信号を、特定できる。この場合、遅れの決定は、２つの相互排他的な入力の集合、空でなく（non-empty）、完全でない（non-exhaustive）部分集合、−−複数の入力の１つを、残っているサブモジュール入力に分配し、変換すべき残りは、マルチプレクサ制御入力に分配する。再定義は、ステージの数を調整することによるマルチプレクサの変更を含んでおり、それらの入力はそれらのステージを制御する。
【００６２】
記述した方法は、１出力のモジュールに対して、適用した。しかし、この方法は、１よりも多い出力を有するモジュールにも、適用することができる。出力における入力の影響による遅れが、基本的に入力への到達の遅れを原因とするような場合に、本方法は特に効果的である。いくつかのケースでは、複数出力モジュールを、１つの出力でタイミングを正すために変更することは、もう１つの出力でのタイミングに、悪影響を及ぼすかもしれない。
【００６３】
複数出力モジュール用の好ましい方法は、それぞれが１つの出力を有する複数のサブモジュールを含んでいるように、モジュールを設計する。記述した方法のステップは、それらの独立のサブモジュールのそれぞれに、適用することができる。このアプローチは、１つのタイミングを悪くして、もう１つのタイミングを改善するという変更の問題を、回避する。それゆえ、各出力は、別々に最適化することができる。
【００６４】
図２に示すように、方法Ｍ１の繰り返しは、最初に、ステージを追加することなく、再設計を行い、所定の状態において、新しいステージの追加を要求する。選択的に、追加のステージを最初に追加してもよく、その場合、その時点の遅れ信号のタイミングが満たされなかったら、取り除いてもよい。また、双方の実施形態は、同時に行ってもよく、より好ましい方を比較して選択してもよい。説明した実施形態について、これら及び他のバリエーション及び変形が、本発明により提供される。その範囲は、添付されたクレームにより定められる。クレームにおいて、引用されて用いられた言葉は、記憶を助けるラベルであり、限定する言葉ではない。
【図面の簡単な説明】
【図１】  図１は、本発明に係る方法の最初の繰り返しのフローチャートである。
【図２】  図２は、図１の方法の続きとなる繰り返しのフローチャートである（図２において、方法の終端は、決定ダイアモンドが成立しない場合である）。
【図３】  図１及び図２の方法を適用する前のオリジナルの（最初の）コンビネーションロジックモジュールについてのブロック図である。
【図４】  図１におけるフローチャートの方法の最初の繰り返しの適用後における、図３のモジュールから得られる、変更された（第２の）コンビネーションロジックモジュールのブロック図である。
【図５】  図２におけるフローチャートの方法の２回目の繰り返しの第１の部分の適用後における、図４のモジュールから得られる、第３のコンビネーションロジックモジュールのブロック図。
【図６】  図２におけるフローチャートの方法の２回目の繰り返しの第２の部分の適用後における、図５のモジュールから得られる、第４のコンビネーションロジックモジュールのブロック図。
【符号の説明】
図３から図６において、入力及び出力は、それらが伝達する信号の名称で、明示されている。
【図１】
0004443775.tif 000002
【図２】
0004443775.tif 000003
【図３】
0004443775.tif 000004
【図４】
0004443775.tif 000005
【図５】
0004443775.tif 000006
【図６】
0004443775.tif 000007