JP2668438B2

JP2668438B2 - データ検索装置

Info

Publication number: JP2668438B2
Application number: JP1102712A
Authority: JP
Inventors: 俊之田村; 雅紀藤田; 伸史小守; 尚和佐藤; 英裕高田
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1989-04-21
Filing date: 1989-04-21
Publication date: 1997-10-27
Anticipated expiration: 2012-10-27
Also published as: US5359720A; US5182799A; JPH02280286A

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明はハッシュ処理され記憶されたデータの検索
装置に関し、特に識別データの一致するデータの対を生
成し、発火処理するデータ駆動形プロセッサに用いるデ
ータ検索装置に関する。

〔従来の技術〕第９図はデータ駆動形処理の概念図であり、２つのデ
ータの加算が行われる様子を示している。図において、
“A"という値を持ち“a"という識別子を付加されたパケ
ット81がマッチングメモリ87に与えられると、識別子フ
ィールド比較部84は待合せメモリ85にパケット81の識別
子“a"と一致する識別子を持つパケットが格納されてい
るか否かを検索する。第９図では“B"という値を持ち
“a"という識別子を持つパケット82が格納されているの
で、このパケット82が待合せメモリ85から読出され、入
力されたパケット81と共にデータ対形成部86へ送られ
る。

データ対形成部86はパケット81とパケット82とを合体
し、“A"という値と“B"という値とに“a"という識別子
を付加したデータ83を形成し（これを発火と呼ぶ）、デ
ータ処理部88で演算が実行される。

第９図の例では待合せメモリ85に入力されたパケット
81と同じ識別子“a"を有するパケット82が格納されてい
たが、待合せメモリ85に入力されたパケット81と同じ識
別子を有するパケットが格納されていない場合は、入力
されたパケット81は待合せメモリ85に格納され、これと
一致する識別子を有するパケットが入力されるまで待合
される。

このようにマッチングメモリとはデータ駆動形プロセ
ッサにおいて演算すべきパケットを検索する役割を持っ
ている。

通常データ駆動形プロセッサにおいては、識別子のビ
ット幅は数十ビットとなるため、識別子毎にメモリのア
ドレスを割当てるとメモリ容量が膨大なものとなるた
め、従来よりマッチングメモリに用いるメモリとしてビ
ット幅を圧縮（以下ハッシュという）し、これをメモリ
アドレスとして用いたメモリ（以下ハッシュメモリとい
う）を用いている。

第10図は入力パケットの一例の構成を示すビットマッ
プ図、第11図はハッシュメモリの一例の構成を示すブロ
ック図である。

入力パケットは演算対象となる18ビットのオペランド
データOD、演算内容を示すコードである７ビットのオペ
レーションコードOC、１ビットのプロセッサ選択ビット
PS、入力パケットが２入力命令か１入力命令かを示す１
ビットのFC処理選択ビット及び演算順に応じて左又は右
に配置することを示す左右データ選択ビットを含み、各
種の選択を行うセレクションコードSC、入力データの入
力順等の属性を示す９ビットのカラー／世代識別番号DN
並びに演算の行われるべき場所を示す21ビットのノード
番号NNの60ビットにて構成されている。そしてプロセッ
サ選択ビットPSとカラー／世代識別番号DNとノード番号
NNとから識別コードである31ビットの識別子が構成され
る。

ハッシュメモリ601はカラー／世代識別番号DNの下位
３ビット及びノード番号NNの下位６ビットの合計９ビッ
トをハッシュアドレスとしてアクセスされるものであ
り、リードライトサイクルを定めるリードライト信号W/
・H,書込みデータ及び各アドレスの有効・無効の別を
示すプレゼンスビットPBの更新を行うセットリセット信
号S/が与えられる。格納される書込みデータは18ビッ
トのオペランドデータと、カラー／世代識別番号DN及び
ノード番号NNの残り21ビットの識別子と、１ビットのプ
ロセッサ選択ビットのPSの合計40ビットからなってい
る。またハッシュメモリ601には別に１ビットのプレゼ
ンスビットPBが格納されており、合計１ワード41ビット
となっている。またアドレス空間は2⁹＝512となってお
り、ハッシュメモリ601は41ビット／ワード×512の大き
さを有している。

ハッシュメモリを用いた場合、ハッシュしたアドレス
（以下ハッシュアドレスという）をアクセスしたときに
同一アドレスでの衝突所謂ハッシュ衝突が起こる虞があ
る。

即ちハッシュ衝突とは識別子の一部をハッシュアドレ
スとした場合にハッシュアドレスが既にハッシュメモリ
内に格納されたデータと一致しても、残りの識別子が一
致しないデータがアクセスされたとき、そのデータを記
憶するアドレスが既に占有されているために起こるもの
である。

これを回避する従来技術として「沖電気研究開発報
告」第19〜第26頁に開示されたデータ駆動形処理装置及
び本出願人による発明（特願昭61−277040号）がある。

