TOP > 国内特許検索 > 再構成可能連想メモリ > 明細書

明細書 :再構成可能連想メモリ

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2015-162257 (P2015-162257A)
公開日 平成27年9月7日(2015.9.7)
発明の名称または考案の名称 再構成可能連想メモリ
国際特許分類 G11C  15/04        (2006.01)
FI G11C 15/04 631W
請求項の数または発明の数 5
出願形態 OL
全頁数 17
出願番号 特願2014-036698 (P2014-036698)
出願日 平成26年2月27日(2014.2.27)
発明者または考案者 【氏名】マタウシュ ハンスユルゲン
【氏名】赤澤 智信
出願人 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
個別代理人の代理人 【識別番号】110001427、【氏名又は名称】特許業務法人前田特許事務所
審査請求 未請求
要約 【課題】参照データの次元数および個数の拡縮が可能な連想メモリを提供する。
【解決手段】再構成可能連想メモリ(100)は、それぞれが、参照データ保存回路(SC)と、距離計算回路(DP)と、距離/クロック数変換回路(DC)とを有する、複数のエレメント回路(30)と、複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力されるマッチ信号を次段のエレメント回路にトリガー信号として供給するか否かを制御する、複数のスイッチ回路(50)とを備える。スイッチ回路でカスケード接続された複数のエレメント回路によって、個別の参照データを保存し、当該参照データと検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する個別の参照データ検索回路(40)が構成される。
【選択図】図8
特許請求の範囲 【請求項1】
それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離/クロック数変換回路とを有する、複数のエレメント回路と、
前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路とを備え、
前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する個別の参照データ検索回路が構成される
ことを特徴とする再構成可能連想メモリ。
【請求項2】
複数の前記スイッチ回路がカスケード接続されており、
前記カスケード接続された複数の前記スイッチ回路によって、複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号の論理和を演算する論理和演算回路、および複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号を保存するシフトレジスタが構成される
ことを特徴とする請求項1に記載の再構成可能連想メモリ。
【請求項3】
前記シフトレジスタのシフト出力を参照して前記シフトレジスタに保存されている前記マッチ信号の出力元の参照データ検索回路を特定し、当該特定した参照データ検索回路を識別する信号を出力するWinner検出回路を備えている
ことを特徴とする請求項2に記載の再構成可能連想メモリ。
【請求項4】
回路構成情報を記憶し、当該回路構成情報に基づいて前記複数のスイッチ回路のそれぞれに前記回路構成信号を出力する回路構成情報記憶回路を備えている
ことを特徴とする請求項1ないし請求項3のいずれかに記載の再構成可能連想メモリ。
【請求項5】
前記回路構成情報記憶回路が不揮発性メモリで構成されている
ことを特徴とする請求項4に記載の再構成可能連想メモリ。
発明の詳細な説明 【技術分野】
【0001】
本発明は、連想メモリに関し、特に、連想メモリに保存される参照データの次元数および個数を拡縮する技術に関する。
【背景技術】
【0002】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI(Large Scale Integrated Circuit)上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【0003】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【0004】
前者は、CAM(Content Addressable Memory)と呼ばれ、ネットワークルータのIPアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ(Associative Memory)と呼ぶ。
【0005】
連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている(非特許文献1参照)。
【先行技術文献】
【0006】

