並列処理方法、並列処理システム及び並列処理プログラム
【課題】 第一及び第二の集合の領域のデータの２つを入力として、第一及び第二の集合の各領域間の重なり合いの探索を高速に並列処理する。
【解決手段】 並列処理方法は、定義空間上に配置された第一及び第二の集合の領域のデータを入力する入力ステップ（Ｓ０１）と、定義空間を複数の格子に分割して、分割した各格子について、各領域のうち当該格子に少なくとも領域の一部を含む領域を当該格子に仕分ける仕分ステップ（Ｓ０２〜Ｓ０６）と、分割された各格子について、一台以上の計算装置のうちの一つを選択して、選択した計算装置当該格子に仕分けられた各領域を示すデータを出力する選択ステップ（Ｓ０７，Ｓ０８）と、計算装置のそれぞれが、各領域間の重なり合う領域を判定して、判定の結果を出力する計算ステップ（Ｓ０９）とを有する。
【解決手段】 並列処理方法は、定義空間上に配置された第一及び第二の集合の領域のデータを入力する入力ステップ（Ｓ０１）と、定義空間を複数の格子に分割して、分割した各格子について、各領域のうち当該格子に少なくとも領域の一部を含む領域を当該格子に仕分ける仕分ステップ（Ｓ０２〜Ｓ０６）と、分割された各格子について、一台以上の計算装置のうちの一つを選択して、選択した計算装置当該格子に仕分けられた各領域を示すデータを出力する選択ステップ（Ｓ０７，Ｓ０８）と、計算装置のそれぞれが、各領域間の重なり合う領域を判定して、判定の結果を出力する計算ステップ（Ｓ０９）とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法、当該並列処理システム及び並列処理プログラムに関する。
【背景技術】
【０００２】
同じ二次元又は三次元の空間上に配置されたＭ個の領域からなる第一の集合と、Ｎ個の領域からなる第二の集合との間で（ここでＭ，Ｎは自然数）、第一の集合の各領域と第二の集合の各領域との重なり合いを探索する場合、単一の計算装置上での単純な総当り探索による方法では、「Ｍ×Ｎ」オーダーの計算量を必要とする。第一の集合のＭ個の領域、及び第二の集合のＮ個の領域を何らかの基準に従って予め並べ替え（ソート）してから照合する等のアルゴリズム上の工夫により、単純な総当り探索よりも計算量を削減できる余地はある。しかし、それにも限界があり、また、並べ替え処理自体の計算量が増加する。又は、スーパーコンピュータ等の高性能な計算装置を用いることで、総当り探索を高速に完了させることも考えられる。しかし、スーパーコンピュータは非常に高価であり、また、誰でも利用できるわけではない。
【０００３】
ところで、リレーショナルデータベースにおいて、複数のテーブルのデータを組み合わせて結合する操作にＪｏｉｎがある。リレーショナルデータベースにおけるＪｏｉｎ操作を高速化する方法は従来からいくつか提案されている。例えば、組み合わせ対象の一つである主データを複製する方法（従来技術１）や、その考え方を更に推し進めた非特許文献１に記載された方法（従来技術２）等がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“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）１０３、通信を行うための通信モジュール１０４、並びにハードディスク等の補助記憶装置１０５等のハードウェアを備えるコンピュータを含むものとして構成される。これらの構成要素がプログラム等により動作することにより、上述した仕分用装置１０及び計算装置２０の機能が発揮される。以上が、並列処理システム１の構成である。
【００６９】
引き続いて、図１６のフローチャートを用いて、本実施形態に係る並列処理システム１で実行される処理である並列処理方法を説明する。まず、仕分用装置１０において、入力部１１によって、探索対象となる、定義空間３０上に配置されたＭ個の領域４０からなる第一の集合とＮ個の領域５０からなる第二の集合とをそれぞれ示すデータが入力される（Ｓ０１、入力ステップ）。当該入力は、上述したように例えば、ユーザの操作によって上記の各データが記録されたファイルが読み込まれることによって行われる。入力されたデータは入力部１１から仕分部１２に出力される。
【００７０】
続いて仕分部１２によって、定義空間３０が複数の格子３１に分割される（Ｓ０２、仕分ステップ）。続いて仕分部１２によって、分割された各格子３１について、入力部１１によって入力されたデータによって示される領域４０，５０のうち、当該格子に少なくとも当該領域４０，５０の一部を含む領域４０，５０が当該格子に仕分けられる（Ｓ０３、仕分ステップ）。この仕分により、仕分済みの領域４１，５１，５２には、対応付けられた格子３１の識別情報が対応付けられる。また、この際、仕分部１２によって、仕分けられた第一の集合の領域４１について、領域４０に対する第一の面積比率が算出されて、当該第一の面積比率を示す情報が領域４１に対応付けられる。
【００７１】
続いて仕分部１２によって、各格子３１について再仕分けが必要であるか判断される（Ｓ０４、仕分ステップ）。この判断は、上述したように、格子３１毎に、各格子３１に仕分けられた領域４１，５１，５２の数及びそれらの和の何れかが予め設定された閾値を超えているか否かを判断することによって行われる。
【００７２】
格子３１の何れかにについて再仕分けが必要であると判断されると（Ｓ０４のＹＥＳ）、仕分部１２によって、当該格子３１の更なる分割が行われる（Ｓ０５、仕分ステップ）。続いて仕分部１２によって、分割された各格子３１について、元の格子３１に対応付けられていた領域４１，５１，５２のうち、当該格子に少なくとも当該領域４１，５１，５２の一部を含む領域４１，５１，５２が当該格子に仕分けられる（Ｓ０６、仕分ステップ）。また、この際、Ｓ０３と同様に領域４１の第一の面積比率が算出されて、当該第一の面積比率を示す情報が領域４１に対応付けられる。
【００７３】
Ｓ０６において、再仕分けが行われた後、再帰的にＳ０４において各格子３１について再仕分けが必要か否かが判断される。なお、この判断は、Ｓ０６において更に分割された格子３１のみに対して行われてもよい。Ｓ０４において全ての格子３１について再仕分けが必要でないと判断された場合（Ｓ０４のＮＯ）、仕分結果の情報が仕分部１２から選択部１３に出力される。なお、Ｓ０４〜Ｓ０６の再帰的な再仕分けについての処理は、予め設定された回数（例えば、１度）だけ行われてもよい。その場合、設定された回数の再仕分けが行われるとＳ０６の処理の後に次の処理（Ｓ０７）に移行する。
【００７４】
続いて、選択部１３によって、格子３１それぞれについて計算装置２０が選択される（Ｓ０７、選択ステップ）。続いて、格子３１毎に選択された計算装置２０に対して、選択部１３から当該格子３１に対応付けられた領域４１，５１，５２及び領域４１に対応付けられた第一の面積比率を示すデータが出力される（Ｓ０８、選択ステップ）。
【００７５】
それぞれの計算装置２０では、仕分用装置１０から出力された当該データが入力される。各計算装置２０では、当該データによって示される各領域４１と各領域５１，５２とが重なり合う領域が判定される。即ち、各計算装置２０では、各領域４１と各領域５１，５２とが重なり合う領域の探索が行われる。続いて、即ち、各計算装置２０では、判定された重なり合う領域の、領域４１に対する第二の面積比率が計算される（Ｓ０９、計算ステップ）。当該計算結果（判定結果）は、各計算装置２０から仕分用装置１０に出力される。仕分用装置１０では、結果保存部１４によって、計算装置２０からの出力される計算結果が入力されて保存される。
【００７６】
仕分用装置１０では、各格子３１の計算結果が計算装置２０から受信されると、続いて、選択部１３によって、第一の集合に含まれる領域４０（の識別子）毎に上記の計算結果を集計するための計算装置２０が選択される（Ｓ１０、集計ステップ）。この選択は、例えば、上述したように第一の集合の領域４０の識別子に基づいて行われる。
【００７７】
続いて、選択部１３から選択された計算装置２０に対して、選択に係る領域４０に係る、Ｓ１０で受信した計算結果を示す情報が送信される（Ｓ１１、集計ステップ）。即ち、同じ領域４０（の識別子）についての、第一の面積比率と第二の面積比率とを示す情報が、領域４０に応じて選択された計算装置２０に送信される。
【００７８】
続いて、各計算装置２０では、当該情報が受信されて、第一の集合の領域４０（の識別子）毎に、第一の面積比率を第二の面積比率を乗じることによって、第一の集合に含まれる領域４０毎に、第二の集合に含まれる領域５０のうちどの領域と重なっているか、また重なり合いの比率を示す情報が計算される（Ｓ１２、集計ステップ）。この計算は、図１４を用いて上述したように行われる。
【００７９】
当該計算結果（集計結果）は、各計算装置２０から仕分用装置１０に出力される。仕分用装置１０では、結果保存部１４によって、計算装置２０からの出力される計算結果が入力されて保存される（Ｓ１３）。保存された探索結果は、アプリケーションに応じて適宜利用される。以上が、本実施形態に係る並列処理システム１で実行される処理である。
【００８０】
上述したように本実施形態では、第一及び第二の集合の領域４０，５０のデータの２つを入力としてそれらが配置される定義空間３０が複数の格子３１に分割されて、格子３１毎に各計算装置２０において、第一の集合に含まれる領域４１と第二の集合に含まれる領域５１，５２とが重なり合う領域を探索する処理が行われる。これにより、第一及び第二の集合の領域４０，５０のデータの２つを入力として第一の集合の各領域４０と第二の集合の各領域５０との重なり合いの探索を高速に並列処理することができる。
【００８１】
その際、２つの入力は、予めリレーショナルデータベースに登録されていなく、任意の形式（例えば、上述したＳｈａｐｅｆｉｌｅ形式、テキストファイル形式）で与えることができる。また、探索処理の実行に際しても、リレーショナルデータベースシステムを用いる必要はなく、任意の並列処理システム（例えば、上述したＯｐｅｎＭＰＩ、Ｈａｄｏｏｐ、Ｄｒｙａｄ）を利用することができる。
【００８２】
また、本実施形態のように、格子３１への第一の集合に含まれる領域４０の仕分時に第一の面積比率を算出し、重なり合う領域の探索時に第二の面積比率を算出して、これらから重なり合う領域の第一の集合に含まれる領域に対する比率を算出することが望ましい。この構成によれば、当該比率を高速に算出することができる。
【００８３】
また、定義空間３０を格子３１に分割する際に格子の大きさを指定したり、領域４０，５０の仕分処理を再帰的に繰り返し行ったりすることにより、一つの格子３１に属する領域４１，５１，５２の総数を十分に小さくすることが可能になる。一つの格子３１に属する領域４１，５１，５２の総数が小さいほど、そして利用できる計算装置２０の台数が多いほど、本発明による並列処理の負荷分散効果が高くなる。
【００８４】
また、領域５０の仕分については、上述した第１の方法及び第２の方法の何れかを用いることが望ましい。この構成により、第一及び第二の集合の領域４１，５１，５２間の重なり合う領域を探索する処理が行うために適切かつ確実に領域３１を仕分けることができる。それにより、適切かつ確実に本発明を実施することができる。
【００８５】
上述した実施形態では、計算装置２０の台数Ｐと格子３１の総数Ｋとが一致（Ｐ＝Ｋ＝４）する例を示したが、これらは必ずしも一致する必要はない。格子３１の総数の方が多い場合、計算装置１台あたりに複数の格子３１を割り当てればよい。１台の計算装置２０に複数の格子３１が割り当てられた場合でも、計算装置２０は格子３１毎に探索処理を行うことができる。計算装置１台辺りの平均割り当て格子数ＡはＫ÷Ｐとなり、計算装置１台あたりの計算量は「Ｍ×Ｎ÷Ｋ÷Ｋ×Ａ」オーダー、つまり「Ｍ×Ｎ÷Ｋ÷Ｐ」オーダーとなる。反対に、格子３１の総数の方が少ない場合、計算装置２０群の内のいくつかは格子３１を割り当てられないことになり、その他の計算装置２０には格子３１を１つずつ割り当てればよい。この場合の計算装置１台あたりの計算量は「ゼロ」又は「Ｍ×Ｎ÷Ｋ÷Ｋ」オーダーとなる。
【００８６】
また、上述した実施形態では、第一の集合の領域４０を主データ、第二の集合の領域５０を従データとして説明したが、第二の集合の領域５０を主データ、第一の集合の領域４０を従データとすることとしてもよい。
【００８７】
引き続いて、上述した一連の並列処理システム１で実行される処理をコンピュータに実行させるための並列処理プログラムを説明する。並列処理プログラムは、図１７（ａ）に示す仕分用装置側の並列処理プログラム６１と、図１７（ｂ）に示す計算装置側の並列処理プログラム７１とを含んで構成されている。図１７に示すように、並列処理プログラム６１，７１は、コンピュータに挿入されてアクセスされる、あるいはコンピュータが備える記録媒体６０，７０に形成されたプログラム格納領域６０ａ，７０ａ内に格納される。
【００８８】
仕分用装置側の並列処理プログラム６１は、仕分用装置側の並列処理を統括的に制御するメインモジュール６１ａと、入力モジュール６１ｂと、仕分モジュール６１ｃと、選択モジュール６１ｄと、結果保存モジュール６１ｅとを備えて構成される。入力モジュール６１ｂと、仕分モジュール６１ｃと、選択モジュール６１ｄと、結果保存モジュール６１ｅとを実行させることにより実現される機能は、上述した仕分用装置１０の入力部１１と、仕分部１２と、選択部１３と、結果保存部１４との機能とそれぞれ同様である。
【００８９】
計算装置側の並列処理プログラム７１は、計算装置側の並列処理を統括的に制御するメインモジュール７１ａと、計算モジュール７１ｂとを備えて構成される。計算モジュール７１ｂを実行させることにより実現される機能は、上述した計算装置２０の機能と同様である。
【００９０】
なお、並列処理プログラム６１，７１は、その一部若しくは全部が、通信回線等の伝送媒体を介して伝送され、他の機器により受信されて記録（インストールを含む）される構成としてもよい。また、並列処理プログラム６１，７１それぞれの各モジュールは、１つのコンピュータでなく、複数のコンピュータのいずれかにインストールされてもよい。その場合、当該複数のコンピュータによるコンピュータシステムよって上述した一連の並列処理プログラム６１，７１それぞれの処理が行われる。
【符号の説明】
【００９１】
１…並列処理システム、１０…仕分用装置、１１…入力部、１２…仕分部、１３…選択部、１４…結果保存部、２０…計算装置、１０１…ＣＰＵ、１０２…ＲＡＭ、１０３…ＲＯＭ、１０４…通信モジュール、１０５…補助記憶装置、６０，７０…記録媒体、６０ａ，７０ａ…プログラム格納領域、６１…仕分用装置側の並列処理プログラム、６１ａ…メインモジュール、６１ｂ…入力モジュール、６１ｃ…仕分モジュール、６１ｄ…選択モジュール、６１ｅ…結果保存モジュール、７１…計算装置側の並列処理プログラム、７１ａ…メインモジュール、７１ｂ…計算モジュール。
【技術分野】
【０００１】
本発明は、一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法、当該並列処理システム及び並列処理プログラムに関する。
【背景技術】
【０００２】
同じ二次元又は三次元の空間上に配置されたＭ個の領域からなる第一の集合と、Ｎ個の領域からなる第二の集合との間で（ここでＭ，Ｎは自然数）、第一の集合の各領域と第二の集合の各領域との重なり合いを探索する場合、単一の計算装置上での単純な総当り探索による方法では、「Ｍ×Ｎ」オーダーの計算量を必要とする。第一の集合のＭ個の領域、及び第二の集合のＮ個の領域を何らかの基準に従って予め並べ替え（ソート）してから照合する等のアルゴリズム上の工夫により、単純な総当り探索よりも計算量を削減できる余地はある。しかし、それにも限界があり、また、並べ替え処理自体の計算量が増加する。又は、スーパーコンピュータ等の高性能な計算装置を用いることで、総当り探索を高速に完了させることも考えられる。しかし、スーパーコンピュータは非常に高価であり、また、誰でも利用できるわけではない。
【０００３】
ところで、リレーショナルデータベースにおいて、複数のテーブルのデータを組み合わせて結合する操作にＪｏｉｎがある。リレーショナルデータベースにおけるＪｏｉｎ操作を高速化する方法は従来からいくつか提案されている。例えば、組み合わせ対象の一つである主データを複製する方法（従来技術１）や、その考え方を更に推し進めた非特許文献１に記載された方法（従来技術２）等がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“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）１０３、通信を行うための通信モジュール１０４、並びにハードディスク等の補助記憶装置１０５等のハードウェアを備えるコンピュータを含むものとして構成される。これらの構成要素がプログラム等により動作することにより、上述した仕分用装置１０及び計算装置２０の機能が発揮される。以上が、並列処理システム１の構成である。
【００６９】
引き続いて、図１６のフローチャートを用いて、本実施形態に係る並列処理システム１で実行される処理である並列処理方法を説明する。まず、仕分用装置１０において、入力部１１によって、探索対象となる、定義空間３０上に配置されたＭ個の領域４０からなる第一の集合とＮ個の領域５０からなる第二の集合とをそれぞれ示すデータが入力される（Ｓ０１、入力ステップ）。当該入力は、上述したように例えば、ユーザの操作によって上記の各データが記録されたファイルが読み込まれることによって行われる。入力されたデータは入力部１１から仕分部１２に出力される。
【００７０】
続いて仕分部１２によって、定義空間３０が複数の格子３１に分割される（Ｓ０２、仕分ステップ）。続いて仕分部１２によって、分割された各格子３１について、入力部１１によって入力されたデータによって示される領域４０，５０のうち、当該格子に少なくとも当該領域４０，５０の一部を含む領域４０，５０が当該格子に仕分けられる（Ｓ０３、仕分ステップ）。この仕分により、仕分済みの領域４１，５１，５２には、対応付けられた格子３１の識別情報が対応付けられる。また、この際、仕分部１２によって、仕分けられた第一の集合の領域４１について、領域４０に対する第一の面積比率が算出されて、当該第一の面積比率を示す情報が領域４１に対応付けられる。
【００７１】
続いて仕分部１２によって、各格子３１について再仕分けが必要であるか判断される（Ｓ０４、仕分ステップ）。この判断は、上述したように、格子３１毎に、各格子３１に仕分けられた領域４１，５１，５２の数及びそれらの和の何れかが予め設定された閾値を超えているか否かを判断することによって行われる。
【００７２】
格子３１の何れかにについて再仕分けが必要であると判断されると（Ｓ０４のＹＥＳ）、仕分部１２によって、当該格子３１の更なる分割が行われる（Ｓ０５、仕分ステップ）。続いて仕分部１２によって、分割された各格子３１について、元の格子３１に対応付けられていた領域４１，５１，５２のうち、当該格子に少なくとも当該領域４１，５１，５２の一部を含む領域４１，５１，５２が当該格子に仕分けられる（Ｓ０６、仕分ステップ）。また、この際、Ｓ０３と同様に領域４１の第一の面積比率が算出されて、当該第一の面積比率を示す情報が領域４１に対応付けられる。
【００７３】
Ｓ０６において、再仕分けが行われた後、再帰的にＳ０４において各格子３１について再仕分けが必要か否かが判断される。なお、この判断は、Ｓ０６において更に分割された格子３１のみに対して行われてもよい。Ｓ０４において全ての格子３１について再仕分けが必要でないと判断された場合（Ｓ０４のＮＯ）、仕分結果の情報が仕分部１２から選択部１３に出力される。なお、Ｓ０４〜Ｓ０６の再帰的な再仕分けについての処理は、予め設定された回数（例えば、１度）だけ行われてもよい。その場合、設定された回数の再仕分けが行われるとＳ０６の処理の後に次の処理（Ｓ０７）に移行する。
【００７４】
続いて、選択部１３によって、格子３１それぞれについて計算装置２０が選択される（Ｓ０７、選択ステップ）。続いて、格子３１毎に選択された計算装置２０に対して、選択部１３から当該格子３１に対応付けられた領域４１，５１，５２及び領域４１に対応付けられた第一の面積比率を示すデータが出力される（Ｓ０８、選択ステップ）。
【００７５】
それぞれの計算装置２０では、仕分用装置１０から出力された当該データが入力される。各計算装置２０では、当該データによって示される各領域４１と各領域５１，５２とが重なり合う領域が判定される。即ち、各計算装置２０では、各領域４１と各領域５１，５２とが重なり合う領域の探索が行われる。続いて、即ち、各計算装置２０では、判定された重なり合う領域の、領域４１に対する第二の面積比率が計算される（Ｓ０９、計算ステップ）。当該計算結果（判定結果）は、各計算装置２０から仕分用装置１０に出力される。仕分用装置１０では、結果保存部１４によって、計算装置２０からの出力される計算結果が入力されて保存される。
【００７６】
仕分用装置１０では、各格子３１の計算結果が計算装置２０から受信されると、続いて、選択部１３によって、第一の集合に含まれる領域４０（の識別子）毎に上記の計算結果を集計するための計算装置２０が選択される（Ｓ１０、集計ステップ）。この選択は、例えば、上述したように第一の集合の領域４０の識別子に基づいて行われる。
【００７７】
続いて、選択部１３から選択された計算装置２０に対して、選択に係る領域４０に係る、Ｓ１０で受信した計算結果を示す情報が送信される（Ｓ１１、集計ステップ）。即ち、同じ領域４０（の識別子）についての、第一の面積比率と第二の面積比率とを示す情報が、領域４０に応じて選択された計算装置２０に送信される。
【００７８】
続いて、各計算装置２０では、当該情報が受信されて、第一の集合の領域４０（の識別子）毎に、第一の面積比率を第二の面積比率を乗じることによって、第一の集合に含まれる領域４０毎に、第二の集合に含まれる領域５０のうちどの領域と重なっているか、また重なり合いの比率を示す情報が計算される（Ｓ１２、集計ステップ）。この計算は、図１４を用いて上述したように行われる。
【００７９】
当該計算結果（集計結果）は、各計算装置２０から仕分用装置１０に出力される。仕分用装置１０では、結果保存部１４によって、計算装置２０からの出力される計算結果が入力されて保存される（Ｓ１３）。保存された探索結果は、アプリケーションに応じて適宜利用される。以上が、本実施形態に係る並列処理システム１で実行される処理である。
【００８０】
上述したように本実施形態では、第一及び第二の集合の領域４０，５０のデータの２つを入力としてそれらが配置される定義空間３０が複数の格子３１に分割されて、格子３１毎に各計算装置２０において、第一の集合に含まれる領域４１と第二の集合に含まれる領域５１，５２とが重なり合う領域を探索する処理が行われる。これにより、第一及び第二の集合の領域４０，５０のデータの２つを入力として第一の集合の各領域４０と第二の集合の各領域５０との重なり合いの探索を高速に並列処理することができる。
【００８１】
その際、２つの入力は、予めリレーショナルデータベースに登録されていなく、任意の形式（例えば、上述したＳｈａｐｅｆｉｌｅ形式、テキストファイル形式）で与えることができる。また、探索処理の実行に際しても、リレーショナルデータベースシステムを用いる必要はなく、任意の並列処理システム（例えば、上述したＯｐｅｎＭＰＩ、Ｈａｄｏｏｐ、Ｄｒｙａｄ）を利用することができる。
【００８２】
また、本実施形態のように、格子３１への第一の集合に含まれる領域４０の仕分時に第一の面積比率を算出し、重なり合う領域の探索時に第二の面積比率を算出して、これらから重なり合う領域の第一の集合に含まれる領域に対する比率を算出することが望ましい。この構成によれば、当該比率を高速に算出することができる。
【００８３】
また、定義空間３０を格子３１に分割する際に格子の大きさを指定したり、領域４０，５０の仕分処理を再帰的に繰り返し行ったりすることにより、一つの格子３１に属する領域４１，５１，５２の総数を十分に小さくすることが可能になる。一つの格子３１に属する領域４１，５１，５２の総数が小さいほど、そして利用できる計算装置２０の台数が多いほど、本発明による並列処理の負荷分散効果が高くなる。
【００８４】
また、領域５０の仕分については、上述した第１の方法及び第２の方法の何れかを用いることが望ましい。この構成により、第一及び第二の集合の領域４１，５１，５２間の重なり合う領域を探索する処理が行うために適切かつ確実に領域３１を仕分けることができる。それにより、適切かつ確実に本発明を実施することができる。
【００８５】
上述した実施形態では、計算装置２０の台数Ｐと格子３１の総数Ｋとが一致（Ｐ＝Ｋ＝４）する例を示したが、これらは必ずしも一致する必要はない。格子３１の総数の方が多い場合、計算装置１台あたりに複数の格子３１を割り当てればよい。１台の計算装置２０に複数の格子３１が割り当てられた場合でも、計算装置２０は格子３１毎に探索処理を行うことができる。計算装置１台辺りの平均割り当て格子数ＡはＫ÷Ｐとなり、計算装置１台あたりの計算量は「Ｍ×Ｎ÷Ｋ÷Ｋ×Ａ」オーダー、つまり「Ｍ×Ｎ÷Ｋ÷Ｐ」オーダーとなる。反対に、格子３１の総数の方が少ない場合、計算装置２０群の内のいくつかは格子３１を割り当てられないことになり、その他の計算装置２０には格子３１を１つずつ割り当てればよい。この場合の計算装置１台あたりの計算量は「ゼロ」又は「Ｍ×Ｎ÷Ｋ÷Ｋ」オーダーとなる。
【００８６】
また、上述した実施形態では、第一の集合の領域４０を主データ、第二の集合の領域５０を従データとして説明したが、第二の集合の領域５０を主データ、第一の集合の領域４０を従データとすることとしてもよい。
【００８７】
引き続いて、上述した一連の並列処理システム１で実行される処理をコンピュータに実行させるための並列処理プログラムを説明する。並列処理プログラムは、図１７（ａ）に示す仕分用装置側の並列処理プログラム６１と、図１７（ｂ）に示す計算装置側の並列処理プログラム７１とを含んで構成されている。図１７に示すように、並列処理プログラム６１，７１は、コンピュータに挿入されてアクセスされる、あるいはコンピュータが備える記録媒体６０，７０に形成されたプログラム格納領域６０ａ，７０ａ内に格納される。
【００８８】
仕分用装置側の並列処理プログラム６１は、仕分用装置側の並列処理を統括的に制御するメインモジュール６１ａと、入力モジュール６１ｂと、仕分モジュール６１ｃと、選択モジュール６１ｄと、結果保存モジュール６１ｅとを備えて構成される。入力モジュール６１ｂと、仕分モジュール６１ｃと、選択モジュール６１ｄと、結果保存モジュール６１ｅとを実行させることにより実現される機能は、上述した仕分用装置１０の入力部１１と、仕分部１２と、選択部１３と、結果保存部１４との機能とそれぞれ同様である。
【００８９】
計算装置側の並列処理プログラム７１は、計算装置側の並列処理を統括的に制御するメインモジュール７１ａと、計算モジュール７１ｂとを備えて構成される。計算モジュール７１ｂを実行させることにより実現される機能は、上述した計算装置２０の機能と同様である。
【００９０】
なお、並列処理プログラム６１，７１は、その一部若しくは全部が、通信回線等の伝送媒体を介して伝送され、他の機器により受信されて記録（インストールを含む）される構成としてもよい。また、並列処理プログラム６１，７１それぞれの各モジュールは、１つのコンピュータでなく、複数のコンピュータのいずれかにインストールされてもよい。その場合、当該複数のコンピュータによるコンピュータシステムよって上述した一連の並列処理プログラム６１，７１それぞれの処理が行われる。
【符号の説明】
【００９１】
１…並列処理システム、１０…仕分用装置、１１…入力部、１２…仕分部、１３…選択部、１４…結果保存部、２０…計算装置、１０１…ＣＰＵ、１０２…ＲＡＭ、１０３…ＲＯＭ、１０４…通信モジュール、１０５…補助記憶装置、６０，７０…記録媒体、６０ａ，７０ａ…プログラム格納領域、６１…仕分用装置側の並列処理プログラム、６１ａ…メインモジュール、６１ｂ…入力モジュール、６１ｃ…仕分モジュール、６１ｄ…選択モジュール、６１ｅ…結果保存モジュール、７１…計算装置側の並列処理プログラム、７１ａ…メインモジュール、７１ｂ…計算モジュール。
【特許請求の範囲】
【請求項１】
一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法であって、
所定の空間上に配置された一つ以上の領域からなる第一の集合と当該空間上に配置された一つ以上の領域からなる第二の集合とをそれぞれ示すデータを入力する入力ステップと、
前記空間を複数の格子に分割して、分割した各格子について、前記入力ステップにおいて入力されたデータによって示される第一の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を、当該領域と当該格子との交差領域として当該格子に仕分けると共に、前記入力ステップにおいて入力されたデータによって示される第二の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を当該格子に仕分ける仕分ステップと、
前記仕分ステップにおいて分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分ステップにおいて当該格子に仕分けられた第一及び第二の集合に含まれる領域を示すデータを出力する選択ステップと、
前記計算装置のそれぞれが、前記選択ステップにおいて出力されたデータを入力して、当該データによって示される第一の集合に含まれる領域と第二の集合に含まれる領域とが重なり合う領域を判定して、判定の結果を出力する計算ステップと、
を有する並列処理方法。
【請求項２】
前記仕分ステップにおいて、前記第一の集合に含まれる領域と当該格子との交差領域の、当該第一の集合に含まれる領域に対する第一の比率を算出し、
前記選択ステップにおいて、選択した計算装置に、前記格子に仕分けられた第一の集合に含まれる領域の第一の比率を示す情報を出力し、
前記計算ステップにおいて、各格子における、前記第一の集合に含まれる領域と前記第二の集合に含まれる領域とが重なり合う領域の、当該第一の集合に含まれる領域に対する第二の比率を算出して、出力し、
前記第一の比率と前記第二の比率とから、前記第一の集合に含まれる領域と前記第二の集合に含まれる領域とが重なり合う領域の、第一の集合に含まれる領域に対する比率を算出して出力する集計ステップを、
更に有する請求項１に記載の並列処理方法。
【請求項３】
前記仕分ステップにおいて、前記格子に少なくとも前記第二の集合に含まれる領域の一部を含む領域を当該領域全体として仕分けることを特徴とする請求項１又は２に記載の並列処理方法。
【請求項４】
前記仕分ステップにおいて、前記格子に少なくとも前記第二の集合に含まれる領域の一部を含む領域を当該領域と当該格子との交差領域として仕分けることを特徴とする請求項１又は２に記載の並列処理方法。
【請求項５】
前記仕分ステップにおいて、各格子に仕分けられた前記第一の集合に含まれる領域の数、各格子に仕分けられた前記第二の集合に含まれる領域の数、及びそれらの和の少なくとも何れかが予め設定された閾値を超えているか否かを判断して、閾値を超えていると判断された場合には閾値を超えていた格子を再帰的に更に分割して、分割した各格子について前記第一及び第二の集合に含まれる領域を仕分けることを特徴とする請求項１〜４の何れか一項に記載の並列処理方法。
【請求項６】
一台以上の計算装置を含んで構成される並列処理システムであって、
所定の空間上に配置された一つ以上の領域からなる第一の集合と当該空間上に配置された一つ以上の領域からなる第二の集合とをそれぞれ示すデータを入力する入力手段と、
前記空間を複数の格子に分割して、分割した各格子について、前記入力手段によって入力されたデータによって示される第一の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を、当該領域と当該格子との交差領域として当該格子に仕分けると共に、前記入力手段によって入力されたデータによって示される第二の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を当該格子に仕分ける仕分手段と、
前記仕分手段によって分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分手段によって当該格子に仕分けられた第一及び第二の集合に含まれる領域を示すデータを出力する選択手段と、を備え、
前記計算装置のそれぞれが、前記選択手段によって出力されたデータを入力して、当該データによって示される第一の集合に含まれる領域と第二の集合に含まれる領域とが重なり合う領域を判定して、判定の結果を出力する、
ことを特徴とする並列処理システム。
【請求項７】
複数のコンピュータに、一台以上の計算装置を含んで構成される並列処理システムによる並列処理を実行させる並列処理プログラムであって、
前記コンピュータの少なくとも一つを、
所定の空間上に配置された一つ以上の領域からなる第一の集合と当該空間上に配置された一つ以上の領域からなる第二の集合とをそれぞれ示すデータを入力する入力手段と、
前記空間を複数の格子に分割して、分割した各格子について、前記入力手段によって入力されたデータによって示される第一の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を、当該領域と当該格子との交差領域として当該格子に仕分けると共に、前記入力手段によって入力されたデータによって示される第二の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を当該格子に仕分ける仕分手段と、
前記仕分手段によって分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分手段によって当該格子に仕分けられた第一及び第二の集合に含まれる領域を示すデータを出力する選択手段と、して機能させ、
前記複数のコンピュータのそれぞれを、前記選択手段によって出力されたデータを入力して、当該データによって示される第一の集合に含まれる領域と第二の集合に含まれる領域とが重なり合う領域を判定して、判定の結果を出力する計算装置として機能させる並列処理プログラム。
【請求項１】
一台以上の計算装置を含んで構成される並列処理システムによる並列処理方法であって、
所定の空間上に配置された一つ以上の領域からなる第一の集合と当該空間上に配置された一つ以上の領域からなる第二の集合とをそれぞれ示すデータを入力する入力ステップと、
前記空間を複数の格子に分割して、分割した各格子について、前記入力ステップにおいて入力されたデータによって示される第一の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を、当該領域と当該格子との交差領域として当該格子に仕分けると共に、前記入力ステップにおいて入力されたデータによって示される第二の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を当該格子に仕分ける仕分ステップと、
前記仕分ステップにおいて分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分ステップにおいて当該格子に仕分けられた第一及び第二の集合に含まれる領域を示すデータを出力する選択ステップと、
前記計算装置のそれぞれが、前記選択ステップにおいて出力されたデータを入力して、当該データによって示される第一の集合に含まれる領域と第二の集合に含まれる領域とが重なり合う領域を判定して、判定の結果を出力する計算ステップと、
を有する並列処理方法。
【請求項２】
前記仕分ステップにおいて、前記第一の集合に含まれる領域と当該格子との交差領域の、当該第一の集合に含まれる領域に対する第一の比率を算出し、
前記選択ステップにおいて、選択した計算装置に、前記格子に仕分けられた第一の集合に含まれる領域の第一の比率を示す情報を出力し、
前記計算ステップにおいて、各格子における、前記第一の集合に含まれる領域と前記第二の集合に含まれる領域とが重なり合う領域の、当該第一の集合に含まれる領域に対する第二の比率を算出して、出力し、
前記第一の比率と前記第二の比率とから、前記第一の集合に含まれる領域と前記第二の集合に含まれる領域とが重なり合う領域の、第一の集合に含まれる領域に対する比率を算出して出力する集計ステップを、
更に有する請求項１に記載の並列処理方法。
【請求項３】
前記仕分ステップにおいて、前記格子に少なくとも前記第二の集合に含まれる領域の一部を含む領域を当該領域全体として仕分けることを特徴とする請求項１又は２に記載の並列処理方法。
【請求項４】
前記仕分ステップにおいて、前記格子に少なくとも前記第二の集合に含まれる領域の一部を含む領域を当該領域と当該格子との交差領域として仕分けることを特徴とする請求項１又は２に記載の並列処理方法。
【請求項５】
前記仕分ステップにおいて、各格子に仕分けられた前記第一の集合に含まれる領域の数、各格子に仕分けられた前記第二の集合に含まれる領域の数、及びそれらの和の少なくとも何れかが予め設定された閾値を超えているか否かを判断して、閾値を超えていると判断された場合には閾値を超えていた格子を再帰的に更に分割して、分割した各格子について前記第一及び第二の集合に含まれる領域を仕分けることを特徴とする請求項１〜４の何れか一項に記載の並列処理方法。
【請求項６】
一台以上の計算装置を含んで構成される並列処理システムであって、
所定の空間上に配置された一つ以上の領域からなる第一の集合と当該空間上に配置された一つ以上の領域からなる第二の集合とをそれぞれ示すデータを入力する入力手段と、
前記空間を複数の格子に分割して、分割した各格子について、前記入力手段によって入力されたデータによって示される第一の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を、当該領域と当該格子との交差領域として当該格子に仕分けると共に、前記入力手段によって入力されたデータによって示される第二の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を当該格子に仕分ける仕分手段と、
前記仕分手段によって分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分手段によって当該格子に仕分けられた第一及び第二の集合に含まれる領域を示すデータを出力する選択手段と、を備え、
前記計算装置のそれぞれが、前記選択手段によって出力されたデータを入力して、当該データによって示される第一の集合に含まれる領域と第二の集合に含まれる領域とが重なり合う領域を判定して、判定の結果を出力する、
ことを特徴とする並列処理システム。
【請求項７】
複数のコンピュータに、一台以上の計算装置を含んで構成される並列処理システムによる並列処理を実行させる並列処理プログラムであって、
前記コンピュータの少なくとも一つを、
所定の空間上に配置された一つ以上の領域からなる第一の集合と当該空間上に配置された一つ以上の領域からなる第二の集合とをそれぞれ示すデータを入力する入力手段と、
前記空間を複数の格子に分割して、分割した各格子について、前記入力手段によって入力されたデータによって示される第一の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を、当該領域と当該格子との交差領域として当該格子に仕分けると共に、前記入力手段によって入力されたデータによって示される第二の集合に含まれる領域のうち、当該格子に少なくとも当該領域の一部を含む領域を当該格子に仕分ける仕分手段と、
前記仕分手段によって分割された各格子について、前記一台以上の計算装置のうち一つの計算装置を選択して、選択した計算装置に前記仕分手段によって当該格子に仕分けられた第一及び第二の集合に含まれる領域を示すデータを出力する選択手段と、して機能させ、
前記複数のコンピュータのそれぞれを、前記選択手段によって出力されたデータを入力して、当該データによって示される第一の集合に含まれる領域と第二の集合に含まれる領域とが重なり合う領域を判定して、判定の結果を出力する計算装置として機能させる並列処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１３−４５２９７（Ｐ２０１３−４５２９７Ａ）
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願番号】特願２０１１−１８２８６０（Ｐ２０１１−１８２８６０）
【出願日】平成２３年８月２４日（２０１１．８．２４）
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願日】平成２３年８月２４日（２０１１．８．２４）
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
[ Back to top ]