制御依存関係による並列度利用の限界に関する定量的評価
吉瀬謙二, 中村友洋, 辻秀典, 田中英彦
東京大学工学部
1

はじめにプログラムの広い範囲を対象にデータフロー解析とプロ,グラム変換を行なうことで プログラムに内在する並列,度の利用が可能となる。しかし 汎用プログラムには多数の分岐命令が存在するため簡単に解析範囲を広げるこ,とができない。最新のマイクロプロセッサは 実行され()る可能性の高い命令をバッファ 命令ウィンド ウ に格,納し 実行可能となった命令をアウト・オブ・オーダ発行することで命令レベルの並列度を利用する。
我々は汎用アプ リケーションを対象に実行コードがも,つ様々なレベルの並列度の利用を目指しており 命令ウィンドウで決定される解析範囲を大きくしていくアプロー,

3

ブロック内で得られる並列度は 以下と非常に小さい,が静的な解析で抽出可能であるため ブロック間にまたがる並列度と比較しこれらの並列度の利用は容易である。
ブロック内のデータフロー解析により得たクリティカルパスの長さを各ブロックのコスト情報として保存して,おき ブロック間の依存関係とブロックのコストを用いて以降の実行ステップ数を計算する。
ブロック数 ブロック長 (命令) 並列度
compress 254,982
7.84
2.19
espresso 377,244
5.30
1.58
表 1: 200 万命令の解析による基本ブロックの特性チとともに プログラム中の独立なフローを抽出する手2.2法を検討している。

