Top > Search of Japanese Patents > (In Japanese)アドレス生成器

(In Japanese)アドレス生成器 achieved

Patent code P09S000279
Posted date Jan 15, 2010
Application number P2008-510866
Patent number P4892693
Date of filing Mar 27, 2007
Date of registration Jan 6, 2012
International application number JP2007056497
International publication number WO2007119539
Date of international filing Mar 27, 2007
Date of international publication Oct 25, 2007
Priority data
  • P2006-101104 (Mar 31, 2006) JP
Inventor
  • (In Japanese)笹尾 勤
Applicant
  • (In Japanese)国立大学法人九州工業大学
Title (In Japanese)アドレス生成器 achieved
Abstract (In Japanese)消費電力を抑え且つデバイスの構造を簡単化して小面積で実装することが可能なアドレス生成器を提供する。
入力ベクトルX=(X1,X2)に対しX1をハッシュ化したY1を出力するハッシュ回路、Y1にハッシュ衝突が生じなければアドレス生成関数f(X)を仮アドレスA’とし、それ以外は固有アドレスAの一つをA’とする仮アドレス生成器、X”=f-1(A’)を出力するデータ再生器、X”とXとが一致する場合はA’を出力し、それ以外は無効値を出力する固有アドレス検出器、固有アドレス検出器が無効値を出力するXに対しf(X)を出力し、それ以外は無効値を出力する補完アドレス生成器、及び固有アドレス検出器及び補完アドレス生成器の出力のうち無効値以外のものがあればその値を固有アドレスAとして出力し、それ以外は無効値をAとして出力する出力合成器を備えた。
Outline of related art and contending technology (In Japanese)


k個(kは自然数)の異なる2値ベクトルの集合を登録ベクトル集合(set of registered vectors)とする。登録ベクトル集合の各要素と一致する入力に対して1からkまでの固有アドレス(intrinsic address)に単射し、それ以外の入力に対して0となる関数をアドレス生成関数(address generation function)という。また、アドレス生成関数の演算を行う回路をアドレス生成器(address generator)という。アドレス生成器に入力されるベクトルを、入力ベクトル(input vector)という。入力ベクトルがn次元ベクトルであるアドレス生成関数を、n入力のアドレス生成関数という。また、n入力のアドレス生成関数の演算を行う回路をn入力のアドレス生成器という。



アドレス生成器は、連想メモリ又は内容検索メモリ(Content Addressable Memory:CAM)とも呼ばれ、パターン・マッチング、インターネットのルータ、プロセッサのキャッシュ、TLB(Translation Lookaside Buffer)、データ圧縮、データベースのアクセラレータ、ニューラルネット、メモリパッチなど幅広い分野において利用されている。



アドレス生成器の機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェア(半導体メモリ)を用いてアドレス生成器を実現することが多い。以下、ハードウェアで構成された従来のアドレス生成器について説明する。



図9は、従来のアドレス生成器(CAM)の基本構成の一例を表すブロック図である(特許文献1参照)。アドレス生成器100は、比較レジスタ101、検索ビット線ドライバ102、k個のワードW1~Wk、k個の一致センス回路MSC1~MSCk、k個の一致フラグレジスタMFR1~MFRk、及びプライオリティ・エンコーダ(優先度付符号化回路)PEを備えている。



比較レジスタ101は、nビットの入力ベクトルを格納するレジスタである。検索ビット線ドライバ102は、比較レジスタ101の各ビットを検索ビット線上にドライブする。各ワードW1~Wkは、それぞれnビットのCAMセルを備えている。



図10は、図9のCAMセルの構成回路図である。図10に例示したCAMセル103は、不一致検出型のものである。CAMセル103は、メモリ・セル104及び一致比較回路105から構成される。メモリ・セル104は、1ビットのデータを記憶するSRAM構成のメモリ・セルである。図10においてDがデータ、DNが反転データを表す。一致比較回路105は、メモリ・セル104に記憶された1ビットのデータと検索ビット線対SL,SLN上にドライブされる入力ベクトルとを比較し、その一致比較結果を一致線ML上に出力する。



