【コンピュータ】指定席と自由席のいいとこ取り！「nウェイセットアソシアティブ」｜情報処理問題1000本ノック
キャッシュメモリのマッピング方式の集大成。現代のCPUのほとんどに採用されている、コストとヒット率のバランスが最も優れた「nウェイセットアソシアティブ」の決定版を攻略しましょう。
1. 【 問題 】：キャッシュメモリのセットアソシアティブ方式
【 問題 】 コンピュータのCPUにおいて、主記憶（メインメモリ）のデータをキャッシュメモリに配置する「マッピング方式」の一つであり、キャッシュメモリを複数のセット（グループ）に分割し、主記憶のアドレスによって格納先のセットを一意に決定した上で、そのセット内にある「n個」のライン（空き領域）であれば、どこにでも自由にデータを配置できる方式はどれでしょうか？
① ダイレクトマッピング方式 (Direct Mapping)
② フルアソシアティブ方式 (Fully Associative Mapping)
③ nウェイセットアソシアティブ方式 (n-Way Set Associative Mapping)
④ ライトバック方式 (Write-Back)
2. 正解：
正解： ③ nウェイセットアソシアティブ方式 (n-Way Set Associative Mapping)
3. 解説：極小の自由席を並べた、現代CPUの最適解
格納場所が1箇所に固定される「ダイレクトマッピング方式」と、どこでも完全に自由な「フルアソシアティブ方式」。この2つの長所を組み合わせ、短所を打ち消し合うように設計されたのがnウェイセットアソシアティブ方式です。
・仕組み：まず、キャッシュメモリをいくつかの「セット」というグループに小分けします。主記憶のデータがどのセットに入るかは、アドレスの計算で一瞬で決まります（ここはダイレクトマッピングと同じで回路が単純）。しかし、決まったセットの中には「n個」の格納スペース（ライン）が用意されており、その中であればどこに格納しても構いません。 ← ココが問題の正解！
・「ウェイ（Way）」とは？：1つのセットの中に用意されている「空き場所の数（ライン数）」のことです。例えば「4ウェイ（4-Way）」であれば、1つのセットの中に4つの席があり、同じセットにマッピングされるデータが4個までなら、上書き（追い出し）されることなく同時にキャッシュに共存できることを意味します。
★ ① ダイレクトマッピング（1ウェイセットアソシアティブと同義）：セット内の席が1つ（1ウェイ）しかないので、競合が起きると即追い出し。回路は最安、ヒット率は最低。
★ ② フルアソシアティブ（1セットアソシアティブと同義）：キャッシュ全体が「1つの巨大なセット」であり、席の数（ウェイ数）がキャッシュ全容量分ある状態。ヒット率は最高、回路コストも最高。
★ ③ nウェイセットアソシアティブ：上記のハイブリッド。現実的な回路規模（コスト）に抑えつつ、フルアソシアティブに近い「高いヒット率」を叩き出せるため、現代のパソコンやスマホのプロセッサの主流となっています。
1. 理解のコツ: 「新幹線の座席チケット」に例えてみましょう。
・チケットに「3号車 5番 A席」とピンポイントで指定され、そこしか座れないのがダイレクトマッピングです。
・「何号車のどこでも、空いている席なら日本中の誰でも座っていいよ」という完全自由席がフルアソシアティブです。
・今回の方式は、「あなたのチケットは『3号車（指定されたセット）』です。3号車の中には4つの席（4ウェイ）があるので、その4つのうち空いている席ならどこに座ってもいいですよ」というルールです。これなら、車両を探す（セットを見つける）のはアドレス計算で一瞬ですし、車両に入った後は、たった4つの席だけを確認すれば友達を見つけられますよね。このスマートなバランス感覚がnウェイセットアソシアティブです。
2. 試験対策 of 視点: 「複数のセットに分割」「セット内にあるn個のラインであればどこにでも配置できる」という、部分的な自由度を持たせた記述があれば「nウェイセットアソシアティブ」が一択です。基本情報や応用情報の午前試験では、コンピュータのアーキテクチャ問題として、「ウェイ数を増やすと、キャッシュのヒット率や回路の複雑さはどう変化するか」といった、これまでの3方式のトレードオフを完璧に理解しているかを試す応用問題として非常に重宝される大トリのキーワードです。
4. まとめ
「アドレスによる『セット指定（効率性）』と、セット内での『n個の自由席（柔軟性）』を組み合わせることで、低コストかつ高ヒット率を実現した、現代コンピュータの基盤を支える傑作マッピング方式」。これがnウェイセットアソシアティブ方式です。これでキャッシュメモリの格納アルゴリズムの全貌がつながりましたね！