前者のものはハッシュメモリ内にハッシュメモリ内の
アドレスの相関関係を示すチェインフィールドを設け、
ハッシュ衝突した場合はハッシュメモリ内のチェインフ
ィールドに示されるアドレスを順次参照することによっ
て対となるデータを検索するものである。

後者のものは、識別子の大小を比較するタグ比較部を
設け、ハッシュ衝突が発生した場合に、入力されたデー
タと読出されたデータの識別子との大小を比較し、識別
子の小さい方のデータをハッシュメモリに格納し、大き
い方のデータはスルーフラグを付加され何も処理されず
にハッシュメモリに格納できるまで何度も装置内を循環
し、ハッシュメモリに入力される。この識別子の大小は
プログラムの処理順に応じて定められているので、識別
子の大小比較を行いハッシュメモリに小さい値の識別子
を有するデータを格納することにより、プログラムの実
行におけるデータの依存関係によって生じる無限ループ
の発生を防ぐ。

〔発明が解決しようとする課題〕

しかしながら前者のものはハッシュ衝突が起きた場合
にチェインフィールドで指示されるアドレスをたどるこ
とにより対となるべきデータを順次検索しているので、
ハッシュ衝突を起こす頻度が増加した場合、１データ当
たりの処理時間が長くなり、プロセッサ全体の処理効率
が著しく低下するという問題がある。

従ってハッシュ衝突の頻度を減少させるべく、ハッシ
ュメモリの容量を大きくする必要が生じ、メモリ容量を
小さくするためのハッシュメモリを用いる意味がなくな
る。

また後者のものは、データの識別子の値の大小を比較
し、ハッシュメモリ内のデータの入換えを行うため、そ
の機構が大がかりな装置となる。またスルーフラグをセ
ットされたデータがプロセッサ内を循環し、その間プロ
セッサを占有することになるため、その処理効率が低下
する。

一方ハッシュアドレスは前述した如く例えば識別子の
９ビットのカラー／世代識別番号DNからの３ビットに21
ビットのノード番号NNからの６ビットを連結して生成さ
れている。そして2⁹のハッシュメモリのアドレス空間は
2³（＝８）のカラー／世代区間に分かれ、１カラー／世
代区間は2⁶（＝64）のアドレス空間がある。従って入力
データのカラー／世代識別番号DNの下位３ビットが等し
い場合、同一のカラー／世代区間にアクセスすることに
なり、カラー／世代が少ない場合、１区間（＝2⁶）のア
ドレス空間へのアクセス頻度が増加し、ハッシュ衝突の
頻度が増大する。即ちカラー／世代識別番号DNの下位３
ビットが等しい入力データはアドレス空間が2⁹（＝51
2）あるのにも拘わらず、実質的にはその1/8の空間（＝
64）をアクセスすることになる。それ故ハッシュ衝突の
頻度は８倍となる場合がある。

この発明は斯かる事情に鑑みなされたものであり、複
数の識別データからハッシュアドレスを生成する場合
に、それからＫビットを抽出し、それらの演算に基づき
生成することにより識別データが類似している場合であ
ってもメモリの全アドレス空間をアクセスすることがで
き、ハッシュ衝突の発生を抑制し、処理効率を向上させ
たデータ検索装置を得ることを目的とする。

〔課題を解決するための手段〕

この発明に係るデータ検索装置は、任意ビット長の複
数の識別データを有する入力パケットの前記複数の識別
データから少なくとも１つの部分ビット列を選択し、選
択されたビット列の逆算可能な演算により前記パケット
の格納アドレスを生成するアドレス生成手段と、生成さ
れた格納アドレスによりアクセスされ、前記パケットの
一部または全部を格納するメモリと、入力されたパケッ
トの前記メモリ内格納アドレスに既に有効なパケットが
格納されているとき、格納されているパケットの識別デ
ータの一部又は全部と、入力されたパケットの識別デー
タの一部又は全部とを比較し、それらの一致／不一致を
判定する第１の比較手段と、該第１の比較手段が不一致
を判定したとき、入力されたパケットの識別データを検
索データとして格納する連想メモリと、入力されたパケ
ットの識別データの一部又は全部と前記連想メモリに格
納されている識別データの一部又は全部とを比較する第
２の比較手段と、前記第１および第２の比較手段の比較
結果に応じて、前記メモリ又は前記連想メモリからの出
力を選択する手段とを備えることを特徴とする。

〔作用〕

この発明においては、メモリの格納アドレスが複数の
識別データの逆算可能な演算により生成されるので、識
別データの一部が類似のパケットであっても、同一の格
納アドレスとなることがなく、ハッシュ衝突の頻度が減
少する。またハッシュ衝突が生じたときにそのパケット
の識別データを検索データとして連想メモリに格納でき
るのでパケットが循環することなく格納でき処理効率が
向上する。

