31

参照の局所性を理解するのに問題があります。誰でも、それが何を意味し、何が何であるかを理解するのを手伝ってくれませんか?

  • 基準の空間的局所性
  • 参照の時間的場所
4

4 に答える 4

55

これは、コンピューターが超高速メモリでいっぱいの場合は問題になりません。

しかし、残念ながらそうではなく、computer-memory は次のようになります1 :

+----------+
| CPU      |  <<-- Our beloved CPU, superfast and always hungry for more data.
+----------+
|L1 - Cache|  <<-- ~4 CPU-cycles access latency (very fast), 2 loads/clock throughput
+----------+
|L2 - Cache|  <<-- ~12 CPU-cycles access latency (fast)
+----+-----+
     |
+----------+
|L3 - Cache|  <<-- ~35 CPU-cycles access latency (medium)
+----+-----+       (usually shared between CPU-cores)
     |
     |   <<-- This thin wire is the memory bus, it has limited bandwidth.
+----+-----+
| main-mem |  <<-- ~100 CPU-cycles access latency (slow)
+----+-----+  <<-- The main memory is big but slow (because we are cheap-skates)
     |
     |   <<-- Even slower wire to the harddisk
+----+-----+
| harddisk | <<-- Works at 0,001% of CPU speed
+----------+

空間的局所性
この図では、データが CPU に近いほど、CPU はより速くデータを取得できます。
これは に関連していSpacial Localityます。データがメモリ内で近接して配置されている場合、データには空間的局所性があります。
私たちがRAMであるという安っぽいスケートのために、実際にはRAMはランダムアクセスではなく、実際にはSlow if random, less slow if accessed sequentially Access MemorySIRLSIAS-AMです. DDR SDRAM は、1 つの読み取りまたは書き込みコマンドで 32 または 64 バイトのバースト全体を転送します。
そのため、関連するデータをまとめて保持するのが賢明な理由です。これにより、一連のデータを順次読み取り、時間を節約できます。

一時的な局所性
データはメイン メモリに保持されますが、キャッシュには保持できません。そうしないと、キャッシュが役に立たなくなります。キャッシュには、最近使用されたデータのみが見つかります。古いデータが押し出されます。
これは に関連していtemporal localityます。データは、同時にアクセスされる場合、強い時間的局所性を持ちます。
これは重要です。なぜなら、アイテム A がキャッシュ内にある (良い) 場合、アイテム B (A に対して時間的局所性が強い) もキャッシュ内にある可能性が非常に高いからです。

脚注 1:

これは、例としてさまざまな CPUから推定されたレイテンシ サイクル カウントを使用して簡略化したものですが、典​​型的な CPU の正確な桁数を示しています。

実際には、レイテンシと帯域幅は別の要因であり、CPU から離れたメモリほどレイテンシを改善するのは困難です。ただし、ハードウェアのプリフェッチやアウトオブオーダー exec は、配列のループなど、場合によってはレイテンシを隠すことができます。予測不可能なアクセス パターンでは、有効なメモリ スループットが L1d キャッシュの 10% よりはるかに低くなる可能性があります。

たとえば、L2 キャッシュ帯域幅は必ずしも L1d 帯域幅の 3 倍悪いわけではありません。(ただし、AVX SIMD を使用して、Haswell または Zen2 CPU の L1d からクロック サイクルごとに 2x 32 バイトのロードを実行している場合は、より低くなります。)

この単純化されたバージョンでは、TLB の影響 (ページ粒度の局所性) と DRAM ページの局所性も除外されています。(仮想メモリ ページとは異なります)。メモリ ハードウェアとそのチューニング ソフトウェアの詳細については、「すべてのプログラマがメモリについて知っておくべきこと」を参照してください。

関連:ほとんどのプロセッサで L1 キャッシュのサイズが L2 キャッシュのサイズよりも小さいのはなぜですか? 必要なレイテンシ/帯域幅と容量 (およびヒット率) の組み合わせを得るために、マルチレベルのキャッシュ階層が必要な理由を説明します。

巨大で高速な L1 データ キャッシュを 1 つ使用すると、非常に電力消費が大きくなり、最新の高性能 CPU の小型で高速な L1d キャッシュほどの低レイテンシでは実現できません。

マルチコア CPU では、L1i/L1d および L2 キャッシュは通常、コアごとのプライベート キャッシュであり、L3 キャッシュは共有されます。異なるコアは、L3 とメモリの帯域幅について互いに競合する必要がありますが、それぞれに独自の L1 と L2 の帯域幅があります。キャッシュを高速化するにはどうすればよいでしょうか? を参照してください。デュアルコア 3GHz IvyBridge CPU からのベンチマーク結果: 両方のコアで 186 GB/秒の合計 L1d キャッシュ読み取り帯域幅と、両方のコアがアクティブな場合の 9.6 GB/秒の DRAM 読み取り帯域幅。(したがって、シングルコアのメモリ = 10% L1d は、128 ビット SIMD ロード/ストア データ パスのみを使用する、その世代のデスクトップ CPU の適切な帯域幅の見積もりです)。また、L1d レイテンシは 1.4 ns、DRAM レイテンシは 72 ns

于 2011-10-03T18:20:10.843 に答える