(57)【要約】【課題】ｎ重ループがある場合における分岐成否の予測精度を向上させることができる分岐予測方法を提供する。【解決手段】今回の分岐命令のアドレスを第１のアドレス、前回の分岐命令のアドレスを第２のアドレス、前記今回の分岐命令による飛び先アドレスを第３のアドレスとして、それぞれ取得する。次に、取得されたアドレスについて、条件：「第３のアドレス＞第１のアドレス＞第２のアドレス」が成立する場合には、次の分岐命令で分岐を「成立」と予測する。【選択図】図１
2008083905.tif 000002
【特許請求の範囲】
【請求項１】
プログラム中の分岐の成立・不成立を予測する分岐予測方法において、
今回の分岐命令のアドレスを第１のアドレス、前回の分岐命令のアドレスを第２のアドレス、前記今回の分岐命令による飛び先アドレスを第３のアドレスとして、それぞれ取得するステップと、
前記取得するステップで取得されたアドレスについて、
条件：「第３のアドレス＞第１のアドレス＞第２のアドレス」
が成立する場合には、次の分岐命令での分岐を「成立」と予測するステップと、
を備えることを特徴とする分岐予測方法。
【請求項２】
２ビットの分岐予測バッファを用いて、プログラム中の分岐の成立・不成立を予測する分岐予測方法において、
今回の分岐命令のアドレスを第１のアドレス、前回の分岐命令のアドレスを第２のアドレス、前記今回の分岐命令による飛び先アドレスを第３のアドレスとして、それぞれ取得するステップと、
前記取得するステップで取得されたアドレスについて、
条件：「第３のアドレス＞第１のアドレス＞第２のアドレス」
が成立する場合には、次の分岐命令での分岐を「成立」と予測するステップと、
を備えることを特徴とする分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム中の分岐の成立・不成立を予測する分岐予測方法に関する。
【背景技術】
【０００２】
プログラムにおいてループを制御する分岐がある。ＲＩＳＣ（Reduced Instruction Set Computer）ではパイプライン処理による処理速度の向上のため、分岐の成否を予測することが行われている。簡単な手順で予測精度が高い方法として、２ビットの分岐予測バッファを用いる方法が知られている。
【０００３】
図４は、２ビットの分岐予測バッファを用いた予測方法における有限状態機械を示す図である。図４に示すように、４つの状態を設け、予測が２回はずれた場合にその予測内容を変更している。例えば、「状態ＳＴ０」のステートから不成立が２回連続すると、ステートが「状態ＳＴ１」を介して「状態ＳＴ１」に移動し、予測内容を“「不成立」と予測”に変更する。
【０００４】
分岐予測バッファは、命令フェッチのステージ中に命令アドレスに基づいてアクセスされる小容量の特殊バッファとして構成できる。分岐が成立すると予測される場合、分岐先アドレスからのフェッチを先取りして開始する。分岐が不成立と予測される場合には、命令順序通りのフェッチと実行が続行される。予測がはずれた場合、所定のアドレスから処理を再度実行するため、誤動作を招くものではない。しかし、処理速度がその分低下する。
【０００５】
【特許文献１】特開平９−１２８２３６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、従来の方法では、ｎ重ループを抜け出した直後の予測が適切でなくなるという問題がある。例えば、図５の例のように多重ループを抜け出す場合、第１の分岐命令、第２の分岐命令および第３の分岐命令において分岐が連続して不成立となる。したがって、ループを抜け出す時点で、ステートは「状態ＳＴ２」または「状態ＳＴ３」となり、新たに現れる分岐命令（図５では第４の分岐命令）について分岐不成立と予測され、予測が外れる。
【０００７】
本発明の目的は、ｎ重ループがある場合における分岐成否の予測精度を向上させることができる分岐予測方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の分岐予測方法は、プログラム中の分岐の成立・不成立を予測する分岐予測方法において、今回の分岐命令のアドレスを第１のアドレス、前回の分岐命令のアドレスを第２のアドレス、前記今回の分岐命令による飛び先アドレスを第３のアドレスとして、それぞれ取得するステップと、前記取得するステップで取得されたアドレスについて、条件：「第３のアドレス＞第１のアドレス＞第２のアドレス」が成立する場合には、次の分岐命令で分岐を「成立」と予測するステップと、を備えることを特徴とする。
この分岐予測方法によれば、「第３のアドレス＞第１のアドレス＞第２のアドレス」が成立する場合には、次の分岐命令での分岐を「成立」と予測するので、分岐成否の予測精度を向上させることができる。
【０００９】
本発明の分岐予測方法は、２ビットの分岐予測バッファを用いて、プログラム中の分岐の成立・不成立を予測する分岐予測方法において、今回の分岐命令のアドレスを第１のアドレス、前回の分岐命令のアドレスを第２のアドレス、前記今回の分岐命令による飛び先アドレスを第３のアドレスとして、それぞれ取得するステップと、前記取得するステップで取得されたアドレスについて、条件：「第３のアドレス＞第１のアドレス＞第２のアドレス」が成立する場合には、次の分岐命令での分岐を「成立」と予測するステップと、を備えることを特徴とする。
この分岐予測方法によれば、「第３のアドレス＞第１のアドレス＞第２のアドレス」が成立する場合には、次の分岐命令での分岐を「成立」と予測するので、分岐成否の予測精度を向上させることができる。
【発明の効果】
【００１０】
本発明の分岐予測方法によれば、「第３のアドレス＞第１のアドレス＞第２のアドレス」が成立する場合には、次の分岐命令での分岐を「成立」と予測するので、分岐成否の予測精度を向上させることができる。
【発明を実施するための最良の形態】
【００１１】
以下、図１〜図３を参照して、本発明による分岐予測方法の一実施形態について説明する。
【００１２】
図１は、本実施形態の分岐予測方法における有限状態機械を示す図である。
【００１３】
図１において、「状態ＳＴ０」および「状態ＳＴ１」では、次の分岐を「成立」と予測する。「状態ＳＴ２」および「状態ＳＴ３」では、次の分岐を「不成立」と予測する。
【００１４】
「状態ＳＴ０」において次の分岐が成立した場合には、「状態ＳＴ０」が維持され、次の分岐が不成立の場合には、「状態ＳＴ１」に遷移する。
【００１５】
「状態ＳＴ１」において次の分岐が成立した場合には、「状態ＳＴ０」に遷移する。「状態ＳＴ１」において次の分岐が不成立の場合には、ｎ重ループを検出するためのフラグが「０」であれば「状態ＳＴ２」に遷移し、このフラグが「１」であれば「状態ＳＴ０」に遷移する。ｎ重ループを検出するためのフラグについては後述する。
【００１６】
「状態ＳＴ２」において次の分岐が成立した場合には、「状態ＳＴ３」に遷移し、次の分岐が不成立の場合には、「状態ＳＴ２」が維持される。
【００１７】
「状態ＳＴ３」において次の分岐が成立した場合には、「状態ＳＴ０」に遷移し、次の分岐が不成立の場合には、「状態ＳＴ２」に遷移する。
【００１８】
次に、本実施形態の分岐予測方法における動作手順を説明する。
【００１９】
図２は状態遷移を制御するためのステートマシンの構成を示すブロック図である。
【００２０】
動作の前提条件は次の通りである。
（１）初期化により、ステートは「状態ＳＴ０」とされ、アドレスバッファ１およびアドレスバッファ２の内容は「０」となる（図２）。
（２）推論制御部４は、分岐命令がフェッチされたことを命令バス制御回路５からの信号により認識する。この信号は、分岐命令が現れたことを示す信号である（図２）。
（３）比較器３の入力「Ａ１」にはアドレスバッファ１の内容が、比較器３の入力「Ａ２」にはアドレスバッファ２の内容が、それぞれ与えられる。比較器３の入力「Ａ３」には、分岐命令により示される飛び先アドレスが与えられる。飛び先アドレスはＣＰＵの命令バス６を介して与えられる（図２）。比較器３はＡ３＞Ａ１＞Ａ２が成立するか否か判断し、判断が肯定されれば、出力「Ｙ」のフラグの値を「１」とする。判断が否定されれば、出力「Ｙ」のフラグの値を「０」とする。このフラグはｎ重ループを検出するためのものである。
（４）推論制御部４から出力される予測結果は命令バス制御回路５に与えられる（図２）。予測結果は、“「成立」と予測”、あるいは“「不成立」と予測”のいずれかである。なお、初期化によりステートは「状態ＳＴ０」となるため、このときの予測結果は、“「成立」と予測”である（図１）。
【００２１】
次に、実際の動作について説明する。図３（ａ）は２重ループが存在するプログラムにおける処理の流れを示している。
【００２２】
図３（ａ）における第１の分岐命令がフェッチされると、アドレスバッファ１の内容がアドレスバッファ２へ書き込まれるとともに、アドレスバッファ１には、第１の分岐命令のアドレス、すなわち「アドレスＡ」が命令バス６を介して書き込まれる。この結果、アドレスバッファ１の内容は「アドレスＡ」となり、アドレスバッファ２の内容は「アドレス０」である。また、比較器３の入力「Ａ３」は「アドレスＦ」となる。Ａ３＞Ａ１＞Ａ２は成立しないため、上記フラグの値は「０」である。
【００２３】
第１の分岐命令で分岐が成立し、アドレスＦからアドレスＡのループを繰り返す間、アドレスバッファ１の内容およびアドレスバッファ２の内容は「アドレスＡ」となる。また、比較器３の入力「Ａ３」は「アドレスＦ」である。Ａ３＞Ａ１＞Ａ２は成立しないため、上記フラグの値は「０」である。また、ステートは「状態ＳＴ０」に維持される。
【００２４】
第１の分岐命令で分岐が不成立となると、アドレスバッファ１の内容およびアドレスバッファ２の内容は「アドレスＡ」であるが、比較器３の入力「Ａ３」は、アドレスＡの次のアドレスとなる。Ａ３＞Ａ１＞Ａ２は成立しないため、上記フラグの値は「０」である。ステートは「状態ＳＴ１」に遷移する。
【００２５】
次に、第２の分岐命令で分岐が成立すると、アドレスバッファ１の内容は「アドレスＢ」、アドレスバッファ２の内容は「アドレスＡ」となる。また、比較器３の入力「Ａ３」は「アドレスＤ」となる。Ａ３＞Ａ１＞Ａ２は成立しないため、上記フラグの値は「０」である。また、ステートは「状態ＳＴ０」に戻る。
【００２６】
第１の分岐命令で分岐が成立し、アドレスＦからアドレスＡのループを繰り返す間、アドレスバッファ１の内容およびアドレスバッファ２の内容は「アドレスＡ」となる。また、比較器３の入力「Ａ３」は「アドレスＦ」である。Ａ３＞Ａ１＞Ａ２は成立しないため、上記フラグの値は「０」である。また、ステートは「状態ＳＴ０」に維持される。
【００２７】
第１の分岐命令で分岐が不成立となると、アドレスバッファ１の内容およびアドレスバッファ２の内容は「アドレスＡ」となり、比較器３の入力「Ａ３」は、アドレスＡの次のアドレスとなる。Ａ３＞Ａ１＞Ａ２は成立しないため、上記フラグの値は「０」である。ステートは「状態ＳＴ１」に遷移する。
【００２８】
次に、第２の分岐命令で分岐が不成立となると、アドレスバッファ１の内容は「アドレスＢ」、アドレスバッファ２の内容は「アドレスＡ」となる。また、比較器３の入力「Ａ３」は「アドレスＢ」の次のアドレス（アドレスＢよりも大きいアドレス）となる。このため、Ａ３＞Ａ１＞Ａ２が成立し、上記フラグの値が「１」となる。したがって、ステートは「状態ＳＴ２」とならず、「状態ＳＴ０」に戻る。
【００２９】
推論制御部４から出力される予測結果は、“「成立」と予測”に戻り、次の第４の分岐命令での分岐は「成立」と予測される。このように、２重ループを抜け出す時点で、ステートが「状態ＳＴ１」から「状態ＳＴ０」に戻り、予測結果が“「成立」と予測”となる。
【００３０】
図３（ｂ）は３重ループが存在するプログラムにおける処理の流れを示している。
【００３１】
この場合、３重ループを抜け出すときに第３の分岐命令のアドレスで分岐が不成立となると、アドレスバッファ１の内容は「アドレスＣ」、アドレスバッファ２の内容は「アドレスＢ」となる。また、比較器３の入力「Ａ３」は「アドレスＣ」の次のアドレス（アドレスＣよりも大きいアドレス）となる。このため、２重ループの場合と同様、Ａ３＞Ａ１＞Ａ２が成立し、上記フラグの値が「１」となる。したがって、ステートは「状態ＳＴ２」とならず、「状態ＳＴ０」に戻るため、次の第４の分岐命令での分岐は「成立」と予測される。
【００３２】
このように、３重ループを抜け出す時点においても、同様にステートが「状態ＳＴ１」から「状態ＳＴ０」に戻り、予測結果が“「成立」と予測”となる。４重ループ以上の場合でも、同様にステートが「状態ＳＴ０」に戻り、予測結果が“「成立」と予測”となる。このため、ｎ重ループがある場合の分岐予測のヒット率を向上させることができる。
【００３３】
以上説明したように、本発明の分岐予測方法によれば、ｎ重ループから抜け出したことを検出し、この場合には次の分岐命令での分岐を「成立」と予測するので、分岐成否の予測精度を向上させることができる。
【００３４】
本発明の適用範囲は上記実施形態に限定されることはない。本発明は、プログラム中の分岐の成立・不成立を予測する分岐予測方法に対し、広く適用することができる。
【図面の簡単な説明】
【００３５】
【図１】本実施形態の分岐予測方法における有限状態機械を示す図。
【図２】状態遷移を制御するためのステートマシンの構成を示すブロック図。
【図３】プログラムにおける処理の流れを示す図であり、（ａ）は２重ループが存在するプログラムにおける処理の流れを示す図、（ｂ）は３重ループが存在するプログラムにおける処理の流れを示す図。
【図４】２ビットの分岐予測バッファを用いた従来の予測方法における有限状態機械を示す図。
【図５】プログラムにおける処理の流れを示す図。
【符号の説明】
【００３６】
１      アドレスバッファ（分岐予測バッファ）
２      アドレスバッファ（分岐予測バッファ）
【図１】
2008083905.tif 000003
【図２】
2008083905.tif 000004
【図３】
2008083905.tif 000005
【図４】
2008083905.tif 000006
【図５】
2008083905.tif 000007