ASSOCIATED MEMORY
| Foreign code | F110002470 |
|---|---|
| File No. | 5016PCT |
| Posted date | 2011年3月8日 |
| Country | 世界知的所有権機関（ＷＩＰＯ） |
| International application number | 2007JP056498 |
| International publication number | WO 2007/119540 |
| Date of international filing | 平成19年3月27日(2007.3.27) |
| Date of international publication | 平成19年10月25日(2007.10.25) |
| Priority data |
|
| Title |
ASSOCIATED MEMORY
|
| Abstract | An associated memory is provided with features of suppression of power consumption and a device structure to be simplified with a small installing area while maintaining high speed retrieval. The associated memory is comprised of a simplified function operation unit made of an LUT coupled logic circuit of a simplified CAM function (g) in which an invalid output of the CAM function (f) is replaced by don't-care, an auxiliary memory in which a reverse function (f-1) of the CAM function (f) is stored, and a consistency judging means for judging whether an output of an LUT operating means is consistent with an output of the CAM function (f), wherein the LUT operating means outputs an operated value (tentative index value) of the simplified CAM function (g) for input data, the auxiliary memory outputs the reverse function (f-1) of the tentative index value when the tentative index value is input, and the judging means compares the input date with the reverse function (f-1) and outputs an output value of the LUT operating means when the input data and the output value are consistent with each other but, otherwise, outputs an invalid signal. |
|
|
|
|
| IPC(International Patent Classification) |
|
| Specified countries | AE(UTILITY MODEL),AG,AL(UTILITY MODEL),AM(PROVISIONAL PATENT)(UTILITY MODEL),AT(UTILITY MODEL),AU,AZ(UTILITY MODEL),BA,BB,BG(UTILITY MODEL),BH,BR(UTILITY MODEL),BW,BY(UTILITY MODEL),BZ(UTILITY MODEL),CA,CH,CN(UTILITY MODEL),CO(UTILITY MODEL),CR(UTILITY MODEL),CU(INVENTOR'S CERTIFICATE),CZ(UTILITY MODEL),DE(UTILITY MODEL),DK(UTILITY MODEL),DM,DZ,EC(UTILITY MODEL),EE(UTILITY MODEL),EG(UTILITY MODEL),ES(UTILITY MODEL),FI(UTILITY MODEL),GB,GD,GE(UTILITY MODEL),GH,GM,GT,HN,HR(CONSENSUAL PATENT),HU(UTILITY MODEL),ID,IL,IN,IS,JP(UTILITY MODEL),KE(UTILITY MODEL),KG(UTILITY MODEL),KM,KN,KP(INVENTOR'S CERTIFICATE)(UTILITY MODEL),KR(UTILITY MODEL),KZ(PROVISIONAL PATENT)(UTILITY MODEL),LA,LC,LK,LR,LS(UTILITY MODEL),LT,LU,LY,MA,MD(UTILITY MODEL),MG,MK,MN,MW,MX(UTILITY MODEL),MY(UTILITY-INNOVATION),MZ(UTILITY MODEL),NA,NG,NI(UTILITY MODEL),NO,NZ,OM,PG,PH(UTILITY MODEL),PL(UTILITY MODEL),PT(UTILITY MODEL),RO,RS(PETTY PATENT),RU(UTILITY MODEL),SC,SD,SE,SG,SK(UTILITY MODEL),SL(UTILITY MODEL),SM,SV,SY,TJ(UTILITY MODEL),TM(PROVISIONAL PATENT),TN,TR(UTILITY MODEL),TT(UTILITY CERTIFICATE),TZ,UA(UTILITY MODEL),UG(UTILITY CERTIFICATE),US,UZ(UTILITY MODEL),VC(UTILITY CERTIFICATE),VN,ZA,ZM,ZW,EP(AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HU,IE,IS,IT,LT,LU,LV,MC,MT,NL,PL,PT,RO,SE,SI,SK,TR),OA(BF(UTILITY MODEL),BJ(UTILITY MODEL),CF(UTILITY MODEL),CG(UTILITY MODEL),CI(UTILITY MODEL),CM(UTILITY MODEL),GA(UTILITY MODEL),GN(UTILITY MODEL),GQ(UTILITY MODEL),GW(UTILITY MODEL),ML(UTILITY MODEL),MR(UTILITY MODEL),NE(UTILITY MODEL),SN(UTILITY MODEL),TD(UTILITY MODEL),TG(UTILITY MODEL)),AP(BW,GH,GM,KE,LS,MW,MZ,NA,SD,SL,SZ,TZ,UG,ZM,ZW),EA(AM,AZ,BY,KG,KZ,MD,RU,TJ,TM) |
日本語項目の表示
| Title |
連想メモリ
|
|---|---|
| Abstract | 検索の高速性を維持しつつも、消費電力を抑え且つデバイスの構造を簡単化して小さい実装面積で実装可能な連想メモリを提供する。ＣＡＭ関数fの無効出力をドントケアで置換した簡略化ＣＡＭ関数gのＬＵＴ結合論理回路で構成された簡略化関数演算部と、ＣＡＭ関数fの逆関数f－1が記憶された補助メモリと、ＬＵＴ演算手段の出力がＣＡＭ関数fの出力に一致するか判定する一致判定手段とを備え、ＬＵＴ演算手段は、入力データに対し簡略化ＣＡＭ関数gの演算値（仮インデックス値）を出力し、補助メモリは、仮インデックス値が入力されるとそれに対しする逆関数f－1の値を出力し、判定手段は、入力データと逆関数f－1の値とを比較して、両者が一致する場合はＬＵＴ演算手段の出力値を出力し、それ以外の場合は無効信号を出力する。 |
| Scope of claims |
【請求項１】入力データに対しそのデータに対応する固有のインデックスを出力する連想記憶メモリであって、入力データに対しそのデータに対応する固有のインデックスを出力する関数（以下「ＣＡＭ（Content Addressable Memory）関数」という。）fの無効出力値をドント・ケアで置き換えた関数（以下「簡略化ＣＡＭ関数」という。）gを表すＬＵＴ結合論理回路又はＰＬＡにより構成された簡略化関数演算部と、前記ＣＡＭ関数fの逆関数f－1が記憶された補助メモリと、前記ＬＵＴ演算手段の出力値がＣＡＭ関数fの出力に一致するか否かを判定する一致判定手段と、を備え、前記ＬＵＴ演算手段は、前記入力データに対して前記簡略化ＣＡＭ関数gの演算値（以下「仮インデックス値」という。）を前記補助メモリの読み出しアドレスとして出力し、前記補助メモリは、前記仮インデックス値が読み出しアドレスとして入力されると、その仮インデックス値に対しする逆関数f－1の値を出力し、前記判定手段は、前記入力データと前記補助メモリが出力する逆関数f－1の値とを比較して、両者が一致する場合は前記ＬＵＴ演算手段の出力値を出力し、それ以外の場合は無効信号を出力することを特徴とする連想メモリ。 【請求項２】前記ＬＵＴ結合論理回路は、ＬＵＴカスケード論理回路であることを特徴とする請求項１記載の連想メモリ。 【請求項３】前記ＬＵＴ結合論理回路は、ｐｑ回路網であることを特徴とする請求項１記載の連想メモリ。 |
| Specification | 【発明の詳細な説明】【技術分野】【０００１】本発明は、連想メモリ（内容検査メモリ：Content Addressable Memory：以下「ＣＡＭ」という。）に関し、特に、高速検索が可能で、消費電力を抑え、且つ小さい実装面積で実装可能な連想メモリに関する。【背景技術】【０００２】通常のメモリは、与えられたインデックス（アドレス）に対して、そのアドレスに格納されている登録データを生成する。一方、ＣＡＭは、与えられた検索（入力）データに対して、それを格納するＣＡＭのインデックス（アドレス）を生成する（非特許文献１，２参照）。【０００３】ＣＡＭは、パターン・マッチング、インターネットのルータ、プロセッサのキャッシュ、ＴＬＢ（Translation Lookaside Buffer）、データ圧縮、データベースのアクセラレータ、ニューラルネット、メモリパッチなど幅広い分野において利用されている。【０００４】通常、ＣＡＭは、その機能から、２値ＣＡＭ（Binary CAM：以下「ＢＣＡＭ」という。）及び３値ＣＡＭ（Ternary CAM：以下「ＴＣＡＭ」という。）の二種類に分類される。ＢＣＡＭでは、各セルに０及び１を格納する。ＴＣＡＭでは各セルに０，１，及び＊を格納する。ここで、「＊」はドント・ケア（don't care）を表し、０と１の両方にマッチする。【０００５】〔定義１〕（ＢＣＡＭ）ｎ入力で登録データ数ｐのＢＣＡＭテーブルは、ｐ個の異なる２値ベクトルを格納する。また、ｐ個のベクトルは、アドレス１からアドレスｐに順に格納されていると仮定する。また、各ベクトルのアドレスはｍビットで表現可能である。ｍは次式（１）により表される。【０００６】【数１】また、ｐ個のベクトルは、アドレス１からアドレスｐに順に格納されていると仮定する。対応するＢＣＡＭ関数f:{0,1}n→{0,1}mは、以下の条件を満たす：f(x)は入力xと同じベクトルがＢＣＡＭテーブル中にあるとき、ベクトルxを格納するＣＡＭのアドレス（１からｐの値の何れか）を出力する。入力xと同じパターンがＢＣＡＭテーブル中に無い場合には、f(x)の値は0である。（定義終り）【０００７】（例１）（表１）は、７個の２値ベクトルを格納するＢＣＡＭを示す。対応するＢＣＡＭ関数を（表２）に示す。何れも、入力データに完全に一致したベクトルを格納するアドレスを３ビットの数（例えば、‘０１１’）として出力する。入力ベクトルと一致するものがＢＣＡＭ中に格納されていない場合には、０を出力する。（例終わり）【０００８】【表１】【０００９】【表２】【００１０】〔定義２〕（ＴＣＡＭ）ｎ入力で要素数ｐのＴＣＡＭテーブルは、ｐ個の３値ベクトルを格納する。また、ｐ個のベクトルは、アドレス１からアドレスｐに順に格納されていると仮定する。また、各ベクトルのアドレスはｍビットで表現可能である。ここで、ｍは上記式（１）により表される。各３値ベクトルは、０，１，又は＊（ドント・ケア）から構成される。対応するＴＣＡＭ関数：f:{0,1}n→{0,1}mは、以下の条件を満たす：入力xに対して、xと一致するベクトルがＴＣＡＭテーブル中にある場合、出力f(x)は、一致したベクトル中の最小のアドレスを示す。また、xと一致するベクトルがＴＣＡＭテーブル中に無い場合には、０を出力する。（定義終り）【００１１】（例２）（表３）に示すＴＣＡＭは、７個の３値ベクトルを格納する。対応するＴＣＡＭ関数を（表４）に示す。入力x=(1,0,1,1)は、アドレス５及び６に蓄えられているパターンと一致する。５の方が小さいので、出力は(0,1,0,1)となる。（例終わり）【００１２】【表３】【００１３】【表４】【００１４】ＣＡＭの機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェア（半導体メモリ）を用いてＣＡＭを実現することが多い。以下、ハードウェアで構成された従来のＣＡＭについて説明する。【００１５】図８は、従来のＣＡＭの基本構成の一例を表すブロック図である（特許文献１参照）。ＣＡＭ１００は、比較レジスタ１０１、検索ビット線ドライバ１０２、ｎ個のワードＷ１～Ｗｎ、ｎ個の一致センス回路ＭＳＣ１～ＭＳＣｎ、ｎ個の一致フラグレジスタＭＦＲ１～ＭＦＲｎ、及びプライオリティ・エンコーダ（優先度付符号化回路）ＰＥを備えている。【００１６】比較レジスタ１０１は、ｍビットの検索データを格納するレジスタである。検索ビット線ドライバ１０２は、比較レジスタ１０１の各ビットを検索ビット線上にドライブする。各ワードＷ１～Ｗｎは、それぞれｍビットのＣＡＭセルを備えている。【００１７】図９は、図８のＣＡＭセルの構成回路図である。図９に例示したＣＡＭセル１０３は、不一致検出型のものである。ＣＡＭセル１０３は、メモリ・セル１０４及び一致比較回路１０５から構成される。メモリ・セル１０４は、１ビットのデータを記憶するＳＲＡＭ構成のメモリ・セルである。図９においてＤがデータ、ＤＮが反転データを表す。一致比較回路１０５は、メモリ・セル１０４に記憶された１ビットのデータと検索ビット線対ＳＬ，ＳＬＮ上にドライブされる検索データとを比較し、その一致比較結果を一致線ＭＬ上に出力する。【００１８】一致比較回路１０５は、３つのｎＭＯＳトランジスタ（以下「ｎＭＯＳ」という。）１０６，１０７，１０８を備えている。ｎＭＯＳ１０６，１０７は、検索ビット線ＳＬＮと検索ビット線ＳＬとの間に直列に接続されている。ｎＭＯＳ１０６，１０７のゲートは、それぞれ、メモリ・セル１０４のデータＤ，反転データＤＮに接続されている。ｎＭＯＳ１０８は、一致線ＭＬとグランドとの間に接続されている。ｎＭＯＳ１０８のゲートは、ｎＭＯＳ１０６，１０７の間のノード１０９に接続されている。【００１９】まず、検索を行う前に、ＣＡＭ１００のそれぞれのワードＷ１～Ｗｎに、検索対象であるデータが記憶される。各ワード内の各ＣＡＭセル１０３において、メモリ・セル１０４へのデータの書き込み及びメモリ・セル１０４からのデータの読み出しは、通常のＳＲＡＭと同様にして行われる。【００２０】検索時には、まず、比較レジスタ１０１に検索データが格納される。検索データの各のビットは、検索ビット線ドライバ１０２により、各々対応する検索ビット線上にドライブされる。【００２１】各々のワードＷ１～Ｗｎでは、各ＣＡＭセルに予め記憶されているデータと検索ビット線上にドライブされた検索データとの一致検索が同時（並列）に実行され、その結果が一致線ＭＬ１～ＭＬｎ上に出力される。これらの検索結果は、それぞれ一致センス回路ＭＳＣ１～ＭＳＣｎに入力される。各一致センス回路ＭＳＣ１～ＭＳＣｎは、各検索結果を増幅し、一致センス出力として一致センス出力線ＭＴ１～ＭＴｎに出力する。各一致センス出力は、一致フラグレジスタＭＦＲ１～ＭＦＲｎに格納され、一致フラグ出力として一致フラグ出力出力線ＭＦ１～ＭＦｎに出力される。一致フラグは、‘１’が「一致あり」、‘０’が「一致なし」を表すものとする。【００２２】各一致フラグ出力は、プライオリティ・エンコーダＰＥに入力される。プライオリティ・エンコーダＰＥでは、所定の優先順位付けに従って、一致が検出されたワードの中から最優先順位のワードのアドレス（最優先一致アドレス：ＨＭＡ）を選択し出力する。各ワードの優先順位は、ワードＷ１が最も高く、Ｗｎに向かうに従って順次優先順位が低くなるものとする。【００２３】尚、各ワードＷ１～Ｗｎ内の各ＣＡＭセル１０３における一致検索は、次のようにして実行される。【００２４】まず、初期化動作を実行する。初期化動作では、検索ビット線対ＳＬ，ＳＬＮがともに‘Ｌ’（＝‘０’）とされる。一方、メモリ・セル１０４に記憶されているデータに応じて、一致比較回路１０５のｎＭＯＳ１０６，１０７のうち一方がオン状態、他方がオフ状態となる。従って、ｎＭＯＳ１０６，１０７のうちオン状態の方を介して、両者の間のノード１０９のレベルが‘Ｌ’となり、ｎＭＯＳ１０８はオフ状態となる。この状態で、一致線ＭＬが‘Ｈ’（＝‘１’）状態にプリチャージされる。尚、一致線ＭＬは‘Ｈ’が「一致」を表す。【００２５】次に、検索ビット線を介して比較レジスタ１０１に記憶された検索データの各ビットが各ＣＡＭセル１０３に入力される。これにより、検索データＳに応じて、検索ビット線対ＳＬ，ＳＬＮの何れか一方が‘Ｈ’、他方が‘Ｌ’となる。【００２６】メモリ・セル１０４に記憶されているデータＤと検索データＳとが一致する場合、ノード１０９のレベルは‘Ｌ’であり、ｎＭＯＳ１０８はオフ状態に保持される。【００２７】一方、データＤと検索データＳとが一致しない場合、ノード１０９のレベルは‘Ｈ’となり、ｎＭＯＳ１０８はオン状態になる。これにより、一致線ＭＬはディスチャージされて‘Ｌ’状態となる。【００２８】ｍビットのＣＡＭセル１０３からなるＣＡＭワードの一致線ＭＬは、各ＣＡＭセル１０３のｎＭＯＳ１０８がパラレルに接続されたワイヤードＯＲ回路を構成している。従って、１ワードを構成するｍビットのＣＡＭセル１０３のすべてにおいて一致が検出された場合に限り、一致線ＭＬは‘Ｈ’（「一致」）の状態に保持される。一方、１ビットでもＣＡＭセル１０３で不一致が検出されると、一致線ＭＬは‘Ｌ’（「不一致」）の状態となる。【００２９】例えば、検索の結果、一致フラグレジスタＭＦＲ１～ＭＦＲｎに、一致フラグとして‘０’，‘１’，‘１’，‘０’，…，‘１’，‘０’が格納されたとする。この場合、ワードＷ２，Ｗ３，…，Ｗｎ－１で一致が検出されている。従って、プライオリティ・エンコーダＰＥは、最も優先順位が高いワードＷ２のアドレスをＨＭＡとして出力する。また、一致フラグレジスタＭＦＲ２に格納された一致フラグを‘０’にクリアすることで、その次に優先順位が高いワードＷ３のアドレスをＨＭＡとして出力することができる。以下同様にして、一致が検出されたワードのアドレスを順次出力することができる。【００３０】尚、ＴＣＡＭとして使用する場合、ドント・ケアのビットについては、検索ビット線対ＳＬ，ＳＬＮをともに‘Ｌ’（＝‘０’）としておけばよい。【００３１】図１０は、図８のＣＡＭセルの別の例の構成回路図である。図１０に示すＣＡＭセル１０３’は一致検出型のものであり、図９と同様、ＳＲＡＭ構成のメモリ・セル１０４及び一致比較回路１０５を備えている。ＣＡＭセル１０３’は、図９のＣＡＭセル１０３において、一致比較回路１０５のｎＭＯＳ１０８の接続が異なる。図ＤのｎＭＯＳ１０８は、一致線ＭＬａと一致線ＭＬｂとの間に接続されている。ｎＭＯＳ１０８のゲートは、ｎＭＯＳ１０６，１０７の間のノード１０９に接続されている。【００３２】ＣＡＭセル１０３’では、検索時には、初期化動作として、ビット線対ＳＬ，ＳＬＮが共に‘Ｈ’とされる。一方、メモリ・セル１０４に記憶されているデータに応じて、一致比較回路１０５のｎＭＯＳ１０６，１０７のうち一方がオン状態、他方がオフ状態となる。従って、ｎＭＯＳ１０６，１０７のうちオン状態の方を介して、両者の間のノード１０９のレベルが‘Ｈ’となり、ｎＭＯＳ１０８はオン状態となる。この状態で、一致線ＭＬの一端が‘Ｈ’（＝‘１’）状態にプリチャージされる。尚、一致線ＭＬは‘Ｈ’が「不一致」を表す。【００３３】ｍビットのＣＡＭセル１０３’からなるＣＡＭワードの一致線ＭＬは、各ＣＡＭセル１０３’のｎＭＯＳ１０８がシリアルに接続されたＡＮＤ回路を構成する。従って、各々のＣＡＭセルの一致線ＭＬａ，ＭＬｂは、各々のＣＡＭセル１０３’のｎＭＯＳ１０８を介して‘Ｈ’にプリチャージされる。【００３４】その後、検索ビット線を介して比較レジスタ１０１に記憶された検索データの各ビットが各ＣＡＭセル１０３’に入力される。これにより、検索データＳに応じて、検索ビット線対ＳＬ，ＳＬＮの何れか一方が‘Ｈ’、他方が‘Ｌ’となる。【００３５】メモリ・セル１０４に記憶されているデータＤと検索データＳとが一致する場合、ノード１０９のレベルは‘Ｈ’であり、ｎＭＯＳ１０８はオン状態に保持される。【００３６】一方、データＤと検索データＳとが一致しない場合、ノード１０９のレベルは‘Ｌ’となり、ｎＭＯＳ１０８はオフ状態になる。【００３７】ＣＡＭワードのｍビットのＣＡＭセル１０３’のすべての状態が確定した後、一致線ＭＬの一方の端部からディスチャージを開始し、他方の端部で一致比較結果を判定する。このとき、１ビットでも不一致のＣＡＭセル１０３’がある場合には、一致比較結果は‘Ｈ’、すなわち、不一致の状態に保持される。一方、すべてのＣＡＭセル１０３’で一致が検出された場合のみ、一致比較結果は‘Ｌ’、すなわち一致状態となる。【００３８】尚、ＴＣＡＭとして使用する場合、ドント・ケアのビットについては、検索ビット線対ＳＬ，ＳＬＮをともに‘Ｈ’（＝‘１’）としておけばよい。【特許文献１】特開２００４－２９５９６７号公報【特許文献２】特願２００３－３８９２６４号明細書【特許文献３】特開２００４－２５８７９９号公報【特許文献４】特開2004-258799号公報【非特許文献１】菅野卓雄監修，香山晋編，「超高速デバイス・シリーズ２ 超高速ＭＯＳデバイス」，初版，倍風館，１９８６年２月，ｐｐ．３２４－３２５．【非特許文献２】電子情報通信学会編，「ＬＳＩハンドブック」，第１版，オーム社，１９９４年１１月，ｐｐ．５２３－５２５．【非特許文献３】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.【非特許文献４】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.【非特許文献５】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).【非特許文献６】井口、笹尾、”LUTカスケード・アーキテクチャについて、” 平成15年電気学会 電子・情報・システム部門大会、MC2-4、2003年8月29日～30日、秋田大学。【発明の開示】【発明が解決しようとする課題】【００３９】上記従来のＣＡＭは、ＲＡＭに比べると、並列に検索可能であるため高速であるが、デバイスの構成は複雑となる。そのため、ＣＡＭの１ビットあたりの価格（ビットコスト）は、ＲＡＭに比べると１０～３０倍程度、高価なものになる。【００４０】また、１ビットあたりの消費電力がＲＡＭに比べて遙かに大きい（非特許文献３参照）。これは、上で説明したように、すべてのＣＡＭセルを同時にアクセスするためである。そのため、１ビットあたりの消費電力は、通常のＲＡＭの約５０倍程度にもなる。【００４１】そこで、本発明の目的は、検索の高速性を維持しつつも、消費電力を抑え且つデバイスの構造を簡単化して小さい実装面積で実装可能な連想メモリを提供することにある。【課題を解決するための手段】【００４２】以下、本明細書において使用する用語の定義及び本発明の前提となる理論を説明し、その後本発明の構成及び作用について説明する。【００４３】〔１〕ＣＡＭ関数の性質〔定義３〕（分解表、基本分解表、列複雑度）関数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の場合も考える。（定義終り）【００４４】〔定義４〕（Ｃ尺度）変数の順序を(x1,x2,…,xn)としたとき、論理関数fの基本分解表の列複雑度の最大値を、fの「Ｃ尺度」という。（定義終り）【００４５】（例３）f1=x1x2∨x3x4∨x5x6のＣ尺度は３であるが、f2=x1x5∨x2x6∨x3x4のＣ尺度は８である。（例終わり）【００４６】分解表の列複雑度は、ＭＴＢＤＤ（多端子二分決定グラフ）の幅に等しい。従って、論理関数のＣ尺度は、与えられた入力変数の順におけるＭＴＢＤＤの幅の最大値に等しい。与えられた論理関数f(x1,x2,…,xn)に対して、Ｃ尺度は容易に計算でき、一意的に定まる。後述するように、Ｃ尺度が小さい関数は、ＬＵＴカスケード（LUT (Lookup-table) cascade）で効率的に実現可能である。従って、Ｃ尺度は、論理関数をＬＵＴカスケードで実現する際の複雑さの尺度となる。【００４７】〔補題１〕与えられた関数fに対して、非零出力を生ずる入力の組み合わせの個数をpとする。このとき、fのＣ尺度は高々p+1である。（補題終り）【００４８】〔定理１〕（ＢＣＡＭ関数のＣ尺度）要素数pのＢＣＡＭテーブルが与えられたとき、そのＢＣＡＭ関数のＣ尺度は高々p+1である。（定理終り）【００４９】〔定理２〕（ＴＣＡＭ関数のＣ尺度）ＴＣＡＭテーブルがp個のベクトルを格納し、各ベクトルが高々k個のドント・ケアを有するとき、対応するＴＣＡＭ関数のＣ尺度は高々2kp+1である。（定理終り）【００５０】〔２〕ＬＵＴカスケードＣＡＭ関数は通常のＲＡＭでも実現可能である。例えば、上記（表１）に示した要素７のＢＣＡＭ関数は、（表２）に示したように、１６ワードのＲＡＭにより実現することができる。ここで、各ワードは３ビットである。ｎ入力のＣＡＭ関数を単一のＲＡＭで実現する場合、ＲＡＭの大きさは、ＢＣＡＭがわずか数個のベクトルしか含まない場合であっても、2nに比例して大きくなる。そこで、ＬＵＴカスケードを用いることにより、必要なメモリ量を大幅に削減することが可能となる（特許文献３参照）。【００５１】〔定理３〕与えられた関数fに対して、XLを分解表の列に対応する変数、XHを行に対応する変数とし、μを分解表の列複雑度とする。このとき、関数fは図１に示すような回路で実現することが可能である。この場合、二つのブロックＨとＧの間を結ぶ信号線数（以下「レイル数」という。）は【００５２】【数２】である。（定理終り）【００５３】二つのブロック間を結ぶ信号線数がXL中の変数の個数よりも少ないとき、関数を実現するためのメモリ量を削減できる可能性がある。この手法を「関数分解」という。与えられた関数を繰り返し関数分解することにより、図２に示すようなＬＵＴカスケードが得られる（非特許文献４参照）。ＬＵＴカスケードは「セル」から構成され、隣接するセル間を接続する信号線を「レイル」という。Ｃ尺度が小さな関数は小型のＬＵＴカスケードで実現可能である。Ｃ尺度を求めるには、必ずしも分解表を使用する必要はなく、多出力関数の特性関数を表現する二分決定グラフ（Binary Decision Diagram for Characteristic Function：以下「BDD_for_CF」という。）から効率的に計算することができる（特許文献２，非特許文献５参照）。【００５４】〔定理４〕Ｃ尺度がμの論理関数は、入力数が高々【００５５】【数３】出力数が【００５６】【数４】のセルから構成されたＬＵＴカスケードで実現可能である。（定理終り）【００５７】〔定理５〕関数fを実現するＬＵＴカスケードを考える。いま、nを外部入力変数、sをセル数、rを最大レイル数（即ち、セル間の信号線数）、kをセルの最大入力数、μを関数fのＣ尺度とする。【００５８】【数５】が成立するとき、以下の関係を満たすfを実現するＬＵＴカスケードが存在する。【００５９】【数６】（定理終り）【００６０】〔３〕ドント・ケアを用いた設計法〔３－１〕ＢＣＡＭ関数の設計法ＢＣＡＭ関数では、真理値表において、非零出力の値が、全体の組み合わせの数2nに比べて大幅に少ない。つまり、次の（仮定１）が成立するものとする。【００６１】（仮定１） ＢＣＡＭテーブルの入力ビット数をn、ベクトル数をpとするとき、p≪2n。【００６２】例えば、n=32でp=1000のＢＣＡＭを考えるとき、非零出力の割合は全最小項の個数の1000／232=2.3×10-7となる。【００６３】ＢＣＡＭ関数をＢＤＤで表現すると、ＢＤＤの最大幅が、Ｃ尺度を超えないこと、及び〔定理１〕から、レイル幅はp+1を超えないことがわかる。しかし、全体の幅はp+1近くなる。従って、ＢＣＡＭ関数をＬＵＴカスケードで実現する場合、入力数が【００６４】【数７】のセルが多数必要となる。そこで、ここではドント・ケアの概念を用いて、ＢＣＡＭ関数を実現するハードウェア量を削減する方法について、図３を参照しながら説明する。【００６５】〔アルゴリズム１〕（１）fをＢＣＡＭ関数とする。また、fにおいてＣＡＭに登録されていないデータに対する出力値をドント・ケアとした関数をgとする。【００６６】（２）gの特性関数を表現する二分決定グラフ（BDD_for_CF）を生成し、簡単化を行う。【００６７】（３）簡単化したＢＤＤから、ＬＵＴカスケード１を生成する。一般に、ＬＵＴカスケード１は、fを実現するＬＵＴカスケード（これを「厳密なＬＵＴカスケード」と呼ぶ。）よりも簡単になる。【００６８】（４）検索データが登録データと一致するときは、ＬＵＴカスケード１は正しい値を出力する。検索データが登録データと一致しないときは、ＬＵＴカスケード１は、誤った値を出力する可能性がある。【００６９】（５）誤りを補正するために、m入力n出力の補助メモリ２を用いる。ここで、mは次式で表される。【００７０】【数８】この補助メモリ２には、各アドレスにＢＣＡＭテーブルの対応するデータが格納されている。【００７１】（６）ＬＵＴカスケード１の出力のインデックスを補助メモリ２に供給し、補助メモリ２内の登録データを読み出す。そして、一致回路３により、入力データと補助メモリ２の出力データとを比較する。両者が一致すれば、ＬＵＴカスケード１の出力値は正しいことが保証される。従ってエンコーダ４はＬＵＴカスケード１の出力のインデックスをそのまま出力する。一方、補助メモリ２の出力データと入力データとが一致しないときは、ＣＡＭ内にそのデータは登録されていない。従って、そのときには、エンコーダ４は無効のインデックス（０）を出力する。（アルゴリズム終り）【００７２】補助メモリ２の全ビット数は、n2mであり、ハードウェアのコストは、ＬＵＴカスケード１のコストに比べ無視できる程度である。【００７３】〔３－２〕ＴＣＡＭ関数の設計法ＴＣＡＭ関数の場合、ＴＣＡＭテーブルは３値となるので、補助メモリ２は、m入力2n出力となる。また、一致回路３で、ドント・ケアに対応するビットは無視する。他の部分はＢＣＡＭと同じである。【００７４】〔４〕本発明の構成本発明に係る連想メモリの構成は、入力データに対しそのデータに対応する固有のインデックスを出力する連想記憶メモリであって、入力データに対しそのデータに対応する固有のインデックスを出力する関数（以下「ＣＡＭ（Content Addressable Memory）関数」という。）fの無効出力値をドント・ケアで置き換えた関数（以下「簡略化ＣＡＭ関数（reduced Content Addressable Memory function）」という。）gを表すＬＵＴ結合論理回路又はＰＬＡ（Programmable Logic Array）により構成された簡略化関数演算部と、前記ＣＡＭ関数fの逆関数f－1が記憶された補助メモリと、前記ＬＵＴ演算手段の出力値がＣＡＭ関数fの出力に一致するか否かを判定する一致判定手段と、を備え、前記ＬＵＴ演算手段は、前記入力データに対して前記簡略化ＣＡＭ関数gの演算値（以下「仮インデックス値」という。）を前記補助メモリの読み出しアドレスとして出力し、前記補助メモリは、前記仮インデックス値が読み出しアドレスとして入力されると、その仮インデックス値に対しする逆関数f－1の値を出力し、前記判定手段は、前記入力データと前記補助メモリが出力する逆関数f－1の値とを比較して、両者が一致する場合は前記ＬＵＴ演算手段の出力値を出力し、それ以外の場合は無効信号を出力することを特徴とする。【００７５】この構成によれば、ＬＵＴ結合論理回路は、通常のＲＡＭを複数個用いて構成することができる。また、補助メモリも通常のＲＡＭで構成できる。また、ＣＡＭ関数fそのものを表すＬＵＴ結合論理回路ではなく、ＣＡＭ関数fの無効出力値をドント・ケアで置き換えた簡略化関数gを表すＬＵＴ結合論理回路又はＰＬＡを用いることによって、当該ＬＵＴ結合論理回路又はＰＬＡを構成するために必要なメモリ量を大幅に削減することができる。従って、全体として、従来のＣＡＭに比べ、デバイスの構造を簡単化して小さい実装面積により実装が可能となる。【００７６】また、通常のＲＡＭで構成することによって、専用のＣＡＭ回路を必要としない。故に、ＡＳＩＣで構成する以外に、汎用のＲＡＭを内蔵したＦＰＧＡ（Field Programmable Gate Array）やＣＬＤ（Complex Programmable Logic Device）のようなプログラマブル・デバイスを用いて簡単に低コストで構成することもできる。【００７７】また、判定手段以外はすべて通常のＲＡＭで構成できる。そして、１回の検索動作に対して、数回（ＬＵＴ結合論理回路でのＲＡＭのアクセス回数＋１）のＲＡＭのアクセスで仮インデックス値が得られる。各ＲＡＭのアクセスでは、ＲＡＭ内の１つのアドレスのみがアクセスされる。全体として、数回のＲＡＭのメモリ・アクセスのみで仮インデックス値が得られる。従って、従来のＣＡＭに比べると、消費電力を大幅に低減することが可能となる。【００７８】一方、高速性の面では、従来のＣＡＭに比べると遅くなるものの、通常のＲＡＭをＣＰＵを用いて検索する方法に比べると遙かに高速に検索を行うことができる。【００７９】ここで、「ＬＵＴ結合論理回路」とは、複数のＬＵＴ（Look-Up Table）をカスケード状又はネットワーク状に結合した回路をいうが、必ずしもハードウェア的に複数のＬＵＴを配置・結合する必要はない。例えば、１つのメモリ内に複数のＬＵＴを記憶させ、ＬＵＴの選択を順次切り替えながら、メモリの出力値をメモリの読み出しアドレスにフィードバックすることによってＬＵＴ結合を実現するような回路であってもよい。ＬＵＴ結合論理回路としては、ＬＵＴカスケード論理回路の他に、ＬＵＴをネットワーク状に結合したＬＵＴネットワークなどを使用することも可能である。【００８０】尚、本発明はＢＣＡＭ及びＴＣＡＭの双方に適用することが可能である。【発明の効果】【００８１】以上のように、本発明によれば、検索の高速性を維持しつつ、消費電力を抑え且つデバイスの構造を簡単化して小さい実装面積で実装可能な連想メモリを提供することができる。【図面の簡単な説明】【００８２】【図１】論理関数の関数分解を表す図である。【図２】中間出力を有するＬＵＴカスケードを表す図である。【図３】ドント・ケアを用いたＣＡＭ関数の実現法を説明する図である。【図４】本発明の実施例１に係る連想メモリの全体構成を表す図である。【図５】図４の簡略化関数演算部５の構成を表す図である。【図６】図４の一致判定手段７の構成を表す図である。【図７】実施例２に係る連想メモリの一致判定手段７の構成を表す図である。【図８】従来のＣＡＭの基本構成の一例を表すブロック図である。【図９】図８のＣＡＭセルの構成回路図である。【図１０】図８のＣＡＭセルの別の例の構成回路図である。【符号の説明】【００８３】１ ＬＵＴカスケード２ 補助メモリ３ 一致回路４ エンコーダ５ 簡略化関数演算部６ 補助メモリ７ 一致判定手段１０ 連想メモリ１１ 入力変数レジスタ１２－１～１２－ｓ 論理関数メモリ１３ 出力変数レジスタ２１ ＥＸＮＯＲゲート２２ ＡＮＤゲート２３ ＡＮＤゲート３１ ｐｑ素子【発明を実施するための最良の形態】【００８４】以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。【実施例１】【００８５】図４は、本発明の実施例１に係る連想メモリの全体構成を表す図である。本実施例の連想メモリ１０は、簡略化関数演算部５、補助メモリ６、及び一致判定手段７を備えている。【００８６】連想メモリ１０は、外部回路から入力されるｎビットの入力データX=(x1,…,xn)に対しその入力データXに対応するｍビットの固有のインデックスA=(a1,…,am)を出力する。入力データXは、簡略化関数演算部５及び一致判定手段７に入力される。【００８７】以下では、入力データXに対しその入力データXに対応する固有のインデックスAを出力するＣＡＭ関数を、Fと記す。また、ＣＡＭ関数Fの出力のうち、無効なインデックス値をドント・ケアで置き換えた簡略化ＣＡＭ関数を、Gと記す。【００８８】簡略化関数演算部５は、簡略化ＣＡＭ関数Gを演算するＬＵＴ結合論理回路により構成されている。簡略化関数演算部５は、入力データXに対し仮インデックスA'=G(X)を演算する。この仮インデックスA'は、補助メモリ６及び一致判定手段７に出力される。【００８９】補助メモリ６は、ＣＡＭ関数Fの逆関数F-1、すなわち、固有のインデックスAに対しそのインデックスAに対応するデータXを出力するデータ出力関数が、ＬＵＴとして記憶されている。補助メモリ６には、簡略化関数演算部５が出力する仮インデックスA'が入力され、それに対する逆算データX'=F-1(A')が出力される。仮インデックスA'は、一致判定手段７に出力される。【００９０】一致判定手段７は、入力データXと逆算データX'とを比較し、両者が一致するか否かを判定する。そして、両者が一致する場合には仮インデックスA'を出力インデックスAとして出力し、一致しない場合には無効値を出力する。【００９１】図５は、図４の簡略化関数演算部５の構成を表す図である。本実施例１においては、簡略化関数演算部５として、ＬＵＴカスケード論理回路を用いる。【００９２】簡略化関数演算部５は、入力変数レジスタ１１、論理関数メモリ１２－１～１２－ｓ、及び出力変数レジスタ１３を備えている。【００９３】入力変数レジスタ１１は、外部から入力される入力データXを一時的に保持するレジスタである。論理関数メモリ１２－１～１２－ｓは、簡略化ＣＡＭ関数Gを関数分解して得られるＣＡＭ関数Gの部分関数G1,…,GsがＬＵＴとして格納されている。ここで、Xの分割をX=(X1,X2,…,Xs)とした場合、各部分関数G1,…,Gsは次のようになる。【００９４】【数９】【００９５】ここでは、ベクトルA1',A2',…,As-1'は、ＬＵＴカスケードの中間出力であり、ベクトルAs'はＬＵＴカスケードの最終出力である。仮インデックスA'は、これらのベクトルの合成として表される。また、ベクトルR1,R2,…,Rs-1は、ＬＵＴカスケードの中間変数を表す。【００９６】出力変数レジスタ１３は、各論理関数メモリ１２－１～１２－ｓが出力する中間出力A1',A2',…,As-1'及び最終出力As'を保持し、仮インデックスA'として出力するレジスタである。【００９７】尚、ＬＵＴカスケード論理回路の詳しい動作については、特許文献４及び非特許文献６に記載されているため、ここでは説明を省略する。【００９８】図６は、図４の一致判定手段７の構成を表す図である。図６では、一例として、入力データXが８ビット、出力インデックスAが８ビットの場合を示しているが、入力データX及び出力インデックスAのビット数はこれに限られるものではない。【００９９】一致判定手段７は、入力データXの各ビットに対応して設けられたＥＸＮＯＲゲート２１、１個のＡＮＤゲート２２、及び出力インデックスAの各ビットに対応して設けられたＡＮＤゲート２３により構成される。【０１００】入力データX及び逆算データX'の各ビットxi, xi'（i=1,2,…,8）は、それぞれ対応するＥＸＮＯＲゲート２１に入力され、EXNOR演算が行われる。各ＥＸＮＯＲゲート２１の演算結果は、ＡＮＤゲート２２に入力され、AND演算が行われる。このＡＮＤゲート２２の出力Qを、一致判定信号と呼ぶ。【０１０１】一方、仮インデックスA'の各ビットa1',a2',…,a8'は、それぞれ各ＡＮＤゲート２３の一方の入力ノードに入力される。また、各ＡＮＤゲート２３の他方の入力ゲートには、一致判定信号Qが入力される。【０１０２】以上のように構成された本実施例に係る連想メモリ１０について、以下その動作を説明する。【０１０３】まず、外部回路から入力データXが入力されると、簡略化関数演算部５は、ＣＡＭ関数G(X)の演算を行い、その結果を仮インデックスA'として出力する。ここで、入力データXに対する真のインデックスが存在する場合、仮インデックスA'の値は真のインデックスの値に一致する。一方、真のインデックスが存在しない場合には、仮インデックスA'の値はドント・ケアとなる。従って、仮インデックスA'は真のインデックスを含むものの、その値が真のインデックスを表すのかドント・ケアを表すのかの判別はできない。【０１０４】次に、仮インデックスA'は補助メモリ６に入力される。補助メモリ６は、仮インデックスA'に対してデータ出力関数F-1(A')のＬＵＴ演算を行い、その結果を逆算データX'= F-1(A')として出力する。このとき、仮インデックスA'は真のインデックスを表す場合には、逆算データX'は入力データXと同じ値となる。しかし、仮インデックスA'がドント・ケアの場合には、仮インデックスA'はデタラメな値なので、逆算データX'には無効値が出力される。【０１０５】次に、一致判定手段７のｉ番目のＥＸＮＯＲゲート２１（i=1,2,…,8）には、それぞれ入力データXのｉ番目の成分xiと逆算データX'のｉ番目の成分xi'とが入力される。ＥＸＮＯＲゲート２１は、論理演算【０１０６】【数１０】を行い、演算値qiを出力する。演算値qiの値は、成分xiと成分xi'とが一致する場合は１、一致しない場合は０となる。【０１０７】各演算値qiは、ＡＮＤゲート２２に入力され、ＡＮＤ演算が行われる。これにより、入力データXと逆算データX'の各成分が完全に一致する場合には一致判定信号Qは１となり、それ以外の場合には一致判定信号Qは０となる。従って、この一致判定信号Qを用いることによって、仮インデックスA'が真のインデックス値を表しているか否かの判別ができる。【０１０８】ｉ番目のＡＮＤゲート２３（i=1,2,…,8）には、それぞれ仮インデックスA'のｉ番目の成分xiと一致判定信号Qが入力される。そして、各ＡＮＤゲート２３はこれらのAND演算を行い、その結果を出力インデックスAのｉ番目の成分aiとして出力する。これにより、仮インデックスA'が真のインデックス値を表している場合には、出力インデックスAとして真のインデックス値が出力され、それ以外の場合は出力インデックスAとして０が出力される。【０１０９】以上のようにして、入力データXに対するCAM関数の演算が行われる。上述のように、本実施の形態では、簡略化関数演算部５及び補助メモリ６はすべてメモリで構成されているため、通常のRAMを用いて構成することが可能である。従って、プロセスの微細化が容易であり回路規模を小さくすることができる。また、メモリであるため、使用しない期間を省電力状態として消費電力の節減を図ることも可能である。【実施例２】【０１１０】本実施例２に係る連想メモリの全体構成及び一致判定手段７の構成は、図４，図６と同様であり、説明は省略する。実施例２に係る連想メモリは、簡略化関数演算部５の構成が実施例１とは異なる。【０１１１】図７は、実施例２に係る連想メモリの簡略化関数演算部５の構成を表す図である。本実施例の簡略化関数演算部５は、複数のｐｑ素子３１を樹形状に結合した構成からなる。ｐｑ素子３１は、ｐ入力ｑ出力のメモリである。各ｐｑ素子３１のｐ，ｑの値はそれぞれのｐｑ素子３１ごとに任意に設定される。各ｐｑ素子３１には、簡略化ＣＡＭ関数Gを関数分解して得られる部分関数G1,G2,…がＬＵＴとして格納されている。このように複数のｐｑ素子３１を樹形状に結合した回路をここでは「ｐｑ回路網」と呼ぶ。【０１１２】尚、図７の構成は一例であり、ｐｑ素子３１の結合の仕方は、ＣＡＭ関数Gにより適宜選択される。【０１１３】このように、簡略化関数演算部５としてｐｑ回路網を使用しても、実施例１と同様の連想メモリを構成することができる。【手続補正書】【提出日】平成21年7月3日(2009.7.3)【手続補正１】【補正対象書類名】特許請求の範囲【補正対象項目名】全文【補正方法】変更【補正の内容】【特許請求の範囲】【請求項１】入力データに対しそのデータに対応する固有のインデックスを出力する連想記憶メモリであって、入力データに対しそのデータに対応する固有のインデックスを出力する関数（以下「ＣＡＭ（Content Addressable Memory）関数」という。）fの無効出力値をドント・ケアで置き換えた関数（以下「簡略化ＣＡＭ関数」という。）gを表すＬＵＴ結合論理回路又はＰＬＡにより構成された簡略化関数演算部と、前記ＣＡＭ関数fの逆関数f－1が記憶された補助メモリと、前記簡略化関数演算部の出力値がＣＡＭ関数fの出力に一致するか否かを判定する一致判定手段と、を備え、前記簡略化関数演算部は、前記入力データに対して前記簡略化ＣＡＭ関数gの演算値（以下「仮インデックス値」という。）を前記補助メモリの読み出しアドレスとして出力し、前記補助メモリは、前記仮インデックス値が読み出しアドレスとして入力されると、その仮インデックス値に対しする逆関数f－1の値を出力し、前記判定手段は、前記入力データと前記補助メモリが出力する逆関数f－1の値とを比較して、両者が一致する場合は前記簡略化関数演算部の出力値を出力し、それ以外の場合は無効信号を出力することを特徴とする連想メモリ。【請求項２】前記ＬＵＴ結合論理回路は、ＬＵＴカスケード論理回路であることを特徴とする請求項１記載の連想メモリ。【請求項３】前記ＬＵＴ結合論理回路は、ｐｑ回路網であることを特徴とする請求項１記載の連想メモリ。【手続補正２】【補正対象書類名】明細書【補正対象項目名】００７４【補正方法】変更【補正の内容】【００７４】〔１〕本発明の構成本発明に係る連想メモリの構成は、入力データに対しそのデータに対応する固有のインデックスを出力する連想記憶メモリであって、入力データに対しそのデータに対応する固有のインデックスを出力する関数（以下「ＣＡＭ（Content Addressable Memory）関数」という。）fの無効出力値をドント・ケアで置き換えた関数（以下「簡略化ＣＡＭ関数（reduced Content Addressable Memory function）」という。）gを表すＬＵＴ結合論理回路又はＰＬＡ（Programmable Logic Array）により構成された簡略化関数演算部と、前記ＣＡＭ関数fの逆関数f－1が記憶された補助メモリと、前記簡略化関数演算部の出力値がＣＡＭ関数fの出力に一致するか否かを判定する一致判定手段と、を備え、前記簡略化関数演算部は、前記入力データに対して前記簡略化ＣＡＭ関数gの演算値（以下「仮インデックス値」という。）を前記補助メモリの読み出しアドレスとして出力し、前記補助メモリは、前記仮インデックス値が読み出しアドレスとして入力されると、その仮インデックス値に対しする逆関数f－1の値を出力し、前記判定手段は、前記入力データと前記補助メモリが出力する逆関数f－1の値とを比較して、両者が一致する場合は前記簡略化関数演算部の出力値を出力し、それ以外の場合は無効信号を出力することを特徴とする。 |
※
詳細は、下記「問合せ先」まで直接お問い合わせください。
Contact Information for " ASSOCIATED MEMORY "
- 国立大学法人九州工業大学 オープンイノベーション推進機構 産学官連携本部
- URL: http://www.ccr.kyutech.ac.jp/
-
E-mail:
- Address: 〒804-8550 福岡県北九州市戸畑区仙水町1-1
- Phone: 093-884-3499
- Fax: 093-884-3531
※ It is possible to retrieve in J-STORE by the same key word. → Retrieval result of J-STORE
