4P{07

トレース・ドリブン・シミ ュレーシ ョンによる分岐予測機構の検討中村 友洋y ,吉瀬 謙二y ,金指 和幸z ,y 東京大学工学部,

田中 英彦yz 富士通 (株)を抽出し処理を続けるには、分岐予測機構の強化が必須
1

はじめにとなっている。本稿では多く使われている分岐履歴情報

半導体技術とプロセッサアーキテクチャの改良によってをもとにした分岐予測機構の性能を、分岐履歴情報を保マイクロプロセッサの性能は飛躍的に進歩している。特存するエントリ数などをパラメータとして評価する。にスーパーパイプライン構造は処理を複数のステージに分けることで実効的な処理のスループットを上げ、スーパースカラ構造は命令レベルの並列性を抽出して実行する能力を持ち、最近の主流となっている。これらの技術

主な分岐予測機構

3

最近のマイクロプロセッサで採用されている主な分岐予測機構としては次のようなものがある。

は一連の命令列を連続もしくは同時に実行するために、 1. 常に分岐成立, 後方分岐,分岐命令のような制御フローの変更を行なう処理によっ

静的な分岐予測 後方分岐はループによる後方分岐て命令のストールが生じることがあり、特に複数命令をの成功率が高いことを利用同時に実行するスーパースカラ構造では大きなペナル(2.

分岐履歴情報に基づく予測ティとなる。そこで分岐命令の結果を予測する機構 分), PA-RISC などで採用

岐予測機構 を採り入れてペナルティの軽減を行なうことが常識となってきている。本稿では最近のマイクロプ
ロセッサで採用されている分岐予測機構をトレース・ド

1〜3{bit 程度の分岐履歴を各分岐命令に対して保存して動的に予測を行なう, PowerPC604 で採用されている 2{bit の分岐履歴は図 1のような情報をもつ, Pentium, Alpha, PowerPC などでも採用

リブン・シミュレーションにより定量的に評価する。
2

非分岐と予測

目的と背景

分岐と予測

分岐と判明するとスーパーパイプライン構造や、スーパースカラ構造をもつ場合には、分岐命令などによる制御フローの変更

<00>
強い
非分岐状態

によって、大きなペナルティが課せられることがあるた
め、分岐予測機構を設け、正しい制御フローを予測し、

<01>
弱い
非分岐状態

<10>
弱い
分岐状態<11>強い分岐状態非分岐と判明するとこのペナルティを軽減している。いくつかのプロセッサ

1: PowerPC604 の分岐履歴情報
プロセッサ
ペナルティ
本 稿 で は 、PowerPC604 の 分 岐 予 測 機 構 を 基 本
サイクル 命令数と し て 図 2のよ うな 分 岐 予 測機 構 の 評 価 を 行 な う。
Alpha 21064
48BTAC(Branch Target Address Cache) は分岐命令のPentium
36PowerPC604
312アド レスと分岐先を保存する。BTAC 中にある分岐命令は分岐成立と予測される。次に BAC(Branch Always
表 1: 分岐予測ミスによるペナルティ
Correction) では無条件分岐命令の予測を修正する。最ら分かるように、スーパーパイプライン構造のために、
1 つの分岐予測ミスによって複数サイクルにわたるパイ 後に BHT(Branch History Table) では分岐履歴を保存
11

図におけるペナルティの大きさを表 にまとめる。 表 かプライン・ハザード が生じ、さらに複数命令を同時に発行するためにペナルティを命令数に換算すると、さらにし、これに基づいて予測を行なう。
4

分岐予測機構シミ ュレータ2〜4 倍となってしまう。分岐命令は全実行コード の 10
実装方法〜30% を占めるといわれており、命令レベルの並列性 本研究では、SPARC シミュレータを用いてトレースデー
4.1

A Study of Branch Prediction Strategies using Trace タを取り、これを分岐予測機構のシミュレータに通すこ
Driven Simulationとで評価を行った。コード は SPARC の命令セットでTomohiro NAKAMURAy , Kenji KISEy , Kazuhiro あるが、シミュレート対象としたプログラムは SPARC
KANAZASHIz, Hidehiko TANAKAy,チップ用の最適化を施さずにコンパイルした。分岐予測y University of Tokyo, Department of Engineering, 機構シミュレータは、図 2の構成を基本としたが、BTACz Fujitsu LTD.のエントリ数は 64 、BHT の履歴情報は 2{bit 、BHT のBTAC

No

add/
deleteadd

BranchAlways?

BHT エントリ数と BHT へのヒット率の関係を示したものである。BAC の制御がある場合は、無条件分岐命令が BHT を使わないので、見かけ上 BHT へのヒット

Yes

率が低下するが、無条件分岐命令をヒットしたものと扱

hit?

BAC の制御がない場合に比べて全体的なヒット率があがる。これも BAC の利用により BHT エントリがNo

うと

Yes

BHT

BACより有効に活用されるためである。
10095

add

分岐予測成功率(%)

hit?

prediction

2: 3 ステージ分岐予測機構
エントリ数は 1〜4096 の範囲で可変とした。また BTACや BHT のエントリが溢れた場合の置き換え戦略は、シミュレートを簡単にするため、疑似 FIFO1 とした。
図858065501

図(100.00%)

521,129( 22.03%)
90,183( 14.18%)
131,936( 21.21%)
134,974( 20.22%)
224,124( 10.59%)

無条件分岐

2,158
( 2.25%)18,712( 2.94%)8,990( 1.45%)8,978( 1.34%)56,073( 2.65%)

2: サンプルプログラムの概要

10000

3: BHT エントリ数{分岐予測成功率

60
50
40
30
20

AAAA
AAA
AAA
AA
AAAAAAAAAAAAAAAAA AAAAAAAAAAAAA AAAAAAAAAAAAAAAAA
A
AAAA
AAAA
AAA
AAA
AA
AAAA
AAAA
A
AAAA
A
AAAA
AAAA
AAAA
AAAAAA
AA
AAA
AAAA
AAAA
AAA
AAAAAA
AAA
AAA
AAA
AAA
AAA
AAAA
AAAA
AAA
AAAAAAAA
AAAA
AAAA
A AA
AA
AAAA
AAA
AAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAA
AAAAAAAAAAAA
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAA
AA
AAAA
AAAA
AAAA
〃(含無条件分岐)
AAAAAAAAAAAAAAAAAAAAAAAA
AAAA
AAAA
AAAA
AAAA
AAAAAAAAAAAAAAAA
AAAA

BAC有り
BAC無し

100110100

1000

10000

BHTエントリ数

図64: BHT エントリ数{BHT ヒット率

おわりにBHT エントリ数が 64 前後で分岐予測成功率に大きな差評価

3

BHTヒット率(%)

70

calc
95,920(100.00%)
compress
636,151(100.00%)
dhrystone 622,019(100.00%)
jhd
667,674(100.00%)
whetstone 2,116,651

1000

90

して使用したプログラムは次の通り。
分岐命令数10010080

実行命令数

10BHTエントリ数て分岐予測機構の動作をトレースした。今回サンプルと表

BAC無し

7055

SPARC シミュレータから得られるトレースデータをもとに、実際に行われた分岐命令 (Bicc, CALL, CBccc,FBfcc, JMPL, RETT, Ticc) についての分岐状況を抽出し、4.1節で述べた分岐予測機構シミュレータを使っ
名称

BAC有り

7560

実験内容

4.290

1 4096 の範囲における BHT エントリ数と分 があることを示した。この値はプログラムによって前後するが、少なくとも BHT エントリが不足した場合には

図 は、 〜岐予測成功率の関係を示したものである。グラフは各サBAC の かなりのペナルティがかかるといえる。シミュレータでは他にも多くのデータが得られており、バッファ置換戦ンプルプログラムの結果の平均をとっており、制御がある場合とない場合を示している。プログラムのサイズにもよるが、ほぼBHT エントリ数が 32〜96 の 略の評価をはじめとする各種解析が今後の課題である。

付近で分岐予測成功率が大きく上がることが分かる。つ
まりこれ以下の謝辞

BHT エントリ数では、履歴情報が有効 本研究の一部は文部省科学研究費 (一般研究 (B) 課題番号に活用される前にエントリの置換が行なわれる確率が高07458052「大規模データパスプロセッサの研究」) による。

BAC の制御が無い場合 参考文献

いということが分かる。また、は、有る場合に比べていずれのエントリ数においても性BAC 制御が無いと BHTに無条件分岐も登録することになり、それだけ BHT エントリが有効に活用されにくくなるためである。図 4は、能が低くなっているが、これは1 FAFO(First Assign First Out):エントリが割り当てられた順に置き換える。同一エントリの更新による再割り当ては考えない。

[1] Scott A. Mahlke, Richard E. Hank, Roger A. Bringmann and John C. Gyllenhaal,\Characterizing theImpact of Predicated Execution on Branch Prediction", 27th International Symposium on Microarchitecture, pp.217-227,1994[2] \PowerPCTM 604 RISC Microprocessor TechnicalSummary", Motorola Inc., 1994