〔実施例〕

以下、この発明を実施例を示す図面に基づいて説明す
る。

第１図はこの発明に係るデータ検索装置をデータ駆動
形プロセッサの発火処理装置に用いた場合の構成を示す
ブロック図である。図において612は入力セレクタであ
り、後述するFIFOメモリ611から出力されたパケットと
入力されたパケットとを選択する。なおパケットはその
ビットマップを第10図に示すごとく62ビットの幅を有し
ている。選択されたパケットはデータクラッチ608に与
えられ、そこでデータ入力信号COが“H"のタイミングで
ラッチされる。ラッチされたパケットはその31ビットの
識別子のうち、カラー／世代識別番号DNの９ビットと、
ノード番号NNの下位９ビットとが、排他的論理和演算を
行いハッシュアドレスを生成するアドレス生成手段であ
る演算器101の２つの入力端子に夫々与えられる。

第２図は演算器101の構成を示す図であり、入力され
た９ビットのカラー／世代識別番号DNとノード番号NNの
下位９ビットとが夫々のビット毎に排他的論理和演算さ
れ、その演算結果がハッシュアドレスとなり、ハッシュ
メモリ601に与えられる。

また31ビットの識別子と18ビットのオペランドデータ
ODとは連想メモリ部602にも与えられる。また識別子の
うちノード番号NNの下位９ビットを除いた22ビットと、
18ビットのオペランドデータODとを合わせた40ビットの
書込みデータがハッシュメモリ601に与えられる。

第３図はハッシュメモリ601の構成を示すブロック図
であり、ハッシュメモリ601は41ビットのビット幅を有
し、2⁹（＝512）のアドレス空間を有している。そして1
8ビットのオペランドデータODと、31ビットの識別子の
うちノード番号NNの下位９ビットを除いた22ビットとが
格納されると共に、そのアドレスの内容の有効（PB＝
１）、無効（PB＝０）の別を示すフラグであるプレゼン
スビットPBが格納されている。ハッシュメモリ601には
前述の如く９ビットのハッシュアドレスと40ビットの書
込みデータが与えられると共に、後述する制御部606か
らそのリードライトサイクルを定めるリードライト信号
W/・Ｈと、プレゼンスビットPBの更新を行うセット信
号S/とが与えられ、リードライト信号W/・Ｈ＝“H"
のサイクルで書込みされ、W/・Ｈ＝“L"のサイクルで
指定されたアドレスの読出しデータとプレゼンスビット
とが出力される。

第４図は連想メモリ部602の構成を示すブロック図で
ある。図において201はハッシュ衝突したときにデータ
ラッチ608からの31ビットの識別子と一致するデータを
検索する連想メモリ（以下CAMという）であり、32ビッ
ト×32アドレスの容量となっている。CAM201のうち１ビ
ットは前記ハッシュメモリ601と同様に格納されている
データの有効性を判別するためのプレゼンスビットPBの
格納に用いられる。CAM201には各アドレスに対して一
致，不一致検索ライン（以下マッチラインという）が設
けられており、与えられた31ビットの識別子と、CAM201
に格納された識別子とが全て一致したアドレスの32ビッ
トのマッチラインの１ビットが“H"となる判定信号が出
力される。またCAM201にはセレクタ205を介してプレゼ
ンスビットPBの更新を行うセット信号S/が与えられる
と共にリードライトのサイクルを定めるリードライト信
号W/・Ｃが与えられる。セレクタ205は一端に基準電
圧が、他端にセット信号S/が与えられており、また切
換端子にはリードライト信号W/・Ｃが与えられてお
り、リードサイクルのときは基準電圧が、ライトサイク
ルのときはセット信号S/が選択される。即ちリードサ
イクル（W/・Ｃ＝Ｌ）のときは、プレゼンスビットPB
＝１のアドレスだけを検索する必要があるので、検索デ
ータのプレゼンスビットPBに相当するビットを常に１と
し、ライトサイクル（W/・Ｃ＝Ｈ）のときのみプレゼ
ンスビットPBを更新する必要があるためにこのセレクタ
205は用いられる。

またCAM201からは32ビットのマッチラインに識別子の
一致，不一致の別を示す判定信号が出力されると共に、
空アドレス検出器203に各アドレスのプレゼンスビットP
Bが出力され、そこでプレゼンスビットPBにより空アド
レスが検出される。

