(57)【要約】  計算ワークフローの各ノードに関連する各サブタスクに第１のサービス品質識別子が割り振られ、第１のサービス品質識別子は、各ノードに関連するサービス品質の水準を示す。各サブタスクに計画リソース要件が割り振られ、計画リソース要件は、各サブタスクを完了するために必要なシステムリソースの総量を示す。サブタスク毎にリソース割り当て計画が生成され、リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上のシステムリソースの分配を示す。少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対するサービス品質の水準の強制のために、リソース割り当て計画及び第１のサービス品質識別子が少なくとも１つのリソースマネージャに出力される。
2019505861.tif 000002
【特許請求の範囲】
【請求項１】
計算ワークフローにおいてサービス品質を確保するための方法であって、
計画ユニットにおいて、
前記計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振るステップであり、前記第１のサービス品質識別子は、各ノードに割り振られたサービス品質の水準を示すステップと、
前記１つ以上のサブタスクのそれぞれに計画リソース要件を割り振るステップであり、前記計画リソース要件は、前記１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示すステップと、
割り振られた前記第１のサービス品質識別子及び前記計画リソース要件を有する前記１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成するステップであり、前記リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上の前記システムリソースの分配を示すステップと、
前記少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対する前記サービス品質の水準の強制のために、前記リソース割り当て計画及び前記第１のサービス品質識別子を前記少なくとも１つのリソースマネージャに出力するステップであり、前記１つ以上のジョブのそれぞれは、前記１つ以上のサブタスクを含むステップと
を含む方法。
【請求項２】
前記計画ユニットにおいて、
前記少なくとも１つのワークフローオーケストレータ及び前記少なくとも１つのリソースマネージャから、前記１つ以上のサブタスク及び前記１つ以上のジョブの現在の進捗を示す実行情報を取り出すステップと、
前記実行情報から、前記１つ以上のサブタスクのそれぞれの実際のリソース要件を決定するステップと、
前記実際のリソース要件を前記計画リソース要件と比較するステップと、
前記実際のリソース要件が前記計画リソース要件と異なる場合、前記１つ以上のサブタスクのうち少なくとも１つの前記リソース割り当て計画を動的に調整するステップと
を更に含む、請求項１に記載の方法。
【請求項３】
前記計画ユニットにおいて、
前記少なくとも１つのワークフローオーケストレータから、前記計算ワークフローにおけるノードの数と、ノードの間の依存関係と、ノード毎のメタデータとを含む入力データを受信するステップであり、前記メタデータは、ノード識別子と、ノード毎の１つ以上の期限と、各ノードにより実行される１つ以上のコマンドと、ノード毎のリソース要件推定値とを含み、前記１つ以上のサブタスクは、前記入力データに基づいて識別されるステップを更に含む、請求項１に記載の方法。
【請求項４】
前記計画ユニットにおいて、
前記１つ以上のコマンドのうち、前記少なくとも１つのリソースマネージャの動作に影響を与えるコマンドを識別するために、前記１つ以上のコマンドの構文解析を実行するステップと、
前記識別されたコマンドのそれぞれに番号を順次に割り振るステップであり、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むステップと
を更に含む、請求項３に記載の方法。
【請求項５】
前記計画ユニットにおいて、ノード毎の過去の実行履歴に基づいて前記１つ以上のサブタスクを予測するステップと、
前記予測された１つ以上のサブタスクのそれぞれに番号を順次に割り振るステップであり、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むステップと
を更に含む、請求項３に記載の方法。
【請求項６】
前記計画リソース要件を割り振るステップは、前記計画ユニットにおいて、前記１つ以上のサブタスクの間で前記リソース要件推定値を均等に分割するステップを含む、請求項３に記載の方法。
【請求項７】
前記計画リソース要件を割り振るステップは、前記計画ユニットにおいて、ノード毎の過去の実行履歴に基づいて前記１つ以上のサブタスクのそれぞれの前記計画リソース要件を予測するステップを含む、請求項１に記載の方法。
【請求項８】
前記計画リソース要件を割り振るステップは、
前記計画ユニットにおいて、
所定の期間に前記１つ以上のサブタスクのそれぞれを実行するステップと、
前記所定の期間の満了のときに前記１つ以上のサブタスクのそれぞれを終了させるステップと、
前記１つ以上のサブタスクのそれぞれの終了のときに前記１つ以上のサブタスクのそれぞれの現在のリソース使用量サンプルを取得するステップと、
前記現在のリソース使用量サンプルに基づいて前記計画リソース要件をモデル化するステップと
を含む、請求項１に記載の方法。
【請求項９】
前記計画ユニットにおいて、前記１つ以上のサブタスクのうち制御されていないサブタスクを識別するステップであり、それぞれの制御されていないサブタスクは、未知のワークフローに関連するステップを更に含み、
前記計画リソース要件を割り振るステップは、前記計画ユニットにおいて、それぞれの制御されていないサブタスクを完了するために必要なシステムリソースの総量をゼロに設定し、前記制御されていないサブタスクを非ゼロの持続時間を有するものとしてモデル化するステップを含む、請求項１に記載の方法。
【請求項１０】
前記リソース割り当て計画を生成するステップは、前記計画ユニットにおいて、前記１つ以上のサブタスクのそれぞれへのリソース割り当てを割り振る順序を選択し、前記１つ以上のサブタスクのそれぞれの時間上のリソース割り当てを選択し、前記１つ以上のサブタスクのそれぞれの開始時間を選択するステップを含む、請求項１に記載の方法。
【請求項１１】
前記計画ユニットにおいて、前記１つ以上のサブタスクのうち、前記１つ以上の期限を違反したサブタスクを識別し、前記識別されたサブタスクをサブタスク拒否リストに追加し、前記サブタスク拒否リストを出力するステップを更に含む、請求項３に記載の方法。
【請求項１２】
ジョブサブミッタにおいて、前記１つ以上のジョブのそれぞれに、ノード毎のサービス品質の要求水準を示す第２のサービス品質識別子を割り振るステップと、
前記少なくとも１つのリソースマネージャにおいて、前記第１のサービス品質識別子、前記第２のサービス品質識別子及び前記リソース割り当て計画を受信し、前記１つ以上のジョブのうち、前記第２のサービス品質識別子が前記第１のサービス品質識別子に対応するジョブのために前記リソース割り当て計画に従って前記システムリソースを割り当てるステップと
を更に含む、請求項１に記載の方法。
【請求項１３】
前記第２のサービス品質識別子を割り振るステップは、前記１つ以上のジョブの順序を観測し、前記順序に従って前記１つ以上のジョブのそれぞれに番号を割り振るステップであり、前記第２のサービス品質識別子は、前記割り振られた番号及びノード識別子を含むステップを含む、請求項１２に記載の方法。
【請求項１４】
計算ワークフローにおいてサービス品質を確保するためのシステムであって、
少なくとも１つの処理ユニットと、
前記少なくとも１つの処理ユニットに通信可能に結合された過渡的でないメモリであり、
前記計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振り、前記第１のサービス品質識別子は、各ノードに割り振られたサービス品質の水準を示し、
前記１つ以上のサブタスクのそれぞれに計画リソース要件を割り振り、前記計画リソース要件は、前記１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示し、
割り振られた前記第１のサービス品質識別子及び前記計画リソース要件を有する前記１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成し、前記リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上の前記システムリソースの分配を示し、
前記少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対する前記サービス品質の水準の強制のために、前記リソース割り当て計画及び前記第１のサービス品質識別子を前記少なくとも１つのリソースマネージャに出力し、前記１つ以上のジョブのそれぞれは、前記１つ以上のサブタスクを含むために、
前記少なくとも１つの処理ユニットにより実行可能なコンピュータ読み取り可能プログラム命令を含む過渡的でないメモリと
を含むシステム。
【請求項１５】
前記コンピュータ読み取り可能プログラム命令は、
前記少なくとも１つのワークフローオーケストレータ及び前記少なくとも１つのリソースマネージャから、前記１つ以上のサブタスク及び前記１つ以上のジョブの現在の進捗を示す実行情報を取り出し、
前記実行情報から、前記１つ以上のサブタスクのそれぞれの実際のリソース要件を決定し、
前記実際のリソース要件を前記計画リソース要件と比較し、
前記実際のリソース要件が前記計画リソース要件と異なる場合、前記１つ以上のサブタスクのうち少なくとも１つの前記リソース割り当て計画を動的に調整するために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項１６】
前記コンピュータ読み取り可能プログラム命令は、
前記少なくとも１つのワークフローオーケストレータから、ノード毎のノード識別子及び各ノードにより実行される１つ以上のコマンドを受信し、
前記１つ以上のコマンドのうち、前記少なくとも１つのリソースマネージャの動作に影響を与えるコマンドを識別するために、前記１つ以上のコマンドの構文解析を実行し、
前記識別されたコマンドのそれぞれに番号を順次に割り振り、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項１７】
前記コンピュータ読み取り可能プログラム命令は、
前記少なくとも１つのワークフローオーケストレータから、ノード識別子及びノード毎の過去の実行履歴を受信し、
前記過去の実行履歴に基づいて前記１つ以上のサブタスクを予測し、
前記予測された１つ以上のサブタスクのそれぞれに番号を順次に割り振り、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項１８】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のサブタスクのうち制御されていないサブタスクを識別し、それぞれの制御されていないサブタスクは、未知のワークフローに関連し、それぞれの制御されていないサブタスクを完了するために必要なシステムリソースの総量をゼロに設定し、前記制御されていないサブタスクを非ゼロの持続時間を有するものとしてモデル化することを含む、前記計画リソース要件を割り振るために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項１９】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のサブタスクのそれぞれへのリソース割り当てを割り振る順序を選択し、前記１つ以上のサブタスクのそれぞれの時間上のリソース割り当てを選択し、前記１つ以上のサブタスクのそれぞれの開始時間を選択することを含む、前記リソース割り当て計画を生成するために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項２０】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のジョブのそれぞれに、ノード毎のサービス品質の要求水準を示す第２のサービス品質識別子を割り振り、
前記１つ以上のジョブのうち、前記第２のサービス品質識別子が前記第１のサービス品質識別子に対応するジョブのために前記リソース割り当て計画に従って前記システムリソースを割り当てるために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項２１】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のジョブの順序を観測し、前記順序に従って前記１つ以上のジョブのそれぞれに番号を割り振り、前記第２のサービス品質識別子は、前記割り振られた番号及びノード識別子を含むことを含む、前記第２のサービス品質識別子を割り振るために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項２０に記載のシステム。
【請求項２２】
計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振り、前記第１のサービス品質識別子は、各ノードに関連するサービス品質の水準を示し、
前記１つ以上のサブタスクのそれぞれに計画リソース要件を割り振り、前記計画リソース要件は、前記１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示し、
割り振られた前記サービス品質識別子及び前記計画リソース要件を有する前記１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成し、前記リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上の前記システムリソースの分配を示し、
前記少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対する前記サービス品質の水準の強制のために、前記リソース割り当て計画及び前記第１のサービス品質識別子を前記少なくとも１つのリソースマネージャに出力し、前記１つ以上のジョブのそれぞれは、前記１つ以上のサブタスクを含むために、
プロセッサにより実行可能なプログラムコードを記憶したコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願への相互参照］
本出願は、2016年11月18日に出願されたシリアル番号62/423,894を持つ仮特許出願の優先権を主張し、その内容を参照により援用する。本出願はまた、2017年5月30日に出願されたシリアル番号15/607,721を持つ特許出願の優先権を主張し、その内容を参照により援用する。
【０００２】
［分野］
ここに記載の実施例は、概してワークフロー管理の分野に関し、より詳しくは、計算ワークフローにおいてサービス品質を確保することに関する。
【背景技術】
【０００３】
企業データ解析システムでは、典型的には、顧客は、様々な制御システムの動作に影響を有する繰り返し可能で複雑な相互依存のビジネスワークフローを有する。サービスは、いくつかのタスクを同時に実行するためにノードの大規模クラスタを構築することにより、顧客に提供される。異なる顧客は異なる要件及びデータ処理ニーズを有し得るため、正式に交渉されたサービス水準合意（SLA）に従って特定のサービス水準が所与の顧客に提供され得る。典型的には、SLAは、可用性、有用性、性能及び運用のようなサービスの特定の側面を指定する。SLAの違反があった場合、ペナルティもまた指定され得る。
【０００４】
いくつかのワークフローでは、最高位ノードが満たされなければならない厳しい期限を有し、典型的には、異なるノードが異なる期限を有する。さらに、ノードは、共通の祖先に依存する可能性があり、所与のノードにおける遅延は、残りのノードに影響を与える可能性があり、全体システムのSLAが潜在的に損なわれることを引き起こす。しかし、いくつかの制御システムは遅延を経験した場合にタスクを早めるためのサービス品質（QoS）制御手順を有さないため、この問題は、ノードに対するサービスを改善することにより部分的にしか制御できない。
【０００５】
したがって、計算ワークフローにおいてQoSを確保するための改善したシステム及び方法のニーズが存在する。
【発明の概要】
【０００６】
１つの側面によれば、計算ワークフローにおいてサービス品質を確保するための方法が提供される。方法は、計画ユニットにおいて、計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振るステップであり、第１のサービス品質識別子は、各ノードに割り振られたサービス品質の水準を示すステップと、１つ以上のサブタスクのそれぞれに計画リソース要件を割り振るステップであり、計画リソース要件は、１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示すステップと、割り振られた第１のサービス品質識別子及び計画リソース要件を有する１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成するステップであり、リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上のシステムリソースの分配を示すステップと、少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対するサービス品質の水準の強制のために、リソース割り当て計画及び第１のサービス品質識別子を少なくとも１つのリソースマネージャに出力するステップであり、１つ以上のジョブのそれぞれは、１つ以上のサブタスクを含むステップとを含む。
【０００７】
いくつかの例示的な実施例では、方法は、少なくとも１つのワークフローオーケストレータ及び少なくとも１つのリソースマネージャから、１つ以上のサブタスク及び１つ以上のジョブの現在の進捗を示す実行情報を取り出すステップと、実行情報から、１つ以上のサブタスクのそれぞれの実際のリソース要件を決定するステップと、実際のリソース要件を計画リソース要件と比較するステップと、実際のリソース要件が計画リソース要件と異なる場合、１つ以上のサブタスクのうち少なくとも１つのリソース割り当て計画を動的に調整するステップとを含んでもよい。
【０００８】
いくつかの例示的な実施例では、方法は、計画ユニットにおいて、少なくとも１つのワークフローオーケストレータから、計算ワークフローにおけるノードの数と、ノードの間の依存関係と、ノード毎のメタデータとを含む入力データを受信するステップであり、メタデータは、ノード識別子と、ノード毎の１つ以上の期限と、各ノードにより実行される１つ以上のコマンドと、ノード毎のリソース要件推定値とを含み、１つ以上のサブタスクは、入力データに基づいて識別されるステップを含んでもよい。
【０００９】
いくつかの例示的な実施例では、方法は、計画ユニットにおいて、１つ以上のコマンドのうち、少なくとも１つのリソースマネージャの動作に影響を与えるコマンドを識別するために、１つ以上のコマンドの構文解析を実行するステップと、識別されたコマンドのそれぞれに番号を順次に割り振るステップであり、第１のサービス品質識別子は、ノード識別子及び割り振られた番号を含むステップとを含んでもよい。
【００１０】
いくつかの例示的な実施例では、方法は、計画ユニットにおいて、ノード毎の過去の実行履歴に基づいて１つ以上のサブタスクを予測するステップと、予測された１つ以上のサブタスクのそれぞれに番号を順次に割り振るステップであり、第１のサービス品質識別子は、ノード識別子及び割り振られた番号を含むステップとを含んでもよい。
【００１１】
いくつかの例示的な実施例では、計画リソース要件を割り振るステップは、計画ユニットにおいて、１つ以上のサブタスクの間でリソース要件推定値を均等に分割するステップを含んでもよい。
【００１２】
いくつかの例示的な実施例では、計画リソース要件を割り振るステップは、計画ユニットにおいて、ノード毎の過去の実行履歴に基づいて１つ以上のサブタスクのそれぞれの計画リソース要件を予測するステップを含んでもよい。
【００１３】
いくつかの例示的な実施例では、計画リソース要件を割り振るステップは、計画ユニットにおいて、所定の期間に１つ以上のサブタスクのそれぞれを実行するステップと、所定の期間の満了のときに１つ以上のサブタスクのそれぞれを終了させるステップと、１つ以上のサブタスクのそれぞれの終了のときに１つ以上のサブタスクのそれぞれの現在のリソース使用量サンプルを取得するステップと、現在のリソース使用量サンプルに基づいて計画リソース要件をモデル化するステップとを含んでもよい。
【００１４】
いくつかの例示的な実施例では、方法は、計画ユニットにおいて、１つ以上のサブタスクのうち制御されていないサブタスクを識別するステップであり、それぞれの制御されていないサブタスクは、未知のワークフローに関連するステップを含んでもよく、計画リソース要件を割り振るステップは、計画ユニットにおいて、それぞれの制御されていないサブタスクを完了するために必要なシステムリソースの総量をゼロに設定し、制御されていないサブタスクを非ゼロの持続時間を有するものとしてモデル化するステップを含んでもよい。
【００１５】
いくつかの例示的な実施例では、リソース割り当て計画を生成するステップは、計画ユニットにおいて、１つ以上のサブタスクのそれぞれへのリソース割り当てを割り振る順序を選択し、１つ以上のサブタスクのそれぞれの時間上のリソース割り当てを選択し、１つ以上のサブタスクのそれぞれの開始時間を選択するステップを含んでもよい。
【００１６】
いくつかの例示的な実施例では、方法は、計画ユニットにおいて、１つ以上のサブタスクのうち、１つ以上の期限を違反したサブタスクを識別し、識別されたサブタスクをサブタスク拒否リストに追加し、サブタスク拒否リストを出力するステップを含んでもよい。
【００１７】
いくつかの例示的な実施例では、方法は、ジョブサブミッタにおいて、１つ以上のジョブのそれぞれに、ノード毎のサービス品質の要求水準を示す第２のサービス品質識別子を割り振るステップと、少なくとも１つのリソースマネージャにおいて、第１のサービス品質識別子、第２のサービス品質識別子及びリソース割り当て計画を受信し、１つ以上のジョブのうち、第２のサービス品質識別子が第１のサービス品質識別子に対応するジョブのためにリソース割り当て計画に従ってシステムリソースを割り当てるステップとを含んでもよい。
【００１８】
いくつかの例示的な実施例では、第２のサービス品質識別子を割り振るステップは、１つ以上のジョブの順序を観測し、順序に従って１つ以上のジョブのそれぞれに番号を割り振るステップであり、第２のサービス品質識別子は、割り振られた番号及びノード識別子を含むステップを含んでもよい。
【００１９】
他の側面によれば、計算ワークフローにおいてサービス品質を確保するためのシステムが提供される。このシステムは、少なくとも１つの処理ユニットと、少なくとも１つの処理ユニットに通信可能に結合された過渡的でないメモリであり、計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振り、第１のサービス品質識別子は、各ノードに割り振られたサービス品質の水準を示し、１つ以上のサブタスクのそれぞれに計画リソース要件を割り振り、計画リソース要件は、１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示し、割り振られた第１のサービス品質識別子及び計画リソース要件を有する１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成し、リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上のシステムリソースの分配を示し、少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対するサービス品質の水準の強制のために、リソース割り当て計画及び第１のサービス品質識別子を少なくとも１つのリソースマネージャに出力し、１つ以上のジョブのそれぞれは、１つ以上のサブタスクを含むために、少なくとも１つの処理ユニットにより実行可能なコンピュータ読み取り可能プログラム命令を含む過渡的でないメモリとを含む。
【００２０】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、少なくとも１つのワークフローオーケストレータ及び少なくとも１つのリソースマネージャから、１つ以上のサブタスク及び１つ以上のジョブの現在の進捗を示す実行情報を取り出し、実行情報から、１つ以上のサブタスクのそれぞれの実際のリソース要件を決定し、実際のリソース要件を計画リソース要件と比較し、実際のリソース要件が計画リソース要件と異なる場合、１つ以上のサブタスクのうち少なくとも１つのリソース割り当て計画を動的に調整するために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２１】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、少なくとも１つのワークフローオーケストレータから、ノード毎のノード識別子及び各ノードにより実行される１つ以上のコマンドを受信し、１つ以上のコマンドのうち、少なくとも１つのリソースマネージャの動作に影響を与えるコマンドを識別するために、１つ以上のコマンドの構文解析を実行し、識別されたコマンドのそれぞれに番号を順次に割り振り、第１のサービス品質識別子は、ノード識別子及び割り振られた番号を含むために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２２】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、少なくとも１つのワークフローオーケストレータから、ノード識別子及びノード毎の過去の実行履歴を受信し、過去の実行履歴に基づいて１つ以上のサブタスクを予測し、予測された１つ以上のサブタスクのそれぞれに番号を順次に割り振り、第１のサービス品質識別子は、ノード識別子及び割り振られた番号を含むために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２３】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、１つ以上のサブタスクのうち制御されていないサブタスクを識別し、それぞれの制御されていないサブタスクは、未知のワークフローに関連し、それぞれの制御されていないサブタスクを完了するために必要なシステムリソースの総量をゼロに設定し、制御されていないサブタスクを非ゼロの持続時間を有するものとしてモデル化することを含む、計画リソース要件を割り振るために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２４】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、１つ以上のサブタスクのそれぞれへのリソース割り当てを割り振る順序を選択し、１つ以上のサブタスクのそれぞれの時間上のリソース割り当てを選択し、１つ以上のサブタスクのそれぞれの開始時間を選択することを含む、リソース割り当て計画を生成するために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２５】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、１つ以上のジョブのそれぞれに、ノード毎のサービス品質の要求水準を示す第２のサービス品質識別子を割り振り、１つ以上のジョブのうち、第２のサービス品質識別子が第１のサービス品質識別子に対応するジョブのためにリソース割り当て計画に従ってシステムリソースを割り当てるために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２６】
いくつかの例示的な実施例では、コンピュータ読み取り可能プログラム命令は、１つ以上のジョブの順序を観測し、順序に従って１つ以上のジョブのそれぞれに番号を割り振り、第２のサービス品質識別子は、割り振られた番号及びノード識別子を含むことを含む、第２のサービス品質識別子を割り振るために、少なくとも１つの処理ユニットにより実行可能でもよい。
【００２７】
他の側面によれば、計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振り、第１のサービス品質識別子は、各ノードに関連するサービス品質の水準を示し、１つ以上のサブタスクのそれぞれに計画リソース要件を割り振り、計画リソース要件は、１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示し、割り振られたサービス品質識別子及び計画リソース要件を有する１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成し、リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上のシステムリソースの分配を示し、少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対するサービス品質の水準の強制のために、リソース割り当て計画及び第１のサービス品質識別子を少なくとも１つのリソースマネージャに出力し、１つ以上のジョブのそれぞれは、１つ以上のサブタスクを含むために、プロセッサにより実行可能なプログラムコードを記憶したコンピュータ読み取り可能媒体が提供される。
【００２８】
本改善に関する多くの更なる機能及びそれらの組み合わせは、当該開示の読み込みに続いて当業者に明らかになる。
【図面の簡単な説明】
【００２９】
【図１Ａ】一実施例に従って計算ワークフローにおいてサービス品質を確保するための例示的なシステムのブロック図である。
【図１Ｂ】一実施例による計算ワークフローの概略図である。
【図１Ｃ】一実施例に従ってモバイルハンドセットベンダ環境に適用される図１Ａのシステムの概略図である。
【図２】図１Ａのシステムの詳細ブロック図である。
【図３】図２のSLA計画ユニットにおいて提供されるQoS識別子生成モジュールのブロック図である。
【図４】図３のQoS識別子生成モジュールにより実現される例示的な手順を示す。
【図５】図２のジョブサブミッタにおいて提供されるQoS識別子生成モジュールにより実現される例示的な手順を示す。
【図６】図２のリソース要件割り振りモジュールのブロック図である。
【図７】図２の計画フレームワークモジュールのブロック図である。
【図８】図２の実行監視モジュールのブロック図である。
【図９】図２のSLA計画ユニットを実現するための例示的なコンピューティングデバイスのブロック図である。
【図１０】一実施例に従って計算ワークフローにおいてサービス品質を確保するための例示的な方法のフローチャートを示す。
【図１１】ワークフローノード毎の基礎サブタスクを識別し、各サブタスクにQoS識別子を割り振る図１０のステップのフローチャートを示す。
【図１２】サブタスク毎の合計リソース要件を決定する図１０のステップのフローチャートを示す。
【図１３】ノード毎のリソース割り当て計画を生成する図１０のステップのフローチャートを示す。
【図１４】ワークフロー編成及び制御システムのレベルで作業負荷の実際の進捗を監視する図１０のステップのフローチャートを示す。
【図１５】必要に応じて実際のリソース要件に基づいて既存のリソース割り当て計画を更新する図１０のステップのフローチャートを示す。
【図１６】一実施例に従ってQoS識別子を生成し、QoSを強制するために図１Ａの制御システムにおいて実現される例示的な手順のフローチャートを示す。  添付の図面を通じて、同様の機能は同様の参照符号により識別される点に留意する。
【発明を実施するための形態】
【００３０】
図１Ａを参照して、一実施例に従って計算ワークフローにおいてサービス品質（QoS）を確保するための例示的なシステム100について、これから説明する。システム100は、ビジネス層104と基礎システム106との間の中間レイヤとして提供されるサービス水準合意（SLA）計画ユニット102を含む。ビジネス層104は、ゲートウェイクラスタ110の複数の接続されたコンピュータ（一般的にノードと呼ばれ、図示しない）上のアクティビティを組織化及び編成するワークフローオーケストレータ108を含む。ワークフローオーケストレータ108の例は、Oozie、Control-M及びAzkabanを含むが、これらに限定されない。
【００３１】
基礎システム106は、QoS機能を有するシステム（ここでは、制御システムと呼ばれる）と、制御できず且つ以下に更に説明するようにリソースをゼロにモデル化することが望ましいシステム（ここでは、制御されていないシステムと呼ばれる）とを含んでもよい。制御システムの例は、Yet  Another  Resource  Negotiator（YARN）に基づくデータ処理アプリケーションを含むが、これに限定されない。制御されていないシステムの例は、レガシーデータベース、データ転送サービス及びファイルシステム動作を含むが、これらに限定されない。基礎システム106は、ジョブサブミッタ112とリソースマネージャ114とを含む。以下に更に説明するように、ジョブサブミッタ112は、ジョブをリソースマネージャ114にサブミットし、サブミットされたジョブは、ワークフローオーケストレータ108により実行されたアクションから生じる。ジョブサブミッタ112の例は、Hive、Pig、Oracle、TeraData、ファイル転送プロトコル（FTP）、セキュアシェル（SSH）、HBase及びHadoop  Distributed  File  System（HDFS）を含むが、これらに限定されない。
【００３２】
リソースマネージャ114は、ジョブサブミッタ112によりサブミットされたジョブを受信し、サブミットされたジョブを利用可能な制御システムリソースに分配する。ここで使用されるQoSという用語は、実行されているジョブのためのリソース割り当て又はリソース優先順位付けの水準を示す。より詳しくは、リソースマネージャ114は、実際の作業負荷（例えば、以下に更に説明するように、ビジネス層のアクションにより生成された基礎制御システムジョブ）に対してSLA計画ユニット102により行われたシステムリソース割り当て判断を強制し、これにより、タスクをより高速に或いはより低速に実行させる。ここで示されるシステムリソースは、中央処理装置（CPU）使用量、ランダムアクセスメモリ（RAM）使用量及びネットワーク帯域幅使用量を含むが、これらに限定されない。リソースマネージャ114は、QoS強制方式が可能ないずれかの基礎システムでもよいことが理解され得る。したがって、リソースマネージャ114は、スケジューラ（例えば、YARN、Mesos、Platform  Load  Sharing  Facility（LSF）、GridEngine、Kubernetes等）及びQoSを強制する機能が可能なデータウェアハウスシステム（例えば、リレーショナルデータベース管理システム（RDBMS）等）を含んでもよいが、これらに限定されない。
【００３３】
次に図１Ａに加えて図１Ｂを参照すると、ワークフローオーケストレータ108は、ビジネスロジック（例えば、ビジネスユーザにより指定される）をビジネス層ワークフロー116（例えば、ワークフローグラフ）にカプセル化し、繰り返し可能な作業負荷を管理し、継続的な処理を確保する。ここで使用されるビジネス層ワークフローという用語は、ビジネスユーザ（例えば、ワークフローオーケストレータ108のユーザ）により規定された相互依存のビジネス層アクション（ここではアクションとも呼ばれる）118のセットを示す。典型的には、ワークフローレベルで期限が規定され、次に、これは、いくつかのジョブに対して厳しいSLAを課す（完了期限を含むが、これに限定されない）。特に、ビジネスユーザは、ビジネス層アクション及びこれらの依存関係を規定し、これにより、116のようなビジネス層ワークフローを生成する。各ビジネス層アクション118は、ビジネスユーザにより規定されたビジネス層ワークフロー116内の単一のアクションであり、１つ以上の他のビジネス層アクション118の完了に依存してもよく、ゲートウェイクラスタノードの１つの上で実行してもよい。Hiveクエリは、ビジネス層アクションの例である。
【００３４】
ワークフローオーケストレータ108のアクション（例えば、ビジネス層アクション118）は、ゲートウェイクラスタ110により処理されるべきジョブのサブミットを生じる。ゲートウェイクラスタ110は、サブミットされたジョブを基礎システム106のような様々な基礎システムに分配する。いくつかの実施例では、ゲートウェイクラスタ110は、ワークフローオーケストレータ108の制御下にある。他の実施例では、ゲートウェイクラスタ110は、ワークフローオーケストレータ108の制御下にない。
【００３５】
特に、単一のビジネス層アクション118は、制御システムワークフロー120、例えば、相互依存の制御システムジョブ（ここではジョブとも呼ばれる）122のセットを実現してもよい。次に、各制御システムジョブ122は、制御システムワークフロー120の単一のステップを実行するために、基礎システム106にサブミットされる。MapReduceフレームワークでは、制御システムジョブ122の例は、HiveによりYARNにサブミットされるMap/Reduceジョブである。基礎システム106は、ビジネス層104から処理されるべき制御システムジョブ122を受信し、それに従って自分の作業負荷（すなわち、ここでは基礎サブタスクと呼ばれる制御システムタスク124のサブフロー）を生成し、これは、実行のために利用可能な制御システムリソースに分配される。特に、各制御システムジョブ122は、性質及び構造がその作業を実行するために対応するビジネス層ジョブアクションにより使用されるアプリケーションに依存する１つ以上の基礎サブタスク124に分割される。各サブタスク124は、制御システムジョブ122の一部として制御システムのリソースマネージャ114により実行される作業の基本単位を表し、制御システムジョブ122は、所与の制御システムリソース上の単一の処理として実行する。例えば、MapReduceフレームワークでは、サブタスクは、データの１つのブロック上で動作する単一のMapタスク又はReduceタスクでもよい。言い換えると、サブタスク124は、ある期間にクラスタ上で実行する個々の計算コンテナとして見られることができ、これにより、並列で動作するサブタスク124のグループの共同の出力は、所与の制御システムジョブ122の目的を達成する。
【００３６】
次に図１Ｃを参照して、システム100の例示的な実施例について、モバイルハンドセットベンダ環境を参照してこれから説明する。図示の実施例では、複数のモバイルハンドセットユーザ126は、例えば、モバイルハンドセットベンダのオンラインストアで購入を行うこと、モバイルハンドセットベンダの製品を求めてオンラインで検索すること等により、複数のモバイルハンドセットベンダサーバ128と相互作用する。次に、モバイルハンドセットユーザ126とモバイルハンドセットベンダサーバ128との間の相互作用は、ログファイルを含むが、これに限定されないいずれか適切なフォーマットで、データベース130のような適切なメモリに記憶される使用量データを生成する。モバイルハンドセットベンダがビジネス目的のため、例えば、顧客をより良く理解するため、提供をカスタマイズするため、将来の投資方向を選択するため、製品の理解度又は業績を測定するため、等のために、使用量データを活用することが望ましいことがある。このため、使用量データは、ビジネス層104において提供されるワークフローオーケストレータ（図１Ａの参照108）に規定されてこれにより実行されるワークフローのセットを使用して解析されてもよい。図示の実施例では、第１のワークフロー132a及び第２のワークフロー132bがビジネス層104において規定されて実行される。
【００３７】
第１のワークフロー132aは、いずれか適切な手段（例えば、SSH）を使用して使用量データをソースから（例えば、データベース130から）転送するステップ134と、転送されたデータを（例えば、HDFS上で）暗号化して記憶するステップ136とを含む２ステップのワークフローである。第１のワークフロー132aは、インポートされるデータセットの鮮度を確保するために、定期的に（例えば、毎時）実行される。ワークフロー132aの出力は、ビジネス層104内の全てのビジネス単位（図示せず）により共有されてもよく、各ビジネス単位は、データに対する異なる許可レベル及びデータに対して行いたいと思う解析の異なる要件を有する。第２のワークフロー132bもまた、定期的に（例えば、毎日）実行され、第１のワークフロー132aにより記憶されたデータを解読し、所望の結果を計算する解析エンジン（例えば、Hive）による使用のために、解読されたデータを適切なフォーマットにロードするステップ138を含む。次のステップ140は、ロード及び解読されたデータ（例えば、Hiveテーブル）をスキャンし、スキャンされたデータに対して集約動作を実行することである。次に、ステップ142において、集約されたテーブルに対して解析動作が実行され、ステップ144において、結果のデータが将来の使用のためにクエリデータベース（例えば、MySQL）に記憶される。次に、ステップ146において、ビジネス単位のリーダによる使用等のために、レポートが定期的に（例えば、毎日）生成される。図示の実施例では、レポートを生成するステップ146は、毎日厳しい期限（例えば、午前8時）までに実行されるべきである。ワークフロー132a及び132bの実行は、ジョブが基礎システム106にサブミットされることを生じる。例えば、ステップ146において生成されたレポートは、基礎システム106に存在するビジネス単位のリーダ148により消費され、ステップ136において記憶されたデータは、ワークフロー132bにより実行される毎日のタスクによりカバーされない更にきめ細かい解析を実行するために、ビジネス単位のリーダ148（又はデータ解析者のような他のエンティティ）により臨時的に問い合わされてもよい。
【００３８】
ビジネス層104において規定されたワークフロー132a、132bの種類は、データが提供されるビジネス単位に特有であり、各ビジネス単位は、解析動作が実行される自分のバージョンのワークフロー132a、132bを有することが理解されるべきである。各ワークフロー132a、132bはまた、異なる期限を有してもよく、或いは異なる期間に実行してもよい。さらに、図示の実施例では、全てのワークフローは、第１のワークフロー132aとの依存関係を共有する（矢印150により示す）。さらに、そのワークフロー（例えば、ジョブ）を基礎システム106にサブミットする各ビジネス単位は、基礎計算インフラストラクチャの異なる優先度又は異なる配分比率を有してもよい。したがって、全てのジョブが異なるビジネス単位により要求されるとおりに完了することを確保することが望ましい。
【００３９】
図１Ｃに加えて図１Ａに戻って参照すると、以下に更に説明するように、SLA計画ユニット102は、計算ワークフロー内のジョブがユーザにより示された仕様及び／又は要件に対して完了すること（例えば、より高いレベルのワークフローの期限及びSLAが満たされること）を確保するために、ビジネス層104及び基礎システム106とインタフェースするエンティティである。このため、SLA計画ユニット102は、システムリソースが調整されるべき方式を判断する。特に、ビジネス層レベルでの重要なワークフローがこれらの期限及びSLAを満たすことを確保するために、SLA計画ユニット102  SLA計画ユニット102は、以下に更に説明するように、所与の制御システムジョブを完了するための合計リソース要件と、リソースが時間上で異なるタスクに割り当てられるべき方式とを決定する。一実施例では、SLA計画ユニット102は、それが活用することができる最大リソースをジョブに与えることにより、所与のジョブをできるだけ高速に実行することを選択することができる。他の実施例では、SLA計画ユニット102は、依然としてSLAを満たすことができつつ、できるだけ少ないリソースを所与のジョブに与えることを選択することができる。次に、SLA計画ユニット102は、実際のサブミットされた作業負荷に対する強制のために、リソース割り当て判断をリソースマネージャ114に送信する。特に、SLA計画ユニット102は、基礎システム106に対して、ジョブが基礎システム106に到達した場合には常に、SLA計画ユニット102により決定された方式でリソースを割り当てるように命令する。
【００４０】
SLA計画ユニット102が単一のワークフローオーケストレータ108とインタフェースするものとしてここに図示及び記載されているが、SLA計画ユニット102は、複数のワークフローオーケストレータと同時にインタフェースしてもよいことが理解されるべきである。また、SLA計画ユニット102が単一の基礎システム106とインタフェースするものとしてここに図示及び記載されているが、SLA計画ユニット102は、複数の基礎システムと同時にインタフェースしてもよいことも理解されるべきである。
【００４１】
図２は、SLA計画ユニット102の例示的な実施例を示す。SLA計画ユニット102は、QoS識別子生成モジュール202と、リソース要件割り振りモジュール204と、計画フレームワークモジュール206と、実行監視モジュール208とを含む。ジョブサブミッタ112は、ジョブサブミットクライアント210を含み、次に、これはQoS識別子生成モジュール212を含む。
【００４２】
以下に更に説明するように、SLA計画ユニット102において提供されるQoS識別子生成モジュール202（ここでは「SLA  QoS識別子生成モジュール」と呼ばれる）は、ワークフロー（例えば、ゲートウェイクラスタ）ノード毎に、ノードに関連する基礎サブタスクを発見する。SLA計画ユニット102はまた、基礎サブタスクの間の依存関係を発見する。次に、SLA  QoS識別子生成モジュール202は、所与のノードのサブタスク毎に固有のQoS識別子を生成する。ジョブサブミットクライアント210において提供されるQoS識別子生成モジュール212は、SLA  QoS識別子生成モジュール202により生成されたQoS識別子と同じQoS識別子を生成する補完手順を実行する。ここで使用されるQoS識別子という用語は、割り振ったQoSの水準を参照するために制御可能システムのユーザにより使用される証明書を示す。
【００４３】
次に、リソース要件割り振りモジュール204は、所与のノードのサブタスク毎のリソース要件を決定して割り振り、計画フレームワークモジュール206は、それに従ってリソース要件及びQoS識別子を有するサブタスク毎のリソース割り当て計画を生成する。ここで使用されるリソース要件という用語は、基礎システム（図１Ａの参照106）においてジョブを完了するために必要なシステムリソースの総量、並びにリソースの総量がリソース及び時間サイズに分割可能な個数を示す。リソース割り当て計画という用語は、必要なシステムリソースが時間上で分配される方式を示す。
【００４４】
実行監視モジュール208は、ワークフロー編成及び基礎システムのレベルの双方で作業負荷の実際の進捗を監視し、進捗情報を計画フレームワークモジュール206に報告する。進捗情報を使用して、計画フレームワークモジュール206は、最高位の期限及びSLAが満たされることを確保するために、必要に応じて以前に生成されたリソース割り当て計画を動的に調整する。図８を参照して以下に説明するように、調整は、全てのサブタスクを再計画すること、又はローカルで予定通りに留めるように個々のサブタスクを再計画することを含んでもよい。一実施例では、１つ以上のサブタスクへのリソース割り当てを割り振る順序、１つ以上のサブタスクの形態（すなわち、時間上のリソース割り当て）、１つ以上のサブタスクの配置（すなわち、開始時間）のうち少なくとも１つが調整される。例えば、計画フレームワークモジュール206は、ジョブをより高速に実行させるために、所与の制御システムジョブのためにより大きいCPU電源電圧（又はVCORE）を提供してもよい。計画フレームワークモジュール206はまた、所与の制御システムジョブに依存するジョブが完了した場合、所与の制御システムジョブをより早く開始させてもよい。
【００４５】
次に図３及び図４を参照すると、SLA  QoS識別子生成モジュール202は、１つ以上のサブモジュール304a、304b、304c、...を含んでもよいサブタスク発見モジュール302を含む。SLA  QoS識別子生成モジュール202は、識別子生成モジュール306を更に含む。SLA  QoS識別子生成モジュール202は、ワークフローオーケストレータ108から、QoS識別子を有するワークフローグラフを生成するように処理される入力データを受信する。入力データは、ワークフローオーケストレータ108によりプッシュされてもよく、或いはSLA計画ユニット（図２の参照102）によりプルされてもよい。入力データは、ワークフローノードの数、ワークフローノードの間の依存関係、及びワークフローノード毎のメタデータを示す。メタデータは、ノード毎の識別子（W）、ノードの期限又は最も早い開始時間、及びノードがゲートウェイクラスタ（図１Ａの参照110）上で実行するコマンドを含むが、これらに限定されない。いくつかの実施例では、メタデータは、ノードのリソース要件推定値を含む。次に、入力データは、各ワークフローノードに関連する基礎サブタスクを識別するために、サブタスク発見モジュール302により処理される。
【００４６】
サブタスク発見モジュール302は、対応するサブモジュール304a、304b、304c、...によりそれぞれ実現される様々な技術を使用して、所与のワークフローノードのための基礎サブタスクを識別する。一実施例では、構文解析モジュール304aは、ノードにより実行されるコマンドを構文的に解析し、基礎システム（図１Ａの参照106）の動作に影響を与えるコマンドを識別するために使用される。次に、構文解析モジュール304aは、各コマンドに番号（N）を順次に割り振る。これが図４に示されており、図４は、構文解析モジュール304aにより実行されるサブタスク発見手順400aの例を示す。サブタスク発見手順400aにおいて、識別子（W）が20589341であるワークフローノード402は、コマンド404のセットを実行する。コマンド404は、パーサー406（例えば、Hiveからのクエリプラナー）に送信され、これは、クエリQ1、Q2、...のセットを出力し、次に、これらは、対応する基礎サブタスク4101、4102、4103を発見するために適切なコマンド（例えば、HiveからのEXPLAINコマンド）4081、4082、4083にカプセル化される。次に、基礎サブタスクは、1からJ+1に順序付けされる。
【００４７】
他の実施例では、所与のワークフローノードのための基礎サブタスクを識別するために、サブタスク予測モジュール304bが使用される。サブタスク予測モジュール304bは、所与のワークフローノードの過去の実行を検査するために、機械学習技術を使用する。以前の実行に基づいて、サブタスク予測モジュール304bは、ノードが実行するサブタスクを予測し、各サブタスクに番号（N）を割り振る。これが図４に示されており、図４は、サブタスク予測モジュール304bにより実行されるサブタスク発見手順400bの例を示す。手順400bにおいて、サブタスク予測モジュール304bは、識別子（W）20589341を有するワークフローノード402により実行された過去のジョブ414のセットを含むワークフローノード履歴412を検査する。次に、ワークフローノード402により実行される基礎サブタスク4181、4182、4183を予測するために、予測器416が使用される。手順400bにより（すなわち、サブタスク予測モジュール304bを使用して）発見された基礎サブタスク4181、4182、4183は、サブタスク発見手順400aにより（すなわち、構文解析モジュール304aを使用して）発見された基礎サブタスク4101、4102、4103と同じである。
【００４８】
しかし、ワークフローノード毎の基礎サブタスクを発見するために構文解析及び予測以外の様々な技術が使用されてもよいことが理解されるべきである（モジュール304cにより示す）。例えば、ユーザは、基礎サブタスクが何であるかに関する自分の推測を提供してもよく、SLA  QoS識別子生成モジュール202は、この情報を入力として受信してもよい。さらに、SLA  QoS識別子生成モジュール202により実現される技術に拘わらず、SLA  QoS識別子生成モジュール202が、ワークフローオーケストレータ（又はビジネス層）のアクション毎に基礎システム（図１Ａの参照106）にサブミットされる制御システムジョブの番号及び順序を正確に予測することが望ましい。このように、SLA  QoS識別子生成モジュール202により生成されたQoS識別子がジョブサブミットクライアント（図２の参照210）において提供されるQoS識別子生成モジュール（図２の参照212）により生成されたQoS識別子に一致し、サブミットされたジョブが予約されたリソースを使用することができることが確保できる。
【００４９】
図４において認識できるように、いずれか所与のワークフローノードについて、基礎サブタスクは、依存するQoS計画ジョブに関連する制御されたサブタスク（4101、4102又は4181、4182）を含む。基礎サブタスクはまた、制御できないワークフローノード（不可解な或いは曖昧なワークフローとも呼ばれる）に関連する制御されていないサブタスク（4103又は4183）を含む。以下に更に説明するように、SLA計画ユニット（図２の参照102）は、制御されていない作業を、その持続時間のみによりモデル化し、制御されていない作業にゼロのリソースを割り振る。このようにリソースが制御されていないサブタスクに依存する作業に利用可能になり得る場合であっても、依存する作業は、開始前に持続時間の満了まで待機する必要がある。
【００５０】
所与のワークフローノードについて基礎サブタスクが発見されると、識別子生成モジュール306は、制御されていないサブタスクを含む各サブタスクへの固有のQoS識別子を生成して割り振る。一実施例では、対（W,N）がQoS識別子として使用され、これは、ノード毎の識別子（W）及びノードの各基礎サブタスクに割り振られた番号（N）を含む。これが図４に示されており、図４は、サブタスク発見手順400a及び400bの双方についてQoS識別子420がノード識別子20589341及びサブタスク番号（1,...,J+1）を含む対として生成されることを示す。次に、識別子生成モジュール306は、ワークフローノード毎の生成されたQoS識別子を含むワークフローノードのグラフをリソース要件割り振りモジュール204に出力する。特に、サブタスク発見モジュール302により識別された基礎サブタスクの間の依存関係を生成することにより、識別子生成モジュール306は、ワークフローオーケストレータ（図２の参照108）により提供されたワークフローグラフに対して拡充する。
【００５１】
前述のように且つ図５に図示するように、ジョブサブミットクライアント（図２の参照210）において提供されるQoS識別子生成モジュール（図２の参照212）は、SLA  QoS識別子生成モジュール（図２の参照202）により実現されるQoS識別子生成手順を複製するための手順500を実現する。QoS識別子生成モジュール212は、それに従って所与のワークフローノード502（識別子（W）20589341を有する）に関連するサブミットされたジョブのためのQoS識別子を生成する。例示的な手順500において、ノード502のためのコマンド504は、Hiveクエリ解析器506に送信され、これは、クエリQ1及びQ2を出力し、次に、これらがそれぞれ実行され、２つのセットのジョブ5081（1〜Iの番号）、5082（I+1〜Jの番号）が双方のクエリについてサブミットされることを生じる。次に、QoS識別子510は、サブミットされたジョブの順序を観測し、それぞれのサブミットされたジョブの番号（図５におけるN、N=1,...,J）を決定し、QoS識別子として対（W,N）を使用することにより生成される。ジョブサブミットクライアント210において提供されるQoS識別子生成モジュール212は、制御されたジョブのみのためのQoS識別子を提供し、制御されていないジョブを考慮しないことが理解される。また、QoS識別子生成モジュール212は、制御されたジョブ（1,...,J）のためにSLA  QoS識別子生成モジュール202により生成されたQoS識別子（図４の参照420）と同じQoS識別子510を生成することも理解される。生成されると、QoS識別子510は、QoSの所望（又は要求）水準を示し、将来のリソース割り当てを要求するために、リソースマネージャ（図２の参照114）にサブミットされる作業負荷に添付される。特に、QoS識別子510は、リソース割り当てがサブミットされたジョブにより活用されるために、リソースマネージャ114に送信される。
【００５２】
次に図６を参照すると、リソース要件割り振りモジュール204は、１つ以上のサブモジュール604a、604b、604c、604d、...を含んでもよいリソース要件決定モジュール602を含む。特に、リソース要件割り振りモジュール204は、サブモジュール604a、604b、604c、604d、...のうち対応するものによりそれぞれ実現される様々な技術を使用して、サブタスク毎のリソース要件を決定する。リソース要件割り振りモジュール204は、予約定義言語（RDL++）記述生成モジュール606を更に含む。リソース要件割り振りモジュール204は、SLA  QoS識別子生成モジュール（図２の参照202）から、ワークフローノード毎にノードについて生成されたQoS識別子を含むメタデータを有するワークフローノードのグラフを受信する。前述のように、いくつかの実施例では、メタデータは、適切な入力手段を使用してユーザにより提供されたノードの全体リソース要件推定値を含む。この場合、リソース要件決定モジュール602は、ノードの基礎サブタスクの間で全体リソース要件推定値を均等に分割するために、手動推定モジュール604aを使用する。
【００５３】
リソース要件推定値が提供されない実施例では、リソース要件決定モジュール602は、ノードの過去の実行履歴を取得し、それに従って各サブタスクのリソース要件を予測するために、リソース要件予測モジュール604bを使用する。他の実施例では、リソース要件決定モジュール602は、所定の期間に各サブタスクを先取り的に実行するために、サブタスク先取実行モジュール604cを使用する。所定の期間の満了のときに、サブタスク先取実行モジュール604cは、サブタスクを終了させるために、「kill」コマンドを呼び出す。サブタスクを終了させたときに、サブタスク先取実行モジュール604cは、サブタスクの現在のリソース使用量のサンプルを取得し、サブタスクの全体リソース要件をモデル化するために、リソース使用量サンプルを使用する。SLA  QoS識別子生成モジュール202により制御されていないとしてフラグ付けされたサブタスクについて、リソース要件決定モジュール602は、リソース要件のリソース使用量サイズをゼロに設定し、持続時間のみを割り振る。各サブタスクへのリソース要件を決定して割り振るために、リソース要件の手動推定、リソース要件の予測、サブタスクの先取実行以外の技術が使用されてもよいことが理解されるべきである（モジュール604dにより示す）。
【００５４】
次に、RDL++記述生成モジュール606は、全体ワークフローのRDL++記述を出力する。RDL++記述は、サブタスク毎の合計リソース要件（すなわち、サブタスクを完了するために必要なシステムリソースの総量、典型的には、メモリのメガバイト及びCPU配分比率として表される）と各サブタスクの持続時間とを指定するワークフローグラフとして提供される。RDL++記述は、制御されていないサブタスクが、依存するタスクが計画できる前に経過しなければならない持続時間のみを有することを更に指定する。このように且つ前述のように、いくつかのワークフローノードがゼロのリソースを必要とするが、依存するジョブが実行することができる前に経過すべき持続時間を有することが可能である。
【００５５】
次に図７を参照すると、計画フレームワークモジュール206は、順序選択モジュール704と、形態選択モジュール706と、配置選択モジュール708とを含むリソース割り当て計画生成モジュール702を含む。計画フレームワークモジュール206は、期限徒過検出モジュール710と、実行情報受信モジュール712とを更に含む。計画フレームワークモジュール206は、リソース要件割り振りモジュール（図２の参照204）から、ワークフローノード毎のメタデータを有するワークフローノードのグラフ（例えば、RDL++記述）を受信する。前述のように、メタデータは、ワークフローノード毎にSLA  QoS識別子生成モジュール（図２の参照202）により生成されたQoS識別子と、リソース要件割り振りモジュール204によりノードに割り振られたリソース要件と、基礎システムのキャパシティ（例えば、適切な入力手段を使用してユーザにより提供される）とを含む。いくつかの実施例では、メタデータは、ワークフローノード毎の期限又は最低の開始時間（例えば、適切な入力手段を使用してユーザにより提供される）を含む。
【００５６】
次に、計画フレームワークモジュール206は、RLD++グラフ内のワークフローノード毎に、リソース割り当て計画生成モジュール702を使用してノードのサブタスク毎のリソース割り当て計画を生成する。リソース割り当て計画は、サブタスクにより要求されるリソースが時間上で分配される方式を指定し、これにより、対応するワークフローノードのQoSの水準を示す。特に、リソース割り当て計画生成モジュール702は、各サブタスクにリソース割り当てを割り振る順序、サブタスク毎の時間上のリソース割り当て及び／又はサブタスク毎の開始時間を選択することにより、各サブタスクにより要求されるリソースの時間上の分配を決定する。このため、順序選択モジュール704は、各サブタスクへのリソース割り当てを割り振る順序を選択する。形態選択モジュール706は、サブタスク毎の形態（すなわち、時間上のリソース割り当て）を選択する。配置選択モジュール708は、サブタスク毎の配置（すなわち、開始時間）を選択する。
【００５７】
一実施例では、順序選択モジュール704、形態選択モジュール706及び配置選択モジュール708のそれぞれは、発見的に順序、形態及び配置のそれぞれの選択を行う。他の実施例では、順序選択モジュール704、形態選択モジュール706及び配置選択モジュール708のそれぞれは、目的関数を最適化するために順序、形態及び配置のそれぞれの選択を行う。更に他の実施例では、順序選択モジュール704、形態選択モジュール706及び配置選択モジュール708のそれぞれは、ランダムに順序、形態及び配置のそれぞれの選択を行う。更に他の実施例では、早い期限を有するワークフローのクリティカルパス上のジョブは、あまり重要でないジョブ（例えば、あまり期限が差し迫っていないワークフローの部分のジョブ）の前に順序付けされ、形成され、配置される。また、順序選択モジュール704、形態選択モジュール706及び配置選択モジュール708は、異なる順序で動作してもよく、例えば、形態選択が順序選択の前に発生することも理解されるべきである。さらに、異なるモジュールは、インターリーブ又は反復方式で動作してもよい。
【００５８】
前述のように、いくつかの実施例では、ワークフローノード毎の期限又は最低の開始時間は、計画フレームワークモジュール206への入力として提供される。この場合、ワークフローノード毎に、期限徒過検出モジュール710は、いずれかのサブタスクがその期限又は最低の開始時間を違反したか否かを決定する。次に、期限徒過検出モジュール710は、期限が満たされていないサブタスクのリストを返信する。期限徒過検出モジュール710は、リソース割り当て計画及び各サブタスクに関連するサービス品質識別子をリソースマネージャ（図２の参照114）に更に出力する。リソースマネージャ114は、（リソース割り当て計画の通りに）ワークフローノードに関連するQoS識別子と同じQoS識別子によってサブミットされたジョブを待機し、ワークフローノードのためのリソース割り当て計画において指定されたQoSの水準を強制する。このように、ジョブが指定の期限までに完了することができ、SLAがユーザ要件の通りに満たされることを確保することが可能になる。
【００５９】
SLA計画ユニット102は、単一のワークフローオーケストレータ108又は基礎システムインスタンス内で複数のリソース割り当て計画を管理してもよいことが理解されるべきである（例えば、マルチテナントのサポートの場合）。また、サブタスク毎のリソース割り当て計画を基礎システム106に提供することに加えて、SLA計画ユニット102はまた、リソース割り当て計画をワークフローオーケストレータ108に提供してもよいことも理解されるべきである。この場合、SLA計画ユニット102は、リソース割り当て計画をワークフローオーケストレータ108にプッシュしてもよい。或いは、リソース割り当て計画は、ワークフローオーケストレータ108によりプルされてもよい。次に、ワークフローノード毎に、ワークフローオーケストレータ108は、各サブタスクの計画開始時間をトラッキングするために、或いは計画開始時間までワークフローをサブミットするのを待機するために、リソース割り当て計画を使用してもよい。
【００６０】
次に図７に加えて図８を参照すると、実行監視モジュール208は、ワークフロー編成及び基礎システムのレベルの双方で実際の作業負荷の進捗を監視するために使用される。このため、実行監視モジュール208は、ワークフローオーケストレータ（図１Ａの参照108）及びリソースマネージャ（図１Ａの参照114）から実行状態情報を取得する実行情報取得モジュール802を含む。一実施例では、実行情報取得モジュール802は、ワークフローオーケストレータ108及びリソースマネージャ114から実行情報を取り出す（例えば、プルする）。他の実施例では、ワークフローオーケストレータ108及びリソースマネージャ114は、実行情報を実行情報取得モジュール802に送信する（例えば、プッシュする）。ワークフローオーケストレータ108から取得された実行状態情報は、開始時間、終了時間、正常終了及び異常終了を含むが、これらに限定されない最高位ワークフローノードの実行についての情報を含む。リソースマネージャ114から取得された実行状態情報は、開始時間、終了時間、完了割合及び実際のリソース要件を含むが、これらに限定されない基礎システムのジョブについての情報を含む。
【００６１】
いったん実行監視モジュール208が実際の作業負荷の進捗を決定すると、実行情報取得モジュール802は、実行情報を計画フレームワークモジュール206に送信する。次に、実行情報は、計画フレームワークモジュール206の実行情報受信モジュール712において受信され、リソース割り当て計画生成モジュール702に送信され、これにより、１つ以上の既存のリソース割り当て計画がそれに従って調整されることができる。調整は、元のリソース要件がリソース要件割り振りモジュール（図２の参照204）により誤って決定された場合に必要になってもよい。例えば、元のリソース要件の誤った決定は、サブタスク要件の誤った予測の結果として発生してもよい。誤ったユーザ入力（例えば、誤ったリソース要件推定値が提供されたこと）もまた、リソース要件の不適切な決定を生じ得る。
【００６２】
調整が必要であると決定された場合、リソース割り当て計画生成モジュール702は、実際のリソース要件に基づいて１つ以上の以前に計画されたジョブのためのリソース割り当て計画を調整する。調整は、全てのサブタスクを再計画すること、又はローカルで予定通りに留めるように個々のサブタスクを再計画することを含んでもよい。例えば、調整は、下流のジョブ割り当てを上げることを含んでもよい。このように、元のリソース要件が誤って計画された場合であっても、実行監視モジュール208を使用して、最高位のSLAが満たされ得る。
【００６３】
一実施例では、リソース割り当て計画の調整が必要であると決定すると、リソース割り当て計画生成モジュール702は、その調整を可能にするための十分なキャパシティが既存のリソース割り当て計画に存在するか否かを評価する。そうでない場合、リソース割り当て計画生成モジュール702は、調整が可能でないことを示す情報を出力する。この情報は、適切な出力手段を使用してユーザに出力されてもよい。例えば、リソース割り当て計画の調整は、いくつかのサブタスクが元々計画されたものより多くのリソースを必要とするとリソース割り当て計画生成モジュール702が決定した場合には不可能でもよい。他の実施例では、異なるワークフローの優先度が考慮され、リソース割り当て計画は、全体のキャパシティが使い果たされている場合であっても、より高いキャパシティのタスクが完了し得るように調整される。特に、空きのキャパシティがリソース割り当て計画に存在しない場合であっても、この実施例では、リソース割り当て計画生成モジュール702は、１つのサブタスクから他のより高いキャパシティのサブタスクにリソースを割り当てる。更に他の実施例では、リソース割り当て計画生成モジュール702は、所与のSLAが損なわれても、より大きい数のSLAが満たされ得るように、既存のリソース割り当て計画を調整する。
【００６４】
図９は、SLA計画ユニット（図１Ａの参照102）を実現するためのコンピューティングデバイス900の例示的な実施例である。コンピューティングデバイス900は、処理ユニット902と、コンピュータ実行可能命令906を記憶したメモリ904とを含む。処理ユニット902は、命令906がコンピューティングデバイス900又は他のプログラム可能装置により実行された場合、ここに記載の方法において指定された機能／動作／ステップを実行させ得るように、一連のステップを実行させるように構成されたいずれか適切なデバイスを含んでもよい。処理ユニット902は、例えば、いずれかの種類の汎用マイクロプロセッサ若しくはマイクロコントローラ、デジタルシグナル処理（DSP）プロセッサ、中央処理装置（CPU）、集積回路、フィールドプログラマブルゲートアレイ（FPGA）、再構成可能プロセッサ、他の適切にプログラムされた論理回路若しくはプログラム可能論理回路、又はこれらのいずれかの組み合わせを含んでもよい。
【００６５】
メモリ904は、いずれか適切な既知又は他の機械読み取り可能記憶媒体を含んでもよい。メモリ904は、例えば、電子、磁気、光学、電磁気、赤外線若しくは半導体のシステム、装置若しくはデバイス、又は前述のいずれか適切な組み合わせに限定されない過渡的でないコンピュータ読み取り可能記憶媒体を含んでもよい。メモリ904は、デバイスの内部又は外部に位置するいずれかの種類のコンピュータメモリ、例えば、ランダムアクセスメモリ（RAM）、読み取り専用メモリ（ROM）、コンパクトディスク読み取り専用メモリ（CDROM）、電気光学メモリ、光磁気メモリ、消去可能プログラム可能読み取り専用メモリ（EPROM）及び電気的消去可能プログラム可能読み取り専用メモリ（EEPROM）、強誘電体メモリ（FRAM）等の適切な組み合わせを含んでもよい。メモリ904は、処理ユニット902により実行可能な機械読み取り可能命令906を取り出し可能に記憶するのに適したいずれかの記憶手段（例えば、デバイス）を含んでもよい。
【００６６】
次に図１０を参照して、計算ワークフローにおいてサービス品質を確保するための例示的な方法1000についてこれから説明する。方法1000は、ジョブが基礎システム（図１Ａの参照106）にサブミットされる前に、SLA計画ユニット（図１Ａの参照102）により実現される。方法1000は、ステップ1002において、ワークフローノード毎に基礎サブタスク及び基礎サブタスクの間の依存関係を識別するステップ1002を含む。次に、ステップ1004において、固有のサービス品質（QoS）識別子が各サブタスクに割り振られる。ステップ1006において、合計リソース要件がサブタスク毎に更に決定される。ステップ1008において、全体ワークフローの予約定義言語（RDL++）記述が出力され、ステップ1010において、リソース割り当て計画がRDL++記述におけるノード毎に生成される。次のステップ1012は、ワークフロー編成及び基礎システムのレベルで作業負荷の実際の進捗を監視することである。次に、ステップ1014において、１つ以上の既存のリソース割り当ては、必要に応じて実際のリソース要件に基づいて更新される。次に、リソース割り当て計画及び対応するQoS識別子は、強制のために基礎システムのリソースマネージャにサブミットされる（ステップ1016）。特に、関連するQoS  IDを有するジョブが基礎システムに到達すると常に、基礎システムのリソースマネージャは、対応するリソース割り当て計画に従って（例えば、これにより指定された通りに）リソースを割り当てる。
【００６７】
次に図１１を参照すると、一実施例では、ワークフローノード毎に基礎サブタスクを識別するステップ1002は、基礎サブシステムの動作に影響を与えるサブタスクを識別するために、ノード（W）により実行されるコマンドを構文的に解析することを含む（ステップ1102a）。他の実施例では、ワークフローノード毎に基礎サブタスクを識別するステップ1002は、以前の実行に基づいてノード（W）が実行するサブタスクを予測するために機械学習技術を使用することを含む（ステップ1102b）。前述のように、基礎サブタスクは、構文解析又は予測以外の複数の技術を使用して発見されてもよい（ステップ1102cにより示す）。例えば、図１１に図示されていないが、ステップ1002は、基礎サブタスクが何であるかに関するユーザにより提供された予測を受信することを含んでもよい。次に、各サブタスクにQoS識別子を割り振るステップ1004は、それぞれ以前に識別されたサブタスク（制御されていないサブタスクを含む）に番号（N）を順次に割り振ること（ステップ1104）を含む。次に、対（W,N）は、当面、ノードのQoS識別子として使用される（ステップ1106）。
【００６８】
図１２を参照すると、一実施例では、ステップ1006は、ステップ1202において、各ノードのサブタスクの間で全体の手動推定値、例えば、ユーザ入力を通じて受信した手動推定値を均等に分割することを含む。他の実施例では、ステップ1204において、過去の実行履歴に基づいて各サブタスクのリソース要件を予測するために、機械学習が使用される。更に他の実施例では、各サブタスクは、所定の期間に先取り的に実行される（ステップ1206）。次に、サブタスクが終了し、ステップ1208において、サブタスクの現在のリソース使用量のサンプルが取得される。次に、ステップ1210において、現在のリソース使用量のサンプルは、サブタスクの全体リソース要件をモデル化するために使用される。次に、次のステップ1212は、いずれかの制御されていないサブタスクがQoS識別子生成処理（図１０のステップ1002及び1004）の間にフラグ付けされているか否かを評価することである。そうでない場合、方法1000は、次のステップ1008に進む。そうでない場合、次のステップ12142は、制御されていないサブタスクのリソース要件の使用量サイズをゼロに設定し、制御されていないサブタスクに持続時間のみを割り振ることである。
【００６９】
次に図１３を参照すると、リソース割り当て計画を生成するステップ1010は、ステップ1302において、各サブタスクへのリソース割り当てを割り振る順序を選択することを含む。順序が選択されると、次のステップ1304は、次のサブタスクを取得することである。次に、ステップ1306において、現在のサブタスクのための時間上のリソース割り当て及び持続時間（すなわち、形態）が設定される。次に、ステップ1308において、サブタスク開始時間（すなわち、配置）が設定され、ステップ1310において、サブタスクがリソース割り当て計画に追加される。次に、次のステップ1312は、現在のサブタスクについて期限が徒過したか否かを評価することである。そうである場合、ステップ1314において、サブタスクは、拒否リストに追加される。そうでない場合、次のステップ1316は、リソース割り当てが割り振られるべきサブタスクが残っているか否かを決定することである。そうである場合、方法はステップ1304に戻り、次のサブタスクを取得する。そうでない場合、ステップ1318において、リソース割り当て計画及び拒否リストが出力される。
【００７０】
前述のように、順序、形態及び配置の選択は、発見的に、目的関数を最適化するために、或いはランダムに行われることができる。重要なジョブもまた、あまり重要でないジョブの前に順序付けされ、形成され、配置されることができる。また、ステップ1302、1306及び1308は、異なる順序で或いはインターリーブ又は反復方式で実行されることができることも理解されるべきである。
【００７１】
図１４を参照すると、ワークフロー編成及び基礎システムのレベルで作業負荷の実際の進捗を監視するステップ1012は、ステップ1402において、最高位ワークフローノードの実行及び基礎システムのジョブについての実行情報を取り出すことを含む。次に、ステップ1404において、取り出された情報は、１つ以上の既存のリソース割り当て計画の調整を引き起こすために、計画フレームワークに送信される。図１５に示すように、実際のリソース要件に基づいて１つ以上の既存のリソース割り当て計画を更新するステップ1014は、ステップ1502において、実行情報を受信し、受信した実行情報に基づいて、実際のリソース要件が計画リソース要件と異なるか否かを評価すること（ステップ1504）を含む。そうでない場合、方法は次のステップ、すなわち、図１０のステップ1016に進む。そうでない場合、一実施例では、次のステップ1506は、調整を可能にするための十分なキャパシティが既存のリソース割り当て計画に存在するか否かを評価することである。そうである場合、次のステップ1508は、実際の作業負荷実行情報及び実際のリソース要件に基づく既存のリソース割り当て計画の調整に進むことである。そうでない場合、調整が可能でないことを示す情報が出力され（例えば、ユーザに対して、ステップ1510）、次に、方法はステップ1016に進む。例えば、空きのキャパシティがリソース割り当て計画に存在しない場合であっても、１つのサブタスクからのリソースは、より高いキャパシティのサブタスクに割り当てられてもよい。或いは、既存のリソース割り当て計画は、所与のSLAが損なわれても、より大きい数のSLAが満たされるように調整されてもよい。
【００７２】
次に図１６を参照すると、図１０のステップ1004を複製するQoS識別子生成手順1600が基礎システム（図１Ａの参照106）において実現される。手順1600は、ステップ1602において、ワークフローノード毎に、サブミットされた基礎システムのジョブの順序を観測することを含む。次に、ステップ1604において、固有のQoS識別子が生成され、それぞれサブミットされたジョブに添付される。次に、次のステップ1606は、リソース割り当て計画が生成されたワークフローノードに関連するQoS識別子と同じQoS識別子でサブミットされたジョブについて、リソース割り当て計画において指定されたQoSの水準を強制すること（すなわち、それに従ってリソースを割り当てること）である。その結果、基礎システムのレベルにおいて提示されたサブミットされたジョブが特定の水準のサービスを達成し、これにより、ビジネスワークフローSLAを満たすことを確保することが可能になる。
【００７３】
前述の説明は、例示の目的のみのためのものであることを意図しており、関連分野の当業者は、開示の発明の範囲を逸脱することなく、記載の実施例に変更が行われてもよいことを認識する。例えば、ここに記載のフローチャート及び図面のブロック及び／又は動作は、例示の目的のみのためのものである。本開示の教示を逸脱することなく、これらのブロック及び／又は動作に対する多くの変形が存在し得る。例えば、ブロックは、異なる順序で実行されてもよく、或いはブロックは追加、削除又は変更されてもよい。
【００７４】
別個のデータ信号接続を介して相互に通信する別々のコンポーネントのグループとしてブロック図に示されているが、本実施例は、ハードウェア及びソフトウェアコンポーネントの組み合わせにより提供され、いくつかのコンポーネントは、ハードウェア又はソフトウェアシステムの所与の機能又は動作により実現され、図示のデータパスの多くは、コンピュータアプリケーション又はオペレーティングシステム内のデータ通信により実現されることが当業者により理解される。このような理解に基づいて、本発明の技術的解決策は、ソフトウェアプロダクトの形式で具現されてもよい。ソフトウェアプロダクトは、不揮発性或いは過渡的でない記憶媒体に記憶されてもよく、これは、読み取り専用メモリ（ROM）、磁気ディスク、光ディスク、フラッシュドライブ、又は他の適切な記憶媒体若しくはデバイスでもよい。
【００７５】
ここに記載の各コンピュータプログラムは、コンピュータシステムと通信するために、ハイレベルの手続き型若しくはオブジェクト指向型プログラミング若しくはスクリプト言語、又はこれらの組み合わせで実現されてもよい。或いは、プログラムは、アセンブリ又は機械言語で実現されてもよい。言語は、コンパイル済又はインタープリタ型言語でもよい。ソフトウェアプロダクトは、コンピュータデバイス（パーソナルコンピュータ、サーバ又はネットワークデバイス）が本発明の実施例において提供される方法を実行するのを可能にする複数の命令を含む。コンピュータ実行可能命令は、１つ以上のコンピュータ又は他のデバイスにより実行される、プログラムモジュールを含む多くの形式になってもよい。一般的に、プログラムモジュールは、特定のタスクを実行するか、特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。典型的には、様々な実施例では、プログラムモジュールの機能は、必要に応じて組み合わされてもよく、或いは分散されてもよい。したがって、図示の構造は、本実施例を教示する効率のために提供されている。本開示は、特許請求の範囲の対象物を逸脱することなく、他の具体的な形式で具現されてもよい。
【００７６】
また、関連分野の当業者は、ここに開示及び図示のシステム、方法及びコンピュータ読み取り可能媒体が、特定の数のエレメント／コンポーネントを含んでもよいが、システム、方法及びコンピュータ読み取り可能媒体は、更なる或いはより少ないこのようなエレメント／コンポーネントを含むように変更されてもよいことを認識する。本開示はまた、技術における全ての適切な変更をカバー及び包含することを意図する。本発明の範囲内に入る変更は、この開示の検討を踏まえて当業者に明らかであり、このような変更は、添付の特許請求の範囲内に入ることを意図する。
【図１Ａ】
2019505861.tif 000003
【図１Ｂ】
2019505861.tif 000004
【図１Ｃ】
2019505861.tif 000005
【図２】
2019505861.tif 000006
【図３】
2019505861.tif 000007
【図４】
2019505861.tif 000008
【図５】
2019505861.tif 000009
【図６】
2019505861.tif 000010
【図７】
2019505861.tif 000011
【図８】
2019505861.tif 000012
【図９】
2019505861.tif 000013
【図１０】
2019505861.tif 000014
【図１１】
2019505861.tif 000015
【図１２】
2019505861.tif 000016
【図１３】
2019505861.tif 000017
【図１４】
2019505861.tif 000018
【図１５】
2019505861.tif 000019
【図１６】
2019505861.tif 000020
【手続補正書】
【提出日】平成29年12月12日(2017.12.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
計算ワークフローにおいてサービス品質を確保するための方法であって、
計画ユニットにおいて、
前記計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振るステップであり、前記第１のサービス品質識別子は、各ノードに割り振られたサービス品質の水準を示すステップと、
前記１つ以上のサブタスクのそれぞれに計画リソース要件を割り振るステップであり、前記計画リソース要件は、前記１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示すステップと、
割り振られた前記第１のサービス品質識別子及び前記計画リソース要件を有する前記１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成するステップであり、前記リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上の前記システムリソースの分配を示すステップと、
前記少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対する前記サービス品質の水準の強制のために、前記リソース割り当て計画及び前記第１のサービス品質識別子を前記少なくとも１つのリソースマネージャに出力するステップであり、前記１つ以上のジョブのそれぞれは、前記１つ以上のサブタスクを含むステップと
を含む方法。
【請求項２】
前記計画ユニットにおいて、
前記少なくとも１つのワークフローオーケストレータ及び前記少なくとも１つのリソースマネージャから、前記１つ以上のサブタスク及び前記１つ以上のジョブの現在の進捗を示す実行情報を取り出すステップと、
前記実行情報から、前記１つ以上のサブタスクのそれぞれの実際のリソース要件を決定するステップと、
前記実際のリソース要件を前記計画リソース要件と比較するステップと、
前記実際のリソース要件が前記計画リソース要件と異なる場合、前記１つ以上のサブタスクのうち少なくとも１つの前記リソース割り当て計画を動的に調整するステップと
を更に含む、請求項１に記載の方法。
【請求項３】
前記計画ユニットにおいて、
前記少なくとも１つのワークフローオーケストレータから、前記計算ワークフローにおけるノードの数と、ノードの間の依存関係と、ノード毎のメタデータとを含む入力データを受信するステップであり、前記メタデータは、ノード識別子と、ノード毎の１つ以上の期限と、各ノードにより実行される１つ以上のコマンドと、ノード毎のリソース要件推定値とを含み、前記１つ以上のサブタスクは、前記入力データに基づいて識別されるステップを更に含む、請求項１又は２に記載の方法。
【請求項４】
前記計画ユニットにおいて、
前記１つ以上のコマンドのうち、前記少なくとも１つのリソースマネージャの動作に影響を与えるコマンドを識別するために、前記１つ以上のコマンドの構文解析を実行するステップと、
前記識別されたコマンドのそれぞれに番号を順次に割り振るステップであり、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むステップと
を更に含む、請求項３に記載の方法。
【請求項５】
前記計画ユニットにおいて、ノード毎の過去の実行履歴に基づいて前記１つ以上のサブタスクを予測するステップと、
前記予測された１つ以上のサブタスクのそれぞれに番号を順次に割り振るステップであり、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むステップと
を更に含む、請求項３に記載の方法。
【請求項６】
前記計画リソース要件を割り振るステップは、前記計画ユニットにおいて、前記１つ以上のサブタスクの間で前記リソース要件推定値を均等に分割するステップを含む、請求項３に記載の方法。
【請求項７】
前記計画リソース要件を割り振るステップは、前記計画ユニットにおいて、ノード毎の過去の実行履歴に基づいて前記１つ以上のサブタスクのそれぞれの前記計画リソース要件を予測するステップを含む、請求項１乃至６のうちいずれか１項に記載の方法。
【請求項８】
前記計画リソース要件を割り振るステップは、
前記計画ユニットにおいて、
所定の期間に前記１つ以上のサブタスクのそれぞれを実行するステップと、
前記所定の期間の満了のときに前記１つ以上のサブタスクのそれぞれを終了させるステップと、
前記１つ以上のサブタスクのそれぞれの終了のときに前記１つ以上のサブタスクのそれぞれの現在のリソース使用量サンプルを取得するステップと、
前記現在のリソース使用量サンプルに基づいて前記計画リソース要件をモデル化するステップと
を含む、請求項１乃至７のうちいずれか１項に記載の方法。
【請求項９】
前記計画ユニットにおいて、前記１つ以上のサブタスクのうち制御されていないサブタスクを識別するステップであり、それぞれの制御されていないサブタスクは、未知のワークフローに関連するステップを更に含み、
前記計画リソース要件を割り振るステップは、前記計画ユニットにおいて、それぞれの制御されていないサブタスクを完了するために必要なシステムリソースの総量をゼロに設定し、前記制御されていないサブタスクを非ゼロの持続時間を有するものとしてモデル化するステップを含む、請求項１乃至８のうちいずれか１項に記載の方法。
【請求項１０】
前記リソース割り当て計画を生成するステップは、前記計画ユニットにおいて、前記１つ以上のサブタスクのそれぞれへのリソース割り当てを割り振る順序を選択し、前記１つ以上のサブタスクのそれぞれの時間上のリソース割り当てを選択し、前記１つ以上のサブタスクのそれぞれの開始時間を選択するステップを含む、請求項１乃至９のうちいずれか１項に記載の方法。
【請求項１１】
前記計画ユニットにおいて、前記１つ以上のサブタスクのうち、前記１つ以上の期限を違反したサブタスクを識別し、前記識別されたサブタスクをサブタスク拒否リストに追加し、前記サブタスク拒否リストを出力するステップを更に含む、請求項３乃至１０のうちいずれか１項に記載の方法。
【請求項１２】
ジョブサブミッタにおいて、前記１つ以上のジョブのそれぞれに、ノード毎のサービス品質の要求水準を示す第２のサービス品質識別子を割り振るステップと、
前記少なくとも１つのリソースマネージャにおいて、前記第１のサービス品質識別子、前記第２のサービス品質識別子及び前記リソース割り当て計画を受信し、前記１つ以上のジョブのうち、前記第２のサービス品質識別子が前記第１のサービス品質識別子に対応するジョブのために前記リソース割り当て計画に従って前記システムリソースを割り当てるステップと
を更に含む、請求項１乃至１１のうちいずれか１項に記載の方法。
【請求項１３】
前記第２のサービス品質識別子を割り振るステップは、前記１つ以上のジョブの順序を観測し、前記順序に従って前記１つ以上のジョブのそれぞれに番号を割り振るステップであり、前記第２のサービス品質識別子は、前記割り振られた番号及びノード識別子を含むステップを含む、請求項１２に記載の方法。
【請求項１４】
計算ワークフローにおいてサービス品質を確保するためのシステムであって、
少なくとも１つの処理ユニットと、
前記少なくとも１つの処理ユニットに通信可能に結合された過渡的でないメモリであり、
前記計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振り、前記第１のサービス品質識別子は、各ノードに割り振られたサービス品質の水準を示し、
前記１つ以上のサブタスクのそれぞれに計画リソース要件を割り振り、前記計画リソース要件は、前記１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示し、
割り振られた前記第１のサービス品質識別子及び前記計画リソース要件を有する前記１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成し、前記リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上の前記システムリソースの分配を示し、
前記少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対する前記サービス品質の水準の強制のために、前記リソース割り当て計画及び前記第１のサービス品質識別子を前記少なくとも１つのリソースマネージャに出力し、前記１つ以上のジョブのそれぞれは、前記１つ以上のサブタスクを含むために、
前記少なくとも１つの処理ユニットにより実行可能なコンピュータ読み取り可能プログラム命令を含む過渡的でないメモリと
を含むシステム。
【請求項１５】
前記コンピュータ読み取り可能プログラム命令は、
前記少なくとも１つのワークフローオーケストレータ及び前記少なくとも１つのリソースマネージャから、前記１つ以上のサブタスク及び前記１つ以上のジョブの現在の進捗を示す実行情報を取り出し、
前記実行情報から、前記１つ以上のサブタスクのそれぞれの実際のリソース要件を決定し、
前記実際のリソース要件を前記計画リソース要件と比較し、
前記実際のリソース要件が前記計画リソース要件と異なる場合、前記１つ以上のサブタスクのうち少なくとも１つの前記リソース割り当て計画を動的に調整するために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４に記載のシステム。
【請求項１６】
前記コンピュータ読み取り可能プログラム命令は、
前記少なくとも１つのワークフローオーケストレータから、ノード毎のノード識別子及び各ノードにより実行される１つ以上のコマンドを受信し、
前記１つ以上のコマンドのうち、前記少なくとも１つのリソースマネージャの動作に影響を与えるコマンドを識別するために、前記１つ以上のコマンドの構文解析を実行し、
前記識別されたコマンドのそれぞれに番号を順次に割り振り、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４又は１５に記載のシステム。
【請求項１７】
前記コンピュータ読み取り可能プログラム命令は、
前記少なくとも１つのワークフローオーケストレータから、ノード識別子及びノード毎の過去の実行履歴を受信し、
前記過去の実行履歴に基づいて前記１つ以上のサブタスクを予測し、
前記予測された１つ以上のサブタスクのそれぞれに番号を順次に割り振り、前記第１のサービス品質識別子は、前記ノード識別子及び前記割り振られた番号を含むために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４乃至１６のうちいずれか１項に記載のシステム。
【請求項１８】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のサブタスクのうち制御されていないサブタスクを識別し、それぞれの制御されていないサブタスクは、未知のワークフローに関連し、それぞれの制御されていないサブタスクを完了するために必要なシステムリソースの総量をゼロに設定し、前記制御されていないサブタスクを非ゼロの持続時間を有するものとしてモデル化することを含む、前記計画リソース要件を割り振るために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４乃至１７のうちいずれか１項に記載のシステム。
【請求項１９】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のサブタスクのそれぞれへのリソース割り当てを割り振る順序を選択し、前記１つ以上のサブタスクのそれぞれの時間上のリソース割り当てを選択し、前記１つ以上のサブタスクのそれぞれの開始時間を選択することを含む、前記リソース割り当て計画を生成するために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４乃至１８のうちいずれか１項に記載のシステム。
【請求項２０】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のジョブのそれぞれに、ノード毎のサービス品質の要求水準を示す第２のサービス品質識別子を割り振り、
前記１つ以上のジョブのうち、前記第２のサービス品質識別子が前記第１のサービス品質識別子に対応するジョブのために前記リソース割り当て計画に従って前記システムリソースを割り当てるために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項１４乃至１９のうちいずれか１項に記載のシステム。
【請求項２１】
前記コンピュータ読み取り可能プログラム命令は、
前記１つ以上のジョブの順序を観測し、前記順序に従って前記１つ以上のジョブのそれぞれに番号を割り振り、前記第２のサービス品質識別子は、前記割り振られた番号及びノード識別子を含むことを含む、前記第２のサービス品質識別子を割り振るために、
前記少なくとも１つの処理ユニットにより実行可能である、請求項２０に記載のシステム。
【請求項２２】
計算ワークフローの各ノードに関連する１つ以上のサブタスクのそれぞれに第１のサービス品質識別子を割り振り、前記第１のサービス品質識別子は、各ノードに関連するサービス品質の水準を示し、
前記１つ以上のサブタスクのそれぞれに計画リソース要件を割り振り、前記計画リソース要件は、前記１つ以上のサブタスクのそれぞれを完了するために必要なシステムリソースの総量を示し、
割り振られた前記第１のサービス品質識別子及び前記計画リソース要件を有する前記１つ以上のサブタスクのそれぞれのためのリソース割り当て計画を生成し、前記リソース割り当て計画は、少なくとも１つのリソースマネージャにおける時間上の前記システムリソースの分配を示し、
前記少なくとも１つのリソースマネージャの外部の少なくとも１つのワークフローオーケストレータを通じてノード毎にサブミットされた１つ以上のジョブに対する前記サービス品質の水準の強制のために、前記リソース割り当て計画及び前記第１のサービス品質識別子を前記少なくとも１つのリソースマネージャに出力し、前記１つ以上のジョブのそれぞれは、前記１つ以上のサブタスクを含むために、
プロセッサにより実行可能なプログラムコードを記憶したコンピュータ読み取り可能媒体。
【国際調査報告】
2019505861.tif 000021
2019505861.tif 000022