キャッシュシステムには2ウェイセットアソシエイティブや4ウェイセットアソシエイティブ,あるいはダイレクトマッピング方式などがありますが,違いを詳しく教えてください。
キャッシュシステムの構造はけっこう分かりにくいので,ここで簡単にまとめて説明しておきましょう。
ご存じかとは思いますが,キャッシュメモリは,急激に高速化しているCPUと,その処理速度に追いつかないメインメモリとのスピード差を埋めるためにあります。そのため,メインメモリに使われているDRAMよりも高速なメモリが使用されます。
キャッシュメモリには,CPUに内蔵されているL1キャッシュと,CPUの外に置かれているL2キャッシュがあります。また,新型のCeleronやXeon,近く発売される予定のSharptooth(K6-3)などのように,L2キャッシュがCPUに内蔵されたものも登場しています。L1キャッシュはCPUコアと等速で動作し,CPU外に置かれているL2キャッシュは,基本的にベースクロックで動作します。CPUに内蔵されているL2キャッシュの場合は,CPUコアと等速か数分の1のクロックで動作します。CPUによって微妙にキャッシュの扱い(とくにL1キャッシュの場合)が違うのですが,ここでは話を単純にするため一般的なキャッシュということで話を進めます。
キャッシュの構成は,実際にデータが置かれるデータ領域と,データのアドレスや更新履歴などが置かれるタグ領域に分かれています。
キャッシュメモリに置かれるデータは,ラインという単位で管理されています。メインメモリ(L1キャッシュの場合はL2キャッシュ)とのやり取りは,ライン単位で行われます。
1ラインはシステムによっても異なりますが,PentiumやPentiumUでは32バイト,i486では16バイトとなっています。これは,PentiumやPentiumUが64ビットデータバス(8バイト)で,PB SRAMのバースト転送で四つの連続したエリアにアクセスすることから,
64/8×4=32
つまり,32バイト単位にすると都合がいいからです。i486は32ビットデータバスのため同じ計算で16バイト単位というわけです。キャッシュのデータ更新はライン単位で行われるため,たとえ必要となるデータが1バイトでも,1ラインの32バイト分すべてが更新されます。繰り返しますが,Pentiumのデータバス幅は64ビット(8バイト)なので,4回のメモリ転送が必要となります。このように,ラインという大きなブロックで管理すると,むだが大きくなって,いくら速いメモリを使っていてもシステムパフォーマンスが低下してしまいそうに感じますが,OSやアプリケーションでは連続したデータを利用することが多いため,それほど効率が悪くなるわけではありません。
キャッシュのデータは,元のデータがあったメインメモリのアドレスによって,ある特定のラインに置くようにコントロールされるのが普通です。どこに置かれるかは次の計算式で決まります。
キャッシュの位置=メインメモリ mod キャッシュの容量
容量が8KB,データ領域が32バイトのライン256本で構成されているキャッシュメモリがあるとします。32バイト単位なので,ブロックの先頭アドレスは0x00〜0x1F(0xは16進数を表します)ごととなります(図1)。また,8KBは0x2000です。
メインメモリの0x123400B1番地へのデータアクセスがあった場合,
0x123400B1 mod 0x2000 = 0xB1
ちなみにこの計算は,Windowsの[アクセサリ]→[電卓]で関数電卓に設定すると簡単にできます。
さて,0xA0〜0xBF(5番め)のラインに0x123400B1番地のデータ(メインメモリ上での先頭アドレスは0x123400A0)がすでに格納されているかどうかを調べます。どのアドレスのデータが格納されているかは,タグ領域に記録されていますから,キャッシュのデータ領域を調べる必要はなく,タグ領域の5番めだけを調べれば分かります。データがキャッシュにあれば,5番めのラインの0x11バイトめのデータ(図1ではメAモ)をCPUに渡します。もし,タグ領域に00B1番地のデータが格納されていないという情報があった場合,キャッシュコントローラが05番ラインに0x123400A0から0x123400BFまでの32バイトのデータを転送します。もちろん,この時点でタグ領域の情報も更新されることとなります。
次に,0x123400C0番地へのアクセスがあると,0x123400C0から0x123400DFまでの32バイトデータは,06番ラインに格納され,05番ラインはそのまま保持されます。05番ラインが更新されるのは,0xCDEF00B1のように0x2000で割った余りが0x00A0から0x00BFのデータがアクセスされたときとなります。
つまり,0x2000で割った余りが同じになるアドレスだと上書きされてしまうわけです(図2)。これでは,せっかくキャッシュにデータを取り込んだとしても,すぐに上書きされてしまい,ミスヒットの確率が高くなります。
質問の,セットアソシエイティブですが,すぐに上書きされないように,キャッシュメモリのラインテーブルを,何セットかに分割するものです。
例えば,上記の説明では32バイトのラインが256本の構成(合計で8KB)でしたが,512本の構成(合計で16KB)にして,2本のセットに分割します。n番めのライン番号に対して2本のラインを使えるように管理するのです。ラインが2本あれば,5番めのラインの片方に0x12340020番地のデータが入っていて0xCDEF0020番地のアクセスがあった場合でも,もう片方のラインに格納できます(図3)。この場合,タグ領域も倍の容量にして,アドレスが2個格納できるようにしておく必要があります。こうすることによって,0x12340020と0xCDEF0020のデータを交互に参照するようなアクセスがあった場合でも,5番めのラインを更新する必要がなくなります。このように2本のラインを用意するのを,2ウェイセットアソシエイティブ方式といいます。また,4本のラインを用意すると4ウェイセットアソシエイティブとなります。
1対1の場合には,1ウェイセットアソシエイティブと呼ばず,ダイレクトマッピング方式と呼ばれます。逆にすべてのラインに対してすべてのアドレスのデータを格納できる方式をフルアソシエイティブ方式といいます(図4)。
ダイレクトマッピングからフルアソシエイティブになるに従って,キャッシュのヒット率は高くなります。しかし,今度はタグ領域を検索する数が増加するため,スピードアップの効果が薄れてしまうのです。例えば,ダイレクトマッピング方式に対して,2ウェイセットアソシエイティブでは2倍,4ウェイセットアソシエイティブでは4倍,フルアソシエイティブではラインの数を掛けただけの時間がかかることになります。
通常,L1キャッシュには2ウェイセットアソシエイティブや4ウェイセットアソシエイティブ方式が使われ,大容量が可能なL2キャッシュでは,ダイレクトマッピング方式が使われています。フルアソシエイティブ方式のキャッシュシステムは,検索時間がかかりすぎるため,容量の大きなキャッシュシステムではあまり利用されることはないようです。
(寺崎基生)
図1 キャッシュとアドレスの関係
1バイトのアクセスでも1ライン(32バイト)分のデータがキャッシュに取り込まれる
図2 ダイレクトマッピング方式
このように上書きされてしまう可能性が高い
図3 2ウェイセットアソシエイティブ方式
2か所にキャッシュ領域を持てるので,ダイレクトマッピング方式よりは上書きされにくくなる
図4 キャッシュの各方式による違い