一致比較回路105は、3つのnMOSトランジスタ(以下「nMOS」という。)106,107,108を備えている。nMOS 106,107は、検索ビット線SLNと検索ビット線SLとの間に直列に接続されている。nMOS 106,107のゲートは、それぞれ、メモリ・セル104のデータD,反転データDNに接続されている。nMOS 108は、一致線MLとグランドとの間に接続されている。nMOS 108のゲートは、nMOS 106,107の間のノード109に接続されている。



まず、検索を行う前に、アドレス生成器100のそれぞれのワードW1~Wkに、検索対象である登録ベクトルが記憶される。各ワード内の各CAMセル103において、メモリ・セル104へのデータの書き込み及びメモリ・セル104からのデータの読み出しは、通常のSRAMと同様にして行われる。



検索時には、まず、比較レジスタ101に入力ベクトルが格納される。入力ベクトルの各のビットは、検索ビット線ドライバ102により、各々対応する検索ビット線上にドライブされる。



各々のワードW1~Wkでは、各CAMセル103に予め記憶されている登録ベクトルと検索ビット線上にドライブされた入力ベクトルとの一致検索が同時(並列)に実行され、その結果が一致線ML1~MLk上に出力される。これらの検索結果は、それぞれ一致センス回路MSC1~MSCkに入力される。各一致センス回路MSC1~MSCkは、各検索結果を増幅し、一致センス出力として一致センス出力線MT1~MTkに出力する。各一致センス出力は、一致フラグレジスタMFR1~MFRkに格納され、一致フラグ出力として一致フラグ出力出力線MF1~MFkに出力される。一致フラグは、‘1’が「一致あり」、‘0’が「一致なし」を表すものとする。



各一致フラグ出力は、プライオリティ・エンコーダPEに入力される。プライオリティ・エンコーダPEでは、所定の優先順位付けに従って、一致が検出されたワードの中から最優先順位のワードのアドレス(最優先一致アドレス:HMA)を選択し出力する。各ワードの優先順位は、ワードW1が最も高く、Wkに向かうに従って順次優先順位が低くなるものとする。



尚、各ワードW1~Wk内の各CAMセル103における一致検索は、次のようにして実行される。



まず、初期化動作を実行する。初期化動作では、検索ビット線対SL,SLNがともに‘L’(=‘0’)とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS 106,107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS 106,107のうちオン状態の方を介して、両者の間のノード109のレベルが‘L’となり、nMOS 108はオフ状態となる。この状態で、一致線MLが‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「一致」を表す。



次に、検索ビット線を介して比較レジスタ101に記憶された入力ベクトルの各ビットが各CAMセル103に入力される。これにより、入力ベクトルSに応じて、検索ビット線対SL,SLNの何れか一方が‘H’、他方が‘L’となる。



メモリ・セル104に記憶されているデータDと入力ベクトルSとが一致する場合、ノード109のレベルは‘L’であり、nMOS 108はオフ状態に保持される。



一方、データDと入力ベクトルSとが一致しない場合、ノード109のレベルは‘H’となり、nMOS 108はオン状態になる。これにより、一致線MLはディスチャージされて‘L’状態となる。



nビットのCAMセル103からなるCAMワードの一致線MLは、各CAMセル103のnMOS 108がパラレルに接続されたワイヤードOR回路を構成している。従って、1ワードを構成するnビットのCAMセル103のすべてにおいて一致が検出された場合に限り、一致線MLは‘H’(「一致」)の状態に保持される。一方、1ビットでもCAMセル103で不一致が検出されると、一致線MLは‘L’(「不一致」)の状態となる。



