(57)【要約】【課題】効率的に型回路を用いた照合処理回路を提供する。【解決手段】照合処理回路は、各々が照合対象データと正規表現パターンの一部との照合を行う複数の型回路と、複数の型回路を直列に接続し、前段の型回路から次段の型回路に照合対象データと前段の型回路が生成した照合結果とを供給する信号経路とを含み、前段の型回路に信号経路を介して接続されている複数の型回路の各々は、前段の型回路からの照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する第１の動作モードと、前段の型回路からの照合対象データと正規表現パターンの一部との照合により得られた結果に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する第２の動作モードとの何れかの動作モードに設定可能である。【選択図】図１
2014199598.tif 000002
【特許請求の範囲】
【請求項１】
各々が照合対象データと正規表現パターンの一部との照合を行う複数の型回路と、
前記複数の型回路を直列に接続し、前段の型回路から次段の型回路に前記照合対象データと前段の型回路が生成した照合結果とを供給する信号経路と、
を含み、前段の型回路に前記信号経路を介して接続されている前記複数の型回路の各々は、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する第１の動作モードと、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する第２の動作モードとの何れかの動作モードに設定可能であることを特徴とする照合処理回路。
【請求項２】
複数の照合コア回路を更に含み、前記複数の照合コア回路は、前記複数の型回路のうちのそれぞれ対応する型回路に接続され、該対応する型回路にそれぞれ対応する照合対象データを供給することを特徴とする請求項１記載の照合処理回路。
【請求項３】
前記複数の型回路はリング状に直列に接続されていることを特徴とする請求項２記載の照合処理回路。
【請求項４】
前記複数の型回路の各々は複数所定個の連続する動作サイクルのうち一つの動作サイクルでのみ前記照合を行い、前記複数の型回路のうち連続する前記複数所定数個の型回路は前記複数所定個の連続する動作サイクルのうち互いに異なる動作サイクルで前記照合を行うことを特徴とする請求項２又は３何れか一項記載の照合処理回路。
【請求項５】
前記信号経路は少なくとも２つの並列な信号経路を含み、前記複数の型回路のうち前記照合コア回路に接続されていない型回路の各々は、前記複数の照合コアのうち少なくとも２つの照合コアからの照合対象データを前記２つの並列な信号経路を介してそれぞれ受け取ることを特徴とする請求項２乃至４何れか一項記載の照合処理回路。
【請求項６】
各々が照合対象データと正規表現パターンの一部との照合を行う複数の型回路が直列に接続された型回路列において、一の型回路から該一の型回路を起点としてＮ番目（Ｎ：１以上の整数）の型回路までのＮ個の型回路に第１の正規表現パターンを割り当て、
前記一の型回路を起点としてＮ＋１番目の型回路からＮ＋Ｍ番目の型回路までのＭ個（Ｍ：１以上の整数）の型回路に第２の正規表現パターンを割り当てる
各段階を含むことを特徴とする照合処理回路の制御方法。
【請求項７】
前記一の型回路から前記Ｎ＋Ｍ番目の型回路まで前記照合対象データを伝搬させることにより、前記第１の正規表現パターンに対する第１の照合と、前記第２の正規表現パターンに対する第２の照合とをそれぞれ独立に行う段階を含むことを特徴とする請求項６記載の照合処理回路の制御方法。
【請求項８】
前記型回路列において、少なくとも２つの別個の照合対象データを並列又は時分割で前段の型回路から次段の型回路に伝搬させることを特徴とする請求項６又は７記載の照合処理回路の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、照合処理回路及び照合処理回路の制御方法に関する。
【背景技術】
【０００２】
与えられた文字列が所望の文字列群の１つに一致するか否かのパターン照合を行うために、通常の文字及び／又はメタキャラクタにより文字列の群を表現する正規表現が用いられる。入力された文字列と正規表現による文字列（正規表現パターン）との一致を判定することにより、入力文字列が所望の文字列群の１つに一致するか否かを判定することができる。
【０００３】
回路上のＲＡＭに正規表現のパターンを設定し、正規表現照合を行う方法が知られている。この方法では、１つの型回路で正規表現パターンの一部を実現し、複数の型回路を連結して得られる型回路列により、複雑な正規表現照合を行うことが可能である。例えば、
[AB]+.{1,3}[BC]?.*[^0]          ・・・・（１）
という正規表現パターンを照合する場合を考える。この場合、第１の型回路に「[AB]+」を割り当て、第２乃至第４の型回路に「.{1,3}」を割り当て、第５の型回路に「[BC]?」を割り当て、第６の型回路に「.*」を割り当て、第７の型回路に「[^0]」を割り当てる。第１乃至第７の型回路を直列に連結して型回路列を形成し、この型回路列の第１の型回路側から照合対象のデータストリームの文字列を一文字ずつ順次入力する。各回路では、各サイクルにおいて、自らに割り当てられた正規表現パターンの一部と供給される各文字との照合を行う。先頭の型回路が、正規表現パターンの一部と現在供給される一文字との照合を行うと、その照合結果と供給された一文字とを次段の型回路に供給する。次段以降の型回路は、正規表現パターンの一部と現在供給される一文字との照合を行うと、その照合結果と前段からの照合結果とに基づいて先頭段から自らの段までの全体の照合結果を生成し、全体の照合結果と供給された一文字とを次段の型回路に供給する。この全体の照合結果を生成する際には、前段からの照合結果が一致を示し、且つ、自らの段の照合結果も一致を示す場合に、全体の照合結果に一致を示す値を設定する。これにより、上記の式（１）の正規表現パターンに一致する文字列が入力された場合には、最終段である第７の型回路から出力される全体の照合結果が、あるサイクルにおいて一致を示すことになる。
【０００４】
型回路列を並列に設けて並列処理を行い、複数のストリームデータに対し、それぞれ別の正規表現パターンを同時に照合してよい。これにより照合処理の高速化を実現することができる。従来、このような並列処理のためには、連結された型回路の数が異なる複数種類の型回路列を用意し、各種類の型回路列を複数個用意する。例えば、型回路４個を連結したサイズ４の型回路列を６つ、型回路８個を連結したサイズ８の型回路列を２つ、型回路１２個を連結したサイズ１２の型回路列を１つ用意する。更に、型回路列への正規表現パターンの書き込みを行うと共に照合対象データである文字列を型回路列に供給する照合コアを、複数のストリームデータに対応して複数個用意し、各照合コアに対し、一つ又は複数の型回路列を接続するように配線する。一つの型回路列は、一つだけの照合コアに接続されて専用に照合処理を行ってもよいし、複数の照合コアに接続されて共用で照合処理を行ってもよい。複数の照合コアで共有される型回路列は、排他制御され、ある任意の時刻においては一つの照合コアに対する照合処理のみを実行する。
【０００５】
上記のような並列構成では、各照合コアが型回路を占有するように回路設計した場合には、各照合コアで種々の長さの異なる正規表現パターンに対して照合を実行するために、各照合コアに対して種々のサイズの型回路列を専用で用意することになる。この場合、回路に無駄が多く、回路サイズが非常に大きくなる。また各照合コアが型回路を共有するように回路設計した場合には、配線数が多くなると共に、処理の並列度が低下してしまう。
【０００６】
なお上記の回路の無駄の問題は、照合コアが一つの場合でも存在する。一つの照合コアで種々の長さの異なる正規表現パターンに対して照合を実行するためには、当該照合コアに対して種々のサイズの型回路列を用意することになる。例えば複数個の異なる正規表現パターンとして、８個のサイズ４のパターンと１個のサイズ８のパターンとを含む第１の構成、及び、１個のサイズ４のパターンと４個のサイズ８のパターンとを含む第２の構成が考えられるとする。このとき、第１の構成と第２の構成との両方に対応可能な回路には、最低でも、４個のサイズ８の型回路列、及び、５個のサイズ４の型回路列を設けることが必要となってしまう（第１の構成ではサイズ８の型回路列でサイズ４の正規表現パターンにも対応できる）。この場合、型回路の数は３２＋２０＝５２個となる。第１の構成の場合において、パターンサイズを無視した場合に単純に必要となる型回路の数は４０（＝８×４＋１×８）であり、第２の構成において、パターンサイズを無視した場合に単純に必要となる型回路の数は３６（＝１×４＋４×８）である。従って、最大でも４０個の型回路しか使用しないのに、第１の構成と第２の構成との両方に対応可能な回路には５２個の型回路が必要になってしまう。このように、回路に無駄が多く、回路サイズが非常に大きくなってしまう。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura , Yoshikazu Miyanaga, "Dynamic Reconfigurable Bit-Parallel Architecture for Large-Scale Regular Expression Matching," Proc. of the 2010 International Conference on Field-Programmable Technology (FPT'10), pp. 21-28, Dec. 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
１つの側面では、本発明は、効率的に型回路を用いた照合処理回路を提供することを目的とする。
【課題を解決するための手段】
【０００９】
照合処理回路は、各々が照合対象データと正規表現パターンの一部との照合を行う複数の型回路と、前記複数の型回路を直列に接続し、前段の型回路から次段の型回路に前記照合対象データと前段の型回路が生成した照合結果とを供給する信号経路とを含み、前段の型回路に前記信号経路を介して接続されている前記複数の型回路の各々は、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する第１の動作モードと、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する第２の動作モードとの何れかの動作モードに設定可能であることを特徴とする。
【００１０】
照合処理回路の制御方法は、各々が照合対象データと正規表現パターンの一部との照合を行う複数の型回路が直列に接続された型回路列において、一の型回路から該一の型回路を起点としてＮ番目（Ｎ：１以上の整数）の型回路までのＮ個の型回路に第１の正規表現パターンを割り当て、前記一の型回路を起点としてＮ＋１番目の型回路からＮ＋Ｍ番目の型回路までのＭ個（Ｍ：１以上の整数）の型回路に第２の正規表現パターンを割り当てる各段階を含むことを特徴とする。
【発明の効果】
【００１１】
効率的に型回路を用いた照合処理回路を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】照合処理回路の構成の一例を示す図である。
【図２】リング状に直列に接続された複数の型回路に対して複数の照合コア回路が接続された照合処理回路の構成の一例を示す図である。
【図３】照合コア回路の構成の一例を示す図である。
【図４】型回路の構成の一例を示す図である。
【図５】型回路の構成の一例を示す図である。
【図６】型回路の構成の別の一例を示す図である。
【図７】型回路の構成の別の一例を示す図である。
【図８】型回路の構成の別の一例を示す図である。
【図９】型回路の構成の別の一例を示す図である。
【図１０】型回路に設けられた照合回路の構成の一例を示す図である。
【図１１】照合処理回路の回路設計時に実行する事前設定の処理手順を示すフローチャートである。
【図１２】図２に示す型回路管理部の処理の一例を示すフローチャートである。
【図１３】照合コア回路の動作の一例を示す図である。
【図１４】出力部の構成の一例を示す図である。
【図１５】型回路の照合動作の一例を示すフローチャートである。
【図１６】型回路の照合動作の一例を示すフローチャートである。
【図１７】型回路の照合動作の一例を示すフローチャートである。
【図１８】型回路の照合動作の一例を示すフローチャートである。
【図１９】型回路の照合動作の一例を示すフローチャートである。
【図２０】型回路の照合動作の一例を示すフローチャートである。
【図２１】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２２】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２３】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２４】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２５】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２６】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２７】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２８】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図２９】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図３０】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図３１】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図３２】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図３３】時分割式の場合の照合対象データの伝搬の一例を示す図である。
【図３４】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図３５】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図３６】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図３７】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図３８】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図３９】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図４０】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図４１】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図４２】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図４３】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【図４４】正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【００１４】
図１は、照合処理回路の構成の一例を示す図である。図１に示す照合処理回路は、照合コア回路１０及び型回路列１１を含む。型回路列１１は、各々が照合対象データと正規表現パターンの一部との照合を行う複数の型回路１２−１乃至１２−１４を含む。複数の型回路１２−１乃至１２−１４は、前段の型回路から次段の型回路に照合対象データと前段の型回路が生成した照合結果とを供給するよう、直列に接続されている。
【００１５】
例えば、型回路１２−１乃至１２−５にはそれぞれ、正規表現パターンの各部分「［ＡＢ］」、「．」、「Ｃ＋」、「．＊」、及び「［＾０］」が割り当てられ、これら正規表現パターンの各部分と照合対象データとの照合を行うように設定されている。型回路１２−１乃至１２−５に対する正規表現パターンの各部分の割り当ては、照合コア回路１０により行われる。これらの型回路１２−１乃至１２−５の直列接続により、「［ＡＢ］．Ｃ＋．＊［＾０］」という正規表現パターンを照合する。
【００１６】
具体的には、型回路１２−１乃至１２−５を含む型回路列の第１の型回路１２−１側から照合対象のデータストリームの文字列を一文字ずつ順次入力する。型回路１２−１乃至１２−５の各回路では、各サイクルにおいて、自らに割り当てられた正規表現パターンの一部と供給される各文字との照合を行う。先頭の型回路１２−１が、正規表現パターンの一部と現在供給される一文字との照合を行うと、その照合結果と供給された一文字とを次段の型回路１２−２に供給する。次段以降の型回路１２−２乃至１２−５は、正規表現パターンの一部と現在供給される一文字との照合を行うと、その照合結果と前段からの照合結果とに基づいて先頭段から自らの段までの全体の照合結果を生成する。全体の照合結果と供給された一文字とは、次段の型回路に供給される。この全体の照合結果を生成する際には、前段からの照合結果が一致を示し、且つ、自らの段の照合結果も一致を示す場合に、全体の照合結果に一致を示す値を設定する。それ以外の場合には、全体の照合結果に不一致を示す値を設定する。これにより、上記の正規表現パターンに一致する文字列が入力された場合には、最終段である第５の型回路１２−５から出力される全体の照合結果が、あるサイクルにおいて一致を示すことになる。
【００１７】
図１に示されるように、複数の型回路１２−１乃至１２−１４には、第１乃至第３の正規表現パターン１３乃至１５が割り当てられている。まず、複数の型回路１２−１乃至１２−１４が直列に接続された型回路列において、一の型回路１２−１から一の型回路を起点としてＮ番目（Ｎ：１以上の整数、この例では５）の型回路１２−５までのＮ個の型回路に第１の正規表現パターン１３を割り当てる。更に、一の型回路１２−１を起点としてＮ＋１番目の型回路１２−６からＮ＋Ｍ番目の型回路１２−７までのＭ個（Ｍ：１以上の整数、この例では２）の型回路に第２の正規表現パターン１４を割り当てる。同様にして、型回路１２−８から型回路１２−１４までの７個の型回路に、第３の正規表現パターン１５を割り当てる。
【００１８】
そして、一の型回路１２−１から型回路１２−１４まで照合対象データを伝搬させる。これにより、第１の正規表現パターン１３に対する第１の照合と、第２の正規表現パターン１４に対する第２の照合と、第３の正規表現パターン１５に対する第３の照合とをそれぞれ独立に行う。即ち、型回路１２−１乃至１２−１４にそれぞれ割り当てられた正規表現パターンの各部分からなる一つの長い正規表現パターンを照合するのではなく、第１乃至第３の正規表現パターン１３乃至１５をそれぞれ別個の３つの正規表現パターンとして照合する。
【００１９】
そのためには、各正規表現パターンの先頭にある型回路において、前段の照合結果を用いることなく、自らに割り当てられた正規表現パターンの一部と前段から供給される照合対象データとを照合した結果を、後段に照合結果として伝えればよい。例えば、第３の正規表現パターン１５の先頭にある型回路１２−８（第３の正規表現パターン１５の最初の一部分「Ｄ」が割り当てられた型回路）に着目する。この型回路１２−８は、前段の型回路１２−７からの照合対象データと正規表現パターンの一部「Ｄ」との照合により得られた結果に応じて、前段の型回路１２−７からの照合結果に依存することなく、後段の型回路１２−９に供給する照合結果を生成する。また型回路１２−９は、前段の型回路１２−８からの照合対象データと正規表現パターンの一部「．」との照合により得られた結果と前段の型回路１２−８からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する。その際、型回路１２−９は、前段からの照合結果が一致を示し、且つ、自らの段の照合結果（照合対象データと「．」との照合結果）が一致を示すときに、一致を示す照合結果を生成する。それ以外の場合には、不一致を示す照合結果を生成する。このようにして、第１乃至第３の正規表現パターン１３乃至１５をそれぞれ別個で独立な３つの正規表現パターンとして照合することができる。
【００２０】
上記の動作を実現するために、前段の型回路に接続されている型回路の各々は、第１の動作モードと第２の動作モードとの何れかの動作モードに設定可能であるよう構成される。第１の動作モードでは、前段の型回路からの照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する。第２の動作モードでは、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する。
【００２１】
なお図１には、単一の照合コア回路１０に接続された単一の型回路列１１のみが示されるが、複数のデータストリーム（照合対象データのデータストリーム）に対して照合を行うためには、図１に示す照合処理回路を各データストリーム毎に設ければよい。また或いは、単一の型回路列に複数の照合コア回路を接続してもよい。また複数の型回路１２−１乃至１２−１４はリング状に直列に接続されてもよい。即ち、型回路１２−１４の出力が型回路１２−１の入力となるように、型回路列１１の後端の型回路と先端の型回路とが接続されてもよい。
【００２２】
図２は、リング状に直列に接続された複数の型回路に対して複数の照合コア回路が接続された照合処理回路の構成の一例を示す図である。図２及び同様の図において、各ボックスで示される各機能又は回路ブロックと他の機能又は回路ブロックとの境界は、基本的には機能的な境界を示すものであり、物理的な位置の分離、電気的な信号の分離、制御論理的な分離等に対応するとは限らない。各機能又は回路ブロックは、他のブロックと物理的にある程度分離された１つのハードウェアモジュールであってもよいし、或いは他のブロックと物理的に一体となったハードウェアモジュール中の１つの機能を示したものであってもよい。
【００２３】
図２に示す照合処理回路は、照合コア回路２０−１乃至２０−４、型回路２２−１乃至２２−２８、ストリームデータ読み出し部２３、型回路管理部２４、及び出力部２５を含む。型回路２２−１乃至２２−２８の各々は、照合対象データと正規表現パターンの一部との照合を行うものであり、図１で説明した型回路１２−１乃至１２−１４の各々と同一の機能を有する。型回路２２−１乃至２２−２８は、前段の型回路から次段の型回路に照合対象データと前段の型回路が生成した照合結果とを供給するよう、信号経路２６を介してリング状に直列に接続されている。但し、リング状であることは必須要件ではなく、例えば、型回路２２−１９と型回路２２−２０との間が接続されて無く、先端と後端とを有する一本の型回路列が形成されていてもよい。以下の説明では、リング状である構成の回路について説明する。
【００２４】
照合コア回路２０−１乃至２０−４は、複数の型回路２２−１乃至２２−２８のうちのそれぞれ対応する型回路２２−６、２２−１３、２２−２０、及び２２−２７に接続され、それら対応する型回路にそれぞれ対応する照合対象データを供給する。照合コア回路２０−１が供給する照合対象データは、例えば型回路２２−６乃至２２−１９を順次伝搬し、型回路２２−６乃至２２−１９のうちの少なくとも一つの型回路により照合されてよい。また照合コア回路２０−２が供給する照合対象データは、例えば型回路２２−１３乃至２２−２６を順次伝搬し、型回路２２−１３乃至２２−２６のうちの少なくとも一つの型回路により照合されてよい。また照合コア回路２０−３が供給する照合対象データは、例えば型回路２２−２０乃至２２−２８及び２２−１乃至２２−５を順次伝搬し、型回路２２−２０乃至２２−２８及び２２−１乃至２２−５のうちの少なくとも一つの型回路により照合されてよい。また照合コア回路２０−４が供給する照合対象データは、例えば型回路２２−２７乃至２２−２８及び２２−１乃至２２−１２を順次伝搬し、型回路２２−２７乃至２２−２８及び２２−１乃至２２−１２のうちの少なくとも一つの型回路により照合されてよい。
【００２５】
前述のように、複数のデータストリーム（照合対象データのデータストリーム）に対して照合を行うためには、図１に示す照合処理回路を各データストリーム毎に設ければよい。しかしながらそのような構成においては、例えば、あるデータストリームに対しては照合するための正規表現パターンの数が少ない或いは長さが短い等の理由により型回路列１１において使用していない型回路が現れる場合がある。そのような余裕のある型回路列１１がある一方で、他のデータストリームを処理する他の型回路列１１では、照合するための正規表現パターンの数が多い或いは長さが長い等の理由により型回路の数が足りないという場合があり得る。
【００２６】
図２に示す構成では、複数の型回路２２−１乃至２２−２８を直列（且つリング状）に接続し、照合コア回路２０−１乃至２０−４は、複数の型回路２２−１乃至２２−２８のうちのそれぞれ対応する型回路にそれぞれ対応する照合対象データを供給する。例えば、照合コア回路２０−１が供給する第１の照合対象データに対しては、照合のために１０個の型回路が必要なのであれば、型回路２２−６乃至２２−１５の型回路に対して、照合コア回路２０−１用の一又は複数の正規表現パターンを割り当てればよい。この時、照合コア回路２０−２が供給する第２の照合対象データに対しては、照合のために４個の型回路が有ればよいのであれば、型回路２２−１６乃至２２−１９の型回路に対して、照合コア回路２０−２用の一又は複数の正規表現パターンを割り当てればよい。そして、型回路２２−１３乃至２２−１５の３つの型回路については、内部を伝搬していく第１の照合対象データと第２の照合対象データとのうち、第１の照合対象データに対してのみ照合を行うように設定すればよい。照合を行わない方の第２の照合対象データについては、単に素通りさせればよい。また型回路２２−１６乃至２２−１９の４つの型回路については、内部を伝搬していく第１の照合対象データと第２の照合対象データとのうち、第２の照合対象データに対してのみ照合を行うように設定すればよい。照合を行わない方の第１の照合対象データについては、単に素通りさせればよい。このような選択的な照合処理は、後述するように、時分割での照合処理或いは型回路間の信号処理経路の複線化により実現することができる。
【００２７】
上記の説明では、照合コア回路２０−１と２０−２を例として用いて説明したが、他の照合コア回路についても同様である。但し、例えば照合コア回路２０−１から供給された照合対象データが型回路２２−１乃至２２−２８が形成するループ内を永遠に伝搬し続けることを避ける必要がある。そこで、上記の例の場合であれば、型回路２２−１９と型回路２２−２０との間において、照合コア回路２０−１からの第１の照合対象データを破棄すればよい。即ち、任意の照合対象データは、２つの照合コア回路に対応する範囲にある型回路（図２の例では１４個の型回路）を伝播して、その後破棄される構成とすればよい。この場合、任意の一つの型回路には、最大で２つの照合コア回路からそれぞれ供給される２つの照合対象データが伝搬することになる。
【００２８】
上記の説明では、任意の一つの照合コア回路は、２つの照合コア回路に対応する範囲にある型回路（図２の例では１４個の型回路）に自らが供給する照合対象データを照合するための正規表現パターンを割り当て可能であるとした。即ち、任意の一つの型回路には、最大でも２つの照合コア回路からそれぞれ供給される２つの照合対象データが伝搬するものとした。これは一例に過ぎず、限定を意図するものではない。例えば、任意の一つの照合コア回路は、３つの照合コア回路に対応する範囲にある型回路（図２の例では２１個の型回路）に自らが供給する照合対象データを照合するための正規表現パターンを割り当て可能であるとしてよい。即ち、任意の一つの型回路には、最大で３つの照合コア回路からそれぞれ供給される３つの照合対象データが伝搬するものとしてよい。
【００２９】
図２において、ストリームデータ読み出し部２３は、各照合コア回路２０−１乃至２０−４に対してそれぞれのストリームデータ（照合対象データ）を供給する。型回路管理部２４は、何れの型回路が既に使用されているか（既に正規表現パターンの一部が割り当てられているか）を示す情報を保持し、何れの型回路を何れの照合コア回路に割り当てるかを決定する。この型回路管理部２４の管理下において、照合コア回路２０−１乃至２０−４が型回路２２−１乃至２２−２８に正規表現パターンの各部分を割り当てる。出力部２５は、型回路２２−１乃至２２−２８からの照合結果を受け取り、照合対象データが正規表現パターンに一致したか否かを判定する。例えば、図１の例では、第１の正規表現パターン１３に一致する文字列が入力された場合には、最終段である型回路１２−５から出力される照合結果が、ある動作サイクルにおいて一致を示すことになる。同様に、図２の構成においても、ある正規表現パターンに一致する文字列が入力された場合には、その正規表現パターンが設定された型回路の最終段から出力される照合結果が、ある動作サイクルにおいて一致を示すことになる。出力部２５は、型回路２２−１乃至２２−２８の各々の照合結果の出力を監視することにより、正規表現パターンと照合対象データとが一致したか否かを判定する。
【００３０】
図３は、照合コア回路の構成の一例を示す図である。図２に示す照合コア回路は、図３に示す構成を有してよい。図３に示す照合コア回路は、制御部３０、書き込み用回路データ格納部３１、タイミング情報供給部３２、バッファ３３、及びバッファ３４を含む。制御部３０は、型回路管理部２４（図２）に型回路利用要求を送信し、型回路管理部２４から利用可能な型回路についての情報を受け取る。制御部３０は、ストリームデータ読み出し部２３（図２）から正規表現パターンを識別する識別情報（正規表現ＩＤ）を受け取り、当該識別情報に一致する書き込み用回路データを書き込み用回路データ格納部３１から読み出す。この書き込み用回路データは、識別情報が示す正規表現パターンの各部に対応する照合処理を型回路に実行させるための構成データ（コンフィギュレーションデータ）である。この構成データは、バッファ３４を介して各型回路に供給される。正規表現パターンのある一部の構成データを送信する際、制御部３０は、タイミング情報供給部３２を介して、当該構成データに対応するタイミング情報と、書き込み先ＩＤ情報と、書き込み指示とを各型回路に供給する。書き込み先ＩＤ情報は書き込み先の型回路を特定するものである。なお制御部３０は、書き込み先の型回路がどの型回路であるかについての情報を、型回路利用要求に応答する型回路管理部２４から受け取る。
【００３１】
書き込み先ＩＤ情報にＩＤが一致する型回路は、書き込み指示を受け取ると、自分のＩＤに一致する書き込み先ＩＤ情報と共に送られてきた構成データを、内部の照合回路のメモリに書き込む。またこの型回路は、ＩＤ情報と共に送られてきたタイミング情報を、内部のタイミング回路に設定する。タイミング回路を設定することにより、例えば第１の照合対象データと第２の照合対象データとの２つの照合対象データが供給されるときに、どちらの照合対象データに対して照合を行うかが制御される。
【００３２】
また制御部３０は、バッファ３３を制御することにより、ストリームデータ読み出し部２３（図２）から供給される照合対象データを、適切なタイミング（適切な動作サイクル）で各型回路に供給する。これにより、各型回路は、照合対象データに対して所望の正規表現パターンの一部との照合を実行し、複数の型回路全体で所望の正規表現パターンの照合を実行する。
【００３３】
図４は、型回路の構成の一例を示す図である。図２に示す型回路のうち、照合コア回路に接続されない型回路は、図４に示す構成を有してよい。図４に示す型回路は、書込み判定部４０、タイミング回路４１、照合回路４２、照合結果バッファ４３、バッファ４４乃至４７、及びセレクタ４８を含む。図３に示す照合コア回路が、接続先の一つの型回路に構成データ、タイミング情報、書き込み先ＩＤ情報、及び書き込み指示を供給すると、当該型回路に直列に接続される一連の型回路内をこれらのデータが伝搬していく。書込み判定部４０は、書き込み指示情報と書き込み先ＩＤ情報とを前段の型回路から受け取ると、書き込み先ＩＤ情報が自らの型回路のＩＤに一致するか否かを判定する。ＩＤが一致する場合、書込み判定部４０は、タイミング回路４１と照合回路４２とに書き込み指示をする。
【００３４】
上記書き込み指示を受けて、タイミング回路４１には、前段の型回路から供給されるタイミング情報が格納される。これにより、タイミング回路４１は、適切な照合対象データに対して照合回路４２が照合を実行するように、照合回路４２の照合動作のタイミングを制御する。また上記書き込み指示を受けて、照合回路４２には、前段の型回路から供給される書き込み用回路データ即ち構成データが格納される。これにより、照合回路４２は、構成データに対応する正規表現パターンの一部と照合対象データとの照合を実行することができる。照合対象データは、前段の型回路からストリームデータとして一文字ずつ照合回路４２に供給される。
【００３５】
照合回路４２は、構成データに応じて第１の動作モード或いは第２の動作モードの何れかで動作するように設定される。第１の動作モードでは、前段の型回路からの照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する。第２の動作モードでは、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する。照合回路４２が生成した照合結果は、出力部２５（図２）に供給される。このとき、タイミング回路４１からタイミング情報も出力部２５に供給される。なお前段の型回路からの照合結果は、照合結果バッファ４３に格納され、照合結果バッファ４３から照合回路４２に供給される。
【００３６】
前段の型回路からの書き込み指示情報と書き込み先ＩＤ情報とは、バッファ４４を介して後段の型回路に供給される。前段の型回路からの書き込み用回路データとタイミング情報とは、バッファ４５を介して後段の型回路に供給される。前段の型回路からの照合対象データ（ストリームデータ）は、バッファ４６を介して後段の型回路に供給される。照合回路４２が求めた照合結果又は前段の型回路から供給された照合結果の何れかが、タイミング回路４１からの指示に応じてセレクタ４８により選択され、バッファ４７を介して後段の型回路に供給される。
【００３７】
なお図４に示す型回路は、時分割式の型回路であり、複数所定個の連続する動作サイクルのうち一つの動作サイクルでのみ照合を行う。図２に示す照合処理回路の各部は、共通のクロック信号に同期して各クロックサイクルで所定の動作を実行することにより、照合処理を行う。時分割型の型回路を用いる場合、図２の複数の型回路２２−１乃至２２−２８のうち連続する複数所定数個の型回路（同一の照合対象データを照合する型回路）は、複数所定個の連続する動作サイクルのうち互いに異なる動作サイクルで照合を行うことになる。
【００３８】
この複数所定個の連続する動作サイクルとは、例えば２つの連続する動作サイクルである。この場合、一つの型回路は、偶数サイクル又は奇数サイクルの何れか一方において照合動作を行う。
【００３９】
例えば、図２において型回路２２−１３乃至２２−１９が、照合コア回路２０−１からの第１の照合対象データと照合コア回路２０−２からの第２の照合対象データとを受け取る場合を考える。この場合、例えは、照合コア回路２０−１から偶数サイクルで第１の照合対象データを送出し、照合コア回路２０−２からも偶数サイクルで第２の照合対象データを送出するように設定する。この設定により、例えば型回路２２−１４は、偶数サイクルで第１の照合対象データを受け取り、奇数サイクルで第２の照合対象データを受け取ることになる。また例えば次段の型回路２２−１５は、奇数サイクルで第１の照合対象データを受け取り、偶数サイクルで第２の照合対象データを受け取ることになる。従って、時分割式の各型回路において、偶数サイクル又は奇数サイクルの何れにおいて照合回路４２による照合を行うかをタイミング回路４１により制御することにより、第１の照合対象データ又は第２の照合対象データの所望の一方に対する照合を行うことができる。即ち各型回路は、複数所定個（２個）の連続する動作サイクルのうち一つの動作サイクルでのみ照合を行う。そして、複数の型回路２２−１乃至２２−２８型回路のうち連続する複数所定数個（２個）の型回路（同一の照合対象データを照合する型回路）は、複数所定個（２個）の連続する動作サイクルのうち互いに異なる動作サイクルで照合を行う。
【００４０】
上記の複数所定個の連続する動作サイクルとは、２つの連続する動作サイクルである必要はなく、任意の数であってよい。例えば、一つの型回路は、第１乃至第３の照合対象データを受け取り、３個の連続する動作サイクルのうち一つの動作サイクルでのみ照合を行うように設定されてよい。この場合、複数の型回路２２−１乃至２２−２８型回路のうち連続する３個の型回路（同一の照合対象データを照合する型回路）は、３個の連続する動作サイクルのうち互いに異なる動作サイクルで照合を行うことになる。
【００４１】
図５は、型回路の構成の一例を示す図である。図２に示す型回路のうち照合コア回路に接続される型回路は、図５に示す構成を有してよい。図５において、図４と同一又は対応する構成要素は同一又は対応する番号で参照し、その説明は適宜省略する。図５に示す型回路は、書込み判定部４０Ａ、タイミング回路４１、照合回路４２、照合結果バッファ４３、バッファ４４乃至４７、セレクタ４８、並びにセレクタ４９−１及び４９−２を含む。
【００４２】
図５の型回路は、前段の型回路だけでなく照合コア回路にも接続されるので、書込み判定部４０Ａは、前段の型回路及び照合コア回路の各々から書き込み先ＩＤ情報及び書き込み指示を受け取る。前段の型回路からの書き込み指示を受け取った場合には、書込み判定部４０Ａは、セレクタ４９−１により前段の型回路からの書き込み用回路データ（構成データ）とタイミング情報とを選択する。また照合コア回路からの書き込み指示を受け取った場合には、書込み判定部４０Ａは、セレクタ４９−１により照合コア回路からの書き込み用回路データ（構成データ）とタイミング情報とを選択する。また書込み判定部４０Ａは、バッファ４４への入力も同様にして選択する。これにより、タイミング回路４１、照合回路４２及びバッファ４４には、前段の型回路からの書き込み指示であるか照合コア回路からの書き込み指示であるかに応じて、適切な設定がなされる。
【００４３】
また照合動作時には、タイミング回路４１は、設定されたタイミング情報に応じてセレクタ４９−２により、照合コア回路からの照合対象データ又は前段の型回路からの照合対象データの何れかを選択し、照合回路４２に供給する。これにより、照合回路４２により適切な照合対象データを対象とした照合が実行される。
【００４４】
図６は、型回路の構成の別の一例を示す図である。図２に示す型回路のうち、照合コア回路に接続されない型回路は、図６に示す構成を有してよい。図６に示す型回路は、書込み判定部５０、タイミング回路５１、照合回路５２、照合結果バッファ５３、バッファ５４乃至５７、及びセレクタ５８−１乃至５８−４を含む。図６に示す型回路は、全ての動作サイクルで照合を行ってよい。
【００４５】
図６の型回路は、複線方式の型回路である。この型回路では、型回路間を接続する信号線として、複数の照合コア回路を起源とする複数の同一種のデータを伝達する複数並列の信号線を設ける。前述のように、図３に示す照合コア回路が、接続先の一つの型回路に構成データ、タイミング情報、書き込み先ＩＤ情報、及び書き込み指示を供給すると、当該型回路に直列に接続される一連の型回路内をこれらのデータが伝搬していく。例えば３つの照合コア回路からのデータが並列に各型回路を伝搬していくように設計した場合、図６に信号線５９−１乃至５９−４として示されるように、同一種のデータを伝達する信号線が３本（３セット）並列に設けられることになる。
【００４６】
書込み判定部５０は、３セットの書き込み指示情報と書き込み先ＩＤ情報とを前段の型回路から受け取ると、何れかのセットの書き込み先ＩＤ情報が自らの型回路のＩＤに一致するか否かを判定する。ＩＤが一致する場合、書込み判定部５０は、タイミング回路５１と照合回路５２とに書き込み指示をすると共に、セレクタ５８−２に対して、ＩＤが一致したセットに対応する書き込み用回路データ及びタイミング情報を選択するように指示する。書き込み指示を受けて、タイミング回路５１には、前段の型回路から供給されるタイミング情報が格納される。これにより、タイミング回路５１は、適切な照合対象データに対して照合回路５２が照合を実行するように、セレクタ５８−３により照合回路５２の照合対象データを選択する。また上記書き込み指示を受けて、照合回路５２には、前段の型回路から供給される書き込み用回路データ即ち構成データが格納される。これにより、照合回路５２は、構成データに対応する正規表現パターンの一部と照合対象データとの照合を実行することができる。照合対象データは、前段の型回路からストリームデータとして、セレクタ５８−３を介して一文字ずつ照合回路５２に供給される。
【００４７】
照合回路５２は、構成データに応じて前記第１の動作モード或いは第２の動作モードの何れかで動作するように設定される。第１の動作モードでは、前段の型回路からの照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する。第２の動作モードでは、前段の型回路からの前記照合対象データと正規表現パターンの一部との照合により得られた結果に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する。なお前段の型回路から供給される照合結果のうち、照合対象データに一致する照合結果が、タイミング回路５１により制御されるセレクタ５８−４を介して照合結果バッファ５３に供給され、照合結果バッファ５３から照合回路５２に供給される。照合回路５２が生成した照合結果は、出力部２５（図２）に供給される。このとき、タイミング回路５１からタイミング情報も出力部２５に供給される。
【００４８】
前段の型回路からの書き込み指示情報と書き込み先ＩＤ情報とは、バッファ５４を介して後段の型回路に供給される。前段の型回路からの書き込み用回路データとタイミング情報とは、バッファ５５を介して後段の型回路に供給される。前段の型回路からの照合対象データ（ストリームデータ）は、バッファ５６を介して後段の型回路に供給される。照合回路５２が求めた照合結果又は前段の型回路から供給された照合結果の何れかが、タイミング回路５１からの指示に応じてセレクタ５８−１により選択され、バッファ５７を介して後段の型回路に供給される。
【００４９】
図７は、型回路の構成の別の一例を示す図である。図２に示す型回路のうち照合コア回路に接続される型回路は、図７に示す構成を有してよい。図７において、図６と同一又は対応する構成要素は同一又は対応する番号で参照し、その説明は適宜省略する。図７に示す型回路は、基本的に、図６に示す型回路と、構成及び動作は同様である。但し、前段の型回路から供給される３セットの信号（例えば書き込み用回路データ及びタイミンク情報）のうち、一セットの信号は用いることなくそのまま破棄される。破棄されたセット以外の残りの２セットの信号及び照合コア回路からの１セットの信号から、当該型回路にて処理される１セットが選択して使用される。
【００５０】
図８は、型回路の構成の別の一例を示す図である。図２に示す型回路のうち、照合コア回路に接続されない型回路は、図８に示す構成を有してよい。図８に示す型回路は、書込み判定部６０、タイミング回路６１、照合回路６２、照合結果バッファ６３、バッファ６４乃至６７、及びセレクタ６８−１乃至６８−４を含む。図８に示す型回路は、構成としては図６に示す型回路と同一の構成であり、図８に示す型回路の各部は図６示す型回路の各部と同一の動作を実行する。
【００５１】
但し、図８に示す型回路は複線式且つ時分割式の型回路であり、複数所定個の連続する動作サイクルのうち一つの動作サイクルでのみ照合を行う。図２に示す照合処理回路の各部は、共通のクロック信号に同期して各クロックサイクルで所定の動作を実行することにより、照合処理を行う。複線式且つ時分割式の型回路を用いる場合、図２の複数の型回路２２−１乃至２２−２８のうち連続する複数所定数個の型回路（同一の照合対象データを照合する型回路）は、複数所定個の連続する動作サイクルのうち互いに異なる動作サイクルで照合を行うことになる。これにより、例えば３セットの複線化された並列配線と２サイクル（偶数及び奇数サイクル）での時分割により、６（＝３×２）個の異なる照合コア回路からのデータに対する選択的な照合処理を実行することができる。複線式の各部動作及び時分割式の各部動作については、前述の型回路と同様であり、その説明は省略する。
【００５２】
図９は、型回路の構成の別の一例を示す図である。図２に示す型回路のうち照合コア回路に接続される型回路は、図９に示す構成を有してよい。図９において、図８と同一又は対応する構成要素は同一又は対応する番号で参照し、その説明は適宜省略する。図９に示す型回路は、基本的に、図８に示す型回路と、構成及び動作は同様である。但し、型回路が選択するデータには、当該型回路に直接に接続される照合コア回路からのデータも含まれる。なお図７の型回路では、最終配線のデータは全て破棄しているが、図９の型回路では、最終配線のデータにはＴ個（Ｔ：時分割数）の異なる照合コア回路からのデータが伝搬しているので、当該配線のデータを全て破棄することはできない。タイミング回路６１等の選択動作により、前段の型回路から供給されるＴ×３個の信号のうち、一つの信号は用いることなくそのまま破棄し、その信号の位置に、直接接続される照合コア回路からの信号を代わりに挿入することになる。
【００５３】
図１０は、型回路に設けられた照合回路の構成の一例を示す図である。図１０に示す照合回路は、メモリ回路７０、ＡＮＤ回路７１及びＯＲ回路７２を含む。メモリ回路７０は、ＲＡＭ（Random Access Memory）等であり、１６進数で表現したアドレス０ｘ００乃至０ｘＦＦに論理値０又は論理値１の何れかが格納されている。このメモリ回路７０の例では、アドレス０ｘ４３及び０ｘ４４において論理値１であり、それ以外のアドレスにおいて論理値０となっている。このメモリ回路７０に、照合対象データとして供給されたアスキーコード一文字をアドレスとして入力すると、そのアドレスに格納される論理値１又は０が読み出される。図１０の例では、０ｘ４３及び０ｘ４４であるアスキーコード文字（即ち「Ｃ」又は「Ｄ」）が照合対象データとして供給されると、メモリ回路７０は論理値１を出力する。それ以外の文字が照合対象データとして供給されると、メモリ回路７０は論理値０を出力する。
【００５４】
前述のように、照合回路は、構成データに応じて第１の動作モード或いは第２の動作モードの何れかで動作するように設定される。第１の動作モードでは、ＯＲ回路７２の一方の入力が０に固定される。この場合、ＡＮＤ回路７１は、ＯＲ回路７２を介して、前段の型回路から照合結果バッファを介して供給される照合結果を一方の入力に受け取る。ＡＮＤ回路７１は、前段の型回路からの照合結果とメモリ回路７０の出力論理値との論理積を演算する。演算結果が、照合回路の照合結果として出力される。即ち、第１の動作モードでは、前段の型回路からの照合対象データと正規表現パターンの一部との照合により得られた結果と前段の型回路からの照合結果とに応じて、後段の型回路に供給する照合結果を生成する。
【００５５】
第２の動作モードでは、ＯＲ回路７２の一方の入力が１に固定される。この場合、ＡＮＤ回路７１は、メモリ回路７０の出力論理値を、照合回路の照合結果としてそのまま出力する。即ち、第２の動作モードでは、照合対象データと正規表現パターンの一部との照合により得られた結果（メモリ回路７０の出力）に応じて、前段の型回路からの照合結果に依存することなく、後段の型回路に供給する照合結果を生成する。
【００５６】
図１１は、照合処理回路の回路設計時に実行する事前設定の処理手順を示すフローチャートである。この処理は、設計者又は設計用計算機等によって実行される。この処理により、各型回路において照合対象データが伝搬していく一つ又は複数の信号経路に対して、複数の照合コア回路を時分割又は複線化により事前に割り当てる。この事前設定の割り当てにより、何れの照合コア回路を起源とする照合対象データが何れの信号経路を伝搬していくのか、及び、何れの型回路を伝搬していくのかが決定される。
【００５７】
なお図１１及び以降のフローチャートにおいて、フローチャートに記載された各ステップの実行順序は一例にすぎず、本願の意図する技術範囲が、記載された実行順序に限定されるものではない。例えば、Ａステップの次にＢステップが実行されるように本願に説明されていたとしても、Ａステップの次にＢステップを実行することが可能なだけでなく、Ｂステップの次にＡステップを実行することが、物理的且つ論理的に可能である場合がある。この場合、どちらの順番でステップを実行しても、当該フローチャートの処理に影響する全ての結果が同一であるならば、本願に開示の技術の目的のためには、Ｂステップの次にＡステップが実行されてもよいことは自明である。Ａステップの次にＢステップが実行されるように本願に説明されていたとしても、上記のような自明な場合を本願の意図する技術範囲から除外することを意図するものではなく、そのような自明な場合は、当然に本願の意図する技術範囲内に属する。
【００５８】
ステップＳ１で、照合コア回路と接続している型回路を選択する。ステップＳ２で、選択した型回路の出力および次の型回路の入力における時分割若しくは複線化又はその両方にて分けられた領域にその領域数分の最も近い照合コア回路をそれぞれ割り当てる。これにより、照合コア回路と接続している型回路に対して、複数の照合コア回路が割り当てられる。
【００５９】
ステップＳ３で、次の型回路を選択する。ステップＳ４で、選択した型回路が初めに選択した型回路であるか否かを判定する。即ち、処理対象の型回路が、型回路のループを一周して最初の型回路に戻ったか否かを判定する。Ｙｅｓの場合には、処理を終了する。Ｎｏの場合には、ステップＳ５で、選択された型回路が照合コア回路と接続されているか否かを判定する。
【００６０】
ステップＳ５の判定において選択された型回路が照合コア回路と接続されていない場合、ステップＳ６に進む。ステップＳ６で、選択した型回路の出力および次の型回路の入力における時分割若しくは複線化又はその両方にて分けられた領域に前の型回路と同じ配線で次のタイミングに対応する照合コア回路を割り当てる。ステップＳ５の判定において選択された型回路が照合コア回路と接続されている場合、ステップＳ７に進む。ステップＳ７で、選択した型回路の出力および次の型回路の入力における時分割若しくは複線化又はその両方にて分けられた領域に前型回路と配線番号＋１の配線で次のタイミングに対応する照合コア回路を割り当てる。但し、一番遠い照合コア回路を割り当てられることになる配線には、当該型回路に接続されている照合コア回路を割り当てる。
【００６１】
図１２は、図２に示す型回路管理部２４の処理の一例を示すフローチャートである。型回路管理部２４は、ある照合コア回路から回路準備要求（即ち型回路利用要求）を受け取ると、図１２に示す処理を実行することにより、当該照合コア回路に対して割り当てる型回路を選択し、選択された型回路を照合コア回路に通知する。
【００６２】
ステップＳ１１で、型回路管理部２４は、照合コア回路から回路準備要求と正規表現サイズとを受け取る。ステップＳ１２で、型回路管理部２４は、当該照合コア回路と直接に接続されている型回路を対象型回路とする。ステップＳ１３で、型回路管理部２４は、対象型回路が使用済みであるか否か（即ち既に照合コア回路に割り当て済みであるか否か）を判定する。
【００６３】
ステップＳ１３での判定により対象型回路が使用済みでないことが判明した場合、ステップＳ１４で、型回路管理部２４は、対象型回路を開始型回路とし、型回路サイズを１とする。ステップＳ１５で、型回路管理部２４は、型回路サイズが正規表現のサイズに等しいか否かを判断する。型回路サイズが正規表現のサイズに等しくない場合、ステップＳ１６で、型回路管理部２４は、次の型回路を対象型回路とする。次にステップＳ１７で、型回路管理部２４は、対象型回路が当該照合コア回路にとって利用不可能な型回路（事前設定で当該照合コア回路に割り当てられていない型回路）であるか否かを判定する。利用不可能である場合には、ステップＳ２４で、型回路管理部２４は、正規表現パターンの書き込みを断念する。利用不可能でない（利用可能である）場合には、ステップＳ１８で、型回路管理部２４は、対象型回路が使用済み（即ち他の正規表現パターンが既に割り当てられている）であるか否かを判定する。使用済みでない場合には、ステップＳ１９で、型回路管理部２４は、型回路サイズを＋１する。その後ステップＳ１５に戻り、以降の処理を繰り返す。
【００６４】
ステップＳ１３の判定により対象型回路が使用済みであることが判明した場合、又は、ステップＳ１８の判定により対象型回路が使用済みであると判明した場合、ステップＳ２２で、型回路管理部２４は、次の型回路を対象型回路とする。次にステップＳ２３で、型回路管理部２４は、対象型回路が当該照合コア回路にとって利用不可能な型回路（事前設定で当該照合コア回路に割り当てられていない型回路）であるか否かを判定する。利用不可能である場合には、ステップＳ２４で、型回路管理部２４は、正規表現パターンの書き込みを断念する。利用不可能でない（利用可能である）場合には、ステップＳ１３に戻り、以降の処理を繰り返す。
【００６５】
ステップＳ１５の判定により型回路サイズが正規表現のサイズに等しいことが判明した場合、要求される長さ（サイズ）の正規表現パターンを書き込むだけの型回路が見つかったことになる。この場合、ステップＳ２０で、型回路管理部２４は、対象型回路を終了型回路とする。最後にステップＳ２１で、型回路管理部２４は、開始型回路と終了型回路とを照合コア回路に通知する。通知された照合コア回路は、開始型回路から終了型回路までの型回路に、正規表現パターンと照合タイミング情報とを書きこむ。
【００６６】
図１３は、照合コア回路の動作の一例を示す図である。ステップＳ３１で、照合コア回路は、ストリームデータ（照合対象データ）を型回路列に供給するタイミング（サイクル）であるか否かを判定する。ストリームデータを供給するタイミングである場合、ステップＳ３２で、照合コア回路は、ストリームデータの先頭のデータを取り出し、取り出したデータを照合コア回路に直接に接続されている型回路に供給する。次にステップＳ３３で、動作サイクルを次のサイクルに推移してから、ステップＳ３１に戻り以降の処理を繰り返す。
【００６７】
ステップＳ３１の判定によりストリームデータを供給するタイミング（サイクル）でないことが判明した場合、ステップＳ３４で、当該サイクルでは何もしない（型回路にストリームデータを供給しない）。次にステップＳ３３で、動作サイクルを次のサイクルに推移してから、ステップＳ３１に戻り以降の処理を繰り返す。
【００６８】
例えば、時分割方式の型回路の場合には、複数所定個の連続する動作サイクルのうち所定の一つの動作サイクルでのみで、照合コア回路から型回路にストリームデータを供給してよい。例えば２サイクルで時分割する場合には、例えば偶数サイクルのみで、照合コア回路から型回路にストリームデータを供給してよい。また複線式の型回路の場合には、各サイクルで、照合コア回路から型回路にストリームデータを供給してよい。
【００６９】
図１４は、出力部２５の構成の一例を示す図である。ステップＳ４１で、出力部２５は、各型回路から照合結果を受け取る。ステップＳ４２で、出力部２５は、型回路からのタイミング情報に基づいて、型回路が照合結果を出力するタイミングであるのか否かを各型回路毎に判定する。照合結果を出力するタイミングである場合には、ステップＳ４３で、照合結果が一致を示すか否かを判定する。照合結果が一致を示す場合には、ステップＳ４４で、入力データストリーム（照合対象データ）が正規表現パターンに一致した旨を示す結果を出力する。次にステップＳ４５で、動作サイクルを次のサイクルに推移してから、ステップＳ４２に戻り以降の処理を繰り返す。
【００７０】
ステップＳ４２の判定により出力タイミングではないことが判明した場合、ステップＳ４６で、当該サイクルでは何もしない（出力部２５からは何も出力しない））。次にステップＳ４５で、動作サイクルを次のサイクルに推移してから、ステップＳ４２に戻り以降の処理を繰り返す。
【００７１】
なお上記のフローにおいて、出力部２５は、例えば各正規表現パターンが設定された型回路のうちの最終段の型回路を知っていてよい。当該最終段の型回路の出力する照合結果が一致を示すときにのみ、出力部２５は、入力データストリーム（照合対象データ）が正規表現パターンに一致した旨を示す結果を出力してよい。また或いは、各型回路は、自らが正規表現パターンの最終部分を照合する型回路（終了型回路）であるか否かを知っており、終了型回路である場合にのみ、照合結果とタイミング情報とを出力部２５に供給してもよい。この場合には、出力部２５は、照合結果とタイミング情報とが出力されたときに、入力データストリーム（照合対象データ）が正規表現パターンに一致した旨を示す結果を出力してよい。
【００７２】
図１５は、型回路の照合動作の一例を示すフローチャートである。このフローチャートに示す動作は、図４に示す型回路のように照合コア回路に接続されない時分割式の型回路により実行される。
【００７３】
ステップＳ５１で、着目型回路は、ストリームデータの一部（照合対象データの一部）と前段の型回路での照合結果とを前段の型回路から受け取る。ここでストリームデータの一部（照合対象データの一部）は、例えば照合対象の一文字のデータ（例えば一文字のアスキー符号）である。ステップＳ５２で、着目型回路のタイミング回路４１が、現在の動作サイクルが照合タイミング（照合サイクル）であるのか否かを判断する。例えば２サイクルでの時分割動作の場合、着目型回路にとって、例えば偶数サイクルが照合タイミング（照合サイクル）であり、奇数サイクルが照合タイミング（照合サイクル）でないことになる。
【００７４】
ステップＳ５２において現在の動作サイクルが照合タイミングでないと判断された場合、ステップＳ５３で、着目型回路は、受け取ったデータを後段の型回路にそのまま送る。その後ステップＳ５４で、動作サイクルが次のサイクルに推移した後、ステップＳ５１に戻り以降の処理を繰り返す。
【００７５】
ステップＳ５２において現在の動作サイクルが照合タイミングであると判断された場合、ステップＳ５４で、照合処理を実行する。即ち、着目型回路の照合回路４２は、前段の型回路から受け取った照合対象データを照合して得られる照合結果と、照合結果バッファ４３に保持されている照合結果とに基づいて新たな照合結果を生成し、生成した照合結果を出力部２５へ出力する。また、着目型回路は、生成した照合結果を照合対象データとともに後段の型回路へ送る。また更に、着目型回路の照合結果バッファ４３には、前段の型回路から受け取った照合結果を新たに保持する。その後ステップＳ５４で、動作サイクルが次のサイクルに推移した後、ステップＳ５１に戻り以降の処理を繰り返す。
【００７６】
上記説明において、着目型回路の照合回路４２は、現在の動作サイクルにおいて前段の型回路から受け取った照合対象データを照合して得られる照合結果と、照合結果バッファ４３に保持されている照合結果とに基づいて新たな照合結果を生成している。このとき、照合結果バッファ４３に保持されている照合結果は、前回の照合動作を実行した動作サイクルにおいて前段の型回路から受け取り照合結果バッファ４３に保持されたものである。このように、現在の照合サイクルで自段にて生成された照合結果と前回の照合サイクルで前段から供給された照合結果とに基づいて新たな照合結果を求めているのは、以下の理由による。照合対象データが正規表現パターンに一致する場合、前段の型回路が照合して一致するのは、照合対象データ（文字列）の例えばＫ番目のデータ（Ｋ番目の文字）である。着目型回路（自段の型回路）は、このＫ番目のデータについての照合結果とＫ番目のデータとを、ある照合動作サイクル（例えばｋ番目の照合動作サイクル）で受け取る。しかしながら、この着目型回路が照合して一致するデータは、照合対象データ（文字列）のＫ＋１番目のデータ（Ｋ＋１番目の文字）である。このＫ＋１番目のデータ（Ｋ＋１番目の文字）を、着目型回路は、ｋ＋１番目の照合動作サイクルで受け取る。従って、着目型回路は、ｋ番目の照合動作サイクルにおいて前段の型回路から受け取った照合結果を保持しておき、この保持した照合結果とｋ＋1番目の照合動作サイクルでの照合結果とに基づいて、新たな照合結果を生成すればよい。
【００７７】
図１６は、型回路の照合動作の一例を示すフローチャートである。このフローチャートに示す動作は、図５に示す型回路のように照合コア回路に接続される時分割式の型回路により実行される。
【００７８】
ステップＳ６１で、着目型回路は、ストリームデータの一部（照合対象データの一部）と前段の型回路での照合結果とを前段の型回路から受け取る。ここでストリームデータの一部（照合対象データの一部）は、例えば照合対象の一文字のデータ（例えば一文字のアスキー符号）である。ステップＳ６２で、着目型回路のタイミング回路４１は、現在の動作サイクルが照合コア回路からのデータ読み込みタイミング（サイクル）であるか否かを判断する。現在の動作サイクルが照合コア回路からのデータ読み込みタイミングでない場合には、ステップＳ６３で、タイミング回路４１によりセレクタ４９−２が、前段の型回路からの照合対象データを選択する。現在の動作サイクルが照合コア回路からのデータ読み込みタイミングである場合には、ステップＳ６４で、タイミング回路４１によりセレクタ４９−２が、照合コア回路からの照合対象データを選択する。
【００７９】
ステップＳ６５で、着目型回路のタイミング回路４１が、現在の動作サイクルが照合タイミング（照合サイクル）であるのか否かを判断する。現在の動作サイクルが照合タイミングでない場合、ステップＳ６６で、着目型回路は、選択したデータを後段の型回路にそのまま送る。その後ステップＳ６８で、動作サイクルが次のサイクルに推移した後、ステップＳ６１に戻り以降の処理を繰り返す。
【００８０】
ステップＳ６５において現在の動作サイクルが照合タイミングであると判断された場合、ステップＳ６７で、照合処理を実行する。即ち、着目型回路の照合回路４２は、前段の型回路から受け取った照合対象データを照合して得られる照合結果と、照合結果バッファ４３に保持されている照合結果とに基づいて新たな照合結果を生成し、生成した照合結果を出力部２５へ出力する。また、着目型回路は、生成した照合結果を照合対象データとともに後段の型回路へ送る。また更に、着目型回路の照合結果バッファ４３には、前段の型回路から受け取った照合結果を新たに保持する。その後ステップＳ６８で、動作サイクルが次のサイクルに推移した後、ステップＳ６１に戻り以降の処理を繰り返す。
【００８１】
図１７は、型回路の照合動作の一例を示すフローチャートである。このフローチャートに示す動作は、図６に示す型回路のように照合コア回路に接続されない複線式の型回路により実行される。
【００８２】
ステップＳ７１で、着目型回路は、複数のストリームデータの一部（複数の照合対象データの一部）と、それらに対応する照合結果とを前段の型回路から受け取る。ステップＳ７２で、着目型回路のタイミング回路５１は、自段の照合対象として割り当てられている照合コア回路を起源とする照合対象データと、それに対応する照合結果とを選択する。ステップＳ７３で、着目型回路の照合回路５２は、選択した照合対象データを照合して得られる照合結果と、照合結果バッファ５３に保持されている照合結果とに基づいて新たな照合結果を生成し、生成した照合結果を出力部２５へ出力する。更に、着目型回路は、生成した照合結果を、選択した照合対象データとともに後段の型回路へ送る。また更に、着目型回路の照合結果バッファ５３には、選択した照合結果を新たに保持する。ステップＳ７４で、着目型回路は、選択しなかった照合対象データ及び照合結果を後段の型回路へ送る。その後ステップＳ７５で、動作サイクルが次のサイクルに推移した後、ステップＳ７１に戻り以降の処理を繰り返す。
【００８３】
図１８は、型回路の照合動作の一例を示すフローチャートである。このフローチャートに示す動作は、図７に示す型回路のように照合コア回路に接続される複線式の型回路により実行される。
【００８４】
ステップＳ８１で、着目型回路は、複数のストリームデータの一部（複数の照合対象データの一部）と、それらに対応する照合結果とを前段の型回路から受け取ると共に、一つのストリームデータの一部（照合対象データの一部）を照合コア回路から受け取る。ステップＳ８２で、着目型回路のタイミング回路５１は、自段の照合対象として割り当てられている照合コア回路を起源とする照合対象データと、対応する照合結果とを選択する。ステップＳ８３で、着目型回路の照合回路５２は、選択した照合対象データを照合して得られる照合結果と、照合結果バッファ５３に保持されている照合結果とに基づいて新たな照合結果を生成し、生成した照合結果を出力部２５へ出力する。更に、着目型回路は、ステップＳ８２で選択したデータの配線番号に対し、その配線番号＋１の配線を介して、生成した照合結果を選択した照合対象データとともに後段の型回路へ送る。このとき、照合コア回路についてのデータは、配線番号１の配線を介して後段の型回路へ送る。また更に、着目型回路の照合結果バッファ５３には、選択した照合結果を新たに保持する。ステップＳ８４で、着目型回路は、入力側の配線番号に対して配線番号＋１の配線を介して、選択しなかった照合対象データ及び照合結果を後段の型回路へ送る。なお入力側の最終配線番号の配線のデータは破棄される。その後ステップＳ８５で、動作サイクルが次のサイクルに推移した後、ステップＳ８１に戻り以降の処理を繰り返す。
【００８５】
図１９は、型回路の照合動作の一例を示すフローチャートである。このフローチャートに示す動作は、図８に示す型回路のように照合コア回路に接続されない時分割式且つ複線式の型回路により実行される。
【００８６】
ステップＳ９１で、着目型回路は、複数のストリームデータの一部（複数の照合対象データの一部）と、それらに対応する照合結果とを前段の型回路から受け取る。ステップＳ９２で、着目型回路のタイミング回路６１は、自段の照合対象として割り当てられている照合コア回路を起源とする照合対象データと、それに対応する照合結果とを選択する。ステップＳ９３で、着目型回路のタイミング回路６１が、現在の動作サイクルが照合タイミング（照合サイクル）であるのか否かを判断する。例えば２サイクルでの時分割動作の場合、着目型回路にとって、例えば偶数サイクルが照合タイミング（照合サイクル）であり、奇数サイクルが照合タイミング（照合サイクル）でないことになる。
【００８７】
ステップＳ９３において現在の動作サイクルが照合タイミングでないと判断された場合、ステップＳ９４で、着目型回路は、受け取ったデータを後段の型回路にそのまま送る。その後ステップＳ９６で、動作サイクルが次のサイクルに推移した後、ステップＳ９１に戻り以降の処理を繰り返す。
【００８８】
ステップＳ９３において現在の動作サイクルが照合タイミングであると判断された場合、ステップＳ９５で、照合処理を実行する。即ち、着目型回路の照合回路６２は、選択した照合対象データを照合して得られる照合結果と、照合結果バッファ６３に保持されている照合結果とに基づいて新たな照合結果を生成し、生成した照合結果を出力部２５へ出力する。また、着目型回路は、生成した照合結果を照合対象データとともに後段の型回路へ送る。また更に、着目型回路の照合結果バッファ６３には、選択した照合結果を新たに保持する。なお選択しなかった照合対象データ及び照合結果も、後段の型回路に送られる。その後ステップＳ９６で、動作サイクルが次のサイクルに推移した後、ステップＳ９１に戻り以降の処理を繰り返す。
【００８９】
図２０は、型回路の照合動作の一例を示すフローチャートである。このフローチャートに示す動作は、図９に示す型回路のように照合コア回路に接続される時分割式且つ複線式の型回路により実行される。
【００９０】
ステップＳ１０１で、着目型回路は、複数のストリームデータの一部（複数の照合対象データの一部）と、それらに対応する照合結果とを前段の型回路から受け取ると共に、一つのストリームデータの一部（照合対象データの一部）を照合コア回路から受け取る。ステップＳ１０２で、着目型回路のタイミング回路６１は、現在の動作サイクルが照合コア回路からのデータ読み込みタイミング（サイクル）であるか否かを判断する。現在の動作サイクルが照合コア回路からのデータ読み込みタイミングでない場合には、ステップＳ１０３に進む。ステップＳ１０３で、タイミング回路６１によりセレクタ６８−３が、自段の照合対象として割り当てられている配線が前段の型回路からの複数の配線中に有れば、その照合対象データと、それに対応する照合結果とを選択する。現在の動作サイクルが照合コア回路からのデータ読み込みタイミングである場合には、ステップＳ１０４で、タイミング回路６１によりセレクタ６８−３が、直接接続の照合コア回路からの照合対象データを選択する。なお現在の動作サイクルにおいて前段の型回路から供給される最終配線番号の配線のデータは、破棄される。この破棄されたデータの位置に、直接接続の照合コア回路からの照合対象データが挿入されることになる。
【００９１】
ステップＳ１０５で、着目型回路のタイミング回路６１が、現在の動作サイクルが照合タイミング（照合サイクル）であるのか否かを判断する。現在の動作サイクルが照合タイミングでない場合、ステップＳ１０６で、着目型回路は、入力側の配線番号に対して配線番号＋１の配線を介して、破棄していない照合対象データ及び照合結果を後段の型回路へ送る。この際、最終配線番号の配線のデータは配線番号１のデータとして、後段の型回路へ送る。なお、この配線番号１のデータの中には、直接接続の照合コア回路のデータも含まれる。その後ステップＳ１０８で、動作サイクルが次のサイクルに推移した後、ステップＳ１０１に戻り以降の処理を繰り返す。
【００９２】
ステップＳ１０５において現在の動作サイクルが照合タイミングであると判断された場合、ステップＳ１０７で、照合処理を実行する。即ち、着目型回路の照合回路６２は、選択した照合対象データを照合して得られる照合結果と、照合結果バッファ６３に保持されている照合結果とに基づいて新たな照合結果を生成し、生成した照合結果を出力部２５へ出力する。更に、着目型回路は、ステップＳ１０３又はＳ１０４で選択したデータの配線番号に対し、その配線番号＋１の配線を介して、生成した照合結果を選択した照合対象データとともに後段の型回路へ送る。このとき、最終配線番号の配線のデータは配線番号１の配線を介して後段の型回路へ送る。なお、入力側の配線番号に対して配線番号＋１の配線を介して、選択しなかった照合対象データ及び照合結果も後段の型回路へ送られる。また更に、着目型回路の照合結果バッファ６３には、選択した照合結果を新たに保持する。その後ステップＳ１０８で、動作サイクルが次のサイクルに推移した後、ステップＳ１０１に戻り以降の処理を繰り返す。
【００９３】
図２１乃至図３３は、時分割式の場合の照合対象データの伝搬の一例を示す図である。この例では、２サイクルでの時分割を想定している。図２１乃至図３３において、同一又は対応する構成要素は同一又は対応する番号で参照し、その説明は適宜省略する。
【００９４】
図２１において、型回路１３１乃至１４３は、例えば図２示す構成のようにリング状に直列に接続された複数の型回路の一部に相当する。型回路１３２に照合コア回路１２０−１が接続され、型回路１３７に照合コア回路１２０−２が接続され、型回路１４２に照合コア回路１２０−３が接続されている。図２１に示されるように、型回路１３２乃至１３６には、照合コア回路１２０−１からの照合対象データを照合するための第１の正規表現パターン「[AB]+.{1,3}[BC]?.*[^0]」が割り当てられている。また型回路１３７乃至１３８には、照合コア回路１２０−１からの照合対象データを照合するための第２の正規表現パターン「P[0]*」が割り当てられている。また型回路１３９乃至１４１には、照合コア回路１２０−２からの照合対象データを照合するための第３の正規表現パターン「ST?[0-9]+」が割り当てられている。また更に、型回路１４２には、照合コア回路１２０−３からの照合対象データを照合するための第４の正規表現パターン「V」が割り当てられている。
【００９５】
利用可能範囲１５０は、照合コア回路１２０−１が、自らの供給する照合対象データを照合させる型回路として利用可能な型回路のグループを示す。この利用可能範囲１５０に属する型回路のみが、照合コア回路１２０−１からの照合対象データを照合可能であり、この利用可能範囲１５０に属しない型回路が、照合コア回路１２０−１からの照合対象データを照合することはない。
【００９６】
図２２は、第１サイクルの様子を示す。奇数サイクルである第１サイクルで、照合コア回路１２０−１、１２０−２及び１２０−３から、それぞれ対応する型回路１３２、１３７及び１４２に、それぞれ対応するストリームデータ（照合対象データ）の第１番目の部分を供給する。型回路１３２及び１４２は、奇数サイクルにて照合するように設定されており、それぞれ対応するストリームデータ（照合対象データ）の第１番目の部分を照合する。型回路１３７は、偶数サイクルにて照合するように設定されており、照合コア回路１２０−２からの照合対象データに対する照合は行わない。
【００９７】
図２３は、第２サイクルの様子を示す。偶数サイクルである第２サイクルで、照合コア回路１２０−１、１２０−２及び１２０−３から、それぞれ対応する型回路１３２、１３７及び１４２には、ストリームデータは供給されない。型回路１３２、１３７及び１４２から、次の型回路１３３、１３８及び１４３に、それぞれ対応するストリームデータ（照合対象データ）の第１番目の部分が供給される。型回路１３３は、偶数サイクルにて照合するように設定されており、対応するストリームデータ（照合対象データ）の第１番目の部分を照合する。型回路１３８は、奇数サイクルにて照合するように設定されており、照合コア回路１２０−２からの照合対象データに対する照合は行わない。
【００９８】
図２４は、第３サイクルの様子を示す。奇数サイクルである第３サイクルで、照合コア回路１２０−１、１２０−２及び１２０−３から、それぞれ対応する型回路１３２、１３７及び１４２に、それぞれ対応するストリームデータ（照合対象データ）の第２番目の部分を供給する。型回路１３２及び１４２は、奇数サイクルにて照合するように設定されており、それぞれ対応するストリームデータ（照合対象データ）の第２番目の部分を照合する。型回路１３７は、偶数サイクルにて照合するように設定されており、照合コア回路１２０−２からの照合対象データに対する照合は行わない。型回路１３３及び１３８から、次の型回路１３４及び１３９に、それぞれ対応するストリームデータ（照合対象データ）の第１番目の部分が供給される。型回路１３４及び１３９は、奇数サイクルにて照合するように設定されており、それぞれ対応するストリームデータ（照合対象データ）の第１番目の部分を照合する。なお型回路１４３の出力については、図面の範囲外となるために図示及び説明をしていない。
【００９９】
このようにして、照合コア回路１２０−１から供給される照合データは、型回路１３７及び１３８では照合されることなく、型回路１３９により初めて照合されることになる。
【０１００】
図２５は第４サイクルの様子、図２６は第５サイクルの様子、図２７は第６サイクルの様子を示す。これらのサイクルでの動作は、上述の奇数サイクル又は偶数サイクルでの動作と同様である。但し、図２７の第６サイクルでは、照合コア回路１２０−２に接続される型回路１３７及び照合コア回路１２０−３に接続される型回路１４２が、前段の型回路から照合対象データの第１の部分を受け取っている。直前の第５サイクルでは、これらの型回路１３７及び型回路１４２は、直接接続される照合コア回路１２０−２及び照合コア回路１２０−３からそれぞれ対応するストリームデータ（照合対象データ）の第３番目の部分を受け取っている。従って、型回路１３７は、連続した２サイクルにおいて、照合コア回路１２０−２からのデータと照合コア回路１２０−１からのデータを受け取ることになる。同様に、型回路１４２は、連続した２サイクルにおいて、照合コア回路１２０−３からのデータと照合コア回路１２０−２からのデータを受け取ることになる。
【０１０１】
これ以降、例えば型回路１３７乃至１４１には、照合コア回路１２０−２からのデータと照合コア回路１２０−１からのデータとが、交互に配置されて伝搬することになる。
【０１０２】
図２８は、第７サイクルの様子を示す。奇数サイクルである第７サイクルで、照合コア回路１２０−１、１２０−２及び１２０−３から、それぞれ対応する型回路１３２、１３７及び１４２に、それぞれ対応するストリームデータ（照合対象データ）の第４番目の部分を供給する。
【０１０３】
以降同様に、図２９は第８サイクルの様子を示し、図３０は第９サイクルの様子を示す。図３０の第９サイクルにおいては、型回路１３７乃至１４１の全ての型回路には、照合コア回路１２０−２からのデータと照合コア回路１２０−１からのデータとが、交互に入力されている。
【０１０４】
図３１は第１０サイクルの様子を示す。照合コア回路１２０−１からの照合対象データの第１番目の部分が、利用可能範囲１５０の最後の型回路１４１に入力されている。
【０１０５】
図３２は、第１１サイクルの様子を示す。利用可能範囲１５０の範囲外にあり、照合コア回路１２０−３に接続される型回路１４２に、照合コア回路１２０−１からの照合対象データの第１番目の部分が到達している。この型回路１４２は、奇数サイクルにおいて照合コア回路１２０−３からのデータを受け取るように設定されているので、照合コア回路１２０−１からの照合対象データの第１番目の部分は受け取られることなく、破棄されることになる。
【０１０６】
図３３は、第１２サイクルの様子を示す。型回路１４２から型回路１４３へは、照合コア回路１２０−３から供給された照合対象データが供給されており、照合コア回路１２０−１から供給された照合対象データは消滅している。
【０１０７】
図３４乃至図４４は、正規表現パターンを割り当てる型回路の選択処理の一例を示す図である。図３４乃至図４４において、図２１と同一又は対応する構成要素は同一又は対応する番号で参照し、その説明は適宜省略する。
【０１０８】
図３４に示すように、利用可能範囲１５０の型回路のうち、型回路１３６、１３９及び１４０において、正規表現パターンが設定されていない。この状態において、照合コア回路１２０−１が、正規表現パターン「[UV][0]+」を設定する型回路を要求する。この要求に応じて、以下に説明するようにして、図２に示される型回路管理部２４に相当する型回路管理部が、正規表現パターン「[UV][0]+」を設定する型回路を選択する。なおこの処理は、図１２のフローチャートに示す処理に相当する。
【０１０９】
まず図３５に示すように、四角枠で囲まれる型回路１３２を対象型回路とする。この対象型回路は使用済みである。次に図３６に示すように、四角枠で囲まれる型回路１３３を対象型回路とする。この対象型回路は使用済みである。図３７乃至図３８でも同様であり、選択された対象型回路は使用済みである。
【０１１０】
図３９において、四角枠で囲まれる型回路１３６を対象型回路とする。この対象型回路は使用済みでない。そこで、この型回路１３６を開始型回路とする（図１２のフローチャートのステップＳ１４参照）。次に図４０に示すように、四角枠で囲まれる型回路１３７を対象型回路とする。この対象型回路は使用済みである。次に図４１に示すように、四角枠で囲まれる型回路１３８を対象型回路とする。この対象型回路は使用済みである。
【０１１１】
その後図４２において、四角枠で囲まれる型回路１３９を対象型回路とする。この対象型回路は使用済みでない。そこで、この型回路１３９を開始型回路とする。次に図４３に示すように、四角枠で囲まれる型回路１４０を対象型回路とする。この対象型回路は使用済みでない。このとき、開始型回路１３９から現在の型回路１４０迄の型回路の数（図１２のフローチャートに示す型回路サイズ）は２であり、設定対象の正規表現パターンの長さに一致する。従って、現在の対象型回路である型回路１４０を終了型回路とする。
【０１１２】
以上のようにして、設定対象の型回路が選択されると、照合コア回路１２０−１が、型回路１３２乃至１３８を介して、正規表現パターン「[UV][0]+」を開始型回路１３９及び終了型回路１４０に書き込む。これにより、図４４に示されるように、正規表現パターン「[UV][0]+」が、開始型回路１３９及び終了型回路１４０に設定される。
【０１１３】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【符号の説明】
【０１１４】
１０  照合コア回路
１１  型回路列
１２−１乃至１２−１４  型回路
２０−１乃至２０−４  照合コア回路
２２−１乃至２２−２８  型回路
２３  ストリームデータ読み出し部
２４  型回路管理部
２５  出力部
【図１】
2014199598.tif 000003
【図２】
2014199598.tif 000004
【図３】
2014199598.tif 000005
【図４】
2014199598.tif 000006
【図５】
2014199598.tif 000007
【図６】
2014199598.tif 000008
【図７】
2014199598.tif 000009
【図８】
2014199598.tif 000010
【図９】
2014199598.tif 000011
【図１０】
2014199598.tif 000012
【図１１】
2014199598.tif 000013
【図１２】
2014199598.tif 000014
【図１３】
2014199598.tif 000015
【図１４】
2014199598.tif 000016
【図１５】
2014199598.tif 000017
【図１６】
2014199598.tif 000018
【図１７】
2014199598.tif 000019
【図１８】
2014199598.tif 000020
【図１９】
2014199598.tif 000021
【図２０】
2014199598.tif 000022
【図２１】
2014199598.tif 000023
【図２２】
2014199598.tif 000024
【図２３】
2014199598.tif 000025
【図２４】
2014199598.tif 000026
【図２５】
2014199598.tif 000027
【図２６】
2014199598.tif 000028
【図２７】
2014199598.tif 000029
【図２８】
2014199598.tif 000030
【図２９】
2014199598.tif 000031
【図３０】
2014199598.tif 000032
【図３１】
2014199598.tif 000033
【図３２】
2014199598.tif 000034
【図３３】
2014199598.tif 000035
【図３４】
2014199598.tif 000036
【図３５】
2014199598.tif 000037
【図３６】
2014199598.tif 000038
【図３７】
2014199598.tif 000039
【図３８】
2014199598.tif 000040
【図３９】
2014199598.tif 000041
【図４０】
2014199598.tif 000042
【図４１】
2014199598.tif 000043
【図４２】
2014199598.tif 000044
【図４３】
2014199598.tif 000045
【図４４】
2014199598.tif 000046