このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

キャッシュメモリ

 キャッシュメモリ(バッファ記憶)はメモリへのアクセスを高速化するために存在する特別なメモリである。 キャッシュメモリ(SRAM)とはCPUのレジスタ(SRAM)と主記憶装置であるメモリ(DRAM)の間に存在する。1度呼ばれたデータは再度呼ばれる可能性が高いので、それらをメモリの一部に保存しておけば、遅いHDに再度アクセスする必要はないわけだ。

キャッシュメモリの特徴

・CPUの高速な処理に追従できる比較的小容量の高速な記憶装置。

・主記憶とCPUの間に置く。

・メモリ参照の局所性を利用し、現在実行中の命令の近くのコードのみをこれに格納する。

・主記憶からキャッシュメモリへは数十バイトを単位として並列的に転送する。

・CPUの主記憶へのアクセス速度を見かけ上早くする。

キャッシュミスが頻発すると処理効率は上がらない。

1次キャッシュと2次キャッシュ

 最近のMPUは、キャッシュメモリを内蔵しているものも多い。また、キャッシュメモリとメインメモリの間にさらにキャッシュメモリを追加することもある。この場合、CPUに近いほうから1次キャッシュ2次キャッシュと呼ぶ。

命令キャッシュとデータキャッシュ

  • 命令キャッシュ(インストラクションキャッシュ)
    • 命令後専用のキャッシュメモリ。
    • 変更されない。
  • データキャッシュ(オペレーティングランドキャッシュ)
    • データ専用のキャッシュメモリ。
    • 命令実行により変更の可能性がある。

キャッシュメモリ以外のキャッシュたち

 キャッシュには4つのタイプがあります。次の順番の流れでキャッシュされていく。

1:CPUの中の高速メモリである1次キャッシュ(オンチップ・キャッシュとも呼ばれる)にキャッシュする。

2:CPUとメモリの間の高速メモリである2次キャッシュにキャッシュする。

3:メモリの一部にキャッシュする。

4:HDの一部にキャッシュする。

 フォントキャッシュ、ブラウザのキャッシュなどはここに含まれる。

ライトスルーとライトバック

 コンピュータ内の処理はキャッシュメモリを対象に行われる。そのため処理の進行と共にキャッシュメモリの内容と主記憶装置の内容がずれてくる。これを整合性(coherency:コヒーレンシー)がずれてくることを意味する。

 コヒーレンシーを保つための手法として、次の2種類がある。

  • ライトスルー方式
  • ライトバック方式

ライトスルー(write through)方式

 キャッシュメモリと主記憶装置の両方に同時にデータを書き込む方式。メモリアクセスが発生するとキャッシュメモリ内にこのブロックがあるかどうか調べ、キャッシュメモリにあればそのブロックを読み出し、データの対応する部分だけに書き込む。次に、このブロックをキャッシュメモリに書き戻すと同時に、メインメモリに対してもデータを書き込む。

 主記憶装置から別のプログラムをキャッシュに持ってくるとき上書きすればよいだけなので、キャッシュとメインメモリとのデータ整合性が常に保たれ、制御も容易である。しかし、主記憶装置へのアクセス時間がキャッシュメモリへのアクセス時間と比べて非常に遅いため、書き込み時のCPUの待ち時間が大きくなる。つまり、読み出しに関しては高速化され、書き込み時には高速化は望めない。

ライトバック(write back)方式

 CPUが書き込み動作をするときに、とりあえずキャッシュメモリだけにデータを書き込む方式。キャッシュメモリとメインメモリの内容が一致しなくなるので、このブロックがキャッシュメモリから追い出されるときに、メインメモリにこのブロックの書き戻しを行う。

 ライトスルー方式に比べてCPUの待ち時間が短くなるので、動作が高速になる。

キャッシュの割当方式

 主記憶装置のブロックとキャッシュメモリのブロックの対応付けの方法にはいくつかの方式がある。

  • ダイレクトマップ(ダイレクトマッピング)方式
    • 主記憶のアドレスに対してキャッシュ上の場所が1対1で固定される。
    • 主記憶のブロックをキャッシュのどのブロックに格納するかは、「キャッシュの格納位置=主記憶のブロック番号 (mod キャッシュの総ブロック数)」を計算する。ハッシュ法と同じイメージである。
    • ハッシュ法と同様にダイレクトマップ方式でもシノニムが発生する。よって、キャッシュのブロック数と主記憶のブロック数が大きいほどシノニムが多発するという欠点がある。
  • フルアソシエイティブ方式
    • 主記憶装置の複数のブロックとキャッシュメモリの複数のブロックをランダムに対応付ける方式。
    • 必要とするブロックがキャッシュメモリのどこにあるか調べるには、キャッシュのブロックをすべて辿らなければならない。よって、キャッシュのブロック数が多い場合は探索に時間がかかるという欠点がある。
  • セットアソシエイティブ方式
    • ダイレクトマップ方式とフルアソシエイティブ方式の欠点を補う形で考案された方式。
    • 探索すべきおおよその位置を決めて、そこから線形探索を行う(あるいはランダムに格納する)という方式である。
    • セットとは、複数のブロックを束ねたものである。
      • セット内のブロックをウェイといい、2ブロック1セットとした場合は2ウェイセットアソシエイティブ方式となる。
    • 主記憶のブロックをキャッシュのどのブロックに格納するかは、「キャッシュの格納位置=主記憶のセット番号 (mod キャッシュの総ブロック数)」で計算する。

