JP5110162B2 - 検索装置および検索方法 - Google Patents

Description

この出願は、検索装置および検索方法に関し、特に、オートマトン処理技術を適用して与えられた入力文字列であるテキストから任意の文字列であるパターンを検索する検索装置および検索方法に関する。

近年、さまざまな分野で情報量が爆発的に増加している。そして、分野によっては、情報量がギガバイトオーダーからテラバイトオーダーになって、その莫大なデータから所望のデータを短時間で取り出すことが困難となって来ている。

与えられたテキストから任意の種類のパターンを検索するパターンマッチングは、ワープロソフトやデータベースの検索など様々な分野で応用されている。

すなわち、近年、ＸＭＬデータベースをはじめとするパターン照合（検索）処理が必要なアプリケーションの需要が増加傾向にあり、その高速化のためにパターン照合を行うオートマトン照合装置（検索コア）をプロセッサに搭載する手法が提案されている。

そして、従来、このような照合装置を複数有するプロセッサシステムにおいては、１枚の照合すべきテキストを如何にして高速に照合するかが検討されている。

具体的に、従来、照合装置を複数有するプロセッサシステムを使用して、複数文字を一度に照合する方法が提案されている。

さらに、従来、照合装置を複数有するプロセッサシステムを使用して並列処理を実行するために、照合テキストを分割する方法も提案されている。

特開２００５−２４２６７２号公報 特許第２８６５８３１号公報

従来、照合装置を複数有するプロセッサシステムを使用してテキストの照合を行うものが提案されている。

しかしながら、例えば、データベースがはじめから複数のＸＭＬテキスト群により構成されたＸＭＬデータベースシステムの照合（検索）処理において、はじめからパターン照合を行うと各ＸＭＬテキスト間で並列性が高いため、照合装置の搭載数を増やすなどして照合処理を容易に並列処理して高速化することができる。しかしながら、その照合結果を用いたＣＰＵによる後処理の比重は大きくなる。

また、照合処理とＣＰＵの後処理とを並列動作させる場合、そのオーバーヘッドを減らすためのデータの受け渡し方法および制御方式が、検索（照合）システム全体の高速化を実現するのに重要となる。

さらに、各照合結果のテキスト単位の順序関係を保持してＣＰＵで後処理を行う仕組みも必要となる。例えば、ＸＭＬデータベースシステムにおける検索において、もし、ＸＭＬテキストのＣＰＵ処理順序がＸＭＬデータベースで管理されている順序と毎回異なると、検索結果が毎回違った順番に表示され、ユーザにとって使いにくいシステムとなってしまう。

そのため、並列動作により順不同に照合完了した照合結果から、レコード順に後処理可能となった段階で並列に処理するための効率的な仕組みも必要となる。

本出願は、上述した従来および関連技術における課題に鑑み、各照合装置（検索コア）とＣＰＵ処理の並列動作のオーバーヘッドを減らしてデータの受け渡しを行いシステムの高速化を行うことが可能な検索装置および検索方法の提供を目的とする。

第１の実施形態によれば、ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えた検索装置が提供される。前記ＣＰＵは、入力された検索式に従ってオートマトンを作成し、前記スケジューラは、処理対象テキストを、順番付けしたレコード単位で前記各検索コアに分配する。さらに、前記各検索コアは、前記分配された各レコードをそれぞれ並列的にオートマトン照合し、前記ＣＰＵは、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価する。

第２の実施形態によれば、ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えた検索装置を使用した検索方法が提供される。前記ＣＰＵが、入力された検索式に従ってオートマトンを作成し、前記スケジューラが、処理対象テキストを順番付けされたレコード単位で前記各検索コアに分配する。さらに、前記各検索コアが、前記分配された各レコードをそれぞれ並列的に照合処理し、前記ＣＰＵが、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価する。

第３の実施形態によれば、ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えたコンピュータに、前記ＣＰＵに、入力された検索式に従ってオートマトンを作成させる手順と、前記スケジューラに、処理対象テキストを順番付けされたレコード単位で前記各検索コアに分配させる手順と、前記各検索コアに、前記分配された各レコードをそれぞれ並列的に照合処理させる手順と、前記ＣＰＵに、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価させる手順と、を実行させる検索プログラムが提供される。

各実施形態によれば、各照合装置とＣＰＵ処理の並列動作のオーバーヘッドを減らしてデータの受け渡しを行いシステムの高速化を行うことが可能な検索装置および検索方法を提供することができる。

まず、検索装置および検索方法の実施例を詳述する前に、従来技術およびその問題点を、図面を参照して説明する。

図１Ａおよび図１Ｂはオートマトンによるキーワード検索アルゴリズムの一例であるシグマ（Ｓｉｇｍａ）アルゴリズムを説明するための図である。なお、図１Ａおよび図１Ｂは、検索対象の文書から"ｂｌｕｅ"，"ｇｒｅｅｎ"，"ｒｅｄ"および"ｙｅｌｌｏｗ"のキーワードが存在するか否かを検索する例を示している。

まず、図１Ａに示されるように、各キーワード条件に対応したオートマトンを作成する。具体的に、"０"で示す根から、各キーワードの先頭文字"ｂ"、"ｇ"、"ｒ"、"ｙ"に遷移し、さらに、各キーワード列の文字に遷移するオートマトンを作成する。

各キーワード列の最後の文字まで一致すれば、そのキーワード列が検索されたことになる。ここで、例えば、"ｇｒｅｅｎ"のキーワード列には、"ｒｅ"が含まれており、その後に"ｄ"があれば"ｒｅｄ"と一致するので、図１Ａに示されるように、"ｇｒｅｅｎ"の途中から"ｒｅｄ"の"ｄ"に遷移する経路が存在する。

検索は、根から始まり、オートマトン内のキーワードがあれば順次遷移し、キーワードと関係のない文字が読み込まれたら根に戻る。

例えば、図１Ｂに示されるように、"ｂｌａｃｋ"を含む文書が入力されると、"ｂｌｕｅ"の先頭の"ｂ"に遷移し、さらに次の"ｌ"に遷移するが、次が"ａ"であるため根に戻る。

このように、文書内にオートマトンのキーワード列があれば、各キーワード列の最後まで到達してヒット（Ｈｉｔ）情報が出力され、キーワード列が存在することが判明する。ここで、オートマトン検索において、各キーワード列の何番目の文字にあるかをノードまたは「状態」で表す。例えば、根が状態１で、"ｂｌｕｅ"の"ｂ"にいれば状態２で、"ｕ"にいれば状態４と称する。

図２は検索装置の一例を概略的に説明するための図であり、決定性有限オートマトンを用いた検索装置を説明するためのものである。

図２に示されるように、ディスク装置などに格納された検索対象文書１１が流し込まれると、そこから順に文字バイトコード１２が取り出される。以下の説明では、文字バイトコード１２が８ビットで、２５６エントリを形成するものとする。

レジスタに保持された現在の状態（現在の状態を示すデータ）１３と、文字バイトコード１２とを合わせたインデックスを、検索キーワードオートマトンを形成するメモリ１５の入力アドレス１４とする。

入力アドレス１４が入力されたメモリ１５は出力データ１６を出力するが、この出力データには、次の状態１７およびヒット情報（ヒット値）が含まれる。そして、次の状態１７は、現在の状態１３に置き換わることになる。

図３は従来の検索装置における検索シーケンスの一例を概略的に示す図であり、図４は従来の検索方法による処理順を概略的に示す図である。

図３に示されるように、従来の検索装置における検索シーケンスは、例えば、検索式が入力される（３０）と、オートマトンが作成され（３１）、そのオートマトンを使用してレコードの照合（３２ａ，３２ｂ，…）および論理式評価（３３ａ，３３ｂ，…）が繰り返される。

ここで、オートマトンの作成３１，レコードの照合３２ａ，３２ｂ，…および論理式評価３３ａ，３３ｂ，…は、全てＣＰＵ（処理装置）で処理される。

さらに、図４に示されるように、従来の検索方法による処理順は、オートマトンを使用したレコードの照合→照合結果→論理式評価→検索結果をレコード順に行わなければならない。

すなわち、従来の検索方法による処理順は、レコードａの照合（１）を行った後、レコードａの評価（２）を行い、さらに、レコードｂの照合（３）を行った後、レコードｂの評価（４）を行い、そして、レコードｃの照合（５）を行った後、レコードｃの評価（６）を行っていた。そして、検索結果は、レコード順に維持する必要があった。

従来の検索装置および検索方法では、各照合装置とＣＰＵ処理の並列動作のオーバーヘッドが多くなってシステム動作が遅くなり、或いは、検索結果をレコード順に維持しなければならなかった。

以下、検索装置および検索方法の実施例を、添付図面を参照して詳述するが、その前に、一例として、ＸＭＬデータベース検索用アクセラレータ（ＡＣ）について説明する。

検索用データベースソフトウエアは、例えば、ＩＡサーバでは対応困難な大規模ＸＭＬデータベースを必要とするユーザ向けに、高性能プロセッサを搭載した専用サーバマシンに移植され、この専用サーバ向けプロセッサとしては、ＸＭＬレコード照合処理を行うアクセラレータ（ＡＣ）を搭載して処理の高速化の図るようになっている。

