参照の局所性

6月 7, 2021

admin

階層型メモリ編集

Main article: メモリ階層

階層型メモリは、空間的および時間的な局所性の利点を取り、メモリ階層のいくつかのレベルで使用することができるハードウェアの最適化です。ページングは明らかに時間的および空間的な局所性から利益を得ています。キャッシュは、時間的な局所性を利用する簡単な例です。キャッシュは、特別に設計された、より高速だが小さいメモリ領域であり、一般に、最近参照したデータや最近参照したデータの近くのデータを保持するために使用され、潜在的な性能向上につながることがあります。

キャッシュ内のデータ要素は、メインメモリ内で空間的に近いデータ要素に必ずしも対応しません。ただし、データ要素はキャッシュに 1 行ずつ取り込まれます。これは、空間的な局所性が再び重要であることを意味する：1つの要素が参照される場合、いくつかの隣接する要素もキャッシュにもたらされることになる。最後に、時間的な局所性は最も低いレベルで役割を果たす。なぜなら、非常に近い距離で参照される結果は、マシンのレジスタに保持することができるからだ。いくつかのプログラミング言語（Cなど）では、プログラマが特定の変数をレジスタに保持することを提案できる。

データ局所性は、通常のプログラムの典型的なメモリ参照機能である（多くの不規則メモリアクセスパターンが存在するが）。それは、階層的なメモリレイアウトを有益なものにする。コンピュータでは、データアクセスを高速化するために、メモリは階層的に分割されている。メモリ階層の下層ほど、速度は遅くなるが、サイズが大きくなる傾向がある。したがって、プログラムは、メモリ階層の上位にキャッシュされている間にメモリを使用し、将来まもなく使用されるデータを置き換えるような他のデータを上位階層に持ち込まないようにすれば、より高い性能を達成することができる。これは理想であり、実現できない場合もあります。

典型的なメモリ階層（アクセス時間とキャッシュサイズは、議論のために 2013 年時点で使用される典型的な値の近似値で、実際の値や階層の実際の数は異なる）。

CPUレジスタ（8～256レジスタ）-即時アクセス、プロセッサの最も内側のコアの速度で
L1 CPUキャッシュ（32KiB～512KiB）-高速アクセス、各コアが独占的に所有する最も内側のメモリバスの速度で
L2 CPUキャッシュ（128KiB～24MiB）-やや低速なアクセス。双子のコア間で共有されるメモリバスの速度で
L3 CPUキャッシュ（2MiB〜32MiB） – さらに遅いアクセス、同じプロセッサのさらに多くのコア間で共有されるメモリバスの速度で
Main Physical Memory (RAM) (256 MiB〜64 GiB) – 低速なアクセス。 8162>
Disk (仮想メモリ、ファイルシステム) (1 GiB to 256 TiB) – コンピュータのメインボードとディスクデバイス間のデータチャネルが狭く（ビット幅）、物理的に非常に長いため、速度が非常に遅くなります。また、遅いハードウェアインターフェイスの上に余分なソフトウェアプロトコルが必要なため、
リモートメモリ (他のコンピュータまたはクラウド) (実質的に無制限) – 速度は非常に遅いものから非常に遅いものまでさまざま

最新のマシンでは、下位メモリのブロックをメモリ階層の次のレベルに読み込む傾向があります。このため、使用中のメモリが移動する場合、オペレーティングシステムは、最もアクセスが少ない (または最も新しい) データを予測し、メモリ階層の下に移動させようとします。予測アルゴリズムはハードウェアの複雑さを軽減するために単純なものになりがちですが、多少複雑になってきています。

Matrix multiplicationEdit

よくある例として行列の乗算があります。これは数学的な結果は変わらないが、効率は向上する。この場合、「大きい」とは、おおよそ、各行列の要素が 10 万を超えるか、行列が L1 および L2 キャッシュに収まらないほどのアドレス可能なメモリを意味します。

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

この速度向上の理由は、最初のケースでは、A の読み取りはキャッシュ内にありますが (k インデックスが最後の次元で連続しているので)、B はないので B でキャッシュミスによるペナルティがあるためです。 C は無関係で、内部ループから吊り上げることができます。

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

2 番目のケースでは、C の読み取りと書き込みは両方ともキャッシュにあり、B の読み取りはキャッシュにあり、A の読み取りは内部ループから吊り上げることが可能です。

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

したがって、最初の例ではキャッシュ・ペナルティがあるのに対し、2番目の例では内側ループでのキャッシュ・ミス・ペナルティがない。

2014年プロセッサで、Cで記述してgcc -O3でコンパイルすると、最初の例より2番目の例が約5倍速くなる。 (ディスアセンブルされたコードを注意深く調べると、最初のケースでは GCC が SIMD 命令を使用し、2 番目のケースでは使用しないことがわかりますが、キャッシュのペナルティは SIMD の利益よりもはるかに悪いです。)

上記の例では、ブロッキングと呼ばれる技術を使用して時間的局所性も向上させることができます。より大きな行列を均等なサイズのサブ行列に分割し、より小さなブロックがメモリ内で数回参照（乗算）できるようにします。

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

上記のソリューションでは、ブロックが移動する前に数回使用できるので、メモリ内外への移動が少なく、時間領域が確保されます。連続したメモリ・アドレスを持つ要素は、一緒にメモリ階層に引き上げられる傾向があるので、空間的な局所性が改善される

。