図面 (/)

技術 複数の分岐予測方式のうちの選択された1つを使用して条件分岐命令を投機的に実行するためのプロセッサおよび方法

出願人 インターナショナル・ビジネス・マシーンズ・コーポレーション
発明者 ソウムミヤ・マリックアルバート・ジョン・ローパー
出願日 1997年4月23日 (23年7ヶ月経過) 出願番号 1997-106128
公開日 1998年5月22日 (22年6ヶ月経過) 公開番号 1998-133873
状態 特許登録済
技術分野 先行制御 機械語命令の実行
主要キーワード 取出ステージ 前方分岐 後方分岐 CRビット 分岐選択 命令識別子 論理機構 性能ペナルティ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1998年5月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (6)

課題

複数の分岐予測方式のうちの選択された1つを使用して、条件分岐命令投機的に実行するための改良されたプロセッサおよび方法を提供すること。

解決手段

選択された分岐予測方式を使用して分岐命令を投機的に実行するためのプロセッサおよび方法を開示する。プロセッサは、分岐命令を実行するための分岐処理ユニットを含む、命令を実行するための1つまたは複数の実行ユニットを有する。分岐処理ユニットには、複数の分岐予測方式のうちの1つを選択するための選択論理機構と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測ユニットが含まれる。分岐処理ユニットには、さらに、予測に基づいて条件分岐命令を投機的に実行するための実行機能が含まれる。予測の結果に基づいて、選択論理機構は、後続の条件分岐命令を予測するための分岐予測方式を選択し、その結果、分岐予測精度が高まる。一実施例では、複数の分岐予測方式に、静的分岐予測と動的分岐予測が含まれる。

概要

背景

現在のスーパースカラプロセッサには、通常は、命令を記憶するための命令キャッシュ、実行のため命令キャッシュから取り出された命令を一時的に記憶するための命令バッファ、順次命令を実行するための1つまたは複数の実行ユニット分岐命令を実行するための分岐処理ユニット(BPU)、命令バッファから特定の実行ユニットへ順次命令をディスパッチするためのディスパッチ・ユニット、および、実行を終了したが完了していない順次命令を一時的に記憶するための完了バッファが含まれる。

スーパースカラ・プロセッサの分岐処理ユニット(BPU)によって実行される分岐命令は、条件分岐命令または無条件分岐命令のいずれかに分類できる。無条件分岐命令とは、プログラム実行の流れを順次経路から指定された目標実行経路に変更する分岐命令であり、別の命令の実行によって供給される条件に依存しない分岐命令である。したがって、無条件分岐命令によって指定された分岐は、必ず採用される。対照的に、条件分岐命令は、プログラムフロー内で示された分岐が、別の命令の実行によって供給される条件に依存して採用される場合とされない場合がある分岐命令である。条件分岐命令は、さらに、条件分岐命令が分岐処理ユニット(BPU)によって評価される時に分岐が依存する条件が使用可能であるか否かに基づいて、解決済みまたは未解決のいずれかに分類できる。解決済み条件分岐命令が依存する条件は、実行の前に既知であるから、解決済み条件分岐命令は、通常は実行可能であり、目標実行経路内の命令は、順次命令の実行の際に遅延がほとんどまたは全くない状態で取り出すことができる。その一方で、未解決条件分岐命令は、その分岐が依存する条件が使用可能になり、分岐が解決されるまで順次命令の取出が遅延される場合には、かなりの性能ペナルティをもたらす可能性がある。

したがって、性能を強化するために、一部のプロセッサは、示された分岐が採用されるか否かを予測することによって、未解決の分岐命令を投機的に実行する。予測の結果を使用すると、フェッチャは、分岐の解決の前に投機実行経路内の命令を取り出せるようになり、これによって、分岐が予測通りに解決される場合に実行パイプラインでのストールがなくなる。

分岐予測機構を有するプロセッサでは、通常は、静的分岐予測方式または動的分岐予測方式のいずれかが使用される。静的分岐予測の最も単純な実施態様の1つが、後方分岐のすべてが採用され、前方分岐のすべてが採用されないと推測することである。静的分岐予測の別の実施態様では、あるプログラム内の分岐命令のそれぞれにYビットを関連付ける。このYビットは、プログラム・コンパイラプロファイリング動作に従って、その分岐が採用されると予測すべきか否かを分岐処理ユニット(BPU)に示すためにセットされる。したがって、コンパイル中にプログラムから収集された情報に基づいて、コンパイラが、投機的に実行する場合に各分岐を採用されると予測するか否かを指示する。静的分岐予測で使用されるソフトウェアに基づくアプローチとは異なって、動的分岐予測では、特定の分岐命令の解決を分岐履歴テーブル(BHT)に記録し、このテーブルに記憶された前の解決を利用して後続の分岐を予測する。