まず、本実施形態の検索装置（プロセッサシステム）に適用されるアクセラレータ（スケジューラＳＤおよび検索コア（照合装置）ＳＤ）の概要を説明する。すなわち、アクセラレータの概要、ブロック構成および動作を述べ、さらに、各モジュールの役割を説明する。

本実施形態の検索装置は、例えば、ＸＭＬデータベースにおける文字列の検索を行うものであり、そのデータベースをユーザから与えられた検索式にマッチするデータを検索する処理である。

使用されている検索アルゴリズムでは、例えば、与えられた検索式に対応するオートマトンを作成し、ＸＭＬデータの管理単位であるレコードをそのオートマトンの入力にして流し込むことで照合を行うようになっている。

本実施形態の検索装置における検索処理は大きくレコード照合と論理式評価の２つに分けられる。アクセラレータは、このうちのレコード照合処理を担当する。

図５は本実施形態の検索装置における検索シーケンスの一例を概略的に示す図である。
図５と前述した図３との比較から明らかなように、本実施形態の検索装置における検索シーケンスでは、レコード照合３２ａ，３２ｂ，…と論理式評価３３ａ，３３ｂ，…を全てＣＰＵで処理するのではなく、スケジューラＳＤおよび複数のオートマトン処理装置（例えば、４個の検索コア）ＳＣを有するアクセラレータＡＣにより処理する。

すなわち、スケジューラＳＤは、レコード分配３４ａ，３４ｂ，…を行い、また、検索コアＳＤは、オートマトンの登録３５およびレコード照合３２を行う。このように、アクセラレータＡＣとしてスケジューラＳＤおよび複数の検索コアＳＣを搭載することにより、レコード照合自体を並列処理して高速化し、さらに、論理式評価と並列に動作させるようになっている。

図６は本実施形態の検索方法による処理順を概略的に示す図である。
図６と前述した図４との比較から明らかなように、まず、参照符号６１において、アクセラレータＡＣの４個の検索コアＳＣによりレコードの照合を４つ並列的に処理（１）する。また、参照符号６２において、レコード順を保持する配列と照合結果を保持するバッファという構成にすることで、照合順のレコード維持から開放し、並列処理を実現する。なお、参照符号６３のように、論理式評価は、ＣＰＵによりＸＭＬレコードの順に逐次処理する必要がある。

図７は検索装置の一実施例の要部を示すブロック図である。
図７に示されるように、メインメモリに格納されているＸＭＬデータの各レコード（ＸＭＬデータベースはレコードと呼ばれる単位で保持されている）を各検索コアＳＣが自立的にメインメモリにアクセスして読み出して照合を行い、照合結果であるヒット情報をＣＰＵから高速にアクセスできるＬ２キャッシュまたはワークメモリ（WorkRAM）に置かれる共有データに書き込む。

ＣＰＵとアクセラレータＡＣで共有される制御データは、大きく２つの配列に分かれる。その１つは、レコード情報（レコードの先頭ポインタなど）を保持するレコードソート配列で、他の１つは、照合結果を保持するイベントバッファ配列である。

スケジューラ（スケジューラ回路）ＳＤは、各検索コアＳＣから通知される空状況をモニタして、空いた検索コアにレコード情報を渡し、照合を指示する。ＣＰＵはヒット情報を用いてアクセラレータＡＣと並列に論理式評価を行う。

図８は検索装置の他の実施例の要部を示すブロック図である。
図８に示す実施例は、上述した図７の構成を２つ設けたもので、これを１つのチップとして構成するようになっている。

図８に示されるように、本実施例では、１つの半導体チップ（ＬＳＩ）ＣＨＩＰが、図７に示すＣＰＵ，アクセラレータＡＣおよびＬ２キャッシュを２組有している。すなわち、半導体チップＣＨＩＰは、２つのＣＰＵシステムＰＳを備え、各ＣＰＵシステムＰＳは、ＣＰＵコア、スケジューラＳＤおよび複数の（図では４個の）検索コアＳＣを有するアクセラレータＡＣおよびＬ２キャッシュ（または、Work RAM）を備えている。

なお、図７および図８の構成は、単なる例であり、例えば、１つの半導体チップＣＨＩＰが、ＣＰＵと８個の検索コアＳＣおよびスケジューラＳＤを有するアクセラレータＡＣとを２組、或いは、４組等有するように構成してもよい。

図９は各実施例が適用される検索サーバの一例を概略的に示す図であり、また、図１０は図９の検索サーバを含む検索システムの全体構成を概略的に示す図である。図９および図１０において、参照符号ＳＳは検索サーバ、ＲＳはラックシステム、ＰＢはプロセッサボックス、ＰＭはプロセッサモジュール、ＰＳはプロセッサシステム（検索装置）を示している。

図９では、検索サーバＳＳは、１つのラックシステムＲＳで構成されており、そのラックシステムＲＳは、複数個（例えば、１５個）のプロセッサボックスＰＢを備え、さらに、各プロセッサボックスＰＢは、それぞれ複数枚（例えば、２８枚）のプロセッサモジュールＰＭを備えて構成されている。

また、各プロセッサモジュールＰＭは、それぞれ３つの半導体チップＣＨＩＰと３つのメインメモリを備え、さらに、各半導体チップＣＨＩＰは、各々が１つのＣＰＵと，４つの検索コアＳＣおよびスケジューラＳＤを有するアクセラレータＡＣで構成される２つのプロセッサシステムＰＳを備えて構成されている。

ここで、照合処理は、例えば、各プロセッサシステムＰＳに設けられた各検索コアＳＣにより各レコード単位でランダム（アウトオブオーダ）に実行することができるが、論理式評価は、例えば、ＣＰＵによりＸＭＬデータのレコード順に行うことになる。

なお、各検索コアＳＣには、例えば、それぞれ高速アクセスが可能なキャシュメモリ（一時キャッシュ）が内蔵されており、このキャッシュメモリに対してオートマトンを作成して格納するようになっている。

図１０に示されるように、データ管理部は、ディレクタサーバＤＳおよびストレージサーバＳＴＲで構成され、また、検索処理部は、検索サーバＳＳで構成される。検索サーバＳＳは、例えば、ＬＡＮ等のネットワークＮＥＴを介してディレクタサーバＤＳに繋がれ、例えば、そのディレクタサーバＤＳに繋がれたＸＭＬのような構造化文書のデータが格納されたストレージサーバＳＴＲにおける文書データを処理する。

このように、例えば、図９に示す検索サーバでは、２つのＣＰＵコア×（システムのチップ数）個のプロセッサがＸＭＬデータに含まれる全てのレコードをプロセッサ個数に分割してそれぞれ担当して別々に検索処理を行う。

具体的に、例えば、ＣＰＵが合計２５６個、レコードがレコードＩＤの００００からＦＦＦＦまである場合、レコードＩＤの００００〜００ＦＦ，０１００〜０１ＦＦ，…というように２５６個に分割し、各プロセッサがそれぞれ担当することになる。

また、図１０に示す検索システムにおいて、システムが起動されると、ストレージＳＴＲに格納されているＸＭＬデータベースは、ディレクタサーバＤＳにより分割され、検索サーバＳＳの各プロセッサ（ＣＰＵ）に分配されて対応するメモリ上に格納される。

検索が始まると、まず、検索式が検索サーバＳＳに送られて検索サーバＳＳがオートマトンを作成し、各アクセラレータＡＣに格納される。そして、各ＣＰＵは、自分の担当するＸＭＬデータベースの断片をアクセラレータＡＣに流して照合する。

なお、図９および図１０に示す検索装置および検索システムは単なる例であり、適用されるシステムの規模や要求される検索性能等に応じて様々に変化され得るのはいうまでもない。例えば、より大規模なシステムでは、検索サーバＳＳを複数台のラックシステムＲＳで構成し、また、複数台のディレクタサーバＤＳにより管理を行うといった構成にすることも可能である。

図１１はレコードＩＤからレコードを特定する処理を説明するための図であり、ＸＭＬデータのデータ構造を示すものである。

図１１に示されるように、各レコードは、ＸＭＬデータテーブルＸＤＴ、レコードインデックステーブルＲＩＴおよびメモリデータ情報ＭＤＩと呼ばれる構造体により管理される。

まず、ＸＭＬデータテーブルＸＤＴには、ＸＭＬデータ全体の情報が収められており、レコードインデックステーブルＲＩＴへのポインタが含まれている。

レコードインデックステーブルＲＩＴは、メモリデータ情報ＭＤＩへのポインタ配列となっており、レコードＩＤの上位２バイトにより要素が識別される。

メモリデータ情報ＭＤＩは、各レコードのレコード情報をメンバに持つ構造体配列であり、レコードＩＤの下位２バイトにより要素が識別される。なお、レコード情報には、アクセラレータＡＣで照合を行う単位となるレコードへのポインタが含まれている。

なお、図６を参照して述べたように、照合処理は各レコード単位でランダム（アウトオブオーダ）に実行可能であるが、論理式評価はこのＸＭＬデータのレコード順に行う必要がある。

図１２は各モジュールの役割を説明するための図である。
図１２に示されるように、モジュールは、大きくソフトとハードに分類される。さらに、ソフトは、アプリ（アプリケーションプログラム）およびドライバに分類され、また、ハードは、スケジューラＳＤおよび検索コアＳＣに分類される。

アプリ（Sigma Evaluation：シグマ評価)は、論理式評価を行い、バッファフルを検出したら、シグマバッファフルを呼ぶ。

