JPH0384685A

JPH0384685A - データ検索装置

Info

Publication number: JPH0384685A
Application number: JP22222889A
Authority: JP
Inventors: Hirono Tsubota; 浩乃坪田; Nobufumi Komori; 伸史小守
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1989-08-29
Filing date: 1989-08-29
Publication date: 1991-04-10

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は識別データの一致するデータを検索するデー
タ検索装置に関し、特に識別データの一致するデータの
対を生成することによってプログラム実行順序を動的に
決定するデータ駆動形プロセッサの発火処理部に用いる
データ検索装置に関する。

〔従来の技術］第９図はデータ駆動形プロセッサの発火処理の概念図で
あり、２つのデータの加算が行われる様子を示している
。図において”Ａ”という値を持ち”ａ″という識別子
を付加されたパケット８１が発火処理部８７に与えられ
ると、識別子フィールド比較部８４はマツチングメモリ
である待合せメモリ８５にパケット８１の識別子”ａ”
と一致する識別子を持つパケットが格納されているか否
かを検索する。第９図では”Ｂ“という値を持ち′ａ”
という識別子を持つパケット８２が格納されているので
、このパケット８２が待合せメモリ８５から読出され、
入力されたパケット８１と共にデータ対形成部８６へ送
られる。

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

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

このように発火処理部８７はデータ駆動形プロセッサに
おいて演算すべきパケ・ントを検索する役割を持ってい
る。

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

第１Ｏ図は入力パケットの一例の構成を示すビ・ントマ
ップ図である。

入力パケットは演算対象となる１８ビツトのオペランド
データＯＤ、演算内容を示すコードである７ビツトのオ
ペレーションコードＱＣ，１ビツトのプロセッサ選択ビ
ットＰＳ、入力パケットが２入力命令か１入力命令かを
示す１ビツトのＦＣ処理選択ビット及び演算項に応じて
左又は右に配置すること。

を示す左右データ選択ビットを含み、各種の選択を行う
セレクションコードＳＣ１入力データの入力順等の属性
を示す９ビツトのカラー／世代識別番号ＤＮ並びに次に
実行すべき命令の格納場所を示す２１ビツトのノード番
号ＮＮの６０ビツトにて構成されている。そしてプロセ
ッサ選択ビットＰＳとカラー／世代識別番号ＤＮとノー
ド番号ＮＮとから識別コードである３１ビツトの識別子
が構成される。

通常データ駆動形の計算機は複数接続されて使用される
。プロセッサ選択ビットが１”の場合は演算実行後、次
の演算は他の計算機で実行を行うことを示す。この場合
、ノード番号の上位９ビツトは次に演算を行う計算機の
計算機番号を格納し、ノード番号は下位１２ビツトで表
現する。

たとえば、ハツシュアドレスは、カラー／世代識別番号
ＯＮの下位３ビツト及びノード番号の下位６ビツトを結
合することで生成される。この場合、ハツシュメモリに
はオペランドデータと、ハツシュアドレス生成に使用さ
れなかったカラー／世代識別番号ＤＮ及びノード番号Ｎ
Ｎの残り２１ビツトと、プロセッサ選択ビットＰＳの合
計４０ビツトが格納される。

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

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

これを回避する従来例として本出願人による発明（特願
平１−１０２７１２号）がある。

これは、複数の識別データからハツシュアドレスを生成
する場合に、各識別データからにビットを抽出し、それ
らの演算に基づき生成することにより識別データが類似
している場合であってもメモリの全アドレス空間をアク
セスすることができ、ハツシュ衝突の発生を抑制し、処
理効率を向上させたデータ検索装置を得ることを目的と
したものである。このデータ検索装置は、パケットのＭ
個のＮビットの識別データのビット列からにビットのビ
ット列を複数選択し、選択されたにビットのビット列の
排他的論理和演算等の逆算可能な演算によりパケットの
格納アドレスを生成する。生成されたアドレスにパケッ
トの一部又は全部をメモリに格納する。そして格納され
たパケットと格納アドレスが等しいパケットが入力され
たとき、格納された識別データの一部又は全部と入力さ
れた識別データの一部又は全部とを比較し、その一致／
不一致を判定するようにしたものである。さらに不一致
のとき、識別データを検索データとし、格納する連想メ
モリと、前記入力された識別データの一部又は全部とメ
モリ又は連想メモリに格納された識別データの一部又は
全部とを比較し、−致したか否かの別によりそれらから
の出力を選択するようにしたものである。

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

