TOP > 国内特許検索 > 情報処理装置および方法、並びにプログラム

情報処理装置および方法、並びにプログラム コモンズ

国内特許コード P110004841
整理番号 07-020JP00
掲載日 2011年8月18日
出願番号 特願2007-199159
公開番号 特開2009-037305
登録番号 特許第5283054号
出願日 平成19年7月31日(2007.7.31)
公開日 平成21年2月19日(2009.2.19)
登録日 平成25年6月7日(2013.6.7)
発明者
  • 二ノ宮 康之
  • 阿部 公輝
出願人
  • 国立大学法人電気通信大学
発明の名称 情報処理装置および方法、並びにプログラム コモンズ
発明の概要

【課題】実装コストの低減、および、分岐予測の予測精度向上を実現させることができるようにする。
【解決手段】重み選択部61は、重みテーブル82から、互いの命令間距離が比較的短い複数の多重化アドレスを用いて生成された通常間隔インデックス87、または、互いの命令間距離が比較的長い複数の多重化アドレスを用いて生成された長間隔インデックス88に対応する重みをそれぞれ選択して読み出す。重み付き分岐結果値算出部62は、重み付き分岐結果値を算出する。重み付き分岐結果値累算部63および重み付き分岐結果値累算部71は、重み付き分岐結果値を累算する。予測値算出部73は、重み付き分岐結果累算値と閾値とを加算することによって予測値を算出する。本発明は、分岐予測器に適用することができる。
【選択図】図2

従来技術、競合技術の概要


近年、プロセッサのパイプラインはさらなる深化の傾向を見せており、パイプラインが深くなるにつれ制御ハザードに起因する性能低下はより深刻なものとなってきている。制御ハザードはプログラム内に存在するif文やWhile文に代表される分岐命令によって引き起こされる。これを回避する1つの手段として用いられるのが分岐命令の分岐方向(分岐成立(Taken)、若しくは、分岐不成立(Not Taken))を予測する分岐予測である。1990年代に入りgshare分岐予測器が考えられたが、わずかな予測精度向上でプロセッサのパフォーマンスは大幅に向上するため、分岐予測器には、さらなる予測精度の向上が要求された。



分岐予測器はCPUの性能向上に大きな役割を果たしており、近年において活発に研究が行われている。中でも学習理論の一種であるパーセプトロンを応用したパーセプトロン分岐予測器は、単体で高い予測精度を示すことで注目されている。



パーセプトロン分岐予測器は、予測すべき分岐命令であるbranch Bのアドレスの他に過去に実行した分岐命令のアドレスを時系列に並べた実行パス履歴、過去の分岐結果の履歴を時系列順に並べたグローバル履歴、および、この分岐履歴を対の情報である分岐命令のアドレスを用いて並び替えたローカル履歴などを用いて予測を行う(例えば、特許文献1参照)。



パーセプトロン分岐予測器は、branch Bのアドレスや実行パス履歴をインデックスとして重みテーブルと呼ばれる多数のテーブルからそれぞれ重みと呼ばれる整数値を読み出す。これらの重みはそれぞれグローバル履歴の特定の場所と1対1に対応している。グローバル履歴の各要素は、1ならば分岐成立、-1ならば分岐不成立を表わす。パーセプトロン分岐予測器は、読み出された重みをWiとし、対応するグローバル履歴の要素をXiとし、さらに、1≦i≦nとし、次式を計算する。



【数式1】





式(1)において、W0はバイアスであり、重みと同様に読み出される。パーセプトロン分岐予測器は、求められたyの値が正ならば分岐成立として値「1」を出力し、yの値が負ならば分岐不成立として値「-1」を出力する。重みWiの更新規則は、分岐結果をt∈{1,-1}とすると次式によって表される。通常の場合、α=1とする。



【数式2】




以上の様なパーセプトロン分岐予測器として、これまでに、基本的な構造によるGlobal/Local Perceptron Branch Predictor、予測処理のパイプライン化を可能としたPath-based Neural Predictor、重み読み出しのインデックスを工夫したPiecewise Linear Branch Predictor、重み読み出しの並列化を行ったPTBP、およびAdvanced Anti-Aliasing Perceptron Branch Predictor (A3PBP)などのパーセプトロン分岐予測器等が知られている。



例えば、A3PBPは、実行パス履歴の情報をより効率的に利用する構造を持ち、ローカル履歴を重み読み出しのインデックスに利用することにより、重みの負の衝突を削減し予測精度を向上させた(例えば非特許文献1および非特許文献2参照)。



A3PBPでは、ステージnにおけるm番目の重みテーブルTablei=(n-1)M+m(1≦n≦h,1≦m≦M)のインデックスindex[i]を、A[s]を用いて生成する。A[s]は、branch Bよりs個前の分岐命令のアドレス、すなわち、実行パス履歴を表す。A[0]は、そのステージで得られうる最新のアドレスを示す。A3PBPは、この実行パス履歴を構成するアドレスの一部分をローカル履歴ビットに置換した多重化アドレスを用いて、以下の式(3)のように、最新のアドレスA[0]と多重化アドレスの排他的論理和によりindex[i]を生成し、そのインデックスを用いて重みを選択する。



