TOP > 国内特許検索 > 連想記憶装置、インデックス生成器、及び登録情報更新方法 > 明細書

明細書 :連想記憶装置、インデックス生成器、及び登録情報更新方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第6229990号 (P6229990)
登録日 平成29年10月27日(2017.10.27)
発行日 平成29年11月15日(2017.11.15)
発明の名称または考案の名称 連想記憶装置、インデックス生成器、及び登録情報更新方法
国際特許分類 G11C  15/04        (2006.01)
G06F  17/30        (2006.01)
FI G11C 15/04 631W
G06F 17/30 412
請求項の数または発明の数 15
全頁数 29
出願番号 特願2016-544229 (P2016-544229)
出願日 平成27年8月19日(2015.8.19)
国際出願番号 PCT/JP2015/073227
国際公開番号 WO2016/027829
国際公開日 平成28年2月25日(2016.2.25)
優先権出願番号 2014168777
優先日 平成26年8月21日(2014.8.21)
優先権主張国 日本国(JP)
審査請求日 平成28年12月22日(2016.12.22)
特許権者または実用新案権者 【識別番号】801000027
【氏名又は名称】学校法人明治大学
発明者または考案者 【氏名】笹尾 勤
個別代理人の代理人 【識別番号】100064908、【弁理士】、【氏名又は名称】志賀 正武
【識別番号】100106909、【弁理士】、【氏名又は名称】棚井 澄雄
【識別番号】100108578、【弁理士】、【氏名又は名称】高橋 詔男
【識別番号】100126882、【弁理士】、【氏名又は名称】五十嵐 光永
審査官 【審査官】後藤 彰
参考文献・文献 国際公開第2007/119539(WO,A1)
国際公開第2007/119540(WO,A1)
中原 啓貴,”並列ふるい法とMPUを用いたウイルス検出エンジンについて”,電子情報通信学会技術研究報告 RECONF2009-41-RECONF2009-53,日本,社団法人電子情報通信学会,2009年12月 3日,第109巻第320号,第25頁-第30頁
中原 啓貴,”並列インデックス生成器を用いたIPv6検索アーキテクチャに関して”,情報処理学会研究報告 2013 February システムLSI設計技術(SLDM),日本,一般社団法人情報処理学会,2013年 2月15日,No.159 (5)
調査した分野 G11C 15/04
G06F 17/30
特許請求の範囲 【請求項1】
複数のハッシュ関数を用いて入力ベクトルの特徴量を生成し、前記特徴量に基づき登録ベクトルに関する登録情報を検索することにより前記入力ベクトルに対応したインデックスを生成する複数のインデックス生成部と、
前記複数のインデックス生成部の各出力を結合して前記入力ベクトルに対応したインデックスを出力する出力部と、
前記登録情報の更新を制御する制御部と、
を備え、
前記複数のインデックス生成部のそれぞれは、
前記特徴量に基づき生成されたインデックスが前記登録情報として存在するか否かを示す第1信号を生成して前記制御部に供給すると共に、前記特徴量に基づき生成されたインデックスを用いて前記入力ベクトルの再生ベクトルを生成し、前記再生ベクトルが前記入力ベクトルと一致するか否かを示す第2信号を生成して前記制御部に供給する、連想記憶装置。
【請求項2】
前記複数のインデックス生成部のそれぞれは、
前記入力ベクトルから前記入力ベクトルの特徴量を算出するためのハッシュ回路と、
前記登録ベクトルのインデックスが前記登録情報として格納された主記憶部を有し、前記主記憶部から前記特徴量に対応した仮のインデックスを読み出して出力する仮インデックス生成回路と、
前記仮インデックス生成回路から出力された仮のインデックスに基づいて前記第1信号を生成して出力する衝突信号生成回路と、
前記登録ベクトルが前記登録情報として格納された副記憶部を有し、前記副記憶部から前記仮のインデックスに対応したベクトルを読み出して前記再生ベクトルとして出力する再生ベクトル生成回路と、
前記再生ベクトルと前記入力ベクトルとを比較し、前記再生ベクトルと前記入力ベクトルとが一致するか否かを示す前記第2信号を出力する比較回路と、
前記第2信号が前記再生ベクトルと前記入力ベクトルとの一致を示す場合、前記仮のインデックスを前記入力ベクトルに対応した固有のインデックスとして出力し、前記第2信号が前記再生ベクトルと前記入力ベクトルとの不一致を示す場合、無効値を出力する出力回路と、
を備えた請求項1に記載の連想記憶装置。
【請求項3】
前記主記憶部と前記副記憶部が、1つのメモリに統合された、請求項2に記載の連想記憶装置。
【請求項4】
前記主記憶部は、前記特徴量を示すビット列がアドレス信号として入力されるメモリから構成された、請求項2または3に記載の連想記憶装置。
【請求項5】
前記副記憶部は、前記仮のインデックスを示すビット列がアドレス信号として入力されるメモリから構成された、請求項2から4の何れか1項に記載の連想記憶装置。
【請求項6】
前記複数のインデックス生成部のうちの一部のインデックス生成部に代えて、または、前記複数のインデックス生成部に加えて、CAMセルを有する連想メモリを備えた、請求項1から5の何れか1項に記載の連想記憶装置。
【請求項7】
前記制御部は、
前記登録情報として登録ベクトルとそのインデックスとを追加する場合、追加すべき登録ベクトルが前記登録情報として存在しない旨を示す前記第1信号を供給するインデックス生成部を選択し、選択した当該インデックス生成部の登録情報として、前記追加すべき登録ベクトルに対応するインデックスを追加する、請求項1から6の何れか1項に記載の連想記憶装置。
【請求項8】
前記制御部は、
前記登録情報として登録された登録ベクトルのインデックスを削除する場合、前記複数のインデックス生成部のうち、削除すべき登録ベクトルのインデックスを用いて生成された再生ベクトルが前記入力ベクトルと一致する旨を示す前記第2信号を供給するインデックス生成部を選択し、選択した当該インデックス生成部の登録情報から、前記登録ベクトルに対応するインデックスを削除する、請求項1から7の何れか1項に記載の連想記憶装置。
【請求項9】
入力ベクトルから前記入力ベクトルの特徴量を算出して出力するハッシュ回路と、
登録ベクトルに関する登録情報として前記登録ベクトルに対応するインデックスが格納された主記憶部を有し、前記主記憶部から前記特徴量に対応した仮のインデックスを読み出して出力する仮インデックス生成回路と、
前記仮インデックス生成回路から出力された仮のインデックスに基づいて、前記特徴量に対応した仮のインデックスが前記登録情報として存在するか否かを示す第1信号を生成して出力する信号生成回路と、
前記登録ベクトルに関する登録情報として前記登録ベクトルが格納された副記憶部を有し、前記副記憶部から前記仮のインデックスに対応したベクトルを読み出して再生ベクトルとして出力する再生ベクトル生成回路と、
前記再生ベクトルと前記入力ベクトルとを比較し、前記再生ベクトルと前記入力ベクトルとが一致するか否かを示す第2信号を出力する比較回路と、
前記第2信号が前記再生ベクトルと前記入力ベクトルとの一致を示す場合、前記仮のインデックスを前記入力ベクトルに対応した固有のインデックスとして出力する出力回路と、
を備えたインデックス生成器。
【請求項10】
請求項1から8の何れか1項に記載の連想記憶装置の登録情報を更新する情報更新方法であって、
前記連想記憶装置は、動作モードとして、検索モードと更新モードとを備え、
前記連想記憶装置に備えられた制御部は、前記更新モードにおいて前記登録情報を更新するための制御を実施する、情報更新方法。
【請求項11】
前記検索モードにおいて、前記複数のインデックス生成部と前記出力部とが連想メモリとして機能する、請求項10に記載の情報更新方法。
【請求項12】
前記更新モードにおいて、前記制御部は、前記登録情報として登録された登録ベクトルに対応するインデックスを削除した後、前記登録情報として追加すべき登録ベクトルに対応するインデックスを追加することにより、前記登録情報を更新する、請求項10または11に記載の情報更新方法。
【請求項13】
前記更新モードにおいて、
削除すべき登録ベクトルを前記入力ベクトルとして前記連想記憶装置に備えられた複数のインデックス生成部に供給する第1段階と、
前記複数のインデックス生成部のそれぞれについて、前記制御部により、前記第2信号に基づき、前記削除すべき登録ベクトルに対応した固有のインデックスが前記登録情報として存在するか否かを判定する第2段階と、
前記複数のインデックス生成部の何れかにおいて、前記削除すべき登録ベクトルに対応した固有のインデックスが前記登録情報として存在する場合、前記制御部により、前記登録情報として存在する前記削除すべき登録ベクトルに対応するインデックスの値を有効値から無効値に変更する第3段階と、
を含む請求項12に記載の情報更新方法。
【請求項14】
前記更新モードにおいて、
追加すべき登録ベクトルを前記入力ベクトルとして前記複数のインデックス生成部に供給する第1段階と、
前記複数のインデックス生成部のそれぞれについて、前記制御部により、前記第1信号に基づき、前記追加すべき登録ベクトルに対応した仮のインデックスが前記登録情報として存在するか否かを判定する第2段階と、
前記複数のインデックス生成部の何れかにおいて、前記追加すべき登録ベクトルに対応した仮のインデックスが前記登録情報として存在しない場合、前記追加すべき登録ベクトルに対応したインデックスの値として有効値を設定する第3段階と、
を含む請求項12または13に記載の情報更新方法。
【請求項15】
前記複数のインデックス生成部の何れかにおいて、前記追加すべき登録ベクトルに対応した仮のインデックスが前記登録情報として存在する場合、前記制御部により、前記追加すべき登録ベクトルに対応した仮のインデックスが存在しない他のインデックス生成部において、前記追加すべき登録ベクトルに対応したインデックスの値として有効値を設定する、請求項14に記載の情報更新方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、連想記憶装置、インデックス生成器、及び登録情報更新方法に関し、特に、連想記憶装置に備えられたインデックス生成器に登録された登録情報の更新を高速化するための技術に関する。
【背景技術】
【0002】
通常のメモリは、与えられたアドレス(インデックス)に対して、そのアドレスに格納されている登録データを生成する。一方、CAM(Content Addressable Memory)は、与えられた検索(入力)データに対して、それを格納する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】
CAMの機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェアを用いてCAMを実現することが多い。
【先行技術文献】
【0006】

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

