(In Japanese)連想メモリ

• P2006-101106 (Mar 31, 2006) JP

• (In Japanese)笹尾 勤

• (In Japanese)国立大学法人九州工業大学

通常のメモリは、与えられたインデックス（アドレス）に対して、そのアドレスに格納されている登録データを生成する。一方、CAMは、与えられた検索（入力）データに対して、それを格納するCAMのインデックス（アドレス）を生成する（非特許文献1，2参照）。

CAMは、パターン・マッチング、インターネットのルータ、プロセッサのキャッシュ、TLB（Translation Lookaside Buffer）、データ圧縮、データベースのアクセラレータ、ニューラルネット、メモリパッチなど幅広い分野において利用されている。

通常、CAMは、その機能から、2値CAM（Binary CAM：以下「BCAM」という。）及び3値CAM（Ternary CAM：以下「TCAM」という。）の二種類に分類される。BCAMでは、各セルに0及び1を格納する。TCAMでは各セルに0，1，及び＊を格納する。ここで、「＊」はドント・ケア（don't care）を表し、0と1の両方にマッチする。

〔定義1〕（BCAM）
n入力で登録データ数pのBCAMテーブルは、p個の異なる2値ベクトルを格納する。また、p個のベクトルは、アドレス1からアドレスpに順に格納されていると仮定する。また、各ベクトルのアドレスはmビットで表現可能である。mは次式（1）により表される。

【数式1】


また、p個のベクトルは、アドレス1からアドレスpに順に格納されていると仮定する。対応するBCAM関数f:{0,1}ⁿ→{0,1}^mは、以下の条件を満たす：
f(x)は入力xと同じベクトルがBCAMテーブル中にあるとき、ベクトルxを格納するCAMのアドレス（1からpの値の何れか）を出力する。入力xと同じパターンがBCAMテーブル中に無い場合には、f(x)の値は0である。
（定義終り）

（例1）
（表1）は、7個の2値ベクトルを格納するBCAMを示す。対応するBCAM関数を（表2）に示す。何れも、入力データに完全に一致したベクトルを格納するアドレスを3ビットの数（例えば、‘011’）として出力する。入力ベクトルと一致するものがBCAM中に格納されていない場合には、0を出力する。
（例終わり）

【表1】

【表2】

〔定義2〕（TCAM）
n入力で要素数pのTCAMテーブルは、p個の3値ベクトルを格納する。また、p個のベクトルは、アドレス1からアドレスpに順に格納されていると仮定する。また、各ベクトルのアドレスはmビットで表現可能である。ここで、mは上記式（1）により表される。各3値ベクトルは、0，1，又は＊（ドント・ケア）から構成される。対応するTCAM関数：f:{0,1}ⁿ→{0,1}^mは、以下の条件を満たす：
入力xに対して、xと一致するベクトルがTCAMテーブル中にある場合、出力f(x)は、一致したベクトル中の最小のアドレスを示す。また、xと一致するベクトルがTCAMテーブル中に無い場合には、0を出力する。
（定義終り）

（例2）
（表3）に示すTCAMは、7個の3値ベクトルを格納する。対応するTCAM関数を（表4）に示す。入力x=(1,0,1,1)は、アドレス5及び6に蓄えられているパターンと一致する。5の方が小さいので、出力は(0,1,0,1)となる。
（例終わり）

【表3】

【表4】

CAMの機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェア（半導体メモリ）を用いてCAMを実現することが多い。以下、ハードウェアで構成された従来のCAMについて説明する。

図8は、従来のCAMの基本構成の一例を表すブロック図である（特許文献1参照）。CAM100は、比較レジスタ101、検索ビット線ドライバ102、n個のワードW₁～W_n、n個の一致センス回路MSC₁～MSC_n、n個の一致フラグレジスタMFR₁～MFR_n、及びプライオリティ・エンコーダ（優先度付符号化回路）PEを備えている。

比較レジスタ101は、mビットの検索データを格納するレジスタである。検索ビット線ドライバ102は、比較レジスタ101の各ビットを検索ビット線上にドライブする。各ワードW₁～W_nは、それぞれmビットのCAMセルを備えている。