以下、従来例を図面を用いて説明する。

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

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

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

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

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

ハツシュメモリ６０１　は４１ビツトのビット幅を有し
、２　”（＝５１２）のアドレス空間を有している。そ
して１８ビツトのオペランドデータＯＤと、３１ビツト
の識別子のうちノード番号ＮＮの下位９ビツトを除いた
２２ビツトとが格納されると共に、そのアドレスの内容
の有効（ＰＢ＝１）、無効（ＰＢ　＝　Ｏ）の別を示す
フラグであるプレゼンスビットＰＢが格納されている。

ハツシュメモリ６０１には前述の如く９ビツトのハツシ
ュアドレスと４０ビツトの書込みデータが与えられると
共に、後述する制御部６０６からそのリードライトサイ
クルを定めるリードライト信号Ｗ／Ｔｉ・Ｈと、プレゼ
ンスビットＰＢの更新を行うセット信号Ｓ／Ｔとが与え
られ、リードライト信号Ｗ／ｌ’ｔ・Ｈ＝　”Ｈ”のサ
イクルで書込みされ、Ｗ／１’Ｊ・Ｈ＝”Ｌ＃のサイク
ルで指定されたアドレスの読出しデータとプレゼンスビ
ットとが出力される。

第１２図は連想メモリ部６０２の構成を示すブロック図
である。図において２０１はハツシュ衝突したときにデ
ータラッチ６０８からの３１ビツトの識別子と一致する
データを検索する連想メモリ　（以下ＣＡＭという）で
あり、３２ビツト×３２アドレスの容量となっている。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

制御部６０６はプレゼンスビットＰＢ、ヒツト信号）１
１Ｔ　、一致信号ＥＱ、入力されたパケットが２入力命
令か１入力命令かの別を示すＦＣ処理選択ビットの状態
で定まる入力選択信号ＦＣ（２入力命令ＦＣ＝１．１入
力命令ＦＣ＝Ｏ）及びフル信号ＦＬが与えられ、それら
を判断してリードライト信号Ｗ／Ｗ・Ｃ，Ｗ／ｆｆ・Ｈ
、セット信号Ｓ／π、データ出力信号Ｃ１及び後述する
ＦＩＦＯメモリ６１１への書込信号ＷＲＦを出力する。

またデータ入力信号ＣＯ、データ出力許可信号ＡＩが入
力され、それらを判断してデータ入力許可信号ＡＯ、ク
ロックＴＩ及び同Ｔ２を出力する。ここでデータ入力信
号ＣＯ及びデータ入力許可信号ＡＯはこの発火処理装置
と、この装置に対してデータを与える処理装置（以下前
段装置という）との間のデータ転送制御信号であり、デ
ータ出力信号Ｃ１及びデータ出力許可信号Ａ１はこの装
置の出力するデータを受取る処理装置（以下後段装置と
いう）との間のデータ転送制御信号である。

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

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

次に以下の如く構成された従来の発火処理装置の動作に
ついて説明する。なおハツシュメモリ６０１にはデータ
対を待つ複数のパケットが格納されているとする。第１
３図は従来例の概略動作を説明するフローチャートであ
る。パケットが入力されると（Ｓｌ）、連想メモリ部６
０２では格納された識別子との一致、不一致を判定（Ｓ
ＩＯ）すると共に９ビツトのハツシュアドレスが９ビツ
トのカラー／世代識別番号ＤＮとノード番号ＮＮの下位
９ビツトとの排性的論理和により生成される（Ｓ２）。