【非特許文献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”, IEEEJournal 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, “Memory-Based Logic Synthesis”, Springer 2011.
【非特許文献6】笹尾勤、“パターンマッチング用プログラマブル論理回路とその設計法”,電子情報通信学会誌,Vol. 96, No.2, pp.100-104,2013年2月.
【発明の概要】
【発明が解決しようとする課題】
【0008】
上記従来のCAMは、RAMに比べると、並列に検索可能であるため高速であるが、デバイスの構成は複雑となる。そのため、CAMの1ビットあたりの価格(ビットコスト)は、RAMに比べると10~30倍程度、高価なものになる。また、1ビットあたりの消費電力がRAMに比べて遙かに大きい(非特許文献3参照)。これは、すべてのCAMセルを同時にアクセスするためである。そのため、1ビットあたりの消費電力は、通常のRAMの約50倍程度にもなる。
従って、上記従来のCAMによれば、ビットコスト及び消費電力の観点から記憶容量の大規模化は困難である。
【0009】
本発明は、上記事情に鑑みてなされたものであり、記憶容量の大規模化を可能としつつ、登録情報の更新を高速に行うことができる連想記憶装置、インデックス生成器、及び登録情報更新方法を提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明の一態様による連想記憶装置は、複数のハッシュ関数を用いて入力ベクトルの特徴量を生成し、前記特徴量に基づき登録ベクトルに関する登録情報を検索することにより前記入力ベクトルに対応したインデックスを生成する複数のインデックス生成部と、前記複数のインデックス生成部の各出力を結合して前記入力ベクトルに対応したインデックスを出力する出力部と、前記登録情報の更新を制御する制御部と、を備え、前記複数のインデックス生成部のそれぞれは、前記特徴量に基づき生成されたインデックスが前記登録情報として存在するか否かを示す第1信号を生成して前記制御部に供給すると共に、前記特徴量に基づき生成されたインデックスを用いて前記入力ベクトルの再生ベクトルを生成し、前記再生ベクトルが前記入力ベクトルと一致するか否かを示す第2信号を生成して前記制御部に供給する、連想記憶装置の構成を有する。
【0011】
本発明の一態様によるインデックス生成器は、入力ベクトルから前記入力ベクトルの特徴量を算出して出力するハッシュ回路と、登録ベクトルに関する登録情報として前記登録ベクトルに対応するインデックスが格納された主記憶部を有し、前記主記憶部から前記特徴量に対応した仮のインデックスを読み出して出力する仮インデックス生成回路と、前記仮インデックス生成回路から出力された仮のインデックスに基づいて、前記特徴量に対応した仮のインデックスが前記登録情報として存在するか否かを示す第1信号を生成して出力する衝突信号生成回路と、前記登録ベクトルに関する登録情報として前記登録ベクトルが格納された副記憶部を有し、前記副記憶部から前記仮のインデックスに対応したベクトルを読み出して再生ベクトルとして出力する再生ベクトル生成回路と、前記再生ベクトルと前記入力ベクトルとを比較し、前記再生ベクトルと前記入力ベクトルとが一致するか否かを示す第2信号を出力する比較回路と、前記第2信号が前記再生ベクトルと前記入力ベクトルとの一致を示す場合、前記仮のインデックスを前記入力ベクトルに対応した固有のインデックスとして出力する出力回路と、を備えたインデックス生成器の構成を有する。
【0012】
本発明の一態様による情報更新方法は、前記連想記憶装置に登録された登録情報を更新する情報更新方法であって、前記連想記憶装置は、動作モードとして、検索モードと更新モードとを備え、前記連想記憶装置に備えられた制御部は、前記更新モードにおいて前記登録情報を更新するための制御を実施する、情報更新方法の構成を有する。
【発明の効果】
【0013】
本発明の一態様によれば、記憶容量の大規模化を可能としつつ、登録情報の更新を高速に行うことができる。
【図面の簡単な説明】
【0014】
【図1】本発明の第1実施形態による連想記憶装置の構成例を示すブロック図である。
【図2】本発明の第1実施形態による連想記憶装置に備えられたインデックス生成部の構成例を示すブロック図である。
【図3A】本発明の第1実施形態による連想記憶装置に備えられた第1のインデックス生成部のハッシュ回路の構成例を示す回路図である。
【図3B】本発明の第1実施形態による連想記憶装置に備えられた第2のインデックス生成部のハッシュ回路の構成例を示す回路図である。
【図3C】本発明の第1実施形態による連想記憶装置に備えられた第3のインデックス生成部のハッシュ回路の構成例を示す回路図である。
【図4A】本発明の第1実施形態による連想記憶装置に備えられたインデックス生成部の比較回路の構成例を示す図である。
【図4B】本発明の第1実施形態による連想記憶装置に備えられたインデックス生成部の出力回路の構成例を示す図である。
【図4C】本発明の第1実施形態による連想記憶装置に備えられたインデックス生成部の衝突信号生成回路の構成例を示す図である。
【図5】本発明の第1実施形態による連想記憶装置に備えられた出力部の回路構成例を示す図である。
【図6】本発明の第1実施形態による連想記憶装置に登録される登録情報の一例を示す図である。
【図7】本発明の第1実施形態による連想記憶装置に備えられた1番目のインデックス生成部で実現される登録情報を説明するための図である。
【図8】本発明の第1実施形態による連想記憶装置に備えられた2番目のインデックス生成部で実現される登録情報を説明するための図である。
【図9】本発明の第1実施形態による連想記憶装置に備えられた3番目のインデックス生成部で実現される登録情報を説明するための図である。
【図10】本発明の第2実施形態による連想記憶装置の構成例を示すブロック図である。
【図11】本発明の第2実施形態による連想記憶装置に備えられた連想メモリの基本構成の一例を示すブロック図である。
【図12】CAMセルの回路構成例を示す図である。
【図13】本発明の第1実施形態による登録情報の削除方法の一例を示すフローチャートである。
【図14】本発明の第1実施形態による新規情報の追加方法の一例を示すフローチャートである。
【発明を実施するための形態】
【0015】
本発明の実施形態を説明する前に、本明細書において使用するいくつかの用語を定義しておく。
〔定義1〕(登録ベクトル)
相異なるk個(kは自然数)のnビット(nは自然数)のベクトルの集合を考える。このベクトルの集合を登録ベクトル集合(set of registered vectors)といい、登録ベクトル集合に属する各ベクトルを登録ベクトルという。

【0016】
〔定義2〕(インデックス生成関数,インデックス生成器,入力ベクトル)
登録ベクトル集合の各要素と一致する入力に対して1からkまでの固有インデックスに単射し、それ以外の入力に対して0となる関数をインデックス生成関数という。
即ち、関数f(X):B→{0,1,…,k}(B={0,1},k∈自然数)において、k個の異なる登録ベクトルa∈B(i=1,2,…,k)に対してf(a)=i(i=1,2,…,k)が成立し、それ以外の(2-k)個の入力ベクトルaに対しては、f(a)=0が成立するとき、f(X)を重みkのインデックス生成関数という。インデックス生成関数は、k個の異なる2値ベクトルに対して、1からkまでの固有インデックスを生成する。なお、本明細書においては、kの値は入力ベクトルの組み合わせ総数2に比べて十分に小さい(k<<2)と仮定する。

【0017】
また、上記のインデックス生成関数の演算を行う回路をインデックス生成器という。インデックス生成器に入力されるベクトルを、入力ベクトルという。入力ベクトルがn次元ベクトルであるインデックス生成関数を、n入力のインデックス生成関数という。また、n入力のインデックス生成関数の演算を行う回路をn入力のインデックス生成器という。

【0018】
〔定義3〕(ハッシュ関数)
ハッシュ関数とは、集合Sから整数の集合{0,1,…,m-1}への写像である。ここで、mは、集合Sの要素を超えない自然数である。

【0019】
以下、図面を参照して、本発明の実施形態を説明する。
(第1実施形態)
1.構成の説明
図1は、本発明の第1実施形態による連想記憶装置100の構成例を示すブロック図である。連想記憶装置100は、検索対象のnビット(nは自然数)の入力ベクトルX(x1,x2,…,xn)に対応した固有のインデックスAを生成して出力するためのものであり、N個(Nは2以上の自然数)のインデックス生成部110-1,110-2,110-3,…,110-N、出力部120、制御部130を備えている。以下では必要に応じて、N個のインデックス生成部110-1,110-2,110-3,…,110-Nのうちの任意の一つを「インデックス生成部110-i」(iは、1からNまでの自然数)と表す。また、インデックス生成部110-1,110-2,110-3,…,110-Nのそれぞれは、インデックス生成器、インデックス生成装置等として単体で取り扱うことができる。

