08 年 月一般財団法人高度情報科学技術研究機構 本資料を教育目的等で利用いただいて構いません 利用に際しては以下の点に留意いただくとともに 下記のヘルプデスクにお問い合わせ下さい 本資料は 構成 文章 画像などの全てにおいて著作権法上の保護を受けています 本資料の一部あるいは全部について いかなる

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁

チューニング技法入門

_{: キャッシュチューニング (C版)}

太田 幸宏

_{(高度情報科学技術研究機構)}

E-mail: yota@rist.or.jp

教科書

青山 幸也「チューニング技法虎の巻」

(平成28年8月1日版)

質問について

(主に)休憩時間に受け付けます

E-mailもご利用ください (後日, 回答します)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂ 2018年11月 一般財団法人高度情報科学技術研究機構 本資料を教育目的等で利用いただいて構いません。利用に際しては以下 の点に留意いただくとともに、下記のヘルプデスクにお問い合わせ下さ い。  本資料は、構成・文章・画像などの全てにおいて著作権法上の保護を 受けています。  本資料の一部あるいは全部について、いかなる方法においても無断で の転載・複製を禁じます。  本資料に記載された内容などは、予告なく変更される場合がありま す。  本資料に起因して使用者に直接または間接的損害が生じても、著作者 はいかなる責任も負わないものとします。 問い合わせ先：ヘルプデスク　helpdesk[-at-]hpci-office.jp（[-at-] を＠にしてください）

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃

アウトライン

第１章 チューニングの基礎

経過時間

, CPU時間, ホットスポット

第２章 コンパイルオプション

コンパイラ

(最適化)を上手に使う

第３章 パフォーマンス測定方法

時間計測の方法

, ホットスポットの特定

第４章 キャッシュチューニング

メモリ階層

(キャッシュの役割),

キャッシュ

(手早く取れるデータ)の活用

第５章 その他のチューニング

”高価”な作業・無駄な計算の削減

, 条件分岐(if文),ループアンローリング

第７章 数値計算ライブラリー

よく調整されたコード利用

(BLAS, LAPACK, FFTW)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄

４－１キャッシュとは

記憶装置の階層構造

(Memory hierarchy) (

4-1

)

記憶装置

(メモリ, キャッシュ, レジスター) の「物理的」特徴

*)

高速

or 大容量 → 高価

低速

or 小容量 → 低価

“速度・容量・コスト

(値段)

” のバランス → 「メモリの階層構造」

(階層構造において) キャッシュの役割 (データの動き) を理解

キャッシュの効率よい利用 → パフォーマンスの向上

*) 内田啓一郎, 小柳滋「コンピュータアーキテクチャ」(オーム社) 3章 渡辺宙志「高速化チューニングとその関連技術2」(CMSI計算科学技術特論A 第9回); https://www.youtube.com/user/CMSInitiative

P. van der Lindern「エキスパートCプログラミング ―知られざるCの深層」 (梅原系 訳) (アスキー,1996) chapter 7

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅

４－１キャッシュとは

Case study: ”バランス”のとれたアーキテクチャー (図4-1-1) プログラム (実行可能モジュール) a.out の処理の流れ 機械語命令とデータから構成 → 各々専用の「場所」に転送 → 解読 or 演算 Question: 「処理の流れ」をどのように計算機中で実現するか? ● メモリ(低速・大容量_{)とレジスタ(}高速・小容量_{) の2段構成 [}図_4-1-1(1)] 性能と価格のバランス データ: メモリ上に一度格納 処理にとって重要な部分:レジスタへ転送 a.out: ロード(実行)モジュール メモリ (低速/安価/大容量) 命令レジスタ (高速/高価/小容量) データレジスタ_{(高速/高価/小容量)} 演算 解読 機械語命令 データ 命令 データ

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₆

４－１キャッシュとは

● 高速・大容量メモリのみ _[図_4-1-1(2)] 高コスト メモリ (低速/安価/大容量) 演算 解読 機械語命令 データ a.out: ロード(実行)モジュール Case study: ”バランス”のとれたアーキテクチャー (図4-1-1) プログラム (実行可能モジュール) a.out の処理の流れ 機械語命令とデータから構成 → 各々専用の「場所」に転送 → 解読 or 演算 Question: 「処理の流れ」をどのように計算機中で実現するか?

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₇

４－１キャッシュとは