次にハツシュメモリ６０１のそのハツシュアドレスに有
効なデータが既に格納されているか否かが判定され（Ｓ
３）、連想メモリ部６０２の識別子と一致せず、かつ（
Ｓ３）でデータが格納されていない場合は入力パケット
をハツシュメモリ６０１のそのハツシュアドレスに格納
しくＳ４）、格納されている場合は２２ビツトの他の識
別子が一致しているか否かが判定され（Ｓ５）、一致し
ていない場合はハツシュ衝突が生じているので、入力パ
ケットを連想メモリ部６０２に格納しくＳ７〉、一致し
た場合はハツシュメモリ６０１内の格納データを選択し
くＳ９）、それと入力パケットとをデータ対となす発火
処理を行う（Ｓ１２）　、ただし、連想メモリ部６０２
の識別子と一致せず、かつ、ハツシュメモリ内の２２ビ
ツトの他の識別子が不一致の時に（Ｓ１４）、メモリ部
６０２が満杯か否かが判定され（Ｓ６）、満杯のときは
入力パケットをＦＩＦＯメモリ６１１に格納しくＳ８）
、満杯でないときは連想メモリ部６０２に格納した後（
Ｓ７）次の処理に移る。

又、入力パケットと連想メモリ部６０２で格納された識
別子との一致、不一致の判定（５１０）で、致したとき
は連想メモリ部６０２の出力を選択しく５ｌｌ）　、発
火処理する（Ｓ１２）。以上が概略動作である。

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

ハツシュアドレスが定められると、リードサイクルでは
ハツシュメモリ６０１　と連想メモリ６０２とが同時に
読出される。メモリ読出しに必要な時間が経過するとク
ロックＴ１が”０″→″１”に変化し、続出されたデー
タはデータラッチ６０９にラッチされる。ここから処理
サイクルに入り、一致検出器６０３及びヒツト検出器６
０４はハツシュメモリ６０１及び連想メモリ部６０２よ
り読出された各データに基づいて一致信号ＥＱ及びヒツ
ト信号同Ｔを出力する。一致検出器６０３はハツシュ衝
突が起こっているか否かを検出するものであり、データ
ラッチ６０８に入力されているパケットの識別子とハシ
シュメモリ６０１から読出されたデータラッチ６０９に
ラッチされている識別子との比較を行う。即ち、カラー
／世代識別番号ＤＮの９ビツト、ノード番号ＮＮの上位
１２ビツト及びプロセッサ識別ビットの１ビツトの計２
２ビットの比較を行う。これらの２２ビツトが全て等し
いと判定されると、９ビツトのハツシュアドレスが等し
く、また９ビツトのカラー／世代識別番号ＤＮが等しい
ので、ノード番号ＮＮの下位９ビツトも等しいことにな
り、３１ビツトの識別子の全てが等しいと判定され、一
致検出器６０３ば一致信号ＥＱ＝”ｌ”を制御部６０６
に出力する。

即ち、入力されたパケットのカラー／世代識別番号ＤＮ
の９ビツトをｇ、ノード番号ＮＮの上位１２ビツトをＮ
Ａ、下位９ビツトをＮ、とし、ハツシュメモリ６０１内
に格納されているカラー／世代識別番号ＯＮをｇＭ、ノ
ード番号ＮＮの上位１２ビツトをＮイとすると、ハツシ
ュアドレスＡは前述の如くＡ＝ｇ［Ｆ］Ｎ　・・・（１
）○：排他的論理和Ｔ又はＮｍ＝ｇ［Ｆ］Ａ　・・・（
２）によって求められ、このハツシュアドレスＡにより
ハ・ンシュメモリ６０１をアクセスしている。ハ・ンシ
ュメモリ６０１上にノード番号ＮＮの２１ビツトのうち
下位９ビツトは格納されていないので、それを求めなけ
れば入力パケットの下位９ビツトＮＩＩとの比較はでき
ない。

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

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

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

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

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

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

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

