社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

キャッシュヒット率の向上のための基本ブロックのアドレスオフセットの探索
後藤 潤哉†

石浦菜岐佐†† 関西学院大学 理工学部 〒 669–1337 兵庫県三田市学園 2-1
あらまし 本稿では, プログラムの基本ブロックの前にキャッシュブロックサイズよりも細かい単位でオフセットを挿入することにより, 命令メモリのキャッシュミスを削減する手法を提案する. 本手法では, キャッシュシミュレーションに基づいて, キャッシュミス数を最小化するオフセットの組み合わせを求める. 可能なオフセットの組み合わせを全探索すると, オフセット挿入箇所の指数に比例する計算時間が必要になるため, 本稿ではシミュレーテッドアニーリングにより解の探索を行う. 1 レベルのダイレクトマッピングキャッシュを想定し, 7 つのベンチマークに対して, 実験を行ったところ, 30 箇所のオフセット挿入によって平均約 10%のキャッシュミスを削減することができた.
キーワード

キャッシュメモリ， シミュレーテッドアニーリング， オフセット, キャッシュミス率, 基本ブロック

Exploration of Address Oﬀsets of Basic Blocks
for Cache Hit Ratio Improvement
Junya GOTO† and Nagisa ISHIURA†† Kwansei Gakuin University, Gakuen 2–1, Sanda, Hyogo, 669–1337, Japan
Abstract This article proposes a method of reducing cache misses on an instruction memory by inserting oﬀsets
before basic blocks of a given program. The addresses of the basic blocks are adjusted by a unit smaller than thecache block size. A combination of the oﬀsets that minimizes cache miss counts, which are computed by cachesimulation, is searched. Since exhaustive search would require time exponential to the number of the oﬀsets, the solution is searched by simulated annealing. An experiment on 7 benchmarks, assuming a single-level direct-mapping
instruction cache, resulted in about 10% reduction in the cache miss count on average.
Key words cache memory, simulated annealing, oﬀset, cache miss rate, basic block

1. は じ め にを調整することによって, キャッシュミスの削減を図る研究も行われている. 文献 [2] では, プログラムとプロファイル情報を入キャッシュメモリ (以下, キャッシュと略する) は, CPU とメ力として, キャッシュミスが最小となるように基本ブロックの配インメモリの速度差を吸収するための高速で小容量のメモリで置アドレスを決定する. 基本ブロック間の遷移確率に基づいて,ある. プログラムの性能はキャッシュのヒット率に大きく左右

1 つ以上の基本ブロックを 「トレース」 としてまとめ, キャッされるが, キャッシュのヒット率はプログラムやデータを配置すシュ上での衝突を最小にするような各トレースの配置アドレスるアドレスや, キャッシュの構成等の様々な要因で変化する. こを整数線形計画法で求めている. トレースは, キャッシュブロッのため, プログラムおよびキャッシュ構成を調整してキャッシュクサイズの境界に整列することを想定しており, オフセットまミスを削減する研究が多く行われている.

で考慮した基本ブロックの配置は行っていない. また, 文献 [3]

文献 [1] では, 与えられたプログラムを高速に実行するため

では, 最悪実行時間 (WCET) を考慮して基本ブロックの配置のキャッシュ構成を求めている. プログラムのトレースに対すアドレスを決定することにより, キャッシュのコンフリクトミスるシミュレーションに基づいて, キャッシュミスを最小化するの削減を図っている. この手法では, 静的コード解析に基づいキャッシュサイズ, ブロックサイズ, 連想度の組み合わせを求めて衝突グラフを作成し, 基本ブロックまたは関数の最適な配置る. このアプローチは, プログラムに合わせてキャッシュ側を最アドレスを求める. この手法においても, 基本ブロックはキャッ適化するものである.

シュブロックサイズに整列することを想定している.

これに対し, 与えられたキャッシュ構成に対してプログラム側

これに対し, 文献 [4] では, 基本ブロックのアドレスをキャッ—1—

シュブロックサイズよりも細かい単位で調整することによって,キャッシュミスを削減することを試みている. 複数の基本ブロッaddress

tag

index