【0020】
N個のインデックス生成部110-1,110-2,110-3,…,110-Nは、入力ベクトルXの特徴量を生成し、その特徴量から、入力ベクトルXに対応した固有のインデックスA1,A2,…,ANをそれぞれ生成して出力するように構成されている。即ち、N個のインデックス生成部110-1,110-2,110-3,…,110-Nは、それぞれ、ハッシュ関数を用いて入力ベクトルXの特徴量を生成し、この特徴量に基づいて、各インデックス生成部に登録された登録ベクトルに関する登録情報を検索することにより、入力ベクトルXに対応した固有のインデックスA1,A2,A3,…,ANを生成する。本実施形態では、後述するように、ハッシュ関数として、排他的論理和ゲート回路のみで構成された回路で実現できる線形関数を用いる。
なお、N個のインデックス生成部110-1,110-2,110-3,…,110-Nでそれぞれ用いられるN個のハッシュ関数は、上述の〔定義3〕に従う限り、相互に同一の関数であってもよく、相互に異なる関数であってもよい。即ち、N個のインデックス生成部110-1,110-2,110-3,…,110-Nのそれぞれは、他のインデックス生成部で用いられるハッシュ関数と同一のハッシュ関数を用いてもよく、他のインデックス生成部で用いられるハッシュ関数とは異なるハッシュ関数を用いてもよい。

【0021】
また、インデックス生成部110-1,110-2,110-3,…,110-Nのそれぞれは、上記の特徴量に基づき生成されたインデックスが上記の登録情報として存在するか否かを示す第1信号(以下、「衝突信号」と称す。)CD1,CD2,CD3,…,CDNを生成すると共に、上記の特徴量に基づき生成されたインデックスを用いて入力ベクトルXの再生ベクトルを生成し、再生ベクトルが入力ベクトルXと一致するか否かを示す第2信号(以下、「一致信号」と称す。)MT1,MT2,…,MTNを生成する。ここで、「再生ベクトル」とは、入力ベクトルXの特徴量から得られるインデックスに基づいて元の入力ベクトルXを再現したベクトルを指す。衝突信号CD(CD1,CD2,CD3,…,CDN)と一致信号MT(MT1,MT2,…,MTN)は制御部130に供給される。

【0022】
出力部120は、N個のインデックス生成部110-1,110-2,110-3,…,110-Nの各出力(インデックスA1,A2,A3,…,AN)を結合して入力ベクトルXに対応した固有のインデックスAを出力するように構成されている。
制御部130は、N個のインデックス生成部110-1,110-2,110-3,…,110-Nのそれぞれに登録された上記の登録情報の更新を制御するためのものである。制御部130からインデックス生成部110-1,110-2,110-3,…,110-Nに対し、登録情報である登録ベクトルの書き込み動作を制御するためのライトイネーブル信号WEと、登録ベクトルのインデックスIDXと、登録情報を書き込むべきインデックス生成部110-1,110-2,110-3,…,110-Nの何れか指定するための選択信号SELが供給される。
なお、制御部130は、指令信号UPDが供給された場合に、動作モードを更新モードに変更する。また、制御部130は、指令信号UPDとインデックスIDXとが供給された場合に、新規な登録情報を追加する動作を行う。また、制御部130は、指令信号UPDのみが供給された場合に、既存の登録情報を削除する動作を行う。
また、制御部130は、例えば、更新モードなどの動作中に、動作中であることを示す信号BSY(ビジー)を出力する。また、制御部130は、例えば、新規な登録情報を追加する動作が失敗した場合に、失敗したことを示す信号FAL(フェイル)を出力する。

【0023】
ここでは、説明の簡略化のため、N=3とし、図1に示す連想記憶装置100は、3個のインデックス生成部110-1,110-2,110-3を備えるものとして説明する。従って、iは、1,2,3のうちの任意の自然数を指し、インデックス生成部110-iは、インデックス生成部110-1,110-2,110-3のうちの一つを表す。ただし、この例に限定されず、インデックス生成部の個数Nは任意に設定し得る。また、n=6とし、インデックス生成部110-1,110-2,110-3には、それぞれ、6ビットの入力ベクトルX(x1,x2,x3,x4,x5,x6)が入力されるものとする。

【0024】
次に、インデックス生成部110-i、出力部120、制御部130の各構成の詳細について説明する。
図2は、本発明の第1実施形態による連想記憶装置100に備えられたインデックス生成部110-iの構成例を示すブロック図である。インデックス生成部110-iは、ハッシュ回路111、仮インデックス生成回路112、再生ベクトル生成回路113、比較回路114、出力回路115、衝突信号生成回路116を備えている。このうち、ハッシュ回路111は、ハッシュ関数を用いて、nビットの入力ベクトルXから、入力ベクトルXの特徴量を表すpビット(pはnよりも小さい自然数)のベクトルY1を生成するためのものである。ここでは、p=3とする。ハッシュ関数は、異なる入力に対して同じ値を与える場合があり、それをハッシュ衝突(collision)と称す。本実施形態による連想記憶装置100では、或るハッシュ関数でハッシュ衝突が発生した場合、別のインデックス生成部を用いることによりハッシュ衝突を回避する。その詳細については後述する。

【0025】
仮インデックス生成回路112は、入力ベクトルXの特徴量を表すpビットのベクトルY1に対応したqビットの仮のインデックスA’を生成するものである。ここで、q=「log(k+1)」であり、kは、このインデックス生成部110-iで実現される登録ベクトルの数を表し、「log(k+1)」は切り上げ関数を表す。仮インデックス生成回路112は、登録ベクトルのインデックスが登録情報として格納された主記憶部を有しており、主記憶部から入力ベクトルXの特徴量に対応した仮のインデックスA’を読み出して出力する。上記の主記憶部は、上記の特徴量を示すビット列がアドレス信号として入力されるDRAM(Dynamic Random Access Memory)やSRAM(Static Random Access Memory)等の汎用の半導体メモリから構成されている。ただし、上記の主記憶部は、DRAM等の汎用メモリと同様に1回のアクセスでメモリセルアレイの一部のメモリセルを選択する方式を採用するメモリであれば、汎用メモリである必要はなく、専用に設計されたメモリであってもよい。

【0026】
再生ベクトル生成回路113は、仮のインデックスA’に対応した入力ベクトルXを再生するためのものであり、登録ベクトルが登録情報として格納された副記憶部を有している。再生ベクトル生成回路113は、副記憶部から仮のインデックスA’に対応した登録ベクトルを読み出して、(n-p)ビットの再生ベクトルX2’として出力する。(n-p)ビットの再生ベクトルX2’は、入力ベクトルX(X1,X2)のX2を再生した要素である。ここで、X1は入力ベクトルXのビットx1,x2,x3を指し、X2は、入力ベクトルXのビットx4,x5,x6を指す。上記の副記憶部は、上記の仮のインデックスA’を示すビット列がアドレス信号として入力されるDRAMやSRAM(Static Random Access Memory)等の汎用の半導体メモリから構成されている。上記の副記憶部についても、上記の主記憶部と同様に、専用に設計されたメモリであってもよい。
なお、上記のハッシュ関数として非線形関数を用いた場合、再生ベクトル生成回路113は、入力ベクトルXの全ビットに対応したnビットの再生ベクトルX’を出力する。

【0027】
比較回路114は、再生ベクトルX2’と入力ベクトルXのX2(x4,x5,x6)とが一致するか否かを検証するためのものである。再生ベクトルX2’と入力ベクトルXのX2とが一致するか否かを検証することは、仮のインデックスA’が入力ベクトルXに対応した固有のインデックスであるかどうかを検証することを意味する。比較回路114は、再生ベクトルX2’と入力ベクトルXのX2とを比較し、この比較の結果に基づき、再生ベクトルX’と入力ベクトルXのX2とが一致するか否かを示す一致信号MTiを出力する。

【0028】
出力回路115は、一致信号MTiに基づき、入力ベクトルXに対応した固有のインデックスAiまたは所定の無効値を出力するためのものである。即ち、出力回路115は、一致信号MTiが再生ベクトルX2’と入力ベクトルXのX2との一致を示す場合、仮のインデックスA’を固有のインデックスAiとして出力し、一致信号MTiが再生ベクトルX2’と入力ベクトルXのX2との不一致を示す場合、所定の無効値を出力する。本実施形態では、インデックスAiの全てのビットの値が‘0’である場合、インデックスAiは所定の無効値を示す。ただし、この例に限定されず、無効値の定義は任意である。例えば、全てのビットの値が‘1’であるインデックスAiを無効値としてもよい。

【0029】
衝突信号生成回路116は、更新モードにおいて、仮インデックス生成回路112から出力される仮のインデックスA’に基づいて衝突信号CDiを生成して出力するためのものである。第1実施形態では、衝突信号生成回路116は、更新モードにおいて、新規な登録ベクトルを登録情報として追加する場合、仮インデックス生成回路112から出力される仮のインデックスA’に基づいて衝突信号CDiを出力する。ここで、衝突信号CDiは、更新モードでハッシュ衝突の有無を示す信号であり、更新対象の入力ベクトルXに対して仮インデックス生成回路112から出力される仮のインデックスA’が無効値でない場合、即ちハッシュ衝突が発生した場合に値‘1’となる信号である。なお、ハッシュ衝突が発生した場合の衝突信号CDiの値は任意に設定し得る。

