(57)【特許請求の範囲】
【請求項１】
高速データストリームに含まれる複雑なパターンの認識と比較を行い、特に、構造化または非構造化データベースに記憶されているデータの検索及び取出しを行う検索エンジンで使用される処理回路（Ｐ１）で、処理回路（Ｐ１）がこれら処理回路のネットワークのノードを形成する処理回路であって、該処理回路（Ｐ１）は、処理回路（Ｐ１）のそれぞれ構成及び操作パラメータであるデータの入力及び出力のインターフェースであって、構成パラメータは、インターフェースの無指定または専用入力を介して処理タスクについて処理回路（Ｐ１）に一度だけ与えられ、操作データは特定の処理タスクの実行により処理され、それぞれ、インターフェースの指定された入力及び出力を介して処理回路（Ｐ１）へ連続的に入出力されるインターフェースと、比較器装置（ＣＯＭ）の形式をした少なくとも１つのカーネルプロセッサ（Ｐ０）であって、比較器装置（ＣＯＭ）は２つのデータワードを比較するように適合された少なくとも１つのカーネルプロセッサと、比較器装置に接続される論理装置（Ｅ）であって、論理装置は、インターフェースの入力（順次データ入力、順次文書入力、順次フリップフロップ入力、直前の処理回路からの順次結果入力、後続の処理回路からの順次結果入力、平行データ入力、平行文書入力、平行フリップフロップ入力、直前の処理回路に関する平行結果入力、及び後続処理回路に関する平行結果入力）とインターフェースの出力（選択されたデータ値の出力、選択された文書値の出力、選択されたフリップフロップ値の出力、直前の処理回路への選択された結果の出力と選択された文書値の出力と、選択されたフリップフロップ値の出力と、直前の処理回路への選択された結果の出力と、後続の処理回路への選択された結果の出力）とに接続されたマルチプレクサ（ＭＵＸ１）と、第１のＤフリップフロップ（２）と、肯定２進値を特定の時間単位を使用して遅延するように適合された遅延装置（ＬＡＴ）と、第２のＤフリップフロップ（４）と、比較器装置（ＣＯＭ）内の比較操作を監視及び制御するように適合されたシーケンスコントロール装置（ＳＣ）と、他の処理回路または他の結果セレクタからの２つの結果値を結合するように適合された結果セレクタとを含む論理装置とを備え、比較器装置（ＣＯＭ）はマルチプレクサ（ＭＵＸ１）の選択データ値の出力とインターフェースのデータ出力とに接続され、さらに、結果出力を第１のＡＮＤゲート（１）に接続され同等装置を第２のＡＮＤゲート（３）に接続され、第１のＤフリップフロップはマルチプレクサ（ＭＵＸ１）の選択文書値の出力に接続され、リセットライン（５）を介してリセット出力を第１のＡＮＤゲート（１）の入力と、第２のＡＮＤゲート（３）の入力と、遅延装置（ＬＡＴ）の入力とにそれぞれ接続され、さらに、インターフェースの文書入力と接続され、第２のＡＮＤゲート（３）はインターフェースの同等出力を出力し、遅延装置（ＬＡＴ）は第１のＡＮＤゲート（１）の出力とシーケンスコントロール装置（ＳＣ）の結果入力とに接続され、第２のＤフリップフロップ（４）は第１のＤフリップフロップ（２）のリセット出力及びシーケンスコントロール装置（ＳＣ）のフリップフロップ出力とフリップフロップ入力のそれぞれ、さらにインターフェースのフリップフロップ出力とに接続され、シーケンスコントロール装置（ＳＣ）はマルチプレクサ（ＭＵＸ１）の直前の処理回路からの選択されたフリップフロップ値の出力と選択された結果の出力及び直前の処理回路の結果入力とインターフェースの結果出力とに接続され、結果セレクタ（ＲＳ）はインターフェースの第１の結果入力と、第１の文書入力と、第１の同等入力と、第２の結果入力と、第２の文書入力と、第２の同等入力とにそれぞれ接続され、インターフェースの結果出力と、文書出力と、同等出力とにそれぞれ接続されることを特徴とする処理回路。
【請求項２】
請求項１に記載の処理回路（Ｐ１）であって、
インターフェースは、以下の表に従って構成パラメータの入力と操作パラメータの入力及び出力により定義され、表の第１の列はパラメータの名称を示し、第２の列はパラメータタイプが操作か構成かを示し、第３の列はパラメータが入力または出力パラメータかを示し、第４の列はビット単位の入力または出力幅を示し、第５の列はそのパラメータの詳細な定義を示すことを特徴とする処理回路。
0003588049.tif 000050
0003588049.tif 000051
【請求項３】請求項１に記載の処理装置（Ｐ１）であって、
比較器装置（ＣＯＭ）は、データワードｘの形式の入力データを各場合に含みデータ入力とデータ出力にそれぞれ接続されている第１のレジスタ（６）と、第１レジスタ（６）に含まれるデータワードｘと比較されるデータワードａが含まれた第２のレジスタ（７）と、比較操作を実行するための１つまたは複数の論理ゲートおよびレジスタ（６，７）と接続されたマルチプレクサ（ＭＵＸ２）とを備え、マルチプレクサ（ＭＵＸ２）の出力が該比較器装置の結果出力を構成することを特徴とする処理装置。
【請求項４】
請求項３に記載の処理回路（Ｐ１）であって、
比較器装置（ＣＯＭ）のインターフェースの定義は、以下の表による構成パラメータの入力及び操作パラメータの入力と出力とで定義され、表の第１の列はパラメータの名称を示し、第２の列はパラメータタイプを操作または構成とそれぞれ示し、第３の列はパラメータを入力または出力パラメータとしてそれぞれ示し、第４の列は入力または出力幅をビット長で示し、第５の列はそのパラメータの詳細な定義を示すことを特徴とする処理回路。
0003588049.tif 000052
【請求項５】請求項４に記載の処理回路（Ｐ１）であって、
比較操作は≦、≧、≠、及び＝の操作のいずれかで、≦の場合は２進０、≧の場合は２進１、≠の場合は２進２、または＝の場合は２進３として入力される構成パラメータで与えられることを特徴とする処理回路。
【請求項６】
請求項１に記載の処理回路（Ｐ１）であって、
遅延装置（ＬＡＴ）は、それぞれ、第１の入力を介して第２のＡＮＤゲート（３）の出力に接続され第２の入力を介してリセットライン（５）に接続されるカウンタ（８）で、該カウンタは構成遅延パラメータを含む遅延レジスタ（９）に接続され、遅延装置の結果出力である出力を出力するカウンタ（８）を備えることを特徴とする処理回路。
【請求項７】
請求項６に記載の処理回路（Ｐ１）であって、遅延装置（ＬＡＴ）のインターフェースは、以下の表による構成遅延パラメータの入力及び操作パラメータの入力と出力とで定義され、表の第１の列はパラメータの名称を示し、第２の列はパラメータタイプを操作または構成とそれぞれ示し、第３の列はパラメータを入力または出力パラメータとしてそれぞれ示し、第４の列は入力または出力幅をビット長で示し、第５の列はそのパラメータの詳細な定義を示す。
0003588049.tif 000053
【請求項８】請求項７に記載の処理回路（Ｐ１）であって、
Ｌ＝０は遅延なしを示し、Ｌ＝ｔは遅延ｔ時間単位を示し、Ｌ＝ｔ＝２ｗ−１は不定遅延を示すことを特徴とする処理回路。
【請求項９】
請求項１に記載の処理回路（Ｐ１）であって、
シーケンスコントロール装置（ＳＣ）は、直前の処理回路の結果入力と遅延装置（ＬＡＴ）の結果出力とに接続された第１のＡＮＤゲート（１０）と、第１のＡＮＤゲート（１０）の出力と第２のＤフリップフロップ（４）の出力とにそれぞれ接続された第１のＯＲゲート（１１）と、遅延装置（ＬＡＴ）の結果出力と後続の処理回路の結果入力に接続された第２のＡＮＤゲート（１２）と、後続の処理回路の結果入力と第２のＤフリップフロップ（４）の出力とに接続された第２のＯＲゲート（１３）と、遅延装置（ＬＡＴ）の結果出力とＯＲゲート（１３）の出力とに接続された第３のＡＮＤゲート（１４）と、遅延装置（ＬＡＴ）の結果出力と、ＡＮＤゲート（１０，１２，１４）と第１のＯＲゲート（１１）のそれぞれの出力と、直前の処理回路の結果入力と、後続の処理回路のフリップフロップ出力とにそれぞれ接続されたマルチプレクサ（ＭＵＸ３）とを備え、シーケンスコントロール装置（ＳＣ）が処理回路（Ｐ１）の結果出力を形成することを特徴とする処理回路。
【請求項１０】
請求項９に記載の処理回路（Ｐ１）であって、
シーケンスコントロール装置（ＳＣ）のインターフェースは、以下の表による構成パラメータの入力及び操作パラメータの入力と出力とで定義され、表の第１の列はパラメータの名称を示し、第２の列はパラメータタイプを操作または構成としてそれぞれ示し、第３の列はパラメータを入力または出力パラメータとしてそれぞれ示し、第４の列は入力または出力幅をビット長で示し、第５の列はそのパラメータの詳細な定義を示すことを特徴とする処理回路。
0003588049.tif 000054
【請求項１１】請求項１０に記載の処理回路（Ｐ１）であって、
シーケンスコントロール装置（ＳＣ）は、
−比較結果を出力する直前または後続の装置に従って、比較器装置（ＣＯＭ）が比較結果を出力できるようにする
−パターンの一部が欠落しているパターンと比較する
−パターンの一部が反復しているパターンと比較する
の１つまたは複数のシーケンスコントロール操作を実現することを特徴とする処理回路。
【請求項１２】
請求項１１に記載の処理回路（Ｐ１）であって、
シーケンスコントロール操作が実行される場合は構成パラメータＳを２進１として入力し、前方シーケンスコントロール及び後方シーケンスコントロールをそれぞれ実行する場合は構成パラメータＤを２進０または２進１として入力し、欠落部分または反復部分があるパターンを比較の対象として許容する場合は構成パラメータＭＭを２進１として入力することを特徴とする処理回路。
【請求項１３】
請求項１に記載の処理回路（Ｐ１）であって、
結果セレクタ（ＲＳ）は、第１の同等入力と第２の同等入力とに接続された第１のＡＮＤゲート（１５）と、第１の結果入力と第２の結果入力とに接続された第２のＡＮＤゲート（１６）と、第１の結果入力と第２の同等入力とに接続された第３のＡＮＤゲート（１７）と、第２の同等入力に接続されたＮＯＴゲート（１８）と、第２の結果入力とＮＯＴゲート（１８）の出力とに接続された第４のＡＮＤゲート（１９）と、第１及び第２の同等入力にそれぞれ接続された第１のＯＲゲート（２０）と、第１及び第２の同等入力にそれぞれ接続された第２のＯＲゲート（２１）と、第３及び第４のＡＮＤゲート（１７；１９）の出力にそれぞれ接続された第３のＯＲゲート（２２）と、第１の結果入力と、第２の結果入力と、第１の同等入力と、第２の同等入力と、第１及び第２のＡＮＤゲート（１５；１６）それぞれからの出力と、第１、第２、及び第３のＯＲゲート（２０；２１；２２）それぞれからの出力とに接続されたマルチプレクサ（ＭＵＸ４）と、第１及び第２の文書入力とインターフェースの文書出力とにそれぞれ接続された第５のＡＮＤゲート（２３）と、第５のＡＮＤゲート（２３）と、マルチプレクサ（ＭＵＸ４）の第１の出力と、インターフェースの結果出力とにそれぞれ接続された第６のＡＮＤゲート（２４）と、第５のＡＮＤゲート（２３）と、マルチプレクサ（ＭＵＸ４）の第２の出力と、インターフェースの同等出力とにそれぞれ接続された第７のＡＮＤゲート（２５）とを備えることを特徴とするプロセッサ回路。
【請求項１４】
請求項１３に記載の処理回路（Ｐ１）であって、
結果セレクタ（ＲＳ）のインターフェースは、以下の表による構成パラメータの入力及び操作パラメータの入力と出力とで定義され、表の第１の列はパラメータの名称を示し、第２の列はパラメータタイプを操作または構成とそれぞれ示し、第３の列はパラメータを入力または出力パラメータとしてそれぞれ示し、第４の列は入力また出力幅をビット長で示し、第５の列はそのパラメータの詳細定義を示すことを特徴とする処理回路。
0003588049.tif 000055
【請求項１５】請求項１４に記載の処理回路（Ｐ１）であって、
結果プロセッサ（ＲＳ）は、
−  第１の結果だけを使用する（ｒｅｓ１）
−  第２の結果だけを使用する（ｒｅｓ２）
−  第１及び第２の結果の論理ＡＮＤ操作を実行する
−  第１及び第２の結果の論理ＯＲ操作を実行する
−  処理回路（Ｐ１）のセットに操作≧を実行する
−  処理回路（Ｐ１）のセットに操作≦を実行する
の１つまたは複数の操作を実行することを特徴とする処理回路。
【請求項１６】
請求項１５に記載の処理回路（Ｐ１）であって、
結果セレクタ（ＲＳ）の構成パラメータＲＭを、結果セレクタが実行する各操作について３ビット２進値として入力することを特徴とする処理回路。
【請求項１７】
ツリー構造になっていて高速データストリームに含まれる複雑なパターンの認識と比較を行うマルチプロセッサ装置Ｐｎを備え、特に構造化または非構造化データベースに記憶されているデータを検索及び取り出す検索エンジンで使用される検索プロセッサ回路（ＰＭＣ）で、マルチプロセッサ装置Ｐｎは請求項１による処理回路Ｐ１を含み、マルチプロセッサ装置Ｐｎはｎ＋１レベルＳ０、Ｓ１、．．．．Ｓｎ及び次数ｋ＝２ｍの２進またはスーパー２進ツリーとして実現する回路を構成し、ｍは１以上の正の整数でスーパー２進ツリーはｋ＞２として定義される検索プロセッサ回路であって、マルチプロセッサ装置ＰｎはレベルＳｎに提供されてツリー内のルートノードを形成しインターフェース
0003588049.tif 000056
及び論理装置Ｅを備え、最も近い下位レベルＳｎ−１はマルチプロセッサ装置Ｐｎがネストされて提供されその子ノードを形成する２ｍ個の回路Ｐｎ−１であって、その各回路Ｐｎ−１は同じインターフェース
0003588049.tif 000057
を持ち且つ対応する論理装置Ｅを含む回路を備え、下位レベルＳｎ−ｑ、ｑ∈｛１，２，．．．ｎ−１｝のマルチプロセッサ装置Ｐｎは一般的に２ｍｑ個の回路Ｐｎ−ｑを備え、その各回路はインターフェース
0003588049.tif 000058
と且つ対応する論理装置（Ｅ）を備え上位レベルＳｎ−ｑ＋１の２ｍ（ｑ−１）個の回路Ｐｎ−ｑ＋１にネストして提供され、このレベルの各回路Ｐｎ−ｑ＋１は２ｍ個の回路Ｐｎ−ｑを備え、ｑ＝ｎ＝Ｓ０についてマルチプロセッサ装置Ｐｎに定義されたｎ−ｑ＝Ｓ０のゼロレベルはレベルＳ１の２ｍ（ｎ−１）個の処理回路Ｐ１内に比較器装置（ＣＯＭ）を形成する２ｍ（ｎ−１）から２ｍｎ個のカーネルプロセッサＰ０を備え、各処理回路Ｐ１は１から２ｍ個の比較器装置（ＣＯＭ）を備え、それぞれがインターフェース
0003588049.tif 000059
及び対応する論理装置（Ｅ）を持ち、一般的に、レベルＳ１、Ｓ２、．．．Ｓｎのすべての回路Ｐ１，Ｐ２，．．．Ｐｎは
0003588049.tif 000060
となるような同一のインターフェースＩを持ち、各論理装置（Ｅ）はレベルＳ１の処理回路Ｐ１が実行する検索操作または比較操作の結果を収集する結果セレクタ（ＲＳ）またはルックアップテーブル装置（ＬＵＴ）を備える、ことを特徴とする検索プロセッサ回路。
【請求項１８】
請求項１７に記載の検索プロセッサ回路（ＰＭＣ）であって、
レベルＳ１の各処理回路Ｐ１は、マルチプロセッサ装置Ｐｎが非縮小の２進またはスーパー２進ツリーを形成するように２ｍ個の比較器装置（ＣＯＭ）を備え、処理回路Ｐ１は上位レベルの回路Ｐ２を係数ｒ＝２ｍでマップし、一般的に、各場合に回路Ｐｎを構成する２進またはスーパー２進ツリーが、回帰的に生成された２進またはスーパー２進ツリーをレベルＳ１から備えるように、ｑ∈｛１，２，．．．ｎ−１｝のレベルＳｎ−ｑの回路Ｐｎ−ｑが上位レベルＳｎ−ｑ＋１の回路Ｐｎ−ｑ＋１を係数ｒ＝２ｍで回帰的にマップすることを特徴とする検索プロセッサ回路。
【請求項１９】
請求項１７に記載の検索プロセッサ回路（ＰＭＣ）であって、
マルチプロセッサ装置Ｐｎのインターフェース
0003588049.tif 000061
及び下位レベルＳｎ−ｑの回路Ｐｎに含まれる各回路Ｐｎ−ｑのインターフェース
0003588049.tif 000062
は、以下の表による構成パラメータの入力及び操作パラメータの入力と出力とで定義され、表の第１の列はパラメータの名称を示し、第２の列はパラメータタイプを操作または構成とそれぞれ示し、第３の列はパラメータを入力または出力パラメータとしてそれぞれ示し、第４の列は入力または出力幅をビット長で示し、第５の列はそのパラメータの詳細な定義を示すことを特徴とする検索プロセッサ回路。
0003588049.tif 000063
0003588049.tif 000064
0003588049.tif 000065
【請求項２０】請求項１７に記載の検索プロセッサ回路（ＰＭＣ）で、論理装置（Ｅ）は遅延装置（ＬＡＴ）とシーケンスコントロール装置（ＳＣ）とルックアップテーブル装置（ＬＵＴ）とで構成される回路であって、
論理装置（Ｅ）は、第１のＡＮＤゲート（２６）と、第１のマルチプレクサ（ＭＵＸ５）と、第２のＡＮＤゲート（２７）と、第２のマルチプレクサ（ＭＵＸ６）とをさらに備え、ルックアップテーブル装置（ＬＵＴ）は次の下位レベルの各処理回路Ｐｎ−１の結果出力に接続され、第１のＡＮＤゲート（２６）は前記回路Ｐｎ−１のそれぞれの文書出力に接続され、第２のＡＮＤゲート（２７）は第１のＡＮＤゲート（２６）の出力とルックアップテーブル装置（ＬＵＴ）の出力とに接続され、第１のマルチプレクサ（ＭＵＸ５）は第２のＡＮＤゲート（２７）の出力と前記回路Ｐｎ−１の最後の回路の第２の結果出力とに接続され、遅延装置（ＬＡＴ）は第１のＡＮＤゲート（２６）の出力に接続され、シーケンスコントロール装置（ＳＣ）は遅延装置（ＬＡＴ）の出力と、前記回路Ｐｎ−１の最初の回路の結果出力とフリップフロップ出力と、論理装置Ｅの結果出力と、前記回路Ｐｎ−１の最後の回路のフリップフロップ出力とに接続され、第２のマルチプレクサ（ＭＵＸ６）はシーケンスコントロール装置（ＳＣ）のフリップフロップ出力と、論理装置（Ｅ）の第１の及び第２のフリップフロップ入力のそれぞれと、さらに、第１及び第２のフリップフロップ出力をそれぞれを介し、前記回路Ｐｎ−１の最初の回路とに接続されていることを特徴とする検索プロセッサ回路。
【請求項２１】
請求項２０に記載の検索プロセッサ回路（ＰＭＣ）であって、
検索プロセッサ回路（ＰＭＣ）は、データ出力を介し、マルチプロセッサ装置Ｐｎの順次及び平行データ入力にそれぞれ接続され、文書出力を介して、マルチプロセッサ装置Ｐｎの順次文書入力に接続されている文書管理装置（ＤＯＣ）を備えていることを特徴とする検索プロセッサ回路。
【請求項２２】
請求項２０に記載の検索プロセッサ回路であって、
検索プロセッサ回路（ＰＭＣ）は、回路Ｐｎ−１の各結果出力と文書出力に接続され提供されている１／２ｋ＝２ｍ−１個のヒット管理装置（ＨＩＴ）を備え、各ヒット管理装置（ＨＩＴ）は結果入力を介し、マルチプロセッサ装置Ｐｎのインターフェースの各結果出力に接続されていることを特徴とする検索プロセッサ回路。
【発明の詳細な説明】
【０００１】
本発明は、高速データストリームにおける複雑なパターンの認識と比較を行う処理装置で、特に、構造化及び非構造化データベースに記憶されているデータを検索し取り出す検索エンジンで使用される処理回路に関する。この処理回路は、このような複数の処理回路で構成されるネットワークにおけるノードを形成する。また、本発明は、高速データストリームにおける複雑なパターンの認識と比較を行うツリー構造を持ったマルチプロセッサ装置Ｐｎからなる検索プロセッサ回路で、特に、構造化及び非構造化データベースに記憶されているデータを検索し取り出す検索エンジンで使用される検索プロセッサ回路に関する。マルチプロセッサ装置Ｐｎは、請求項１による処理回路Ｐ１を備え、また、マルチプロセッサ装置Ｐｎは、ｎ＋１個のレベルＳ０、Ｓ１、．．．Ｓｎと次数ｋ＝２ｍの２進またはスーパー２進として実現される回路を形成する（ここで、ｍは１以上の正の整数で、スーパー２進ツリーはｋ＞２により定義される）。
【０００２】
本発明は、複数の処理回路を持つマルチプロセッサ装置をベースにした検索プロセッサ回路を実現する。検索操作実行時に、データストリームは検索プロセッサ回路の処理回路をステップ単位で移動し、ステップごとに、現時点でチップに記憶されているデータは、ビットストリングとしてコーディングされ事前に処理回路に入力することができるパターンと比較される。
【０００３】
大量データストリームの情報検索用に、例えば、インターネットやイントラネットなどのデータ通信ネットワークの検索エンジンや、データストリームの内容の監視、大規模な構造化及び非構造化データベースからのデータの取り出し、などで話題になる情報検索用に、近年、幾つかの専用プロセッサが開発された。それは、上記の分野における情報の認識と取出しは重要な操作であって、通常のデータプロセッサでは効果的に実現するのが難しいからである。基本的には、大量データのパターンを検索したり取り出したりする場合、多数の処理要素を使用して同じデータ部分または異なったデータ部分を同時に検索する大量・平行処理による解決方法が適している。大量・平行処理は、大量の照会または検索を同時に処理することが可能である。検索処理については、検索対象となる情報の特徴を記述するための十分な表現能力を備えた特殊検索言語が提案されている。
【０００４】
この技術では、データストリングや記号ストリングの比較を使用するプロセッサが周知である。これに関連した従来技術の例としては、“Ｎｏｎ−ｎｕｍｅｒｉｃ  ｃｏｐｒｏｃｅｓｓｏｒ（非数値コプロセッサ）”という名称の国際特許出願ＰＣＴ／ＮＯ９２／００１７３号がある。さらに、パラケル（Ｐａｒａｃｅｌ）社は高速データ発見器（Ｆａｓｔ  Ｄａｔａ  Ｆｉｎｄｅｒ（ＦＤＦ））と呼ばれるデータ処理装置を開発していて、この装置はデータ間の類似点を分析するのに特に適している。ＦＤＦは正確な一致を検出できるパターン突合せテクノロジを使用していて、遺伝子研究やテキスト検索に有用なわずかな類似点を見つけることもできる。
【０００５】
また、リニアシストリックアレイプロセッサと呼ばれる米国特許第５，５５３，２７２号（Ｒａｎｇａｎａｔｈａｎ等）もある。このプロセッサは、特定アルファベットの２つのストリング間の編集距離を計算するものである。この計算は、少ないビット数で計算の状態を表すコーディング方法を基にしている。シストリックアレイプロセッサが採用しているアーキテクチャは、ＶＬＳＩの製作に最適なように、比較可能なストリング長に制限を設けず、しかも、最も近い隣接セルとだけ通信すればよい単純な基本セルを使用するというものである
【０００６】
このような周知の専用検索プロセッサの欠点は、非常に複雑な検索照会を処理する場合の機能が不十分な点である。また、これらの機能を提供しようとすると、その基となる回路アーキテクチャが必要以上に複雑になるという欠点もある。
【０００７】
この問題を解決する試みとしては、米国特許第４８６０２０１号（Ｓｔｏｌｆｏ等）が知られている。この特許は、それぞれが入出力装置を備えた多数のプロセッサを使用する２進ツリーとして構成された並列処理装置を開示している。概略を説明すると、Ｓｔｏｌｆｏ等は２進ツリー構造で接続された多数のプロセッサを持つコンピュータを開示している。これは、ツリーのルートとリーフをそれぞれ除けば、各プロセッサは親プロセッサを１つ持ち、子プロセッサを２つ持つ。これらのプロセッサは親プロセッサから送信されるデータと通常は同期して動作し、最も近い次のプロセッサにさらに結果を伝える。また、親プロセッサの子プロセッサは、お互いに通信することもできる。Ｓｔｏｌｆｏ等によれば、各ノードは処理要素を形成し、この要素が実質上のプロセッサ、読取り／書込みメモリーまたはランダムアクセスメモリー、及び入出力手段を備えている。この入出力手段は、２進ツリー構造を介してデータが送信される速度を大幅に向上させるように、各処理要素とその親及び子処理要素間のインターフェースを提供している。２進ツリー構造はすべてのノードに処理要素を備えているため、処理装置は通常は２ｎ−１の処理要素、つまり、２進ツリーをｎ＝１０レベルで実現している場合であれば、１０２３の処理要素を備える。好ましい実施例では、この従来技術の並列処理装置のクロック周波数は１２ＭＨｚである。これは、ツリーに１０２３のプロセッサがある場合は、各プロセッサの平均命令サイクル時間が１．８μｓである場合は、処理パフォーマンスは約５．７億命令／秒となる。
【０００８】
この種類の２進並列プロセッサは、大量の情報量単位で検索する場合など、区分可能データ処理問題を扱うのに適している。区分可能検索問題は、オブジェクトｘとオブジェクト集合間の関係に関する照会が、恒等関係を持つ「ａ  ２項演算子  ｂ」に可換及び結合を反復使用することと、新しいオブジェクトｘと集合Ｆの各要素ｆに適用される基本検索照会ｑとに対応する問題として定義できる。区分可能検索問題が発生するのは、論理関数ＯＲがオブジェクトｘとＦ内の各要素ｆ間に適用される基本照会「ｘ＝ｆ」と結合する場合である。Ｓｔｏｌｆｏ等が述べているように、集合Ｆに関する照会に応答する問題は、Ｆの任意の部分集合に適用される照会を組み合せることで回答を得ることができる。言いかえると、この問題は、区分可能で、並列処理による高速実行が適している。集合Ｆは、使用可能なプロセッサ数に等しい任意の部分集合に区分される。次に、基本照会ｑは、すべてのプロセッサに送られる未知数ｘとローカルに記憶されている集合Ｆ内の要素ｆ間で各プロセッサで並列に適用される。次に、この結果は演算子ｂをｌｏｇ２Ｎ回繰り返すことで並列で任意に組み合され、最初にＮ／２個の隣接プロセッサに対する計算が複数回行われ、次に、最初の計算の結果を使用してＮ／４個のプロセッサペアに対する計算が対応する回数だけ行われる。この操作は処理時に、２進ツリーの上位レベルの方向、即ち子プロセッサから親プロセッサに対し行われ、各レベルで並列に繰り返される。
【０００９】
本発明の出願人に属する国際特許出願ＰＣＴ／ＮＯ９９／００３０８から、デジタルデータ信号構造の処理に適したデジタル処理装置が知られていて、この装置では、データ信号構造は反復シーケンスとネストパターン（あるいはその両方）で構成されている。この処理装置は、通常は、ｎ＋１レベルＳ０、Ｓ１、．．．Ｓｎと次数ｋの通常のツリーとして構成される。このアーキテクチャは、上記の米国特許第４８６０２０１号で開示しているアーキテクチャと比べ幾つかの利点がある。例えば、１実施例では、スーパー２進ツリーの次数が４、８、１６．．．等になるように、次数２の通常の２進ツリーまたは次数２ｍ（ｍは２より大きな正の整数）のスーパー２進ツリーをベースにしたマルチプロセッサアーキテクチャを実現できる。この種類の２進またはスーパー２進アーキテクチャは、米国特許第４８６０２０１号で提案されているアーキテクチャと同様に、区分可能な検索問題を効果的な方法で処理できる。
【００１０】
したがって、本発明の主な目的は、出願人の上記の国際特許出願で開示している一般的なマルチプロセッサアーキテクチャを基に、マルチプロセッサアーキテクチャで実現可能な検索プロセッサ回路を提供することにある。ここで使用するアーキテクチャは、専用検索プロセッサを使用することで上記の不都合を回避し、同時に、米国特許第４８６０２０１号で開示している並列プロセッサの場合より処理効率及び装置効率がはるかに優れているアーキテクチャである。
【００１１】
さらに、本発明の目的は、検索プロセッサ回路に組み込んでマルチプロセッサ装置の実現に使用でき、パターンを比較することで検索を効率的に実行する処理回路を提供することにある。
【００１２】
最後に、本発明の目的は、２進区分可能検索問題を適切な機能で処理するだけでなくマイクロエレクトロニクスの分野で周知の回路解決方法を様々に統合して実現するアーキテクチャを活用する検索プロセッサ回路を提供することでもある。特に、この点について、所謂フィールドプログラマブルゲートアレイ（ＦＰＧＡ）または特定用途向け集積回路（ＡＳＩＣ）として実現されるマイクロエレクトロニクス構成要素の形式で回路を実現するのが本発明の目的である。
【００１３】
上記の目的及び他の機能と利点は、本発明では、処理回路のそれぞれ構成及び操作パラメータであるデータの入力及び出力のインターフェースであって、構成パラメータは、インターフェースの無指定または専用入力を介して処理タスクについて処理回路に一度だけ与えられ、操作データは特定の処理タスクの実行により処理され、それぞれ、インターフェースの指定された入力及び出力を介して処理回路へ連続的に入出力されるインターフェースと、比較器装置の形式をした少なくとも１つのカーネルプロセッサであって、比較器装置は２つのデータワードを比較するように適合された少なくとも１つのカーネルプロセッサと、比較器装置に接続される論理装置であって、論理装置は、インターフェースの入力（順次データ入力、順次文書入力、順次フリップフロップ入力、直前の処理回路からの順次結果入力、後続の処理回路からの順次結果入力、平行データ入力、平行文書入力、平行フリップフロップ入力、直前の処理回路に関する平行結果入力、及び後続の処理回路に関する平行結果入力）とインターフェースの出力（選択されたデータ値の出力、選択された文書値の出力、選択されたフリップフロップ値の出力、直前の処理回路への選択された結果の出力と選択された文書値の出力と、選択されたフリップフロップ値の出力と、直前の処理回路への選択された結果の出力と、後続の処理回路への選択された結果の出力）とに接続されたマルチプレクサと、第１のＤフリップフロップと、肯定２進値を特定の時間単位を使用して遅延するように適合された遅延装置と、第２のＤフリップフロップと、比較器装置内の比較操作を監視及び制御するように適合されたシーケンスコントロール装置と、他の処理回路または他の結果セレクタからの２つの結果値を結合するように適合された結果セレクタとを含む論理装置とを備え、比較器装置はマルチプレクサの選択データ値の出力とインターフェースのデータ出力とに接続され、さらに、結果出力を第１のＡＮＤゲートに接続され同等装置を第２のＡＮＤゲートに接続され、第１のＤフリップフロップはマルチプレクサの選択文書値の出力に接続され、リセットラインを介してリセット出力を第１のＡＮＤゲートの入力と、第２のＡＮＤゲートの入力と、遅延装置の入力とにそれぞれ接続され、さらに、インターフェースの文書入力と接続され、第２のＡＮＤゲートはインターフェースの同等出力を出力し、遅延装置は第１のＡＮＤゲートの出力とシーケンスコントロール装置の結果入力とに接続され、第２のＤフリップフロップは第１のＤフリップフロップのリセット出力及びシーケンスコントロール装置のフリップフロップ出力とフリップフロップ入力のそれぞれ、さらにインターフェースのフリップフロップ出力とに接続され、シーケンスコントロール装置はマルチプレクサの直前の処理回路からの選択されたフリップフロップ値の出力と選択された結果の出力及び直前の処理回路の結果入力とインターフェースの結果出力とに接続され、結果セレクタはインターフェースの第１の結果入力と、第１の文書入力と、第１の同等入力と、第２の結果入力と、第２の文書入力と、第２の同等入力とにそれぞれ接続され、インターフェースの結果出力と、文書出力と、同等出力とにそれぞれ接続されることを特徴とする処理回路で達成される。
【００１４】
本発明による処理回路の好都合な実施例では、比較器装置ＣＯＭは、データワードｘの形式の入力データを各場合に含みデータ入力とデータ出力にそれぞれ接続されている第１のレジスタと、第１レジスタに含まれるデータワードｘと比較されるデータワードａが含まれた第２のレジスタと、比較操作を実行するための１つまたは複数の論理ゲートおよびレジスタと接続されたマルチプレクサとを備え、マルチプレクサの出力が該比較器装置の結果出力を構成することを特徴とする。
【００１５】
本発明による処理回路の好都合な実施例では、遅延装置は、それぞれ、第１の入力を介して第２のＡＮＤゲートの出力に接続され第２の入力を介してリセットラインに接続されるカウンタで、該カウンタは構成遅延パラメータを含む遅延レジスタに接続され、遅延装置の結果出力である出力を出力するカウンタを備えることを特徴とする。
【００１６】
本発明による処理回路の好都合な実施例では、シーケンスコントロール装置は、直前の処理回路の結果入力と遅延装置の結果出力とに接続された第１のＡＮＤゲートと、第１のＡＮＤゲートの出力と第２のＤフリップフロップの出力とにそれぞれ接続された第１のＯＲゲートと、遅延装置の結果出力と後続の処理回路の結果入力に接続された第２のＡＮＤゲートと、後続の処理回路の結果入力と第２のＤフリップフロップの出力とに接続された第２のＯＲゲートと、遅延装置の結果出力とＯＲゲートの出力とに接続された第３のＡＮＤゲートと、遅延装置の結果出力と、ＡＮＤゲートと第１のＯＲゲートのそれぞれの出力と、直前の処理回路の結果入力と、後続の処理回路のフリップフロップ出力とにそれぞれ接続されたマルチプレクサとを備え、シーケンスコントロール装置が処理回路の結果出力を形成することを特徴とする。
【００１７】
本発明による処理回路の好都合な実施例では、結果セレクタは、第１の同等入力と第２の同等入力とに接続された第１のＡＮＤゲートと、第１の結果入力と第２の結果入力とに接続された第２のＡＮＤゲートと、第１の結果入力と第２の同等入力とに接続された第３のＡＮＤゲートと、第２の同等入力に接続されたＮＯＴゲートと、第２の結果入力とＮＯＴゲートの出力とに接続された第４のＡＮＤゲートと、第１及び第２の同等入力にそれぞれ接続された第１のＯＲゲートと、第１及び第２の同等入力にそれぞれ接続された第２のＯＲゲートと、第３及び第４のＡＮＤゲートの出力にそれぞれ接続された第３のＯＲゲートと、第１の結果入力と、第２の結果入力と、第１の同等入力と、第２の同等入力と、第１及び第２のＡＮＤゲートそれぞれからの出力と、第１、第２、及び第３のＯＲゲートそれぞれからの出力とに接続されたマルチプレクサと、第１及び第２の文書入力とインターフェースの文書出力とにそれぞれ接続された第５のＡＮＤゲートと、第５のＡＮＤゲートと、マルチプレクサの第１の出力と、インターフェースの結果出力とにそれぞれ接続された第６のＡＮＤゲートと、第５のＡＮＤゲートと、マルチプレクサの第２の出力と、インターフェースの同等出力とにそれぞれ接続された第７のＡＮＤゲートとを備えることを特徴とする。
【００１８】
上記の目的及び他の機能と利点は、本発明では、マルチプロセッサ装置はレベルＳｎに提供されてツリー内のルートノードを形成しインターフェース
0003588049.tif 000002
及び論理装置Ｅを備え、最も近い下位レベルＳｎ−１はマルチプロセッサ装置Ｐｎがネストされて提供されその子ノードを形成する２ｍ個の回路Ｐｎ−１であって、その各回路Ｐｎ−１は同じのインターフェース
0003588049.tif 000003
を持ち且つ対応する論理装置Ｅを含む回路を備え、下位レベルＳｎ−ｑ、ｑ∈｛１，２，．．．ｎ−１｝のマルチプロセッサ装置Ｐｎは一般的に２ｍｑ個の回路Ｐｎ−ｑを備え、その各回路はインターフェース
0003588049.tif 000004
と且つ対応する論理装置を備え上位レベルＳｎ−ｑ＋１の２ｍ（ｑ−１）個の回路Ｐｎ−ｑ＋１にネストして提供され、このレベルの各回路Ｐｎ−ｑ＋１は２ｍ個の回路Ｐｎ−ｑを備え、ｑ＝ｎ＝Ｓ０についてマルチプロセッサ装置Ｐｎに定義されたｎ−ｑ＝Ｓ０のゼロレベルはレベルＳ１の２ｍ（ｎ−１）個の処理回路Ｐ１内に比較器装置を形成する２ｍ（ｎ−１）から２ｍｎ個のカーネルプロセッサＰ０を備え、各処理回路Ｐ１は１から２ｍ個の比較器装置を備え、それぞれがインターフェース
0003588049.tif 000005
及び対応する論理装置を持ち、一般的に、レベルＳ１、Ｓ２、．．．Ｓｎのすべての回路Ｐ１、Ｐ２、．．．Ｐｎは
0003588049.tif 000006
となるような同一のインターフェースＩを持ち、各論理装置はレベルＳ１の処理回路Ｐ１が実行する検索操作または比較操作の結果を収集する結果セレクタまたはルックアップテーブル装置を備える、ことを特徴とする検索プロセッサ回路でも達成される。
【００１９】
本発明による検索プロセッサ回路の好都合な実施例では、レベルの各処理回路は、マルチプロセッサ装置Ｐｎが非縮小の２進またはスーパー２進ツリーを形成するように２ｍ個の比較器装置を備え、処理回路Ｐ１は上位レベルの回路Ｐ２を係数ｒ＝２ｍでマップし、一般的に、各場合に回路Ｐｎを構成する２進またはスーパー２進ツリーが、回帰的に生成された２進またはスーパー２進ツリーをレベルＳ１から備えるように、ｑ∈｛１，２，．．．ｎ−１｝のレベルＳｎ−ｑの回路Ｐｎ−ｑが上位レベルＳｎ−ｑ＋１の回路Ｐｎ−ｑ＋１を係数ｒ＝２ｍで回帰的にマップすることを特徴とする。
【００２０】
本発明による検索プロセッサ回路の好都合な実施例では、論理装置は遅延装置とシーケンスコントロール装置とルックアップテーブル装置とで構成される回路であって、論理装置は、第１のＡＮＤゲートと、第１のマルチプレクサと、第２のＡＮＤゲートと、第２のマルチプレクサとをさらに備え、ルックアップテーブル装置は次の下位レベルの各処理回路Ｐｎ−１の結果出力に接続され、第１のＡＮＤゲートは前記回路Ｐｎ−１のそれぞれの文書出力に接続され、第２のＡＮＤゲートは第１のＡＮＤゲートの出力とルックアップテーブル装置の出力とに接続され、第１のマルチプレクサは第２のＡＮＤゲートの出力と前記回路Ｐｎ−１の最後の回路の第２の結果出力とに接続され、遅延装置は第１のＡＮＤゲートの出力に接続され、シーケンスコントロール装置は遅延装置の出力と、前記回路Ｐｎ−１の最初の回路の結果出力とフリップフロップ出力と、論理装置Ｅの結果出力と、前記回路Ｐｎ−１の最後の回路のフリップフロップ出力とに接続され、第２のマルチプレクサはシーケンスコントロール装置のフリップフロップ出力と、論理装置の第１の及び第２のフリップフロップ入力のそれぞれと、さらに、第１及び第２のフリップフロップ出力をそれぞれを介し、前記回路Ｐｎ−１の最初の回路とに接続されていることを特徴とする。
【００２１】
本発明による検索プロセッサ回路の好ましい実施例では、データ出力を介し、マルチプロセッサ装置Ｐｎの順次及び平行データ入力にそれぞれ接続され、文書出力を介して、マルチプロセッサ装置Ｐｎの順次文書入力に接続されている文書管理装置（ＤＯＣ）を備えていることを特徴とする。
【００２２】
好ましくは、本発明による検索プロセッサ回路は、回路Ｐｎ−１の各結果出力と文書出力に接続され提供されている１／２ｋ＝２ｍ−１個のヒット管理装置（ＨＩＴ）を備え、各ヒット管理装置（ＨＩＴ）は結果入力を介し、マルチプロセッサ装置Ｐｎのインターフェースの各結果出力に接続されていることを特徴とする。
【００２３】
他の機能及び利点は、残りの追加従属請求項から明らかである。
【００２４】
以下に、本発明による処理回路の個別装置の実施例、その実施例の実例と該種類の処理回路を基にしたマルチプロセッサ装置を有する検索プロセッサ回路について、図面を参照して本発明を詳細に説明する。
【００２５】
個別装置及び回路の詳細な説明については、Ｖｅｒｉｌｏｇコードで開示している。これについては、この説明に別途用意された付録の表Ａ１−Ａ１３に示してある。当業者が周知のように、ＶｅｒｉｌｏｇはＩＥＥＥ標準１３６４−１９９５（「Ｖｅｒｉｌｏｇハードウェア記述言語に基づく標準記述言語」）で定義している。
【００２６】
以下に、本発明による検索プロセッサ回路を詳細に説明する。検索プロセッサ回路全体の動作については、図１に示す通りである。データストリームが回路を介してシフトされ、各ステップで、回路に現在存在するデータと他のある種のパターンとを比較する。このパターンはビットストリングとしてコーディングされていて、回路に書き込まれたものである。検索プロセッサ回路の基本単位は１バイトとし、このバイトが通常は１文字を表す。しかし、この長さレベルは非常に重要というわけではなく、容易に変更可能である。
【００２７】
本発明による検索プロセッサ回路は、比較器装置の形式をした多数のカーネルプロセッサで構成されていている。基本的な比較器装置を図２に示す。ここに示すレジスタＸにはバイトｘだけが含まれていて、これが比較器にシフトされる。レジスタＡには、ｘの比較対象となるバイトａが含まれている。図２から明らかなように、４種類の比較、つまりｘ＝ａ、ｘ≧ａ、ｘ≠ａ、ｘ≦ａは同時に実行可能で、結果は比較器装置の出力として得られる。カーネルプロセッサ、つまり、図２に示した比較器装置を相互接続することで、単純文字パターンの比較または突合せが可能である。例えば、図３に示すように接続された装置はストリング“ａｂｃ”（つまり、“ａ”の直後に“ｂ”が続き、その直後に“ｃ”が続く）と一致する。しかし、“ａ”の後ろに“ｂ”が続き、その直後に“ｃ”が続くパターンと比較することにも重要な意味がある。これを、以下ではパターン“ａｂ＋ｃ”と記述する。図３の比較器装置は、単一ビットメモリーを用意することで、この処理を実行できるように変更可能である。そのメモリのビットを“ｂ”に一致する要素に割り当て、最後のシフトが行われる前に“ｂ”が検出されたかどうかをそのビットで示す。さらに、比較器装置は次の、つまり後続の比較器装置も一致を示している場合だけ一致を示すように、ある種のシーケンスコントロールを実行することも必要である。これは、最終的な結果は、最後の比較器装置から得られることを意味する。その点については、最初の文字のシフト先装置が「第１」となるように、比較器装置（つまりカーネル処理装置）を用意するものとする。つまり、この装置がパターンの最後の文字を含み、「最後」の装置がパターンの最初の文字を含むことになる。
【００２８】
反復パターンの突合せをどのように行うかについて、図４ａ−図４ｅを参照して以下の例で説明する。
【００２９】
図４ａ−“ａ”が最初の比較器装置へシフトされる。どの比較器も一致を示していない。
【００３０】
図４ｂ−“ｂ”がシフトされ、この場合も一致していない。
【００３１】
図４ｃ−別の“ｂ”がシフトして入力されて最後の２つの装置が一致するが、最初の装置は一致していない。最後の２つの装置が一致したため、最初の装置が一致しなくても、この一致状態を中間の装置が一致している限り装置に記憶させる。
【００３２】
図４ｄ−複数の“ｂ”がシフトして入力されて、図４ｃで説明したように一致状態が維持される。この状態で“ｂ”以外の文字が中間の装置にシフトして入力されると、最初の２つの装置で維持されていた一致状態はクリアされることになる。
【００３３】
図４ｅ−“ｃ”が最初の装置にシフトされて入力され、３つの装置すべてが一致を示すように設定される。これで、“ａｂ＋ｃ”の形式のパターンが検出されたことになる。
【００３４】
複数の文字で構成されるパターンの反復にこの方法を使用する場合は、パターンに一致する比較器装置のグループにメモリを接続する必要がある。これについて以下に説明する。
【００３５】
上記で説明した方法を使用して複数バイト（例えば長さｎ）の反復して現れるパターンを突合せるためには、考えられるｎ個の開始点のそれぞれで一致が検出されるかどうかを調べる必要がある。このためには、ｎ個のフリップフロップを接続し、新しいバイトがこれらの装置にシフトして入力されるたびにメモリービットをフリップフロップにシフトする必要がある。これにより、最後のフリップフロップの出力を調べることで、ｎ個の箇所で一致が発生したかどうかを調べることができる。２文字のパターン突合せの例を図５に示す。ここで、Ｅ［ｉ］’は比較からの実際の結果で、Ｅ［ｉ−１］はシーケンスコントロールを実行するために使用される次の比較器装置からの結果で、Ｅ［ｉ］は信号ｍｉが設定されている場合に反復突合せが許されている場合の新しい結果である。信号ｓｃを調べることで、シーケンスコントロールが使用されたかどうかが分かる。ｓｃが設定されていない場合は、複数パターンの突合せは行われない。反復パターンの長さを変更することが可能な場合は、図６に示すような方法を使用することができる。ここでは、ｉ’番目のフリップフロップ後に出力を選択するためにマルチプレクサを使用していて、ｉは突き合わせるパターンの長さである。しかし、この方法を使用する必要はなく、それについて以下に説明する。
【００３６】
図７に、反復パターンの出現を突合せるのに必要なシーケンスコントロールを実行する装置を示す。この装置は、１組の比較器装置及び必要な数のＤフリップフロップ数と共に設置するものとする。マルチプレクサを使用し、複数のパターンの出現が可能かどうかを決定する。入力及び出力を以下に説明する。
ｒｅｓ［ｉ］’：  ｒｅｓ［ｉ］’信号は、反復可能パターンとの比較の結果である。
ｓｃ（バー）：  ｓｃ信号は、シーケンスコントロールを上記の節で説明したように使用するかどうかを指定する。ｓｃを設定すると、次の装置も肯定結果の場合だけ、この装置は肯定結果を出力する。設定しないと、結果は他の装置からの結果に依存し、反復突合せは行われない。
ｒｅｓ［ｉ−１］：  信号ｒｅｓ［ｉ−１］は、次の装置からの結果を入手し、シーケンスコントロールの実行に使用する。
ｆｆｏｕｔ［ｉ］：  信号ｆｆｏｕｔ［ｉ］はメモリービットが通過する最後のフリップフロップからの結果を入力する。
ｆｆｉｎ：  信号ｆｆｉｎは、メモリービットが通過する最初のフリップフロップへの入力として与えられる。
ｒｅｓ［ｉ］：  ｒｅｓ［ｉ］は当該装置からの新しい結果である。シーケンスコントロールを使用せずｓｃを設定しないと、この値はｒｅｓ［ｉ］’に等しくなる。設定すると、ｒｅｓ［ｉ−１］が真、及びｒｅｓ［ｉ］’が真、または反復パターンが許されている場合はｆｆｏｕｔ［ｉ］がセットされていれば、セットされる。
ｆｆｏｕｔ［ｉ＋１］：  ｆｆｏｕｔ［ｉ＋１］入力は、直前の要素のフリップフロップからの出力である。これにより、可変長の反復パターンの突合せ用に比較器装置を接続することが可能になる。
【００３７】
図８では、シーケンスコントロール装置を図２の比較器装置と共に示し、比較器装置により突き合せる文字が反復して現れてもよいようにしている。ここでは、単一のＤフリップフロップを使用してメモリを表している。このＤフリップフロップは、以下の条件が真の場合にセットされる。
・  これらの装置により突き合されるパターンが反復して現れてもよい。
・  当該装置及びそれ以降について同時に一致する。
・  上記の条件が真になった後に当該装置にシフトして入力されるすべてのバイトが一致する。
【００３８】
この回路構成を機能させるためには、一致パターンが複数回発生してもよい装置の出力を使用し、当該装置及び直前の装置の結果を示す必要がある。この機能を一般化するためには、上記で説明したように、シーケンスコントロールを複数のパターン突合せと共に常に使用する。この装置は、言いかえると、直前の装置も肯定結果の場合だけ肯定結果を出力する。
【００３９】
上記の節で説明した突合せまたは繰返しパターン以外にも、パターンの一部がオプションであるストリングの突合せにも重要な意味がある。この突合せはアナログ方法で実行でき、図９ａ−ｃを参照して以下の例により説明できる。
図９ａ  −  “ａ”がシフトして最初の装置に入力される。どの装置も一致していない。
図９ｂ  −  “ｃ”がシフトして入力され、最初の装置で一致する。中間の装置はこの事実を記憶する。
図９ｃ  −  文字は右方向にシフトされ、最後の装置で一致する。１文字前の時点では中間の装置で同じ一致が検出されたため、これらの装置はストリング“ａｃ”と一致したことになる。
【００４０】
この方法を実行するためには、繰返しパターンの一致の場合とは逆方向にシーケンスコントロールを機能させる必要がある。
【００４１】
ここで、複数の比較器装置へデータを分散するためのツリー構造について説明する。データ分散ツリーとして、図１０に示す完全な平衡２進ツリーを使用する。ツリー３の各内部ノードでは、マルチプレクサが２つのサブツリーが同じデータ要素を平行に受け取るかまたは要素を順次に受け取るかを決定する。図１１に、図１０の２進データ分散ツリーの簡単な実現例を示す。
【００４２】
上記で説明した反復またはスキップパターンの出現の突合せは、別の角度から考えることもできる。図８に示した処理回路を図１１のツリー構造の生成に使用し、反復及びスキップパターンを幾つかのレベルで突き合せる。この処理を単純化するために、この処理が許されるのは個別文字または８個の処理回路で構成されるツリー全体だけとする。
【００４３】
このような条件下では、このツリーには基本的には以下の６種類の異なったモードがある。
・  シーケンスコントロールを使用しない。８つの各処理回路の結果は独立している。
・  簡単なシーケンスコントロールを使用する。処理回路０からの結果だけを使用し、８つの比較器装置すべてが一致した場合だけ肯定とする。
・  １つまたは複数の比較器装置について反復突合せを可能とする。
・  １つまたは複数の比較器装置についてスキップ突合せを可能とする。
・  ツリー全体について反復突合せを可能とする。
・  ツリー全体についてスキップ突合せを可能とする。
【００４４】
上記で述べた項目の最初の項目は、図８に示した処理回路で処理され、第４の項目は、パターンをスキップするアナログ要素で処理される。しかし、最後の２つについては、別のシーケンスコントロール装置（図７に示す）をツリー全体に使用する必要がある。この図から分かるように、適切なフリップフロップ数がこの装置で利用できなければならない。使用するフリップフロップ数は、反復パターンに含まれる文字数と等しくなければならず、この文字数は、ツリーを定義しているマルチプレクサの構成により１から８文字まで変化する。図６に示すような解決方法を使用すれば良いことは分かっているが、この方法では、反復文字数が２度セットされると（ツリー定義時に１度と、正しいフリップフロップからの結果を選択するマルチプレクサで１度）、回路のプログラミングが複雑になり、エラーが発生しやすくなる。都合のよいことには、ツリー内の処理回路にすでに存在しているフリップフロップを使用して、より簡潔な解決方法が可能である。任意の時点でツリー内に存在する文字数がデータフローにより与えられると、データ分散用のマルチプレクサを使用し、適切なフリップフロップ数でメモリービットを転送できる。この方法を実現したものを図１２に示してある。同じフリップフロップを２つの可能なレベルでの繰返しに使用すると、そのパターンはいずれかのレベルで一度に反復できる。複数レベルで反復パターンを同時に使用することは、どのような場合でも、この方法で実行することはできないことに注意すべきである。これは、反復可能ストリングの長さが変わるからである。さらに複雑な点は、各処理回路はシーケンスコントロールを実行するために直前の比較器装置からの結果を必要とする点で、これについて以下に述べる。
【００４５】
ツリー構造を拡張することができる。図１３に示すように、合計３２個のカーネルプロセッサつまり比較器装置が使用され、単一の処理回路、８つの処理回路グループ、またはツリー全体で反復処理を実行できる。同じ理由が、パターンのスキップにも適用される。
【００４６】
基本的に、データ収集ツリーから結果を収集する方法には、上記の節で説明したように実際には２つの方法がある。最も自然な方法は、別の２進ツリーを使用し、結果を各内部ノードで結合することである。しかし、一定数の処理回路の突合せなど特定の操作を実行することが不可能であるため、この方法には幾つかの欠点がある。処理回路数が比較的少ない場合は、ルックアップテーブルＬＵＴを使用することが可能である。しかし、ツリーの一部について突合せが定義されていないため、反復突合せが許されているときはこの方法は問題がある。これら２つの方法については以下の節で説明し、その説明に続き、これら方法の利点と欠点を説明する。まず、２進ツリーによる結果の収集方法を説明する。
【００４７】
２つの処理回路から結果が与えられると、それらを組み合わせてＡＮＤ及びＯＲの論理操作のいずれかを実行するのが自然である。また、２つの処理回路からの結果のいずれかを選択して他方を無視することができると、有利な場合もある。この操作を実行する装置を図１４に示し、以下でセレクタとして示す。この装置を２進ツリーで組み合せ、図１５に示すように、処理回路のグループから１つの結果を得ることができる。２進ツリーを使用して、ストリングを英字順または数字順に比較することも可能で、これについては以下に説明する。上記で述べた問題、つまり、現在の処理回路で処理している文字の前後の文字を比較する結果を入手することは、この方法で処理できる。まず、任意の時点で、直前または直後のいずれかの結果だけが必要である。これは、反復パターンとスキップパターンの両方の突合せを同時に実行することはできないからである。これは、使用するシーケンスコントロールでは、異なった文字を調べる任意処理回路の右側または左側のいずれかの結果を選択できるように、結果収集ツリーを構成できることを意味する。ｎ個の装置で構成される任意のサブツリーの結果は、結果収集ツリー内のｎレベル遡ったレベルで見つけることができる。幾つかの装置が同じ文字を調べる場合、直前及び直後の結果も同じになる。これらの結果は、同じ文字を調べる隣接装置にだけ結果を渡すように、同じマルチプレクサを使用してデータフローを制御して見つけることができる。
【００４８】
図１６は、この方法を使用して実施例を完成させる方法を示したものである。同じマルチプレクサセットを３つの異なった目的で使用することに注意することが重要である。即ち、データを分散すること、適切な数のフリップフロップによりメモリービットを転送すること、及び直前または直後の文字の比較から得られる結果を提供することである。
【００４９】
異なる処理回路から得られる結果を組み合せる簡単な方法は、ルックアップテーブル（ＬＵＴ）を使用することである。一致数をカウントするなど、異なった処理回路に任意の要件を指定することができる。適切な小さなツリーを使用している限り、ルックアップテーブル（ＬＵＴ）のサイズが大きくなり過ぎることはない。８つの比較器装置の場合、２８＝２５６ビットを設定する必要があり、これは管理可能である。ＬＵＴが備わったデータ分散ツリーの実現例を図１７に示す。この方法を使用する場合の主な欠点は、単一の処理回路のレベルまたはツリー全体について行われない限り、パターンの反復出現を突き合せることができない点である。これは、ＬＵＴを使用する場合、２ｎ個の装置で調べる文字に関する結合を定義できないからである。しかし、シーケンスコントロールの機能を発揮させるにはこれは必要である。
【００５０】
場合によっては、ヒットを長期間維持することが望ましい場合がある。つまり、一致が検出されたら、実際の一致検出後に特定の文字数の間、肯定結果を維持する。この機能を使用すると、複数パターンの一致がお互いに一定の距離内にある検索を実行できる。これを簡単に実現したものを図１８に示す。この図では、ある数値ｎをレジスタに記憶し、一致が検出されると、この値を次のカウンタにシフトする。このように、最終結果は、カウンタが０になり一致の遅延がｎ文字になるまで、正の値で維持される。この遅延はヒット遅延と呼ばれる。
【００５１】
上記を考え合わせると、結果を収集するためにツリーとＬＵＴを使用することは、長所も短所もあることが分かる。ツリーの方法は反復パターンの突合せを簡単にするが、特定の論理関数しか使用できない。これに対し、ＬＵＴは使用可能なすべての関数を使用できるが、反復パターンの突合せは厄介になる。
【００５２】
したがって、明らかな解決方法は、両方の方法を使用することである。これにより、ユーザはそれぞれの場合に最善の方法を選択できるからである。しかし、この方法では、オーバーヘッドが増える。さらに、ツリーの場所により異なった方法を使用するという方法もある。例えば、反復パターンが最も望まれる下位レベルではツリー方法を使用し、異なったパターンのヒット数のカウントは望まれる可能性がある上位レベルではＬＵＴを使用し、また、下位レベルでは両方を使用して上位レベルではＬＵＴだけを使用するなどの方法である。
【００５３】
テキストデータは、オーバーラップしない文書セットに分割することがある。このような文書について検索を実行するときは、複数の文書にまたがった一致を取り出すことは通常は望ましくない。したがって、何等かの方法でこのような取出しを避けるようにする必要がある。図１９は、データ分散ツリーを無視したパターン突合せの検索プロセッサ回路の基本操作を示している（「パターン突合せチップ」（ＰＭＣ））。ここに示してある各処理回路は、テキストに含まれる１文字だけを処理すると考えられる。文書の分離は、図２０に示す構成を使用して処理できる。この図では、特殊なパターン突合せ装置をデータパスの先頭に置き、この装置でタグを検索する。このタグは、新しい文書の先頭を示すものである。このタグを示す信号がデータと共に各処理回路へ渡される。この信号を受け取ると、処理回路は、設定されている可能性があるすべての遅延をリセットできる。この信号はさらに結果セレクタ及び結果を収集するルックアップテーブルＬＵＴへも渡される。これは、同じ文書内で肯定結果が得られたときだけそれらの結果を受け取るようにするためである。
【００５４】
上記で説明したパターン突合せ機能を用意しても、なお解決しなければならない次のような２つの問題がある。
・  受信システムが処理できるように、ヒット数が十分に制限する。
・  データ分散ツリーの異なった箇所で、異なった照会を同時に処理できなければならない。
【００５５】
これら２つの問題は関連していて、以下で説明する。
【００５６】
ヒット数の制限を最初に説明する。パターン突合せチップからホストプロセッサへヒットを返す機能は容量が限られていて、しかも、ヒットがグループ単位で発生するため、何等かの方法でヒット数を制限する必要がある。この問題については、次の２つの明らかな解決方法がある。
・  一定の隣接文字については、１つのヒットだけを報告する。
・  各文書について１つのヒットだけを報告する。
【００５７】
通常であれば、これら両方の方法を採用する。図２１は、その方法を示したものである。フリップフロップＤは現在のヒット範囲内でヒットが報告されたかどうかを追跡し、すべてのヒットが報告された場合にマルチプレクサＭＵＸの最初の入力を選択する。さらに、実際のヒットの代わりにこの数を返却するように、ヒット数をカウントするカウンタを設ける。１文書に１ヒットだけを報告する場合、このカウントがヒットを持つ文書数になる。
【００５８】
次に、複数照会の管理を説明する。パターン突合せチップ（検索プロセッサ回路）が複数の同時照会を処理できれば非常に便利である。単一照会に必要な処理回路数は大幅に異なる可能性が高いため、単一照会は個別に構成できるはずである。その実際的な方法の１つは、データ分散ツリーの一部に個別照会を構成させる方法である。この方法の問題点は、膨大な結果数（ｎ処理回路について２ｎ−１）を受信システムに戻さなければならないことである。つまり、処理回路が５１２の場合は、考えられる結果数は２・５１２−１＝１０２３で、これは通常は多過ぎると考えられる。この数を制限する最もありふれた方法は、単一照会に使用する処理回路数の下限を設定することである。適切な数は１６で、この場合は５１２回路について、２・（５１２／１６）−１＝６３の結果が得られ、容認できる数となる。図２２は、ツリーの下位レベルのボックスを１６個の処理回路（つまり比較器装置）で構成したときに予想される結果を模式的に示したものである。これを上記の節で説明した方法と組み合せると、予想される各結果にヒット制限装置が組み込むことができる。しかし、同時照会はｎ／１６以下であるため、この回路数で十分である。この方法を有効に機能させるためには、ヒット制限装置が複数の場合、同時にアクティブになることがないようにこれらの照会を選択しなければならないため、予想されるいくつかの照会から結果を入手する必要がある。図２３は、その実行方法を示したものである。この図で黒の照会点には自分自身のヒット制限装置があり、白の照会点だけが矢印で示すように結果を分散する。さらに、その結果が実際に独立照会を表しているかどうかを示すために、考えられる各照会について１ビットをセットする必要がある。
【００５９】
以下に、本発明による処理回路を詳細に説明する。処理回路は、検索プロセッサの１モジュールと見なされるため、ここでは、検索モジュールとして説明する。詳細な説明では、個別装置についてＶｅｒｉｌｏｇコードを参照する。これらのコードは、この説明の付録に表として示してある。
【００６０】
検索プロセッサ回路の処理回路にはクロックが組み込まれていて、このクロックのＶｅｒｉｌｏｇコードは付録の表Ａ１に示してある。クロック信号ＣＬＫは、いずれの場合も、処理回路内の比較器装置とＤフリップフロップにそれぞれ送られるか、または検索プロセッサ回路内のすべての比較器装置とＤフリップフロップに送られる。これは自明であるため、クロック及びクロック信号線についてはここでは示していない。
【００６１】
カーネルプロセッサ、つまり、比較器装置を図２５に示す。この装置は、勿論、図２のカーネルプロセッサつまり比較器装置に相当する。レジスタ６には、以前の説明と同様に、現在この装置にシフトされて入力されているバイトｘが含まれていて、レジスタ７にはバイトａが含まれていて、ｘとの比較に使用される。図２５から分かるように、４種類の比較、つまり、ｘ＝ａ、ｘ≧ａ、ｘ≠ａ、ｘ≦ａが実行可能である。結果は、ｒｅｓとして出力に送られる。さらに、信号ｅｑはｘ＝ａを示し、これを使用することでストリングを英字順及び数字順に比較できる。これについては、以下に詳細に説明する。カーネルプロセッサつまり比較器装置を実現するＶｅｒｉｌｏｇコードを付録の表Ａ２に示す。入力と出力が与えられた比較器装置のインターフェースの説明は、表１から明らかである。
表１
0003588049.tif 000007
【００６２】
図２５にＤフリップフロップを模式的に示す。Ｄフリップフロップを実現するＶｅｒｉｌｏｇコードを付録の表Ａ３に示す。入力と出力が与えられたインターフェースの説明は、表２から明らかである。
表２
0003588049.tif 000008
【００６３】
遅延装置ＬＡＴを図２６に示す。この装置は肯定２進値ｒｅｓ＿を一定サイクル数だけ遅延するのに使用する。レジスタ９には遅延が含まれていて、カウンタ８は肯定結果が登録されてからのカウントダウンに使用される。ｒｅｓは変更結果信号で、信号＿ｒｅｓｅｔはカウンタを０にセットする。遅延装置ＬＡＴを実現するＶｅｒｉｌｏｇコードを付録の表Ａ４に示す。入力と出力が与えられたインターフェースの説明は、表３から明らかである。
表３
0003588049.tif 000009
【００６４】
文書管理装置ＤＯＣを図２７に示す。この装置は、検索プロセッサ回路に各種文書を追跡させる。３つの比較器装置またはその接尾部は新しい文書を示すタグに一致するようにセットし、信号ｄｏｃはこのタグが現れると０に設定される。タグに３文字未満が使用されるときは、左側から最も遠い比較器装置は結果に影響を及ぼさないため、この図は少し変更される。遅延値は、タグの文字数、即ち１から３にセットされる。この装置を実現するＶｅｒｉｌｏｇコードを付録の表Ａ５に示す。入力と出力が与えられたインターフェースの説明は、表４から明らかである。
表４
0003588049.tif 000010
【００６５】
入力が８個のルックアップテーブル装置ＬＵＴを図３６に示す。ｒｅｓは結果である。ルックアップテーブル装置のＶｅｒｉｌｏｇコードを付録の表Ａ６に示す。入力と出力が与えられたインターフェースの説明は、表５から明らかである。
表５
0003588049.tif 000011
【００６６】
シーケンスコントロール装置ＳＣは、以下の３つの可能性を実現するために使用される。
・  現在の回路が一致を報告する前に、直前または直後の処理回路つまり比較器装置が一致を報告することを要求する。
・  パターンの一部が欠落している場合のパターンの突合せを行う。
・  パターンの一部が反復している場合のパターンの突合せを行う。
【００６７】
シーケンスコントロール装置ＳＣは、処理回路と組み合わせて使用する。この処理回路は、単一のカーネルプロセッサつまり比較器装置でも、処理回路のグループと１組のフリップフロップでもよい。フリップフロップの数は、処理回路で突き合せる文字数に等しくする。これを図２９に示す。したがって、シーケンスコントロール装置ＳＣは、図３０に示すように実現できる。ここでは、３つの結果値及び現在及び直前のフリップフロップからの値を入力として使用し、新しい結果値を出力する。これで、シーケンスコントロール装置ＳＣの動作だけを純粋の組合せとして指定すればよいことになる。
【００６８】
５種類のケース、即ち、シーケンスコントロールなし、前方シーケンスコントロール、後方シーケンスコントロール、反復パターンの突合せ、及びスキップパターンの突合せ、に関する真理値表を、表６から１０にそれぞれ示す。
表６−シーケンスコントロールなし
0003588049.tif 000012
表７−前方シーケンスコントロール
0003588049.tif 000013
表８−後方シーケンスコントロール
0003588049.tif 000014
表９−反復パターンの突合せ
0003588049.tif 000015
表１０−パターンのスキップ
0003588049.tif 000016
【００６９】
これらの表には示していないが、最初の３つの場合の出力ｆｆ＿ｏｕｔは直前の処理回路のフリップフロップからの出力に等しく設定し、フリップフロップ値がシステムの各構成要素へ流れるようにする。表１１に示した記号形式は、追加されている真理値表を基に、簡単に導き出すことができる。結果として得られるシーケンスコントロール装置を図３０に示す。この図に示されているマルチプレクサは操作モードを、右から左、上から下へ番号が付けられた表１１の５種類の操作モードから選択する。
表１１  記号表現
0003588049.tif 000017
【００７０】
シーケンスコントロール装置を実現するＶｅｒｉｌｏｇコードを付録の表Ａ７に示す。入力と出力が与えられたインターフェースの説明は、表１２から明らかである。
表１２
0003588049.tif 000018
【００７１】
結果セレクタＲＳは、処理回路または他の結果セレクタからの２つの結果値を結合する場合に使用する。以下の操作がサポートされている。
・  最初の結果だけを使用する。
・  ２番目の結果だけを使用する。
・  ２つの結果の論理演算ＡＮＤを実行する。
・  ２つの結果の論理演算ＯＲを実行する。
・  処理回路の組について操作≦を実行する。
・  処理回路の組について操作≧を実行する。
【００７２】
最初の４つの操作は直接処理できるが、残りは多少複雑である。図３１は、英字／数字で１９９０より大きなすべてのストリングの突合せ処理を示した例である。セレクタＲＳ２から開始し、最右端の処理装置と突き合せ、突合せの対象となる数字の最左端の文字である文字が１より大きい場合、数字全体は比較対象より大きく、これが結果となる。この例では両者は等しいため、他の処理回路で決定する。したがって、セレクタＲＳ２は同等を返す。セレクタＲＳ１は、再び同じ原理を使用する。この場合、２番目のセレクタＲＳ２は同等を返すが、第１のセレクタＲＳ１は値が比較対象より大きい値を返し、これがＲＳ１の結果となる。セレクタＲＳ３も同じ動作を実行し、１９９０より大きな数字であることを返す。英字／数字比較を行った場合は、ｒｅｓはｒｅｓ＝ｅｑ２ｒｅｓ１±ｅｑ２ｒｅｓ２が与えられる。
【００７３】
上記の機能に基づき、実現される結果セレクタは図３２に示すようになる。マルチプレクサＭＵＸ４は、５つの操作モード、つまり、第１の結果を選択する、第２の結果を選択しその結果にＡＮＤ操作を実行する、結果にＯＲ操作を実行する、ストリング比較を実行する、の５つの操作モードから選択する。
【００７４】
この装置を実現するＶｅｒｉｌｏｇコードを付録の表Ａ８に示す。入力と出力が与えられたインターフェースの説明は、表１３から明らかである。文書信号と文書管理装置とを使用し、文書境界をまたがる結果は受け付けないようにする。
表１３
0003588049.tif 000019
【００７５】
本発明による処理回路を、図３３に示す。この回路は、少なくとも１つの比較器装置ＣＯＭ、１つの遅延装置ＬＡＴ、Ｄフリップフロップ２，４、シーケンスコントロール装置ＳＣ、及び結果セレクタＲＳで構成されている。図３３には、入力と出力とを備えた処理回路のブロック版を示してある。処理回路を実現するＶｅｒｉｌｏｇコードを付録の表Ａ９に示す。入力と出力が与えられたインターフェースの説明は、表１４から明らかである。
表１４
0003588049.tif 000020
0003588049.tif 000021
【００７６】
データツリー、つまり、マルチプロセッサ装置Ｐｎの形式をした本発明による検索プロセッサ回路ＰＭＣを、図３３に示す。マルチプロセッサ装置はツリーとして構成されていて、８つの処理装置Ｐｎ−１、シーケンスコントロール装置ＳＣ、遅延装置ＬＡＴ、及びＬＵＴとで構成されている。回路Ｐｎ、つまり“Ｔｒｅｅ８”という名称のデータツリーは、処理回路とまったく同じインターフェースを持っている。これは、ツリーに含まれる各処理回路をこの種類のツリーで置き換えることで、任意のレベル数でツリーを構成できることを意味する。また、データツリーが、複数のネストされた回路Ｐｎ−ｑを含むことも意味する。それは、データツリー自身が最高位レベルの場合、つまり、レベルＳｎ及びｑ∈｛１，２，．．．．ｎ｝の場合、下位レベルＳｎ−ｑの各回路が上位レベルＳｎ−ｑ＋１の回路内にネストするように構成される。ツリーが正規ツリー（例えば２進ツリー）の場合、あるレベルの処理回路Ｐｎ−ｑはその上位レベルＳｎ−ｑ＋１の処理回路Ｐｎ−ｑ＋１を再帰的にマップする。２進ツリーの場合は、当然、マッピング係数２でマップする。導入部でも述べたように、一般的な検索問題は２進の区分可能問題と見なすことができるため、次数が２でなく、４、８、１６など（ここではスーパー２進と呼ぶ）のツリーについても、この種類の区分化問題の管理に問題ない。一般的に述べれば、次数ｋ＝２ｍで、スーパー２進ツリーのツリーの場合、ｍは１より大きい整数（つまりｋ＞２）である。再帰マッピングでは、マッピング係数は勿論ｒ＝ｋである。例えば、図３５に示すツリーは、第１のレベルが８つの処理回路Ｐ１を含み、それぞれが、例えば図３３の処理回路Ｐｎ−１にそれぞれ対応しているため、２レベルＳ１、Ｓ２のプロセッサと見なすことができる。したがって、各回路には１つのカーネルプロセッサ、つまり、１つの比較器要素ＣＯＭが含まれる。このように、カーネルプロセッサは、このツリーのリーフノードで、ツリーのゼロレベルの回路Ｐ０で実現されるツリー内のゼロレベルＳ０を形成する。一方、処理回路Ｐ１は、カーネル処理装置Ｐ０と図３３に示す処理回路の残りの構成要素で表されている論理要素Ｅとで構成される。レベルＳ２では、回路は検索プロセッサ自身と同一で、この回路がレベルＳ１自身の８つの処理回路Ｐ１に加えて、論理装置Ｅを備えている。この論理装置は、実際に、前述したシーケンスコントロール装置ＳＣ、遅延装置ＬＡＴ、及びＬＵＴを含んでいる。これまでの説明で、図３３のマルチプロセッサ装置Ｐｎは、各処理回路Ｐ１が１つ比較器装置しか含まないため、対称の均衡縮小ツリーとなる。しかし、検索プロセッサ回路、つまりｔｒｅｅ８、を次数８の正規の非縮小ツリーとして実現し、第１レベルの８つの処理回路Ｐ１それぞれが８つのカーネルプロセッサ、つまり比較器装置Ｐ０を備えて、合計６４になるようにしても問題はない。正規性を保ったままでツリーのレベルをさらに拡張すると、ゼロレベルＳ０は５１２のカーネルプロセッサつまり比較器装置になり、第１レベルＳ１は６４の処理回路Ｐ１になり、第２レベルＳ２は８つの処理回路Ｐ２になり、検索プロセッサ装置回路はレベルＳ３の回路Ｐ３で構成されることになる。図３５に示すｔｒｅｅ８を実現するＶｅｒｉｌｏｇコードは付録の表Ａ１０に示す。入力と出力とで示す検索処理回路のインターフェースの説明は、表１５から明らかである。
表１５
0003588049.tif 000022
0003588049.tif 000023
0003588049.tif 000024
【００７７】
例えば、検索プロセッサを６４または５１２のカーネルプロセッサでそれぞれ実現する場合、マッピング係数８の正規ツリーの形式でネストされた回路として理想的な検索プロセッサを実現できる。しかし、ｔｒｅｅ６４またはｔｒｅｅ５１２としても、それぞれ、直接実現することもできる。いずれの場合も、６４個のカーネルプロセッサを備えた検索プロセッサのＶｅｒｉｌｏｇコードは付録の表Ａ１１に示し、５１２個のカーネルプロセッサを備えた検索プロセッサのＶｅｒｉｌｏｇコードは付録の表Ａ１２に示す。
【００７８】
ヒット管理装置ＨＩＴを図３６に示す。ここではフリップフロップは、次の装置を報告の対象とするかどうかの追跡に使用している。ヒット管理装置を実現するＶｅｒｉｌｏｇコードを付録の表Ａ１３に示し、入力及び出力が与えられたインターフェースの説明は、表１６から明らかである。
表１６
0003588049.tif 000025
【００７９】
添付の図３７は、文書管理装置ＤＯＣとヒット管理装置ＨＩＴとが図３５に示すマルチプロセッサ装置Ｐｎつまりｔｒｅｅ８の形式で検索処理回路ＰＭＣ内に設置されている様子を示している。分かりやすくするために、図３７にはＤＯＣとＨＩＴとマルチプロセッサ装置間の接続線しか記載せず、残りの信号線は省略している。この図から、検索プロセッサ装置ＰＭＣがマルチプロセッサ装置Ｐｎ以外にも文書管理装置ＤＯＣを備えていて、この文書管理装置がデータ出力を介してマルチプロセッサ装置Ｐｎの順次及び平行データ入力にそれぞれ接続し、文書出力を介して、マルチプロセッサ装置Ｐｎの順次文書入力に接続されていることが分かる。さらに、検索プロセッサ回路ＰＭＣは、１／２ｋ＝２ｍ−１＝２３−１＝４個のヒット管理装置ＨＩＴ１−４も備えている。これらのヒット管理装置は処理回路Ｐｎ−１の結果出力と文書出力とにそれぞれ接続していて、各ヒット管理装置ＨＩＴは、結果出力を介して、検索プロセッサ回路のインターフェースの各結果出力に接続している。ヒット管理装置については、さらに図２１で模式的に示し、その図に関連して説明している。さらに、検索プロセッサ回路ＰＭＣ内にヒット管理装置ＨＩＴを備えることについては、図２３に示したツリー構造のマルチプロセッサ回路として実現されていて、この図に関連して、ヒット管理装置を使用して複数の質問から得られる結果を報告する方法についてもすでに説明してある。したがって、ここでは詳細には扱わない。しかし、注意しなければならない点は、ヒット管理装置は黒のノードにだけ備わっていて、図２３の白のノードは矢印で示すように結果を分散するということである。
【００８０】
したがって、図３７に示すヒット管理装置の２つの入力側に、マルチプレクサが１台と２台それぞれ備わっている。
【００８１】
回路チップにおける実装では、本発明による検索プロセッサ回路ＰＭＣは、好ましくは、ｋを２３、２６、または２９などのスーパー２進ツリーとして実現する。したがって、回路はゼロレベルで均衡縮小型のスーパー２進ツリーになる。この場合も、マルチプロセッサ装置ＰｎはＰ２に等しくなることを意味し、それぞれ、８個のプロセッサ装置Ｐ１を備えたｔｒｅｅ８、または６４個の処理装置Ｐ１を備えたｔｒｅｅ６４、または５１２個の処理装置Ｐ１を備えたｔｒｅｅ５１２をそれぞれ形成することを意味する。この処理装置は、それぞれ、１つの比較器装置ＣＯＭを備えている。したがって、ゼロレベルでは、ツリーは縮小している。また、各処理回路Ｐ１の論理装置Ｅも、フリップフロップ、マルチプレクサＭＵＸ１、遅延装置ＬＡＴ、及び結果セレクタＲＳとは別に、１つのシーケンスコントロール装置ＳＣだけで実現できる。
【００８２】
最後に、本発明による検索プロセッサ回路ＰＭＣ内のマルチプロセッサ装置Ｐｎは、任意の次数で任意のレベルのツリーネットワークに基づいたマルチプロセッサアーキテクチャの特殊なケースである点に注意しておく。これについては、本発明の出願人に属しＮＯ特許出願第１９９８４７４６号（１９９８年１０月９日）から優先権を得ている上記の国際特許出願ＰＣＴ／ＮＯ９９／０３０８（Ｈａｌａａｓ等）で開示している。この種類の複数プロセッサアーキテクチャの特殊な機能は、単一のデータプロセッサだけがツリー構造のゼロレベルに備わっているか、またはツリーが縮小ツリーの場合は、ツリー構造内の第１レベルの処理回路に対応していることである。縮小がゼロレベルＳ０で対称でありしかも均衡している場合は、回路はレベルＳ１の処理回路Ｐ１により上位レベルＳ２，．．．Ｓｎでさらに再帰的に生成される。このような回路は非常に安価に実現でき、しかも、任意の区分度のデータ処理問題（従来からの検索問題も当然含め）、一般的な２進区分可能データ処理問題として扱うことができる。
【００８３】
Ｈａｌａａｓ等をベースに、カーネルプロセッサＰ０は図８に示す接続に正式に対応し、プロセッサ本体以外にも、図３８に示すように比較器装置ＣＯＭ、遅延装置ＬＡＴ、シーケンスコントロールＳＣ、必要な数のフリップフロップ２，４、及び論理ゲート１，３を備えている。勿論、比較器装置ＣＯＭごとに、シーケンスコントロール装置ＳＣ（図２９と比較）を備える必要がある。したがって、図３３に示す処理装置Ｐ１は、実際には、２つまたはそれ以上の比較器装置を備え、論理装置Ｅには対応する数のシーケンスコントロール装置ＳＣを備える必要がある。比較器装置ＣＯＭ（正式にはカーネルプロセッサ本体１７）とシーケンスコントロール装置ＳＣとが備わった回路Ｐ０のインターフェースは、表１７に示す回路の入力及び出力が送られる。
表１７
0003588049.tif 000026
【００８４】
実際には、本発明による検索プロセッサ回路ＰＭＣは集積回路チップで実現され、好ましくは、レベルＳ１の処理回路Ｐ１が比較器ＣＯＭを１つだけ有するスーパー２進ツリーとして実現する。これにより、実際の処理すべて（検索と突合せ操作）がこのレベルで行われる。検索プロセッサ回路Ｐｎ＝Ｐ２（つまり、正式には３レベル）として実現すると、例えば５１２個の処理回路Ｐ１を持つスーパー２進ツリーが形成され、これにより、回路チップの利用価値はさらに高まる。
0003588049.tif 000027
0003588049.tif 000028
0003588049.tif 000029
0003588049.tif 000030
0003588049.tif 000031
0003588049.tif 000032
0003588049.tif 000033
0003588049.tif 000034
0003588049.tif 000035
0003588049.tif 000036
0003588049.tif 000037
0003588049.tif 000038
0003588049.tif 000039
0003588049.tif 000040
0003588049.tif 000041
0003588049.tif 000042
0003588049.tif 000043
0003588049.tif 000044
0003588049.tif 000045
0003588049.tif 000046
0003588049.tif 000047
0003588049.tif 000048
0003588049.tif 000049
【図面の簡単な説明】
【図１】本発明による検索プロセッサ回路の原理を示す図である。
【図２】本発明で使用する比較器装置を示す図である。
【図３】本発明で文字パターンを比較する方法の原理を示す図である。
【図４】本発明で第２の文字パターンを比較する方法の原理を示す図である。
【図５】本発明で２文字のパターンを比較する方法の原理を示す図である。
【図６】本発明で可変長の反復パターンを比較する方法の原理を示す図である。
【図７】本発明で文字パターンの反復出現の比較に使用するシーケンスコントロール装置を示す図である。
【図８】図２の比較器装置と接続された図７のシーケンスコントロール装置を示す図である。
【図９】本発明でパターンが任意である文字ストリングを比較する方法の原理を示す図である。
【図１０】本発明による検索プロセッサ回路の２進データ分散ツリーの第１実施例を示す図である。
【図１１】図１０の２進データ分散ツリーで図８に示す接続を使用したツリーの実現例を示す図である。
【図１２】本発明による検索プロセッサ回路の２進データ分散ツリーの第２実施例を示す図である。
【図１３】本発明による検索プロセッサ回路の２進データ分散ツリーの第３実施例を示す図である。
【図１４】本発明で使用する結果セレクタの原理を示す図である。
【図１５】本発明で使用する結果セレクタを使用することで処理回路からの結果を収集する原理を示す図である。
【図１６】本発明による検索プロセッサの２進データ分散ツリーの第４実施例を示す図である。
【図１７】本発明による検索プロセッサ回路のデータ分散ツリーの第５実施例を示す図である。
【図１８】本発明の比較が行われた後に、一定文字数の間、比較の肯定結果を維持する方法の原理を示す図である。
【図１９】本発明によるパターンの比較の操作原理を示す図である。
【図２０】本発明で各文書にタグを使用することで、異った文書の管理方法の原理を示す図である。
【図２１】本発明で突合せにおいてヒット数を制限する原理を示す図である。
【図２２】複数の照会を同時に処理するデータ分散ツリーで、リーフノードが複数の処理回路で構成されるツリーを模式的に示す図である。
【図２３】本発明による検索プロセッサ回路で、データ分散ツリーでヒット数の減少を実現する方法の原理を示す図である。
【図２４】本発明による処理回路に含まれる比較器装置の実施例を示す図である。
【図２５】本発明による処理回路に含まれるＤフリップフロップの実施例を示す図である。
【図２６】本発明による処理回路に含まれる遅延装置の実施例を示す図である。
【図２７】本発明による検索プロセッサ回路に含まれる文書管理装置の実施例を示す図である。
【図２８】本発明による検索プロセッサ回路に含まれるルックアップテーブルの実施例を模式的に示す図である。
【図２９】シーケンスコントロール装置と本発明による処理回路の併用の操作原理を示す図である。
【図３０】本発明による処理回路に含まれるシーケンスコントロール装置の実施例を示す図である。
【図３１】本発明による検索プロセッサ回路で結果セレクタを使用して文字ストリングが比較される方法の原理を示す図である。
【図３２】本発明による処理回路に含まれる結果セレクタの実施例を示す図である。
【図３３】本発明による処理回路の実施例を示す図である。
【図３４】図３３の処理回路の入力と出力のブロック図である。
【図３５】８つの処理回路を持つデータツリーの形式でマルチプロセッサ装置を実現した本発明による検索プロセッサ回路の実施例を示す図である。
【図３６】本発明による検索プロセッサ回路で使用されるヒット管理装置を示す図である。
【図３７】図２７に示す文書管理装置及び図３６に示すヒット管理装置を使用して実現された図３６の検索プロセッサ回路を示す図である。
【図３８】比較器装置とシーケンスコントロール装置とを備えたカーネルプロセッサを示す図である。
【図１】
0003588049.tif 000066
【図２】
0003588049.tif 000067
【図３】
0003588049.tif 000068
【図３ａ】
0003588049.tif 000069
【図３ｂ】
0003588049.tif 000070
【図３ｃ】
0003588049.tif 000071
【図３ｄ】
0003588049.tif 000072
【図４】
0003588049.tif 000073
【図５】
0003588049.tif 000074
【図６】
0003588049.tif 000075
【図７】
0003588049.tif 000076
【図８】
0003588049.tif 000077
【図９ａ】
0003588049.tif 000078
【図９ｂ】
0003588049.tif 000079
【図９ｃ】
0003588049.tif 000080
【図１０】
0003588049.tif 000081
【図１１】
0003588049.tif 000082
【図１２】
0003588049.tif 000083
【図１３】
0003588049.tif 000084
【図１４】
0003588049.tif 000085
【図１５】
0003588049.tif 000086
【図１６】
0003588049.tif 000087
【図１７】
0003588049.tif 000088
【図１８】
0003588049.tif 000089
【図１９】
0003588049.tif 000090
【図２０】
0003588049.tif 000091
【図２１】
0003588049.tif 000092
【図２２】
0003588049.tif 000093
【図２３】
0003588049.tif 000094
【図２４】
0003588049.tif 000095
【図２５】
0003588049.tif 000096
【図２６】
0003588049.tif 000097
【図２７】
0003588049.tif 000098
【図２８】
0003588049.tif 000099
【図２９】
0003588049.tif 000100
【図３０】
0003588049.tif 000101
【図３１】
0003588049.tif 000102
【図３２】
0003588049.tif 000103
【図３３】
0003588049.tif 000104
【図３４】
0003588049.tif 000105
【図３５】
0003588049.tif 000106
【図３６】
0003588049.tif 000107
【図３７】
0003588049.tif 000108
【図３８】
0003588049.tif 000109