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

連想メモリ

国内特許コード P130009371
整理番号 11012
掲載日 2013年6月14日
出願番号 特願2011-243733
公開番号 特開2013-101729
登録番号 特許第5800422号
出願日 平成23年11月7日(2011.11.7)
公開日 平成25年5月23日(2013.5.23)
登録日 平成27年9月4日(2015.9.4)
発明者
  • 小出 哲士
  • マタウシュ ハンスユルゲン
  • 安田 雅浩
  • 佐々木 静龍
出願人
  • 国立大学法人広島大学
発明の名称 連想メモリ
発明の概要 【課題】誤検索を抑制可能な連想メモリを提供する。
【解決手段】連想メモリは、R個の距離/時間変換回路DT~DTを備える。R個の距離/時間変換回路DT~DTの各々は、NAND回路40と、Nビットステージ41~4kとを含む。Nビットステージ41~4kは、それぞれ、参照データと検索データとの間の距離が大きいほど、より長い遅延時間によってNAND回路40からの信号を遅延して発振信号を発振し、参照データと検索データとの間の距離が小さいほど、より短い遅延時間によってNAND回路40からの信号を遅延して発振信号を発振する。そして、距離/時間変換回路DT~DTから出力されたR個の発振信号のうち、最も早く変化する発振信号がWinner行の発振信号として検出される。
【選択図】図2
従来技術、競合技術の概要


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



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



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



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

産業上の利用分野


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

特許請求の範囲 【請求項1】
各々がW(Wは以上の整数)ビットのビット長を有するR(Rは2以上の整数)個の参照データを保存する参照データ保存回路と、
Wビットのビット長を有し、かつ、検索対象である検索データを前記R個の参照データの各々とビット毎に比較し、各々が前記検索データと前記参照データとの間の距離を表し、かつ、Wビットのビット値からなるR個の距離信号を前記検索データと前記R個の参照データとの比較結果として出力する比較回路と、
前記R個の距離信号に対応して設けられ、各々がk(kは、W/Nまたは(W/N)+1を満たす整数、Nは、3以上の整数)個の遅延回路をリング状に接続した発振回路を含むR個の変換回路と、
前記R個の距離信号および前記R個の変換回路に対応して設けられ、各々がk個の経路選択回路を含むR個の選択回路と、
前記R個の変換回路から出力されたR個の出力信号のうち、最も早く変化する出力信号を検出し、その検出した出力信号を前記検索データに最も類似した参照データを示す信号として出力する検出回路とを備え、
前記R個の選択回路の各々は、対応するWビットの距離信号によって表される距離が小さいほど前記k個の遅延回路における遅延時間が短くなり、かつ、前記対応するWビットの距離信号によって表される距離が大きいほど前記k個の遅延回路における遅延時間が長くなるように前記k個の遅延回路の各々におけるN+1個の遅延経路から1つの遅延経路を選択するためのk個の選択信号を前記対応するWビットの距離信号に基づいて生成し、その生成したk個の選択信号を前記対応する変換回路へ出力し、
前記R個の変換回路の各々は、前記対応する選択回路から前記k個の選択信号を受けると、その受けたk個の選択信号によって選択されたk個の遅延経路を介して発振し、その発振した発振信号を出力信号として前記検出回路へ出力
前記k個の遅延回路の各々は、
入力ノードと、
出力ノードと、
前記入力ノードと前記出力ノードとの間に接続された第1のゲートからなる第1の遅延経路と、
各々が、前記入力ノード側に配置された第2のゲートと、前記出力ノードに接続された第3のゲートと、前記第2のゲートと前記第3のゲートとの間に接続された遅延器とからなるN個の遅延経路とを含み、
前記N個の遅延経路のうち、前記第1の遅延経路に隣接する第2の遅延経路の前記第2のゲートは、前記入力ノードに接続され、
前記N個の遅延経路のうち、前記第2の遅延経路以外のN-1個の遅延経路に含まれるN-1個の前記第2のゲートは、それぞれ、前記第1の遅延経路側で隣接する遅延経路に含まれる前記遅延器の出力側に接続され、
前記第1のゲート、前記N個の第2のゲートおよび前記N個の第3のゲートは、前記Nビットの距離信号によって表される距離がd(d=0,1,2,・・・,N)であるとき前記入力ノードからd個の前記遅延器を介して前記出力ノードへ信号が出力されるように前記選択信号によって開閉され、
前記k個の経路選択回路の各々は、
直列に接続されたN-1個の第1の選択信号生成回路と、
前記N-1個の第1の選択信号生成回路のうち、入力側からN-1番目の第1の選択信号生成回路から出力されたN個の出力信号に基づいて、前記第1の遅延経路から最も離れた位置に配置された第N+1番目の遅延経路に含まれる前記第3のゲートと前記第1のゲートとを除いたN-1個の前記第3のゲートを開閉するN-1個の第1の選択信号と、前記N個の第2のゲートを開閉するN個の第2の選択信号とを生成する第2の選択信号生成回路とを含み、
前記N-1個の第1の選択信号生成回路は、
前記Wビットの距離信号のうちの第1および第2番目のビット値に基づいて2個の選択信号を生成する第1の信号生成回路と、
各々が、m(mは2≦m≦N-1を満たす整数)個の選択信号と、前記Wビットの距離信号のうちの第n(nは3≦n≦Nを満たす整数)番目のビット値とに基づいてm+1個の選択信号を生成するN-2個の第2の信号生成回路とを含み、
前記N-2個の第2の信号生成回路の各々は、前記第1の信号生成回路、または前記第1の信号生成回路側の第2の信号生成回路から前記m個の選択信号を受け、
前記第2の選択信号生成回路は、前記N-1個の第1の選択信号を前記N-1個の第3のゲートへ出力し、前記N個の第2の選択信号を前記N個の第2のゲートへ出力し、前記第2の遅延経路に含まれる前記第2のゲートへ出力する前記第2の選択信号の反転信号を前記第1のゲートへ出力し、前記第N+1番目の遅延経路に含まれる前記第2のゲートへ出力する前記第2の選択信号と同じ選択信号を前記第N+1番目の遅延経路に含まれる前記第3のゲートへ出力する、連想メモリ。

