情報処理学会研究報告IPSJ SIG Technical Report
マルチコアプロセッサのためのスレッド間共有データを考慮したキャッシュ機構
西村 秦†1佐藤 雅之†2江川 隆輔†2小林 広明†2
概要：マルチコアプロセッサでは，ラストレベルキャッシュ (LLC) を複数のコアで共有している．このため，LLC 上には複数のスレッドで共有しているデータ (共有データ) が存在する．複数のスレッドからア
クセスされる共有データは，単一のスレッドからしかアクセスされないデータ (私有データ) に比べ再利用性が高い．しかし，共有データと私有データの区別を行わないデータ管理では，私有データによる過剰な
キャッシュ占有のため，共有データを十分に保存できずヒット率の低下を招く．そこで，本研究では，並
列プログラムの実効性能向上を目的とし，複数のスレッドに共有されるデータとそれ以外のデータを LLC上で個別に管理するキャッシュ機構を提案する．提案手法は，LLC 上のデータを共有データと私有データ
に分けて管理することで，再利用性の高い共有データを優先的に LLC に保持する．これにより，共有データのヒット率が向上し，並列プログラムの実効性能向上が期待できる．シミュレーションによる評価結果
から，提案手法は，LRU 置換ポリシに基づくキャッシュ機構と比較して最大 1.70 倍，平均 1.13 倍の性能向上を可能にすることが明らかとなった．
1.はじめに
ムーアの法則 [1] に従う半導体の集積密度の向上により，
1 つのチップに複数のコアを搭載することが可能になった．
このため，プロセッサの演算性能は飛躍的に向上してい
る．一方で，演算に用いられるデータを保存するメインメ
モリのデータ転送性能の向上率は，プロセッサの演算性能
の向上率よりも小さい．このため，計算機システムにおい
て，メインメモリのデータ転送速度がボトルネックとなっ
この問題を解決するために，近年のプロセッサにはキャッ
シュメモリ (キャッシュ) を搭載している．キャッシュはメ
インメモリよりも高速なデータ転送を可能とし，メインメ
モリへのアクセス時間を隠蔽することができる．また，容
量とデータ転送速度の異なるキャッシュをプロセッサ内に
複数搭載することで，ヒット率の向上とアクセス時間の短
縮を両立し，システムの高性能化を実現している．
近年のマルチコアプロセッサにおいて，LLC は複数のコ
アで共有されている．このため，複数のコアで分担処理を
行う並列プログラムを実行した際に，共有データが LLC
に保存される．共有データは複数のコアからアクセスされ
るため，私有データに比べアクセスが集中すると考えられ
†1現在，東北大学 大学院情報科学研究科†2現在，東北大学 サイバーサイエンスセンター
る．したがって，共有データを優先的に LLC に残してお
くことでヒット率が増加し，実効性能が向上する可能性が
ある．これまでにも共有データを考慮した LLC の管理機
構は提案されている [2] [3]．しかし，これらの提案では，
将来のアクセスパターンを予測する必要があることや，コ
ア数が増大した際にハードウェアオーバーヘッドが大きく
なる問題がある．
本研究では，並列プログラムの実効性能向上を目的とし，
共有データを保護するキャッシュ管理機構を提案する．本
機構では，LLC において少ないハードウェアオーバーヘッ
ドで共有データと私有データを判別し，別々に管理する．
これにより，再利用性の低い私有データによって共有デー
タが追い出されることを防ぎ，共有データへのヒット数が
増加する．その結果，並列プログラムの実効性能向上が期
2.共有データが性能に与える影響
本章では，共有データを保護する必要性について述べる．
まず，予備実験を通して共有データのアクセス特性を調査
する．そして，従来手法のコア間共有キャッシュにおける
データ管理機構の問題点について述べる．
c⃝ 2015 Information Processing Society of Japan1
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
表 1予備実験の環境
ベンチマーク速度向上MPKI
is1.331.03
mg1.3610.02
canneal1.4213.84
ocean.ncont1.5720.86
ocean.cont1.5721.24
ft1.782.78
streamcluster1.887.82
表 2予備実験の環境
パラメータ値
CPU8 コア，2.66GHz
L1I キャッシュ4-way，32KB/1 コア，4 サイクル
L1D キャッシュ8-way，32KB/1 コア，4 サイクル
L2 キャッシュ8-way，256kB/1 コア，9 サイクル
LLC16-way，8MB/8 コア，35 サイクル
メインメモリ175 サイクル
2.1共有データのアクセス特性
2.1.1共有データの平均再利用回数
共有データは複数のコアからアクセスされるため，単一
のコアからしかアクセスされない私有データに比べて再利
用性が高い可能性がある．そこで，共有データのアクセス
特性を調査するため，予備実験を行った．予備実験では，
LLC 上で再利用されたブロックに着目し，共有データと私
有データについての 1 ブロックあたりの再利用回数 (平均
再利用回数) を求める．
予備実験は Sniper シミュレータ [4] を用いた．実験環
境を表 2 に示す．全てのキャッシュは LRU 置換ポリシ
によって管理され，ブロックサイズは 64 バイトとする．
ベンチマークには並列プログラムである PARSEC [5] と
SPLASH-2 [6]，Nas Parallel Benchmark [7] から，LLC の
データ管理ポリシを変更することによって速度向上が得
られる可能性のあるものを選択して用いた．表 1 に，選
択したベンチマークの一覧を示す．これらのベンチマー
クは，容量が 8MB の場合において MPKI(Miss Per Kilo
Instructions) が 1 以上であり，かつ，LLC 容量を 8MB か
ら 16MB に増加させた際に 10%以上の速度向上が得られ
たベンチマークである．MPKI は，1000 命令あたりのミ
ス数を表しており，1 より小さいとミスが性能に与える影
響は小さいことを意味する [8]．シミュレーションの実行
区間は，並列処理を行うスレッドが生成されてから破棄さ
れるまでとする．
予備実験の結果を図 1 に示す．図 1 の縦軸は私有データ
(private) と共有データ (shared) それぞれの平均再利用回
数を示す．横軸はベンチマークと相乗平均 (GM) を示す．
図 1 から，全てのベンチマークにおいて，私有データの
平均再利用回数よりも，共有データの回数が平均で 2 倍以
上多いことがわかる．したがって，私有データよりも共有
10	
  