【非特許文献1】S.Sasaki et al., "Digital Associative Memory for Word-Parallel Manhattan-Distance-Based Vector Quantization," ESSCIRC'2012, 2012, pp.185-188
【発明の概要】
【発明が解決しようとする課題】
【0007】
本願発明者は、これまでに、検索に係るクロックカウント数を削減する機構(有効ビット設定部)とユークリッド距離検索のための二乗計算回路(距離演算回路)とを備えたクロックカウント式の連想メモリを発明し、特願2013-025465において開示した。これにより、データ規模が増大しても高速な検索が可能なユークリッド/マンハッタン距離検索連想メモリをエラーフリー、高電力効率に実現した。
【0008】
連想メモリが利用される分野として、コードブックベース画像圧縮のデータ検索やBoW(Bag of Words)などが挙げられる。前者では比較的少ない次元数の大量の参照データの検索が行われ、後者では膨大な次元数の少量の参照データの検索が行われる。しかし、従来の連想メモリでは回路構成が固定されているため、アプリケーションに応じて参照データの次元数および個数を拡縮することが困難である。
【0009】
上記問題に鑑み、本発明は、参照データの次元数および個数の拡縮が可能な連想メモリを提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明の一局面に従った再構成可能連想メモリは、それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離/クロック数変換回路とを有する、複数のエレメント回路と、前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路とを備え、前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する個別の参照データ検索回路が構成されるものである。
【0011】
これによると、複数のスイッチ回路のそれぞれを適宜制御することにより、エレメント回路の接続形態を任意に変更して、任意の次元数の参照データを保存する任意の個数の参照データ検索回路を構成することができる。
【0012】
複数の前記スイッチ回路がカスケード接続されていてもよく、前記カスケード接続された複数の前記スイッチ回路によって、複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号の論理和を演算する論理和演算回路、および複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号を保存するシフトレジスタが構成されてもよい。
【0013】
これによると、各エレメント回路から出力されるマッチ信号をまとめて信号本数を減らすことができる。
【0014】
さらに、上記の再構成可能連想メモリは、前記シフトレジスタのシフト出力を参照して前記シフトレジスタに保存されている前記マッチ信号の出力元の参照データ検索回路を特定し、当該特定した参照データ検索回路を識別する信号を出力するWinner検出回路を備えていてもよい。
【0015】
また、上記の再構成可能連想メモリは、回路構成情報を記憶し、当該回路構成情報に基づいて前記複数のスイッチ回路のそれぞれに前記回路構成信号を出力する回路構成情報記憶回路を備えていてもよい。
【0016】
これによると、回路構成情報記録回路の記憶内容を書き換えるだけで、再構成可能連想メモリを任意に再構成することができる。
【0017】
なお、前記回路構成情報記憶回路は、例えば、不揮発性メモリで構成することができる。
【発明の効果】
【0018】
本発明によると、連想メモリにおいて参照データの次元数および個数を拡縮することができる。これにより、アプリケーションに応じて再構成可能連想メモリを最適に再構成して、再構成可能連想メモリに割り当てられたリソースを最大限利用することができる。
【図面の簡単な説明】
【0019】
【図1】一例に係るクロックカウント式連想メモリの概略構成図
【図2】一例に係る距離/クロック数変換回路の概略構成図
【図3】一例に係るカウンタ一致検出回路の概略構成図
【図4】Winner検出回路の動作を説明するための図
【図5】本発明に係る再構成可能連想メモリのある再構成例を示す図
【図6】本発明に係る再構成可能連想メモリの別の再構成例を示す図
【図7】本発明に係る再構成可能連想メモリのさらに別の再構成例を示す図
【図8】本発明の一実施形態に係る再構成可能連想メモリのメモリアレイ部の概略構成図
【図9】一例に係るスイッチ回路の回路構成図
【図10】本発明の一実施形態に係る再構成可能連想メモリにおけるWinner検出回路およびその入力部分の一構成例を示す図
【発明を実施するための形態】
【0020】
以下、図面を参照しながら本発明を実施するための形態について説明する。なお、本発明は、以下の実施形態に限定されるものではない。

【0021】
≪クロックカウント式連想メモリの基本構成例≫
まず、本発明に係る再構成可能連想メモリの前提となるクロックカウント式連想メモリの基本構成について説明する。

【0022】
図1は、一例に係るクロックカウント式連想メモリの概略構成を示す。一例に係るクロックカウント式連想メモリは、メモリアレイ部10と、Winner検出回路20とを備える。

【0023】
メモリアレイ部10は、メモリ部11、行デコーダ12、列デコーダ13、読出/書込回路14、および検索データ保存回路15を含む。

【0024】
メモリ部11は、参照データ保存回路(Storage Cell:SC)SC11~SC1W,SC21~SC2W,…,SCR1~SCRWと、距離演算回路(絶対値差演算回路)(Distance Processor:DP)DP11~DP1W,DP21~DP2W,…,DPR1~DPRWと、距離/クロック数変換回路DC~DCとを含む。なお、WおよびRは、それぞれ、2以上の整数である。

【0025】
距離演算回路DP11~DP1Wは、それぞれ、参照データ保存回路SC11~SC1Wに対応して設けられる。また、距離演算回路DP21~DP2Wは、それぞれ、参照データ保存回路SC21~SC2Wに対応して設けられる。以下、同様にして、距離演算回路DPR1~DPRWは、それぞれ、参照データ保存回路SCR1~SCRWに対応して設けられる。

【0026】
距離/クロック数変換回路DCは、距離演算回路DP11~DP1Wに対応して設けられる。距離/クロック数変換回路DCは、距離演算回路DP21~DP2Wに対応して設けられる。以下、同様にして、距離/クロック数変換回路DCは、距離演算回路DPR1~DPRWに対応して設けられる。

【0027】
参照データ保存回路SC11~SC1W,SC21~SC2W,…,SCR1~SCRWは、行デコーダ12、列デコーダ13、および読出/書込回路14によって書き込まれた参照データを保存する。この場合、参照データ保存回路SC11~SC1Wは、M×W(Mは1以上の整数)ビットの参照データ1を保存し、参照データ保存回路SC21~SC2Wは、M×Wビットの参照データ2を保存し、以下、同様にして、参照データ保存回路SCR1~SCRWは、M×Wビットの参照データRを保存する。つまり、参照データ保存回路SC11~SC1W,SC21~SC2W,…,SCR1~SCRWのそれぞれは、参照データのM×Wビットを保存する。

