The 3 key challenges in programming for MC

Transcription

1 プロセッサー キャッシュ 最 適 化 技 法 インテル 株 式 会 社 ソフトウェア&ソリューションズ 統 括 部 ソフトウェア 製 品 部

2 はじめに L1キャッシュでのアクセスミスは 数 十 クロックのペナ ルティーが 生 じる L2キャッシュでのアクセスミスは 数 十 バスクロックの ペナルティーが 生 じる キャッシュを 有 効 利 用 するにはデータやコードの 位 置 関 係 が 重 要 となる しかしそれは... 他 の 最 適 化 技 術 に 影 響 を 及 ぼす 場 合 がある 2

3 キャッシュに 読 み 込 まれるタイミング 1. アプリケーションが 参 照 したメモリーの 内 容 がキャッシュにない 場 合 2. アプリケーションがメモリーに 書 き 込 みを 行 った 内 容 がキャッシュにない 場 合 3. アプリケーションがプリフェッチ 命 令 を 実 行 した 場 合 4. ハードウェア プリフェッチャーが 動 作 した 場 合 読 み 込 み 書 き 出 しの 最 小 単 位 はキャッシュライン(64バイト) 3

4 ハードウェア プリフェッチャー ハードウェアは 2 つの 方 法 でデータを 取 り 込 む ストライド プリフェッチ データ アクセス パターンを 基 にキャッシュラインのプリフェッチを 開 始 する いくつかのキャッシュラインを 取 得 する 通 常 のデータ アクセス パターンのときによいパフォーマンスが 得 られるようにする キャッシュライン 参 照 の 読 み 込 みミスがトリガーになる しきい 値 内 での 2 回 のキャッシュミスがトリガーになる 90 ナノ メートル テクノロジーのインテル Pentium 4 プロセッサーでは 512 バイト それ 以 前 のインテル Pentium 4 プロセッサーでは 256 バイト 次 のノードへの 距 離 をトリガーとなる 距 離 の 1/2 以 上 に 保 つ 隣 接 ライン プリフェッチ 128 バイトのフェッチで L2(L3)ミスを 考 慮 する キャッシュミスが 下 位 64 バイトで 起 こったなら 隣 接 する 上 位 64 バイトを 取 り 込 む キャッシュミスが 上 位 64 バイトで 起 こったなら 隣 接 する 下 位 64 バイトを 取 り 込 む キャッシュライン 参 照 の 読 み 込 みミスがトリガーになる 4

5 Intel NetBurst マイクロアーキテクチャー システムバス 頻 繁 に 使 用 されるパス それほど 頻 繁 に 使 用 されないパス クワッド パンプ 100MHz/333MHz 400MT/ 秒 = 3.2 GB/ 秒 最 大 1066MT/ 秒 = 8.5 GB/ 秒 バス インターフェイス ユニット L2 キャッシュ (1/2MB 8 ウエイ 128 バイト キャッシュ ライン) 108G バイト/ 秒 フェッチ/ デコード 64 ビット 幅 フロントエンド BTB 分 岐 予 測 L1 データキャッシュ (16KB 8 ウエイ 64 バイト キャッシュ ライン) 実 行 ユニット 256 ビット 幅 リタイアメント 5 トレースキャッシュ TC μコードrom BTB 命 令 プール (ROB)

6 インテル モバイル マイクロアーキテクチャー システムバス 頻 繁 に 使 用 されるパス それほど 頻 繁 に 使 用 されないパス クワッドパンプ 100MHz 400MT/ 秒 = 3.2 GB/ 秒 ( 最 大 533MT/ 秒 = 4.2 GB/ 秒 ) バス インターフェイス ユニット L2 キャッシュ (1MB 8ウエイ 128バイト キャッシュ ライン) L1 命 令 キャッシュ (32KB 8ウエイ ) フェッチ/ デコード 64ビット 幅 フロントエンド BTB 分 岐 予 測 実 行 ユニット L1 データキャッシュ (32KB 8ウエイ ) 256ビット 幅 リタイアメント μopのフュージョン 6 命 令 プール (ROB)

