(57)【要約】【課題】総当り計算を行う際に、並列計算機の間で行われるデータ通信を抑制しうる計算機システム、データ処理装置、データ処理方法およびプログラムを提供する。【解決手段】計算機システム１０は、複数の計算機１１０と、データ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なるデータから成る少なくとも二つの論理空間同士を互いに組み合わせ、論理空間の組合せの夫々を複数の計算機１１０のいずれかに割り当てるデータ割当部１０１と、割り当てられた論理空間に含まれるデータ同士の総当り計算の一部または全部を、計算機１１０の夫々に割り当てるグローバル計算割当部１０２と、を備える。そして、データ割当部１０１によって割り当てられた論理空間の組合せが、計算機１１０ごとに異なる。【選択図】図１
2011243020.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算実行手段と、
複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の前記計算実行手段のいずれかに割り当てるデータ割当手段と、
前記データ割当手段によって割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当手段と、を備え、
前記データ割当手段によって割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とする計算機システム。
【請求項２】
請求項１に記載の計算機システムであって、
前記データ割当手段は、
前記データ群の複製数に基づいて分割数と構成数とを決定し、
複製された前記データ群を分割して前記分割数が示す数の前記論理空間を生成し、
決定された前記構成数が示す数の前記計算実行手段に、前記論理空間の組合せの夫々を割り当てることを特徴とする計算機システム。
【請求項３】
請求項２に記載の計算機システムであって、
前記データ割当手段は、
前記データ群の複製数より１少ない数が素数であるとき、
前記素数を二乗して前記分割数を決定し、
前記分割数の前記論理空間の夫々を成分とし、行成分の数と列成分の数とが前記素数に等しい正方行列を生成し、
生成された前記正方行列を基準行列とする循環シフト行列を、前記素数より１少ない数だけ生成し、
生成された前記正方行列の転置行列を生成し、
生成された前記正方行列、前記循環シフト行列または前記転置行列の夫々において同じ列成分となる複数の前記論理空間を組み合わせ、
夫々の前記論理空間の組合せを、前記複製数と前記素数とを乗算した数の前記計算実行手段に割り当てることを特徴とする計算機システム。
【請求項４】
請求項２に記載の計算機システムであって、
前記データ割当手段は、
前記データ群の複製数が素数であるとき、
前記複製数を二乗して前記分割数を決定し、
前記分割数の前記論理空間の夫々を成分とし、行成分の数と列成分の数とが前記複製数に等しい正方行列を生成し、
生成された前記正方行列を基準行列とする循環シフト行列を、前記複製数より１少ない数だけ生成し、
生成された前記正方行列または前記循環シフト行列の夫々において同じ列成分となる複数の前記論理空間を組み合わせ、
夫々の前記論理空間の組合せを、前記複製数を二乗した数の前記計算実行手段に割り当てることを特徴とする計算機システム。
【請求項５】
請求項１乃至４いずれか一項に記載の計算機システムであって、
一の計算実行手段に割り当てられた前記総当り計算が完了したとき、かつ他の計算実行手段に割り当てられた前記総当り計算が未完了であるとき、
前記計算割当手段は、前記他の計算実行手段に割り当てられた前記総当り計算に含まれ、未実行である演算処理の少なくとも一部を前記一の計算実行手段に割り当てることを特徴とする計算機システム。
【請求項６】
請求項５に記載の計算機システムであって、
前記計算割当手段によって前記一の計算実行手段に割り当てられる前記演算処理は、前記データ割当手段によって前記一の計算実行手段に割り当てられた前記論理空間に含まれる前記データを用いて実行可能な前記演算処理であることを特徴とする計算機システム。
【請求項７】
請求項１乃至６いずれか一項に記載の計算機システムであって、
複数の前記計算実行手段は、互いにネットワーク機器を介して接続することを特徴とする計算機システム。
【請求項８】
複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の計算実行手段のいずれかに割り当てるデータ割当手段と、
前記データ割当手段によって割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当手段と、を備え、
前記データ割当手段によって割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とするデータ処理装置。
【請求項９】
複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の計算実行手段のいずれかに割り当てるデータ割当ステップと、
前記データ割当ステップで割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当ステップと、を備え、
前記データ割当ステップで割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とするデータ処理方法。
【請求項１０】
コンピュータが読み出し可能な記憶媒体に格納されたプログラムであって、
複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の計算実行手段のいずれかに割り当てるデータ割当処理と、
前記データ割当処理で割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当処理と、
を前記コンピュータに実行させ、
前記データ割当処理で割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、総当り計算を行う計算機システム、データ処理装置、データ処理方法およびプログラムに関する。
【背景技術】
【０００２】
総当り計算とは、個々のデータ同士のすべての組み合わせに対して演算を実施する計算である。例えば、個々の文書同士の類似性を計算するなどが挙げられる。
【０００３】
データが分散されて配置されている場合、別々の場所にあるデータをどちらか一方のデータがあるところに持ってくる、あるいは同じ場所に持ってくるなどをしなければならないため、大量の通信が発生する。
【０００４】
この種の技術が、特許文献１（特開平２−１６３８６６号公報）に記載されている。特許文献１のシステムは、超立方体型並列演算装置を対象として、プロセッサ間同士の通信がぶつからないようにデータを流す経路を構成することで、通信負荷の抑制を図っている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平２−１６３８６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一方で、近年は、汎用のサーバ、ネットワーク機器を用いてツリー型の構成した並列計算機が広く用いられている。このような計算機を用いて総当り計算を行う場合、ツリー構造の並列計算機間を接続するネットワーク機器に対する負荷が大きくなる。その理由は、超立方型計算機ではプロセッサに接続されたネットワークが複数あるため、ボトルネックとなるネットワークを作らないようにデータの転送ルートを確保することができるが、ツリー構造では、ネットワーク機器に対して反対側にある計算機にあるデータを取得するには、必ずネットワーク機器を通らなければならないからである。ツリー構造が２分木であったとしても、半分の計算機がネットワーク機器に対して反対側に存在することになる。
【０００７】
本発明の目的は、総当り計算を行う際に、並列計算機の間で行われるデータ通信を抑制しうる計算機システム、データ処理装置、データ処理方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明によれば、複数の計算実行手段と、複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の前記計算実行手段のいずれかに割り当てるデータ割当手段と、前記データ割当手段によって割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当手段と、を備え、前記データ割当手段によって割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とする計算機システムが提供される。
【０００９】
また、本発明によれば、複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の計算実行手段のいずれかに割り当てるデータ割当手段と、前記データ割当手段によって割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当手段と、を備え、前記データ割当手段によって割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とするデータ処理装置が提供される。
【００１０】
さらに、本発明によれば、複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の計算実行手段のいずれかに割り当てるデータ割当ステップと、前記データ割当ステップで割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当ステップと、を備え、前記データ割当ステップで割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とするデータ処理方法が提供される。
【００１１】
さらに、本発明によれば、コンピュータが読み出し可能な記憶媒体に格納されたプログラムであって、複数のデータから成るデータ群が分割され、更に少なくとも二つに複製されて得られる複数の論理空間のうち、異なる前記データから成る少なくとも二つの前記論理空間同士を互いに組み合わせ、前記論理空間の組合せの夫々を複数の計算実行手段のいずれかに割り当てるデータ割当処理と、前記データ割当処理で割り当てられた前記論理空間に含まれる前記データ同士の総当り計算の一部または全部を、前記計算実行手段の夫々に割り当てる計算割当処理と、を前記コンピュータに実行させ、前記データ割当処理で割り当てられた前記論理空間の組合せが、前記計算実行手段ごとに異なることを特徴とするプログラムが提供される。
【発明の効果】
【００１２】
本発明によれば、総当り計算を行う際に、並列計算機の間で行われるデータ通信を抑制しうる計算機システム、データ処理装置、データ処理方法およびプログラムが提供される。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態に係る計算機システムのブロック構成図である。
【図２】本実施形態のデータ割当に関する動作フローを示すフローチャートである。
【図３】本実施形態に係る計算機システムを構成する各機器間の接続の一例を示す図である。
【図４】本実施形態の総当り計算の実行に関する動作フローを示すフローチャートである。
【図５】計算済記憶部に格納されるテーブルの一例を示す図である。
【図６】ローカル計算割当部による総当り計算のスケジューリングの一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００１５】
図１は、本発明の実施の形態に係る計算機システム１０のブロック構成図である。計算機システム１０は、データ処理装置１００と、複数の計算機１１０とから構成されている。複数の計算機１１０は、いわゆる並列計算機であり、データ処理装置１００から割り当てられた処理を、並列的に実行することができる。
【００１６】
データ処理装置１００と計算機１１０は、いずれもプログラム制御により動作するコンピュータである。データ処理装置１００または計算機１１０に内蔵されているプロセッサ（図示せず）が、不揮発性メモリなどの記録媒体（図示せず）に格納されているプログラム（またはプログラムコード）を読み出し実行することによって、図１に図示されている各種構成要素を実現する。
【００１７】
データ処理装置１００は、データ割当部１０１（データ割当手段）と、グローバル計算割当部１０２（計算割当手段）と、データ割当先記憶部１０８と、計算済記憶部１０９とを含む。
また、複数の計算機１１０は夫々、データ格納部１１１と、ローカル計算割当部１１２と、計算実行部１１３と、データ記憶部（データ割当先記憶部）１１９とを含む。
【００１８】
ここに挙げた各構成要素は、それぞれ概略つぎのように動作する。
データ割当部１０１は、計算対象となるデータ群に含まれるデータの夫々を、複数の計算機１１０のいずれかに割り当てる。グローバル計算割当部１０２は、対象となる総当り計算に含まれる演算処理の夫々を、複数の計算機１１０のいずれかに割り当てる。データ割当先記憶部１０８は、どのデータをどの計算機１１０に格納したかを記憶する。計算済記憶部１０９は、完了した演算処理を記憶する。
データ格納部１１１は、自機（計算機１１０）で格納するデータを受信し、データ記憶部１１９に格納する。ローカル計算割当部１１２は、自機で実行される演算処理の順序を決定する。計算実行部１１３は、個々の演算処理を実行する。データ記憶部１１９は、データ格納部１１１から受け付けたデータを記憶する。
【００１９】
（データ割当）
つぎに、本実施形態のデータ割当に関する動作について詳細に説明する。図２は、本実施形態のデータ割当に関する動作フローを示すフローチャートである。
【００２０】
まず、データ割当部１０１は、計算対象となるデータ群を受け付ける（ステップＡ１）。つぎに、データ割当部１０１は、ステップＡ１で受け付けたデータ群を、少なくとも二つに複製する（ステップＡ２）。そして、データ割当部１０１は、ステップＡ２で複製されたデータ群の数（データ群の複製数）に基づいて当該データ群の分割数を決定し、決定された分割数で当該データ群を分割し、複数の論理空間を生成する（ステップＡ３）。
ここで、データ群は複数のデータの集合である。また、論理空間とは、データ群に含まれる複数のデータから成り、当該データ群より小さい集合である。
【００２１】
さらに、データ割当部１０１は、ステップＡ２におけるデータ群の複製数に基づいて、データを割り当てる計算機グループの構成数を決定し、決定された構成数に応じた計算機グループを構成する（ステップＡ４）。
ここで、計算機グループとは、ネットワーク構成上近傍、例えば、互いに接続している複数の計算機１１０から成るグループである。すなわち、単一の計算機グループに、互いに接続している複数の計算機１１０が包含されている。
【００２２】
ステップＡ４の処理について、図３を用いて更に詳細に説明する。図３は、本実施形態に係る計算機システム１０を構成する各機器間の接続の一例を示す図である。図３に示すように、データ処理装置１００や各々の計算機１１０が互いにネットワーク機器１２０を介して接続し、本実施形態の計算機システム１０はツリー構造を構成している。ここで、ネットワーク機器１２０とは、具体的にはネットワークルータやハブのことである。
【００２３】
図３に示すように、単一のネットワーク機器１２０と、当該ネットワーク機器１２０に接続する複数の計算機１１０とを、一括りの構成（ラック）として扱う場合、本実施形態の計算機システム１０は４つのラックＲ１、Ｒ２、Ｒ３、Ｒ４から構成されるシステムと見做すことができる。このような構成であるとき、データ割当部１０１は、同一のラックＲ１（あるいはＲ２、Ｒ３、Ｒ４）に含まれる複数の計算機１１０を、同一の計算機グループとなるように構成する。
このように計算機グループを構成することで、ある計算機グループ内の計算機同士がデータ交換する際、ネットワーク機器１２０を経由しなくてよい。
【００２４】
再び図２を参照し、データ割当の動作フローについて説明する。ステップＡ４の処理に続いて、データ割当部１０１は、異なるデータから成る少なくとも二つの論理空間同士を互いに組み合わせ、論理空間の組合せの夫々を複数の計算機グループ（計算実行手段）のいずれかに割り当てる（ステップＡ５）。具体的には、ステップＡ４で決定された構成数の計算機グループに、論理空間の組合せの夫々を割り当てる。そして、データ割当部１０１は、データを割り当てた結果（マッピング）を、データ割当先記憶部１０８に格納する（ステップＡ６）。
なお、ステップＡ５で割り当てられた論理空間の組合せは、計算機グループごとに異なるものとする。すなわち、データ割当部１０１は、任意の論理空間の組合せが、高々一つの計算機グループに割り当てられるようにマッピングを決定する。例えば、ステップＡ５で、論理空間Ｄｘと論理空間Ｄｙとを組み合わせて一の計算機グループに割り当てる場合、他の計算機グループには論理空間Ｄｘと論理空間Ｄｙとの組合せを割り当てないようにする。ただし、上記の場合において、論理空間Ｄｚがさらに存在する場合、論理空間Ｄｘと論理空間Ｄｚとの組合せや、論理空間Ｄｙと論理空間Ｄｚとの組合せは、他の計算機グループに割り当ててもよいものとする。すなわち、「論理空間の組合せが、計算機グループごとに異なる」とは、当該論理空間の組合せに含まれる論理空間の一部が異なればよい。
【００２５】
最後に、データ割当部１０１は、ステップＡ５で割り当てられた論理空間に含まれる各データを、ステップＡ６で格納されたマッピングに従って、各計算機グループに格納させる（ステップＡ７）。具体的には、データ割当部１０１は、各データを、格納先の計算機グループに属する計算機１１０のデータ格納部１１１を介してデータ記憶部１１９に格納させる。
【００２６】
（総当り計算の実行）
次に総当り計算を実行する動作について詳細に説明する。図４は、本実施形態の総当り計算の実行に関する動作フローを示すフローチャートである。
【００２７】
ローカル計算割当部１１２は、データ割当部１０１によって割り当てられた論理空間に含まれるデータの総当り計算の一部または全部を、計算機グループの夫々に割り当てる（ステップＢ１）。具体的には、グローバル計算割当部１０２は、データ割当先記憶部１０８を参照して、個々の計算機１１０のローカル計算割当部１１２に対して、その計算機１１０のデータ記憶部１１９に格納された（ステップＡ５で割り当てられた）論理空間に含まれるデータ同士の総当り計算の一部または全部を割り当てる。
【００２８】
ステップＢ１で総当り計算を割り当てられた計算機グループに属する計算機１１０は、自機のローカル計算割当部１１２で当該総当り計算（演算処理）のスケジューリングを決定する（ステップＢ２）。
ステップＢ２において、必要であれば、ローカル計算割当部１１２は、データ格納部１１１に、当該計算機グループ内にある他の計算機１１０から必要なデータ（またはデータセット）を指示する。そして、データ格納部１１１は、指示されたデータを他の計算機１１０から取得し、データ記憶部１１９に格納する。
【００２９】
また、計算実行部１１３は、ローカル計算割当部１１２によって決定されたスケジューリングに従って、自機のデータ記憶部１１９を参照し、ローカル計算割当部１１２によって指示された演算処理を実行する（ステップＢ３）。ローカル計算割当部１１２は、計算実行部１１３による演算処理の進捗を監視し、割り当てられた論理空間同士の演算処理が完了すると、グローバル計算割当部１０２に通知する（ステップＢ４）。
【００３０】
グローバル計算割当部１０２は、ローカル計算割当部１１２から通知された演算処理の完了通知に応じて、計算済記憶部１０９に完了した演算処理を記録（記憶）する（ステップＢ５）。
【００３１】
図５は、計算済記憶部１０９に格納されるテーブルの一例を示す図である。ステップＢ５において、グローバル計算割当部１０２は、図５で示すような表形式で完了した演算処理を記録すればよい。
【００３２】
再び、図４を参照して総当り計算の動作フローについて説明する。一の計算機グループに対して割り当てられた総当り計算が未完了である間は（ステップＢ６のＮＯ）、ステップＢ３からステップＢ５の処理が繰り返される。
【００３３】
一の計算機グループに対して割り当てられた総当り計算が完了したとき（ステップＢ６のＹＥＳ）、かつ一部の計算機グループ（他の計算機グループ）に対して割り当てられた総当り計算が未完了であるとき（ステップＢ７のＮＯ）、グローバル計算割当部１０２は、データ割当先記憶部１０８と計算済記憶部１０９を参照して、他の計算機グループに割り当てられた総当り計算に含まれ、未実行である演算処理の少なくとも一部を、一の計算機グループに割り当てる（ステップＢ８）。
ただし、ステップＢ８で一の計算機グループに割り当てられる演算処理は、極力、ステップＡ５で一の計算機グループに割り当てられた論理空間に含まれるデータを用いて実行可能な演算処理とすることが好ましい。
しかし、ステップＢ８で割り当てられた演算処理を実行するのに必要なデータ（論理空間）が、一の計算機グループで保持されていない場合、ローカル計算割当部１１２は、他の計算機グループに属する他の計算機１１０（データ記憶部１１９）から取得するように、自機のデータ格納部１１１に指示してもよい。このとき、ステップＢ８で割り当てられた演算処理を実行するのに必要な論理空間のうち、少なくとも一部が予め一の計算機グループで保持されているように、演算処理を割り当てることが望ましい。
【００３４】
ローカル計算割当部１１２は、ステップＢ８で一の計算機グループに割り当てられた演算処理のスケジューリングを決定する（ステップＢ９）。ステップＢ９からステップＢ３に移行し、上述と同様にステップＢ３以降の処理が実行される。
【００３５】
一の計算機グループに対して割り当てられた総当り計算が完了したとき（ステップＢ６のＹＥＳ）、かつ全部の計算機グループに対して割り当てられた総当り計算が完了したとき（ステップＢ７のＹＥＳ）、図４に示す動作フローは終了となる。
【００３６】
つづいて、図４のステップＢ２またはステップＢ９で実行される、ローカル計算割当部１１２による総当り計算に含まれる演算処理のスケジューリング（ローカルなスケジューリング）について、図６を用いて具体的に説明する。
【００３７】
図６は、ローカル計算割当部１１２による総当り計算のスケジューリングの一例を示す図である。ここでは、ある計算機グループに含まれる７台の計算機１１０の夫々にデータセット（ｄ０，ｄ１，ｄ２，ｄ３，ｄ４，ｄ５，ｄ６）が一つずつ保持されているものとする。
なお、図６で各計算機１１０の中に（  ）で図示される記号が、当該計算機が保持しているデータセットを表している。例えば、（ｄ０，ｄ１）は、データセットｄ０とデータセットｄ１が保持されていることを表している。
ここで、データセットとは、当該計算機グループに割り当てられた論理空間に含まれるデータの少なくとも一部である。
【００３８】
図６（Ａ）では、上記のデータセットを持っている７台の計算機１１０を図示している。ここでは、分かりやすく説明するために、便宜的に左側からデータセットのインデックス順に並べて図示する。
【００３９】
そして、計算機１１０の各々が、右隣（あるいは左隣）が持っているデータセットを受け取り、総当り計算し、左隣（あるいは右隣）へと受け取ったデータを渡すという手順を、データセットの個数（計算機１１０の台数）の半分回繰り返す。マクロの視点で見ると、データを左シフト（あるいは右シフト）で半回転したところで、総当り計算が実行される。
なお、図６に示すようにデータセットの個数が奇数である場合、（データセットの個数）／２の余りは無視する。従って、図６の場合、３回繰り返すことで、総当り計算が実行される。
【００４０】
図６（Ｂ）は左シフトを１回行った状態、図６（Ｃ）は左シフトを２回行った状態、図６（Ｄ）は左シフトを３回行った状態、を図示している。
【００４１】
図６（Ｂ）〜図６（Ｄ）に示すとおり、３回の左シフトで２１通りのデータセット同士の総当り計算が実施され、異なるデータセット同士で実行可能な総当り計算が網羅されることがわかる。当然、図６（Ａ）に示す状態で、上記のデータセットで実施可能な総当り計算のうち、同一のデータセットに含まれるデータ間で実行可能な総当り計算が網羅される。
【００４２】
次に、本実施の形態の効果について説明する。
本実施の形態では、夫々の計算機グループに対し異なる論理空間に組合せを割り当てるため、総当り計算を実行する際に、計算機グループ間のデータ通信を抑えることができる。従って、計算機グループ間を接続するネットワーク機器に対する負荷が抑制される。
【００４３】
また、本実施の形態では、割り当てられた総当り計算の演算処理が完了した計算機グループに、他の計算機グループで未実行の演算処理を割り当てるため、いずれかの計算機が停止する場合や、あるいは計算機ごとの性能差が著しい場合でも、効率的に最後まで計算を終えることができる。
【００４４】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【００４５】
上記実施形態では、計算対象であるデータ群の総当り計算を実行する際、各計算機グループへのデータ割当（論理空間の割当）と、総当り計算実行のスケジューリングについて詳細に説明した。一方で、当該データ群の総当り計算の解をどのように利用するかについては特に述べていないが、その目的や環境に応じて適切に決定されればよい。例えば、図１に図示した計算機システム１０の中で利用してもよいし、図示していない他のシステムまたは装置に送出しても構わない。
このとき、計算機グループの各々で実行された総当り計算の解を結合し、データ群の総当り計算の解を得る機能が必要となるが、当該機能は、計算機システム１０が備えてもよいし、他のシステムまたは装置が備えてもよい。
【００４６】
上記実施形態ではデータ処理装置１００と計算機１１０との夫々が、コンピュータプログラムにより各種機能として論理的に実現されることを例示した。しかし、このような各部の各々を固有のハードウェアとして形成することもでき、ソフトウェアとハードウェアとの組み合わせとして実現することもできる。
【００４７】
上記実施形態では互いに接続している複数の計算機１１０からなる計算機グループを、本発明の計算実行手段として説明した。しかし、本発明の計算実行手段は、単一の計算機であってもよい。
【００４８】
上記実施形態の説明には、複数のフローチャートを用いており、それぞれに複数のステップを順番に記載してあるが、その記載の順番は、本発明のデータ処理方法のステップを実行する順番を限定するものではない。このため、本発明のデータ処理方法を実行するときには、その複数のステップの順番は内容的に支障しない範囲で変更することができる。
例えば、上記実施形態の図２の説明において、計算対象となるデータ群を複製する処理（ステップＡ２）の後に、当該データ群を分割する処理（ステップＡ３）を実行したが、この順番は逆であってもよい。すなわち、計算対象となるデータ群を分割して複数の論理空間を生成し、その後に生成された複数の論理空間を少なくとも二つに複製してもよい。
【００４９】
上記実施形態の図２の説明において、ステップＡ１〜ステップＡ６の動作について、全てデータ割当部１０１が主体となって実行するように説明したが、必ずしもこれに限らない。データ割当部１０１が主体的に実行するべき処理は、ステップＡ５の割当処理であって、他の処理は図１に図示しない構成要素や装置によって処理されてもよい。
【００５０】
なお、当然ながら、上述した実施の形態および複数の変形例は、その内容が相反しない範囲で組み合わせることができる。また、上述した実施の形態および変形例では、各構成要素の機能などを具体的に説明したが、その機能などは本願発明を満足する範囲で各種に変更することができる。
【００５１】
本発明によれば、大規模なデータセットに対する分析（データエントリ同士の距離、比較）といった用途に適用できる。
【実施例】
【００５２】
（実施例１）
本実施例において、計算対象のデータ群を複製した数（データ群の複製数）をＲ、計算対象のデータ群を分割した数（データ群の分割数）をＮ、データ（論理空間の組合せ）が割り当てられる計算機グループの構成数をＭとする。
なお、「データ群の複製数」「データ群の分割数」「計算機グループの構成数」とは、上記実施形態の図２のフローチャートの説明で用いた同様の文言に対応している。
【００５３】
本実施例においては、（Ｒ−１）が素数である場合におけるデータ割当（論理空間の割当）について説明する。このとき、Ｎ＝（Ｒ−１）＾２、Ｍ＝Ｒ（Ｒ−１）となる（（Ｒ−１）＾２は（Ｒ−１）の２乗の意味）。例えば、Ｒ＝４（Ｒ−１＝３）の場合、Ｎ＝９、Ｍ＝１２となる。
従って、データ割当部１０１は、計算対象となるデータ群を４つに複製し、複製されたデータ群の夫々を９つに分割して、９つの論理空間（Ｄ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５，Ｄ６，Ｄ７，Ｄ８）を生成する。そして、データ割当部１０１は、３つずつ論理空間を組み合わせて、夫々を１２個の計算機グループ（Ｓ００，Ｓ０１，Ｓ０２，Ｓ０３，Ｓ０４，Ｓ０５，Ｓ０６，Ｓ０７，Ｓ０８，Ｓ０９，Ｓ１０，Ｓ１１）のいずれかに割り当てる。
【００５４】
本発明において、論理空間の組合せは、計算機グループごとに異なるように割り当てる必要がある。このため、データ割当部１０１は、以下のような処理をして、各計算機グループに割り当てる論理空間を決定する。
【００５５】
まず、データ割当部１０１は、９つの論理空間の夫々を成分とし、（Ｒ−１）×（Ｒ−１）の正方行列Ａを生成する。このとき、生成された正方行列Ａを式（１）で示す。
【００５６】
【数１】
2011243020.tif 000003
式（１）では、単純にＤ０からＤ８を正方行列に並べている。これは、重複出現することがないようにランダムな順番にならべてもよい。
【００５７】
つぎに、データ割当部１０１は、正方行列Ａを基準行列として、Ｒ−２個のｋ−循環シフト行列（ただし、ｋ＝１，...，Ｒ−２）を生成する。ここで、ｋ−循環シフト行列とは、基準行列を、ｎ行目を行方向にｋ（ｎ−１）回循環シフトして作られる行列である。
このとき、生成された１−循環シフト行列Ｂを式（２）に、２−循環シフト行列Ｃを式（３）に示す。
【００５８】
【数２】
2011243020.tif 000004
【００５９】
【数３】
2011243020.tif 000005
【００６０】
さらに、データ割当部１０１は、正方行列Ａの転置行列Ｄを生成する。このとき、生成された転置行列Ｄを式（４）に示す。
【００６１】
【数４】
2011243020.tif 000006
【００６２】
そして、データ割当部１０１は、式（１）〜式（４）に示した各行列において同じ列成分となる複数の論理空間を組み合わせて、夫々の論理空間の組合せを１２個の計算機グループに割り当てる。すなわち、各計算機グループへの論理空間の割り当ては、例えば、以下のようになる。
計算機グループＳ００：（Ｄ０，Ｄ３，Ｄ６）
計算機グループＳ０１：（Ｄ１，Ｄ４，Ｄ７）
計算機グループＳ０２：（Ｄ２，Ｄ５，Ｄ８）
計算機グループＳ０３：（Ｄ０，Ｄ５，Ｄ７）
計算機グループＳ０４：（Ｄ１，Ｄ３，Ｄ８）
計算機グループＳ０５：（Ｄ２，Ｄ４，Ｄ６）
計算機グループＳ０６：（Ｄ０，Ｄ４，Ｄ８）
計算機グループＳ０７：（Ｄ１，Ｄ５，Ｄ６）
計算機グループＳ０８：（Ｄ２，Ｄ３，Ｄ７）
計算機グループＳ０９：（Ｄ０，Ｄ１，Ｄ２）
計算機グループＳ１０：（Ｄ３，Ｄ４，Ｄ５）
計算機グループＳ１１：（Ｄ６，Ｄ７，Ｄ８）
【００６３】
Ｒ−１が素数であるとき、このような手順でデータのマッピングを決めると上記のデータ分散の条件を満たす。
【００６４】
さらに、付け加えるべき特徴として、任意の分割された論理空間の組合せ（Ｄｘ，Ｄｙ）（ただし、ｘ≠ｙ）は、たった一つ、かつ、同一の計算機グループに割り当てられる。例えば、本実施例において、Ｄ０は、計算機グループＳ００、Ｓ０３、Ｓ０６、Ｓ０９のうちどこか１箇所で、Ｄ１からＤ８と一緒に保持される。
【００６５】
（実施例２）
第２の実施例においても、第１の実施例と同様に、データ群の複製数をＲ、データ群の分割数をＮ、データが割り当てられる計算機グループの構成数をＭとして説明する。
【００６６】
本実施例では、Ｒが素数である場合について説明する。この場合、Ｎ＝Ｒ＾２、Ｍ＝Ｒ＾２となる（Ｒ＾２はＲの２乗の意味）。
例えば、Ｒ＝５のとき、Ｎ＝２５、Ｍ＝２５となる。このとき、データ割当部１０１は、以下のような処理をして、各計算機グループに割り当てる論理空間を決定する。
【００６７】
まず、データ割当部１０１は、２５個の論理空間の夫々を成分とし、Ｒ×Ｒの正方行列Ｅを生成する。このとき、生成された正方行列Ｅを式（５）で示す。
【００６８】
【数５】
2011243020.tif 000007
【００６９】
つぎに、データ割当部１０１は、正方行列Ｅを基準行列として、Ｒ−１個のｌ−循環シフト行列（ただし、ｌ＝１，...，Ｒ−１）を生成する。ここで、ｌ−循環シフト行列とは、基準行列を、ｍ行目を行方向にｌ（ｍ−１）回循環シフトして作られる行列である。
このとき、生成された１−循環シフト行列Ｆを式（６）に、２−循環シフト行列Ｇを式（７）に、３−循環シフト行列Ｈを式（８）に、４−循環シフト行列Ｉを式（９）に示す。
【００７０】
【数６】
2011243020.tif 000008
【００７１】
【数７】
2011243020.tif 000009
【００７２】
【数８】
2011243020.tif 000010
【００７３】
【数９】
2011243020.tif 000011
【００７４】
そして、データ割当部１０１は、式（５）〜式（９）に示した各行列のおいて同じ列成分となる複数の論理空間を組み合わせて、夫々の論理空間の組合せを２５個の計算機グループに割り当てる。
【００７５】
上記のように論理空間の組合せを割り当てた場合、全組み合わせのＲ／（Ｒ＋１）に相当する組み合わせが計算機グループ内に閉じた総当り計算でカバーされる。上記のＲ＝５の場合、全ての論理空間の組合せである３００通りのうち、２５０通りの組合せについて網羅した総当り計算が実行できる。
残りの１／（Ｒ＋１）に相当する５０通りの論理空間の組合せに関しては、図４のステップＢ８で説明したように、計算機グループ間で必要なデータ（論理空間）を授受し保持してから、計算すればよい。
【００７６】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００７７】
（付記１）
単一の前記計算実行手段に、互いに接続している複数の計算機が包含されることを特徴とする計算機システム。
【００７８】
（付記２）
前記計算実行手段の各々で実行された前記総当り計算の解を結合し、前記データ群の総当り計算の解を得る結合手段を、さらに備えることを特徴とする計算機システム。
【符号の説明】
【００７９】
１０    計算機システム
１００  データ処理装置
１０１  データ割当部
１０２  グローバル計算割当部
１０８  データ割当先記憶部
１０９  計算済記憶部
１１０  計算機
１１１  データ格納部
１１２  ローカル計算割当部
１１３  計算実行部
１１９  データ記憶部
１２０  ネットワーク機器
【図１】
2011243020.tif 000012
【図２】
2011243020.tif 000013
【図３】
2011243020.tif 000014
【図４】
2011243020.tif 000015
【図５】
2011243020.tif 000016
【図６】
2011243020.tif 000017