【0028】
距離演算回路DP11~DP1Wは、参照データ保存回路SC11~SC1Wに保存されたM×Wビットの参照データ1と、検索データ保存回路15に保存されたM×Wビットの検索データとの距離を後述する方法によって演算する。また、距離演算回路DP21~DP2Wは、参照データ保存回路SC21~SC2Wに保存されたM×Wビットの参照データ2と、検索データ保存回路15に保存されたM×Wビットの検索データとの距離を後述する方法によって演算する。以下、同様にして、距離演算回路DPR1~DPRWは、参照データ保存回路SCR1~SCRWに保存されたM×Wビットの参照データRと、検索データ保存回路15に保存されたM×Wビットの検索データとの距離を後述する方法によって演算する。そして、距離演算回路DP11~DP1W、距離演算回路DP21~DP2W、…、距離演算回路DPR1~DPRWにおける参照データと検索データとの距離の演算は、並列に行われる。

【0029】
そして、距離演算回路DP11~DP1Wは、参照データ1と検索データとの距離をM×Wビットの距離信号として距離/クロック数変換回路DCへ出力する。距離演算回路DP21~DP2Wは、参照データ2と検索データとの距離をM×Wビットの距離信号として距離/クロック数変換回路DCへ出力する。以下、同様にして、距離演算回路DPR1~DPRWは、参照データRと検索データとの距離をM×Wビットの距離信号として距離/クロック数変換回路DCへ出力する。

【0030】
距離演算回路DP11~DP1Wのそれぞれは、参照データ1と検索データとの距離を次式を用いて演算する。

【0031】
【数1】
JP2015162257A_000003t.gif

【0032】
式(1)において、Drj(r=1~R,j=1~W)は、参照データと検索データとの距離(絶対値差)を表す。nMrは、参照データと検索データとのマンハッタン距離を示している。また、式(1)において、Injは、検索データであり、Rerjは、参照データである。各データInj、Rerjは、それぞれ、Mビットからなる。

【0033】
このように、距離演算回路DP11~DP1Wは、M×Wビットの参照データ1と、M×Wビットの検索データとの距離をMビットずつ演算し、それぞれがMビットのビット長を有するW個の距離信号D1jを距離/クロック数変換回路DCへ出力する。

【0034】
距離演算回路DP21~DP2W、…および距離演算回路DPR1~DPRWも、同様にして、それぞれ、式(1)を用いて参照データ2~Rと検索データとの距離を演算する。そして、距離演算回路DP21~DP2W、…および距離演算回路DPR1~DPRWも、それぞれがMビットのビット長を有するW個の距離信号D2j~DRjをそれぞれ距離/クロック数変換回路DC~DCへ出力する。

【0035】
距離/クロック数変換回路DCは、距離演算回路DP11~DP1WからW個の距離信号D1jを受け、各距離信号D1jの二乗値の和に相当するクロック信号CLKのクロック数CN_total1を後述する方法によってカウントする。そして、そのクロック数CN_total1をカウントしたタイミングを示すマッチ信号Mを出力する。

【0036】
距離/クロック数変換回路DCは、距離演算回路DP21~DP2WからW個の距離信号D2jを受け、各距離信号D2jの二乗値の和に相当するクロック信号CLKのクロック数CN_total2を後述する方法によってカウントする。そして、そのクロック数CN_total2をカウントしたタイミングを示すマッチ信号Mを出力する。

【0037】
以下、同様にして、距離/クロック数変換回路DCは、距離演算回路DPR1~DPRWからW個の距離信号DRjを受け、各距離信号DRjの二乗値の和に相当するクロック信号CLKのクロック数CN_totalRを後述する方法によってカウントする。そして、そのクロック数CN_totalRをカウントしたタイミングを示すマッチ信号Mを出力する。

【0038】
行デコーダ12は、メモリ部11の行方向のアドレスを指定する。列デコーダ13は、メモリ部11の列方向のアドレスを指定する。読出/書込回路14は、参照データを行デコーダ12および列デコーダ13によって指定された参照データ保存回路SC11~SC1W,SC21~SC2W,…,SCR1~SCRWに書き込むとともに、検索データを検索データ保存回路15に書き込む。

【0039】
検索データ保存回路15は、読出/書込回路14によって書き込まれた検索データ(M×Wビットのデータ)を保存する。

【0040】
Winner検出回路20は、マッチ信号M~Mをそれぞれ距離/クロック数変換回路DC~DCから受ける。そして、その受けたマッチ信号M~Mのうち、一致タイミングが早い順にk(kは1≦k<Rを満たす整数)個のマッチ信号を検出する。

【0041】
図2は、一例に係る距離/クロック数変換回路DCの概略構成を示す。なお、距離/クロック数変換回路DC~DCのそれぞれも、図2に示す距離/クロック数変換回路DCと同様の構成を有する。距離/クロック数変換回路DCは、バッファ121~12Wと、カウンタ一致検出回路131~13Wとを含む。

