JPH02280286A

JPH02280286A - データ検索装置

Info

Publication number: JPH02280286A
Application number: JP1102712A
Authority: JP
Inventors: Toshiyuki Tamura; 田村　俊之; Masaki Fujita; 雅紀藤田; Nobufumi Komori; 伸史小守; Hisakazu Sato; 尚和佐藤; Hidehiro Takada; 高田　英裕
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1989-04-21
Filing date: 1989-04-21
Publication date: 1990-11-16
Anticipated expiration: 2012-10-27
Also published as: JP2668438B2; US5182799A; US5359720A

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

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

〔従来の技術〕

第９図はデータ駆動形処理の概念図であり、２つのデー
タの加算が行われる様子を示している。

図において“Ａ”という値を持ち“ａ“という識別子を
付加されたパケット８１がマツチングメモリ８７に与え
られると、識別子フィールド比較部８４は待合せメモリ
８５にパケット８１の識別子“ａ″と一致する識別子を
持つパケットが格納されているか否かを検索する。第９
図では“Ｂ”という値を持ち“ａ′″という識別子を持
つパケット８２が格納されているので、このパケット８
２が待合せメモリ８５から読出され、入力されたパケッ
ト８１と共にデータ対形成部８６へ送られる。

データ対形成部８６はパケット８１とパケット８２とを
合体し、”Ａ”という値と”Ｂ″という値とにａ”とい
う識別子を付加したデータ８３を形成しくこれを発火と
呼ぶ）、データ処理部８８で演算が実行される。

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

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

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

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

入力パケットは演算対象となる１８ピツトのオペランド
データＯＤ、演算内容を示すコードである７ビツトのオ
ペランドコード００１１ビツトのプロセッサ選択ビット
ＰＳ１人カパケットが２人力命令か１人力命令かを示す
１ビツトのＰＣ処理選択ビット及び演算順に応じて左又
は右に配置することを示す左右データ選択ビットを含み
、各種の選択を行うセレクションコードＳＣ１入力デー
タの入力順等の属性を示す９ビツトのカラー／世代識別
番号ＯＮ並びに演算の行われるべき場所を示す２１ビツ
トのノード番号ＮＮの６０ビツトにて構成されている。

そしてプロセッサ選択ビットＰＳとカラー／世代識別番
号ＤＮ４ノード番号ＮＮとから識別コードである３１ビ
ツトの識別子が構成される。

ハツシュメモリ６０１はカラー／世代識別番号ＤＮの下
位３ビツト及びノード番号ＮＮの下位６ビツトの合計９
ビツトをハツシュアドレスとしてアクセスされるもので
あり、リードライトサイクルを定めるリードライト信号
Ｗ／π・Ｈ１書込みデータ及び各アドレスの有効・無効
の別を示すプレゼンスビットＰＢの更新を行うセットリ
セット信号Ｓ／πが与えられる。格納される書込みデー
タは１８ビツトのオペランドデータと、カラー／世代識
別番号ＤＮ及びノード番号ＮＮの残り２１ビツトの識別
子と、１ビツトのプロセッサ選択ビットＰＳの合計４０
ピントからなっている。またハツシュメモリ６０１には
別に１ビツトのプレゼンスビットＰＢが格納されており
、合計１ワード４１ビツトとなっている。またアドレス
空間は２’　＝５１２となっており、ハツシュメモリ６
０１は４１とット／ワード×５１２の大きさを有してい
る。

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

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

これを回避する従来技術として［沖電気研究開発報告］
第１９〜第２６真に開示されたデータ駆動形処理装置及
び本出願人による発明（特願昭６１−２７７０４０号）
がある。

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

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

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

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

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

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

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

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

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

この発明に係るデータ検索装置は、パケットのＭ個のＮ
ビットの識別データのビット列からにビットのビット列
を複数選択し、選択されたにビットのビット列の排他的
論理和演算等の逆算可能な演算によりパケットの格納ア
ドレスを生成し、生成されたアドレスにパケットの一部
又は全部をメモリに格納すると共に、格納されたパケッ
トと格納アドレスが等しいパケットが入力されたとき、
格納された識別データの一部又は全部と入力された識別
データの一部又は全部とを比較し、その−致／不一致を
判定する判定手段を設けたものである。さらに不一致の
とき、識別データを検索データとし、格納する連想メモ
リと、前記入力された識別データの一部又は全部とメモ
リ又は連想メモリに格納された識別データの一部又は全
部とを比較し、−敗したか否かの別によりそれらからの
出力を選択する選択手段を設けるようにしたものである
。

