チップマルチプロセッサにおける データ プリフェッチ効果の分析 福本尚人, 三原智伸九州大学大学院システム情報科学府情報理学専攻 井上弘士, 村上和彰九州大学大学院システム情報科学研究院情報理学部門 2007/6/1 1
発表手順 研究の背景 目的 効果に基づくプリフェッチの分類法 マルチプロセッサ チップマルチプロセッサ 性能モデル式による定性的評価 定量的評価 まとめ 2007/6/1 2
研究の背景 CMP (Chip MultiProcessor) の登場 1つのチップに複数のプロセッサコアを搭載 並列処理により性能向上 例 POWER5, Core2 Duo コア CMP コア CMP の高性能化阻害要因 L1 $ L1 $ メモリウォール問題の深刻化 主記憶へのアクセス頻度の増加 L2 $ コアあたりのメモリバンド幅の減少 データ プリフェッチにより 平均メモリアクセス時間を削減 チップ 2007/6/1 3
研究の背景 目的 研究の背景 従来のプリフェッチ手法はシングルコアプロセッサ前提 CMPでも高い性能向上を発揮できるか分からない メモリ性能をさらに向上させるためにはCMPの特性を考慮したプリフェッチ手法が必要では? 研究目的 CMP におけるプリフェッチ効果の分析 2007/6/1 4
発表手順 研究の背景 目的 効果に基づくプリフェッチの分類法 マルチプロセッサ チップマルチプロセッサ 性能モデル式による定性的評価 定量的評価 まとめ 2007/6/1 5
効果に基づくプリフェッチの分類法 (1/2) プリフェッチ処理においてアクセス対象となるデータ ( プリフェッチ データ ) に着目 プリフェッチ データの状態を定義 初期状態 : プリフェッチ データがキャッシュに読込まれた直後の状態 状態はメモリ性能へ影響を与えるイベントにより遷移 最終状態 : プリフェッチ データがキャッシュから追出されるときの状態 2007/6/1 6
効果に基づくプリフェッチの分類法 (2/2) メモリ性能へ影響を与えるイベント 1. プリフェッチ データの参照 メモリアクセス時間の削減 2. プリフェッチ データによってキャッシュから追出されたデータへの参照 キャッシュミスの増加 3. プリフェッチにより共有状態になったデータへの書込み プリフェッチ データの無効化 無効化要求の増加 状態名 Useful: 1が発生した状態 Conflict:2が発生した状態 Harmful:3が発生した状態 コア 1 2007/6/1 7 L1$ AL2$ 主記憶 コア 2 L1$ L2$ A 3の例 1. コア2:prefetch A 2. データが共有状態へ 3. コア1:Store A 4. コア2のデータが無効化
シングルプロセッサにおける プリフェッチ データの状態遷移 プリフェッチ データの参照 Useful プリフェッチ データの参照 Useful/Conflict Useless 追い出されたデータの参照 Useless/Conflict Useless: プリフェッチ データが参照されていない状態 Useful: プリフェッチ データが参照された状態 Conflict: プリフェッチにより追い出されたデータへの参照があった状態 2007/6/1 8
マルチプロセッサにおけるプリフェッチ データの状態遷移 * プリフェッチ データの参照 Useful プリフェッチ データの参照 Useful/Conflict Useless 追い出されたデータの参照 Useless/Conflict プリフェッチにより共有状態になったデータへの書きこみ プリフェッチにより共有状態になったデータへの書きこみ Harmful 追い出されたデータの参照 Harmful/Conflict Useless: プリフェッチ データが参照されていない状態 Useful: プリフェッチ データが参照された状態 Conflict: プリフェッチにより追い出されたデータへの参照があった状態 Harmful: プリフェッチによる無効化要求が発生した状態 * Jerger, N., Hill, E., and Lipasti, M., ``Friendly Fire: Understanding the Effects of Multiprocessor Prefetching In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 2006. 9
マルチプロセッサと CMP の違い マルチプロセッサ プロセッサ間の通信の際 オフチップをまたぐ必要あり プロセッサ間の通信が遅い マルチプロセッサ コア L1$ L2$ コア L1$ L2$ CMP プロセッサコア間の通信の際 オフチップをまたぐ必要なし プロセッサコア間の通信が高速 あるコアがプリフェッチしたデータを周りのコアが高速にアクセス可能 CMP コア L1 $ コア L1 $ チップ L2 $ 2007/6/1 10
CMP において新たに増えるイベント プリフェッチ データの他コアからの参照 下位メモリ階層よりプリフェッチしたデータを他コアが参照 そのデータを参照したコアのメモリアクセス時間を削減 このイベントが発生した後の状態名 :Remote コア 1 AL1 $ コア 2 L1 $ A 1. コア 1:prefetch A A L2 $ 2. コア 2:Load A A 主記憶 2007/6/1 11
CMP におけるプリフェッチ データの状態遷移 Useless Useful プリフェッチ データの参照 Useless/Remote 他のコアからの参照 Harmful Useful/Conflict プリフェッチ データの参照 2007/6/1 追い出されたデータへの参照 Useless/Conflict /Remote Useless/Conflict 他のコアからの参照 Harmful/Conflict 12
CMP におけるプリフェッチ データの状態遷移 Useless Useful Useless/Remote Harmful プリフェッチによりキャッシュミス増加 Useless/Conflict 2007/6/1 Useful/Conflict Useless/Conflict /Remote Harmful/Conflict 13
CMP におけるプリフェッチ データの状態遷移 プリフェッチ データが参照される プリフェッチ データが他のコアに参照される Useless プリフェッチによる無効化要求の増加 Useful Useless/Remote Harmful Useless/Conflict Useful/Conflict 2007/6/1 Useless/Conflict /Remote プリフェッチ データが参照されない Harmful/Conflict 14
発表手順 研究の背景 目的 効果に基づくプリフェッチの分類法 マルチプロセッサ チップマルチプロセッサ 性能モデル式による定性的評価 定量的評価 まとめ 2007/6/1 15
性能モデル式 (1/2) あるスレッドの実行クロックサイクル CC = CC exe + CC mem CC overlap CC CC CC CC exe mem overlap : 実行クロックサイクル数 : 演算実行に要するクロックサイクル数 : メモリアクセスに要するクロックサイクル数 : オーバーラップ実行したクロックサイクル数 2007/6/1 16
性能モデル式 (2/2) CC mem = AC [ HCC { SBCC ( HCC L2 L1 + (1 MR + + MR MR L2 L1 L1R ) HCC L1 + ( MBCC + MC MR L2 L1R ))}] AC HCC MR MR L1 L1R L2 L1, HCC, MR L2 L2 SBCC, MBCC MC : メモリアクセス回数 :L1(L2) キャッシュアクセス時間 :L1(L2) キャッシュミス率 : 周りのコアのL1キャッシュに対するミス率 :L1 L2 間 (L2 主記憶間 ) バスアクセス時間 : 主記憶アクセス時間 コアコア L1 $ L1 $ L2 $ 主記憶 2007/6/1 17
プリフェッチによるメモリアクセス時間の変化 CC mem = AC [ HCC { SBCC ( HCC L2 L1 + (1 MR + + MR MR ))}] MRL1(MRL2) SBCC(MBCC) MRL1R Useful( プリフェッチ データの参照 ) - - Useless( 参照なし ) - - Remote( 周りのコアからの参照 ) - - Conflict( 必要なデータの追出し ) - Harmful( 無効化要求の増加 ) - - L2 L1 L1R ) HCC L1 + ( MBCC + MC MR L2 L1R Harmful による悪影響を小さくし Remote を利用することで CMP においてより高い性能向上を得ることが可能 18
プリフェッチ効果の定量的分析 分析項目 プリフェッチ データの最終状態の割合 平均メモリアクセス時間 シミュレーション環境 M5:CMP シミュレータ L1 キャッシュでプリフェッチ ストライドプリフェッチ tagged プリフェッチ MOESI プロトコル ベンチマークプログラム SPLASH2: 並列計算用の科学技術計算 D コア I 4MB 8way コアコア D I D I L2$ 主記憶 D コア I 64KB 2 way 2007/6/1 19
周りのコアが得をする場合 (Remote) 参照される場合 1 2 FMM LU Radix Water 1. ストライドプリフェッチ 2.taggedプリフェッチ 周りのコアが得をするプリフェッチは約 5% 2007/6/1 20
プリフェッチによるトラフィックの増加 参照される場合 1 2 FMM LU Radix Water 1. ストライドプリフェッチ 2.taggedプリフェッチ taggedプリフェッチはトラフィックの増加量が大きい 無効化要求が増加するプリフェッチは極めて少ない 2007/6/1 21
プリフェッチによるバスアクセス時間の変化 バスアクセス時間 1 2 3 FMM LU Radix Water 1. ベース 2. ストライドプリフェッチ 3.taggedプリフェッチ プリフェッチによるバスアクセス時間の増加は小さい 2007/6/1 22
まとめと今後の課題 まとめ 発行された各プリフェッチを分類し調査することで CMPにおけるデータ プリフェッチ効果を分析した 従来のプリフェッチ手法は周りのコアからの参照を有効活用していない プリフェッチによる無効化要求の増加は極めて小さい プリフェッチによるトラフィックの増加が性能へ与える影響は小さい 今後の課題 より詳細なプリフェッチ効果の分析 プリフェッチ手法 ベンチマークプログラム キャッシュ構成 CMP 向けプリフェッチ手法の考案 2007/6/1 23
ご清聴ありがとうございました 2007/6/1 24