【数式3】





【特許文献1】特開平10-171653号公報

【非特許文献1】二ノ宮康之、阿部公輝「実行パスとローカル履歴を重み選択に利用したパーセプトロン分岐予測器」情報処理学会研究報告(IPSJ SIG Technical Report),2006-ARC-169(6),2006年8月1日,p.31-36

【非特許文献2】Y. Ninomiya and K. Abe, "A3PBP: A Path Traced Perceptron Branch Predictor Using Local History for Weight Selection," The Journal of Instruction-Level Parallelism, Vol.9, pp.1-18, May 2007.

産業上の利用分野


本発明は、情報処理装置および方法、並びにプログラムに関し、特に、実装コストの低減、および、分岐予測の予測精度向上を実現させることができるようにした情報処理装置および方法、並びにプログラムに関する。

特許請求の範囲 【請求項1】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、
前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、
最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、
前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルと、
前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、
前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、
前記重み付き分岐結果値算出手段により最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、
少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段と
を備える情報処理装置。

【請求項2】
少なくとも、前記重み選択手段による前記重みの選択、および、前記重み付き分岐結果値算出手段による重み付き分岐結果の算出をステージ1とし、
少なくとも、前記予測値算出手段による予測値の算出をステージ0とし、
ステージ毎に順次処理を行う
請求項1に記載の情報処理装置。

【請求項3】
前記ステージ1における処理の処理結果を保持する保持手段をさらに備え、
前記分岐命令の分岐方向の予測の度に、前記ステージ0の処理、および、前記ステージ1の処理を行い、
前記ステージ1の処理の処理結果を前記保持手段に保持させるとともに、前記ステージ0の処理を、前記保持手段に保持されている前回の予測において行われた前記ステージ1の処理の処理結果を用いて行う
請求項2に記載の情報処理装置。

【請求項4】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ1とし、
前記ステージ1において前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値の累算結果を前記保持手段に保持させ、
前記ステージ0において、前記予測値算出手段により、前記保持手段に保持されている前記累算結果を用いて前記予測値を算出させる
請求項3に記載の情報処理装置。

【請求項5】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算の一部を前記ステージ1とし、残りの一部を前記ステージ0とし、
前記ステージ1において、前記重み付き分岐結果値累算手段により、前記重み付き分岐結果値の累算を途中まで行わせ、
得られた累算途中結果を前記保持手段に保持させ、
前記ステージ0において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記累算途中結果をさらに累算させる
請求項3に記載の情報処理装置。

【請求項6】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ0とし、
前記ステージ1において前記重み付き分岐結果値算出手段により算出された重み付き分岐結果を前記保持手段に保持させ、
前記ステージ0において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記重み付き分岐結果を累算させる
請求項3に記載の情報処理装置。

【請求項7】
前記重みテーブルのインデックスに含まれる複数の多重化アドレスに対応する過去の複数の分岐命令は、前記各重みテーブル間で重複が少なくなるように決定されたものである
請求項1から6のいずれか1項に記載の情報処理装置。

【請求項8】
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令における前記多重化アドレスからインデックスが生成されたものであり、
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令における前記多重化アドレスからインデックスが生成されたものである
請求項7に記載の情報処理装置。

【請求項9】
前記予測値算出手段により算出された前記予測値と実際の分岐結果の一致不一致に基づいて、前記重みテーブルの重みの値を更新する学習処理を行う学習手段をさらに備える
請求項1から8のいずれか1項に記載の情報処理装置。

【請求項10】
前記学習手段は、さらに、前記多重化アドレスに反映されたローカル履歴を、前記実際の分岐結果に置換する
請求項9に記載の情報処理装置。

【請求項11】
予測対象分岐命令のターゲットアドレスの多重化アドレスに対応づけられ閾値を保持した第2の重みテーブルと、
前記ターゲットアドレスの多重化アドレスで前記第2の重みテーブルを索引することによって閾値を算出する閾値算出手段を備え、
前記予測値算出手段は、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、前記予測値を算出する
請求項1から10のいずれか1項に記載の情報処理装置。

【請求項12】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備える情報処理装置の情報処理方法において、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成し、
前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択し、
前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出し、
最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算し、
少なくとも累算された前記重み付き分岐結果値を用いて、予測値を算出する
情報処理方法。

【請求項13】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備えるコンピュータ
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、
前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、
前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、
前記重み付き分岐結果値算出手段により最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、
少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段と
して機能させるプログラム。
産業区分
  • 演算制御装置
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2007199159thum.jpg
出願権利状態 権利存続中


PAGE TOP

close
close
close
close
close
close
close