【0030】
図3A~図3Cは、本発明の第1実施形態による連想記憶装置100に備えられたインデックス生成部110-iに備えられたハッシュ回路111の構成例を示す回路図である。ここで、図3Aは、インデックス生成部110-1に備えられたハッシュ回路111(i=1)の構成例を示し、図3Bは、インデックス生成部110-2に備えられたハッシュ回路111(i=2)の構成例を示し、図3Cは、インデックス生成部110-3に備えられたハッシュ回路111(i=3)の構成例を示している。図3A~図3Cでは、インデックス生成部110-iに入力される入力ベクトルXとして、6ビット(n=6)の入力ベクトルX(x1,x2,x3,x4,x5,x6)を想定している。

【0031】
図3Aに示すハッシュ回路111(i=1)は、インデックス生成部110-1において入力ベクトルXの特徴量を算出するためのハッシュ関数を実現する。図3Aの例ではハッシュ回路111は、入力ベクトルXの6ビット(x1,x2,x3,x4,x5,x6)のうち、X1(x1,x2,x3)の3ビットを、入力ベクトルXの特徴量を表す3ビット(p=3)のベクトルY1(y1,y2,y3)に変換するハッシュ関数を実現する。具体的には、図3Aに示すハッシュ回路111は、3個の排他的論理和ゲート回路から構成される。これら3個の排他的論理和ゲート回路の第1入力部には、X1(x1,x2,x3)の各ビットがそれぞれ供給され、第2入力部には、値‘0’が共通に供給される。これにより、図3Aのハッシュ回路111は、入力ベクトルXのX1(x1,x2,x3)を3ビットのベクトルY1(y1,y2,y3)として出力する。

【0032】
図3Bに示すハッシュ回路111(i=2)は、インデックス生成部110-2において入力ベクトルXの特徴量を算出するためのハッシュ関数を実現する。図3Bの例ではハッシュ回路111は、入力ベクトルXの6ビット(x1,x2,x3,x4,x5,x6)のうち、X2(x4,x5,x6)の3ビットを、入力ベクトルXの特徴量を表す3ビット(p=3)のベクトルY1(y1,y2,y3)に変換するハッシュ関数を実現する。具体的には、図3Bに示すハッシュ回路111は、3個の排他的論理和ゲート回路から構成される。これら3個の排他的論理和ゲート回路の第1入力部には、X2(x4,x5,x6)の各ビットがそれぞれ供給され、第2入力部には、値‘0’が共通に供給される。これにより、図3Bのハッシュ回路111(i=2)は、入力ベクトルXのX2(x4,x5,x6)を3ビットのベクトルY1(y1,y2,y3)として出力する。

【0033】
図3Cに示すハッシュ回路111(i=3)は、インデックス生成部110-3において入力ベクトルXの特徴量を算出するためのハッシュ関数を実現する。図3Cの例ではハッシュ回路111は、入力ベクトルXの6ビット(x1,x2,x3,x4,x5,x6)のうち、ビットx1とビットx6の排他的論理和を演算し、その演算結果を、入力ベクトルXの特徴量を表す3ビット(p=3)のベクトルY1(y1,y2,y3)として出力するハッシュ関数を実現する。

【0034】
具体的には、図3Cに示すハッシュ回路111(i=3)は、3個の排他的論理和ゲート回路111-31,111-32,111-33から構成される。排他的論理和ゲート回路111-31の入力部には、入力ベクトルXのビットx1とビットx6が供給される。排他的論理和ゲート回路111-31によりビットx1とビットx6との排他的論理和が演算され、その演算結果はベクトルY1のビットy1の値とされる。また、排他的論理和ゲート回路111-32の入力部には、入力ベクトルXのビットx2とビットx5が供給される。排他的論理和ゲート回路111-32によりビットx2とビットx5との排他的論理和が演算され、その演算結果はベクトルY1のビットy2の値とされる。

【0035】
更に、排他的論理和ゲート回路111-33の入力部には、入力ベクトルXのビットx3とビットx4が供給される。排他的論理和ゲート回路111-33によりビットx3とビットx4との排他的論理和が演算され、その演算結果はベクトルY1のビットy3の値とされる。
このように、3個のハッシュ回路111(i=1),111(i=2),111(i=3)は、それぞれ異なるハッシュ関数を実現している。

【0036】
インデックス生成部110-1,110-2,110-3の各ハッシュ回路111で実現されるハッシュ関数は、入力ベクトルXのビット数nよりも少ないビット数pで登録ベクトルを有意に識別し得る特徴量が得られるように、登録ベクトルの内容に応じて設定される。その詳細については後述する。

【0037】
次に、図2に示すインデックス生成部110-iに備えられた仮インデックス生成回路112の構成を説明する。
仮インデックス生成回路112は、前述のように、DRAM等の汎用の半導体メモリから構成され、この汎用の半導体メモリは仮インデックス生成回路112の上記の主記憶部を形成する。データの書き込みと読み出しの両方が可能であることを限度に、仮インデックス生成回路112の主記憶部を形成するメモリとして、強誘電体メモリや磁性体メモリ等、任意の方式のメモリを用いることができる。仮インデックス生成回路112の主記憶部を形成するメモリには、登録ベクトルのインデックスに関する情報が登録情報として格納されている。仮インデックス生成回路112の主記憶部を形成する汎用メモリのアドレス入力端子には、ハッシュ回路111から出力されるpビットのベクトルY1の各ビットがアドレス信号として供給される。

【0038】
ここで、ベクトルY1の各ビットの値の組み合わせによって指定される上記の主記憶部を形成する汎用メモリのメモリセルには、登録ベクトルのインデックスに関する登録情報として、その特徴量に対応したインデックスを示すデータが格納されている。従って、ベクトルY1に基づいて上記の主記憶部を形成する汎用メモリをアクセスすることにより、上記の主記憶部から入力ベクトルXの特徴量に対応したqビットのインデックスが仮のインデックスA’として読み出される。

【0039】
次に、図2に示すインデックス生成部110-iに備えられた再生ベクトル生成回路113の構成を説明する。
再生ベクトル生成回路113は、上述の仮インデックス生成回路112と同様に、DRAM等の汎用の半導体メモリから構成され、この汎用の半導体メモリは再生ベクトル生成回路113の上記の副記憶部を形成する。データの書き込みと読み出しの両方が可能であることを限度に、再生ベクトル生成回路113の副記憶部を形成するメモリとして、強誘電体メモリや磁性体メモリ等、任意の方式のメモリを用いることができる。再生ベクトル生成回路113の副記憶部を形成するメモリには、登録ベクトルのビットの値が登録情報として格納されている。再生ベクトル生成回路113の副記憶部を形成する汎用メモリのアドレス入力端子には、仮インデックス生成回路112から出力されたqビットの仮のインデックスA’の各ビットがアドレス信号として供給される。

【0040】
本実施形態では、ハッシュ回路111においてハッシュ関数として線形関数を用いていることから、後述の比較回路114において入力ベクトルと再生ベクトルとの一致を検証するのに一部のビットを比較すれば足りる。このため、仮のインデックスA’の各ビットの値の組み合わせによって指定される上記の副記憶部を形成する汎用メモリのメモリセルには、登録ベクトルに関する登録情報として、仮のインデックスA’に対応した登録ベクトルの一部のビットである(n-p)ビットの値が格納されている。ただし、上記のハッシュ関数として非線形関数を用いる場合、上記の副記憶部を形成するメモリには、登録ベクトルの全ビット(即ちnビット)の値が登録情報として格納される。

【0041】
ここで、仮のインデックスA’は、入力ベクトルXに対応している。従って、仮のインデックスA’に基づいて再生ベクトル生成回路113の副記憶部を形成する汎用メモリをアクセスすることにより、上記の副記憶部から入力ベクトルXのX2に対応した登録ベクトルの一部のビットが再生ベクトルX2’として読み出される。

【0042】
なお、仮インデックス生成回路112の主記憶部と、再生ベクトル生成回路113の副記憶部は、DRAM等の1つの半導体メモリに統合されてもよい。これにより、構成部品数を低減するとともに、メモリアクセス時間を削減することができる。

【0043】
次に、図2に示すインデックス生成部110-iに備えられた比較回路114の構成を説明する。
図4Aは、本発明の第1実施形態による連想記憶装置100に備えられたインデックス生成部110-iの比較回路114の構成例を示す図である。比較回路114は、一致ゲートである否定的排他的論理和ゲート回路1144,1145,1146から構成されている。否定的排他的論理和ゲート回路1144の入力部には、入力ベクトルXのX2のビットx4と再生ベクトルX2’のビットx4’が供給される。また、否定的排他的論理和ゲート回路1145の入力部には、入力ベクトルXのX2のビットx5と再生ベクトルX2’のビットx5’が供給される。更に、否定的排他的論理和ゲート回路1146の入力部には、入力ベクトルXのX2のビットx6と再生ベクトルX2’のビットx6’が供給される。否定的排他的論理和ゲート回路1144,1145,1146の各出力部は論理積ゲート回路1147の入力部に接続され、論理積ゲート回路1147の出力信号は一致信号MTiとされる。

【0044】
上記の比較回路114の構成によれば、入力ベクトルXのX2のビットx4,x5,x6の各値と再生ベクトルX2’のビットx4’,x5’,x6’の各値が完全に一致した場合のみ、一致信号MTiとして値‘1’を示すハイレベルの論理信号が出力される。