〔作用〕

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

〔実施例〕

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

第１図はこの発明に係るデータ検索装置をデータ駆動形
プロセッサの発火処理装置に用いた場合の構成を示すブ
ロック図である。図において６１２は入力セレクタであ
り、後述するＦＩＦＯメモリ６１１から出力されたパケ
ットと入力されたパケットとを選択する。なおパケット
はそのビットマツプを第１０図に示すごと＜６２ビツト
の幅を有している。

選択されたパケットはデータラッチ６０８に与えられ、
そこでデータ入力信号ＣＯが“Ｈ”のタイミングでラッ
チされる。ラッチされたパケットはその３１ビツトの識
別子のうち、カラー／世代識別番号ＯＮの９ビツトと、
ノード番号ＮＮの下位９ビツトとが、排他的論理和演算
を行いハツシュアドレスを生成するアドレス生成手段で
ある演算器１０１の２つの入力端子に夫々与えられる。

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

また３１ビツトの識別子と１８ビツトのオペランドデー
タＯＤとは連想メモリ部６０２にも与えられる。

また識別子のうちノード番号ＮＮの下位９ビツトを除い
た２２ビツトと、１８ビツトのオペランドデータＯＤと
を合わせた４０ビツトの書込みデータがハツシュメモリ
６０１に与えられる。

第３図はハツシュメモリ６０１の構成を示すブロック図
であり、ハツシュメモリ６０１は４１ビツトのビット幅
を有し、２”（＝５１２）のアドレス空間を有している
。そして１８ビツトのオペランドデータｏＤと、３１ピ
ントの識別子のうちノード番号ＮＮの下位９ビツトを除
いた２２ビツトとが格納されると共に、そのアドレスの
内容の有効（ＰＨ＝　１）、無効（ＰＨ＝Ｏ）の別を示
すフラグであるプレゼンスビットＰＲが格納されている
。ハツシュメモリ６０１には前述の如く９ビツトのハツ
シュアドレスと４０ビツトの書込みデータが与えられる
と共に、後述する制御部６０６からそのリードライトサ
イクルを定めるリードライト信号Ｗ／Ｔ−Ｈと、プレゼ
ンスビットＰＢの更新を行うセット信号Ｓ／πとが与え
られ、リードライト信号Ｗ／π・Ｈ＝“Ｈ′のサイクル
で書込みされ、Ｗ／π・Ｈ＝“Ｌ”のサイクルで指定さ
れたアドレスの読出しデータとプレゼンスビットとが出
力される。

第４図は連想メモリ部６０２の構成を示すブロック図で
ある０図において２０１はハツシュ衝突したときにデー
タラッチ６０８からの３１ビツトの識別子と一致するデ
ータを検索する連想メモリ　（以下ＣＡＭという）であ
り、３２ビツト×３２アドレスの容量となっている。　
ＣＡＭ　２０１のうち１ビツトは前記ハツシュメモリ６
０１と同様に格納されているデータの有効性を判別する
ためのプレゼンスビットＰＢの格納に用いられる。　Ｃ
ＡＭ　２０１には各アドレスに対して一部、不−敗検索
ライン（以下マツチラインという）が設けられており、
与えられた３１ビツトの識別子と、ＣＡＭ　２０１に格
納された識別子とが全て一致したアドレスの３２ビツト
のマツチラインの１ビツトが“Ｈ”となる判定信号が出
力される。またＣＡに２０１にはセレクタ２０５を介し
てプレゼンスビットＰＲの更新を行うセット信号Ｓ／π
が与えられると共にリードライトのサイクルを定めるリ
ードライト信号Ｗ／π・Ｃが与えられる。セレクタ２０
５は一端に基準電圧が、他端にセント信号Ｓ／Ｔが与え
られており、また切換端子にはリードライト信号Ｗ／π
・Ｃが与えられており、リードサイクルのときは基準電
圧が、ライトサイクルのときはセット信号Ｓ／πが選択
される。即ちリードサイクル（Ｗ／π・Ｃ＝Ｌ）のとき
は、プレゼンスビットＰＲ＝１のアドレスだけを検索す
る必要があるので、検索データのプレゼンスビットＰＲ
に相当するビットを常に１とし、ライトサイクル（Ｗ／
π・Ｃ＝Ｈ）のときのみプレゼンスビットＰＢを更新す
る必要があるためにこのセレクタ２０５は用いられる。