● キャッシュの挿入 [図_4-1-1(3)] メモリ(低速・大容量)とレジスタ(高速・小容量) の中間的な存在 必要性に応じた階層的なデータ格納 ここのデータ の動きを追う Case study: ”バランス”のとれたアーキテクチャー (図4-1-1) プログラム (実行可能モジュール) a.out の処理の流れ 機械語命令とデータから構成 → 各々専用の「場所」に転送 → 解読 or 演算 Question: 「処理の流れ」をどのように計算機中で実現するか? 機械語命令 データ HDD/SSD メモリ 命令キャッシュ データキャッシュ 命令レジスタ データレジスタ 機械語命令 データ メモリ 低速/安価/大容量/必要性低い 高速/高価/小容量/必要性高い 命令 データ 命令 データ

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₈

４－１キャッシュとは

Memo 典型的なデバイスのデータ転送特性*) バンド幅 (bandwidth): 単位時間あたりのデータ転送量 (throughput) レイテンシ (latency): データ転送の立ち上げに「必ず」かかる時間

*) Hager and Wellein, Introduction to High Performance Computing for Scientists and Engineers (CRC) p.64 Parallel I/O in Practice; http://www.nersc.gov/assets/Training/pio-in-practice-sc12.pdf

レイテンシ (sec) 10-9 10-8 10-9 10-7 10-2 バンド幅 (bytes/sec) 1011 1010 107 L1キャッシュ L2/L3キャッシュ メインメモリ HDD 108

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₉

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルの設定

(

図

4-1-2

) (実際の例→

4-3節

)

データレジスタ

: 1個; データキャッシュ: 2段 (2-way); メモリ

データレジスタ (高速) データキャッシュ メモリ (低速) 各段は小区画(キャッシュライン) に分かれている 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 メモリ内もキャッシュラインに対応 するよう小区画に分かれている

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₀

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルの設定

(

図

4-1-2

) (実際の例→

4-3節

)

データレジスタ

: 1個; データキャッシュ: 2段 (2-way); メモリ

Memo