【0045】
次に、図2に示すインデックス生成部110-iに備えられた出力回路115の構成を説明する。
図4Bは、本発明の第1実施形態による連想記憶装置100に備えられたインデックス生成部110-iの出力回路115の構成例を示す図である。この例では、k=15を考慮して、仮のインデックスA’が4ビット(a1’,a2’,a3’,a4’)で表される場合を想定している。ただし、この例に限定されず、仮のインデックスA’のビット数は任意の値に設定し得る。

【0046】
出力回路115は、仮のインデックスA’のビット数(4ビット)に対応する4個の論理積ゲート回路1151,1152,1153,1154から構成されている。論理積ゲート回路1151,1152,1153,1154の各第1入力部には、それぞれ、仮のインデックスA’のビットa1’,a2’,a3’,a4’が供給される。また、論理積ゲート回路1151,1152,1153,1154の各第2入力部には一致信号MTiが共通に供給される。

【0047】
上記の出力回路115の構成によれば、一致信号MTiの値が‘1’(ハイレベル)である場合、論理積ゲート回路1151,1152,1153,1154は、仮のインデックスA’のビットa1’,a2’,a3’,a4’の値を、そのまま、固有のインデックスAiのビットa1i,a2i,a3i,a4iの値として出力する。また、一致信号MTiの値が‘0’(ローレベル)である場合、論理積ゲート回路1151,1152,1153,1154は、仮のインデックスA’のビットa1’,a2’,a3’,a4’の値とは関係なく、値‘0’(ローレベル)の信号を出力し、固有のインデックスAiのビットa1i,a2i,a3i,a4iの値はすべて‘0’となる。これは無効値を示す信号である。

【0048】
次に、図2に示すインデックス生成部110-iに備えられた衝突信号生成回路116の構成を説明する。
図4Cは、本発明の第1実施形態による連想記憶装置100に備えられたインデックス生成部110-iの衝突信号生成回路116の構成例を示す図である。この例でも、k=15を考慮して、仮のインデックスA’が4ビット(a1’,a2’,a3’,a4’)で表される場合を想定している。

【0049】
衝突信号生成回路116は、仮のインデックスA’のビット数(4ビット)に対応する4入力の論理和ゲート回路1161から構成されている。論理和ゲート回路1161は、仮のインデックスA’のビットa1’,a2’,a3’,a4’の論理和を演算し、その演算結果を衝突信号CDiとして出力する。衝突信号生成回路116は、仮のインデックスA’のビットa1’,a2’,a3’,a4’の何れかに‘1’の値が含まれている場合、衝突信号CDiとして値‘1’を示すハイレベルの論理信号を出力する。この衝突信号CDiの値‘1’は、更新モードにおいてハッシュ衝突が発生していることを示す。これに対し、仮のインデックスA’のビットa1’,a2’,a3’,a4’の全ての値が‘0’である場合、即ち、仮のインデックスA’が無効値を示す場合、衝突信号生成回路116は、衝突信号CDiとして値‘0’を示すローレベルの論理信号を出力する。この衝突信号CDiの値‘0’は、更新モードにおいてハッシュ衝突が発生していないことを示す。
以上で、図1に示す連想記憶装置100に備えられたインデックス生成部110-iの構成を説明した。

【0050】
次に、図1に示す連想記憶装置100に備えられた出力部120の構成を説明する。
図5は、本発明の第1実施形態による連想記憶装置100に備えられた出力部120の回路構成例を示す図である。
出力部120は、インデックス生成部110-1,110-2,110-3の個数に対応した3個の論理和ゲート回路1201,1202,1203から構成されている。論理和ゲート回路1201の入力部には、インデックス生成部110-1から出力されたインデックスA1のビットa1と、インデックス生成部110-2から出力されたインデックスA2のビットa1と、インデックス生成部110-3から出力されたインデックスA3のビットa1とが供給される。論理和ゲート回路1201は、インデックス生成部110-1,110-2,110-3からそれぞれ入力されたビットa1の論理和を演算し、その演算結果を、インデックスAのビットa1の値として出力する。

【0051】
また、論理和ゲート回路1202の入力部には、インデックス生成部110-1から出力されたインデックスA1のビットa2と、インデックス生成部110-2から出力されたインデックスA2のビットa2と、インデックス生成部110-3から出力されたインデックスA3のビットa2とが供給される。論理和ゲート回路1202は、インデックス生成部110-1,110-2,110-3からそれぞれ入力されたビットa2の論理和を演算し、その演算結果を、インデックスAのビットa2の値として出力する。

【0052】
更に、論理和ゲート回路1203の入力部には、インデックス生成部110-1から出力されたインデックスA1のビットa3と、インデックス生成部110-2から出力されたインデックスA2のビットa3と、インデックス生成部110-3から出力されたインデックスA3のビットa3とが供給される。論理和ゲート回路1203は、インデックス生成部110-1,110-2,110-3からそれぞれ入力されたビットa3の論理和を演算し、その演算結果を、インデックスAのビットa3の値として出力する。

【0053】
上記の論理演算を実施することにより、出力部120は、インデックス生成部110-1,110-2,110-3から出力されたインデックスA1,A2,A3の対応ビットを結合してインデックスAを生成し出力する。ここで、上記論理演算の過程で、回路の構成法から、高々1個のインデックス生成部のみが有効値を生成し、他のインデックス生成部は無効値を生成する。従って、上記構成によれば、有効値のみが出力部120からインデックスAとして出力される。
なお、全てのビットが‘1’からなる仮のインデックスA’を無効値として定義した場合、出力部120は、論理和ゲート回路1201,1202,1203に代えて、論理積演算を実施する論理積ゲート回路を備えればよい。

【0054】
次に、図6から図10を参照して、連想記憶装置100で実現される登録情報を説明する。
図6は、本発明の第1実施形態による連想記憶装置100に登録される登録情報の一例を示す図である。図6の登録情報は、n=6、k=15、X1=(x1、x2、x3)、X2=(x4,x5,x6)としたときに、入力ベクトルX(x1,x2,x3,x4,x5,x6)の各値と、入力ベクトルXの固有のインデックスAを表すインデックスIDXの値との対応関係を規定している。例えば、入力ベクトルX(x1,x2,x3,x4,x5,x6)の値(0,1,1,0,0,0)に対し、この入力ベクトルXの値に固有のインデックスAを表すインデックスIDXの値として値「1」が対応付けられている。

【0055】
前述したインデックス生成部110-1,110-2,110-3の各ハッシュ回路111で実現されるハッシュ関数は、入力ベクトルXのビット数nよりも少ないpビットのベクトルY1によって、登録情報に登録された登録ベクトルを有意に識別する特徴量を表現できるように、登録ベクトルの内容に応じて設定される。図6の例では、例えばX1のビットx1の値に着目した場合、インデックスIDXの値「1」及び「2」にそれぞれ対応付けられている登録ベクトルのビットx1の値は共に‘0’である。従って、ビットx1のみに基づいて、インデックスIDXの値「1」及び「2」にそれぞれ対応付けられている登録ベクトルを識別することはできない。そこで、ビットx2に着目すると、インデックスIDXの値「1」及び「2」にそれぞれ対応付けられている登録ベクトルのビットx2の値は共に‘1’である。従って、ビットx1とビットx2の二つのビットに着目しても、インデックスIDXの値「1」及び「2」にそれぞれ対応付けられている登録ベクトルを識別することはできない。

【0056】
そこで、更にビットx3に着目すると、インデックスIDXの値「1」に対応付けられている登録ベクトルのビットx3の値は‘1’であり、インデックスIDXの値「2」に対応付けられている登録ベクトルのビットx3の値は‘0’である。従って、ビットx3に着目すれば、インデックスIDXの値「1」及び「2」にそれぞれ対応付けられている登録ベクトルを識別することができる。即ち、インデックスIDXの値「1」及び「2」に対応する登録ベクトルの特徴量は、X1のビットx1,x2,x3を用いて表現可能である。
ただし、この例では、ビットx2、x3のみからインデックスIDXの値「1」及び「2」に対応する登録ベクトルを識別することが可能であり、この場合の登録ベクトルの特徴量としてビットx2,x3の値を用いることもできる。このようにして、X1によって識別可能な登録ベクトルに対応したインデックスIDXの集合が得られる。

【0057】
第1実施形態では、上述の図6に示す登録情報のうち、X1を用いて識別可能な登録ベクトルとインデックスIDXとの対応を規定した登録情報は、3個のインデックス生成部110-1,110-2,110-3のうち、1番目のインデックス生成部110-1で実現される。

【0058】
図7は、本発明の第1実施形態による連想記憶装置100に備えられた1番目のインデックス生成部110-1で実現される登録情報を説明するための図である。
図7に示すように、インデックス生成部110-1で実現される登録情報は、上述の図6に示す登録情報のうち、インデックスIDXの8個の値「4」、「5」、「2」、「1」、「11」、「10」、「15」、「3」と、これらのインデックスIDXの値に対応した8個の登録ベクトルのビット(x1,x2,x3,x4,x5,x6)の値との対応関係を規定するように決定される。

【0059】
このようにインデックス生成部110-1で実現すべき登録情報が決定されると、この登録情報の登録ベクトルを有意に識別するために必要なビットx1,x2,x3が入力ベクトルXから得られるように、インデックス生成部110-1のハッシュ回路111で実現すべきハッシュ関数が設定される。そして、このようなハッシュ関数を実現するために、前述したように、インデックス生成部110-1のハッシュ回路111(i=1)は、入力ベクトルXのビットx1,x2,x3,x4,x5,x6のうち、X1(x1,x2,x3)をベクトルY1(y1,y2,y3)として仮インデックス生成回路112に供給するように構成されている。

