(57)【要約】【課題】互いに依存関係のある複数のジョブを複数のプロセッサ上で動作させるシステムにおいて、高速かつスケーラブルなスケジューリングを可能とする階層スケジューリング装置を提供すること。【解決手段】初期化部４は、対象となる複数のジョブを、階層関係を有する複数のグループにグルーピングする。また、ボトムアップスケジューリング部５は、スケジューリングエンジンコア２を利用して、各グループに対するスケジューリングを、該階層関係における最下位のリーフグループから、該階層関係における最上位のルートグループへ向かって、順次実行する。トップダウンスケジューリング部６は、スケジューリングエンジンコア２を利用して、該階層関係におけるより上位のグループをその下位のグループ又はジョブへ分割した上で、ルートグループに対する再スケジューリングを実行することを、繰り返す。【選択図】      図１
2009070264.tif 000002
【特許請求の範囲】
【請求項１】
依存関係を有する複数のジョブを、複数のプロセッサに割り当てるスケジューリングを実行する階層スケジューリング装置において、
前記複数のジョブを、階層関係を有する複数のグループにグルーピングするグルーピング手段と、
前記複数のグループのそれぞれに対するスケジューリングを、前記階層関係における最下位のグループであるリーフグループから、前記階層関係における最上位のグループであるルートグループへ向かって、順次実行する第１のスケジューリング手段と、
前記階層関係におけるより上位のグループをその下位のグループ又はジョブへ分割した上で、前記ルートグループに対する再スケジューリングを実行することを、１回又は複数回繰り返し実行する第２のスケジューリング手段とを備えたことを特徴とする階層スケジューリング装置。
【請求項２】
前記第１のスケジューリング手段は、前記階層関係における親となるグループについて、その子となるグループ又はジョブのみに基づいて、前記スケジューリングを実行することを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項３】
前記第１のスケジューリング手段は、前記階層関係における親となるグループに対するスケジューリングを実行するにあたって、その子となるグループに対するスケジューリング結果を、再計算なしで利用することを特徴とする請求項２に記載の階層スケジューリング装置。
【請求項４】
前記第２のスケジューリング手段は、前記ルートグループについて、その子となるグループのうち分割がなされたグループの当該分割後のグループ又はジョブ、及びその子となるグループのうち分割がなされていないグループが残っている場合における当該分割がなされていないグループのみに基づいて、前記スケジューリングを実行することを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項５】
前記第２のスケジューリング手段は、前記ルートグループに対するスケジューリングを実行するにあたって、前記第１のスケジューリング手段による各々の前記グループに対するスケジューリング結果を、再計算なしで利用することを特徴とする請求項４に記載の階層スケジューリング装置。
【請求項６】
前記グループに対するスケジューリング結果に基づいて、各グループのスケジューリング結果を評価する評価手段を更に備え、
前記前記第２のスケジューリング手段は、前記評価手段による評価の結果に基づいて、前記分割の対象とするグループを選択することを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項７】
前記評価手段は、前記グループに対するスケジューリング結果につき、プロセッサが休眠する程度を考慮して、前記評価を行うことを特徴とする請求項６に記載の階層スケジューリング装置。
【請求項８】
前記第２のスケジューリング手段による前記ルートグループに対する再スケジューリングの結果につき、前記複数のジョブが開始してから終了するまでに要する時間が、与えられた目標値を満たす場合に、前記第２のスケジューリング手段による前記再スケジューリングを終了すると判定する判定手段を更に備えたことを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項９】
スケジューリングの実行に費やす時間が、与えられた上限値に達した場合に、前記第２のスケジューリング手段による前記再スケジューリングを終了すると判定する判定手段を更に備えたことを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項１０】
前記スケジューリング結果は、少なくとも、利用するプロセッサの数ごとに、前記複数のジョブを実行するのに要する時間を示す実行時間と、前記複数のジョブの各々を実行するのに要する時間の総計を示すのべ実行時間とを含むものであることを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項１１】
前記前記第１のスケジューリング手段により得られた、前記複数のグループのそれぞれに対するスケジューリングの結果を、該グループに対応して格納する階層スケジューリングテーブルを記憶する手段を更に備えたことを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項１２】
スケジューリング対象となるジョブに関する情報と、プロセッサ数とを入力とし、各ジョブを各プロセッサにスケジューリングした結果を出力するスケジューリングエンジンコアを更に備え、
前記第１のスケジューリング手段及び前記第２のスケジューリング手段は、それぞれ、前記スケジューリングエンジンコアを利用して、前記スケジューリングを実行することを特徴とする請求項１に記載の階層スケジューリング装置。
【請求項１３】
依存関係を有する複数のジョブを、複数のプロセッサに割り当てるスケジューリングを実行する階層スケジューリング装置の階層スケジューリング方法において、
前記階層スケジューリング装置の備えるグルーピング手段が、前記複数のジョブを、階層関係を有する複数のグループにグルーピングするグルーピングステップ、
前記階層スケジューリング装置の備える第１のスケジューリング手段が、前記複数のグループのそれぞれに対するスケジューリングを、前記階層関係における最下位のグループであるリーフグループから、前記階層関係における最上位のグループであるルートグループへ向かって、順次実行する第１のスケジューリングステップと、
前記階層スケジューリング装置の備える第２のスケジューリング手段が、前記階層関係におけるより上位のグループをその下位のグループ又はジョブへ分割した上で、前記ルートグループに対する再スケジューリングを実行することを、１回又は複数回繰り返し実行する第２のスケジューリングステップとを有することを特徴とするスケジューリング方法。
【請求項１４】
依存関係を有する複数のジョブを、複数のプロセッサに割り当てるスケジューリングを実行するスケジューリング装置としてコンピュータを機能させるためのプログラムにおいて、
前記複数のジョブを、階層関係を有する複数のグループにグルーピングするグルーピング手段と、
前記複数のグループのそれぞれに対するスケジューリングを、前記階層関係における最下位のグループであるリーフグループから、前記階層関係における最上位のグループであるルートグループへ向かって、順次実行する第１のスケジューリング手段と、
前記階層関係におけるより上位のグループをその下位のグループ又はジョブへ分割した上で、前記ルートグループに対する再スケジューリングを実行することを、１回又は複数回繰り返し実行する第２のスケジューリング手段とをコンピュータに機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のジョブを複数のプロセッサへ割り当てるスケジューリングを行う階層スケジューリング装置、階層スケジューリング方法及びプログラムに関する。
【背景技術】
【０００２】
ジョブ集合のプロセッサ群への割り当てを適切に行うために、ジョブ集合について３種類のグループを階層的に定義し、粗いグループから、細かいグループへトップダウンでスケジューリングする手法が提案されている（非特許文献１参照）。
【０００３】
ここで提案されている手法においては、各グループへの割り当てプロセッサ数は１度決定すると不変である。この結果として、第１に、計算時間の長短にスケーラブルに対応できない（より時間をかけて計算を行っても解が改善しない）という問題点が存在する。第２に、最適から遠い局所解しか求められない場合が多く存在する、という問題点が存在する。
【非特許文献１】笠原博徳他，  「マルチグレイン並列処理のための階層的並列性制御手法」，  情報処理学会論文誌，  Ｖｏｌ．  ４４，  Ｎｏ．  ４，  ２００３
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来、互いに依存関係のある複数のジョブを複数のプロセッサ上で動作させるシステムにおいて、高速かつスケーラブルなスケジューリングを行うことは困難であった。
【０００５】
本発明は、上記事情を考慮してなされたもので、互いに依存関係のある複数のジョブを複数のプロセッサ上で動作させるシステムにおいて、高速かつスケーラブルなスケジューリングを可能とする階層スケジューリング装置、階層スケジューリング方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、依存関係を有する複数のジョブを、複数のプロセッサに割り当てるスケジューリングを実行する階層スケジューリング装置において、前記複数のジョブを、階層関係を有する複数のグループにグルーピングするグルーピング手段と、前記複数のグループのそれぞれに対するスケジューリングを、前記階層関係における最下位のグループであるリーフグループから、前記階層関係における最上位のグループであるルートグループへ向かって、順次実行する第１のスケジューリング手段と、前記階層関係におけるより上位のグループをその下位のグループ又はジョブへ分割した上で、前記ルートグループに対する再スケジューリングを実行することを、１回又は複数回繰り返し実行する第２のスケジューリング手段とを備えたことを特徴とする。
【発明の効果】
【０００７】
本発明によれば、互いに依存関係のある複数のジョブを複数のプロセッサ上で動作させるシステムにおいて、高速かつスケーラブルなスケジューリングが可能になる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照しながら本発明の実施形態について説明する。
【０００９】
図１に、本発明の一実施形態に係る階層スケジューリング装置の構成例を示す。
【００１０】
図１に示されるように、本実施形態の階層スケジューリング装置は、階層スケジューリングテーブル管理部１、スケジューリングエンジンコア２、階層スケジューリングテーブル保存部３、初期化部４、ボトムアップスケジューリング部５、トップダウンスケジューリング部６、足かせ度演算部７、終了判定部８を備えている。
【００１１】
この階層スケジューリング装置は、詳しくは後述するように、例えば、スケジューリング対象となる複数のジョブからなる「ジョブ集合」、このジョブ集合の実行に使用できるプロセッサの数（上限数）を示す「プロセッサ数」、レイテンシ（すべてのジョブが開始してから終了するまでに要する時間）の目標値を示す「目標レイテンシ」、スケジューリング時間（スケジューリングの実行に費やす時間）の最大値を示す「最大スケジューリング時間」、ジョブを階層的にグルーピングする際における個々のグループが有する子（ジョブ又はグループ）の数の最大値を示す「最大子グループ数」を入力として、「スケジューリング結果」を出力する。「スケジューリング結果」は、例えば、各プロセッサにおいてどのジョブをどの順番に実行するかについてスケジューリングした結果である。なお、図１において、上記各入力は、例えば図示しない入力部から入力される。また、スケジューリング結果は、例えば、図示しない出力部から出力される。これら入力部や出力部は、そのような形態のものであってもよい。
【００１２】
なお、スケジューリングエンジンコア２には、既存の一般のスケジューリング装置を用いることができる。図２に、スケジューリングエンジンコア２の入出力を示す。このように、ジョブ集合とプロセッサ数とを入力し、スケジューリング結果を出力する。なお、スケジューリングエンジンコア２に用いる一般のスケジューリング装置としては、特定の装置に限定されるものではないが、例えば厳密解を与えるスケジューリング結果を出力するものを用いた場合に、本発明によるスケジューリング時間の短縮効果が特に大きい。本実施形態では、スケジューリングコアは、厳密解を求める装置であるとする。
【００１３】
ここで、本実施形態の階層スケジューリング装置の説明に先立って、まず、スケジューリングについて説明する。
【００１４】
一般に、スケジューリング装置は、ジョブ集合とプロセッサ数とを入力として、例えば、「ジョブ集合を高速に実行するためには、ジョブ集合中の各ジョブを、どのプロセッサで、どの順番に実行すればよいか」についてスケジューリングし、その結果を出力する。
【００１５】
スケジューリング対象のジョブ集合中の各ジョブは、複数存在するプロセッサの中のどれにおいても実行可能であるが、「１個のプロセッサで同時に実行可能なジョブの個数は１個である」という制約を満たすようにスケジューリングする必要がある。逆に、１個のジョブを複数のプロセッサを同時に用いて実行することは可能である。
【００１６】
スケジューリング装置に入力されるジョブ集合中の各ジョブには、  
・１個のプロセッサでジョブを実行した場合の実行時間、  
・２個のプロセッサでジョブを実行した場合の実行時間、  
・…  
・全プロセッサを使ってジョブを実行した場合の実行時間、  
という情報が付与されているものとする。
【００１７】
また、通常、ジョブ集合中のジョブ間に（実行の順序について）依存関係が存在するが、このような場合には、「依存元のジョブは、依存先のジョブが実行終了してから初めて実行することが可能である」という制約も満たすようにスケジューリングする必要がある。ジョブの依存関係を表現する方法はいくつか存在するが、本実施形態では、データフローグラフを用いて表現する場合を例にとって説明する。データフローグラフは、依存先ジョブから依存元ジョブへ必ずグラフの枝をたどって到達可能である有向グラフによるジョブ集合の表現形式である。
【００１８】
スケジューリング装置でジョブ集合をスケジューリングした結果、  
・１個のプロセッサでジョブ集合を実行した場合の実行時間、  
・２個のプロセッサでジョブ集合を実行した場合の実行時間、  
・…  
・全プロセッサを使ってジョブ集合を実行した場合の実行時間、  
のように、利用するプロセッサ数ごとのジョブ集合実行時間が得られる。
【００１９】
ここで、スケジューリングの一例として、上記制約を満たすように、加算「＋」と減算「−」と乗算「＊」の３個のジョブをスケジューリングする例について、図３を参照しながら説明する。
【００２０】
図３（ａ）に、加算「＋」と減算「−」と乗算「＊」の３個のジョブを含むプログラムの一例を示す。
【００２１】
なお、この例のように、互いに依存関係のある複数のジョブからなる集合は、アルゴリズムを記述するプログラミング言語によって表現されることが多い。
【００２２】
ただし、本実施形態において、ジョブ集合を表現する特定のプログラミング言語を想定している訳ではなく、また、プログラミング言語以外の方法によってジョブ集合を表現してもよい。
【００２３】
このように、互いに依存関係のある複数のジョブからなる集合が、プログラムによって表現される場合には、プログラムからジョブの依存関係を抽出し、ジョブ集合をデータフローグラフで表現した上で、スケジューリング装置の入力とする。
【００２４】
図３（ｂ）に、（ａ）のプログラムにおける「＋」と「−」と「＊」の３個のジョブの依存関係を表すデータフローグラフの一例を示す。
【００２５】
スケジューリング装置は、ジョブ間の依存関係に従って、例えば、各ジョブを、複数（例えば、４個）のプロセッサ中のどのプロセッサで、どの順番に実行するかについて、スケジューリングをする。
【００２６】
図３（ｃ）に、スケジューリングの結果の一例を示す。この例では、２個のプロセッサを用いてジョブ集合を実行する場合について、プロセッサ１で「＋」、「＊」の順番にジョブを実行し、プロセッサ２でジョブ「−」を実行するスケジューリング結果が得られる（なお、１個のプロセッサを用いてジョブ集合を実行する場合については、例えば、プロセッサ１で「＋」、「−」、「＊」の順番又は「−」、「＋」、「＊」の順番にジョブを実行するスケジューリング結果が得られる）。
【００２７】
スケジューリングを行う際には、ジョブ間の依存関係を守る（例えば、ジョブ「＋」は、ジョブ「＊」よりも先に実行されなければならない）ことに加えて、例えば、  
・ジョブの実行に関して、なるべく短い時間ですべてのジョブの実行が終了すること、  
・ジョブの実行に関して、なるべく少ないリソース（メモリなど）を用いてすべてのジョブを実行すること、  
・スケジューリングの実行に関して、なるべく短い時間でスケジューリング実行を終了すること、  
など、入力ごとに定められた目的関数を満たすようにジョブのプロセッサへの割り当てを行う。
【００２８】
本実施形態では、ユーザに所望なレイテンシ（すべてのジョブが開始してから終了するまでに要する時間）を実現するスケジューリング結果を、ユーザに所望なスケジューリング時間（スケジューリングの実行に費やす時間）以内で求めることをスケジューリングの目的とする場合を想定して説明するものとする。なお、ここで、レイテンシにおける時間の単位は、任意に設定可能であり、各ジョブの実行に要する時間が秒単位やクロック単位で厳密に分かっている場合には、秒やクロックを単位とするのでもよい。また、各ジョブの実行に要する時間が厳密に分かっていない場合には、１つのジョブを実行するのに要する時間が（＋も−も＊も）すべて同じであるとみなして、これを単位とするのでもよい。
【００２９】
ところで、スケジューリング対象のジョブ集合に含まれるジョブ数が多い場合には、ジョブへのプロセッサ割り当て方法の組み合わせ数が膨大になるため（具体的には、ジョブ数がＮ、プロセッサ数がＭの場合、ジョブへのプロセッサの割り当て方法の組み合わせがＭＮ通り存在する）、すべての組み合わせの中からレイテンシが最も短いスケジューリング結果を選び出すのは、Ｎが大きな場合には時間がかかり過ぎて現実的ではない（スケジューリングエンジンコアは現実的な時間でスケジューリング結果を返さない）。このように、一般に「ジョブ集合を最もレイテンシが短くなるようにスケジューリングしなさい」とか、「ジョブ集合をレイテンシが○○ｓｅｃ以下になるようにスケジューリングすることは可能ですか？」という問題は、厳密解を求めることがとても難しいクラスに属する。
【００３０】
そこで、本実施形態の階層スケジューリング装置では、スケジューリングエンジンコアを用いて、１回で大量のジョブをスケジューリングするよりは、何回かに分けて少数のジョブをスケジューリングする方が、スケジューリング結果を得るまでの時間が圧倒的に速いという性質を利用して、スケジューリング時間を短く抑える。具体的には、階層スケジューリングテーブルを用い、スケジューリングエンジンコアにおいて１回あたりにスケジューリングを行うジョブが少数になるように制御することで、ユーザに所望なスケジューリング時間以内でのスケジューリングを目指す。
【００３１】
このために階層スケジューリング装置におけるスケジューリングを、「ボトムアップスケジューリング」と呼ぶ初期解を求める段階と、「トップダウンスケジューリング」と呼ぶ初期解を改良する段階との２段階から構成する。
【００３２】
ボトムアップスケジューリング（ボトムアップスケジューリング部５）では、１回のスケジューリングあたりでスケジューリングエンジンコア２に入力するジョブ数を一定数以下に抑えながら、スケジューリングをボトムアップ的に繰り返すことによって、スケジューリングエンジンコア２に入力するジョブ数に制限を設けない場合より短いスケジューリング時間で、ジョブの依存関係の制約を満たすスケジューリング結果を（１通り）求める。
【００３３】
ボトムアップスケジューリング終了時に、目標レイテンシを満たすスケジューリング結果が得られていれば、階層スケジューリング装置におけるスケジューリングは終了である。ただし、一般には、ボトムアップスケジューリングのみでは目標レイテンシを満たさない場合が存在するので、その場合、ボトムアップスケジューリングの結果得られたスケジューリング結果を、トップダウンスケジューリングによって改良する。
【００３４】
トップダウンスケジューリング（トップダウンスケジューリング部６）では、１回のスケジューリングあたりでスケジューリングエンジンコア２に入力するジョブ数を徐々に増加させながら、スケジューリング時間が許す限り、または、目標レイテンシが満たされるまで、スケジューリングをトップダウン的に繰り返すことで、レイテンシの改良を行う。
【００３５】
トップダウンスケジューリングは、スケジューリング時間が長ければ長いほど、よりレイテンシが短いスケジューリング結果を得ることが可能である（つまり、スケジューリング時間に対してスケーラブルなスケジューリング結果を得ることが可能である）と言える。
【００３６】
本実施形態の階層スケジューリング装置は、初期解を求める部品と初期解を改良する部品を保持するが、独立な初期解を求める部品と、改良を行う部品とを単純に組み合わせている訳ではなく、初期解を求める部品であるボトムアップスケジューリング部５の計算結果を、初期解を改良する部品であるトップダウンスケジューリング部６（及びボトムアップスケジューリング部５自身）において再計算なしに再利用する構成になっているところに特徴を有している。
【００３７】
以下、図１に示した階層スケジューリング装置の構成・動作について詳しく説明する。
【００３８】
まず、階層スケジューリング装置の各部の概要は次の通りである。
【００３９】
初期化部４は、スケジューリング対象となるジョブ集合に含まれる複数のジョブのグルーピングと、このグルーピング結果に基づく階層スケジューリングテーブルの初期化を行う。
【００４０】
ボトムアップスケジューリング部５は、子グループをもとに親グループをスケジューリングすることを繰り返し行うボトムアップスケジューリングにより、ジョブ集合のスケジューリング結果の初期解を求める。
【００４１】
トップダウンスケジューリング部６は、親グループを子グループに分割して再スケジューリングを行うトップダウンスケジューリングにより、上記初期解の改善を行う。
【００４２】
足かせ度演算部７は、各グループの足かせ度を求める。足かせ度は、トップダウンスケジューリングにおいて、子グループに分割する対象とするグループを選択する際の基準として用いられる。
【００４３】
終了判定部８は、トップダウンスケジューリングを継続するかどうかを判定する。
【００４４】
スケジューリングエンジンコア２は、互いに依存関係のある複数のジョブとプロセッサ数を入力とし、レイテンシが最短になるように各ジョブを各プロセッサにスケジューリングした結果を出力する。
【００４５】
階層スケジューリングテーブル管理部１は、大きく分けて、「階層スケジューリングテーブルの初期化、読み出し、書き込みを行う」というような手続きと、「現在どのグループのスケジューリングを、どのグループのスケジューリング結果を用いて行っているか（どのジョブ（または、仮想的に１個のジョブとみなしたグループ）から構成されるとみなしてスケジューリングしているか）を、階層スケジューリングテーブルを用いて管理し、ボトムアップスケジューリング部５、トップダウンスケジューリング部６からの問い合わせに対して答える」というような手続きとを行う。
【００４６】
次に、グルーピング、階層スケジューリングテーブル、初期化について詳しく説明する。
【００４７】
初期化部４は、「ジョブを階層的にグルーピングする」という手続きと、「グルーピング結果に従い、階層スケジューリングテーブル管理部１経由で、階層スケジューリングテーブルを初期化する」という手続きとを行う。
【００４８】
図４（ａ）に、複数のジョブとその依存関係を表すデータフローグラフの一例を示し、図４（ｂ）に、このデータフローグラフ中のジョブを階層的にグルーピングした結果の一例を示す。
【００４９】
この例では、グループＡがジョブａとジョブｂを含み、グループＢがジョブｃとジョブｄを含み、グループＥがグループＡとグループＢを含み、グループＨがグループＥとグループＦとグループＧを含むというような階層関係が成り立っている。
【００５０】
なお、グルーピングの方法としては、種々のものが利用可能であり、特定のグルーピング方法に限定されるものではない。なお、後でグルーピングの具体例を示す。
【００５１】
グループの階層関係は、ツリーによって表現することが可能である。
【００５２】
図５に、中間ノードとして、グループをスケジューリングした結果（スケジューリングテーブル）を持ち、葉ノードとして、ジョブを持つツリーの一例を示す。
【００５３】
このようなスケジューリングテーブルのツリーを、「階層スケジューリングテーブル」と呼ぶ。
【００５４】
階層スケジューリングテーブルは、階層スケジューリングテーブル管理部１経由で、階層スケジューリングテーブル保存部３に格納される。
【００５５】
階層スケジューリングテーブルにおいて、親（子）の関係にあるグループのことを「親（子）グループ」と呼ぶ。図４の例において、グループＥはグループＢの親グループであり、グループＡはグループＥの子グループである。また、階層スケジューリングテーブルにおいて先祖（子孫）の関係にあるグループのことを「先祖（子孫）グループ」と呼ぶ。グループＨはグループＡの先祖グループであり、グループＡはグループＨの子孫グループである。
【００５６】
さらに、階層スケジューリングテーブルの根に相当するグループのことを「ルートグループ」、ルートグループのスケジューリング結果を格納するテーブルを「ルートスケジューリングテーブル」と呼ぶことにする。図４／図５の例では、グループＨがルートグループであり、グループＨのスケジューリングテーブルがルートスケジューリングテーブルである。ルートグループは階層スケジューリング装置の入力ジョブ集合に対応するので、ジョブ集合のスケジューリングを行うことはルートグループをスケジューリングすることを意味する。
【００５７】
なお、ジョブをグルーピングする際に、各グループの子（ジョブまたはグループ）の数が「最大子グループ数」以下になるようにすれば、後述するように、ボトムアップスケジューリングにおいて１回のスケジューリングあたりのジョブ数を「最大子グループ数」以下に抑えることができ、これがスケジューリング時間の短縮につながる。
【００５８】
階層スケジューリングテーブルの初期化時は、各スケジューリングテーブルは「枠」だけ用意され、「中身」は空の状態である。ボトムアップスケジューリングにおいて各グループのスケジューリングが実行されると、その結果が、当該スケジューリングテーブルの「中身」として埋められて行く。
【００５９】
図６に、階層スケジューリングテーブルの中間ノードであるスケジューリングテーブルの一例を示す。
【００６０】
この例では、スケジューリングテーブルは、（当該スケジューリングテーブルに対応する）当該グループをスケジューリングした結果を、当該グループに割り当てるプロセッサ数ごとにまとめたものであり、テーブルの各行は、当該グループを特定のプロセッサ数にスケジューリングした結果を表している。
【００６１】
図６の例において、「割当プロセッサ数」は、そのグループに割り当てるプロセッサ数であり、この例では、１個から４個までそれぞれ示されている。
【００６２】
「実行時間」は、当該グループの実行を開始してから終了するまでにかかる時間を表す。「のべ実行時間」は、当該グループの実行を開始してから実行するまでの間に、当該グループ内のジョブが実行された時間をすべて足し合わせたものである。なお、ここでの時間の単位は、任意に設定可能であり、例えばプロセッサが１つのジョブを実行するのに要する時間などを単位とするものでもよい。
【００６３】
例えば、図６の「プロセッサ数」が４個割り当てられるケースでは、「実行時間」は“２”、「のべ実行時間」は“５”となっている。例えば、図７のハッチングされた矩形が当該プロセッサの実行期間（以下、動作スロットと呼ぶ）を示し、ハッチングされていない矩形が当該プロセッサの休眠状態（以下、休眠スロットと呼ぶ）を示し、各矩形の時間軸方向の長さが、１つのプロセッサが１つのジョブを実行するのに要する単位時間（図７の両矢印の長さ）を示すものとして、図６の「プロセッサ数」が４個割り当てられるケースは、例えば、図７のようにプロセッサ１が最初の単位時間と次の単位時間で動作し、プロセッサ２〜４が最初の単位時間では休止となり、次の単位時間で動作するような状況に該当するものである。すなわち、図７において、当該グループの実行を開始してから終了するまでに２つ分の動作スロットの時間かかるので、「実行時間」は２単位時間となり、当該グループは延べで５つ分の動作スロットを使用するので、「のべ実行時間」は５単位時間となる。ただし、「プロセッサ数」が４、「実行時間」が２、「のべ実行時間」が５となる状況は、図７の状況以外にも存在する（図６の内容から、図７の状態が特定される訳ではない）。
【００６４】
なお、後述するように、実行時間は、当該グループを仮想的に１つの「ジョブ」とみなしてスケジューリングする際のスケジューリングエンジンコア２の入力や足かせ度演算部７の入力などとして利用され、のべ実行時間は、足かせ度演算部７の入力として利用される。
【００６５】
階層スケジューリングテーブル（ツリー）の中間ノードごとに、例えば図６のような形式のスケジューリングテーブルが保持される。
【００６６】
次に、ボトムアップスケジューリングについて詳しく説明する。
【００６７】
ボトムアップスケジューリング部５は、前述のように、より短いスケジューリング時間で、依存関係の制約を満たすジョブ集合のスケジューリング結果の初期解を求める。より具体的には、ボトムアップスケジューリング部５は、初期化部４で得られた、スケジューリング対象となるジョブ集合に対する、すべてのグループのスケジューリングを、スケジューリングエンジンコア２を用いて実行し、各グループのスケジューリング結果を、ボトムアップスケジューリングにおけるその後段のグループ（上位のグループ）のスケジューリングの実行時及びトップダウンスケジューリング実行時に、再計算なしで再利用できるように、階層スケジューリングテーブル管理部１経由で、階層スケジューリングテーブル保存部３の階層スケジューリングテーブルに格納する。
【００６８】
ただし、ボトムアップスケジューリングでは、或るグループ（グループＧとする。）のスケジューリングを行う際には、グループＧの個々の子グループを仮想的に１個の「ジョブ」とみなし、それら「ジョブ」（子グループ）のスケジューリング結果を用いて、グループＧのスケジューリングを実行する。例えば、グループＧが５個の子グループのみから構成される場合には、グループＧが仮想的に５個の「ジョブ」のみを持つとみなして、スケジューリングエンジンコア２を用いて５個の「ジョブ」のスケジューリングを行い、その結果を、グループＧのスケジューリング結果として、階層スケジューリングテーブルに格納する。
【００６９】
このように、子グループのスケジューリングがすべて実行されてから、それらの結果を用いて親グループのスケジューリングを実行するため、階層スケジューリングテーブルの最下位階層であるリーフグループから、階層スケジューリングテーブルの最上位階層であるルートグループに向かって、ボトムアップ方式でスケジューリングを実行する。このため、この手続きをボトムアップスケジューリングと呼ぶ。
【００７０】
初期化部４によりジョブ集合全体がＪ個のグループにグルーピングされているとすると、ボトムアップスケジューリングにおいて、スケジューリングエンジンコア２を用いたＪ回のスケジューリングが実行される。これらのうちＪ回目のスケジューリングがルートグループのスケジューリングであり、Ｊ回目のスケジューリングの結果が初期解である。
【００７１】
ここで、グループを仮想的に１個の「ジョブ」とみなす利点は次の通りである。すなわち、スケジューリングエンジンコア２の入力ジョブ数を少ない数に抑えることが可能である。この結果、本実施形態の階層スケジューリング装置への入力ジョブ集合をそのままスケジューリングエンジンコア２に入力してスケジューリング行う場合と比較して、圧倒的に高速にジョブ集合のスケジューリング行うことが可能である。
【００７２】
ただし、複数のジョブからなるグループを仮想的に１個のジョブとみなすことは、近似を行っていることを意味する。この結果として、階層スケジューリング装置への入力ジョブ集合をそのままスケジューリングエンジンコア２に入力してスケジューリング行う場合と比較して、スケジューリング結果のレイテンシが同じ、又は長くなる。このことから分かるように、階層スケジューリングテーブルに格納されるスケジューリング結果のうち、リーフスケジューリングテーブル以外は、レイテンシ最小化という意味において、近似解になる。なお、本実施形態では、ボトムアップスケジューリングで得られた初期解を、トップダウンスケジューリングで改善するわけである。
【００７３】
なお、以下では、「ジョブ」（括弧付きジョブ）は、広義のジョブであり、グループを仮想的に１個のジョブとみなす場合におけるその仮想的な１個のジョブ、または、最小のジョブ（狭義のジョブ）を意味するものとする。
【００７４】
図８に、ボトムアップスケジューリングにおいてスケジューリングを行うグループと、スケジューリングに用いる「ジョブ」の一例を示す。
【００７５】
ボトムアップスケジューリングにおいて、  
・グループＡのスケジューリングは、ジョブａとジョブｂの２ジョブのスケジューリングであり、  
・グループＥのスケジューリングは、「ジョブ」グループＡと「ジョブ」グループＢとからなる２「ジョブ」のスケジューリングであり、  
・グループＨのスケジューリングは、「ジョブ」グループＥと「ジョブ」グループＦと「ジョブ」グループＧとからなる３「ジョブ」のスケジューリングである。
【００７６】
図９に、ボトムアップスケジューリングにおける階層スケジューリングテーブルの変化の様子を例示する。なお、図中、９０１のハッチングがスケジューリング済みのグループを表し、９０２のハッチングがスケジューリング中のグループを表し、９０３のハッチングが利用中（スケジューリング済み）のグループ又はジョブを表している。
【００７７】
この例では、１回あたり２個か３個の「ジョブ」からなるグループのスケジューリングを８回行うことで、全１１個のジョブからなるジョブ集合をスケジューリングし、初期解を得ている。
【００７８】
次に、トップダウンスケジューリングについて詳しく説明する。
【００７９】
トップダウンスケジューリング部６は、ボトムアップスケジューリング部５によって計算されたルートスケジューリンググループのスケジューリング結果を参照し、スケジューリング結果が目標レイテンシに達しておらず、かつ、スケジューリング時間がまだ最大スケジューリング時間に達していない場合に、スケジューリング時間の許す範囲で、スケジューリングエンジンコア２に入力する「ジョブ」数を徐々に増加させながら、再スケジューリングを実行し、ルートグループのスケジューリング結果のレイテンシ改善を行う。
【００８０】
例えば、２つの「ジョブ」のスケジューリング結果に関して、２つの「ジョブ」の動作スロットと休眠スロットの状況が、それぞれ、図１０の（ａ）の１００１，１００２のようになるとした場合に、（ａ）の１００１のように、休眠状態になっているプロセッサが多い（休眠スロットが多い）「ジョブ」（ここではグループ）がある場合に、（ｂ）のように当該グループを分割して、再スケジューリングを行うことによって、例えば（ｃ）のように休眠状態になっているプロセッサ（休眠スロット）が削減されれば、「実行時間」が短縮できる。
【００８１】
ボトムアップスケジューリングの終了直後には、ジョブ集合（ルートグループ）は、仮想的にルートグループの子供グループに等しい数（高々最大子グループ数）の「ジョブ」から構成されるとみなされて、スケジューリングされている。
【００８２】
トップダウンスケジューリングでは、ルートグループを構成する「ジョブ」の粒度をより細かくして、スケジューリングエンジンコア２を用いた再スケジューリングを実行することで、レイテンシを向上させる。ここで、「ジョブ」（ここではグループ）を分割することによって、スケジューリング結果のレイテンシが単調減少することは、明らかである。ただし、「ジョブ」の粒度を極端に細かくすることは、スケジューリング対象の「ジョブ」数が極端に増加することにつながり、スケジューリングエンジンコア２によるスケジューリングにかかる時間が極端に長くなる事態を招きかねない。よって、本実施形態では、１度に分割する「ジョブ」は１個に限定し、また「ジョブ」は子「ジョブ」に分割するのみとする（いきなり、子「ジョブ」よりもさらに細かい単位に分割することは行わないものとする）。これにより、「ジョブ」数が徐々に増加するように制御する。また、分割を行う「ジョブ」は、分割することでレイテンシを短くする効果が大きいものを、足かせ度演算部７を用いて選択することで、より高速に目的レイテンシに達することが可能である。
【００８３】
以上、トップダウンスケジューリングでは、所望なレイテンシ実現の「足かせ」になっている「ジョブ」（グループ）を、複数の「ジョブ」（子グループ）に分割してルートグループの再スケジューリングをするという手続きを、所望なレイテンシが実現するまで、または時間の許す限り、繰り返す。
【００８４】
より具体的には、  
・ルートグループのスケジューリングに現在用いられている個々の「ジョブ」に関して、足かせ度演算部７を用いて足かせ度を計算し、最も足かせ度が高い「ジョブ」を選択し、  
・選択された「ジョブ」を子グループの単位に分割した上で、スケジューリングエンジンコア２を用いて、ルートグループを再スケジューリングし、  
・終了判定部８を用いて、トップダウンスケジューリングを継続するかどうか判定する。
【００８５】
図１１に、図９の初期解を対象としたトップダウンスケジューリングにおける階層スケジューリングテーブルの変化の様子を例示する。なお、各ハッチングが表す意味は図９と同じである。
【００８６】
この例では、グループを子グループに分割して再スケジューリングを行う手続きを２回行っているが、図９の例の場合、最大８回まで再スケジューリングを行う手続きを繰り返すことができる。
【００８７】
次に、トップダウンスケジューリングで利用する足かせ度演算部７について説明する。
【００８８】
足かせ度演算部７は、「ジョブ」を入力とし、この「ジョブ」が現在のスケジューリング結果において目標レイテンシを実現する上で、どの程度足かせになっているかを計算する。
【００８９】
具体的には、この「ジョブ」の実行期間中に、休眠状態になっているプロセッサが多いほど、この「ジョブ」がより大きな足かせになっていると判断できることから、足かせ度は、例えば、  
足かせ度ｆ１＝「ジョブ」実行時間＊「ジョブ」割り当てプロセッサ数−「ジョブ」のべ実行時間、  
で計算することができる。
【００９０】
例えば、図１２の例の場合、「ジョブ」実行時間＝２、「ジョブ」割り当てプロセッサ数＝３、「ジョブ」のべ実行時間＝４であることから、足かせ度ｆ１＝２＊３−４＝２となる（図１２の１２０１参照）。
【００９１】
足かせ度演算部７は、トップダウンスケジューリング中に、グループを分割するかしないかの判断に用いられるので、トップダウンスケジューリング部６から呼び出されて、階層スケジューリングテーブル管理部１経由で階層スケジューリングテーブルの内容を参照しながら、足かせ度を計算し、計算結果をトップダウンスケジューリング部６に返す。
【００９２】
次に、トップダウンスケジューリングで利用する終了判定部８について説明する。
【００９３】
終了判定部８は、トップダウンスケジューリングを継続するかどうか判定する。現在得られているスケジューリング結果におけるレイテンシが目標レイテンシよりも長く、かつ、スケジューリングに要した時間が最大スケジューリング時間よりも短い場合には、「継続するべき」と返し、そうでない場合には「継続するべきでない」と返す。終了判定部８は、トップダウンスケジューリング中に、トップダウンスケジューリングを継続するかどうかの判断に用いられるので、トップダウンスケジューリング部６から呼び出されて、判定結果をトップダウンスケジューリング部６に返す。
【００９４】
図１３に、本実施形態の階層スケジューリング装置の処理手順の一例を示す。
【００９５】
まず、前処理について説明する。
【００９６】
（ステップＳ１）ジョブ集合のグルーピングと、グルーピング結果を用いた階層スケジューリングテーブルの初期化を行い、ステップＳ２へ進む。
【００９７】
次に、ボトムアップスケジューリング（第１段階）について説明する。  
（ステップＳ２）すべてのグループのスケジューリングが終了しているかどうか判定する。終了している場合には、ステップＳ５へ、終了していない場合には、ステップＳ３へ進む。  
（ステップＳ３）スケジューリングされていないグループであって、かつ、すべての子グループがスケジューリングされているグループを、１個選択する。  
（ステップＳ４）ステップＳ３で選択したグループのスケジューリングを行い、ステップＳ２へ進む。
【００９８】
次に、トップダウンスケジューリング（第２段階）について説明する。  
（ステップＳ５）目標レイテンシが実現されている、または、最大スケジューリング時間に達しているかどうか判定を行う。目標レイテンシが実現されている、または、最大スケジューリング時間に達している場合には、現在得られているルートグループのスケジューリング結果を出力して終了、それ以外の場合には、ステップＳ６へ進む。  
（ステップＳ６）分割されていないグループが存在するかどうか判定する。存在しない場合には、現在得られているルートグループのスケジューリング結果を出力して終了し、それ以外の場合には、ステップＳ７へ進む。  
（ステップＳ７）目標レイテンシ実現の「足かせ」になっているグループを選択する。  
（ステップＳ８）ステップＳ７で選択されたグループを子グループに分割した上でルートグループを再度スケジューリングし、ステップＳ５へ進む。
【００９９】
以上説明してきたように、本実施形態によれば、互いに依存関係のある複数のジョブを複数のプロセッサ上で動作させるシステムにおいて、高速かつスケーラブルなスケジューリングが可能になる。
【０１００】
以下では、これまで説明した実施形態に対する幾つかのバリエーションについて説明する。なお、以下のバリエーションは、適宜組み合わせて実施することが可能である。
【０１０１】
（バリエーション１）
これまでの説明では、目標レイテンシを階層スケジューリング装置への入力として与えて、該目標レイテンシに基づいて再スケジューリングを行うかどうかを判断するものとしたが、その代わりに、目標レイテンシを入力とせず、その代わりに、得られたレイテンシを表示し、（これを見て判断した）ユーザからの再スケジューリングを行うかどうかの指示入力に従うようにしてもよい。
【０１０２】
この場合、階層スケジューリング装置が、終了判定部８に接続されるレイテンシ表示部及び指示入力部（図示せず）を保持し、トップダウンスケジューリング部６は、ルートグループのスケジューリング結果が得られるごとに、そのレイテンシをレイテンシ表示部に表示し、ユーザはこの表示内容を確認した上で、再スケジューリングを行うかどうか指示入力部に入力する。指示入力部が再スケジューリングする旨の指示を入力した場合には、トップダウンスケジューリングが「ジョブ」の分割、再スケジューリングを実行し、指示入力部が再スケジューリングしない旨の指示を入力した場合には、現在得られているスケジューリング結果を出力して終了する。
【０１０３】
（バリエーション２）
これまでの説明では、最大スケジューリング時間を階層スケジューリング装置への入力として与え、該最大スケジューリング時間に基づいて再スケジューリングを行うかどうかを判断するものとしたが、その代わりに、最大スケジューリング時間を入力とせず、その代わりに、現在までにかかったスケジューリング時間を表示し、（これを見て判断した）ユーザからの再スケジューリングを行うかどうかの指示入力に従うようにしてもよい。
【０１０４】
この場合、階層スケジューリング装置が、終了判定部８に接続されるスケジューリング時間表示部及び指示入力部（図示せず）を保持し、トップダウンスケジューリング部６は、ルートグループのスケジューリング結果が得られるごとに現在までにかかったスケジューリング時間をスケジューリング時間表示部に表示し、ユーザはこの表示結果を確認した上で再スケジューリングを行うかどうか指示入力部に入力する。指示入力部が再スケジューリングする旨の指示を入力した場合には、トップダウンスケジューリングが「ジョブ」の分割、再スケジューリングを実行し、指示入力部が再スケジューリングしない旨の指示を入力した場合には、現在得られているスケジューリング結果を出力して終了する。
【０１０５】
（バリエーション３）
次に、足かせ度のバリエーションについて説明する。
【０１０６】
足かせ度演算部７で「ジョブ」の足かせ度を計算する方法には、既に説明した（１）の方法に加えて、例えば次の（２）から（６）の方法も考えられる。
【０１０７】
（１）足かせ度ｆ１＝「ジョブ」実行時間＊「ジョブ」への割り当てプロセッサ数−「ジョブ」のべ実行時間（図１２の１２０１参照）  
（２）足かせ度ｆ２＝「ジョブ」実行期間におけるのべプロセッサ休眠時間（図１４（ａ）参照の１２０２参照）  
（３）足かせ度ｆ３＝ｆ２−ｆ１（図１４（ｂ）の１２０３参照参照）  
（４）足かせ度＝ｆ１／「ジョブ」実行時間  
（５）足かせ度＝ｆ２／「ジョブ」実行時間  
（６）足かせ度＝ｆ３／「ジョブ」実行時間
（バリエーション４）
前述のように、ジョブ集合は、プログラムよって表現される場合もある。本実施形態では、ジョブ集合を表現する特定のプログラミング言語を想定している訳ではないが、ジョブ集合の表現に用いられるプログラミング言語において（ほとんどのプログラミングがそうであるように）ユーザ関数定義とその呼び出しが可能である場合には、関数ごとにグループを定義することによってジョブ集合のグルーピングを行う実施形態も考えられる。その場合には、関数ごとに定義されるグループが最大子グループ数より多い子「ジョブ」（ジョブ、またはグループ）を持つ場合に、このグループの子「ジョブ」をさらに細かい単位に再グルーピングする方法が考えられる。
【０１０８】
また、これまでに、階層スケジューリング装置において、最大子グループ数を入力として、ジョブをグルーピングする際に、各グループの子（ジョブまたはグループ）の数が「最大子グループ数」以下になるようにする説明を行ったが、その代わりに、最大子グループ数を入力とせず、関数によって定義されるグループをそのまま利用する方法も考えられる。
【０１０９】
（バリエーション５）
これまでの説明では、スケジューリングエンジンコアとして、以下の条件を満たすものを想定していた。  
（１）スケジューリング結果の厳密解を求める装置である。  
（２）依存元のジョブは、依存先のジョブが実行終了してから初めて実行することが可能であるという制約も満たすようにスケジューリングを行う装置である。  
（３）ジョブ集合中の各ジョブは、複数存在するプロセッサの中のどれにおいても実行可能であるという制約を満たすようにスケジューリングを行う装置である。
【０１１０】
ここで、スケジューリングエンジンコアとして、上記条件を満たすものとは異なる装置を用いることも可能である。
【０１１１】
第１に、スケジューリングエンジンコアとして、最適なスケジューリング結果の近似解を求めるスケジューリング装置を用いる場合が考えられる。この場合と、上記条件（１）を満たすスケジューリング装置を用いる場合との相違は、スケジューリングエンジンコアの相違のみである。ただし、スケジューリングエンジンコアとして、スケジューリング結果の近似度が高く、ジョブの数が多い場合に非常に長いスケジューリング時間を要する装置を採用するほど、スケジューリングエンジンコアを単体で用いる場合に比べて階層スケジューリング装置におけるスケジューリング時間短縮の効果が大きいと言える。また、スケジューリングエンジンコアが過去に行ったスケジューリング結果を保持し、同一のジョブ集合が入力された場合に、再度スケジューリングを行うことなく、過去のスケジューリング結果をそのまま再利用する方法も考えられる。
【０１１２】
第２に、スケジューリングエンジンコアとして、依存先ジョブの実行が終了する前であっても、依存元ジョブの実行を開始するプロセッサ割り当てを行うスケジューリング装置を用いる場合が考えられる。
【０１１３】
図１５（ａ）に示した「ジョブ」Ａ、「ジョブ」Ｂの２個の「ジョブ」を、スケジューリングエンジンコアを用いてスケジューリングする場合について考える。ただし、ここで、「ジョブ」Ａは、Ａ１、Ａ２、Ａ３の３個のジョブから構成され、「ジョブ」Ｂは、Ｂ１、Ｂ２、Ｂ３の３個のジョブから構成され、さらに、ジョブＡ１はジョブＢ１に、ジョブＡ２はジョブＢ２に、ジョブＡ３はジョブＢ３にそれぞれ依存しているものとする。
【０１１４】
図１５（ｂ）に、上記条件（２）を満たすスケジューリングエンジンコアで、これら２個のジョブをスケジューリングした結果の一例を示す。この場合、「ジョブ」Ａは「ジョブ」Ｂに依存しているため、「ジョブ」Ｂの実行が終了してから、「ジョブ」Ａが開始するようにスケジューリングされる。
【０１１５】
図１５（ｃ）に、依存先ジョブの実行が終了する前であっても、依存元ジョブの実行を開始するプロセッサ割り当てを行うスケジューリング装置で、これら２個のジョブをスケジューリングした結果の一例を示す。この場合、ジョブＡ１がジョブＢ１実行終了後に、ジョブＡ２がジョブＢ２実行終了後に、ジョブＡ３がジョブＢ３実行終了後にそれぞれ実行開始するように、「ジョブ」Ａと「ジョブ」Ｂとがスケジューリングされている。この場合は、個々のグループがいくつのプロセッサを用いて、どれだけの時間で実行されるかという図６に記載されている情報に加えて、より詳細な情報、つまりグループ実行時にグループの個々の子「ジョブ」がいくつのプロセッサを利用して、いつ実行されるかが必要とされる。
【０１１６】
図１６に、この場合のスケジューリングテーブルの一例を示す。
【０１１７】
第３に、スケジューリングエンジンコアとして、ジョブ集合中のジョブごとに実行可能なプロセッサが限定されている場合に、制約を満たすようにプロセッサ割り当てを行うことが可能なスケジューリング装置を用いる場合が考えられる。この場合には、スケジューリングエンジンコアが、利用プロセッサ「名」ごとにジョブ集合をスケジューリングした結果を返し、この結果を利用して後段のボトムアップスケジューリング、トップダウンスケジューリングを実行する。
【０１１８】
図１７に、この場合のスケジューリングテーブルの一例を示す。
【０１１９】
以下では、グルーピングの具体例について説明する。
【０１２０】
ここで、グルーピング方法の一例として簡単なアルゴリズムによるものを示す。もちろん、このアルゴリズムは一例であり、本実施形態のグルーピング方法は、以下で説明するアルゴリズムに限定されるものではない。
【０１２１】
ここで、１グループ中の子供グループ（子供ジョブ）の個数は、高々、ｎであるとする。
【０１２２】
（第１段階）データフローグラフ中のジョブを、トポロジカルソートする（なお、トポロジカルソートについては例えば文献“クリフォード・シェーファー (久野禎子、久野靖訳)、Ｊａｖａ（登録商標）によるデータ構造とアルゴリズム解析入門、ピアソン・エデュケーション、２０００”に詳しく開示されている）。トポロジカルソートされた結果において、ジョブＡが依存するジョブＢは、必ず、ジョブＡより前に配置される。
【０１２３】
図１８の（ａ）に、１５個のジョブからなるデータフローグラフの一例を示し、（b）にそのトポロジカルソートの結果を示す。図中、矩形は、ジョブを示し、矩形中の番号は、ジョブの識別情報を示す。また、（ｂ）においては、左端のジョブ１が先頭であり、以下、右に向かって順番に並んでいる。
【０１２４】
（第２段階）トポロジカルソートされたジョブを先頭から順番にｎ個ずつのグループにまとめる。ただし、ジョブの総数はｎの倍数になっているとは限らないので、最後のグループの子ジョブ数はｎ未満になっていても構わないとする。
【０１２５】
この手続きをグループ数が１になるまで繰り返し行なう。
【０１２６】
図１９に、ｎ＝３として図１８のデータフローグラフをグルーピングした結果の一例を示す。この例では、グループ１〜３が一つのグループにまとめられ、それ以外が、もう一つのグループにまとめられている。この例では、ここで、グルーピングが完了する。
【０１２７】
次に、スケジューリングエンジンコア２によるスケジューリングとスケジューリングの結果についてより詳しく説明する。
【０１２８】
階層スケジューリング装置において、スケジューリングエンジンコア２は、ジョブ集合とプロセッサ数を入力とし、例えば、個々のジョブに関して、  
・いつから、  
・どれだけの期間、  
・どのプロセッサを利用して、  
実行するか決定する。
【０１２９】
階層スケジューリングテーブル管理部１では、この結果を受け、必要な情報を階層スケジューリングテーブルに記憶する。
【０１３０】
より具体的には、例えば、次のような内容を格納する。  
（１）図６の第１の例のように、利用プロセッサ「数」ごとに、ジョブ集合全体の「実行時間」と「のべ実行時間」を格納する。  
（２）図１６の第２の例のように、上記第１の例の情報に加えて、個々のジョブに関して、「いつから」、「いくつのプロセッサを利用して」、実行するかを格納する。  
（３）図１７の第３の例のように、利用プロセッサ「名」ごとに、ジョブ集合全体の「実行時間」と「のべ実行時間」のみを格納する。
【０１３１】
階層スケジューリング装置として最終的に得られるスケジューリング結果は、階層スケジューリングテーブルに格納する情報に依存する。
【０１３２】
上記の（１）や（３）のようにジョブ集合「全体」がどれだけの時間かかって実行されるかのみを格納する場合には、最終的に得られるスケジューリング結果は、ジョブ集合全体がどれだけの時間かかって実行されるかという内容（上記の（２）に比較して粗いスケジューリング結果）になる。
【０１３３】
一方、上記の（２）のように「個々」のジョブに関して、「いつから」、「いくつのプロセッサを利用して」、実行するか格納する場合には、最終的に得られるスケジューリング結果は、「個々」のジョブに関して、いつから、いくつのプロセッサを利用して、実行するかという内容（上記の（１）や（３）に比較して細かいスケジューリング結果）になる。
【０１３４】
なお、これまでの説明は、上記の（１）のスケジューリングテーブルを想定して行ったものであり、この場合には、スケジューリング結果は、上記のように、ジョブ集合全体がどれだけの時間かかって実行されるかという内容（より粗いスケジューリング結果）になるが、個々のジョブをどのタイミングでどの（いくつの）プロセッサで実行するかについてのスケジューリング結果を得たい場合には、例えば上記の（２）のように、より細かい結果が得られるようなスケジューリングテーブルを用いればよい。
【０１３５】
例えば、図２０に示すように、「ジョブ」グループＡと「ジョブ」グループＢからなる「ジョブ」グループＣがあり、「ジョブ」グループＡがジョブ１とジョブ２からなり、「ジョブ」グループＢがジョブ３とジョブ４からなり、各ジョブは１個のプロセッサで１単位時間で実行可能であり、プロセッサ数を２とする。この場合に、図１６の例のスケジューリングテーブルの具体例は、例えば、「ジョブ」グループＡについては図２１、「ジョブ」グループＢについては図２２、「ジョブ」グループＣについては図２３のようになる。
【０１３６】
もちろん、上記の（１）〜（３）は一例であり、これらの他にも（より細かいスケジューリング結果が得られるものについても、より粗いスケジューリング結果が得られるものについても）種々の形態が可能である。
【０１３７】
なお、スケジューリングテーブルに格納されるのは、「ジョブ」（グループを仮想的に１個のジョブとみなす場合におけるその仮想的な１個のジョブ、または、本来のジョブ）のスケジューリング結果であって、最小のジョブの粒度のスケジューリング結果を得るためには、複数のスケジューリングテーブルを組み合わせればよい。
【０１３８】
例えば、「ジョブ」Ｃのスケジューリングテーブルに記憶されるのは、「ジョブ」Ｃの子「ジョブ」である「ジョブ」Ａと「ジョブ」Ｂのスケジューリング結果であり、ジョブ１〜４の粒度でのスケジューリング結果は直接的には記憶されない。図２４（ａ）のように、ジョブ１，２については「ジョブ」Ａのスケジューリングテーブルに記憶され、ジョブ３，４については「ジョブ」Ｂのスケジューリングテーブルに記憶され、図２４（ｂ）のように、それらスケジューリングを組み合わせて、ジョブ１〜４の粒度でのスケジューリング結果が得られる。
【０１３９】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０１４０】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１４１】
【図１】本発明の一実施形態に係る階層スケジューリング装置の構成例を示す。
【図２】スケジューリングエンジンコアについて説明するための図
【図３】スケジューリングについて説明するための図
【図４】データフローグラフ及び階層的グルーピングについて説明するための図
【図５】階層的グルーピング及び階層スケジューリングテーブルについて説明するための図
【図６】スケジューリングテーブルの一例を示す図
【図７】実行時間及びのべ実行時間について説明するための図
【図８】ボトムアップスケジューリングについて説明するための図
【図９】ボトムアップスケジューリングについて説明するための図
【図１０】トップダウンスケジューリングについて説明するための図
【図１１】トップダウンスケジューリングについて説明するための図
【図１２】足かせ度について説明するための図
【図１３】同実施形態に係る階層スケジューリング装置の処理手順の一例を示すフローチャート
【図１４】足かせ度について説明するための図
【図１５】ジョブの重なり実行について説明するための図
【図１６】スケジューリングテーブルの他の例を示す図
【図１７】スケジューリングテーブルの更に他の例を示す図
【図１８】グルーピングについて説明するための図
【図１９】グルーピングについて説明するための図
【図２０】スケジューリング結果について説明するための図
【図２１】スケジューリング結果について説明するための図
【図２２】スケジューリング結果について説明するための図
【図２３】スケジューリング結果について説明するための図
【図２４】スケジューリング結果について説明するための図
【符号の説明】
【０１４２】
１…階層スケジューリングテーブル管理部、２…スケジューリングエンジンコア、３…階層スケジューリングテーブル保存部、４…初期化部、５…ボトムアップスケジューリング部、６…トップダウンスケジューリング部、７…足かせ度演算部、８…終了判定部
【図１】
2009070264.tif 000003
【図２】
2009070264.tif 000004
【図３】
2009070264.tif 000005
【図４】
2009070264.tif 000006
【図５】
2009070264.tif 000007
【図６】
2009070264.tif 000008
【図７】
2009070264.tif 000009
【図８】
2009070264.tif 000010
【図９】
2009070264.tif 000011
【図１０】
2009070264.tif 000012
【図１１】
2009070264.tif 000013
【図１２】
2009070264.tif 000014
【図１３】
2009070264.tif 000015
【図１４】
2009070264.tif 000016
【図１５】
2009070264.tif 000017
【図１６】
2009070264.tif 000018
【図１７】
2009070264.tif 000019
【図１８】
2009070264.tif 000020
【図１９】
2009070264.tif 000021
【図２０】
2009070264.tif 000022
【図２１】
2009070264.tif 000023
【図２２】
2009070264.tif 000024
【図２３】
2009070264.tif 000025
【図２４】
2009070264.tif 000026