【0042】
バッファ121は、クロックカウント式連想メモリの制御回路(図示せず)から検索開始信号SBを受け、クロックカウント式連想メモリに内蔵されたクロック発生回路(図示せず)からクロック信号CLKを受ける。そして、バッファ121は、検索開始信号SBがLレベルからHレベルに遷移すると、その受けたクロック信号CLKをバッファ122およびカウンタ一致検出回路131へ出力する。バッファ122は、クロック信号CLKをバッファ121から受け、カウンタ一致検出回路131から、後述するHレベルの一致信号(DETECT1)を受けると、クロック信号CLKをバッファ123(図示せず)およびカウンタ一致検出回路132へ出力する。以下、同様にして、バッファ12Wは、クロック信号CLKをバッファ12W-1(図示せず)から受け、カウンタ一致検出回路13W-1(図示せず)から、後述するHレベルの一致信号(DETECTW-1)を受けると、クロック信号CLKをカウンタ一致検出回路13Wへ出力する。

【0043】
カウンタ一致検出回路131~13Wは、それぞれ、距離演算回路DP11~DP1Wに対応して設けられる。そして、カウンタ一致検出回路131~13Wは、直列に接続される。ここで、カウンタ一致検出回路131~13Wの概略構成について説明する。

【0044】
図3は、一例に係るカウンタ一致検出回路131~13Wの概略構成を示す。本例は、W=2の場合を示している。カウンタ一致検出回路131は、クロック数変換回路131aと、カウンタ131bと、一致検出回路131cとを含む。カウンタ一致検出回路132は、クロック数変換回路132aと、カウンタ132bと、一致検出回路132cとを含む。以下、各構成の機能について説明する。

【0045】
クロック数変換回路131aは、距離演算回路DP11からMビットのビット長を有する距離信号D11と、バッファ121からのクロック信号CLKとを受ける。クロック数変換回路131aは、クロック信号CLKのクロック数をカウントし、距離信号D11が示す距離と一致するクロック数を検出したタイミングで、カウンタ131bにHレベルの一致検出信号を出力する処理を行う。クロック数変換回路131aは、後述の一致検出回路131cからHレベルの一致信号(DETECT1)が出力されるまで、この処理を繰り返し行い、Hレベルの一致信号(DETECT1)が出力されると動作を停止する。

【0046】
カウンタ131bは、クロック数変換回路131aからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウント値を一致検出回路131cへ出力する。

【0047】
一致検出回路131cは、カウンタ131bからカウンタ値を受け、距離演算回路DP11からMビットのビット長を有する距離信号D11を受ける。一致検出回路131cは、距離信号D11が示す距離とカウンタ値とを比較し、距離信号D11が示す距離とカウンタ値とが一致するときに、Hレベルの一致信号(DETECT1)をクロック数変換回路131aとバッファ122へ出力する。一致検出回路131cは、距離信号D11が示す距離とカウンタ値とが一致しないときは、Lレベルの一致信号(DETECT1)をクロック数変換回路131aとバッファ122へ出力する。

【0048】
クロック数変換回路132aは、バッファ122からクロック信号CLKを受けると駆動する。クロック数変換回路132aは、距離演算回路DP12からMビットのビット長を有する距離信号D12を受ける。クロック数変換回路131aと同様、クロック数変換回路132aは、クロック信号CLKのクロック数をカウントし、距離信号D12が示す距離と一致するクロック数を検出したタイミングで、カウンタ132bにHレベルの一致検出信号を出力する処理を行う。クロック数変換回路132aは、後述の一致検出回路132cからHレベルの一致信号(DETECT2)が出力されるまで、この処理を繰り返し行う。クロック数変換回路132aは、Hレベルの一致信号(DETECT2)が出力されると動作を停止する。

【0049】
カウンタ132bは、クロック数変換回路132aからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウント値を一致検出回路132cへ出力する。

【0050】
一致検出回路132cは、カウンタ132bからカウンタ値を受け、距離演算回路DP12からMビットのビット長を有する距離信号D12を受ける。一致検出回路132cは、距離信号D12が示す距離とカウンタ値とを比較し、距離信号D12が示す距離とカウンタ値とが一致するときに、Hレベルの一致信号(DETECT2)をクロック数変換回路132aとバッファ122へ出力するとともに、Hレベルの一致信号(DETECT2)をマッチ信号MとしてWinner検出回路20へ出力する。また、一致検出回路132cは、距離信号D12が示す距離とカウンタ値とが一致しないときは、Lレベルの一致信号(DETECT2)をクロック数変換回路132aに出力する。

【0051】
ここで、例えば、距離演算回路DP11から距離「2」を示すMビットの距離信号D11が出力され、距離演算回路DP12から距離「3」を示すMビットの距離信号D12が出力された場合の動作例について説明する。

【0052】
クロック数変換回路131aは、距離「2」を示すMビットの距離信号D11を受け、バッファ121からのクロック信号CLKのクロックに同期して、距離「2」に一致するクロック数をカウントする。クロック数変換回路131aは、カウントしたクロック数と距離とが一致すると、Hレベルの一致検出信号を出力する。カウンタ131bは、一致検出信号が立ち上がると、カウント値をカウントアップし、「1」を示すカウンタ値を一致検出回路131cに出力する。このとき、距離信号D11が示す距離「2」とカウント値「1」とが一致しないため、一致検出回路131cからLレベルの一致信号(DETECT1)が出力される。

