4F{2

明示的な分岐制御の可能性の検討および制御機構の提案
中村 友洋,

吉瀬 謙二,
辻 秀典,
東京大学工学部

田中 英彦

4 8数系アプ リケーションでは 〜 命令程度と小さいためはじめに命令レベルの並列性を利用するにあたって、分岐制御1が重要となる。既存のプロセッサにおいても、多くのものがハード ウェアによる分岐予測機構を設けて、分岐命令によるオーバーヘッドの削減を行なっている。ところが、満足できる性能まで達していないにも関わらず、その大きな向上は望めなくなっている。そのである。つまり、数十命令を解析して命令レベルの並列性を抽出するには、数個〜十数個の分岐予測を正しくおこなう必要がある。ところが、現在の分岐予測機構の予測成功率には、このような要求に十分応えられるだけの性能があるとはいい難い。

分岐処理コスト
1 つの原因 分岐処理のコストとしては主に次の2 つが挙げられる。

は、あくまでも分岐方向を過去の履歴から予測するという、根本的な制御方式によるところが大きい。予測であるためにある確率で予測が外れるからである。そこで本研究では、分岐制御を明示的に行なうことを目指し、その可能性を調査・検討した。また、このような制御を行なうための機構モデルについても提案する。

3制御コスト 分岐予測等の分岐制御のコスト
修正コスト 分岐予測等の失敗による修正のコスト
制御コストとしては、例えばBHT(Branch HistoryTable) をひいて分岐予測をするときにかかるコストがある。BHT をひく処理は分岐命令のデコード 時におこ目的と背景
現在のマイクロプロセッサは、スーパースカラ構造やなわれ、そこで分岐予測が修正された場合には、すでにプロセッサは数段のパイプラインを持ち、さらに複数命近のマイクロプロセッサでは、これは非常にコストの高令を同時に発行・実行するため、分岐命令の出現頻度のい処理になる。これらのプロセッサの一部に装備されて2分岐不成立と予測して次命令をフェッチしているので少VLIW 構造をとり、命令レベルの並列性を利用し、高性 なくとも 1 命令分は無駄な処理を行なったことになる。
能化を目指してきた。しかしこのような構造が抱える問修正コストは BHT のような分岐予測機構の予測結果
題の 1 つに分岐処理の問題がある。現在多くのマイクロ が間違っていたときに課せられるペナルティである。最高さとも相俟って、性能的にクリティカルな問題となっ いるている。

re-order バッファなどの複数の命令を一時的に保存しておくバッファには、分岐予測に基づいてフェッチさ現在までに分岐命令を効率的に処理するための機構とれた命令が入っており、これらをフラッシュして新しいして分岐履歴情報を用いたものなどがさまざま提案・実パスへのフェッチ・ポイントを計算して移動する必要が装されているが、未だ完全な分岐予測機構はなく、よりある。さらにバッファをフラッシュしたために次の命令1 列の解析を行ない命令を実行ユニットに発行するまではは、主な分岐予測機構の分岐予測成功率の比較である。 実行ユニットのパイプラインは処理がない状態 (ストー
この表から、静的な分岐予測機構では 65〜70%程度、動 ル状態) となる。よってバッファ・サイズの大きさなど的な分岐予測機構でも 80〜90%程度の予測成功率しか によるが大きなペナルティを課せられることがある。

効率的な分岐制御機構の検討が課題となっている。表得られていないことが分かる。
分岐予測戦略

Branch Always
Branch Backward
Pentium 2-bit
PowerPC604
2-Level Adaptive表

分岐予測成功率の低下を招かずに制御コストを現状か
予測成功率

70.1%
64.5%
82.0%
82.5%
91.3%

1: 分岐予測戦略の予測成功率

命令レベルの並列性をより多く動的に抽出するには、命令ウィンド ウのサイズを大きくする必要があるが、そのためには分岐をまたがる命令の解析が必須である。なぜならば、ベーシック・ブロックのサイズは一般的な整A Proposal of Mechanism for Explicit Branch Control

Tomohiro NAKAMURA, Kenji KISE, Hidenori TSUJI,
Hidehiko TANAKA,
University of Tokyo, Department of Engineering

ら削減するのは難しい。しかし修正コストにはまだコスト削減の可能性が残されている。
4

明示的な分岐制御機構

1

修正コストの削減方法の つの可能性として、明示的な分岐制御機構を検討する。
分岐条件決定タイミングの最適化

4.1

分岐予測ミスの修正は、分岐ミスを検出し修正処理を行なうまでの時間を短縮することで削減が可能である。そのためには、分岐条件を決定する命令)(XXXcc 命令と呼ぶ の実行時点で分岐予測ミスの修正処理を開始することで、この時間を短縮できる。しかしこの効果を十分XXXcc 命令に発揮するためには、分岐命令に対して、を出来る限り早く実行することが重要である。

1は 、サ ンプ ル・プ ログ ラ ム と し て compress
性能評価(SPECint92) について、各ベーシック・ブロック内で XXXcc 命令の最適スケジューリングおよび CCC 機構のデータフロー解析を行なって XXXcc 命令を分岐命令か 実装による性能評価を簡単に述べる。compress の場合、らできるかぎり離すようにスケジューリングした場合 分岐処理にかかるコストは表 2のようになった。CCC 機に、XXXcc 命令と分岐命令との間にとることのできる 構により削減できる分岐処理コストは、修正コストのみ命令数である。ただしここでのスケジューリングはベー であり、表 2では修正コストの約半分を CCC 機構によ
図5

シック・ブロック内という厳しい制約の元でのものであり削減できたことが分かる。なお、削減できない修正コる。実際にはベーシック・ブロックにまたがるスケジューストとは、ある。ここでの値は最も厳しい制約のもとでのものであ令のスケジューリングに関してより多くの自由度を与え

XXXcc 命令を分岐命令に比べてあまり早いリングを行なってより間隔をあけることができる場合も 時期に実行出来なかったことによるもので、XXXcc 命り、データフロー解析を行なっているので、安全なスケ ることでさらに削減が可能であると思われる。
ジューリングとなっている。

制御コスト

32.31%

compress
90000

削減された修正コスト

32.48%

35.21%

2: compress

表の分岐処理コスト比率
各種プログラムに対して、このようなコスト削減の80000

ベーシック・ブロック数削減できない修正コスト

370000効果を分岐予測成功率に換算した値を図 に示す。この

60000

換算は、CCC 機構により得られたコスト削減効果を、CCC 機構をもたない分岐予測機構で同様のコスト削減

5000040000を実現しようとしたときに必要となる分岐予測成功率を96%以上の分岐予測成功率30000示したものである。最高で、20000を達成したことと同等の性能を示している。

10000

980123456789--

1: XXXcc 命令の最適化スケジューリング

新しい分岐制御ハード ウェアの提案

4.2

XXXcc 命令のスケジューリングに関す

前節で述べた、る最適化を行なっても、現在のハード ウェアでは修正コ

+3.91

92
+1.24

+1.46
+1.57

88+1.6986
84

XXXcc 命令

82の実行時に分岐予測の修正処理を行なうハード ウェア

80 compress(CCC 機構: Condition Code Cache) の提案を行+2.00

espresso(bca.in)espresso(cps.in)espresso(ti.in)espresso(tial.in)calcdhrystone

grepjhdaverage

サンプル・プログラム

図なう。

+1.68

90ストの削減は望めない。そこで本節では、
機構

+0.86
+1.62

既存分

94

分岐予測成功率(%)

図改善分

+0.79

96

分岐命令とXXXcc命令との最大距離

3: CCC 機構による修正コスト削減効果の分岐予測

CCC
 XXXcc
 XXXcc 命令の結果から次の分岐命令のアド レスと れを実現する方式として、XXXcc 命令の最適スケジューその分岐方向を決定できること
リングおよび CCC 機構の提案を行なった。また性能評
価によって分岐予測成功率換算で 1〜4%程度の性能向
このような要件を満たすモデルとして図 2を考える。図2で 、PC(XXXcc) は XXXcc 命令のプログラムカウン 上を確認した。90%程度の予測成功率にさらに 1〜4%程度の成功率向上は決して小さい値ではない。今後はベータ、PC(Bicc) は PC(XXXcc) フィールド で指定されるXXXcc 命令によって分岐条件が決定される分岐命令の シック・ブロックをまたがった命令スケジューリングを考え、より CCC 機構が有効に働くスケジューリング方プログラム・カウンタを意味する。cond. フィールド は式の提案などを検討したい。
条件分岐命令中の cond. (condition) フィールド の内容である。この CCC 機構により分岐条件決定時に修正処 謝辞の実装に必要とされる項目は次の通りである。 成功率への換算
6
おわりに命令のアド レスからエントリをひけること 本研究では、明示的な分岐制御機構の可能性を調査し、そ本研究の一部は文部省科学研究費 (一般研究 (B) 課題番号PC(XXXcc) PC(Bicc) cond.

07458052「大規模データパスプロセッサの研究」) による。

参考文献
2: CCC(condition code cache) の実装モデル[1] 中村友洋, 吉瀬謙二, 金指和幸, 田中英彦, \トレース・ドリブン・シミュレーションによる分岐予測機構の検討",
理を開始することができ、XXXcc 命令を分岐命令から図離すことにより、修正コストの削減を実現できる。

第 51 回情報処理学会全国大会, pp.6-13{6-14, 1995