7 第 1 世 代 のデュアルコア プロセッサー Pentium D Pentium Extreme Edition システムバス バス インターフェイス ユニット L2 キャッシュ (1/2MB 8 ウエイ 128 バイト キャッシュ ライン) 108G バイト/ 秒 L2 キャッシュ (1/2MB 8 ウエイ 128 バイト キャッシュ ライン) 108G バイト/ 秒 L1 データキャッシュ (16KB 8 ウエイ 64 バイト キャッシュ ライン) L1 データキャッシュ (16KB 8 ウエイ 64 バイト キャッシュ ライン) 64 ビット 幅 256 ビット 幅 64 ビット 幅 256 ビット 幅 フェッチ/ デコード フロントエンド BTB 分 岐 予 測 実 行 ユニット リタイアメント フェッチ/ デコード フロントエンド BTB 分 岐 予 測 実 行 ユニット リタイアメント トレースキャッシュ TC μコードrom BTB トレースキャッシュ TC μコードrom BTB 命 令 プール (ROB) 命 令 プール (ROB) 7

8 インテル Core マイクロアーキテクチャー システムバス クワッド パンプ 166MHz/266MHz/333MHz 頻 繁 に 使 用 されるパス それほど 頻 繁 に 使 用 されないパス 667MT/ 秒 = 5.3 GB/ 秒 1066MT/ 秒 = 8.5GB/ 秒 1333MT/ 秒 = 10.6GB/ 秒 バス インターフェイス ユニット アドバンスド スマートL2 キャッシュ (2MB/4MB 8ウエイ 128バイト キャッシュ ライン) 256ビット 幅 256ビット 幅 L1 命 令 キャッシュ (32KB 8ウエイ ) L1 データキャッシュ (32KB 8ウエイ ) L1 命 令 キャッシュ (32KB 8ウエイ ) L1 データキャッシュ (32KB 8ウエイ ) 64ビット 幅 64ビット 幅 5 フロントエンド フェッチ/ BTB デコード 分 岐 予 測 実 行 ユニット(5つ) リタイアメント 5 フロントエンド フェッチ/ BTB デコード 分 岐 予 測 実 行 ユニット(5つ) リタイアメント マクロ オペレーションのフュージョン 4 マイクロ オペレーション(μOP)のフュージョン 4 マクロ オペレーションのフュージョン 4 マイクロ オペレーション(μOP)のフュージョン 4 命 令 プール (ROB) 命 令 プール (ROB) 8

9 インテル Core マイクロアーキテクチャー クアッドコア プロセッサー システムバス バス インターフェイス ユニット アドバンスド スマートL2 キャッシュ (2MB/4MB 8ウエイ 128バイト キャッシュ ライン) アドバンスド スマートL2 キャッシュ (2MB/4MB 8ウエイ 128バイト キャッシュ ライン) 256ビット 幅 256ビット 幅 256ビット 幅 256ビット 幅 L1 命 令 キャッシュ (32KB 8ウエイ ) L1 データキャッシュ (32KB 8ウエイ ) L1 命 令 キャッシュ (32KB 8ウエイ ) L1 データキャッシュ (32KB 8ウエイ ) L1 命 令 キャッシュ (32KB 8ウエイ ) L1 データキャッシュ (32KB 8ウエイ ) L1 命 令 キャッシュ (32KB 8ウエイ ) L1 データキャッシュ (32KB 8ウエイ ) 64ビット 幅 64ビット 幅 64ビット 幅 64ビット 幅 5 フロントエンド フェッチ/ BTB デコード 分 岐 予 測 実 行 ユニット(5つ) リタイアメント 5 フロントエンド フェッチ/ BTB デコード 分 岐 予 測 実 行 ユニット(5つ) リタイアメント 5 フロントエンド フェッチ/ BTB デコード 分 岐 予 測 実 行 ユニット(5つ) リタイアメント 5 フロントエンド フェッチ/ BTB デコード 分 岐 予 測 実 行 ユニット(5つ) リタイアメント マクロ オペレーションのフュージョン 4 マイクロ オペレーション(μOP)のフュージョン 4 マクロ オペレーションのフュージョン 4 マイクロ オペレーション(μOP)のフュージョン 4 マクロ オペレーションのフュージョン 4 マイクロ オペレーション(μOP)のフュージョン 4 マクロ オペレーションのフュージョン 4 マイクロ オペレーション(μOP)のフュージョン 4 命 令 プール (ROB) 命 令 プール (ROB) 命 令 プール (ROB) 命 令 プール (ROB) 9