静的分岐予測と動的分岐予測どちらもが、かなり高い精度を有し、静的予測では平均60%から70%の間、動的予測では平均90%から97%の間の精度になるが、単一の分岐予測方式を排他的に使用すると、特定の命令シナリオが発生する時に深刻な性能ペナルティがもたらされる可能性がある。たとえば、前方分岐は採用されず、後方分岐は採用されると予測する静的分岐予測では、前方分岐が必ず採用される命令シナリオの場合に100%誤予測がもたらされる。この特定のタイプのコード・シーケンスは、動的分岐予測には理想的であるが、静的分岐予測は、他のコード・シーケンスについては動的分岐予測より優秀である。たとえば、交番カウント指標に基づいて採用される、ループに含まれる分岐は、動的分岐予測を利用する時には100%誤予測になるが、静的分岐予測を使用すると50%だけが誤予測になる。誤りを含むコードに起因する動的分岐予測に関する問題に加えて、プロセッサのコールドスタートの後には、使用可能な分岐履歴がないので、動的分岐予測は予測精度が低下する可能性がある。同様に、動的分岐予測を使用するプロセッサは、小さい分岐履歴テーブルしか維持せず、したがって、分岐命令エイリアスの可能性がある場合には、予測精度が低くなる可能性がある。

分岐予測の各タイプに固有欠陥対処するために、一部のプロセッサは、モード・ビットを備え、このモード・ビットの状態に依存して、分岐処理ユニット(BPU)が静的分岐予測機構または動的予測機構のいずれかを使用できるようになっている。しかし、このようなプロセッサでは、分岐処理ユニット(BPU)が、分岐命令の特定の実例についてどの分岐予測方式を使用するかを知的に選択することが許容されない。その結果、条件分岐命令を投機的に実行するための、複数の分岐予測方式のうちの1つを知的に選択するプロセッサおよび方法が必要である。

概要

複数の分岐予測方式のうちの選択された1つを使用して、条件分岐命令を投機的に実行するための改良されたプロセッサおよび方法を提供すること。

選択された分岐予測方式を使用して分岐命令を投機的に実行するためのプロセッサおよび方法を開示する。プロセッサは、分岐命令を実行するための分岐処理ユニットを含む、命令を実行するための1つまたは複数の実行ユニットを有する。分岐処理ユニットには、複数の分岐予測方式のうちの1つを選択するための選択論理機構と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測ユニットが含まれる。分岐処理ユニットには、さらに、予測に基づいて条件分岐命令を投機的に実行するための実行機能が含まれる。予測の結果に基づいて、選択論理機構は、後続の条件分岐命令を予測するための分岐予測方式を選択し、その結果、分岐予測精度が高まる。一実施例では、複数の分岐予測方式に、静的分岐予測と動的分岐予測が含まれる。

目的

本発明の目的は、データ処理のための改良された方法およびシステムを提供することである。

本発明のもう1つの目的は、分岐命令を実行するための改良されたプロセッサおよび方法を提供することである。

本発明のもう1つの目的は、複数の分岐予測方式のうちの選択された1つを使用して、条件分岐命令を投機的に実行するための改良されたプロセッサおよび方法を提供することである。

効果

実績

技術文献被引用数
5件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

命令を実行するための1つまたは複数の実行ユニットを含み、前記1つまたは複数の実行ユニットが、分岐命令を実行するための分岐処理ユニットを含み、前記分岐処理ユニットが、複数の分岐予測方式のうちの1つを選択するための選択手段と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測手段と、前記予測に従って前記分岐命令を投機的に実行するための手段とを含み、前記選択手段が、前記予測の結果に応答して後続の条件分岐命令の解決を予測するための分岐予測方式を選択することを特徴とするプロセッサ

請求項2

前記複数の分岐予測方式に、動的分岐予測が含まれることを特徴とする、請求項1のプロセッサ。

請求項3

前記動的分岐予測を使用する場合に分岐がとられるものと予測すべきか否かの表示を記憶する分岐履歴テーブルをさらに含むことを特徴とする、請求項2のプロセッサ。

請求項4

前記複数の分岐予測方式に、静的分岐予測が含まれることを特徴とする、請求項3のプロセッサ。

請求項5

前記選択手段が、動的分岐予測において誤予測が所定回数生じた場合に静的分岐予測を選択するための手段と、静的分岐予測において条件分岐命令の同じ解決が所定回数生じた場合に動的分岐予測を選択するための手段とを含むことを特徴とする、請求項4のプロセッサ。

請求項6

バスと、実行される命令を記憶する、前記バスに結合されたメモリと、前記バスを介して前記メモリに結合された、前記メモリから命令を取り出すためのフェッチャと、分岐命令を実行するための分岐処理ユニットを含む、取り出された命令を実行するための1つまたは複数の命令ユニットとを含み、前記分岐処理ユニットが、複数の分岐予測方式のうちの1つを選択するための選択手段と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測手段と、前記予測に従って前記分岐命令を投機的に実行するための手段とを含み、前記予測の結果に基づいて、前記選択手段が、分岐予測精度が高まるように後続の条件分岐命令の解決を予測するための分岐予測方式を選択することを特徴とするデータ処理システム

請求項7

前記複数の分岐選択方式に、動的分岐予測が含まれることを特徴とする、請求項6のデータ処理システム。

請求項8

前記動的分岐予測を使用する場合に分岐がとられるものと予測すべきか否かの表示を記憶する分岐履歴テーブルをさらに含むことを特徴とする、請求項7のデータ処理システム。

請求項9

前記複数の分岐予測方式に、静的分岐予測が含まれることを特徴とする、請求項8のデータ処理システム。

請求項10

前記選択手段が、動的分岐予測において誤予測が所定回数生じた場合に静的分岐予測を選択するための手段と、静的分岐予測において条件分岐命令の同じ解決が所定回数生じた場合に動的分岐予測を選択するための手段とを含むことを特徴とする、請求項9のデータ処理システム。

