TOP > 国内特許検索 > アドレス生成器 > 明細書

明細書 :アドレス生成器

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4892693号 (P4892693)
登録日 平成24年1月6日(2012.1.6)
発行日 平成24年3月7日(2012.3.7)
発明の名称または考案の名称 アドレス生成器
国際特許分類 G11C  15/04        (2006.01)
G06F   7/00        (2006.01)
FI G11C 15/04 D
G11C 15/04 E
G06F 7/00 204
請求項の数または発明の数 4
全頁数 43
出願番号 特願2008-510866 (P2008-510866)
出願日 平成19年3月27日(2007.3.27)
国際出願番号 PCT/JP2007/056497
国際公開番号 WO2007/119539
国際公開日 平成19年10月25日(2007.10.25)
優先権出願番号 2006101104
優先日 平成18年3月31日(2006.3.31)
優先権主張国 日本国(JP)
審査請求日 平成21年7月3日(2009.7.3)
特許権者または実用新案権者 【識別番号】504174135
【氏名又は名称】国立大学法人九州工業大学
発明者または考案者 【氏名】笹尾 勤
個別代理人の代理人 【識別番号】100121371、【弁理士】、【氏名又は名称】石田 和人
審査官 【審査官】堀江 義隆
参考文献・文献 特開2004-229163(JP,A)
特開昭64-76320(JP,A)
Hui Qin,Tsutomu Sasao,Jon.T.Butler,Implementation of LPM address generatorson FPGAs,Reconfigurable Computing: Architectures and Applications. SecondInternational Workshop, ARC 2006. (L,2006年 3月 3日,p.170-181,URL,http://www.lsi-cad.com/sasao/Papers/files/ARC2006_qin.pdf
調査した分野 G11C 15/04
G06F 7/00
G06F 17/30
特許請求の範囲 【請求項1】
入力される2値ベクトル(以下「入力ベクトル」という。)Xに対し、当該入力ベクトルXが登録ベクトルの場合にはそれに対応する固有アドレスAを出力し、それ以外の場合には無効値を出力するアドレス生成関数f(X)の演算を行うアドレス生成器であって、
A.1乃至複数個設けられ、前記入力ベクトルXが前記登録ベクトル集合の所定の部分集合に属す場合にはそれに対応する固有アドレスAを出力し、それ以外の場合には無効値を出力する主アドレス生成器と、
B.すべての前記主アドレス生成器の出力が無効値となり且つ前記登録ベクトル集合に属す前記入力ベクトルXに対しては、対応する固有アドレスAを出力し、それ以外には無効値又は入力ベクトルXに対応する固有アドレスAを出力する副アドレス生成関数f(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カスケード論理回路により構成されており、
前記各部分関数メモリには、前記副アドレス生成関数f(X)を関数分解して得られる複数の部分関数がLUTとして格納されていることを特徴とするアドレス生成器。
【請求項2】
前記副アドレス生成器は、すべての前記主アドレス生成器において前記ハッシュ化された束縛変数Y1iがハッシュ衝突を生じる入力ベクトルXに対しては、当該入力ベクトルXに対応する前記固有アドレスAを出力し、それ以外の場合には無効値を出力するものであることを特徴とする請求項1記載のアドレス生成器。
【請求項3】
前記仮アドレス生成器は、前記ハッシュ化された束縛変数Yにおいてハッシュ衝突が生じない場合には、当該束縛変数Yに対応する固有アドレスAを前記仮アドレスA’として出力する仮アドレス生成関数が、ルックアップ・テーブル(LUT)として格納されたハッシュ・メモリであることを特徴とする請求項1記載のアドレス生成器。
【請求項4】
前記データ再生器は、前記データ再生関数f-1(A)が、LUTとして格納された補助メモリであることを特徴とする請求項1記載のアドレス生成器。
発明の詳細な説明 【技術分野】
【0001】
本発明は、入力ベクトルに対し対応する固有アドレスを出力するアドレス生成器に関し、特に、書き換えが容易で且つ小面積で実装可能なアドレス生成器に関する。
【背景技術】
【0002】
k個(kは自然数)の異なる2値ベクトルの集合を登録ベクトル集合(set of registered vectors)とする。登録ベクトル集合の各要素と一致する入力に対して1からkまでの固有アドレス(intrinsic address)に単射し、それ以外の入力に対して0となる関数をアドレス生成関数(address generation function)という。また、アドレス生成関数の演算を行う回路をアドレス生成器(address generator)という。アドレス生成器に入力されるベクトルを、入力ベクトル(input vector)という。入力ベクトルがn次元ベクトルであるアドレス生成関数を、n入力のアドレス生成関数という。また、n入力のアドレス生成関数の演算を行う回路をn入力のアドレス生成器という。
【0003】
アドレス生成器は、連想メモリ又は内容検索メモリ(Content Addressable Memory:CAM)とも呼ばれ、パターン・マッチング、インターネットのルータ、プロセッサのキャッシュ、TLB(Translation Lookaside Buffer)、データ圧縮、データベースのアクセラレータ、ニューラルネット、メモリパッチなど幅広い分野において利用されている。
【0004】
アドレス生成器の機能をソフトウェアで実現することも可能であるが、ソフトウェアで実現したものは大幅に低速である。そのため、専用のハードウェア(半導体メモリ)を用いてアドレス生成器を実現することが多い。以下、ハードウェアで構成された従来のアドレス生成器について説明する。
【0005】
図9は、従来のアドレス生成器(CAM)の基本構成の一例を表すブロック図である(特許文献1参照)。アドレス生成器100は、比較レジスタ101、検索ビット線ドライバ102、k個のワードW~W、k個の一致センス回路MSC~MSC、k個の一致フラグレジスタMFR~MFR、及びプライオリティ・エンコーダ(優先度付符号化回路)PEを備えている。
【0006】
比較レジスタ101は、nビットの入力ベクトルを格納するレジスタである。検索ビット線ドライバ102は、比較レジスタ101の各ビットを検索ビット線上にドライブする。各ワードW~Wは、それぞれnビットのCAMセルを備えている。
【0007】
図10は、図9のCAMセルの構成回路図である。図10に例示したCAMセル103は、不一致検出型のものである。CAMセル103は、メモリ・セル104及び一致比較回路105から構成される。メモリ・セル104は、1ビットのデータを記憶するSRAM構成のメモリ・セルである。図10においてDがデータ、DNが反転データを表す。一致比較回路105は、メモリ・セル104に記憶された1ビットのデータと検索ビット線対SL,SLN上にドライブされる入力ベクトルとを比較し、その一致比較結果を一致線ML上に出力する。
【0008】
一致比較回路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に接続されている。
【0009】
まず、検索を行う前に、アドレス生成器100のそれぞれのワードW~Wに、検索対象である登録ベクトルが記憶される。各ワード内の各CAMセル103において、メモリ・セル104へのデータの書き込み及びメモリ・セル104からのデータの読み出しは、通常のSRAMと同様にして行われる。
【0010】
検索時には、まず、比較レジスタ101に入力ベクトルが格納される。入力ベクトルの各のビットは、検索ビット線ドライバ102により、各々対応する検索ビット線上にドライブされる。
【0011】
各々のワードW~Wでは、各CAMセル103に予め記憶されている登録ベクトルと検索ビット線上にドライブされた入力ベクトルとの一致検索が同時(並列)に実行され、その結果が一致線ML~ML上に出力される。これらの検索結果は、それぞれ一致センス回路MSC~MSCに入力される。各一致センス回路MSC~MSCは、各検索結果を増幅し、一致センス出力として一致センス出力線MT~MTに出力する。各一致センス出力は、一致フラグレジスタMFR~MFRに格納され、一致フラグ出力として一致フラグ出力出力線MF~MFに出力される。一致フラグは、‘1’が「一致あり」、‘0’が「一致なし」を表すものとする。
【0012】
各一致フラグ出力は、プライオリティ・エンコーダPEに入力される。プライオリティ・エンコーダPEでは、所定の優先順位付けに従って、一致が検出されたワードの中から最優先順位のワードのアドレス(最優先一致アドレス:HMA)を選択し出力する。各ワードの優先順位は、ワードWが最も高く、Wに向かうに従って順次優先順位が低くなるものとする。
【0013】
尚、各ワードW~W内の各CAMセル103における一致検索は、次のようにして実行される。
【0014】
まず、初期化動作を実行する。初期化動作では、検索ビット線対SL,SLNがともに‘L’(=‘0’)とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS 106,107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS 106,107のうちオン状態の方を介して、両者の間のノード109のレベルが‘L’となり、nMOS 108はオフ状態となる。この状態で、一致線MLが‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「一致」を表す。
【0015】
次に、検索ビット線を介して比較レジスタ101に記憶された入力ベクトルの各ビットが各CAMセル103に入力される。これにより、入力ベクトルSに応じて、検索ビット線対SL,SLNの何れか一方が‘H’、他方が‘L’となる。
【0016】
メモリ・セル104に記憶されているデータDと入力ベクトルSとが一致する場合、ノード109のレベルは‘L’であり、nMOS 108はオフ状態に保持される。
【0017】
一方、データDと入力ベクトルSとが一致しない場合、ノード109のレベルは‘H’となり、nMOS 108はオン状態になる。これにより、一致線MLはディスチャージされて‘L’状態となる。
【0018】
nビットのCAMセル103からなるCAMワードの一致線MLは、各CAMセル103のnMOS 108がパラレルに接続されたワイヤードOR回路を構成している。従って、1ワードを構成するnビットのCAMセル103のすべてにおいて一致が検出された場合に限り、一致線MLは‘H’(「一致」)の状態に保持される。一方、1ビットでもCAMセル103で不一致が検出されると、一致線MLは‘L’(「不一致」)の状態となる。
【0019】
例えば、検索の結果、一致フラグレジスタMFR~MFRに、一致フラグとして‘0’,‘1’,‘1’,‘0’,…,‘1’,‘0’が格納されたとする。この場合、ワードW,W,…,Wk-1で一致が検出されている。従って、プライオリティ・エンコーダPEは、最も優先順位が高いワードWのアドレスをHMAとして出力する。また、一致フラグレジスタMFRに格納された一致フラグを‘0’にクリアすることで、その次に優先順位が高いワードWのアドレスをHMAとして出力することができる。以下同様にして、一致が検出されたワードのアドレスを順次出力することができる。
【0020】
図11は、図9のCAMセルの別の例の構成回路図である。図11に示すCAMセル103’は一致検出型のものであり、図10と同様、SRAM構成のメモリ・セル104及び一致比較回路105を備えている。CAMセル103’は、図10のCAMセル103において、一致比較回路105のnMOS 108の接続が異なる。図11のnMOS 108は、一致線MLと一致線MLとの間に接続されている。nMOS 108のゲートは、nMOS 106,107の間のノード109に接続されている。
【0021】
CAMセル103’では、検索時には、初期化動作として、ビット線対SL,SLNが共に‘H’とされる。一方、メモリ・セル104に記憶されているデータに応じて、一致比較回路105のnMOS 106,107のうち一方がオン状態、他方がオフ状態となる。従って、nMOS 106,107のうちオン状態の方を介して、両者の間のノード109のレベルが‘H’となり、nMOS 108はオン状態となる。この状態で、一致線MLの一端が‘H’(=‘1’)状態にプリチャージされる。尚、一致線MLは‘H’が「不一致」を表す。
【0022】
nビットのCAMセル103’からなるCAMワードの一致線MLは、各CAMセル103’のnMOS 108がシリアルに接続されたAND回路を構成する。従って、各々のCAMセルの一致線ML,MLは、各々のCAMセル103’のnMOS 108を介して‘H’にプリチャージされる。
【0023】
その後、検索ビット線を介して比較レジスタ101に記憶された入力ベクトルの各ビットが各CAMセル103’に入力される。これにより、入力ベクトルSに応じて、検索ビット線対SL,SLNの何れか一方が‘H’、他方が‘L’となる。
【0024】
メモリ・セル104に記憶されているデータDと入力ベクトルSとが一致する場合、ノード109のレベルは‘H’であり、nMOS 108はオン状態に保持される。
【0025】
一方、データDと入力ベクトルSとが一致しない場合、ノード109のレベルは‘L’となり、nMOS 108はオフ状態になる。
【0026】
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).
【発明の開示】
【発明が解決しようとする課題】
【0027】
n入力のアドレス生成関数は、通常、出力値が非零となる入力ベクトルの数kが、n次元ベクトルのすべての組み合わせの数2に比べて十分に小さい、いわゆる疎な論理関数(sparse logic function)である。
【0028】
例えば、n=128,k=40000の登録ベクトル集合について考える。この場合、入力ベクトルの取り得る場合の数に対する登録ベクトルの数の割合は、40000/2128=1.17549×10-34である。この登録ベクトル集合に対するアドレス生成器を実現する最も単純な方法は、真理値表である。しかし、このような真理値表を直接メモリに記憶するのは、メモリが大きくなりすぎるため現実的ではない。
【0029】
また、上述の従来のアドレス生成器や2段論理回路,PLA(Programmable Logic Array)でも実現可能である。しかし、この登録ベクトル集合では、LSIにした場合、チップ面積や消費電力が大きくなりすぎるという問題がある。また、上述の従来のアドレス生成器は、RAMに比べると1ビットあたりの価格(ビットコスト)が高価となる。
【0030】
例えば、上記従来のアドレス生成器は、RAMに比べると、並列に検索可能であるため高速であるが、デバイスの構成は複雑となる。そのため、このアドレス生成器の1ビットあたりの価格(ビットコスト)は、RAMに比べる高価なものになる。
【0031】
また、1ビットあたりの消費電力がRAMに比べて遙かに大きい(非特許文献3参照)。これは、上で説明したように、すべてのCAMセルを同時にアクセスするためである。そのため、1ビットあたりの消費電力は、通常のRAMの数十倍程度にもなる。
【0032】
そこで、本発明の目的は、検索の高速性を維持しつつも、消費電力を抑え且つデバイスの構造を簡単化して小面積で実装することが可能なアドレス生成器を提供することにある。
【課題を解決するための手段】
【0033】
本発明の構成を説明する前に、まず、本明細書において使用する用語を定義し、本発明の基本原理について説明する。
【0034】
〔1〕用語の定義及びいくつかの定理
〔定義1〕(アドレス生成関数)
関数f(X):B→{0,1,…,k}(B={0,1},k∈自然数)において、k個の異なる登録ベクトルa∈B(i=1,2,…,k)に対してf(a)=i(i=1,2,…,k)が成立し、それ以外の(2-k)個の入力ベクトルaに対しては、f(a)=0が成立するとき、f(X)を重みkのアドレス生成関数(address generation function)という。アドレス生成関数は、k個の異なる2値ベクトルに対して、1からkまでの固有アドレスを生成する。
(定義終わり)
本明細書においては、kの値は入力ベクトルの組み合わせ総数2に比べて十分に小さい(k<<2)と仮定する。
【0035】
〔定義2〕(登録ベクトル,登録ベクトル表)
k個のnビットのベクトルの集合を考える。このベクトルの集合を登録ベクトル集合といい、登録ベクトル集合に属する各ベクトルを登録ベクトルという。登録ベクトル集合に属するすべての登録ベクトルに1からkまでの整数を1対1に対応させる表を登録ベクトル表という。
(定義終わり)
【0036】
(例1)
(表1)は、4ビットの7個の登録ベクトルからなる登録ベクトル表を示す。この登録ベクトル表に対応するアドレス生成関数を(表2)に示す。いずれも、登録ベクトルに一致した入力ベクトルに対応するアドレスを3ビットの数(例えば、‘001’)として出力する。入力ベクトルと一致する登録ベクトルが登録ベクトル表の中にない場合には、‘000’を出力する。
(例終わり)
【0037】



















【表1】
JP0004892693B2_000002t.gif

【0038】









































【表2】
JP0004892693B2_000003t.gif

【0039】
〔定義3〕(分割)
入力ベクトルをX=(x,x,…,x)とする。Xの変数の集合を{X}で表す。{X}∪{X}={X}且つ{X}∩{X}=φのとき、X=(X,X)をXの分割(partition)という。ここで、φは空集合を表す。
(定義終わり)
【0040】
〔定義4〕(分解表,基本分解表,列複雑度)
完全定義関数f(X):B→B(B={0,1},X=(x,x,…,x),n,q∈自然数)が与えられているとする。(X,X)をXの分割とする。Xの次元(変数の個数)をd(X)と記す。関数f(X)及びXの分割X=(X,X)に対して、以下の(1)~(3)の条件を満たす表をfの分解表という。
(1)2nL列2nH行の表である。ここで、n=d(X),n=d(X)とする。
(2)各行,各列に2進符号のラベルを持ち、列及び行のラベルの集合は、それぞれn,nビットのすべてのパターンを要素とする。
(3)表の各要素が、その要素に対応する列及び行のラベルの組み合わせ(X,X)に対するfの真理値f(X,X)である。
を束縛変数、Xを自由変数という。分解表の異なる列パターンの個数を分解表の列複雑度といい、μと記す。分解表の特別な場合として、X=X,X=φの場合も考える。
また、関数fの分解表のうちで、X=(x,x,…,xnL)且つX=(xnL+1,xnL+2,…,x)となるものを基本分解表という。
(定義終わり)
【0041】
(例2)
(表3)の分解表では、n=3,n=2,μ=2である。
(例終わり)
【0042】

















【表3】
JP0004892693B2_000004t.gif

【0043】
〔定義5〕(C尺度)
ベクトルXの変数の順序をX=(x,x,…,x)としたとき、論理関数f(X)の基本分解表の列複雑度の最大値をfのC尺度という。
(定義終わり)
【0044】
(例3)
=x∨x∨xのC尺度は3であるが、f=x∨x∨xのC尺度は8である。
(例終わり)
【0045】
分解表の列複雑度は、MTBDD(多端子二分決定グラフ)の幅に等しい。従って、論理関数のC尺度は、与えられた入力変数の順におけるMTBDDの幅の最大値に等しい。与えられた論理関数f(x1,x2,…,xn)に対して、C尺度は容易に計算でき、一意的に定まる。後述するように、C尺度が小さい関数は、LUTカスケードで効率的に実現可能である。従って、C尺度は、論理関数をLUTカスケードで実現する際の複雑さの尺度となる。
【0046】
〔補題1〕
重みkの論理関数fのC尺度は高々k+1である。
(補題終わり)
【0047】
〔定理1〕
与えられた関数f(X)に対して、Xを分解表の自由変数、Xを束縛変数とし、μを分解表の列複雑度とする。このとき、関数fは図1に示す回路で実現可能である。この場合、2つのブロックH,Gの間を結ぶ信号線数は高々
【0048】


【数1】
JP0004892693B2_000005t.gif
である。
(定理終わり)
【0049】
〔定義6〕(関数分解)
一つの関数f(X)=f(X,X)を分解し2つの関数G,H(但し、f(X)=(G(H(X)),X))として実現することを関数分解という。関数分解により得られる関数G,Hを分解の部分関数という。
(定義終わり)
【0050】
図1において、2つのブロック間を結ぶ信号線数がX中の変数の個数よりも少ないとき、関数を実現するためのメモリ量を削減できる可能性がある。与えられた関数を繰り返し関数分解することにより、図2に示すようなLUTカスケードが得られる。
【0051】
〔定義7〕(LUTカスケード)
一つの関数f(X)に対して関数分解を繰り返し行って得られる部分関数をG,G,…,Gと記す。
【0052】










【数2】
JP0004892693B2_000006t.gif
各部分関数G,G,…,Gをルックアップ・テーブル(LUT)で実現し、各LUTを信号線でカスケード接続したものをLUTカスケードという。各部分関数G,G,…,Gを表す各LUTをセルという。隣接するセル間を接続する信号線をレイルという。
(定義終わり)
【0053】
〔定理2〕
C尺度がμの論理関数は、入力数が高々q+1で、出力数がqのセルから構成されたLUTカスケードで実現可能である。ここで、
【0054】


【数3】
JP0004892693B2_000007t.gif
である。
(定理終わり)
【0055】
〔定理3〕
関数fを実現するLUTカスケードを考える。いまnを外部入力数、sをセル数、qを最大レイル数(セル間の信号線数)、pをセルの最大入力数、およびμを関数fのC尺度とする。
【0056】


【数4】
JP0004892693B2_000008t.gif
が成立するとき、以下の関係を満たす関数fを実現するLUTカスケードが存在する。
【0057】


【数5】
JP0004892693B2_000009t.gif
(定理終わり)
【0058】
重みがkのアドレス生成関数は、レイル数が
【0059】


【数6】
JP0004892693B2_000010t.gif
のLUTカスケードで実現可能である。しかし、kの値が大きいときは、単一のカスケードでは、セルが大きくなり過ぎ、実現困難となる。例えば、k=40000のとき、17入力16出力のセルが必要となる。この場合、ベクトルの集合をいくつかに分解して、各ベクトルの集合を別々のカスケードで実現すると、必要メモリ量を削減することが可能である。しかし、この場合には、複数のカスケードの出力を纏めるエンコーダが必要となる。
【0060】
〔2〕本発明の原理
(1)1個のハッシュ・メモリを使用する方法(ハイブリッド法(Hybrid Method))
重みkのアドレス生成関数f(X,X)において、入力変数(X,X)を(Y,X)と一次変換し、アドレス空間をハッシュ化する。ハッシュ化した後の関数
【0061】


【数7】
JP0004892693B2_000011t.gif
の分解表(図3)を考える。尚、以下では
【0062】


【数8】
JP0004892693B2_000012t.gif
のように「^」が付された表記をテキスト上では「f^」のように記す。Yの変数(束縛変数)の個数をpとする。非零要素が分解表で一様に分布していると仮定すると、2>kのとき、分解表は、平均すると各列に高々1個の非零要素を持つ。いま、簡単のために、分解表は各列に高々1個の非零要素を持つと仮定する。次に、
【0063】













【数9】
JP0004892693B2_000013t.gif
とし、h^(Y)をハッシュ・メモリ(Hash memory)3’で実現する(図5参照)。
【0064】
関数f^の入力は(Y,X)であるのに対し、h^(Y)はYの値のみでf^の値を予測するので、h^(Y)の値はf^とは異なる可能性がある。そこで、h^(Y)の値が正しいか否かを補助メモリ(auxiliary (AUX) memory)4’により検査する。補助メモリ4’の入力数は
【0065】


【数10】
JP0004892693B2_000014t.gif
で、出力数はnである(実際には、n-pまで削減できる)。補助メモリ4’の各アドレスに、対応する登録ベクトルを格納しておく。補助メモリ4’の出力と入力の検索パターンが等しい場合には、ハッシュ・メモリ3’は、正しい値を出力しており、ハッシュ・メモリ3’の出力値をそのまま出力する。等しくない場合は、ハッシュ・メモリ3’はf^と異なった値を出力しているので、0を出力する。
【0066】
ある列に、非零要素が2個以上ある場合(ハッシュ衝突がある場合)には、上記の方法は利用できないため、f^(Y,X)を
【0067】



【数11】
JP0004892693B2_000015t.gif
と関数分解し、関数f^(Y,X)の分解表の各列では非零要素が高々1個となるようにする。また、関数f^(Y,X)=f(X,X)に関しては、LUTカスケードや再構成可能PLA(例えば、特許文献4参照)等の再構成可能論理回路で実現する。ここで、f(X,X)は、f^(Y,X)のハッシュ化された束縛変数Yを束縛変数Xに変換して得られる関数を表す。
尚、関数f^(Y,X)を主アドレス生成関数(master address generation function)という。また、関数f(X,X)を副アドレス生成関数(slave address generation function)という。
【0068】
このアドレス生成器の特徴は、次の通りである。ハッシュ・メモリ3’は、アドレス生成関数を能率よく実現するが、ハッシュ衝突が起こるため、一部の登録ベクトルは表現することができない。一方、LUTカスケードや再構成可能PLA等の再構成可能論理回路は、アドレス生成関数を確実に実現するが、kの値が大きい場合には能率が悪い。そこで、図5のアドレス生成器は、これら2つの手法をうまく組み合わせてアドレス生成関数を能率よく実現できるようにしたものである。このアドレス生成器は、nの値が大きく、kの値が2に比べて十分に小さい場合に有効である。ハッシュ・メモリ3’と補助メモリ4’で、およそ90%の登録ベクトルの集合を実現し、残りの10%の登録ベクトルの集合をLUTカスケードや再構成可能PLA等の再構成可能論理回路 6’で実現する。
【0069】
(2)2個以上のハッシュ・メモリを使用する方法(スーパー・ハイブリッド法(Super Hybrid Method))
【0070】
入力変数Xに対してM個の異なる分割(X1i,X2i)(i=1,…,M)を考える。これらの各分割に対して、(1)と同様にアドレス空間をハッシュ化し、ハッシュ・メモリ3’と補助メモリ4’を用いてアドレス生成関数f^1i(Y1i,X2i)を実現する(図7参照)。そして、アドレス生成関数f^(Y,X)を
【0071】



【数12】
JP0004892693B2_000016t.gif
と関数分解し、主アドレス生成関数f^1i(Y1i,X2i)の分解表の各列では非零要素が高々1個となるようにする。また、副アドレス生成関数f^(Y,X)=f(X,X)に関しては、LUTカスケードや再構成可能PLA等の再構成可能論理回路で実現する。ここで、f(X,X)は、f^(Y,X)のハッシュ化された束縛変数Yを束縛変数Xに変換して得られる関数を表す。
【0072】
一例として、k=2の場合(図7参照)を考えると、分割(X11,X21),(X12,X22)(図7においては、X11=X,X21=X,X12=X’,X22=X’と記す。)に対して、2つのハッシュ・メモリ3’、3’及び2つの補助メモリ4’、4’を用いて、主アドレス生成関数f^11(Y11,X21),f^12(Y12,X22)を実現したとする。主アドレス生成関数f^11(Y11,X21)は、登録ベクトルのうちの約80%に対してアドレスAを返し、f^12(Y12,X22)は、登録ベクトルのうち約16%に対してアドレスAを返す。Y11,Y12のハッシュ化が完全にランダムに行われた場合、主アドレス生成関数f^11(Y11,X21),f^12(Y12,X22)により、すべての登録ベクトルのうちの約96%の登録ベクトルに対してアドレス生成関数が実現される。したがって、副アドレス生成関数f(X,X)は残りの約4%の登録ベクトルに対してアドレス生成関数を実現すればよい。したがって、再構成可能論理回路で実現すべき副アドレス生成関数f(X,X)は、ハイブリッド法に比べて更に小さくなり、より小規模な回路により実現することが可能となる。
【0073】
(例4)
重みがkのn変数のアドレス生成関数f(X)を考える。
【0074】
〔ハイブリッド法〕
ハイブリッド法の場合、ハッシュ・メモリ3’の入力数はp=q+2,出力数はqである。ここで、qは式(3)により表される。また、補助メモリの入力数はq,出力数は(n-q-2)である。従って、総メモリ量は、
【0075】


【数13】
JP0004892693B2_000017t.gif
となる。
【0076】
〔スーパー・ハイブリッド法〕
スーパー・ハイブリッド法の場合、第1のハッシュメモリの入力数は(q+1),出力数はq、第1の補助メモリの入力数はq,出力数は(n-q-1)、第2のハッシュメモリの入力数は(q-1),出力数は(q-2)、第2の補助メモリの入力数は(q-2),出力数は(n-q+2)である。従って、総メモリ量は、
【0077】


【数14】
JP0004892693B2_000018t.gif
となる。
【0078】
上の2つの式より、
【0079】


【数15】
JP0004892693B2_000019t.gif
が成立するとき、スーパー・ハイブリッド法の方が、ハイブリッド方よりも、必要メモリ量が少なくなる。
(例終わり)
【0080】
〔3〕本発明の構成
本発明に係るアドレス生成器の第1の構成は、
入力される2値ベクトル(以下「入力ベクトル」という。)Xに対し、当該入力ベクトルXが登録ベクトルの場合にはそれに対応する固有アドレスAを出力し、それ以外の場合には無効値を出力するアドレス生成関数f(X)の演算を行うアドレス生成器であって、
A.1乃至複数個設けられ、前記入力ベクトルXが前記登録ベクトル集合の所定の部分集合に属す場合にはそれに対応する固有アドレスAを出力し、それ以外の場合には無効値を出力する主アドレス生成器と、
B.すべての前記主アドレス生成器の出力が無効値となり且つ前記登録ベクトル集合に属す前記入力ベクトルXに対しては、対応する固有アドレスAを出力し、それ以外には無効値又は入力ベクトルXに対応する固有アドレスAを出力する副アドレス生成関数f(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’を出力し、それ以外の場合には無効値を出力する固有アドレス検出器と、
を備えたことを備えたことを特徴とする。
【0081】
この構成によれば、アドレス生成器に外部から入力ベクトルXが入力された場合、ハッシュ回路が入力ベクトルX=(X1i,X2i)に対し束縛変数X1iをハッシュ化し、ハッシュ化された束縛変数Y1iとして出力する。ここで、X=(X1i,X2i)はXの分割とする。また、ハッシュ化により束縛変数X1iはY1iに変換され、入力ベクトルXはハッシュ入力ベクトルXi’=(Y1i,X2i)となる。
【0082】
次に、仮アドレス生成器は、Y1iについてハッシュ衝突が生じない場合にはY1iに対応する固有アドレスAを仮アドレスA’として出力する。ハッシュ衝突が生じる場合には任意の値又は対応する固有アドレスAのうちの何れか一つを、仮アドレスA’として出力する。データ再生器は、得られた仮アドレスA’からそのアドレスに対応する再生ベクトルX”=f-1(A’)を出力する。固有アドレス検出器は、X”とXを比較し、両者が一致する場合には仮アドレスA’を出力する。それ以外の場合には無効値を出力する。これにより、固有アドレス検出器からは、入力ベクトルXに対して正しい固有アドレスA又は無効値が出力される。
【0083】
一方、副アドレス生成器は、固有アドレス検出器の出力が無効値となる入力ベクトルXに対しては、Xに対応する正しい固有アドレスA=f(X)(固有アドレスがない場合は無効値)を出力する。一方、固有アドレス検出器の出力が無効値以外となる場合には、無効値を出力するか、又はXに対応する正しい固有アドレスA=f(X)を出力する。
【0084】
最後に、出力合成器は、固有アドレス検出器の出力値及び副アドレス生成器の出力値のうち無効値でないものがあれば、それを固有アドレスAとして出力する。両者とも無効値の場合は無効値を出力する。これにより、入力ベクトルXに一致する登録ベクトルがあれば、出力合成器からは、Xに対する正しい固有アドレスAが出力される。
【0085】
入力ベクトルXを一旦ハッシュ化することにより、アドレス生成関数A=f(X)=f(X1i,X2i)は、A=f^(Y1i,X2i)に変換される。固有アドレスAの数kがn次元の入力ベクトルXの組み合わせの数2に対して十分に小さい場合、Y1iに対応するAの数は平均して高々1個となる。すなわち、ハッシュ関数をうまく選択すれば、Y1iの割り当てとAとはほぼ一対一対応の関係となる。そこで、ハッシュ化の際に使用するハッシュ関数を、Y1iの値を用いて、Aを一意的に決定できる確率をできるだけ大きくなるように選択する。そうすれば、大部分のAは、束縛変数Y1iの関数A=G(Y1i)として表される。Gの入力ベクトルY1iの要素数が入力ベクトルXの要素数に比べて少ないため、仮アドレス生成器は小規模な回路で実現することができる。
【0086】
そして、残りのハッシュ衝突を生じる入力ベクトルXについては、副アドレス生成器において、AをXの全要素の関数として計算する。このとき、Xはハッシュ衝突を生じるものに限定されているため、副アドレス生成器で計算することが必要なAの組み合わせの数は少ない。従って、副アドレス生成器は小規模な回路により実現することができる。
【0087】
故に、全体として、アドレス生成器全体の回路規模を小さくすることができ、消費電力を抑えることができる。また、デバイスの構造を簡単化し、小面積で実装することが可能となる。
【0088】
また、主アドレス生成器を2つ以上備える場合には、各主アドレス生成器での分割(X1i,X2i)を互いに異なる分割とすることで、主アドレス生成器が1つの場合に比べて、主アドレス生成器によりアドレス生成関数が実現される登録ベクトルの割合が大きくなる。したがって、副アドレス生成器によりアドレス生成関数を実現すべき登録ベクトルの数を減らすことができ、より小規模な回路でアドレス生成器を構成することが可能となる。
【0089】
ここで、「2値ベクトル(binary vector)」とは、ベクトルの各成分が2値であるベクトルをいう。
【0090】
「ハッシュ化(hashing)」とは、アドレス生成関数の分解表において非零要素が多くの列に分散するように、入力ベクトルXの一部又は全部のベクトル成分の順序を置換することをいう。「ハッシュ衝突(hash collision)が生じる」とは、ハッシュ入力ベクトルX’のベクトル成分からハッシュ化されていないベクトル成分を除いた束縛変数Yの割り当てに対し、複数の固有アドレスAが対応することをいう。
【0091】
「データ再生関数(data-regeneration function)」とは、アドレス生成関数f(X)の逆関数、すなわち、固有アドレスAをそれに対応する入力ベクトルXに写像する関数をいう。
【0092】
「無効値(invalid value)」とは、アドレスが無効である(存在しない)ことを表す値をいう。無効値としては、アドレスのすべての成分を0としたもの,すべての成分を1としたもの,実際に存在しないアドレス値としたものなどが使用される。
【0093】
「副アドレス生成関数(slave address generation function)」とは、前記固有アドレス検出器が無効値を出力する場合には、当該入力ベクトルXに対しアドレス生成関数f(X)の演算値を出力し、それ以外の場合には無効値又はアドレス生成関数f(X)の演算値を出力する関数をいう。すなわち、副アドレス生成関数は、前者の場合には、当該入力ベクトルXをそれに対応する固有アドレスAに写像し、後者の場合には無効値又は当該入力ベクトルXに対応する固有アドレスAに写像する。
【0094】
副アドレス生成器としては、LUTカスケード、その他の論理回路を使用することができる。
【0095】
本発明に係るアドレス生成器の第2の構成は、前記第1の構成において、前記副アドレス生成器は、前記主アドレス生成器のいずれかにおいて前記ハッシュ化された束縛変数Y1iがハッシュ衝突を生じる入力ベクトルXに対しては、当該入力ベクトルXに対応する前記固有アドレスAを出力し、それ以外の場合には無効値を出力するものであることを特徴とする。
【0096】
この構成によれば、副アドレス生成器は、ハッシュ衝突を生ずる場合には正しい固有アドレスを出力し、ハッシュ衝突を生じない場合には、常に無効値を出力する。従って、副アドレス生成器は、ハッシュ衝突が生じる場合のXを調べ、その結果得られるいくつかのXに対して固有アドレスAを演算するように構成すればよい。従って、副アドレス生成器における論理演算回路の構成が容易となる。
【0097】
本発明に係るアドレス生成器の第3の構成は、前記第1の構成において、前記仮アドレス生成器は、前記ハッシュ化された束縛変数Yにおいてハッシュ衝突が生じない場合には、当該束縛変数Yに対応する固有アドレスAを前記仮アドレスA’として出力する仮アドレス生成関数が、ルックアップ・テーブル(LUT)として格納されたハッシュ・メモリであることを特徴とする。
【0098】
このように、仮アドレス生成器をハッシュ・メモリで構成することにより、演算速度を高速に維持しつつも、メモリの書き換えによる再構成も簡単に行うことが可能である。
【0099】
本発明に係るアドレス生成器の第4の構成は、前記第1の構成において、前記データ再生器は、前記データ再生関数f-1(A)が、LUTとして格納された補助メモリであることを特徴とする。
【0100】
このように、データ再生器を補助メモリで構成することにより、演算速度を高速に維持しつつも、メモリの書き換えによる再構成も簡単に行うことが可能である。
【0101】
本発明に係るアドレス生成器の第5の構成は、前記第1の構成において、前記副アドレス生成器は、カスケード状に接続された複数の部分関数メモリを備えたLUTカスケード論理回路により構成されており、
前記各部分関数メモリには、前記副アドレス生成関数f(X)を関数分解して得られる複数の部分関数がLUTとして格納されていることを特徴とする。
【0102】
このように、副アドレス生成器をLUTカスケード論理回路で構成することにより、演算速度を高速に維持しつつも、回路規模も、PLA(プログラマブル・ロジック・アレイ)で構成する場合に比べて小規模化することができる。また、メモリの書き換えによる再構成も簡単に行うことが可能である。
【発明の効果】
【0103】
以上のように、本発明によれば、入力ベクトルをハッシュするハッシュ回路及びハッシュ入力ベクトルから固有アドレスを出力する仮アドレス生成器を備えるとともに、仮アドレス生成器で計算できない固有アドレスを計算するための副アドレス生成器を備え、仮アドレス生成器及び副アドレス生成器を相補的に組み合わせて固有アドレスの生成を行う構成とした。これにより、アドレス生成器全体の回路規模を小さくすることができ、消費電力を抑え且つデバイスの構造を簡単化して小面積で実装することが可能となる。
【0104】
また、仮アドレス生成器やデータ再生器をLUTを格納したメモリで構成し、副アドレス生成器をLUTカスケードにより構成することで、演算速度を高速に維持しつつも、メモリの書き換えによる再構成も簡単に行うことが可能である。
【図面の簡単な説明】
【0105】
【図1】論理関数を関数分解により実現した場合を表す図である。
【図2】中間出力を有するLUTカスケードを表す図である。
【図3】ハッシュ化関数f^(Y,X)の分解表を表す概念図である。
【図4】本発明の実施例1に係るアドレス生成器の機能構成を表すブロック図である。
【図5】図4のアドレス生成器1の具体的なハードウェア構成を表すブロック図である。
【図6】6変数関数をハッシュ・メモリで実現した例を示す図である。
【図7】本発明の実施例1に係るアドレス生成器のハードウェア構成を表すブロック図である。
【図8】レジスタとゲートを用いた再構成可能PLA 6’の構成を表す図である。
【図9】従来のアドレス生成器(CAM)の基本構成の一例を表すブロック図である。
【図10】図6のCAMセルの構成回路図である。
【図11】図6のCAMセルの別の例の構成回路図である。
【符号の説明】
【0106】
1,1’ アドレス生成器
2 ハッシュ回路
3 仮アドレス生成器
3’ ハッシュ・メモリ
4 データ再生器
4’ 補助メモリ(AUX memory)
5 固有アドレス検出器
6 副アドレス生成器
6’ LUTカスケード
6” 再構成可能PLA
7 出力合成器
7’ OR回路
8,8’ 主アドレス生成器
10 比較回路
11 AND回路
15 レジスタ
16 EXNORゲート
17 ANDゲート
【発明を実施するための最良の形態】
【0107】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例1】
【0108】
本実施例では、主アドレス生成器が1個の場合(ハイブリッド法)について説明する。
【0109】
〔1〕アドレス生成器の構成
図4は、本発明の実施例1に係るアドレス生成器の機能構成を表すブロック図である。本実施例に係るアドレス生成器1は、ハッシュ回路2、仮アドレス生成器3、データ再生器4、固有アドレス検出器5、副アドレス生成器6、及び出力合成器7を備えている。
【0110】
アドレス生成器1は、重みkのアドレス生成関数f(X)の演算を行う演算器である。すなわち、アドレス生成器1は、外部から入力ベクトルXが入力されると、入力ベクトルXに対応する登録ベクトルがある場合にはその登録ベクトルの固有アドレスAを出力する。それ以外の場合には無効値0を出力する。
【0111】










【数16】
JP0004892693B2_000020t.gif

【0112】
ここで、入力ベクトルXはn次元のベクトルである。また、固有アドレスAは1~kまでの値をとり、qビットの2進数で表現されている。ここで、qは上述の式(3)により表される。
【0113】
ハッシュ回路2は、入力ベクトルXの一部又は全部を、所定のハッシュ関数に従ってハッシュ化する。ここで、Xの分割をX=(X,X)とする。Xは束縛変数、Xは自由変数である。X=Xの場合も考える。ハッシュ回路2は、Xの束縛変数Xをハッシュ化しハッシュ入力ベクトルX’=(Y,X)を生成する。
【0114】
仮アドレス生成器3は、仮アドレスA’を生成する。この場合、仮アドレスA’は次のように決定される:
(1)ハッシュ化された束縛変数Yに対する一つの割り当てが、ハッシュ衝突が生じない場合、その割り当てに対応する固有アドレスAを仮アドレスA’とする;
(2)ハッシュ化された束縛変数Yに対する一つの割り当てが、ハッシュ衝突が生じる場合、その割り当てに対応する固有アドレスAの集合{A}の中で最も小さいものを仮アドレスA’とする。
【0115】
以下、束縛変数Yに対する一つの割り当て(全部で2個ある)を仮アドレスA’に写像する関数を仮アドレス生成関数と呼び、h^(Y)と記す。
【0116】
データ再生器4は、アドレス生成関数A=f(X)の逆関数X=f-1(A)を演算する演算器である。データ再生器4は、仮アドレス生成器3から入力される仮アドレスA’に対して、再生ベクトルX”=f-1(A’)を出力する。
【0117】
固有アドレス検出器5には、入力ベクトルX,再生ベクトルX”,及び仮アドレスA’が入力される。固有アドレス検出器5は、再生ベクトルX”と入力ベクトルXとの比較を行う。そして、両者が一致する場合は、仮アドレスA’を出力し、それ以外は無効値0を出力する。
【0118】
副アドレス生成器6は、アドレス生成関数f(X)に対し、仮アドレス生成器3,データ再生器4,及び固有アドレス検出器5による仮アドレスA’の演算と補完関係にある副アドレス生成関数f^(X)の演算を行い、副アドレスA”を出力する演算器である。副アドレス生成関数f^(X)は、次のような関数である:
(1)固有アドレス検出器5が無効値0を出力する場合には、入力ベクトルXをそれに対応する固有アドレスAに写像する;
(2)それ以外の場合には、入力ベクトルXを無効値0又は対応する固有アドレスAに写像する。
【0119】
副アドレス生成器6は、論理ゲートを組み合わせることによって構成してもよいし、LUTカスケード論理回路を用いて構成してもよい。
【0120】
出力合成器7には、固有アドレス検出器5の出力値、及び副アドレス生成器6の出力値が入力される。出力合成器7は、これらの出力値のうち、一方又は両方が無効値0以外の場合には、その値を固有アドレスAとして出力する。両方とも無効値0の場合には、無効値0を出力する。
【0121】
尚、図4においては、ハッシュ回路2,仮アドレス生成器3,データ再生器4,及び固有アドレス検出器5により、主アドレス生成器8が構成される。
【0122】
図5は、図4のアドレス生成器1の具体的なハードウェア構成を表すブロック図である。図4と対応するものには同一符号を付している。図5においては、仮アドレス生成器3は、ハッシュ・メモリ3’によって構成されている。データ再生器4は、補助メモリ4’により構成されている。固有アドレス検出器5は、比較回路10及びAND回路11により構成されている。副アドレス生成器6は、LUTカスケード6’により構成されている。また、出力合成器7は、OR回路7’により構成されている。
【0123】
ハッシュ・メモリ3’は書き換え可能メモリにより構成される。ハッシュ・メモリ3’には、式(2a)又は式(2b)に示した仮アドレス生成関数h^(Y)がLUTとして記憶されている。
【0124】
補助メモリ4’は書き換え可能メモリにより構成される。補助メモリ4’には、アドレス生成関数fの逆関数であるデータ再生関数f-1がLUTとして記憶されている。
【0125】
LUTカスケード6’は、図2のように複数の信号線(レイル)によってカスケード接続された複数の書き換え可能メモリ(セル)により構成される。LUTカスケード6’には、副アドレス生成関数f^(X)がLUTカスケードとして構成されている。尚、本実施例においては、副アドレス生成器6は、LUTカスケード6’に限られるものではなく、例えば、論理ゲートの組み合わせや再構成可能PLA等の他の再構成可能論理回路により構成してもよい。
【0126】
〔2〕アドレス生成器の動作
まず、アドレス生成器1にn次元ベクトルの入力ベクトルXが入力される。ハッシュ回路2は、所定のハッシュ関数に従って入力ベクトルX=(X,X)を(Y,X)に一次変換し、アドレス空間をハッシュ化する。ここで、(X,X)はXの分割であり、Xは束縛変数、Xは自由変数である。ベクトルXの変数の個数をd(X)と記す。d(X)=n,d(X)=d(Y)=p,d(X)=r=n-pとする。また、qは式(3)で表される。
【0127】
ハッシュ回路2において生成されたハッシュ化された束縛変数Y1は、ハッシュ・メモリ3’に入力される。
【0128】
ここで、ハッシュ関数は、アドレス生成関数fに適応してあらかじめハッシュ回路2に設定されている。このハッシュ関数の生成方法に関しては、後述する。
【0129】
ハッシュ化した後のアドレス生成関数をf^(Y,X)と記す。関数f^(Y,X)の分解表は、図3に示したようなものとなる。ハッシュ回路2でのハッシュ化によって、分解表における非零要素は分散される。また、アドレス生成関数fの重みkは、2に比べて十分に小さいものとし、束縛変数Xの個数pは、2がkよりも大きいものとする。ハッシュ化により、非零要素が均等に分散されると、図3の分解表の殆どの列は、高々1個の非零要素を持つ。
【0130】
ハッシュ・メモリ3’は、束縛変数Yに基づき、式(2a)又は式(2b)で定義される仮アドレス生成関数h^(Y)により仮アドレスA’を生成する。ここで、d(A’)=qである。尚、Yの値のみで、Aの値を予測しているので、A’=h^(Y)は正しい値A=f^(Y,X)とは異なる値をとる場合がある。
【0131】
仮アドレスA’は、補助メモリ4’及びAND回路11に入力される。
【0132】
補助メモリ4’は、仮アドレスA’に対応する再生ベクトルX”=f-1(A’)を生成する。比較回路10には、再生ベクトルX”ともとの入力ベクトルXとが入力される。
【0133】
比較回路10は、両者を比較し、両者が一致する場合には1、それ以外は0を、AND回路11に出力する。AND回路11は、比較回路10の出力値と仮アドレスA’の各ビットとのAND演算を行う。この演算結果は、OR回路7’に出力される。
【0134】
これにより、仮アドレスA’がXに対する正しい固有アドレスAと等しい場合には、AND回路11からOR回路7’へ仮アドレスA’が出力され、それ以外の場合は無効値0が出力される。すなわち、AND回路11の出力値は、ハッシュ化後のアドレス生成関数f^(Y,X)の分解表において、非零要素が2個以上存在する列について最小の非零要素以外のものを0に置き換えた関数となる。以下、この関数を主アドレス生成関数(master address generation function)と呼び、f^(Y,X)と記す。
【0135】
一方、入力ベクトルXは、LUTカスケード6’にも入力される。LUTカスケード6’においては、副アドレス生成関数(slave address generation function)f(X,X)の演算をLUTカスケードにより行い、その結果を副アドレスA”としてOR回路7’に出力する。
【0136】
尚、副アドレス生成関数f(X,X)は、上述のようにハッシュ化後のアドレス生成関数をf^(Y,X)を式(5)のように関数分解し、f^(Y,X)の変数Yをハッシュ関数の逆関数によってXに変換することによって得られる。
【0137】


【数17】
JP0004892693B2_000021t.gif
従って、ハッシュ化された副アドレス生成関数f^(Y,X)は、主アドレス生成関数f^(Y,X)が決まれば、一意的に次式(6)により求まる。
【0138】






【数18】
JP0004892693B2_000022t.gif

【0139】
尚、具体的な副アドレス生成関数f(X,X)の構成方法に関しては後述する。
【0140】
主アドレス生成関数f^(Y,X)と副アドレス生成関数f(X,X)は、アドレス生成関数f(X,X)に対して相補的である。すなわち、式(5)より、
【0141】


【数19】
JP0004892693B2_000023t.gif
となる。そこで、OR回路7’は、AND回路11の出力値f^(Y,X)とLUTカスケード6’の出力値f(X,X)とのOR演算を行うことによって、アドレス生成関数f(X,X)の値を算出する。
【0142】
〔3〕ハッシュ関数の構成方法
ハッシュ回路2において、束縛変数Xをハッシュ化するハッシュ関数は、アドレス生成関数fの分解表における非零要素を一様に分布させるものであれば、どのような関数でも利用することができる。ここでは、実現の容易さを考慮して、一例として、次のハッシュ関数を用いる。
【0143】




【数20】
JP0004892693B2_000024t.gif

【0144】
〔3-1〕ハッシュ関数の生成アルゴリズム
アドレス生成関数f(X,X)において、束縛変数をX=(x,x,…,x)、自由変数をX=(xp+1,xp+2,…,x)とする。束縛変数XをY=(y,y,…,y)に置換した関数をf^(Y,X)とする。関数f^(Y,X)の分解表の列中で、非零要素を含む列の個数をwとする。ハッシュ・メモリ3’に多くのアドレスを格納するためには、wを最大化するようなYを選択すればよい。Yは、種々の公知のアルゴリズム(非線形計画法や発見的アルゴリズム)を用いて選択すればよい。
【0145】
〔アルゴリズム1〕
の各要素x(i=1,2,…,p)に対して、
【0146】


【数21】
JP0004892693B2_000025t.gif
としたとき、wが最大となるxji'∈{X}を選択する。この操作をwが増加しなくなるまで繰り返す。
(アルゴリズム終わり)
【0147】
このようにして求めたX=(xj1,xj2,…,xjp)によりハッシュ関数を構成する。
【0148】
〔3-2〕ハッシュ関数の実現法
重みkのアドレス生成関数f(X,X)において、束縛変数X=(x,x,…,x)を
【0149】


【数22】
JP0004892693B2_000026t.gif
で置き換えて得られる関数をf^(Y,X)とする。ここで、束縛変数の個数pは次式(10)の条件を満たすものとする。
【0150】


【数23】
JP0004892693B2_000027t.gif

【0151】
p次元の2値ベクトルa(∈Y)に対してf^(a,X)の非零出力値が2個以上ある場合、f^(a,X)の最小の非零出力値以外の値を0に置き換えた関数を主アドレス生成関数f^(Y,X)とする。主アドレス生成関数f^(Y,X)は次式(11)で表される。
【0152】







【数24】
JP0004892693B2_000028t.gif
次に、関数f^(Y,X)を式(6)により求める。このとき、式(7)の関係が成り立つ。
【0153】
主アドレス生成関数f^(Y,X)の分解表の各列において、非零出力値は高々1個しか存在しない。次に、次式(12)で定義される関数h^(Y)をハッシュ・メモリ3’で実現する。
【0154】


【数25】
JP0004892693B2_000029t.gif

【0155】
但し、関数h^(Y)の値は主アドレス生成関数f^(Y,X)の値と異なっている可能性があるので、補助メモリ4’を用いて出力値が正しいか確認する。また、関数f^(Y,X)から次式(13)の置換を行って副アドレス生成関数f(Y,X)を生成する。副アドレス生成関数f(Y,X)は、LUTカスケード6’で実現される。
【0156】


【数26】
JP0004892693B2_000030t.gif

【0157】
(例5)
重みがk=7の6変数のアドレス生成関数f(X,X)の分解表を(表4)に示す。この関数で束縛変数X=(x,x,x)を次式(14)のようにYに置換し、ハッシュ化した関数f^(Y,X)の分解表を(表5)に示す。
【0158】


【数27】
JP0004892693B2_000031t.gif

【0159】
ハッシュ化した関数では、元の関数の列が入れ替わっている。また、入れ替えの方法は、行ごとに異なっている。元の関数では、(x,x,x)=(0,0,0),(0,1,0),(0,0,1)の列に非零要素が2個存在する。一方、(表5)に示すハッシュ化後の関数f^(X,X)では、(y,y,y)=(0,1,0)の列にのみ、非零要素が2個存在する。そのうち、大きい方の非零要素の4を0に置き換えた関数f^(Y,X)の分解表を(表6)に示す。また、(表7)にLUTカスケード6’で実現すべき関数f^(Y,X)の分解表を示す。この例の場合、わずか1個の非零要素しかない。残りの関数は、(表8)に示すハッシュ・メモリ3’と(表9)の補助メモリ4’で実現する。ハッシュ・メモリ3’の出力h^(Y)は、(y,y,y)のみの値を用いて、関数f^の値を予測しており、f^とは異なっている可能性がある。そのため、(表9)に示す補助メモリ4’を用いて、その出力が正しいか否かを検証する。LUTカスケード6’で実現すべき関数は、非零出力値4をとる。その入力時の組み合わせは(x,x,x,x,x,x)=(0,0,1,0,1,1)である。
【0160】
図6に、本方式で、関数fを実現する回路の全体図を示す。LUTカスケード6’の部分は、ANDゲートのカスケードで実現している。また、非零出力は4であるが、2進表現では(1,0,0)であるので、OR回路7’においては、AND回路11の出力ビットのうち、最上位の出力ビットのみ、カスケードの出力とのORをとっている。
(例終わり)
【0161】





















【表4】
JP0004892693B2_000032t.gif

【0162】





















【表5】
JP0004892693B2_000033t.gif

【0163】





















【表6】
JP0004892693B2_000034t.gif

【0164】





















【表7】
JP0004892693B2_000035t.gif

【0165】













【表8】
JP0004892693B2_000036t.gif

【0166】


















【表9】
JP0004892693B2_000037t.gif

【0167】
尚、ハッシュ関数として式(8)を用いた場合、補助メモリ4’のXの部分の出力及び比較回路10でのXとの比較部分は省略することができる。理由は、以下の通りである。
【0168】
ハッシュ・メモリ3’で実現する関数は、h^(Y)である。この出力値で、補助メモリ4’の値を参照するが、ハッシュ化したアドレス生成関数f^の分解表では、元のアドレス生成関数fの分解表で行の要素が置換されている。従って、ハッシュ・メモリ3’の出力値が正しいことを確認するためには、Xの値を調べれば十分である。つまり、補助メモリ4’の出力値とXの値が一致すれば、式(8)の関係より、Xの値も一致することが保証される。従って、ハッシュ・メモリ3’の出力が正しいことが分かる。また、一致しなければ比較回路10の出力値は0である。
【0169】
例えば、図6の回路の場合、補助メモリ4’の出力は、(x,x,x)があれば十分であり、比較回路10の入力も(x,x,x)は省略可能である。
【0170】
〔4〕ハッシュ・メモリで実現可能な登録ベクトルの割合
次に、本発明に係るアドレス生成器において、回路規模をどの程度小さくすることが可能であるかを評価するため、仮アドレス生成器3(ハッシュ・メモリ3’)で実現可能な登録ベクトルの割合を評価する。
まず、仮アドレス生成器3で実現可能な登録ベクトルの割合に関しては、次の定理が成り立つ。
【0171】
〔定理4〕
fを重みkのn入力アドレス生成関数とし、非零要素が分解表中に一様に分布していると仮定する。このとき、図4における仮アドレス生成器3で実現可能なアドレスの割合δは、次式()で表される。ここで、p=|Y|はf^(Y,X)の分解表の束縛変数の個数である。
【0172】


【数28】
JP0004892693B2_000038t.gif
(定理終わり)
【0173】
(証明)
kは分解表中の非零要素の総数を示す。α=k/2は、分解表中での非零要素の割合を示す。β=1-αは、分解表中での零要素の割合を示す。r=n-p=|X|は、f^(Y,X)の分解表の自由変数の個数を表す。このとき、ある列の要素がすべて0となる確率P、及びある列の要素中に少なくとも1つの非零要素が含まれる確率Pは、次式(16),(17)により表される。
【0174】





【数29】
JP0004892693B2_000039t.gif
全体では2個の列が存在し、非零要素数はkである。非零要素が2個以上ある列に関しては、仮アドレス生成器3で1個だけ非零要素を実現すると仮定すると、仮アドレス生成器3で表現可能なアドレスの割合δは、式(18)により表される。
【0175】






【数30】
JP0004892693B2_000040t.gif
また、s=n-qとおくと、関係r=n-pより、r-s=q-pとなる。s>rであるから、上式の各項の絶対値は、iの増加とともに減少する。次に、δを式(18)の右辺最後の式の第3項までを用いて近似すると、式(19)で表される。
【0176】





【数31】
JP0004892693B2_000041t.gif

(証明終わり)
【0177】
例えば、k/2=1/4とすると、δ≒0.8854となる。また、1/4≦k/2≦1/2の領域では、δは、k/2の単調減少関数となる。
【0178】
(例6)
n=40,k=1730の場合を考える。このとき、
【0179】


【数32】
JP0004892693B2_000042t.gif
であるから、束縛変数の変数の個数をp=13とする。
【0180】
(1)LUTカスケードのみで実現した場合
セルの入力数をp=13とすると、カスケードの段数は、(定理2)より、
【0181】


【数33】
JP0004892693B2_000043t.gif
セル1個当たりのメモリ量は、2×q=213×11bits。従って、総メモリ量は、213×11×15=1,351,680bitsとなる。
【0182】
(2)本発明のアドレス生成器1で実現した場合
s=n-q=40-11=29,r=n-p=40-13=27であるから、(定理4)の近似式の仮定は成立する。(定理4)より、
【0183】





【数34】
JP0004892693B2_000044t.gif
となる。ハッシュ・メモリ3’は、p=13入力q=11出力、補助メモリ4’は、q=11入力n=40出力。LUTカスケード6’は、重みが1730×(1-0.901)=170のアドレス生成関数を実現する。このとき、LUTカスケードのセルの出力数は、
【0184】


【数35】
JP0004892693B2_000045t.gif
となる。セルの入力数を10とすると、実現すべきLUTカスケードの段数は、
【0185】


【数36】
JP0004892693B2_000046t.gif
となる。最終段以外のセル1個当たりのメモリ量は、高々210×8bits。最終段のセルのメモリ量は、高々210×11bits。カスケードの総メモリ量は、210×8×15+210×11=134,144bits。ハッシュ・メモリ3’の容量は、213×11=901112bits。補助メモリ4’の容量は、211×40=81920bitsとなる。従って、総メモリ量は、306,176bitsとなる。
従って、この例の場合、本発明のアドレス生成器1を使用した方が、LUTカスケードのみでアドレス生成関数を構成するよりも総メモリ量は少なくてよい。
(例終わり)
【0186】
〔5〕実験結果
アドレス生成回路1の応用例として、頻繁に使用する英単語を表にしたものを考える。ここでは、ベンチマークとして3種類の単語表(単語表1,単語表2,単語表3)を用いた。単語帳中の単語の文字数は、最大13文字であるが、最初の8文字のみを取り扱う。また、8文字より短い単語は、最後に空白を追加して8文字とした。各英文字を5ビットで表現すると、各英単語は40ビットで表現することができる。また、単語表1,単語表2,単語表3の中の単語数は、それぞれ、1730語,3366語,4705語である。各表において、各単語に固有のインデックス(自然数)を付加する。このとき、単語のインデックスは、それぞれ、11bits,12bits,13bitsとなる。
【0187】
次に、ハッシュ関数を生成する。ハッシュ関数の入力数は、(単語帳のインデックスのビット数)+2とする。単語表1の場合、単語数はk=1730、インデックスのビット数は
【0188】


【数37】
JP0004892693B2_000047t.gif
束縛変数の個数は、p=q+2=13。分解表の列の個数は2=213=8192。非零要素を1個含む列の数は1389。非零要素を2個以上含む列の数は、165。ハッシュ・メモリ3’で実現不可能な登録ベクトル数は、176である。つまり、全単語の90%がハッシュ・メモリ3’で実現可能であり、残りの10%をLUTカスケードで実現する必要がある。実験結果を(表10)に示す。
【0189】















【表10】
JP0004892693B2_000048t.gif

【0190】
次に、疑似乱数を用いて同等のアドレス生成関数を実現した場合(100個の平均)の実験結果を(表11)に示す。この場合、非零要素を1個含む列の数は1398.4、非零要素を2個以上含む列の数は160.0、ハッシュ・メモリ3’で実現可能な登録ベクトル数は171.6であった。同様の実験を単語帳2,3に関しても行った。
【0191】
















【表11】
JP0004892693B2_000049t.gif

【0192】
実際の単語表の結果、及び疑似乱数で生成したアドレス生成関数に対する結果は、(定理4)で理論的に求めた結果と大差はない。従って、上記(アルゴリズム1)を用いて生成したハッシュ関数は、非零要素をランダムに分布させる関数として、有効であることが分かる。
【0193】
また、必要メモリ量を比較した結果を(表12)に示す。(表12)から明らかなように、必要な総メモリ量は、1つのLUTカスケードで実現する場合に比べて、大幅に少ない。
【0194】



















【表12】
JP0004892693B2_000050t.gif

【実施例2】
【0195】
本実施例では、主アドレス生成器が2個の場合(スーパー・ハイブリッド法)について説明する。
【0196】
図7は、本発明の実施例1に係るアドレス生成器のハードウェア構成を表すブロック図である。図7において、図5と同様の構成部分については同一の符号が付してある。
【0197】
図5と比較すると、実施例1のアドレス生成器1は主アドレス生成器8が1つであったのに対し、本実施例のアドレス生成器1’は主アドレス生成器8,8’を2つ備えている点で異なる。
【0198】
主アドレス生成器8では、入力ベクトルXに対する分割(X,X)について、主アドレス生成関数f^(Y,X)の演算を行う。ここで、YはXをハッシュ化したベクトルであり、式(8)と同様に計算される。また、主アドレス生成器8’では、入力ベクトルXに対する分割(X’,X’)について、主アドレス生成関数f^’(Y’,X’)の演算を行う。ここで、Y’はX’をハッシュ化したベクトルであり、式(8)と同様に計算される。
【0199】
ここで、分割(X,X)と分割(X’,X’)とは異なる分割とする。具体的には、最適な分割(X’,X’)については次のような手順により決定すればよい。
【0200】
(1)アドレス生成関数fに対して、
(1-1)第1のハッシュメモリの入力数は(q+1),出力数はq、第1の補助メモリの入力数はq,出力数は(n-q-1)となるように、変数を順に分割する。
(1-2)なるべく、分解表の非零要素が分散するようにハッシュ関数を求める。この構成で実現された固有アドレスが表現する関数をf^11とする(ランダム関数の場合は元の固有アドレスの約80%が表現できる)。
(2)上記操作で実現されない固有アドレスが表現する関数、つまりf-f^11に対して、
(2-1)第2のハッシュメモリの入力数は(q-1),出力数は(q-2)、第2の補助メモリの入力数は(q-2),出力数は(n-q+2)となるように、変数を順に分割する。
(2-2)なるべく、分解表の非零要素が分散するようにハッシュ関数を求める。この構成で実現された固有アドレスが表現する関数をf^12とする(ランダム関数の場合は元の固有アドレスの約16%が表現できる)。
(3)上記何れの操作でも実現されない固有アドレスが表現する関数に対しては、LUTカスケード又は再構成可能PLAなどの方法で実現する。
【0201】
このように、主アドレス生成器8,8’を2つ備えたことで、実施例1の場合に比べると、主アドレス生成器8,8’ により固有アドレスが決定される登録ベクトルの割合が多くなる。したがって、副アドレス生成関数f^(X,X)により固有アドレスが決定される登録ベクトルの数は少なくなるため、副アドレス生成器6(再構成可能PLA 6”)の回路規模をより小さくすることが可能となる。
【0202】
(例7)
重みk=1730で変数の数がn=40のアドレス生成関数f(X)を、図7のアドレス生成器1’を用いて実現する場合を考える。尚、比較のため、図5のアドレス生成器1についても考察する。
この場合、
【0203】


【数38】
JP0004892693B2_000051t.gif
である。
【0204】
〔再構成可能PLA〕
再構成可能PLA 6”を実現する方法としては、種々の方法があるが、ここでは、入力ベクトルの各ビットの値を記憶するレジスタとANDゲートを使用したレジスタ-ゲート・アプローチ(register and gates approach)を採用する。図8は、レジスタとゲートを用いた再構成可能PLA 6”の構成を表す図である。図8において、再構成可能PLA 6”は、n個のレジスタ15、n個のEXNORゲート16、及び1個のANDゲート17により構成されている。
【0205】
このアプローチでは、どのような幅のワードであっても構成することができ、高速に再構成することが可能である。入力数をn、出力数をq、実現すべきアドレス生成関数の重みをkとすると、図8の再構成可能PLA 6”をFPGAで構成する場合に必要なLR(Logic Element)の数は、
【0206】


【数39】
JP0004892693B2_000052t.gif
となる。
【0207】
この例では、再構成可能PLA 6”において実現すべき登録ベクトルの数は1730である。従って、式(23)より、再構成可能PLA 6”を実装するのに必要なLE数は、84,478となる。
【0208】
〔ハイブリッド法〕
仮アドレス生成器3で表現可能なアドレスの割合δは、式(19)より、
【0209】





【数40】
JP0004892693B2_000053t.gif
となる。図5のハッシュ・メモリ3’の入力数はp=13、出力数はq=11である。補助メモリ4’の入力数はq=11、出力数はr=n-p=27である。ハッシュ・メモリ3’のサイズは213×11=90,112(bits)である。補助メモリ4’のサイズは211×27=55,297(bits)である。故に、メモリ・サイズの総量は、145,408(bits)である。再構成可能PLA 6”で実現される登録ベクトルの数は173である。
【0210】
〔スーパー・ハイブリッド法〕
仮アドレス生成器3により表現可能なアドレスの割合δは、式(19)より、
【0211】





【数41】
JP0004892693B2_000054t.gif
となる。図7の第1のハッシュ・メモリ3’の入力数はp=12、出力数はq=11である。第1の補助メモリ4’の入力数はq=11、出力数はr=n-p=27である。第2のハッシュ・メモリ3’の入力数はp=10、出力数はq=9である。第2の補助メモリ4’の入力数はq=9、出力数はr=n-p=30である。
【0212】
第1のハッシュ・メモリ3’のサイズは、212×11=45,056(bits)、第1の補助メモリ4’のサイズは211×28=57,344(bits)、第2のハッシュ・メモリ3’のサイズは、210×9=9,216(bits)、第2の補助メモリ4’のサイズは2×30=15,360(bits)である。故に、メモリ・サイズの総量は、126,976(bits)である。再構成可能PLA 6”で実現される登録ベクトルの数は43である。従って、この例では、スーパー・ハイブリッド法の方がハードウェア量をより少なくすることができる。
(例終わり)
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10