またＣＡＭ　２０１からは３２ビツトのマツチラインに
識別子の一部、不一致の別を示す判定信号が出力される
と共に、空アドレス検出器２０３に各アドレスのプレゼ
ンスビットＰＲが出力され、そこでプレゼンスビットＰ
Ｂにより空アドレスが検出される。

空アドレス検出器２０３は３２ビツトの検出信号をアド
レスセレクタ２０４の一端に出力すると共に空アドレス
がなく　ＣＡＭ　２０１の全アドレス空間にハツシュ衝
突したパケットの識別子が格納されたとき、そのことを
示すフル信号ＦＬを制御部６０６に出力する。なお検出
信号はＣＡＭ　２０１のアドレスに対応する３２ヒツト
の出力であり、その空アドレスのビットが“Ｈ”となっ
ている。アドレスセレクタ２０４の他端にはマツチライ
ンからの判定信号が与えられ、その切換端子に与えられ
たリードライト信号Ｗ／π・Ｃのリードライトに応じア
ドレスセレクタ２０４はリードサイクルのときは判定信
号を、またライトサイクルのときは空アドレス検出器２
０３の検出信号を夫々選択する。アドレスセレクタ２０
４のアドレス選択出力はＲＡＭ　２０２に与えられ、そ
れにより指定されたアドレスがアクセスされる。ＲＡＭ
２０２はオペランドデータを格納するためのものであり
、１８ビツト×３２アドレスの容量となっている。

リードライト信号Ｗ／π・Ｃ及びアドレス選択出力に応
じてオペランドデータの読書きが行われる。

即ちリードサイクルではＲＡＭ　２０２のアドレスライ
ンには判定信号が与えられ、ＣＡＭ　２０１に入力され
たパケットの識別子と一致する識別子がＣＡＭ　２０１
に格納されている場合（これをＣＡＭ　２０１がヒツト
したという）、判定信号に応じたアドレスの１８ビツト
のオペランドデータが読出しデータとして出力される。

この読出しデータは判定信号とマージされ、５０ビツト
の出力信号としてデータラッチ６０９に出力される。ま
たＣＡＭ　２０１がヒツトしなければ判定信号は３２ビ
ツト全て“Ｌ”のままであり、ＲＡＭ２０２からは如何
なるオペランドデータも読出されない。

一方ライトサイクルでは空アドレス検出器２０３から検
出信号が選択され、ＣＡＭ　２０１とＲＡＭ　２０２の
いずれかのアドレスに３１ビツトの識別子と１８ビツト
のオペランドデータ００とを格納するか指示する。

またＣＡＭ　２０１がヒツトした場合はプレゼンスビッ
トＰＢを更新する必要が生じるので、ライトサイクルに
てＣＡＭ　２０１に与えられるアドレスはヒツトしたア
ドレスである。

入力されたパケットとハツシュアドレスとが等しいハツ
シュメモリ６０１内の４０ビツトの格納データ、ハツシ
ュメモリ６０１のプレゼンスビットＰＲ及び連想メモリ
部６０２の出力信号はデータラッチ６０９にクロックＴ
１のタイミングでラッチされ、プレゼンスビットＰＢは
制御部６０６へ、また格納データのうちの２２ビツトの
識別子は一致検出器６０３の一端へ、格納データのうち
の１８ビツトのオペランドデータ００は出力セレクタ６
０５の一端へ夫々与えられる。また連想メモリ部６０２
の出力信号のうち３２ビツトの判定信号はヒツト検出器
６０４へ、また１８ビツトのオペランドデータＯＤは出
力セレクタ６０５の他端へ与えられる。

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

またヒツト検出器６０４はＣＡＭ　２０１からの３２本
のマツチラインの反転信号をモニタし、その中の１ビツ
トでも“Ｈ”に立上ったものがあった場合は（＝ＣＡＭ
　２０１がヒツトすれば）、ヒツト信号＋１１７を制御
部６０６及び出力セレクタ６０５の切換端子に与える。

出力セレクタ６０５は、入力されたパケットの識別子と
ハツシュメモリ６０１又は連想メモリ６０２内に格納さ
れた識別子とが全て一致する発火対象の相手データが検
索された場合に一致した識別子を格納した方のメモリか
らのオペランドデータＯＤを選択するものである。選択
結果のオペランドデータ００はデータラッチ６１０に与
えられ、制御部６０６からのクロックＴ２の“Ｈ”のタ
イミングでラッチされ、データ対形成器６０７の一端に
与えられる。