ドライバは、シグマ検索（Sigma Search）およびシグマバッファフル（Sigma Buffer Full）に分類される。シグマ検索は、ＸＭＬのインデックスを参照して、レコードへのポインタをインオーダで取り出し、ソート配列に登録する。適当なタイミング（ポーリング）でバッファ状態を見て、論理式評価関数を起動する。また、論理式評価関数が終了したら、そこまでのソート配列エントリをフラッシュする。そして、適当なタイミング（論理式評価関数が終了したら評価終了レコード個数をカウントし、閾値を設けて起動など）でレコード情報をソート配列に補充する。

シグマバッファフルは、論理式評価がイベントバッファ終端に到達したら、呼ばれる。そして、イベントバッファフラッシュを行って、現在論理式評価中のレコードの照合結果が終了または次のイベントバッファがフルになるまで待って、終了する。

スケジューラＳＤは、アイドル状態の検索コアＳＣがあれば、ソート配列に登録された照合未開始の先頭のレコード情報（ポインタなど）を検索コアＳＣに分配して、検索開始を指示する。

検索コアＳＣは、レコード情報が与えられたら、メモリからレコードの文字列を読み込んで照合を行う。ヒットしたらイベントバッファに書き込む。イベントバッファを跨ぐなどがあった場合は、バッファ状態フラグを適切に変更する。そして、照合が終了したら、スケジューラＳＤにアイドル状態を通知して停止する。イベントバッファフルなどがあったらストールして、イベントバッファがフラッシュされるのを待つ。

次に、アクセラレータＡＣのドライバソフトウエアとアプリケーションの関係について説明する。

図１３は各ＡＰＩ関数と呼び出し手続きを説明するための図であり、アプリケーション、ＡＰＩ関数、ドライバ（アクセラレータライブラリ１３８）およびアクセラレータＡＣの関係を示している。

図１３に示されるように、まず、検索式が与えられると、アプリケーション側で対応するオートマトンを作成（１３１）する。さらに、シグマロックハンドル（Sigma Alloc Handle）関数およびシグマコンフィグ（Sigma Config）関数を呼んで、アクセラレータＡＣの初期設定（作業域取得１３２および環境設定１３３）を行う。なお、シグマコンフィグ関数は、システム起動時のみとしてもよい。

そして、シグマ登録（Sigma Registration）関数を呼んで作成したオートマトンをアクセラレータＡＣに登録（１３４）する。さらに、シグマ検索（Sigma Search）関数を呼んで検索処理の本体を開始（照合実行を起動：１３５）する。このシグマ検索関数で検索の全体が実行され、アプリケーションは終了を待つ。

最後に，シグマフリーハンドル（Sigma Free Handle）関数を呼んで一連の検索処理が終了（作業域を解放１３６）する。なお、シグマ検索関数は、レコードの照合をアクセラレータＡＣに指示し、論理式評価の準備ができたレコードを、シグマ評価（Sigma Evaluation）関数を呼んで論理式評価（１３７）を行う。また、シグマバッファフル（Sigma Buffer Full）関数は、照合結果を保持するイベントバッファが切り替わる際に呼ばれる。

次に、本アクセラレータＡＣの制御方式について説明する。
はじめに、制御データであるレコードソート配列とイベントバッファ配列について、詳細を述べる。さらに、アクセラレータの各動作について、主な動作である検索動作（Sigma Search関数に対応）について述べ、全体制御の遷移概要について述べる。そして、残りのオートマトン登録動作（Sigma Registration関数に対応）および環境設定動作（Sigma Config関数に対応）について述べる。

図１４は制御データの詳細なデータ構造を示す図である。
まず、図１４に示されるように、制御データは、各レコードの情報を管理するレコードソート配列と、検索コアによる照合結果を書き込むイベントバッファ配列との２つに大きく分かれている。

レコードソート配列の各行には、ＸＭＬデータの各レコードがＸＭＬデータのインデックス順に格納され、照合と論理式評価が終了したレコードの行から解放され、そして、行が終端まで使用されたら循環して先頭に戻って使用される。

ここで、各項目は、次の意味を有する。
・照合状態フラグ：そのレコードの検索コアによる照合状態が記録され、論理式評価可能の判定、および、バッファフラッシュ時の論理式評価再開可能の判定に使用される。なお、フラグの意味は、次の通りである。

０：照合未終了かつ照合がイベントバッファを跨いでいない。
１：照合が１つでもイベントバッファを跨いだ。
２：照合が終了した。
・検索コア番号：そのレコードを照合し、または、照合した検索コアの番号で、バッファフラッシュ時に使用される。

・＊レコード：ＸＭＬデータのレコードの先頭アドレスへのポインタで、照合開始時に検索コアに渡されて使用される。なお、以下において、「＊」はアドレスを示している。

・有効フラグ：その行が使用されているかどうかのフラグで、スケジューラがその行を自分のバッファ内に持ってきたときに有効かどうかのチェックに使用される。

０：未使用。
１：使用。
・レコードＩＤ（Record ID）：論理式評価で使用され、本発明の制御には直接関与しない。

・＊イベントバッファ：照合結果が格納されているイベントバッファ領域へのポインタで、論理式評価で使用される。

なお、「＊登録ｔｏｐ」および「＊登録ｂｏｔｔｏｍ」の２つのポインタ変数は、現在使用されている行の先頭アドレスおよび終端アドレスを指し示し、ドライバ関数シグマ検索（Sigma Search）により保持される。次検索ｔｏｐポインタ変数は、現在登録されているレコードの中でまだ照合開始していない行の先頭アドレスを示し、スケジューラ内レジスタに保持されている。

イベントバッファ配列には、検索コアによる照合結果が書き込まれる。なお、図１４は、検索コアが４個（検索コア０，１，２，３：ＳＣ）で、各検索コアに割り当てられた領域がイベントバッファ４枚（Ａ，Ｂ，Ｃ，Ｄ）の場合を示している。

各イベントバッファの終端エントリには、次イベントバッファ（例えば、ＡならばＢ、ＢならばＣ、…）へのポインタが予め書き込まれている。そして、例えば、図１４における検索コア０のイベントバッファに示されるように、検索コアおよび論理式評価関数（Sigma Evaluation：シグマ評価）が、それぞれ自分で次のバッファに移行できるようになっている。

図１４において、荒い点線ＲＥＴは、論理式評価で現在参照する最後のエントリの位置を示し、また、細かい点線ＷＥＴは、照合コアで現在照合結果を書き込んでいる最後のエントリＷＥＴを示す。さらに、太線ＮＲは、そのレコードがまだ照合終了していないことを示す。なお、バッファ枚数は、実際には２枚を想定している。

この他に制御に必要なデータとしてバッファ距離がある。これは、検索コアと論理式評価で現在使用されているイベントバッファ間の距離を示し、例えば、図１４の検索コア０では『４』が書き込まれている。このデータは、検索コア内部のレジスタに格納されており、検索コアがイベントバッファを跨ぐごとに『１』を加え（＋１）また、イベントバッファがフラッシュされるごとに『１』を引く（−１）。

上記のデータは、検索コアの動作のみでなくバッファフラッシュ時の動作判定にドライバ（ＣＰＵ側）からも参照されるため、そのコピーがスケジューラ（ＳＤ）に置かれたマップＩＯレジスタにもコピーされる（或いは、検索コアのバッファ距離レジスタがメモリマップ上に置かれる）。

図１５は共有データの構造（制御データの配置）を説明するための図である。
図１５に示されるように、レコードソート配列およびイベントバッファ配列は、Ｌ２キャッシュまたはワークＲＡＭ（ＷｏｒｋＲＡＭ）領域に置かれる。

バッファ距離のオリジナルは、検索コア（ＳＣ）内部に置かれ、バッファ距離のコピーは、スケジューラ（ＳＤ）に置かれる。次照合ｔｏｐは、スケジューラ内部におかれる。また、図１５では、後で検索動作を説明するためのスケジューラと検索コアＳＣ内にあるレジスタも描かれている。

ここで、スケジューラは、次の意味を持っている。
・アイドル（idle）フラグ：各検索コアの状態を示す。
０：アイドル状態。
１：ビジー状態。
・＊次検索ｔｏｐ：次に照合するレコード情報が格納されているソート配列のエントリアドレスを指すレジスタ。

・レコード情報バッファ：レコードソート配列のエントリを一時的に格納するバッファであり、検索コアの個数分だけある。＊次照合ｔｏｐからバッファ数分だけ持ってくるが、もし、ソート配列の有効フラグが『０』であれば破棄して、＊次照合ｔｏｐは適当なサイクル後に再度読み込む。

・バッファ距離コピー：検索コアのバッファ距離のコピーを置く。
・フラッシュ完了フラグ：イベントバッファフラッシュの待ち合わせに使う。
・＊登録ｂｏｔｔｏｍコピー：＊登録ｂｏｔｔｏｍ変数のコピーを保持する。スケジューラがレコード情報をバッファリングする際に、次照合ｔｏｐが追い越さないために使用する。

また、検索コアは、次の意味を持っている。
・文字バッファ：照合するレコードを一時的に格納する数十バイト程度のバッファで、検索コアは、ここから１文字ずつ使用し、オートマトンを遷移させて照合する。

