(57)【要約】  ＣＲＥＳＴに基づき、予測実行タスクのスケジューリングモデルを組み合わせ最適化することと、前記予測実行タスクのスケジューリングモデルに基づき、ノード間の帯域幅およびノード処理能力の細粒度リソース情報を収集することと、ノード間の帯域幅およびノード処理能力の細粒度リソース情報により、タスクを再スケジューリングする完了見込み時間を取得することと、遅いタスクを組み合わせ再実行するスキームを設計し、遅いタスクを組み合わせ再実行する完了見込み時間を取得することと、最適な遅いタスクを組み合わせ再実行するスキームを設計し、タスクを再スケジューリングする完了見込み時間および遅いタスクを組み合わせ再実行する完了見込み時間により、組み合わせ再実行を最適化した目標方程式を取得することと、重みを設置し、組み合わせ再実行を最適化した目標方程式を用いて効果的に短縮された予測実行タスクの動作時間を取得することとを含む予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法を開示する。
2020524313.tif 000002
【特許請求の範囲】
【請求項１】
組み合わせ最適化の予測実行技術ＣＲＥＳＴに基づき、予測実行タスクのスケジューリングモデルを組み合わせ最適化することと、
前記予測実行タスクのスケジューリングモデルに基づき、ノード間の帯域幅およびノード処理能力の細粒度リソース情報を収集することと、
前記ノード間の帯域幅および前記ノード処理能力の細粒度リソース情報により、タスクを再スケジューリングする完了見込み時間を取得することと、
遅いタスクを組み合わせ再実行するスキームを設計し、遅いタスクを組み合わせ再実行する完了見込み時間を取得することと、
最適な遅いタスクを組み合わせ再実行するスキームを設計し、前記タスクを再スケジューリングする完了見込み時間および前記遅いタスクを組み合わせ再実行する完了見込み時間により、組み合わせ再実行を最適化した目標方程式を取得することと、
重みを設置し、前記組み合わせ再実行を最適化した目標方程式を用いて効果的に短縮された予測実行タスクの動作時間を取得することと、
を含む、予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法。
【請求項２】
前記ＣＲＥＳＴは、（ｉ）予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルと、（ｉｉ）ＣＲＥＳＴにより組み合わせ再実行するスケジューリングアルゴリズムおよびその実現とを含み、前記予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルは１つの有向完全グラフである、請求項１に記載の方法。
【請求項３】
予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルは、
完全グラフでノードを表すネットワークトポロジ構成図とタスク遷移図を採用し、予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルの有向完全グラフの各辺は１つの可能な遷移パスを表し、前記各辺の始点で動作しているタスクを終了し、前記各辺の終点に遷移して再実行することを含む、請求項２に記載の方法。
【請求項４】
前記ノード間の帯域幅およびノード処理能力の細粒度リソース情報は、ノードで動作するＭａｐタスク、前記Ｍａｐタスクが処理するデータ、前記Ｍａｐタスクが処理するデータの大きさ、ノードがこのタイプのＭａｐタスクを完了する進捗速度、およびノード間のネットワーク接続の帯域幅を含む、請求項３に記載の方法。
【請求項５】
前記ノード間の帯域幅および前記ノード処理能力の細粒度リソース情報により、タスクを再スケジューリングする完了見込み時間を取得することは、タスクを再スケジューリングする完了見込み時間の式により、タスクを再スケジューリングする完了見込み時間を取得し、前記タスクを再スケジューリングする完了見込み時間ｔ’ｅｔｆ（ｕ，ｖ）の式は、
【数１】
2020524313.tif 000015
（式中、ｔｃは現在時刻であり、ｔｄａｔａ＿ｍｏｖｅｍｅｎｔはデータ伝送時間であり、（ｕ，ｖ）は有向完全グラフの辺であり、ｕ、ｖは２つのノードであり、ＰＲｖはノードがこのタイプのＭａｐタスクを完了する進捗速度である）であることを含む、請求項４に記載の方法。
【請求項６】
前記遅いタスクを組み合わせ再実行するスキームを設計し、遅いタスクを組み合わせ再実行する完了見込み時間を取得することは、
ｓを遅いタスクの動作ノードとし、ｆをアイドルノードとし、ＰＡＴＨ（ｓ，ｆ）をｓからｆまでの１本のパスとすると、ＰＡＴＨ（ｓ，ｆ）はカスケードに従って辺における始点ノードを含む全てのタスクを終点ノードに遷移して実行し、ＰＡＴＨ（ｓ，ｆ）に沿う遅いタスクの組み合わせ再実行のスキームとして定義されることを含み、
遅いタスクを組み合わせ再実行する完了見込み時間は、所定のＰＡＴＨ（ｓ，ｆ）に沿う遅いタスクの組み合わせ再実行のスキームであれば、その完了見込み時間は全ての遷移作業の完了見込み時間の最大値として定義され、その式は、
【数２】
2020524313.tif 000016
である、請求項５に記載の方法。
【請求項７】
前記最適な遅いタスクを組み合わせ再実行するスキームを設計し、前記タスクを再スケジューリングする完了見込み時間および前記遅いタスクを組み合わせ再実行する完了見込み時間により、組み合わせ再実行を最適化した目標方程式を取得することは、
最適な遅いタスクを組み合わせ再実行するスキームは、完了見込み時間が最小である組み合わせ再実行のスキームとして定義され、ＣＲＥＳで表し、すなわち、最適な遅いタスクを組み合わせ再実行する完了見込み時間は、
【数３】
2020524313.tif 000017
であり、
最適な組み合わせ再実行のスキームに従って取得される完了見込み時間は、
【数４】
2020524313.tif 000018
であり、
タスクを再スケジューリングする完了見込み時間とまとめると、
【数５】
2020524313.tif 000019
という組み合わせ再実行を最適化した目標方程式を取得することを含む、請求項６に記載の方法。
【請求項８】
前記重みを設置し、前記組み合わせ再実行を最適化した目標方程式を用いて効果的に短縮された予測実行タスクの動作時間を取得することは、
前記予測実行タスクのスケジューリングモデルの図における有向辺（ｕ，ｖ）の重みをｔ’ｅｔｆ（ｕ，ｖ）とし、組み合わせ再実行を最適化した目標方程式により、効果的に短縮された予測実行タスクの動作時間を取得することである、請求項７に記載の方法。
【請求項９】
前記重みｔ’ｅｔｆ（ｕ，ｖ）が０よりも大きい、請求項８に記載の方法。
【請求項１０】
レプリカ最適化選択ポリシーを用いてデータ伝送を加速し、前記データ伝送時間の式は、
【数６】
2020524313.tif 000020
（式中、ｄ（Ｔｕ）はｕ以外のノードからｖへ伝送することを表し、Ｔｕはノードｕで動作するＭａｐタスクであり、ｄ（Ｔｕ）はＴｕの処理するデータであり、｜ｄ（Ｔｕ）｜はｄ（Ｔｕ）の大きさであり、ｂｗ（ｕ，ｖ）はノードｕ、ｖ間のネットワーク接続の帯域幅である）である、請求項５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１８年０５月２４日に中国専利局に出願した出願番号が２０１８１０５１０２７１．Ｘの中国特許出願に基づく優先権を出張するものであり、該出願の全ての内容を引用により本願に援用する。
【０００２】
本願はオフライン作業のスケジューリング方法に関し、例えば、予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法に関する。
【背景技術】
【０００３】
送配電ビッグデータアプリケーションには大容量データのリアルタイム処理を実現する必要があり、関連する並列処理技術に依存する必要があると同時に、相関計算と記憶能力の柔軟性、信頼性、管理可能性および経済性を更に強調する。そのうち、ＭａｐＲｅｄｕｃｅ等のようなオフライン作業をスケジューリングする時に、ＭａｐＲｅｄｕｃｅ作業の動作時間は、実行時間が最も長いＭａｐタスクと動作時間が最も長いＲｅｄｕｃｅタスクの動作時間との合計により決定されるため、作業の動作時間を最も短くするためには、Ｍａｐタスクの動作時間とＲｅｄｕｃｅタスクの動作時間の最大値を最小化する必要がある。そのため、ＭａｐＲｅｄｕｃｅ作業の動作時間をどのように最小化するかは、Ｍｉｎ−Ｍａｘ最適化の問題に変換される。関連技術では、作業の動作時間の基本的な最小化を実現することができるが、最適な場合に性能利得を効果的に増加させることができず、且つ、分散コンピューティング環境におけるリソースの異種性および動的性に良好に適用することができない。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本願は上記関連技術に存在する欠陥を克服するために、予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法を提供する。
【０００５】
Ｒｅｄｕｃｅタスクの数が少ないため、タスクの伝送する必要があるデータセットが小さく、その入力データが全てのＭａｐタスクから取得する必要があり、データのローカル性の問題が存在しない。よって、ＣＲＥＳＴ技術を採用して全てのＭａｐタスクにおける遅いタスクの動作時間を低減することができるため、Ｍａｐ遅いタスクの予測実行タスクの実行時間ｔｓｐｅｃをどのように最小化するかという問題に更に変換することができる。
【０００６】
オフラインスケジューリングをサポートする１つのネットワークにおいて、タスクのノード間の帯域幅が小さく、タスクのノードの処理能力が異なり、予測実行タスクをスケジューリングする時にデータのローカル性のニーズを考慮する必要がある。分散コンピューティング環境におけるリソースの異種性および動的性に対し、一連のリソース監視の方法とシステムが発生した。それと同時に、ＭａｐＲｅｄｕｃｅ作業におけるタスクの実行時間モデルと、サンプルタスクのサンプリング動作によりノードのタスクに対する処理能力を予測する等の方法についても、良好な適用効果を取得した。そのため、分散コンピューティング環境におけるノード間の帯域幅およびタスクを処理する能力等の細粒度リソース情報は、予測実行タスクのスケジューリングを最適化するために用いることができる。
【課題を解決するための手段】
【０００７】
上記内容に基づき、本願は、予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法に関し、該方法は以下のステップＳ１〜ステップＳ６を含む。
【０００８】
ステップＳ１において、組み合わせ最適化の予測実行技術（Ｃｏｍｂｉｎａｔｉｏｎ  Ｒｅ−Ｅｘｅｃｕｔｉｏｎ  Ｓｐｅｃｕｌａｔｉｖｅ  Ｔｅｃｈｎｏｌｏｇｙ、ＣＲＥＳＴ）に基づき、予測実行タスクのスケジューリングモデルを組み合わせ最適化する。
【０００９】
ＣＲＥＳＴは、（ｉ）予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルと、（ｉｉ）ＣＲＥＳＴにより組み合わせ再実行するスケジューリングアルゴリズムおよびその実現とを含む。各計算ノード間にいずれも直接なネットワーク接続が存在し、すなわち、任意の２点の通信には３つ目のノードによる転送が必要としないため、完全グラフでノードを表すネットワークトポロジ構成図とタスク遷移図を採用する。予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルは１つの有向完全グラフであり、各辺は１つの可能な遷移パスを代表し、すなわち、該辺の始点で動作しているタスクを終了し、該辺の終点に遷移して再実行する。
【００１０】
予測実行タスクのスケジューリングには一般的にＬＡＴＥとＣＲＥＳＴとの２種類のメカニズムが存在する。
【００１１】
１）予測タスクの最長完了時間のスケジューリングメカニズム（Ｌｏｎｇｅｓｔ  Ａｐｐｒｏｘｉｍａｔｅ  Ｔｉｍｅ  ｔｏ  Ｅｎｄ、ＬＡＴＥ）：アイドルリソースで予測実行タスクを直接動作する。
【００１２】
２）ＣＲＥＳＴ：組み合わせ再実行のメカニズムであって、その組み合わせ再実行のスキームは、遅いタスクノードからアイドルノードまでの１本の非巡回パスと見なすことができる。該パスにおける各辺に対し、その始点におけるタスクはその終点に遷移されて再実行され、順次順延し、遅いタスクノードにおける遅いタスクが保留されて引き続き実行される。組み合わせ再実行のメカニズムにおいてノード間の作業交換の状況が存在せず、すなわち、パスにループが存在しないとすると、既に動作しはじめた作業はそのデータが既にノードのローカルに伝送され、且つＭａｐタスクの負荷はほぼ同等であり、最初に作業を割り当てる時に既にデータのローカル性の要求を考慮したため、ノード間の作業交換が性能利得をもたらしていない。
【００１３】
ステップＳ２において、ノード間の帯域幅およびノード処理能力の細粒度リソース情報を導入する。
【００１４】
有向完全グラフの辺（ｕ，ｖ）については、Ｔｕがノードｕで動作するＭａｐタスクを表し、ｄ（Ｔｕ）がＴｕの処理するデータを表し、｜ｄ（Ｔｕ）｜がｄ（Ｔｕ）の大きさを表し、ＰＲｖがノードのこのタイプのＭａｐタスクを完了する進捗速度（Ｐｒｏｇｒｅｓｓ  Ｒａｔｅ）を表し、ｂｗ（ｕ，ｖ）がノードｕ、ｖ間のネットワーク接続の帯域幅を表すことにする。
【００１５】
ステップＳ３において、タスクを再スケジューリングする完了見込み時間を取得する。
【００１６】
所定のノードｕで実行するＭａｐタスクをノードｖに再スケジューリングして実行すると、その完了見込み時間（Ｅｘｐｅｃｔｅｄ  Ｔｉｍｅｔｏ  Ｆｉｎｉｓｈ、ＥＴＦ）をｔ’ｅｔｆ（ｕ，ｖ）で表し、以下の式として定義する。
【００１７】
【数１】
2020524313.tif 000003
【００１８】
式中、ｔｃは現在時刻を表す。データ伝送時間ｔｄａｔａ＿ｍｏｖｅｍｅｎｔは以下の数式により得られる。
【００１９】
【数２】
2020524313.tif 000004
【００２０】
なお、ｄ（Ｔｕ）はｕ以外のノードからｖに伝送されてもよく、アルゴリズムの実現においてレプリカ最適化選択ポリシーを用いて伝送を加速する。
【００２１】
ステップＳ４において、遅いタスクを組み合わせ再実行するスキームを取得する。
【００２２】
所定のｓは遅いタスクの動作ノードを表し、ｆはアイドルノードを表し、ＰＡＴＨ（ｓ，ｆ）はｓからｆまでの１本のパスを表し、ＰＡＴＨ（ｓ，ｆ）はカスケードに従って辺における始点ノードを含む全てのタスクを終点ノードに遷移して実行し、ＰＡＴＨ（ｓ，ｆ）に沿う遅いタスクの組み合わせ再実行のスキームとして定義される。
【００２３】
遅いタスクを組み合わせ再実行する完了見込み時間は、所定のＰＡＴＨ（ｓ，ｆ）に沿う遅いタスクの組み合わせ再実行のスキームであれば、その完了見込み時間は全ての遷移作業の完了見込み時間の最大値として定義され、その式は以下のとおりである。
【００２４】
【数３】
2020524313.tif 000005
【００２５】
ステップＳ５において、最適な遅いタスクを組み合わせ再実行するスキームを取得する。
【００２６】
最適な遅いタスクを組み合わせ再実行するスキームは、完了見込み時間が最小である組み合わせ再実行のスキームとして定義され、ＣＲＥＳで表し、すなわち、最適な遅いタスクを組み合わせ再実行する完了見込み時間は以下のとおりである。
【００２７】
【数４】
2020524313.tif 000006
【００２８】
最適な組み合わせ再実行のスキームに従って取得された遅いタスクの予測実行の完了見込み時間は以下のとおりである。
【００２９】
【数５】
2020524313.tif 000007
【００３０】
ステップＳ３とまとめると、以下のような組み合わせ再実行を最適化した目標方程式を取得することができる。
【００３１】
【数６】
2020524313.tif 000008
【００３２】
ステップＳ６において、重みを調節し、短縮された予測実行タスクの動作時間を取得する。
【００３３】
タスクスケジューリングモデルの図における有向辺（ｕ，ｖ）の重みをｔ’ｅｔｆ（ｕ，ｖ）とし、該重み値が０よりも大きければ、最適な遅いタスクを組み合わせ再実行するスキームは、タスクスケジューリングモデルの図において１本の最適なパス（ＣＲＥＳ）として具体化され、該パスの重み値は含まれた辺の重み値の算術加算ではなく、含まれた辺の重み値の最大値である。最適化すると、効果的に短縮された予測実行タスクの動作時間を取得することができる。
【発明の効果】
【００３４】
関連技術と比べ、本願は以下の利点を有する。
【００３５】
（１）本願はＣＲＥＳＴ技術を採用することで、平均で５０％以上の予測実行タスクの動作時間を短縮することができ、最適な場合、この性能利得が７０％に達することができる。それと同時に、ＣＲＥＳＴ技術を採用する時に、４０％以上の性能利得を取得する確率が５０％を超え、レプリカ数係数の増大に従い、ＣＲＥＳＴ技術を採用した性能の向上幅は更に大きくなる。
【００３６】
（２）本願はノード間の帯域幅およびノード処理能力の細粒度リソース情報を導入して組み合わせ最適化のメカニズムを設計し、予測実行タスクのデータのローカル性のニーズを満たすことができ、分散コンピューティング環境におけるリソースの異種性および動的性に良好に適用する。
【図面の簡単な説明】
【００３７】
【図１】本願の実施例に係る予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法のフローチャートである。
【発明を実施するための形態】
【００３８】
以下、図面および具体的な実施例を参照しながら本願を詳細に説明する。
【００３９】
実施例
図１に示すように、本願は、以下のステップ１１０〜ステップ１６０を含む予測実行タスクの実行時間を組み合わせ最適化するスケジューリング方法に関する。
【００４０】
ステップ１１０において、ＣＲＥＳＴ技術に基づき、予測実行タスクのスケジューリングモデルを組み合わせ最適化する。
【００４１】
ステップ１２０において、ノード間の帯域幅およびノード処理能力の細粒度リソース情報を収集する。
【００４２】
式中、ノード処理能力の細粒度のリソース情報は、主にノードで動作するＭａｐタスク、前記Ｍａｐタスクが処理するデータ、前記Ｍａｐタスクが処理するデータの大きさ、ノードがこのタイプのＭａｐタスクを完了する進捗速度、およびノード間のネットワーク接続の帯域幅を含む。
【００４３】
ステップ１３０において、ノード間の帯域幅およびノード処理能力の細粒度リソース情報により、タスクを再スケジューリングする完了見込み時間を取得する。
【００４４】
ステップ１４０において、遅いタスクを組み合わせ再実行するスキームを設計し、遅いタスクを組み合わせ再実行する完了見込み時間を取得する。
【００４５】
ステップ１５０において、最適な遅いタスクを組み合わせ再実行するスキームを設計し、前記タスクを再スケジューリングする完了見込み時間および前記遅いタスクを組み合わせ再実行する完了見込み時間により、組み合わせ再実行を最適化した目標方程式を取得する。
【００４６】
ステップ１６０において、重み値を設置し、組み合わせ再実行を最適化した目標方程式を用いて効果的に短縮された予測実行タスクの動作時間を取得する。
【００４７】
オフラインスケジューリングをサポートする１つのネットワークにおいて、タスクのノード間の帯域幅が小さく、タスクのノードの処理能力が異なり、予測実行タスクをスケジューリングする時にデータのローカル性のニーズを考慮する必要がある。分散コンピューティング環境におけるリソースの異種性および動的性に対し、一連のリソース監視の方法とシステムが発生した。それと同時に、ＭａｐＲｅｄｕｃｅ作業におけるタスクの実行時間モデルと、サンプルタスクのサンプリング動作によりノードのタスクに対する処理能力を予測する等の方法についても、良好な適用効果を取得した。そのため、分散コンピューティング環境におけるノード間の帯域幅およびタスクを処理する能力等の細粒度リソース情報は、予測実行タスクのスケジューリングを最適化するために用いることができる。
【００４８】
ＣＲＥＳＴは、細粒度リソース情報を介して、組み合わせ最適化のメカニズムにより予測実行タスクのデータのローカル性のニーズを満たし、データ伝送の時間のオーバヘッドをなくし、更に作業全体のＭａｐ段階の実行時間を大幅に短縮する最適化技術である。ＣＲＥＳＴ技術は、予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルと、ＣＲＥＳＴにより組み合わせ再実行するスケジューリングアルゴリズムおよびその実現との２部分を含む。各計算ノード間にいずれも直接なネットワーク接続が存在し、すなわち、任意の２点の通信には３つ目のノードによる転送が必要としないため、完全グラフでノードを表すネットワークトポロジ構成図とタスク遷移図を採用することができる。予測実行タスクをＣＲＥＳＴにより組み合わせ最適化するスケジューリングモデルは１つの有向完全グラフであり、各辺は１つの可能な遷移パスを代表し、すなわち、該辺の始点で動作しているタスクを終了し、該辺の終点に遷移して再実行する。一般的には、予測実行タスクのスケジューリングにＬＡＴＥとＣＲＥＳＴとの２種類のメカニズムが存在する。
【００４９】
１）ＬＡＴＥ：アイドルリソースで予測実行タスクを直接動作する。
【００５０】
２）ＣＲＥＳＴ：組み合わせ再実行のメカニズムであって、その組み合わせ再実行のスキームは、上記図（有向非巡回グラフ）において遅いタスクノードからアイドルノードまでの１本の非巡回パスと見なすことができる。該パスにおける各辺に対し、その始点におけるタスクはその終点に遷移されて再実行され、順次順延するが、遅いタスクノードにおける遅いタスクが保留されて引き続き実行される。組み合わせ再実行のメカニズムにノード間の作業交換の状況が存在せず、すなわち、パスにループが存在しないとすれば、現実で合理的である。これは、既に動作しはじめた作業はそのデータが既にノードのローカルに伝送され、且つＭａｐタスクの負荷はほぼ同等であり、最初に作業を割り当てる時に既にデータのローカル性の要求を考慮したため、ノード間の作業交換が性能利得をもたらしていないからである。
【００５１】
ＬＡＴＥに対し、ＣＲＥＳＴはノード間の帯域幅およびノード処理能力の細粒度リソース情報を導入するとともに、組み合わせ最適化のメカニズムを設計し、予測実行タスクのデータのローカル性のニーズを満たす。上記図における辺（ｕ，ｖ）については、Ｔｕがノードｕで動作するＭａｐタスクを表し、ｄ（Ｔｕ）がＴｕの処理するデータを表し、｜ｄ（Ｔｕ）｜がｄ（Ｔｕ）の大きさを表し、ＰＲｖがノードのこのタイプのＭａｐタスクを完了する進捗速度（Ｐｒｏｇｒｅｓｓ  Ｒａｔｅ）を表し、ｂｗ（ｕ，ｖ）がノードｕ、ｖ間のネットワーク接続の帯域幅を表すことにする。
【００５２】
タスクを再スケジューリングする完了見込み時間は、所定のノードｕで実行するＭａｐタスクをノードｖに再スケジューリングして実行すると、その完了見込み時間ｔ’ｅｔｆ（ｕ，ｖ）の定義は以下のとおりである。
【００５３】
【数７】
2020524313.tif 000009
【００５４】
式中、データ伝送時間ｔｄａｔａ＿ｍｏｖｅｍｅｎｔは以下の数式により得られる。
【００５５】
【数８】
2020524313.tif 000010
【００５６】
式中、ｔｃは現在時刻を表す。なお、ｄ（Ｔｕ）はｕ以外のノードからｖに伝送されてもよく、アルゴリズムの実現においてレプリカ最適化選択ポリシーを用いて伝送を加速する。
【００５７】
最適な遅いタスクを組み合わせ再実行するスキームにおいて、所定のｓは遅いタスクの動作ノードを表し、fはアイドルノードを表し、ＰＡＴＨ（ｓ，ｆ）はｓからｆまでの１本のパスを表し、ＰＡＴＨ（ｓ，ｆ）はカスケードに従って辺における始点ノードを含む全てのタスクを終点ノードに遷移して実行し、ＰＡＴＨ（ｓ，ｆ）に沿う遅いタスクの組み合わせ再実行のスキームとして定義される。遅いタスクを組み合わせ再実行する完了見込み時間は、所定のＰＡＴＨ（ｓ，ｆ）に沿う遅いタスクの組み合わせ再実行のスキームであれば、その完了見込み時間は全ての遷移作業の完了見込み時間の最大値として定義され、以下の式のとおりである。
【００５８】
【数９】
2020524313.tif 000011
【００５９】
式中、ＰＡＴＨ（ｓ，ｆ）はｓからｆまでの１本のパスであり、ｔ’ｅｔｆ（ｕ，ｖ）はタスクを再スケジューリングする完了見込み時間である。数式は、遅いタスクを組み合わせ再実行する完了見込み時間が、全てのｓからｆまでのパスに属する有向辺のタスクを再スケジューリングする完了見込み時間の最大値、すなわち、全ての遷移作業の完了見込み時間の最大値として定義されると意味する。
【００６０】
最適な遅いタスクを組み合わせ再実行するスキームにおいて、所定のｓは遅いタスクの動作ノードを表し、ｆはアイドルノードを表す。ＰＡＴＨ（ｓ，ｆ）はｓからｆまでの１本のパスであり、最適な遅いタスクを組み合わせ再実行するスキームは、完了見込み時間が最小である組み合わせ再実行のスキームとして定義され、ＣＲＥＳで表し、以下の式のとおりである。
【００６１】
【数１０】
2020524313.tif 000012
【００６２】
ｔｓｐｅｃ（ＣＲＥＳ）で最適な組み合わせ再実行のスキームに従って取得された遅いタスクの予測実行の完了見込み時間を表し、以下の式となる。
【００６３】
【数１１】
2020524313.tif 000013
【００６４】
数式により、組み合わせ再実行を最適化した目標方程式が得られる。
【００６５】
【数１２】
2020524313.tif 000014
【００６６】
式中、ｆｏｒａｌｌｐａｔｈｃｏｎｎｅｃｔｓは全てのパス接続の組み合わせを表す。
【００６７】
タスクスケジューリングモデルの図における有向辺（ｕ，ｖ）の重みをｔ’ｅｔｆ（ｕ，ｖ）とし、該重み値が０よりも大きければ、最適な遅いタスクを組み合わせ再実行するスキームは、タスクスケジューリングモデルの図において１本の最適なパス（ＣＲＥＳ）として具体化され、該パスの重み値は含まれた辺の重み値の算術加算ではなく、含まれた辺の重み値の最大値である。最適化すると、効果的に短縮された予測実行タスクの動作時間を取得することができる。
【００６８】
大量の実験により、ＣＲＥＳＴ技術を用いることで、平均で５０％以上の予測実行タスクの動作時間を短縮することができ、最適な場合、この性能利得が７０％に達することができる。それと同時に、ＣＲＥＳＴ技術を採用する時に、４０％以上の性能利得を取得する確率が５０％を超える。レプリカ数係数の増大に従い、ＣＲＥＳＴ技術を採用した性能の向上幅は更に大きくなる。
【図１】
2020524313.tif 000021
【国際調査報告】
2020524313.tif 000022
2020524313.tif 000023
2020524313.tif 000024
2020524313.tif 000025