1
情報数理工学/コンピュータサイエンス実験第二 A/B
「キャッシュシミュレーション」
担当：三輪忍
本書は，電気通信大学 I 類授業科目「情報数理工学実験第二 A/B」および「コンピュー タサイエンス実験第二 A/B」における課題名「キャッシュシミュレーション」の手引書で す．本課題を履修する学生は，本書をよく読んだ上で授業に臨んでください． １．本実験の目的 本実験の目的は，多くの CPU に搭載されており，性能への影響が大きなハードウェアで あるキャッシュについて，シミュレーションとエントリ置換アルゴリズムの開発を通して その理解を深めることにあります．エントリ置換アルゴリズムの開発を通して，コンピュー タアーキテクチャ研究の面白さを知ってください． ２．評価基準 本実験の成績はラウンド終了後に提出するレポートの内容により評価します．評価は，開 発したアルゴリズムの独自性と有用性，および，レポートの読みやすさの 3 つの観点から 行います．独自性に関しては，単にどこかの文献に記載されているアルゴリズムを実装した 場合よりも，各自が工夫して編み出したアルゴリズムを実装した場合の方が評点は高くな ります．また，有用性に関しては，開発アルゴリズムのシミュレーション結果がよい程（具 体的には IPC (Instruction Per Cycle) とキャッシュヒット率が高い程）評点は高くなりま す．皆さん，有用でオリジナリティに溢れるアルゴリズムを頑張って開発してください． ３．実験スケジュール 本実験は明確な中間目標を設けていません．全 7 回の授業時間を自由に使って実験を進 めてください．実験終了までの時間配分の一例を以下に挙げますので参考にしてください． 授業日 内容 第 1 回 実験概要とキャッシュの理解，および，実験環境のセットアップ 第 2 回 実装するアルゴリズムの検討 第 3 回 アルゴリズムの実装とデバッグ作業 第 4 回 第 5 回 実装したアルゴリズムの初期評価と改良作業 第 6 回 第 7 回 最終評価（報告用データの取得）とレポートの執筆2 ４．実験方法 本章では具体的な実験方法を説明します．本章をよく読んで作業を進めてください． 4.3 章以降はキャッシュの構造や動作について既に十分に理解していることが前提となっ ています．キャッシュの理解に自信がない学生は，4.3 章に進む前に，まずはキャッシュの 構造と動作を理解した方がよいでしょう．キャッシュの勉強には文献[1]の 5.3 章と 5.4 章 を熟読することを強く勧めますが，本書の 5 章の内容を理解すればレポート作成に必要な 最低限の成果を得ることは可能だと思います． 実験が思うように進まない学生へのヒントが本書の 6 章に記載されています．実験に行 き詰まりを感じた場合は 6 章を読んでください． ４．１．環境設定
始めにシミュレーション環境の設定を行います．CED の端末（OS は Ubuntu を選択）に 自分のアカウントでログインし，以下の手順に従って環境設定を行ってください． (1) ChampSim のダウンロード 実験に使用するシミュレータ (ChampSim) を GitHub のレポジトリ[2]からダウ ンロードします．ChampSim のダウンロード手順は以下の通りです． I. ターミナルを起動 II. ターミナル上で以下を入力
git clone https://github.com/ChampSim/ChampSim.git
上記の操作により，「git clone」を実行したディレクトリの下に「ChampSim」とい う名前のディレクトリが生成されます．以後，後者のディレクトリをルートディレク トリと呼びます． (2) 実行/解析用スクリプトのコピー 次に，実験に使用する実行用/解析用プログラムを取得します．ルートディレクト リに移動し，以下のコマンドを実行してください． cp –r /home3/staff/ma002344/.ced_centos/MICS2/ChampSim/myscript . 「myscript」というディレクトリが生成されます．「.sh」や「.py」などの拡張子を 持ついくつかのファイルが「myscript」の中に存在することを確認してください．
3 ４．２．ChampSim と実行/解析用スクリプトの動作確認 続いて，ChampSim と実行/解析用スクリプトの動作確認を行います． ChampSim は，命令の実行トレース（以後トレースと呼びます）を入力として与えること により，キャッシュなどの CPU 内ハードウェアの挙動をシミュレートします．トレースと はプログラムを実行した際の命令の実行系列のことです．トレースの例を図 1 に示します． 図 1. プログラム（左）とトレース（右） 図 1 左は 1 から 10 までの数の総和を計算するプログラムの機械語を表しています．5 行 目の命令「beq r2==r3, EXIT」から 8 行目の命令「b LOOP」がループになっており，これ ら 4 つの命令が 10 回ずつ実行されることによって，総和（レジスタ r1 の値）が計算され ます．このプログラムの命令を実行順に並べると右のようになります．右図では 4 行目か ら 7 行目がループの 1 周目に対応しており，8 行目からループの 2 周目が開始しています． これがトレースです． トレースは自分で作成することもできますが，代表的なトレースを共有ディレクトリに 用意してありますので，本実験ではこれらのトレースを使用してください．トレース作成を 試してみたい人は，ルートディレクトリにある README.md の ”How to create traces” と いう箇所を読んでください．
ChampSim には，キャッシュの代表的なエントリ置換アルゴリズムが既にいくつか実装 されています．具体的には，LRU (Least Recently Used), SRRIP (Static Re-Reference Interval Prediction), DRRIP (Dynamic Re-Reference Interval Prediction), SHIP (Signature-based Hit Predictor) の 4 つのアルゴリズムが利用可能です． 以下では，これらのアルゴリズムを使用した場合のキャッシュヒット率と CPU 性能を計 測してみます．ここでは各アルゴリズムの詳細を理解する必要はありません．各アルゴリズ ムの詳細を知りたい人は文献[1,3-4]を読んでください．計測手順を以下に示します． 1: set r1 = 0; 2: set r2 = 1; 3: set r3 = 11; 4: LOOP: 5: beq r2 == r3, EXIT; 6: add r1 = r1 + r2; 7: add r2 = r2 + 1; 8: b LOOP; 9: EXIT: 1: set r1 = 0; 2: set r2 = 1; 3: set r3 = 11; 4: beq r2 == r3, EXIT; 5: add r1 = r1 + r2; 6: add r2 = r2 + 1; 7: b LOOP; 8: beq r2 == r3, EXIT; …
4 (1) ChampSim のビルド
まずは各アルゴリズムに対応したシミュレータをビルドします．ルートディレク トリで以下のコマンドを実行してください．
./build_champsim.sh perceptron no no lru 1 ./build_champsim.sh perceptron no no srrip 1 ./build_champsim.sh perceptron no no drrip 1 ./build_champsim.sh perceptron no no ship 1
「build_champsim.sh」はシミュレータの実行バイナリを生成するスクリプトです． 同スクリプトの第 4 引数がキャッシュのエントリ置換アルゴリズムを表しています． ルートディレクトリの「bin/」の下に 4 つの実行バイナリが生成されていることを確 認してください． (2) 実行 (1)で作成したシミュレータを用いてキャッシュのシミュレーションを行います． ルートディレクトリで以下のコマンドを実行してください． ./myscript/run_all_models.sh 5 「top」コマンドを使って，4 つのシミュレータの実行が開始されたことを確認し てみてください．図 2 のように，(1)で生成した 4 つのバイナリファイルの名前が表 示されており，これらのプロセスの CPU 使用率（「%CPU」の項）が 100%に近い値 を示していれば，シミュレータは正常に動作していると思って構いません． 図 2. シミュレータの実行を top コマンドで確認しているようす
5 上記の 4 つのプロセスがすべて終了すれば（top コマンドを実行した時に上記のプ ロセス名の表示がなくなれば），シミュレーションは完了です．ルートディレクトリ 内の「result_100M」という名前のディレクトリに，シミュレーション結果のテキス トファイルが生成されていることを確認してください．テキストファイルは計 20 個 （＝シミュレータ数 (4) ×トレース数 (5)）生成されます． シミュレーションの完了までには 1 時間程度を見込んでください． (3) 実行結果の描画 最後に，シミュレーション結果をグラフにしてみましょう．ルートディレクトリで 以下のコマンドを実行してください． ./myscript/mk_sample_graphs.sh 上記コマンドにより，ルートディレクトリの「graphs/」に「ipc.pdf」「llc.pdf」と いう 2 つのファイルが作成されますので，これらを Acrobat Reader などで表示して みてください．4 つのエントリ置換アルゴリズムを 5 つのトレースに対してシミュレ ーションした結果が棒グラフで表示されているはずです．「ipc.pdf」は IPC を表した グラフです．IPC は 1 サイクルあたりに実行された命令数のことで，CPU 性能を表 す指標として用いられます．「llc.pdf」はラストレベルキャッシュ（一番メモリに近 い層のキャッシュ）のヒット率を表したグラフです． これで実験の準備は完了です． ４．３．エントリ置換アルゴリズムの考え方 次は，シミュレータに実装するエントリ置換アルゴリズムを考えてみましょう．開発する アルゴリズムは，有限のハードウェアで実現可能ならばどのようなアルゴリズムでも構い ません．自分なりの工夫を凝らして，高性能なアルゴリズムを開発してみてください． どのようにアルゴリズムを考えたらよいかわからない人は，まずは LRU の問題点を改良 することを目標にアルゴリズムを考えてみるとよいと思います．一般的によく知られてい る LRU の問題点はスキャンアクセスに弱いことです．スキャンアクセスとは以下のような メモリアクセスパターンのことを言います．ただし，下の例において，0x00 などの文字列 はメモリアドレスを表すものとし，各アドレスは左から右に向かって順にアクセスが行わ れるものとします． 0x00, 0x04, 0x08, 0x0C, 0x10, 0x14, …
6 このようなメモリアクセスパターンを有するプログラムを，4 エントリのキャッシュ（キ ャッシュブロックの大きさは 4B と仮定します）からなるプロセッサ上で実行する場合を考 えます．キャッシュのエントリを LRU で置換した場合，各メモリアクセス時のキャッシュ のヒット/ミスとエントリの状態は以下のようになります． 1 2 3 4 5 6 Address 0x00 0x04 0x08 0x0C 0x10 0x14 Hit/miss Miss Miss Miss Miss Miss Miss Entry 0 0x00 0x00 0x00 0x00 0x10 0x10 Entry 1 - 0x04 0x04 0x04 0x04 0x14 Entry 2 - - 0x08 0x08 0x08 0x08 Entry 3 - - - 0x0C 0x0C 0x0C このように，すべてのメモリアクセスでキャッシュミスが発生し，キャッシュのエントリ が古いものから順に置き換えられた結果，最終的にはすべてのエントリが置き換えられて しまいます．これは，次のような，キャッシュにヒットしやすいアクセスとスキャンアクセ スが混在するプログラムで問題となります． 0x20, 0x24, 0x20, 0x24, 0x00, 0x04, 0x08, 0x0C, 0x20, 0x24 … このプログラムに対してエントリを LRU で置換した場合，キャッシュの状態は以下のよ うに推移します． 1 2 3 4 5 6 7 8 9 10 Address 0x20 0x24 0x20 0x24 0x00 0x04 0x08 0x0C 0x20 0x24 Hit/miss Miss Miss Hit Hit Miss Miss Miss Miss Miss Miss Entry 0 0x20 0x20 0x20 0x20 0x20 0x20 0x08 0x08 0x08 0x08 Entry 1 - 0x24 0x24 0x24 0x24 0x24 0x24 0x0C 0x0C 0x0C Entry 2 - - - - 0x00 0x00 0x00 0x00 0x20 0x20 Entry 3 - - - 0x04 0x04 0x04 0x04 0x24 この例では，キャッシュにヒットしやすいアクセス（0x20 と 0x24 に対するアクセス）の 間にスキャンアクセス（5 番目から 8 番目までのアクセス）が入ったことによって，キャッ シュのエントリがすべて置き換えられてしまいます．その結果，本来はキャッシュにヒット しやすいはずのエントリ（0x20 と 0x24）が一旦キャッシュから追い出されてしまい，スキ
7 ャンアクセス後の 0x20 と 0x24 へのアクセス（9 番目と 10 番目のアクセス）に対してキャ ッシュミスが発生します． 上記の例では，スキャンアクセスに対してエントリ 0 と 1 を置換しなければ，9 番目と 10 番目のアクセスはキャッシュにヒットします．つまり，スキャンアクセスに対して置換 対象のエントリを制限できれば，キャッシュのヒット率は向上します．そのようなアルゴリ ズムを考えてみてください． ４．４．エントリ置換アルゴリズムの実装と動作確認 エントリ置換アルゴリズムを決めたら，シミュレータへの実装を行います． (1) コーディングの準備 ルートディレクトリにおいて以下のコマンドを実行してください． cp replacement/llc_replacement.cc replacement/myrep.llc_repl コピー元のファイルである「llc_replacement.cc」には，エントリ置換アルゴリズムの 関数のひな形が用意されています．このファイルをコピーして，自身のエントリ置換 アルゴリズムを実装していきます．コピー先のファイル名は，拡張子が「.llc_repl」 であれば何でも構いませんが，ここでは「myrep」とします． (2) コーディング 「myrep.llc_repl」にアルゴリズムを実装します．同ファイルをテキストエディタ で開いてください．ファイルの中には 4 つの関数（ChampSim は C++で記述されて いるため，正確には CACHE クラスの 4 つのメンバ関数ですが，この実験ではメン バ関数と通常の関数の違いを意識する必要はないため，以後は関数と呼びます）が存 在します．これらの関数の中に，実現したいアルゴリズムを記述していきます． 各関数の意味は以下の通りです． void CACHE::llc_initialize_replacement() 置換アルゴリズムで使用する状態（例えば各キャッシュブロックの優先度情報） を初期化する関数．シミュレーションの開始時に呼び出される．
uint32_t CACHE::llc_find_victim(uint32_t cpu, uint64_t instr_id, uint32_t set,
const BLOCK *current_set, uint64_t ip, uint64_t full_addr, uint32_t type) 置換対象のブロックを探す関数．キャッシュミス時に呼び出される．返り値は置 換対象のブロックのウェイ番号．各引数の意味は以下の通り．
8 変数名 説明 cpu コア番号．この実験では使用しない（1 コアの CPU のシミュレ ーションを行うので，常に 0 となる）． instr_id キャッシュミスした命令の ID（命令アドレス）． set 上記命令がアクセスしたセットの番号． current_set 上記命令がアクセスしたセットに格納されているキャッシュブ ロック． ip プリフェッチに使用．この実験では使用しない． full_addr アクセスしたブロックのアドレス． type アクセスのタイプ．アクセスのタイプに応じて値がセットされ るが，この実験に関係するのはライトバックのみ（WRITEBACK という列挙型の値がセットされる）．
void CACHE::llc_update_replacement_state(uint32_t cpu, uint32_t set, uint32_t
way, uint64_t full_addr, uint64_t ip, uint64_t victim_addr, uint32_t type, uint8_t hit) 置換アルゴリズムで使用する状態を更新する関数．キャッシュアクセスが行わ れる度に呼び出される．各引数の意味は以下の通り． 変数名 説明 cpu llc_find_victim() と同様． set llc_find_victim() と同様． way アクセスした way の番号． full_addr llc_find_victim() と同様． ip llc_find_victim() と同様． victim_addr 置換対象のブロックのアドレス． type llc_find_victim() と同様． hit キャッシュにヒットした場合は 1，ミスした場合は 0． void CACHE::llc_replacement_final_stats() 置換アルゴリズムで使用する状態の後処理をする関数．シミュレーションの終 了時に呼び出される． (3) ビルド ルートディレクトリで以下のコマンドを実行することにより，実装した置換アル ゴリズムに対応したシミュレータをビルドします．
9
./build_champsim.sh perceptron no no myrep 1
ビルドに失敗した場合は，エラーメッセージの内容を確認し，自分が作成したプログ ラムのデバッグ作業を行ってください． (4) 実行 4.2 章で実行したトレースに対して，実装した置換アルゴリズムのシミュレーショ ンを行います．以下のコマンドをルートディレクトリで実行してください． ./myscript/run_5apps.sh perceptron-no-no-myrep-1core 実行が完了すると，「result_100M」ディレクトリに実行結果（*-myrep-1core.txt と いう名前の 5 つのファイル）が生成されます． (5) 実行結果の描画 結果をグラフに描画します．以下のコマンドをルートディレクトリで実行してく ださい． ./myscript/mk_your_graphs.sh myrep 「graphs」ディレクトリに「your_ipc.pdf」と「your_llc.pdf」という名前の 2 つのフ ァイルが生成されます． ４．５．報告用データの取得 レポートには，必ず，次の 10 本のトレース（cactusADM_734B, calculix_2655B, lbm_94B, leslie3d_94B, libquantum_964B, mcf_46B, milc_360B, soplex_66B, sphinx3_883B, xalancbmk_99B）に対する評価結果を載せてください．開発したアルゴリズムの有用性は， この 10 本のトレースに対する評価結果から判断します． 10 本のトレースの実行には 2 時間程度必要です．各自，報告用データの取得に必要な時 間を考慮して実験を進めてください． 10 本のトレースに対するシミュレーションは，以下のコマンドにより実行できます． ./myscript/final_run.sh myrep
10 また，報告用データのグラフ化には以下のコマンドを使用してください． ./myscript/mk_final_graphs.sh myrep ルートディレクトリの「graphs/」に「final_ipc.pdf」「final_llc.pdf」というファイルが生 成されますので，この結果をレポートに掲載してください． ５．キャッシュの構造と動作 本章ではキャッシュについて簡単に説明します． ５．１．概要 キャッシュは，CPU 内に存在するハードウェアであり，メインメモリに対するアクセス を高速化するために用いられます．最近のハイエンド CPU ではメインメモリへのアクセス に数百クロックサイクル程度の時間が必要であり，実行中のプログラムがメインメモリへ のアクセスを開始すると，CPU 性能は大幅に低下してしまいます．そこで，CPU は，キャ ッシュと呼ばれる高速かつ小容量のメモリを内部に搭載し，メインメモリの代わりにキャ ッシュにアクセスすることによってメモリアクセス速度を改善しています．キャッシュに はメインメモリ上のデータの一部が保持されており，所望のデータがキャッシュに存在す れば，キャッシュのアクセス速度（1-3 クロックサイクル程度）で当該データにアクセスす ることが可能です．データがキャッシュに存在しない場合は下位のメモリから当該データ を取得しなければならず，メモリアクセス速度は改善されません． また，キャッシュは，多くの CPU において階層化されています（図 3）．つまり，異なる 速度と容量のキャッシュを演算装置とメインメモリの間に階層的に配置し，各階層のキャ ッシュに順にアクセスすることによってメモリアクセス速度を改善します．ちなみに，本実 験で使用するシミュレータは 3 階層のキャッシュを有しており，皆さんがエントリ置換ア ルゴリズムを実装するのはメインメモリに最も近い階層のキャッシュ（ラストレベルキャ ッシュ）です． キャッシュの容量は限られており，メインメモリ上のデータの一部しか保持することが できません．そのため，新しいデータをキャッシュに 1 つ配置するには，代わりのデータを キャッシュから 1 つ追い出す必要があります．これを決定するのが置換アルゴリズムです． 図 3. コンピュータのメモリ階層 演算装置 L1Dキャッシュ L2キャッシュ ラストレベルキャッシュ 数十 cycle 1～3 cycle 10～ cycle メインメモリ 100～ cycle
11 ５．２．基本的な構成と動作 キャッシュの構成を図 4 に示します．キャッシュは複数（数十から数十万）エントリから なる表であり，各エントリはタグ部とデータ部という 2 つのフィールドから構成されてい ます．キャッシュは，参照の空間的局所性を利用するため，メインメモリ上の連続するアド レスを持つデータ（図では 4B のデータ 4 つ）を 1 つのまとまりとして管理しています．こ れをキャッシュブロックと言います．キャッシュのデータ部はキャッシュブロックを格納 するためのフィールドです． 一方，タグ部はキャッシュブロックのアドレスを格納します．キャッシュブロックのアド レスは，キャッシュブロックの先頭のデータのアドレスからオフセット部分を除いたもの です．図の例はオフセットが 16 ですので，先頭のデータのアドレス「0x1000」から下位 4 ビットを除いた「0x100」がブロックアドレスとしてタグ部に格納されます． キャッシュに対するアクセスは次のように行われます．まず，参照するデータのブロック アドレスを計算します．次に，上記のブロックアドレスとキャッシュのタグ部を比較し，一 致するエントリを探します．一致するエントリが見つかった場合はキャッシュヒットです． キャッシュにヒットした場合は，同エントリのデータ部を読みだすことにより，該当するデ ータを参照することができます．一致するエントリが見つからない場合はキャッシュミス となり，下位のメモリへアクセスを行います． ５．３．セットアソシアティブ方式 前章で説明したキャッシュは，キャッシュミスを判定するために，参照するブロックアド レスを，キャッシュに格納された全ブロックアドレスと比較する必要がありました．前述の ように，容量の大きなキャッシュではエントリ数が数十万にも達するため，キャッシュアク セスの度に全エントリのタグ部との一致比較を行うと，この比較処理が性能上のボトルネ ックとなってしまいます． この問題を緩和するため，多くのキャッシュはセットアソシアティブ方式を採用してい ます．セットアソシアティブキャッシュの構成を図 5 に示します．セットアソシアティブ キャッシュでは各ブロックの配置場所がある程度決まっており，これをセットと呼びます． 図 4. キャッシュの構成 0x100 タグ部 データ部 0x100Cのデータ 0x1008のデータ 0x1004のデータ 0x1000のデータ キャッシュブロック
12 一方，セット内ではブロックを自由に配置することができ，この場所をウェイと呼びます． 図は 2 ウェイからなるセットアソシアティブキャッシュの構成例です．セットアソシアテ ィブキャッシュではブロックの格納位置がセットにより決まるため，キャッシュアクセス 時は対応するセットの各ウェイに対してのみ検索を行えばよく，図 4 のキャッシュと比べ てアクセスに必要な検索処理のコストを大幅に削減することができます． セットアソシアティブキャッシュでは，参照するアドレスを 3 つの部分に分割します． 下位部分がオフセットとして使用されるのは図 4 のキャッシュと同じです．オフセットに 続く数ビットがセットインデクスとなります．残りの部分はタグと呼ばれ，キャッシュのタ グ部との一致比較に使用されます． セットアソシアティブキャッシュへのアクセスは，具体的には次のような手順で行われ ます．まず，セットインデクス（図の例では 0）を用いて，キャッシュから該当するセット の全ウェイのタグ部（図の例では 0x10 と 0x26）を読み出します．続いて，タグとキャッシ ュから読み出したタグ部を比較します．一致するタグが存在した場合はキャッシュヒット です．該当するウェイに当該データが存在することがわかります．そこで，データ部からキ ャッシュブロックを読み出し（この処理はタグ部の読み出しと並列に行われることもあり ます），オフセットを用いて読み出したブロックから該当データを取り出します． ちなみに ChampSim のラストレベルキャッシュは 2,048 セット，16 ウェイのセットアソ シアティブキャッシュです． 図 5. セットアソシアティブキャッシュ 0x10 タグ部 データ部 0x100Cのデータ 0x1008のデータ 0x1004のデータ 0x1000のデータ 0x10 0 4 参照するアドレス ウェイ0 ウェイ1 セット0 セット1 0x31 0x3110のデータ 0x3114のデータ 0x3118のデータ 0x311Cのデータ セット1 セット0 オフセット セット インデクス タグ 0x26 0x79
＝
＝
0x260Cのデータ 0x2608のデータ 0x2604のデータ 0x2600のデータ 0x791Cのデータ 0x7918のデータ 0x7914のデータ 0x7910のデータ 0x100Cのデータ 0x1008のデータ 0x1004のデータ 0x1000のデータ 0x1004のデータ13 ５．４．LRU アルゴリズム
多くの CPU のキャッシュでは，置換アルゴリズムとして LRU が採用されています．LRU は最も過去に参照されたエントリを置換対象とするアルゴリズムです． 具体的なアルゴリズムを 4.3 章の例（以下に再掲します）を用いて説明します． 0x20, 0x24, 0x20, 0x24, 0x00, 0x04, 0x08, 0x0C, 0x20, 0x24 … 今，CPU のキャッシュは 2 エントリのみとし，LRU によってエントリを置換するものと します．また，ブロックサイズは 4B と仮定します． さて，5 番目のメモリアクセス（0x00 へのアクセス）が行われた時のキャッシュの状態 を考えます．この時，キャッシュには，0x20 のブロックと 0x24 のブロックが格納されてい ます．一方，アクセスされたブロックは 0x00 なので，0x00 のブロックを格納するために は，上記 2 つのブロックのどちらか一方をキャッシュから追い出さなくてはなりません． ここで，0x20 のブロックと 0x24 のブロックでは，0x20 のブロックの方が過去に参照さ れています（0x24 に対する最後のアクセスは 4 番目のアクセスなのに対し，0x20 に対する 最後のアクセスは 3 番目のアクセス）．そこで，0x20 のブロックを置換対象とするのが LRU 方式です． ６．実験が思うように進まない学生に向けて
実験が進まない学生は，まずは練習として，LFU (Least Frequently Used) アルゴリズム を ChampSim に実装してみるとよいでしょう．LFU は，最も参照回数の少ないエントリを 置換対象とするアルゴリズムです．サンプル置換アルゴリズム（LRU, DRRIP, SRRIP, SHIP） と LFU の比較評価結果がレポートに記載されていれば，成績は少なくとも不可にはなりま せん．本書の末尾に LFU の実装例を示します． 参考文献 [1] パターソン＆ヘネシー，「コンピュータの構成と設計—ハードウェアとソフトウェアの インターフェース— 第 5 版下巻」，日経 BP 社，2014． [2] ChampSim, https://github.com/ChampSim/ChampSim
[3] Aamer Jaleel, Kevin B. Theobald, Simon C. Steely, Jr., Joel Emer, “High Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP),” in Proceedings of the 37th Annual International Symposium on Computer Architecture, pp. 60–71, 2010 [4] Carole-Jean Wu, Aamer Jaleel, Will Hasenplaugh, Margaret Martonosi, Simon C. Steely,
Joel Emer, “SHiP: Signature-based Hit Predictor for High Performance Caching,” in Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 430–441, 2011
14
図 6. LFU の実装例 #include "cache.h"
uint32_t refCount[LLC_SET][LLC_WAY]; // initialize replacement state
void CACHE::llc_initialize_replacement() {
for (int i = 0 ; i < LLC_SET ; ++i) for (int j = 0 ; j < LLC_WAY ; ++j) refCount[i][j] = 0; }
// find replacement victim
uint32_t CACHE::llc_find_victim(uint32_t cpu, uint64_t instr_id, uint32_t set, const BLOCK *current_set, uint64_t ip, uint64_t full_addr, uint32_t type)
{
uint32_t minCount = UINT_MAX; int v = 0;
for (int j = 0 ; j < LLC_WAY ; ++j) { if (refCount[set][j] < minCount) { minCount = refCount[set][j]; v = j; } } return v; }
// called on every cache hit and cache fill
void CACHE::llc_update_replacement_state(uint32_t cpu, uint32_t set, uint32_t way, uint64_t full_addr, uint64_t ip, uint64_t victim_addr, uint32_t type, uint8_t hit)
{
string TYPE_NAME; if (type == LOAD)
TYPE_NAME = "LOAD"; else if (type == RFO) TYPE_NAME = "RFO"; else if (type == PREFETCH) TYPE_NAME = "PF"; else if (type == WRITEBACK) TYPE_NAME = "WB"; else assert(0); if (hit) TYPE_NAME += "_HIT"; else TYPE_NAME += "_MISS"; if ((type == WRITEBACK) && ip) assert(0);
if (hit && (type == WRITEBACK)) // writeback hit does not update refCount return;
if (hit && (refCount[set][way] < UINT_MAX - 1)) refCount[set][way]++; else if (!hit) refCount[set][way] = 1; return; } void CACHE::llc_replacement_final_stats() { }
15 よくある質問 Q. シミュレーション時間を短くするにはどうすればいいの？ A. ルートディレクトリの「myscript」以下にある実行スクリプトは，複数のトレースや置 換アルゴリズムに対してシミュレーションを行うため，すべてのシミュレーションが 完了するまでには 1-2 時間程度必要です．一方，開発した置換アルゴリズムのテスト実 行を行うだけならば，すべてのトレースに対するシミュレーションは必要ありません ので，1 トレースに対するシミュレーション（10 分程度で終了します）を行ってくだ さい．1 トレースに対するシミュレーションは以下のコマンドにより実行可能です． ./myscript/run_champsim.sh 実行バイナリ名 1 100 トレース名 「実行バイナリ名」はシミュレータの実行バイナリ名（ 「perceptron-no-no-myrep-1core」など）を指定します．実行バイナリは，ルートディレクトリで「ls bin/」を行 うと確認できます．「トレース名」は「cactusADM_734B」「mcf_46B」「soplex_66B」 「sphinx3_883B」「xalancbmk_99B」などが選択できますが，テスト実行には，置換 アルゴリズムによる CPU 性能差が大きい「sphinx3_883B」がお薦めです．
