Top > Search of Japanese Patents > (In Japanese)連想メモリ

(In Japanese)連想メモリ achieved

Patent code P110001685
File No. 5016PCT/JP
Posted date Mar 10, 2011
Application number P2008-510867
Patent number P4934825
Date of filing Mar 27, 2007
Date of registration Mar 2, 2012
International application number JP2007056498
International publication number WO2007119540
Date of international filing Mar 27, 2007
Date of international publication Oct 25, 2007
Priority data
  • P2006-101106 (Mar 31, 2006) JP
Inventor
  • (In Japanese)笹尾 勤
Applicant
  • (In Japanese)国立大学法人九州工業大学
Title (In Japanese)連想メモリ achieved
Abstract (In Japanese) 検索の高速性を維持しつつも、消費電力を抑え且つデバイスの構造を簡単化して小さい実装面積で実装可能な連想メモリを提供する。
CAM関数fの無効出力をドントケアで置換した簡略化CAM関数gのLUT結合論理回路で構成された簡略化関数演算部と、CAM関数fの逆関数f-1が記憶された補助メモリと、LUT演算手段の出力がCAM関数fの出力に一致するか判定する一致判定手段とを備え、LUT演算手段は、入力データに対し簡略化CAM関数gの演算値(仮インデックス値)を出力し、補助メモリは、仮インデックス値が入力されるとそれに対しする逆関数f-1の値を出力し、判定手段は、入力データと逆関数f-1の値とを比較して、両者が一致する場合はLUT演算手段の出力値を出力し、それ以外の場合は無効信号を出力する。
Outline of related art and contending technology (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}n→{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}n→{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個のワードW1~Wn、n個の一致センス回路MSC1~MSCn、n個の一致フラグレジスタMFR1~MFRn、及びプライオリティ・エンコーダ(優先度付符号化回路)PEを備えている。



比較レジスタ101は、mビットの検索データを格納するレジスタである。検索ビット線ドライバ102は、比較レジスタ101の各ビットを検索ビット線上にドライブする。各ワードW1~Wnは、それぞれ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のそれぞれのワードW1~Wnに、検索対象であるデータが記憶される。各ワード内の各CAMセル103において、メモリ・セル104へのデータの書き込み及びメモリ・セル104からのデータの読み出しは、通常のSRAMと同様にして行われる。



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



各々のワードW1~Wnでは、各CAMセルに予め記憶されているデータと検索ビット線上にドライブされた検索データとの一致検索が同時(並列)に実行され、その結果が一致線ML1~MLn上に出力される。これらの検索結果は、それぞれ一致センス回路MSC1~MSCnに入力される。各一致センス回路MSC1~MSCnは、各検索結果を増幅し、一致センス出力として一致センス出力線MT1~MTnに出力する。各一致センス出力は、一致フラグレジスタMFR1~MFRnに格納され、一致フラグ出力として一致フラグ出力出力線MF1~MFnに出力される。一致フラグは、‘1’が「一致あり」、‘0’が「一致なし」を表すものとする。



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



尚、各ワードW1~Wn内の各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’(「不一致」)の状態となる。



例えば、検索の結果、一致フラグレジスタMFR1~MFRnに、一致フラグとして‘0’,‘1’,‘1’,‘0’,…,‘1’,‘0’が格納されたとする。この場合、ワードW2,W3,…,Wn-1で一致が検出されている。従って、プライオリティ・エンコーダPEは、最も優先順位が高いワードW2のアドレスをHMAとして出力する。また、一致フラグレジスタMFR2に格納された一致フラグを‘0’にクリアすることで、その次に優先順位が高いワードW3のアドレスを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は、一致線MLaと一致線MLbとの間に接続されている。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セルの一致線MLa,MLbは、各々の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日、秋田大学。

Field of industrial application (In Japanese)


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

Scope of claims (In Japanese)
【請求項1】
  入力データに対しそのデータに対応する固有のインデックスを出力する連想記憶メモリであって、
入力データに対しそのデータに対応する固有のインデックスを出力する関数(以下「CAM(Content Addressable Memory)関数」という。)fの無効出力値をドント・ケアで置き換えた関数(以下「簡略化CAM関数」という。)gを表すLUT結合論理回路又はPLAにより構成された簡略化関数演算部と、
前記CAM関数fの逆関数f-1が記憶された補助メモリと、
前記簡略化関数演算部の出力値が、前記入力データに対するCAM関数fの出力に一致するか否かを判定し、一致する場合には前記簡略化関数演算部の出力値を出力し、それ以外の場合は無効信号を出力する一致判定手段と、
を備え、
前記簡略化関数演算部は、前記入力データに対して前記簡略化CAM関数gの演算値(以下「仮インデックス値」という。)を前記補助メモリの読み出しアドレスとして出力し、
前記補助メモリは、前記仮インデックス値が読み出しアドレスとして入力されると、その仮インデックス値に対しする逆関数f-1の値を出力し、
前記一致判定手段は、前記入力データと前記補助メモリが出力する逆関数f-1の値とを比較して、両者が一致する場合は前記簡略化関数演算部の出力値を出力し、それ以外の場合は無効信号を出力すること
を特徴とする連想メモリ。
【請求項2】
  前記LUT結合論理回路は、LUTカスケード論理回路であることを特徴とする請求項1記載の連想メモリ。
【請求項3】
  前記LUT結合論理回路は、pq回路網であることを特徴とする請求項1記載の連想メモリ。
Industrial division
  • Storage device
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2008510867thum.jpg
State of application right Right is in force
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close