(57)【要約】計算機の負荷状況を負荷情報取得部によって取得し、取得した負荷情報をもとにデータ割当算出部（５）が各計算機に割り当てるデータを算出および決定し、計算機の間でデータの移動させることで計算機の負荷を均一化する。さらに、プロセス制御部によって新規プロセスの生成、既存プロセスの削除を実行する。新規プロセスを追加する場合には既存のプロセスからデータを受領し、既存プロセスを削除する場合には担当データを他のプロセスに移管することで、計算機のアーキテクチャに依存しないプロセス制御を実現する。
2004006116.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算機のそれぞれに演算プロセスを生成し、前記複数の計算機のそれぞれに生成した演算プロセスに対してデータを分散して割り当てることで、データの演算を並列におこなう並列演算プログラムであって、
前記複数の計算機に対する前記データの割当状況を示す割当情報を記憶する割当情報記憶工程と、
前記複数の計算機の負荷状況を示す負荷情報を取得する負荷情報取得工程と、
前記割当情報および前記負荷情報から、前記複数の計算機に割り当てるデータを変更する必要があるか否かを判定し、データの割当の変更が必要であると判断した場合に、前記データの割当の変更内容を算出するデータ割当算出工程と、
前記データ割当算出工程が算出したデータの割当をもとに、前記複数の計算機間でデータの移動をおこなうデータ分配工程と、
をコンピュータに実行させることを特徴とする並列演算プログラム。
【請求項２】
前記負荷情報取得工程は、前記複数の計算機に生成された演算プロセスが所定量のデータの演算に要した時間を前記負荷情報として取得することを特徴とする請求の範囲第１項に記載の並列演算プログラム。
【請求項３】
前記複数の計算機から新規に演算プロセスを作成可能な計算機を検出し、当該計算機に新規に演算プロセスを作成する新規プロセス作成工程をさらに含むことを特徴とする請求の範囲第２項に記載の並列演算プログラム。
【請求項４】
所定の計算機に割り当てられたデータを他の計算機に移動させ、移動元の計算機上の演算プロセスを終了させるプロセス削除工程をさらに含むことを特徴とする請求の範囲第３項に記載の並列演算プログラム。
【請求項５】
前記演算プロセスにおけるデータの演算の途中経過を記憶する演算経過記憶工程と、前記演算経過記憶工程が記憶した途中経過と前記割当情報とをもとに異なる演算プロセスにおいて前記データの演算を再開するプロセス移動工程をさらに含むことを特徴とする請求の範囲第４項に記載の並列演算プログラム。
【請求項６】
複数の計算機のそれぞれに演算プロセスを生成し、前記複数の計算機のそれぞれに生成した演算プロセスに対してデータを分散して割り当てることで、データの演算を並列におこなう並列演算システムであって、
前記複数の計算機に対する前記データの割当状況を示す割当情報を記憶する割当情報記憶手段と、
前記複数の計算機の負荷状況を示す負荷情報を取得する負荷情報取得手段と、
前記割当情報および前記負荷情報から、前記複数の計算機に割り当てるデータを変更する必要があるか否かを判定し、データの割当の変更が必要であると判断した場合に、前記データの割当の変更内容を算出するデータ割当算出手段と、
前記データ割当算出手段が算出したデータの割当をもとに、前記複数の計算機間でデータの移動をおこなうデータ分配手段と、
を備えたことを特徴とする並列演算システム。
【請求項７】
前記負荷情報取得手段は、前記複数の計算機に生成された演算プロセスが所定量のデータの演算に要した時間を前記負荷情報として取得することを特徴とする請求の範囲第６項に記載の並列演算システム。
【請求項８】
前記複数の計算機から新規に演算プロセスを作成可能な計算機を検出し、当該計算機に新規に演算プロセスを作成する新規プロセス作成手段をさらに備えたことを特徴とする請求の範囲第７項に記載の並列演算システム。
【請求項９】
所定の計算機に割り当てられたデータを他の計算機に移動させ、移動元の計算機上の演算プロセスを終了させるプロセス削除手段をさらに備えたことを特徴とする請求の範囲第８項に記載の並列演算システム。
【請求項１０】
前記演算プロセスにおけるデータの演算の途中経過を記憶する演算経過記憶手段と、前記演算経過記憶手段が記憶した途中経過と前記割当情報とをもとに異なる演算プロセスにおいて前記データの演算を再開するプロセス移動手段をさらに備えたことを特徴とする請求の範囲第９項に記載の並列演算システム。
【請求項１１】
前記割当情報記憶手段、前記負荷情報取得手段および前記データ割当算出手段を、前記複数の計算機の一つに設けたことを特徴とする請求の範囲第６項から請求の範囲第１０項のいずれか一つに記載の並列演算システム。
【請求項１２】
前記割当情報記憶手段、前記負荷情報取得手段および前記データ割当算出手段を、前記複数の計算機に対して独立した筐体内に設けたことを特徴とする請求の範囲第６項から請求の範囲第１０項のいずれか一つに記載の並列演算システム。
【請求項１３】
複数の計算機のそれぞれに演算プロセスを生成し、前記複数の計算機のそれぞれに生成した演算プロセスに対してデータを分散して割り当てることで、データの演算を並列におこなう並列演算管理装置であって、
前記複数の計算機に対する前記データの割当状況を示す割当情報を記憶する割当情報記憶部と、
前記複数の計算機の負荷状況を示す負荷情報を取得する負荷情報取得部と、
前記割当情報および前記負荷情報から、前記複数の計算機に割り当てるデータを変更する必要があるか否かを判定し、データの割当の変更が必要であると判断した場合に、前記データの割当の変更内容を算出するデータ割当算出部と、
前記データ割当算出手段が算出したデータの割当をもとに、前記複数の計算機にデータの移動を指示するコマンドを送信する分配コマンド送信部と、
を備えたことを特徴とする並列演算管理装置。
【請求項１４】
前記負荷情報取得部は、前記複数の計算機に生成された演算プロセスが所定量のデータの演算に要した時間を前記負荷情報として取得することを特徴とする請求の範囲第１３項に記載の並列演算管理装置。
【請求項１５】
前記複数の計算機から新規に演算プロセスを作成可能な計算機を検出し、当該計算機に新規に演算プロセスを作成する新規プロセス作成部をさらに備えたことを特徴とする請求の範囲第１４項に記載の並列演算管理装置。
【請求項１６】
所定の計算機に割り当てられたデータを他の計算機に移動させ、移動元の計算機上の演算プロセスを終了させるプロセス削除部をさらに備えたことを特徴とする請求の範囲第１５項に記載の並列演算管理装置。
【請求項１７】
前記演算プロセスにおけるデータの演算の途中経過を記憶する演算経過記憶部と、前記演算経過記憶部が記憶した途中経過と前記割当情報とをもとに異なる演算プロセスにおいて前記データの演算を再開するプロセス移動部をさらに備えたことを特徴とする請求の範囲第１６項に記載の並列演算管理装置。
【請求項１８】
前記複数の計算機のいずれか一つの内部に設けたことを特徴とする請求の範囲第１３項から請求の範囲第１７項のいずれか一つに記載の並列演算管理装置。
【請求項１９】
前記複数の計算機に対して独立した筐体内に設けたことを特徴とする請求の範囲第１３項から請求の範囲第１７項のいずれか一つに記載の並列演算管理装置。
【発明の詳細な説明】
【技術分野】  この発明は、複数の計算機のそれぞれにプロセスを生成し、各プロセスにデータを分散することで、データの演算を並列におこなう並列演算プログラム、並列演算システムおよび並列演算管理装置に関し、特に、各計算機の処理量を高効率でスケジューリング可能な並列演算プログラム、並列演算システムおよび並列演算管理装置に関する。
【背景技術】  従来、大量のデータを効率的に演算処理するシステムとして、複数の計算機を並列して稼動させる並列演算システムが用いられてきた。この従来の並列演算システムでは、各計算機にデータの演算をおこなうプロセスを生成し、各プロセスにデータを分散して演算をおこなうことで、データの演算を効率化していた。
この従来の並列演算システムでは、所定の計算機にかかる負荷が高くなった場合や、計算機自体の処理能力が異なる場合に、プロセス単位で負荷分散をおこなっていた。
すなわち、負荷が高くなった計算機や処理能力の小さい計算機に対して生成するプロセスの数を減らし、負荷の小さい計算機や処理能力の大きい計算機に対して生成するプロセスの数を増やすことで、各計算機の能力および負荷状況に応じたスケジューリングをおこなっていた。
また、プロセス自体に、プロセス間でデータの移動をおこなう機能を設けることで、負荷の高い計算機から負荷の小さい計算機にデータを移動させ、負荷の分散を実現していた。
しかしながら、従来の並列演算システムにおけるプロセス単位の負荷分散では、負荷分散の単位が粗くなり、十分な負荷分散をおこなうことができないという問題点があった。また、従来の並列演算システムでは、演算開始時に決定したプロセスの数を変更することができない、という問題点があった。
一方で実行中のプロセスのメモリイメージをそのまま保存し、他の計算機上で処理を続行する機能を持たせた場合、本機能を完全に動作させるためにはバイナリの互換性が必要であった。すなわち、従来の並列演算システムでは、計算機間でのデータ移動に制限が発生するという問題点があった。
この発明は、上述した従来技術による問題点を解消するためになされたものであり、各計算機の処理量を高効率でスケジューリング可能な並列演算プログラム、並列演算システムおよび並列演算管理装置を提供することを目的とする。
【発明の開示】
上述した課題を解決し、目的を達成するため、本発明に係る並列演算プログラム、並列演算システムおよび並列演算管理装置は、複数の計算機のそれぞれに演算プロセスを生成し、前記複数の計算機のそれぞれに生成した演算プロセスに対してデータを分散して割り当てることで、データの演算を並列におこなう並列演算において、前記複数の計算機に対する前記データの割当状況を示す割当情報を記憶する割当情報記憶工程と、前記複数の計算機の負荷状況を示す負荷情報を取得する負荷情報取得工程と、前記割当情報および前記負荷情報から、前記複数の計算機に割り当てるデータを変更する必要があるか否かを判定し、データの割当の変更が必要であると判断した場合に、前記データの割当の変更内容を算出するデータ割当算出工程と、前記データ割当算出工程が算出したデータの割当をもとに、前記複数の計算機間でデータの移動をおこなうデータ分配工程と、を含むことを特徴とする。
この発明によれば、各計算機の負荷を取得し、各計算機にかかる負荷を分散する必要があるか否かを判定し、負荷を分散する必要がある場合には、各計算機に割り当てるデータの量を変更することで計算機の負荷を分散している。
また、本発明に係る並列演算プログラム、並列演算システムおよび並列演算管理装置は、前記負荷情報取得工程は、前記複数の計算機に生成された演算プロセスが所定量のデータの演算に要した時間を前記負荷情報として取得することを特徴とする。
この発明によれば、演算プロセスが所定量のデータの演算に要する時間を負荷情報として用いることで、計算機本来の処理能力と、その時点における負荷とを加味し、その時点における計算機の処理能力を取得することができる。
また、本発明に係る並列演算プログラム、並列演算システムおよび並列演算管理装置は、前記複数の計算機から新規に演算プロセスを作成可能な計算機を検出し、当該計算機に新規に演算プロセスを作成する新規プロセス作成工程をさらに含むことを特徴とする。
本発明によれば、演算プロセスを新規に作成可能な計算機を検出して新たな演算プロセスを生成することで、プロセス数を任意に増加させることができる。
また、本発明に係る並列演算プログラム、並列演算システムおよび並列演算管理装置は、所定の計算機に割り当てられたデータを他の計算機に移動させ、移動元の計算機上の演算プロセスを終了させるプロセス削除工程をさらに含むことを特徴とする。
この発明によれば、所定の計算機に割り当てられたデータを他の計算機に移動させ、移動元の演算プロセスを終了させることで、プロセス数を任意に減少させることができる。
また、本発明に係る並列演算プログラム、並列演算システムおよび並列演算管理装置は、前記演算プロセスにおけるデータの演算の途中経過を記憶する演算経過記憶工程と、前記演算経過記憶工程が記憶した途中経過と前記割当情報とをもとに異なる演算プロセスにおいて前記データの演算を再開するプロセス移動工程をさらに含むことを特徴とする。
この発明によれば、データ演算の途中経過を記憶し、他のプロセスにおいて演算を再開することで、プロセスを移動させることができる。
【図面の簡単な説明】  第１図は、本発明にかかる並列演算システムの概要構成を示す概要構成図であり、第２図は、並列演算システムの動作を説明する説明図であり、第３図は、担当情報記憶部が記憶する割当情報について説明する図であり、第４図は、負荷状態が変化した場合の担当情報を示す図であり、第５図は、並列演算システムにおける計算機の処理動作を説明するフローチャートであり、第６図は、並列演算管理装置の処理動作を説明するフローチャートであり、第７図は、データ分割方法の一例を示す図であり、第８図は、複数のデータ配列を有するデータの一例を示す図である。
【発明を実施するための最良の形態】  以下に添付図面を参照して、この発明に係る並列演算プログラム、並列演算システムおよび並列演算管理装置の好適な実施の形態を詳細に説明する。
（実施の形態）
第１図は、本実施の形態における並列演算システムの概要構成を示す概要構成図である。第１図において、並列演算システムは、並列演算管理装置１、計算機１０、計算機２０、計算機３０および計算機４０を備えている。並列演算管理装置１は、計算機１０，２０，３０，４０に接続され、各計算機に生成するプロセスの管理およびスケジューリングをおこなっている。
計算機１０は、その内部に通信部１１、プロセス実行部１２およびデータ記憶部１３を有している。プロセス実行部１２は、並列演算管理装置１によって作成されたプロセスを実行するノードとして機能する。データ記憶部１３は、プロセス実行部１２において演算処理するデータを記憶する。通信部１１は、並列演算管理装置１および計算機２０と接続される。
同様に、計算機２０は、その内部に通信部２１、プロセス実行部２２およびデータ記憶部２３を有している。プロセス実行部２２は、並列演算管理装置１によって作成されたプロセスを実行するノードとして機能する。また、データ記憶部２３は、プロセス実行部２２において演算処理するデータを記憶する。さらに、通信部２１は、並列演算管理装置１、計算機１０および計算機３０に接続される。
また、計算機３０，４０は、その内部にそれぞれ通信部３１，４１、プロセス実行部３２，４２およびデータ記憶部３３，４３を有している。プロセス実行部３２，４２は、並列演算管理装置１によって作成されたプロセスを実行するノードとしてそれぞれ機能する。また、データ記憶部３３，４３は、プロセス実行部３２，４２において演算処理するデータを記憶する。さらに、通信部３１は、並列演算管理装置１、計算機２０および計算機４０に接統され、通信部４１は、並列管理装置１および計算機３０に接続される。
一方、並列演算管理装置１は、その内部に通信部３および主制御部２を備えており、主制御部３は、割当情報記憶部４、データ割当算出部５、負荷情報取得部６、プロセス制御部７、演算経過記憶部８に接続される。また、通信部３は計算機１０内部の通信部１１、計算機２０内部の通信部２１、計算機３０内部の通信部３１、計算機４０内部の通信部４１と接続される。
並列演算管理装置１内部のプロセス制御部７は、計算機１０，２０，３０，４０に対してプロセスの作成および削除をおこなう。また、割当情報記憶部４は、各計算機に対するデータの割当状況、すなわち各計算機に生成したプロセスで処理するデータの配分を割当情報として記憶する。さらに、負荷情報取得部６は、各計算機の負荷状態を取得し、負荷情報として記憶する。
ここで、計算機の負荷状態とは、計算機自体の処理能力と、その時点において計算機が処理しているプロセスの量によって決定される。すなわち、その計算機の所定の時点における処理能力を示す値である。以下、負荷状態とは、計算機自体の所定時刻における処理能力をいうものとし、負荷情報とは負荷状態を示すデータをいうものとする。
データ割当処理部５は、割当情報記憶部４が記憶した割当情報と、負荷情報取得部６が取得した負荷情報とをもとに、各計算機に割り当てるデータのスケジューリングをおこなう。また、演算経過記憶部８は、各計算機の演算の途中経過を記憶している。
この並列演算システムによって、データの演算処理をおこなう場合、第２図に示すように、まず各計算機にプロセスを生成してデータ処理を開始する。つぎに、並列演算管理装置１内部の負荷情報取得部６によって、各計算機の負荷状態を取得する。つぎに、並列演算管理装置１内部のデータ割当処理部５によってスケジューリングをおこなう。具体的には、データ割当処理部５は、まず、データの移動による負荷分散が必要であるか否かを判定する。ここで、負荷分散が必要であるか否かの判定は、各計算機の負荷状態を比較し、突出して高負荷となっている計算機がないかを判定することで実現する。この時、所定の閾値を設定し、負荷情報と閾値とを比較するようにしてもよい。負荷分散にはオーバヘッドの増加が伴うため、閾値の設定によって負荷の許容範囲を定め、不必要なオーバヘッドの増加を避けることができる。
負荷の分散をおこなう必要がある場合、データ割当処理部５は、割当情報と負荷情報とをもとに、各計算機に割り当てるデータの量を算出する。さらに、データ割当処理部５は、算出結果を各計算機に送信する。計算機１０，２０，３０は、それぞれ受信した算出結果をもとに、計算機間でデータを移動させる。
このように、各計算機の負荷情報を取得し、負荷情報をもとに計算機間でデータを移動させ、各計算機に割り当てるデータの量を変更することで、負荷の分散をおこなうことができる。この負荷分散では、データの量によって負荷の分散をおこなっているので、負荷分散を柔軟におこなうことができる。また、計算機間におけるデータの移動で負荷を分散させることができるので、メモリイメージを保存する必要がなく、したがってバイナリの互換性を必要とせず、異なるアーキテクチャ間においても負荷の分散を行うことができる。
つぎに、第３図を参照し、担当情報記憶部４が記憶する割当情報について説明する。第３図（ａ）は、演算すべきデータ全体を示す全体データ６１であり、第３図（ｂ）は、各プロセスに対するデータの配分を示すデータ配分表６２である。また、第３図（ｃ）は、第３図（ａ）に示した全体データのうち、どのデータをどのプロセスに割り当てるかを示すデータ割当表６３である。
第３図（ａ）に示すように、全体データ６１は、データ配列Ａに関する情報を記憶している。なお、全体データ６１が記憶する情報は、データ配列Ａの取り扱いのために必要なデータ配列Ａに関する情報であり、データ配列Ａが有するデータ自体はここでは記憶しない。ここでは、全体データ６１は、データ配列Ａについて、データタイプ「整数型」、次元数「２次元」、データサイズ「２００×２００」、分割時の次元「１」を記憶している。
また、第３図（ｂ）に示すように、プロセス１にはデータ全体、すなわちデータ配列Ａの２５％が割り当てられる。同様に、プロセス２にはデータ配列Ａの２５％が割り当てられ、プロセス３，４にデータ配列Ａの２５％が割り当てられる。
なお、ここでプロセス１〜４とは、計算機１０，２０，３０，４０において実行されるプロセスを示している。単一の計算機に複数のプロセスを実行させることも可能であるが、ここでは計算機１０にプロセス１を実行させ、計算機２０にプロセス２を実行させ、計算機３０にプロセス３を実行させ、計算機４０にプロセス４を実行させるものする。
さらに第３図（ｃ）に示したデータ割当表６３は、第３図（ａ）に示したデータ配列Ａのうち、どのデータをどのプロセスに割り当てるかを示している。全体データ６１によって、データ配列Ａのサイズが「２００×２００」、分割時の次元が「１」、さらに配分データ６２にからプロセス１〜４にそれぞれ２５％ずつデータが割り当てられるので、プロセス１〜４に割り当てられるデータは、それぞれ「２００×５０」のサイズとなる。
ここで、第３図においては、各計算機１０，２０，３０，４０の負荷状態が同等であるとして、データを均等に配分している。しかし、一部の計算機が他のプロセスを同時に実行している状況が発生した場合は、計算機間の負荷状態に不均衡が生じる。また、新規にプロセスを実行可能な計算機ができた場合、この計算機にもプロセスを生成し、並列するプロセス数を増大させることが望ましい。
第４図は、第３図に示した状態の後、負荷状態が変化した場合の担当情報を示す図である。ここでは、プロセス１およびプロセス２の処理能力がプロセス３およびプロセス４の半分となり、さらに他の計算機にプロセス５を生成した状態を示す。
第４図（ａ）は、各プロセスに対するデータの配分を示すデータ配分表６２ａである。また、第４図（ｂ）は、第３図（ａ）に示した全体データのうち、どのデータをどのプロセスに割り当てるかを示すデータ割当表６３ｂである。ここで、全体データは、第３図（ａ）に示した全体データ６１と同一である。
この第４図（ａ）に示したように、計算機１０に高い負荷がかかり、処理能力が落ちている場合、計算機１０において実行するプロセス１に対するデータの割り当てを減少させる。ここでは、データ配分表６２ａに示すようにデータ全体の１２．５％を割り当てる。同様に、計算機２０に高い負荷がかかり、処理能力が落ちている場合、計算機２０において実行するプロセス２に対するデータの割り当てを減少させる。ここでは、データ配分表６２ａに示すように、データ全体の１２．５％を割り当てる。さらに、新規にプロセス５を生成し、第４図（ｂ）に示すように、プロセス５にデータ全体の２５％を割り当てている。
したがって、第４図（ｂ）に示したデータ割当表６３ａは、データ配列Ａのうちプロセス１およびプロセス２に割り当てるデータのサイズを「２００×２５」とし、プロセス３、プロセス４およびプロセス５に割り当てるデータのサイズをそれぞれ「２００×５０」としている。
このように、データ割当算出部５は、各プロセスに全データを予め割り当てておき、各プロセスの負荷状況によって割り当てる量を変化させる。この時、データ割当算出部５は、変化させたデータの割り当て、すなわちデータ割当表６３ａを、通信部３を介して各計算機に送信する。
各計算機の通信部１１，２１，３１，４１は、データ割当表６３ａを受信し、データ割当表６３ａの内容をもとにデータ記憶部１３，２３，３３，４３に記憶したデータを、通信部１１，２１，３１，４１を介して移動させる。このデータの移動は、各計算機間で直接におこない、並列演算管理装置１は経由しない。
つぎに、各計算機の負荷状態の取得について説明する。プロセス制御部７によって計算機上に作成されるプロセスは、データ処理をおこなうメインループ内に同期ポイントを備えている。各プロセスは、その処理が同期ポイントに到達した場合に、到達した時刻を並列演算管理装置１に送信する。各プロセスは通常、メインループを複数回実行するので、この同期ポイントに到達する間隔を計測することで計算機の負荷状態を取得することができる。たとえば、計算機上に他のプロセスが実行されていない場合、計算機の処理能力の全体を使用することができ、同期ポイントに到達する間隔は短くなる。一方、計算機上に他のプロセスが実行されている場合、それぞれのプロセスに使用することができる計算機の処理能力は少なくなり、同期ポイントに到達する間隔が長くなる。
ここで、他のプロセスが実行されていない場合であっても、処理能力の高い計算機上で実行されたプロセスは同期ポイントに到達する間隔が短くなり、処理能力の低い計算機上で実行されたプロセスは同期ポイントに到達する間隔が長くなる。プロセスに対してデータを割り当てる場合、必要な情報はそのプロセスにどれだけの処理を実行する能力があるか、であるので、計算機の処理能力が高いために同期ポイントに到達する間隔が短いプロセスに対しては、より多くのデータを割り当てることが望ましい。
すなわち、同期ポイントに到達する間隔を負荷情報としてもちいることで、計算機本来の処理能力に、処理中のプロセスによる負荷を加味した処理能力を取得することができる。
つぎに第５図、第６図を参照し、本実施の形態にかかる並列演算システムの処理動作について説明する。なお、第５図は、並列演算システムにおける計算機の処理動作を説明するフローチャートであり、第６図は、並列演算管理装置の処理動作を説明するフローチャートである。まず、計算機の処理動作について例として計算機１０を用い、第５図を参照して説明する。
第５図において、計算機１０は、まず、プロセス制御部７からプロセス生成の指示を受信し、プロセス実行部１２にプロセスを生成する（ステップＳ１０１）。つぎに、計算機１０は、割当情報記憶部４が記憶する割当情報をもとに割り当てられたデータを受信する（ステップＳ１０２）。このデータは、他の計算機から送信され、通信部１１を介して受信する。
つぎに、プロセス実行部１２においてデータの演算を開始する（ステップＳ１０３）。プロセス実行部１２は、データの演算が同期ポイントに到達した時刻を測定し、通信部１１を介してその時刻を並列演算管理装置１に送信する（ステップＳ１０４）。
つづいて、計算機１０は並列演算管理装置１からデータ割当表を受信する（ステップＳ１０５）。このデータ割当表にデータの移動が指示されている場合（ステップＳ１０６，Ｙｅｓ）、計算機１０は、データ記憶部１３に記憶したデータの一部を指定された計算機に送信する（ステップＳ１０７）。
受信したデータ割当表にデータの移動が指示されていない場合（ステップＳ１０６，Ｎｏ）、またはステップＳ１０７終了後、プロセス実行部１２は、全てのデータ処理が終了したか否かを判定する（ステップＳ１０８）。終了していないデータ処理がある場合（ステップＳ１０８，Ｎｏ）、プロセス実行部１２はデータ処理を続行し（ステップＳ１０３）、全てのデータ処理が終了した場合（ステップＳ１０８，Ｙｅｓ）に処理を終了する。
計算機２０，３０，４０は、計算機１０と同様に動作するのでここでは説明を省略し、つぎに、並列演算管理装置１の処理動作について第６図を参照して説明する。
第６図において、並列演算管理装置１は、まず、負荷情報取得部６によって各計算機の負荷情報を収集する（ステップＳ２０１）。この負荷情報の収集は、各計算機から同期ポイントの到達時刻を受信することでおこなう。つぎに、データ割当算出部５が、負荷を調整する必要があるか否かを判定する（ステップＳ２０２）。
負荷を調整する必要がある場合（ステップＳ２０２，Ｙｅｓ）、プロセス制御部が遊休状態にある計算機が存在するか否かを判定する（ステップＳ２０３）。遊休状態の計算機とは、プロセスを実行していない計算機をいう。プロセスを実行していない計算機では、上述の同期ポイントの到達時刻の検出ができないため、遊休状態の計算機は、負荷状態の取得とは独立して検出する必要がある。
遊休状態の計算機が存在する場合（ステップＳ２０３，Ｙｅｓ）、さらにデータ割当算出部５は、プロセスを生成する必要があるか否かを判定する（ステップＳ２０４）。ここでの判定は、新規のプロセスを生成することによる具体的な効果をもとに判定する。新規のプロセスを生成した場合、プロセスの並列度の増加にともなってオーバーヘッドが増加する。データ割当算出部５は、このオーバヘッドの増加に見合う効果が得られる場合に新規プロセスの生成が必要であると判断する。データ割当算出部５は、新規プロセスの生成が必要であると判断した場合（ステップＳ２０４，Ｙｅｓ）、遊休計算機に新規プロセスを作成する（ステップＳ２０５）。
遊休状態の計算機がない場合（ステップＳ２０３，Ｎｏ）、新規プロセスの生成が必要ないと判断した場合（ステップＳ２０４，Ｎｏ）、または新規プロセスの作成（ステップＳ２０５）の終了後、データ割当算出部５は、各プロセスに対する負荷が分散されるようにデータの割当を算出し（ステップＳ２０６）、割当情報記憶部４に記憶する。
データ割当の算出（ステップＳ２０６）終了後、または負荷調整が不必要である場合（ステップＳ２０２）、通信部３が割当情報記憶部４に記憶した割当情報をもとにデータの移動指示を各計算機に送信し（ステップＳ２０７）、処理を終了する。なお、負荷調整が不要である場合、データの移動指示にかわりデータ移動が不要であることを示すメッセージを送信する。
つぎに、並列演算管理装置１内部の演算経過記憶部８について説明する。この演算経過記憶部８は、各計算機が同期ポイントに到達する度に、その時点における演算の途中経過を取得し、記憶している。
一方、プロセス制御部７は、任意の計算機上にプロセスを生成し、またプロセスを終了させることができる。したがって、プロセス制御部が新規にプロセスを生成し、演算経過記憶部８が記憶した途中経過から演算を再開させ、もとのプロセスを終了させることで、プロセスを所定の計算機から他の計算機に移動させることができる。
また、データ割当算出時に所定のプロセスに割り当てていたデータを他のプロセスに全て割り当てた後、プロセスを終了させることで、データの演算内容に影響を与えることなくプロセス数を減少させることができる。
すなわち、プロセス制御部７は、プロセス数の増減およびプロセスの計算機間の移動を任意におこなうことができることとなる。さらに、プロセス間の移動は、データの移動によって実現するため、メモリイメージを記憶することなく、また、計算機のアーキテクチャに制限されることなくプロセスの移動をおこなうことができる。
なお、ここでは並列演算管理装置１に演算経過記憶部８を備え、演算経過記憶部８に演算途中のデータを記憶するようにしているが、演算途中のデータは必ずしも並列演算管理装置１の内部に記憶する必要は無く、独立した記憶装置を設けても良いし、各計算機で記憶するようにしてもよい。一方で、途中経過の記憶は、所定の計算機に不具合が発生した場合のバックアップとして有用であるため、計算機上に記憶する場合であっても、複数の計算機に分散するなどリスク減少の対策をとることが望ましい。
上述してきたように、本実施の形態にかかる並列演算システムでは、各計算機の負荷状況を負荷情報取得部によって取得し、取得した負荷情報をもとにデータ割当算出部が各計算機に割り当てるデータを決定し、各計算機の間でデータの移動させることで、計算機の負荷状態に対応してデータの分配をおこなうことができ、計算機の処理量を高効率でスケジューリングすることができる。
また、各プロセスの負荷をデータ量で管理しているため、所定のプロセスに割り当てていたデータを他のプロセスに移動させることができ、プロセス数の変更を安全かつ容易におこなうことができる。
さらに、データ演算の途中経過を記憶することで、アーキテクチャの制限をうけることなく任意の計算機で処理の再開をおこなうことができる。
なお、上述した実施の形態においては、処理するデータを１種類とし、データを２次元データとし、データの分割を所定方向のサイズによって決定していたが、本発明の利用はこれに限られることなく、任意のデータ数、データ形状、データ分割方法を用いることができる。
第７図に、データ分割方法の一例を示す。第７図において、２次元のデータであるデータ配列Ｂは、セル７６によって分割されている。このデータ配列Ｂを、各プロセスに分配する場合、各プロセスに対してセルを割り当てることで分配をおこなう。第７図では、プロセス１に対してセル１０個を含むデータブロック７１を割り当て、プロセス２に対してセル９個を含むデータブロック７２を割り当て、プロセス３に対してセル９個を含むデータブロック７４を割り当て、プロセス４に対してセル１２個を含むデータブロック７４を割り当てている。このように、データ配列をセルに分割し、各プロセスに割り当てるデータブロックのセル数を調節することで、データの配分をおこなうことができる。
また、第８図に、３種類のデータ配列を有するデータの一例を示す。第８図において、処理すべきデータは、データ配列Ａ、データ配列Ｂ、データ配列Ｃの３つのデータ配列を有している。また、第８図（ａ）に示すように、全体データ８１は、データ配列Ａ、データ配列Ｂ、データ配列Ｃに関する情報を記憶している。ここでは、全体データ８１は、データ配列Ａについて、データタイプ「整数型」、次元数「３次元」、データサイズ「１００×１００×１００」、分割時の次元「１」を記憶している。
同様に、全体データ８１は、データ配列Ｂについて、データタイプ「倍精度浮動小数点型」、次元数「１次元」、データサイズ「４００」、分割時の次元「１」を記憶している。さらに、全体データ８１は、データ配列Ｃについて、データタイプ「倍精度浮動小数点型」、次元数「３次元」、データサイズ「４００×４００×２００」、分割時の次元「３」を記憶している。
また、第８図（ｂ）に示すように、プロセス１にはデータ全体の２５％、すなわちデータ配列Ａの「１００×１００×２５」、データ配列Ｂの「１００」、データ配列Ｃの「４００×４００×５０」が割り当てられる。
同様に、プロセス２，３，４に対してそれぞれデータ全体の２５％、すなわちデータ配列Ａの「１００×１００×２５」、データ配列Ｂの「１００」、データ配列Ｃの「４００×４００×５０」が割り当てられる。
このように、任意の数のデータ配列を有する場合であっても、上述の場合と同様に、データの割り当てをおこなうことができる。
なお、上述した実施の形態においては、並列演算管理装置を計算機に対して独立して設けていたが、並列演算管理装置は、必ずしも独立した筐体内に設けることを必要とせず、任意の計算機に組み込んで構成しても良い。
また、並列演算管理装置の機能を、ソフトウェアを用いて実現するようにしてもよい。この場合、他のプロセスと同様に、いずれかの計算機のプロセス実行部において動作する並列演算管理プログラムを得ることができる。
以上説明したように、本発明によれば、各計算機の負荷を取得し、各計算機にかかる負荷を分散する必要があるか否かを判定し、負荷を分散する必要がある場合には、各計算機に割り当てるデータの量を変更することで計算機の負荷を分散しているので、計算機の負荷状態に対応してデータの分配をおこなうことができ、計算機の処理量を高効率でスケジューリング可能な並列演算プログラム、並列演算システムおよび並列演算管理装置を得ることができるという効果を奏する。
また、本発明によれば、演算プロセスが所定量のデータの演算に要する時間を負荷情報として用いることで、計算機本来の処理能力と、その時点における負荷とを加味し、その時点における計算機の処理能力を取得することができるので、各計算機の処理能力を適切に把握することができ、計算機の処理量を高効率でスケジューリング可能な並列演算プログラム、並列演算システムおよび並列演算管理装置を簡易な構成で得ることができるという効果を奏する。
また、本発明によれば、演算プロセスを新規に作成可能な計算機を検出して新たな演算プロセスを生成することで、プロセス数を任意に増加させることができ、所定の計算機に割り当てられたデータを他の計算機に移動させ、移動元の演算プロセスを終了させることで、プロセス数を任意に減少させることができ、データ演算の途中経過を記憶し、他のプロセスにおいて演算を再開することで、プロセスを移動させることができるので、計算機のアーキテクチャの制限を受けることなくプロセスの増減および移動をおこなうことができるという効果を奏する。
【産業上の利用可能性】  以上のように、本発明にかかる並列演算プログラム、並列演算システムおよび並列演算管理装置は、各計算機の処理量を高効率でスケジューリング可能とし、高機能、高信頼、高可用な並列演算システムの構築に対して有用である。
【図１】
2004006116.tif 000003
【図２】
2004006116.tif 000004
【図３】
2004006116.tif 000005
【図４】
2004006116.tif 000006
【図５】
2004006116.tif 000007
【図６】
2004006116.tif 000008
【図７】
2004006116.tif 000009
【図８】
2004006116.tif 000010
【国際調査報告】
2004006116.tif 000011
2004006116.tif 000012
2004006116.tif 000013
2004006116.tif 000014