JPH0419570B2 - - Google Patents
Info
- Publication number
- JPH0419570B2 JPH0419570B2 JP58005709A JP570983A JPH0419570B2 JP H0419570 B2 JPH0419570 B2 JP H0419570B2 JP 58005709 A JP58005709 A JP 58005709A JP 570983 A JP570983 A JP 570983A JP H0419570 B2 JPH0419570 B2 JP H0419570B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- hashing
- bit
- groups
- bit array
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】
１ 発明の属する分野の説明
本発明は複数個のデータ群の中から、データ内
容が全てのデータ群について相互に一致している
可能性のあるデータを選別するデータ選別方式に
関するものである。
容が全てのデータ群について相互に一致している
可能性のあるデータを選別するデータ選別方式に
関するものである。
２ 従来の技術の説明
データ管理の分野において、特に、２つのデー
タ群の中から相互にデータ内容の一致するデータ
を取り出して結合する場合、結合処理に要する処
理時間が大きいため、あらかじめ各々のデータ群
から結合可能性の無いデータを除去し、結合処理
時間を短縮させるデータ選別操作がしばしば行な
われる。このデータ選別のためには、ハツシング
装置とビツトアレイを使用するのが一般的であ
る。
タ群の中から相互にデータ内容の一致するデータ
を取り出して結合する場合、結合処理に要する処
理時間が大きいため、あらかじめ各々のデータ群
から結合可能性の無いデータを除去し、結合処理
時間を短縮させるデータ選別操作がしばしば行な
われる。このデータ選別のためには、ハツシング
装置とビツトアレイを使用するのが一般的であ
る。
従来、この種の装置は、LEECH(D.R.Mc
Gregor,R.H.Thomson、W.N.Dawson:High
Performance Hardware for Database
Systems,in Systems for Large Data Bases,
PP.103-116,North-Holland,1976.)や、
CAFS((1) E.Babb:Implementing a
Relational Database by Means of
Specialiyed Hardware, ACM Trans.Database
Syst.,Vol.4,No.1,PP.1-29,March 1979.(2)
E.Babb:Patent Application No.27093/74,
June 1974(Hashed Bit Arrays Store).)などの
システムで用いられている。
Gregor,R.H.Thomson、W.N.Dawson:High
Performance Hardware for Database
Systems,in Systems for Large Data Bases,
PP.103-116,North-Holland,1976.)や、
CAFS((1) E.Babb:Implementing a
Relational Database by Means of
Specialiyed Hardware, ACM Trans.Database
Syst.,Vol.4,No.1,PP.1-29,March 1979.(2)
E.Babb:Patent Application No.27093/74,
June 1974(Hashed Bit Arrays Store).)などの
システムで用いられている。
第１図、第２図、第３図により従来技術を説明
する。
する。
第１図は、従来のビツトアレイを用いる方式の
基本的な操作手順を示す。１，２はデータ群、５
は適切に定められたハツシユ関数を持つハツシン
グ装置、７はビツトアレイ、１０は選別されたデ
ータ群、１０１はデータ群１のデータ内容をハツ
シング装置５に入力してハツシングを行ない、ビ
ツトアレイ７のハツシング値を番地とするビツト
位置を▼１▼にする操作、２０１はデータ群２の
データ内容をハツシング装置５に入力してハツシ
ングを行ない、ビツトアレイ７のハツシング値を
番地とするビツト位置が▼１▼であるデータのみ
を選別する操作を示す。
基本的な操作手順を示す。１，２はデータ群、５
は適切に定められたハツシユ関数を持つハツシン
グ装置、７はビツトアレイ、１０は選別されたデ
ータ群、１０１はデータ群１のデータ内容をハツ
シング装置５に入力してハツシングを行ない、ビ
ツトアレイ７のハツシング値を番地とするビツト
位置を▼１▼にする操作、２０１はデータ群２の
データ内容をハツシング装置５に入力してハツシ
ングを行ない、ビツトアレイ７のハツシング値を
番地とするビツト位置が▼１▼であるデータのみ
を選別する操作を示す。
まず、ビツトアレイ７の全てのビツトを▼０▼
に初期設定する。次に、操作１０１によりビツト
アレイ７に▼１▼を設定した後に、操作２０１に
よりデータ群２のデータ内容をハツシングして、
ビツトアレイ７のハツシング値を番地とするビツ
ト位置が▼０▼であるデータについては不必要な
データとして除去し，▼１▼であるデータは必要
なデータとして選び出す（これを選別と称する）。
この第１図に示す方式では、２つのデータ群のう
ち一方のデータ群についてしか選別が行なわれな
いという欠点がある。
に初期設定する。次に、操作１０１によりビツト
アレイ７に▼１▼を設定した後に、操作２０１に
よりデータ群２のデータ内容をハツシングして、
ビツトアレイ７のハツシング値を番地とするビツ
ト位置が▼０▼であるデータについては不必要な
データとして除去し，▼１▼であるデータは必要
なデータとして選び出す（これを選別と称する）。
この第１図に示す方式では、２つのデータ群のう
ち一方のデータ群についてしか選別が行なわれな
いという欠点がある。
次に、複数個のデータ群についてデータ選別を
行なう場合を説明する。
行なう場合を説明する。
第２図に示す方式は、２つのデータ群の中から
相互にデータ内容が一致する可能性のあるデータ
を選別するものであり、１，２はデータ群、４，
５は同じハツシユ関数をもつハツシング装置、
７，８はビツトアレイ、１０，１１は選別された
データ群を示す。
相互にデータ内容が一致する可能性のあるデータ
を選別するものであり、１，２はデータ群、４，
５は同じハツシユ関数をもつハツシング装置、
７，８はビツトアレイ、１０，１１は選別された
データ群を示す。
まずビツトアレイの全てのビットを▼０▼に初
期設定する。
期設定する。
次に、データ群１をハツシング装置５に入力し
てハツシングを行ない、ビツトアレイ８のハツシ
ング値を番地とするビツト位置を▼１▼にセツト
し（操作１０１）、次に、データ群２をハツシン
グ装置４に入力してハツシングを行ない、ビツト
アレイ７のハツシング値を番地とするビツト位置
を▼１▼にセツトする（操作１０２）とともに、
ビツトアレイ８のハツシング値を番地とするビツ
ト位置が▼１▼であるデータのみを選別する（操
作２０１）、さらに、操作１０２ならびに操作２
０１の両方が終了した時点で、データ群１をハツ
シング装置４に入力してハツシングを行ない、ビ
ツトアレイ７のハツシング値を番地とするビツト
位置が▼１▼であるデータのみを選別する（操作
２０２）。
てハツシングを行ない、ビツトアレイ８のハツシ
ング値を番地とするビツト位置を▼１▼にセツト
し（操作１０１）、次に、データ群２をハツシン
グ装置４に入力してハツシングを行ない、ビツト
アレイ７のハツシング値を番地とするビツト位置
を▼１▼にセツトする（操作１０２）とともに、
ビツトアレイ８のハツシング値を番地とするビツ
ト位置が▼１▼であるデータのみを選別する（操
作２０１）、さらに、操作１０２ならびに操作２
０１の両方が終了した時点で、データ群１をハツ
シング装置４に入力してハツシングを行ない、ビ
ツトアレイ７のハツシング値を番地とするビツト
位置が▼１▼であるデータのみを選別する（操作
２０２）。
第３図は、第２図に示す方式におけるタイムチ
ヤートを示したものである。第３図は、データ群
１，２のデータの数を各々m1，m2（m1＜m2）と
し、また、 S1：操作１０１に要する処理時間 S2：操作１０２に要する処理時間 R1：操作２０２に要する処理時間 R2：操作２０１に要する処理時間 とした場合を示しており、この場合にはS1＜S2，
R1＜R2であり、また、max（R2、S2）はR2とS2
のどちらか大きい方の値を表わすものとすると、
処理時間（T1）は T1＝S1＋max（R2，S2）＋R1 となる。
ヤートを示したものである。第３図は、データ群
１，２のデータの数を各々m1，m2（m1＜m2）と
し、また、 S1：操作１０１に要する処理時間 S2：操作１０２に要する処理時間 R1：操作２０２に要する処理時間 R2：操作２０１に要する処理時間 とした場合を示しており、この場合にはS1＜S2，
R1＜R2であり、また、max（R2、S2）はR2とS2
のどちらか大きい方の値を表わすものとすると、
処理時間（T1）は T1＝S1＋max（R2，S2）＋R1 となる。
第２図に示すような方式では、第１図に示す方
式に比して２つのデータ群の両方についてデータ
の選別処理が行なわれるという利点があるが、第
３図で示したように、一般に、操作２０１により
選別されたデータ群１１が出力された後に、操作
２０２により選別されたデータ群１０が出力され
るので、第１図に示す方式に比べて処理時間が長
いという欠点があつた。また、データ群の結合処
理を行なう場合の前処理として２つのビツトアレ
イを用いる場合には、原理的に取扱えるデータ群
は２つのみである。従つて、３つ以上のｎ個のデ
ータ群について結合処理を行なう場合の方法とし
ては、まず２つのデータ群について選別処理、結
合処理を行ない、新たなデータ群を作成した後、
この新しいデータ群（中間データ群）と残りのデ
ータ群との間で再び選別処理、結合処理を繰り返
していくという方法を採らざるを得ない。しか
し、この方法では、中間データ群を生成する操作
が（ｎ−２）回必要であること、また、（ｎ−１）
回のデータ選別の操作を行なう必要があることに
より、処理時間が極めて大きくなるという欠点が
あつた。また、第２図に示すような従来方式で
は、第２図から明らかなように、対となつている
ハツシング装置をビツトアレイに入力するデータ
群は、例えば、操作１０１と次の操作２０１（も
う片方では、操作１０２と次の操作２０２）で、
異なつている。つまり、操作１０１から操作２０
１に移行する直前で、入力するデータ群を切り替
える必要があつた。
式に比して２つのデータ群の両方についてデータ
の選別処理が行なわれるという利点があるが、第
３図で示したように、一般に、操作２０１により
選別されたデータ群１１が出力された後に、操作
２０２により選別されたデータ群１０が出力され
るので、第１図に示す方式に比べて処理時間が長
いという欠点があつた。また、データ群の結合処
理を行なう場合の前処理として２つのビツトアレ
イを用いる場合には、原理的に取扱えるデータ群
は２つのみである。従つて、３つ以上のｎ個のデ
ータ群について結合処理を行なう場合の方法とし
ては、まず２つのデータ群について選別処理、結
合処理を行ない、新たなデータ群を作成した後、
この新しいデータ群（中間データ群）と残りのデ
ータ群との間で再び選別処理、結合処理を繰り返
していくという方法を採らざるを得ない。しか
し、この方法では、中間データ群を生成する操作
が（ｎ−２）回必要であること、また、（ｎ−１）
回のデータ選別の操作を行なう必要があることに
より、処理時間が極めて大きくなるという欠点が
あつた。また、第２図に示すような従来方式で
は、第２図から明らかなように、対となつている
ハツシング装置をビツトアレイに入力するデータ
群は、例えば、操作１０１と次の操作２０１（も
う片方では、操作１０２と次の操作２０２）で、
異なつている。つまり、操作１０１から操作２０
１に移行する直前で、入力するデータ群を切り替
える必要があつた。
このデータ群の切り替え制御に関しては、ハツ
シング装置に入力するためのデータパスを複数用
意する必要があること、また、データパスを介し
て、データ群とハツシング装置とを結び付けるた
めの切り替え制御回路が必要であり、切り替え制
御が複雑となり、構成上複雑であるという欠点が
あつた。
シング装置に入力するためのデータパスを複数用
意する必要があること、また、データパスを介し
て、データ群とハツシング装置とを結び付けるた
めの切り替え制御回路が必要であり、切り替え制
御が複雑となり、構成上複雑であるという欠点が
あつた。
３ 発明の目的
本発明は、上述した従来方式の欠点を除去する
ため、複数個（ｎ）のデータ群について、ハツシ
ング装置とビツトアレイの組をｎ台と全てのビツ
トアレイ間のＡＮＤをとるＡＮＤ装置を１台備える
ことにより、全てのデータ群についてデータ内容
が一致する可能性のあるデータを一括して選別す
ることを特徴とし、その目的は、選別処理時間を
短縮することにある。
ため、複数個（ｎ）のデータ群について、ハツシ
ング装置とビツトアレイの組をｎ台と全てのビツ
トアレイ間のＡＮＤをとるＡＮＤ装置を１台備える
ことにより、全てのデータ群についてデータ内容
が一致する可能性のあるデータを一括して選別す
ることを特徴とし、その目的は、選別処理時間を
短縮することにある。
以下、本発明は、実施例をもつて詳細に説明す
る。
る。
４ 発明構成および作用の説明
第４図は、本発明実施例方式における操作の手
順を説明するための図である。ここでは説明を簡
単にするために、データ群の個数を３つとした場
合で説明する。同図において、１，２，３はデー
タ群、４，５，６は同じハツシユ関数をもつハツ
シング装置、７，８，９はビツトアレイ、１３は
ＡＮＤ装置、１０，１１，１２は選別されたデー
タ群を示す。
順を説明するための図である。ここでは説明を簡
単にするために、データ群の個数を３つとした場
合で説明する。同図において、１，２，３はデー
タ群、４，５，６は同じハツシユ関数をもつハツ
シング装置、７，８，９はビツトアレイ、１３は
ＡＮＤ装置、１０，１１，１２は選別されたデー
タ群を示す。
まず、ビツトアレイの全てのビツトを‘０’に初
期設定する。次に、１つのデータ群には、対とな
ている１個のハツシング装置と１個のビツトアレ
イとを割当て、データ群１をハツシング装置４に
入力してハツシングを行ない、ビツトアレイ７の
ハツシング値を番地とするビツト位置に▼１▼を
セツトする（操作３０１）とともに、データ群２
をハツシング装置５に入力してハツシングを行な
い、ビツトアレイ８のハツシング値を番地とする
ビツト装置に▼１▼をセツトし（操作３０２）、
更にデータ群３をハツシング装置６に入力してハ
ツシングを行ない、ビツトアレイ９のハツシング
値を番地とするビツト位置に▼１▼をセツトする
（操作３０３）、これら全てのデータ群のセツト操
作が終了した時点で、ＡＮＤ装置１３にビツトア
レイ７，８，９を入力してＡＮＤをとり、ＡＮＤを
とつた結果をビツトアレイ７，８，９に転送す
る。
期設定する。次に、１つのデータ群には、対とな
ている１個のハツシング装置と１個のビツトアレ
イとを割当て、データ群１をハツシング装置４に
入力してハツシングを行ない、ビツトアレイ７の
ハツシング値を番地とするビツト位置に▼１▼を
セツトする（操作３０１）とともに、データ群２
をハツシング装置５に入力してハツシングを行な
い、ビツトアレイ８のハツシング値を番地とする
ビツト装置に▼１▼をセツトし（操作３０２）、
更にデータ群３をハツシング装置６に入力してハ
ツシングを行ない、ビツトアレイ９のハツシング
値を番地とするビツト位置に▼１▼をセツトする
（操作３０３）、これら全てのデータ群のセツト操
作が終了した時点で、ＡＮＤ装置１３にビツトア
レイ７，８，９を入力してＡＮＤをとり、ＡＮＤを
とつた結果をビツトアレイ７，８，９に転送す
る。
その様子を第５図で説明する。全てのデータ群
のセツト操作が終了した時点のビツトアレイ７，
８，９の内容を各々２０，２１，２２とする。
ＡＮＤ装置１３は、ビツトアレイの内容２０，２
１，２２を入力し、各ビツト位置ごとにＡＮＤを
とる。例えば、第５図の例では、 ビツトアレイ７，８，９の各ビツト位置１につ
いての内容が０、０、１であるから、そのＡＮＤ
をとつた結果は０、 同様に、ビツト位置１＋１についての内容が
０、１、０であるから、そのＡＮＤをとつた結果
は０、 同様に、ビツト位置１＋２についての内容が
１、１、１であるから、そのＡＮＤをとつた結果
は１、 というように、全てのビツト位置ごとにＡＮＤを
とつた結果２３をビツトアレイ７，８，９の各ビ
ツト位置ごとに更新し直す。これにより、ビツト
アレイ７，８，９の更新後の内容は全て同じとな
り、第５図の２４，２５，２６に示されるように
なる。
のセツト操作が終了した時点のビツトアレイ７，
８，９の内容を各々２０，２１，２２とする。
ＡＮＤ装置１３は、ビツトアレイの内容２０，２
１，２２を入力し、各ビツト位置ごとにＡＮＤを
とる。例えば、第５図の例では、 ビツトアレイ７，８，９の各ビツト位置１につ
いての内容が０、０、１であるから、そのＡＮＤ
をとつた結果は０、 同様に、ビツト位置１＋１についての内容が
０、１、０であるから、そのＡＮＤをとつた結果
は０、 同様に、ビツト位置１＋２についての内容が
１、１、１であるから、そのＡＮＤをとつた結果
は１、 というように、全てのビツト位置ごとにＡＮＤを
とつた結果２３をビツトアレイ７，８，９の各ビ
ツト位置ごとに更新し直す。これにより、ビツト
アレイ７，８，９の更新後の内容は全て同じとな
り、第５図の２４，２５，２６に示されるように
なる。
ここで、データ群１をハツシング装置４に入力
してハツシングを行ない、ビツトアレイ７のハツ
シング値を番地とするビツト位置が▼１▼である
データのみを選別する（操作４０１）とともに、
データ群２をハツシング装置５に入力してハツシ
ングを行ない、ビツトアレイ８のハツシング値を
番地とするビツト位置が▼１▼であるデータのみ
を選別し（操作４０２）、更にデータ群３をハツ
シング装置６に入力してハツシングを行ない、ビ
ツトアレイ９のハシング値を番地とするビツト位
置が▼１▼であるデータのみを選別する（操作４
０３）。
してハツシングを行ない、ビツトアレイ７のハツ
シング値を番地とするビツト位置が▼１▼である
データのみを選別する（操作４０１）とともに、
データ群２をハツシング装置５に入力してハツシ
ングを行ない、ビツトアレイ８のハツシング値を
番地とするビツト位置が▼１▼であるデータのみ
を選別し（操作４０２）、更にデータ群３をハツ
シング装置６に入力してハツシングを行ない、ビ
ツトアレイ９のハシング値を番地とするビツト位
置が▼１▼であるデータのみを選別する（操作４
０３）。
以上述べたように、まずデータ群１，２，３の
セツト操作を同時に行なうことにより、各々のビ
ツトアレイ７，８，９をセツトし、次にビツトア
レイ７，８，９の各ビツト位置ごとにＡＮＤをと
り、その結果により、各々ビツトアレイ７，８，
９の各ビツト位置ごとに更新し直し、次に、各々
のデータ群１，２，３のデータ内容をハツシング
し、更新後のビツトアレイ７，８，９を参照しハ
ツシング値を番地とするビツト位置の内容が▼１
▼であるデータのみを選別する操作、すなわち
ＲＥＦＥＲ操作を同時に行なうことにより、全ての
データ群についてデータ内容が一致する可能性の
あるデータを一括して選別することができる。
セツト操作を同時に行なうことにより、各々のビ
ツトアレイ７，８，９をセツトし、次にビツトア
レイ７，８，９の各ビツト位置ごとにＡＮＤをと
り、その結果により、各々ビツトアレイ７，８，
９の各ビツト位置ごとに更新し直し、次に、各々
のデータ群１，２，３のデータ内容をハツシング
し、更新後のビツトアレイ７，８，９を参照しハ
ツシング値を番地とするビツト位置の内容が▼１
▼であるデータのみを選別する操作、すなわち
ＲＥＦＥＲ操作を同時に行なうことにより、全ての
データ群についてデータ内容が一致する可能性の
あるデータを一括して選別することができる。
第６図は、第４図に示す実施例方式におけるタ
イムチヤートを示したものである。第６図は、デ
ータ群１，２，３のデータの数をm1，m2，m3
（m1＜m2＜m3）とし、また、 Si：操作３０ｉに要する処理時間（ｉ＝１、２、
３） Rj：操作４０ｊに要する処理時間（ｊ＝１、２
３） Ｑ：全てのビツトアレイ間のＡＮＤをとつて、結
果を全てのビツトアレイに転送するために要す
る処理時間 とした場合を示しており、 その処理時間（T3）は、 T3＝Ｑ＋max｛S1，S2，S3｝＋max｛R1，R2，R3｝ となる。ここで、ＡＮＤ装置により、全てのビツ
トアレイ間のＡＮＤをとつて、結果を全てのビツ
トアレイに転送するための処理時間Ｑがオーバヘ
ツドとなる。しかしながら、このＡＮＤ装置は単
純なＡＮＤ回路の群であるから、LSI化により高
速化してこのオーバーヘツドを短縮することが期
待できる。このため、従来のハツシング装置とビ
ツトアレイを２台備えたものでｎ個のデータ群全
てについて選別するような方式に比べて、中間デ
ータ群生成の採作が不要であることにもとづい
て、処理時間を短縮することが期待できる。
イムチヤートを示したものである。第６図は、デ
ータ群１，２，３のデータの数をm1，m2，m3
（m1＜m2＜m3）とし、また、 Si：操作３０ｉに要する処理時間（ｉ＝１、２、
３） Rj：操作４０ｊに要する処理時間（ｊ＝１、２
３） Ｑ：全てのビツトアレイ間のＡＮＤをとつて、結
果を全てのビツトアレイに転送するために要す
る処理時間 とした場合を示しており、 その処理時間（T3）は、 T3＝Ｑ＋max｛S1，S2，S3｝＋max｛R1，R2，R3｝ となる。ここで、ＡＮＤ装置により、全てのビツ
トアレイ間のＡＮＤをとつて、結果を全てのビツ
トアレイに転送するための処理時間Ｑがオーバヘ
ツドとなる。しかしながら、このＡＮＤ装置は単
純なＡＮＤ回路の群であるから、LSI化により高
速化してこのオーバーヘツドを短縮することが期
待できる。このため、従来のハツシング装置とビ
ツトアレイを２台備えたものでｎ個のデータ群全
てについて選別するような方式に比べて、中間デ
ータ群生成の採作が不要であることにもとづい
て、処理時間を短縮することが期待できる。
第７図は、第４図に示す実施例方式を実現する
回路の１例を示す。第７図において、４，５，６
はハツシング装置、７，８，９はビツトアレイ、
１３はＡＮＤ装置、６０，７０，８０は入力端子、
６１，７１，８１はデータ取出し回路、６２，７
２，８２はハツシング回路、６３，７３，８３は
バツフア、６７，７７，８７は転送回路、６４，
７４，８４は出力端子、６５，７５，８５はビツ
トアレイのハツシング値を番地とするビツト位置
に▼｜▼をセツトする操作（ＳＥＴ操作）を指示
するＳＥＴ信号、６６，７６，８６はビツトアレ
イのハツシング値を番地とするビツト位置が▼｜
▼であるデータのみを選別する操作（ＲＥＦＥＲ操
作）を指示するＰＥＦＥＲ信号、６７，７７，８７
は転送回路、９０は全てのビツトアレイ間の
ＡＮＤをとり、ＡＮＤをとつた結果を全てのビツト
アレイに転送するＡＮＤ装置への起動信号である
（なお、SET信号、REFER信号、ＡＮＤ装置への
起動信号を発する制御回路については図から省略
している。） まず、ビツトアレイ７，８，９の全てのビツト
を▼０▼に初期設定する。データ群１のデータは
入力端子６０に、データ群２のデータは入力端子
７０に、データ群３のデータは入力端子８０に入
力される。データ取出し回路６１，７１，８１
は、各々のＳＥＴ信号６５，７５，８５あるいは
各々のＲＥＦＥＲ信号６６，７６，８６の発生と同
期して起動され、データをバツフア６３に転送す
る。
回路の１例を示す。第７図において、４，５，６
はハツシング装置、７，８，９はビツトアレイ、
１３はＡＮＤ装置、６０，７０，８０は入力端子、
６１，７１，８１はデータ取出し回路、６２，７
２，８２はハツシング回路、６３，７３，８３は
バツフア、６７，７７，８７は転送回路、６４，
７４，８４は出力端子、６５，７５，８５はビツ
トアレイのハツシング値を番地とするビツト位置
に▼｜▼をセツトする操作（ＳＥＴ操作）を指示
するＳＥＴ信号、６６，７６，８６はビツトアレ
イのハツシング値を番地とするビツト位置が▼｜
▼であるデータのみを選別する操作（ＲＥＦＥＲ操
作）を指示するＰＥＦＥＲ信号、６７，７７，８７
は転送回路、９０は全てのビツトアレイ間の
ＡＮＤをとり、ＡＮＤをとつた結果を全てのビツト
アレイに転送するＡＮＤ装置への起動信号である
（なお、SET信号、REFER信号、ＡＮＤ装置への
起動信号を発する制御回路については図から省略
している。） まず、ビツトアレイ７，８，９の全てのビツト
を▼０▼に初期設定する。データ群１のデータは
入力端子６０に、データ群２のデータは入力端子
７０に、データ群３のデータは入力端子８０に入
力される。データ取出し回路６１，７１，８１
は、各々のＳＥＴ信号６５，７５，８５あるいは
各々のＲＥＦＥＲ信号６６，７６，８６の発生と同
期して起動され、データをバツフア６３に転送す
る。
次に、各々のハツシング装置４，５，６は、
各々のハツシング回路６２，７２，８２と各々の
バツフア６３，７３，８３からなつており、例え
ば、ハツシング回路６２がＳＥＴ信号６５を検出
した時は、バツフア６３に格納されているデータ
の内容をハツシングして、ビツトアレイ７のハツ
シング値を番地とするビツト位置に▼１▼をセツ
トし（ＳＥＴ操作）、順にデータのＳＥＴ操作を繰り
返して行なうために、次のデータをバツフア６３
に転送することを要求する信号をデータ取出し回
路６１に発する。また、ハツシング回路６２が
ＲＥＦＥＲ信号６６を検出した時は、バツフア６３
に格納されているデータの内容をハツシングし
て、ビツトアレイ７のハツシング値を番地とする
ビツト位置が▼１▼であれば、転送回路６７に起
動信号を発し、転送回路６７はこの起動信号によ
りバツフア６３のデータ内容を出力端子６４に出
力するとともに、次のデータをバツフア６３に転
送することを要求する信号をデータ取出し回路６
１に発する。また、該ビット位置が▼１▼でなけ
れば、データ取出し回路６１に次のデータがバツ
フア６３に転送することを要求する信号を発する
（ＲＥＦＥＲ操作）。
各々のハツシング回路６２，７２，８２と各々の
バツフア６３，７３，８３からなつており、例え
ば、ハツシング回路６２がＳＥＴ信号６５を検出
した時は、バツフア６３に格納されているデータ
の内容をハツシングして、ビツトアレイ７のハツ
シング値を番地とするビツト位置に▼１▼をセツ
トし（ＳＥＴ操作）、順にデータのＳＥＴ操作を繰り
返して行なうために、次のデータをバツフア６３
に転送することを要求する信号をデータ取出し回
路６１に発する。また、ハツシング回路６２が
ＲＥＦＥＲ信号６６を検出した時は、バツフア６３
に格納されているデータの内容をハツシングし
て、ビツトアレイ７のハツシング値を番地とする
ビツト位置が▼１▼であれば、転送回路６７に起
動信号を発し、転送回路６７はこの起動信号によ
りバツフア６３のデータ内容を出力端子６４に出
力するとともに、次のデータをバツフア６３に転
送することを要求する信号をデータ取出し回路６
１に発する。また、該ビット位置が▼１▼でなけ
れば、データ取出し回路６１に次のデータがバツ
フア６３に転送することを要求する信号を発する
（ＲＥＦＥＲ操作）。
ハツシング装置５，６ならびにデータ取出し回
路７１，８１も上記と同様な動作を行ない、各々
出力端子７４，８４に選別されたデータを送出す
る。
路７１，８１も上記と同様な動作を行ない、各々
出力端子７４，８４に選別されたデータを送出す
る。
全てのデータ群についてＳＥＴ操作が終了した
時点で、ＡＮＤ装置１３の起動信号を発する。
ＡＮＤ装置１３はビツトアレイ７，８，９を入力
してＡＮＤをとり、ＡＮＤをとつた結果をビツトア
レイ７，８，９に転送し、その内容を更新する。
時点で、ＡＮＤ装置１３の起動信号を発する。
ＡＮＤ装置１３はビツトアレイ７，８，９を入力
してＡＮＤをとり、ＡＮＤをとつた結果をビツトア
レイ７，８，９に転送し、その内容を更新する。
以上述べたように、まずデータ群１，２，３の
ＳＥＴ操作を同時に行なうことにより、各々のビ
ツトアレイ７，８，９をセツトし、次にビツトア
レイ７，８，９のＡＮＤをとつた結果のビツトア
レイ７，８，９を用いて、各々のデータ群１，
２，３のＲＥＦＥＲ操作を同時に行なうことによ
り、全てのデータ群についてデータ内容が一致す
る可能性のあるデータを一括して選別することが
できる。
ＳＥＴ操作を同時に行なうことにより、各々のビ
ツトアレイ７，８，９をセツトし、次にビツトア
レイ７，８，９のＡＮＤをとつた結果のビツトア
レイ７，８，９を用いて、各々のデータ群１，
２，３のＲＥＦＥＲ操作を同時に行なうことによ
り、全てのデータ群についてデータ内容が一致す
る可能性のあるデータを一括して選別することが
できる。
５ 効果の説明
以上説明したように、本発明は複数個（ｎ）の
データ群について、ハツシング装置とビツトアレ
イの組をｎ台と１台のＡＮＤ装置を備えることに
より、同時に全てのデータ群でデータ内容の一致
の可能性のあるデータを選別するものであるか
ら、従来のハツシング装置２台とビツトアレイ２
個備えたものでｎ個のデータ群全てについて選別
するような方式に比べて、選別処理に要する時間
を短縮できるという利点がある。従来技術である
第２図と本願発明の第４図を対比すれば明かなよ
うに、各ハツシング装置へ入力するためのデータ
パスは１本であり、データ群の切り替え制御が不
要であること、さらに、ＡＮＤ装置そのものも構
成が単純であり、ハードウエア構成が簡素化で
き、LSI化が容易になり、LSI化により高速化を
図ることが期待できるという利点がある。
データ群について、ハツシング装置とビツトアレ
イの組をｎ台と１台のＡＮＤ装置を備えることに
より、同時に全てのデータ群でデータ内容の一致
の可能性のあるデータを選別するものであるか
ら、従来のハツシング装置２台とビツトアレイ２
個備えたものでｎ個のデータ群全てについて選別
するような方式に比べて、選別処理に要する時間
を短縮できるという利点がある。従来技術である
第２図と本願発明の第４図を対比すれば明かなよ
うに、各ハツシング装置へ入力するためのデータ
パスは１本であり、データ群の切り替え制御が不
要であること、さらに、ＡＮＤ装置そのものも構
成が単純であり、ハードウエア構成が簡素化で
き、LSI化が容易になり、LSI化により高速化を
図ることが期待できるという利点がある。
第１図、第２図は従来のデータ選別方式の操作
手順の説明図、第３図は第２図に示す操作におけ
るタイムチヤート、第４図は本発明におけるデー
タ選別方式の操作手順の説明図、第５図はＡＮＤ
装置の機能説明図、第６図は第４図に示す操作に
おけるタイムチヤート、第７図は本発明実施例の
回路図である。 図中、１，２，３はデータ群、４，５，６はハ
ツシング装置、７，８，９はビツトアレイ、１
０，１１，１２は選別されたデータ群、３０１，
３０２，３０３はデータ群のデータ内容のハツシ
ング値を番地とするビツトアレイのビツト位置を
▼１▼にセツトする操作、４０１，４０２，４０
３はデータ群のデータ内容のハツシング値を番地
とするビツトアレイのビツト位置が▼１▼である
データのみを選別する操作、１３は全てのビツト
アレイを入力してＡＮＤをとり、ＡＮＤをとつた結
果により全てのビツトアレイを更新するＡＮＤ装
置を表わす。
手順の説明図、第３図は第２図に示す操作におけ
るタイムチヤート、第４図は本発明におけるデー
タ選別方式の操作手順の説明図、第５図はＡＮＤ
装置の機能説明図、第６図は第４図に示す操作に
おけるタイムチヤート、第７図は本発明実施例の
回路図である。 図中、１，２，３はデータ群、４，５，６はハ
ツシング装置、７，８，９はビツトアレイ、１
０，１１，１２は選別されたデータ群、３０１，
３０２，３０３はデータ群のデータ内容のハツシ
ング値を番地とするビツトアレイのビツト位置を
▼１▼にセツトする操作、４０１，４０２，４０
３はデータ群のデータ内容のハツシング値を番地
とするビツトアレイのビツト位置が▼１▼である
データのみを選別する操作、１３は全てのビツト
アレイを入力してＡＮＤをとり、ＡＮＤをとつた結
果により全てのビツトアレイを更新するＡＮＤ装
置を表わす。
Claims (1)
- １ データ群が複数のｎ個（ｎ≧３）ある場合
で、データ内容が全てのデータ群について相互に
一致する可能性のあるデータを選別する方式にお
いて、データをハツシングするハツシング装置と
ビツトアレイとの組をデータ群に等しい数のｎ個
だけを備え、１つのデータ群に１個のハツシング
装置と１個のビツトアレイとを割当て、ｎ個のデ
ータ群を同時にハツシングしてビツトアレイを設
定し、次にＡＮＤ装置により全てのビツトアレイ
間のＡＮＤをとり、その結果を全てのビツトアレ
イに同時に転送して更新し、続いて、前記ｎ個の
データ群を前記ハツシングの際に用いたハツシン
グ装置と同じハツシング装置に同時に入力してハ
ツシングし、各々のビツトアレイを参照し、全て
のデータ群について相互に一致する可能性のある
データを選別することを特徴とするデータ選別方
式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58005709A JPS59132041A (ja) | 1983-01-17 | 1983-01-17 | デ−タ選別方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58005709A JPS59132041A (ja) | 1983-01-17 | 1983-01-17 | デ−タ選別方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS59132041A JPS59132041A (ja) | 1984-07-30 |
| JPH0419570B2 true JPH0419570B2 (ja) | 1992-03-30 |
Family
ID=11618640
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58005709A Granted JPS59132041A (ja) | 1983-01-17 | 1983-01-17 | デ−タ選別方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS59132041A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4903194A (en) * | 1987-11-12 | 1990-02-20 | International Business Machines Corporation | Storage addressing error detection circuitry |
-
1983
- 1983-01-17 JP JP58005709A patent/JPS59132041A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS59132041A (ja) | 1984-07-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| DE3533847C2 (de) | Weglenkendes Paketvermittlungs-Koppelfeld mit stufeninterner Paketübertragung | |
| EP0138952B1 (en) | A self-routing switching network | |
| CA1240022A (en) | Self-routing packets with stage address identifying fields | |
| US5111453A (en) | Apparatus and method for recognizing addresses of information packets | |
| US7023797B2 (en) | Flexible aggregation of output links | |
| US5926626A (en) | Network bridge using only hardware to process media access control (MAC) packet-switching operations | |
| JPH11266273A (ja) | スイッチ構造及びそのアップグレード方法 | |
| JPH06203001A (ja) | 電子メッセージ通信の経路選択方法 | |
| CA2011934A1 (en) | Method and apparatus for source routing bridging | |
| JP3520709B2 (ja) | ネットワークアドレス検索方式 | |
| JP2003224581A (ja) | 最長一致検索回路および方法およびプログラムおよび記録媒体 | |
| US5648957A (en) | Distributor employing controlled switching elements | |
| EP0520116A1 (en) | Method and apparatus for performing pattern search functions | |
| US20100098070A1 (en) | Multistage switch control circuit | |
| JP3199914B2 (ja) | フレーム中継制御方法、及びその装置 | |
| JP2001144801A (ja) | ヘッダ変換装置およびフレーム転送装置 | |
| US6769005B1 (en) | Method and apparatus for priority resolution | |
| EP0186595A2 (en) | Routing technique | |
| JPS59132041A (ja) | デ−タ選別方式 | |
| JPS59132042A (ja) | デ−タ選別方式 | |
| JP3680446B2 (ja) | パイプライン制御装置およびデータ処理方法 | |
| JPH0460768A (ja) | データ処理装置 | |
| JP2557873B2 (ja) | 自己ル−チング通話路 | |
| JPH0771353B2 (ja) | スイツチング回路網の制御方法 | |
| JPS62154139A (ja) | デ−タ選別装置 |