Top > Search of Japanese Patents > ASSOCIATIVE MEMORY

ASSOCIATIVE MEMORY

Patent code P150012573
File No. S2014-0188-N0
Posted date Nov 20, 2015
Application number P2014-022398
Publication number P2015-149113A
Patent number P6215726
Date of filing Feb 7, 2014
Date of publication of application Aug 20, 2015
Date of registration Sep 29, 2017
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)赤澤 智信
  • (In Japanese)山崎 翔悟
Applicant
  • (In Japanese)国立大学法人広島大学
Title ASSOCIATIVE MEMORY
Abstract PROBLEM TO BE SOLVED: To expand the number of data dimensions that can be handled in an associative memory.
SOLUTION: An associative memory 100 includes: a retrieval data storage circuit 5 for storing retrieval data in E*M dimensions into retrieval data in M dimension each for E times; a reference data storage circuit SC for storing R reference data in E*M dimensions into reference data in M dimensions for E times; a distance calculation circuit DC for calculating partial distance of each dimension between retrieval data and reference data each time new data are stored in the retrieval data storage circuit and the reference data storage circuit; a number-of-dimensions expansion circuit DEC for accumulating and adding partial distance of each dimension each time when new data are stored in the retrieval data storage circuit and the reference data storage circuit; and a distance/number-of-clocks conversion circuit DE for totaling the accumulated and added partial distance and calculating distance between the retrieval data in E*M dimensions and the reference data in E*M dimensions after the retrieval data and the reference data are stored in the respective data storage circuits for E times each, and for outputting a timing signal for indicating timing at which the number of clocks corresponding to the distance is counted.
Outline of related art and contending technology (In Japanese)

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

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

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

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

Field of industrial application (In Japanese)

本発明は、連想メモリに関し、特に、クロックカウント式の連想メモリの次元数を拡張する技術に関する。

Scope of claims (In Japanese)
【請求項1】
 
E×M次元(ただし、E,Mはいずれも2以上の整数である。)の検索データをM次元ずつE回に分けて保存する検索データ保存回路と、
R個(ただし、Rは2以上の整数である。)のE×M次元の参照データをR個のM次元ずつE回に分けて保存する参照データ保存回路と、
前記検索データ保存回路および前記参照データ保存回路に新たなデータが保存されるたびに、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の部分距離を計算する距離計算回路と、
前記検索データ保存回路および前記参照データ保存回路に新たなデータが保存されるたびに、個々の参照データごとに、前記距離計算回路によって計算された各次元の部分距離を累積加算する次元数拡張回路と、
前記E×M次元の検索データおよび前記R個のE×M次元の参照データがそれぞれE回に分けて前記検索データ保存回路および前記参照データ保存回路に保存された後に、個々の参照データごとに、前記次元数拡張回路によって累積加算された部分距離を合計して前記E×M次元の検索データと個々の前記E×M次元の参照データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号を出力する距離/クロック数変換回路とを備えている
ことを特徴とする連想メモリ。

【請求項2】
 
前記次元数拡張回路が、第1および第2のマルチプレクサと、全加算器と、第1および第2のDフリップフロップとを有するものであり、
前記第1のマルチプレクサは、前記距離計算回路によって計算された第1の次元の部分距離および前記第1のDフリップフロップの出力がそれぞれ第1および第2の入力として与えられ、第1の制御信号によって前記第1および第2の入力のいずれか一方を選択的に出力するものであり、
前記第2のマルチプレクサは、前記距離計算回路によって計算された第2の次元の部分距離および前記第2のDフリップフロップの出力がそれぞれ第1および第2の入力として与えられ、前記第1の制御信号によって前記第1および第2の入力のいずれか一方を選択的に出力するものであり、
前記全加算器は、前記第1のマルチプレクサの出力と前記第2のマルチプレクサの出力とを全加算するものであり、
前記第1のDフリップフロップは、前記全加算器の出力がデータ入力され、第2の制御信号によって入力データの保存が制御されるものであり、
前記第2のDフリップフロップは、前記全加算器の出力がデータ入力され、前記第2の制御信号の反転である第3の制御信号によって入力データの保存が制御されるものである
ことを特徴とする請求項1に記載の連想メモリ。

【請求項3】
 
前記距離計算回路が、前記部分距離として、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の差分絶対値を計算する
ことを特徴とする請求項1または請求項2に記載の連想メモリ。

【請求項4】
 
前記距離計算回路が、前記部分距離として、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の差分二乗値を計算する
ことを特徴とする請求項1または請求項2に記載の連想メモリ。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2014022398thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close