【0060】
ここで、図7に示す登録情報のうち、登録ベクトルのビットx1,x2,x3に対応付けられているインデックスIDXの各値は、インデックス生成部110-1の仮インデックス生成回路112の主記憶部に仮のインデックスA’として格納されている。この場合、インデックスIDXを表す仮のインデックスA’は、そのインデックスIDXに対応する登録ベクトルのビットx1,x2,x3によって指定されるメモリセルに格納されている。このように、登録ベクトルとインデックスIDXとが対応付けられて登録情報として仮インデックス生成回路112の主記憶部に格納されている。

【0061】
また、図7に示す登録情報のうち、登録ベクトルのビットx1,x2,x3,x4,x5,x6の各値は、再生ベクトル生成回路113の副記憶部に格納される。即ち、仮インデックス生成回路112からqビットの仮のインデックスA’としてインデックスIDXが再生ベクトル生成回路113に供給され、この仮のインデックスA’によって指定される副記憶部のメモリセルには、登録ベクトルのビットx1,x2,x3,x4,x5,x6の各値が格納されている。このように、登録ベクトルの各ビットの値が、仮のインデックスA’に対応付けられた登録情報として再生ベクトル生成回路113の副記憶部に格納されている。ただし、前述したように、上記のハッシュ関数として線形関数を用いた場合、登録ベクトルの全ビットを再生ベクトル生成回路113の副記憶部に格納する必要はなく、登録ベクトルの一部のビットx4,x5,x6を再生ベクトル生成回路113の副記憶部に格納すれば足りる。

【0062】
上述のインデックス生成部110-1は、検索モードにおいて、入力ベクトルXが供給されると、入力ベクトルXの全ビットのうち、ビットx4,x5,x6の値が、再生ベクトル生成回路113の副記憶部を構成するメモリに貯えられた値と一致する場合、比較回路114の一致信号MT1の値が‘1’となり、インデックスIDXの値がインデックスA1として出力される。また、入力ベクトルXのビットx4,x5,x6の値が上記の副記憶部を構成するメモリに貯えられた値と一致しない場合、比較回路114の一致信号MT1の値が‘0’となり、インデックスIDXの値を表すインデックスA1として無効値が出力される。この場合、インデックス生成部110-1から出力されるインデックスA1の全ビットが‘0’となる。

【0063】
上述したように、インデックス生成部110-1では、上述の図6に示す登録情報のうち、インデックスIDXの8個の値「4」、「5」、「2」、「1」、「11」、「10」、「15」、「3」と、これらのインデックスIDXの値に対応した登録ベクトルとの対応関係を規定する登録情報が実現される。しかしながら、インデックスIDXの残りの7個の値「7」、「9」、「13」、「14」、「12」、「6」、「8」をインデックス生成部110-1では実現できない。

【0064】
そこで、続いて、2番目のインデックス生成部110-2では、登録情報の登録ベクトルのビットx4,x5,x6に着目して、上述の図6に示す登録情報のうち、インデックスIDXの5個の値「7」、「13」、「12」、「6」、「8」と、これらのインデックスIDXの値に対応した登録ベクトルとの対応関係を規定する登録情報が実現される。
この場合、登録ベクトルのX2のビットx4,x5,x6を用いて、インデックス生成部110-2で実現する登録情報のインデックスIDXが決定される。

【0065】
図8は、本発明の第1実施形態による連想記憶装置100に備えられた2番目のインデックス生成部110-2で実現される登録情報を説明するための図である。この例では、上述の図6に示す登録情報のうち、インデックスIDXの5個の値「7」、「13」、「12」、「6」、「8」に関する登録情報が実現されている。しかしながら、インデックスIDXの残りの2個の値「9」、「14」をインデックス生成部110-2では実現できない。
なお、図8に示す例では、入力ベクトルXの全ビットのうち、ビットx1,x2,x3の値が再生ベクトル生成回路113の副記憶部を構成するメモリに貯えられた値と一致する場合、比較回路114の一致信号MT2の値が‘1’となる。

【0066】
そこで、最後に、3番目のインデックス生成部110-3では、図3Cを参照して説明したように、登録情報の登録ベクトルのビットx1,x2,x3とビットx4,x5,x6との排他的論理和の演算結果として得られるビットy1,y2,y3の値によって指定される上記の主記憶部及び副記憶部の各メモリセルに、残りのインデックスIDXの値「9」、「14」に関する登録情報が格納される。この場合、登録情報の登録ベクトルのビットx1,x2,x3とビットx4,x5,x6との排他的論理和の演算結果として得られるビットy1,y2,y3を用いて、インデックス生成部110-3で実現する登録情報のインデックスIDXが決定される。

【0067】
図9は、本発明の第1実施形態による連想記憶装置100に備えられた3番目のインデックス生成部110-3で実現される登録情報を説明するための図である。
この例では、上述の図6に示す登録情報のうち、インデックスIDXの5個の値「9」、「14」に関する登録情報が実現されている。この場合、登録情報のうち、インデックスIDXの値「9」、「14」に関する情報は、ビットy1,y2,y3の値によって指定される仮インデックス生成回路112の主記憶部のメモリセルに格納される。また、インデックスIDXの値「9」、「14」に対応した登録ベクトルのビット(y1,y2,y3,x4,x5,x6)の各値は、インデックスIDXの値「9」、「14」を表す仮のインデックスA’によって指定される再生ベクトル生成回路113の副記憶部のメモリセルに格納される。
なお、図9に示す例では、入力ベクトルXの全ビットのうち、ビットx4,x5,x6の値が再生ベクトル生成回路113の副記憶部を構成するメモリに貯えられた値と一致する場合、比較回路114の一致信号MT3の値が‘1’となる。

【0068】
このように、3個のインデックス生成部110-1,110-2,110-3を用いることにより、それぞれにおいてハッシュ衝突が発生したとしても、図6に示す15個のインデックスに関する登録情報の全てを実現することができる。

【0069】
2.動作の説明
次に、第1実施形態による連想記憶装置100の通常の検索モードでの動作を説明する。通常の検索モードでの動作時には、入力ベクトルXに応答して、3個のインデックス生成部110-1,110-2,110-3のうち、一つのインデックス生成部110-iが有効値を示すインデックスAiを出力する。他の二つのインデックス生成部110-iは無効値を出力する。出力部120は、3個のインデックス生成部110-1,110-2,110-3からそれぞれ出力されたインデックスA1,A2,A3を結合してインデックスAを生成して出力する。このインデックスAは、3個のインデックス生成部110-1,110-2,110-3から出力されたインデックスA1,A2,A3のうち、有効値を示すインデックスAiと同値になる。入力ベクトルXがインデックス生成部110-1,110-2,110-3に設定された登録ベクトルのいずれとも一致しない場合は、すべてのインデックス生成部110-1,110-2,110-3が無効値を生成する。

【0070】
以上により、通常の検索モードでは、3個のインデックス生成部110-1,110-2,110-3の何れかから、入力ベクトルXに対応した固有のインデックスAが得られ、このインデックスAが出力部120から出力される。従って、検索モードにおいて、3個のインデックス生成部110-1,110-2,110-3と出力部120とが一体となって、一つの連想メモリとして機能する。

【0071】
次に、連想記憶装置100の更新モードでの動作を説明する。
更新モードでの動作として、既存の登録情報を削除する動作と、新規な登録情報を追加する動作がある。更新モードにおいて、制御部130は、登録情報として登録された既存の登録ベクトルが存在する場合、その既存の登録ベクトルに対応するインデックスを削除した後、登録情報として新規な登録ベクトルのインデックスを追加することにより、登録情報を更新する。更新モードにおいて登録情報を更新するための動作は制御部130により制御される。

【0072】
2-1.既存の登録情報を削除する動作
ここでは、図13を参照して、上述した制御部130による既存の登録情報を削除する動作の一例について説明する。
図13は、本発明の第1実施形態による登録情報の削除方法の一例を示すフローチャートである。
既存の登録情報を削除する場合、連想記憶装置100を管理するシステム(図示なし)から、連想記憶装置100の制御部130に、更新モードの起動を示す指令信号UPDが供給される。そして、図13に示すように、指令信号UPDが制御部130に供給されると、制御部130は、削除すべき登録ベクトルを入力ベクトルとして、複数のインデックス生成部110-iに供給する(ステップS101)。すなわち、3個のインデックス生成部110-1,110-2,110-3には、削除すべき登録ベクトルが入力ベクトルXとして共通に供給される。

【0073】
次に、各インデックス生成部110-iは、該当する登録ベクトルが存在すれば、一致信号MTi=‘1’を出力する。また、各インデックス生成部110-iは、該当する登録ベクトルが存在しなければ、一致信号MTi=‘0’を出力する(ステップS102)。すなわち、インデックス生成部110-1,110-2,110-3は、それぞれ、該当する登録情報が存在すれば、一致信号MT1,MT2,MT3として値‘1’の信号を制御部130に供給し、該当する登録情報が存在しなければ、一致信号MT1,MT2,MT3として値‘0’の信号を制御部130に供給する。

