(57)【要約】【課題】  マルチサイクル・クロック・ゲータと回路設計アップデータとを含む装置を提供する。【解決手段】  マルチサイクル・クロック・ゲータは、回路設計のデータ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成する。回路設計アップデータは、選択されたマルチサイクル・ゲーティング・グループで回路設計を更新する。各ゲーティング・グループは、単一ゲーティング関数に関連付けられる。各ゲーティング・グループごとに、そのゲーティング・グループの０番目のレベルのデータ・ラッチ・デバイスがそのゲーティング関数でゲーティングされ、そのゲーティング・グループのｉ番目のレベルのデータ・ラッチ・デバイスがそのゲーティング関数のｉ番目のラッチ・バージョンでゲーティングされる。【選択図】  図３
2009520287.tif 000002
【特許請求の範囲】
【請求項１】
マルチサイクル・クロック・ゲーティングのための方法において、
データ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成することを含む前記方法。
【請求項２】
各前記ゲーティング・グループが単一ゲーティング関数に関連付けられ、各ゲーティング・グループごとに、前記ゲーティング・グループの０番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数でゲーティングし、前記ゲーティング・グループのｉ番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数のｉ番目のラッチ・バージョンでゲーティングすることも含む、請求項１に記載の方法。
【請求項３】
前記生成することが、
入力回路設計のデータ・ラッチ・デバイスの値が変化しない条件を識別するインジケータ信号を作成することと、
Ｋ回という複数回、前記インジケータ信号で前記回路を展開することと、
少なくとも前記展開インジケータ信号から前記データ・ラッチ・デバイスに関する複数の候補ゲーティング関数を決定することと、
を含む、請求項１または２に記載の方法。
【請求項４】
前記決定することが、
まとめてＡＮＤが取られた前記展開インジケータ信号の二分決定グラフ（ＢＤＤ）Ｘを構築することと、
無変更値でＸのＢＤＤ  Ｙを生成することと、
各タイム・スタンプｋごとに、その入力がｋ番目のサイクルのものではないＢＤＤ  Ｙkの変数を除去することと、
を含む、請求項３に記載の方法。
【請求項５】
前記生成することが、
入力サイクルにのみ依存する、前記回路のデータ・ラッチ・デバイスのグループＧを検出することと、
ｊ番目のゲーティング関数Ｆjを共用する、前記グループＧのデータ・ラッチ・デバイスのグループＨjを決定することと、
各グループＨjごとに、グループＨjの既存のデータ・ラッチ・デバイスから入力を受け取る、前記回路のデータ・ラッチ・デバイスを追加することと、
を含む、請求項１ないし４のいずれかに記載の方法。
【請求項６】
前記追加することが、
各初期グループＨjごとに、そこに含まれるデータ・ラッチ・デバイスをレベル０のデータ・ラッチ・デバイスとして定義することと、
各ｉ番目のレベルごとに、前記データ・ラッチ・デバイスがすでにグループＨjに存在するレベルｉのデータ・ラッチ・デバイスのみに依存する場合、前記回路のデータ・ラッチ・デバイスをレベルｉ＋１のデータ・ラッチ・デバイスとしてグループＨjに追加することと、
を含む、請求項５に記載の方法。
【請求項７】
データ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成するためのマルチサイクル・クロック・ゲータにおいて、
入力回路設計のデータ・ラッチ・デバイスの値が変化しない条件を識別するインジケータ信号を作成するためのインジケータ信号発生器と、
Ｋ回という複数回、前記インジケータ信号で前記回路を展開するための展開器と、
少なくとも前記展開インジケータ信号から前記データ・ラッチ・デバイスに関する複数の候補ゲーティング関数を決定するためのゲーティング関数決定器と、
を含む、マルチサイクル・クロック・ゲータ。
【請求項８】
前記ゲーティング関数決定器が、
まとめてＡＮＤが取られた前記展開インジケータ信号の二分決定グラフ（ＢＤＤ）Ｘを構築して無変更値でＸのＢＤＤ  Ｙを生成し、各タイム・スタンプｋごとに、その入力がｋ番目のサイクルのものではないＢＤＤ  Ｙkの変数を除去するための二分決定グラフ・オペレータを含む、請求項７に記載のマルチサイクル・クロック・ゲータ。
【請求項９】
入力サイクルにのみ依存する、前記回路のデータ・ラッチ・デバイスのグループＧを検出するための回路レビュアと、
ｊ番目のゲーティング関数Ｆjを共用する、前記グループＧのデータ・ラッチ・デバイスのグループＨjを決定するためのゲーティング関数決定器と、
各グループＨjごとに、グループＨjの既存のデータ・ラッチ・デバイスから入力を受け取る、前記回路のデータ・ラッチ・デバイスを追加するグループ発生器と、
を含む、請求項７または８に記載のマルチサイクル・クロック・ゲータ。
【請求項１０】
前記グループ発生器が、
各初期グループＨjごとに、そこに含まれるデータ・ラッチ・デバイスをレベル０のデータ・ラッチ・デバイスとして定義するためのレベル０の定義器と、
各ｉ番目のレベルごとに、前記データ・ラッチ・デバイスがすでにグループＨjに存在するレベルｉのデータ・ラッチ・デバイスのみに依存する場合、前記回路のデータ・ラッチ・デバイスをレベルｉ＋１のデータ・ラッチ・デバイスとしてグループＨjに追加するための非レベル０の定義器と、
を含む、請求項９に記載のマルチサイクル・クロック・ゲータ。
【請求項１１】
各前記ゲーティング・グループが単一ゲーティング関数に関連付けられ、前記回路設計アップデータが前記データ・ラッチ・デバイスをゲーティングするためのゲーティング関数インプリメンタを含み、各ゲーティング・グループごとに、前記インプリメンタが前記ゲーティング・グループの０番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数でゲーティングし、前記ゲーティング・グループのｉ番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数のｉ番目のラッチ・バージョンでゲーティングする、請求項７ないし１０のいずれかに記載のマルチサイクル・クロック・ゲータ。
【請求項１２】
前記データ・ラッチ・デバイスがフリップフロップおよびラッチのタイプである、請求項７ないし１１のいずれかに記載のマルチサイクル・クロック・ゲータ。
【請求項１３】
回路設計のデータ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成するための請求項７ないし１２のいずれかに記載のマルチサイクル・クロック・ゲータと、
選択されたマルチサイクル・ゲーティング・グループで前記回路設計を更新するための回路設計アップデータと、
を含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、回路設計に関し、特に、データ・ラッチ・デバイス（data latching device）のクロック・ゲーティング（clockgating）に関する。
【背景技術】
【０００２】
複雑なハードウェア部品は、典型的には、無数のトランジスタから構成されている。回路設計者は、典型的には、その設計プロセスを支援するための計算機援用設計プログラムを使用する。設計者が回路の概念設計を終了すると、多くの最適化を行うことができる。
【０００３】
たとえば、低電力設計の場合、必要ではないときにその他の素子を動作させないために、論理素子を追加することが有用である場合が多い。
【０００４】
次に、低電力動作のために行うことができる変更を例示する図１および図２を参照する。図１は、フリップフロップ１２を有する第１の回路１０を示している。すべてのフリップフロップのように、フリップフロップ１２は、クロック信号ＣＬＫによって制御される。クロック信号ＣＬＫがハイになると、フリップフロップ１２はその入力Ｉから計算された値Ｑを出力し、その入力Ｉは論理回路１４の一関数にすることができ、次に論理回路１４は複数の入力（ａ、ｂ、およびｃが示されている）の一関数にすることができる。フリップフロップ１２は、入力Ｉが変化したかどうかに関係なく、その計算を実行することになる。回路設計者は、自分の回路の電力消費量を最小限にする方法を決定することになると、フリップフロップの活動を検討することができ、特定の状況の場合に値が変化しないと自分が把握しているものを「ゲーティング」することができる。このようにするために、設計者は、フリップフロップへのクロック入力を切断するための回路を追加することができる。
【０００５】
この変更は図２に示されている。１０’と示されているこの回路では、フリップフロップ１２は論理回路１４が実行する通りに存続しているが、フリップフロップ１２へのクロック信号は変化している。ＧＣＬＫと示されているクロック信号は、クロック信号ＣＬＫとイネーブル信号ＥＮの両方がアクティブであるときにのみアクティブになるゲート・クロック信号である。ゲート・クロック信号ＧＣＬＫはゲート１６によって生成される。個々のフリップフロップ上でこのように実行されるクロック・ゲーティングは「密（fine-grained）」クロック・ゲーティングとして知られている。
【０００６】
クロック・ゲーティングのためのもう１つの方法は「粗（coarse-grained）」クロック・ゲーティングとして知られている。粗クロック・ゲーティングでは、同じクロック・ゲーティング関数を使用して多数のフリップフロップが遮断され、その結果、電力使用量の大幅な低減がもたらされる。たとえば、浮動小数点演算ユニットなど、単一ユニットとして動作する回路の各種セクションをクロック・ゲーティングすることができる。
【０００７】
クロック・ゲーティングのためのその他の候補は、いつでも決定しやすいわけではない。その上、回路をいつゲーティングしなければならないかを決定する論理関数は、フリップフロップなどの論理ゲートによって実装される。ゲーティングすべき回路と比較して、論理関数が複雑である（すなわち、遮断される回路より多くのゲートを有する）場合、クロック・ゲーティングはほとんど電力を節約できない。
【０００８】
以下の論文では、自動クロック・ゲーティング方法について論じている。
1997European Design and Test ConferenceにおけるL. Benini、G. De Micheli、E. Macii、M. Poncino、R. Scarsiによる「Symbolic Synthesis of Clock-Gating Logic for Power Optimization ofControl-Oriented Synchronous Networks」
Proc. IFIP Int. Workshop on Logic andArchitecture Synthesis, 1996におけるF. Theeuwen、E. Seelenによる「Power Reduction through Clock Gating by Symbolic Manipulation」
Proc. Twelfth International Conference onVLSI Design, 1999におけるN. Raghavan、V. Akella、S. Bakshiによる「Automatic Insertion of GatedClocks at Register Transfer Level」
IEEE Transactions on Circuits and Systems- II: Analog and Digital Signal Processing, Vol. 44, No. 6, June 1997におけるT.Lang、E. Musoll、J. Cortadellaによる「Individual Flip-Flops with Gated Clocks for Low Power Datapaths」
【０００９】
本発明と見なされる主題は、本明細書の結論部分で詳しく指摘され、明確に権利が主張されている。しかし、本発明は、その目的、特徴、および利点とともに構成および動作方法の両方について、添付図面とともに読んだときに以下の詳細な説明を参照することによって最も良く理解することができる。
【００１０】
例証を単純かつ明瞭にするため、図面に示されている要素は必ずしも一定の縮尺で描かれているわけではないことが分かるであろう。たとえば、いくつかの要素の寸法は明瞭にするために他の要素に対して誇張されている可能性がある。さらに、適切と見なされる場合、対応する要素または類似している要素を示すために、複数の図面間で参照番号が繰り返される可能性もある。
【特許文献１】米国特許出願第１１／２９５９３６号
【非特許文献１】1997 European Design and Test ConferenceにおけるL.Benini、G. De Micheli、E. Macii、M. Poncino、R. Scarsiによる「Symbolic Synthesis of Clock-Gating Logic for Power Optimization ofControl-Oriented Synchronous Networks」
【非特許文献２】Proc. IFIP Int. Workshop on Logic and Architecture Synthesis, 1996におけるF. Theeuwen、E. Seelenによる「Power Reduction through Clock Gating by Symbolic Manipulation」
【非特許文献３】Proc. Twelfth International Conference on VLSI Design, 1999におけるN. Raghavan、V. Akella、S. Bakshiによる「Automatic Insertion of GatedClocks at Register Transfer Level」
【非特許文献４】IEEE Transactions on Circuits and Systems - II: Analog and DigitalSignal Processing, Vol. 44, No. 6, June 1997におけるT. Lang、E. Musoll、J. Cortadellaによる「Individual Flip-Flops with Gated Clocks for Low Power Datapaths」
【非特許文献５】CHARME 2003におけるR. Tzoref、M. Matusevich、E. Berger、I. Beerによる「An Optimized Symbolic BoundedModel Checking Engine」
【非特許文献６】IEEE Transactions on Computers, Vol. C-35(8), 1986におけるR. Bryantによる「Graph-based algorithms forBoolean function manipulation」
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の諸態様は、複数サイクル・クロック・ゲーティング機会を検出するための方法およびシステムを提供し、これらは特許請求の範囲に定義されているが、それらについて述べる。
【課題を解決するための手段】
【００１２】
したがって、本発明の好ましい一実施形態により、マルチサイクル・クロック・ゲータ（multi-cycle clock gater）と回路設計アップデータ（circuitdesign updater）とを有するユニットが提供される。マルチサイクル・クロック・ゲータは、回路設計のデータ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成することができる。回路設計アップデータは、選択されたマルチサイクル・ゲーティング・グループで回路設計を更新することができる。
【００１３】
さらに、本発明の好ましい一実施形態により、各ゲーティング・グループは、単一ゲーティング関数に関連付けることができる。各ゲーティング・グループごとに、そのゲーティング・グループの０番目のレベルのデータ・ラッチ・デバイスをそのゲーティング関数でゲーティングすることができ、そのゲーティング・グループのｉ番目のレベルのデータ・ラッチ・デバイスをそのゲーティング関数のｉ番目のラッチ・バージョンでゲーティングすることができる。
【００１４】
その上、本発明の好ましい一実施形態により、データ・ラッチ・デバイスはフリップフロップまたはラッチにすることができる。
【００１５】
さらに、本発明の第１の好ましい実施形態により、マルチサイクル・クロック・ゲータは、インジケータ信号発生器（indicator signal generator）と、展開器（unfolder）と、ゲーティング関数決定器（gating function determiner）とを含む。インジケータ信号発生器は、入力回路設計のデータ・ラッチ・デバイスの値が変化しない条件を識別するインジケータ信号を作成することができる。展開器は、Ｋ回という複数回、インジケータ信号で回路を展開することができ、ゲーティング関数決定器は、少なくとも展開インジケータ信号から多数のデータ・ラッチ・デバイスに関する複数の候補ゲーティング関数を決定することができる。
【００１６】
さらに、本発明の第１の好ましい実施形態により、ゲーティング関数決定器は、まとめてＡＮＤが取られた展開インジケータ信号の二分決定グラフ（ＢＤＤ：binary decision diagram）Ｘを構築して無変更値（no changevalue）でＸのＢＤＤ  Ｙを生成し、各タイム・スタンプｋごとに、その入力がｋ番目のサイクルのものではないＢＤＤ  Ｙkの変数を除去するための二分決定グラフ・オペレータを含む。
【００１７】
その上、本発明の第２の好ましい実施形態により、マルチサイクル・クロック・ゲータは、回路レビュア（circuit reviewer）と、ゲーティング関数決定器と、グループ発生器（groupgenerator）とを含む。回路レビュアは、入力サイクルにのみ依存する、その回路のデータ・ラッチ・デバイスのグループＧを検出することができる。ゲーティング関数決定器は、ｊ番目のゲーティング関数Ｆjを共用する、そのグループＧのデータ・ラッチ・デバイスのグループＨjを決定することができ、グループ発生器は、各グループＨjごとに、グループＨjの既存のデータ・ラッチ・デバイスから入力を受け取る、その回路のデータ・ラッチ・デバイスを追加することができる。
【００１８】
さらに、本発明の第２の好ましい実施形態により、グループ発生器は、各初期グループＨjごとに、そこに含まれるデータ・ラッチ・デバイスをレベル０のデータ・ラッチ・デバイスとして定義するためのレベル０の定義器（definer）と、各ｉ番目のレベルごとに、データ・ラッチ・デバイスがすでにグループＨjに存在するレベルｉのデータ・ラッチ・デバイスのみに依存する場合、回路のデータ・ラッチ・デバイスをレベルｉ＋１のデータ・ラッチ・デバイスとしてグループＨjに追加するための非レベル０の定義器とを含む。
【００１９】
最後に、本発明の好ましい一実施形態により、本発明は、マルチサイクル・クロック・ゲータと回路設計アップデータによって実装される方法を組み込むものである。
【発明を実施するための最良の形態】
【００２０】
以下の詳細な説明では、本発明を完全に理解するために多数の具体的な詳細が示されている。しかし、当業者であれば、これらの具体的な詳細がなくても本発明を実施可能であることを理解するであろう。その他の事例では、本発明を曖昧にしないために、周知の方法、手順、およびコンポーネントについては詳細に記載されていない。
【００２１】
特に他の指定がない限り、「処理（processing）」、「コンピューティング（computing）」、「計算（calculating）」、「決定（determining）」などの用語を使用する考察は、コンピューティング・システムのレジスタまたはメモリあるいはその両方内の電子などの物理量として表現されたデータについて、コンピューティング・システムのメモリ、レジスタ、あるいはその他のこのような情報記憶装置、情報伝送装置、または情報表示装置内の物理量として同様に表現された他のデータへの操作または変換あるいはその両方を行うコンピュータ、コンピューティング・システム、または同様の電子コンピューティング・デバイスのアクションまたはプロセスあるいはその両方を指すことが認識されるであろう。
【００２２】
本明細書に提示されたプロセスおよび表示は、特定のコンピュータまたはその他の装置に本質的に関連するものではない。加えて、本発明の諸実施形態は、特定のプログラミング言語に関連して記載されているわけではない。本明細書に記載されている本発明の教示を実装するために様々なプログラミング言語を使用可能であることは認識されるであろう。
【００２３】
本出願人は、特定のフリップフロップ用のクロック・ゲーティング関数が少なくとも１つの他のフリップフロップ用のクロック・ゲーティング関数としてラッチ形式で使用可能である状況が存在する可能性があることを認識している。これは、おそらくラッチされた同じクロック・ゲーティング関数を使用する複数サイクルのフリップフロップを伴う可能性があるので、「マルチサイクル」クロック・ゲーティングとして知られている可能性がある。
【００２４】
本発明のマルチサイクル・ゲーティング・グループでは、ある設計のセクション全体をまとめてオフにするのではなく、ある回路の種々のデータ・ラッチ・デバイスが異なる時期にオン／オフになることが認識されるであろう。
【００２５】
マルチサイクル・ゲーティング・グループはデータ・ラッチ・デバイスの「データ依存（data dependent）」状態もゲーティングすることができ、データ依存状態はデータ・ラッチ・デバイスの出力が制御入力の値だけでなくデータ入力値に依存するときの状態として定義できることが認識されるであろう。データ独立（data independent）状態は、データ・ラッチ・デバイスの出力がデータ入力に関係なく同じである状態である。たとえば、（ｉｆ  ＥＮ＝１  ｔｈｅｎ  ｆ（Ａ，Ｂ，Ｃ）  ｅｌｓｅ  Ｑ）などの単純な入力関数の場合、出力Ｑの値が変化しないケースとして、１）ＥＮ＝０の場合と、２）ＥＮ＝１かつｆ（Ａ，Ｂ，Ｃ）＝Ｑの場合という２つのケースが存在する。第１のケースは、入力値Ａ、Ｂ、またはＣのいずれにも依存せず、したがって、データ独立である。第２のケースは、入力値Ａ、Ｂ、またはＣに依存するので、データ依存である。
【００２６】
次に、電力低減回路レビュア１８を例示している図３を参照する。レビュア１８は、新規のマルチサイクル・クロック・ゲータ２０と、回路アップデータ（circuit updater）２２とを含むことができる。マルチサイクル・クロック・ゲータ２０は、入力回路設計Ｒを検討して、潜在的なマルチサイクル・クロック・ゲーティング機会を検出し、クロック・ゲートを制御するための論理関数を生成することができる。回路アップデータ２２は、回路設計者などのユーザと対話して、どの潜在的な機会をユーザが実装する必要があるかを決定することができ、選択されたクロック・ゲートとその関連論理で回路設計Ｒを更新することができる。その結果は、更新された低電力設計Ｒ’になる可能性がある。
【００２７】
マルチサイクル・クロック・ゲータ２０は、複数サイクルに使用可能なクロック・ゲーティング論理関数を生成することができ、その結果、オーバヘッドを低減するか、またはより大きい関数（すなわち、より多くのゲートを有するもの）をクロック・ゲーティングに使用できるようにするか、あるいはその両方になる。
【００２８】
マルチサイクル・クロック・ゲータ２０は、それぞれの動作に基づいて回路を複数ユニットに分割せずに、回路を全体として見なすことによって動作することができる。次に、クロック・ゲータ２０によって実行される方法を例示している図４と、図４の方法の諸ステップを理解する際に有用である図５、図６、および図７とを参照する。
【００２９】
クロック・ゲータ２０は初めに設計Ｒを検討して、そこに含まれるフリップフロップ、ラッチ、またはその他のデータ・ラッチ・デバイスを識別することができる（ステップ２４）。図５、図６、および図７にこのように示されているので、残りの考察では「フリップフロップ」という用語を使用する。しかし、本発明はすべてのタイプのデータ・ラッチ・デバイスについて動作することが理解されるであろう。
【００３０】
ステップ２５では、クロック・ゲータ２０は、どのイネーブル信号がどのフリップフロップを制御するかを決定することができ、それに応じてフリップフロップをグループ化することができる。すべてのフリップフロップをイネーブル信号で制御できるわけではなく、すべてのイネーブル信号をゲーティングに使用できるわけではないことが認識されるであろう。いくつかのイネーブル信号は、その周りにフィードバック・ループを有するフリップフロップを制御することができる。このようなイネーブル信号は、本発明の譲受人に対し２００５年１２月７日に出願された「Ｃｌｏｃｋ  Ｇａｔｉｎｇ  Ｔｈｒｏｕｇｈ  Ｄａｔａ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｌｏｇｉｃ」という米国特許出願第１１／２９５９３６号に記載されている方法を使用して、異なるイネーブル信号に変換することができる。
【００３１】
（ループ２３でチェックされている通り）このように決定された各イネーブル信号の場合、次にクロック・ゲータ２０は、現行イネーブル信号によって使用可能になる回路内のフリップフロップまたはいずれのイネーブル信号にも割り当てられていないフリップフロップの値が変化しない条件を識別できる論理を一時的に追加することができる（ステップ２６）。たとえば、図５は分析すべき回路３０を示している。これは、５つの入力ｘ１、ｘ２、ｘ３、ｘ４、およびｘ５と、３つのフリップフロップＦＦ−１、ＦＦ−２、およびＦＦ−３とを有する。また、これは、組み合わせ論理３２−１、３２−２、および３２−３も有し、論理３２−１および３２−３はフリップフロップＦＦ−１およびＦＦ−３にフィードし、論理３２−３はフリップフロップＦＦ−１およびＦＦ−３の出力を組み合わせてフリップフロップＦＦ−２にフィードする。
【００３２】
図６は、ここで３０’と示されている回路であって、それぞれフリップフロップＦＦ−１、ＦＦ−２、およびＦＦ−３に関連する一時論理３４−１、３４−２、および３４−３の追加後の回路を示している。この例では、各追加論理３４−ｉ（ｉ＝１、・・・、Ｎである場合であって、Ｎは回路３０内のフリップフロップの数である）は、その関連フリップフロップＦＦ−ｉの入力Ａおよび出力Ｂを受け入れるＸＯＲゲートにすることができる。ＸＯＲ３４−ｉの出力信号は、インジケータ信号ｐｉにすることができ、その関連フリップフロップＦＦ−ｉの入力Ａおよび出力Ｂが異なるときに１という値を有し、それらが同じであるときに０という値を有することができる。したがって、インジケータ信号ｐｉは、フリップフロップＦＦ−ｉの値が変化する場合と変化しない場合を示すことができる。クロック・ゲータ２０は、ＲＴＬ論理記述に追加論理３４−ｉ（すなわち、図６の例内のＸＯＲ）を追加することができる。
【００３３】
図４に戻ると、ステップ４０では、クロック・ゲータ２０は、Ｋ個のステップ用に回路３０’を「展開」することができ、Ｋは関心のある論理の深さである。たとえば、Ｋは、チップ入力からチップ出力まで、またはチップのあるセクションへの入力からその出力までの最長パス内のフリップフロップの数として定義できる可能性がある。図５〜図７の例では、２つのレベルのフリップフロップ（第１のレベルのＦＦ−１およびＦＦ−３と、第２のレベルのＦＦ−２）しか存在しないので、Ｋは２になる可能性がある。
【００３４】
「展開」は、実質的に各時間ｋごとに回路３０’のコピーを作成するプロセスにすることができる。CHARME 2003におけるR. Tzoref、M. Matusevich、E. Berger、I. Beerによる「An Optimized Symbolic BoundedModel Checking Engine」という論文では、記号モデル・チェッカ（symbolic modelchecker）内の展開プロセスを論じている。
【００３５】
図７は、２つのサイクル１および２に関する模範的な回路３０’の展開を示している。各入力信号ｘｊは、インジケータ信号ｐｉのようにタイム・スタンプを押される。たとえば、図７は、２つのサイクル１および２に関する入力信号ｘ１の２つのコピー（ｘ１1、ｘ１2）を有し、インジケータ信号ｐ３の２つのコピー（ｐ３1、ｐ３2）が存在している。
【００３６】
図４に戻ると、次にクロック・ゲータ２０は、まとめてＡＮＤが取られた展開インジケータ信号ｐｉkを表す二分決定グラフ（ＢＤＤ）Ｘを構築することができる（ステップ４２）。二分決定グラフ（ＢＤＤ）は、ブール式の全体的にコンパクトな表現であり、一般に、特に複雑なハードウェアの記号モデル・チェックで使用される。
【００３７】
手短に言えば、ＢＤＤは、ブール式を表す有向非周期グラフである。次に簡単に参照することができる図８は、式（（Ａ  ＆  Ｂ  ＆  Ｃ）｜（Ｃ  ＆  Ｄ））に関する模範的なＢＤＤを示しており、「＆」は「ＡＮＤ」を意味し、「｜」は「ＯＲ」を意味する。それぞれの円（またはノード）は変数（Ａ、Ｂ、Ｃ、Ｄ）を示し、線は変数がＦＡＬＳＥ（左側）またはＴＲＵＥ（右側）と評価するときに従うべき方向を示している。リーフ・ノード５１はブール式の値を表している。
【００３８】
したがって、ステップ４２では、クロック・ゲータ２０は、修正された回路３０’のＲＴＬ論理を使用して、各インジケータ信号ｐｉを定義するブール式Ｑｉを決定することができる。ブール演算はＢＤＤ上で実行することができるので、クロック・ゲータ２０は、すべてのブール式Ｑｉとその複数コピーＱｉkについてまとめてＡＮＤを取って、ＢＤＤ  Ｘを生成することができる。
【００３９】
ステップ４４では、クロック・ゲータ２０は、フリップフロップＦＦ−ｉが値を変更しないときにインジケータ信号ｐｉが生成する値を有する無変更ＢＤＤを生成することができる。この実施形態では、インジケータ信号ｐｉは、フリップフロップＦＦ−ｉが値を変更しないときに０という値を生成し、したがって、この実施形態の場合、クロック・ゲータ２０は、ＢＤＤ  Ｘ＝０を作成することによって無変更ＢＤＤ  Ｙを生成することができる。
【００４０】
０からＫまでのｋに関するループ５０では、クロック・ゲータ２０は、ｋ以外のサイクルからの入力ｘｊkに依存する任意のインジケータ信号ｐｉを除去することによってｋ番目のゲーティング・グループを決定することができる。このように実行するために、クロック・ゲータ２０は、まずサイクルｋで使用するために無変更ＢＤＤ  Ｙの一時コピーＹkを生成することができる（ステップ５２）。次にクロック・ゲータ２０は、ｋ以外のサイクルからの入力ｘｊnot_kの関数である任意のインジケータ信号ｐｉ（ｎｏｔ＿ｋ）を一時無変更ＢＤＤ  Ｙkから除去することができる（ステップ５４）。残りのインジケータ信号ｐｉ（ｒｅｍａｉｎ）は、ｋ番目の候補ゲーティング・グループＹk’を形成する。
【００４１】
クロック・ゲータ２０は、望ましくない信号ｐｉ（ｎｏｔ＿ｋ）を除去することができ、次に、ＢＤＤ  Ｙk’について標準的な圧縮動作を実行することができる。このような動作は、当技術分野では既知のものであり、IEEE Transactions on Computers, Vol. C-35(8), 1986におけるR. Bryantによる「Graph-based algorithms forBoolean function manipulation」という論文に論じられている。
【００４２】
ｋ番目の候補ゲーティング・グループＹk’に残されている残りのインジケータ信号ｐｉ（ｒｅｍａｉｎ）は、現行イネーブル信号またはそのラッチ形式あるいはその両方によってゲーティング可能なフリップフロップＦＦ−ｉを示している。
【００４３】
それぞれのゲーティング関数を実装するために必要な論理に比較して大きいゲーティング・グループは、クロック・ゲーティングのための良好な候補である可能性がある。ゲーティング・グループのサイズは、そこに含まれるフリップフロップまたはその他のデータ・ラッチ・デバイスの数によって定義することができる。
【００４４】
クロック・ゲータ２０がループ２３および５０を終了すると、クロック・ゲータ２０は検討のための１組の候補ゲーティング関数とそれぞれのゲーティング・グループとを有することができる。回路アップデータ２２はこれらのゲーティング関数とそのゲーティング・グループを回路設計者に提供することができ、次に回路設計者はどれを実装すべきかを選択することができ、その後、回路アップデータ２２は選択されたゲーティング関数を回路に追加することができ、それにより、更新された回路Ｒ’を生成する。
【００４５】
次に、同じ素子の３２個の繰り返しを有する単純な回路を示す図９と、その回路のクロック・ゲート・バージョンを示す図１０を簡単に参照する。各素子ｎは、入力ｓ（ｎ）と、マルチプレクサ６０−ｎと、３つの連結フリップフロップ６２Ａ−ｎ、６２Ｂ−ｎ、および６２Ｃ−ｎとを有する。フリップフロップ６２Ａ−ｎ、６２Ｂ−ｎ、および６２Ｃ−ｎの出力はａ（ｎ）、ｂ（ｎ）、およびｏ（ｎ）であり、マルチプレクサ６０−ｎへの入力は入力ｓ（ｎ）、信号ｅｎ、およびフリップフロップ６２Ａ−ｎの出力ａ（ｎ）である。マルチプレクサ６０−ｎはイネーブル信号ｅｎによって使用可能になる。
【００４６】
このような回路の場合、クロック・ゲータ２０は、図１０に示すように以下のゲーティング関数を生成することができる。
イネーブル信号ｅｎで信号ａ（ｎ）をゲーティングして、ゲート・クロックｇ０を生成し、
イネーブル信号ｅｎのラッチ・バージョンで信号ｂ（ｎ）をゲーティングして、ゲート・クロックｇ１を生成し、
イネーブル信号ｅｎの二重ラッチ・バージョンで出力信号ｏ（ｎ）をゲーティングして、ゲート・クロックｇ２を生成する。
【００４７】
この例の場合、オーバヘッドは、３つのゲート７０−１、７０−２、および７０−３と、２つの遅延７２−１および７２−２である。特定のケースでは、これは受け入れられるオーバヘッドである可能性がある。単純な回路同士の間に組み合わせ論理が存在する（したがって、たとえば、ｂ（０）がａ（０）−ａ（４）の関数である可能性がある）場合でも、上記のゲーティングが機能することが認識されるであろう。
【００４８】
次に、マルチサイクル・クロック・ゲーティングのためにどのラッチ・デバイスをクロック・ゲーティングするべきかを決定するために、クロック・ゲータ２０によって実行すべき代替方法を例示する図１１を参照する。
【００４９】
前の実施形態のように、クロック・ゲータ２０は初めに設計Ｒを検討して、そこに含まれるデータ・ラッチ・デバイスを識別することができる（ステップ２４）。この場合も、以下の考察では模範的なフリップフロップを使用し、すべてのタイプのデータ・ラッチ・デバイスが含まれることが認識されるであろう。
【００５０】
本発明の好ましい代替実施形態により、クロック・ゲータ２０は、どのフリップフロップが入力のみに依存するかを決定するために設計Ｒのネットリストをトラバースすることができる（ステップ８０）。これはセットＧである。
【００５１】
ステップ８２では、クロック・ゲータ２０は、前のステップで識別された「入力専用（input-only）」フリップフロップＧを検討して、どのフリップフロップが同じクロック・ゲーティング関数Ｆjにより動作するかを決定することができる。クロック・ゲーティング関数Ｆjは、入力専用フリップフロップＧへのイネーブル関数にすぎない可能性がある。代わって、クロック・ゲーティング関数Ｆjは、上述の通り２００５年１２月７日に出願された「Ｃｌｏｃｋ  Ｇａｔｉｎｇ  Ｔｈｒｏｕｇｈ  Ｄａｔａ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｌｏｇｉｃ」という米国特許出願第１１／２９５９３６号に記載されているような密クロック・ゲーティングに関する標準的なアルゴリズムを使用して決定することができる。その結果は、ｊ番目のゲーティング関数Ｆjによってまとめてクロック・ゲーティングすることができるデータ・ラッチ・デバイスのグループＨjをリストすることができる。
【００５２】
次にクロック・ゲータ２０は、各ゲーティング関数Ｆjによってゲーティングすべきフリップフロップを決定することができる。ｊに関するループ８４によって制御される各ゲーティング関数Ｆjについて、クロック・ゲータ２０は、ゲーティング・グループＨj内のフリップフロップを「レベル０」のフリップフロップとして初期設定することができる（ステップ８６）。次にクロック・ゲータ２０は、ｉに関するループ８８に入ることができる。ステップ９０では、クロック・ゲータ２０は、回路のフリップフロップを検討して、ゲーティング・グループＨj内のレベルｉのフリップフロップのみに依存するものを検出することができる。これらのフリップフロップは、「レベルｉ＋１」のフリップフロップと示すことができ、ゲーティング・グループＨjに追加することができる。
【００５３】
ステップ９２では、クロック・ゲータ２０は、ステップ９０で任意の新しいフリップフロップがゲーティング・グループＨjに追加されたかどうかをチェックすることができる。追加された場合、クロック・ゲータ２０は、ステップ９４でｉを増分することができ、ステップ９２の結果が否定になるまでループ８８を続行することができる。
【００５４】
各ゲーティング・グループｊの場合、クロック・ゲータ２０は、以下のゲーティング関数を生成することができる。
クロック・ゲーティング関数Ｆjでレベル０のフリップフロップに関する信号をゲーティングし、
クロック・ゲーティング関数Ｆjのｉ番目のラッチ・バージョンでｉ番目のレベルのフリップフロップに関する信号をゲーティングする。
【００５５】
各ゲーティング・グループＨjのサイズは、そこに保管されるフリップフロップの数にすることができる。
【００５６】
本発明の特定の特徴が本明細書に例示され記載されているが、当業者であれば、多くの修正、代用、変更、および同等のものが思い浮かぶであろう。したがって、特許請求の範囲は、本発明の真の本質に含まれるこのような修正および変更のすべてを包含するものであることが理解されたい。
【００５７】
本発明の範囲は、本明細書に開示された任意の新規な特徴または特徴の組み合わせを含む。これにより、本出願人は、本出願またはそこから派生する任意のその他の出願の手続き遂行中にこのような特徴または特徴の組み合わせに応じて新しい請求項を作成できることを通知する。特に、特許請求の範囲に関しては、従属請求項からの特徴を独立請求項の特徴と組み合わせることができ、それぞれの独立請求項からの特徴は、特許請求の範囲に列挙された特定の組み合わせだけでなく、任意の適切な方法で組み合わせることができる。
【００５８】
念のために付言すると、説明および特許請求の範囲全体を通して本明細書で使用する「含む（comprising）」という用語は、「のみから構成される（consistingonly of）」という意味として解釈すべきではない。
【図面の簡単な説明】
【００５９】
【図１】フリップフロップを含有する回路の概略回路図である。
【図２】フリップフロップ上のクロック・ゲーティングを有する図１の回路の概略図である。
【図３】電力低減回路レビュアのブロック図である。
【図４】本発明の第１の実施形態により動作するクロック・ゲーティング方法の流れ図である。
【図５】図４の方法の諸ステップを理解する際に有用な概略回路図である。
【図６】図４の方法の諸ステップを理解する際に有用な概略回路図である。
【図７】図４の方法の諸ステップを理解する際に有用な概略回路図である。
【図８】図４の方法の諸ステップを理解する際に有用な二分決定グラフの概略図である。
【図９】同じ回路の３２個の繰り返しを有する素子の回路図である。
【図１０】図９の回路のクロック・ゲート・バージョンの回路図である。
【図１１】本発明の第２の実施形態により動作するクロック・ゲーティング方法の流れ図である。
【図１】
2009520287.tif 000003
【図２】
2009520287.tif 000004
【図３】
2009520287.tif 000005
【図４】
2009520287.tif 000006
【図５】
2009520287.tif 000007
【図６】
2009520287.tif 000008
【図７】
2009520287.tif 000009
【図８】
2009520287.tif 000010
【図９】
2009520287.tif 000011
【図１０】
2009520287.tif 000012
【図１１】
2009520287.tif 000013
【手続補正書】
【提出日】平成21年2月17日(2009.2.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成するための方法において、
入力回路設計のデータ・ラッチ・デバイスの値が変化しない条件を識別するインジケータ信号を作成することと、
Ｋ回という複数回、前記インジケータ信号で前記回路を展開することと、
少なくとも前記展開インジケータ信号から前記データ・ラッチ・デバイスに関する複数の候補ゲーティング関数を決定することと、
を含み、
前記決定することが、
まとめてＡＮＤが取られた前記展開インジケータ信号の二分決定グラフ（ＢＤＤ）Ｘを構築することと、
無変更値でＸのＢＤＤ  Ｙを生成することと、
各タイム・スタンプｋごとに、その入力がｋ番目のサイクルのものではないＢＤＤ  Ｙkの変数を除去することと、
を含む前記方法。
【請求項２】
各前記ゲーティング・グループが単一ゲーティング関数に関連付けられ、各ゲーティング・グループごとに、前記ゲーティング・グループの０番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数でゲーティングし、前記ゲーティング・グループのｉ番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数のｉ番目のラッチ・バージョンでゲーティングすることも含む、請求項１に記載の方法。
【請求項３】
前記生成することが、
入力サイクルにのみ依存する、前記回路のデータ・ラッチ・デバイスのグループＧを検出することと、
ｊ番目のゲーティング関数Ｆjを共用する、前記グループＧのデータ・ラッチ・デバイスのグループＨjを決定することと、
各グループＨjごとに、グループＨjの既存のデータ・ラッチ・デバイスから入力を受け取る、前記回路のデータ・ラッチ・デバイスを追加することと、
を含む、請求項１ないし２のいずれかに記載の方法。
【請求項４】
前記追加することが、
各初期グループＨjごとに、そこに含まれるデータ・ラッチ・デバイスをレベル０のデータ・ラッチ・デバイスとして定義することと、
各ｉ番目のレベルごとに、前記データ・ラッチ・デバイスがすでにグループＨjに存在するレベルｉのデータ・ラッチ・デバイスのみに依存する場合、前記回路のデータ・ラッチ・デバイスをレベルｉ＋１のデータ・ラッチ・デバイスとしてグループＨjに追加することと、
を含む、請求項３に記載の方法。
【請求項５】
データ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成するためのマルチサイクル・クロック・ゲータにおいて、
入力回路設計のデータ・ラッチ・デバイスの値が変化しない条件を識別するインジケータ信号を作成するためのインジケータ信号発生器と、
Ｋ回という複数回、前記インジケータ信号で前記回路を展開するための展開器と、
少なくとも前記展開インジケータ信号から前記データ・ラッチ・デバイスに関する複数の候補ゲーティング関数を決定するためのゲーティング関数決定器と、
を含み、
前記ゲーティング関数決定器が、
まとめてＡＮＤが取られた前記展開インジケータ信号の二分決定グラフ（ＢＤＤ）Ｘを構築して無変更値でＸのＢＤＤ  Ｙを生成し、各タイム・スタンプｋごとに、その入力がｋ番目のサイクルのものではないＢＤＤ  Ｙkの変数を除去するための二分決定グラフ・オペレータを含む、
前記マルチサイクル・クロック・ゲータ。
【請求項６】
入力サイクルにのみ依存する、前記回路のデータ・ラッチ・デバイスのグループＧを検出するための回路レビュアと、
ｊ番目のゲーティング関数Ｆjを共用する、前記グループＧのデータ・ラッチ・デバイスのグループＨjを決定するためのゲーティング関数決定器と、
各グループＨjごとに、グループＨjの既存のデータ・ラッチ・デバイスから入力を受け取る、前記回路のデータ・ラッチ・デバイスを追加するグループ発生器と、
を含む、請求項５に記載のマルチサイクル・クロック・ゲータ。
【請求項７】
前記グループ発生器が、
各初期グループＨjごとに、そこに含まれるデータ・ラッチ・デバイスをレベル０のデータ・ラッチ・デバイスとして定義するためのレベル０の定義器と、
各ｉ番目のレベルごとに、前記データ・ラッチ・デバイスがすでにグループＨjに存在するレベルｉのデータ・ラッチ・デバイスのみに依存する場合、前記回路のデータ・ラッチ・デバイスをレベルｉ＋１のデータ・ラッチ・デバイスとしてグループＨjに追加するための非レベル０の定義器と、
を含む、請求項６に記載のマルチサイクル・クロック・ゲータ。
【請求項８】
各前記ゲーティング・グループが単一ゲーティング関数に関連付けられ、前記回路設計アップデータが前記データ・ラッチ・デバイスをゲーティングするためのゲーティング関数インプリメンタを含み、各ゲーティング・グループごとに、前記インプリメンタが前記ゲーティング・グループの０番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数でゲーティングし、前記ゲーティング・グループのｉ番目のレベルのデータ・ラッチ・デバイスを前記ゲーティング関数のｉ番目のラッチ・バージョンでゲーティングする、請求項５ないし７のいずれかに記載のマルチサイクル・クロック・ゲータ。
【請求項９】
前記データ・ラッチ・デバイスがフリップフロップおよびラッチのタイプである、請求項５ないし８のいずれかに記載のマルチサイクル・クロック・ゲータ。
【請求項１０】
回路設計のデータ・ラッチ・デバイスのマルチサイクル・ゲーティング・グループを生成するための請求項５ないし９のいずれかに記載のマルチサイクル・クロック・ゲータと、
選択されたマルチサイクル・ゲーティング・グループで前記回路設計を更新するための回路設計アップデータと、
を含む装置。
【国際調査報告】
2009520287.tif 000014
2009520287.tif 000015
2009520287.tif 000016