HN 日本語サマリー

← 一覧へ戻る
科学・技術

プロセッサキャッシュ効果のギャラリー

Gallery of Processor Cache Effects (igoro.com)

40 pointsby porridgeraisin4 コメント

要約

この記事は、プロセッサキャッシュがプログラムのパフォーマンスに与える影響を視覚的に解説するギャラリーです。キャッシュの動作原理や、それがデータアクセス速度にどのように影響するかをデモンストレーションを通じて示しています。

全文翻訳

プロセッサキャッシュの効果ギャラリー

私の読者の多くは、キャッシュが高速だが小容量のメモリで、最近アクセスされたメモリ位置を格納することを理解しているでしょう。この説明は概ね正確ですが、プロセッサキャッシュがどのように機能するかの「退屈な」詳細は、プログラムのパフォーマンスを理解する上で大いに役立ちます。

この記事では、コードサンプルを使用して、キャッシュがどのように機能するか、そしてそれが実際のプログラムのパフォーマンスにどのような影響を与えるかの様々な側面を説明します。

例はC#ですが、言語の選択はパフォーマンススコアやそこから導かれる結論にほとんど影響を与えません。

例1: メモリアクセスとパフォーマンス

ループ2はループ1と比較して、どれくらい速く実行されると期待しますか?

int[] arr = new int[64 * 1024 * 1024];

// ループ1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// ループ2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

最初のループは配列のすべての値を3倍し、2番目のループは16番目の値だけを3倍します。2番目のループは最初のループの仕事量の約6%しか行いませんが、最新のマシンでは、2つのforループはほぼ同じ時間で完了します。私のマシンでは、それぞれ80msと78msです。

ループが同じ時間を要する理由はメモリにあります。これらのループの実行時間は、整数乗算ではなく、配列へのメモリアクセスによって支配されます。そして、例2で説明するように、ハードウェアは2つのループで同じメインメモリアクセスを実行します。

例2: キャッシュラインの影響

この例をさらに掘り下げてみましょう。1と16だけでなく、他のステップ値も試します。

for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;

ここでは、異なるステップ値(K)に対するこのループの実行時間を示します。

[画像: image]

ステップが1から16の範囲内では、forループの実行時間はほとんど変化しません。しかし、16以降では、ステップを2倍にするたびに実行時間が半分になります。

この背後にある理由は、今日のCPUはバイト単位でメモリにアクセスしないことです。代わりに、それらは(通常)64バイトのチャンク、いわゆるキャッシュラインでメモリを取得します。特定のメモリ位置を読み取ると、キャッシュライン全体がメインメモリからキャッシュにフェッチされます。そして、同じキャッシュラインの他の値へのアクセスは安価です!

16個のintは64バイト(1つのキャッシュライン)を占めるため、ステップが1から16のforループは同じ数のキャッシュライン、つまり配列内のすべてのキャッシュラインに触れる必要があります。しかし、ステップが32になると、約2つおきのキャッシュラインにしか触れず、64になると、4つおきにしか触れません。

キャッシュラインの理解は、特定の種類のプログラム最適化において重要になることがあります。例えば、データの配置(アライメント)は、操作が1つまたは2つのキャッシュラインに触れるかどうかを決定する可能性があります。上記の例で見たように、これは誤った配置の場合、操作が2倍遅くなることを容易に意味します。

例3: L1およびL2キャッシュサイズ

今日のコンピュータには、通常L1、L2、そして場合によってはL3と呼ばれる2つまたは3つのレベルのキャッシュが搭載されています。異なるキャッシュのサイズを知りたい場合は、CoreInfo SysInternalsツールを使用するか、GetLogicalProcessorInfo Windows API呼び出しを使用できます。どちらの方法でも、キャッシュサイズに加えてキャッシュラインサイズもわかります。

私のマシンでは、CoreInfoは32kBのL1データキャッシュ、32kBのL1命令キャッシュ、および4MBのL2データキャッシュがあると報告しています。L1キャッシュはコアごとであり、L2キャッシュはコアのペア間で共有されています。