空アドレス検出器203は32ビットの検出信号をアドレ
スセレクタ204の一端に出力すると共に空アドレスがな
くCAM201の全アドレス空間にハッシュ衝突したパケット
の識別子が格納されたとき、そのことを示すフル信号FL
を制御部606に出力する。なお検出信号はCAM201のアド
レスに対応する32ビットの出力であり、その空アドレス
のビットが“H"となっている。アドレスセレクタ204の
他端にはマッチラインからの判定信号が与えられ、その
切換端子に与えられたリードライト信号W/・Ｃのリー
ドライトに応じアドレスセレクタ204はリードサイクル
のときは判定信号を、またライトサイクルのときは空ア
ドレス検出器203の検出信号を夫々選択する。アドレス
セレクタ204のアドレス選択出力はRAM202に与えられ、
それにより指定されたアドレスがアクセスされる。RAM2
02はオペランドデータを格納するためのものであり、18
ビット×32アドレスの容量となっている。リードライト
信号W/・Ｃ及びアドレス選択出力に応じてオペランド
データの読書きが行われる。即ちリードサイクルではRA
M202のアドレスラインには判定信号が与えられ、CAM201
に入力されたパケットの識別子と一致する識別子がCAM2
01に格納されている場合（これをCAM201がヒットしたと
いう）、判定信号に応じたアドレスの18ビットのオペラ
ンドデータが読出しデータとして出力される。この読出
しデータは判定信号とマージされ、50ビットの出力信号
としてデータラッチ609に出力される。またCAM201がヒ
ットしなければ判定信号は32ビット全て“L"のままであ
り、RAM202からは如何なるオペランドデータも読出され
ない。

一方ライトサイクルでは空アドレス検出器203から検
出信号が選択され、CAM201とRAM202のいずれかのアドレ
スに31ビットの識別子と18ビットのオペランドデータOD
とを格納するか指示する。

またCAM201がヒットした場合はプレゼンスビットPBを
更新する必要が生じるので、ライトサイクルにてCAM201
に与えられるアドレスはヒットしたアドレスである。

入力されたパケットとハッシュアドレスとが等しいハ
ッシュメモリ601内の40ビットの格納データ、ハッシュ
メモリ601のプレゼンスビットPB及び連想メモリ部602の
出力信号はデータラッチ609にクロックT₁のタイミング
でラッチされ、プレゼンスビットPBは制御部606へ、ま
た格納データのうちの22ビットの識別子は第一の比較手
段を構成する一致検出器603の一端へ、格納データのう
ちの18ビットのオペランドデータODは出力セレクタ605
の一端へ夫々与えられる。また連想メモリ部602の出力
信号のうち32ビットの判定信号は第２の比較手段を構成
するヒット検出器604へ、また18ビットのオペランドデ
ータODは出力セレクタ605の他端へ与えられる。

一致検出器603の他端には入力されたパケットの31ビ
ットの識別子の下位９ビットを除いた22ビットの識別子
が与えられ、入力された２つの識別子の一致を検出し、
一致している場合は一致信号EQを制御部606に出力す
る。即ち一致した場合はハッシュアドレスとして用いた
９ビットの識別子と22ビットの識別子とが全て一致した
こととなるためその旨を一致信号EQとして制御部606へ
告知する。

またヒット検出器604はCAM201からの32本のマッチラ
インの反転信号をモニタし、その中の１ビットでも“H"
に立上ったものがあった場合は（＝CAM201がヒットすれ
ば）、ヒット信号HITを制御部606及び出力セレクタ605
の切換端子に与える。

出力セレクタ605は、入力されたパケットの識別子と
ハッシュメモリ601又は連想メモリ602内に格納された識
別子とが全て一致する発火対象の相手データが検索され
た場合に一致した識別子を格納した方のメモリからのオ
ペランドデータODを選択するものである。選択結果のオ
ペランドデータODはデータラッチ610に与えられ、制御
部606からのクロックT₂の“H"のタイミングでラッチさ
れ、データ対形成器607の一端に与えられる。

出力セレクタ605の選択は切換端子に与えられたヒッ
ト信号HITにより行われ、CAM201がヒットした場合にの
み連想メモリ部602に格納されていたオペランドデータO
Dを選択し、ヒットしなかった場合にはハッシュメモリ6
01に格納されていたデータを選択し、データラッチ610
に送る。

データ対形成器607は出力セレクタ605により選択され
たオペランドデータODが一端に入力されると共に他端に
は、データラッチ608からの62ビットの入力されたパケ
ットのデータが与えられる。そして２つのデータがマー
ジされ80ビットの２オペランドデータが形成される。こ
のとき２項演算の減算命令の如くオペランドの順序関係
が重要なものがあるので、選択されたオペランドデータ
ODと入力されたパケットのオペランドデータODとは正し
く左又は右のオペランドとして配置される必要がある。