10 スマート メモリー アクセス システムバス L1 データ キャッシュ コア1 スマート 共 有 L2 キャッシュ L1 データ キャッシュ コア2 時 間 の 局 所 性 空 間 の 局 所 性 データを 可 能 な 限 り 早 く 利 用 できるようにする データが 可 能 な 限 り 近 くにあるようにする メモリー サブシステムのレイテンシーを を 隠 蔽 10

11 プリフェッチャーとマルチコア マイクロ コード ROM 命 令 フェッチ およびプリデコード 命 令 キュー デコード リネーム/ 割 り 当 て リタイアメント ユニット (リオーダーバッファー リオーダーバッファー) 5 4 スケジューラー 4 2M/4M 共 有 L2 キャッシュ 最 大 10.6GB/ 秒 のFSB 命 令 フェッチ およびプリデコード 命 令 キュー デコード リネーム/ 割 り 当 て スケジューラー マイクロ コード ROM リタイアメント ユニット (リオーダーバッファー リオーダーバッファー) ALU 分 岐 MMX/SSE FPmove ALU FAdd MMX/SSE FPmove ALU FMul MMX/SSE FPmove ロード ストア ストア ロード ALU FMul MMX/SSE FPmove ALU FAdd MMX/SSE FPmove ALU 分 岐 MMX/SSE FPmove L1 データキャッシュと D-TLB L1 データキャッシュと D-TLB 11 動 的 に 共 有 される 2 つの L2 プリフェッチャー

12 アドバンスト スマート キャッシュ マルチコアに 最 適 化 コア1 コア2 L2 キャッシュ スマートキャッシュの 利 点 L2 が 各 コアの 負 荷 に 適 応 できる 高 速 データ 共 有 複 製 データがない 追 加 の 利 点 L1 キャッシュに 対 する 2 倍 の 帯 域 幅 マルチコアに 最 適 化 された 共 有 キャッシュ2 倍 の 帯 域 幅 12

13 アドバンスト スマート キャッシュ ダイナミック キャッシュ アロケーション アドバンスト スマート キャッシュ 独 立 キャッシュ コア1 コア2 コア1 コア2 L2 キャッシュ L2 L2 キャッシュ キャッシュ 共 有 キャッシュは2つのコアからの 不 均 衡 な 負 荷 に 適 応 しかし 独 立 キャッシュは 一 方 のキャッシュの 使 用 率 が 低 く キャッシュが 空 いていても もう 一 方 の 高 負 荷 のアプリケ ーションはその 空 きキャッシュを 利 用 できずパフォーマンス 向 上 が 見 込 めない 13

14 アドバンスト スマート キャッシュ 効 率 的 なデータ 共 有 アドバンスト スマート キャッシュ 独 立 キャッシュ コア1 コア2 コア1 コア2 L2 キャッシュ FSB チップセット MCH L2 キャッシュ L2 キャッシュ FSB チップセット MCH 14 L2 から L1 への 2 倍 の 帯 域 幅

15 空 間 の 局 所 性 と 時 間 の 局 所 性 アクセスされたデータに 隣 接 するデータは 近 い 将 来 参 照 される 可 能 性 が 高 い アクセスされたデータは 近 い 将 来 再 びアクセスされる 可 能 性 が 高 い 15

16 キャッシュの 構 成 容 量 ( C ) ラインサイズ ( B ) アソシアティビティ ( A ) いくつかの 不 特 定 なメモリーの 内 容 がキャッシュの 特 定 の ブロックに 割 り 当 てられる A = 1 A = C / B 1< A < (C / B) ダイレクトマッピング フルアソシアティビティー セット アソシアティビティー 16

