Top > Search of Japanese Patents > K VICINITY METHOD ASSOCIATION MEMORY WHICH CAN BE RECONFIGURED

K VICINITY METHOD ASSOCIATION MEMORY WHICH CAN BE RECONFIGURED

Patent code P170013653
File No. 14074
Posted date Jan 25, 2017
Application number P2015-034716
Publication number P2016-157496A
Patent number P6411914
Date of filing Feb 25, 2015
Date of publication of application Sep 1, 2016
Date of registration Oct 5, 2018
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)山崎 翔悟
Applicant
  • (In Japanese)国立大学法人広島大学
Title K VICINITY METHOD ASSOCIATION MEMORY WHICH CAN BE RECONFIGURED
Abstract PROBLEM TO BE SOLVED: To provide a k vicinity method association memory which can expand a dimension and a number of reference data.
SOLUTION: A k vicinity method association memory (100) which can be reconfigured comprises: a clock count type association memory (10) which can be reconfigured; and a k vicinity clustering circuit (30). The association memory (10) comprises: plural element circuits (70); and plural switch circuits (50) for optionally connecting the plural element circuits. Until some k pieces of match signals out of plural match signals output from the association memory (10) become an active state, the k vicinity clustering circuit (30) selects class data corresponding to each and at least one of the k pieces of match signals, which become the active state, from plural pieces of class data indicating classes of plural pieces of reference data, for every time that at least one of the plural match signals become the active state, and then determines a class in which a number of data becomes maximum, when the all k pieces of class data being selected, are classified for every class.
Outline of related art and contending technology (In Japanese)

近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI(Large Scale Integrated Circuit)上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。

パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。

前者は、CAM(Content Addressable Memory)と呼ばれ、ネットワークルータのIPアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ(Associative Memory)と呼ぶ。

連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている(非特許文献1参照)。また、連想メモリにk近傍探索を取り入れたものが知られている(非特許文献2参照)。

また、本願発明者は、検索に係るクロックカウント数を削減する機構(有効ビット設定部)とユークリッド距離検索のための二乗計算回路(距離演算回路)とを備えたクロックカウント式の連想メモリを発明している(特許文献1参照)。当該発明によれば、データ規模が増大しても高速な検索が可能なユークリッド/マンハッタン距離検索連想メモリをエラーフリー、高電力効率に実現することができる。

一方、パターン認識の分野において機械学習アルゴリズムとしてk近傍法がよく用いられる。本願発明者は、連想メモリを用いてk近傍法を効果的に実現することができるk近傍法連想メモリを発明している(特許文献2参照)。

Field of industrial application (In Japanese)

本発明は、連想メモリに関し、特に、k近傍法を効果的に実現する連想メモリに保存される参照データの次元数および個数を拡縮する技術に関する。

Scope of claims (In Japanese)
【請求項1】
 
それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離/クロック数変換回路とを有する、複数のエレメント回路と、
前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路と、
k近傍法に従って前記検索データのクラスを判定するk近傍クラスタリング回路とを備え、
前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する複数の参照データ検索回路からなる再構成可能なクロックカウント式連想メモリが構成され、
前記k近傍クラスタリング回路は、前記再構成可能なクロックカウント式連想メモリから出力される複数のマッチ信号のうちいずれかk個のマッチ信号がアクティブになるまでの間、前記複数のマッチ信号の少なくとも一つがアクティブになるごとに、前記複数の参照データ検索回路のそれぞれが保存する参照データのクラスを表す複数のクラスデータから当該アクティブになった少なくとも一つのマッチ信号のそれぞれに対応するクラスデータを選択し、当該選択した全部でk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するように構成されている
ことを特徴とする再構成可能なk近傍法連想メモリ。

【請求項2】
 
前記k近傍クラスタリング回路が、
前記複数のクラスデータを保持するクラスデータメモリと、
X個のクラスのそれぞれに対応するX個のクラスカウンタと、
前記アクティブになった少なくとも一つのマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータを前記クラスデータメモリから読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタをカウントアップし、前記アクティブになった少なくとも一つのマッチ信号をすべて選択し終わると終了信号を出力するクラス識別回路と、
前記X個のクラスカウンタの中からカウント値が最大のクラスカウンタを見つける最大カウンタ検出回路と、
前記クラス識別回路がアクティブになったマッチ信号を一つ選択するごとにカウントアップし、カウント値がkに一致したことを検出するk-マッチ信号数一致検出回路とを有するものであり、
前記再構成可能なk近傍法連想メモリが、前記複数のマッチ信号の少なくとも一つがアクティブになると前記再構成可能なクロックカウント式連想メモリの動作を停止させて前記クラス識別回路を動作させ、前記クラス識別回路から前記終了信号が出力されると前記クラス識別回路の動作を停止させて前記再構成可能なクロックカウント式連想メモリを動作させる制御回路を備え、
前記再構成可能なクロックカウント式連想メモリが、前記k-マッチ信号数一致検出回路によって前記カウント値がkに一致したことが検出されたとき、動作を停止するように構成されている、請求項1に記載の再構成可能なk近傍法連想メモリ。

