(57)【要約】  タスク依存関係のグラフ表現の仕様は、異なるタスクとそれぞれが関係付けられる複数のタスク要素と、複数の接続場所を有するリソース要素と、関係付けられる複数の接続場所でリソース要素にタスク要素を結合するリンク要素とを有する。リソース要素上の接続場所への時間タスク要素の関係付けは、タスク要素と関係付けられるタスクに関する順序制約を規定する。タスクは、タスク依存関係のグラフ表現に従って実行される。
2007528080.tif 000002
【特許請求の範囲】
【請求項１】
コンピューターシステム内のタスク実行を制御するための方法であって、
異なるタスクとそれぞれが関係付けられる複数のタスク要素、
複数の接続場所を有するリソース要素、および、
前記複数の接続場所で、前記タスク要素を前記リソース要素に結合するリンク要素であって、前記リソース要素上の接続場所へのタスク要素の結合は、前記タスク要素と関係付けられる前記タスクに関する実行順序制約を規定する、リンク要素を有するタスク依存関係のグラフ表現の仕様を受け入れるステップを含む方法。
【請求項２】
更に、タスク依存関係の前記グラフ表現に従って前記タスクを実行するステップを含む請求項１の方法。
【請求項３】
前記タスク要素が、前記グラフ表現内にノードを含み、前記リンク要素が、前記グラフ表現内にリンクを含む請求項１の方法。
【請求項４】
前記リソース要素はタイムラインを備え、前記接続場所が前記タイムライン上の点と関係付けられている請求項１の方法。
【請求項５】
前記リソース要素が、前記タスクによるアクセスのために計算リソースと関係付けられている請求項１の方法。
【請求項６】
前記計算リソースが格納リソースを含む請求項５の方法。
【請求項７】
前記計算リソースがデータテーブルを含む請求項５の方法。
【請求項８】
コンピュータ可読媒体上に格納したデータ構造であって、
複数のタスク要素のデータ表現と、
複数の接続場所のデータ表現と、
前記タスク要素を前記接続場所に関係付けるデータであって、タスク要素の接続場所への関係付けは、前記タスク要素と関係付けられるタスクに関する順序制約を規定する、データとを含むデータ構造。
【請求項９】
前記データ構造は、リソースと関係付けられる請求項８のデータ構造。
【請求項１０】
前記リソースが、前記タスクによるアクセスのために計算リソースと関係付けられる請求項８のデータ構造。
【請求項１１】
前記計算リソースが格納リソースを含む請求項１０のデータ構造。
【請求項１２】
前記計算リソースがデータテーブルを含む請求項１０のデータ構造。
【請求項１３】
タスク実行システムであって、
データモデルに適合するデータを含む収納庫であって、前記データモデルは、
異なるタスクとそれぞれ関係付けられる複数のタスク要素、
複数の接続場所を有するリソース要素、および、
前記複数の接続場所で前記タスク要素を前記リソース要素と結合するリンク要素であって、前記リソース要素上の接続場所へのタスク要素の結合は、前記タスク要素と関係付けられる前記タスクに関する実行順序制約を規定する、リンク要素を含む、収納庫と、
前記収納庫へのアクセスを有するとともに、タスク依存関係の前記グラフ表現に従って、前記タスクを実行するよう構成されるタスク実行モデルとを含むシステム。
【請求項１４】
前記タスク要素は、前記グラフ表現内にノードを備え、前記リンク要素は、前記グラフ表現内にリンクを備える請求項１３のシステム。
【請求項１５】
前記リソース要素はタイムラインを備え、前記接続場所が前記タイムライン上の点と関係付けられている請求項１３のシステム。
【請求項１６】
前記リソース要素が、前記タスクによるアクセスのために計算リソースと関係付けられる請求項１３のシステム。
【請求項１７】
前記計算リソースが格納リソースを含む請求項１６のシステム。
【請求項１８】
前記計算リソースがデータテーブルを含む請求項１６のシステム。
【請求項１９】
タスク実行システムであって、
異なるタスクとそれぞれが関係付けられる複数のタスク要素、
複数の接続場所を有するリソース要素、および、
前記複数の接続場所で、前記タスク要素を前記リソース要素に結合するリンク要素であって、前記リソース要素上の接続場所へのタスク要素の結合は、前記タスク要素と関係付けられる前記タスクに関する実行順序制約を規定するリンク要素を有するタスク依存関係のグラフ表現の仕様を受け入れるための手段と、
タスク依存関係の前記グラフ表現に従って前記タスクを実行するための手段とを含むシステム。
【請求項２０】
前記タスク要素が、前記グラフ表現内にノードを含み、前記リンク要素が、前記グラフ表現内にリンクを含む請求項１９のシステム。
【請求項２１】
前記リソース要素はタイムラインを備え、前記接続場所が前記タイムライン上の点と関係付けられている請求項１９のシステム。
【請求項２２】
前記リソース要素が、前記タスクによるアクセスのために計算リソースと関係付けられる請求項１９のシステム。
【請求項２３】
前記計算リソースが格納リソースを含む請求項２２のシステム。
【請求項２４】
前記計算リソースがデータテーブルを含む請求項２２のシステム。
【請求項２５】
コンピューターシステム内のタスク実行を制御するための方法であって、
異なるタスクとそれぞれが関係付けられる複数のタスク要素、
リソース要素、および、
前記複数の接続場所で、前記タスク要素と関係付けられる前記タスクに関する実行順序制約を定義する時間順シーケンスで、前記タスク要素を前記リソース要素に結合するリンク要素、
を有するタスク依存関係のグラフ表現の仕様を受け入れるステップと、
タスク依存関係の前記グラフ表現に従って、前記タスクを実行するステップとを含む方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
発明の背景
本発明はタスク実行の制御に関する。
【０００２】
計算システム内の計算タスクは、幾つかのタスクが、他のタスクの前後に、実行を開始または終了しなければならないという制約を受ける依存関係を有することが多い。タスクに部分的な順序を課して、かかる制約に応じることができる。タスクは、同一または異なるランタイム環境内で実行される処理により、同時実行の潜在能力を有する幾つかのタスクとともに実行できる。タスク依存関係の制約の仕様に従って制御処理を実施して、タスク実行を開始またはモニタできる。
【０００３】
図１Ａは、タスク間の依存関係を表すグラフの一例として「依存関係グラフ」を示す。ノードはタスクを表し、有向リンクは、依存関係の制約を表す。この例では、タスク間の依存関係は、共通データ構造、この場合はテーブルへのアクセスによってもたらされる。テーブル初期化タスク１０２は、テーブルサイズを設定し、テーブル内に既定値を入力する。テーブルロードタスク１０４は、テーブルの行にデータ記録セットを書き込む。第１リンク１０６は、テーブルロードタスク１０４の前に、テーブル初期化タスク１０２が実行しなければならないことを規定している。アンテーブルロードタスク１０８は、後続の計算で用いるために、テーブルの行からデータ記録を読み取る。第２リンク１１０は、アンテーブルロードタスク１０８の前に、テーブルロードタスク１０４が実行しなければならないことを規定している。リンクの方向性は、実行順序を指示している。アンテーブルロードタスク１０８の前に、テーブル初期化タスク１０２が実行しなければならないことにも暗黙の依存関係がある。
【０００４】
計算システム内で実行されるタスクに変更がある場合（例えば、タスクの追加または削除による）、対応する依存関係グラフを変更する必要がある。図１Ｂを参照すると、依存関係グラフ１００は、テーブルロードタスク１０４と、アンテーブルロードタスク１０８との間に、ソートテーブルタスク１１４が含まれるように、グラフ１１２で修正されている。テーブルロードタスク１０４とアンテーブルロードタスク１０８との間のリンク１１０は、テーブルロードタスク１０４とソートテーブルタスク１１４との間のリンク１１６、およびソートテーブルタスク１１４とアンテーブルロードタスク１０８との間のリンク１１８により置換される。
【０００５】
依存関係グラフは、タスクを同時に実行させるという制約を規定できる。タスクグループのどれか一つは、先行するタスクの後に実行できる。より一般的には、非循環型有向グラフで表される依存関係をもつタスク間の部分的な順序を決定するよう規則を公式化できる。依存関係グラフ内のタスク間の部分的な順序に対する規則の例は（規則１）「先行タスク」から「後継タスク」まで、グラフを通る有向パスが存在する場合、後継タスクは、先行タスクが実行を終了するまで、開始してはならない。
【０００６】
図１Ｃは、テーブルの部分に操作（例えば、読み出し、ソート等）を実行する３つのタスクからなる第２グループ１２４の何れかが実行を開始する前に、テーブルの異なる部分をロードする３つのタスクからなる第１グループ１２２が、実行を全て終了させなければならないという依存関係グラフ１２０を示す。この例は、幾つかの依存関係グラフに存在しうる潜在的複雑さを示している。この種の構造をもつグラフでは、第１グループのタスク数（この例では３本）と、第２グループのタスク数（この例では３本）との積として、グループ間のリンク数（この例では９本）が増加する。また、テーブル初期化タスク１２６から第１グループ１２２のそれぞれのタスクにリンクがあり、第２グループ１２４のそれぞれのタスクからアンテーブルロードタスク１２８にリンクがある。
【０００７】
概要
一般的な態様では、本発明は、コンピューターシステム内のタスク実行を制御するための方法を特徴とする。タスク依存関係のグラフ表現の仕様は、異なるタスクとそれぞれが関係付けられる複数のタスク要素と複数の接続場所を有するリソース要素とタスク要素を複数の関係付けられた接続場所でリソース要素に結合するリンク要素とを有する。タスク要素のリソース要素上の接続場所への関係付けは、タスク要素と関係付けられるタスクに関する順序制約を規定する。タスクは、タスク依存関係のグラフ表示に従って実行される。
【０００８】
この態様は、以下の特徴の内の一つ以上を含むことができる：
【０００９】
グラフ表現では、タスク要素は、ノードを含み、リンク要素はリンクを含む。
【００１０】
リソース要素は、タイムライン上の点と関係付けられる接続場所をもつタイムラインを含む。
【００１１】
リソース要素は、タスクがアクセスするための計算リソースと関係付けられる。計算リソースは、データテーブル等の格納リソースを含むことができる。
【００１２】
本発明の態様は、以下の利点の内の一つ以上を含むことができる：
【００１３】
タスク依存関係のグラフ表現でリソース要素を用いると、順序制約と関係付けられるリソースとの相互作用の明示的な視覚化が可能になる。これにより、ユーザは、構成時点で、かかる順序制約をグラフ的に規定するか、ランタイムでのタスク実行および相互作用を監視できる。
【００１４】
タスク依存関係のグラフ表現でリソース要素を用いると、同一リソースと相互作用する多数のタスクと関係付けられるリンクが多数となる可能性を減少させることができる。
【００１５】
リソースと関係付けられるタイムラインは、リソースとの一連の相互作用により順序制約の簡単な視覚表現を提供できる。
【００１６】
本発明の他の特徴および利点は、以下の説明および特許請求の範囲から明らかである。
【００１７】
説明
ランタイム環境で実行または開始されるタスク間の依存関係制約を満たす一方法は、依存関係のグラフ表現を、これら依存関係の仕様として受け入れる制御処理を実装することによる。制御処理は、タスク依存関係のグラフ表現に従って、タスクの実行を（同一または異なるランタイム環境内で）開始する。例えば、ユーザは、グラフのノードおよびリンクをそれぞれタスクおよび依存関係とグラフィカルユーザーインターフェースを用いて関係付けることにより、依存関係グラフを構築できる。代替として、依存関係グラフは、明示的または暗示的順序制約に基づいて自動的に生成できる。依存関係グラフが生成されると、ユーザは、グラフィカルユーザーインターフェースを介してグラフを見ることができる。
【００１８】
リソースと相互作用するタスクグループと関係付けられる依存関係グラフにおける制約を表す第１の手法は、リソース要素を依存関係グラフに含めて、タスクの部分的な順序を、より効率的に規定することである。リソース要素は必ずしも処理タスクと関係付けられない。リソース要素を用いて、（一対のタスク間、またはタスクグループ間の）順序制約を規定し、その制約と関連するリソースを識別する。
【００１９】
例えば、図１Ｃに示す依存関係グラフ１２０を修正して、タスクがアクセスするテーブルを表すリソース要素を含めることができる。図２Ａを参照すると、依存関係グラフ２００には、タスクノードと併せて、グラフ内の別のノードとして表されるテーブルリソース要素２０２が含まれる。３つのタスクの第１グループ１２２は、ここでは、テーブルリソース要素２０２の「入力」接続場所２０４にリンクされ、３つのタスクの第２グループ１２４は、テーブルリソース要素２０２の「出力」接続場所２０６にリンクされる。この種の構造のグラフでは、グループ間のリンク数（この例では６本）は、２つのグループそれぞれのタスク数（この例では３つ）と比例して増加する。これは、リンク数に対する複雑さを減少させるという大きな可能性を表す。
【００２０】
タスクノードだけをもつ依存関係グラフに関しては、タスク間の部分的な順序について同一の規則を図２Ａに示す種類の依存関係グラフに用いることができる（規則１）。すなわち、「先行タスク」から「後継タスク」まで、グラフを通る有向パスが存在する場合、後継タスクは、先行タスクが実行を終了するまで、開始してはならない。リソースと関係付けられるノードを、そのリソースとの相互作用により先行／後継関係を有する個々のタスクの任意の対またはタスクグループに対して、グラフに加えることができる。
【００２１】
制約を表す第２の手法は、リソースとの一連の相互作用に関する制約の表現を提供することができる。先の手法におけるように、リソースを表すグラフ要素をグラフに導入する。このグラフ要素は、リソースとの多数の相互作用に対する順序制約を規定するように用いられるタイムラインを含む。「タイムラインリソース要素」により、リソースと相互作用するタスクグループの実行順序の視覚的な指示が可能になる。タスクは、タスク実行順序と対応する順序で、タイムラインリソース要素にリンクされている。
【００２２】
図２Ｂを参照すると、依存関係グラフ２２０は、タイムラインリソース要素２２２を含んでいる。タスクは、タイムラインリソース要素２２２上の接続場所２２３〜２２６にリンクされ、タイムラインリソース要素２２２上の接続場所の相対位置は、タイムラインリソース要素２２２にリンクされるタスクに対する順序制約を定義する（接続場所２２３〜２２６の内の任意の２つの間の距離は、対応するタスクを実行する間の実際の時間と必ずしも関連していない）。同時に実行できるリソースと相互作用するタスクは、タイムライン上の同一接続場所にリンクされる。タスクは、タイムライン上の接続場所に従って時間シーケンス（この例では左から右へ）で実行される。このグラフ２２０では、タスクの第１グループ１２２に対する接続場所２２４と、タスクの第２グループに対する接続場所２２５との相対位置は、グラフ１２０および２００で規定するのと同一の、タスクグループに対する順序制約を規定する。また、接続場所２２３に、テーブル初期化タスク１２６からタイムラインリソース要素２２２までの単一リンクがあり、接続場所２２６に、タイムラインリソース要素２２２からアンテーブルロードタスク１２８までの単一リンクがあり、グラフ１２０および２００で規定するのと同一の、これらタスクに対する順序制約を規定する。
【００２３】
タイムラインリソース要素により識別されるリソースは、この例ではテーブル２２１のようにリソースの種類に従ってグラフで表すことができる。タイムラインリソース要素により識別されるリソースは、任意の各種リソースとすることができる（例えば、データベーステーブル、直列または並列のファイル、格納装置、待ち行列等）。リソース内容は、タイムラインリソース要素にリンクされる最初のタスクの実行の前に存在させてもよく、またはリソースは、タイムラインリソース要素にリンクされる最初のタスクにより実行されるアクションにより、完全に、または部分的に生成してもよい。例えば、リソース要素にリンクされる最初のタスクは、グラフのリソース要素が識別するテーブルまたはファイルを生成するコマンドを実行できる。そのテーブルまたはファイルを削除するタイムラインリソース要素に接続した最後のタスクがあってもよい。
【００２４】
この依存関係グラフ２２０にあるタスク間の部分的な順序に対する新規則（規則２）としては、タイムラインリソース要素２２２に接続されるタスクは、前の（すなわち、この例では左への）接続場所で、タイムラインリソース要素２２２に接続される全てのタスクが実行を終了するまで実行を開始してはならない。この新規則（規則２）を前の規則（規則１）と組合せて、タスク間の部分的な順序を規定する新しい形式の依存関係グラフを実装することができる。
【００２５】
図３を参照すると、依存関係グラフ３００は、接続場所３０４〜３０７をもつタイムラインリソース要素３０２を含んでいる。タイムラインリソース要素へのリンクは、テーブル３０１との相互作用に対する順序制約を規定する。グラフ３００は、テーブル３０１との直接相互作用を含まないタスク間の相互作用に対する順序制約を更に規定する「タスク間」リンク３２２および３２４も含む。Ａパート構築タスク３０８は、テーブル３０１にロードすべきデータを生成する。次にＡパートロードタスク３１０は、生成したデータをテーブル３０１にロードする。Ｂパートロードタスク３１２は、Ａパートロードタスク３１０の後に実行され（規則２に従って）、Ａパートロードタスクは、Ａパート構築タスクの後に実行される（規則１に従って）ので、Ｂパートロードタスク３１２が、Ａパート構築タスク３０８の後に実行されるのも真である。
【００２６】
依存関係グラフ３００は、また、同時に（または規定されない順序で）発生する幾つかのタスクを規定する。Ｂパートロードタスク３１２が実行を終了した後、２つのタスク（例えば、Ｂパートロードタスクと異なるプロセッサで実行される）が、任意の順序でテーブル３０１にアクセスできる。テーブルコピータスク３１４は、テーブル３０１内のデータ全てをある場所にコピーし、Ｂパートアンロードタスク３１６は、データをテーブル３０１からｆｔｐタスク３１８がアクセスするための一時的な場所にアンロードする。ｆｔｐタスク３１８は、Ｂパートアンロードタスク３１６の後に実行する（例えば、一時的な場所からデータを転送する）順序制約を有する（規則１による）が、ｆｔｐタスク３１８は、テーブルコピータスク３１４の前、後、または同時に実行してもよい。また、規則２は、テーブル削除タスク３２０に制約を与えて、テーブルコピータスク３１４、およびＢパートアンロードタスク３１６の両方が実行を終了した後に実行するが、テーブル削除タスク３２０は、ｆｔｐタスク３１８の前、後、または同時に実行してもよい。グラフ３００が規定するタスク順序の例は、２つの規則（規則１および規則２）を組合せて適用して、グラフ内のタスク間順序を規定できる方法を示す。他の順序規則を公式化して、タイムラインリソース要素をタスク依存関係の他のグラフ表現と組合せて、一貫した順序制約を生み出すこともできる。
【００２７】
タイムラインリソース要素へのリンクは、有向である必要はないが、方向性を用いて、タスクとリソースとの間の生産関連性または消費関連性等のタスクの相互作用および／または関連性の特徴、または局面を指示できる。例えば、図４は、接続場所４０３〜４０６で、タイムラインリソース要素４０２（例えば、ファイル４０１を識別する）に接続される有向リンクを有する依存関係グラフ４００を示す。第１タスク４０８は、生産関連性（例えば、タスク４０８はファイル４０１にデータを書き込む）を指示する有向リンクにより、タイムラインリソース要素４０２にリンクされる。第２タスク４１０および第３タスク４１２は、消費関連性（例えば、タスク４１０および４１２はファイル４０１からデータを読み取る）を指示する有向リンクにより、タイムラインリソース要素４０２にリンクされる。次いで、第４タスク４１４は、生産関連性によりリンクされる。
【００２８】
場合によっては、リンクの方向性は、タスク依存関係を変更せずにタスク再順序化を可能にする情報を提供できる。かかる場合の一つには、生産関連性が、タスクがリソースの状態を変更できる関連性である場合、および消費関連性が、リソースの状態を変更しない関連性である場合、隣接する消費タスクは、再順序化されてもよい。例えば、依存関係グラフ４００では、第２タスク４１０、および第３タスク４１２（ともに消費タスク）の位置は、第１タスク４０８（または任意の前のタスク）または第４タスク４１４（または任意の後のタスク）の動作の何らかの結果に影響を与えることなく、変更できる。
【００２９】
上記の手法は、コンピュータ上で実行するためのソフトウエアを用いて実装できる。例えば、ソフトウエアは、一台以上のプログラムされた、またはプログラム可能な（分散型、クライアント／サーバ、またはグリッド型等の、各種のアーキテクチャからなる）コンピューターシステム上で実行する一つ以上のコンピュータープログラムで手順を形成する。各コンピューターシステムは、少なくとも一つのプロセッサ、少なくとも一つのデータ格納システム（揮発性または不揮発性メモリ、および／または格納素子を含む）、少なくとも一つの入力装置またはポート、および少なくとも一つの出力装置またはポートを含む。ソフトウエアは、例えば、計算グラフの設計および構成と関連する他のサービスを提供するより長いプログラムの一つ以上のモジュールを形成してもよい。本明細書で説明するグラフのノードおよび素子は、コンピュータ可読媒体に格納されているデータ構造またはデータ収納庫に格納されるデータモデルと一致する他の組織化データとして実装できる。
【００３０】
ソフトウエアは、汎用、または特殊用途のプログラマブルコンピュータにより可読なＣＤ−ＲＯＭ等の媒体上に提供されるか、またはそれを実行するコンピュータにネットワークを越えて配信されてもよい（伝搬信号で符号化する）。全ての機能は、特殊用途のコンピュータ上で、またはコプロセッサ等の特殊用途ハードウエアを用いて実行できる。ソフトウエアは、ソフトウエアが規定する計算の異なる部分を異なるコンピュータで実行する分散形式で実装してもよい。かかるコンピュータープログラムはそれぞれ、汎用、または特殊用途プログラマブルコンピュータにより可読な格納媒体または装置（例えば、固体メモリまたは媒体、または磁気式または光式媒体）に格納するか、またはダウンロードし、その格納媒体または装置をコンピューターシステムが読み取って、本明細書で説明した手順を実行する場合に、コンピュータを構成および動作させるのが好ましい。発明性のある本システムは、また、コンピュータープログラムにより構成したコンピュータ可読格納媒体として実装されると考えてもよく、そのように構成した格納媒体は、コンピューターシステムに、規定の、かつ所定の方法で本明細書で説明した機能を実行するよう動作させる。
【００３１】
上記説明は、説明を意図したものであり、付帯のクレームの範囲により定義される本発明の範囲を制限する意図はないことは言うまでもない。他の実施の形態は、以下のクレームの範囲内にある。
【図面の簡単な説明】
【００３２】
【図１Ａ】逐次的な依存関係グラフである。
【図１Ｂ】図１Ａの依存関係グラフの修正を示す。
【図１Ｃ】非逐次的な依存関係グラフである。
【図２Ａ】リソース要素をもつ依存関係グラフである。
【図２Ｂ】タイムラインリソース要素をもつ依存関係グラフである。
【図３】タイムラインリソース要素およびタスク間依存関係リンクをもつ依存関係グラフである。
【図４】直接リンクを有するタイムラインリソース要素をもつ依存関係グラフである。
【図１Ａ】
2007528080.tif 000003
【図１Ｂ】
2007528080.tif 000004
【図１Ｃ】
2007528080.tif 000005
【図２Ａ】
2007528080.tif 000006
【図２Ｂ】
2007528080.tif 000007
【図３】
2007528080.tif 000008
【図４】
2007528080.tif 000009
【国際調査報告】
2007528080.tif 000010