プログラム解析に基づく分岐予測機構に関する問題点の検討

3K{5中村 友洋y ,吉瀬 謙二y ,金指 和幸z ,z 富士通 (株)y 東京大学工学部,

1

はじめに

田中 英彦yre-order バッファ数

プロセッサ

56401616PA-8000
Pentium ProK5PowerPC620

半導体技術の進歩により単一のプロセッサに数多くの機能ユニットを組み込めるようになってきており、スーパースカラ・プロセッサが広く使われるようになった。

同時命令発行数4554

1: 最近のマイクロプロセッサにおける命令レベル並

しかしながらスーパースカラ・プロセッサはその構成

表上、複数の有効な命令が同時に実行できてはじめてその列性利用のためのハード ウェア・サイズ機能を余すところなく発揮するものであって、分岐命令バッファリングするため、分岐命令の出現頻度をが多く含まれる汎用プログラムでは必ずしもその性能を仮定すると約 命令が分岐命令であることになる。分岐

十分に発揮できているとはいない。このような問題点を20%と3予測成功率が 90%であると仮定した場合、この 16 命令隠蔽するため、これまでに数多くの分岐予測機構が提案がすべて正しいパスからフェッチされたものである確率され実装されてきたが、その結果既存の分岐予測機構のは枠組では性能限界が見えてきた。本研究では分岐命令に令を同時にバッファリングするため、分岐命令の出現頻72.9% である。ところが PA-8000 の場合最大 56 命
11

関わる様々な特性を調査・解析し、いま一度分岐命令の度が同じとすると、約命令が分岐命令で、同様の確扱い方の基本から検討すべくプログラム解析を行ない、 率で正しいパスをフェッチするには、もの高確率
現状の分岐予測機構における問題点に関する考察を行 で分岐予測を成功させなければならなくなる。このよう97.2%なった。に命令レベルの並列性を利用しようとすると、必ず分岐2目的と背景スーパースカラ・プロセッサなどのように命令レベルの命令によるペナルティを考慮しなければならなくなる。

並列性を利用する場合には、その性能を十分活かすたを使った分岐予測機構について、プログラム解析に基づ

本研究ではこれまでに提案・実装されてきた分岐履歴

めに命令実行ユニットに意味のある命令を連続的に供いて分岐命令の特性に関するデータを収集することで、給することが重要である。しかし一般的にプログラム・ その問題点を調査した。
〜程度の割合で分岐命令が含まれ 3 分岐履歴に基づいた分岐予測機構
コード 中には10 30%ているため、分岐先を正しく予測し、その予測に従って最近のマイクロプロセッサで採用されている分岐予測機命令をフェッチし続けなければならない。よって分岐先構のほとんどは分岐履歴に基づいて予測を行なうものの予測に失敗するとその分岐命令にまで遡って正しいパである。通常 〜スをフェッチし直さなければならない。このために実行次回の分岐方向を予測するものである。

1 3{bit 程度の分岐履歴を動的に保存し、ユニットに命令が供給できなくなり、パイプライン・ハザードが起こる。特にout-of-order 機構などをもった最非分岐と予測

新のマイクロプロセッサでは、数十の命令をバッファリ<00>
強い非分岐状態ングするために、このペナルティーが増大する傾向にある。バッファリング・サイズの上限を決定する要因のつが分岐予測性能にあるといえる。

1

表 は最近のマイクロプロセッサがめに備える分岐と予測分岐と判明すると

1<01>
弱い非分岐状態<10>
弱い分岐状態<11>
強い分岐状態

非分岐と判明すると

1: PowerPC604/620 の分岐履歴情報
例えば PowerPC604/620 の場合、図 1のような 2{bitout-of-order のた図

re-order バッファのサイズと同時発行できre-order バッファ の分岐履歴ビットを用いて予測を行なう。

る命令数を示したものである。一般にのサイズが大きくなれば命令レベルの並列性を抽出しやすくなるが、分岐予測性能によるペナルティが高く

44.1

分岐命令特性プログラム解析の概要

PowerPC620 では最大 16 命令を同時に 本研究では SPARC シミュレータを用いてプログラム解なる。例えば、

A Study of Problem of Branch Prediction Strategies using
Program Analysis

析を行なった。実験に使用したサンプル・プログラムは

2

表 の通りである。

Tomohiro NAKAMURAy , Kenji KISEy , Kazuhiro
表 から、分岐命令が程度というかなり高い確率
KANAZASHIz , Hidehiko TANAKAy ,y University of Tokyo, Department of Engineering, z Fujitsu で存在することが分かる。また、その中でも条件分岐のLTD.
程度が条件占める割合が相当に高く、分岐命令の220%70%2:(100.00%)

分岐命令数7,140( 21.22%)
393,473( 13.12%)436,841( 21.08%)
544,837( 18.16%)
22,859( 22.55%)
135,140( 20.22%)

条件分岐数5,207( 15.48%)
278,099( 9.27%)289,135( 13.95%)
386,713( 12.89%)
18,159( 17.92%)
111,673( 16.71%)表
サンプルプログラムの概要
分岐であることも分かる。つまり分岐制御、とりわけ条Seccess Rate(%)

実行命令数747270686664626058

calc

dhrystone

espresso

grep

jhd

図

201-1000

100110000

2: 初期分岐予測性能

4035All

Bicc

3025201510501

件分岐の制御がマイクロプロセッサの高性能化には欠か

2

34-10

11-100101-200

10001-

Loop Countせないといえる。
4.2

compress

program

Executed Ratio(%)

名称

calc
33,647(100.00%)
compress 3,000,000(100.00%)
dhrystone 2,072,456(100.00%)
espresso 3,000,000(100.00%)
grep
101,354(100.00%)
jhd
668,186

図

分岐予測ミス原因

3: 分岐命令の繰り返し回数頻度

BHT(Branch 表 3は後方への分岐のパターンに関する偏りを示してHistory Table) のサイズを十分に大きくしても 90%程 いる。ここで集中度とは、1 つの後方分岐命令が同じ回分岐履歴を利用した分岐予測機構の性能は度で飽和してしまう。この原因として主に「初期分岐予数だけループを回ってから抜け出る確率で、例えばある1 つの後方分岐命令が、「3 回ループを回って (3 回分岐分岐ミスとは、履歴情報が揃っていないような初めて実 成立) から抜け出る (1 回分岐不成立) 」というパターン行する分岐に対する予測ミスである。構造上ミスとは、 を 9 回繰り返し、その後で「 1 回もループを回らずに抜分岐予測機構の構造上の問題 (限界) によって起こる予 け出る」という場合には、3 回ループを回るという可能測ミスのことである。後者には履歴情報の不足によるミ 性が最も高く、その集中度は 90%となる。よって集中度2測ミス」、「構造上予測ミス」の つが考えられる。初期スや、履歴情報を保存するためのエントリ不足によるもが高いほどループを回る回数が毎回一定である可能性がのなどが含まれる。本稿では、初期分岐、後方への条件高いといえる。表 によれば、いずれのプログラムでもれらのミスの頻度を調査し、その対策を考える。

岐に関してはこのパターンをつかみ、予測することで大3分岐パターンをプログラム解析により求めることで、こ この集中度が 97〜99%となっており、後方への条件分4.3

初期分岐予測ミス幅な性能改善が可能である。

2 PowerPC604 の分岐予測機構を用いて初期分岐の calc compress dhrystone espresso grep jhd
98.75
99.99
99.94
98.62
97.61 99.21
予測を行なった場合の予測成功率を表している。Pow表 3: 後方分岐のパターン集中度 (%)
erPC604 の分岐予測機構では分岐履歴がない場合には分おわりに岐不成立と予測する (ただし無条件分岐は成立と予測すプログラム解析に基づいて、初期分岐予測、後方への条る) 。分岐全体に対する分岐予測成功率はおよそ 90%で件分岐予測に関する考察を行なった。特に後方への条件あるから、明らかに初期分岐に関しては分岐予測成功率
分岐はループ終端などに多く見られ、表 3に示した特性が低い。しかし図 3から分かるように十分 BHT エント
図 は5リがあれば初期分岐に相当する分岐は非常に少なくなり、性能への影響は小さいと考える。基本的に初期分岐は静的な分岐予測を行なうことで予測成功率をあげるのが妥当な対策である。
4.4

後方への条件分岐パターン

ループの終端には分岐命令が存在する。通常この分岐命令は後方への分岐であり、複数回分岐が成立しループを回った後で分岐が不成立となりループから抜け出る。このような分岐をPowerPC604/620 のような 2{bit の分

岐履歴情報をもとにして正しく予測することは困難である。そこでまずこのような後方への条件分岐の分岐パターンを調べることでその制御方法を考える。

を利用して分岐予測を行なえば、かなりの性能向上が見込める。これを効率良く実現するためのハード ウェア、ならびにソフトウェア支援の検討が今後の課題である。
謝辞
本研究の一部は文部省科学研究費 (一般研究 (B) 課題番号07458052「大規模データパスプロセッサの研究」) による。
参考文献

[1] Po-Yung Chang, Yale Patt,\Branch Classi cation:
A New Mechanism for Improving Branch Predictor
Performance", 27th International Symposium on Microarchitecture, pp.22-31,1994[2] 中村友洋, 吉瀬謙二, 金指和幸, 田中英彦, \トレース・ド
リブン・シミュレーションによる分岐予測機構の検討",
第 51 回情報処理学会全国大会, pp.6-13{6-14, 1995