(57)【要約】【課題】  領域及び点のデータの２つを入力として各点を包含する領域の探索を高速に並列処理する。【解決手段】  並列処理方法は、定義空間上に配置されたＭ個の領域とＮ個の点とをそれぞれ示すデータを入力する入力ステップ（Ｓ０１）と、定義空間を複数の格子に分割して、分割した各格子について、入力された領域及び点のうち当該格子に少なくとも当該領域の一部及び当該点を含む領域及び点を当該格子に仕分ける仕分ステップ（Ｓ０２〜Ｓ０６）と、分割された各格子について一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に当該格子に仕分けられた領域及び点を示すデータを出力する選択ステップ（Ｓ０７，Ｓ０８）と、計算装置のそれぞれが、入力した各点が各領域に含まれるか否かを判定して、判定の結果を出力する計算ステップ（Ｓ０９，Ｓ１０）とを有する。【選択図】  図１２
2013008195.tif 000002
【特許請求の範囲】
【請求項１】
一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法であって、
所定の空間上に配置された一つ以上の領域と当該空間上に配置された一つ以上の点とをそれぞれ示すデータを入力する入力ステップと、
前記空間を複数の格子に分割して、分割した各格子について、前記入力ステップにおいて入力されたデータによって示される領域及び点のうち、当該格子に少なくとも当該領域の一部及び当該点を含む領域及び点を当該格子に仕分ける仕分ステップと、
前記仕分ステップにおいて分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分ステップにおいて当該格子に仕分けられた領域及び点を示すデータを出力する選択ステップと、
前記計算装置のそれぞれが、前記選択ステップにおいて出力されたデータを入力して、当該データによって示される各点が当該データによって示される各領域に含まれるか否かを判定して、判定の結果を出力する計算ステップと、
を有する並列処理方法。
【請求項２】
前記仕分ステップにおいて、前記格子に少なくとも当該領域の一部を含む領域を当該領域全体として仕分けることを特徴とする請求項１に記載の並列処理方法。
【請求項３】
前記仕分ステップにおいて、前記格子に少なくとも当該領域の一部を含む領域を当該領域と当該格子との交差領域として仕分けることを特徴とする請求項１に記載の並列処理方法。
【請求項４】
前記仕分ステップにおいて、各格子に仕分けられた領域の数、各格子に仕分けられた点の数、及びそれらの和の少なくとも何れかが予め設定された閾値を超えているか否かを判断して、閾値を超えていると判断された場合には閾値を超えていた格子を再帰的に更に分割して、分割した各格子について領域及び点を仕分けることを特徴とする請求項１〜３の何れか一項に記載の並列処理方法。
【請求項５】
一台以上の計算装置を含んで構成される並列処理システムであって、
所定の空間上に配置された一つ以上の領域と当該空間上に配置された一つ以上の点とをそれぞれ示すデータを入力する入力手段と、
前記空間を複数の格子に分割して、分割した各格子について、前記入力手段によって入力されたデータによって示される領域及び点のうち、当該格子に少なくとも当該領域の一部及び当該点を含む領域及び点を当該格子に仕分ける仕分手段と、
前記仕分手段によって分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分手段によって当該格子に仕分けられた領域及び点を示すデータを出力する選択手段と、を備え、
前記計算装置のそれぞれが、前記選択手段によって出力されたデータを入力して、当該データによって示される各点が当該データによって示される各領域に含まれるか否かを判定して、判定の結果を出力する、
ことを特徴とする並列処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法、及び当該並列処理システムに関する。
【背景技術】
【０００２】
同じ二次元又は三次元の空間上に配置されたＭ個の領域とＮ個の点との間で（ここでＭ，Ｎは自然数）各点を包含する領域を探索する場合、単一の計算装置上での単純な総当り探索による方法では、「Ｍ×Ｎ」オーダーの計算量を必要とする。Ｍ個の領域及びＮ個の点を何らかの基準に従って予め並べ替え（ソート）してから照合する等のアルゴリズム上の工夫により、単純な総当り探索よりも計算量を削減できる余地はある。しかし、それにも限界があり、また、並べ替え処理自体の計算量が増加する。または、スーパーコンピュータ等の高性能な計算装置を用いることで、総当り探索を高速に完了させることも考えられる。しかし、スーパーコンピュータは非常に高価であり、また、誰でも利用できるわけではない。
【０００３】
ところで、リレーショナルデータベースにおいて、複数のテーブルのデータを組み合わせて結合する操作にＪｏｉｎがある。リレーショナルデータベースにおけるＪｏｉｎ操作を高速化する方法は従来からいくつか提案されている。例えば、組み合わせ対象の一つである主データを複製する方法（従来技術１）や、その考え方を更に推し進めた非特許文献１に記載された方法（従来技術２）等がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“Application of Hash to Data BaseMachine and Its Architecture”，NEW GENERATION COMPUTING Volume 1，Number 1
【発明の概要】
【発明が解決しようとする課題】
【０００５】
今日では、安価な計算装置を多数接続してクラスタを構築し、それらの間で計算負担を分担することで、膨大な計算を高速に完了する方法が主流となってきている。これは、予算に応じて接続する計算装置の種類や台数を任意に決定できること、及びそのような並列処理を実現するためのソフトウェアが広く利用可能になってきたことによる。以上の経緯を踏まえると、Ｍ個の領域とＮ個の点との間で各点を包含する領域を探索する処理を、並列処理により高速化することが考えられる。
【０００６】
すると今度は、上記の探索処理をどのように並列処理するかが問題となる。ところで、上記の探索処理は、Ｍ個の領域からなる入力を主データ、Ｎ個の点からなる入力を従データとして見ると、主従データの突き合わせ処理とみなせる（反対に、Ｎ個の点からなる入力を主データ、Ｍ個の領域からなる入力を従データとしてみなしてもよい）。つまり、リレーショナルデータベースにおけるＪｏｉｎ操作に似た処理となっている（但し、あくまで似ているだけであって、領域や点のデータがリレーショナルデータベースに登録されている必要はない）。
【０００７】
上述した従来技術１では、並列処理を行う計算装置に主データを複製し、その一方で従データを全ての計算装置で（ほぼ）均等に分配する。この方法を上記の探索処理に適用することを想定すると、計算装置１台あたりの計算量は、計算装置の台数をＰとすると「Ｍ×Ｎ÷Ｐ」オーダーとなり、上述の単純な総当りにおける計算量よりも小さくなる。
【０００８】
従来技術１による方法では、主データは全ての計算装置に複製されるため、主データのサイズ、及び計算装置の台数Ｐが大きくなるほど、計算装置群全体で見た場合の複製に要するコストはそれらの積に比例して大きくなる、という問題がある。また、主データの含まれる領域の個数Ｍが非常に大きい場合、計算装置１台あたりの計算量の削減が不十分となる場合が発生しえる。
【０００９】
従来技術２は、主従両方のデータを計算装置に分配するものである。この方法では、主データ全体を計算装置群全体に複製する必要がなくなり、従来技術１に比べて複製に要するコストが削減される。また、従データと同様に、主データも全ての計算装置で（ほぼ）均等に分配すると、計算装置１台あたりの計算量は、「Ｍ×Ｎ÷Ｐ÷Ｐ」オーダーとなり、従来技術１による計算量より小さくなる。
【００１０】
しかしながら、従来技術２は、主従２つのデータが予めリレーショナルデータベースに登録されていることを前提としている。リレーショナルデータベースに登録されているデータは、互いが完全に独立している個々のレコードから構成され、それぞれのレコードには予めキー情報が付与されている。主データは、同じキー情報を共有するレコード群（以下、グループと呼ぶ）を単位として分配される。同様に、従データもグループを単位として分配される。そして、同じキー情報を持つ主データからのグループと従データからのグループとが、計算装置群の中の一つに集められ、結合処理（Ｊｏｉｎ操作）が行われる。
【００１１】
しかしながら、各点を包含する領域を探索する処理では、主データ（Ｍ個の領域）及び従データ（Ｎ個の点）が予めリレーショナルデータベースに登録されていることを前提としない。例えば、ＧＩＳ（Geographic Information System）において広く利用されているＳｈａｐｅｆｉｌｅ形式のファイルや、又は単純なテキストファイルとして用意することなどが考えられる。
【００１２】
このように用意されたデータの場合、主データ及び従データには、予めキー情報が付与されている保証はなく、リレーショナルデータベースに登録されている、キー情報が付与されたデータが利用可能であるという前提をおくことはできない。また、領域や点のデータの何をもって、リレーショナルデータベースにおけるレコードやグループの概念に当てはめるかも自明ではない。従って、各点を包含する領域を探索する処理に対して、データが予めリレーショナルデータベースに登録されていることを前提とする従来技術２を適用することはできない。
【００１３】
本発明は、上記の問題点を鑑みてなされたものであり、領域及び点のデータの２つを入力として各点を包含する領域の探索を高速に並列処理することができる並列処理方法及び並列処理システムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の目的を達成するために、本発明に係る並列処理方法は、一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法であって、所定の空間上に配置された一つ以上の領域と当該空間上に配置された一つ以上の点とをそれぞれ示すデータを入力する入力ステップと、空間を複数の格子に分割して、分割した各格子について、入力ステップにおいて入力されたデータによって示される領域及び点のうち、当該格子に少なくとも当該領域の一部及び当該点を含む領域及び点を当該格子に仕分ける仕分ステップと、仕分ステップにおいて分割された各格子について、一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に仕分ステップにおいて当該格子に仕分けられた領域及び点を示すデータを出力する選択ステップと、計算装置のそれぞれが、選択ステップにおいて出力されたデータを入力して、当該データによって示される各点が当該データによって示される各領域に含まれるか否かを判定して、判定の結果を出力する計算ステップと、を有することを特徴とする。
【００１５】
本発明に係る並列処理方法では、領域及び点のデータの２つを入力としてそれらが配置される空間が複数の格子に分割されて、格子毎に各計算装置において各点を包含する領域を探索する処理が行われる。これにより、領域及び点のデータの２つを入力として各点を包含する領域の探索を高速に並列処理することができる。
【００１６】
仕分ステップにおいて、格子に少なくとも当該領域の一部を含む領域を当該領域全体として仕分けることが望ましい。あるいは、仕分ステップにおいて、格子に少なくとも当該領域の一部を含む領域を当該領域と当該格子との交差領域として仕分けることが望ましい。これらの構成の何れかによれば、各点を包含する領域を探索する処理が行うために適切かつ確実に領域を仕分けることができる。それにより、適切かつ確実に本発明を実施することができる。
【００１７】
仕分ステップにおいて、各格子に仕分けられた領域の数、各格子に仕分けられた点の数、及びそれらの和の少なくとも何れかが予め設定された閾値を超えているか否かを判断して、閾値を超えていると判断された場合には閾値を超えていた格子を再帰的に更に分割して、分割した各格子について領域及び点を仕分けることが望ましい。この構成によれば、一つの格子に属する領域及び点の数を十分に小さくすることが可能となる。これにより、並列処理の負荷分散効果が高くなる。
【００１８】
ところで、本発明は、上記のように並列処理方法の発明として記述できる他に、以下のように並列処理システムの発明としても記述することができる。これはカテゴリが異なるだけで、実質的に同一の発明であり、同様の作用及び効果を奏する。
【００１９】
即ち、本発明に係る並列処理システムは、一台以上の計算装置を含んで構成される並列処理システムであって、所定の空間上に配置された一つ以上の領域と当該空間上に配置された一つ以上の点とをそれぞれ示すデータを入力する入力手段と、空間を複数の格子に分割して、分割した各格子について、入力手段によって入力されたデータによって示される領域及び点のうち、当該格子に少なくとも当該領域の一部及び当該点を含む領域及び点を当該格子に仕分ける仕分手段と、仕分手段によって分割された各格子について、一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に仕分手段によって当該格子に仕分けられた領域及び点を示すデータを出力する選択手段と、を備え、計算装置のそれぞれが、選択手段によって出力されたデータを入力して、当該データによって示される各点が当該データによって示される各領域に含まれるか否かを判定して、判定の結果を出力する、ことを特徴とする。
【発明の効果】
【００２０】
本発明では、領域及び点のデータの２つを入力としてそれらが配置される空間が複数の格子に分割されて、格子毎に各計算装置において各点を包含する領域を探索する処理が行われる。これにより、本発明によれば、領域及び点のデータの２つを入力として各点を包含する領域の探索を高速に並列処理することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係る並列処理システムの機能構成を示す図である。
【図２】本実施形態の例における入力のうち、主データであるＭ個の領域を示す図である。
【図３】本実施形態の例における入力のうち、従データであるＮ個の点を示す図である。
【図４】本実施形態の例において用いられる空間を分割した格子を示す図である。
【図５】本実施形態の例における第１の方法による主データの仕分を示す図である。
【図６】本実施形態の例における第２の方法による主データの仕分を示す図である。
【図７】本実施形態の例における従データの仕分を示す図である。
【図８】本実施形態の例における第１の方法によって計算装置＃１に集められるデータを示す図である。
【図９】本実施形態の例における第２の方法によって計算装置＃１に集められるデータを示す図である。
【図１０】本実施形態の例における探索の最終結果のデータを示す図である。
【図１１】本発明の実施形態に係る並列処理システムを構成する仕分用装置及び計算装置のハードウェア構成を示す図である。
【図１２】本発明の実施形態に係る並列処理システムで実行される処理（並列処理方法）を示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、図面と共に本発明に係る並列処理方法及び並列処理システムの好適な実施形態について詳細に説明する。なお、図面の説明においては同一要素には同一符号を付し、重複する説明を省略する。
【００２３】
図１に本実施形態に係る並列処理方法が実行される並列処理システム１を示す。並列処理システム１は、所定の空間上に配置された一つ以上の領域と当該空間上に配置された一つ以上の点とをそれぞれ示すデータを入力して、各点を包含する領域を探索するためのシステムである。ここで所定の空間とは、例えば、二次元又は三次元の有限の空間である。また、領域は、当該有限の空間に配置されえる（無限の広がりをもたない）有限の領域である。
【００２４】
上記の処理は、具体的には以下のようなアプリケーションに用いられる。例えば、各領域は移動体通信のサービスが提供されるエリアに相当し、点はユーザの位置に相当し、上記の探索によって各ユーザがどのサービスを受けられるかどうかを把握することができる。あるいは、各領域は天球上の着目したい領域に相当し、点は星の位置に相当し、上記の探索によってそれぞれの星が何れの領域に含まれるかを把握することができる。
【００２５】
図１に示すように、並列処理システム１は、仕分用装置１０と１台以上の計算装置２０とを含んで構成されている。仕分用装置１０と計算装置２０とは、無線あるいは有線の通信網によって接続されており、互いに情報の送受信を行うことができる。計算装置２０は、上記の探索処理を実際に行う装置である。なお、並列処理を行う観点から、並列処理システム１は複数の計算装置２０を含むことが望ましい。
【００２６】
仕分用装置１０は、並列処理システム１での処理対象となるデータを入力し、当該データを各計算装置２０が探索処理を行えるように仕分ける装置である。なお、仕分用装置１０は、図１に示すように各計算装置２０とは別体として構成されていてもよいし、あるいは、各計算装置２０の何れかに仕分用装置１０の機能が備えられていてもよい。あるいは、複数の計算装置２０によって仕分用装置１０の機能が実現されていてもよい。また、仕分用装置１０の機能の一部が、各計算装置２０の何れに設けられていてもよい。
【００２７】
以下の例では、領域及び点が配置される空間は、二次元であるものとし、計算装置２０の台数Ｐは４台とする。
【００２８】
引き続いて、仕分用装置１０及び計算装置２０の機能について説明する。図１に示すように仕分用装置１０は、入力部１１と、仕分部１２と、選択部１３と、結果保存部１４とを備えて構成されている。
【００２９】
入力部１１は、所定の空間上に配置された一つ以上の領域（Ｍ個の領域）と当該空間上に配置された一つ以上の点（Ｎ個の点）とをそれぞれ示すデータを入力する入力手段である。データの入力は、例えば、仕分用装置１０に対するユーザの操作によって上記の各データが記録されたファイル（例えば、Ｓｈａｐｅｆｉｌｅ形式のファイルや単純なテキストファイル）が読み込まれることによって行われる。なお、並列処理が行われる趣旨から、領域の数Ｍと点の数Ｎとは、通常両方あるいは何れかが複数（２以上）である。
【００３０】
領域を示すデータとしては、具体的には例えば、領域の頂点の座標の集合である。点を示すデータとしては、具体的には例えば、点の座標である。本実施形態では、領域を示すデータを主データ、点を示すデータを主データに対応付ける従データとする。図２は、主データ（Ｍ個の領域３１）の例である。説明のため、各領域にはＡ〜Ｉの識別子を付与してある。なお、図２に示す領域が、互いに重複している部分がないが、複数の領域３１間で重複している部分があってもよい。図３は、従データ（Ｎ個の点３２）の例である。なお、図２及び図３の周囲の四角形の破線が、領域及び点が配置される空間（定義空間）３０の範囲を示している。
【００３１】
なお、入力部１１は、定義空間３０を示すデータも領域及び点を示すデータも合わせて入力することとしてもよい。あるいは、入力された領域及び点を全て含むように定義空間３０が（例えば、後述する仕分部１２等によって）生成（定義）されることとしてよい。また、リレーショナルデータベースに予め格納されていたならば利用できていたであろう、主データと従データとを付き合わせるためのキー情報は予め付与されていないものとする。また、領域と点とを示すデータは、必ずしも上記のデータに限られず、領域と点とを表現しうるものであればどのような形式のデータでもよい。
【００３２】
入力部１１は、入力したＭ個の領域及びＮ個の点を示すデータを仕分部１２に出力する。
【００３３】
仕分部１２は、定義空間を複数の格子に分割して、分割した各格子について、入力部１１によって入力されたデータによって示される領域及び点のうち、当該格子に少なくとも当該領域の一部及び当該点を含む領域及び点を当該格子に仕分ける仕分手段である。
【００３４】
具体的には、仕分部１２は、まず、領域及び点が配置される定義空間を複数の格子に分割する。各格子が、計算装置２０における探索処理の単位となる。仕分部１２は、どのように定義空間を格子に分割するかの情報を、例えば、ユーザによって予め入力されて設定ファイルとして予め記憶している。どのように定義空間を格子に分割するかの情報は、具体的には例えば、いくつの格子に分割するか、個々の格子の形状及び大きさを示す情報である。仕分部１２は、当該情報に基づいて定義空間を分割して格子を生成する。仕分部１２は、定義空間を分割して生成した各格子を識別できるように各格子に識別情報（識別子）を（動的に生成して）付与する。
【００３５】
例えば、格子の数が４であり、格子の形状が矩形であるとすると、図４に示すように定義空間３０が４つに分割されて４つの格子３３が生成される。以下の説明では、格子の総数をＫで表す。本実施形態の例では、計算装置２０の台数Ｐと格子の総数Ｋが一致（Ｐ＝Ｋ＝４）している。図４に示す例では、各格子３３には、１〜４の識別子が付与される。
【００３６】
仕分部１２は、上記のように複数の格子を生成すると、領域３１及び点３２を当該格子に仕分ける。領域３１については、以下の２つの方法の何れかによって行われる。何れの方法を用いるかは、ユーザ等によって予め仕分部１２に設定されている。
【００３７】
第１の方法では、仕分部１２は、格子３３に少なくとも領域３１の一部を含む領域３１を領域全体として各格子３３に属しているものとして仕分ける。この方法では図５に示すように、例えば領域Ａは、格子１に完全に包含されているため、格子１にのみ属すると判定される。一方、領域Ｂは格子１及び２に跨っているため、格子１及び２の両方に属すると判定される。その他の領域についても、同様に判定が下され、図５はその結果を示している。図５に示すように各領域の領域全体３４が各格子３３に属するものとされる。仕分部１２は、各領域（全体）３４に当該領域３４が属すると判定された格子３３の識別子（格子番号）を割り当てる。
【００３８】
第２の方法では、仕分部１２は、格子３３に少なくとも領域３１の一部を含む領域３１を当該領域３１と当該格子３３との交差領域（重複している領域）として各格子３３に属しているものとして仕分ける。この方法では図６に示すように、例えば領域Ａは、格子１に完全に包含されているため、格子１にのみ属すると判定される。一方、領域Ｂは格子１及び２に跨っているため、領域Ｂと格子１、及び領域Ｂと格子１との交差領域３５が計算され、それぞれの交差領域３５がそれぞれの格子３３に割り当てられる。なお、この交差領域３５も、元々の領域３１と同様に、当該有限の空間に配置されえる有限の領域である。その他の領域についても、同様に判定が下され、図６はその結果を示している。図６に示すように各領域と格子の交差領域３５が各格子３３に属するものとされる。仕分部１２は、各領域（交差領域）３５に当該領域３４が属すると判定された格子３３の識別子（格子番号）を割り当てる。
【００３９】
また、仕分部１２は、点３２が属する格子３３を仕分ける。具体的には、点３２は、当該点３２が位置する格子３３に属しているものと判定される。図７に示すように、各点３２は何れか格子３３に属するものと判定される。点３２には、“大きさ”が無いため、一つの点３２は必ず一つの格子３３にのみ属することになる。なお、点３２が格子３３の境界上にある場合は、予め設定したルール（例えば、境界の右側あるいは下側の格子３３に属するとのルール）に基づいてどちらの領域に属するか判断する。仕分部１２は、各点３２に当該領域３４が属すると判定された格子３３の識別子（格子番号）を割り当てる。
【００４０】
仕分部１２は、上記のように領域３１と点３２とを仕分けた後、各格子３３について再仕分けが必要であるか判断して、必要であれば再帰的に再仕分けを行うこととしてもよい。その場合、仕分部１２は、どのような条件で再仕分けを行うか否かの基準の情報を、例えば、ユーザによって予め入力されて設定ファイルとして予め記憶している。
【００４１】
例えば、仕分部１２は、格子３３毎に、各格子３３に仕分けられた領域３４，３５の数、各格子３３に仕分けられた点の数、及びそれらの和の何れかが予め設定された閾値を超えているか否かを判断して、閾値を超えている場合にその格子３３について再帰的に再仕分けを行うと判断する。なお、上記の判断は、各格子３３に仕分けられた領域３４，３５の数、各格子３３に仕分けられた点の数、及びそれらの和の全てについて判断する必要は無く、一種類の数のみにて判断が行われても良い。また、３種類の数のうち２つ、あるいは３種類全てが閾値を超えている場合にその格子３３について再仕分けを行うと判断することとしてもよい。
【００４２】
再仕分けを行うと判断されると仕分部１２は、その格子３３を更に細かい格子３３に分割する。更なる格子３３の分割についても、上述した（１度目の）定義空間の分割と同様に、どのように定義空間を格子に分割するかの情報を予め保持しておきその情報に基づいて行う。例えば、予め設定された数の同じ大きさの格子に再分割する。更に細かい格子３３に分割すると、上記と同様に、当該格子３３に識別情報を付与して領域３１及び点３２の仕分を行う。なお、再仕分けについては、予め設定された回数（例えば、１度）だけ行うこととしてもよいし、各格子３３に仕分けられた領域３４，３５の数、各格子３３に仕分けられた点の数、及びそれらの和の何れかが予め設定された閾値を超えない状態となるまで、繰り返し行うこととしてもよい。
【００４３】
仕分部１２は、仕分結果の情報を選択部１３に出力する。具体的には、仕分部１２は、格子３３の識別情報が対応付けられた領域及び点を示すデータを選択部１３に出力する。
【００４４】
選択部１３は、仕分部１２によって分割された各格子３３について、一台以上の計算装置２０のうち一つの計算装置２０を選択して、選択した計算装置２０に仕分部１２によって当該格子３３に仕分けられた（対応付けられた）領域及び点を示すデータを出力する選択手段である。
【００４５】
まず、選択部１３は、格子３３それぞれについて計算装置２０を選択する。例えば、計算装置２０を予め設定された基準に従って並べて、順番に選択していく。選択部１３は、格子３３毎に選択した計算装置２０に、格子３３に対応付けられた領域３４，３５及び点３２を示すデータを出力（送信）する。仕分済みの領域３４，３５のデータについては、仕分の方法に応じたデータを出力する。
【００４６】
図５を用いて説明した第１の方法を用いた場合、領域全体３４のデータが出力される。図５に示す例において、格子１に属する領域は、計算装置＃１に割り当てられるものとする。その場合、格子１に属すると判定された領域Ａ，Ｂ，Ｄ（の領域全体）が計算装置＃１に出力される（割り当てられる）。ここで、領域Ｂは格子２にも属すると判定されていたため、領域Ｂのデータは複製され計算装置＃２に出力される（割り当てられる）。同様に領域Ｄのデータも複製され、計算装置＃に３出力される（割り当てられる）。図８に、図５及び図７の結果から計算装置＃１が受け取ることになる領域３４及び点３２のデータを示す。
【００４７】
図６を用いて説明した第２の方法を用いた場合、交差領域３５（但し、一つの格子３３のみに属する領域については領域全体）のデータが出力される。この場合、一つの交差領域３５は必ず一つの格子３３にのみ属するため、領域の複製を行う必要はない。つまり、第１の方法と第２の方法とは、領域の（データの）複製を行うか、領域と格子との交差領域の計算を行うかのトレードオフの関係にある。図９に、図６及び図７の結果から計算装置＃１が受け取ることになる領域３５及び点３２のデータを示す。
【００４８】
図８及び図９に示すように、図２及び図３に示した領域３１及び点３２の総数と比べ、１台の計算装置２０で扱う領域及び点の個数がそれぞれ削減されている。本実施形態の例では、説明を簡単にするために格子を４つだけ用いたが、計算装置２０の台数Ｐ及び格子３３の総数を増やすほど、１台の計算装置で扱う領域３４，３５及び点３２の個数が減少する。十分に少ない領域３４，３５と点３２の個数になれば、点３２を包含する領域３４，３５の探索をそれらの間での単純な総当りにより行うことも現実的となる。
【００４９】
結果保存部１４は、計算装置２０からの出力される判定結果を入力（受信）し、それらを集約して、点３２を包含する領域３１の探索結果として保存する。図１０に計算結果＃１から＃４までの探索結果を集約した結果を示す。なお、図１０では、領域３１に包含されている点３２のみを示している。探索結果の保存は、例えば電子的なストレージ装置に記憶させることによって行われる。又は、仕分用装置１０が備えるディスプレイ上に結果を表示するだけでもよい。
【００５０】
計算装置２０は、仕分用装置１０から出力された領域３４，３５及び点３２を示すデータを入力（受信）して、各点３２が各領域３４，３５に含まれるか否かを判定する計算装置である。即ち、計算装置２０は、各点３２を包含する領域３４，３５の探索を行う。なお、各計算装置２０には格子３３毎のデータが入力されているので、この探索は格子３３毎に行われる。この探索は、上述したような単純な総当りによって行ってもよいし、あるいはアルゴリズム的な工夫を施してもよい。計算装置２０は、上記の判定結果を仕分用装置１０に出力（送信）する。出力される判定結果は、例えば、主データである領域３４，３５を示す情報に、当該領域３４，３５に包含されると判断された従データである点３２を対応付けた情報である。
【００５１】
なお、選択部１３における計算装置２０を選択する機能、仕分用装置１０と計算装置２０との間の通信の制御、並びに計算装置２０に割り当てられた領域３４，３５及び点３１のデータを計算装置２０上で処理するプログラムを実行する仕組み等は、計算装置を多数接続したクラスタ上での並列計算における汎用的な機能要件である。従って、近年ではそのような機能を提供するソフトウェアが多数利用できるようになってきている。例えば、ＭＰＩ（Message Passing Interface）技術のオープンソース実装であるＯｐｅｎ  ＭＰＩ、Ｇｏｏｇｌｅ社が提唱するＭａｐＲｅｄｕｃｅ技術のオープンソース実装であるＨａｄｏｏｐ、Ｍｉｃｒｏｓｏｆｔ社が提唱するＤｒｙａｄ技術等がある。選択部１３や計算装置２０の部分は、これらのソフトウェアを適用することで構築することが可能である。以上が、並列処理システム１の機能構成である。
【００５２】
図１１に並列処理システム１を構成する仕分用装置１０及び計算装置２０のハードウェア構成を示す。図１１に示すように仕分用装置１０及び計算装置２０は、ＣＰＵ（Central Processing Unit）１０１、主記憶装置であるＲＡＭ（Random Access Memory）１０２及びＲＯＭ（ReadOnly Memory）１０３、通信を行うための通信モジュール１０４、並びにハードディスク等の補助記憶装置１０５等のハードウェアを備えるコンピュータを含むものとして構成される。これらの構成要素がプログラム等により動作することにより、上述した仕分用装置１０及び計算装置２０の機能が発揮される。以上が、並列処理システム１の構成である。
【００５３】
引き続いて、図１２のフローチャートを用いて、本実施形態に係る並列処理システム１で実行される処理である並列処理方法を説明する。まず、仕分用装置１０において、入力部１１によって、探索対象となる、定義空間３０上に配置されたＭ個の領域３１とＮ個の点３２とをそれぞれ示すデータが入力される（Ｓ０１、入力ステップ）。当該入力は、上述したように例えば、ユーザの操作によって上記の各データが記録されたファイルが読み込まれることによって行われる。入力されたデータは入力部１１から仕分部１２に出力される。
【００５４】
続いて仕分部１２によって、定義空間３０が複数の格子３３に分割される（Ｓ０２、仕分ステップ）。続いて仕分部１２によって、分割された各格子３３について、入力部１１によって入力されたデータによって示される領域３１及び点３２のうち、当該格子に少なくとも当該領域３１の一部及び当該点３２を含む領域３１及び点３２が当該格子に仕分けられる（Ｓ０３、仕分ステップ）。この仕分により、仕分済みの領域３４，３５及び点３２には、対応付けられた格子３３の識別情報が対応付けられる。
【００５５】
続いて仕分部１２によって、各格子３３について再仕分けが必要であるか判断される（Ｓ０４、仕分ステップ）。この判断は、上述したように、格子３３毎に、各格子３３に仕分けられた領域３４，３５の数、各格子３３に仕分けられた点の数、及びそれらの和の何れかが予め設定された閾値を超えているか否かを判断することによって行われる。
【００５６】
格子３３の何れかにについて再仕分けが必要であると判断されると（Ｓ０４のＹＥＳ）、仕分部１２によって、当該格子３３の更なる分割が行われる（Ｓ０５、仕分ステップ）。続いて仕分部１２によって、分割された各格子３３について、元の格子３３に対応付けられていた領域３４，３５及び点３２のうち、当該格子に少なくとも当該領域３４，３５の一部及び当該点３２を含む領域３４，３５及び点３２が当該格子に仕分けられる（Ｓ０６、仕分ステップ）。
【００５７】
Ｓ０６において、再仕分けが行われた後、再帰的にＳ０４において各格子３３について再仕分けが必要か否かが判断される。なお、この判断は、Ｓ０６において更に分割された格子３３のみに対して行われてもよい。Ｓ０４において全ての格子３３について再仕分けが必要でないと判断された場合（Ｓ０４のＮＯ）、仕分結果の情報が仕分部１２から選択部１３に出力される。なお、Ｓ０４〜Ｓ０６の再帰的な再仕分けについての処理は、予め設定された回数（例えば、１度）だけ行われてもよい。その場合、設定された回数の再仕分けが行われるとＳ０６の処理の後に次の処理（Ｓ０７）に移行する。
【００５８】
続いて、選択部１３によって、格子３３それぞれについて計算装置２０が選択される（Ｓ０７、選択ステップ）。続いて、格子３３毎に選択された計算装置２０に対して、選択部１３から当該格子３３に対応付けられた領域３４，３５及び点３２を示すデータが出力される（Ｓ０８、選択ステップ）。
【００５９】
それぞれの計算装置２０では、仕分用装置１０から出力された当該データが入力される。各計算装置２０では、当該データによって示される各点３２が、当該データによって示される各領域３４，３５に含まれるか否かが判定される。即ち、各計算装置２０では、各点３２を包含する領域３４，３５の探索が行われる（Ｓ０９、計算ステップ）。判定結果は、各計算装置２０から仕分用装置１０に出力される（Ｓ１０、計算ステップ）。
【００６０】
続いて、仕分用装置１０では、結果保存部１４によって、計算装置２０からの出力される判定結果が入力されて、それらが集約されて点３２を包含する領域３１の探索結果として保存される（Ｓ１０）。保存された探索結果は、アプリケーションに応じて適宜利用される。以上が、本実施形態に係る並列処理システム１で実行される処理である。
【００６１】
上述したように本実施形態では、領域３１及び点３２のデータの２つを入力としてそれらが配置される定義空間３０が複数の格子３３に分割されて、格子３３毎に各計算装置２０において各点３２を包含する領域３４，３５を探索する処理が行われる。これにより、領域３１及び点３２のデータの２つを入力として各点３２を包含する領域３１の探索を高速に並列処理することができる。
【００６２】
その際、２つの入力は、予めリレーショナルデータベースに登録されていなく、任意の形式（例えば、上述したＳｈａｐｅｆｉｌｅ形式、テキストファイル形式）で与えることができる。また、探索処理の実行に際しても、リレーショナルデータベースシステムを用いる必要はなく、任意の並列処理システム（例えば、上述したＯｐｅｎＭＰＩ、Ｈａｄｏｏｐ、Ｄｒｙａｄ）を利用することができる。
【００６３】
また、定義空間３０を格子３３に分割する際に格子の大きさを指定したり、領域や点の仕分処理を再帰的に繰り返し行ったりすることにより、一つの格子３３に属する領域３４，３５及び点３２の総数を十分に小さくすることが可能になる。一つの格子３３に属する領域３４，３５及び点３２の総数が小さいほど、そして利用できる計算装置２０の台数が多いほど、本発明による並列処理の負荷分散効果が高くなる。
【００６４】
また、領域３１の仕分については、上述した第１の方法及び第２の方法の何れかを用いることが望ましい。この構成により、各点３２を包含する領域３４，３５を探索する処理が行うために適切かつ確実に領域３１を仕分けることができる。それにより、適切かつ確実に本発明を実施することができる。
【００６５】
上述した実施形態では、計算装置２０の台数Ｐと格子３３の総数Ｋとが一致（Ｐ＝Ｋ＝４）する例を示したが、これらは必ずしも一致する必要はない。格子３３の総数の方が多い場合、計算装置１台あたりに複数の格子を割り当てればよい。１台の計算装置２０に複数の格子が割り当てられた場合でも、計算装置２０は格子３３毎に探索処理を行うことができる。計算装置１台辺りの平均割り当て格子数ＡはＫ÷Ｐとなり、計算装置１台あたりの計算量は「Ｍ×Ｎ÷Ｋ÷Ｋ×Ａ」オーダー、つまり「Ｍ×Ｎ÷Ｋ÷Ｐ」オーダーとなる。反対に、格子３３の総数の方が少ない場合、計算装置２０群の内のいくつかは格子３３を割り当てられないことになり、その他の計算装置２０には格子３３を１つずつ割り当てればよい。この場合の計算装置１台あたりの計算量は「ゼロ」又は「Ｍ×Ｎ÷Ｋ÷Ｋ」オーダーとなる。
【００６６】
また、上述した実施形態では、領域３１を主データ、点３２を従データとして説明したが、点３２を主データ、領域３１を従データとすることとしてもよい。
【符号の説明】
【００６７】
１…並列処理システム、１０…仕分用装置、１１…入力部、１２…仕分部、１３…選択部、１４…結果保存部、２０…計算装置、１０１…ＣＰＵ、１０２…ＲＡＭ、１０３…ＲＯＭ、１０４…通信モジュール、１０５…補助記憶装置。
【図１】
2013008195.tif 000003
【図２】
2013008195.tif 000004
【図３】
2013008195.tif 000005
【図４】
2013008195.tif 000006
【図５】
2013008195.tif 000007
【図６】
2013008195.tif 000008
【図７】
2013008195.tif 000009
【図８】
2013008195.tif 000010
【図９】
2013008195.tif 000011
【図１０】
2013008195.tif 000012
【図１１】
2013008195.tif 000013
【図１２】
2013008195.tif 000014