第５図はデータ対形成器607の構成を示すブロック図
である。データ対形成器607は２つのデータセレクタ70
1,702からなり、夫々の切換端子には入力されたパケッ
トの左／右データ選択ビットでその状態を示すセレクタ
制御信号L/が与えられる。データセレクタ701のＡ端
子及びデータセレクタ702のＢ端子にはデータラッチ608
よりの入力されたパケットのオペランドデータODが夫々
与えられ、データセレクタ701のＢ端子及びデータセレ
クタ702のＡ端子にはデータラッチ610よりの格納された
オペランドデータODが与えられる。そして入力されたパ
ケットのオペランドデータODからのセレクタ制御信号L/
が“1"のときは夫々のデータセレクタ701,702のＡ端
子に与えられたオペランドデータが、またL/が“0"の
ときはＢ端子に与えられたオペランドデータが選択さ
れ、データセレクタ701からの選択出力が左オペランド
となり、データセレクタ702からの選択出力が右オペラ
ンドとなり、それらと入力されたパケットのオペランド
データODを除く他のデータとがマージされ出力される。

制御部606はプレゼンスビットPB、ヒット信号HIT、一
致信号EQ、入力されたパケットが２入力命令か１入力命
令かの別を示すFC処理選択ビットの状態で定まる入力選
択信号FC（２入力命令FC＝１、１入力命令FC＝０）及び
フル信号FLが与えられ、それらを判断してリードライト
信号W/・C,W/・Ｈ、セット信号S/、データ出力信
号C1及び後述するFIFOメモリ611への書込信号WRFを出力
する。またデータ入力信号C0、データ出力許可信号▲
▼が入力され、それらを判断してデータ入力許可信号
▲▼、クロックT₁及び同T₂を出力する。ここでデー
タ入力信号C0及びデータ入力許可信号▲▼はこの発
火処理装置と、この装置に対してデータを与える処理装
置（以下前段装置という）との間のデータ転送制御信号
であり、データ出力信号C1及びデータ出力許可信号▲
▼はこの装置の出力するデータを受取る処理装置（以
下後段装置という）との間のデータ転送制御信号であ
る。

制御部606にフル信号FLが入力され、さらにハッシュ
衝突が生じた場合、制御部606から２ポートタイプのFIF
Oメモリ611に書込み信号WRFが与えられる。このときFIF
Oメモリ611はデータ対形成器607からの出力信号のうち
入力されたパケットの62ビットのデータを格納し、それ
を所定時間バッファリングした後：入力セレクタ612の
他端に与える。この間にハッシュ衝突の原因となったハ
ッシュアドレスのハッシュメモリ601内のデータか、ま
たはCAM201内のデータのいずれかのデータが読出されて
発火されている場合はFIFOメモリ611を経由して再び入
力されたパケットはこの装置内のハッシュメモリ601又
は連想メモリ部602のいずれかで待合せを行うことがで
きる。

この際、入力セレクタ612は通常外部より与えられる
データをセレクトし、FIFOメモリ611の出力端にバッフ
ァリングを施されたデータが存在するときのみ、外部よ
り与えられるデータとFIFOメモリ611の与えるデータを
交互にセレクトするよう制御される。

次に以下の如く構成されたこの発明の発火処理装置の
動作について説明する。なおハッシュメモリ601にはデ
ータ対を待つ複数のパケットが格納されているとする。
第６図はこの発明の概略動作を説明するフローチャート
である。パケットが入力されると（S1）、連想メモリ部
602では格納された識別子との一致，不一致を判定（SI
0）すると共に、９ビットのハッシュアドレスがカラー
／世代識別番号DN（９ビット）とノード番号NNの下位９
ビットとの排他的論理和により生成される（S2）。次に
ハッシュメモリ601のそのハッシュアドレスに有効なデ
ータが既に格納されているか否かが判定され（S3）、連
想メモリ部602の識別子と一致せず、かつ（S3）でデー
タが格納されていない場合は入力パケットをハッシュメ
モリ601のそのハッシュアドレスに格納し（S4）、格納
されている場合は22ビットの他の識別子が一致している
か否かが判定され（S5）、一致していない場合はハッシ
ュ衝突が生じているので、入力パケットを連想メモリ部
602に格納し（S7）、一致した場合はハッシュメモリ601
内の格納データを選択し（S9）、それと入力パケットと
をデータ対となす発火処理を行う（S12）。

また連想メモリ部602に格納した後、そのメモリ部602
が満杯か否かが判定され（S7）、満杯のときは入力パケ
ットをFIFOメモリ611に格納し、満杯でないときはその
まま次処理に移る。

一方パケットが入力されとハッシュアドレスが生成さ
れると共に連想メモリ部602では格納された識別子との
一致、不一致を判定し（S10）、一致したときは連想メ
モリ部602の出力を選択し（S11）、発火処理する（S1
2）。また一致しないときはステップ９に移る。以上が
概略動作である。

