演算/メモリ性能バランスを考慮したCMP向け ヘルパースレッド実行方式の提案と評価 九州大学 ○今里 賢一 福本 尚人 井上 弘士 村上 和彰 1 発表手順 • 研究背景 – チップマルチプロセッサ – CMP上の並列処理における性能向上阻害要因 • 演算/メモリ性能バランスを考慮したヘルパー スレッド実行方式 • 提案方式の評価 – 性能モデリングによる評価 – シミュレータによる評価 • まとめと今後の課題 2 チップマルチプロセッサ(CMP) • 1つのチップ上に複数のプロセッサコアを搭載 • 同時に複数のコアで実行することにより性能向上 マルチプログラミング プログラム プログラム プログラム プログラム 1 2 3 4 コア1 コア2 コア3 コア4 L1D$ L1I$ L1D$ L1I$ L1D$ L1I$ L1D$ L1I$ 並列処理 複数のスレッド に分割 コア1 並列 プログラム コア2 コア3 コア4 L1D$ L1I$ L1D$ L1I$ L1D$ L1I$ L1D$ L1I$ L2共有キャッシュ L2共有キャッシュ 主記憶 主記憶 CMP上の並列処理における 性能向上阻害要因 • メモリウォール問題 – プロセッサ-主記憶間の速度差拡大 – CMPではさらに深刻化 • オフチップメモリバンド幅の制約 8 7 6 5 4 3 2 1 0 Perfect L2 cache (100% ヒット) 1MB L2 cache 0 1 2 3 4 5 6 7 8 実行プロセッサコア数 性能向上比 性能向上比 Barnes 4 3.5 3 2.5 2 1.5 1 0.5 0 Cholesky 0 1 2 3 4 5 6 7 8 実行プロセッサコア数 4 本研究のねらい • 従来方式: すべてのコアで並列プログラムを実行 • 疑問点: 本当に全コア実行が得策なのか? – 6コアから +2コアでわずか 「6.9%」 の性能向上 – コアの一部をメモリ性能 向上に利用 性能向上比 • 解決策: 演算/メモリ性能のバランスを考えたコアの Cholesky 運用 4 3.5 3 2.5 2 1.5 1 0.5 0 Perfect L2 cache (100% ヒット) 提案方式の狙い 6.9% 1MB L2 cache 0 1 2 3 4 5 6 7 8 実行プロセッサコア数 5 本研究のねらい • 従来方式: すべてのコアで並列プログラムを実行 • 疑問点: 本当に全コア実行が得策なのか? – 6コアから +2コアでわずか 「6.9%」 の性能向上 – コアの一部をメモリ性能 向上に利用 – 6コアから +2コアで… • 提案:57%の性能向上 性能向上比 • 解決策: 演算/メモリ性能のバランスを考えたコアの Cholesky 運用 4 3.5 3 2.5 2 1.5 1 0.5 0 Perfect L2 cache (100% ヒット) 57% 6.9% 1MB L2 cache 0 1 2 3 4 5 6 7 8 実行プロセッサコア数 6 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ 従来方式 並列 プログラム コア コア コア コア コア コア コア 5 1 2 3 4 6 7 D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ L2共有キャッシュ 主記憶 7 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ • ヘルパースレッド 提案方式 並列 プログラム ヘルパー スレッド コア コア コア コア コア コア コア 5 1 2 3 4 6 7 D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ L2共有キャッシュ 主記憶 – 演算コア用にプリ フェッチ • 利点と欠点 – メモリ性能の向上 – 演算性能の低下 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ • ヘルパースレッド 提案方式 並列 プログラム ヘルパーヘルパー スレッド スレッド コア コア コア コア コア コア コア 5 1 2 3 4 6 7 D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ L2共有キャッシュ – 演算コア用にプリ フェッチ • 利点と欠点 – メモリ性能の向上 – 演算性能の低下 主記憶 9 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ 提案方式 並列 プログラム ヘルパー ヘルパーヘルパー スレッド スレッド スレッド コア コア コア コア コア コア コア 5 1 2 3 4 6 7 D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ L2共有キャッシュ 主記憶 • ヘルパースレッド – 演算コア用にプリ フェッチ • 利点と欠点 – メモリ性能の向上 – 演算性能の低下 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ • ヘルパースレッド 提案方式 並列 プログラム ヘルパーヘルパー スレッド スレッド コア コア コア コア コア コア コアPrefetch A 5 1 2 3 4 6 7 D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ miss L2共有キャッシュ miss – 演算コア用にプリ フェッチ • 利点と欠点 – メモリ性能の向上 – 演算性能の低下 A 主記憶 11 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ • ヘルパースレッド 提案方式 並列 プログラム ヘルパーヘルパー スレッド スレッド コア コア コア コア コア コア コア 5 1 2 3 4 6 7 A I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ A L2共有キャッシュ – 演算コア用にプリ フェッチ • 利点と欠点 – メモリ性能の向上 – 演算性能の低下 A 主記憶 12 演算/メモリ性能のバランシング ~ヘルパースレッドによるプリフェッチ~ • ヘルパースレッド 提案方式 並列 プログラム ヘルパーヘルパー スレッド スレッド コアA コア コア コア コア コア コア Load 5 1 2 3 4 6 7 A I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ I$ D$ hit A L2共有キャッシュ – 演算コア用にプリ フェッチ • 利点と欠点 – メモリ性能の向上 – 演算性能の低下 A 主記憶 13 アーキテクチャ・サポート • ヘルパースレッドはキャッシュミス情報を用い てメモリ参照アドレスを予測 • Miss Status Buffer の導入 – 他コアのキャッシュミス情報をスヌープし格納 並列プログラム を実行 ヘルパースレッド を実行 コア1 MSB L1D$ L1I$ 共有バス コア2 … … MSB L1D$ L1I$ コアN MSB L1D$ L1I$ L2 共有キャッシュ 14 アーキテクチャ・サポート • ヘルパースレッドはキャッシュミス情報を用い てメモリ参照アドレスを予測 • Miss Status Buffer の導入 – 他コアのキャッシュミス情報をスヌープし格納 並列プログラム を実行 ヘルパースレッド を実行 コア1 L1I$ MSB L1D$ miss 共有バス コア2 … … MSB L1D$ L1I$ コアN MSB L1D$ L1I$ L2 共有キャッシュ 15 アーキテクチャ・サポート • ヘルパースレッドはキャッシュミス情報を用い てメモリ参照アドレスを予測 • Miss Status Buffer の導入 – 他コアのキャッシュミス情報をスヌープし格納 並列プログラム を実行 ヘルパースレッド を実行 コア1 L1I$ MSB L1D$ miss 共有バス コア2 … … MSB L1D$ L1I$ コアN MSB L1D$ L1I$ L2 共有キャッシュ 16 ヘルパースレッドの動作 ヘルパースレッドが実行するコード while (true) { 1. miss_info = msb.addr; 2. pref = predict(miss_info); 3. prefetch(pref); } Stride,Marcov, Delta correlation,… 1. Miss Status Buffer からキャッシュミス情報を取得 – Miss Status Buffer が空であれば待機 2. メモリ参照アドレスの予測 – ハードウェアプリフェッチャの模倣 3. プリフェッチ命令の実行 17 発表手順 • 研究背景 – チップマルチプロセッサ – CMP上の並列処理における性能向上阻害要因 • 演算/メモリ性能バランスを考慮したヘルパー スレッド実行方式 • 提案方式の評価 – 性能モデリングによる評価 – シミュレータによる評価 • まとめと今後の課題 18 性能モデリング • Nコア CMP 上での並列処理 – N – m コア: 通常実行,m コア: ヘルパースレッドを実行 提案方式の実行 クロックサイクル数 CC Nhtm 全コア実行時の実行 クロックサイクル数 f 1 演算性能の低下 f メモリ性能の向上 N m による実行クロック による実行クロック 1 rht k N CC N サイクル数の増加 サイクル数の減少 f (1以上) (1以下) 1 f N 19 性能モデリング 並列化できる演算の割合 提案方式の実行 クロックサイクル数 CC Nhtm ヘルパースレッドを実行するコア数 全コア実行時の実行 クロックサイクル数 f 1 f メモリ性能の向上 N m による実行クロック 1 rht k N CC N サイクル数の減少 f (1以下) 1 f N プロセッサコア数 20 性能モデリング 並列化できる演算の割合 提案方式の実行 クロックサイクル数 CC Nhtm ヘルパースレッドを実行するコア数 全コア実行時の実行 クロックサイクル数 f 1 f N m 1 r k CC ht N N f 1 f N プロセッサコア数 全コア実行時の全実行時間にしめる 主記憶アクセスによるストールの割合 全コア実行時からのL2キャッシュミス率の削減率 21 性能解析(Cholesky) f N m 1 r k CC ht N N f 1 f N 1 f CC Nhtm 相対実行時間 CCNthm / CCN 提案方式 従来方式 2 .5 2 .0 性能低下 1 .5 1 .0 0 .5 0 7 6 5 4 3 2 1 0 1 .0 0 .8 m 性能向上 0 0 . 2 0 .6 0 .4 rht ベンチマークプログラム Cholesky (f = 0.73, k N =0.45)の 性能モデル式による実行クロックサイクル数の予測 22 性能解析(Cholesky) f N m 1 r k CC ht N N f 1 f N ヘルパースレッドを実行するコア数 m 2 1 f CC Nhtm 相対実行時間 CCNthm / CCN 1.2 提案方式 従来方式 2 .5 2 .0 1.1 0 .5 0 6 5 4 3 2 1 0 1 .0 0 .8 m 性能向上 0 0 . 2 0 .6 0 .4 rht ベンチマークプログラム Cholesky (f = 0.73, k N =0.45)の 性能モデル式による実行クロックサイクル数の予測 相対実行時間 1 .0 7 1 性能低下 1 .5 +8.4% 0.9 -16.1% 0.8 0.7 -41.4% 0.6 0.5 17.1% 0 0.2 0.4 0.6 0.8 1 L2キャッシュミス率の削減率 rht 23 性能解析(Cholesky) f N m 1 r k CC ht N N f 1 f N ヘルパースレッドを実行するコア数 m 2 1 f CC Nhtm 相対実行時間 CCNthm / CCN 1.2 提案方式 従来方式 0 7 6 5 4 3 2 1 0 1 .0 0 .8 m 性能向上 0 0 . 2 0 .6 0 .4 rht ベンチマークプログラム Cholesky (f = 0.73, k N =0.45)の 性能モデル式による実行クロックサイクル数の予測 +8.4% 1 相対実行時間 • 17.1%以上のミス削減率を 2 .0 達成で高性能化を実現 性能低下 1 .5 • 最大で41.4%の実行時間の削減 1 .0 0.5• ミス削減率が低い場合性能低下 2 .5 1.1 0.9 -16.1% 0.8 0.7 -41.4% 0.6 0.5 17.1% 0 0.2 0.4 0.6 0.8 1 L2キャッシュミス率の削減率 rht 24 提案方式の評価 • 評価内容 – 従来方式: すべてのコアで並列プログラムを実行 – 提案方式: いくつかのコアでヘルパースレッドを実行 比較 • プログラム実行中に実行するスレッドは変更しない • 最適なコア配分は既知 • 評価環境 – シミュレータ: CMPシミュレータ M5 – ベンチマークプログラム: Splash2 から 6 個のプログラムを選択 32KB 1 clock cycle コア1 20 エントリ 1 clock cycle MSB L1D$ L1I$ 共有バス 300 clock cycle コア2 … MSB L1D$ L1I$ L2 共有キャッシュ 主記憶 … コア8 MSB L1D$ L1I$ 1MB 12 clock cycle 25 実装したプリフェッチアルゴリズム • Local Stride プリフェッチ – 命令別にキャッシュミスアドレスのストライド値を保持 – 使用する情報:キャッシュミスアドレス,PC,コア番号 • Global Stride プリフェッチ – 過去 n 個 のキャッシュミスアドレスと現在のキャッシュミスアドレス との差分のうち最も絶対値が小さいものをストライド値として予測 – 使用する情報:キャッシュミスアドレス,コア番号 • Delta Correlation プリフェッチ – 時間的に連続するキャッシュミスアドレスの差分がマルコフ情報 源になっていると仮定しプリフェッチ – 使用する情報:キャッシュミスアドレス,コア番号 26 評価モデル • 従来方式 – BASE: すべてのコアで並列プログラムを実行 • 提案方式 – 必ず1コア以上はヘルパースレッドを実行 – PB-LS: Local Strideプリフェッチ – PB-GS: Global Stride プリフェッチ – PB-DC: Delta Correlation プリフェッチ 27 ヘルパースレッドによるL2キャッシュミス率の削減 0.7 L2キャッシュミス率 0.6 0.5 BASE PB-LS PB-GS LU Ocean PB-DC 64.3% 削減 0.4 0.3 0.2 0.1 0 Cholesky FMM Radix Raytrace ほぼすべての場合において L2 キャッシュミス率を削減 28 提案方式による性能向上 全コア実行時からの性能向上 1.6 BASE 1.4 PB-LS PB-GS PB-DC Ocean Radix 最大で47%の 性能向上 1.2 1 0.8 0.6 0.4 0.2 0 Cholesky FMM LU Raytrace 29 まとめと今後の課題 • まとめ – 演算/メモリ性能のバランスを考慮したヘルパース レッドの実行方式を提案 – 性能モデリングによる評価 – シミュレータによる評価 • 最大で 47% の性能向上 • 今後の課題 – 最適なコアの配分を決定する機構の考案 – 提案方式の詳細な評価 • ベンチマークプログラムの追加 • メモリ関連のパラメータの変更 • ハードウェアプリフェッチャとの組み合わせ 30 ご清聴ありがとうございました 31 最適なコアの配分を決定する機構の考案 • 静的:プログラム実行前に決定 – コンパイラによる解析,事前実行による予測 • 動的:プログラム実行時に決定 – 実行前にパフォーマンスカウンタを入力とした予測モ デルを構築 • 性能モデル式,機械学習,クラスタリング – 実行時にパフォーマンスカウンタの値を取得し予測 32 最適なコアの割当て ※ Ocean,Radix ではスレッド数の制約(2 の累乗にしかスレッド数を設定できない) のため 4:4 となっている :従来方式よりも高い性能向上が得られたもの 33 L2キャッシュサイズを変化させた場合の 提案方式の評価 全コア実行時からの性能向上 1.6 L2-1MB L2-2MB L2-4MB 1.4 1.2 1 0.8 0.6 0.4 0.2 0 Cholesky FMM LU Ocean Radix Raytrace 34 提案方式による性能向上 (並列実行部分) 35 Prefetch Coverage 1 0.90.6 0.80.5 0.7 0.4 0.6 0.50.3 0.40.2 0.3 0.1 0.2 0.1 0 0 PB-GS PB-DC L2キャッシュミス率 Prefetch Coverage PB-LS Cholesky Cholesky FMM LU Ocean Radix Raytrace FMM LU Ocean Radix Raytrace MSB accept rate PB-LS PB-GS PB-DC 1 0.6 0.9 MSB accept rate L2キャッシュミス率 0.8 0.5 0.7 0.4 0.6 0.3 0.5 0.2 0.4 0.3 0.1 0.2 0.1 0 Cholesky FMM LU Ocean Radix Raytrace Cholesky FMM LU Ocean Radix Raytrace 0 プリフェッチの内訳 (PB-LS) 100% discarded l1hits 80% l1mshr_hits 60% 40% remote_hits l2hits l2mshr_hits 20% 0% l2mshr_misses_useless l2mshr_misses_usefull (mshr) l2mshr_misses_usefull (cache) 相対誤差 性能モデル式の誤差(Cholesky, PB-LS) 0.2 0.18 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 L2-1MB+helper_est L2-2MB+helper_est L2-4MB+helper_est 3 4 5 6 メインコア数 7 8 39 プリフェッチアルゴリズム 40 実装したプリフェッチアルゴリズム • Local Stride プリフェッチ – 命令別にメモリ参照アドレスのストライド値を保持 – 使用する情報:キャッシュミスアドレス,PC,コア番号 • Global Stride プリフェッチ – 過去 n 個 メモリ参照アドレスと現在のメモリ参照アドレスとの差分 のうち最も絶対値が小さいものをストライド値として予測 – 使用する情報:キャッシュミスアドレス,コア番号 • Delta Correlation プリフェッチ – 時間的に連続するキャッシュミスアドレスの差分がマルコフ情報 源になっていると仮定しプリフェッチ – 使用する情報:キャッシュミスアドレス,コア番号 41 実装したプリフェッチアルゴリズム (1/2) • ストライドプリフェッチ – キャッシュミスアドレスのストライド値が一定であると予 測しプリフェッチ – Local Stride プリフェッチ • 命令別にメモリ参照アドレスのストライド値を保持 • 使用する情報 – キャッシュミスアドレス,プログラムカウンタ,コア番号 – Global Stride プリフェッチ • 過去 n 個 メモリ参照アドレスと現在のメモリ参照アドレスとの 差分のうち最も絶対値が小さいものをストライド値として予測 • 使用する情報 – キャッシュミスアドレス,コア番号 42 実装したプリフェッチアルゴリズム (2/2) • Delta Correlation プリフェッチ – 時間的に連続するキャッシュミスアドレスの差分が マルコフ情報源になっていると仮定しプリフェッチ – Global History Buffer を用いる手法 – 使用する情報 • キャッシュミスアドレス • コア番号 1, 1 1, 62 時間 ミスアドレス delta 56 57 58 120 121 122 123 185 186 187 1 1 62 1 1 1 62 1 1 62, 1 order = 2 43 Local Stride Prefetching • 命令別にメモリ参照アドレスのストライド値を保持 • ひとつ前のストライド値 と現在のストライド値が 等しい場合プリフェッチ を実行 – 現在のメモリ参照アドレス にストライド値を足したメモリ アクセスアドレス 出典: A Survey of Data Prefetching Techniques 44 Local Stride Prefetching (実験に使用した設定) • 使用する情報 – コア番号 – L2キャッシュミスを起こした命令のプログラムカウンタ – L2キャッシュミスを起こしたメモリ参照アドレス • 助ける対象のコア別に違うテーブルを使用 • テーブルサイズの合計はL1キャッシュサイズと同じ – 総エントリ数: 2048 • 1コアを助けるとき 2048 エントリ/テーブル • 7コアを助けるとき 256 エントリ/テーブル 45 Global Stride Prefetching Miss address Next Addr Stride 更新 エントリの割り当て (LRU置換ポリシ) + Prefetch Addr 46 Global Stride Prefetching (実験に使用した設定) • 使用する情報 – コア番号 – L2キャッシュミスを起こしたメモリ参照アドレス • 助ける対象のコア別に違う Global Miss Address History と テーブルを保持 – エントリ数 • Global Miss Address History : 8 エントリ • Next Addr,Stride を保持するテーブル: 8 エントリ 47 性能モデル式の導出 48 スレッド数 i のときの実行クロックサイクル数 • 一番実行時間が長いスレッドの実行クロックサイクル数 CCi CCexe,i CCmem,i CC i : スレッド数 i のときの実行クロックサイクル数 CC exe,i : スレッド数 i のときの演算実行に要するクロックサイクル数 CC mem ,i : スレッド数 i のときのメモリアクセスに要するクロックサイクル数 ※ ただし、演算とメモリアクセスのオーバーラップ実行は考えない 49 スレッド数 i のときの実行クロックサイクル数 CCexe,i 1 f CCexe,1 f CCexe,1 i f : 並列化できる演算の割合 f 1 f CCexe,1 i CCmem,i ACi HCCL1 MRL1,i HCCL2 MRL2,i MML メモリアクセス回数 ACi ACi (1 f AC ) AC1 f AC AC1 i f AC 1 f AC AC1 i f AC : 並列化できるメモリアクセスの割合 コア ミス率: MRL1,i ・・・ L1$ アクセス時間:HCCL1 ミス率: MRL 2,i アクセス時間:HCCL 2 L2$ 主記憶 バスアクセス時間はスレッド数に 対し一定であると仮定し, アクセス時間: L2キャッシュアクセス時間, 主記憶アクセス時間に含める。 MML 50 スレッド数 i のときの実行クロックサイクル数 f AC f CCi 1 f CCexe,1 1 f AC AC1 i i HCCL1 MRL1,i HCCL2 MRL2,i MML f f AC と仮定 f : 並列化できる演算の割合 f AC : 並列化できるメモリアクセスの割合 f CCi 1 f CCexe,1 AC1 HCCL1 MRL1,i HCCL 2 MRL 2,i MML i 51 スレッド数 N m のときの実行クロックサイクル数 f CC N m 1 f CCexe,1 AC1 HCCL1 MRL1, N m HCCL 2 MRL 2, N m MML N m MRL1, N m MRL1, N MRL 2, N m 1 rMRL 2 , N ,m MRL 2, N と仮定 r MRL 2 , N ,m :スレッド数をNからN-mに減らした時のL2ミス率の減少率 f N m 1 f f CC AC HCC MR HCC MR exe,1 1 L1 L1, N L2 L 2 , N MML f N 1 f スレッド数Nのときの実行クロックサイクル数 CC N N f rMRL 2 , N ,m 1 f AC1 MRL1, N MRL 2, N MML N 1 f CC N m f N m 1 r MR L 2 , N , m k N CC N f 1 f N 1 f スレッド数Nのときの主記憶アクセスによるストール k N :スレッド数Nのときの全実行時間にしめる 主記憶アクセスによるストールの割合 52 スレッド数 N m のときの実行クロックサイクル数 f N m 1 r CC N m MRL 2 , N , m k N CC N f 1 f L2キャッシュミス率の変化による N クロックサイクル数の変化 並列効果の低下による 実行時間 クロックサイクル数の増加 1 1 f 理想的な並列化 f CC1 f CC 1 f CC 1 f CC1 1 N N N f CC CC1 N m 1 f N m CC N m CC N f N m f 1 f N 1 f f が大きいほどスレッド数の減少による クロックサイクル数の増加は大きい rMRL 2 , N ,m k N kN 主記憶 アクセス による ストール 主記憶 アクセス による ストール k N が大きいほど L2 キャッシュミス率の 53 減少によるクロックサイクル数の減少は大きい スレッド数 N m のときの実行クロックサイクル数 f N m 1 r CC N m MRL 2 , N , m k N CC N f 1 f L2キャッシュミス率の変化による N クロックサイクル数の変化 並列効果の低下による 実行時間 クロックサイクル数の増加 1 1 f 8 f 1.0 理想的な並列化 7 f 1 ff N m CC 1 f CC1 N 6 N f 1 f 5 fN CC N m 1 f CC1 N m 4 f 0.8 3 2CC N m 1 f 0.9 CC N 0 f 1 f N m f 1 f 1 2 N3 f 0.6 f 0.4 4 5 6 7 rMRL 2 , N ,m k N kN 主記憶 アクセス による ストール 主記憶 アクセス による ストール m f が大きいほどスレッド数の減少による クロックサイクル数の増加は大きい k N が大きいほど L2 キャッシュミス率の 54 減少によるクロックサイクル数の減少は大きい
© Copyright 2024 ExpyDoc