【請求項3】
 
前記制御回路が、
前記複数のスイッチ回路のそれぞれに対応して設けられ、対応するスイッチ回路が前記回路構成信号に応じて選択的に出力する前段のエレメント回路のマッチ信号がアクティブになってから前記クラス識別回路から前記終了信号が出力されるまでの間だけアクティブになる検出信号を出力する複数のマッチ信号アクティブ検出回路と、
前記複数のマッチ信号アクティブ検知回路から出力される複数の検出信号の論理和を演算するORゲートとを有し、
前記ORゲートの出力信号で前記クラス識別回路および前記再構成可能なクロックカウント式連想メモリの動作を制御する、請求項2に記載の再構成可能なk近傍法連想メモリ。

【請求項4】
 
前記クラス識別回路が、前記複数のスイッチ回路のそれぞれに対応して設けられ、対応するスイッチ回路が前記回路構成信号に応じて選択的に出力する前段のエレメント回路のマッチ信号がアクティブであることを検出して前記クラスデータメモリに当該マッチ信号に対応するクラスデータを選択する選択信号を出力する複数のマッチ信号検出回路を有し、
前記複数のマッチ信号検出回路が、動作開始信号を伝搬するように直列に接続されており、
前記複数のマッチ信号検出回路のそれぞれが、前記対応するスイッチ回路から出力されるマッチ信号が非アクティブのとき、入力された前記動作開始信号をすぐさま次段に伝達し、前記対応するスイッチ回路から出力されるマッチ信号がアクティブのとき、前記動作開始信号を受けて前記選択信号を出力してから前記動作開始信号を次段に伝達するように構成されている、請求項2および3いずれか一つに記載の再構成可能なk近傍法連想メモリ。

【請求項5】
 
前記最大カウンタ検出回路が、
初期値からカウント値をカウントダウンするダウンカウンタと、
前記X個のクラスカウンタのそれぞれに対応して設けられ、対応するクラスカウンタのカウント値と前記ダウンカウンタのカウント値との一致を検出するX個の一致検出回路とを有し、
前記ダウンカウンタのカウント値がカウントダウンされている間に、前記X個の一致検出回路のうちのいずれか一つによって前記ダウンカウンタのカウント値と対応するクラスカウンタのカウント値との一致が検出されたとき、前記ダウンカウンタのカウント動作を停止させる、請求項2ないし4のいずれか一つに記載の再構成可能なk近傍法連想メモリ。

【請求項6】
 
前記最大カウンタ検出回路が、2入力1出力の複数の最大値選出回路がツリー状に接続されてなり、リーフノードの複数の最大値選出回路に前記X個のクラスカウンタの各カウント値および各クラスカウンタの識別番号を結合した各信号が入力され、ルートノードの最大値選出回路から前記X個のクラスカウンタの最大カウント値およびそのクラスカウンタの識別番号を結合した信号を出力するトーナメント回路であり、
前記最大値選出回路が、第1のクラスカウンタのカウント値および前記第1のクラスカウンタの識別番号を結合した第1の信号、および第2のクラスカウンタのカウント値および前記第2のクラスカウンタの識別番号を結合した第2の信号を受け、前記第1および第2のクラスカウンタのうちカウント値が大きい方のクラスカウンタのカウント値およびそのクラスカウンタの識別番号を結合した第3の信号を出力する、請求項2ないし4のいずれか一つに記載の再構成可能なk近傍法連想メモリ。

【請求項7】
 
回路構成情報を記憶し、当該回路構成情報に基づいて前記複数のスイッチ回路のそれぞれに前記回路構成信号を出力する回路構成情報記憶回路を備えている
ことを特徴とする請求項1ないし請求項3のいずれかに記載の再構成可能なk近傍法連想メモリ。

【請求項8】
 
前記回路構成情報記憶回路が不揮発性メモリで構成されている
ことを特徴とする請求項7に記載の再構成可能なk近傍法連想メモリ。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2015034716thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close