第７図はこの発明装置の動作サイクルを説明するタイ
ミングチャートであり、この図に示す如くこの発明装置
の動作サイクルはリードサイクル、処理サイクル及びラ
イトサイクルの３つのサイクルに分けられる。前段装置
からのデータ入力信号C0が制御部606に入力されると、
前段装置への出力許可信号▲▼が“1"→“0"に変化
し、次の入力を禁止し、リードサイクルに入る。リード
サイクルに入ると入力セレクタ612で選択された入力パ
ケット又はCAM201のオーバフローにより循環されたパケ
ットのいずれかが、データ入力信号COの“0"→“1"のタ
イミングでデータラッチ608にラッチされる。データラ
ッチ608にパケットが入力されると、前記パケットの31
ビットの識別子のうち、カラー／世代識別番号DNの９ビ
ットと21ビットのノード番号NNの下位９ビットとが演算
器101に与えられそれらの排他的論理和演算が行われ、
９ビットのハッシュアドレスが定められる。

なおこの実施例では演算器101により２種類の識別コ
ードの排他的論理和演算が行われているが、識別コード
の演算対象数及び演算内容はこれに限るものではなく、
演算対象数は３つ以上でもよく、また演算内容は加算等
の他の逆算可能な演算でもよい。

即ち、任意の自然数a,bに対してａｂ＝ｃならばｂ
ｃ＝ａが成立する演算子により下記式〔k₁〕_ｋ…〔k_M〕_ｋ但しk₁・・・k_M…識別コードによりハッシュアドレスを生成してもよい。

ハッシュアドレスが定められると、リードサイクルで
はハッシュメモリ601と連想メモリ602とが同時に読出さ
れる。メモリ読出しに必要な時間が経過するとクロック
T₁が“0"→“1"に変化し、読出されたデータはデータラ
ッチ609にラッチされる。ここから処理サイクルに入
り、一致検出器603及びヒット検出器604はハッシュメモ
リ601及び連想メモリ部602より読出された各データに基
づいて一致信号EQ及びヒット信号HITを出力する。即ち
一致検出器603はハッシュ衝突が起こっているか否かを
検出するものであり、データラッチ608に入力されてい
るパケットの識別子とハッシュメモリ601から読出され
たデータラッチ609にラッチされている識別子との比較
を行う。即ちカラー／世代識別番号DNの９ビット、ノー
ド番号NNの上位12ビット及びプロセッサ識別ビットの１
ビットの計22ビットの比較を行う。これらの22ビットが
全て等しいと判定されると、９ビットのハッシュアドレ
スが等しく、また９ビットのカラー／世代識別番号DNが
等しいので、ノード番号NNの下位９ビットも等しいこと
になり、31ビットの識別子の全てが等しいと判定され、
一致検出器603は一致信号EQ＝“1"を制御部606に出力す
る。

即ち入力されたパケットのカラー／世代識別番号DNの
９ビットをｇ、ノード番号NNの上位12ビットをN_A、下位
９ビットをN_Bとし、ハッシュメモリ601内に格納されて
いるカラー／世代識別番号DNをg_M、ノード番号NNの上位
12ビットをN_Mとすると、ハッシュアドレスＡは前述の如
くＡ＝ｇＮ …（１）：排他的論理和又は N_B＝ｇＡ …（２）によって求められ、このハッシュアドレスＡによりハッ
シュメモリ601をアクセスしている。ハッシュメモリ601
上にノード番号NNの21ビットのうち下位９ビットは格納
されていないので、それを求めなければ入力パケットの
下位９ビットN_Bとの比較はできない。

しかし前述の如くｇ＝g_Mが判明すると、上記（２）式
より N_B＝g_MＡ …（３）が得られる。しかしN_Bが直接に得られるため、格納され
ていない下位９ビットを求める必要がなく、比較する必
要もなくなる。

そしてヒット検出器604では連想メモリ部602に格納さ
れている識別子とデータラッチ608に入力されているパ
ケットの識別子とが等しい場合、即ち32ビットのマッチ
ラインのいずれかが“H"となったときにヒット信号HIT
＝“1"を出力する。

上述の操作に必要な時間が経過すると、クロックT₂が
“0"→“1"に変化し、ライトサイクルに入る。ライトサ
イクルではプレゼンスビットPBの更新を含むメモリの書
込みとデータ対の生成が行われる。これらの操作に必要
な時間が経過すると制御部606はデータ出力信号C1を出
力し、クロックT₁,T₂及びデータ入力許可信号▲▼
の復帰を行い一連の処理を終了する。但しデータ出力信
号C1の出力は入力されたパケットが発火したときだけで
あり、発火しなかった場合は、クロックT₁,T₂及びデー
タ入力許可信号▲▼の復帰だけを行い、データ出力
信号C1は出力されない。そしてこのライトサイクルでは
プレゼンスビットPB、一致信号EQ、ヒット信号HIT,フル
信号FL及び入力選択信号FCによってリードライト信号W/
・H,W/・C,FIFOメモリ611の書込信号WRF及びセット
信号S/が制御部606で生成される。この真理値表を第
８図に示す。これによりハッシュメモリ601及び連想メ
モリ部602に入力されたパケットを書込むか否かを定
め、下記の如くの動作をする。