17 メモリー 中 のスキップを 避 ける メモリー スキップするアクセスはパフォーマンスを 低 下 させる IA-32 / インテル 64 プロセッサーのハードウェア プリフェッチャーは メモリー 中 のスキップを 認 識 しない TLB のエントリーには 限 りがある 各 アクセスにつき 1 つのキャッシュ ラインが 入 出 力 される キャッシュに 未 使 用 データが 含 まれる 未 使 用 データのためにより 多 くの 帯 域 が 必 要 ユニット ストライドされないアクセスのため 効 率 的 にベクトル 化 されない 17

18 スキップの 例 特 定 のスキップ for (i = 0; i < MAX; i += 10) A[i]; 外 部 次 元 中 のループ for (i = 0; i < MAX; i++) A[i][1]; ループ 構 造 の 1 つの 要 素 のみにアクセス Struct Person[100] { int ID; char[50] Name; char[100] address; } for (i = 0; i < 100; i++) if (Person[i].ID=match) matchid = i; 18

19 2 n の 法 則 さまざまなアーキテクチャーの 特 性 は 2 n 離 れた アドレスで 明 示 される 大 きな 幅 の 2 n (キャッシュ ラインよりも 大 きい 場 合 )は キャッシュ アクセスを 招 く セット アソシアティブ( 連 想 方 式 ) キャッシュ キャッシュ 管 理 大 きな 幅 の 2 n のスキップは 大 きなパフォーマン ス 低 下 につながる! 2 n の 境 界 (2K 4K 16K...256K)でメモリー スキップを 行 うと キャッシュ 入 れ 替 えの 原 因 となる 正 確 なサイズはプロセッサーとキャッシュ 構 成 によって 異 なる 19

20 8ウェイ セット アソシアティブの 場 合 バイト 8ウェイ set0 set1 set2 set3 set4 set5 set KB set30 set31 20 タグブロック 64バイト データブロック

21 キャッシュ アクセス ミスとは 初 期 参 照 ミス 容 量 ミス 競 合 ミス キャッシュ 競 合 なし 競 合 A B A B メモリー メモリー 21

22 キャッシュ アクセス ミスを 減 らす 最 適 化 技 術 配 列 のマージ パディングとアライメント パッキング 書 き 込 み 前 の 読 み 込 み ループインターチェンジ ループフュージョン ブロッキング コードサイズの 削 除 struct { int A[ ]; int B[ ]; } for(){ } 22

23 ローカリティーを 増 やす コードとデータサイズを 減 らす 23

24 SoA( 配 列 構 造 体 )とAoS( 構 造 体 配 列 ) Loop Loop s.a[i] s.b[i] Loop s[i].a s[i].b struct { int a[size]; int b[size]; } s; struct { int a; int b; } s[size] 24

25 SoA( 配 列 構 造 体 )とAoS( 構 造 体 配 列 ) struct { int a[size]; int b[size]; } s; a a a a a a a a b b b b b b b b Loop s[i].a s[i].b Loop struct { int a; int b; } s[size] a a b b a a b b a a b b a a b b s.a[i] Loop s.b[i] 25

26 パディング struct { int val[15]; } struct { int val[15]; int pad; } コンパイラーによって 自 動 的 にアライメントされないデータ 構 造 を 考 える 26

27 64 バイト (1キャッシュライン) struct { int val[15]; } s [SIZE] struct { int val[15]; int Pad; } s [SIZE] pad pad pad pad もしくは _declspec (align (16)) struct { int val[15]; } s [SIZE] 27

28 自 然 なアライメントと SIMD アライメント C 言 語 の 仕 様 では 構 造 体 と 配 列 内 のデータは 宣 言 したデータ 要 素 が 自 然 なサイズになるようにアライメントされる 他 の 方 法 (パッキング)を 指 定 した 場 合 を 除 く 標 準 コードのメモリーアクセスをスピードアップ C 言 語 では SSE のパフォーマンスを 上 げる SIMD アライメント (16 バイト)は 強 要 しない 例 : float A[100] 16 バイトアドレスでアライメントする 必 要 はない 高 速 な SIMD movapd 命 令 は 使 用 できない インテル コンパイラーは 16/32 バイト 境 界 でアライメントしようとする 28

