Top > Search of Japanese Patents > ASSOCIATIVE MEMORY

ASSOCIATIVE MEMORY

Patent code P130008705
File No. 12070,S2012-1038-N0
Posted date Mar 18, 2013
Application number P2013-025465
Publication number P2014-154196A
Patent number P6085187
Date of filing Feb 13, 2013
Date of publication of application Aug 25, 2014
Date of registration Feb 3, 2017
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)佐々木 静龍
  • (In Japanese)赤澤 智信
Applicant
  • (In Japanese)国立大学法人広島大学
Title ASSOCIATIVE MEMORY
Abstract PROBLEM TO BE SOLVED: To provide an associative memory such that similarity retrieval can be accurately performed even when Euclidean distances are used.
SOLUTION: An associative memory 100 includes: distance arithmetic circuits DP11 to DPRW which calculate Manhattan distances between R (R: an integer equal to or larger than 2) reference data having a bit length of M×W (W: an integer equal to or larger than 1, W: an integer equal to or larger than 2) bits and retrieval data having a bit length of M×W bits; and distance/clock number conversion circuits DC1 to DCR. The distance/clock number conversion circuits DC1 to DCR use the Manhattan distances calculated by the corresponding distance arithmetic circuits to detect the numbers of clocks matching Euclidean distances between the reference data and retrieval data. The distance/clock number conversion circuits output timing signals indicative of timings when the numbers of clocks matching the Euclidean distances of the reference data to the retrieval data.
Outline of related art and contending technology (In Japanese)

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

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

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

連想メモリを実現する手段として(1)ディジタル方式による実現方法(非特許文献1)、(2)アナログ方式による実現方法および(3)ディジタル・アナログ融合方式(非特許文献2)等が提案されている。

Field of industrial application (In Japanese)

この発明は、連想メモリに関するものである。

Scope of claims (In Japanese)
【請求項1】
 
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、
前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとの差の絶対値を表すR×W個の絶対値差を、前記検索データと前記参照データの距離として算出する第1距離算出手段と、
前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力するタイミング信号出力処理を、前記R個の参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。

【請求項2】
 
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記各参照データにつき、前記W個の絶対値差の各々に一致する回数だけ、前記絶対値差と一致するクロック数を検出する処理を繰り返すことにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項1に記載の連想メモリ。

【請求項3】
 
前記各参照データにつき、前記第1距離算出手段で算出された前記W個の絶対値差の各々の二乗値を算出することにより、前記検索対象の検索データと前記参照データとの距離として、前記W個の絶対値差の二乗値を算出する第2距離算出手段を更に備え、
前記タイミング信号出力手段は、前記タイミング信号出力処理として、前記参照データごとに、前記第2距離算出手段で算出された前記W個の前記絶対値差の二乗値の和に一致するクロック数を検出することにより、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力する、請求項1に記載の連想メモリ。

【請求項4】
 
マンハッタン距離とユークリッド距離のいずれかの距離を選択する選択手段を備え、
前記タイミング信号出力手段は、
(1)前記選択手段によって前記マンハッタン距離が選択された場合、前記各参照データにつき、前記W個の絶対値差の和に一致するクロック数を検出したタイミングを示す前記タイミング信号を出力し、
(2)前記選択手段によって前記ユークリッド距離が選択された場合、前記参照データごとに、前記第1距離算出手段で算出された前記距離を用い、前記参照データと前記検索データとのユークリッド距離に一致するクロック数を検出したタイミングを示すタイミング信号を出力する
請求項1から請求項3のいずれか一項に記載の連想メモリ。

【請求項5】
 
各々がM×W(Mは1以上の整数、Wは2以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存手段と、
前記R個の参照データに対応して設けられ、M×Wビットのビット長を有する検索対象の検索データと前記参照データとのR×W個の距離を算出する距離算出手段と、
前記参照データごとに、前記距離算出手段で算出された距離を表すビットのうち、設定された対象ビットの値と一致するクロック数を検出したタイミングで一致検出信号を出力する一致検出手段と、
前記各参照データについて算出された前記距離を表す最上位ビットから順に、予め定められたビット単位に前記対象ビットを設定し、いずれかの前記参照データについて、前記対象ビットに対する前記一致検出信号が出力される毎に、前記対象ビットを拡張するビット設定手段と、
前記各参照データについて、前記距離を表す全てのビットに対する前記一致検出信号が出力されたタイミングを示すタイミング信号を出力する処理を、R個の前記参照データについて行うタイミング信号出力手段と、
前記タイミング信号出力手段から出力されるR個のタイミング信号に基づいて、前記タイミング信号の出力が早い順に、k個(kは1≦k<Rを満たす整数)の前記タイミング信号を検出し、検出した前記k個のタイミング信号を、前記検索データと前記参照データとの類似度を示すマッチ信号として出力するマッチ信号出力手段と、
を備える連想メモリ。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2013025465thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close