第 4 章 投機対象パスの複数化
4.3 パス履歴情報の詳細化
および#2パス以外のパスを予測の対象とすることは，予測成功率を向上させるに あたって非常に有望であると言える．
HR
1 1 1 1 0 0 0 0
1 0 result of
next path (#3path) 1 1 0 0 0 0 1 0
2-bit shift-left
図 4.4: パス履歴レジスタの更新の様子
においては，#3パスが実行された場合の例を示しており，#3パスに対応した10 をパス履歴レジスタに加算している．
4.3.1 GAg 分岐予測ベースのパス予測器
本節では，詳細化したパス予測器のハードウェア構成を検討する．既に述べた とおり，本研究における提案手法であるNビットに詳細化したパス予測器におい ても，パス履歴レジスタに記録するのは0/1のビット列であり，従来のパス予測 器と大きくハードウェアを変更する必要はない．本研究では，まず，従来パス予 測器と同様の，2レベル適応型分岐予測機構[25]をベースとしたパス予測器につい て検討する．
2レベル適応型分岐予測機構には，分岐履歴レジスタと分岐PHTを実装する方 法により，4種類の構成 (GAg，GAp，PAg，PAp) が存在する[25]．GAp，PAg，
PApでは，複数の分岐履歴レジスタ，または，複数分岐PHT，あるいはその両方 を持つ．本研究では，1つの履歴レジスタと1つのPHTを持つGAg分岐予測機構 をベースとして，パス実行履歴情報を詳細化したパス予測機構の構成を検討する．
GAgをベースとすることにより，パス予測機構に必要なメモリ資源量が少なく済 むという利点がある．
前節で説明したとおり，パス実行履歴情報を詳細化したパス予測機構において も，パス履歴レジスタは0/1のビット列を記録するため，従来の構成を変更する 必要はない．一方，1つのパスPHTによって複数のパスの実行パターンを学習さ せる場合，パスごとにテーブルの異なるインデックスへアクセスするか，あるい は，1つのテーブルのインデックスがパスごとに複数の状態を保持できるようにす る必要がある．これらの方法の実現には複雑なハードウェア回路の追加が必要と
HR
10 00000000 00000001 11111111
#1path PHT
01
#2path PHT
01
#3path PHT
00 other paths PHT 0 0 0 0 0 0 0 1
00000000 00000001 11111111
00000000 00000001 11111111 00000000
00000001 11111111
#1path comparator
図 4.5: GAgベースのパス予測器
なり，予測にかかる時間が増大してしまう可能性がある．そこで本研究では，パ スごとにパスPHTを分けるパス予測機構を提案する．パスごとに異なるテーブル にアクセスすることにより，パス間で実行履歴の学習結果が衝突することがない．
図4.5に，パス実行履歴情報を2ビットに詳細化し，8ビット長のパス履歴レジ スタを持つ，GAgベースのパス予測器を示す．2ビットのパス実行履歴情報によ り，3つのパス (#1パス，#2パス，#3パス) とその他のパスを区別することが でき，4つのパスPHTを持つ．予測を行う際には，パス履歴レジスタをインデッ クスとして，各テーブルへアクセスを行う．そして，テーブルに記録されたカウ ンタの値が最も大きいテーブルを選び，そのテーブルに対応したパスを予測結果 として出力する．図では，#1パスのテーブルの値が最も大きいため，#1パスを 予測している．複数のテーブルにおいてカウンタの値が等しい場合には，実行割 合の高いパスを優先した選択を行う．すなわち，#1パスのテーブルと#2パスの テーブルの値が等しかった場合，#1パスを予測する．
図4.6に，#1パスが実行されたときのパスPHTの更新の様子を示す．パスの実 行が確定した場合，パス履歴レジスタをインデックスとしてテーブルにアクセス を行う．そして，実行されたパスに対応したテーブルのカウンタをインクリメン
HR
1 1 1 1 0 0 0 0
11110000
#1path PHT
#2path PHT
#3path PHT
other paths PHT 10 11 11110000
11110000
11110000 01 00 01 00
01 00
図 4.6: #1パスが実行されたときのパスPHTの更新
strongly
#1-path / 11
weakly
#1-path / 10
weakly not #1-path
/ 01
strongly not #1-path
/ 00
#1-path executed
other path executed
#1-path executed
#1-path executed
#1-path executed
other path executed
other path executed
other path executed
図 4.7: #1パスのパスPHTにおける2ビット飽和カウンタの状態遷移
トし，それ以外のパスに対応したテーブルのカウンタをデクリメントする．図4.7 に，#1パスのパスPHTにおける2ビット飽和カウンタの状態遷移を示す．なお，
‘その他のパスの実行’は，#1パス以外のパスの実行を意味しており，00に対応づ
けられた‘その他のパス’とは含めるパスが異なる．図4.6では，実行された#1パ スのテーブルのカウンタをインクリメントし，それ以外のパスのテーブルのカウ ンタをデクリメントしている．その後，パス履歴レジスタの更新を行う (図4.4で 説明)．
4.3.2 Gshare ベースのパス予測器
GAgベースのパス予測器では，1つのパス履歴レジスタにより予測を行う．プ ログラムを並列実行するにあたり，並列化の対象とするループがただ1つである 場合には問題は生じないが，複数のループを並列実行する場合には，パスPHTに
HR
1 1 1 1 0 0 0 0
loop head address
1 1 1 0 0 0 0 0 0 0 0 0
LSB XOR
to PHTs
図 4.8: Gshareベースのパス予測器によるパスPHTへのアクセス
おいてループごとの学習結果が衝突する可能性がある．この問題に対して，本研 究では学習結果の衝突を抑制するため，Gshare分岐予測器の仕組みをパス予測機 構に導入する．Gshare分岐予測器では，分岐履歴レジスタと，実行された分岐命 令のアドレスのXOR (排他的論理和) を取り，PHTへのアクセスを行う．これに より，PHTの利用効率を向上し，学習の衝突を抑止することができる．
図4.8にGshareベースのパス予測器を示す．パス実行履歴情報は2ビット，パ
ス履歴レジスタ長は8ビットである．本パス予測器では，分岐命令のアドレスの 代わりとして，投機実行対象ループにおける先頭アドレス (一番目の命令のアド レス) を使用してPHTへのアクセスを行う．固定長の命令セットアーキテクチャ では，下位数ビットは常に0となるため，それらの下位ビットを除いたアドレス (図では8ビット分) とパス履歴レジスタとのXORを取り，PHTへのアクセスを 行う．ループの先頭アドレスとのXORを取ることにより，パス履歴レジスタの値 が同一であっても，異なるループを実行している場合には異なるインデックスに アクセスすることになる．このため，PHTの使用効率が向上し，異なるループ間 における学習結果の衝突を抑制することができる．
4.3.3 ハッシュによる PHT へのアクセス
従来の2パス限定投機方式におけるパス予測器と，パス実行履歴情報を詳細化 したパス予測器において，同一のビット長を持った履歴レジスタを持った場合に ついて比較する．例えば，8ビットのパス履歴レジスタを持っていた場合，従来の パス予測器では8回分の実行パスの履歴を記録できることになる．一方，2ビット の実行履歴情報を用いたパス予測器では，その半分である4回分の実行パスの履 歴を記録することができる．
HR
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 XOR
to PHTs
図 4.9: ハッシュインデックスを用いたPHTへのアクセス
一般に，実行履歴情報を多く持っていれば，すなわち履歴レジスタ長が長けれ ば，高い予測性能を達成することができる．しかしながら，本提案パス予測器に おいてはパスごとにPHTを用意しているため，履歴レジスタ長を長大にした際に は必要な記憶容量が膨大になる．そこで本研究では，ビット長が2N であるパス 履歴レジスタから，Nビットのインデックスを持つPHTへアクセスできるような ハッシュインデックス法を導入する．
図4.9にパス履歴レジスタ長が16ビットである，2ビットの実行履歴情報により 詳細化されたパス予測器によるハッシュインデックス法を示す．本手法では，非 常に簡単なハッシュとして，パス履歴レジスタの上位半分のビットと下位半分の ビットのXORを取る．図においては，パス履歴レジスタの上位8ビットと下位8 ビットのXORを取り，その演算結果をインデックスとしてPHTにアクセスして いる．本手法により，PHTの記憶容量を増大させずに，記録可能なパス実行履歴 回数を増大することができる．また，本手法はGAgベースおよびGshareベース のパス予測機構と直交する手法であり，どちらのパス予測器に対しても適用する ことが可能である．