【請求項2】
前記R個の変換回路から出力されたR個の出力信号を分周し、その分周したR個の出力信号を前記検出回路へ出力する分周器をさらに備える、請求項1に記載の連想メモリ。

【請求項3】
前記k個の経路選択回路は、前記k個の遅延回路に対応して設けられ、
前記k個の経路選択回路の各々は、前記k個の経路選択回路が含まれる選択回路へ出力されるWビットの距離信号のうち、Nビットの距離信号を受け、その受けたNビットの距離信号によって表される距離が小さいほど遅延時間が短くなり、かつ、前記受けたNビットの距離信号によって表される距離が大きいほど遅延時間が長くなるように前記N+1個の遅延経路から1つの遅延経路を選択するための選択信号を生成し、その生成した選択信号を前記対応する遅延回路へ出力し、
前記k個の遅延回路の各々は、前記N+1個の遅延経路を含み、前記対応する経路選択回路から前記選択信号を受けると、その受けた選択信号によって選択された前記1つの遅延経路によって信号を遅延して出力する、請求項1または請求項2に記載の連想メモリ。

【請求項4】
K(Kは2以上の整数)ビットのビット長を有する参照データを列方向にW(Wは2以上の整数)個配列し、かつ、行方向にR(Rは2以上の整数)個配列してW×R個の参照データを保存する参照データ保存回路と、
Kビットのビット長を有し、かつ、検索対象である検索データを前記W×R個の参照データの各々とビット毎に比較し、各々が前記検索データと前記参照データとの間の距離を表し、かつ、各々がKビットのビット値からなるW×R個の距離信号を前記検索データと前記W×R個の参照データとの比較結果として出力する比較回路と、
各々が前記列方向に配列されたW個の参照データと前記検索データとの比較結果を示すR個の距離信号に対応して設けられたR個の変換回路と、
前記R個の距離信号および前記R個の変換回路に対応して設けられたR個の選択回路と、
前記R個の変換回路から出力されたR個の出力信号のうち、最も早く変化する出力信号を検出し、その検出した出力信号を前記検索データに最も類似した参照データを示す信号として出力する検出回路とを備え、
前記R個の選択回路の各々は、前記R個の距離信号のうち、対応する距離信号のW×K個のビット値に基づいて、前記参照データと前記検索データとの同位ビット同士が異なるとき第1の遅延時間を有する第1の遅延経路を選択し、前記同位ビット同士が一致するとき前記第1の遅延時間よりも短い第2の遅延時間を有する第2の遅延経路を選択するための選択信号を生成し、
前記R個の変換回路の各々は、前記対応する選択回路から受けた選択信号によって選択された前記第1の遅延経路または前記第2の遅延経路を用いて、前記参照データと前記検索データとの最上位ビット同士の距離を示す第1の距離信号から前記参照データと前記検索データとの最下位ビット同士の距離を示す第2の距離信号に向かって遅延時間が順次短くなり、かつ、周波数が順次高くなるように前記第1の距離信号から前記第2の距離信号に向かって前記距離信号を発振信号に順次変換し、その変換した発振信号を出力信号として前記検出回路へ出力する、連想メモリ。