Logical Processor to Cache Map:
*---  Data Cache          0, Level 1,   32 KB, Assoc   8, LineSize  64
*---  Instruction Cache   0, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Data Cache          1, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Instruction Cache   1, Level 1,   32 KB, Assoc   8, LineSize  64
**--  Unified Cache       0, Level 2,    4 MB, Assoc  16, LineSize  64
--*-  Data Cache          2, Level 1,   32 KB, Assoc   8, LineSize  64
--*-  Instruction Cache   2, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Data Cache          3, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Instruction Cache   3, Level 1,   32 KB, Assoc   8, LineSize  64
--**  Unified Cache       1, Level 2,    4 MB, Assoc  16, LineSize  64

実験によってこれらの数値を検証しましょう。そのためには、配列をステップオーバーし、16番目の整数ごとにインクリメントします。これは各キャッシュラインを変更する簡単な方法です。最後の値に達したら、先頭に戻ります。異なる配列サイズで実験し、配列が1つのキャッシュレベルからあふれるサイズでパフォーマンスの低下が見られるはずです。

プログラムは次のとおりです。

int steps = 64 * 1024 * 1024; // 任意回数のステップ
int lengthMod = arr.Length - 1;
for (int i = 0; i < steps; i++)
{
    arr[(i * 16) & lengthMod]++; // (x & lengthMod) は (x % arr.Length) と等価です
}

そして、タイミングは次のとおりです。

[画像: image]

32kBと4MB(私のマシンでのL1とL2キャッシュのサイズ)の後に、明確な低下が見られます。

例4: 命令レベル並列性

次に、異なるものを見てみましょう。これら2つのループのうち、どちらが速いと期待しますか?

int steps = 256 * 1024 * 1024;
int[] a = new int[2];

// ループ1
for (int i=0; i<steps; i++) { a[0]++; a[0]++; }

// ループ2
for (int i=0; i<steps; i++) { a[0]++; a[1]++; }

少なくとも私がテストしたすべてのマシンでは、2番目のループは最初のループの約2倍速いことが判明しました。なぜでしょうか?これは、2つのループ本体内の操作間の依存関係に関係しています。

最初のループの本体では、操作は次のように互いに依存しています。

[画像: image]

しかし、2番目の例では、これらの依存関係しかありません。

[画像: image]

現代のプロセッサには、わずかな並列性を持つ様々な部分があります。例えば、L1で同時に2つのメモリ位置にアクセスしたり、2つの単純な算術演算を実行したりできます。最初のループでは、プロセッサはこの命令レベル並列性を活用できませんが、2番目のループでは可能です。

[更新]: Redditの多くの人がコンパイラ最適化について、そして { a[0]++; a[0]++; } が { a[0]+=2; } に最適化されるのではないかと尋ねています。実際、C#コンパイラとCLR JITは、配列アクセスが関与する場合、この最適化を行いません。私はすべてのテストをリリースモード(つまり最適化あり)でビルドしましたが、最適化が結果を歪めていないことを確認するためにJITコンパイルされたアセンブリを確認しました。

例5: キャッシュアソシアティビティ

キャッシュ設計における重要な決定事項の1つは、メインメモリの各チャンクが任意のキャッシュスロットに格納できるか、それとも一部のスロットにしか格納できないかということです。

キャッシュスロットをメモリチャンクにマッピングするには、3つの可能なアプローチがあります。

  1. ダイレクトマップドキャッシュ
    各メモリチャンクは、キャッシュ内の1つの特定の場所にのみ格納できます。簡単な解決策は、インデックス chunk_index のチャンクをキャッシュスロット (chunk_index % cache_slots) にマッピングすることです。同じスロットにマッピングされる2つのメモリチャンクは、同時にキャッシュに格納できません。
  2. N-wayセットアソシアティブキャッシュ
    各メモリチャンクは、キャッシュ内のN個の特定のスロットのいずれかに格納できます。例えば、16-wayキャッシュでは、各メモリチャンクは16個の異なるキャッシュスロットに格納できます。一般的に、インデックスの最下位ビットが同じチャンクはすべて16個のスロットを共有します。
  3. フルアソシアティブキャッシュ
    各メモリチャンクは、キャッシュ内の任意のスロットに格納できます。実質的に、キャッシュはハッシュテーブルのように機能します。

ダイレクトマップドキャッシュは競合に悩まされる可能性があります。複数の値がキャッシュ内の同じスロットを競合すると、それらは互いに追い出し続け、ヒット率は急落します。一方、フルアソシアティブキャッシュはハードウェアで実装するのが複雑でコストがかかります。N-wayセットアソシアティブキャッシュは、実装の単純さと良好なヒット率の間の良いトレードオフを作るため、プロセッサキャッシュの一般的なソリューションです。