図9は、図8のCAMセルの構成回路図である。図9に例示したCAMセル103は、不一致検出型のものである。CAMセル103は、メモリ・セル104及び一致比較回路105から構成される。メモリ・セル104は、1ビットのデータを記憶するSRAM構成のメモリ・セルである。図9においてDがデータ、DNが反転データを表す。一致比較回路105は、メモリ・セル104に記憶された1ビットのデータと検索ビット線対SL，SLN上にドライブされる検索データとを比較し、その一致比較結果を一致線ML上に出力する。

一致比較回路105は、3つのnMOSトランジスタ（以下「nMOS」という。）106，107，108を備えている。nMOS106，107は、検索ビット線SLNと検索ビット線SLとの間に直列に接続されている。nMOS106，107のゲートは、それぞれ、メモリ・セル104のデータD，反転データDNに接続されている。nMOS108は、一致線MLとグランドとの間に接続されている。nMOS108のゲートは、nMOS106，107の間のノード109に接続されている。

まず、検索を行う前に、CAM100のそれぞれのワードW₁～W_nに、検索対象であるデータが記憶される。各ワード内の各CAMセル103において、メモリ・セル104へのデータの書き込み及びメモリ・セル104からのデータの読み出しは、通常のSRAMと同様にして行われる。

検索時には、まず、比較レジスタ101に検索データが格納される。検索データの各のビットは、検索ビット線ドライバ102により、各々対応する検索ビット線上にドライブされる。

各々のワードW₁～W_nでは、各CAMセルに予め記憶されているデータと検索ビット線上にドライブされた検索データとの一致検索が同時（並列）に実行され、その結果が一致線ML₁～ML_n上に出力される。これらの検索結果は、それぞれ一致センス回路MSC₁～MSC_nに入力される。各一致センス回路MSC₁～MSC_nは、各検索結果を増幅し、一致センス出力として一致センス出力線MT₁～MT_nに出力する。各一致センス出力は、一致フラグレジスタMFR₁～MFR_nに格納され、一致フラグ出力として一致フラグ出力出力線MF₁～MF_nに出力される。一致フラグは、‘1’が「一致あり」、‘0’が「一致なし」を表すものとする。

各一致フラグ出力は、プライオリティ・エンコーダPEに入力される。プライオリティ・エンコーダPEでは、所定の優先順位付けに従って、一致が検出されたワードの中から最優先順位のワードのアドレス（最優先一致アドレス：HMA）を選択し出力する。各ワードの優先順位は、ワードW₁が最も高く、W_nに向かうに従って順次優先順位が低くなるものとする。

尚、各ワードW₁～W_n内の各CAMセル103における一致検索は、次のようにして実行される。

まず、初期化動作を実行する。初期化動作では、検索ビット線対SL，SLNがともに‘L’（＝‘0’）とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS106，107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS106，107のうちオン状態の方を介して、両者の間のノード109のレベルが‘L’となり、nMOS108はオフ状態となる。この状態で、一致線MLが‘H’（＝‘1’）状態にプリチャージされる。尚、一致線MLは‘H’が「一致」を表す。

次に、検索ビット線を介して比較レジスタ101に記憶された検索データの各ビットが各CAMセル103に入力される。これにより、検索データSに応じて、検索ビット線対SL，SLNの何れか一方が‘H’、他方が‘L’となる。

メモリ・セル104に記憶されているデータDと検索データSとが一致する場合、ノード109のレベルは‘L’であり、nMOS108はオフ状態に保持される。

一方、データDと検索データSとが一致しない場合、ノード109のレベルは‘H’となり、nMOS108はオン状態になる。これにより、一致線MLはディスチャージされて‘L’状態となる。

mビットのCAMセル103からなるCAMワードの一致線MLは、各CAMセル103のnMOS108がパラレルに接続されたワイヤードOR回路を構成している。従って、1ワードを構成するmビットのCAMセル103のすべてにおいて一致が検出された場合に限り、一致線MLは‘H’（「一致」）の状態に保持される。一方、1ビットでもCAMセル103で不一致が検出されると、一致線MLは‘L’（「不一致」）の状態となる。

例えば、検索の結果、一致フラグレジスタMFR₁～MFR_nに、一致フラグとして‘0’，‘1’，‘1’，‘0’，…，‘1’，‘0’が格納されたとする。この場合、ワードW₂，W₃，…，W_n－1で一致が検出されている。従って、プライオリティ・エンコーダPEは、最も優先順位が高いワードW₂のアドレスをHMAとして出力する。また、一致フラグレジスタMFR₂に格納された一致フラグを‘0’にクリアすることで、その次に優先順位が高いワードW₃のアドレスをHMAとして出力することができる。以下同様にして、一致が検出されたワードのアドレスを順次出力することができる。