第８図の（１）は、１入力命令が与えられた場合を示
し、ハッシュメモリ601の内容を何ら更新することなく
１オペランドデータがそのまま出力される。

第８図の（２）〜（７）は２入力命令が与えられた場
合を示し、データを出力するか否かは各種の条件により
定まる。（２）はハッシュメモリ601の入力パケットに
より定められたハッシュアドレスにデータが格納されて
おり（PB＝１）、それがハッシュ衝突を起こすことがな
かった（EQ＝１）場合を示す。ハッシュメモリ601と連
想メモリ部602とに重複してデータが格納されることは
ないので、この場合CAM201がヒットすることはない（HI
T＝０）。このときライトサイクルにおいてはハッシュ
メモリ601のプレゼンスビットPBをリセットする必要が
あるのでリードライト信号W/・Ｈ＝１、セット信号S/
＝０とする。連想メモリ部602には手を加える必要が
ないので、リードライト信号W/・Ｃ＝０とする。入力
されたパケットはハッシュメモリ601の内容と発火した
ので、ライトサイクルの終了と同時にデータ出力信号C1
を出力する。

第８図の（３）及び（４）はハッシュメモリ601に有
効なデータが格納されていたが、それがハッシュ衝突を
起こした場合を示す（PB＝1,EQ＝０）。そして（３）で
はCAM201でもヒットしなかったため（HIT＝０）、入力
されたデータは連想メモリ部602に格納され（W/・Ｃ
＝1,S/＝１）データの出力は行われない（C1＝０）。
（４）ではCAM201がヒットしたため（HIT＝１）、入力
されたパケットは連想メモリ部602の内容と発火し、出
力される（C1＝１）。ここでCAM201のプレゼンスビット
PBがリセットされなければいけないので、リードライト
信号W/・Ｃ＝1,セット信号S/＝０とされる。（５）
及び（６）はハッシュメモリ601に有効なデータが格納
されていなかった場合であり（PB＝０）、一致信号EQの
値に意味はない。（５）ではCAM201がヒットしなかった
場合を示し（HIT＝０）、入力されたパケットはハッシ
ュメモリ601に書込まれる（W/・Ｈ＝1,S/＝1,C1＝
０）。（６）ではCAM201がヒットしており、（４）と同
様な操作を行う。また（７）はハッシュメモリ601に有
効なデータが格納されていたがそれがハッシュ衝突を起
こし（PB＝１、EQ＝０）、連想メモリ部602に格納する
必要が生じたが、CAM201が満杯となり全アドレスが有効
となった場合（FL＝１）を示し、入力されたパケットは
FIFOメモリ611に所定時間をバッファリングされる（WRF
＝１）。第８図を参照して述べた動作は全てライトサイ
クルにおけるものであり、ライトサイクル以外の動作で
はリードライト信号W/,W/・Ｃは常に“0"となって
いる。

これらの動作で発火することが判明したパケット及び
データはデータ対形成器607に送られ、オペランド対パ
ケットが形成されて出力される。このように発火処理装
置に対してハッシュメモリ601と連想メモリ602とを併用
し、両者の読出しを同時に行うことにより、ハッシュ衝
突の如何に拘わらず同じ速度で処理ができ、装置の制御
も第８図に示した如く簡潔に行える。

ここでハッシュアドレスの生成を排他的論理和の演算
により行った場合、第１の識別データであるカラー／世
代識別番号DNが同一又はその下位３ビットが同一であっ
ても生成されるハッシュアドレスの値が広範囲に及ぶこ
との一例を説明する。

第１表はこの発明及び従来技術において生成されたハ
ッシュアドレスを比較したものであり、表内の数字は全
て16進数で示している。従来技術の場合はカラー／世代
識別番号DNが異なっていてもその下位３ビットが共に０
で等しいため（0_H＝000000000,8_H＝000001000,80_H＝010
000000）、生成されるハッシュアドレスは０〜３番地の
４アドレスだけとなるが、この発明では０〜83と広い範
囲に及ぶことがわかる。従ってこの発明においては識別
データのうちいくつかが同一又は近接したものであって
も、異なったハッシュアドレスを生成し、それによりハ
ッシュ衝突の頻度が低減される。

なお、この実施例では、ハッシュアドレスの決定に際
し、識別子のカラー／世代識別番号DNの９ビットと、ノ
ード番号NNの下位９ビットとの排他的論理和をとりハッ
シュアドレスを生成したが、ノード番号NNの下位９ビッ
トの位置を上位と下位を並べかえるビットリバースさ
せ、排他的論理和をとりハッシュアドレスを生成しても
同様な効果を得ることができる。