第１５図の（３）及び（４）はハツシュメモリ６０１に
有効なデータが格納されていたが、それがハツシュ衝突
を起こした場合を示す（ＰＲ＝１．Ｅ口＝０）。そして
（３）ではＣＡ？＋　２０１でもヒツトしなかったため
（ＨＩＴ＝０）、入力されたデータは連想メモリ部６０
２に格納され（Ｗ／脣・Ｃ＝１．Ｓ／頁＝１）データの
出力は行われなイ（Ｃ１＝０）。（４）テはＣＡＭ　２
０１がヒツトしたため（ＨＩＴ＝１）、入力されたパケ
ットは連想メモリ部６０２の内容と発火し、出力される
（ｃ１＝ｌ）。ここでＣＡＭ　２０１のプレゼンスビッ
トＰＢがリセットされなければいけないので、リードラ
イト信号Ｗ／Ｔｒ・Ｃ＝１．セット信号Ｓ／Ｎ＝０とさ
れる。（５）及び（６）はハツシュメモリ６０１に有効
なデータが格納されていなかった場合であり　（ＰＢ＝
０）、一致信号ＥＱの値に意味はない。（５）ではＣＡ
Ｍ　２０１がヒツトしなかった場合を示しくＨＩＴ＝０
）、入力されたパケットはハツシュメモリ６０１に書込
まれる（Ｗ／１・Ｈ＝１．Ｓ／ＴＪ＝１．Ｃ１＝Ｏ）。

（６）ではＣＡＭ　２０１がヒツトしており、（４）と
同様な操作を行う。また（７）はハツシュメモリ６０１
に有効なデータが格納されていたがそれがハツシュ衝突
を起こしくＰＢ＝１　、ＥＱ＝０）、連想メモリ部６０
２に格納する必要が生じたが、ＣＡＭ　２０１が満杯と
なり全アドレスが有効となった場合（ＰＬ　＝　１）を
示し、入力されたパケットはＦＩＦＯメモリ６１１に所
定時間をバッファリングされる（ＷＲＦ＝１）。第１５
図を参照して述べた動作は全てライトサイクルにおける
ものであり、ライトサイクル以外の動作ではリードライ
ト信号Ｗ／ＴＵ・Ｈ，Ｗ／ｌ’ｒ・Ｃは常に”０”とな
っている。

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

またこの従来例ではハシシュ衝突が頻発しＣＡＭ２０１
がオーバフローした場合であっても、入力されたパケッ
トを所定時間ＦＩＦＯメモリ６１１にバッファリングす
るようにしており、ＣＡＭ　２０１の容量を小さくする
ことができ、ＣＡＭ　２０１が満杯となリオーバフロー
した場合に何ら特別の処理を行う必要がないという効果
がある。

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

従来のデータ検索装置は以上のように構成されており、
入力されたパケットがハツシュ衝突し、かつＣＡＭが満
杯の場合、入力されたパケットをＰＩＦＯメモリに出力
していた。このため、ＣＡＭが満杯のとき、発火対象の
パケットが続けて入力されると、それらがＦＩＦＯメそ
りに続けて出力され、２つのパケットの間での発火がな
されないために、それらが処理されないとそれ以後の処
理ができない場合、他の全てのパケットが永遠に発火で
きない状態、即ちデッドロック状態に陥る虞があった。

この発明は従来例を改良し、上記のような問題点を解消
するためになされたものであり、連想メモリ部が満杯の
場合にパケットが入力し、ハツシュ衝突したとき連想メ
モリ部に格納されていたパケットのうち任意の１つのパ
ケットをＦＩＦＯメモリに出力し、あいたアドレスに入
力したパケットを格納することにより、デッドロックを
回避できるデータ検索装置を得ることを目的とする。

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

この発明に係るデータ検索装置は、識別データを検索デ
ータとして格納されたパケットを検索すると共に、所定
の条件で入力パケットの一部又は全部を格納する第１格
納手段を設けると共に、第１格納手段が満杯か否かを判
断する判断手段、満杯と判断されたとき、第１格納手段
に格納されたパケットから任意のアドレスのパケットを
出力し、入力されたパケットをそこに格納すべく制御す
る制御手段及び出力されたパケットを格納すると共に、
格納されているパケットを第１格納手段に出力する第２
格納手段を設けたものである。