請求項11

条件分岐命令の解決を予測するため複数の分岐予測方式のうちの1つを選択するステップと、選択された分岐予測方式を使用して、採用または非採用として前記条件分岐命令の解決を予測するステップと、前記予測に従って前記条件分岐命令を投機的に実行するステップと、その後、採用または非採用として前記条件分岐命令を解決するステップと、前記条件分岐命令の解決に応答して、分岐予測の精度が高まるように、後続の条件分岐命令の解決の予測のために分岐予測方式を選択するため前記予測の結果を使用するステップとを含む、条件分岐命令を投機的に実行するための方法。

請求項12

前記複数の分岐予測方式に、動的分岐予測が含まれることを特徴とする、請求項11の方法。

請求項13

さらに、動的分岐予測を使用して、前記後続の条件分岐命令を採用または非採用として予測すべきか否かの表示を記憶するステップを含む、請求項12の方法。

請求項14

前記複数の分岐予測方式に、静的分岐予測が含まれることを特徴とする、請求項13の方法。

請求項15

前記複数の分岐方式のうちの1つを選択するステップが、動的分岐予測において誤予測が所定回数生じた場合に静的分岐予測を選択するステップと、静的分岐予測において分岐命令の同じ解決が所定回数生じた場合に動的分岐予測を選択するステップとを含むことを特徴とする、請求項14の方法。

技術分野

(15)前記複数の分岐方式のうちの1つを選択するステップが、動的分岐予測において誤予測所定回数生じた場合に静的分岐予測を選択するステップと、静的分岐予測において分岐命令の同じ解決が所定回数生じた場合に動的分岐予測を選択するステップとを含むことを特徴とする、上記(14)の方法。

背景技術

0001

本発明の技術分野は、全般的にはデータ処理の方法およびシステムに関し、具体的には、分岐命令を実行するためのプロセッサおよび方法に関する。さらに具体的には、本発明の技術分野は、複数の分岐予測方式のうちの選択された1つを使用して条件分岐命令投機実行するためのプロセッサおよび方法に関する。

0002

現在のスーパースカラ・プロセッサには、通常は、命令を記憶するための命令キャッシュ、実行のため命令キャッシュから取り出された命令を一時的に記憶するための命令バッファ、順次命令を実行するための1つまたは複数の実行ユニット、分岐命令を実行するための分岐処理ユニット(BPU)、命令バッファから特定の実行ユニットへ順次命令をディスパッチするためのディスパッチ・ユニット、および、実行を終了したが完了していない順次命令を一時的に記憶するための完了バッファが含まれる。

0003

スーパースカラ・プロセッサの分岐処理ユニット(BPU)によって実行される分岐命令は、条件分岐命令または無条件分岐命令のいずれかに分類できる。無条件分岐命令とは、プログラム実行の流れを順次経路から指定された目標実行経路に変更する分岐命令であり、別の命令の実行によって供給される条件に依存しない分岐命令である。したがって、無条件分岐命令によって指定された分岐は、必ず採用される。対照的に、条件分岐命令は、プログラムフロー内で示された分岐が、別の命令の実行によって供給される条件に依存して採用される場合とされない場合がある分岐命令である。条件分岐命令は、さらに、条件分岐命令が分岐処理ユニット(BPU)によって評価される時に分岐が依存する条件が使用可能であるか否かに基づいて、解決済みまたは未解決のいずれかに分類できる。解決済み条件分岐命令が依存する条件は、実行の前に既知であるから、解決済み条件分岐命令は、通常は実行可能であり、目標実行経路内の命令は、順次命令の実行の際に遅延がほとんどまたは全くない状態で取り出すことができる。その一方で、未解決条件分岐命令は、その分岐が依存する条件が使用可能になり、分岐が解決されるまで順次命令の取出が遅延される場合には、かなりの性能ペナルティをもたらす可能性がある。

0004

したがって、性能を強化するために、一部のプロセッサは、示された分岐が採用されるか否かを予測することによって、未解決の分岐命令を投機的に実行する。予測の結果を使用すると、フェッチャは、分岐の解決の前に投機実行経路内の命令を取り出せるようになり、これによって、分岐が予測通りに解決される場合に実行パイプラインでのストールがなくなる。

0005

分岐予測機構を有するプロセッサでは、通常は、静的分岐予測方式または動的分岐予測方式のいずれかが使用される。静的分岐予測の最も単純な実施態様の1つが、後方分岐のすべてが採用され、前方分岐のすべてが採用されないと推測することである。静的分岐予測の別の実施態様では、あるプログラム内の分岐命令のそれぞれにYビットを関連付ける。このYビットは、プログラム・コンパイラプロファイリング動作に従って、その分岐が採用されると予測すべきか否かを分岐処理ユニット(BPU)に示すためにセットされる。したがって、コンパイル中にプログラムから収集された情報に基づいて、コンパイラが、投機的に実行する場合に各分岐を採用されると予測するか否かを指示する。静的分岐予測で使用されるソフトウェアに基づくアプローチとは異なって、動的分岐予測では、特定の分岐命令の解決を分岐履歴テーブル(BHT)に記録し、このテーブルに記憶された前の解決を利用して後続の分岐を予測する。

0006