京 (SPARC64TM _{VIIIfx) の場合 (http://www.r-ccs.riken.jp/jp/k/system.html)}

倍精度浮動小数点レジスタ: 256個 (1コア当り)

1次命令キャッシュ: 32 KiByte (2段, 1段当りキャッシュラインは128個)

1次データキャッシュ: 32 KiByte (2段,1段当りキャッシュラインは128個)

→ 「画」を描いてみるとよい

32KiB, 2段 ==> 16 (=32/2) KiB per 段 1 2

16 KiB ==> 16/(8 bytes) = 2048要素 (倍精度浮動小数点) 1 128 ラインの幅 = L (bytes) 16×1014 bytes = 128 × L ==> L = 128 bytes ==> 128/(8 bytes) = 16 要素 (倍精度浮動小数点)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₁ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルの設定

(

図

4-1-2

) (実際の例→

4-3節

)

1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 動作に関する約束１ メモリ-キャッシュ間でデータはキャッシュライン単位で移動(コピー) 1 1 2 2 3 3 1 1 2 2 3 3 a[0] a[1] a[2] データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[30] a[31] a[32] a[33] a[34] a[35]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₂ 1 1 2 2 3 3

４－１キャッシュとは

1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルの設定

(

図

4-1-2

) (実際の例→

4-3節

)

データレジスタ (高速) データキャッシュ メモリ (低速) 動作に関する約束２ メモリ-キャッシュ間は, 同じ数字のラベル同士で移動(コピー) (1↔1, 2↔2, 3↔3) 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 a[0] a[1] a[2] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₃ 1 1 2 2 3 3

４－１キャッシュとは

1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 a[15] a[16] a[17] a[33] a[34] a[35]

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルの設定

(

図

4-1-2

) (実際の例→

4-3節

)

データレジスタ (高速) データキャッシュ メモリ (低速) 動作に関する約束３ データはキャッシュ上の空いている段に移動(コピー) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₄ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 Step 0 配列データはメモリ上に(キャッシュの構造から見て)”連続的”に配置 [図4-1-2(2)] メモリ上の配置開始位置は状況依存 (図では左上からと仮定) データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₅ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 1 ループでi=0[図4-1-2(1)]→ a[0]が必要 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=0 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₆ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 1 ループでi=0[図4-1-2(1)]→ a[0]が必要 → メモリからキャッシュに転送 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=0 データレジスタ (高速) データキャッシュ メモリ (低速) (低速) a[0] a[1] a[2] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₇ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 1 ループでi=0[図4-1-2(1)]→ a[0]が必要 → メモリからキャッシュに転送 → キャッシュからレジスタへa[0]が転送→演算 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=0 a[0] a[1] a[2] a[0] データレジスタ (高速) データキャッシュ メモリ (低速) (高速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₈ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 データレジスタ (高速) データキャッシュ メモリ (低速) Step 1 ループでi=0[図4-1-2(1)]→ a[0]が必要 → メモリからキャッシュに転送 → キャッシュからレジスタへa[0]が転送→演算 → 演算後, レジスタからキャッシュへa[0]が転送 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=0 a[0] a[1] a[2] a[0] (高速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₁₉ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 2 ループでi=1[図4-1-2(1)]→ a[1]が必要 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=1 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₀ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 2 ループでi=1[図4-1-2(1)]→ a[1]が必要 →既にあるキャッシュ上のデータをレジスターへ転送 → 演算 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=1 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[1] (高速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₁ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 2 ループでi=1[図4-1-2(1)]→ a[1]が必要 → 既にあるキャッシュ上のデータをレジスターへ転送 → 演算 → 演算後, レジスターからキャッシュへa[1]が転送 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 I=2 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[1] (高速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₂ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 3 ループでi=3[図4-1-2(1)]→ a[3]が必要 →メモリからキャッシュへ転送 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=3 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₃ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 3 ループでi=3[図4-1-2(1)]→ a[3]が必要 →メモリからキャッシュへ転送 → キャッシュからレジスタへa[3]が転送→演算 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=3 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[3] (高速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₄ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 3 ループでi=3[図4-1-2(1)]→ a[3]が必要 →メモリからキャッシュへ転送 → キャッシュからレジスタへa[3]が転送→演算 → 演算後, レジスターからキャッシュへa[3]が転送 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=3 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[3] (高速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₅ 1 1 2 2 3 3

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

1段目 2段目 Step 4 ループでi=17の処理が終わった時点の状態 [図4-1-2(3)] → キャッシュは1段目, 2段目どちらも満杯 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=17 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₆

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

Step 5 ループでi=18[図4-1-2(1)]→ a[18]が必要 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=18 データレジスタ (高速) データキャッシュ メモリ (低速) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₇

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

Step 5 ループでi=18[図4-1-2(1)]→ a[18]が必要 →古いデータがキャッシュより追い出し → メモリ内データと異なればメモリ内データを変更 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=18 データレジスタ (高速) データキャッシュ メモリ (低速) (低速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₈

４－１キャッシュとは

レジスター

↔ キャッシュ ↔ メモリ間のデータ転送

₍

_4-2

₎

簡易モデルによるデータ転送の説明

(

図

4-1-2

)

Step 5 ループでi=18[図4-1-2(1)]→ a[18]が必要 →古いデータがキャッシュより追い出し → メモリ内データと異なればメモリ内データを変更 → 空いたキャッシュラインにメモリから転送 → 以後, i=35まで同様の処理 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=18 データレジスタ (高速) データキャッシュ メモリ (低速) (低速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₂₉

４－１キャッシュとは

Memo キャッシュ上データとメモリ上のデータの同期 (一貫性)*) 今回の方式: ライトバック キャッシュ上からデータの追い出し → メモリ上のデータ更新 *) 内田啓一郎, 小柳滋「コンピュータアーキテクチャ」(オーム社) 3章 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 i=18 データレジスタ (高速) データキャッシュ メモリ (低速) (低速) _a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[33] a[34] a[35] a[30] a[31] a[32] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17]

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₀

４－２キャッシュミスを少なくするための考慮点

キャッシュミスとは

(

4-3

)

計算に必要なデータがキャッシュにない状態

キャッシュミス

:メモリからのデータ転送が要求→ パフォーマンス低下

データ転送速度

: (レジスタ

↔キャッシュ) > (キャッシュ↔メモリ)

キャッシュミスを抑える

[31]

ゼロは難しい

(例: 初期段階ではメモリから転送する必要あり)

一度キャッシュに入ったデータの有効利用

→ 大事

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₁

ここまでのまとめ

第４章 キャッシュチューニング

キャッシュの役割

(メモリ階層)

レジスタ

(演算器に最も近いデータ格納領域) とメモリの中間

必要性が高いデータを格納し

, 高速にレジスタへ転送

キャッシュミス

キャッシュ上のデータが有効利用されないこと

ミスの原因を理解

: (ある程度は)ハードウェアの知識が必要

着眼点

: レジスタ-キャッシュ-メモリ間のデータ転送の動きを理解

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₂

アウトライン

第１章 チューニングの基礎

経過時間

, CPU時間, ホットスポット

第２章 コンパイルオプション

コンパイラ

(最適化)を上手に使う

第３章 パフォーマンス測定方法

時間計測の方法

, ホットスポットの特定

第４章 キャッシュチューニング

メモリ階層

(キャッシュの役割),

キャッシュ

(手早く取れるデータ)の活用

第５章 その他のチューニング

”高価”な作業・無駄な計算の削減

, 条件分岐(if文),ループアンローリング

第７章 数値計算ライブラリー

よく調整されたコード利用

(BLAS, LAPACK, FFTW)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₃

４－２キャッシュミスを少なくするための考慮点

１次元配列

(１重ループ)とキャッシュミス

(

4-3

)

ストライド

: メモリ上での処理される配列要素間の距離 (

図

4-2-1, 図4-2-2

)

1次元配列の考慮点:

キャッシュミスを少なくするためには

, ストライドを短くすること

Case study: 1次元配列のアクセスパターン (図4-2-1, 図4-2-2) どちらがキャッシュが有効利用されているか? (簡易モデルで考える) キャッシュ: 2段, キャッシュライン: 3個, ラインあたりに3要素入力可能 ストライド4 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[30] a[31] a[32] a[33] a[34] a[35] ストライド1 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] a[27] a[28] a[29] a[30] a[31] a[32] a[33] a[34] a[35] ストライド4 □でキャッシュミス発生; 　○のデータはキャッシュ上 ストライド1

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₄

４－２キャッシュミスを少なくするための考慮点

Case study: 1次元配列のアクセスパターン (図4-2-1, 図4-2-2) ストライド4の何が問題か? (簡易モデルで考える) 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] 3 3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 1 1 2 2 3 3 1 1 2 2 a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] 33 a[27] a[28] a[29] a[30] a[31] a[32] a[33] a[34] a[35] データキャッシュ メモリ ストライド4 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] i=20の時点 (キャッシュは満杯) 利用されたデータ: 赤字のみ i=0 i=4 i=8 i=12 i=16 i=20

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₅ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]

４－２キャッシュミスを少なくするための考慮点

Case study: 1次元配列のアクセスパターン (図4-2-1, 図4-2-2) ストライド4の何が問題か? (簡易モデルで考える) 1 1 2 2 3 3 1段目 2段目 1 1 2 2 3 3 1 1 2 2 3 3 a[9] a[10] a[11] a[12] a[13] a[14] a[15] a[16] a[17] 1 1 2 2 3 3 1 1 2 2 a[27] a[28] a[29] a[30] a[31] a[32] a[33] a[34] a[35] 3 3 a[18] a[19] a[20] a[21] a[22] a[23] a[24] a[25] a[26] データキャッシュ メモリ ストライド4 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[12] a[13] a[14] a[15] a[16] a[17] a[18] a[19] a[20] i=20の時点 (キャッシュは満杯) 利用されたデータ: 赤字のみ 次 (i=24) のデータはキャッシュ上にない メモリから転送 + キャッシュから(未使用の)古いデータの追い出 し i=0 i=4 i=8 i=12 i=16 i=20 i=24

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₆

４－２キャッシュミスを少なくするための考慮点

１次元配列

(１重ループ)とキャッシュミス

(

4-3

)

ストライド

: メモリ上での処理される配列要素間の距離 (

図

4-2-1, 図4-2-2

)

1次元配列の考慮点

キャッシュミスを少なくするためには

, ストライドを短くすること

Memo ストライド1アクセスなら問題ないか? キャッシュミスに関する留意点あり: 4-4節, 4-5節 (スラッシング, Thrashing)*) *) 今村俊幸「キャッシュ性能安定性について」スーパーコンピューティングニュース Vol.9特集号 (2008) pp.111-121; http://www.cc.u-tokyo.ac.jp/support/press/news/VOL9/special/ サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₇