出力セレクタ６０５の選択は切換端子に与えられたヒツ
ト信号器Ｔにより行われ、ＣＡＭ　２０１がヒツトした
場合にのみ連想メモリ部６０２に格納されていたオペラ
ンドデータ００を選択し、ヒツトしなかった場合にはハ
ツシュメモリ６０１に格納されていたデータを選択し、
データラッチ６１０に送る。

データ対形成器６０７は出力セレクタ６０５により選択
されたオペランドデータＯＤが一端に入力されると共に
他端には、データラッチ６０Ｂからの６２ビツトの入力
されたパケットのデータが与えられる。

そして２つのデータがマージされ８０ビツトの２オペラ
ンドデータが形成される。このとき２項演算の減算命令
の如くオペランドの順序関係が重要なものがあるので、
選択されたオペランドデータ００と入力されたパケット
のオペランドデータＯＤとは正しく左又は右のオペラン
ドとして配置される必要がある。

第５図はデータ対形成器６０７の構成を示すブロック図
である。データ対形成器６０７は２つのデータセレクタ
７０１．７０２からなり、夫々の切換端子には入力され
たパケットの左／右データ選択ビットでその状態を示す
セレクタ制御信号Ｌ／πが与えられる。データセレクタ
７０１のＡ端子及びデータセレクタ７０２のＢ端子には
データラッチ６０８よりの入力されたパケットのオペラ
ンドデータＯＤが夫々与えられ、データセレクタ７０１
のＢ端子及びデータセレクタ７０２のＡ端子にはデータ
ラッチ６１０よりの格納されたオペランドデータ００が
与えられる。そして入力されたパケットのオペランドデ
ータＯＤからのセレクタ制御信号Ｌ／πが“１”のとき
は夫々のデータセレクタ７０１．７０２のＡ端子に与え
られたオペランドデータが、またＬ／πが”０”のとき
はＢ端子に与えられたオペランドデータが選択され、デ
ータセレクタ７０１からの選択出力が左オペランドとな
り、データセレクタ７０２からの選択出力が右オペラン
ドとなり、それらと入力されたパケットのオペランドデ
ータ００を除く他のデータとがマージされ出力される。

制御部６０６はプレゼンスビットＰＢ、ヒント信号ＨＩ
Ｔ　、−敗信号１１ｉＱ、入力されたパケットが２人力
命令か１人力命令かの別を示すＦＣ処理選択ビットの状
態で定まる入力選択信号ＦＣ（２入力命令ＦＣ＝１．１
入力命令ＦＣ＝０）及びフル信°号ＦＬが与えられ、そ
れらを判断してリードライト信号Ｗ／π・Ｃ，Ｗ／π・
Ｈ、セット信号Ｓ／Ｔ、データ出力信号Ｃ１及び後述す
るＦＩＦＯメモリ６１１への書込信号ＷＲＦを出力する
。またデータ入力信号ＣＯ、データ出力許可信号■が入
力され、それらを判断してデータ入力許可信号■、クロ
ックＴ１及び同Ｔ２を出力する。ここでデータ入力信号
ＣＯ及びデータ入力許可信号■はこの発火処理装置と、
この装置に対してデータを与える処理装置（以下前段装
置という）との間のデータ転送制御信号であり、データ
出力信号Ｃ１及びデータ出力許可信号■はこの装置の出
力するデータを受取る処理装置（以下後段装置という）
との間のデータ転送制御信号である。

制御部６０６にフル信号ＰＬが入力され、さらにハツシ
ュ衝突が生じた場合、制御部６０６から２ボートタイプ
のＦＩＦＯメモリ６１１に書込み信号−ＲＰが与えられ
る。このときＦＩＦＯメモリ６１１はデータ対形成器６
０７からの出力信号のうち入力されたパケットの６２ビ
ツトのデータを格納し、それを所定時間バッファリング
した後二人力セレクタ６１２の他端に与える。この間に
ハツシュ衝突の原因となったハツシュアドレスのハツシ
ュメモリ６０１内のデータか、またはＣＡＭ　２０１内
のデータのいずれかのデータが読出されて発火されてい
る場合はＦＩＦＯメモリ６１１を経由して再び入力され
たパケットはこの装置内のハツシュメモリ６０１又は連
想メモリ部６０２のいずれかで待合せを行うことができ
る。

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