offsetクの直前にオフセットを挿入することによってアドレスの調整tagを行い, キャッシュミスを最小化するオフセットの組み合わせを

0キャッシュシミュレーションによる全探索で求める. シミュレー

1

data…

ションによって, 与えられたトレースに対する厳密なキャッシュi…

ミス数を求めることができるが, 探索にはオフセット挿入箇所の指数に比例する計算量が必要となる. このため, この文献でẚ㍑ᅇ㊰1

は, 二分決定グラフ (BDD) [5] を用いてこのシミュレーションを高速化する手法を提案しているが, オフセットの挿入箇所はhit / miss

10 箇所程度に限られる.

図 1 キャッシュメモリの構成

そこで本稿では, シミュレーテッドアニーリングを用いて文献 [4] の探索に要する時間を削減し, オフセットの挿入箇所を増やす方法を提案する. 複数の基本ブロックの前に挿入するオフセット量の組み合わせをシミュレーテッドアニーリングの状態とし, キャッシュシミュレーションにより求めるキャッシュミス数を評価関数として最小化を行う. 7 つのベンチマークプログラ
ムに対して実験を行った結果, 命令メモリの 30 箇所にオフセットを挿入することにより, キャッシュミスを平均約 10.36%削減することができた.
以下, 本稿では, 2 章でキャッシュメモリについて要点を整理した後, 3 章で提案手法について述べる. 4 章で実験結果を示し,5 章でまとめと今後の課題を述べる.

レスは, ブロックサイズの倍数に限定しない. ただし, 基本ブロックの順序の入れ替えは行わないものとする.
オフセットは基本ブロックの直前に挿入するが, 連続して実行される可能性がある基本ブロックの間には挿入しないものとする. 例えば, 図 2 (a) では, 条件分岐で終了する基本ブロック

BB1 の次に BB2 が続いているが, BB1 と BB2 は連続して実行される可能性があるため, この間にオフセットは挿入しない.

(b) の BB4 は無条件分岐で終了しているため, その直後にはオフセットを挿入しても良い. BB6 は無条件分岐の分岐先であるが, 直前の BB5 と連続して実行される可能性があるため, BB6の前にオフセットを挿入することはできない.

2. キャッシュメモリ
本稿では, ダイレクトマッピング (direct mapping) のキャッBB1シュを扱う. また, キャッシュのレベル数は 1 とする.

䜸䝣䝉䝑䝖
ᤄධ୙ྍ

BB4
䜸䝣䝉䝑䝖
ᤄධྍ

BB2

BB5

フィールドに分けられる. キャッシュは, サイズ 2b バイトのブBB3

BB6

ロック (ライン) 単位でメインメモリ上のデータのコピーを管(a)(b)

メモリアクセスに用いられるアドレスは, 図 1 に示すように, 上位から tag, index (c ビット), oﬀset (b ビット) の 3 つの䜸䝣䝉䝑䝖ᤄධ୙ྍ理する. キャッシュには 2c 個のブロックが収容でき, キャッシュの容量は 2b+c バイトである. キャッシュの i 番目の位置には,

図 2 オフセット挿入箇所

index フィールドの値が i であるブロックのデータが, ブロッ
クを識別するための tag フィールドの値とともに格納される.

index が i のアドレスにアクセスがあった時, そのアドレスの基本ブロックが 1 つの場合には, 図 3 (a) のように, 基本ブtag の値がキャッシュに格納されている tag と等しければキャッロックの開始アドレスをブロックサイズの境界に整列すれば,シュヒット, そうでなければキャッシュミスが発生する. キャッ

必ず使用ブロック数が最小になる. しかし, 複数の基本ブロッシュミスが発生した場合には, キャッシュの i 番目の エントリ

クがある場合には, (b) のように, 基本ブロックをブロックサイを新しいものに更新する.

ズ境界に整列しない方が使用ブロック数が少なくなることがあキャッシュミスは, キャッシュ容量の不足に起因する容量性ミる. また, (c) のように, 連続する基本ブロック BB1, BB2 のうス (capacity miss), index が等しいアドレスのアクセス衝突にち後続 BB2 が高頻度で実行されるような場合には, BB1 をブ起因する (conflict miss), キャッシュブロックを最初にアクセスロックサイズ境界からオフセットさせることにより BB2 の使する時に発生する初期参照ミス (compulsory miss) に分類され用ブロック数を減らすことができる.

