連想メモリ

連想メモリ（れんそうメモリ、Content Addressable Memory、CAM）は、コンピュータなどの記憶装置（メモリ）の一種で、たいていの一般的なメモリは整数値などでアドレスを指定してその内容を読み書きするものであるのに対し、内容（の一部）を指定して、そのアドレスあるいは内容全体を読み出すことができる、というメモリである。

概説

一般的な記憶装置（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やキャッシュのサイズはその時点の半導体プロセスの技術レベルとの兼ね合いで決定される（キャッシュの場合、キャッシュとしての効率を度外視すればセット数を少なくしてサイズを大きくするという考え方もある）。

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

• データベースエンジン
• データ圧縮ハードウェア
• 人工ニューラルネットワーク

関連項目

• アソシアトロン

外部リンク

• CAM Primer（英語）
• Content-addressable memory (CAM) circuits and architectures: A tutorial and survey（英語）