４－２キャッシュミスを少なくするための考慮点

例: 簡易モデルにおける2次元配列a[9][4]のメモリ上の配置

[Cの場合]多次元配列(多重ループ)とキャッシュミス

(

4-5

)

メモリー上の配列の配置

[

図

4-2-6(2), 図4-2-7(2)

]

右側の添字が先に動く

キャッシュミスを抑制

: ストライド 1のアクセスパターンが好ましい

→

内側のループを配列の右側の添字で反復させること

Memo コンパイラによる自動ループ入れ替え (4-3節) a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3] a[3][0] a[3][1] a[3][2] a[3][3] a[4][0] a[4][1] a[4][2] a[4][3] a[5][0] a[5][1] a[5][2] a[5][3] a[6][0] a[6][1] a[6][2] a[6][3] a[7][0] a[7][1] a[7][2] a[7][3] a[8][0] a[8][1] a[8][2] a[8][3] サンプルコード: alloc2d

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₈ a[4][2] a[4][3] a[5][0] a[5][1] a[5][2] a[5][3] a[6][0] a[6][1] a[6][2]

４－２キャッシュミスを少なくするための考慮点

メモリ上の配置 (簡易モデル) Case study: 配列の図とメモリ上の配置の比較 配列a[i][j]の図 (行列とみなす場合) (図_4-2-8) a[0][0] a[1][0] a[2][0] a[3][0] a[4][0] a[5][0] a[6][0] a[7][0] a[8][0] a[0][1] a[1][1] a[2][1] a[3][1] a[4][1] a[5][1] a[6][1] a[7][1] a[8][1] a[0][2] a[1][2] a[2][2] a[3][2] a[4][2] a[5][2] a[6][2] a[7][2] a[8][2] i j a[0][3] a[1][3] a[2][3] a[3][3] a[4][3] a[5][3] a[6][3] a[7][3] a[8][3] a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3] a[3][0] a[3][1] a[3][2] a[3][3] a[4][0] a[4][1] a[6][3] a[7][0] a[7][1] a[7][2] a[7][3] a[8][0] a[8][1] a[8][2] a[8][3]