〔作用〕

この発明においてはパケットが入力されるとその識別デ
ータを検索データとして格納されているパケットを検索
すると共に、そこに同じ識別子を有するパケットが格納
されていないとき、入力パケットの一部又は全部を第１
格納手段に格納しようとするが、判断手段により第１格
納手段が満杯であると判断されると、第１格納手段に格
納されたパケットのうち任意のアドレスに格納されたパ
ケットを第２格納手段に格納し、空いたアドレスに入力
パケットを格納する。第２格納手段は格納されているパ
ケットを第１格納手段に出力し、そこでデータが検索さ
れる。

〔実施例〕

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

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

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

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

また入力パケットの全ビットは、３１ビツトの識別子と
その他の３１ビツトに分けて、連想メモリ部６０２にも
与えられる。また識別子のうちノード番号ＮＮの下位９
ビツトを除いた２２ビツトと、１８ビツトのオペランド
データＯＤとを合わせた４０ビツトの書込みデータがハ
ツシュメモリ６０１に与えられる。

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

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

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

空アドレス検出器２０３は、空アドレスを示す３２ビツ
トの検出信号をアドレスセレクタの一端に出力すると共
に空アドレスがなく　ＣＡＭ　２０１の全アドレス空間
にハツシュ衝突したパケットが識別子に格納されたとき
、そのことを示すフル信号ＰＬをアドレスセレクタ２０
４　　および制御部６０６に出力する。なお、空アドレ
スを示す検出信号はＣＡＭ２０１のアドレスに対応する
３２ビツトの出力であり、その空アドレスのビットが”
Ｈ”となっている。アドレスセレクタ２０４の他端には
マツチラインからの判定信号が与えられる。また、アド
レスセレクタ２０４の内部にＣＡＭ２０１の追い出しア
ドレスに対応する３２ビツトのアドレス信号を格納する
追い出しポインタ２０６がある。

アドレスセレクタ２０４では、切換端子に与えられたリ
ードライト信号Ｗ／ＴＶ・Ｃに応じて、リードサイクル
のとき（即ち　Ｗ／Ｔｒ・Ｃが”Ｌ”）は判定信号と追
い出しアドレスを、またライトサイクルのときは、通常
は空アドレス検出器２０３の検出信号を、またＣＡＭ　
２０１がフルでＰＬ倍信号”Ｈ”の場合には、追い出し
アドレスを夫々選択する。

アドレスセレクタ２０４のアドレス選ｔＨｉカバｃＡＭ
２０１およびＩ？ＡＭ　２０２に与えられ、それにより
指定されたアドレスがアクセスされる。

ＲＡＭ　２０２は２ポ一トＲＡＭであり、オペランドデ
ータ０Ｄ１８　ビット、オペレーションコードＱＣ７ビ
ツトおよびプロセッサ選択ビットを除くセレクションコ
ードＳＣ６ビツトの合計３１ビツトを格納するものであ
り、３１ビツト×３２アドレスの容量となっている。即
ちリードサイクルでは、ＲＡＭ　２０２の第１のアドレ
スライン２０７に判定信号が与えられ、ＣＡＭ　２０１
に入力されたパケットの識別子と一致する識別子がＣＡ
Ｍ　２０１に格納されている場合（これをＣＡＭ　２０
１がヒツトしたという）、判定信号に応じたアドレスの
オペランドデータの１８ビツトのみが読み出しデータと
して出力される。この読み出しデータは判定信号とマー
ジされ、５０ビツトの出力信号としてデータラッチ６０
９に出力される。同時に、第２のアドレスライン２０８
には、追い出しアドレスが与えられ、追い出しアドレス
に応じたアドレスのＲＡＭ　２０２の３１ビツトのデー
タがＣＡＭ　２０１の識別子３１ビツトとともに、合計
６２ビツトがデータラッチ６０９に出力される。以下こ
の６２ビツトのデータを追い出しパケットデータと呼ぶ
。

