キャッシュ・ミス頻発命令を考慮 したメモリ・システムの高性能化 三輪英樹 九州大学 大学院システム情報科学府 情報理学専攻 堂後靖博 福岡大学 大学院工学研究科 電子情報工学専攻 Victor Mauro Goulart Ferreira 九州大学 大学院システム情報科学府 情報理学専攻 井上弘士，村上和彰 九州大学 大学院システム情報科学研究院 情報理学部門 2004/12/2 デザインガイア ARC 研究会 1 発表手順 • 研究背景 • ロード対象データの再計算による 実行サイクル削減手法 • 本手法により性能向上を得るための条件 • 予備評価実験および考察 • まとめ 2004/12/2 デザインガイア ARC 研究会 2 研究背景 • キャッシュ・ミス頻発ロード命令 – Delinquent ロード命令「DL 命令」 • DL 命令に着目したキャッシュ・プリフェッチ – ロード対象アドレスを，別スレッドにて計算． – 既存研究: DDMT (Sohi@Wisconsin), Pre-Computation (J.P.Shen@Intel) – 主記憶へ先見的にアクセスし，レイテンシを隠 蔽． • DL 命令に着目したレイテンシ削減手法 – 本発表にて提案． 2004/12/2 デザインガイア ARC 研究会 3 提案手法 • データを主記憶からロードするのではなく 再計算 (Re-Computation; RC)． – DL 命令を再計算 (RC) コードで置換し， 実行サイクル数を削減する． 2004/12/2 デザインガイア ARC 研究会 4 DL 命令対象データの再計算 (RC) による 実行サイクル数削減手法 プログラムコード 本手法適用コード (静的/動的に生成) c = a + b; z = x + c; 2004/12/2 値cはキャッシュ メモリになく， 主記憶から読み 込まれると仮定 c = a + b; (Re-Computation) ... ... 値cは主記憶に 保存される RC コード 値cを再計算! ロード時の 主記憶への アクセスが 削減できる! c = a + b; z = x + c; 値 a,b は キャッシュメモリに 存在すると仮定 5 RC コードの例 プログラムコード アセンブリコード c = a + b; Load a Load b Add c, a, b Store c 値cを 再利用 2004/12/2 Load c Load x Add z, x, c Store z RC コード Load a Load b Add c, a,b ‘Load c’ をRCコード で置換! デザインガイア ARC 研究会 Load a Load b Add c, a, b Store c ... ... ... z = x + c; 本手法適用コード [RCコード] Load x Add z, x, c Store z 6 RC コードの生成方法 ソースコード … 00409588 l.d 00409590 l.d 004095a0 neg.d 004095a0 mul.d 004095a8 l.d 004095b0 mul.d CDFG $f2 $f0 $f2,$f2 $f2,$f2,$f0 $f0 $f2,$f2,$f0 $f2,10b34594 00402280 l.d … 10b34594 CDFG 生成 同一 アドレス Load Load Store DL命令 DL 命令 2004/12/2 Load … 004095e0 s.d … Load デザインガイア ARC 研究会 7 本手法により 性能向上を得るためには? 1. DL 命令によるキャッシュ・ミスの絶対回数が 多いこと． 2. 多数の DL 命令が RC コードで置換可能で あること. 3. 少なくとも RC コードの実行サイクル数が， 主記憶へのアクセスサイクル数よりも小さく なること． – RC コードのクリティカルパスが短いこと． – RC コードに含まれるロード命令は，すべて キャッシュ・ヒットすること． 2004/12/2 デザインガイア ARC 研究会 8 45.3% 60% 24.3% 7.9% 2.6% bzip2 vortex parser gcc mcf 4.3% gzip vpr_p vpr_r -1.5% 5.2% 13.0% 1.8% mesa art ammp 1.7% 20% 9 デザインガイア ARC 研究会 2004/12/2 ベンチマーク 26.2% -20% equake 0% 23.7% 40% 本手法適用時 実行サイクル数削減率 [%] 本手法適用時の 実行サイクル数削減率 予備評価実験 • 予備評価実験の主旨 – ベンチマークプログラムを利用し， 本手法を定量的に評価する． – 本手法の実現方法に関係なく， 本手法による最大性能向上を評価する． 2004/12/2 デザインガイア ARC 研究会 10 評価環境 • シミュレータ: SimpleScalar 3.0d • ベンチマーク: SPEC CPU 2000 – 入力データ: Reference • ベンチマークのコマンドラインは，DL 命令による キャッシュ・ミス回数が多い設定を利用． – バイナリ • MIRV Compiler (ミシガン大学) を利用してコンパイ ル． • mesa, art, equake, ammp • gzip, vpr, gcc, mcf, parser, vortex, bzip2 – 20億命令実行後の2億命令が評価対象 2004/12/2 デザインガイア ARC 研究会 11 主なシミュレータの設定 • 命令発行: アウト・オブ・オーダ • キャッシュ・メモリ容量 – L1D: 32KB (64B/エントリ, 2 ウェイ) – L1I: 32KB (64B/エントリ, 1 ウェイ) – L2: 2MB (64B/エントリ, 4 ウェイ) • アクセスレイテンシ – L1: 1 サイクル – L2: 16 サイクル – 主記憶: 250 サイクル 2004/12/2 デザインガイア ARC 研究会 12 本手法により 性能向上を得るためには? 1. DL 命令によるキャッシュ・ミスの絶対回数 が多いこと． 2. 多数の DL 命令が RC コードで置換可能で あること. 3. 少なくとも RC コードの実行サイクル数が， 主記憶へのアクセスサイクル数よりも小さく なること． 2004/12/2 デザインガイア ARC 研究会 13 全DL命令のキャッシュ・ヒット時 100% 80% 60% 40% 20% bzip2 vortex parser mcf gcc vpr_r vpr_p gzip ammp equake art 2004/12/2 0% mesa 実行サイクル数削減率 [%] DL 命令が全てキャッシュ・ヒットした 場合の実行サイクル数削減率 ベンチマーク デザインガイア ARC 研究会 14 本手法により 性能向上を得るためには? 1. DL 命令によるキャッシュ・ミスの絶対回数 が多いこと． 2. 多数の DL 命令が RC コードで置換可能 であること. 3. 少なくとも RC コードの実行サイクル数が， 主記憶へのアクセスサイクル数よりも小さく なること． 2004/12/2 デザインガイア ARC 研究会 15 RCコードで置換できたDL命令の割合 RCコードで置換できたDL命令の割合 RCコードで置換できた DL命令の割合 [%] 100% 80% 60% 40% 20% 0% bzip2 vortex parser デザインガイア ARC 研究会 mcf gcc vpr_r vpr_p gzip ammp equake art mesa 2004/12/2 ベンチマーク 16 本手法により 性能向上を得るためには? 1. DL 命令によるキャッシュ・ミスの絶対回数 が多いこと． 2. 多数の DL 命令が RC コードで置換可能で あること. 3. 少なくとも RC コードの実行サイクル数が， 主記憶へのアクセスサイクル数よりも小さく なること． 2004/12/2 デザインガイア ARC 研究会 17 RCコード平均実行サイクル数 RCコード平均実行サイクル数 [クロックサイクル] 200 RCコード平均実行サイクル数 150 100 0 bzip2 vortex デザインガイア ARC 研究会 parser ベンチマーク mcf gcc vpr_r vpr_p gzip ammp equake art mesa 2004/12/2 50 18 80% 2.6% 7.9% 24.3% 4.3% -1.5% -20% 5.2% 13.0% 26.2% 1.8% 0% bzip2 vortex parser mcf gcc vpr_r vpr_p gzip ammp ベンチマーク equake art mesa 19 デザインガイア ARC 研究会 2004/12/2 1.7% 20% 23.7% 40% 本手法適用時 全DL命令のキャッシュ・ヒット時 100% 45.3% 60% 実行サイクル数削減率 [%] 実行サイクル数削減率 考察 • 効果があまり出ないベンチマーク – DL 命令によるキャッシュ・ミスの絶対回数が少な いベンチマーク: mesa,vpr_p,gcc,vortex – RC コード置換可能 DL 命令数が少ないベンチ マーク: art, vpr_r – RC コードサイズが比較的大きいベンチマーク: ammp • 効果が出るベンチマーク – 上記のどれにも該当しない: mcf 2004/12/2 デザインガイア ARC 研究会 20 まとめ (1/2) • メモリ・ウォール問題への対策として，再計算 に基づくメモリ・システム高性能化手法を提案 した． • 予備評価結果より，実行サイクル数を削減す ることができる可能性があることを示した． 2004/12/2 デザインガイア ARC 研究会 21 まとめ (2/2) • 以下の点を中心に研究を進める必要がある． – RC コード生成方法の確立． – RC コード内のロード命令のキャッシュ・ヒット 状況の調査． – RC の適用によるキャッシュ・ヒット状況の変化の 調査． 2004/12/2 デザインガイア ARC 研究会 22 終了 ご静聴ありがとうございました 2004/12/2 デザインガイア ARC 研究会 23 評価における仮定 • DL 命令は，L2 キャッシュ・ミスを頻発させる 上位 16 個 (命令アドレス) のロード命令とする． • RC コード生成時に必要なコントールフローはトレー スデータから 1 パスを抽出する． • RC コード中のロード命令は，全て L1 ヒット． • RC コードを生成できた場合でも，命令数が主記憶 へのアクセスサイクル数より多ければ，RC コードは 生成できなかったとする． • キャッシュのヒット状況の変化は考慮しない． 2004/12/2 デザインガイア ARC 研究会 24 本評価における RC コード 実行サイクル数の評価方法 全 RC コード 1. RCコードをグループに分類 グループA 代表RCコードA 実行サイクル数A グループB 代表RCコードB 実行サイクル数B … … … 2. 各グループごとに 代表コードを生成 2004/12/2 3. 実行サイクル数を求め， 各グループの代表値とする デザインガイア ARC 研究会 25 本評価におけるRCコードの生成方法 • RC コードを生成するためには，コントロール フローおよびデータフローが必要． • コントロールフロー – トレースデータを利用し 1 つのパスのみを抽出． • データフロー – アセンブリコードにおいてレジスタの依存関係を 追跡することで抽出． 2004/12/2 デザインガイア ARC 研究会 26 top8 100% top16 top32 top64 80% 60% 40% 20% 0% bzip2 vortex parser mcf gcc vpr gzip equake art mesa Percentages of matched DL instructions [%] 異なる入力を使用した場合のDL命令 の一致状況 (smallinput v.s. train) Benchmark programs 2004/12/2 デザインガイア ARC 研究会 27 top8 100% top16 top32 top64 80% 60% 40% 20% 0% bzip2 vortex parser mcf gcc vpr gzip equake art mesa Percentages of matched DL instructions [%] 異なる入力を使用した場合のDL命令 の一致状況 (smallinput v.s. ref) Benchmark programs 2004/12/2 デザインガイア ARC 研究会 28 実行サイクル数削減率 • 実行サイクル数削減率 (Corg - Cccc ) / Corg ×100[%] – Cccc : 本手法適用後実行サイクル数 – Corg : 本手法適用前実行サイクル数 2004/12/2 デザインガイア ARC 研究会 29 本手法適用後実行サイクル数 • Cccc = Cideal + Crc + Cnorc – Cccc : 本手法適用後実行サイクル数 – Cideal : DL 命令による L2 ミス・ぺナルティを 0 と した場合 – Crc : RC コードの実行サイクル数 – Cnorc : RC コードで置換できなかった DL 命令の 実行サイクル数 2004/12/2 デザインガイア ARC 研究会 30 RC コードの総実行サイクル数 • Crc = CPI ·∑idldpc∑krccg Irccg(i,k) · Nrccg(i,k) – CPI : Clock cycles per instruction – Irccg(i,k) : ある DL 命令のインスタンス i に対する RC コードのうち，ストア命令(のアドレス) k に対 応する RC コード命令数 – Nrccg(i,k) : ある DL 命令のインスタンス i のうち， RC コードを生成することができた回数 2004/12/2 デザインガイア ARC 研究会 31 DL 命令の総実行サイクル数 • Cnorc = (Corg - Cideal ) / Ndl2miss · Nnorc – Corg : 本手法適用前の実行サイクル数 – Ndl2miss : DL 命令による DL2 ミス回数の総数 – Nnorc : RC コードが生成できない (サイズオーバ を含む) 判断された DL 命令数 2004/12/2 デザインガイア ARC 研究会 32 シミュレータの設定 (1/2) • 命令発行: アウトオーダ • メモリ – L1D: 32KB (64B/e,2w) • 分岐予測: gshare, 2K – L1I: 32KB (64B/e,1w) • 命令デコード幅，命令 – L2: 2MB (64B/e, 4w) 発行幅:8命令/サイクル • ヒットレイテンシ • IFQ: 8エントリ – L1: 1 サイクル • LSQ: 32エントリ – L2: 16 サイクル • RUU: 64エントリ – 主記憶: 250 サイクル • メモリバンド幅: 8B • ITLB,DTLB:1Mエントリ • メモリポート: 2 2004/12/2 デザインガイア ARC 研究会 33 シミュレータの設定 (2/2) • 整数演算器 • 浮動小数点除算器 (装置数，実行レイテンシ， 発行レイテンシ) – ALU: 4, 1, 1 – 乗算器: 1, 3, 1 – 除算器: 1, 20, 19 2004/12/2 (装置数，実行レイテンシ， 発行レイテンシ) – ALU: 4, 2, 1 – 乗算器: 1, 4, 1 – 除算器: 1, 12, 12 – 開平演算器: 1,24, 24 デザインガイア ARC 研究会 34 CCC の実装方法の分類 RCコード実行場所 実行前 RCコード 生成方法 実行中 2004/12/2 同一スレッド 別スレッド コンパイル時 CCC 静的 マルチスレッド CCC 動的CCC 動的 マルチスレッド CCC デザインガイア ARC 研究会 35 研究背景 (1/3) • マイクロプロセッサおよび主記憶 (DRAM) の 動作周波数は毎年向上． • しかし，年次動作周波数向上率はマイクロ プロセッサのほうが高い． – マイクロプロセッサ側から見れば，主記憶は 毎年遅くなっている! – 計算よりもデータのロードが圧倒的に遅い． – 「メモリ・ウォール問題」 2004/12/2 デザインガイア ARC 研究会 36 研究背景 (2/3) • メモリ・ウォール問題の代表的な対策技術 – キャッシュ・メモリの搭載 • 多層化 – キャッシュ・プリフェッチ • ストライドプリフェッチ • キャッシュ・ミス頻発ロード命令に着目したプリフェッチ • キャッシュ・ミス頻発ロード命令 – Delinquent ロード 命令: 「DL 命令」 2004/12/2 デザインガイア ARC 研究会 37 提案手法 値を参照するのではなく，計算で求める Computing Centric Computation (CCC) • DL 命令の対策に，CCC の概念を利用． – データを主記憶からロードするのではなく再計算 (Re-Computation; RC)． – DL 命令を再計算 (RC) コードで置換し， 実行サイクル数を削減する手法を提案． 2004/12/2 デザインガイア ARC 研究会 38 全Ｌ２ミス中のDL命令の割合 top1 top2 top3 top4-16 80% 60% 40% 20% bzip2 vortex デザインガイア ARC 研究会 parser ベンチマーク mcf gcc vpr_r vpr_p gzip ammp equake art 2004/12/2 0% mesa 全L2キャッシュ・ミス回数に占める DL 命令によるミス回数の割合 [%] 100% 39
© Copyright 2025 ExpyDoc
