Top > Search of Japanese Patents > CONTENT ADDRESSABLE MEMORY

CONTENT ADDRESSABLE MEMORY

Patent code P130008462
File No. 12024,S2012-0663-N0
Posted date Jan 8, 2013
Application number P2012-183975
Publication number P2014-041676A
Patent number P5916563
Date of filing Aug 23, 2012
Date of publication of application Mar 6, 2014
Date of registration Apr 15, 2016
Inventor
  • (In Japanese)マタウシュ ハンスユルゲン
  • (In Japanese)小出 哲士
  • (In Japanese)佐々木 静龍
  • (In Japanese)赤澤 智信
Applicant
  • (In Japanese)国立大学法人広島大学
Title CONTENT ADDRESSABLE MEMORY
Abstract PROBLEM TO BE SOLVED: To provide a content addressable memory which allows accurate and rapid similarity search even when using Manhattan distances.
SOLUTION: The content addressable memory includes R distance/clock count conversion circuits DC1 to DCR each of which includes counter matching detection circuits 31 to 3W. Each of distance signals D11 to D1W represents a distance between search data and reference data. The counter matching detection circuit 31 counts the number of clocks for acquisition of a counter value matching the distance signal D11, and then the counter matching detection circuit 32 counts the number of clocks for acquisition of a counter value matching the distance signal D12. The same operation is performed hereafter, and the counter matching detection circuit 3W counts the number of clocks for acquisition of a counter value matching a distance signal D1W after the counter matching detection circuit 3W-1 counts the number of clocks for acquisition of a counter value matching a distance signal D1W-1.
Outline of related art and contending technology (In Japanese)

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

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

