(57)【特許請求の範囲】
【請求項１】
コンピュータシステムに方法を実行させるプログラムであって、前記方法は、
ユーザコードのランタイム非依存表現の実行のための前記コンピュータシステムにおける第１の実行ランタイムを、ランタイム非依存ライブラリによって選択することであって、前記第１の実行ランタイムは、前記ランタイム非依存表現の少なくとも１つのヒューリスティックに基づき選択される、選択することと、
スケジューラを、前記ランタイム非依存ライブラリによって呼び出して、前記第１の実行ランタイムを使用した前記コンピュータシステムでの実行のための前記ランタイム非依存表現中のタスクのセットをディスパッチすることと
を含むことを特徴とするプログラム。
【請求項２】
請求項１に記載のプログラムであって、前記方法は、前記ユーザコードを前記タスクのセットを含む前記ランタイム非依存表現に変換することをさらに含むことを特徴とするプログラム。
【請求項３】
請求項１または２に記載のプログラムであって、前記ユーザコードは、前記タスクのセットおよび前記タスクのセットの相互関係のセットを固有の方法で表すことを特徴とするプログラム。
【請求項４】
請求項１から３のうちの何れか一項に記載のプログラムであって、前記ユーザコードは、クエリー構文を使用して前記タスクのセットおよび前記タスクのセットの相互関係のセットを特定することを特徴とするプログラム。
【請求項５】
請求項１から４のうちの何れか一項に記載のプログラムであって、前記ランタイム非依存表現は、前記第１の実行ランタイムおよび前記第１の実行ランタイムとは異なる第２の実行ランタイムによって実行可能であることを特徴とするプログラム。
【請求項６】
請求項１から５のうちの何れか一項に記載のプログラムであって、前記ランタイム非依存表現は、データフローに関して前記タスクのセットを表すことを特徴するプログラム。
【請求項７】
請求項１から６のうちの何れか一項に記載のプログラムであって、前記ランタイム非依存表現は、ＤＡＧ（有向非巡回グラフ）を形成することを特徴とするプログラム。
【請求項８】
請求項１から７のうちの何れか一項に記載のプログラムであって、前記第１の実行ランタイムは、シングルマシン、マシンのクラスタおよびマシンのクラウドのうちの１つに対応することを特徴とするプログラム。
【請求項９】
請求項１から８のうちの何れか一項に記載のプログラムであって、前記コンピュータシステムは、シングルマシン、マシンのクラスタおよびマシンのクラウドのうちの１つを含むことを特徴とするプログラム。
【請求項１０】
請求項１から９のうちの何れか一項に記載のプログラムであって、前記スケジューラは、利用可能になるタスクに対応する入力データのセットに応じて前記タスクのセットにおけるタスクをディスパッチするように構成されていることを特徴とするプログラム。
【請求項１１】
コンピュータシステムに方法を実行させるためのプログラムであって、前記方法は、
ユーザコードにおける固有の方法で表現されるタスクのセットおよび前記タスクのセットの相互関係のセットを、ランタイム非依存ライブラリによって特定することと、
前記タスクのセットおよび前記相互関係のセットを前記ユーザコードのランタイム非依存表現に、前記ランタイム非依存ライブラリによって変換することと
を含むことを特徴するプログラム。
【請求項１２】
請求項１１に記載のプログラムであって、前記ランタイム非依存表現は、データフローに関して前記タスクのセットを表すことを特徴するプログラム。
【請求項１３】
請求項１１または１２に記載のプログラムであって、前記ランタイム非依存表現は、ＤＡＧ（有向非巡回グラフ）を形成することを特徴とするプログラム。
【請求項１４】
請求項１１から１３のうちの何れか一項に記載のプログラムであって、前記ランタイム非依存表現の実行のための前記コンピュータシステムにおける実行ランタイムは、シングルマシン、マシンのクラスタおよびマシンのクラウドのうちの１つに対応することを特徴とするプログラム。
【請求項１５】
請求項１１から１４のうちの何れか一項に記載のプログラムであって、前記コンピュータシステムは、シングルマシン、マシンのクラスタおよびマシンのクラウドのうちの１つを含むことを特徴とするプログラム。
【請求項１６】
少なくとも１つのコンピュータシステムによって実行される方法であって、前記方法は、
ユーザコードを、ランタイム非依存表現に、ランタイム非依存ライブラリによって変換することであって、前記ランタイム非依存表現は、データフローに関してタスクのセットを表すＤＡＧ（有向非巡回グラフ）を形成し、前記ユーザコードは前記タスクのセットおよび前記タスクのセットの相互関係のセットを固有の方法で表す、変換することと、
前記ランタイム非依存表現の実行のための前記コンピュータシステムにおける２つまたはそれより多い実行ランタイムのセットから第１の実行ランタイムを、前記ランタイム非依存ライブラリによって選択することであって、前記第１の実行ランタイムは、前記ランタイム非依存表現の少なくとも１つのヒューリスティックに基づき選択される、選択することと、
スケジューラを、前記ランタイム非依存ライブラリによって呼び出して、前記第１の実行ランタイムを使用した前記コンピュータシステムでの実行のための前記ランタイム非依存表現中のタスクのセットをディスパッチすることと
を含むことを特徴とする方法。
【請求項１７】
請求項１６に記載の方法であって、前記ランタイム非依存表現は、前記第１の実行ランタイムおよび前記２つまたはそれより多い実行ランタイムのセットにおける第２の実行ランタイムによって実行可能であり、前記第２の実行ランタイムは前記第１の実行ランタイムとは異なることを特徴とする方法。
【請求項１８】
請求項１６または１７に記載の方法であって、前記第１の実行ランタイムは、シングルマシン、マシンのクラスタおよびマシンのクラウドのうちの１つに対応することを特徴とする方法。
【請求項１９】
請求項１６から１８のうちの何れか一項に記載の方法であって、前記コンピュータシステムは、シングルマシン、マシンのクラスタおよびマシンのクラウドのうちの１つを含むことを特徴とする方法。
【請求項２０】
請求項１から１０のうちの何れか一項に記載のプログラムであって、前記ランタイム非依存表現は、前記ユーザコードの固有の並列性を表し、前記第１の実行ランタイムは、前記第１の実行ランタイムに対して利用可能な前記コンピュータシステムの計算リソースにも基づき選択されることを特徴とするプログラム。
【請求項２１】
請求項１１から１５のうちの何れか一項に記載のプログラムであって、前記ランタイム非依存表現は、前記ユーザコードの固有の並列性を表し、前記方法は、更に、
前記ランタイム非依存表現の実行のための前記コンピュータシステムにおける第１の実行ランタイムを、前記ランタイム非依存ライブラリによって、ランタイムに、前記第１の実行ランタイムに対して利用可能な前記コンピュータシステムの計算リソースに基づき選択すること
を含むことを特徴とするプログラム。
【請求項２２】
請求項１６から１９のうちの何れか一項に記載の方法であって、前記ランタイム非依存表現は  前記ユーザコードの固有の並列性を表し、前記第１の実行ランタイムは、前記第１の実行ランタイムに対して利用可能な前記コンピュータシステムの計算リソースにも基づき選択されることを特徴とする方法。
【請求項２３】
請求項１から１５、２０及び２１のうちの何れか一項に記載のプログラムを記憶したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、選択された実行ランタイムによる実行のためのユーザコードのランタイム非依存表現に関する。
【背景技術】
【０００２】
コンピュータシステムは、しばしば同じプログラムの異なる部分を同時に（すなわち、並列に）実行する能力を有する。プログラマは、一般にプログラム内での同時実行を表して、特定の部分の同時の実行を可能にする。しかしながら、プログラムでの同時実行の表現は、普通、プログラムを実行するために使用される実行環境と密接に結びつけられる。プログラムのための実行環境は、例えば、コンピュータシステムの種類、プログラムのプログラミング言語、およびコンピュータシステムにおけるランタイム・ライブラリ（単数または複数）を含みうる。この結びつきの結果、ある実行環境のために記述されたプログラムは、別の実行環境では実行可能ではないかもしれない。
【０００３】
たとえ、プログラムが異なる実行環境において実行可能であったとしても、プログラムはいずれかの実行環境において利用可能な計算リソースを十分に活用することができないかもしれない。例えば、シングルマシンのために記述されたプログラムは、マシンのクラスタまたはクラウドで実行することができないかもしれない。たとえ、プログラムが修正されて、クラスタまたはクラウドで実行したとしても、プログラムは動的に（例えば、新しいマシンをクラスタまたはクラウドに加えることによってなど）利用可能にされるリソースを使用することができないかもしれない。
【発明の概要】
【０００４】
この要約が提供されて、以下の詳細な説明においてさらに記載される概念の抜粋を簡易化した形式にて紹介される。この要約は、特許を請求する事項の重要な特徴または本質的特徴を特定することを意図しないし、特許を請求する事項の範囲を限定するために使用されることも意図しない。
【０００５】
コンピュータシステムにおける実行環境は、ユーザコードが、複数の実行ランタイムを使用して実行されることを可能にする。実行環境は、ユーザコードをランタイム非依存表現へ変換し、ランタイム非依存表現を実行するための実行ランタイムを選択し、および、選択された実行ランタイムのためのスケジューラを呼び出す。スケジューラは、選択された実行ランタイムにおいて同時実行のメカニズムを使用するコンピュータシステムによる実行のためのランタイム非依存表現内のタスクをディスパッチする。
【図面の簡単な説明】
【０００６】
添付の図面は、さらに実施形態の理解が提供されるために含まれて、およびこの明細書に組み込まれおよびこの明細書の一部を構成する。図面は、実施形態を図示し、および明細書と共に実施形態の原理を説明するのに役立つ。他の実施形態および実施形態の意図する有利な点の多くは、以下の詳細な説明を参照することによってより理解されるようになると、直ちに認められるだろう。図面の要素は、必ずしも互いに関連した縮尺ではない。同様の参照の数字は、対応する同様の部分を指定する。
【図１】図１は、コンピュータシステムにおける実行環境の実施形態を図示するブロック図である。
【図２】図２は、ランタイムに依存しない中間の表現を生成する実施形態を図示するブロック図である。
【図３】図３は、ランタイムに依存しない中間の表現を使用してユーザコードを実行する実施形態を図示するブロック図である。
【図４Ａ】図１に示された実行環境を実装するよう構成されたコンピュータシステムの実施形態を図示するブロック図である。
【図４Ｂ】図１に示された実行環境を実装するよう構成されたコンピュータシステムの実施形態を図示するブロック図である。
【図４Ｃ】図１に示された実行環境を実装するよう構成されたコンピュータシステムの実施形態を図示するブロック図である。
【発明を実施するための形態】
【０００７】
以下の詳細な説明において、参照が添付図面に対してなされ、添付図面は詳細な説明の一部を形成し、および本発明が実行されるであろう特定の実施形態を図示する手段として示される。これに関して、「最上部」「底部」「前面」「裏面」「先頭」「末尾」などの方向の専門用語は、説明されている図面の方向に関して使用される。なぜなら、実施形態のコンポーネントは、複数の異なる方向にて位置づけられることが可能で、方向の専門用語は、例示のために使用され、および全く限定しない。他の実施形態が利用されうること、および構造上または論理上の変更が本発明の範囲から逸脱することなくなされうることが理解される。以下の詳細な説明は、それゆえ、限定した意味にとられず、および本発明の範囲は、添付の特許請求の範囲によって定義される。
【０００８】
ここで記載される様々な例示的な実施形態の特徴は、特に別に書き留められない限り、互いに組み合わせられうることが理解される。
【０００９】
図１は、コンピュータシステムにおける実行環境１０の実施形態を図示しているブロック図である。コンピュータシステムは、図４Ａで示されるコンピュータシステム１００（例えば、シングルマシン）、図４Ｂで示されるコンピュータシステム１５０（例えば、マシンのクラスタ）、または図４Ｃで示されるコンピュータシステム１６０（例えば、マシンのクラウド）などである。実行環境１０は、コンピュータシステムにおけるオペレーションのランタイムモードを表している。ここで、コンピュータシステムは、図４Ａにおいて示されおよび以下の追加の詳細において記載されるプロセッシングコア１０３のようなコンピュータシステムの１つまたは複数のプロセッシングコア上にて、命令を実行する。実行環境１０は、２つまたはそれより多いタスク１４を伴う呼び出されたユーザコード１２、ランタイム非依存ライブラリ１６、ユーザコード１２のランタイム非依存表現（ＲＡＲ）１８、呼び出されたスケジューラ２０、および実行ランタイム２４（１）−２４（Ｍ）を含む。ここで、Ｍは２より大きいまたは２と等しい整数であり、Ｍ番目の実行ランタイム２４（Ｍ）を意味する。
【００１０】
実行環境１０は、ユーザコード１２が異なる実行ランタイム２４（１）―２４（Ｍ）を使用して実行させられることを可能にする、分散タスクプログラミングモデルを提供する。特に、実行環境１０は、動的にユーザコード１２を選択された実行ランタイム２４に結合して、ユーザコード１２の実行が実行環境１０のコンピュータシステム内でスケーリングされることを可能にする。実行環境１０は、ユーザコード１２によって定義されるタスク１４が、ランタイム非依存ライブラリ１６、ＲＡＲ１８、スケジューラ２０、および選択された実行ランタイム２４を使用して同時に実行されることを可能にする。
【００１１】
各実行ランタイム２４（１）−２４（Ｍ）は、典型的に、基礎となるコンピュータシステムに適しているプログラミング言語および／またはプログラミングモデルに対応している。例えば、ある実行ランタイム２４（例えば、ＣｏｎｃＲＴ（Microsoft Concurrency Runtime））は、マルチプロセッサコアを有するシングルマシンでユーザコード１２の並列実行を向上させるよう設計されうる（例えば、図４Ａにおいて示されるコンピュータシステム１００）。別の実行ランタイム２４（例えば、ＭＰＩ（Message Passing Interface）ランタイム）は、マシンのクラスタでユーザコード１２の並列実行を向上させるように設計されうる（例えば、図４Ｂにおいて示されるコンピュータシステム１５０）。さらに実行ランタイム２４は、マシンのクラウドでユーザコード１２の並列実行を向上させるように設計されうる（例えば、図４Ｃにおいて示されるコンピュータシステム１６０）。
【００１２】
ユーザコード１２は、１つまたは複数の並列アルゴリズムの直感的な表現を形成する一連の命令を含む。ユーザコード１２は、各アルゴリズム内のタスク１４およびタスク１４の相互関係を特定することによって、データフロー上の各アルゴリズムを基礎とする。ユーザコード１２は、任意の特定の実行ランタイム２４（１）−２４（Ｍ）のプログラミングの特徴または構文を明確に考慮せずに、タスク１４およびタスク１４の相互関係を表す。したがって、ユーザコード１２は、ＲＡＲ１８へ変換され、およびスケジューラ２０およびランタイム非依存ライブラリ１６によって選択される実行ランタイム２４（１）−２４（Ｍ）を使用して実行されることが可能である。ある実施形態において、ユーザコード１２は、ランタイム非依存ライブラリ１６中のＡＰＩ（Application Program Interface）を呼び出す命令を含んで、タスク１４の実行を開始する。他の実施形態において、ユーザコード１２は、他のプログラミング言語の構文および／またはこれに対応するランタイム非依存ライブラリ１６によって提供されるツールを使用して、動的に選択された実行ランタイム２４（１）−２４（Ｍ）を使用してタスク１４の実行を開始する。
【００１３】
各タスク１４は、コンピュータシステムによって実行されるときに、１つのワークを行なう一連の命令を含む。各タスク１４は、自己完結しており（すなわち、副次的影響がない）、入力データの定義されたセット上で動作して、出力データの定義されたセットを作り出す。あるタスク１４によって作り出された出力データのセットは、別のタスク１４のための入力データのセットの全てまたは一部として使用されうる。したがって、タスク１４は、１つまたは複数の他のタスク１４によって作り出された入力データを使用することができ、および１つまたは複数のタスク１４によって入力データとして使用されるであろう出力データを作り出すことができる。これらタスク１４は、しかしながら、データを共有（すなわち、データの同じセット上で同時に動作）しないように定義される。なぜなら、タスク１４の入力および出力データは、明確に定義され、タスク１４の相互関係は、ランタイム非依存ライブラリ１６によって決定されうる。タスク１４は、タスク１４のための入力データのセットが利用可能になったときに、コンピュータシステムのプロセッシングコアによって、各タスク１４がスケジューラ２０によって同時実行のためにアクティブにされおよびディスパッチされうるようにコード化される。
【００１４】
ある実施形態において、ユーザコード１２は、ネイティブ（すなわちアンマネージド）のＣ＋＋のようなプログラミング言語にて書かれる。この実施形態において、各タスク１４は、シーケンスのセットまたは他の適した命令を含むＣ＋＋ラムダ式のための抽象化としてコード化されうる。他の実施形態において、ユーザコード１２は、ＲＡＲ１８に変換可能で選択された実行ランタイム２４（１）−２４（Ｍ）によって実行可能である他の適したネイティブのプログラミング言語にて書かれうる。同様に、各タスク１４は、他の適したプログラミング言語の構文を使用してコード化されうる。
【００１５】
ユーザコード１２は、任意の適したコンピュータシステムの実行モデルに基づく１つまたは複数のコンピュータシステムにおいて動作するように構成されうる。コンピュータシステムの実行モデルは、スタックモデルまたはインタープリタモデルなどであり、および任意の適したコードの種類（アプリケーション、ライブラリ関数、またはオペレーティングシステムサービスなど）を表すことができる。ユーザコード１２は、定義されたメモリアドレス空間を含むコンピュータシステムの割り当てられたリソースのセットに関連するプログラム状態およびマシン状態を有する。ユーザコード１２は、実行環境１０においていずれかの共存するプロセスから自立的にまたは実質上自立的に実行する。したがって、ユーザコード１２は、共存するプロセスのプログラム状態または共存するプロセスに対して割り当てられる任意のリソースのマシン状態を影響を与えるように変更しない。同様に、共存するプロセスは、ユーザコード１２のプログラム状態またはユーザコード１２に対して割り当てられる任意のリソースのマシン状態を影響を与えるように変更しない。
【００１６】
タスク１４の実行を開始するユーザコード１２に応答して、ランタイム非依存ライブラリ１６は、ユーザコード１２をＲＡＲ１８へ変換し、ＲＡＲ１８の実行のための実行ランタイム２４を選択し、および選択された実行ランタイム２４のためのスケジューラ２０を呼び出す。上で述べたように、ユーザコード１２は、ランタイム非依存ライブラリ１６中のＡＰＩを呼び出す、または別の適したプログラミングの構文を使用してタスク１４の実行を開始することが可能である。
【００１７】
ランタイム非依存ライブラリ１６は、ユーザプログラム１２における固有の並列性に基づいてユーザコード１２におけるタスク１４およびタスク１４の相互関係を特定する。ランタイム非依存ライブラリ１６は、ＲＡＲ１８がユーザコード１２の固有の並列性を具象化しおよび実行ランタイム２４（１）−２４（Ｍ）のいずれかによって実行されうるように、ユーザコード１２をＲＡＲ１８へ変換する。ＲＡＲ１８は、実行ランタイム２４（１）−２４（Ｍ）のいずれかのスケジューラ２０に移植しうるタスク１４の抽象化を含む。ある実施形態において、ランタイム非依存ライブラリ１６は、ユーザコード１２におけるタスク１４間のシーケンスを特定してユーザコード１２におけるデータのフローを表すＤＡＧ（Directed Acyclic Graph）を形成することによって、ＲＡＲ１８を生成する。ＤＡＧのゆえに、ランタイム非依存ライブラリ１６は、タスク１４を表しおよびタスク間のデータのフローにしたがってノード間の関係（すなわち、相互関係）を表すノードを形成する。他の実施形態において、ランタイム非依存ライブラリ１６は、他の適したデータ構成を使用してＲＡＲ１８を生成して、ユーザプログラム１２における固有の並列性を表す。
【００１８】
ＲＡＲ１８の作成とともに、ランタイム非依存ライブラリ１６は、ユーザコード１２の実行のための実行ランタイム２４（１）−２４（Ｍ）を、基礎となるコンピュータシステムおよびＲＡＲ１８に対応するヒューリスティックに基づいて選択する。特に、ランタイム非依存ライブラリ１６は、ユーザコード１２のタスク１４を最も効率よく実行できる実行ランタイム（１）―２４（Ｍ）を選択することによって、ユーザコード１２のための最適なスケーリングに達するように試みる。ランタイム非依存ライブラリ１６は、ユーザコード１２の特徴（例えば、データ集約型対コンピュータ集約型など）を考慮し、ユーザコード１２の実行のためのコンピューティングリソースの適切なレベル（例えば、シングルマシン、マシンのクラスタ、マシンのクラウドなど）を基礎となるコンピュータシステムを前提に決定する。決定をした後、ランタイム非依存ライブラリ１６は、選択された実行ランタイム２４のためのスケジューラ２０のインスタンスを作成する。
【００１９】
スケジューラ２０は、ユーザコード１２のタスク１４が、選択された実行ランタイム２４を使用して実行環境１０において実行されるようにする。スケジューラ２０は、選択された実行ランタイム２４においてＡＰＩを呼び出しまたは他の適したプログラミングの構文を使用することによって、実行のために、ＲＡＲ１８からタスクをキューに入れ、およびユーザコード１２からタスク１４をディスパッチする。スケジューラ２０は、タスク１４を、任意の適したスケジューリングアルゴリズムに従ってディスパッチする。スケジューラ２０は、タスク１４のための入力データのセットおよびコンピュータシステムの処理リソースが利用可能になったときに、実行のためのタスク１４をディスパッチすることによって、タスク１４の実行を管理する。上で記載したように、タスク１４のための入力データのセットは、１つまたは複数の他のタスク１４の完了のときに利用可能になりうる。
【００２０】
動的にユーザコード１２を選択された実行ランタイム２４と結合することによって、実行環境１０は、ユーザコード１２のためのプログラミングモデルを実行ランタイム２４（１）−２４（Ｍ）のセットに基づいて表現する。そうすることによって、同じユーザコード１２は、各実行ランタイム２４（１）−２４（Ｍ）のためのランタイム特有のコードを含むことのオーバーヘッドを負うことなく、異なる実行ランタイム２４（１）−２４（Ｍ）を対象とするために使用されうる。結果として、実行環境１０は、シングルマシンから多重のマシン（例えば、クラスタまたはクラウド）への自動のスケーリングを提供するユーザコード１２のためのプログラミングモデルをサポートする。
【００２１】
実行環境１０は、実行ランタイム２４（１）−２４（Ｍ）の特徴をサポートするリッチプログラミングモデルを提供することもできる。例えば、ＭＰＩなどのある実行ランタイム２４は、マシンのクラスタにおいてノード間を通過するデータがシリアルにされることを規定できるのに対して、ＣｏｎｃＲＴなどの別の実行ランタイム２４は、データが共有メモリマシン上のポインタを使用してアクセスされることを可能にしうる。リッチプログラミングモデルのゆえに、ユーザコード１２は、ＭＰＩなどのランタイム２４のためのユーザ定義型についての適切なシリアルなルーチンを含む。実行環境１０（すなわち、ランタイム非依存ライブラリ１６およびスケジューラ２０）は、しかしながら、シリアルなルーチンはユーザコード１２が共有メモリマシン上で実行されるときに呼び出されないことを確実にする。
【００２２】
実行環境１０は、さらに、デッドロック防止およびフォールト・トレランスをサポートするリッチプログラミングモデルを提供することができる。ＲＡＲ１８を生成することによって、実行環境１０は、循環を不可能にし、およびそれゆえデッドロックを除外および不経済な動的なデッドロック検出の方策の使用を避ける。加えて、タスク１４はコード化されて副次的影響がないので、タスク１４は、与えられたコンピューティングノードがタスク１４の実行中に失敗するときに他のコンピューティングノード上で再開されうる。
【００２３】
他の実施形態において、実行環境１０は、Ｃ＋＋などのネイティブの言語上の宣言型のプログラミングモデルを使用して実装される。この実施形態において、ユーザコード１２は、データフローに関してタスク１４を固有の方法で表すネイティブの言語におけるクエリー構文を伴って記述される。クエリー構文のゆえに、ユーザコード１２のタスク１４は、定義によって副次的影響がなく、明確に定義された相互関係を有する。結果として、ユーザコード１２の実行は、自動的にシングルマシンからクラスタまたはクラウドなどの分散環境へスケーリングされうる。
【００２４】
図２は、クエリー構文を伴うユーザコード１２の実施形態１２Ａを図示しているブロック図である。図２の例において、ユーザコード１２Ａは、ネイティブの言語のクエリーとしてｍａｐ−ｒｅｄｕｃｅを表す。そうすることによって、ユーザコード１２Ａは、ランタイム非依存ライブラリ１６にＲＡＲ１８の実施形態を生成させる。ＲＡＲ１８は、矢印３２によって示されるようにランタイム非依存ＤＡＧ１８Ａを形成する。ランタイム非依存ライブラリ１６は、タスク１４（１）−１４（４）（すなわち、それぞれ、読み出し、ＳｅｌｅｃｔＭａｎｙ（マッパー（mapper））、ＧｒｏｕｐＢｙ、およびＳｅｌｅｃｔＭａｎｙ（レデューサ（reducer）））をユーザコード１２Ａにおけるクエリーから認識し、およびタスク１４（１）―１４（４）の表現をＤＡＧ１８Ａへ変換する（図２の実施形態のフロー図におけるブロックで示されるように）。ランタイム非依存ライブラリ１６は、タスク１４（１）―１４（４）の相互関係を認識し、および相互関係の表現をＤＡＧ１８Ａへ変換することもできる。相互関係は、あるタスク１４による出力および別のタスク１４への入力であるデータのセットを含むタスク１４間の順序を特定する。図２において、矢印３４（１）は、タスク１４（１）（すなわち、読み出し）とタスク１４（２）（すなわち、ＳｅｌｅｃｔＭａｎｙ（マッパー（mapper）））との間の相互関係を表している。言い換えると、矢印３４（１）は、タスク１４（１）による出力およびタスク１４（２）への入力であるデータのセットを表している。同様に、矢印３４（２）は、タスク１４（２）とタスク１４（３）との間の関係を表しており、矢印３４（３）はタスク１４（３）とタスク１４（４）との間の関係を表している。
【００２５】
図２の例において、タスク１４は、入力データのセットをある他のタスク１４から受け取り、出力データのセットをある他のタスク１４へ提供する。他の実施形態において、各タスク１４は、入力データのセットを任意の適した数の他のタスク１４から受け取り、および／または出力データのセットを任意の適した数の他のタスク１４へ提供する。
【００２６】
図２の実施形態において、クエリー構文は、クエリー構文がネイティブのプログラミング言語に直接統合されないような呼び出し方策に基づく方法を使用する。例えば、Ｃ＋＋などのネイティブのプログラミング言語のゆえ、クエリー構文は、ラムダ式を使用して実装されうる。クエリー構文は、ユーザコード１２においてネイティブの言語にて他のコードを伴い構成されることが可能で、およびユーザコード１２の遅延実行を許すことが可能である。結果として、クエリー構文を伴う宣言型のプログラミングモデルは、Ｃ＋＋などのネイティブの言語上で実装されることが可能で、分散環境において増加した実行性能を提供する一方で、存在するネイティブの言語のコンパイラを使用することができる。
【００２７】
ある実施形態において、実行環境１０は動的なデータおよび計算を提供して、およびユーザコード１２のための柔軟性を調達して、実行の効率を改善する。特に、実行環境１０は、ユーザコード１２の実行が、タスク１４よって操作されるデータのサイズ、ランタイムにて利用可能である計算リソース、およびユーザコード１２によって提供される任意のコンテクストに応じたヒューリスティックに対して柔軟性があるようにする。実行環境１０は、ＲＡＲ１８およびスケジューラ２０の使用を通じて柔軟性を提供する。柔軟性は、ユーザコード１２の各タスク１４のための同時実行のレベルを、タスク１４の実行の時間にて利用可能なデータの量および計算リソースに基づいて動的に調整する能力について言及する。
【００２８】
上で記載したように、スケジューラ２０は、タスク１４のための入力データのセットおよびコンピュータシステムの処理リソースが利用可能になるときに、実行のためのタスク１４をディスパッチする。ＲＡＲ１８における各タスク１４のために、スケジューラ２０は、タスク１４のための入力データのセットのサイズ、タスク１４の呼び出しの時に利用可能である計算リソースの量、およびユーザコード１２によって提供される任意のコンテクストに応じたヒューリスティックを考慮することによって、同時実行のレベルを決定する。スケジューラ２０は、決定された同時実行のレベルに依存するタスク１４の多数のインスタンスを呼び出し、および利用可能な計算リソースへ分配する。そうすることによって、スケジューラ２０は、入力データのセットのサイズ、利用可能な計算リソース、およびユーザ指定のヒューリスティックを前提に、自動的にユーザコード１２の実行を適切なレベルへスケーリングする。
【００２９】
スケジューラ２０は、適切な同時実行のレベルの決定において、各タスク１４のための入力データのセットのサイズを考慮する。特に、スケジューラ２０は、コンピュータシステム内で入力データを移動することの多量のオーバーヘッド（例えば、クラスタにおけるマシン間でデータを移動することに費やされる時間）を考慮することができる。例えば、オーバーヘッドに基づいて、スケジューラ２０は、少量の入力データを伴うタスク１４のための同時実行の低いレベル、および多量の入力データを伴うタスク１４のための同時実行の高いレベルを選択することができる。
【００３０】
スケジューラ２０は、各タスク１４のための呼び出しの時に適切な同時実行のレベルを決定するので、スケジューラ２０は、基礎となるコンピュータシステムにおける計算リソースの能力の変更をとらえて説明する（account for）。例えば、スケジューラ２０は、計算リソースがコンピュータシステムに増加させられたこと（例えば、１つまたは複数のマシンがコンピュータシステムに加えられることが原因で）、またはコンピュータシステムから取り除かれたこと（例えば、コンピュータシステムの１つまたは複数のノードの失敗または利用不可能が原因で）を検出できる。
【００３１】
スケジューラ２０は、タスク１４の入力データのサイズおよびタスク１４のための利用可能な計算リソースの量を表す情報を、ユーザコード１２における１つまたは複数の関数に提供することができる。関数は、次々に、スケジューラ２０に、プログラマがタスク１４の実行のために薦める、推奨されているまたは最適な同時実行のレベルを提供することができる。スケジューラ２０は、この情報を入力データのサイズおよび利用可能な計算リソースの量とともに考慮して、適切なタスク１４のための同時実行のレベルを決定する。
【００３２】
図３は、（図２において示されている）ＤＡＧ１８Ａを使用して、ユーザコード１２を実行する実施形態を図示しているブロック図である。図３の例において、スケジューラ２０は、ＤＡＧ１８Ａにおけるタスク１４（１）−１４（４）のそれぞれのための適切な同時実行のレベルを決定し、および同時実行のレベルに基づく各タスク１４（１）−１４（４）のインスタンスの適切な数を決定する。例えば、スケジューラ２０は、タスク１４（１）が呼び出されるときに、シングルインスタンスが上記関数に基づきタスク１４（１）のために適切であると決定する。同様に、スケジューラ２０は、タスク１４（３）が呼び出されるときに、シングルインスタンスが上記関数に基づきタスク１４（３）のために適切であると決定する。
【００３３】
タスク１４（２）のために、スケジューラ２０は、Ｎのインスタンスが適切であると決定する。Ｎは２より大きいまたは２と等しい整数である。したがって、スケジューラ２０は、タスク１４（２）のための入力データのセットが、Ｎのサブセットに分けられるようにし、および実行のためにＮの計算リソース（例えば、クラスタまたはクラウドにおけるノードマシン）に至るまで提供されるようにする。スケジューラ２０は、タスク１４（２）によって生成される出力データのセットが、タスク１４（３）に提供されうる形式にマージされるようにすることもできる。
【００３４】
タスク１４（４）のために、スケジューラ２０は、Ｐのインスタンスが適切であると決定する。Ｐは２より大きいまたは２と等しい整数であり、Ｎと等しくてもまたは等しくなくてもよい。したがって、スケジューラ２０は、タスク１４（４）のための入力データのセットが、Ｐのサブセットに分けられるようにし、および実行のためにＰの計算リソース（例えば、クラスタまたはクラウドにおけるノードマシン）に至るまで提供されるようにする。スケジューラ２０は、タスク１４（４）によって生成される出力データのセットが、クエリーの出力として提供されうる形式にマージされるようにすることもできる。
【００３５】
動的データおよび計算の柔軟性は、ユーザコード１２の最適なスケーリングが起こりうる技術を提供する。ＲＡＲ１８またはＤＡＧ１８Ａにおける各タスク１４のための同時実行のレベルの確立における柔軟性は、ユーザコード１２が、利用可能な計算リソースおよびロードバランスに対して効率的に柔軟性があるようにできる。したがって、ユーザコード１２は、効率的に様々なコンピュータシステム上で実行されうる。
【００３６】
図４Ａは、上で記載したように、実行環境１０を実装するように構成されるコンピュータシステム１００の実施形態を図示しているブロック図である。
【００３７】
コンピュータシステム１００は、それぞれが１つまたは複数のプロセッシングコア１０３を含む１つまたは複数のプロセッサパッケージ１０２、メモリシステム１０４、ゼロまたはそれより多い入力／出力装置１０６、ゼロまたはそれより多い表示装置１０８、ゼロまたはそれより多い周辺機器装置１１０、およびゼロまたはそれより多いネットワーク装置１１２を含む。プロセッサパッケージ１０２、メモリシステム１０４、入力／出力装置１０６、表示装置１０８、周辺機器装置１１０、およびネットワーク装置１１２は、任意の適した種類、数、および構成のコントローラ、バス、インタフェースを含む相互接続のセット、および／または他の有線または無線の接続を使用して、通信する。
【００３８】
コンピュータシステム１００は、一般的な目的または特定の目的のために構成される任意の適した処理装置を表している。コンピュータシステム１００の例は、サーバ、パーソナルコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、携帯電話またはスマートフォン、および音声／映像装置を含む。コンピュータシステム１００のコンポーネント（すなわち、プロセッサパッケージ１０２、メモリシステム１０４、入力／出力装置１０６、表示装置１０８、周辺機器装置１１０、ネットワーク装置１１２、および相互接続１１４）は、共通の筐体（図示せず）または任意の適した数の別々の筐体（図示せず）に含まれうる。
【００３９】
プロセッサパッケージ１０２は、それぞれ、命令を実行するように構成される実行ハードウェアを形成する１つまたは複数のプロセッシングコア１０３を含む（すなわち、ソフトウェア）。各プロセッシングコア１０３は、他のプロセッシングコア１０３から独立または実質上独立して命令を実行するように構成されており、マシン状態を含む。各プロセッサパッケージ１０２は、同じまたは異なるアーキテクチャおよび／または命令のセットを伴うプロセッシングコア１０３を含むことができる。例えば、プロセッシングコア１０３は、イン・オーダー実行コア、スーパースカラ実行コア、およびＧＰＧＰＵの実行コアの任意の組み合わせを含むことができる。プロセッサパッケージ１０２における各プロセッシングコア１０３は、メモリシステム１０４に格納される命令にアクセスし、および命令を実行するように構成される。命令は、ＢＩＯＳ（Basic Input Output System）またはファームウェア（図示せず）、ユーザコード１２、ランタイム非依存ライブラリ１６、スケジューラ２０、オペレーティグシステム（ＯＳ）１２２、および１つまたは複数の実行ランタイム２４のセット１２４を含むことができる。各プロセッシングコア１０３は、入力／出力装置１０６、表示装置１０８、周辺機器装置１１０、および／またはネットワーク装置１１２から受信された情報と連動して、または情報に応じて、命令を実行することができる。
【００４０】
メモリシステム１０４は、命令およびデータを格納するように構成される、任意の適した種類、数、および構成の揮発性または不揮発性の記憶装置を含む。メモリシステム１０４の記憶装置は、ユーザコード１２、ランタイム非依存ライブラリ１６、スケジューラ２０、ＯＳ１２２、および１つまたは複数の実行ランタイム２４のセット１２４を含むコンピュータが実行可能な命令（すなわち、ソフトウェア）を格納する、コンピュータが読み取り可能な記憶媒体を表す。メモリシステム１０４は、プロセッサパッケージ１０２、入力／出力装置１０６、表示装置１０８、周辺機器装置１１０、およびネットワーク装置１１２から受信された命令およびデータを格納する。メモリシステム１０４は、格納された命令およびデータを、プロセッサパッケージ１１２、入力／出力装置１０６、表示装置１０８、周辺機器装置１１０、およびネットワーク装置１１２に提供する。命令は、コンピュータシステム１００によって実行可能であり、明細書に記載されたユーザコード１２、ランタイム非依存ライブラリ１６、スケジューラ２０、ＯＳ１２２、および実行ランタイム２４の関数および方法を行なう。メモリシステム１０４における記憶装置の例は、ハードディスクドライブ、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリドライブおよびカード、ＣＤおよびＤＶＤなどの磁気および光学ディスクを含む。
【００４１】
コンピュータシステム１００は、ＯＳ１２２を起動および実行する。ＯＳ１２２は、プロセッサパッケージ１０２によって実行可能である命令を含んで、コンピュータシステム１００のコンポーネントを管理し、およびランタイム非依存ライブラリ１６、スケジューラ２０、ＯＳ１２２、および実行ランタイム２４がコンポーネントにアクセスおよび使用できるようにする関数のセットを提供する。ある実施形態において、ＯＳ１２２は、ウインドウズオペレーティングシステムである。他の実施形態において、ＯＳ１２２は、コンピュータシステム１００とともに使用するために適している別のオペレーティングシステムである。ランタイム非依存ライブラリ１６は、ＯＳ１２２と連動して実行可能である命令を含んで、図１において示される実行環境を生成し、およびランタイム関数をユーザコード１２およびスケジューラ２０に提供する。ランタイム関数は、ＯＳ１２２の統合された部分、または他の実施形態における他のプログラミングエンティティおよび／または構文として含まれうる。
【００４２】
入力／出力装置１０６は、命令またはデータをユーザからコンピュータシステム１００へ入力するように、または命令またはデータをコンピュータシステム１００からユーザへ出力するように構成される、任意の適した種類、数、および構成の入力／出力装置を含む。入力／出力装置１０６の例は、キーボード、マウス、タッチパッド、タッチスクリーン、ボタン、ダイヤル、ノブ、およびスイッチを含む。
【００４３】
表示装置１０８は、テキストおよび／または図形の情報をコンピュータシステム１００のユーザに出力するように構成される、任意の適した種類、数、および構成の表示装置を含む。表示装置１０８の例は、モニタ、ディスプレイスクリーン、およびプロジェクタを含む。
【００４４】
周辺機器装置１１０は、コンピュータシステム１００における１つまたは複数の他のコンポーネントを伴い操作されて、一般または特定の処理の機能を実行するように構成される、任意の適した種類、数、および構成の周辺機器装置を含む。
【００４５】
ネットワーク装置１１２は、コンピュータシステム１００が１つまたは複数のネットワーク（図示せず）にわたって通信できるように構成される、任意の適した種類、数、および構成の表示装置を含む。ネットワーク装置１１２は、情報が、コンピュータシステム１００によってネットワークへ転送され、またはコンピュータシステム１００によってネットワークから受信されるようにする、任意の適したネットワークプロトコルおよび／または構成にしたがって動作できる。
【００４６】
図４Ｂは、上で記載したように、実行環境１０を実装するように構成されるコンピュータシステム１５０の実施形態を図示しているブロック図である。コンピュータシステム１５０は、２つまたはそれより多いコンピュータシステム１００（１）−１００（Ｑ）のセットを含む分散コンピューティング環境を形成する。Ｑは、２より大きいまたは２と等しい整数である。コンピュータシステム１００（１）−１００（Ｑ）は、任意の適した種類、数、および構成のコントローラ、バス、インタフェースを含む相互接続１５２、および／または他の有線または無線の接続を使用して通信する。
【００４７】
コンピュータシステム１５０は、マシンのクラスタ（すわなち、コンピュータシステム１００（１）−１００（Ｑ）のクラスタ）として構成される。各コンピュータシステム１００（１）−１００（Ｑ）は、他のコンピュータシステム１００（１）―１００（Ｑ）として同じ構成または異なる構成を含むことができる。ある実施形態において、システム１５０における各コンピュータシステム１００（１）−１００（Ｑ）は、ＭＰＩなどのランタイム２４を含む。ランタイム２４は、コンピュータシステム１００（１）−１００（Ｑ）が含みうる任意の他のランタイム２４に加えて、クラスタのために構成される。他の実施形態において、システム１５０における各コンピュータシステム１００（１）―１００（Ｑ）は、任意の適した種類、数、および／または組み合わせのランタイム２４を含む。
【００４８】
図４Ｃは、上で記載したように、実行環境１０を実装するように構成されるコンピュータシステム１６０の実施形態を図示しているブロック図である。コンピュータシステム１６０は、２つまたはそれより多いコンピュータシステム１００（１）―１００（Ｒ）のセットを含む分散コンピューティング環境を形成する。Ｒは、２より大きいまたは２と等しい整数である。コンピュータシステム１００（１）−１００（Ｒ）は、任意の適した種類、数、および構成の有線および／または無線のネットワーク装置を含むネットワーク１６２を使用して、通信する。
【００４９】
コンピュータシステム１６０は、マシンのクラウド（すなわち、コンピュータシステム１００（１）−１００（Ｒ）のクラウド）として構成される。各コンピュータシステム１００（１）−１００（Ｒ）は、他のコンピュータシステム１００（１）−１００（Ｒ）として同じ構成または異なる構成を含むことができる。ある実施形態において、システム１６０における各コンピュータシステム１００（１）―１００（Ｒ）は、コンピュータシステム１００（１）−１００（Ｒ）が含みうる任意の他のランタイム２４に加えてクラウドのために構成されるランタイム２４を含む。他の実施形態において、システム１６０における各コンピュータシステム（１）―１００（Ｒ）は、任意の適した種類、数、および／または組み合わせのランタイム２４を含む。
【００５０】
特定の実施形態が明細書で例示および記載されてきたが、当業者にとって、様々な代替および／または同等の実装例が、本発明の範囲から逸脱すること無く、示されおよび記載された特定の実施形態の代わりとなりうることが認められるだろう。この出願は、本明細書で議論された特定の実施形態の任意の適用または変形に及ぶことを意図する。それゆえ、本発明は特許請求の範囲およびそれと同等なものによってのみ限定されることが意図される。
【図１】
0006010540.tif 000002
【図２】
0006010540.tif 000003
【図３】
0006010540.tif 000004
【図４Ａ】
0006010540.tif 000005
【図４Ｂ】
0006010540.tif 000006
【図４Ｃ】
0006010540.tif 000007