次に以下の如く構成されたこの発明の発火処理装置の動
作について説明する。なおハツシュメモ＋７６０１には
データ対を待つ複数のパケットが格納されているとする
。第６図はこの発明の概略動作を説明するフローチャー
トである。パケットが入力されると（Ｓｌ）、９ビツト
のハツシュアドレスがカラー／世代識別番号ＤＮ（９ビ
ツト）とノード番号ＮＮの下位９ビツトとの排他的論理
和により生成される（Ｓ２）。次にハフシュメモリ６０
１のそのハツシュアドレスに有効なデータが既に格納さ
れているか否かが判定され（Ｓ３）、格納されていない
場合は入力パケットをハツシュメモリ６０１のそのハツ
シュアドレスに格納しくＳ４）、格納されている場合は
２２ビツトの他の識別子が一致しているか否かが判定さ
れ（Ｓ５）、一致していない場合はハツシュ衝突が生じ
ているので、入力パケットを連想メモリ部６０２に格納
しくＳ６）、一致した場合はハツシュメモリ６０１内の
格納データを選択しくＳ９）、それと入力パケットとを
データ対となす発火処理を行う（Ｓ１２）。

また連想メモリ部６０２に格納した後、そのメモリ部６
０２が満杯か否かが判定され（Ｓ７）、満杯のときは入
力パケットをＦＩＦＯメモリ６１１に格納し、満杯でな
いときはそのまま次処理に移る。

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

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

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

即ち、任意の２進敗ａ、ｂに対してａ■ｂ＝ｃならばｂ
　＠　ｃ　＝　ａが成立する演算子により下記式６式％
）但し　ｋ、・・・ｋ、ｌ・・・識別コードによりハツシ
ュアドレスを生成してもよい。

ハツシュアドレスが定められると、リードサイクルでは
ハツシュメモリ６０１　と連想メモリ６０２とが同時に
読出される。メモリ読出しに必要な時間が経過すると々
ロックＴ、が“Ｏ”−“１”に変化し、読出されたデー
タはデータラッチ６０９にラッチされる。ここから処理
サイクルに入り、一致検出器６０３及びヒツト検出器６
０４はハツシュメモ１７６０１及び連想メモリ部６０２
より読出された各データに基づいて一致信号ＥＱ及びヒ
ツト信号旧Ｔを出力する。即ち一致検出器６０３はハツ
シュ衝突が起こっているか否かを検出するものであり、
データランチ６０８に入力されているパケ・ノドの識別
子とハツシュメモリ６０１から読出されたデータラ・ノ
チ６０９にラッチされている識別子との比較を行う。

即ちカラー／世代識別番号ＤＮの９ビツト、ノード番号
ＮＮの上位１２ビツト及びプロセッサ識別ビットの１ビ
ツトの計２２ビットの比較を行う。これらの２２ビツト
が全て等しいと判定されると、９ビツトのハツシュアド
レスが等しく、また９ビツトのカラー／世代識別番号Ｄ
Ｎが等しいので、ノード番号ＮＮの下位９ビツトも等し
いことになり、３１ビツトの識別子の全てが等しいと判
定され、一致検出器６０３は一致信号ＥＱ＝“ビを制御
部６０６に出力する。

即ち入力されたパケットのカラー／世代識別番号ＤＮの
９ビツトをｇ、ノード番号ＮＮの上位！２ビットをＮＡ
、下位９ビツトをＮ、とし、ハツシュメモリ６０１内に
格納されているカラー／世代識別番号ＤＮをｇＭ、ノー
ド番号ＮＮの上位１２ビツトをＮ。

とすると、ハツシュアドレスＡは前述の如くＡ＝ｇ■Ｎ
　・・・（１）　　■：排他的論理和又はＮｙｒ＝ｇ■
Ａ　・・・（２）によって求められ、このハフシュアドレスＡによりハツ
シュメモリ６０１をアクセスしている。ハツシュメモリ
６０１上にノード番号ＮＮの２１ビツトのうち下位９ビ
ツトは格納されていないので、それを求めなければ入力
パケットの下位９ビットＮ、との比較はできない。

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

そしてヒツト検出器６０４では連想メモリ部６０２に格
納されている識別子とデータラッチ６０８に入力されて
いるパケットの識別子とが等しい場合、即ち３２ビツト
のマツチラインのいずれかが“Ｈ”となったときにヒツ
ト信号ＨＩＴ　＝“１”を出力する。