例えば、検索の結果、一致フラグレジスタMFR1~MFRkに、一致フラグとして‘0’,‘1’,‘1’,‘0’,…,‘1’,‘0’が格納されたとする。この場合、ワードW2,W3,…,Wk-1で一致が検出されている。従って、プライオリティ・エンコーダPEは、最も優先順位が高いワードW2のアドレスをHMAとして出力する。また、一致フラグレジスタMFR2に格納された一致フラグを‘0’にクリアすることで、その次に優先順位が高いワードW3のアドレスをHMAとして出力することができる。以下同様にして、一致が検出されたワードのアドレスを順次出力することができる。



図11は、図9のCAMセルの別の例の構成回路図である。図11に示すCAMセル103’は一致検出型のものであり、図10と同様、SRAM構成のメモリ・セル104及び一致比較回路105を備えている。CAMセル103’は、図10のCAMセル103において、一致比較回路105のnMOS 108の接続が異なる。図11のnMOS 108は、一致線MLaと一致線MLbとの間に接続されている。nMOS 108のゲートは、nMOS 106,107の間のノード109に接続されている。



CAMセル103’では、検索時には、初期化動作として、ビット線対SL,SLNが共に‘H’とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS 106,107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS 106,107のうちオン状態の方を介して、両者の間のノード109のレベルが‘H’となり、nMOS 108はオン状態となる。この状態で、一致線MLの一端が‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「不一致」を表す。



nビットのCAMセル103’からなるCAMワードの一致線MLは、各CAMセル103’のnMOS 108がシリアルに接続されたAND回路を構成する。従って、各々のCAMセルの一致線MLa,MLbは、各々のCAMセル103’のnMOS 108を介して‘H’にプリチャージされる。



その後、検索ビット線を介して比較レジスタ101に記憶された入力ベクトルの各ビットが各CAMセル103’に入力される。これにより、入力ベクトルSに応じて、検索ビット線対SL,SLNの何れか一方が‘H’、他方が‘L’となる。



メモリ・セル104に記憶されているデータDと入力ベクトルSとが一致する場合、ノード109のレベルは‘H’であり、nMOS 108はオン状態に保持される。



一方、データDと入力ベクトルSとが一致しない場合、ノード109のレベルは‘L’となり、nMOS 108はオフ状態になる。



CAMワードのnビットのCAMセル103’のすべての状態が確定した後、一致線MLの一方の端部からディスチャージを開始し、他方の端部で一致比較結果を判定する。このとき、1ビットでも不一致のCAMセル103’がある場合には、一致比較結果は‘H’、すなわち、不一致の状態に保持される。一方、すべてのCAMセル103’で一致が検出された場合のみ、一致比較結果は‘L’、すなわち一致状態となる。
【特許文献1】
特開2004-295967号公報
【特許文献2】
特願2003-389264号明細書
【特許文献3】
特開2004-258799号公報
【特許文献4】
米国特許第5,063,573号公報
【非特許文献1】
菅野卓雄監修,香山晋編,「超高速デバイス・シリーズ2 超高速MOSデバイス」,初版,培風館,1986年2月,pp.324-325.
【非特許文献2】
電子情報通信学会編,「LSIハンドブック」,第1版,オーム社,1994年11月,pp.523-525.
【非特許文献3】
Kostas Pagiamtzis and Ali Sheikholeslami, "A Low-Power Content-Addressable Memory (CAM) Using Pipelined Hierarchical Search Scheme", IEEE Journal of Solid-State Circuits, Vol.39, No.9, Sept.2004, pp.1512-1519.
【非特許文献4】
T.Sasao, M.Matsuura, and Y.Iguchi, "A cascade realization of multi-output function for reconfigurable hardware", International Workshop on Logic and Synthesis (IWLS01), Lake Tahoe, CA, June 12-15, 2001, pp.225-230.
【非特許文献5】
T.Sasao and M.Matsuura, "BDD representation for incompletely specified multiple-output logic functions and its applications to functional decomposition," Design Autonmation Conference, June 2005, (pp.373-378).

