投機実行によりメモリレベル並列性を抽出するインオーダ

Tokyo Institute of Technology
Department of Computer Science
修士論文
投機実行によりメモリレベル並列性を抽出する
インオーダプロセッサの性能向上手法に関する研究
指導教員: 吉瀬謙二准教授
平成 27 年 1 月
提出者
大学院情報理工学研究科計算工学専攻
11M38134
大久保直昭
i
概要
近年，１つのチップに複数のプロセッサコアを集積するチップマルチプロセッサ（CMP）
が広く普及している．CMP は異なるスレッドを複数のコアで並列に実行することでスレッ
ドレベル並列性を抽出し，性能向上を達成する．
プロセッサの性能向上に対する主な障害として，プロセッサの速度に比べてメモリのア
クセス時間が長く，メモリの速度が性能のボトルネックになるというメモリウォール問題
がある．この影響を緩和する対策の 1 つとして，命令のアウトオブオーダ実行が挙げられ
る．しかし，伝統的なアウトオブオーダコアには多くの複雑な機構の追加が必要となるた
め，プロセッサのハードウェア量と消費電力が大きくなってしまうという問題がある．
この要求をハードウェア量の少ないインオーダコアで達成する手法として，Simultaneous
Speculative Threading（SST）が提案されている．SST は，メモリの長いアクセス時間の
間に実行可能な命令を先に実行し，メモリアクセスが完了した後にデータ依存関係にある
命令を実行するスレッディング手法である．SST はインオーダコアをベースにしているた
め，伝統的なアウトオブオーダコアに比べより少ないハードウェア量で高い性能向上を可
能にしている．また，SST に対しては性能を向上させる様々な提案がなされており，ALU
カスケーディングと組み合わせて相乗効果を狙うものや，SST の弱点である投機実行の失
敗に対するリスクを軽減するスレッディング手法などが提案されている．しかし，実際に
はこれらの提案が有効に機能しない場面が多く存在している．SST と ALU カスケーディ
ングの相乗効果は，SST でよく見られるメモリアクセス命令とその依存命令に対して発揮
されず，またリスクを軽減させたスレッディング手法はその代償としてそのリターンを一
定量に限定してしまっている．
本論文では，これらの場面に対しても効率的な命令実行が可能となるスレッディング手
法を提案する．提案手法によって，メモリアクセス命令とその依存命令を ALU カスケー
ディングによって効率的に処理することができ，また従来のスレッディング手法の課題で
あった命令再実行時のストール状態を抑制することが可能となる．
ソフトウェアシミュレータによる評価の結果，以前のスレッディング手法に比べ，IPC
が平均で 1.23%，最大 2.00% 向上することが確認できた．
iii
目次
目次
iii
図目次
v
表目次
vii
第1章
1.1
1.2
第2章
2.1
序論
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
命令レベル並列性とメモリレベル並列性
命令レベル並列性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1
2.1.2
2.1.3
2.2
第3章
3.1
依存関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
アウトオブオーダ実行 . . . . . . . . . . . . . . . . . . . . . . . . .
メモリレベル並列性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1
2.2.2
2.3
概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
投機実行 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
関連研究
Simultaneous Speculative Threading
3.1.1 アーキテクチャ . . . . . . . .
3.1.2 SST における命令実行の流れ
3.1.3 SST の利点 . . . . . . . . . .
3.1.4 データハザードの扱い . . . .
3.1.5 課題 . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
3
3
3
4
6
6
6
8
9
11
11
11
12
15
15
16
iv
目次
3.2
3.3
第4章
4.1
4.2
第5章
5.1
5.2
5.3
5.4
5.5
5.6
第6章
ALU カスケーディング . . . . . . . . . . .
SST と ALU カスケーディングの統合 . . .
3.3.1 SST を改良したスレッディング手法
3.3.2 ALU カスケーディングとの併用 . .
3.3.3 ALU カスケーディングの課題 . . . .
3.3.4 改良スレッディング手法の課題 . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
18
18
18
21
21
.
.
.
.
23
23
23
24
25
新たなスレッディング手法の提案
. . . .
4.1.1 概要 . . . . . . . . . . . . . . . .
4.1.2 アーキテクチャ . . . . . . . . . .
新たに提案するスレッディング手法 . .
提案するロード命令の処理手法
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
提案手法の評価
評価環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
提案手法による性能変化 . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
5.3.1 ALU カスケーディング適用率 . . . . .
5.3.2 bzip2 における提案手法の効果 . . . .
提案したスレッディング手法の効果 . . . . .
5.4.1 SST の実行状態の変化 . . . . . . . . .
5.4.2 分岐予測ミスの影響 . . . . . . . . . .
今後の課題 . . . . . . . . . . . . . . . . . . .
DQ の構成による性能変化 . . . . . . . . . .
5.6.1 DQ 構成を変化させた場合の性能向上
5.6.2 DQ 構成の提案手法への影響 . . . . .
提案したロード命令処理の効果
結論
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
29
30
30
30
32
36
36
38
40
41
41
41
45
謝辞
47
参考文献
49
v
図目次
2.1
2.2
2.3
インオーダ実行およびアウトオブオーダ実行における実行サイクル数の違い
ILP の抽出よりも MLP の抽出の方が性能向上に有効である例 [1] . . . . .
Runahead Execution の実行イメージ [2] . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
アプリケーションがメモリインテンシブな場合とそうでない場合の例 [4]
ALU カスケーディングが効率的に動作していない場合の例 [4] . . . . .
改良スレッディング手法においてストールが発生する例 . . . . . . . . .
7
8
9
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
SST を採用するプロセッサのブロック図 [3] . . . . . . . . . .
SST によるプログラム実行の流れ . . . . . . . . . . . . . . . .
SST における各ベンチマーク実行時の投機状態の割合 [3] . . .
SST から各種の投機失敗を取り除いた場合の性能向上率 [3] . .
ALU カスケーディングにおける命令実行の例 . . . . . . . . .
SST によるプログラム実行の流れ . . . . . . . . . . . . . . . .
松村らの提案した SST によるプログラム実行の流れ . . . . . .
ALU カスケーディングによって効率的に実行できる命令列 [4]
.
.
.
.
.
.
.
.
.
.
.
12
13
16
16
17
19
19
20
20
21
22
4.1
4.2
4.3
4.4
提案手法による実行サイクル短縮の例 . . . . . . . . . . . . . . . . . . . .
24
25
26
26
5.1
5.2
5.3
5.4
5.5
5.6
各ベンチマークの IPC
提案手法のブロック図 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
従来手法によるストール発生時の実行例 . . . . . . . . . . . . . . . . . . .
提案手法によるストール発生時の実行例 . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
各ベンチマークの IPC 変化率 . . . . . . . . . . . . . . . . . .
命令再実行時における ALU カスケーディング適用率 . . . . .
提案したロード手法を行った場合の SST に対する IPC 変化率 .
提案したスレッディング手法と組み合わせた場合の IPC 変化率
.
.
.
.
.
提案したロード命令処理手法において性能が低下する場合の例 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
32
34
34
35
vi
図目次
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
SST の実行状態の割合 . . . . . . . . . . . . . . .
SST の実行状態の割合の変化率 . . . . . . . . . .
全実行時間に対する投機実行状態の増加分の割合 .
投機実行時間における無効な投機実行の割合 . . .
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
全実行時間に対する有効な投機実行状態の増加分の割合 . . . . . . .
DQ の構成を変化させた場合の SST の IPC 変化率 . . . . . . . . . .
DQ の構成を変化させた場合の提案手法の IPC 変化率 . . . . . . . .
DQ の構成を変化させた場合の SST に対する提案手法の IPC 変化率
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
37
38
39
40
42
42
43
vii
表目次
5.1
評価に用いたプロセッサのパラメータ . . . . . . . . . . . . . . . . . . . .
29
1
第1章
序論
1.1
はじめに
20 世紀中頃に集積回路が発明されて以来，” ムーアの法則” に表されるように，半導体
の集積技術は劇的な速度で進歩を遂げた．そして集積回路の微細化に伴い，マイクロプロ
セッサの性能も驚異的な発展を続けてきた．かつて，プロセッサの性能向上はシングルス
レッド性能が中心であり，1 つのチップに 1 つのコアを搭載する時代が長く続いていた．
しかし，20 世紀末にシングルコアの性能向上が限界に達すると，1 つのチップに複数のプ
ロセッサコアを集積するチップマルチプロセッサ（CMP）が主流となった．CMP は異な
るスレッドを複数のコアで並列に実行することで性能向上を達成するものであり，現在使
用されているマイクロプロセッサの大部分を占めている．
プロセッサの性能向上に対する主な障害として，プロセッサの速度に比べてメモリのア
クセス時間が長く，メモリの速度が性能のボトルネックになるというメモリウォール問題
[5] がある．この影響を緩和する対策の 1 つとして，命令のアウトオブオーダ実行が挙げ
られる．プログラムの命令レベル並列性を抽出することで，メモリへのアクセス中に平行
して実行可能な命令を実行し，長いアクセス時間を隠蔽する．しかし，伝統的なアウトオ
ブオーダコアには多くの複雑な機構の追加が必要となるため，プロセッサのハードウェア
量と消費電力が大きくなってしまう．CMP の時代においては，コアを多く集積するため，
ハードウェア量や消費電力の少ない軽量なコアが求められる．このような性能と軽量化の
相反する要求を満たすことは，近年のマイクロプロセッサにおける課題となっている．
この要求を，ハードウェア量の少ないインオーダコアで達成する手法として，Simulta-
neous Speculative Threading（SST）[3] が提案されている．SST は，メモリの長いアクセ
ス時間の間に実行可能な命令を先に実行し，メモリアクセスが完了した後にデータ依存関
係にある命令を実行するスレッディング手法である．SST はインオーダコアをベースにし
Chapter 1 序論
2
ているため，伝統的なアウトオブオーダコアに比べより少ないハードウェア量で高い性能
向上を可能にしている．また，SST に対しては性能を向上させる様々な提案がなされてお
り，ALU カスケーディングと組み合わせて相乗効果を狙うものや，SST の弱点である投機
実行の失敗に対するリスクを軽減するスレッディング手法などが提案されている [4]．し
かし，実際にはこれらの提案が有効に機能しない場面が多く存在している．SST と ALU
カスケーディングの相乗効果は，SST でよく見られるメモリアクセス命令とその依存命令
に対して発揮されず，またリスクを軽減させたスレッディング手法はその代償としてその
リターンを一定量に限定してしまっている．
本論文では，これらの場面に対しても効率的な命令実行が可能となるスレッディング手
法を提案する．そして，シミュレータを用いた評価を行い，その有用性を明らかにする．
1.2
本論文の構成
本論文の構成は次の通りである．まず 2 章では，本論文の重要な概念である命令レベル
並列性およびメモリレベル並列性について述べ，3 章では，関連研究として Simultaneous
Speculative Threading と ALU カスケーディング，そしてそれらを組み合わせたプロセッ
サおよびその問題点について述べる．そして 4 章では提案手法について述べ，5 章で提案
手法をシミュレーションによって評価する．最後に 6 章で本論文をまとめる．
3
第2章
命令レベル並列性とメモリレベル並
列性
本章では，本論文の前提となる概念である，命令レベル並列性（ILP）[6] およびメモリ
レベル並列性（MLP）について述べる．
2.1
命令レベル並列性
2.1.1 概要
次の命令列について考える．
list1:
i1:
i2:
i3:
i4:
r1
r2
r3
r4
=
=
=
=
r1
r2
r3
r4
+
+
+
+
1
2
3
4
list2:
i1:
i2:
i3:
i4:
r1
r2
r3
r4
=
=
=
=
r1
r1
r2
r3
+
+
+
+
1
2
3
4
list1 の命令列では，各命令で使用するレジスタは独立しており，どの命令を実行しても
他の命令の実行に影響を与えない．そのため，全ての命令を並列に実行可能である．
一方 list2 の命令列では，各命令で使用するレジスタは独立しておらず，命令 i1 の結果
は i2 の実行に影響を与え，i2 は i3 に，i3 は i4 にそれぞれ影響を与える．そのため，list2
の命令列には並列に実行可能な命令の組は存在しない．この状態のことを，list1 の命令列
は list2 よりも命令レベル並列性が高いという．命令レベル並列性とは，並列に実行可能な
命令の数を表す基準である．
Chapter 2 命令レベル並列性とメモリレベル並列性
4
2.1.2 依存関係
前項で示した命令列において，list2 の命令 i1 の実行結果は命令 i2 の実行に影響を与え
ていた．この状態を，i1 と i2 には依存関係が存在するという．依存関係には次のようなも
のがある．
• データ依存
– 真のデータ依存
– 逆依存
– 出力依存
• 制御依存
• 資源制約
依存関係にある命令列は，命令の実行順序に注意する必要があるため，命令の並列実行を
大きく制限する．本項では，並列実行を阻害するこれらの依存関係について述べる．
真のデータ依存
i1: r1 = r1 + 1
i2: r2 = r1 + 2
上の命令列において，命令 i2 の実行にはレジスタ r1 の値が必要であり，かつレジスタ r1
の値は命令 i1 によって書き込まれている．このように，ある命令の結果を別の命令が使用
する依存関係のことを，真のデータ依存と呼ぶ．
また，命令 i1 より先に i2 を実行すると，正しい r1 の値が得られないため，命令順に
実行した場合とは異なった結果となってしまう．この状態のことを Read-After-Write ハ
ザードという．
逆依存
i1: r1 = r2 + r3
i2: r3 = r4 + 5
上の命令列において，命令 i1 の実行にはレジスタ r3 の値が必要である．一方，レジスタ
r3 の値は命令 i2 によって上書きされている．このように，ある命令が使用するレジスタを
別の命令が更新する依存関係のことを，逆依存と呼ぶ．
また，命令 i1 より先に i2 を実行すると，r3 の値が上書きされるため，命令 i1 は命令順
に実行した場合とは異なった結果となってしまう．この状態のことを Write-After-Read
2.1 命令レベル並列性
5
ハザードという．
出力依存
i1: r3 = r2 + r1
i2: r3 = r4 + 5
上の命令列において，命令 i1 と i2 はどちらもレジスタ r3 の値を更新している．このよう
に，複数の命令が同じレジスタを更新する依存関係のことを，出力依存と呼ぶ．
また，命令 i1 より先に i2 を実行すると，後に実行した命令 i1 によって r3 の値が上書き
されるため，レジスタ r3 の値は命令順に実行した場合とは異なった値となってしまう．こ
の状態のことを，Write-After-Write ハザードという．
制御依存
i1: if (r1 == r2) goto L1
i2: r3 = r4 + 5
L1:
i3: r5 = r6 + 7
上の命令列において命令 i1 は分岐命令であり，命令 i1 の結果によって命令 i2 を実行する
かどうかが変化する．このように，分岐命令によって実行する命令が変化する依存関係の
ことを制御依存と呼ぶ．
また，命令 i1 より先に i2 を実行すると，命令 i1 の分岐結果によっては命令順に実行し
た場合と異なった結果になってしまう．この状態のことを，制御ハザードという．制御依
存は全ての分岐命令に対して生じるため，一般的に制御依存は命令レベル並列性の抽出を
大きく阻害する．
資源制約
命令の並列実行を阻害する要因として，データ依存や制御依存の他にプロセッサの資源
の問題が挙げられる．
例えば，演算命令を並列に実行するためには，同時に実行する命令数と同数の演算器が
必要となる．特に乗算や除算など，演算に大きなハードウェアを必要とする命令は，演算
器の数が少ないことが多く，命令の並列実行を阻害する要因となる．
また，ロードストア命令も同様である．同時に実行できるロードストア命令の数は
キャッシュのポート数に依存するため，これも命令の並列実行を阻害する．
Chapter 2 命令レベル並列性とメモリレベル並列性
6
2.1.3 アウトオブオーダ実行
命令実行をプログラムの順序通りに行うことをインオーダ実行といい，プログラムの命
令順とは異なる順序で命令を実行することをアウトオブオーダ実行と呼ぶ．アウトオブ
オーダ実行では命令レベル並列性を抽出し，実行可能な命令から順に実行していくことで，
インオーダ実行よりも高い性能を実現する．
i1:
i2:
i3:
i4:
i5:
r1
r4
r5
r6
r7
=
=
=
=
=
r2
r1
r4
r1
r6
+
+
+
+
+
r3
r4
r5
r6
5
上の命令列において，i1 と i2，i2 と i3，i1 と i4，i4 と i5 の間には真のデータ依存関係が
存在する．この命令列を演算器を 2 つ持つ 5 段パイプラインのプロセッサで実行する場合
を考える．命令実行に必要なサイクルは 1 サイクルとする．
インオーダ実行およびアウトオブオーダ実行において，命令列の実行にかかるサイクル
数を図 2.1 に示す．上がインオーダ実行の場合，下がアウトオブオーダ実行の場合である．
ここでは簡単のため，EX ステージおよび WB ステージのみを記載している．インオーダ
実行の場合，i1 から i3 までは真のデータ依存関係があるため並列実行ができず，i4 と i5
で初めて並列実行を行い，結果的に命令列の実行には 5 サイクルが必要となっている．一
方アウトオブオーダ実行の場合，i1 を実行完了した時点で i2 と i4 が並列実行可能になり，
そして i2 と i4 を実行完了した時点で，i3 と i5 が並列実行可能となる．結果的に命令列の
実行には 4 サイクル必要となり，インオーダ実行よりも 1 サイクル分実行サイクルが短縮
できていることが分かる．
2.2
メモリレベル並列性
2.2.1 概要
メモリレベル並列性とは，複数のメモリ操作，特にキャッシュミスを同時に処理できる
能力のことである．
近年，プロセッサの速度向上に比べてメモリのアクセス時間が長く，メモリの速度がプ
ロセッサ性能のボトルネックになっているというメモリウォール問題が表面化している．
そのような状況下では，命令レベル並列性の抽出による性能向上を狙うよりも，メモリレ
2.2 メモリレベル並列性
7
cycle
1
2
i1: r1 = r2 + r3
EX
WB
i2: r4 = r1 + r4
EX
3
i3: r5 = r4 + r5
EX
WB
i4: r6 = r1 + r6
EX
WB
EX
cycle
1
2
i1: r1 = r2 + r3
EX
WB
i2: r4 = r1 + r4
EX
i3: r5 = r4 + r5
i4: r6 = r1 + r6
i5: r7 = r6 + 5
3
WB
4
WB
EX
EX
5
WB
i5: r7 = r6 + 5
図 2.1
4
WB
WB
EX
WB
インオーダ実行およびアウトオブオーダ実行における実行サイクル数の違い
ベル並列性の抽出に資源を集中させ，それによる性能向上を狙うことが提案されている
[1]．
命令レベル並列性の抽出よりも，メモリレベル並列性の抽出の方が性能向上に有効であ
る例を図 2.2 に示す．この図は，積和演算のタスクを二種類のプロセッサで処理した場合
の処理時間を比較した図である．左側の図は，命令レベル並列性を積極的に抽出するプロ
セッサにおける処理時間のイメージであり，4 つのキャッシュミスを同時に処理すること
が可能となっている．一方右側の図は，メモリレベル並列性を積極的に抽出するプロセッ
サの場合であり，6 つのキャッシュミスを同時に処理することが可能となっている．
左側の場合，12 個のキャッシュミスの処理に，少なくとも 3 回のミスペナルティ分の
時間がかかっている．一方，右側では 2 回分のミスペナルティで処理を終えている．命令
レベル並列性を積極的に抽出しないため命令実行に多少時間はかかるものの，ミスペナル
ティに比べれば命令実行にかかる時間はわずかなため，メモリレベル並列性を抽出するプ
ロセッサの方が処理を早く完了することが可能となっている．
Chapter 2 命令レベル並列性とメモリレベル並列性
8
Processors with low IPC can have high MLP
AXPY
A * Xi + Yi
Wide Superscalar CPU
4 misses deep
Narrow CPU
6 misses deep
Many cache misses ⇒ Narrow - Wide = small startup cost
Why not spend HW on cache misses, not superscalar EUs?
図 2.2
ILP の抽出よりも MLP の抽出の方が性能向上に有効である例 [1]
2.2.2 投機実行
メモリレベル並列性を積極的に抽出する方法として，キャッシュミスを処理している
間に投機実行を行う手法が提案されている．ここではその例として，Mutlu らの提案した
Runahead Execution[2] を取り上げる．
投機実行のイメージを図 2.3 に示す．上が一般的なアウトオブオーダプロセッサ（a）で
あり，下が Runahead Execution（b）である．一般的なアウトオブオーダプロセッサでは，
L2 キャッシュのミス中に命令ウィンドウを使い切り，キャッシュミスから回復するまでス
トール状態になると考えられる．一方 Runahead Execution では，最も古い命令（Load A）
が L2 キャッシュミスの回復を待っている場合，プロセッサの現在の状態のチェックポイン
トを取り，ミスを引き起こした命令（Load A）がキャッシュミスから回復するまでキャッ
シュミスに依存しない命令のみを投機実行していく（Runahead mode）
．投機実行中に別の
ロード命令（Load B）が新たにキャッシュミスした場合は，そのミスも追加で処理し，最
初の命令がキャッシュミスから回復したら，パイプラインをフラッシュし，チェックポイ
ントから実行を再開する．チェックポイントからの実行再開後は，投機実行時に実行した
ロード命令がプリフェッチの役割を果たすため，一般的なアウトオブオーダプロセッサよ
りも効率的に命令を実行できる．
2.3 まとめ
Load A misses
in L2 cache
9
Instruction window
becomes full
Load B misses
in L2 cache
Instruction window
becomes full
No forward progress in program
C ompute
Useful
computation
(a)
Load A misses
in L2 cache
S tall
C ompute
S tall
L2 miss A (being serviced from memory)
Load A is the oldest Load B misses
instruction in window in L2 cache
C ompute
L2 miss B (being serviced from memory)
Load A reexecuted
(cache hit)
Load B reexecuted
(cache hit)
P ipeline flush
R unahead mode
C ompute
C ompute
C ompute
L2 miss A (being serviced from memory)
L2 miss B (being serviced from memory)
C ycles saved by runahead execution
(b)
P rogram execution timeline
図 2.3
Runahead Execution の実行イメージ [2]
[2] によると，Runahead Execution によって IPC が平均で 22% 程度向上しており，投機
実行によるメモリレベル並列性の抽出がプロセッサの性能向上に有効であることが確認で
きる．
2.3
まとめ
本章では，スーパースカラプロセッサの基本的な概念である命令レベル並列性（ILP）お
よびメモリレベル並列性（MLP）について述べ，さらにそれを活用する方法として，アウ
トオブオーダ実行と投機実行について述べた．
次章では，インオーダプロセッサで投機実行を行い，命令レベル並列性およびメモリレベ
ル並列性を抽出するスレッディング手法である SST（Simultaneous Speculative Threading）
と，ALU カスケーディング，そしてそれらを組み合わせたプロセッサについて述べる．
11
第3章
関連研究
この章では関連研究として，投機実行をするプロセッサである Simultaneous Speculative
Threading（SST）と，２つの ALU を組み合わせて利用する ALU カスケーディング，そし
て SST に ALU カスケーディングを組み合わせたプロセッサについて述べる．
3.1 Simultaneous Speculative Threading
Simultaneous Speculative Threading（SST）[3] は， Chaundhry らによって提案された投
機実行をおこなうスレッディング手法である．キャッシュミスを引き起こした命令および
それに依存する命令列と，キャッシュミスに依存しない命令列をそれぞれ別のスレッドで
同時に実行することで ILP と MLP を抽出し，高い実効性能を達成する．
3.1.1 アーキテクチャ
図 3.1 は，SST の動作に必要なハードウェア機構を表している．灰色部分が SST で追加
されたハードウェアとなる．
追加する主なハードウェアは 3 つある．キャッシュミスした命令などの遅延実行する命
令列を格納する deferred queue（DQ），投機実行中の状態を保存するチェックポイントと
して扱われる投機レジスタファイル（図中 Register Files），そして DQ から供給された命
令の実行時に使用するレジスタファイル（図中 Working Register Files）である．これに加
えて．チェックポイントおよびレジスタファイル内の各レジスタには，そのレジスタが利
用可能であるかどうかを表す Not Available（NA）ビットが追加されている．投機実行中，
キャッシュミスなどにより値をまだ利用できないレジスタには，この NA ビットが立てら
れる．
DQ は，遅延実行する命令の情報だけでなく，命令の実行に必要なオペランドの情報も
Chapter 3 関連研究
12
図 3.1
SST を採用するプロセッサのブロック図 [3]
保持している．これは，命令間のデータ依存関係に起因するハザードを回避するためであ
る．これについては後の項で詳しく述べる．
SST の実行には，DQ と同数のチェックポイントが必要となり，その数は変更可能であ
る．例えば，SST が実装されたプロセッサである ROCK プロセッサ [7] では，DQ および
チェックポイントを 1 コアあたりそれぞれ 2 つ搭載している．DQ の個数およびサイズに
よって，投機実行時に遅延実行が可能な命令の総数が決定される．
3.1.2 SST における命令実行の流れ
SST における命令実行の順序を表したイメージを図 3.2 に示す．横軸は時間経過を表し
ており，左から右の順序で命令を実行していく．図中の小さな正方形 1 つが命令 1 つに
対応しており，正方形内の数字はプログラム中の命令順である．この図では DQ のサイズ
を 4 命令としている．白い命令は非投機実行状態で実行される命令を表し，赤い命令は
キャッシュミスを引き起こすロード命令を，黄色の命令は赤い命令の結果に依存する命令
を表している．緑色の命令は赤や黄色の命令に依存しない命令であり，投機実行状態で処
理される．ただし，この図はあくまでイメージであることに留意する必要がある．例えば，
図では Ahead thread と Behind thread が 1 命令ごとに切り替わっているが，実際の動作で
はそうではない．
まずプログラムの開始時には，プロセッサは非投機実行状態である．この状態では DQ
やチェックポイントは使用されず，命令キャッシュから命令が供給され，通常通りにリタ
イアされて値がレジスタファイルに書き込まれる（図の命令 1）．キャッシュミス等の原
因で，実行が完了できない命令（図の命令 2）に遭遇すると，プロセッサは現在の状態の
チェックポイントをとり（図の Cp0）
，これをコミット済みチェックポイントとして投機実
3.1 Simultaneous Speculative Threading
13
Thread sync
Ahead thread
1
2
3
4
5
6
7
9
10
11
Cp1
Cp0
DQ1
8
2
4
6
7
2
4
12
13
DQ2
9 11
6
7
14
9
15
11
Behind thread
Non Speculative Instruction
Load Miss
Instruction Dependent on Load Miss
Speculative Instruction Independent on Load Miss
図 3.2
SST によるプログラム実行の流れ
行状態へ遷移する．投機実行状態では，それまでと同様に命令キャッシュから命令が供給
されるが，その先の動作が異なる．
投機実行状態において，命令は遅延実行をするものと即時リタイアするものの 2 種類に
分類される．遅延実行をする命令とは，キャッシュミスなどの原因で実行完了に長いサイ
クルを必要とする命令（図の赤色の命令）と，その命令にデータ依存を持つため，命令実
行に必要なレジスタの値が利用不可能になっている命令（図の黄色の命令）のことである．
これらの命令はこの時点でまだ実行を開始できないため，現在書き込んでいる DQ に追加
され，遅延して実行されることとなる．命令の結果を書き込むレジスタには NA ビットが
立てられる．一方，即時リタイアする命令とは，遅延実行をする命令に依存していない命
令（図の緑色の命令）のことである．これらの命令の実行結果はレジスタファイルに書き
込まれ，命令結果を書き込むレジスタの NA ビットはクリアされる．
この方針に従って命令を処理するスレッドを，Ahead thread と呼ぶ．Ahead thread を処
理していくと，DQ の空きが無くなり，これ以上命令を追加できなくなる場合（図の命令 9
Chapter 3 関連研究
14
を追加しようとする時点）が発生する．そのような場合は，現在の状態のチェックポイン
トを取り（図の Cp1）
，命令を追加する DQ を次の DQ（図の DQ2）に変更し，投機実行を
継続する．また，DQ に領域が不足している場合以外でも，DQ を切り替える場合がある．
例えば，遅延実行をする命令の中に分岐命令が含まれていた場合，分岐条件の計算に必要な
レジスタの値が利用不可能なため，分岐の結果が確定できない．そのため，分岐予測ミス
に備えてここでもチェックポイントを取り，次の DQ への追加を開始する．もし DQ の切
り替え時に空いている DQ が無い場合は，命令を遅延実行できないため，現在のチェック
ポイントをコミット不可能とし，命令とデータのプリフェッチのみを行う Hardware scout
thread として動作する．
投機実行中，キャッシュミスからの復帰などで DQ 内の命令が実行可能になると，Ahead
thread とは別に，DQ 内の命令を処理する Behind thread の実行が開始される．Behind
thread では，DQ から最も古い命令を取り出して実行し，結果を Behind thread 用のレジス
タファイル（図 3.1 における灰色の Working Register Files）と DQ に対応する投機レジス
タファイル（図 3.2 の DQ1 の場合は Cp1 に使用した投機レジスタファイル）の両方に書
き込み，命令をリタイアする．ある DQ 内の命令が全てリタイアされた時点（図の Behind
thread における命令 7 の実行完了時）で，DQ に対応するチェックポイント（図の Cp1）に
は，チェックポイントをとった時点（図の命令 8 の実行完了時）におけるアーキテクチャ
ステートが書き込まれている．このため，これを新しくコミット済みチェックポイントと
し，次の DQ からの命令供給を開始し，Behind thread を継続する．
Behind thread の実行中に，遅延実行した分岐命令の分岐予測ミスが発覚した場合，Ahead
thread と Behind thread 両方の実行を中止し，最後にコミットしたチェックポイントから非
投機実行状態で命令実行を再開する．例えば，図 3.2 の命令 9 が分岐命令であり，分岐予
測ミスをしていた場合は，最後にコミットしたチェックポイントである Cp1 からの実行再
開となる．
SST では，命令を DQ に追加する Ahead thread と DQ 内の命令を処理する Behind thread
を同じコアで同時に平行して実行する．そして，全ての DQ から命令がリタイアされた場
合（図の Behind thread における命令 11 のリタイア時）
，2 つのスレッドを統合する Thread
sync を行い，投機実行状態を終了させる．Thread sync とは，Ahead thread と Behind thread
のレジスタを統合してアーキテクチャの状態を生成する作業であり，Ahead thread で使用
したレジスタファイルの NA ビットを参照し，NA ビットが立っていれば Behind thread の
値を，そうでなければ Ahead thread の値を採用する．これによって生成される 2 つのス
レッドの結果を反映させたレジスタファイルを用いて，非投機実行状態を再開する．
3.1 Simultaneous Speculative Threading
15
3.1.3 SST の利点
SST の利点は，メモリレベル並列性と命令レベル並列性の両方を活用することによって，
ハードウェア量の少ないインオーダコアでアウトオブオーダコアのような効率的な命令実
行が行えることである．一般的なアウトオブオーダコアには，複雑かつ消費電力の大きい
多くの機構が必要となるため，インオーダコアで高い性能を達成できる SST は，優れたス
レッディング手法と言える．
3.1.4 データハザードの扱い
SST では，投機実行中に独立した 2 つのスレッドを同時に並行して実行する．しかし，2
つのスレッドで実行する命令の間には依存関係が存在するため，データハザードを適切に
処理する必要がある．
Read-After-Write ハザード
RAW ハザードには，NA ビットが使用される．命令実行に必要な全てのレジスタの NA
ビットがクリアされ，利用可能にならない限り命令はリタイアされないため，命令は適切
に実行される．
Write-After-Read ハザード
Ahead thread において命令を DQ に追加する際，命令自体の情報だけでなく，命令に必
要なオペランド（その時点で利用可能なもののみ）も DQ に格納し，その値を利用して命
令を実行する．そのため，遅延した命令より後の命令がレジスタファイルを更新した場合
でも，DQ に格納されている値は上書きされないため，WAR ハザードは回避される．
Write-After-Write ハザード
WAW ハザードは，Thread sync によって除去される．レジスタに最後に書き込む命令が
Ahead thread で処理される場合（リタイア可能命令の場合）は，Ahead thread で使用する
レジスタファイルの NA ビットがクリアされるため，Ahead thread の結果が採用される．
一方最後に書き込む命令が Behind thread で処理される場合（遅延可能命令の場合）は，
Ahead thread で使用するレジスタファイルの NA ビットが立っているため，Behind thread
の結果が採用される．どちらの場合でも，レジスタに最後に書き込む命令の結果が採用さ
れるため，WAW ハザードは除去される．
Chapter 3 関連研究
図 3.3
図 3.4
16
SST における各ベンチマーク実行時の投機状態の割合 [3]
SST から各種の投機失敗を取り除いた場合の性能向上率 [3]
3.1.5 課題
前述したように，投機実行中に条件判定に必要なレジスタが利用不可能な分岐命令を発
見した場合は，命令を DQ に送って遅延実行し，Behind thread で分岐条件を判定すること
となる．しかし，このときに分岐予測ミスが発覚した場合，この分岐命令以前にコミット
された最新のチェックポイントから再開するため，投機実行によって得た結果の大部分は
利用できなくなる．
図 3.3 は，SST における各ベンチマーク実行時の投機状態の割合を表したものである．
ほとんどのベンチマークで投機実行状態（図の黒の部分）の割合が大きいため，分岐予測
ミス率が高い場合は，SST における性能向上がかなりの割合で抑制されていると考えられ
る．図 3.4 は SST における投機失敗を取り除いた理想的な環境での性能向上率を表してい
る．これによると，分岐の結果が初回実行時に判明するとした場合，商業的ベンチマーク
では 20% 弱，SPEC2006 の整数ベンチマークでも 10% 程度の性能向上が見込まれており，
SST において分岐予測ミスは，実効性能に大きな影響を与えることが分かる．
3.2 ALU カスケーディング
17
R1
R1 = R1+R2
ALU1
R1
R2
R1
R1 = R1+R3
R1
ALU2
R1
R3
図 3.5
ALU カスケーディングにおける命令実行の例
3.2 ALU カスケーディング
ALU カスケーディングとは，複数の演算器を並べて各演算器の間にパスを設けることに
よって，依存関係にある複数の命令を 1 サイクルで実行する手法であり，この手法を用い
て様々な研究が行われている [8][9]．
ALU カスケーディングを利用した命令実行の例を図 3.5 に示す．データ依存関係のある
2 命令を実行する場合，後の命令は最初の命令の結果を用いて計算を行うため，通常はそ
れぞれ別のサイクルに命令実行をおこなう必要がある．しかし ALU カスケーディングの
場合，ALU1 と ALU2 の間にあるパス（図の赤線部分）を利用することで，前の命令の結
果のフォワーディングを行い，依存関係にある 2 つの命令を同時に実行することが可能と
なる．
上野らは，ALU カスケーディングを非同期式プロセッサに適用することを提案した [8]．
非同期式プロセッサでは，同期式プロセッサと違いクロックによって実行タイミングを均
一化しない．そのため，データ依存関係のある命令列を直列に処理することができる ALU
カスケーディングの利点を，最大限に活用することが可能だとしている．
尾形らは，ALU カスケーディングをアウトオブオーダプロセッサに適用する際に必要と
なる，データ依存関係のある命令列を同時に発行するスケジューラを提案した [9]．これに
より，アウトオブオーダプロセッサの性能が平均で 3.8% 向上したとしている．
Chapter 3 関連研究
18
3.3 SST と ALU カスケーディングの統合
SST を改良した新たなスレッディング手法と，それに ALU カスケーディングを組み合
わせたプロセッサが松村らによって提案されている [4]．本節ではその概要を述べる．
3.3.1 SST を改良したスレッディング手法
松村らは，SST の実効性能が分岐予測ミスの影響を大きく受けることに注目し，投機実
行時の分岐予測ミスを早期に発見する新たなスレッディング手法を提案した．
図 3.6 は SST における命令実行の例を表し，図 3.7 は松村らの提案した SST における命
令実行の例を表している．従来手法の問題点として，分岐予測ミスは SST の性能に大きな
影響を与えるにもかかわらず，遅延実行する分岐命令の実行タイミングが遅いという点が
挙げられる．その原因として，SST では Ahead thread と Behind thread を同時に並行して
実行するため，コアのリソースがスレッドごとに分割されることが考えられる．
松村らはこの問題を解決するため，Behind thread が実行可能になった段階で Ahead
thread の実行を停止し，Behind thread のみを実行する手法を提案した．これにより，遅延
実行する分岐命令の実行タイミングを早めることが可能になるだけでなく，Ahead thread
を停止することで遅延実行命令の増加を抑え，投機実行時間を最小限のものとすることが
可能となる．
図 3.6 および図 3.7 において，命令 9 が分岐命令だった場合を考える．従来手法では，
Ahead thread と Behind thread を平行して実行させていたため，命令 9 の分岐条件を評価
するタイミングが遅く，また命令 11 のような新たな遅延実行命令を生み出していた．しか
し松村らの手法では，Behind thread のみの実行とするため命令 9 の実行タイミングが早く
なり，かつ新たな遅延実行命令の追加を抑え，投機実行時間を減らすことに成功している．
3.3.2 ALU カスケーディングとの併用
松村らは，SST の新たなスレッディング手法の他に，SST と ALU カスケーディングを
併用することを提案した．SST において遅延実行される命令とは，キャッシュミスを引き
起こすロード命令と，それらに依存する命令である．そのため，Behind thread で実行され
る命令列は必然的に命令間の依存関係が多いものとなる．ALU カスケーディングは依存
関係にある命令列の効率的な実行に適しているため，SST と ALU カスケーディングを併
用することで，Behind thread の実行効率を高めることができる．
図 3.8 は，Behind thread で実行される命令列の例である．それぞれの命令が，直前の命
3.3 SST と ALU カスケーディングの統合
19
Thread sync
Ahead thread
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DQ2
9 11
15
Cp1
Cp0
DQ1
2
4
6
7
2
4
6
7
9
11
Behind thread
図 3.6
SST によるプログラム実行の流れ
Thread sync
Ahead thread
1
2
3
4
5
6
7
9
10
Cp1
Cp0
DQ1
8
2
4
6
DQ2
7
2
4
6
9
7
9
Behind thread
Non Speculative Instruction
Load Miss
Instruction Dependent on Load Miss
Speculative Instruction Independent on Load Miss
図 3.7
松村らの提案した SST によるプログラム実行の流れ
Chapter 3 関連研究
20
/ŶƐƚϭ
/ŶƐƚϮ
/ŶƐƚϯ
/ŶƐƚϰ
図 3.8
ĂĚĚ
ĂĚĚ
ĂĚĚ
ĂĚĚ
Ψϯ
Ψϱ
Ψϳ
Ψϵ
Ψϭ
Ψϰ
Ψϲ
Ψϴ
ΨϮ;EͿ
Ψϯ;EͿ
Ψϱ;EͿ
Ψϳ;EͿ
ALU カスケーディングによって効率的に実行できる命令列 [4]
㻭㻸㼁㻌㼏㼍㼟㼏㼍㼐㼕㼚㼓
㼣㼛㼞㼗㼟㻚
㻭㼘㼘㻌㼑㼤㼑㼏㼡㼠㼕㼛㼚㻌㼏㼥㼏㼘㼑㼟
㻭㼘㼘㻌㼑㼤㼑㼏㼡㼠㼕㼛㼚㻌㼏㼥㼏㼘㼑㼟
㻿㼜㼑㼏㼡㼘㼍㼠㼕㼢㼑㻌㼠㼔㼞㼑㼍㼐㼕㼚㼓
㼣㼛㼞㼗㼟
㻿㼜㼑㼏㼡㼘㼍㼠㼕㼢㼑㻌㼠㼔㼞㼑㼍㼐㼕㼚㼓
㼣㼛㼞㼗㼟
㻭㻸㼁㻌㼏㼍㼟㼏㼍㼐㼕㼚㼓
㼣㼛㼞㼗㼟㻚
㻼㼕㼜㼑㼘㼕㼚㼑㻌㼕㼟㻌㼞㼍㼞㼑㼘㼥㻌㼟㼠㼍㼘㼘㼑㼐
㻼㼕㼜㼑㼘㼕㼚㼑㻌㼕㼟㻌㼟㼠㼍㼘㼘㼑㼐㻌㼢㼑㼞㼥㻌㼛㼒㼠㼑㼚
㻼㼕㼜㼑㼘㼕㼚㼑㻌㼕㼟㻌㼟㼠㼍㼘㼘㼑㼐㻌㼎㼥㻌㼏㼍㼏㼔㼑㻌㼙㼕㼟㼟
㻼㼕㼜㼑㼘㼕㼚㼑㻌㼕㼟㻌㼟㼡㼜㼜㼘㼕㼑㼐㻌㼛㼒㻌㼕㼚㼟㼠㼞㼡㼏㼠㼕㼛㼚㼟
図 3.9
アプリケーションがメモリインテンシブな場合とそうでない場合の例 [4]
令の結果を利用して計算を行っている．通常は，直前の命令の結果をフォワーディングす
るために命令の実行サイクルを分ける必要があるため，この命令列の実行には 4 サイクル
必要となる．しかし，ALU カスケーディングを利用することで，この命令列を 2 サイクル
で実行することが可能となる．
また，ALU カスケーディングとの併用は，Behind thread だけでなく全体的な性能の向
上を可能とする．SST は，キャッシュミスが頻繁に発生するようなアプリケーションの性
能向上に向いているが，そうでないアプリケーションに対しては効果が薄い．一方 ALU
カスケーディングは，パイプラインに演算命令が十分に供給されるアプリケーションの性
3.3 SST と ALU カスケーディングの統合
21
cycle
1
2
3
4
5
load R2, 0(R1)
IF
ID
EX
MA
WB
add R4, R2, R3
IF
ID
EX
6
7
MA
WB
図 3.10 ALU カスケーディングが効率的に動作していない場合の例 [4]
能向上に向いているが，キャッシュミスなどによってパイプラインがストールするアプ
リケーションに対しては効果が薄い．SST と ALU カスケーディングはこのような異なる
特色を持つため，この二つを併用することで，様々なアプリケーションに対する性能向上
が可能と考えられる．そのイメージを図 3.9 に示す．右側はメモリインテンシブなアプリ
ケーションであり，左側はそうでないアプリケーションである．どちらの場合でも，SST
または ALU カスケーディングのどちらかが効果を発揮し，性能向上が期待できることが
分かる．
3.3.3 ALU カスケーディングの課題
[4] によると，Behind thread における ALU カスケーディング適用率が全体よりも低い
場合が多く，SST と ALU カスケーディングによる相乗効果が想定通りに発生していない
ことが示されている．その原因として，Behind thread ではキャッシュミスを引き起こした
ロード命令とそれに依存する命令が連続する場合が多く，そのような命令列を ALU カス
ケーディングで効率的に処理できていない可能性が挙げられている．
図 3.10 はその例である．一般的な 5 段のパイプラインにおいて，ロード命令とそれに依
存する命令が連続している場合，ロード命令の結果をバイパスするため，後続の命令は 2
サイクルストールする必要がある．そのため，依存する命令列を ALU カスケーディング
によって処理できず，ALU カスケーディング適用率が下がっていると考えられる．
3.3.4 改良スレッディング手法の課題
提案されたスレッディング手法によって，分岐予測ミスの早期発見が可能となった．し
かし，この手法では Behind thread の開始後，Ahead thread の実行を完全に停止してしまう
ため，キャッシュミスを引き起こす命令が複数遅延されていた場合，Behind thread の実行
中にキャッシュミスからの回復を待つストール状態が発生してしまう可能性がある．
そのような例を図 3.11 に示す．図では Ahead thread によって，キャッシュミスを発生
させた 3 つのロード命令が DQ に追加されている．最初のロード命令（命令 2）がキャッ
シュミスから回復した時点で Ahead thread の実行を停止し，Behind thread のみの実行に
Chapter 3 関連研究
22
Thread sync
Ahead thread
1
2
3
4
5
6
7
Cp0
DQ1
8
9
Cp1
2
4
5
DQ2
7
2
4
5
8
7
8
Behind thread
Non Speculative Instruction
Load Miss
Instruction Dependent on Load Miss
Speculative Instruction Independent on Load Miss
Waiting for Load Miss (STALL)
図 3.11 改良スレッディング手法においてストールが発生する例
切り替わる．しかし，この時点で Behind thread で実行できる命令は，命令 2 に依存する命
令（命令 4）までであり，命令 5 の実行には，キャッシュミスからの回復を待たなければ
ならない．従来のスレッディング手法では Ahead thread と平行して実行するため，Behind
thread がストールしていても Ahead thread を実行することが可能であった．しかし提案さ
れたスレッディング手法では，遅延実行命令の追加発行を防ぎ，投機実行時間を最小限に
するために Ahead thread を停止させているため，完全にストールする時間が発生してしま
うと考えられる．
23
第4章
新たなスレッディング手法の提案
前章では，SST と ALU カスケーディング，そしてその両者を併用するプロセッサにつ
いて述べ，その長所と問題点について説明した．本章では，前章で説明した問題点を解決
するための提案手法について述べる．
4.1
提案するロード命令の処理手法
4.1.1 概要
前章では，Behind thread における ALU カスケーディング適用率がプログラム全体より
も低い場合が多いこと，そしてその原因として，ロード命令とそれに依存する命令列を
ALU カスケーディングによって効率的に処理できていないことを述べた．
しかし SST では，キャッシュミスを引き起こしたロード命令が実行可能になった時点，
すなわちデータキャッシュから値が返ってきた時点で Behind thread が開始される．した
がって，Behind thread が開始される時点で，ロードした結果はロードストアキューに格納
されていることになる．
そこで，これらの問題点を解決するために，Ahead thread においてアドレス計算が終
わっているロード命令については，命令実行時にロードストアキューから値を取得する
のではなく，あらかじめ DQ にロード結果を格納することを提案する．前述したように，
データハザードを除去するため，DQ には命令実行に必要な値を格納する領域がすでに存
在しており，かつその値を用いて命令を実行するパスもすでに用意されている．これを利
用し，ロードした値を DQ に格納しておき，該当するロード命令は DQ に格納された値を
供給する命令として動作させることで，ロード命令とそれに依存する命令列を ALU カス
ケーディングによって効率的に処理できると考えられる．
図 4.1 は提案手法を用いた場合の処理の例である．5 段のパイプラインを持つプロセッ
Chapter 4 新たなスレッディング手法の提案
24
cycle
1
2
3
4
5
6
7
load R2, 0(R1)
IF
ID
EX
MA
WB
add R4, R2, R3
IF
ID
EX
MA
WB
6
7
stall
cycle
1
2
3
4
5
load R2, 0(R1)
IF
ID
EX
MA
WB
add R4, R2, R3
IF
ID
EX
MA
WB
Load data
ALU cascading
2 cycles
In DQ
shorter
図 4.1
提案手法による実行サイクル短縮の例
サにおける動作を想定し，上が従来手法，下が提案手法となっている．従来手法ではロー
ド命令の結果を MA ステージで取得してから値を次の命令にフォワーディングするため，
依存関係にある後続命令の実行には 2 サイクルのストールが必要となっていた．提案手法
ではロードした値を DQ に格納しておき，その値を供給する命令として動作させるため，
ALU カスケーディングによってロードした値をフォワーディングすることができ，命令列
の処理に要するサイクルが短縮されている．
4.1.2 アーキテクチャ
提案手法のブロック図を図 4.2 に示す．これは，一般的な 5 段パイプラインに SST を実
装し，提案手法を加えたものである．図の赤線部分が提案手法で追加した部分となる．
データキャッシュから返ってきた値をロードストアキューだけでなく DQ にも格納する
パスを追加することで，ロード結果をストールすることなく EX ステージで活用すること
ができ，ロード結果に依存する命令を ALU カスケーディングによって効率的に処理でき
るようになると考えられる．
4.2 新たに提案するスレッディング手法
25
Behind
RF
D$
LSQ
DQ
DQ
DQ
Exec
Fetch
Decode
Ahead
RF
図 4.2
4.2
MA
Checkpoint
Checkpoint
Checkpoint
RFRF
RF
提案手法のブロック図
新たに提案するスレッディング手法
前章において，改良スレッディング手法では Ahead thread の実行を完全に停止させるた
め，Behind thread の実行時にストール状態が発生してしまう可能性があることを述べた．
そこで，問題点を解決するために，Behind thread が実行可能な時は Behind thread のみ
を，Behind thread がストールしている場合は Ahead thread のみを実行するスレッディン
グ手法を提案する．前述した提案手法を活用し，DQ の先頭の命令がロード命令であった
場合，ロード結果がまだ DQ に格納されていない場合は Ahead thread を実行し，そうでな
い場合は Behind thread を実行する．
Behind thread においてストールが発生した場合の，従来手法と提案手法での実行例を
図 4.3 と図 4.4 に示す．前述した方法によるスレッド切り替えにより，従来手法で Behind
thread がストールしている間，提案手法では Ahead thread を進めることが可能となる．こ
れにより，Behind thread のストールサイクルを有効に活用することができる．また提案手
Chapter 4 新たなスレッディング手法の提案
26
Thread sync
Ahead thread
1
2
3
4
5
6
7
Cp0
8
9
Cp1
DQ1
2
4
5
DQ2
7
2
4
5
8
7
8
Behind thread
図 4.3
従来手法によるストール発生時の実行例
Thread sync
Ahead thread
1
2
3
4
5
6
7
Cp0
DQ1
8
9 10 11
Cp1
2
4
5
12 13 14
DQ2
7
2
4
5
15
8 10
7
8 10
Behind thread
Non Speculative Instruction
Load Miss
Instruction Dependent on Load Miss
Speculative Instruction Independent on Load Miss
Waiting for Load Miss (STALL)
図 4.4
提案手法によるストール発生時の実行例
4.2 新たに提案するスレッディング手法
27
法では，Behind thread が実行可能な時は Ahead thread の実行を一時停止し，Behind thread
のみに注力するため，分岐予測ミスの検出を早めるという従来手法の利点を損なわずに投
機実行を続行することができる．投機実行を続行することで遅延実行命令を増加させてい
くため，従来手法より投機実行時間は長くなることが予想される．しかし，Behind thread
の命令実行タイミングは従来手法とほぼ変わらないため，分岐予測ミスを早期に発見でき
る点は変わっておらず，むしろ正しいパスを実行していた場合には投機実行による結果を
活用できるため，従来手法よりも効率的にアプリケーションを実行できると考えられる．
29
第5章
提案手法の評価
前章では，SST の性能を向上させる新たなスレッディング手法を提案した．本章では提
案手法についてシミュレータを用いて評価し，その有用性について検証する．
5.1
評価環境
表 5.1
評価に用いたプロセッサのパラメータ
Pipeline
IF, ID, EX, MA, WB
PipeLine way
2
L1 I-cache
32KB 4-way, 1 cycle, 64B line
L1 D-cache
32KB 4-way, 1 cycle, 64B line
L2 cache
4MB 8-way, 25cycle, 64B line
Main Memory
300 cycle latency
Branch predictor
Bi-mode, 6bit GHR, 1k entries PHT
Branch target buﬀer
1k entries, 2-way
Load Store Queue
256 entries
DQ size
16 entries
Checkpoints
16
評価に用いるシミュレータとして，Linux 上で動作する MIPS システムレベルシミュ
レータである SimMips[10] を拡張したものを使用した．シミュレータには評価対象となる
アーキテクチャとして，以下の 5 つを実装した．
Chapter 5 提案手法の評価
1.
2.
3.
4.
5.
30
2way インオーダスーパースカラプロセッサ
1 に ALU カスケーディングを追加したもの
2 に松村らの提案する SST を追加したもの
3 に提案するロード命令処理手法を追加したもの
4 に提案する新たなスレッディング手法を追加したもの
評価に使用するプロセッサのパラメータは表 5.1 の通りである．評価に使用するベン
チマークには，SPEC2006 整数ベンチマーク（bzip2 gcc mcf libquantum h264ref omnetpp
astar）を使用した．これらのベンチマークに対し，最初の 1G 命令をスキップし，続く
100M 命令を評価対象とした．
5.2
提案手法による性能変化
まず，前章で提案した 2 つの提案手法が性能に与える影響を評価する．各ベンチマーク
実行時の IPC を図 5.1 に，従来の SST に対する提案手法の IPC 増加率を図 5.2 に示す．図
5.1 の 5 種類のデータ系列は，前述した 5 つのアーキテクチャに対応しており，青色の系
列は提案したロード命令処理手法のみの場合であり，赤色の系列は 2 つの提案手法の両方
を実装した場合である．
提案手法によって，従来の SST と比較して IPC が向上することが確認できた．7 種のベ
ンチマークの調和平均において，提案したロード命令処理手法では IPC が 0.51% 向上し，
提案したスレッディング手法と組み合わせると IPC が 1.23% 向上した．最も向上の幅が
大きかった mcf では，IPC が 2.00% 向上した．
5.3
提案したロード命令処理の効果
本項では，提案したロード命令処理手法の効果について評価する．
5.3.1 ALU カスケーディング適用率
前章では，Behind thread において ALU カスケーディングが十分に機能しない状況が存
在し，提案手法によってそのような場合でも ALU カスケーディングが効率的に行われる
ようになることを述べた．本項ではこの予想の妥当性を検証する．
評価のための指標として，ALU カスケーディング適用率を使用する．ここでは ALU カ
スケーディング適用率を，「実行命令数に対する ALU カスケーディング適用回数」と定義
している．ALU カスケーディング適用率が高いほど，ALU カスケーディングによって命
令が効率的に実行されていることを表している．
5.3 提案したロード命令処理の効果
SS
ALU cascading
SST
31
SST+proposed Load
SST+all proposed method
1.6
1.4
e
l
c
y
c
r
e
p
n
o
i
t
c
u
r
t
s
n
I
1.2
1
0.8
0.6
0.4
0.2
0
bzip2
gcc
mcf
図 5.1
libquantum h264ref
omnetpp
astar
hmean
各ベンチマークの IPC
SST+proposed Load
SST+all proposed method
2.5
2
)
%
( 1.5
o
i
t
a
r
1
g
n
i
s
a
e 0.5
r
c
in
C
P
I
0
-0.5
-1
bzip2
gcc
図 5.2
mcf
libquantum h264ref
omnetpp
各ベンチマークの IPC 変化率
astar
hmean
Chapter 5 提案手法の評価
SST
32
SST+proposed Load
SST+all proposed method
40
) 30
%
(
io
ta
r
20
d
e
d
ac
sa
C
10
0
bzip2
図 5.3
gcc
mcf
libquantum h264ref
omnetpp
astar
total
命令再実行時における ALU カスケーディング適用率
遅延した命令の再実行時における ALU カスケーディング適用率を図 5.3 に示す．図の
total とは全ベンチマークの総遅延実行命令数に対する，全ベンチマークにおける遅延実行
時の ALU カスケーディング回数の合計値の割合である．
従来の SST における遅延実行時の ALU カスケーディング適用率は全体で 6.07% である
のに対し，提案するロード命令処理手法では全体で 7.06%，さらに提案するスレッディン
グ手法と組み合わせると全体で 8.68% となり，提案手法によって遅延実行時に ALU カス
ケーディングが効率的に動作していることが確認できた．
5.3.2 bzip2 における提案手法の効果
図 5.2 によると，提案したロード命令処理手法によって，ほとんどのベンチマークで性
能向上が確認され，平均で 0.5%，最大で 1.29% 性能が向上している．しかし bzip2 の場
合，提案したロード命令処理手法によって IPC が 1% 弱低下しており，提案したスレッ
ディング手法と組み合わせた場合のみ性能が向上している．
また図 5.3 によると，多くのベンチマークでは主に提案したロード命令処理手法によっ
て ALU カスケーディング適用率が向上しており，提案したスレッディング手法と組み合
5.3 提案したロード命令処理の効果
33
わせた場合にはあまり ALU カスケーディング適用率の向上がみられていない．しかし，
bzip2 では 2 つの提案手法を組み合わせることによって ALU カスケーディング適用率が大
幅に向上している．
図 5.4 と図 5.5 に，bzip2 を実行した際の時間経過に伴う IPC 向上率の変化を示す．上は
提案したロード命令処理手法のみの場合であり，下は提案したスレッディング手法と組み
合わせた場合である．横軸は時間経過であり，評価の対象とした 100M 命令の処理時に，
従来の SST に比べどれだけ IPC が向上したかを表している．
提案したロード命令処理のみの場合，IPC が向上している部分はあるものの，ほとんど
の場面で逆に IPC が低下している．しかし提案したスレッディング手法と組み合わせた場
合，上の図で IPC が低下していた場面のほとんどで IPC が上昇していることが確認でき
る．特に一部の場面では，IPC が 20% 以上向上していることが分かる．
この原因として，従来のスレッディング手法の問題点であった，Behind thread で発生
するストール状態が考えられる．図 4.3 が示す通り，従来のスレッディング手法では，遅
延実行させたロード命令のうち，最初の命令のキャッシュミスペナルティの間しか投機実
行が行われない．図では命令 2，5，8 の 3 つのロード命令が遅延実行されているものの，
命令 2 のキャッシュミスを処理している間しか投機実行が行われず，命令 5 および 8 の
キャッシュミスの処理の間はストール状態となっている．そのため，提案したロード命令
処理手法によって ALU カスケーディングを効率的に動作させ，1 回の投機実行の間に DQ
へ追加されるロード命令を増加させた場合，Behind thread で発生するストール状態が長く
なってしまうと考えられる．
図 5.6 にその例を示す．図中の小さな正方形 1 つが命令 1 つに対応しており，正方形内
の数字はプログラム中の命令順である．灰色の正方形はストール状態を表す．図中の橙色
の長方形はキャッシュミスのペナルティを表しており，数字は対応するロード命令の番号
である．各命令列は，上から順番に従来手法の場合，提案したロード命令処理手法のみの
場合，提案したロード命令処理手法と提案したスレッディング手法を組み合わせた場合で
ある．提案手法の効果によって，下 2 つの命令列は命令 1 の実行タイミングが上よりも早
くなっている．ただし，データキャッシュが別のミスを処理しているため，命令 1 の結果
が返ってくるタイミングはどちらも同じとする．
従来手法の場合では，Ahead thread の間に 5 命令を処理し，うち 2 命令（命令 1 および
3）を DQ に送っている．そして Behind thread で 2 命令を処理し，Thread Sync を行って
非投機状態に戻る．しかし次の命令（命令 6）がキャッシュミスを引き起こすため，再び
Ahead thread が開始されている．一方，提案したロード命令処理手法を利用する場合（下
2 つ）では最初の Ahead thread で 6 命令を処理し，うち 3 命令（命令 1，3，6）を遅延実
行した後 Thread sync を行っている．
提案したロード命令処理手法のみの場合では，Behind thread の実行時にストール状態と
Chapter 5 提案手法の評価
34
125
120
)
%
(
o
i
t
a
r
g
n
i
s
a
e
r
c
in
115
110
C
P
I
105
100
95
time
図 5.4
提案したロード手法を行った場合の SST に対する IPC 変化率
125
120
)
%
(
o
i
t
a
r
g
n
i
s
a
e
r
c
n
i
C
P
I
115
110
105
100
95
time
図 5.5 提案したスレッディング手法と組み合わせた場合の IPC 変化率
5.3 提案したロード命令処理の効果
Ahead
1
2
35
Behind
3
4
5
1
3
1
SST
2
3
6
7
3
9 10 6 11 12 13
8
6
Behind
Ahead
1
Behind
Ahead
4
5
6
1
3
1
3
6
7
8
9 10 11
6
SST + proposed Load
Ahead + Behind
Ahead
1
2
3
4
5
6
1
1
7
8
9
3
3 10 11 12 6 13 14 15 16 17
6
SST + proposed Load + proposed Threading
Non Speculative Instruction
Load Miss
Instruction Dependent on Load Miss
Speculative Instruction Independent on Load Miss
Waiting for Load Miss (STALL)
Cache miss penalty
図 5.6
提案したロード命令処理手法において性能が低下する場合の例
Chapter 5 提案手法の評価
36
なる時間が増加するため，従来手法よりも早く命令 1 を実行し，Ahead thread の間に多く
命令を処理できたにもかかわらず，命令 11 の実行タイミングは従来手法よりも遅くなって
しまっている．しかし，提案したスレッディング手法を組み合わせた場合では，ストール
状態の間も投機実行を行うことにより，命令 11 を早く実行することが可能になっている．
これが，提案したロード命令処理のみの場合は性能が低下し，提案したスレッディング手
法と組み合わせると性能が向上する原因だと考えられる．
5.4
提案したスレッディング手法の効果
本項では，提案したスレッディング手法の効果について検証する．
5.4.1 SST の実行状態の変化
前章では，改良スレッディング手法において Behind thread の実行時にストール状態が
発生してしまう可能性があり，提案するスレッディング手法によってストール状態を有効
に活用することが可能となることを述べた．本項ではこの予想の妥当性を検証する．
SST の実行時，プロセッサは次の 4 つの状態を遷移することとなる．
Nonspeculative 非投機実行状態．命令は通常通りリタイアされる．
Speculative 投機実行状態．Ahead thread によって遅延実行する命令を DQ に追加する．
Reexec 命令の再実行状態．Behind thread によって DQ 内の命令を実行する．
HWS Ahead thread によって命令とデータのプリフェッチのみを行っている状態．
提案手法では，命令の再実行状態に発生するストールを投機実行に活用するため，命令再
実行状態の割合が減少し，投機実行状態の割合が増加すると考えられる．
各ベンチマーク実行時の SST の状態変化の割合を図 5.7 に，実行状態の割合の変化率を
図 5.8 に示す．図の total とは，全ベンチマークの総実行時間に対する，各状態の総実行
時間の割合の変化率である．提案手法では命令の再実行状態が全体で 19.3% 減少し，投機
実行状態が 30.9% 増加している．非投機実行状態は 0.92% の減少，プリフェッチ状態は
7.08% の減少となっており，投機実行状態や命令の再実行状態に比べると変化量は小さい
ものとなっている．
これは，従来手法において命令の再実行時に発生していたストール状態を，提案手法で
は投機実行を行うことで有効に活用しているためだと考えられ，提案手法によって命令再
実行時のストール状態が投機実行状態へと想定通りに変化していることが確認できた．
5.4 提案したスレッディング手法の効果
NonSpeculative
37
Speculative
Reexec
HWS
100%
n
w 80%
o
d
k
a
e
r 60%
B
e
im
T 40%
n
o
it
u
c
e
xE 20%
0%
T
S
S
T
S
S
d
e
s
o
p
o
r
P
bzip2
T
S
S
d
e
s
o
p
o
r
P
gcc
d
e
s
o
p
o
r
P
mcf
図 5.7
NonSpeculative
T
S
S
T
S
S
d
e
s
o
p
o
r
P
d
e
s
o
p
o
r
P
libquantum h264ref
T
S
S
d
e
s
o
p
o
r
P
omnetpp
T
S
S
astar
SST の実行状態の割合
Speculative
Reexec
HWS
100
)
%
( 80
io
t 60
ar
g 40
n
is
a
e
rc 20
in
e 0
m
i
T -20
n
o
it -40
u
c
e
xE -60
-80
bzip2
gcc
mcf
libquantum h264ref
omnetpp
図 5.8 SST の実行状態の割合の変化率
astar
total
d
e
s
o
p
o
r
P
Chapter 5 提案手法の評価
38
12
e
m
it
n
io
ta
l
u
ce
p
S
f
o
eg
at
n
ec
re
P
10
) 8
%
(
t
n
e 6
m
er
c
in 4
2
0
bzip2
gcc
mcf
libquantum h264ref
omnetpp
astar
total
図 5.9 全実行時間に対する投機実行状態の増加分の割合
5.4.2 分岐予測ミスの影響
全実行時間に対する，投機実行状態の増加分の割合を図 5.9 に示す．図の total とは，全ベ
ンチマークの総実行時間に対する，投機実行状態の増加分の総計の割合である．libquantum
や h264ref，omnetpp などの，投機実行状態の割合が比較的小さいベンチマークでは，投機
実行状態の増加分は全実行時間の 2% 未満と非常に小さいものとなっている．一方，bzip2
や mcf，astar などの投機実行状態の割合が比較的大きいベンチマークでは，投機実行状態
の増加分が全実行時間の 6% 以上となっている．この投機実行状態の増加分は，元々は命
令再実行時のストール状態であるため，投機実行状態の割合が大きく，多くの命令を遅延
実行するベンチマークほど提案手法が有効に機能すると考えられる．
しかし，図 5.2 が示すように，投機実行状態の増加幅が比較的大きいベンチマークにお
いても，投機実行の増加分に比べて性能向上の幅はわずかなものとなっている．この理由
として，分岐予測ミスの影響が考えられる．
第 3 章で述べたように，SST は分岐予測ミスの影響を受けやすいスレッディング手法で
あり，分岐予測ミス率が高い場合は SST による性能向上が大幅に抑制されることが分かっ
ている．そのため，提案手法によってストール状態を投機実行に活用したとしても，分岐
予測ミス率が高い場合は，投機実行の大部分が無効なものとなってしまう可能性がある．
5.4 提案したスレッディング手法の効果
39
Failed Speculation
Succeeded Speculation
100%
n
w
o 80%
d
k
a
e
r
B 60%
e
im
T
n 40%
o
it
a
l
u
c 20%
e
p
S
0%
T
S
S
d
e
s
o
p
o
r
P
bzip2
図 5.10
T
S
S
gcc
d
e
s
o
p
o
r
P
T
S
S
mcf
d
e
s
o
p
o
r
P
T
S
S
d
e
s
o
p
o
r
P
T
S
S
T
S
S
d
e
s
o
p
o
r
P
libquantum h264ref
d
e
s
o
p
o
r
P
omnetpp
T
S
S
d
e
s
o
p
o
r
P
astar
投機実行時間における無効な投機実行の割合
投機実行時間のうち，無効な投機実行の割合を図 5.10 に示す．図中 Succeeded Specu-
lation とは，処理した命令の結果が活用された投機実行のことであり，Failed Speculation
とは，分岐予測ミスが発生したため，処理した命令の結果を破棄した投機実行のことであ
る．libquantum や h264ref では有効な投機実行の割合が大きく，無効な投機実行が投機実
行時間の 20% 未満に留まっているのに対し，その他のベンチマークでは無効な投機実行が
40% 以上存在しており，分岐予測ミスによって投機実行による性能向上が抑制されている
ことが確認できる．
また，提案手法によって投機実行状態の総量が増加し，それに伴って分岐予測ミスが発
生する機会も増加したため，全体的に有効な投機実行の割合が減少している．これは特に
bzip2 や mcf において顕著であり，これによって投機実行の増加分が相殺されてしまって
いる可能性がある．
全実行時間に対する，有効な投機実行の増加分の割合を図 5.11 に示す．図の total とは，
全ベンチマークの総実行時間に対する，有効な投機実行の増加分の総計の割合である．全
てのベンチマークにおいて，有効な投機実行状態の増加分は全実行時間の 1% 未満と非常
Chapter 5 提案手法の評価
n
io
ta
l
u
ce
p
s
d
e
d
ee
cc
u
S
f
o
eg
at
n
ec
re
P
40
1
0.8
)
%
(
t
n
e 0.6
m
er
c
in0.4
e
m
it
0.2
0
bzip2
gcc
mcf
libquantum h264ref
omnetpp
astar
total
図 5.11 全実行時間に対する有効な投機実行状態の増加分の割合
に小さなものとなっており，図 5.9 と比較すると，投機実行状態の増加分の多くは分岐予
測ミスによって無効になってしまったことが確認できる．
5.5
今後の課題
これまで述べてきたように，提案したロード命令処理手法および提案したスレッディン
グ手法は，ALU カスケーディング適用率の向上や投機実行状態の割合の増加といった形で
効果が確認された．しかしこれらの効果は性能向上にあまり寄与せず，結果として 1% 程
度の性能向上に留まっている．
その原因として，SST による性能向上の限界が挙げられる．図 3.9 に示した通り，SST
の性能向上幅はまずアプリケーションの性質に左右される．つまり，SST による性能向上
は，投機実行状態の割合が大きいメモリインテンシブなアプリケーションに対しては効果
があるものの，そうでないアプリケーションに対しては効果が小さくなる．また，SST の
性能向上を左右する要因として，分岐予測精度の問題も挙げられる．図 5.10 に示した通
り，SST における投機実行は分岐予測ミスの影響を受け，ベンチマークによっては半分以
上が無効な投機実行となっている．今回提案した 2 つの手法は，どちらも投機実行の性能
を向上させるものであるため，これらの制約の強い影響を受けていると考えられる．
前項で示した図 5.11 は，提案したスレッディング手法による効果の幅を表したものであ
5.6 DQ の構成による性能変化
41
るが，前項で述べたように，これは投機実行状態の割合と分岐予測精度という二つの制約
による影響を反映させたものであり，これらの制約の傾向をも表したものだと考えられる．
この傾向は，提案したスレッディング手法だけでなく，提案したロード命令処理手法にも
反映されており，提案手法による性能向上率を示した図 5.2 が示す通り，提案したロード
命令処理手法のみの場合における性能向上率にも，該当する項で述べた bzip2 以外のベン
チマークで図 5.11 と同様の傾向を見ることができる．これは，提案した 2 つの手法のどち
らも，この制約による影響によって性能向上幅が制限されていることを表しており，さら
なる性能向上のためには，この制約を緩和する必要があると考えられる．
その方法の 1 つとして，投機実行時の分岐予測精度の改善が挙げられる．図 3.4 が示す
通り，SST は分岐予測精度を改善することによって性能向上幅が大きくなることが分かっ
ており，分岐予測精度を改善することによって，SST だけでなく提案手法による性能向上
幅も大きくなると考えられる．
5.6 DQ の構成による性能変化
最後に，DQ の数およびサイズが性能に与える影響を評価する．
DQ の数を 2，4，8，16 と変化させ，また DQ のサイズを 8，16，32 と変化させた．チェッ
クポイントは DQ と同数とし，ロードストアキューのサイズは (DQ のサイズ) × (DQ の数
) とした．
5.6.1 DQ 構成を変化させた場合の性能向上
まず，DQ の構成を変化させた場合の性能向上率を評価する．ここでは，命令数 8 の DQ
が 2 個という最小の構成をベースラインとし，各手法において，ベースラインから DQ の
構成を変化させた場合の性能向上率を調べた．
その結果を図 5.12 および図 5.13 に示す．図 5.12 は従来の SST に対して DQ の構成を
変化させた場合の IPC 向上率であり，図 5.13 は提案手法に対して DQ の構成を変化させ
た場合の IPC 向上率である．
ベンチマークによって幅は異なるものの，DQ の数およびサイズを増加させた場合に性
能向上がみられ，投機実行状態において遅延実行可能な命令数が性能に深い影響を与えて
いることが確認できる．
5.6.2 DQ 構成の提案手法への影響
次に，DQ の構成を変化させた場合の提案手法の性能向上幅を評価する．
Chapter 5 提案手法の評価
42
DQ size = 8
DQ size = 16
DQ size = 32
12
10
)
%
(
o
i
t
a
r
g
n
i
s
a
e
r
c
in
C
P
I
8
6
4
2
0
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
bzip2
gcc
mcf
libquantum h264ref
omnetpp
astar
hmean
number of DQ
図 5.12 DQ の構成を変化させた場合の SST の IPC 変化率
DQ size = 8
DQ size = 16
DQ size = 32
12
10
)
%
(
o
i
t
a
r
g
n
i
s
a
e
r
c
in
C
P
I
8
6
4
2
0
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
bzip2
gcc
mcf
libquantum h264ref
omnetpp
astar
number of DQ
図 5.13 DQ の構成を変化させた場合の提案手法の IPC 変化率
hmean
5.6 DQ の構成による性能変化
43
DQ size = 8
DQ size = 16
DQ size = 32
2.5
)
%
(
o
i
t
a
r
g
n
i
s
a
e
r
c
n
i
C
P
I
2
1.5
1
0.5
0
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
bzip2
gcc
mcf
libquantum h264ref
omnetpp
astar
hmean
number of DQ
図 5.14
DQ の構成を変化させた場合の SST に対する提案手法の IPC 変化率
DQ の構成を変化させた場合の，従来の SST に対する提案手法の IPC 向上率を図 5.14
に示す．これは，各 DQ の構成に対して，提案手法によってどれだけ性能が向上したかを
表すものである．
いくつかの例外はあるものの，DQ の数を増加させると，提案手法における IPC 向上率
も高くなる傾向がみられた．これは，使用可能な DQ の数が少なく，投機実行状態におい
て遅延可能な命令数が十分でない場合，提案したスレッディング手法によって新たに増え
た投機実行の機会を十分に活用できないからであると考えられる．
45
第6章
結論
本論文では，アウトオブオーダプロセッサと比較して面積効率の良いインオーダプロ
セッサをベースとした，ALU カスケーディングと投機実行を併用するプロセッサに対し，
性能を向上させる新たなスレッディング手法を提案した．
ソフトウェアシミュレーションによる評価の結果，従来のスレッディング手法を行うプ
ロセッサに対して IPC が平均 1.23%，最大で 2.00% 向上したことを確認した．
今後の課題として次のことが挙げられる．
• 分岐予測ミスの精度を変化させた場合における提案手法の効果の評価
• 分岐予測ミスの影響を軽減する手法の検討
47
謝辞
本研究を進めるにあたり，熱心な御指導をしていただいた吉瀬謙二准教授に深く感謝致
します．様々な課題に直面していた私に対し，道筋を示して頂き，本当にありがとうござ
いました．先生の御指導なくして本研究はありえませんでした．
また，本研究の基礎となった，SST に対する改良を考案された松村貴之氏に感謝致しま
す．松村氏の論文なくして本研究は無かったと思います．
吉瀬研究室の皆様には，様々な形で大変お世話になりました．深く感謝致します．
最後に，在学中に様々な形で私を支えていただいた友人たちに，深く感謝の意を表し
ます．
49
参考文献
[1] Andy Glew. MLP yes! ILP no! In Wild and Crazy Ideas Session, 8th International Conference on Architectural Support for Programming Languages and Operating Systems,
October 1998.
[2] Onur Mutlu, Hyesoon Kim, and Yale N. Patt. Eﬃcient runahead execution: Powereﬃcient memory latency tolerance. IEEE Micro, Vol. 26, No. 1, pp. 10–20, January
2006.
[3] Shailender Chaudhry, Robert Cypher, Magnus Ekman, Martin Karlsson, Anders Landin,
Sherman Yip, Håkan Zeﬀer, and Marc Tremblay. Simultaneous speculative threading: A
novel pipeline architecture implemented in sun’s rock processor. In Proceedings of the
36th Annual International Symposium on Computer Architecture, ISCA ’09, pp. 484–
495, New York, NY, USA, 2009. ACM.
[4] Takayuki Matsumura. A study of an in-order processor exploiting memory level parallelism with speculative execution. Master’s thesis, Tokyo Institute of Technology, Japan,
2013.
[5] Wm. A. Wulf and Sally A. McKee. Hitting the memory wall: Implications of the obvious.
SIGARCH Comput. Archit. News, Vol. 23, No. 1, pp. 20–24, March 1995.
[6] David W. Wall. Limits of instruction-level parallelism. In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS IV, pp. 176–188, New York, NY, USA, 1991. ACM.
[7] Shailender Chaudhry, Robert Cypher, Magnus Ekman, Martin Karlsson, Anders Landin,
Sherman Yip, Håkan Zeﬀer, and Marc Tremblay. Rock: A high-performance sparc cmt
processor. IEEE Micro, Vol. 29, No. 2, pp. 6–16, March 2009.
[8] 上野洋一郎, 深作泉, 中村宏, 南谷崇. 非同期式カスケード alu アーキテクチャ. 電子
情報通信学会技術研究報告. FTS, フォールトトレラントシステム, Vol. 98, No. 27, pp.
61–68, apr 1998.
[9] 尾形幸亮, 姚駿, 三輪忍, 嶋田創, 富田眞治. Alu cascading を行う動的命令スケジュー
参考文献
50
ラ (集積回路とアーキテクチャの協創-プロセッサ, メモリ, システム lsi 及び一般-). 情
報処理学会研究報告. 計算機アーキテクチャ研究会報告, Vol. 2007, No. 55, pp. 91–96,
may 2007.
[10] 藤枝直輝, 渡邉伸平, 吉瀬謙二. 教育・研究に有用な mips システムシミュレータ
simmips. 情報処理学会論文誌, Vol. 50, No. 11, pp. 2665–2676, nov 2009.
51
研究業績
全国大会
1.
大久保直昭, 吉瀬謙二：インプレース実行型プロセッサ CRIB における内部データ
転送の効率化, 情報処理学会第 74 会全国大会, 名古屋工業大学御器所キャンパス
(2012 年 3 月 6 日発表).
ポスター
2.
大久保直昭, 吉瀬謙二：インプレース実行型プロセッサ CRIB における効率的な浮動
小数点命令実行手法, 電子情報通信学会集積回路研究会学生・若手技術者育成のた
めの研究会, 大阪大学会館 (2011 年 12 月 8 日発表).

Download Report