12	
  
14	
  
canneal	
  
is	
  
mg	
  
ocean.cont	
  
ocean.ncont	
  
streamcluster	
  
GM	
  
平均再利用回数	
private	
  shared	
  
図 1平均再利用回数
1	
  1.1	
  1.2	
  1.3	
  1.4	
  1.5	
  1.6	
  1.7	
  1.8	
  1.9	
  2	
  
0.1	
  0.2	
  0.3	
  0.4	
  0.5	
  0.6	
  0.7	
  0.8	
  0.9	
  
canneal	
  
is	
  
mg	
  
ocean.cont	
  
ocean.ncont	
  
streamcluster	
  
速度向上	
共有データの割合	
LRU	
  SBR	
  速度向上	
図 2共有データの割合
データの方が再利用性が高いことがわかる．
2.1.2共有データの LLC に占める割合
LLC において，共有データがどの程度の割合で保存され
ているかを確認するための予備実験を行った．実験環境は
表 2 の通りとする．図 2 に予備実験の結果を示す．図 2 の
左縦軸と棒グラフは LLC を占める共有データの割合を示
し，横軸はベンチマークを示す．図 2 の LRU は LRU ポ
リシにおける共有データの割合を示す．図 2 より，全ての
ベンチマークで共有データは LLC の半分以下しか占めて
いないことがわかる．前節で示したとおり，共有データの
平均再利用回数が多いにもかかわらず，そのキャッシュ中
に占める割合は非常に低いといえる．
図 2 の SBR(Static Best Ratio) は，LLC の一部容量を
共有データのために最適に割り当てた場合の，共有データ
の割合を示している．具体的には，共有データに割り当て
るキャッシュ容量をウェイ数単位で 1 から 15 まで変化さ
せて実験を行い，この中で最も高い性能を実現したウェイ
数の結果を SBR として用いた．図 2 より，7 個のうち 6 個
のベンチマークで SBR の共有データの割合は LRU ポリシ
の割合よりも高いことがわかる．このことは，LRU におい
て共有データが十分に保存されず追い出されていることを
示している．また，最大の性能が得られる共有データの割
合は，ベンチマーク毎に異なっていることもわかる．
図 2 の右側縦軸とプロットは LRU に対して SBR で得ら
c⃝ 2015 Information Processing Society of Japan2
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
れた性能向上を示す．図 2 から，全てのベンチマークにお
いて，SBR は LRU と比較して性能が向上していることが
わかる．is 以外のベンチマークでは，共有データの割合を
増加させた結果として性能が向上しており，共有データを
保護することで性能向上を達成できることが明らかとなっ
た．一方で，is では共有データの割合を減少させることで
性能が向上している．このことから，アクセス特性に応じ
て共有データの割合を適切に調整することが必要である．
2.2関連研究
これまでにもデータの共有を考慮した管理ポリシは研究
されている [2] [3]．これらの研究においても，共有データ
は再利用性が高いことが示されている [2]．また，ミスし
た際に複数のコアでストールを発生させるため，性能に与
える影響が大きく，共有データを保護すべきであると述べ
られている [3]．
Natarajan ら [2] は，Oone と Oall の 2 つのキャッシュ置
換ポリシを提案している．Oone は，2 つ以上のコアからア
クセスされる共有データを保護するポリシである．また，
Oall は，全てのコアからアクセスされる共有データを保
護するポリシである．これらのポリシは将来においてどの
データがどのスレッドからアクセスされるかを予測する必
要があるが，予測の正確性が低いことから現実的な実装に
は至っていない．
Muthukumar ら [3] は，置換によって追い出すデータを決
定する際に，優先度を計算し，優先度が低いデータをキャッ
シュから追い出す Sharing and Hit based Prioritizing 置換
ポリシ (SHP) を提案している．本ポリシにおける優先度
は，データへの参照回数と，データへアクセスするスレッ
ド数で表される共有度を用いて算出される．この優先度に
より，参照回数が多く，かつ，アクセスするスレッド数が
多いデータはキャッシュから追い出されにくくなる．しか
し，SHP では共有度を算出するために，アクセスしたコア
を記録するビットをコア数分用意する必要がある．そのた
め，コア数の増加に伴ってハードウェアコストが増大する
ため，拡張性に乏しい．
異なるアクセス特性を持つデータを判別し，各々のデー
タ毎にキャッシュ資源を分割して管理を行う機構として，
キャッシュ分割機構 [9] [10] が提案されている．Qureshi
ら [9] は，Utility-based cache partitioning を提案してい
る．スレッド毎にデータを判別し，ユーティリティモニタ
を用いて各スレッドが必要とするキャッシュ資源量を見積
もることで，各スレッドに適切な容量の割当を行う．ユー
ティリティモニタは，再利用間隔とヒット数の関係を表す
ヒストグラム [11] に基づき，ヒット数がより増加するよう
にキャッシュ容量の割当を変化させる．
また，Khan ら [10] は Read-Write Partitioning(RWP)
を提案している．RWP では，読み込みだけのデータ (Read
リーダーセット 
リーダーセット 
データ アレイ 
タグ アレイ 
共有データ 
ウェイ数決定器 
アドレス， コアID 
共有データへの割当ウェイ数 
図 3共有データを保護する機構の概要図
データ) と書き込みがあるデータ (Write データ) を判別
し，キャッシュの分割管理を行っている．Read データは，
Write データよりも性能に影響を与えやすい．そのため，
Read データと Write データを分割して管理することによ
り，互いに追い出し合うことを防ぐ．各データへの割当容
量はユーティリティモニタを用いて決定される．
これらの動的キャッシュ分割機構では，独立した複数の
プログラムを同時に実行するマルチプログラムワークロー
ドを対象としており，データをそれぞれのプログラム毎に
分割管理することを対象としている．そのため，並列プロ
グラムを実行した際にキャッシュ上に生じる共有データに
ついては考慮していない．したがって，LLC 上で共有デー
タを判別することで，共有・私有データを LLC 上で分割
管理することが可能になる．これにより，共有データの保
護が可能になり，性能向上が期待できる．
3.共有データを考慮した動的キャッシュ分割機構
共有データを保護するために，共有データと私有データ
をキャッシュ上で分割管理する機構を提案する．本機構
の概要を図 3 に示す．本機構は，LLC のタグアレイの各
ブロック毎に共有データを判別するための追加情報 (共有
ビット，コア ID フィールド) と，共有データに割り当てる
ウェイ数を決定する共有データウェイ数決定器を必要とす
る．これらのハードウェアを用いて，セット上を共有デー
タが占めるウェイ数と，共有データへの割当ウェイ数 (Ws)
を把握し，データ置換時にセット上から追い出すデータを
決定する．セット上の共有データ数は Ws 以下にならず，
共有データの保護が可能になる．以下の節では，提案機構
の詳細について述べる．
3.1共有データへの割当ウェイ数の決定
共有データウェイ数決定器の概要を図 4 に示す．Ws を
決定するために，セットサンプリング [12]，シャドウディ
レクトリ，ユーティリティモニタ [9] を用いる．セットサ
ンプリングは，キャッシュアクセスのサンプリングを行
c⃝ 2015 Information Processing Society of Japan3
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
共有データ 
私有データ 
リーダーセット 
LRU優先度 
共有シャドウディレクトリ(sSD) 
リーダーセット 
LRU優先度 
私有シャドウディレクトリ(pSD) 
0	
1	
2	
3	
4	
5	
6	
7	
LRU優先度 
共有データへの 割当ウェイ数 
アドレス，コアID シャドウ 
ディレクトリ 
ヒット カウンタ 
共有データ 
ウェイ数決定器 
ユーティリティ 
LRU優先度 
図 4共有データウェイ数決定機構
前回アクセスと	
  今回アクセスの	
  コアIDが異なる	
