(57)【特許請求の範囲】
【請求項１】
複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数の前記データセットについて繰り返し行うプログラム、が実行されるコンピュータ上のメモリへの、前記複数の前記データセットの配置を行う情報処理装置であって、
前記複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、前記プログラムで処理される順番で連続して配置され、前記特定種別以外のデータについては、同じデータセットのデータが、前記プログラムで処理される順番で連続して配置されるように、前記メモリ上の配置順序を決定する、配置決定手段と、
前記配置順序に従って、前記コンピュータ上の前記メモリへ、前記所定数の前記データセットを配置する、データ配置手段と、
を備えた情報処理装置。
【請求項２】
前記特定種別は、前記複数種別の内、前記プログラムにより前記所定演算が行われる確率が、所定値以上の種別である、
請求項１に記載の情報処理装置。
【請求項３】
さらに、前記配置順序に従って、前記プログラムにおける、前記所定数の前記データセットに係る記載を、当該配置順序に応じた記載に書き換える、プログラム変換手段を備える、
請求項１または２に記載の情報処理装置。
【請求項４】
さらに、前記プログラムにおける、前記所定演算が行われる種別の順番を、前記複数種別の各々の優先度に従って並び替える、並び替え手段を備える、
請求項１乃至３のいずれかに記載の情報処理装置。
【請求項５】
さらに、前記プログラムの前記一連の処理から、前記特定種別のデータに対する前記所定演算を分割し、複数の前記データセットに対するベクトル演算により行うように変更する、構造変更手段を備える、
請求項１乃至４のいずれかに記載の情報処理装置。
【請求項６】
複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数の前記データセットについて繰り返し行うプログラム、が実行されるコンピュータ上のメモリへの、前記複数の前記データセットの配置を行うデータ格納方法であって、
前記複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、前記プログラムで処理される順番で連続して配置され、前記特定種別以外のデータについては、同じデータセットのデータが、前記プログラムで処理される順番で連続して配置されるように、前記メモリ上の配置順序を決定し、
前記配置順序に従って、前記コンピュータ上の前記メモリへ、前記所定数の前記データセットを配置する、
データ格納方法。
【請求項７】
前記特定種別は、前記複数種別の内、前記プログラムにより前記所定演算が行われる確率が、所定値以上の種別である、請求項６に記載のデータ格納方法。
【請求項８】
さらに、前記配置順序に従って、前記プログラムにおける、前記所定数の前記データセットに係る記載を、当該配置順序に応じた記載に書き換える、
請求項６または７に記載のデータ格納方法。
【請求項９】
さらに、前記プログラムにおける、前記所定演算が行われる種別の順番を、前記複数種別の各々の優先度に従って並び替える、
請求項６乃至８のいずれかに記載のデータ格納方法。
【請求項１０】
複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数の前記データセットについて繰り返し行う所定のプログラム、が実行されるコンピュータ上のメモリへの、前記複数の前記データセットの配置を行う情報処理装置のプログラムを格納する記録媒体であって、
前記情報処理装置に、
前記複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、前記所定のプログラムで処理される順番で連続して配置され、前記特定種別以外のデータについては、同じデータセットのデータが、前記所定のプログラムで処理される順番で連続して配置されるように、前記メモリ上の配置順序を決定し、
前記配置順序に従って、前記コンピュータ上の前記メモリへ、前記所定数の前記データセットを配置する、
処理を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、データ格納方法、及び、記録媒体に関する。
【背景技術】
【０００２】
パターンマッチング処理は、比較元データセットと複数の比較先データセットの各々とを比較することで、比較元データセットと合致する比較先データセットを抽出する処理である。比較元データセット、及び、比較先データセットは、複数種別のデータにより構成される。【０００３】
このようなパターンマッチング処理は、比較元データセットと比較先データセットが合致しないことを判定する、複数の非マッチング判定と、比較元データセットと比較先データセットが合致することを判定する、マッチング判定と、を含む。【０００４】
複数の非マッチング判定は、複数の種別にそれぞれ対応し、順番に実行される。各非マッチング判定では、当該非マッチング判定に対応する種別のデータについて、判定が行われる。ある種別までの非マッチング判定の結果、非マッチングと判定された場合、それ以降の種別の非マッチング判定、及び、マッチング判定は行われない。【０００５】
また、マッチング判定では、データセットに含まれる全ての種別のデータを利用して、判定が行われる。【０００６】
比較元データセットと複数の比較先データセットのパターンマッチング処理は、各比較先データセットに対するパターンマッチング処理（ループ処理）を繰り返すことにより行われる。各ループ処理内では、比較先データセットに対する、複数の非マッチング判定とマッチング判定とが行われる。【０００７】
一方、パターンマッチング処理を、コンピュータ上のプログラムにより実行する場合、キャッシュメモリのようなメモリ階層構造とベクトル演算器とを含むプロセッサが利用される。【０００８】
パターンマッチング処理をこのようなプロセッサで高速化する場合、データセットのロードに係る実行時間を短くすることが重要である。【０００９】
このような、データセットのロードに係る実行時間を短くするための技術が、例えば、特許文献１に開示されている。特許文献１に記載の技術では、ループ中で順次アクセスされる複数の配列を一つのグループにグループ化し、グループに属する異なる配列のデータが連続するように、各データがメモリ上に配置される。【００１０】
なお、関連技術として、特許文献２には、プログラム上のループ中に記述されている任意の二つの配列において、一方を他方の配列に置き換えることにより、キャッシュヒット率を向上させる技術が開示されている。また、特許文献３には、プログラム上のループ間の依存関係をもとに、ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振ることにより、キャッシュを有効的に利用する技術が開示されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００４−０２１４２５号公報
【特許文献２】特開２００３−２２８４８８号公報
【特許文献３】特開２０１０−２４４２０４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上述の特許文献１の技術を、非マッチング判定を含むパターンマッチング処理に適用する場合、ループ処理内で順次アクセスされる可能性がある、同じデータセット内の各種別のデータをグループ化し、連続してメモリに配置することが考えられる。しかしながら、上述のように、パターンマッチング処理では、ある種別までの非マッチング判定の結果、非マッチングと判定された場合、それ以降の種別の非マッチング判定は行われない。このため、同じデータセット内のデータを連続してメモリに配置しても、順次アクセスされるとは限らず、キャッシュメモリが有効に利用されない。【００１３】
本発明の目的は、上述した課題を解決し、複数種別のデータを含むデータセット間のパターンマッチング処理を高速に実行する、情報処理装置、データ格納方法、及び、記録媒体を提供することである。
【課題を解決するための手段】
【００１４】
本発明の一態様における情報処理装置は、複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数の前記データセットについて繰り返し行うプログラム、が実行されるコンピュータ上のメモリへの、前記複数の前記データセットの配置を行う情報処理装置であって、前記複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、前記プログラムで処理される順番で連続して配置され、前記特定種別以外のデータについては、同じデータセットのデータが、前記プログラムで処理される順番で連続して配置されるように、前記メモリ上の配置順序を決定する、配置決定手段と、前記配置順序に従って、前記コンピュータ上の前記メモリへ、前記所定数の前記データセットを配置する、データ配置手段と、を備える。【００１５】
本発明の一態様におけるデータ格納方法は、複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数の前記データセットについて繰り返し行うプログラム、が実行されるコンピュータ上のメモリへの、前記複数の前記データセットの配置を行うデータ格納方法であって、前記複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、前記プログラムで処理される順番で連続して配置され、前記特定種別以外のデータについては、同じデータセットのデータが、前記プログラムで処理される順番で連続して配置されるように、前記メモリ上の配置順序を決定し、前記配置順序に従って、前記コンピュータ上の前記メモリへ、前記所定数の前記データセットを配置する。【００１６】
本発明の一態様におけるコンピュータが読み取り可能な記録媒体は、複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数の前記データセットについて繰り返し行うプログラム、が実行されるコンピュータ上のメモリへの、前記複数の前記データセットの配置を行う情報処理装置のプログラムを格納する記録媒体であって、前記情報処理装置に、前記複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、前記プログラムで処理される順番で連続して配置され、前記特定種別以外のデータについては、同じデータセットのデータが、前記プログラムで処理される順番で連続して配置されるように、前記メモリ上の配置順序を決定し、前記配置順序に従って、前記コンピュータ上の前記メモリへ、前記所定数の前記データセットを配置する、処理を実行させるプログラムを格納する。
【発明の効果】
【００１７】
本発明の効果は、複数種別のデータを含むデータセット間のパターンマッチング処理を高速に実行できることである。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【図２】本発明の第１の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【図３】本発明の第１の実施の形態における、コンピュータにより実現されたデータ格納装置２００の構成を示すブロック図である。
【図４】本発明の第１の実施の形態における、パターンマッチング処理で用いられるデータセットの例を示す図である。
【図５】本発明の第１の実施の形態における、マッチングプログラム９００の構成を示す図である。
【図６】本発明の第１の実施の形態における、各非マッチング判定処理９３０−ｊがアクセスするデータを示す図である。
【図７】本発明の第１の実施の形態における、マッチングプログラム９００の処理を示すフローチャートである。
【図８】本発明の第１の実施の形態における、データ格納処理を示すフローチャートである。
【図９】本発明の第１の実施の形態における、メモリ１０３上でのデータの配置順序を示す図である。
【図１０】本発明の第２の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【図１１】本発明の第２の実施の形態における、データ格納処理を示すフローチャートである。
【図１２】本発明の第２の実施の形態における、マッチングプログラム９００のプログラムコードの例を示す図である。
【図１３】本発明の第２の実施の形態における、マッチングプログラム９００の変換後のプログラムコードの例を示す図である。
【図１４】本発明の第２の実施の形態における、マッチングプログラム９００の変換例を示す図である。
【図１５】本発明の第２の実施の形態における、マッチングプログラム９００の変換後のプログラムコードの他の例を示す図である。
【図１６】本発明の第３の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【図１７】本発明の第３の実施の形態における、データ格納処理を示すフローチャートである。
【図１８】本発明の第３の実施の形態における、非マッチング判定処理９３０−ｊの優先度の例を示す図である。
【図１９】本発明の第３の実施の形態における、非マッチング判定処理９３０−ｊの並び替えの例を示す図である。
【図２０】本発明の第３の実施の形態における、メモリ１０３上でのデータの配置順序を示す図である。
【図２１】本発明の第４の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【図２２】本発明の第４の実施の形態における、データ格納処理を示すフローチャートである。
【図２３】本発明の第４の実施の形態における、ループの分割の例を示す図である。
【図２４】本発明の第４の実施の形態における、変換後のマッチングプログラム９００のプログラムコードの例を示す図である。
【図２５】本発明の第４の実施の形態における、変換後のマッチングプログラム９００のプログラムコードの他の例を示す図である。
【図２６】本発明の第４の実施の形態における、変換後のマッチングプログラム９００のプログラムコードの他の例を示す図である。
【図２７】本発明の第５の実施の形態における、ループの分割の例を示す図である。
【図２８】本発明の第６の実施の形態におけるパターンマッチングシステムの構成を示すブロック図である。
【図２９】本発明の第６の実施の形態における、データ格納処理を示すフローチャートである。
【発明を実施するための形態】
【００１９】
（第１の実施の形態）
本発明の第１の実施の形態について説明する。
【００２０】
はじめに、本発明の第１の実施の形態における、パターンマッチング処理について説明する。
【００２１】
図４は、本発明の第１の実施の形態における、パターンマッチング処理で用いられるデータセットの例を示す図である。
【００２２】
パターンマッチング処理では、図４に示すように、一つの比較元データセット８０１「Ｓ」とＭ個（Ｍは１以上の整数）の比較先データセット８０２「Ｆｉ（ｉは１からＭの整数）」が用いられる。比較元データセット８０１と比較先データセット８０２とは、それぞれ、Ｎ種別（Ｎは１以上の整数）のデータ「ｄｊ（ｊは１からＮの整数）」より構成される。以下、比較元データセット８０１におけるｊ番目のデータを「Ｓ−ｄｊ」と記述する。また、ｉ番目の比較先データセット８０２におけるｊ番目のデータを「Ｆｉ−ｄｊ」と記述する。
【００２３】
次に、本発明の第１の実施の形態のパターンマッチング処理について説明する。
【００２４】
本発明の第１の実施の形態では、コンピュータ上で、パターンマッチングプログラム（マッチングプログラム９００）を実行することにより、パターンマッチング処理が行われる。
【００２５】
図５は、本発明の第１の実施の形態における、マッチングプログラム９００の構成を示す図である。
【００２６】
マッチングプログラム９００は、比較元データセット取得処理９１０、比較先データセット選択処理９２０、Ｎ個の非マッチング判定処理９３０−ｊ（ｊは１からＮの整数）、及び、マッチング判定処理９４０を含む。
【００２７】
比較元データセット取得処理９１０は、メモリに格納されている、比較元データセット８０１を取得する。比較先データセット選択処理９２０は、比較元データセット８０１とパターンマッチングを行う、比較先データセット８０２を選択する。非マッチング判定処理９３０−ｊは、データ「ｄｊ」について、比較元データセット８０１と比較先データセット８０２との間で、非マッチング判定を行う。マッチング判定処理９４０は、比較元データセット８０１と比較先データセット８０２との間で、マッチング判定を行う。
【００２８】
図６は、本発明の第１の実施の形態における、各非マッチング判定処理９３０−ｊがアクセスするデータを示す図である。
【００２９】
非マッチング判定処理９３０−ｊは、図６に示すように、メモリ１０３に格納されている、データ「ｄｊ」（「Ｓ−ｄｊ」、及び、「Ｆｉ−ｄｊ」）にアクセスする。
【００３０】
図７は、本発明の第１の実施の形態における、マッチングプログラム９００の処理を示すフローチャートである。
【００３１】
比較元データセット取得処理９１０は、比較元データセット８０１を取得する（ステップＳ９０１）。
【００３２】
比較先データセット選択処理９２０は、比較先データセット８０２の中から、処理対象の比較先データセット８０２を一つ選択する（ステップＳ９０２）。
【００３３】
非マッチング判定処理９３０−ｊは、比較元データセット８０１と比較先データセット８０２との間で、データセットにおけるデータｄｊに対する非マッチング判定（所定演算）を行う(ステップＳ９０３）。各非マッチング判定処理９３０−ｊによる、非マッチング判定は、マッチングプログラム９００に従った順番で行われる。図７の例では、非マッチング判定処理９３０−１、９３０−２、…、９３０−Ｎの順番に、非マッチング判定が行われる。
【００３４】
各非マッチング判定処理９３０−ｊは、例えば、比較元データセット８０１と比較先データセット８０２との間で、データｄｊの差分の絶対値を算出する。そして、非マッチング判定処理９３０−ｊは、例えば、差分の絶対値が所定の閾値以上の場合、非マッチングと判定する。
【００３５】
各非マッチング判定処理９３０−ｊで非マッチングと判定された場合、ステップＳ９０２の処理に戻る。各非マッチング判定処理９３０−ｊで非マッチングと判定されなかった場合（所定条件を満たした場合）は、マッチングプログラム９００に従って、次の非マッチング判定処理９３０−ｊで非マッチング判定が行われる。
【００３６】
Ｎ個の非マッチング判定処理９３０−ｊで非マッチングと判定されなかった場合、マッチング判定処理９４０は、比較元データセット８０１と比較先データセット８０２との間で、マッチング判定を行う（ステップＳ９０４）。
【００３７】
マッチング判定処理９４０は、例えば、比較元データセット８０１と比較先データセット８０２との間で、各データの差分の絶対値に所定の係数を乗じて加算する等、予め決められた演算を行う。そして、マッチング判定処理９４０は、例えば、演算の結果得られた値が所定の閾値未満の場合、マッチングと判定する。
【００３８】
比較先データセット選択処理９２０からマッチング判定処理９４０までは、ループを構成する。ループは、比較先データセット８０２の数だけ繰り返される。
【００３９】
次に、本発明の第１の実施の形態の構成を説明する。
【００４０】
図２は、本発明の第１の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。図２を参照すると、パターンマッチングシステムは、マッチングプログラム９００によりパターンマッチング処理を実行するコンピュータ１００、及び、コンピュータ１００のメモリ１０３に比較先データセット８０２を格納するデータ格納装置２００を含む。データ格納装置２００は、本発明の情報処理装置の一実施形態である。
【００４１】
コンピュータ１００は、ＣＰＵ１０１（Central Processing Unit）、キャッシュメモリ１０２、及び、メモリ１０３を含む。
【００４２】
ＣＰＵ１０１は、マッチングプログラム９００を実行する。
【００４３】
メモリ１０３は、比較元データセット８０１、及び、比較先データセット８０２を記憶する。また、メモリ１０３は、マッチングプログラム９００を格納する。
【００４４】
キャッシュメモリ１０２は、ＣＰＵ１０１上でマッチングプログラム９００の処理が実行された時に、メモリ１０３から読み出されたデータを格納する。キャッシュメモリ１０２は、メモリ１０３上で、ＣＰＵ１０１により読み出されたデータから連続して所定の範囲に格納されているデータを、同時に格納する。キャッシュメモリ１０２にさらにデータを格納する容量がなくなった場合、新たなデータを格納するために、古いデータが削除される。ＣＰＵ１０１は、メモリ１０３から読み出すべきデータがキャッシュに存在する場合、当該キャッシュに格納されているデータを読み出す。
【００４５】
データ格納装置２００は、データ格納制御部２１０を含む。データ格納制御部２１０は、非マッチング判定解析部２１１、アクセス確率算出部２１２、配置決定部２１３、及び、データ配置部２１４を含む。
【００４６】
非マッチング判定解析部２１１は、マッチングプログラム９００における各非マッチング判定処理９３０−ｊが、非マッチング判定を行う順序を解析する。
【００４７】
アクセス確率算出部２１２は、比較先データセット８０２のデータｄｊへのアクセス確率を算出する。
【００４８】
配置決定部２１３は、アクセス確率算出部２１２により算出されたデータへのアクセス確率をもとに、比較先データセット８０２のメモリ１０３への配置順序を決定する。
【００４９】
データ配置部２１４は、決定した順序に従って、比較先データセット８０２をメモリ１０３へ配置する。
【００５０】
なお、データ格納装置２００は、ＣＰＵとプログラムを記憶した記憶媒体を含み、プログラムに基づく制御によって動作するコンピュータであってもよい。
【００５１】
図３は、本発明の第１の実施の形態における、コンピュータにより実現されたデータ格納装置２００の構成を示すブロック図である。データ格納装置２００は、ＣＰＵ２０１、ハードディスクやメモリ等の記憶手段（記憶媒体）２０２、他の装置等とデータ通信を行う通信手段２０３、キーボード等の入力手段２０４、及び、ディスプレイ等の出力手段２０５を含む。
【００５２】
ＣＰＵ２０１は、データ格納制御部２１０の機能を実現するためのコンピュータプログラムを実行する。記憶手段２０２は、データ格納制御部２１０の機能を実現するためのコンピュータプログラムやコンピュータ１００から取得したマッチングプログラム９００を記憶する。通信手段２０３は、コンピュータ１００へ比較先データセット８０２の格納指示を送信する。また、通信手段２０３は、コンピュータ１００との間でマッチングプログラム９００を送受信してもよい。入力手段２０４は、データ格納の指示の入力を受け付ける。出力手段２０５は、データ格納の結果を出力する。
【００５３】
また、図２に示したデータ格納装置２００の各構成要素は、独立した論理回路でもよい。
【００５４】
また、本発明の第１の実施の形態では、コンピュータ１００とデータ格納装置２００とを別の装置としたが、データ格納装置２００が、コンピュータ１００上に実装されていてもよい。
【００５５】
次に、本発明の第１の実施の形態の動作を説明する。
【００５６】
ここでは、図４の比較先データセット８０２を、コンピュータ１００のメモリ１０３に格納する場合を例に、動作を説明する。
【００５７】
図８は、本発明の第１の実施の形態における、データ格納処理を示すフローチャートである。
【００５８】
はじめに、データ格納装置２００は、管理者等から、データ格納の指示を受け付けると、マッチングプログラム９００を取得する（ステップＳ１０１）。
【００５９】
例えば、データ格納装置２００は、コンピュータ１００から、図５のマッチングプログラム９００を取得する。
【００６０】
非マッチング判定解析部２１１は、マッチングプログラム９００における各非マッチング判定処理９３０−ｊが、非マッチング判定を行う順序を解析する（ステップＳ１０２）。
【００６１】
例えば、非マッチング判定解析部２１１は、図５のマッチングプログラム９００において、非マッチング判定処理９３０−１から、９３０−２、…、９３０−Ｎの順番に、非マッチング判定が行われることを検出する。
【００６２】
アクセス確率算出部２１２は、比較先データセット８０２のデータｄｊへのアクセス確率を算出する（ステップＳ１０３）。
【００６３】
ここで、データｄｊへのアクセス確率は、非マッチング判定処理９３０−ｊが非マッチング判定を行う確率（非マッチング判定処理９３０−ｊによる非マッチング判定までの到達率）に相当する。非マッチング判定処理９３０−ｊが非マッチング判定を行う確率は、最初の種別に対する非マッチング判定から直前の種別に対する非マッチング判定の各々で「非マッチング」と判定される確率（非マッチング確率）をもとに算出される。各種別の非マッチング確率は、例えば、管理者等により、予め設定される。また、各種別の非マッチング確率は、パターンマッチング処理の実行時に、コンピュータ１００において取得されてもよい。なお、各比較先データセット８０２で最初に非マッチング判定が行われる種別のアクセス確率は「１００％」である。
【００６４】
例えば、各種別のデータの非マッチング確率が「５０％」の場合、アクセス確率算出部２１２は、データｄ１、ｄ２、ｄ３…へのアクセス確率を、それぞれ、「１００％」、「５０％」、「２５％」…と算出する。
【００６５】
配置決定部２１３は、アクセス確率算出部２１２により算出されたアクセス確率をもとに、比較先データセット８０２のメモリ１０３への配置順序を決定する（ステップＳ１０４）。
【００６６】
ここで、配置決定部２１３は、アクセス確率が「１００％」の種別のデータについては、配置順序を「データセット間方向」に決定する。「データセット間方向」とは、異なる比較先データセット８０２のデータが、マッチングプログラム９００で処理される順番に、連続して配置されることを示す。また、配置決定部２１３は、アクセス確率が「１００％」未満の種別のデータについては、配置順序を「データセット内方向」に決定する。「データセット内方向」とは、同じ比較先データセット８０２のデータが、非マッチング判定が行われる順番に、連続して配置されることを示す。
【００６７】
図９は、本発明の第１の実施の形態における、メモリ１０３上でのデータの配置順序を示す図である。例えば、配置決定部２１３は、アクセス確率が「１００％」のデータｄ１については、図９に示すように、「Ｆ１−ｄ１」、「Ｆ２−ｄ１」、…、「ＦＭ−ｄ１」の順に、配置順序を決定する。また、配置決定部２１３は、アクセス確率が「１００％」未満のデータｄ２、…、ｄＮについては、「Ｆ１−ｄ２」、「Ｆ１−ｄ３」、…、「Ｆ１−ｄＮ」、「Ｆ２−ｄ２」、「Ｆ２−ｄ３」、…、「Ｆ２−ｄＮ」、…の順に、配置順序を決定する。
【００６８】
なお、複数の種別のアクセス確率が「１００％」の場合、配置決定部２１３は、それぞれの種別のデータ配置順序を「データセット間方向」に決定する。例えば、データｄ１、ｄ２のアクセス確率が「１００％」の場合、配置決定部２１３は、データｄ１、ｄ２について、「Ｆ１−ｄ１」、「Ｆ２−ｄ１」、…、「ＦＭ−ｄ１」、「Ｆ１−ｄ２」、「Ｆ２−ｄ２」、…、「ＦＭ−ｄ２」の順に、配置順序を決定する。
【００６９】
データ配置部２１４は、決定した配置順序に従って、比較先データセット８０２をコンピュータ１００のメモリ１０３上へ配置する（ステップＳ１０５）。
【００７０】
ここで、データ配置部２１４は、管理者等から入力された比較先データセット８０２を、決定した配置順序に従って、コンピュータ１００のメモリ１０３上に配置してもよい。また、データ配置部２１４は、メモリ１０３上に既に格納されている比較先データセット８０２を、決定した配置順序に従って配置し直してもよい。
【００７１】
例えば、データ配置部２１４は、図９の配置順序に従って、図４の比較先データセット８０２をメモリ１０３上に配置する。
【００７２】
このように、本発明の第１の実施の形態では、アクセス確率が「１００％」の種別のデータについては、「データセット間方向」に配置される。したがって、ある比較先データセット８０２のデータと次に処理される比較先データセット８０２のデータは、同時にキャッシュメモリ１０２に格納される。そして、次に処理される比較先データセット８０２のデータは、キャッシュメモリ１０２から読み出される。これにより、ＣＰＵ１０１からメモリ１０３へのアクセスが低減される。
【００７３】
また、アクセス確率が「１００％」未満の種別のデータについては、「データセット内方向」に配置される。したがって、比較先データセット８０２において、ある非マッチング判定で処理されるデータと次の非マッチング判定で処理されるデータは、同時にキャッシュメモリ１０２に格納される。そして、次の非マッチング判定で処理されるデータは、キャッシュメモリ１０２から読み出される。これにより、ＣＰＵ１０１からメモリ１０３へのアクセスが低減される。
【００７４】
最後に、データ格納装置２００は、管理者等へ、データ格納の結果を出力する。
【００７５】
以上により、本発明の第１の実施の形態の動作が完了する。
【００７６】
なお、本発明の第１の実施の形態では、配置決定部２１３が、アクセス確率が「１００％」の種別のデータの配置順序を「データセット間方向」に決定し、アクセス確率が「１００％」未満の種別のデータの配置順序を「データセット内方向」に決定した。しかしながら、これに限らず、配置決定部２１３は、アクセス確率が所定値以上の種別のデータの配置順序を「データセット間方向」に決定し、アクセス確率が所定値未満の種別のデータの配置順序を「データセット内方向」に決定してもよい。
【００７７】
また、配置決定部２１３は、例えば、最初から、管理者等により予め設定された順番までに非マッチング判定が行わる種別のデータの配置順序を「データセット間方向」に決定し、それ以外の種別のデータの配置順序を「データセット内方向」に決定してもよい。
【００７８】
次に、本発明の第１の実施の形態の特徴的な構成を説明する。図１は、本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【００７９】
データ格納装置２００（情報処理装置）は、コンピュータ上のメモリへの、複数のデータセットの配置を行う。コンピュータでは、複数種別のデータを含むデータセットの各種別のデータに対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理（ループ処理）を、所定数のデータセットについて繰り返し行うプログラム、が実行される。
【００８０】
データ格納装置２００は、配置決定部２１３、及び、データ配置部２１４を含む。
【００８１】
配置決定部２１３は、複数種別のデータの内、特定種別のデータについては、異なるデータセットのデータが、プログラムで処理される順番で連続して配置されるように、メモリ上の配置順序を決定する。また、配置決定部２１３は、特定種別以外のデータについては、同じデータセットのデータが、プログラムで処理される順番で連続して配置されるように、メモリ上の配置順序を決定する。
【００８２】
データ配置部２１４は、配置順序に従って、コンピュータ上のメモリへ、所定数のデータセットを配置する。
【００８３】
本発明の第１の実施の形態によれば、複数種別のデータを含むデータセット間のパターンマッチング処理を高速に実行できる。その理由は、配置決定部２１３が、特定種別のデータについては、配置順序を「データセット間方向」に決定し、特定種別以外のデータについては、配置順序を「データセット内方向」に決定するためである。
【００８４】
これにより、例えば、アクセス確率が「１００％」の種別のデータは「データセット間方向」で、アクセス確率が「１００％」未満の種別のデータは「データセット内方向」で、メモリ１０３上に配置される。そして、プログラムで連続して処理されるデータが、同時にキャッシュメモリ１０２に格納される可能性が高くなるため、メモリ１０３へのアクセスが低減され、プログラムが高速に実行される。
【００８５】
（第２の実施の形態）
次に、本発明の第２の実施の形態について説明する。本発明の第２の実施の形態においては、マッチングプログラム９００の記述を、配置順序に対応した記述に変換する点で、本発明の第１の実施の形態と異なる。
【００８６】
はじめに、本発明の第２の実施の形態の構成を説明する。
【００８７】
図１０は、本発明の第２の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【００８８】
本発明の第２の実施の形態におけるデータ格納装置２００は、本発明の第１の実施の形態におけるデータ格納装置２００の構成に加えて、プログラム解析部２２０、及び、プログラム変換部２３０を含む。プログラム解析部２２０は、ループ解析部２２１、及び、非マッチング判定検出部２２２を含む。
【００８９】
ループ解析部２２１は、マッチングプログラム９００におけるループを検出する。
【００９０】
非マッチング判定検出部２２２は、検出されたループ内の、非マッチング判定処理９３０−ｊを検出する。
【００９１】
プログラム変換部２３０は、マッチングプログラム９００の記述を、決定した配置順序に対応した記述に変換する。
【００９２】
次に、本発明の第２の実施の形態の動作を説明する。
【００９３】
図１２は、本発明の第２の実施の形態における、マッチングプログラム９００のプログラムコードの例を示す図である。図１２の例では、比較先データセット８０２の数は、１００である。ここでは、マッチングプログラム９００のプログラムコードが図１２の場合を例に動作を説明する。
【００９４】
図１１は、本発明の第２の実施の形態における、データ格納処理を示すフローチャートである。
【００９５】
はじめに、データ格納装置２００は、マッチングプログラム９００を取得する（ステップＳ２０１）。
【００９６】
例えば、データ格納装置２００は、コンピュータ１００から、図１２のプログラムコードを取得する。
【００９７】
ループ解析部２２１は、マッチングプログラム９００におけるループを検出する（ステップＳ２０２）。非マッチング判定検出部２２２は、検出されたループ内の、非マッチング判定処理９３０−ｊを検出する（ステップＳ２０３）。
【００９８】
例えば、データ格納装置２００は、コンピュータ１００から、図１２のプログラムコードにおいて、ループ（行番号２３〜２８）を検出する。そして、データ格納装置２００は、ループ内の、非マッチング判定処理９３０−１（行番号２４）、９３０−２（行番号２５）、９３０−３（行番号２６）、…を検出する。
【００９９】
各非マッチング判定処理９３０−ｊによる非マッチング判定の順序の解析から、決定した配置順序に従った比較先データセット８０２の配置までの処理（ステップＳ２０４〜Ｓ２０７）は、本発明の第１の実施形態（ステップＳ１０２〜Ｓ１０５）と同様である。
【０１００】
例えば、非マッチング判定解析部２１１は、図１２のプログラムコードにおいて、非マッチング判定処理９３０−１、９３０−２、９３０−３、…の順番に、非マッチング判定が行われることを検出する。そして、配置決定部２１３は、図９に示すように、配置順序を決定する。
【０１０１】
次に、プログラム変換部２３０は、マッチングプログラム９００の記述を、決定した配置順序に対応した記述に変換する（ステップＳ２０８）。ここで、プログラム変換部２３０は、例えば、マッチングプログラム９００における、データ宣言、メモリ確保、データアクセス方法等に係る記載を、配置順序に対応した記述に変換する。
【０１０２】
図１３は、本発明の第２の実施の形態における、マッチングプログラム９００の変換後のプログラムコードの例を示す図である。
【０１０３】
例えば、プログラム変換部２３０は、図１２のプログラムコードにおける、データ宣言（行番号１〜６）、メモリ確保（行番号２０、２１）、及び、データアクセス方法（行番号８〜１５）を、図１３のように変換する。
【０１０４】
以上により、本発明の第２の実施の形態の動作が完了する。
【０１０５】
なお、連続して非マッチング判定が行われる複数の種別のアクセス確率が「１００％」の場合、先に行われる非マッチング判定では、非マッチングと判定されることがないため、当該先の非マッチング判定は不要な判定と考えることができる。この場合、上述のステップＳ２０８において、プログラム変換部２３０が、不要な非マッチング判定に係る非マッチング判定処理９３０−ｊをマッチングプログラム９００から削除してもよい。
【０１０６】
図１４は、本発明の第２の実施の形態における、マッチングプログラム９００の変換例を示す図である。図１５は、本発明の第２の実施の形態における、マッチングプログラム９００の変換後のプログラムコードの他の例を示す図である。図１５の例では、ループに対応する部分のみが示されている。
【０１０７】
例えば、例えば、データｄ１、ｄ２のアクセス確率が「１００％」の場合、プログラム変換部２３０は、図１４、図１５のように、先に行われる非マッチング判定に係る非マッチング判定処理９３０−１を、マッチングプログラム９００から削除する。
【０１０８】
本発明の第２の実施の形態によれば、パターンマッチング処理を行うためのプログラムを、メモリアクセスが低減されたプログラムに変換できる。その理由は、プログラム変換部２３０が、マッチングプログラム９００の記述を、決定した配置順序に対応した記述に変換するためである。
【０１０９】
（第３の実施の形態）
次に、本発明の第３の実施の形態について説明する。本発明の第３の実施の形態においては、非マッチング判定処理９３０−ｊの実行順序を並び替える点で、本発明の第２の実施の形態と異なる。
【０１１０】
はじめに、本発明の第３の実施の形態の構成を説明する。
【０１１１】
図１６は、本発明の第３の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【０１１２】
本発明の第３の実施の形態におけるデータ格納装置２００は、本発明の第２の実施の形態におけるデータ格納装置２００の構成に加えて、非マッチング判定並び替え部（または、並び替え部）２４０を含む。
【０１１３】
非マッチング判定並び替え部２４０は、非マッチング判定処理９３０−ｊの実行順序を、優先度の高い順に並び替える。
【０１１４】
次に、本発明の第３の実施の形態の動作を説明する。
【０１１５】
図１７は、本発明の第３の実施の形態における、データ格納処理を示すフローチャートである。
【０１１６】
はじめに、マッチングプログラム９００の取得から、非マッチング判定処理９３０−ｊの検出までの処理（ステップＳ３０１〜Ｓ３０３）は、本発明の第２の実施の形態（ステップＳ２０１〜Ｓ２０３）と同様である。
【０１１７】
次に、非マッチング判定並び替え部２４０は、非マッチング判定処理９３０−ｊの実行順序を、優先度の高い順に並び替える（ステップＳ３０４）。
【０１１８】
図１８は、本発明の第３の実施の形態における、非マッチング判定処理９３０−ｊの優先度の例を示す図である。図１８の例では、優先度の値が小さいほど、優先度が高いことを示す。
【０１１９】
優先度は、例えば、各非マッチング判定処理９３０−ｊに対応する種別のデータｄｊの非マッチング確率をもとに、非マッチング確率が大きいほど、優先度が高くなるように付与される。
【０１２０】
なお、優先度は、各非マッチング判定処理９３０−ｊにおけるロード命令数等、命令数が少ないほど、優先度が高くなるように付与されてもよい。
【０１２１】
図１９は、本発明の第３の実施の形態における、非マッチング判定処理９３０−ｊの並び替えの例を示す図である。
【０１２２】
例えば、非マッチング判定並び替え部２４０は、図１８の優先度をもとに、非マッチング判定処理９３０−ｊの実行順序を、図１９のように並び替える。この場合、並び替え前は、非マッチング判定処理９３０−１、９３０−２、９３０−３、９３０−４の順番に、非マッチング判定が行われる。並び替え後は、図１８の優先度に従って、非マッチング判定処理９３０−４、９３０−３、９３０−２、９３０−１の順番に、非マッチング判定が行われる。
【０１２３】
各非マッチング判定処理９３０−ｊによる非マッチング判定の順序の解析から、決定した配置順序に従った比較先データセット８０２の配置までの処理（ステップＳ３０５〜Ｓ３０８）は、本発明の第２の実施形態（ステップＳ２０４〜Ｓ２０７）と同様である。
【０１２４】
図２０は、本発明の第３の実施の形態における、メモリ１０３上でのデータの配置順序を示す図である。例えば、配置決定部２１３は、アクセス確率が「１００％」のデータｄ４については、図２０に示すように、「Ｆ１−ｄ４」、「Ｆ２−ｄ４」、…、「ＦＭ−ｄ４」の順に、配置順序を決定する。また、配置決定部２１３は、アクセス確率が「１００％」未満のデータｄ１、ｄ２、ｄ３については、並び替え後の非マッチング判定処理９３０−ｊによる非マッチング判定の実行順序に従って、図２０に示すように、配置順序を決定する。すなわち、配置決定部２１３は、「Ｆ１−ｄ３」、「Ｆ１−ｄ２」、「Ｆ１−ｄ１」、…、「ＦＭ−ｄ３」、「ＦＭ−ｄ２」、「ＦＭ−ｄ１」の順に、配置順序を決定する。
【０１２５】
次に、プログラム変換部２３０は、マッチングプログラム９００の記述を、決定した配置順序、及び、並び替え後の非マッチング判定処理９３０−ｊの実行順序に対応した記述に変換する（ステップＳ３０９）。
【０１２６】
以上により、本発明の第３の実施の形態の動作が完了する。
【０１２７】
本発明の第３の実施の形態によれば、本発明の第１、第２の実施の形態に比べて、パターンマッチング処理をさらに高速に実行できる。その理由は、非マッチング判定並び替え部２４０が、マッチングプログラム９００における、非マッチング判定処理９３０−ｊの実行順序を、優先度の高い順に並び替えるためである。
【０１２８】
これにより、例えば、非マッチング率の高い順に非マッチング判定処理９３０−ｊを実行することで、後段の非マッチング判定処理９３０−ｊを実行する回数が削減される。この場合、非マッチング判定処理９３０−ｊに伴うロード命令数が低減されるため、マッチングプログラム９００がさらに高速に実行される。また、例えば、ロード命令数の少ない順に非マッチング判定処理９３０−ｊを実行することで、ロード命令数が多い非マッチング判定処理９３０−ｊを実行する回数が削減される。この場合も、非マッチング判定処理９３０−ｊに伴うロード命令数が低減されるため、マッチングプログラム９００がさらに高速に実行される。
【０１２９】
（第４の実施の形態）
次に、本発明の第４の実施の形態について説明する。本発明の第４の実施の形態においては、マッチングプログラム９００におけるループを分割してベクトル化する点で、本発明の第２の実施の形態と異なる。
【０１３０】
はじめに、本発明の第４の実施の形態の構成を説明する。
【０１３１】
図２１は、本発明の第４の実施の形態における、パターンマッチングシステムの構成を示すブロック図である。
【０１３２】
本発明の第４の実施の形態におけるデータ格納装置２００は、本発明の第２の実施の形態におけるデータ格納装置２００の構成に加えて、ループ構造変更部（または、構造変更部）２５０を含む。
【０１３３】
ループ構造変更部２５０は、マッチングプログラム９００におけるループを分割する。
【０１３４】
次に、本発明の第４の実施の形態の動作を説明する。
【０１３５】
図２２は、本発明の第４の実施の形態における、データ格納処理を示すフローチャートである。
【０１３６】
はじめに、マッチングプログラム９００の取得から、決定した配置順序に従った比較先データセット８０２の配置までの処理（ステップＳ４０１〜Ｓ４０７）は、本発明の第２の実施の形態（ステップＳ２０１〜Ｓ２０７）と同様である。
【０１３７】
次に、ループ構造変更部２５０は、アクセス確率算出部２１２により算出されたデータへのアクセス確率をもとに、マッチングプログラム９００におけるループを分割する。そして、ループ構造変更部２５０は、分割されたループの一方をベクトル化する（ステップＳ４０８）。ここで、ループ構造変更部２５０は、アクセス確率が「１００％」の種別に対する非マッチング判定処理９３０−ｊの内、判定を伴わない処理（演算）を、別ループ（ループ１）として抽出することにより、ループをループ１とループ２とに分割する。そして、ループ構造変更部２５０は、ループ１をベクトル化する（ループ１を、複数の比較先データセット８０２に対するベクトル演算で行うように指定する）。
【０１３８】
図２３は、本発明の第４の実施の形態における、ループの分割の例を示す図である。
【０１３９】
例えば、ループ構造変更部２５０は、図２３に示すように、図７のマッチングプログラム９００におけるループを、ループ１とループ２に分割する。
【０１４０】
ループ１は、比較先データセット選択処理９２１、非マッチング判定処理９３１−１、及び、テンポラリデータ生成処理９３２−１を含む。比較先データセット選択処理９２１は、比較先データセット選択処理９２０と同様に、比較先データセット８０２を選択する。非マッチング判定処理９３１−１は、非マッチング判定処理９３０−１内の判定を伴わない処理（演算）を行う。テンポラリデータ生成処理９３２−１は、非マッチング判定処理９３１−１の演算結果をテンポラリデータとして生成する。第１のループにより、テンポラリデータは、比較先データセット８０２の数だけ生成される。
【０１４１】
ループ２は、比較先データセット選択処理９２２、非マッチング判定処理９３３−１、及び、非マッチング判定処理９３０−２からマッチング判定処理９４０までを含む。比較先データセット選択処理９２２は、比較先データセット選択処理９２０と同様に、比較先データセット８０２を選択する。非マッチング判定処理９３３−１は、テンポラリデータを用いて、非マッチング判定処理９３０−１の内の判定に係る処理を行う。
【０１４２】
そして、ループ構造変更部２５０は、第１のループをベクトル化する。
【０１４３】
プログラム変換部２３０は、ステップＳ２０８と同様に、マッチングプログラム９００の記述を、決定した配置順序に対応した記述に変換する（ステップＳ４０９）。
【０１４４】
図２４、図２５は、本発明の第４の実施の形態における、変換後のマッチングプログラム９００のプログラムコードの例を示す図である。図２４、図２５の例では、ループに対応する部分のみが示されている。
【０１４５】
例えば、ループ構造変更部２５０は、図１２のプログラムコードにおけるループを、図２４、または、図２５のループ１、ループ２のように分割する。
【０１４６】
図２４は、非マッチング判定処理９３１−１が、非マッチング判定処理９３０−１の内の、差分の算出、及び、閾値との比較を行う場合の例である。この場合、閾値との比較結果がテンポラリデータとして生成される（行番号３４、３５）。また、図２５は、非マッチング判定処理９３１−１が、非マッチング判定処理９３０−１の内の、差分の算出を行う場合の例である。この場合、差分の算出結果がテンポラリデータとして生成される（行番号３３）。また、図２４、図２５において、コンパイラによるループ１のベクトル化が、「#pragma vector」（行番号３１）により指定されている。
【０１４７】
なお、アクセス確率が「１００％」の種別が複数存在する場合、ループ構造変更部２５０は、複数の種別に対する非マッチング判定処理９３０−ｊの内、判定を伴わない処理（演算）を、別ループ（ループ１）として抽出する。
【０１４８】
図２６は、本発明の第４の実施の形態における、変換後のマッチングプログラム９００のプログラムコードの他の例を示す図である。例えば、ループ構造変更部２５０は、図２６のように、非マッチング判定処理９３０−１、９３０−２の処理の内の、差分の算出、及び、閾値との比較を、一つの別ループ（ループ１）として抽出し、ベクトル化する。
【０１４９】
以上により、本発明の第４の実施の形態の動作が完了する。
【０１５０】
本発明の第４の実施の形態によれば、第１、第２の実施の形態に比べて、パターンマッチング処理をさらに高速に実行できる。その理由は、ループ構造変更部２５０が、マッチングプログラム９００のループにおける、特定種別の非マッチング判定処理９３０−ｊを分割し、複数の比較先データセット８０２に対するベクトル演算で行うようにベクトル化するためである。
【０１５１】
これにより、特定種別のデータの非マッチング判定処理９３０−ｊに係るループの繰り返し数（比較先データセット８０２の数）分のロード命令を、当該繰り返し数より少ないベクトルロード命令に変更でき、ロード命令数が低減される。ロード命令数が低減することで、データのロードに必要な時間が短縮され、マッチングプログラム９００がさらに高速に実行される。
【０１５２】
（第５の実施の形態）
次に、本発明の第５の実施の形態について説明する。本発明の第５の実施の形態においては、分割された二つのループを含む、新たなループを生成する点で、本発明の第４の実施の形態と異なる。
【０１５３】
上述のステップＳ４０８において、ループ構造変更部２５０は、マッチングプログラム９００におけるループを分割するとともに、分割された二つのループの繰り返し回数を比較先データセット８０２の数より少なく設定する。ループ構造変更部２５０は、さらに、分割された二つのループが、比較先データセット８０２の数だけ実行されるように、分割された二つのループの繰り返しを含む、新たなループを生成する。
【０１５４】
図２７は、本発明の第５の実施の形態における、ループの分割の例を示す図である。
【０１５５】
例えば、ループ構造変更部２５０は、マッチングプログラム９００におけるループを、図２７に示すように、繰り返し回数Ｋ（Ｋは１以上の整数）のループ１とループ２とに分割する。ここで、繰り返し回数Ｋは、比較先データセット８０２の数より少ない値であり、かつ、ループ１のＫ回の繰り返しにより生成されるテンポラリデータのサイズがキャッシュメモリ１０２のサイズより小さくなるように設定される。
【０１５６】
ループ構造変更部２５０は、さらに、図２７に示すように、Ｋ回のループ１とＫ回のループ２とを含む、繰り返し回数Ｍ／Ｋ回のループ３を生成する。
【０１５７】
そして、ループ構造変更部２５０は、第１のループをベクトル化する。
【０１５８】
本発明の第５の実施の形態によれば、本発明の第４の実施の形態に比べて、パターンマッチング処理をさらに高速に実行できる。その理由は、分割された二つのループの繰り返し回数を比較先データセット８０２の数より少なく設定するためである。これにより、二つのループ間のテンポラリデータがキャッシュメモリ１０２に存在し、ループ２におけるテンポラリデータのロードに必要な時間が短縮され、マッチングプログラム９００がさらに高速に実行される。
【０１５９】
（第６の実施の形態）
次に、本発明の第６の実施の形態について説明する。本発明の第６の実施の形態においては、第３の実施の形態と同様に、非マッチング判定処理９３０−ｊの実行順序を並び替える点、及び、第４、第５の実施の形態と同様に、マッチングプログラム９００におけるループを分割する点で、第２の実施の形態と異なる。
【０１６０】
はじめに、本発明の第６の実施の形態の構成を説明する。
【０１６１】
図２８は、本発明の第６の実施の形態におけるパターンマッチングシステムの構成を示すブロック図である。
【０１６２】
本発明の第４の実施の形態におけるデータ格納装置２００は、本発明の第２の実施の形態におけるデータ格納装置２００の構成に加えて、非マッチング判定並び替え部２４０、及び、ループ構造変更部２５０を含む。
【０１６３】
次に、本発明の第６の実施の形態の動作を説明する。
【０１６４】
図２９は、本発明の第６の実施の形態における、データ格納処理を示すフローチャートである。
【０１６５】
はじめに、マッチングプログラム９００の取得から、非マッチング判定処理９３０−ｊの検出までの処理（ステップＳ６０１〜Ｓ６０３）は、本発明の第２の実施の形態（ステップＳ２０１〜Ｓ２０３）と同様である。
【０１６６】
次に、非マッチング判定並び替え部２４０は、ステップＳ３０４と同様に、非マッチング判定処理９３０−ｊの実行順序を、優先度の高い順に並び替える（ステップＳ６０４）。
【０１６７】
各非マッチング判定処理９３０−ｊによる非マッチング判定の順序の解析から、決定した配置順序に従った比較先データセット８０２の配置までの処理（ステップＳ６０５〜Ｓ６０８）は、本発明の第２の実施形態（ステップＳ２０４〜Ｓ２０７）と同様である。
【０１６８】
次に、ループ構造変更部２５０は、ステップＳ４０８と同様に、アクセス確率算出部２１２により算出されたデータへのアクセス確率をもとに、マッチングプログラム９００におけるループを分割する。そして、ループ構造変更部２５０は、分割されたループの一方をベクトル化する（ステップＳ６０９）。
【０１６９】
プログラム変換部２３０は、ステップＳ３０９と同様に、マッチングプログラム９００の記述を、決定した配置順序、及び、並び替え後の非マッチング判定処理９３０−ｊの実行順序に対応した記述に変換する（ステップＳ６１０）。
【０１７０】
以上により、本発明の第６の実施の形態の動作が完了する。
【０１７１】
本発明の第６の実施の形態によれば、本発明の第３、第４、第５の実施の形態に比べて、パターンマッチング処理をさらに高速に実行できる。その理由は、非マッチング判定並び替え部２４０が、マッチングプログラム９００における、非マッチング判定処理９３０−ｊの実行順序を、優先度の高い順に並び替え、ループ構造変更部２５０が、ループの分割、及び、ベクトル化を行うためである。
【０１７２】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１７３】
例えば、本発明の実施の形態では、配置されるデータセットを用いるプログラムが、パターンマッチングを行うマッチングプログラム９００の場合を例に説明を行った。しかしながら、データセットの各種別に対する所定演算を、順番に、所定の条件を満たす場合に行う一連の処理を、所定数のデータセットについて繰り返し行うプログラムであれば、プログラムは、パターンマッチング以外の他のプログラムでもよい。
【０１７４】
この出願は、２０１４年６月１９日に出願された日本出願特願２０１４−１２５８６５を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１７５】
本発明は、データベースとの比較によって画像を判別する画像認識処理や画像照合処理、データベースとの比較によって個人を特定する生体認証処理等の用途に適用できる。
【符号の説明】
【０１７６】
１００    コンピュータ
１０１    ＣＰＵ
１０２    キャッシュメモリ
１０３    メモリ
２００    データ格納装置
２０１    ＣＰＵ
２０２    記憶手段
２０３    通信手段
２０４    入力手段
２０５    出力手段
２１０    データ格納制御部
２１１    非マッチング判定解析部
２１２    アクセス確率算出部
２１３    配置決定部
２１４    データ配置部
２２０    プログラム解析部
２２１    ループ解析部
２２２    非マッチング判定検出部
２３０    プログラム変換部
２４０    非マッチング判定並び替え部
２５０    ループ構造変更部
８０１    比較元データセット
８０２    比較先データセット
９００    マッチングプログラム
９１０    比較元データセット取得処理
９２０    比較先データセット選択処理
９２１    比較先データセット選択処理
９２２    比較先データセット選択処理
９３０    非マッチング判定処理
９３１    非マッチング判定処理
９３２    テンポラリデータ生成処理
９３３    非マッチング判定処理
９４０    マッチング判定処理
【図１】
0006555259.tif 000002
【図２】
0006555259.tif 000003
【図３】
0006555259.tif 000004
【図４】
0006555259.tif 000005
【図５】
0006555259.tif 000006
【図６】
0006555259.tif 000007
【図７】
0006555259.tif 000008
【図８】
0006555259.tif 000009
【図９】
0006555259.tif 000010
【図１０】
0006555259.tif 000011
【図１１】
0006555259.tif 000012
【図１２】
0006555259.tif 000013
【図１３】
0006555259.tif 000014
【図１４】
0006555259.tif 000015
【図１５】
0006555259.tif 000016
【図１６】
0006555259.tif 000017
【図１７】
0006555259.tif 000018
【図１８】
0006555259.tif 000019
【図１９】
0006555259.tif 000020
【図２０】
0006555259.tif 000021
【図２１】
0006555259.tif 000022
【図２２】
0006555259.tif 000023
【図２３】
0006555259.tif 000024
【図２４】
0006555259.tif 000025
【図２５】
0006555259.tif 000026
【図２６】
0006555259.tif 000027
【図２７】
0006555259.tif 000028
【図２８】
0006555259.tif 000029
【図２９】
0006555259.tif 000030