右側の添字が先に動く_{(raw major order)}*)

*) P. van der Lindern「エキスパートCプログラミング ―知られざるCの深層」(梅原系 訳) (アスキー,1996) chapter 10 北山洋幸「高速化プログラミング入門」(カットシステム, 2016) 第4章

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₃₉

４－２キャッシュミスを少なくするための考慮点

Case study: 2次元配列a[9][4]に対する2重ループ計算 (簡易モデル)

多重ループでは(より)内側の添字が(より)先に動く 左側の添字 右側の添字 右側の添字 左側の添字 ストライド4 a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3] a[3][0] a[3][1] a[3][2] a[3][3] a[4][0] a[4][1] a[4][2] a[4][3] a[5][0] a[5][1] a[5][2] a[5][3] a[6][0] a[6][1] a[6][2] a[6][3] a[7][0] a[7][1] a[7][2] a[7][3] a[8][0] a[8][1] a[8][2] a[8][3] a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3] a[3][0] a[3][1] a[3][2] a[3][3] a[4][0] a[4][1] a[4][2] a[4][3] a[5][0] a[5][1] a[5][2] a[5][3] a[6][0] a[6][1] a[6][2] a[6][3] a[7][0] a[7][1] a[7][2] a[7][3] a[8][0] a[8][1] a[8][2] a[8][3] ストライド1 内側のループを配列の 右側の添字で反復させる こと

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₀

４－２キャッシュミスを少なくするための考慮点

[Fortranの場合]多次元配列(多重ループ)とキャッシュミス

(

4-4

)

メモリー上の配列の配置

[

図

4-2-3(2), 図4-2-4(2)

]

左側の添字が先に動く

キャッシュミスを抑制

: ストライド 1のアクセスパターンが好ましい

→

内側のループを配列の左側の添字で反復させること

Memo コンパイラによる自動ループ入れ替え (4-3節) 例: 簡易モデルにおける 2次元配列A(4,9)のメモリ上の配置 A(1,1) A(2,1) A(3,1) A(4,1) A(1,2) A(2,2) A(3,2) A(4,2) A(1,3) A(2,3) A(3,3) A(4,3) A(1,4) A(2,4) A(3,4) A(4,4) A(1,5) A(2,5) A(3,5) A(4,5) A(1,6) A(2,6) A(3,6) A(4,6) A(1,7) A(2,7) A(3,7) A(4,7) A(1,8) A(2,8) A(3,8) A(4,8) A(1,9) A(2,9) A(3,9) A(4,9) サンプルコード: alloc2d

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₁

４－６キャッシュチューニング

行と列の入れ替え

(Interchange) (

4-15

)

2重ループの最内ループ[図4-6-1(1)]: 配列b[j][i]でキャッシュミス多発 Cにおける「右側の添字から動かす」原則に従っていない 対策: 一時配列の利用による行と列の入れ替え [図4-6-1(2)] 入れ替えでキャッシュミス発生 10000回実行されるループ中ではキャッシュミス軽減 → 性能向上が期待

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₂

４－６キャッシュチューニング

ブロック化

(Loop blocking) (

4-19, 4-20; 4-8も参照

)

[27]

2重ループの最内ループ[図4-6-8(1)]: 配列b[j][i]でキャッシュミス多発 Cにおける「右側の添字から動かす」原則に従っていない 対策: 行と列の入れ替えをせず, キャッシュミスを軽減→ ブロック化[図4-6-9(1)] Memo プログラムの演算順序を変更する対策 利用前提: 順序変更によるロジック変更が発生しないこと サンプルコード: mattp 外側ループ (ブロック)の インデックス: 3個跳び 内側ループのインデックス: 1個づつ

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₃

４－６キャッシュチューニング

ブロック化

(Loop blocking) (

4-19, 4-20; 4-8も参照

)

[27]