該当アドレスの	
  LRU優先度に	
  
対応する共有データの	
  
ヒットカウンタを	
  インクリメント	
アクセスしたコアIDを	
  IDフィールドに記録	
アドレスが	
  
sSDに存在する	
アドレスが	
  
pSDに存在する	
No	
No	
pSDの	
  
LRU優先度を更新	
sSDとpSDの	
  
LRU優先度を更新	
sSDの	
  
LRU優先度を更新	
pSDの	
  
LRU優先度を更新	
該当アドレスを	
  
pSDからsSDへ移動	
  
該当アドレスの	
  LRU優先度に	
  
対応する共有データの	
  
ヒットカウンタを	
  インクリメント	
該当アドレスの	
  LRU優先度に	
  
対応する私有データの	
  
ヒットカウンタを	
  インクリメント	
pSD内のLRUタグアレイに	
  
タグアドレスを記録	
  
リーダーセットへの	
  
アクセス	
図 5シャドウディレクトリ内の管理手順
う．サンプリングされたアクセスは，シャドウディレクト
リを用いて共有データに対するヒットと私有データに対す
るヒットの判別を行い，それぞれのヒット数と再利用間隔
(LRU 優先度) の関係を明らかにする．この関係に基づき，
ユーティリティモニタ [9] は，Ws を変化させた場合のヒッ
トを予測し，Ws の増減を決定する．
3.1.1セットサンプリングを用いたアクセス情報の取得
セットサンプリングは，キャッシュの一部のセットを用
いてキャッシュへのアクセス情報を収拾する．サンプリ
ングに用いられるセットのことをリーダーセットと呼ぶ．
リーダーセットは LLC 上に 32 個 [10] あり，全セット数を
N としたとき，N/32 個の間隔で配置されている．これら
のリーダーセットにアクセスが生じた場合，アドレスとア
クセスしたコアの ID をシャドウディレクトリに通知する．
3.1.2シャドウディレクトリを用いたヒット数計測
シャドウディレクトリには，共有データをサンプリング
するためのシャドウディレクトリ (sSD) と私有データのた
めのシャドウディレクトリ (pSD) である．各ディレクト
リは通常のタグアレイと同様に，ウェイ数分のタグアドレ
スと LRU 優先度を記録するためのビットを持つ．また，
pSD についてはアクセスしたコアを記録しておくためのコ
ア ID フィールドを持つ．
図 5 にシャドウディレクトリにおけるタグアレイの具
体的な管理方法と共有データの判別方法を示す．アクセス
が発生した際には，要求されたアドレスと同じアドレスが
sSD に存在するかを確認する．sSD にアドレスが存在する
場合，該当アドレスの LRU 優先度に対する共有ヒットが
あったことをユーティリティモニタに通知する．そして，
LRU ポリシに基づき sSD の LRU 優先度を更新する．
sSD に該当のアドレスが存在せず，pSD に存在する場
合，今回アクセスしたコア ID と pSD に保存されている前
回アクセスしたコア ID を比較する．もし，異なるコアか
らのアクセスであれば，そのデータは共有データであると
みなし，該当の LRU 優先度に対する共有ヒットがあった
ことをユーティリティモニタに通知する．その後，該当ア
ドレスを sSD に保存するためにアドレスを LRU ポリシで
置換し，pSD の該当アドレスを無効化する．一方で，前回
のアクセスと同じコアからのアクセスであれば，そのデー
タを私有データであるとみなす．そして，該当アドレスの
LRU 優先度に対応する私有ヒットがあったことをユーティ
リティモニタに通知する．その後，pSD を LRU ポリシに
基づき更新する．
sSD と pSD のどちらにもアドレスが存在しなかった場
合，pSD に新しいアドレスとコア ID を記録するために，
LRU ポリシに基づきアドレスを置換する．
3.1.3ユーティリティモニタによる割当ウェイ数の決定
ユーティリティモニタは，再利用間隔とヒット数の関係
を評価するためのヒットカウンタを持つ．ヒットカウンタ
はキャッシュと同等のウェイ数分あり，共有データと私有
データそれぞれのために 2 つ用意されている．ヒットカウ
ンタは sSD または pSD でヒットが発生した場合，それぞ
れ共有データまたは私有データの通知された LRU 優先度
に対応するヒットカウンタをインクリメントする．
ヒットカウンタの計測結果に基づき，ユーティリティモニ
タは Ws を変更した場合のヒット数を算出する．ユーティ
リティモニタの Ws 決定の具体例を図 6 に示す．図 6(a)
は 8 ウェイのキャッシュにおけるヒット数の計測結果の例
を示す．この計測結果から，任意の Ws におけるヒット数
を予測することが可能である．図 6(a) では Ws = 2 である
ため，共有データにおいては，LRU 優先度が 0 から 1 まで
のヒット数の合計が実際の LLC での共有データへのヒッ
ト数 (共有ヒット数) となる．また，私有データへの割当
c⃝ 2015 Information Processing Society of Japan4
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
22 14 11 11 11 7 7 7 
23 19 19 15 7 7 7 
0	
1	
2	
3	
4	
5	
6	
7	
共有データ 
私有データ 
Ws＝2 ： 全ヒット数＝132 
Ws＝1 ： 予測全ヒット数＝125 
Ws＝3 ： 予測全ヒット数＝136 
(a)現在の割当ウェイ数	
 
