本文はこちら(ps 421K) - 名古屋大学

卒業論文
値予測によるスレッド・レベル並列性の
限界に関する研究
平成 13 年 3 月
電気電子・情報工学科
伊吹誠二
概要
本論文では、非数値計算プログラムにおいてスレッド・レベル並列性への制限を緩和す
る技術の有効性を調査した。その技術は、スレッド間のデータ依存制約を緩和する受信値
予測によるスレッドの投機的実行である。
本論文では、予測方式として静的値予測を用いて、受信値予測による並列性の増加率を測
定した。その結果、理想的な回復機構を用いたモデルでも並列性の増加率は 6.3∼17.9%と
低いことがわかった。また、現実的な回復機構を用いるモデルでは、値予測ミスによる影
響により、並列性は減少することがわかった。
また、基本ブロックレベルでスレッド分割を行うモデルでは、予測する頻度が高いにも
関わらず、受信値値予測による並列性の増加率の限界は低いことがわかった。
i
目次
1 はじめに
1
2 関連研究
3
3 分割レベルによるマシン・モデル
5
3.1
モデルを説明する例
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
9
4 受信値予測
4.1
4.2
4.3
スレッド間のデータ依存制約 : : : : : :
受信値予測によるスレッドの投機的実行
予測ミス時の回復動作 : : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
9
10
11
12
5 評価
5.1
5.2
7
評価環境 : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
評価 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
5.2.1 値予測精度の評価 : : : : : : : : : : : : : : : : : : : :
5.2.2 スレッド分割レベルによる受信値予測の有効性の違い
: : : : : : : :
: : : : : : : :
: : : : : : : :
: : : : : : : :
12
13
14
16
6 まとめ
18
謝辞
19
参考文献
20
ii
第 1章
はじめに
プロセッサの処理能力は、プログラム内の並列性を利用することにより向上させること
ができる。近年のマイクロプロセッサの主流であるスーパスカラ・プロセッサは、並列性の
中でも最も下位のレベルにあたる命令レベルの並列性 (ILP: Instruction-Level Parallelism)
を利用するものである。スーパスカラ・プロセッサはこれまで、命令の発行幅を広げ、種々
の投機的実行技術を取り入れ、より多くの並列性を利用する方向で進んできた。しかし最
近では、このような方向だけでは、ハードウェアの複雑さの増加に見合うだけの並列性が
得られなくなり、大きな性能向上が困難となっている [6][18] 。
スーパスカラ・プロセッサに代わるアプローチとして、最近、複数のプロセッサを単一の
チップに集積するマルチプロセッサの研究が盛んに行なわれている [9][10][11][16][19][22] 。
このアプローチでは、単一のプロセッサによる過度な命令レベル並列性の追求をやめ、複
雑度を押さえ高いクロック速度を維持する。その上で、マルチプロセッサによりスレッド・
レベルの並列性（ TLP: Thread-Level Parallelism ）を利用するものである。
しかし、これまでのところ非数値計算プログラムにおいては、十分な性能向上が達成さ
れているとはいえない。この主な理由は、数値計算と比べ非数値計算は、制御構造が複雑
な上、多くのデータ依存が存在するため、TLP を引き出すことが困難なことにある。
このような問題に対し、これまでの研究は、特定のアーキテクチャに対し、問題解決の
新しい技術を考案適用し、その有効性を示すというアプローチをとっている。これに対し
本研究では、並列性に対する制約のみを考慮し、そのような新しい技術を用い制約を取り
除くことにより、並列性の限界値がどの程度押し上げられるかに興味を持ち、研究を行っ
ている。ある技術を適用したときの並列性の限界値がわかれば、その技術を特定のアーキ
テクチャに対して適用する際、その価値の大きさ、実現方法の良否、そのアーキテクチャ
1
2
第 1 章はじめに
への適合性を評価する指標となる。
本研究では、TLP への制約を緩和する技術に注目している。非数値計算には、並列性を
妨げる制約が複雑かつ多数存在するため、コンパイラのみによる並列性抽出には限界があ
る。そこで、制約を予測により取り除き、スレッドあるいはスレッドに含まれる命令を投
機的に実行することにより、並列性を増加させることは重要である。そのような技術とし
て、データ依存制約を緩和する受信値予測 [2][5] 、制御依存制約を緩和するスレッドの投機
的実行 [19][22][23] 、投機的送信 [23] などが挙げられる。本論文の目的は、これらの中でも
有効と考えられる受信値予測に着目し、その有効性を調べることである。
第 2章
関連研究
TLP を利用する一般的な方法は、マルチプロセッサによるスレッド並列実行である。
Olukotun らは、同一チップ面積の単一チップ・マルチプロセッサとスーパスカラ・プロセッ
サの性能を比較し、非数値計算プログラムではスーパスカラ・プロセッサの方が多くの並
列性を引き出せるという結果を得た [16] 。しかし、マルチプロセッサは高いクロック速度
での動作が期待できるため、性能差はなくなると推測している。
単一チップへの集積の利点を生かし、従来のメモリ・ベースの同期／通信機構に対し、レ
ジスタ・ベースの機構を取り入れた研究として、マルチスカラ [19][23] 、MUSCAT[22] 、
SKY[10][11][15] 、マルチ ALU プロセッサ（ MAP ）[9] などがある。
非数値計算向けのコンパイラ技術として、基本ブロック・レベルの並列性を利用する研究
がなされている。岩田らは、制御依存解析により依存のないスレッドに分割した後、デー
タ依存解析により高い並列性が得られる分割を選択するという手法を提案している [7] 。こ
れに対し、鳥居ら [22] と Vijaykumar ら [23] の研究では、投機的スレッド実行に対するハー
ドウェア支援機構を利用し、制御依存のあるスレッドを含めた分割手法を提案している。
命令レベルの並列性（ ILP: Instruction-Level Parallelism ）の限界に関して、多くの研究
がなされている。Jouppi らは、スーパスカラとスーパパイプライン・アーキテクチャにお
いて、静的スケジューリングの重要性を示した [8] 。Smith らは、プロセッサの現実的な仮
定において、利用可能な ILP について測定した [20] 。Wall は、種々の制約緩和技術により
引き出せる並列性について、一般性の高いマシン・モデルを仮定評価し、制御に関する投
機的実行の重要性を示した [24] 。Lam らは、プログラムの制御フローに着目し、プログラ
ムに内在する並列性について測定した [13] 。この研究は、それまでの研究と異なり、複数
の制御フローについて同時実行した場合の並列性の測定に及んでおり、TLP の限界につい
3
4
第 2 章関連研究
ても示唆している。
TLP への制約を緩和するために、値予測を利用する研究が行なわれている。Marcuello
らは、ループレベルの並列性を利用する特定のアーキテクチャに対して、値予測の効果を
測定した [4] 。Akkary らは、関数レベルとループレベルの並列性を利用し、かつ、受信値
予測によってスレッド間のデータ依存を緩和するアーキテクチャを提案した [2] 。Oplinger
らは、関数レベルとループ・レベルの TLP の限界、および、受信値予測の効果について測
定した [17] 。
第 3章
分割レベルによるマシン・モデル
本研究では、分割レベルの違いにより 4 つのモデルを仮定し、それぞれのモデルにおけ
る値予測による並列性の限界を測定した。測定においては、本質的な制約である真のデー
タ依存と制御依存のみを考慮する。このためにまず、マルチプロセッサを構成する 1 つの
プロセッサを次のように仮定した。無限の命令バンド幅を持ち、分岐予測が正しい間命令
をフェッチできる。分岐予測には静的予測を用いる。フェッチした命令を無限の大きさの命
令ウィンドウに格納し、レジスタとメモリの両方について真の依存を満たす命令を同時に
発行する。レジスタは無限にあるとし、出力依存と逆依存はないとする。機能ユニットや
メモリ・ポート等は無限に存在し、資源制約はない。全ての命令の実行レイテンシを 1 サ
イクルとする。また、理想のメモリ・システムを仮定する。このモデルは 2章で述べた Lam
の研究 [13] における SP モデルと同一であり、本論文でも SP モデルと呼ぶ。
マルチプロセッサについては次のように仮定した。プロセッサ数を無限とし、無限の数
のスレッドを同時に実行できる。通信やスレッド生成などの並列実行に関わるオーバヘッ
ドはゼロとする。スレッド間通信については次のように仮定した。後続スレッドに到達す
る [1] 可能性のある各定義について、その到達が確定する点が命令ウィンドウに含まれたと
き、その定義が投機的かどうかに関わらず、定義された値を送信する。
測定した 4 つのモデルを以下に説明する。第 1 のモデルは、関数レベルでスレッドに分
割するモデルである。このモデルを FC モデルと呼ぶ。命令ウインドウに関数呼び出しが
存在すれば、呼ばれる関数を新しくスレッドとして生成する。命令ウィンドウには、制御
依存が解消していない命令が含まれるので、新しく生成されるスレッドは一般には投機的
である。
第 2 のモデルは、ループ・レベルでスレッドに分割するモデルである。このモデルを LP
5
6
第 3 章分割レベルによるマシン・モデル
モデルと呼ぶ。命令ウィンドウにループの先頭の命令が存在すれば、そのループの各イタ
レーションをスレッドとして、並列に実行する。内側から外側まで全て並列化する。また、
ループ・レベル並列の上限を知るため、ループの繰り返し回数が動的にしかわからない場
合であっても、実際に繰り返される回数だけスレッドを生成する。FC モデルと同じく、こ
のスレッド実行は一般に投機的である。ループの繰り返し回数が動的にしかわからない場
合も、各イタレーションは独立したスレッドとして実行されるので、この点でも投機的で
ある。
第 3 のモデルは、基本ブロック・レベルでスレッド並列実行するものである。このモデ
ルを PD モデルと呼ぶ。このモデルでは、命令ウィンドウに存在する各基本ブロックにつ
いて、これを後支配 [25] する全ての基本ブロックを始点とする新しいスレッドを生成する。
一般に、制御フローグラフ [1] において、基本ブロック X から終点に至るいかなるパス上
にも Y があるとき、Y は X を後支配するという。この場合、Y は X に制御依存しない。
第 4 のモデルは、PD モデルと同様、基本ブロック・レベルでスレッド並列実行するが、
スレッドの始点を後支配のブロックではなく、制御等価 [21] のブロックに限定する点が異
なる [7] 。このモデルを CE モデルと呼ぶ。ここで基本ブロック X と Y が制御等価とは、X
が Y を支配 [1] し、Y が X を後支配する関係をいう。制御等価の関係にある基本ブロック
の組の数は、後支配関係にある基本ブロックの組の数より少ないので、実際にコンパイラ
がスレッド分割を行う場合に計算量の削減になる。このモデルの分割では、一般的には様々
の場合が存在するが、典型的には、IF-THEN-ELSE 文レベルでの並列化と考えることがで
きる。PD モデルでは、IF 部、THEN 部、ELSE 部のいずれの部分からも IF-THEN-ELSE
文の後方のブロックを始点とするスレッドを生成できるが、CE モデルでは、IF 部からの
みとなる。
いずれのモデルにおける並列性の測定においても、完全に関数を展開し、関数の呼び出
しに関係する本質的でない制約を除いた。具体的には、スタック・フレームを確保および
解放する操作、および、関数呼び出しに関わるコンパイラに対する種々の規約に起因する
3.1. モデルを説明する例
7
func2
1a
func1
SP
FC
1a
1
1a
6
1b
2b
3a
4a
call
2
3a
4a
1b
2b
4b
3a
4a
4b
3
1b
5
6
5
6
2b
LP
4
PD
4b
1a
5
5
2b
4b
1a
4a
6
5
1b 2b 4b
6
3a
(a) プログラム
1b
4a
5
6
(b) トレース
3a
(c) モデル
図 3.1: 各モデルにおける実行順
依存（たとえば、関数をまたいで生存するレジスタのスタックへの保存と回復）を無視し
た。さらに、ループについては誘導変数を削除した。これはループ伝搬依存として強く並
列性を制約するが、コンパイラにより容易に取り除くことができるからである。
3.1 モデルを説明する例
図 3.1を用いて、SP 、FC 、LP 、PD モデルを説明する。図 3.1(a) は、本説明に使用する
プログラムの制御フローグラフである。太く強調したエッジは予測された分岐方向を示す。
ここでは、説明を容易にするため、命令間にはデータ依存は存在しない仮定する1 。さらに、
各基本ブロックは単一の命令しか含まないとし、各ノードに付けた番号は、そのまま命令
を表す番号とする。
図 3.1(b) にこのプログラムの実行トレースを示す。トレース中のそれぞれの命令は、ノー
ド番号とインスタンスを区別するための文字 (a, b 等) で表している。円で囲っている命令
は予測ミスした分岐命令である。
各モデルにおける命令実行順を図 3.1(c) に示す。同時に実行される命令を同一階層に示
1 実際のプログラムにはデータ依存があり、5章の測定においてはこれを満足するよう実行順を定めている。
8
第 3 章分割レベルによるマシン・モデル
している。SP モデルでは、分岐予測ミスした分岐間の命令がスケジュールの対象となり、
この例ではデータ依存がないので、スケジュール対象となる全命令が同時に実行される。
FC モデルでは、呼ばれた関数を別のスレッドとし実行し、呼び出した側の関数は実行を続
けることができるので、命令 6 がより早く実行される。LP モデルでは、各イタレーション
をスレッドとして、並列に実行できるので、2 イタレーション目の命令以降がより早く実
行される。PD モデルでは、制御依存のない命令は同時に実行可能なので、命令 4, 5, 6 が
より早く実行される。
第 4章
受信値予測
制約にはデータ依存と制御依存がある。1章で述べたように、本論文ではデータ依存に着
目し、受信値予測を用いたスレッドの投機的実行の有効性について調査する。
本章では、まず、スレッド間のデータ依存制約について述べる。その後、受信値予測に
よるスレッドの投機的実行について述べる。最後に、値予測ミス時の回復動作について述
べる。
4.1 スレッド間のデータ依存制約
スレッド間のデータ依存がどのように並列性の抽出を妨げているかを図 4.1を用いて説明
する。太い線はプログラムの動的な命令列を示している。図 4.1(a) に示す逐次的な動的命
令列を図 4.1(b) に示すようにスレッド 1∼3(Th1∼Th3) に分割したとする。分割された各
スレッドは図 4.1(c) に示すように、並列に実行される。ただし、図 4.1(b) に示すように、
命令 a から命令 b 、命令 c から命令 d にデータ依存が存在するとする。つまり、命令 b は
命令 a の結果を使用し、命令 d は命令 c の結果を使用している。
スレッド分割を行なうと、図 4.1(c) に示すように、一般に各スレッド間には、データ依
存関係が存在する。スレッド間にデータ依存が存在する場合、スレッド間でデータ通信を
行なう必要がある。スレッド間に命令 a から命令 b の様なデータ依存が存在する場合は、
命令 a が実行され、結果が通信されてから、命令 b が実行されるため、命令 b は受信を待
たなくてよい。しかし、スレッド間に命令 c から命令 d の様なデータ依存が存在する場合、
命令 c で生成されたデータが送られてくるまで、命令 d はプロセッサ 3 において受信待ち
状態となる。
このような、受信待ち状態の命令を作り出す原因となるスレッド間のデータ依存関係は、
9
10
第 4 章受信値予測
Th1
Th1
プログラムの流れ
命令a
Th2
命令a
Th3
命令d
通信
命令c
通信
命令d
データ待ち状態
Th2
データ依存
命令b
命令c
命令b
データ依存
プロセッサ１
プロセッサ２
プロセッサ３
(c)マルチプロセッサによるスレッド実行
Th3
命令d
(a)動的な命令列
(b)コンパイラによる
スレッド分割
図 4.1: マルチプロセッサによるスレッド実行の様子
プログラム中に多く存在し、並列性の抽出を妨げる大きな原因となっている。
4.2 受信値予測によるスレッドの投機的実行
受信値予測とは、受信待ち状態になる命令の受信値を予測する技術である。予測値を受
信値として使用することにより、受信待ち状態になる命令を、受信値を待つことなく実行
できる。このように、受信値予測を用いてスレッドを投機的に実行することにより大きな
並列性を引き出すことができる。
図 4.1を用いて受信値予測によるスレッドの投機的実行を説明する。前節で述べた通り、
図 4.1(c) では、命令 d はプロセッサ 3 において受信待ちの状態になる。受信値予測では、
4.3. 予測ミス時の回復動作
11
命令 d が受信する必要がある受信値、つまり、命令 c の実行結果を予測する。そして、予
測値を用いて命令 d を受信値を待つことなく投機的に実行する。
予測の正否は、実際に命令 c が実行され、その結果を命令 d が受信した時に判明する。
予測値が正しければ、そのまま、スレッドの実行が続けられる。予測値が間違っているな
ら、つまり、値予測ミスが起きれば、正しい命令実行を保つための回復動作が必要となる。
4.3 予測ミス時の回復動作
前節で述べた通り、値予測ミスが起きた場合、正しい命令の実行を保つための回復動作
が必要となる。本節では、本研究で用いた２つの回復方式について具体的に述べる。
１つ目は、間違った予測値を用いた命令と、その命令の結果に依存する後続命令のみ再
実行する、再実行 (reexec) 方式である。予測値が間違っていれば、予測値を用いた命令 (以
下、値予測した命令と呼ぶ) は間違った実行結果を得る。また、値予測した命令の結果を用
いた命令、つまり、値予測した命令に依存している命令も間違った結果を得る。したがっ
て、正しい命令の実行を保つためには、これらの命令のみを、実際に計算された通信値を
用いて再実行すれば十分である。このように値予測した命令およびその命令に依存する後
続命令を再実行する。この方式では、図 4.1(c) において、命令 d と命令 d の結果に依存す
る命令のみ再実行することになる。
２つ目は、間違った予測値を用いた命令と、その後続命令を全て再実行する、無効化 (ush)
方式である。reexec 方式のように命令を選択的に再実行するには複雑な機構が必要となる。
これに対し ush 方式は比較的簡単な機構で回復を実現できる現実的な方式である。この
方式では、図 4.1(c) において、命令 d とその後続命令を全て再実行することになる。
第 5章
評価
5.1 評価環境
評価にはトレース駆動型シミュレータを使用した。ベンチマーク・プログラムは、SPECint95
の全 8 種類を使用した。ベンチマーク・プログラムのバイナリのコンパイルには GNU GCC
Version 2.7.2.3(コンパイルオプション：-O6, -funroll-loops) を用いた。命令セットは MIPS
R10000 を拡張した SimpleScalar/PISA とした。トレースは SimpleScalar Tool Set Version
3.0a のシミュレータを基にして採取した。
表 5.1: ベンチマーク・プログラム
ベンチマーク
compress95
gcc
go
ijpeg
li
m88ksim
perl
vortex
入力セット
ref/bigtest.in (30K 要素に減らしたもの)
ref/genoutput.i
9 9 board, level 6, train/2stone9.in
ref/specmun.ppm
train/train.lsp
train/dcrand
train/scrabbl.pl, scrabbl.in(3 語追加), dictionary
ref/persons.1K, vortex.in
2
動的命令数
95M
84M
75M
100M
100M
100M
80M
100M
表 5.1に各ベンチマークにおける入力セットと、シュミレータに入力したトレースの長
さ (動的命令数) を示す。各プログラムへの入力セットは、実行命令数が過大にならないよ
うにするために、SPEC の標準入力での実行と関数の出現頻度をほぼ維持しつつ、実行命
令数が 100M∼200M になるように調節した。シミュレータに入力したトレースは、プログ
ラム実行の最初の 100M 命令、あるいは、それ未満で実行が終了するまでとした。ただし、
ijpeg と vortex では、プログラムの初期化部分である最初から 50M 命令と 100M 命令をそ
12
5.2. 評価
13
れぞれスキップし、それ以降の命令を入力とした。
5.2 評価
本研究では、値予測方式として、静的値予測を用いた。これは、予測対象の通信値で最
も出現頻度の高い値を予測値とするのである。
各マシン・モデルの値予測による並列性の増加率を測定した。測定結果を図 5.1に示す。
並列性の増加率は、値予測を行わない場合での全ベンチマーク・プログラムの並列性の調
和平均と、値予測を行う場合での並列性の調和平均より求めた。比較対象として、完全に
値予測できる場合の並列性の増加率も測定した。これは、受信値予測による並列性の上限
を示している。
140
flush方式
120
reexec方式
並列性の増加率 [%]
100
完全な値予測
80
60
40
20
0
-20
-40
FC
LP
PD
CE
図 5.1: 値予測による IPC の調和平均の増加率
同図からわかるとおり、ush 方式では、全てのマシン・モデルにおいて値予測をしない
場合に比べて並列性が減少している。この原因は以下のように考えられる。ush 方式では
14
第 5 章評価
値予測ミスが起こった時に、間違った予測値を用いて実行された命令 (以下、予測ミスした
命令と呼ぶ) とその後続命令を全て再実行する。予測ミスした命令は、予測ミスが判明し
た直後に再実行される。予測の正否が判明するのは、実際に通信値が生成される時刻、つ
まり、依存元の命令が実行される時刻である。よって、予測ミスした命令は依存元の命令
が実行された直後に再実行される。また、値予測しない場合でも、依存先の命令は依存元
の命令が実行された直後に実行される。以上より、値予測ミスを起こした命令は、予測ミ
スにより、ペナルティを受けることはない。しかし、予測ミスした命令に依存していない
命令が、予測ミスした命令の後続命令中に存在している場合、そのような命令は、値予測
しない場合に比べ実行時刻が遅くなる可能性がある。それは、そのような命令が、予測の
正否が判明した後に再実行されるからである。このような影響が値予測が成功したことに
よって得られる利得を上回り、結局並列性は減少していると考えられる。
reexec 方式では、予測ミスが起こった時、予測ミスした命令と予測ミスした命令に依存
する後続命令のみ再実行する。予測ミスした命令に依存する後続命令は、値予測しない場
合でも、予測ミスした命令の実行を待たなければいけない。予測ミスが起きても、予測ミ
スした命令は値予測しない場合と同じ時刻に再実行される。よって、予測ミスが起きた場
合でも値予測しなかった場合と同じ時刻で後続命令が再実行されることになる。ush 方式
のように、値予測ミスによる影響で並列性が減少するということはない。
5.2.1
値予測精度の評価
ush 方式での値予測精度を図 5.2に、reexec 方式の値予測精度を図 5.3に示す。
図 5.2より ush 方式での値予測精度は FC 、LP 、PD 、CE モデルでそれぞれ、平均 40.3% 、
15.9% 、34.2% 、35.3%となった。図 5.3より reexec 方式での値予測精度は FC 、LP 、PD 、
CE モデルでそれぞれ、平均 40.6% 、22.3% 、39.5% 、39.3%となった。
全体的に値予測精度は低い。値予測精度についてはまだ改善できる余地が多く残されて
いるといえる。図 5.1をみて分かる通り、reexec 方式での並列性の増加率は完全な値予測を
5.2. 評価
15
70
FC
60
LP
PD
値予測精度 [%]
50
CE
40
30
20
10
0
comp.
gcc
go
ijpeg
li
m88k.
perl
vortex 算術平均
図 5.2: ush 方式での値予測精度
70
FC
LP
60
PD
CE
値予測精度 [%]
50
40
30
20
10
0
comp.
gcc
go
ijpeg
li
m88k.
perl
図 5.3: reexec 方式の値予測精度
vortex 算術平均
16
第 5 章評価
行った場合に比べ非常に低い。ush 方式では、逆に並列性は減少している。最終値予測、
ストライド値予測などの動的値予測を行い、値予測精度を向上することができれば、並列
性の増加率は改善できるはずである。
5.2.2
スレッド分割レベルによる受信値予測の有効性の違い
値予測による並列性の増加率の上限は、値予測を行う頻度に関係があると考え、動的命
令数に対する値予測した通信値の数を測定した。結果を図 5.4に示す。左側の縦軸は並列性
の増加率を示し、棒グラフと対応している。右側の縦軸は動的命令数を値予測した通信値
の数で割ったもので折れ線グラフと対応している。各ベンチマークプログラムにつき、４
つの棒グラフがあり、左から FC 、LP 、PD 、CE モデルでの完全な値予測を行った場合の
並列性の増加率を示している。
10
20
FC
LP
PD
8
15
CE
7
予測を行った頻度
6
10
5
4
予測を行った頻度
完全な値予測による並列性の増加率
9
5
3
2
1
0
comp.
gcc
go
ijpeg
li
m88k.
perl
vortex 調和平均
図 5.4: 値予測頻度と完全な値予測による並列性の増加率の関係
FC 、LP モデルでは、vortex を除き、値予測の頻度が増えるに従い、並列性の増加率も
大きくなっていることがわかる。しかし、PD 、CE モデルでは、FC 、LP モデルに比べ値
5.2. 評価
17
予測の頻度が増えているにもかかわらず、並列性の増加率は減少しているものが多い。こ
のことより、FC 、LP モデルではスレッド間のデータ依存が並列性を大きく制限している
が、PD 、CE モデルでは、他の要因が並列性を大きく制限していると考えられる。
第 6章
まとめ
本論文では、非数値計算プログラムにおいて、受信値予測の有効性を調査した。予測方
式として、静的値予測を用いた。
その結果、全ての予測が成功するとした場合でも、66∼135%しか並列性が増加しないこ
とがわかった。また、静的値予測の値予測精度は 15.9∼40.6%と低いため、理想的な回復機
構を用いるモデルでも並列性の増加率は 6.3∼17.9%と全ての予測が成功するとした場合に
比べ、かなり低くなることがわかった。また、現実的な回復機構を用いるモデルでは、値
予測ミスによる影響により、並列性は減少することがわかった。
予測の頻度と、並列性の増加率の関係を調査したところ、基本ブロック分割モデルでは、
予測する頻度が高いにも関わらず、受信値予測による並列性の増加率の限界は低いことが
わかった。基本ブロックレベル分割を行うモデルでは、スレッド間のデータ依存以外の要
因が並列性を大きく制限していると考えられる。
18
謝辞
本研究にあたり、御指導を頂いた名古屋大学大学院工学研究科島田俊夫教授、安藤秀樹
助教授、小林良太郎助手、博士課程 (前期課程) 加納正晃氏に感謝の意を表します。
19
参考文献
[1] A. V. Aho, R. Sethi, and J. D. Ullman,
Compilers: Principles, Techniques, and Tools,
Addison-Wesley Publishing Company, Reading, MA, 1986.
[2] H. Akkary and M. Driscoll, \A Dynamic Multithreading Processor," In Proc. 31st
Int.
Symp. on Microarchitecture, pp.226-236, December 1998.
[3] E. Rotenberg, Q. Jacobson, Y. Sazeides, J. E. Smith, \Trace Processors," In
Proc.
30th Int. Symp. on Microarchitecture, pp.138-148, December 1997.
[4] P. Marcuello, J. Tubella, and A. Gonzalez, \Value Prediction for Specualtive Multithreaded Architecture," In
Proc. 32nd Int. Symp. on Microarchitecture, pp.230-236,
November 1999.
[5] L. Hammond, M. Willey, and K. Olukotun, "Data Speculation Support for a Chip
Multiprocessor," In Proc. Eighth
Int. Conf. on Architectural Support for Programming
Languages and Operating Systems, pp. 58-69, October 1998.
[6] T. Hara, H. Ando, C. Nakanishi, and M. Nakaya, \Performance Comparison of ILP
Machines with Cycle Time Evaluation," In
Proc. 23rd Int. Symp. on Computer Ar-
chitecture, pp.213-224, May 1996.
[7] 岩田充晃, 小林良太郎, 安藤秀樹, 島田俊夫, \制御等価を利用したスレッド分割技法,"
情報処理学会研究報告 97-ARC-128, pp.127-132, 1998 年 3 月.
[8] N. P. Jouppi and S. W. Wall, \Available Instruction-Level Parallelism for Superscalar
and Superpipelined Machines," In
Proc. Third Int. Conf. on Architectural Support for
20
21
参考文献
Programming Languages and Operating Systems, pp. 272-282, April 1989.
[9] S. W. Keckler, W. J. Dally, D. Maskit, N. P. Carter, A. Chang, and W. S. Lee,
\Exploiting Fine-Grain Thread Level Parallelism on the MIT Multi-ALU Processor,"
In
Proc. 25th Int. Symp. on Computer Architecture, pp.306-317, July 1998.
[10] 小林良太郎，岩田充晃，安藤秀樹，島田俊夫, \非数値計算プログラムのスレッド間命
令レベル並列を利用するプロセッサ・アーキテクチャSKY," 1998 年並列処理シンポジ
ウム JSPP'98 ，pp.87-94, 1998 年 6 月.
[11] R. Kobayashi, M. Iwata, Y. Ogawa, H. Ando, and T. Shimada, \An On-Chip Multiprocessor Architecture with a Non-Blocking Synchronization Mechanism," In
Proc.
25th EUROMICRO Conference, pp.432-440, September 1999.
[12] B. Kreaseck, D. Tullsen, and B. Calder, \Limits of Task-based Parallelism in Irregular
Applications," In
Proc. Third Int. Symp. on High Performance Computing, pp.43-58,
October 2000.
[13] M. S. Lam and R. P. Wilson, \Limits of Control Flow on Parallelism," In
Proc. 19th
Int. Symp. on Computer Architecture, pp.46-57, June 1992.
[14] W. Ogata, A. Yoshida, M. Okamoto, K. Kimura, and H. Kasahara, \Near Fine Grain
Parallel Processing without Explicit Synchronization on a Multiprocessor System," In
Proc. Sixth Workshop on Compilers for Parallel Computers, December 1996.
[15] 小川行宏，小林良太郎，安藤秀樹，島田俊夫, \オンチップマルチプロセッサアーキテ
クチャSKY の評価," 情報処理学会研究報告 99-ARC-135, pp.17-24, 1999 年 11 月.
[16] K. Olukotun, B. A. Nayfeh, L. Hammond, K. Wilson, and K. Chang, \The Case for a
Single-Chip Multiprocessor," In Proc.
Seventh Int. Conf. on Architectural Support for
22
参考文献
Programming Languages and Operating Systems, pp.2-11, October 1996.
[17] J. T. Oplinger, D. L. Heine, and M. S. Lam, \In Search of Speculative Thread-Level
Parallelism," In Proc. of the 1999 Int. Conf. on Parallel Architectures and Compilation
Techniques, pp.303-313, October 1999.
[18] S. Palacharla, N. P. Jouppi, and J. E. Smith, \Complexity-Eective Superscalar Processors," In
Proc. 24th Int. Symp. on Computer Architecture, pp.206-218, June 1997.
[19] G. S. Sohi, S. E. Breach, and T. N. Vijaykumar, \Multiscalar Processor," In
Proc.
22nd Int. Symp. on Computer Architecture, pp.414-425, June 1995.
[20] M. D. Smith, M. Johnson, and M. A. Horowitz, \Limits on Multiple Instruction Issue,"
In
Proc. Third Int. Conf. on Architectural Support for Programming Languages and
Operating Systems, pp. 290-302, April 1989.
[21] M. D. Smith, M. A. Horowitz, and M. S. Lam, \Ecient Superscalar Performance
Through Boosting," In
Proc. Fifth Int. Conf. on Architectural Support for Program-
ming Languages and Operating Systems, pp.248-259, October 1992.
[22] 鳥居淳, 近藤真己, 本村真人, 池野晃久, 小長谷明彦, 西直樹, \オンチップ制御並列プロ
セッサ MUSCAT の提案," 情報処理学会論文誌, Vol. 39, No. 6, pp. 1622-1631, 1998
年 6 月.
[23] T. N. Vijaykumar, \Compiling for the Multiscalar Architecture," Ph.D. thesis, University of Wisconsin-Madison, Madison, WI 53706, 1998.
[24] D. W. Wall, \Limits of Control Flow on Parallelism," In
Proc. Fourth Int. Conf. on
Architectural Support for Programming Languages and Operating Systems, pp.176-188,
April 1991.
23
参考文献
[25] H. Zima and B. Chapman,
Supercompilers for Parallel and Vector Computers,
Addison-Wesley Publishing Company, Inc., New York, NY, 1991.

Download Report