【0053】
クロック数変換回路131aは、出力した一致検出信号がLレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路131aは、再びクロック信号CLKのクロック数をカウントし、カウントしたクロック数が距離「2」と一致すると、カウンタ131bにHレベルの一致検出信号を出力する。カウンタ131bは、一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路131cに「2」を示すカウンタ値を出力する。一致検出回路131cは、距離信号D11が示す距離「2」とカウンタ値「2」とが一致するため、一致信号(DETECT1)をバッファ122とクロック数変換回路131aに出力する。つまり、検索開始からのクロック数が「4」となるタイミングで、Hレベルの一致信号(DETECT1)が出力される。そして、クロック数変換回路131aは、Hレベルの一致信号(DETECT1)に応じて動作を停止する。

【0054】
バッファ122は、一致検出回路131cからHレベルの一致信号(DETECT1)を受けて、クロック数変換回路132aにクロック信号CLKを出力する。クロック数変換回路132aは、バッファ122からのクロック信号CLKのクロックに同期して、クロック信号CLKのクロック数をカウントする。クロック数変換回路132aは、距離「3」を示すMビットの距離信号D12を受け、カウントしたクロック数が距離「3」と一致するタイミングで、Hレベルの一致検出信号をカウンタ132bに出力する。カウンタ132bは、クロック数変換回路132aからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路132cに「1」を示すカウンタ値を出力する。このとき、距離「3」とカウンタ値「1」とが一致しないため、一致検出回路132cからLレベルの一致信号(DETECT2)が出力される。

【0055】
クロック数変換回路132aは、出力した一致検出信号がLレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路132aは、再びクロック信号CLKのクロック数をカウントし、カウントしたクロック数が距離「3」と一致すると、カウンタ132bにHレベルの一致検出信号を出力する。カウンタ132bは、クロック数変換回路132aからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路132cに「2」を示すカウンタ値を出力する。このとき、距離「3」とカウンタ値「2」とが一致しないため、一致検出回路132cからLレベルの一致信号(DETECT2)が出力される。

【0056】
クロック数変換回路132aは、一致検出信号がLレベルになると、再びカウントしたクロック数をリセットしてクロック信号CLKをカウントし、カウントしたクロック数が距離「3」と一致すると、カウンタ132bにHレベルの一致検出信号を出力する。そして、クロック数変換回路132aは、Hレベルの一致信号(DETECT2)に応じて動作を停止する。カウンタ132bは、クロック数変換回路132aからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路132cに「3」を示すカウンタ値を出力する。一致検出回路132cは、距離「3」とカウント値「3」とが一致するため、Hレベルの一致信号(DETECT2)をクロック数変換回路132aに出力するとともに、マッチ信号MとしてWinner検出回路20に出力する。つまり、クロック数変換回路132aにおいてカウントされたクロック数は「9(=3+3+3)」であり、検索開始からクロック数「13(=4+9)」のタイミングでマッチ信号Mが出力される。

【0057】
カウンタ一致検出回路131,132全体でカウントされるクロック数CN_total1「13」は、カウンタ一致検出回路131においてカウントするクロック数「4(=2+2)」と、カウンタ一致検出回路132においてカウントするクロック数「9(=3+3+3)」とを加算したものである。つまり、カウンタ一致検出回路131,132によって、距離「2」の二乗値と距離「3」の二乗値との和に一致するクロック数をカウントすることに相当する。

【0058】
距離/クロック数変換回路DCは、一般的に、W個の距離信号D11~D1Wを受ける。そして、W個の距離信号D11~D1Wのそれぞれは、Mビットのビット長を有する。したがって、距離/クロック数変換回路DCは、M×Wビットのビット長を有する距離信号D1112…D1Wを受ける。カウンタ一致検出回路131において、距離信号D11が示す距離に一致する回数分だけ、その距離に一致するクロック数を繰り返しカウントする。また、カウンタ一致検出回路132~13Wは、それぞれ、カウンタ一致検出回路131~13W-1から一致信号を受けた後に、距離信号D12~D1Wにそれぞれ一致するクロック数を、その距離に一致する回数だけ繰り返しカウントする。その結果、距離/クロック数変換回路DCにおいてカウントされる全体のクロック数CN_total1は、カウンタ一致検出回路131~13Wのそれぞれにおいてカウントされたクロック数の和に等しい。カウンタ一致検出回路131~13Wのそれぞれにおいてカウントされたクロック数は、それぞれ、距離信号D11~D1Wが示す各距離の二乗値に相当するため、距離/クロック数変換回路DCにおいてカウントされる全体のクロック数CN_totalRは、各距離信号D11~D1Wの二乗値の和を表している。

【0059】
ここで、ユークリッド距離nErは、次式によって表される。

【0060】
【数2】
JP2015162257A_000004t.gif