基本ブロックを解析の単位として考え ブロック間で命,ブロックレベル並列度の限界)(

本稿では 広範囲の解析を可能とするために基本ブロッ 令の移動を禁止 ブロックレベルの並列度を利用する。
ブロック間のデータ依存関係をエッジとし ブロッククを解析の基本単位とし ブロックレベル並列度の限界,,,ブロック単位の解析範囲を広げて得ることができる並列をノードとしたデータフローグラフを作成する。ただし度を測定する。これよりブロックレベル並列度の利用に各ノードには先に計算したブロック内のコスト情報を付関する考察をおこなった。

加しておく。得られたデータフローグラフからクリティ

2カルパスのコストを求め それを利用して並列度を計算

ト レースデータを用いた解析

プログラムから並列に実行できるフローの利用を考える

した結果を表2 に示す。

,実行ステップ数 並列度 (平均)compress
340,982
5.87
espresso
365,399
5.47
表 2: ブロックレベル並列度の限界

とき命令ごとの依存関係を求めていては解析が複雑にな,め, 解析の単位としてトレースデータから得られる基本り 大域的な評価が困難になる。この問題を解決するたブロックを考える。

SPECint92 から compress, データフローグラフ作成の際に制御依存関係を排除しespresso をとりあげる。これらのプログラムは SPARC ているため, 表 2 の並列度はブロックレベルの並列度をStation20 の上で gcc コンパイラを用いコンパイルさ 利用した場合の限界を示す。現実にはこの条件を満たすれたものである。実際の解析ではスカラプロセッサのシ ことはできないが, 並列に実行可能で計算に必要なブロックをフェッチ時に指定することができれば, 5〜6 程度のミュレーションで得られたトレースデータを使った。な並列度を利用できる可能性がある。
お解析する命令数は 200 万命令で打ち切った。
解析 するプログ ラムは

2.1

1

2.3

ブロック長とブロック内並列度

表 に解析の単位となる基本ブロックに関するデータと,,(ブロックレベルのウィンド ウ

1 エントリに 1 ブロックの情報を格納するウィンド ウをして 実行されたブロックの数 ブロックの長さ ブロッ 用いブロックレベルの並列度を利用することを考える。
ク内の命令数 ブロック内のデータフロー解析により得 ウィンド ウ内を十分なブロックで満たすため ウィンド),られた並列度を示す。ただし全ての命令のレイテンシは1 ステップと仮定している。
Extracting basic block lebel parallelism
Kenji KISE, Tomohiro NAKAMURA,
Hidenori TSUJI, Hidehiko TANAKA
Faculty of Engineering, University of Tokyo,

ウサイズと同じ段数の分岐予測をおこなう。ウィンド ウ
内のブロックを解析し同時に実行可能なブロックを発行することでブロックレベル並列度を得る。また全ての分岐予測が当たると仮定する。

1 100 まで変化させたときの1 に示す。

ウィンド ウサイズを から総実行ステップ数を図compress では 5 以下のウィンド ウサイズで, espresso それぞれのモデルにおいて compress, espresso の 200
では 10 以下で, 明らかなステップ数の減少がみられるが 万命令を実行したときの総実行ステップ数を図 2 に示す。
それ以降では変化がゆるやかになっていくのがわかる。

¯­­àìêíïâððâðíïâððì®°­âðíïâððì¶­®²­àìêíïâðð

¼ÉÆÚN

®­­¼ÉÆÚN

®®­

®¯­

®­­

µ­²­

´­
³­²­­

±­
°­

®

®­
©§öÌ©¸§½®­­ðàÞéÞï

図3考察

ßéìàèßª®­ÈåÊîßªæáâÞé

ìïÞàéâ

2: 実行ステップ数の推移

1: ウィンド ウサイズによるステップ数の変化 先の実行モデルのうち, 理想的なブロック実行モデルとオラクルマシンは, 制御依存関係の理想化 (分岐の結果
表 3 にウィンド ウサイズが 10 と 100 の場合におけが全てわかっている) を仮定しているためトレースデーる並列度と, ウィンド ウサイズが 1 の時の相対性能を 1タを用いることではじめてシミュレートできる。これらとし, ウィンド ウサイズが無限大のときの性能向上率をのモデルは性能向上の限界を示すという点で重要である
100%とした時の性能向上率を示す。
が, 実現不可能なモデルである。これらの理想的なモデルから, ブロック間の命令移動を禁止することが並列度
ウィンド ウサイズ 10 ウィンド ウサイズ 100
図

並列度

性能向上率

並列度

性能向上率

compress 3.82
64.9%
4.38
74.6%
espresso 2.92
53.4%
3.56
65.1%
表 3:ウィンド ウサイズとブロックレベル並列度の関係

利用に関する大きな制約になっていることがわかる。こcompress で 32.0 から 5.9
espresso で 34.6 から 5.5 へと大幅に減少する。
ブロックを解析単位とした 3 つのモデルに注目する。
表からウィンド ウサイズ 10 のときに, ウィンド ウサイ ウィンド ウサイズ 10 のブロック実行モデルでは, ウィンズを増加させて得られるすべての性能向上に対し 50%以 ド ウサイズの増加により得られる全性能向上の 50%以上上の性能向上率を得ていることがわかる。の性能向上を達成できることが判明した。残り 50%の性能向上を得るためには, 広範囲の解析を可能とするテク
2.4 実行ステップ数の推移
ここまでのデータを整理する。それぞれのデータは, 以 ニックが必要となる。
下で定義する各実行モデルによる総実行ステップ数に対の制約により並列度の限界はへ

4

まとめ

基本ブロックを解析の単位とする 3 つのモデルを中心: 1 ステップに 1 命令 に 5 つの実行モデルを定義し, 各モデルにおいてプログ実行可能なモデル (比較対象用のモデル)ラムの総実行ステップ数を計算した。これより, ブロッ
ブロック実行モデル (block) : 実行中の 1 ブロック内の クレベル並列度を十分に利用するには 10 段以上の分岐応している。

スカラプロセッサモデル (scalar)

みの並列度が利用可能なモデル

予測とさらに広範囲にわたる解析が必要であることを示: した。
ウィンド ウ内の 10 ブロックを解析し並列に実行できる
今後, 多様なプログラムに対する解析をおこなうとと複数のブロックを同時に実行可能としたモデル
もに, スーパースカラ等の実行モデルとの比較をおこなっ
理想的なブロック実行モデル (b-ideal) : 同時に複数の ていく。
ブロックを実行可能とし, 制御依存を理想化したモデル 謝辞
オラクルマシン (oracle) : 1 ステップに複数の命令が 本研究の一部は文部省科学研究費 (一般研究 (B) 課題番号
実行可能であり, 制御依存関係を理想化したモデル
07458052「 大規模データパスプロセッサの研究 」) による。
スカラプロセッサモデルでは並列度 1, オラクルマシ
参考文献
ンの並列度は compress, espresso それぞれ 32.0, 34.6 で [1] 吉瀬, 中村, 金指, 田中 データフローグラフを用いた複数
ウィンド ウサイズ 10 のブロック実行モデル (b-10)ある。参考としてこれらのモデルを評価に加えた。

命令のブロック化 情処第52 回, pp.6-81-82, 1996.