Top > Search of International Patents > INFORMATION PROCESSING DEVICE AND METHOD, PROGRAM, AND RECORDING MEDIUM

INFORMATION PROCESSING DEVICE AND METHOD, PROGRAM, AND RECORDING MEDIUM

Foreign code F080001916
File No. F080001916
Posted date Sep 12, 2008
Country WIPO
International application number 2007JP051965
International publication number WO 2008/012957
Date of international filing Feb 6, 2007
Date of international publication Jan 31, 2008
Priority data
  • P2006-203106 (Jul 26, 2006) JP
Title INFORMATION PROCESSING DEVICE AND METHOD, PROGRAM, AND RECORDING MEDIUM
Abstract An information processing device and method, a program, and a recording medium capable of reducing the time required for prediction and improving the accuracy of branch prediction. In a pipeline structure where M chains each having a length of n groups and sequentially processed at each stage are formed by dividing pipelines in which the branch results included in a global history (84) are divided in order of history and sequentially processed at each stage into n groups in each of which M branch results are processed in a block parallel way at the same stage sequentially from the latest history except for the last stage, a weight selecting section (61) selects a weight from a weight table (82) and reads it, a weighted branch result value accumulating section (62) calculates the weighted branch result value by using the weight value and determines the accumulated value, and a prediction value calculating section (73) calculates the prediction value by using the sum of the weighted branch result accumulated values and the threshold calculated by a threshold calculating section (72). The invention can be applied to a branch predictor.
Scope of claims (In Japanese)
【請求項1】過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプライン構造を有し、前記分岐命令のアドレスに前記分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成する多重化アドレス生成手段と、前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記多重化アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択する重み選択手段と、前記重み選択手段により選択された前記各重みにより、前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出する重み付き分岐結果値累算手段と、前記ステージの最終段において、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果累算値を用いて、予測値を算出する予測値算出手段とを備える情報処理装置。

【請求項2】前記最終段のステージを除いて、前記パイプラインを履歴順に所定長を有する複数の鎖に分割し、前記各鎖を前記ステージ毎に順次処理することにより、前記鎖の本数分の処理を同時並列的に行うパイプライン構造を有し、前記重み選択手段は、いずれかの前記鎖のいずれかの前記ステージにおいては、前記多重化アドレスを用いて、割り当てられた前記重みテーブルより重みを選択し、前記重み付き分岐結果値累算手段は、前記鎖の前記ステージ毎に前記重み付き分岐結果値を取得し、前記鎖毎に前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、前記予測値算出手段は、前記重み付き分岐結果値累算手段により前記鎖毎に累算された重み付き分岐結果累算値の総和を算出し、算出した重み付き分岐結果累算値の総和を用いて予測値を算出する請求項1に記載の情報処理装置。

【請求項3】前記最終段のステージを除いて、前記パイプラインを履歴順に同一ステージで同時並列的に処理する複数のグループに分割することにより、前記グループの数分の長さを有し前記ステージ毎に順次処理を行う鎖が複数本形成されるパイプライン構造を有し、前記重み選択手段は、いずれかの前記鎖のいずれかの前記ステージにおいては、前記多重化アドレスを用いて、割り当てられた前記重みテーブルより重みを選択し、前記重み付き分岐結果値累算手段は、前記鎖の前記ステージ毎に前記重み付き分岐結果値を取得し、前記鎖毎に前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、前記予測値算出手段は、前記重み付き分岐結果値累算手段により前記鎖毎に累算された重み付き分岐結果累算値の総和を算出し、算出した重み付き分岐結果累算値の総和を用いて予測値を算出する請求項1に記載の情報処理装置。

【請求項4】前記重み選択手段は、予測を行う分岐命令のアドレスであるターゲットアドレスに最も近い分岐命令のアドレスに対する分岐結果が割り当てられた前記鎖の前記ステージにおいては、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスのみをインデックスとして前記重みテーブルより前記重みを選択し、前記ターゲットアドレスに最も近い分岐命令のアドレスに対する分岐結果以外の分岐結果が割り当てられた前記鎖の前記ステージにおいては、前記最新のアドレスと前記多重化アドレスとの排他的論理和をインデックスとして前記重みテーブルより前記重みを選択する請求項2または3に記載の情報処理装置。