【0061】
式(2)の右辺の|Inj-Rerjは、式(1)の右辺の|Inj-Rerj|において、検索データと参照データとの距離の二乗値に一致する。したがって、ユークリッド距離nErの演算は、上述したように、式(1)によって演算したW個の各距離について、距離に一致するクロック数をカウントする処理を距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図3の例において、カウンタ一致検出回路132が、カウンタ一致検出回路131,132全体でカウントしたクロック数のタイミングを示すマッチ信号Mを出力することは、ユークリッド距離nErによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示す信号を出力することに相当する。なお、距離/クロック数変換回路DC~DCのそれぞれも、距離/クロック数変換回路DCの動作と同じ動作によって、それぞれ、マッチ信号M~Mを出力する。

【0062】
次に、Winner検出回路20の動作について説明する。図4は、Winner検出回路20の動作を説明するための図である。距離/クロック数変換回路DC~DCは、図4に示すように、例えばマッチ信号M~Mをそれぞれクロック信号CLKに同期してWinner検出回路20へ出力する。

【0063】
Winner検出回路20は、マッチ信号M~Mを受け、その受けたマッチ信号M~Mの立ち上がりタイミングt~tを検出する。そして、Winner検出回路20は、タイミングt~tが早い順にk個のマッチ信号を検出する。

【0064】
≪再構成可能連想メモリの構成例≫
次に、本発明に係る再構成可能連想メモリについて説明する。本発明に係る再構成可能連想メモリは、例えば上記構成のクロックカウント式連想メモリにおいて参照データの次元数および個数を任意に拡縮できるように構成したものである。図5、図6、および図7は、本発明に係る再構成可能連想メモリのさまざまな再構成例を示す。

【0065】
再構成可能連想メモリ100におけるメモリアレイ部10において、複数のエレメント回路30がR行×C列(ただし、R,Cはいずれも2以上の整数である。)のマトリクス状に配置されている。なお、便宜のため、以下では、再構成可能連想メモリ100におけるメモリアレイ部10において4行×4列の計16個のエレメント回路30がマトリクス状に配置されているものとして説明する。また、行デコーダ2、列デコーダ3、読出/書込回路4、検索データ保存回路5などの周辺回路の図示は省略する。

【0066】
各エレメント回路30は、1組以上の上記の参照データ保存回路SCおよび距離計算回路DPの対応するペア、ならびにそれら距離計算回路DCから出力される距離信号が入力される上記の距離/クロック数変換回路DCを含む。各エレメント回路30から出力されるMN(Match Next)信号は、各エレメント回路30における距離/クロック数変換回路DCから出力されるマッチ信号に相当する。すなわち、各エレメント回路30は、Q次元(Qは2以上の整数)の参照データを保存し、当該Q次元の参照データとQ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号(MN信号)を出力する。

【0067】
後述する図示しないスイッチ回路によってエレメント回路30どうしが任意に接続および切断可能となっている。エレメント回路30どうしが接続された場合、前段のエレメント回路30から出力されるMN信号は、次段のエレメント回路30における距離/クロック数変換回路DCのトリガー信号として次段のエレメント回路30に供給される。

【0068】
図5の再構成例では、図示しないスイッチ回路によって4個のエレメント回路30がカスケード接続されて4個の参照データ検索回路40が構成されている。図5の再構成例において、4個の参照データ検索回路40は、それぞれ、4Q次元の参照データを保存し、当該4Q次元の参照データと4Q次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号(MN信号)をWinner検出回路20へ出力する。

【0069】
図6の再構成例では、図示しないスイッチ回路によって2個のエレメント回路30がカスケード接続されて8個の参照データ検索回路40が構成されている。図6の再構成例において、8個の参照データ検索回路40は、それぞれ、2Q次元の参照データを保存し、当該2Q次元の参照データと2Q次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号(MN信号)をWinner検出回路20へ出力する。すなわち、図6の再構成例は、図5の再構成例に対して、参照データの次元数を半分にする代わりに個数を倍にしたものである。

【0070】
図7の再構成例では、図示しないスイッチ回路によって8個のエレメント回路30がカスケード接続されて2個の参照データ検索回路40が構成されている。図7の再構成例において、2個の参照データ検索回路40は、それぞれ、8Q次元の参照データを保存し、当該8Q次元の参照データと8Q次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号(MN信号)をWinner検出回路20へ出力する。すなわち、図7の再構成例は、図5の再構成例に対して、参照データの個数を半分にする代わりに次元数を倍にしたものである。

【0071】
≪再構成可能連想メモリの実施形態≫
次に、本発明の一実施形態に係る再構成可能連想メモリについて説明する。図8は、本発明の一実施形態に係る再構成可能連想メモリ100のメモリアレイ部10の概略構成を示す。各エレメント回路30に対応してスイッチ回路50が設けられており、上述したように、スイッチ回路50によってエレメント回路30どうしが任意に接続および切断可能となっている。各スイッチ回路50がエレメント回路30どうしを接続するか否かは、各スイッチ回路50に入力される回路構成信号SRによって決まる。

