キャッシュ・ミス頻発ロード命令 を対象としたミス原因解析 三輪英樹†，堂後靖博‡，井上弘士¶，村上和彰¶ †九州大学 大学院システム情報科学府 ‡福岡大学大学院工学研究科 ¶九州大学 大学院システム情報科学研究院 2005/8/5 SWoPP 2005 (CPSY2005-22) 1 発表手順 • 研究背景 – メモリ・ウォール問題とは? – キャッシュ・ミス頻発ロード命令 (DL 命令) とは? – CS 命令とは? • DL/CS命令に着目した性能向上手法 – どのような場合に妥当であると言えるか? – そのような場合は実際にあるのか? • まとめ 2005/8/5 SWoPP 2005 (CPSY2005-22) 2 メモリ・ウォール問題とは? • MPUおよびDRAMの動作周波数の違い： – Intel Pentium4: 3.8GHz – DDR2 SDRAM: 533MHz • 計算に必要なデータの参照時間が長い！ DRAM が MPU の性能を抑制 「メモリ・ウォール問題」 2005/8/5 SWoPP 2005 (CPSY2005-22) 3 メモリ・ウォールへの対策と問題点 • 代表的なメモリ・ウォール対策技術 – メモリ・アクセス時間の低減・隠蔽 • オンチップ・キャッシュ・メモリの搭載， キャッシュ・プリフェッチ，ロード値予測，再計算， アウト・オブ・オーダ実行など – メモリ・アクセス回数の削減 • コンパイラによるアクセス回数の削減，再計算など • 性能低下を招くオフチップ・メモリ・アクセス (キャッシュ・ミス) を完全には解消できない． 2005/8/5 SWoPP 2005 (CPSY2005-22) 4 キャッシュ・ミスによる性能低下を 防ぐには? • 命令のキャッシュ・ミスはなんとかなる． • データのキャッシュ・ミスの犯人は? – 犯人グループは少人数．(=少数のロード命令) – くり返し犯行に及ぶ．(=何度もキャッシュ・ミス) Delinquent Load 命令 (DL 命令) • DL命令によるキャッシュ・ミスを防ぐことで， 性能を大幅に改善できる可能性がある！ 2005/8/5 SWoPP 2005 (CPSY2005-22) 5 DL命令をやっつける方法 • プリフェッチもしくは再計算 – ロード対象アドレスに対しプリフェッチ • Data-Driven Multithreading [Roth@Wisconsin,2001] • Speculative Pre-Computation [Collins@Intel,2001] – ロード対象値を再計算 • Load Data Re-Computation [三輪,2004] アドレスもしくは値が間違っている場合，性能 は向上しない． 2005/8/5 SWoPP 2005 (CPSY2005-22) 6 正確にDL命令をやっつけるには? • 犯人グループには黒幕が存在していた！ – DL命令がロードするデータを，メモリ・システムに 書き込んだ (ストアした) 命令． Corresponding Store 命令 (CS命令)(*) • CS命令に着目することで，DL命令のロード 対象データアドレスおよび値が判明！ (*) A. L. Holloway and G. S. Sohi, “Characterization of Problem Stores,” IEEE Computer Architecture Letter, Dec. 2004. 2005/8/5 SWoPP 2005 (CPSY2005-22) 7 DL命令とCS命令との関係 オブジェクト コード 実行された命令の履歴 (命令) (ミス) (データアドレス) (データ値) … STORE1 STORE2 … … … DL1 LOAD1 LOAD2 DL2 LOAD3 LOAD1 ミス アドレス1 DL1 アドレス2 LOAD2 DL2 ミス アドレス3 LOAD3 DL1 ミス アドレス4 LOAD1 値1 値2 値3 値4 知りたい！ 知りたい！ 知りたい！ … 2005/8/5 SWoPP 2005 (CPSY2005-22) 8 DL命令とCS命令との関係 オブジェクト コード CS1 STORE1 CS2 STORE2 CS1 STORE1 (ミス) (データアドレス) (データ値) … アドレス1 アドレス3 アドレス4 値1 値3 値4 ミス アドレス1 DL1 LOAD2 アドレス2 DL2 ミス アドレス3 DL1 ミス アドレス4 値1 値2 値3 値4 … … DL1 LOAD2 DL2 (命令) … … CS1 STORE1 CS2 STORE2 実行された命令の履歴 知りたい！ 知りたい！ 知りたい！ … DL/CS命令に着目しメモリ・システムを高性能化 2005/8/5 SWoPP 2005 (CPSY2005-22) 9 発表手順 (再) • 研究背景 – メモリ・ウォール問題とは? – キャッシュ・ミス頻発ロード命令 (DL 命令) とは? – CS 命令とは? • DL/CS命令に着目した性能向上手法 – どのような場合に妥当であると言えるか? – そのような場合は実際にあるのか? • まとめ 2005/8/5 SWoPP 2005 (CPSY2005-22) 10 仮定 • 32bit の RISC 型マイクロプロセッサ上で プログラムを実行する場合を仮定． – プログラム実行スレッド数: 1 – オンチップ・キャッシュ・メモリ階層数: 2 – 主記憶はDRAMを利用． • DL命令 – キャッシュ・ミスを頻発させる上位16ロード命令 2005/8/5 SWoPP 2005 (CPSY2005-22) 11 DL命令およびCS命令に着目した メモリ・システム高性能化手法 オブジェクトコード CS 命令 DL 命令 Load a Load b Add c, a, b Store c Load c Load x Add z, x, c Store z (1) ストアした値をロード時に短時 間で参照できれば，性能向上可 能． (2) ストア対象アドレスがロード前 に判明していれば，プリフェッチす ることで性能向上可能．(*) (*) A. L. Holloway and G. S. Sohi, “Characterization of Problem Stores,” IEEE Computer Architecture Letter, Dec. 2004. 2005/8/5 SWoPP 2005 (CPSY2005-22) 12 DL命令およびCS命令に着目すること で，本当に性能が上がるのか? • まず，DL/CS命令に着目する妥当性を示す． • 検討項目 1. DL命令がプログラム実行時間に及ぼす影響は 大きいのか? 2. CS命令はそもそも存在するのか? 3. DL命令とCS命令はどのように対応している か?どのような処理か? 4. DL命令およびCS命令のアクセスパタンは? 2005/8/5 SWoPP 2005 (CPSY2005-22) 13 評価実験環境 • シミュレータ – SimpleScalar 3.0d – 命令セット: PISA (32bit MIPS ISA のサブセット) • ベンチマーク・プログラム – SPEC CPU 2000 から 15 (Int:6, Fp: 9) 種類． – gcc-2.7.2.3 で -O2 コンパイル． – 入力セットは ‘‘Reference’’ を利用． 2005/8/5 SWoPP 2005 (CPSY2005-22) 14 主なシミュレータの設定 • 命令発行: アウト・オブ・オーダ • キャッシュ・メモリ容量 – L1データ$: 32KB (64B/エントリ, 2 ウェイ) – L1命令$: 32KB (64B/エントリ, 1 ウェイ) – L2統合: 2MB (64B/エントリ, 4 ウェイ) • アクセスレイテンシ – L1: 1 クロックサイクル – L2: 16 クロックサイクル – 主記憶: 250 クロックサイクル 2005/8/5 SWoPP 2005 (CPSY2005-22) 15 検討項目 (1) DL命令を全て退治できたら? 2005/8/5 SWoPP 2005 (CPSY2005-22) 16 検討項目 (2) CS命令は存在するのか? 2005/8/5 SWoPP 2005 (CPSY2005-22) 17 検討項目 (3) DL命令とCS命令との対応状況 • 検討項目 (1) において，性能向上可能性が 高かったベンチマークについて紹介． – 171.swim, 179.art, 188.ammp – 181.mcf 2005/8/5 SWoPP 2005 (CPSY2005-22) 18 DL-CS対応状況 (179.art) scanner.c:476 (2重ループ中) Y[tj].j += f1_layer[ti].P * bus[ti][tj] scanner.c:193 bus[j][i] += … scanner.c:192 temp = bus[j][i] 5288271 66% (全CS命令の発見回数: 8051663) 2005/8/5 SWoPP 2005 (CPSY2005-22) 1802134 22% scanner.c:455 f1_layer[ti].P =f1_layer[ti].U + tsum; 19 DL-CS対応状況 (188.ammp) atoms.c:152 if (ap->next = ap) break; atoms.c:181 if (ap == ap->next) ap=first; atoms.c:126 last->next = new; atoms.c:123 if (new->next == NULL) 1169021 99% atoms.c:150 if (ap->next == NULL) brak; (全CS命令の発見回数: 1169305) 2005/8/5 SWoPP 2005 (CPSY2005-22) 20 DL-CS対応状況 (181.mcf) 16% mcfutil.c:85 n->pot =n->b_a->cost +n->pred->pot 18% 17% (全CS命令の発見回数: 5399729) 2005/8/5 SWoPP 2005 (CPSY2005-22) 21 DL-CS対応状況 (171.swim) 23% 23% swim.c:416 (2重ループ中) _BLNK__1.z[i + 1 + (j + 1) * 1335 - 1336] = (fsdx * (_BLNK__1.v[i + 1 + (j + 1) * 1335 - 1336] - _BLNK__1.v[i + (j + 1) * 1335 - 1336]) - fsdy * (_BLNK__1.u[i + 1 + (j + 1) * 1335 - 1336] - _BLNK__1.u[i + 1 + j * 1335 - 1336])) / ( _BLNK__1.p[i + j * 1335 - 1336] + _BLNK__1.p[i + 1 + j * 1335 - 1336] + _BLNK__1.p[i + 1 + (j + 1) * 1335 - 1336] + _BLNK__1.p[i + (j + 1) * 1335 - 1336]); 23% (全CS命令の発見回数:1169911) 2005/8/5 SWoPP 2005 (CPSY2005-22) 22 まとめ (1/2) • メモリ・システム高性能化手法開発において， DL命令およびCS命令に着目することの妥当 性を検討． – DL命令が性能に大きな影響を与えることを確認． – ほぼ全てのDL命令に対し，CS命令が存在． 非常に密接に関連している場合もある． DL命令およびCS命令への着目は妥当． • 性能向上に寄与するかどうかの検討が必要． 2005/8/5 SWoPP 2005 (CPSY2005-22) 23 まとめ (2/2) • 今後の課題 – DL命令およびCS命令によるアクセス・パタンの 調査(済み)． – 入力を変えた場合の調査． – キャッシュ・ミスの特徴をより詳しく解析し， その特徴を反映した方法論の提案および評価． 2005/8/5 SWoPP 2005 (CPSY2005-22) 24 ご静聴ありがとうございました 2005/8/5 SWoPP 2005 (CPSY2005-22) 25
© Copyright 2025 ExpyDoc
