演算/メモリ性能バランスを考慮したCMP向け ヘルパー - 九州大学

演算/メモリ性能バランスを考慮した CMP 向け
ヘルパースレッド実行方式の提案と評価
今里 賢一†
福本 尚人†
井上
弘士†
村上
和彰†
† 九州大学大学院 システム情報科学府/科学研究院 〒 819–0395 福岡市西区元岡 744
E-mail: †{imazato,[email protected], ††{inoue,[email protected]
あらまし 複数のプロセッサコアを 1 チップに搭載するチップマルチプロセッサ (CMP) が現在注目されている. チッ
プ内スレッドレベル並列処理により高い演算性能を得ることができるためである.しかしながら,メモリバンド幅の
制約や複数コア搭載によるメモリアクセス頻度の増加により,メモリウォール問題が深刻化する.その結果,多くの
メモリ参照を必要とする並列プログラムの実行においては実効性能が低下するといった問題が生じる.そこで本稿で
は,CMP の性能向上を目的として,演算性能とメモリ性能のバランスを考慮したヘルパースレッド実行方式を提案
する.従来の方式では,スレッドレベル並列性を高めるため,搭載された全てのプロセッサコアを利用して並列プロ
グラムを実行する.これに対し,提案方式では,一部のプロセッサコアをプリフェッチを行うヘルパースレッドに割
当てる.ヘルパースレッドの最適な数が既知であると仮定して提案方式の性能を評価した結果,従来方式と比較して,
最大で 47%の性能向上を得ることができた.
キーワード
チップマルチプロセッサ,並列処理,プリフェッチ,ヘルパースレッド
Performance Balancing: An Efficient Helper-Thread Execution on CMPs
Kenichi IMAZATO† , Naoto FUKUMOTO† , Koji INOUE† , and Kazuaki MURAKAM†
† Graduate school / Faculty of Information Science and Electrical Engineering, Kyushu University
Motooka 744, Nishi-ku, Fukuoka-shi, 819–0395 Japan
E-mail: †{imazato,[email protected], ††{inoue,[email protected]
Abstract Conventional CMPs attempt to exploit the thread-level parallelism (TLP) by using all of the cores
integrated in a chip. However, this kind of straightforward way does not always achieve the best performance. This
is because the memory-wall problem becomes more critical in CMPs, resulting in poor performance in spite of high
TLP. To solve this issue, we propose an efficient thread management technique, called performance balancing. We
dare to throttle the TLP to execute software prefetchers as helper-threads. Our experimental results show 47%
speed up in the best case compared with a conventional parallel execution.
Key words chip multiprocessor, parallel processing,prefetching, helper thread
1. は じ め に
的として,演算性能とメモリ性能のバランスを考慮したヘル
パースレッド実行方式を提案する.従来方式とは異なり,並列
複数のプロセッサコアを 1 チップに搭載するチップマルチプ
プログラムを実行するプロセッサコア数を減らす一方,メモリ
ロセッサ (CMP) が注目されている. CMP は,複数コアで並
性能向上を目的としたヘルパースレッドを実行するプロセッサ
列処理することにより,高い演算性能を達成することができる.
コア数を増加させる.このように,演算性能をある程度犠牲に
しかしながら,オフチップメモリバンド幅の制約や複数コア搭
してでも,性能向上阻害要因であるメモリボトルネックを解消
載によるメモリアクセス頻度の増加によりメモリウォール問題
することにより CMP 全体の性能向上を目指す.
が深刻化する.その結果,多くのメモリ参照を必要とする並列
本稿の構成は以下の通りである.第 2 節で CMP における問
処理においては実効性能が低下するといった問題が生じる.こ
題点について議論し,従来の解決策について述べる.第 3 節で
のような場合,単純に全てのコアで並列実行しても十分な性能
は,提案方式とそのアーキテクチャ・サポートについて説明す
向上を得られない.
る.さらに性能モデル式を用いて提案方式の効果を示す.第 4
そこで本研究では,CMP における並列処理の性能向上を目
節では,ベンチマークプログラムを用いた定量的評価を行い,
—1—
提案方式の有効性を明らかにする.最後に第 5 節でまとめる.
30
4.5
L2-perfect
4
2. チップマルチプロセッサにおける問題点と従
来の解決策
2. 1 性能向上阻害要因
CMP 上の並列処理では,実行コア数に比例した性能向上を
3.5
L2-1MB
3
上向 2.5
能 2
性 1.5
1
は第 5.2 節を参照).横軸は実行コア数,縦軸は L2 キャッシュサ
イズ 1MB のときのシングルスレッド実行を基準とした性能向
上率である.凡例の”L2-1MB” は L2 キャッシュサイズを 1MB
とした場合,“L2-perfect” はオフチップメモリアクセス時間ゼ
0
0
1
2
3
4
5
実行コア数
6
7
8
図 1(d) の Barnes に関しては,実行コア数の増加に対してほ
0
1
2
(a) Cholesky
3
4
5
実行コア数
6
7
8
6
7
8
(b) Ocean
9
3.5
8
3
L2-perfect
7
2.5
6
上向 2
能 1.5
性
L2-perfect
1
2
L2-1MB
0.5
L2-1MB
上向 5
能4
性3
1
0
0
ロの理想メモリを想定した場合を示す.
L2-1MB
5
0
増加に伴う相対メモリ性能の低下が挙げられる.図 1 は CMP
における実行コア数と性能向上の関係を示している (実験環境
L2-perfect
20
上
向
15
能
性10
0.5
実現できない場合が多くある.この 1 つ要因として,コア数の
25
0
1
2
3
4
5
実行コア数
6
7
8
(c) Raytrace
0
1
2
3
4
5
実行コア数
(d) Barnes
ぼ比例した性能向上を得ることができている.しかしながら,
図 1 実行コア数の増加による性能向上
図 1(a)(b)(c) に示すようにその他 3 つのプログラムにおいては
十分な性能向上を達成していない.これは,主に以下 2 つの問
題に起因する.
からメモリ参照アドレスを予測する方法などが提案されてい
る [3] [4].
• 低いスレッドレベル並列性:図 1(a)(c) に示す Cholesky と
Raytrace では,理想的なメモリシステムを想定した L2perfect においても,実行コア数が 4 以上になると十分な性
3. 演算/メモリ性能のバランスを考慮したヘル
パースレッド実行方式
能向上を実現できていない.実行コア数の増加に伴い,そ
3. 1 基 本 概 念
の性能改善率が徐々に低下している.これは,1) 並列化不
第 2.2 節で説明した従来技術では,CMP の演算性能やメモ
可能な処理部分の顕在化や,2) コア間通信オーバーヘッド
リ性能の向上についてそれぞれ個別のアプローチを取っている.
の増大が原因である.
しかしながら,より高い性能を得るためには演算性能とメモリ
• メモリウォール問題:図 1(a)(b) に示す Cholesky や Ocean
において,L2-1MB モデルではコア数の増加に伴う性能向
上が低い.これに対し,L2-perfect では極めて高い性能と
なっている.特に Ocean については,実行コア数に対する
性能スケーラビリティは高いものの,メモリ性能の違いに
より大きな差が存在している.これは,演算性能とメモリ
性能差の拡大 (いわゆるメモリウォール問題) が顕在化した
ためである.
2. 2 従来技術による解決策
CMP において高い性能を実現するためには,第 2.1 節で示
した問題点を解決する必要がある.低いスレッドレベル並列性
による性能向上の阻害を解決する手法として,並列化コンパイ
ラによる並列性の抽出がある.また,実行スレッド数を制限す
る手法などが提案されている [1].
一方,CMP のメモリ性能を向上させる手法として,共有型
キャッシュにおける競合ミス削減法が提案されている.例えば,
文献 [2] では,総 L2 ミス回数の削減を目的としたキャッシュ領
域割当て方式が提案されている.また,CMP においてアイド
ル状態のコアが存在する場合,それを利用してヘルパースレッ
ド(ソフトウェア・プリフェッチャ)を実行する方法がある.プ
リフェッチの方法としては,周囲のコアのメモリ参照アドレス
計算を先行して行う方法や,周囲のコアのキャッシュミス情報
性能の両方を考える必要がある.そこで本稿では,演算/メモリ
性能のバランスを考慮したヘルパースレッド実行方式を提案す
る.図 2 に,提案方式の基本概念を示す.通常の実行方式とは
異なり,メインスレッドを実行するメインコアと,メモリ性能
を高めるためにヘルパースレッドを実行するヘルパーコアが存
在する.ここで,メインスレッドとはアプリケーション・プロ
グラムを実行するスレッドである.ヘルパーコアはすべてのメ
インコアのメモリ性能を高めるために,メインコアからキャッ
シュミス情報を収集しプリフェッチを行う.これにより,メイ
ンコアでのキャッシュミスが減少する.プログラム実行におい
て,演算性能が必要な場合はメインコア数を,メモリ性能が必
要な場合はヘルパーコア数を増加する.こうすることで,演算
性能とメモリ性能のバランスをとり,CMP 全体でより高い性
能を実現する.ヘルパースレッドを実行することによるメモリ
性能の向上が,メインコアの減少による演算性能の低下を上回
れば,CMP 全体の高性能化を実現できる.
3. 2 アーキテクチャ・サポート
本稿では,オンチップに共有 L2 キャッシュを持つ CMP アー
キテクチャを対象とする.したがって,ヘルパースレッドによ
り L2 キャッシュにプリフェッチされたデータに対しメインコア
からアクセス可能となる.
ヘルパーコアは,周りに存在する複数のメインコアに対して
プリフェッチを行う必要がある.したがって,ヘルパーコアはメ
—2—
メモリ性能が低いとき
通常の
プログラムを実行
メインコア
コア0
MSB L1D$
MSB
L1I$
共有バス
L2
演算性能が低いとき
ヘルパースレッド
ヘルパーコア
を実行
コア1 … … コアN
L1D$ L1I$
MSB L1D$
共有キャッシュ
主記憶
a
• HCCL2 :L2 キャッシュアクセスに要するクロックサイク
ル数
• M RL2,i:スレッド数が i のときの L2 キャッシュミス率
• M M L:主記憶アクセスに要するクロックサイクル数
L1I$
なお,L1-L2 キャッシュ間,L2-主記憶間のバスアクセスに要す
オンチップ
オフチップ
る時間はスレッド数に対し一定であると仮定し,L2 キャッシュ
アクセス時間ならびに主記憶アクセス時間に含めている.さら
に,ACi はスレッド数 i と並列化できるメモリアクセスの割合
fAC を用いて,
図 2 提案方式の全体図
ACi = (1 − fAC ) × AC1 +
インコアとキャッシュミス情報を共有しなければならない.こ
れを可能にするために,各プロセッサコアに対してキャッシュミ
ス情報を格納する専用バッファを追加する (図 2).これを Miss
Status Buffer(以下 MSB) と呼ぶ.MSB では,各キャッシュミ
fAC × AC1
i
(4)
と表すことができる.f = fAC を仮定すると,式 (1)∼(4) よ
り CCi は,
{
CCi = (1 − f ) +
{
スを発生したメモリ参照アドレス,プロセッサコア番号,当該
} [
f
× CCexe,1 + AC1 ×
i
}]
メモリ参照命令の PC 値を保持する.これらの情報は,キャッ
HCCL1 +M RL1,i ×(HCCL2 + M RL2,i ×M M L)
シュミスが発生したときに生じるコヒーレンス維持のためのブ
(5)
ロードキャストをスヌープすることで取得する.ヘルパーコア
が複数存在する場合は,それぞれのヘルパーコアが担当するメ
インコアを決定する.各ヘルパーコアの MSB には担当するメ
インコアのキャッシュミス情報のみが格納される.ヘルパーコ
アは MSB に収められたキャッシュミス情報を参照し,メイン
コアのキャッシュミスアドレスを予測して L2 共有キャッシュに
プリフェッチを行う.
と表すことができる.従来方式の実行クロックサイクル数は,
コア数を N とした場合,式 (5) の i に N を代入することによ
り導かれる.
次に,N コア CMP 上で m 個をヘルパーコアとして動作させ
た場合の提案方式の実行クロックサイクル数を求める.N − m
スレッド実行時の実行クロックサイクル数 CCN −m を式 (5) よ
り求め,式変形を行うと式 (6) を得る.
3. 3 性能モデリング
本節では,提案方式の性能モデリングを行う.並列処理の実
行クロックサイクル数は,最も実行時間の長いスレッドの実行
CCN −m =
クロックサイクル数で表される.スレッド数 i における実行ク
ロックサイクル数 CCi は,演算実行に要するクロックサイク
ル数 CCexe,i ,メモリアクセスによりストールした実行クロッ
クサイクル数 CCmem,i によって以下のように表される.
CCi = CCexe,i + CCmem,i
(1)
f
N −m ×(1−r
M RL2 ,N,m×kN )×CCN (6)
f
1−f +
N
1−f +
kN =
ACN × M RL1,N × M RL2,N × M M L
CCN
(7)
ここで,rM RL2 ,N,m は N スレッド実行から N − m スレッド実
行に変更したときの L2 キャッシュミス率の減少率である.kN
はスレッド数 N で実行したときの,全実行時間に占める主記
ただし,ここでは簡単化のため演算とメモリアクセスのオー
憶アクセスによるプロセッサストール時間の割合である.また,
バーラップ実行は考慮しない.ここで,CCexe,i と CCmem,i は
本稿ではプライベート L1 キャッシュを前提としており,以下
以下のように表すことができる.
のように仮定した.
CCexe,i
f × CCexe,1
= (1 − f ) × CCexe,1 +
i
(2)
• M RL1,N −m = M RL1,N:スレッド数 N とスレッド数 N −m
とでは L1 キャッシュミス率はほぼ同一と考えられる.メモ
CCmem,i = ACi × {HCCL1 + M RL1,i ×
(HCCL2 + M RL2,i × M M L)}
リアクセス回数が変化するため,厳密には上記の値は異な
(3)
るが,アクセスパターンはほぼ同じと考えられるためミス
率の変化は小さいと推測できる.
各項の定義は以下の通りである.
• f :並列化できる演算の割合
• M RL2,N −m = (1 − rM RL2 ,N,m ) × M RL2,N :スレッド数 N
とスレッド数 N −m とで,L2 キャッシュミス率は rM RL2 ,N,m
• ACi:スレッド数が i のときのメモリ参照回数
の割合だけ減少する.スレッド数の減少により,あるキャッ
• HCCL1 :L1 キャッシュアクセスに要するクロックサイク
シュセットに対してアクセスされる間隔が長くなると考え
ル数
• M RL1,i:スレッド数が i のときの L1 キャッシュミス率
られる.そのため競合性のミスが減り,ミス率は減少する.
ヘルパースレッドを実行させた場合,プリフェッチ効果によ
—3—
cc(x,y)
1
"memori.dat"
"xymemori.dat"
CC Nth− m / CC N
2. 5
2. 0
1.5
1 .0
0.5
0
7 6
5 4
m
3 2
1 0 1.0 0.8 0.6
0.4 0.2
cc(x,y)
1
"memori1.dat"
"xymemori.dat"
CC Nth− m / CC N
0
7.0
6.0
5. 0
4.0
3.0
2 .0
1.0
0
7 6
rht
4
3 2
1 0 1.0 0.8
0.6 0.4
0.2 0
rht
(b) f = 0.99,kN = 0.6
cc(x,y)
1
"memori1.dat"
"xymemori.dat"
1.5
1 .0
0.5
0
7 6
5
4
m
3 2
1 0 1.0 0.8
0.6 0.4
0.2 0
CC Nth− m / CC N
7.0
6.0
5. 0
4.0
3.0
2 .0
1.0
0
7 6
rht
(c) f = 0.70,kN = 0.1
テーブルの総エントリ数 2048,
ミス履歴バッファのエントリ数 8/core,
テーブルのエントリ数 8/core, degree 8
5
cc(x,y)
1
"memori.dat"
"xymemori.dat"
2. 0
設定
local stride
degree 8
m
2.5
プリフェッチアルゴリズムの設定
global stride
(a) f = 0.70,kN = 0.6
CC Nth− m / CC N
表1
アルゴリズム
delta correlation
インデックステーブルの総エントリ数 2048,
GHB の総エントリ数 2048,
グラム実行中にはヘルパーコア数を変更しない.最適なヘル
パーコア数の決定法ならびに,動的なヘルパーコア数の変更は
今後の課題である.ヘルパースレッドの動作としては,以下の
5
4
m
3 2
1 0 1.0 0.8
0.6 0.4
0.2 0
3 種類を実装した.
rht
(d) f = 0.99,kN = 0.1
ht
図 3 提案方式の実行クロックサイクル数 CCN
−m の変化 (コア数
N = 8)
• local stride プリフェッチ [5]:stride プリフェッチの一種であ
る.stride プリフェッチとは,連続したメモリ参照アドレス
の差分 (以下ストライド値) が一定であるようなメモリアク
セスパターンを検出し,プリフェッチを行う手法である.現
り L2 キャッシュミス率が減少する.m 個のプロセッサコアで
ヘルパースレッドを実行した場合に式 (6) の L2 キャッシュミス
率の減少率 rM RL2 ,N,m が rht に変化したとする.ここで,rht
は従来実行方式を基準としたときの提案実行方式の L2 キャッ
シュミス率の減少率である.このときの実行クロックサイクル
ht
数 CCN
−m は,rM RL2 ,N,m を rht に置き換えることによって
導かれ,式 (8) で表せる.
f
1− f +
N
−m
ht
CCN −m =
× (1 − rht × kN ) × CCN
f
1− f +
N
在のミスアドレスを a,ストライド値を s とした場合,アド
レス a + s,a + 2s,…,a + ds に対しプリフェッチを行う.
ただし,d は prefetch degree と呼ばれる値で,キャッシュ
ミス発生時に発行するプリフェッチ数を表す.local stride
プリフェッチでは,命令別にミスアドレスのストライド値を
計算する.キャッシュミスを起こした命令のプログラムカウ
ンタ値,ミスアドレス,ストライド値を記録するテーブル
が必要となる.
(8)
3. 4 従来方式と提案方式の比較
式 (8) を用いて提案方式と従来方式の性能を比較する.図 3
に,f と kN の値の大小の組み合わせについて,m と rht が変
化したときの実行クロックサイクル数の変化を示す.縦軸は,
• global stride プリフェッチ [4]:stride プリフェッチの一種で
ある.global stride プリフェッチでは現在のミスアドレスと
最近 n 個のミスアドレスとの差のうち最も絶対値が小さい
ものをストライド値として算出する.最近 n 個のミスアド
レスを記録するミス履歴バッファとストライド一定のアド
レスストリームを記録するテーブルが必要となる.
N スレッド実行時のクロックサイクル数 CCN を 1 としたとき
• delta correlation プリフェッチ [6] [7]:時間的に連続するキャッ
ht
の提案方式による実行クロックサイクル数 CCN
−m の比を示し
シュミスアドレスの差分がマルコフ情報源になっていると仮
ている.傾きのある曲面が提案方式による実行クロックサイク
定し,プリフェッチを行う.マルコフモデルの構築はミスア
ル数の変化を表しており,この曲面が高さ 1 の平面 (従来の全
ドレスの履歴を記録しておくことにより疑似的に行われる.
コア並列実行方式) を下回れば,提案方式により性能向上が実
プリフェッチは現在のマルコフモデル上での状態ノードを特
現できることを示す.
定し,その後マルコフモデルのエッジを辿ることで実現する.
提案方式が最も有効なのは,f が小さく,かつ kN が大きい
場合である (図 3(a)).これは,プログラムを実行するスレッド
の減少によるクロックサイクル数の増加が小さく (f が小さい),
さらに,L2 キャッシュミス率を改善することによるクロックサ
イクル数の減少が大きい (kN が大きい) ためである.逆に,f
が大きく,かつ kN が小さい場合 (図 3(d)) は,提案方式によっ
て性能向上を実現することは難しい.
4. ベンチマークを用いた定量的評価
4. 1 評 価 環 境
提案方式の有効性を明らかにするため,ベンチマークプログ
ラムを用いた定量的評価を行う.ここで,本稿では最も高い性
能を達成できるヘルパーコア数は既知と仮定する.また,プロ
本稿では文献 [6] で示された Global History Buffer(GHB)
を用いる手法を用いる.
本実験で使用したプリフェッチアルゴリズムの設定を表 1 に示
す.本実験では,マルチプロセッサシミュレータ M5 [8] に Miss
Status Buffer を実装し評価を行った.実験に用いたシミュレー
タの設定を表 2 に示す.また,評価対象モデルは以下の通りで
ある.
• BASE:すべてのコアで並列プログラムを実行する従来モ
デル
• PB-LS:ヘルパースレッドの動作として local stride プリ
フェッチを実行する提案モデル
• PB-GS:ヘルパースレッドの動作として global stride プリ
—4—
表2
シミュレータの設定
1.6
コアの構成
8 コア, イン・オーダ
L1 命令キャッシュ
32KB, 2-way, 64B lines,
1 clock cycle, MSHR 8
L1 データキャッシュ
32KB, 2-way, 64B lines,
1 clock cycle, MSHR 32
L2 キャッシュ
1MB, 8-way, 64B lines,
12 clock cycles, MSHR 92
L1-L2 間共有バス幅
64B
L2-主記憶間バス幅
16B
主記憶レイテンシ
300 clock cycles
miss status buffer
エントリ数:20,
上1.4
向
能1.2
性1
の
らか0.8
時0.6
行
実
アコ0.4
0.2
全0
BASE
Cholesky
図4
PB-LS
FMM
LU
PB-GS
PB-DC
Ocean
Radix
Raytrace
ヘルパースレッドによる性能の変化
レイテンシ:1 clock cycles
表 4 最適なコアの割当て (メインコア:ヘルパーコア)
表3
Cholesky
FMM
LU
Ocean
Radix
Raytrace
kN
PB-LS
6:2
7:1
7:1
4:4
4:4
7:1
7:1
7:1
7:1
4:4
4:4
7:1
7:1
7:1
7:1
4:4
4:4
7:1
各ベンチマークプログラムの入力と f ,kN の値
プログラム
入力
f
評価モデル
Barnes
32K particles
1.0017
0.0897
PB-GS
Cholesky
tk29.O
0.7294
0.4519
PB-DC
FMM
64K particles
0.9869
0.2900
LU
1024 × 1024 matrix
0.8818
0.1740
258 × 258 ocean
0.7
Ocean
0.9946
0.7155
Radix
16M integers
0.9997
0.6098
0.6
Raytrace
teapot
0.7061
0.1811
WaterSpatial
4096 molecules
0.9871
0.0532
f :並列化できる演算の割合
kN :全てのコアを通常実行させる場合の実行時間にしめる
主記憶アクセスによるストール時間の割合
BASE
PB-LS
PB-GS
FMM
LU
Ocean
PB-DC
率
スミ0.5
ュシ0.4
ッャ0.3
0.2
キ
2
L
0.1
0
Cholesky
フェッチを実行する提案モデル
• PB-DC:ヘルパースレッドの動作として delta correlation
図5
Radix
Raytrace
ヘルパースレッドによる L2 キャッシュミス率の変化
プリフェッチを実行する提案モデル
ただし,PB-LS,PB-GS,PB-DC では,ヘルパーコアの数は
1 以上とする.
ベンチマークプログラムは Splash2 [9] から複数のプログラ
ムを選択した.各ベンチマークプログラムの入力を表 3 に示す.
各ベンチマークに関して,第 4 節で用いたパラメータ f と kN
の値は表 3 の通りである(注 1).第 4 節で述べたように,提案方
式は f が小さく,また kN が大きい場合に有効である.従って,
kN が大きい Cholesky,Ocean,Radix といったプログラムや
f が小さい Cholesky,LU,Raytrace では,提案方式による効
果が期待できる.
4. 2 評 価 結 果
4. 2. 1 提案方式の性能
従来方式と比較した提案方式の性能向上を表す実験結果を図
4 に示す.縦軸はすべてのコアで並列プログラムを実行した場
合の性能を 1 としたときの相対性能を示している.それぞれの
ベンチマークプログラムと評価モデルの組について最適なヘル
パーコア数で実行したときの性能を示している.また,表 4 に
は,そのときコアの割当てを示す.ただし,Ocean,Radix に
ついてはスレッド数の制約 (2 の累乗にしかスレッド数を設定
できない) のため,ヘルパーコアが 4 個の場合しか評価してお
らず,最適なヘルパーコア数が 4 となっている.
(注 1):f は,第 2.1 節の実験結果から得られた実行命令数から最小自乗法を用
いて近似的に求めた値である.
図 4 から Cholesky,Ocean,Raytrace では提案方式による
性能向上が得られている.さらに,すべてのベンチマークプロ
グラムにおいて提案手法の評価モデルの中では PB-LS が最も
高い性能を示している.Cholesky,PB-LS の組で最大 47% の
性能向上を達成した.
図 5 には,各モデルに関する L2 キャッシュミス率を示す.た
だし,L2 キャッシュミス率はメインコアの L2 キャッシュアク
セスのみについて算出している.提案方式により性能向上が得
られていた Cholesky,Ocean,Raytrace では,L2 キャッシュ
ミス率の削減が大きい.一方,提案方式による効果が低かった
FMM では,ほとんど L2 キャッシュミス率を削減できていな
い.Radix では,L2 キャッシュミス率の減少が大きいが,図 4
では性能向上が得られていない.これは,スレッド数の制限の
ために通常実行を行うコア数を半分にしたことによる性能低下
が大きい (第 2.1 節の実験より性能は 34.5% 低下) ためと考え
られる.
4. 2. 2 並列実行部分の提案方式の性能
並列処理では,一つのスレッドのみが動作する逐次実行部分
と複数のスレッドが同時に動作する並列実行部分が存在する.
本実験において,実際に通常実行を行うコア数を減らし,その
コアをヘルパーコアとして動作させているのは並列実行部分で
ある.
図 6 に並列実行部分のみの提案方式の性能を示す.プログラ
ム全体で性能向上が得られていた Cholesky と Raytrace におい
—5—
1.4
上1.2
向能
性の 1
らか0.8
時0.6
行0.4
実ア
コ0.2
全0
BASE
PB-LS
PB-GS
今後は,ヘルパースレッドを実行するコア数を決定する機構
PB-DC
を考える.また,実験結果の詳細な解析および考察を行う.具
体的には,ベンチマークプログラムの変更,メモリ関連のパラ
メータの変更,ハードウェアプリフェッチャと組み合わせた場
合の提案方式の効果の検証について行う.
謝辞
日頃から御討論頂いております九州大学安浦・村上・
松永・井上研究室ならびにシステム LSI 研究センターの諸氏に
Cholesky
FMM
LU
Ocean
Radix
Raytrace
感謝します.また,本研究は主に九州大学情報基盤研究開発セ
ンターの研究用計算機システムを利用しました.
図6
ヘルパースレッドによる性能の変化 (並列実行部分)
1.6
上1.4
向能
性1.21
のら
か0.8
時0.6
行
実ア0.4
コ0.2
全0
L2-1MB
Cholesky
FMM
L2-2MB
LU
Ocean
L2-4MB
Radix
Raytrace
図 7 L2 キャッシュサイズの変化による提案方式の性能の変化 (PB-LS)
ては,並列実行部分では性能向上が得られていない.このよう
なプログラムでは,プログラム全体を通してあるコアをヘル
パーコアとして動作させるのではなく,逐次実行部分のみヘル
パーコアとして動作させ,並列実行部分ではメインコアとして
動作させることにより,より高い性能向上が得られるのではな
いかと考えられる.一方,Ocean については,並列実行部分で
も提案方式による性能向上が得られている.これは,従来実行
方式での主記憶メモリアクセスによるストール時間の割合が大
きく (kN が大きく),さらに図 5 よりヘルパースレッドを実行
することによる L2 キャッシュミス率の減少が特に大きいため
だと考えられる.
4. 2. 3 L2 キャッシュサイズを変化させた場合の提案方式の
性能
図 7 に L2 キャッシュサイズを 1MB,2MB,4MB としたと
文
献
[1] M. A. Suleman, M. K. Qureshi and Y. N. Patt: “Feedbackdriven threading: power-efficient and high-performance execution of multi-threaded workloads on cmps”, SIGARCH
Comput. Archit. News, 36, 1, pp. 277–286 (2008).
[2] M. K. Qureshi and Y. N. Patt: “Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches”, IEEE MICRO, 0, pp.
423–432 (2006).
[3] J. A. Brown, G. C. Hong Wang, P. H. Wang and J. P. Shen:
“Speculative precomputation on chip multiprocessors”, Proceedings of the 6th Workshop on Multithreaded Execution,
Architecture, and Compilation (2001).
[4] I. Ganusov and M. Burtscher: “Efficient emulation of hardware prefetchers via event-driven helper threading”, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, pp. 144–153 (2006).
[5] J. L. Baer and T. F. Chen: “Effective Hardware-Based Data
Prefetching for High-Performance Processors”, IEEE Trans.
Comput., 44, 5, pp. 609–623 (1995).
[6] K. J. Nesbit and J. E. Smith: “Data Cache Prefetching Using a Global History Buffer”, IEEE Micro, 25, 1, pp. 90–97
(2005).
[7] K. J. Nesbit, A. S. Dhodapkar and J. E. Smith: “AC/DC:
An Adaptive Data Cache Prefetcher”, Proceedings of the
13th International Conference on Parallel Architectures and
Compilation Techniques, pp. 135–145 (2004).
[8] N. L. Binkert, R. G. Dreslinski, L. R. Hsu, K. T. Lim, A. G.
Saidi and S. K. Reinhardt: “The M5 Simulator: Modeling
Networked Systems”, IEEE Micro, 26, 4, pp. 52–60 (2006).
[9] S. C. Woo, M. Ohara, E. Torrie, J. P. Singh and A. Gupta:
“The SPLASH-2 programs: characterization and methodological considerations”, Proceedings of the 22nd annual international symposium on Computer architecture, pp. 24–
36 (1995).
きの提案方式による性能向上を示す.この図では,PB-LS モデ
ルの性能を示している.縦軸は,それぞれの L2 キャッシュサ
イズにおける全コア並列実行時の性能を 1 とした時の相対性能
を示している.すべてのプログラムにおいて L2 キャッシュサ
イズの増加に伴い提案方式による性能向上が低くなっている.
これは,従来実行方式の主記憶メモリアクセスによるストール
時間が少なく (kN が小さく) なり,ヘルパーコアによるメモリ
性能向上の効果が得られにくくなったためと考えられる.
5. お わ り に
本稿では,ヘルパースレッドの新しい実行方式について提案
とその評価および考察を行った.その結果,すべてのコアで並
列プログラムを実行する従来の実行方式と比較して,提案方式
は最大で 47%の性能向上を得ることができた.
—6—