【0072】
各スイッチ回路50に入力される回路構成信号SRは、メモリ(回路構成情報記憶回路)60に記憶されている。メモリ60は、SRAM(Static Random Access Memory)、フラッシュメモリ、EEPROM(Electrically Erasable Programmable Read-Only Memory)などの不揮発性メモリやシフトレジスタなどで構成することができる。メモリ60の記憶内容を書き換えるだけで、再構成可能連想メモリ100を任意に再構成することができる。

【0073】
原理的には、再構成可能連想メモリ100において、1個のエレメント回路30で1個の参照データ検索回路40を構成することで、参照データの個数が最大となる再構成が可能である。そのような再構成に対応可能にするためには、各エレメント回路30から出力されるMN信号をWinner検出回路20へ接続しなければならない。しかし、そのような回路構成は、エレメント回路30の個数が増えるとWinner検出回路20へ接続するMN信号の信号線もその分だけ増えるため、エレメント回路30の個数が数十個以上になると信号線のレイアウトが非常に困難になってくる。そこで、本実施形態では、メモリアレイ部10において同じ行に配置された各エレメント回路30から出力されるMN信号の論理和を演算し、その論理和であるMOR(Match OR)信号をWinner検出回路20へ入力する。これにより、Winner検出回路20に接続すべき信号線をR本(マトリクスの行数)にまで削減することができる。また、各参照データ検索回路40から出力されるMN信号がMOR信号としてまとめられると、いずれの参照データ検索回路40からMN信号が出力されたのかが判別できなくなるため、後述するように、本実施形態では、各参照データ検索回路40から出力されるMN信号を保存するシフトレジスタを構成し、そのシフトレジスタの出力であるSHM(Shift Match)信号をWinner検出回路20へ入力する。

【0074】
図9は、スイッチ回路50の回路構成例を示す。スイッチ回路50は、例えば、図9(A)、図9(B)、および図9(C)に示した3つの回路を備えている。

【0075】
図9(A)において、マルチプレクサ(MUX)51は、検索開始信号SBが入力in0として、前段のエレメント回路30から出力されるMN信号(MNin)が入力in1としてそれぞれ与えられ、回路構成信号SRによってin0およびin1のいずれか一方を選択的に出力する。MUX51から出力されるMN信号(MNout)は、次段のエレメント回路30における距離/クロック数変換回路DCのトリガー信号となる。具体的には、MUX51は、回路構成信号SRがHレベル(SR=1)のとき、in1を出力する。この場合、前段のエレメント回路30における距離/クロック数変換回路DCから出力されるマッチ信号(MN信号)が次段のエレメント回路30における距離/クロック数変換回路DCのトリガー信号として供給される。一方、MUX51は、回路構成信号SRがLレベル(SR=0)のとき、in0を出力する。この場合、次段のエレメント回路30における距離/クロック数変換回路DCに検索開始信号SBが供給される。すなわち、この場合の次段のエレメント回路30は、参照データ検索回路40における初段のエレメント回路30に相当する。

【0076】
図9(B)において、ORゲート53は、前段のスイッチ回路50から出力されるMOR信号(MORin)と前段のエレメント回路30から出力されるMN信号(MNin)が入力され、これら信号の論理和を出力する。MUX52は、ORゲート53の出力が入力in0として、前段のスイッチ回路50から出力されるMOR信号(MORin)が入力in1としてそれぞれ与えられ、回路構成信号SRによってin0およびin1のいずれか一方を選択的に出力する。MUX52から出力されるMOR信号(MORout)は、次段のスイッチ回路50またはWinner検出回路20へ供給される。また、Lレベルの回路構成信号SRが入力された複数のスイッチ回路50がカスケード接続されることで、各スイッチ回路50におけるORゲート53がカスケード接続される。そして、カスケード接続されたORゲート53によって、複数のデータ検索回路40から出力されるMN信号の論理和を演算する論理和演算回路が構成される。

【0077】
図9(C)において、MUX54は、前段のエレメント回路30から出力されるMN信号(MNin)が入力in0として、前段のスイッチ回路50から出力されるSHM信号(SHMin)が入力in1としてそれぞれ与えられ、検索終了遅延信号SEL(Search End Lag)によってin0およびin1のいずれか一方を選択的に出力する。検索終了遅延信号SELは、再構成可能連想メモリ100における検索終了時に出力される検索終了信号SE(Search End)を遅延させた信号である。MUX54から出力される信号は、Dフリップフロップ(DFF)56にデータ入力される。具体的には、MUX54は、検索終了遅延信号SELがLレベル(SEL=0)のとき、すなわち、検索終了前において、in0を出力する。この場合、前段のエレメント回路30における距離/クロック数変換回路DCから出力されるマッチ信号(MN信号)がDFF56にデータ入力される。一方、MUX54は、検索終了遅延信号SELがHレベル(SEL=1)のとき、すなわち、検索終了後において、in1を出力する。この場合、前段のスイッチ回路50から出力されるSHM信号(SHMin)がDFF56にデータ入力される。MUX55は、DFF56の出力信号が入力in0として、前段のスイッチ回路50から出力されるSHM信号(SHMin)が入力in1としてそれぞれ与えられ、回路構成信号SRによってin0およびin1のいずれか一方を選択的に出力する。MUX55から出力されるSHM信号(SHMout)は、次段のスイッチ回路50またはWinner検出回路20へ供給される。