プログラムの書き換え方 (ループ変換) ループを「(ループ長がより短い)入れ子ループ (nested loop)」に変換 ブロック化, ストリップマイニング (

4-20

) において基本となる変換 変換後: コードの可読性は低下 → 効果がある部分のみに適用すべき サンプルコード: mattp for(i=0;i<N;++i){ A(i) += B; } LEN = N/3; for(i=0;i<LEN;++i){ A(i) += B; } for(i=LEN;i<2*LEN;++i){ A(i) += B; } for(i=2*LEN+1;i<N;++i){ A(i) += B; }

#define MIN(a,b) ((a)<(b)?(a):(b)) LEN = N/3; for(i=0;i<N;i+=LEN){ for(ii=i;ii<MIN(i+LEN,N);++ii){ A(ii) += B; } }

=

=

3個の短いループに分割 (各ループの長さ ~ N/3) まとめて記述 (入れ子ループ) 外側ループ長 = 3 (or 3+1) 内側ループ長 ~ N/3

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₄

４－６キャッシュチューニング

ブロック化

(Loop blocking) (

4-19, 4-20; 4-8も参照

)

[27]

プログラムの書き換え方 (ループ変換) ループを「(ループ長がより短い)入れ子ループ (nested loop)」に変換 ブロック化, ストリップマイニング (

4-20

) において基本となる変換 変換後: コードの可読性は低下 → 効果がある部分のみに適用すべき ブロック化 = 2重 (多重) ループの各ループに対し「分割&入れ子化」 期待: ループ長を短くする → キャッシュ内データの再利用を促進 サンプルコード: mattp Memo ストリップマイニング (

4-20

) ベクトル計算機における技法*) スカラー計算機では? キャッシュ上のデータの再利用 (

4-20

)

SIMD (Single Instruction Multiple Data)**) 命令を促進

*) ヘネシー&パターソン「コンピュータ・アーキテクチャ: 定量的アプローチ 第5版」(翔泳社, 2014) 第4章 **) HPCプログラミングセミナー 「Introduction to Tuning on Intel Knights Landing」

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₅

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) ブロック化前 配列の図 (メモリ上の配置ではない) i j _i j

=

