TOP > 国内特許検索 > 連想メモリ

連想メモリ コモンズ

国内特許コード P130008462
整理番号 12024,S2012-0663-N0
掲載日 2013年1月8日
出願番号 特願2012-183975
公開番号 特開2014-041676
登録番号 特許第5916563号
出願日 平成24年8月23日(2012.8.23)
公開日 平成26年3月6日(2014.3.6)
登録日 平成28年4月15日(2016.4.15)
発明者
  • マタウシュ ハンスユルゲン
  • 小出 哲士
  • 佐々木 静龍
  • 赤澤 智信
出願人
  • 国立大学法人広島大学
発明の名称 連想メモリ コモンズ
発明の概要 【課題】マンハッタン距離を用いた場合にも、正確、かつ、高速に類似検索を行うことが可能な連想メモリを提供する。
【解決手段】連想メモリは、各々がカウンタ一致検出回路31~3Wを含むR個の距離/クロック数変換回路DC~DCを備える。距離信号D11~D1Wの各々は、検索データと参照データとの距離を表わす。カウンタ一致検出回路31は、距離信号D11に一致するカウンタ値が得られるときのクロック数をカウントする。その後、カウンタ一致検出回路32は、距離信号D12に一致するカウンタ値が得られるときのクロック数をカウントする。以下、同様にして、カウンタ一致検出回路3Wは、カウンタ一致検出回路3W-1が距離信号D1W-1に一致するカウンタ値が得られるときのクロック数をカウントすると、距離信号D1Wに一致するカウンタ値が得られるときのクロック数をカウントする。
【選択図】図2
従来技術、競合技術の概要



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





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





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





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

産業上の利用分野



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

特許請求の範囲 【請求項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は、2(iは2以上の整数)からなり、
前記R個の距離/クロック数変換回路の各々は、W/s(sはW以下である2に等しい。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)
画像

※ 画像をクリックすると拡大します。

JP2012183975thum.jpg
出願権利状態 登録
参考情報 (研究プロジェクト等) 小出哲士のホームページ


PAGE TOP

close
close
close
close
close
close
close