４実験方法本章では具体的な実験方法を説明します本章をよく読んで作業を進めてください 4.3 章以降はキャッシュの構造や動作について既に十分に理解していることが前提となっていますキャッシュの理解に自信がない学生は 4.3 章に進む前にまずはキャッシュの構造と動作を理解した方がよいでしょう

Size: px

Start display at page:

Download "４実験方法本章では具体的な実験方法を説明します本章をよく読んで作業を進めてください 4.3 章以降はキャッシュの構造や動作について既に十分に理解していることが前提となっていますキャッシュの理解に自信がない学生は 4.3 章に進む前にまずはキャッシュの構造と動作を理解した方がよいでしょう"

こうたかなり
5 years ago
Views:

1 情報数理工学/コンピュータサイエンス実験第二 A/B キャッシュシミュレーション担当三輪忍本書は電気通信大学 I 類授業科目情報数理工学実験第二 A/B およびコンピュータサイエンス実験第二 A/B における課題名キャッシュシミュレーションの手引書です本課題を履修する学生は本書をよく読んだ上で授業に臨んでください１本実験の目的本実験の目的は多くの CPU に搭載されており性能への影響が大きなハードウェアであるキャッシュについてシミュレーションとエントリ置換アルゴリズムの開発を通してその理解を深めることにありますエントリ置換アルゴリズムの開発を通してコンピュータアーキテクチャ研究の面白さを知ってください２評価基準本実験の成績はラウンド終了後に提出するレポートの内容により評価します評価は開発したアルゴリズムの独自性と有用性およびレポートの読みやすさの 3 つの観点から行います独自性に関しては単にどこかの文献に記載されているアルゴリズムを実装した場合よりも各自が工夫して編み出したアルゴリズムを実装した場合の方が評点は高くなりますまた有用性に関しては開発アルゴリズムのシミュレーション結果がよい程具体的には IPC (Instruction Per Cycle) とキャッシュヒット率が高い程評点は高くなります皆さん有用でオリジナリティに溢れるアルゴリズムを頑張って開発してください３実験スケジュール本実験は明確な中間目標を設けていません全 7 回の授業時間を自由に使って実験を進めてください実験終了までの時間配分の一例を以下に挙げますので参考にしてください授業日内容第1回実験概要とキャッシュの理解および実験環境のセットアップ第2回実装するアルゴリズムの検討第3回第4回第5回第6回第7回アルゴリズムの実装とデバッグ作業実装したアルゴリズムの初期評価と改良作業最終評価報告用データの取得とレポートの執筆 1

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 上記の操作により git clone を実行したディレクトリの下に ChampSim という名前のディレクトリが生成されます以後後者のディレクトリをルートディレクトリと呼びます (2) 実行/解析用スクリプトのコピー次に実験に使用する実行用/解析用プログラムを取得しますルートディレクトリに移動し以下のコマンドを実行してください cp r /home3/staff/ma002344/.ced_centos/mics2/champsim/myscript. myscript というディレクトリが生成されます.sh や.py などの拡張子を持ついくつかのファイルが myscript の中に存在することを確認してください 2

3 ４２ ChampSim と実行/解析用スクリプトの動作確認続いて ChampSim と実行/解析用スクリプトの動作確認を行います ChampSim は命令の実行トレース以後トレースと呼びますを入力として与えることによりキャッシュなどの CPU 内ハードウェアの挙動をシミュレートしますトレースとはプログラムを実行した際の命令の実行系列のことですトレースの例を図 1 に示します 1: set r1 = 0; 1: set r1 = 0; 2: set r2 = 1; 2: set r2 = 1; 3: set r3 = 11; 3: set r3 = 11; 4: LOOP: 4: beq r2 == r3, EXIT; 5: beq r2 == r3, EXIT; 5: add r1 = r1 + r2; 6: add r1 = r1 + r2; 6: add r2 = r2 + 1; 7: add r2 = r2 + 1; 7: b LOOP; 8: b LOOP; 8: beq r2 == r3, EXIT; 9: EXIT: 図 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 ReReference Interval Prediction), DRRIP (Dynamic ReReference Interval Prediction), SHIP (Signaturebased Hit Predictor) の 4 つのアルゴリズムが利用可能です以下ではこれらのアルゴリズムを使用した場合のキャッシュヒット率と CPU 性能を計測してみますここでは各アルゴリズムの詳細を理解する必要はありません各アルゴリズムの詳細を知りたい人は文献[1,34]を読んでください計測手順を以下に示します 3

