高速・低消費電力かつスケーラビリティを有する時間領域連想メモリ回路
学生氏名 安田 雅浩
              
推薦者 広島大学大学院 先端物質科学研究科 半導体集積科学専攻     
研究・開発の目的・狙いとが可能である．提案回路では，各データの距離に応じ連想メモリはパターン認識等に適用可能な，複数の参て，入力から出力までの遅延回路の総数が変わる仕組み

照データの中から入力データに最も似ているデータを探 を取り入れている．つまり，距離が小さければ小さいほし出し、そのデータまたはアドレスを出力する機能メモ ど，入力から出力までの遅延時間は短くなる．検索開始
リであり，画像・音声認識のような高度な認識処理や，画信号を同時に入力し，最初に出力が出てきた参照データ像圧縮などの処理に応用できる．各データの距離（類似を  とすることで最小距離検索を実現する．距離度）を表現するためには完全ディジタル，ディジタル・ を遅延時間に変換する回路にはリングオシレータ状の遅アナログ混載など様々な手法があるが，本試作チップは延回路を採用し，距離‐周波数変換を行なった後，周波小面積・低消費電力かつ微細テクノロジへのスケーラブ 数‐時間変換を行っている．これにより，ばらつきの影ルな設計が可能な距離比較手法として、時間領域を利用響が大きく誤検索が生じても，設計後に時間差を拡大すした新しい手法を用いている．本試作では，リングオシることができ，検索精度を向上させることができる．こレータベースの時間領域（周波数マッピング）連想メモの手法による連想メモリを特に周波数マッピング連想メ

リの性能とスケーラビリティを確認することを目的とし モリと呼ぶこととする．図  に周波数マッピング連想メている．

モリのブロック図を示す．

連想メモリによる最小距離検索の実現方法
最小距離の参照データを  ，それに次ぐ類似度をもつデータを !  ，それ以外のデータを  と呼ぶ． の検索には検索データとデータベースのそれぞれの参照データの距離の計算・比較という膨大な処理が必要とされる．この処理を完全ディジタル回路で行
うには回路面積・検索速度・消費電力が大きくなってしまう．そこで電流・電圧差変換のようなアナログ変換によって高速・低消費電力での検索と小面積での "# 化を可能にした．この手法では，最終的に距離の差を電圧差という有限の領域に変換して比較を行うため，電源電圧アナログ信号を用いた考え方
VDD
Analogdynamicrange
GND

スケーラブルでない
電圧差＝距離の差

時間領域を用いた考え方
時間差＝距離の差Time

時間差を設計にあわせて調整可能
距離の差を時間差で表現することで，設計に合わせて取り扱える範囲を調整可能

距離を表現するための電圧はダイナミックレンジの範囲内でのみ取り扱うことができる
図 $ 時間領域マッピングのコンセプト．

リングオシレータベース距離−周波数変換回路
距離−周波数変換回路には段数可変のリングオシレーの低下やデータ数の増加に伴い，距離の差を表現できるタベース回路を利用している．図 % に回路図を示す．イ

範囲が狭くなってしまう．また，トランジスタの微細化

ンバータチェインによる遅延回路のあるパスと無いパスに伴う特性ばらつきの影響を完全に打ち消すことは難し を選択可能な１ビットステージを各ビットに一つずつ用く， と  !  を区別できないなど誤検索を 意し，リングオシレータ制御用の & ' を一つ挿入する生じさせる原因となった．時間領域（周波数マッピング） ことでリングオシレータを形成している．各１ビットス
連想メモリは，距離の差を無限の領域である時間領域に テージは対応するビットの比較結果に応じて，比較結果変換することで，ばらつきの影響を軽減し，かつ高速・ が一致していれば遅延回路の無いパス（"  ! ! ），不一致ならば遅延回路のあるパス（( ! ）を選択する．
低消費電力での "# 化を可能にする．
ここで，全てのパスが "  ! ! だった場合のリングオ

時間領域（周波数マッピング）連想メモリのコンセプト

シレータ $ 周の遅延時間を¼ とし，

