(57)【要約】  現在の状態から複数の状態への遷移が可能なデータ処理装置において、遷移する可能性に応じて順位付けられた、遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、データ処理装置の状態毎に作成して保持する。そして、現在の状態から実際に遷移した状態を示す遷移情報をデータ装置から受け取ると、該遷移情報を用いて遷移予測順位リストを更新する。
2009096247.tif 000002
【特許請求の範囲】
【請求項１】
現在の状態から複数の状態への遷移が可能なデータ処理装置の、前記遷移先の状態を予測するための多分岐予測方法であって、
遷移する可能性に応じて順位付けられた、前記遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、前記データ処理装置の前記状態毎に作成し、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ装置から受け取ると、前記遷移情報を用いて前記遷移予測順位リストを更新する多分岐予測方法。
【請求項２】
前記遷移予測順位リストを、前記状態とその一つ以上前の状態の組毎に生成する請求項１記載の多分岐予測方法。
【請求項３】
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、前記遷移予測順位リストにおける該状態の順位を上位へ移動し、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在しない場合、該状態の順位を前記遷移予測順位リストの予め決められた順位に挿入する請求項１または２記載の多分岐予測方法。
【請求項４】
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、
前記遷移予測順位リストにおける該状態の順位を最上位へ移動する請求項１または２記載の多分岐予測方法。
【請求項５】
前記遷移情報を用いて、前記遷移先の候補である状態毎に、同じ状態に再び遷移するまでの遷移数を示す遷移間隔をカウンタで計数し、
前記遷移先の候補である状態毎に、複数の前記遷移間隔を保持することで遷移間隔履歴リストを作成し、
前記カウンタの値と前記遷移間隔履歴リストで保持された値とを比較し、
前記カウンタの値と一致する前記遷移間隔履歴リストで保持された値の数が多いほど対応する前記状態を上位の遷移先の候補とする、前記遷移予測順位リストを作成する請求項１または２記載の多分岐予測方法。
【請求項６】
前記遷移予測順位リストに登録された前記遷移先の状態を実現するための構成情報を、前記データ処理装置が備える、前記構成情報を一時的に保持するための構成情報記憶部に書き込むよう、前記遷移予測順位リストに登録された上位の前記遷移先の状態から順に前記データ処理装置に要求する請求項１から５のいずれか１項記載の多分岐予測方法。
【請求項７】
請求項１または２記載の遷移予測順位リスト、及び請求項５記載の遷移予測順位リストをそれぞれ作成し、
いずれか一方の遷移予測順位リストを選択し、該選択した遷移予測順位リストに用いて前記構成情報記憶部に対する前記構成情報の書き込みを要求する請求項６記載の多分岐予測方法。
【請求項８】
請求項１または２記載の遷移予測順位リスト、及び請求項５記載の遷移予測順位リストをそれぞれ作成し、
作成した遷移予測順位リストを組み合わせた遷移予測順位リストを生成し、該生成した遷移予測順位リストに用いて前記構成情報記憶部に対する前記構成情報の書き込みを要求する請求項６記載の多分岐予測方法。
【請求項９】
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在するか否かにより、前記遷移予測順位リスト毎の当否確率を求め、
前記当否確率を用いて前記遷移先の状態の予測に用いる前記遷移予測順位リストを選択する請求項７または８記載の多分岐予測方法。
【請求項１０】
前記データ処理装置から取得した手掛情報を状態毎に保持し、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ処理装置から受け取ると、前記遷移情報と前記手掛情報とを用いて前記遷移予測順位リストを更新する請求項１乃至９のいずれか１項記載の多分岐予測方法。
【請求項１１】
前記データ処理装置から取得した手掛情報を状態毎に保持し、
遷移予測順位リストの選択作成に使用する請求項７乃至１０のいずれか１項記載の多分岐予測方法。
【請求項１２】
前記データ処理装置から取得した手掛情報に所要の加工処理を実施した後、状態毎に保持する請求項１０または１１記載の多分岐予測方法。
【請求項１３】
現在の状態から複数の状態への遷移が可能なデータ処理装置の、前記遷移先の状態を予測するための多分岐予測装置であって、
遷移する可能性に応じて順位付けられた、前記遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、前記データ処理装置の前記状態毎に保持する予測保持部と、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ装置から受け取ると、前記遷移情報を用いて前記遷移予測順位リストを更新する予測更新部と、
を有する多分岐予測装置。
【請求項１４】
前記予測保持部は、
前記遷移予測順位リストを、前記状態とその一つ以上前の状態の組毎に保持する請求項１３記載の多分岐予測装置。
【請求項１５】
前記予測更新部は、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、前記遷移予測順位リストにおける該状態の順位を上位へ移動し、前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在しない場合、該状態の順位を前記遷移予測順位リストの予め決められた順位に挿入する請求項１３または１４記載の多分岐予測装置。
【請求項１６】
前記予測更新部は、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、前記遷移予測順位リストにおける該状態の順位を最上位へ移動する請求項１３または１４記載の多分岐予測装置。
【請求項１７】
前記予測更新部は、
前記遷移情報を用いて、前記遷移先の候補である状態毎に、同じ状態に再び遷移するまでの遷移数を示す遷移間隔をカウンタで計数し、前記遷移先の候補である状態毎に、複数の前記遷移間隔を保持することで遷移間隔履歴リストを作成し、前記カウンタの値と前記遷移間隔履歴リストで保持された値とを比較し、前記カウンタの値と一致する前記遷移間隔履歴リストで保持された値の数が多いほど対応する前記状態を上位の遷移先の候補とする、前記遷移予測順位リストを作成する履歴保持部を有する請求項１３または１４記載の多分岐予測装置。
【請求項１８】
前記遷移予測順位リストに登録された前記遷移先の状態を実現するための構成情報を、前記データ処理装置が備える、前記構成情報を一時的に保持するための構成情報記憶部に書き込むよう、前記遷移予測順位リストに登録された上位の前記遷移先の状態から順に前記データ処理装置に要求する選択部を有する請求項１３から１７のいずれか１項記載の多分岐予測装置。
【請求項１９】
請求項１３または１４記載の予測保持部と、
請求項１７記載の予測保持部と、
を有し、
前記選択部は、
いずれか一方の予測保持部で作成した遷移予測順位リストを選択し、該選択した遷移予測順位リストに用いて前記構成情報記憶部に対する前記構成情報の書き込みを要求する請求項１８記載の多分岐予測装置。
【請求項２０】
請求項１３または１４記載の予測保持部と、
請求項１７記載の予測保持部と、
を有し、
前記選択部は、
前記予測保持部で作成した遷移予測順位リストを組み合わせた遷移予測順位リストを生成し、該生成した遷移予測順位リストに用いて前記構成情報記憶部に対する前記構成情報の書き込みを要求する請求項１８記載の多分岐予測装置。
【請求項２１】
前記選択部は、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在するか否かにより、前記遷移予測順位リスト毎の当否確率を求め、前記当否確率を用いて前記遷移先の状態の予測に用いる前記遷移予測順位リストを選択する請求項１９または２０記載の多分岐予測装置。
【請求項２２】
前記データ処理装置から取得した手掛情報を状態毎に保持する手掛保持部を有し、
前記予測更新部は、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ処理装置から受け取ると、前記遷移情報と前記手掛情報とを用いて前記遷移予測順位リストを更新する請求項１３乃至２１のいずれか１項記載の多分岐予測装置。
【請求項２３】
前記データ装置から取得した手掛情報を状態毎に保持する手掛保持部を有し、
前記選択部は、
遷移予測順位リストの選択作成に使用する請求項１９乃至２２のいずれか１項記載の多分岐予測装置。
【請求項２４】
前記手掛保持部は、
前記データ装置から取得した手掛情報に所要の加工処理を実施した後、状態毎に保持する請求項２２または２３記載の多分岐予測装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、現在の状態から多方向に分岐する遷移先の状態を予測するための多分岐予測方法及び装置に関し、特に再構成可能デバイスから成るデータ処理装置に好適な多分岐予測方法及び装置に関する。
【背景技術】
【０００２】
ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processor  Unit）を用いるデータ処理装置は、複数の命令によって記述されたオブジェクトコード及び処理対象となるデータが格納されるメモリを備え、ＣＰＵやＭＰＵによりメモリに格納された命令やデータを順次読出して各種の処理を実行する。【０００３】
このとき、ＣＰＵやＭＰＵは、各命令を、メモリからの命令の取得、取得した命令の解読、データの準備、命令の実行、実行結果のメモリへの書き戻し等の複数の段階に分割して実行する。近年のＣＰＵやＭＰＵは、これら各段階の処理を独立して動作させることにより、先の命令の処理が終了する前に次の命令の処理を開始する、いわゆるパイプライン動作により処理速度を向上させている。【０００４】
ＣＰＵやＭＰＵがパイプライン動作で命令を実行する場合、取得した命令を解読して分岐命令であることが判明すると、該分岐命令の後続の命令については、既に開始していた解読等の処理を中断し、それまでの処理結果を破棄し、分岐先の命令を取得して解読からやり直す必要がある（分岐のペナルティ）。【０００５】
そこで、命令列が遷移する方向を予測し、予測した命令をパイプライン動作で処理すれば、予測が的中したときには分岐のペナルティ無しに命令列を実行できる。なお、近年のＣＰＵやＭＰＵで用いる分岐命令は、ある特定のアドレスに移行するか該分岐命令の後続の命令に移行する、２分岐を指示する命令がほとんどである。【０００６】
ところで、複数の命令を並列に処理することが可能な複数の論理回路を備え、該論理回路の構成をソフトウェアによって変更できるデータ処理装置として、コンフィギュアラブルプロセッサ（再構成デバイス）がある。コンフィギュアラブルプロセッサは、ＦＰＧＡ（Field  Programmable  Gate  Array）とリコンフィギュアラブルプロセッサとに大別される。【０００７】
リコンフィギャラブルプロセッサとしては、ＤＲＰ（Dynamic  Reconfigurable  Processor）が知られている。ＤＲＰについては、例えば特許文献１〜６にその詳細が記載されている。【０００８】
ＤＲＰは、演算を実行する演算部と、演算部の動作を制御する制御部とを備えている。演算部は、小規模な複数の演算器とそれらの接続を切り替える相互接続部とを備え、各演算器及び相互接続部に対する命令コードを書き換え、該命令コードにしたがって各演算器の接続を切り換えることで所望の機能を実現する回路を構成できる。【０００９】
ＤＲＰでは、限られた記憶容量のメモリ（構成情報記憶部）により、複数の処理（状態）で必要な演算器やその接続を示す、各状態を実現するための構成情報を一時的に保持しておき、該構成情報を必要に応じて書き換えることで、より多くの状態への遷移を可能にしている。そのための処理方法については、例えば特許文献７〜９に記載されている。【００１０】
近年のＣＰＵやＭＰＵには、分岐による遷移先を予測する方法が周知の技術として既に組み込まれているが、上述したように、そのほとんどの分岐命令は２分岐を指示する命令である。【００１１】
それに対して、上述した再構成デバイスでは、多分岐を扱うことが可能である。多分岐による遷移先の予測方法は、例えば非特許文献１等で提案されている。この背景技術には、４分岐を扱うデータ処理装置において、最も遷移する確率が高い状態を遷移先として予測する方法が記載されている。【００１２】
再構成デバイスでは、上述したように構成情報記憶部で複数の状態に対応する構成情報を一時的に保持しておき、該構成情報にしたがって各演算器の接続を切り換えることで所望の機能を実現する。この構成情報記憶部の記憶容量は限られているため、全ての状態の構成情報を保持しておくことはできず、遷移先の状態の構成情報が無ければ、該構成情報を構成情報記憶部に書き込む必要がある。【００１３】
したがって、多分岐による遷移先の状態を正確に予測し、予測した遷移先の構成情報を構成情報記憶部に事前に格納しておけば、構成情報記憶部に対する構成情報の書き込みを待つ必要が無くなるため、データ処理装置の処理性能（スループット）が向上する。【００１４】
しかしながら、上述したように、背景技術の遷移先の予測方法では、予測する遷移先が１つであり、予測が外れる可能性が高い。そのため、構成情報記憶部に対する構成情報の書き込みが頻繁に発生し、構成情報の書き込みを待つことによる待機時間が長くなるため、データ処理装置のスループットが低下してしまう。
【先行技術文献】
【００１５】
【特許文献１】特開２０００−１３８５７９号公報
【特許文献２】特開２０００−２２４０２５号公報
【特許文献３】特開２０００−２３２３５４号公報
【特許文献４】特開２０００−２３２１６２号公報
【特許文献５】特開２００３−０７６６６８号公報
【特許文献６】特開２００３−０９９４０９号公報
【特許文献７】特開２００５−２２２１４１号公報
【特許文献８】特開２００５−２２２１４２号公報
【特許文献９】特開２００７−１７９３５８号公報
【非特許文献１】Kishore  N.  Menezes  Sumedh  W.  Sathaye  Thomas  M.  Conteが"Path  Prediction  for  High  Issue-Rate  Processors",  IEEE  PACT,  pp.  178-188,  1997.
【発明の概要】
【００１６】
そこで、本発明は、構成情報記憶部に対する構成情報の書き込みを待つことによる待機時間を低減してデータ処理装置の処理性能を向上できる多分岐予測方法及び装置を提供することを目的とする。
【００１７】
上記目的を達成するため本発明の多分岐予測方法は、現在の状態から複数の状態への遷移が可能なデータ処理装置の、前記遷移先の状態を予測するための多分岐予測方法であって、
遷移する可能性に応じて順位付けられた、前記遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、前記データ処理装置の前記状態毎に作成し、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ装置から受け取ると、前記遷移情報を用いて前記遷移予測順位リストを更新する方法である。
【００１８】
一方、本発明の多分岐予測装置は、現在の状態から複数の状態への遷移が可能なデータ処理装置の、前記遷移先の状態を予測するための多分岐予測装置であって、
遷移する可能性に応じて順位付けられた、前記遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、前記データ処理装置の前記状態毎に保持する予測保持部と、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ装置から受け取ると、前記遷移情報を用いて前記遷移予測順位リストを更新する予測更新部と、
を有する。
【図面の簡単な説明】
【００１９】
【図１】図１は、第１の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図２】図２は、第２の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図３】図３は、第３の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図４】図４は、第４の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図５】図５は、第５の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図６】図６は、第６の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図７】図７は、第７の実施の形態の多分岐予測装置の構成を示すブロック図である。
【図８】図８は、第１実施例の多分岐予測装置の構成を示すブロック図である。
【図９】図９は、遷移予測順位リストの更新処理の実現例を示す回路図である。
【図１０】図１０は、データ処理装置による処理対象の一例を示す状態遷移図である。
【図１１】図１１は、状態３に対応する遷移予測順位リストの一例を示す模式図である。
【図１２】図１２は、第２実施例の多分岐予測装置の構成を示すブロック図である。
【図１３Ａ】図１３Ａは、第２実施例の予測更新部が備えるカウンタ及び遷移間隔履歴リストの一例を示す模式図である。
【図１３Ｂ】図１３Ｂは、図１３Ａに示したカウンタ及び遷移間隔履歴リストを更新する様子を示す模式図である。
【図１３Ｃ】図１３Ｃは、図１３Ｂに示した更新処理による、更新後のカウンタ及び遷移間隔履歴リストの一例を示す模式図である。
【図１３Ｄ】図１３Ｄは、図１３Ｃに示したカウンタ及び遷移間隔履歴リストを用いた遷移予測順位リストの更新方法の一例を示す模式図である。
【図１４】図１４は、データ処理装置の状態の遷移に対してカウンタ及び遷移間隔履歴リストが変化している様子を示す模式図である。
【図１５】図１５は、第２実施例の予測更新部が備えるカウンタ及び遷移間隔履歴リストの他の例を示す模式図である。
【図１６】図１６は、第３実施例の多分岐予測装置の構成を示すブロック図である。
【図１７】図１７は、図１６に示した予測部が備える手掛保持部の一例を示す模式図である。
【発明を実施するための形態】
【００２０】
次に本発明について図面を用いて説明する。
（第１の実施の形態）
図１は第１の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００２１】
図１に示すように、第１の実施の形態の多分岐予測装置は、予測保持部１１、予測更新部１２及び選択部２を備えている。
【００２２】
予測保持部１１は、状態毎に、該状態からの遷移先候補の状態を示す複数の状態番号を遷移予測順位リストとして保持する。各遷移予測順位リストには、予め決められた数の遷移先候補の状態番号が、次に遷移する可能性が最も高い最上位の遷移先候補から最も低い最下位の遷移先候補まで順に登録される。
【００２３】
予測保持部１１は、データ処理装置から現在の状態を示す情報（現状態情報）を受け取ると、該状態に対応する遷移予測順位リストを選択部２及び予測更新部１２に通知する。
【００２４】
選択部２は、遷移予測順位リストに登録された遷移先候補のうち、順位が高く、かつ構成情報が構成情報記憶部で保持されていない遷移先候補の状態を選択し、該状態の状態番号を出力する。
【００２５】
選択部２は、予測保持部１１から遷移予測順位リストを受け取ると、該遷移予測順位リスト内の上位の遷移先候補の状態から順に、該状態番号に対応する構成情報が構成情報記憶部で保持されているか否かを判定する。構成情報の有無については、データ処理装置から通知される在非情報を用いる。
【００２６】
選択部２は、構成情報記憶部に遷移先候補の構成情報が有る場合、構成情報記憶部に構成情報を書き込む必要が無いため、次の順位の遷移先候補に対する判定処理へ移行する。構成情報記憶部に遷移先候補の構成情報が無い場合は、その構成情報を構成情報記憶部に書き込むようデータ処理装置に要求する。
【００２７】
予測更新部１２は、データ処理装置から通知される実際の状態遷移に基づいて遷移予測順位リストを更新する。予測更新部１２には、予測保持部１１から現在の状態に対応する遷移予測順位リストが通知されると共に、データ処理装置が現在の状態から次に実際に遷移した状態の状態番号が遷移情報として通知される。
【００２８】
予測更新部１２は、遷移情報で通知された状態番号が遷移予測順位リストに有る（予測が当たった）場合は、その状態（遷移先候補）の順位を一つ上位の遷移先候補と入れ替える。但し、その状態が既に最上位である場合は入れ替えを行わない。
【００２９】
遷移情報で通知された状態番号が遷移予測順位リストに無い（予測が外れた）場合は、遷移予測順位リストの予め決められた順位にその状態の状態番号を挿入し、それ以下の遷移先候補の順位を一つずつ下げる。その場合、最下位の遷移先候補は遷移予測順位リストから削除される。予測更新部１２は、このようにして更新した遷移予測順位リストを、予測保持部１１で保持している、対応する状態の遷移予測順位リストと置き換える。
【００３０】
本実施形態の多分岐予測装置は、以上の処理をデータ処理装置の状態毎に繰り返し実行する。
【００３１】
なお、遷移予測順位リストの更新処理は、上述した方法に限定されるものではない。例えば、通知された現在の状態番号が遷移予測順位リストに有る場合、その状態（遷移先候補）の順位を一つ上位の遷移先候補と入れ替えるだけでなく、二つあるいは三つ上位の遷移先候補と入れ替えてもよい。
【００３２】
また、通知された現在の状態番号が遷移予測順位リストにない場合、その状態（遷移先候補）を遷移予測順位リストの予め決められた順位に挿入するだけでなく、最下位の遷移先候補とする方法、あるいは最上位の遷移先候補とする方法（ＬＲＵ（Least  Recently  Used）とも呼ばれる）もある。
【００３３】
また、図１に示す選択部２、予測保持部１１及び予測更新部１２は、それぞれ独立して備える必要はない。例えば、任意の構成要素が他の構成要素に含まれていてもよく、複数の構成要素が一体となった構成でもよい。例えば、予測保持部１１と予測更新部１２とが一体の構成であってもよい。
【００３４】
また、図１に示す選択部２、予測保持部１１及び予測更新部１２は、その全てを１つの装置内に備える必要はない。例えば、選択部２を他の装置に含む構成や他の装置が備えるＭＰＵ等で実現してもよい。
【００３５】
さらに、図１に示す選択部２、予測保持部１１及び予測更新部１２は、プログラムにしたがって動作するＣＰＵやＭＰＵで実現することも可能である。
【００３６】
以上の各構成要素に対する要件は、第１の実施の形態だけでなく、以下に記載する第２の実施の形態〜第７の実施の形態にも適用できる。
【００３７】
本実施形態によれば、遷移予測順位リストに基づいて各状態の遷移先候補の構成情報を構成情報記憶部で保持することで、構成情報記憶部に遷移先の状態の構成情報が存在する確率が上昇する。したがって、構成情報記憶部に対する構成情報の書き込みを待つことによる待機時間が低減するため、データ処理装置の処理性能（スループット）が向上する。
（第２の実施の形態）
図２は第２の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００３８】
図２に示すように、第２の実施の形態の多分岐予測装置は、予測保持部１３、予測更新部１２及び選択部２を備えている。
【００３９】
第２の実施の形態の多分岐予測装置は、予測保持部１３が、ある状態とその前の状態の組毎に遷移予測順位リストを備える点で第１の実施の形態と異なっている。
【００４０】
予測保持部１３は、データ処理装置から通知された状態とその前の状態の組毎に、次に遷移する遷移先候補の状態を示す複数の状態番号を遷移予測順位リストとして保持する。各遷移予測順位リストには、予め決められた数の遷移先候補の状態番号が、次に遷移する可能性が最も高い最上位の遷移先候補から最も低い最下位の遷移先候補まで順に登録される。
【００４１】
予測保持部１３は、データ処理装置から現在の状態を示す情報（現状態情報）を受け取ると、該状態に対応する遷移予測順位リストを選択部２及び予測更新部１２に通知する。
【００４２】
選択部２は、遷移予測順位リストに登録された遷移先候補のうち、順位が高く、かつ構成情報が構成情報記憶部で保持されていない遷移先候補の状態を選択し、該状態の状態番号を出力する。
【００４３】
選択部２は、予測保持部１３から遷移予測順位リストを受け取ると、該遷移予測順位リスト内の上位の遷移先候補から順に、その状態番号に対応する構成情報が構成情報記憶部で保持されているか否かを判定する。構成情報の有無については、データ処理装置から通知される在非情報を用いる。
【００４４】
選択部２は、構成情報記憶部に遷移先候補の構成情報が有る場合、構成情報記憶部に構成情報を書き込む必要が無いため、次の順位の遷移先候補に対する判定処理へ移行する。構成情報記憶部に遷移先候補の構成情報が無い場合は、その構成情報を構成情報記憶部に書き込むようデータ処理装置に要求する。
【００４５】
予測更新部１２は、データ処理装置から通知される実際の状態遷移に基づいて遷移予測順位リストを更新する。予測更新部１２には、予測保持部１３から現在の状態とその前の状態の組に対応する遷移予測順位リストが通知されると共に、データ処理装置が現在の状態から次に実際に遷移した状態の状態番号が遷移情報として通知される。
【００４６】
予測更新部１２は、遷移情報で通知された状態番号が遷移予測順位リストに有る（予測が当たった）場合は、その状態（遷移先候補）の順位を一つ上位の遷移先候補と入れ替える。但し、その状態が既に最上位である場合は入れ替えを行わない。
【００４７】
遷移情報で通知された状態番号が遷移予測順位リストに無い（予測が外れた）場合は、遷移予測順位リストの予め決められた順位にその状態の状態番号を挿入し、それ以下の遷移先候補の順位を一つずつ下げる。その場合、最下位の遷移先候補は遷移予測順位リストから削除される。予測更新部１２は、このようにして更新した遷移予測順位リストを、予測保持部１１で保持している、対応する状態の組の遷移予測順位リストと置き換える。
【００４８】
本実施形態の多分岐予測装置は、以上の処理をデータ処理装置の状態毎に繰り返し実行する。
【００４９】
なお、上記説明では、現在の状態とその前の状態の組毎に遷移予測順位リストを生成する例を示したが、現在の状態とその前の状態の数、すなわち各組の履歴数は多分岐予測装置の演算資源が足りる範囲内であれば増やしてもよい。但し、各組の履歴数を増やすと処理速度が遅くなるため、本発明の効果が低減する。
【００５０】
本実施形態によれば、遷移予測順位リストに基づいて現在の状態とその前の状態の組に対応する遷移先候補の構成情報を構成情報記憶部に保持させることで、以前の状態によって現在の状態からの遷移先が異なる場合でも、より適切な遷移先候補を選択できる。そのため、構成情報記憶部に遷移先の状態の構成情報が存在する確率が上昇する。したがって、構成情報記憶部に対する構成情報の書き換えを待つことによる待機時間が低減して、データ処理装置の処理性能（スループット）が向上する。
（第３の実施の形態）
図３は第３の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００５１】
図３に示すように、第３の実施の形態の多分岐予測装置は、予測保持部１１、予測更新部１２及び選択部２を備えている。
【００５２】
第３の実施の形態の多分岐予測装置は、予測更新部１２による遷移予測順位リストの更新方法が第１の実施の形態と異なっている。
【００５３】
予測保持部１１は、状態毎に、該状態からの遷移先候補の状態を示す複数の状態番号を遷移予測順位リストとして保持する。各遷移予測順位リストには、予め決められた数の遷移先候補の状態番号が、次に遷移する可能性が最も高い最上位の遷移先候補から最も低い最下位の遷移先候補まで順に登録される。予測保持部１１は、データ処理装置から現在の状態を示す情報（現状態情報）を受け取ると、該状態に対応する遷移予測順位リストを選択部２に通知する。
【００５４】
選択部２は、遷移予測順位リストに登録された遷移先候補のうち、順位が高く、かつ構成情報が構成情報記憶部で保持されていない遷移先候補の状態を選択し、該状態の状態番号を出力する。
【００５５】
選択部２は、予測保持部１１から遷移予測順位リストが通知されると、該遷移予測順位リスト内の上位の遷移先候補の状態から順に、該状態番号に対応する構成情報が構成情報記憶部で保持されているか否かを判定する。構成情報の有無については、データ処理装置から通知される在非情報を用いる。
【００５６】
選択部２は、構成情報記憶部に遷移先候補の構成情報が有る場合、構成情報記憶部に構成情報を書き込む必要が無いため、次の順位の遷移先候補に対する判定処理に移行する。構成情報記憶部に遷移先候補の構成情報が無い場合は、その構成情報を構成情報記憶部に書き込むようデータ処理装置に要求する。
【００５７】
予測更新部１２は、データ処理装置から通知される実際の状態遷移に基づいて遷移予測順位リストを更新する。さらに、本実施形態の予測更新部１２は、状態毎に、各遷移先候補の遷移間隔（同じ遷移先候補の状態に再び遷移するまでの遷移数）を保持する履歴保持部１４を備えている。履歴保持部１４は、遷移先候補の状態毎に遷移間隔を計数するカウンタと、遷移先候補の状態毎に、該カウンタの計数結果（遷移間隔）を複数保持する遷移間隔履歴リストとを備えている。
【００５８】
本実施形態の予測更新部１２は、履歴保持部１４が備える、カウンタで計数した遷移間隔の値に対して、遷移間隔履歴リストで保持している遷移間隔の一致数が多いほど、対応する遷移先候補を上位とする、遷移予測順位リストを予測保持部１１に通知する。
【００５９】
本実施形態の多分岐予測装置は、以上の処理をデータ処理装置の状態毎に繰り返し実行する。
【００６０】
なお、本実施形態では、カウンタで計数した遷移間隔の値に対して、遷移間隔履歴リストで保持している遷移間隔の一致数が多いほど、対応する遷移先候補を上位とする例を示したが、遷移予測順位リスト内で上位とする遷移先候補はこれに限定するものではない。例えば任意の遷移先候補で２種類の遷移間隔が交互に発生している場合は、２つ前や４つ前に実際に遷移した状態を遷移先候補として上位にすることも考えられる。
【００６１】
本実施形態によれば、遷移間隔履歴リストに基づいて遷移予測順位リストを更新するため、処理対象であるオブジェクトコードの特性に応じて遷移先候補を選択できる。そのため、予測の精度がより向上して構成情報記憶部に遷移先の状態の構成情報が存在する確率が上昇する。したがって、構成情報記憶部に対する構成情報の書き換えを待つことによる待機時間が低減するため、データ処理装置の処理性能（スループット）が向上する。
（第４の実施の形態）
図４は第４の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００６２】
図４に示すように、第４の実施の形態の多分岐予測装置は、２組の予測保持部１１（図４では１１１、１１２）及び予測更新部１２（図４では１２１、１２２）を備え、それら２組の予測保持部１１及び予測更新部１２が１つの選択部２を共有する構成である。なお、予測保持部１１及び予測更新部１２は、２組に限定されるものではなく、何組であってもよい。
【００６３】
本実施形態の多分岐予測装置が備える選択部２は、各予測保持部１１による予測結果の当否を判定し、該判定結果を蓄積して実際の状態遷移に対する予測結果の当否確率を求め、どの予測保持部１１で保持している遷移予測順位リストを用いるかを判定する。すなわち、より高い確率で予測が正解する予測保持部１１の遷移予測順位リストを用いて、構成情報記憶部に対する構成情報の書き込みをデータ処理装置に要求する。
【００６４】
予測保持部１１及び予測更新部１２のその他の構成及び動作は、上述した第１の実施の形態から第３の実施の形態で示した多分岐予測装置と同様であるため、その説明は省略する。
【００６５】
本実施形態によれば、複数の予測方法の利点を併せ持つことができるため、構成情報記憶部に遷移先の状態の構成情報が存在する確率がより上昇する。したがって、構成情報記憶部に対する構成情報の書き換えを待つことによる待機時間がより低減するため、データ処理装置の処理性能（スループット）が向上する。
（第５の実施の形態）
図５は第５の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００６６】
図５に示すように、第５の実施の形態の多分岐予測装置は、図１に示した第１の実施の形態の多分岐予測装置に手掛保持部１５を追加した構成である。
【００６７】
手掛保持部１５は、予測保持部１１や予測更新部１２で取り扱わない、現状態情報や遷移情報以外にデータ処理装置から動的に取得できる情報を各状態に対応して保持する。これらの情報は、予測保持部１１や予測更新部１２による予測の手掛りとして利用するものである。手掛保持部１５は、データ処理装置から取得した情報に所要の加工処理を実施した後、保持してもよい。
【００６８】
本実施形態の多分岐予測装置が備える予測更新部１２は、データ処理装置から通知される実際の状態遷移に加えて、手掛保持部１５で保持している状態毎の情報（手掛情報）を用いて遷移予測順位リストを更新する。
【００６９】
予測保持部１１及び予測更新部１２のその他の構成及び動作は、上述した第１の実施の形態から第３の実施の形態で示した多分岐予測装置と同様であるため、その説明は省略する。
（第６の実施の形態）
図６は第６の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００７０】
図６に示すように、第６の実施の形態の多分岐予測装置は、図４に示した第４の実施の形態の多分岐予測装置に手掛保持部１５を追加した構成である。
【００７１】
手掛保持部１５は、予測保持部１１や予測更新部１２で取り扱わない、現状態情報や遷移情報以外にデータ処理装置から動的に取得できる情報を各状態に対応して保持する。これらの情報は、予測保持部１１や予測更新部１２による予測の手掛りとして利用するものである。手掛保持部１５は、データ処理装置から取得した情報に所要の加工処理を実施した後、保持してもよい。
【００７２】
本実施形態の多分岐予測装置が備える選択部２は、各予測保持部１１による予測結果の当否確率に基づき、どの予測保持部１１で保持している遷移予測順位リストを用いるかを判定すると共に、手掛保持部１５で保持している状態毎の情報（手掛情報）を用いて、構成情報記憶部に対する構成情報の書き込みをデータ処理装置に要求する。
【００７３】
予測保持部１１及び予測更新部１２のその他の構成及び動作は、上述した第１の実施の形態から第３の実施の形態で示した多分岐予測装置と同様であるため、その説明は省略する。
（第７の実施の形態）
図７は第７の実施の形態の多分岐予測装置の構成を示すブロック図である。
【００７４】
図７に示すように、第７の実施の形態の多分岐予測装置は、第５の実施の形態で示した予測保持部１１、予測更新部１２及び手掛保持部１５を備える予測部を複数台備える構成である。なお、手掛保持部１５は、予測部毎に備える必要はなく、多分岐予測装置内に１台だけ備える構成であってもよい。図７は、各予測部及び選択部２で１台の手掛保持部１５を共通に利用する構成例を示している。
【００７５】
また、本実施形態の多分岐予測装置は、全ての予測部に手掛保持部１５を備える構成である必要はなく、第１の実施の形態〜第３の実施の形態で示した手掛保持部１５を持たない予測部を含んでいてもよい。
【００７６】
さらに、手掛保持部１５から選択部２及び各予測更新部１２に供給する手掛情報は同一であってもよく、異なっていてもよい。
【００７７】
本実施形態の多分岐予測装置が備える選択部２は、各予測保持部１１による予測結果の当否確率に基づき、どの予測保持部１１で保持している遷移予測順位リストを用いるかを判定すると共に、手掛保持部１５で保持している状態毎の情報（手掛情報）を用いて、構成情報記憶部に対する構成情報の書き込みをデータ処理装置に要求する。
【００７８】
また、本実施形態の多分岐予測装置が備える予測更新部１２は、データ処理装置から通知される実際の状態遷移に加えて、手掛保持部１５で保持している状態毎の情報（手掛情報）を用いて遷移予測順位リストを更新する。
【００７９】
予測保持部１１及び予測更新部１２のその他の構成及び動作は、上述した第１の実施の形態から第３の実施の形態で示した多分岐予測装置と同様であるため、その説明は省略する。
【００８０】
次に本発明の実施例について図面を用いて説明する。
【００８１】
（第１実施例）
第１実施例は、データ処理装置として上記特許文献１に記載されたＤＲＰを用い、該ＤＲＰに第１の実施の形態で示した多分岐予測装置を備える例である。
【００８２】
図８は第１実施例の多分岐予測装置の構成を示すブロック図である。
【００８３】
図８に示すように、本実施例のデータ処理装置（ＤＲＰ）は、演算部４、制御部３及び予測部２を有する。
【００８４】
演算部４は、演算を実行するアレイ状に配置された複数のプロセッサエレメント（ＰＥ）４１と、制御部３よりも少数の状態を管理する補助制御部４２とを有する。
【００８５】
プロセッサエレメント４１は、レジスタファイル（ＲＦＵ）、ＡＬＵ、データ処理演算器（ＤＭＵ）及び命令メモリを備え、上記構成情報にしたがって他のプロセッサエレメント４１と接続される。上記構成情報記憶部は、例えば命令メモリに備えている。
【００８６】
制御部３は、状態管理部３１、構成番号変換部３２及び構成書換部３５を備えた、上記ＤＲＰの状態遷移管理部（ＳＴＣ）に相当する。
【００８７】
予測部１は、本発明の多分岐予測装置に相当し、予測保持部１１、選択部２及び予測更新部１２を有する。
【００８８】
予測保持部１１は、状態毎に、例えば上位３つの遷移先候補の状態の状態番号を保持できるメモリを有する。
【００８９】
選択部２は、構成書換部３５に対して構成情報記憶部に対する構成情報の書き込みを要求（構成要求）すると共に、構成書換部３５から該構成要求を受理したか否かを示す回答を受け取る。
【００９０】
図８に示すデータ処理装置の起動時、予測保持部１１は、状態管理部３１で保持している構成情報を受け取り、仮の遷移予測順位リストとして保持する。
【００９１】
予測保持部１１は、制御部３及び演算部４が動作を開始し、制御部３から現在の状態を示す現状態情報を受け取ると、該状態に対応する遷移予測順位リストを選択部２及び予測更新部１２に送信する。
【００９２】
選択部２は、制御部３から通知される、構成情報記憶部で保持している構成情報に対応する状態を示す情報（在非情報）を受けとり、該在非情報を用いて予測保持部１１から受け取った遷移予測順位リストから構成情報記憶部で保持された構成情報に対応する状態（遷移先候補）を削除する。そして、遷移予測順位リストに残った遷移先候補のうち、最上位の遷移先候補に対応する構成情報を構成情報記憶部に書き込むよう構成書換部３５に要求（構成要求）する。
【００９３】
構成書換部３５は、構成情報記憶部に対する構成情報の書き換え処理を行っている場合は、その書き換え処理を優先して実行する。構成書換部３５は、構成情報記憶部に対する構成情報の書き換え処理を行っていないとき、予測部１から発行される構成要求を受理する。但し、構成書換部３５に対して演算部４からの遷移要求、または構成番号変換部３２からの書き換え要求が発行されている場合は、そちらの処理を優先して実行する。
【００９４】
構成書換部３５は、予測部１からの構成要求を受け付けることができない場合、その旨を予測部１に回答する。構成書換部３５に対して予測部１からの構成要求のみが発行されている場合、構成書換部３５は予測部１から発行された構成要求を受理し、構成要求を受理した旨を示す回答を予測部１に返信する。
【００９５】
選択部２は、構成要求を送信すると、該構成要求に対する回答を受信するまで待機し、構成要求を受理した旨を示す回答を受信すると、遷移予測順位リストに残った遷移先候補のうち、構成要求が受理された最上位の遷移先候補を削除する。そして、最上位の遷移先候補を削除することで最上位に繰り上がった遷移先候補に対応する構成情報を構成情報記憶部に書き込むよう構成書換部３５に要求する。
【００９６】
選択部２は、以降、構成書換部３５により構成要求が受理されなくなるか、遷移予測順位リスト内の遷移先候補が無くなるまで同様の処理を繰り返す。
【００９７】
選択部２は、遷移予測順位リスト内の遷移先候補が無くなると、データ処理装置で状態遷移が発生するまで何も処理を実行しない。また、構成書換部３５から構成要求を受理できない旨の回答を受信した場合は、当該遷移予測順位リストを廃棄し、次に状態遷移が発生するまで何も処理を実行しない。
【００９８】
予測更新部１２は、遷移予測順位リストを予測保持部１１から受け取ると、データ処理装置で状態遷移が発生するまで待機する。状態遷移が発生し、その遷移先を示す遷移情報が制御部３から通知されると、遷移予測順位リストと通知された遷移情報に基づいて新しい遷移予測順位リストを作成する。
【００９９】
予測更新部１２は、遷移予測順位リストに登録された状態（遷移先候補）への遷移が発生した場合、その状態（遷移先候補）の順位を一つ上位の遷移先候補と入れ替える。
【０１００】
また、予測更新部１２は、遷移予測順位リストに登録されていない状態（遷移先候補）への遷移が発生した場合、その状態を第２位の遷移先候補とし、第２位であった遷移先候補を第３位に下げ、第３位であった遷移先候補を遷移予測順位リストから削除する。新しい遷移予測順位リストは、予測保持部１１が保持している対応する状態の遷移予測順位リストと入れ替える。
【０１０１】
上記予測更新部１２による遷移予測順位リストの更新処理は、例えば図９に示すような論理回路（ハードワイヤード回路）で実現できる。なお、予測更新部１２は、論理回路で実現する構成に限定されるものではなく、例えばプログラマブルアレイ回路で実現してもよく、プログラムにしたがって動作するＣＰＵやＭＰＵで実現してもよい。
【０１０２】
以下、図１０に示す状態遷移を実現するオブジェクトコードにしたがってデータ処理装置（ＤＲＰ）が動作する場合を例にして、本実施例の多分岐予測装置の動作について説明する。
【０１０３】
図１０に示す状態遷移は、画像データ等を転送するパケット処理を想定したものであり、三重のループ内に複数の主処理を備えている。主処理のうち、状態４を経由するパスは初期化時に実行する処理であり、状態１０を経由するパスは通常動作時に実行する処理であり、状態８を経由するパスは障害発生時に実行する処理である。
【０１０４】
ここでは、データ処理装置（ＤＲＰ）が備える命令メモリ内の構成情報記憶部は８つの構成情報を保持できるものとし、状態３，５，７，１０，１２，１３，１４，１５の構成情報が構成情報記憶部で保持されているものとする。これらの状態は、補助制御部４２によって遷移が制御される、ＤＲＰ内で長期間滞留する状態である。また、ここでは、データ処理装置（ＤＲＰ）が状態１→２→３→４→９→１２→１５→３→７→１０→１４→１５→３→５→１０→１３→１５→３の順に遷移し、現在、状態３であるとする。
【０１０５】
データ処理装置（ＤＲＰ）が状態３に遷移したことが制御部３から予測部１に通知されると、予測保持部１１は状態３に対応する遷移予測順位リストを選択部２及び予測更新部１２に送信する。遷移予測順位リストには、状態５が最上位（第１位）の遷移先候補として登録され、状態７が第２位の遷移先候補として登録され、状態４が第３位の遷移先候補として登録されているものとする。以下、このような遷移予測順位リストを（５−７−４）と表す。
【０１０６】
選択部２には、命令メモリの構成情報記憶部で保持された構成情報を示す在非情報が制御部３及び予測保持部１１を介して通知される。
【０１０７】
選択部２は、予測保持部１１から遷移予測順位リスト（５−７−４）を受け取ると、遷移予測順位リストの上位の遷移先候補から順に、その状態の構成情報が命令メモリの構成情報記憶部で保持されているか否かを判定する。
【０１０８】
ここでは、上述したように遷移予測順位リストの第１位の状態５及び第２位の状態７の構成情報が構成情報記憶部で保持されているため、選択部２は第３位の状態４の構成情報を命令メモリの構成情報記憶部に書き込むよう構成書換部３５に要求する。
【０１０９】
構成書換部３５は、構成番号変換部３２や演算部４からの要求が無く、構成情報記憶部に対する構成情報の書き込みを行っていないとき、選択部２からの構成要求を受理する旨の回答を選択部２に通知し、状態４の構成情報を構成情報記憶部に書き込む。このとき、状態４の構成情報を新たに書き込むことで構成情報記憶部から削除する構成情報の選択方法には様々な方法があるが、例えば遷移先候補に含まれない状態うち、最も過去に遷移した状態の構成情報を構成情報記憶部から削除する。具体的には、状態１２が最も過去に遷移した状態であり、かつ現在の状態３の遷移先候補に含まれていないため、状態１２の構成情報を状態４の構成情報で上書きする。
【０１１０】
選択部２は、構成情報記憶部に対する状態４の構成情報の書き込みの要求が受理された旨を構成書換部３５から受け取ると、遷移予測順位リストの全ての遷移先候補について、構成情報記憶部における構成情報の有無の調査を終了したことになるため、データ処理装置（ＤＲＰ）が次の状態に遷移するまで待機する。
【０１１１】
続いて、データ処理装置（ＤＲＰ）が状態３から状態６に遷移したとする。この場合、予測が外れたことになるが、予測更新部１２は、予測の当否に係わらず、制御部３から通知される、状態６に遷移したことを示す遷移情報を用いて遷移予測順位リストを更新する。
【０１１２】
状態３に対応する更新前の遷移予測順位リストの一例を図１１（ａ）に示す。
【０１１３】
図１１（ａ）に示すように、状態６は遷移予測順位リストに登録されていないため、予測更新部１２は、図９に示した論理回路を用いて、状態６の状態番号を遷移予測順位リストの第２位の遷移先候補として登録し、第２位の遷移先候補であった状態７の状態番号を第３位の遷移先候補に下げる。また、第３位の遷移先候補であった状態４の状態番号を遷移予測順位リストから削除する（図１１（ｂ））。予測更新部１２は、更新した状態３の新しい遷移予測順位リスト（５−６−７）（図１１（ｃ））を、予測保持部１１が保持している状態３の遷移予測順位リストと入れ替える。
【０１１４】
次に、データ処理装置（ＤＲＰ）が状態６、状態１０、状態１３、状態１５の順に遷移し、状態３に再び遷移した場合を考える。このとき、構成情報記憶部では、状態３，５，６，７，１０，１３，１４，１５の構成情報が保持され、予測保持部１１で保持している状態３の遷移予測順位リストは（５−６−７）である。
【０１１５】
データ処理装置（ＤＲＰ）が状態３に遷移したことが制御部３から予測部１に通知されると、予測保持部１１は状態３に対応する遷移予測順位リスト（５−６−７）を選択部２及び予測更新部１２に送信する。
【０１１６】
選択部２には、データ処理装置（ＤＲＰ）の命令メモリの構成情報記憶部で保持された構成情報を示す在非情報が制御部３及び予測保持部１１を介して通知される。
【０１１７】
選択部２は、予測保持部１１から遷移予測順位リスト（５−６−７）を受け取ると、遷移予測順位リストの上位の遷移先候補から順に、その状態の構成情報が命令メモリの構成情報記憶部で保持されているか否かを判定する。
【０１１８】
ここでは、上述したように遷移予測順位リストの全ての遷移先候補の構成情報が構成情報記憶部で保持されているため、選択部２はデータ処理装置（ＤＲＰ）が次の状態に遷移するまで待機する。
【０１１９】
続いて、データ処理装置（ＤＲＰ）が状態３から状態６に遷移したとする。その場合、予測が的中したことになる。予測更新部１２は、予測の当否に係わらず、制御部３から通知される、状態６に遷移したことを示す遷移情報を用いて遷移予測順位リストを更新する。
【０１２０】
予測更新部１２は、図９に示した論理回路を用いて、遷移予測順位リストの第２位の遷移先候補である状態６を第１位の遷移先候補として登録し、第１位の遷移先候補であった状態５を第２位の遷移先候補に下げる。遷移予測順位リストの第３位の状態７の順位は変更しない（図１１（ｄ））。
【０１２１】
予測更新部１２は、更新した状態３の新しい遷移予測順位リスト（６−５−７）（図１１（ｅ））を、予測保持部１１が保持している状態３の遷移予測順位リストと入れ替える。
【０１２２】
なお、本実施例では遷移予測順位リストに登録する遷移先候補数を３とし、遷移予測順位リストに登録されていない状態に遷移した場合、該状態を第２位の遷移先候補とする例を示しているが、上述したようにこれらの遷移先候補の登録方法については他の方法を採用してもよい。
【０１２３】
本実施例のように、遷移先候補に対して順位を付与し、多分岐による遷移先候補を予測し、該予測結果により遷移する可能性の高い状態から順に各々に対応する構成情報を構成情報記憶部に書き込むことで、遷移先の構成情報を構成情報記憶部で保持している可能性がより高まる。したがって、構成情報記憶部に対する構成情報の書き換えを待つことによる待機時間が低減するため、データ処理装置の処理性能（スループット）が向上する。
【０１２４】
（第２実施例）
第２実施例は、データ処理装置として上記特許文献１に記載されたＤＲＰを用い、該ＤＲＰに第４の実施の形態で示した多分岐予測装置を備える例である。上述したように第４の実施の形態の多分岐予測装置は、複数組の予測保持部及び予測更新部を備える構成である。第２実施例の多分岐予測装置は、第２の実施の形態で示した予測保持部及び予測更新部と、第３の実施の形態で示した予測保持部及び予測更新部を備えているものとする。
【０１２５】
図１２は第２実施例の多分岐予測装置の構成を示すブロック図である。
【０１２６】
図１２に示すように、本実施例のデータ処理装置（ＤＲＰ）は、演算部４、制御部３及び予測部１を有する。
【０１２７】
演算部４は、演算を実行するアレイ状に配置された複数のプロセッサエレメント（ＰＥ）４１と、制御部３よりも少数の状態を管理する補助制御部４２とを有する。
【０１２８】
プロセッサエレメント４１は、レジスタファイル（ＲＦＵ）、ＡＬＵ、データ処理演算器（ＤＭＵ）、命令メモリを備え、上記構成情報にしたがって他のプロセッサエレメント４１と接続される。上記構成情報記憶部は、例えば命令メモリに備えている。
【０１２９】
制御部３は、状態管理部３１、構成番号変換部３２及び構成書換部３５を備えた、ＤＲＰの状態遷移管理部（ＳＴＣ）に相当する。
【０１３０】
予測部１は、本発明の多分岐予測装置に相当し、２組の予測保持部１１及び予測更新部１２及び選択部２を有する。予測保持部１１１及び予測更新部１２１は第２の実施の形態で示した構成であり、予測保持部１１２及び予測更新部１２２は第３の実施の形態で示した構成である。
【０１３１】
予測保持部１１１（以下、予測保持部Ａと称す）は、現在の状態とその前の状態の組毎に、上位３つの遷移先候補の状態の状態番号を保持できるメモリを有する。
【０１３２】
予測保持部１１２（以下、予測保持部Ｂと称す）は、状態毎に、上位３つの遷移先候補の状態の状態番号を保持できるメモリを有する。
【０１３３】
選択部２は、予測保持部Ａ及び予測保持部Ｂで保持する、状態毎または状態の組毎の遷移予測順位リストで示される予測結果の当否確率を求め、予測保持部Ａまたは予測保持部Ｂで保持している遷移予測順位リストのうち、より高い確率で予測が正解する遷移予測順位リストを選択する。また、選択した遷移予測順位リストを用いて構成書換部３５に対して構成情報記憶部に対する構成情報の書き込みを要求（構成要求）すると共に、構成書換部３５から該構成要求を受理したか否かを示す回答を受け取る。なお、選択部２は、いずれか一方の遷移予測順位リストを選択する方法に限らず、例えば、予測結果の当否確率に基づいて、２つの遷移予測順位リストから構成情報の書き込みを要求する状態を選択してもよい。
【０１３４】
図１２に示すデータ処理装置の起動時、予測保持部Ａ，Ｂは、遷移予測順位リストを保持していない。
【０１３５】
予測保持部Ａ，Ｂは、制御部３及び演算部４が動作を開始し、制御部３から現在の状態を示す現状態情報を受け取ると、該状態に対応する遷移予測順位リストを選択部２及び予測更新部１２に送信する。この段階では遷移予測順位リスト内の遷移先候補数はゼロである。
【０１３６】
選択部２は、制御部３から通知される、構成情報記憶部で保持している構成情報の有無を示す情報（在非情報）を受けとる。ここでは、遷移予測順位リスト内の遷移先候補数がゼロであるため、構成書換部３５に対して構成情報の書き込みを要求しない。
【０１３７】
予測更新部Ａ，Ｂは、遷移予測順位リストを予測保持部Ａ，Ｂから受け取ると、データ処理装置（ＤＲＰ）で実際に状態遷移が発生するまで待機する。状態遷移が発生し、その遷移先を示す遷移情報が制御部３から通知されると、遷移予測順位リストと遷移情報に基づいて新しい遷移予測順位リストを作成する。
【０１３８】
予測更新部Ａは、遷移情報にしたがって実際に遷移した状態の状態番号を遷移先候補として遷移予測順位リストに順次登録する。ここで、遷移予測順位リストに登録された状態（遷移先候補）への遷移が発生した場合は、その状態（遷移先候補）の順位を一つ上位の遷移先候補と入れ替える。遷移予測順位リストの遷移先候補が３未満の場合は、空いている最上位の遷移先候補に遷移情報で通知された状態の状態番号を登録する。
【０１３９】
また、予測更新部Ａは、遷移予測順位リストに登録されていない状態（遷移先候補）への遷移が発生した場合、その状態を第２位の遷移先候補として登録し、第２位であった遷移先候補を第３位に下げ、第３位であった遷移先候補を遷移予測順位リストから削除する。新しい遷移予測順位リストは、予測保持部Ａが保持している対応する状態の遷移予測順位リストと入れ替える。
【０１４０】
予測更新部Ｂは、遷移情報により実際に遷移した状態が通知されると、各状態の遷移方向毎の遷移間隔履歴リストを作成する。
【０１４１】
予測更新部Ｂは、遷移情報により実際に遷移した状態が通知されると、その遷移先候補の状態に対応するカウンタの値を遷移間隔履歴リストへ格納し、該カウンタの値を１にする。また、該遷移先候補の状態以外の遷移先候補に対応するカウンタの値には１を加算する。
【０１４２】
また、予測更新部Ｂは、各遷移先候補に対応するカウンタの値と遷移間隔履歴リスト内の各値とを比較し、カウンタの値と一致する遷移間隔履歴リスト内の値の数が多い順に上位の遷移先候補とする遷移予測順位リストを作成する。新しい遷移予測順位リストは、予測保持部Ｂが保持している対応する状態の遷移予測順位リストと入れ替える。なお、カウンタの値と一致する遷移間隔履歴リスト内の値の数が等しい遷移先候補が複数ある場合は、カウンタの値がより大きい方を上位の遷移先候補とすればよい。
【０１４３】
以上の処理を状態の遷移毎に繰り返し実行することで、遷移先の状態を十分に高い精度で予測できる遷移予測順位リスト及び遷移間隔履歴リストが作成される。
【０１４４】
以下、図１０に示した状態遷移を実現するオブジェクトコードにしたがってデータ処理装置（ＤＲＰ）が動作する場合を例にして、本実施例の多分岐予測装置の動作について説明する。
【０１４５】
図１０に示した状態遷移は、画像データ等を転送するパケット処理を想定したものであり、三重のループ内に複数の主処理を備えている。主処理のうち、状態４を経由するパスは初期化時に実行する処理であり、状態１０を経由するパスは通常時に実行する処理であり、状態８を経由するパスはエラー発生時に実行する処理である。また、状態１は１２８回の遷移毎に１回通過し、状態２は１６回の遷移毎に１回通過するものとする。
【０１４６】
ここでは、データ処理装置（ＤＲＰ）が備える命令メモリ内の構成情報記憶部にて８つの構成情報が保持できるものとし、状態１，２，３，５，１０，１３，１４，１５の構成情報が構成情報記憶部で保持されているものとする。これらの状態は、補助制御部４２によって遷移が制御される、ＤＲＰ内で長期間滞留する状態である。また、ここでは、データ処理装置（ＤＲＰ）が図１０に示した状態遷移を多数回繰り返し実行し、現在、状態１５から状態３に遷移しているものとする。
【０１４７】
データ処理装置（ＤＲＰ）が状態３に遷移したことが制御部３から予測部１に通知されると、予測保持部Ａは、状態１５及び状態３の組に対応する遷移予測順位リストを選択部２及び予測更新部Ａに送信する。以下、このような状態の組を［１５−３］と表す。
【０１４８】
予測保持部Ａの遷移予測順位リストには、状態５が最上位（第１位）の遷移先候補として登録され、状態６が第２位の遷移先候補として登録され、状態７が第３位の遷移先候補として登録されているものとする。以下、このような遷移予測順位リストを（５−６−７）と表す。
【０１４９】
一方、予測保持部Ｂの遷移予測順位リストには、状態５が最上位（第１位）の遷移先候補として登録され、状態７が第２位の遷移先候補として登録され、状態６が第３位の遷移先候補として登録されているものとする。
【０１５０】
この場合、予測保持部Ａは状態３に対応する遷移予測順位リスト（５−６−７）を選択部２に送信し、予測保持部Ｂは状態３に対応する遷移予測順位リスト（５−７−６）を選択部２に送信する。このように予測保持部Ａの遷移予測順位リストと予測保持部Ｂの遷移予測順位リストは必ずしも一致するとは限らない。また、予測保持部Ａの遷移予測順位リストと予測保持部Ｂの遷移予測順位リストは遷移先候補数が異なることもある。
【０１５１】
選択部２には命令メモリの構成情報記憶部で保持された構成情報を示す在非情報が制御部３及び予測保持部Ａ，Ｂを介して通知される。
【０１５２】
選択部２は、予測保持部Ａから遷移予測順位リスト（５−６−７）を受け取り、予測保持部Ｂから遷移予測順位リスト（５−７−６）を受け取ると、過去の遷移予測の当否確率からいずれか一方の遷移予測順位リストを選択する。ここでは、予測保持部Ａの遷移予測順位リストの方がより予測が正解しているものとする。選択部２は、選択した遷移予測順位リストの上位の遷移先候補から順に、その状態の構成情報が命令メモリの構成情報記憶部で保持されているか否かを判定する。上述したように第１位の遷移先候補である状態５の構成情報が構成情報記憶部で保持されているため、選択部２は、第２位の状態６及び第３位の状態７の構成情報を命令メモリの構成情報記憶部に書き込むよう構成書換部３５に要求する。以降の構成書換部３５の動作は第１実施例と同様であるため、その説明は省略する。
【０１５３】
ここで、状態６の構成情報を命令メモリの構成情報記憶部に書き込むよう構成書換部３５に要求し、構成書換部３５が状態６の構成情報を構成情報記憶部に書き込んだ後にデータ処理装置（ＤＲＰ）が状態６に遷移した場合、予測が的中したことになる。仮に、選択部２が予測保持部Ｂの遷移予測順位リストを選択していた場合、構成書換部３５は先に状態７の構成情報を構成情報記憶部に書き込むため、状態７の構成情報を書き込んだ時点でデータ処理装置（ＤＲＰ）が状態６に遷移すると、構成情報記憶部に状態６の構成情報が無いために予測が外れたことになる。その場合、データ処理装置（ＤＲＰ）は状態６の構成情報の書き込みが完了するまで何も実行せずに待機する。選択部２は、このような予測結果の当否を保持して統計処理し、以降の遷移予測順位リストの選択時に利用する。
【０１５４】
遷移予測順位リストの選択方法には、より高い確率で予測が正解する遷移予測順位リストのみを選択する方法と、予測の当否確率に基づいて各遷移予測順位リストの遷移先候補にそれぞれ重みを付与し、重み付与後の遷移先候補からなる遷移予測順位リストを選択する方法とがある。本実施例では前者を採用する。後者は遷移先候補に対する重み付け等の処理を要するため、処理コストが上昇する。
【０１５５】
予測更新部Ａは、状態の組［１５−３］に対応する遷移予測順位リストを予測保持部Ａから受け取り、データ処理装置（ＤＲＰ）が状態６に遷移すると、第１実施例と同様の処理にて該遷移予測順位リストを更新し、新しい遷移予測順位リスト（６−５−７）を予測保持部Ａで保持している状態の組［１５−３］に対応する遷移予測順位リストと入れ替える。
【０１５６】
図１０に示した状態遷移では、状態３に関連して、状態の組［２−３］に対応する遷移予測順位リストと［１５−３］に対応する遷移予測順位リストの二つが存在する。また、データ処理装置（ＤＲＰ）が状態２から状態３へ遷移した場合、次の遷移先は状態４だけであるが、状態１５から状態３へ遷移した場合、次の遷移先は状態５，６，７，８がある。すなわち、状態の組［２−３］に対応する遷移予測順位リストには状態４が遷移先候補として登録されるが、状態の組［１５−３］に対応する遷移予測順位リストには状態４が遷移先候補として登録されない。したがって、現在の状態とその前の状態の組毎に遷移予測順位リストを備えることで、状態毎に遷移予測順位リストを備える構成よりも予測の精度を向上させることができる。
【０１５７】
予測更新部Ｂは、状態３に対応する、例えば図１３Ａに示すカウンタ及び遷移間隔履歴リストを備えている。
【０１５８】
図１３Ａは、最も新しい状態から古い状態に向かって、状態５，５，６，７，５，５，６，６，５，５，６，４，５，５，６，６，５，５，６，…の順に遷移してきたときの遷移先候補毎に備えるカウンタ及び遷移間隔履歴リストの一例をそれぞれ示している。図１３Ａでは、状態３の遷移先候補が状態４、５、６、７、８であり、カウンタの値は対応する状態の遷移間隔を示し、遷移間隔履歴リストの値は過去の遷移間隔の履歴（４つの遷移間隔）を示している。なお、初期状態から任意の遷移先候補への遷移が一度もない場合は、カウンタの値は初期状態からの遷移回数を示すことになる。
【０１５９】
例えば、図１３Ａに示す状態４に対応するカウンタの値は、前回状態４に遷移してから１２回の遷移で状態３から状態４へ再び到達したことを示している。また、状態４に対応する遷移間隔履歴リストは、遷移間隔が１６毎に状態３から状態４へ到達していることを示している。
【０１６０】
図１４は、上述した状態の遷移（遷移履歴）に対して、遷移先候補である状態５、６に対応するカウンタ及び遷移間隔履歴リストが変化している様子を模式的に示したものである。
【０１６１】
図１３Ａに示す状態８に対応するカウンタの値は、データ処理装置（ＤＲＰ）が初期化されてから状態が１２４回遷移しても、状態３から状態８への遷移が一度も発生していないことを示している。
【０１６２】
本実施例ではデータ処理装置が状態３から状態６へ遷移しているため、予測更新部Ｂは、図１３Ｂに示すように、状態６に対応する遷移間隔履歴リストの各値をシフトさせ、カウンタの値を遷移間隔履歴リストの先頭に挿入した後、カウンタの値を１に設定する。また、遷移していない状態４、５、７、８に対応するカウンタの値に１を加算する。以上の操作を行った後の各遷移先候補に対応するカウンタ及び遷移間隔履歴リストの値は図１３Ｃに示すようになる。
【０１６３】
予測更新部Ｂは、遷移先候補毎にカウンタの値と遷移間隔履歴リストの各エントリの値とを比較し、カウンタの値と一致するエントリの値の数が多い遷移先候補を抽出する（図１３Ｄ）。カウンタ及び遷移間隔履歴リストの値が図１３Ｃで示す例であった場合、予測更新部Ｂは、状態６を最も上位とする遷移予測順位リストを作成し、新しい遷移予測順位リストを、予測保持部Ｂで保持している状態３に対応する遷移予測順位リストと入れ替える。
【０１６４】
次に、データ処理装置（ＤＲＰ）の状態が遷移して状態１５に到達した場合を考える。
【０１６５】
この場合でも予測更新部Ａ及び予測更新部Ｂは、上述した処理と同様の処理により遷移予測順位リストを更新する。このとき、予測更新部Ｂの遷移間隔履歴リストには、状態１へは１２８回の遷移毎に１回到達し、状態２へは１６回の遷移毎に１回到達することが記録される。したがって、状態１５に対応する、予測更新部Ｂの遷移間隔履歴リストに基づいて更新された遷移予測順位リスト内の遷移先候補には、高い確率で遷移する。
【０１６６】
その場合、選択部２は、予測保持部Ｂの遷移予測順位リストを採用し、必要なときのみに状態１及び状態２の構成情報を構成情報記憶部に書き込むよう構成書換部３５に要求すればよい。
【０１６７】
そのため、構成情報記憶部に対する不要な構成情報の書き込みを行うことによって他の構成情報が消去されることがなく、かつ必要なときには構成情報の書き込みを待つことなく状態１及び状態２へ遷移できる。よって、必要な状態の構成情報を構成情報記憶部から消去する確率が減少する。
【０１６８】
図１５は状態１５から状態１へ遷移するときの予測更新部Ｂが備える遷移先候補毎のカウンタ及び遷移間隔履歴リストの一例を示している。
【０１６９】
図１５に示す例では、全ての遷移先候補にて、カウンタの値と遷移間隔履歴リストの各エントリの値とが一致している。このような場合は、カウンタの値が大きい遷移先候補を上位とする遷移予測順位リストを生成する。具体的には、カウンタの値が１２８である状態１を最も上位とする遷移予測順位リスト（１−２−３）を予測保持部Ｂの状態１５に対応する遷移予測順位リストと入れ替える。
【０１７０】
本実施例のように、多分岐による遷移先候補を複数の方法を用いて予測し、それら複数の方法の予測結果のうち、最も正解する確率が高い予測結果、あるいは複数の予測結果の組み合せに基づいて、遷移する可能性の高い状態から順に各々に対応する構成情報を構成情報記憶部に書き込むことで、遷移先の構成情報を構成情報記憶部で保持している可能性がより高まる。したがって、構成情報記憶部に対する構成情報の書き換えを待つことによる待機時間がより低減するため、第１実施例よりもデータ処理装置の処理性能（スループット）が向上する。
【０１７１】
（第３実施例）
第３実施例は、データ処理装置として、上記特許文献１に記載されたＤＲＰを用い、該ＤＲＰに第６の実施の形態または第７の実施の形態で示した多分岐予測装置を備える例である。上述したように第６の実施の形態及び第７の実施の形態の多分岐予測装置は、複数組の予測保持部及び予測更新部を備える構成である。第３実施例の多分岐予測装置は、第２の実施の形態で示した予測保持部及び予測更新部を備えた予測部と、第３の実施の形態で示した予測保持部及び予測更新部を備えた予測部とを有するものとする。
【０１７２】
図１６は第３実施例の多分岐予測装置の構成を示すブロック図である。
【０１７３】
図１６に示すように、本実施例の多分岐予測装置は、第２実施例で示した予測部１に手掛保持部１５を追加した構成である。予測保持部１１１及び１１２の動作は第２実施例と同様であるため、その説明は省略する。また、データ処理装置（ＤＲＰ）が備える演算部４及び制御部３の構成及び動作についても第２実施例と同様であるため、その説明は省略する。
【０１７４】
手掛保持部１５は、現状態情報や遷移情報以外に演算部４及び制御部３から動的に取得できる情報、例えば各状態における滞留時間の長短を示す情報を保持する。この滞留時間の情報は、選択部２に手掛情報として供給される。
【０１７５】
また、手掛保持部１５は、例えば演算部４から制御部３に構成情報の先読み（プリロード）が要求された場合、このプリロード要求の有無を示す情報を保持する。このプリロード要求の有無を情報は、予測更新部１２１及び１２２に手掛情報として供給される。
【０１７６】
本実施例の選択部２は、第２実施例と同様に、予測保持部Ａ（１１１）及び予測保持部Ｂ（１１２）で保持する、状態毎または状態の組毎の遷移予測順位リストで示される予測結果の当否確率を求め、予測保持部Ａまたは予測保持部Ｂで保持している遷移予測順位リストのうち、より高い確率で予測が正解する遷移予測順位リストを選択する。また、選択部２は、選択した遷移予測順位リストを用いて構成書換部３５に対して構成情報記憶部に対する構成情報の書き込みを要求（構成要求）すると共に、構成書換部３５から該構成要求を受理したか否かを示す回答を受け取る。なお、選択部２は、予測保持部Ａまたは予測保持部Ｂのいずれか一方の遷移予測順位リストを選択する方法に限らず、例えば予測結果の当否確率に基づいて２つの遷移予測順位リストから構成情報の書き込みを要求する状態を選択してもよい。
【０１７７】
さらに、本実施例の選択部２は、手掛保持部１５で保持している手掛情報に基づき、状態の特性に応じて予測保持部Ａまたは予測保持部Ｂで保持している遷移予測順位リストを選択する。このとき、本実施例の選択部２では、手掛保持部１５から供給される手掛情報に基づいて、全ての遷移予測順位リストを採用しない場合もある。例えば、現在の状態の滞留時間が短いという手掛情報を取得し、かつ各遷移先の構成情報が構成情報記憶部に存在しておらず、予測による遷移先の構成情報を構成情報記憶部に書き込んでも処理サイクル数の短縮が期待できない場合等が該当する。
【０１７８】
逆に、現在の状態及び全ての遷移先の状態への滞留時間が長いという手掛情報を取得した場合、現在の状態からの遷移先の構成情報を全て用意しておき、遷移後の長い滞留時間で不要であった状態を、その後必要となる状態に再度書き換える方針を採用してもよい。また、手掛情報に基づいて、滞留時間が短い状態では、予測による構成情報記憶部に対する構成情報の書き込みを構成書換部３５へ要求しない方法も選択できる。
【０１７９】
本実施例の選択部２の具体的な動作について図１０に示した状態遷移図を用いて説明する。
【０１８０】
図１０に示した状態遷移図によれば、データ処理装置は、例えば状態１０からは状態１３または状態１４へ遷移し、状態１３及び状態１４からは状態１５へ遷移する。
【０１８１】
本実施例の手掛保持部１５は、図１７に示すように、データ処理装置から動的に取得できる情報（滞留時間の情報）に所要の加工処理を実施して保持する。具体的には、状態毎にその滞留時間の長短を示す情報を２ｂｉｔで保持する。
【０１８２】
例えば、状態１０、状態１３及び状態１４に対応する手掛情報として滞留時間が長いことを示す情報（ｂｉｔ列が「１０」）を手掛保持部１５が保持している場合、選択部２は、データ処理装置が状態１０にあるとき、状態１３及び状態１４の構成情報を構成情報記憶部に書き込むよう構成書換部３５に要求し、状態１３または状態１４に遷移すると、その状態の滞留中に状態１５の構成情報を書き込めると予測できる。
【０１８３】
一方、選択部２は、状態１０に対応してｂｉｔ列が「０１」、すなわち滞留時間が短いという手掛情報を手掛保持部１５から得た場合、例えば状態１３の構成情報を書き込み始めた直後に状態１４に遷移するような場合であって、かつ予測保持部１１の予測を併せても状態１３または状態１４へ遷移する確率がそれぞれ５０％の場合、状態１３の構成情報の書き込みが大きな分岐のペナルティとなると予測できる。その場合、状態１０の滞留中に構成情報の書き込みを要求しないことで分岐のペナルティの発生を防止できる。
【０１８４】
ところで、状態の遷移に先立って遷移先候補の構成情報のプリロード要求が発行される場合、データ処理装置は、その遷移先候補の状態へ必ず遷移する。その場合、プリロード要求が発行される遷移先候補を遷移予測順位リストに登録するのは無駄であり、遷移予測順位リストから他の遷移先候補を排除してしまうことになる。したがって、本実施例の予測更新部Ａ１２１は、手掛保持部１５から得られる手掛情報に基づき、プリロード要求が発行される遷移先候補を遷移予測順位リストに登録しないようにする。
【０１８５】
本実施例の予測更新部Ａ（１２１）の具体的な動作について図１０に示した状態遷移図を用いて説明する。
【０１８６】
図１０に示した状態遷移図によれば、データ処理装置は、例えば状態３から状態４、状態５、状態６、状態７または状態８へ遷移する。ここで、データ処理装置は、状態３でエラーが発生したときに状態８へ遷移するものとし、状態８への遷移が確定した時点でプリロード要求を発行し、以降の処理へ進むものとする。
【０１８７】
本実施例の手掛保持部１５は、図１７に示すように、データ処理装置から動的に取得できる情報（プリロード要求の有無）に所要の加工処理を実施して保持する。具体的には、状態毎にその状態から分岐可能な遷移先候補数に一致するｂｉｔ列を備え、分岐可能な各遷移先候補に対応するｂｉｔの初期値を「０」とし、プリロード要求が発行されることなく遷移したことがある遷移先候補に対応するｂｉｔの値を「１」に変更する。
【０１８８】
図１７に示す例では、状態３から状態８へ遷移する場合、過去にプリロード要求が発行されているため、手掛保持部１５は、状態８に対応するｂｉｔで「０」を保持し、予測対象外の遷移先候補としている。また、状態３から状態４、５、６、７へ遷移する場合、過去にプリロード要求が発行されないため、手掛保持部１５は、状態４、５、６、７に対応するｂｉｔで「１」を保持し、予測対象の遷移先候補としている。この場合、予測更新部Ａは、手掛保持部１５で保持しているｂｉｔの値が１の遷移先候補、すなわち状態４、５、６、７を遷移予測順位リストに登録し、ｂｉｔの値が０の遷移先候補、すなわち状態８は遷移予測順位リストに登録しない。
【０１８９】
本実施例のように、手掛情報に基づき、予測による構成情報記憶部に対する構成情報の書き込みにデメリットが予想される場合は構成情報の書き込みを構成書換部３５に要求しないことで、遷移先の構成情報を構成情報記憶部で保持している可能性がより高まる。したがって、構成情報記憶部に対する構成情報の書き換えを待つことによる待機時間がより低減するため、第２実施例よりもデータ処理装置の処理性能（スループット）が向上する。
【０１９０】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されものではない。本願発明の構成や詳細は本願発明のスコープ内で当業者が理解し得る様々な変更が可能である。
【０１９１】
この出願は、２００８年２月  １日に出願された特願２００８−０２２６４７号および２００８年  ６月２６日に出願された特願２００８−１６７３３２号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2009096247.tif 000003
【図２】
2009096247.tif 000004
【図３】
2009096247.tif 000005
【図４】
2009096247.tif 000006
【図５】
2009096247.tif 000007
【図６】
2009096247.tif 000008
【図７】
2009096247.tif 000009
【図８】
2009096247.tif 000010
【図９】
2009096247.tif 000011
【図１０】
2009096247.tif 000012
【図１１】
2009096247.tif 000013
【図１２】
2009096247.tif 000014
【図１３Ａ】
2009096247.tif 000015
【図１３Ｂ】
2009096247.tif 000016
【図１３Ｃ】
2009096247.tif 000017
【図１３Ｄ】
2009096247.tif 000018
【図１４】
2009096247.tif 000019
【図１５】
2009096247.tif 000020
【図１６】
2009096247.tif 000021
【図１７】
2009096247.tif 000022
【手続補正書】
【提出日】平成22年7月30日(2010.7.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
現在の状態から複数の状態への遷移が可能なデータ処理装置の、前記遷移先の状態を予測するための多分岐予測方法であって、
遷移する可能性に応じて順位付けられた、前記遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、前記データ処理装置の前記状態毎に作成し、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ装置から受け取ると、前記遷移情報を用いて前記遷移予測順位リストを更新する多分岐予測方法。
【請求項２】
前記遷移予測順位リストを、前記状態とその一つ以上前の状態の組毎に生成する請求項１記載の多分岐予測方法。
【請求項３】
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、前記遷移予測順位リストにおける該状態の順位を上位へ移動し、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在しない場合、該状態の順位を前記遷移予測順位リストの予め決められた順位に挿入する請求項１または２記載の多分岐予測方法。
【請求項４】
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、
前記遷移予測順位リストにおける該状態の順位を最上位へ移動する請求項１または２記載の多分岐予測方法。
【請求項５】
前記遷移情報を用いて、前記遷移先の候補である状態毎に、同じ状態に再び遷移するまでの遷移数を示す遷移間隔をカウンタで計数し、
前記遷移先の候補である状態毎に、複数の前記遷移間隔を保持することで遷移間隔履歴リストを作成し、
前記カウンタの値と前記遷移間隔履歴リストで保持された値とを比較し、
前記カウンタの値と一致する前記遷移間隔履歴リストで保持された値の数が多いほど対応する前記状態を上位の遷移先の候補とする、前記遷移予測順位リストを作成する請求項１または２記載の多分岐予測方法。
【請求項６】
現在の状態から複数の状態への遷移が可能なデータ処理装置の、前記遷移先の状態を予測するための多分岐予測装置であって、
遷移する可能性に応じて順位付けられた、前記遷移先の候補となる状態を示す複数の状態番号から成る遷移予測順位リストを、前記データ処理装置の前記状態毎に保持する予測保持部と、
前記現在の状態から実際に遷移した状態を示す遷移情報を前記データ装置から受け取ると、前記遷移情報を用いて前記遷移予測順位リストを更新する予測更新部と、
を有する多分岐予測装置。
【請求項７】
前記予測保持部は、
前記遷移予測順位リストを、前記状態とその一つ以上前の状態の組毎に保持する請求項６記載の多分岐予測装置。
【請求項８】
前記予測更新部は、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、前記遷移予測順位リストにおける該状態の順位を上位へ移動し、前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在しない場合、該状態の順位を前記遷移予測順位リストの予め決められた順位に挿入する請求項６または７記載の多分岐予測装置。
【請求項９】
前記予測更新部は、
前記遷移情報で通知された状態の状態番号が前記遷移予測順位リストに存在する場合、前記遷移予測順位リストにおける該状態の順位を最上位へ移動する請求項６または７記載の多分岐予測装置。
【請求項１０】
前記予測更新部は、
前記遷移情報を用いて、前記遷移先の候補である状態毎に、同じ状態に再び遷移するまでの遷移数を示す遷移間隔をカウンタで計数し、前記遷移先の候補である状態毎に、複数の前記遷移間隔を保持することで遷移間隔履歴リストを作成し、前記カウンタの値と前記遷移間隔履歴リストで保持された値とを比較し、前記カウンタの値と一致する前記遷移間隔履歴リストで保持された値の数が多いほど対応する前記状態を上位の遷移先の候補とする、前記遷移予測順位リストを作成する履歴保持部を有する請求項６または７記載の多分岐予測装置。
【国際調査報告】
2009096247.tif 000023
2009096247.tif 000024
2009096247.tif 000025
2009096247.tif 000026