a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5] a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5] a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5] a[3][0] a[3][1] a[3][2] a[3][3] a[3][4] a[3][5] a[4][0] a[4][1] a[4][2] a[4][3] a[4][4] a[4][5] a[5][0] a[5][1] a[5][2] a[5][3] a[5][4] a[5][5] b[0][0] b[0][1] b[0][2] b[0][3] b[0][4] b[0][5] b[1][0] b[1][1] b[1][2] b[1][3] b[1][4] b[1][5] b[2][0] b[2][1] b[2][2] b[2][3] b[2][4] b[2][5] b[3][0] b[3][1] b[3][2] b[3][3] b[3][4] b[3][5] b[4][0] b[4][1] b[4][2] b[4][3] b[4][4] b[4][5] b[5][0] b[5][1] b[5][2] b[5][3] b[5][4] b[5][5] メモリ上の配置 配列a: ストライド1アクセス 配列b: ストライド6アクセス →キャッシュミス多発の温床

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₆

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) メモリ a[0][0] a[0][1] a[0][2] b[2][0] b[2][1] b[2][2] b[1][0] b[1][1] b[1][2] b[0][0] b[0][1] b[0][2] データキャッシュ i=0, j=2 の時点 利用されたキャッシュ上データ: 赤字のみ 配列b[j][i]を転送するため, キャッシュミス多発 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5] a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5] a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5] a[3][0] a[3][1] a[3][2] a[3][3] a[3][4] a[3][5] a[4][0] a[4][1] a[4][2] a[4][3] a[4][4] a[4][5] a[5][0] a[5][1] a[5][2] a[5][3] a[5][4] a[5][5] b[0][0] b[0][1] b[0][2] b[0][3] b[0][4] b[0][5] b[1][0] b[1][1] b[1][2] b[1][3] b[1][4] b[1][5] b[2][0] b[2][1] b[2][2] b[2][3] b[2][4] b[2][5] b[3][0] b[3][1] b[3][2] b[3][3] b[3][4] b[3][5] b[4][0] b[4][1] b[4][2] b[4][3] b[4][4] b[4][5] b[5][0] b[5][1] b[5][2] b[5][3] b[5][4] b[5][5] ブロック化前

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₇

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) メモリ a[0][0] a[0][1] a[0][2] b[2][0] b[2][1] b[2][2] b[1][0] b[1][1] b[1][2] b[0][0] b[0][1] b[0][2] データキャッシュ i=0, j=2 の時点 利用されたキャッシュ上データ: 赤字のみ 配列b[j][i]を転送するため, キャッシュミス多発 次のデータ (i=0, j=3) → キャッシュ上にない メモリから転送 古いキャッシュ上の(未使用)データをメモリに追い出す可能性 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5] a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5] a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5] a[3][0] a[3][1] a[3][2] a[3][3] a[3][4] a[3][5] a[4][0] a[4][1] a[4][2] a[4][3] a[4][4] a[4][5] a[5][0] a[5][1] a[5][2] a[5][3] a[5][4] a[5][5] b[0][0] b[0][1] b[0][2] b[0][3] b[0][4] b[0][5] b[1][0] b[1][1] b[1][2] b[1][3] b[1][4] b[1][5] b[2][0] b[2][1] b[2][2] b[2][3] b[2][4] b[2][5] b[3][0] b[3][1] b[3][2] b[3][3] b[3][4] b[3][5] b[4][0] b[4][1] b[4][2] b[4][3] b[4][4] b[4][5] b[5][0] b[5][1] b[5][2] b[5][3] b[5][4] b[5][5] ブロック化前

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₈

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) メモリ a[0][0] a[0][1] a[0][2] b[2][0] b[2][1] b[2][2] b[1][0] b[1][1] b[1][2] b[0][0] b[0][1] b[0][2] データキャッシュ i=0, j=2 の時点 利用されたキャッシュ上データ: 赤字のみ 配列b[j][i]を転送するため, キャッシュミス多発 もし, 次のデータを(i=1, j=0) から取るとする: メモリから転送 キャッシュ上のデータが利用される可能性 → 多重ループの内側を短 くすると, キャッシュミスが軽減される可能性 (4-3節) → ブロック化 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5] a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5] a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5] a[3][0] a[3][1] a[3][2] a[3][3] a[3][4] a[3][5] a[4][0] a[4][1] a[4][2] a[4][3] a[4][4] a[4][5] a[5][0] a[5][1] a[5][2] a[5][3] a[5][4] a[5][5] b[0][0] b[0][1] b[0][2] b[0][3] b[0][4] b[0][5] b[1][0] b[1][1] b[1][2] b[1][3] b[1][4] b[1][5] b[2][0] b[2][1] b[2][2] b[2][3] b[2][4] b[2][5] b[3][0] b[3][1] b[3][2] b[3][3] b[3][4] b[3][5] b[4][0] b[4][1] b[4][2] b[4][3] b[4][4] b[4][5] b[5][0] b[5][1] b[5][2] b[5][3] b[5][4] b[5][5] i j 0 0 0 1 0 2 0 3 … 0 5 1 0 i j 0 0 0 1 0 2 0 3 … 0 5 1 0 飛ばす (後回し)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₄₉

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) ブロック化後 内側のループの反復数を小さくする → 反復数は「3」 配列a: ブロック内でストライドが変わる

例: a00, a01, a02→ストライド1; a02,a10→ストライド4 オリジナル版よりキャッシュミスは若干増える可能性 配列b: 内側ループの反復数が小さい キャッシュミスは軽減される可能性 → 2種の効果のバランスで, 性能向上が期待 i i j

=

j ブロック化後の配列の図 (メモリ上の配置ではない)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₀

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) ブロック化後 内側のループの反復数を小さくする → 反復数は「3」 配列a: ブロック内でストライドが変わる

例: a00, a01, a02→ストライド1; a02,a10→ストライド4 オリジナル版よりキャッシュミスは若干増える可能性 配列b: 内側ループの反復数が小さい キャッシュミスは軽減される可能性 → 2種の効果のバランスで, 性能向上が期待 i i j

=

j ブロック化後の配列の図 (メモリ上の配置ではない)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₁

４－６キャッシュチューニング

Case study: ブロック化によるキャッシュミス軽減 (簡易モデル) ブロック化後 内側のループの反復数を小さくする → 反復数は「3」 配列a: ブロック内でストライドが変わる

例: a00, a01, a02→ストライド1; a02,a10→ストライド4 オリジナル版よりキャッシュミスは若干増える可能性 配列b: 内側ループの反復数が小さい キャッシュミスは軽減される可能性 → 2種の効果のバランスで, 性能向上が期待 i i j

=

j ブロック化後の配列の図 (メモリ上の配置ではない)

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₂

４－６キャッシュチューニング

ブロック化

(Loop blocking) (

4-19, 4-20; 4-8も参照

)

2重ループの最内ループ[図4-6-8(1)]: 配列b[j][i]でキャッシュミス多発 Cにおける「右側の添字から動かす」原則に従っていない 対策: 行と列の入れ替えをせず, キャッシュミスを軽減→ ブロック化[図4-6-9(1)] Memo ● ブロック化は行列演算で有効 ● ブロック数 (最内ループ反復数)はマシン環境および課題依存 最適値の決定には try&errorが必要 ● [27]の第３章 メモリ階層の視点からブロック化を統一的に理解

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₃

