Top > Search of Japanese Patents > (In Japanese)情報処理装置および方法、プログラム、並びに記録媒体

(In Japanese)情報処理装置および方法、プログラム、並びに記録媒体

Patent code P110004864
File No. 05-061JP01
Posted date Aug 18, 2011
Application number P2008-526684
Patent number P5167489
Date of filing Feb 6, 2007
Date of registration Jan 11, 2013
International application number JP2007051965
International publication number WO2008012957
Date of international filing Feb 6, 2007
Date of international publication Jan 31, 2008
Priority data
  • P2006-203106 (Jul 26, 2006) JP
Inventor
  • (In Japanese)二ノ宮 康之
  • (In Japanese)阿部 公輝
Applicant
  • (In Japanese)国立大学法人電気通信大学
Title (In Japanese)情報処理装置および方法、プログラム、並びに記録媒体
Abstract (In Japanese)予測に必要な時間を抑制するとともに分岐予測の精度を向上させることができる情報処理装置および方法、プログラム、並びに記録媒体に関する。
グローバル履歴84に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプラインを、ステージの最終段を除いて、M個ずつ最新の履歴から順に同一ステージで同時並列的に処理するn個のグループに分割することにより、n個の長さを有しステージ毎に順次処理を行う鎖がM本形成されてなるパイプライン構造において、重み選択部61は、重みテーブル82より重みを選択して読み出し、重み付き分岐結果値累算部62は、その重みの値を用いて、重み付き分岐結果値を算出し、その累算値を求め、予測値算出部73は、その重み付き分岐結果累算値の総和と、閾値算出部72により算出された閾値とを用いて予測値を算出する。本発明は、分岐予測器に適用することができる。
Outline of related art and contending technology (In Japanese)

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

そこで、ニューラルネットワークの一種であるパーセプトロンを応用したパーセプトロン分岐予測器が注目された。

例えば、図1に示されるように、予測すべき分岐命令のアドレスであるターゲットアドレスとプログラムの分岐結果を時系列に並べたグローバル履歴(GH)を入力として用いるグローバルパーセプトロン分岐予測器(Global Perceptron)があった(例えば、特許文献1参照)。

この分岐予測器の場合、図1に示されるように、まず、ターゲットアドレス(TA)の下位ビットをインデックスとして重みテーブルより重みベクトルを読み出す。この重みベクトルは、分岐結果に対して事前になされた分岐予測の正否に応じて付与され、各要素がグローバル履歴(GH)の特定の場所と1対1に対応付けされている。グローバル履歴(GH)の各要素は、その値が「1」であれば分岐成立であり、値が「-1」であれば分岐不成立であることを表している。読み出された重みベクトル(重み群)の各要素とグローバル履歴(GH)を1つずつ乗算することにより重み付き分岐結果値を求め、この重み付き分岐結果値の総和の値が正であれば分岐成立(Taken)と予測され、値が負であれば分岐不成立(Not Taken)と予測される。このグローバルパーセプトロン分岐予測器を式で表すと、式(1)のように表すことができる。

【数1】
(省略)

なお、式(1)において、Wiは読み出された重みを示し、Xi(1≦i≦n)は、各重みの要素に対応するグローバル履歴(GH)の要素を示す。また、WOは、分岐成立、不成立を区別するための閾値であり、重みベクトルとともに重みテーブルより読み出される。

求められたyの値が正ならば分岐成立として値「1」が出力され、yの値が負ならば分岐不成立として値「-1(または0)」が出力される。

この重みWiの更新規則は分岐結果をt∈{1,-1}とすると基本的に次の式(2)によって表される。

【数2】
(省略)

なお、式(2)において、係数αの値は通常の場合「1」である。

このようなグローバルパーセプトロン分岐予測器は、gshare分岐予測器などの予測器と比べて予測精度は高いが、予測に必要となる計算量が多いため、ターゲットアドレスが入力されてから分岐予測結果が得られるまでのレイテンシが非常に大きく、CPU(Central Processing Unit)等への実装は事実上不可能であった。

また、図1に示されるグローバルパーセプトロン分岐予測器では、グローバル履歴(GH)を用いるように説明したが、グローバル履歴の代わりに分岐命令毎の分岐結果を並べたローカル履歴を用いたものも知られている。図4は、その場合のローカルパーセプトロン分岐予測器の例を示す図である。このようにローカル履歴(LHT(Local History Table))より読み出した分岐結果(LH)を用いることにより、ローカルパーセプトロン分岐予測器は、グローバルパーセプトロン分岐予測器よりも予測精度を向上させることができる。ただし、このローカルパーセプトロン分岐予測器の場合も、グローバルパーセプトロン分岐予測器の場合と同様に、予測に必要となる計算量が多いため、ターゲットアドレスが入力されてから分岐予測結果が得られるまでのレイテンシが非常に大きく、CPU等への実装は事実上不可能であった。

レイテンシを隠蔽する工夫がなされたパーセプトロン分岐予測器としては、グローバル履歴を履歴順に分割して履歴が古い方から順次処理を行うパイプライン構造を有するパスベースドパーセプトロン分岐予測器(Path-Based Perceptron)があった。パスベースドパーセプトロン分岐予測器では、図2に示されるように、パイプラインの最終段ステージ以外に割り当てられた重みテーブル(テーブル1乃至テーブルN)より重みを読み出すためのインデックスにターゲットアドレスではなく、過去に実行された分岐命令のアドレスを用い、最終段ステージにおいて重みテーブル(テーブル0)より閾値を読み出すためにのみターゲットアドレスを用いるようになされている。つまり、インデックスに使用するターゲットアドレスを必要最低限に抑えることで、ターゲットアドレスが入力されるより前から、パイプライン化による複数の予測計算を同時に行うことが可能である。

