演算処理装置及び演算処理装置の制御方法
【課題】効率的なスレッド選択を可能にする演算処理装置を提供することを課題とする。
【解決手段】複数のスレッドの命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して複数のスレッドのアドレスを出力する第１のセレクタ（ＳＬ１〜ＳＬｎ）と、第１のセレクタが出力した複数のスレッドのアドレスのうち１個を選択する第２のセレクタ（３１３）と、第１のサイクルステージで、第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を選択されたアドレスに基づき予測して出力するとともに、第１のサイクルステージより後の第２のサイクルステージで、予測対象の分岐命令の分岐先アドレスを選択されたアドレスに基づき予測して出力する分岐予測回路（２０４）と、分岐予測回路が出力した分岐方向に基づき、第１セレクタ及び第２のセレクタによるスレッドのアドレスの選択を制御するスレッド調停回路（３１１）とを有する。
【解決手段】複数のスレッドの命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して複数のスレッドのアドレスを出力する第１のセレクタ（ＳＬ１〜ＳＬｎ）と、第１のセレクタが出力した複数のスレッドのアドレスのうち１個を選択する第２のセレクタ（３１３）と、第１のサイクルステージで、第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を選択されたアドレスに基づき予測して出力するとともに、第１のサイクルステージより後の第２のサイクルステージで、予測対象の分岐命令の分岐先アドレスを選択されたアドレスに基づき予測して出力する分岐予測回路（２０４）と、分岐予測回路が出力した分岐方向に基づき、第１セレクタ及び第２のセレクタによるスレッドのアドレスの選択を制御するスレッド調停回路（３１１）とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
まず、演算処理装置であるパイプラインプロセッサと分岐予測について説明する。パイプライン化されたプロセッサ（パイプラインプロセッサ）の単純な実装では、プログラム実行中に分岐命令を実行した場合、命令フェッチから分岐命令実行までのパイプラインステージの段数分のクロックサイクルだけ、パイプラインが停止（ストール）し、パイプライン処理の効率が低下する。
【０００３】
これを防ぐため、パイプラインプロセッサでは、分岐命令をフェッチした場合、分岐先の命令アドレスもしくは、分岐方向として分岐する場合にはtakenと予想し又は分岐しない場合はnot takenと予想し、もしくは、これらtakenとnot takenの両方を予測し、分岐命令の実行完了を待たずに命令フェッチを続行する分岐予測処理が行われることが一般的である。分岐予測により、プロセッサのパイプラインに命令を流し続けることでパイプラインの処理効率を向上させることができる。
【０００４】
分岐予測には、分岐先予測又は分岐方向予測又はそれら両方を含む。分岐先予測とは、ある分岐命令の次に実行される命令（分岐先命令）の命令アドレスを予測することである。分岐方向予測とは、ある分岐命令が分岐する（taken）か分岐しない（not-taken）かを予測することである。分岐予測方式の一例としては、特許文献１が知られている。
【０００５】
分岐予測の方式には、分岐予測レイテンシが小さいが分岐予測精度の劣る静的分岐予測と、分岐予測レイテンシが大きいが分岐予測精度の高い動的分岐予測とがある。静的分岐予測とは、例えば、後続アドレスを単純に読み込む（not-takenと仮定）、あるいは、命令コード上の予測ビットを利用するといったものである。動的分岐予測とは、実行したプログラムの過去の分岐履歴を参照し、プログラムの分岐の挙動の規則性を用いて実行の完了していない分岐命令による分岐方向又は分岐先命令アドレス又はそれら両方を予測するものである。
【０００６】
動的分岐予測は大規模履歴を利用するなど、動的分岐予測を使用しない場合よりも複雑な回路を必要とし、複数クロックサイクルを分岐予測完了まで要することが普通である。パイプライン段数や同時命令実行数の多いプロセッサコアでは、分岐予測の失敗による性能、電力面での効率低下は大きく、予測精度の高い動的分岐予測回路を用いることが一般的である。
【０００７】
次に、マルチスレッディングについて説明する。１９６０年ごろより、レイテンシの長い演算器を効率的に利用するため、パイプライン化し、複数スレッドで時分割多重化して用いるシステムが登場している。
【０００８】
現代のコンピュータシステムでは、プロセッサ内での演算レイテンシと比較して、メモリ読み書きにかかる時間であるメモリレイテンシが大きくなっており、メモリレイテンシを隠蔽してプロセッサのスループットを向上させる手段として、ハードウエアによるマルチスレッド処理方式であるハードウエアマルチスレッディングを採用することが、スループット指向のプロセッサで一般化している。
【０００９】
スレッドを実行するハードウエア資源であるハードウエアスレッド（ストランドとも呼ばれる）とは、プロセッサコア内に１セット以上保持される、アーキテクチャ状態及びそれより派生するプロセッサ状態のことを指す。したがって、殆どの場合、命令フェッチ部の処理で扱われる命令フェッチアドレスは、スレッド毎に異なる値を持つ。
【００１０】
ハードウエアマルチスレッディングとは、単一プロセッサコア内部で、複数のハードウエアスレッドをサイクル単位の時分割で切り替え、又は、同一サイクル内で同時に処理する方式である。
【００１１】
マイクロアーキテクチャに関する用語のハードウエアスレッドやマルチスレッディングと、オペレーティングシステムなどソフトウエア関連分野の用語のスレッドやマルチスレッディングとでは定義が異なることが普通である。以降、前述の意味で用いる。
【００１２】
複数スレッドの命令を並列実行することで、複数スレッド間での演算器利用の効率向上、あるいは、複数スレッド間でのメモリアクセスと演算器利用との平行（オーバラップ）化が実現され、プロセッサのスループットが向上する。
【００１３】
複数スレッドを平行して処理するために、ハードウエアで複数スレッドを処理するプロセッサ（マルチスレッドプロセッサ）では、命令フェッチの段階ではサイクル単位で、対象とするスレッドを切り替えて命令をフェッチすることが一般的である。フェッチするスレッドを切り替える時間的単位は最小で１クロックサイクルであり、それより時間的粒度が大きい方式もある。前者は一般にＦＧＭＴ（Fine-grained multithreading）などと呼ばれ、後者はＶＭＴ（Vertical multithreading）又はＣＧＭＴ（Coarse-grained multithreading）などと呼ばれる。
【００１４】
命令フェッチ部のスレッド切り替え（スレッドスケジューリング）の方式としては、例えば、ラウンドロビンで行う方式がある。これは、スケジュールするスレッドをサイクル毎に予め決めておいた順番で切り替えていく方法である。
【００１５】
また、インタリーブされた複数の命令スレッドを優先規則に従ってサイクル単位で処理するデータ・プロセッサであって、命令スレッドに関連した事象又は条件に基づいて、特定の命令スレッドに割り当てられた優先度を調整するプロセッサが知られている（例えば、特許文献２参照）。
【００１６】
また、インタリーブされた複数の命令スレッドを優先規則に従ってサイクル単位で処理するデータ・プロセッサであって、命令スレッドに関連した事象又は条件に基づいて処理する、特定の命令スレッドを選択するプロセッサが知られている（例えば、特許文献３参照）。
【００１７】
また、複数の命令スレッドを処理する能力を有するプロセッサであって、処理のために命令スレッドをインタリーブする方法にランダム化を導入し、同時に命令スレッド間のインタリービングの全体的な比率又は程度をある所望の比率又は程度に維持するプロセッサが知られている（例えば、特許文献４参照）。
【００１８】
また、条件分岐命令の次に、どの命令を実行するかを予測し、あらかじめその命令列を読み込んでおくことが可能な分岐予測機構を備えた計算機装置において、分岐予測機構に加えて、条件分岐方向のヒントを得る手段と、特定の命令の実行結果から条件分岐方向のヒントを取得する手段と、上記ヒントを分岐予測装置に伝える手段と、ヒントに従って分岐方向を決定する手段を設けた分岐予測装置が知られている（例えば、特許文献５参照）。
【００１９】
また、マルチスレッディングプロセッサにおけるスケジューリング方法であって、実行可能な複数のスレッドを割り当て、実行するスレッド数をマルチスレッディングプロセッサの動作状態に応じて動的に決定し、割り当てられた複数スレッドから決定された数のスレッドを選択し、同一期間内に選択されたスレッドの命令をフェッチし実行するスケジューリング方法が知られている（例えば、特許文献６参照）。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開平６−８９１７３号公報
【特許文献２】特許第４１７９５５５号公報
【特許文献３】特許第４０８６８０８号公報
【特許文献４】特許第４０８６８０９号公報
【特許文献５】特開２００１−５６６５号公報
【特許文献６】国際公開第０４／０４４７４５号
【発明の概要】
【発明が解決しようとする課題】
【００２１】
まず、レイテンシの課題を説明する。命令フェッチを時分割でスレッドごとに行うパイプラインプロセッサでは、あるスレッドの命令フェッチ開始から分岐予測の結果が出るまでのレイテンシと、時分割で起こるスレッド切り替えのタイミングが合わない場合がある。スレッド切り替えのタイミングが合わない場合とは、あるスレッドの分岐予測結果が出ていても、分岐予測結果を受け取って命令フェッチを行うパイプラインステージが別のスレッドを処理している場合である。パイプラインステージが別のスレッドを処理している場合、分岐予測結果が即座に使われず、分岐予測レイテンシが余計に延びる結果となる。分岐予測レイテンシが延びることが原因で、当該スレッドの実行サイクル数が増大しうる。例えば、純粋なラウンドロビン方式のスレッドスケジューリングを用いた場合で、分岐予測レイテンシのサイクル数が、ハードウエアスレッド数の倍数でない場合、分岐予測結果が次の命令フェッチに利用されるまでのサイクル数が、ハードウエアマルチスレッディング動作を行ったことにより、単一スレッド動作を行った場合と比較して、増大する。
【００２２】
次に、スループットの課題を説明する。分岐方向を先見しない従来方式でスレッドスケジューリングを行うプロセッサコアでは、命令フェッチ開始から分岐予測結果が出るまでのサイクル数（分岐予測レイテンシ）が、ハードウエアで扱うスレッド数より大きい場合は、分岐予測レイテンシの全てをハードウエアマルチスレッディングによって隠蔽することはできない。そのため、動的分岐予測器による分岐予測結果をすぐに命令フェッチに用いることができず、パイプラインがストール、あるいは、動的分岐予測器によらない低レイテンシだが不正確な静的分岐予測を用いざるを得なくなる。不正確な分岐予測を用いることで、不必要な命令フェッチが起こる可能性が高まり、命令フェッチスループットが低下する。命令フェッチスループットの低下は、プロセッサ全体の命令実行効率をも低下させうる。動的分岐予測完了が間に合わなかった場合にアドレスが連続する後続命令をフェッチする（分岐しないと仮定する）静的分岐予測制御を用いるマルチスレッドプロセッサでは、分岐しないと予測していた場合に、分岐命令の実際の実行結果が分岐するであった場合は、命令フェッチパイプラインのスループットを浪費する。予測された分岐方向が分岐する場合、次のアドレスの後続命令をフェッチしても実行されることはなく、その後続命令のパイプライン処理をキャンセルして予測された分岐先命令のフェッチをやり直すため、必ず無駄となる。これによりマルチスレッドプロセッサではスループット性能の低下を起こし、また、電力を空費する結果となる。
【００２３】
また、プロセッサ内部には、キャッシュ、ＴＬＢ（Translation Lookaside Buffer）、分岐履歴表などの、命令フェッチ履歴により内容が蓄積される記憶資源を持つことが一般的である。これらの記憶資源が不正確な命令フェッチにより内容が汚染され、プロセッサの性能低下につながる可能性がある。
【００２４】
１つの側面では、本発明は、効率的なスレッド選択を可能にすることを目的とする。
【課題を解決するための手段】
【００２５】
演算処理装置は、複数のスレッドの命令を複数のサイクルステージ毎に実行する演算処理装置において、入力した複数のスレッドの命令の命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して、前記複数のスレッドのアドレスを出力する第１のセレクタと、前記第１のセレクタが出力した複数のスレッドのアドレスのうち、いずれか１個のスレッドのアドレスを選択する第２のセレクタと、前記複数のサイクルステージのうち第１のサイクルステージで、前記第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を前記選択されたアドレスに基づき予測して出力するとともに、前記第１のサイクルステージより後の第２のサイクルステージで、前記予測対象の分岐命令の分岐先アドレスを前記選択されたアドレスに基づき予測して出力する分岐予測回路と、前記分岐予測回路が出力した前記分岐方向に基づき、前記第１セレクタ及び第２のセレクタによるスレッドのアドレスの選択を制御するスレッド調停回路と、を有する。
【発明の効果】
【００２６】
演算処理装置において、効率的なスレッド選択が可能となる。
【図面の簡単な説明】
【００２７】
【図１】実施形態による情報処理装置の構成例を示す図である。
【図２】演算処理装置の構成例を示す図である。
【図３】参考技術による命令フェッチ部及び分岐予測回路の構成例を示す図である。
【図４】図３の演算処理装置のパイプライン処理例を示す図である。
【図５】本実施形態による命令フェッチ部及び分岐予測回路の構成例を示す図である。
【図６】図５の演算処理装置のパイプライン処理例を示す図である。
【図７】図５の演算処理装置の他のパイプライン処理例を示す図である。
【図８】命令フェッチ部及び一次命令キャッシュの構成例を示す図である。
【図９】図５の分岐方向予測回路の構成例を示す図である。
【図１０】図５の分岐方向予測回路の他の構成例を示す図である。
【図１１】図５のスレッド調停回路の構成例を示す図である。
【図１２】図５のスレッド調停回路の他の構成例を示す図である。
【発明を実施するための形態】
【００２８】
図１は、実施形態による情報処理装置の構成例を示す図である。情報処理装置は、例えば、マルチスレッド演算処理装置（プロセッサ）１０１をサーバなどに組み込んだシステムであり、複数の演算処理装置１０１、複数のメモリ１０２、及びインターコネクト制御部１０３を有する。演算処理装置１０１は、例えば中央演算処理装置（ＣＰＵ）であり、インターコネクト制御部１０３に接続される。複数の演算処理装置１０１には、それぞれ、複数のメモリ１０２が接続される。インターコネクト制御部１０３は、外部装置１０４に対して入出力制御を行う。
【００２９】
図２は、演算処理装置１０１の構成例を示す図である。演算処理装置１０１は、アウトオブオーダ実行及びパイプライン機能を有する。命令フェッチステージ２２１では、命令フェッチ部２０３、命令バッファ２０６、分岐予測回路２０４、一次命令キャッシュ２０５及び二次キャッシュ２０２などが動作する。
【００３０】
命令フェッチ部２０３は、分岐予測回路２０４から入力したフェッチする命令の予測分岐先アドレス、分岐制御部２１１から入力した分岐演算により確定した分岐先アドレス、及び命令フェッチ部２０３内で生成した分岐しない場合のフェッチする命令の連続した次のアドレスのうちから１つのアドレスを選択し、次の命令フェッチアドレスを確定する。命令フェッチ部２０３は、確定した命令フェッチアドレスを一次命令キャッシュ２０５に出力し、該当するアドレスから命令コードをフェッチする。一次命令キャッシュ２０５は、二次キャッシュ２０２の一部の情報を格納し、二次キャッシュ２０２はメモリ１０２（図１）の一部の情報を格納している。一次命令キャッシュ２０５に該当するアドレスのデータが存在しない場合は二次キャッシュ２０２から、二次キャッシュ２０２に該当するデータが存在しない場合はメモリ１０２からデータをフェッチする。本実施形態では、メモリ１０２は演算処理装置１０１の外部に配置しているため、外部にあるメモリ１０２との入出力制御はメモリコントローラ２０１を介して行われる。一次命令キャッシュ２０５、二次キャッシュ２０２、又はメモリ１０２の該当するアドレスからフェッチされた命令コードは、命令バッファ２０６に格納される。
【００３１】
分岐予測回路２０４は、上記の命令フェッチと並行して分岐予測を実行する。分岐予測回路２０４は、命令フェッチ部２０３から出力された命令フェッチアドレスを入力し、それを基に分岐予測を行い、分岐する又は分岐しないを示す分岐方向と分岐先アドレスとを命令フェッチ部２０３に出力する。命令フェッチ部２０３は、予測された分岐方向が分岐する旨を示す場合に、次の命令フェッチアドレスとして、予測された分岐先アドレスを選択する。分岐しない旨の分岐方向が予測された場合は、連続した次のアドレスが命令フェッチアドレスとして選択される。
【００３２】
命令発行ステージ２２２では、命令デコーダ２０７、命令発行制御部２０８が動作する。命令デコーダ２０７は、命令バッファ２０６から命令コードを受け取り、命令の種別や必要な実行資源などを解析し、解析結果を命令発行制御部２０８に出力する。命令発行制御部２０８は、リザベーションステーションの構造を持ち、命令で参照するレジスタなどの依存性を見て、依存性のあるレジスタの更新状況や同じ演算器などの実行資源を用いる命令の実行状況などから、実行資源が命令を実行可能かどうかを判断し、実行可能なら各実行資源に対してレジスタ番号やオペランドアドレスなど命令実行に必要な情報を、一次オペランドキャッシュ２０９及び演算器２１０に出力する。また、命令発行制御部２０８は、実行可能となるまで命令を格納しておくバッファの役割も担う。
【００３３】
命令実行ステージ２２３では、演算器２１０、一次オペランドキャッシュ２０９、分岐制御部２１１などの実行資源が動作する。演算器２１０は、必要に応じてレジスタ２１２や一次オペランドキャッシュ２０９からデータを入力し、四則演算や論理演算、三角関数演算、アドレス計算などの命令に対応した演算を実行し、演算結果をレジスタ２１２やキャッシュ２０９に出力する。一次オペランドキャッシュ２０９は、一次命令キャッシュ２０５と同様に、二次キャッシュ２０２の一部の情報を格納しているものであり、ロード命令によりメモリ１０２（図１）から演算器２１０又はレジスタ２１２へデータをロードし、ストア命令により演算器２１０又はレジスタ２１２からメモリ１０２へデータをストアする。各実行資源は、命令実行の完了通知を命令完了制御部２１３へ出力する。
【００３４】
分岐制御部２１１は、命令デコーダ２０７から分岐命令の種別を入力し、演算器２１０から分岐先アドレスや分岐条件となる演算の結果を入力し、演算結果が分岐条件を満たしていれば分岐する、満たしていなければ分岐しないことの判断を行い、分岐方向を確定する。また、分岐制御部２１１は、演算結果と分岐予測時の分岐先アドレスと分岐方向が一致するかどうかの判断や、分岐命令の順序関係の制御も行う。分岐制御部２１１は、演算結果と予測とが一致した場合は命令完了制御部２１３へ分岐命令の完了通知を出力する。また、分岐制御部２１１は、演算結果と予測とが一致しなかった場合は分岐予測失敗を意味するので、命令完了制御部２１３へ分岐命令の完了通知と共に後続命令のキャンセル及び再命令フェッチ要求を出力する。
【００３５】
命令完了ステージ２２４では、命令完了制御部２１３、レジスタ２１２、分岐履歴更新部２１４が動作する。命令完了制御部２１３は、各命令実行資源から入力した完了通知を基に、コミットスタックエントリに格納された命令コード順に命令完了処理を行い、レジスタ２１２の更新指示を出力する。レジスタ２１２は、命令完了制御部２１３からレジスタ更新指示を入力すると、演算器２１０や一次オペランドキャッシュ２０９から入力する演算結果のデータを基にレジスタ２１２の更新を実行する。分岐履歴更新部２１４は、分岐制御部２１１から入力する分岐演算の結果を基に、分岐予測回路２０４の履歴更新データを生成し、分岐予測回路２０４に出力し、分岐予測回路２０４の履歴データの更新を実行する。
【００３６】
図３は、参考技術による命令フェッチ部２０３及び分岐予測回路２０４の構成例を示す図である。命令フェッチ部２０３は、第１のセレクタＳＬ１〜ＳＬｎ、パイプラインレジスタＲＧ１〜ＲＧｎ、スレッド調停回路３１１、パイプラインレジスタ３１２及び第２のセレクタ３１３を有する。分岐予測回路２０４は、大規模履歴テーブル３２１、パイプラインレジスタ３２２及び分岐予測論理回路３２３を有する。命令フェッチステージ２２１では、パイプライン処理により分岐予測を行う。分岐予測レイテンシが、Ａステージ３０１、Ｔステージ３０２及びＭステージ３０３の３サイクルである命令フェッチパイプラインの一例を示す。Ａステージ３０１では、命令アドレス生成が行われる。Ｔステージ３０２では、分岐先アドレスの履歴読み出しが行われる。Ｍステージ３０３では、分岐予測の完了処理が行われる。命令フェッチステージ２２１のパイプライン段数やパイプラインレジスタの位置、パイプラインステージの機能、ハードウエアスレッド数などは任意に構成されうる。
【００３７】
ｎ個の第１のセレクタＳＬ１〜ＳＬｎは、スレッド調停回路３１１の制御により、それぞれ、ｎ個のスレッドの命令アドレスＡＡ１〜ＡＡｎ又は分岐先アドレスＡＤを選択し、ｎ個のスレッドのアドレスＡＢ１〜ＡＢｎを出力する。ここで、ｎは２以上の整数である。例えば、セレクタＳＬ１は、第１のスレッドの命令アドレスＡＡ１及び分岐先アドレスＡＤを入力し、第１のスレッドのアドレスＡＢ１を出力する。セレクタＳＬ２は、第２のスレッドの命令アドレスＡＡ２及び分岐先アドレスＡＤを入力し、第２のスレッドのアドレスＡＢ２を出力する。ｎ個のパイプラインレジスタＲＧ１〜ＲＧｎは、それぞれ、フリップフロップで構成され、クロック信号に同期して、ｎ個のスレッドのアドレスＡＢ１〜ＡＢｎをラッチして出力する。スレッド調停回路３１１は、ｎ個のスレッドのうちの次にフェッチする命令のスレッド番号ＳＮを出力する。パイプラインレジスタ３１２は、クロック信号に同期して、スレッド番号ＳＮをラッチして出力する。
【００３８】
Ａステージ３０１では、第２のセレクタ３１３は、ｎ個のスレッドのアドレスＡＢ１〜ＡＢｎの中から、スレッド番号ＳＮが示す１個のスレッドの命令アドレスＡＣを選択して出力する。命令アドレスＡＣは、フェッチするアドレスであり、一次命令キャッシュ２０５へ出力されるとともに、次の分岐予測に用いるために、パイラインレジスタを介して分岐予測回路２０４に出力される。
【００３９】
Ｔステージ３０２では、分岐予測回路２０４が動的分岐予測を行う。具体的には、分岐予測回路２０４内の大規模履歴テーブル３２１は、分岐命令の命令アドレスＡＣに対する分岐方向及び分岐先アドレスの履歴情報を記憶し、命令アドレスＡＣに応じた分岐方向及び分岐先アドレスをパイプラインレジスタ３２２に出力する。大規模履歴テーブル３２１は、高い分岐予測精度と引き換えに予測結果が出るまで、長いレイテンシを必要とする。パイプラインレジスタ３２２は、クロック信号に同期して、分岐方向及び分岐先アドレスをラッチして出力する。
【００４０】
Ｍステージ３０３では、分岐予測回路２０４内の分岐予測論理回路３２３は、パイプラインレジスタ３２２から分岐命令の分岐方向及び分岐先アドレスを入力し、スレッド選択情報ＳＩをスレッド調停回路３１１に出力し、分岐命令の分岐先アドレスＡＤを第１のセレクタＳＬ１〜ＳＬｎに出力する。スレッド選択情報ＳＩは、分岐方向及びその分岐命令のスレッド番号ＳＮを含む。
【００４１】
第１のセレクタＳＬ１〜ＳＬｎは、スレッド調停回路３１１の制御により、スレッド選択情報ＳＩ内の分岐方向が分岐する旨を示す場合は、分岐先アドレスＡＤを選択し、スレッド選択情報ＳＩ内の分岐方向が分岐しない旨を示す場合は、後続の命令アドレスＡＡ１〜ＡＡｎを選択する。
【００４２】
また、スレッド調停回路３１１は、スレッド選択情報ＳＩ内のスレッド番号ＳＮをパイプラインレジスタ３１２に出力する。パイプラインレジスタ３１２は、クロック信号に同期して、スレッド番号ＳＮをラッチして出力する。第２のセレクタ３１３は、パイプラインレジスタ３１２が出力するスレッド番号ＳＮに応じて、アドレスＡＢ１〜ＡＢｎの中から１つを選択し、命令アドレスＡＣとして出力する。例えば、第２のセレクタ３１３は、スレッド番号ＳＮが１番のときには、第１のスレッドのアドレスＡＢ１を選択し、スレッド番号ＳＮが２番のときには、第２のスレッドのアドレスＡＢ２を選択する。
【００４３】
図４は、図３の演算処理装置１０１のパイプライン処理例を示す図である。ここでは、演算処理装置１０１が第１のスレッド及び第２のスレッドの２スレッドを切り替えてフェッチし、フェッチ開始から分岐先アドレスＡＤの確定までのレイテンシが３サイクルである例を示す。右方向の矢印は時間順を示し、下方向の矢印は命令の処理順を示す。
【００４４】
第１のスレッドは、分岐命令Ａ、後続命令Ｂ及び分岐先命令Ｃを有する。第２のスレッドは、命令Ｘ及び命令Ｙを有する。第１のスレッドと第２のスレッドとの間には制御依存関係はなく、性能に対する影響を除き、実行結果に影響を与えることなく、自由にスレッド選択できる。この例では、第１のスレッドと第２のスレッドを交互に命令フェッチしている。具体的には、命令フェッチは、分岐命令Ａ（第１のスレッド）、命令Ｘ（第２のスレッド）、後続命令Ｂ（第１のスレッド）、命令Ｙ（第２のスレッド）、分岐先命令Ｃ（第１のスレッド）の順で行われる。
【００４５】
後続命令Ｂ（第１のスレッド）は、分岐命令Ａ（第１のスレッド）の命令アドレスに連続した次のアドレスにある命令であり、分岐命令Ａ（第１のスレッド）の実行結果により分岐しない場合に実行される命令である。分岐先命令Ｃ（第１のスレッド）は、分岐命令Ａ（第１のスレッド）の実行結果により分岐する場合に実行される分岐先アドレスの命令である。
【００４６】
まず、時刻ｔ１において、着目する分岐命令ＡのＡステージ３０１が実行される。
【００４７】
次に、時刻ｔ２において、分岐命令ＡのＴステージ３０２が実行され、命令ＸのＡステージ３０１が実行される。
【００４８】
次に、時刻ｔ３では、分岐命令ＡのＭステージ３０３が実行され、命令ＸのＴステージ３０２が実行され、後続命令ＢのＡステージ３０１が実行される。分岐命令ＡのＭステージ３０３でスレッド選択情報ＳＩ及び分岐先アドレスＡＤが確定し、時刻ｔ５で分岐先命令ＣをＡステージ３０１でフェッチ開始することが可能になる。例えば、スレッド選択情報ＳＩが分岐する旨を示す場合を例に説明する。
【００４９】
時刻ｔ３では、分岐先アドレスＡＤが確定しておらず、分岐先命令Ｃを命令フェッチすることは不可能である。そのため、時刻ｔ３では、分岐しないと仮定する静的分岐予測により、後続命令Ｂをフェッチしている。
【００５０】
時刻ｔ４で、後続命令ＢがＡステージ３０１の終了の際に、分岐命令Ａの分岐先予測が完了し、分岐先アドレスＡＤが確定し、後続命令Ｂではなく、分岐先命令Ｃが次の命令であると予測される。このため、時刻ｔ４では、後続命令Ｂはキャンセルされる。
【００５１】
なお、時刻ｔ３で、第２のスレッドの命令ＹのＡステージ３０１を実行する場合、後続命令Ｂのキャンセルは回避されるが、後続命令ＢのＡステージ３０１の時点で分岐予測結果が出ておらず、分岐予測結果を用いて第２のスレッドをスケジュールし、意図的にキャンセルを回避することは不可能である。
【００５２】
時刻ｔ４では、スレッド選択情報ＳＩが分岐する旨を示すので、後続命令Ｂがキャンセルされ、分岐命令ＡのＢステージ３０４（図８）が実行され、命令ＸのＭステージ３０３が実行され、命令ＹのＡステージ３０１が実行される。ここで、Ｂステージ３０４は、命令を後段に伝送するステージである。
【００５３】
次に、時刻ｔ５では、命令ＸのＢステージ３０４が実行され、命令ＹのＴステージ３０２が実行され、分岐先命令ＣのＡステージ３０１が実行される。
【００５４】
次に、時刻ｔ６では、命令ＹのＭステージ３０３が実行され、分岐先命令ＣのＴステージ３０２が実行される。
【００５５】
次に、時刻ｔ７では、命令ＹのＢステージ３０４が実行され、分岐先命令ＣのＭステージ３０３が実行される。
【００５６】
次に、時刻ｔ８では、分岐先命令ＣのＢステージ３０４が実行される。
【００５７】
なお、時刻ｔ４では、分岐先アドレスＡＤの予測結果が出ているため、命令Ｙではなく分岐先命令ＣのＡステージ３０１を実行することも可能である。その場合は、第２のスレッドの命令ＹのＡステージ３０１が遅れ、第１のスレッドの命令フェッチ状態に悪影響を与えることになる。
【００５８】
上記の例では、第２のスレッドの命令Ｙではなく、第１のスレッドの分岐先命令Ｃを遅らせるスケジューリング結果となっている。いずれの場合でも、後続命令Ｂのフェッチにより上から３つ目の命令スロットを消費したことにより、第１のスレッド又は第２のスレッドのいずれかの命令フェッチが遅れることになる。
【００５９】
図５は、本実施形態による命令フェッチ部２０３及び分岐予測回路２０４の構成例を示す図である。図５の演算処理装置１０１は、図３の演算処理装置１０１に対して、分岐方向予測回路５０１を追加したものである。以下、図５の演算処理装置１０１が図３の演算処理装置１０１と異なる点を説明する。
【００６０】
分岐方向予測回路５０１は、分岐予測回路２０４内に設けられ、小規模履歴テーブル５０２、分岐方向予測論理回路５０３及びパイプラインレジスタ５０４を有する。Ｔステージ３０２では、小規模履歴テーブル５０２は、代表的な一部の分岐命令の命令アドレスＡＣに対する分岐方向の履歴情報を記憶し、命令アドレスＡＣに応じた分岐方向を分岐方向予測論理回路５０３に出力する。分岐方向予測論理回路５０３は、小規模履歴テーブル５０２が出力する分岐方向を基に分岐方向ＢＤを出力する。パイプラインレジスタ５０４は、クロック信号に同期して、パイプラインレジスタ３１２が出力するスレッド番号ＳＮをラッチして出力する。スレッド選択情報ＳＩは、分岐方向予測論理回路５０３が出力する分岐方向ＢＤ及びフリップフロップ５０４が出力するスレッド番号ＳＮを含み、スレッド調停回路３１１に入力される。次に、Ｍステージ３０３では、分岐予測論理回路３２３は、分岐先アドレスＡＤを第１のセレクタＳＬ１〜ＳＬｎに出力する。
【００６１】
Ｔステージ３０２における分岐方向予測論理回路５０３が出力する分岐方向ＢＤは、Ｍステージ３０３における分岐予測論理回路３２３が出力する分岐先アドレスＡＤよりも先に結果が出ている。分岐方向ＢＤは、スレッド番号ＳＮと共に、スレッド調停回路３１１に入力され、次に命令フェッチを行うスレッドが決定される。これにより、分岐することが予測される分岐命令のスレッドをスケジュールしないことが可能となる。その詳細は、後に図６を参照しながら説明する。
【００６２】
本実施形態では、大規模履歴テーブル３２１を有する図３の分岐予測回路２０４よりも低レイテンシの分岐方向予測回路５０１を設ける。小規模履歴テーブル５０２は、１つ以上の少数の分岐命令の分岐方向（分岐先）を記憶するエントリを記憶する。これにより、小規模履歴テーブル５０２に保持したエントリにヒットする場合において、分岐方向予測のレイテンシを短縮し、分岐命令のフェッチ開始から命令フェッチのスレッド選択に反映されるまでのレイテンシを短縮する。
【００６３】
小規模履歴テーブル５０２及び大規模履歴テーブル３２１は、図２の分岐履歴更新部２１４により更新される。記憶素子としての小規模履歴テーブル５０２と大規模履歴テーブル３２１との特性には、素子遅延と記憶密度との間で利害得失がある。小規模履歴テーブル５０２の記憶素子は、大規模履歴テーブル３２１の記憶素子に対して、遅延時間が短いが、記憶密度（回路量に対するデータ容量）が低い。大規模履歴テーブル３２１は、小規模履歴テーブル５０２に対して遅延が大きいが、記憶密度が高い。性能向上や回路量削減のために、記憶素子の最適な使い分けが行われる。大規模履歴テーブル３２１は、例えばＳＲＡＭであり、多数のエントリを記憶する。小規模履歴テーブル５０２は、例えばラッチ回路であり、少数のエントリ（例えば１個）を記憶する。小規模履歴テーブル５０２のエントリ数は、大規模履歴テーブル３２１のエントリ数よりも少ない。分岐方向予測回路５０１の構成例は、後に図９及び図１０を参照しながら説明する。
【００６４】
分岐先アドレスＡＤの予測完了に先行して、分岐方向ＢＤの予測が完了する。予測された分岐方向ＢＤが分岐する旨を示す場合は、次のアドレスの後続命令をフェッチしても実行されることはなく、パイプライン処理をキャンセル（命令処理の取り消し）して、予測された分岐先命令のフェッチをやり直すため、必ず無駄となる。この場合、分岐方向ＢＤの予測が完了した際に、分岐先アドレスＡＤはまだ予測されていないことから、分岐先命令をフェッチすることはできない。そこで、スレッド調停回路３１１において、別のスレッドをスケジュールすることにより、命令のキャンセルを回避し、命令フェッチスループットの効率化を図る。以下、その詳細を説明する。
【００６５】
図６は、図５の演算処理装置１０１のパイプライン処理例を示す図である。以下、図６が図４と異なる点を説明する。時刻ｔ２において、分岐命令ＡのＴステージ３０２では、命令アドレスＡＣが小規模履歴テーブル（分岐方向予測テーブル）５０２にヒットし、分岐方向予測論理回路５０３は、分岐する旨を示す分岐方向ＢＤを出力する。スレッド選択情報ＳＩは、スレッド調停回路３１１に入力される。スレッド選択情報ＳＩは、分岐方向ＢＤ及びスレッド番号ＳＮを含む。この場合、スレッド番号ＳＮは、命令Ｘが属する第２のスレッドの番号である。
【００６６】
次に、時刻ｔ３では、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、スレッド番号ＳＮが示す第２のスレッドの命令Ｙを選択し、命令ＹのＡステージ３０１が実行される。また、時刻ｔ３では、分岐命令ＡのＭステージ３０３が実行され、分岐予測論理回路３２３は、分岐先アドレスＡＤを第１のセレクタＳＬ１〜ＳＬｎに出力する。第１のセレクタＳＬ１〜ＳＬｎは、スレッド調停回路３１１の制御により、分岐する旨を示す分岐方向ＢＤを基に、分岐先アドレスＡＤを選択する。
【００６７】
次に、時刻ｔ４では、分岐先命令ＣのＡステージ３０１が実行される。具体的には、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、分岐する旨を示す分岐方向ＢＤを基に、分岐命令Ａが属する第１のスレッドのアドレスＡＢ１を選択し、分岐先命令ＣのＡステージ３０１を実行する。本実施形態によれば、時刻ｔ３の分岐命令ＡのＭステージ３０３の直後に、時刻ｔ４の分岐先命令ＣのＡステージ３０１を実行することができる。これにより、図６では、図４に比べ、分岐先命令Ｃの命令フェッチレイテンシが短縮される。
【００６８】
分岐方向ＢＤの予測結果を用いて、第２のスレッドの命令Ｘ及び命令Ｙをスケジューリングすることにより、図４のような後続命令Ｂのキャンセルを回避することができる。これにより、図６では、図４に比べ、第２のスレッドの命令Ｙは、命令フェッチ時刻が早くなる。
【００６９】
後続命令Ｂのキャンセルは回避され、命令フェッチスループットが効率化されたことにあわせ、上記のように命令フェッチレイテンシ及び命令フェッチスループットの両面で、命令フェッチ部２０３の効率が向上する。
【００７０】
図７は、図５の演算処理装置１０１の他のパイプライン処理例を示す図であり、分岐方向ＢＤが分岐しない旨を示す場合を示す。以下、図７が図６と異なる点を説明する。第２のセレクタ３１３は、スレッド調停回路３１１の制御により、基本的に第１のスレッド及び第２のスレッドを交互に選択する。
【００７１】
時刻ｔ２において、分岐命令ＡのＴステージ３０２では、命令アドレスＡＣが小規模履歴テーブル（分岐方向予測テーブル）５０２にヒットせず、分岐方向予測論理回路５０３は、分岐しない旨を示す分岐方向ＢＤを出力する。スレッド選択情報ＳＩは、スレッド調停回路３１１に入力される。スレッド選択情報ＳＩは、分岐方向ＢＤ及びスレッド番号ＳＮを含む。
【００７２】
次に、時刻ｔ３では、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、分岐しない旨を示す分岐方向ＢＤを基に、第１のスレッドの後続命令Ｂを選択し、後続命令ＢのＡステージ３０１が実行される。後続命令Ｂは、時刻ｔ４でＴステージ３０２が実行され、時刻ｔ５でＭステージ３０３が実行され、時刻ｔ６でＢステージ３０４が実行される。
【００７３】
次に、時刻ｔ４では、第２のスレッドの命令ＹのＡステージ３０１が実行される。具体的には、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、分岐しない旨を示す分岐方向ＢＤを基に、第２のスレッドの命令Ｙを選択し、命令ＹのＡステージ３０１を実行する。命令Ｙは、時刻ｔ５でＴステージ３０２が実行され、時刻ｔ６でＭステージ３０３が実行され、時刻ｔ７でＢステージ３０４が実行される。
【００７４】
本実施形態によれば、分岐しない旨の分岐方向ＢＤが予測された場合にも、効率的なパイプライン処理を行うことができる。
【００７５】
以上のように、分岐予測回路２０４は、第２のセレクタ３１３により選択されたアドレスＡＣを基に、選択されたアドレスＡＣの命令が分岐命令である場合にその分岐命令が分岐するか否かを示す分岐方向ＢＤを予測してＴステージ（第１のサイクルステージ）３０２で出力し、そのＴステージ（第１のサイクルステージ）３０２より後のＭステージ（第２のサイクルステージ）３０３で上記の分岐命令の分岐先アドレスＡＤを予測して出力する。
【００７６】
分岐予測回路２０４は、過去の分岐命令の分岐履歴を記憶する大規模履歴テーブル（第１の履歴テーブル）３２１と、過去の分岐命令の分岐履歴を記憶する小規模履歴テーブル（第２の履歴テーブル）５０２とを有する。分岐予測回路２０４は、大規模履歴テーブル３２１を用いて分岐先アドレスＡＤを予測し、小規模履歴テーブル５０２を用いて分岐方向ＢＤを予測する。
【００７７】
スレッド調停回路３１１は、分岐予測回路２０４により出力される分岐方向ＢＤを基に第１のセレクタＳＬ１〜ＳＬｎ及び第２のセレクタ３１３の選択を制御する。第１のセレクタＳＬ１〜ＳＬｎは、分岐予測回路２０４により出力される分岐先アドレスＡＤを入力する。
【００７８】
第１のセレクタＳＬ１〜ＳＬｎは、予測された分岐方向ＢＤが分岐する旨を示す場合には分岐先アドレスＡＤを選択し、予測された分岐方向ＢＤが分岐しない旨を示す場合にはｎ個のスレッドの命令アドレスＡＡ１〜ＡＡｎを選択する。
【００７９】
第２のセレクタ３１３は、予測された分岐方向ＢＤが分岐する旨を示す場合（図６）には分岐命令Ａが属する第１のスレッドとは異なる第２のスレッドの命令Ｙのアドレスを選択し、予測された分岐方向ＢＤが分岐しない旨を示す場合（図７）には分岐命令Ａが属する第１のスレッドと同じ第１のスレッドの後続命令Ｂのアドレスを選択する。
【００８０】
図８は、命令フェッチ部２０３及び一次命令キャッシュ２０５の構成例を示す図である。命令フェッチ部２０３は、Ａステージ３０１、Ｔステージ３０２、Ｍステージ３０３、Ｂステージ３０４及びＲステージ３０５のパイプラインを有する。Ａステージ３０１は、命令アドレス生成の機能を有する。Ｔステージ３０２は、分岐先アドレスの履歴読み出しの機能を有する。Ｍステージ３０３は、分岐予測の完了を行う機能を有する。Ｂステージ３０４は、命令フェッチパイプラインのその他後段の機能（命令の伝送処理）を有する。Ｒステージ３０５は、命令バッファの処理である。一次命令キャッシュ２０５は、命令アドレスをインデックスとしてタグ・データを読み出し、タグ・データと比較し、一致した命令を命令バッファ２０６に出力する。
【００８１】
本実施形態では、Ｔステージ３０２で分岐方向ＢＤの予測が完了し、Ｍステージ３０３で分岐先アドレスＡＤの予測が完了し、効率的なパイライン処理を行うことができる。
【００８２】
図９は、図５の分岐方向予測回路５０１の構成例を示す図である。比較器９０２及び論理積（ＡＮＤ）回路９０３は、図５の分岐方向予測論理回路５０３に対応する。命令アドレスＡＣは、上位ビットアドレスであるタグＡＣ１及び下位ビットアドレスであるインデックスＡＣ２に分割される。パイプラインレジスタ９０１は、クロック信号に同期して、タグＡＣ１をラッチして出力する。小規模履歴テーブル（分岐方向予測テーブル）５０２は、１個以上の少数のエントリを記憶し、低レイテンシのラッチ回路などの素子を用いて構成する。エントリは、インデックスＡＣ２に対応する分岐方向ＢＡ及びタグＡＣ３である。小規模履歴テーブル５０２は、インデックスＡＣ２を入力し、インデックスＡＣ２に対応する分岐方向ＢＡ及びタグＡＣ３を出力する。比較回路９０２は、フリップフロップ９０１が出力するタグＡＣ１及び小規模履歴テーブル５０２が出力するタグＡＣ３を比較し、両者が一致しているとき（ヒットのとき）には「１」を予測有効信号ＢＢとして出力し、両者が不一致のとき（ミスのとき）には「０」を予測有効信号ＢＢとして出力する。論理積回路９０３は、予測有効信号ＢＢ及び分岐方向ＢＡの論理積信号を分岐方向ＢＤとして出力する。予測有効信号ＢＢが「１」のときには、分岐方向ＢＤは分岐方向ＢＡと同じになり、予測有効信号ＢＢが「０」のときには、分岐方向ＢＤは「０」になる。分岐方向ＢＤは、「１」が分岐する旨を示し、「０」が分岐しない旨を示す。
【００８３】
なお、分岐予測回路２０４は、分岐命令に限らず他の命令も予測対象とするとことができる。その場合、分岐予測回路２０４は、命令が分岐命令であるかを含めて予測し、命令が分岐命令であるかどうかは後段の命令デコーダ２０７で確定する。
【００８４】
高遅延の大規模履歴テーブル３２１の記憶素子は、例えば高密度素子のＲＡＭ（ランダムアクセスメモリ：Random Access Memory）である。低遅延の小規模履歴テーブル５０２の記憶素子は、大規模履歴テーブル３２１に対して、低遅延な素子を用いた記憶素子であれば良い。小規模履歴テーブル５０２の記憶素子は、例えばラッチ回路又はフリップフロップであるが、これらに限られない。低遅延な分岐方向予測回路５０１は、ＣＡＭ（Content Addressable Memory）によって構成しても良い。
【００８５】
小規模履歴テーブル５０２は、ダイレクトマップであってもセットアソシアティブであってもフルアソシアティブであっても良い。エントリ数は、１エントリ以上あれば良い。小規模履歴テーブル５０２のインデックスのビット幅は問わない。インデックスは、命令アドレスの関数であれば良い。例えば、命令アドレスの任意のハッシュをインデックスとしても良い。タグＡＣ１は、予測精度と引き換えに、ビット幅を減らしてもよい。
【００８６】
また、分岐予測回路２０４は、低遅延な分岐方向予測回路５０１とは別に、予測精度の高い分岐方向予測回路を持っていても良い。
【００８７】
図１０は、図５の分岐方向予測回路５０１の他の構成例を示す図である。図１０の分岐方向予測回路５０１は、図９の分岐方向予測回路５０１に対して、論理積回路９０３を削除したものである。以下、図１０が図９と異なる点を説明する。小規模履歴テーブル５０２は、分岐方向ＢＡを省略し、分岐すると予想される分岐命令のみに対応するエントリを記憶する。小規模履歴テーブル５０２は、インデックスＡＣ２に対応するタグＡＣ３を出力する。比較回路９０２は、タグＡＣ１及びＡＣ３を比較し、両者が一致するときには「１」の分岐方向ＢＤを出力し、両者が不一致のときには「０」の分岐方向ＢＤを出力する。
【００８８】
図１１は、図５のスレッド調停回路３１１の構成例を示す図である。ここでは、第１のスレッド及び第２のスレッドの２スレッドを調停する場合を例に示す。スレッド番号ＳＮは、「０」が第１のスレッドを示し、「１」が第２のスレッドを示す。排他的論理和回路１１０４は、インバータ１１０２の出力信号及びスレッド番号ＳＮの排他的論理和信号を出力する。論理積回路１１０５は、排他的論理和回路１１０４の出力信号の論理反転信号と分岐方向ＢＤとの論理積信号を出力する。ラッチ回路１１０１は、クロック信号に同期して、排他的論理和回路１１０３の出力信号をラッチして出力する。インバータ１１０２は、フリップフロップ１１０１の出力信号の論理反転信号を出力する。排他的論理和回路１１０３は、インバータ１１０２の出力信号と論理積回路１１０５の出力信号との排他的論理和信号をスレッド番号ＳＮとして第２のセレクタ３１３に出力する。第２のセレクタは、スレッド番号ＳＮが「０」のときには第１のスレッドのアドレスＡＢ１を選択し、スレッド番号ＳＮが「１」のときには第２のスレッドのアドレスＡＢ２を選択し、アドレスＡＣを出力する。
【００８９】
まず、図７のように分岐方向ＢＤが分岐しない旨を示す場合を説明する。その場合、分岐方向ＢＤは「０」であり、論理積回路１１０５は「０」を出力する。すると、排他的論理和回路１１０３は、インバータ１１０２の出力信号をそのまま出力する。例えば、フリップフロップ１１０１の出力信号が「１」の場合、インバータ１１０２は「０」の信号を出力し、排他的論理和回路１１０３は「０」のスレッド番号ＳＮを第２のセレクタ３１３に出力する。第２のセレクタ３１３は、スレッド番号ＳＮが「０」であるので、第１のスレッドのアドレスＡＢ１を選択し、命令アドレスＡＣとして出力する。
【００９０】
次に、フリップフロップ１１０１は、排他的論理和回路１１０３から「０」のスレッド番号ＳＮを入力し、「０」の信号を出力する。すると、インバータ１１０２は「１」の信号を出力し、排他的論理和回路１１０３は「１」のスレッド番号ＳＮを第２のセレクタ３１３に出力する。第２のセレクタ３１３は、スレッド番号ＳＮが「１」であるので、第２のスレッドのアドレスＡＢ２を選択し、命令アドレスＡＣとして出力する。
【００９１】
以後、同様に、第２のセレクタ３１３は、第１のスレッドのアドレスＡＢ１と第２のスレッドのアドレスＡＢ２とを交互に選択して出力する。
【００９２】
次に、図６のように分岐方向ＢＤが分岐する旨を示す場合を説明する。その場合、分岐方向ＢＤは「１」であり、スレッド番号ＳＮは分岐命令Ａが属する第１のスレッドを示す「０」である。例えば、図６の時刻ｔ２では、命令ＸのＡステージ３０１が実行される。その時、命令Ｘは、第２のスレッドであるので、その後、インバータ１１０２は「０」の信号を出力する。すると、排他的論理和回路１１０４は、「０」のスレッド番号ＳＮとインバータ１１０２の「０」の出力信号との排他的論理和信号として「０」の信号を出力し、論理積回路１１０５は「１」の信号を出力する。すると、排他的論理和回路１１０３は、インバータ１１０２の出力信号の論理反転信号をスレッド番号ＳＮとして出力する。この場合、インバータ１１０２の出力信号が「０」であるので、スレッド番号ＳＮは「１」になる。第２のセレクタ３１３は、スレッド番号ＳＮが「１」であるので、第２のスレッドのアドレスＡＢ２を選択し、命令アドレスＡＣとして出力する。その結果、図６の時刻ｔ３では、第２のスレッドの命令ＹのＡステージ３０１が実行される。
【００９３】
図１２は、図５のスレッド調停回路３１１の他の構成例を示す図であり、２個以上のスレッドの調停を行うことができる。スレッド調停回路３１１は、ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎ、スケジューラ１２０１及びセレクタ１２０２を有する。スレッド選択情報ＳＩは、分岐方向ＢＤ及びスレッド番号ＳＮを含む。ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎは、スレッド選択情報ＳＩを基に、それぞれの優先順位に従い、ｎ個のスレッドの中でフェッチ可能なスレッドの番号を１つ出力する。ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎは、それぞれ優先順位が異なる。例えば、第１のプライオリティエンコーダＰＥ１は、第１のスレッドが最も優先順位が高く、第ｎのプライオリティエンコーダＰＥｎは、第ｎのスレッドが最も優先順位が高い。セレクタ１２０２は、スケジューラ１２０１の制御により、ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎの出力信号のうちの１個を選択して出力する。スケジューラ１２０１は、ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎの出力信号が均等に選ばれるように制御することにより、特定のスレッドの選択回数が多くなりすぎることを防止できる。なお、スケジューラ１２０１は、任意のスケジューリングポリシーによって、いずれかのスレッドを優先して選択するように制御してもよい。
【００９４】
また、命令フェッチ部２０３と命令デコーダ２０７との間には、命令バッファ２０６があってもなくても良い。命令フェッチ部２０３は、パイプライン化され、複数スレッドに対しサイクル粒度の時分割で、命令コードと分岐予測回路２０４により命令フェッチ制御を行う装置であれば良い。命令フェッチ部２０３は、同一スレッドの複数命令を同一サイクルに同時にフェッチするものであっても良い。
【００９５】
また、パイプライン段数は問わず、分岐予測レイテンシも問わない。パイプラインの構成方式は、同期、非同期を問わず、ウェーブパイプラインを構成してもよい。
【００９６】
また、１コアあたり複数の命令フェッチ部２０３を持つ演算処理装置であっても良い。すなわち、命令フェッチ部２０３より後段の回路を、他の命令フェッチ部２０３と共用しても良い。言い換えると、複数の命令フェッチ部２０３と合わせて全体で、同一サイクルで複数スレッドに対する命令フェッチ制御を構成してもよい。
【００９７】
また、ハードウエアスレッド数は２スレッド又はそれ以上であってもよい。基本とするスレッドスケジューリング方式は問わず、ラウンドロビン方式以外のスケジューリング方式であっても、命令フェッチに先行して分岐方向を予測することで、不要な命令フェッチを避けることができる。
【００９８】
また、演算処理装置１０１が採用する命令セットアーキテクチャは問わない。ＲＩＳＣ（縮小命令セットコンピュータ：Reduced Instruction Set Computer）であってもＣＩＳＣ（複合命令 セットコンピュータ：Complex Instruction Set Computer）であってもＶＬＩＷ（超長命令語：Very Long Instruction Word）であっても良い。
【００９９】
また、命令デコーダ２０７の形式は、問わず、順序制御又はスーパースカラであっても、ＶＬＩＷであっても良く、静的・動的なコード変換を行ってもよい。
【０１００】
また、命令実行部の形態は問わない。命令実行部は、単一サイクル実行であっても、パイプライン制御であっても、順序制御であっても良く、スーパースカラ実行であっても良く、アウトオブオーダ実行であってもインオーダ実行であってもよい。演算器制御は、ＳＩＭＤ（Single Instruction Multiple Data）型であってもよく、プロセッサコア外の演算資源を制御する形態であってもよい。また、命令完了形式は、問わず、投機的実行や正確な割り込みを実現していてもしていなくてもよい。
【０１０１】
以上のように、本実施形態によれば、分岐先アドレスＡＤの予測に先行して分岐方向ＢＤを予測することにより、効率的なスレッド選択が可能になり、処理速度を向上させることができる。
【０１０２】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１０３】
２０４ 分岐予測回路
２０５ 一次命令キャッシュ
３０１ Ａステージ
３０２ Ｔステージ
３０３ Ｍステージ
３１１ スレッド調停回路
３１２ パイプラインレジスタ
３１３ 第２のセレクタ
３２１ 大規模履歴テーブル
３２２ パイプラインレジスタ
３２３ 分岐予測論理回路
５０１ 分岐方向予測回路
５０２ 小規模履歴テーブル
５０３ 分岐方向予測論理回路
５０４ パイプラインレジスタ
ＳＬ１〜ＳＬｎ 第１のセレクタ
【技術分野】
【０００１】
本発明は、演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
まず、演算処理装置であるパイプラインプロセッサと分岐予測について説明する。パイプライン化されたプロセッサ（パイプラインプロセッサ）の単純な実装では、プログラム実行中に分岐命令を実行した場合、命令フェッチから分岐命令実行までのパイプラインステージの段数分のクロックサイクルだけ、パイプラインが停止（ストール）し、パイプライン処理の効率が低下する。
【０００３】
これを防ぐため、パイプラインプロセッサでは、分岐命令をフェッチした場合、分岐先の命令アドレスもしくは、分岐方向として分岐する場合にはtakenと予想し又は分岐しない場合はnot takenと予想し、もしくは、これらtakenとnot takenの両方を予測し、分岐命令の実行完了を待たずに命令フェッチを続行する分岐予測処理が行われることが一般的である。分岐予測により、プロセッサのパイプラインに命令を流し続けることでパイプラインの処理効率を向上させることができる。
【０００４】
分岐予測には、分岐先予測又は分岐方向予測又はそれら両方を含む。分岐先予測とは、ある分岐命令の次に実行される命令（分岐先命令）の命令アドレスを予測することである。分岐方向予測とは、ある分岐命令が分岐する（taken）か分岐しない（not-taken）かを予測することである。分岐予測方式の一例としては、特許文献１が知られている。
【０００５】
分岐予測の方式には、分岐予測レイテンシが小さいが分岐予測精度の劣る静的分岐予測と、分岐予測レイテンシが大きいが分岐予測精度の高い動的分岐予測とがある。静的分岐予測とは、例えば、後続アドレスを単純に読み込む（not-takenと仮定）、あるいは、命令コード上の予測ビットを利用するといったものである。動的分岐予測とは、実行したプログラムの過去の分岐履歴を参照し、プログラムの分岐の挙動の規則性を用いて実行の完了していない分岐命令による分岐方向又は分岐先命令アドレス又はそれら両方を予測するものである。
【０００６】
動的分岐予測は大規模履歴を利用するなど、動的分岐予測を使用しない場合よりも複雑な回路を必要とし、複数クロックサイクルを分岐予測完了まで要することが普通である。パイプライン段数や同時命令実行数の多いプロセッサコアでは、分岐予測の失敗による性能、電力面での効率低下は大きく、予測精度の高い動的分岐予測回路を用いることが一般的である。
【０００７】
次に、マルチスレッディングについて説明する。１９６０年ごろより、レイテンシの長い演算器を効率的に利用するため、パイプライン化し、複数スレッドで時分割多重化して用いるシステムが登場している。
【０００８】
現代のコンピュータシステムでは、プロセッサ内での演算レイテンシと比較して、メモリ読み書きにかかる時間であるメモリレイテンシが大きくなっており、メモリレイテンシを隠蔽してプロセッサのスループットを向上させる手段として、ハードウエアによるマルチスレッド処理方式であるハードウエアマルチスレッディングを採用することが、スループット指向のプロセッサで一般化している。
【０００９】
スレッドを実行するハードウエア資源であるハードウエアスレッド（ストランドとも呼ばれる）とは、プロセッサコア内に１セット以上保持される、アーキテクチャ状態及びそれより派生するプロセッサ状態のことを指す。したがって、殆どの場合、命令フェッチ部の処理で扱われる命令フェッチアドレスは、スレッド毎に異なる値を持つ。
【００１０】
ハードウエアマルチスレッディングとは、単一プロセッサコア内部で、複数のハードウエアスレッドをサイクル単位の時分割で切り替え、又は、同一サイクル内で同時に処理する方式である。
【００１１】
マイクロアーキテクチャに関する用語のハードウエアスレッドやマルチスレッディングと、オペレーティングシステムなどソフトウエア関連分野の用語のスレッドやマルチスレッディングとでは定義が異なることが普通である。以降、前述の意味で用いる。
【００１２】
複数スレッドの命令を並列実行することで、複数スレッド間での演算器利用の効率向上、あるいは、複数スレッド間でのメモリアクセスと演算器利用との平行（オーバラップ）化が実現され、プロセッサのスループットが向上する。
【００１３】
複数スレッドを平行して処理するために、ハードウエアで複数スレッドを処理するプロセッサ（マルチスレッドプロセッサ）では、命令フェッチの段階ではサイクル単位で、対象とするスレッドを切り替えて命令をフェッチすることが一般的である。フェッチするスレッドを切り替える時間的単位は最小で１クロックサイクルであり、それより時間的粒度が大きい方式もある。前者は一般にＦＧＭＴ（Fine-grained multithreading）などと呼ばれ、後者はＶＭＴ（Vertical multithreading）又はＣＧＭＴ（Coarse-grained multithreading）などと呼ばれる。
【００１４】
命令フェッチ部のスレッド切り替え（スレッドスケジューリング）の方式としては、例えば、ラウンドロビンで行う方式がある。これは、スケジュールするスレッドをサイクル毎に予め決めておいた順番で切り替えていく方法である。
【００１５】
また、インタリーブされた複数の命令スレッドを優先規則に従ってサイクル単位で処理するデータ・プロセッサであって、命令スレッドに関連した事象又は条件に基づいて、特定の命令スレッドに割り当てられた優先度を調整するプロセッサが知られている（例えば、特許文献２参照）。
【００１６】
また、インタリーブされた複数の命令スレッドを優先規則に従ってサイクル単位で処理するデータ・プロセッサであって、命令スレッドに関連した事象又は条件に基づいて処理する、特定の命令スレッドを選択するプロセッサが知られている（例えば、特許文献３参照）。
【００１７】
また、複数の命令スレッドを処理する能力を有するプロセッサであって、処理のために命令スレッドをインタリーブする方法にランダム化を導入し、同時に命令スレッド間のインタリービングの全体的な比率又は程度をある所望の比率又は程度に維持するプロセッサが知られている（例えば、特許文献４参照）。
【００１８】
また、条件分岐命令の次に、どの命令を実行するかを予測し、あらかじめその命令列を読み込んでおくことが可能な分岐予測機構を備えた計算機装置において、分岐予測機構に加えて、条件分岐方向のヒントを得る手段と、特定の命令の実行結果から条件分岐方向のヒントを取得する手段と、上記ヒントを分岐予測装置に伝える手段と、ヒントに従って分岐方向を決定する手段を設けた分岐予測装置が知られている（例えば、特許文献５参照）。
【００１９】
また、マルチスレッディングプロセッサにおけるスケジューリング方法であって、実行可能な複数のスレッドを割り当て、実行するスレッド数をマルチスレッディングプロセッサの動作状態に応じて動的に決定し、割り当てられた複数スレッドから決定された数のスレッドを選択し、同一期間内に選択されたスレッドの命令をフェッチし実行するスケジューリング方法が知られている（例えば、特許文献６参照）。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開平６−８９１７３号公報
【特許文献２】特許第４１７９５５５号公報
【特許文献３】特許第４０８６８０８号公報
【特許文献４】特許第４０８６８０９号公報
【特許文献５】特開２００１−５６６５号公報
【特許文献６】国際公開第０４／０４４７４５号
【発明の概要】
【発明が解決しようとする課題】
【００２１】
まず、レイテンシの課題を説明する。命令フェッチを時分割でスレッドごとに行うパイプラインプロセッサでは、あるスレッドの命令フェッチ開始から分岐予測の結果が出るまでのレイテンシと、時分割で起こるスレッド切り替えのタイミングが合わない場合がある。スレッド切り替えのタイミングが合わない場合とは、あるスレッドの分岐予測結果が出ていても、分岐予測結果を受け取って命令フェッチを行うパイプラインステージが別のスレッドを処理している場合である。パイプラインステージが別のスレッドを処理している場合、分岐予測結果が即座に使われず、分岐予測レイテンシが余計に延びる結果となる。分岐予測レイテンシが延びることが原因で、当該スレッドの実行サイクル数が増大しうる。例えば、純粋なラウンドロビン方式のスレッドスケジューリングを用いた場合で、分岐予測レイテンシのサイクル数が、ハードウエアスレッド数の倍数でない場合、分岐予測結果が次の命令フェッチに利用されるまでのサイクル数が、ハードウエアマルチスレッディング動作を行ったことにより、単一スレッド動作を行った場合と比較して、増大する。
【００２２】
次に、スループットの課題を説明する。分岐方向を先見しない従来方式でスレッドスケジューリングを行うプロセッサコアでは、命令フェッチ開始から分岐予測結果が出るまでのサイクル数（分岐予測レイテンシ）が、ハードウエアで扱うスレッド数より大きい場合は、分岐予測レイテンシの全てをハードウエアマルチスレッディングによって隠蔽することはできない。そのため、動的分岐予測器による分岐予測結果をすぐに命令フェッチに用いることができず、パイプラインがストール、あるいは、動的分岐予測器によらない低レイテンシだが不正確な静的分岐予測を用いざるを得なくなる。不正確な分岐予測を用いることで、不必要な命令フェッチが起こる可能性が高まり、命令フェッチスループットが低下する。命令フェッチスループットの低下は、プロセッサ全体の命令実行効率をも低下させうる。動的分岐予測完了が間に合わなかった場合にアドレスが連続する後続命令をフェッチする（分岐しないと仮定する）静的分岐予測制御を用いるマルチスレッドプロセッサでは、分岐しないと予測していた場合に、分岐命令の実際の実行結果が分岐するであった場合は、命令フェッチパイプラインのスループットを浪費する。予測された分岐方向が分岐する場合、次のアドレスの後続命令をフェッチしても実行されることはなく、その後続命令のパイプライン処理をキャンセルして予測された分岐先命令のフェッチをやり直すため、必ず無駄となる。これによりマルチスレッドプロセッサではスループット性能の低下を起こし、また、電力を空費する結果となる。
【００２３】
また、プロセッサ内部には、キャッシュ、ＴＬＢ（Translation Lookaside Buffer）、分岐履歴表などの、命令フェッチ履歴により内容が蓄積される記憶資源を持つことが一般的である。これらの記憶資源が不正確な命令フェッチにより内容が汚染され、プロセッサの性能低下につながる可能性がある。
【００２４】
１つの側面では、本発明は、効率的なスレッド選択を可能にすることを目的とする。
【課題を解決するための手段】
【００２５】
演算処理装置は、複数のスレッドの命令を複数のサイクルステージ毎に実行する演算処理装置において、入力した複数のスレッドの命令の命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して、前記複数のスレッドのアドレスを出力する第１のセレクタと、前記第１のセレクタが出力した複数のスレッドのアドレスのうち、いずれか１個のスレッドのアドレスを選択する第２のセレクタと、前記複数のサイクルステージのうち第１のサイクルステージで、前記第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を前記選択されたアドレスに基づき予測して出力するとともに、前記第１のサイクルステージより後の第２のサイクルステージで、前記予測対象の分岐命令の分岐先アドレスを前記選択されたアドレスに基づき予測して出力する分岐予測回路と、前記分岐予測回路が出力した前記分岐方向に基づき、前記第１セレクタ及び第２のセレクタによるスレッドのアドレスの選択を制御するスレッド調停回路と、を有する。
【発明の効果】
【００２６】
演算処理装置において、効率的なスレッド選択が可能となる。
【図面の簡単な説明】
【００２７】
【図１】実施形態による情報処理装置の構成例を示す図である。
【図２】演算処理装置の構成例を示す図である。
【図３】参考技術による命令フェッチ部及び分岐予測回路の構成例を示す図である。
【図４】図３の演算処理装置のパイプライン処理例を示す図である。
【図５】本実施形態による命令フェッチ部及び分岐予測回路の構成例を示す図である。
【図６】図５の演算処理装置のパイプライン処理例を示す図である。
【図７】図５の演算処理装置の他のパイプライン処理例を示す図である。
【図８】命令フェッチ部及び一次命令キャッシュの構成例を示す図である。
【図９】図５の分岐方向予測回路の構成例を示す図である。
【図１０】図５の分岐方向予測回路の他の構成例を示す図である。
【図１１】図５のスレッド調停回路の構成例を示す図である。
【図１２】図５のスレッド調停回路の他の構成例を示す図である。
【発明を実施するための形態】
【００２８】
図１は、実施形態による情報処理装置の構成例を示す図である。情報処理装置は、例えば、マルチスレッド演算処理装置（プロセッサ）１０１をサーバなどに組み込んだシステムであり、複数の演算処理装置１０１、複数のメモリ１０２、及びインターコネクト制御部１０３を有する。演算処理装置１０１は、例えば中央演算処理装置（ＣＰＵ）であり、インターコネクト制御部１０３に接続される。複数の演算処理装置１０１には、それぞれ、複数のメモリ１０２が接続される。インターコネクト制御部１０３は、外部装置１０４に対して入出力制御を行う。
【００２９】
図２は、演算処理装置１０１の構成例を示す図である。演算処理装置１０１は、アウトオブオーダ実行及びパイプライン機能を有する。命令フェッチステージ２２１では、命令フェッチ部２０３、命令バッファ２０６、分岐予測回路２０４、一次命令キャッシュ２０５及び二次キャッシュ２０２などが動作する。
【００３０】
命令フェッチ部２０３は、分岐予測回路２０４から入力したフェッチする命令の予測分岐先アドレス、分岐制御部２１１から入力した分岐演算により確定した分岐先アドレス、及び命令フェッチ部２０３内で生成した分岐しない場合のフェッチする命令の連続した次のアドレスのうちから１つのアドレスを選択し、次の命令フェッチアドレスを確定する。命令フェッチ部２０３は、確定した命令フェッチアドレスを一次命令キャッシュ２０５に出力し、該当するアドレスから命令コードをフェッチする。一次命令キャッシュ２０５は、二次キャッシュ２０２の一部の情報を格納し、二次キャッシュ２０２はメモリ１０２（図１）の一部の情報を格納している。一次命令キャッシュ２０５に該当するアドレスのデータが存在しない場合は二次キャッシュ２０２から、二次キャッシュ２０２に該当するデータが存在しない場合はメモリ１０２からデータをフェッチする。本実施形態では、メモリ１０２は演算処理装置１０１の外部に配置しているため、外部にあるメモリ１０２との入出力制御はメモリコントローラ２０１を介して行われる。一次命令キャッシュ２０５、二次キャッシュ２０２、又はメモリ１０２の該当するアドレスからフェッチされた命令コードは、命令バッファ２０６に格納される。
【００３１】
分岐予測回路２０４は、上記の命令フェッチと並行して分岐予測を実行する。分岐予測回路２０４は、命令フェッチ部２０３から出力された命令フェッチアドレスを入力し、それを基に分岐予測を行い、分岐する又は分岐しないを示す分岐方向と分岐先アドレスとを命令フェッチ部２０３に出力する。命令フェッチ部２０３は、予測された分岐方向が分岐する旨を示す場合に、次の命令フェッチアドレスとして、予測された分岐先アドレスを選択する。分岐しない旨の分岐方向が予測された場合は、連続した次のアドレスが命令フェッチアドレスとして選択される。
【００３２】
命令発行ステージ２２２では、命令デコーダ２０７、命令発行制御部２０８が動作する。命令デコーダ２０７は、命令バッファ２０６から命令コードを受け取り、命令の種別や必要な実行資源などを解析し、解析結果を命令発行制御部２０８に出力する。命令発行制御部２０８は、リザベーションステーションの構造を持ち、命令で参照するレジスタなどの依存性を見て、依存性のあるレジスタの更新状況や同じ演算器などの実行資源を用いる命令の実行状況などから、実行資源が命令を実行可能かどうかを判断し、実行可能なら各実行資源に対してレジスタ番号やオペランドアドレスなど命令実行に必要な情報を、一次オペランドキャッシュ２０９及び演算器２１０に出力する。また、命令発行制御部２０８は、実行可能となるまで命令を格納しておくバッファの役割も担う。
【００３３】
命令実行ステージ２２３では、演算器２１０、一次オペランドキャッシュ２０９、分岐制御部２１１などの実行資源が動作する。演算器２１０は、必要に応じてレジスタ２１２や一次オペランドキャッシュ２０９からデータを入力し、四則演算や論理演算、三角関数演算、アドレス計算などの命令に対応した演算を実行し、演算結果をレジスタ２１２やキャッシュ２０９に出力する。一次オペランドキャッシュ２０９は、一次命令キャッシュ２０５と同様に、二次キャッシュ２０２の一部の情報を格納しているものであり、ロード命令によりメモリ１０２（図１）から演算器２１０又はレジスタ２１２へデータをロードし、ストア命令により演算器２１０又はレジスタ２１２からメモリ１０２へデータをストアする。各実行資源は、命令実行の完了通知を命令完了制御部２１３へ出力する。
【００３４】
分岐制御部２１１は、命令デコーダ２０７から分岐命令の種別を入力し、演算器２１０から分岐先アドレスや分岐条件となる演算の結果を入力し、演算結果が分岐条件を満たしていれば分岐する、満たしていなければ分岐しないことの判断を行い、分岐方向を確定する。また、分岐制御部２１１は、演算結果と分岐予測時の分岐先アドレスと分岐方向が一致するかどうかの判断や、分岐命令の順序関係の制御も行う。分岐制御部２１１は、演算結果と予測とが一致した場合は命令完了制御部２１３へ分岐命令の完了通知を出力する。また、分岐制御部２１１は、演算結果と予測とが一致しなかった場合は分岐予測失敗を意味するので、命令完了制御部２１３へ分岐命令の完了通知と共に後続命令のキャンセル及び再命令フェッチ要求を出力する。
【００３５】
命令完了ステージ２２４では、命令完了制御部２１３、レジスタ２１２、分岐履歴更新部２１４が動作する。命令完了制御部２１３は、各命令実行資源から入力した完了通知を基に、コミットスタックエントリに格納された命令コード順に命令完了処理を行い、レジスタ２１２の更新指示を出力する。レジスタ２１２は、命令完了制御部２１３からレジスタ更新指示を入力すると、演算器２１０や一次オペランドキャッシュ２０９から入力する演算結果のデータを基にレジスタ２１２の更新を実行する。分岐履歴更新部２１４は、分岐制御部２１１から入力する分岐演算の結果を基に、分岐予測回路２０４の履歴更新データを生成し、分岐予測回路２０４に出力し、分岐予測回路２０４の履歴データの更新を実行する。
【００３６】
図３は、参考技術による命令フェッチ部２０３及び分岐予測回路２０４の構成例を示す図である。命令フェッチ部２０３は、第１のセレクタＳＬ１〜ＳＬｎ、パイプラインレジスタＲＧ１〜ＲＧｎ、スレッド調停回路３１１、パイプラインレジスタ３１２及び第２のセレクタ３１３を有する。分岐予測回路２０４は、大規模履歴テーブル３２１、パイプラインレジスタ３２２及び分岐予測論理回路３２３を有する。命令フェッチステージ２２１では、パイプライン処理により分岐予測を行う。分岐予測レイテンシが、Ａステージ３０１、Ｔステージ３０２及びＭステージ３０３の３サイクルである命令フェッチパイプラインの一例を示す。Ａステージ３０１では、命令アドレス生成が行われる。Ｔステージ３０２では、分岐先アドレスの履歴読み出しが行われる。Ｍステージ３０３では、分岐予測の完了処理が行われる。命令フェッチステージ２２１のパイプライン段数やパイプラインレジスタの位置、パイプラインステージの機能、ハードウエアスレッド数などは任意に構成されうる。
【００３７】
ｎ個の第１のセレクタＳＬ１〜ＳＬｎは、スレッド調停回路３１１の制御により、それぞれ、ｎ個のスレッドの命令アドレスＡＡ１〜ＡＡｎ又は分岐先アドレスＡＤを選択し、ｎ個のスレッドのアドレスＡＢ１〜ＡＢｎを出力する。ここで、ｎは２以上の整数である。例えば、セレクタＳＬ１は、第１のスレッドの命令アドレスＡＡ１及び分岐先アドレスＡＤを入力し、第１のスレッドのアドレスＡＢ１を出力する。セレクタＳＬ２は、第２のスレッドの命令アドレスＡＡ２及び分岐先アドレスＡＤを入力し、第２のスレッドのアドレスＡＢ２を出力する。ｎ個のパイプラインレジスタＲＧ１〜ＲＧｎは、それぞれ、フリップフロップで構成され、クロック信号に同期して、ｎ個のスレッドのアドレスＡＢ１〜ＡＢｎをラッチして出力する。スレッド調停回路３１１は、ｎ個のスレッドのうちの次にフェッチする命令のスレッド番号ＳＮを出力する。パイプラインレジスタ３１２は、クロック信号に同期して、スレッド番号ＳＮをラッチして出力する。
【００３８】
Ａステージ３０１では、第２のセレクタ３１３は、ｎ個のスレッドのアドレスＡＢ１〜ＡＢｎの中から、スレッド番号ＳＮが示す１個のスレッドの命令アドレスＡＣを選択して出力する。命令アドレスＡＣは、フェッチするアドレスであり、一次命令キャッシュ２０５へ出力されるとともに、次の分岐予測に用いるために、パイラインレジスタを介して分岐予測回路２０４に出力される。
【００３９】
Ｔステージ３０２では、分岐予測回路２０４が動的分岐予測を行う。具体的には、分岐予測回路２０４内の大規模履歴テーブル３２１は、分岐命令の命令アドレスＡＣに対する分岐方向及び分岐先アドレスの履歴情報を記憶し、命令アドレスＡＣに応じた分岐方向及び分岐先アドレスをパイプラインレジスタ３２２に出力する。大規模履歴テーブル３２１は、高い分岐予測精度と引き換えに予測結果が出るまで、長いレイテンシを必要とする。パイプラインレジスタ３２２は、クロック信号に同期して、分岐方向及び分岐先アドレスをラッチして出力する。
【００４０】
Ｍステージ３０３では、分岐予測回路２０４内の分岐予測論理回路３２３は、パイプラインレジスタ３２２から分岐命令の分岐方向及び分岐先アドレスを入力し、スレッド選択情報ＳＩをスレッド調停回路３１１に出力し、分岐命令の分岐先アドレスＡＤを第１のセレクタＳＬ１〜ＳＬｎに出力する。スレッド選択情報ＳＩは、分岐方向及びその分岐命令のスレッド番号ＳＮを含む。
【００４１】
第１のセレクタＳＬ１〜ＳＬｎは、スレッド調停回路３１１の制御により、スレッド選択情報ＳＩ内の分岐方向が分岐する旨を示す場合は、分岐先アドレスＡＤを選択し、スレッド選択情報ＳＩ内の分岐方向が分岐しない旨を示す場合は、後続の命令アドレスＡＡ１〜ＡＡｎを選択する。
【００４２】
また、スレッド調停回路３１１は、スレッド選択情報ＳＩ内のスレッド番号ＳＮをパイプラインレジスタ３１２に出力する。パイプラインレジスタ３１２は、クロック信号に同期して、スレッド番号ＳＮをラッチして出力する。第２のセレクタ３１３は、パイプラインレジスタ３１２が出力するスレッド番号ＳＮに応じて、アドレスＡＢ１〜ＡＢｎの中から１つを選択し、命令アドレスＡＣとして出力する。例えば、第２のセレクタ３１３は、スレッド番号ＳＮが１番のときには、第１のスレッドのアドレスＡＢ１を選択し、スレッド番号ＳＮが２番のときには、第２のスレッドのアドレスＡＢ２を選択する。
【００４３】
図４は、図３の演算処理装置１０１のパイプライン処理例を示す図である。ここでは、演算処理装置１０１が第１のスレッド及び第２のスレッドの２スレッドを切り替えてフェッチし、フェッチ開始から分岐先アドレスＡＤの確定までのレイテンシが３サイクルである例を示す。右方向の矢印は時間順を示し、下方向の矢印は命令の処理順を示す。
【００４４】
第１のスレッドは、分岐命令Ａ、後続命令Ｂ及び分岐先命令Ｃを有する。第２のスレッドは、命令Ｘ及び命令Ｙを有する。第１のスレッドと第２のスレッドとの間には制御依存関係はなく、性能に対する影響を除き、実行結果に影響を与えることなく、自由にスレッド選択できる。この例では、第１のスレッドと第２のスレッドを交互に命令フェッチしている。具体的には、命令フェッチは、分岐命令Ａ（第１のスレッド）、命令Ｘ（第２のスレッド）、後続命令Ｂ（第１のスレッド）、命令Ｙ（第２のスレッド）、分岐先命令Ｃ（第１のスレッド）の順で行われる。
【００４５】
後続命令Ｂ（第１のスレッド）は、分岐命令Ａ（第１のスレッド）の命令アドレスに連続した次のアドレスにある命令であり、分岐命令Ａ（第１のスレッド）の実行結果により分岐しない場合に実行される命令である。分岐先命令Ｃ（第１のスレッド）は、分岐命令Ａ（第１のスレッド）の実行結果により分岐する場合に実行される分岐先アドレスの命令である。
【００４６】
まず、時刻ｔ１において、着目する分岐命令ＡのＡステージ３０１が実行される。
【００４７】
次に、時刻ｔ２において、分岐命令ＡのＴステージ３０２が実行され、命令ＸのＡステージ３０１が実行される。
【００４８】
次に、時刻ｔ３では、分岐命令ＡのＭステージ３０３が実行され、命令ＸのＴステージ３０２が実行され、後続命令ＢのＡステージ３０１が実行される。分岐命令ＡのＭステージ３０３でスレッド選択情報ＳＩ及び分岐先アドレスＡＤが確定し、時刻ｔ５で分岐先命令ＣをＡステージ３０１でフェッチ開始することが可能になる。例えば、スレッド選択情報ＳＩが分岐する旨を示す場合を例に説明する。
【００４９】
時刻ｔ３では、分岐先アドレスＡＤが確定しておらず、分岐先命令Ｃを命令フェッチすることは不可能である。そのため、時刻ｔ３では、分岐しないと仮定する静的分岐予測により、後続命令Ｂをフェッチしている。
【００５０】
時刻ｔ４で、後続命令ＢがＡステージ３０１の終了の際に、分岐命令Ａの分岐先予測が完了し、分岐先アドレスＡＤが確定し、後続命令Ｂではなく、分岐先命令Ｃが次の命令であると予測される。このため、時刻ｔ４では、後続命令Ｂはキャンセルされる。
【００５１】
なお、時刻ｔ３で、第２のスレッドの命令ＹのＡステージ３０１を実行する場合、後続命令Ｂのキャンセルは回避されるが、後続命令ＢのＡステージ３０１の時点で分岐予測結果が出ておらず、分岐予測結果を用いて第２のスレッドをスケジュールし、意図的にキャンセルを回避することは不可能である。
【００５２】
時刻ｔ４では、スレッド選択情報ＳＩが分岐する旨を示すので、後続命令Ｂがキャンセルされ、分岐命令ＡのＢステージ３０４（図８）が実行され、命令ＸのＭステージ３０３が実行され、命令ＹのＡステージ３０１が実行される。ここで、Ｂステージ３０４は、命令を後段に伝送するステージである。
【００５３】
次に、時刻ｔ５では、命令ＸのＢステージ３０４が実行され、命令ＹのＴステージ３０２が実行され、分岐先命令ＣのＡステージ３０１が実行される。
【００５４】
次に、時刻ｔ６では、命令ＹのＭステージ３０３が実行され、分岐先命令ＣのＴステージ３０２が実行される。
【００５５】
次に、時刻ｔ７では、命令ＹのＢステージ３０４が実行され、分岐先命令ＣのＭステージ３０３が実行される。
【００５６】
次に、時刻ｔ８では、分岐先命令ＣのＢステージ３０４が実行される。
【００５７】
なお、時刻ｔ４では、分岐先アドレスＡＤの予測結果が出ているため、命令Ｙではなく分岐先命令ＣのＡステージ３０１を実行することも可能である。その場合は、第２のスレッドの命令ＹのＡステージ３０１が遅れ、第１のスレッドの命令フェッチ状態に悪影響を与えることになる。
【００５８】
上記の例では、第２のスレッドの命令Ｙではなく、第１のスレッドの分岐先命令Ｃを遅らせるスケジューリング結果となっている。いずれの場合でも、後続命令Ｂのフェッチにより上から３つ目の命令スロットを消費したことにより、第１のスレッド又は第２のスレッドのいずれかの命令フェッチが遅れることになる。
【００５９】
図５は、本実施形態による命令フェッチ部２０３及び分岐予測回路２０４の構成例を示す図である。図５の演算処理装置１０１は、図３の演算処理装置１０１に対して、分岐方向予測回路５０１を追加したものである。以下、図５の演算処理装置１０１が図３の演算処理装置１０１と異なる点を説明する。
【００６０】
分岐方向予測回路５０１は、分岐予測回路２０４内に設けられ、小規模履歴テーブル５０２、分岐方向予測論理回路５０３及びパイプラインレジスタ５０４を有する。Ｔステージ３０２では、小規模履歴テーブル５０２は、代表的な一部の分岐命令の命令アドレスＡＣに対する分岐方向の履歴情報を記憶し、命令アドレスＡＣに応じた分岐方向を分岐方向予測論理回路５０３に出力する。分岐方向予測論理回路５０３は、小規模履歴テーブル５０２が出力する分岐方向を基に分岐方向ＢＤを出力する。パイプラインレジスタ５０４は、クロック信号に同期して、パイプラインレジスタ３１２が出力するスレッド番号ＳＮをラッチして出力する。スレッド選択情報ＳＩは、分岐方向予測論理回路５０３が出力する分岐方向ＢＤ及びフリップフロップ５０４が出力するスレッド番号ＳＮを含み、スレッド調停回路３１１に入力される。次に、Ｍステージ３０３では、分岐予測論理回路３２３は、分岐先アドレスＡＤを第１のセレクタＳＬ１〜ＳＬｎに出力する。
【００６１】
Ｔステージ３０２における分岐方向予測論理回路５０３が出力する分岐方向ＢＤは、Ｍステージ３０３における分岐予測論理回路３２３が出力する分岐先アドレスＡＤよりも先に結果が出ている。分岐方向ＢＤは、スレッド番号ＳＮと共に、スレッド調停回路３１１に入力され、次に命令フェッチを行うスレッドが決定される。これにより、分岐することが予測される分岐命令のスレッドをスケジュールしないことが可能となる。その詳細は、後に図６を参照しながら説明する。
【００６２】
本実施形態では、大規模履歴テーブル３２１を有する図３の分岐予測回路２０４よりも低レイテンシの分岐方向予測回路５０１を設ける。小規模履歴テーブル５０２は、１つ以上の少数の分岐命令の分岐方向（分岐先）を記憶するエントリを記憶する。これにより、小規模履歴テーブル５０２に保持したエントリにヒットする場合において、分岐方向予測のレイテンシを短縮し、分岐命令のフェッチ開始から命令フェッチのスレッド選択に反映されるまでのレイテンシを短縮する。
【００６３】
小規模履歴テーブル５０２及び大規模履歴テーブル３２１は、図２の分岐履歴更新部２１４により更新される。記憶素子としての小規模履歴テーブル５０２と大規模履歴テーブル３２１との特性には、素子遅延と記憶密度との間で利害得失がある。小規模履歴テーブル５０２の記憶素子は、大規模履歴テーブル３２１の記憶素子に対して、遅延時間が短いが、記憶密度（回路量に対するデータ容量）が低い。大規模履歴テーブル３２１は、小規模履歴テーブル５０２に対して遅延が大きいが、記憶密度が高い。性能向上や回路量削減のために、記憶素子の最適な使い分けが行われる。大規模履歴テーブル３２１は、例えばＳＲＡＭであり、多数のエントリを記憶する。小規模履歴テーブル５０２は、例えばラッチ回路であり、少数のエントリ（例えば１個）を記憶する。小規模履歴テーブル５０２のエントリ数は、大規模履歴テーブル３２１のエントリ数よりも少ない。分岐方向予測回路５０１の構成例は、後に図９及び図１０を参照しながら説明する。
【００６４】
分岐先アドレスＡＤの予測完了に先行して、分岐方向ＢＤの予測が完了する。予測された分岐方向ＢＤが分岐する旨を示す場合は、次のアドレスの後続命令をフェッチしても実行されることはなく、パイプライン処理をキャンセル（命令処理の取り消し）して、予測された分岐先命令のフェッチをやり直すため、必ず無駄となる。この場合、分岐方向ＢＤの予測が完了した際に、分岐先アドレスＡＤはまだ予測されていないことから、分岐先命令をフェッチすることはできない。そこで、スレッド調停回路３１１において、別のスレッドをスケジュールすることにより、命令のキャンセルを回避し、命令フェッチスループットの効率化を図る。以下、その詳細を説明する。
【００６５】
図６は、図５の演算処理装置１０１のパイプライン処理例を示す図である。以下、図６が図４と異なる点を説明する。時刻ｔ２において、分岐命令ＡのＴステージ３０２では、命令アドレスＡＣが小規模履歴テーブル（分岐方向予測テーブル）５０２にヒットし、分岐方向予測論理回路５０３は、分岐する旨を示す分岐方向ＢＤを出力する。スレッド選択情報ＳＩは、スレッド調停回路３１１に入力される。スレッド選択情報ＳＩは、分岐方向ＢＤ及びスレッド番号ＳＮを含む。この場合、スレッド番号ＳＮは、命令Ｘが属する第２のスレッドの番号である。
【００６６】
次に、時刻ｔ３では、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、スレッド番号ＳＮが示す第２のスレッドの命令Ｙを選択し、命令ＹのＡステージ３０１が実行される。また、時刻ｔ３では、分岐命令ＡのＭステージ３０３が実行され、分岐予測論理回路３２３は、分岐先アドレスＡＤを第１のセレクタＳＬ１〜ＳＬｎに出力する。第１のセレクタＳＬ１〜ＳＬｎは、スレッド調停回路３１１の制御により、分岐する旨を示す分岐方向ＢＤを基に、分岐先アドレスＡＤを選択する。
【００６７】
次に、時刻ｔ４では、分岐先命令ＣのＡステージ３０１が実行される。具体的には、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、分岐する旨を示す分岐方向ＢＤを基に、分岐命令Ａが属する第１のスレッドのアドレスＡＢ１を選択し、分岐先命令ＣのＡステージ３０１を実行する。本実施形態によれば、時刻ｔ３の分岐命令ＡのＭステージ３０３の直後に、時刻ｔ４の分岐先命令ＣのＡステージ３０１を実行することができる。これにより、図６では、図４に比べ、分岐先命令Ｃの命令フェッチレイテンシが短縮される。
【００６８】
分岐方向ＢＤの予測結果を用いて、第２のスレッドの命令Ｘ及び命令Ｙをスケジューリングすることにより、図４のような後続命令Ｂのキャンセルを回避することができる。これにより、図６では、図４に比べ、第２のスレッドの命令Ｙは、命令フェッチ時刻が早くなる。
【００６９】
後続命令Ｂのキャンセルは回避され、命令フェッチスループットが効率化されたことにあわせ、上記のように命令フェッチレイテンシ及び命令フェッチスループットの両面で、命令フェッチ部２０３の効率が向上する。
【００７０】
図７は、図５の演算処理装置１０１の他のパイプライン処理例を示す図であり、分岐方向ＢＤが分岐しない旨を示す場合を示す。以下、図７が図６と異なる点を説明する。第２のセレクタ３１３は、スレッド調停回路３１１の制御により、基本的に第１のスレッド及び第２のスレッドを交互に選択する。
【００７１】
時刻ｔ２において、分岐命令ＡのＴステージ３０２では、命令アドレスＡＣが小規模履歴テーブル（分岐方向予測テーブル）５０２にヒットせず、分岐方向予測論理回路５０３は、分岐しない旨を示す分岐方向ＢＤを出力する。スレッド選択情報ＳＩは、スレッド調停回路３１１に入力される。スレッド選択情報ＳＩは、分岐方向ＢＤ及びスレッド番号ＳＮを含む。
【００７２】
次に、時刻ｔ３では、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、分岐しない旨を示す分岐方向ＢＤを基に、第１のスレッドの後続命令Ｂを選択し、後続命令ＢのＡステージ３０１が実行される。後続命令Ｂは、時刻ｔ４でＴステージ３０２が実行され、時刻ｔ５でＭステージ３０３が実行され、時刻ｔ６でＢステージ３０４が実行される。
【００７３】
次に、時刻ｔ４では、第２のスレッドの命令ＹのＡステージ３０１が実行される。具体的には、第２のセレクタ３１３は、スレッド調停回路３１１の制御により、分岐しない旨を示す分岐方向ＢＤを基に、第２のスレッドの命令Ｙを選択し、命令ＹのＡステージ３０１を実行する。命令Ｙは、時刻ｔ５でＴステージ３０２が実行され、時刻ｔ６でＭステージ３０３が実行され、時刻ｔ７でＢステージ３０４が実行される。
【００７４】
本実施形態によれば、分岐しない旨の分岐方向ＢＤが予測された場合にも、効率的なパイプライン処理を行うことができる。
【００７５】
以上のように、分岐予測回路２０４は、第２のセレクタ３１３により選択されたアドレスＡＣを基に、選択されたアドレスＡＣの命令が分岐命令である場合にその分岐命令が分岐するか否かを示す分岐方向ＢＤを予測してＴステージ（第１のサイクルステージ）３０２で出力し、そのＴステージ（第１のサイクルステージ）３０２より後のＭステージ（第２のサイクルステージ）３０３で上記の分岐命令の分岐先アドレスＡＤを予測して出力する。
【００７６】
分岐予測回路２０４は、過去の分岐命令の分岐履歴を記憶する大規模履歴テーブル（第１の履歴テーブル）３２１と、過去の分岐命令の分岐履歴を記憶する小規模履歴テーブル（第２の履歴テーブル）５０２とを有する。分岐予測回路２０４は、大規模履歴テーブル３２１を用いて分岐先アドレスＡＤを予測し、小規模履歴テーブル５０２を用いて分岐方向ＢＤを予測する。
【００７７】
スレッド調停回路３１１は、分岐予測回路２０４により出力される分岐方向ＢＤを基に第１のセレクタＳＬ１〜ＳＬｎ及び第２のセレクタ３１３の選択を制御する。第１のセレクタＳＬ１〜ＳＬｎは、分岐予測回路２０４により出力される分岐先アドレスＡＤを入力する。
【００７８】
第１のセレクタＳＬ１〜ＳＬｎは、予測された分岐方向ＢＤが分岐する旨を示す場合には分岐先アドレスＡＤを選択し、予測された分岐方向ＢＤが分岐しない旨を示す場合にはｎ個のスレッドの命令アドレスＡＡ１〜ＡＡｎを選択する。
【００７９】
第２のセレクタ３１３は、予測された分岐方向ＢＤが分岐する旨を示す場合（図６）には分岐命令Ａが属する第１のスレッドとは異なる第２のスレッドの命令Ｙのアドレスを選択し、予測された分岐方向ＢＤが分岐しない旨を示す場合（図７）には分岐命令Ａが属する第１のスレッドと同じ第１のスレッドの後続命令Ｂのアドレスを選択する。
【００８０】
図８は、命令フェッチ部２０３及び一次命令キャッシュ２０５の構成例を示す図である。命令フェッチ部２０３は、Ａステージ３０１、Ｔステージ３０２、Ｍステージ３０３、Ｂステージ３０４及びＲステージ３０５のパイプラインを有する。Ａステージ３０１は、命令アドレス生成の機能を有する。Ｔステージ３０２は、分岐先アドレスの履歴読み出しの機能を有する。Ｍステージ３０３は、分岐予測の完了を行う機能を有する。Ｂステージ３０４は、命令フェッチパイプラインのその他後段の機能（命令の伝送処理）を有する。Ｒステージ３０５は、命令バッファの処理である。一次命令キャッシュ２０５は、命令アドレスをインデックスとしてタグ・データを読み出し、タグ・データと比較し、一致した命令を命令バッファ２０６に出力する。
【００８１】
本実施形態では、Ｔステージ３０２で分岐方向ＢＤの予測が完了し、Ｍステージ３０３で分岐先アドレスＡＤの予測が完了し、効率的なパイライン処理を行うことができる。
【００８２】
図９は、図５の分岐方向予測回路５０１の構成例を示す図である。比較器９０２及び論理積（ＡＮＤ）回路９０３は、図５の分岐方向予測論理回路５０３に対応する。命令アドレスＡＣは、上位ビットアドレスであるタグＡＣ１及び下位ビットアドレスであるインデックスＡＣ２に分割される。パイプラインレジスタ９０１は、クロック信号に同期して、タグＡＣ１をラッチして出力する。小規模履歴テーブル（分岐方向予測テーブル）５０２は、１個以上の少数のエントリを記憶し、低レイテンシのラッチ回路などの素子を用いて構成する。エントリは、インデックスＡＣ２に対応する分岐方向ＢＡ及びタグＡＣ３である。小規模履歴テーブル５０２は、インデックスＡＣ２を入力し、インデックスＡＣ２に対応する分岐方向ＢＡ及びタグＡＣ３を出力する。比較回路９０２は、フリップフロップ９０１が出力するタグＡＣ１及び小規模履歴テーブル５０２が出力するタグＡＣ３を比較し、両者が一致しているとき（ヒットのとき）には「１」を予測有効信号ＢＢとして出力し、両者が不一致のとき（ミスのとき）には「０」を予測有効信号ＢＢとして出力する。論理積回路９０３は、予測有効信号ＢＢ及び分岐方向ＢＡの論理積信号を分岐方向ＢＤとして出力する。予測有効信号ＢＢが「１」のときには、分岐方向ＢＤは分岐方向ＢＡと同じになり、予測有効信号ＢＢが「０」のときには、分岐方向ＢＤは「０」になる。分岐方向ＢＤは、「１」が分岐する旨を示し、「０」が分岐しない旨を示す。
【００８３】
なお、分岐予測回路２０４は、分岐命令に限らず他の命令も予測対象とするとことができる。その場合、分岐予測回路２０４は、命令が分岐命令であるかを含めて予測し、命令が分岐命令であるかどうかは後段の命令デコーダ２０７で確定する。
【００８４】
高遅延の大規模履歴テーブル３２１の記憶素子は、例えば高密度素子のＲＡＭ（ランダムアクセスメモリ：Random Access Memory）である。低遅延の小規模履歴テーブル５０２の記憶素子は、大規模履歴テーブル３２１に対して、低遅延な素子を用いた記憶素子であれば良い。小規模履歴テーブル５０２の記憶素子は、例えばラッチ回路又はフリップフロップであるが、これらに限られない。低遅延な分岐方向予測回路５０１は、ＣＡＭ（Content Addressable Memory）によって構成しても良い。
【００８５】
小規模履歴テーブル５０２は、ダイレクトマップであってもセットアソシアティブであってもフルアソシアティブであっても良い。エントリ数は、１エントリ以上あれば良い。小規模履歴テーブル５０２のインデックスのビット幅は問わない。インデックスは、命令アドレスの関数であれば良い。例えば、命令アドレスの任意のハッシュをインデックスとしても良い。タグＡＣ１は、予測精度と引き換えに、ビット幅を減らしてもよい。
【００８６】
また、分岐予測回路２０４は、低遅延な分岐方向予測回路５０１とは別に、予測精度の高い分岐方向予測回路を持っていても良い。
【００８７】
図１０は、図５の分岐方向予測回路５０１の他の構成例を示す図である。図１０の分岐方向予測回路５０１は、図９の分岐方向予測回路５０１に対して、論理積回路９０３を削除したものである。以下、図１０が図９と異なる点を説明する。小規模履歴テーブル５０２は、分岐方向ＢＡを省略し、分岐すると予想される分岐命令のみに対応するエントリを記憶する。小規模履歴テーブル５０２は、インデックスＡＣ２に対応するタグＡＣ３を出力する。比較回路９０２は、タグＡＣ１及びＡＣ３を比較し、両者が一致するときには「１」の分岐方向ＢＤを出力し、両者が不一致のときには「０」の分岐方向ＢＤを出力する。
【００８８】
図１１は、図５のスレッド調停回路３１１の構成例を示す図である。ここでは、第１のスレッド及び第２のスレッドの２スレッドを調停する場合を例に示す。スレッド番号ＳＮは、「０」が第１のスレッドを示し、「１」が第２のスレッドを示す。排他的論理和回路１１０４は、インバータ１１０２の出力信号及びスレッド番号ＳＮの排他的論理和信号を出力する。論理積回路１１０５は、排他的論理和回路１１０４の出力信号の論理反転信号と分岐方向ＢＤとの論理積信号を出力する。ラッチ回路１１０１は、クロック信号に同期して、排他的論理和回路１１０３の出力信号をラッチして出力する。インバータ１１０２は、フリップフロップ１１０１の出力信号の論理反転信号を出力する。排他的論理和回路１１０３は、インバータ１１０２の出力信号と論理積回路１１０５の出力信号との排他的論理和信号をスレッド番号ＳＮとして第２のセレクタ３１３に出力する。第２のセレクタは、スレッド番号ＳＮが「０」のときには第１のスレッドのアドレスＡＢ１を選択し、スレッド番号ＳＮが「１」のときには第２のスレッドのアドレスＡＢ２を選択し、アドレスＡＣを出力する。
【００８９】
まず、図７のように分岐方向ＢＤが分岐しない旨を示す場合を説明する。その場合、分岐方向ＢＤは「０」であり、論理積回路１１０５は「０」を出力する。すると、排他的論理和回路１１０３は、インバータ１１０２の出力信号をそのまま出力する。例えば、フリップフロップ１１０１の出力信号が「１」の場合、インバータ１１０２は「０」の信号を出力し、排他的論理和回路１１０３は「０」のスレッド番号ＳＮを第２のセレクタ３１３に出力する。第２のセレクタ３１３は、スレッド番号ＳＮが「０」であるので、第１のスレッドのアドレスＡＢ１を選択し、命令アドレスＡＣとして出力する。
【００９０】
次に、フリップフロップ１１０１は、排他的論理和回路１１０３から「０」のスレッド番号ＳＮを入力し、「０」の信号を出力する。すると、インバータ１１０２は「１」の信号を出力し、排他的論理和回路１１０３は「１」のスレッド番号ＳＮを第２のセレクタ３１３に出力する。第２のセレクタ３１３は、スレッド番号ＳＮが「１」であるので、第２のスレッドのアドレスＡＢ２を選択し、命令アドレスＡＣとして出力する。
【００９１】
以後、同様に、第２のセレクタ３１３は、第１のスレッドのアドレスＡＢ１と第２のスレッドのアドレスＡＢ２とを交互に選択して出力する。
【００９２】
次に、図６のように分岐方向ＢＤが分岐する旨を示す場合を説明する。その場合、分岐方向ＢＤは「１」であり、スレッド番号ＳＮは分岐命令Ａが属する第１のスレッドを示す「０」である。例えば、図６の時刻ｔ２では、命令ＸのＡステージ３０１が実行される。その時、命令Ｘは、第２のスレッドであるので、その後、インバータ１１０２は「０」の信号を出力する。すると、排他的論理和回路１１０４は、「０」のスレッド番号ＳＮとインバータ１１０２の「０」の出力信号との排他的論理和信号として「０」の信号を出力し、論理積回路１１０５は「１」の信号を出力する。すると、排他的論理和回路１１０３は、インバータ１１０２の出力信号の論理反転信号をスレッド番号ＳＮとして出力する。この場合、インバータ１１０２の出力信号が「０」であるので、スレッド番号ＳＮは「１」になる。第２のセレクタ３１３は、スレッド番号ＳＮが「１」であるので、第２のスレッドのアドレスＡＢ２を選択し、命令アドレスＡＣとして出力する。その結果、図６の時刻ｔ３では、第２のスレッドの命令ＹのＡステージ３０１が実行される。
【００９３】
図１２は、図５のスレッド調停回路３１１の他の構成例を示す図であり、２個以上のスレッドの調停を行うことができる。スレッド調停回路３１１は、ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎ、スケジューラ１２０１及びセレクタ１２０２を有する。スレッド選択情報ＳＩは、分岐方向ＢＤ及びスレッド番号ＳＮを含む。ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎは、スレッド選択情報ＳＩを基に、それぞれの優先順位に従い、ｎ個のスレッドの中でフェッチ可能なスレッドの番号を１つ出力する。ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎは、それぞれ優先順位が異なる。例えば、第１のプライオリティエンコーダＰＥ１は、第１のスレッドが最も優先順位が高く、第ｎのプライオリティエンコーダＰＥｎは、第ｎのスレッドが最も優先順位が高い。セレクタ１２０２は、スケジューラ１２０１の制御により、ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎの出力信号のうちの１個を選択して出力する。スケジューラ１２０１は、ｎ個のプライオリティエンコーダＰＥ１〜ＰＥｎの出力信号が均等に選ばれるように制御することにより、特定のスレッドの選択回数が多くなりすぎることを防止できる。なお、スケジューラ１２０１は、任意のスケジューリングポリシーによって、いずれかのスレッドを優先して選択するように制御してもよい。
【００９４】
また、命令フェッチ部２０３と命令デコーダ２０７との間には、命令バッファ２０６があってもなくても良い。命令フェッチ部２０３は、パイプライン化され、複数スレッドに対しサイクル粒度の時分割で、命令コードと分岐予測回路２０４により命令フェッチ制御を行う装置であれば良い。命令フェッチ部２０３は、同一スレッドの複数命令を同一サイクルに同時にフェッチするものであっても良い。
【００９５】
また、パイプライン段数は問わず、分岐予測レイテンシも問わない。パイプラインの構成方式は、同期、非同期を問わず、ウェーブパイプラインを構成してもよい。
【００９６】
また、１コアあたり複数の命令フェッチ部２０３を持つ演算処理装置であっても良い。すなわち、命令フェッチ部２０３より後段の回路を、他の命令フェッチ部２０３と共用しても良い。言い換えると、複数の命令フェッチ部２０３と合わせて全体で、同一サイクルで複数スレッドに対する命令フェッチ制御を構成してもよい。
【００９７】
また、ハードウエアスレッド数は２スレッド又はそれ以上であってもよい。基本とするスレッドスケジューリング方式は問わず、ラウンドロビン方式以外のスケジューリング方式であっても、命令フェッチに先行して分岐方向を予測することで、不要な命令フェッチを避けることができる。
【００９８】
また、演算処理装置１０１が採用する命令セットアーキテクチャは問わない。ＲＩＳＣ（縮小命令セットコンピュータ：Reduced Instruction Set Computer）であってもＣＩＳＣ（複合命令 セットコンピュータ：Complex Instruction Set Computer）であってもＶＬＩＷ（超長命令語：Very Long Instruction Word）であっても良い。
【００９９】
また、命令デコーダ２０７の形式は、問わず、順序制御又はスーパースカラであっても、ＶＬＩＷであっても良く、静的・動的なコード変換を行ってもよい。
【０１００】
また、命令実行部の形態は問わない。命令実行部は、単一サイクル実行であっても、パイプライン制御であっても、順序制御であっても良く、スーパースカラ実行であっても良く、アウトオブオーダ実行であってもインオーダ実行であってもよい。演算器制御は、ＳＩＭＤ（Single Instruction Multiple Data）型であってもよく、プロセッサコア外の演算資源を制御する形態であってもよい。また、命令完了形式は、問わず、投機的実行や正確な割り込みを実現していてもしていなくてもよい。
【０１０１】
以上のように、本実施形態によれば、分岐先アドレスＡＤの予測に先行して分岐方向ＢＤを予測することにより、効率的なスレッド選択が可能になり、処理速度を向上させることができる。
【０１０２】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１０３】
２０４ 分岐予測回路
２０５ 一次命令キャッシュ
３０１ Ａステージ
３０２ Ｔステージ
３０３ Ｍステージ
３１１ スレッド調停回路
３１２ パイプラインレジスタ
３１３ 第２のセレクタ
３２１ 大規模履歴テーブル
３２２ パイプラインレジスタ
３２３ 分岐予測論理回路
５０１ 分岐方向予測回路
５０２ 小規模履歴テーブル
５０３ 分岐方向予測論理回路
５０４ パイプラインレジスタ
ＳＬ１〜ＳＬｎ 第１のセレクタ
【特許請求の範囲】
【請求項１】
複数のスレッドの命令を複数のサイクルステージ毎に実行する演算処理装置において、
入力した複数のスレッドの命令の命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して、前記複数のスレッドのアドレスを出力する第１のセレクタと、
前記第１のセレクタが出力した複数のスレッドのアドレスのうち、いずれか１個のスレッドのアドレスを選択する第２のセレクタと、
前記複数のサイクルステージのうち第１のサイクルステージで、前記第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を前記選択されたアドレスに基づき予測して出力するとともに、前記第１のサイクルステージより後の第２のサイクルステージで、前記予測対象の分岐命令の分岐先アドレスを前記選択されたアドレスに基づき予測して出力する分岐予測回路と、
前記分岐予測回路が出力した前記分岐方向に基づき、前記第１セレクタ及び第２のセレクタによるスレッドのアドレスの選択を制御するスレッド調停回路と、を有することを特徴とする演算処理装置。
【請求項２】
前記分岐予測回路は、
過去の分岐命令の分岐方向及び分岐先アドレスの履歴を記憶する第１の履歴テーブルを用いて前記予測対象分岐命令の分岐先アドレスを予測し、
過去の分岐命令の分岐方向の履歴を記憶する第２の履歴テーブルを用いて前記予測対象分岐命令の分岐方向を予測することを特徴とする請求項１記載の演算処理装置。
【請求項３】
前記第２の履歴テーブルのエントリ数は、前記第１の履歴テーブルのエントリ数よりも少ないことを特徴とする請求項２記載の演算処理装置。
【請求項４】
前記第１のセレクタは、
前記予測された分岐方向が分岐する旨を示す場合には前記分岐先アドレスを選択し、前記予測された分岐方向が分岐しない旨を示す場合には前記複数のスレッドの命令の命令アドレスを選択することを特徴とする請求項１〜３のいずれか１項に記載の演算処理装置。
【請求項５】
前記第２のセレクタは、
前記予測された分岐方向が分岐する旨を示す場合、前記複数のスレッドのうち前記分岐命令が属するスレッドと異なるスレッドのアドレスを選択し、前記予測された分岐方向が分岐しない旨を示す場合、前記分岐命令が属するスレッドと同じスレッドのアドレスを選択することを特徴とする請求項１〜４のいずれか１項に記載の演算処理装置。
【請求項６】
複数のスレッドの命令を複数のサイクルステージ毎に実行する演算処理装置の制御方法において、
前記演算処理装置が有する第１のセレクタが、入力した複数のスレッドの命令の命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して複数のスレッドのアドレスを出力し、
前記演算処理装置が有する第２のセレクタが、前記第１のセレクタが出力した複数のスレッドのアドレスのうち、いずれか１個のスレッドのアドレスを選択し、
前記演算処理装置が有する分岐予測回路が、前記複数のサイクルステージのうち第１のサイクルステージで、前記第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を、前記選択されたアドレスに基づき予測して出力するとともに、前記複数のサイクルステージのうち前記第１のサイクルステージより後の第２のサイクルステージで、前記予測対象の分岐命令の分岐先アドレスを前記選択されたアドレスに基づき予測して出力することを特徴とする演算処理装置の制御方法。
【請求項１】
複数のスレッドの命令を複数のサイクルステージ毎に実行する演算処理装置において、
入力した複数のスレッドの命令の命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して、前記複数のスレッドのアドレスを出力する第１のセレクタと、
前記第１のセレクタが出力した複数のスレッドのアドレスのうち、いずれか１個のスレッドのアドレスを選択する第２のセレクタと、
前記複数のサイクルステージのうち第１のサイクルステージで、前記第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を前記選択されたアドレスに基づき予測して出力するとともに、前記第１のサイクルステージより後の第２のサイクルステージで、前記予測対象の分岐命令の分岐先アドレスを前記選択されたアドレスに基づき予測して出力する分岐予測回路と、
前記分岐予測回路が出力した前記分岐方向に基づき、前記第１セレクタ及び第２のセレクタによるスレッドのアドレスの選択を制御するスレッド調停回路と、を有することを特徴とする演算処理装置。
【請求項２】
前記分岐予測回路は、
過去の分岐命令の分岐方向及び分岐先アドレスの履歴を記憶する第１の履歴テーブルを用いて前記予測対象分岐命令の分岐先アドレスを予測し、
過去の分岐命令の分岐方向の履歴を記憶する第２の履歴テーブルを用いて前記予測対象分岐命令の分岐方向を予測することを特徴とする請求項１記載の演算処理装置。
【請求項３】
前記第２の履歴テーブルのエントリ数は、前記第１の履歴テーブルのエントリ数よりも少ないことを特徴とする請求項２記載の演算処理装置。
【請求項４】
前記第１のセレクタは、
前記予測された分岐方向が分岐する旨を示す場合には前記分岐先アドレスを選択し、前記予測された分岐方向が分岐しない旨を示す場合には前記複数のスレッドの命令の命令アドレスを選択することを特徴とする請求項１〜３のいずれか１項に記載の演算処理装置。
【請求項５】
前記第２のセレクタは、
前記予測された分岐方向が分岐する旨を示す場合、前記複数のスレッドのうち前記分岐命令が属するスレッドと異なるスレッドのアドレスを選択し、前記予測された分岐方向が分岐しない旨を示す場合、前記分岐命令が属するスレッドと同じスレッドのアドレスを選択することを特徴とする請求項１〜４のいずれか１項に記載の演算処理装置。
【請求項６】
複数のスレッドの命令を複数のサイクルステージ毎に実行する演算処理装置の制御方法において、
前記演算処理装置が有する第１のセレクタが、入力した複数のスレッドの命令の命令アドレス又は予測対象の分岐命令の分岐先アドレスを選択して複数のスレッドのアドレスを出力し、
前記演算処理装置が有する第２のセレクタが、前記第１のセレクタが出力した複数のスレッドのアドレスのうち、いずれか１個のスレッドのアドレスを選択し、
前記演算処理装置が有する分岐予測回路が、前記複数のサイクルステージのうち第１のサイクルステージで、前記第２のセレクタが選択したアドレスの分岐命令が分岐するかを示す分岐方向を、前記選択されたアドレスに基づき予測して出力するとともに、前記複数のサイクルステージのうち前記第１のサイクルステージより後の第２のサイクルステージで、前記予測対象の分岐命令の分岐先アドレスを前記選択されたアドレスに基づき予測して出力することを特徴とする演算処理装置の制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１３−６９１２９（Ｐ２０１３−６９１２９Ａ）
【公開日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願番号】特願２０１１−２０７３５４（Ｐ２０１１−２０７３５４）
【出願日】平成２３年９月２２日（２０１１．９．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願日】平成２３年９月２２日（２０１１．９．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]