29 コンパイラーの 支 援 : データのアライメント(1) declspec(align(16)) float B[MAX]; void funca(float * B) { assume_aligned(b,16); A=_mm_malloc(sizeof(float) * MAX,16); for (i = 0; i < MAX; i++) A[i] += B[i]; _mm_free(a); } 29

30 コンパイラーの 支 援 : データのアライメント(2) _declspec(align(16)) float B[MAX]; void funca(float * B[]) { A=_mm_malloc(sizeof(float)*MAX,16); #pragma vector aligned for ( i = 0 ; i < MAX; i++) A[i] += B[i]; _mm_free(a); } 30

31 アライメント 用 のコンパイラー 組 み 込 み 関 数 declspec(align(base, [offset])) 境 界 からのオフセット offset (バイト 単 位 デフォルトは 0)で base バイト 境 界 でアライメントされる 変 数 を 作 成 する void* _mm_malloc (int size, int n) n バイト 境 界 でアライメントされるメモリーへのポインターを 作 成 する #pragma vector aligned unaligned ベクトルアクセスにアライメントされている またはアライメントされていないロード およびストアーを 使 用 する assume_aligned(a,n) 配 列 "a" が "n" バイト 境 界 でアライメントされると 仮 定 する 31

32 構 造 体 メンバーの 再 配 置 struct unix_proc { struct proc *next; struct proc *back;... int pid;... int prio; int nice;... char uid; } struct unix_proc { struct proc *next; int pid; int prio; struct proc *back; int nice;... char uid; } 32

33 キャッシュ ラインの 分 割 定 義 : データ 要 素 がキャッシュ 境 界 をまたぐこと 影 響 : そのデータ 要 素 にアクセスするには 1 回 ではなく 2 回 のメモリーアクセ スが 必 要 になるため パフォーマンスが 低 下 する インテル Pentium 4 プロセッサーのキャッシュ ラインは 64 バイト SSE3 では キャッシュ ラインの 分 割 問 題 を 解 消 するために 新 しい lddqu 命 令 を 追 加 アドレス 029e70c1h アドレス 029e70feh キャッシュ ライン 029e70c0h キャッシュ ライン 029e7100h Index 0 Index 0( 続 き) Index 1 Index 15 Index 16 33

34 ソフトウェア プリフェッチーの 追 加 メカニズム void _mm_prefetch(char const*a, int sel) (PREFETCH を 使 用 ) 指 定 されたアドレスからプロセッサーに 近 い キャッシュ 階 層 にデータのキャッシュ ラインをロ ードする 値 のセットは プリフェッチ 命 令 のタイプを 指 定 する プリフェッチ 命 令 のタイプに 合 わ せて 次 の 定 数 を 選 択 する: _MM_HINT_T0 _MM_HINT_T1 _MM_HINT_T2 _MM_HINT_NTA 使 用 方 法 インテル Pentium 4 プロセッサーのアーキテクチャーでは CPU コアのリソース を 要 求 しないでハードウェア プリフェッチを 行 うことができるため ソフトウェア プリフ ェッチは 通 常 意 味 がない 細 心 の 注 意 を 払 って 試 す メモリーをランダムにアクセスするコードには 有 効 34

35 ストリーミング ストアー #pragma vector nontemporal for (i = 0; i < N; i++) a[i] = 1; 定 義 : キャッシュ 中 にデータを 置 かないストアーのこと ループ 回 数 が 大 きなループのパフォーマンスを 著 しく 向 上 注 : a[i] は 終 了 時 にキャッシュ 中 に 存 在 しないため 通 常 は a[i] に 格 納 され たデータをすぐに 使 用 しない 35

36 データ アクセス パターンの 理 想 しきい 値 距 離 内 のデータをアクセスすることで ハードウェア ストライド プリフェッチャーは 連 続 してアクセスできる L2(L3)のヒットレートを 向 上 させる 128 バイト 以 内 に 分 散 したデータを 利 用 することで 隣 接 ライ ン プリフェッチャーの 恩 恵 を 受 けられる 4K 以 内 にデータアクセスを 集 中 することで 過 剰 なページン グを 防 止 する 36

37 実 行 コードによるキャッシュ アクセス 最 適 化 37

38 ループインターチェンジ for ( j = 0; j < 100; j++ ) for ( i = 0; i < 100; i++ ) a[i][j] = 2 * a[i][j]; for ( i = 0; i < 100; i++ ) for ( j = 0; j < 100; j++ ) a[i][j] = 2 * a[i][j]; 38 3,1 2,1 1,1 1,2 1,3... 1,100 3,1 2,1 1,1 1,2 1,3... 1, ,1 100,1

39 ループフュージョン ループフュージョン 実 行 前 ; for ( i = 0; i < N; i++ ) for ( j = 0; j < N; j++ ) a[i][j] = b[i][j] * c[i][j]; for ( i = 0; i < N; i++ ) for ( j = 0; j < N; j++ ) d[i][j] = a[i][j] + c[i][j]; ループフュージョン 実 行 後 ; for ( i = 0; i < N; i++ ) for ( j = 0; j < N; j++ ) { a[i][j] = b[i][j] * c[i][j]; d[i][j] = a[i][j] + c[i][j]; } 39

40 ループアンロール for ( j = 0; j < M; j++) for ( k = 0; k < N; k++ ) for ( i = 0; i < L; i++ ) C[k][i]+=A[k][j] * B[j][i]; for ( j = 0; j < M; j += 4 ) for ( k = 0; k < N; k++ ) for ( i = 0; i < L; i++ ) C[k][i]+=A[k][j] * B[j][i] + A[k][j+1] * B[j+1][i] + A[k][j+2] * B[j+2][i] + A[k][j+3] * B[j+3][i]; 40

41 ストリップマイニング ストリップマイニング(ループセクション)はキャッシュを 効 率 良 く 使 用 するためのループ 変 換 手 法 であり 大 きなループを 小 さな ループに 分 割 することで データキャッシュの 時 間 および 空 間 の 局 所 性 を 高 める strip_mine(){ struct _vertex{ float x, y, z, nx, ny, nz, u, v; } v[num]; } for(i=0; i<num; i++){ transform(&v[i]); Lighting(&v[i]); } for(i=0; i<num; i+=sm){ for(j=i; j < min(num, i*sm); j++){ transform(&v[j]); Lighting(&v[j]); } } 41

42 ブロッキング float A[MAX, MAX], B[MAX, MAX]; for(i=0, i<max, i++){ for(j=0, j<max, j++){ A[ i ][ j ] = A[ i ][ j ] + B[ j ][ i ]; } } 配 列 AとBはシーケンシャルにアクセス されるが 配 列 Bはアクセスするたびに キャッシュミスが 発 生 し キャッシュの 再 利 用 がまったく 考 慮 されていない float A[MAX, MAX], B[MAX, MAX]; for(i=0, i<max, i+=blocksize){ for(j=0; j<n; j+= blocksize){ for(ii=i; ii<i+blocksize; ii++){ for(jj=j; j<j+blocksize; jj++){ A[ii][jj] = A[ii][jj] + B[jj][ii]; 42 配 列 AとBをキャッシュサイズに 収 ま るように 断 片 的 にアクセスすること により 配 列 Bのキャッシュミスを 減 らす Blocksizeを8にすると 各 配 列 がブロッキングされる 断 片 は8キ ャッシュラインとなる

43 A(i,j)のアクセスパターン j キャッシュサイズより 小 さい i B(i,j)のアクセスパターン + 43

44 オルタ-ネイトル-プ void matrix(n){ double a[100][100],b[100][100],c[100][100]; int i,j,k; } for(i=0; i < n; j++){ for(j=0; j < n; j++){ for(k=0; k < n; k++) a[i][j] = a[i][j] + b[i][k] * c[k][j]; } } if(n > itval){ ル-プの 回 数 が 不 定 で あるため,ブロッキング 等 ができない ブロッキング 化 したコ-ド ル-プのコピ-を 作 り,ル-プの 回 数 がトランスフォ-メ-ションを 行 なうのに 十 分 な 大 きさがあれば, 最 適 化 したコ-ドを 実 行 する 44 } else { for(i=0; i < n; j++){ for(j=0; j < n; j++){ for(k=0; k < n; k++) a[i][j] = a[i][j] + b[i][k] * c[k][j]; } } }

45 コードサイズを 減 らす(アセンブリー) 複 数 サイクル 命 令 を 使 用 する アドレス 生 成 時 にインデックス オフセット そしてスケールを 使 用 する 短 いオペコードを 使 用 する +/-128 以 下 の 即 値 mov eax, 0 の 変 わりに xor eax, eax を 使 用 レジスターはなるべく eax を 使 用 45

46 まとめ コード/データアクセスのローカリティー 向 上 コード/データサイズを 減 らす キャッシュの 性 能 を 監 視 する: キャッシュの 使 用 率 のプロファイル ホットスポットの 検 索 アクセスミスのタイプ 割 り 出 し 適 切 な 方 法 で 最 適 化 46

47 参 考 資 料 47

48 プリフェッチ 命 令 プリフェッチ 命 令 はデータの 参 照 に 先 行 してデータをフェッチすることにより アプリケーション コードのパフォーマンス クリティカルな 部 分 でのメモリー アクセス 遅 延 を 隠 すことができる 非 一 時 命 令 prefetchnta 一 時 命 令 prefetcht0 prefetcht1 prefetcht2 L0へ 読 み 込 み(L1) すべてのレベルのキャッシュへ 読 み 込 み L0を 除 くキャッシュへ 読 み 込 み(L2) L0,L1を 除 くキャッシュ(L2)へ 読 み 込 み 48

49 メモリーアクセスによる 遅 延 とプリフェッチ 時 間 実 行 パイプライン フロントサイドバス 実 行 ユニット のアイドル 時 間 ロード 命 令 メモリーの 遅 延 実 行 ユニット のアイドル 時 間 ロード 命 令 メモリーの 遅 延 FSBのアイドル 時 間 実 行 パイプライン 時 間 フロントサイドバス 49

50 プリフェッチ 命 令 による メモリーアクセスの 最 適 化 プリフェッチを 実 行 する 間 隔 プリフェッチの 連 結 プリフェッチの 最 小 化 プリフェッチの 分 散 キャッシュのブロッキング メモリーバンクのアクセス 競 合 キャッシュ 管 理 50

51 プリフェッチを 実 行 する 間 隔 プリフェッチ 命 令 を 有 効 に 使 用 するには 適 切 な 実 行 間 隔 が 設 定 されなけ ればいけない 間 隔 が 狭 すぎると プリフェッチの 時 間 を 他 の 演 算 実 行 サイクルで 隠 すことができず 間 隔 が 広 すぎるとプリフェッチしたデータが キャッシュに 無 い 可 能 性 がある i i+1 i+2 i+3 小 さくてタイトなループはプリ フェッチの 恩 恵 を 受 けそうに 見 えるが 実 際 にはそうでは ない 51

52 プリフェッチ 間 隔 (PSD) Psd = Nlookup + Nxfer (N pref +N st ) CPI N inst Psd Nlookup Nxfer NprefとNst Ninst プリフェッチのスケジュール 間 隔 ルックアップレイテンシークロック メモリーやチップセットに 依 存 キャッシュラインの 転 送 に 要 するクロック プリフェッチとストアーされるキャッシュライン 数 1 回 のループの 命 令 数 Psd = (N pref +N st ) 1.5 N inst 52

53 プリフェッチの 連 結 ネストしたループでは 内 側 のループが 終 了 し 外 側 のループ 処 理 が 始 まるまでにパイプラインが 途 切 れる 可 能 性 がある for (ii=0; ii=100; ii++){ for(jj=0; jj<32; jj+=8){ prefetch a[ii][jj+8]; computation a[ii][jj]; } } この 例 では a[ii][0]を 含 むキャッシュラインがプリフェッチされて おらず 内 側 のループの 最 後 で 不 要 なプリフェッチが 行 われる 53

54 プリフェッチの 連 結 (2) プリフェッチの 連 結 は 内 側 と 外 側 の 実 行 パイプラインを 繋 ぐブリッジの 役 目 をはたす 内 側 のループの 繰 り 返 しを ループ 外 で 次 のループで 使 用 す るデータのプリフェッチと 共 に 行 うことで メモリーパイプラインの 途 切 れに よる 性 能 低 下 を 回 避 する for (ii=0; ii=100; ii++){ for(jj=0; jj<24; jj+=8){ prefetch a[ii][jj+8]; computation a[ii][jj]; } prefetch a[ii+1][0]; computation a[ii][jj]; } 54

55 プリフェッチの 最 小 化 過 度 なプリフェッチは 次 のような 問 題 を 招 く フィル バッファーに 空 きが 無 い 場 合 フィル バッファー エントリーの 割 り 当 て 待 ちでプリフェッチがロードバッファー 内 に 蓄 積 する ロードバッファーに 空 きが 無 いと 命 令 の 割 り 当 てがストールする 対 象 ループが 小 さな 場 合 プリフェッチによってオーバーヘッドが 増 大 する 55 Loop: prefetchnta [edx+esi+32] prefetchnta [edx*4+esi+32] movaps xmm1,[edx+esi] movaps xmm2,[edx*4+esi] add esi,16 cmp esi,ecx jl Loop Loop: prefetchnta [edx+esi+32] prefetchnta [edx*4+esi+32] movaps xmm1,[edx+esi] movaps xmm2,[edx*4+esi] movaps xmm1,[edx+esi+16] movaps xmm2,[edx*4+esi+16] add esi,32 cmp esi,ecx jl Loop

56 プリフェッチの 分 散 すべてのプリフェッチをループのはじめに 実 行 すると 大 幅 な 性 能 低 下 につながる 可 能 性 がある プリフェッチは 他 の 演 算 と 交 互 に 配 置 する PentiumIIIプロセッサー(500MHz)では 20-25サイクル 毎 にプリフェッチ 命 令 を 挿 入 する Loop: prefetchnta [ebx+128] prefetchnta [ebx+1128] prefetchnta [ebx+2128] prefetchnta [ebx+3128] prefetchnta [ebx+17128] prefetchnta [ebx+18128] prefetchnta [ebx+19128] prefetchnta [ebx+20128] mulps xmm3,[ebx+4000] addps xmm1,[ebx+1000] addps xmm2,[ebx+3016] mulps xmm3,[ebx+2000] mulps xmm1,xmm2 add ebx,32 cmp ebx,ecx jl Loop 56

57 ビデオデコーダにおけるキャッシュ 管 理 ここでのビデオデコーダでは 処 理 済 のフレームデータをビデオメモリー へ 書 き 込 み その 後 データのコピーがプロセッサーによってライトバックメ モリーに 格 納 され 以 降 のデータ 生 成 に 利 用 されることを 前 提 とする データはストリーミング ストアー 命 令 でビデオメモリーへ 直 接 書 き 込 むこと により プロセッサーキャッシュの 汚 染 を 防 止 する その 後 プロセッサーは prefetchnta 再 読 み 込 みされるため 使 用 可 能 なバンド 幅 は 最 大 とな る NTA( 非 一 時 ) 読 み 込 みを 行 うことで キャッシュ 内 の 他 のデータへの 影 響 を 最 小 限 に 押 さえる MOVNTQ m64, mm MOVNTPS m128, xmm Pentium 4 L1 regs bsb L2 fsb グラフィック コントローラー AGP チップセット システム メモリー 57

58 本 資 料 に 掲 載 されている 情 報 は インテル 製 品 の 概 要 説 明 を 目 的 としたものです 製 品 に 付 属 の 売 買 契 約 書 Intel s Terms and conditions of Sales に 規 定 され ている 場 合 を 除 き インテルはいかなる 責 を 負 うものではなく またインテル 製 品 の 販 売 や 使 用 に 関 する 明 示 または 黙 示 の 保 証 ( 特 定 目 的 への 適 合 性 商 品 性 に 関 する 保 証 第 三 者 の 特 許 権 著 作 権 その 他 知 的 所 有 権 を 侵 害 していない ことへの 保 証 を 含 む) に 関 しても 一 切 責 任 を 負 わないものとします インテル 製 品 は 予 告 なく 仕 様 が 変 更 されることがあります * その 他 の 社 名 製 品 名 などは 一 般 に 各 社 の 商 標 または 登 録 商 標 です 2007, Intel Corporation. 58