連想メモリ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

連想メモリ（れんそう-、Content Addressable Memory、CAMと略記）は、特殊な高速検索用途のコンピュータメモリの一種。「連想ストレージ」、「連想配列」などとも呼ばれることがある。

一般的なメモリ（RAMなど）では、ユーザーがアドレスを指定すると、そのアドレスに格納されたデータが返ってくる。しかし、連想メモリではユーザーがあるデータワードを指定し、連想メモリは全内容からそのデータワードを検索して探し出す。そのデータワードが見つかれば、連想メモリはそのワードが見つかった場所のアドレスを返す（ある種のアーキテクチャでは、データワード自身を返すか、そのデータに関連して連想されるデータを返す）。従って、連想メモリはソフトウェアの用語で連想配列と呼ばれるものをハードウェアで実現したものである。

連想メモリはメモリ全体をひとつの操作で検索するため、事実上全ての検索用途においてRAMよりもずっと高速である。しかしながら連想メモリはコストがかかるという問題がある。単純な記憶セルから構成されるRAMと異なり、完全並行動作する連想メモリではメモリ内の全ビット毎に入力データとの比較回路が必要である。しかも、1ビットの一致ではなくデータワード全体の一致を探さなければならないため、比較結果をまとめる回路も必要である。これらの追加回路によって連想メモリの回路サイズは増大し、製造コストも増大する。また、それら比較回路はデータが入力される度に全体が動作するため、消費電力も増大する。その結果、現状では連想メモリは非常に高速な検索がどうしても必要な用途でのみ使用されている。

速度とサイズとコストのバランスをうまく取るために、木構造検索やハッシュテーブルを使って連想メモリの機能をエミュレートするような実装をハードウェア的に行う場合もあり、その際には高速化のためにレプリケーションやパイプラインを使用する。そのような設計はルーターでよく使われている。

連想メモリおよび他のネットワーク検索のための主要インターフェイスは、ネットワーク機器の相互運用性を高める目的でNetwork Processing Forumが標準化したルックアサイドインターフェイス（LA-1 および LA-1B）で定義されている。この標準に基づいた様々な機器がIDTやサイプレス・セミコンダクタなどが製造している。

[編集] アーキテクチャの種類

二値連想メモリ（Binary CAM）は最も単純なタイプで、検索ワードの内容を 1 および 0 の二種類の値で構成されているものとして扱う。三値連想メモリ（Ternary CAM）は三番目の値として "X" あるいは "気にしない（Don't Care）"を格納されたデータワードに使用する。例えば、三値連想メモリに "10XX0" というワードが格納されていた場合、このワードは "10000"、"10010"、"10100"、"10110" のいずれとも一致する。二値連想メモリに比較して検索の柔軟性が向上するが、三種類目の値を持つという回路構成上のコスト増大要因がある。一般にこの三番目の状態はメモリ全体にマスクビットを用意することで実装される。

[編集] 適用例

連想メモリはコンピュータネットワーク機器でよく使われる。例えば、スイッチングハブはパケットを一つのポートで受信すると、内部テーブルにそのパケットのMACアドレスとポート番号を格納する。次に、送信先MACアドレスをそのテーブル上で検索してパケットを送り出すべきポート番号を得て、そのポートにパケットを送る。このMACアドレスのテーブルは一般に二値連想メモリで実装され、高速検索によってスイッチングによる遅延を小さくしている。

三値連想メモリはネットワークルーターで使われる。ルーティングに使われるIPアドレスはネットワークアドレスとホストアドレスに分割され、このときサブネットマスクがこの分割に使われ、各サブネット毎にマスクすべきビットが異なる。ルーティングテーブルには各ネットワークアドレスと対応するサブネットマスク、関連情報が格納される。連想メモリを使わない場合、ルーターは宛先アドレスをルーティングテーブルの各エントリと比較、すなわちサブネットマスクで論理積を実施した上でネットワークアドレスと比較する必要がある。もし等しかったら、そのエントリにある関連情報を使ってパケットの転送を行う。三値連想メモリをルーティングテーブルに使用すると、テーブル検索が非常に高速化される。この場合、ホストアドレス部分が "気にしない（Don't Care）" に設定されていると見なされ、正しいエントリの検索（マスクと比較）が迅速に連想メモリのハードウェアで行われるのである。

CPUのキャッシュ制御部やTLBも連想メモリを使用している。キャッシュは最も一般的なセットアソシアティブ方式で連想メモリを使う。セットアソシアティブ方式では、物理アドレスに対応するキャッシュメモリ上の位置がセット数ぶんだけ存在するため、そのうちのどこに格納されているかを高速に検索するのに連想メモリを使用する。これに対してダイレクトマップ方式では物理アドレスにより一意に格納場所が決まるため検索の必要はないが、その物理アドレスのメモリ内容がキャッシュに格納されているかをチェックする必要があるため、連想メモリのキーに相当する部分が存在する。TLBは物理アドレスと論理アドレスを対応させるもので、論理アドレスの一部をデータとして検索を行い、対応する物理アドレスを探す。一般にTLBやキャッシュは非常に高速な動作を要求されるため、ある程度以上サイズを大きくすると連想メモリであっても要求速度に応えられない。従って、TLBやキャッシュのサイズはその時点の半導体プロセスの技術レベルとの兼ね合いで決定される（キャッシュの場合、キャッシュとしての効率を度外視すればセット数を少なくしてサイズを大きくするという考え方もある）。

その他の連想メモリの使用例として以下のものがある。