研究紹介
丸文研究奨励賞 受賞者

最小距離検索連想メモリLSI
アーキテクチャの開発とその集積化― 連想メモリベースパターンマッチング処理の基盤技術開発に向けて ―小出 哲士
広島大学 ナノデバイス・システム研究センター 助教授

認識処理などにおいては、入力パターン(データ)とデータベースに保存された参照用パターンを比較して最も似ているパターンを検索する処理は、基本的かつ重要な操作です。この操作は汎用プロセッサ上でソフトウェアにより実現されることが一般的ですが、ソフトウェア処理の場合には、パターンの検索に時間がかかるため実時間での処理が難しい、ハードウェアの小型化・低消費電力化が難しい、という問題点があります。システムの小型化や携帯端末上での認識処理の実現等への応用には、小面積かつ低消費電力で類似するパターンを高速に検出するパターンマッチング処理技術が不可欠です。本研究では、パターンマッチング処理の要素技術の一つである連想メモリに注目し、新しいLSIアーキテクチャの開発とその集積回路化について研究を行いました。

１．
研究の背景

イム処理やシステムの小型化が要求されるにCAM（Content Associative Memory）

場合には高速・小面積・低消費電力で実と呼ばれます。これに対して後者の連想メ入力パターンとデータベースに保存され現する集積回路技術の開発が非常に重モリは距離と呼ばれる類似度の指標（例えている参照パターンの中から最も類似した要な課題となっています。本研究で取り扱ばハミング距離 ※1やマンハッタン距離 ※1なパターンを検索する類似パターン検索（最っている連想メモリは機能メモリの一つであど）を用いることで距離が0の完全一致検

小距離検索）機能は認識システムや画像・り、従来の一般的なメモリ機能に加えてメモ索から最小距離の検索まで行うことが可能

データ圧縮などのパターンマッチングを必要リ内データの検索機能を備えています。こです。これはパターン認識や認証への応用とする応用において必要不可欠です。現在の連想メモリは検索する方法により大きくの他に、類似パターンの検出が可能である

主流の汎用のディジタルプロセッサベース分けて2種類に分類することができ、入力デため、画像・音声認識、セキュリティシステムのシステムでは、処理対象となるパターンのータと完全に一致する参照データを検索すにおける認証、及び将来の人工知能システ

データ長や数が増加するにつれて各データる完全一致検索型と入力データと最も類ムにおける柔軟な情報処理などへの応用の比較に要する演算処理回数が飛躍的に似した参照データを検索する最小距離検が期待されています。本研究では後者の最増加してしまいます。そのため特にリアルタ索型があります。前者の連想メモリは一般小距離検索型連想メモリについて研究を行いました。

2．
研究の成果
我々の研究グループではパターンマッチ
ング処理に不可欠な高速・小面積・低消費電力を同時に実現することが可能な全並列型ディジタル・アナログ混載連想メモリアーキテクチャを開発し、その集積回路化について研究を行いました【1-5】。開発した連想メモリは、複数の信号処理回路とメモリを用いて並列実行するだけでなく、さらにアナログ信号処理を取り入れることにより、処理
図1 全並列最小距離検索連想メモリのシステム構成図

速度を格段に向上させています。入力デー

図2 最小ハミング距離検索連想メモリ（0.6um CMOS技術）（a）テストチップ写真 （b）検索時間の実測平均値

タと参照データは共にディジタル信号です

来の連想メモリの完全一致の検索に加え補足説明が、その類似度を出力する回路や最も似通て、最も近いパターンの検索を並列に検索ったデータを選ぶ出す最小距離検索回路することを可能としました。その上、1回の最に、高速で並列処理に適したアナログ回路

小距離検索に要する時間も200nsec程度※1 ハミング距離、マンハッタン距離
入力データをA=（A1、A2、…、AW）、参照データをB=（B1、B 2、…、B W ）とし、それぞれkビット×W個の要素で構成されているとすると、2つのデータA、Bのマンハッタンを用いています（図1）。検索に必要な最小と高速です。また、本研究では、CMOS集積