るが, 本稿では特にこれを区別しない.

本稿では, このような考察に基づき, 基本ブロックをブロックサイズ境界に整列させる以外のアドレス調整を探索する.

3. 基本ブロックのオフセット探索

3. 2 キャッシュミス数を最小化するオフセットの探索

3. 1 オフセットによる基本ブロックのアドレス調整

本稿では, 機械語のプログラムおよび命令メモリのトレース

本稿では命令メモリを対象に, 基本ブロックの開始アドレス(実行された命令アドレスの系列) が与えられた時に, キャッシュをオフセットの挿入により調整する. 基本ブロックの開始アドミス数が最小となるオフセットの組み合わせを求める. ブロッ—2—

Main Memory

与えられた時に, ms,a (v) を最小にする v を求める問題である.

Main Memory

3. 3 探 索 手 法
本稿では, この最小化問題の解を, メタヒューリスティク

3BB1BB1スの 1 つであるシミュレーテッドアニーリング法 (simulated2annealing) [6] により求める.
オフセットレベル v = (v1 , v2 , · · · , vm ) をそのまま探索の状態とし, ms,a (v) を目的関数として最小化する. v が与えられた(a) 基本ブロックが１つの場合時の ms,a (v) は, キャッシュシミュレーションにより求める.
Main Memory

Main Memory

