Top > Search of Japanese Patents > (In Japanese)k近傍法連想メモリ

(In Japanese)k近傍法連想メモリ foreign

Patent code P170013665
File No. F13011-JP
Posted date Jan 25, 2017
Application number P2015-528142
Patent number P6327717
Date of filing Jul 17, 2014
Date of registration Apr 27, 2018
International application number JP2014003809
International publication number WO2015011907
Date of international filing Jul 17, 2014
Date of international publication Jan 29, 2015
Priority data
  • P2013-154887 (Jul 25, 2013) JP
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)赤澤 智信
  • (In Japanese)山崎 翔悟
Applicant
  • (In Japanese)国立大学法人広島大学
Title (In Japanese)k近傍法連想メモリ foreign
Abstract (In Japanese)k近傍法連想メモリ(100)は、R個の参照データを保持しており、R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリ(10)と、クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかK個のマッチ信号がアクティブになったことを検出し、そのときのR個のマッチ信号を保持するk近傍検索回路(20)と、R個の参照データのそれぞれのクラスを表すR個のクラスデータからk近傍検索回路が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、k個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路(30)とを備えている。
Outline of related art and contending technology (In Japanese)

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

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

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

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

Field of industrial application (In Japanese)

本発明は、連想メモリに関し、特に、k近傍法を効果的に実現する連想メモリに関する。

Scope of claims (In Japanese)
【請求項1】
 
R個の参照データを保持しており、前記R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリと、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになったことを検出し、そのときの前記R個のマッチ信号を保持するk近傍検索回路と、
前記R個の参照データのそれぞれのクラスを表すR個のクラスデータから前記k近傍検索回路が保持するアクティブのk個のマッチ信号のそれぞれに対応するk個のクラスデータを選択し、前記k個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路とを備えている
ことを特徴とするk近傍法連想メモリ。

【請求項2】
 
前記k近傍検索回路が、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちアクティブになったマッチ信号の数をカウントするマッチ信号カウント回路と、
前記マッチ信号カウント回路のカウント値がkに一致したことを検出するk-マッチ信号数一致検出回路と、
前記クロックカウント式連想メモリから出力されるR個のマッチ信号が入力され、前記k-マッチ信号数一致検出回路によって前記マッチ信号カウント回路のカウント値がkに一致したことが検出されたときの前記R個のマッチ信号を保持するマッチ信号保持回路とを有する、請求項1に記載のk近傍法連想メモリ。

【請求項3】
 
前記クロックカウント式連想メモリが、前記k-マッチ信号数一致検出回路によって前記マッチ信号カウント回路のカウント値がkに一致したことが検出されたとき、動作を停止するように構成されている、請求項2に記載のk近傍法連想メモリ。

【請求項4】
 
前記k-マッチ信号数一致検出回路が、前記マッチ信号カウント回路のカウント値がkを超えたことを検出するように構成されている、請求項2および3のいずれか一つに記載のk近傍法連想メモリ。

【請求項5】
 
前記マッチ信号カウント回路が、複数の加算器がツリー状に接続されてなり、リーフノードの複数の加算器に前記R個のマッチ信号がそれぞれ入力され、ルートノードの加算器からカウント値を出力する加算器ツリー回路である、請求項2から4のいずれか一つに記載のk近傍法連想メモリ。

【請求項6】
 
前記k近傍クラスタリング回路が、
前記R個のクラスデータを保持するクラスデータメモリと、
X個のクラスのそれぞれに対応するX個のクラスカウンタと、
前記k近傍検索回路が保持するアクティブのk個のマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータを前記クラスデータメモリから読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタをカウントアップするクラス識別回路と、
前記X個のクラスカウンタの中からカウント値が最大のクラスカウンタを見つける最大カウンタ検出回路とを有する、請求項1から5のいずれか一つに記載のk近傍法連想メモリ。

【請求項7】
 
前記クラス識別回路が、前記k近傍検索回路が保持するR個のマッチ信号のそれぞれに対応して設けられ、対応するマッチ信号がアクティブであることを検出して前記クラスデータメモリに当該マッチ信号に対応するクラスデータを選択する選択信号を出力するR個のマッチ信号検出回路を有し、
前記R個のマッチ信号検出回路が、動作開始信号を伝搬するように直列に接続されており、
前記R個のマッチ信号検出回路のそれぞれが、前記対応するマッチ信号が非アクティブのとき、入力された前記動作開始信号をすぐさま次段に伝達し、前記対応するマッチ信号がアクティブのとき、前記動作開始信号を受けて前記選択信号を出力してから前記動作開始信号を次段に伝達するように構成されている、請求項6に記載のk近傍法連想メモリ。

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

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

※Click image to enlarge.

JP2015528142thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close