・＊イベントバッファ：各照合コアがレコード照合のヒット情報を書き込む先のイベントバッファへのポインタである。

・バッファ距離：論理式評価と照合の同期に使うもので、その検索コアのイベントバッファにおける現在の論理式評価読み出し位置と照合結果書き込み位置のバッファ枚数単位の距離である。なお、初期値は『０』で、書き込みは検索コアのみが行う。照合結果書き込み時に現在のバッファ終端に到達したタイミングで『１』を加え（＋１）また、イベントバッファフラッシュを指示されると『１』を引く（−１）。

図１６および図１７は、各データの書き込みおよび読み出しの関係を説明するための図である。

図１６に示されるように、まず、各データの書き込みに関して、シグマ検索（Sigma Search）からレコードソート配列への書き込みが多いが、これは、シグマ検索でＸＭＬデータインデックスを参照してレコード情報を取り出し、ソート配列に格納するためである。検索コアからのレコードソート配列への書き込みは、レコード照合開始時に決まるレコードの管理情報であり、また、検索コアからイベントバッファ配列への書き込みは、照合ヒット情報である。

また、読み出しに関して、シグマ検索はソート配列の状態フラグを見るが、これは、シグマ評価（Sigma Evaluation）起動可能判定のためである。シグマ評価は、論理式評価開始に必要となるレコード管理情報をソート配列から読み出し、論理式評価のためのヒット情報をイベントバッファから読み出す。

シグマバッファフル（Sigma Buffer Full）は、バッファフル時の制御に必要となる情報（レコードＩＤ、および、*イベントバッファ）をソート配列から読み込む。スケジューラは、検索コアが照合を開始するための情報（*レコード）をソート配列から取り出す。

次に、本アクセラレータの主な処理である検索動作（シグマ検索関数が呼ばれてから終了するまで）について述べる。

まず、イベントバッファの制御（イベントバッファの読み書きの同期方法）について説明する。

図１６および図１７に示されるように、イベントバッファは、照合結果が格納されるバッファであり、照合ヒット時には検索コアから直接イベントバッファに書き込まれ、論理式評価関数で読み出されて使用される。

イベントバッファは、検索コアごとに領域が割り当てられており、その領域を２枚以上のイベントバッファに分割して使用する。なお、領域は有限であるから、いずれバッファをフラッシュして再利用する必要がある。このフラッシュには、シグマバッファフル関数を使用して同期を取るようになっている。

ここで、必要な条件判定は、次の通りである。
A) シグマ評価関数の起動可能条件判定。
B) シグマバッファフル関数の終了可能条件判定（シグマ評価の再開）。
C) 検索コアの照合結果を書き込み、未追い越し判定。
なお、イベントバッファを跨いだ情報だけではうまくいかない例としては、照合がイベントバッファを跨いだ情報と、そのレコードの照合が終了した情報の２つがないとうまくいかない。例えば、バッファ距離のみしかなくてそれが２以上だと、次バッファの論理式評価継続可とした場合に、イベントバッファを２つ跨いで終了するようなレコード（イベントバッファを２枚半程度使うレコード）が照合終了し、その検索コアでは、そのレコードの照合以降はアイドル状態になっているとすると、デッドロックしてしまう。

そこで、本実施例の制御方法では、上記の処理を行うときに、前述した状態フラグ（制御データ）とバッファ距離（検索コア内レジスタ、および、ＩＯレジスタへのコピー）を使用する。

ここで、各変数の操作ルールを説明する。
まず、バッファ距離に関しては、次の通りである。
・照合がバッファ終端に到達したら、『１』を加える（＋１）
・シグマバッファフルから通知を受けたら、『１』を引く（−１）。
また、状態フラグに関しては、次の通りである。
・初期状態は『０』
・照合がイベントバッファを跨いだら『１』とする
・照合が終了したら『２』とする
ここで、必要な条件判定方法は、次の通りである。
A) シグマ評価関数の起動可能条件判定。
・ソート配列の先頭からレコード状態フラグが『０』以外なら可。
B) シグマバッファフル関数の終了可能条件判定（シグマ評価の再開）。
・バッファ距離が『２』以上であれば可（フラッシュ完了前）。
・バッファ距離が『１』以上であれば可（フラッシュ完了後）。
・レコード状態フラグが『２』であれば可。
C) 検索コアの照合結果を書き込み、未追い越し判定。
・バッファ距離がイベントバッファ枚数（図１６の例では４）未満なら可。
次に、検索動作の２つの例を用いて説明する。なお、その１つの動作は、イベントバッファフラッシュが起きていない通常時の例であり、他の１つは、イベントバッファがフラッシュされる場合の例である。

図１８Ａ〜図１８Ｃはスケジューラの動作を説明するための図であり、検索動作時の時間経過による動作を示すものである。

図１８Ａ〜図１８Ｃにおいて、図中の上部にあるブロック（ＣＰＵ，Ｌ２キャッシュ（または、Work RAM），アクセラレータ，メモリ）は、ハードウエアのカテゴリを示し、それらの中にある小さなブロックが動作実体を示す。なお、説明を簡略化するために、図１８Ａ〜図１８Ｃでは、２つの検索コアＳＣ（検索コア０および１）の構成を示し、また、レコードは、Ａ，Ｂ，Ｃ，…の順になっているものとする。

すなわち、条件は、検索コアが２個、および、レコード順がＡ，Ｂ，Ｃ，…で、状況概要は、レコードＢ照合が終了しても、レコードＡ照合未終了のため評価待ち、並びに、レコードＣ照合が終了しても、レコードＤ照合未終了のため評価待ちとする。

次に、図１８Ａ〜図１８Ｃ中の左側に示す(1)〜(6)の各時間範囲における各動作実体の動作について説明する。

時間範囲 (1) において
・シグマ検索（Sigma Search）：シグマ検索関数が開始すると、メモリにあるＸＭＬデータのレコードインデックスを参照して行き、レコード情報を取り出してソート配列のエントリ個数分を取り込む。登録ｔｏｐ，ｂｏｔｔｏｍポインタを適切に変更する。なお、この段階では、登録ｔｏｐは１つ目のエントリ、登録ｂｏｔｔｏｍは一番下のエントリを指す。そして、登録ｂｏｔｔｏｍをスケジューラのマップＩＯレジスタの登録ｂｏｔｔｏｍにコピーする。

・シグマ評価（Sigma Evaluation）：存在していない。
・スケジューラ：アイドルモードである。
・検索コア：アイドルモードである。

時間範囲 (2) において
・シグマ検索：スケジューラを検索モードに変更し、論理式評価待ちを開始する。登録ｔｏｐポインタが指すソート配列エントリ（レコードＡのレコード情報が格納されている）のレコード状態フラグをポーリングする。この時点では、フラグが『０』であるためなにもしない。

・シグマ評価：存在していない。
・スケジューラ：検索モードに移行し、照合ｔｏｐレジスタが示すソート配列エントリから２つのレコード情報を、自回路内のレコード情報バッファ（検索コアの個数分ある）に格納する。照合ｔｏｐレジスタを『＋２』する（ポインタを２エントリ先に進める）。

さらに、各検索コアのアイドルフラグを見て、検索コア０および１がアイドル状態であるため、レコード情報（レコードへのポインタ、および、ソート配列エントリへのポインタ）を渡して照合開始を指示してアイドルフラグをビジー状態にセットする。そして、再度上記と同様にして、レコード情報を自回路内にバッファリングする。

次に、再度、アイドルフラグレジスタをモニタして、次レコードの分配可能を検索コアと待ち合わせる。この時点ではビジー状態なので、アイドル状態になるのを待つことになる。

・検索コア：各検索コア０および１は、スケジューラから渡されたレコードへのポインタから照合を開始する。まず、渡された＊ソート配列が指すエントリの検索コア番号と＊イベントバッファに対して、それぞれ自分のコア番号と自回路内にある＊イベントバッファレジスタの内容を書き込む。さらに、メモリから＊レコードから連続する数十バイト（文字バッファのサイズ）のデータ（文字バッファサイズの文字列）を自回路内の文字バッファに取り込む。

そして、文字バッファから１文字ずつ用いて、自コア内に予め格納されているオートマトンを遷移させる。もし、オートマトンがヒット状態であれば、自コア内の＊イベントバッファレジスタが指すイベントバッファエントリにヒット情報を書き込んで、＊イベントバッファレジスタを『＋１』する。ヒットするごとに同様に処理する。なお、ヒット時の書き込みモードによっては、上書き、或いは、書き込まないなどの動作をすることもある。

ここで、文字バッファが空になる前に次の数十バイトを同様に取り込み、検索コアがストールしないようにする。いずれレコードの終端に到着するが、これはレコード文字列を見ることにより検索コアが自分で判別する。

終端に到着したらスケジューラにアイドル状態を通知し（スケジューラのアイドルフラグにアイドル状態を書きこみ）、同時に、ソート配列のレコード状態フラグを『２』（レコード照合終了）にする。この時点では、検索コア０および１のどちらもまだ照合終了していないので、レコードの読み込みとオートマトン遷移を続ける。

時間範囲 (3) において
・シグマ検索：(2)のポーリングを続けている。この時点で、レコードＢは照合を終了しているが、先頭レコードＡがまだ照合未終了のためポーリングを続ける。