BB1BB1v に対し, i 番目のオフセットレベルのみが異なっており, その差が d 以下であるようなオフセットレベルの集合を Nv,i,dとする.
34| i), ui =| vi , | ui −vi | <Nv,i,d = {u ∈ Lmk | vj = uj (f or j == d}BB2BB2シミュレーテッドアニーリングの総冷却回数が C, ある時点までの冷却回数が c の時, r = (C − c)/C をその時点での冷却回(b) 基本ブロックが複数の場合数の残率と呼ぶことにする. 冷却回数の残率 r におけるオフ
Main Memory
BB1BB2∆r = (1 − r) +BB1
31000ᅇ

セットレベルの許容変動幅 ∆r を次のように定義する.

Main Memory

BB21000ᅇ

22k2r

この時, 本手法では, 冷却回数の残率 r における状態 v の近傍

Nv,r を次のように定義する.
Nv,r =(c) 実行回数の多い基本ブロックが後続にある場合
図3

基本ブロックのアドレス調整

m∪

Nv,i,∆ri=1

シミュレーテッドアニーリングの初期状態は Lmk からランダムに選び, v の次状態は, Nv,r からランダムに選ぶ.

クサイズやキャッシュサイズは固定されているものとする.
オフセットは機械語プログラムの m 箇所 (前節で述べたオフセ

4. 実 験 結 果

ットが挿入可能な基本ブロックの先頭) に挿入するものとし, その提案手法に基づくオフセット探索プログラムを C 言語 で実アドレスを, s = (s1 , s2 , · · · , sm ) (ただし, s1 < s2 < · · · < sm )装した. 本プログラムは Windows Cygwin, Ubuntu Linux 等とする. 各オフセットは, u バイト単位で 0 から始まる 2k 段階のの環境で動作する.

値を取るとする. 即ち, オフセットの値は 0, u, 2u, · · · , (2k −1)u

実験には 7 つのベンチマークを ARM 用にコンパイルしたのいずれかである. Lk = {0, 1, 2, · · · , (2k − 1)} とする. 以下ものを用いた. 各プログラムのトレース長と基本ブロックは数では挿入するオフセットの段階 (単位数) をオフセットレベル

は表 1 に示すとおりである.と呼び, アドレス si に挿入するオフセットレベルを vi ∈ Lk とする. この時, アドレス si に挿入するオフセットは vi · u バイ
トとなる. アドレス s = (s1 , s2 , · · · , sm ) に挿入するオフセッ
トレベルが v = (v1 , v2 , · · · , vm ) の時, アドレス a は次のように定義されるアドレス ts,v (a) にマップされる.

ai∑
a+vj · uts,v (a) =j=1m∑
a+vj · u(a < s1 )(si <= a < si+1 )表 1 ベンチマークプログラムの諸元プログラム

トレース長

基本ブロック数

mips

29,853224

mpeg2

35,661

256

gsm

52,659287

dfmul

102,079

431

dfdiv

179,681

497

adpcm

189,242

283

dfadd

251,911478(sm <= a)j=1

表 2 は, ベンチマークのうちトレース長の短い 3 つについて,オフセット挿入箇所数 m を 4 に限定して実験を行った結果で

s へ の オ フ セット レ ベ ル v の 挿 入 に よ り, ト レ ー ス a =ある. 各オフセットの値は 4 バイト単位の 32 段階 (最小 0 バイa1 a2 · · · an は, ts,v (a) = ts,v (a1 )ts,v (a2 ) · · · ts,v (an ) にマップ

ト, 最大 124 バイト) で探索した. キャッシュブロックサイズはされる. トレース ts,v (a) に対するキャッシュミス数を ms,a (v)32, キャッシュサイズは 64 または 256 である. 「全探索」 は,とすると, 本稿で扱うキャッシュミス数最小化問題は, a と s が可能なオフセットの全組み合わせに対してシミュレーションを—3—

表 2 キャッシュミス数の比較

ロックの数が m より小さくなり, 削減効果がほとんどない空間(オフセット挿入箇所数 m=4)を探索しているためと考えられる.
表 5 は探索に要した時間である. CPU は Core i7, メモリ

キャッシュ
サイズ

キャッシュミス数

mips

25624,795 24,795

ミュレーションで求めているため, 探索時間はトレース長に比mpeg26430,883 30,883例して増加する. 現在, アドレスのマッピングを線形探索で求め

gsm

256

46,360 46,360

プログラム

全探索

SA

オフセット: 4 バイト単位, 32 段階
ブロックサイズ: 32

は 7.7GB, OS は Ubuntu 14.04 である. キャッシュミス数をシているため, m に比例する計算時間が必要になっているが, この点には改善の余地がある.
表 4 提案手法のキャッシュミス率表 3 基本ブロックのキャッシュブロック境界からのオフセット
プログラム

オフセット [バイト]mips(16, 20, 0, 8) × 2

mpeg2(16, 24, 20, 8) × 144

gsm(0, 4, 0, 4) × 1, (0, 4, 24, 4) × 3,

プログラム

キャッシュサイズ

キャッシュミス率

m=0

m=20

m=30

m=40

256 17.07%

9.81%

8.75%

8.17%

mpeg2

64 13.45%

13.36%

13.36%

13.35%gsm

256 12.05%

8.15%

7.79%

7.78%

dfmul

4096

6.93%

5.39%

5.24%

5.69%

dfdiv

1024

9.48%

8.84%

8.62%

8.28%

行う方法である. 「SA」 は, 本稿のシミュレーテッドアニーリ

adpcm

128 10.41%

9.98%

9.98%

9.98%

ングであり, 冷却率は 0.95, 冷却回数は 90 回, 反復回数は 1000

dfadd

9.89%

10.15%

10.75%(0, 12, 0, 4) × 1, (0, 12, 24, 4) × 3

mips回に設定した. この規模の問題では, シミュレーテッドアニー
リングで厳密な最小解が得られている.

1024 11.55%−2.22% −2.44% −2.42%

増減 (平均)キャッシュミス削減率 (平均)9.72%

10.36%

9.82%

m: オフセット挿入箇所数表 3 は, 表 2 の実験の全探索において, キャッシュミス数を最オフセット: 4 バイト単位, 32 段階

小にする全てのオフセットの組み合わせについて, 基本ブロッブロックサイズ: 32

クのキャッシュブロック境界からのオフセットを列挙したものである. 例えば, mips の「 (16, 20, 0, 8) 」 は, キャッシュミス
表5 探索時間数が最小になった時の 4 つの基本ブロックのキャッシュブロック境界からのオフセットが, それぞれ 16, 20, 0, 8 バイトであっ探索時間 [秒]

プログラム

m=20

m=30

m=40

mips

331.60511.24740.23

mpeg2

436.53626.65766.99gsm

581.85849.07 1237.85

mpeg2 では 144 通りの組み合わせについて, キャッシュブロッ

dfmul

1133.50 1676.44 3286.88

ク境界からのオフセットは全て等しかった. gsm は 8 通りの組

dfdiv

2011.96 3002.86 4086.46

み合わせが 4 パターンに分類された. 4 つの基本ブロックが全adpcm

1966.37 3123.24 3968.00てキャッシュブロック境界に整列されている場合には, このオフdfadd

2983.11 4252.70 5966.49

セットは (0, 0, 0, 0) となるが, 表 3 にはこれが現れていない.

CPU: Core i7 1.80GHz, メモリ: 7.7GBたことを表す. 「×2」 は, キャッシュミス数を最小にするオ
フセットの組み合わせは全部で 2 通りあったが, キャッシュブロック境界からのオフセットはいずれも等しかったことを表す.

これは, ブロックサイズよりも細かい単位で基本ブロックのアドレスを調整することにより, キャッシュミスを削減できることを意味する.

5. む す び

オフセット挿入箇所数 m を 20〜40 に増やして実験を行っ

本稿では, プログラムの基本ブロックの前にキャッシュブロッた結果を表 4 に示す. 表 2 の実験と同様, 各オフセットの値はクサイズよりも細かい単位でオフセットを挿入することにより,4 バイト単位の 32 段階とし, キャッシュブロックサイズは 32 と命令メモリのキャッシュミスを削減する手法を提案した. 7 つした. キャッシュサイズは 表 2 に示した通りである. 挿入箇所のベンチマークに対して, 実験を行った結果, 平均約 10.36%のは, 実行回数が最も多い m 個の基本ブロックの前とした. シ

キャッシュミスを削減することができた.

ミュレーテッドアニーリングの冷却率は 0.97, 冷却回数は 152回, 反復回数は 1000 回とした.

m = 0 はオフセットを全く挿入しない場合であり, オフセッキャッシュミスは個々の要因だけでなく, 様々な要因の組み合わせでも大きく変化するため, これらを考慮した最適化について検討することが今後の課題として挙げられる.

ト挿入によりキャッシュミス率が削減できていることがわかる.

m = 30 の時に最も効果が大きく, キャッシュミス率が平均で謝辞

2.44% 削減できている. これは, キャッシュミスが 10.36% 削

た関西学院大学理工学部 石浦研究室の諸氏に感謝します.

本研究を進めるにあたり, 多くのご助言やご協力を頂い減できていることに相当する. m を増やしてもヒット率が減少しないプログラムが見られるが, これは実行回数が多い基本ブ

—4—

文

献

[1] Nobuaki Tojo, Nozomu Togawa, Masao Yanagisawa andTatsuo Ohtsuki: “Exact and Fast L1 Cache Simulation forEmbedded Systems,” in Proc. Asia and South Pacific Design Automation Conference (ASP-DAC 2009), pp. 817–822(Jan. 2009).
[2] Hiroyuki Tomiyama and Hiroto Yasuura: “Code Placement
Techniques for Cache Miss Rate Reduction,” ACM Transactions on Design Automation of Electronic Systems (TODAES) Vol. 2, No. 4, pp. 410–429 (Oct. 1997).
[3] Heiko Falk and Helena Kotthaus: “WCET-Driven CacheAware Code Positioning,” in Proc. 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES ’11), pp. 145–154 (Oct. 2011).
[4] 林憲太郎, 平見健太, 石浦菜岐佐: “オフセット探索のためのキャッシュシミュレーションの二分決定グラフによる高速化,” 電子情報通信学会ソサイエティ大会, A-3-3 (Sept. 2015).
[5] 石浦菜岐佐: “BDD とは,” 情報処理, 第 34 巻, 第 5 号, pp. 585–592 (May 1993).
[6] 喜多一: “シミュレーテッドアニーリング,” 日本ファジィ学会誌
Vol. 9, No. 6, pp. 870–875 (Dec 1997).

—5—