記憶装置へのアクセス速度

 CPUによる記憶装置へのアクセス速度を速い順に並べると次のようになる。

  1. CPUのレジスタ
  2. キャッシュメモリ
  3. メインメモリ(主記憶装置)
  4. 磁気ディスク装置

CPUの平均アクセス時間

 CPUはプログラムを実行するとき、まずキャッシュメモリに入っているかどうかをチェックする。常にキャッシュにあるとは限らないので、入っていなければ主記憶装置に取りに行く必要がある。これは処理時間がかかり、CPUにとって大きな損失となる。

 キャッシュメモリにデータが存在する確率は、次の用語を用いて表現される。

  • ヒット率
    • データがキャッシュメモリに存在する確率。
  • NFP(Not Found Probability)=ミス率
    • データがキャッシュメモリに存在しない確率。

 ヒット率とNFPには次のような関係が成り立つ。

ヒット率+NFP=1

 データがキャッシュメモリにあるときはそこから読み込むのでアクセス速度は速い。一方、データがキャッシュメモリになければ、主記憶装置であるメモリから読み込む。このアクセス速度は遅い。一度読んだデータは、キャッシュメモリに置いておく。よって、(平均の)実効メモリアクセス時間は次の公式で求めることができる。

(実効メモリアクセス時間)=(キャッシュメモリへのアクセス時間)×(ヒット率)+(メモリへのアクセス時間)×NFP
(実効メモリアクセス時間)=(キャッシュメモリへのアクセス時間)×(ヒット率)+(メモリへのアクセス時間)×(1−ヒット率)

例:1GHz(ページフォールドの確率は0.001%)+メモリ増設、2GHz(ページフォールドの確率は0.01%)+メモリ増設なしではどちらが得するか。

 実行中命令の70%は1サイクルで実行でき、残りの30%のうち95%は2サイクル、5%は実効メモリ参照時間で実行する。

 よって、 0.7×1サイクル+0.3×(0.95×2サイクル+0.05×実効メモリ参照時間) で平均実行時間が計算できる。

 また、実効メモリ参照時間は1サイクルの長さに関係なく、次のように計算できる。

(1−p)×Tma+p×Tpf

ただし、
p:ページフォールトが起こる確率
Tma:物理メモリの参照にかかる時間
Tpf:ページフォールトの処理時間

 ここで、Tma=50ns、Tpf=1.5msとして、p=0.01%あるいはp=0.001%のときの実効メモリ参照時間を計算する。

[1]p=0.01%のとき

(1−0.0001)×50[ns]+0.0001×(1.5×106) [ns]
=0.9999×50+0.0001×1,500,000
=49.995+150
=199.995 [ns]

[2]p=0.001%のとき

(1−0.00001)×50[ns]+0.00001×(1.5×106) [ns]
=0.99999×50+0.00001×1,500,000
=49.9995+15
=64.9995 [ns]

 よって、1機械語命令あたりの平均実行時間を計算する次のようになる。

[a]1GHzのプロセッサのとき(メモリ増設)

 1サイクル=1[ns]、ページフォールドの確率は0.001%のときなので、実効メモリ参照時間=64.9995[ns]より、

(平均実行時間)
=0.7×1[ns]+0.3×(0.95×2[ns]+0.05×64.9995[ns])
=0.7+0.3×(1.9+3.249975)
=0.7+0.3×5.149975
=0.7+1.5449925
=2.2449925 [ns]

[b]2GHzのプロセッサのとき(メモリ増設なし)

 1サイクル=0.5[ns]、ページフォールドの確率は0.01%のときなので、実効メモリ参照時間=199.995[ns]より、

(平均実行時間)
=0.7×0.5[ns]+0.3×(0.95×1[ns]+0.05×199.995[ns])
=0.35+0.3×(0.95+9.99975)
=0.35+0.3×10.94975
=0.35+3.284925
=3.634925 [ns]

 したがって、プロセッサ1GHzのままで、メモリを増設してページフォールトの確率を0.001%に減らすほうが、より高速にプログラムを実行できる。

参考文献

  • 『プログラムはなぜ動くのか』
  • 『実践コンピュータシステム』
  • 『2001秋 徹底解説 基本情報技術者本試験問題』
  • 『超図解mini 基本情報技術者試験 平成19年度版』
  • 『ソフトウェア開発技術者 午前対策(基礎編) テキスト』
  • 『1週間で分かる基本情報技術者集中ゼミ【午前編】 2006春秋』
  • 『ソフトウェア開発技術者 合格エッセンシャルハンドブック』