【請求項5】
前記R個の変換回路の各々は、
各々がリング状に接続されたW個の遅延回路を含み、前記参照データおよび前記検索データのK個のビット位に対応して配置されたK個の発振回路と、
各々が隣接する2つの発振回路間に配置され、前記K個の発振回路を直列に接続するK-1個の選択器と、
前記直列に接続されたK個の発振回路のうちの一方端の発振回路と他方端の発振回路との間に配置され、当該変換回路を活性化するための活性化信号を前記一方端の発振回路へ出力する活性化回路と
前記直列に接続されたK個の発振回路のうちの前記他方端の発振回路と前記活性化回路との間に配置されたK個目の選択器とを含み、
前記K-1の選択器の各々は、前記2つの発振回路のうちの一方の発振回路の出力信号を入力信号として前記一方の発振回路へ出力するとともに、前記一方の発振回路への出力回数が所望回数に達すると、前記一方の発振回路の出力信号を前記2つの発振回路のうちの他方の発振回路へ出力し、
前記K個目の選択器は、前記他方端の発振回路の出力信号を入力信号として前記他方端の発振回路へ出力するとともに、前記他方端の発振回路への出力回数が所望回数に達すると、前記他方端の発振回路の出力信号を前記活性化回路へ出力し、
前記W個の遅延回路の各々は、前記第1および第2の遅延経路を有し、前記選択信号によって選択された前記第1または第2の遅延経路を用いて入力信号を遅延して隣接する遅延回路へ出力し、
前記K個の発振回路は、前記一方端の発振回路から前記他方端の発振回路へ向かうに従って前記第1の遅延経路における前記第1の遅延時間が順次短くなっており、
前記R個の選択回路の各々は、前記W×K個のビット値に基づいて、前記W個の参照データと前記検索データとの同位ビット同士の比較結果を示すWビットの距離信号をK個生成し、その生成したK個のWビットの距離信号に基づいて、各々が前記Wビットの距離信号によって表される距離が大きいほど遅延時間が長くなり、かつ、前記Wビットの距離信号によって表される距離が小さいほど遅延時間が短くなるように前記第1または第2の遅延経路を選択するためのK個の選択信号を生成し、各選択信号が各ビット位に対応して配置された発振回路へ出力されるように前記生成したK個の選択信号をそれぞれ前記K個の発振回路へ出力する、請求項に記載の連想メモリ。