しかしながら、この場合、過去のアドレスを用いて予測を行うため、プログラムが辿るアドレスが変化した場合には、無関係な値によって予測計算がなされてしまうことになる。このため、履歴長を伸ばしても予測精度の向上度はグローバルパーセプトロン分岐予測器に及ばない恐れがあった。

また、パーセプトロン分岐予測器として他に、パイプライン化されたパストレース分岐予測器(Pipelined PTBP(Path Trace Branch Predictor))が考えられた。パイプラインドPTBP(Pipelined PTBP)は、前記最終段のステージを除いて、前記パイプラインを履歴順に所定長を有する複数の鎖に分割し、前記各鎖を前記ステージ毎に順次処理することにより、前記鎖の本数分の処理を同時並列的に行うパイプライン構造を有しており、鎖の長さ(図3において横方向の段数)をNとすると1鎖目(図3中、上の鎖)のn(n≦N)番目のグローバル履歴に対応する重みは、過去に実行された分岐命令のアドレスを並べた実行パス履歴のn番目のアドレス(読み出し時はその時点で取得可能な最新のアドレス(A[0]))を重み選択のインデックスとし、2鎖目のn+N番目のグローバル履歴に対応する重みはn番目のアドレス(A[0])とn+N番目のアドレス(A[N])をローテートして排他的論理和を取った値をインデックスとし、3鎖目のn+2N番目のグローバル履歴に対応する重みはn番目のアドレス(A[0])とn+N番目のアドレス(A[N])とn+2N番目のアドレス(A[2N])をローテートして排他的論理和を取った値をインデックスとして重みを読み出す。ここで、ターゲットアドレスに代えて最新のアドレスA〔0〕を用いているのは、プログラムは局所的なループ構造を持つことが多いため、ターゲットアドレスの数個程度前に処理された分岐命令アドレスであればターゲットアドレスの情報を含んでいる可能性が高いためである。パイプラインドPTBPは、このようにN個毎にアドレス履歴の排他的論理和を取り、それをインデックスとして読み出した重みにより、各鎖のステージ毎に割り当てられた各分岐結果に対して重み付けをした重み付き分岐結果値を鎖毎に各ステージにおいて順次累算する。そして、最終段ステージにおいて、鎖毎に累算された重み付き分岐結果値の総和を算出し、その総和とターゲットアドレスをインデックスとしてテーブル0より読み出された閾値としての重みとを加算して分岐予測を行う。このようにすることにより、パイプラインドPTBPは、ターゲットの分岐命令までに辿ったパス情報を予測に反映することができ、予測精度を向上させることができた。

しかしながら、プログラム中にはグローバルな分岐履歴の一部が異なっても同じふるまいをする分岐命令が多数存在する。このような場合、パイプラインドPTBPのパイプライン構造では、予測に関係の無いアドレス履歴によってテーブルの読み出し位置の一部が変化し予測に悪影響を与える恐れがあった。パーセプトロン分岐予測器では、この予測に関係の無いアドレス履歴によって生成されるインデックスで読み出される重みは予測に相関のある重みと異なるものとなってしまう。PTBPはその構造上、1つのアドレス履歴が従来のパーセプトロンに比べて多くの重みのインデックスに関わることになり、この問題が及ぼすPTBPへの影響は他の分岐予測器に比較して大きくなってしまう。その結果として予測精度の向上を妨げてしまう恐れがあった。
【特許文献】

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

Field of industrial application (In Japanese)

本発明は、情報処理装置および方法、プログラム、並びに記録媒体に関し、特に、予測に必要な時間を抑制するとともに分岐予測の精度を向上させ、プロセッサのプログラム実行速度を向上させることができるようにした情報処理装置および方法、プログラム、並びに記録媒体に関する。

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

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

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

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

【請求項5】
 
前記閾値算出手段は、前記多重化アドレス生成手段により生成された前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択する代わりに、前記最終段のステージに割り当てられた前記重みテーブルから、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスに対応する重みを閾値の候補として全て特定し、前記ローカル履歴を用いて全候補の中から前記閾値を選択し、
前記重み付き分岐結果値累算手段は、最終段の1つ前のステージの1本目の鎖において、前記重み選択手段により選択された前記重みにより、1つ前の分岐命令に対する予測値に対して重み付けを行うことによって重み付き分岐結果値を取得する
請求項1乃至4のいずれかに記載の情報処理装置。

【請求項6】
 
前記閾値算出手段は、前記多重化アドレス生成手段により生成された前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択する代わりに、前記最終段のステージに割り当てられた前記重みテーブルから、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスに対応する重みを閾値の候補として全て特定し、前記候補の特定と並行して前記最新のアドレスに対応する前記ローカル履歴を特定し、前記ローカル履歴を用いて全候補の中から前記閾値を選択する
請求項1乃至5のいずれかに記載の情報処理装置。

【請求項7】
 
前記予測値算出手段により算出された前記予測値が分岐命令の実行結果と一致するか否か、並びに、前記予測値の信頼性に応じて、前記重みテーブルを更新する学習処理を行う学習処理部をさらに備える
請求項1乃至6のいずれかに記載の情報処理装置。

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

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

【請求項10】
 
請求項9に記載のプログラムが記録されている記録媒体。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2008526684thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close