(b)共有データへの割当ウェイ数を1増加させた場合	
 
(c)共有データへの割当ウェイ数を1減少させた場合	
 
LRU優先度 
0	
1	
2	
3	
4	
5	
6	
7	
LRU優先度 
0	
1	
2	
3	
4	
5	
6	
7	
LRU優先度 
22 14 11 11 11 7 7 7 
23 19 19 15 7 7 7 
22 14 11 11 11 7 7 7 
23 19 19 15 7 7 7 
共有データ 
私有データ 
共有データ 
私有データ 
共有ヒット数＝36 
私有ヒット数＝96 
予測共有ヒット数＝47 
予測私有ヒット数＝89 
予測共有ヒット数＝22 
予測私有ヒット数＝103 
図 6ヒットカウンタに基づくヒット予測
ウェイ数は 6 ウェイのため，LRU 優先度が 0 から 5 までの
ヒット数の合計が，実際の LLC での私有データへのヒッ
ト数 (私有ヒット数) となる．よって，共有ヒット数と私有
ヒット数の和は実際の LLC での全ヒット数となる．
この計測結果を用い，ユーティリティモニタは Ws を変
更した場合のヒット数を予測する．図 6(b) は図 6(a) の計
測結果に基づき Ws を 1 増加させた場合を示す．Ws を 1
増加することにより，全ヒット数が図 6(a) の場合より増
加することが予測される．一方で，図 6(c) は Ws を 1 減少
させた場合を示す．Ws を 1 減少することにより，全ヒッ
ト数が図 6(a) の場合より減少することがわかる．
図 6(b) と図 6(c) の予測結果から，Ws を 1 増加すること
により，ヒット数が増加することが予測されたので，ユー
ティリティモニタは Ws を 3 にする．もし，双方でヒット
数の増加が予測された場合，よりヒット数の増加が望める
方へ Ws を増加または減少させる．同じ増加量の場合，共
有データに多く割り当てるように，Ws を 1 増加させる．
これらの Ws の更新は 5000 万サイクルごとに行われる．
また，Ws の更新後は，すべてのヒットカウンタを 1 ビッ
ト右シフトする．これは，前の区間のアクセス傾向を考慮
しつつ，現区間における最適なウェイ数を判定するためで
以上の管理方法により，共有・私有データ毎に再利用間
隔とヒット数の関係を評価することができる．
3.2割当ウェイ数に基づく共有データの保護
3.2.1LLC における共有データの判別方法
LLC では複数のコアからアクセスされる共有データと，
単一のコアからのみアクセスされる私有データを判別す
る．これは，リーダーセット以外のセットでは，LLC の
みで共有データと私有データを識別する必要があるためで
ある．具体的には，データがキャッシュに挿入されてから
追い出されるまでに，複数のスレッドにアクセスされた場
合，本機構はそのデータを共有データと判別する．この判
別のために LLC では，共有データを判別する共有ビット
に 1 ビット，キャッシュブロック 1 つ当たりにアクセスし
たコア ID を記録するコア ID フィールドを，n コアの場
合 log n ビット分追加する．共有ビットは 0 で初期化され，
コア ID フィールドは，置換時にデータにアクセスしたコ
アの ID を記録しておく．データにアクセスがあった際に，
アクセスしたコア ID とフィールドに記録されているコア
ID を比較し，異なれば，複数のスレッドからアクセスがあ
ると判断し，共有ビットを 1 にする．一方で，同じであれ
ば，ビットは 0 のままにする．
3.2.2キャッシュ分割による共有データの保護
セット上の共有データ数と Ws を比較し，共有データ数
が Ws を下回らないようにデータ置換を管理する．ここで，
共有データの数を Ns とした際，追い出すデータを決定す
る方法を以下に示す．
• Ns < Ws共有データに与えられているウェイ数が少ない．この
とき，次にデータが挿入される際には私有データを追
• Ns > Ws共有データに与えられているウェイ数が多い．このと
き，次にデータが挿入される際には共有データを追い
• Ns = Ws共有データに与えられているウェイ数は最適である．
このとき，本機構は新たに挿入されるデータを必ず私
有データと判別するので，共有データの割合を維持す
るために私有データを追い出す．
これにより，各セットにおいて共有データが必要とする
ウェイ数を割り当てることができる．
4.性能評価
4.1評価環境
提案手法の有効性を確認するために，LLC に提案手法を
適用したプロセッサの評価を行う．評価は共有データの割
合，MPKI，速度向上について，提案手法 (Proposal) と従
来手法である LRU 置換ポリシ，SHP [3]，RWP [10]，SBR
と比較を行う．評価環境は予備実験と同等とし，表 2 の
パラメータを用いる．提案手法と RWP のベースポリシは
c⃝ 2015 Information Processing Society of Japan5
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
0.1	
  0.2	
  0.3	
  0.4	
  0.5	
  0.6	
  0.7	
  0.8	
  0.9	
  