( ! ひとつ分

提案時間領域（周波数マッピング）連想メモリでは，参の遅延時間をとすると，ハミング距離
照データと検索データの距離の差を信号伝播の遅延時間 シレータの発振周波数  はに変換している．図 $ に示すように，時間差は設計によっ$て無限に拡大できるので，ばらつきの影響を打ち消すこ) ¼   * のリングオ)$*

ンー
タパ
R

SE (Search End)
検索データ
k
ビット比較器1 k 距離‐周波数変換回路1

参照データ1
参照データ1

k

Sd1

M1

RdR

R

マッチ
信号

分 時間周 領域器 S WTA M
Skk

S1

ビット比較器R k 距離‐周波数変換回路RSB (Search Begin)

図  周波数マッピング時間領域連想メモリのブロック図
 が小さいほど発振周波数は高くとなる．ハミング距離る．( ! の遅延時間倍に拡大精度が必要な場合，分周器を使って時間差をなり，リングオシレータを信号が $ 周する時間は短くなすることで時間領域 & 回路で判別できる時間差までの大きさはシミュレーショ 拡大することができ，最小距離の  のみを出力すンによってばらつきの影響があっても検索結果に影響し ることができる．分周を行うと検索時間はループ回数にないように設計される．

比例して大きくなるため，検索時間と検索精度のトレードオフで分周回数を決定する．

各ビット比較結果
1bit
stage

1bit
stage

1bit
stage

1bit
stage

1bit
stage

1bit
stage

（距離1のパス）

S0

in

out

S0Q

S = 1

S = 0

（距離0のパス）

S0

Short path

された回数ループして出力されたリングオシレータの出out

S0Q

回路

時間領域  + &（&）回路は分周器で指定SE(Search End)

力信号の中で最初に変化したものを  とし，それ以外のデータを  と判定するための回路である．提案

検索データと参照データの各ビットの比較結果に応じて信号が通過するパスが決定

Long path

S0 時間領域

SB(Search Begin)：ビット比較結果が不一致→ Long pathを選択

・・・：ビット比較結果が一致→ Short pathを選択

Winner

検出回路

SE(Search End)

input<0>図 % 段数可変リングオシレータ．

τD・・・Wout<0>

Q
D
RST Register
CLK・・ ・・・ ・・・・・・・・・・

分周器ユニットによる周波数‐時間変換
τD

input<R>

分周器はリングオシレータの何周目のループの出力で

Q
D
RST Register
CLK時間差を比較するか決定する回路である．分周回数は分

Wout<R>

周器ユニットへの外部からの制御信号によって指定でき，設計後に検索精度を向上させることができる．分周回数をSB(Search Begin)とすると，検索開始からリングオシレータの出力が出るまでの時間

は， ) ¼

図  時間領域 & 回路．
 となる．つまり，比較に使う時間差を*)*倍に拡大するこ

GNDとができる． と  を判別するためには次節でいない

とSB

GND

いような厳しい条件では，ばらつき等の影響により， つGNDの信号の時間差が時間領域 & 回路の分解能を下回る

B

B

A・・・SB

SEGND

Sd61
Sd62
Sd63
Sd64

どのパスの変化に対しても出力遅延時間一定のNOR

OUT

A

B

B

A

A

B

OUT

（b） Static CMOS型Winner検出回路

図   検出回路．

信号のどちらも  として出力する．非常に高い検索

BSE（a） Wired OR型Winner検出回路

可能性がある．その場合，時間領域 & 回路は  つのどのパスの変化に対しても A
出力遅延時間一定のNAND A・・・(Search End)

SdR

Sd1
Sd2
Sd3
Sd4

SB

Precharge&KeeperSdR-k+1の時間差しかな

Precharge&Keeper
GND

GND

 !  の距離が $ しか離れて ½ の時間差，つまり・・・

Sd2

のべる時間領域 & 回路の分解能以上の時間差が必要となるが， とPrecharge&Keeper

Sd1

連想メモリのために図  に示す高分解能の時間領域 &トステージの間に必要だったゲートを削減することができ，/ ビットをまとめた場合，基本リングオシレータ遅回路を開発した．

