明細書 :再構成可能連想メモリ
| 発行国 | 日本国特許庁(JP) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 公報種別 | 特許公報(B2) | ||||||||||
| 特許番号 | 特許第6215732号 (P6215732) | ||||||||||
| 公開番号 | 特開2015-162257 (P2015-162257A) | ||||||||||
| 登録日 | 平成29年9月29日(2017.9.29) | ||||||||||
| 発行日 | 平成29年10月18日(2017.10.18) | ||||||||||
| 公開日 | 平成27年9月7日(2015.9.7) | ||||||||||
| 発明の名称または考案の名称 | 再構成可能連想メモリ | ||||||||||
| 国際特許分類 | G11C 15/04 (2006.01) | ||||||||||
| ＦＩ | G11C 15/04 631F | ||||||||||
| 請求項の数または発明の数 | 5 | ||||||||||
| 全頁数 | 17 | ||||||||||
| 出願番号 | 特願2014-036698 (P2014-036698) | ||||||||||
| 出願日 | 平成26年2月27日(2014.2.27) | ||||||||||
| 審査請求日 | 平成28年12月14日(2016.12.14) | ||||||||||
| 特許権者または実用新案権者 | 【識別番号】504136568 【氏名又は名称】国立大学法人広島大学 |
||||||||||
| 発明者または考案者 | 【氏名】マタウシュ ハンスユルゲン 【氏名】赤澤 智信 |
||||||||||
| 個別代理人の代理人 | 【識別番号】110001427、【氏名又は名称】特許業務法人前田特許事務所 | ||||||||||
| 審査官 | 【審査官】後藤 彰 | ||||||||||
| 参考文献・文献 | 特開２０１３－１０１７２９（ＪＰ，Ａ） 特開２００２－２８８９８５（ＪＰ，Ａ） 矢野 祐二，”全並列型最小マンハッタン距離検索連想メモリ”，電子情報通信学会技術研究報告 ＤＣ２００２－３４～７１，日本，社団法人電子情報通信学会，２００２年１１月２１日，第102巻，第479号，ｐ．181-186 |
||||||||||
| 調査した分野 | Ｇ１１Ｃ １５／０４ | ||||||||||
| 特許請求の範囲 | 【請求項1】 それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離／クロック数変換回路とを有する、複数のエレメント回路と、 前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路とを備え、 前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する個別の参照データ検索回路が構成される ことを特徴とする再構成可能連想メモリ。 【請求項2】 複数の前記スイッチ回路がカスケード接続されており、 前記カスケード接続された複数の前記スイッチ回路によって、複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号の論理和を演算する論理和演算回路、および複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号を保存するシフトレジスタが構成される ことを特徴とする請求項１に記載の再構成可能連想メモリ。 【請求項3】 前記シフトレジスタのシフト出力を参照して前記シフトレジスタに保存されている前記マッチ信号の出力元の参照データ検索回路を特定し、当該特定した参照データ検索回路を識別する信号を出力するＷｉｎｎｅｒ検出回路を備えている ことを特徴とする請求項２に記載の再構成可能連想メモリ。 【請求項4】 回路構成情報を記憶し、当該回路構成情報に基づいて前記複数のスイッチ回路のそれぞれに前記回路構成信号を出力する回路構成情報記憶回路を備えている ことを特徴とする請求項１ないし請求項３のいずれかに記載の再構成可能連想メモリ。 【請求項5】 前記回路構成情報記憶回路が不揮発性メモリで構成されている ことを特徴とする請求項４に記載の再構成可能連想メモリ。 |
||||||||||
| 発明の詳細な説明 | 【技術分野】 【0001】 本発明は、連想メモリに関し、特に、連想メモリに保存される参照データの次元数および個数を拡縮する技術に関する。 【背景技術】 【0002】 近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをＬＳＩ（Large Scale Integrated Circuit）上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。 【0003】 パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。 【0004】 前者は、ＣＡＭ（Content Addressable Memory）と呼ばれ、ネットワークルータのＩＰアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ（Associative Memory）と呼ぶ。 【0005】 連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている（非特許文献１参照）。 【先行技術文献】 【0006】 【非特許文献1】S.Sasaki et al., "Digital Associative Memory for Word-Parallel Manhattan-Distance-Based Vector Quantization," ESSCIRC'2012, 2012, pp.185-188 【発明の概要】 【発明が解決しようとする課題】 【0007】 本願発明者は、これまでに、検索に係るクロックカウント数を削減する機構（有効ビット設定部）とユークリッド距離検索のための二乗計算回路（距離演算回路）とを備えたクロックカウント式の連想メモリを発明し、特願２０１３－０２５４６５において開示した。これにより、データ規模が増大しても高速な検索が可能なユークリッド／マンハッタン距離検索連想メモリをエラーフリー、高電力効率に実現した。 【0008】 連想メモリが利用される分野として、コードブックベース画像圧縮のデータ検索やＢｏＷ（Bag of Words）などが挙げられる。前者では比較的少ない次元数の大量の参照データの検索が行われ、後者では膨大な次元数の少量の参照データの検索が行われる。しかし、従来の連想メモリでは回路構成が固定されているため、アプリケーションに応じて参照データの次元数および個数を拡縮することが困難である。 【0009】 上記問題に鑑み、本発明は、参照データの次元数および個数の拡縮が可能な連想メモリを提供することを目的とする。 【課題を解決するための手段】 【0010】 本発明の一局面に従った再構成可能連想メモリは、それぞれが、参照データを保存する参照データ保存回路と、検索データと前記参照データ保存回路に保存されている前記参照データとの距離を計算する距離計算回路と、トリガー信号を受けてクロック信号のカウント動作を開始し、前記距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する距離／クロック数変換回路とを有する、複数のエレメント回路と、前記複数のエレメント回路のそれぞれに対応して設けられ、それぞれが、与えられた回路構成信号に応じて、前段のエレメント回路から出力される前記マッチ信号を次段のエレメント回路に前記トリガー信号として供給するか否かを制御する、複数のスイッチ回路とを備え、前記スイッチ回路でカスケード接続された複数の前記エレメント回路によって、個別の参照データを保存し、当該参照データと前記検索データとの距離を計算し、当該距離に応じたクロック数をカウントしたタイミングを示すマッチ信号を出力する個別の参照データ検索回路が構成されるものである。 【0011】 これによると、複数のスイッチ回路のそれぞれを適宜制御することにより、エレメント回路の接続形態を任意に変更して、任意の次元数の参照データを保存する任意の個数の参照データ検索回路を構成することができる。 【0012】 複数の前記スイッチ回路がカスケード接続されていてもよく、前記カスケード接続された複数の前記スイッチ回路によって、複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号の論理和を演算する論理和演算回路、および複数の前記参照データ検索回路のそれぞれから出力される前記マッチ信号を保存するシフトレジスタが構成されてもよい。 【0013】 これによると、各エレメント回路から出力されるマッチ信号をまとめて信号本数を減らすことができる。 【0014】 さらに、上記の再構成可能連想メモリは、前記シフトレジスタのシフト出力を参照して前記シフトレジスタに保存されている前記マッチ信号の出力元の参照データ検索回路を特定し、当該特定した参照データ検索回路を識別する信号を出力するＷｉｎｎｅｒ検出回路を備えていてもよい。 【0015】 また、上記の再構成可能連想メモリは、回路構成情報を記憶し、当該回路構成情報に基づいて前記複数のスイッチ回路のそれぞれに前記回路構成信号を出力する回路構成情報記憶回路を備えていてもよい。 【0016】 これによると、回路構成情報記録回路の記憶内容を書き換えるだけで、再構成可能連想メモリを任意に再構成することができる。 【0017】 なお、前記回路構成情報記憶回路は、例えば、不揮発性メモリで構成することができる。 【発明の効果】 【0018】 本発明によると、連想メモリにおいて参照データの次元数および個数を拡縮することができる。これにより、アプリケーションに応じて再構成可能連想メモリを最適に再構成して、再構成可能連想メモリに割り当てられたリソースを最大限利用することができる。 【図面の簡単な説明】 【0019】 【図1】一例に係るクロックカウント式連想メモリの概略構成図 【図2】一例に係る距離／クロック数変換回路の概略構成図 【図3】一例に係るカウンタ一致検出回路の概略構成図 【図4】Ｗｉｎｎｅｒ検出回路の動作を説明するための図 【図5】本発明に係る再構成可能連想メモリのある再構成例を示す図 【図6】本発明に係る再構成可能連想メモリの別の再構成例を示す図 【図7】本発明に係る再構成可能連想メモリのさらに別の再構成例を示す図 【図8】本発明の一実施形態に係る再構成可能連想メモリのメモリアレイ部の概略構成図 【図9】一例に係るスイッチ回路の回路構成図 【図10】本発明の一実施形態に係る再構成可能連想メモリにおけるＷｉｎｎｅｒ検出回路およびその入力部分の一構成例を示す図 【発明を実施するための形態】 【0020】 以下、図面を参照しながら本発明を実施するための形態について説明する。なお、本発明は、以下の実施形態に限定されるものではない。 【0021】 ≪クロックカウント式連想メモリの基本構成例≫ まず、本発明に係る再構成可能連想メモリの前提となるクロックカウント式連想メモリの基本構成について説明する。 【0022】 図１は、一例に係るクロックカウント式連想メモリの概略構成を示す。一例に係るクロックカウント式連想メモリは、メモリアレイ部１０と、Ｗｉｎｎｅｒ検出回路２０とを備える。 【0023】 メモリアレイ部１０は、メモリ部１１、行デコーダ１２、列デコーダ１３、読出／書込回路１４、および検索データ保存回路１５を含む。 【0024】 メモリ部１１は、参照データ保存回路（Storage Cell：ＳＣ）ＳＣ１１～ＳＣ１Ｗ，ＳＣ２１～ＳＣ２Ｗ，…，ＳＣＲ１～ＳＣＲＷと、距離演算回路（絶対値差演算回路）（Distance Processor：ＤＰ）ＤＰ１１～ＤＰ１Ｗ，ＤＰ２１～ＤＰ２Ｗ，…，ＤＰＲ１～ＤＰＲＷと、距離／クロック数変換回路ＤＣ１～ＤＣＲとを含む。なお、ＷおよびＲは、それぞれ、２以上の整数である。 【0025】 距離演算回路ＤＰ１１～ＤＰ１Ｗは、それぞれ、参照データ保存回路ＳＣ１１～ＳＣ１Ｗに対応して設けられる。また、距離演算回路ＤＰ２１～ＤＰ２Ｗは、それぞれ、参照データ保存回路ＳＣ２１～ＳＣ２Ｗに対応して設けられる。以下、同様にして、距離演算回路ＤＰＲ１～ＤＰＲＷは、それぞれ、参照データ保存回路ＳＣＲ１～ＳＣＲＷに対応して設けられる。 【0026】 距離／クロック数変換回路ＤＣ１は、距離演算回路ＤＰ１１～ＤＰ１Ｗに対応して設けられる。距離／クロック数変換回路ＤＣ２は、距離演算回路ＤＰ２１～ＤＰ２Ｗに対応して設けられる。以下、同様にして、距離／クロック数変換回路ＤＣＲは、距離演算回路ＤＰＲ１～ＤＰＲＷに対応して設けられる。 【0027】 参照データ保存回路ＳＣ１１～ＳＣ１Ｗ，ＳＣ２１～ＳＣ２Ｗ，…，ＳＣＲ１～ＳＣＲＷは、行デコーダ１２、列デコーダ１３、および読出／書込回路１４によって書き込まれた参照データを保存する。この場合、参照データ保存回路ＳＣ１１～ＳＣ１Ｗは、Ｍ×Ｗ（Ｍは１以上の整数）ビットの参照データ１を保存し、参照データ保存回路ＳＣ２１～ＳＣ２Ｗは、Ｍ×Ｗビットの参照データ２を保存し、以下、同様にして、参照データ保存回路ＳＣＲ１～ＳＣＲＷは、Ｍ×Ｗビットの参照データＲを保存する。つまり、参照データ保存回路ＳＣ１１～ＳＣ１Ｗ，ＳＣ２１～ＳＣ２Ｗ，…，ＳＣＲ１～ＳＣＲＷのそれぞれは、参照データのＭ×Ｗビットを保存する。 【0028】 距離演算回路ＤＰ１１～ＤＰ１Ｗは、参照データ保存回路ＳＣ１１～ＳＣ１Ｗに保存されたＭ×Ｗビットの参照データ１と、検索データ保存回路１５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。また、距離演算回路ＤＰ２１～ＤＰ２Ｗは、参照データ保存回路ＳＣ２１～ＳＣ２Ｗに保存されたＭ×Ｗビットの参照データ２と、検索データ保存回路１５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。以下、同様にして、距離演算回路ＤＰＲ１～ＤＰＲＷは、参照データ保存回路ＳＣＲ１～ＳＣＲＷに保存されたＭ×Ｗビットの参照データＲと、検索データ保存回路１５に保存されたＭ×Ｗビットの検索データとの距離を後述する方法によって演算する。そして、距離演算回路ＤＰ１１～ＤＰ１Ｗ、距離演算回路ＤＰ２１～ＤＰ２Ｗ、…、距離演算回路ＤＰＲ１～ＤＰＲＷにおける参照データと検索データとの距離の演算は、並列に行われる。 【0029】 そして、距離演算回路ＤＰ１１～ＤＰ１Ｗは、参照データ１と検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣ１へ出力する。距離演算回路ＤＰ２１～ＤＰ２Ｗは、参照データ２と検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣ２へ出力する。以下、同様にして、距離演算回路ＤＰＲ１～ＤＰＲＷは、参照データＲと検索データとの距離をＭ×Ｗビットの距離信号として距離／クロック数変換回路ＤＣＲへ出力する。 【0030】 距離演算回路ＤＰ１１～ＤＰ１Ｗのそれぞれは、参照データ１と検索データとの距離を次式を用いて演算する。 【0031】 【数1】 【0032】 式（１）において、Ｄｒｊ（ｒ＝１～Ｒ，ｊ＝１～Ｗ）は、参照データと検索データとの距離（絶対値差）を表す。ｎＭｒは、参照データと検索データとのマンハッタン距離を示している。また、式(１)において、Ｉｎｊは、検索データであり、Ｒｅｒｊは、参照データである。各データＩｎｊ、Ｒｅｒｊは、それぞれ、Ｍビットからなる。 【0033】 このように、距離演算回路ＤＰ１１～ＤＰ１Ｗは、Ｍ×Ｗビットの参照データ１と、Ｍ×Ｗビットの検索データとの距離をＭビットずつ演算し、それぞれがＭビットのビット長を有するＷ個の距離信号Ｄ１ｊを距離／クロック数変換回路ＤＣ１へ出力する。 【0034】 距離演算回路ＤＰ２１～ＤＰ２Ｗ、…および距離演算回路ＤＰＲ１～ＤＰＲＷも、同様にして、それぞれ、式（１）を用いて参照データ２～Ｒと検索データとの距離を演算する。そして、距離演算回路ＤＰ２１～ＤＰ２Ｗ、…および距離演算回路ＤＰＲ１～ＤＰＲＷも、それぞれがＭビットのビット長を有するＷ個の距離信号Ｄ２ｊ～ＤＲｊをそれぞれ距離／クロック数変換回路ＤＣ２～ＤＣＲへ出力する。 【0035】 距離／クロック数変換回路ＤＣ１は、距離演算回路ＤＰ１１～ＤＰ１ＷからＷ個の距離信号Ｄ１ｊを受け、各距離信号Ｄ１ｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌ１を後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌ１をカウントしたタイミングを示すマッチ信号Ｍ１を出力する。 【0036】 距離／クロック数変換回路ＤＣ２は、距離演算回路ＤＰ２１～ＤＰ２ＷからＷ個の距離信号Ｄ２ｊを受け、各距離信号Ｄ２ｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌ２を後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌ２をカウントしたタイミングを示すマッチ信号Ｍ２を出力する。 【0037】 以下、同様にして、距離／クロック数変換回路ＤＣＲは、距離演算回路ＤＰＲ１～ＤＰＲＷからＷ個の距離信号ＤＲｊを受け、各距離信号ＤＲｊの二乗値の和に相当するクロック信号ＣＬＫのクロック数ＣＮ＿ｔｏｔａｌＲを後述する方法によってカウントする。そして、そのクロック数ＣＮ＿ｔｏｔａｌＲをカウントしたタイミングを示すマッチ信号ＭＲを出力する。 【0038】 行デコーダ１２は、メモリ部１１の行方向のアドレスを指定する。列デコーダ１３は、メモリ部１１の列方向のアドレスを指定する。読出／書込回路１４は、参照データを行デコーダ１２および列デコーダ１３によって指定された参照データ保存回路ＳＣ１１～ＳＣ１Ｗ，ＳＣ２１～ＳＣ２Ｗ，…，ＳＣＲ１～ＳＣＲＷに書き込むとともに、検索データを検索データ保存回路１５に書き込む。 【0039】 検索データ保存回路１５は、読出／書込回路１４によって書き込まれた検索データ（Ｍ×Ｗビットのデータ）を保存する。 【0040】 Ｗｉｎｎｅｒ検出回路２０は、マッチ信号Ｍ１～ＭＲをそれぞれ距離／クロック数変換回路ＤＣ１～ＤＣＲから受ける。そして、その受けたマッチ信号Ｍ１～ＭＲのうち、一致タイミングが早い順にｋ（ｋは１≦ｋ＜Ｒを満たす整数）個のマッチ信号を検出する。 【0041】 図２は、一例に係る距離／クロック数変換回路ＤＣ１の概略構成を示す。なお、距離／クロック数変換回路ＤＣ２～ＤＣＲのそれぞれも、図２に示す距離／クロック数変換回路ＤＣ１と同様の構成を有する。距離／クロック数変換回路ＤＣ１は、バッファ１２１～１２Ｗと、カウンタ一致検出回路１３１～１３Ｗとを含む。 【0042】 バッファ１２１は、クロックカウント式連想メモリの制御回路（図示せず）から検索開始信号ＳＢを受け、クロックカウント式連想メモリに内蔵されたクロック発生回路（図示せず）からクロック信号ＣＬＫを受ける。そして、バッファ１２１は、検索開始信号ＳＢがＬレベルからＨレベルに遷移すると、その受けたクロック信号ＣＬＫをバッファ１２２およびカウンタ一致検出回路１３１へ出力する。バッファ１２２は、クロック信号ＣＬＫをバッファ１２１から受け、カウンタ一致検出回路１３１から、後述するＨレベルの一致信号（ＤＥＴＥＣＴ１）を受けると、クロック信号ＣＬＫをバッファ１２３（図示せず）およびカウンタ一致検出回路１３２へ出力する。以下、同様にして、バッファ１２Ｗは、クロック信号ＣＬＫをバッファ１２Ｗ－１（図示せず）から受け、カウンタ一致検出回路１３Ｗ－１（図示せず）から、後述するＨレベルの一致信号（ＤＥＴＥＣＴＷ－１）を受けると、クロック信号ＣＬＫをカウンタ一致検出回路１３Ｗへ出力する。 【0043】 カウンタ一致検出回路１３１～１３Ｗは、それぞれ、距離演算回路ＤＰ１１～ＤＰ１Ｗに対応して設けられる。そして、カウンタ一致検出回路１３１～１３Ｗは、直列に接続される。ここで、カウンタ一致検出回路１３１～１３Ｗの概略構成について説明する。 【0044】 図３は、一例に係るカウンタ一致検出回路１３１～１３Ｗの概略構成を示す。本例は、Ｗ＝２の場合を示している。カウンタ一致検出回路１３１は、クロック数変換回路１３１ａと、カウンタ１３１ｂと、一致検出回路１３１ｃとを含む。カウンタ一致検出回路１３２は、クロック数変換回路１３２ａと、カウンタ１３２ｂと、一致検出回路１３２ｃとを含む。以下、各構成の機能について説明する。 【0045】 クロック数変換回路１３１ａは、距離演算回路ＤＰ１１からＭビットのビット長を有する距離信号Ｄ１１と、バッファ１２１からのクロック信号ＣＬＫとを受ける。クロック数変換回路１３１ａは、クロック信号ＣＬＫのクロック数をカウントし、距離信号Ｄ１１が示す距離と一致するクロック数を検出したタイミングで、カウンタ１３１ｂにＨレベルの一致検出信号を出力する処理を行う。クロック数変換回路１３１ａは、後述の一致検出回路１３１ｃからＨレベルの一致信号（ＤＥＴＥＣＴ１）が出力されるまで、この処理を繰り返し行い、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力されると動作を停止する。 【0046】 カウンタ１３１ｂは、クロック数変換回路１３１ａからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウント値を一致検出回路１３１ｃへ出力する。 【0047】 一致検出回路１３１ｃは、カウンタ１３１ｂからカウンタ値を受け、距離演算回路ＤＰ１１からＭビットのビット長を有する距離信号Ｄ１１を受ける。一致検出回路１３１ｃは、距離信号Ｄ１１が示す距離とカウンタ値とを比較し、距離信号Ｄ１１が示す距離とカウンタ値とが一致するときに、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）をクロック数変換回路１３１ａとバッファ１２２へ出力する。一致検出回路１３１ｃは、距離信号Ｄ１１が示す距離とカウンタ値とが一致しないときは、Ｌレベルの一致信号（ＤＥＴＥＣＴ１）をクロック数変換回路１３１ａとバッファ１２２へ出力する。 【0048】 クロック数変換回路１３２ａは、バッファ１２２からクロック信号ＣＬＫを受けると駆動する。クロック数変換回路１３２ａは、距離演算回路ＤＰ１２からＭビットのビット長を有する距離信号Ｄ１２を受ける。クロック数変換回路１３１ａと同様、クロック数変換回路１３２ａは、クロック信号ＣＬＫのクロック数をカウントし、距離信号Ｄ１２が示す距離と一致するクロック数を検出したタイミングで、カウンタ１３２ｂにＨレベルの一致検出信号を出力する処理を行う。クロック数変換回路１３２ａは、後述の一致検出回路１３２ｃからＨレベルの一致信号（ＤＥＴＥＣＴ２）が出力されるまで、この処理を繰り返し行う。クロック数変換回路１３２ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）が出力されると動作を停止する。 【0049】 カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がるごとにカウンタ値をカウントアップさせ、そのカウント値を一致検出回路１３２ｃへ出力する。 【0050】 一致検出回路１３２ｃは、カウンタ１３２ｂからカウンタ値を受け、距離演算回路ＤＰ１２からＭビットのビット長を有する距離信号Ｄ１２を受ける。一致検出回路１３２ｃは、距離信号Ｄ１２が示す距離とカウンタ値とを比較し、距離信号Ｄ１２が示す距離とカウンタ値とが一致するときに、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路１３２ａとバッファ１２２へ出力するとともに、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をマッチ信号Ｍ１としてＷｉｎｎｅｒ検出回路２０へ出力する。また、一致検出回路１３２ｃは、距離信号Ｄ１２が示す距離とカウンタ値とが一致しないときは、Ｌレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路１３２ａに出力する。 【0051】 ここで、例えば、距離演算回路ＤＰ１１から距離「２」を示すＭビットの距離信号Ｄ１１が出力され、距離演算回路ＤＰ１２から距離「３」を示すＭビットの距離信号Ｄ１２が出力された場合の動作例について説明する。 【0052】 クロック数変換回路１３１ａは、距離「２」を示すＭビットの距離信号Ｄ１１を受け、バッファ１２１からのクロック信号ＣＬＫのクロックに同期して、距離「２」に一致するクロック数をカウントする。クロック数変換回路１３１ａは、カウントしたクロック数と距離とが一致すると、Ｈレベルの一致検出信号を出力する。カウンタ１３１ｂは、一致検出信号が立ち上がると、カウント値をカウントアップし、「１」を示すカウンタ値を一致検出回路１３１ｃに出力する。このとき、距離信号Ｄ１１が示す距離「２」とカウント値「１」とが一致しないため、一致検出回路１３１ｃからＬレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。 【0053】 クロック数変換回路１３１ａは、出力した一致検出信号がＬレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路１３１ａは、再びクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数が距離「２」と一致すると、カウンタ１３１ｂにＨレベルの一致検出信号を出力する。カウンタ１３１ｂは、一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３１ｃに「２」を示すカウンタ値を出力する。一致検出回路１３１ｃは、距離信号Ｄ１１が示す距離「２」とカウンタ値「２」とが一致するため、一致信号（ＤＥＴＥＣＴ１）をバッファ１２２とクロック数変換回路１３１ａに出力する。つまり、検索開始からのクロック数が「４」となるタイミングで、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）が出力される。そして、クロック数変換回路１３１ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ１）に応じて動作を停止する。 【0054】 バッファ１２２は、一致検出回路１３１ｃからＨレベルの一致信号（ＤＥＴＥＣＴ１）を受けて、クロック数変換回路１３２ａにクロック信号ＣＬＫを出力する。クロック数変換回路１３２ａは、バッファ１２２からのクロック信号ＣＬＫのクロックに同期して、クロック信号ＣＬＫのクロック数をカウントする。クロック数変換回路１３２ａは、距離「３」を示すＭビットの距離信号Ｄ１２を受け、カウントしたクロック数が距離「３」と一致するタイミングで、Ｈレベルの一致検出信号をカウンタ１３２ｂに出力する。カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３２ｃに「１」を示すカウンタ値を出力する。このとき、距離「３」とカウンタ値「１」とが一致しないため、一致検出回路１３２ｃからＬレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。 【0055】 クロック数変換回路１３２ａは、出力した一致検出信号がＬレベルになると、カウントしたクロック数をリセットする。そして、クロック数変換回路１３２ａは、再びクロック信号ＣＬＫのクロック数をカウントし、カウントしたクロック数が距離「３」と一致すると、カウンタ１３２ｂにＨレベルの一致検出信号を出力する。カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３２ｃに「２」を示すカウンタ値を出力する。このとき、距離「３」とカウンタ値「２」とが一致しないため、一致検出回路１３２ｃからＬレベルの一致信号（ＤＥＴＥＣＴ２）が出力される。 【0056】 クロック数変換回路１３２ａは、一致検出信号がＬレベルになると、再びカウントしたクロック数をリセットしてクロック信号ＣＬＫをカウントし、カウントしたクロック数が距離「３」と一致すると、カウンタ１３２ｂにＨレベルの一致検出信号を出力する。そして、クロック数変換回路１３２ａは、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）に応じて動作を停止する。カウンタ１３２ｂは、クロック数変換回路１３２ａからの一致検出信号が立ち上がると、カウンタ値をカウントアップさせ、一致検出回路１３２ｃに「３」を示すカウンタ値を出力する。一致検出回路１３２ｃは、距離「３」とカウント値「３」とが一致するため、Ｈレベルの一致信号（ＤＥＴＥＣＴ２）をクロック数変換回路１３２ａに出力するとともに、マッチ信号Ｍ１としてＷｉｎｎｅｒ検出回路２０に出力する。つまり、クロック数変換回路１３２ａにおいてカウントされたクロック数は「９（＝３＋３＋３）」であり、検索開始からクロック数「１３（＝４＋９）」のタイミングでマッチ信号Ｍ１が出力される。 【0057】 カウンタ一致検出回路１３１，１３２全体でカウントされるクロック数ＣＮ＿ｔｏｔａｌ１「１３」は、カウンタ一致検出回路１３１においてカウントするクロック数「４（＝２＋２）」と、カウンタ一致検出回路１３２においてカウントするクロック数「９（＝３＋３＋３）」とを加算したものである。つまり、カウンタ一致検出回路１３１，１３２によって、距離「２」の二乗値と距離「３」の二乗値との和に一致するクロック数をカウントすることに相当する。 【0058】 距離／クロック数変換回路ＤＣ１は、一般的に、Ｗ個の距離信号Ｄ１１～Ｄ１Ｗを受ける。そして、Ｗ個の距離信号Ｄ１１～Ｄ１Ｗのそれぞれは、Ｍビットのビット長を有する。したがって、距離／クロック数変換回路ＤＣ１は、Ｍ×Ｗビットのビット長を有する距離信号Ｄ１１Ｄ１２…Ｄ１Ｗを受ける。カウンタ一致検出回路１３１において、距離信号Ｄ１１が示す距離に一致する回数分だけ、その距離に一致するクロック数を繰り返しカウントする。また、カウンタ一致検出回路１３２～１３Ｗは、それぞれ、カウンタ一致検出回路１３１～１３Ｗ－１から一致信号を受けた後に、距離信号Ｄ１２～Ｄ１Ｗにそれぞれ一致するクロック数を、その距離に一致する回数だけ繰り返しカウントする。その結果、距離／クロック数変換回路ＤＣ１においてカウントされる全体のクロック数ＣＮ＿ｔｏｔａｌ１は、カウンタ一致検出回路１３１～１３Ｗのそれぞれにおいてカウントされたクロック数の和に等しい。カウンタ一致検出回路１３１～１３Ｗのそれぞれにおいてカウントされたクロック数は、それぞれ、距離信号Ｄ１１～Ｄ１Ｗが示す各距離の二乗値に相当するため、距離／クロック数変換回路ＤＣ１においてカウントされる全体のクロック数ＣＮ＿ｔｏｔａｌＲは、各距離信号Ｄ１１～Ｄ１Ｗの二乗値の和を表している。 【0059】 ここで、ユークリッド距離ｎＥｒは、次式によって表される。 【0060】 【数2】 【0061】 式（２）の右辺の｜Ｉｎｊ－Ｒｅｒｊ｜２は、式（１）の右辺の｜Ｉｎｊ－Ｒｅｒｊ｜において、検索データと参照データとの距離の二乗値に一致する。したがって、ユークリッド距離ｎＥｒの演算は、上述したように、式（１）によって演算したＷ個の各距離について、距離に一致するクロック数をカウントする処理を距離に一致する回数だけ繰り返し行うことで実現される。そうすると、図３の例において、カウンタ一致検出回路１３２が、カウンタ一致検出回路１３１，１３２全体でカウントしたクロック数のタイミングを示すマッチ信号Ｍ１を出力することは、ユークリッド距離ｎＥｒによって検索データに類似する参照データを検索し、検索データに類似する参照データを検出したことを示す信号を出力することに相当する。なお、距離／クロック数変換回路ＤＣ２～ＤＣＲのそれぞれも、距離／クロック数変換回路ＤＣ１の動作と同じ動作によって、それぞれ、マッチ信号Ｍ２～ＭＲを出力する。 【0062】 次に、Ｗｉｎｎｅｒ検出回路２０の動作について説明する。図４は、Ｗｉｎｎｅｒ検出回路２０の動作を説明するための図である。距離／クロック数変換回路ＤＣ１～ＤＣＲは、図４に示すように、例えばマッチ信号Ｍ１～ＭＲをそれぞれクロック信号ＣＬＫに同期してＷｉｎｎｅｒ検出回路２０へ出力する。 【0063】 Ｗｉｎｎｅｒ検出回路２０は、マッチ信号Ｍ１～ＭＲを受け、その受けたマッチ信号Ｍ１～ＭＲの立ち上がりタイミングｔ１～ｔＲを検出する。そして、Ｗｉｎｎｅｒ検出回路２０は、タイミングｔ１～ｔＲが早い順にｋ個のマッチ信号を検出する。 【0064】 ≪再構成可能連想メモリの構成例≫ 次に、本発明に係る再構成可能連想メモリについて説明する。本発明に係る再構成可能連想メモリは、例えば上記構成のクロックカウント式連想メモリにおいて参照データの次元数および個数を任意に拡縮できるように構成したものである。図５、図６、および図７は、本発明に係る再構成可能連想メモリのさまざまな再構成例を示す。 【0065】 再構成可能連想メモリ１００におけるメモリアレイ部１０において、複数のエレメント回路３０がＲ行×Ｃ列（ただし、Ｒ，Ｃはいずれも２以上の整数である。）のマトリクス状に配置されている。なお、便宜のため、以下では、再構成可能連想メモリ１００におけるメモリアレイ部１０において４行×４列の計１６個のエレメント回路３０がマトリクス状に配置されているものとして説明する。また、行デコーダ２、列デコーダ３、読出／書込回路４、検索データ保存回路５などの周辺回路の図示は省略する。 【0066】 各エレメント回路３０は、１組以上の上記の参照データ保存回路ＳＣおよび距離計算回路ＤＰの対応するペア、ならびにそれら距離計算回路ＤＣから出力される距離信号が入力される上記の距離／クロック数変換回路ＤＣを含む。各エレメント回路３０から出力されるＭＮ（Match Next）信号は、各エレメント回路３０における距離／クロック数変換回路ＤＣから出力されるマッチ信号に相当する。すなわち、各エレメント回路３０は、Ｑ次元（Ｑは２以上の整数）の参照データを保存し、当該Ｑ次元の参照データとＱ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）を出力する。 【0067】 後述する図示しないスイッチ回路によってエレメント回路３０どうしが任意に接続および切断可能となっている。エレメント回路３０どうしが接続された場合、前段のエレメント回路３０から出力されるＭＮ信号は、次段のエレメント回路３０における距離／クロック数変換回路ＤＣのトリガー信号として次段のエレメント回路３０に供給される。 【0068】 図５の再構成例では、図示しないスイッチ回路によって４個のエレメント回路３０がカスケード接続されて４個の参照データ検索回路４０が構成されている。図５の再構成例において、４個の参照データ検索回路４０は、それぞれ、４Ｑ次元の参照データを保存し、当該４Ｑ次元の参照データと４Ｑ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）をＷｉｎｎｅｒ検出回路２０へ出力する。 【0069】 図６の再構成例では、図示しないスイッチ回路によって２個のエレメント回路３０がカスケード接続されて８個の参照データ検索回路４０が構成されている。図６の再構成例において、８個の参照データ検索回路４０は、それぞれ、２Ｑ次元の参照データを保存し、当該２Ｑ次元の参照データと２Ｑ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）をＷｉｎｎｅｒ検出回路２０へ出力する。すなわち、図６の再構成例は、図５の再構成例に対して、参照データの次元数を半分にする代わりに個数を倍にしたものである。 【0070】 図７の再構成例では、図示しないスイッチ回路によって８個のエレメント回路３０がカスケード接続されて２個の参照データ検索回路４０が構成されている。図７の再構成例において、２個の参照データ検索回路４０は、それぞれ、８Ｑ次元の参照データを保存し、当該８Ｑ次元の参照データと８Ｑ次元の検索データとの距離を計算し、その距離に応じたクロック数をカウントしたタイミングを示すマッチ信号（ＭＮ信号）をＷｉｎｎｅｒ検出回路２０へ出力する。すなわち、図７の再構成例は、図５の再構成例に対して、参照データの個数を半分にする代わりに次元数を倍にしたものである。 【0071】 ≪再構成可能連想メモリの実施形態≫ 次に、本発明の一実施形態に係る再構成可能連想メモリについて説明する。図８は、本発明の一実施形態に係る再構成可能連想メモリ１００のメモリアレイ部１０の概略構成を示す。各エレメント回路３０に対応してスイッチ回路５０が設けられており、上述したように、スイッチ回路５０によってエレメント回路３０どうしが任意に接続および切断可能となっている。各スイッチ回路５０がエレメント回路３０どうしを接続するか否かは、各スイッチ回路５０に入力される回路構成信号ＳＲによって決まる。 【0072】 各スイッチ回路５０に入力される回路構成信号ＳＲは、メモリ（回路構成情報記憶回路）６０に記憶されている。メモリ６０は、ＳＲＡＭ（Static Random Access Memory）、フラッシュメモリ、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）などの不揮発性メモリやシフトレジスタなどで構成することができる。メモリ６０の記憶内容を書き換えるだけで、再構成可能連想メモリ１００を任意に再構成することができる。 【0073】 原理的には、再構成可能連想メモリ１００において、１個のエレメント回路３０で１個の参照データ検索回路４０を構成することで、参照データの個数が最大となる再構成が可能である。そのような再構成に対応可能にするためには、各エレメント回路３０から出力されるＭＮ信号をＷｉｎｎｅｒ検出回路２０へ接続しなければならない。しかし、そのような回路構成は、エレメント回路３０の個数が増えるとＷｉｎｎｅｒ検出回路２０へ接続するＭＮ信号の信号線もその分だけ増えるため、エレメント回路３０の個数が数十個以上になると信号線のレイアウトが非常に困難になってくる。そこで、本実施形態では、メモリアレイ部１０において同じ行に配置された各エレメント回路３０から出力されるＭＮ信号の論理和を演算し、その論理和であるＭＯＲ（Match OR）信号をＷｉｎｎｅｒ検出回路２０へ入力する。これにより、Ｗｉｎｎｅｒ検出回路２０に接続すべき信号線をＲ本（マトリクスの行数）にまで削減することができる。また、各参照データ検索回路４０から出力されるＭＮ信号がＭＯＲ信号としてまとめられると、いずれの参照データ検索回路４０からＭＮ信号が出力されたのかが判別できなくなるため、後述するように、本実施形態では、各参照データ検索回路４０から出力されるＭＮ信号を保存するシフトレジスタを構成し、そのシフトレジスタの出力であるＳＨＭ（Shift Match）信号をＷｉｎｎｅｒ検出回路２０へ入力する。 【0074】 図９は、スイッチ回路５０の回路構成例を示す。スイッチ回路５０は、例えば、図９（Ａ）、図９（Ｂ）、および図９（Ｃ）に示した３つの回路を備えている。 【0075】 図９（Ａ）において、マルチプレクサ（ＭＵＸ）５１は、検索開始信号ＳＢが入力ｉｎ０として、前段のエレメント回路３０から出力されるＭＮ信号（ＭＮｉｎ）が入力ｉｎ１としてそれぞれ与えられ、回路構成信号ＳＲによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。ＭＵＸ５１から出力されるＭＮ信号（ＭＮｏｕｔ）は、次段のエレメント回路３０における距離／クロック数変換回路ＤＣのトリガー信号となる。具体的には、ＭＵＸ５１は、回路構成信号ＳＲがＨレベル（ＳＲ＝１）のとき、ｉｎ１を出力する。この場合、前段のエレメント回路３０における距離／クロック数変換回路ＤＣから出力されるマッチ信号（ＭＮ信号）が次段のエレメント回路３０における距離／クロック数変換回路ＤＣのトリガー信号として供給される。一方、ＭＵＸ５１は、回路構成信号ＳＲがＬレベル（ＳＲ＝０）のとき、ｉｎ０を出力する。この場合、次段のエレメント回路３０における距離／クロック数変換回路ＤＣに検索開始信号ＳＢが供給される。すなわち、この場合の次段のエレメント回路３０は、参照データ検索回路４０における初段のエレメント回路３０に相当する。 【0076】 図９（Ｂ）において、ＯＲゲート５３は、前段のスイッチ回路５０から出力されるＭＯＲ信号（ＭＯＲｉｎ）と前段のエレメント回路３０から出力されるＭＮ信号（ＭＮｉｎ）が入力され、これら信号の論理和を出力する。ＭＵＸ５２は、ＯＲゲート５３の出力が入力ｉｎ０として、前段のスイッチ回路５０から出力されるＭＯＲ信号（ＭＯＲｉｎ）が入力ｉｎ１としてそれぞれ与えられ、回路構成信号ＳＲによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。ＭＵＸ５２から出力されるＭＯＲ信号（ＭＯＲｏｕｔ）は、次段のスイッチ回路５０またはＷｉｎｎｅｒ検出回路２０へ供給される。また、Ｌレベルの回路構成信号ＳＲが入力された複数のスイッチ回路５０がカスケード接続されることで、各スイッチ回路５０におけるＯＲゲート５３がカスケード接続される。そして、カスケード接続されたＯＲゲート５３によって、複数のデータ検索回路４０から出力されるＭＮ信号の論理和を演算する論理和演算回路が構成される。 【0077】 図９（Ｃ）において、ＭＵＸ５４は、前段のエレメント回路３０から出力されるＭＮ信号（ＭＮｉｎ）が入力ｉｎ０として、前段のスイッチ回路５０から出力されるＳＨＭ信号（ＳＨＭｉｎ）が入力ｉｎ１としてそれぞれ与えられ、検索終了遅延信号ＳＥＬ（Search End Lag）によってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。検索終了遅延信号ＳＥＬは、再構成可能連想メモリ１００における検索終了時に出力される検索終了信号ＳＥ（Search End）を遅延させた信号である。ＭＵＸ５４から出力される信号は、Ｄフリップフロップ（ＤＦＦ）５６にデータ入力される。具体的には、ＭＵＸ５４は、検索終了遅延信号ＳＥＬがＬレベル（ＳＥＬ＝０）のとき、すなわち、検索終了前において、ｉｎ０を出力する。この場合、前段のエレメント回路３０における距離／クロック数変換回路ＤＣから出力されるマッチ信号（ＭＮ信号）がＤＦＦ５６にデータ入力される。一方、ＭＵＸ５４は、検索終了遅延信号ＳＥＬがＨレベル（ＳＥＬ＝１）のとき、すなわち、検索終了後において、ｉｎ１を出力する。この場合、前段のスイッチ回路５０から出力されるＳＨＭ信号（ＳＨＭｉｎ）がＤＦＦ５６にデータ入力される。ＭＵＸ５５は、ＤＦＦ５６の出力信号が入力ｉｎ０として、前段のスイッチ回路５０から出力されるＳＨＭ信号（ＳＨＭｉｎ）が入力ｉｎ１としてそれぞれ与えられ、回路構成信号ＳＲによってｉｎ０およびｉｎ１のいずれか一方を選択的に出力する。ＭＵＸ５５から出力されるＳＨＭ信号（ＳＨＭｏｕｔ）は、次段のスイッチ回路５０またはＷｉｎｎｅｒ検出回路２０へ供給される。 【0078】 Ｌレベルの回路構成信号ＳＲが入力された複数のスイッチ回路５０がカスケード接続されることで、各スイッチ回路５０におけるＤＦＦ５６がカスケード接続される。そして、カスケード接続されたＤＦＦ５６によって、複数のデータ検索回路４０から出力されるＭＮ信号を保存するシフトレジスタが構成される。当該シフトレジスタは、検索終了遅延信号ＳＥＬがＬレベルのときはデータ取得モードで、検索終了遅延信号ＳＥＬがＨレベルのときはデータシフトモードでそれぞれ動作する。データ取得モードでは、データ取得信号ＲＥＡＤＷがクロック入力されることで、ＤＦＦ５６は、前段のエレメント回路３０から出力されるＭＮ信号（ＭＮｉｎ）を保存する。データシフトモードでは、シフトクロック信号ＳＨＣＬＫがクロック入力されることで、ＤＦＦ５６は、前段のスイッチ回路５０から出力されるＳＨＭ信号（ＳＨＭｉｎ）をシフトする。なお、ＲＥＡＤＷ信号とＳＨＣＬＫ信号はＯＲゲート５７によってその論理和が演算されてＤＦＦ５６にクロック入力される。 【0079】 ところで、図７のようにメモリアレイ部１０において行を跨いでエレメント回路をカスケード接続して参照データ検索回路４０を構成する場合、メモリアレイ部１０の各行の最終端に配置されたスイッチ回路５０から出力されるＳＨＭ信号およびＭＯＲ信号がＷｉｎｎｅｒ検出回路２０へ入力されないようにする必要がある。以下、それを実現する構成について説明する。 【0080】 図１０は、再構成可能連想メモリ１００におけるＷｉｎｎｅｒ検出回路２０およびその入力部分の一構成例を示す。図１０に示したスイッチ回路５０は、メモリアレイ部１０の各行の最終端に配置されたスイッチ回路５０である。各スイッチ回路５０から出力されるＳＨＭ信号およびＭＯＲ信号は、各スイッチ回路５０に入力される回路構成信号ＳＲによってマスクされる。具体的には、ＡＮＤゲート５８は、ＳＨＭ信号と回路構成信号ＳＲの反転信号との論理積を演算し、ＳＨＭ’信号としてＷｉｎｎｅｒ検出回路２０へ供給する。また、ＡＮＤゲート５９は、ＭＯＲ信号と回路構成信号ＳＲの反転信号との論理積を演算し、ＭＯＲ’信号としてＷｉｎｎｅｒ検出回路２０へ供給する。すなわち、ＳＲ＝１のとき、行を跨いでエレメント回路３０どうしがカスケード接続されるため、回路構成信号ＳＲの反転信号によってスイッチ回路５０から出力されるＳＨＭ信号およびＭＯＲ信号がマスクされてＳＨＭ’＝０、ＭＯＲ’＝０となり、Ｗｉｎｎｅｒ検出回路２０へＳＨＭ信号およびＭＯＲ信号が供給されない。一方、ＳＲ＝０のとき、行を跨いでエレメント回路３０どうしがカスケード接続されないため、回路構成信号ＳＲの反転信号によってスイッチ回路５０から出力されるＳＨＭ信号およびＭＯＲ信号がマスクされずにそのままＷｉｎｎｅｒ検出回路２０へ供給される。 【0081】 Ｗｉｎｎｅｒ検出回路２０は、メモリアレイ部１０の各行に対応するＳＩＰＯ（直列入力並列出力）型のシフトレジスタ２１を備えている。各シフトレジスタ２１は、ＳＨＭ’信号を受けて、ビット幅ＥＬＮの信号Ｗを出力する。ＥＬＮは、メモリアレイ部１０の各行に配置されたエレメント回路３０の個数である。上述のシフトレジスタがデータシフトモードにあるとき、当該シフトレジスタのシフト出力がＳＨＭ’信号としてシフトレジスタ２１に入力される。そして、シフトレジスタ２１は、上述のシフトレジスタにおけるＤＦＦ２６に保存されたＭＮ信号がシフト入力されるまで、上述のシフトクロック信号ＳＨＣＬＫをカウントする。そして、そのカウント結果を多ビット信号Ｗとして出力する。これにより、メモリアレイ部１０の各行におけるいずれの参照データ検索回路４０からＭＮ信号が出力されたのかを判別することができる。 【0082】 また、各ＭＯＲ’信号は検索終了判定回路７０に入力され、検索終了判定回路７０は入力されたすべてのＭＯＲ’信号の論理和を演算して上述の検索終了信号ＳＥを出力する。すなわち、参照データ検索回路４０のいずれかからＭＮ信号が出力されると、検索終了判定回路７０から検索終了信号ＳＥが出力される。検索終了判定回路７０は、例えば、ＯＲツリーとして構成することができる。 【0083】 以上のように、本実施形態によると、複数のエレメント回路３０をさまざまにつなぎ替えて参照データの次元数および個数を任意に拡縮することができる。これにより、アプリケーションに応じて再構成可能連想メモリ１００を最適に再構成して、再構成可能連想メモリ１００に割り当てられたリソースを最大限利用することができる。 【符号の説明】 【0084】 １００ 再構成可能連想メモリ ２０ Ｗｉｎｎｅｒ検出回路 ３０ エレメント回路 ４０ 参照データ検索回路 ５０ スイッチ回路 ５３ ＯＲゲート（論理和演算回路） ５４ Ｄフリップフロップ（シフトレジスタ） ６０ メモリ（回路構成情報記憶回路） ＳＣ 参照データ保存回路 ＤＰ 距離計算回路 ＤＣ 距離／クロック数変換回路 |
||||||||||
| 図面 |
|