静的分岐予測と動的分岐予測どちらもが、かなり高い精度を有し、静的予測では平均60%から70%の間、動的予測では平均90%から97%の間の精度になるが、単一の分岐予測方式を排他的に使用すると、特定の命令シナリオが発生する時に深刻な性能ペナルティがもたらされる可能性がある。たとえば、前方分岐は採用されず、後方分岐は採用されると予測する静的分岐予測では、前方分岐が必ず採用される命令シナリオの場合に100%誤予測がもたらされる。この特定のタイプのコード・シーケンスは、動的分岐予測には理想的であるが、静的分岐予測は、他のコード・シーケンスについては動的分岐予測より優秀である。たとえば、交番カウント指標に基づいて採用される、ループに含まれる分岐は、動的分岐予測を利用する時には100%誤予測になるが、静的分岐予測を使用すると50%だけが誤予測になる。誤りを含むコードに起因する動的分岐予測に関する問題に加えて、プロセッサのコールドスタートの後には、使用可能な分岐履歴がないので、動的分岐予測は予測精度が低下する可能性がある。同様に、動的分岐予測を使用するプロセッサは、小さい分岐履歴テーブルしか維持せず、したがって、分岐命令エイリアスの可能性がある場合には、予測精度が低くなる可能性がある。

発明が解決しようとする課題

0007

分岐予測の各タイプに固有欠陥対処するために、一部のプロセッサは、モード・ビットを備え、このモード・ビットの状態に依存して、分岐処理ユニット(BPU)が静的分岐予測機構または動的予測機構のいずれかを使用できるようになっている。しかし、このようなプロセッサでは、分岐処理ユニット(BPU)が、分岐命令の特定の実例についてどの分岐予測方式を使用するかを知的に選択することが許容されない。その結果、条件分岐命令を投機的に実行するための、複数の分岐予測方式のうちの1つを知的に選択するプロセッサおよび方法が必要である。

0008

本発明の目的は、データ処理のための改良された方法およびシステムを提供することである。

0009

本発明のもう1つの目的は、分岐命令を実行するための改良されたプロセッサおよび方法を提供することである。

課題を解決するための手段

0010

本発明のもう1つの目的は、複数の分岐予測方式のうちの選択された1つを使用して、条件分岐命令を投機的に実行するための改良されたプロセッサおよび方法を提供することである。

0011

前述の目的は、下記に従って達成される。選択された分岐予測方式を使用して分岐命令を投機的に実行するためのプロセッサおよび方法を開示する。プロセッサは、分岐命令を実行するための分岐処理ユニットを含む、命令を実行するための1つまたは複数の実行ユニットを有する。分岐処理ユニットには、複数の分岐予測方式のうちの1つを選択するための選択論理機構と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測ユニットが含まれる。分岐処理ユニットには、さらに、予測に基づいて条件分岐命令を投機的に実行するための実行機能が含まれる。予測の結果に基づいて、選択論理機構は、後続の条件分岐命令を予測するための分岐予測方式を選択し、その結果、分岐予測精度が高まる。一実施例では、複数の分岐予測方式に、静的分岐予測と動的分岐予測が含まれる。

0012

ここで図面、具体的には図1を参照すると、請求項に記載された本発明による情報処理のためのプロセッサ10の実施例のブロック図が示されている。図示の実施例では、プロセッサ10に、単一の集積回路スーパースカラ・マイクロプロセッサが含まれる。したがって、下でさらに説明するように、プロセッサ10には、さまざまな実行ユニット、レジスタ、バッファ、メモリおよび他の機能ユニットが含まれ、これらのすべてが集積回路によって形成される。プロセッサ10は、縮小命令セットコンピュータRISC技法に従って動作する、IBM Microelectronics社が販売するPowerPC(商標系列のマイクロプロセッサの1つであることが好ましいが、当業者であれば、他の適当なプロセッサを使用できることを諒解するであろう。図1からわかるように、プロセッサ10は、プロセッサ10内のバスインターフェース・ユニット(BIU)12を介してシステム・バス11に結合される。BIU12は、プロセッサ10と、主記憶(図示せず)など、システム・バス11に結合された他のデバイスとの間の情報の転送を制御する。プロセッサ10、システム・バス11および、システム・バス11に結合された他のデバイスが、データ処理システムを形成する。

0013

BIU12は、プロセッサ10内の命令キャッシュ14およびデータ・キャッシュ16に結合される。命令キャッシュ14やデータ・キャッシュ16などの高速キャッシュを用いると、プロセッサ10が、前に主記憶から命令キャッシュ14またはデータ・キャッシュ16に転送されたデータまたは命令のサブセットへの比較的高速のアクセス時間を達成でき、したがって、データ処理システムの動作速度が向上する。命令キャッシュ14は、さらに、シーケンシャル・フェッチャ17に結合され、このシーケンシャル・フェッチャ17は、各サイクル中に命令キャッシュ14から実行のため命令を取り出す。シーケンシャル・フェッチャ17は、命令キャッシュ14から取り出した命令を分岐処理ユニット(BPU)18と命令キュー19の両方に伝送し、これらは、その命令が分岐命令か順次命令かを判定するために命令を復号する。分岐命令は、実行のためBPU18に保存され、命令キュー19から取り消される。その一方で、順次命令は、BPU18から取り消され、プロセッサ10内の他の実行回路による後続の実行のため命令キュー19内に記憶される。

0014

図示の実施例では、BPU18に加えて、プロセッサ10の実行回路に、順次命令用の複数の実行ユニットが含まれ、これには、固定小数点ユニット(FXU)22、ロード/ストア・ユニット(LSU)28および浮動小数点ユニットFPU)30が含まれる。コンピュータ技術の技量を有する者には周知のとおり、FXU22、LSU28およびFPU30のそれぞれは、通常は、各プロセッサ・サイクル中に特定のタイプの順次命令のうちの1つまたは複数の命令を実行する。たとえば、FXU22は、加算、減算、AND、OR、XORなどの固定小数点の算術演算および論理演算を実行し、指定された汎用レジスタ(GPR)32またはGPRリネーム・バッファ33から受け取るソースオペランドを使用する。固定小数点命令の実行の後に、FXU22は、命令のデータ結果をGPRリネーム・バッファ33に出力し、GPRリネーム・バッファ33は、結果データをGPRリネーム・バッファ33からGPR32のうちの1つまたは複数に転送することによって命令を完了するまでその結果データの一時的な記憶を提供する。対照的に、FPU30は、通常は、浮動小数点レジスタ(FPR)36またはFPRリネーム・バッファ37から受け取るソース・オペランドに対して、浮動小数点の乗除算などの単精度および倍精度の浮動小数点の算術演算および論理演算を実行する。FPU30は、浮動小数点命令の実行から生じるデータを、選択されたFPRリネーム・バッファ37に出力し、このFPRリネーム・バッファ37は、結果データをFPRリネーム・バッファ37から選択されたFPR36に転送することによって命令を完了するまで結果データを一時的に記憶する。名前から示されるように、LSU28は、通常は、メモリ(すなわち、データ・キャッシュ16または主記憶)から選択されたGPR32またはFPR36にデータをロードするか、GPR32、GPRリネーム・バッファ33、FPR36またはFPRリネーム・バッファ37のうちの選択された1つからメモリへデータをストアする、浮動小数点命令および固定小数点命令を実行する。