一方ライトサイクルではフル信号ＰＬが”Ｈ”で入力さ
れたときには追い出しアドレスが、フル信号が”Ｌ”で
入力されたときには（フルでないとき）空アドレス検出
器２０３からの検出信号が選択され、ＣＡＭ　２０１と
ＲＡＭ　２０２のいずれのアドレスに３１ビツトの識別
子とオペランドデータＯＤ、オペレーションコードＯＣ
およびプロセッサ選択ビットを除くセレクションコード
ＳＣの３１ビツトとを格納するかを指示する。追い出し
アドレスが選択された場合は書き込み終了後、追い出し
ポインタ２０６の追い出しアドレスは１インクリメント
され次のアドレスを指す。但し、追い出しポインタ２０
６にＣＡＭ２０１の最後のアドレスが追い出しアドレス
として格納されている場合は最初のアドレスを指すよう
になっている。

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

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

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

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

出力セレクタ６０５は、入力されたパケットの識別子と
ハツシュメモリ６０１又は連想メモリ６０２内に格納さ
れた識別子とが全て一致する発火対象の相手データが検
索された場合に一致した識別子を格納した方のメモリか
らのオペランドデータＯＤを選択するものである。両方
のメモリで同時に一致が検出されることは方式上あり得
ないので、出力セレクタ６０５は後述する如くヒツト信
号旧Ｔの値のみによって制御されている。選択結果のオ
ペランドデータＯＤはデータラッチ６１０に与えられ、
制御部６０６からのクロックＴ２の”Ｈ”のタイ旦ング
でラッチされ、データ対形成器６０７の一端に与えられ
る。

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

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

そして２つのデータがマージされ、２オペランドデータ
を含む８０ビツトのパケットが形成される。

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

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

出力セレクタ６１３は、発火もしくは１入力命令で出力
されるパケットか、又は、連想メモリ部６０２がフルの
とき、入力パケットを連想メモリ部６０２に格納するか
わりに追い出された追い出しパケットかを選択するもの
である。この選択は制御部６０６から与えられた選択信
号Ｆ／ｒｆによって選択される。この選択信号Ｆ／ｒｆ
は、旧Ｔ　、　Ｅｌｌが”１”のとき、又はＦＣが”０
′のいずれかのとき、＃１”となり、データ対形成器６
０７からの入力が選択される。

制御部６０６はプレゼンスビットＰＢ、ヒント信号ＨＩ
Ｔ　、一致信号ＥＱ、入力されたパケットが２入力命令
か１入力命令かの別を示すＦＣ処理選択ビットの状態で
定まる入力選択信号ＦＣＣ２入力命令ＦＣ＝１．１入力
命令ＦＣ＝Ｏ）及びフル信号ＰＬが与えられ、それらを
判断してリードライト信号Ｗ／１’Ｊ・Ｃ，Ｗ／Ｔｒ・
Ｈ、セット信号Ｓ／ＩＴ、発火または追い出しを指定す
る信号Ｆ／Ｔｆｆ、データ出力信号Ｃ１及び後述するＦ
ＩＦＯメモリ６１１への書込信号ＷＲＦを出力する。

ま゛たデータ入力信号ＣＯ、データ出力許可信号Ａ１が
入力され、それらを判断してデータ入力許可信号ＡＯ、
クロックＴｌ及び同Ｔ２を出力する。ここでデータ入力
信号ＣＯ及びデータ入力許可信号ＡＯはこの発火処理装
置と、この装置に対してデータを与える処理装置（以下
前段装置という）との間のデータ転送制御信号であり、
データ出力信号Ｃ１及びデータ出力許可信号ＡＩはこの
装置の出力するデータを受取る処理装置（以下後段装置
という）との間のデータ転送制御信号である。