canneal	
  
is	
  
mg	
  
ocean.cont	
  
ocean.ncont	
  
streamcluster	
  
共有データの割合	
LRU	
  RWP	
  SHP	
  Proposal	
  SBR	
  
図 7LLC を占める共有データの割合
0.2	
  
0.4	
  
0.6	
  
0.8	
  
1.2	
  
1.4	
  
canneal	
  
is	
  
mg	
  
ocean.cont	
  
ocean.ncont	
  
streamcluster	
  
GM	
  
正規化MPKI	
RWP	
  SHP	
  Proposal	
  SBR	
  
図 8MPKI
LRU ポリシとする．ベンチマークは予備実験で選択した
ものを用いる．
4.2共有データの割合の評価
提案手法により共有データが保護されているかを確認す
るために，共有データの割合を評価した．各ベンチマーク
の共有データの割合の結果を図 7 に示す．図 7 の縦軸は，
各ポリシにおける共有データの割合を示し，横軸はベンチ
マークを示す．
図 7 から，提案手法の共有データの割合は，LRU の割
合に比べ高いことがわかる．したがって，提案手法は共有
データの保護を可能にすることが明らかとなった．また，
各ベンチマークにおける提案手法の共有データの割合は，
既存手法よりも高いことがわかる．したがって，共有デー
タの保護は，既存手法よりも有効であることが明らかと
また，提案手法の共有データの割合は，SBR と比較して
少ないため，Ws を決定する機構に改善の余地があること
4.3MPKI の評価
提案手法により MPKI の削減が可能かを確認するため
に MPKI を評価した．各ベンチマークの MPKI の結果を
図 8 に示す．図 8 の縦軸は，各ポリシにおける MPKI を
0.1	
  0.2	
  0.3	
  0.4	
  0.5	
  0.6	
  0.7	
  0.8	
  0.9	
  