(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.

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 コマンドで確認しているようす 4

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 の問題点はスキャンアクセスに弱いことですスキャンアクセスとは以下のようなメモリアクセスパターンのことを言いますただし下の例においてなどの文字列はメモリアドレスを表すものとし各アドレスは左から右に向かって順にアクセスが行われるものとします,,,, 0x10, 0x14, 5

6 このようなメモリアクセスパターンを有するプログラムを 4 エントリのキャッシュキャッシュブロックの大きさは 4B と仮定しますからなるプロセッサ上で実行する場合を考えますキャッシュのエントリを LRU で置換した場合各メモリアクセス時のキャッシュのヒット/ミスとエントリの状態は以下のようになります Address 0x10 0x14 Hit/miss Entry 0 0x10 0x10 Entry 1 0x14 Entry 2 Entry 3 このようにすべてのメモリアクセスでキャッシュミスが発生しキャッシュのエントリが古いものから順に置き換えられた結果最終的にはすべてのエントリが置き換えられてしまいますこれは次のようなキャッシュにヒットしやすいアクセスとスキャンアクセスが混在するプログラムで問題となります,,,,,,,,, このプログラムに対してエントリを LRU で置換した場合キャッシュの状態は以下のように推移します Address Hit/miss Hit Hit Entry 0 Entry 1 Entry 2 Entry 3 この例ではキャッシュにヒットしやすいアクセスとに対するアクセスの間にスキャンアクセス 5 番目から 8 番目までのアクセスが入ったことによってキャッシュのエントリがすべて置き換えられてしまいますその結果本来はキャッシュにヒットしやすいはずのエントリとが一旦キャッシュから追い出されてしまいスキ 6

7 ャンアクセス後のとへのアクセス 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) 置換対象のブロックを探す関数キャッシュミス時に呼び出される返り値は置換対象のブロックのウェイ番号各引数の意味は以下の通り 7

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) ビルドルートディレクトリで以下のコマンドを実行することにより, 実装した置換アルゴリズムに対応したシミュレータをビルドします. 8

9 ./build_champsim.sh perceptron no no myrep 1 ビルドに失敗した場合はエラーメッセージの内容を確認し自分が作成したプログラムのデバッグ作業を行ってください (4) 実行 4.2 章で実行したトレースに対して実装した置換アルゴリズムのシミュレーションを行います以下のコマンドをルートディレクトリで実行してください./myscript/run_5apps.sh perceptronnonomyrep1core 実行が完了すると result_100m ディレクトリに実行結果 *myrep1core.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 9

10 また報告用データのグラフ化には以下のコマンドを使用してください./myscript/mk_final_graphs.sh myrep ルートディレクトリの graphs/ に final_ipc.pdf final_llc.pdf というファイルが生成されますのでこの結果をレポートに掲載してください５キャッシュの構造と動作本章ではキャッシュについて簡単に説明します５１概要キャッシュは CPU 内に存在するハードウェアでありメインメモリに対するアクセスを高速化するために用いられます最近のハイエンド CPU ではメインメモリへのアクセスに数百クロックサイクル程度の時間が必要であり実行中のプログラムがメインメモリへのアクセスを開始すると CPU 性能は大幅に低下してしまいますそこで CPU はキャッシュと呼ばれる高速かつ小容量のメモリを内部に搭載しメインメモリの代わりにキャッシュにアクセスすることによってメモリアクセス速度を改善していますキャッシュにはメインメモリ上のデータの一部が保持されており所望のデータがキャッシュに存在すればキャッシュのアクセス速度 13 クロックサイクル程度で当該データにアクセスすることが可能ですデータがキャッシュに存在しない場合は下位のメモリから当該データを取得しなければならずメモリアクセス速度は改善されません 1 3 cycle 演算装置 10 cycle L1Dキャッシュ数十 cycle L2キャッシュ 100 cycle ラストレベルキャッシュメインメモリ図 3. コンピュータのメモリ階層またキャッシュは多くの CPU において階層化されています図 3 つまり異なる速度と容量のキャッシュを演算装置とメインメモリの間に階層的に配置し各階層のキャッシュに順にアクセスすることによってメモリアクセス速度を改善しますちなみに本実験で使用するシミュレータは 3 階層のキャッシュを有しており皆さんがエントリ置換アルゴリズムを実装するのはメインメモリに最も近い階層のキャッシュラストレベルキャッシュですキャッシュの容量は限られておりメインメモリ上のデータの一部しか保持することができませんそのため新しいデータをキャッシュに 1 つ配置するには代わりのデータをキャッシュから 1 つ追い出す必要がありますこれを決定するのが置換アルゴリズムです 10

