JPH038023A - ブランチ予測アルゴリズム - Google Patents
ブランチ予測アルゴリズムInfo
- Publication number
- JPH038023A JPH038023A JP14328189A JP14328189A JPH038023A JP H038023 A JPH038023 A JP H038023A JP 14328189 A JP14328189 A JP 14328189A JP 14328189 A JP14328189 A JP 14328189A JP H038023 A JPH038023 A JP H038023A
- Authority
- JP
- Japan
- Prior art keywords
- branch
- plant
- predicted
- case
- instruction
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Advance Control (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
この発明は、電子計算機におけるプランチ命令のプラン
チするかいなかを予測するプランチターゲットバッファ
（ＢＴＢ）のプランチ予測アルゴリズムに関するもので
ある。
チするかいなかを予測するプランチターゲットバッファ
（ＢＴＢ）のプランチ予測アルゴリズムに関するもので
ある。
第３図、第４図は、従来のプランチ命令における過去２
回のプランチ状況データを基にプランチ命令のプランチ
予測を実施するプランチ予測アルゴリズムを説明する図
である。
回のプランチ状況データを基にプランチ命令のプランチ
予測を実施するプランチ予測アルゴリズムを説明する図
である。
次に動作について説明する。
まずは、このアルゴリズムを説明する前に、第５図を用
いてプランチターゲットバッファ（以下。
いてプランチターゲットバッファ（以下。
ＢＴＢという）について説明する。
このＢＴＢはパイプライン制御下におけるプランチ命令
のプランチ先アドレスを格納するキャッシュメモリであ
る。
のプランチ先アドレスを格納するキャッシュメモリであ
る。
通常のキャッシュメモリは、基本的にアドレスプレイ、
アドレス比較回路、データアレイにて構成されるが、Ｅ
ＴＥもほぼ同様にアドレスアレイ。
アドレス比較回路、データアレイにて構成されるが、Ｅ
ＴＥもほぼ同様にアドレスアレイ。
アドレス比較回路、プランチ予測回路、データアレイと
いう構成になる。唯一プランチ予測回路が追加された点
が異なる。ＢＴＢのアドレスアレイには、プランチ命令
アドレスが格納されており。
いう構成になる。唯一プランチ予測回路が追加された点
が異なる。ＢＴＢのアドレスアレイには、プランチ命令
アドレスが格納されており。
データアレイにはプランチ先アドレスと過去のプランチ
履歴を示すプランチステータスが格納される、プランチ
ステータスは、第３図、第４図の２重マル内に示される
データ（“ＮＴ’ ”ＴＮ″ ”ＮＮ”。
履歴を示すプランチステータスが格納される、プランチ
ステータスは、第３図、第４図の２重マル内に示される
データ（“ＮＴ’ ”ＴＮ″ ”ＮＮ”。
“ＴＴ″）である。
プランチ予測回路では、下記条件時、起動される。
アドレスアレイ内アドレスとメモリリクエストされたア
ドレスが一致した場合（ＢＴＥｂｔｔ時）。
ドレスが一致した場合（ＢＴＥｂｔｔ時）。
データアレイよりプランチステータスを読み出し。
プランチ命令がプランチするかいなかを予測し。
プランチするとなればデータアレイのプランチ先アドレ
スによりキャッシュメモリにアクセスさせ。
スによりキャッシュメモリにアクセスさせ。
プランチしなければ、プランチ命令アドレスをそのまま
キャッシュメモリに送出する、プランチ命令が命令実行
された場合、このプランチ予測が正しかったかいなかが
判明する。この時点でＢＴＢのデータアレイのプランチ
ステータス部が更新される。
キャッシュメモリに送出する、プランチ命令が命令実行
された場合、このプランチ予測が正しかったかいなかが
判明する。この時点でＢＴＢのデータアレイのプランチ
ステータス部が更新される。
本発明は、プランチ予測回路におけるプランチ命令がプ
ランチするかいなかを予測するプランチ予測アルゴリズ
ムに関するものである。
ランチするかいなかを予測するプランチ予測アルゴリズ
ムに関するものである。
第３図、第１図、第５図において、プランチステータス
は２ｂｉｔである。つまシプランチ予測のプランチ履歴
は最新２回に関してのデータである。
は２ｂｉｔである。つまシプランチ予測のプランチ履歴
は最新２回に関してのデータである。
次に、第３図を用いて従来のプランチ予測アルゴリズム
について説明する。
について説明する。
プランチステータスは、２ｂｉｔであることから。
４個の状態が存在する。“ＴＴ“ＴＮ″ ”ＮＴ″”Ｎ
Ｎ’である。“ＴＴ″ ”ＮＮ’ に関しては、過去２
回のプランチ状況が一致していることから９次回も同様
と予測できる。したがって、プランチステータスが”Ｔ
Ｔ″の場合はＴ″と予測され、つま先 プランチすると
予測される。また、プランチステータスが”ＮＮ−の場
合＠Ｎ”と予測され、つまシ、プランチしないと予測さ
れる。
Ｎ’である。“ＴＴ″ ”ＮＮ’ に関しては、過去２
回のプランチ状況が一致していることから９次回も同様
と予測できる。したがって、プランチステータスが”Ｔ
Ｔ″の場合はＴ″と予測され、つま先 プランチすると
予測される。また、プランチステータスが”ＮＮ−の場
合＠Ｎ”と予測され、つまシ、プランチしないと予測さ
れる。
プランチステータスが＠ＴＮ“ ”ＮＴ−の場合。
次の予測が難かしい。“Ｎ″とも“Ｔ″とも予測できる
が、第３図の場合は、プランチステータスが１個の時と
同じようになる。つ′１シ、前回の状態と同様な状況に
次回もなると予測している。また。
が、第３図の場合は、プランチステータスが１個の時と
同じようになる。つ′１シ、前回の状態と同様な状況に
次回もなると予測している。また。
第４図が第３図と異なる点は＠ＴＮ”の場合１Ｔ＃と予
測することである。このように、プランチステータスを
２個使用し、プランチ命令のプランチ予測を実施してい
る。
測することである。このように、プランチステータスを
２個使用し、プランチ命令のプランチ予測を実施してい
る。
従来の２個のプランチステータスを使用してプランチ予
測アルゴリズムは、プランチステータスが２個しかない
ため、プランチ履歴の前回と前々回の状況が異なる場合
（“ＮＴ″、“ＴＮ’ ）、 プランチ予測の成功率
が低いという９問題点があった。
測アルゴリズムは、プランチステータスが２個しかない
ため、プランチ履歴の前回と前々回の状況が異なる場合
（“ＮＴ″、“ＴＮ’ ）、 プランチ予測の成功率
が低いという９問題点があった。
この発明は上記のような問題点を解消するため罠なされ
たもので、よシプランチ予測の成功率を高めるプランチ
予測アルゴリズムを得ること金目的とする。
たもので、よシプランチ予測の成功率を高めるプランチ
予測アルゴリズムを得ること金目的とする。
この発明に係るプランチ予測アルゴリズムは。
プランチステータスを３個以上とし、プランチ履歴を増
やすことにより、プランチを予測する条件を珈したもの
である。
やすことにより、プランチを予測する条件を珈したもの
である。
〔作用〕
この発明におけるプランチ予測アルゴリズムは。
３個以上の過去のプランチ履歴を基にプランチ命令のプ
ランチ予測をするため、よりプランチ予測の成功率が高
まる。
ランチ予測をするため、よりプランチ予測の成功率が高
まる。
本発明のプランチ予測アルゴリズムを第１図で示してい
る。
る。
１６個のマルで囲まれたものは、４個の過去のプランチ
履歴を示す。左サイドが最も古い。例えば、”ＮＴＴＮ
＝ｆは＠Ｎ’！＞Ｕｌ−も古（’、−Ｔ”７＞Ｅ２番目
に古い、“Ｔ″は３番目に古く、“Ｎ″が前回のプラン
チ履歴である。
履歴を示す。左サイドが最も古い。例えば、”ＮＴＴＮ
＝ｆは＠Ｎ’！＞Ｕｌ−も古（’、−Ｔ”７＞Ｅ２番目
に古い、“Ｔ″は３番目に古く、“Ｎ″が前回のプラン
チ履歴である。
矢印は、状態の遷移を表わし、プランチ命令が実行され
た後、プランチした場合“↓”に示す状態に遷移し、プ
ランチしなかった場合“Ｎ″に示す状態に遷移する。ま
た、各１６個のマルで囲まれたプランチ履歴に関して、
どのようにプランチを予測するかを示している。例えば
“ＴＴＴＴ″の場合、（次回は）“Ｔ″と予測（つまシ
、プランチすると予測）している。
た後、プランチした場合“↓”に示す状態に遷移し、プ
ランチしなかった場合“Ｎ″に示す状態に遷移する。ま
た、各１６個のマルで囲まれたプランチ履歴に関して、
どのようにプランチを予測するかを示している。例えば
“ＴＴＴＴ″の場合、（次回は）“Ｔ″と予測（つまシ
、プランチすると予測）している。
プランチ命令は、大きく分割すると、２種類に分割され
る。
る。
（１）無条件プランチ命令（必ずプランチする）（２）
条件付プランチ命令（条件が合致した場合プランチする
） プランチ予測アルゴリズムは、（２）の条件付プランチ
命令のプランチをいかく正確に予測できるかが最も重要
である。このため、過去のプランチ履歴を見て、履歴パ
ターンよりプランチが発生しそうか、または、しそうも
ないかを判定してプランチを予測している。この判定で
は、最新履歴から逆昇って２個以上同じ履歴であった場
合１次回も同じ履歴になるだろうというのが基本である
。例えば”ＮＴＴＴ”は＠Ｔ−と予測され、”ＮＴＩＪ
Ｎ”は“Ｎ″と予測される。
条件付プランチ命令（条件が合致した場合プランチする
） プランチ予測アルゴリズムは、（２）の条件付プランチ
命令のプランチをいかく正確に予測できるかが最も重要
である。このため、過去のプランチ履歴を見て、履歴パ
ターンよりプランチが発生しそうか、または、しそうも
ないかを判定してプランチを予測している。この判定で
は、最新履歴から逆昇って２個以上同じ履歴であった場
合１次回も同じ履歴になるだろうというのが基本である
。例えば”ＮＴＴＴ”は＠Ｔ−と予測され、”ＮＴＩＪ
Ｎ”は“Ｎ″と予測される。
なお１判定において最も難しいものは、最新履歴から逆
昇った２個の履歴が異なる場合のプランチ予測である。
昇った２個の履歴が異なる場合のプランチ予測である。
本発明は、この場合の予測精度を上げるために考えられ
たものである。例えば。
たものである。例えば。
−ＮＴＮＴ″の場合、プランチ及びプランチしない状態
の繰り返しである。これは、今後も繰り返すことが予想
される。しだがって、“Ｎ”と予測できる。”ＴＮＩＪ
“も同様に“Ｔ″と予測できる。第３図のアルゴリズム
を用いれば、 ”ＮＴ″の場合”Ｔ″と予測し、”Ｔ
Ｎ″の場合”Ｎ″と予測するため１００チプランチ予測
が不成功になることが予想できる。
の繰り返しである。これは、今後も繰り返すことが予想
される。しだがって、“Ｎ”と予測できる。”ＴＮＩＪ
“も同様に“Ｔ″と予測できる。第３図のアルゴリズム
を用いれば、 ”ＮＴ″の場合”Ｔ″と予測し、”Ｔ
Ｎ″の場合”Ｎ″と予測するため１００チプランチ予測
が不成功になることが予想できる。
第４図では、“ＮＴ″の場合”Ｔ″と予測し、”ＴＮ″
の場合“Ｔ″と予測することから、プランチ予測は５０
％の確率になることが予想される。
の場合“Ｔ″と予測することから、プランチ予測は５０
％の確率になることが予想される。
次に“ＮＮＮＴ”の場合、算術通算後にかかわるプラン
チ命令などに関する１例えばＯｖｅ ｒ ＦＩ Ｏｗ：
ＢＯＲ（桁あぶれのときプランチ）９桁あぶれがおこっ
た時のみプランチするというようなプランチ命令と予測
される。しｆＣがって、“Ｎ″と予測されるが、第３図
、第４図においては、“ＮＴ″は“Ｔ″と予測する。
チ命令などに関する１例えばＯｖｅ ｒ ＦＩ Ｏｗ：
ＢＯＲ（桁あぶれのときプランチ）９桁あぶれがおこっ
た時のみプランチするというようなプランチ命令と予測
される。しｆＣがって、“Ｎ″と予測されるが、第３図
、第４図においては、“ＮＴ″は“Ｔ″と予測する。
また、同様Ｋ”ＴＴＴＮ″の場合、 Ｂｒａｎｃｈ
Ｃ！０ｕｎｔ（ＢＯＴ）命令のように、カウンタが°Ｏ
”でない場合はプランチするというようなプランチ命令
と予測できる。したがって９次回は°Ｔ″と予測される
。第３図、第４図に関しては、“ＴＮ″の場合、第３図
では“Ｎ″と予測され、第４図では“Ｔ″と予測される
。
Ｃ！０ｕｎｔ（ＢＯＴ）命令のように、カウンタが°Ｏ
”でない場合はプランチするというようなプランチ命令
と予測できる。したがって９次回は°Ｔ″と予測される
。第３図、第４図に関しては、“ＴＮ″の場合、第３図
では“Ｎ″と予測され、第４図では“Ｔ″と予測される
。
ＮＮＴＮ”の場合は、上記で説明した“ＮＮＮＴ’と同
様なプランチ命令による履歴と考えられる。
様なプランチ命令による履歴と考えられる。
このためＮ″と予測される。
−ＴＴＮＴ“の場合は、”ＴＴＴＮ”と同様なプランチ
命令と考えられ、“Ｔ″と予測できる。
命令と考えられ、“Ｔ″と予測できる。
”ＮＴＴＮ″ “ＴＮＮＴ″の場合、規則性のあるプラ
ンチ命令と予測できる。例えばＢｒａｎｃｈ ０ｏｕｎ
ｔ命令（ＢＯＴ）のようなカウンタ使用命令のように予
測できる。したがって、”ＮＴＴＮ″の場合は°Ｔ″と
予測され、”ＴＮＮＴ″の場合は°Ｎ”と予測される。
ンチ命令と予測できる。例えばＢｒａｎｃｈ ０ｏｕｎ
ｔ命令（ＢＯＴ）のようなカウンタ使用命令のように予
測できる。したがって、”ＮＴＴＮ″の場合は°Ｔ″と
予測され、”ＴＮＮＴ″の場合は°Ｎ”と予測される。
この“ＮＴＴＮ″ ’ＴＮＮＴ″ の予測が最も難しい
が、予測が失敗した場合、“ＮＴＴＮ″は“τＴＮＮ″
に遷移しているので９次には′Ｎ“と予測され９次回以
降の予測精度は上がる。同様に。
が、予測が失敗した場合、“ＮＴＴＮ″は“τＴＮＮ″
に遷移しているので９次には′Ｎ“と予測され９次回以
降の予測精度は上がる。同様に。
＠ＴＮＮＴ”は＠ＮＮＴＴ”に遷移するので１次回は“
Ｔ″と予測され、やはり１次回以降のプランチ予測精度
は上がる。
Ｔ″と予測され、やはり１次回以降のプランチ予測精度
は上がる。
このように、４個のプランチステータスを用いると、５
０％以上の確率で予測が失敗するということはありえな
くなる。
０％以上の確率で予測が失敗するということはありえな
くなる。
次に第２図を用いて、３個の過去のプランチ履歴の場合
を説明する。
を説明する。
過去２個のプランチステータスが＠ＮＮ”または“ＴＴ
″の場合は、同様にそれぞれ次のステータスを“Ｎ″ま
たは°Ｔ″と予測する。
″の場合は、同様にそれぞれ次のステータスを“Ｎ″ま
たは°Ｔ″と予測する。
その他の’ＮＴＮ” ’ＮＮＴ’ ”ＴＴＮ’、”
ＴＮＴ’は、それぞれ多数決によシ決定する。しだがっ
てＮＴＮ″ −ＮＮＴ’は−Ｎ−と予測し、 ”ＴＴＮ
’″、”ＴＮＴ−は“Ｔ″と予測する。
ＴＮＴ’は、それぞれ多数決によシ決定する。しだがっ
てＮＴＮ″ −ＮＮＴ’は−Ｎ−と予測し、 ”ＴＴＮ
’″、”ＴＮＴ−は“Ｔ″と予測する。
なお、上記実施例においては、プランチステ−タスを４
または３個と限定しているが、基本的に３個以上なら何
個でも良い。
または３個と限定しているが、基本的に３個以上なら何
個でも良い。
また、上記実施例では、“Ｙ″と“Ｎ″でプランチステ
ータスを表わしたが、“１″とＯ″や“Ｙ″とＮ″など
他の方法で表わしてもよい。さらに。
ータスを表わしたが、“１″とＯ″や“Ｙ″とＮ″など
他の方法で表わしてもよい。さらに。
これらが、ビットやバイトなどのサイズを問わず。
かつフォーマットも問わず、メモリ内でどのような形で
保持されていてもかまわない。
保持されていてもかまわない。
以上のように、この発明によれば、プランチステータス
などのプランチ履歴情報を３個以上にしてプランチ予測
を実施しているので、予測の不確定要素が少なく、高い
精度のプランチ予測ができる。
などのプランチ履歴情報を３個以上にしてプランチ予測
を実施しているので、予測の不確定要素が少なく、高い
精度のプランチ予測ができる。
第１図、第２図はそれぞれ本発明の一実施例である３個
以上のプランチステータスを用いたプランチ予測アルゴ
リズムを説明する図、第３図、第４図は従来の２個のプ
ランチステータスのプランチ予測アルゴリズムを示す図
、第５図は従来のプランチ予測アルゴリズムを示す図で
ある。
以上のプランチステータスを用いたプランチ予測アルゴ
リズムを説明する図、第３図、第４図は従来の２個のプ
ランチステータスのプランチ予測アルゴリズムを示す図
、第５図は従来のプランチ予測アルゴリズムを示す図で
ある。
Claims (1)
- 【特許請求の範囲】 計算機の動作時におけるプランチ命令がプランチするか
をプランチ履歴情報をもちいて予測するプランチ予測ア
ルゴリズムにおいて、 プランチを“Ｔ”で表わし、否プランチを“Ｎ”で表わ
すとき、以下の手段を備えたことを特徴とするプランチ
予測アルゴリズム （ａ）あるプランチ命令の２個の最新のプランチ履歴情
報が“ＴＴ”のとき、次の動作を“Ｔ”と予測する手段
、 （ｂ）あるプランチ命令の２個の最新のプランチ履歴情
報が“ＮＮ”のとき、次の動作を“Ｎ”と予測する手段
、 （ｃ）あるプランチ命令の２個の最新のプランチ履歴情
報が“ＴＴ”と“ＮＮ”のいずれでもないとき、それ以
前のプランチ履歴情報を用いて次の動作を予測する手段
。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP14328189A JPH038023A (ja) | 1989-06-06 | 1989-06-06 | ブランチ予測アルゴリズム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP14328189A JPH038023A (ja) | 1989-06-06 | 1989-06-06 | ブランチ予測アルゴリズム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH038023A true JPH038023A (ja) | 1991-01-16 |
Family
ID=15335091
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP14328189A Pending JPH038023A (ja) | 1989-06-06 | 1989-06-06 | ブランチ予測アルゴリズム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH038023A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06236270A (ja) * | 1993-01-08 | 1994-08-23 | Internatl Business Mach Corp <Ibm> | スーパースカラ・プロセッサ・システムにおいてブランチ・ヒストリ予測精度を向上させる方法およびシステム |
-
1989
- 1989-06-06 JP JP14328189A patent/JPH038023A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06236270A (ja) * | 1993-01-08 | 1994-08-23 | Internatl Business Mach Corp <Ibm> | スーパースカラ・プロセッサ・システムにおいてブランチ・ヒストリ予測精度を向上させる方法およびシステム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6115808A (en) | Method and apparatus for performing predicate hazard detection | |
| JP2640454B2 (ja) | ディジタル命令プロセッサ制御装置および１サイクル内で分岐を実行する方法 | |
| US5987595A (en) | Method and apparatus for predicting when load instructions can be executed out-of order | |
| EP0847004B1 (en) | Information processing apparatus with branch prediction | |
| KR970002637A (ko) | 멀티프로세서 시스템 | |
| US10228864B1 (en) | Pre-fetching data based on memory usage patterns | |
| US6715064B1 (en) | Method and apparatus for performing sequential executions of elements in cooperation with a transform | |
| JP2021527248A (ja) | 予測ミス回復の待ち時間を短縮するための偶発的な分岐予測の格納 | |
| US7051191B2 (en) | Resource management using multiply pendent registers | |
| KR20200090103A (ko) | 분기 예측기 | |
| JPH02216545A (ja) | 実行履歴記憶装置 | |
| US20050283593A1 (en) | Loop end prediction | |
| US6484256B1 (en) | Apparatus and method of branch prediction utilizing a comparison of a branch history table to an aliasing table | |
| JPH038023A (ja) | ブランチ予測アルゴリズム | |
| US4559596A (en) | History memory control system | |
| JP5379712B2 (ja) | 車載制御装置 | |
| US4124892A (en) | Data processing systems | |
| US5974535A (en) | Method and system in data processing system of permitting concurrent processing of instructions of a particular type | |
| CN100354820C (zh) | 外部微代码 | |
| US6978361B2 (en) | Effectively infinite branch prediction table mechanism | |
| JP5154763B2 (ja) | 複数の命令セットデータ処理システム内の条件付分岐命令エンコーディング | |
| US7353343B2 (en) | Memory management system for preventing program execution when CPU fetches execution code from unoccupied region of memory | |
| JPS6236575B2 (ja) | ||
| JP4872883B2 (ja) | 計算機及び障害再現方法並びにプログラム | |
| CN119025164B (zh) | Risc-v矢量指令配置确定方法及装置 |