このビットリバースを用いた場合の効果について詳し
く説明する。発火処理装置においては、パケットのカラ
ー／世代識別番号DNは続き番号で流れてくることが多
い。例えばカラー／世代識別番号DN＝1_Hとノード番号NN
の下位９ビット＝2_Hとを有するパケットの後にカラー／
世代識別番号DN＝2_Hとノード番号NNの下位９ビット＝1_H
を有するパケットが入力されるというようにである。こ
の場合、それらの排他的論理和は等しいので双方のハッ
シュアドレスは等しく、識別子が一致していないのでハ
ッシュ衝突が生じる。

しかし、ノード番号NNの下位９ビットをビットリバー
スし、排他的論理和によりハッシュアドレスを求める
と、前者のパケットのハッシュアドレスは81_H、後者の
は102_Hとなり、全く違ったハッシュアドレスを生成する
ことができる。第２表は以上のビットリバースの場合の
ハッシュアドレスの生成の一例を示している。

ビットリバースしない場合に比してビットリバースし
た場合はハッシュアドレスをさらに多くのパターンで生
成することができる。

またこの実施例ではハッシュ衝突が頻発しCAMがオー
バフローした場合であっても、入力されたパケットを所
定時間FIFOメモリにバッファリングできるので、CAMを
小容量とすることができ、オーバーフロー時に何ら特別
の処理を行う必要がなく処理速度が向上する。

なおこの実施例ではこの発明のデータ検索装置をデー
タ駆動プロセッサの発火処理装置に適用した場合を説明
したが、この発明はこれに限るものではなく、キーワー
ド等の識別子によりデータ検索を行う一般的なマッチン
グメモリに対して適用できることは言うまでもない。

〔発明の効果〕

以上説明したようにこの発明によれば、ハッシュアド
レスの生成を複数の識別データの逆算可能な所定の論理
演算により行っているので、複数の識別データが等しい
か又は類似した値であっても生成されるハッシュアドレ
スは幅広い領域を有するため、アドレス空間の全域が有
効利用され、ハッシュ衝突の頻度が低減する。また連想
メモリ部を設けたことでハッシュ衝突したパケットをそ
れに格納することができ、パケットの循環がなくなり、
ハッシュメモリと連想メモリ部との同時検索により処理
速度が向上する等優れた効果を奏する。

【図面の簡単な説明】

第１図はこの発明に係るデータ検索装置をデータ駆動形
プロセッサの発火処理装置に適用した場合の構成を示す
ブロック図、第２図は演算器の構成を示す図、第３図は
ハッシュメモリの構成を示すブロック図、第４図は連想
メモリ部の構成を示すブロック図、第５図はデータ対形
成器の構成を示すブロック図、第６図はこの発明の概略
動作を説明するフローチャート、第７図はこの発明の動
作サイクルの説明図、第８図はライトサイクルの真理値
を示す図、第９図は従来のデータ駆動形処理の概念図、
第10図は入力パケットの一例を示す図、第11図は従来の
ハッシュメモリの構成を示すブロック図である。 101……演算器、201……CAM、601……ハッシュメモリ、
602……連想メモリ部、603……一致検出器、604……ヒ
ット検出器、605……出力セレクタ、606……制御部、60
7……データ対形成器なお、図中、同一符号は同一、又は相当部分を示す。

───────────────────────────────────────────────────── フロントページの続き (72)発明者佐藤尚和兵庫県伊丹市瑞原４丁目１番地三菱電機株式会社エル・エス・アイ研究所内 (72)発明者高田英裕兵庫県伊丹市瑞原４丁目１番地三菱電機株式会社エル・エス・アイ研究所内 (56)参考文献特開昭59−158443（ＪＰ，Ａ) 特開昭59−33555（ＪＰ，Ａ) 特開昭57−59252（ＪＰ，Ａ) 特開昭63−129425（ＪＰ，Ａ)

Claims

(57)【特許請求の範囲】

【請求項１】任意ビット長の複数の識別データを有する
入力パケットの前記複数の識別データから少なくとも１
つの部分ビット列を選択し、選択されたビット列の逆算
可能な演算により前記パケットの格納アドレスを生成す
るアドレス生成手段と、生成された格納アドレスによりアクセスされ、前記パケ
ットの一部または全部を格納するメモリと、入力されたパケットの前記メモリ内格納アドレスに既に
有効なパケットが格納されているとき、格納されている
パケットの識別データの一部又は全部と、入力されたパ
ケットの識別データの一部又は全部とを比較し、それら
の一致／不一致を判定する第１の比較手段と、該第１の比較手段が不一致を判定したとき、入力された
パケットの識別データを検索データとして格納する連想
メモリと、入力されたパケットの識別データの一部又は全部と前記
連想メモリに格納されている識別データの一部又は全部
とを比較する第２の比較手段と、前記第１および第２の比較手段の比較結果に応じて、前
記メモリ又は前記連想メモリからの出力を選択する手段
とを備えることを特徴とするデータ検索装置。