この回路は各参照データ行に遅延回路とレジスタを一 延時間つずつ備え， 検出回路と " 

 ツリーを全体に一つ備えている． 検出回路は  行の出力信号の変化を検出し，検出信号を発生させる． "  ツリーは全行のレジスタのクロック端子にスキューの無いように検出信号を分配する． 行のレジスタ¼ 

*)*間の一部を削減することができる．今回の試作では２ビッ

ここで， 信号が変化してから，全行のレジスタをトのパスエンコーディングを行い，その効果と有効性を確認した．
試作結果

ラッチするまでに必要な時間を  ， の信号がレ周波数マッピング連想メモリの試作結果を表 $ に示す．

ジスタにデータ入力される時間を  ，レジスタのセット

試作チップは最小ハミング距離検索連想メモリである．

 と  を判別する

 とすると， )となり，全体の検索時間の基本周波数に依存した遅延時ラッチすることで， 行と  行を判別している．

ために必要な時間差  は，/ 分の $ に短縮できる．その結果，リングオシレータの出力の遅延時間は，のデータ入力だけが変化している時に全行のレジスタをアップ時間を¼ を約

テストチップ１（.$）は  × 0!，テストチップ （.）は $ × $0! の連想メモリとしては世界最大規)%*模のデータサイズであり，データサイズに対するスケーラビリティを確認できる．また，. のみ２ビットパスとなる．高分解能を有する為には  の信号がレジスエンコーディングを取り入れている．実測結果から，最タに入力された直後にレジスタをラッチすることが望ま 短検索時間は .$ で  ，. で   となった．.
しい．そのため，レジスタのデータ入力端子の前には遅 ではビット数を .$ の  倍に拡張しているため，本来であれば .$ の２倍程度の検索時間になるが， ビットパ延回路を挿入し，  だけ遅延させている．判別分解能である時間差  は  とスエンコーディングによって約   程度削減され，ほぼ のばらつきを考慮して決定される． 検出回路には図  に示すように， 同等の検索時間となった．最大消費電力に関しても，デー,- 型と "!! ./," 型の回路を採用した．これらはどの行が  になっても等しい時間で高速に検出信号タサイズの増加に対して，大幅な増加は見られなかった．
回路規模はデータサイズに比例し，約４倍となっている．
それぞれの結果を規格化し他研究と比較すると，図  にを出力する特長がある．

示すように，. では飛躍的に向上しており，ディジタ２ビットパスエンコーディングによる高速化

ル手法と比較して，半分以下の検索時間と % 分の１以下以上が周波数マッピング連想メモリの基本構成であるの消費電力での検索を実現した．また，アナログ手法でが，更に検索時間を高速化させる手法として，パスエンコーディング手法を開発した．これは図  に示すように，$ ビット毎にパスを選択していた従来の処理を複数ビット程度までの検索精度は $1 を達成し， 距離 $せる手法である．これにより，$ ビットステージと $ ビッ
S0

S1

S0

Delay
S0Q

S1

Delay

S0Q

S1Q

out

S1QS0S0Q

Delayin

S0S2Q

out

S1

S0S2Q

S1Qとして出力される組み合わせがわずかに現れる．この検索の誤差は，例えば  の距離が  のときに $の距離を持つ題ない精度であると考えられる．厳しい条件での  !  の差を区別する分解能を図 2 に示す．検索の分解能 $ の時  と  !  の差 $ を $1区別でき，分解能  のときは距離  の差を $1 区別でと最短パスのゲート数

S0Q（b） 2ビットパスエンコーディング時の2ビット分の遅延パス !  のデータを出力してしまうといった状態であり，アプリケーションに適用した場合は問半減

S2

Delay

 !  の差が距離 $ しかない場合のような，非常に厳しい条件で  !  が 4

S1

S2

以降では  と最短パスのゲート数（a） 通常の2ビット分の遅延パス間と約 % 分の $ の消費電力となった．

また，アプリケーションで想定される  距離 $分まとめて処理することで最短パスのゲート数を減少さ

in

ある電流マッピング手法と比較しても，約半分の検索時2きる．この結果は，従来のアナログ手法と比較すると非常に優れており，微細テクノロジに対してスケーラブル