例えば、私のマシン上の4MB L2キャッシュは16-wayアソシアティブです。すべての64バイトメモリチャンクはセットにパーティション化され(チャンクインデックスの最下位ビットに基づく)、同じセット内のチャンクはL2キャッシュの16個のスロットを競合します。

L2キャッシュには65,536個のスロットがあり、各セットはキャッシュに16個のスロットを必要とするため、4,096個のセットが存在します。したがって、チャンクインデックスの最下位12ビットがチャンクが属するセットを決定します(2^12 = 4,096)。結果として、アドレスが262,144バイト(4096 * 64)の倍数で異なるキャッシュラインは、キャッシュ内の同じスロットを競合します。私のマシン上のキャッシュは、最大でそのようなキャッシュラインを16個保持できます。

キャッシュアソシアティビティの効果を顕著にするには、同じセットから16個を超える要素に繰り返しアクセスする必要があります。私は次の方法でこれを実証します。

public static long UpdateEveryKthByte(byte[] arr, int K)
{
    Stopwatch sw = Stopwatch.StartNew();
    const int rep = 1024*1024; // 反復回数 – 任意

    int p = 0;
    for (int i = 0; i < rep; i++)
    {
        arr[p]++;
        p += K;
        if (p >= arr.Length) p = 0;
    }

    sw.Stop();
    return sw.ElapsedMilliseconds;
}

このメソッドは、配列のK番目のバイトごとに値をインクリメントします。配列の終わりに達したら、最初からやり直します。十分に長く実行した後(2^20ステップ)、ループは停止します。

異なる配列サイズ(1MB単位)と異なるステップサイズで UpdateEveryKthByte() を実行しました。ここでは、結果のプロットを示します。青は実行時間が長く、白は短いことを表します。

[画像: image]

青い領域(実行時間が長い)は、更新された値がキャッシュ内に同時に保持できなかったケースです。明るい青い領域は実行時間約80ms、ほぼ白い領域は約10msに対応します。

チャートの青い部分を説明しましょう。

  1. なぜ縦線があるのか?
    縦線は、同じセットから多すぎるメモリ位置(>16)に触れるステップ値を示しています。これらのステップでは、16-wayアソシアティブキャッシュに触れたすべての値を同時に保持することはできません。
    悪いステップ値には2のべき乗(256や512)があります。例として、8MBの配列でステップ512を考えます。8MBのキャッシュラインには、262,144バイト間隔の値が32個含まれています。512は262,144で割り切れるため、ループの各パスでこれらの値すべてが更新されます。
    そして、32 > 16 なので、これらの32個の値はキャッシュの同じ16個のスロットを競合し続けます。
    2のべき乗ではない値の中には、単に不運なものがあり、同じセットから不釣り合いに多くの値にアクセスすることになります。そのようなステップ値も青い線として表示されます。

  2. なぜ縦線は4MBの配列長で止まるのか?
    4MB以下の配列では、16-wayアソシアティブキャッシュはフルアソシアティブキャッシュと同じくらい優れています。
    16-wayアソシアティブキャッシュは、262,144バイト間隔のキャッシュラインを最大16個保持できます。4MB以内に262,144バイト間隔で17個以上のキャッシュラインを持つセットは存在しません。なぜなら、16 * 262,144 = 4,194,304だからです。

  3. なぜ左上に青い三角形があるのか?
    三角形の領域では、キャッシュサイズ制限のために、必要なデータをすべてキャッシュに同時に保持できません。
    例えば、配列長16MB、ステップ128を考えます。配列の128バイトごとに更新しているということは、64バイトメモリチャンクを2つおきに触れていることになります。16MB配列の2つおきのキャッシュラインを格納するには、8MBのキャッシュが必要です。しかし、私のマシンには4MBのキャッシュしかありません。
    たとえ私のマシン上の4MBキャッシュがフルアソシアティブであったとしても、8MBのデータを保持することはできませんでした。

  4. なぜ三角形が左側で薄れていくのか?
    勾配が0から64バイト、つまり1つのキャッシュラインに変化していることに注意してください!例1と例2で説明したように、同じキャッシュラインへの追加アクセスはほぼ無料です。例えば、16バイトでステップする場合、次のキャッシュラインに到達するには4回のステップが必要です。そのため、1回の価格で4回のメモリアクセスが得られます。
    ステップ数はすべてのケースで同じなので、ステップが安いほど実行時間は短くなります。