0015

プロセッサ10は、命令のパイプライン化順番外実行の両方を使用して、そのスーパースカラ・アーキテクチャの性能をさらに高める。したがって、命令は、データ依存性が観察される限り、FXU22、LSU28およびFPU30によって任意の順序で適宜実行できる。さらに、命令は、一連パイプラインステージで、FXU22、LSU28およびFPU30のそれぞれによって処理される。高性能プロセッサの多数で典型的であるように、各命令は、5つの別個のパイプライン・ステージ、すなわち、取出、復号/ディスパッチ、実行、終了および完了の各ステージで処理される。

0016

取出ステージでは、シーケンシャル・フェッチャ17が、命令キャッシュ14から、1つまたは複数のメモリ・アドレスに関連する1つまたは複数の命令を取り出す。上で述べたように、命令キャッシュ14から取り出される順次命令は、シーケンシャル・フェッチャ17によって命令キュー19に格納され、分岐命令は、順次命令ストリームから除去(fold out)される。図2に関して下で説明するように、分岐命令はBPU18によって実行されるが、BPU18には、複数の分岐予測方式のうちの選択された1つを使用してBPU18が未解決の条件分岐命令を投機的に実行できるようにする新規の分岐予測機構が含まれる。

0017

復号/ディスパッチ・ステージ中には、ディスパッチ・ユニット20が、命令キュー19からの1つまたは複数の命令を復号し、FXU22、LSU28およびFPU30にディスパッチする。また、復号/ディスパッチ・ステージ中に、ディスパッチ・ユニット20は、ディスパッチされた命令のそれぞれの結果データのために、GPRリネーム・バッファ33またはFPRリネーム・バッファ37内のリネーム・バッファを割り振る。図示の実施例によれば、ディスパッチ・ユニット20によってディスパッチされる命令は、完了ユニット40内の完了バッファにも渡される。プロセッサ10は、独自の命令識別子を使用して、順番外実行中にディスパッチされた命令のプログラム順を追跡する。

0018

実行ステージ中には、指示された動作のオペランドおよび実行資源が使用可能になった時に、FXU22、LSU28およびFPU30が、ディスパッチ・ユニット20から受け取った順次命令を適宜実行する。FXU22、LSU28およびFPU30のそれぞれは、オペランドまたは実行資源が使用可能になるまでその実行ユニットにディスパッチされた命令を記憶するリザベーションステーションを備えることが好ましい。命令の実行が終了した後に、FXU22、LSU28またはFPU30は、その命令のデータ結果を、命令のタイプに応じてGPRリネーム・バッファ33またはFPRリネーム・バッファ37のいずれかに格納する。その後、FXU22、LSU28またはFPU30は、完了ユニット40の完了バッファに記憶された命令のどれが実行を終了したかを完了ユニット40に通知する。最後に、命令は、完了ユニット40が命令のデータ結果をプログラム順でGPRリネーム・バッファ33からGPR32へまたはFPRリネーム・バッファ37からFPR36へ転送することによって完了する。

0019

ここで図2および図5を参照すると、プロセッサ10のBPU18を示す詳細なブロック図と、BPU18内の分岐命令の実行の詳細を示す流れ図が示されている。まず図5を参照すると、この処理は、ブロック200から始まり、その後、ブロック202およびブロック204に進む。ブロック202およびブロック204には、シーケンシャル・フェッチャ17が、命令キャッシュ14から順次命令の次の組を取り出すことと、取り出された命令をBPU18および命令キュー19に送ることが示されている。図2に示されるように、BPU18は、各サイクルに2つまでの命令をシーケンシャル・フェッチャ17から受け取り命令レジスタ(IR)50および52内に命令を記憶する。取り出された命令をIR50および52内に記憶することが、図5のブロック206に示される、分岐復号ユニット54による命令復号のトリガになる。