まとめ

第４章 キャッシュチューニング

高速で転送されるキャッシュ上データを効率よく利用すること

1重ループ: ストライドを短く

多重ループ

[Fortran]:内側のループを配列の左側の添字で反復

多重ループ

[C]:内側のループを配列の右側の添字で反復

キャッシュチューニング → キャッシュミスの軽減策

ブロック化

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₄

Appendix

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₅

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

Case study: より現実的な簡易モデル (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8} データキャッシュ 1段目 2段目 ライン 1 ライン 2 メモリ 1 2 1 2 1 1 11 11 2 2 22 22 Recall: データの移動は キャッシュライン単位 Recall: キャッシュ-メモリ 間のマッピング 1↔ 11, 2 ↔ 22

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₆

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₇

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] i=0: a[0], b[0]が転送された状態 c[0],…,c[3]が入る空きがない a[0] a[1] a[2] a[3] b[0] b[1] b[2] b[3] 入れない サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₈

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] i=0: a[0], b[0], c[0]が転送された状態 c[0],…,c[3]が入る空きがない →古いデータ(例: a[0],…,a[3]) の追い出し b[0] b[1] b[2] b[3] 追い出し+データ同期 c[0] c[1] c[2] c[3] 転送 サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₅₉

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] i=0: 演算後 b[0] b[1] b[2] b[3] c[0] c[1] c[2] c[3] サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₆₀

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] i=1:a[1]をメモリに要求 (キャッシュミス) b[0] b[1] b[2] b[3] c[0] c[1] c[2] c[3] a[0],…,a[3]が入る空きがない 入れない サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₆₁

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] i=1:a[1]をメモリに要求 (キャッシュミス) c[0] c[1] c[2] c[3] a[0],…,a[3]が入る空きがない →古いデータ(例: b[0],…,b[3]) の追い出し a[0] a[1] a[2] a[3] 転送 追い出し+データ同期 サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₆₂

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

データキャッシュ 1段目 2段目 メモリ a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] Case study: キャッシュスラッシング (より現実的な簡易モデル) (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8}

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗 (が典型)

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] i=1:b[1]をメモリに要求 (キャッシュミス) a[0] a[1] a[2] a[3] b[0],…,b[3]が入る空きがない →古いデータ(例: c[0],…,c[3]) の追い出し b[0] b[1] b[2] b[3] 追い出し+データ同期 転送 サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₆₃

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

Case study: より現実的な簡易モデル (図4-5-1) 段数_{: 2}段 _{(2-way), キャッシュライン数: 2, 1段当たりの要素数: 8} 何故発生したか? 配列の要素数(8) = 1段当たりの要素数

→ a[i], b[i], c[i]: 同一キャッシュライン上で, 同一位置への配置を要求 → 段数は2のため, この要求は実現不可能

キャッシュスラッシングとは

(Thrashing) (

4-10

)

メモリ上データ要求の度に

, キャッシュ上データ追い出し (eviction)

キャッシュの

構造

と関連

キャッシュライン数

, 1段当たりの要素数:

2のベキ乗(が典型)

サンプルコード: thrashing

HPCプログラミングセミナー「チューニング技法入門: キャッシュチューニング (C版)」 ₆₄

４－５ストライドが

_{1でキャッシュミスが発生する例}

(キャッシュスラッシング)

キャッシュスラッシングとは

(Thrashing) (

4-10

)

スラッシングが発生し得る状況

:

(典型的には) 配列の要素数 = 2

n

[配列の要素数]=[キャッシュ1段当たりの要素数の整数倍]

→ 特定のキャッシュライン上のデータ配置が常に要求

キャッシュの

連想度

(associativity, 段数に対応) が小さい

場合

特に配慮が必要

(

著しい性能劣化の可能性

)

スラッシングの検出

*)

キャッシュミス率を取得可能なプロファイラが必要

スラッシングの回避

**)

パディング

(padding) (

4-12

), 配列マージなど (

4-13

)

*) 今村俊幸「キャッシュ性能安定性について」スーパーコンピューティングニュース Vol.9特集号 (2008) pp.111-121; http://www.cc.u-tokyo.ac.jp/support/press/news/VOL9/special/ **)サイエンティフィック・システム研究会「ポストペタアプリ性能WG 成果報告書 (別冊)」 (会員登録が必要); http://www.ssken.gr.jp/MAINSITE/download/wg_report/p-pap/index.html サンプルコード: thrashing