0	
   5	
   10	
  15	
  20	
  25	
  30	
  35	
  40	
  45	
  50	
  55	
  60	
  65	
  70	
  75	
  80	
  85	
  90	
  95	
  
共有データの割合	
実行時間[5Mサイクル]	
Proposal	
  SBR	
  
図 9LLC を占める共有データの割合の時間変化：mg
示し，LRU ポリシの MPKI で正規化されている．横軸は
ベンチマークと相乗平均 (GM) を示す．図 8 から，提案手
法は LRU ポリシと比較して，streamcluster で最大 73.0%，
平均で 24.5%の MPKI を削減が得られることがわかる．ま
た，RWP，SHP，と比較しても，それぞれ 19.9%，10.6%，
の MPKI の削減が得られることがわかる．したがって，提
案手法により並列プログラムの MPKI の削減が可能であ
ることが明らかとなった．
streamcluster において提案手法が大幅に MPKI を削減
した理由は以下の通りである．このベンチマークはスト
リームアクセスを行うプログラムである．ワーキングセッ
トは 16MB [5] であるため，LRU ポリシで管理されている
8MB の LLC では私有データのスラッシングを引き起こす．
このことは，実行区間における Ws は 15 を保ち続けたこ
とからも明らかである．そして，このような場合セットに
挿入される私有データは，次の置換によって直ちに追い出
される．これにより，私有データのスラッシングから共有
データを保護し，MPKI が減少した．
ocean.cont と ocean.ncont において，提案手法は MPKI
を削減できていないが，SHP では MPKI を大幅に削減し
ている．これは，これらのベンチマークの時間的局所性
が低く，空間的局所性が高いためだと考えられる．また，
キャッシュアクセスのほとんどが，私有データに対するア
クセスであり，共有データを保護することで得られるヒッ
ト数は多くなかった．よって，LRU ポリシをベースとして
いる RWP と提案手法では MPKI を削減できず，アクセス
が多いデータを保護する SHP は MPKI を大幅に削減した
と考えられる．
mg において提案手法の MPKI は LRU ポリシに比べて
増加していることがわかる．このベンチマークでは，提案
手法により共有ヒット数は増加したが，私有ヒット数は大
きく減少していた．この原因を解析するために，図 9 に mg
の LLC を占める共有データの割合の時間変化を示す．図 9
の縦軸は 2 つのポリシにおける LLC を占める共有データ
の割合を示し，横軸は実行時間を示す．図 9 より，ほとん
どのサンプリング区間において，提案手法の共有データの
c⃝ 2015 Information Processing Society of Japan6
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
0.2	
  0.4	
  0.6	
  0.8	
  
1.2	
  1.4	
  1.6	
  1.8	
  
canneal	
  
is	
  
mg	
  
ocean.cont	
  
ocean.ncont	
  
streamcluster	
  
GM	
  
速度向上	
RWP	
  SHP	
  Proposal	
  SBR	
  
