Specification :(In Japanese)最小ユークリッド距離検索連想メモリ装置

Country	(In Japanese)日本国特許庁(JP)
Gazette	(In Japanese)特許公報(B2)
Patent Number	P4892720
Publication number	P2007-080375A
Date of registration	Jan 6, 2012
Date of issue	Mar 7, 2012
Date of publication of application	Mar 29, 2007
Title of the invention, or title of the device	(In Japanese)最小ユークリッド距離検索連想メモリ装置
IPC (International Patent Classification)	G11C  15/04        (2006.01)
FI (File Index)	G11C 15/04 601W G11C 15/04 631F
Number of claims or invention	4
Total pages	12
Application Number	P2005-266250
Date of filing	Sep 14, 2005
Date of request for substantive examination	Jul 18, 2008
Patentee, or owner of utility model right	(In Japanese)【識別番号】504136568 【氏名又は名称】国立大学法人広島大学
Inventor, or creator of device	(In Japanese)【氏名】マタウシュ ハンスユルゲン 【氏名】小出 哲士 【氏名】アベディン モハマド アノワルル
Representative	(In Japanese)【識別番号】100077931、【弁理士】、【氏名又は名称】前田 弘 【識別番号】100094134、【弁理士】、【氏名又は名称】小山 廣毅 【識別番号】100110939、【弁理士】、【氏名又は名称】竹内 宏 【識別番号】100110940、【弁理士】、【氏名又は名称】嶋田 高久 【識別番号】100113262、【弁理士】、【氏名又は名称】竹内 祐二 【識別番号】100115059、【弁理士】、【氏名又は名称】今江 克実 【識別番号】100115691、【弁理士】、【氏名又は名称】藤田 篤史 【識別番号】100117581、【弁理士】、【氏名又は名称】二宮 克也 【識別番号】100117710、【弁理士】、【氏名又は名称】原田 智雄 【識別番号】100121728、【弁理士】、【氏名又は名称】井関 勝守 【識別番号】100124671、【弁理士】、【氏名又は名称】関 啓 【識別番号】100131060、【弁理士】、【氏名又は名称】杉浦 靖也
Examiner	(In Japanese)【審査官】堀江 義隆
Document or reference	(In Japanese)特開2005－242808（JP，A） 特開2005－190429（JP，A） 特開2002－288985（JP，A） 特開平03－283193（JP，A）
Field of search	Ｇ１１Ｃ １５／０４
Scope of claims	(In Japanese)【請求項1】 検索データについて複数の参照データと並列に差の絶対値計算に基づくユークリッド距離の2乗を計算する距離計算回路と、前記ユークリッド距離の2乗の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、 前記検索データおよび参照データがそれぞれkビット（k＞1）単位でユニット化されている場合に、 前記距離計算回路は、 前記参照データをユニット単位で保存するためのW列R行のユニット保存回路と、 ユニット毎に参照データと検索データの差の絶対値計算を行うW列R行のユニット比較回路と、 行毎に前記W列のユニット比較回路で計算された差の絶対値の2乗の和に相当する電流または電圧信号を生成するR行のワード重み比較回路とを備える、 ことを特徴とする最小ユークリッド距離検索連想メモリ装置。 【請求項2】 請求項1において、 前記R行のワード重み比較回路の各々は、 対応する行のユニット比較回路の各々に対応させて電流変換回路とアナログ2乗回路とが設けられており、 前記電流変換回路の各々は、 対応するユニット比較回路から出力されるディジタル信号をアナログ電流に変換するものであり、 前記アナログ2乗回路の各々は、 対応する電流変換回路からの出力電流を2乗して対応する行のマッチラインに出力するものである、 ことを特徴とする最小ユークリッド距離検索連想メモリ。 【請求項3】 請求項1において、 前記R行のワード重み比較回路の各々は、 対応する行のユニット比較回路の各々に対応させてディジタル2乗回路と電流変換回路とが設けれており、 前記ディジタル2乗回路の各々は、 対応するユニット比較回路から出力されるディジタル信号を2乗するものであり、 前記電流変換回路の各々は、 対応するディジタル2乗回路から出力されるディジタル信号をアナログ電流に変換して対応する行のマッチラインに出力するものである、 ことを特徴とする最小ユークリッド距離検索連想メモリ。 【請求項4】 請求項1において、 前記距離計算回路および前記検索回路は半導体集積回路の同一チップ上に形成されている、 ことを特徴とする最小ユークリッド距離検索連想メモリ。
Detailed description of the invention	(In Japanese)【技術分野】 【0001】 本発明は、カラー、グレースケールの画像圧縮、画像認識等の情報処理装置に用いられ、全並列処理による最小ユークリッド距離検索機能を有する連想メモリ装置に関する。 【背景技術】 【0002】 近年、情報処理技術、特に画像圧縮・画像認識の分野においては、最小距離検索機能を持つ連想メモリが注目されている。連想メモリは、知的情報処理で必要となる物体認識のためのパターンマッチングやコードブックと呼ばれるデータ群を利用したデータ圧縮に非常に有効である。連想メモリは、入力されたデータ列（検索データ）に対して連想メモリ内にある複数の参照データ中から最も類似した（距離の近い）データを検索する機能を持つ機能メモリの代表的なものの一つであり、その優れた検索機能により、先に述べた画像圧縮・画像認識などのパターンマッチング機能を有するアプリケーションにおいて、その性能を飛躍的に向上できるものとして期待されている。 【0003】 kビット×Wユニット幅R個の参照データから、入力データと最も似ているデータを見つけることはパターンマッチングにおいて基本的な処理である（非特許文献1）。ゆえに画像圧縮、画像認識などの情報処理には、最小距離検索連想メモリ（特許文献1）は中核を担う部分であるといえる。既存の全並列最小距離検索連想メモリとしては、単純な距離であるマンハッタン、ハミング距離の検索機能を持つものがそれぞれ提案されている。これらの距離は以下の数1で定義される（非特許文献2）。 【0004】 【数1】 【0005】 ここで、SW＝｛SW1，SW2，・・・，SWw｝は入力データ、REF＝｛REF1，REF2，・・・，REFw｝は参照データを表す。SWiとREFiが1ビットの2進数である場合、Dはハミング距離となる。また、SWiとREFiがkビット（k＞1）の2進数であるときに、Dはマンハッタン距離となる。これまでに、全並列最小ハミング距離検索アーキテクチャ（非特許文献2）や全並列最小マンハッタン距離検索アーキテクチャ（非特許文献3、特許文献2）が提案されてきている。 【0006】 しかし、いくつかのアプリケーションで使用されるアルゴリズムにおいては、距離指標としてユークリッド距離を適用することが望まれている。ユークリッド距離は数2で表されるものであり、ベクトル空間における2点間の距離を測定する尺度としてはマンハッタン距離よりも正確である。 【0007】 【数2】 【特許文献1】特開2002－288985号公報 【特許文献2】特開2005－209317号公報 【特許文献3】特開2004－5825号公報 【非特許文献1】D. R. Tveter, "The Pattern Recognition Basis of Artificial Intelligence," Los Alamitos, CA: IEEE computer society, 1998. 【非特許文献2】H.J.Mattausch,T.Gyohten, Y. Soda, and T. Koide, "Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance," IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002. 【非特許文献3】H. J. Mattausch, N. Omori, S. Fukae, T. Koide and T. Gyohten, "Fully-Parrallel Pattern-Matching Engine with Dynamic Adaptibility to Hamming or Manhattan Distance," 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002. 【非特許文献4】P. Heim, F. Krummenacher and E. A. Vittoz, "CMOS Full-wave Operational Transconductance Rectifier with Improved DC Transfer Characteristic," Electron. Lett., vol. 28, pp. 333-334, 1992. 【非特許文献5】Y. Tulay and J. S. Marsland, "A Conic Section Function Network Synapse and Neuron Implementation in VLSI Hardware," IEEE Conf. Neural Networks, pp. 974-979, 1996. 【非特許文献6】S. Churcher, A. F. Murray and H. M. Reekie, "Programmable Analogue VLSI for Radial Basis Function Networks," Electron. Lett., vol. 29, pp.1603-1605, 1993. 【非特許文献7】O. Landolt, E. Vittoz and P. Heim, "CMOS Selfbiased Euclidean Distance Computing Circuit with Highdynamic Range," Electron. Lett., vol. 28, pp. 352-354, 1992. 【非特許文献8】S. Collins, G. F. Marshall and D. R. Brown, "An Analogue Radial Basis Function Circuit Using a Compact Euclidean Distance Calculator," IEEE Int. Symp. Circuits Systems, pp. 233-236, 1994. 【非特許文献9】P. Hasler, B. A. Minch, J. Dugger, and C. Dorio, "Adaptive Circuits and Synapses using Floating Gate Devices," in Learning on Silicon: Adaptive VLSI Neural Systems, G. Cauwenberghs and M. A. Bayoumi, Eds. Boston, MA: Kluwer, pp. 33-65, 1999. 【非特許文献10】M. Freeman, M. Weeks and J. Austin, "Hardware Implementation of Similarity Functions," IADIS International Conference on Applied Computing, Algarve, Portugal, vol. 2, pp. 329-332, 2005. 【非特許文献11】Y. Yano, T. Koide and H. J. Mattausch, "Fully Parallel Nearest Manhattan-distance Search Memory with Large Reference-pattern Number," Extend. Abst. of the Int. Conf. on Solid State Devices and Materials (SSDM'2002), pp. 254-255, 2002. 【発明の開示】 【発明が解決しようとする課題】 【0008】 これまでに多くのユークリッド距離を計算する回路が提案されている（非特許文献4～7）。しかし、それらの大部分において計算できる距離の大きさの制限や回路規模が大きいことなどの欠点がある。 【0009】 これらの問題を解決するために、フローティングゲートを用いたいくつかの回路が開発されている（非特許文献8、9）。しかし、この回路は回路シミュレーションが難しいために、チップ製造前に回路動作を予想して設計することが難しい。 【0010】 一方、ユークリッド距離を逐次的に計算する回路とそのハードウェア記述言語VHDLによる記述が報告されている（非特許文献10）。この回路は乗算器、加算器、レジスタ、平方根計算回路を用いたディジタル回路であるが、実装トランジスタ数が非常に多いために各参照データと入力データを全並列処理する連想メモリには適していない。 【0011】 ユークリッド距離を計算するためには二乗と平方根という複雑な計算が必要である。特に平方根は最新のプロセッサを使用しても負荷の大きな計算である。なぜなら平方根は近似を繰り返すこと、つまり値を入れてその値がエラーマージン以内になるまで繰り返し計算をすることにより算出されるからである。ハードウェアとして平方根の計算機能を持っていないような場合に、たとえ小さな値の平方根の計算でさえ不可能である。 【0012】 以上のように、ハードウェアで全並列最小ユークリッド距離検索メモリを実現する効果的なアーキテクチャはこれまで提案されていない。 【課題を解決するための手段】 【0013】 最も近いユークリッド距離を持つパターンデータを検索するために平方根の計算は必要ではなく2乗した距離だけを比較することで十分である。なぜならパターンマッチングでは、距離の相対的な大きさの比較だけが必要であり、平方根はこの相対的な大きさを変えないからである。本発明に係る連想メモリ装置は、このような観点に基づいており、以下のように構成される。 【0014】 検索データについて複数の参照データと並列に差の絶対値計算に基づくユークリッド距離の2乗を計算する距離計算回路と、前記ユークリッド距離の2乗の計算結果から最小距離の参照データを検索する検索回路とをメモリ上に形成してなる連想メモリ装置であって、 前記検索データおよび参照データがそれぞれkビット（k＞1）単位でユニット化されている場合に、 前記距離計算回路は、 前記参照データをユニット単位で保存するためのW列R行のユニット保存回路（US）と、 ユニット毎に参照データと検索データの差の絶対値計算を行うW列R行のユニット比較回路（UC）と、 行毎に前記W列のユニット比較回路で計算された差の絶対値の2乗の和に相当する電流または電圧信号を生成するR行のワード重み比較回路（WC）とを備えることを特徴とする。 【発明の効果】 【0015】 本発明による連想メモリ装置では、距離計算回路においてユークリッド距離の2乗を計算し、このユークリッド距離の2乗の計算結果から最小距離の参照データを検索回路において検索するようにしており、平方根計算を行わないため、回路規模の縮小および計算処理の高速化を実現することができる。この結果、連想メモリ装置への適用において、低消費電力で小面積なチップ構成で最小ユークリッド距離検索を実現することができる。 【0016】 このように、本発明では、全並列連想メモリベースシステムにおいて、カラーやグレースケールの画像圧縮・画像認識などに必要なユークリッド距離計算回路を開発し、低消費電力で小面積な最小ユークリッド距離検索連想メモリ装置を実現する。特にこの回路構成は、パターンマッチングアプリケーション（例えば、ネットワークルータ、コードブックベースデータ圧縮、および、対象認識）に対して従来のCMOS技術を用いて高効率な全並列連想メモリ装置のチップ化を可能にする。 【発明を実施するための最良の形態】 【0017】 以下、図面を参照して、本発明を実施するための最良な形態を詳細に説明する。 ［全並列型連想メモリアーキテクチャ］ 図1は、本発明に係る全並列型連想メモリ装置のアーキテクチャを示すブロック図である。メモリコア部分は、メモリ領域100、ウィナー・ラインナップ増幅回路（以下、WLA回路（Winner Line-Up Amplifier））200、全ウィナー取得回路（以下、WTA回路（Winner Take All Circuit））300で構成されており、また、周辺回路として列デコーダおよびR／W回路（Column Decoder and Read/Write(k×W Columns)）110、行デコーダ（Row Decoder(R Rows)）120、検索データ保存回路（Search Data(k×W Bits)）130を持つ。この連想メモリ装置は集積回路として1チップ上に実現されており、上記メモリコア部分および周辺回路はこの1チップ上に形成されている。 【0018】 メモリ領域100は、参照データをユニット（kビット）単位で保存するためのSRAMセルで形成されるW×R個のユニット保存回路（Unit Storage：US）、ユニット毎に参照データと検索データの差の絶対値計算を行うW×R個のユニット比較回路（Unit Comparison：UC）、計算した絶対差をアナログ電圧（あるいは電流）に変換し変換結果を2乗するR個のワード重み比較回路（Word Comparison：WC）により構成されている。 【0019】 ワード重み比較回路WCで生成された信号C（Comparison Signal）はWLA回路200に入り、WLA回路200がこの信号Cを回路自身のバランスにより制御し、最初の段階で各行の電圧の差を最も大きく増幅する。WLA回路200とWTA回路300は、行数Rに対する面積増加の割合が行数Rに対して線形のO(R)になるという特徴がある。 【0020】 WTA回路300は、WLA回路200により増幅された各行の電圧出力LAの差を更に増幅する機能を持つ。WTA回路300の出力WTAにおいては、winner（ウィナー）行が"1"、その他のloser（ルーザ）行が"0"のディジタル信号となる。WLA回路200は、フィードバック信号をワード重み比較回路WCに返す際に、当該WLA回路200に内蔵された電圧フォロワ回路を用いることにより、フィードバックを高速化している。 ［ユークリッド距離計算回路］ 最も近いユークリッド距離を持つパターンデータを検索するために平方根の計算は必要ではなく2乗した距離だけを比較することで十分である。なぜならパターンマッチングでは、距離の相対的な大きさの比較だけが必要であり、平方根はこの相対的な大きさを変えないからである。本実施形態の連想メモリ装置に用いられるユークリッド距離計算回路は、このような観点に基づいて構成されている。 【0021】 本実施形態によるユークリッド距離計算回路は、図1に示すように、取り扱うデータを符号化したkビット（k＞1）相当のユニットをW個並べたものとなる。連想メモリ装置の入力となる検索データと連想メモリ装置内に格納されている参照データ（i行）をそれぞれSW、REFiとおくとき、SWとREFiの間のユークリッド距離の2乗は数3のように表される。 【0022】 【数3】 【0023】 ユークリッド距離は主にカラー画像やグレースケール画像などのkビット、W個のデータの比較を必要とする画像データ処理などに用いられる。ユークリッド距離の計算を実現するためには、重み付けされた検索データ（SW）と参照データ（REFi）の比較を行う回路、すなわちW個のユニットそれぞれの2つのkビットデータの差の絶対値（｜SWj－REFij｜）を生成する回路と、この絶対差の2乗を計算する回路が必要となる。 【0024】 図2は、連想メモリ装置内に構築される、行iに対するユークリッド距離計算回路の構成を示すブロック図（Wユニット分）である。図2において、USi1～USiWはそれぞれ非反転信号SWおよび反転信号～SW（～は反転を意味する。以下同様）のkビットバイナリコードデータによる検索データユニットを取り込み、予め保存されている参照データユニットと共にビット単位で保存するユニット保存回路、UCi1～UCiWはそれぞれkビット減算器および絶対値計算回路を備え、ユニット保存回路USi1～USiWから検索データSWと参照データREFiを受け取り、両者の差の絶対値を計算するユニット比較回路である。各ユニット比較回路UCi1～UCiWで計算された検索データSWと参照データREFiの差の絶対値のデータは、各ビットの出力OUT＝｛0，1｝のディジタル値として、ワード重み比較回路WCiへ送られ、ワード重み比較回路WCiにおいて、全ビットのユークリッド距離の2乗（絶対差の2乗）の総和を計算する。 【0025】 ワード重み比較回路WCiには、ユニット比較回路UCi1～UCiWの各々に対して電流変換回路10およびアナログ2乗回路20が設けられている。 【0026】 各ユニット比較回路UCi1～UCiWから出力されるディジタル信号OUT1～OUTkは、対応する電流変換回路10でアナログ電流に変換される。各電流変換回路10は、対応するユニット比較回路から出力されるディジタル信号OUT1～OUTk（ディジタルの距離）をアナログ電流に変換するために、それぞれのディジタル信号をゲートに受けるk個のPMOS（電流変換トランジスタ）が用いられている。ここでは各ビットの出力値OUT1，OUT2，…，OUTkを、それぞれビットの位置に応じて、最下位ビットの出力OUT1の電流値の2k-1倍になるように調整し重み付けが行われている。調整方法としては、各ビットの出力OUTkに接続するトランジスタのゲート幅Wkを整数（2k-1×W0）倍（W0は基準となるトランジスタ幅を示す）して、アナログ2乗回路20に接続しているトランジスタに流れる電流値を制御することで各ビットの重み付けを行う。 【0027】 各電流変換回路10からの出力電流Iiは、対応するアナログ2乗回路20により2乗される。アナログ2乗回路20の回路構成例を図3に示す。各アナログ2乗回路20から出力される電流（絶対差の2乗に応じた電流）Ioはマッチラインに流れ、これによって各グループの検索データSWiと参照データREFijのユークリッド距離の2乗に対応した電流が流れ、全体の検索データSWと参照データREFiのユークリッド距離DEuclid, iの2乗に相当する電流値Iが得られる。この電流値Iは電圧値に変換されてWLA回路200、WTA回路300に送られ、最もユークリッド距離が最小となる行の信号が増幅され、距離が最小の行から"1"が出力される。 【0028】 なお、図2に示したユニット保存回路（US）、ユニット比較回路（UC）については公知の回路を用いて実現可能であり、たとえば特許文献2に開示されているものを用いて実現することができる。 ［最小ユークリッド距離検索連想メモリの性能評価］ 本実施形態に基づく最小ユークリッド距離検索連想メモリの性能をHSPICEによってシミュレーションで確認した。テクノロジは0.35μm CMOSで16個の5-bitバイナリ（図2におけるW＝16、k＝5）と128個の参照データ（図1におけるR＝128）を用いた。図3に示したアナログ2乗回路20のBasic Squarer部についてのシミュレーション結果を図4に、最小ユークリッド距離の参照データを検索するための時間（Winner 検索時間）の結果を図5に、平均消費電力の結果を図6にそれぞれ示す。このように、本実施形態に基づく最小ユークリッド距離検索連想メモリは、ウィナーを参照データとウィナー距離の広い範囲において見つけることができる。 ［本実施形態の変形例］ なお、図2に示したユークリッド距離計算回路の代わりに図7に示すユークリッド距離計算回路を用いることも可能である。図7に示すユークリッド距離計算回路のワード重み比較回路WCiには、ユニット比較回路UCi1～UCiWの各々に対してディジタル2乗回路30および電流変換回路40が設けられている。各ユニット比較回路UCi1～UCiWから出力されるディジタル信号（kビット）OUT1～OUTkは、対応するディジタル2乗回路により2乗される。ディジタル2乗回路30からの出力（2kビット、k＞1）OUT1～OUT2kは、対応する電流変換回路40でアナログ電流に変換される。各電流変換回路40は、対応するディジタル2乗回路30から出力されるディジタル信号OUT1～OUT2kをアナログ電流に変換するために、それぞれのディジタル信号をゲートに受ける2k個のPMOS（電流変換トランジスタ）が用いられている。ここでは各ビットの出力値OUT1，OUT2，…，OUT2kを、それぞれビットの位置に応じて、最下位ビットの出力OUT1の電流値の22kー1倍になるように調整し重み付けが行われている。調整方法としては、各ビットの出力OUT2k（k＞1）に接続するトランジスタのゲート幅W2kを整数（22kー1×W0）倍（W0は基準となるトランジスタ幅を示す）して、電流変換回路40内のトランジスタに流れる電流値を制御することで各ビットの重み付けを行う。各電流変換回路40から出力される電流（絶対差の2乗に応じた電流）はマッチラインに流れ、これによって各グループの検索データSWiと参照データREFijのユークリッド距離の2乗に対応した電流が流れ、全体の検索データSWと参照データREFiのユークリッド距離DEuclid, iの2乗に相当する電流値Iが得られる。 【0029】 また、本実施形態において示した回路（図2、3、7）の論理は一例であり、論理回路を正または負論理に反転させることも可能である。例えば、メモリ領域のN－MOSをP－MOS、電流変換回路10，40のP－MOSをN－MOSに変更したりしても、その作用効果に変わりはない。 【産業上の利用可能性】 【0030】 本発明に係る連想メモリ装置は、人工知能システム、データバンクシステム、インターネットルータ、モバイル端末（例えば、モバイルテレビ電話）、コードブックベースデータ圧縮、および、対象認識などの圧縮、認識処理技術全般に利用することができる。 【図面の簡単な説明】 【0031】 【図1】本発明に係る実施形態として、ユークリッド距離計算回路を用いる全並列型連想メモリ装置のアーキテクチャを示すブロック図。 【図2】図1に示すメモリ内のユークリッド距離計算回路の1行分の構成を示すブロック図。 【図3】図2に示すアナログ2乗回路の内部構成を示す回路図。 【図4】図3に示したアナログ2乗回路20のBasic Squarer部についてのシミュレーション結果を示す図。 【図5】Winner 検索時間のシミュレーション結果を示す図。 【図6】平均消費電力のシミュレーション結果を示す図。 【図7】図1に示すメモリ内のユークリッド距離計算回路の1行分の構成の変形例を示すブロック図。 【符号の説明】 【0032】 100 メモリ領域 200 ウィナー・ラインナップ増幅回路（WLA：Winner Line-Up Amplifier） 300 全ウィナー取得回路（WTA：Winner Take All Circuit） 110 行デコーダおよびR／W回路（Column Decoder and Read/Write (k x W Column)） 120 列デコーダ（Row Decoder (R Rows)） 130 検索データ保存回路（Search Data (k bit x W)） US ユニット保存回路（Unit Storage） UC ユニット比較回路（Unit Comparison） WC ワード重み比較回路（Word Comparison） 10 電流変換回路 20 アナログ2乗回路 30 ディジタル2乗回路 40 電流変換回路
Drawing	(In Japanese)【図1】 (In Japanese)【図2】 (In Japanese)【図4】 (In Japanese)【図5】 (In Japanese)【図6】 (In Japanese)【図7】 (In Japanese)【図3】