【0074】
次に、制御部130は、一致信号MTiを参照して、削除すべき登録ベクトルが存在するインデックス生成部110-iを特定する(ステップS103)。すなわち、制御部130は、インデックス生成部110-1,110-2,110-3からそれぞれ供給される一致信号MT1,MT2,MT3の値を参照して、削除すべき登録ベクトルが存在するインデックス生成部を特定する。
ここで、削除すべき登録ベクトルが存在すると、衝突が発生するので、衝突信号CDiおよび一致信号MTiが値‘1’を示す。この一致信号MTiから削除すべき登録ベクトルに対応するインデックス生成部を特定することができる。

【0075】
次に、制御部130は、特定されたインデックス生成部110-iがあるか否かを判定する(ステップS104)。制御部130は、特定されたインデックス生成部110-iがある場合(ステップS104:YES)に、処理をステップS105に進める。また、制御部130は、特定されたインデックス生成部110-iがない場合(ステップS104:NO)に、処理を終了する。

【0076】
ステップS105において、制御部130は、削除すべき登録ベクトルが存在するインデックス生成部110-iに対して、WE=‘1’として、既存の登録ベクトルのインデックスの値を無効値に変更する。すなわち、制御部130は、書き込み動作を制御するためのライトイネーブル信号WEにより、3個のインデックス生成部110-1,110-2,110-3のうち、削除すべき登録インデックスに対応するインデックス生成部の主記憶部及び副記憶部をライトモードに設定し、これらの記憶部に格納された登録情報を削除する。具体的には、削除すべき登録インデックスが格納されたインデックス生成部110-iの主記憶部に格納された仮のインデックスの値を有効値から無効値に書き換える。例えば、インデックス生成部110-1の登録ベクトル(x1,x2,x3)=(0,1,1)に対するインデックスIDXを無効値に書き換える場合、インデックス生成部110-1の主記憶部を構成するメモリのアドレス(0,1,1)におけるインデックスIDXの内容を(0,0,0)に書き換える。これにより、システムから制御部130に供給された登録ベクトルに関する登録情報が削除された状態になる。

【0077】
上述の登録情報の削除に関する動作をまとめると、制御部130は、登録情報として登録された既存の登録ベクトルに対応するインデックスを削除する場合、複数のインデックス生成部110-1,110-2,110-3のうち、削除すべき登録ベクトルのインデックスを用いて生成された再生ベクトルX2’が入力ベクトルXのX2と一致する旨を示す一致信号MTiを供給するインデックス生成部を選択する。制御部130は、選択した当該インデックス生成部の登録情報から、既存の登録ベクトルのインデックスを削除する。

【0078】
更新モードにおいて登録情報を削除する場合、制御部130による制御は次の第1段階から第3段階を含む。
第1段階:更新モードにおいて、削除すべき既存の登録ベクトルを入力ベクトルXとして複数のインデックス生成部110-1,110-2,110-3に供給する。
第2段階:複数のインデックス生成部110-1,110-2,110-3のそれぞれについて、制御部130は、一致信号MTiに基づき、削除すべき既存の登録ベクトルに対応した固有のインデックスが登録情報として存在するか否かを判定する。
第3段階:複数のインデックス生成部110-1,110-2,110-3の何れかにおいて、既存の登録ベクトルに対応した固有のインデックスが登録情報として存在する場合、制御部130は、登録情報として存在する既存の登録ベクトルのインデックスの値を有効値から無効値に変更する。

【0079】
このように、既存の登録情報を削除する場合、制御部130が、一致信号MTiの値から、削除すべき既存の登録ベクトルが格納されているインデックス生成部を特定し、制御部130が各インデックス生成部の主記憶部と副記憶部を直接的にアクセスして登録情報を削除するので、登録情報を高速に削除することができる。従って、既存の登録情報の削除を伴う更新動作を高速に実施することが可能になる。

【0080】
2-2.新規な登録情報を追加する動作
ここでは、図14を参照して、上述した制御部130による新規な登録情報を追加する動作の一例について説明する。
図14は、本発明の第1実施形態による新規情報の追加方法の一例を示すフローチャートである。
新規な登録ベクトルを追加する場合、連想記憶装置100を管理するシステムから、連想記憶装置100の制御部130に、更新モードの起動を示す指令信号UPDが供給される。また、同システムから、追加すべき登録ベクトルのインデックスIDXが供給される。そして、図14に示すように、指令信号UPDとインデックスIDXとが制御部130に供給されると、制御部130は、追加登録ベクトルを入力ベクトルとして、複数のインデックス生成部110-iに供給する(ステップS201)。すなわち、3個のインデックス生成部110-1,110-2,110-3には、追加すべき登録ベクトルが入力ベクトルXとして供給される。

【0081】
次に、各インデックス生成部110-iは、該当する登録と衝突するベクトルが存在すれば、衝突信号CDi=‘1’を出力する。また、各インデックス生成部110-iは、該当する登録と衝突するベクトルが存在しなければ、衝突信号CDi=‘0’を出力する(ステップS202)。すなわち、インデックス生成部110-1,110-2,110-3は、それぞれ、該当する登録情報の仮のインデックスA’が存在すれば、衝突信号CD1,CD2,CD3として値‘1’の信号を制御部130に供給し、該当する登録情報が存在しなければ、衝突信号CD1,CD2,CD3として値‘0’の信号を制御部130に供給する。

【0082】
次に、制御部130は、衝突信号CDiを参照して、追加登録すべきベクトルと衝突する登録ベクトルが存在しないインデックス生成部110-iを特定する(ステップS203)。すなわち、制御部130は、インデックス生成部110-1,110-2,110-3からそれぞれ供給される衝突信号CD1,CD2.CD3の値を参照して、追加すべき登録ベクトルを登録可能なインデックス生成部を特定する。ここで、追加すべき登録ベクトルと衝突する登録ベクトルが存在すると、ハッシュ衝突が発生するので、衝突信号CDiが値‘1’を示す。この衝突信号CDiの値から登録ベクトルを追加可能なインデックス生成部を特定することができる。

【0083】
次に、制御部130は、特定されたインデックス生成部110-iがあるか否かを判定する(ステップS204)。制御部130は、特定されたインデックス生成部110-iがある場合(ステップS204:YES)に、処理をステップS205に進める。また、制御部130は、特定されたインデックス生成部110-iがない場合(ステップS204:NO)に、処理をステップS206に進める。

【0084】
ステップS205において、制御部130は、追加登録すべきインデックス生成部110-iに対して、WE=‘1’として、主記憶部に追加登録すべきベクトルのインデックスの値を書き込む。すなわち、制御部130は、ライトイネーブル信号WEにより、3個のインデックス生成部110-1,110-2,110-3のうち、追加すべき登録ベクトルと衝突する登録ベクトルが存在しないインデックス生成部の主記憶部及び副記憶部をライトモードに設定し、これらの記憶部に新規な登録情報を追加する。具体的には、追加すべき登録ベクトルと衝突する登録ベクトルが存在しないインデックス生成部の主記憶部に仮のインデックスの有効値を書き込む。例えば、インデックス生成部110-3に追加すべき登録ベクトルと衝突する登録ベクトルが存在しない場合、インデックス生成部110-3の主記憶部を構成するメモリのアドレス(y1,y2,y3)=(1,1,0)にインデックスの有効値を書き込む。これにより、システムから制御部130に供給された登録ベクトルに関する登録情報が連想記憶装置100に追加された状態になる。

【0085】
また、ステップS206において、制御部130は、追加不可を示す信号FALを出力する。すなわち、制御部130は、3個のインデックス生成部110-1,110-2,110-3の全てが、追加すべき登録ベクトルと衝突する登録ベクトルが存在する場合に、新規な登録情報の追加を行わない。そして、この場合、制御部130は、追加不可を示す信号FALを出力する。

【0086】
上述の登録情報の追加に関する動作をまとめると、制御部130は、登録情報として新規な登録ベクトルのインデックスを追加する場合、複数のインデックス生成部110-1,110-2,110-3のうち、新規な登録ベクトルが登録情報として格納されていない旨を示す衝突信号CDiを供給するインデックス生成部を選択する。制御部130は、選択した当該インデックス生成部の登録情報として、上記の追加すべき新規な登録ベクトルのインデックスを追加する。また、複数のインデックス生成部110-1,110-2,110-3の何れかにおいて、追加すべき新規な登録ベクトルに対応した仮のインデックスが登録情報として格納されている場合、制御部130は、新規な登録ベクトルに対応した仮のインデックスが存在しない他のインデックス生成部において、新規な登録ベクトルに対応したインデックスの値として有効値を設定する。

【0087】
更新モードにおいて登録情報を追加する場合、制御部130による制御は次の第1段階から第3段階を含む。
第1段階:追加すべき新規な登録ベクトルを入力ベクトルXとして複数のインデックス生成部110-1,110-2,110-3に供給する。
第2段階:複数のインデックス生成部110-1,110-2,110-3のそれぞれについて、制御部130により、衝突信号CDiに基づき、追加すべき新規な登録ベクトルに対応した仮のインデックスが登録情報として存在するか否かを判定する。
第3段階:複数のインデックス生成部110-1,110-2,110-3の何れかにおいて、新規な登録ベクトルに対応した仮のインデックスが登録情報として存在しない場合、新規な登録ベクトルに対応したインデックスの値として有効値を設定する。

【0088】
このように、新規な登録情報を追加する場合、制御部130が、一致信号MTiの値から、追加すべき登録ベクトルと衝突しないインデックス生成部を特定し、制御部130が各インデックス生成部の主記憶部と副記憶部を直接的にアクセスして登録情報を追加するので、登録情報を高速に追加することができる。従って、新規な登録情報の追加を伴う更新動作を高速に実施することが可能になる。