・シグマ評価：存在していない。
・スケジューラ：検索コアのアイドルフラグを毎サイクル見ている。暫くすると検索コア１のアイドルフラグが『０（アイドル状態）』となるので、検索コアに３つ目のレコードＣのレコード情報を渡して照合を指示する。さらに、(2)と同様に、検索コア１のアイドルフラグを『１（ビジー状態）』にして、１レコード分のレコード情報をソート配列から再度バッファリングする。

・検索コア：検索コア０および１は、文字列読み込みとオートマトン遷移を続け、ヒットがあればイベントバッファに書き込む。暫くすると、検索コア１は照合終了するのでスケジューラのアイドルフラグを『０』（アイドル状態）に変更し、スケジューラから渡された＊ソート配列が指すエントリのレコード状態フラグに『２』を書き込む。

時間範囲 (4) において
・シグマ検索：(2)のポーリングを続けている。この時点でレコードＡのレコード状態フラグが『２』となったので、論理式評価が可能。次のエントリのフラグも見て行き、２番目のエントリまでが論理式評価可能なので、レコードＡとレコードＢを論理式評価するようにシグマ評価を起動する（レコードＡのソート配列エントリのアドレスと評価可能レコード数２を引数として渡す）。

・シグマ評価：レコードＡとレコードＢを論理式評価し、ソート配列の＊イベントバッファを用いてイベントバッファから照合結果を読んで論理式評価する。レコードＩＤ（Record ID）は処理に使用されるが、本アクセラレータには関係しない。この時点では、論理式評価は終了していない。

・スケジューラ：(3)と同様の動作となる。ここでは検索コア０のレコードＡが照合終了するので、次のレコードＤを検索コア０に分配し照合を指示する。(3)と同様に、次レコードの分配を待つ。

・検索コア：(3)と同様の動作となる。検索コア０は次レコードＤが割り当てられて照合を開始し、また、検索コア１はレコードＣの照合を継続する。

時間範囲 (5) において
・シグマ検索：なにもしない。
・シグマ評価：論理式評価を継続する。
・スケジューラ：(3)と同様の動作となる。ここでは検索コア０のレコードＤが照合終了するので、次のレコードＥを検索コア０に分配し照合を指示する。(3)と同様に、次レコードの分配を待つ。

・検索コア：(3)と同様の動作となる。検索コア０は次レコードＥが割り当てられて照合を開始し、また、検索コア１はレコードＣの照合を継続する。

時間範囲 (6) において
・シグマ検索：シグマ評価から処理が戻る。ソート配列のレコードＡおよびレコードＢが格納されていたエントリは不要となったので、(1)と同様にして、ＸＭＬデータインデックスを参照して、続きの２つの新しいレコード情報をソート配列に格納する。検索ｔｏｐを『＋２』、検索ｂｏｔｔｏｍを『＋２』する（配列最終要素の次は先頭に循環する）。

検索ｂｏｔｔｏｍをスケジューラのマップレジスタにコピーする。再度、論理式評価可能待ちでレコードＣの状態フラグをポーリングするが、『２』であるので、この時点で直ぐに論理式評価が可能となる。(4)と同様にして、レコードＣおよびＤを指定して、シグマ評価を起動する。

・シグマ評価：レコードＡおよびＢの論理式評価を継続して終了する。その後、再度呼び出され、レコードＣおよびＤの論理式評価を開始する。

・スケジューラ：(3)と同様の動作となる。ここでは検索コア１のレコードＣが照合終了するので、次のレコードＦを検索コア１に分配して照合を指示する。(3)と同様に、次レコードの分配を待つ。

・検索コア：(3)と同様の動作となる。検索コア１は次レコードＦが割り当てられて照合を開始し、また、検索コア０はレコードＥの照合を継続する。

ここで、図１８Ａ〜図１８Ｃにおけるシグマ検索の点線で囲まれた部分ＳＳＲ、並びに、スケジューラの点線で囲まれた部分ＳＤＲが繰り返される。このように、照合については、レコード順に関係なく先行するレコードが終了していなくても、検索コアが空くと直ぐに次のレコードが開始される（矢印ＬＢ参照）。しかしながら、論理式評価は、レコード順に待ち合わせる（矢印ＬＲ参照）必要がある。この制御を，ソート配列で行うようになっている。

また、図１８Ａ〜図１８Ｃに示す実施例では、論理式評価の可能か否かの判定に用いる情報（＊登録ｔｏｐの状態フラグ）の待ち合わせにポーリングを用いた場合を説明したが、ハードウエアの割り込みも可能なようにすることもできるのはいうまでもない。

図１９Ａ〜図１９Ｃはイベントバッファ制御の課題を説明するための図であり、イベントバッファが４枚の場合を示している。すなわち、イベントバッファは有限であるため、レコードバッファの照合終了を示すフラグだけでは制御することができない。なお、図１９Ａ〜図１９Ｃにおいて、参照符号ＳＰは照合結果始点、ＥＰは照合結果終点、ＷＰは照合結果書き込み位置、そして、ＲＰは照合結果読み出し位置を示している。

まず、問題がない場合は、図１９Ａに示されるように、照合結果が１枚のバッファ内に全て収まっている場合である。

次に、問題がある第１の場合としては、図１９Ｂに示されるように、照合結果が全てのイベントバッファより大きい場合であり、論理式評価がはじまらず、詰まってしまうことになる。

さらに、問題がある第２の場合としては、図１９Ｃに示されるように、書き込みが読み出しを追い抜いてしまう場合であり、照合と論理式評価の同期を取ることが必要となる。

図２０Ａ〜図２０Ｃは各データの書き込みおよび読み出しの関係を説明するための図であり、各バッファ単位で論理式評価を開始してフラッシュを管理する様子を示している。

まず、図１９Ｂに示す照合結果が全てノイベントバッファより大きい場合（問題がある第１の場合）には、図２０ＡのＰＰ１に示されるように、照合がイベントバッファの終端に到達した情報を照合情報フラグに付加し、到着時点で論理式評価可能と判定する。

次に、図１９Ｃに示す書き込みが読み出しを追い抜いてしまう場合（問題がある第２の場合）には、図２０ＢのＰＰ２に示されるように、照合と論理式評価の距離を保持するレジスタを追加し、照合の追い抜きをバッファ単位で防止する。

さらに、図２０ＣのＰＰ３に示されるように、論理式評価がイベントバッファ終端に到着したら、そのバッファをフラッシュするようにしてもよい。

なお、或る検索コアに対して割り当てられたレコード照合結果（論理式評価）を記録したイベントバッファ（ローカルメモリ：例えば、Ｌ２キャシュメモリ）の終端ＥＰには、その次のイベントバッファ（記憶領域）の先頭へのポインタ（ＳＰ’）が記載されている。

図２１はイベントバッファ制御用情報を説明するための図であり、前述した図１５に対応するものである。

図２１に示されるように、論理式評価と照合の同期に使うバッファ距離は、スケジューラＳＤにおけるバッファ距離レジスタＰＱ１に格納され、イベントバッファフラッシュの待ち合わせに使うフラッシュ完了フラグは、スケジューラＳＤにおけるフラッシュ完了フラグＰＱ２に格納される。

また、各検索コアＳＣ（検索コア０〜３）のアイドル状態（空いている状態）は、スケジューラＳＤに設けられたレジスタＰＱ３に保持され、スケジューラＳＤが空いている検索コアを判断できるようになっている。

なお、共有データにおける複数のレコードを管理する管理情報は、スケジューラＳＤに設けられたバッファＰＱ４に一時的に保持されるようになっている。

さらに、照合状態フラグは、レコードの検索コアによる照合状態が記録され、論理式評価可能の判定およびバッファフラッシュ時の論理式評価再開可能の判定に使用されるもので、例えば、Ｌ２キャッシュのＰＱ５に格納される。なお、検索コア番号は、レコードを照合し、または、照合した検索コアの番号でバッファフラッシュ時に使用されるもので、例えば、Ｌ２キャッシュのＰＱ６に格納される。

図２２Ａ〜図２２Ｃはイベントバッファフラッシュ時の動作例を説明するための図であり、イベントバッファフラッシュ時の時間経過による動作を示すものである。

図１８Ａ〜図１８Ｃを参照して述べた例では、イベントバッファサイズが無限にあるケースを想定して説明した。しかしながら、実際には、イベントバッファサイズは有限であるため、イベントバッファを２枚以上に分割して切り替えながら使うことになる。ここでは、その場合の例を説明する。

なお、説明を簡略化するために、図２２Ａ〜図２２Ｃでは、検索コアが１個でイベントバッファが２枚の構成を示し、また、あるレコードＡの照合結果のサイズが合計２枚以上のイベントバッファサイズとなる場合を示す。

すなわち、条件は、検索コアが１個、および、イベントバッファが２枚で、状況概要は、レコードＡの照合がバッファ跨いだので即評価可能であり、１度目のバッファフラッシュ時は、レコードＡの照合が２つ目のバッファ跨いだので即終了可能であり、そして、２度目バッファフラッシュ時は、レコードＡ照合が３つ目のバッファ跨いでいないので待ち合わせとする。

次に、図２２Ａ〜図２２Ｃ中の左側に示す(1)〜(7)の各時間範囲における各動作実体の動作について説明する。