【請求項6】
前記R個の変換回路の各々は、
各々がリング状に接続されたW個の遅延回路を含み、前記参照データおよび前記検索データのK個のビット位に対応して配置されたK個の発振回路と、
各々が隣接する2つの発振回路間に配置され、前記K個の発振回路を直列に接続するK-1個の分周器と、
前記直列に接続されたK個の発振回路のうちの一方端の発振回路と他方端の発振回路との間に配置され、当該変換回路を活性化するための活性化信号を前記一方端の発振回路へ出力する活性化回路とを含み、
前記K-1の分周器の各々は、前記2つの発振回路のうちの一方の発振回路の出力信号を分周して前記一方の発振回路へ出力するとともに、分周回数が所望回数に達すると、分周後の信号を前記2つの発振回路のうちの他方の発振回路へ出力し、
前記W個の遅延回路の各々は、前記第1および第2の遅延経路を有し、前記選択信号によって選択された前記第1または第2の遅延経路を用いて入力信号を遅延して隣接する遅延回路へ出力し、
前記W個の遅延回路に含まれるW個の前記第1の遅延経路におけるW個の前記第1の遅延時間は、相互に同じであり、
前記K-1個の分周器は、前記一方端の発振回路の出力信号を受ける分周器から前記他方端の発振回路へ信号を出力する分周器に向かうに従って分周回数が減少し、
前記R個の選択回路の各々は、前記W×K個のビット値に基づいて、前記W個の参照データと前記検索データとの同位ビット同士の比較結果を示すWビットの距離信号をK個生成し、その生成したK個のWビットの距離信号に基づいて、各々が前記Wビットの距離信号によって表される距離が大きいほど遅延時間が長くなり、かつ、前記Wビットの距離信号によって表される距離が小さいほど遅延時間が短くなるように前記第1または第2の遅延経路を選択するためのK個の選択信号を生成し、各選択信号が各ビット位に対応して配置された発振回路へ出力されるように前記生成したK個の選択信号をそれぞれ前記K個の発振回路へ出力する、請求項に記載の連想メモリ。

【請求項7】
前記R個の変換回路の各々は、
各々が前記第1および第2の遅延経路を有し、リング状に接続されたW個の遅延回路を含む第1の発振回路と、
各々が前記第1および第2の遅延経路を有し、リング状に接続されたW個の遅延回路を含む第2の発振回路と、
前記第1の発振回路の出力信号を所望回数だけ分周し、その分周した信号を前記第2の発振回路へ出力する第1の分周器と、
前記第2の発振回路の出力信号を所望回数だけ分周し、その分周した信号を前記第1の発振回路へ出力する第2の分周器と、
前記第2の分周器と前記第1の発振回路との間に配置され、当該変換回路を活性化するための活性化信号を前記第1の発振回路へ出力する活性化回路とを含み、
前記第1の分周器は、前記参照データと前記検索データとの最上位ビットから奇数番目のビット同士の比較結果を示す第1の距離信号を変換した発振信号を前記第1の発振回路から受け、前記第1の距離信号がより下位のビット同士の比較結果を示すほど少ない回数だけ前記受けた発振信号を分周して前記第2の発振回路へ出力し、
前記第2の分周器は、前記参照データと前記検索データとの最上位ビットから偶数番目のビット同士の比較結果を示す第2の距離信号を変換した発振信号を前記第2の発振回路から受け、前記第2の距離信号がより下位のビット同士の比較結果を示すほど少ない回数だけ前記受けた発振信号を分周して前記第1の発振回路へ出力し、
前記R個の選択回路の各々は、前記W×K個のビット値に基づいて、前記W個の参照データと前記検索データとの同位ビット同士の比較結果を示すWビットの距離信号をK個生成し、その生成したK個のWビットの距離信号に基づいて、各々が前記Wビットの距離信号によって表される距離が大きいほど遅延時間が長くなり、かつ、前記Wビットの距離信号によって表される距離が小さいほど遅延時間が短くなるように前記第1または第2の遅延経路を選択するためのK個の選択信号を生成し、前記第1の距離信号に基づいて生成された選択信号が前記第1の発振回路へ出力され、前記第2の距離信号に基づいて生成された選択信号が前記第2の発振回路へ出力されるように前記K個の選択信号を交互に前記第1および第2の発振回路へ出力する、請求項に記載の連想メモリ。
産業区分
  • 記憶装置
国際特許分類(IPC)
画像

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

JP2011243733thum.jpg
出願権利状態 登録


PAGE TOP

close
close
close
close
close
close
close