制御部６０６にフル信号ＰＬが入力され、さらにハツシ
ュ衝突が生じた場合、制御部からＦ／Ｔｆｆ信号が出力
セレクタ６１３に与えられ追い出し用に連想メモリ部よ
りあらかじめ出力されていた全６２ビツトの追い出しパ
ケットを出力するように制御する。

また、２ポートタイプのＦＩＦＯメモリ６１１に書込み
信号ＷＲＦが与えられる。このときＦＴＰＯメモリ６１
１は追い出されたパケットを一旦、格納し、先入れ先出
し方式により、入力セレクタ６１２の他端に与える。

ＦＩＦＯメモリ６１１は、３２段のシフトレジスタの直
列接続構造になっている。シフトレジスタの段数はＣＡ
Ｍ　２０１のアドレス空間以下となる必要がある。

これはＦＩＦＯメモリ６１１に格納されたパケットと発
火対象のパケットとが同時にＦＩＦＯメモリ６１１に格
納されることを防ぐためである。発火処理装置より追い
出されたパケットはシフトレジスタ３２段分の転送遅延
時間の後また、入力セレクタ６１２の他端に入力される
。

従来の発火処理装置で観測されていたデッドロックは、
本来発火すべき２つのパケットがＦＩＦＯメモリ６１１
に出力され続け、発火がなされず、他のすべてのパケッ
トが永遠に発火できないというものであった。

本発明の発火処理装置では本来発火すべきパケットＡお
よびパケットＢがともにＦＩＦＯメモリ６１１に追い出
されたとしても、いずれかのパケットたとえばパケット
Ａが発火処理装置に再び入力されるとすでに格納されて
いるパケットを追い出すことになり、パケットＡは、必
ず連想メモリ部６０２に格納される。このとき次にパケ
ットＡが追い出されるのは、連想メモリ部６０２のアド
レス数が３２であり、追い出しアドレスは１インクリメ
ントするので、少なくとも発火処理装置で３２回以上の
処理を行った後である。一方、パケットＢは３２段のＦ
ＩＦＯメモリ６１１のいずれかの段にある。発火処理装
置が３２回の処理を終了する前に必ず入力セレクタ６１
２を介して入力され、パケットＡとパケットＢとは必ず
発火でき、デッドロック状態は回避される。

次に以下の如く構成されたこの発明の発火処理装置の動
作について説明する。なおハツシュメモリ６０１にはデ
ータ対を待つ複数のパケットが格納されているとする。

第６図はこの発明の概略動作を説明するフローチャート
である。

パケットが入力されると（Ｓｌ）、連想メモリ部６０２
では格納された識別データとの一致／不一致を判定（Ｓ
１０）するとともに、演算器１０１において、９ビツト
のハツシュアドレスが９ビツトのカラー／世代識別番号
ＤＮとノード番号ＮＮの下位９ビツトとの排他的論理和
により生成される（Ｓ２）。

ステップ１０の結果、不一致の場合には、連想メモリ部
６０２より追い出しポインタ２０６の指すパケットをデ
ータラッチ６０９にコピーしておく　（Ｓ１５）。

次にハツシュメモリ６０１のステップ２で生成されたハ
ツシュアドレスに有効なデータが既に格納されているか
否かが判定され（Ｓ３）、連想メモリ部６０２の識別子
と一致せず（ステップ１０の判断ＮＯ）、かつ、ステッ
プ３でデータが格納されていない場合は入力パケットを
ハツシュメモリ６０１のそのハツシュアドレスに格納し
する（Ｓ４）。格納されている場合は２２ビツトの他の
識別子が一致しているか否かが判定され（Ｓ５）、一致
していない場合はハツシュ衝突が生じている。

ここでさらに、連想メモリ部６０２の識別子と一致しな
い（ステップ１０でＮＯの判断）場合は、入力パケット
を連想メモリ部６０２に格納する（Ｓ６）。ここで格納
するアドレスは、連想メモリ部６０２に空アドレスがあ
る場合は空アドレスに、連想メモリ部６０２がフルの場
合は、追い出しポインタ２０６の指すアドレスである。