Field of industrial application (In Japanese)


本発明は、入力ベクトルに対し対応する固有アドレスを出力するアドレス生成器に関し、特に、書き換えが容易で且つ小面積で実装可能なアドレス生成器に関する。

Scope of claims (In Japanese)
【請求項1】
 
入力される2値ベクトル(以下「入力ベクトル」という。)Xに対し、当該入力ベクトルXが登録ベクトルの場合にはそれに対応する固有アドレスAを出力し、それ以外の場合には無効値を出力するアドレス生成関数f(X)の演算を行うアドレス生成器であって、
A.1乃至複数個設けられ、前記入力ベクトルXが前記登録ベクトル集合の所定の部分集合に属す場合にはそれに対応する固有アドレスAを出力し、それ以外の場合には無効値を出力する主アドレス生成器と、
B.すべての前記主アドレス生成器の出力が無効値となり且つ前記登録ベクトル集合に属す前記入力ベクトルXに対しては、対応する固有アドレスAを出力し、それ以外には無効値又は入力ベクトルXに対応する固有アドレスAを出力する副アドレス生成関数f2(X)の演算を行う副アドレス生成器と、
C.主アドレス生成器又は副アドレス生成器の出力値が無効値以外であればその値を固有アドレスAとして出力し、それ以外の場合は無効値を出力する出力合成器と、
を備え、
前記各主アドレス生成器は、
a.前記入力ベクトルXの所定の分割(X1i,X2i)(iは各主アドレス生成器を識別するインデックス)に対し束縛変数X1iをハッシュ化し、ハッシュ化された束縛変数Y1iを出力するハッシュ回路と、
b.前記束縛変数Y1iに対する割り当てに対し、前記固有アドレスAが一対一対応する場合(ハッシュ衝突が生じない場合)には当該固有アドレスAを仮アドレスA’として出力し、それ以外の場合(ハッシュ衝突が生じる場合)には任意の値又は対応する固有アドレスAの何れか一つを仮アドレスA’として出力する仮アドレス生成器と、
c.アドレス生成関数f(X)の逆関数であるデータ再生関数f-1(A)の演算を行う演算器であって、前記仮アドレス生成器が出力する仮アドレスA’が入力されると、それに対応する再生ベクトルX”=f-1(A’)を出力するデータ再生器と、
d.前記再生ベクトルX”と前記入力ベクトルXとを比較し、両者が一致する場合には前記仮アドレスA’を出力し、それ以外の場合には無効値を出力する固有アドレス検出器と、
を備え
前記副アドレス生成器は、カスケード状に接続された複数の部分関数メモリを備えたLUTカスケード論理回路により構成されており、
前記各部分関数メモリには、前記副アドレス生成関数f2(X)を関数分解して得られる複数の部分関数がLUTとして格納されていることを特徴とするアドレス生成器。

【請求項2】
 
前記副アドレス生成器は、すべての前記主アドレス生成器において前記ハッシュ化された束縛変数Y1iがハッシュ衝突を生じる入力ベクトルXに対しては、当該入力ベクトルXに対応する前記固有アドレスAを出力し、それ以外の場合には無効値を出力するものであることを特徴とする請求項1記載のアドレス生成器。

【請求項3】
 
前記仮アドレス生成器は、前記ハッシュ化された束縛変数Y1においてハッシュ衝突が生じない場合には、当該束縛変数Y1に対応する固有アドレスAを前記仮アドレスA’として出力する仮アドレス生成関数が、ルックアップ・テーブル(LUT)として格納されたハッシュ・メモリであることを特徴とする請求項1記載のアドレス生成器。

【請求項4】
 
前記データ再生器は、前記データ再生関数f-1(A)が、LUTとして格納された補助メモリであることを特徴とする請求項1記載のアドレス生成器。
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2008510866thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close