時間範囲 (1) において
・シグマ検索：レコードＡの論理式評価可能を、レコードＡの状態フラグをポーリングして待っている。この段階では、ポーリング中である。

・シグマ評価：存在していない。
・シグマバッファフル：存在していない。
・スケジューラ：次レコードＢの分配可能を、検索コアのアイドル（idle）フラグを見ることで待つ。この段階では、『１』（ビジー状態）を示したままであるため待ち続けることになる。

・検索コア：レコードＡの照合中であり、通常時と同様に、メモリからレコード文字列を持ってきてオートマトンを遷移する。そして、ヒットしたらイベントバッファにヒット情報を書き込む。ヒット情報を書き込んでいるうちに、書き込み先のアドレスが１枚目のイベントバッファの終端に到着したら、ソート配列の状態フラグに『１』を書き込む（イベントバッファ跨ぎを通知する）。そして、バッファ距離レジスタを『＋１』する。

時間範囲 (2) において
・シグマ検索：状態フラグをポーリングすると、状態フラグが『１』となっているので、レコードＡを論理式評価するように、シグマ評価を呼び出す。

・シグマ評価：渡されたレコードＡを、通常時と同様に、論理式評価を開始する。このとき、イベントバッファからヒット情報を参照する。

・シグマバッファフル：存在していない。
・スケジューラ：(1)と同じで、変化なし。
・検索コア：２枚目のイベントバッファにヒット情報を書き出す。他は、(1)と同じである。

時間範囲 (3) において
・シグマ検索：シグマ評価の終了を待つ。
・シグマ評価：(2)の論理式評価を継続中である。
・シグマバッファフル：存在していない。
・スケジューラ：(2)と同じ。変化なし。

・検索コア：(1)と同様にヒット情報を書き込んでいるうちに、書き込み先のアドレスが１枚目のイベントバッファの終端に到着。今回は既に状態フラグを『１』にしてあるので、特に外部に通知はしない。バッファ距離レジスタを『＋１』する。このときバッファ距離レジスタ＝２で、イベントバッファ枚数（２枚）未満でないので、１枚目のイベントバッファが論理式評価で消費されて終わっていないためストールする。

時間範囲 (4) において
・シグマ検索：(3)と同じくシグマ評価の終了を待つ。
・シグマ評価：論理式評価中に参照するイベントバッファのヒット情報の内容がバッファ終端を示している（イベントバッファの終端には、終端を示すビットパターンと次イベントバッファへのポインタが予め書き込まれている）ため、シグマバッファフルを呼び出す。引数にはこのレコードのソート配列エントリへのポインタを渡す。しばらくすると、シグマバッファフルが終了し、次イベントバッファの先頭から論理式評価を再開する。

・シグマバッファフル：渡されたソート配列エントリへのポインタから、検索コア番号を割り出す。そして対応するフラッシュ完了フラグが『０』であるか否かを確認する。『０』なのでフラグに『１』を書き込み、バッファ距離コピーを獲得しておく。

また、検索コア番号をスケジューラに渡し、その検索コアのイベントバッファフラッシュを指示する。（この例では、検索コアが１つしかないため検索コア番号を指定する必要はないが、一般のケースでは必要となる。）

次に、先に獲得しておいたバッファ距離コピー（ＩＯレジスタ）が２以上、または、状態フラグが『２』であるか否かを判定する。バッファ距離コピーが『２』なのですぐに関数が終了可能である。論理式評価再開可能の待ち合わせを行う。

・スケジューラ：フラッシュ指示と検索コア番号０が与えられたので、対応する検索コア０にフラッシュ指示する。

・検索コア：ストール中にフラッシュ指示命令が与えられたので、バッファ距離レジスタを『−１』し、その内容をスケジューラのバッファ距離レジスタのコピーに上書きする。そして、フラッシュ完了フラグを『０』にする。さらに、バッファ距離が『１』となったので照合を再開する。

時間範囲 (5) において
・シグマ検索：(4)と同じくシグマバッファフルの終了を待つ。
・シグマ評価：(4)と同様にイベントバッファ終端に到着したので、再度シグマバッファフルを呼び出す。その後は、シグマバッファフルの終了を待つ。

・シグマバッファフル：スケジューラへの指示までは(4)と同じ。もしこの時点でフラッシュ完了フラグが『１』なら待ち合わせる（１回前のフラッシュ。この場合は関係ない）。次に、予め保持しておいたバッファ距離が『１』なので、フラッシュ完了フラグとバッファ距離をポーリングして待ち合わせ。（フラッシュ完了フラグ＝０かつ（バッファ距離≧１または状態フラグ＝２））となるのを待つ。

・スケジューラ：(4)と同様にフラッシュを指示する。
・検索コア：(4)と同様に、フラッシュし、照合を継続する。

時間範囲 (6) において
・シグマ検索：(5)と同じく、シグマ評価の終了を待つ。
・シグマ評価：シグマバッファフルの終了を待つ。しばらくすると、シグマバッファフルが終了し、次イベントバッファの先頭から論理式評価を再開する。

・シグマバッファフル：(5)に引き続きポーリングを行い、しばらくすると、バッファ距離＝１であるが、状態フラグ＝２となるので終了する。

・スケジューラ：次レコードの分配を待ち、検索コア０からアイドル状態が通知されるので次のレコードＢを分配する。レコード情報バッファを再度充填して、また次レコードの分配待ち状態になる。

・検索コア：レコード照合が終了し、それをソート配列とスケジューラに通知する。次のレコードＢが渡されて、照合を開始する。

時間範囲 (7) において
・シグマ検索：(6)に引き続き、シグマ評価の終了を待つ。しばらくすると終了するので、空いたソート配列のエントリに続きのレコード情報を充填し、論理式評価可能を待つ。この時点では、レコードＢが照合終了していないので待つことになる。

・シグマ評価：論理式評価が終了し、関数が終了する。
・シグマバッファフル：存在していない。
・スケジューラ：(6)に引き続き次レコードの分配を待つ。
・検索コア：(6)に引き続きレコードＢを照合する。

以上、実施例における動作を説明してきたが、次に、各関数の検索動作を、フローチャートを参照して説明する。

図２３はＡＰＩ関数と呼び出し手続きをフローチャートと関連付けて説明するための図である。図２３において、左側部の図は、図５に示す検索シーケンスを書き換えたものに相当し、また、中央の図は、各ＡＰＩ関数と呼び出し手続きを説明するために使用した図１３と同様のものである。

図２３に示されるように、本実施例が対象とする動作は、検索シーケンスにおけるレコード照合処理，照合結果処理，論理式評価処理および検索結果処理に対応する検索動作である。ここで、検索動作（図２３中で太線で囲んだ部分）において、照合実行起動１３５は、図２４に示すシグマ検索処理に対応し、論理式評価１３７は、図２７に示すシグマ評価処理に対応し、そして、アクセラレータライブラリ１３８内のバッファフル処理１３９は、図２８に示すシグマバッファフル処理に対応する。

以下、各フローチャートを参照して、シグマ検索処理，シグマ評価処理およびシグマバッファフル処理を説明する。

図２４はシグマ検索処理の一例を示すフローチャートである。ここで、シグマ検索（Sigma Search）処理は、メインルーチンであり、検索動作をはじめるための処理（関数）である。

シグマ検索処理を介しすると、まず、ステップＳＴ１において、はじめにＸＭＬインデックスを参照して（なめて）、ソート配列にレコード情報を格納し、ステップＳＴ２に進む。

ステップＳＴ２では、アクセラレータを照合モードに変更し、ステップＳＴ３に進んで、ポーリングを行う。ここで、ポーリングでは、次評価レコードエントリの状態フラグをポーリングする。

さらに、論理式評価可能となったら、ステップＳＴ４において、シグマ評価（Sigma Evaluation）の引数を決定し、ステップＳＴ５に進んでシグマ評価を呼ぶ。ここで、渡すレコードの個数に下限や上限を設けてもよい。

次に、ステップＳＴ６に進んで、シグマ評価の終了を待ち、さらに、ステップＳＴ７に進おいて、シグマ評価が終了したら、渡したレコード情報が格納されているソート配列のエントリに新しいレコード情報を充填してステップＳＴ８に進む。

ステップＳＴ８では、ＸＭＬデータのＸＭＬインデックスが終端になったかどうかを判定する。ステップＳＴ８において、ＸＭＬデータのＸＭＬインデックスが終端になっていないと判定されると、ステップＳＴ３に戻って同様の処理を繰り返す。

一方、ステップＳＴ８において、ＸＭＬデータのＸＭＬインデックスが終端になったと判定されると、ステップＳＴ９に進んで、アクセラレータにアイドル状態への移行条件を通知してステップＳＴ１０に進む。

ステップＳＴ１０では、論理式評価が終了したかどうかを判定し、論理式評価が終了したと判定すると関数を終了し、そうでなければステップＳＴ３のポーリングに戻り、同様の処理を繰り返す。

図２５は図２４のシグマ評価を１エントリごとに待ち合わせる場合を示すフローチャートであり、図２６は図２４のシグマ評価を複数エントリごとに待ち合わせる場合を示すフローチャートである。

図２５に示されるように、図２４のシグマ評価を１エントリごとに待ち合わせる場合、まず、ステップＳＴ２１において、ソート配列の全エントリに対して、レコード順（レコードの順番付けの順）にレコード管理情報を格納し、次に、ステップＳＴ２２に進んで、アクセラレータを起動する。