図 10速度向上
割合は SBR の割合よりも高いことがわかる．よって，提
案手法では共有データの過剰な保護が私有データのヒット
数減少につながり，MPKI が増加したと考えられる．共有
データの過剰な保護の原因究明は今後の課題である．
4.4速度向上の評価
提案手法により性能向上が得られるかを確認するため
に，速度向上を評価した．各ベンチマークの速度向上の結
果を図 10 に示す．図 10 の縦軸は，LRU ポリシに対する
各ポリシの速度向上を示し，横軸はベンチマークと相乗平
均を示す．図 10 から，提案手法は LRU ポリシと比較し
て最大 1.70 倍，平均で 1.13 倍の速度向上が得られること
がわかる．また，RWP，SHP，と比較しても，それぞれ
1.08 倍，1.05 倍，の速度向上が得られることがわかる．し
たがって，本提案手法は並列プログラムの実効性能向上に
有効であることが明らかとなった．
提案手法は，is の MPKI 削減に見合った性能向上が得ら
れていない．これは，2.1 節で示したように，is は私有デー
タが共有データによって追い出されているベンチマークで
あるためだと考えられる．しかし，提案手法が共有データ
の割合を増加させたため，私有データの割合が減少した．
この結果，性能への影響が大きい私有データのヒット数が
減少し，性能向上を得ることができなかったと考えられる．
各データの性能に対する影響度の詳細な解析については今
後の課題とする．
4.5ハードウェアオーバーヘッドの評価
ハードウェアオーバーヘッドの比較評価を行う．まず，
提案手法に必要な追加のハードウェアについて述べる．提
案手法では，共有データを判別するためのコア情報を記録
するビット，共有データと私有データの再利用間隔を計測
するシャドウディレクトリ，ヒット数を計測するヒットカ
ウンタの 3 つの追加のハードウェアが必要である．この 3
つについて，実験環境と同様のコア数 8，LLC の容量 8MB
と仮定した場合の LRU ポリシに対するハードウェアオー
バーヘッドについて以下に示す．
• 共有データの判別
LLC の各ブロックには，共有データを判別するために
1 ビット，前回アクセスしたコアの ID を記録するた
めのビットを，コア数を n とした場合，log n ビット分
必要である．したがって，64KB の追加のハードウェ
アが必要となる．
• シャドウディレクトリ
セットサンプリングを行うシャドウディレクトリは，
ウェイ数分のブロックが必要である．各ブロックには，
タグアドレスを保存するために 27 ビット [13]，LRU
優先度を保存するために 4 ビット，コアのアクセス情
報を記録するために 3 ビット必要である．また，共有
データと私有データそれぞれのために 2 つのシャド
ウディレクトリが必要である，これらはサンプルセッ
トの数だけ必要である．したがって，4.1KB の追加の
ハードウェアが必要となる．
• ヒットカウンタ
分割サイズを動的に決定するためのヒットカウンタは
12 ビット [10] からなり，ウェイ数分必要である．ま
た，ヒットカウンタは共有データと私有データのヒッ
ト数を計測するために 2 つ必要である．したがって，
48B の追加のハードウェアが必要となる．
ユーティリティモニタに必要な比較器のハードウェアコス
トは非常に小さく無視できる [9] のでここでは考慮しない．
以上をまとめると，本提案手法に必要な追加のハードウェ
アは 68.1KB となり，0.83%のハードウェアオーバーヘッ
次に，RWP のコストについて述べる．セットサンプリ
ングに 4.2KB 必要であり，また，書き込みが行われたこと
を判別するために 1 ブロックあたり 1 ビット必要である．
したがって，RWP に必要な追加のハードウェアは 20.2KB
となり，0.25%のハードウェアオーバーヘッドとなる．
最後に，SHP のコストについて述べる．SHP は置換対
象のブロックを決定するために優先度を計算する必要が
ある．優先度は，共有度とヒット数から計算されるため，
LRU 優先度の情報を必要としない．共有度はデータにア
クセスするコア数から算出されるため，コア数を n とした
とき，1 ブロックあたり n ビット必要である．また，ヒッ
ト数を計測するために 4 ビット [14] 必要である．したがっ
て，SHP に必要な追加のハードウェアは 128KB となり，
1.56%のハードウェアオーバーヘッドとなる．
提案手法のハードウェアオーバーヘッドは RWP と比較
すると 0.56%高いが，それに対する性能向上を考えると提
案手法の方が優れている．また，提案手法のハードウェア
オーバーヘッドは SHP を比較すると 0.73%低い．今回の評
価環境では 8 コアで LLC 容量が 8MB を想定しているが，
コア数を増大するとこのオーバーヘッドの差はさらに増大
する．具体的に，64 コアで LLC 容量を 64MB を想定した
c⃝ 2015 Information Processing Society of Japan7
Vol.2015-ARC-216 No.38
2015/8/6
情報処理学会研究報告IPSJ SIG Technical Report
場合，ハードウェアオーバーヘッドは SHP では 12.5%と
なるが，提案手法では 1.37%となる．したがって，提案手
法は SHP よりも拡張性に優れていることがわかる．
5.おわりに
マルチコアプロセッサ上で並列プログラムを実行する場
合，複数のスレッドで共有されるデータが LLC に保存さ
れる．しかし，再利用性の低い私有データの保存によって
再利用性の高い共有データが追い出される問題がある．本
論文では，並列プログラムの実効性能向上を目的とし，共
有データを考慮したキャッシュ分割機構を提案した．本機
構は，キャッシュ分割を用いて共有データのみを保存する
領域を確保することにより，共有データを私有データから
保護することが可能である．評価結果から，LRU 置換ポリ
シと比較して，最大で 1.70 倍，平均で 1.13 倍の性能向上
が得られた．
今後の課題として，共有データの保護によって性能向上
が得られないベンチマークの詳細な解析と，解析結果に基
づく提案機構の改善が挙げられる．
[1]Moore, G. E. et al.: Cramming more components ontointegrated circuits, Electronics Magazine, p. 4 (1965).
[2]Natarajan, R. and Chaudhuri, M.: Characterizing multi-threaded applications for designing sharing-aware last-level cache replacement policies, Workload Characteri-zation (IISWC), 2013 IEEE International Symposiumon, IEEE, pp. 1–10 (2013).
[3]Muthukumar, S. and Jawahar, P.: Sharing and Hit basedPrioritizing Replacement Algorithm for Multi-ThreadedApplications, International Journal of Computer Appli-cations, Vol. 90, No. 12 (2014).
[4]Carlson, T. E., Heirman, W. and Eeckhout, L.: Sniper:Exploring the Level of Abstraction for Scalable and Ac-curate Parallel Multi-Core Simulations, InternationalConference for High Performance Computing, Net-working, Storage and Analysis (SC), pp. 52:1–52:12(2011).
[5]Bienia, C., Kumar, S., Singh, J. P. and Li, K.: ThePARSEC benchmark suite: characterization and archi-tectural implications, Proceedings of the 17th interna-tional conference on Parallel architectures and compi-lation techniques, ACM, pp. 72–81 (2008).
[6]Woo, S. C., Ohara, M., Torrie, E., Singh, J. P. andGupta, A.: The SPLASH-2 programs: Characterizationand methodological considerations, ACM SIGARCHComputer Architecture News, ACM, pp. 24–36 (1995).
[7]Bailey, D. H., Barszcz, E., Barton, J. T., Browning,D. S., Carter, R. L., Dagum, L., Fatoohi, R. A., Freder-ickson, P. O., Lasinski, T. A., Schreiber, R. S. et al.: TheNAS parallel benchmarks, International Journal of HighPerformance Computing Applications, Vol. 5, No. 3, pp.63–73 (1991).
[8]Rajan, K. and Govindarajan, R.:Emulating optimalreplacement with a shepherd cache, Microarchitecture,2007. MICRO 2007. 40th Annual IEEE/ACM Inter-national Symposium on, IEEE, pp. 445–454 (2007).
[9]Qureshi, M. K. and Patt, Y. N.: Utility-based cache par-titioning:A low-overhead, high-performance, runtimemechanism to partition shared caches, Proceedings of the39th Annual IEEE/ACM International Symposium onMicroarchitecture, pp. 423–432 (2006).
[10]Khan, S., Alameldeen, A. R., Wilkerson, C., Mutluy,O. and Jimenezz, D. A.: Improving cache performanceusing read-write partitioning, High Performance Com-puter Architecture (HPCA), 2014 IEEE 20th Interna-tional Symposium on, IEEE, pp. 452–463 (2014).
[11]Chandra, D., Guo, F., Kim, S. and Solihin, Y.: Pre-dicting inter-thread cache contention on a chip multi-processor architecture,High-Performance ComputerArchitecture, 2005. HPCA-11. 11th International Sym-posium on, IEEE, pp. 340–351 (2005).
[12]Qureshi, M. K., Lynch, D. N., Mutlu, O. and Patt,Y. N.: A case for MLP-aware cache replacement, ACMSIGARCH Computer Architecture News, Vol. 34, No. 2,pp. 167–178 (2006).
[13]Intel:Intel Xeon Processor E7-8890 v3 (45M Cache,2.50 GHz), http://ark.intel.com/products/84685/Intel-Xeon-Processor-E7-8890-v3-45M-Cache-2_50-GHz.
[14]Kharbutli, M. and Solihin, Y.: Counter-based cache re-placement and bypassing algorithms, Computers, IEEETransactions on, Vol. 57, No. 4, pp. 433–447 (2008).
c⃝ 2015 Information Processing Society of Japan8
Vol.2015-ARC-216 No.38
2015/8/6