また、追い出しポインタ２０６の指すアドレスに入力パ
ケットを格納した場合は、追い出しポインタ２０６の追
い出しアドレスを１インクリメントし、次のアドレスを
ポイントするようにする。また、連想メモリ部６０２が
フルの場合は、追い出しポインタ２０６の指すアドレス
に格納し、同時にステップ１５で書き出しておいた追い
出しパケットをＦＩＦＯメモリ６１１に送出する（Ｓ１
６）。

一方、ステップ５で他の識別子と一致した場合はハツシ
ュメモリ６０１内の格納データを選択しくＳ９）、それ
と入力パケットとをデータ対となす発火処理を行う（Ｓ
１２）。

また、入力パケットと連想メモリ部６０２で格納された
識別子との一致／不一致の判定で、一致したときは連想
メモリ部６０２の出力を選択しく５ｌｌ）、発火処理す
る（Ｓ１２）。以上が発明装置の論理的な動作である。

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

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

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

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

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

このライトサイクルでの制御は、プレゼンスビットＰＢ
、一致信号ＥＱ、ヒツト信号Ｉｔ　Ｉ　Ｔ　。

フル信号ＰＬ及び入力選択信号ＦＣによってリードライ
ト信号Ｗ／−・Ｈ，Ｗ／Ｗ・Ｃ，ＦＩＦＯメモリ６１１
の書込信号ＷＲＦ及びセット信号Ｓ／πが制御部６０６
で生成されることにより行われる。この真理値表を第８
図に示す。これによりハツシュメモリ６０１及び連想メ
モリ部６０２に入力されたパケットを書込むか否かを定
め、下記の如くの動作をする。

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

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

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

（Ｗ／π・Ｃ＝１、Ｄ／Ｆ”＝０、ＷＲＦ　＝　１　）
。第８図を参照して述べた動作は全てライトサイクルに
おけるものであり、ライトサイクル以外の動作ではリー
ドライト信号Ｗ／７’Ｊ−Ｈ，Ｗ／Ｗ・Ｃは常に”０”
となっている。

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

なお、この実施例では検索データの格納場所としてハツ
シュメモリと連想メモリの両方がある場合について記述
したが、この発明は、ハツシュメモリがなく、連想メモ
リのみに検索データを格納するデータ検索装置に対して
も適用できる。

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

さらに、この実施例では追い出しアドレスを１ずつイン
クリメントする所謂ラウントロピン方式で指定したので
、ＦＩＦＯメモリの段数をＣＡ）１のアドレス空間の数
より小さくする必要があったが、この発明はこれに限る
ものではなく、ＦＩＦＯメモリの段数はＣＡＭのアドレ
ス空間より大きくてもよい。

また第２格納手段はＦＩＦＯメモリではなく他の記憶手
段でもよいことは言うまでもない。

〔発明の効果〕

以上説明したようにこの発明によれば、ハツシュ衝突が
生じたときに第１格納手段が満杯であっても、そのこと
を判断すると、追い出しアドレスで指定されるアドレス
のパケットを第２格納手段に格納し、入力されたパケッ
トを第１格納手段に格納するので、ハツシュ衝突が頻発
し、第１格納手段がオーバフローした状態でも必ず互い
に発火すべきパケットは発火することができ、デッドロ
ック状態を回避することができる等優れた効果を奏する
。

【図面の簡単な説明】

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

Claims

【特許請求の範囲】

（１）入力パケットの識別データを検索データとしてそ
こに格納されているパケットを検索すると共に、所定の
条件のもとで、入力パケットの一部又は全部を格納する
第１格納手段と、該第１格納手段が満杯か否かを判断す
る判断手段と、該判断手段が前記第１格納手段が満杯であると判断した
とき、既に格納されているパケットのうち任意のアドレ
スに格納されているパケットを出力すべく制御すると共
に、入力されたパケットを前記アドレスに格納すべく制
御する制御手段と、出力されたパケットを格納すると共に、格納されている
パケットを前記第１格納手段に出力する第２格納手段とを備えることを特徴とするデータ検索装置。