(57)【要約】  コンピュータ・システム内で条件付き分岐の結果を予測するシステムおよび方法であって、前記方法が、条件付き分岐の発生を特定するステップ（１０５）と、前の分岐以降のシステム・アクティビティに関連するデータを取得するステップ（１０６）と、前記データを前のシステム・アクティビティに関連するデータと比較するステップ（１１０）と、こうした比較に基づいて分岐結果を予測するステップ（１０８）とを含むシステムおよび方法。アクティビティ・モニタ（図３の２０）は、システム・アクティビティに関するデータを提供するために使用されることができる。
2007527050.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・システム内で条件付き分岐の結果を予測する装置であって、条件付き分岐の発生を特定する手段と、前の分岐以降のシステム・アクティビティに関連するデータを取得する手段と、前記データを前のシステム・アクティビティに関連するデータと比較する手段と、こうした比較に基づいて前記分岐結果を予測する手段とを備える装置。
【請求項２】
システム・アクティビティに関連する前記データは平均のシステム・アクティビティを備える請求項１に記載の装置。
【請求項３】
前のシステム・アクティビティとこうしたアクティビティに対応する分岐結果に関連するデータを格納するアクティビティ履歴テーブルが提供される請求項１または２に記載の装置。
【請求項４】
条件付き分岐に到達した場合に、前の分岐から現在の分岐までのシステム・アクティビティに関するデータを取得する手段と、このデータを前記アクティビティ履歴テーブルに格納されたデータと比較する手段とを備えており、前記分岐結果を予測する手段は現在取得されているアクティビティ・データに最も近いアクティビティ・データに関連する分岐結果を選択する請求項３に記載の装置。
【請求項５】
前記アクティビティ履歴テーブルは、最新のアクティビティ・データと前記選択された分岐結果に従って更新される請求項４に記載の装置。
【請求項６】
条件付き分岐の結果を、その分岐および／または前の分岐の結果履歴を使用して予測する手段を含む前記請求項のいずれか一項に記載の装置。
【請求項７】
前記システムのアクティビティに関連するデータは、分岐履歴を使用した分岐結果の予測精度の信頼度が比較的低い場合にのみ分岐結果の予測に使用される請求項７に記載の装置。
【請求項８】
コンピュータ・システム内で条件付き分岐の結果を予測する方法であって、前記条件付き分岐の発生を特定するステップと、前の分岐以降のシステム・アクティビティに関連するデータを取得するステップと、前記データを前のシステム・アクティビティに関連するデータと比較するステップと、こうした比較に基づいて分岐結果を予測するステップとを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐予測の方法およびシステムに関し、プログラム可能集積回路向けのシーケンシャルなプログラムを実行するプロセッサでの使用に特に適している。
【背景技術】
【０００２】
分岐は、プログラム内でシーケンシャルな実行が中断するポイントである。分岐が無条件の場合は、その結果が常に同じである。つまり、分岐は必ず発生する。しかし、分岐が条件付きの場合は、条件が既知の場合にのみ結果がわかっている。換言すると、条件付き分岐命令では、特定のデータ部分の検査に基づいて、条件付きで制御の移行（ｔｒａｎｓｆｅｒ）が発生する。こうした命令には、ターゲット・アドレスの指定の他にテストする条件が含まれる。この条件は、通常は数値の代数的性質の小規模なセットの１つである。条件が満たされると分岐が発生する。それ以外の場合は分岐が発生しない。
【０００３】
パイプライン・プロセッサ（ｐｉｐｅｌｉｎｅｄ  ｐｒｏｃｅｓｓｏｒｓ）のパフォーマンスは、条件付き分岐の実行に必要な時間によって大きく制限される。パイプライン・コンピュータにおけるこうした条件付き分岐を原因とするパフォーマンスの低下は、検査するデータの代数的条件が決定する前に分岐がフェッチされる場合に発生する。この現象は、このようなコンピュータにおいて分岐命令自体が検査するデータのロケーションを指定する場合は最悪である。代数的条件の評価は、パイプラインの複数のステージが実行され経過した後でしか実行されない。この操作は分岐命令がフェッチされるまで開始できないので、検査する条件は分岐がフェッチされてから数クロック後にならないと認識されない。フェッチする次の命令のロケーションは、データの検査が完了するまでしばらくの間決定できないので、数クロック・サイクルにわたって命令をフェッチできない。
【０００４】
こうしたパフォーマンスの低下を軽減するために、分岐予測技術を利用してもよい。分岐予測では、同じ分岐またはその他の分岐の履歴を使用して現在の分岐結果を予測する。したがって、この予測に基づいて分岐を実行し、パフォーマンス低下の回避を試みる。もちろん、予測された結果が正しくないことが判明するたびに、システムは分岐ポイントに戻り、予測を誤った分岐ポイントより後にフェッチされた命令の実行結果をすべて元に戻し、それからシステムは正しい分岐結果に従って実行を続ける必要がある。このように、誤った分岐の後にフェッチされた命令はすべて廃棄する必要があり、これらはすべて無駄な労力である。したがって、マシンのパフォーマンスは分岐予測の精度に直接関連することが明らかである。
【０００５】
分岐予測で使用する従来のさまざまな考え方が存在する。分岐予測スキームは、静的でも動的でもよい。静的なスキームでは、分岐命令自体に予測が含まれている。こうした予測は通常はプログラムを生成するコンパイラから供給され、典型的なデータ・セットに対してこれまでプログラムを実行してきたコンパイラに基づいている。静的な予測は、コンピュータの命令セットが予測を考慮して設計されている場合にのみ可能である。商業上成功している命令セットのほとんどは、静的分岐予測の機能を提供しない。
【０００６】
動的分岐予測では、プログラムを実行する間にハードウェアによって収集された分岐に関する情報を使用する。プログラムは指定された分岐命令の過去の実行パターンについてしか「認識」できないので、その動的な予測はこうした情報に基づいて行われる。条件付き分岐はかなり頻繁に発生するので、必要なメモリ容量の増大を避けるために、各分岐について格納できる履歴の件数はそれほど多くはない傾向がある。一般に、プログラムにおいて、分岐予測情報は小規模な、しかし変動する分岐のサブセットのみが保持される。
【０００７】
もう１つの考え方は、「バイモーダル（ｂｉｍｏｄａｌ）」分岐予測と呼ばれており、分岐する必要があるかどうかを示す予測インディケータとして２ビットの飽和カウンタ（ｓａｔｕｒａｔｉｎｇ  ｃｏｕｎｔｅｒ）を使用する。２ビットの飽和カウンタでは分岐がグループで発生するという仮定が採用されており、分岐が単独で発生するかグループで発生するかは、最後の分岐が単独で発生したかグループで発生したかを参照して予測できる。
【０００８】
たとえば、国際公開第９８／３６３５０号パンフレット、米国特許第５，８９６，５２９号明細書、米国特許第６，４３８，６５６  Ｂ１号明細書、米国特許第５，９４８，１００号明細書など、既知のさまざまな分岐予測の方法が説明されている。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、要約すると先行技術において分岐予測は基本的に次に示す２つの概念の組み合わせに基づく傾向がある。
−分岐の履歴に基づく分岐結果の予測。この場合は、一般には、たとえば分岐を実行した最新の２回あるいは４回の結果を格納するテーブルが使用される。最も頻度の高い結果に基づいて予測が行われる。しかし、予測の信頼度が変化するのは明らかである。たとえば、分岐の結果が常に同じである場合の信頼度は１００％である。しかし、分岐の結果が毎回変わる場合の信頼度は０％になる。
−前のｎ回の分岐の結果に基づく分岐結果の予測。処理と実装は、前述の概念と同様であるが、予測が基づく情報は明らかに異なっている。繰り返すが、予測の信頼度は大きく変化する。
【００１０】
分岐予測の信頼度がそれほど高くない場合は、失敗する可能性が高い。
そこで、改善された仕組みを考案した。
【課題を解決するための手段】
【００１１】
本発明により、コンピュータ・システム内で条件付き分岐の結果を予測する装置であって、条件付き分岐の発生を特定する手段と、前の分岐以降のシステム・アクティビティに関連するデータを取得する手段と、前記データを前のシステム・アクティビティに関連するデータと比較する手段と、こうした比較に基づいて分岐結果を予測する手段とを備える装置が提供される。
【００１２】
さらに、本発明により、コンピュータ・システム内で条件付き分岐の結果を予測する方法であって、条件付き分岐の発生を特定するステップと、前の分岐以降のシステム・アクティビティに関連するデータを取得するステップと、前記データを前のシステム・アクティビティに関連するデータと比較するステップと、こうした比較に基づいて分岐の結果を予測するステップとを含む方法が提供される。
【００１３】
好ましい実施形態において、システム・アクティビティに関連するデータは平均のシステム・アクティビティを備えている。好ましくは、前のシステム・アクティビティとこうしたアクティビティに対応する分岐結果に関連するデータを格納するアクティビティ履歴テーブルが提供される。このように、好ましい実施形態において、条件付き分岐に到達すると、前の分岐から現在の分岐までのシステム・アクティビティに関するデータが取得され（好ましくはアクティビティ・モニタから）、このデータがアクティビティ履歴テーブルに格納されたデータと比較され、さらに現在取得されているアクティビティ・データに最も近いアクティビティ・データに関連する分岐結果が選択される。ここで、アクティビティ履歴テーブルは、好ましくは最新のアクティビティ・データと選択された分岐の結果に従って更新される。
【００１４】
好ましい実施形態において、本装置は、条件付き分岐の結果を、その分岐および／または前の分岐の結果履歴を使用して予測する手段をさらに含む。システムのアクティビティに関連するデータは、分岐履歴を使用した分岐結果の予測精度の信頼度が比較的低く、あらかじめ指定したしきい値を下回る可能性が高い場合にのみ分岐結果の予測に使用されるのが有利である。
【００１５】
先行技術では、分岐予測で分岐の履歴は考慮するがこうした履歴をもたらすシステム・アクティビティは考慮しない。本発明は、分岐予測のためのもう１つのパラメータ、すなわち最後に予測した分岐から現在の分岐までのシステムのアクティビティ、実行された計算の量に関連するアクティビティの利用を提案する。
【００１６】
アクティビティの監視は、基本的に同じシステム（またはシステムの一部）に関する前のシステムの状態と現在のシステムの状態との差の尺度である。差が大きいほどシステム・アクティビティは大きくなる。アクティビティの監視を実装するにはいくつかの方法があり、こうした方法は当業者には明らかである。比較的単純なものとして供給電流の監視があり、この方法ではシステムのアクティビティも提供される。通常は、資料でよく知られるように、回路の平均電流を測定でき、したがって平均のアクティビティを監視できる。例示的なアクティビティ・モニタについては、後で詳細に説明する。
【００１７】
本発明の以上に示した機能およびその他の機能については、添付の例示的な図面と以下の説明から明らかになるであろう。
【００１８】
ここで、単に例として添付の図面に関連付けながら本発明の１つの実施形態について説明する。
【発明を実施するための最良の形態】
【００１９】
図１を参照すると、本発明の例示的な実施形態による分岐予測方法の流れ図が示されている。
【００２０】
ステップ１００で命令がフェッチされ、分岐かどうかについて判断が行われる（ステップ１０２）。分岐でない場合は命令が実行される（ステップ１０４）。分岐の場合は、それが条件付きかどうかについて判断が行われる（ステップ１０５）。条件付きでない場合は命令が実行され（ステップ１０４）、条件付きの場合は、ステップ１０６で最後の基本ブロック（つまり、最後に予測された分岐から現在の分岐までのコード・ブロック）におけるシステムのアクティビティに関連するデータが取得される。アクティビティ履歴テーブルが提供され、個々の結果に関連して平均のシステム・アクティビティに関するデータがこのテーブルに格納される。取得したアクティビティ・データが比較され（ステップ１１０）、アクティビティ履歴テーブルに格納された結果の中から、取得したアクティビティ・データに最もよく似たものを選択することで、分岐結果が予測される（ステップ１０８）。次に、それに応じて分岐が行われ（ステップ１０４）、最新のシステム・アクティビティ・データと予測された分岐の結果を反映してアクティビティ履歴テーブルが更新される。さらに、次の命令がフェッチされ、このプロセスが繰り返し実行される。
【００２１】
したがって、要約すると、システム・アクティビティを以下のように使用して分岐予測を実行する。
−分岐結果ごとに平均のアクティビティを格納する。
−最後の基本ブロックのアクティビティをこうした値と比較する。
−格納された結果の中でアクティビティが最もよく似たものに基づいて分岐結果を予測する。
【００２２】
好ましい実施形態において、比較のステップには取得したアクティビティの値の上位数桁のみを比較するステップが含まれる。
【００２３】
図２を参照すると、アクティビティ・モニタの回路図が示されており、これを使用して前述の方法を実行するのに必要なさまざまなアクティビティの値を取得できる。しかし、当業者には言うまでもないが、さまざまなタイプのシステム・アクティビティ・モニタが当業者に知られており、その任意のタイプを本発明と組み合わせて利用できる。
【００２４】
図示されたアクティビティ・モニタ１０は、一連のＤタイプのラッチ（フリップフロップまたはシーケンシャル・ロジックと呼ばれることもある）１２ａ〜１２ｅおよび２つの組み合わせ論理ブロック１４、１６を備えている。
【００２５】
このアクティビティ・モニタの例示的な実施形態について説明するために、Ｄタイプのフリップフロップについて説明し、図示したことに留意されたい。しかし、このタイプの回路の目的は、当業者には言うまでもないが、たとえばＪ〜ＫまたはＳ〜Ｒタイプのフリップフロップなどのシーケンシャルでもそれ以外でも、他の論理を使用しても実施できる。さらに、組み合わせ論理ブロック１４、１６は、たとえば処理論理ブロックとデータ・パス論理ブロックの非網羅的な（ｎｏｎ−ｅｘｈａｕｓｔｉｖｅ）実例として示されている。
【００２６】
使用時に、フリップフロップ１２ａは、入力信号Ｉ１を受け取り、第１の論理ブロック１４への第１の入力信号として作用する適切な出力信号Ｏ１を生成する。フリップフロップ１２ｂは、第１の論理ブロック１４からの第１の出力信号である入力信号Ｉ２を受け取り、第２の論理ブロック１６への第１の入力信号として作用する適切な出力信号Ｏ２を生成する。フリップフロップ１２ｃは、第２の論理ブロック１６からの第１の出力信号である入力信号Ｉ３を受け取り、適切な出力信号Ｏ３を生成する。フリップフロップ１２ｄは、第１の論理ブロック１４からの第２の出力信号である入力信号Ｉ４を受け取り、第１の論理ブロック１４への第２の入力信号として作用する適切な出力信号Ｏ４を生成する。フリップフロップ１２ｅは第２の論理ブロック１６からの第２の出力信号である入力信号Ｉ５を受け取り、第２の論理ブロック１６への第２の入力信号として作用する適切な出力信号Ｏ５を生成する。フリップフロップ１２ａ〜１２ｅのそれぞれは、クロック信号ＣＬＫを受け取り、これを使用して入力信号と出力信号を有効にゲート処理する。
【００２７】
任意のフリップフロップ１２ａ〜１２ｅのデータ・コンテンツが変化しない場合は、論理状態の変更（すなわちシステム・アクティビティ）はない。しかし、適切な刺激により、フリップフロップ１２ａ〜１２ｅの１つまたは複数および論理ブロック１４、１６の１つまたは両方、あるいはその一部で状態変更が発生する場合は、この状態変更が回路１０を経由して伝搬する。したがって、指定されたクロック・サイクルについて、システム・アクティビティは回路１０を構成するエレメント内で発生する状態変更の数に比例する。したがって、指定されたクロック・サイクルで状態を変更するエレメントの数がわかれば、その特定のクロック・サイクルにおけるシステム・アクティビティへの直接的な相関が得られる。最新のデジタルＩＣの方法およびツールを使用すると、多くの回路について、入力刺激に応答してどんな状態変更が発生しているか、さらにこうした変更がどこで発生しているかを、設計者があらかじめ知ることができる。こうした事前の知識は、本発明の目的において明らかに有利である。
【００２８】
図３を参照すると、アクティビティ・モニタ２０は、図２に関連して説明した回路のアクティビティを監視するために使用する基本的な構成要素である。フリップフロップまたは論理状態１２は、この特定の例において関連の２つの入力と１つの出力を有するアクティビティ・モニタ２０を備えている。アクティビティ・モニタ２０の第１の入力はフリップフロップ１２の入力Ｄに接続し、アクティビティ・モニタ２０の第２の入力はフリップフロップ１２の出力Ｑに接続する。アクティビティ・モニタ２０は、フリップフロップ１２のＤターミナルとＱターミナルのそれぞれの入力信号と出力信号Ｉ、Ｏの状態によって決定する出力信号ＣＳを生成する。
【００２９】
このように、本発明の実装は従来の分岐予測にシステム・アクティビティを監視する構造を追加したものとほとんど同じである。本発明は、単独でも使用できるが、好ましくは従来の分岐予測スキーマ（１つまたは複数）と組み合わせて使用される。好ましくは、本発明によって提示されたスキーマは、他の方法の信頼度が非常に低い場合にのみ使用される。分岐予測においてシステム・アクティビティの監視を使用すると、システム／コア・アクティビティを考慮することで予測の精度が向上する。
【００３０】
以上に示す本発明の実施形態に関する説明は本発明を限定しないこと、および当業者は添付の特許請求の範囲で定義する本発明の範囲を逸脱することなく、多くの代替的な実施形態を設計できることを理解されたい。請求項において、括弧内に示す任意の参照番号は、特許請求の範囲を限定するものと解釈してはならない。任意の請求項または明細書の全体において、「備えている」、「備える」、およびこれに類する言葉は、列挙する以外のエレメントまたはステップを除外するものではない。特定のエレメントの単数の参照はこうしたエレメントの複数の参照を除外せず、複数の参照は単数の参照を除外しない。本発明は、複数の個別の要素を備えるハードウェアの手段によって実装してもよく、適切にプログラムされたコンピュータの手段によって実装してもよい。複数の手段を列挙するデバイスに関する請求項において、こうした複数の手段はハードウェアの１つの同じアイテムによって実施してもよい。互いに異なる従属請求項において特定の手段が列挙されているという単なる事実は、こうした手段の組み合わせが有利に使用されることができないことを示すものではない。
【図面の簡単な説明】
【００３１】
【図１】本発明の例示的な実施形態による分岐予測方法の概略を示す流れ図である。
【図２】本発明の例示的な実施形態で使用するアクティビティ・モニタの動作の基本原理機能を示す概略的な回路図である。
【図３】例示的なアクティビティ・モニタの一般的な実施形態を示す図である。
【図１】
2007527050.tif 000003
【図２】
2007527050.tif 000004
【図３】
2007527050.tif 000005
【国際調査報告】
2007527050.tif 000006
2007527050.tif 000007
2007527050.tif 000008