📝キャッシュ

📝キャッシュ

キャッシュとは #

Cache, Cache Archtecture.

ある領域から他の領域へ情報を転送する際, その転送遅延を極力隠蔽化させ転送効率を向上させるために考案された記憶階層の実現手段.

たとえば,

  • Memory -> Cache -> CPU
  • Memory -> Cache -> HDD

Memory Hierarchy #

registers
L1 Cache SRAM
L2 Cache SRAM
Memory DRAM
local 2nd storage local disks
remote 2nd storage Web Servers

Locality #

局所性.

Programs tend to use data and instructions with addresses near or equal to those they have used recently.

時間的局所性 (英: temporal locality) #

ある時点で参照されたリソースが近い将来にも再び参照される可能性が高いことを表す概念

空間的局所性 (英: spatial locality) #

あるリソースが参照されたとき, その近傍のリソースが参照される可能性が高いことを表す概念

逐次的局所性 (英: sequential locality) #

メモリが逐次アクセスされるという概念

Associativity #

キャッシュメモリはデータを Block (Line) と呼ぶある程度まとまった単位で管理する. 複数セットのタグを持てば同じエントリアドレスでも複数データの格納を行うことが可能となる. このタグのセット数 (ウエイ) を連想度と呼ぶ. データ格納構造の相違は連想度の相違でもある.

ダイレクトマップ方式 (Direct Mapped) #

1 組のタグにより構成 (連想度 1) されるデータ格納構造. アドレスにより一意に配置が決まるため, タグの構造が非常に単純.

だが, 同一エントリに異なるフレームアドレスが転送されると必ずラインの入れ替えが発生する.

Direct Mapped Cache

セットアソシアティブ方式 (Set Associative) #

複数のタグにより構成 (連想度 2 以上) されるデータ格納構造.

同一エントリに異なるフレームアドレスのデータを複数格納することができる. 連想度が上がるほどキャッシュヒット率は上昇するが製造は困難になっていくため, システムによりバランスのよい実装が異なる.

Set Associative Cache

フルアソシアティブ方式 (Fully Associative) #

エントリアドレスによる振り分けはなく, 全てのラインが検索対象となる構造. 従って連想度はライン数分となる. キャッシュスラッシングは起こり難くヒット率は最も優れているが, 実装コストや複雑度の面から通常用いられることはない.

General Cache Organization #

Block (Line), Set という概念を踏まえ, 一般的なキャッシュ構造は以下になる.

Cache Structure #

     Cache size = Block size
               	x 連想数 (2 の倍数)
               	x Set 数 (2 の倍数)
Block …. Block
Block …. Block
Block …. Block
Block …. Block
Block …. Block

Set Structure #

1 Set は, Block の集合.集合の size が associativity.

Block …. Block

Block Structure #

  • tags … 同一 set のなかで一位に識別するための情報.
  • set index … xxx 個のアドレスを yyy 個に圧縮するためのハッシュキー. ここが何ビットになるかは associativity の決め方次第.
  • block offset … x bit を 2 の倍数 bit に収めるための offset.
  • data … メインメモリからロードしたデータ
tags set index block offset data
     ex.) 0x1833 .... 0000...... 0011 0011
     -> 0011 は block offset として使わない.
     -> 011 が index

Tags