0020

さらに図5を参照すると、ブロック208でIR50および52のいずれかに記憶された命令が非分岐命令であると判定されたことに応答して、ブロック210に示されるように、その命令は単に破棄される。その後、処理は、ブロック210からブロック270に進み、破棄された命令の処理が終了する。その一方で、ブロック208でIR50および52のいずれかに記憶された命令が分岐命令であると判定される場合、ブロック220で、その命令が条件分岐命令であるか否かの判定を行う。無条件分岐命令は、単に分岐選択ユニット56に渡され、この分岐選択ユニット56が、目標命令有効アドレス(EA)を計算する。ブロック222に示されるように、分岐選択ユニット56は、その後、EAを命令キャッシュ14に送って、目標アドレスにある順次命令の取出を開始する。

0021

ブロック220に戻って、取り出された命令が分岐命令であることが分岐復号ユニット54のうちの1つによって判定される場合、処理はブロック230に進み、その分岐が依存する条件レジスタ(CR)のフィールドが進行中の命令すなわち取り出されたがまだ完了していない命令の目標であるか否かが判定される。ブロック230に示された判定を行うために、命令が分岐選択ユニット56に渡され、分岐選択ユニット56は、分岐が依存するCRフィールドの表示を探索論理機構58および60に送る。分岐選択ユニット56から受け取ったCRフィールド識別子を使用して、探索論理機構58は、命令キュー19内の命令を検査して、分岐が依存するCRフィールドが命令キュー19内の1つまたは複数の命令の目標であるかどうかを判定する。これと同時に、問題のCRフィールドが、ディスパッチされたが完了ユニット40の完了バッファ62内に格納されている未完了の命令の目標であるかどうかの判定が、探索論理機構60によって行われる。問題のCRフィールドが、進行中の命令の目標ではない場合、その分岐命令は、すでに解決されており、分岐が依存するCRフィールドは、CRの時間的状態を記憶する図示されていないCR特殊目的レジスタ(SPR)内に存在する。したがって、処理は、ブロック230からブロック232に進み、分岐決定ユニット64が、CR SPR内の問題のCRフィールドを調べ、可能であれば条件分岐を解決する。その後、分岐命令の解決が、分岐選択ユニット56に供給される。その後、ブロック222に示されるように、分岐選択ユニット56が、目標命令のEAを計算し、そのEAを命令キャッシュ14に送る。

0022

ここでブロック230に戻って、問題のCRフィールドが進行中の命令の目標であることが探索論理機構58または60によって判定された場合、処理はブロック240に進み、その命令によって供給されるCRビットが使用可能であるか否かの判定が、探索論理機構60によって行われる。ある命令によって供給されるCRビットは、その命令が完了し、その命令の実行によって生成されたCRビットが完了バッファ62に格納されている場合に使用可能である。CRビットが使用可能な場合には、処理はブロック240からブロック242に進み、分岐決定ユニット64が、命令に関連するCRビットを検査して、分岐を解決する。さらに、分岐決定ユニット64は、条件分岐命令の解決を分岐選択ユニット56に供給し、分岐選択ユニット56は、ブロック222に示されるように、次に取り出す命令のEAを計算し、そのEAを命令キャッシュ14に転送する。

0023

ブロック240に戻って、CRビットがまだ使用可能でない(すなわち、命令がまだディスパッチされていないか、実行を終了していない)場合には、処理はブロック250ないしブロック260に進み、未解決条件分岐命令の投機実行を行う。したがって、分岐決定ユニット64は、CRビットが使用可能でないことを選択論理機構66に通知し、その命令を予測によって投機的に実行しなければならないことを示す。次に、ブロック250に示されるように、選択論理機構66は、分岐予測方式を選択する。本発明の重要な態様に従い、また、図3および図4に関連して詳細に説明するように、選択論理機構66は、分岐履歴テーブル(BHT)68に格納された過去の予測の結果に基づいて分岐予測方式を選択する。したがって、複数の分岐予測モードをサポートする従来技術のプロセッサとは異なり、図1に示された実施例では、過去の予測の結果に基づいて知的かつ動的に最適分岐予測方式が選択される。ブロック252に示されるように、選択された分岐予測方式を使用して、分岐決定ユニット64は、分岐の採否を予測し、その予測を分岐選択ユニット56に示す。その後、ブロック254に示されるように、分岐選択ユニット56は、目標命令のEAを計算し、命令キャッシュ14に送る。

0024

図5に示された処理は、ブロック254からブロック256に進み、条件分岐命令が予測通りに解決されたかどうかが判定される。ブロック256に示された判定は、分岐決定ユニット64によって行われ、この分岐決定ユニット64は、関連する命令の終了の後に、分岐が依存するCRビットを探索論理機構60から受け取る。分岐が誤予測されたことが分岐決定ユニット64によって判定される場合、処理はブロック258に進み、分岐決定ユニット64が、命令キュー19とFXU22、LSU28およびFPU30から、誤予測された分岐命令の投機実行経路内の命令を取り消す。その後、処理はブロック260に進む。当業者であれば、複数レベル投機を許容するプロセッサ実施態様の場合、すべての投機命令を取り消す必要はなく、分岐の誤予測に応答して取り出された投機命令だけを取り消せばよいことを諒解するであろう。ブロック256に戻って、分岐が正しく予測されたとブロック256で判定される場合、これに応答して、処理はブロック256からブロック260に進む。ブロック260では、必要があれば選択論理機構66がBHT68を更新して、条件分岐命令の後続の投機実行のために適当な分岐予測方式が選択されるようにする。その後、この処理はブロック270で終了する。

