(57)【要約】【課題】ジョブを高速に実行することができる並列処理装置、並列処理方法及び並列処理プログラムを提供すること。【解決手段】ジョブの実行中に、かかるジョブを実行している各ノードから性能情報を取得し、取得した性能情報に基づいて、ジョブを高速に実行できる割付パターンを予測し、予測した割付パターンが現行の割付パターンよりも高速にジョブを実行できる場合に、ジョブの実行を中断して、予測した割付パターンに基づいて各ノードにタスクを割り付けた後に、ジョブの実行を再開する。【選択図】図２
2010257056.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理要素を含むジョブを複数のノードに実行させる並列処理装置であって、
前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得部と、
前記取得部によって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付部と
を備えたことを特徴とする並列処理装置。
【請求項２】
前記取得部によって取得された性能情報に基づいて、割付パターンごとに前記ジョブを実行する時間を予測する性能予測部をさらに備え、
前記割付部は、前記性能予測部によって現行の割付パターンよりも高速に前記ジョブを実行する割付パターンが予測された場合に、前記性能予測部によって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする請求項１に記載の並列処理装置。
【請求項３】
前記ジョブは、前記性能情報を収集し始めるタイミングを示す情報である開始タイミング情報と、前記性能情報の収集を終了するタイミングを示す情報である終了タイミング情報とを含み、
前記取得部は、前記終了タイミング情報を検知した場合に、前記複数のノードによって前記開始タイミング情報が示すタイミングから前記終了タイミング情報が示すタイミングの間に収集された性能情報を取得することを特徴とする請求項１又は２に記載の並列処理装置。
【請求項４】
前記取得部は、複数のジョブに含まれる処理要素が割り付けられた各ノードから性能情報を取得し、
前記性能予測部は、前記取得部によって取得された性能情報に基づいて、前記複数のジョブに跨って割付パターンを変動させて前記複数のジョブを実行する時間を予測し、
前記割付部は、前記性能予測部によって、現行の割付パターンよりも高速に前記複数のジョブを実行する割付パターンが予測された場合に、前記性能予測部によって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする請求項２又は３に記載の並列処理装置。
【請求項５】
前記取得部は、前記性能情報として、前記各ノードから、処理要素実行時にデータを送受するノード間の情報である通信パターンと、処理要素実行時に送受されるデータの量である通信量及び通信時間と、前記各ノードにおいて実行される演算の内容及び演算にかかる時間とを取得することを特徴とする請求項１〜４のいずれか一つに記載の並列処理装置。
【請求項６】
複数の処理要素を含むジョブを複数のノードに実行させる並列処理装置による並列処理方法であって、
前記並列処理装置が、
前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得ステップと、
前記取得ステップによって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付ステップと
を含んだことを特徴とする並列処理方法。
【請求項７】
複数の処理要素を含むジョブを複数のノードに実行させる並列処理プログラムであって、
前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得手順と、
前記取得手順によって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付手順と
をコンピュータに実行させることを特徴とする並列処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列処理装置、並列処理方法及び並列処理プログラムに関する。
【背景技術】
【０００２】
複数のプロセッサや複数の情報処理装置等のノードを用いて、ジョブを分散して実行する並列処理装置が知られている。このような並列処理装置は、ジョブに含まれる処理要素であるタスクを複数のノードに割り付ける。そして、各ノードは、自身に割り付けられたタスクを他のノードと並列に実行する。
【０００３】
並列処理装置によるジョブの実行時間は、タスクの割り付け方によって変動する。これは、ノードによって性能が異なったり、ノード間の通信経路によってデータの転送時間が変動するからである。このようなことから、並列処理装置は、ジョブを効率良く実行できるようにタスクを割り付けることが求められる。
【０００４】
そこで、近年では、シミュレータなどを用いてジョブを実行することにより処理時間を予測する技術が知られている。かかる技術は、シミュレータによって、ジョブの実行時間が短くなると考えられるノードとタスクとの組合せのパターン（以下、「割付パターン」と言う）、及び、ノードにタスクを割り付けるスケジュールを予測する。そして、並列処理装置は、シミュレータによって予測された割付パターン及びスケジュールにしたがって、各ノードにタスクを割り付けてジョブを実行する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平６−７５７８６号公報
【特許文献２】特開平５−７３５１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来技術を用いると、シミュレータによって予測された割付パターンにしたがって、各ノードにタスクを割り付けることができない場合があった。具体的には、実際にジョブを実行する際に、シミュレータによって予測された割付パターンに含まれるノードが空いていないことがあった。かかる場合、従来の並列処理装置は、予測された割付パターンにしたがってタスクを割り付けることができなかった。このことは、効率良くジョブを実行できないため、ジョブの実行時間が長くなるという問題を招いていた。
【０００７】
開示の技術は、上記に鑑みてなされたものであって、ジョブを高速に実行することができる並列処理装置、並列処理方法及び並列処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願の開示する並列処理装置は、一つの態様において、複数の処理要素を含むジョブを複数のノードに実行させる並列処理装置であって、前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得部と、前記取得部によって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付部とを備える。
【発明の効果】
【０００９】
本願の開示する並列処理装置の一つの態様によれば、ジョブを高速に実行することができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、典型的なシミュレーションプログラムにおける処理プロセスを示す図である。
【図２】図２は、実施例１に係る並列処理装置によるタスク割付処理を説明するための図である。
【図３】図３は、実施例１に係る並列処理装置の構成を示す図である。
【図４】図４は、図３に示したノードの通信経路の一例を示す図である。
【図５】図５は、図３に示したノードの構成を示す図である。
【図６】図６は、ジョブ実行開始時における割付パターンの一例を示す図である。
【図７−１】図７−１は、第二演算においてデータ転送が行われるノードの一例を示す図である。
【図７−２】図７−２は、第三演算においてデータ転送が行われるノードの一例を示す図である。
【図７−３】図７−３は、第五演算においてデータ転送が行われるノードの一例を示す図である。
【図８−１】図８−１は、第一演算及び第二演算を実行しているノードによって収集される性能情報の一例を示す図である。
【図８−２】図８−２は、第三演算を実行しているノードによって収集される性能情報の一例を示す図である。
【図８−３】図８−３は、第五演算を実行しているノードによって収集される性能情報の一例を示す図である。
【図９】図９は、性能予測部によって特定された割付パターンの一例を示す図である。
【図１０−１】図１０−１は、第二演算においてデータ転送が行われるノードの一例を示す図である。
【図１０−２】図１０−２は、第三演算においてデータ転送が行われるノードの一例を示す図である。
【図１０−３】図１０−３は、第五演算においてデータ転送が行われるノードの一例を示す図である。
【図１１−１】図１１−１は、第一演算及び第二演算の実行時間の予測例を示す図である。
【図１１−２】図１１−２は、第三演算の実行時間の予測例を示す図である。
【図１１−３】図１１−３は、第五演算の実行時間の予測例を示す図である。
【図１２】図１２は、実施例１に係る並列処理装置による処理手順を示すフローチャートである。
【図１３】図１３は、性能予測装置と接続される並列処理装置の構成を示す図である。
【図１４】図１４は、性能情報収集処理の開始終了タイミングが埋め込まれたジョブの一例を示す図である。
【図１５】図１５は、割付処理を複数回行う例を説明するための図である。
【図１６】図１６は、複数のジョブを実行する場合における割付処理の一例を示す図である。
【図１７】図１７は、並列処理プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する並列処理装置、並列処理方法及び並列処理プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例により本願の開示する並列処理装置、並列処理方法及び並列処理プログラムが限定されるものではない。
【実施例１】
【００１２】
［実施例１に係る並列処理装置によって実行されるジョブ］
実施例１に係る並列処理装置１００は、多種多様なジョブを実行することができるが、特に、シミュレーション処理を行うジョブを実行する場合に有用である。そこで、実施例１では、並列処理装置１００が、シミュレーション処理を行うジョブを実行する場合について説明する。まず、シミュレーション処理を行う典型的なジョブについて説明する。
【００１３】
シミュレーション処理が行われるジョブは、一般的に、所定のプログラミング言語で記述されたプログラムにより形成される。以下では、所定のプログラミング言語でシミュレーション処理が記述されたプログラムを「シミュレーションプログラム」と表記するものとする。
【００１４】
図１は、典型的なシミュレーションプログラムにおける処理プロセスを示す図である。図１に示すように、シミュレーションプログラムを並列処理装置１００に実行させると、一般的には、並列処理装置１００は、まず、初期値を設定する処理などの前処理を行う（ステップＳ１）。続いて、並列処理装置１００は、初期値に基づいてシミュレーション処理を行う（ステップＳ２）。以下では、シミュレーションプログラムにおいて行われるシミュレーション処理を「核心処理」と表記するものとする。
【００１５】
続いて、並列処理装置１００は、シミュレーションの結果が収束していない場合（ステップＳ３否定）、例えば、核心処理において用いられる各種設定値を修正する設定値修正処理を行う（ステップＳ４）。一方、並列処理装置１００は、シミュレーションの結果が収束した場合（ステップＳ３肯定）、処理を終了する。
【００１６】
ここで、上述した処理について、シミュレーションプログラムの具体例を挙げて説明する。例えば、分子動力学計算に関するシミュレーションプログラムである場合、並列処理装置１００は、核心処理において、各原子に働く力の計算や、運動方程式にしたがった原子及び分子の座標更新を行う。
【００１７】
また、例えば、量子論の計算に関するシミュレーションプログラムである場合、並列処理装置１００は、前処理において、初期の電子状態（波動関数及び電荷密度）を設定する処理を行う。続いて、並列処理装置１００は、核心処理において、かかる電子状態からポテンシャルを算出し、算出したポテンシャルを用いて電子状態の更新を行う。そして、並列処理装置１００は、収束判定において、核心処理によって更新される前の電子状態と、更新後の電子状態との差異が所定の誤差の範囲に含まれるか否かを判定する。
【００１８】
このように、シミュレーションプログラムを実行すると、一般的に、シミュレーションの結果が収束するまで核心処理が繰り返し行われる。すなわち、シミュレーションプログラムにより形成されるジョブを実行する時間は、核心処理の実行時間に依存する。言い換えれば、核心処理の実行時間を予測することができれば、シミュレーションプログラムの実行時間を予測できると言える。
【００１９】
［実施例１に係る並列処理装置によるタスク割付処理］
次に、上述したようなシミュレーションプログラムにより形成されるジョブを実行する並列処理装置１００によるタスク割付処理について説明する。実施例１に係る並列処理装置１００は、処理郡であるジョブを実行する場合に、かかるジョブに含まれるタスクを、プロセッサや情報処理装置であるノードに割り付ける。そして、並列処理装置１００は、ノードによってタスクが実行されている途中で、各ノードから、タスク実行時における性能に関する情報（以下、「性能情報」と言う）を取得する。続いて、並列処理装置１００は、取得した性能情報に基づいて、割付パターンごとに、ジョブの実行時間を予測する。そして、並列処理装置１００は、現行の割付パターンよりも高速にジョブを実行できる割付パターンが存在する場合に、予測した割付パターンに基づいて各ノードにタスクを割り付ける。
【００２０】
図２を用いて具体的に説明する。図２は、実施例１に係る並列処理装置１００によるタスク割付処理を説明するための図である。図２の左側には、ジョブ実行時における処理の流れを示し、図２の右側には、タスク割付処理の流れを示す。
【００２１】
図２に示すように、並列処理装置１００は、ジョブを実行すると、図１に示した処理と同様に、まず、前処理を行う（ステップＳ１１）。なお、かかる前処理は、前処理に対応するタスクが割り付けられたノードによって行われる。
【００２２】
続いて、並列処理装置１００は、核心処理を行う（ステップＳ１２−１）。上述したように核心処理は何度も繰り返し行われるので、並列処理装置１００は、核心処理を繰り返し行う（ステップＳ１２−２）。なお、かかる核心処理は、核心処理に対応するタスクが割り付けられたノードによって行われる。
【００２３】
ここで、並列処理装置１００は、ジョブが実行されてから所定の時間が経過した場合に、各ノードから性能情報を取得する。図２に示した例では、並列処理装置１００は、核心処理が２回行われた後に（ステップＳ１２−１及びＳ１２−２）、性能情報を取得している（ステップＳ２１）。なお、ここで言う「性能情報」とは、タスク実行時におけるノード間の通信量や、通信時間、ノードによって実行される演算の内容や、かかる演算にかかる時間などを示す。性能情報については後述する。
【００２４】
このとき、各ノードは、継続して核心処理を行う（ステップＳ１２−３及びＳ１２−４）。すなわち、並列処理装置１００によって性能情報が取得された場合であっても、各ノードは自身に割り付けられたタスクを実行する。
【００２５】
続いて、並列処理装置１００は、ステップＳ２１において取得した性能情報に基づいて、割付パターンごとにジョブ時における性能を予測する（ステップＳ２２）。具体的には、シナリオ作成装置１００は、割付パターンごとにジョブの実行時間を予測する。そして、並列処理装置１００は、現行の割付パターンよりも高速にジョブを実行する割付パターンが存在する場合に、ジョブの実行を中断する（ステップＳ２３）。図２に示した例では、並列処理装置１００は、ステップＳ１２−４における核心処理を行った後に、ジョブの実行を中断する。
【００２６】
続いて、並列処理装置１００は、予測した割付パターンに基づいて各ノードにタスクを割り付ける（ステップＳ２４）。なお、ジョブが実行中である場合や、ジョブの実行が中断されている場合、かかるジョブを実行しているノードは、他のジョブに用いられて、実行中や中断中のジョブを実行できなくなることはない。すなわち、並列処理装置１００は、ステップＳ２２において予測した割付パターンに基づいて、確実に各ノードにタスクを割り付けることができる。
【００２７】
続いて、並列処理装置１００は、ジョブの実行を再開する（ステップＳ２５）。これにより、各ノードは、核心処理を再度行う（ステップＳ１２−５）。そして、各ノードは、核心処理の結果が収束した場合に（ステップＳ１２−ｎ）、核心処理を終了し、後処理を行う（ステップＳ１３）。
【００２８】
このように、実施例１に係る並列処理装置１００は、ジョブの実行中に、各ノードから性能情報を取得し、取得した性能情報に基づいて、ジョブを高速に実行できる割付パターンを予測する。そして、並列処理装置１００は、ジョブの実行を中断して、予測した割付パターンに基づいて各ノードにタスクを割り付けた後に、ジョブの実行を再開する。これにより、実施例１に係る並列処理装置１００は、ジョブを高速に実行できる割付パターンに基づいて、確実に各ノードにタスクを割り付けることができるので、ジョブを高速に実行することができる。
【００２９】
特に、上記例のように、ジョブがシミュレーションプログラムである場合、並列処理装置１００は、核心処理を数回だけ実行した時点で性能情報を取得すれば、ジョブの実行時間を高精度に予測することができる。これは、上述したように、シミュレーションプログラムは、核心処理を繰り返し行う場合が多いので、核心処理の実行時間を予測することができれば、シミュレーションプログラムの実行時間を予測することができるからである。すなわち、並列処理装置１００は、核心処理の実行時間を高速化することができるので、ジョブ全体の実行時間を高速化することができる。
【００３０】
［実施例１に係る並列処理装置の構成］
次に、図３を用いて、実施例１に係る並列処理装置１００の構成について説明する。図３は、実施例１に係る並列処理装置１００の構成を示す図である。図３に示すように、並列処理装置１００は、並列計算部１１０と、ジョブ制御部１２０と、性能予測部１３０とを有する。
【００３１】
並列計算部１１０は、タスクを実行する複数のノード１１１−１〜１１１−ｎを有する。ノード１１１−１〜１１１−ｎは、一又は複数のＣＰＵ（Central  Processing  Unit）を有し、自身に割り付けられたタスクを実行する。
【００３２】
また、ノード１１１−１〜１１１−ｎは、タスクを実行している場合に、性能情報を収集する。具体的には、ノード１１１−１〜１１１−ｎは、タスク実行時にデータを送受する相手先のノードの情報である通信パターンや、タスク実行時における通信量及び通信時間、タスク実行時における演算内容及び演算にかかる時間などを収集する。なお、ノード１１１−１〜１１１−ｎの構成については、図５を用いて後述する。
【００３３】
かかるノード１１１−１〜１１１−ｎは、相互に所定の通信経路によって接続される。図４に、図３に示したノード１１１−１〜１１１−ｎの通信経路の一例を示す。図４では、ノード１１１−１〜１１１−ｎのうち、ノード１１１−１〜１１１−８を例に挙げて説明する。図４に示すように、ノード１１１−１〜１１１−８は、距離の異なる通信経路によって接続される。ここで言う「距離」とは、ノード間に介在する通信機構の数を示す。
【００３４】
例えば、図４に示した例において、ノード１１１−１及びノード１１１−２は、距離が「１」である通信経路によって接続されている。同様に、ノード１１１−３及びノード１１１−４、ノード１１１−５及びノード１１１−６、ノード１１１−７及びノード１１１−８は、距離が「１」である通信経路によって接続されている。
【００３５】
また、図４に示した例において、例えば、ノード１１１−１及びノード１１１−３は、距離が「２」である通信経路によって接続されている。同様に、例えば、ノード１１１−２及びノード１１１−４や、ノード１１１−５及びノード１１１−７、ノード１１１−６及びノード１１１−８は、距離が「２」である通信経路によって接続されている。
【００３６】
また、図４に示した例において、ノード１１１−１及びノード１１１−５は、距離が「３」である通信経路によって接続されている。同様に、例えば、ノード１１１−２及びノード１１１−６や、ノード１１１−３及びノード１１１−７、ノード１１１−４及びノード１１１−８は、距離が「３」である通信経路によって接続されている。
【００３７】
実施例１において、「距離」の値が大きい通信経路で接続されているノード間ほど、通信時間が長くなるものとする。例えば、図４に示した例において、距離が「２」である通信経路によって接続されているノード１１１−１及び１１１−３間の通信は、距離が「１」である通信経路によって接続されているノード１１１−１及びノード１１１−２間の通信よりも時間がかかる。なお、図４では、ノード１１１−１〜１１１−８の接続関係の例を示したが、ノード１１１−９〜１１１−ｎも、距離の異なる通信経路によって接続される。
【００３８】
図３の説明に戻って、ジョブ制御部１２０は、ジョブの実行を制御する。具体的には、ジョブ制御部１２０は、ジョブを実行開始する場合に、かかるジョブを実行するノードを確保したり、確保したノードに対して、タスクの実行を中断させたり、タスクの実行を再開させたりする。
【００３９】
また、実施例１におけるジョブ制御部１２０は、性能情報取得部１２１と、タスク割付部１２２とを有する。性能情報取得部１２１は、タスクが割り付けられた複数のノードによってジョブが実行されてから所定の時間が経過した場合に、かかる複数のノードから、タスク実行時における性能情報を取得する。具体的には、性能情報取得部１２１は、各ノードによって収集された通信パターンや、通信時間、演算内容、演算時間などを、各ノードから取得する。そして、性能情報取得部１２１は、取得した性能情報と現行の割付パターンとを性能予測部１３０へ送信する。
【００４０】
なお、ジョブがシミュレーションプログラムである場合、性能情報取得部１２１は、核心処理が所定の回数実行された場合に、各ノードから性能情報を取得してもよい。例えば、性能情報取得部１２１は、図２に示した例のように、核心処理が２回実行された後に、各ノードから性能情報を取得してもよい。
【００４１】
タスク割付部１２２は、後述する性能予測部１３０によって、現行の割付パターンよりも高速にジョブを実行する割付パターンが予測された場合に、予測された割付パターンに基づいて各ノードにタスクを割り付ける。
【００４２】
以下に、ジョブ制御部１２０による処理について、処理の順に具体的に説明する。まず、ジョブ制御部１２０は、ジョブを実行するノードを確保する。例えば、ジョブ制御部１２０は、ノード１１１−１〜１１１−ｎのうち、ノード１１１−１〜１１１−８を確保する。
【００４３】
続いて、ジョブ制御部１２０のタスク割付部１２２は、確保した各ノードに対して、ジョブに含まれるタスクを割り付ける。このとき、タスク割付部１２２は、例えば、事前にシミュレーションした結果に基づいてタスクをノードに割り付けてもよいし、ランダムにタスクをノードに割り付けてもよい。
【００４４】
続いて、ジョブ制御部１２０は、タスクを割り付けた各ノードに対して、タスクを実行するように指示する。これにより、各ノードは、自身に割り付けられたタスクを実行するとともに、性能情報を収集する。
【００４５】
そして、ジョブ制御部１２０の性能情報取得部１２１は、各ノードによってタスクが実行されてから所定の時間が経過した場合に、各ノードから性能情報を取得する。続いて、性能情報取得部１２１は、取得した性能情報と現行の割付パターンとを性能予測部１３０へ送信する。これにより、性能予測部１３０によって割付パターンごとにジョブの実行時間が予測される。
【００４６】
続いて、ジョブ制御部１２０は、性能予測部１３０によって、現行の割付パターンよりも高速にジョブを実行する割付パターンが予測された場合に、各ノードに対してタスクの実行を中断させる。かかる指示を受け付けた各ノードは、計算の一単位が終了した後にタスクの実行を中断する。例えば、各ノードは、核心処理を実行中である場合、かかる核心処理が終了した後にタスクの実行を中断する。
【００４７】
続いて、ジョブ制御部１２０のタスク割付部１２２は、性能予測部１３０によって予測された割付パターンに基づいて各ノードにタスクを割り付ける。すなわち、タスク割付部１２２は、現行の割付パターンを、現行よりもジョブを高速に実行できる割付パターンに変更する。
【００４８】
続いて、ジョブ制御部１２０は、各ノードに対して、タスクの実行に用いられる各種データを相互に転送するように指示する。かかる指示を受け付けた各ノードは、タスクの実行に用いる各種データを相互に転送する。例えば、タスク割付部１２２が、ノード１１１−１に割り付けられていたタスクＴ１１をノード１１１−２に割り付け、ノード１１１−２に割り付けられていたタスクＴ１２をノード１１１−１に割り付けたものとする。かかる場合、ノード１１１−１は、タスクＴ１１の実行に用いる各種データを、ノード１１１−２へ転送する。また、ノード１１１−２は、タスクＴ１２の実行に用いる各種データを、ノード１１１−１へ転送する。
【００４９】
そして、ジョブ制御部１２０は、各ノードによる転送処理が終了した場合に、各ノードに対して、ジョブの実行を再開するように指示する。かかる指示を受け付けた各ノードは、新たに割り付けられたタスクを実行する。
【００５０】
性能予測部１３０は、性能情報取得部１２１によって取得された性能情報に基づいて、割付パターンごとにジョブを実行する時間を予測する。具体的には、性能予測部１３０は、割付パターンを変動させてジョブを実行する時間をシミュレーションする。このとき、性能予測部１３０は、例えば、遺伝的アルゴリズム等を用いてシミュレーションを行う。そして、性能予測部１３０は、シミュレーションした実行時間と割付パターンの組合せの中から、最も実行時間が短くなる割付パターンを特定する。続いて、性能予測部１３０は、特定した割付パターンの方が、現行の割付パターンよりも高速にジョブを実行できる場合に、特定した割付パターンをタスク割付部１２２へ送信する。
【００５１】
［実施例１におけるノードの構成］
次に、図５を用いて、図３に示したノード１１１−１〜１１１−ｎの構成について説明する。図５は、図３に示したノード１１１−１〜１１１−ｎの構成を示す図である。なお、図５に示したノード１１１は、図３に示したノード１１１−１〜１１１−ｎに対応する。
【００５２】
図５に示すように、ノード１１１は、外部記憶装置１１２と、主記憶装置１１３と、退避用記憶装置１１４と、ＣＰＵ１１５ａ〜１１５ｄとを有する。かかる外部記憶装置１１２、主記憶装置１１３、退避用記憶装置１１４、ＣＰＵ１１５ａ〜１１５ｄとは、バス１１６によって接続される。
【００５３】
外部記憶装置１１２は、ハードディスク等の記憶デバイスであり、タスクを実行する際に用いられる各種データを記憶する。主記憶装置１１３は、メモリ等の記憶デバイスであり、タスクを実行する際に用いられる各種データを記憶する。
【００５４】
退避用記憶装置１１４は、タスクの実行に用いられる各種データを他のノード１１１と相互に転送する場合に、外部記憶装置１１２や主記憶装置１１３に記憶されている各種データを記憶する。
【００５５】
ＣＰＵ１１５ａ〜１１５ｄは、ノード１１１に割り付けられたタスクを実行する。具体的には、ＣＰＵ１１５ａ〜１１５ｄは、外部記憶装置１１２や主記憶装置１１３に記憶されている各種データを用いて、タスクを実行する。
【００５６】
また、ＣＰＵ１１５ａ〜１１５ｄは、ジョブ制御部１２０から、タスクの実行に用いられる各種データを他のノード１１１へ転送する旨の指示を受け付けた場合に、各データの転送処理を行う。具体的には、ＣＰＵ１１５ａ〜１１５ｄは、外部記憶装置１１２や主記憶装置１１３に記憶されている各種データを退避用記憶装置１１４に退避する。続いて、ＣＰＵ１１５ａ〜１１５ｄは、退避用記憶装置１１４に退避した各種データを、かかる各種データを処理する他のノード１１１へ転送する。また、ＣＰＵ１１５ａ〜１１５ｄは、他のノード１１１から、自身に新たに割り付けられたタスクを実行する際に用いる各種データが転送された場合に、かかる各種データを外部記憶装置１１２や主記憶装置１１３に記憶させる。
【００５７】
なお、図５に示した例では、ノード１１１が４個のＣＰＵ１１５ａ〜１１５ｄを有する例を示したが、ノード１１１は、１〜３個のＣＰＵを有してもよいし、５個以上のＣＰＵを有してもよい。
【００５８】
［実施例１に係る並列処理装置の適用例］
次に、上述した並列処理装置１００による処理について、ジョブの具体例を用いて詳細に説明する。以下では、まず、並列処理装置１００によって実行されるジョブの具体例について説明し、次に、ジョブ実行開始時における割付パターンについて説明し、次に、各ノードによるタスクの実行処理について説明する。そして、タスク実行時における性能情報について説明し、最後に、性能情報に基づいて最適な割付パターンを予測する処理について説明する。
【００５９】
まず、並列処理装置１００によって実行されるジョブの具体例について説明する。ここでは、並列処理装置１００によって実行されるジョブの核心処理は、以下に示す演算を行うことにより算出されるｈを求める処理であるものとする。
【００６０】
【数１】
2010257056.tif 000003
【００６１】
【数２】
2010257056.tif 000004
【００６２】
【数３】
2010257056.tif 000005
【００６３】
上記式（１）〜（３）について具体的に説明すると、まず、上記式（１）に示すように、所定の範囲の変数ｉについてｗ（ｉ、ｊ）の和ｖ（ｊ）を算出する。続いて、算出したｖ（ｊ）の二乗であるｚ（ｊ）を算出する。そして、最後に、所定の範囲の変数ｊについてｚ（ｊ）の和を算出することによりｈを求める。なお、ここでは、「ｉ＝１〜８０」であり、「ｊ＝１〜４０」であるものとする。
【００６４】
次に、ジョブ実行開始時における割付パターンについて説明する。ここでは、８個のノード１１１−１〜１１１−８によって、上記のジョブを実行するものとする。また、ここでは、説明を簡単にするために、ノード１１１−１〜１１１−８による処理性能は全て同一であるものとする。なお、ノード１１１−１〜１１１−８は、上記式（１）〜（３）の順に演算を行わずに、他の演算を行うことにより、上記式（１）〜（３）により算出されるｈと等しい値を求める。
【００６５】
図６に、ジョブ実行開始時における割付パターンの一例を示す。図６において、タスク番号は、タスクを識別するための番号を示す。また、タスクは、ノードに割り付けられたタスクを示す。また、ノード識別子は、ノードを識別するための識別子を示す。なお、本明細書において、ノード識別子は、各ノードに付与した符号「１１１−ｎ」に該当するものとする。
【００６６】
すなわち、図６に示すように、ノード１１１−１は、ジョブ実行開始時において、タスク「ｗ（１：２０、１：２０）」が割り付けられている。ｗ（１：２０、１：２０）は、上記式（１）を条件「ｉ＝１〜２０」で算出し、算出した値に「ｊ＝１〜２０」を代入することを示す。すなわち、ｗ（１：２０、１：２０）を演算すると、２０個の値が求められる。
【００６７】
また、図６に示すように、ノード１１１−６は、タスクｗ「（２１：４０、１：２０）」が割り付けられている。ｗ（２１：４０、１：２０）は、上記式（１）を条件「ｉ＝２１〜４０」で算出し、算出した値に「ｊ＝１〜２０」を代入することを示す。すなわち、ｗ（２１：４０、１：２０）を演算すると、ｗ（１：２０、１：２０）と同様に２０個の値が求められる。
【００６８】
同様に、ノード１１１−２は、タスクｗ「（４１：６０、１：２０）」が割り付けられ、ノード１１１−３は、タスクｗ「（６１：８０、１：２０）」が割り付けられている。
【００６９】
また、図６に示すように、ノード１１１−５は、タスクｗ「（１：２０、２１：４０）」が割り付けられている。ｗ（１：２０、２１：４０）は、上記式（１）を条件「ｉ＝１〜２０」で算出し、算出した値に「ｊ＝２１〜４０」を代入することを示す。すなわち、ｗ（１：２０、２１：４０）を演算すると、ｗ（１：２０、１：２０）と同様に２０個の値が求められる。
【００７０】
同様に、ノード１１１−４は、タスクｗ「（２１：４０、２１：４０）」が割り付けられ、ノード１１１−７は、タスクｗ「（４１：６０、２１：４０）」が割り付けられ、ノード１１１−８は、タスクｗ「（６１：８０、２１：４０）」が割り付けられている。
【００７１】
次に、ノード１１１−１〜１１１−８によるタスクの実行処理について説明する。ここでは、ノード１１１−１〜１１１−８は、図６に示したようにタスクが割り付けられたものとする。ノード１１１−１〜１１１−８は、以下に示す（第一演算）〜（第五演算）を行うことにより、上記式（３）に示したｈを算出する。以下に、（第一演算）〜（第五演算）に分けて、各演算について説明する。
【００７２】
（第一演算）
まず、ノード１１１−１〜１１１−８は、自身に割り付けられたタスクを実行する。具体的には、ノード１１１−１は、タスク「ｗ（１：２０、１：２０）」を実行する。具体的には、ノード１１１−１は、上記式（１）を条件「ｉ＝１〜２０」で算出し、算出した値に「ｊ＝１〜２０」を代入して、２０個の値を算出する。
【００７３】
また、ノード１１１−６は、タスク「ｗ（２１：４０、１：２０）」を実行する。具体的には、ノード１１１−６は、上記式（１）を条件「ｉ＝２１〜４０」で算出し、算出した値に「ｊ＝１〜２０」を代入して、２０個の値を求める。
【００７４】
また、ノード１１１−４は、タスク「ｗ（２１：４０、２１：４０）」を実行する。具体的には、ノード１１１−４は、上記式（１）を条件「ｉ＝２１〜４０」で算出し、算出した値に「ｊ＝２１〜４０」を代入して、２０個の値を求める。同様に、ノード１１１−２、１１１−３、１１１−５、１１１−７及び１１１−８は、それぞれ自身に割り付けられたタスクを実行し、２０個の値を算出する。
【００７５】
なお、以下では、（第一演算）により算出された値をｖＡｎ（ｊ）と表記するものとする。なお、ｖＡｎ（ｊ）に付した「ｎ」は、ノード識別子の末尾に付した数字を示す。例えば、ノード１１１−１によって算出された値は、ｖＡ１（ｊ）であり、ノード１１１−２によって算出された値は、ｖＡ２（ｊ）である。すなわち、例えば、ノード１１１−１は、（第一演算）により、２０個のｖＡ１（１）〜ｖＡ１（２０）を算出する。また、例えば、ノード１１１−４は、（第一演算）により、２０個のｖＡ４（２１）〜ｖＡ４（４０）を算出する。
【００７６】
（第二演算）
続いて、ノード１１１−１〜１１１−８は、（第一演算）において算出した２０個のｖＡｎ（ｊ）を、所定のノード間で転送し、自身が算出したｖＡｎ（ｊ）と、他のノードから転送されたｖＡｎ（ｊ）とを加算する。ここでは、以下の（Ａ）〜（Ｄ）に示すタスク番号が割り付けられたノード間でデータ転送を行うものとする。
【００７７】
（Ａ）タスク番号「Ｔ１」及びタスク番号「Ｔ２」
（Ｂ）タスク番号「Ｔ３」及びタスク番号「Ｔ４」
（Ｃ）タスク番号「Ｔ５」及びタスク番号「Ｔ６」
（Ｄ）タスク番号「Ｔ７」及びタスク番号「Ｔ８」
【００７８】
図７−１に、（第二演算）においてデータ転送が行われるノードの一例を示す。図７−１に示すように、（第二演算）において、タスク番号「Ｔ１」が示すタスクを割り付けられたノード１１１−１と、タスク番号「Ｔ２」が示すタスクを割り付けられたノード１１１−６との間で、ｖＡｎ（ｊ）が転送される。すなわち、ノード１１１−１とノード１１１−６との間では、距離「３」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。
【００７９】
また、ノード１１１−２とノード１１１−３との間では、距離「２」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。また、ノード１１１−４とノード１１１−５との間では、距離「３」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。また、ノード１１１−７とノード１１１−８との間では、距離「１」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。
【００８０】
そして、ノード１１１−１は、自身が算出したｖＡ１（１）〜ｖＡ１（２０）と、ノード１１１−６から転送されたｖＡ６（１）〜ｖＡ６（２０）とを加算する。このとき、ノード１１１−１は、ｊの値が一致するｖＡｎ（ｊ）同士を加算する。具体的には、ノード１１１−１は、ｖＡ１（１）とｖＡ６（１）とを加算し、ｖＡ１（２）とｖＡ６（２）とを加算し、・・・、ｖＡ１（２０）とｖＡ６（２０）とを加算する。
【００８１】
同様にして、ノード１１１−２〜１１１−８は、自身が算出したｖＡｎ（ｊ）と、他のノードから転送されたｖＡｎ（ｊ）とを加算する。
【００８２】
すなわち、ノード１１１−１及び１１１−６は、（第二演算）により、上記式（１）を条件「ｉ＝１〜４０」で算出し、算出した値に「ｊ＝１〜２０」を代入した２０個の値を算出したことになる。また、ノード１１１−２及び１１１−３は、（第二演算）により、上記式（１）を条件「ｉ＝４１〜８０」で算出し、算出した値に「ｊ＝１〜２０」を代入した２０個の値を算出したことになる。
【００８３】
また、ノード１１１−４及び１１１−５は、（第二演算）により、上記式（１）を条件「ｉ＝１〜４０」で算出し、算出した値に「ｊ＝２１〜４０」を代入した２０個の値を算出したことになる。ノード１１１−７及び１１１−８は、（第二演算）により、上記式（１）を条件「ｉ＝４１〜８０」で算出し、算出した値に「ｊ＝２１〜４０」を代入した２０個の値を算出したことになる。
【００８４】
なお、以下では、（第二演算）により算出された値をｖＢｎ（ｊ）と表記するものとする。例えば、ノード１１１−１は、（第二演算）により、２０個のｖＢ１（１）〜ｖＢ１（２０）を算出する。また、例えば、ノード１１１−４は、（第二演算）により、２０個のｖＢ４（２１）〜ｖＢ４（４０）を算出する。
【００８５】
（第三演算）
続いて、ノード１１１−１〜１１１−８は、（第二演算）において算出した２０個のｖＢｎ（ｊ）を、所定のノード間で転送し、自身が算出したｖＢｎ（ｊ）と、他のノードから転送されたｖＢｎ（ｊ）とを加算する。ここでは、以下の（Ｅ）〜（Ｈ）に示すタスク番号が割り付けられたノード間でデータ転送を行うものとする。
【００８６】
（Ｅ）タスク番号「Ｔ１」及びタスク番号「Ｔ３」
（Ｆ）タスク番号「Ｔ２」及びタスク番号「Ｔ４」
（Ｇ）タスク番号「Ｔ５」及びタスク番号「Ｔ７」
（Ｈ）タスク番号「Ｔ６」及びタスク番号「Ｔ８」
【００８７】
図７−２に、（第三演算）においてデータ転送が行われるノードの一例を示す。図７−２に示すように、（第三演算）において、タスク番号「Ｔ１」が示すタスクを割り付けられたノード１１１−１と、タスク番号「Ｔ３」が示すタスクを割り付けられたノード１１１−２との間で、ｖＢｎ（ｊ）が転送される。すなわち、（第三演算）において、ノード１１１−１とノード１１１−２との間では、距離「１」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。
【００８８】
また、ノード１１１−３とノード１１１−６との間では、距離「３」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。また、ノード１１１−４とノード１１１−８との間では、距離「３」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。また、ノード１１１−５とノード１１１−７との間では、距離「２」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。
【００８９】
そして、ノード１１１−１は、自身が算出したｖＢ１（１）〜ｖＢ１（２０）と、ノード１１１−２から転送されたｖＢ２（１）〜ｖＢ２（２０）とを加算する。このとき、ノード１１１−１は、ｊの値が一致するｖＢｎ（ｊ）同士を加算する。具体的には、ノード１１１−１は、ｖＢ１（１）とｖＢ２（１）とを加算し、ｖＢ２（２）とｖＢ２（２）とを加算し、・・・、ｖＢ２（２０）とｖＢ２（２０）とを加算する。
【００９０】
同様にして、ノード１１１−２〜１１１−８は、自身が算出したｖＢ（ｊ）と、他のノードから転送されたｖＢ（ｊ）とを加算する。
【００９１】
すなわち、ノード１１１−１、１１１−２、１１１−３及び１１１−６は、（第三演算）により、上記式（１）を条件「ｉ＝１〜８０」で算出し、算出した値に「ｊ＝１〜２０」を代入した２０個の値を算出したことになる。また、ノード１１１−４、１１１−５、１１１−７及び１１１−８は、（第三演算）により、上記式（１）を条件「ｉ＝１〜８０」で算出し、算出した値に「ｊ＝２１〜４０」を代入した２０個の値を算出したことになる。
【００９２】
なお、以下では、（第三演算）により算出された値をｖＣｎ（ｊ）と表記するものとする。すなわち、ノード１１１−１、１１１−２、１１１−３及び１１１−６は、（第三演算）により、それぞれ２０個のｖＣ１（１）〜ｖＣ１（２０）、ｖＣ２（１）〜ｖＣ２（２０）、ｖＣ３（１）〜ｖＣ３（２０）、ｖＣ６（１）〜ｖＣ６（２０）を算出する。また、ノード１１１−４、１１１−５、１１１−７及び１１１−８は、（第三演算）により、それぞれ２０個のｖＣ４（２１）〜ｖＣ４（４０）、ｖＣ５（２１）〜ｖＣ５（４０）、ｖＣ７（２１）〜ｖＣ７（４０）、ｖＣ８（２１）〜ｖＣ８（４０）を算出する。
【００９３】
（第四演算）
続いて、ノード１１１−１〜１１１−８は、（第三演算）において算出した２０個のｖＣｎ（ｊ）について、上記式（２）に示した演算を行い、演算結果の総和を算出する。具体的には、ノード１１１−１は、「ｖＣ１（１）・ｖＣ１（１）」、「ｖＣ１（２）・ｖＣ１（２）」、・・・、「ｖＣ１（２０）・ｖＣ１（２０）」を算出し、算出した２０個の値の総和を算出する。また、ノード１１１−２は、「ｖＣ２（１）・ｖＣ２（１）」、「ｖＣ２（２）・ｖＣ２（２）」、・・・、「ｖＣ２（２０）・ｖＣ２（２０）」を算出し、算出された２０個の値の総和を算出する。
【００９４】
同様にして、ノード１１１−３〜１１１−８は、（第三演算）において算出した２０個のｖＣｎ（ｊ）について、上記式（２）に示した演算を行い、演算結果の総和を算出する。
【００９５】
なお、以下では、（第四演算）により算出された値をｖＤｎと表記するものとする。すなわち、ノード１１１−１、１１１−２、１１１−３及び１１１−６は、（第四演算）により、それぞれｖＤ１、ｖＤ２、ｖＤ３、ｖＤ６を算出する。また、ノード１１１−４、１１１−５、１１１−７及び１１１−８は、（第四演算）により、それぞれｖＤ４、ｖＤ５、ｖＤ７、ｖＤ８を算出する。
【００９６】
（第五演算）
続いて、ノード１１１−１〜１１１−８は、（第四演算）において算出したｖＤｎを、所定のノード間で転送し、自身が算出したｖＤｎと、他のノードから転送されたｖＤｎとを加算する。ここでは、以下の（Ｉ）〜（Ｌ）に示すタスク番号が割り付けられたノード間でデータ転送を行うものとする。
【００９７】
（Ｉ）タスク番号「Ｔ１」及びタスク番号「Ｔ５」
（Ｊ）タスク番号「Ｔ２」及びタスク番号「Ｔ６」
（Ｋ）タスク番号「Ｔ３」及びタスク番号「Ｔ７」
（Ｌ）タスク番号「Ｔ４」及びタスク番号「Ｔ８」
【００９８】
図７−３に、（第五演算）においてデータ転送が行われるノードの一例を示す。図７−３に示すように、（第五演算）において、タスク番号「Ｔ１」が示すタスクを割り付けられたノード１１１−１と、タスク番号「Ｔ５」が示すタスクを割り付けられたノード１１１−５との間で、距離「３」の通信経路を介してｖＤｎが転送される。
【００９９】
また、ノード１１１−２とノード１１１−７との間では、距離「３」の通信経路を介してｖＤｎが転送される。また、ノード１１１−３とノード１１１−８との間では、距離「３」の通信経路を介してｖＤｎが転送される。また、ノード１１１−４とノード１１１−６との間では、距離「３」の通信経路を介してｖＤｎが転送される。
【０１００】
そして、ノード１１１−１は、自身が算出したｖＤ１と、ノード１１１−５から転送されたｖＤ５とを加算する。これにより、ノード１１１−１は、上記式（３）に示したｈを算出する。同様にして、ノード１１１−２〜１１１−８は、自身が算出したｖＤと、他のノードから転送されたｖＤとを加算することにより、ｈを算出する。
【０１０１】
このようにして、ノード１１１−１〜１１１−８は、自身に割り付けられたタスクを実行することにより、上記式（３）に示したｈを算出する。ｈを算出する処理は、１個の核心処理であるので、ノード１１１−１〜１１１−８は、上述したｈを算出する処理を、例えば、「ｉ」や「ｊ」の条件を変えながら繰り返し行うことになる。
【０１０２】
次に、上述したタスクを実行しているノード１１１−１〜１１１−８によって収集される性能情報について説明する。まず、図８−１を用いて、上述した（第一演算）及び（第二演算）を実行しているノード１１１−１〜１１１−８によって収集される性能情報について説明する。図８−１は、第一演算及び第二演算を実行しているノード１１１−１〜１１１−８によって収集される性能情報の一例を示す図である。
【０１０３】
図８−１に示した例では、ノード１１１−１〜１１１−８は、性能情報として、通信パターンや、通信量、通信時間、演算内容、演算時間を収集する。図７−１を用いて説明したように、（第二演算）において、ノード１１１−１とノード１１１−６とは、相互にデータの送受を行う。同様に、ノード１１１−２とノード１１１−３とはデータの送受を行い、ノード１１１−４とノード１１１−５とはデータの送受を行い、ノード１１１−７とノード１１１−８とはデータの送受を行う。
【０１０４】
したがって、ノード１１１−１〜１１１−８は、図８−１に示すように、「通信パターン」として、例えば、「１１１−１⇔１１１−６」、「１１１−２⇔１１１−３」、「１１１−４⇔１１１−５」、「１１１−７⇔１１１−８」といった情報を収集する。なお、図８−１に示した例において、通信パターンが「Ｘ⇔Ｙ」である場合、ノードＸとノードＹとが通信を行うことを示す。
【０１０５】
また、上述したように、（第二演算）では、２０個のｖＡｎ（ｊ）がノード間で転送される。したがって、ノード１１１−１〜１１１−８は、図８−１に示すように、「通信量」として、例えば、「２０個の値」といった情報を収集する。
【０１０６】
ここで、（第二演算）において行われる転送処理にかかる時間を「ｔｓ１（Ｎ）」、「ｔｓ２（Ｎ）」、「ｔｓ３（Ｎ）」のいずれかにより示すものとする。なお、ｔｓ１（Ｎ）〜ｔｓ３（Ｎ）のうち、「ｔｓ」の後に付した数値「１」〜「３」は、通信経路の距離を示し、「Ｎ」は、転送された値の数を示す。すなわち、ｔｓ１（２０）は、距離が「１」である通信経路を介して、２０個の値が転送されたことを示す。また、ｔｓ２（２０）は、距離が「２」である通信経路を介して、２０個の値が転送されたことを示す。
【０１０７】
したがって、ノード１１１−１〜１１１−８は、図８−１に示すように、通信パターン「１１１−１⇔１１１−６」に対応する「通信時間」として、「ｔｓ３（２０）」といった情報を収集する。これは、ノード１１１−１とノード１１１−６との間は、距離が「３」である通信経路によって接続されているからである。
【０１０８】
同様に、ノード１１１−１〜１１１−８は、通信パターン「１１１−２⇔１１１−３」に対応する「通信時間」として、「ｔｓ２（２０）」といった情報を収集する。また、ノード１１１−１〜１１１−８は、通信パターン「１１１−４⇔１１１−５」に対応する「通信時間」として、「ｔｓ３（２０）」といった情報を収集する。また、ノード１１１−１〜１１１−８は、通信パターン「１１１−７⇔１１１−８」に対応する「通信時間」として、「ｔｓ１（２０）」といった情報を収集する。
【０１０９】
また、上述したように、（第一演算）及び（第二演算）では、加算処理が行われるので、ノード１１１−１〜１１１−８は、図８−１に示すように、「演算内容」として、例えば、「加算」といった情報を収集する。
【０１１０】
ここで、（第一演算）にかかる演算時間を「ｔａ（Ｎ）」により示し、（第二演算）にかかる演算時間を「ｔｂ（Ｎ）」により示すものとする。なお、Ｎは、演算処理が行われた値の数を示す。したがって、ノード１１１−１〜１１１−８は、図８−１に示すように、「演算時間」として、「ｔａ（２０）＋ｔｂ（２０）」といった情報を収集する。
【０１１１】
このようにして、ノード１１１−１〜１１１−８は、（第一演算）及び（第二演算）を実行している場合に、図８−１に示したような性能情報を収集する。ここで、（第一演算）及び（第二演算）にかかる実行時間について検討する。ノード１１１−１〜１１１−８は、互いに並列処理を行うので、（第一演算）及び（第二演算）にかかる実行時間は、各ノード間で行われる転送処理にかかる通信時間の最大値と、各ノードにより行われる演算にかかる演算時間の最大値との総和になる。
【０１１２】
（第一演算）及び（第二演算）における通信時間は、図８−１に示すように、「ｔｓ１（２０）」、「ｔｓ２（２０）」、「ｔｓ３（２０）」の３種類が存在する。上述したように、「距離」の値が大きい通信経路を介して通信を行うほど通信時間がかかるので、上記の通信時間の間には「ｔｓ１（２０）  ＜  ｔｓ２（２０）  ＜  ｔｓ３（２０）」の関係が成り立つ。すなわち、（第一演算）及び（第二演算）における通信時間の最大値は、「ｔｓ３（２０）」である。
【０１１３】
また、（第一演算）及び（第二演算）における演算時間は、図８−１に示すように、全て「ｔａ（２０）＋ｔｂ（２０）」である。すなわち、（第一演算）及び（第二演算）における演算時間の最大値は、「ｔａ（２０）＋ｔｂ（２０）」である。
【０１１４】
以上のことから、（第一演算）及び（第二演算）にかかる実行時間は、「ｔｓ３（２０）＋ｔａ（２０）＋ｔｂ（２０）」である。
【０１１５】
なお、図８−１に示した各性能情報は、「通信パターン」に示したノードによって収集される。具体的には、１行目に示した性能情報は、ノード１１１−１及び１１１−６によって収集される。また、２行目に示した性能情報は、ノード１１１−２及び１１１−３によって収集され、３行目に示した性能情報は、ノード１１１−４及び１１１−５によって収集され、４行目に示した性能情報は、ノード１１１−７及び１１１−８によって収集される。
【０１１６】
続いて、図８−２を用いて、（第三演算）を実行しているノード１１１−１〜１１１−８によって収集される性能情報について説明する。図８−２は、第三演算を実行しているノード１１１−１〜１１１−８によって収集される性能情報の一例を示す図である。
【０１１７】
図７−２を用いて説明したように、（第三演算）において、ノード１１１−１とノード１１１−２とは、相互にデータの送受を行う。また、ノード１１１−３とノード１１１−６とはデータの送受を行い、ノード１１１−４とノード１１１−８とはデータの送受を行い、ノード１１１−５とノード１１１−７とはデータの送受を行う。
【０１１８】
したがって、ノード１１１−１〜１１１−８は、図８−２に示すように、「通信パターン」として、「１１１−１⇔１１１−２」、「１１１−３⇔１１１−６」、「１１１−４⇔１１１−８」、「１１１−５⇔１１１−７」といった情報を収集する。
【０１１９】
また、上述したように、（第三演算）では、２０個のｖＢｎ（ｊ）がノード間で転送される。したがって、ノード１１１−１〜１１１−８は、図８−２に示すように、「通信量」として、例えば、「２０個の値」といった情報を収集する。
【０１２０】
また、ノード１１１−１〜１１１−８は、図８−２に示すように、通信パターン「１１１−１⇔１１１−２」に対応する「通信時間」として、「ｔｓ１（２０）」といった情報を収集する。これは、ノード１１１−１とノード１１１−２との間は、距離が「１」である通信経路によって接続されているからである。
【０１２１】
同様に、ノード１１１−１〜１１１−８は、通信パターン「１１１−３⇔１１１−６」に対応する「通信時間」として、「ｔｓ３（２０）」といった情報を収集する。また、ノード１１１−１〜１１１−８は、通信パターン「１１１−４⇔１１１−８」に対応する「通信時間」として、「ｔｓ３（２０）」といった情報を収集する。また、ノード１１１−１〜１１１−８は、通信パターン「１１１−５⇔１１１−７」に対応する「通信時間」として、「ｔｓ２（２０）」といった情報を収集する。
【０１２２】
ここで、（第三演算）にかかる演算時間を「ｔｃ（Ｎ）」により示すものとする。したがって、ノード１１１−１〜１１１−８は、図８−２に示すように、「演算時間」として、「ｔｃ（２０）」といった情報を収集する。
【０１２３】
このようにして、ノード１１１−１〜１１１−８は、（第三演算）を実行している場合に、図８−２に示したような性能情報を収集する。ここで、（第三演算）にかかる実行時間について検討する。上述したように、「ｔｓ１（２０）＜ｔｓ２（２０）＜ｔｓ３（２０）」の関係が成り立つので、（第三演算）にかかる実行時間は、「ｔｓ３（２０）＋ｔｃ（２０）」である。
【０１２４】
続いて、（第四演算）を実行しているノード１１１−１〜１１１−８によって収集される性能情報について説明する。（第四演算）では、ノード間でデータの送受は行われず、各ノードによって乗算及び加算処理が行われる。ここでは、（第四演算）にかかる演算時間を「ｔｄ（Ｎ）」により示すものとする。したがって、ノード１１１−１〜１１１−８は、「演算時間」として、「ｔｄ（２０）」といった情報を収集する。
【０１２５】
続いて、図８−３を用いて、（第五演算）を実行しているノード１１１−１〜１１１−８によって収集される性能情報について説明する。図８−３は、第五演算を実行しているノード１１１−１〜１１１−８によって収集される性能情報の一例を示す図である。
【０１２６】
図７−３を用いて説明したように、（第五演算）において、ノード１１１−１とノード１１１−５とは、相互にデータの送受を行う。また、ノード１１１−２とノード１１１−７とはデータの送受を行い、ノード１１１−３とノード１１１−８とはデータの送受を行い、ノード１１１−４とノード１１１−６とはデータの送受を行う。
【０１２７】
したがって、ノード１１１−１〜１１１−８は、図８−３に示すように、「通信パターン」として、「１１１−１⇔１１１−５」、「１１１−２⇔１１１−７」、「１１１−３⇔１１１−８」、「１１１−４⇔１１１−６」といった情報を収集する。
【０１２８】
また、上述したように、（第五演算）では、１個のｖＤｎがノード間で転送される。したがって、ノード１１１−１〜１１１−８は、図８−３に示すように、「通信量」として、例えば、「１個の値」といった情報を収集する。
【０１２９】
また、ノード１１１−１〜１１１−８は、図８−３に示すように、通信パターン「１１１−１⇔１１１−５」に対応する「通信時間」として、「ｔｓ３（１）」といった情報を収集する。同様に、ノード１１１−１〜１１１−８は、通信パターン「１１１−２⇔１１１−７」に対応する「通信時間」として、「ｔｓ３（１）」といった情報を収集する。また、ノード１１１−１〜１１１−８は、通信パターン「１１１−３⇔１１１−８」に対応する「通信時間」として、「ｔｓ３（１）」といった情報を収集する。また、ノード１１１−１〜１１１−８は、通信パターン「１１１−４⇔１１１−６」に対応する「通信時間」として、「ｔｓ３（１）」といった情報を収集する。
【０１３０】
ここで、（第五演算）にかかる演算時間を「ｔｅ（Ｎ）」により示すものとする。したがって、ノード１１１−１〜１１１−８は、図８−３に示すように、「演算時間」として、「ｔｅ（１）」といった情報を収集する。
【０１３１】
このようにして、ノード１１１−１〜１１１−８は、（第五演算）を実行している場合に、図８−３に示したような性能情報を収集する。すなわち、（第五演算）にかかる実行時間は、「ｔｓ３（１）＋ｔｅ（１）」である。
【０１３２】
以上のように、図６に示した例のように、ノード１１１−１〜１１１−８にタスクが割り付けられた場合、ジョブにおける１個の核心処理を実行する時間は、上述した（第一演算）〜（第五演算）にかかる実行時間の総和になる。具体的には、（第一演算）〜（第五演算）にかかる実行時間の総和は、以下に示す値になる。
【０１３３】
【数４】
2010257056.tif 000006
【０１３４】
次に、性能予測部１３０による割付パターン予測処理について説明する。性能予測部１３０は、図８−１〜図８−３に示した性能情報に基づいて、最適な割付パターンを予測する。ここで言う「最適な割付パターン」とは、ジョブの実行を最も高速に実行できる割付パターンを示す。
【０１３５】
性能予測部１３０は、ノード１１１−１〜１１１−８に割り付けるタスクを変動させながら、図８−１〜図８−３に示した性能情報を用いて、１個の核心処理の実行時間を予測する。例えば、性能予測部１３０は、ノード１１１−１〜１１１−８に、それぞれタスク番号Ｔ１、Ｔ３、Ｔ５、Ｔ７、Ｔ２、Ｔ４、Ｔ６、Ｔ８を割り付けたり、タスク番号Ｔ１、Ｔ４、Ｔ７、Ｔ２、Ｔ５、Ｔ８、Ｔ３、Ｔ６を割り付けたりして、核心処理の実行時間を予測する。
【０１３６】
このとき、性能予測部１３０は、図８−１〜図８−３に示した通信時間や、演算時間を用いて、１個の核心処理の実行時間を予測する。そして、性能予測部１３０は、予測した実行時間と割付パターンの組合せの中から、核心処理を最も高速に実行できる割付パターンを特定する。続いて、性能予測部１３０は、特定した割付パターンが現行の割付パターンよりも高速に核心処理を実行できる場合に、特定した割付パターンをタスク割付部１２２へ送信する。
【０１３７】
ここで、図９に、性能予測部１３０によって特定された割付パターンの一例を示す。図９に示すように、ノード１１１−１〜１１１−８は、それぞれ、タスク番号Ｔ１〜Ｔ８が示すタスクが割り付けられる。性能予測部１３０は、図９に示すようにタスクが割り付けられた場合に、核心処理を最も高速に実行できると予測したことになる。
【０１３８】
以下に、図９に示した例のようにタスクが割り付けられたノード１１１−１〜１１１−８によって行われる処理を、（第一演算）〜（第五演算）に分けて説明する。
【０１３９】
（第一演算）
図９に示した例のようにタスクが割り付けられた場合、ノード１１１−１は、タスク「ｗ（１：２０、１：２０）」を実行する。同様に、ノード１１１−２〜１１１−８は、それぞれ図９に示したタスクを実行する。
【０１４０】
（第二演算）
続いて、ノード１１１−１〜１１１−８は、（第一演算）において算出した２０個のｖＡｎ（ｊ）を、所定のノード間で転送し、自身が算出したｖＡｎ（ｊ）と、他のノードから転送されたｖＡｎ（ｊ）とを加算する。ここでは、上記例と同様に、上述した（Ａ）〜（Ｄ）に示したノード間でデータ転送を行うものとする。
【０１４１】
図１０−１に、（第二演算）においてデータ転送が行われるノードの一例を示す。図１０−１に示すように、タスク番号「Ｔ１」が示すタスクを割り付けられたノード１１１−１と、タスク番号「Ｔ２」が示すタスクを割り付けられたノード１１１−２との間で、ｖＡｎ（ｊ）が転送される。すなわち、ノード１１１−１とノード１１１−２との間では、距離「１」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。
【０１４２】
同様に、ノード１１１−３とノード１１１−４との間では、距離「１」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。また、ノード１１１−５とノード１１１−６との間では、距離「１」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。また、ノード１１１−７とノード１１１−８との間では、距離「１」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。
【０１４３】
（第三演算）
続いて、ノード１１１−１〜１１１−８は、（第二演算）において算出した２０個のｖＢｎ（ｊ）を、所定のノード間で転送し、自身が算出したｖＢｎ（ｊ）と、他のノードから転送されたｖＢｎ（ｊ）とを加算する。ここでは、上記例と同様に、上述した（Ｅ）〜（Ｈ）に示したノード間でデータ転送を行うものとする。
【０１４４】
図１０−２に、（第三演算）においてデータ転送が行われるノードの一例を示す。図１０−２に示すように、タスク番号「Ｔ１」が示すタスクを割り付けられたノード１１１−１と、タスク番号「Ｔ３」が示すタスクを割り付けられたノード１１１−３との間で、距離「２」の通信経路を介して２０個のｖＡｎ（ｊ）が転送される。
【０１４５】
同様に、ノード１１１−２とノード１１１−４との間では、距離「２」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。また、ノード１１１−５とノード１１１−７との間では、距離「２」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。また、ノード１１１−６とノード１１１−８との間では、距離「２」の通信経路を介して２０個のｖＢｎ（ｊ）が転送される。
【０１４６】
（第四演算）
続いて、ノード１１１−１〜１１１−８は、（第三演算）において算出した２０個のｖＣｎ（ｊ）について、上記式（２）に示した演算を行い、演算結果の総和を算出する。
【０１４７】
（第五演算）
続いて、ノード１１１−１〜１１１−８は、（第四演算）において算出したｖＤｎを、所定のノード間で転送し、自身が算出したｖＤｎと、他のノードから転送されたｖＤｎとを加算する。ここでは、上記例と同様に、上述した（Ｉ）〜（Ｌ）に示したノード間でデータ転送を行うものとする。
【０１４８】
図１０−３に、（第五演算）においてデータ転送が行われるノードの一例を示す。図１０−３に示すように、タスク番号「Ｔ１」が示すタスクを割り付けられたノード１１１−１と、タスク番号「Ｔ５」が示すタスクを割り付けられたノード１１１−５との間で、距離「３」の通信経路を介してｖＤｎが転送される。
【０１４９】
同様に、ノード１１１−２とノード１１１−６との間では、距離「３」の通信経路を介してｖＤｎが転送される。また、ノード１１１−３とノード１１１−７との間では、距離「３」の通信経路を介してｖＤｎが転送される。また、ノード１１１−４とノード１１１−８との間では、距離「３」の通信経路を介してｖＤｎが転送される。
【０１５０】
性能予測部１３０は、ノード１１１−１〜１１１−８によって上述した（第一演算）〜（第五演算）が行われることにより、上記式（３）に示したｈが算出されると予測する。そして、性能予測部１３０は、ノード１１１−１〜１１１−８によって上述した（第一演算）〜（第五演算）が行われる実行時間を予測する。図１１−１〜図１１−３を用いて、性能予測部１３０によって予測される実行時間について説明する。
【０１５１】
まず、図１１−１を用いて、性能予測部１３０によって予測される（第一演算）及び（第二演算）の実行時間について説明する。図１１−１は、第一演算及び第二演算の実行時間の予測例を示す図である。図１０−１を用いて説明したように、（第二演算）では、ノード１１１−１〜１１１−８との間で、距離が「１」である通信経路を介して通信が行われる。したがって、性能予測部１３０は、図１１−１に示すように、ノード間の通信時間が全て「ｔｓ１（２０）」であると予測する。
【０１５２】
また、性能予測部１３０は、（第一演算）及び（第二演算）にかかる演算時間が、図８−１に示した例と同様に「ｔａ（２０）＋ｔｂ（２０）」であると予測する。
【０１５３】
続いて、図１１−２を用いて、性能予測部１３０によって予測される（第三演算）の実行時間について説明する。図１１−２は、第三演算の実行時間の予測例を示す図である。図１０−２を用いて説明したように、（第三演算）では、ノード１１１−１〜１１１−８との間で、距離が「２」である通信経路を介して通信が行われる。したがって、性能予測部１３０は、図１１−２に示すように、ノード間の通信時間が全て「ｔｓ２（２０）」であると予測する。
【０１５４】
また、性能予測部１３０は、（第三演算）にかかる演算時間が、図８−２に示した例と同様に「ｔｃ（２０）」であると予測する。
【０１５５】
続いて、性能予測部１３０によって予測される（第四演算）の実行時間について説明する。（第四演算）では、ノード間でデータの送受は行われず、各ノードによって乗算及び加算処理が行われる。したがって、性能予測部１３０は、（第四演算）にかかる演算時間が、「ｔｄ（２０）」であると予測する。
【０１５６】
続いて、図１１−３を用いて、性能予測部１３０によって予測される（第五演算）の実行時間について説明する。図１１−３は、第五演算の実行時間の予測例を示す図である。図１０−３を用いて説明したように、（第五演算）では、ノード１１１−１〜１１１−８との間で、距離が「３」である通信経路を介して通信が行われる。したがって、性能予測部１３０は、図１１−３に示すように、ノード間の通信時間が全て「ｔｓ３（１）」であると予測する。
【０１５７】
また、性能予測部１３０は、図１１−３に示すように、（第五演算）にかかる演算時間が、図８−３に示した例と同様に「ｔｅ（１）」であると予測する。
【０１５８】
そして、性能予測部１３０は、予測した（第一演算）〜（第五演算）の実行時間の総和を算出する。具体的には、（第一演算）〜（第五演算）の実行時間の総和は、以下に示す値になる。
【０１５９】
【数５】
2010257056.tif 000007
【０１６０】
このようにして、性能予測部１３０は、図９に示した例のようにノード１１１−１〜１１１−８にタスクを割り付けた場合における核心処理の実行時間を予測する。そして、性能予測部１３０は、現行の割付パターンによる核心処理の実行時間と、最適な割付パターンによる核心処理の実行時間とを比較する。具体的には、性能予測部１３０は、上記式（４）によって示される実行時間から、上記式（５）によって示される実行時間を減算する。減算結果は以下に示す値となる。
【０１６１】
【数６】
2010257056.tif 000008
【０１６２】
上述したように「ｔｓ３（２０）＞ｔｓ２（２０）＞ｔｓ１（２０）」が成り立つため、上記式（６）は、正の値となる。すなわち、上記式（６）により、最適な割付パターンによる核心処理の実行時間は、現行の割付パターンによる核心処理の実行時間よりも短くなることが分かる。
【０１６３】
このように、並列処理装置１００は、ジョブ実行開始時に図６に示した例のようにタスクを割り付けた場合、ジョブを実行中に図９に示した例のようにタスクを割り付け直す。これにより、並列処理装置１００は、核心処理を高速に実行することができるので、ジョブを高速に実行することができる。
【０１６４】
なお、上記例では、ノード１１１−１〜１１１−８が全て同一の処理性能を有することを前提として説明した。したがって、ノード１１１−１〜１１１−８における通信時間や演算時間は全て同一であることを前提とした。例えば、図８−１に示した例において、「１１１−１⇔１１１−６」における通信時間と、「１１１−４⇔１１１−５」における通信時間とは、同一であるものとした。また、例えば、図８−１に示した例において、ノード１１１−１〜１１１−８における演算時間は、同一であるものとした。
【０１６５】
しかし、ノード１１１−１〜１１１−８の処理性能が異なる場合、通信時間や演算時間は、ノード１１１−１〜１１１−８によって異なる。かかる場合、ノード１１１−１〜１１１−８は、性能情報として、それぞれ異なる通信時間や演算時間を収集する。そして、並列処理装置１００は、収集された性能情報に基づいて、ジョブの実行時間を予測する。したがって、並列処理装置１００は、ノード１１１−１〜１１１−８の処理性能が異なる場合であっても、最適な割付パターンを予測することができる。
【０１６６】
また、上記例では、性能予測部１３０が、性能情報の「演算内容」を、予測処理に用いない例を示した。しかし、性能予測部１３０は、演算内容を用いて予測処理を行ってもよい。例えば、高速処理できる演算がノードによって異なる場合がある。具体的には、ノード１１１−１は、算術論理演算を高速に処理できるが、浮動小数点演算を高速に処理できない場合がある。一方、ノード１１１−２は、算術論理演算を高速に処理できないが、浮動小数点演算を高速に処理できる場合がある。このような場合に、性能予測部１３０は、「演算内容」に基づいて、高速に処理できるノードに対してタスクを割り付けるようにしてもよい。
【０１６７】
［実施例１に係る並列処理装置による処理手順］
次に、図１２を用いて、実施例１に係る並列処理装置１００による処理手順について説明する。図１２は、実施例１に係る並列処理装置１００による処理手順を示すフローチャートである。
【０１６８】
図１２に示すように、並列処理装置１００のジョブ制御部１２０は、ジョブの実行を開始する旨の指示を受け付けた場合に（ステップＳ１０１肯定）、かかるジョブを実行するノードを確保する（ステップＳ１０２）。
【０１６９】
続いて、ジョブ制御部１２０のタスク割付部１２２は、ステップＳ１０２において確保された各ノードに対して、ジョブに含まれるタスクを割り付ける（ステップＳ１０３）。そして、各ノードは、自身に割り付けられたタスクを実行する（ステップＳ１０４）。また、各ノードは、タスクを実行している間に、性能情報を収集する（ステップＳ１０５）。
【０１７０】
続いて、ジョブ制御部１２０の性能情報取得部１２１は、各ノードによってタスクを実行されてから所定の時間が経過した場合に（ステップＳ１０６肯定）、各ノードから性能情報を取得する（ステップＳ１０７）。
【０１７１】
続いて、性能予測部１３０は、性能情報取得部１２１によって取得された性能情報に基づいて、割付パターンを変動させてジョブを実行する時間を予測する（ステップＳ１０８）。続いて、性能予測部１３０は、シミュレーションした実行時間と割付パターンの組合せの中から、最も実行時間が短くなる割付パターンを特定する。
【０１７２】
そして、性能予測部１３０は、特定した割付パターンの方が、現行の割付パターンよりも高速にジョブを実行できる場合に（ステップＳ１０９肯定）、特定した割付パターンをタスク割付部１２２へ送信する。
【０１７３】
続いて、ジョブ制御部１２０は、各ノードに対してタスクの実行を中断させる（ステップＳ１１０）。続いて、タスク割付部１２２は、性能予測部１３０によって特定された割付パターンに基づいて各ノードにタスクを割り付ける（ステップＳ１１１）。
【０１７４】
続いて、ジョブ制御部１２０は、各ノードに対して、タスクの実行に用いられる各種データを相互に転送するように指示する。かかる指示を受け付けた各ノードは、タスクの実行に用いる各種データを相互に転送する（ステップＳ１１２）。
【０１７５】
そして、ジョブ制御部１２０は、各ノードによる転送処理が終了した場合に、各ノードに対して、ジョブの実行を再開するように指示する。かかる指示を受け付けた各ノードは、新たに割り付けられたタスクを実行する（ステップＳ１１３）。
【０１７６】
なお、性能予測部１３０によって特定された割付パターンが、現行の割付パターンよりも高速にジョブを実行できない場合（ステップＳ１０９否定）、並列処理装置１００は、処理を終了する。
【０１７７】
［実施例１の効果］
上述してきたように、実施例１に係る並列処理装置１００は、ジョブの実行中に、各ノードから性能情報を取得する。そして、並列処理装置１００は、取得した性能情報に基づいて、ジョブを高速に実行できる割付パターンが予測された場合に、ジョブの実行を中断して、予測された割付パターンに基づいて各ノードにタスクを割り付けてジョブの実行を再開する。ジョブが実行中である場合や中断中である場合、かかるジョブを実行しているノードは、実行中や中断中のジョブを実行できなくなることはない。このため、実施例１に係る並列処理装置１００は、ジョブを高速に実行できる割付パターンに基づいて、確実に各ノードにタスクを割り付けることができる。その結果、並列処理装置１００は、ジョブを高速に実行することができる。
【０１７８】
また、実施例１に係る並列処理装置１００は、割付パターンごとにジョブの実時間を予測するので、ジョブを高速に実行できる割付パターンを確実に予測することができる。
【０１７９】
また、実施例１に係る並列処理装置１００は、性能情報として、タスク実行時におけるノード間の通信量及び通信時間、ノードにおいて実行される演算の内容及び演算にかかる時間を取得する。これにより、並列処理装置１００は、実際にタスクが実行された際に収集された通信時間や演算時間等に基づいて、ジョブを高速に実行できる割付パターンを高精度に予測することができる。
【０１８０】
特に、ジョブがシミュレーションプログラムである場合、並列処理装置１００は、核心処理を数回だけ実行した時点で性能情報を取得すれば、ジョブの実行時間を高精度に予測することができる。すなわち、並列処理装置１００は、核心処理の実行時間を高速化することができるので、ジョブ全体の実行時間を高速化することができる。
【０１８１】
また、従来の並列処理装置では、シミュレータによって予測された割付パターンにしたがって各ノードにタスクを割り付ける場合、プログラム作成者が、プログラム内に割付パターンを記述していた。このため、従来の並列処理装置を用いると、プログラム作成者にかかる負担が増大していた。一方、実施例１に係る並列処理装置１００は、ジョブの実行中に、並列処理装置１００自身が最適な割付パターンに基づいて、各ノードにタスクを割り付けるので、プログラム作成者にかかる負担を低減することができる。
【０１８２】
また、実施例１に係る並列処理装置１００は、特に、ノードによって処理性能が異なる場合や、ノード間によって通信時間が異なるシステムに適用する場合に有効である。なお、現在の計算機システムは、大規模になっているので、全てのノードを同一の処理性能にしたり、各ノード間をクロスバースイッチなどにより接続することは困難である。したがって、多くの計算機システムは、処理性能の異なるノードを有したり、各ノード間がツリー型、トーラス型などのネットワークトポロジーにより接続されている。
【０１８３】
また、実施例１に係る並列処理装置１００は、特に、複数の利用者によって用いられるシステムに提供する場合に有効である。これは、複数の利用者によって用いられる場合、従来の並列処理装置では、シミュレータによって予測された割付パターンにしたがって各ノードにタスクを割り付けることができないケースが多発するからである。一方、実施例１に係る並列処理装置１００は、複数の利用者によって用いられる場合であっても、最初に確保したノードに対して最適な割付パターンを予測するので、ジョブを高速に実行することができる。
【実施例２】
【０１８４】
ところで、本願の開示する並列処理装置等は、上述した実施例以外にも、種々の異なる形態にて実施されてよい。そこで、実施例２では、本願に開示する並列処理装置等の他の実施例について説明する。
【０１８５】
［ノード］
上記実施例１では、並列処理装置１００が、ノード１１１−１〜１１１−ｎを有する態様について説明した。しかし、本願の開示する並列処理装置は、ノード１１１−１〜１１１−ｎを有していない態様にも適用することができる。例えば、本願の開示する並列処理装置は、並列処理装置とノード１１１−１〜１１１−ｎとがネットワーク接続されている場合にも適用することができる。また、ノード１１１−１〜１１１−ｎは、パーソナルコンピュータやサーバ等の情報処理装置であってもよい。
【０１８６】
［性能予測部］
また、上記実施例１では、並列処理装置１００が性能予測部１３０を有する例を示した。しかし、並列処理装置は、性能予測部１３０と同様の機能を有する性能予測装置と接続されていてもよい。図１３に、性能予測装置と接続される並列処理装置２００の構成を示す。なお、ここでは、図３に示した構成部位と同様の機能を有する部位には同一符号を付すこととして、その詳細な説明を省略する。図１３に示すように、並列処理装置２００は、図３に示した並列処理装置１００と比較して、性能予測部１３０を有さない。また、並列処理装置２００は、性能予測装置３００と接続されている。並列処理装置２００は、並列計算部１１０から取得した性能情報を性能予測装置３００へ送信し、性能予測装置３００によって予測された割付パターンを受け付ける。
【０１８７】
［性能情報収集タイミング］
また、上記実施例１では、ノード１１１が、タスクを実行している間に性能情報を収集する例について説明した。しかし、ノード１１１は、所定の時間だけ性能情報を収集してもよい。例えば、処理対象のプログラムに、性能情報収集処理の開始タイミングを示す情報と、性能情報収集処理の終了タイミングを示す情報とを記述しておく。以下に、図１４を用いて具体的に説明する。
【０１８８】
図１４は、性能情報収集処理の開始終了タイミングが埋め込まれたジョブの一例を示す図である。図１４に示すように、ノード１１１は、まず、前処理を行う（ステップＳ３１）。続いて、ノード１１１は、性能情報収集処理の開始タイミングを示す情報を検知した場合に（ステップＳ３２）、性能情報収集処理を開始する。具体的には、ノード１１１は、核心処理を行うとともに、性能情報を収集する（ステップＳ３３−１及びＳ３３−２）。そして、各ノードは、性能情報収集処理の終了タイミングを示す情報を検知した場合に（ステップＳ３４）、性能情報収集処理を終了する。そして、性能情報取得部１２１は、性能情報収集処理の終了タイミングを示す情報を検知した場合に（ステップＳ３４）、性能情報を取得する（ステップＳ４１）。以降の処理は、図２に示した例と同様である。
【０１８９】
このように、処理対象のプログラムに、性能情報収集処理の開始及び終了タイミングを記述しておくことにより、ノード１１１は、所定の時間だけ性能情報収集処理を行えばよい。これにより、ノード１１１にかかる負荷を低減することができる。
【０１９０】
［割付処理］
また、上記実施例１では、並列処理装置１００がジョブの実行中に割付処理を１回行う場合を例に挙げて説明した。しかし、並列処理装置１００は、ジョブの実行中に、何度も割付処理を行ってもよい。図１５を用いて具体的に説明する。図１５は、割付処理を複数回行う例を説明するための図である。図１５に示すように、並列処理装置１００は、ステップＳ１２−４における核心処理が行われた後に、性能情報を取得して最適な割付パターンに基づいてタスクを割り付ける（ステップＳ５１）。また、並列処理装置１００は、ステップＳ１２−ｍにおける核心処理が行われた後に、再度、性能情報を取得して最適な割付パターンに基づいてタスクを割り付ける（ステップＳ５２）。
【０１９１】
このように割付処理を複数回行うことは、核心処理における通信パターンや演算内容が変動するジョブに適用する場合に有効である。なお、上述した性能情報収集処理の開始及び終了タイミングを、処理対象のプログラムに複数記述しておくことにより、並列処理装置１００は、核心処理における通信パターンや演算内容が変化したタイミングで、再度、割付処理を行うことができる。
【０１９２】
［複数のジョブ］
また、上記実施例１では、並列処理装置１００が１個のジョブを実行する場合を例に挙げて説明した。しかし、並列処理装置１００は、複数のジョブを実行する場合に、上述してきた割付処理を行ってもよい。具体的には、並列処理装置１００の性能情報取得部１２１は、複数のジョブに含まれるタスクが割り付けられた全てのノード１１１から性能情報を取得する。そして、性能予測部１３０は、性能情報取得部１２１によって取得された性能情報に基づいて、複数のジョブに跨って割付パターンを変動させて、複数のジョブの実行時間を予測する。続いて、性能予測部１３０は、複数のジョブを最も高速に実行できる割付パターンを特定する。そして、タスク割付部１２２は、性能予測部１３０によって、現行の割付パターンよりも高速に複数のジョブを実行できる割付パターンが予測された場合に、予測された割付パターンに基づいて各ノードにタスクを割り付ける。
【０１９３】
図１６に、複数のジョブを実行する場合における割付処理の一例を示す。図１６の上段に示すように、ジョブＡに含まれるタスクＴ１１〜Ｔ１４が、それぞれノード１１１−１、１１１−２、１１１−７及び１１１−８に割り付けられているものとする。また、ジョブＢに含まれるタスクＴ２１〜Ｔ２４が、それぞれノード１１１−３〜１１１−６に割り付けられているものとする。かかる場合に、並列処理装置１００は、ノード１１１−１〜１１１−８から性能情報を取得して、最適な割付パターンを予測する。そして、並列処理装置１００は、例えば、図１６の下段に示すように、タスクＴ１１〜Ｔ１４を、それぞれノード１１１−１〜１１１−４に割り付け、タスクＴ２１〜Ｔ２４を、それぞれノード１１１−５〜１１１−８に割り付ける。図１６に示した例の場合、割付パターン変更前よりも変更後の方が、ノード間の通信時間を短くすることができるので、ジョブＡ及びＢの実行時間を高速化することができると考えられる。
【０１９４】
［プログラム］
上記実施例１で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図１７を用いて、上記の実施例１における並列処理装置１００と同様の機能を有する並列処理プログラムを実行するコンピュータの一例を説明する。
【０１９５】
図１７は、並列処理プログラムを実行するコンピュータを示す図である。図１７に示すように、コンピュータ１０００は、ＲＡＭ（Random  Access  Memory）１０１０と、キャッシュ１０２０と、ＨＤＤ１０３０と、ＲＯＭ（Read  Only  Memory）１０４０と、ＣＰＵ（Central  Processing  Unit）１０５０とを有する。ＲＡＭ１０１０、キャッシュ１０２０、ＨＤＤ１０３０、ＲＯＭ１０４０、ＣＰＵ１０５０は、バス１０６０によって接続されている。
【０１９６】
ＲＯＭ１０４０には、上記の実施例１における並列処理装置１００と同様の機能を発揮する並列処理プログラムが予め記憶されている。具体的には、ＲＯＭ１０４０には、性能情報取得プログラム１０４１と、タスク割付プログラム１０４２と、性能予測プログラム１０４３とが記憶されている。
【０１９７】
そして、ＣＰＵ１０５０は、これらの性能情報取得プログラム１０４１と、タスク割付プログラム１０４２と、性能予測プログラム１０４３とを読み出して実行する。これにより、図１７に示すように、性能情報取得プログラム１０４１は、性能情報取得プロセス１０５１になり、タスク割付プログラム１０４２は、タスク割付プロセス１０５２になり、性能予測プログラム１０４３は、性能予測プロセス１０５３になる。
【０１９８】
なお、性能情報取得プロセス１０５１は、図３に示した性能情報取得部１２１に対応し、タスク割付プロセス１０５２は、図３に示したタスク割付部１２２に対応し、性能予測プロセス１０５３は、図３に示した性能予測部１３０に対応する。
【０１９９】
また、ＨＤＤ１０３０には、図１７に示すように、性能情報データ１０３１が設けられる。かかる性能情報データ１０３１は、性能情報取得プロセス１０５１によって取得される性能情報が記憶される。
【０２００】
なお、上記した各プログラム１０４１〜１０４３については、必ずしもＲＯＭ１０４０に記憶させなくてもよい。例えば、コンピュータ１０００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラム１０４１〜１０４３を記憶させてもよい。または、コンピュータ１０００の内外に備えられるハードディスクドライブ（ＨＤＤ）などの「固定用の物理媒体」にプログラム１０４１〜１０４３を記憶させてもよい。または、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ１０００に接続される「他のコンピュータ（またはサーバ）」にプログラム１０４１〜１０４３を記憶させてもよい。そして、コンピュータ１０００は、上述したフレキシブルディスク等から各プログラムを読み出して実行するようにしてもよい。
【０２０１】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２０２】
（付記１）複数の処理要素を含むジョブを複数のノードに実行させる並列処理装置であって、
前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得部と、
前記取得部によって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付部と
を備えたことを特徴とする並列処理装置。
【０２０３】
（付記２）前記取得部によって取得された性能情報に基づいて、割付パターンごとに前記ジョブを実行する時間を予測する性能予測部をさらに備え、
前記割付部は、前記性能予測部によって現行の割付パターンよりも高速に前記ジョブを実行する割付パターンが予測された場合に、前記性能予測部によって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする付記１に記載の並列処理装置。
【０２０４】
（付記３）前記取得部は、割付パターンごとに前記ジョブを実行する時間を予測する性能予測装置に対して、前記各ノードから取得した性能情報を送信し、
前記割付部は、前記性能予測装置によって現行の割付パターンよりも高速に前記ジョブを実行する割付パターンが予測された場合に、前記性能予測装置によって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする付記１に記載の並列処理装置。
【０２０５】
（付記４）前記ジョブは、同一又は近似する処理要素を複数含み、
前記取得部は、前記各ノードによって同一又は近似する処理要素が所定の回数実行された場合に、前記各ノードから性能情報を取得することを特徴とする付記１〜３のいずれか一つに記載の並列処理装置。
【０２０６】
（付記５）前記ジョブは、前記性能情報を収集し始めるタイミングを示す情報である開始タイミング情報と、前記性能情報の収集を終了するタイミングを示す情報である終了タイミング情報とを含み、
前記取得部は、前記終了タイミング情報を検知した場合に、前記複数のノードによって前記開始タイミング情報が示すタイミングから前記終了タイミング情報が示すタイミングの間に収集された性能情報を取得することを特徴とする付記１〜３のいずれか一つに記載の並列処理装置。
【０２０７】
（付記６）前記取得部は、複数のジョブに含まれる処理要素が割り付けられた各ノードから性能情報を取得し、
前記性能予測部は、前記取得部によって取得された性能情報に基づいて、前記複数のジョブに跨って割付パターンを変動させて前記複数のジョブを実行する時間を予測し、
前記割付部は、前記性能予測部によって、現行の割付パターンよりも高速に前記複数のジョブを実行する割付パターンが予測された場合に、前記性能予測部によって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする付記２、４又は５に記載の並列処理装置。
【０２０８】
（付記７）前記取得部は、前記性能情報として、前記各ノードから、処理要素実行時にデータを送受するノード間の情報である通信パターンと、処理要素実行時に送受されるデータの量である通信量及び通信時間と、前記各ノードにおいて実行される演算の内容及び演算にかかる時間とを取得することを特徴とする付記１〜６のいずれか一つに記載の並列処理装置。
【０２０９】
（付記８）複数の処理要素を含むジョブを複数のノードに実行させる並列処理装置による並列処理方法であって、
前記並列処理装置が、
前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得ステップと、
前記取得ステップによって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付ステップと
を含んだことを特徴とする並列処理方法。
【０２１０】
（付記９）前記取得ステップによって取得された性能情報に基づいて、割付パターンごとに前記ジョブを実行する時間を予測する性能予測ステップをさらに含み、
前記割付ステップは、前記性能予測ステップによって現行の割付パターンよりも高速に前記ジョブを実行する割付パターンが予測された場合に、前記性能予測ステップによって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする付記８に記載の並列処理方法。
【０２１１】
（付記１０）複数の処理要素を含むジョブを複数のノードに実行させる並列処理プログラムであって、
前記複数のノードによって前記ジョブが実行されている間に、前記複数のノードから処理要素実行時における性能に関する情報である性能情報を取得する取得手順と、
前記取得手順によって取得された性能情報に基づいて、現行の各ノードと各処理要素との組合せのパターンである割付パターンよりも前記ジョブを高速に実行する割付パターンが存在する場合に、該割付パターンに基づいて各ノードに処理要素を割り付ける割付手順と
をコンピュータに実行させることを特徴とする並列処理プログラム。
【０２１２】
（付記１１）前記取得手順によって取得された性能情報に基づいて、割付パターンごとに前記ジョブを実行する時間を予測する性能予測手順をさらにコンピュータに実行させ、
前記割付手順は、前記性能予測手順によって現行の割付パターンよりも高速に前記ジョブを実行する割付パターンが予測された場合に、前記性能予測手順によって予測された割付パターンに基づいて各ノードに処理要素を割り付けることを特徴とする付記１０に記載の並列処理プログラム。
【符号の説明】
【０２１３】
１００、２００          並列処理装置
１１０                  並列計算部
１１１                  ノード
１１１−１〜１１１−ｎ  ノード
１１２                  外部記憶装置
１１３                  主記憶装置
１１４                  退避用記憶装置
１１５ａ〜１１５ｄ      ＣＰＵ
１１６                  バス
１２０                  ジョブ制御部
１２１                  性能情報取得部
１２２                  タスク割付部
１３０                  性能予測部
３００                  性能予測装置
１０００                コンピュータ
１０１０                ＲＡＭ
１０２０                キャッシュ
１０３０                ＨＤＤ
１０３１                性能情報データ
１０４０                ＲＯＭ
１０４１                性能情報取得プログラム
１０４２                タスク割付プログラム
１０４３                性能予測プログラム
１０５０                ＣＰＵ
１０５１                性能情報取得プロセス
１０５２                タスク割付プロセス
１０５３                性能予測プロセス
１０６０                バス
【図１】
2010257056.tif 000009
【図２】
2010257056.tif 000010
【図３】
2010257056.tif 000011
【図４】
2010257056.tif 000012
【図５】
2010257056.tif 000013
【図６】
2010257056.tif 000014
【図７−１】
2010257056.tif 000015
【図７−２】
2010257056.tif 000016
【図７−３】
2010257056.tif 000017
【図８−１】
2010257056.tif 000018
【図８−２】
2010257056.tif 000019
【図８−３】
2010257056.tif 000020
【図９】
2010257056.tif 000021
【図１０−１】
2010257056.tif 000022
【図１０−２】
2010257056.tif 000023
【図１０−３】
2010257056.tif 000024
【図１１−１】
2010257056.tif 000025
【図１１−２】
2010257056.tif 000026
【図１１−３】
2010257056.tif 000027
【図１２】
2010257056.tif 000028
【図１３】
2010257056.tif 000029
【図１４】
2010257056.tif 000030
【図１５】
2010257056.tif 000031
【図１６】
2010257056.tif 000032
【図１７】
2010257056.tif 000033