TOP > 国内特許検索 > 連想メモリ > 明細書

明細書 :連想メモリ

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4934825号 (P4934825)
登録日 平成24年3月2日(2012.3.2)
発行日 平成24年5月23日(2012.5.23)
発明の名称または考案の名称 連想メモリ
国際特許分類 G11C  15/04        (2006.01)
FI G11C 15/04 D
請求項の数または発明の数 3
全頁数 19
出願番号 特願2008-510867 (P2008-510867)
出願日 平成19年3月27日(2007.3.27)
国際出願番号 PCT/JP2007/056498
国際公開番号 WO2007/119540
国際公開日 平成19年10月25日(2007.10.25)
優先権出願番号 2006101106
優先日 平成18年3月31日(2006.3.31)
優先権主張国 日本国(JP)
審査請求日 平成21年7月3日(2009.7.3)
特許権者または実用新案権者 【識別番号】504174135
【氏名又は名称】国立大学法人九州工業大学
発明者または考案者 【氏名】笹尾 勤
個別代理人の代理人 【識別番号】100121371、【弁理士】、【氏名又は名称】石田 和人
審査官 【審査官】堀江 義隆
参考文献・文献 特開2004-229163(JP,A)
特開2002-334114(JP,A)
特開2000-105770(JP,A)
調査した分野 G11C 15/04
G06F 7/00
G06F 17/30
特許請求の範囲 【請求項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記載の連想メモリ。
発明の詳細な説明 【技術分野】
【0001】
本発明は、連想メモリ(内容検査メモリ:Content Addressable Memory:以下「CAM」という。)に関し、特に、高速検索が可能で、消費電力を抑え、且つ小さい実装面積で実装可能な連想メモリに関する。
【背景技術】
【0002】
通常のメモリは、与えられたインデックス(アドレス)に対して、そのアドレスに格納されている登録データを生成する。一方、CAMは、与えられた検索(入力)データに対して、それを格納するCAMのインデックス(アドレス)を生成する(非特許文献1,2参照)。
【0003】
CAMは、パターン・マッチング、インターネットのルータ、プロセッサのキャッシュ、TLB(Translation Lookaside Buffer)、データ圧縮、データベースのアクセラレータ、ニューラルネット、メモリパッチなど幅広い分野において利用されている。
【0004】
通常、CAMは、その機能から、2値CAM(Binary CAM:以下「BCAM」という。)及び3値CAM(Ternary CAM:以下「TCAM」という。)の二種類に分類される。BCAMでは、各セルに0及び1を格納する。TCAMでは各セルに0,1,及び*を格納する。ここで、「*」はドント・ケア(don't care)を表し、0と1の両方にマッチする。
【0005】
〔定義1〕(BCAM)
n入力で登録データ数pのBCAMテーブルは、p個の異なる2値ベクトルを格納する。また、p個のベクトルは、アドレス1からアドレスpに順に格納されていると仮定する。また、各ベクトルのアドレスはmビットで表現可能である。mは次式(1)により表される。
【0006】
【数1】
JP0004934825B2_000002t.gif
また、p個のベクトルは、アドレス1からアドレスpに順に格納されていると仮定する。対応するBCAM関数f:{0,1}n→{0,1}mは、以下の条件を満たす:
f(x)は入力xと同じベクトルがBCAMテーブル中にあるとき、ベクトルxを格納するCAMのアドレス(1からpの値の何れか)を出力する。入力xと同じパターンがBCAMテーブル中に無い場合には、f(x)の値は0である。
(定義終り)
【0007】
(例1)
(表1)は、7個の2値ベクトルを格納するBCAMを示す。対応するBCAM関数を(表2)に示す。何れも、入力データに完全に一致したベクトルを格納するアドレスを3ビットの数(例えば、‘011’)として出力する。入力ベクトルと一致するものがBCAM中に格納されていない場合には、0を出力する。
(例終わり)
【0008】
【表1】
JP0004934825B2_000003t.gif

【0009】
【表2】
JP0004934825B2_000004t.gif

【0010】
〔定義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を出力する。
(定義終り)
【0011】
(例2)
(表3)に示すTCAMは、7個の3値ベクトルを格納する。対応するTCAM関数を(表4)に示す。入力x=(1,0,1,1)は、アドレス5及び6に蓄えられているパターンと一致する。5の方が小さいので、出力は(0,1,0,1)となる。
(例終わり)
【0012】
【表3】
JP0004934825B2_000005t.gif

【0013】
【表4】
JP0004934825B2_000006t.gif

【0014】
CAMの機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェア(半導体メモリ)を用いてCAMを実現することが多い。以下、ハードウェアで構成された従来のCAMについて説明する。
【0015】
図8は、従来のCAMの基本構成の一例を表すブロック図である(特許文献1参照)。CAM100は、比較レジスタ101、検索ビット線ドライバ102、n個のワードW~W、n個の一致センス回路MSC~MSC、n個の一致フラグレジスタMFR~MFR、及びプライオリティ・エンコーダ(優先度付符号化回路)PEを備えている。
【0016】
比較レジスタ101は、mビットの検索データを格納するレジスタである。検索ビット線ドライバ102は、比較レジスタ101の各ビットを検索ビット線上にドライブする。各ワードW~Wは、それぞれmビットのCAMセルを備えている。
【0017】
図9は、図8のCAMセルの構成回路図である。図9に例示したCAMセル103は、不一致検出型のものである。CAMセル103は、メモリ・セル104及び一致比較回路105から構成される。メモリ・セル104は、1ビットのデータを記憶するSRAM構成のメモリ・セルである。図9においてDがデータ、DNが反転データを表す。一致比較回路105は、メモリ・セル104に記憶された1ビットのデータと検索ビット線対SL,SLN上にドライブされる検索データとを比較し、その一致比較結果を一致線ML上に出力する。
【0018】
一致比較回路105は、3つのnMOSトランジスタ(以下「nMOS」という。)106,107,108を備えている。nMOS106,107は、検索ビット線SLNと検索ビット線SLとの間に直列に接続されている。nMOS106,107のゲートは、それぞれ、メモリ・セル104のデータD,反転データDNに接続されている。nMOS108は、一致線MLとグランドとの間に接続されている。nMOS108のゲートは、nMOS106,107の間のノード109に接続されている。
【0019】
まず、検索を行う前に、CAM100のそれぞれのワードW~Wに、検索対象であるデータが記憶される。各ワード内の各CAMセル103において、メモリ・セル104へのデータの書き込み及びメモリ・セル104からのデータの読み出しは、通常のSRAMと同様にして行われる。
【0020】
検索時には、まず、比較レジスタ101に検索データが格納される。検索データの各のビットは、検索ビット線ドライバ102により、各々対応する検索ビット線上にドライブされる。
【0021】
各々のワードW~Wでは、各CAMセルに予め記憶されているデータと検索ビット線上にドライブされた検索データとの一致検索が同時(並列)に実行され、その結果が一致線ML~ML上に出力される。これらの検索結果は、それぞれ一致センス回路MSC~MSCに入力される。各一致センス回路MSC~MSCは、各検索結果を増幅し、一致センス出力として一致センス出力線MT~MTに出力する。各一致センス出力は、一致フラグレジスタMFR~MFRに格納され、一致フラグ出力として一致フラグ出力出力線MF~MFに出力される。一致フラグは、‘1’が「一致あり」、‘0’が「一致なし」を表すものとする。
【0022】
各一致フラグ出力は、プライオリティ・エンコーダPEに入力される。プライオリティ・エンコーダPEでは、所定の優先順位付けに従って、一致が検出されたワードの中から最優先順位のワードのアドレス(最優先一致アドレス:HMA)を選択し出力する。各ワードの優先順位は、ワードWが最も高く、Wに向かうに従って順次優先順位が低くなるものとする。
【0023】
尚、各ワードW~W内の各CAMセル103における一致検索は、次のようにして実行される。
【0024】
まず、初期化動作を実行する。初期化動作では、検索ビット線対SL,SLNがともに‘L’(=‘0’)とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS106,107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS106,107のうちオン状態の方を介して、両者の間のノード109のレベルが‘L’となり、nMOS108はオフ状態となる。この状態で、一致線MLが‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「一致」を表す。
【0025】
次に、検索ビット線を介して比較レジスタ101に記憶された検索データの各ビットが各CAMセル103に入力される。これにより、検索データSに応じて、検索ビット線対SL,SLNの何れか一方が‘H’、他方が‘L’となる。
【0026】
メモリ・セル104に記憶されているデータDと検索データSとが一致する場合、ノード109のレベルは‘L’であり、nMOS108はオフ状態に保持される。
【0027】
一方、データDと検索データSとが一致しない場合、ノード109のレベルは‘H’となり、nMOS108はオン状態になる。これにより、一致線MLはディスチャージされて‘L’状態となる。
【0028】
mビットのCAMセル103からなるCAMワードの一致線MLは、各CAMセル103のnMOS108がパラレルに接続されたワイヤードOR回路を構成している。従って、1ワードを構成するmビットのCAMセル103のすべてにおいて一致が検出された場合に限り、一致線MLは‘H’(「一致」)の状態に保持される。一方、1ビットでもCAMセル103で不一致が検出されると、一致線MLは‘L’(「不一致」)の状態となる。
【0029】
例えば、検索の結果、一致フラグレジスタMFR~MFRに、一致フラグとして‘0’,‘1’,‘1’,‘0’,…,‘1’,‘0’が格納されたとする。この場合、ワードW,W,…,Wn-1で一致が検出されている。従って、プライオリティ・エンコーダPEは、最も優先順位が高いワードWのアドレスをHMAとして出力する。また、一致フラグレジスタMFRに格納された一致フラグを‘0’にクリアすることで、その次に優先順位が高いワードWのアドレスをHMAとして出力することができる。以下同様にして、一致が検出されたワードのアドレスを順次出力することができる。
【0030】
尚、TCAMとして使用する場合、ドント・ケアのビットについては、検索ビット線対SL,SLNをともに‘L’(=‘0’)としておけばよい。
【0031】
図10は、図8のCAMセルの別の例の構成回路図である。図10に示すCAMセル103’は一致検出型のものであり、図9と同様、SRAM構成のメモリ・セル104及び一致比較回路105を備えている。CAMセル103’は、図9のCAMセル103において、一致比較回路105のnMOS108の接続が異なる。図DのnMOS108は、一致線MLと一致線MLとの間に接続されている。nMOS108のゲートは、nMOS106,107の間のノード109に接続されている。
【0032】
CAMセル103’では、検索時には、初期化動作として、ビット線対SL,SLNが共に‘H’とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS106,107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS106,107のうちオン状態の方を介して、両者の間のノード109のレベルが‘H’となり、nMOS108はオン状態となる。この状態で、一致線MLの一端が‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「不一致」を表す。
【0033】
mビットのCAMセル103’からなるCAMワードの一致線MLは、各CAMセル103’のnMOS108がシリアルに接続されたAND回路を構成する。従って、各々のCAMセルの一致線ML,MLは、各々のCAMセル103’のnMOS108を介して‘H’にプリチャージされる。
【0034】
その後、検索ビット線を介して比較レジスタ101に記憶された検索データの各ビットが各CAMセル103’に入力される。これにより、検索データSに応じて、検索ビット線対SL,SLNの何れか一方が‘H’、他方が‘L’となる。
【0035】
メモリ・セル104に記憶されているデータDと検索データSとが一致する場合、ノード109のレベルは‘H’であり、nMOS108はオン状態に保持される。
【0036】
一方、データDと検索データSとが一致しない場合、ノード109のレベルは‘L’となり、nMOS108はオフ状態になる。
【0037】
CAMワードのmビットのCAMセル103’のすべての状態が確定した後、一致線MLの一方の端部からディスチャージを開始し、他方の端部で一致比較結果を判定する。このとき、1ビットでも不一致のCAMセル103’がある場合には、一致比較結果は‘H’、すなわち、不一致の状態に保持される。一方、すべてのCAMセル103’で一致が検出された場合のみ、一致比較結果は‘L’、すなわち一致状態となる。
【0038】
尚、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日、秋田大学。
【発明の開示】
【発明が解決しようとする課題】
【0039】
上記従来のCAMは、RAMに比べると、並列に検索可能であるため高速であるが、デバイスの構成は複雑となる。そのため、CAMの1ビットあたりの価格(ビットコスト)は、RAMに比べると10~30倍程度、高価なものになる。
【0040】
また、1ビットあたりの消費電力がRAMに比べて遙かに大きい(非特許文献3参照)。これは、上で説明したように、すべてのCAMセルを同時にアクセスするためである。そのため、1ビットあたりの消費電力は、通常のRAMの約50倍程度にもなる。
【0041】
そこで、本発明の目的は、検索の高速性を維持しつつも、消費電力を抑え且つデバイスの構造を簡単化して小さい実装面積で実装可能な連想メモリを提供することにある。
【課題を解決するための手段】
【0042】
以下、本明細書において使用する用語の定義及び本発明の前提となる理論を説明し、その後本発明の構成及び作用について説明する。
【0043】
〔1〕CAM関数の性質
〔定義3〕(分解表、基本分解表、列複雑度)
関数f(X) : Bn→Bq、及びX=(x1,x2,…,xn)が与えられているものとする。ここで、B={0,1}である。(XL, XH)をXの分割とする。fの「分解表」とは、二次元のマトリックスであって、列のラベルは、XLにBの構成要素をすべての可能な組み合わせに対して割り当てたものであり、また行のラベルは、XHにBの構成要素をすべての可能な組み合わせに対して割り当てたものである。また、対応するマトリックスの値はf(XL,XH)の値に等しい。
関数fの分解表のうちで、XL=(x1, x2, …, xnL)且つXH=(xnL+1, xnL+2, …, xn)となる分解表を「基本分解表」という。
分解表の異なる列パターンの個数を分解表の「列複雑度」という。
尚、分解表の特別な場合として、XL=Xの場合も考える。
(定義終り)
【0044】
〔定義4〕(C尺度)
変数の順序を(x1,x2,…,xn)としたとき、論理関数fの基本分解表の列複雑度の最大値を、fの「C尺度」という。
(定義終り)
【0045】
(例3)
f1=x1x2∨x3x4∨x5x6のC尺度は3であるが、f2=x1x5∨x2x6∨x3x4のC尺度は8である。
(例終わり)
【0046】
分解表の列複雑度は、MTBDD(多端子二分決定グラフ)の幅に等しい。従って、論理関数のC尺度は、与えられた入力変数の順におけるMTBDDの幅の最大値に等しい。与えられた論理関数f(x1,x2,…,xn)に対して、C尺度は容易に計算でき、一意的に定まる。後述するように、C尺度が小さい関数は、LUTカスケード(LUT (Lookup-table) cascade)で効率的に実現可能である。従って、C尺度は、論理関数をLUTカスケードで実現する際の複雑さの尺度となる。
【0047】
〔補題1〕
与えられた関数fに対して、非零出力を生ずる入力の組み合わせの個数をpとする。このとき、fのC尺度は高々p+1である。
(補題終り)
【0048】
〔定理1〕(BCAM関数のC尺度)
要素数pのBCAMテーブルが与えられたとき、そのBCAM関数のC尺度は高々p+1である。
(定理終り)
【0049】
〔定理2〕(TCAM関数のC尺度)
TCAMテーブルがp個のベクトルを格納し、各ベクトルが高々k個のドント・ケアを有するとき、対応するTCAM関数のC尺度は高々2kp+1である。
(定理終り)
【0050】
〔2〕LUTカスケード
CAM関数は通常のRAMでも実現可能である。例えば、上記(表1)に示した要素7のBCAM関数は、(表2)に示したように、16ワードのRAMにより実現することができる。ここで、各ワードは3ビットである。n入力のCAM関数を単一のRAMで実現する場合、RAMの大きさは、BCAMがわずか数個のベクトルしか含まない場合であっても、2nに比例して大きくなる。そこで、LUTカスケードを用いることにより、必要なメモリ量を大幅に削減することが可能となる(特許文献3参照)。
【0051】
〔定理3〕
与えられた関数fに対して、XLを分解表の列に対応する変数、XHを行に対応する変数とし、μを分解表の列複雑度とする。このとき、関数fは図1に示すような回路で実現することが可能である。この場合、二つのブロックHとGの間を結ぶ信号線数(以下「レイル数」という。)は
【0052】
【数2】
JP0004934825B2_000007t.gif
である。
(定理終り)
【0053】
二つのブロック間を結ぶ信号線数がXL中の変数の個数よりも少ないとき、関数を実現するためのメモリ量を削減できる可能性がある。この手法を「関数分解」という。与えられた関数を繰り返し関数分解することにより、図2に示すようなLUTカスケードが得られる(非特許文献4参照)。LUTカスケードは「セル」から構成され、隣接するセル間を接続する信号線を「レイル」という。C尺度が小さな関数は小型のLUTカスケードで実現可能である。C尺度を求めるには、必ずしも分解表を使用する必要はなく、多出力関数の特性関数を表現する二分決定グラフ(Binary Decision Diagram for Characteristic Function:以下「BDD_for_CF」という。)から効率的に計算することができる(特許文献2,非特許文献5参照)。
【0054】
〔定理4〕
C尺度がμの論理関数は、入力数が高々
【0055】
【数3】
JP0004934825B2_000008t.gif
出力数が
【0056】
【数4】
JP0004934825B2_000009t.gif
のセルから構成されたLUTカスケードで実現可能である。
(定理終り)
【0057】
〔定理5〕
関数fを実現するLUTカスケードを考える。いま、nを外部入力変数、sをセル数、rを最大レイル数(即ち、セル間の信号線数)、kをセルの最大入力数、μを関数fのC尺度とする。
【0058】
【数5】
JP0004934825B2_000010t.gif
が成立するとき、以下の関係を満たすfを実現するLUTカスケードが存在する。
【0059】
【数6】
JP0004934825B2_000011t.gif
(定理終り)
【0060】
〔3〕ドント・ケアを用いた設計法
〔3-1〕BCAM関数の設計法
BCAM関数では、真理値表において、非零出力の値が、全体の組み合わせの数2nに比べて大幅に少ない。つまり、次の(仮定1)が成立するものとする。
【0061】
(仮定1) BCAMテーブルの入力ビット数をn、ベクトル数をpとするとき、p≪2n
【0062】
例えば、n=32でp=1000のBCAMを考えるとき、非零出力の割合は全最小項の個数の1000/232=2.3×10-7となる。
【0063】
BCAM関数をBDDで表現すると、BDDの最大幅が、C尺度を超えないこと、及び〔定理1〕から、レイル幅はp+1を超えないことがわかる。しかし、全体の幅はp+1近くなる。従って、BCAM関数をLUTカスケードで実現する場合、入力数が
【0064】
【数7】
JP0004934825B2_000012t.gif
のセルが多数必要となる。そこで、ここではドント・ケアの概念を用いて、BCAM関数を実現するハードウェア量を削減する方法について、図3を参照しながら説明する。
【0065】
〔アルゴリズム1〕
(1)fをBCAM関数とする。また、fにおいてCAMに登録されていないデータに対する出力値をドント・ケアとした関数をgとする。
【0066】
(2)gの特性関数を表現する二分決定グラフ(BDD_for_CF)を生成し、簡単化を行う。
【0067】
(3)簡単化したBDDから、LUTカスケード1を生成する。一般に、LUTカスケード1は、fを実現するLUTカスケード(これを「厳密なLUTカスケード」と呼ぶ。)よりも簡単になる。
【0068】
(4)検索データが登録データと一致するときは、LUTカスケード1は正しい値を出力する。検索データが登録データと一致しないときは、LUTカスケード1は、誤った値を出力する可能性がある。
【0069】
(5)誤りを補正するために、m入力n出力の補助メモリ2を用いる。ここで、mは次式で表される。
【0070】
【数8】
JP0004934825B2_000013t.gif
この補助メモリ2には、各アドレスにBCAMテーブルの対応するデータが格納されている。
【0071】
(6)LUTカスケード1の出力のインデックスを補助メモリ2に供給し、補助メモリ2内の登録データを読み出す。そして、一致回路3により、入力データと補助メモリ2の出力データとを比較する。両者が一致すれば、LUTカスケード1の出力値は正しいことが保証される。従ってエンコーダ4はLUTカスケード1の出力のインデックスをそのまま出力する。一方、補助メモリ2の出力データと入力データとが一致しないときは、CAM内にそのデータは登録されていない。従って、そのときには、エンコーダ4は無効のインデックス(0)を出力する。
(アルゴリズム終り)
【0072】
補助メモリ2の全ビット数は、n2mであり、ハードウェアのコストは、LUTカスケード1のコストに比べ無視できる程度である。
【0073】
〔3-2〕TCAM関数の設計法
TCAM関数の場合、TCAMテーブルは3値となるので、補助メモリ2は、m入力2n出力となる。また、一致回路3で、ドント・ケアに対応するビットは無視する。他の部分はBCAMと同じである。
【0074】
〔1〕本発明の構成
本発明に係る連想メモリの構成は、入力データに対しそのデータに対応する固有のインデックスを出力する連想記憶メモリであって、
入力データに対しそのデータに対応する固有のインデックスを出力する関数(以下「CAM(Content Addressable Memory)関数」という。)fの無効出力値をドント・ケアで置き換えた関数(以下「簡略化CAM関数(reduced Content Addressable Memory function)」という。)gを表すLUT結合論理回路又はPLA(Programmable Logic Array)により構成された簡略化関数演算部と、
前記CAM関数fの逆関数f-1が記憶された補助メモリと、
前記簡略化関数演算部の出力値が、前記入力データに対するCAM関数fの出力に一致するか否かを判定し、一致する場合には前記簡略化関数演算部の出力値を出力し、それ以外の場合は無効信号を出力する一致判定手段と、
を備え、
前記簡略化関数演算部は、前記入力データに対して前記簡略化CAM関数gの演算値(以下「仮インデックス値」という。)を前記補助メモリの読み出しアドレスとして出力し、
前記補助メモリは、前記仮インデックス値が読み出しアドレスとして入力されると、その仮インデックス値に対しする逆関数f-1の値を出力し、
前記一致判定手段は、前記入力データと前記補助メモリが出力する逆関数f-1の値とを比較して、両者が一致する場合は前記簡略化関数演算部の出力値を出力し、それ以外の場合は無効信号を出力することを特徴とする。
【0075】
この構成によれば、LUT結合論理回路は、通常のRAMを複数個用いて構成することができる。また、補助メモリも通常のRAMで構成できる。また、CAM関数fそのものを表すLUT結合論理回路ではなく、CAM関数fの無効出力値をドント・ケアで置き換えた簡略化関数gを表すLUT結合論理回路又はPLAを用いることによって、当該LUT結合論理回路又はPLAを構成するために必要なメモリ量を大幅に削減することができる。従って、全体として、従来のCAMに比べ、デバイスの構造を簡単化して小さい実装面積により実装が可能となる。
【0076】
また、通常のRAMで構成することによって、専用のCAM回路を必要としない。故に、ASICで構成する以外に、汎用のRAMを内蔵したFPGA(Field Programmable Gate Array)やCLD(Complex Programmable Logic Device)のようなプログラマブル・デバイスを用いて簡単に低コストで構成することもできる。
【0077】
また、一致判定手段以外はすべて通常のRAMで構成できる。そして、1回の検索動作に対して、数回(LUT結合論理回路でのRAMのアクセス回数+1)のRAMのアクセスで仮インデックス値が得られる。各RAMのアクセスでは、RAM内の1つのアドレスのみがアクセスされる。全体として、数回のRAMのメモリ・アクセスのみで仮インデックス値が得られる。従って、従来のCAMに比べると、消費電力を大幅に低減することが可能となる。


【0078】
一方、高速性の面では、従来のCAMに比べると遅くなるものの、通常のRAMをCPUを用いて検索する方法に比べると遙かに高速に検索を行うことができる。
【0079】
ここで、「LUT結合論理回路」とは、複数のLUT(Look-Up Table)をカスケード状又はネットワーク状に結合した回路をいうが、必ずしもハードウェア的に複数のLUTを配置・結合する必要はない。例えば、1つのメモリ内に複数のLUTを記憶させ、LUTの選択を順次切り替えながら、メモリの出力値をメモリの読み出しアドレスにフィードバックすることによってLUT結合を実現するような回路であってもよい。LUT結合論理回路としては、LUTカスケード論理回路の他に、LUTをネットワーク状に結合したLUTネットワークなどを使用することも可能である。
【0080】
尚、本発明はBCAM及びTCAMの双方に適用することが可能である。
【発明の効果】
【0081】
以上のように、本発明によれば、検索の高速性を維持しつつ、消費電力を抑え且つデバイスの構造を簡単化して小さい実装面積で実装可能な連想メモリを提供することができる。
【図面の簡単な説明】
【0082】
【図1】論理関数の関数分解を表す図である。
【図2】中間出力を有するLUTカスケードを表す図である。
【図3】ドント・ケアを用いたCAM関数の実現法を説明する図である。
【図4】本発明の実施例1に係る連想メモリの全体構成を表す図である。
【図5】図4の簡略化関数演算部5の構成を表す図である。
【図6】図4の一致判定手段7の構成を表す図である。
【図7】実施例2に係る連想メモリの一致判定手段7の構成を表す図である。
【図8】従来のCAMの基本構成の一例を表すブロック図である。
【図9】図8のCAMセルの構成回路図である。
【図10】図8のCAMセルの別の例の構成回路図である。
【符号の説明】
【0083】
1 LUTカスケード
2 補助メモリ
3 一致回路
4 エンコーダ
5 簡略化関数演算部
6 補助メモリ
7 一致判定手段
10 連想メモリ
11 入力変数レジスタ
12-1~12-s 論理関数メモリ
13 出力変数レジスタ
21 EXNORゲート
22 ANDゲート
23 ANDゲート
31 pq素子
【発明を実施するための最良の形態】
【0084】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例1】
【0085】
図4は、本発明の実施例1に係る連想メモリの全体構成を表す図である。本実施例の連想メモリ10は、簡略化関数演算部5、補助メモリ6、及び一致判定手段7を備えている。
【0086】
連想メモリ10は、外部回路から入力されるnビットの入力データX=(x1,…,xn)に対しその入力データXに対応するmビットの固有のインデックスA=(a1,…,am)を出力する。入力データXは、簡略化関数演算部5及び一致判定手段7に入力される。
【0087】
以下では、入力データXに対しその入力データXに対応する固有のインデックスAを出力するCAM関数を、Fと記す。また、CAM関数Fの出力のうち、無効なインデックス値をドント・ケアで置き換えた簡略化CAM関数を、Gと記す。
【0088】
簡略化関数演算部5は、簡略化CAM関数Gを演算するLUT結合論理回路により構成されている。簡略化関数演算部5は、入力データXに対し仮インデックスA'=G(X)を演算する。この仮インデックスA'は、補助メモリ6及び一致判定手段7に出力される。
【0089】
補助メモリ6は、CAM関数Fの逆関数F-1、すなわち、固有のインデックスAに対しそのインデックスAに対応するデータXを出力するデータ出力関数が、LUTとして記憶されている。補助メモリ6には、簡略化関数演算部5が出力する仮インデックスA'が入力され、それに対する逆算データX'=F-1(A')が出力される。仮インデックスA'は、一致判定手段7に出力される。
【0090】
一致判定手段7は、入力データXと逆算データX'とを比較し、両者が一致するか否かを判定する。そして、両者が一致する場合には仮インデックスA'を出力インデックスAとして出力し、一致しない場合には無効値を出力する。
【0091】
図5は、図4の簡略化関数演算部5の構成を表す図である。本実施例1においては、簡略化関数演算部5として、LUTカスケード論理回路を用いる。
【0092】
簡略化関数演算部5は、入力変数レジスタ11、論理関数メモリ12-1~12-s、及び出力変数レジスタ13を備えている。
【0093】
入力変数レジスタ11は、外部から入力される入力データXを一時的に保持するレジスタである。論理関数メモリ12-1~12-sは、簡略化CAM関数Gを関数分解して得られるCAM関数Gの部分関数G1,…,GsがLUTとして格納されている。ここで、Xの分割をX=(X1,X2,…,Xs)とした場合、各部分関数G1,…,Gsは次のようになる。
【0094】
【数9】
JP0004934825B2_000014t.gif

【0095】
ここでは、ベクトルA1',A2',…,As-1'は、LUTカスケードの中間出力であり、ベクトルAs'はLUTカスケードの最終出力である。仮インデックスA'は、これらのベクトルの合成として表される。また、ベクトルR1,R2,…,Rs-1は、LUTカスケードの中間変数を表す。
【0096】
出力変数レジスタ13は、各論理関数メモリ12-1~12-sが出力する中間出力A1',A2',…,As-1'及び最終出力As'を保持し、仮インデックスA'として出力するレジスタである。
【0097】
尚、LUTカスケード論理回路の詳しい動作については、特許文献4及び非特許文献6に記載されているため、ここでは説明を省略する。
【0098】
図6は、図4の一致判定手段7の構成を表す図である。図6では、一例として、入力データXが8ビット、出力インデックスAが8ビットの場合を示しているが、入力データX及び出力インデックスAのビット数はこれに限られるものではない。
【0099】
一致判定手段7は、入力データXの各ビットに対応して設けられたEXNORゲート21、1個のANDゲート22、及び出力インデックスAの各ビットに対応して設けられたANDゲート23により構成される。
【0100】
入力データX及び逆算データX'の各ビットxi, xi'(i=1,2,…,8)は、それぞれ対応するEXNORゲート21に入力され、EXNOR演算が行われる。各EXNORゲート21の演算結果は、ANDゲート22に入力され、AND演算が行われる。このANDゲート22の出力Qを、一致判定信号と呼ぶ。
【0101】
一方、仮インデックスA'の各ビットa1',a2',…,a8'は、それぞれ各ANDゲート23の一方の入力ノードに入力される。また、各ANDゲート23の他方の入力ゲートには、一致判定信号Qが入力される。
【0102】
以上のように構成された本実施例に係る連想メモリ10について、以下その動作を説明する。
【0103】
まず、外部回路から入力データXが入力されると、簡略化関数演算部5は、CAM関数G(X)の演算を行い、その結果を仮インデックスA'として出力する。ここで、入力データXに対する真のインデックスが存在する場合、仮インデックスA'の値は真のインデックスの値に一致する。一方、真のインデックスが存在しない場合には、仮インデックスA'の値はドント・ケアとなる。従って、仮インデックスA'は真のインデックスを含むものの、その値が真のインデックスを表すのかドント・ケアを表すのかの判別はできない。
【0104】
次に、仮インデックスA'は補助メモリ6に入力される。補助メモリ6は、仮インデックスA'に対してデータ出力関数F-1(A')のLUT演算を行い、その結果を逆算データX'= F-1(A')として出力する。このとき、仮インデックスA'は真のインデックスを表す場合には、逆算データX'は入力データXと同じ値となる。しかし、仮インデックスA'がドント・ケアの場合には、仮インデックスA'はデタラメな値なので、逆算データX'には無効値が出力される。
【0105】
次に、一致判定手段7のi番目のEXNORゲート21(i=1,2,…,8)には、それぞれ入力データXのi番目の成分xiと逆算データX'のi番目の成分xi'とが入力される。EXNORゲート21は、論理演算
【0106】
【数10】
JP0004934825B2_000015t.gif
を行い、演算値qiを出力する。演算値qiの値は、成分xiと成分xi'とが一致する場合は1、一致しない場合は0となる。
【0107】
各演算値qiは、ANDゲート22に入力され、AND演算が行われる。これにより、入力データXと逆算データX'の各成分が完全に一致する場合には一致判定信号Qは1となり、それ以外の場合には一致判定信号Qは0となる。従って、この一致判定信号Qを用いることによって、仮インデックスA'が真のインデックス値を表しているか否かの判別ができる。
【0108】
i番目のANDゲート23(i=1,2,…,8)には、それぞれ仮インデックスA'のi番目の成分xiと一致判定信号Qが入力される。そして、各ANDゲート23はこれらのAND演算を行い、その結果を出力インデックスAのi番目の成分aiとして出力する。これにより、仮インデックスA'が真のインデックス値を表している場合には、出力インデックスAとして真のインデックス値が出力され、それ以外の場合は出力インデックスAとして0が出力される。
【0109】
以上のようにして、入力データXに対するCAM関数の演算が行われる。上述のように、本実施の形態では、簡略化関数演算部5及び補助メモリ6はすべてメモリで構成されているため、通常のRAMを用いて構成することが可能である。従って、プロセスの微細化が容易であり回路規模を小さくすることができる。また、メモリであるため、使用しない期間を省電力状態として消費電力の節減を図ることも可能である。
【実施例2】
【0110】
本実施例2に係る連想メモリの全体構成及び一致判定手段7の構成は、図4,図6と同様であり、説明は省略する。実施例2に係る連想メモリは、簡略化関数演算部5の構成が実施例1とは異なる。
【0111】
図7は、実施例2に係る連想メモリの簡略化関数演算部5の構成を表す図である。本実施例の簡略化関数演算部5は、複数のpq素子31を樹形状に結合した構成からなる。pq素子31は、p入力q出力のメモリである。各pq素子31のp,qの値はそれぞれのpq素子31ごとに任意に設定される。各pq素子31には、簡略化CAM関数Gを関数分解して得られる部分関数G1,G2,…がLUTとして格納されている。このように複数のpq素子31を樹形状に結合した回路をここでは「pq回路網」と呼ぶ。
【0112】
尚、図7の構成は一例であり、pq素子31の結合の仕方は、CAM関数Gにより適宜選択される。
【0113】
このように、簡略化関数演算部5としてpq回路網を使用しても、実施例1と同様の連想メモリを構成することができる。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9