上述の操作に必要な時間が経過すると、クロックＴ２が
“０”→“１”に変化し、ライトサイクルに入る。ライ
トサイクルではプレゼンスビットＰＲの更新を含むメモ
リの書込みとデータ対の生成が行われる。これらの操作
に必要な時間が経過すると制御部６０６はデータ出力信
号Ｃ１を出力し、クロックＴ、、Ｔ、及びデータ入力許
可信号ｎの復帰を行い一連の処理を終了する。但しデー
タ出力信号Ｃ１の出力は入力されたパケットが発火した
ときだけであり、発火しなかった場合は、クロックＴ＋
　、Ｔｔ及びデータ入力許可信号■の復帰だけを行い、
データ出力信号Ｃ１は出力されない。そしてこのライト
サイクルではプレゼンスビットＰＢ。

一致信号ＥＱ、ヒツト信号＋１１７　、フル信号ＰＬ及
び入力選択信号ＦＣによってリードライト信号Ｗ／π・
Ｈ９Ｗ／π・Ｃ，ＦＩＦＯメモリ６１１の書込信号−計
及びセット信号Ｓ／πが制御部６０６で生成される。

この真理値表を第８図に示す。これによりハツシュメモ
リ６０１及び連想メモリ部６０２に入力されたパケット
を書込むか否かを定め、下記の如くの動作をする。

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

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

第８図の（３）及び（４）はハツシュメモリ６０１に有
効なデータが格納されていたが、それがハツシュ衝突を
起こした場合を示す（ＰＲ＝　Ｉ　、　ＥＱ　＝　０）
。そして（３）ではＣＡＭ　２０１でもヒントしなかっ
たため（ｌＩＩＴ＝Ｏ）、入力されたデータは連想メモ
リ部６０２に格納され（Ｗ／π・Ｃ＝１．Ｓ／π−１）
データの出力は行われない（Ｃ１＝Ｏ）。（４）ではＣ
ＡＭ　２０１がヒツトしたため（）ＩＩＴ　＝　１）、
入力されたパケットは連想メモリ部６０２の内容と発火
し、出力される（Ｃ１＝１）。ここでＣＡＭ　２０１の
プレゼンスビットＰＲがリセットされなければいけない
ので、リードライト信号Ｗ／π・Ｃ＝１．セット信号Ｓ
／Ｔ＝０とされる。（５）及び（６）はハツシュメモリ
６０１に有効なデータが格納されていなかった場合であ
り　（ＰＢ　＝　Ｏ）、一致信号ＥＱの値に意味はない
。（５）ではＣＡＭ　２０１がヒツトしなかった場合を
示しくＨＩＴ＝０）、入力されたパケットはハツシュメ
モリ６０１に書込まれる（Ｗ／π・Ｈ＝１．Ｓ／π−１
，ＣＩ＝０）。（６）ではＣＡＭ　２０１がヒツトして
おり、（４）と同様な操作を行う、また（７）はハツシ
ュメモリ６０１に有効なデータが格納されていたがそれ
がハフシュ衝突を起こしくＰＲ＝１　、　Ｅ口＝０）、
連想メモリ部６０２に格納する必要が生じたが、ＣＡＭ
　２０１が満杯となり全アドレスが有効となった場合（
ＰＬ　＝　１）を示し、入力されたパケットはＦＩＦＯ
メモリ６１１に所定時間をバッファリングされる（ＷＲ
Ｆ　＝　１）。第８図を参照して述べた動作は全てライ
トサイクルにおけるものであり、ライトサイクル以外の
動作ではリードライト信号Ｗ／π・Ｈ，Ｗ／π・Ｃは常
に“０”となっている。

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

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

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

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

このビットリバースを用いた場合の効果について詳しく
説明する。発火処理装置においては、パケットのカラー
／世代識別番号ＤＮは続き番号で流れてくることが多い
。例えばカラー／世代識別番号ＤＮ＝１ｎとノード番号
ＮＮの下位９ビツト＝　２　Ｎとを有するパケットの後
にカラー／世代識別番号ＤＮ＝２Ｈとノード番号ＮＮの
下位９ビツト＝１１１を有するパケットが入力されると
いうようにである。

この場合、それらの排他的論理和は等しいので双方のハ
ツシュアドレスは等しく、識別子が一致していないので
ハツシュ衝突が生じる。

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

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

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

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

〔発明の効果〕

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

【図面の簡単な説明】

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

Claims

【特許請求の範囲】

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