11 ５２基本的な構成と動作キャッシュの構成を図 4 に示しますキャッシュは複数数十から数十万エントリからなる表であり各エントリはタグ部とデータ部という 2 つのフィールドから構成されていますキャッシュは参照の空間的局所性を利用するためメインメモリ上の連続するアドレスを持つデータ図では 4B のデータ 4 つを 1 つのまとまりとして管理していますこれをキャッシュブロックと言いますキャッシュのデータ部はキャッシュブロックを格納するためのフィールドですデータ部タグ部キャッシュブロック 0x100 0x1000のデータ 0x1004のデータ 0x1008のデータ 0x100Cのデータ図 4. キャッシュの構成一方タグ部はキャッシュブロックのアドレスを格納しますキャッシュブロックのアドレスはキャッシュブロックの先頭のデータのアドレスからオフセット部分を除いたものです図の例はオフセットが 16 ですので先頭のデータのアドレス 0x1000 から下位 4 ビットを除いた 0x100 がブロックアドレスとしてタグ部に格納されますキャッシュに対するアクセスは次のように行われますまず参照するデータのブロックアドレスを計算します次に上記のブロックアドレスとキャッシュのタグ部を比較し一致するエントリを探します一致するエントリが見つかった場合はキャッシュヒットですキャッシュにヒットした場合は同エントリのデータ部を読みだすことにより該当するデータを参照することができます一致するエントリが見つからない場合はキャッシュミスとなり下位のメモリへアクセスを行います５３セットアソシアティブ方式前章で説明したキャッシュはキャッシュミスを判定するために参照するブロックアドレスをキャッシュに格納された全ブロックアドレスと比較する必要がありました前述のように容量の大きなキャッシュではエントリ数が数十万にも達するためキャッシュアクセスの度に全エントリのタグ部との一致比較を行うとこの比較処理が性能上のボトルネックとなってしまいますこの問題を緩和するため多くのキャッシュはセットアソシアティブ方式を採用していますセットアソシアティブキャッシュの構成を図 5 に示しますセットアソシアティブキャッシュでは各ブロックの配置場所がある程度決まっておりこれをセットと呼びます 11

12 一方セット内ではブロックを自由に配置することができこの場所をウェイと呼びます図は 2 ウェイからなるセットアソシアティブキャッシュの構成例ですセットアソシアティブキャッシュではブロックの格納位置がセットにより決まるためキャッシュアクセス時は対応するセットの各ウェイに対してのみ検索を行えばよく図 4 のキャッシュと比べてアクセスに必要な検索処理のコストを大幅に削減することができます参照するアドレス 0x データ部タグ部セット0 0x10 0x1000のデータ 0x1004のデータ 0x1008のデータ 0x100Cのデータセット1 0x31 0x3110のデータ 0x3114のデータ 0x3118のデータ 0x311Cのデータセットインデクスセット0 0x26 0x2600のデータ 0x2604のデータ 0x2608のデータ 0x260Cのデータセット1 0x79 0x7910のデータ 0x7914のデータ 0x7918のデータ 0x791Cのデータ 0x1000のデータ 0x1004のデータ 0x1008のデータ 0x100Cのデータウェイ0 タグウェイ1 オフセット 0x1004のデータ図 5. セットアソシアティブキャッシュセットアソシアティブキャッシュでは参照するアドレスを 3 つの部分に分割します下位部分がオフセットとして使用されるのは図 4 のキャッシュと同じですオフセットに続く数ビットがセットインデクスとなります残りの部分はタグと呼ばれキャッシュのタグ部との一致比較に使用されますセットアソシアティブキャッシュへのアクセスは具体的には次のような手順で行われますまずセットインデクス図の例では 0 を用いてキャッシュから該当するセットの全ウェイのタグ部図の例では 0x10 と 0x26 を読み出します続いてタグとキャッシュから読み出したタグ部を比較します一致するタグが存在した場合はキャッシュヒットです該当するウェイに当該データが存在することがわかりますそこでデータ部からキャッシュブロックを読み出しこの処理はタグ部の読み出しと並列に行われることもありますオフセットを用いて読み出したブロックから該当データを取り出しますちなみに ChampSim のラストレベルキャッシュは 2,048 セット 16 ウェイのセットアソシアティブキャッシュです 12

