(57)【要約】【課題】  スレッドの分岐予測精度を高める分岐予測装置および分岐予測方法を提供する。【解決手段】  第１のスレッド実行ユニット１３及び第２のスレッド実行ユニット１４との情報の通信が可能な分岐予測装置であって、第１のスレッド実行ユニット１３の分岐予測情報を記憶する第１の分岐予測テーブル１５と、第２のスレッド実行ユニットの分岐予測情報を記憶する第２の分岐予測テーブル１６と、読み出しアドレスに基づき第１と第２の分岐予測テーブル１５、１６をアクセスする読み出しアドレスレジスタ４０と、第２のスレッド実行ユニット１４が待機状態の間に読み出しアドレスにより第１又は第２の分岐予測テーブル１５、１６から、第１又は第２のスレッド実行ユニット１３、１４の分岐予測情報を読み出し、第１のスレッド実行ユニット１３へ出力する選択回路４２と、を備える。【選択図】        図１
2006053830.tif 000002
【特許請求の範囲】
【請求項１】
第１のスレッド実行ユニット及び第２のスレッド実行ユニットとの情報の通信が可能な分岐予測装置であって、
前記第１のスレッド実行ユニットの分岐予測情報を記憶する第１の分岐予測テーブルと、
前記第２のスレッド実行ユニットの分岐予測情報を記憶する第２の分岐予測テーブルと、
前記第１のスレッド実行ユニットから受信した読み出しアドレスに基づき前記第１と第２の分岐予測テーブルをアクセスする読み出しアドレスレジスタと、
前記第２のスレッド実行ユニットが待機状態の間に前記読み出しアドレスにより前記第１又は第２の分岐予測テーブルから、前記第１又は第２のスレッド実行ユニットの分岐予測情報を読み出し、前記第１のスレッド実行ユニットへ出力する選択回路と、
を備えることを特徴とする分岐予測装置。
【請求項２】
前記選択回路に接続され、前記分岐予測情報の成功比率を判定する判定回路を更に備えることを特徴とする請求項１に記載の分岐予測装置。
【請求項３】
前記選択回路は、前記第２のスレッド実行ユニットの待機状態を示す共有フラグの値と前記読み出しアドレスの値に基づき前記分岐予測情報を出力することを特徴とする請求項１に記載の分岐予測装置。
【請求項４】
第１のスレッド実行ユニットから読み出しアドレスを受信するステップと、
前記読み出しアドレスに基づき前記第１と第２の分岐予測テーブルをアクセスするステップと、
前記第２のスレッド実行ユニットの待機状態を判定するステップと、
前記第２のスレッド実行ユニットが待機状態の間に前記読み出しアドレスにより前記第２の分岐予測テーブルから、前記第２のスレッド実行ユニットの分岐予測情報を読み出し、前記第１のスレッド実行ユニットへ出力するステップと、
を含むことを特徴とする分岐予測方法。
【請求項５】
前記分岐予測情報は、分岐検証器の検証結果に基づいて書き換えられることをを特徴とする請求項４に記載の分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐予測装置および分岐予測方法に関する。
【背景技術】
【０００２】
近年のプロセッサでは、プロセッサが各々のスレッド実行部で別々のスレッドを実行する構成のマルチスレッドプロセッサが存在する（特許文献１、参照。）。
【０００３】
しかしながら、スレッドの分岐結果の予測精度が低く、分岐予測自体が外れた場合にはプロセッサの性能が低下するという問題が存在していた。
【特許文献１】特開平１１−９６００５号公報（第３頁、図１）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、スレッドの分岐予測精度を高める分岐予測装置および分岐予測方法を提供する。
【課題を解決するための手段】
【０００５】
本発明の一態様は、第１のスレッド実行ユニット及び第２のスレッド実行ユニットとの情報の通信が可能な分岐予測装置であって、第１のスレッド実行ユニットの分岐予測情報を記憶する第１の分岐予測テーブルと、第２のスレッド実行ユニットの分岐予測情報を記憶する第２の分岐予測テーブルと、第１のスレッド実行ユニットから受信した読み出しアドレスに基づき第１と第２の分岐予測テーブルをアクセスする読み出しアドレスレジスタと、第２のスレッド実行ユニットが待機状態の間に読み出しアドレスにより第１又は第２の分岐予測テーブルから、第１又は第２のスレッド実行ユニットの分岐予測情報を読み出し、第１のスレッド実行ユニットへ出力する選択回路と、を備える分岐予測装置であることを要旨とする。
【０００６】
本発明の一態様は、第１のスレッド実行ユニットから読み出しアドレスを受信するステップと、読み出しアドレスに基づき第１と第２の分岐予測テーブルをアクセスするステップと、第２のスレッド実行ユニットの待機状態を判定するステップと、第２のスレッド実行ユニットが待機状態の間に読み出しアドレスにより第２の分岐予測テーブルから、第２のスレッド実行ユニットの分岐予測情報を読み出し、第１のスレッド実行ユニットへ出力するステップと、を含む分岐予測方法であることを要旨とする。
【発明の効果】
【０００７】
本発明によれば、スレッドの分岐予測精度を高める分岐予測装置および分岐予測方法を提供することができる。
【発明を実施するための最良の形態】
【０００８】
（分岐予測装置のシステム例）
本発明の実施の形態に係る分岐予測装置は、図１に示すように、第１のスレッド実行ユニット１３及び第２のスレッド実行ユニット１４との情報の通信が可能な分岐予測装置であって、第１のスレッド実行ユニット１３の分岐予測情報を記憶する第１の分岐予測テーブル１５と、第２のスレッド実行ユニットの分岐予測情報を記憶する第２の分岐予測テーブル１６と、読み出しアドレスに基づき第１と第２の分岐予測テーブル１５、１６をアクセスする読み出しアドレスレジスタ４０と、第２のスレッド実行ユニット１４が待機状態の間に読み出しアドレスにより第１又は第２の分岐予測テーブル１５、１６から、第１又は第２のスレッド実行ユニット１３、１４の分岐予測情報を読み出し、第１のスレッド実行ユニット１３へ出力する選択回路４２と、を備える。
【０００９】
第１のスレッド実行ユニット１３は、分岐予測情報を受信する命令フェッチユニット２０ａと、第２の分岐予測テーブル１６の共有状態を示す共有フラグ１７と、分岐命令アドレスレジスタ４０ａと、切替回路４１と、を備える。また、第２のスレッド実行ユニット１４は、第２の分岐予測テーブル１６に接続され、分岐命令アドレスを出力する分岐命令アドレスレジスタ４０ｇを備える。
【００１０】
さらに、分岐予測装置１２は、選択回路４２の出力段に設けられ、分岐予測情報の成功比率を判定する判定回路４４ａを更に備えている。
【００１１】
ここで、分岐予測装置１２に設けられた判定回路４４ａは命令フェッチユニット２０ａに接続され、選択回路４２は切替回路４１に接続され、第１のスレッド実行ユニット１３側の分岐命令アドレスレジスタ４０ａは読み出しアドレスレジスタ４０に接続され、切替回路４１は共有フラグ１７及び分岐命令アドレスレジスタ４０ａの中のテーブル切替ビット１８（図中「Ｔ」と略記する。）に接続されている。
【００１２】
分岐予測装置１２は、第２のスレッド実行ユニット１４が待機状態の間、共有フラグ１７とテーブル切替ビット１８の論理積を出力する切替回路４１の出力信号に基づき、第２の分岐予測テーブル１６を第１のスレッド実行ユニット１３が使用することができ、分岐予測テーブルを実質的に拡張させることで、第１のスレッド実行ユニット１３の条件分岐予測精度を向上させることができる。
【００１３】
第２のスレッド実行ユニット１４の待機状態は、プログラムの並列化の過程において、プログラム実行前に並列処理が出来ないサイクルに相当する。この並列処理ができないサイクルの割合が大きい場合には、第１のスレッド実行ユニット１３の条件分岐命令の予測精度を向上させ、並列処理装置のプログラム実行効率を向上させることができる。
【００１４】
（分岐予測装置を備えるプロセッサ例）
本発明の実施の形態に係る分岐予測装置１２は、マルチスレッド実行プロセッサに組み込み、命令コードに存在する条件分岐命令が、プログラマやコンパイラによってコードが生成される際に静的に予測できる分岐予測装置を含むプロセッサに適用させることができる。
【００１５】
また、本発明の好適な実施の形態よれば、条件分岐先を静的に予測できる分岐予測装置１２を備えるプロセッサに比して、条件分岐命令が動的な履歴からある程度の確率で分岐先が予測できるもの、並びに、ほとんど予測が当らない条件分岐命令を実行するプロセッサを対象とする。
【００１６】
図２に示すように、プロセッサ１は、外部メモリ２３に接続され、命令キャッシュ１０と、スレッド管理部１１と、分岐予測装置１２と、第１のスレッド実行ユニット１３と、第２のスレッド実行ユニット１４と、を備える。
【００１７】
第１のスレッド実行ユニット１３は、命令キャッシュ１０に接続する命令フェッチユニット２０ａと、命令キャッシュ１０及び命令フェッチユニット２０ａに接続する命令デコーダ２１ａと、命令フェッチユニット２０ａ及び命令デコーダ２１ａに接続する分岐検証器２２ａと、命令デコーダ２１ａ及び共有フラグ１７に接続する切替回路４１を備える。
【００１８】
さらに、図中の命令デコーダ２１ａは、内部に不図示の分岐命令アドレスレジスタ４０ａ（図１参照）を設けて、切替回路４１へテーブル切替ビット１８（図１参照）の信号を供給する。
【００１９】
ただし、本発明は命令デコーダ２１ａの内部に設けた分岐命令アドレスレジスタ４０ａに限定されるものではなく、図１に示したように他の回路（例えば、命令フェッチユニット）から独立して分岐命令アドレスレジスタ４０ａを設けても良い。
【００２０】
第２のスレッド実行ユニット１４は、命令キャッシュ１０に接続する命令フェッチユニット２０ｂと、命令キャッシュ１０及び命令フェッチユニット２０ｂに接続する命令デコーダ２１ｂと、命令フェッチユニット２０ｂ及び命令デコーダ２１ｂに接続する分岐検証器２２ｂと、を備える。
【００２１】
なお、図２では、図１に示した分岐命令アドレスレジスタ４０ｇを省略しているが、分岐命令アドレスレジスタ４０ｇを命令デコーダ２１ｂの内部に設けても良く、回路設計に応じて命令デコーダ２１ｂと別個に設けても良い。
【００２２】
分岐予測装置１２は、第２のスレッド実行ユニット１４が待機状態の間、第１のスレッド実行ユニット１３に第１及び第２の分岐予測テーブル１５、１６を使用させ、第１のスレッド実行ユニット１３の条件分岐予測精度を飛躍的に向上させることができる。
【００２３】
プロセッサ１は、第１及び第２のスレッド実行ユニット１３、１４を動作させて、マルチスレッド実行を行う場合、プログラム中の逐次部分では一方のスレッド実行部以外は待機状態となる期間が生じる。
【００２４】
例えば、プロセッサ１は、第２のスレッド実行ユニット１４が待機状態の場合は、スレッドの分岐命令の予測精度を向上させ、分岐命令処理の性能を向上させる。
【００２５】
本発明の実施の形態では、プロセッサ１の並列処理において、待機中のスレッド実行部が使用する分岐予測装置１２を活用して条件分岐命令の精度を高めることができる。
【００２６】
（パイプライン方式のプロセッサ例）
図３は、図１及び図２に示す分岐予測装置１２を用いたプロセッサ１の分岐命令処理シーケンスを示すデータのフローチャートである。なお、図３においては、第１のスレッド実行ユニット１３側の処理シーケンスを経時的に示し、第２のスレッド実行ユニット１４側の部材を省略している。
【００２７】
パイプライン方式のプロセッサ１は、第２のスレッド命令実行ユニット１４が待機状態の場合は、第１のスレッド実行ユニット１３側の命令キャッシュ１０と、命令キャッシュ１０に接続する命令デコーダ２１ａと、命令キャッシュ１０に接続する分岐予測装置１２と、分岐予測装置１２に接続する第１のスレッド実行ユニット１３側の命令フェッチユニット２０ａと、命令フェッチユニット２０ａ及び分岐予測装置１２に接続する第１のスレッド実行ユニット１３側の分岐検証器２２ａと、を動作させる。
【００２８】
この場合、第１のスレッド命令実行ユニット１３は、読み出しアドレスレジスタ４０（図１参照）を通して第１及び第２の分岐予測テーブル１５、１６にアクセスする。
【００２９】
切替回路４１は、共有フラグ１７が論理値「１」であって、テーブル切替ビット１８が論理値「１」を条件として、第２の分岐予測テーブル１６から読み出される分岐予測情報を選択回路４２（図１参照）に選択させ、判定回路４４ａ（図１参照）を通して第１のスレッド実行ユニット１３側の命令フェッチユニット２０ａへ受信させる。
【００３０】
図示するパイプラインステージでは、命令キャッシュ１０及び第１のスレッド実行ユニット１３側の命令フェッチユニット２０ａが動作するＩＦステージと、第１のスレッド実行ユニット１３側の命令デコーダ２１ａ及び分岐予測装置１２が動作するＩＤステージと、第１のスレッド実行ユニット１３側の分岐検証器２２ａが動作するＥＸＥステージと、を含み、第１のスレッド実行ユニット１３が分岐命令を処理する。
【００３１】
分岐予測装置１２は、入力段に命令キャッシュ１０を接続され、命令キャッシュ１０からアドレスを入力する。また、分岐予測装置１２は、第１のスレッド実行ユニット１３側の分岐検証器２２ａに接続され、分岐命令実行信号及び分岐結果を入力する。
【００３２】
第１のスレッド実行ユニット１３側の命令フェッチユニット２０ａは、分岐予測装置１２に接続され、分岐予測装置１２から分岐予測結果Ａを入力する。また、命令フェッチユニット２０ａは、第１のスレッド実行ユニット１３側の命令デコーダ２１ａに接続され、命令デコーダ２１ａから分岐命令検出信号Ｂ及び分岐先アドレスＣを入力する。
【００３３】
さらに、命令フェッチユニット２０ａは、第１のスレッド実行ユニット１３側の分岐検証器２２ａに接続され、分岐検証器２２ａから次サイクルフェッチアドレスＤ及びアドレス選択信号Ｅを入力する。
【００３４】
命令キャッシュ１０は、第１のスレッド実行ユニット１３側の命令デコーダ２１ａに接続され、命令キャッシュ１０からフェッチした命令を第１のスレッド実行ユニット１３側の命令デコーダ２１ａへ出力する。命令デコーダ２１ａは、命令をデコードして実行コードを生成し出力する。
【００３５】
図２及び図３を参照して、パイプライン方式のプロセッサ１の動作を説明する。
【００３６】
パイプライン方式のプロセッサは、インストラクションフェッチステージ（以下、「ＩＦステージ」と略記する。）、インストラクションデコードステージ（以下、「ＩＤステージ」と略記する。）、命令実行ステージ（以下、「ＥＸＥステージ」と略記する。）からなる各ステージをマシンサイクルに同期させて実行する。
【００３７】
命令フェッチユニット２０ａは、ＩＦステージにおいて、プログラムカウンタのアドレスに基づき、命令キャッシュ１０をアクセスし、命令キャッシュ１０から命令を読み出す。
【００３８】
命令キャッシュ１０は、ＩＤステージにおいて、命令を命令デコーダ２１ａに入力し、実行コードを生成させる。並行して、命令フェッチユニット２０ａから出力されているプログラムカウンタのアドレスを命令デコーダ２１ａ及び分岐予測装置１２へ入力する。
【００３９】
分岐予測装置１２は、ＩＤステージで分岐命令の分岐予測結果Ａを命令フェッチユニット２０ａへ送信し、次ぎのパイプラインステージで実行される命令の的中確度を報知する。
【００４０】
次ぎに、ＥＸＥステージに移行し、分岐検証器２２ａは、命令デコーダ２１ａが出力した実行コードの分岐が成立したか否かを検証する。又、分岐検証器２２ａは、分岐予測装置１２で正しく予測できたか否かの分岐検証結果を命令フェッチユニット２０ａにフィードバックする。同時に分岐検証器２２ａは分岐検証結果を分岐予測装置１２にフィードバックし、第１又は第２の分岐予測テーブル１５、１６（図１参照）の分岐予測情報の更新に使用する。
【００４１】
図４は、図１〜図３に示した第１のスレッド実行ユニット１３側の命令フェッチユニット２０ａのブロック図である。命令フェッチユニット２０ａは、加算器３０と、加算器３０の加算結果と分岐先アドレスを入力する選択回路３３と、選択回路３３の選択結果と次サイクルフェッチアドレスを入力する選択回路３４と、選択回路３４の出力に接続さるアドレスレジスタ３１（ＰＣ）と、分岐命令検出信号と分岐予測結果を入力するＡＮＤ回路３２と、を備え、フェッチアドレスを命令キャッシュ１０（図３参照）へ出力する。
【００４２】
選択回路３３は、分岐予測結果及び分岐命令検出信号の論理積をＡＮＤ回路３２から受信し、分岐先アドレス又は加算器３０の出力の何れか一方を選択する。選択回路３３で選択された信号は次段の選択回路３４の一方の入力端子で受信される。
【００４３】
選択回路３４は、アドレス選択信号を受信して、次サイクルフェッチアドレス又は選択回路３３で選択された信号の何れか一方を選択し次段のアドレスレジスタ３１へ出力する。アドレスレジスタ３１は、命令キャッシュ１０へフェッチアドレスを出力する。
【００４４】
選択回路３４では、もし分岐命令を含まないパイプラインステージを処理している場合は、次サイクルフェッチアドレスを選択せずにアドレスレジスタ３１から選択回路３３を通して前サイクルのフェッチアドレスに加算器３０で「４」アドレス値を加算したフェッチアドレスを選択するように制御されている。
【００４５】
例えば、分岐命令が成立する確率が高い場合では、ＡＮＤ回路３２は、分岐予測装置１２（図３参照）から分岐予測結果としての高レベル（Ｈ）信号と、命令デコーダ２１ａ（図３参照）から分岐命令検出信号としての高レベル（Ｈ）信号をそれぞれ入力し、高レベル（Ｈ）信号を出力して選択回路３３を制御し、選択回路３３に入力する分岐先アドレスを選択させる。
【００４６】
一方、選択回路３３は、分岐命令でないパイプラインステージにおいて、フェッチアドレスに「４」アドレス値を加算させた次ぎのフェッチアドレスを選択させ、選択回路３４を通してアドレスレジスタ３１へ出力させる。
【００４７】
さらに、選択回路３４は、実行ステージにおいて、分岐予側が外れた場合はアドレス選択信号が高論理値（Ｈ）に遷移し、次サイクルフェッチアドレスを選択回路３４からアドレスレジスタ３１（ＰＣ）へ出力する。
【００４８】
このように、命令フェッチユニットは、分岐予測装置１２から受信する分岐予測結果及び分岐命令検出信号に応答して、次ぎのフェッチアドレスを選択し、分岐予測を行うことができる。
【００４９】
（分岐予測装置）
図５は、図１〜図３に示した分岐予測装置１２のブロック図である。分岐予測装置１２は、第１のスレッド実行ユニット側に設けられた分岐命令アドレスレジスタ４０ａ及び切替回路４１と、第２のスレッド実行ユニット側に設けられた分岐命令アドレスレジスタ４０ｇに接続され、第１の分岐予測テーブル１５と、第２の分岐予測テーブル１６と、を備える。
【００５０】
分岐予測装置１２は、分岐命令アドレスレジスタ４０ａに接続される前予測アドレスレジスタ４０ｂ、選択回路４２ａ、及び第１の分岐予測テーブル１５と、第１の分岐予測テーブル１５に接続される選択回路４２ｂ及び前状態レジスタ４０ｄと、選択回路４２ｂの出力に接続される判定回路４４ａと、前状態レジスタ４０ｄに接続される状態遷移回路４３ａと、第１の分岐予測テーブル１５に接続される書き込みイネーブル生成回路４４ｃ（図中「ＷＥ」と略記する。）と、分岐命令アドレスレジスタ４０ｇに接続される選択回路４２ａと、選択回路４２ａに接続される第２の分岐予測テーブル１６及び前予測アドレスレジスタ４０ｃ、第２の分岐予測テーブル１６に接続される選択回路４２ｂ、判定回路４４ｂ、及び前状態レジスタ４０ｅと、前状態レジスタ４０ｅに接続される状態遷移回路４３ｂと、第２の分岐予測テーブル１６に接続される書き込みイネーブル生成回路４４ｄ（図中「ＷＥ」と略記する。）と、切替回路４１に接続される前選択レジスタ４０ｆと、前選択レジスタ４０ｆに接続される選択回路４２ｃ、４２ｄと、を備えている。
【００５１】
第１の分岐予測テーブル１５は、入力側に、第１のスレッド実行ユニット側の分岐命令アドレスレジスタ４０ａの任意の桁数から抽出する最上位ビットＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）から最下位ビットＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）のビット群からなる分岐命令アドレスを読み出しアドレスとして受信する。
【００５２】
また、分岐命令アドレスは、前予測アドレスレジスタ４０ｂにも格納される。
【００５３】
さらに、前状態レジスタ４０ｄは、分岐検証器２２ａ（図２参照）が出力する分岐検証結果に対応させて第１の分岐予測テーブル１５の内容を更新する。
【００５４】
書き込みイネーブル生成回路４４ｃは、分岐命令実行信号を受信し、前予測アドレスレジスタ４０ｂのアドレスと状態遷移回路４３ａの出力を用いて、第１の分岐予測テーブル１５の内容を更新させる。
【００５５】
選択回路４２ｃは、切替回路４１から前選択レジスタ４０ｆを通して切替信号を受信し、第１のスレッド実行ユニット側の分岐検証器２２ａ（図２参照）の分岐検証結果と第２のスレッド実行ユニット側の分岐検証器２２ｂ（図２参照）の分岐検証結果の何れか一方の分岐検証結果を選択する。
【００５６】
選択回路４２ｂは、切替回路４１に接続され、第１の分岐予測テーブル１５又は第２の分岐予測テーブル１６の何れか一方の分岐予測情報を選択し、次段の判定回路４４ａへ出力する。判定回路４４ａは、受信した分岐予測情報に基づき第１の分岐予測結果を出力する。
【００５７】
第２の分岐予測テーブル１６は、分岐命令アドレスレジスタ４０ａ及び分岐命令アドレスレジスタ４０ｇの何れか一方の出力を選択する選択回路４２ａに接続され、読み出しアドレスを受信する。
【００５８】
第２のスレッド実行ユニット側の分岐命令アドレスレジスタ４０ｇは、任意の桁数から抽出する最上位ビットＭＳＢから最下位ビットＬＳＢのビット群からなる分岐命令アドレスを読み出しアドレスとして第２の分岐予測テーブル１６から分岐予測情報を読み出すと共に、分岐予測情報のアドレスを前予測アドレスレジスタ４０ｃに格納する。
【００５９】
また、第２の分岐予測テーブル１６は、前予測アドレスレジスタ４０ｃに記憶する分岐命令アドレスを書き込みアドレスとして受信するが、第２の分岐予測テーブル１６は、好ましくは書き込みイネーブル生成回路４４ｄの書き込み許可信号に応答し、第２のスレッド実行ユニット側の分岐検証器２２ｂ（図２参照）が出力する分岐検証結果に対応させて第２の分岐予測テーブル１６の内容を更新すると良い。
【００６０】
図下部に示す選択回路４２ｄは、切替回路４１から前選択レジスタ４０ｆを通して切替信号を受信し、第１のスレッド実行ユニット側の分岐検証器２２ａからの分岐命令実行信号と第２のスレッド実行ユニット側の分岐検証器２２ｂからの分岐命令実行信号の何れか一方の分岐命令実行信号を選択する。
【００６１】
第２の分岐予測テーブル１６は、判定回路４４ｂを通して分岐予測情報を出力する。
【００６２】
（分岐成立予測テーブル）
本発明の実施の形態に係る分岐予測装置は、図６（ａ）に示すように、２ビットの状態遷移による分岐成立予測の確率を分岐予測情報として決定している。
【００６３】
分岐予測装置１２（図５参照）は、強成立予測ステップ５０（以下、ステップを「Ｓ」と略記する。）において、最も分岐成立確立の高い状態で分岐予測を「成立」させた場合は、分岐予測テーブル１５又は分岐予測テーブル１６分岐予測情報を用いて強成立予測Ｓ５０を維持する。
【００６４】
但し、強成立予測Ｓ５０の状態で分岐予測を「不成立」にさせたときは、弱成立予測Ｓ５１に移行させる。弱成立予測Ｓ５１のシーケンスは、分岐予測装置１２において２番目に分岐成立確立の高い状態である。
【００６５】
分岐予測装置１２は、２番目に分岐成立確立の高い弱成立予測Ｓ５１の状態で分岐予測を「成立」させた場合は、分岐予測テーブル１５又は分岐予測テーブル１６分岐予測情報を用いて強成立予測Ｓ５０に移行する。
【００６６】
但し、弱成立予測Ｓ５１の状態で分岐予測を「不成立」にさせたときは、弱不成立予測Ｓ５２に移行させる。弱不成立予測Ｓ５２のシーケンスは、分岐予測装置１２においては３番目に分岐成立確立の高い状態である。
【００６７】
分岐予測装置１２は、３番目に分岐成立確立の高い弱不成立予測Ｓ５２の状態で分岐予測を「成立」させた場合は、分岐予測テーブル１５又は分岐予測テーブル１６分岐予測情報を用いて弱成立予測Ｓ５１に移行する。
【００６８】
但し、弱不成立予測Ｓ５２の状態で分岐予測を「不成立」にさせたときは、強不成立予測Ｓ５３に移行させる。強不成立予測Ｓ５３は分岐予測装置１２においては４番目に分岐成立確立の高い状態であり、言い換えれば、最下位の分岐成立予測のシーケンスである。
【００６９】
分岐予測装置１２は、最も分岐成立確立の低い強不成立予測Ｓ５３の状態で分岐予測を「成立」させた場合は、分岐予測テーブル１５又は分岐予測テーブル１６分岐予測情報を用いて弱不成立予測Ｓ５２に移行する。
【００７０】
但し、強不成立予測Ｓ５３の状態で分岐予測を「不成立」にさせたときは、強不成立予測Ｓ５３の状態を維持する。
【００７１】
本発明は、強成立予測Ｓ５０〜強不成立予測Ｓ５３のシーケンスに限定するものではなく、例えば、図６（ｂ）に示すように、最も成立予測の高い強成立予測Ｓ５５の次ぎに弱成立予測Ｓ５６に移行し、弱成立予測Ｓ５６の次ぎに強不成立予測Ｓ５７に移行し、強不成立予測Ｓ５７の次ぎに弱不成立予測Ｓ５８に移行し、弱不成立予測Ｓ５８から強成立予測Ｓ５５に移行させるように制御しても良い。要は、分岐の成立予測の順位は回路設計に応じて適宜変更できる事項である。
【００７２】
さらに、本発明は、分岐予測の「成立」又は「不成立」に対応させて次ぎの分岐成立予測を決定するシーケンスに限定されず、例えば、図６（ｃ）の右側に示すように、第１の分岐予測テーブル１５又は第２の分岐予測テーブル１６から読み出された読み出し値（例えば、２ビット値）の中から上位１ビットを判定回路４４ａ又は判定回路４４ｂで選択して分岐予測結果を生成し、精度の高い分岐予測シーケンスを提供することもできる。
【００７３】
すなわち、分岐予測装置１２は、第１又は第２の分岐予測テーブル１５、１６の読み出し値が図６（ｃ）の左側に示す「強成立予測」及び「弱成立予測」の場合は、分岐成立として判定回路４４ａ又は判定回路４４ｂが、読み出し値の上位１ビットを選択し分岐成立（ビット「１」）と判定する。
【００７４】
一方、分岐予測装置１２は、第１又は第２の分岐予測テーブル１５、１６の読み出し値が図６（ｃ）の左側に示す「弱不成立予測」及び「強成立予測」の場合は、判定回路４４ａ又は判定回路４４ｂが、図６（ｃ）の右側に示すように、読み出し値の上位１ビットを選択し分岐不成立（ビット「０」）と判定する。
【００７５】
（パイプラインプロセッサの分岐成立例）
図７は、本発明の実施の形態に係る分岐予測装置を備えたパイプラインプロセッサの動作を説明するタイミングチャートである。図２と図７を参照して、プロセッサ１の動作を説明する。
【００７６】
第１のスレッド実行ユニット１３は、分岐命令を含むプログラムを実行する。例えば、「ｂｅｑ」の条件付き分岐命令６０をパイプライン方式で処理し、各パイプラインステージの分岐制御に関連するフェッチステージ、デコードステージ、実行ステージのプログラムカウンタ（以下、「ＰＣ」と略記する。）のアドレスを出力する。
【００７７】
命令キャッシュ１０には、例えば、１６進を表示するコード「０ｘ」とアドレス「１００」を組合わせるＰＣアドレス「０ｘ１００」番地に、「ｂｅｑ」の条件付き分岐命令６０を記憶する。
【００７８】
レジスタ１９ｂには、命令キャッシュから命令を読み出すのに用いたＰＣアドレスを記憶する。レジスタ１９ａには命令キャッシュから読み出した命令をそのまま記憶する。ＰＣアドレス「０ｘ１００」番地の命令キャッシュの内容を読み出した場合、レジスタ１９ａには「ｂｅｑ」を示す命令コードと、分岐の条件判定に用いる汎用レジスタの番号「＄１」、「＄２」と、分岐先のアドレスの生成に用いる分岐オフセットの「０ｘ６４」が記憶され、レジスタ１９ｂにはＰＣアドレス「０ｘ１００」が記憶される。
【００７９】
又、ＰＣアドレス「０ｘ１０４」番地の命令キャッシュの内容を読み出した場合、レジスタ１９ａには「ａｄｄ」を示す命令コードと、汎用レジスタの番号「＄８」、「＄９」が記憶される。
【００８０】
さらに、ＰＣアドレス「０ｘ１６４」番地の命令キャッシュの内容を読み出した場合、レジスタ１９ａには「ｌｗ」を示す命令コードと、汎用レジスタの番号「＄１０」、「＄１１」が記憶される。
【００８１】
ここで、レジスタ１９ａ、１９ｂ、１９ｃは、「パイプラインレジスタ」と称する構成要素に対応し、「汎用レジスタ」は通常「１６」〜「３２」本程度のレジスタの集合として「汎用レジスタファイル」と称する構成要素に対応する。
【００８２】
レジスタ１９ａは、命令の内容（例えば、６ｂｉｔでｂｅｑを示す）や、オペランドとなる汎用レジスタの番号１（例えば、５ｂｉｔで＄８を示す)や、オペランドとなる汎用レジスタの番号２（例えば、５ｂｉｔで＄９を示す)や、相対アドレス指定（例えば、１６ｂｉｔでＰＣに「０ｘ６４」を加算したアドレスに分岐することを示す）を入力し記憶する。
【００８３】
レジスタファイル１９ａは、合計３２ｂｉｔで、命令キャッシュから読み出したデータ（例えば、命令）を記憶し、命令キャッシュ１０の内容も、このような３２ｂｉｔ単位の命令が複数並んで記憶されている。
【００８４】
レジスタ１９ｃは、デコード後の命令の内容（例えば、２０ｂｉｔ中の数ｂｉｔが「ｂｅｑ」を示す）や、オペランドとなる番号１の汎用レジスタの内容 （例えば、３２ｂｉｔ）や、オペランドとなる番号２の汎用レジスタの内容（例えば、３２ｂｉｔ）や、分岐先アドレス（例えば、３２ｂｉｔ）を記憶する。
【００８５】
第１のスレッド実行ユニット１３は、各命令を上部に示す実行サイクル（図中「Ｃ１」〜「Ｃ８」）の番号に沿ってパイプライン方式により処理する。
【００８６】
プロセッサ１は、５段のパイプラインステージからなる実行サイクルで「ｂｅｑ」、「ａｄｄ」の命令を処理する。各パイプラインステージは、命令フェッチ（ＩＦ）、命令デコード（ＩＤ）、命令実行（ＥＸＥ）、メモリアクセス（ＭＥＭ）、レジスタライトバック（ＷＢ）を含み、１つのパイプラインステージで１つの処理を実行する。
【００８７】
また、プロセッサ１は、「ｌｗ」の命令では、各パイプラインステージが、命令フェッチ（ＩＦ）、命令デコード（ＩＤ）、アドレス計算（ＡＣ）、メモリアクセス（ＭＥＭ）、レジスタライトバック（ＷＢ）を含んだ一連の処理を実行する。
【００８８】
プロセッサ１は、分岐予測装置１２を動作させて条件付き分岐命令６０を実行する場合、分岐命令処理の流れが合計４通り存在する。すなわち、プロセッサ１の分岐予測結果と分岐結果の組み合わせが４通り存在するからである。
【００８９】
プロセッサ１は、分岐予測と分岐結果が共に分岐成立である場合と、分岐予測結果が分岐成立を予測しているが、分岐結果が分岐不成立の場合では、処理の流れが相違する。
【００９０】
分岐予測装置１２は、分岐予測結果が分岐成立であることを予測し、分岐結果も分岐成立した場合のプロセッサ１の分岐制御について説明する。
【００９１】
プロセッサ１は、実行サイクルＣ１で、「０ｘ１００」番地の命令のＩＦステージの処理を行う。例えば、命令フェッチユニット２０ａは、「０ｘ１００」をフェッチアドレスとして命令キャッシュ１０とパイプラインレジスタに出力する。
【００９２】
第１のスレッド実行ユニット１３は、「０ｘ１００」番地の「ｂｅｑ」の命令と、第１および第２のオペランドで指定される汎用レジスタ「＄１」、「＄２」の内容を比較し、２つの値が等しい場合に、現在の「ｂｅｑ」の命令を読み込んだアドレスへ「０ｘ６４」番地を加算した相対アドレスへ処理を分岐させる。
【００９３】
一方、汎用レジスタ「＄１」、「＄２」の値が等しくない場合は、分岐しない命令のＩＦステージ終了時に、命令キャッシュ１０から読み出された「ＢＥＱ」の命令が、パイプラインレジスタに書き込まれる。
【００９４】
第１のスレッド実行ユニット１３は、同時に「０ｘ１００」番地のアドレスをパイプラインレジスタに書き込み、命令フェッチユニット２０ａの内部で、命令デコーダ２１ａからの分岐命令検出信号と分岐検証器２２ａからのアドレス選択信号が低レベル（Ｌ）のＯＦＦ状態を検知し、次のサイクルで命令を読み込むアドレスとして、現在のフェッチアドレスに４アドレスを加算する加算器３０（図４参照）の出力を選択し、パイプラインステージの終了時にアドレスレジスタ３１（図４参照）へＰＣアドレスを書き込む。
【００９５】
第１のスレッド実行ユニット１３は、実行サイクルＣ２で、「０ｘ１０４」番地の「ａｄｄ」の命令をＩＦステージでフェッチ処理を行うとともに、「０ｘ１００」番地６１の「ｂｅｑ」の命令をＩＤステージでデコード処理を行う。
【００９６】
第１のスレッド実行ユニット１３は、ＩＤステージで読み出しアドレス「０ｘ１００」番地６１と読み出された命令（ＢＥＱ命令）などが命令デコーダ２１ａに入力されて各種制御信号やデータを生成し、パイプラインステージの終了時に、生成したデータをパイプラインレジスタに書き込む。
【００９７】
第１のスレッド実行ユニット１３は、デコードした命令が分岐命令の場合、命令デコーダ２１ａの分岐命令検出信号を高レベル（Ｈ）のＯＮ状態として検出し、分岐アドレスの「０ｘ１６４」番地６２を生成するとともに、分岐予測装置１２から「０ｘ１００」番地６１の条件分岐命令の分岐予測結果を出力するように制御する。
【００９８】
プロセッサ１は、共有フラグ１７（図１参照）を「０」にセットし、分岐予測装置１２が、第１又は第２のスレッド実行ユニット１３、１４からの制御により、それぞれ対応する第１又は第２の分岐予測テーブル１５、１６（図１参照）を用いて分岐予測結果を出力する。
【００９９】
プロセッサ１は、共有フラグ１７を「０」にしている場合は、第１のスレッド実行ユニット１３の制御による第１の分岐予測テーブル１５（図１参照）を用いた分岐予測ブロックを動作させる。
【０１００】
分岐予測装置１２は、分岐命令アドレスレジスタ４０ａに記憶する分岐命令アドレスの任意のＬＳＢ〜ＬＳＢのビット群（例えば、下位ｎビットから下位３ビットまで）を、第１の分岐予測テーブル１５の読み出しアドレス「０ｘ４０」として入力し分岐予測データの読み出し動作を実行する。
【０１０１】
例えば、プロセッサ１では、命令が３２ビットの固定長で、命令が置かれる先頭アドレスが４バイト毎に命令キャッシュ１０に書き込み、最下位の２ビットは２進表示で「００」となるので最下位の２ビットを除いた読み出しアドレスを読み出しアドレスの対象とする。
【０１０２】
分岐予測装置１２は、スレッド実行時に、２ビットカウンタ方式の動的な分岐予測方式を用いて、第１の分岐予測テーブル１５の「０ｘ４０」番地から読み出された、２ビット長の読み出し値（又は、データ）「１１」が、選択回路４２ｂ（図５参照）を経由して判定回路４４ａ（図５参照）に入力され、並行して、前状態レジスタ４０ｄにも「１１」を入力する。
【０１０３】
また、分岐予測装置１２は、読み出しアドレス「０ｘ４０」を前予測アドレスレジスタ４０ｂに入力し、パイプラインステージの終了時に「０ｘ４０」を書き込む。
【０１０４】
判定回路４４ａは、第１の分岐予測テーブル１５の読み出し値と分岐予測結果の関係に従って、分岐成立を示す「ＴＲＵＥ」分岐予測出力６３を判定回路４４ａから出力する。この分岐予測テーブル１５の読み出し値の２進表示は、強不成立予測の時「００」、弱不成立予測の時「０１」、弱成立予測の時「１０」、強成立予測の時「１１」に設定される。
【０１０５】
命令フェッチユニット２０ａでは、分岐命令検出信号が高レベル（Ｈ）のＯＮ状態を検知し、分岐予測結果が分岐成立の「ＴＲＵＥ」分岐予測出力６３に設定されているため、命令デコーダ２１ａで生成された分岐先アドレスが選択されて、パイプラインステージの終了時にアドレスレジスタ３１（図４参照）にＰＣアドレスとして書き込まれる。
【０１０６】
第１のスレッド実行ユニット１３は、実行サイクルＣ３で、「０ｘ１６４」番地６５の命令のＩＦステージの処理と、「０ｘ１０４」番地の命令のＩＤステージの処理を実行する。並行して、「０ｘ１００」番地６５の命令をＥＸＥステージで実行処理する。
【０１０７】
第１のスレッド実行ユニット１３は、ＩＤステージでレジスタ１９ｃから実行コードを読み出し、ＥＸＥステージで、実行コードを実行する。
【０１０８】
第１のスレッド実行ユニット１３は、条件付き分岐命令６０のＥＸＥステージで、レジスタ１９ｃから実行コードを読み出して演算回路に入力し指定された条件の演算操作を行う。
【０１０９】
分岐検証器２２ａは、ＥＸＥステージの命令が条件付き分岐命令６０の場合、分岐命令実行信号を高レベル（Ｈ）のＯＮ状態とする。この場合は、指定された条件が成立している状態であり、例えば、レジスタ「＄１」とレジスタ「＄２」の内容が等しい場合が該当する。前サイクルのＩＤステージにおける分岐予測結果の分岐成立「ＴＲＵＥ」分岐結果６６と一致するので、アドレス選択信号を低レベル（Ｌ）のＯＦＦ状態に遷移させる。
【０１１０】
分岐予測装置１２では、前状態レジスタ４０ｄ（図５参照）の出力が強成立予測の「１１」と分岐結果の出力が状態遷移回路４３ａに入力される。例えば、分岐条件が成立して分岐が行われる「Ｔａｋｅｎ」更新情報６７が出力されている状態で、次状態の分岐予測情報を生成し判定回路４４ａに出力する。
【０１１１】
分岐予測装置１２は、図６（ｂ）に示す状態遷移方式に従って強成立予測の「１１」から強成立予測の「１１」へ状態を遷移させ、次状態の分岐予測情報を強成立予測の「１１」に維持させる。
【０１１２】
分岐予測装置１２は、分岐命令実行信号が高レベル（Ｈ）のＯＮ状態で、前サイクルの読み出しが第１の分岐予測テーブル１５からアクセスされているので、書き込みイネーブル生成回路４４ｃの出力信号をイネーブル状態にセットし、前予測アドレス「０ｘ４０」を書き込みアドレスとして、生成された次の分岐予測情報をパイプラインステージの終了時に第１の分岐予測テーブル１５に書き込む。
【０１１３】
命令フェッチユニット２０ａでは、ＩＤステージの「ａｄｄ」の命令が分岐命令でないため、命令デコーダ２１ａからの分岐命令検出信号はＯＦＦ状態であり、ＥＸＥステージの分岐検証器２２ａのアドレス選択信号がＯＦＦ状態である。
【０１１４】
命令フェッチユニット２０ａは、次のサイクルで命令を読み込むアドレスとして、現在のフェッチアドレスに「４」アドレスを加算する加算器３０の出力「０ｘ１６８」を選択してパイプラインステージの終了時にアドレスレジスタ３１に「０ｘ１６８」を書き込む。
【０１１５】
このように、分岐予測装置１２は、分岐予測結果が分岐成立を予測し、分岐結果も分岐成立の場合は、プロセッサ１が、「０ｘ１００」番地の条件付き分岐命令６０の分岐成立を予測して実行サイクルＣ２の「０ｘ１０４」番地の「ａｄｄ」の命令に続いて実行サイクルＣ３では分岐先の「０ｘ１６４」番地の命令を投機的に実行を開始する。
【０１１６】
一方、分岐命令の実行サイクルＣ３では、分岐条件が成立する結果が得られる。この結果は分岐予測通りのため、投機的に実行した「０ｘ１６４」番地の「ｌｗ」の命令が継続して実行することができ、プログラム処理の高速化が実現できるという利点がある。
【０１１７】
（パイプラインプロセッサの分岐不成立例）
図８は、本発明の実施の形態に係る分岐予測装置を備えたパイプラインプロセッサの動作を説明するタイミングチャートである。図２と図８を参照して、プロセッサ１の動作を説明する。
【０１１８】
分岐予測装置１２は、分岐予測出力６３として分岐成立を示す「ＴＲＵＥ」を予測している状態で、分岐不成立を示す「ＦＡＬＳＥ」の分岐結果６６を得た場合、レジスタ１９ａ、レジスタ１９ｂに記憶した分岐先の命令６８を実行サイクルＣ３で消去する。
【０１１９】
なお、第１のスレッド実行ユニット１３の実行サイクルＣ１、Ｃ２は図７に示した処理と同等であり、重複する説明を省略する。
【０１２０】
第１のスレッド実行ユニット１３は、実行サイクルＣ３において、「０ｘ１６４」番地の「ｌｗ」の命令のＩＦステージの処理と、「０ｘ１０４」番地の「ａｄｄ」の命令のＩＤステージの処理と、「０ｘ１００」番地の命令のＥＸＥステージの処理を、それぞれ実行する。
【０１２１】
第１のスレッド実行ユニット１３は、「ｂｅｑ」の条件付き分岐命令６０のＥＸＥステージでは、指定されたレジスタからデータを読み出して演算回路にデータを入力し、指定された条件の演算操作を行い、演算結果を分岐検証器２２ａに入力する。
【０１２２】
分岐検証器２２ａでは、ＥＸＥステージの「ｂｅｑ」の命令が条件付き分岐命令６０のため、分岐命令実行信号をＯＮ状態とする。「ｂｅｇ」の命令は、指定された条件が不成立の場合に分岐不成立となる。例えば、レジスタ「＄１」とレジスタ「＄２」の内容が等しくないときは分岐不成立の検証結果としてＯＮ状態の分岐命令実行信号を出力する。
【０１２３】
第１のスレッド実行ユニット１３は、前サイクルのＩＤステージにおける分岐予測結果の分岐成立を示す「ＴＲＵＥ」と一致しないので、アドレス選択信号をＯＮ状態とし、次サイクルフェッチアドレス「０ｘ１０８」を生成出力する。
【０１２４】
状態遷移回路４３ａは、前状態レジスタ４０ｄの出力「１１」と分岐結果の出力（条件が不成立で分岐が行われない「ＮｏｔＴａｋｅｎ」）を入力し、次状態を生成して第１の分岐予測テーブル１５へ出力する。
【０１２５】
状態遷移回路４３ａは、例えば、図６（ｂ）に示した状態遷移方式に従って「１１」状態から「１０」状態へ状態遷移させ、次状態を「１０」に変更する。
【０１２６】
書き込みイネーブル生成回路４４ｃは、前サイクルにおいて、第１の分岐予測テーブル１５からＯＮ状態の分岐命令実行信号を読み出している。
【０１２７】
書き込みイネーブル生成回路４４ｃは、イネーブル状態となり、前予測アドレスの「０ｘ４０」を第１の分岐予測テーブル１５に書き込みアドレスとして書き込み、ＩＤステージの終了時に、生成された次状態を第１の分岐予測テーブル１５に書き込ませる。
【０１２８】
第１のスレッド実行ユニット１３側の命令フェッチユニット２０ａでは、ＩＤステージの命令が分岐命令でないため、命令デコーダ２１ａからの分岐命令検出信号をＯＦＦ状態にする。ＥＸＥステージの分岐検証器２２ａのアドレス選択信号がＯＮ状態であり、次のサイクルで命令を読み込むアドレスとして、分岐検証器２２ａから出力された次サイクルフェッチアドレスが選択されてＩＤステージの終了時にアドレスレジスタ３１（ＰＣ）に書き込まれる。
【０１２９】
命令フェッチユニット２０ａは、条件分岐命令に基づき処理を分岐すると予測してプログラムを処理した場合、分岐条件が成立しないことが分岐検証器２２ａにより判明すると、条件分岐命令の分岐が不成立の場合のプログラム処理手順に復帰させる。
【０１３０】
第１のスレッド実行ユニット１３は、すでに開始していた「０ｘ１６４」番地の「ｌｗ」の命令のＩＦステージの処理を中止するとともに、命令キャッシュ１０から命令を読み出した後に、レジスタ１９ａ、レジスタ１９ｂに命令及びアドレスを書き込む直前のタイミングで「０ｘ１６４」番地の「ｌｗ」の命令６８を消去（フラッシュ）する。
【０１３１】
このように、分岐予測装置１２は、分岐結果が分岐不成立の場合は、分岐条件が確定するまでプログラム処理を停止する。パイプライン制御のプロセッサは、命令の消去処理については、条件分岐命令のプログラム処理に１サイクル余分な時間が必要となる。
【０１３２】
ただし、本発明の実施の形態で示すプロセッサ１は、過去の分岐結果の履歴を利用するので、分岐予測の成功比率が失敗比率に対して高く設定されているので、プロセッサ１の処理性能が低下することを防止できる。
【０１３３】
第２のスレッド実行ユニット１４は、条件分岐命令を含むプログラムを処理する場合は、分岐予測テーブル１６を用いる点が第１のスレッド実行ユニット１３と相違するだけで、第１のスレッド実行ユニット１３と同等の動作を実行する。
【０１３４】
プロセッサ１は、複数のスレッド実行ユニットを並列動作させることでプロセッサ１の処理性能向上を図っても、処理するプログラムを複数のスレッドに分割できない場合がある。
【０１３５】
この場合は、例えば、第１のスレッド実行ユニット１３でプログラム処理を実行し、第２のスレッド実行ユニット１４が消費電力の低減などを目的に停止状態に移行させる。
【０１３６】
プロセッサ１は、停止状態の第２のスレッド実行ユニット１４に対応つけられた第２の分岐予測テーブル１６を、実行中の第１の分岐予測テーブル１５に加えて分岐予測を行うように再構成する。
【０１３７】
すなわち、第２のスレッド実行ユニット１４が停止状態の時、第１のスレッド実行ユニット１３が第１の分岐予測テーブル１５および第２の分岐予測テーブル１６を用いて分岐予測を行う。なお、第２のスレッド実行ユニット１４が停止する状況を示す停止情報は、共有フラグ１７に「１」として設定される。
【０１３８】
分岐予測装置１２は、第２のスレッド実行ユニット１４が停止状態においても、第１のスレッド実行ユニット１３でプログラムを処理し条件分岐命令の実行サイクルＣ２のＩＤステージでは、分岐命令アドレスレジスタ４０ａに記憶した条件分岐命令のアドレス番地の下位ｎ＋１ビットから下位３ビットまでを第１の分岐命令アドレスとして第１の分岐予測テーブル１５へ入力する。
【０１３９】
分岐命令アドレスレジスタ４０ａは、テーブル切替ビット１８が「０」の場合、第１の分岐予測テーブル１５を用いて、最上位ビットＭ〜最下位ビットＬまでが、読み出しアドレスとして第１の分岐予測テーブル１５に入力され、２ビット長のデータが第１の分岐予測テーブル１５から読み出され、最上位ビットＭ〜最下位ビットＬまでが、前予測アドレスレジスタ４０ｂに入力される。
【０１４０】
分岐命令アドレスレジスタ４０ａは、読み出された２ビット長のデータを出力し、選択回路４２ｂを経由して判定回路４４ａに入力させる。判定回路４４ａは、分岐予測結果を前状態レジスタ４０ｄに入力する。前予測アドレスレジスタ４０ｂと前状態レジスタ４０ｄは、ＩＤステージの終了時に分岐予測結果を書き込む。
【０１４１】
第１の分岐予測テーブル１５は、ＥＸＥステージで生成された分岐結果に基づいて内容を更新する。
【０１４２】
一方、分岐命令アドレスレジスタ４０ａは、テーブル切替ビット１８が「１」の場合は、選択回路４２ａを経由して、最上位ビットＭ〜最下位ビットＬまでが、読み出しアドレスとして第２の分岐予測テーブル１６に入力され、２ビット長のデータが第２の分岐予測テーブル１６から読み出され、前状態レジスタ４０ｅに入力される。
【０１４３】
第２の分岐予測テーブル１６は、読み出された２ビット長のデータを出力し、選択回路４２ｂ及び判定回路４４ａを経由させて分岐予測結果を出力させる。
【０１４４】
前予測アドレスレジスタ４０ｃは、ＩＤステージの終了時に分岐命令アドレスレジスタ４０ａから選択回路４２ａを通して入力データが書き込まれる。前状態レジスタ４０ｅは、ＩＤステージの終了時に第２の分岐予測テーブル１６から入力データが書き込まれる。
【０１４５】
選択回路４２ｃ及び選択回路４２ｄは、ＥＸＥステージで、前選択レジスタ４０ｆがＩＤステージで取得した保存データに基づき、第１の分岐予測テーブル１５の分岐結果を選択して状態遷移回路４３ｂへ入力し、第１の分岐命令実行信号を選択して書き込みイネーブル生成回路４４ｄへ入力し、第２の分岐予測テーブル１６の更新を実行する。
【０１４６】
第１の分岐予測テーブル１５のフィードバック処理では、テーブル切替ビット１８を「０」に設定し、第１の分岐予測テーブル１５の分岐予測結果と分岐結果に基づき第１の分岐予測テーブル１５を更新する。
【０１４７】
また、第２の分岐予測テーブル１６のフィードバック処理では、テーブル切替ビット１８を「１」に設定し、第１の分岐予測テーブル１５の分岐予測結果と分岐結果に基づき第２の分岐予測テーブル１６を更新する。
【０１４８】
第１の分岐予測テーブル１５では、分岐命令のアドレスの下位ｍビットを用いてアクセスされる。下位ｍビット分のアドレスが同一アドレスで上位ビットが異なるアドレスの条件分岐命令が実行される場合がある。
【０１４９】
この場合、分岐予測装置１２は、第１の分岐予測テーブル１５において下位ｍビット分のアドレスが同じアドレスを用いる分岐予測と分岐結果による状態遷移を行う。下位ｍビット分のアドレスが同じアドレスのときは、異なる条件分岐命令の分岐予測情報が第１の分岐予測テーブル１５で融合（マージ）されるため、分岐予測性能が低下する場合があるが、分岐予測成立の比率を向上させてプロセッサの性能を向上させることができる。
【０１５０】
本発明の実施の形態に係る分岐予測装置１２は、第２のスレッド実行ユニット１４が停止した期間、第１のスレッド実行ユニット１３が第１の分岐予測テーブル１５と第２の分岐予測テーブル１６の容量を加算した２倍のサイズの分岐予測テーブルを用いて分岐予測を行うこともできる。
【０１５１】
したがって、第１の分岐予測テーブル１５だけを用いる分岐予測に比して、条件分岐命令のアドレスが同じになる確率が半分になるため、マージによる分岐予測性能の低下を減少させることができ、プログラム処理性能のより高いプロセッサ１を少ない回路規模の増加で提供できる。
【０１５２】
ただし、本発明は、スレッド実行ユニット数を２個に限定するものではなく、３個以上のスレッド実行ユニットを設けたプロセッサをも対象とする分岐予測装置であることは上述の説明から明らかであろう。
【０１５３】
また、マルチスレッドプロセッサは、各実行サイクルの遷移期間に遅延スロットを用いた５段のパイプラインプロセッサで動作を説明したが、遅延スロットを用いない構成やパイプライン段数が異なるプロセッサにおいても、本発明の実施の形態に係る分岐予測装置に適用させることができる。
【０１５４】
図１及び図９を参照して、本発明の実施の形態に係る分岐予測装置の動作を説明する。分岐予測装置１２は、第１のスレッド実行ユニット１３から読み出しアドレスを受信するＳ７０と、読み出しアドレスに基づき第１と第２の分岐予測テーブル１５、１６をアクセスするＳ７１と、第２のスレッド実行ユニット１４の待機状態を判定するＳ７３と、第２のスレッド実行ユニット１４が待機状態の間に読み出しアドレスにより第２の分岐予測テーブル１６から、第２のスレッド実行ユニットの分岐予測情報を読み出すＳ７５、第１のスレッド実行ユニット１３へ出力するＳ７８と、を含む。
【０１５５】
このように構成すると、分岐予測装置１２は、第２のスレッド実行ユニット１４が待機中に、スレッドを実行している第１のスレッド実行ユニット１３に対して、第２の分岐予測テーブル１６から読み出した分岐予測情報を出力し、分岐命令の分岐予測精度を高めることができる。
【０１５６】
また、切替ビット判定Ｓ７４は、分岐命令アドレスレジスタ４０ａの中のテーブル切替ビット１８を判定し、例えば、値「１」を記憶している場合は、切替回路４１で第１の分岐予測テーブル１５から第２の分岐予測テーブル１６へアクセスを切り替えて、分岐予測情報を読み出すことができる。
【０１５７】
さらに、分岐予測装置１２は、分岐命令アドレスレジスタ４０ａの中の任意に定めたテーブル切替ビット１８の値と共有フラグ１７との論理積に対応させて、第１又は第２の分岐予測テーブル１５、１６の何れか一方に記憶する分岐予測情報を命令フェッチユニット２０ａへ出力することができる。
【０１５８】
さらに、第２のスレッド実行ユニット１４がスレッドを実行中の場合は、判定Ｓ７３から第１の分岐予測テーブルの読み出しＳ７６へ分岐し、第１のスレッド実行ユニットの分岐予測情報を読み出し、第１のスレッド実行ユニット１３へ送信することができる。
【０１５９】
さらに、判定回路４４ａは、Ｓ７５又はＳ７６で取得した分岐予測情報を解析し、分岐予測判定Ｓ７７を遂行する。
【０１６０】
なお、第１と第２の分岐予測テーブル１５、１６をアクセスするＳ７１において、分岐命令が読み出されない場合はＳ７２へ分岐しＰＣの値を次ぎの命令に変更する。
【０１６１】
（実施の形態の変形例１）
上述の実施の形態に用いた図１の共有フラグ１７を、プログラムにより制御し、共有フラグ１７を「１」に設定して、第１のスレッド実行ユニット１３が第１の分岐予測テーブル１５及び第２の分岐予測テーブル１６を共有する分岐予測制御を実行する。
【０１６２】
第２のスレッド実行ユニット１４は、プログラム処理が割り当てられた時に、ただちに共有フラグ１７を「０」に変更するのではなく、第２のスレッド実行ユニット１４に割り当てられるプログラムのサイズや分岐先の内容に応じて、共有フラグ１７の変更制御を実行する。
【０１６３】
第２のスレッド実行ユニット１４は、共有フラグ１７が「１」の状態で、プログラムを実行する時は、条件分岐命令の分岐先アドレスが分岐命令のアドレスより小さな場合は、常に分岐成立と判定し、固定的な分岐予測を実行する。
【０１６４】
このように第２のスレッド実行ユニット１４は、スレッド実行ユニット１４で実行されるプログラムサイズが小さな時や、プログラム処理中の条件分岐に偏り（分岐先アドレスが分岐命令のアドレスより小さい）が、プログラム作成時に判明している時に、第２の分岐予測テーブル１６を第１のスレッド実行ユニット１３の分岐予測に継続的に利用させ、プロセッサ１の処理性能を高めることができる。
【０１６５】
（実施の形態の変形例２）
図１の共有フラグ１７を複数ビットに拡張して、共有する分岐予測テーブルを使用するスレッド実行ユニットの情報を付加する。図１の分岐予測装置１２の分岐アドレスや選択回路４２などは、付加された分岐予測情報が示す追加のスレッド実行ユニットからの分岐アドレスが、共有状態の分岐予測テーブル（例えば、第１又は第２若しくは追加の分岐予測テーブル）に入力されて分岐予測結果を出力させ分岐結果の書き込みが可能な拡張された分岐予測テーブルを提供し、分岐予測精度を高めることができる。
【０１６６】
このように拡張された分岐予測テーブルを備えることで、第１のスレッド実行ユニット１３以外の第２のスレッド実行ユニット１４又は追加のスレッド実行ユニットにおいても共有する拡張された分岐予測テーブルを用いて分岐予測の精度の向上を図ることができ、プロセッサ１の処理性能を高めるだけでなく、プログラムをどのスレッド実行ユニットに割り当てるかの柔軟性が向上してプログラム制御の容易性が高まる。
【０１６７】
なお、本発明の実施例に記載された、作用及び効果は、本発明から生じる最も好適な作用及び効果を列挙したに過ぎず、本発明による作用及び効果は、本発明の実施の形態に記載されたものに限定されるものではない。
【０１６８】
例えば、マルチスレッド方式のプロセッサ１は、第１及び第２のスレッド実行ユニット１３、１４が分岐予測テーブル１５、１６を用いて動的（プログラム実行中）に分岐予測を行う分岐予測装置１２は、第１のスレッド実行ユニット１３を対象とする第１の分岐予測テーブル１５と、第２のスレッド実行ユニット１４を対象とする第２の分岐予測テーブル１６と、を備え、第２のスレッド実行ユニット１４が第２の分岐予測テーブル１６を使用しない時に、第１のスレッド実行ユニット１３が、第１および第２の分岐予測テーブル１５、１６を用いて分岐予測を行うように制御する。
【０１６９】
また、マルチスレッド方式のプロセッサ１の第１及び第２のスレッド実行ユニット１３、１４が分岐予測手段を用いて動的に分岐予測を行わせる分岐予測方法は、第１のスレッド実行ユニット１３と第２のスレッド実行ユニット１４が動的（プログラム実行中）に分岐予測を行わせる時に、分岐予測手段を少なくとも第１の分岐予測テーブル１５と第２の分岐予測テーブル１６に分割し、第１のスレッド実行ユニット１３に第１の分岐予測テーブル１５を用いる分岐予測を実行させ、第２のスレッド実行ユニット１４に第２の分岐予測テーブル１６を用いる分岐予測を実行させ、第１のスレッド実行ユニット１３に動的（プログラム実行中）に分岐予測を行わせ、第２のスレッド実行ユニット１４に動的（プログラム実行中）に分岐予測を行わせない時に、第１のスレッド実行ユニット１３に、第１及び第２の分岐予測テーブル１５、１６用いる動的な分岐予測を実行させる。
【０１７０】
さらに、分岐予測を行う第１のスレッド実行ユニット１３が動的（プログラム実行中）に分岐予測を行うことを実行中のプログラムで制御する。
【図面の簡単な説明】
【０１７１】
【図１】本発明の実施の形態に係る分岐予測装置のブロック図。
【図２】本発明の実施の形態に係る分岐予測装置を備えたプロセッサのブロック図。
【図３】本発明の実施の形態に係る分岐予測装置を備えたプロセッサの動作フロー図。
【図４】本発明の実施の形態に用いる命令フェッチユニットのブロック図。
【図５】本発明の実施の形態に係る分岐予測装置のブロック図。
【図６】本発明の実施の形態に係る分岐予測装置に用いる分岐予測情報の状態遷移図。
【図７】本発明の実施の形態に係る分岐予測装置のタイミングチャート。
【図８】本発明の実施の形態に係る分岐予測装置のタイミングチャート。
【図９】本発明の実施の形態に係る分岐予測装置のフローチャート。
【符号の説明】
【０１７２】
１０…命令キャッシュ
１１…スレッド管理部
１２…分岐予測装置
１３…第１のスレッド実行ユニット
１４…第２のスレッド実行ユニット
１５…第１の分岐予測テーブル
１６…第２の分岐予測テーブル
１７…共有フラグ
１８…テーブル切替ビット
２０ａ…命令フェッチユニット
２０ｂ…命令フェッチユニット
２１ａ…命令デコーダ
２１ｂ…命令デコーダ
２２ａ…分岐検証器
２２ｂ…分岐検証器
２３…外部メモリ
３０…加算器
３１…アドレスレジスタ
３２…ＡＮＤ回路
３３…選択回路
３４…選択回路
４０…アドレスレジスタ
４０ａ…分岐命令アドレスレジスタ
４０ｂ…前予測アドレスレジスタ
４０ｃ…前予測アドレスレジスタ
４０ｄ…アドレスレジスタ
４０ｅ…前状態レジスタ
４０ｆ…前選択レジスタ
４０ｇ…分岐命令アドレスレジスタ
４１…切替回路
４２、４２ａ〜４２ｄ…選択回路
４３ａ、４３ｂ…状態遷移回路
４４ａ、４４ｂ…判定回路
４４ｃ、４４ｄ…イネーブル生成回路
【図１】
2006053830.tif 000003
【図２】
2006053830.tif 000004
【図３】
2006053830.tif 000005
【図４】
2006053830.tif 000006
【図５】
2006053830.tif 000007
【図６】
2006053830.tif 000008
【図７】
2006053830.tif 000009
【図８】
2006053830.tif 000010
【図９】
2006053830.tif 000011