Nothing Special   »   [go: up one dir, main page]

JP5940503B2 - グラフ型計算における計算リソースの管理法 - Google Patents

グラフ型計算における計算リソースの管理法 Download PDF

Info

Publication number
JP5940503B2
JP5940503B2 JP2013201721A JP2013201721A JP5940503B2 JP 5940503 B2 JP5940503 B2 JP 5940503B2 JP 2013201721 A JP2013201721 A JP 2013201721A JP 2013201721 A JP2013201721 A JP 2013201721A JP 5940503 B2 JP5940503 B2 JP 5940503B2
Authority
JP
Japan
Prior art keywords
data processing
processing elements
processing element
elements
storage medium
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2013201721A
Other languages
English (en)
Other versions
JP2014029718A (ja
Inventor
ジョセフ スケフィントン サード ホーリー
ジョセフ スケフィントン サード ホーリー
イゴール シャーブ
イゴール シャーブ
エフライム メリウェザー ヴィシュニアク
エフライム メリウェザー ヴィシュニアク
Original Assignee
アビニシオ テクノロジー エルエルシー
アビニシオ テクノロジー エルエルシー
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by アビニシオ テクノロジー エルエルシー, アビニシオ テクノロジー エルエルシー filed Critical アビニシオ テクノロジー エルエルシー
Publication of JP2014029718A publication Critical patent/JP2014029718A/ja
Application granted granted Critical
Publication of JP5940503B2 publication Critical patent/JP5940503B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46Multiprogramming arrangements
    • G06F9/50Allocation of resources, e.g. of the central processing unit [CPU]
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46Multiprogramming arrangements
    • G06F9/50Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5061Partitioning or combining of resources
    • G06F9/5066Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46Multiprogramming arrangements
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T1/00General purpose image data processing

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Stored Programmes (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Magnetic Resonance Imaging Apparatus (AREA)
  • Complex Calculations (AREA)
  • Apparatus For Radiation Diagnosis (AREA)
  • Debugging And Monitoring (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Medicines That Contain Protein Lipid Enzymes And Other Medicines (AREA)
  • Advance Control (AREA)
  • Multi Processors (AREA)
  • Executing Machine-Instructions (AREA)

Description

本発明は、グラフ型計算(graph-based computations)における計算リソースの管理
に関する。
複雑な計算は有向グラフによるデータの流れとして表わせることがあり、有効グラフは、そのグラフの頂点と関係付けられる計算要素と、そのグラフのリンク(弧、辺)と対応する要素間のデータの流れと、を有する。そのようなグラフ型計算を実行するシステムが、米国特許第5,966,072号、「グラフとして表される計算の実行法」に記載されている。グラフ型計算を実行する一手法は、そのグラフの異なる頂点とそれぞれ関係付けられる幾つかのプロセスを実行し、そのグラフのリンクに従ってプロセス間の通信経路(コミュニケーションパス)を確立することである。例えば、通信経路は、指定されたパイプ、TCP/IP又はUNIX(登録商標)のドメインソケット、又は共有メモリを用いてプロセス間でデータを渡す。
本発明の一側面は、概して、グラフ型計算を実行するための方法を特徴付ける。本方法は:データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップ;データ処理要素を複数のセットに分割するステップであって、そのセットの内の少なくとも一つは複数のデータ処理要素を含む、ステップ;それぞれのセットに異なる計算リソースを割り当てるステップ;及び、その計算グラフに従ってデータを処理するステップであって前記割り当てられた計算リソースを用いて前記データ処理要素に対応する計算を実行するステップを含むステップ、を含む。
本発明の別の側面は、概ね、グラフ型計算を実行するためのコンピュータが読み取り可能な媒体上に格納されるコンピュータープログラムを特徴付ける。本コンピュータープログラムは:データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップ;データ処理要素を複数のセットに分割するステップであって、そのセットの内の少なくとも一つは複数のデータ処理要素を含むステップ;それぞれのセットに異なる計算リソースを割り当てるステップ;及び、その計算グラフに従ってデータを処理するステップであって前記割り当てられた計算リソースを用いて前記データ処理要素に対応する計算を実行するステップを含むステップ、をコンピューターシステムに実行させるための命令を含む。
本発明の別の側面は、概ね、グラフ型計算を実行するためのシステムを特徴付ける。本システムは、複数のデータ処理要素がリンク要素により連結される計算グラフの仕様を受け取るとともに、その複数のデータ処理要素を複数のセットに分割し、その分割されたセットのうちの少なくとも一つのセットは複数のデータ処理要素を含むようにする、電子回路を含む予備実行モジュールを含む。本システムは、それぞれのセットに異なる計算リソースを割り当てるとともに、その割り当てられた計算リソースを用いてデータ処理要素に対応する計算を実行することを含む「計算グラフに基づくデータ処理を行う」、ための電子回路を含む実行モジュールを含む。
本発明の態様には、以下の特徴の内の一つ以上を含めることができる。
ひとつのセットに割り当てられた少なくとも一つの計算リソースは、処理(プロセス)を含む。
それぞれのリンク要素は、上流のデータ処理要素の出力から下流のデータ処理要素の入力へのデータの流れと関係付けられる。
データ処理ステップは、その複数のセットの内の少なくとも一つのセットに対して、そのセット内のデータ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内のデータ処理要素と対応する計算を実行するステップを含む。
1つのセットに割り当てられた1つの計算リソースは、上流のデータ処理要素の出力からのデータの流れと関係付けられるワーク要素を、同上流のデータ処理要素と同じセット内の下流のデータ処理要素と関係付けられる機能を呼び出すことにより、同下流のデータ処理要素の入力へと通過させる。
その関数は、その上流のデータ処理要素と関係付けられた関数によりワーク要素が書き込まれた格納場所から、ワーク要素を読み出す。
その上流のデータ処理要素と関係付けられた関数及びその下流のデータ処理要素と関係付けられた関数は、同一プロセスにより呼び出される。
データ処理ステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を維持するステップを更に含む。
その各アクティビティ量は、各データ処理要素に従って処理されるデータ量を含む。
その各アクティビティ量は、各データ処理要素と対応する計算を実行する1つのセットに割り当てられた計算リソースが費やす時間量を含む。
1つのセット内の複数のデータ処理要素は、前記計算グラフの連結有向サブグラフを(1つ)形成する。
サブグラフはツリーを含む。
複数の入力を有する1つのセット内の各データ処理要素に対して、そのデータ処理要素の入力にリンクされる全ての上流のデータ処理要素もそのセット内にある。
サブグラフ内に上流要素を持たないそのサブグラフ内のデータ処理要素に対する制御メッセージの受信に応答して、そのサブグラフ内の他のデータ処理要素のそれぞれと関係付けられる関数が呼び出され、それにより、そのサブグラフ内の各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、そのサブグラフ外部にその制御メッセージを伝播する。
そのサブグラフ内のデータ処理要素毎の状態情報は、単一ファイルに保存される。
そのデータ処理要素は、特定の並列処理段数を有する。
1つのセット内のデータ処理要素のそれぞれは、同一の並列処理段数を有する。
計算グラフの仕様は、各データ処理要素と関係付けられる実行段階を示す。
1つのセット内の各データ処理要素は、同じ実行段階と関係付けられる。
本発明の態様には、以下の利点の内の一つ以上を含めることができる。
データ処理アプリケーションをデータの流れ(データフロー)計算グラフとして表すことは、アプリケーションを構築し、関連する計算を理解し且つ分析する過程にある開発者を援助する。その計算は、処理毎に、ホストのオペレーティングシステム内で実行される。各処理は、処理する時間及びメモリ等の計算リソースと関係付けられる。各プロセスと関連するオーバーヘッドに起因して、計算システムが使用する計算リソースの全体は、同時に実行している処理の数とともに増大するのが普通である(場合によっては、処理の数とともに全てのリソースが直線的に増加する訳ではないが)。処理の回数を低減させるために、計算を「手で」組み合せて処理の数を減らすことができるが、それでは、計算グラフのプログラミングの利点(例えば、使用法の簡便さ、理解の容易さ等)が幾つかが犠牲になる。
通信する処理(通信プロセス)として実装されるデータの流れ計算グラフにおいては、バッファリングにより、端から端までの待ち時間は増加するけれども処理のオーバーヘッドを低下させることができる。バッファリングをしなければ待ち時間を低下させることができるが、オーバーヘッドは増加する。何故なら、より大きなオペレーティングシステムのリソースを用いてより小さなデータ量を移動させることになるからである。
この過剰なオーバーヘッドと過剰な待ち時間との間のトレードオフを軽減するために、多数のグラフ成分を、一度に一つの成分のワーク(作業)を実行する単一の処理として(つまり「折り畳んで」)実行し、コピーせずに、つまり処理間でのデータを移動しなくても、メモリにデータを渡すことができる。この手法では、データは、単一の処理内の成分のネットワークを通じてプッシュされる。
例えば、折畳みのない実行(非折り畳み実行)においては、一つのデータの流れにより連結される二つの成分は、それぞれ別々の処理において実行され、1つのバッファを通じて通信する。第1成分は、その生成された出力(例えば、多数の出力ワーク要素の蓄積)をバッファに格納する。第1成分は、そのバッファを、例えばオペレーティングシステムコールを用いて、第2成分に渡す。次いで、第2成分は、そのバッファ内のデータを処理する。二つの処理が、同一の処理内にて「折畳み実行」で一緒に折り畳まれている場合には、折り畳まれたプロセスは、それがワーク要素を生成し且つ受け取る関連手順を制御するので、ワーク要素をバッファリングする必要がない。折り畳まれたプロセスは、第1成分と関係付けられる処理が生成した各ワーク要素を、それが生成されたとき、第2成分と関係付けられる手順に入力引数として渡す。即ち、データの流れは制御の流れとして実現される。
折畳み実行または非折畳み実行のいずれにおいても、成分は、関連する段数の並列処理を有することができる。非折畳み実行では、成分の並列処理段数に等しい幾つかのプロセスを創出することができる。折畳み実行では、同一の並列処理段数をもつ連結された成分は、同一処理において例示化されるので、共通の並列処理段数と等しい幾つかのプロセスが創出される。
多数の成分を単一の処理内に折り畳むと、処理間のデータ移動が減少し且つ計算グラフの起動時間及びシステム規模が減少することにより(何故なら、実行している合計プロセスがより少ないので)、性能が向上する。データのバファリングを持つことなく且つ待ち時間を増加することなしに、過度の文脈切換え(context-switching)が回避される。これら全てが、データ流れ計算グラフモデルの表現性、使用法の簡便さ、及び、明解さを犠牲にすることなく行われる。
本発明の他の特徴および利点は、以下の説明から、およびクレームから明らかとなろう。
グラフ型計算を実行するためのシステムのブロック図である。 計算グラフである。 計算グラフである。 並列計算グラフである。 並列計算グラフである。 折り畳まれたセットに成分を割り当てる手順を示すフローチャートである。
1 システム概観
図1を参照すると、グラフ型計算を実行するためのシステム100は、データ記憶装置102に連結される開発環境104、及び、データ記憶装置102に連結されるランタイム環境106を含む。開発者101は、開発環境102を用いてアプリケーションを構築する。アプリケーションは、開発者が開発環境を使用した結果としてデータ記憶装置に書き込むことができる「そのデータ記憶装置102内のデータ構造」により規定された一つ以上の計算グラフと関係付けられる。データ構造は、例えば、計算グラフの頂点(成分またはデータセット)及び頂点間のリンク(データの流れ)を規定する。そのデータ構造は、グラフの「成分、データセット、及び、データの流れ」の様々な特性を含むこともできる。データ処理アプリケーションは、例えば、一つ以上の入力データセットから処理成分のグラフを通して一つ以上の出力データセットまで流れるデータ上において実行される計算を実施する計算グラフと関係付けられ得る。
ランタイム環境106は、UNIXオペレーティングシステム(UNIXは登録商標)等の、適切なオペレーティングシステムの管理下にある一台以上の汎用コンピュータ上で主催(host)される。例えば、ランタイム環境106には、ローカルな(例えば、SMPコンピュータのようなマルチプロセッサシステム)、ローカルに分散された(例えば、クラスタまたはMPPのように連結された複数のプロセッサシステム)、リモートで、リモートで分散された(例えば、LAN又はWANネットワークを経由して連結される複数のプロセッサ)、又は、これらの任意の組み合せの、マルチ中央処理ユニット(CPU)を用いるコンピューターシステムの構成を含む「複数ノード並列計算環境(multiple-node parallel computing environment)」を含めることができる。ランタイム環境106によってアクセスされる入力、出力又は中間のデータセットは、並列ファイルシステム(例えば、データ記憶装置102、又は、通信リンクを通してローカル的に或いはリモート的にシステム100に連結される外部データ記憶装置)内に格納される並列の「マルチファイル」とすることができる。
グラフ内の多数の成分(multiple components)を同時に実行することは、並列処理の一形式を提供する。追加的な並列処理は、グラフの様々な成分を様々な計算ノードに分配することにより達成することができる。グラフの要素(例えば、データセット、成分、及び、流れ)は明示的に又は暗示的に複製されることができ、それにより、ランタイム環境106内に追加的な並列処理を導入することができる。
ランタイム環境106は、計算の実行及び(装置の)コンフィギュレーションのために、格納されたスクリプトからの制御入力、又は、ユーザ103からの入力に基く制御入力を受け取るよう構成される。その制御入力には、対応する計算グラフを用いて特定のデータセットを処理するコマンドを含めることができ、そのコマンドは、格納されたグラフデータ構造において規定される。ユーザ103は、例えば、コマンドライン又はグラフィカルインターフェースを用いて、ランタイム環境106と対話(相互に作用)することができる。
ランタイム環境106は、「与えられた計算グラフを規定する格納されたグラフデータ構造を読み出し、且つ、成分の計算を実行するためのプロセス(例えば、ホストオペレーティングシステム内での実行プロセス、つまりスレッド)等の計算リソースを割り振り且つ配置構成(コンフィギュレーション)する」ための予備実行モジュール110を含む。以下に更に詳細に説明するように、計算グラフを実行するときに、成分をプロセスに割り当てる様々な手法がある。
予備実行モジュール110は、また、成分間のデータの流れを実行するための成分間通信リソース(例えば、指定されたパイプ又は共有メモリ)を割り当て、そのプロセスが新しいワーク要素を受け取る準備が未だ整っていない成分の入力ポートに到着するワーク要素に対する記憶場所(storage space)を割り当てる。ワーク要素を成分間のデータの流れの上で通過させるためのリソースは、システム100の処理及び格納のオーバーヘッドの一因となる。より詳細に後述するように、幾つかの手法においては、成分間通信が関数呼出しにより実行され、このオーバーヘッドを減少させる。
ランタイム環境106には、予備実行モジュール110が計算グラフに割り当てたプロセスの実行をスケジュール化し且つ管理するための実行モジュール112が含まれる。実行モジュール112は、データベースエンジン、データ記憶装置、又は、そのグラフ成分と関係付けられる処理の最中にアクセスされる他のモジュールのような、システム100に連結される外部計算リソースと相互に作用することができる。
計算グラフを実行した後に、又は、実行中に所定の間隔にて、報告モジュール114は、その計算グラフの個々の成分と関係付けられる統計値等の「与えられた計算を特徴付ける情報」を提供する。報告モジュール114により報告される幾つかの情報は、その計算グラフが生成する出力から得られる。その報告される情報の幾つかは、その計算グラフの実行を監視することにより得られる。
ランタイム監視モジュール(RMM)116は、計算グラフに割り当てられた一つ以上の処理の実行を監視し、報告モジュール114に情報を提供する。この情報には、例えば、それぞれの成分を実行するために費やした中央処理ユニット(CPU)の時間、又は、それぞれの成分によって処理されたデータの量が含まれる。
2 グラフ実行
図2Aを参照すると、計算グラフ200の一例は、計算グラフ200の成分204A〜204Jによって処理される予定の一連のワーク要素を提供する入力データセット202を含む。例えば、データセット202は、「データベースシステム、又は、トランザクション処理システムのトランザクション」と関連する「データのレコード(記録)」を含むことができる。各成分は、計算グラフ200全体により定義される計算の一部と関係付けられる。ワーク要素(例えば、個々のデータのレコード)は、成分の一つ以上の入力ポートに入り、出力ワーク要素(場合によっては、入力ワーク要素であるか、又は、入力ワーク要素の処理されたバージョンである)は、一般的には成分の一つ以上の出力ポートから出る。グラフ200においては、成分204E、204G及び204Jからの出力ワーク要素が出力データセット206A〜206C内に格納される。
グラフ200においては、第1フィルタ成分204Aが、その入力ポートで受け取ったワーク要素のサブセットを選択して第2フィルタ成分204Bに送り、選択されなかったワーク要素を成分204Cに送り、成分204Cは成分204Dに提供する。第2フィルタ成分204Bは、その入力で受け取ったワーク要素のサブセットを選択して成分204Eに送り、成分204Eは出力データセット206Aに提供する。第2フィルタ成分204Bにて選択されなかったワーク要素は複製成分204Fに送られ、複製成分204Fは各ワーク要素のコピー(複製物)を成分204Gに送る。成分204Gは出力データセット206Bに供給する。複製成分204Fは前記各ワーク要素のコピー(複製物)をインターフェース成分204Hにも送る。インターフェース成分204Hは、ランタイム環境106に対して完全にはネイティブでない「外部プログラム」の実行をトリガーするインターフェースを提供する。例えば、この外部プログラムは、ランタイム環境106に完全には組み込まれていない言語で書かれた旧仕様のプログラムでもよい。インターフェース成分204Hは、その開発環境のネイティブ言語を用いて外部プログラムを再コード化することなしに、その外部プログラムを計算グラフ200の一部として実行するメカニズムを提供する。集約成分204Iは、インターフェース成分204H及び成分204Dからのデータの流れを結合し、そのワーク要素の結合したデータの流れを成分204Jに送り、成分204Jは出力データセット206Cに提供する。
2.1 別々のプロセス
計算グラフを実行する手法の第1の形式においては、予備実行モジュール110は、各成分に対して別々の処理を割り当てる。例えば、「一成分につき一処理」の方法においては、1つの処理が各成分に対して割り当てられる。成分と対応する処理は、その成分により定義されるデータアクセス、計算、及び、データ変換タスクを取り扱う。実行モジュール112は、ホストのオペレーティングシステム内で処理を起動し、その成分の処理により実行されない計算グラフと関係付けられるタスクを取り扱う。
グラフ成分が、関連する段数の並列処理を有する場合、予備実行モジュール110は、そのグラフ成分の異なるインスタンスに対して、成分の並列処理段数と同じ数の別々のプロセスを割り当てる。例えば、ある成分は、随意的に、N列の(N通りの)並列成分として(例えば開発者101により)指定される。N列の並列成分に対して、その成分のN個のインスタンスのそれぞれが、N個のノードの内の一つにおける処理として(又はスレッドとして、又はマルチスレッドプロセッサ内の軽量処理の他の形式として)実行される。これらの場合、並列成分のインスタンス毎に一つの処理またはスレッドがあることになる。
図3Aを参照すると、並列グラフ300は、出力マルチファイル306に連結される直列の三つのN列並列成分304A、304Bおよび304Cに連結される入力マルチファイル302を含む。この例においては、入力(出力)マルチファイルは、N個の処理による並列アクセスが、N個に分割されたデータの流れの情報源となる(N個に分割されたデータの流れを押し込む)ことを可能にするように「N列に並列」である。代替として、入力及び出力のデータセットは、シリアルにアクセスされるデータファイルであってもよく、又は、入力302と第1成分304Aとの間のデータの流れ上の成分、及び/又は、最後の成分304Cと出力306との間のデータの流れ上の成分、を再分割することを利用して、N個に分割されたものを越えるか又はそれ未満のマルチファイルとしてもよい。グラフ300が、一成分インスタンスあたり一つの処理を用いて実行される場合、同時に実行されている処理が3N個だけ存在する。
上記の一成分あたり一つの処理、一インスタンスあたり一処理の手法は、システム100がパイプライン並列処理を上手く活用できるようにするので、複数の成分にデータを同時に処理させることによって計算グラフの処理量(スループット)を増加させることができる。しかしながら、各処理に関連するオーバーヘッドがシステム性能を制限することがある。例えば、起動時間は、場合により、成分処理を開始するのに必要な時間によって支配される。従って、成分の多いグラフの方が開始時間が長くなる場合がある。そのようなグラフは、同時に実行できる計算グラフの数を制限する「より大きな規模のメモリ(a larger memory footprint)」を有する場合もある。開発者101は、場合によっては、複数の成分内に実装されているロジックを一つ以上の複雑な成分に集約することにより、グラフ内の成分の数を減少させることができる。しかしながら、そのような手動によるグラフ操作は、常に可能とは限らないし、或いは、好ましいとは限らない(例えば、使用法の簡便さ、理解の容易さ、又は、成分の再利用性を維持するために)。
2.2 成分折畳み
計算グラフを実行する手法の第2の形式においては、予備実行モジュール110は、随意的に、マルチ成分を実行するための幾つかのプロセスを割り当てる。例えば、「成分折畳み」法においては、予備実行モジュール110は、グラフの成分を、一つ以上の成分をそれぞれが含む一つ以上のセットに分割する。それぞれのセットには異なるプロセスが割り当てられる。従って、同一のセットに「一緒に折り畳まれた」成分に対しては、これらの成分により表される計算は同一の処理によって実行される。多数の成分を有するセットに対しては、実行モジュール112はホストのオペレーティングシステム内で「折り畳まれた処理」を起動する。
折り畳まれたプロセスは、そのセット内の成分それぞれにより定義されるデータアクセス、計算、及び、データ変換タスクを取り扱い、関数の呼出しとして、そのセット内の成分間のリンクに越しに通信を実施する。折り畳まれたプロセスは、与えられた入力を伴う最初の「ルート(root,根源)」成分の計算を呼び起こす「計算」関数を呼び出す。そのルート成分の計算が出力ポートと関係付けられる結果を生成した後、その折り畳まれたプロセスは、その結果を下流成分に対する入力として用いるリンクされた下流成分の「計算」関数を呼び出す。こうして、データは、ルート成分からサブセット内の下流の「内部」成分にプッシュされる。場合によっては、1つのサブセットは、ワーク要素をそのサブセットの内部成分に供給する二つ以上のルート成分を有することができる。この成分折畳み手法は、起動の待ち時間を減少させることに加えて、処理及び格納のオーバーヘッド並びにサブセット内の成分間通信に関連する待ち時間を減少させる。
幾つかの成分、例えば再フォーマットまたはフィルタリングを実行する成分であって、例えば単一のワーク要素上で一度に実行する成分は、この「プッシュ型モデル」の実行法に既に対応している。すなわち、プッシュ型成分が第1ワーク要素の処理を完了すると、そのプッシュ型成分は、入力ポートで利用可能になり次第、新しいワーク要素を処理する準備が整う。このプッシュ型モデルにおいては、上流成分は下流成分にてワーク要素をプッシュし、その下流成分はその計算を実行し、次いで、その下流成分は結果を更にそれの下流成分にてプッシュする、と次々に続く。
他の成分は、初期段階においてこのプッシュ型モデルに従って動作するように構成されていないこともあり、代わりに、「プル型モデル」の実行に従って動作するかもしれない。プル型成分の1つの例は、ワーク要素が到着した入力ポートに依る計算を実行する多数の入力ポートを有する成分である。その成分は、第2入力ポートでのワーク要素を待っているので、第1入力ポートにおけるワーク要素を処理する準備が出来ていないことがある(例えば、ソート操作又は結合操作を実行する成分)。他の種類のプル型成分には、単一入力ポートを有するものがある。従って、折り畳まれるプロセスは、必ずしも、プル型成分の入力ワーク要素に対して作動する「計算」関数を呼び出すことができるとは限らない。
プル型成分は、処理シーケンスにおける何らかのロジック中断(例えば、ファイルの終了点、又は、関連のないワークのユニット間の境界をマークする何らかの他のイベント)まで、全ての入力をバッファリングさせることにより、プッシュ型成分に作り直され得る。この場合、プル型成分に対する「計算」関数は、入ってくる各レコードをバッファ内に挿入し、且つ、ロジック中断時にそれが決定する順序がどうであろうともその順序にてバッファから読み出してその入力の全てを処理するように進む。
折り畳まれたプロセスは、関連する折り畳まれた成分の計算をスケジュール化する他の手法を利用することができる。例えば、折り畳まれたプロセスは、状態情報を検査してどの成分が実行される準備が整っている成分であるかを決定することができる。
2.2.1 折畳みの制約
予備実行モジュール110は、グラフを解析して、同一のセット内にどの成分を一緒に折り畳むべきかを決定する。このとき、モジュール110は、随意的に、開発者101又はユーザ103による「折り畳まれるセットへの成分の手動による割当て」、もしくは、どの成分を同一又は別の折り畳まれるセットに入れるかに関する他の制約を考慮しながらグラフを解析する。予備実行モジュール110は、どの成分が一緒に折り畳まれるべきかを決定するために以下の制約を考慮することができる。幾つかの手順は、折り畳まれる処理が追加的な関連処理を取り扱うためのメカニズムを提供することにより、これら制約の一部又は全てを随意的に省略することができる。
第1の制約は、成分が「折畳み可能」及び「折畳み不可能」の何れに指定されるか(例えば、開発者101により)に依存する。折畳み可能として指定された成分には、その成分の対応する計算を呼び出すために折り畳まれた処理により使用され得る特徴が含まれる。例えば、折畳み可能成分は、ランタイム環境106で実行されている折り畳まれた処理により呼び出され得る「計算」関数であって、その成分と関係する計算を起動することができる「計算」関数を有する。旧仕様のプログラムを実行しているインターフェース成分は、このような関数呼出しと互換性がないことがあり、従って、折畳み不可能として指定されることがある。他の成分が、実行されている計算の性質(例えば、計算が外部環境との複雑な相互作用に関わっている場合)に起因して、折畳み不可能として指定されることがある。
他の制約は、様々なグラフ部分が実行される予定である段階(フェーズ)の指定に依存する。例えば、上流成分の第1グループが第1段階で実行するよう選択され、これら成分がワーク要素の一つのバッチ分を完了した後、下流成分の第2グループが第2段階においてそのバッチに対して実行するよう選択される。ある場合においては、所与の段階にある成分に対する処理だけが所与の時点にて実行される。他の場合には、複数の段階を用いて、所与の時点にて所与のワーク要素のバッチ処理を行う予定の成分のグループを指定するが、異なる段階での処理がパイプライン並列処理を達成するために異なるバッチ上にて同時に実行されていることもある。どちらの場合でも、この制約は、所与の段階にある成分が同一の段階にある成分とともに折り畳められるべきことを維持する。
別の制約は、成分に対して指定される並列処理段数に関連する。成分は、直列に、又は、N列並列として指定される。上述したように、N列並列成分については、N個の成分のインスタンスのそれぞれが別の処理において実行される。成分の折畳み手法においては、並列に実行できるN個の成分のインスタンスが残っているが、その成分インスタンスは他の成分インスタンスと一緒に折り畳められ得る。この制約においては、同一の並列処理段数を有する成分だけが一緒に折り畳められる。直列成分は他の直列成分と一緒に折り畳まれ、N列の並列成分は、他のN列並列成分と一緒に折り畳まれる。例えば、図3Bは、図3Aに示された並列成分がどのように一緒に折り畳められるかについて図解する。グラフ300’が成分折畳みを用いて実行される場合、同時に実行されるN個の折り畳まれた処理が存在する。成分のセット312のN個のインスタンス毎に一つの折り畳まれた処理が存在する。
関連する別の制約は、一緒に折り畳められる成分が、そのデータの流れによって表わされるワーク要素を分割することを変更しない「直線状」のデータの流れにより連結されるということである。例えば、あるデータの流れは、N列並列成分から流れるワーク要素のN個の分割されたもの(パーティション)を、M個の分割されたもの(パーティション)に再分割することができる(ここで、M≠N、又はM=Nであり且つワーク要素がN個の分割されたもの(パーティション)の内で再シャッフルされたものである)。この制約においては、一緒に折り畳まれる成分は同一の並列処理段数を有し、折り畳まれる成分の内のワーク要素の明示的又は暗示的な再分割化(パーティション化)はない。
グラフの成分を折り畳んだセットに割り当てるための準備においては、予備実行モジュール110は、グラフ内のどの折畳み可能な成分がルート成分となり得るものの内部成分とはなり得ないか、及び、どの折畳み可能な成分がルート成分又は内部成分となり得るか、を決定する。例えば、幾つかの成分は、折り畳まれる処理により起動させることができる関連する「計算」関数を有するように構成されることができない。
潜在的なルート成分及び/又は潜在的な内部成分として成分を分類することは、例えば、これらの成分が開発されている間に、オフラインにて発生し得る。グラフを構築するために利用可能な成分と関係付けられるデータ記憶装置102内に格納されるデータ構造には、その成分が折畳み可能成分か又は折畳み不可能成分かどうか、及び、その成分が潜在的なルート成分及び/又は内部成分であるかどうか、を示すメタデータを含めることができる。
2.2.2 折り畳まれるセットの決定
図4は、グラフ成分を折り畳まれるセットに割り当てるために予備実行モジュール110により使用される例示の手順400のフローチャートを示す。手順400は、折り畳まれる各セットを可能な限り大きくするように試みる「欲張り(greedy)アルゴリズム」に基づく。この手順400により生成される折り畳まれるセットは、データの流れを、グラフの連結されたサブグラフの一つ以上の内部成分に提供する単一のルート成分を有する。折り畳まれるセットはオーバーラップもしていない。予備実行モジュール110は、例えば実行時間よりも十分前に、手順400を実行し、データ記憶装置102内にその結果を格納することができる。或いは、予備実行モジュール110は、グラフが実行モジュール112によって実行される直前において手順400を実行することができる。例えば、予備実行モジュール110は、グラフが実行される前のランタイムに手順400を実行することができるが、但し、より詳細に後述するように、条件付き成分がそのグラフから削除された後に手順400を実行することができる。
手順400は、上述した折畳み制約の幾つかを使用する。成分が以下の条件を満たす場合、成分は折り畳まれたセットに対する制約を満たす:成分が折畳み可能である、成分がセット内の成分と同一の並列処理段数を有する、成分がセット内の成分と同一の段階にある、そして、成分が直線的流れによりセット内の成分に連結されている。
手順400は、グラフ内の各成分を「割当てされていない(未割当て)」としてマーキング(402)することにより開始される。手順400は、上流成分から下流成分までのトポロジカル(位相)順(例えば、深さ優先探索順)に基づいてグラフ内の成分を検査する。手順400は、入力データセットに連結される成分又は入力ポートのない成分にて開始され、この成分をルートとして第1セットに割り当てる(404)。手順はそのルート(ルート成分)が折畳み可能かどうかを判定する(406)。そのルート成分が折畳み可能であれば、手順400は、制約を満たす現セット内の成分の下流に直接的に連結される「割り当てされていない(未割当て)折畳み可能成分」があるかどうかを判定する(408)。このような成分が見付かった場合、その成分は現セットに追加され(410)、「割当て済」としてマークされる(412)。手順は、割当てされていない折畳み可能成分が追加できるかどうかを継続して判定する(408)。場合によっては、1つのセットに割り当てられる折畳み可能なルート成分は、他のどの成分とも一緒に折り畳まれず、その成分に専用の処理により実行されるように単集合(singleton:与えられた一個の元を唯一の要素とする集合)セット内に残される。
現セットがもはやそれ以上に大きく成長できない場合(例えば、そのセットに連結される残りの成分が既に割り当てられているか、又は、全ての制約を満たさない場合)、手順400は、割当てされていない成分がグラフ内に残っているか否かを判定し(414)、割当てされていない成分が残っていれば、入力データセットに連結される割当てされていない成分から、又は、入力ポートなしの割当てされていない成分から、又は、割り当てられる成分に連結される割当てされていない成分から、新規のルート成分を割り当てる(404)。
ルート成分が折畳み不可能であれば、手順400は、このルート成分を、その成分に専用の処理によって実行されるようにそれ自身のセット内に単独で残し、割当てされていない成分が残っている場合、新たしいルート成分を選択する。手順400は、割当てされていない成分が残っていないとき終了する(416)。
図2Bは、手順400に従ってグラフ200内で識別される3つの折り畳まれたセットを示す。手順400は、セット210のルートとして成分204Aを選択する。手順400は、トポロジカル順にグラフを廻って、成分204B、204E、204F及び204Gを折り畳まれたセット210に追加する。成分204Hは、折畳み可能という制約を満たさないので、セット210に追加されない。手順400は、続けて、成分204C及び204Dを折り畳まれたセット210に追加する。他の折り畳まれたセットはセット210に追加できないので、手順400は、折畳み不可能成分204Hを有する第2セット211を選択し、残りの成分204I及び204Jを有する第3セット212を選択する。
計算グラフによっては、成分自体が、計算グラフとして実行される。手順400は、グラフ内のそのような成分をそのグラフ内のサブグラフに拡張する。従って、折り畳まれる成分のセットは、そのような挿入されるサブグラフの境界を拡張して、そのような成分の何れかの「サブ成分」を含む。
計算グラフによっては、条件付き成分のメカニズムにより、パラメータ値及び計算されたメタデータに基づいてグラフ構造に対する変更が可能になる。グラフの条件付き成分は、その成分がランタイムにてグラフに現れるかどうかを制御する条件を有する。その条件は、ランタイムパラメータにより直接的又は間接的に計算され得る。条件付き成分を用いてグラフを最適化し、又は、グラフを特殊化することができる。条件付き成分は、2000年7月28日出願の米国特許出願第09/627,252号に詳細に記載され、引用して本明細書に組み込む。
折り畳まれたセットが識別された後、予備実行モジュール110には、随意的に、グラフを修正し、それにより、折り畳まれたセット間のバッファ又はアダプタ等の要素を含めることができる。
折り畳まれたセット内のサブグラフの成分のトポロジーについての制約を有する手順を含む他の手順を用いて、折り畳まれたセットを決定することができる。例えば、実施の形態によっては、折り畳まれたセット内の連結された成分のサブグラフは、ルート成分から下流の単一の入力内部成分を持つツリートポロジーを有する。実施の形態によっては、折り畳まれた処理は、折り畳まれたセット内のマルチ入力成分を支給するアクションを実行することができる。例えば、マルチ入力成分がルート成分の下流にある場合、折り畳まれた処理は複数の入力に対するデータをバッファリングし、全てのバッファが利用可能なデータを有する場合、マルチ入力関数の「計算」関数を呼び出すことのみを行う。折り畳まれるセットは、セット内のマルチ入力成分それぞれに対して、その成分の入力に連結される全ての上流成分もそのセット内にあるようなトポロジーを有することができる。
2.2.3 折り畳まれた処理の実行
実行モジュール112は、予備実行モジュール110により識別された折り畳まれたセットと対応する折り畳まれた処理を開始する。予備実行モジュール110は、実行モジュール112に、それぞれの折り畳まれたセット内の成分及びこれらの成分を連結するデータの流れを識別する情報を提供する。実行モジュール112は、データ記憶装置102内の成分オブジェクトを指すポインタを含むランタイムデータ構造を生成し、折り畳まれたセット内の成分間で通信するためのワーク要素を格納する記憶空間を割り当てる。割り当てられる記憶空間の量及び成分間でワーク要素データを移動するために費やされる時間は、小さい値に維持され得る。異なる成分に対する計算が実行されている間に、折り畳まれたプロセスが同じ記憶空間にアクセスできるからである。
例えば、折り畳まれたプロセスは、データの流れと対応するワーク要素を格納するために割り当てられた記憶空間を用いて、上流成分から下流成分にデータを通信する。成分に対する「計算」関数は、その記憶空間内の適切な場所を指すデータポインタ変数を読み出すことにより、そのワーク要素にアクセスすることができる。
上流成分の「計算」関数は、下流成分に対するデータポインタ変数と対応する記憶空間が、処理されるべきデータを確実に含むようにする。場合によって、これは、下流成分がアクセスする記憶空間内にデータを単に書き込むだけの上流成分に関係する。しかしながら、入力データを変更しない成分(例えば、フィルタ成分)については、データはアクセス可能な場所に既に格納されている場合があり、そのデータを移動する必要はなく、反対に、適切なデータポインタ変数を提供することにより準備され得る。
それぞれの折り畳まれた処理は、折り畳まれたセット内の成分を連結するデータの流れによって定義されるシーケンスに従って計算関数を繰り返し呼び出すことによって、成分と対応する計算を起動する。上流成分は、下流成分の「計算」関数を呼び出す。「計算」関数は、成分と関係付けられる計算を実行する。例えば、その計算は、成分と関係付けられる状態変数の更新、格納したワーク要素の変換、新規ワーク要素の生成、又は、出力データを適切な記憶空間内に格納することを確実にすることによるデータの下流への通信、を伴うことができる。「計算」関数が、折り畳まれた処理に制御を戻すと、関連する成分は、そのデータポインタ変数と関係付けられるデータを既に処理したと見なされる。
ルート成分は、折り畳まれたセットにデータが供給されるポイントである。多くの場合、これは入力ストリーム又はファイルからデータを読み出すことにより、若しくはデータベースや待ち行列等の外部システムからデータを抽出することにより行われる。場合によっては、データはルート成分によって生成される。ルート成分の「計算」関数は、折り畳まれた処理へと制御を戻すことなしに折り畳まれたセットを通じて任意の大量のデータをプッシュすることはない。例えば、ルート成分の「計算」関数は、以下のコードの内の一つにより、所定の間隔で折り畳まれた処理に制御を戻す:
KEEP_GOING:このコードは供給されるべきデータが更にあることを示す。折り畳まれたプロセスは、「計算」関数を再度読み出すことにより応答する。
ERROR:このコードは、エラーが発生したことを示す。折り畳まれたプロセスにアクセス可能なグローバルな「エラーステータス」変数は、詳細なエラーメッセージを含む。例えば、折り畳まれた処理は、エラーメッセージを表示すし且つ異常終了することにより応答する。
REACHED_EOF:このコードは、供給されるべきデータがそれ以上ないことを示す。折り畳まれた処理は、詳細に後述するように、折り畳まれたセットを停止する(シャットダウンする)ことにより応答する。
GOT_BLIP:このコードは、制御メッセージ(ブリップ、blip)を受け取ったことを示す(例えば、ワーク要素の連続的な流れの中のチェックポイントメッセージ)。折り畳まれたプロセスにアクセス可能なグローバルな「ブリップ」変数は、制御メッセージを含む。折り畳まれたプロセスは、制御メッセージを処理し、処理が終ると、「計算」関数を再度呼び出すことにより応答する。
ルート成分がREACHED_EOFを返すと、折り畳まれたプロセスは、折り畳まれたセットを停止(シャットダウン)する。これは、その折り畳まれたセット内の成分それぞれと関係付けられる「シャットダウン」関数を、上流成分から下流成分に向けてトポロジカル的にソートされた順に呼び出すことにより行われる。
「シャットダウン」関数は、下流にプッシュされるデータを生成することができる。例えば、ハッシュロールアップ成分に対する「計算」関数は、各種の積算器内のデータを構築し、「シャットダウン」関数が呼び出されるまで出力データを生成しない。
ルート成分がGOT_BLIPを返すと、折り畳まれた処理は、ブリップを下流に伝播する。これは、折り畳まれたセット内の成分それぞれと関係付けられる「プロセスブリップ」関数を呼び出すことにより行われる。「シャットダウン」関数と同様に、その「プロセスブリップ」関数は、更なる計算をトリガーする。例えば、連続的なフローロールアップ成分は、その「プロセスブリップ」関数が呼び出されるまで、データを下流にプッシュしない。
例えば、引用して本明細書に組み込む米国特許第6,584,581号、発明の名称「データ処理をチェックポイントで調べる連続フロー」に記載されているように、ブリップはグラフ内の成分の状態をチェックポイントで調べるように、グラフ内の成分に指示できる。その場合、「プロセスブリップ」関数は、現在の状態情報を不揮発性記憶装置内のチェックポイントファイルに格納する責任を負う。折り畳まれたセット内の成分は、(例えば、効率化のために)チェックポイントファイルを共有することができる。共有されたチェックポイントファイルが採用される場合、チェックポイントブリップが折り畳まれたセットの外部にある何れかの成分に伝播される前に、折り畳まれたセット内の全ての成分はそれらのチェックポイント(それらをチェックポイントでチェックすること)を完了する。これは、例えば、チェックポイントでのチェックが完了した後、上流成分から下流成分に向けて、トポロジカルソート順で、成分の「プロセスブリップ」関数を読み出すことによるか、又は、ブリップを別の経路内の折り畳まれたセットの外部にある成分に伝播させることにより、達成することができる。
例えば、「計算」関数がデータベース又はウェブサーバを含む外部装置との相互作用に関与する成分を組み込むために、実行モデルは拡張されることができる。
外部装置との相互作用は、一般に、比較的規模が大きな及び/又は無限の時間量を取り得るので、アプリケーションのスループットを事実上制限する。一つの成分毎に一つの処理を実行にあたりスループットを向上させるための一方策は、ひとつの装置に対して複数の接続からなるセット(又はプール)を開放する(オープンする)ことであり、入力レコードが成分によって受け取られる際に、利用可能な接続に関するリクエスト(要求)を発生する。成分は、応答が返される時に、その応答を装置から非同期で取得し、適宜、出力レコードを生成する。しかしながら、この手法は、折り畳まれた実行の幾つかの実装と互換性がないことがある。何故なら、そのような成分に対する「計算」関数が、1回に一つの入力レコードを受け取り、その成分が戻される前に、その受け取った入力レコードについて対応する出力レコードを生成するからである。
プールされた接続及び折り畳まれた実行における非同期の結果の取得を上手く利用するために、そのようなリクエストを行う成分は、二つの成分、即ち:入力レコードを受け取ってリクエストを発行する第1成分、及び、応答を受け取って出力レコードを構築する第2成分、に効率的に分解される。次いで、第2成分は、単一の処理により実行されている折り畳まれた成分のセットへの追加された「ルート」として扱われ、対応する外部装置からの応答は第2成分への入力として扱われる。次いで、折り畳まれたセットを実行する処理は、何れかのソースからの入力−元のルート成分への入力又は外部装置からの応答−を待ち、適切なルート成分についての「計算」関数を呼び出す。
非折畳み又は折畳みの何れの実行においても、離間している装置に連結している成分からの結果の順番が入力の順番と一致している必要がある場合、結果は下流成分に渡される前に蓄積され且つ整理し直され得る。
3 モニタ(監視)
RMM116は、グラフの実行に関する情報を開発者101及び/又はユーザ103に提供する。RMM116は、グラフの個々の成分が実行中に一緒に折り畳まれた場合でも、それらの個々の成分のランタイム特性に関する情報を提供する。従って、グラフの成分と関係付けられる計算の特性は、その計算を実行する処理の数がそのグラフ内の成分の数と一致することを要求することなく、グラフの論理的構造に従って解析されることができる。例えば、RMM116は、成分折畳み手法又は一つの成分毎に一つのプロセス手法を用いて実行されるグラフに対する特性と概ね同じランタイム特性を表すことができる。
たった一つの成分を有する折り畳まれたセットに対し、及び、1つの成分毎に1つのプロセス手法において、RMM116は、成分と対応する処理に基づいてCPU時間等の特性を追跡し、RMM116は、その成分に出入りするデータの流れをサポートするデータ通信チャンネルに基づいてデータ処理量を追跡する。
二つ以上の成分を有する折り畳まれたセットに関し、RMM116は、折り畳まれる処理についてのCPU時間、及び、折り畳まれるセットのデータ処理量を、追跡し、これらの合計値を成分毎に分割する。簡単な手法は、その合計量を、折り畳まれたセット内の成分の数で除することであろう。しかしながら、多くの場合、監視した量をより正確に分割することが望まれる。
折り畳まれた処理は、対応する折り畳まれたセット内で表される成分及びデータフローと対応するように、格納される変数内に追跡情報を書き込む。例えば、成分に入ってくる(又は、成分から出て行く)データの流れと対応するデータポインタ変数が読み出される(又は、書き込まれる)たびに、対応するレコードカウントおよびバイトカウントの追跡値がインクリメントされる。
RMM116は、割り込み手法を用いてCPU時間のより正確な分解を獲得することができる。折り畳まれた処理が「折り畳まれたセット内の各種成分と関係付けられる関数」を呼び出すのに費やした時間の割合をサンプリングするために、タイマーが割り込みをトリガーする。それぞれの関数が呼び出されるときに、例えば、その関数は、対応する成分が「アクティブ」であることをグローバル変数内に書き込む。タイマーの時間がくると、割り込みがトリガーされ、折り畳まれた処理がアクティブな状態にある成分と関係付けられるカウンタをインクリメントする。折り畳まれたセット内の各成分についてのCPU時間を報告するために、折り畳まれたセットの合計時間が、これらのカウントに従って比例分割される。
CPU時間の正確な分解を獲得するための別の手法は、それぞれの折り畳まれた成分の「計算」関数及び「プロセスブリップ」関数の呼出し時間を計測することである。全ての呼出しの時間を計測することは許容できないオーバーヘッドを招くので、システムは、呼出しの何分かの一の時間を計測してもよい(例えば、最初は100の内のそれぞれを、次いで1000番目毎に)。次いで、収集した時間を用いて、合計のCPU時間を、折り畳まれた成分の内のそのプロセスに対して比例配分する。
上述した成分折畳み手法は、コンピュータ上で実行するためのソフトウエアを用いて実装することができる。例えば、本ソフトウエアは、プログラムされるか又はプログラム可能な一台以上のコンピューターシステム(分散、クライアント/サーバ、又は、グリッド等の様々なアーキテクチャを有することができる)上で実行する一つ以上のコンピュータープログラム内の手順を形成する。そのそれぞれのコンピューターシステムは、少なくとも一つのプロセッサ、少なくとも一つのデータ記憶装置システム(揮発性、及び、不揮発性メモリ、及び/又は記憶要素を含む)、少なくとも一つの入力装置または入力ポート、並びに、少なくとも一つの出力装置または出力ポートを備える。本ソフトウエアは、例えば、計算グラフの設計及び配置構成と関連する他のサービスを提供する規模がさらに大きなプログラムの内の一つ以上のモジュールを形成してもよい。グラフのノード及び要素は、コンピュータが読み取り可能な媒体に格納されるデータ構造、又は、データ収納庫内に格納されるデータモデルに準拠する他の体系化されたデータ、として実装することができる。
本ソフトウエアは、汎用又は専用のプログラム可能なコンピュータにより読み出すことが可能なCD−ROM等の媒体上で提供するか、若しくは、本ソフトウエアを実行するコンピュータにネットワークを経由して(伝播信号にエンコードして)配布することができる。全ての機能は専用コンピュータ上で、或いは、コプロセッサ等の専用ハードウエアを用いて、実行することができる。本ソフトウエアは、ソフトウエアにより規定される計算の様々な部分が異なるコンピュータにより実行されるように分散された様式にて実装することができる。そのようなコンピュータープログラムはそれぞれ、汎用又は専用のプログラム可能なコンピュータにより読み取り可能な記憶媒体又は装置(例えば、ソリッドステートメモリ又は媒体、若しくは磁気式もしくは光学式媒体)上に、格納されるか又はダウンロードされることが好ましく、記憶媒体又は装置がコンピューターシステムにより読み出されて本明細書で説明した手順を実行するとき、コンピュータを構成し且つ動作させる。本発明のシステムは、コンピュータープログラムとともに構成されたコンピュータが読み取り可能な記憶媒体として実装されると考えることもでき、その場合は、そのように構成されたストレージ媒体は、コンピューターシステムを特有でかつ所定の方法で動作させて本明細書で説明した機能を実行できるように構成される。
本発明の幾つかの実施の形態を説明してきた。しかし、言うまでもなく、本発明の精神および範囲から逸脱することなく、様々な改変を行うことができる。例えば、上記のステップの幾つかは、独立した順序とすることができ、従って、説明と異なる順序で実行することができる。言うまでもないが、上記説明は、説明を意図し、本発明の範囲を限定する意図はなく、本発明の範囲は、付帯の特許請求の範囲により定義される。他の実施の形態は特許請求の範囲の範囲内にある。

Claims (102)

  1. グラフ型計算を実行するための方法であって、
    コンピュータが、データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップ;
    前記コンピュータが、前記データ処理要素を複数のセットに分割するステップであって、少なくとも第1のセットは、前記計算グラフの連結有向サブグラフを形成する複数のデータ処理要素を含むステップ;
    前記コンピュータが、それぞれのセットに異なる計算リソースを割り当てるステップであって、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含むステップ;
    前記コンピュータが、前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含むステップであって、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にあるステップ;及び
    前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播するステップ;
    を含む方法。
  2. 請求項1に記載の方法において、
    前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
    方法。
  3. 請求項1に記載の方法において、
    前記データを処理するステップは、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行するステップを含む、
    方法。
  4. 請求項1に記載の方法において、
    前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    方法。
  5. 請求項4に記載の方法において、
    前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
    方法。
  6. 請求項1に記載の方法において、
    前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
    方法。
  7. 請求項1に記載の方法において、
    前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
    方法。
  8. 請求項1に記載の方法において、
    前記サブグラフはツリーを含む、
    方法。
  9. 請求項1に記載の方法において、
    セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
    方法。
  10. 請求項1に記載の方法において、
    前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するステップを更に含む、
    方法。
  11. 請求項10に記載の方法において、
    前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
    方法。
  12. 請求項1に記載の方法において、
    前記データ処理要素は、特定の並列処理段数を有する、
    方法。
  13. 請求項12に記載の方法において、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
    方法。
  14. 請求項1に記載の方法において、
    前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
    方法。
  15. 請求項14に記載の方法において、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
    方法。
  16. グラフ型計算を実行するためのコンピュータプログラムを格納するコンピュータ読み取り可能記憶媒体であって、前記コンピュータプログラムは、
    複数のデータ処理要素が複数のリンク要素により結合される計算グラフの仕様を受け取るステップ;
    前記複数のデータ処理要素を複数のセットに分割するステップであって、少なくとも第1のセットは、前記計算グラフの連結有向サブグラフを形成する複数のデータ処理要素を含むステップ;
    それぞれのセットに異なる計算リソースを割り当てるステップであって、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含むステップ;
    前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素と対応する計算を実行することを含むステップであって、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にあるステップ;及び
    前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播するステップ;
    をコンピュータシステムに実行させる命令を含む、コンピュータ読み取り可能記憶媒体。
  17. グラフ型計算を実行するためのシステムであって、
    予備実行モジュールであって、
    データ処理要素がリンク要素により結合される計算グラフの仕様を受け取り、
    前記データ処理要素を複数のセットに分割し、第1のセットは、前記計算グラフの連結有向サブグラフを形成する複数のデータ処理要素を含む、
    ための電子回路を含む予備実行モジュールと、
    実行モジュールであって、
    それぞれのセットに異なる計算リソースを割り当て、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含み、
    前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含む前記計算グラフに従ってデータを処理し、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にあり、
    前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播する、
    ための電子回路を含む実行モジュールと、
    を含むシステム。
  18. グラフ型計算を実行するためのシステムであって、
    データ処理要素がリンク要素により結合される計算グラフの仕様を受け取るための手段;
    複数の前記データ処理要素を複数のセットに分割するための手段であって、第1のセットは、連結有向サブグラフを形成する複数の前記データ処理要素を含む手段;
    それぞれのセットに異なる計算リソースを割り当てるための手段であって、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含む手段;
    前記計算グラフに従ってデータを処理するための手段であって、前記割り当てられた計算リソースを用いて、前記データ処理要素と対応する計算を実行することを含む手段であって、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にある手段;及び
    前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播する手段;
    を含むシステム。
  19. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
    コンピュータ読み取り可能記憶媒体。
  20. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記データを処理するステップは、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行するステップを含む、
    コンピュータ読み取り可能記憶媒体。
  21. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    コンピュータ読み取り可能記憶媒体。
  22. 請求項21に記載のコンピュータ読み取り可能記憶媒体において、
    前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
    コンピュータ読み取り可能記憶媒体。
  23. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
    コンピュータ読み取り可能記憶媒体。
  24. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
    コンピュータ読み取り可能記憶媒体。
  25. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記サブグラフはツリーを含む、
    コンピュータ読み取り可能記憶媒体。
  26. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
    コンピュータ読み取り可能記憶媒体。
  27. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するステップを更に含む、
    コンピュータ読み取り可能記憶媒体。
  28. 請求項27に記載のコンピュータ読み取り可能記憶媒体において、
    前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
    コンピュータ読み取り可能記憶媒体。
  29. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記データ処理要素は、特定の並列処理段数を有する、
    コンピュータ読み取り可能記憶媒体。
  30. 請求項29に記載のコンピュータ読み取り可能記憶媒体において、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
    コンピュータ読み取り可能記憶媒体。
  31. 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
    前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
    コンピュータ読み取り可能記憶媒体。
  32. 請求項31に記載のコンピュータ読み取り可能記憶媒体において、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
    コンピュータ読み取り可能記憶媒体。
  33. 請求項17に記載のシステムにおいて、
    前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
    システム。
  34. 請求項17に記載のシステムにおいて、
    前記データを処理することは、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行することを含む、
    システム。
  35. 請求項17に記載のシステムにおいて、
    前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    システム。
  36. 請求項35に記載のシステムにおいて、
    前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
    システム。
  37. 請求項17に記載のシステムにおいて、
    前記データを処理することは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納することを更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
    システム。
  38. 請求項17に記載のシステムにおいて、
    前記データを処理することは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納することを更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
    システム。
  39. 請求項17に記載のシステムにおいて、
    前記サブグラフはツリーを含む、
    システム。
  40. 請求項17に記載のシステムにおいて、
    セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
    システム。
  41. 請求項17に記載のシステムにおいて、
    前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するための電子回路を更に含む、
    システム。
  42. 請求項41に記載のシステムにおいて、
    前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
    システム。
  43. 請求項17に記載のシステムにおいて、
    前記データ処理要素は、特定の並列処理段数を有する、
    システム。
  44. 請求項43に記載のシステムにおいて、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
    システム。
  45. 請求項17に記載のシステムにおいて、
    前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
    システム。
  46. 請求項45に記載のシステムにおいて、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
    システム。
  47. 請求項18に記載のシステムにおいて、
    前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
    システム。
  48. 請求項18に記載のシステムにおいて、
    前記データを処理するための手段は、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行するための手段を含む、
    システム。
  49. 請求項18に記載のシステムにおいて、
    前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    システム。
  50. 請求項49に記載のシステムにおいて、
    前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
    システム。
  51. 請求項18に記載のシステムにおいて、
    前記データを処理するための手段は、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するための手段を更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
    システム。
  52. 請求項18に記載のシステムにおいて、
    前記データを処理するための手段は、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するための手段を更に含み、
    前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
    システム。
  53. 請求項18に記載のシステムにおいて、
    前記サブグラフはツリーを含む、
    システム。
  54. 請求項18に記載のシステムにおいて、
    セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
    システム。
  55. 請求項18に記載のシステムにおいて、
    前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するための手段を更に含む、
    システム。
  56. 請求項55に記載のシステムにおいて、
    前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
    システム。
  57. 請求項18に記載のシステムにおいて、
    前記データ処理要素は、特定の並列処理段数を有する、
    システム。
  58. 請求項57に記載のシステムにおいて、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
    システム。
  59. 請求項18に記載のシステムにおいて、
    前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
    システム。
  60. 請求項59に記載のシステムにおいて、
    1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
    システム。
  61. グラフ型計算を実行するための方法であって、
    コンピュータが、データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップ;
    各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定するステップであって、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができないステップ;
    前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割するステップであって、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含むステップ;
    前記データ処理要素の各セットに前記コンピュータの異なる計算リソースを割り当てるステップ;
    前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含み、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にあるステップ;
    を含む方法。
  62. 請求項61に記載の方法において、
    少なくとも1つのデータ処理要素が折畳み可能であり、少なくとも1つデータ処理要素が折畳み不可能であることを決定するステップを更に含む、
    方法。
  63. 請求項61に記載の方法において、
    前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
    方法。
  64. 請求項61に記載の方法において、
    前記データ処理要素の各セット内の各データ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含む、
    方法。
  65. 請求項61に記載の方法において、
    前記データを処理するステップは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行するステップを含む、
    方法。
  66. 請求項61に記載の方法において、
    前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    方法。
  67. 請求項66に記載の方法において、
    前記上流データ処理要素と関係付けられた前記関数を呼び出すプロセスは、前記下流データ処理要素と関係付けられた前記関数を呼び出すプロセスである、
    方法。
  68. 請求項61に記載の方法において、
    複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
    方法。
  69. 請求項61に記載の方法において、
    前記データ処理要素のそれぞれは、特定の並列処理段数を有する、
    方法。
  70. 請求項69に記載の方法において、
    前記データ処理要素のセット内の全てのデータ処理要素は、同一の並列処理段数を有する、
    方法。
  71. 請求項61に記載の方法において、
    前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
    方法。
  72. 請求項71に記載の方法において、
    前記データ処理要素のセット内のデータ処理要素のそれぞれは、同一の実行段階と関係付けられる、
    方法。
  73. 請求項61に記載の方法において、
    前記計算グラフを分析して、前記データ処理要素の特徴に基づく制約を用いて、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定するステップを更に含む、
    方法。
  74. 請求項73に記載の方法において、
    前記制約は、どのデータ処理要素が折畳み可能であり、どのデータ処理要素が折畳み不可能であるかの制約を含む、
    方法。
  75. 請求項73に記載の方法において、
    予備実行モジュールが、前記計算グラフを解析して、前記グラフ型計算が実行される前に、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定する、
    方法。
  76. 請求項73に記載の方法において、
    前記データ処理要素の各セットを決定するステップは、折畳み可能ルートデータ処理要素を決定するステップ、及び前記セット内に既にある折畳み可能データ処理要素から直接下流にあるどの折畳み可能データ処理要素も前記セット内にあるように、追加のデータ処理要素を決定するステップを含む、
    方法。
  77. グラフ型計算を実行するためのコンピュータプログラムを格納するコンピュータ読み取り可能記憶媒体であって、前記コンピュータプログラムは、
    データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップであって、リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられるステップ;
    各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定するステップであって、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができないステップ;
    前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割するステップであって、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含むステップ;
    前記データ処理要素の各セットコンピュータシステムの異なる計算リソースを割り当てるステップ;
    前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含み、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にあるステップ;
    前記コンピュータシステムに実行させる命令を含む、コンピュータ読み取り可能記憶媒体。
  78. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記コンピュータプログラムは、少なくとも1つのデータ処理要素が折畳み可能であり、少なくとも1つデータ処理要素が折畳み不可能であることを決定するための命令を更に含む、
    コンピュータ読み取り可能記憶媒体。
  79. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
    コンピュータ読み取り可能記憶媒体。
  80. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記コンピュータプログラムは、前記データ処理要素の各セット内の各データ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するための命令を更に含む、
    コンピュータ読み取り可能記憶媒体。
  81. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記データを処理するステップは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行するステップを含む、
    コンピュータ読み取り可能記憶媒体。
  82. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    コンピュータ読み取り可能記憶媒体。
  83. 請求項82に記載のコンピュータ読み取り可能記憶媒体において、
    前記上流データ処理要素と関係付けられた前記関数を呼び出すプロセスは、前記下流データ処理要素と関係付けられた前記関数を呼び出すプロセスである、
    コンピュータ読み取り可能記憶媒体。
  84. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
    コンピュータ読み取り可能記憶媒体。
  85. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記データ処理要素のそれぞれは、特定の並列処理段数を有する、
    コンピュータ読み取り可能記憶媒体。
  86. 請求項85に記載のコンピュータ読み取り可能記憶媒体において、
    前記データ処理要素のセット内の全てのデータ処理要素は、同一の並列処理段数を有する、
    コンピュータ読み取り可能記憶媒体。
  87. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
    コンピュータ読み取り可能記憶媒体。
  88. 請求項87に記載のコンピュータ読み取り可能記憶媒体において、
    前記データ処理要素のセット内のデータ処理要素のそれぞれは、同一の実行段階と関係付けられる、
    コンピュータ読み取り可能記憶媒体。
  89. 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
    前記計算グラフを分析して、前記データ処理要素の特徴に基づく制約を用いて、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定するステップを更に含む、
    コンピュータ読み取り可能記憶媒体。
  90. 請求項89に記載のコンピュータ読み取り可能記憶媒体において、
    前記制約は、どのデータ処理要素が折畳み可能であり、どのデータ処理要素が折畳み不可能であるかの制約を含む、
    コンピュータ読み取り可能記憶媒体。
  91. 請求項89に記載のコンピュータ読み取り可能記憶媒体において、
    予備実行モジュールが、前記計算グラフを解析して、前記グラフ型計算が実行される前に、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定する、
    コンピュータ読み取り可能記憶媒体。
  92. 請求項89に記載のコンピュータ読み取り可能記憶媒体において、
    前記データ処理要素の各セットを決定するステップは、折畳み可能ルートデータ処理要素を決定するステップ、及び前記セット内に既にある折畳み可能データ処理要素から直接下流にあるどの折畳み可能データ処理要素も前記セット内にあるように、追加のデータ処理要素を決定するステップを含む、
    コンピュータ読み取り可能記憶媒体。
  93. グラフ型計算を実行するためのシステムであって、
    予備実行モジュールであって、
    データ処理要素がリンク要素により連結される計算グラフの仕様を受け取り、リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられ、
    各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定し、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができず
    前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割し、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含む、
    ための電子回路を含む予備実行モジュールと、
    実行モジュールであって、
    前記データ処理要素の各セットに前記システムの異なる計算リソースを割り当て、
    前記計算グラフに従ってデータを処理し、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含み、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にある、
    ための電子回路を含む実行モジュールと、
    を含むシステム。
  94. 請求項93に記載のシステムにおいて、
    前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
    システム。
  95. 請求項93に記載のシステムにおいて、
    前記データを処理することは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行することを含む、
    システム。
  96. 請求項93に記載のシステムにおいて、
    前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    システム。
  97. 請求項93に記載のシステムにおいて、
    複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
    システム。
  98. グラフ型計算を実行するためのシステムであって、
    データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るための手段であって、リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる手段;
    各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定する手段であって、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができない手段;
    前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割する手段であって、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含む手段;
    前記データ処理要素の各セットに前記システムの異なる計算リソースを割り当てる手段;及び
    前記計算グラフに従ってデータを処理する手段であって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含む手段であって、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にある手段;
    を含むシステム。
  99. 請求項98に記載のシステムにおいて、
    前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
    システム。
  100. 請求項98に記載のシステムにおいて、
    前記データを処理することは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行することを含む、
    システム。
  101. 請求項98に記載のシステムにおいて、
    前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
    システム。
  102. 請求項98に記載のシステムにおいて、
    複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
    システム。
JP2013201721A 2006-05-16 2013-09-27 グラフ型計算における計算リソースの管理法 Active JP5940503B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US11/434,623 US7870556B2 (en) 2006-05-16 2006-05-16 Managing computing resources in graph-based computations
US11/434,623 2006-05-16

Related Parent Applications (1)

Application Number Title Priority Date Filing Date
JP2009511202A Division JP2009537908A (ja) 2006-05-16 2007-05-15 グラフ型計算における計算リソースの管理法

Publications (2)

Publication Number Publication Date
JP2014029718A JP2014029718A (ja) 2014-02-13
JP5940503B2 true JP5940503B2 (ja) 2016-06-29

Family

ID=38713244

Family Applications (2)

Application Number Title Priority Date Filing Date
JP2009511202A Pending JP2009537908A (ja) 2006-05-16 2007-05-15 グラフ型計算における計算リソースの管理法
JP2013201721A Active JP5940503B2 (ja) 2006-05-16 2013-09-27 グラフ型計算における計算リソースの管理法

Family Applications Before (1)

Application Number Title Priority Date Filing Date
JP2009511202A Pending JP2009537908A (ja) 2006-05-16 2007-05-15 グラフ型計算における計算リソースの管理法

Country Status (9)

Country Link
US (1) US7870556B2 (ja)
EP (1) EP2021920B1 (ja)
JP (2) JP2009537908A (ja)
KR (1) KR101413049B1 (ja)
CN (2) CN101443733B (ja)
AU (1) AU2007253862C1 (ja)
CA (1) CA2650143C (ja)
HK (1) HK1122627A1 (ja)
WO (1) WO2007137034A2 (ja)

Families Citing this family (79)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7877350B2 (en) 2005-06-27 2011-01-25 Ab Initio Technology Llc Managing metadata for graph-based computations
CA2657233C (en) * 2006-08-10 2016-06-21 Ab Initio Software Llc Distributing services in graph-based computations
US8904391B2 (en) * 2007-04-23 2014-12-02 International Business Machines Corporation Policy-based access control approach to staff activities of a business process
EP2234017A3 (en) * 2007-07-26 2010-10-27 Ab Initio Technology LLC Transactional graph-based computation with error handling
US8954482B2 (en) * 2007-09-20 2015-02-10 Ab Initio Technology Llc Managing data flows in graph-based computations
US8069210B2 (en) * 2008-10-10 2011-11-29 Microsoft Corporation Graph based bot-user detection
AU2009322602B2 (en) * 2008-12-02 2015-06-25 Ab Initio Technology Llc Mapping instances of a dataset within a data management system
KR101693229B1 (ko) * 2009-02-13 2017-01-05 아브 이니티오 테크놀로지 엘엘시 데이터 저장 시스템과의 통신
CN102317911B (zh) 2009-02-13 2016-04-06 起元技术有限责任公司 管理任务执行
US8266289B2 (en) * 2009-04-23 2012-09-11 Microsoft Corporation Concurrent data processing in a distributed system
US8205113B2 (en) 2009-07-14 2012-06-19 Ab Initio Technology Llc Fault tolerant batch processing
EP2478433A4 (en) * 2009-09-16 2016-09-21 Ab Initio Technology Llc MAPPING DATA SET ELEMENTS
US8667329B2 (en) * 2009-09-25 2014-03-04 Ab Initio Technology Llc Processing transactions in graph-based applications
US8832663B2 (en) 2009-11-23 2014-09-09 International Business Machines Corporation Thread serialization and disablement tool
US8549523B2 (en) 2009-11-23 2013-10-01 International Business Machines Corporation Performing runtime analysis and control of folding identified threads by assuming context of another thread and executing in lieu of another thread folding tool
CN107102848B (zh) 2009-12-14 2020-11-24 起元技术有限责任公司 规定用户界面元素
US9665620B2 (en) 2010-01-15 2017-05-30 Ab Initio Technology Llc Managing data queries
US8555265B2 (en) 2010-05-04 2013-10-08 Google Inc. Parallel processing of data
US8875145B2 (en) 2010-06-15 2014-10-28 Ab Initio Technology Llc Dynamically loading graph-based computations
US20110314075A1 (en) * 2010-06-18 2011-12-22 Nokia Corporation Method and apparatus for managing distributed computations within a computation space
WO2012027560A1 (en) * 2010-08-25 2012-03-01 Ab Initio Technology Llc Evaluating dataflow graph characteristics
JP5902185B2 (ja) 2010-10-25 2016-04-13 アビニシオ テクノロジー エルエルシー コンピュータプログラムを表すデータフローグラフ内のデータセットオブジェクトの管理
KR101872748B1 (ko) 2011-01-14 2018-06-29 아브 이니티오 테크놀로지 엘엘시 데이터 콜렉션에 대한 변경 관리 방법
US9021299B2 (en) 2011-02-18 2015-04-28 Ab Initio Technology Llc Restarting processes
US9116759B2 (en) 2011-02-18 2015-08-25 Ab Initio Technology Llc Restarting data processing systems
US8782656B2 (en) * 2011-02-24 2014-07-15 International Business Machines Corporation Analysis of operator graph and dynamic reallocation of a resource to improve performance
US9116955B2 (en) 2011-05-02 2015-08-25 Ab Initio Technology Llc Managing data queries
US8606615B2 (en) * 2011-06-27 2013-12-10 Bank Of America Corporation System for managing and tracking an inventory of elements
US9503512B2 (en) 2012-03-21 2016-11-22 Intertrust Technologies Corporation Distributed computation systems and methods
JP6004818B2 (ja) * 2012-08-07 2016-10-12 インターナショナル・ビジネス・マシーンズ・コーポレーションInternational Business Machines Corporation 並列化方法、システム、及びプログラム
US10489360B2 (en) 2012-10-17 2019-11-26 Ab Initio Technology Llc Specifying and applying rules to data
US10108521B2 (en) 2012-11-16 2018-10-23 Ab Initio Technology Llc Dynamic component performance monitoring
US9507682B2 (en) * 2012-11-16 2016-11-29 Ab Initio Technology Llc Dynamic graph performance monitoring
US9274926B2 (en) 2013-01-03 2016-03-01 Ab Initio Technology Llc Configurable testing of computer programs
US9811233B2 (en) 2013-02-12 2017-11-07 Ab Initio Technology Llc Building applications for configuring processes
US11061539B2 (en) 2013-03-15 2021-07-13 The Mathworks, Inc. Reference nodes in a computational graph
KR102305084B1 (ko) 2013-04-23 2021-09-24 아브 이니티오 테크놀로지 엘엘시 컴퓨팅 시스템에 의해 수행되는 태스크 제어
CA3128713C (en) * 2013-12-05 2022-06-21 Ab Initio Technology Llc Managing interfaces for dataflow graphs composed of sub-graphs
KR102186050B1 (ko) 2013-12-06 2020-12-03 아브 이니티오 테크놀로지 엘엘시 소스 코드 번역
CN104954823B (zh) * 2014-03-31 2018-06-15 华为技术有限公司 一种图计算预处理的装置、方法及系统
KR102279859B1 (ko) 2014-07-18 2021-07-20 아브 이니티오 테크놀로지 엘엘시 파라미터 세트의 관리
US9330199B2 (en) * 2014-07-21 2016-05-03 Facebook, Inc. Striping of directed graphs and nodes with improved functionality
US9760406B2 (en) 2014-09-02 2017-09-12 Ab Initio Technology Llc Controlling data processing tasks
CA2959525C (en) * 2014-09-02 2021-08-03 Ab Initio Technology Llc Controlling data processing tasks
US9933918B2 (en) * 2014-09-02 2018-04-03 Ab Initio Technology Llc Specifying control and data connections in graph-based programs
WO2016036817A1 (en) * 2014-09-02 2016-03-10 Ab Initio Technology Llc Executing graph-based program specifications
KR102361155B1 (ko) * 2014-09-02 2022-02-09 아브 이니티오 테크놀로지 엘엘시 특정 데이터 포트 연결의 식별에 기반한 그래프 구성요소의 자동화된 클러스터링을 통한 그래프 기반 프로그램 명세의 컴파일
CA2959528C (en) * 2014-09-02 2023-03-07 Ab Initio Technology Llc Specifying components in graph-based programs
WO2016036820A1 (en) 2014-09-02 2016-03-10 Ab Initio Technology Llc Managing invocation of tasks
US9934070B2 (en) 2014-09-02 2018-04-03 Ab Initio Technology Llc Managing state for controlling tasks
US9626393B2 (en) 2014-09-10 2017-04-18 Ab Initio Technology Llc Conditional validation rules
JP6375201B2 (ja) * 2014-10-24 2018-08-15 株式会社野村総合研究所 データフローの自動並列化システム
US10055333B2 (en) 2014-11-05 2018-08-21 Ab Initio Technology Llc Debugging a graph
US9880818B2 (en) * 2014-11-05 2018-01-30 Ab Initio Technology Llc Application testing
US10437819B2 (en) 2014-11-14 2019-10-08 Ab Initio Technology Llc Processing queries containing a union-type operation
JP6413789B2 (ja) * 2015-01-22 2018-10-31 富士通株式会社 ジョブ管理プログラム、ジョブ管理方法及びジョブ管理装置
US10417281B2 (en) 2015-02-18 2019-09-17 Ab Initio Technology Llc Querying a data source on a network
CA2979066A1 (en) 2015-03-24 2016-09-29 Kyndi, Inc. Cognitive memory graph indexing, storage and retrieval
US20160342396A1 (en) * 2015-05-20 2016-11-24 Ab lnitio Technology LLC Visual program specification and compilation of graph-based computation
US10657134B2 (en) 2015-08-05 2020-05-19 Ab Initio Technology Llc Selecting queries for execution on a stream of real-time data
EP3335116B1 (en) * 2015-08-11 2024-10-23 AB Initio Technology LLC Data processing graph compilation
JP6273069B2 (ja) * 2015-09-03 2018-01-31 株式会社日立製作所 データ処理システムおよびデータ処理方法
US11151446B2 (en) 2015-10-28 2021-10-19 Google Llc Stream-based accelerator processing of computational graphs
CN108351983A (zh) * 2015-10-28 2018-07-31 谷歌有限责任公司 修改计算图
JP6584672B2 (ja) 2015-12-21 2019-10-02 アビニシオ テクノロジー エルエルシー サブグラフインターフェースの生成
CN109154897B (zh) * 2016-05-17 2022-01-21 起元技术有限责任公司 分布式处理方法、存储介质、和分布式处理系统
EP3559868A1 (en) * 2017-03-24 2019-10-30 Google LLC Device placement optimization with reinforcement learning
JP7216654B2 (ja) * 2017-03-29 2023-02-01 アビニシオ テクノロジー エルエルシー 可変レベル並列性を用いたデータ処理動作を行うためのシステム及び方法
US10817310B2 (en) 2017-09-01 2020-10-27 Ab Initio Technology Llc Executing graph-based program specifications
US11423083B2 (en) 2017-10-27 2022-08-23 Ab Initio Technology Llc Transforming a specification into a persistent computer program
US11188434B2 (en) 2017-12-08 2021-11-30 Ab Initio Technology Llc Systems and methods for monitoring execution of structured query language (SQL) queries
US10559276B2 (en) * 2018-02-03 2020-02-11 Facebook Technologies, Llc Apparatus, system, and method for mitigating motion-to-photon latency in head-mounted displays
CN110297699B (zh) * 2018-03-23 2021-09-14 华为技术有限公司 调度方法、调度器、存储介质及系统
US12032631B2 (en) 2018-05-30 2024-07-09 Ab Initio Technology Llc Systems and methods for dataflow graph optimization
US10978176B2 (en) 2018-06-29 2021-04-13 pulseData Inc. Machine learning systems and methods for predicting risk of renal function decline
US11093223B2 (en) 2019-07-18 2021-08-17 Ab Initio Technology Llc Automatically converting a program written in a procedural programming language into a dataflow graph and related systems and methods
GB202004594D0 (en) 2020-03-30 2020-05-13 Microsoft Technology Licensing Llc Partitioning for an execution pipeline
EP4285238A1 (en) 2021-01-31 2023-12-06 Ab Initio Technology LLC Data processing system with manipulation of logical dataset groups
WO2024086674A1 (en) * 2022-10-18 2024-04-25 The Regents Of The University Of California Systems and methods for subgraph matching using active learning

Family Cites Families (29)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS57153359A (en) * 1981-03-18 1982-09-21 Ibm Data processing system with common memory
US4972314A (en) * 1985-05-20 1990-11-20 Hughes Aircraft Company Data flow signal processor method and apparatus
JPH04227589A (ja) * 1990-08-10 1992-08-17 Sharp Corp データフロープログラムの割付け装置および割付け方法
US5694546A (en) * 1994-05-31 1997-12-02 Reisman; Richard R. System for automatic unattended electronic information transport between a server and a client by a vendor provided transport software with a manifest list
US5768594A (en) * 1995-07-14 1998-06-16 Lucent Technologies Inc. Methods and means for scheduling parallel processors
AU6501496A (en) * 1995-07-19 1997-02-18 Ascom Nexion Inc. Point-to-multipoint transmission using subqueues
US7028088B1 (en) * 1996-04-03 2006-04-11 Scientific-Atlanta, Inc. System and method for providing statistics for flexible billing in a cable environment
US5966072A (en) * 1996-07-02 1999-10-12 Ab Initio Software Corporation Executing computations expressed as graphs
US6330008B1 (en) * 1997-02-24 2001-12-11 Torrent Systems, Inc. Apparatuses and methods for monitoring performance of parallel computing
US6110220A (en) * 1997-02-24 2000-08-29 Lucent Technologies Inc. Concurrent hardware-software co-synthesis of hard real-time aperiodic and periodic specifications of embedded system architectures
US5933640A (en) * 1997-02-26 1999-08-03 Digital Equipment Corporation Method for analyzing and presenting test execution flows of programs
US5999729A (en) * 1997-03-06 1999-12-07 Continuum Software, Inc. System and method for developing computer programs for execution on parallel processing systems
US6088716A (en) * 1997-04-28 2000-07-11 Ab Initio Software Corporation Method for preventing buffer deadlock in dataflow computations
US6437796B2 (en) * 1998-02-17 2002-08-20 Sun Microsystems, Inc. Multiple processor visibility search system and method
US6675189B2 (en) * 1998-05-28 2004-01-06 Hewlett-Packard Development Company, L.P. System for learning and applying integrated task and data parallel strategies in dynamic applications
US6480876B2 (en) * 1998-05-28 2002-11-12 Compaq Information Technologies Group, L.P. System for integrating task and data parallelism in dynamic applications
US6101599A (en) * 1998-06-29 2000-08-08 Cisco Technology, Inc. System for context switching between processing elements in a pipeline of processing elements
SE515820C3 (sv) * 1998-09-01 2001-12-11 Ericsson Telefon Ab L M Mobiltelefonapparat och metod för vidarekoppling av samtal
US6983463B1 (en) * 1998-10-02 2006-01-03 Microsoft Corporation Network independent profiling of applications for automatic partitioning and distribution in a distributed computing environment
US6608628B1 (en) * 1998-11-06 2003-08-19 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration (Nasa) Method and apparatus for virtual interactive medical imaging by multiple remotely-located users
US6449711B1 (en) * 1999-02-04 2002-09-10 Sun Microsystems, Inc. Method, apparatus, and article of manufacture for developing and executing data flow programs
US6748440B1 (en) * 1999-05-12 2004-06-08 Microsoft Corporation Flow of streaming data through multiple processing modules
US20020129340A1 (en) * 1999-10-28 2002-09-12 Tuttle Douglas D. Reconfigurable isomorphic software representations
US6584581B1 (en) * 1999-12-06 2003-06-24 Ab Initio Software Corporation Continuous flow checkpointing data processing
US6848100B1 (en) * 2000-03-31 2005-01-25 Intel Corporation Hierarchical software path profiling
US6813761B1 (en) * 2000-06-30 2004-11-02 Microsoft Corporation Methods for enhancing flow analysis
GB2376094A (en) * 2001-05-30 2002-12-04 Ibm Flexible navigation of a workflow graph in a data processing system
JP3719509B2 (ja) * 2002-04-01 2005-11-24 株式会社ソニー・コンピュータエンタテインメント シリアル演算パイプライン、演算装置、算術論理演算回路およびシリアル演算パイプラインによる演算方法
US7167850B2 (en) * 2002-10-10 2007-01-23 Ab Initio Software Corporation Startup and control of graph-based computation

Also Published As

Publication number Publication date
KR20090018113A (ko) 2009-02-19
WO2007137034A3 (en) 2008-10-30
EP2021920A2 (en) 2009-02-11
AU2007253862B2 (en) 2012-07-12
EP2021920B1 (en) 2017-03-01
KR101413049B1 (ko) 2014-06-30
CN103778015B (zh) 2017-06-09
CN103778015A (zh) 2014-05-07
WO2007137034A2 (en) 2007-11-29
CA2650143A1 (en) 2007-11-29
AU2007253862A1 (en) 2007-11-29
CN101443733A (zh) 2009-05-27
AU2007253862C1 (en) 2013-03-21
WO2007137034A9 (en) 2009-01-15
EP2021920A4 (en) 2013-01-23
JP2014029718A (ja) 2014-02-13
HK1122627A1 (zh) 2009-05-22
US20070271381A1 (en) 2007-11-22
CN101443733B (zh) 2013-10-30
US7870556B2 (en) 2011-01-11
CA2650143C (en) 2017-06-13
JP2009537908A (ja) 2009-10-29

Similar Documents

Publication Publication Date Title
JP5940503B2 (ja) グラフ型計算における計算リソースの管理法
JP6815456B2 (ja) 複数ソースからのデータの処理
Wang et al. Gunrock: GPU graph analytics
Pautasso et al. Parallel computing patterns for grid workflows
US8239847B2 (en) General distributed reduction for data parallel computing
US9110706B2 (en) General purpose distributed data parallel computing using a high level language
AU2020210281A1 (en) Impact analysis
Raychev et al. Parallelizing user-defined aggregations using symbolic execution
JP2013528884A (ja) グラフに基づく計算の動的ロード
Groote et al. Modelling and analysing software in mCRL2
Van Antwerpen et al. Scope states: Guarding safety of name resolution in parallel type checkers
Bischl et al. Computing on high performance clusters with r: Packages batchjobs and batchexperiments
Melatti et al. Parallel and distributed model checking in eddy
AU2012241069B2 (en) Managing computing resources in graph-based computations
Liu et al. An empirical analysis on expressibility of vertex centric graph processing paradigm
Pautasso et al. Autonomic computing for virtual laboratories
JP7204011B2 (ja) コンピュータプログラムシステムの静的及び実行時分析
Guo et al. Efficient parallel graph trimming by arc-consistency
US10545965B2 (en) Data skew finding and analysis
Kroß Automatic Modeling and Simulating the Performance of Big Data Applications
Srivastava Exploring model parallelism in distributed scheduling of neural network frameworks
Sikora et al. Automated and dynamic abstraction of MPI application performance
CN118202331A (zh) 计算机程序的自动修改
Ferscha et al. Performance Prediction of Dynamic Task Structures With N-Map
DARROUS A Programming and Data Model for In-Situ frameworks

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20141114

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20150213

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20150513

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20151030

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20160201

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20160502

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20160518

R150 Certificate of patent or registration of utility model

Ref document number: 5940503

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250