Top > Search of Japanese Patents > (In Japanese)連想記憶装置、インデックス生成器、及び登録情報更新方法

(In Japanese)連想記憶装置、インデックス生成器、及び登録情報更新方法

Patent code P170014151
File No. (S2014-1403-N0)
Posted date May 29, 2017
Application number P2016-544229
Patent number P6229990
Date of filing Aug 19, 2015
Date of registration Oct 27, 2017
International application number JP2015073227
International publication number WO2016027829
Date of international filing Aug 19, 2015
Date of international publication Feb 25, 2016
Priority data
  • P2014-168777 (Aug 21, 2014) JP
Inventor
  • (In Japanese)笹尾 勤
Applicant
  • (In Japanese)学校法人明治大学
Title (In Japanese)連想記憶装置、インデックス生成器、及び登録情報更新方法
Abstract (In Japanese)本発明による連想記憶装置は、複数のインデックス生成部、出力部、制御部を備える。前記複数のインデックス生成部は、複数のハッシュ関数を用いて入力ベクトルの特徴量を生成し、前記特徴量に基づき登録ベクトルに関する登録情報を検索することにより前記入力ベクトルに対応したインデックスを生成する。前記複数のインデックス生成部は、前記インデックスが前記登録情報として存在するか否かを示す第1信号を生成すると共に、再生ベクトルを生成し、前記再生ベクトルが前記入力ベクトルと一致するか否かを示す第2信号を生成して前記制御部に供給する。前記出力部は、前記複数のインデックス生成部の各出力を結合してインデックスを出力する。制御部は、前記登録情報の更新を制御する。
Outline of related art and contending technology (In Japanese)

通常のメモリは、与えられたアドレス(インデックス)に対して、そのアドレスに格納されている登録データを生成する。一方、CAM(Content Addressable Memory)は、与えられた検索(入力)データに対して、それを格納する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の両方にマッチする。

CAMの機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェアを用いてCAMを実現することが多い。

Field of industrial application (In Japanese)

本発明は、連想記憶装置、インデックス生成器、及び登録情報更新方法に関し、特に、連想記憶装置に備えられたインデックス生成器に登録された登録情報の更新を高速化するための技術に関する。

Scope of claims (In Japanese)
【請求項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に記載の情報更新方法。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2016544229thum.jpg
State of application right Registered
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