図   ビットパスエンコーディング．

な手法と言える．

%

高速Search key data
Search Key & Precharge Circuit

redocedwoR

Memory&Ring Oscillator(64 data, 256 bits)

WTA&Frequencydivi
der

Wmm
86
1.

Column Decoder & R/W Circuit
1.87 mmredocedwoRTAMemory&Freq 3.
&5u 4 .0
Ring Oscillator ency mm mm(128 data, 512 bit)Column decoder

divider（current mapping）（bubble sorting,Thermometer code）

5.0 mm

図 3 チップ写真。左は   0!，右は $  $ 0!．

図  最短検索時間と最大消費電力の比較．

表 $試作チップの諸元．
テストチップ1
テストチップ2

検索時間
最大消費電力面積

全体
メモリ

リングオシレータ

WTA

Rohm 0.18 μm
2009年第１回
1.8 V

Rohm 0.18 μm
2009年第５回
1.8 V

64-word 256-bit
1.9 mm×1.7 mm

128-word 512-bit
3.7 mm×3.4 mm

Wired OR型
160 ps
770 ps50 – 245 ns
3.05 – 14.95 ps/bit
36.54 mW
2.23 μW/bit
3.08 mm2

Static CMOS型
154 ps1070 ps60 – 575 ns
0.91 – 8.78 ps/bit
41.94 mW
0.64 μW/bit
12.58 mm2

ハミング距離未使用

0.94 mm (31%)
1.63 mm (53%)
0.11 mm ( 4%)222（clocked delay line）（current mapping）

3.7 mm

テクノロジ
試作ラン
電源電圧
距離指標
データサイズ
回路規模
2ビットパスエンコーディング
WTA回路の構成
分解能τΔvar
距離1に対する時間差τS

低消費電力)it 0.1
テストチップ2
re /b
180 nm, 3-path, meas.
Ww
1oP μ( 1 180テストチップ
nm 2-path, meas. ●noVLSI ’02 [4]imtu aISSCC ’04 [2]mix pis 10a si●● CICC ’03 [3]MD● ISSCC ’01 [1]100101Minimum search time (psec/bit)

入力
データ

参照データの例

・・・・・・
距離= 0 30Aの参照データの範囲

ハミング距離256128 150）離間距離
025664192
128
6距（ 5 実際のWinner（A)が 距離2の差が100% 類似度－D ×100
能＝ 256256
区別できる範囲
解43 検出される範囲
分2（データの一致率）
索
11007550250
検 最類似データの類似度※右下に行くほど厳しい条件

使用

Input - winner(Diw)iw[%]

検索分解能N ・・・ WinnerとNearest loserの 距離Nの差を100%区別可能

4.46 mm (35%)
6.51 mm (52%)
0.22 mm ( 2%)222

図 2 検索の分解能．

まとめ

参考文献リングオシレータベースの周波数マッピング連想メモ

4$5 = > /!!  !  &   !!  < ! !:   8!    ! ! 0!
 !  ( !    '(! < #""..  $3 $3$$
45 " +   !  & (!   ! <   !   (     0 00  <!     '(! < #""..    
4%5 6 ,+ !  & (   8 :!( !:    8! =( !   ( (8            !!   @ < .#..  %  %
45 => /!!  !  B  @  @!!  /! (( 8! ' & !0! ! =(  / !
! '!  @  < "   C"# .  !   リを試作し，有効性を検証した．実測の結果，アプリケーションに適用可能な検索精度を有しており，従来手法の半分以下での最短検索時間と，ディジタル手法の % 分の$ 以下アナログ手法の３分の $ 以下の消費電力での最小距離検索を実現した．
発表文献4$5 / 6  !  78 9! !  8
 !+    ! 8! ( !    !
!  0 8!   : !; 9!  &0 <""'/$  $$ $$ $45 = > /!!   !  78 8 8   ! ( !     ! 0  < ? (; @  < "".#-. $  % $ $
4%5  &  !  7& < 8!     !
 ./,"   : ! 8! A( 0 (!  ; 9!  &0 < ""'/$  
% $