13 ５４ LRU アルゴリズム多くの CPU のキャッシュでは置換アルゴリズムとして LRU が採用されています LRU は最も過去に参照されたエントリを置換対象とするアルゴリズムです具体的なアルゴリズムを 4.3 章の例以下に再掲しますを用いて説明します,,,,,,,,, 今 CPU のキャッシュは 2 エントリのみとし LRU によってエントリを置換するものとしますまたブロックサイズは 4B と仮定しますさて 5 番目のメモリアクセスへのアクセスが行われた時のキャッシュの状態を考えますこの時キャッシュにはのブロックとのブロックが格納されています一方アクセスされたブロックはなのでのブロックを格納するためには上記 2 つのブロックのどちらか一方をキャッシュから追い出さなくてはなりませんここでのブロックとのブロックではのブロックの方が過去に参照されていますに対する最後のアクセスは 4 番目のアクセスなのに対しに対する最後のアクセスは 3 番目のアクセスそこでのブロックを置換対象とするのが LRU 方式です６実験が思うように進まない学生に向けて実験が進まない学生はまずは練習として LFU (Least Frequently Used) アルゴリズムを ChampSim に実装してみるとよいでしょう LFU は最も参照回数の少ないエントリを置換対象とするアルゴリズムですサンプル置換アルゴリズム LRU, DRRIP, SRRIP, SHIP と LFU の比較評価結果がレポートに記載されていれば成績は少なくとも不可にはなりません本書の末尾に LFU の実装例を示します参考文献 [1] パターソンヘネシーコンピュータの構成と設計ハードウェアとソフトウェアのインターフェース第 5 版下巻日経 BP 社 2014 [2] ChampSim, [3] Aamer Jaleel, Kevin B. Theobald, Simon C. Steely, Jr., Joel Emer, High Performance Cache Replacement Using ReReference Interval Prediction (RRIP), in Proceedings of the 37th Annual International Symposium on Computer Architecture, pp , 2010 [4] CaroleJean Wu, Aamer Jaleel, Will Hasenplaugh, Margaret Martonosi, Simon C. Steely, Joel Emer, SHiP: Signaturebased Hit Predictor for High Performance Caching, in Proceedings of the 44th Annual IEEE/ACM Microarchitecture, pp , International Symposium on

14 #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() { } 図 6. LFU の実装例 14

15 よくある質問 Q. シミュレーション時間を短くするにはどうすればいいの A. ルートディレクトリの myscript 以下にある実行スクリプトは複数のトレースや置換アルゴリズムに対してシミュレーションを行うためすべてのシミュレーションが完了するまでには 12 時間程度必要です一方開発した置換アルゴリズムのテスト実行を行うだけならばすべてのトレースに対するシミュレーションは必要ありませんので 1 トレースに対するシミュレーション 10 分程度で終了しますを行ってください 1 トレースに対するシミュレーションは以下のコマンドにより実行可能です./myscript/run_champsim.sh 実行バイナリ名トレース名実行バイナリ名はシミュレータの実行バイナリ名 perceptronnonomyrep1core などを指定します実行バイナリはルートディレクトリで ls bin/ を行うと確認できますトレース名は cactusadm_734b mcf_46b soplex_66b sphinx3_883b xalancbmk_99b などが選択できますがテスト実行には置換アルゴリズムによる CPU 性能差が大きい sphinx3_883b がお薦めです 15

スライド 1

スライド 1 知能制御システム学画像処理の高速化 OpenCV による基礎的な例東北大学大学院情報科学研究科鏡慎吾 swk(at)ic.is.tohoku.ac.jp 2007.07.03 リアルタイム処理と高速化リアルタイム = 高速ではない目標となる時間制約が定められているのがリアルタイム処理である.34 ms かかった処理が 33 ms に縮んだだけでも, それによって与えられた時間制約が満たされるのであれば,