米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 富士通株式会社

発明の名称 分岐予測装置、プロセッサ、及び分岐予測方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2003−5956(P2003−5956A)
公開日 平成15年1月10日(2003.1.10)
出願番号 特願2001−186473(P2001−186473)
出願日 平成13年6月20日(2001.6.20)
代理人 【識別番号】100070150
【弁理士】
【氏名又は名称】伊東 忠彦
【テーマコード(参考)】
5B013
【Fターム(参考)】
5B013 BB01 BB02 
発明者 多湖 真一郎 / 山名 智尋 / 竹部 好正
要約 課題
本発明は、PHTを使用する分岐予測方式において、可能な限り小さなメモリ容量を使用しながらエントリ干渉を回避して分岐予測の精度を向上させた分岐予測方式を提供することを目的とする。

解決手段
分岐予測装置は、過去の分岐命令の履歴を保持する履歴レジスタと、履歴レジスタが保持する履歴と命令アドレスとから第1のインデックスを生成するインデックス生成回路と、各第1のインデックスに対して命令アドレスの一部であるタグと分岐のし易さを示す第1の値とを格納する履歴テーブルと、命令アドレスの少なくとも一部を第2のインデックスとして命令アドレスが示す命令の分岐先アドレスと分岐のし易さを示す第2の値とを格納する分岐先バッファと、第1の値及び該第2の値の何れかを選択することで分岐予測を行う選択ユニットを含む。
特許請求の範囲
【請求項1】過去の分岐命令の履歴を保持する履歴レジスタと、該履歴レジスタが保持する該履歴と命令アドレスとから第1のインデックスを生成するインデックス生成回路と、各第1のインデックスに対して該命令アドレスの一部であるタグと分岐のし易さを示す第1の値とを格納する履歴テーブルと、該命令アドレスの少なくとも一部を第2のインデックスとして該命令アドレスが示す命令の分岐先アドレス又は予測分岐先アドレスと分岐のし易さを示す第2の値とを格納する分岐先バッファと、該第1の値及び該第2の値の何れかを選択することで分岐予測を行う選択ユニットを含むことを特徴とする分岐予測装置。
【請求項2】該選択ユニットは、現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在する場合には該第1の値を選択し、該現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在しない場合には該第2の値を選択することを特徴とする請求項1記載の分岐予測装置。
【請求項3】該選択ユニットは、該現在の命令アドレスに対して該分岐先バッファにエントリが存在しない場合には分岐しないと予測することを特徴とする請求項2記載の分岐予測装置。
【請求項4】該インデックス生成回路は、該履歴レジスタが保持する該履歴と該命令アドレスとの排他的論理和として該第1のインデックスを生成することを特徴とする請求項1記載の分岐予測装置。
【請求項5】該履歴テーブルは該第1のインデックスの各々に対して複数のエントリが登録できるように複数個設けられることを特徴とする請求項1記載の分岐予測装置。
【請求項6】過去の分岐命令の履歴を保持する履歴レジスタと、該履歴レジスタが保持する該履歴と命令アドレスとから第1のインデックスを生成するインデックス生成回路と、各第1のインデックスに対して該命令アドレスの一部であるタグと分岐のし易さを示す第1の値とを格納する履歴テーブルと、該命令アドレスの少なくとも一部を第2のインデックスとして該命令アドレスが示す命令の分岐先アドレスと分岐のし易さを示す第2の値とを格納する分岐先バッファと、該第1の値及び該第2の値の何れかを選択することで分岐予測を行う選択ユニットと、命令の実行を制御する実行制御ユニットと、該命令を実行する演算実行ユニットを含むことを特徴とするプロセッサ。
【請求項7】過去の分岐命令の履歴と命令アドレスとから生成する第1のインデックスに対して該命令アドレスの一部であるタグと分岐のし易さを示す第1の値とを格納する履歴テーブルと、該命令アドレスの少なくとも一部を第2のインデックスとして該命令アドレスが示す命令の分岐先アドレスと分岐のし易さを示す第2の値とを格納する分岐先バッファとを設けた構成において、該第1の値及び該第2の値の何れかを選択し、選択した値に応じて分岐予測を行う各段階を含むことを特徴とする分岐予測方法。
【請求項8】該選択する段階は、現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在する場合には該第1の値を選択し、該現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在しない場合には該第2の値を選択することを特徴とする請求項7記載の分岐予測方法。
【請求項9】該現在の命令アドレスに対して該分岐先バッファにエントリが存在しない場合に該分岐先バッファに該現在の命令アドレスを登録し、該現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在せず且つ該第2の値に基づく予測結果が誤りである場合に該履歴テーブルに該現在の命令アドレスに関する登録を行う各段階を含むことを特徴とする請求項8記載の分岐予測方法。
【請求項10】該現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在せず且つ該第2の値に基づく予測結果が正しい場合に該履歴テーブルに該現在の命令アドレスに関する登録を行わないことを特徴とする請求項9記載の分岐予測方法。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、一般に分岐命令の分岐予測方式及びプロセッサに関し、詳しくは、PHT(Pattern History Table)を用いた分岐予測方式及びプロセッサに関する。
【0002】
【従来の技術】パイプライン動作を実行するプロセッサにおいては、分岐命令の分岐結果を待ってから分岐先アドレスに分岐するのでは、命令フェッチのタイミングが遅くなりパイプライン動作に乱れが生じる。従って、分岐命令を実行する前に分岐予測をし、パイプライン動作の流れに沿った一連の命令フェッチを可能にする必要がある。
【0003】分岐命令には、その分岐命令自体が分岐し易い或いは分岐し難いといったように、ローカルな意味で分岐方向に偏りが存在する場合が多い。また最近実行された分岐命令の分岐結果に依存してある分岐命令が分岐し易い或いは分岐し難いといったように、グローバルな意味で分岐方向に偏りが存在する場合も多い。PHT(Pattern History Table)は、このような分岐傾向のローカル性及びグローバル性を考慮して、高い精度で分岐を予測する方式である。
【0004】図1は、従来のPHTを利用した分岐予測方式の構成図である。
【0005】図1の分岐予測装置は、XOR回路11、GHRユニット12、及びPHTユニット13を含む。GHR(Global History Register)12は、最近実行した分岐命令について分岐したか否かに関する履歴を記録しておくレジスタである。分岐命令が分岐した場合にはレジスタ内部を左に1ビットシフトしながら最下位ビットに1を格納し、分岐命令が分岐しなかった場合にはレジスタ内部を左に1ビットシフトしながら最下位ビットに0を格納する。例えば、GHR12が6ビット長であり、現在の内容が“011001”であるとする。この状態で、ある分岐命令を実行した結果が「分岐」であったとすると、GHR12の内容を左に1ビットシフトし更に1を最下位ビットに挿入する。結果として、GHR12の内容は“110011”となる。この“110011”は、6回前の分岐命令が分岐、5回前の分岐命令が分岐、4回前の分岐命令が非分岐、3回前の分岐命令が非分岐、2回前の分岐命令が分岐、最も最近の分岐命令が分岐であったことを示す。
【0006】XOR回路11は、プログラムカウンタ10が示す実行する分岐命令アドレスとGHRユニット12の内容との排他的論理和を計算する。計算された排他的論理和は、PHTユニット13にインデックスとして供給される。
【0007】PHT13は、各インデックスに対して例えば2ビットのカウントを格納するRAMである。ここでインデックスは、上述のようにプログラムカウンタ10の示す実行する分岐命令アドレスとGHRユニット12の内容との排他的論理和である。また、インデックスの内容である2ビットのカウント値は、そのインデックスをヒットした場合の予測結果である。カウント値が0及び1の場合には分岐しないと予測し、カウント値が2及び3の場合には分岐すると予測する。
【0008】例えば、GHR12の内容が“110011”であり、分岐命令アドレスが“001000”である場合、インデックスは“111011”となる。このインデックス“111011”の内容の2ビットカウント値を参照して、例えばカウント値が2であるとする。上述のように2或いは3のカウント値は分岐予測を意味するので、命令アドレスが“001000”である現在実行しようとしている分岐命令は、分岐すると予測する。実際に命令を実行した結果として分岐すれば、カウント値に1を加算する。また実際に命令を実行した結果として分岐しない場合には、カウント値から1を減算する。従って、例えば実際の実行結果として分岐したとすると、カウント値は3に設定される。
【0009】その後、例えば、GHRユニット12が全く同一の内容“110011”である状態で、同じ分岐命令アドレス“001000”の分岐命令を再度実行する場合、インデックスは前回と同一の“111011”となる。この場合のカウント値は3であり、分岐命令は分岐すると予測する。前述のように、GHRユニット12の内容は、最近実行した分岐命令の分岐結果の履歴である。従って、最近の分岐傾向が同一の条件で同一の分岐命令を実行した場合には、その分岐結果は同一のインデックスに蓄積されていく。次回同一のインデックスを参照したときには、そのカウント値が分岐予測に用いられる。
【0010】最近実行した分岐命令の分岐結果の履歴が、上記の履歴と若干異なる場合として、例えばGHRユニット12の内容が“110010”であるとする。これは上記の場合“110011”と比較して、最後の分岐命令の結果が異なっていた場合である。この場合、上記と同一の分岐命令アドレス“001000”の分岐命令を実行するとすると、インデックスは“111010”となる。従って、このインデックスには、過去の分岐の履歴が“110010”である条件で分岐命令アドレス“001000”の分岐命令を実行した場合について、分岐結果が蓄積されていくことになる。
【0011】従って、仮に分岐命令がプログラム中に1つしか存在しない場合には、各インデックスは、この分岐命令の分岐の結果を種々の分岐履歴に対して蓄積することになり、分岐履歴を反映した非常に高い精度での分岐予測が可能となる。しかし分岐命令がプログラム中に複数個存在する場合には、PHTユニット13内で互いの分岐命令の結果が干渉し合うことになり、予測精度が低下する。例えば、GHRユニット12の内容が“111010”の場合に分岐命令アドレス“000001”の分岐命令を実行するとすると、インデックスは“111011”となり、上記のようにGHR12の内容が“110011”であり分岐命令アドレスが“001000”である場合と同一のインデックスとなってしまう。このようにXOR回路11でインデックスを計算する方式では、異なった分岐命令間で同一のインデックスを共有することになり、分岐結果の記録が干渉してしまい予測精度が低下する。
【0012】予測精度を低下させないためには、GHRユニット12の内容とプログラムカウンタ10の内容とを繋ぎ合わせてインデックスを作成すればよい。例えば、GHR12の内容が“110011”であり分岐命令アドレスが“001000”である場合には、インデックスを“110011001000”とすればよい。しかしこの場合には、インデックスが長くなることで、PHTユニット13のRAMのエントリ数が大幅に増大してしまう。実際、この場合のエントリ数は64倍(=26)に増大することになる。
【0013】
【発明が解決しようとする課題】上述のように、分岐予測に使用するPHTにおいてエントリが干渉する構成においては、分岐予測の精度が低下してしまうという問題がある。しかし予測精度を向上させるために、PHTのメモリ容量を必要以上に増大させることは望ましくない。可能な限り小さなメモリ容量で可能な限り予測精度を向上させることが望ましい。
【0014】従って本発明は、PHTを使用する分岐予測方式において、可能な限り小さなメモリ容量を使用しながらエントリ干渉を回避して分岐予測の精度を向上させた分岐予測方式を提供することを目的とする。
【0015】
【課題を解決するための手段】本発明による分岐予測装置は、過去の分岐命令の履歴を保持する履歴レジスタと、該履歴レジスタが保持する該履歴と命令アドレスとから第1のインデックスを生成するインデックス生成回路と、各第1のインデックスに対して該命令アドレスの一部であるタグと分岐のし易さを示す第1の値とを格納する履歴テーブルと、該命令アドレスの少なくとも一部を第2のインデックスとして該命令アドレスが示す命令の分岐先アドレスと分岐のし易さを示す第2の値とを格納する分岐先バッファと、該第1の値及び該第2の値の何れかを選択することで分岐予測を行う選択ユニットを含むことを特徴とする。
【0016】上記分岐予測装置において、該選択ユニットは、現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在する場合には該第1の値を選択し、該現在の命令アドレスに対して該分岐先バッファにエントリが存在し且つ該現在の命令アドレスと現在の履歴とに対して該履歴テーブルにエントリが存在しない場合には該第2の値を選択することを特徴とする。
【0017】上記分岐予測装置においては、履歴テーブル(PHT)のエントリに命令の一部をタグとして設けることで、異なった分岐命令間でのPHTエントリの干渉を避けることが可能になる。しかしながらあるインデックスを参照しても、タグが現在の命令に一致しない場合には、当該履歴状況での当該命令に関する情報は登録されていないことになる。このような場合には、分岐先バッファ(BTB)を分岐予測に使用する。即ち、履歴テーブルがヒットした場合(タグが一致)には、履歴テーブルの第1の値を分岐予測に使用し、履歴テーブルがミスした場合(タグが不一致)には、分岐先バッファの第2の値を分岐予測に使用する。
【0018】このように本発明による分岐予測方式では、エントリ干渉を回避して高精度な分岐予測が可能になるので、実際の分岐方向が確定する前に予測に基づいて命令フェッチしても、予測がはずれる可能性は小さく、パイプライン動作の乱れを避けることが出来る。
【0019】また本発明による分岐予測方式では、分岐先バッファの第2の値を予測に併用することにより、従来のようにPHT単体で分岐予測を実行する場合と比較して、分岐結果を学習させるまでの時間が短くてすむ。従って、本発明による分岐予測方式は、コンテキストスイッチによる状況変化に短時間で対応できる。
【0020】
【発明の実施の形態】以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【0021】図2は、本発明によるPHTを利用した分岐予測装置の構成図である。
【0022】本発明による分岐予測装置は、XOR回路21、GHRユニット22、タグ付きPHTユニット23、比較ユニット24、BTB(Branch Target Buffer)25、比較ユニット26、及び選択ユニット27を含む。
【0023】GHR(Global History Register)22は、最近実行した分岐命令について分岐したか否かに関する履歴を記録しておくレジスタである。分岐命令が分岐した場合にはレジスタ内部を左に1ビットシフトしながら最下位ビットに1を格納し、分岐命令が分岐しなかった場合にはレジスタ内部を左に1ビットシフトしながら最下位ビットに0を格納する。XOR回路21は、プログラムカウンタ20が示す実行する分岐命令アドレスとGHRユニット22の内容との排他的論理和を計算する。計算された排他的論理和は、タグ付きPHTユニット23にインデックスとして供給される。
【0024】タグ付きPHTユニット23は、XOR回路21の出力である各インデックスに対して、タグ23aとカウント値23bとを格納するRAMである。またBTBユニット25は、命令アドレスの一部をインデックスとして、タグ(命令アドレスの一部)25aと、分岐命令の分岐先アドレス25bと、バイアスビット25cとを格納するRAMである。
【0025】BTBユニット25は、従来の分岐予測方式においても使用されるユニットであり、分岐命令が分岐すると予測されると、その分岐先アドレスを直ちに提供するために設けられる。通常分岐先アドレスは、フェッチした分岐命令をデコードして命令を実行する時に算出する必要があるために、分岐先アドレスの特定には時間を要する。BTBを設けておき各分岐命令に対して分岐先アドレスを格納しておくことで、分岐命令が分岐すると予測される時に、分岐先アドレスを直ちにBTBから読み出すことが出来る。ここでBTBのメモリ容量を小さくするために、命令アドレスの一部をインデックスとし、残りの部分をタグとして、当該インデックスのエントリの一部としてタグを格納しておく。
【0026】プログラムカウンタ20から命令アドレスが入力されると、この命令アドレスに対応するインデックスからタグ25aを読み出し、読み出したタグ25aと入力命令アドレスの対応部分とを比較する。この比較は、比較ユニット26によって実行される。比較結果が一致を示す場合(ヒットした場合)には、この命令アドレスの分岐命令が登録されていることになり、当該インデックスに格納されている分岐先アドレス25bをプリフェッチアドレスとして使用する。
【0027】バイアスビット25cは、その分岐命令が分岐し易いが分岐し難いかを示す。1ビットで構成される場合には、例えば“1”が分岐し易いことを示し、“0”が分岐し難いことを示す。このバイアスビット25cは、その分岐命令自体が分岐し易いか分岐し難いかを示す、ローカルな意味での分岐方向の偏りに関する情報である。
【0028】タグ付きPHTユニット23は、XOR回路21が求めた命令アドレスの一部とGHRユニット22との排他的論理和をインデックスとして、過去に実行した分岐結果の情報をカウント値23bとして保持する。本発明においては、タグ付きPHTユニット23は、カウント値23bだけでなく、命令アドレスの一部をタグ23aとして保持している。
【0029】プログラムカウンタ20の命令アドレスとGHRユニット22の内容とからXOR回路21によりインデックスが求められると、タグ付きPHTユニット23からタグ23aを読み出し、読み出したタグ23aと入力命令アドレスの対応部分とを比較する。この比較は、比較ユニット24によって実行される。比較結果が一致を示す場合(ヒットした場合)には、GHRユニット22の内容が示す履歴状態での当該命令アドレスの分岐命令の情報が登録されていることになる。この場合には、このインデックスに格納されているカウント値23bを、分岐予測に使用する。カウント値23bは、例えば2ビットカウンタのカウントであり、0及び1の場合には分岐しないと予測し、2及び3の場合には分岐すると予測する。
【0030】タグ23aを設けることで、異なった分岐命令間でのPHTエントリの干渉を避けることが可能になる。しかしながら、あるインデックスを参照しても、タグ23aが現在の命令に一致しない場合(ミスした場合)には、当該履歴状況での当該命令に関する情報は登録されていないことになる。本発明では、このような場合には、BTBユニット25のバイアスビット25cを分岐予測に使用する。
【0031】即ち、タグ付きPHTユニット23がヒットした場合(タグが一致)には、タグ付きPHTユニット23のカウント値23bを分岐予測に使用し、タグ付きPHTユニット23がミスした場合(タグが不一致)には、BTBユニット25のバイアスビット25cを分岐予測に使用する。この選択は、選択ユニット27によって実行される。選択ユニット27は、比較ユニット24からの比較結果によって、タグ付きPHTユニット23がヒットしたか否かを検出する。この検出に基づいて、比較ユニット24は、タグ付きPHTユニット23からのカウント値23b或いはBTBユニット25からのバイアスビット25cの何れかを選択し、選択したデータに基づいて分岐予測をして分岐予測結果を出力する。なおBTBユニット25がヒットしていない場合には、分岐先アドレス25bが利用できないので、一律に「分岐しない」と予測して予測結果を出力する。
【0032】図3は、本発明による分岐予測のフローチャートである。
【0033】ステップS1で、BTBユニット25がヒットしたか否かを判断する。ヒットした場合にはステップS3に進み、ミスした場合にはステップS2に進む。
【0034】ステップS2で、BTBユニット25がヒットしておらず分岐先アドレス25bが利用できないので、一律に「分岐しない」と予測する。
【0035】ステップS3で、タグ付きPHTユニット23がヒットしたか否かを判断する。ヒットした場合にはステップS5に進み、ミスした場合にはステップS4に進む。
【0036】ステップS4で、BTBユニット25のバイアスビット25cに基づいて分岐予測を行う。
【0037】ステップS5で、タグ付きPHTユニット23のカウント値23bに基づいて分岐予測を行う。
【0038】図4は、本発明によるデータ更新処理のフローチャートである。
【0039】ステップS1で、BTBユニット25がヒットしたか否かを判断する。ヒットした場合にはステップS3に進み、ミスした場合にはステップS2に進む。
【0040】ステップS2で、ヒットしなかった対象命令アドレスを、その分岐先アドレスと共にBTBユニット25に登録する。この際、実際に命令を実行した分岐結果を、BTBユニット25のバイアスビット25cとして格納する。即ち、実際の命令実行の結果、分岐をしたのであれば1をバイアスビット25cに格納し、分岐しなかったのであれば0をバイアスビット25cに格納する。
【0041】ステップS3では、BTBユニット25がヒットしているので、BTBユニット25の対象命令アドレスを更新する。
【0042】ステップS4で、タグ付きPHTユニット23がヒットしたか否かを判断する。ヒットした場合にはステップS8に進み、ミスした場合にはステップS5に進む。
【0043】ステップS 5で、対象命令を実際に実行した結果、実際の分岐方向が分岐予測と一致したか否かを判断する。ここで判断対象の分岐予測は、タグ付きPHTユニット23がミスした場合であるので、BTBユニット25のバイアスビット25cに基づいて行われたものである。判断の結果、一致する場合にはステップS6に進み、一致しない場合にはステップS7に進む。
【0044】ステップS6で、何もせずに処理を終了する。これは、分岐予測の結果と実際の分岐の結果とが一致する場合には、現状の分岐予測が適切であると判断できるからである。
【0045】ステップS7で、タグ付きPHTユニット23に当該履歴状況での当該命令に関する情報を登録する。即ち、対象となるインデックスに、対象となる命令アドレスのタグ23aを格納すると共に、カウント値23bに実際の分岐結果を格納する。例えば、分岐した場合には2(“10”)を格納し、分岐しなかった場合には1(“01”)を格納する。これは、分岐予測の結果と実際の分岐の結果とが一致しない場合には、BTBユニット25のバイアスビット25cに基づく現状の分岐予測が不適切であると判断できるからである。
【0046】ステップS8では、タグ付きPHTユニット23がヒットしているので、タグ付きPHTユニット23のカウント値23bを更新する。具体的には、実際の分岐結果が分岐の場合にカウント値23bを1増加させ、分岐結果が分岐でない場合にカウント値23bを1減少させる。なおカウント値23bが既に最大値(例えば2ビットカウンタなら3)の場合には、実際の分岐結果が分岐であってもカウント値23bはそのままである。またカウント値23bが既に最小値(例えば0)の場合には、実際の分岐結果が非分岐であってもカウント値23bはそのままである。
【0047】ステップS9で、BTBユニット25のバイアスビット25cとタグ付きPHTユニット23のカウント値23bとについて、夫々の値をチェックする。バイアスビット25cとカウント値23bとが、夫々0と0(“00”)であるか或いは夫々1と3(“11”)である場合に、ステップS11に進む。それ以外の場合には、ステップS10に進む。
【0048】ステップS10で、LRUビット等を更新する。ここでLRU(Least Recently Used)ビットとは、タグ付きPHTユニット23の各エントリに付加され、参照されてから最も使われなかったエントリを特定するためのビットである。タグ付きPHTユニット23を分岐予測に使用する毎に、このLRUビットを更新する。LRUビットの意味については後述する。
【0049】ステップS11で、タグ付きPHTユニット23の対象エントリを無効にする。即ち、タグ付きPHTユニット23の当該対象エントリを実質的に削除する。これは、タグ付きPHTユニット23のカウント値23bが特定の分岐方向を強く示唆しており且つBTBユニット25のバイアスビット25cがそれと同一の分岐方向を示している場合には、BTBユニット25のバイアスビット25cで分岐を予測しても同一の予測結果が得られるので、タグ付きPHTユニット23から登録を抹消することで、タグ付きPHTユニット23のRAMのメモリ空間を有効に使用するためである。
【0050】以上が、本発明によるデータ更新処理である。
【0051】以下に、本発明におけるセットアソシアティブ方式について説明する。
【0052】本発明においては、図2に示されるように、タグ付きPHTユニット23が複数個設けられていてもよい。このように複数のタグ付きPHTユニット23を設けることで、同一インデックスに対して複数のエントリを格納可能になる。例えば、4セットのPHTが設けられる4−ウェイセットアソシアティブ方式においては、同一インデックスに対して、4つまでのエントリを格納可能である。
【0053】このようにセットアソシアティブ方式を使用した場合には、データ更新時にどのエントリを削除するかを決定する必要がある。例えば4−ウェイセットアソシアティブにおいて既に4つのエントリを使用している状況で、5つめのエントリを格納する必要があるとすると、既存の4つのエントリの何れかを選択して削除する必要がある。例えば、図4のステップS7では、タグ付きPHTユニット23に当該履歴状況での当該命令に関する情報を登録するが、既に同一のインデックスに対するエントリが満杯である場合には、既存の登録の何れかを削除して新規登録に置き換える必要がある。
【0054】図4のステップS10に関連して説明したLRUビットは、既存エントリを新規エントリで置き換える際に、置き換え対象のエントリを特定するために使用される。LRUビットは、各エントリに対して保持され、各エントリの参照順序を示すビットである。このLRUビットを調べることで、参照されてから最も長期間使われなかったエントリを特定して、新規エントリと置き換えることが出来る。
【0055】LRU方式は置き換え対象のエントリを特定する方式の1つに過ぎず、他の方式として、最も使用されなかった最低使用頻度のエントリを置換するLFU(Least Frequently Used)方式、最も過去に登録されたエントリを置換するFIFO(First-In First-Out)方式、任意に選択したエントリを置換するランダム方式などがある。
【0056】なおセットアソシアティブ方式を使用せずタグ付きPHTユニット23が一つだけ設けられる場合には、各インデックスに対して1つのエントリしか格納することは出来ない。この場合、タグ付きPHTユニット23に新規の情報を登録する際に、既に同一のインデックスに対して別の命令アドレスの登録がなされている場合には、この既存の登録を削除して、新規登録に置き換えることになる。
【0057】また図2に示されるように、BTBユニット25に対してもセットアソシアティブ方式を用いても良い。
【0058】以下に、本発明による分岐予測を具体的なプログラムの例を用いて説明する。
【0059】図5は、分岐命令を含むプログラムの一例である。
【0060】GHRユニット22の長さは6であり、その初期値を000000とする。
【0061】命令アドレス000001において、BTBユニット25に0001をインデックスとしてアクセスすると、タグミスが検出され「分岐しない」と予測する。これは図3のステップS2に対応する。実際の命令実行の結果、分岐命令が分岐するので予測がはずれる。BTBユニット25のインデックス0001のエントリにタグ00、バイアス1、分岐先アドレス000011を登録する。これは図4のステップS2に対応する。
【0062】GHRユニット22は、左に1ビットシフトしながら最下位ビットに分岐を表す1を格納し、結果として000001となる。この状態で、予測結果と各レジスタ/メモリの内容は、PC=000001, 予測失敗, BTB[0001]=00-1-000011, GHR:000001となる。ここでPCはプログラムカウンタを示し、BTBの内容は、タグ00、バイアス1、及び分岐先アドレス000011の順に示される。
【0063】次に命令アドレス000100において、BTBユニット25に0100をインデックスとしてアクセスすると、タグミスが検出され「分岐しない」と予測する。実際の命令実行の結果、分岐命令が分岐しないので予測があたる。BTBユニット25のインデックス0100のエントリにタグ00、バイアス0を登録する。
【0064】GHRユニット22は、左に1ビットシフトしながら最下位ビットに非分岐を表す0を格納し、結果として000010となる。この状態で、予測結果と各レジスタ/メモリの内容は、PC=000001, 予測成功, BTB[0100]=00-0- ******, GHR:000010となる。
【0065】更に命令アドレス0005、0006、0007、及び0008の分岐命令が分岐しない。結果として、上記と同様に,PC=000101, 予測成功, BTB[0101]=00-0- ******, GHR=000100PC=000110, 予測成功, BTB[0110]=00-0- ******, GHR:001000PC=000111, 予測成功, BTB[0111]=00-0- ******, GHR=010000PC=001000, 予測成功, BTB[1000]=00-0- ******, GHR=100000となる。
【0066】更に命令アドレス001100において、BTBユニット25に1100をインデックスとしてアクセスすると,タグミスが検出され「分岐しない」と予測する。実際の命令実行の結果、分岐命令が分岐するので予測がはずれる。BTBユニット25のインデックス1100のエントリに、タグ00、バイアス1、分岐先アドレス001001を登録する。
【0067】GHRユニット22は、左に1ビットシフトしながら最下位ビットに分岐を表す1を格納し、結果として000001となる。この状態で、予測結果と各レジスタ/メモリの内容は、PC=001100, 予測失敗, BTB[1100]=00-1-001001, GHR=000001となる。
【0068】ここで命令アドレス001001に分岐したので、再び命令アドレス001100において、BTBユニット25に1100をインデックスとしてアクセスを行う。今回はタグヒットが検出され、分岐先アドレス001001を得る。BTBユニット25がタグヒットしたので、タグ付きPHTユニット23がタグヒットするか否かをチェックする。これは図3のステップS3に対応する。
【0069】具体的には、アドレス001100とGHRの内容000001との排他的論理和001101をインデックスとして、タグ付きPHTユニット23にアクセスする。タグ判定結果はミスなので、BTBユニット25のバイアスビットに基づいて、「アドレス001001に分岐する」と予測する。これは図3のステップS4に対応する。実際の命令実行の結果、分岐命令が001001に分岐し予測が的中する。従って、図4のステップS6にあるように、BTBユニット25及びタグ付きPHTユニット23の更新はしない。この状態で、予測結果と各レジスタ/メモリの内容は、PC=001100, 予測成功, BTB[1100]=00-1-001001(更新無し), GHR=000011である。命令アドレス001100の分岐命令によって、ループが更に3回実行されると、PC=001100, 予測成功, BTB[1100]=00-1-001001(更新無し), GHR=000111PC=001100, 予測成功, BTB[1100]=00-1-001001(更新無し), GHR=001111PC=001100, 予測成功, BTB[1100]=00-1-001001(更新無し), GHR=011111となる。
【0070】ループが6回実行(5回分岐)された後に、命令アドレス001100において、上記と同様に「アドレス001001に分岐する」と予測する。この場合、ループは6回目で終了するので、分岐命令は分岐せず予測がはずれる。従って、図4のステップS7に示されるように、命令アドレス001100とGHRの内容011111との排他的論理和010011をタグ付きPHTユニット23のインデックスとし、タグ1100とカウント値0を登録する。この状態で、予測結果と各レジスタ/メモリの内容は、PC=001100, 予測失敗, PHT[010011]=1100-0, GHR=111110となる。
【0071】その後、命令アドレス001111において命令アドレス000010に分岐すると、PC=001111, 予測失敗, BTB[1111]=00-1-000010, GHR=111101となる。
【0072】命令アドレス000010以降の命令を再度実行すると、PC=000100, 予測成功(非分岐), BTB及びPHT更新なし, GHR=111010PC=000101, 予測成功(非分岐), BTB及びPHT更新なし, GHR=110100PC=000110, 予測成功(非分岐), BTB及びPHT更新なし, GHR=101000PC=000111, 予測成功(非分岐), BTB及びPHT更新なし, GHR=010000PC=001000, 予測成功(非分岐), BTB及びPHT更新なし, GHR=100000PC=001100, 予測成功(分岐), BTB及びPHT更新なし, GHR=000001PC=001100, 予測成功(分岐), BTB及びPHT更新なし, GHR=000011PC=001100, 予測成功(分岐), BTB及びPHT更新なし, GHR=000111PC=001100, 予測成功(分岐), BTB及びPHT更新なし, GHR=001111PC=001100, 予測成功(分岐), BTB及びPHT更新なし, GHR=011111PC=001100, 予測成功(非分岐), PHT[010011]=1100-0, GHR=111110となる。ここで、ループの最後の繰り返しにおける命令アドレス001100の実行においては、BTBユニット25及びタグ付きPHTユニット23が双方共にヒットし、タグ付きPHTユニット23のカウント値23bは0なので、非分岐を予測する。最後に、PC=001111, 予測成功(分岐), BTB及びPHT更新なし, GHR=111101となる。従って、今回は分岐予測が全て的中することになる。
【0073】このプログラムの実行において、本発明による分岐予測方式では、タグ付きPHTユニット23では1つのエントリしか使用していない。このように、本発明の分岐予測方式は、RAMの使用容量が少なくても、高い予測精度を実現することが出来る方式である。
【0074】なお図1に示される従来技術の分岐予測方式では、上記プログラムを実行した場合に、命令アドレス000010以降の命令を2度目に実行した際であっても、PHTエントリの干渉により全ての予測を的中させることは出来ない。
【0075】図6は、本発明による分岐予測装置を採用したプロセッサの構成例を示す。
【0076】図6のプロセッサ100は、命令キャッシュ101、データキャッシュ102、命令フェッチユニット103、命令実行制御部104、レジスタ105、レジスタ106、演算部107乃至110を含む。
【0077】命令キャッシュ101及びデータキャッシュ102は、それぞれ命令及びデータを一時的に格納する。命令フェッチユニット103は、プログラムカウンタの示すアドレスの命令を、命令キャッシュ101から順次フェッチする。命令実行制御部104は、命令フェッチユニット103がフェッチした命令を順次デコードして、デコード結果に基づいて命令実行動作を制御する。レジスタ105、レジスタ106、及び演算部107乃至110は、演算実行ユニットを構成する。この演算実行ユニットは、命令実行制御部104の制御の下で動作して、命令に基づいた演算を実行する。ここで演算部107乃至110は、夫々命令0乃至3を独立に実行する形となっており、パイプライン動作を高速に実行可能な構成となっている。
【0078】図2に示される本発明による分岐予測装置は、命令フェッチユニット103に設けられ、分岐命令があるときにその分岐方向を予測して、予測分岐方向に対応したアドレスの命令をフェッチする。本発明による分岐予測方式ではエントリ干渉を回避して高精度な分岐予測が可能になるので、実際の分岐方向が確定する前に予測に基づいて命令フェッチしても、予測がはずれる可能性は小さく、パイプライン動作の乱れを避けることが出来る。
【0079】また本発明による分岐予測方式では、BTBユニット25のバイアスビット25cを使用することにより、従来のようにPHT単体で分岐予測を実行する場合と比較して、分岐結果を学習させるまでの時間が短くてすむ。従って、本発明による分岐予測方式は、コンテキストスイッチによる状況変化に短時間で対応できる。8KBのRAMを使用したベンチマークjpeg, jbig, mpeg4, ghostscriptにおいて、本発明による分岐予測方式は、平均で96%の予測精度を実現した。
【0080】以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【0081】
【発明の効果】本発明による分岐予測方式では、エントリ干渉を回避して高精度な分岐予測が可能になるので、実際の分岐方向が確定する前に予測に基づいて命令フェッチしても、予測がはずれる可能性は小さく、パイプライン動作の乱れを避けることが出来る。
【0082】また本発明による分岐予測方式では、BTBのバイアスビットを予測に併用することにより、従来のようにPHT単体で分岐予測を実行する場合と比較して、分岐結果を学習させるまでの時間が短くてすむ。従って、本発明による分岐予測方式は、コンテキストスイッチによる状況変化に短時間で対応できる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013