尚、TCAMとして使用する場合、ドント・ケアのビットについては、検索ビット線対SL，SLNをともに‘L’（＝‘0’）としておけばよい。

図10は、図8のCAMセルの別の例の構成回路図である。図10に示すCAMセル103’は一致検出型のものであり、図9と同様、SRAM構成のメモリ・セル104及び一致比較回路105を備えている。CAMセル103’は、図9のCAMセル103において、一致比較回路105のnMOS108の接続が異なる。図DのnMOS108は、一致線ML_aと一致線ML_bとの間に接続されている。nMOS108のゲートは、nMOS106，107の間のノード109に接続されている。

CAMセル103’では、検索時には、初期化動作として、ビット線対SL，SLNが共に‘H’とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS106，107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS106，107のうちオン状態の方を介して、両者の間のノード109のレベルが‘H’となり、nMOS108はオン状態となる。この状態で、一致線MLの一端が‘H’（＝‘1’）状態にプリチャージされる。尚、一致線MLは‘H’が「不一致」を表す。

mビットのCAMセル103’からなるCAMワードの一致線MLは、各CAMセル103’のnMOS108がシリアルに接続されたAND回路を構成する。従って、各々のCAMセルの一致線ML_a，ML_bは、各々のCAMセル103’のnMOS108を介して‘H’にプリチャージされる。

その後、検索ビット線を介して比較レジスタ101に記憶された検索データの各ビットが各CAMセル103’に入力される。これにより、検索データSに応じて、検索ビット線対SL，SLNの何れか一方が‘H’、他方が‘L’となる。

メモリ・セル104に記憶されているデータDと検索データSとが一致する場合、ノード109のレベルは‘H’であり、nMOS108はオン状態に保持される。

一方、データDと検索データSとが一致しない場合、ノード109のレベルは‘L’となり、nMOS108はオフ状態になる。

CAMワードのmビットのCAMセル103’のすべての状態が確定した後、一致線MLの一方の端部からディスチャージを開始し、他方の端部で一致比較結果を判定する。このとき、1ビットでも不一致のCAMセル103’がある場合には、一致比較結果は‘H’、すなわち、不一致の状態に保持される。一方、すべてのCAMセル103’で一致が検出された場合のみ、一致比較結果は‘L’、すなわち一致状態となる。

尚、TCAMとして使用する場合、ドント・ケアのビットについては、検索ビット線対SL，SLNをともに‘H’（＝‘1’）としておけばよい。

【特許文献1】特開2004－295967号公報

【特許文献2】特願2003－389264号明細書

【特許文献3】特開2004－258799号公報

【特許文献4】特開2004-258799号公報

【非特許文献1】菅野卓雄監修，香山晋編，「超高速デバイス・シリーズ2 超高速MOSデバイス」，初版，倍風館，1986年2月，pp．324－325．

【非特許文献2】電子情報通信学会編，「LSIハンドブック」，第1版，オーム社，1994年11月，pp．523－525．

【非特許文献3】Kostas Pagiamtzis and Ali Sheikholeslami, "A Low-Power Content-Addressable Memory (CAM) Using Pipelined Hierarchical Search Scheme", IEEE Journal of Solid-State Circuits, Vol.39, No.9, Sept.2004, pp.1512-1519.

【非特許文献4】T.Sasao, M.Matsuura, and Y.Iguchi, "A cascade realization of multi-output function for reconfigurable hardware", International Workshop on Logic and Synthesis (IWLS01), Lake Tahoe, CA, June 12-15, 2001, pp.225-230.

【非特許文献5】T.Sasao and M.Matsuura, "BDD representation for incompletely specified multiple-output logic functions and its applications to functional decomposition," Design Autonmation Conference, June 2005, (pp.373-378).

【非特許文献6】井口、笹尾、”LUTカスケード・アーキテクチャについて、” 平成15年電気学会 電子・情報・システム部門大会、MC2-4、2003年8月29日～30日、秋田大学。

本発明は、連想メモリ（内容検査メモリ：Content Addressable Memory：以下「CAM」という。）に関し、特に、高速検索が可能で、消費電力を抑え、且つ小さい実装面積で実装可能な連想メモリに関する。

• Storage device

• G11C  15/04      using semiconductor elements