(57)【要約】【課題】  一部の計算機の負荷が上昇したり、一部の計算機が停止したりした場合でも、全体の処理速度が低下することを防ぐ。【解決手段】  本発明の一態様に従った並列計算方法は、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す各々有効度が付与された複数のワーカ計算機とを用い、前記マスタ計算機が：各々価値を有する複数のジョブを生成し；生成された前記ジョブをジョブ記憶部内に格納し；前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出し；前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出し；前記有効度演算値が前記有効度閾値に満たないジョブを空きの前記ワーカ計算機に実行させ；前記ワーカ計算機から前記ジョブの実行結果を受け取り、前記受け取ったジョブを前記ジョブ記憶部から削除する。【選択図】  図１
2005242986.tif 000002
【特許請求の範囲】
【請求項１】
ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す各々有効度が付与された複数のワーカ計算機とを用いて並列計算処理を行う並列計算方法であって：
前記マスタ計算機が、
各々価値を有する複数のジョブを生成し；
生成された前記ジョブをジョブ記憶部内に格納し；
前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出し；
前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出し；
前記有効度演算値が前記有効度閾値に満たないジョブを空きの前記ワーカ計算機に実行させ；
前記ワーカ計算機から前記ジョブの実行結果を受け取り、前記受け取ったジョブを前記ジョブ記憶部から削除する；
並列計算方法。
【請求項２】
各前記ワーカ計算機にはグループ番号が付与されており、前記マスタ計算機は、同一のジョブを複数の前記ワーカ計算機に実行させる場合は、それぞれ異なるグループ番号を有するワーカ計算機に前記ジョブを実行させることを特徴とする請求項１に記載の並列計算方法。
【請求項３】
前記ワーカ計算機に付与されている有効度は、前記ワーカ計算機の信頼度及び計算能力のいずれかであることを特徴とする請求項１に記載の並列計算方法。
【請求項４】
前記マスタ計算機は、前記ジョブの価値を用いた演算により前記ジョブの有効度閾値を算出することを特徴とする請求項１に記載の並列計算方法。
【請求項５】
前記マスタ計算機は、前記ワーカ計算機からジョブの実行結果を受け取った後、当該ジョブを実行している他のワーカ計算機が存在する場合は、前記他のワーカ計算機に当該ジョブの実行を停止させることを特徴とする請求項１に記載の並列計算方法。
【請求項６】
前記マスタ計算機は、ジョブの価値の大きさの順位と、有効度閾値とを対応付けたテーブルを保持しており、前記テーブルに基づいて、前記有効度閾値を算出することを特徴とする請求項１に記載の並列計算方法。
【請求項７】
分岐限定法に従って最適化問題の計算を行うことを特徴とする請求項１に記載の並列計算方法。
【請求項８】
前記マスタ計算機は、回収した前記ジョブの実行結果の数が規定数に達した場合は、前記ジョブの実行結果の回収を終了する判定を下すことを特徴とする請求項１に記載の並列計算方法。
【請求項９】
ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行う並列計算方法であって：
前記マスタ計算機が、
複数のジョブを生成し；
生成した前記ジョブを前記ワーカ計算機に実行させ；
前記ワーカ計算機からジョブの実行結果を回収し；
所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する；
並列計算方法。
【請求項１０】
前記マスタ計算機は、回収した前記ジョブの実行結果の数が規定数に達した場合は、前記ジョブの実行結果の回収を終了する判定を下すことを特徴とする請求項９に記載の並列計算方法。
【請求項１１】
ニューラルネットワークの重み計算を行うことを特徴とする請求項１０に記載の並列計算方法。
【請求項１２】
ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行う並列計算方法であって：
前記マスタ計算機が、
各々価値を有する複数のジョブを生成し；
前記ジョブの価値に基づいて各前記ジョブの多重度を算出し；
算出された多重度に従って前記ジョブを前記ワーカ計算機に実行させ；
前記ワーカ計算機からジョブの実行結果を回収し；
所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する；
並列計算方法。
【請求項１３】
前記マスタ計算機は、回収した前記ジョブの実行結果の数が規定数に達した場合は、前記ジョブの実行結果の回収を終了する判定を下すことを特徴とする請求項１２に記載の並列計算方法。
【請求項１４】
遺伝的アルゴリズムに従った計算を行うことを特徴とする請求項１３に記載の並列計算方法。
【請求項１５】
ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す各々有効度が付与された複数のワーカ計算機とを用いて並列計算処理を行うシステムにおける前記マスタ計算機で実行する並列計算プログラムであって：
各々価値を有する複数のジョブを生成するステップと；
生成された前記ジョブをジョブ記憶部内に格納するステップと；
前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出するステップと；
前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出するステップと；
前記有効度演算値が前記有効度閾値に満たないジョブを空きの前記ワーカ計算機に実行させるステップと；
前記ワーカ計算機から前記ジョブの実行結果を受け取り、前記受け取ったジョブを前記ジョブ記憶部から削除するステップと；
を備えた並列計算プログラム。
【請求項１６】
ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行うシステムにおける前記マスタ計算機で実行する並列計算プログラムであって：
複数のジョブを生成するステップと；
生成した前記ジョブを前記ワーカ計算機に実行させる実行ステップと；
前記ワーカ計算機から前記ジョブの実行結果を回収する回収ステップと；
所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する判定ステップと；
を備えた並列計算プログラム。
【請求項１７】
ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行うシステムにおける前記マスタ計算機で実行する並列計算プログラムであって：
価値を有する複数のジョブを生成する生成ステップと；
前記ジョブの価値に基づいて各前記ジョブの多重度を算出する算出ステップと；
算出された多重度に従って前記ジョブを前記ワーカ計算機に実行させる実行ステップと；
前記ワーカ計算機からジョブの実行結果を回収する回収ステップと；
所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する判定ステップと；
を備えた並列計算プログラム。
【請求項１８】
複数のワーカ計算機にジョブを実行させて、前記ワーカ計算機から前記ジョブの実行結果を受け取る計算機であって：
価値を有するジョブを生成するジョブ生成部と；
生成された前記ジョブを格納するジョブ記憶部と；
前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出する有効度閾値算出部と；
各前記ワーカ計算機に付与された有効度を格納した有効度記憶部と；
前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出する有効度演算値算出部と；
前記有効度演算値が前記有効度閾値に満たないジョブを空いている前記ワーカ計算機に実行させ、前記ワーカ計算機から前記ジョブの実行結果を受け取った場合は、前記受け取ったジョブを前記ジョブ記憶部から削除するジョブ管理部と；
を備えた計算機。
【請求項１９】
複数のワーカ計算機にジョブを実行させて、前記ワーカ計算機から前記ジョブの実行結果を受け取る計算機であって：
複数のジョブを生成するジョブ生成部と；
生成した前記ジョブを前記ワーカ計算機に実行させ、前記ワーカ計算機からジョブの実行結果を回収するジョブ回収部と；
所定のジョブ結果回収終了条件に基づき、前記ジョブ結果の回収を終了するか否かを判定する判定部と；
を備えた計算機。
【請求項２０】
複数のワーカ計算機にジョブを実行させて、前記ワーカ計算機から前記ジョブの実行結果を受け取る計算機であって：
各々価値を有する複数のジョブを生成するジョブ生成部と；
前記ジョブの価値に基づいて各前記ジョブの多重度を算出するジョブ多重化部と；
算出された多重度に従って前記ジョブを前記ワーカ計算機に実行させ、前記ワーカ計算機からジョブの実行結果を回収するジョブ回収部と；
所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する判定部と；
を備えた計算機。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マスタ・ワーカ型の計算機システムを用いて複数のジョブを並列処理するための並列計算方法、並列計算プログラム及び計算機に関し、より詳しくは、一部の計算機が何らかの要因で高負荷になったり故障したりした場合でも、実行性能を著しく低下させることなく計算を進めることを可能にした並列計算方法、並列計算プログラム及び計算機に関する。
【背景技術】
【０００２】
複数のジョブを並列処理する計算機が存在する場合に処理速度の低下を防ぐ方法として負荷分散と称される手法がある。これは、負荷の高い計算機に割り当てる仕事(以降ジョブと記述する)の量を減らし他の計算機に割り当てることで負荷の均等化を図り、これにより処理速度の低下を阻止するものである(例えば、非特許文献１に負荷分散方式とその効果に関する記述がある)。
【０００３】
この負荷分散を用いた並列計算において、特定の計算機の負荷が、ジョブの実行途中で外的要因により動的に変化し、例えば上昇する場合がある。ジョブの実行途中で特定の計算機の負荷が上昇することをジョブの実行前に分かっていれば、この計算機へのジョブを減らし、他の計算機に割り振ることで負荷の上昇を抑えることができる。しかし、負荷の変動予測は一般に困難であるため、ジョブを適切に配分することは困難である。したがって、ある計算機の負荷が並列計算中に外的要因で上昇した場合、この計算機におけるジョブの終了が遅れ、この結果、並列計算全体の処理速度が低下する問題があった。
【０００４】
一方、この負荷分散を用いた並列計算においては、一部の計算機が高負荷になることの他、ジョブの実行の途中で計算機が故障により停止することもある。
【０００５】
計算機が故障により停止してしまう場合の対処方法としては大きく分けて３つの方法が考えられる。
【０００６】
第１番目として、あらかじめ予備のハードウェアを用意してハードウェアを多重化する方法がある。非特許文献２には、故障に対処するために、並行動作を行うハードウェア及び比較器を用いたシステムの構成法が記述されている。しかし、この方法ではハードウェアの構成が大規模になりコスト増につながる。
【０００７】
第２番目として、各計算機にミドルウェアを走らせて耐故障性を持たせるという方法がある。非特許文献３には、耐故障性実現のための基本技術であるチェックポインティング（check pointing）とミグレーション（migration）の技術の概要が述べてられている。チェックポインティングは、ある時点でのジョブの実行イメージを保存する技術である。ミグレーションは保存した実行イメージを他の計算機に移し、計算を再実行する機能である。計算機同士で互いに実行イメージを保存し合い、ダウンした計算機のジョブを他の計算機で実行することで、並列計算の停止を防ぐ。しかし、このようなチェックポインティング及びミグレーションを行うミドルウェアを全ての計算機に配るのは大変であり、また、定期的にチェックポインティングを行うことはジョブの実行に余計なオーバーヘッドがかかるという問題点がある。また、この方法では、故障が発見された時点で、ジョブを再実行するので、故障のない場合と比べて並列処理の実行性能は大きく劣ることになる。
【０００８】
第３番目として、全てのジョブを多重化して実行する方法がある。しかし、この方法であると、多重化した分だけジョブの数が余計に増えてしまう。例えば、２重化した場合にはジョブの数が２倍になってしまう。
【非特許文献１】Nicholas Carriero, David Gelernter著、”HOW TO WRITE PARALLEL PROGRAMS A FIRST COURSE”, The MIT Press. 79ページ。
【非特許文献２】Gregor v. Bochmann著「分散処理システム入門」産報出版、48ページ。
【非特許文献３】Douglas Thain, Todd Tannenbaum, Miron Livny著, "Condor and the Grid", John Wiley, 304ページ。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
このように、従来においては、並列処理の途中で一部の計算機の負荷が上昇したり、一部の計算機が停止したりした場合に、全体の処理速度の低下を防ぐことは困難であった。
【００１０】
本発明は、上記問題点に鑑みてなされたものであり、その目的は、一部の計算機の負荷が上昇したり、一部の計算機が停止したりした場合でも、全体の処理速度の低下を可及的に阻止する並列計算方法、並列計算プログラム及び計算機を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の一態様としての並列計算方法は、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す各々有効度が付与された複数のワーカ計算機とを用いて並列計算処理を行う並列計算方法であって：前記マスタ計算機が、  各々価値を有する複数のジョブを生成し；生成された前記ジョブをジョブ記憶部内に格納し；前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出し；前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出し；前記有効度演算値が前記有効度閾値に満たないジョブを空きの前記ワーカ計算機に実行させ；前記ワーカ計算機から前記ジョブの実行結果を受け取り、前記受け取ったジョブを前記ジョブ記憶部から削除する；ことを特徴とする。
【００１２】
本発明の一態様としての並列計算方法は、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行う並列計算方法であって：前記マスタ計算機が、複数のジョブを生成し；生成した前記ジョブを前記ワーカ計算機に実行させ；前記ワーカ計算機からジョブの実行結果を回収し；所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する；ことを特徴とする。
【００１３】
本発明の一態様としての並列計算方法は、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行う並列計算方法であって：前記マスタ計算機が、各々価値を有する複数のジョブを生成し；前記ジョブの価値に基づいて各前記ジョブの多重度を算出し；算出された多重度に従って前記ジョブを前記ワーカ計算機に実行させ；前記ワーカ計算機からジョブの実行結果を回収し；所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する；ことを特徴とする。
【００１４】
本発明の一態様としての並列計算プログラムは、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す各々有効度が付与された複数のワーカ計算機とを用いて並列計算処理を行うシステムにおける前記マスタ計算機で実行する並列計算プログラムであって：各々価値を有する複数のジョブを生成するステップと；生成された前記ジョブをジョブ記憶部内に格納するステップと；前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出するステップと；前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出するステップと；前記有効度演算値が前記有効度閾値に満たないジョブを空きの前記ワーカ計算機に実行させるステップと；前記ワーカ計算機から前記ジョブの実行結果を受け取り、前記受け取ったジョブを前記ジョブ記憶部から削除するステップと；を備えたことを特徴とする。
【００１５】
本発明の一態様としての並列計算プログラムは、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行うシステムにおける前記マスタ計算機で実行する並列計算プログラムであって：複数のジョブを生成するステップと；生成した前記ジョブを前記ワーカ計算機に実行させる実行ステップと；前記ワーカ計算機から前記ジョブの実行結果を回収する回収ステップと；所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する判定ステップと；を備えたことを特徴とする。
【００１６】
本発明の一態様としての並列計算プログラムは、ジョブを生成するマスタ計算機と、前記ジョブを実行して実行結果を前記マスタ計算機に返す複数のワーカ計算機とを用いて並列計算処理を行うシステムにおける前記マスタ計算機で実行する並列計算プログラムであって：価値を有する複数のジョブを生成する生成ステップと；前記ジョブの価値に基づいて各前記ジョブの多重度を算出する算出ステップと；算出された多重度に従って前記ジョブを前記ワーカ計算機に実行させる実行ステップと；前記ワーカ計算機からジョブの実行結果を回収する回収ステップと；所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する判定ステップと；を備えたことを特徴とする。
【００１７】
本発明の一態様としての計算機は、複数のワーカ計算機にジョブを実行させて、前記ワーカ計算機から前記ジョブの実行結果を受け取る計算機であって：価値を有するジョブを生成するジョブ生成部と；生成された前記ジョブを格納するジョブ記憶部と；前記ジョブ記憶部に格納された前記ジョブの価値の大きさの順位に応じた有効度閾値を前記ジョブに対して算出する有効度閾値算出部と；各前記ワーカ計算機に付与された有効度を格納した有効度記憶部と；前記ジョブ記憶部内の前記ジョブについて、前記ジョブを実行しているワーカ計算機の有効度を用いた演算によって有効度演算値を算出する有効度演算値算出部と；前記有効度演算値が前記有効度閾値に満たないジョブを空いている前記ワーカ計算機に実行させ、前記ワーカ計算機から前記ジョブの実行結果を受け取った場合は、前記受け取ったジョブを前記ジョブ記憶部から削除するジョブ管理部と；備えたことを特徴とする。
【００１８】
本発明の一態様としての計算機は、複数のワーカ計算機にジョブを実行させて、前記ワーカ計算機から前記ジョブの実行結果を受け取る計算機であって：複数のジョブを生成するジョブ生成部と；生成した前記ジョブを前記ワーカ計算機に実行させ、前記ワーカ計算機からジョブの実行結果を回収するジョブ回収部と；所定のジョブ結果回収終了条件に基づき、前記ジョブ結果の回収を終了するか否かを判定する判定部と；を備えたことを特徴とする。
【００１９】
本発明の一態様としての計算機は、複数のワーカ計算機にジョブを実行させて、前記ワーカ計算機から前記ジョブの実行結果を受け取る計算機であって：各々価値を有する複数のジョブを生成するジョブ生成部と；前記ジョブの価値に基づいて各前記ジョブの多重度を算出するジョブ多重化部と；算出された多重度に従って前記ジョブを前記ワーカ計算機に実行させ、前記ワーカ計算機からジョブの実行結果を回収するジョブ回収部と；所定のジョブ結果回収終了条件に基づき、前記ジョブの実行結果の回収を終了するか否かを判定する判定部と；を備えたことを特徴とする。
【発明の効果】
【００２０】
本発明によれば、並列処理の実行時に一部の計算機が高負荷により処理が滞ってしまったり停止したりした場合でも、全体の並列計算の速度が著しく低下する状況を可及的に防ぐことができる。
【発明を実施するための最良の形態】
【００２１】
（第１の実施の形態）
図１は、本発明の第１の実施の形態としての並列処理方法を実施するための計算機システムの基本的な構成を示した図である。
【００２２】
以下、本計算機システムの基本的な構成及び動作を説明し、その後、本計算機システムの具体的な適用例を説明する。
【００２３】
図１に示すように、本計算機システムは、ジョブの生成及び管理等を行うマスタ計算機１１と、マスタ計算機１１から与えられたジョブを実行して実行結果（ジョブ結果）を返すワーカＡ〜Ｅとを備える。
【００２４】
マスタ計算機１１内のジョブプール（ジョブ記憶部）１４は、マスタ計算機１１によって生成されたジョブを格納する。各ジョブは番号で区別され、それぞれが価値を持つ。本例では、ジョブプール１４内にジョブ１〜ジョブ５が格納され、ジョブ１は価値４、ジョブ２は価値７、ジョブ３は価値８、ジョブ４は価値３、ジョブ５は価値５を有する。
【００２５】
有効度集計値保持手段１７は、ジョブ番号を保持する手段と、有効度集計値（有効度演算値）を保持する手段とを有する。
【００２６】
ジョブ番号を保持する手段にはジョブプール１４内のジョブの番号が入る。ジョブ番号は、ジョブの価値の大きい順に左から並ぶ。
【００２７】
有効度集計値を保持する手段には、該当するジョブを実行しているワーカの有効度を用いた演算結果が入る。演算は加算でもよいし、ワーカの有効度やジョブの実行時間を用いた関数による計算でもよい。ここではワーカの有効度を加算したものを有効度集計値とする。
【００２８】
例えば、ジョブ３の有効度集計値が３となっているのは、ジョブ３を実行中のワーカＡ、Ｂの有効度がそれぞれ２と１だからである。また、ジョブ２の有効度集計値が２となっているのは、ジョブ２を実行中のワーカＣ、Ｄの有効度が両方とも１だからである。
【００２９】
有効度閾値保持手段１２は、有効度閾値を保持する。有効度閾値は、有効度集計値保持手段１７中の左から見て同じ位置にあるジョブ（同じインデックスを持つジョブ）に対して与えることのできる有効度集計値の上限を示す。
【００３０】
例えば、ジョブ３に与えることのできる有効度集計値の上限は、最大で３であり、ジョブ２では２となっている。
【００３１】
有効度閾値は有効度閾値算出手段１５によって算出される。有効度閾値算出手段１５は、例えば、ジョブの価値の順位と有効度閾値とを対応づけたテーブルを保持し、ジョブプール１４内の各ジョブについて、その価値の順位に応じた有効度閾値を上記テーブルに基づいて決定する。この他、ジョブプール１４内のジョブ数、空きのワーカ数、ジョブの価値等を用いて、有効度閾値を算出しても良い。有効度閾値算出手段１５は、ジョブプール１４内にジョブが生成される度に、有効度閾値を再計算する。
【００３２】
マスタ計算機１１内のワーカ有効度保持手段１０は個々のワーカに付加された有効度を格納する。有効度は、例えば計算能力であったり、信頼度であったりする。
【００３３】
ジョブ管理手段１６は、ジョブプール１４内のジョブのうち、有効度集計値が有効度閾値に満たないジョブをワーカへ通信手段１３を介して投入する。また、ジョブ管理手段１６は、ワーカから返された結果を受け取り、受け取った結果に基づきジョブプール１４内のジョブを管理（例えば削除や生成）し、また、有効度集計値保持手段１７内のジョブ番号及び有効度集計値を管理（例えば変更等）する。
【００３４】
制御手段１９は、後述のマスタプログラムを実行してマスタ計算機１１全体を制御する。
【００３５】
マスタ計算機１１内の上記各手段によって実現される機能は、ハードウェア構成によって実現されても、プログラム（例えばマスタプログラム）の実行によって実現されてもよい。
【００３６】
ワーカは、マスタ計算機１１から渡されたジョブを実行し、ジョブ結果をマスタ計算機１１に返す。
【００３７】
以上のマスタ計算機１１はマスタプログラムに従って動作し、ワーカはワーカプログラムに従って動作する。
【００３８】
以下、マスタプログラム及びワーカプログラムについてそれぞれ詳しく説明する。
【００３９】
まず、マスタプログラムについて説明する。
【００４０】
図２は、マスタ計算機１１の制御手段１９によって実行されるマスタプログラムのステップを示すフローチャートである。
【００４１】
図２に示すように、マスタプログラムは、ジョブ送信スレッドとジョブ受信スレッドとを含む。制御手段１９は、ジョブ送信スレッドとジョブ受信スレッドとをそれぞれ起動する(ステップＳ１１、Ｓ１２)。ジョブ送信スレッド及びジョブ受信スレッドの終了をもってマスタプログラムは終了する。
【００４２】
以下、ジョブ送信スレッド及びジョブ受信スレッドについてそれぞれ説明する。
【００４３】
まず、ジョブ送信スレッドについて説明する。
【００４４】
図３は、ジョブ送信スレッドのステップを示すフローチャートである。
【００４５】
まず、制御手段１９が、初期ジョブ（例えば複数のジョブ）をジョブプール１４内に作成し、有効度閾値算出手段１５が有効度閾値の初期値を算出する。ジョブ管理手段１６は、有効度集計値保持手段１７内にジョブ番号及び有効度集計値を格納する（ステップＳ２１）。
【００４６】
次に、制御手段１９は、目的の結果を得たかどうかを判定する（ステップＳ２２）。制御手段１９は目的の結果を得た場合は（ステップＳ２２のＹＥＳ）、ジョブ送信スレッドの実行を終了する。
【００４７】
制御手段１９は、目的の結果をまだ得ていない場合は（ステップＳ２２のＮＯ）、次に、空きのワーカが存在するかどうかを判定する（ステップＳ２３）。
【００４８】
制御手段１９は、空きのワーカが存在しない場合は（ステップＳ２３のＮＯ）、ステップＳ２２に戻る。
【００４９】
一方、空きのワーカが存在する場合は（ステップＳ２３のＹＥＳ）、次に、有効度閾値算出手段１５が、ジョブプール１４内の各ジョブについて有効度閾値を再計算する（ステップＳ２４）。
【００５０】
ジョブ管理手段１６は、有効度集計値が有効度閾値に満たないジョブを空きワーカに投入する（ステップＳ２５）。この際、ジョブ管理手段１６は有効度集計値保持手段１７内の有効度集計値を更新する（ステップＳ２５）。
【００５１】
この後、制御手段１９は、ステップＳ２２に戻って、目的の結果を得たかどうかを判定する。
【００５２】
次に、ジョブ受信スレッドについて説明する。
【００５３】
図４は、ジョブ受信スレッドのステップを示すフローチャートである。
【００５４】
まず、ジョブ管理手段１６は、ワーカからジョブ結果が返されたか否かを判定する（ステップＳ３１）。
【００５５】
ジョブ管理手段１６は、ワーカからジョブ結果が返されていない場合は（ステップＳ３１のＮＯ）、ジョブ結果が返されるまで待機する。
【００５６】
一方、ジョブ管理手段１６は、ワーカからジョブ結果が返された場合は（ステップＳ３１のＹＥＳ）、ジョブプール１４から該当するジョブを削除する（ステップＳ３２）。
【００５７】
次に、制御手段１９は、返されたジョブ結果を用いて所定の計算を行い（ステップＳ３３）、目的の結果を得たかどうかを判定する（ステップＳ３４）。
【００５８】
制御手段１９は、目的の結果を得た場合は（ステップＳ３４のＹＥＳ）、ジョブ受信スレッドの実行を終了する。
【００５９】
一方、制御手段１９は、目的の結果を得ていない場合は（ステップＳ３４のＮＯ）、ジョブ管理手段１６に対し、返されたジョブ結果を用いてジョブプール１４内に新たなジョブ（単数あるいは複数）を作成させる（ステップＳ３５）。
【００６０】
次に、有効度閾値算出手段１５は、ジョブプール１４内の各ジョブについて有効度閾値を再計算する（ステップＳ３６）。この後、制御手段１９はステップＳ３１に戻る。
【００６１】
次に、ワーカプログラムについて説明する。
【００６２】
図５は、ワーカによって実行されるワーカプログラムのステップを示すフローチャートである。
【００６３】
ワーカは、マスタ計算機１１から投入されたジョブを実行し（ステップＳ４１）、ジョブ結果をマスタ計算機１１に送信する（ステップＳ４２）。
【００６４】
ここで、本実施の形態に係る計算機システムを用いて分枝限定法による最適化問題の計算を行う例を説明する。
【００６５】
まず、分枝限定法について簡単に説明する。
【００６６】
分枝限定法は最適化問題を解く方法の一つである。分枝限定法は解の空間を木で表し、ルートから葉までのパスを１つの解とみなす（図６参照）。木を作成しながら、最適となるパス、すなわち最適解を発見する。
【００６７】
例えば、最適化問題の一つであるナップザック問題では、深さｄにある木の節点は、ｄ番目の荷物を入れるか否かの場合分けを示している。木全体では、各節点に荷物を入れるか入れないかの全ての場合が尽くされる。この全ての場合の中で、評価値が最も高くなる荷物の入れ方（ルートから葉へのパス）が、求めるナップザック問題の解となる。
【００６８】
解の探索は、ルートから葉方向へ木を生成しながら行う。節点を分岐させて新たな節点を作る操作を分枝操作と呼ぶ。
【００６９】
いま、評価値の最も高くなる解を求めているものとする。個々の節点においてその節点から下に木を広げていった場合に、到達の可能性がある最大の評価値を節点ごとに計算できる。この到達の可能性のある最大の評価値を上界値と呼ぶ。一方、個々の節点ごとに、少なくとも達成可能である評価値も計算可能であり、この値を下界値と呼ぶ。
【００７０】
ある節点の上界値が他の節点の下界値を下回った場合、このある節点を通過する探索では明らかに最適解に到達できない。従って、その場合には、このある節点からの分枝操作を中止する。この処理を限定操作と呼ぶ。分枝限定法では、この限定操作により無用な解の探索を打ち切ることで解の探索空間を限定する。
【００７１】
上界値及び下界値はこの限定操作に利用できることの他に、対象となる節点より下の木を探索する操作の有望性の指標としても利用できる。例えば、下界値が大きな節点は、大きな評価値を得られる可能性が高いため、有望性があると言える。
【００７２】
以下、各節点における分枝操作をジョブ、各節点の有望性をジョブの価値とみなして、本計算機システムにより分枝限定法の計算を行う例を説明する。
【００７３】
まず、分枝限定法による計算を行っている途中のある一時点における状態を、図６〜図１４を用いて説明し、その後、続きの動作を説明する。
【００７４】
図６は、分枝限定法により解の探索を行っている途中の木の状態を示す図である。
【００７５】
この木において、複数の節点ＮＤ１〜ＮＤ９が示され、このうち節点ＮＤ５〜ＮＤ９は、現時点での探索の最前線であり、各節点ＮＤ５〜ＮＤ９では各ワーカによる分枝操作が行われる。各節点では、探索の有望性の観点からの価値を計算できる。各節点の丸の中の数字が価値を表す。
【００７６】
図７は、現時点でのジョブプール１４内の状態を示す図である。
【００７７】
図７に示すように、図６の木において探索の最前線に存在する節点ＮＤ５〜ＮＤ９に対応するジョブ５〜９が格納されている。高い価値を有するジョブほど図中左側に配置される。
【００７８】
図８は、有効度閾値、各ジョブ５〜９のジョブ番号及び有効度集計値を示す図である。
【００７９】
図８に示すように、有効度閾値は価値が高いものから順に３、２、１、１、１が与えられ、最も高い価値を有するジョブ８は有効度集計値３、次に高い価値を有するジョブ９は有効度集計値２、残りのジョブ５〜７は有効度集計値が１となっている。
【００８０】
図９は、ワーカにジョブ５〜９を割り当てた状態を示す図である。
【００８１】
ワーカがＡ〜Ｈまで存在する。各ワーカ内の数字５〜９は、実行中のジョブの番号を示す。また、ワーカＡ〜Ｈには有効度と呼ばれる指標が付加されている。カッコ内の数字が有効度である。図１０は、マスタ計算機１１におけるワーカ有効度保持手段１０を示し、ワーカ有効度保持手段１０によって、ワーカ名と有効度との対応関係が示される。
【００８２】
図１１は、ワーカの空き状況を管理するワーカプール１８を示す図である。このワーカプール１８はマスタ計算機１１内に備えられる。
【００８３】
ワーカプール１８にはワーカＨが登録されている。これは、ワーカＨが空き状態であることを示す（図９参照）。
【００８４】
以上の状態において、続きの処理を以下に説明する。以下の説明においては、参考のため、図３及び図４で説明したフローチャートに示されるステップ番号を付する。
【００８５】
まず、ワーカＡがジョブ８の実行を終了し（図９参照）、ジョブ結果をマスタ計算機に返すと、制御手段１９がワーカプール１８（図１１参照）内にワーカＡを登録する（図示せず）（図４のステップＳ３１）。
【００８６】
ジョブ管理手段１６は、ワーカＡによって処理されたジョブ８をジョブプール１４（図７参照）から削除し、さらに有効度集計値保持手段１７（図８参照）内からジョブ８のデータを削除する（図４のステップＳ３２）。
【００８７】
また、ジョブ８を実行しているワーカＢの仕事を停止させワーカＢをワーカプール１８に登録する。
【００８８】
一方、制御手段１９は、ワーカＡからのジョブの結果を用いて所定の演算を行って、次の節点ＮＤ１０、ＮＤ１１（図６参照）における解の探索の有望性の観点からの価値（ジョブの価値）を計算する（図４のステップＳ３３）。この際、枝狩りが可能な節点があれば枝狩りを行う。
【００８９】
制御手段１９は、現時点ではまだ目的の結果を得ていないと判断し（図４のステップＳ３４のＮＯ）、ジョブ管理手段１６は、ジョブ８の結果を用いて生成される新たな節点ＮＤ１０、ＮＤ１１に対応したジョブ１０、１１をジョブプール１４内に登録する（図４のステップＳ３５）。この状態を図１２に示す。ジョブ１０、１１の価値が、ジョブ９、５、６、７よりも高いため、ジョブプール１４内の先頭側（図中左側）に配置される。
【００９０】
ジョブプール１４内に新たにジョブが生成されると、有効度閾値算出手段１５は、有効度閾値を算出し、ジョブ管理手段１６は、ジョブ番号と有効度集計値とを再設定する（図４のステップＳ３６）。この状態を図１３に示す。この時点では、新たに生成されたジョブ１０、１１の有効度集計値は０である。次に、制御手段１９は空きのワーカが存在するかどうかを判定し（図３のステップＳ２３）、現時点では、上述した内容から分かるように、Ａ、Ｂ、Ｈの３つが空きである（図３のステップＳ２３のＹＥＳ）。従って、ジョブ管理手段１６は、有効度閾値算出手段１５による有効度閾値の再計算の後（図３のステップＳ２４）、各ジョブ１０、１１を空きワーカに割り当てる（図３のステップＳ２５）。例えば、ジョブ管理手段１６は、有効度閾値が３であるジョブ１０を例えば２台のワーカＡ、Ｂに割り当て、有効度閾値２を有するジョブ１１を例えばＨに割り当てる。
【００９１】
以上の処理を続けることで木の探索が行われ、最終的な解（評価値）を得る（図３のステップＳ２２のＹＥＳ、図４のステップＳ３４のＹＥＳ）。
【００９２】
以上に説明した分枝限定法による計算に本実施の形態に係る計算機システムを用いたことによる効果について述べると以下の通りである。
【００９３】
即ち、有効な方向の分枝処理（高いジョブ価値を有する節点での分枝処理）は多重化して実行されるので、負荷の高いワーカ（例えば性能が他のものより低い）や、途中で故障するワーカに有効な方向の探索処理（ジョブ）が割り当てられてしまっても、有効な方向の停止や停滞を阻止できる。また、これにより有効な探索方向での下界値計算も停滞、停止しないので、枝狩り処理の遅れが生じない利点がある。
【００９４】
また、価値が他のものよりも低く多重化されていないジョブであっても、価値が高いジョブが終了するとジョブプール内での順位が上がるので、最終的に多重化され得る。即ち、価値の低いジョブであっても、処理の停止や停滞を阻止し得る。
【００９５】
以上のように、本実施の形態によれば、高い価値を有するジョブを優先的に実行するようにしたので並列計算そのものが著しく遅滞することなく終了することが可能となる。
【００９６】
（第２の実施の形態）
本実施の形態では、ワーカの有効度をワーカの信頼度とした例を説明する。
【００９７】
例えば、ワーカＡの信頼性は２で、ワーカＢからＨまでの信頼性は１であるとし、ワーカＡの信頼性は他のワーカに比べて２倍高いものとする。このような仮定のもとで第１の実施形態と同様な処理を進めるとすると、有効度閾値３を持つジョブを実行する場合、有効度２であるＡを使う場合は、ワーカＡと、有効度１である他のワーカ（例えばＢ）とを用いることになる。一方、有効度１だけのワーカでジョブを実行する場合は、例えば３台のワーカＢ、Ｃ、Ｄを用いることになる。すなわち信頼性の高いワーカを用いて実行する場合は２台で実行することになり、そうでない場合は３台で実行することになる。これによりワーカを効率よく使用できる。
【００９８】
（第３の実施の形態）
本実施の形態では、ワーカの有効度をワーカの処理能力（例えば計算速度）にとした例を説明する。例えば、ワーカＡの計算速度は２で、ワーカＢからＨまでの計算速度は１であるとし、ワーカＡの計算速度は他のワーカに比べて２倍速いものとする。このような仮定のもとで第１の実施形態と同様な処理を進める。
【００９９】
ただし、有効度集計値を計算する際に、そのジョブを実行しているワーカの有効度の加算を行うのではなく、例えば、現在の有効度集計値を1.5倍した値に新しくジョブを実行するワーカの有効度を足した値を有効度集計値とする。なお、一般には、有効度集計値は、現在そのジョブを実行しているワーカの有効度とジョブの実行経過時間とを用いた関数に基づいて計算される値とすればよい。
【０１００】
例えば、有効度閾値３を持つジョブを実行する場合、まず有効度２であるワーカＡを使用し、続いて有効度１である他のワーカ(例えばＢ)を使用すると、その時点での有効度集計値は、2×1.5+1=4（>3）となり、２台のワーカで実行されることになる。なお、ジョブを割り当てる時点で有効度集計値が有効度閾値を越えていなければ、ジョブの割り当て後に有効度集計値が有効度閾値を越えても良い。
【０１０１】
一方、有効度１だけのワーカで順次実行する場合は、例えばワーカＢ、Ｃ、Ｄの順で実行される。ワーカＢで実行する際の有効度集計値は1で、続いてワーカＣで実行する際の有効度集計値は1×1.5+1 = 2.5で、続いてワーカＤで実行するときの有効度集計値は2.5×1.5+1=4.75（>3）となる。
【０１０２】
したがって、速いワーカを使う場合は少ないワーカで、遅いワーカを使う場合は多くのワーカで処理を実行することになり、速いワーカを使う場合は使用するワーカ数を削減することができる。
【０１０３】
（第４の実施の形態）
本実施の形態では、ワーカはいずれかのグループに属しているものとする。ワーカのグループを保持するグループ番号保持手段をマスタ計算機に導入する。
【０１０４】
図１４はグループ番号保持手段２６を示す。図１４において、ワーカＡからＤはグループ１に、ＥからＨはグループ２に属しているものとする。ワーカの故障は同じグループで発生しやすいものとする。
【０１０５】
ここでジョブをワーカに割り当てる際に、有効度が同じワーカの場合、現在そのジョブを実行しているワーカと違うグループのワーカを割り当てるようにする。
【０１０６】
例えば、あるジョブの有効度閾値が２で、有効度１且つグループ１のワーカが既に割り当てられている場合において、さらにもう１つワーカを割り当てる場合は、有効度１且つグループ２のワーカを割り当てる。
【０１０７】
同じグループに属しているワーカに故障が連鎖して発生しやすい場合などは、このように別のグループにジョブを割り当てることで、ジョブが正常終了する可能性を高めることができる。
【０１０８】
（第５の実施の形態）
本実施の形態では、ジョブの価値を用いて有効度閾値を計算する例を具体的に説明する。
【０１０９】
例えば、ジョブプール内に５つのジョブがあり、それぞれ価値が300, 200, 100, 100, 100である場合、有効度閾値を前から3, 2, 1, 1, 1とする。
【０１１０】
例えば８台のワーカが存在した場合、ジョブの価値をジョブの価値の総和(300+200+100+100+100=800)で割った値にワーカ台数（8）を掛けることで、上記値が求められる。
【０１１１】
この方法で有効度閾値を計算することで、価値の高いジョブほど有効度集計値を高くできるため、価値の高いジョブの計算の信頼性を高めたり（例えば信頼性の高いワーカほど有効度が高い場合）、価値の高いジョブの計算速度を速めたり（例えば速度の速いワーカほど有効度が高い場合）できる。
【０１１２】
（第６の実施の形態）
図１５は、本発明の第６の実施の形態としての並列計算方法を実施するための計算機システムの基本的な構成を示した図である。
【０１１３】
以下、本計算機システムの基本的な構成及び動作を説明し、その後、本計算機システムの具体的な適用例を説明する。
【０１１４】
マスタ計算機１１内のジョブプール１４は、マスタ計算機１１によって生成されたジョブを格納する。ジョブはワーカで実行され、ジョブ結果がマスタ計算機１１に返される。ジョブ結果回収終了判定手段２０は、１つ以上のワーカから返されたジョブ結果を用いて、ジョブ結果の回収を終了するか否かの判定をする。
【０１１５】
制御手段１９はマスタプログラムを実行してマスタ計算機１１全体を制御する。ワーカＡ〜Ｅは、第１の実施の形態と同じワーカプログラムに従って動作する。
【０１１６】
図１６は、マスタ計算機１１における制御手段１９によって実行されるマスタプログラムのステップを示すフローチャートである。
【０１１７】
まず、制御手段１９は、１つ以上のジョブを生成し、ワーカに実行させる（ステップＳ５１）。
【０１１８】
制御手段１９は、ワーカの返すジョブ結果を逐一受け取り、ジョブ結果回収終了判定手段２０は、例えばジョブ結果の回収数に基づいて、ジョブ結果の回収を終了するか否かの判定を行う（ステップＳ５２）。
【０１１９】
ジョブ結果回収終了判定手段２０がジョブ結果の回収を終了しないと判定した場合は（ステップＳ５２のＮＯ）、制御手段１９は再びワーカからのジョブ結果を待つ。
【０１２０】
一方、ジョブ結果回収終了判定手段２０がジョブ結果の回収を終了すると判定した場合は（ステップＳ５２のＹＥＳ）、制御手段１９は受け取ったジョブ結果に基づき所定の計算を行う（ステップＳ５３）。
【０１２１】
制御手段１９は、所定の計算の結果、目的の結果を得たかどうかを判断し（ステップＳ５４）、目的の結果を得た場合は（ステップＳ５４のＹＥＳ）本処理を終了し、得ていない場合は（ステップＳ５４のＮＯ）ステップＳ５１に戻り、新たなジョブを生成する。
【０１２２】
以下、本実施の形態に係る計算機システムを用いてニューラルネットワークの重み計算を行う例を説明する。
【０１２３】
まず、ニューラルネットワークについて簡単に説明する。
【０１２４】
ニューラルネットワークは、入力データに対する出力を予測するモデルである。
【０１２５】
図１７は、３層構造のニューラルネットワークの例を示す図である。
【０１２６】
入力と出力との間に図中横方向に沿って素子が３列並んでおり、隣り合う列の素子間にはリンクが張られている。各リンクに適当な重みを設定することで予測モデルを構築する。ここでは、３次元の入力(x1, x2, x3)から出力(y)を予測するモデルを学習する場合を考える。但し、j番目のリンクの重みをwjとし、全体の重みをW（図示せず）とする。学習に用いる６組の学習データＤ１〜Ｄ６の例を図１８に示す。i組目のデータはDiで表される。
【０１２７】
ニューラルネットワークの重み計算では、全体の重みＷの初期値（例えば時刻０における重み）W0を決め、モデルの性能が良くなるように順次この重みを更新し、収束判定することで最終的な重みを求める。時刻ｔにおける全体の重みWtから、次の時刻ｔ＋１における全体の重みWt+1を求める方法は、
Wt+1 = Wt + ΔWt  ・・・（式１）
但し、ΔWt =定数×（Δｗt１＋Δｗt２＋Δｗt３＋Δｗt４＋Δｗt５＋Δｗt６）
である。ここで、Δwti（ｉ＝１〜６）はDi（ｉ＝１〜６）（図１８参照）から計算される差分の一要素である。
【０１２８】
図１９は、本計算機システムにより重み計算を行っている状態を示す図である。
【０１２９】
ニューラルネットワークの重み計算をマスタ・ワーカ型で行う場合は、上述のΔwtiの計算をジョブiとしてワーカで処理する。即ち、Δｗt１をジョブ１として、Δｗt２をジョブ２として、・・・Δｗt６をジョブ６として処理する。
【０１３０】
通常の重み計算では、全てのジョブ１〜６を回収してΔWtを計算し、この後、重みの更新ステップを（式１）に従って一つ進める。
【０１３１】
しかし、本実施の形態では、一部のジョブの回収が終了した時点で重みの更新ステップを進める。
【０１３２】
例えば、図１９に示すように、６台のワーカＡ〜Ｆのうち、「先着４台のジョブ結果を回収」という条件が、ジョブ結果回収終了判定手段２０に与えられているとする。この場合、ジョブ２〜５の結果が、ジョブ１、６のよりも先に戻ってきたとすると、ジョブ結果回収終了判定手段２０は、この時点でジョブ結果の回収の終了を判定し、制御手段１９は重み計算の更新ステップを一つ進める。
【０１３３】
より詳しくは、まず、重みの差分ΔWｔを、
ΔWt =定数×（Δｗt２＋Δｗt３＋Δｗt４＋Δｗt５）
として計算し、次いで、（式１）に従って、重みを更新する。
【０１３４】
この後は、再び６つのジョブを生成し、各ジョブをワーカで実行させ、先着４台のジョブ結果を回収する。
【０１３５】
上述の例では、ジョブ結果回収終了判定の条件として先着ｎ個のジョブ結果を回収することを採用したが、その他の条件をこれに追加することもできる。例えば、先着４個ジョブを受け取った後、所定の時間（例えば２秒間）は、他のジョブの終了を待ち、その間に回収できたジョブ結果は計算に加えるなどとすることもできる。
【０１３６】
以上のように、本実施の形態によれば、ジョブ結果の回収を終了するか否かをジョブ結果回収終了条件に基づいて判定するジョブ結果回収終了判定手段を設けたことにより、全てのジョブ結果を回収せずとも、一部のジョブ結果だけを用いて計算を進めることができる。このため、一部のワーカが高負荷で結果の返答が遅れたり、ワーカがダウンしたりした場合でも、全体の処理が遅れたり、全体の処理が停止したりすることはない。このように一部のジョブ結果のみを用いて処理を進めると全てのジョブ結果を用いた場合と比べて計算精度は落ちるが、即ち、耐故障性及び耐高負荷性と計算精度とはトレードオフの関係になるが、計算精度に厳密性が要求されない場合や、収束計算の初期ループ等では，本手法は有効なものとなるといえる。
【０１３７】
（第７の実施の形態）
図２０は、本発明の第７の実施の形態としての並列計算方法を実施するための計算機システムの基本的な構成を示した図である。
【０１３８】
以下、本計算機システムの基本的な構成及び動作を説明し、その後、本計算機システムの具体的な適用例を説明する。
【０１３９】
マスタ計算機１１内のジョブプールは、マスタ計算機１１によって生成された１つ以上のジョブを格納する。各ジョブはそれぞれ所定の価値を有する。
【０１４０】
ジョブ多重化手段２４は、ジョブの価値に応じて各ジョブの多重度を決定する。各ジョブは、決定された多重度によって実行される。即ち、多重度がｎのジョブは、ｎ台のワーカで実行される。ワーカによるジョブ結果はマスタ計算機１１に返される。
【０１４１】
ジョブ結果回収終了判定手段２０は、ワーカからのジョブ結果に基づき、ジョブ結果の回収を終了するか否かの判定を行う。
【０１４２】
制御手段１９はマスタプログラムを実行してマスタ計算機１１全体を制御する。ワーカＡ〜Ｅは、第１の実施の形態と同じワーカプログラムに従って動作する。
【０１４３】
図２１は、マスタ計算機１１における制御手段１９によって実行されるマスタプログラムのステップを示すフローチャートである。
【０１４４】
まず、制御手段１９は、ジョブを生成し、個々のジョブの価値を計算する（ステップＳ７１）。
【０１４５】
次に、ジョブ多重化手段２４が、各ジョブについて、各ジョブの価値に応じた多重度を計算する（ステップＳ７２）。
【０１４６】
次に、制御手段１９は、決定された多重度によって各ジョブをワーカに実行させる（ステップＳ７３）。
【０１４７】
制御手段１９は、ワーカからのジョブ結果を逐一受け取り、ジョブ結果回収終了判定手段２０は、予め与えられた条件に基づいて、ジョブ結果の回収を終了するか否かの判定をする（ステップＳ７４）。
【０１４８】
ジョブ結果回収終了判定手段２０がジョブ結果の回収を終了しないと判定した場合は（ステップＳ７４のＮＯ）、制御手段１９は再びワーカからのジョブ結果を待つ。
【０１４９】
一方、ジョブ結果回収終了判定手段２０がジョブ結果の回収を終了すると判定した場合は（ステップＳ７４のＹＥＳ）、次に、制御手段１９は、ワーカからのジョブ結果を用いて所定の計算を行う（ステップＳ７５）。
【０１５０】
制御手段１９は、所定の演算の結果、目的の結果を得た場合は（ステップＳ７６のＹＥＳ）本処理を終了し、得ていない場合は（ステップＳ７６のＮＯ）、ステップＳ７１に戻り、再度、ジョブを生成する。
【０１５１】
以下、本実施の形態に係る計算機システムを用いて遺伝的アルゴリズムに従った計算を行う例を説明する。
【０１５２】
遺伝的アルゴリズムは最適化手法の一つである。この遺伝的アルゴリズムでは、まず、中間解と呼ばれる暫定解の集合を作り、その中の２つの暫定解から新たな解の候補を作るという作業を一回以上行う。次に、作られた解の候補を評価し、暫定解よりも良い解を新たな暫定解として残す。以上の作業を解の質が向上しなくなるまで行う。マスタ・ワーカ型の計算機システムで遺伝的アルゴリズムを処理する場合、例えば解の候補の評価にジョブを割り当てる。
【０１５３】
図２２は、本実施の形態に係る計算機システムにより遺伝的アルゴリズムに従って計算を行っている状態を示す図である。
【０１５４】
いま、６つの暫定解１〜６が得られ、各暫定解１〜６が、マスタ計算機１１内の記憶部２５に格納されている。各暫定解の評価値が円の中に示される。
【０１５５】
この状態において、次に解の候補を作成する。ここでは、暫定解１、４のペア、暫定解２、５のペア、及び暫定解３、６のペアからそれぞれ解の候補を作成したとする。
【０１５６】
作成された解の候補の評価がそれぞれジョブ１，２，３として、ジョブプール１４内に格納されている。各ジョブはそれぞれ価値を有する。
【０１５７】
一般に、遺伝的アルゴリズムでは、良い暫定解から作られた解の候補は良い評価値を持つことが多く、悪い暫定解から作られた解の候補は悪い評価値を持つことが多い。したがって、解の候補の質を評価する指標として親の解の評価値の平均を求め、この値をジョブの価値とみなす。
【０１５８】
ジョブ多重化手段２４は、ジョブプール１４内の各ジョブ１〜３をそれぞれの価値に応じて多重化する。ここでは、最も価値の高いジョブが２重化され、それ以外のジョブは多重化されないものとする。従って、本例では、最も高い価値「８」を有するジョブ１が２重化され、他のジョブ２、３は多重化されない。
【０１５９】
制御手段１９は、ジョブプール１４内の各ジョブ１〜３をワーカＡ〜Ｄに割り当てる。ジョブ１は２重化され、２台のワーカＡ、Ｂで処理される。
【０１６０】
ジョブ結果回収終了判定手段２０は、ジョブ結果の回収を終了するか否かの判定を行う。ここでは、先着３台のジョブ結果を回収するという条件がジョブ結果回収終了判定手段２０に与えられるとする。かかる条件の下、ワーカＡ、Ｂ、Ｄのジョブ結果がワーカＣよりも先に戻ってきたとする。即ち、ジョブ１の実行結果が２つと、ジョブ３の実行結果が１つ戻ってきたとする。制御手段１９は、ジョブ１の実行結果のうち１つを削除し、残りのジョブ１の実行結果とジョブ３の実行結果とを使って処理を進める。例えば、ジョブ１の実行結果として、新たな解の候補の評価値が、暫定解１あるいは４よりも大きければ新たな解の候補を暫定解として残し、これより低い評価値を有する暫定解１あるいは４あるいはこれらの両方を削除する。ジョブ３の実行結果についても同様にして処理する。
【０１６１】
以上の処理を解の質が向上しなくなるまで続ける。
【０１６２】
以上のように一部のジョブの実行結果だけを用いて計算を進めることで、一部のワーカが高負荷で結果の返答が遅れた場合でも全体の処理を遅らせることなく処理を進めることができ、また、一部のワーカが故障した場合でも全体の処理が停止することはない。また、良い解である可能性の高い解の候補は多重化されて実行されるので、得られた解を次のステップに残す可能性を高くできる。
【０１６３】
以上のように、本実施の形態によれば、価値の高いジョブを多重化して実行するようにしたので、一部のジョブ結果を用いて処理を進める場合においても、有効な結果を得る可能性を高くできる。
【０１６４】
ここで、本実施の形態は、第１の実施の形態と組み合わせることもできる。
【０１６５】
図２３は、図２２の計算システムに対し、図１のワーカ有効度保持手段１０、有効度閾値保持手段１２及び有効度集計値保持手段１７を追加した構成を示す図である。ジョブ多重化手段２４は、有効度集計値が有効度閾値に満たないジョブをワーカに実行させる。
【０１６６】
ワーカＡ〜Ｅは、それぞれ性能(例えば信頼性)が異なっており、Ａの信頼性が他に比べて2倍高いとする。これに対応して、ワーカ有効度保持手段１０には、ワーカＡ〜Ｅに対して、有効度２、１、１、１、１が格納されている。
【０１６７】
ジョブプール１４にはジョブ１〜３が格納され、ジョブ１、２、３の順に、価値が高い。従って、有効度集計値保持手段１７内にジョブが図中左から１、２、３の順に格納される。各ジョブ１〜３の有効度閾値は、それぞれ３、２、１である。各ジョブ１〜３は、対応する有効度閾値に基づいてワーカに割り当てられて実行される。
【０１６８】
例えば、ワーカＡの有効度は２なので、ジョブ１はワーカＡ、Ｂの２台、ジョブ２はワーカＣ、Ｄの２台、ジョブ３はワーカＥの１台で実行される。
【０１６９】
ジョブ回収終了判定手段２０は、所定の回収条件を満たしたら（例えばジョブ結果の回収数が規定数に達したら）、ジョブ結果の回収を終了することを判定する。
【０１７０】
図２３の計算機システムは、図２２の計算機システムと比べてワーカをより有効に利用できる利点がある。即ち、本例では、ジョブ１は、有効度が２のＡと有効度が１のＢで実行する選択肢と、有効度が１のＢ、Ｃ、Ｄで実行する選択肢と生じる。これに対し、ワーカの有効度を利用する方法がない図２２の構成であると、例えばジョブ１を２台のＡとＢで実行すれば十分な状況でも、全てのワーカの信頼度が同じだと仮定してＡ、Ｂ、Ｃの３台で実行なければならなくなる。
【図面の簡単な説明】
【０１７１】
【図１】本発明の第１の実施の形態としての並列処理方法を実施するための計算機システムの基本的な構成を示した図である。
【図２】マスタ計算機によって実行されるマスタプログラムによるステップを示すフローチャートである。
【図３】ジョブ送信スレッドによるステップを示すフローチャートである。
【図４】ジョブ受信スレッドによるステップを示すフローチャートである。
【図５】ワーカプログラムによるステップを示すフローチャートである。
【図６】分枝限定法に従った計算を行っている最中における木の状態を示す図である。
【図７】ジョブプールを示す図である。
【図８】有効度集計値保持手段を示す図である。
【図９】ワーカに対するジョブの割り当ての様子を示す図である。
【図１０】有効度保持手段を示す図である。
【図１１】ワーカプールを示す図である。
【図１２】ジョブプールを示す図である。
【図１３】有効度集計値保持手段を示す図である。
【図１４】グループ番号保持手段を示す図である。
【図１５】本発明の第６の実施の形態としての並列計算方法を実施するための計算機システムの基本的な構成を示した図である。
【図１６】マスタ計算機によって実行されるマスタプログラムのステップを示すフローチャートである。
【図１７】３層ニューラルネットワークの構成図である。
【図１８】３層ニューラルネットワークに与える学習データ例を示す図である。
【図１９】図１５の計算機システムがニューラルネットワークの重み計算を行う状態を示す図である。
【図２０】本発明の第７の実施の形態としての並列計算方法を実施するための計算機システムの基本的な構成を示した図である。
【図２１】マスタ計算機によって実行されるマスタプログラムのステップを示すフローチャートである。
【図２２】図２０の計算機システムが遺伝的アルゴリズムに従った計算を行う状態を示す図である。
【図２３】図２２の計算システムと図１の計算機システムとを組み合わせた構成例を示す。
【符号の説明】
【０１７２】
１０  ワーカ有効度保持手段
１１  マスタ計算機
１２  有効度閾値保持手段
１３  通信手段
１４  ジョブプール
１５  有効度閾値算出手段
１６  ジョブ管理手段
１７  有効度集計値保持手段
１８  ワーカプール
１９  制御手段
２０  ジョブ結果回収終了判定手段
２４  ジョブ多重化手段
２６  グループ番号保持手段
【図１】
2005242986.tif 000003
【図２】
2005242986.tif 000004
【図３】
2005242986.tif 000005
【図４】
2005242986.tif 000006
【図５】
2005242986.tif 000007
【図６】
2005242986.tif 000008
【図７】
2005242986.tif 000009
【図８】
2005242986.tif 000010
【図９】
2005242986.tif 000011
【図１０】
2005242986.tif 000012
【図１１】
2005242986.tif 000013
【図１２】
2005242986.tif 000014
【図１３】
2005242986.tif 000015
【図１４】
2005242986.tif 000016
【図１５】
2005242986.tif 000017
【図１６】
2005242986.tif 000018
【図１７】
2005242986.tif 000019
【図１８】
2005242986.tif 000020
【図１９】
2005242986.tif 000021
【図２０】
2005242986.tif 000022
【図２１】
2005242986.tif 000023
【図２２】
2005242986.tif 000024
【図２３】
2005242986.tif 000025