これらのパターンは、チャートを拡張しても引き続き有効です。

[[画像: assoc_big]]

キャッシュアソシアティビティは理解するのが興味深く、確かに実証できますが、この記事で議論されている他の問題と比較すると、問題となることは少ない傾向があります。プログラムを書く際に最優先で考慮すべきことではありません。

例6: 偽キャッシュライン共有

マルチコアマシンでは、キャッシュは別の問題、つまり一貫性に直面します。異なるコアは、完全にまたは部分的に分離されたキャッシュを持っています。私のマシンでは、L1キャッシュは分離されています(一般的です)、そして2つのプロセッサペアがあり、各ペアがL2キャッシュを共有しています。詳細は異なりますが、最新のマルチコアマシンにはマルチレベルキャッシュ階層があり、より高速で小容量のキャッシュは個々のプロセッサに属します。

1つのプロセッサがキャッシュ内の値を変更すると、他のプロセッサは古い値を使用できなくなります。そのメモリ位置は、すべてのキャッシュで無効化されます。さらに、キャッシュは個々のバイトではなくキャッシュラインの粒度で動作するため、キャッシュライン全体がすべてのキャッシュで無効化されます!

この問題を実証するために、この例を考えてみましょう。

private static int[] s_counter = new int[1024];
private void UpdateCounter(int position)
{
    for (int j = 0; j < 100000000; j++)
    {
        s_counter[position] = s_counter[position] + 3;
    }
}

私のクアッドコアマシンでは、4つの異なるスレッドから UpdateCounter をパラメータ0,1,2,3で呼び出すと、すべてのスレッドが完了するまで4.3秒かかります。

一方、パラメータ16,32,48,64で UpdateCounter を呼び出すと、操作は0.28秒で完了します!

なぜでしょうか?最初のケースでは、4つの値すべてが同じキャッシュラインに収まる可能性が非常に高いです。コアがカウンターをインクリメントするたびに、4つのカウンターすべてを保持するキャッシュラインが無効化されます。他のすべてのコアは、次に自身のカウンターにアクセスする際にキャッシュミスを起こします。この種の Средний (スレッドの振る舞い) は、キャッシュを無効にし、プログラムのパフォーマンスを著しく低下させます。

例7: ハードウェアの複雑さ

キャッシュの仕組みの基本を知っていても、ハードウェアは時々あなたを驚かせます。異なるプロセッサは、最適化、ヒューリスティック、およびそれらが物事を行う微妙な詳細において異なります。

一部のプロセッサでは、L1キャッシュは、異なるバンクからキャッシュラインにアクセスする場合に2つのアクセスを並列に処理できますが、同じバンクに属する場合はシリアルに処理します。また、プロセッサは巧妙な最適化であなたを驚かせることがあります。例えば、私が過去にいくつかのマシンで使用した偽共有の例は、私のマシンでは調整なしではうまく機能しませんでした。私のホームマシンは、最も単純なケースでキャッシュ無効化を減らすために実行を最適化できます。

ここに「ハードウェアの奇妙さ」の奇妙な例があります。

private static int A, B, C, D, E, F, G;
private static void Weirdness()
{
    for (int i = 0; i < 200000000; i++)
    {
        <something>
    }
}

「<something>」に3つの異なるブロックを代入すると、次のタイミングが得られます。

<something>Time
A++; B++; C++; D++;719 ms
A++; C++; E++; G++;448 ms
A++; C++;518 ms

フィールドA、B、C、Dをインクリメントする方が、フィールドA、C、E、Gをインクリメントするよりも時間がかかります。さらに奇妙なことに、AとCだけをインクリメントする方が、AとC、そしてEとGをインクリメントするよりも時間がかかります!

これらの数値の背後にある理由を確信してはいませんが、メモリバンクに関連していると疑っています。誰かがこれらの数値を説明できるなら、ぜひ聞きたいです。

この例の教訓は、ハードウェアのパフォーマンスを完全に予測するのは難しいということです。予測できることはたくさんありますが、最終的には、測定して仮定を検証することが非常に重要です。

結論

これがキャッシュの仕組みの理解に役立ち、プログラムのチューニングに応用できることを願っています。