【請求項5】前記最終段のステージに割り当てられた前記重みテーブルより前記多重化アドレスを用いて閾値としての重みを算出する閾値算出手段を備え、前記予測値算出手段は、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果累算値に前記前記閾値算出手段により算出された前記閾値を加算することにより、前記予測値を算出する請求項1乃至請求項4のいずれかに記載の情報処理装置。

【請求項6】前記閾値算出手段は、前記多重化アドレスをインデックスとして前記重みテーブルより前記閾値を算出する請求項5に記載の情報処理装置。

【請求項7】前記閾値算出手段は、前記最新のアドレスを用いて対応する前記閾値を候補として全てを特定し、前記ローカル履歴を用いて前記全候補の中から前記閾値を選択する請求項5に記載の情報処理装置。

【請求項8】過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理方法であって、前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次パイプライン処理を行い、前記分岐命令のアドレスに前記分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成し、前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記多重化アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択し、前記重み選択手段により選択された前記各重みにより、前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、前記ステージの最終段において、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果累算値を用いて、予測値を算出するステップを含む情報処理方法。

【請求項9】過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する処理を行うプログラムであって、前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次パイプライン処理を行い、前記分岐命令のアドレスに前記分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成し、前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記多重化アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択し、前記重み選択手段により選択された前記各重みにより、前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、前記ステージの最終段において、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果累算値を用いて、予測値を算出するステップをコンピュータに実行させるプログラム。

【請求項10】請求項9に記載のプログラムが記録されている記録媒体。

【請求項11】過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプラインを、前記ステージの最終段を除いて、履歴順に同一ステージで同時並列的に処理する複数のグループに分割することにより、前記グループの数分の長さを有し前記ステージ毎に順次処理を行う鎖が複数本形成されるパイプライン構造を有し、前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記分岐結果に対する分岐命令アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択する重み選択手段と、前記重み選択手段により選択された前記各重みにより、前記各鎖の前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記鎖毎に前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出する重み付き分岐結果値累算手段と、前記ステージの最終段において、前記重み付き分岐結果値累算手段により前記鎖毎に累算された前記重み付き分岐結果値の総和を算出し、算出した重み付き分岐結果値を少なくとも用いて予測値を算出する予測値算出手段とを備える情報処理装置。

【請求項12】過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する処理を行うプログラムであって、前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプラインを、前記ステージの最終段を除いて、履歴順に同一ステージで同時並列的に処理する複数のグループに分割することにより、前記グループの数分の長さを有し前記ステージ毎に順次処理を行う鎖を複数本形成してパイプライン処理を行い、前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記分岐結果に対する分岐命令アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択し、前記重み選択手段により選択された前記各重みにより、前記各鎖の前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記鎖毎に前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、前記ステージの最終段において、前記重み付き分岐結果値累算手段により前記鎖毎に累算された前記重み付き分岐結果値の総和を算出し、算出した重み付き分岐結果値を少なくとも用いて予測値を算出するステップをコンピュータに実行させるプログラム。

【請求項13】請求項12に記載のプログラムが記録されている記録媒体。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • The University Of Electro-communications
  • Inventor
  • Ninomiya, Yasuyuki
  • Abe, Koki
IPC(International Patent Classification)
Specified countries AE AG AL AM AT AU AZ BA BB BE BF BG BJ BR BW BY BZ CA CF CG CH CI CM CN CO CR CU CY CZ DE DK DM DZ EC EE EG ES FI FR GA GB GD GE GH GM GN GQ GR GT GW HN HR HU ID IE IL IN IS IT JP KE KG KM KN KP KR KZ LA LC LK LR LS LT LU LV LY MA MC MD MG MK ML MN MR MW MX MY MZ NA NE NG NI NL NO NZ OM PG PH PL PT RO RS RU SC SD SE SG SI SK SL SM SN SV SY SZ TD TG TJ TM TN TR TT TZ UA UG US UZ VC VN ZA ZM ZW
Please contact us by E-mail or facsimile if you have any interests on this patent.

PAGE TOP

close
close
close
close
close
close