さらに、ステップＳＴ２３に進んで、ソート配列の先頭エントリの照合完了を待ち合わせて、ステップＳＴ２４に進む。ステップＳＴ２４では、先頭エントリのレコードの論理式評価を実行して、ステップＳＴ２５に進む。

ステップＳＴ２５では、ソート配列に１レコード分のレコード管理情報を充填し、先頭エントリを１つ進める。

そして、ステップＳＴ２６に進んで、データベースの全レコード処理が終了したかどうかを判定し、終了していないと判定されれば、ステップＳＴ２３に戻って同様の処理を繰り返し、データベースの全レコード処理が終了したと判定されると処理を終了する。

図２６に示されるように、図２４のシグマ評価を複数エントリごとに待ち合わせる場合、まず、ステップＳＴ３１において、ソート配列の全エントリに対して、レコード順にレコード管理情報を格納し、次に、ステップＳＴ３２に進んでアクセラレータを起動する。

さらに、ステップＳＴ３３に進んで、ソート配列の先頭エントリの照合完了を待ち合わせて、ステップＳＴ３４に進む。ステップＳＴ３４では、先頭エントリからレコード順に連続して照合が終了した複数のレコードの論理式評価をレコード順に実行して、ステップＳＴ３５に進む。

ステップＳＴ３５では、ソート配列に論理式評価を行ったレコード数と同じ数だけレコード管理情報を充填し、先頭エントリを処理した数だけ進める。

そして、ステップＳＴ３６に進んで、データベースの全レコード処理が終了したかどうかを判定し、終了していないと判定されれば、ステップＳＴ３３に戻って同様の処理を繰り返し、データベースの全レコード処理が終了したと判定されると処理を終了する。

図２７はシグマ評価処理の一例を示すフローチャートである。ここで、シグマ評価（Sigma Evaluation）は、論理式評価を行うための関数であり、シグマ検索で論理式評価可能と判断されたら呼び出される。

図２７に示されるように、依頼された先頭レコードのソート配列エントリアドレスとそこからのレコード個数が渡されると、まず、ステップＳＴ４１において、ａ＝（レコードソート構造体配列の現在のレコードのイベントバッファのアドレス）、ｂ＝１として、ステップＳＴ４２に進む。ステップＳＴ４２において、ソート配列からレコードＩＤを取得し、通常動作のステップＳＴ５（通常動作のループ）に進む。すなわち、先頭レコードを現在のレコードとして論理式評価を開始し、イベントバッファから各エントリを読んで評価する。

ステップＳＴ５は、ステップＳＴ５１〜ＳＴ５４で構成され、ま、ステップＳＴ５１において、ａが示す先の照合結果を読んで論理式評価を実行する。

次に、ステップＳＴ５２に進んで、ａ＋＋とし、さらに、ステップＳＴ５３に進んで、（ａが示す先のエントリ）＝＝（レコード結果の終端エントリ）かどうかを判定する。

ステップＳＴ５３において、（ａが示す先のエントリ）＝＝（レコード結果の終端エントリ）であると判定されると、レコード終了時ループ（ステップＳＴ６）のステップＳＴ６１に進み、逆に、（ａが示す先のエントリ）＝＝（レコード結果の終端エントリ）ではないと判定されると、ステップＳＴ５４に進む。

ステップＳＴ６１では、ｂ＝＝（渡されたレコード個数）かどうかを判定し、ｂ＝＝（渡されたレコード個数）ではないと判定されると、ステップＳＴ６２で、ａ＝（次レコード照合結果の先頭アドレス）、ｂ＋＋として、ステップＳＴ４２に戻り同様の処理を繰り返す。そして、ステップＳＴ６１において、ｂ＝＝（渡されたレコード個数）であると判定されると処理を終了する。

すなわち、もし、現在のレコードが終了したら、次レコードをセットして通常動作に戻り、現在のレコードが終了しなければ終了する。

ステップＳＴ５４では、（ａが示す先のエントリ）＝＝（イベントバッファ終端のエントリ）かどうかを判定し、（ａが示す先のエントリ）＝＝（イベントバッファ終端のエントリ）であると判定されると、バッファフル時のステップＳＴ７におけるステップＳＴ７１に進んで、シグマバッファフルを起動して、ステップＳＴ７２に進む。

そして、ステップＳＴ７２において、ａ＝（次イベントバッファの先頭エントリのアドレス）としてステップＳＴ５１に戻り、また、ステップＳＴ５４で、^*ａ＝＝イベントバッファ終端のエントリではないと判定された場合もステップＳＴ５１に戻り、同様の処理を繰り返す。

すなわち、イベントバッファ終端に到達したらシグマバッファフルを呼び出して帰ってくるのを待ち、また、通常動作に戻る。

図２８シグマバッファフル処理の一例を示すフローチャートである。ここで、シグマバッファフル（Sigma Buffer Full）は、イベントバッファの切り替わりを司る関数であり、対応する検索コアのイベントバッファのフラッシュを指示し、そして、シグマ評価でイベントバッファ終端に達したら呼び出される。

図２８に示されるように、まず、ステップＳＴ８１において、渡されたソート配列要素に対応する検索コア番号を検索し、ステップＳＴ８２に進む。すなわち、フラッシュするイベントバッファのソート配列エントリのアドレスが引数として渡されるが、そのアドレスからソート配列を参照して検索コア番号を獲得する。

ステップＳＴ８２では、フラッシュ完了フラグ＝１かどうかを判定し、フラッシュ完了フラグ＝１ではないと判定されるまで処理を続け、フラッシュ完了フラグ＝１ではないと判定されると、ステップＳＴ８３に進む。

ステップＳＴ８３において、フラッシュ完了フラグ＝１として、ステップＳＴ８４に進み、バッファ距離コピーを獲得する。すなわち、その検索コアに対する前回のフラッシュ指示との待ち合わせを行い、フラッシュ指示が可能であればその時点でスケジューラのＩＯレジスタであるバッファ距離コピーを獲得しておく。

さらに、ステップＳＴ８５に進んで、スケジューラにバッファフラシュ指示と検索コア番号の通知を行って、ステップＳＴ８６に進む。

ステップＳＴ８６では、バッファ距離コピー≧２、または、状態フラグ＝２かどうかを判定し、バッファ距離コピー≧２ではなく、且つ、状態フラグ＝２ではないと判定されると、ポーリングを行うステップＳＴ９に進み、バッファ距離コピー≧２、または、状態フラグ＝２であると判定されると、処理を終了する。

すなわち、先に獲得しておいたバッファ距離コピーの値とソート配列の状態フラグから終了可能かどうかを判定する。なお、終了すると論理式評価が再開される。

そして、ステップＳＴ９においてはステップＳＴ９１〜ＳＴ９３において、フラッシュ完了フラグをポーリングし、次に状態フラグとバッファ距離コピーをポーリングして可能状態を待ち合わせる。

すなわち、ステップＳＴ９１では、フラッシュ完了フラグ＝０かどうかを判定し、フラッシュ完了フラグ＝０であると判定されるまで処理を続け、フラッシュ完了フラグ＝０であると判定されると、ステップＳＴ９２に進み、バッファ距離コピーを再度獲得して、ステップＳＴ９３に進む。

ステップＳＴ９３では、バッファ距離≧１、または、状態フラグ＝２であるかどうかを判定し、バッファ距離コピー≧２ではなく、且つ、状態フラグ＝２ではないと判定されると、ステップＳＴ９２に戻って、同様の処理を繰り返し、バッファ距離≧１、または、状態フラグ＝２であると判定されると、処理を終了する。

上述した各実施例では、主としてオートマトン処理を行う検索装置および検索方法を説明したが、一般的な並列処理システムであって、その入力データおよび中間データに特徴があり、その特徴のあるデータの処理に対して所定のルールに従って処理する検索装置および検索方法に対しても適用することが可能である。

以上の実施例を含む実施形態に関し、さらに、以下の付記を開示する。
（付記１）
ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えた検索装置であって、
前記ＣＰＵは、入力された検索式に従ってオートマトンを作成し、
前記スケジューラは、処理対象テキストを、順番付けしたレコード単位で前記各検索コアに分配し、
前記各検索コアは、前記分配された各レコードをそれぞれ並列的にオートマトン照合し、
前記ＣＰＵは、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価することを特徴とする検索装置。

（付記２）
付記１に記載の検索装置において、
前記処理対象テキストの前記各レコード、および、前記各レコードの前記照合結果は、それぞれのデータサイズに規則性を持たないことを特徴とする検索装置。

（付記３）
付記１または２に記載の検索装置において、さらに、
前記ＣＰＵおよび前記検索コアの共有データを格納するローカルメモリを備え、
該共有データは、前記複数のレコードの照合結果を格納する照合結果情報と、複数のレコードを管理する管理情報とを有し、
前記各レコードの前記順番付けは、前記管理情報として前記ローカルメモリに保持されることを特徴とする検索装置。

（付記４）
付記３に記載の検索装置において、
前記照合結果情報は、前記各検索コアに対して前記ローカルメモリの２枚以上の記憶領域に分割して割り当てて管理されることを特徴とする検索装置。

（付記５）
付記４に記載の検索装置において、
前記各検索コアに対して割り当てられた前記記憶領域の終端には、次の記憶領域の先頭へのポインタが記載されていることを特徴とする検索装置。

