(57)【特許請求の範囲】
【請求項１】
所定の周期で繰り返し入力データを入力し、直列関係にある複数のプロセスからなるパイプライン処理により上記入力データを処理し、最前段のプロセスは上記入力データを処理して処理結果を出力し、後段のプロセスは前段のプロセスが出力した処理結果を処理して処理結果を出力し、上記入力データを入力した時刻から所定の制限時間が経過するまでの間に最後段のプロセスが処理結果を出力することを要求される計算機システムにおいて、
上記計算機システムは、複数の計算機と、プロセス処理時間算出部と、パイプライン処理時間算出部と、パイプライン処理時間予測部と、制限時間超過判定部と、分割プロセス選択部と、空き処理装置選択部と、スレッド起動部と、他計算機処理装置選択部と、他計算機スレッド起動部とを有し、
上記複数の計算機の各計算機は、１以上の処理装置を有し、
上記複数の計算機のうち少なくともいずれかの計算機の少なくともいずれかの処理装置は、上記パイプライン処理の複数のプロセスのうちいずれかのプロセスの処理の少なくとも一部の処理をスレッドとして実行し、
上記プロセス処理時間算出部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、各周期の入力データについて、上記パイプライン処理の各プロセスの処理にかかった時間を算出し、
上記パイプライン処理時間算出部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、各周期の入力データについて、上記パイプライン処理にかかった時間を算出し、
上記パイプライン処理時間予測部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記パイプライン処理時間算出部が算出した時間に基づいて、将来の周期において上記パイプライン処理にかかる時間を予測し、
上記制限時間超過判定部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記パイプライン処理時間予測部が予測した時間に基づいて、将来の周期において上記制限時間を超過するか否かを判定し、
上記分割プロセス選択部は、将来の周期において上記制限時間を超過すると上記制限時間超過判定部が判定した場合に、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記プロセス処理時間算出部が算出した時間に基づいて、上記複数のプロセスのうちから、プロセスの処理にかかる時間が増加しているプロセスを選択し、
上記空き処理装置選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスについて、上記プロセスの処理の一部であるスレッドを実行している処理装置と同じ計算機の処理装置のなかに、上記プロセスのスレッドを実行していない処理装置があるか否かを判定し、上記プロセスのスレッドを実行していない処理装置があると判定した場合に、上記プロセスのスレッドを実行していないと判定した処理装置を選択し、
上記スレッド起動部は、上記空き処理装置選択部が処理装置を選択した場合に、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記空き処理装置選択部が選択した処理装置に、上記分割プロセス選択部が選択したプロセスのスレッドを新たに実行させ、
上記他計算機処理装置選択部は、上記空き処理装置選択部が処理装置を選択しなかった場合に、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスのスレッドを実行している処理装置と異なる計算機の処理装置のなかから、処理装置を選択し、
上記他計算機スレッド起動部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記他計算機処理装置選択部が選択した処理装置に、上記分割プロセス選択部が選択したプロセスのスレッドを新たに実行させ、
上記パイプライン処理の複数のプロセスのうち少なくともいずれかのプロセスは、直前の所定の入力回数の周期で入力した入力データまたは前段のプロセスが直前の所定の入力回数の周期で出力した処理結果を処理して処理結果を出力し、
上記複数の計算機の各計算機は、上記１以上の処理装置が共有する記憶装置を有し、
上記記憶装置は、上記記憶装置を共有する１以上の処理装置のいずれかが実行しているスレッドのプロセスについて、上記プロセスが処理する入力データまたは前段のプロセスが出力した処理結果を記憶し、
上記制限時間超過判定部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、現在の周期から所定の予測回数だけ先の周期において上記制限時間を超過するか否かを判定し、上記予測回数は、上記パイプライン処理の複数のプロセスの入力回数のうち最も大きい入力回数よりも大きく、
上記他計算機処理装置選択部が選択した処理装置に上記他計算機スレッド起動部が実行させたスレッドのプロセスについて、上記プロセスの後段のプロセスのスレッドを実行している処理装置は、上記プロセスの入力回数が経過するまで、上記他計算機処理装置選択部が選択した処理装置が実行したスレッドの処理結果を利用しないことを特徴とする計算機システム。
【請求項２】
上記他計算機処理装置選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスについて実行されているスレッドの数よりも多い数の処理装置を選択し、
上記計算機システムは、移動プロセス終了部を有し、
上記移動プロセス終了部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスについて、上記他計算機スレッド起動部が上記プロセスのスレッドを実行させた場合に、上記他計算機スレッド起動部が上記プロセスのスレッドを実行させてから上記プロセスの入力回数の周期が経過したのちに、上記他計算機スレッド起動部が上記プロセスのスレッドを実行させるよりも前から上記プロセスのスレッドを実行していた処理装置に、上記プロセスのスレッドの実行を終了させることを特徴とする請求項１に記載の計算機システム。
【請求項３】
上記空き処理装置選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスについて、上記プロセスの処理の一部であるスレッドを実行している処理装置と同じ計算機の処理装置のなかに、上記パイプライン処理の複数のプロセスのいずれのプロセスのスレッドも実行していない処理装置があるか否かを判定し、上記パイプライン処理の複数のプロセスのいずれのプロセスのスレッドも実行していない処理装置があると判定した場合に、上記パイプライン処理の複数のプロセスのいずれのプロセスのスレッドも実行していないと判定した処理装置を選択することを特徴とする請求項１または請求項２に記載の計算機システム。
【請求項４】
上記他計算機処理装置選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスのスレッドを実行している処理装置と異なる計算機の処理装置のなかから、上記パイプライン処理の複数のプロセスのいずれのプロセスのスレッドも実行していない処理装置を選択することを特徴とする請求項１乃至請求項３のいずれかに記載の計算機システム。
【請求項５】
上記他計算機処理装置選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスのスレッドを実行している処理装置と異なる計算機のなかから、上記分割プロセス選択部が選択したプロセスの前段のプロセスまたは後段のプロセスのスレッドを実行している処理装置を有する計算機を選択し、選択した計算機の処理装置のなかから処理装置を選択することを特徴とする請求項１乃至請求項４のいずれかに記載の計算機システム。
【請求項６】
上記計算機システムは、処理時間短縮判定部と、分割済プロセス選択部と、終了スレッド選択部と、スレッド終了部とを有し、
上記処理時間短縮判定部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記パイプライン処理時間予測部が予測した時間に基づいて、上記パイプライン処理にかかる時間が短縮しつつあるか否かを判定し、
上記分割済プロセス選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記パイプライン処理にかかる時間が短縮しつつあると上記処理時間短縮判定部が判定した場合に、上記パイプライン処理の複数のプロセスのなかから、複数のスレッドが実行されているプロセスを選択し、
上記終了スレッド選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割済プロセス選択部が選択したプロセスの複数のスレッドのなかから、終了するスレッドを選択し、
上記スレッド終了部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記終了スレッド選択部が選択したスレッドについて、上記スレッドを実行している処理装置に、上記スレッドの実行を終了させることを特徴とする請求項１乃至請求項５のいずれかに記載の計算機システム。
【請求項７】
上記分割済プロセス選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記プロセス処理時間算出部が算出した時間に基づいて、上記パイプライン処理の複数のプロセスのなかから、プロセスの処理にかかる時間が減少しているプロセスを選択することを特徴とする請求項６に記載の計算機システム。
【請求項８】
上記終了スレッド選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割済プロセス選択部が選択したプロセスの複数のスレッドのなかから、他のスレッドと異なる計算機の処理装置が実行しているスレッドを選択することを特徴とする請求項６または請求項７に記載の計算機システム。
【請求項９】
上記終了スレッド選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割済プロセス選択部が選択したプロセスについて、上記プロセスの複数のスレッドのなかから、同一の計算機の他の処理装置のなかに、上記プロセスの前段のプロセスまたは後段のプロセスのスレッドを実行している処理装置がない処理装置が実行しているスレッドを選択することを特徴とする請求項６乃至請求項８のいずれかに記載の計算機システム。
【請求項１０】
１以上の処理装置を有する複数の計算機からなる計算機システムの少なくともいずれかの計算機のいずれかの処理装置が実行することにより、上記計算機システムが請求項１乃至請求項９のいずれかに記載の計算機システムとして機能することを特徴とするコンピュータプログラム。
【請求項１１】
１以上の処理装置を有する複数の計算機からなる計算機システムが、所定の周期で繰り返し入力データを入力し、直列関係にある複数のプロセスからなるパイプライン処理により上記入力データを処理し、最前段のプロセスは上記入力データを処理して処理結果を出力し、後段のプロセスは前段のプロセスが出力した処理結果を処理して処理結果を出力し、上記入力データを入力した時刻から所定の制限時間が経過するまでの間に最後段のプロセスが処理結果を出力することを要求される処理を実行するパイプライン処理方法において、
上記複数の計算機の各計算機は、１以上の処理装置を有し、
上記複数の計算機のうち少なくともいずれかの計算機の少なくともいずれかの処理装置は、上記パイプライン処理の複数のプロセスのうちいずれかのプロセスの処理の少なくとも一部の処理をスレッドとして実行し、
プロセス処理時間算出部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、各周期の入力データについて、上記パイプライン処理の各プロセスの処理にかかった時間を算出し、
パイプライン処理時間算出部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、各周期の入力データについて、上記パイプライン処理にかかった時間を算出し、
パイプライン処理時間予測部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記パイプライン処理時間算出部が算出した時間に基づいて、将来の周期において上記パイプライン処理にかかる時間を予測し、
制限時間超過判定部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記パイプライン処理時間予測部が予測した時間に基づいて、将来の周期において上記制限時間を超過するか否かを判定し、
将来の周期において上記制限時間を超過すると上記制限時間超過判定部が判定した場合に、分割プロセス選択部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記プロセス処理時間算出部が算出した時間に基づいて、上記複数のプロセスのうちから、プロセスの処理にかかる時間が増加しているプロセスを選択し、
空き処理装置選択部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記分割プロセス選択部が選択したプロセスについて、上記プロセスの処理の一部であるスレッドを実行している処理装置と同じ計算機の処理装置のなかに、上記プロセスのスレッドを実行していない処理装置があるか否かを判定し、上記プロセスのスレッドを実行していない処理装置があると判定した場合に、上記プロセスのスレッドを実行していないと判定した処理装置を選択し、
スレッド起動部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記空き処理装置選択部が処理装置を選択した場合に、上記空き処理装置選択部が選択した処理装置に、上記分割プロセス選択部が選択したプロセスのスレッドを新たに実行させ、
他計算機処理装置選択部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記空き処理装置選択部が処理装置を選択しなかった場合に、上記分割プロセス選択部が選択したプロセスのスレッドを実行している処理装置と異なる計算機の複数の処理装置のなかから、処理装置を選択し、
他計算機スレッド起動部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、上記他計算機処理装置選択部が選択した処理装置に、上記分割プロセス選択部が選択したプロセスのスレッドを新たに実行させ、
上記パイプライン処理の複数のプロセスのうち少なくともいずれかのプロセスは、直前の所定の入力回数の周期で入力した入力データまたは前段のプロセスが直前の所定の入力回数の周期で出力した処理結果を処理して処理結果を出力し、
上記複数の計算機の各計算機は、上記１以上の処理装置が共有する記憶装置を有し、
上記記憶装置は、上記記憶装置を共有する１以上の処理装置のいずれかが実行しているスレッドのプロセスについて、上記プロセスが処理する入力データまたは前段のプロセスが出力した処理結果を記憶し、
上記制限時間超過判定部として、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置は、現在の周期から所定の予測回数だけ先の周期において上記制限時間を超過するか否かを判定し、上記予測回数は、上記パイプライン処理の複数のプロセスの入力回数のうち最も大きい入力回数よりも大きく、
上記他計算機処理装置選択部が選択した処理装置に上記他計算機スレッド起動部が実行させたスレッドのプロセスについて、上記プロセスの後段のプロセスのスレッドを実行している処理装置は、上記プロセスの入力回数が経過するまで、上記他計算機処理装置選択部が選択した処理装置が実行したスレッドの処理結果を利用しないことを特徴とするパイプライン処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、１以上の処理装置を有する複数の計算機からなる計算機システムに関する。また、そのような計算機システムを用いて、リアルタイム性が要求されるパイプライン処理をするパイプライン処理方法に関する。
【背景技術】
【０００２】
複数の処理装置を有する計算機システムにおいて、処理の負荷を分散させることにより、処理にかかる時間を短縮する技術がある。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００５−１５７９５５号公報
【特許文献２】特開２００８−１２３２０５号公報
【特許文献３】特開２００８−１６５３０１号公報
【特許文献４】特開２００８−１９１９４９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
計算機システムが複数の計算機を有し、各計算機が１以上の処理装置を有する場合、同じ計算機の処理装置の間の通信コストと、異なる計算機の処理装置の間の通信コストとは同じではない。このため、処理の負荷を均等に分散させるだけでは、効率が悪くなり、処理にかかる時間が短縮しない場合がある。
この発明は、例えば、上記のような課題を解決するためになされたものであり、効率よく処理の負荷を分散させることにより、パイプライン処理にかかる時間が制限時間を超過するのを未然に防ぐことを目的とする。
【課題を解決するための手段】
【０００５】
この発明にかかる計算機システムは、
所定の周期で繰り返し入力データを入力し、直列関係にある複数のプロセスからなるパイプライン処理により上記入力データを処理し、最前段のプロセスは上記入力データを処理して処理結果を出力し、後段のプロセスは前段のプロセスが出力した処理結果を処理して処理結果を出力し、上記入力データを入力した時刻から所定の制限時間が経過するまでの間に最後段のプロセスが処理結果を出力することを要求される計算機システムにおいて、
上記計算機システムは、複数の計算機と、スレッド開始時刻取得部と、スレッド終了時刻取得部と、プロセス開始時刻算出部と、プロセス終了時刻算出部と、プロセス処理時間算出部と、パイプライン処理時間算出部と、パイプライン処理時間予測部と、制限時間超過判定部と、分割プロセス選択部と、空き処理装置選択部と、スレッド起動部と、他計算機処理装置選択部と、他計算機スレッド起動部とを有し、
上記複数の計算機の各計算機は、１以上の処理装置を有し、
上記複数の計算機のうち少なくともいずれかの計算機の少なくともいずれかの処理装置は、上記パイプライン処理の複数のプロセスのうちいずれかのプロセスの処理の少なくとも一部の処理をスレッドとして実行し、
上記プロセス処理時間算出部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、各周期の入力データについて、上記パイプライン処理の各プロセスの処理にかかった時間を算出し、
上記パイプライン処理時間算出部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、各周期の入力データについて、上記パイプライン処理にかかった時間を算出し、
上記パイプライン処理時間予測部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記パイプライン処理時間算出部が算出した時間に基づいて、将来の周期において上記パイプライン処理にかかる時間を予測し、
上記制限時間超過判定部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記パイプライン処理時間予測部が予測した時間に基づいて、将来の周期において上記制限時間を超過するか否かを判定し、
上記分割プロセス選択部は、将来の周期において上記制限時間を超過すると上記制限時間超過判定部が判定した場合に、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記プロセス処理時間算出部が算出した時間に基づいて、上記複数のプロセスのうちから、プロセスの処理にかかる時間が増加しているプロセスを選択し、
上記空き処理装置選択部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスについて、上記プロセスの処理の一部であるスレッドを実行している処理装置と同じ計算機の処理装置のなかに、上記プロセスのスレッドを実行していない処理装置があるか否かを判定し、上記プロセスのスレッドを実行していない処理装置があると判定した場合に、上記プロセスのスレッドを実行していないと判定した処理装置を選択し、
上記スレッド起動部は、上記空き処理装置選択部が処理装置を選択した場合に、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記空き処理装置選択部が選択した処理装置に、上記分割プロセス選択部が選択したプロセスのスレッドを新たに実行させ、
上記他計算機処理装置選択部は、上記空き処理装置選択部が処理装置を選択しなかった場合に、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記分割プロセス選択部が選択したプロセスのスレッドを実行している処理装置と異なる計算機の処理装置のなかから、処理装置を選択し、
上記他計算機スレッド起動部は、上記複数の計算機のうちいずれかの計算機のいずれかの処理装置を用いて、上記他計算機処理装置選択部が選択した処理装置に、上記分割プロセス選択部が選択したプロセスのスレッドを新たに実行させることを特徴とする。
【発明の効果】
【０００６】
この発明にかかる計算機システムによれば、繰り返し処理の各周期におけるパイプライン処理時間の変化から、将来の周期のパイプライン処理時間を予測するので、制限時間の超過を早い段階で予測し、対策を取ることができる。また、プロセスを分割したスレッドを実行する処理装置を、同じ計算機の処理装置を優先させて選択するので、スレッド間通信の負荷を減らすことができ、プロセスを分割したことによるパイプライン処理時間の短縮効果を確実にすることができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１における計算機リソース制御方式が対象とする計算機システム１の構成図。
【図２】実施の形態１における計算機３が持つＣＰＵ４の例を示す図。
【図３】実施の形態１における計算機システム１で動作するプロセス群の処理形態を示す図。
【図４】実施の形態１におけるプロセス７の構成を示す図。
【図５】実施の形態１におけるプロセス７の動作の概要を示す図。
【図６】実施の形態１における計算機リソース制御方式の構成を示す図。
【図７】実施の形態１における計算機リソース制御方式の各構成要素の連係動作の一例を示す図。
【図８】実施の形態１における計算機リソース制御方式の各構成要素の連係動作の別の例を示す図。
【図９】実施の形態１におけるシステム負荷監視部１３の、パイプライン処理の処理時間変動時におけるスレッド８、スレッド８を動作させるＣＰＵ４、ＣＰＵコア５の決定の手順を示すフローチャート図。
【図１０】実施の形態１におけるステップＳ３のシステム負荷監視部１３の処理を示すフローチャート図。
【図１１】実施の形態１におけるプロセスの分割とＣＰＵ時間の削減量との関係を説明するための図。
【図１２】実施の形態１におけるステップＳ１０２３における、システム負荷監視部１３の他計算機３へのプロセス配置処理を示すフローチャート図。
【図１３】実施の形態１におけるステップＳ５における処理手順を示すフローチャート図。
【図１４】実施の形態２におけるシステム負荷監視部１３のステップＳ３の処理手順を示すフローチャート図。
【図１５】実施の形態２におけるステップＳ２０１７の動作を示すフローチャート図。
【図１６】実施の形態３におけるシステム負荷監視部１３のステップＳ３の処理手順を示すフローチャート図。
【図１７】実施の形態４におけるシステム負荷監視部１３のステップＳ４の処理の詳細を示すフローチャート図。
【図１８】実施の形態５における計算機システム８００の全体構成の一例を示すシステム構成図。
【図１９】実施の形態５における計算機８１０のハードウェア資源の一例を示すハードウェア構成図。
【図２０】実施の形態５におけるパイプライン処理８５０の一例を示す図。
【図２１】実施の形態５におけるパイプライン処理８５０のタイミングの一例を示すタイミング図。
【図２２】実施の形態５におけるプロセス８５１の処理のタイミングの一例を示すタイミング図。
【図２３】実施の形態５におけるプロセス８５１の処理８５２の構成の一例を示す図。
【図２４】実施の形態５におけるスレッド８５４の構成の一例を示す図。
【図２５】実施の形態５における計算機システム８００の機能ブロックの構成の一例を示すブロック構成図。
【図２６】実施の形態５におけるパイプライン管理処理Ｓ４００の流れの一例を示すフローチャート図。
【図２７】実施の形態５におけるプロセス分割工程Ｓ４０５の流れの一例を示すフローチャート図。
【図２８】実施の形態５におけるプロセス併合工程Ｓ４０９の流れの一例を示すフローチャート図。
【発明を実施するための形態】
【０００８】
計算機リソース制御方式について説明する。
プロセスを処理する計算機を複数台接続して複数のプロセスを連携処理するシステムにおいて、処理対象プロセスが要求するリソース量と、各計算機が持つ余剰リソース量を考慮し、計算機が、プロセスの処理量増加や、システム内計算機の故障などにより、プロセスが必要とするリソース量を提供できなくなった場合に、プロセスの必要とするリソース量を保持する他の計算機に、処理対象プロセスを移行させることにより、プロセスの制限時間超過の継続発生を防ぐ。
【０００９】
このような計算機リソース制御方式では、計算機に複数の異なる処理が動作している場合において、他の計算機に処理を移行すると他の処理の制限時間超過が発生する可能性がある。
また、プロセスを他の計算機に移動させる際、処理を継続させるために必要なデータを移動させる必要がある。例えば、過去Ｎ回のデータをもとにして次の処理結果を求める場合、プロセスを移動させ、移動させたプロセスが直ちに処理に参入すると、過去Ｎ回のデータを破棄することになり、計算結果が必ずしも正確ではない。
【００１０】
また、近年、ＣＰＵ内に複数のＣＰＵコアを持つマルチコアＣＰＵが計算機に搭載されている。マルチコアＣＰＵを持つ計算機に従来の計算機リソース制御方式を適用した場合、同一計算機内のＣＰＵコアに処理を再配置したほうが、過去Ｎ回のデータを計算機内に保持しているため、処理再配置に伴うオーバーヘッドは小さくなる。このため、同一計算機内の他ＣＰＵコアへの配置を優先的に行うことが望ましい。
また、制限時間超過の原因プロセスの処理を、そのプロセスと連携して処理を行う他の計算機のプロセスに配置したほうが計算機間通信の時間を短縮できる。
【００１１】
以下に説明する計算機システムおよびパイプライン処理方法は、マルチコアＣＰＵを搭載した計算機で構成された分散計算機システムにおいて、処理の制限時間超過発生の可能性がある場合に、原因となるプロセスを複数の処理に分割し、分割後の処理を行うスレッドを同一計算機の他ＣＰＵコアに優先的に配置することにより、処理の再配置時のオーバーヘッドを小さくする。また、他の計算機にプロセスを起動した場合に、ｎ周期分データを蓄積するだけの時間が経過してから新規起動したプロセスを処理に参入させる。
【００１２】
実施の形態１．
実施の形態１について、図１〜図１３を用いて説明する。
【００１３】
図１は、この実施の形態における計算機リソース制御方式が対象とする計算機システム１の構成図である。
本計算機システム１は、ネットワーク２、ネットワーク２に接続された複数の計算機３（３−１、３−２、・・・３−Ｎ）によって構成される。
【００１４】
図２は、この実施の形態における計算機３が持つＣＰＵ４の例を示す図である。
図のように、本計算機システム１の計算機３は、２つ以上のＣＰＵコア（５−１、５−２、・・・５−Ｎ）を持つＣＰＵ４（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）で構成される。各ＣＰＵ４では、ＳＭＰ（Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉ  Ｐｒｏｃｅｓｓｉｎｇ）用ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）６が動作しているものとする。ＳＭＰではＣＰＵコア５でメモリを共有しているため、異なるＣＰＵコア５で動作するプロセスおよびスレッド間でデータを共有することが可能である。
【００１５】
図３は、この実施の形態における計算機システム１で動作するプロセス群の処理形態を示す図である。
プロセス７は、図のように、パイプライン状に連なって、他のプロセス群と連携して処理を行う。以降、プロセス７がパイプライン状に連なって構成される処理を、パイプライン処理と呼ぶ。各パイプライン処理は、一定の周期で処理を行い、各パイプライン処理は周期内に終了する必要があるリアルタイム処理を行う。
また、プロセス７は、過去Ｎ周期の演算結果もとに計算を行うものとする。
【００１６】
図４は、この実施の形態におけるプロセス７の構成を示す図である。
図に示すように、プロセス７は１つ以上のスレッド８によって構成される。
【００１７】
図５は、この実施の形態におけるプロセス７の動作の概要を示す図である。
本計算機リソース制御方式が対象とするプロセス７は、Ｎ個のスレッドに処理を分割可能なように作成されており、プロセス７のメインスレッド（プロセス起動時に作成されるスレッド）がデータを受信し、プロセス７内に１つのスレッド８しか存在しない場合には、そのスレッド８がデータを処理してパイプライン処理の次の処理を行うプロセス７にデータを送信し、プロセス７内にスレッド８が複数個ある場合には、これらのスレッド８でデータを分割して処理し、各スレッド８がデータを次の処理を行うプロセス７に送信できるようになっているものとする。
【００１８】
なお、本システムにおける各パイプライン処理およびそれを構成するプロセス７には識別子が付与されており、識別子によってどのプロセス７がどのパイプライン処理に属するかがわかるようになっているものとする。
【００１９】
図６は、この実施の形態における計算機リソース制御方式の構成を示す図である。
本実施の形態における計算機リソース制御方式は、スレッド処理時間監視部９、計算機負荷監視部１０、パイプライン処理時間監視部１１、スレッド割付部１２、システム負荷監視部１３、スレッド制御部１４によって構成される。以下、各構成要素の役割の概要を説明する。
【００２０】
スレッド処理時間監視部９は、各ＣＰＵコア５に１つ存在し、各ＣＰＵコア５で動作するスレッド８の処理時間、ＣＰＵ時間をスレッド制御部１４から取得し、それぞれの履歴を保持し、各スレッド８の処理時間、各スレッド８のＣＰＵ時間の変動を求める役割を持つ。なお、本実施の形態において、処理時間とは、スレッド８がデータを受信してから、パイプライン処理における次の処理を行うスレッド８にデータを転送し終わるまでに要した時間を示し、ＣＰＵ時間とは、処理時間のうち実際にＣＰＵ４がそのスレッド８に対して演算処理を行った時間を示す。
【００２１】
また、スレッド処理時間監視部９は、パイプライン処理の先頭の処理を行うスレッド８の処理開始時刻、および、パイプライン処理の末尾のスレッド８の処理終了時刻を、パイプライン処理時間監視部１１に通知する役割を持つ。
【００２２】
計算機負荷監視部１０は、各計算機３に１つ存在し、システム負荷監視部１３からの指示にしたがい、プロセス７の処理時間、ＣＰＵ時間の状況をスレッド処理時間監視部９から取得して返す役割を持つ。また、計算機負荷監視部１０は、システム負荷監視部１３からの指示に従い、プロセス７の複数スレッド化による処理分散化、スレッド８の処理の集約の実現可／不可の応答を返し、システム負荷監視部１３からのスレッド８の起動／停止指示を適切なスレッド割付部１２に転送する役割を持つ。
【００２３】
パイプライン処理時間監視部１１は、システムに１つ存在し、スレッド処理時間監視部９から送られるパイプライン処理の開始時刻、終了時刻をもとに、パイプライン処理全体の処理時間を求め、パイプライン処理の処理時間の変動の傾向を調査し、今後、Ｔ１だけ先の時刻に制限時間オーバーの可能性がある場合、制限時間オーバー発生間近の場合、制限時間が短縮傾向にある場合に、システム負荷監視部１３に通知する役割を持つ。ここで、時間Ｔ１は、システム中のパイプライン処理のＮ周期の時間の最大値よりも長いものとする。例えば、システム中のパイプライン処理の処理周期の最大値がＣｘであった場合、時間Ｔ１の値は、Ｃｘ×Ｎよりも大きな値となる。
【００２４】
スレッド割付部１２は、計算機負荷監視部１０からの指示に基づき、スレッド８の起動／停止を行う役割を持つ。また、スレッド割付部１２は、スレッド８に、データの送信先の変更、送信するデータの変更、データ送信元の変更を指示する役割を持つ。
【００２５】
システム負荷監視部１３は、システムに１つ存在し、パイプライン処理がどのプロセス７から構成されているかを保持するとともに、パイプライン処理時間監視部１１からの、パイプライン処理の処理時間の変動の通知に基づき、処理時間の変動が発生したパイプライン処理のプロセス７が動作する計算機３に対し、プロセス７のＣＰＵ時間、処理時間に変動のあったプロセス７の検出の指示を行い、処理時間変動の原因となったプロセス７を検出し、プロセス７のスレッド８への分割や、スレッド数の削減などの処理を各計算機負荷監視部１０に指示する役割を持つ。ここで、プロセス７のＣＰＵ時間とは、プロセス７を構成するスレッド８のＣＰＵ時間の総和であり、プロセス７の処理時間とは、本実施の形態では、処理開始時刻は同一であるとし、スレッド８の処理時間（スレッドの処理終了時刻−スレッドの処理開始時刻）であるとする。
【００２６】
スレッド制御部１４は、スレッド８ごとに持つものであり、スレッド処理時間監視部９に、処理開始時刻、処理終了時刻、処理時間中におけるＣＰＵ時間を送信する役割を持つ。また、スレッド制御部１４は、スレッド割付部１２からの、どの計算機にデータを送信すればよいか、各計算機にどの領域のデータを送信するか、どの計算機からどの領域のデータを待つ必要があるか、などの指示を元に、送信すべき全計算機に適切なサイズのデータを送信し、受信すべき全ての送信元スレッドからのデータを受信する役割を持つ。
【００２７】
図７は、この実施の形態における計算機リソース制御方式の各構成要素の連係動作の一例を示す図である。
なお、図において、スレッド８−２−１〜８−２−３は、プロセス７−２の処理を３つのスレッドの処理量が均等になるよう分割したものである。
【００２８】
スレッド８−１−１、スレッド８−２−１〜８−２−３、プロセス８−３−１はそれぞれデータを受け取ると、スレッド処理時間監視部９に処理開始時刻を通知し（Ａ１）、処理を行い、パイプライン処理中における次の処理を行うスレッド８にデータを転送すると、スレッド処理時間監視部９に処理終了時刻のデータを送信する（Ａ２）。パイプライン処理の先頭の処理を行うスレッド（８−１−１）からの処理開始時刻を受信したスレッド処理時間監視部（９−１−１）は、処理開始時刻をパイプライン処理時間監視部１１に通知し（Ａ３）、パイプライン処理の末尾の処理を行うプロセスまたはスレッド（８−３−１）からの処理終了時刻を受信するスレッド処理時間監視部（９−３−１）は、処理完了時刻をパイプライン処理時間監視部１１に通知する（Ａ４）。
【００２９】
パイプライン処理時間監視部１１は、スレッド処理時間監視部９からパイプライン処理の処理開始時刻、処理終了時刻を受信すると、この２つの時刻から処理時間を求め、処理時間の履歴として保持しておく。そして、パイプライン処理時間監視部１１は、過去の履歴をもとに処理時間の変動を調査し、今後時間Ｔ１以内に制限時間オーバーの可能性が生じた場合、制限時間オーバー発生間近の場合、処理時間が短縮傾向にある場合のいずれかの場合、それらの内容の通知をシステム負荷監視部１３に送信する（Ａ６）。なお、パイプライン処理における先頭の処理、または末尾の処理が複数のスレッド８により行われている場合、パイプライン処理の先頭の処理を複数のスレッド８が行っている場合は、同一処理を行っている複数のスレッド８のうち最初に処理を開始したスレッド８の時刻がパイプライン処理の処理開始時刻として採用され、また、パイプライン処理の末尾の処理を複数のスレッド８が行っている場合は、同一処理を行っている複数のスレッド８のうち、最後に処理を終了したスレッド８の時刻がパイプライン処理の処理終了時刻として採用される。また、複数のスレッド８によってプロセス７が構成されている場合は、プロセス７の処理時間は、最初に処理を開始したスレッド８の処理開始時刻から最後に処理を完了したスレッド８の処理完了時刻までとする。そして、その処理時間の中で、プロセス７のＣＰＵ時間が求められる。
【００３０】
各スレッド処理時間監視部９は、各ＣＰＵコア５で動作するスレッド８の開始時刻、処理終了時刻をスレッド８より受信すると、それぞれのスレッド８の処理時間、ＣＰＵ時間を求め、計算機負荷監視部１０に送信する。計算機負荷監視部１０は、スレッド処理時間監視部９から処理時間、ＣＰＵ時間を受信すると、スレッド８ごとに処理時間、ＣＰＵ時間の履歴を保持するとともに、プロセス７としての処理時間、ＣＰＵ時間を求める。また、各履歴をもとに、スレッド８およびプロセス７の処理時間、ＣＰＵ時間に関する傾向を一次近似式で求め、保持しておく。一次近似式は、例えば最小二乗法などで求めることが考えられる。
【００３１】
図８は、この実施の形態における計算機リソース制御方式の各構成要素の連係動作の別の例を示す図である。
パイプライン処理時間監視部１１からシステム負荷監視部１３に処理時間変動通知（Ａ６）が届くと、図において、処理時間変動の要因となったプロセス７を調査するため、処理時間変動が発生したパイプライン処理の各スレッド８が動作するＣＰＵ４の計算機負荷監視部１０に、処理時間に変動のあったプロセス７を抽出するよう指示する（Ａ７）。計算機負荷監視部１０は、処理時間の傾向に変動のあったプロセス７の識別子、および、すでに処理を複数のスレッド８に分割している場合は分割数をシステム負荷監視部１３に通知する（Ａ８）。
【００３２】
Ａ８以降、システム負荷監視部１３は、Ａ８で受信したプロセス７のうち、処理時間が短縮傾向にある場合で、かつ、すでに処理が複数のスレッド８に分割されているプロセス７があれば、デッドラインミスを発生させずにスレッド数を削減させるよう、処理の分割数を決定する。
【００３３】
また、処理が増加傾向にある場合で、かつ、１つのプロセスの分割数がそのＣＰＵのＣＰＵコア数以下である場合には、制限時間オーバーを先延ばしするか、もしくは制限時間オーバーを解消可能なスレッド数に分割するよう、スレッド数、およびスレッドを動作させるＣＰＵ、ＣＰＵコアを決定する。
なお、システム負荷監視部１３の、スレッド数、および、スレッドを動作させるＣＰＵ４、ＣＰＵコア５の決定方式は、後にフローチャートにて詳細を述べる。
そして、そのプロセス７が動作するＣＰＵ４の計算機負荷監視部１０に、スレッドの起動、停止などを指示する（Ａ９）。
スレッド８の起動、停止指示を受け取った計算機負荷監視部１０は、ＣＰＵコア５ごとに存在するスレッド割付部１２に、各ＣＰＵコア５にスレッドを起動、停止するよう指示し（Ａ１０）、スレッド割付部１２は、各ＣＰＵコア５でスレッド８を起動、停止する（Ａ１１）。
【００３４】
図９は、この実施の形態におけるシステム負荷監視部１３の、パイプライン処理の処理時間変動時におけるスレッド８、スレッド８を動作させるＣＰＵ４、ＣＰＵコア５の決定の手順を示すフローチャート図である。
【００３５】
ステップＳ１で、システム負荷監視部１３は、パイプライン処理時間監視部１１から処理時間変動の通知を待つ。
パイプライン処理時間監視部１１から処理時間変動の通知を受信すると、ステップＳ２で、システム負荷監視部１３は、通知内容が、今後時間Ｔ１以内にパイプライン処理の処理時間が制限時間をオーバーすることを示すものであるか、制限時間オーバー発生間近を示すものであるか、処理時間が短縮傾向であることを示すものであるかを調べる。通知内容が時間Ｔ１内に制限時間オーバーするというものであれば、ステップＳ３に進み、制限時間オーバー間近であれば、ステップＳ５に進み、減少傾向であればステップＳ４に進み、各ステップにおいて処理を行う。各ステップの処理を終了すると、ステップＳ１に戻る。システム負荷監視部１３は、Ｓ１〜Ｓ５の処理を、パイプライン処理時間監視部１１から通知を受ける限り繰り返す。
【００３６】
図１０は、この実施の形態におけるステップＳ３のシステム負荷監視部１３の処理を示すフローチャート図である。
【００３７】
ステップＳ１００１で、システム負荷監視部１３は、パイプライン処理時間監視部１１から受信したパイプライン処理の識別子より、そのパイプライン処理を構成するプロセス７を調べる。
ステップＳ１００２で、システム負荷監視部１３は、ステップＳ１００１で抽出したプロセス７が動作する計算機３の計算機負荷監視部１０に、処理時間、ＣＰＵ時間が増加傾向にあるプロセス７と、処理時間、ＣＰＵ時間の変化に関する近似式、およびプロセス７の現在の分割数を調べるよう指示し、計算機負荷監視部１０からこれらの通知を受信し、記憶しておく。
【００３８】
ステップＳ１００３で、システム負荷監視部１３は、各パイプライン処理を構成するプロセス７のＣＰＵ時間の増加量、処理時間の増加量、および、パイプライン処理の処理時間の増加量から、パイプライン処理の処理時間増加が、パイプライン処理を構成するプロセス７に原因があるのか、同一ＣＰＵコア５で動作する、より優先度の高い他のパイプライン処理に属するスレッド８がＣＰＵ４を占有したことによって処理時間が長くなって起きたのか、を調査する。
調査の具体的な方法としては、例えば、パイプライン処理を構成するスレッド８のＣＰＵ時間の増加量とパイプライン処理の処理時間の増加量の差を求め、パイプライン処理の処理時間の増加量が各スレッド８のＣＰＵ時間の増加量の和と同一であれば、制限時間オーバーの可能性のあるパイプライン処理に属するスレッド８がＣＰＵ４を占有したことによって処理時間が長くなったことと考えることができる。
なお、本実施の形態では、現在時刻より時間Ｔ１だけ先の時刻までに制限時間オーバーが発生する原因が、自パイプライン処理を構成するプロセス７にあるパイプライン処理に対してのみ処理時間短縮に向けた処理を行うこととする。この理由は、このパイプライン処理のスレッド８の実行時間を短縮することにより、制限時間オーバーの原因が他のパイプライン処理を構成するプロセス７にある場合のパイプライン処理の時間短縮も可能となると考えられるためである。
【００３９】
ステップＳ１００３で、システム負荷監視部１３は、処理時間短縮に向けた処理を行うパイプライン処理の識別子を全て抽出し、記憶する。
ステップＳ１００４で、システム負荷監視部１３は、ステップＳ１００３において処理時間短縮に向けた処理を行うことになったパイプライン処理の全てについて、Ｓ１００５〜Ｓ１０２３を行ったかどうかを調べ、行った場合は終了し、行っていなければ、パイプライン処理の処理時間短縮に向けた処理を行う。
【００４０】
ステップＳ１００５以降では、まず、パイプライン処理の制限時間オーバー発生の原因となったプロセス７の処理を同一ＣＰＵ４上の他ＣＰＵコア５にて分割することにより制限時間オーバーの解消を目指し、それが不可能であれば、他計算機３へのプロセス移行を行う。
以下、ステップＳ１００５以降の処理を説明する。
【００４１】
ステップＳ１００５で、システム負荷監視部１３は、ステップＳ１００３で抽出したパイプライン処理の中から１つを選択する。
ステップＳ１００６で、システム負荷監視部１３は、ステップＳ１００５で選択したパイプライン処理を構成するプロセス７中のＣＰＵ時間が増加傾向にあるプロセス７で、ステップＳ１００７で記憶した分割数（ステップＳ１００５で選択したパイプライン処理について、ステップＳ１００７で分割数を記憶していない場合には、ステップＳ１００２にて記憶した分割数）にさらに１加えた場合に、現在時刻からＴ１だけ先の時刻において１スレッドあたりのＣＰＵ時間の削減量の最も多いプロセスを選択する。
【００４２】
図１１は、この実施の形態におけるプロセスの分割とＣＰＵ時間の削減量との関係を説明するための図である。
例えば、図において、パイプライン処理Ａがプロセス１、プロセス２、プロセス３で構成され、プロセス１とプロセス３のＣＰＵ時間が増加傾向にあったとする。ステップＳ１００２にて記憶しているプロセス１の分割数が１、プロセス３の分割数が３であったとし、現在時刻から時間Ｔ１だけ先の時刻におけるプロセス１、プロセス３のＣＰＵ時間を、ステップＳ１００２で記憶した近似式を用いて求めたところ、プロセス１のＣＰＵ時間が１００、プロセス３のＣＰＵ時間が１２０であったとする。この場合、プロセス１の分割数を１加えるとプロセス１の分割数は２であり、各スレッドのＣＰＵ時間は５０、プロセス３の分割数を１加えると、プロセス３の分割数は４となり、ＣＰＵ時間は３０となる。本例の場合、元のプロセス１の分割数は１、スレッドのＣＰＵ時間は１００であり、分割数を１増やした（分割数は２となる）場合のプロセス１を構成するスレッドのＣＰＵ時間は５０となり、削減量は５０となる。そして、プロセス３は、元は３つのスレッドに分割されており、元の各スレッドのＣＰＵ時間は４０であったため、分割数を１増やした（分割数は４となる）場合のスレッドのＣＰＵ時間は３０となり、削減量は１０である。以上から、スレッドのＣＰＵ時間の削減量の最も多いプロセスはプロセス１となるため、プロセス１を選択する。
【００４３】
ステップＳ１００７で、システム負荷監視部１３は、ステップＳ１００６で選択したプロセス７のみ分割数を１加え、その他のプロセス７の分割数はステップＳ１００２で記憶したときのままとして記憶する。前記の例の場合、プロセス１の分割数を２、プロセス３の分割数を３として記憶する。
ステップＳ１００８で、システム負荷監視部１３は、ステップＳ１００７の分割数における、現在時刻から時間Ｔ１だけ先の時刻におけるパイプライン処理の処理時間を求める。
ステップＳ１００９で、システム負荷監視部１３は、制限時間オーバーが解消されるかどうか調べる。制限時間オーバーが解消されなければ、ステップＳ１０２２に進む。
【００４４】
ステップＳ１０２２において、システム負荷監視部１３は、ステップＳ１００７における各プロセス７の分割数が、そのプロセス７が動作する計算機３のうち、同一パイプライン処理に属する他のプロセス７、スレッド８が動作していないＣＰＵコア数の値よりも大きいかどうかを調べ、ＣＰＵコア数以下であればステップＳ１００６に進む。
コア数よりも大きい場合は、１つのＣＰＵコア５に同一パイプライン処理のスレッド８が複数動作することになり、スレッド８の処理時間が分割数よりも大きくなるため、そのプロセス７をスレッド分割してもパイプライン処理の制限時間オーバーの解消は不可能とし、ステップＳ１００４に進む。
【００４５】
ステップＳ１０２２からステップＳ１００６に進んだ場合、ステップＳ１００６において、システム負荷監視部１３は、ステップＳ１００５で選択したパイプライン処理を構成するプロセス７で、Ｓ１００７で記憶した分割数からさらに１だけ加えた場合に、ＣＰＵ時間の削減量が最も多いプロセスを選択する。前記の例の場合、新たにプロセス１の分割数を１加えると分割数は３となり、スレッドのＣＰＵ時間は３３．３、スレッドのＣＰＵ時間の削減量は１６．７、プロセス３の分割数を１加えると分割数は４となり、スレッドのＣＰＵ時間は３０、ＣＰＵ時間の削減量は１０となる。この場合、スレッドあたりのＣＰＵ時間の削減量が最も多いプロセスはプロセス１となる。以下、同様にステップＳ１００７〜ステップＳ１００８を行う。
【００４６】
システム負荷監視部１３は、ステップＳ１００５〜ステップＳ１００９を、現在時刻から時間Ｔ１だけ先の時刻において、制限時間オーバーが解消されるか、ステップＳ１００６で選択したプロセスの、ステップＳ１００７で記憶したスレッドへの分割数がＣＰＵコア数になっても制限時間オーバー解消が不可能となるまで行う。
ステップＳ１００５〜ステップＳ１００９の処理の結果、現在時刻から時間Ｔ１だけ先の時刻において制限時間オーバーが解消される場合、ステップＳ１０１０に進む。
【００４７】
ステップＳ１０１０以降では、ステップＳ１００６で選択したプロセス群を、ステップＳ１００７で記憶した分割数まで分割し、各スレッドを同一ＣＰＵ４の異なるＣＰＵコア５に配置させる。
【００４８】
ステップＳ１０１０において、システム負荷監視部１３は、分割数を変更するプロセス７の中で、過去にステップＳ１０１１で選択していないプロセス７のうち、スレッド８あたりのＣＰＵ時間が最も長いプロセス７を１つ選択する。
ステップＳ１０１１において、システム負荷監視部１３は、Ｓ１０１０のプロセス７の新規起動するスレッド８のうち、配置するスレッド８を１つ選択する。
ステップＳ１０１２で、システム負荷監視部１３は、スレッド８の属するプロセス７が動作する計算機３において、同一プロセス７のスレッド８が動作しておらず、同一パイプライン処理を構成するプロセス７のスレッド８が動作していないＣＰＵコア５を選択し、そのＣＰＵコア５でスレッド８を動作させた場合に、新規起動するスレッド８が動作可能か、そして、そのＣＰＵコア５で動作しているその他のスレッド８が、新規にスレッド８を起動しても制限時間内に動作可能かどうか、を調べる。
スレッドｔｍの処理時間Ｅｘｅｃ（ｔｍ）は、スレッドｔｍの起動を予定するＣＰＵコアですでに動作しているスレッドを、処理の優先度の高い順に並べたものを｛ｔ１，ｔ２，…，ｔｍ，…，ｔｎ｝とし、スレッドｔｍの処理周期をＣｍ、ＣＰＵ時間をｃｐｕ（ｔｍ）とした場合、次の式として表すことができる。
【数１１】
0005465105.tif 000002
そして、その他のスレッド８の処理時間は、ｔｍよりも優先度の高いスレッドは変化せず、ｔｍよりも優先度の低い各スレッドｔｘは、次の式の分だけ増加する。
【数１２】
0005465105.tif 000003
【００４９】
ステップＳ１０１３において、システム負荷監視部１３は、ステップＳ１０１２で求めた各スレッド８の処理時間から、各スレッド８が属するプロセス７の処理時間を求め、プロセス７の処理時間からパイプライン処理の処理時間を求める。そして、システム中のパイプライン処理が制限時間オーバーを発生させないかどうかを調べる。新たに分割数を決定した後の、ステップＳ１００３で抽出した以外のパイプライン処理の処理時間は、「パイプライン処理の処理時間＋（分割数決定後のプロセスの処理時間−新しい分割数を決定する前のプロセスの処理時間）」として求めることができる。
ステップＳ１０１４で、システム負荷監視部１３は、プロセス７の処理時間が変動した全てのパイプライン処理が制限時間オーバーを起こしていないかどうか調べ、起こしていなければ、ステップＳ１０１５に進み、制限時間オーバーするパイプライン処理があれば、ステップＳ１０１５を行わずにステップＳ１０１６に進む。
ステップＳ１０１５にて、システム負荷監視部１３は、そのＣＰＵコア５をスレッド８の配置先の候補として記憶する。
ステップＳ１０１６において、システム負荷監視部１３は、同一のパイプライン処理に属するプロセス７のスレッド８が動作していないＣＰＵコア５の全てについてスレッド８の配置可能性の調査を行ったかどうか調べ、行っていなければ、ステップＳ１０１２に戻る。調査をおこなった場合はステップＳ１０１７に進む。
【００５０】
ステップＳ１０１７にて、システム負荷監視部１３は、ステップＳ１０１５において記憶したＣＰＵコア５、つまり、スレッド８を配置可能なＣＰＵコア５があればステップＳ１０１８に進み、記憶したＣＰＵコア５がなければ、そのプロセス７は同一計算機に配置不可能であるため、ステップＳ１０２３に進み、他の計算機に配置するための処理を行う。
ステップＳ１０１８において、システム負荷監視部１３は、ステップＳ１０１５にて記憶した全てのＣＰＵコア５のうち、ＣＰＵ空き時間の最も少ないＣＰＵコア５を、スレッド８の配置先として決定する。ここで求めるＣＰＵ空き時間は、最も優先度の低いスレッド８をｔｘ、スレッドｔｘの処理周期をＣ（ｔｘ）、ＣＰＵ時間をｃｐｕ（ｔｘ）とすると、次の式で求められる。
【数１３】
0005465105.tif 000004
【００５１】
そして、ステップＳ１０１９において、システム負荷監視部１３は、新規起動する全てのスレッド８の再配置が決まっていなければ、ステップＳ１０１１に戻る。ステップＳ１０１１〜ステップＳ１０１９の処理を、全てのスレッド８の配置先が決まるまで行う。
１つのプロセス７の全てのスレッド８の配置が決定したら、ステップＳ１０２０で、システム負荷監視部１３は、計算機負荷監視部１０にステップＳ１０１７で記憶したＣＰＵコア５でスレッド８を起動するよう指示する。計算機負荷監視部１０は、ステップＳ１０２０でスレッド起動の指示を受けると、ステップＳ１０１８で記憶したＣＰＵコア５のスレッド割付部１２にスレッド起動を指示する。スレッド割付部１２は、スレッド８を起動する。その際、スレッド割付部１２は、スレッド制御部１４に、各スレッド８がデータ中どの部分を処理すべきかを指示し、さらに、パイプライン処理において、自プロセス７の次に処理を行うプロセス７にデータを送信するよう指示する。各スレッド８がデータ中のどの部分を処理すべきか、という分け方は、例えば、各スレッド８にスレッド数と固有の番号を与え、スレッド数に応じてデータを均等分割し、そのうちの自スレッドの番号である、Ｎ番目のデータを処理するなどが考えられる。例えば、プロセス７を５つのスレッド８に分割し、１００個の配列を持つデータを受信した場合、１番のスレッドは分割後の配列の１番目のブロックである配列の１番目〜２０番目のデータを処理する、２番のスレッドは２１〜４０番目を処理する、などのようなことが考えられる。
その後、ステップＳ１０２１に進む。
【００５２】
ステップＳ１０２１で、システム負荷監視部１３は、全てのプロセス７およびスレッド８について処理を完了していれば、ステップＳ１００４に戻り、完了していなければ、ステップＳ１０１０に戻る。
【００５３】
ステップＳ１０２３の処理を行う場合は、ステップＳ１０１７で、スレッド８を配置可能なＣＰＵコア５が計算機３内に存在しない場合であるため、この場合には、これまでに決定したスレッド８のＣＰＵコア配置をキャンセルし、他の計算機３にプロセス７を配置するための処理を行う。
【００５４】
図１２は、この実施の形態におけるステップＳ１０２３における、システム負荷監視部１３の他計算機３へのプロセス配置処理を示すフローチャート図である。
【００５５】
ステップＳ１０２４で、システム負荷監視部１３は、他計算機３に移行対象となったプロセス７の動作中の計算機３以外の計算機３を１つ抽出し、分割数をステップＳ１００７で記憶した数とし、ステップＳ１０１１〜ステップＳ１０１５を行う。
その結果、ステップＳ１０２６において、システム負荷監視部１３は、ステップＳ１０１５でスレッド８の配置先として記憶したＣＰＵコア５があれば、ステップＳ１０２７に進む。
ステップＳ１０２７で、システム負荷監視部１３は、ステップＳ１０１８を行う。そして、選択したプロセス７の、新規起動する全てのスレッド８の配置するＣＰＵコア５が決定した場合は、ステップＳ１０２９に進む。
ステップＳ１０２９で、システム負荷監視部１３は、ステップＳ１０２７で記憶したＣＰＵコア５全てでスレッド８を起動するよう計算機負荷監視部１０に指示する。計算機負荷監視部１０は、指定されたＣＰＵコア５でスレッド８を起動するよう、スレッド割付部１２に指示する。スレッド割付部１２は、スレッド８を起動する。その際、スレッド割付部１２は、スレッド制御部１４に、各スレッド８がデータ中どの部分を処理すべきかを指示し、さらに、パイプライン処理において、自プロセスの次に処理を行うプロセスにデータを送信しないよう指示する。各スレッド８がデータ中どの部分を処理すべきか、という分け方は、例えば、各スレッド８にスレッド数と固有の番号を与え、スレッド数に応じてデータを均等分割し、そのうちの自スレッドの番号である、Ｎ番目のデータを処理するなどが考えられる。例えば、プロセス７を５つのスレッド８に分割し、１００個の配列を持つデータを受信した場合、１番のスレッドは分割後の配列の１番目のブロックである配列の１番目〜２０番目のデータを処理する、２番のスレッドは２１〜４０番目を処理する、などのようなことが考えられる。
ステップＳ１０３０で、システム負荷監視部１３は、パイプライン処理において、選択したプロセス７にデータを送信するプロセス７が動作する計算機３の計算機負荷監視部１０に、Ｓ１０２４で選択したホスト（計算機３）で新規プロセスを起動した旨を伝える。計算機負荷監視部１０は、スレッド制御部１４に、データ送信処理を行うプロセス７が、新規プロセスにデータを送信するよう指示する。これにより、データ送信処理を行うプロセス７が新規プロセスにデータを送信できるようになる。
そして、ステップＳ１０３１において、システム負荷監視部１３は、選択したプロセス７のデータ送信先となるプロセス７が動作する計算機３の計算機負荷監視部１０に、Ｓ１０２４で選択したホスト（計算機３）で新規プロセスを起動した旨を伝え、計算機負荷監視部１０は、スレッド制御部１４に、新規起動したスレッド８からのデータを破棄するよう指示する。本処理の後、ステップＳ１０２１に進む。
【００５６】
ステップＳ１０２６において、ステップＳ１０１５でスレッドの配置先ＣＰＵコアを記憶していなければ、ステップＳ１０２４で選択した計算機３でプロセス配置不可とし、ステップＳ１０３２に進む。システム負荷監視部１３は、未選択の計算機３があれば、ステップＳ１０２４に戻る。未選択のＣＰＵ４（計算機３）がなければ、そのプロセス７はシステムの全計算機３で配置不可とし、ステップＳ１０２１に進む。
【００５７】
また、本実施の形態において、ステップＳ１０２３を実行した場合、他の計算機３上にプロセスを新規起動したため、Ｎ周期分のデータを蓄積するまでプロセス７を処理に参入させないようにしている。これは、ステップＳ１０３１において、処理を分割し、プロセス７からのデータを破棄することにより実現している。
Ｔ１時間以上経過し、制限時間オーバーが発生するまでに、パイプライン処理時間監視部１１は、システム負荷監視部１３に、図９のＳ１において、制限時間オーバー間近である旨を通知する。すると、システム負荷監視部１３は、ステップＳ５で、新規起動したプロセスを処理に参入させる。
【００５８】
図１３は、この実施の形態におけるステップＳ５における処理手順を示すフローチャート図である。
【００５９】
ステップＳ１０３２で、システム負荷監視部１３は、新規起動したプロセス７のデータの送信先となるプロセス７が動作する計算機３の計算機負荷監視部１０に、新規起動したスレッド８が送信するデータを受信するよう指示する。システム負荷監視部１３からの指示を受けた計算機負荷監視部１０は、スレッド制御部１４に新規起動したスレッド８が送信するデータを受信するよう指示する。これにより、プロセス７は、新規起動したスレッド８からのデータを受信することができる。計算機負荷監視部１０からスレッド制御部１４への通知内容としては、例えば、自プロセスの前の処理を行うプロセス７のスレッド８の数などが考えられる。スレッド数がわかれば、１回の処理で受信すべきデータ数を把握することができる。
これにより、パイプライン処理において新規起動したプロセス７の次の処理を行うプロセス７は、新規起動したスレッド８からのデータを受信するようになる。
ステップＳ１０３３で、新規起動するプロセス７と同一処理を行い新規起動するプロセス７よりも前から動作していたプロセス７の計算機負荷監視部１０に、プロセス７を停止するよう指示する。計算機負荷監視部１０は、スレッド割付部１２にプロセス７の各スレッド８を停止するよう指示し、各ＣＰＵコア５で動作するスレッド割付部１２は、停止対象のプロセス７のスレッド８を停止させる。
【００６０】
以上説明した計算機システムは、複数のＣＰＵコア５を持つＣＰＵ４を搭載した計算機３をネットワーク２により複数台接続することにより構成される。
分散リアルタイム処理システムは、各計算機３の各ＣＰＵコア５で複数のプロセス７が連携または独立して動作する。各プロセス７は、一定時間周期で処理を行い、制限時間内に処理を完了することが求められている。
計算機リソース制御方式は、スレッド処理時間監視部９と、計算機負荷監視部１０と、パイプライン処理時間監視部１１と、スレッド割付部１２と、スレッド制御部１４と、システム負荷監視部１３とを有する。
スレッド処理時間監視部９は、プロセス７の構成要素であるスレッド８の処理時間を監視する。
計算機負荷監視部１０は、各計算機３上で動作するスレッド８の処理時間およびＣＰＵ時間を取得して履歴を保持し、履歴をもとに処理時間やＣＰＵ時間の変動を調査する。
パイプライン処理時間監視部１１は、複数のプロセス７が連携して動作する場合に連携動作するプロセス群全体の処理時間を取得し、履歴を保持し、履歴をもとに、処理時間の変動を検出する。
スレッド割付部１２は、ＣＰＵコア５にてスレッド起動、停止を指示するとともに、データの送信先や送信元の変更、送信するデータの領域などをスレッド制御部１４に指示する。
スレッド制御部１４は、スレッド割付部１２の指示をもとに、各計算機３、各ＣＰＵコア５からのデータから、適切なデータ領域のデータを受信し、適切なデータ領域のデータを送信する役割を持つ。
システム負荷監視部１３は、処理時間に変更があった場合に、プロセス７のスレッド８への処理の分割やスレッド数の削減などの処理を行う。
計算機リソース制御方式は、各構成要素に以下の特徴を付与することにより、前記分散リアルタイム処理システムの制限時間超過の防止、処理時間短縮時の処理の集約を行う。
【００６１】
・処理の制限時間超過が予想される場合に、システム負荷監視部１３により、制限時間超過発生の原因となるプロセス７を、自プロセス７が属する処理およびシステムで動作する全ての処理の制限時間超過が発生しない数の処理に分割する。
・決定した分割数のスレッド８を、元のプロセス７が動作していたＣＰＵコア５に配置できない場合に、システム負荷監視部１３が、プロセス７を他の計算機３に移動させ、他のＣＰＵコア５で分割数分のスレッド８を起動する。
・他の計算機３にプロセス７を移動させた場合、スレッド割付部１２により、プロセス７が必要とするデータが蓄積された後、プロセス７を処理に参入させる。
【００６２】
このように、本実施の形態の計算機リソース制御方式では、プロセス７を制限時間超過が発生しない数のスレッド８に分割し、そのスレッド８を、元のプロセス７が動作していた計算機３の他ＣＰＵコア５に配置させることにより、プロセス移動のオーバーヘッドを排除し、他の計算機３への移行が必要となった場合には、極力同一計算機３内に処理を配置することにより、ステップＳ５の処理が不要となるため、プロセス７の分散化にともなうオーバーヘッドを排除することが可能になる。また、他の計算機３にてプロセス７を起動した場合も、新規起動したプロセス７が必要とするデータが十分蓄積された段階でそのプロセス７を処理に参入させることにより、演算データの不整合を防ぐことが可能となる。
【００６３】
実施の形態２．
実施の形態２について、図１４〜図１５を用いて説明する。
なお、実施の形態１と共通する部分については、同一の符号を付し、説明を省略する。
【００６４】
実施の形態１は、パイプライン処理の制限時間オーバーが予想される場合に、パイプライン処理を構成するプロセス７を複数のスレッド８に分割し、全スレッド８を同一計算機３で動作できるようにしたものであるが、次に、一部のスレッド８は元の計算機３の他のＣＰＵコア５で動作可能であるが、他のスレッド８が元の計算機３の他のＣＰＵコア５で動作できない場合に、それらのスレッド８を他の計算機３で動作させる実施の形態を示す。
【００６５】
図１４は、この実施の形態におけるシステム負荷監視部１３のステップＳ３の処理手順を示すフローチャート図である。
【００６６】
ステップＳ２００１において、システム負荷監視部１３は、ステップＳ１００１〜Ｓ１００３を実行する。
ステップＳ２００２で、システム負荷監視部１３は、ステップＳ１００３において処理時間短縮に向けた処理を行うことになったパイプライン処理の全てについて、ステップＳ２００３〜Ｓ２０１４を行ったかどうかを調べる。行った場合、システム負荷監視部１３は、ステップＳ３を終了する。行っていなければ、システム負荷監視部１３は、ステップＳ２００３以降でパイプライン処理の処理時間短縮に向けた処理を行う。
ステップＳ２００３で、システム負荷監視部１３は、ステップＳ１００５を実行する。
ステップＳ２００４で、システム負荷監視部１３は、ステップＳ１００６〜Ｓ１００８を実行する。
ステップＳ２００５で、システム負荷監視部１３は、現在時刻から時間Ｔ１だけ先の時刻において制限時間オーバーが解消される場合、ステップＳ２００６に進む。
制限時間オーバーが解消されない場合、システム負荷監視部１３は、ステップＳ２０１６に進む。システム負荷監視部１３は、現在のスレッドの分割数を調べる。分割数がＣＰＵコア数よりも大きい場合、システム負荷監視部１３は、１つのＣＰＵコア５に同一パイプライン処理のスレッド８が複数動作することになり、スレッド８の処理時間が分割数よりも大きくなるため、そのプロセス７をスレッド分割してもパイプライン処理の制限時間オーバーの解消は不可能とし、ステップＳ２００２に戻る。分割数がＣＰＵコア数以下の場合、システム負荷監視部１３は、ステップＳ２００４に戻る。
ステップＳ２００６で、システム負荷監視部１３は、ステップＳ１０１０を実行する。
ステップＳ２００７で、システム負荷監視部１３は、ステップＳ１０１１を実行する。
ステップＳ２００８で、システム負荷監視部１３は、ステップＳ１０１２〜Ｓ１０１３を実行する。
ステップＳ２００９で、システム負荷監視部１３は、プロセス７の処理時間が変動した全てのパイプライン処理が制限時間オーバーを起こしていないかどうか調べる。起こしていなければ、システム負荷監視部１３は、ステップＳ２０１０に進む。制限時間オーバーするパイプライン処理があれば、システム負荷監視部１３は、ステップＳ２０１０を行わずにステップＳ２０１１に進む。
ステップＳ２０１０にて、システム負荷監視部１３は、そのＣＰＵコア５をスレッド８の配置先の候補として記憶する。ステップＳ２０１１において、システム負荷監視部１３は、同一のパイプライン処理に属するプロセス７のスレッド８が動作していないＣＰＵコア５の全てについてスレッド８の配置可能性の調査を行ったかどうか調べる。行っていなければ、システム負荷監視部１３は、ステップＳ２００８に戻る。調査をおこなった場合、システム負荷監視部１３は、ステップＳ２０１２に進む。
ステップＳ２０１２で、システム負荷監視部１３は、Ｓ１０１５で記憶したＣＰＵコアがあれば、ステップＳ２０１３に進む。
ステップＳ２０１３で、システム負荷監視部１３は、記憶したＣＰＵコアのうち、最も空きＣＰＵ時間の少ないＣＰＵコア５でスレッドを起動する。
ステップＳ２０１４で、システム負荷監視部１３は、選択したプロセスの全新規起動スレッド８について、配置するＣＰＵコア５が決定していれば、ステップＳ２０１５に進む。決定していなければ、システム負荷監視部１３は、ステップＳ２００７に戻る。
ステップＳ２０１５にて、システム負荷監視部１３は、全てのプロセス７のスレッド８の配置先が決定していれば、ステップＳ２００２に戻る。決定していなければ、システム負荷監視部１３は、ステップＳ２００６に戻る。
なお、ステップＳ２０１２において、ステップＳ１０１５で記憶したＣＰＵコア５がなければ、同一計算機３の他コア内にスレッド８を動作可能な計算機３が存在しないことになるため、そのプロセス７の残りスレッド８を他の計算機３で動作させるため、ステップＳ２０１７に進む。
【００６７】
図１５は、この実施の形態におけるステップＳ２０１７の動作を示すフローチャート図である。
【００６８】
ステップＳ２０１８において、システム負荷監視部１３は、スレッド分割の対象となっているプロセス７が動作している計算機３およびステップＳ２０１８で選択した計算機以外の計算機３を１つ選択する。
ステップＳ２０１９で、システム負荷監視部１３は、選択した計算機３で起動すべきスレッド数を、ステップＳ１００７で記憶したスレッド数から、ステップＳ１０２０、ステップＳ２０２２で起動したスレッド数を引いたものとする。
ステップＳ２０２０で、システム負荷監視部１３は、ステップＳ１０１１〜Ｓ１０１６を実行する。
ステップ２０２１で、システム負荷監視部１３は、ステップＳ１０１５で記憶したＣＰＵコア５があるかどうかを調べ、あればステップＳ２０２２に進む。なければ、システム負荷監視部１３は、ステップＳ２０２６に進む。
ステップＳ２０２２で、システム負荷監視部１３は、ステップＳ１０１８を実行する。
ステップＳ２０２３で、システム負荷監視部１３は、ステップＳ２０２２で選択したＣＰＵコア５でスレッドを起動する。
ステップＳ２０２４で、システム負荷監視部１３は、パイプライン処理において、起動したプロセス７のデータ送信元となるプロセスに、新規にプロセス７が起動した旨と、起動したホスト（計算機３）を通知する。
ステップＳ２０２５で、システム負荷監視部１３は、配置すべき全てのスレッド８の配置するＣＰＵコア５が決定したかどうかを調べる。決定していれば、システム負荷監視部１３は、ステップＳ２０１５に戻る。決定していなければ、システム負荷監視部１３は、ステップＳ２０２０に戻り、配置先ＣＰＵコア５が決定していないスレッド８について、配置可能なＣＰＵコア５の調査を行う。
ステップＳ２０２６で、システム負荷監視部１３は、Ｓ２０１８で未選択の計算機３があるかどうかを調べる。あれば、システム負荷監視部１３は、他の計算機３でスレッド８を起動するため、ステップＳ２０１８に進む。未選択の計算機３がなければ、システム負荷監視部１３は、制限時間オーバー解消に向けたプロセス７の処理時間短縮を断念し、ステップＳ２０１５に戻る。
【００６９】
本実施の形態において、ステップＳ２０１７を実行した場合、他の計算機３上にプロセス７を新規起動したため、Ｎ周期分のデータを蓄積するまで、プロセス７を処理に参入させないようにする必要がある。そこで、Ｔ１時間以上経過し、制限時間オーバーが発生するまでに、パイプライン処理時間監視部１１は、システム負荷監視部１３に、図９のＳ１において、制限時間オーバー間近である旨を通知する。そして、ステップＳ５で、システム負荷監視部１３は、新規起動したプロセス７を処理に参入させる。この場合の処理手順において、システム負荷監視部１３は、新規起動したプロセス７のデータの送信先となるプロセス７が動作する計算機３の計算機負荷監視部１０に、新規起動したプロセス７からのデータを受信するよう指示する。計算機負荷監視部１０は、スレッド制御部１４に、新規起動したプロセス７からのデータを受信するよう指示する。指示の内容としては、プロセス７が新規起動した計算機３の識別子、スレッド８の数などが考えられる。これにより、パイプライン処理において、新規起動したプロセス７の後の処理を行うプロセス７からのデータを受信するようになり、新規起動したプロセス７は処理に参入することができる。
【００７０】
以上説明した計算機リソース制御方式は、以下の特徴を加えることにより、システムの計算機リソースを効率よく使用する。
・決定した分割数の全てのスレッド８を元のプロセス７が動作していたものと同一計算機３の他ＣＰＵコア５に配置できない場合に、システム負荷監視部１３により、動作可能なスレッド８のみ配置し、配置できなかったスレッド８を他の計算機３に移動させる。
・プロセス７の一部処理を他の計算機３に移動させた場合、スレッド割付部１２により、新規起動した全てのプロセス７が必要とするデータが蓄積された後、全ての新規起動したプロセス７を処理に参入させる。
【００７１】
このように、本実施の形態における計算機リソース制御方式では、同一計算機３のＣＰＵコア５に配置できなかったスレッド８の処理のみ他の計算機に配置することにより、計算機３の余剰リソースを有効に活用することができる。
【００７２】
実施の形態３．
実施の形態３について、図１６を用いて説明する。
なお、実施の形態１〜実施の形態２と共通する部分については、同一の符号を付し、説明を省略する。
【００７３】
実施の形態１は、パイプライン処理の制限時間オーバーが予想される場合に、パイプライン処理を構成するプロセス７を複数のスレッド８に分割し、全スレッド８を同一計算機で動作できるようにしたものであるが、次に、ＣＰＵ時間が増加傾向にあるプロセス７を、パイプライン処理における、自プロセス７の前または後の処理を行うプロセス７が動作する計算機３上の異なるＣＰＵコア５に優先的に配置することにより、プロセス間通信時間を短縮し、パイプライン処理の制限時間オーバーまでの時間をさらに先延ばしにさせる実施の形態を示す。
【００７４】
図１６は、この実施の形態におけるシステム負荷監視部１３のステップＳ３の処理手順を示すフローチャート図である。
【００７５】
ステップＳ３００１で、システム負荷監視部１３は、Ｓ１００１〜Ｓ１００３を行う。
ステップＳ３００２で、システム負荷監視部１３は、Ｓ１００３で抽出した全てのパイプライン処理について、Ｓ３００３〜Ｓ３０１６を実施したかどうかを調べる。実施していなければ、システム負荷監視部１３は、ステップ３００３に進む。実施していれば、システム負荷監視部１３は、ステップＳ３を終了する。
ステップＳ３００３において、システム負荷監視部１３は、ステップＳ１００５を実行する。
ステップＳ３００４において、システム負荷監視部１３は、ステップＳ１００６〜Ｓ１００８を実行する。
ステップＳ３００５において、システム負荷監視部１３は、ステップＳ１００６で選択したプロセス７をステップＳ１００７で記憶したスレッド数に分割した場合に、制限時間オーバーの解消が可能であるかどうかを調べる。可能であれば、システム負荷監視部１３は、ステップＳ３００６に進む。可能でなければ、システム負荷監視部１３は、ステップＳ３００４に戻る。
ステップＳ３００６で、システム負荷監視部１３は、ステップＳ１０１０を実行する。
ステップＳ３００７で、システム負荷監視部１３は、パイプライン処理において、ステップＳ３００６で選択したプロセス７のデータ送信元となるプロセス７が動作する計算機３があるかどうかを調べる。あれば、システム負荷監視部１３は、ステップＳ３００８に進む。なければ、システム負荷監視部１３は、ステップＳ３０１７に進む。
ステップＳ３００８で、システム負荷監視部１３は、その計算機を選択する。
ステップＳ３００９で、システム負荷監視部１３は、ステップＳ１０１１を実行する。
ステップＳ３０１０で、システム負荷監視部１３は、ステップＳ３００７で選択した計算機３のＣＰＵコア５において、ステップＳ３００６で選択したプロセス７と同一パイプライン処理に属するプロセス７のスレッド８が動作していないＣＰＵコア５が、分割数以上あるかどうかを調べる。あれば、システム負荷監視部１３は、ステップＳ３０１１に進む。なければ、システム負荷監視部１３は、ステップＳ３０１７に進む。
ステップＳ３０１１で、システム負荷監視部１３は、ステップＳ１０１２〜Ｓ１０１６を実行する。
ステップＳ３０１２で、システム負荷監視部１３は、ステップＳ１０１５で記憶したＣＰＵコア５があるかどうかを調べる。あれば、システム負荷監視部１３は、ステップＳ３０１３に進む。ステップＳ１０１５で記憶したＣＰＵコア５がなければ、スレッド８がその計算機３に配置できないことを意味するので、システム負荷監視部１３は、ステップＳ３０１７に進む。
ステップＳ３０１３で、システム負荷監視部１３は、ステップＳ１０１８を実行する。
ステップＳ３０１４において、システム負荷監視部１３は、ステップＳ３００６で選択したプロセス７の新規起動スレッド８を配置するＣＰＵコア５が決定していなければ、ステップ３００９に戻り、他のスレッド８を動作させるＣＰＵコア５の決定処理を行う。決定していれば、システム負荷監視部１３は、ステップＳ３０１４に進む。
ステップＳ３０１５で、システム負荷監視部１３は、ステップＳ１０２０を行う。
ステップＳ３０１６で、システム負荷監視部１３は、全てのプロセス７のスレッド８の配置先が決定したかどうかを調べる。決定していれば、システム負荷監視部１３は、ステップＳ３００２に進む。決定していなければ、システム負荷監視部１３は、ステップＳ３００６に戻り、他のプロセス７のスレッド８を動作させる計算機３およびＣＰＵコア５を決定する。
【００７６】
ステップＳ３０１７において、システム負荷監視部１３は、パイプライン処理において、ステップＳ３００６で選択したプロセス７のデータ送信先となるプロセス７が動作する計算機３へのプロセス７の配置可能性を調べたかどうかを調べる。未調査であれば、システム負荷監視部１３は、ステップＳ３００６で選択したプロセス７のデータ送信先となるプロセス７が動作する計算機を選択し、ステップＳ３００８以降を実行する。調査済であれば、システム負荷監視部１３は、パイプライン処理において、自プロセスの前または後の処理を行うプロセス７と同一計算機３に配置するのを断念し、ステップ３０１７に進み、それ以外の計算機３に配置を試行する。
【００７７】
ステップＳ３０１７の動作は、ステップＳ２０１８で、自プロセスが動作している計算機３、ステップＳ３００１〜Ｓ３０１７で調査した計算機３以外の計算機３を選択すること以外は図１５のステップＳ２０１７と同じである。
【００７８】
以上説明した計算機リソース制御方式は、以下の特徴を加えることにより、分散処理におけるプロセス間の計算機間通信の所要時間を短縮させる。
・制限時間オーバーの原因となったプロセス７を、連携して処理を行う他の計算機３上のプロセス７と同一の計算機３の他ＣＰＵコア５に配置する。
【００７９】
このように、本実施の形態における計算機リソース制御方式では、制限時間超過の可能性がある場合に、その原因となるプロセス７を、パイプライン処理において、前後の処理を行うプロセス７と同一計算機３の他ＣＰＵコア５に配置することにより計算機間通信時間を短縮することができ、制限時間オーバーまでの時間を先延ばしにすることができる。
【００８０】
実施の形態４．
実施の形態４について、図１７を用いて説明する。
なお、実施の形態１〜実施の形態３と共通する部分については、同一の符号を付し、説明を省略する。
【００８１】
実施の形態１から実施の形態３では、パイプライン処理の処理時間が増加している際に、パイプライン処理の制限時間オーバーを防ぐために、制限時間オーバーの原因となっているプロセス７をスレッド８に分割することについて述べたが、本実施の形態は、パイプライン処理の処理時間が増加から短縮に転じたときに、実施の形態１から実施の形態３までの方式によって分散させた処理を集約させることについて述べる。
【００８２】
図９のフローチャートにおいて、パイプライン処理の処理時間が短縮傾向にある場合、パイプライン処理時間監視部１１は、そのパイプライン処理の処理時間の変動の監視を継続し、処理時間が一定になったときに、システム負荷監視部１３に、処理時間が減少傾向にあるパイプライン処理の識別子を通知する。すると、システム負荷監視部１３は、ステップＳ４において、処理の集約を行う。
【００８３】
図１７は、この実施の形態におけるシステム負荷監視部１３のステップＳ４の処理の詳細を示すフローチャート図である。
【００８４】
ステップＳ４００１において、システム負荷監視部１３は、パイプライン処理時間監視部１１から受信したパイプライン処理の識別子より、そのパイプライン処理を構成するプロセス７を調べる。
ステップＳ４００２で、システム負荷監視部１３は、ステップＳ４００１で抽出したプロセス７が動作する各計算機負荷監視部１０に、処理時間、ＣＰＵ時間が減少したプロセスと、処理時間、ＣＰＵ時間の変化に関する近似式、およびプロセス７の現在の分割数を調べるよう指示し、計算機負荷監視部１０からこれらの通知を受信し、記憶しておく。
ステップＳ４００３で、システム負荷監視部１３は、各パイプライン処理を構成するプロセス７のＣＰＵ時間の減少量、処理時間の減少量、および、パイプライン処理のピーク時から処理時間が一定になるまでの処理時間の減少量から、パイプライン処理の処理時間の減少量が、パイプライン処理を構成するプロセス７に原因があるのか、同一ＣＰＵコア５で動作する、より優先度の高い他のパイプライン処理を構成するスレッド８の処理時間が短くなったことによって処理時間が短くなったのか、を調査する。
調査の具体的な方式としては、例えば、システム負荷監視部１３は、パイプライン処理を構成するスレッド８のＣＰＵ時間の減少量とパイプライン処理の処理時間の減少量の差を求める。パイプライン処理の処理時間の減少量が各スレッドのＣＰＵ時間の減少量の和と同一であれば、システム負荷監視部１３は、処理時間が減少したパイプライン処理に属するスレッドのＣＰＵ時間が減少したことによって処理時間が短くなったことが考えられる。
なお、本実施の形態では、処理時間が減少した原因が自パイプライン処理を構成するプロセス７にあるパイプライン処理に対してのみ処理の集約を行うこととする。
【００８５】
ステップＳ４００３で、システム負荷監視部１３は、処理の集約を行うパイプライン処理の識別子を全て記憶する。
ステップＳ４００４で、システム負荷監視部１３は、ステップＳ４００３において記憶したパイプライン処理の全てについて、Ｓ４００５〜Ｓ４０１８を行ったかを調べる。行った場合、システム負荷監視部１３は、ステップＳ４を終了する。行っていなければ、システム負荷監視部１３は、パイプライン処理に属するプロセス７の集約に向けた処理を行う。
ステップＳ４００５で、システム負荷監視部１３は、まず、ステップＳ４００３で記憶したパイプライン処理から１つを選択する。
ステップＳ４００６で、システム負荷監視部１３は、ステップＳ４００５で選択したパイプライン処理を構成するプロセス中、ＣＰＵ時間がピークから減少し、一定になったプロセス７を選択する。
なお、本実施の形態では、ＣＰＵ時間が増加する前は１つのプロセスであったが、プロセス７が消費するＣＰＵ時間の増加により、複数の計算機３で複数のプロセス７に分割して処理を行っている可能性がある。この場合、システム負荷監視部１３は、同一処理を行うプロセス７を全て選択する。
ステップＳ４００７で、システム負荷監視部１３は、ステップＳ４００６で選択したプロセス群の総スレッド数を求める。
ステップＳ４００８で、システム負荷監視部１３は、ステップＳ４００６で選択したプロセス群の各スレッドが動作するＣＰＵコア５から、ステップＳ４００９で未選択のＣＰＵコア５があるかどうかを調べる。あれば、システム負荷監視部１３は、ステップＳ４００９に進む。
ステップＳ４００９で、システム負荷監視部１３は、ＣＰＵコア５を１つ選択する。
ステップＳ４０１０で、システム負荷監視部１３は、ステップＳ４００９で選択したＣＰＵコア５に集約可能なスレッド８の最大数を求める。例えば、分散配置されているスレッド８のうち１つを、ステップＳ４００９で選択したＣＰＵコア５のスレッド８に集約した場合、そのスレッド８のＣＰＵ時間、およびプロセスの処理時間は倍になる。また、２つのスレッドを１つのスレッドに集約した場合には、ＣＰＵ時間、プロセスの処理時間は３倍になる。スレッドを１つのＣＰＵコア５に集約した場合に、そのプロセス７が属するパイプライン処理が制限時間オーバーを起こさず、かつ、同一ＣＰＵコア５で動作するスレッド８が属するパイプライン処理が制限時間オーバーを起こさないような最大値を求める。本ステップ以降、集約処理後、処理を行うスレッド８を被集約スレッド、処理の集約により、処理が不要となるスレッド８を集約スレッドと呼ぶ。
【００８６】
ステップＳ４０１１で、システム負荷監視部１３は、ステップＳ４０１０で求めた最大値を過去に記憶した最大値と比較する。過去の最大値よりも大きければ、システム負荷監視部１３は、ステップＳ４０１２へ進む。
ステップＳ４０１２で、システム負荷監視部１３は、その最大値および、ステップＳ４００９で選択したＣＰＵコア５を記憶する。
システム負荷監視部１３は、ステップＳ４００９〜Ｓ４０１２を、全てのＣＰＵコア５について実施する。その後、システム負荷監視部１３は、ステップＳ４０１３に進む。
【００８７】
システム負荷監視部１３は、ステップＳ４０１３以降で、ステップＳ４０１２で記憶したＣＰＵコア５に、記憶した数のスレッド８を集約することとし、集約スレッドを選択する。選択の方式は、そのスレッド８がそのＣＰＵコア５で動作しなくなった場合に、空きＣＰＵ時間が最も大きくなるものから順に選択する。空きＣＰＵ時間とは、優先度が最低のスレッド８が動作した場合において、１周期の時間でどのスレッド８も動作していない時間のことである。そのＣＰＵコア５において、最も優先度の低いスレッドをｔｘ、スレッドｔｘの処理周期をＣ（ｔｘ）、ＣＰＵ時間をｃｐｕ（ｔｘ）とすると、数１３で求めることができる。
【００８８】
ステップＳ４０１３で、システム負荷監視部１３は、各集約スレッドが動作するＣＰＵコア５において、集約スレッドが不在になった場合の各ＣＰＵコア５の空きＣＰＵ時間を求める。
ステップＳ４０１４で、システム負荷監視部１３は、Ｓ４０１３で求めた各ＣＰＵコア５の空きＣＰＵ時間で、最も大きいものから順に、そのＣＰＵコア５で動作するスレッド８を集約スレッドとして決定する。
ステップＳ４０１５において、システム負荷監視部１３は、ステップＳ４０１０で記憶したスレッド８が動作する計算機３の計算機負荷監視部１０に、各集約スレッドが処理を担当していたデータの領域を通知する。そして、計算機負荷監視部１０は、スレッド割付部１２に、集約するスレッド数および集約スレッドが処理を担当していたデータ領域を通知する。これにより、ステップＳ４０１０で記憶したＣＰＵコア５で動作する非集約スレッドは、集約スレッドの処理も行う。ただし、この段階では、パイプライン処理において、集約スレッドのデータ送信先のプロセス７は、集約プロセスのデータのうち、もともと担当していたデータ領域のみを受信し、ステップＳ４０１５で新しく担当することとなった集約スレッドのデータの演算結果は破棄する。
ステップＳ４０１６で、システム負荷監視部１３は、Ｎ周期だけ時間が経過するのを待つ。Ｎ周期経過後、システム負荷監視部１３は、ステップＳ４０１７へ進む。
ステップＳ４０１７において、システム負荷監視部１３は、Ｓ４００６で選択したプロセス７のデータ送信先となるプロセス７に、集約スレッドが送信する全データを受信するよう指示する。
ステップＳ４０１８で、システム負荷監視部１３は、集約スレッドが動作する計算機の計算機負荷監視部１０に、集約スレッドを停止するよう指示する。計算機の計算機負荷監視部１０は、各ＣＰＵコア５のスレッド割付部１２に、スレッドを停止するよう指示する。スレッド割付部１２は、スレッド８を停止する。その後、システム負荷監視部１３は、ステップＳ４００４に戻り、Ｓ４００３で抽出した全てのパイプライン処理について、スレッド８の処理の集約処理が完了したかどうかを調べる。完了していれば、システム負荷監視部１３は、ステップＳ４を終了する。完了していなければ、システム負荷監視部１３は、ステップＳ４００５以降を行う。
【００８９】
以上説明した計算機リソース制御方式は、以下の特徴を加えることにより、プロセス７の処理時間が短縮傾向にある場合に処理を集約し、計算機リソース利用を効率化する。
・処理時間が短縮傾向にある分散処理において、処理時間短縮の原因となったプロセス７のスレッド８の数を、自プロセス７が属する処理およびシステム内の全ての処理が制限時間超過を発生させない数にまで集約する。
・スレッド８の集約により、他のスレッド８の処理を行うスレッド８が、処理をするために必要なデータを蓄積した後、処理集約に伴い不要となったスレッド８を停止させる。
【００９０】
このように、本実施の形態における計算機リソース制御方式では、パイプライン処理の処理時間が増加から短縮に転じた場合に、その原因となったプロセス７の処理を、自プロセスが属するパイプライン処理および他のパイプライン処理が制限時間超過を発生させない程度に集約することにより、計算機リソースの利用効率化を実現することができる。また、処理を集約した際に、これまで集約スレッドが行っていた処理を代行することとなった被集約スレッドの、代行処理箇所を、パイプライン処理の後段処理が十分に時間が経過してから採用することにより、演算結果の不整合を防ぐことを可能とする。
【００９１】
実施の形態５．
実施の形態５について、図１８〜図２８を用いて説明する。
なお、実施の形態１と共通する部分については、同一の符号を付し、説明を省略する。
【００９２】
図１８は、この実施の形態における計算機システム８００の全体構成の一例を示すシステム構成図である。
計算機システム８００は、複数の計算機８１０と、ネットワーク８２０とを有する。ネットワーク８２０は、複数の計算機８１０を相互に接続する。複数の計算機８１０は、ネットワーク８２０を介して通信する。
複数の計算機８１０のうち少なくともいずれかの計算機８１０は、計算機システム８００の外部からデータを入力する。複数の計算機８１０のうち少なくともいずれかの計算機８１０は、計算機システム８００の外部へデータを出力する。外部からデータを入力する計算機８１０と、外部へデータを出力する計算機８１０とは、同じ計算機８１０でもよいし、異なる計算機８１０でもよい。また、複数の計算機８１０が、外部からデータを入力し、あるいは、外部へデータを出力してもよい。
【００９３】
図１９は、この実施の形態における計算機８１０のハードウェア資源の一例を示すハードウェア構成図である。
計算機８１０は、１以上の処理装置９１１と、バス９１２と、記憶装置９１４と、入力装置９１５と、出力装置９１６とを有する。複数の計算機８１０それぞれが有する処理装置９１１の数は、同じ数であってもよいし、異なる数であってもよい。少なくともいずれかの計算機８１０は、複数の処理装置９１１を有する。
バス９１２は、処理装置９１１と、記憶装置９１４と、入力装置９１５と、出力装置９１６との間を接続する。処理装置９１１と、記憶装置９１４と、入力装置９１５と、出力装置９１６とは、バス９１２を介して通信する。
処理装置９１１は、プログラムを実行することにより、データを処理し、記憶装置９１４や入力装置９１５や出力装置９１６などを制御する。
記憶装置９１４は、処理装置９１１が実行するプログラムや、処理装置９１１が処理するデータなどを記憶する。計算機８１０が複数の処理装置９１１を有する場合、記憶装置９１４は、複数の処理装置９１１が共有している。すなわち、記憶装置９１４が記憶したデータは、いずれの処理装置９１１も読み出すことができ、いずれの処理装置９１１も、処理したデータを記憶装置９１４に記憶させることができる。記憶装置９１４は、ロック機能など、記憶したデータの整合性を保つための機能を持つ。記憶装置９１４は、例えば、半導体メモリ、フラッシュメモリ、磁気ディスク装置、光学ディスク装置などである。
入力装置９１５は、計算機システム８００の外部や他の計算機８１０など、計算機８１０の外部からデータや信号などの情報を入力する。入力装置９１５が信号など処理装置９１１が直接処理できない形式の情報を入力する場合、入力装置９１５は、入力した信号を、処理装置９１１が処理できるデータの形式に変換する。入力装置９１５が入力あるいは変換したデータは、処理装置９１１が直接処理してもよいし、記憶装置９１４が一時的あるいは恒久的に記憶してもよい。入力装置９１５は、例えば、他の計算機８１０や計算機システム８００の外部の装置などと通信する通信装置、カメラやスキャナなど画像を入力する画像入力装置、マイクなど音声を入力する音声入力装置、キーボードやマウスなど利用者の操作を入力する操作入力装置、アナログ信号を入力するアナログデジタル変換装置などである。
出力装置９１６は、計算機システム８００の外部や他の計算機８１０など、処理装置９１１が処理したデータや記憶装置９１４が記憶したデータ、あるいはこれらのデータを計算機８１０の外部に出力する形式に変換した信号などの情報を出力する。出力装置９１６は、例えば、他の計算機８１０や計算機システム８００の外部の装置などと通信する通信装置、ディスプレイやプリンタなど画像を出力する画像出力装置、スピーカなど音声を出力する音声出力装置、アナログ信号を出力するデジタルアナログ変換装置などである。
【００９４】
以下に説明する計算機システム８００の機能ブロックや、パイプライン処理の一部であるスレッドの処理は、いずれかの計算機８１０の記憶装置９１４が記憶したプログラムを、いずれかの処理装置９１１が実行することにより、実現される。
【００９５】
図２０は、この実施の形態におけるパイプライン処理８５０の一例を示す図である。
なお、同じ要素が複数ある場合、符号の後ろにアルファベットを付加して区別する場合がある。他の図においても同様である。
【００９６】
計算機システム８００は、１以上のパイプライン処理８５０を実行する。パイプライン処理８５０は、入力データ８６１を入力する。パイプライン処理８５０は、入力した入力データを処理して、処理結果を表わす結果データを生成する。パイプライン処理８５０は、生成した結果データを出力する。
パイプライン処理８５０は、直列関係にある複数のプロセス８５１からなる。例えば、パイプライン処理８５０ａは、５つのプロセス８５１ａ〜８５１ｅからなる。パイプライン処理８５０ｂは、４つのプロセス８５１ｆ〜８５１ｉからなる。
【００９７】
パイプライン処理８５０ａを構成する複数のプロセス８５１ａ〜８５１ｅのうち、最前段のプロセス８５１ａは、パイプライン処理８５０ａが入力した入力データ８６１ａを入力する。プロセス８５１ａは、入力した入力データ８６１ａを処理して、処理結果を表わす結果データ８６２ａを生成する。プロセス８５１ａは、生成した結果データ８６２ａを出力する。
二段目のプロセス８５１ｂは、最前段のプロセス８５１ａが出力した結果データ８６２ａを入力する。プロセス８５１ｂは、入力した結果データ８６２ａを処理して、処理結果を表わす結果データ８６２ｂを生成する。プロセス８５１ｂは、生成した結果データ８６２ｂを出力する。
以下同様に、後段のプロセス８５１は、前段のプロセス８５１が生成した結果データ８６２を処理して、結果データを生成する。
パイプライン処理８５０ａが出力する結果データは、最後段のプロセス８５１ｅが生成した結果データ８６２ｅである。
【００９８】
図２１は、この実施の形態におけるパイプライン処理８５０のタイミングの一例を示すタイミング図である。
横軸は、時刻を表わす。
【００９９】
パイプライン処理８５０は、所定の周期で繰り返し入力データ８６１を入力する。複数のパイプライン処理８５０が入力データ８６１を入力する周期は、同じ周期であってもよいし、異なる周期であってもよい。
パイプライン処理８５０が入力データ８６１を入力してから、結果データを出力するまでにかかった時間を、パイプライン処理時間８７１と呼ぶ。
パイプライン処理８５０において、後段のプロセス８５１は、前段のプロセス８５１の結果データを処理するから、前段のプロセス８５１の処理が終わってから、後段のプロセス８５１の処理が開始する。したがって、パイプライン処理時間８７１は、パイプライン処理８５０を構成する各プロセス８５１の処理時間の合計である。
また、処理が後段のプロセス８５１に移ったのち、前段のプロセス８５１は、次のデータ待ち状態になる。このため、パイプライン処理８５０は、ある入力データ８６１の処理が終わる前であっても、次の入力データ８６１の処理を開始することができる。
【０１００】
この実施の形態において、パイプライン処理８５０は、リアルタイム性が要求される処理をする。すなわち、パイプライン処理８５０は、入力データ８６１を入力してから、所定の制限時間８７２が経過する前に、結果データを出力することを要求される。なお、複数のパイプライン処理８５０の制限時間８７２は、同じ制限時間であってもよいし、異なる制限時間であってもよい。
【０１０１】
また、複数のパイプライン処理８５０の間には、優先順序が存在する。例えば、複数のパイプライン処理８５０が入力データ８６１を入力する周期が異なる場合、入力データ８６１を入力するタイミングが重なって、一時的に処理が追いつかなくなる場合がある。例えば、パイプライン処理８５０ｂの優先順位が、パイプライン処理８５０ａの優先順位より高い場合であれば、そのようなとき、パイプライン処理８５０ａの処理を待たせ、パイプライン処理８５０ｂの処理を優先して実行する。
【０１０２】
図２２は、この実施の形態におけるプロセス８５１の処理のタイミングの一例を示すタイミング図である。
横軸は、時刻を表わす。
【０１０３】
対象データ８６３は、プロセス８５１が入力するデータである。プロセス８５１がパイプライン処理８５０の最前段のプロセスである場合、対象データ８６３は、そのパイプライン処理８５０が入力した入力データ８６１である。プロセス８５１がそれ以外のプロセスである場合、対象データ８６３は、前段のプロセス８５１が出力した結果データ８６２である。
【０１０４】
少なくともいずれかのパイプライン処理８５０のいずれかのプロセス８５１において、各周期の処理８５２は、その周期で入力した対象データ８６３だけでなく、直前の所定の回数の周期で入力した対象データ８６３に基づいて実行される。例えば、処理８５２Ｃは、その周期で入力した対象データ８６３Ｃと、１つ前の周期で入力した対象データ８６３Ｂと、２つ前の周期で入力した対象データ８６３Ａとの３つの対象データ８６３に基づいて実行される。
プロセス８５１の処理８５２をするために必要となる対象データ８６３の数を「入力回数ｎ」と呼ぶ。入力回数ｎのプロセス８５１は、［ｎ−１］周期前の周期で入力した対象データ８６３から、今の周期で入力した対象データ８６３までのｎ個の対象データ８６３に基づいて、処理８５２を実行する。
【０１０５】
例えば、入力回数ｎが３である場合、プロセス８５１が起動した第一回目の周期では、その周期で入力した対象データ８６３Ａしかないので、第一回目の処理８５２Ａは、実行できない。あるいは、第一回目の処理８５２Ａを実行したとしても、その結果として生成する結果データ８６２Ａは、正しい処理結果ではない。プロセス８５１は、後の周期の処理８５２のため、対象データ８６３Ａを記憶しておく。
第二回目の周期では、その周期で入力した対象データ８６３Ｂと、第一回目の周期で記憶しておいた対象データ８６３Ａとがあるが、２つ前の周期の対象データ８６３がないので、第二回目の処理８５２Ｂも、実行できない。あるいは、第二回目の処理８５２Ｂを実行したとしても、その結果として生成する結果データ８６２Ｂは、正しい処理結果ではない。プロセス８５１は、後の周期の処理８５２のため、対象データ８６３Ｂを記憶しておく。
第三回目の周期になると、その周期で入力した対象データ８６３Ｃと、第二回目の周期で記憶しておいた１つ前の対象データ８６３Ｂと、第一回目の周期で記憶しておいた２つ前の対象データ８６３Ａとが揃うので、処理８５２Ｃを実行できる。プロセス８５１は、処理８５２Ｃを実行して、結果データ８６２Ｃを生成する。また、プロセス８５１は、後の周期のため、対象データ８６３Ｃを記憶しておく。
それ以降の周期では、同様に３つの対象データ８６３が揃うので、プロセス８５１は、処理８５２を実行して、結果データ８６２を生成する。また、プロセス８５１は、後の周期のため、対象データ８６３を記憶しておく。
【０１０６】
なお、複数のプロセス８５１の入力回数ｎは、同じ入力回数であってもよいし、異なる入力回数であってもよい。各パイプライン処理８５０のすべてのプロセス８５１のうち、最も入力回数ｎが多いプロセス８５１の入力回数を「最大入力回数ｎｍａｘ」と呼ぶ。
【０１０７】
図２３は、この実施の形態におけるプロセス８５１の処理８５２の構成の一例を示す図である。
【０１０８】
１つのプロセス８５１の１回の処理８５２は、複数の部分処理８５３ａ〜８５３ｄに分けることができる。各部分処理８５３ａ〜８５３ｄは、並列関係にあり、各部分処理８５３ａ〜８５３ｄの間には、依存関係がない。すなわち、各部分処理８５３ａ〜８５３ｄは、他の部分処理が処理した処理結果を利用することなく、プロセス８５１が入力した対象データ８６３を処理して、結果データ８６２の一部を生成する。プロセス８５１の結果データ８６２は、各部分処理８５３ａ〜８５３ｄが生成した結果データ８６２の一部を結合することにより、生成することができる。
【０１０９】
このような処理の一例としては、例えば、共通鍵による暗号化処理および復号処理や、画像に所定の視覚効果を加えるフィルタ処理などがある。
例えば、共通鍵による暗号化処理および復号処理では、データを共通鍵と同じ長さのブロックに分割して、分割したブロックごとに、共通鍵との間でビットごとの排他的論理和を取る。排他的論理和を取ったブロックを結合して、暗号化もしくは復号したデータを生成する。したがって、この処理は、ブロックの長さの整数倍ごとにデータを分割することにより、部分処理に分けることができる。
また、例えば、画像にソフトフォーカスやエンボスなどの視覚効果を加えるフィルタ処理では、各画素の近傍に位置する画素の色や輝度などに基づいて、その画素の色や輝度などを算出する。したがって、この処理は、画像を複数に分割することにより、部分処理に分けることができる。ただし、分割された画像の境界付近では、隣の画像の画素のデータを必要とする場合がある。このため、各部分処理が入力する画像は、担当する部分だけでなく、隣接する部分の少なくとも一部を含む。
【０１１０】
図２４は、この実施の形態におけるスレッド８５４の構成の一例を示す図である。
【０１１１】
スレッド８５４は、処理装置９１１が処理を実行する単位である。処理装置９１１は、スレッド８５４として処理を実行する。
１つのプロセス８５１の処理８５２を４つの部分処理８５３ａ〜８５３ｄに分けた場合、それに対応して、４つのスレッド８５４ａ〜８５４ｄが起動される。４つのスレッド８５４ａ〜８５４ｄのうちの１つ（スレッド８５４ａ）は、そのプロセス８５１の主スレッドであり、残りの３つのスレッド８５４ｂ〜８５４ｄは、そのプロセス８５１の従スレッドである。
【０１１２】
主スレッド８５４ａを実行する処理装置９１１は、主スレッド８５４ａに割り当てられた部分処理８５３ａのほかに、対象データ入力処理８８１、対象データ通知処理８８２、結果データ取得処理８８５、結果データ結合処理８８６、結果データ出力処理８８７などの処理を実行する。
従スレッド８５４ｂ〜８５４ｄを実行する処理装置９１１は、従スレッド８５４ｂ〜８５４ｄにそれぞれ割り当てられた部分処理８５３ｂ〜８５３ｄのほかに、対象データ取得処理８８３、結果データ通知処理８８４などの処理を実行する。
【０１１３】
対象データ入力処理８８１は、主スレッド８５４ａが、そのプロセス８５１の代表として、対象データ８６３を入力する処理である。
対象データ通知処理８８２は、主スレッド８５４ａが、対象データ入力処理８８１で入力した対象データ８６３を、従スレッド８５４ｂ〜８５４ｄに通知する処理である。なお、対象データ入力処理８８１で入力した対象データ８６３全部を通知してもよいし、各従スレッド８５４ｂ〜８５４ｄが必要とする部分のみを通知してもよい。
【０１１４】
対象データ取得処理８８３は、従スレッド８５４ｂ〜８５４ｄが、対象データ通知処理８８２で主スレッド８５４が通知した対象データ８６３（の一部）を取得する処理である。
結果データ通知処理８８４は、従スレッド８５４ｂ〜８５４ｄが、部分処理８５３ｂ〜８５３ｄで生成した結果データ８６２の一部を、主スレッド８５４ａに通知する処理である。
【０１１５】
結果データ取得処理８８５は、主スレッド８５４ａが、結果データ通知処理８８４で従スレッド８５４ｂ〜８５４ｄが通知した結果データ８６２の一部を取得する処理である。
結果データ結合処理８８６は、主スレッド８５４ａが、部分処理８５３ａで生成した結果データ８６２の一部と、結果データ取得処理８８５で取得した結果データ８６２の一部とを結合して、結果データ８６２を生成する処理である。
結果データ出力処理８８７は、主スレッド８５４ａが、そのプロセス８５１の代表として、生成した結果データ８６２を出力する処理である。
【０１１６】
なお、１つのプロセス８５１につき、１つの主スレッドを設けるのではなく、２つの主スレッドを設ける構成としてもよい。２つの主スレッドのうちの１つは、対象データ入力処理８８１や対象データ通知処理８８２など入力側の処理を担当する。もう一つの主スレッドは、結果データ取得処理８８５や結果データ結合処理８８６や結果データ出力処理８８７など出力側の処理を担当する。
【０１１７】
対象データ通知処理８８２、対象データ取得処理８８３、結果データ通知処理８８４、結果データ取得処理８８５の具体的な内容は、主スレッド８５４ａを実行する処理装置９１１と、従スレッド８５４ｂ〜８５４ｄを実行する処理装置９１１との関係によって異なる。
主スレッド８５４ａを実行する処理装置９１１と、従スレッド８５４を実行する処理装置９１１とが、同じ計算機８１０の処理装置９１１である場合、通知されるべきデータは、その計算機８１０の記憶装置９１４が既に記憶している。したがって、対象データ通知処理８８２や結果データ通知処理８８４では、データが出来たことを単に通知するだけでよい。対象データ取得処理８８３や結果データ取得処理８８５は、その通知を受けて、記憶装置９１４からデータを読み出す。
これに対し、主スレッド８５４ａを実行する処理装置９１１と、従スレッド８５４を実行する処理装置９１１とが、異なる計算機８１０の処理装置９１１である場合、通知側の処理装置９１１は、出力装置９１６（通信装置）を用いて、ネットワーク８２０を介して、通知されるべきデータを送信し、取得側の処理装置９１１は、入力装置９１５（通信装置）を用いて、送信されたデータを受信する必要がある。
したがって、プロセス８５１の主スレッド８５４ａと、従スレッド８５４ｂ〜８５４ｄとを、同じ計算機８１０の処理装置９１１が実行するほうが、異なる計算機８１０の処理装置９１１が実行するよりも、処理装置９１１の間の通信処理の負荷が減り、効率がよい。
【０１１８】
対象データ入力処理８８１や結果データ出力処理８８７の具体的な内容も、同様に、前段のプロセス８５１の主スレッド８５４を実行する処理装置９１１と、後段のプロセス８５１の主スレッド８５４を実行する処理装置９１１との関係によって異なる。
前段のプロセス８５１の主スレッド８５４を実行する処理装置９１１と、後段のプロセス８５１の主スレッド８５４を実行する処理装置９１１とが同じ計算機８１０の処理装置９１１である場合、前段のプロセス８５１の主スレッド８５４ａの結果データ出力処理８８７は、データが出来たことを単に通知するだけでよい。後段のプロセス８５１の主スレッド８５４ａの対象データ入力処理８８１は、その通知を受けて、記憶装置９１４からデータを読み出す。
これに対し、前段のプロセス８５１の主スレッド８５４を実行する処理装置９１１と、後段のプロセス８５１の主スレッド８５４を実行する処理装置９１１とが異なる計算機８１０の処理装置９１１である場合、出力側の処理装置９１１は、出力装置９１６（通信装置）を用いて、ネットワーク８２０を介して、出力すべきデータを送信し、入力側の処理装置９１１は、入力装置９１５（通信装置）を用いて、送信されたデータを受信する必要がある。
したがって、前段のプロセス８５１の主スレッド８５４ａと、後段のプロセス８５１の主スレッド８５４ａとを、同じ計算機８１０の処理装置９１１が実行するほうが、異なる計算機８１０の処理装置９１１が実行するよりも、処理装置９１１間の通信処理の負荷が減り、効率がよい。
【０１１９】
なお、１つのプロセス８５１の処理８５２を分割せず、１つのスレッド８５４で実行してもよい。その場合、対象データ通知処理８８２、対象データ取得処理８８３、結果データ通知処理８８４、結果データ取得処理８８５が不要になるので、効率がよい。
【０１２０】
１つの処理装置９１１は、複数のスレッド８５４を実行することができる。しかし、１つのプロセス８５１の複数のスレッド８５４は、それぞれ異なる処理装置９１１が実行するほうがよい。同じ処理装置９１１が、１つのプロセス８５１の複数のスレッド８５４を実行すると、処理の負荷が分散されないので、処理８５２を複数の部分処理８５３に分けた意義が失われる。それどころか、対象データ通知処理８８２、対象データ取得処理８８３、結果データ通知処理８８４、結果データ取得処理８８５が必要になる分、処理の効率が落ちる。
【０１２１】
図２５は、この実施の形態における計算機システム８００の機能ブロックの構成の一例を示すブロック構成図である。
計算機システム８００は、スレッド実行部１１１と、スレッド管理部１１２と、スレッド開始時刻取得部１２１と、スレッド終了時刻取得部１２２と、プロセス開始時刻算出部１２５と、プロセス終了時刻算出部１２６と、プロセス処理時間算出部１３１と、パイプライン処理時間算出部１３２と、パイプライン処理時間予測部１３３と、制限時間超過判定部１４１と、分割プロセス選択部１４２と、空き処理装置選択部１４３と、スレッド起動部１４４と、他計算機処理装置選択部１４５と、他計算機スレッド起動部１４６と、移動プロセス終了部１４７と、処理時間短縮判定部１５１と、分割済プロセス選択部１５２と、終了スレッド選択部１５３と、スレッド終了部１５４とを有する。
上述したように、これらの機能ブロックは、処理装置９１１がプログラムを実行することにより実現される。スレッド実行部１１１以外の機能ブロックを実現する処理装置９１１は、いずれの計算機８１０のいずれの処理装置９１１であってもよい。例えば、スレッド実行部１１１以外のすべての機能ブロックを、１つの処理装置９１１が実現してもよい。あるいは、すべての処理装置９１１に、処理の負荷が均等になるよう、機能ブロックを分散して配置してもよい。また、１つの機能ブロックを、複数の処理装置９１１が分担して実現してもよい。
【０１２２】
スレッド実行部１１１は、割り当てられた処理装置９１１を用いて、スレッド８５４を実行する。
【０１２３】
スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１が実行するスレッド８５４を管理する。
例えば、スレッド管理部１１２は、記憶装置９１４を用いて、どの計算機８１０のどの処理装置９１１が、どのパイプライン処理８５０のどのプロセス８５１のどのスレッド８５４を実行しているかを表わすスレッド管理テーブルを記憶している。スレッド管理部１１２は、後述するスレッド起動部１４４などからの指示にしたがい、処理装置９１１を用いて、スレッド実行部１１１に対して、スレッド８５４の起動・終了などを指示するとともに、記憶したスレッド管理テーブルを更新する。
【０１２４】
スレッド開始時刻取得部１２１は、処理装置９１１を用いて、各パイプライン処理８５０の各周期において、スレッド実行部１１１が実行する各スレッド８５４の処理が開始した時刻を取得する。スレッド開始時刻取得部１２１は、記憶装置９１４を用いて、取得した時刻を記憶する。
スレッド終了時刻取得部１２２は、処理装置９１１を用いて、各パイプライン処理８５０の各周期において、スレッド実行部１１１が実行する各スレッド８５４の処理が終了した時刻を取得する。スレッド終了時刻取得部１２２は、記憶装置９１４を用いて、取得した時刻を記憶する。
【０１２５】
プロセス開始時刻算出部１２５は、処理装置９１１を用いて、スレッド開始時刻取得部１２１が記憶した時刻に基づいて、各パイプライン処理８５０の各周期において、各プロセス８５１の処理が開始した時刻を算出する。プロセス開始時刻算出部１２５は、記憶装置９１４を用いて、算出した時刻を記憶する。
例えば、プロセス開始時刻算出部１２５は、処理装置９１１を用いて、スレッド管理部１１２が記憶したスレッド管理テーブルに基づいて、各プロセスの主スレッドを判定する。プロセス開始時刻算出部１２５は、記憶装置９１４を用いて、判定した主スレッドについて、スレッド開始時刻取得部１２１が取得した時刻を、そのプロセス８５１の処理が開始した時刻として記憶する。
あるいは、プロセス開始時刻算出部１２５は、処理装置９１１を用いて、あるプロセス８５１の各スレッド８５４についてスレッド開始時刻取得部１２１が取得した時刻のなかから、最も早い時刻を判定する。プロセス開始時刻算出部１２５は、記憶装置９１４を用いて、判定した時刻を、そのプロセス８５１の処理が開始した時刻として記憶する。
【０１２６】
プロセス終了時刻算出部１２６は、処理装置９１１を用いて、スレッド終了時刻取得部１２２が記憶した時刻に基づいて、各パイプライン処理８５０の各周期において、各プロセス８５１の処理が終了した時刻を算出する。プロセス終了時刻算出部１２６は、記憶装置９１４を用いて、算出した時刻を記憶する。
例えば、プロセス終了時刻算出部１２６は、処理装置９１１を用いて、スレッド管理部１１２が記憶したスレッド管理テーブルに基づいて、各プロセスの主スレッドを判定する。プロセス開始時刻算出部１２５は、記憶装置９１４を用いて、判定した主スレッドについて、スレッド終了時刻取得部１２２が取得した時刻を、そのプロセス８５１の処理が終了した時刻として記憶する。
あるいは、プロセス終了時刻算出部１２６は、処理装置９１１を用いて、あるプロセス８５１の各スレッド８５４についてスレッド終了時刻取得部１２２が取得した時刻のなかから、最も遅い時刻を判定する。プロセス終了時刻算出部１２６は、記憶装置９１４を用いて、判定した時刻を、そのプロセス８５１の処理が終了した時刻として記憶する。
【０１２７】
プロセス処理時間算出部１３１は、処理装置９１１を用いて、プロセス開始時刻算出部１２５が記憶した時刻と、プロセス終了時刻算出部１２６が記憶した時刻とに基づいて、各パイプライン処理８５０の各周期において、各プロセス８５１の処理にかかった時間を算出する。プロセス処理時間算出部１３１は、記憶装置９１４を用いて、算出した時間を記憶する。
例えば、プロセス処理時間算出部１３１は、処理装置９１１を用いて、あるプロセス８５１についてプロセス終了時刻算出部１２６が算出した時刻から、プロセス開始時刻算出部１２５が算出した時刻を差し引いた差を計算する。プロセス処理時間算出部１３１は、記憶装置９１４を用いて、計算した差を、そのプロセス８５１の処理にかかった時間として記憶する。
【０１２８】
パイプライン処理時間算出部１３２は、処理装置９１１を用いて、プロセス開始時刻算出部１２５が記憶した時刻と、プロセス終了時刻算出部１２６が記憶した時刻とに基づいて、各パイプライン処理８５０の各周期において、パイプライン処理８５０にかかったパイプライン処理時間８７１を算出する。パイプライン処理時間算出部１３２は、記憶装置９１４を用いて、算出したパイプライン処理時間８７１を記憶する。
例えば、パイプライン処理時間算出部１３２は、処理装置９１１を用いて、あるパイプライン処理８５０の最後段のプロセス８５１についてプロセス終了時刻算出部１２６が算出した時刻から、最前段のプロセス８５１についてプロセス開始時刻算出部１２５が算出した時刻を差し引いた差を計算する。パイプライン処理時間算出部１３２は、記憶装置９１４を用いて、計算した差を、そのパイプライン処理８５０のパイプライン処理時間８７１として記憶する。
あるいは、パイプライン処理時間算出部１３２は、処理装置９１１を用いて、あるパイプライン処理８５０の各プロセス８５１についてプロセス開始時刻算出部１２５が算出した時刻のなかから、最も早い時刻を判定して、そのパイプライン処理８５０の開始時刻とする。パイプライン処理時間算出部１３２は、処理装置９１１を用いて、そのパイプライン処理８５０の各プロセス８５１についてプロセス終了時刻算出部１２６が算出した時刻のなかから、最も遅い時刻を判定して、そのパイプライン処理８５０の終了時刻とする。パイプライン処理時間算出部１３２は、処理装置９１１を用いて、判定したパイプライン処理８５０の終了時刻から、判定したパイプライン処理８５０の開始時刻を差し引いた差を計算する。パイプライン処理時間算出部１３２は、記憶装置９１４を用いて、計算した差を、そのパイプライン処理８５０のパイプライン処理時間８７１として記憶する。
【０１２９】
パイプライン処理時間予測部１３３は、処理装置９１１を用いて、パイプライン処理時間算出部１３２が記憶したパイプライン処理時間８７１に基づいて、各パイプライン処理８５０について、将来の周期におけるパイプライン処理時間８７１を予測する。パイプライン処理時間予測部１３３は、記憶装置９１４を用いて、予測したパイプライン処理時間８７１を記憶する。
例えば、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、パイプライン処理時間８７１の変化を直線で近似する。例えば、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、重み付き最小二乗法により、パイプライン処理時間８７１の変化を近似する直線の傾きや切片を算出する。パイプライン処理時間予測部１３３は、処理装置９１１を用いて、パイプライン処理時間８７１の変化を近似する直線を外挿して、将来の周期におけるパイプライン処理時間８７１を予測する。
あるいは、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、カルマンフィルタにより、将来の周期におけるパイプライン処理時間８７１を予測するための計算式の係数を推定する構成であってもよい。例えば、パイプライン処理時間８７１が等差級数的あるいは等比級数的に変化すると仮定して、時間推移モデルを作る。パイプライン処理時間８７１のバラツキは、観測誤差として捉える。
【０１３０】
パイプライン処理時間予測部１３３がパイプライン処理時間８７１を予測する将来の周期が、現在の周期から数えてｍ周期後であるとする。ｍを「予測周期」と呼ぶ。パイプライン処理時間予測部１３３は、そのパイプライン処理８５０の最大入力回数ｎｍａｘよりも大きい予測周期ｍについて、パイプライン処理時間８７１を予測する。
【０１３１】
制限時間超過判定部１４１は、処理装置９１１を用いて、パイプライン処理時間予測部１３３が予測したパイプライン処理時間８７１に基づいて、各パイプライン処理８５０のパイプライン処理時間８７１が増加傾向にある場合、ｍ周期後に制限時間８７２を超過するか否かを判定する。
【０１３２】
分割プロセス選択部１４２は、制限時間超過判定部１４１の判定結果に基づいて、あるパイプライン処理８５０のパイプライン処理時間８７１がｍ周期後に制限時間８７２を超過する場合、処理装置９１１を用いて、そのパイプライン処理８５０のプロセス８５１のなかから、分割するプロセスを選択する。分割プロセス選択部１４２は、処理装置９１１を用いて、選択したプロセスを記憶する。
「プロセスを分割する」とは、プロセス８５１の処理８５２を複数の部分処理８５３に分割して、処理の負荷を分散させることである。また、プロセスが既に分割済である場合には、分割数を増やして、処理の負荷を更に分散させることである。
【０１３３】
上述したように、パイプライン処理時間８７１は、各プロセス８５１の処理時間の合計である。したがって、パイプライン処理時間８７１の増加は、少なくともいずれかのプロセス８５１の処理時間の増加に原因がある。
【０１３４】
例えば、分割プロセス選択部１４２は、処理装置９１１を用いて、パイプライン処理時間８７１がｍ周期後に制限時間８７２を超過すると制限時間超過判定部１４１が判定したパイプライン処理８５０を構成するすべてのプロセス８５１について、プロセス処理時間算出部１３１が算出した時間に基づいて、そのプロセス８５１の処理時間が増加傾向にあるか減少傾向にあるか、増加傾向や減少傾向の強さなどを判定する。例えば、分割プロセス選択部１４２は、処理装置９１１を用いて、プロセス８５１の処理時間の変化を直線で近似する。例えば、分割プロセス選択部１４２は、処理装置９１１を用いて、重み付き最小二乗法により、プロセス８５１の処理時間の変化を近似する直線の傾きを算出する。分割プロセス選択部１４２が算出した直線の傾きが正であれば増加傾向、負であれば減少傾向を表わし、その絶対値は、増加傾向や減少傾向の強さを表わす。
分割プロセス選択部１４２は、処理装置９１１を用いて、パイプライン処理時間８７１がｍ周期後に制限時間８７２を超過すると制限時間超過判定部１４１が判定したパイプライン処理８５０を構成するすべてのプロセス８５１のなかから、処理時間の増加傾向が最も強いプロセス８５１を、分割するプロセスとして選択する。
【０１３５】
あるいは、分割プロセス選択部１４２は、分割による効果を加味して、分割するプロセスを選択する構成であってもよい。
例えば、分割されていないプロセスを２つに分割すれば、各部分処理８５３の負荷は半分になる。したがって、プロセス８５１の処理時間は、最高で半分に縮まることが期待できる。これに対し、２つに分割されているプロセスの分割数を３つに増やすと、各部分処理８５３の負荷は３分の２になる。したがって、プロセス８５１の処理時間は、最高でも３分の１しか縮まらない。すなわち、プロセスの処理時間をｔ、現在の分割数をｋ、分割数の増加数をΔｋとすると、プロセス８５１の処理時間は、最高で［ｔ・Δｋ／（ｋ＋Δｋ）］縮まる可能性がある。
例えば、分割プロセス選択部１４２は、処理装置９１１を用いて、パイプライン処理時間８７１がｍ周期後に制限時間８７２を超過すると制限時間超過判定部１４１が判定したパイプライン処理８５０を構成するプロセス８５１のうち、処理時間が増加傾向にあるすべてのプロセスについて、プロセスを分割することにより処理時間がどれだけ縮まるかを算出する。分割プロセス選択部１４２は、処理装置９１１を用いて、算出した減少量が最も大きいプロセス８５１を、分割するプロセスとして選択する。
【０１３６】
あるいは、分割プロセス選択部１４２は、ＣＰＵ時間を加味して、分割するプロセスを選択する構成であってもよい。
ＣＰＵ時間とは、処理装置９１１が実際にそのスレッド８５４の処理を実行するのにかかった時間のことである。処理装置９１１が複数のスレッド８５４を実行している場合、実際に、処理装置９１１が一度に実行できるスレッド８５４は一つだけであり、時分割により、複数のスレッド８５４を並行して実行する。例えば、優先度の低いパイプライン処理８５０のスレッド８５４は、優先度の高いパイプライン処理８５０のスレッド８５４を処理装置９１１が実行している間、待たされることになる。したがって、プロセス８５１の処理時間には、処理装置９１１がそのプロセス８５１のスレッド８５４を実行していた時間と、処理装置９１１が他のプロセス８５１のスレッド８５４を実行していた時間とが含まれる。プロセス８５１の処理時間が増加傾向にある場合、そのプロセスの処理の負荷が増加することによりＣＰＵ時間が増加している場合と、他のプロセスの処理の負荷が増加したことの影響によるものでＣＰＵ時間はあまり増加していない場合とがある。
例えば、分割プロセス選択部１４２は、処理装置９１１は、パイプライン処理時間８７１がｍ周期後に制限時間８７２を超過すると制限時間超過判定部１４１が判定したパイプライン処理８５０を構成するプロセス８５１のうち、処理時間が増加傾向にあるプロセスのなかから、ＣＰＵ時間の増加傾向が最も強いプロセス８５１を、分割するプロセスとして選択する。
【０１３７】
空き処理装置選択部１４３は、処理装置９１１を用いて、分割プロセス選択部１４２が選択したプロセス８５１について、新たに起動するスレッド８５４を実行する処理装置９１１を選択する。空き処理装置選択部１４３は、処理装置９１１を用いて、そのプロセス８５１の主スレッド８５４を実行している処理装置９１１と同じ計算機８１０の処理装置９１１のなかから、同じプロセス８５１のスレッド８５４を実行していない処理装置９１１を選択する。
【０１３８】
なお、同じプロセス８５１のスレッド８５４を実行していない処理装置９１１であっても、同じパイプライン処理８５０の別のプロセス８５１のスレッド８５４を実行している処理装置９１１に新たに起動するスレッド８５４を実行させると、負荷分散の皺寄せが、同じパイプライン処理８５０の別のプロセス８５１に出ることになり、パイプライン処理８５０のパイプライン処理時間８７１を短縮させることに繋がらない可能性がある。
このため、空き処理装置選択部１４３は、同じプロセス８５１のスレッド８５４を実行していない処理装置９１１であっても、同じパイプライン処理８５０の別のプロセス８５１のスレッド８５４を実行している場合には、選択しない構成であってもよい。
【０１３９】
また、既に処理の負荷が大きい処理装置９１１に新たに起動するスレッド８５４を実行させると、処理装置９１１がもっと優先度が高いパイプライン処理８５０のスレッド８５４の実行に追われて、新たに起動したスレッド８５４の実行時間を確保できない可能性がある。逆に、新たに起動したスレッド８５４の実行時間を確保した結果、もっと優先度が低いパイプライン処理８５０のスレッド８５４の実行時間を確保できなくなり、もっと優先度が低いパイプライン処理８５０のパイプライン処理時間８７１が増加して制限時間８７２を超過する可能性がある。
このため、空き処理装置選択部１４３は、処理装置９１１を用いて、選択した処理装置９１１のＣＰＵ時間を算出し、新たに起動するスレッド８５４を実行する余裕があるか否かを判定する。新たに起動するスレッド８５４を実行する余裕がないと判定した場合、空き処理装置選択部１４３は、処理装置９１１を用いて、その処理装置９１１の選択を撤回する。
【０１４０】
スレッド起動部１４４は、空き処理装置選択部１４３が処理装置９１１を選択した場合、処理装置９１１を用いて、分割プロセス選択部１４２が選択したプロセス８５１のスレッド８５４を新たに起動して、空き処理装置選択部１４３が選択した処理装置９１１に実行させる。
例えば、スレッド起動部１４４は、処理装置９１１を用いて、新たに起動するスレッド８５４を実行する処理装置９１１や、新たに起動するスレッド８５４がどのパイプライン処理８５０のどのプロセス８５１のものであるかなどの情報を含む指示を、スレッド管理部１１２に通知する。スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、新たなスレッド８５４の起動を指示する。
【０１４１】
また、新たなスレッド８５４の起動により、同じプロセス８５１の他のスレッド８５４が処理すべき部分処理８５３の範囲が変わるので、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、同じプロセス８５１の主スレッドや他の従スレッドの部分処理８５３の範囲の変更を指示する。
【０１４２】
そのプロセス８５１の主スレッドを実行している処理装置９１１と同じ計算機８１０で、新たなスレッド８５４を起動する場合、その計算機８１０の記憶装置９１４は、そのプロセス８５１の対象データ８６３を、既に蓄積している。このため、新たに起動するスレッド８５４は、すぐに処理を開始することができ、正しい結果データ８６２を生成する。
スレッド管理部１１２は、処理装置９１１を用いて、新たに起動したスレッド８５４を、そのプロセス８５１の処理にすぐに参入させる。スレッド管理部１１２は、処理装置９１１を用いて、すぐに、同じプロセス８５１の他のスレッド８５４の部分処理８５３を変更する。
【０１４３】
他計算機処理装置選択部１４５は、空き処理装置選択部１４３が選択できる処理装置９１１がない場合、処理装置９１１を用いて、そのプロセス８５１の主スレッド８５４を実行している処理装置９１１と異なる計算機８１０の処理装置９１１のなかから、新たに起動するスレッド８５４を実行する処理装置９１１を選択する。他計算機処理装置選択部１４５は、記憶装置９１４を用いて、選択した処理装置９１１を記憶する。
【０１４４】
上述したように、同じプロセス８５１の主スレッドと従スレッドとは、同じ計算機８１０の処理装置９１１が実行するほうがよい。このため、他計算機処理装置選択部１４５は、プロセス８５１のスレッド８５４をまるごと別の計算機８１０に移動しようとする。他計算機処理装置選択部１４５は、増加数の処理装置９１１だけでなく、増加した分割数の処理装置９１１を選択しようとする。
また、上述したように、前段のプロセス８５１の主スレッドと、後段のプロセス８５１の主スレッドとは、同じ計算機８１０の処理装置９１１が実行するほうがよい。このため、他計算機処理装置選択部１４５は、可能であれば、そのプロセス８５１の前段または後段のプロセスの主スレッドを実行している処理装置９１１と同じ計算機８１０の処理装置９１１を選択する。
【０１４５】
例えば、他計算機処理装置選択部１４５は、処理装置９１１を用いて、そのプロセス８５１の前段のプロセスの主スレッドを実行している処理装置９１１の計算機８１０を選択する。
他計算機処理装置選択部１４５は、処理装置９１１を用いて、選択した計算機８１０の処理装置９１１を選択する。なお、同じパイプライン処理８５０の他のプロセス８５１のスレッド８５４を実行している処理装置９１１や、新たに起動するスレッドを実行する余裕がない処理装置９１１を除外する点は、空き処理装置選択部１４３と同様である。
増加した分割数以上の処理装置９１１が選択できた場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、増加した分割数の処理装置９１１を残し、それ以外の処理装置９１１の選択を撤回する。
増加した分割数の処理装置９１１を選択できない場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、処理装置９１１の選択をすべて撤回する。他計算機処理装置選択部１４５は、処理装置９１１を用いて、そのプロセス８５１の後段のプロセスの主スレッドを実行している処理装置９１１の計算機８１０を選択する。他計算機処理装置選択部１４５は、処理装置９１１を用いて、選択した計算機８１０で、増加した分割数の処理装置９１１を選択しようとする。
それもできない場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、それ以外の計算機８１０を順に１つずつ選択し、選択した計算機８１０で、増加した分割数の処理装置９１１を選択しようとする。
【０１４６】
いずれの計算機８１０でも、増加した分割数の処理装置９１１を選択できない場合、他計算機処理装置選択部１４５は、そのプロセス８５１のスレッド８５４全部を移動させるのを断念し、元のスレッド８５４を残したまま、増加数分のスレッド８５４だけを別の計算機８１０の処理装置９１１に実行させることにする。
例えば、他計算機処理装置選択部１４５は、処理装置９１１を用いて、そのプロセス８５１の主スレッドを実行している処理装置９１１の計算機８１０と異なる計算機８１０のなかに、そのプロセス８５１の従スレッドを実行している処理装置９１１の計算機８１０があれば、その計算機８１０を選択する。他計算機処理装置選択部１４５は、処理装置９１１を用いて、選択した計算機８１０で、増加数の処理装置９１１を選択しようとする。
それができない場合や、そのプロセス８５１の主スレッドを実行している処理装置９１１の計算機８１０と異なる計算機８１０のなかに、そのプロセス８５１の従スレッドを実行している処理装置９１１の計算機８１０がない場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、それ以外の計算機８１０を順に１つずつ選択し、選択した計算機８１０で、増加数の処理装置９１１を選択しようとする。
【０１４７】
他計算機スレッド起動部１４６は、処理装置９１１を用いて、分割プロセス選択部１４２が選択したプロセス８５１のスレッド８５４を新たに起動して、他計算機処理装置選択部１４５が選択した処理装置９１１に実行させる。
例えば、他計算機スレッド起動部１４６は、処理装置９１１を用いて、新たに起動するスレッド８５４を実行する処理装置９１１や、新たに起動するスレッド８５４がどのパイプライン処理８５０のどのプロセス８５１のものであるかなどの情報を含む指示を、スレッド管理部１１２に通知する。スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、新たなスレッド８５４の起動を指示する。
【０１４８】
そのプロセス８５１のスレッド８５４を実行していた処理装置９１１がない計算機８１０で、新たなスレッド８５４を起動する場合、その計算機８１０の記憶装置９１４は、そのプロセス８５１の対象データ８６３が蓄積されていない。このため、新たに起動するスレッド８５４は、すぐに処理を開始することはできず、入力回数ｎの対象データ８６３が蓄積されるまで、正しい結果データ８６２を生成することができない。
スレッド管理部１１２は、処理装置９１１を用いて、新たに起動したスレッド８５４を、そのプロセス８５１の処理にはすぐに参入させない。入力回数ｎ以上の周期が経過して、記憶装置９１４に十分な対象データ８６３が蓄積されたのち、新たに起動したスレッド８５４を、そのプロセス８５１の処理に参入させる。
【０１４９】
例えば、そのプロセス８５１の既存のスレッド８５４を生かしつつ、追加の従スレッドだけを別の計算機８１０で起動した場合、すぐに、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、そのプロセス８５１の主スレッドが、対象データ通知処理８８２で、そのプロセス８５１の既存のスレッド８５４だけでなく、新たに起動した従スレッドに対しても、入力した対象データ８６３（の一部）を通知するよう、指示する。ただし、この時点では、そのプロセス８５１の既存のスレッド８５４が処理する部分処理８５３の範囲は、変更しない。そのプロセス８５１の主スレッドは、結果データ結合処理８８６で、そのプロセス８５１の既存の従スレッドが通知してきた結果データだけを使って結果データ８６２を生成する。新たに起動した従スレッド８５４が通知してきた結果データ８６２は、利用しない。
入力回数ｎ以上の周期が経過したのち、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、そのプロセス８５１の既存のスレッドが処理する部分処理８５３の範囲の変更を指示する。そのプロセス８５１の主スレッドは、結果データ結合処理８８６で、そのプロセス８５１の既存の従スレッドが通知してきた結果データだけでなく、新たに起動した従スレッドが通知してきた結果データも使って結果データ８６２を生成する。
【０１５０】
また、そのプロセス８５１のスレッド８５４をまるごと別の計算機８１０に移動した場合、すぐに、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、そのプロセス８５１の前段のプロセスの主スレッドが、そのプロセス８５１の既存の主スレッドだけでなく、新たに起動した主スレッドに対しても、結果データ８６２を通知するよう、指示する。ただし、この時点では、そのプロセス８５１の後段のプロセスの主スレッドは、そのプロセス８５１の既存の主スレッドが通知してきた結果データ８６２を、対象データ８６３として入力する。新たに起動した主スレッドが通知してきた結果データ８６２は、利用しない。
入力回数ｎ以上の周期が経過したのち、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、そのプロセス８５１の後段のプロセスの主スレッドが、新たに起動した主スレッドが通知してきた結果データを、対象データ８６３として入力するよう、指示する。
【０１５１】
移動プロセス終了部１４７は、他計算機処理装置選択部１４５が増加した分割数の処理装置９１１を選択した場合、処理装置９１１を用いて、他計算機スレッド起動部１４６が新たなスレッドを起動してから、そのプロセス８５１の入力回数ｎ以上の周期が経過したのち、そのプロセス８５１の既存のスレッド８５４を終了させる。
例えば、移動プロセス終了部１４７は、処理装置９１１を用いて、終了させるスレッド８５４などの情報を含む指示を、スレッド管理部１１２に通知する。スレッド管理部１１２は、新たに起動したスレッドをそのプロセス８５１の処理に参入させたのち、処理装置９１１を用いて、スレッド実行部１１１に対して、指示された既存のスレッド８５４の終了を指示する。
【０１５２】
処理時間短縮判定部１５１は、処理装置９１１を用いて、パイプライン処理時間予測部１３３が予測した予測結果に基づいて、各パイプライン処理８５０のパイプライン処理時間８７１が減少傾向にある場合、制限時間８７２を超過する危険が去ったか否かを判定する。
例えば、制限時間８７２の８０％を安全ラインとして、制限時間８７２を超過の危険が去ったか否かを判定する。処理時間短縮判定部１５１は、処理装置９１１を用いて、パイプライン処理時間予測部１３３がパイプライン処理時間８７１の変化を近似した直線の係数が正であるか負であるかを判定する。パイプライン処理時間８７１の変化を近似した直線の係数が負である場合、パイプライン処理時間８７１は、減少傾向にある。処理時間短縮判定部１５１は、処理装置９１１を用いて、パイプライン処理時間算出部１３２が算出した現在のパイプライン処理時間８７１と、制限時間８７２の８０％とを比較する。現在のパイプライン処理時間８７１が制限時間８７２の８０％以下であれば、処理時間短縮判定部１５１は、制限時間８７２を超過する危険が去ったと判定する。
【０１５３】
分割済プロセス選択部１５２は、処理時間短縮判定部１５１の判定結果に基づいて、あるパイプライン処理８５０のパイプライン処理時間８７１が制限時間８７２を超過する危険が去った場合、処理装置９１１を用いて、そのパイプライン処理８５０の分割済のプロセス８５１のなかから、分割数を減らすプロセス８５１を選択する。
例えば、分割済プロセス選択部１５２は、処理装置９１１を用いて、分割済のプロセス８５１のなかから、処理時間の減少傾向が最も強いプロセスを選択する。
あるいは、分割済プロセス選択部１５２は、処理装置９１１を用いて、分割済であって処理時間が減少傾向にあるプロセス８５１のなかから、分割数を減らすことによる処理時間の増加が最も少ないプロセスを選択する。
あるいは、分割済プロセス選択部１５２は、処理装置９１１を用いて、分割済であって処理時間が減少傾向にあるプロセス８５１のなかから、主スレッドを実行している処理装置９１１と異なる計算機８１０の処理装置９１１が従スレッドを実行していることにより効率が悪くなっているプロセスを選択する。
あるいは、分割済プロセス選択部１５２は、処理装置９１１を用いて、分割済であって処理時間が減少傾向にあるプロセス８５１のなかから、前段および後段のプロセスのスレッド８５４を実行している処理装置９１１と異なる計算機８１０の処理装置９１１がスレッド８５４を実行していることにより効率が悪くなっているプロセスを選択する。
【０１５４】
終了スレッド選択部１５３は、処理装置９１１を用いて、分割済プロセス選択部１５２が選択したプロセス８５１のスレッド８５４のなかから、終了するスレッド８５４を選択する。
例えば、分割済プロセス選択部１５２が選択したプロセス８５１の従スレッドのなかに、主スレッドを実行している処理装置９１１と異なる計算機８１０の処理装置９１１が実行している従スレッドがあれば、終了スレッド選択部１５３は、処理装置９１１を用いて、その従スレッドを選択する。
あるいは、終了スレッド選択部１５３は、処理装置９１１を用いて、分割済プロセス選択部１５２が選択したプロセス８５１の各スレッド８５４を実行している各処理装置９１１のＣＰＵ時間に基づいて、空き時間が最も少ない処理装置９１１を選択し、その処理装置９１１が実行しているスレッド８５４を選択する。
あるいは、終了スレッド選択部１５３は、処理装置９１１を用いて、分割済プロセス選択部１５２が選択したプロセス８５１のスレッド８５４のなかから、そのスレッド８５４を実行している処理装置９１１と同じ計算機８１０の処理装置９１１のなかに前段または後段のプロセスを実行している処理装置９１１がないスレッド８５４を選択する。
【０１５５】
スレッド終了部１５４は、処理装置９１１を用いて、終了スレッド選択部１５３が選択したスレッド８５４を終了させる。
例えば、スレッド終了部１５４は、処理装置９１１を用いて、終了するスレッド８５４を実行する処理装置９１１や、新たに起動するスレッド８５４がどのパイプライン処理８５０のどのプロセス８５１のものであるかなどの情報を含む指示を、スレッド管理部１１２に通知する。スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、指示されたスレッド８５４の終了を指示する。
【０１５６】
また、スレッド８５４の終了により、同じプロセス８５１の他のスレッド８５４が処理すべき部分処理８５３の範囲が変わるので、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、同じプロセス８５１の主スレッドや他の従スレッドの部分処理８５３の範囲の変更を指示する。
【０１５７】
図２６は、この実施の形態におけるパイプライン管理処理Ｓ４００の流れの一例を示すフローチャート図である。
パイプライン管理処理Ｓ４００において、計算機システム８００は、実行している各パイプライン処理８５０のパイプライン処理時間８７１を監視し、制限時間８７２を超過しないようにする。
パイプライン管理処理Ｓ４００は、パイプライン選択工程Ｓ４０１と、パイプライン処理時間予測工程Ｓ４０２と、制限時間超過判定工程Ｓ４０３と、対策済判定工程Ｓ４０４と、プロセス分割工程Ｓ４０５と、参入時刻判定工程Ｓ４０６と、参入工程Ｓ４０７と、処理時間短縮判定工程Ｓ４０８と、プロセス併合工程Ｓ４０９とを有する。
【０１５８】
パイプライン選択工程Ｓ４０１において、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、計算機システム８００が実行しているパイプライン処理８５０のなかから、パイプライン処理８５０を一つ選択する。
【０１５９】
パイプライン処理時間予測工程Ｓ４０２において、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、パイプライン選択工程Ｓ４０１で選択したパイプライン処理８５０について、ｍ周期先におけるパイプライン処理時間８７１を予測する。
予測の結果、パイプライン処理時間８７１が増加傾向にある場合、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、制限時間超過判定工程Ｓ４０３へ処理を進める。
パイプライン処理時間８７１が減少傾向にある場合、パイプライン処理時間予測部１３３は、処理装置９１１を用いて、処理時間短縮判定工程Ｓ４０８へ処理を進める。
【０１６０】
制限時間超過判定工程Ｓ４０３において、制限時間超過判定部１４１は、処理装置９１１を用いて、パイプライン処理時間予測工程Ｓ４０２でパイプライン処理時間予測部１３３が予測したパイプライン処理時間８７１に基づいて、ｍ周期後にパイプライン処理時間８７１が制限時間８７２を超過するか否かを判定する。
超過すると判定した場合、制限時間超過判定部１４１は、処理装置９１１を用いて、対策済判定工程Ｓ４０４へ処理を進める。
超過しないと判定した場合、制限時間超過判定部１４１は、処理装置９１１を用いて、参入時刻判定工程Ｓ４０６へ処理を進める。
【０１６１】
対策済判定工程Ｓ４０４において、分割プロセス選択部１４２は、処理装置９１１を用いて、制限時間超過への対策が済んでいるか否かを判定する。制限時間超過への対策が済んでいる場合とは、プロセス８５１を分割して新たなスレッド８５４を起動したが、入力回数ｎの対象データ８６３がまだ蓄積されていないため、プロセスの処理に参入していない状態のことである。
対策済であると判定した場合、分割プロセス選択部１４２は、処理装置９１１を用いて、参入時刻判定工程Ｓ４０６へ処理を進める。
まだ対策していないと判定した場合、分割プロセス選択部１４２は、処理装置９１１を用いて、プロセス分割工程Ｓ４０５へ処理を進める。
【０１６２】
プロセス分割工程Ｓ４０５において、分割プロセス選択部１４２は、処理装置９１１を用いて、分割するプロセス８５１を選択する。空き処理装置選択部１４３または他計算機処理装置選択部１４５は、処理装置９１１を用いて、新たに起動するスレッド８５４を実行する処理装置９１１を選択する。スレッド起動部１４４または他計算機スレッド起動部１４６は、処理装置９１１を用いて、空き処理装置選択部１４３または他計算機処理装置選択部１４５が選択した処理装置９１１に、新たなスレッド８５４を実行させる。
新たに起動したスレッド８５４を実行する処理装置９１１が、それまでとは異なる計算機８１０の処理装置である場合、データが蓄積されていないので、すぐにプロセス８５１の処理に参入できない。移動プロセス終了部１４７は、処理装置９１１を用いて、分割プロセス選択部１４２が選択したプロセス８５１の入力回数ｎに基づいて、ｎ周期以上経過したあとの時刻を、新たに起動したスレッド８５４を処理に参入させる時刻として算出する。移動プロセス終了部１４７は、記憶装置９１４を用いて、算出した時刻を記憶する。
【０１６３】
参入時刻判定工程Ｓ４０６において、移動プロセス終了部１４７は、処理装置９１１を用いて、プロセス分割工程Ｓ４０５で記憶した時刻があるか否か、ある場合には、その時刻を過ぎたか否かを判定する。
プロセス分割工程Ｓ４０５で記憶した時刻を過ぎた場合、移動プロセス終了部１４７は、処理装置９１１を用いて、参入工程Ｓ４０７へ処理を進める。
プロセス分割工程Ｓ４０５で記憶した時刻をまだ過ぎていない場合、あるいは、プロセス分割工程Ｓ４０５で時刻を記憶していない場合、移動プロセス終了部１４７は、処理装置９１１を用いて、パイプライン選択工程Ｓ４０１に処理を戻す。パイプライン処理時間予測部１３３は、次のパイプライン処理８５０を選択する。
【０１６４】
参入工程Ｓ４０７において、スレッド管理部１１２は、処理装置９１１を用いて、新たに起動したスレッド８５４を、プロセス８５１の処理に参入させる。移動プロセス終了部１４７は、処理装置９１１を用いて、まるごと別の計算機８１０に移動したプロセス８５１の既存のスレッド８５４を終了させる。
移動プロセス終了部１４７は、処理装置９１１を用いて、パイプライン選択工程Ｓ４０１に処理を戻す。パイプライン処理時間予測部１３３は、次のパイプライン処理８５０を選択する。
【０１６５】
処理時間短縮判定工程Ｓ４０８において、処理時間短縮判定部１５１は、処理装置９１１を用いて、制限時間超過の危険が去ったか否かを判定する。
制限時間超過の危険が去ったと判定した場合、処理時間短縮判定部１５１は、処理装置９１１を用いて、プロセス併合工程Ｓ４０９へ処理を進める。
制限時間超過の危険がまだ去っていないと判定した場合、処理時間短縮判定部１５１は、処理装置９１１を用いて、参入時刻判定工程Ｓ４０６へ処理を進める。
【０１６６】
プロセス併合工程Ｓ４０９において、分割済プロセス選択部１５２は、処理装置９１１を用いて、併合するプロセスを選択する。終了スレッド選択部１５３は、処理装置９１１を用いて、終了するスレッド８５４を選択する。スレッド終了部１５４は、処理装置９１１を用いて、終了スレッド選択部１５３が選択したスレッド８５４を終了させる。
【０１６７】
図２７は、この実施の形態におけるプロセス分割工程Ｓ４０５の流れの一例を示すフローチャート図である。
プロセス分割工程Ｓ４０５は、プロセス選択工程Ｓ４１１と、処理装置選択工程Ｓ４１２と、スレッド起動工程Ｓ４１３と、他計算機選択工程Ｓ４１４と、処理装置選択工程Ｓ４１５と、他計算機選択工程Ｓ４１６と、処理装置選択工程Ｓ４１７と、スレッド起動工程Ｓ４１８と、参入工程Ｓ４１９と、参入予約工程Ｓ４２０とを有する。
【０１６８】
プロセス選択工程Ｓ４１１において、分割プロセス選択部１４２は、処理装置９１１を用いて、パイプライン選択工程Ｓ４０１でパイプライン処理時間予測部１３３が選択したパイプライン処理８５０のプロセス８５１のなかから、分割するプロセス８５１を選択する。
【０１６９】
処理装置選択工程Ｓ４１２において、空き処理装置選択部１４３は、処理装置９１１を用いて、スレッド管理部１１２が記憶したスレッド管理テーブルに基づいて、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の主スレッドを実行している処理装置９１１を判定する。
空き処理装置選択部１４３は、処理装置９１１を用いて、判定した処理装置９１１を有する計算機８１０の処理装置９１１のなかから、新たに起動するスレッド８５４を実行させる処理装置９１１を選択する。
新たに起動するスレッド８５４を実行させることができる処理装置９１１がある場合、空き処理装置選択部１４３は、処理装置９１１を用いて、スレッド起動工程Ｓ４１３へ処理を進める。
新たに起動するスレッド８５４を実行させることができる処理装置９１１がない場合、空き処理装置選択部１４３は、処理装置９１１を用いて、他計算機選択工程Ｓ４１４へ処理を進める。
【０１７０】
スレッド起動工程Ｓ４１３において、スレッド起動部１４４は、処理装置９１１を用いて、処理装置選択工程Ｓ４１２で空き処理装置選択部１４３が選択した処理装置９１１に、新たに起動するスレッド８５４を実行させる。
スレッド起動部１４４は、処理装置９１１を用いて、参入工程Ｓ４１９へ処理を進める。
【０１７１】
他計算機選択工程Ｓ４１４において、他計算機処理装置選択部１４５は、処理装置９１１を用いて、処理装置選択工程Ｓ４１２で空き処理装置選択部１４３が判定した処理装置９１１を有する計算機８１０と異なる計算機８１０のなかから、まだ選択していない計算機８１０を１つ選択する。選択の優先順位は、例えば、以下のとおりである。
（１）プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の前段または後段のプロセスの主スレッドを実行している処理装置９１１と、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の従スレッドを実行している処理装置９１１とを有する計算機８１０。
（２）プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の前段または後段のプロセスの主スレッドを実行している処理装置９１１を有し、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の従スレッドを実行している処理装置９１１を有さない計算機８１０。
（３）プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の前段または後段のプロセスの主スレッドを実行している処理装置９１１を有さず、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の従スレッドを実行している処理装置９１１を有する計算機８１０。
（４）プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の前段または後段のプロセスの主スレッドを実行している処理装置９１１を有さず、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の従スレッドを実行している処理装置９１１も有さない計算機８１０。
【０１７２】
前段または後段のプロセスの主スレッドを実行している処理装置９１１を有する計算機８１０を優先させるのは、プロセス間通信の負荷を抑えるためである。また、同じプロセス８５１の従スレッドを実行している処理装置９１１を有する計算機８１０を優先させるのは、対象データ８６３の蓄積があり、すぐに処理に参入できるからである。
【０１７３】
すべての計算機８１０が選択済であり、選択できる計算機８１０がない場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、他計算機選択工程Ｓ４１６へ処理を進める。
まだ選択していない計算機８１０がある場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、優先順位にしたがって、そのなかから、計算機８１０を１つ選択する。他計算機処理装置選択部１４５は、処理装置９１１を用いて、処理装置選択工程Ｓ４１５へ処理を進める。
【０１７４】
処理装置選択工程Ｓ４１５において、他計算機処理装置選択部１４５は、処理装置９１１を用いて、他計算機選択工程Ｓ４１４で選択した計算機８１０の処理装置９１１のなかから、新たに起動するスレッド８５４を実行させることができる処理装置９１１を選択する。他計算機処理装置選択部１４５は、処理装置９１１を用いて、選択した処理装置９１１の数と、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の現在のスレッド８５４の数ｋとを比較する。
選択した処理装置９１１の数が、現在のスレッド８５４の数ｋより大きい場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、スレッド起動工程Ｓ４１８へ処理を進める。
選択した処理装置９１１の数が、現在のスレッド８５４の数ｋ以下である場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、処理装置９１１の選択を解除し、他計算機選択工程Ｓ４１４に処理を戻して、次の計算機８１０を選択する。
【０１７５】
他計算機選択工程Ｓ４１６において、他計算機処理装置選択部１４５は、処理装置９１１を用いて、再び最初から、処理装置選択工程Ｓ４１２で空き処理装置選択部１４３が判定した処理装置９１１を有する計算機８１０と異なる計算機８１０のなかから、まだ選択していない計算機８１０を１つ選択する。選択の優先順位は、他計算機選択工程Ｓ４１４のときと同様である。
【０１７６】
処理装置選択工程Ｓ４１７において、他計算機処理装置選択部１４５は、処理装置９１１を用いて、他計算機選択工程Ｓ４１６で選択した計算機８１０について、処理装置選択工程Ｓ４１５で選択した処理装置９１１のなかから、処理装置９１１を１つ選択する。
処理装置選択工程Ｓ４１５で選択した処理装置９１１が１つもなかった場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、他計算機選択工程Ｓ４１６に処理を戻し、次の計算機８１０を選択する。
処理装置選択工程Ｓ４１５で選択した処理装置９１１があった場合、他計算機処理装置選択部１４５は、処理装置９１１を用いて、スレッド起動工程Ｓ４１８へ処理を進める。
【０１７７】
スレッド起動工程Ｓ４１８において、他計算機スレッド起動部１４６は、処理装置９１１を用いて、処理装置選択工程Ｓ４１５またはＳ４１７で他計算機処理装置選択部１４５が選択した処理装置９１１に、新たに起動するスレッドを実行させる。
スレッド管理部１１２は、処理装置９１１を用いて、新たに起動したスレッドがプロセスの処理にすぐに参入できるか否かを判定する。新たに起動したスレッドがプロセスの処理にすぐに参入できる場合とは、新たに起動したスレッドを実行する処理装置９１１を有する計算機８１０の記憶装置９１４に、そのプロセス８５１の入力回数ｎ以上の対象データ８６３が蓄積されている場合である。
新たに起動したスレッドがプロセスの処理にすぐに参入できる場合、スレッド管理部１１２は、処理装置９１１を用いて、参入工程Ｓ４１９へ処理を進める。
新たに起動したスレッドがプロセスの処理にすぐに参入できない場合、スレッド管理部１１２は、処理装置９１１を用いて、参入予約工程Ｓ４２０へ処理を進める。
【０１７８】
参入工程Ｓ４１９において、スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の既存のスレッド８５４が担当する部分処理８５３の変更を指示し、新たに起動したスレッド８５４をプロセス８５１の処理に参入させる。
また、新たに起動したスレッド８５４がプロセス８５１の処理に参入したことにより、不要になったスレッド８５４があれば、移動プロセス終了部１４７は、処理装置９１１を用いて、不要になったスレッド８５４を終了させる。
スレッド管理部１１２は、処理装置９１１を用いて、プロセス分割工程Ｓ４０５を終了する。
【０１７９】
参入予約工程Ｓ４２０において、スレッド管理部１１２は、処理装置９１１を用いて、プロセス選択工程Ｓ４１１で分割プロセス選択部１４２が選択したプロセス８５１の入力回数ｎに基づいて、ｎ周期以上先の時刻を算出する。スレッド管理部１１２は、記憶装置９１４を用いて、算出した時刻を、スレッド起動工程Ｓ４１８で他計算機スレッド起動部１４６が新たに起動したスレッドをプロセスの処理に参入させる予約時刻として記憶する。
スレッド管理部１１２は、処理装置９１１を用いて、プロセス分割工程Ｓ４０５を終了する。
【０１８０】
図２８は、この実施の形態におけるプロセス併合工程Ｓ４０９の流れの一例を示すフローチャート図である。
プロセス併合工程Ｓ４０９は、プロセス選択工程Ｓ４２１と、スレッド選択工程Ｓ４２２と、スレッド終了工程Ｓ４２３とを有する。
【０１８１】
プロセス選択工程Ｓ４２１において、分割済プロセス選択部１５２は、処理装置９１１を用いて、パイプライン選択工程Ｓ４０１でパイプライン処理時間予測部１３３が選択したパイプライン処理８５０のプロセス８５１のなかから、併合するプロセス８５１を選択する。
【０１８２】
スレッド選択工程Ｓ４２２において、終了スレッド選択部１５３は、処理装置９１１を用いて、プロセス選択工程Ｓ４２１で分割済プロセス選択部１５２が選択したプロセス８５１のスレッド８５４のなかから、終了するスレッド８５４を選択する。
【０１８３】
スレッド終了工程Ｓ４２３において、スレッド終了部１５４は、処理装置９１１を用いて、スレッド選択工程Ｓ４２２で終了スレッド選択部１５３が選択したスレッド８５４を終了させる。スレッド管理部１１２は、処理装置９１１を用いて、スレッド実行部１１１に対して、プロセス選択工程Ｓ４２１で分割済プロセス選択部１５２が選択したプロセス８５１の他のスレッドの部分処理８５３の変更を通知する。
スレッド管理部１１２は、処理装置９１１を用いて、プロセス併合工程Ｓ４０９を終了する。
【０１８４】
以上、各実施の形態で説明した構成は、一例であり、異なる実施の形態で説明した構成を組み合わせた構成としてもよい。また、主要でない部分の構成を既存の技術など他の構成と置き換えるなどの変形をした構成としてもよい。
【０１８５】
以上説明した計算機システム（８００；１）は、所定の周期で繰り返し入力データ（８６１）を入力し、直列関係にある複数のプロセス（８５１；７）からなるパイプライン処理（８５０）により上記入力データ（８６１）を処理する。最前段のプロセス（８５１；７）は、上記入力データ（８６１）を処理して処理結果（結果データ８６２）を出力する。後段のプロセス（８５１；７）は、前段のプロセス（８５１；７）が出力した処理結果（８６２）を処理して処理結果（８６２）を出力する。上記入力データ（８６１）を入力した時刻から所定の制限時間（８７２）が経過するまでの間に最後段のプロセス（８５１；７）が処理結果を出力することを要求される。
計算機システム（８００；１）は、複数の計算機（８１０；３）と、スレッド開始時刻取得部（１２１；スレッド処理時間監視部９）と、スレッド終了時刻取得部（１２２；９）と、プロセス開始時刻算出部（１２５）と、プロセス終了時刻算出部（１２６）と、プロセス処理時間算出部（１３１；計算機負荷監視部１０）と、パイプライン処理時間算出部（１３２；パイプライン処理時間監視部１１）と、パイプライン処理時間予測部（１３３；１１）と、制限時間超過判定部（１４１；１１）と、分割プロセス選択部（１４２；システム負荷監視部１３）と、空き処理装置選択部（１４３；１３）と、スレッド起動部（１４４；１３）と、他計算機処理装置選択部（１４５；１３）と、他計算機スレッド起動部（１４６；１３）とを有する。
各計算機（８１０；３）は、１以上の処理装置（９１１；ＣＰＵコア５）を有する。
複数の計算機（８１０；３）のうち少なくともいずれかの計算機の少なくともいずれかの処理装置（９１１；５）は、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のうちいずれかのプロセスの処理の少なくとも一部の処理をスレッド（８５４；８）として実行する。
スレッド開始時刻取得部（１２１；９）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、各周期の入力データ（８６１）について、いずれかの処理装置（９１１；５）が上記スレッド（８５４；８）の実行を開始した時刻を取得する。
スレッド終了時刻取得部（１２２；９）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、各周期の入力データ（８６１）について、いずれかの処理装置（９１１；５）が上記スレッド（８５４；８）の実行を終了した時刻を取得する。
プロセス開始時刻算出部（１２５）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、各周期の入力データ（８６１）について、上記スレッド開始時刻取得部（１２１；９）が取得した時刻に基づいて、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）それぞれの処理が開始した時刻を算出する。
プロセス終了時刻算出部（１２６）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、各周期の入力データ（８６１）について、上記スレッド終了時刻取得部（１２２；９）が取得した時刻に基づいて、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）それぞれの処理が終了した時刻を算出する。
プロセス処理時間算出部（１３１；１０）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、各周期の入力データ（８６１）について、上記プロセス開始時刻算出部（１２５）が算出した時刻と、上記プロセス終了時刻算出部（１２６）が算出した時刻とに基づいて、上記パイプライン処理（８５０）の各プロセス（８５１；７）の処理にかかった時間を算出する。
パイプライン処理時間算出部（１３２；１１）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、各周期の入力データ（８６１）について、上記プロセス開始時刻算出部（１２５）が上記パイプライン処理（８５０）の最前段のプロセス（８５１；７）について算出した時刻と、上記プロセス終了時刻算出部（８５１；７）が上記パイプライン処理（８５０）の最後段のプロセス（８５１；７）について算出した時刻とに基づいて、上記パイプライン処理（８５０）にかかった時間（パイプライン処理時間８７１）を算出する。
パイプライン処理時間予測部（１３３；１１）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記パイプライン処理時間算出部（１３２；１１）が算出した時間に基づいて、将来の周期において上記パイプライン処理（８５０）にかかる時間を予測する。
上記制限時間超過判定部（１４１；１１）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記パイプライン処理時間予測部（１３３；１１）が予測した時間に基づいて、将来の周期において上記制限時間（８７２）を超過するか否かを判定する。
上記分割プロセス選択部（１４２；１３）は、将来の周期において上記制限時間（８７２）を超過すると上記制限時間超過判定部（１４１；１１）が判定した場合に、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記プロセス処理時間算出部（１３１；１０）が算出した時間に基づいて、上記複数のプロセス（８５１）のうちから、プロセスの処理にかかる時間が増加しているプロセスを選択する。
上記空き処理装置選択部（１４３；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１）について、上記プロセスの処理の一部であるスレッド（８５４；８）を実行している処理装置（９１１；５）と同じ計算機（８１０；３）の処理装置（９１１；５）のなかに、上記プロセス（８５１）のスレッド（８５４）を実行していない処理装置（９１１；５）があるか否かを判定し、上記プロセス（８５１）のスレッド（８５４）を実行していない処理装置（９１１；５）があると判定した場合に、上記プロセス（８５１）のスレッド（８５４）を実行していないと判定した処理装置（９１１；５）を選択する。
スレッド起動部（１４４；１３）は、上記空き処理装置選択部（１４３；１３）が処理装置（９１１；５）を選択した場合に、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記空き処理装置選択部（１４３；１３）が選択した処理装置（９１１；５）に、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１）のスレッド（８５４）を新たに実行させる。
他計算機処理装置選択部（１４５；１３）は、上記空き処理装置選択部（１４３；１３）が処理装置（９１１；５）を選択しなかった場合に、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１）のスレッド（８５４）を実行している処理装置（９１１；５）と異なる計算機（８１０；３）の処理装置（９１１；５）のなかから、処理装置（９１１；５）を選択する。
他計算機スレッド起動部（１４６；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記他計算機処理装置選択部（１４５；１３）が選択した処理装置（９１１；５）に、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）のスレッド（８５４；８）を新たに実行させる。
【０１８６】
繰り返し処理の各周期におけるパイプライン処理時間の変化から、将来の周期のパイプライン処理時間を予測するので、制限時間の超過を早い段階で予測し、対策を取ることができる。また、プロセスを分割したスレッドを実行する処理装置を、同じ計算機の処理装置を優先させて選択するので、スレッド間通信の負荷を減らすことができ、プロセスを分割したことによるパイプライン処理時間の短縮効果を確実にすることができる。
【０１８７】
パイプライン処理（８５０）の複数のプロセス（８５１；７）のうち少なくともいずれかのプロセスは、直前の所定の入力回数の周期で入力した入力データ（８６１）または前段のプロセス（８５１；７）が直前の所定の入力回数の周期で出力した処理結果（８６２）を処理して処理結果（８６２）を出力する。
各計算機（８１０；３）は、上記１以上の処理装置（９１１；５）が共有する記憶装置（９１４）を有する。
記憶装置（９１４）は、上記記憶装置（９１４）を共有する１以上の処理装置（９１１；５）のいずれかが実行しているスレッド（８５４；８）のプロセス（８５１；７）について、上記プロセス（８５１；７）が処理する入力データ（８６１）または前段のプロセス（８５１；７）が出力した処理結果（８６２）を記憶する。
制限時間超過判定部（１４１；１１）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、現在の周期から所定の予測回数だけ先の周期において上記制限時間（８７２）を超過するか否かを判定する。予測回数は、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）の入力回数のうち最も大きい入力回数よりも大きい。
他計算機処理装置選択部（１４５；１３）が選択した処理装置（９１１；５）に上記他計算機スレッド起動部（１４６；１３）が実行させたスレッド（８５４；８）のプロセス（８５１；７）について、上記プロセス（８５１；７）の後段のプロセス（８５１；７）のスレッド（８５４；８）を実行している処理装置（９１１；５）は、上記プロセス（８５１；７）の入力回数が経過するまで、上記他計算機処理装置選択部（１４５；１３）が選択した処理装置（９１１；５）が実行したスレッド（８５４；８）の処理結果（８６２）を利用しない。
【０１８８】
パイプライン処理８５０の最大入力回数の周期よりも先の周期において制限時間を超過するか否かを予測するので、制限時間の超過を早い段階で予測し、対策を取ることができる。それまでとは異なる計算機の処理装置が新たに起動したスレッドを実行する場合であっても、新たに起動したスレッドが必要とするデータが蓄積されるまで待つ余裕がある。このため、新たに起動したスレッドが必要とするデータをまとめて転送するなど、新たなスレッド起動に伴う余計な処理をする必要がなく、新たなスレッド起動の影響により逆にパイプライン処理時間が長くなり、制限時間を超過するのを防ぐことができる。
【０１８９】
他計算機処理装置選択部（１４５；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）について実行されているスレッド（８５４；８）の数よりも多い数の処理装置（９１１；５）を選択する。
計算機システム（８００；１）は、移動プロセス終了部（１４７；１３）を有する。
上記移動プロセス終了部（１４７；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）について、上記他計算機スレッド起動部（１４６；１３）が上記プロセス（８５１；７）のスレッド（８５４；８）を実行させた場合に、上記他計算機スレッド起動部（１４６；１３）が上記プロセス（８５１；７）のスレッド（８５４；８）を実行させてから上記プロセス（８５１；７）の入力回数の周期が経過したのちに、上記他計算機スレッド起動部（１４６；１３）が上記プロセス（８５１；７）のスレッド（８５４；８）を実行させるよりも前から上記プロセス（８５１；７）のスレッド（８５４；８）を実行していた処理装置（９１１；５）に、上記プロセス（８５１；７）のスレッド（８５４；８）の実行を終了させる。
【０１９０】
プロセスを分割したスレッドを異なる計算機の処理装置に実行させる場合、増加分のスレッドだけを異なる計算機の処理装置で実行させるのでなく、すべてのスレッドを同じ計算機の処理装置に実行させるので、スレッド間通信の負荷を軽減することができ、プロセスを分割したことによるパイプライン処理時間の短縮効果を確実にすることができる。また、新たに起動したスレッドが必要とするデータを蓄積するまでは、それより前から実行されていたスレッドを残しておくので、新たに起動したスレッドが必要とするデータをまとめて転送するなど、新たなスレッド起動に伴う余計な処理をする必要がなく、新たなスレッド起動の影響により逆にパイプライン処理時間が長くなり、制限時間を超過するのを防ぐことができる。
【０１９１】
空き処理装置選択部（１４３；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）について、上記プロセス（８５１；７）の処理の一部であるスレッド（８５４；８）を実行している処理装置（９１１；５）と同じ計算機（８１０；３）の処理装置（９１１；５）のなかに、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のいずれのプロセスのスレッド（８５４；８）も実行していない処理装置（９１１；５）があるか否かを判定し、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のいずれのプロセスのスレッド（８５４；８）も実行していない処理装置（９１１；５）があると判定した場合に、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のいずれのプロセスのスレッド（８５４；８）も実行していないと判定した処理装置（９１１；５）を選択する。
【０１９２】
分割したプロセスのスレッドを、同じパイプライン処理のプロセスのスレッドを実行していない処理装置に実行させるので、新たなスレッド起動の影響が同じパイプライン処理の別のプロセスに出るのを防ぎ、プロセスを分割したことによるパイプライン処理時間の短縮効果を確実にすることができる。
【０１９３】
他計算機処理装置選択部（１４５；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）のスレッド（８５４；８）を実行している処理装置（９１１；５）と異なる計算機（８１０；３）の処理装置（９１１；５）のなかから、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のいずれのプロセスのスレッド（８５４；８）も実行していない処理装置（９１１；５）を選択する。
【０１９４】
分割したプロセスのスレッドを、同じパイプライン処理のプロセスのスレッドを実行していない処理装置に実行させるので、新たなスレッド起動の影響が同じパイプライン処理の別のプロセスに出るのを防ぎ、プロセスを分割したことによるパイプライン処理時間の短縮効果を確実にすることができる。
【０１９５】
他計算機処理装置選択部（１４５；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）のスレッド（８５４；８）を実行している処理装置（９１１；５）と異なる計算機（８１０；３）のなかから、上記分割プロセス選択部（１４２；１３）が選択したプロセス（８５１；７）の前段のプロセス（８５１；７）または後段のプロセス（８５１；７）のスレッド（８５４；８）を実行している処理装置（９１１；５）を有する計算機（８１０；３）を選択し、選択した計算機（８１０；３）の処理装置（９１１；５）のなかから処理装置（９１１；５）を選択する。
【０１９６】
新たに起動するスレッドを、前段または後段のプロセスを実行している処理装置を有する計算機の処理装置に実行させるので、プロセス間通信の負荷を減らすことができ、プロセスを分割したことによるパイプライン処理時間の短縮効果を確実にすることができる。
【０１９７】
計算機システム（８００；１）は、処理時間短縮判定部（１５１；１１）と、分割済プロセス選択部（１５２；１３）と、終了スレッド選択部（１５３；１３）と、スレッド終了部（１５４；１３）とを有する。
処理時間短縮判定部（１５１；１１）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記パイプライン処理時間予測部（１３３；１１）が予測した時間に基づいて、上記パイプライン処理（８５０）にかかる時間が短縮しつつあるか否かを判定する。
分割済プロセス選択部（１５２；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記パイプライン処理（８５０）にかかる時間が短縮しつつあると上記処理時間短縮判定部（１５１；１１）が判定した場合に、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のなかから、複数のスレッド（８５４；８）が実行されているプロセスを選択する。
終了スレッド選択部（１５３；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割済プロセス選択部（１５２；１３）が選択したプロセス（８５１；７）の複数のスレッド（８５４；８）のなかから、終了するスレッド（８５４；８）を選択する。
スレッド終了部（１５４；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記終了スレッド選択部（１５３；１３）が選択したスレッド（８５４；８）について、上記スレッド（８５４；８）を実行している処理装置（９１１；５）に、上記スレッド（８５４；８）の実行を終了させる。
【０１９８】
パイプライン処理時間が減少傾向にある場合に、分割したプロセスのスレッドを終了するので、プロセス分割による処理負荷を減らすことができ、計算機資源を有効活用することができる。
【０１９９】
分割済プロセス選択部（１５２；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記プロセス処理時間算出部（１３１；１０）が算出した時間に基づいて、上記パイプライン処理（８５０）の複数のプロセス（８５１；７）のなかから、プロセス（８５１；７）の処理にかかる時間が減少しているプロセス（８５１；７）を選択する。
【０２００】
処理時間が減少しているプロセスのスレッドを終了するので、プロセスの併合によりパイプライン処理時間が増加するのを防ぐことができる。
【０２０１】
終了スレッド選択部（１５３；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割済プロセス選択部（１５２；１３）が選択したプロセス（８５１；７）の複数のスレッド（８５４；８）のなかから、他のスレッド（８５４；８）と異なる計算機（８１０；３）の処理装置（９１１；５）が実行しているスレッド（８５４；８）を選択する。
【０２０２】
スレッド間通信の負荷が大きいスレッドを終了させるので、スレッド間通信の負荷を減らすことができる。
【０２０３】
終了スレッド選択部（１５３；１３）は、上記複数の計算機（８１０；３）のうちいずれかの計算機のいずれかの処理装置（９１１；５）を用いて、上記分割済プロセス選択部（１５２；１３）が選択したプロセス（８５１；７）について、上記プロセス（８５１；７）の複数のスレッド（８５４；８）のなかから、同一の計算機（８１０；３）の他の処理装置（９１１；５）のなかに、上記プロセス（８５１；７）の前段のプロセス（８５１；７）または後段のプロセス（８５１；７）のスレッド（８５４；８）を実行している処理装置（９１１；５）がない処理装置（９１１；５）が実行しているスレッド（８５４；８）を選択する。
【０２０４】
プロセス間通信の負荷が大きいスレッドを終了させるので、プロセス間通信の負荷を減らすことができる。
【０２０５】
以上説明した計算機システムの機能ブロックは、計算機システムの少なくともいずれかの計算機の少なくともいずれかの処理装置がコンピュータプログラムを実行することにより、実現することができる。
【符号の説明】
【０２０６】
１，８００  計算機システム、２，８２０  ネットワーク、３，８１０  計算機、４  ＣＰＵ、５  ＣＰＵコア、６  ＯＳ、７，８５１  プロセス、８，８５４  スレッド、９  スレッド処理時間監視部、１０  計算機負荷監視部、１１  パイプライン処理時間監視部、１２  スレッド割付部、１３  システム負荷監視部、１４  スレッド制御部、１１１  スレッド実行部、１１２  スレッド管理部、１２１  スレッド開始時刻取得部、１２２  スレッド終了時刻取得部、１２５  プロセス開始時刻算出部、１２６  プロセス終了時刻算出部、１３１  プロセス処理時間算出部、１３２  パイプライン処理時間算出部、１３３  パイプライン処理時間予測部、１４１  制限時間超過判定部、１４２  分割プロセス選択部、１４３  空き処理装置選択部、１４４  スレッド起動部、１４５  他計算機処理装置選択部、１４６  他計算機スレッド起動部、１４７  移動プロセス終了部、１５１  処理時間短縮判定部、１５２  分割済プロセス選択部、１５３  終了スレッド選択部、１５４  スレッド終了部、８５０  パイプライン処理、８５２  処理、８５３  部分処理、８６１  入力データ、８６２  結果データ、８６３  対象データ、８７１  パイプライン処理時間、８７２  制限時間、８８１  対象データ入力処理、８８２  対象データ通知処理、８８３  対象データ取得処理、８８４  結果データ通知処理、８８５  結果データ取得処理、８８６  結果データ結合処理、８８７  結果データ出力処理、９１１  処理装置、９１２  バス、９１４  記憶装置、９１５  入力装置、９１６  出力装置。
【図１】
0005465105.tif 000005
【図２】
0005465105.tif 000006
【図３】
0005465105.tif 000007
【図４】
0005465105.tif 000008
【図５】
0005465105.tif 000009
【図６】
0005465105.tif 000010
【図７】
0005465105.tif 000011
【図８】
0005465105.tif 000012
【図９】
0005465105.tif 000013
【図１０】
0005465105.tif 000014
【図１１】
0005465105.tif 000015
【図１２】
0005465105.tif 000016
【図１３】
0005465105.tif 000017
【図１４】
0005465105.tif 000018
【図１５】
0005465105.tif 000019
【図１６】
0005465105.tif 000020
【図１７】
0005465105.tif 000021
【図１８】
0005465105.tif 000022
【図１９】
0005465105.tif 000023
【図２０】
0005465105.tif 000024
【図２１】
0005465105.tif 000025
【図２２】
0005465105.tif 000026
【図２３】
0005465105.tif 000027
【図２４】
0005465105.tif 000028
【図２５】
0005465105.tif 000029
【図２６】
0005465105.tif 000030
【図２７】
0005465105.tif 000031
【図２８】
0005465105.tif 000032