0025

ここで図3を参照すると、BPU18のBHT68を表す図が示されている。図からわかるように、BHT68には、256個の項目80を含むテーブルが含まれ、項目80のそれぞれは、指標82を使用してアクセスされる。図示の実施例では、指標82のそれぞれに、分岐命令アドレス最下位8ビットが含まれる。したがって、たとえば、00hで終わるアドレスを有する命令の分岐履歴は、最初の項目80に格納され、01hで終わるアドレスを有する分岐命令は、第2の項目に格納され、以下同様である。図からわかるように、各項目80には、3ビットが含まれ、これによって、後続の条件分岐命令に関する7つの予測状態(8番目の可能な状態は未使用)のうちの1つが指定される。従来の分岐履歴テーブルと同様に、BHT68の項目80内に格納される予測状態は、その分岐命令の後続の実行をより正確に予測するために、関連する分岐の採否の解決の後に更新される。

0026

ここで図4を参照すると、分岐予測方式の選択に使用される状態機械の実施例が示されている。状態機械88には、4つの動的予測状態90、92、94および96と、3つの静的予測状態98、100および102を含む7つの状態が含まれる。図からわかるように、予測状態90ないし102のそれぞれは、BHT68の各項目80の7つの可能な設定のうちの1つに対応する。

0027

まず、静的予測状態100を参照すると、予測される分岐命令が、「000」に設定されたBHT68の項目80にマッピングされる場合、分岐が採用されるか否かの予測には、静的分岐予測が使用される。この分岐が採用されて解決された場合(これを略語RTで示す)、BHT68の項目80は、静的予測状態102に示されるように「001」に更新される。状態機械88は、分岐が正しく予測されたか否かに無関係に、この解決RTに応答して静的予測状態100から静的予測状態102に進行することに留意することが重要である。その条件分岐命令が次に予測される時には、静的予測状態102によって指定されるように、やはり静的分岐予測が使用される。その分岐がやはり採用されて解決された場合、BHT68の項目80は、「010」に更新され、動的予測状態90によって示されるように、次の予測には動的分岐予測が使用されることが示される。

0028

その後、状態機械88は、後続の分岐予測がRTとして解決される限り、動的予測状態90にとどまる。動的予測状態90のところに示されている「PT」は、分岐予測が採用であること、すなわち分岐がとられるものと予測されることを表している。しかし、分岐が採用されずに解決されると(これを略語RNTで示す)、これに応答して、状態機械88は、動的予測状態90から動的予測状態92に進み、BHT68の項目80は、「011」に更新される。項目80が、動的予測状態92に対応する「011」に設定される場合、項目80にマッピングされる分岐命令は、状態90と同じく、採用されるものとして予測される。RTとしての分岐の解決(すなわち正しい予測)に応答して、状態機械88は、すでに説明した動的予測状態90に戻る。しかし、分岐の解決がRNTの場合は、状態機械88は、動的予測状態92から静的予測状態100に戻る。

0029

もう一度静的予測状態100を参照すると、分岐命令がRNTとして解決された場合には、状態機械88は、静的予測状態100から静的予測状態98に進み、項目80は「111」に更新される。この分岐命令の次の出現がRTとして解決された場合には、状態機械88は、静的予測状態98からすでに説明した静的予測状態100に戻る。その一方で、分岐命令がRNTとして解決された場合には、状態機械88は、静的予測状態98から動的予測状態96に進み、項目80は「110」に更新される。

0030

条件分岐は、状態機械88が動的予測状態96であり、項目80がそれに対応して「110」に設定されている間は非採用として予測される(これを略語PNTで示す)。予測された条件分岐が、RNTとして解決された場合、状態機械88は、動的予測状態96にとどまる。その代わりに、予測された条件分岐が、RTとして解決された場合、状態機械88は、動的予測状態94に進む。これは、BHT設定「101」に対応する。状態機械88が動的予測状態94である時には、状態96と同じく、条件分岐は非採用として予測される(PNT)。動的予測状態94でRNTと予測された分岐がRNTとして解決された場合、状態機械88は、すでに説明した動的予測状態96に戻る。しかし、この分岐がRTとして解決された場合には、処理は、すでに説明した静的予測状態100に戻る。

0031

図4の前述の説明からわかるように、状態機械88が、静的予測状態98ないし102のうちのどれかである間は、分岐解決の方向によって、予測機構の次の状態が決定される。分岐が2回連続してRTまたはRNTとして解決された後には、動的分岐予測方式が使用される。同様に、状態機械88が、動的予測状態90または96のいずれかである場合に、2回連続して分岐誤予測が発生すると、分岐は、静的分岐予測を使用して予測される。図4で状態機械88の実施例を示したが、当業者であれば、分岐履歴に基づいて分岐予測方式を知的に選択できるようにする、他の状態機械を実施できることを諒解するであろう。さらに、当業者であれば、複数のタイプの静的予測と動的予測を使用できることを諒解するであろう。たとえば、BPU18は、示された分岐が前方分岐か後方分岐かに基づいて分岐命令の解決を予測する単純な静的分岐予測方式を実施することができる。その代わりに、プログラムのコンパイル中に学習した情報に基づいて分岐命令を予測する、より複雑な静的分岐予測方式を使用することができる。

