(57)【要約】【課題】既知のデバイスの問題を防止するプログラマブルブランチ予測システムを提供する。【解決手段】コンピュータシステムにおけるブランチを予測するためのシステムは、ブランチ命令を含む複数の命令を備えるプログラムコードおよび予測オペレーションを含むメモリと、前記プログラムコードにおけるブランチ命令への参照および対応する予測データを含むストアと、前記プログラムコード内に含まれた前記予測オペレーションに応答して前記予測データを変更する変更手段と、前記予測データに基づいてブランチ命令の挙動を予測して、ある予測を発生する予測手段と、前記予測に応答してブランチ命令の挙動を予測する手段とを備える。ブランチを予測する方法も提供される。【選択図】図２
2007058875.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステムにおいてブランチを予測するためのシステムにおいて、
ブランチ命令を含む複数の命令からなるプログラムコードと、前記ブランチ命令に対して前記プログラムコードにおける所定の位置に該プログラムコードの実行前に該プログラムコードへ挿入される予測オペレーションとを含むメモリと、
前記プログラムコードにおけるブランチ命令への参照、およびブランチ命令の予測結果を有する対応する予測データを含むストアと、
ブランチ命令の挙動の予測に影響するように前記プログラムコード内に含まれた前記予測オペレーションの実行に応答して前記ストアにおける前記予測データを変更するための変更手段と、
前記ストアにおける前記変更された予測データに基づいてブランチ命令の挙動をハードウェアで予測するための予測手段と、
を備えることを特徴とするシステム。
【請求項２】
前記予測手段は、行われると予測されるブランチの行き先参照を予測する手段を備える請求項１記載のシステム。
【請求項３】
前記予測手段は、前記プロセッサによって実行されるコンピュータプログラムを備える請求項１記載のシステム。
【請求項４】
前記予測オペレーションは、ブランチ命令の実行前にそのブランチ命令が行われると予想されるかを前記プロセッサが決定するように予測命令を備える請求項１記載のシステム。
【請求項５】
前記ブランチ命令は前記プログラムコードを繰り返し実行させ、前記予測オペレーションは、前記繰り返し実行を起こさせるブランチ命令の繰り返し実行前に繰り返し実行が行われる予測回数が決定されるように繰り返し予測オペレーションを備える請求項１記載のシステム。
【請求項６】
予測データストレージシステムに記憶された予測データを使用してコンピュータシステムにおける特定のブランチの挙動を予測するための方法において、
ブランチ命令を含む複数の命令を有するプログラムコードを与えるステップと、
前記プログラムコード内のブランチ命令の位置を決定するステップと、
ブランチの挙動のその後の予測に影響する予測オペレーションをブランチ命令の位置の前で前記プログラムコードへ挿入するための挿入ステップと、
プロセッサにて前記プログラムコードを実行する実行ステップと、
前記予測オペレーションの実行に応答してブランチに対する前記予測データを更新する更新ステップと、
前記更新された予測データに基づいてブランチの挙動を予測する予測ステップと、
を含むことを特徴とする方法。
【請求項７】
ブランチ命令を含む複数の命令を有するプログラムコードおよび前記ブランチ命令に対応する予測オペレーションを実行しているコンピュータシステムにおいてブランチの挙動を予測する方法であって、前記コンピュータシステムは、ブランチについての予測データを記憶しているような方法において、
プロセッサにて前記プログラムコードを実行する実行ステップと、
前記予測オペレーションに応答して且つブランチ命令の実行前に前記ブランチ命令に対するブランチ命令の予測結果を含む予測データを更新する更新ステップと、
特定のブランチ命令に対して更新された予測データを自動ブランチ命令予測システムに適用することによって前記ブランチの挙動を予測する予測ステップと、
を含むことを特徴とする方法。
【請求項８】
プログラムコードを繰り返し実行させるブランチ命令の挙動を予測するための方法であって、前記プログラムコードは、前記繰り返し実行を制御するブランチ命令を含み、前記ブランチ命令に対応する予測オペレーションは、前記プログラムコードの実行前に該プログラムコードへ挿入され、前記繰り返し実行の挙動は、前記ブランチ命令が特定の挙動を有する予測回数を含むような方法において、
前記繰り返し実行が行われる予測回数が決定されるようにブランチ命令に対応する予測オペレーションを実行する実行ステップと、
前記繰り返し実行命令の実行の前記予測回数を予測カウンタに記憶させる記憶ステップと、
前記繰り返し実行を制御するブランチ命令が実行される毎に前記予測カウンタをデクレメントするデクレメントステップと、
前記予測カウンタに基づいて前記繰り返し実行命令の最後の実行を予測する予測ステップと、
前記繰り返し実行命令の予測された最後の実行に応答して前記繰り返し実行を脱出する脱出ステップと、
を含むことを特徴とする方法。
【請求項９】
ブランチの挙動を予測するために、ブランチ命令を含む複数の命令を備えるプログラムコードへ、該プログラムコードの実行前に予測オペレーションを挿入する方法において、
前記プログラムコードの実行前に前記プログラムコードを解析して、所定の特性に依存した挙動をするブランチを探し出す解析ステップと、
前記ブランチの実行前に所定の特性の値を計算する計算ステップと、
予測データストレージシステムへ前記所定の特性の前記値を記憶させる予測オペレーションを発生する発生ステップと、
前記予測データストレージシステムに記憶された計算された値に基づいてブランチ命令の挙動を予測するために、前記予測オペレーションが前記ブランチ命令の前に実行されるように、前記プログラムコードの実行前に前記プログラムコードへ前記予測オペレーションを挿入する挿入ステップと、
を含むことを特徴とする方法。
【請求項１０】
前記所定の特性は、帰納変数を備える請求項９記載の方法。
【請求項１１】
自動ブランチプレディクタおよびブランチ値ストレージを有するコンピュータシステムによって実行されるプログラムコードにおいてブランチを予測するためのシステムにおいて、
前記プログラムコードを解析して前記コンピュータシステムによる前記プログラムコードの実行前にブランチ命令を識別するための解析手段と、
前記プログラムコードの実行前にブランチに対して所定の位置に前記プログラムコードへ予測オペレーションを挿入するための挿入手段であって、前記予測オペレーションは、前記ブランチの挙動についてのブランチ命令の予測結果を含む情報を前記ブランチプレディクタへ与えるような挿入手段と、
前記予測オペレーションおよび前記ブランチを含む前記プログラムコードを実行するための実行手段と、
前記ブランチプレディクタによって使用される値を変化させて前記予測オペレーションに基づいて前記ブランチの挙動を予測するための変化手段と、
を備えており、
前記ブランチプレディクタは、前記変化された値に基づいて前記ブランチの挙動を予測する、
ことを特徴とするシステム。
【請求項１２】
前記変更手段は、ブランチの挙動の予測を変化させる手段を備える請求項１記載のシステム。
【請求項１３】
前記予測オペレーションは、ブランチの挙動の予測を変化させる請求項６記載の方法。
【請求項１４】
前記所定の特性は、予測パターンからなる請求項９記載の方法。
【請求項１５】
前記所定の特性は、予測表現からなる請求項９記載の方法。
【請求項１６】
前記所定の特性は、伝播値からなる請求項９記載の方法。
【請求項１７】
前記挿入ステップは、プログラムコードの編集中に該プログラムコードへ前記予測オペレーションを挿入することを含む請求項９記載の方法。
【請求項１８】
自動ブランチ予測システムおよびブランチ予測データストレージデバイスを使用してプログラムコードにおけるブランチ命令を実行する前に使用しうる情報に基づいてプログラムコードのピースにおけるブランチ命令の挙動を予測するための方法において、
前記ブランチ命令に対してある位置に前記プログラムコードへ予測オペレーションを挿入する挿入ステップであって、前記予測オペレーションは、前記ブランチ命令の実行前に使用でき且つ前記ブランチの挙動に影響する、ブランチ命令の予測結果を含む予測データを計算するような挿入ステップと、
前記プログラムコードを実行する実行ステップであって、該プログラムコードの実行は、ブランチ命令に対する前記予測データストレージデバイスに記憶された予測データの値を変化させる予測オペレーションを実行し、前記予測データストレージデバイスに記憶された予測データの変化された値に部分的に基づいてブランチ命令の挙動を予測することを含むような実行ステップと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にコンピュータシステムに係るものであり、特定すればコンピュータシステムのためのプログラマブルなブランチ予測システムと方法に係るものである。
【背景技術】
【０００２】
高性能のプロセッサにおいて命令を幾つかのステップ、例えばフエッチステップ、デコードステップそして実行ステップに分けて、別個の命令処理サブユニットにより各ステップを遂行するというのが普通である。これらの命令処理サブユニットは非同期的に作動してもよく、同じ命令を処理していなければならないということもない。もし個々の命令処理ユニットが同じ命令を処理しているのでなければ、そのことがプロセッサの速度を増大させる。こうして、１クロックサイクル内で順次の命令をオーバラップさせて、一つのフェッチユニットが第２の命令の処理を開始するとき、デコードユニットは第１の命令を処理しているというようにするのが普通である。次のクロックサイクルでそのフェッチユニットは第３の命令を処理し、その間そのデコードユニットは第２の命令を処理し、実行ユニットは第１の命令を処理している。ノーマルなシステムでは各命令処理ユニットは同期して作動し、そして各命令は実行に３クロックサイクルを必要とする。
【０００３】
こうして、非オーバラップ式システムでは４つの命令を実行するのに１２クロックサイクルかかる。これと対照的に命令をオーバラップさせるとこれら４つの命令は唯の６クロックサイクルで実行できる。このオーバラップがプロセッサの処理速度をかなり増大する。同様に、実行されている命令は、２つもしくはそれ以上の命令に対するデコードステップが同じ時間になされるというような仕方で、オーバラップされる。このオーバラップシステムでは複数の命令が同時に処理される。
【０００４】
しかし、この命令オーバラップは大抵のプログラムで様々なブランチ命令が頻繁に発生するため原則として利用できなかったり、無効であったりする。ブランチ命令は命令オーバラップの利点のどれかを完全に失わせ、特にもしもブランチが発生し、そして新しいコードをパイプラインに装填して実行しなければならなくなると、特にそうなる。
【０００５】
ブランチ命令は、命令オーバラップの効率をなくす、もしくは排除することとなるかなり大きな原因を有する。ブランチを取っても、取らなくても、それはどの命令が次になり、そして次の命令が知られていないので、どの命令が命令オーバラップを阻止するかについての一時的な不確かさを持ち込む。
【０００６】
ブランチ命令がつくる命令パイプラインの問題は、ブランチ命令の予測システムを設けることにより解消できる。このブランチ命令の予測システムは、ブランチの実行前に、そのブランチを取るか、否か、もしそのブランチを取るならば、その次の命令、アドレスもしくはそのブランチの行き先に対する他の参照、そしてもしそのブランチを取らないのであれば、その次の命令、そのブランチの行き先に対する参照、例えばアドレスを予測する。ブランチ予測が当たると、ブランチによって処理時間を遅らされることなくプロセッサは働く。しかしながら、もしもその予測が外れると、大きな時間のペナルティが生じ、そしてこの予測外れに対するペナルティはブランチの不確かさに起因する遅延よりも大きい。それ故、ブランチ命令の予測システムにおける予測の精度は高いことが望まれる。
【０００７】
最もありふれたブランチ命令の予測システムは、予測された命令順序に対し反応するか、過去のブランチ命令の挙動に対し反応するか、もしくはプログラムオペランドもしくは命令に対し反応するかのいずれかによってブランチの結果を予測している。
【０００８】
従来の自動ブランチ命令予測システムは記憶ヒエラルキーと一体となっているか、もしくは記憶ヒエラルキーとは別個のものとなっている。例えば、一つの従来のシステムは自動ブランチ命令予測システムを命令キャッシュに組み込んでいる。この組み込みによりシステムは命令キャッシュとしてそしてブランチプレディクタとして働き、このことは都合のよいことである。両システムは同じ命令で作動しなければならず、そしてメモリや他の資源も共用しなければならないからである。他の従来のシステムは、ノンシーケンシャルなアドレスレンジからの命令を含んでいるトレース内に実行プログラムを自動的に再編成し、そしてこれらのトレースを命令キャッシュ内の予測と回復情報と一緒に蓄えるシステムにより、基本的な一体コンセプトに基づいて改善している。
【０００９】
ブランチを取るか、否か（予測される結果）及び／又はその結果（予測される結果）の予測が当たった後そのブランチの行く先のアドレスもしくは参照である）ブランチの挙動の予測の精度を高めるためブランチの結果を正確に予測しようとする幾つかのブランチ予測システムが従来もあった。これらの従来のシステムは以下に説明するように、それらの精度の程度は様々である。あるものはブランチの結果もしくは結末の６０％を正確に予測し、最も精度の高いシステムは９０％の精度となる。これら従来のブランチ予測システムは、静的なブランチプレディクタ、動的なブランチプレディクタ、暗黙理にプログラマブルなブランチプレディクタ、そして明示的にプログラマブルなブランチプレディクタを含む幾つかのカテゴリーに分類される。これらのカテゴリーの各々は異なる利点と欠点と予想精度とを有している。
【００１０】
スタティックブランチ命令予測システムにおいて、ブランチは、スタティックな不変の情報に基づいて予測される。例えば、１つの従来形のスタティックブランチ命令予測システムは、予測される命令のシーケンスのブランチを確認し、それから、ブランチの各々が選択されると常に予測する。このブランチ予測システムは、約６０％の正確さを有する（すなわち、それは、時間に関して約６０％の正確さで予測する）。より正確なスタティックブランチ予測システムは、もし、数字的に、ブランチの目的アドレスがブランチ命令自体よりも低位のメモリ位置であるならば、そのブランチが選択されることを予測する。別の従来のスタティックブランチ予測システムは、ブランチ命令がコンパイルされる時にブランチ命令自体にエンコードされる予測情報を使用する。これらのシステムは全て、与えられたブランチが、スタティック予測情報にしたがって動くと予測する。しかしながら、スタティックブランチ予測情報がつくられた後、いづれかの時間に、ブランチの動きが変化するならば、スタティックブランチ予測システムは、ブランチの動きを間違って予測してしまうであろう。例えば、もし、ブランチ命令の動きがコンパイルする時点で規定されない別の変数によって変化するならば、スタティック予測情報がつくられた後、ブランチの動きは変わってしまうであろう。
【００１１】
与えられたブランチの各々に対する予測判定は固定されており、従って、これらのスタティックブランチ予測システムの正確さには限界がある。正確さを増すために、ダイナミックブランチ予測システムを使用するのが良い。
【００１２】
ダイナミックブランチ予測システムでは、ブランチの結果は、過去のブランチの動きのような、プログラムの実施中、変化するかもしくは変更され得るダイナミックな情報に基づいて予測される。例えば、１つの従来のダイナミックブランチ予測システムは、前のブランチの選択／非選択判定によって更新される飽和カウンターを使用して、もし、前のブランチ判定が、最近、ブランチは、選択されない場合よりも選択される場合の方が多いことを示すならば、そのブランチが選択されると予測する。そうでなければ、ダイナミックシステムは、そのブランチは決して選択されないと予測する。ブランチが実施された後、ブランチ予測情報は更新されるであろう。
【００１３】
ブランチ命令の未来の動きを予測するために、過去のブランチ命令の動きを使用するような様々なダイナミックブランチ予測システムが提案されてきた。これらのダイナミックブランチ予測システムは、しかしながら、依然として正確さに限界がある。何故ならば、これらのシステムは、未来のブランチの動きを予測するために、過去のプログラムデータ及びブランチの動きを使用するからである。
【００１４】
過去のプログラムの動きは、未来のブランチの動きを正確に予測できない。
別の従来のダイナミックブランチ予測システムは、プロシジャーリターンやループのような、予測可能な動きを有するあるブランチ命令に対して、特別なブランチ命令を使用する。これらの特別なブランチ命令は、オペランドの使用法について一致しており、この使用法をこれらのあるブランチの正確な予測に転化することができる。これらのシステムは、しかしながら、他のブランチを正確に予測しない。上記に記述されたこれらのダイナミックシステムのいくつかは、ブランチの結果（すなわち、ブランチが選択されるかどうか）については予測するが、ブランチが選択された場合に、ブランチの目的アドレスについては予測しない。
【００１５】
ブランチが選択されるかどうかの予測がされると、次のステップは、アドレスのような、ブランチの目的地への参照値となるものを決めることである。もし、ブランチが選択されないならば、ブランチの次の目的地は、ブランチの後の次のアドレスであり、従って、ブランチの目的値を容易に予測できる。しかしながら、もし、ブランチが選択されると予測されるならば、次のアドレスとなるものを決めることはより困難になる。１つの従来の目的地アドレス予測システムは、スタック機構を使用することによって、プロシジャーリターンの目的地を予測する。このシステムでは、プログラムがサブルーチンへ分岐する時、例えば、サブルーチンの前に実施された最後の命令のアドレスをスタックに記憶できる。サブルーチンが終了する時、スタックに記憶されたアドレスを使用して、次のアドレスを決めることができる。このスタックは、しかしながら、Ｃ＋＋の仮想ファンクションのコーリングアドレスのような、コンピュータが決める目的地を予測することはできない。何故ならば、仮想ファンクションのコーリングアドレスはスタティックに、固定されていない、もしくは、前のブランチによってつくられていないからである。従って、これらのシステムは、全てのタイプのブランチに対して有効に動作しない。
【００１６】
別の従来の目的地アドレス予測システムは、様々なブランチの過去の目的地アドレスを含むブランチ履歴テーブルを使用する。やはり、このシステムは、プロシジャーリターンについては予測できるが、コンピュータがつくる目的地については予測できない。何故ならば、ブランチの目的地は変わることができるので、過去の目的地は、正確な未来の目的地にはなり得ないからである。第３のブランチアドレス予測システムは、専用のリターンアドレスレジスターを使用して、専用レジスターに記憶された値を観察することによってブランチの目的地アドレスを予測する。これらの専用レジスターシステムは、常に使用可能ではない特別なハードウェア、及び、命令セットの中で、これらのレジスター装置を要求する。
【００１７】
従って、このシステムは実用性に制限がある。第４のブランチアドレス予測システムは、全ての記憶されたオペランドを監視して、未来のブランチアドレスを決める。しかし、このシステムは、過去のプログラムの動きのみを含む情報が使用される場合に良いだけであり。プログラム実行中に、実施可能な分析の量には限界がある。これらのブランチアドレス予測システムは、いくつかのブランチ結果予測装置とほぼ同じ正確さを有する。これらの上記のシステムのいづれかの正確さを更に増大するために、プログラム可能なブランチ予測システムを使用することができる。
【００１８】
プログラマブルブランチ予測システムは、上に述べたいずれの自動ブランチ予測システムの動作に対しても幾つかの形態のプログラマブル制御を与える。これらのプログラマブルシステムでは、自動ブランチ予測システムが実際のブランチ予測を行うのであり、プログラマブルシステムは単にプレディクタを妨害して、不正確であるかもしれない予測情報を調整し、若しくは、プログラム状態を調査して引き出された情報を組み入れるだけである。これらのプログラマブルシステムは単に予測システムに対する制御を出すだけであることから、これらのプログラマブルシステムは、この結果、全ての自動ブランチ予測システムにとって透過であり、また、これら全ての自動ブランチ予測システムと互換性がある。これらのプログラマブルブランチ予測システムは、以下に記述されているように、明示制御、若しくは、暗示制御を使用することができる。
【００１９】
暗示的プログラマブルブランチ予測システムは、ブランチ予測情報に直接的には影響しない。例えば、暗示制御を使用するプログラマブルシステムは、同じ機能を異なる方法で実行するような複数の代替のコードフラグメントの間で選択することもできる。この暗示プログラマブルシステムは、ある特別な実行情況(execution context)においてブランチ予測システムによって最も正確に予測されていそうなコードフラグメントを選択し得る。これらの暗示システムは、しかしながら、多数のコードフラグメントが記憶されねばならないことから、より多くの記憶スペースを必要とし、より複雑なブランチに対しては有用ではない。更に、幾つかのプログラムはリードオンリメモリ（ＲＯＭ）から実行されるため、代替のコードフラグメントはリードオンリメモリ中には書き込まれ得ないことから、このシステムをこれらのプログラムに対しては使用することはできない。あるブランチ命令内で符号化された予測情報を使用する暗示プログラマブルシステムも存在する。これらの暗示プログラマブルシステムは、しかしながら、そのブランチ命令内で符号化されたその予測情報を変更するためにそれが必要になったときに損害を被る。プログラマーはブランチ予測システムを実際に直接的に制御するわけではないが、ブランチ予測システムに与えられたブランチを制御することから、これらのシステムは全て暗示である。明示プログラマブルブランチ予測はより正確であり、より少ないメモリスペースしか必要としない。
明示的プログラマブルシステムは、予測オペレーション、命令、若しくは、命令シーケンスを使用することによって、ブランチ予測システムを直接的に制御する。これらの命令は、プログラムコード中に付加される。これらの明示システムはよりフレキシブルである。なぜなら、付加されるこれらの命令は、いずれの命令セット中にでも付加され得るものであり、また、予測ｏｐ＿コードは、より古いプロセッサ設計がそれらの命令をｎｏ＿ｏｐ命令として取り扱って、付加的なブランチ予測オペレーションさえも有しているようなプログラムコードをこれらのより古いシステムがいまだに使用できるように選択され得るからである。これらの予測システムは通常、基礎的な（underlying）ブランチ予測システムがある特別の時間において使用されようとしているかどうか、予測情報が更新されるかどうか、及び、予測情報のバルク初期化を制御する。これらの明示プログラマブルシステムは、しかしながら、ブランチプレディクタが交互に作動され且つ非作動とされない場合には、ブランチプレディクタによってなされる全ての予測に影響を与える。
【００２０】
上に述べたこれらのシステムはいずれも、どのブランチについてのブランチ結果及び行き先アドレスをも正確且つ確実に予測できるようなプログラマブルブランチ予測システムを提供するものではない。更に、これらの従来システムはいずれも、１つ１つのブランチの予測についての明示制御を与えるものではない。
【発明の開示】
【発明が解決しようとする課題】
【００２１】
既知のデバイスのこれら及び他の問題を防止するプログラマブルブランチ予測システム及び方法が必要とされており、本発明はこれを目的としている。
【課題を解決するための手段】
【００２２】
本発明はブランチ予測システム内の基礎的な予測情報の記憶を制御し得ることから、幾つかの従来システムよりもよりフレキシブルなプログラマブルブランチ予測システムを与える。更に、本発明は、プログラマブルブランチ予測システムを提供するものであるが、このプログラマブルブランチ予測システムは、それら従来システムの欠点が存在しないよう、プログラムコードを変更せず、若しくは、複数のコードフラグメントの間で選択を行わない。本発明は、また、所定のブランチについての予測データの明示制御を、ブランチを実際に実行する前に、また、他のブランチについての予測に影響を与えることなく、有し得るような、プログラマブルブランチ予測システムを与える。
【００２３】
基礎的なブランチ予測情報の予測情報の明示マニピュレーションは、従来のいずれのブランチ予測システムよりも高い予測正確さではない場合でも、少なくともそれらと同程度の高い予測正確さを提供する。更に、この基礎的なブランチ予測情報は制御されていることから、本発明によるプログラマブルブランチ予測システムは、どのタイプのブランチ命令を用いても使用され得るものであり、また、どの命令セットへも付加され得る。このプログラマブルブランチ予測システムはまた、どのタイプの自動ブランチ予測システムをも組み入れることができる。
【００２４】
本発明はまた、予測情報をセーブし、記憶して、様々なタイプのブランチが予測され得るようにした、プログラマブルブランチ予測システムを与える。例えば、ある一片のプログラムコードの実行が他の異なる一片のプログラムコードによって妨害されるようなタスクスイッチについては、古いタスクに関する予測情報が記憶され得る。その後、もしそのプログラムがそのタスクに戻った場合には、そのタスクについての予測情報は、ブランチ予測システムへ再びロードされ得る。同様に、あるブランチについての予測データをセーブして、後にタスクスイッチとは無関係に回復することもできる。従って、複数のフェーズで動作するタスクスイッチやプログラムに対する本発明の予測正確さは劇的に増加される。
【００２５】
本発明によると、ブランチ命令を含む複数の命令を備えるプログラムコードおよび予測オペレーションを含むメモリと、前記プログラムコードにおけるブランチ命令への参照および対応する予測データを含むストアと、前記プログラムコード内に含まれた前記予測オペレーションに応答して前記予測データを変更する変更手段と、予測データに基づいてブランチ命令の結果を予測し、ある予測を発生する予測手段と、前記予測に応答してあるオペレーションを行なう手段とを備えるプログラム可能なブランチ予測システムが提供される。また、ブランチを予測するための方法も提供される。更に、予測オペレーションをプログラムコードに挿入するための方法が提供される。
【発明を実施するための最良の形態】
【００２６】
本発明は、特にプログラム可能なブランチ予測システムに適用できる。それは、本発明が説明されるこのコンテキストに示される。しかし、本発明によるシステム及び方法は大きな実用性を有していることが判るであろう。
【００２７】
図１は、ブランチ予測システムを有するコンピュータシステム２０のブロック図である。このコンピュータシステムは、ブランチプレディクタ２２、プロセッサ２４及びメモリ２６を有することができる。殆どのコンピュータシステムにおけるように、プロセッサは、メモリに記憶されることができる命令を実行することによってコンピュータの動作を制御する。本発明は、特定の型のプロセッサに限定されず、簡約化命令集合コード(RISC: Reduced Instruction Set Code)型プロセッサと同様にＣＩＳＣ(Complex Instruction Set Code)型プロセッサを含むことができる。
【００２８】
従来技術において知られているように、プロセッサ内には１以上の命令パイプラインがあるので、いろいろな命令が同時に処理される。命令群は、メモリから一般に検索され、１以上のパイプラインに配置される。命令群はプロセッサ内の１以上のパイプラインにロードされるので、ブランチは、既知のシステムによって検出され、フラッグが付けられる。フラッグが付けられたブランチの出力は、ブランチプレディクタによって予測されることができる。例えば、ブランチが或るブランチ予測データに基づいて行われるか否かは、以下に説明されるように決定される。もし、ブランチが行われるように予測されるなら、ブランチプレディクタはブランチの行き先を予測することもできる；行き先はブランチが行くアドレスとして表される。ブランチプレディクタは、ブランチが行われるか否か、及び同時にアドレスのようなブランチの行き先が何であるか予測することもできる。上述のように、ブランチがスタティックなブランチプレディクタおよびダイナミックなブランチプレディクタを含む、いろいろな異なる自動ブランチプレディクタによって行われる。もし、ブランチが行われないように予測されるなら、プロセッサは、ブランチが実行される必要がある後に直接命令以降特別なことを行わない。しかし、もし、ブランチが行われるように予測されるなら、プロセッサ又は自動ブランチプレディクタは、ブランチ予測に基づいて正しいアクションを起こすので、命令パイプラインにロードされる次の命令は予測された命令である。このように、プロセッサは、ブランチプレディクタによって行われる予測に従って、メモリないの命令を実行する。さて、本発明によるプログラム可能なブランチ予測システムが以下に説明される。
【００２９】
図２は、本発明によるプログラム可能なブランチ予測システムの第１の実施形態のブロック図である。コンピュータシステム３０は、図示されるように、プログラム可能なブランチ予測システム３２を含む。また、このコンピュータシステムは、プロセッサ３４も含む。上述のように、プロセッサは、図示されないメモリに記憶される命令を実行する。上述のように、本発明は特定型式のプロセッサに限定されず、ＣＩＳＣ型及びＲＩＳＣ型プロセッサを含むことができる。
【００３０】
プログラマブルブランチ予測システム３２は、自動ブランチプレディクタ（ＡＢＰ）３６及び予測データストレージシステム（Ｐ−ＳＴＯＲＥ）３８とを含んでいる。自動ブランチプレディクタ３６は、プログラマブルブランチ予測システム３２が後述のように任意の従来のブランチ予測システムを組み込み得るので、任意のタイプの従来の予測システムでよい。例えば、以前のブランチの履歴に基づいてブランチを予測するブランチ予測システムが用いられるのが好ましい。本書に記述した実施例については、１ビットカウンタ又は２ビットカウンタを有する前ブランチ履歴予測システムが、本発明の明確さのために記述されるが、任意の他のタイプの自動ブランチ予測システムが、用いられ得る。これは、プログラマブル予測システムは、Ｐ−ＳＴＯＲＥ内の予測データを変更し、任意のタイプの予測データを用いて動作するように変更され得るからである。ブランチの結果だけを予測する自動ブランチプレディクタが図示されているけれど、ブランチの結果と行き先アドレスの両方を予測するブランチプレディクタもまた用いられ得る。
【００３１】
自動ブランチ予測システム３６は、例えば、Ｐ−ＳＴＯＲＥ３８内に過去の履歴に関する予測データを記憶する。図３は、１ビットカウンタ付きの過去ブランチ履歴自動プレディクタのためのＰ−ＳＴＯＲＥ３８内に記憶された予測データの例を示している。この特定の例について、予測データストレージシステム３８は、各ブランチ毎に、ブランチ参照コラム４０と、対応する予測データコラム４２とを有する。異なるタイプのブランチ予測システムが用いられた場合、Ｐ−ＳＴＯＲＥ内のデータは違ったものになるであろう。ブランチ参照コラム４０は、ブランチ４４のアドレスを含んでいる。対応する予測コラム４２は特定のブランチの予測の結果をストアする。図示の例では、第１のブランチが採られるものとして予測され、第２のブランチは採られないものとして予測されている。
【００３２】
本発明は、予測データを参照するための特定の方法には限定されないが、２つの好ましい、参照方法が以下に記述される。その第１は、ブランチアドレスのようなブランチ参照が、Ｐ−ＳＴＯＲＥアドレスのようなＰ−ＳＴＯＲＥ参照にマップされる。そのマッピングは、直接マッピング、セット連想（アソシエーティブ）、又は連想（アソシエーティブ）マッピングのような、多数の既知の方法によって成される。予測データは、各々がＰ−ＳＴＯＲＥ参照を特定する複数の予測オペレーションにおいて直接参照される。上述のように、予測データのための参照は、アドレスであるのが好ましいが、その特定のブランチに関連するデータの他のピースであってもよい。その予測データには、如何にしてブランチ参照がＰ−ＳＴＯＲＥ内の参照に転送されるかを示すマッピング情報を含まれるのが好ましい。
【００３３】
再度、図２を参照すると、ブランチ命令又はブランチ命令への参照が、ＡＢＰ（自動ブランチ予測プレディクタ）に遭遇する場合、ＡＢＰは、上述のように、特定のブランチについての参照を決定して、次に、Ａ−ＡDDR ラインを通してＰ−ＳＴＯＲＥ３８内の正しい予測データにアクセスし、Ａ−ＲEAD ラインを通してＰ−ＳＴＯＲＥから予測データを読み出す。ＡＢＰは、その予測データをＡ−ＲESULT ラインを通してプロセッサに戻す。ＡＢＰは、Ｐ−ＳＴＯＲＥを更新することができてもよいし、更新できなくてもよい。例えば、第１のブランチについて、プロセッサにはブランチが採られるとして予測されることが知らされ、プロセッサは命令パイプライン中のブランチによってポイントされた命令をロードする。
【００３４】
本発明は、Ｐ−ＳＴＯＲＥ３８内に記憶された予測データを、自動ブランチプレディクタから独立して変更するシステム及び方法を提供する。本発明は、いつでも、予測データを変更し得る。上述の自動ブランチプレディクタは、Ｐ−ＳＴＯＲＥ内に記憶された予測データを用いているけれど、本発明は、プログラムの実行中に、予測オペレーションに応答して、予測データを発生及び／又は変更する。これらの予測オペレーションは、後述するようにコンパイラタイプのプログラムを走らせている別のコンピュータシステムによってプログラムの実行の前に発生されてもよい。例えば、プロシージャコール命令のためのＰ−ＳＴＯＲＥ内の予測データはプログラムが編集されるときに発生される。しかしながら、プログラムの実行前には、そのプロシージャコールのための実際の行き先アドレスは必ずしも知られていない。従って、自動ブランチプレディクタは、プロシージャコールの行き先を誤って予測する惧れがある。しかしながら、プログラムが実行され始めると、プロシージャコール行き先は、後述のように、予測オペレーションを用いて決定されて、正しい行き先が、プロシージャコール命令の実行の前に、Ｐ−ＳＴＯＲＥ内にロードされる。従って、実際のタスクスイッチ命令が実行されているとき、自動ブランチプレディクタは、本発明によって提供される更新された予測データに基づいて、プロシージャコールの行き先を正しく予測することになる。
【００３５】
本発明は、任意の自動ブランチ予測システムと協働して、後に詳細に記述する予測オペレーションに基づいて、予測データを修正する。本発明は、従来の自動ブランチ予測システムの精度を向上するが、本発明は予測データだけを更新し、変更し、アクセスするから、自動ブランチプレディクタの動作を邪魔することはない。図示の実施例において、Ｐ−ＳＴＯＲＥ内のデータを自動ブランチプレディクタとは独立に修正する能力は、Ｐ-ＷRITEライン４８及びＰ−ＡDDR ライン５０によって提供される。これらのラインは、Ｐ−ＳＴＯＲＥ３８内に記憶された予測データを更新するアップデータ５２に接続されている。アップデータ５２は、また、後述する一定の状況においてＰ−ＳＴＯＲＥから予測データを読み出すことによって、予測データを更新する。
【００３６】
アップデータは、プロセッサ３４と同じ命令を実行して、後述するように実行されるプログラムコードに挿入されてしまった命令オペレーションに反応する第２のプロセッサであってもよい。これらの予測オペレーションに応答して、Ｐ−ＳＴＯＲＥ内の予測データが変更、更新、アクセスされてもよい。アプデータにＰ−ＳＴＯＲＥ内の値を変更させる予測オペレーションの例については、後述する。
【００３７】
図４は、コンピュータのプログラマブルブランチ予測システム８０の第２の例のブロック図である。プログラマブルブランチ予測システムは、プロセッサ８２、命令を記憶するメモリ８４、自動ブランチプレディクタ８６及びＰ−ＳＴＯＲＥ８８を含んでもよい。この実施例は、前記の実施例と同じであるが、Ｐ−ＳＴＯＲＥは、プロセッサに接続されている。というのは、この実施例では、上述したように、アプデータは、そのプロセッサで働くプログラムであってもよいからである。実際、この実施例における更新は、プログラムコード内部に埋設された予測オペレーションとしてプロセッサにより実行されるプログラムの一部であってもよい。この実施例について、プロセッサの命令セットは、プロセッサが予測オペレーションの解釈の方法を理解してＰ−ＳＴＯＲＥの内容を更新できるように、変更されてもよい。
【００３８】
プロセッサ８２は、自動ブランチプレディクタを制御する同じＡ＿Ｒｅｓｕｌｔ及びＣ＿Ｒｅｓｕｌｔのラインを有しているが、自動ブランチプレディクタにＰ−ＳＴＯＲＥの内容をリセットさせるＧ＿Ｃｏｎｔｒｏｌラインを有してもよい。プロセッサは、Ｇ＿Ｃｏｎｔｒｏｌラインを介して自動ブランチプレディクタからの情報を要求してもよい。たとえば、過去の予測の正確性が、Ｇ＿Ｒｅｓｕｌｔラインを介してプロセッサに送られてもよい。
【００３９】
図示されるように、自動ブランチプレディクタ８６は、Ａ＿Ａｄｄｒラインを介して記憶システムから予測データを要求し、Ａ＿Ｒｅａｄラインを介してそれらの予測を受け取る。この実施例では、自動ブランチプレディクタは、ブランチがＡ＿Ｗｒｉｔｅラインを介して実行されてしまった後に、Ｐ−ＳＴＯＲＥ８８内にデータを書き込んでもよい。自動ブランチプレディクタがブランチを誤って予測すると、自動ブランチプレディクタは、記憶システムにおいてそのブランチの予測データを変更してもよい。自動ブランチプレディクタは、ブランチが実行されてしまった後、Ａ＿Ｗｒｉｔｅラインを用いて、Ｐ−ＳＴＯＲＥ内に予測データを書き込む。
【００４０】
上述したように、予測データ記憶装置内のデータを更新するシステムは、この実施例では、プロセッサに働くプログラムであってもよい。この実施例と最初の実施例の双方について、アップデータは、プログラムコードに埋設されている１つ又はそれ以上の予測オペレーションに応答して、Ｐ−ＳＴＯＲＥ内のデータを更新する。たとえば、プログラムコードが編集されるにつれて、プログラマブルブランチ予測プロセッサから完全に分離されているコンパイラが、或る条件及び命令のタイプについて編集されているコードをチェックして、予測オペレーションが編集された命令内に挿入されるか又はコードが作成されるようになっている。これらの予測オペレーションの発生及びプログラム内への挿入については、後述する。実行時に、挿入された予測オペレーションは、Ｐ−ＳＴＯＲＥ内のデータを更新させる。上述したように、一部のブランチは、編集時に未知の宛先を有するが、プログラムの実行が開始されると、明確な宛先を有するであろう、また、宛先は、プログラム実行中に変わってもよい。したがって、コンパイルコードに予測オペレーションがあってもよく、それにより、アップデータが特定のブランチを見てアドレスを決定し、記憶された予測データを更新する。
【００４１】
本発明と従来の命令セットとの互換性を確保するために、プログラマブルブランチ予測システムの予測オペレーションは、古いシステムの未使用の無オペレーションコードの言葉で表現されてもよい。したがって、本発明によるプログラマブルブランチプレディクタは、ブランチプレディクタ用に設計された現代のコンピュータアーキテクチャとともに使用されてもよいが、古いシステムとともに使用されてもよい。というのは、予測オペレーションは、古いシステムのどのような適当なオペレーションも妨害しないからである。
【００４２】
この第２の実施例では、記憶システムにおける予測データの更新は、プロセッサに働くプログラマブルブランチプレディクタにより達成されてもよい。そこで、予測データの更新が要求される場合には、その更新は、上述したようなＰＡｄｄｒ及びＰ＿Ｗｒｉｔｅラインを用いて行われてもよい。Ｐ−ＳＴＯＲＥ内の予測データは、Ｐ＿ＲＥＡＤラインを介してＰ−ＳＴＯＲＥから予測データを読み出すことにより更新されてもよい。以下、本発明の第３の実施例について述べる。
【００４３】
図５は、本発明によるプログラマブルブランチ予測システムの第３の実施例１００のブロック図である。プログラマブルブランチプレディクタのこの実施例は、プロセッサ１０２、メモリ１０４、自動ブランチプレディクタ１０６及びＰ−ＳＴＯＲＥ１０８を含んでもよい。これらのシステムは、上述したのでここでは説明しない。プログラマブルブランチ予測システム１００は、シンクロナイザ１１０を含んでもよい。シンクロナイザは、Ｐ＿Ｓｙｎｃラインを介してプロセッサを制御し、Ａ＿Ｓｙｎｃラインを介して自動ブランチプレディクタを制御してもよい。シンクロナイザは、Ｐ−ＳＴＯＲＥからの予測データが適当な時間に自動ブランチプレディクタにより受け取られる（すなわち、ブランチが遅過ぎて起きた後のブランチ予測データを受け取る）ことを確保するために、使用されてもよい。シンクロナイザシステムは、従来周知である。このプログラマブルブランチプレディクタは、上述したように、Ｐ＿Ａｃｃｅｓｓラインを介してＰ−ＳＴＯＲＥ内に記憶されたデータを更新してもよい。しかしながら、この実施例では、Ｐ＿Ａｃｃｅｓｓラインは、Ｐ＿Ｗｒｉｔｅ、Ｐ＿Ｒｅａｄ及びＰＡｄｄｒのラインとして動作してもよい。この実施例は、前述した実施例と同様に動作するので、ここでは説明しない。以下、プログラマブルブランチ予測システムの動作の例について説明する。
【００４４】
図６は、２ビットカウンタ予測システムのＰ−ＳＴＯＲＥの内容にかかる概略ダイヤグラムである。２ビットカウンタ自動ブランチ予測システムでは、２ビットは、過去のブランチ予測を追跡するのに使用される。図示のように、データストレージシステム１４０は、アドレスフィールド１４２、ビット１フィールド１４４、ビット０フィールド１４６を有している。ブランチが以前には行われず、あるいは少なくとも二回は行われていない場合には、アドレス３に示すように、両方のビットは０である。もしブランチが一度行われた場合には、ビット０は、アドレス０で示すようにビット０は ”１”である。もし、ブランチが２回行われるならば、任意のバイナリカウンタを有するようにビット１は、”１”であり、ビット０は、”０”である。この２ビットカウンタ自動ブランチプレディクタに対して、もし、ビット１が”１”であるならば、将来ブランチが行われると予測される。
従来のシステムでは、図７に示すように、カウンタの４つの可能な状態（00、01、10、11）が、カウンタ上において、使用されたブランチか、あるいは行われていないブランチの効果とともに示されている。図示のように、行われると予測されているブランチは、カウンタを１だけ増加させる。したがって、”１０”は”１１”となる。行われないと予想されているブランチは、カウンタを１だけ減少させる。この方法で、カウンタは、それぞれのブランチが実行されたのち１だけ増加または減少される。
【００４５】
図８は、２ビットカウンタにかかる本発明の効果を示すテーブルである。本発明は、カウンタを必ずしも増加または減少させるものではないが、カウンタをセットし、これによって、ブランチの次に実行される時間が予測される。これを達成するため、たとえば、カウンタのビット１は”１”にセットされ、ブランチの使用を予測させる、あるいは”０”にセットされ、ブランチが行われないことを予測させる。コンパイルされたコードに挿入される予測オペレーションのタイプの実例が以下に詳述される。一般に、予測オペレーションの挿入方法は、将来の予測ブランチ挙動を使用されるデータを計算する機会があるかどうかを決定するプログラムを解析し、Ｐ−ＳＴＯＲＥを更新し、あるいは変更するコンピュータコードに予測オペレーションを挿入し、これにしたがってブランチオペレーションを反応させることを含んでいる。 ここで、プログラムコードにこれらの予測オペレーションを挿入する方法の２つの例について説明する。
【００４６】
予測オペレーションは、Ｐ−ＳＴＯＲＥ内容を変更するための予測表現、あるいは予測パターンを使用する。予測表現の例は、以下の述べるように伝播値とすることができる。予測パターンの例は、以下にのべる指示変数とすることができる。予測表現は、ブランチの挙動が依存する表現を予測し、計算するのに使用する任意の表現とすることができる。同様に、予測パターンは、ブランチの挙動が依存する表現を予測し、計算するのに使用する予測のパターンである。予測表現あるいはパターンを特定することができる多くの種類の手順あるいは方法があり、これらの表現あるいは、パターンのすべてを本発明に従って使用することができ、予測オペレーションの挿入の機会を特定する。これらの異なるタイプの２つの例をここで以下に説明する。
【００４７】
図９は、コンピュータコードに予測オペレーションを挿入する本発明にしたがう方法１６０の第１の例にかかるフローチャートである。図９及び図１０に示される例に対して、予測オペレーションの挿入は、プログラム可能な予測システムのプロセッサによっても実行可能である。これはまた、完全に別個のコンピュータシステムによっても実行可能であり、このコンピュータシステムはプログラムコードにこれらの特別の予測オペレーションを発生し、挿入することができるコンパイラを実行する。これは、また、プログラムの実行よりもはやい時間でコンパイラを実行する同じプロセッサによって実行することもできる。したがって、プログラム可能な予測システムは、異なるコンピュータシステムによってプログラムコードに挿入されるプログラムコード含有予測オペレーションを実行することができる。この方法は、ステップ１６２及び１６４で始まり、コンパイルされたプログラムコードはさまざまな特性、たとえば、ブランチアドレス、変数をサーチするために解析される。ステップ１６６では、予測パターンの例である、プログラムコード内の任意の帰納変数が、公知のように特定される。次に、ステップ１６８では、表現が帰納変数に依存するブランチのために計算される。たとえば、ループが実行される回数を制御する変数は、インダクション変数であり、実行される実際の回数を計算することができる。次に、ステップ１７０では、予測オペレーションがプログラムコードに挿入され、ループを制御するブランチ命令のための予測データが、たとえば、更新され、ループの実行が予測される計算された回数を反映させる。ステップ１７２では、コンパイラは、解析すべきコンピュータコードにおけるさらなるブランチがあるかどうかを決定する。もし他のブランチが存在するならば、その後制御は、ステップ１６４に戻る。さらに、制御は、ステップ１６８に戻る。この理由は、単一の帰納変数あるいは、帰納変数の組が制御マルチブランチとすることができるからである。また、すべての帰納変数あるいはブランチが最初を特定することができる。コンピュータコードが完全に解析されたとき、方法は、ステップ１７４で終了する。
【００４８】
図１０は、予測オペレーションをコンピュータコードに挿入する、本発明によるメソッド２００の第２の例のフローチャートである。かかる方法はステップ２０２で始まり、ステップ２０４で、ブランチアドレス及び変数のような種々の指数部を探索するために、コンパイルされるプログラムコードを解析する。ステップ２０６では、いかなる伝播値も、当業者に周知であるとして識別されているプログラムコード内の予測式の例である。次いで、ステップ２０８では、式は、伝播値に依存しているブランチに関して計算される。例えば、if文に対応するブランチを制御するフラグが、例えば、伝播値であっても良く、その伝播値は計算され得る。次いで、ステップ２１０では、例えば、if文に対応するブランチ命令を制御するブランチ命令に関する予測データが、伝播値の計算された値を反映するために更新されるように、予測オペレーションをプログラムコードに挿入する。ステップ２１２では、コンパイラは、解析される必要があるコンピュータコードにこれ以上ブランチがあるか否か判断する。他のブランチがあるならば、次いで、制御はステップ２０４に戻され得る。更に、単一のプログラムされた値又はプログラムされた値のセットが多重ブランチを制御し、全てのプログラムされた値又はブランチが初めに識別され得るので、制御はステップ２０８に戻され得る。コンピュータコードが完全に解析されてしまっているならば、次いで、メソッドはステップ２１４で終わる。今、帰納変数及び伝播値に関する予測オペレーションをコンピュータコードのピース内に挿入する例が、記載されている。
【００４９】
この例に関して、シンプルＣソースコードループのフラグメントが、予測オペレーションなしでコンパイルされるのが示され、次いで、予測オペレーション、及び、予測オペレーションがシステムの予測正確性を有する効果で適所にコンパイルされる。
【００５０】
Ｃタイプソースコードのフラグメントのサンプルは、
i=0; flag=old; do  {
@1 flag=new;
@2
if(!flag)  {
@3 }
else@4
} while(++i<n);
であってよい。
【００５１】
ここで、＠１、＠２、＠３及び＠４はコードの任意フラグメントである。実際に、変数フラグは、コードの他の点で変更され得る。Ｃのようなソースコードのこのフラグメントは、そのようにみえるアセンブリコードにコンパイルされる：
mov           #0,i
mov           old,flag
TOP                    c@1
mov           new,flag
c@2
branch flag,FLGSKP
c@3
FLGSKP                 c@4
add           #1,i
branch i<n, TOP
【００５２】
ここで、ｃ＠１、ｃ＠２、ｃ＠３及びｃ＠４は、それぞれ＠１、＠２、＠３及び＠４に関するコンパイルされたコードであり、当業者に知られているコンパイルされたコードのラベルは、大文字である。変数「ｉ」は、当業者に知られている帰納値である。値「old 」及び「new 」は、当業者に知られている伝播値である。
【００５３】
コンパイルされたコードによって示されているように、ループが入力される初めてのときに、ブランチ予測システムは、前もってそのブランチを見ることができないので、ブランチが得られない誤予測であり得る。次いで、一旦ループが最後まで実行されるならば、在来のブランチ予測システムは、ブランチが別の時間を得ることがある誤予測である。対照的に、本発明は、以下に記載するように、１００％正確に、全てのブランチを正確に予測し得る。
【００５４】
本発明に関して、いくらかの予測オペレーションは、改訂コンパイルコードが以下のようになるようにコンパイルコードに加えられることができる：
mov           #0,i
repeat        n-1,BACK
mov           old,flag
predict       old,TSTFLG
TOP                    c@1
predict       new,TSTFLG
mov           new,flag
c@2
TSTFLG                 branch flag,FLGSKP
c@3
FLGSKP                 c@4
add           #1,i
BACK  branch i<n, TOP
【００５５】
ここで、２つのサンプル予測オペレーション「predict 」及び「repeat」が、本発明に従って、コンパイルコードに挿入される。予測オペレーションは、状態の予測値である第１の引数と、予測が適用されるブランチのアドレスである第２の引数とを有し得る。プログラムに基づいた予測オペレーションは、ブランチ予測システムがループを最初に誤予測しないように、予測データのその値を変更させる。
【００５６】
繰り返し予測オペレーションは、ブランチが選ばれる前に選ばれると予測される回数である第１独立変数を有してもよい。繰り返し予測オペレーションの第２独立変数は、予測を適用する分岐のアドレスである。繰り返し予測オペレーションは、予測データをＰ−ＳＴＯＲＥ内で改変し、ブランチ予測システムがループの終わりを間違って予測しないようにする。従って、繰り返し予測の予測オペレーションにより、この例についてプログラム可能な予測システムが100 ％正確である。適当なブランチを実行する前にＦＬＡＧとｎの値は分かるので、プログラム可能なブランチ予測システムは、これを利用して予測オペレーションを追加することができる。ここに示す例は簡単な例であり、多くの他の異なる予測オペレーション、例えばブランチの行き先を予測する「destination 」予測オペレーションをプログラムコード中に挿入することができる。この例について、本発明によるＰ−ＳＴＯＲＥ内の変化について記述する。
【００５７】
この例では、Ｐ−ＳＴＯＲＥは、上述したように２ビット飽和カウンターと、個々のブランチアドレスの大きいカウンタを記憶することができる。予測したデータストレージを図11に示す。図示するように、この例ではオリジナルのＣ状ソースコード内のイフステートメントは、ＴＳＴ−ＦＬＧラベルに対応した２ビットカウンターを有し、テーブル内で２ビットに分類される。より大きなカウントダウンカウンターがＢＡＣＫラベル（doループ用）に対応し、テーブルはＣに分類される。記憶装置システム内のこれら２つの予測データ（２ビットとＣ）の値は、プログラムコードの実行のいろいろのポイントで示され、予測オペレーションにより起こる変化がより明らかになる。
【００５８】
コンパイルされたプログラムコードの実行の初期に、イフステートメントとdo/whileループ用の２ビットカウンターは、両方とも「00」にセットされ、両ブランチ用のカウントダウンカウンターもまた「０」にセットされる。より複雑なプログラムでは、テーブルにより多くの記入がある。「repeat ｎ−１，ＢＡＣＫ」予測オペレーションを実行するとき、イフステートメント用の２ビットカウンターは影響されないが、do/whileループ用のＣカウンタは、ループを実行するのにブランチが選ばれる予測回数を表わす「ｎ−１」にセットされる。さらに、do/whileループ用の２ビットカウンタは、次にブランチが選ばれることを示す「10」又は他の値にセットされる。上述したように、実際のdoループを実行する前にＣカウンターと２ビットカウンターを「ｎ−１」と「10」にそれぞれセットすることは、ブランチプレディクタがdo/whileループの第１ブランチが選ばれないと誤って予測することを防止する。図示するループの作用はまた、２ビットカウンタを無視し、Ｃカウンタによることで予測することができる。Ｃカウンタがゼロに到達すると、次のブランチの実行は選ばれないと予測される。従って、どのブランチプレディクタもdo/whileループを前に見ていなくても、プログラム可能なブランチプレディクタは、do/whileループの第１ブランチが正確に予測されていることを保証できる。
【００５９】
「predict old,ＴＳＴＦＬＧ」予測オペレーションに遭遇すると、イフステートメントに対応するブランチ命令用２ビットカウンタは、「old 」が間違いと仮定すると、「０Ｘ」にリセットされ、do/whileループのカウンターは影響されない。「Ｘ」は、そのビットの値は重要でなく、どのような値でもよいことを示す。「predict new,ＴＳＴＦＬＧ」予測オペレーションが実行されると、イフステートメントに対応するブランチ命令に対応する２ビットカウンターは、「new 」
が正しいと仮定すると、例えば「１Ｘ」にリセットされ、予測されるブランチが選ばれるようにする。このイフステートメントに対応するブランチ用の２ビットカウンタの設定は、再度ブランチプレディクタがイフステートメントの第１ブランチを間違って予測することを防止する。do/whileループに対応するカウンタは影響されない。
【００６０】
「branch i＜ｎ，ＴＯＰ」ブランチオペレーションを実行するとき、do/whileループを実行するブランチ命令のＣカウンタと２ビットカウンタは、選ばれるブランチを予測するようセットされるので、コードのはじめに戻るブランチは正確に予測され、Ｃカウンタは「ｎ−２」に等しくなるように１ずつ減少する。do/whileブランチは多数回選ばれたので、do/whileループに対応するブランチ用の２ビットカウンタは、「11」の値を保持し続ける。イフステートメントに対応するブランチ用のカウンタは、影響されない。プログラムコードの実行は、do/whileループの終わりまでこのようにして継続する。
【００６１】
do/whileループの終わりで、Ｃカウンタが「０」に等しいとき、do/whileループに対応するブランチ用の２ビットカウンタは、プログラム可能な予測システムにより「00」にリセットされ、次にdo/whileループが実行されるとき、ブランチプレディクタは、ブランチが選ばれないと正確に予測する。従来のブランチプレディクタは、ブランチが選ばれると間違って予測することがあるのは、これらの従来のシステムは過去のブランチの作用を使用して予測データの値を更新し、将来の作用を予測するからである。この例に示すように、本発明のプログラム可能なブランチプレディクタは、１ビット又は２ビットカウンタ等の従来の自動ブランチプレディクタにあった間違った予測を減少させる。この例でのプログラム可能なブランチプレディクタの予測の正確さは100 ％である。ループの初めと終わりでブランチの作用を例えばブランチがdo/whileを実行する等と予測すると、ほとんどの従来のブランチプレディクタは少なくとも１回間違って予測するが、発明のプログラム可能なブランチプレディクタは、ループブランチの初めと終わりを正確に予測することができる。
【００６２】
プログラムコードに１つ以上の予測オペレーションを挿入して、自動ブランチ予測の性能を改良するシステム及び方法は、上述の様に、コンピュータシステムのプロセッサ内で実行することが出来るし、コンパイリングプログラムを実行している別のプロセッサによって実行することも出来る。１つ以上の予測オペレーションの発生及び挿入は、プログラマブルブランチプレディクタを有するシステムとは全く異なるコンピュータシステムのもとで実行することが出来る。更に、１つ以上の予測オペレーションの発生及び挿入は、ブランチ予測直前又はブランチ予測以前の或る時に行うことが出来る。よって、上述したプログラマブルブランチ予測システムは、１つ以上の予測オペレーションを発生又は挿入することは出来るが、このことは必然的では無い。従って、プログラマブルブランチ予測システムは、１つ以上のブランチ命令が事前に挿入されたプログラムコードを実行することができる。同様に、１つ以上の予測オペレーションを発生し且つ挿入するシステム及び方法は、上述のプログラマブルブランチ予測システムと独立して使用することが出来る。予測オペレーションの２つの特定の実施例が次に記述される。
【００６３】
発生され且つプログラムコードに挿入される予測オペレーションは、新たなデータP-STORE を書き込むことによって予測データを更新するか、新たなデータがP-STORE 内の或る位置から読み出されるべきであることを特定することの何れかによって予測データを更新することが出来る。データを書き込むこれらの予測オペレーションは、例えば、上述の予測及び繰り返し予測オペレーションとすることができる。しかしながら、予測データを書き込みためのこれらの予測オペレーションは、ブランチアドレスの様なブランチのための参照と更新されるべき予測データとを有する何れの予測オペレーションともすることが出来る。
【００６４】
予測データを書き込むためのこれらの予測オペレーションは１つ以上の予測オペレーションから構成することが出来るし、又は、別の基本命令とするとして表現することが出来る。例えば、“predict old，TSTFLG”予測オペレーション及び“predict new，TSTFLG”予測オペレーションは、予測オペレーションがP-STORE に影響するが、プログラマブルブランチ予測システムを有さないより古いシステムには影響を及ぼさない様な、基本命令とすることが実際出来る。これらの命令の両方は、P-STORE に書き込むことによって更新されるべきTSTFLGによって、ブランチ用の予測データを参照するようにする。更新された予測データはブランチが生じるか生じないかの予測を行うようにする。
【００６５】
予測オペレーションも２以上の基本命令として表現することができる。例えば、“predict old，TSTFLG”予測オペレーションは、
mov<data>,Ｅ
mov<address>，Ｆ
又は
output<data>，Ｇ
output<address>,Ｈ
【００６６】
ここで、Ｅ−Ｈは、命令がより古いシステム上で何もせず、より新しいシステム上では、その命令がP-STORE に影響する様に、選択される。この２つの命令の例だと、各対内の第１の命令がデータを更新するが、各対内の第２の命令がアドレスを更新する。同様に、予測オペレーションは３つの基本命令で実行することができるが、この基本命令の第１の命令が予測データを特定し、第２の命令がブランチ参照を特定し、第３の命令が予測データ上のオペレーションを達成する。
【００６７】
従って、予測オペレーションは如何なる数の基本命令からも構成することができる。本発明に従って命令を使用して読出予測オペレーションを表現する例が次に記述される。
【００６８】
読出予測オペレーションは、上述された予測オペレーションに類似しているが、予測オペレーションが予測データが記憶されている場所を特定するが、以下に述べる様に書込データを特定しない点で異なっている。書込予測オペレーションと同様に、読出オペレーションは１つ以上の基本命令に分解することが出来る。読出予測オペレーションの一例が以下に記述される。
【００６９】
上述の様に、タスクスイッチは、本発明に従うプログラマブルブランチ予測システムによって扱うことができるが、これは、タスクスイッチ以前のP-STORE の内容を記憶することができ、そしてタスクが再びスタートされた時に、特定のタスクに対する予測データをP-STORE に戻して記憶することが出来るためである。
タスクスイッチがコンパイラによって位置決めされる時、予測データが、P-STORE から読み出され、そして例えば、“movPSTPRE[0...n],SAVE[0..n]”基本命令、一連の命令、又はサブプログラムによって実行することが出来る例えば、“save<prediction data>予測オペレーションを使用して記憶される。従って、P-STORE からのデータの幾つか又は全てがSAVE位置に記憶される。その時、プログラムが、オリジナルタスクに切り換わって戻る時、SAVE位置内の予測データは、例えば、“movSAVE[0..n]，PSTORE[0..n]”基本命令、一連の命令、又はサブプログラムによって実行することが出来る例えば、“restore<prediction data>”予測操作を使用してP-STORE に戻して再記憶することが出来る。これらの読出予測オペレーションは、タスクスイッチが発生する時刻付近で発生される様に挿入することが出来る。
【００７０】
以上の説明は本発明の特定の実施の形態を参照して行われたが、この実施の形態の変形を、範囲が添付された請求の範囲によって規定される本発明の基本概念及び精神から離れること無しに行うことが出来ることは、当業者には理解されるであろう。
【図面の簡単な説明】
【００７１】
【図１】図１は、本発明によるプログラム可能なブランチ予測システムを組み込むことができる自動ブランチ予測のブロック図である。
【図２】図２は、本発明によるプログラム可能なブランチ予測システムの第１の実施形態のブロック図である。
【図３】図３は、図２の予測情報ストレージシステムに記憶されることができる予測データの概略図である。
【図４】図４は、本発明によるプログラム可能なブランチ予測システムの第２の実施形態のブロック図である。
【図５】図５は、本発明によるプログラム可能なブランチ予測システムの第３の実施形態のブロック図である。
【図６】図６は、２−ビットカウンタを用いることができる予測データストレージシステムの例を示す図である。
【図７】図７は、従来のブランチ予測システムによる、図６の２−ビットカウンタのマニピュレーションを示すテーブルである。
【図８】図８は、本発明によるプログラム可能なブランチ予測システムによる、図６の２−ビットカウンタのマニピュレーションの例を示すテーブルである。
【図９】図９は、予測オペレーションをコンピュータコードに挿入する、本発明による方法の第１の例のフローチャートである。
【図１０】図１０は、予測オペレーションをコンピュータコードに挿入する、本発明による方法の第２の例のフローチャートである。
【図１１】図１１は、分岐がプログラム可能なブランチ予測システムによって予測される場合、プログラムコードのフラグメントに対するサンプル予測データ値のテーブルである。
【符号の説明】
【００７２】
２０  コンピュータシステム
２２  ブランチプレディクタ
２４  プロセッサ
２６  メモリ
３０  コンピュータシステム
３２  ブランチ予測システム
３４  プロセッサ
３６  自動ブランチ予測システム（ＡＢＰ）
３８  予測データストレージシステム（Ｐ−ＳＴＯＲＥ）
４０  ブランチ参照コラム
４２  予測データコラム
４４  ブランチ
４８  Ｐ−ＷＲＩＴＥライン
５０  Ｐ−ＡＤＤＲライン
５２  アップデータ
８２  マイクロプロセッサ
８４  メモリ
８６  自動ブランチ予測システム（ＡＢＰ）
８８  予測データストレージシステム（Ｐ−ＳＴＯＲＥ）
１００  プログラマブルブランチ予測システム
１０２  マイクロプロセッサ
１０４  メモリ
１０６  自動ブランチ予測システム（ＡＢＰ）
１０８  予測データストレージシステム（Ｐ−ＳＴＯＲＥ）
１１０  シンクロナイザ
１４０  データストレージシステム
１４２  アドレスフィールド
１４４  ビット１フィールド
１４６  ビット０フィールド
【図１】
2007058875.tif 000003
【図２】
2007058875.tif 000004
【図３】
2007058875.tif 000005
【図４】
2007058875.tif 000006
【図５】
2007058875.tif 000007
【図６】
2007058875.tif 000008
【図７】
2007058875.tif 000009
【図８】
2007058875.tif 000010
【図９】
2007058875.tif 000011
【図１０】
2007058875.tif 000012
【図１１】
2007058875.tif 000013