(57)【要約】【課題】連想メモリで取り扱い可能なデータ次元数を拡張する。【解決手段】連想メモリ100は、E*M次元の検索データをM次元ずつE回に分けて保存する検索データ保存回路5と、R個のE*M次元の参照データをR個のM次元ずつE回に分けて保存する参照データ保存回路SCと、検索データ保存回路および参照データ保存回路に新たなデータが保存されるたびに検索データと参照データとの各次元の部分距離を計算する距離計算回路DCと、検索データ保存回路および参照データ保存回路に新たなデータが保存されるたびに各次元の部分距離を累積加算する次元数拡張回路DECと、検索データおよび参照データがそれぞれE回に分けて各データ保存回路に保存された後に、累積加算された部分距離を合計してE*M次元の検索データとE*M次元の参照データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号を出力する距離／クロック数変換回路DEとを備える。【選択図】図２
2015149113.tif 000002
【特許請求の範囲】
【請求項１】
Ｅ×Ｍ次元（ただし、Ｅ，Ｍはいずれも２以上の整数である。）の検索データをＭ次元ずつＥ回に分けて保存する検索データ保存回路と、
Ｒ個（ただし、Ｒは２以上の整数である。）のＥ×Ｍ次元の参照データをＲ個のＭ次元ずつＥ回に分けて保存する参照データ保存回路と、
前記検索データ保存回路および前記参照データ保存回路に新たなデータが保存されるたびに、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の部分距離を計算する距離計算回路と、
前記検索データ保存回路および前記参照データ保存回路に新たなデータが保存されるたびに、個々の参照データごとに、前記距離計算回路によって計算された各次元の部分距離を累積加算する次元数拡張回路と、
前記Ｅ×Ｍ次元の検索データおよび前記Ｒ個のＥ×Ｍ次元の参照データがそれぞれＥ回に分けて前記検索データ保存回路および前記参照データ保存回路に保存された後に、個々の参照データごとに、前記次元数拡張回路によって累積加算された部分距離を合計して前記Ｅ×Ｍ次元の検索データと個々の前記Ｅ×Ｍ次元の参照データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号を出力する距離／クロック数変換回路とを備えている
ことを特徴とする連想メモリ。
【請求項２】
前記次元数拡張回路が、第１および第２のマルチプレクサと、全加算器と、第１および第２のＤフリップフロップとを有するものであり、
前記第１のマルチプレクサは、前記距離計算回路によって計算された第１の次元の部分距離および前記第１のＤフリップフロップの出力がそれぞれ第１および第２の入力として与えられ、第１の制御信号によって前記第１および第２の入力のいずれか一方を選択的に出力するものであり、
前記第２のマルチプレクサは、前記距離計算回路によって計算された第２の次元の部分距離および前記第２のＤフリップフロップの出力がそれぞれ第１および第２の入力として与えられ、前記第１の制御信号によって前記第１および第２の入力のいずれか一方を選択的に出力するものであり、
前記全加算器は、前記第１のマルチプレクサの出力と前記第２のマルチプレクサの出力とを全加算するものであり、
前記第１のＤフリップフロップは、前記全加算器の出力がデータ入力され、第２の制御信号によって入力データの保存が制御されるものであり、
前記第２のＤフリップフロップは、前記全加算器の出力がデータ入力され、前記第２の制御信号の反転である第３の制御信号によって入力データの保存が制御されるものである
ことを特徴とする請求項１に記載の連想メモリ。
【請求項３】
前記距離計算回路が、前記部分距離として、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の差分絶対値を計算する
ことを特徴とする請求項１または請求項２に記載の連想メモリ。
【請求項４】
前記距離計算回路が、前記部分距離として、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の差分二乗値を計算する
ことを特徴とする請求項１または請求項２に記載の連想メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連想メモリに関し、特に、クロックカウント式の連想メモリの次元数を拡張する技術に関する。
【背景技術】
【０００２】
近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをＬＳＩ（Large Scale Integrated circuit）上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。
【０００３】
パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。
【０００４】
前者は、ＣＡＭ（Content Addressable Memory）と呼ばれ、ネットワークルータのＩＰアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ（Associative Memory）と呼ぶ。
【０００５】
連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている（非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】S.Sasaki et al., "Digital Associative Memory for Word-Parallel Manhattan-Distance-Based Vector Quantization," ESSCIRC'2012, 2012, pp.185-188
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本願発明者は、これまでに、検索に係るクロックカウント数を削減する機構（有効ビット設定部）とユークリッド距離検索のための二乗計算回路（距離演算回路）とを備えたクロックカウント式の連想メモリを発明し、特願２０１３−０２５４６５（以下、先願と称する）において開示した。これにより、データ規模が増大しても高速な検索が可能なユークリッド／マンハッタン距離検索連想メモリをエラーフリー、高電力効率に実現した。
【０００８】
しかし、ハードウェアに実装可能なデータサイズには制約がある。先願発明に係る連想メモリは、原理的にはデータサイズに制約がないが、データサイズの増加により動作周波数が低下してしまう。この点において、小さなハードウェアによって大きな次元までの１ＮＮ（1-Nearest Neighbor）検索を実現することができれば効率が向上する。
【０００９】
上記問題に鑑み、本発明は、アプリケーション上でより大きなデータサイズが要求される場合に次元数の拡張が可能な連想メモリを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の一局面に従った連想メモリは、Ｅ×Ｍ次元（ただし、Ｅ，Ｍはいずれも２以上の整数である。）の検索データをＭ次元ずつＥ回に分けて保存する検索データ保存回路と、Ｒ個（ただし、Ｒは２以上の整数である。）のＥ×Ｍ次元の参照データをＲ個のＭ次元ずつＥ回に分けて保存する参照データ保存回路と、前記検索データ保存回路および前記参照データ保存回路に新たなデータが保存されるたびに、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の部分距離を計算する距離計算回路と、前記検索データ保存回路および前記参照データ保存回路に新たなデータが保存されるたびに、個々の参照データごとに、前記距離計算回路によって計算された各次元の部分距離を累積加算する次元数拡張回路と、前記Ｅ×Ｍ次元の検索データおよび前記Ｒ個のＥ×Ｍ次元の参照データがそれぞれＥ回に分けて前記検索データ保存回路および前記参照データ保存回路に保存された後に、個々の参照データごとに、前記次元数拡張回路によって累積加算された部分距離を合計して前記Ｅ×Ｍ次元の検索データと個々の前記Ｅ×Ｍ次元の参照データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号を出力する距離／クロック数変換回路とを備えているものである。
【００１１】
これによると、Ｅ×Ｍ次元の検索データおよび参照データがＭ次元ずつＥ回に分けて検索データ保存回路および参照データ保存回路に保存され、検索データ保存回路および参照データ保存回路に新たなデータが保存されるたびに検索データと参照データの各次元の部分距離が計算され、さらに累積加算される。これにより、Ｅ×Ｍ次元のデータの次元数がＭ次元に圧縮され、最大でＭ次元のデータしか扱えない連想メモリにおいて実質的にＥ×Ｍ次元のデータの取り扱いが可能となる。
【００１２】
上記の連想メモリにおいて、前記次元数拡張回路が、第１および第２のマルチプレクサと、全加算器と、第１および第２のＤフリップフロップとを有するものであってもよく、前記第１のマルチプレクサは、前記距離計算回路によって計算された第１の次元の部分距離および前記第１のＤフリップフロップの出力がそれぞれ第１および第２の入力として与えられ、第１の制御信号によって前記第１および第２の入力のいずれか一方を選択的に出力するものであってもよく、前記第２のマルチプレクサは、前記距離計算回路によって計算された第２の次元の部分距離および前記第２のＤフリップフロップの出力がそれぞれ第１および第２の入力として与えられ、前記第１の制御信号によって前記第１および第２の入力のいずれか一方を選択的に出力するものであってもよく、前記全加算器は、前記第１のマルチプレクサの出力と前記第２のマルチプレクサの出力とを全加算するものであってもよく、前記第１のＤフリップフロップは、前記全加算器の出力がデータ入力され、第２の制御信号によって入力データの保存が制御されるものであってもよく、前記第２のＤフリップフロップは、前記全加算器の出力がデータ入力され、前記第２の制御信号の反転である第３の制御信号によって入力データの保存が制御されるものであってもよい。
【００１３】
これによると、距離計算回路によって計算された各次元の部分距離を２次元分まとめて累積加算することができ、データ信号線を削減することができる。
【００１４】
前記距離計算回路が、前記部分距離として、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の差分絶対値を計算してもよい。
【００１５】
これによると、検索データと参照データとの間のマンハッタン距離を計算することができる。
【００１６】
前記距離計算回路が、前記部分距離として、前記検索データ保存回路に保存された検索データと前記参照データ保存回路に保存された個々の参照データとの各次元の差分二乗値を計算してもよい。
【００１７】
これによると、検索データと参照データとの間のユークリッド距離を計算することができる。
【発明の効果】
【００１８】
本発明によると、連想メモリで取り扱い可能なデータ次元数を任意に拡張することができる。これにより、大きなデータサイズが要求されるアプリケーションにもクロックカウント式の連想メモリを適用できるようになる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施形態に係る連想メモリにおける次元数拡張を説明する模式図
【図２】本発明の一実施形態に係る連想メモリの概略構成図
【図３】一例に係るタイミング信号のタイミングチャート
【図４】一例に係る次元数拡張回路の構成図
【図５Ａ】図４の次元数拡張回路の動作例を示す図
【図５Ｂ】図４の次元数拡張回路の動作例を示す図５Ａに続く図
【図６】一例に係る制御回路の構成図
【図７】図６の制御回路の入出力信号のタイミングチャート
【図８】一例に係るＤＣ制御回路の構成図
【図９】図８のＤＣ制御回路の入出力信号のタイミングチャート
【図１０】一例に係るＤＥＣ制御回路の構成図
【図１１】図１０のＤＥＣ制御回路の入出力信号のタイミングチャート
【発明を実施するための形態】
【００２０】
以下、図面を参照しながら本発明を実施するための形態について説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰り返さない。また、本発明は、下記の実施形態に限定されるものではない。
【００２１】
≪次元数拡張の概要≫  
本発明の一実施形態に係る連想メモリは、先願発明に係る連想メモリにおいて検索データおよび参照データの次元数を拡張可能にしたものである。すなわち、先願発明に係る連想メモリは最大で設計時に指定したＭ次元（Ｍは２以上の整数）のデータしか扱えなかったのに対して、本実施形態に係る連想メモリは、データの次元数をＥ×Ｍ次元（Ｅは２以上の整数）にまで拡張することができる。
【００２２】
図１は、本発明の一実施形態に係る連想メモリにおける次元数拡張を説明する模式図である。データの次元数がＥ×Ｍ次元の場合において、検索データと参照データとの間のａ＝ｈかつｊ次元目の二乗計算結果（部分距離）をｄｈ，（ｈ−１）Ｍ＋ｊとすると、検索データと参照データとの間の距離（例えば、ユークリッド距離）ＤＥは次式（１）のように計算される。
【００２３】
【数１】
2015149113.tif 000003
【００２４】
ここで、式（１）においてΣａ＝１Ｅの計算を先に行う。すなわち、図１に示したように、Ｅ×Ｍ次元のデータをＥ行×Ｍ列の行列形式で表した場合において、先に列方向（図中の破線枠）の累積加算を行う。これにより、Ｅ×Ｍ次元のデータの次元数がＭ次元に圧縮され、最大でＭ次元のデータしか扱えない先願発明に係る連想メモリにおいて実質的にＥ×Ｍ次元のデータの取り扱いが可能となる。
【００２５】
本実施形態に係る連想メモリは、先願発明に係る連想メモリに、Ｅ×Ｍ次元のデータの次元数を上記のように圧縮してＭ次元のデータにする機能を追加したものである。以下、本実施形態に係る連想メモリの詳細について説明する。
【００２６】
≪本実施形態に係る連想メモリの構成例≫
図２は、本発明の一実施形態に係る連想メモリの概略構成を示す。本実施形態に係る連想メモリ１００は、メモリアレイ部１０と、Ｗｉｎｎｅｒ検出器２０とを備える。
【００２７】
メモリアレイ部１０は、メモリ部１、行デコーダ２、列デコーダ３、読出／書込回路４、および検索データ保存回路５を含む。
【００２８】
メモリ部１は、参照データ保存回路（Storage Cell）ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭと、距離計算回路（Distance Calculator）ＤＣ１１〜ＤＣ１Ｍ，ＤＣ２１〜ＤＣ２Ｍ，…，ＤＣＲ１〜ＤＣＲＭと、次元数拡張回路（Dimensional Extension Circuit）ＤＥＣ１１〜ＤＥＣ１Ｍ／２，ＤＥＣ２１〜ＤＥＣ２Ｍ／２，…，ＤＥＣＲ１〜ＤＥＣＲＭ／２と、距離／クロック数変換回路（Distance Evaluator）ＤＥ１〜ＤＥＲとを含む。なお、ＭおよびＲは、いずれも２以上の整数である。
【００２９】
行デコーダ２は、メモリ部１の行方向のアドレスを指定する。列デコーダ３は、メモリ部１の列方向のアドレスを指定する。読出／書込回路４は、参照データを行デコーダ２および列デコーダ３によって指定された参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭに書き込むとともに、検索データを検索データ保存回路５に書き込む。
【００３０】
距離計算回路ＤＣ１１〜ＤＣ１Ｍは、それぞれ、参照データ保存回路ＳＣ１１〜ＳＣ１Ｍに対応して設けられる。また、距離計算回路ＤＣ２１〜ＤＣ２Ｍは、それぞれ、参照データ保存回路ＳＣ２１〜ＳＣ２Ｍに対応して設けられる。以下、同様にして、距離計算回路ＤＣＲ１〜ＤＣＲＭは、それぞれ、参照データ保存回路ＳＣＲ１〜ＳＣＲＭに対応して設けられる。
【００３１】
次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２は、それぞれ、距離計算回路ＤＣ１１〜ＤＣ１Ｍの隣り合う２個に対応して１個設けられる。また、次元数拡張回路ＤＥＣ２１〜ＤＥＣ２Ｍ／２は、それぞれ、距離計算回路ＤＣ２１〜ＤＣ２Ｍの隣り合う２個に対応して１個設けられる。以下、同様にして、次元数拡張回路ＤＥＣＲ１〜ＤＥＣＲＭ／２は、それぞれ、距離計算回路ＤＣＲ１〜ＤＣＲＭの隣り合う２個に対応して１個設けられる。
【００３２】
距離／クロック数変換回路ＤＥ１は、次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２に対応して設けられる。また、距離／クロック数変換回路ＤＥ２は、次元数拡張回路ＤＥＣ２１〜ＤＥＣ２Ｍ／２に対応して設けられる。以下、同様にして、距離／クロック数変換回路ＤＥＲは、次元数拡張回路ＤＥＣＲ１〜ＤＥＣＲＭ／２に対応して設けられる。
【００３３】
参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭは、行デコーダ２、列デコーダ３、および読出／書込回路４によって書き込まれた参照データを保存する。この場合、参照データ保存回路ＳＣ１１〜ＳＣ１Ｍは、Ｎ×Ｍ（Ｎは１以上の整数）ビットの参照データ１を保存する。また、参照データ保存回路ＳＣ２１〜ＳＣ２Ｍは、Ｎ×Ｍビットの参照データ２を保存する。以下、同様にして、参照データ保存回路ＳＣＲ１〜ＳＣＲＭは、Ｎ×Ｍビットの参照データＲを保存する。すなわち、参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭは、Ｒ個のＭ次元の参照データ（各次元はＮビットデータ）を保存する。
【００３４】
検索データ保存回路５は、Ｎ×Ｍビットの検索データを保存する。すなわち、検索データ保存回路５は、Ｍ次元の検索データ（各次元はＮビットデータ）を保存する。
【００３５】
上記のように、検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭが保存可能な検索データおよび参照データの次元数はＭ次元であるため、Ｅ×Ｍ次元の検索データおよび参照データをＥ回に分けてこれらデータ保存回路に保存する。具体的には、検索データ保存回路５は、Ｅ×Ｍ次元の検索データをＭ次元ずつＥ回に分けて保存する。一方、参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭは、Ｒ個のＥ×Ｍ次元の参照データをＲ個のＭ次元ずつＥ回に分けて保存する。
【００３６】
なお、Ｅ×Ｍ次元の検索データおよびＲ個のＥ×Ｍ次元の参照データは、図示しないメモリに保存されており、図示しない制御回路によってＥ回に分けて当該メモリからＭ次元ずつ読み出される。そして、当該メモリから読み出されたＭ次元の検索データおよびＲ個のＭ次元の参照データは、行デコーダ２、列デコーダ３、および読出／書込回路４によって検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭにそれぞれ書き込まれる。
【００３７】
距離計算回路ＤＣ１１〜ＤＣ１Ｍは、それぞれ、検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍに新たなデータが保存されるたびに、検索データ保存回路５に保存されたＮ×Ｍビットの検索データと参照データ保存回路ＳＣ１１〜ＳＣ１Ｍに保存されたＮ×Ｍビットの参照データ１との各次元の部分距離を計算する。また、距離計算回路ＤＣ２１〜ＤＣ２Ｍは、それぞれ、検索データ保存回路５および参照データ保存回路ＳＣ２１〜ＳＣ２Ｍに新たなデータが保存されるたびに、検索データ保存回路５に保存されたＮ×Ｍビットの検索データと参照データ保存回路ＳＣ２１〜ＳＣ２Ｍに保存されたＮ×Ｍビットの参照データ２との各次元の部分距離を計算する。以下、同様にして、距離計算回路ＤＣＲ１〜ＤＣＲＭは、それぞれ、検索データ保存回路５および参照データ保存回路ＳＣＲ１〜ＳＣＲＭに新たなデータが保存されるたびに、検索データ保存回路５に保存されたＮ×Ｍビットの検索データと参照データ保存回路ＳＣＲ１〜ＳＣＲＭに保存されたＮ×Ｍビットの参照データＲとの各次元の部分距離を計算する。これら距離計算回路ＤＣ１１〜ＤＣ１Ｍ，ＤＣ２１〜ＤＣ２Ｍ，…，ＤＣＲ１〜ＤＣＲＭによる部分距離の計算は並列に行われる。
【００３８】
なお、部分距離は、検索データと参照データとの各次元の差分絶対値および差分二乗値のいずれでもよい。検索データと参照データとの間の距離をマンハッタン距離で評価する場合、差分距離として差分絶対値を用いるとよい。検索データと参照データとの間の距離をユークリッド距離で評価する場合、差分距離として差分二乗値を用いるとよい。距離計算回路の具体的な回路構成については先願の明細書および図面に詳しく説明されている。以下では、便宜上、部分距離として差分二乗値を用いるものとして説明する。
【００３９】
次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２は、それぞれ、検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍに新たなデータが保存されるたびに、距離計算回路ＤＣ１１〜ＤＣ１Ｍによって計算された各次元の部分距離を２次元分まとめて累積加算する。また、次元数拡張回路ＤＥＣ２１〜ＤＥＣ２Ｍ／２は、それぞれ、検索データ保存回路５および参照データ保存回路ＳＣ２１〜ＳＣ２Ｍに新たなデータが保存されるたびに、距離計算回路ＤＣ２１〜ＤＣ２Ｍによって計算された各次元の部分距離を２次元分まとめて累積加算する。以下、同様にして、次元数拡張回路ＤＥＣＲ１〜ＤＥＣＲＭ／２は、それぞれ、検索データ保存回路５および参照データ保存回路ＳＣＲ１〜ＳＣＲＭに新たなデータが保存されるたびに、距離計算回路ＤＣＲ１〜ＤＣＲＭによって計算された各次元の部分距離を２次元分まとめて累積加算する。これら次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２，ＤＥＣ２１〜ＤＥＣ２Ｍ／２，…，ＤＥＣＲ１〜ＤＥＣＲＭ／２による部分距離の累積加算は並列に行われる。
【００４０】
距離計算回路ＤＣ１１〜ＤＣ１Ｍ，ＤＣ２１〜ＤＣ２Ｍ，…，ＤＣＲ１〜ＤＣＲＭに１対１に対応するように次元数拡張回路を配置してもよいが、Ｅが２の冪乗で表される場合、ｌｏｇ２Ｅだけ余分にビット数が必要となる。Ｅ＝６４の場合、ハードウェア上に用意された次元の６４倍の次元まで処理できるが、１次元当たり６ビット余分に用意しておく必要がある。そこで、データ信号線を削減するために、本実施形態のように、各次元数拡張回路において２次元分の部分距離の累積加算を行うようにするとよい。
【００４１】
距離計算回路ＤＣ１１〜ＤＣ１Ｍ，ＤＣ２１〜ＤＣ２Ｍ，…，ＤＣＲ１〜ＤＣＲＭからは、それぞれ、２Ｎビットの部分距離（差分二乗値）が出力される。したがって、２個の距離計算回路から出力される２次元分の部分距離は４Ｎビットとなる。このとき、各距離計算回路から出力される各次元の部分距離を逐次的にａ＝１からａ＝Ｅまで累積加算する場合、各次元数拡張回路の出力ビット幅は２次元当たり４Ｎ＋２ｌｏｇ２Ｅビット必要となる。これに対して、本実施形態のように、２個の距離計算回路から出力される２次元分の部分距離をまとめて累積加算を行うことで、各次元数拡張回路の出力ビット幅は（２Ｎ＋１）＋ｌｏｇ２Ｅビットに削減することができる。例えば、Ｅ＝２２Ｎ−１倍の次元拡張を行う場合、次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２，ＤＥＣ２１〜ＤＥＣ２Ｍ／２，…，ＤＥＣＲ１〜ＤＥＣＲＭ／２の出力ビット幅は４Ｎビットとなり、２個の距離計算回路から出力される２次元分の部分距離である４Ｎビットと等しくすることができる。また、例えば、Ｎ＝８ビット、すなわち、Ｅ＝３２７６８倍の次元数拡張を行う場合、次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２，ＤＥＣ２１〜ＤＥＣ２Ｍ／２，…，ＤＥＣＲ１〜ＤＥＣＲＭ／２の出力ビット幅は４Ｎ＝３２ビットとなる。ここで、Ｍ＝１６次元とすると、本実施形態に係る連想メモリ１００は、約５０万次元まで拡張したデータを取り扱うことができる。
【００４２】
距離／クロック数変換回路ＤＥ１は、Ｅ×Ｍ次元の検索データおよびＲ個のＥ×Ｍ次元の参照データがそれぞれＥ回に分けて検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍに保存された後に、次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２によって累積加算された部分距離を合計してＥ×Ｍ次元の検索データとＥ×Ｍ次元の参照データ１との距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号Ｃ１を出力する。また、距離／クロック数変換回路ＤＥ２は、Ｅ×Ｍ次元の検索データおよびＲ個のＥ×Ｍ次元の参照データがそれぞれＥ回に分けて検索データ保存回路５および参照データ保存回路ＳＣ２１〜ＳＣ２Ｍに保存された後に、次元数拡張回路ＤＥＣ２１〜ＤＥＣ２Ｍ／２によって累積加算された部分距離を合計してＥ×Ｍ次元の検索データとＥ×Ｍ次元の参照データ２との距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号Ｃ２を出力する。以下、同様にして、距離／クロック数変換回路ＤＥＲは、Ｅ×Ｍ次元の検索データおよびＲ個のＥ×Ｍ次元の参照データがそれぞれＥ回に分けて検索データ保存回路５および参照データ保存回路ＳＣＲ１〜ＳＣＲＭに保存された後に、次元数拡張回路ＤＥＣＲ１〜ＤＥＣＲＭ／２によって累積加算された部分距離を合計してＥ×Ｍ次元の検索データとＥ×Ｍ次元の参照データＲとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すタイミング信号ＣＲを出力する。これら距離／クロック数変換回路ＤＥ１〜ＤＥＲによる、距離に応じたクロック数のカウントは並列に行われる。
【００４３】
Ｗｉｎｎｅｒ検出器２０は、距離／クロック数変換回路ＤＥ１〜ＤＥＲからそれぞれタイミング信号Ｃ１〜ＣＲを受ける。図３は、一例に係るタイミング信号のタイミングチャートである。そして、Ｗｉｎｎｅｒ検出器２０は、その受けたタイミング信号Ｃ１〜ＣＲのうち、一致タイミングが早い順にｋ（ｋは１≦ｋ≦Ｒを満たす整数）個のタイミング信号を検出し、その検出したｋ個のタイミング信号を検索データと参照データとの類似度を示すマッチ信号Ｍ１〜Ｍｋとして出力する。
【００４４】
≪次元数拡張回路の構成例≫
上述したように２個の距離計算回路から出力される２次元分の部分距離をまとめて累積加算を行う場合、式（１）は次式（２）のように変形される。
【００４５】
【数２】
2015149113.tif 000004
【００４６】
次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２，ＤＥＣ２１〜ＤＥＣ２Ｍ／２，…，ＤＥＣＲ１〜ＤＥＣＲＭ／２は、それぞれ、式（２）におけるΣａ＝１Ｅの計算を行う。
【００４７】
図４は、次元数拡張回路の構成例を示す。次元数拡張回路は、二つのマルチプレクサ（ＭＵＸ）１１ａ，１１ｂと、全加算器（Ｆｕｌｌ  Ａｄｄｅｒ）１２と、二つのＤフリップフロップ（ＤＦＦ）１３ａ，１３ｂとを含む。
【００４８】
ＭＵＸ１１ａは、距離計算回路ＤＣｉ（２ｊ−１）（ｉは１≦ｉ≦Ｒを満たす整数、ｊは１≦ｊ≦Ｍ／２を満たす整数）によって計算された部分距離ｄｉ（２ｊ−１）が入力ｉｎ０として、ＤＦＦ１３ａの出力が入力ｉｎ１としてそれぞれ与えられ、制御信号ＳＤＤによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。部分距離ｄｉ（２ｊ−１）は差分二乗値であり、そのビット幅は２Ｎビットである。
【００４９】
ＭＵＸ１１ｂは、距離計算回路ＤＣｉ（２ｊ）によって計算された部分距離ｄｉ（２ｊ）が入力ｉｎ０として、ＤＦＦ１３ｂの出力が入力ｉｎ１としてそれぞれ与えられ、制御信号ＳＤＤによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。部分距離ｄｉ（２ｊ）は差分二乗値であり、そのビット幅は２Ｎビットである。
【００５０】
ＭＵＸ１１ａおよびＭＵＸ１１ｂは、いずれも、ＳＤＤが“０”のときはｉｎ０を出力し、ＳＤＤが“１”のときはｉｎ１を出力する。
【００５１】
全加算器１２は、ＭＵＸ１１ａの出力が入力Ａとして、ＭＵＸ１１ｂの出力が入力Ｂとしてそれぞれ与えられ、ＡとＢの全加算を行う２Ｎビットの全加算器である。ＣＢ（Carry Before）、ＣＮ（Carry Next）は、それぞれ、前のビットからの桁上げ信号、および次のビットへの桁上げ信号である。
【００５２】
ＤＦＦ１３ａは、全加算器１２の出力ＯＵＴがデータ入力され、制御信号ＳＤによって入力データの保存が制御される。具体的には、ＤＦＦ１３ａは、ＳＤの立ち上がりエッジのタイミングで入力データを保存する。
【００５３】
ＤＦＦ１３ｂは、全加算器１２の出力ＯＵＴがデータ入力され、制御信号ＳＤＱによって入力データの保存が制御される。ＳＤＱはＳＤの反転信号である。具体的には、ＤＦＦ１３ｂは、ＳＤＱの立ち上がりエッジのタイミングで入力データを保存する。
【００５４】
図５Ａおよび図５Ｂは、図４の次元数拡張回路の動作例を示す図である。図５Ａおよび図５Ｂを参照しながら上記構成の次元数拡張回路の動作例について説明する。なお、図中の矢印はデータの流れを表す。
【００５５】
ｓｔｅｐ１：ａ＝１で連想メモリ１００にＭ次元の検索データおよびＲ個のＭ次元の参照データが保存され、これら検索データと個々の参照データとの間の各次元の部分距離が計算される。ＳＤＤが“０”であるため、全加算器１２に２次元分のｄｉ（２ｊ−１）およびｄｉ（２ｊ）が入力されて加算される。全加算器１２の加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、この時点ではそのどちらにも取り込まれない。
【００５６】
ｓｔｅｐ２：ＳＤが“０”から“１”へ変化し、ＳＤＱが“１”から“０”へ変化する。ＳＤが立ち上がることで、ＤＦＦ１３ａが全加算器１２の加算結果を保存し、ＤＦＦ１３ａから保存値が出力される。
【００５７】
ｓｔｅｐ３：ａ＝２で連想メモリ１００に新たなＭ次元の検索データおよびＲ個のＭ次元の参照データが保存され、これら検索データと個々の参照データとの間の各次元の部分距離が計算される。ＳＤＤが“０”であるため、全加算器１２に更新された２次元分のｄｉ（２ｊ−１）およびｄｉ（２ｊ）が入力されて加算される。全加算器１２の加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、ＳＤが“１”のまま、ＳＤＱが“０”のままであるため、ＤＦＦ１３ａおよびＤＦＦ１３ｂに全加算器１２の加算結果は取り込まれない。
【００５８】
ｓｔｅｐ４：ＳＤが“１”から“０”へ変化し、ＳＤＱが“０”から“１”へ変化する。ＳＤＱが立ち上がることで、ＤＦＦ１３ｂが全加算器１２の加算結果を保存し、ＤＦＦ１３ｂから保存値が出力される。
【００５９】
ｓｔｅｐ５：ＳＤＤが“０”から“１”へ変化し、全加算器１２にＤＦＦ１３ａの出力およびＤＦＦ１３ｂの出力が入力されて加算される。これにより、ａ＝１のときのｄｉ（２ｊ−１）およびｄｉ（２ｊ）の加算結果と、ａ＝２のときのｄｉ（２ｊ−１）およびｄｉ（２ｊ）の加算結果とが加算される。すなわち、ａ＝１からａ＝２までの２次元分の部分距離が累積加算される。全加算器１２の加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、ＳＤが“０”のまま、ＳＤＱが“１”のままであるため、ＤＦＦ１３ａおよびＤＦＦ１３ｂに全加算器１２の加算結果は取り込まれない。
【００６０】
ｓｔｅｐ６：ＳＤが“０”から“１”へ変化し、ＳＤＱが“１”から“０”へ変化する。ＳＤが立ち上がることで、ＤＦＦ１３ａが全加算器１２の加算結果、すなわち、ａ＝１からａ＝２までの２次元分の部分距離の累積加算値を保存し、ＤＦＦ１３ａから保存値が出力される。このとき、全加算器１２においてＤＦＦ１３ｂの出力とＤＦＦ１３ａの更新された出力とが加算され、新たな加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、ＳＤおよびＳＤＱがいずれも立ち上がらないため、ＤＦＦ１３ａおよびＤＦＦ１３ｂに全加算器１２の更新された加算結果は取り込まれない。
【００６１】
ｓｔｅｐ７：ａ＝３で連想メモリ１００に新たなＭ次元の検索データおよびＲ個のＭ次元の参照データが保存され、これら検索データと個々の参照データとの間の各次元の部分距離が計算される。ＳＤＤが“１”から“０”へ変化し、全加算器１２に更新された２次元分のｄｉ（２ｊ−１）およびｄｉ（２ｊ）が入力されて加算される。全加算器１２の加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、ＳＤが“１”のまま、ＳＤＱが“０”のままであるため、ＤＦＦ１３ａおよびＤＦＦ１３ｂに全加算器１２の加算結果は取り込まれない。
【００６２】
ｓｔｅｐ８：ＳＤが“１”から“０”へ変化し、ＳＤＱが“０”から“１”へ変化する。ＳＤＱが立ち上がることで、ＤＦＦ１３ｂが全加算器１２の加算結果を保存し、ＤＦＦ１３ｂから保存値が出力される。
【００６３】
ｓｔｅｐ９：ＳＤＤが“０”から“１”へ変化し、全加算器１２にＤＦＦ１３ａの出力およびＤＦＦ１３ｂの出力が入力されて加算される。これにより、ａ＝１からａ＝２までのｄｉ（２ｊ−１）およびｄｉ（２ｊ）の累積加算結果と、ａ＝３のときのｄｉ（２ｊ−１）およびｄｉ（２ｊ）の加算結果とが加算される。すなわち、ａ＝１からａ＝３までの２次元分の部分距離が累積加算される。全加算器１２の加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、ＳＤが“０”のまま、ＳＤＱが“１”のままであるため、ＤＦＦ１３ａおよびＤＦＦ１３ｂに全加算器１２の加算結果は取り込まれない。
【００６４】
ｓｔｅｐ１０：ＳＤが“０”から“１”へ変化し、ＳＤＱが“１”から“０”へ変化する。ＳＤが立ち上がることで、ＤＦＦ１３ａが全加算器１２の加算結果、すなわち、ａ＝１からａ＝３までの２次元分の部分距離の累積加算値を保存し、ＤＦＦ１３ａから保存値が出力される。このとき、全加算器１２においてＤＦＦ１３ｂの出力とＤＦＦ１３ａの更新された出力とが加算され、新たな加算結果がＤＦＦ１３ａおよびＤＦＦ１３ｂにデータ入力されるが、ＳＤおよびＳＤＱがいずれも立ち上がらないため、ＤＦＦ１３ａおよびＤＦＦ１３ｂに全加算器１２の更新された加算結果は取り込まれない。
【００６５】
以後、同様の処理をａ＝Ｅまで繰り返すことで、ＤＦＦ１３ａにａ＝１からａ＝Ｅまでの２次元分の部分距離の累積加算値が保存され、ＤＦＦ１３ａから累積加算値Ｄｉ（２ｊ−１）が出力される。このように、次元数拡張回路によってＥ×Ｍ次元のデータの次元数がＭ次元に圧縮される。これにより、一度に最大でＭ次元のデータしか扱えないメモリアレイ部１０を有する連想メモリ１００において、処理可能なデータの次元数を任意に拡張することができる。
【００６６】
≪制御回路の構成例≫
次に、メモリアレイ部１０へのデータ書き込み、距離計算回路ＤＣ１１〜ＤＣ１Ｍ，ＤＣ２１〜ＤＣ２Ｍ，…，ＤＣＲ１〜ＤＣＲＭの制御、および次元数拡張回路ＤＥＣ１１〜ＤＥＣ１Ｍ／２，ＤＥＣ２１〜ＤＥＣ２Ｍ／２，…，ＤＥＣＲ１〜ＤＥＣＲＭ／２の制御について説明する。
【００６７】
図６は、制御回路の構成例を示す。本例に係る制御回路２００は、ＤＣ制御回路（距離計算回路の制御回路）２１０と、ＤＥＣ制御回路（次元数拡張回路の制御回路）２２０とを含む。図中の「Ｄ−ＦＦ」は、ネガティブエッジ型のＤフリップフロップを表す。図７は、制御回路２００の入出力信号のタイミングチャートである。
【００６８】
図８は、ＤＣ制御回路２１０の構成例を示す。図中の「ＦＤＩＶ」は分周回路（２分周）を表す。図９は、ＤＣ制御回路２１０の入出力信号のタイミングチャートである。ＤＣ制御回路２１０において、ＳＱＧが立ち上がるとＣＬＫの反転信号としてＲＳＴＤＱが立ち下がる。そして、１クロックカウントされることで、分周回路ＦＤＶＩの出力が“１”になる。ＳＱＧも“１”なのでＳＱＤはＳＱＧの１クロック後に“１”になる。
【００６９】
図１０は、ＤＥＣ制御回路２２０の構成例を示す。図中の「ＦＤＩＶ」は分周回路（２分周）を、「ＳＲＦＦ」はＳＲフリップフロップを表す。図１１は、ＤＥＣ制御回路２２０の入出力信号のタイミングチャートである。ＤＥＣ制御回路２２０において、ＳＱＧが１回目に立ち下がると、分周回路ＦＤＶＩの出力が“１”になる。これにより、その後はＳＱＧとＳＤのタイミングが等しくなり、また、ＳＤＤはＳＤの反転信号となる。なお、厳密には、ＳＤＤはＣＬＫに同期した信号である。
【００７０】
次に、図７のタイミングチャートを参照しながら制御回路２００の動作例について説明する。
【００７１】
ｓｔｅｐ  Ｉ：Ｒ個のＥ×Ｍ次元の参照データの部分データであるＲ個のＭ次元の参照データ（ａ＝１のときの参照データ）が参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭに保存される（処理Ａ）。また、Ｅ×Ｍ次元の検索データの部分データであるＭ次元の検索データ（ａ＝１のときの検索データ）が検索データ保存回路５に保存される（処理Ｂ）。処理Ａおよび処理Ｂは、行デコーダ２および列デコーダ３を１クロックずつ切り替えながら行われる。処理Ａおよび処理Ｂが終了するとＳＱが立ち上がる。ＳＱは図示しないＣＰＵから出力される。以後、ＳＱは、ａ＝Ｅまで、すなわち、Ｅ×Ｍ次元のデータ検索によってｗｉｎｎｅｒが検出されるまで立ち上げ続ける。
【００７２】
ｓｔｅｐ  ＩＩ：ＳＱが立ち上がると、ＳＱとＧＣＬＫＱの論理積であるＳＱＧが立ち上がる。ＧＣＬＫＱは、ＧＣＬＫの反転信号であり、ＧＣＬＫは、距離計算回路において二乗計算（部分距離の計算）が終了すると“１”となる信号である。ＳＱＧは、距離計算回路において、検索データと参照データとの各次元の差分絶対値ＡＤをラッチ回路で保存するためのラッチ信号として使用される。ＳＱＧをクロック信号ＣＬＫに同期させたのがＳＱＧＳＹである。ＳＱＧＳＹが立ち上がってから１クロックでＲＳＴＤが立ち上がることで距離計算回路における図示しない二乗計算用のＤフリップフロップをリセットする。そして、ＲＳＴＤが再び立ち上がるタイミングでＳＱＤが立ち上がる。ＳＱＤは、距離計算回路における図示しないマルチプレクサの切り替えに使用される。つまり、絶対値差計算から二乗計算に切り替わり、クロックが入力されるごとに逐次的に部分積の加算が行われる。ＳＱＤが立ち上がってからＮクロックで二乗計算が終了し、ＧＣＬＫが立ち上がる。なお、二乗計算を行う距離計算回路の具体的な構成については先願の明細書および図面に詳しく説明されている。
【００７３】
ｓｔｅｐ  ＩＩＩ：ＧＣＬＫの立ち上がりを受けて再び処理Ａおよび処理Ｂが開始される。処理Ａおよび処理Ｂが終了するとＲＳＴＤＣが立ち上がる。つまり、本ステップでは、ａ＝２のときのデータの書き込みと絶対値差計算が行われる。
【００７４】
ｓｔｅｐ  ＩＶ：ＲＳＴＤＣが立ち上がると、ＧＣＬＫが立ち下がる。ＧＣＬＫの立ち下がりによりＳＱＧが立ち上がるため、距離計算回路において絶対値差がラッチされる。距離計算回路に関するＲＳＴＤ、ＳＱＤ、ＳＱＧについては以上の動作を繰り返す。ａ＝２からＳＱＧＳＹとＳＤの信号変化のタイミングは等しくなる。ａ＝２でＳＱＧＳＹが立ち上がることでＳＤも立ち上がり、次元数拡張回路におけるＤＦＦ１３ａにａ＝１のときの計算結果が保存される。
【００７５】
ｓｔｅｐ  Ｖ：前ステップでａ＝２の場合の部分距離の計算が終了する。そして、ＧＣＬＫが立ち上がることでＳＱＧが立ち下がる。ＳＱＧＳＹもＣＬＫに同期して立ち下がり、ＳＤも立ち下がる。ＳＤが立ち下がることでＳＤＱが立ち上がり、次元数拡張回路におけるＤＦＦ１３ｂにａ＝２のときの計算結果が保存される。そして、ａ＝２からＳＤＱのクロック同期信号としてＳＤＤが動作する。ＳＤＤが立ち上がることで、次元数拡張回路におけるＭＵＸ１１ａおよび１１ｂが切り替わり、ａ＝１とａ＝２の場合の部分距離が累積加算される。本ステップでは、同時にａ＝３の場合の処理Ａおよび処理Ｂが行われる。その処理が終わり、ＲＳＴＤＣが立ち上がることでＳＤが立ち上がるため、次元数拡張回路におけるＤＦＦ１３ａにａ＝１からａ＝２までの累積加算結果が保存される。そして、その１クロック後にＳＤＤが立ち上がる。
【００７６】
以上の動作を繰り返すことで、Ｅ×Ｍ次元の検索データがＭ次元ずつＥ回に分けて検索データ保存回路５に保存されるとともに、Ｒ個のＥ×Ｍ次元の参照データがＲ個のＭ次元ずつＥ回に分けて参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭに保存され、さらに、距離計算回路および次元数拡張回路における処理がパイプライン化される。
【００７７】
以上、本実施形態によると、連想メモリ１００で取り扱い可能なデータ次元数を任意に拡張することができる。これにより、大きなデータサイズが要求されるアプリケーションにもクロックカウント式の連想メモリを適用できるようになる。
【００７８】
なお、データの次元数を拡張すると検索データと参照データとの距離も大きくなるため、距離／クロック数変換回路における処理時間（クロック数カウント）が増大することが予想される。そこで、先願に開示されているように、距離／クロック数変換回路における有効ビットを設定する有効ビット設定部を設けることで、クロックカウント数を削減することができる。
【００７９】
本実施形態に係る連想メモリ１００では、Ｅ×Ｍ次元のデータが図示しないメモリからＭ次元ずつＥ回に分けて検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭに保存されるが、変形例として、連想メモリ１００の容量を拡張してＥ×Ｍ次元の検索データおよびＲ個のＥ×Ｍ次元の参照データのすべてを連想メモリ１００に格納しておいてもよい。例えば、Ｅ×Ｍ次元のデータからＭ次元の部分データを選択して距離計算回路ＤＣ１１〜ＤＣ１Ｍ，ＤＣ２１〜ＤＣ２Ｍ，…，ＤＣＲ１〜ＤＣＲＭに入力するための選択回路を設けるか、または、検索データ保存回路５および参照データ保存回路ＳＣ１１〜ＳＣ１Ｍ，ＳＣ２１〜ＳＣ２Ｍ，…，ＳＣＲ１〜ＳＣＲＭをＦＩＦＯ（First-In First Out）型のスタックメモリなどで構成することでそのような変形例が可能である。そのような変形例では、Ｒ個のＭ次元のデータの並列処理が可能となる。
【産業上の利用可能性】
【００８０】
本発明に係る連想メモリは、パターン認識・学習、類似検索処理、知能情報処理、インテリジェント家電、監視システム、セキュリティ認証などの分野で利用することができる。
【符号の説明】
【００８１】
１００  連想メモリ
５      検索データ保存回路
ＳＣ    参照データ保存回路
ＤＣ    距離計算回路
ＤＥＣ  次元数拡張回路
ＤＥ    距離／クロック数変換回路
１１ａ  ＭＵＸ（第１のマルチプレクサ）
１１ｂ  ＭＵＸ（第２のマルチプレクサ）
１２    全加算器
１３ａ  ＤＦＦ（第１のＤフリップフロップ）
１３ｂ  ＤＦＦ（第２のＤフリップフロップ）
【図１】
2015149113.tif 000005
【図２】
2015149113.tif 000006
【図３】
2015149113.tif 000007
【図４】
2015149113.tif 000008
【図５Ａ】
2015149113.tif 000009
【図５Ｂ】
2015149113.tif 000010
【図６】
2015149113.tif 000011
【図８】
2015149113.tif 000012
【図１０】
2015149113.tif 000013
【図７】
2015149113.tif 000014
【図９】
2015149113.tif 000015
【図１１】
2015149113.tif 000016