0032

実施例を具体的に図示し、説明してきたが、当業者であれば、実施例の趣旨および範囲から逸脱することなく、形態と詳細においてさまざまな変更を行えることを理解するであろう。

0033

まとめとして、本発明の構成に関して以下の事項を開示する。

図面の簡単な説明

0034

(1)命令を実行するための1つまたは複数の実行ユニットを含み、前記1つまたは複数の実行ユニットが、分岐命令を実行するための分岐処理ユニットを含み、前記分岐処理ユニットが、複数の分岐予測方式のうちの1つを選択するための選択手段と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測手段と、前記予測に従って前記分岐命令を投機的に実行するための手段とを含み、前記選択手段が、前記予測の結果に応答して後続の条件分岐命令の解決を予測するための分岐予測方式を選択することを特徴とするプロセッサ。
(2)前記複数の分岐予測方式に、動的分岐予測が含まれることを特徴とする、上記(1)のプロセッサ。
(3)前記動的分岐予測を使用する場合に分岐がとられるものと予測すべきか否かの表示を記憶する分岐履歴テーブルをさらに含むことを特徴とする、上記(2)のプロセッサ。
(4)前記複数の分岐予測方式に、静的分岐予測が含まれることを特徴とする、上記(3)のプロセッサ。
(5)前記選択手段が、動的分岐予測において誤予測が所定回数生じた場合に静的分岐予測を選択するための手段と、静的分岐予測において条件分岐命令の同じ解決が所定回数生じた場合に動的分岐予測を選択するための手段とを含むことを特徴とする、上記(4)のプロセッサ。
(6)バスと、実行される命令を記憶する、前記バスに結合されたメモリと、前記バスを介して前記メモリに結合された、前記メモリから命令を取り出すためのフェッチャと、分岐命令を実行するための分岐処理ユニットを含む、取り出された命令を実行するための1つまたは複数の命令ユニットとを含み、前記分岐処理ユニットが、複数の分岐予測方式のうちの1つを選択するための選択手段と、選択された分岐予測方式を使用して条件分岐命令の解決を予測するための分岐予測手段と、前記予測に従って前記分岐命令を投機的に実行するための手段とを含み、前記予測の結果に基づいて、前記選択手段が、分岐予測精度が高まるように後続の条件分岐命令の解決を予測するための分岐予測方式を選択することを特徴とするデータ処理システム。
(7)前記複数の分岐選択方式に、動的分岐予測が含まれることを特徴とする、上記(6)のデータ処理システム。
(8)前記動的分岐予測を使用する場合に分岐がとられるものと予測すべきか否かの表示を記憶する分岐履歴テーブルをさらに含むことを特徴とする、上記(7)のデータ処理システム。
(9)前記複数の分岐予測方式に、静的分岐予測が含まれることを特徴とする、上記(8)のデータ処理システム。
(10)前記選択手段が、動的分岐予測において誤予測が所定回数生じた場合に静的分岐予測を選択するための手段と、静的分岐予測において条件分岐命令の同じ解決が所定回数生じた場合に動的分岐予測を選択するための手段とを含むことを特徴とする、上記(9)のデータ処理システム。
(11)条件分岐命令の解決を予測するため複数の分岐予測方式のうちの1つを選択するステップと、選択された分岐予測方式を使用して、採用または非採用として前記条件分岐命令の解決を予測するステップと、前記予測に従って前記条件分岐命令を投機的に実行するステップと、その後、採用または非採用として前記条件分岐命令を解決するステップと、前記条件分岐命令の解決に応答して、分岐予測の精度が高まるように、後続の条件分岐命令の解決の予測のために分岐予測方式を選択するため前記予測の結果を使用するステップとを含む、条件分岐命令を投機的に実行するための方法。
(12)前記複数の分岐予測方式に、動的分岐予測が含まれることを特徴とする、上記(11)の方法。
(13)さらに、動的分岐予測を使用して、前記後続の条件分岐命令を採用または非採用として予測すべきか否かの表示を記憶するステップを含む、上記(12)の方法。
(14)前記複数の分岐予測方式に、静的分岐予測が含まれることを特徴とする、上記(13)の方法。

--

0035

図1分岐処理ユニットを含むプロセッサの実施例を示すブロック図である。
図2図1に示された分岐処理ユニットの詳細なブロック図である。
図3図2に示された分岐処理ユニット(BPU)の分岐履歴テーブル(BHT)を表す図である。
図4図2に示された分岐処理ユニットによって、投機的に実行される条件分岐命令の解決の予測に使用される分岐予測方式を選択するのに使用される方法の状態図である。
図5図1に示された実施例による、分岐命令を実行する方法の流れ図である。

0036

18分岐処理ユニット(BPU)
19命令キュー
50命令レジスタ(IR)
52 命令レジスタ(IR)
54分岐復号ユニット
56分岐選択ユニット
58 探索論理機構
60 探索論理機構
64 分岐決定ユニット
66選択論理機構
68分岐履歴テーブル(BHT)

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