(57)【要約】【課題】タスクグラフ動作のスケジューリングを提供する。【解決手段】ある実施形態のある側面によれば、方法は、タスクのための動作を表わすタスクグラフを取得するステップを含んでいてもよい。タスクグラフは、複数のサブ・タスクグラフを含んでいてもよい。本方法はさらに、前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を実行するための、前記動作の部分集合の並列実行に基づく第一の計算時間を得るステップを含んでいてもよい。本方法はさらに、複数の資源の資源スケジュールに従って複数の資源を使用して前記動作の前記部分集合を実行するための第二の計算時間を得るステップと、前記第一の計算時間と前記第二の計算時間との間の差異を決定するステップとを含んでいてもよい。本方法はさらに、前記差異が閾値を満たすことに応答して、前記複数の資源の前記資源スケジュールに基づいて前記複数の資源を使って前記タスクグラフの前記動作を実行することを含んでいてもよい。【選択図】図１
2020091858.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力に基づいて機械学習モデルを生成するための動作を表わすタスクグラフを取得する段階であって、前記タスクグラフは複数のサブ・タスクグラフを含み、各サブ・タスクグラフは、前記複数の入力のうちの異なるものに対応する、段階と；
前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を、前記動作の前記部分集合の並列実行に基づいて実行するための第一の計算時間を取得する段階と；
複数の資源を該複数の資源の資源スケジュールに従って使って前記動作の前記部分集合を実行するための第二の計算時間を取得する段階と；
前記第一の計算時間と第二の計算時間との間の差異を決定する段階と；
前記差異が閾値を満たすことに応答して、前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することによって、前記複数の資源を使って前記機械学習モデルを生成する段階と；
前記機械学習モデルを未分類の入力に適用して、該未分類の入力を前記複数の入力の分類に関して分類する段階とを含む、
方法。
【請求項２】
前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のうちの各集合について前記動作の前記部分集合を逐次的に実行することを含み、前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフの異なる部分を含み、前記動作の前記部分集合のそれぞれの逐次的実行は、前記複数の資源の前記資源スケジュールに従って実行される、請求項１記載の方法。
【請求項３】
前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフのうちの同数を含む、請求項２記載の方法。
【請求項４】
前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の前記実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まり、前記第二の集合についての前記動作の前記部分集合の前記実行は、前記第一の集合についての前記動作の前記部分集合の前記実行のすぐ後に続く、請求項２記載の方法。
【請求項５】
前記複数の資源の前記資源スケジュールは、前記複数の集合のうちの前記第二の集合についての前記動作の前記部分集合の前記実行が、前記複数の集合のうちの前記第一の集合についての前記動作の前記部分集合の実行が終わる前に始まることを許容するよう構成される、請求項４記載の方法。
【請求項６】
前記複数のサブ・タスクグラフのそれぞれが、前記動作の前記部分集合の同じ構成を含む、請求項１記載の方法。
【請求項７】
前記複数の資源の物理的構成を表わす資源グラフを取得する段階をさらに含み、前記複数の資源の前記資源スケジュールは前記資源グラフに基づく、請求項１記載の方法。
【請求項８】
システムによって実行されると該システムに請求項１記載の方法を実行させるまたは実行するよう指令する命令を記憶するよう構成された一つまたは複数のコンピュータ可読媒体。
【請求項９】
タスクのための動作を表わすタスクグラフを取得する段階であって、前記タスクグラフは複数のサブ・タスクグラフを含む、段階と；
前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を、前記動作の前記部分集合の並列実行に基づいて実行するための第一の計算時間を取得する段階と；
複数の資源を該複数の資源の資源スケジュールに従って使って、前記動作の前記部分集合を実行するための第二の計算時間を取得する段階と；
前記第一の計算時間と前記第二の計算時間との間の差異を決定する段階と；
前記差異が閾値を満足することに応答して、前記複数の資源の前記資源スケジュールに基づいて前記複数の資源を使って、前記タスクグラフの前記動作を実行する段階とを含む、
方法。
【請求項１０】
前記タスクは、複数の入力に基づいて機械学習モデルを生成することを含み、前記複数のサブ・タスクグラフのそれぞれが前記複数の入力のうちの一つに対応し、前記動作を実行することは前記機械学習モデルを生成することにつながる、請求項９記載の方法。
【請求項１１】
前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のうちの各集合について前記動作の前記部分集合を逐次的に実行することを含み、前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフの異なる部分を含み、前記動作の前記部分集合のそれぞれの逐次的実行は、前記複数の資源の前記資源スケジュールに従って実行される、請求項９記載の方法。
【請求項１２】
前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフのうちの同数を含む、請求項１１記載の方法。
【請求項１３】
前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の前記実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まり、前記第二の集合についての前記動作の前記部分集合の前記実行は、前記第一の集合についての前記動作の前記部分集合の前記実行のすぐ後に続く、請求項１１記載の方法。
【請求項１４】
前記複数の資源の前記資源スケジュールは、前記複数の集合のうちの前記第二の集合についての前記動作の前記部分集合の前記実行が、前記複数の集合のうちの前記第一の集合についての前記動作の前記部分集合の実行が終わる前に始まることを許容するよう構成される、請求項１３記載の方法。
【請求項１５】
前記複数のサブ・タスクグラフのそれぞれが、前記動作の前記部分集合の同じ構成を含む、請求項９記載の方法。
【請求項１６】
前記複数の資源の物理的構成を表わす資源グラフを取得する段階をさらに含み、前記複数の資源の前記資源スケジュールは前記資源グラフに基づく、請求項９記載の方法。
【請求項１７】
命令を記憶するよう構成された一つまたは複数のコンピュータ可読媒体と；
前記一つまたは複数のコンピュータ可読媒体に結合された一つまたは複数のプロセッサとを有するシステムであって、前記一つまたは複数のプロセッサは前記命令を実行して前記システムに手順を実行させるよう構成され、前記手順は：
タスクのための動作を表わすタスクグラフを取得する段階であって、前記タスクグラフは複数のサブ・タスクグラフを含む、段階と；
前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を、前記動作の前記部分集合の並列実行に基づいて実行するための第一の計算時間を取得する段階と；
複数の資源を該複数の資源の資源スケジュールに従って使って、前記動作の前記部分集合を実行するための第二の計算時間を取得する段階と；
前記第一の計算時間と前記第二の計算時間との間の差異を決定する段階と；
前記差異が閾値を満足することに応答して、前記複数の資源の前記資源スケジュールに基づいて前記複数の資源を使って、前記タスクグラフの前記動作を実行する段階とを含む、
システム。
【請求項１８】
前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のうちの各集合について前記動作の前記部分集合を逐次的に実行することを含み、前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフの異なる部分を含み、前記動作の前記部分集合のそれぞれの逐次的実行は、前記複数の資源の前記資源スケジュールに従って実行される、請求項１７記載のシステム。
【請求項１９】
前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の前記実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まり、前記第二の集合についての前記動作の前記部分集合の前記実行は、前記第一の集合についての前記動作の前記部分集合の前記実行のすぐ後に続く、請求項１８記載のシステム。
【請求項２０】
前記複数のサブ・タスクグラフのそれぞれが、諸タスクの同じ構成を含む、請求項１７記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示において論じられる実施形態は、タスクグラフ動作のスケジューリングに関する。
【背景技術】
【０００２】
タスクグラフとは、あるタスクを実行するための、動作と動作間のデータの流れとを表わす。たとえば、タスクグラフは、機械学習モデルを生成する機械学習アルゴリズムのための動作およびデータ・フローを表わすことができる。タスクグラフは、タスクグラフ内の動作を実行するために使用されうる、サーバーのクラスターのような装置のクラスターをスケジュールするために使用されうる。
【０００３】
本開示において請求される主題は、何らかの欠点を解決する実施形態、または上記のような環境においてのみ動作する実施形態に限定されない。むしろ、この背景は、本開示に記載されるいくつかの実施形態が実施されうる一つの例示的な技術を示すために与えられているだけである。
【発明の概要】
【課題を解決するための手段】
【０００４】
ある実施形態のある側面によれば、方法は、タスクのための動作を表わすタスクグラフを取得するステップを含んでいてもよい。タスクグラフは、複数のサブ・タスクグラフを含んでいてもよい。本方法はさらに、前記複数のサブ・タスクグラフの集合に対応する前記動作の部分集合を実行するための、前記動作の部分集合の並列実行に基づく第一の計算時間を得るステップを含んでいてもよい。本方法はさらに、複数の資源の資源スケジュールに従って複数の資源を使用して前記動作の前記部分集合を実行するための第二の計算時間を得るステップと、前記第一の計算時間と前記第二の計算時間との間の差異を決定するステップとを含んでいてもよい。本方法はさらに、前記差異が閾値を満たすことに応答して、前記複数の資源の前記資源スケジュールに基づいて前記複数の資源を使って前記タスクグラフの前記動作を実行することを含んでいてもよい。
【０００５】
本実施形態の目的および利点は、少なくとも請求項において具体的に指摘される要素、特徴、および組み合わせによって実現され、達成される。
【０００６】
上記の概括的な説明および下記の詳細な説明は、いずれも例として与えられており、説明するものであり、特許請求の範囲に記載された本発明を制約するものではない。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、添付の図面の使用を通じてさらに具体的かつ詳細に記述され、説明される。
【０００８】
【図１】タスクグラフ動作のスケジューリングに関係した例示的な環境を表わす図である。
【０００９】
【図２Ａ】例示的なタスクグラフを示す図である。
【００１０】
【図２Ｂ】例示的な資源グラフを示す図である。
【００１１】
【図３】タスクグラフ動作のスケジューリングを支援するよう構成されうる例示的なコンピューティング・システムを示す図である。
【００１２】
【図４】タスクグラフ動作をスケジューリングする例示的な方法のフローチャートである。
【００１３】
【図５】タスクグラフ動作をスケジューリングする別の例示的な方法のフローチャートである。
【００１４】
【図６】タスクグラフ動作をスケジューリングする別の例示的な方法のフローチャートである。
【発明を実施するための形態】
【００１５】
タスクの非循環グラフのようなタスクグラフは、特定の機能を完了するための、動作と動作間のデータの流れとを表わしうる。たとえば、タスクグラフは、入力と入力のラベルとに基づいて機械学習モデルを生成する機械学習アルゴリズムのための動作およびデータ・フローを表わしてもよい。タスクグラフにおけるデータの流れおよび動作の配置は、他の動作の終了に基づいていつ特定の動作が開始しうるかに関する制約条件を表わしうる。たとえば、タスクグラフは、第一および第二の動作を示し、第二の動作が使用しうるデータを第一の動作が生成することに基づいて第一の動作と第二の動作との間の関係をモデル化することができる。結果として、第一の動作が完了するまで第二の動作は開始できないことがある。
【００１６】
状況によっては、タスクグラフが非常に大きく、複数の動作を含むことがある。結果として、いくつかの状況においては、単一の装置にタスクグラフの動作を実行させると、動作の実行が遅すぎる結果となることがある。いくつかの実施形態において、タスクグラフの動作を実行する時間を短縮するために、動作は、複数の異なる資源を横断して分散されてもよい。これらおよび他の実施形態では、動作は、資源の利用可能性およびタスクグラフのフローに基づいて、諸資源を横断してスケジュールされうる。タスクグラフの動作を処理するための資源のスケジュールを決定することは、非決定性多項式時間（NP）完全問題である可能性がある。よって、タスクグラフの動作を実行する時間を短縮しうるスケジュールを決定することは困難である可能性がある。
【００１７】
いくつかのタスクグラフは、繰り返し構造を含むことがある。タスクグラフ内の繰り返し構造は、タスクグラフ内で複数回繰り返される構造を含んでいてもよい。たとえば、機械学習アルゴリズムのためのタスクグラフは、個々のサンプルに関するトレーニングが、並行して実行されうる同様の動作を含みうるので、繰り返し構造を有することがある。いくつかの実施形態では、動作を実行するためのスケジュールは、繰り返し構造のグループおよび資源のグループについて決定されてもよい。繰り返し構造のグループにおける繰り返し構造の数は、資源のグループを使って前記動作を実行するためのパイプライン状スケジュールを与える繰り返し構造の数であって、前記動作を集団的に実行する時間を短縮するものに基づいて選択されてもよい。次いで、そのスケジュールは、同じ資源グループを使って、繰り返し構造の他のグループについて逐次的に反復されてもよい。繰り返し構造の複数のグループについて前記スケジュールを反復することによって、タスクグラフの動作を実行するための合計時間が、他の方法と比較して短縮されうる。いくつかの実施形態では、繰り返し構造の諸グループの実行を逐次的に反復するとき、タスクグラフの動作を実行するための合計時間は、タスクグラフの動作を実行するための最小時間に漸近的に近くなりうる。
【００１８】
このように、本開示の一つまたは複数の実施形態によれば、本明細書に記載される動作は、タスクグラフの動作の実行のスケジューリングにおける改善を許容する。タスクグラフの動作の実行のスケジューリングにおける改善は、タスクグラフの動作を実行している可能性がある装置および／またはシステムのような資源のよりよい使用につながる可能性がある。代替的または追加的に、タスクグラフの動作の実行のスケジューリングにおける改善は、資源がタスクグラフの動作を実行する時間を短縮する可能性がある。代替的または追加的に、タスクグラフの動作の実行のスケジューリングにおける改善は、タスクグラフの動作を実行している資源のパフォーマンスを高める可能性がある。たとえば、機械学習アルゴリズムのためのタスクグラフの動作の実行のスケジューリングにおける改善は、サーバーのようなコンピュータ・システムが機械学習モデルをトレーニングするためのレイテンシーおよび時間を減少させることができる。代替的または追加的に、機械学習アルゴリズムのためのタスクグラフの動作の実行のスケジューリングにおける改善は、機械学習モデルを生成するときに使用されうる入力の数を増加させることができ、機械学習モデルが改善されうる。このように、本明細書に開示される実施形態は、機械学習の技術分野、タスクグラフのような大きな動作のための資源のスケジューリング、およびコンピューティング・システム資源の使用における問題を解決しうる。さらに、本明細書に開示される実施形態は、動作を実行するために稼働するコンピューティング・システム資源の処理時間およびレイテンシーを減少させることができる。
【００１９】
本開示の実施形態は、添付の図面を参照して説明される。
【００２０】
図１は、本開示に記載される少なくとも一つの実施形態に従って構成された、タスクグラフ動作のスケジューリングに関する例示的な環境100を表わす図である。環境100は、スケジューリング・モジュール120および実行環境130を含んでいてもよい。
【００２１】
スケジューリング・モジュール120および／または実行環境130は、一つまたは複数のコンピューティング装置またはシステムが、それとともに記述される前記動作の一つまたは複数を実行できるようにするよう構成されたコードおよびルーチンを含んでいてもよい。これらおよび他の実施形態において、スケジューリング・モジュール120および／または実行環境130は、任意の数のプロセッサ、マイクロプロセッサ（たとえば、一つまたは複数の動作を実行するまたはその実行を制御するため）、フィールド・プログラマブル・ゲート・アレイ（FPGA）、特定用途向け集積回路（ASIC）、またはそれらの二つ以上の任意の好適な組み合わせを含むハードウェアを使って実装されてもよい。代替的または追加的に、スケジューリング・モジュール120および実行環境130は、ハードウェアおよびソフトウェアの組み合わせを使って実装されてもよい。本開示において、スケジューリング・モジュール120および実行環境130によって実行されるものとして説明される動作は、スケジューリング・モジュール120および実行環境130が対応するシステムに実行するよう指示しうる動作を含んでいてもよい。
【００２２】
いくつかの実施形態では、環境100は、タスクグラフ110および資源グラフ112を入力として受け取ってもよい。タスクグラフ110は、特定の機能を完了するための、動作と、動作間のデータの流れとを表わしうる。たとえば、タスクグラフ110の頂点が動作を表わしてもよく、タスクグラフ110のエッジが動作間のデータ・フローを表わしてもよい。資源グラフ112は、タスクグラフ110内の動作を実行するために使用されうる実行環境130内の資源132を表わしうる。資源グラフ112の頂点は、資源132を表わしてもよく、資源グラフ112のエッジは、資源132間の物理的接続と、該物理的接続に沿ったデータ転送速度とを表わしうる。
【００２３】
いくつかの実施形態では、資源グラフ112において表現される資源は、タスクグラフからの入力に基づいて、タスクグラフ110内の動作の一部、全部、または複数を実行するよう構成された物理的装置を表わしていてもよい。タスクグラフ110において定義される前記入力および動作を使って、資源は、タスクグラフ110内の動作についての出力を生成することができる。
【００２４】
これらおよび他の実施形態において、資源グラフ112において表現される資源は、コンピューティング・ユニットを含んでいてもよい。たとえば、コンピューティング・ユニットは、中央処理ユニット（CPU）、グラフィックス処理ユニット（GPU）、プロセッサ、マルチコアプロセッサのプロセッサコア、FPGA、ASIC、またはハードウェア要素の他の組み合わせを含んでいてもよい。これらおよび他の実施形態において、単一の装置が、複数のコンピューティング・ユニット、よって、複数の資源を含んでいてもよい。代替的または追加的に、資源グラフ112において表現される資源は、装置を含んでいてもよい。該装置は、他の装置の中でも、プロセッサとメモリの組み合わせのようなコンピューティング・システム、たとえばモバイル装置、サーバー、パーソナルコンピュータなどを含んでいてもよい。
【００２５】
図２Ｂは、本開示の少なくとも一つの実施形態による、例示的な資源グラフ210を示している。資源グラフ210は、資源R1、R2、およびR3を表わしうる三つの頂点を含んでいてもよい。頂点間のエッジは、資源間のネットワーク接続を、よってどの資源が他の資源と通信しうるかを示していてもよい。図のように、各資源は他の資源と通信してもよい。しかしながら、いくつかの資源グラフでは、各資源は相互接続されなくてもよい。
【００２６】
いくつかの実施形態では、エッジは、資源間のネットワーク接続の速度に関する情報をも含んでいてもよい。図のように、資源R1と資源R2の間のネットワーク接続は10GB/sであってもよい。資源R2と資源R3の間のネットワーク接続は15GB/sであってもよく、資源R1と資源R3との間のネットワーク接続は5GB/sであってもよい。図示するところでは、ネットワーク接続はすべて異なる。代替的または追加的に、ネットワーク接続のそれぞれは同じであってもよく、または、ネットワーク接続のいくつかは同じであって他のものは異なっていてもよい。
【００２７】
いくつかの実施形態では、資源グラフ210はまた、資源グラフ210内の資源に関するタスクグラフ内の動作のパフォーマンスに関する情報を含んでいてもよい。たとえば、資源グラフ210は、資源グラフ210内の各資源がタスクグラフ内の各動作を実行する時間に関する情報を含んでいてもよい。代替的または追加的に、資源グラフ210は、各資源についてのメモリ量と、タスクグラフ内の各動作を実行するための資源グラフ210内の各資源についてのメモリ要件とに関する情報を含んでいてもよい。
【００２８】
いくつかの実施形態では、資源グラフ210内の情報は、タスクグラフの総処理時間を決定するために使用されてもよい。代替的または追加的に、資源グラフ210内の情報は、資源グラフ210内の資源を使う処理のためにタスクグラフ内の動作のスケジューリングを決定するために使用されてもよい。これらおよび他の実施形態において、タスクグラフの動作のスケジューリングは、資源グラフ210内の資源の制約条件およびタスクグラフの動作フローに基づいて、タスクグラフ内の各動作を実行しうる資源を選択することを指してもよい。
【００２９】
たとえば、いくつかの実施形態では、資源グラフ210は、どの資源がタスクグラフ内の動作を実行するかを決定するのを助けるように使用されてもよい。たとえば、ある動作が特定の資源についてのメモリ量より大きいメモリ量を使用する場合、その動作はその特定の資源に割り当てられない可能性がある。代替的または追加的に、ある特定の資源がある量のメモリを使用する特定の動作を実行している場合、その特定の資源は、重複する時間区間の間は、その特定の動作のメモリ使用と組み合わされたらその特定の資源のメモリ量より大きいメモリ量を使用することになりうる他の動作を実行しなくてもよい。
【００３０】
別の例として、いくつかの実施形態では、資源グラフ210はまた、他の動作からの出力に基づくタスクグラフ内の動作が、資源の動作時間および資源間のネットワーク・レイテンシーに基づいて開始されうる時を決定するために使用されてもよい。たとえば、資源R1が第一の動作を実行し、資源R2が第一の動作からの出力に基づいて第二の動作を実行する場合、資源グラフ210は、資源R1と資源R2との間で情報を送信するための時間遅延および資源R1が第一の動作を実行するための時間を決定するために使用されてもよい。こうして、資源グラフ210は、資源R1によって第一の動作を実行する時間および資源R1と資源R2との間のネットワーク接続に基づいて、資源R2が第二の動作を処理し始めてもよい時間を決定するために使用されてもよい。
【００３１】
図１の議論に戻ると、いくつかの実施形態では、タスクグラフ110は、複数のサブ・タスクグラフを含んでいてもよい。タスクグラフのサブ・タスクグラフは、タスクグラフの他のサブ・タスクグラフに含まれないタスクグラフの複数の頂点を含んでいてもよい。いくつかの実施形態において、サブ・タスクグラフのそれぞれは、類似または同一の構成を含んでいてもよい。たとえば、各サブ・タスクグラフは同じ数および配置の頂点を含んでいてもよく、各頂点は同じ動作に対応していてもよく、それによりサブ・タスクグラフは諸動作の同じ構成を含んでいてもよい。
【００３２】
いくつかの実施形態において、サブ・タスクグラフは、入力について互いに依存しなくてもよい。これらおよび他の実施形態では、サブ・タスクグラフは、並列に実行されてもよい。たとえば、サブ・タスクグラフの一部またはサブ・タスクグラフのすべては、タスクグラフ110の動作から独立した入力から、またはタスクグラフ110の別の部分から入力を得ることができる。たとえば、いくつかの実施形態では、サブ・タスクグラフのそれぞれは、タスクグラフ110において実行される動作とは無関係な源からの入力を得てもよい。代替的または追加的に、各サブ・タスクグラフは、そのサブ・タスクグラフの一部ではない、タスクグラフ110において実行される一つまたは複数の動作から、入力を得てもよい。いくつかの実施形態では、サブ・タスクグラフのそれぞれのための一つまたは複数の入力は、異なっていてもよい。代替的または追加的に、サブ・タスクグラフのうちの一つまたは複数は同じ入力を有していてもよい。
【００３３】
いくつかの実施形態では、諸動作の同じ構成を含み、入力について互いに依存しないサブ・タスクグラフは、本開示では、タスクグラフ110内の繰り返しサブ・タスクグラフと称されることがある。
【００３４】
図２Ａは、本開示の少なくとも一つの実施形態による、例示的なタスクグラフ200を示している。タスクグラフ200は、タスクグラフ200において実行されうる動作1〜13を表わす、1〜13とラベル付けされた13の頂点を含んでいてもよい。いくつかの実施形態では、動作1、5、および9は同じ動作であってもよく、動作2、6、および10は同じ動作であってもよく、動作3、7、および11は同じ動作であってもよく、動作4、8、および12は同じ動作であってもよい。
【００３５】
図示されるタスクグラフ200は、三つのサブ・タスクグラフを含んでいてもよい。第一のサブ・タスクグラフは、動作1〜4を含んでいてもよい。第二のサブ・タスクグラフは動作5〜8を含んでいてもよく、第三のサブ・タスクグラフは動作9〜12を含んでいてもよい。各サブ・タスクグラフは、独立した入力を得てもよい。代替的または追加的に、各サブ・タスクグラフは、動作13に出力を提供してもよい。これらおよび他の実施形態において、三つのサブ・タスクグラフは、繰り返しサブ・タスクグラフ（recurring  sub-task  graph）でありうる。なぜなら、各サブ・タスクグラフは、同じ構成の動作を含んでいてもよく、各サブ・タスクグラフは、入力について、それらのサブ・タスクグラフのうちの他のものに依存しないからである。
【００３６】
図１の議論に戻ると、タスクグラフ110および資源グラフ112はスケジューリング・モジュール120に提供されてもよい。スケジューリング・モジュール120は、資源グラフ112において表現される資源132によってタスクグラフ110内の動作を実行するためのスケジュール122を決定するよう構成されてもよい。スケジュール122は、各動作について、動作の開始時間と、資源132のうちの一つまたは複数のうちのどれが動作を実行しうるかとを示してもよい。スケジュール122はまた、タスクグラフ110内の動作すべてを処理するための総処理時間を提供してもよい。
【００３７】
いくつかの実施形態では、スケジュール・モジュール120は、スケジュール122が、資源132を使ってタスクグラフ110内の動作のすべてを処理するための時間を最小にするおよび／または処理時間を短縮するよう、スケジュール122を決定するよう構成されてもよい。先に示したように、いくつかのタスクグラフについては、タスクグラフ110および資源グラフ112を使用してスケジュールを生成することは、NP完全問題でありうる。よって、タスクグラフ110内の動作すべてを使用してスケジュールを生成することは困難であり、時間がかかることがありうる。これらおよび他の実施形態において、スケジューリング・モジュール120は、タスクグラフ110のいくつかのサブ・タスクグラフについてのサブスケジュールを決定し、それらのサブ・タスクグラフのサブスケジュールをタスクグラフ110の他のサブ・タスクグラフに適用してスケジュール122を決定することに基づいて、スケジュール122を決定するよう構成されてもよい。
【００３８】
いくつかの実施形態では、スケジューリング・モジュール120は、タスクグラフ110内のサブ・タスクグラフを識別することによってサブスケジュールを決定するよう構成されてもよい。これらおよび他の実施形態において、スケジューリング・モジュール120は、同じ動作構成を含み、入力について互いに依存しない繰り返しサブ・タスクグラフを識別するよう構成されてもよい。繰り返しサブ・タスクグラフを識別した後、スケジューリング・モジュール120は、サブスケジュールの間に一緒にスケジュールされうる繰り返しサブ・タスクグラフの数を決定するよう構成されてもよい。この数は、その数の繰り返しサブ・タスクグラフにわたる処理時間を最小化または短縮するものである。
【００３９】
たとえば、一つの特定の繰り返しサブ・タスクグラフについての処理時間は、資源132がその特定の繰り返しサブ・タスクグラフの処理が終了するまで他の動作を実行していないとして、時間T1であってもよい。二つの繰り返しサブ・タスクグラフについての処理時間は、資源132がそれら二つの繰り返しサブ・タスクグラフの処理が終了するまで他の動作を実行していないとして、時間T2であってもよい。しかしながら、資源132の構成および複数の資源にわたるパイプライン処理の性質を考えると、T2＜2×T1である。このように、二つ以上の繰り返しサブ・タスクグラフを重複する時間期間における資源132による処理のためにスケジューリングすることは、効率を生み出す可能性がある。しかしながら、何らかの点で、多数の繰り返しサブ・タスクグラフについて重複する時間期間においてスケジューリングを実行すると、各繰り返しサブ・タスクグラフのための処理時間の追加的な増大につながる可能性がある。
【００４０】
いくつかの実施形態では、サブスケジュールの間に一緒にスケジュールされうる繰り返しサブ・タスクグラフの数を決定することであって、この数は、その数の繰り返しサブ・タスクグラフにわたる処理時間を最小化または短縮するものである、ことのために、スケジューリング・モジュール120は、一緒にスケジュールするべき繰り返しサブ・タスクグラフの数について逐次反復的な探索を実行してもよい。まず、スケジューリング・モジュール120は、一緒にスケジュールするべき繰り返しサブ・タスクグラフの数について、初期数を選択してもよい。スケジューリング・モジュール120は、資源グラフ112に基づいて、繰り返しサブ・タスクグラフの初期数についての処理時間を決定してもよい。スケジューリング・モジュール120はまた、繰り返しサブ・タスクグラフの初期数についての最小処理時間をも決定するよう構成されてもよい。スケジューリング・モジュール120は、前記処理時間と前記最小処理時間とを比較して、前記処理時間と前記最小処理時間との差異を決定してもよい。前記差異が閾値を満たすことに応答して、スケジューリング・モジュール120は、一緒にスケジュールするための繰り返しサブ・タスクグラフの数についての初期数を選択してもよい。
【００４１】
処理時間と最小処理時間との間の前記差異が閾値を満たさないことに応答して、スケジューリング・モジュール120は、繰り返しサブ・タスクグラフの別の数を選択してもよい。スケジューリング・モジュール120は、資源グラフ112に基づいて、繰り返しサブ・タスクグラフの前記別の数について第二の処理時間を決定してもよい。スケジューリング・モジュール120は、繰り返しサブ・タスクグラフの前記別の数について第二の最小処理時間をも決定するよう構成されてもよい。スケジューリング・モジュール120は、第二の処理時間と第二の最小処理時間との間の第二の差異を決定することができる。第二の差異が閾値を満たすことに応答して、スケジューリング・モジュール120は、一緒にスケジュールするべき繰り返しサブ・タスクグラフの数について、前記別の数を選択してもよい。第二の差異が閾値を満たさないことに応答して、スケジューリング・モジュール120は、繰り返しサブ・タスクグラフの別の数を選択し、処理時間と最小処理時間との差異が閾値を満足するまで、上記で論じたように逐次反復を続けてもよい。
【００４２】
いくつかの実施形態では、資源グラフ112に基づく特定の数の繰り返しサブ・タスクグラフについての処理時間は、その特定の数の繰り返しサブ・タスクグラフについての処理時間を短縮および／または最小化するスケジュールの発見的探索に基づいて決定されてもよい。発見的探索は、タスクグラフ110および資源グラフ112に関連する制約条件を考慮に入れてもよい。これらおよび他の実施形態において、任意の型の発見的探索が実行されてもよい。代替的または追加的に、特定の数の繰り返しサブ・タスクグラフについての処理時間を決定するために、他の型のアルゴリズムが使用されてもよい。
【００４３】
いくつかの実施形態では、特定の数の繰り返しサブ・タスクグラフについての最小処理時間は、それらの繰り返しサブ・タスクグラフ内の動作すべての並列実行に基づくことができる。たとえば、特定の数の繰り返しサブ・タスクグラフについての最小処理時間は、タスクグラフ110および資源グラフ112の制約条件なしに動作が並列に実行される場合に、各動作を処理するための処理時間であってもよい。代替的または追加的に、特定の数の繰り返しサブ・タスクグラフについての最小処理時間は、その特定の数の繰り返しサブ・タスクグラフを処理するための時間の、トリビアルな下限に基づいて決定されてもよい。トリビアルな下限は、それらの繰り返しサブ・タスクグラフ内の各プロセスについての個々の処理時間の合計を、それらの繰り返しサブ・タスクグラフ内のプロセスの数で割ったものを含んでいてもよい。これらおよび他の実施形態では、個々の処理時間は、最小、最大、平均、または他の時間で処理を実行する処理を実行する資源132のうちの一つに基づいていてもよい。代替的または追加的に、特定の数の繰り返しサブ・タスクグラフの最小処理時間は、線形計画法緩和のような他のアルゴリズムまたは技術に基づいていてもよい。これらおよび他の実施形態では、最小処理時間は、資源132を与えられたときの最小処理時間の推定値であってもよい。
【００４４】
いくつかの実施形態では、スケジューリング・モジュール120は、前記処理時間と前記最小処理時間との間の比を決定することによって、前記処理時間と前記最小処理時間との間の前記差異を決定してもよい。比は閾値と比較されてもよい。これらおよび他の実施形態において、閾値は、ほぼ1に等しくてもよい。
【００４５】
代替的または追加的に、スケジューリング・モジュール120は、前記処理時間から前記最小処理時間を引くことによって、前記処理時間と前記最小処理時間との前記差異を決定してもよい。減算の結果は、閾値と比較されてもよい。これらおよび他の実施形態において、閾値はほぼ0に等しくてもよい。代替的または追加的に、スケジューリング・モジュール120は、前記処理時間および前記最小処理時間を規格化し、規格化された処理時間から規格化された最小処理時間を引いてもよい。減算の結果は、閾値と比較されてもよい。これらおよび他の実施形態において、閾値はほぼ0に等しくてもよい。代替的または追加的に、スケジューリング・モジュール120は、何らかの他のメトリックを使って、処理時間と最小処理時間との間の差異を決定してもよい。
【００４６】
閾値は、上述で論じたように処理時間と最小処理時間とを比較するために使用されるメトリックに基づいて変わってもよい。これらおよび他の実施形態において、閾値は、スケジュール122を決定するためにスケジューリング・モジュール120に付与される時間の量に基づいていてもよい。閾値はまた、タスクグラフ110内の動作の数に基づいていてもよい。たとえば、タスクグラフ110がより多くの動作を含むことに応答して、閾値は、該閾値を満足すには処理時間と最小処理時間との差が、異なる閾値と比較して小さくなるように設定されてもよい。処理時間と最小処理時間との間の差を減らすことは、実行環境130におけるタスクグラフ110の処理時間を短縮しうる。代替的または追加的に、閾値は、最小処理時間の推定の品質に基づいていてもよい。たとえば、最小処理時間の推定値が期待されるよりも低いと判別される場合、閾値はより大きくてもよい。代替的または追加的に、閾値は可変であってもよい。これらおよび他の実施形態において、処理時間および最小処理時間が、繰り返しサブ・タスクグラフのその特定の数が増加するときに収束しない場合、閾値は調整されてもよい。
【００４７】
いくつかの実施形態において、閾値は、下限、上限または範囲でありうる。これらおよび他の実施形態において、閾値を満たすために、処理時間と最小処理時間との差異が閾値内であってもよい。たとえば、閾値が下限である場合、処理時間と最小処理時間との差異は、下限よりも小さくてもよい。
【００４８】
サブスケジュールの間に一緒にスケジュールされうる繰り返しサブ・タスクグラフの数を決定した後、スケジューリング・モジュール120は、繰り返しサブ・タスクグラフのそれぞれを処理するために実行されうる逐次的なサブスケジュールの数を決定してもよい。スケジューリング・モジュール120は、繰り返しサブ・タスクグラフの総数を、サブスケジュールの間に一緒にスケジュールされうる繰り返しサブ・タスクグラフの数で割り、次の整数に切り上げることによって、その数を決定してもよい。
【００４９】
これらおよび他の実施形態において、スケジュール122は、その間に複数の繰り返しサブ・タスクグラフが実行されうるサブスケジュールを複数含んでいてもよい。繰り返しサブ・タスクグラフの総数が、繰り返しサブ・タスクグラフの前記数で割り切れる整数である場合、それら複数のサブスケジュールのそれぞれは、同じ数の繰り返しサブ・タスクグラフを処理するためのスケジューリングを含んでいてもよい。繰り返しサブ・タスクグラフの総数が繰り返しサブ・タスクグラフの前記数で割り切れる整数でない場合、それら複数サブスケジュールのそれぞれは、それら複数のサブスケジュールのうちの一つが繰り返しサブ・タスクグラフの前記数より少数を処理するためのスケジューリングを含みうるほかは、同じ数の繰り返しサブ・タスクグラフを処理するためのスケジューリングを含んでいてもよい。
【００５０】
スケジュール122のための逐次的なサブスケジュールの数を決定した後、スケジューリング・モジュール120は、スケジュール122を完了するために、それら逐次的なサブスケジュールの前または後に生起しうる他のプロセスをスケジュールしてもよい。
【００５１】
いくつかの実施形態では、スケジューリング・モジュール120は、現在のサブスケジュールが処理を完結するまでその後のサブスケジュールが開始しないように、逐次的なサブスケジュールのそれぞれをスケジュールすることができる。代替的または追加的に、スケジューリング・モジュール120は、現在のサブスケジュールの処理中にその後のサブスケジュールが開始するように、逐次的なサブスケジュールをスケジュールしてもよい。現在のサブスケジュールの処理中にその後のサブスケジュールが開始することは、サブスケジュールのタイリングと称されることがある。これらおよび他の実施形態において、サブスケジュールのよりよいタイリングを許容するために、一つまたは複数の制約条件が資源グラフ112に追加されてもよい。たとえば、当該サブスケジュール内の動作の第一の部分を実行する資源が、その後のサブスケジュールの動作を自由に開始することができ、当該サブスケジュールの終了時に動作を実行するために使用されないように、制約条件が資源グラフ112に追加されてもよい。
【００５２】
いくつかの実施形態では、スケジュール122は、逐次的な複数のサブスケジュールの複数の逐次反復を含んでいてもよい。たとえば、タスクグラフ110は、複数の繰り返しサブ・タスクグラフから始まってもよく、そこから出力が決定される。該出力は、タスクグラフ110の最終プロセスのために使用されうる、他の複数の繰り返しサブ・タスクグラフのための基礎でありうる。これらの実施形態および他の実施形態において、スケジュール122は、逐次的なサブスケジュール、それに続く、動作のスケジューリング、それに続く他の逐次的なサブスケジュールと、タスクグラフ110からの他の動作を用いた完結とを含むことができる。スケジューリング・モジュール120は、スケジュール122を実行環境130に提供することができる。
【００５３】
実行環境130は、スケジュール122および入力データ114を得てもよい。実行環境130は、スケジュール122に従って、入力データ114に基づいて、資源132を使って、タスクグラフ110の動作を実行するよう構成されてもよい。入力データ114は、タスクグラフ110内の動作がそのために設計されているデータであってもよい。実行環境130は、タスクグラフ110の動作の実行に基づいて出力140を生成してもよい。
【００５４】
ここで、環境100の例示的な動作が与えられる。この例では、タスクグラフ110は、機械学習モデルを生成するための機械学習アルゴリズムのタスクグラフであってもよい。タスクグラフ110は、TensorFlowおよびONNXによって使用されるもののような既知のソフトウェア技術を使用して生成されてもよい。入力データ114は、その上に機械学習モデルが構築されうる入力を含んでいてもよい。入力データ114はさらに、各入力についてのラベルを含んでいてもよい。たとえば、入力は画像であってもよく、ラベルは画像に何が含まれるかの説明であってもよい。入力データ114は、機械学習アルゴリズムによって使用されるパラメータのための初期値をさらに含んでいてもよい。
【００５５】
機械学習アルゴリズムのタスクグラフ110は、100万個の繰り返しサブ・タスクグラフのような、複数の繰り返しサブ・タスクグラフを含んでいてもよい。これらおよび他の実施形態では、入力、ラベル、および入力のための関連パラメータのそれぞれは、一つの繰り返しサブ・タスクグラフに関連付けられてもよい。よって、タスクグラフ110は、複数の繰り返しサブ・タスクグラフから開始することができる。繰り返しサブ・タスクグラフのそれぞれは、出力を生成するための同様の動作を含んでいてもよい。いくつかの実施形態では、動作は、パラメータの即時更新またはバッチ更新を含んでいてもよい。これらおよび他の実施形態において、繰り返しサブ・タスクグラフの出力は、機械学習モデルにおいて使用されう重み付けされたパラメータを生成するために組み合わされてもよく、たとえば平均されてもよい。
【００５６】
スケジューリング・モジュール120は、資源グラフ112に基づいて、サブスケジュールについての繰り返しサブ・タスクグラフの数が18であると決定してもよい。よって、スケジューリング・モジュール120は、18個の繰り返しサブ・タスクグラフの動作を処理するサブスケジュール55,555個が逐次的に実行されて、繰り返しサブ・タスクグラフ999,990個を処理するようにスケジュールしてもよい。スケジューリング・モジュール120はまた、残りの10個の繰り返しサブ・タスクグラフを処理するサブスケジュールをもスケジュールすることができる。代替的または追加的に、スケジューリング・モジュール120は、タスクグラフ110の残りの10個の繰り返しサブ・タスクグラフおよび他の動作を処理するためのスケジュールを決定してもよい。スケジューリング・モジュール120は、スケジュール122を実行環境130に提供してもよい。
【００５７】
実行環境130は、スケジュール122に従い、タスクグラフ110および入力データ114を使用して、機械学習モデルを生成してもよい。機械学習モデルは、入力データ114を使ったトレーニングに基づいて未知の入力を分類するよう構成されてもよい。たとえば、機械学習モデルは、諸動物の画像でトレーニングされると、未知の動物の画像を識別することができる。これらおよび他の実施形態において、本開示に記載される方法および／またはシステムを使用することにより、機械学習モデルのために、より大きなサイズの画像が使用されることが許容されうる。本方法の前には、より大きなサイズの画像は、処理を増加させ、機械学習モデルをトレーニングする際に使用するには実際的ではなかった可能性がある。しかしながら、本開示で論じたようにスケジューリングし、画像を処理するために複数の資源を使用できることによって、より大きな画像サイズが機械学習モデルをトレーニングするために使用されうる。
【００５８】
環境100は、機械学習アルゴリズムのスケジューリングおよび処理以外の目的で使用されてもよい。たとえば、環境100は、深層畳み込みニューラルネットワーク（CNN）、リカレントニューラルネット（RNN）、CNN、RNNの諸変形、全結合ネットワーク、タスクグラフ内の繰り返しサブ・タスクグラフを含みうる他の深層アーキテクチャーを処理するために使用されうる。別の例として、環境100は、コンピュータ・ビジョン・アプリケーションを処理するために使用されてもよい。コンピュータ・ビジョン・アプリケーションは、本開示に記載される仕方でスケジュールされうる繰り返しサブ・タスクグラフを含みうる。
【００５９】
本開示の範囲から逸脱することなく、図１に修正、追加、または省略を行なってもよい。たとえば、環境100は、本開示において図示されかつ説明されたものよりも多くの、または少ない要素を含んでいてもよい。
【００６０】
図３は、本開示の少なくとも一つの実施形態による、格子関連問題を解くよう構成された例示的なコンピューティング・システム302のブロック図を示している。コンピューティング・システム302は、スケジューリング・モジュール（たとえば、図１のスケジューリング・モジュール120）および／または実行環境（たとえば、図１の実行環境130）に関連する一つまたは複数の動作を実装または指揮するように構成されてもよい。いくつかの実施形態では、コンピューティング・システム302は、アニーリング・システムに含まれてもよく、またはアニーリング・システムの一部をなしてもよい。コンピューティング・システム302は、プロセッサ350、メモリ352、およびデータ記憶装置354を含んでいてもよい。プロセッサ350、メモリ352、およびデータ記憶装置354は、通信的に結合されてもよい。
【００６１】
一般に、プロセッサ350は、さまざまなコンピュータ・ハードウェアまたはソフトウェア・モジュールを含む任意の好適な特殊目的または汎用のコンピュータ、コンピューティング・エンティティ、または処理装置を含んでいてもよく、任意の適用可能なコンピュータ読み取り可能記憶媒体に記憶された命令を実行するよう構成されてもよい。たとえば、プロセッサ350は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（DSP）、特定用途向け集積回路（ASIC）、フィールド・プログラマブル・ゲート・アレイ（FPGA）、またはプログラム命令を解釈および／または実行するおよび／またはデータを処理するように構成された任意の他のデジタルまたはアナログ回路を含んでいてもよい。図３では単一のプロセッサとして示されているが、プロセッサ350は、個別にまたは集団的に、本開示に記載される任意の数の動作を実行するまたはその実行を指揮するように構成された任意の数のプロセッサを含んでいてもよい。さらに、該プロセッサの一つまたは複数が、一つまたは複数の異なる電子装置、たとえば異なるサーバー上に存在してもよい。
【００６２】
いくつかの実施形態では、プロセッサ350は、メモリ352、データ記憶装置354、またはメモリ352およびデータ記憶装置354に記憶されたプログラム命令を解釈および／または実行するおよび／またはデータを処理するように構成されてもよい。いくつかの実施形態では、プロセッサ350は、データ記憶装置354からプログラム命令を取り出し、該プログラム命令をメモリ352にロードしてもよい。プログラム命令がメモリ352にロードされた後、プロセッサ350は、該プログラム命令を実行することができる。
【００６３】
メモリ352およびデータ記憶装置354は、コンピュータ実行可能命令またはデータ構造を担持するまたは記憶するためのコンピュータ読取可能な記憶媒体を含んでいてもよい。そのようなコンピュータ読取可能な記憶媒体は、プロセッサ350のような汎用または特殊目的のコンピュータによってアクセスされうる任意の利用可能な非一時的媒体を含んでいてもよい。限定ではなく例として、そのようなコンピュータ読取可能な記憶媒体は、ランダムアクセスメモリ（RAM）、読出し専用メモリ（ROM）、電気的に消去可能なプログラマブル読出し専用メモリ（EEPROM）、コンパクトディスク読出し専用メモリ（CD-ROM）または他の光ディスク記憶、磁気ディスク記憶または他の磁気記憶デバイス、フラッシュメモリ・デバイス（たとえば、ソリッドステートメモリデバイス）、またはコンピュータ実行可能命令またはデータ構造の形で特定のプログラムコードを担持または記憶するために使用でき、汎用または特殊目的のコンピュータによってアクセスされうる任意の他の非一時的記憶媒体を含む、有体なまたは非一時的なコンピュータ読取可能な記憶媒体を含んでいてもよい。これらおよび他の実施形態において、本開示で説明される「非一時的」という用語は、In  re  Nuijten,  500  F.3d  1346の連邦巡回控訴裁判所の決定（Fed.  Cir.  2007）において特許可能な主題の範囲外であると認定された型の一時的媒体のみを除外すると解釈されるべきである。上記の組み合わせも、コンピュータ読取可能媒体の範囲内に含まれうる。
【００６４】
上記の組み合わせも、コンピュータ読取可能な記憶媒体の範囲内に含まれうる。コンピュータ実行可能命令は、たとえば、プロセッサ350にある種の動作または一群の動作を実行させるよう構成された命令およびデータを含んでいてもよい。
【００６５】
本開示の範囲から逸脱することなく、コンピューティング・システム302に修正、追加、または省略を行なってもよい。たとえば、いくつかの実施形態では、コンピューティング・システム302は、明示的に図示または説明されないことがありうる任意の数の他の構成要素を含んでいてもよい。
【００６６】
図４は、本開示に記載される少なくとも一つの実施形態による、タスクグラフ動作をスケジューリングする例示的な方法400のフローチャートである。方法400は、任意の好適なシステム、装置、またはデバイスによって実行されうる。たとえば、方法400の一つまたは複数の動作は、図１の環境100の一つまたは複数の要素によって、または図３のコンピューティング・システム302または図３のコンピューティング・システム302の複数によって実行されてもよい。離散的なブロックで示されているが、方法400のブロックの一つまたは複数に関連するステップおよび動作は、特定の実装に依存して、追加的なブロックに分割されてもよく、より少数のブロックに結合されてもよく、または除去されてもよい。
【００６７】
方法400はブロック402で始まってもよく、ここで、タスクグラフが得られてもよい。ブロック404では、タスクグラフ内のサブ・タスクグラフが識別されてもよい。いくつかの実施形態では、繰り返しサブ・タスクグラフが識別されてもよい。これらおよび他の実施形態において、繰り返しサブ・タスクグラフの数が決定されてもよい。代替的または追加的に、繰り返しサブ・タスクグラフの実行を許容するために実行されるべき動作が決定されてもよい。たとえば、タスクグラフは、N個の入力に関して機械学習モデルをトレーニングするための複数入力トレーニング・タスクグラフを含んでいてもよい。サブ・タスクグラフは、N個の入力のうちの一つの入力に関して機械学習モデルをトレーニングするための単一入力トレーニング・タスクグラフを含んでいてもよい。これらおよび他の実施形態では、サブ・タスクグラフは、入力および該入力のためのラベルを含む二つの入力ノードを含んでいてもよい。サブ・タスクグラフはまた、機械学習モデルのパラメータのためのM個のモデル・リーフ・ノード、入力に基づく機械学習モデルのパラメータ重みのためのM個の出力リーフ・ノード、およびパラメータ重みを決定するための動作のための2M＋1個のタスク非リーフ・ノードを含んでいてもよい。非リーフ・ノードのそれぞれは、サブ・タスクグラフ内のあるタスクを表わすことができる。
【００６８】
これらおよび他の実施形態において、タスクグラフは、サブ・タスクグラフのN個のコピーを含み、各サブ・タスクグラフからのパラメータ重みの平均を実行するための諸ノードが続く。結果として、タスクグラフは、2N個の入力リーフ・ノード、M個のモデル・リーフ・ノード、サブ・タスクグラフのN個のコピーのそれぞれからのパラメータ重みの平均であるM個の出力リード・ノード、およびN(2M＋1)個のタスク非リーフ・ノードを含んでいてもよい。非リーフ・ノードのそれぞれは、タスクグラフにおけるあるタスクを表わすことができる。
【００６９】
ブロック406では、資源グラフが得られてもよい。資源グラフは、タスクグラフに含まれる動作を実行するために使用されうる資源を示してもよい。資源グラフは、タスクグラフ内の動作を実行するときの資源についての処理時間およびメモリ使用量ならびに装置間でタスクの出力を通信するための時間といった追加的な情報を含んでいてもよい。
【００７０】
ブロック408では、カウンタiが1に設定されてもよい。これらおよび他の実施形態において、カウンタiは別の整数に設定されてもよい。たとえば、カウンタiは、5、10、20、30、または何らかの他の数に設定されてもよい。いくつかの実施形態では、数は、タスクグラフのサイズに関する諸因子に基づいて選択されてもよい。
【００７１】
ブロック410では、含まれる繰り返しサブ・タスクグラフの数がiに等しいことに基づいて、資源グラフを使用して、繰り返しサブ・タスクグラフを処理するためのサブスケジュールについて、最小処理時間が決定されてもよい。いくつかの実施形態では、サブスケジュールは、i個の繰り返しサブ・タスクグラフの動作をパイプライン式に実行する、資源グラフからの諸資源のスケジュールを含んでいてもよい。最小処理時間は、i個の繰り返しサブ・タスクグラフの各動作の並列処理に基づいていてもよい。たとえば、サブ・タスクグラフが機械学習モデルをトレーニングするための単一入力トレーニング・タスクグラフを表わすとする。結果として、i個のサブ・タスクグラフについて、最小処理時間が決定されうる。i個のサブ・タスクグラフは、2i個の入力リーフ・ノード、M個のモデル・リーフ・ノード、M個の出力リーフ・ノード、およびi(2M＋1)個の非リーフ・ノードを含んでいてもよい。よって、i個のサブ・タスクグラフは、i(2M＋1)個のタスクを含んでいてもよい。
【００７２】
最小処理時間は、i個のサブ・タスクグラフのこれらのタスクを並列に実行するための推定値であってもよい。たとえば、i(2M＋1)個のタスクのそれぞれについての最小の個別の処理時間は、その処理が資源グラフの中の資源のうちの一つによって個別に実行されるときに決定されうる。各タスクについての最小の個別の処理時間が合計され、タスクの数i(2M＋1)で割ることができる。なお、最小の個別の処理時間が、i個のサブ・タスクグラフについての最小処理時間の推定値であってもよい。
【００７３】
ブロック412では、繰り返しサブ・タスクグラフの数がiに等しいことに基づいて、資源グラフを使用して、繰り返しサブ・タスクグラフを処理するための前記サブスケジュールについて、処理時間が決定されてもよい。処理時間は、i個の繰り返しサブ・タスクグラフについての処理時間を短縮および／または最小化するサブスケジュールを求めての発見的探索に基づいて決定されてもよく、該発見的探索はタスクグラフおよび資源グラフに関連付けられた制約条件を考慮に入れてもよい。
【００７４】
たとえば、サブ・タスクグラフが機械学習モデルをトレーニングするための単一入力トレーニング・タスクグラフを表わすとする。結果として、i個のサブ・タスクグラフについて、処理時間が決定されうる。i個のサブ・タスクグラフは、2i個の入力リーフ・ノード、M個のモデル・リーフ・ノード、M個の出力リーフ・ノード、およびi(2M＋1)個の非リーフ・ノードを含んでいてもよい。よって、i個のサブ・タスクグラフは、i(2M＋1)個のタスクを含んでいてもよい。
【００７５】
決定された処理時間は、資源グラフ内の資源がi個のサブ・タスクグラフを処理するための最小のまたは短縮された処理時間であってもよい。これらおよび他の実施形態において、処理時間は、上述したようなi個のサブ・タスクグラフにおけるi(2M＋1)個のタスクの一つ一つを資源グラフ内の装置にマッピングすることによって決定されてもよく、各タスクについての開始時間を含んでもよい。資源グラフは、毎時間ステップにおいて、装置上で実行されているすべてのタスクについての合計メモリが、装置の合計メモリよりも少なく、かつ、i個のサブ・タスクグラフにおけるi(2M＋1)個のタスクを実行するための処理時間を短縮または最小化することを目標として、タスクのためのすべての入力が、装置が該タスクを実行し始めるときに、装置において利用可能であるという制約条件に基づいて構成されてもよい。
【００７６】
ブロック414では、前記最小処理時間と前記処理時間との差異が閾値を満たすかどうかが判定されてもよい。差異が閾値を満たさない場合、方法400はブロック416に進んでもよい。差異が閾値を満たす場合、方法400はブロック418に進んでもよい。たとえば、処理時間と最小処理時間との間の差異は、処理時間と最小処理時間との間の比を決定することを含んでいてもよい。比が0.8ないし1.2の範囲内であることに応答して、その差は閾値を満たすことができる。
【００７７】
ブロック416では、iのカウントが、1ずつ増加されるなど、調整されてもよい。いくつかの実施形態では、カウントは、たとえば2、3、5、10、または20など、1より大きい整数だけ増されてもよい。代替的または追加的に、カウントはある整数だけ減じられてもよい。カウントが増やされるか減らされるかは、iの現在の値およびiのカウントに対する一つまたは複数の以前の変化の値に依存してもよい。ブロック416には、ブロック410および412が続いてもよい。ブロック410、412、414、および416は、最小処理時間と処理時間との差異が閾値を満たすまで反復されてもよい。
【００７８】
ブロック418では、サブスケジュールは、タスクグラフの動作を実行するためのスケジュールを決定するために複製されてもよい。いくつかの実施形態では、サブスケジュールは、繰り返しサブ・タスクグラフの大半についての動作をスケジュールするために、前記スケジュールにおいて前記サブスケジュールを逐次的に適用することによって複製されてもよい。たとえば、タスクグラフが、N個の入力に関して機械学習モデルをトレーニングするための複数入力トレーニング・タスクグラフを含んでいてもよいとする。サブスケジュールは、タスクグラフのi個のサブ・タスクグラフを処理するための資源グラフの資源のスケジュールを表わしうる。これらおよび他の実施形態において、サブスケジュールは、N/i回実行されてもよく、各サブスケジュールは、サブ・タスクグラフのN/i個のグループのうちの異なるものを処理しうる。ここで、サブ・タスクグラフの各グループはi個のサブ・タスクグラフを含む。いくつかの実施形態では、サブ・タスクグラフの各グループの処理がサブ・タスクグラフの直前のグループの処理の終了前に開始されるよう、サブ・タスクグラフの諸グループの処理がタイリングされうるように、サブ・タスクグラフの諸グループの諸サブスケジュールが構成されてもよい。
【００７９】
ブロック420では、タスクグラフの諸動作が、ブロック418で決定されたスケジュールに従って、資源グラフ内の資源を使って実行されてもよい。
【００８０】
本開示の範囲から逸脱することなく、方法400に修正、追加、または省略を行なってもよい。たとえば、方法400の動作は、異なる順序で実施されてもよい。追加的または代替的に、二つ以上の動作が同時に実行されてもよい。さらに、概説された動作およびアクションは、例として与えられているだけであって、動作およびアクションのいくつかは任意的であってもよく、より少数の動作およびアクションに結合されてもよく、または開示された実施形態の本質を損なうことなく、追加的な動作およびアクションに展開されてもよい。たとえば、方法400は、サブスケジュール間のよりよいタイリングを提供するために資源グラフを調整することをさらに含んでいてもよい。
【００８１】
図５は、本開示に記載される少なくとも一つの実施形態による、タスクグラフ動作をスケジューリングする別の例示的方法500のフローチャートである。方法500は、任意の適切なシステム、装置、またはデバイスによって実行されうる。たとえば、方法500の一つまたは複数の動作は、図１の環境100の一つまたは複数の要素、図３のコンピューティング・システム302、または図３のコンピューティング・システム302の複数によって実行されてもよい。離散的なブロックで示されているが、方法500のブロックの一つまたは複数に関連するステップおよび動作は、特定の実装に依存して、追加的なブロックに分割されてもよく、より少数のブロックに結合されてもよく、または除去されてもよい。
【００８２】
方法500は、ブロック502で開始されてもよく、ここで、複数の入力に基づいて機械学習モデルを生成するための動作を表わすタスクグラフが得られてもよい。いくつかの実施形態では、タスクグラフは、複数のサブ・タスクグラフを含んでいてもよく、各サブ・タスクグラフは、前記複数の入力のうちの異なるものに対応する。
【００８３】
ブロック504では、前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を実行するための、前記動作の前記部分集合の並列実行に基づく第一の計算時間が得られてもよい。いくつかの実施形態では、前記複数の集合の各集合は、前記複数のサブ・タスクグラフの同数を含んでいてもよい。代替的または追加的に、前記複数のサブ・タスクグラフのそれぞれは、前記動作の前記部分集合の同じ構成を含んでいてもよい。
【００８４】
ブロック506では、複数の資源の資源スケジュールに従って複数の資源を使って前記動作の前記部分集合を実行するための第二の計算時間が得られてもよい。ブロック508では、第一の計算時間と第二の計算時間との間の差異が決定されてもよい。
【００８５】
ブロック510では、差異が閾値を満たすことに応答して、前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することによって、前記複数の資源を使って、機械学習モデルが生成されてもよい。
【００８６】
ブロック512では、前記機械学習モデルが未分類の入力に適用されて、前記複数の入力の分類に関して、該未分類の入力を分類することができる。いくつかの実施形態では、前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のそれぞれについての前記動作の前記部分集合を逐次的に実行することを含んでいてもよい。これらおよび他の実施形態において、前記複数の集合のそれぞれは、前記複数のサブ・タスクグラフの異なる部分を含んでいてもよい。これらおよび他の実施形態において、前記動作の前記部分集合のそれぞれの逐次的な実行は、前記複数の資源の前記資源スケジュールに従って実行されてもよい。
【００８７】
いくつかの実施形態では、前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まってもよい。ここで、前記第二の集合についての前記動作の前記部分集合の実行は、前記第一の集合についての前記動作の前記部分集合の実行の直後にくる。代替的または追加的に、前記複数の資源の前記資源スケジュールは、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に、前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の実行が始まることを許容するように構成されてもよい。
【００８８】
本開示の範囲から逸脱することなく、方法500に修正、追加、または省略を行なってもよい。たとえば、方法500の動作は、異なる順序で実施されてもよい。追加的または代替的に、二つ以上の動作が同時に実行されてもよい。さらに、概説された動作およびアクションは例として与えられているだけであり、開示された実施形態の本質を損なうことなく、動作およびアクションのいくつかは任意的であってもよく、より少数の動作およびアクションに結合されてもよく、または追加的な動作およびアクションに展開されてもよい。
【００８９】
たとえば、方法500は、前記複数の資源の物理的な構成を表わす資源グラフを取得するステップをさらに含んでいてもよい。いくつかの実施形態では、前記複数の資源の前記資源スケジュールは、該資源グラフに基づいていてもよい。
【００９０】
図６は、本開示に記載される少なくとも一つの実施形態による、タスクグラフ動作をスケジューリングする別の例の方法600のフローチャートである。方法600は、任意の好適なシステム、装置、またはデバイスによって実行されうる。たとえば、方法600の一つまたは複数の動作は、図１の環境100の一つまたは複数の要素によって、図３のコンピューティング・システム302によって、または図３のコンピューティング・システム302の複数によって実行されてもよい。離散的なブロックで示されているが、方法600のブロックの一つまたは複数に関連するステップおよび動作は、特定の実装に依存して、追加的なブロックに分割されてもよく、より少数のブロックに結合されてもよく、または除去されてもよい。
【００９１】
方法600は、ブロック602で始まってもよく、ここで、タスクのための諸動作を表わすタスクグラフが得られてもよい。いくつかの実施形態では、タスクグラフは、複数のサブ・タスクグラフを含んでいてもよい。いくつかの実施形態では、前記複数の集合の各集合は、前記複数サブ・タスクグラフの同数を含んでいてもよい。いくつかの実施形態では、前記複数のサブ・タスクグラフのそれぞれは、前記動作の前記部分集合の同じ構成を含んでいてもよい。
【００９２】
ブロック604では、前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を実行するための、前記動作の前記部分集合の並列実行に基づく第一の計算時間が得られてもよい。
【００９３】
ブロック606では、複数の資源の資源スケジュールに従って複数の資源を使用して前記動作の前記部分集合を実行するための第二の計算時間が得られてもよい。ブロック608では、第一の計算時間と第二の計算時間との間の差異が決定されてもよい。
【００９４】
ブロック610では、差異が閾値を満足することに応答して、タスクグラフの動作は、前記複数の資源の前記資源スケジュールに基づいて、前記複数の資源を使用して実行されてもよい。いくつかの実施形態では、前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの動作を実行することは、複数の集合のそれぞれについて前記動作の前記部分集合を逐次的に実行することを含んでいてもよい。これらおよび他の実施形態において、前記複数の集合のそれぞれは、前記複数のサブ・タスクグラフの異なる部分を含んでいてもよく、前記動作の前記部分集合のそれぞれの逐次的な実行は、前記複数の資源の前記資源スケジュールに従って実行されてもよい。これらおよび他の実施形態において、前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に開始されてもよい。これらおよび他の実施形態において、第二の集合についての前記動作の前記部分集合の実行は、第一の集合についての前記動作の前記部分集合の実行の直後に来てもよい。これらおよび他の実施形態において、前記複数の資源の前記資源スケジュールは、前記複数の集合のうちの第一の集合のための前記動作の前記部分集合の実行が終了する前に、前記複数の集合のうちの第二の集合のための前記動作の前記部分集合の実行が始まることを許容するよう構成されてもよい。
【００９５】
いくつかの実施形態では、タスクは、複数の入力に基づいて機械学習モデルを生成することを含んでいてもよい。これらおよび他の実施形態において、前記複数のサブ・タスクグラフのそれぞれは、前記複数の入力のうちの一つに対応してもよく、前記動作を実行する結果、機械学習モデルが生成されうる。
【００９６】
本開示の範囲から逸脱することなく、方法600に修正、追加、または省略を行なうことができる。たとえば、方法600の動作は、異なる順序で実施されてもよい。追加的または代替的に、二つ以上の動作が同時に実行されてもよい。さらに、概説された動作およびアクションは、例として与えられているだけであり、開示された実施形態の本質を損なうことなく、動作およびアクションのいくつかは任意的であってもよく、より少数の動作およびアクションに結合されてもよく、または追加的な動作およびアクションに展開されてもよい。たとえば、方法600は、前記複数の資源の物理的な構成を表わす資源グラフを取得するステップをさらに含んでいてもよい。これらおよび他の実施形態において、前記複数の資源の前記資源スケジュールは、前記資源グラフに基づいていてもよい。
【００９７】
上述のように、本開示に記載される実施形態は、下記でより詳細に議論されるように、さまざまなコンピュータ・ハードウェアまたはソフトウェア・モジュールを含む、特殊目的または汎用コンピュータ（たとえば、図３のプロセッサ350）の使用を含んでいてもよい。さらに、上述のように、本開示に記載される実施形態は、コンピュータ実行可能な命令またはデータ構造を担持または記憶するためのコンピュータ読取可能な媒体（たとえば、図３のメモリ352またはデータ記憶装置354）を使用して実装されてもよい。
【００９８】
本開示において使用されるところでは、用語「モジュール」または「コンポーネント」は、該モジュールまたはコンポーネントのアクションを実行するように構成された特定のハードウェア実装、および／または、コンピューティング・システムの汎用ハードウェア（たとえば、コンピュータ読み取り可能媒体、処理装置など）に記憶および／または実行されうるソフトウェア・オブジェクトもしくはソフトウェア・ルーチンを指すことができる。いくつかの実施形態では、本開示に記載される異なるコンポーネント、モジュール、エンジン、およびサービスは、コンピューティング・システム上で実行されるオブジェクトまたはプロセスとして（たとえば、別個のスレッドとして）実装されてもよい。本開示に記載されるシステムおよび方法のいくつかは、一般に、（汎用ハードウェアに記憶および／または実行される）ソフトウェアで実装されるものとして記載されるが、個別的なハードウェア実装またはソフトウェアと個別的なハードウェア実装との組み合わせも可能であり、考えられている。本稿において、「コンピューティング・エンティティ」は、本開示において前に定義された任意のコンピューティング・システム、またはコンピューティング・システム上で動作する任意のモジュールまたは小モジュールの組み合わせであってもよい。
【００９９】
本開示において、特に添付の特許請求の範囲（たとえば、添付の特許請求の範囲の本文）において使用される用語は、一般に「開放的」な用語として意図されている（たとえば、「含む」という用語は、「含むが、これに限定されない」と解釈されるべきであり、「有する」という用語は、「少なくとも…を有する」と解釈されるべきであり、「包含する」という用語は、「包含するが、これに限定されない」などと解釈されるべきである)。
【０１００】
さらに、特定の数の導入されたクレーム記載が意図されている場合、そのような意図はクレームに明示的に記載され、そのような記載がない場合、そのような意図は存在しない。たとえば、理解を助けるために、以下の添付の特許請求の範囲は、クレーム記載を導入するために、「少なくとも一つの」および「一つまたは複数の」という導入句の使用を含むことがある。しかし、そのような句の使用は、不定冠詞「a」または「an」による請求項記載の導入が、そのように導入されたクレーム記載を含むいずれかの特定のクレームを、そのような記載を一つだけ含む実施形態に限定することを含意するものと解釈すべきではない。これは、たとえ同じクレームが導入句「一つまたは複数の」または「少なくとも一つの」および「a」または「an」のような不定冠詞を含むときであっても同じである（たとえば、「a」および／または「an」は、「少なくとも一つの」または「一つまたは複数の」を意味すると解釈されるべきである）。同じことは、クレーム記載を導入するために使われる定冠詞の使用についても当てはまる。
【０１０１】
さらに、たとえ導入されたクレーム記載の特定の数が明示的に記載されている場合であっても、当業者は、そのような記載は少なくともその記載された数を意味するものと解釈されるべきであることを認識するであろう（たとえば、他の修飾語を伴わない「二つの記載」というだけの記載は、少なくとも二つの記載または二つ以上の記載を意味する）。さらに、「A、B、C等の少なくとも一つ」または「A、B、C等の一つまたは複数」と類似の慣用表現が用いられる場合、一般に、そのような構文は、Aだけ、Bだけ、Cだけ、AとBが一緒、AとCが一緒、BとCが一緒、またはA、B、Cが一緒等を含むことが意図される。さらに、用語「および／または」の使用は、このように解釈されることが意図されている。
【０１０２】
さらに、明細書、特許請求の範囲、または図面のいずれかに記載されているかを問わず、二つ以上の代替的な用語を提示する任意の離接的な語句は、それらの用語の一方、それらの用語のいずれか、または両方の用語を含む可能性を考えていると理解されるべきである。たとえば、句「AまたはB」は、たとえ他所では用語「および／または」が使われていたとしても、「A」または「B」または「AおよびB」の可能性を含むと理解されるべきである。
【０１０３】
本開示に記載されたすべての例および条件付き言辞は、本開示および発明者によって当該技術の進歩に寄与される概念を理解する際に読者を助けるための教育目的のために意図されており、そのように具体的に記載された例および条件に限定することなく解釈されるべきである。本開示の実施形態を詳細に記述してきたが、本開示の精神および範囲から逸脱することなく、それにさまざまな変更、置換、および代替を行なうことができる。
【０１０４】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
複数の入力に基づいて機械学習モデルを生成するための動作を表わすタスクグラフを取得する段階であって、前記タスクグラフは複数のサブ・タスクグラフを含み、各サブ・タスクグラフは、前記複数の入力のうちの異なるものに対応する、段階と；
前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を、前記動作の前記部分集合の並列実行に基づいて実行するための第一の計算時間を取得する段階と；
複数の資源を該複数の資源の資源スケジュールに従って使って前記動作の前記部分集合を実行するための第二の計算時間を取得する段階と；
前記第一の計算時間と第二の計算時間との間の差異を決定する段階と；
前記差異が閾値を満たすことに応答して、前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することによって、前記複数の資源を使って前記機械学習モデルを生成する段階と；
前記機械学習モデルを未分類の入力に適用して、該未分類の入力を前記複数の入力の分類に関して分類する段階とを含む、
方法。
（付記２）
前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のうちの各集合について前記動作の前記部分集合を逐次的に実行することを含み、前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフの異なる部分を含み、前記動作の前記部分集合のそれぞれの逐次的実行は、前記複数の資源の前記資源スケジュールに従って実行される、付記１記載の方法。
（付記３）
前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフのうちの同数を含む、付記２記載の方法。
（付記４）
前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の前記実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まり、前記第二の集合についての前記動作の前記部分集合の前記実行は、前記第一の集合についての前記動作の前記部分集合の前記実行のすぐ後に続く、付記２記載の方法。
（付記５）
前記複数の資源の前記資源スケジュールは、前記複数の集合のうちの前記第二の集合についての前記動作の前記部分集合の前記実行が、前記複数の集合のうちの前記第一の集合についての前記動作の前記部分集合の実行が終わる前に始まることを許容するよう構成される、付記４記載の方法。
（付記６）
前記複数のサブ・タスクグラフのそれぞれが、前記動作の前記部分集合の同じ構成を含む、付記１記載の方法。
（付記７）
前記複数の資源の物理的構成を表わす資源グラフを取得する段階をさらに含み、前記複数の資源の前記資源スケジュールは前記資源グラフに基づく、付記１記載の方法。
（付記８）
システムによって実行されると該システムに付記１記載の方法を実行させるまたは実行するよう指令する命令を記憶するよう構成された一つまたは複数のコンピュータ可読媒体。
（付記９）
タスクのための動作を表わすタスクグラフを取得する段階であって、前記タスクグラフは複数のサブ・タスクグラフを含む、段階と；
前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を、前記動作の前記部分集合の並列実行に基づいて実行するための第一の計算時間を取得する段階と；
複数の資源を該複数の資源の資源スケジュールに従って使って、前記動作の前記部分集合を実行するための第二の計算時間を取得する段階と；
前記第一の計算時間と前記第二の計算時間との間の差異を決定する段階と；
前記差異が閾値を満足することに応答して、前記複数の資源の前記資源スケジュールに基づいて前記複数の資源を使って、前記タスクグラフの前記動作を実行する段階とを含む、
方法。
（付記１０）
前記タスクは、複数の入力に基づいて機械学習モデルを生成することを含み、前記複数のサブ・タスクグラフのそれぞれが前記複数の入力のうちの一つに対応し、前記動作を実行することは前記機械学習モデルを生成することにつながる、付記９記載の方法。
（付記１１）
前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のうちの各集合について前記動作の前記部分集合を逐次的に実行することを含み、前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフの異なる部分を含み、前記動作の前記部分集合のそれぞれの逐次的実行は、前記複数の資源の前記資源スケジュールに従って実行される、付記９記載の方法。
（付記１２）
前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフのうちの同数を含む、付記１１記載の方法。
（付記１３）
前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の前記実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まり、前記第二の集合についての前記動作の前記部分集合の前記実行は、前記第一の集合についての前記動作の前記部分集合の前記実行のすぐ後に続く、付記１１記載の方法。
（付記１４）
前記複数の資源の前記資源スケジュールは、前記複数の集合のうちの前記第二の集合についての前記動作の前記部分集合の前記実行が、前記複数の集合のうちの前記第一の集合についての前記動作の前記部分集合の実行が終わる前に始まることを許容するよう構成される、付記１３記載の方法。
（付記１５）
前記複数のサブ・タスクグラフのそれぞれが、前記動作の前記部分集合の同じ構成を含む、付記９記載の方法。
（付記１６）
前記複数の資源の物理的構成を表わす資源グラフを取得する段階をさらに含み、前記複数の資源の前記資源スケジュールは前記資源グラフに基づく、付記９記載の方法。
（付記１７）
命令を記憶するよう構成された一つまたは複数のコンピュータ可読媒体と；
前記一つまたは複数のコンピュータ可読媒体に結合された一つまたは複数のプロセッサとを有するシステムであって、前記一つまたは複数のプロセッサは前記命令を実行して前記システムに手順を実行させるよう構成され、前記手順は：
タスクのための動作を表わすタスクグラフを取得する段階であって、前記タスクグラフは複数のサブ・タスクグラフを含む、段階と；
前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を、前記動作の前記部分集合の並列実行に基づいて実行するための第一の計算時間を取得する段階と；
複数の資源を該複数の資源の資源スケジュールに従って使って、前記動作の前記部分集合を実行するための第二の計算時間を取得する段階と；
前記第一の計算時間と前記第二の計算時間との間の差異を決定する段階と；
前記差異が閾値を満足することに応答して、前記複数の資源の前記資源スケジュールに基づいて前記複数の資源を使って、前記タスクグラフの前記動作を実行する段階とを含む、
システム。
（付記１８）
前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することは、複数の集合のうちの各集合について前記動作の前記部分集合を逐次的に実行することを含み、前記複数の集合のうちの各集合は、前記複数のサブ・タスクグラフの異なる部分を含み、前記動作の前記部分集合のそれぞれの逐次的実行は、前記複数の資源の前記資源スケジュールに従って実行される、付記１７記載のシステム。
（付記１９）
前記複数の集合のうちの第二の集合についての前記動作の前記部分集合の前記実行は、前記複数の集合のうちの第一の集合についての前記動作の前記部分集合の実行が終わる前に始まり、前記第二の集合についての前記動作の前記部分集合の前記実行は、前記第一の集合についての前記動作の前記部分集合の前記実行のすぐ後に続く、付記１８記載のシステム。
（付記２０）
前記複数のサブ・タスクグラフのそれぞれが、諸タスクの同じ構成を含む、付記１７記載のシステム。
【符号の説明】
【０１０５】
１１０  タスクグラフ
１１２  資源グラフ
１１４  入力データ
１２０  スケジューリング・モデル
１２２  スケジュール
１３０  実行環境
１３２  資源
１４０  出力
３０２  コンピューティング・システム
３５０  プロセッサ
３５２  メモリ
３５４  データ記憶
４０２  タスクグラフを取得
４０４  サブ・タスクグラフを識別
４０６  資源グラフを取得
４０８  i＝1と設定
４１０  最小処理時間を決定
４１２  処理時間を決定
４１４  時間の差異が閾値を満たすか？
４１８  サブスケジュールを複製してスケジュールを決定
４２０  スケジュールに基づいてタスクグラフの動作を実行
５０２  複数の入力に基づいて機械学習モデルを生成するための動作を表わすタスクグラフを取得。タスクグラフは複数のサブ・タスクグラフを含み、各サブ・タスクグラフは、前記複数の入力のうちの異なるものに対応
５０４  前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を実行するための、前記動作の前記部分集合の並列実行に基づく第一の計算時間を取得
５０６  複数の資源の資源スケジュールに従って複数の資源を使って前記動作の前記部分集合を実行するための第二の計算時間を取得
５０８  第一の計算時間と第二の計算時間との間の差異を決定
５１０  差異が閾値を満たすことに応答して、前記複数の資源の前記資源スケジュールに基づいて前記タスクグラフの前記動作を実行することによって、前記複数の資源を使って前記機械学習モデルを生成
５１２  前記機械学習モデルを未分類の入力に適用して、該未分類の入力を前記複数の入力の分類に関して分類
６０２  タスクのための諸動作を表わすタスクグラフを取得。タスクグラフは、複数のサブ・タスクグラフを含む
６０４  前記複数のサブ・タスクグラフのある集合に対応する前記動作の部分集合を実行するための、前記動作の前記部分集合の並列実行に基づく第一の計算時間を取得
６０６  複数の資源の資源スケジュールに従って複数の資源を使用して前記動作の前記部分集合を実行するための第二の計算時間を取得
６０８  第一の計算時間と第二の計算時間との間の差異を決定
６１０  差異が閾値を満足することに応答して、タスクグラフの動作を、前記複数の資源の前記資源スケジュールに基づいて、前記複数の資源を使用して実行
【図１】
2020091858.tif 000003
【図２Ａ】
2020091858.tif 000004
【図２Ｂ】
2020091858.tif 000005
【図３】
2020091858.tif 000006
【図４】
2020091858.tif 000007
【図５】
2020091858.tif 000008
【図６】
2020091858.tif 000009