前者は、CAM(Contents 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個の距離信号を出力するR個の距離演算回路と、
前記R個の距離演算回路に対応して設けられ、各々が対応する距離演算回路から各々がMビットのビット長を有するW個の距離信号を受け、その受けたW個の距離信号の和に一致するカウンタ値が得られるときのクロック信号のクロック数をカウントし、前記クロック数をカウントしたタイミングである一致タイミングを示すタイミング信号を出力するR個の距離/クロック数変換回路と、
前記R個の距離/クロック数変換回路から受けたR個のタイミング信号に基づいて、前記一致タイミングが早い順にk(kは1≦k<Rを満たす整数)個のタイミング信号を検出し、その検出したk個のタイミング信号を前記検索データと前記参照データとの類似度を示すマッチ信号として出力するWinner検出器とを備える連想メモリ。

【請求項2】
 
前記R個の距離/クロック数変換回路の各々は、各々がMビットのビット長を有するW個の距離信号に対応して設けられ、かつ、直列に接続されたW個のカウンタ一致検出回路を含み、
前記W個のカウンタ一致検出回路は、W=2である場合、
前記W個の距離信号を一列に配列したときの一方端の距離信号である1番目の距離信号に対応して設けられ、前記1番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けた1番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第1のクロック数をカウントし、前記第1のクロック数をカウントしたタイミングを示す第1の一致信号を出力する第1のカウンタ一致検出回路と、
前記一方端からW番目の距離信号に対応して設けられ、前記第1のカウンタ一致検出回路から前記第1の一致信号を受けると駆動されるとともに前記W番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第2のクロック数をカウントし、前記第2のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する第2のカウンタ一致検出回路とを含み、
前記W個のカウンタ一致検出回路は、Wが3以上である場合、
前記第1のカウンタ一致検出回路と、
2番目の距離信号からW-1番目の距離信号までのW-2個の距離信号に対応して設けられ、各々が、前記第1のカウンタ一致検出回路またはw-1(wは2≦w≦W-1を満たす整数)番目の距離信号に対応して設けられたカウンタ一致検出回路から前記1番目または前記w番目の距離信号に一致するカウンタ値が得られるときのクロック信号のクロック数をカウントしたタイミングを示す第2の一致信号を受けると駆動されるとともに前記w番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたw番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第3のクロック数をカウントし、前記第3のクロック数をカウントしたタイミングを示す第3の一致信号を出力するW-2個の第3のカウンタ一致検出回路と、
W番目の距離信号に対応して設けられ、W-1番目の距離信号に対応して設けられたカウンタ一致検出回路から前記第3の一致信号を受けると駆動されるとともに前記W番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第4のクロック数をカウントし、前記第4のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する第4のカウンタ一致検出回路とを含む、請求項1に記載の連想メモリ。

【請求項3】
 
前記第1のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第1のカウンタと、
前記第1のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記1番目の距離信号を受け、前記受けたカウンタ値が前記1番目の距離信号に一致するときの前記第1のクロック数をカウントし、前記第1のクロック数が得られると、前記第1の一致信号を出力する第1の一致検出回路とを含み、
前記第2のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第2のカウンタと、
前記第2のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記W番目の距離信号を受け、前記第1のカウンタ一致検出回路から前記第1の一致信号を受けると駆動され、前記受けたカウンタ値が前記W番目の距離信号に一致するときの前記第2のクロック数をカウントし、前記第2のクロック数が得られると、前記タイミング信号を前記Winner検出器へ出力する第2の一致検出回路とを含み、
前記W-2個の第3のカウンタ一致検出回路の各々は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第3のカウンタと、
前記第3のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記w番目の距離信号を受け、前記第2の一致信号を受けると駆動され、前記受けたカウンタ値が前記w番目の距離信号に一致するときの前記第3のクロック数をカウントし、前記第3のクロック数が得られると、前記第3の一致信号を出力する第3の一致検出回路とを含み、
前記第4のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第4のカウンタと、
前記第4のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記W番目の距離信号を受け、前記第3の一致信号を受けると駆動され、前記受けたカウンタ値が前記W番目の距離信号に一致するときの前記第4のクロック数をカウントし、前記第4のクロック数が得られると、前記タイミング信号を前記Winner検出器へ出力する第4の一致検出回路とを含む、請求項2に記載の連想メモリ。

【請求項4】
 
前記Wは、2i(iは2以上の整数)からなり、
前記R個の距離/クロック数変換回路の各々は、W/s(sはW以下である2xに等しい。xは正の整数)個の距離信号に対応して設けられ、各々がMビットのビット長を有するW個の距離信号に基づいて、前記タイミング信号を出力するW/s個のカウンタ一致検出回路を含み、
前記W/s個のカウンタ一致検出回路は、各々が前記W/s個の距離信号からなるs組の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたs組の距離信号に含まれるW個の距離信号の和に一致するカウンタ値が得られるときの前記クロック数をカウントし、前記クロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する、請求項1に記載の連想メモリ。

【請求項5】
 
前記W/s個のカウンタ一致検出回路は、前記W/s個の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW/s個の距離信号の和に一致するカウンタ値が得られるときのクロック信号の第1のクロック数をカウントし、前記第1のクロック数をカウントしたタイミングを示す第1の一致信号を出力する処理をs-1回繰り返し実行し、前記第1の一致信号を前記s-1回出力し、かつ、s回目に前記W/s個の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたW/s個の距離信号の和に一致するカウンタ値が得られるときのクロック信号の第2のクロック数をカウントし、前記第2のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する、請求項4に記載の連想メモリ。

【請求項6】
 
前記W/s個のカウンタ一致検出回路は、
前記W個の距離信号を一列に配列したときの一方端からp(pは1≦p<Wを満たす奇数)番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記p番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第3のクロック数をカウントし、前記第3のクロック数をカウントしたタイミングを示す第2の一致信号を出力する第1の一致処理をW/2回繰り返し実行する第1のカウンタ一致検出回路と、
前記一方端からq(qは1<q≦Wを満たす偶数)番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記q番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第4のクロック数をカウントし、前記第4のクロック数をカウントしたタイミングを示す第3の一致信号を出力する第2の一致処理を((W/2)-1)回繰り返し実行し、前記第2の一致信号を前記W/2回受け、かつ、W番目の距離信号を受けると、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記W番目の距離信号に一致するカウンタ値が得られるときのクロック信号の第5のクロック数をカウントし、前記第5のクロック数をカウントしたタイミングを示す前記タイミング信号を前記Winner検出器へ出力する第2のカウンタ一致検出回路とを含む、請求項4に記載の連想メモリ。

【請求項7】
 
前記R個の距離/クロック数変換回路の各々は、
前記第1のカウンタ一致検出回路から前記第2の一致信号を受けると、その受けた第2の一致信号を前記第2のカウンタ一致検出回路へ出力し、前記第2のカウンタ一致検出回路から前記第3の一致信号を受けると、その受けた第3の一致信号を前記第1のカウンタ一致検出回路へ出力するスイッチング制御回路を更に含み、
前記第1のカウンタ一致検出回路は、前記スイッチング制御回路から前記第3の一致信号を受ける毎に前記第1の一致処理を1回実行し、
前記第2のカウンタ一致検出回路は、前記スイッチング制御回路から前記第2の一致信号を受ける毎に前記第2の一致処理を1回実行するとともに、前記第2の一致信号を前記W/2回受けると、前記第5のクロック数をカウントし、前記タイミング信号を前記Winner検出器へ出力する、請求項6に記載の連想メモリ。

【請求項8】
 
前記第1のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第1の出力処理を前記W/2回繰り返し実行する第1のカウンタと、
前記第1のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記p番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたカウンタ値が前記p番目の距離信号に一致するときの前記第3のクロック数をカウントし、前記第2の一致信号を出力する第2の出力処理を前記W/2回繰り返し実行する第1の一致検出回路とを含み、
前記第2のカウンタ一致検出回路は、
Mビットのビット値を昇順にカウントし、そのカウントしたカウンタ値を順次出力する第3の出力処理を前記W/2回繰り返し実行する第2のカウンタと、
前記第2のカウンタから前記カウンタ値を順次受けるとともに前記距離演算回路から前記q番目の距離信号を受け、カウンタ値をクロック信号に同期して昇順にカウントしたときに、前記受けたカウンタ値が前記q番目の距離信号に一致するときの前記第4のクロック数をカウントし、前記第3の一致信号を出力する第2の出力処理を前記((W/2)-1)回繰り返し実行し、前記第2の一致信号を前記W/2回受けると、前記受けたカウンタ値が前記W番目の距離信号に一致するときの前記第5のクロック数をカウントし、前記タイミング信号を前記Winner検出器へ出力する第2の一致検出回路とを含む、請求項6または請求項7に記載の連想メモリ。

【請求項9】
 
前記第1から第4のカウンタの各々は、Mビットのカウンタ値を昇順に出力するM個の分周器からなり、
前記Mビットのカウンタ値の最下位ビットから最上位ビットへ向かう方向において第m(mは1≦m≦Mを満たす整数)位のビット値を出力する分周器は、クロック信号を2m-1回に分周した信号を出力する、請求項3または請求項8に記載の連想メモリ。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2012183975thum.jpg
State of application right Registered
Reference ( R and D project ) (In Japanese)小出哲士のホームページ


PAGE TOP

close
close
close
close
close
close
close