(57)【要約】  並列処理の粒度が細かいスレッドを実行する際に、分岐予測の精度を向上する。ＣＰＵ（＃０）は、時刻（ｔ０）にて、並列処理の粒度が細かいスレッド（１−０）をＣＰＵ（＃１）で実行する際に、スレッド１種別用分岐予測情報（１０４）を読み出し、分岐予測テーブル（１０６＃１）に書き込む。スレッド（１−０）の動作終了後、ＣＰＵ（＃０）は、分岐予測テーブル（１０６＃１）に蓄積された分岐予測情報をスレッド１種別用分岐予測情報（１０４）に書き込む。ＣＰＵ（＃０）は、上記動作を時刻（ｔ１）、時刻（ｔ３）でも行い、スレッド１種別用の分岐予測情報を蓄積し、分岐予測の精度を向上させる。
2012127589.tif 000002
【特許請求の範囲】
【請求項１】
複数のＣＰＵと、
前記複数のＣＰＵのそれぞれに対応して設けられる複数の分岐予測メモリと、
前記複数のＣＰＵで実行される複数のスレッドのそれぞれに対応する分岐予測情報を格納する共有分岐予測メモリと、
を含み、
前記複数のＣＰＵの内の第１ＣＰＵによって実行される前記複数のスレッドの内の第１スレッドに対応する分岐予測情報を前記共有分岐予測メモリから前記第１ＣＰＵに対応する前記分岐予測メモリに設定すること
を特徴とするマルチコアプロセッサシステム。
【請求項２】
さらに、前記分岐予測情報を前記共有分岐予測メモリから前記分岐予測メモリに転送するバスを含むこと
を特徴とする請求項１に記載のマルチコアプロセッサシステム。
【請求項３】
前記第１スレッドの動作終了時、前記第１ＣＰＵに対応する前記分岐予測メモリの分岐予測情報が前記共有分岐予測メモリに書き込まれること
を特徴とする請求項１または請求項２に記載のマルチコアプロセッサシステム。
【請求項４】
前記共有分岐予測メモリは、メインメモリに対応すること
を特徴とする請求項１乃至請求項３の何れか一に記載のマルチコアプロセッサシステム。
【請求項５】
さらに、前記メインメモリ内の前記分岐予測情報の少なくとも一部を格納する共有分岐予測キャッシュを含むこと
を特徴とする請求項４に記載のマルチコアプロセッサシステム。
【請求項６】
前記第１スレッドに対応する分岐予測情報は、前記第１スレッドより前に実行された第２スレッドに関する分岐予測情報をも含むこと
を特徴とする請求項１乃至請求項５の何れか一に記載のマルチコアプロセッサシステム。
【請求項７】
複数のＣＰＵの内の第１ＣＰＵは、
第１スレッドに対応する分岐予測情報を共有分岐予測メモリから前記第１ＣＰＵに対応する分岐予測メモリに書き込み、
前記第１スレッドに対応する分岐予測情報に基づいて、分岐予測を行って前記第１スレッドを実行すること
を特徴とする分岐予測方法。
【請求項８】
前記第１スレッドの動作終了時、前記第１ＣＰＵに対応する前記分岐予測メモリの分岐予測情報を前記共有分岐予測メモリに書き込むこと
を特徴とする請求項７に記載の分岐予測方法。
【請求項９】
前記共有分岐予測メモリ内に有効な前記第１スレッドに対応する分岐予測情報が存在しないとき、分岐予測情報が格納されていないテーブルをクリアし、前記テーブルから前記第１スレッドに対応する分岐予測情報を読み出すこと
を特徴とする請求項７または請求項８に記載の分岐予測方法。
【請求項１０】
前記第１スレッドに対応する分岐予測情報は、前記第１スレッドより前に実行された第２スレッドに関する分岐予測情報をも含むこと
を特徴とする請求項７乃至請求項９の何れか一に記載の分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐命令の結果を予測するマルチコアプロセッサシステム、および分岐予測方法に関する。
【背景技術】
【０００２】
従来から、１つのシステム内に、複数のコアを有するマルチコアプロセッサシステムの形態を採用する機器が増加している。また、複数のコアを利用して、アプリケーションプログラム（以下、「アプリ」と称す）を複数のスレッドに分割し、スレッド単位での並列を行うことで、マルチコアプロセッサシステムは、単一のコアで処理を実行する場合より高速処理を可能にしている。なお、スレッドとはプログラムの実行単位である。また、スレッド単位の並列処理の性能をより高める方法として、スレッドの処理量を細かくし、細粒度並列性を用いるといった技術も開示されている。【０００３】
また、コアの高速化技術について、コアが１命令で実行するフェッチ、解釈、実行といったステージに分割し、パイプライン式で各ステージを実行するパイプライン処理が開示されている。パイプライン処理により、コアは、複数の命令を、ステージをずらして同時に実行することで処理性能を向上することができる。【０００４】
しかし、パイプライン処理で命令を実行するケースにおいて、コアは、先行する命令の結果によって後続する命令が変化する分岐命令を読み込むと、次に実行すべき命令が判断できない。この場合、コアは、パイプラインを停止し、分岐命令が完了するまで待機することになり、処理性能が低下する。【０００５】
このような分岐命令による処理性能の低下を避けるため、分岐方向を予測する分岐予測技術が開示されている。分岐予測技術を適用し、分岐命令が完了する前に次に実行すべき命令を予測することで、予測が正しかった場合に処理性能の低下を避けることができる。分岐予測技術は、静的分岐予測と動的分岐予測とに大別できる。静的分岐予測は、プログラム内に分岐方向のヒントを記載し、実行時にヒントを参照して分岐方向を予測する方法である。動的分岐予測とは、コアのメモリに過去の分岐の履歴や個々の分岐先、分岐頻度の情報（以下、分岐予測情報と称する）を保持し、実行時に分岐予測情報を参照して分岐方向を予測する方法である。【０００６】
たとえば、動的分岐予測を行う技術として、たとえば、特定の分岐命令に対する過去の分岐履歴と、現時点より前に実行された分岐命令群に対応する分岐履歴とを用いて、分岐予測を行う技術が開示されている。また、動的分岐予測の精度を向上させる技術として、たとえば、複数のコアで実行されている複数のスレッドに対して、各スレッドから他のコアで実行されている別スレッドの分岐予測情報を参照する技術が開示されている（たとえば、下記特許文献１、２を参照。）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平９−２４４８９１号公報
【特許文献２】特開２００６−５３８３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した従来技術において、動的分岐予測にて保持される分岐予測情報は、コアの持つメモリに保持される。メモリの容量は有限であるため、コアは、分岐予測情報群のうち、古い分岐予測情報や、参照頻度の低い分岐予測情報等から削除し、新しい分岐予測情報で上書きする。また、動的分岐予測は、過去に充分な回数以上実行されていない分岐命令に対する分岐予測情報では、予測精度が悪く、処理性能が低下する。【０００９】
したがって、各コアが細粒度並列性での並列処理を行うと、スレッドあたりの処理ステップ数が小さくなり、同一の処理、または相関性のある処理を実行するスレッドを１種別とみなした場合の総種類数は増加する。このように、細粒度並列性で並列処理における動的予測分岐は、１つの分岐命令の実行回数が少なくなるため、分岐予測の予測精度が悪化し、処理性能が低下するという問題があった。また、細粒度並列性で並列処理における動的予測分岐は、総種類数が増加するため、相関性のない命令列が次々に実行される。したがって、分岐予測情報が次々に上書きされることになり、分岐予測の予測精度が悪化するという問題があった。【００１０】
本発明は、上述した従来技術による問題点を解消するため、並列処理の粒度が細かいスレッドを実行する際に、分岐予測の精度を向上できるマルチコアプロセッサシステム、および分岐予測方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、本発明の一側面によれば、複数のＣＰＵと、複数のＣＰＵのそれぞれに対応して設けられる複数の分岐予測メモリと、複数のＣＰＵで実行される複数のスレッドのそれぞれに対応する分岐予測情報を格納する共有分岐予測メモリと、を含み、複数のＣＰＵの内の第１ＣＰＵによって実行される複数のスレッドの内の第１スレッドに対応する分岐予測情報を共有分岐予測メモリから第１ＣＰＵに対応する分岐予測メモリに設定するマルチコアプロセッサシステム、および分岐予測方法が提案される。
【発明の効果】
【００１２】
本発明の一側面によれば、並列処理の粒度が細かいスレッドを実行する際に、分岐予測の精度を向上できるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１】図１は、実施の形態１にかかるマルチコアプロセッサシステム１００の動作を示す説明図である。
【図２】図２は、実施の形態１にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。
【図３】図３は、マルチコアプロセッサシステム１００の機能を示すブロック図である。
【図４】図４は、マルチコアプロセッサシステム１００のソフトウェアを示すブロック図である。
【図５】図５は、独立分岐予測テーブル３０２の記憶内容の一例を示す説明図である。
【図６】図６は、共有分岐予測テーブル３０４の記憶内容の一例を示す説明図である。
【図７】図７は、スレッド種別識別子の設定方法を示す説明図である。
【図８】図８は、マルチコアプロセッサシステム１００が正常動作を行う場合のシーケンス図である。
【図９】図９は、マルチコアプロセッサシステム１００が中断動作を行う場合のシーケンス図である。
【図１０】図１０は、スレッドの起動処理を示すフローチャートである。
【図１１】図１１は、スレッドの動作終了処理を示すフローチャートである。
【図１２】図１２は、実施の形態２にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。
【図１３】図１３は、実施の形態３にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。
【図１４】図１４は、実施の形態３にかかるスレッドの起動処理を示すフローチャート（その１）である。
【図１５】図１５は、実施の形態３にかかるスレッドの割り当て開始を示すフローチャート（その２）である。
【図１６】図１６は、実施の形態３にかかるスレッドの動作終了処理を示すフローチャートである。
【図１７】図１７は、実施の形態４にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。
【図１８】図１８は、実施の形態４にかかる共有分岐予測テーブル１７０１の記憶内容の一例を示す説明図である。
【発明を実施するための形態】
【００１４】
以下に添付図面を参照して、開示のマルチコアプロセッサシステム、分岐予測方法、および分岐予測プログラムの実施の形態１〜４を詳細に説明する。
【００１５】
（実施の形態１の説明）
図１は、実施の形態１にかかるマルチコアプロセッサシステム１００の動作を示す説明図である。符号１０１で示す説明図は、アプリ１０３内にて実行されるスレッドの例を示している。符号１０２で示す説明図は、アプリ１０３内にて実行されるスレッドにおける分岐予測精度の状態を示している。
【００１６】
アプリ１０３は、スレッド１−０、スレッド１−１、スレッド１−２、スレッド１−３、スレッド１−４、スレッド２−０、スレッド２−０’、スレッド２−１を実行する。スレッド１−０〜スレッド１−４はお互いに相関性のある処理であり、スレッド種別をスレッド１種別と呼称する。同様に、スレッド２−０〜スレッド２−１はお互いに相関性のある処理であり、スレッド種別をスレッド２種別と呼称する。スレッド１種別に属するスレッドとスレッド２種別に属するスレッドに関しては、相関性がない。
【００１７】
また、スレッドの処理順序としては、アプリ１０３はスレッド１−０の実行要求を発行する。次に、アプリ１０３は、スレッド１−０の結果を利用するスレッド１−１、スレッド２−０の実行要求を発行する。続けて、アプリ１０３は、スレッド１−１の結果とスレッド２−０の結果を用いて判定を行う。判定結果がＹｅｓであれば、アプリ１０３は、スレッド１−２と、スレッド２−１を実行する。なお、スレッド２−１は、スレッド１−１の結果を利用し、スレッド２−０の結果を利用しない。したがって、スレッド２−１は、スレッド１−１終了時点で判定を待たずに投機実行可能である。
【００１８】
スレッド１−２とスレッド２−１の終了後、アプリ１０３は、スレッド１−２の結果とスレッド２−１の結果を利用するスレッド１−３の実行要求を発行し、スレッド１−３の終了後、スレッド１−３の結果を利用するスレッド１−４の実行要求を発行する。
【００１９】
また、判定結果がＮｏであれば、アプリ１０３は、スレッド２−０’の実行要求を発行し、スレッド２−０’の結果を利用するスレッド１−４の実行要求を発行する。なお、判定結果がＮｏである場合、アプリ１０３は、スレッド２−１の結果を利用しない。
【００２０】
次に、符号１０２で示す説明図では、アプリ１０３内にて実行されるスレッドにおける分岐予測精度の状態を示している。マルチコアプロセッサシステム１００は、ＣＰＵ＃０〜ＣＰＵ＃２を含み、さらにスレッド１種別用分岐予測情報１０４と、スレッド２種別用分岐予測情報１０５と、を含む。また、時刻ｔ０の時点では、スレッド１種別用分岐予測情報１０４の記憶内容とスレッド２種別用分岐予測情報１０５の記憶内容は、初期値である。また、ＣＰＵ＃１、ＣＰＵ＃２は、分岐予測情報を格納する分岐予測テーブル１０６＃１、分岐予測テーブル１０６＃２を含む。
【００２１】
時刻ｔ０にて、スレッド１−０の起動開始を受けると、ＣＰＵ＃０は、スレッド１種別用分岐予測情報１０４を読み出し、スレッド１−０を実行するＣＰＵ＃１の分岐予測テーブル１０６＃１に書き込む。時刻ｔ０〜時刻ｔ１にて、ＣＰＵ＃１は、スレッド１種別に属するスレッド１−０を実行し、分岐予測情報となる分岐命令の分岐結果を分岐予測テーブル１０６＃１に蓄積していく。時刻ｔ１にてスレッド１−０が完了し、動作終了すると、ＣＰＵ＃１は、スレッド１種別用分岐予測情報１０４に分岐予測テーブル１０６＃１に蓄積された分岐予測情報を書き込む。
【００２２】
以降、スレッド１種別に属するスレッドを起動開始する場合、ＣＰＵ＃０は、スレッド１種別用分岐予測情報１０４を読み出して、分岐予測テーブル１０６に書き込む。同様に、スレッド２種別に属するスレッドを起動開始する場合、ＣＰＵ＃０は、スレッド２種別用分岐予測情報１０５を読み出して、分岐予測テーブル１０６に書き込む。
【００２３】
なお、時刻ｔ０〜時刻ｔ１は短い時間を想定しており、蓄積された分岐予測情報量は少ない。図１の例では、ＣＰＵ＃１が、分岐予測精度が良くなる回数の１／３程分岐命令を実行した場合を想定している。したがって、時刻ｔ１でのスレッド１−０実行に伴う分岐予測の精度は悪い。
【００２４】
次に、時刻ｔ１にて、スレッド１−１の起動開始を受けると、ＣＰＵ＃０は、スレッド１種別用分岐予測情報１０４を読み出し、スレッド１−１を実行するＣＰＵ＃１の分岐予測テーブル１０６＃１に書き込む。同様に、スレッド２−０の起動開始を受けると、ＣＰＵ＃０は、スレッド２種別用分岐予測情報１０５を読み出し、スレッド２−０を実行するＣＰＵ＃１の分岐予測テーブル１０６＃１に書き込む。
【００２５】
時刻ｔ１〜時刻ｔ２にて、分岐予測テーブル１０６＃１にはスレッド１の分岐予測情報が蓄積され、分岐予測テーブル１０６＃２にはスレッド２の分岐予測情報が蓄積される。分岐予測テーブル１０６＃１には、時刻ｔ０〜時刻ｔ１間で蓄積された分岐予測情報も含まれており、全体として、分岐予測精度が良くなる回数の２／３程蓄積されることになり、分岐予測の精度が中程度となる。また、分岐予測テーブル１０６＃２には、時刻ｔ１〜時刻ｔ２間で蓄積された分岐予測情報として、分岐予測精度が良くなる回数の１／３程蓄積されることになり、分岐予測の精度は悪い。
【００２６】
時刻ｔ２にて、ＣＰＵ＃１は、スレッド２−１を投機実行する。また、ＣＰＵ＃０は、スレッド１−１、スレッド２−０の結果を用いて判定を行う。符号１０２で示す図では、判定結果がＮｏとなったので、ＣＰＵ＃０は、スレッド２−１の結果が不要となるため、スレッド２−１の投機実行を中断する。スレッド２−１は投機実行を行わない場合、本来実行されないスレッドであり、投機実行により蓄積された分岐予測情報は、他に悪影響を与える。したがって、ＣＰＵ＃０は、スレッド２−１により蓄積された分岐予測情報を破棄する。
【００２７】
時刻ｔ３〜時刻ｔ４にて、分岐予測テーブル１０６＃１にはスレッド２の分岐予測情報が蓄積され、分岐予測テーブル１０６＃２にはスレッド１の分岐予測情報が蓄積される。分岐予測テーブル１０６＃１には、時刻ｔ１〜時刻ｔ２間で蓄積された分岐予測情報も含まれており、全体として、分岐予測精度が良くなる回数の２／３程分岐予測情報が蓄積されることになり、分岐予測の精度が中程度となる。また、分岐予測テーブル１０６＃２には、既に蓄積された分岐予測情報と併せて、分岐予測精度が良くなる回数分、分岐予測情報が蓄積されることになり、分岐予測の精度は良くなる。
【００２８】
時刻ｔ４にて、ＣＰＵ＃０は、分岐予測テーブル１０６＃１、分岐予測テーブル１０６＃２に、スレッド１種別用分岐予測情報１０４を読み出す。時刻ｔ４におけるスレッド１種別用分岐予測情報１０４は、充分に分岐予測情報が蓄積されているため、ＣＰＵ＃１とＣＰＵ＃２は、スレッド１−３とスレッド１−４を高速に実行することができる。
【００２９】
このように、本実施の形態１にかかるマルチコアプロセッサシステム１００は、スレッドごとに分岐予測結果の履歴を持ち、コアがスレッドを実行する度に、対応する履歴を設定し、終了後回収する。これにより、マルチコアプロセッサシステム１００は、粒度が小さくすぐ終了してしまうスレッドでも履歴を蓄積でき、予測精度を向上することができる。以下、図１で示した動作を実現するためのマルチコアプロセッサシステム１００のハードウェア、ソフトウェアの説明を行う。
【００３０】
（マルチコアプロセッサシステム１００のハードウェア）
図２は、実施の形態１にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。図２において、マルチコアプロセッサシステム１００は、ＣＰＵを複数搭載するＣＰＵｓ２０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ）２０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２０３と、を含む。また、マルチコアプロセッサシステム１００は、フラッシュＲＯＭ２０４と、フラッシュＲＯＭコントローラ２０５と、フラッシュＲＯＭ２０６と、を含む。また、マルチコアプロセッサシステム１００は、ユーザやその他の機器との入出力装置として、ディスプレイ２０７と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）２０８と、キーボード２０９と、を含む。また、各部はバス２１０によってそれぞれ接続されている。
【００３１】
ここで、ＣＰＵｓ２０１は、マルチコアプロセッサシステム１００の全体の制御を司る。ＣＰＵｓ２０１は、シングルコアのプロセッサを並列して接続した全てのＣＰＵを指している。ＣＰＵｓ２０１は、ＣＰＵ＃０〜ＣＰＵ＃２を含む。また、ＣＰＵｓ２０１は、少なくとも２つ以上のＣＰＵを含んでいてもよい。ＣＰＵ＃０〜ＣＰＵ＃２は、それぞれ専用のキャッシュメモリを有する。また、マルチコアプロセッサシステムとは、コアが複数搭載されたプロセッサを含むコンピュータのシステムである。コアが複数搭載されていれば、複数のコアが搭載された単一のプロセッサでもよく、シングルコアのプロセッサが並列されているプロセッサ群でもよい。なお、本実施の形態では、シングルコアのプロセッサであるＣＰＵが並列されている形態を例にあげて説明する。
【００３２】
また、ＣＰＵ＃０〜ＣＰＵ＃２は、分岐予測情報バス２１１を通じて、共有分岐予測レジスタ２１２にアクセス可能である。共有分岐予測レジスタ２１２は、ＣＰＵ＃０〜ＣＰＵ＃２が共有して利用する分岐予測情報が格納されている。
【００３３】
ＲＯＭ２０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ２０３は、ＣＰＵｓ２０１のワークエリアとして使用される。フラッシュＲＯＭ２０４は、読出し速度が高速なフラッシュＲＯＭであり、たとえば、ＮＯＲ型フラッシュメモリである。フラッシュＲＯＭ２０４は、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）などのシステムソフトウェアやアプリケーションソフトウェアなどを記憶している。たとえば、ＯＳを更新する場合、マルチコアプロセッサシステム１００は、Ｉ／Ｆ２０８によって新しいＯＳを受信し、フラッシュＲＯＭ２０４に格納されている古いＯＳを、受信した新しいＯＳに更新する。
【００３４】
フラッシュＲＯＭコントローラ２０５は、ＣＰＵｓ２０１の制御にしたがってフラッシュＲＯＭ２０６に対するデータのリード／ライトを制御する。フラッシュＲＯＭ２０６は、データの保存、運搬を主に目的としたフラッシュＲＯＭであり、たとえば、ＮＡＮＤ型フラッシュメモリである。フラッシュＲＯＭ２０６は、フラッシュＲＯＭコントローラ２０５の制御で書き込まれたデータを記憶する。データの具体例としては、マルチコアプロセッサシステム１００を使用するユーザがＩ／Ｆ２０８を通して取得した画像データ、映像データなどや、また本実施の形態にかかる分岐予測方法を実行するプログラムなどを記憶してもよい。フラッシュＲＯＭ２０６は、たとえば、メモリカード、ＳＤカードなどを採用することができる。
【００３５】
ディスプレイ２０７は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。ディスプレイ２０７は、たとえば、ＴＦＴ液晶ディスプレイなどを採用することができる。
【００３６】
Ｉ／Ｆ２０８は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク２１３に接続され、ネットワーク２１３を介して他の装置に接続される。そして、Ｉ／Ｆ２０８は、ネットワーク２１３と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２０８には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００３７】
キーボード２０９は、数字、各種指示などの入力のためのキーを有し、データの入力を行う。また、キーボード２０９は、タッチパネル式の入力パッドやテンキーなどであってもよい。
【００３８】
（マルチコアプロセッサシステム１００の機能）
次に、マルチコアプロセッサシステム１００の機能について説明する。図３は、マルチコアプロセッサシステム１００の機能を示すブロック図である。マルチコアプロセッサシステム１００は、検出部３１１と、読出部３１２と、書込部３１３と、読出部３１４と、書込部３１５と、を含む。この制御部となる機能（検出部３１１〜書込部３１５）は、記憶装置に記憶されたプログラムをＣＰＵｓ２０１が実行することにより、その機能を実現する。記憶装置とは、たとえば、図２に示したＲＯＭ２０２、ＲＡＭ２０３、フラッシュＲＯＭ２０４、フラッシュＲＯＭ２０６などである。なお、図３では、検出部３１１〜書込部３１５は、マスタＣＰＵとなるＣＰＵ＃０の機能として図示されているが、ＣＰＵ＃１、またはＣＰＵ＃２の機能であってもよい。
【００３９】
また、マルチコアプロセッサシステム１００は、メインメモリ３０１、独立分岐予測テーブル３０２、共有分岐予測テーブル３０４にアクセス可能である。ＣＰＵ＃０〜ＣＰＵ＃２は、他ＣＰＵの独立分岐予測テーブル３０２にアクセスする際には、独立分岐予測テーブルＩ／Ｆ３０３を介してアクセスする。また、図３では、ＣＰＵ＃０がメインスレッド３０５を実行する。また、メインスレッド３０５の実行要求によって、ＣＰＵ＃１がサブスレッド３０６を実行する。
【００４０】
メインメモリ３０１は、ＣＰＵｓ２０１からアクセス可能な主記憶装置である。たとえば、メインメモリ３０１は、ＲＡＭ２０３全体であったり、ＲＡＭ２０３の一部であったりしてもよい。
【００４１】
独立分岐予測テーブル３０２は、動的な分岐予測機構でアクセスされる分岐予測情報を記憶する。動的な分岐予測機構としては、たとえば、Ｂｉ−Ｍｏｄａｌ方式、Ｇ−Ｓｈａｒｅ方式、パーセプトロン分岐予測方式、または前述の方式を組み合わせた方式などである。独立分岐予測テーブル３０２の詳細は、図５にて後述する。また、独立分岐予測テーブル３０２は、ＣＰＵ＃０〜ＣＰＵ＃２がそれぞれ有し、それぞれのレジスタに記憶されている。
【００４２】
独立分岐予測テーブルＩ／Ｆ３０３は、ＣＰＵの外部から、各ＣＰＵが有する独立分岐予測テーブル３０２中の分岐予測情報に対して、読み込み可能、書き込み可能にするＩ／Ｆである。共有分岐予測テーブル３０４は、スレッド種類ごとに分岐予測情報を格納するテーブルである。共有分岐予測テーブル３０４の詳細は、図６にて後述する。
【００４３】
検出部３１１は、複数のスレッドのうち第１スレッドを複数のＣＰＵのうち第１ＣＰＵで実行されることを検出する機能を有する。また、検出部３１１は、第１スレッドが動作終了することを検出してもよい。たとえば、検出部３１１は、サブスレッド３０６がＣＰＵ＃１で実行されることを検出する。なお、対象のスレッドが実行されるという情報は、ＣＰＵ＃０のレジスタ、キャッシュメモリ、メインメモリ３０１等に記憶される。
【００４４】
読出部３１２は、検出部３１１によって検出された第１スレッドに対応する分岐予測情報を各ＣＰＵで共有された分岐予測の履歴を記憶するメモリから読み出す機能を有する。たとえば、読出部３１２は、サブスレッド３０６に対応する分岐予測情報を共有分岐予測テーブル３０４から読み出す。
【００４５】
また、読出部３１２は、各ＣＰＵで共有された分岐予測の履歴を記憶するメモリに第１スレッドに対応する分岐予測情報がない場合、分岐予測情報が記憶されていない領域をクリアし、クリアした領域を第１スレッドに対応する分岐予測情報として読み出してもよい。なお、読み出された分岐予測情報は、ＣＰＵ＃０のレジスタ、キャッシュメモリ等に記憶される。
【００４６】
書込部３１３は、読出部３１２によって読み出された分岐予測情報を第１ＣＰＵに対応する分岐予測の履歴を記憶するメモリに書き込む機能を有する。たとえば、書込部３１３は、ＣＰＵ＃１の独立分岐予測テーブル３０２＃１に分岐予測情報を書き込む。なお、書き込みが行われたという情報は、ＣＰＵ＃０のレジスタ、キャッシュメモリ、メインメモリ３０１等に記憶されてもよい。
【００４７】
読出部３１４は、第１スレッドの動作終了時、第１ＣＰＵに対応する分岐予測の履歴を記憶するメモリ内の分岐予測情報を読み出す機能を有する。たとえば、読出部３１４は、サブスレッド３０６の実行終了時、ＣＰＵ＃１の独立分岐予測テーブル３０２＃１内の分岐予測情報を読み出す。なお、読み出された分岐予測情報は、ＣＰＵ＃０のレジスタ、キャッシュメモリ等に記憶される。
【００４８】
書込部３１５は、読出部３１２によって読み出された分岐予測情報を各ＣＰＵで共有された分岐予測の履歴を記憶するメモリに書き込む機能を有する。たとえば、書込部３１５は、読み出された分岐予測情報を、共有分岐予測テーブル３０４に書き込む。なお、書き込みが行われたという情報は、ＣＰＵ＃０のレジスタ、キャッシュメモリ、メインメモリ３０１等に記憶されてもよい。
【００４９】
図４は、マルチコアプロセッサシステム１００のソフトウェアを示すブロック図である。図４におけるマルチコアプロセッサシステム１００は、スレッド制御ライブラリ（マスタ）４０１とスレッド制御ライブラリ（スレイブ）４０２＃１とスレッド制御ライブラリ（スレイブ）４０２＃２とを実行する。さらに、マルチコアプロセッサシステム１００は、分岐予測制御ライブラリ４０３を実行する。
【００５０】
また、マルチコアプロセッサシステム１００は、メインスレッド３０５と、メインスレッド３０５の要求によって実行されるスレッドＡ１、スレッドＡ２、スレッドＢ１、スレッドＢ２、スレッドＣ１、スレッドＣ２、スレッドＤ１、スレッドＤ２を実行する。なお、スレッドＡ１とスレッドＡ２は、スレッドＡという同一のスレッド種別に属する。同様に、スレッドＢ１とスレッドＢ２は、スレッドＢという同一のスレッド種別に属し、スレッドＣ１とスレッドＣ２は、スレッドＣという同一のスレッド種別に属し、スレッドＤ１とスレッドＤ２は、スレッドＤという同一のスレッド種別に属する。
【００５１】
また、ＣＰＵ＃０は、スレッド制御ライブラリ（マスタ）４０１と、分岐予測制御ライブラリ４０３と、メインスレッド３０５と、を実行する。ＣＰＵ＃１は、メインスレッド３０５がスレッド制御ライブラリ（マスタ）４０１、スレッド制御ライブラリ（スレイブ）４０２＃１を介して行ったスレッド起動要求にしたがって、スレッドＡ１〜スレッドＤ２を実行する。ＣＰＵ＃２も同様に、スレッド制御ライブラリ（マスタ）４０１、スレッド制御ライブラリ（スレイブ）４０２＃２を介して行ったスレッド起動要求にしたがって、スレッドＡ１〜スレッドＤ２を実行する。
【００５２】
このように、マルチコアプロセッサシステム１００は、組み込みシステムでよく採用される、ＣＰＵコアに特定のスレッドを割り当てるＡＭＰ（Ａｓｙｍｍｅｔｒｉｃ  ＭｕｌｔｉＰｒｏｃｅｓｓｉｎｇ）の形態をとっている。また、マルチコアプロセッサシステム１００は、ＣＰＵの立場が対等なＳＭＰ（Ｓｙｍｍｅｔｒｉｃ  ＭｕｌｔｉＰｒｏｃｅｓｓｉｎｇ）の形態をとってもよい。
【００５３】
スレッド制御ライブラリ（マスタ）４０１とスレッド制御ライブラリ（スレイブ）４０２は、メインスレッド３０５からのスレッド起動要求に基づいて、スケジューリングを行ったうえでスレッドを実行させる機能を有する。たとえば、スレッド制御ライブラリ（マスタ）４０１は、メインスレッド３０５からのスレッド起動要求に基づいて、スケジューリングを行ったうえでスレッドＡ１を実行させるように、スレッド制御ライブラリ（スレイブ）４０２に通知する。通知を受けたスレッド制御ライブラリ（スレイブ）４０２は、スレッドＡ１をＣＰＵ＃１に実行させる。
【００５４】
また、スレッド制御ライブラリ（マスタ）４０１とスレッド制御ライブラリ（スレイブ）４０２は、スレッドの動作が終了したタイミングでメインスレッド３０５にスレッドの動作完了を通知する機能を有する。たとえば、スレッド制御ライブラリ（スレイブ）４０２は、スレッドＡ１の動作が終了した場合、スレッド制御ライブラリ（マスタ）４０１に通知する。通知を受けたスレッド制御ライブラリ（マスタ）４０１は、メインスレッド３０５にスレッドの動作が終了したことを通知する。
【００５５】
分岐予測制御ライブラリ４０３は、スレッド制御ライブラリ（マスタ）４０１のスレッド起動、スレッド制御ライブラリ（スレイブ）４０２のスレッド動作終了のタイミングで、共有分岐予測テーブル３０４のアクセスや、分岐予測情報の転送を行う機能を有する。たとえば、分岐予測制御ライブラリ４０３は、スレッドＡ１が起動された場合、共有分岐予測テーブル３０４にアクセスし、スレッドＡに対応する分岐予測テーブル情報を、ＣＰＵ＃１に転送する。
【００５６】
図５は、独立分岐予測テーブル３０２の記憶内容の一例を示す説明図である。独立分岐予測テーブル３０２は、ＧＨＲ（Ｇｌｏｂａｌ  Ｈｉｓｔｏｒｙ  Ｒｅｇｉｓｔｅｒ）５０１、ＰＨＴ（Ｐａｔｔｅｒｎ  Ｈｉｓｔｏｒｙ  Ｔａｂｌｅ）５０２、ＢＴＢ（Ｂｒａｎｃｈ  Ｔａｒｇｅｔ  Ｂｕｆｆｅｒ）５０３を含む。また、独立分岐予測テーブル３０２は、ＧＨＲ５０１〜ＢＴＢ５０３を操作する回路、機能部として、ＢＴＢ更新回路５０４、ＧＨＲ更新回路５０５、ＰＨＴ更新回路５０６、エントリ選択部５０７、アドレス一致部５０８、予測方向判定部５０９を含む。また、独立分岐予測テーブルＩ／Ｆ３０３は、分岐予測情報となるＧＨＲ５０１〜ＢＴＢ５０３を更新する。
【００５７】
ＧＨＲ５０１は、過去数回分の分岐命令が成立したか不成立だったかを記憶するレジスタである。分岐命令の成立時を示す識別子は、成立を示す“Ｔ”、不成立を示す“Ｎ”となる。たとえば、ＧＨＲ５０１は、過去４回の分岐命令の成立結果として、成立、成立、不成立、成立を記憶する。
【００５８】
ＰＨＴ５０２は、分岐命令が成立しやすい傾向にあるか不成立となる傾向にあるのかを数ビットの飽和カウンタ等で表現したテーブルである。ＰＨＴ５０２が取り得る値としては、分岐しない可能性が大きいことを示す“２’ｂ００”、分岐しない可能性が小さいことを示す“２’ｂ０１”、分岐する可能性が小さいことを示す“２’ｂ１０”、分岐する可能性が大きいことを示す“２’ｂ１１”である。なお、“２’ｂ”は２進数であることを示している。
【００５９】
ＢＴＢ５０３は、分岐命令ごとに分岐先アドレスを記憶するバッファである。ＢＴＢ５０３は、テーブルは、有効フラグ、分岐元命令アドレス、分岐先命令アドレスという３つのフィールドを含む。有効フラグフィールドには、該当のレコードが有効であるか否かを示す値が格納される。たとえば、有効フラグフィールドが“１”であれば、該当のレコードが有効であることを示す。また、有効フラグフィールドが“０”であれば、該当のレコードが無効であることを示す。分岐元命令アドレスフィールドには、分岐命令となるアドレスが格納される。分岐先命令アドレスフィールドには、分岐する場合の分岐先アドレスが格納される。
【００６０】
ＢＴＢ更新回路５０４は、分岐元命令アドレスと分岐先命令アドレスとに基づいて、ＢＴＢ５０３を更新する回路である。具体的に、ＢＴＢ更新回路５０４は、分岐元命令アドレスの下位ビットを用いてＢＴＢ５０３のレコードを選択し、有効フラグと、分岐元命令アドレスと分岐先命令アドレスを設定する。
【００６１】
ＧＨＲ更新回路５０５は、分岐先方向に基づいて、ＧＨＲ５０１を更新する回路である。具体的に、ＧＨＲ更新回路５０５は、分岐先方向から分岐命令の成立または不成立を示す１［ビット］の情報を受信し、ＧＨＲ５０１に設定する。
【００６２】
ＰＨＴ更新回路５０６は、分岐元命令アドレスと分岐先方向とに基づいて、ＰＨＴ５０２を更新する回路である。具体的に、ＰＨＴ更新回路５０６は、分岐元命令アドレスの下位ビットを用いてＰＨＴ５０２のレコードを選択し、ＰＨＴ５０２内のカウンタを変更する。より詳細には、ＰＨＴ更新回路５０６は、分岐先方向が分岐成立を示す情報であればカウンタをインクリメントし、分岐先方向が分岐不成立を示す情報であればカウンタをデクリメントする。
【００６３】
エントリ選択部５０７は、予測対象アドレスの下位ビットとＧＨＲ５０１に基づいて、ＰＨＴ５０２のレコードを選択する機能を有する。たとえば、エントリ選択部５０７は、予測対象アドレスの下位ビットにＧＨＲ５０１のビット列を結合して、ＰＨＴ５０２のレコードを一意に選択可能なデータを生成する。また、エントリ選択部５０７は、ＰＨＴ５０２のレコードを一意に選択可能なデータとして、予測対象アドレスの下位ビットとＧＨＲ５０１のビット列とのＸＯＲを算出してもよい。
【００６４】
アドレス一致部５０８は、予測対象アドレスの上位ビットと分岐元命令アドレスとが一致しているか否かを判断する。一致した場合、アドレス一致部５０８は、アドレスが一致した旨を示す信号を出力する。
【００６５】
予測方向判定部５０９は、予測対象アドレスに対応する分岐命令が分岐するか否かを判定する機能を有する。具体的に、予測方向判定部５０９は、アドレス一致部５０８からアドレスが一致したという信号を受け取り、かつ、エントリ選択部５０７によって選択されたレコードが、分岐する可能性がある場合に、分岐が成立するとして分岐先方向を出力する。
【００６６】
以上の機能により、独立分岐予測テーブル３０２に予測対象アドレスが入力された場合、独立分岐予測テーブル３０２は、出力として分岐が成立するか否かを分岐先方向として出力し、また、分岐先命令アドレスを出力する。
【００６７】
図６は、共有分岐予測テーブル３０４の記憶内容の一例を示す説明図である。共有分岐予測テーブル３０４は、タグ情報、分岐予測テーブル情報という２つのフィールドを含む。タグ情報フィールドには、さらに、有効フラグ、スレッド種別識別子という２つのフィールドを含む。有効フラグフィールドには、該当の分岐予測情報が有効であるか否かを示す値が格納される。たとえば、有効フラグフィールドが“１”であれば、分岐予測情報が有効であることを示す。
【００６８】
スレッド種別識別子フィールドには、スレッド種別を識別する情報が格納される。スレッド種別を識別する情報としては、たとえば、スレッドを一意に特定できる情報として、命令列の先頭アドレスをスレッド種別としてもよい。また、スレッド種別識別子は、相関性のあるスレッドごとに共通の識別子を設定してもよい。具体的なスレッド種別識別子の設定方法については、図７にて後述する。
【００６９】
分岐予測テーブル情報は、図５に示したＧＨＲ５０１に対応するＧＨＲフィールド、ＰＨＴ５０２に対応するＰＨＴフィールド、ＢＴＢ５０３に対応するＢＴＢフィールドという３つのフィールドを含む情報である。分岐予測テーブル情報の各フィールドの記憶内容は図５で説明したＧＨＲ５０１〜ＢＴＢ５０３に等しいため、説明を省略する。
【００７０】
以下、１スレッド分のタグ情報と分岐予測テーブル情報を合わせて共有分岐予測テーブル３０４の１エントリと呼称する。たとえば、図６で示す共有分岐予測テーブル３０４は、エントリ６０１〜エントリ６０４の合計４エントリが登録されている。
【００７１】
たとえば、エントリ６０１は、スレッド種別識別子がスレッドＡであり、分岐予測テーブル情報として、ＧＨＲフィールドに全て分岐成立、ＰＨＴフィールドに“２’ｂ１０”、“２’ｂ１１”の２レコードが登録されている。さらに、エントリ６０１は、ＢＴＢフィールドに２レコードが登録されている。２レコードの詳細は、分岐元命令アドレス“０ｘ００００１０００”、分岐先命令アドレス“０ｘ２０００Ｃ４００”からなるレコードと、分岐元命令アドレス“０ｘ００００１ＣＣ０”、分岐先命令アドレス“０ｘＣ０Ｆ０００００”からなるレコードである。
【００７２】
また、エントリ６０２は、スレッド種別識別子がスレッドＢであり、分岐予測テーブル情報として、ＧＨＲフィールドに分岐成立、分岐不成立、分岐不成立、分岐成立、ＰＨＴフィールドに“２’ｂ００”、“２’ｂ１１”の２レコードが登録されている。さらに、エントリ６０２は、ＢＴＢフィールドに１レコードが登録されている。１レコードの詳細は、分岐元命令アドレス“０ｘ００００１ＣＣ０”、分岐先命令アドレス“０ｘＦＤ０１００００”からなるレコードである。
【００７３】
また、エントリ６０３は、スレッド種別識別子がスレッドＣであり、分岐予測テーブル情報として、ＧＨＲフィールドに分岐不成立、分岐成立、分岐不成立、分岐不成立、ＰＨＴフィールドに“２’ｂ１０”、“２’ｂ１１”の２レコードが登録されている。さらに、エントリ６０３は、ＢＴＢフィールドに２レコードが登録されている。２レコードの詳細は、分岐元命令アドレス“０ｘ００００１０００”、分岐先命令アドレス“０ｘ２０００Ｃ０００”からなるレコードと、分岐元命令アドレス“０ｘ００００１ＣＣ０”、分岐先命令アドレス“０ｘ４００００３００”からなるレコードである。
【００７４】
また、エントリ６０４は、スレッド種別識別子がスレッドＤであり、分岐予測テーブル情報として、ＧＨＲフィールドに全て分岐成立、ＰＨＴフィールドに“２’ｂ００”、“２’ｂ０１”の２レコードが登録されている。なお、エントリ６０４のＢＴＢフィールドには、有効なレコードが存在しない。
【００７５】
図７は、スレッド種別識別子の設定方法を示す説明図である。図７では、マルチコアプロセッサシステム１００が画像処理を行う場合におけるスレッド種別識別子の設定方法について説明する。マルチコアプロセッサシステム１００は、画像７０１について特定の処理を行うことを想定する。特定の処理とは、たとえば、色調補正であったり、色相彩度変換であったり、どのような処理であってもよい。
【００７６】
マルチコアプロセッサシステム１００は、画像７０１を領域１〜領域４に分割して処理を行う。分割された領域について、ＣＰＵ＃０が領域１に対してスレッドＡ種別に属するスレッド、スレッドＢ種別に属するスレッド、スレッドＣ種別に属するスレッドの順に実行する。以下、説明を簡略化するため、実行されるスレッドは、それぞれスレッドＡ１、スレッドＢ１、スレッドＣ１であると想定する。同様に、ＣＰＵ＃１が領域２に対して、ＣＰＵ＃２が領域３に対して、スレッドＡ１、スレッドＢ１、スレッドＣ１の順に実行する。
【００７７】
このとき、特定のエントリのスレッド種別識別子がスレッドＡ種別に設定されると、特定のエントリは、グループ７０２に属するスレッド群によってアクセスされることになる。また、特定のエントリのスレッド種別識別子を、領域１を示す識別子に設定すると、特定のエントリが、グループ７０３に属するスレッド群によってアクセスされることになる。領域１を示す識別子としては、領域１の先頭アドレスや、ファイルシステム上のファイルポインタ等である。
【００７８】
同様に、特定のエントリのスレッド種別識別子を、領域２を示す識別子に設定すると、特定のエントリが、グループ７０４に属するスレッド群によってアクセスされる。また、特定のエントリのスレッド種別識別子を、領域３を示す識別子に設定すると、特定のエントリが、グループ７０５に属するスレッド群によってアクセスされる。
【００７９】
このように、スレッド種別識別子をデータに関する識別子に設定すると、データの分類によって分岐命令の結果が変化する場合、マルチコアプロセッサシステム１００は、予測精度を向上することができる。
【００８０】
図８は、マルチコアプロセッサシステム１００が正常動作を行う場合のシーケンス図である。図８では、ＣＰＵ＃０がメインスレッド３０５、スレッド制御ライブラリ（マスタ）４０１、分岐予測制御ライブラリ４０３を実行する。また、ＣＰＵ＃１が独立分岐予測テーブル３０２＃１にアクセスし、スレッド制御ライブラリ（スレイブ）４０２、スレッド１を実行する。
【００８１】
メインスレッド３０５は、スレッド起動要求をスレッド制御ライブラリ（マスタ）４０１に通知する（ステップＳ８０１）。通知を受け取ったスレッド制御ライブラリ（マスタ）４０１は、さらにスレッド起動準備要求を分岐予測制御ライブラリ４０３に通知する（ステップＳ８０２）。
【００８２】
スレッド起動準備要求を受け取った分岐予測制御ライブラリ４０３は、起動要求のあったスレッド種別識別子を用いて、共有分岐予測テーブル３０４から分岐予測情報を読み出す（ステップＳ８０３）。分岐予測制御ライブラリ４０３は、読み出し完了（ステップＳ８０４）後、独立分岐予測テーブル３０２＃１に、読み出した分岐予測情報を書き込む（ステップＳ８０５）。分岐予測制御ライブラリ４０３は、書き込み完了（ステップＳ８０６）後、スレッド起動準備完了をスレッド制御ライブラリ（マスタ）４０１に通知する（ステップＳ８０７）。
【００８３】
スレッド起動準備完了を受け取ったスレッド制御ライブラリ（マスタ）４０１は、スレッド起動要求をスレッド制御ライブラリ（スレイブ）４０２＃１に通知し（ステップＳ８０８）、メインスレッド３０５にスレッド起動完了を通知する（ステップＳ８０９）。
【００８４】
スレッド起動要求を受け取ったスレッド制御ライブラリ（スレイブ）４０２は、ＣＰＵ＃１にてスレッド１を起動させる（ステップＳ８１０）。ＣＰＵ＃１は、スレッド１実行中では、独立分岐予測テーブル３０２＃１にアクセスし、分岐予測を行う。
【００８５】
スレッド１の動作が終了すると、スレッド制御ライブラリ（スレイブ）４０２は、スレッド動作終了を受け取り（ステップＳ８１１）、スレッド制御ライブラリ（マスタ）４０１にスレッド動作終了を通知する（ステップＳ８１２）。
【００８６】
スレッド動作終了を受け取ったスレッド制御ライブラリ（マスタ）４０１は、メインスレッドにスレッド動作終了を通知しつつ（ステップＳ８１３）、分岐予測制御ライブラリ４０３にスレッド動作終了通知を通知する（ステップＳ８１４）。通知を受け取った分岐予測制御ライブラリ４０３は、独立分岐予測テーブル３０２＃１から分岐予測情報を読み出す（ステップＳ８１５）。
【００８７】
分岐予測制御ライブラリ４０３は、読み出し完了（ステップＳ８１６）後、共有分岐予測テーブル３０４に、読み出した分岐予測情報を書き込む（ステップＳ８１７）。分岐予測制御ライブラリ４０３は、書き込み完了（ステップＳ８１８）後、スレッド動作終了完了をスレッド制御ライブラリ（マスタ）４０１に通知する（ステップＳ８１９）。
【００８８】
図９は、マルチコアプロセッサシステム１００が中断動作を行う場合のシーケンス図である。図９における中断動作のシーケンス図において、ステップＳ９０１〜ステップＳ９１０で示すシーケンスは、ステップＳ８０１〜ステップＳ８１０で示すシーケンスと同様であるため、説明を省略する。
【００８９】
メインスレッド３０５がスレッド制御ライブラリ（マスタ）４０１にスレッド中断要求を通知する（ステップＳ９１１）。通知を受け取ったスレッド制御ライブラリ（マスタ）４０１は、スレッド制御ライブラリ（スレイブ）４０２＃１にスレッド中断要求を通知し（ステップＳ９１２）、メインスレッド３０５にスレッド中断応答を通知する（ステップＳ９１３）。
【００９０】
スレッド中断要求を受け取ったスレッド制御ライブラリ（スレイブ）４０２＃１は、スレッド１を中断させ（ステップＳ９１４）、スレッド中断終了をスレッド制御ライブラリ（マスタ）４０１に通知する（ステップＳ９１５）。スレッド中断終了を受け取ったスレッド制御ライブラリ（マスタ）４０１は、スレッド動作中断通知を通知する（ステップＳ９１６）。スレッド動作中断通知を受け取った分岐予測制御ライブラリ４０３は、共有分岐予測テーブル３０４を更新せずに、スレッド動作中断完了をスレッド制御ライブラリ（マスタ）４０１に通知する（ステップＳ９１７）。スレッド動作中断完了を受け取ったスレッド制御ライブラリ（マスタ）４０１は、メインスレッド３０５にスレッド動作中断完了を通知する（ステップＳ９１８）。
【００９１】
次に、図８、図９で示したシーケンス図の動作を満たすような分岐予測制御ライブラリ４０３の処理を図１０、図１１にて示す。図１０がスレッドの起動処理のフローチャートを示し、図１１がスレッドの動作終了処理のフローチャートを示す。なお、スレッドの動作終了処理が発生する場合としては、スレッドの処理が完了する場合、スレッドの処理が中断されて終了する場合である。
【００９２】
図１０は、スレッドの起動処理を示すフローチャートである。ＣＰＵ＃０は、起動するスレッドのスレッド種別識別子を取得する（ステップＳ１００１）。取得後、ＣＰＵ＃０は、スレッド種別識別子を用いて共有分岐予測テーブル３０４にアクセスする（ステップＳ１００２）。ＣＰＵ＃０は、アクセスした結果、有効な分岐予測情報が存在するか否か判断する（ステップＳ１００３）。有効な分岐予測情報が存在する場合（ステップＳ１００３：Ｙｅｓ）、ＣＰＵ＃０は、共有分岐予測テーブル３０４から分岐予測情報を読み出す（ステップＳ１００４）。
【００９３】
有効な分岐予測情報がない場合（ステップＳ１００３：Ｎｏ）、ＣＰＵ＃０は、共有分岐予測テーブル３０４の空きエントリを検索する（ステップＳ１００５）。なお、空きエントリとは、有効フラグが“０”のエントリのことである。検索後、ＣＰＵ＃０は、空きエントリが存在するか否かを判断する（ステップＳ１００６）。空きエントリが存在する場合（ステップＳ１００６：Ｙｅｓ）、ＣＰＵ＃０は、空きエントリをクリアし、取得したスレッド種別識別子を設定して有効化し（ステップＳ１００７）、クリアされた分岐予測情報を読み出す（ステップＳ１００８）。
【００９４】
なお、エントリをクリアするとは、具体的には、分岐予測情報の予測結果を中立状態にすることである。たとえば、ＣＰＵ＃０は、ＰＨＴ５０２を分岐しない（可能性小）に設定する。また、エントリのクリアについては、独立分岐予測テーブル３０２の仕様にしたがって予測結果をクリアしてもよい。
【００９５】
空きエントリが存在しない場合（ステップＳ１００６：Ｎｏ）、または、ステップＳ１００４、ステップＳ１００８の終了後、ＣＰＵ＃０は、スレッドを実行するＣＰＵを決定する（ステップＳ１００９）。なお、スレッドを実行するＣＰＵの決定方法としては、ＯＳ等が有するスケジューラが持つ機能によって決定される。
【００９６】
決定後、ＣＰＵ＃０は、分岐予測情報が読み出せているか否かを判断する（ステップＳ１０１０）。分岐予測情報が読み出せている場合（ステップＳ１０１０：Ｙｅｓ）、ＣＰＵ＃０は、スレッドを実行するＣＰＵの独立分岐予測テーブル３０２に分岐予測情報を書き込む（ステップＳ１０１１）。書き込み後、または分岐予測情報が読み出せていない場合（ステップＳ１０１０：Ｎｏ）、ＣＰＵ＃０は、スレッドを実行するＣＰＵにスレッド実行を要求し（ステップＳ１０１２）、スレッドの起動処理を終了する。
【００９７】
なお、スレッドの起動処理は、ＯＳのスケジューリング機能によって、別のスレッドに切り替わる際の切替後のスレッドに対しても発生する。この場合、ＣＰＵ＃０は、ステップＳ１００１の処理を、「切替後のスレッドのスレッド種別識別子を取得」として実行する。また、スレッドの起動処理は、スレッドに割り当てられたタイムスライスが満了した際に発生したスレッド切替において、切替後のスレッドに対して行ってもよい。また、スレッドの起動処理は、ＩＳＲ（Ｉｎｔｅｒｒｕｐｔ  Ｓｅｒｖｉｃｅ  Ｒｏｕｔｉｎｅ）によって割り込まれた後の、復帰後のスレッドに対して行ってもよい。
【００９８】
図１１は、スレッドの動作終了処理を示すフローチャートである。ＣＰＵ＃０は、スレッドを実行したＣＰＵから動作終了の通知を受け取る（ステップＳ１１０１）。通知を受け取った後、ＣＰＵ＃０は、スレッドが中断されて終了したか否かを判断する（ステップＳ１１０２）。スレッドが中断されずに終了した場合（ステップＳ１１０２：Ｎｏ）、ＣＰＵ＃０は、スレッドを実行したＣＰＵの独立分岐予測テーブル３０２から分岐予測情報を読み出す（ステップＳ１１０３）。読出し後、ＣＰＵ＃０は、終了したスレッドのスレッド種別識別子を取得する（ステップＳ１１０４）。
【００９９】
取得後、ＣＰＵ＃０は、スレッド種別識別子を用いて共有分岐予測テーブル３０４にアクセスする（ステップＳ１１０５）。アクセスの結果、ＣＰＵ＃０は、有効な分岐予測情報が存在するか否かを判断する（ステップＳ１１０６）。有効な分岐予測情報が存在する場合（ステップＳ１１０６：Ｙｅｓ）、ＣＰＵ＃０は、共有分岐予測テーブル３０４の分岐予測情報を独立分岐予測テーブル３０２の分岐予測情報で上書きする（ステップＳ１１０７）。上書き後、有効な分岐予測情報が存在しない場合（ステップＳ１１０６：Ｎｏ）、またはスレッドが中断されて終了した場合（ステップＳ１１０２：Ｙｅｓ）、ＣＰＵ＃０は、スレッドの後始末の処理を実行する（ステップＳ１１０８）。実行後、ＣＰＵ＃０は、スレッドの動作終了処理を終了する。
【０１００】
なお、スレッドの動作終了処理は、ＯＳのスケジューリング機能によって、別のスレッドに切り替わる際の切替前のスレッドに対しても発生する。この場合、ＣＰＵ＃０は、ステップＳ１１０１の処理を、「スレッドを実行するＣＰＵからスレッド切替の通知」として実行し、ステップＳ１１０４の処理を、「切替前のスレッドのスレッド種別識別子を取得」として実行する。さらに、ＣＰＵ＃０は、ステップＳ１１０８の処理を実行しない。
【０１０１】
以上説明したように、マルチコアプロセッサシステム、および分岐予測方法によれば、スレッドごとに分岐予測結果の履歴を持ち、コアがスレッドを実行する度に、対応する履歴をコア内の分岐予測の履歴を記憶するメモリに設定し、スレッドの終了時に回収する。これにより、マルチコアプロセッサシステムは、並列処理の粒度が細かくすぐ終了するスレッドでも履歴を蓄積でき、予測精度を向上できる。
【０１０２】
また、マルチコアプロセッサシステムは、投機実行を行ったスレッドが中断された場合に、投機実行を行ったスレッドが蓄積していた分岐予測の履歴を破棄してもよい。これにより、マルチコアプロセッサシステムは、現在蓄積中の分岐予測結果の履歴の中に、実行不要であったスレッドによる分岐予測の履歴を混合させずに済み、より正確な分岐予測結果の履歴を蓄積することができる。
【０１０３】
また、マルチコアプロセッサシステムは、分岐予測情報を、各ＣＰＵで共有された分岐予測の履歴を記憶するメモリから、各ＣＰＵ内の分岐予測の履歴を記憶するメモリに転送するバスを有していてもよい。これにより、マルチコアプロセッサシステムは、分岐予測情報の転送を、他のデータの転送に阻害されずに行える。
【０１０４】
また、マルチコアプロセッサシステムは、各ＣＰＵで共有された分岐予測の履歴を記憶するメモリ内にスレッドに対応する分岐予測情報が存在しない場合、分岐予測情報が格納されていない領域をクリアし、スレッドに対応する分岐予測情報として読み出してもよい。これにより、マルチコアプロセッサシステムは、空き領域を有効利用することができる。
【０１０５】
また、マルチコアプロセッサシステムは、スレッドの粒度を細かくしても、分岐予測の精度を維持することができる。たとえば、特定のコアが細粒度スレッドを実行し、他のコアでも細粒度スレッドを実行する場合を想定する。従来技術では、他のコアは、特定のコアで実行された細粒度スレッドの分岐予測情報を参照できないため、予測精度が悪くなってしまっていた。実施の形態１では、他のコアは、特定のコアで実行された細粒度スレッドの分岐予測情報を参照でき、予測精度を向上することができる。
【０１０６】
また、マルチコアプロセッサシステムは、共有分岐予測テーブルのサイズが、各コアが有している独立分岐予測テーブルのサイズのＮ倍である場合、従来技術における、コアが保持する分岐予測情報用のメモリをＮ倍にしたことと同じ分岐予測精度を実現できる。共有分岐予測テーブルに使用するメモリは、コアが保持する分岐予測情報用のメモリよりアクセスされる頻度が低いため、低速のメモリを使用することができ、コストを削減することができる。
【０１０７】
（実施の形態２の説明）
図１２は、実施の形態２にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。実施の形態２にかかるマルチコアプロセッサシステム１００は、共有分岐予測テーブル３０４の格納場所が、実施の形態１にマルチコアプロセッサシステム１００のハードウェアと異なる。実施の形態２にかかるマルチコアプロセッサシステム１００は、共有分岐予測テーブル３０４の格納場所以外に関して、実施の形態１にかかるマルチコアプロセッサシステム１００と同一のハードウェアを有し、同一の機能を有するため、説明を省略する。
【０１０８】
実施の形態２にかかるマルチコアプロセッサシステム１００では、共有分岐予測テーブル３０４をメインメモリ３０１に格納する。また、独立分岐予測テーブル３０２は、Ｉ／Ｏ空間にマッピングし、各ＣＰＵからアクセス可能であるとする。また、分岐予測情報バス２１１とバス２１０が独立分岐予測テーブルＩ／Ｆ３０３＃Ｂによって接続されている。たとえば、ＣＰＵ＃０は、独立分岐予測テーブルＩ／Ｆ３０３＃０と独立分岐予測テーブルＩ／Ｆ３０３＃Ｂを経由して共有分岐予測テーブル３０４にアクセスする。
【０１０９】
分岐予測制御ライブラリ４０３は、スレッド起動時にて、メインメモリ３０１上の共有分岐予測テーブル３０４から起動するスレッドの分岐予測情報を読み出す。続けて、分岐予測制御ライブラリ４０３は、Ｉ／Ｏ空間上のスレッドを実行するＣＰＵの独立分岐予測テーブル３０２に共有分岐予測テーブル３０４を書き込む。これにより、実施の形態１にかかるマルチコアプロセッサシステム１００に比べ、ハードウェアの追加コストを削減することができる。また、実施の形態２にかかるマルチコアプロセッサシステム１００は、メインメモリ３０１に空きがある場合、共有分岐予測テーブル３０４を記憶する記憶素子を追加しなくてよい。
【０１１０】
（実施の形態３の説明）
図１３は、実施の形態３にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。実施の形態３にかかるマルチコアプロセッサシステム１００は、共有分岐予測テーブル３０４の格納場所がメインメモリ３０１であり、さらにその一部が共有分岐予測テーブルキャッシュ１３０１として、共有分岐予測レジスタ２１２に格納されている。共有分岐予測テーブルキャッシュ１３０１は、共有分岐予測テーブル３０４と同一のフィールドを有する。実施の形態３にかかるマルチコアプロセッサシステム１００は、共有分岐予測テーブル３０４の格納場所以外に関して、実施の形態１にかかるマルチコアプロセッサシステム１００と同一のハードウェアを有し、同一の機能を有するため、説明を省略する。
【０１１１】
図１４は、実施の形態３にかかるスレッドの起動処理を示すフローチャート（その１）である。なお、実施の形態３にかかるスレッドの起動処理のうち、ステップＳ１４０６〜ステップＳ１４１１は、図１０で示したステップＳ１００３〜ステップＳ１００８と、ステップＳ１４０９：Ｎｏの処理後を除いて等しいため、説明を省略する。
【０１１２】
ＣＰＵ＃０は、起動するスレッドのスレッド種別識別子を取得する（ステップＳ１４０１）。取得後、ＣＰＵ＃０は、スレッド種別識別子を用いて共有分岐予測テーブルキャッシュ１３０１にアクセスする（ステップＳ１４０２）。ＣＰＵ＃０は、アクセスした結果、有効な分岐予測情報が存在するか否か判断する（ステップＳ１４０３）。有効な分岐予測情報が存在する場合（ステップＳ１４０３：Ｙｅｓ）、ＣＰＵ＃０は、共有分岐予測テーブルキャッシュ１３０１から分岐予測情報を読み出す（ステップＳ１４０４）。読み出し後、ＣＰＵ＃０は、ステップＳ１５０３の処理に移行する。
【０１１３】
有効な分岐予測情報がない場合（ステップＳ１４０３：Ｎｏ）、ＣＰＵ＃０は、スレッド種別識別子を用いて、メインメモリ３０１の共有分岐予測テーブル３０４にアクセスする（ステップＳ１４０５）。ステップＳ１４０７、またはステップＳ１４１１の終了後、ＣＰＵ＃０は、ステップＳ１５０１の処理に移行する。また、ステップＳ１４０９：Ｎｏの処理後、ＣＰＵ＃０は、ステップＳ１５０３の処理に移行する。
【０１１４】
図１５は、実施の形態３にかかるスレッドの割り当て開始を示すフローチャート（その２）である。なお、ステップＳ１５０３〜ステップＳ１５０６は、図１０で示したステップＳ１００９〜ステップＳ１０１２と等しいため、説明を省略する。
【０１１５】
ＣＰＵ＃０は、置換アルゴリズムを用いて、共有分岐予測テーブルキャッシュ１３０１の１エントリを選択する（ステップＳ１５０１）。なお、置換アルゴリズムは、たとえば、ＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）、ＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）等を適用してもよい。選択後、ＣＰＵ＃０は、選択したエントリを、メインメモリ３０１の共有分岐予測テーブル３０４に上書きする（ステップＳ１５０２）。
【０１１６】
図１６は、実施の形態３にかかるスレッドの動作終了処理を示すフローチャートである。なお、実施の形態３にかかるスレッドの動作終了処理のうち、ステップＳ１６０１〜ステップＳ１６０４の処理は、図１１で示したステップＳ１１０１〜ステップＳ１１０４と等しいため、説明を省略する。同様に、ステップＳ１６０９〜ステップＳ１６１１の処理は、ステップＳ１１０６〜ステップＳ１１０８と等しいため、説明を省略する。
【０１１７】
ＣＰＵ＃０は、スレッド種別識別子を用いて共有分岐予測テーブルキャッシュ１３０１にアクセスする（ステップＳ１６０５）。アクセス後、ＣＰＵ＃０は、有効な分岐予測情報が存在するか否かを判断する（ステップＳ１６０６）。有効な分岐予測情報が存在する場合（ステップＳ１６０６：Ｙｅｓ）、ＣＰＵ＃０は、共有分岐予測テーブルキャッシュ１３０１の分岐予測情報を独立分岐予測テーブル３０２の分岐予測情報で上書きし（ステップＳ１６０７）、ステップＳ１６１１の処理に移行する。
【０１１８】
有効な分岐予測情報が存在しない場合（ステップＳ１６０６：Ｎｏ）、ＣＰＵ＃０は、スレッド種別識別子を用いてメインメモリ３０１の共有分岐予測テーブル３０４にアクセスする（ステップＳ１６０８）。アクセス後、ＣＰＵ＃０は、ステップＳ１６０９の処理に移行する。
【０１１９】
以上のように、実施の形態３にかかるマルチコアプロセッサシステム１００は、スレッド起動に時間的局所性が存在する場合、スレッド起動、スレッド動作終了にかかる性能上のオーバーヘッドを削減することができる。
【０１２０】
（実施の形態４の説明）
実施の形態１〜実施の形態３にかかるマルチコアプロセッサシステム１００では、現在実行されるスレッド種別に基づいて分岐予測情報を取得していた。実施の形態４にかかるマルチコアプロセッサシステム１００は、過去のスレッドの起動履歴に基づいて分岐予測情報を取得する。
【０１２１】
図１７は、実施の形態４にかかるマルチコアプロセッサシステム１００のハードウェアを示すブロック図である。実施の形態４にかかるマルチコアプロセッサシステム１００では、実施の形態１にかかる共有分岐予測テーブル３０４の代わりに共有分岐予測テーブル１７０１を含む。共有分岐予測テーブル１７０１の詳細については、図１８にて後述する。また、実施の形態４にかかるマルチコアプロセッサシステム１００は、共有分岐予測テーブル３０４以外に関して、実施の形態１にかかるマルチコアプロセッサシステム１００と同一であり、また、読出部３１２を除いて同一の機能を有するため、説明を省略する。
【０１２２】
読出部３１２は、検出部３１１によって検出された第１スレッドと、第１スレッドより前に実行された第２スレッドと、に対応する分岐予測情報を各ＣＰＵで共有された分岐予測の履歴を記憶するメモリから読み出す。
【０１２３】
図１８は、実施の形態４にかかる共有分岐予測テーブル１７０１の記憶内容の一例を示す説明図である。共有分岐予測テーブル１７０１は、共有分岐予測テーブル３０４のスレッド種別識別子の代わりにスレッド起動順序識別子フィールドを含む。共有分岐予測テーブル１７０１における他のフィールドについては、共有分岐予測テーブル３０４の他のフィールドと同一の記憶内容を記憶しているため、説明を省略する。
【０１２４】
スレッド起動順序識別子フィールドは、スレッドの起動される順番でスレッド種別識別子群が格納されている。たとえば、エントリ１８０１のスレッド起動順序識別子フィールドは、今回起動されるスレッド種別識別子がスレッドＡであり、その前にスレッドＢ種別のスレッドが起動され、さらにその前にスレッドＣ種別のスレッドが起動されたことを示している。以下、説明を簡略化するため、各スレッド種別で実行されるスレッドは、それぞれスレッドＡ１、スレッドＢ１、スレッドＣ１、スレッドＤ１であると想定する。同様に、エントリ１８０２のスレッド起動順序識別子フィールドは、今回起動されるスレッドがスレッドＢ１であり、その前にスレッドＢ１が起動され、さらにその前にスレッドＡ１が起動されたということを示している。
【０１２５】
また、エントリ１８０３のスレッド起動順序識別子フィールドは、今回起動されるスレッドがスレッドＣ１であり、その前にスレッドＢ１が起動され、さらにその前にスレッドＡ１が起動されたということを示している。最後に、エントリ１８０４のスレッド起動順序識別子フィールドは、今回起動されるスレッドがスレッドＣ１であり、その前にスレッドＢ１が起動され、さらにその前にスレッドＤ１が起動されたということを示している。
【０１２６】
実施の形態４にかかるマルチコアプロセッサシステム１００は、以上説明したように、共有分岐予測テーブル１７０１にアクセスしてスレッドの起動処理、動作終了処理を実行する。具体的なフローチャートに関しては、図１０、図１１にて示したフローチャートにて、スレッド種別識別子をスレッド起動順序識別子に置き換えることで対応可能であるため、説明を省略する。
【０１２７】
以上説明したように、実施の形態４にかかるマルチコアプロセッサシステムによれば、スレッドの起動順序に基づいて分岐予測情報を設定する。これにより、マルチコアプロセッサシステムは、スレッドの起動順序と個々の分岐の傾向に相関性がある場合、分岐予測精度を向上させることができる。
【０１２８】
なお、本実施の形態１〜実施の形態４で説明した分岐予測方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本分岐予測方法を実行するプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本分岐予測方法を実行するプログラムは、インターネット等のネットワークを介して配布してもよい。
【符号の説明】
【０１２９】
＃０、＃１、＃２  ＣＰＵ
１００  マルチコアプロセッサシステム
２０８  Ｉ／Ｆ
２１０  バス
２１１  分岐予測情報バス
２１２  分岐予測情報レジスタ
３０１  メインメモリ
３０２  独立分岐予測テーブル
３０３  独立分岐予測テーブルＩ／Ｆ
３０４  共有分岐予測テーブル
３０５  メインスレッド
３０６  サブスレッド
３１１  検出部
３１２  読出部
３１３  書込部
３１４  読出部
３１５  書込部
【図１】
2012127589.tif 000003
【図２】
2012127589.tif 000004
【図３】
2012127589.tif 000005
【図４】
2012127589.tif 000006
【図５】
2012127589.tif 000007
【図６】
2012127589.tif 000008
【図７】
2012127589.tif 000009
【図８】
2012127589.tif 000010
【図９】
2012127589.tif 000011
【図１０】
2012127589.tif 000012
【図１１】
2012127589.tif 000013
【図１２】
2012127589.tif 000014
【図１３】
2012127589.tif 000015
【図１４】
2012127589.tif 000016
【図１５】
2012127589.tif 000017
【図１６】
2012127589.tif 000018
【図１７】
2012127589.tif 000019
【図１８】
2012127589.tif 000020
【国際調査報告】
2012127589.tif 000021
2012127589.tif 000022
2012127589.tif 000023
2012127589.tif 000024