【0078】
Lレベルの回路構成信号SRが入力された複数のスイッチ回路50がカスケード接続されることで、各スイッチ回路50におけるDFF56がカスケード接続される。そして、カスケード接続されたDFF56によって、複数のデータ検索回路40から出力されるMN信号を保存するシフトレジスタが構成される。当該シフトレジスタは、検索終了遅延信号SELがLレベルのときはデータ取得モードで、検索終了遅延信号SELがHレベルのときはデータシフトモードでそれぞれ動作する。データ取得モードでは、データ取得信号READWがクロック入力されることで、DFF56は、前段のエレメント回路30から出力されるMN信号(MNin)を保存する。データシフトモードでは、シフトクロック信号SHCLKがクロック入力されることで、DFF56は、前段のスイッチ回路50から出力されるSHM信号(SHMin)をシフトする。なお、READW信号とSHCLK信号はORゲート57によってその論理和が演算されてDFF56にクロック入力される。

【0079】
ところで、図7のようにメモリアレイ部10において行を跨いでエレメント回路をカスケード接続して参照データ検索回路40を構成する場合、メモリアレイ部10の各行の最終端に配置されたスイッチ回路50から出力されるSHM信号およびMOR信号がWinner検出回路20へ入力されないようにする必要がある。以下、それを実現する構成について説明する。

【0080】
図10は、再構成可能連想メモリ100におけるWinner検出回路20およびその入力部分の一構成例を示す。図10に示したスイッチ回路50は、メモリアレイ部10の各行の最終端に配置されたスイッチ回路50である。各スイッチ回路50から出力されるSHM信号およびMOR信号は、各スイッチ回路50に入力される回路構成信号SRによってマスクされる。具体的には、ANDゲート58は、SHM信号と回路構成信号SRの反転信号との論理積を演算し、SHM’信号としてWinner検出回路20へ供給する。また、ANDゲート59は、MOR信号と回路構成信号SRの反転信号との論理積を演算し、MOR’信号としてWinner検出回路20へ供給する。すなわち、SR=1のとき、行を跨いでエレメント回路30どうしがカスケード接続されるため、回路構成信号SRの反転信号によってスイッチ回路50から出力されるSHM信号およびMOR信号がマスクされてSHM’=0、MOR’=0となり、Winner検出回路20へSHM信号およびMOR信号が供給されない。一方、SR=0のとき、行を跨いでエレメント回路30どうしがカスケード接続されないため、回路構成信号SRの反転信号によってスイッチ回路50から出力されるSHM信号およびMOR信号がマスクされずにそのままWinner検出回路20へ供給される。

【0081】
Winner検出回路20は、メモリアレイ部10の各行に対応するSIPO(直列入力並列出力)型のシフトレジスタ21を備えている。各シフトレジスタ21は、SHM’信号を受けて、ビット幅ELNの信号Wを出力する。ELNは、メモリアレイ部10の各行に配置されたエレメント回路30の個数である。上述のシフトレジスタがデータシフトモードにあるとき、当該シフトレジスタのシフト出力がSHM’信号としてシフトレジスタ21に入力される。そして、シフトレジスタ21は、上述のシフトレジスタにおけるDFF26に保存されたMN信号がシフト入力されるまで、上述のシフトクロック信号SHCLKをカウントする。そして、そのカウント結果を多ビット信号Wとして出力する。これにより、メモリアレイ部10の各行におけるいずれの参照データ検索回路40からMN信号が出力されたのかを判別することができる。

【0082】
また、各MOR’信号は検索終了判定回路70に入力され、検索終了判定回路70は入力されたすべてのMOR’信号の論理和を演算して上述の検索終了信号SEを出力する。すなわち、参照データ検索回路40のいずれかからMN信号が出力されると、検索終了判定回路70から検索終了信号SEが出力される。検索終了判定回路70は、例えば、ORツリーとして構成することができる。

【0083】
以上のように、本実施形態によると、複数のエレメント回路30をさまざまにつなぎ替えて参照データの次元数および個数を任意に拡縮することができる。これにより、アプリケーションに応じて再構成可能連想メモリ100を最適に再構成して、再構成可能連想メモリ100に割り当てられたリソースを最大限利用することができる。
【符号の説明】
【0084】
100 再構成可能連想メモリ
20 Winner検出回路
30 エレメント回路
40 参照データ検索回路
50 スイッチ回路
53 ORゲート(論理和演算回路)
54 Dフリップフロップ(シフトレジスタ)
60 メモリ(回路構成情報記憶回路)
SC 参照データ保存回路
DP 距離計算回路
DC 距離/クロック数変換回路
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9