距離DManhは、DManh = ∑ Ai-Bi と定義され、距離の計算には取り扱う用途に応じて異な回路を開発し、テストチップを試作して評価

各要素Ai、B（1≦i≦W）の差の絶対値の総和で表される。
iる距離指標が用いられます。例えば、文字も行いました（図2）。これまでの試作では、これに対してハミング距離DHammは、DHamm = ∑(Ai⊗Bi)

認識や指紋認識などにおいてはハミング距

ハミング距離検索に対して、最大パターンビ離が用いられ、データ圧縮やカラー画像認ット長768ビット、パターン数32、マンハッタン（⊗は排他的論理和演算子）となり、入力データと参照データの間の異なるビット数と定義され、k=1の時にはマンハッタン距離と等しくなる。

Wi=1

Wi=1

識などではマンハッタン距離が用いられます。

距離検索に対して、最大パターン長5bit×

そこで、我々の研究グループではハミング距16ユニット、パターン数256を実現していまR e f e r e n c e s（ 参 考 文 献 ）離【1-3】とマンハッタン距離【4・5】を取り扱うこす。更に提案アーキテクチャを大規模なビッとが可能な連想メモリ技術を開発し、幅広ト数やパターン数に対応できるようにバンクい用途への対応を実現しました。

構造を用いた回路の改良を行い【5】、低消【1】 H. J. Mattausch, T. Gyohten, Y. Soda, T.
Koide: "Compact associative-memory architecturewith fully-parallel search capability for the minimum
Hamming distance", IEEE Journal of Solid-State
Circuits, Vol. 37, No. 2, pp. 218-226（2002）.
【2】 H. J. Mattausch, N. Omori, S. Fukae, T.
Koide, T. Gyohten: "Fully-parallel pattern-matchingengine with dynamic adaptability to Hamming or
Manhattan distance", Proc. of Symposium on VLSI
Circuits, pp. 252-255（2002）.
【3】 T. Koide, H. J. Mattausch, T. Gyohten, Y.
Soda: "A nearest-Hamming-distance searchmemory with fully parallel mixed digital-analog
match circuitry", Proc. of Asia and South Pacific
Design Automation Conf., pp. 591-592（2002）.
【4】 T. Koide, Y. Yano, H. J. Mattausch: "An
Associative Memory for Real-Time Applications
Requiring Fully Parallel Nearest ManhattanDistance-Search", Proc. of Workshop on Synthesis
And System Integration of MIxed Technologies,
pp. 200-205（2003）.
【5】T. Koide, Y. Yano and H. J. Mattausch, "BankType Associative Memory for High-Speed Nearest
Manhattan Distance Search in Large ReferencePattern Space", Extend. Abst. of the Int. Conf. onSolid State Devices and Materials, pp. 360-361（2004）.

このパターンマッチング機能を汎用プロセッサ上で実現すると、パターンをビット毎に費電力化を図ると共に、それを実現する回路を実装しています。

逐次的に比較することが必要になるため、現在、我々の研究グループでは、この基取り扱うビット数やパターン数が増加するに盤技術をもとに人間のような高度の知能情つれて、演算回数が膨大になり検索処理報処理を実現するために、画像やパターン時間が長くなります。また、これまでに提案さ認識処理に連想メモリを応用するための新れている従来型の連想メモリでは、実装面しいLSIシステムアーキテクチャへの応用や積や消費電力が大きい、1回の検索に複数連想メモリに参照パターンを自動的に学習サイクルかかるという問題点がありました。

する機能の付加やその集積回路技術などこれに対して我々の研究グループが提案すに関して研究を行っています。

る方式は、ディジタルとアナログの両者の利点をうまく利用して融合することで、回路規模の増加がメモリの参照パターン数に対して、線形増加と小面積で実現可能であり、全ての参照パターンに対して同時に並列に検索ができるため、検索時間も高速であるという利点があります。
このように提案した連想メモリは、ディジタ
ル・アナログ回路を融合することにより、従