【0089】
上述したように、第1実施形態によれば、複数のインデックス生成部110-1,110-2,110-3において、複数のハッシュ関数を用いて入力ベクトルの特徴量を抽出し、この特徴量に基づいて仮のインデックスA’を生成するようにしたので、ハッシュ関数に起因したハッシュ衝突が発生しても、このハッシュ衝突を回避しつつ、汎用の半導体メモリを用いて登録情報を連想記憶装置100上に実現することができる。

【0090】
また、複数のインデックス生成部110-1,110-2,110-3,…,110-Nのそれぞれに備えられたハッシュ回路111が入力ベクトルXのビット数nよりも小さいpビットのベクトルY1を生成するようにしたので、ベクトルY1がアドレスとして入力される仮インデックス生成回路112の主記憶部を構成するメモリのアドレス空間を小さくすることができる。従って、上記の主記憶部を構成する半導体メモリの記憶容量を削減することができる。

【0091】
更に、ハッシュ回路111がハッシュ関数として線形関数を用いて入力ベクトルXの特徴量を抽出するようにしたので、再生ベクトル生成回路113の副記憶部には、登録ベクトルのビットの値として、登録ベクトルの一部の(n-p)ビットの値を格納しておけばよい。従って、再生ベクトル生成回路113の副記憶部を構成する半導体メモリの記憶容量を有効に削減することができる。
従って、第1実施形態によれば、ビットコストと消費電力の上昇を抑制しつつ、連想記憶装置100の記憶容量を大規模化することが可能となる。

【0092】
また、第1実施形態によれば、複数のインデックス生成部110-1,110-2,110-3のそれぞれにおいて、衝突信号CDiと一致信号MTiを発生させ、これらの信号を制御部130に供給するようにしたので、更新モードにおいて、制御部130は、衝突信号CDiと一致信号MTiを参照することにより、削除すべき登録情報が存在するインデックス生成部と、登録情報を追加可能なインデックス生成部とを直接的にアクセスすることにより登録情報を更新することができる。従って、登録情報の更新を高速化することが可能になる。

【0093】
(第2実施形態)
次に、本発明の第2実施形態を説明する。
図10は、本発明の第2実施形態による連想記憶装置200の構成例を示すブロック図である。

【0094】
連想記憶装置200は、上述の第1実施形態による図1に示す連想記憶装置100の構成において、複数のインデックス生成部110-1,110-2,110-3,…,110-Nに加えて、または、複数のインデックス生成部110-1,110-2,110-3,…,110-Nのうちの一部のインデックス生成部に代えて、連想メモリ110-Cを備えている。連想メモリ110-Cは、CAMセルを有する内容検索型の半導体メモリであり、例えば従来型のCAMを用いることができる。連想メモリ110-Cの動作(検索モード及び更新モードでの動作)は、制御部130により制御される。

【0095】
また、連想記憶装置200は、出力結合部220を更に備えている。出力結合部220は、第1実施形態による連想記憶装置100に備えられた出力部120から出力されるインデックスAと、連想メモリ110-Cから出力されるインデックスBとを結合して一つのインデックスCとして出力するためのものである。出力結合部220は、出力部120から出力されるインデックスAと、連想メモリ110-Cから出力されるインデックスBとのいずれか一方のインデックスを出力する。出力結合部220は、例えば、図5に示す出力部120と同様に、論理和ゲート回路から構成されている。その他は、第1実施形態と同様である。

【0096】
次に、図11及び図12を参照して、連想記憶装置200に備えられた連想メモリ110-Cについて説明する。
図11は、本発明の第2実施形態による連想記憶装置200に備えられた連想メモリ110-Cとして用いられる従来型のCAM1000の基本構成の一例を表すブロック図である(特許文献1参照)。CAM1000は、比較レジスタ1001、検索ビット線ドライバ1002、m個のワードW~W、m個の一致センス回路MSC~MSC、m個の一致フラグレジスタMFR~MFR、及びプライオリティ・エンコーダ(優先度付符号化回路)PEを備えている。

【0097】
比較レジスタ1001は、nビットの検索データを格納するレジスタである。検索ビット線ドライバ1002は、比較レジスタ1001の各ビットを検索ビット線上にドライブする。各ワードW~Wは、それぞれnビットのCAMセルを備えている。

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

【0099】
一致比較回路1005は、3つのnMOSトランジスタ(以下「nMOS」という。)1006,1007,1008を備えている。nMOS1006,1007は、検索ビット線SLNと検索ビット線SLとの間に直列に接続されている。nMOS1006,1007のゲートは、それぞれ、メモリセル1004のデータD,反転データDNに接続されている。nMOS1008は、一致線MLとグランドとの間に接続されている。nMOS1008のゲートは、nMOS1006,1007の間のノード1009に接続されている。

【0100】
まず、検索を行う前に、CAM1000のそれぞれのワードW~Wに、検索対象であるデータ(登録ベクトル)を記入する。各ワード内の各CAMセル1003において、メモリセル1004へのデータの書き込み及びメモリセル1004からのデータの読み出しは、通常のSRAMと同様にして行われる。

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

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

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

【0104】
尚、各ワードW~W内の各CAMセル1003における一致検索は、次のようにして実行される。

【0105】
まず、初期化動作を実行する。初期化動作では、検索ビット線対SL,SLNがともに‘L’(=‘0’)とされる。一方、メモリセル1004に記憶されているデータに応じて、一致比較回路1005のnMOS1006,1007のうち一方がオン状態、他方がオフ状態となる。従って、nMOS1006,1007のうちオン状態の方を介して、両者の間のノード1009のレベルが‘L’となり、nMOS1008はオフ状態となる。
この状態で、一致線MLが‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「一致」を表す。

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

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

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

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

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

【0111】
尚、TCAMとして使用する場合、ドント・ケアのビットについては、検索ビット線対SL,SLNをともに‘L’(=‘0’)としておけばよい。
以上で、第2実施形態による連想記憶装置200に備えられた連想メモリ110-Cとして用いられる従来型のCAM1000を説明した。

【0112】
上述した第2実施形態によれば、複数のインデックス生成部110-1,110-2,110-3,…,110-Nと共に連想メモリ110-Cを備えたので、110-1,110-2,110-3,…,110-Nにおいてハッシュ衝突を回避することができない場合であっても、連想メモリ110-Cは、任意の登録ベクトルの登録を実現することができるので、ハッシュ衝突に関する問題を完全に解消することができる。また、登録ベクトルのほとんどは、複数のインデックス生成部110-1,110-2,110-3,…,110-Nで実現できるので、連想メモリ110-Cの記憶容量は小さくてもよい。このため、連想メモリ110-Cの消費電力を抑制することができる。従って、第2実施形態よれば、第1実施形態と同様に、ビットコストと消費電力の上昇を抑制しつつ、連想記憶装置200の記憶容量の大規模化を実現することができると共に、ハッシュ関数に起因したハッシュ衝突を完全に回避することが可能になる。

【0113】
次に、参考として、第2実施形態の連想記憶装置200による更新動作の実験結果を述べる。4個のインデックス生成部110-iと1個のCAMとを組み合わせた場合、5個のインデックス生成部110-iと1個のCAMとを組み合わせた場合のそれぞれについて、C言語で開発したシミュレータを用いて更新動作の実験を実施した。この実験では、ランダムなベクトルを100万回更新するものとし、インデックス生成部110-iで発生したハッシュ衝突を回避するために必要なCAM(連想メモリ110-C)の記憶容量の大きさを求めた。この実験では、n=32、k=100000とし、入力ベクトルを発生させる乱数の生成法としてメルセンヌツイスタ法を用いた。

【0114】
実験での更新手順は次の通りである。
(手順1)k個の登録ベクトルを生成し、本発明による連想記憶装置100の複数のインデックス生成部110-iとCAMに格納する。
(手順2)複数の登録ベクトルの中からランダムに1つの登録ベクトルを取り出して、その登録ベクトルを連想記憶装置100から削除する。
(手順3)新規な登録ベクトルを生成し、連想記憶装置100に格納する。

【0115】
上記実験において、CAMに登録されたベクトルの個数の平均値と最大値を求める。上記実験によるシミュレーションの結果から得られた値と、確率計算により得られた値は、ほぼ一致した。連想記憶装置の実現に用いるFPGA(Field Programmable Gate Array)の制約を考慮すると、3個のインデックス生成部110-iと1個のCAMとの組み合わせの場合、CAMの語数が多くなり過ぎる。そのため、5個のインデックス生成部110-iと1個のCAMとの組み合わせが望ましい。
上記の実験により、上述の実施形態による連想記憶装置の有効性を確認することができた。

【0116】
以上、本発明の実施形態を説明したが、本発明は上述の実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲で種々の変形、変更、修正、置換等が可能である。
【符号の説明】
【0117】
100,200…連想記憶装置
110-1,110-2,110-3,110-i,110-N…インデックス生成部
110-C…連想メモリ
111…ハッシュ回路
112…仮インデックス生成回路
113…再生ベクトル生成回路
114…比較回路
115…出力回路
116…衝突信号生成回路
120…出力部
130…制御部
1000…CAM
1003…CAMセル
図面
【図1】
0
【図2】
1
【図3A】
2
【図3B】
3
【図3C】
4
【図4A】
5
【図4B】
6
【図4C】
7
【図5】
8
【図6】
9
【図7】
10
【図8】
11
【図9】
12
【図10】
13
【図11】
14
【図12】
15
【図13】
16
【図14】
17