（付記６）
付記３に記載の検索装置において、
前記管理情報は、配列またはリスト構造により照合すべきテキスト群の順番を保持することを特徴とする検索装置。

（付記７）
付記３〜６のいずれか１項に記載の検索装置において、
前記スケジューラは、前記管理情報を読んで空いている前記検索コアに前記順番付けの順で前記管理データを分配して照合を指示し、検索コアはランダムに照合完了することを特徴とする検索装置。

（付記８）
付記７に記載の検索装置において、
前記スケジューラは、前記空いている前記検索コアを判断するための情報を保持するレジスタを備えることを特徴とする検索装置。

（付記９）
付記７または８に記載の検索装置において、
前記スケジューラは、前記管理情報を一時的に保持するバッファを備えることを特徴とする検索装置。

（付記１０）
付記１〜９のいずれか１項に記載の検索装置において、
前記処理対象テキストは、構造化文書であり、
前記各検索コアは、前記構造化文書のデータから所定の文字列を検索することを特徴とする検索装置。

（付記１１）
付記１０に記載の検索装置において、
前記構造化文書は、ＸＭＬ文書であることを特徴とする検索装置。

（付記１２）
付記１〜１１のいずれか１項に記載の検索装置を複数結合したことを特徴とする半導体チップ。

（付記１３）
付記１２に記載の半導体チップにおいて、該半導体チップは付記１〜８のいずれか１項に記載の検索装置を２個備えたことを特徴とする半導体チップ。

（付記１４）
付記１２または１３に記載の半導体チップを複数結合し、
該各半導体チップに対してそれぞれ設けた複数のメモリを備えることを特徴とするプロセッサモジュール。

（付記１５）
付記１４に記載のプロセッサモジュールを複数結合すると共に、前記各検索コアがアクセス可能な主記憶装置を備えることを特徴とする検索サーバ。

（付記１６）
付記１５に記載の検索サーバと、
検索対象のデータが格納されたストレージサーバと、
前記検索サーバおよび前記ストレージサーバを管理するディレクタサーバと、を備える検索システム。

（付記１７）
ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えた検索装置を使用した検索方法であって、
前記ＣＰＵが、入力された検索式に従ってオートマトンを作成し、
前記スケジューラが、処理対象テキストを順番付けされたレコード単位で前記各検索コアに分配し、
前記各検索コアが、前記分配された各レコードをそれぞれ並列的に照合処理し、
前記ＣＰＵが、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価することを特徴とする検索方法。

（付記１８）
付記１７に記載の検索方法において、
前記処理対象テキストの前記各レコード、および、前記各レコードの前記照合結果は、それぞれのデータサイズに規則性を持たないことを特徴とする検索方法。

（付記１９）
付記１７または１８に記載の検索方法において、
前記スケジューラは、前記ＣＰＵおよび前記検索コアの共有データにおける複数のレコードを管理する管理情報を読んで空いている前記検索コアに前記順番付けの順で前記管理データを分配して照合を指示し、検索コアはランダムに照合完了することを特徴とする検索方法。

（付記２０）
ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えたコンピュータに、
前記ＣＰＵに、入力された検索式に従ってオートマトンを作成させる手順と、
前記スケジューラに、処理対象テキストを順番付けされたレコード単位で前記各検索コアに分配させる手順と、
前記各検索コアに、前記分配された各レコードをそれぞれ並列的に照合処理させる手順と、
前記ＣＰＵに、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価させる手順と、を実行させる検索プログラム。

オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図（その１）である。 オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図（その２）である。 検索装置の一例を概略的に説明するための図である。 従来の検索装置における検索シーケンスの一例を概略的に示す図である。 従来の検索方法による処理順を概略的に示す図である。 本実施形態の検索装置における検索シーケンスの一例を概略的に示す図である。 本実施形態の検索方法による処理順を概略的に示す図である。 検索装置の一実施例の要部を示すブロック図である。 検索装置の他の実施例の要部を示すブロック図である。 各実施例が適用される検索サーバの一例を概略的に示す図である。 図９の検索サーバを含む検索システムの全体構成を概略的に示す図である。 レコードＩＤからレコードを特定する処理を説明するための図である。 各モジュールの役割を説明するための図である。 各ＡＰＩ関数と呼び出し手続きを説明するための図である。 制御データの詳細なデータ構造を示す図である。 共有データの構造を説明するための図である。 各データの書き込みおよび読み出しの関係を説明するための図（その１）である。 各データの書き込みおよび読み出しの関係を説明するための図（その２）である。 スケジューラの動作を説明するための図（その１）である。 スケジューラの動作を説明するための図（その２）である。 スケジューラの動作を説明するための図（その３）である。 イベントバッファ制御の課題を説明するための図（その１）である。 イベントバッファ制御の課題を説明するための図（その２）である。 イベントバッファ制御の課題を説明するための図（その３）である。 各データの書き込みおよび読み出しの関係を説明するための図（その１）である。 各データの書き込みおよび読み出しの関係を説明するための図（その２）である。 各データの書き込みおよび読み出しの関係を説明するための図（その３）である。 イベントバッファ制御用情報を説明するための図である。 イベントバッファフラッシュ時の動作例を説明するための図（その１）である。 イベントバッファフラッシュ時の動作例を説明するための図（その２）である。 イベントバッファフラッシュ時の動作例を説明するための図（その３）である。 ＡＰＩ関数と呼び出し手続きをフローチャートと関連付けて説明するための図である。 シグマ検索処理の一例を示すフローチャートである。 図２４のシグマ評価を１エントリごとに待ち合わせる場合を示すフローチャートである。 図２４のシグマ評価を複数エントリごとに待ち合わせる場合を示すフローチャートである。 シグマ評価処理の一例を示すフローチャートである。 シグマバッファフル処理の一例を示すフローチャートである。

１１ 検索対象文書
１２ 入力文字
１３ 現在の状態
１４ 入力アドレス
１５ メモリ
１６ 出力データ
１７ 次の状態
ＡＣ アクセラレータ
ＣＨＩＰ 半導体チップ
ＤＳ ディレクタサーバ
ＭＥＭ メモリコントローラ
ＮＥＴ ネットワーク
ＰＢ プロセッサボックス
ＰＭ プロセッサモジュール
ＰＳ プロセッサシステム（検索装置）
ＲＳ ラックシステム
ＳＣ 検索コア（照合装置）
ＳＤ スケジューラ
ＳＳ サーチサーバ
ＳＴＲ ストレージ

Claims (8)

1. ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えた検索装置であって、
   前記ＣＰＵは、入力された検索式に従ってオートマトンを作成し、
   前記スケジューラは、処理対象テキストを、順番付けしたレコード単位で前記各検索コアに分配し、
   前記各検索コアは、前記分配された各レコードをそれぞれ並列的にオートマトン照合し、
   前記ＣＰＵは、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価することを特徴とする検索装置。
2. 請求項１に記載の検索装置において、さらに、
   前記ＣＰＵおよび前記検索コアの共有データを格納するローカルメモリを備え、
   該共有データは、前記複数のレコードの照合結果を格納する照合結果情報と、複数のレコードを管理する管理情報とを有し、
   前記各レコードの前記順番付けは、前記管理情報として前記ローカルメモリに保持されることを特徴とする検索装置。
3. 請求項２に記載の検索装置において、
   前記照合結果情報は、前記各検索コアに対して前記ローカルメモリの２枚以上の記憶領域に分割して割り当てて管理されることを特徴とする検索装置。
4. 請求項２または３に記載の検索装置において、
   前記スケジューラは、前記管理情報を読んで空いている前記検索コアに前記順番付けの順で前記管理データを分配して照合を指示し、検索コアはランダムに照合完了することを特徴とする検索装置。
5. 請求項１〜４のいずれか１項に記載の検索装置において、
   前記処理対象テキストは、構造化文書であり、
   前記各検索コアは、前記構造化文書のデータから所定の文字列を検索することを特徴とする検索装置。
6. ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えた検索装置を使用した検索方法であって、
   前記ＣＰＵが、入力された検索式に従ってオートマトンを作成し、
   前記スケジューラが、処理対象テキストを順番付けされたレコード単位で前記各検索コアに分配し、
   前記各検索コアが、前記分配された各レコードをそれぞれ並列的に照合処理し、
   前記ＣＰＵが、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価することを特徴とする検索方法。
7. 請求項６に記載の検索方法において、
   前記スケジューラは、前記ＣＰＵおよび前記検索コアの共有データにおける複数のレコードを管理する管理情報を読んで空いている前記検索コアに前記順番付けの順で前記管理データを分配して照合を指示し、検索コアはランダムに照合完了することを特徴とする検索方法。
8. ＣＰＵと、複数の検索コアおよびスケジューラを有するアクセラレータと、を備えたコンピュータに、
   前記ＣＰＵに、入力された検索式に従ってオートマトンを作成させる手順と、
   前記スケジューラに、処理対象テキストを順番付けされたレコード単位で前記各検索コアに分配させる手順と、
   前記各検索コアに、前記分配された各レコードをそれぞれ並列的に照合処理させる手順と、
   前記ＣＰＵに、前記各レコード単位の照合結果を該各レコードの前記順番付けの順で論理式評価させる手順と、を実行させる検索プログラム。

Images