JP5940503B2 - グラフ型計算における計算リソースの管理法 - Google Patents
グラフ型計算における計算リソースの管理法 Download PDFInfo
- 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
Links
- 238000007726 management method Methods 0.000 title description 2
- 238000012545 processing Methods 0.000 claims description 454
- 238000000034 method Methods 0.000 claims description 225
- 230000008569 process Effects 0.000 claims description 117
- 238000004364 calculation method Methods 0.000 claims description 97
- 238000011144 upstream manufacturing Methods 0.000 claims description 66
- 230000000694 effects Effects 0.000 claims description 21
- 230000001902 propagating effect Effects 0.000 claims description 13
- 238000004590 computer program Methods 0.000 claims description 11
- 230000004044 response Effects 0.000 claims description 10
- 230000006870 function Effects 0.000 description 46
- 239000000872 buffer Substances 0.000 description 12
- 230000006854 communication Effects 0.000 description 12
- 238000013500 data storage Methods 0.000 description 11
- 238000004891 communication Methods 0.000 description 10
- 238000013459 approach Methods 0.000 description 8
- 230000008901 benefit Effects 0.000 description 4
- 238000011161 development Methods 0.000 description 4
- 238000005192 partition Methods 0.000 description 4
- 230000003993 interaction Effects 0.000 description 3
- 230000007246 mechanism Effects 0.000 description 3
- 238000012544 monitoring process Methods 0.000 description 3
- 230000004913 activation Effects 0.000 description 2
- 230000003139 buffering effect Effects 0.000 description 2
- 230000008859 change Effects 0.000 description 2
- 238000006243 chemical reaction Methods 0.000 description 2
- 239000004615 ingredient Substances 0.000 description 2
- 230000000644 propagated effect Effects 0.000 description 2
- 230000001960 triggered effect Effects 0.000 description 2
- 238000009825 accumulation Methods 0.000 description 1
- 230000009471 action Effects 0.000 description 1
- 230000004931 aggregating effect Effects 0.000 description 1
- 230000002776 aggregation Effects 0.000 description 1
- 238000004220 aggregation Methods 0.000 description 1
- 238000004422 calculation algorithm Methods 0.000 description 1
- 230000015556 catabolic process Effects 0.000 description 1
- 238000013499 data model Methods 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000001914 filtration Methods 0.000 description 1
- 238000012905 input function Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000002360 preparation method Methods 0.000 description 1
- 238000004886 process control Methods 0.000 description 1
- 238000013515 script Methods 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
- 238000000638 solvent extraction Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements 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/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements 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/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5066—Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements 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/46—Multiprogramming arrangements
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T1/00—General 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
に関する。
図1を参照すると、グラフ型計算を実行するためのシステム100は、データ記憶装置102に連結される開発環境104、及び、データ記憶装置102に連結されるランタイム環境106を含む。開発者101は、開発環境102を用いてアプリケーションを構築する。アプリケーションは、開発者が開発環境を使用した結果としてデータ記憶装置に書き込むことができる「そのデータ記憶装置102内のデータ構造」により規定された一つ以上の計算グラフと関係付けられる。データ構造は、例えば、計算グラフの頂点(成分またはデータセット)及び頂点間のリンク(データの流れ)を規定する。そのデータ構造は、グラフの「成分、データセット、及び、データの流れ」の様々な特性を含むこともできる。データ処理アプリケーションは、例えば、一つ以上の入力データセットから処理成分のグラフを通して一つ以上の出力データセットまで流れるデータ上において実行される計算を実施する計算グラフと関係付けられ得る。
図2Aを参照すると、計算グラフ200の一例は、計算グラフ200の成分204A〜204Jによって処理される予定の一連のワーク要素を提供する入力データセット202を含む。例えば、データセット202は、「データベースシステム、又は、トランザクション処理システムのトランザクション」と関連する「データのレコード(記録)」を含むことができる。各成分は、計算グラフ200全体により定義される計算の一部と関係付けられる。ワーク要素(例えば、個々のデータのレコード)は、成分の一つ以上の入力ポートに入り、出力ワーク要素(場合によっては、入力ワーク要素であるか、又は、入力ワーク要素の処理されたバージョンである)は、一般的には成分の一つ以上の出力ポートから出る。グラフ200においては、成分204E、204G及び204Jからの出力ワーク要素が出力データセット206A〜206C内に格納される。
計算グラフを実行する手法の第1の形式においては、予備実行モジュール110は、各成分に対して別々の処理を割り当てる。例えば、「一成分につき一処理」の方法においては、1つの処理が各成分に対して割り当てられる。成分と対応する処理は、その成分により定義されるデータアクセス、計算、及び、データ変換タスクを取り扱う。実行モジュール112は、ホストのオペレーティングシステム内で処理を起動し、その成分の処理により実行されない計算グラフと関係付けられるタスクを取り扱う。
計算グラフを実行する手法の第2の形式においては、予備実行モジュール110は、随意的に、マルチ成分を実行するための幾つかのプロセスを割り当てる。例えば、「成分折畳み」法においては、予備実行モジュール110は、グラフの成分を、一つ以上の成分をそれぞれが含む一つ以上のセットに分割する。それぞれのセットには異なるプロセスが割り当てられる。従って、同一のセットに「一緒に折り畳まれた」成分に対しては、これらの成分により表される計算は同一の処理によって実行される。多数の成分を有するセットに対しては、実行モジュール112はホストのオペレーティングシステム内で「折り畳まれた処理」を起動する。
予備実行モジュール110は、グラフを解析して、同一のセット内にどの成分を一緒に折り畳むべきかを決定する。このとき、モジュール110は、随意的に、開発者101又はユーザ103による「折り畳まれるセットへの成分の手動による割当て」、もしくは、どの成分を同一又は別の折り畳まれるセットに入れるかに関する他の制約を考慮しながらグラフを解析する。予備実行モジュール110は、どの成分が一緒に折り畳まれるべきかを決定するために以下の制約を考慮することができる。幾つかの手順は、折り畳まれる処理が追加的な関連処理を取り扱うためのメカニズムを提供することにより、これら制約の一部又は全てを随意的に省略することができる。
図4は、グラフ成分を折り畳まれるセットに割り当てるために予備実行モジュール110により使用される例示の手順400のフローチャートを示す。手順400は、折り畳まれる各セットを可能な限り大きくするように試みる「欲張り(greedy)アルゴリズム」に基づく。この手順400により生成される折り畳まれるセットは、データの流れを、グラフの連結されたサブグラフの一つ以上の内部成分に提供する単一のルート成分を有する。折り畳まれるセットはオーバーラップもしていない。予備実行モジュール110は、例えば実行時間よりも十分前に、手順400を実行し、データ記憶装置102内にその結果を格納することができる。或いは、予備実行モジュール110は、グラフが実行モジュール112によって実行される直前において手順400を実行することができる。例えば、予備実行モジュール110は、グラフが実行される前のランタイムに手順400を実行することができるが、但し、より詳細に後述するように、条件付き成分がそのグラフから削除された後に手順400を実行することができる。
実行モジュール112は、予備実行モジュール110により識別された折り畳まれたセットと対応する折り畳まれた処理を開始する。予備実行モジュール110は、実行モジュール112に、それぞれの折り畳まれたセット内の成分及びこれらの成分を連結するデータの流れを識別する情報を提供する。実行モジュール112は、データ記憶装置102内の成分オブジェクトを指すポインタを含むランタイムデータ構造を生成し、折り畳まれたセット内の成分間で通信するためのワーク要素を格納する記憶空間を割り当てる。割り当てられる記憶空間の量及び成分間でワーク要素データを移動するために費やされる時間は、小さい値に維持され得る。異なる成分に対する計算が実行されている間に、折り畳まれたプロセスが同じ記憶空間にアクセスできるからである。
KEEP_GOING:このコードは供給されるべきデータが更にあることを示す。折り畳まれたプロセスは、「計算」関数を再度読み出すことにより応答する。
RMM116は、グラフの実行に関する情報を開発者101及び/又はユーザ103に提供する。RMM116は、グラフの個々の成分が実行中に一緒に折り畳まれた場合でも、それらの個々の成分のランタイム特性に関する情報を提供する。従って、グラフの成分と関係付けられる計算の特性は、その計算を実行する処理の数がそのグラフ内の成分の数と一致することを要求することなく、グラフの論理的構造に従って解析されることができる。例えば、RMM116は、成分折畳み手法又は一つの成分毎に一つのプロセス手法を用いて実行されるグラフに対する特性と概ね同じランタイム特性を表すことができる。
Claims (102)
- グラフ型計算を実行するための方法であって、
コンピュータが、データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップ;
前記コンピュータが、前記データ処理要素を複数のセットに分割するステップであって、少なくとも第1のセットは、前記計算グラフの連結有向サブグラフを形成する複数のデータ処理要素を含むステップ;
前記コンピュータが、それぞれのセットに異なる計算リソースを割り当てるステップであって、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含むステップ;
前記コンピュータが、前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含むステップであって、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にあるステップ;及び
前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播するステップ;
を含む方法。 - 請求項1に記載の方法において、
前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
方法。 - 請求項1に記載の方法において、
前記データを処理するステップは、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行するステップを含む、
方法。 - 請求項1に記載の方法において、
前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
方法。 - 請求項4に記載の方法において、
前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
方法。 - 請求項1に記載の方法において、
前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
方法。 - 請求項1に記載の方法において、
前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
方法。 - 請求項1に記載の方法において、
前記サブグラフはツリーを含む、
方法。 - 請求項1に記載の方法において、
セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
方法。 - 請求項1に記載の方法において、
前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するステップを更に含む、
方法。 - 請求項10に記載の方法において、
前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
方法。 - 請求項1に記載の方法において、
前記データ処理要素は、特定の並列処理段数を有する、
方法。 - 請求項12に記載の方法において、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
方法。 - 請求項1に記載の方法において、
前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
方法。 - 請求項14に記載の方法において、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
方法。 - グラフ型計算を実行するためのコンピュータプログラムを格納するコンピュータ読み取り可能記憶媒体であって、前記コンピュータプログラムは、
複数のデータ処理要素が複数のリンク要素により結合される計算グラフの仕様を受け取るステップ;
前記複数のデータ処理要素を複数のセットに分割するステップであって、少なくとも第1のセットは、前記計算グラフの連結有向サブグラフを形成する複数のデータ処理要素を含むステップ;
それぞれのセットに異なる計算リソースを割り当てるステップであって、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含むステップ;
前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素と対応する計算を実行することを含むステップであって、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にあるステップ;及び
前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播するステップ;
をコンピュータシステムに実行させる命令を含む、コンピュータ読み取り可能記憶媒体。 - グラフ型計算を実行するためのシステムであって、
予備実行モジュールであって、
データ処理要素がリンク要素により結合される計算グラフの仕様を受け取り、
前記データ処理要素を複数のセットに分割し、第1のセットは、前記計算グラフの連結有向サブグラフを形成する複数のデータ処理要素を含む、
ための電子回路を含む予備実行モジュールと、
実行モジュールであって、
それぞれのセットに異なる計算リソースを割り当て、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含み、
前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含む前記計算グラフに従ってデータを処理し、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にあり、
前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播する、
ための電子回路を含む実行モジュールと、
を含むシステム。 - グラフ型計算を実行するためのシステムであって、
データ処理要素がリンク要素により結合される計算グラフの仕様を受け取るための手段;
複数の前記データ処理要素を複数のセットに分割するための手段であって、第1のセットは、連結有向サブグラフを形成する複数の前記データ処理要素を含む手段;
それぞれのセットに異なる計算リソースを割り当てるための手段であって、1つのセットに割当てられる少なくとも1つの計算リソースが1つのプロセスを含む手段;
前記計算グラフに従ってデータを処理するための手段であって、前記割り当てられた計算リソースを用いて、前記データ処理要素と対応する計算を実行することを含む手段であって、前記データ処理要素の前記第1のセットに割り当てられた前記計算リソースの1つは、上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、下流データ処理要素と関係付けられる関数を呼び出すことにより、該下流データ処理要素の入力へと通過させ、前記上流データ処理要素及び前記下流データ処理要素は、前記データ処理要素の前記第1のセット内にある手段;及び
前記第1のセット内に上流データ処理要素を持たない前記第1のセット内のデータ処理要素に対する制御メッセージの受信に応答して、前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播する手段;
を含むシステム。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記データを処理するステップは、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行するステップを含む、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
コンピュータ読み取り可能記憶媒体。 - 請求項21に記載のコンピュータ読み取り可能記憶媒体において、
前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記データを処理するステップは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記サブグラフはツリーを含む、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するステップを更に含む、
コンピュータ読み取り可能記憶媒体。 - 請求項27に記載のコンピュータ読み取り可能記憶媒体において、
前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記データ処理要素は、特定の並列処理段数を有する、
コンピュータ読み取り可能記憶媒体。 - 請求項29に記載のコンピュータ読み取り可能記憶媒体において、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
コンピュータ読み取り可能記憶媒体。 - 請求項16に記載のコンピュータ読み取り可能記憶媒体において、
前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
コンピュータ読み取り可能記憶媒体。 - 請求項31に記載のコンピュータ読み取り可能記憶媒体において、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
コンピュータ読み取り可能記憶媒体。 - 請求項17に記載のシステムにおいて、
前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
システム。 - 請求項17に記載のシステムにおいて、
前記データを処理することは、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行することを含む、
システム。 - 請求項17に記載のシステムにおいて、
前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
システム。 - 請求項35に記載のシステムにおいて、
前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
システム。 - 請求項17に記載のシステムにおいて、
前記データを処理することは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納することを更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
システム。 - 請求項17に記載のシステムにおいて、
前記データを処理することは、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納することを更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
システム。 - 請求項17に記載のシステムにおいて、
前記サブグラフはツリーを含む、
システム。 - 請求項17に記載のシステムにおいて、
セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
システム。 - 請求項17に記載のシステムにおいて、
前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するための電子回路を更に含む、
システム。 - 請求項41に記載のシステムにおいて、
前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
システム。 - 請求項17に記載のシステムにおいて、
前記データ処理要素は、特定の並列処理段数を有する、
システム。 - 請求項43に記載のシステムにおいて、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
システム。 - 請求項17に記載のシステムにおいて、
前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
システム。 - 請求項45に記載のシステムにおいて、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
システム。 - 請求項18に記載のシステムにおいて、
前記リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる、
システム。 - 請求項18に記載のシステムにおいて、
前記データを処理するための手段は、前記複数のセットの内の少なくとも一つのセットに対し、そのセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、そのセット内の前記データ処理要素と対応する計算を実行するための手段を含む、
システム。 - 請求項18に記載のシステムにおいて、
前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
システム。 - 請求項49に記載のシステムにおいて、
前記上流データ処理要素と関係付けられる前記関数及び前記下流データ処理要素と関係付けられる前記関数が、前記データ処理要素の第1のセットに割り当てられた前記計算リソースの同一のプロセスにより呼び出される、
システム。 - 請求項18に記載のシステムにおいて、
前記データを処理するための手段は、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するための手段を更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素に従って処理されるデータ量を含む、
システム。 - 請求項18に記載のシステムにおいて、
前記データを処理するための手段は、それぞれのセット内の個々のデータ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するための手段を更に含み、
前記個々のアクティビティ量は、前記個々のデータ処理要素と対応する計算を実行するセットに割り当てられた計算リソースが費やす時間量を含む、
システム。 - 請求項18に記載のシステムにおいて、
前記サブグラフはツリーを含む、
システム。 - 請求項18に記載のシステムにおいて、
セット内のデータ処理要素における、複数の入力を有する各データ処理要素に対して、そのデータ処理要素の入力にリンクされる前記上流データ処理要素の全てもまた前記セット内にある、
システム。 - 請求項18に記載のシステムにおいて、
前記第1のセット内の他のデータ処理要素のそれぞれに前記制御メッセージを伝播することは、前記第1のセット内の他のデータ処理要素それぞれと関係付けられる関数を呼び出し、前記第1のセット内の前記各データ処理要素についての状態情報を不揮発性ストレージ内に保存してから、前記第1のセット内の外部に前記制御メッセージを伝播するための手段を更に含む、
システム。 - 請求項55に記載のシステムにおいて、
前記第1のセット内の前記データ処理要素毎の前記状態情報は、単一のファイルに保存される、
システム。 - 請求項18に記載のシステムにおいて、
前記データ処理要素は、特定の並列処理段数を有する、
システム。 - 請求項57に記載のシステムにおいて、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の並列処理段数を有する、
システム。 - 請求項18に記載のシステムにおいて、
前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
システム。 - 請求項59に記載のシステムにおいて、
1つのセット内の複数の前記データ処理要素のそれぞれは、同一の実行段階と関係付けられる、
システム。 - グラフ型計算を実行するための方法であって、
コンピュータが、データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップ;
各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定するステップであって、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができないステップ;
前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割するステップであって、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含むステップ;
前記データ処理要素の各セットに前記コンピュータの異なる計算リソースを割り当てるステップ;
前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含み、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にあるステップ;
を含む方法。 - 請求項61に記載の方法において、
少なくとも1つのデータ処理要素が折畳み可能であり、少なくとも1つのデータ処理要素が折畳み不可能であることを決定するステップを更に含む、
方法。 - 請求項61に記載の方法において、
前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
方法。 - 請求項61に記載の方法において、
前記データ処理要素の各セット内の各データ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するステップを更に含む、
方法。 - 請求項61に記載の方法において、
前記データを処理するステップは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行するステップを含む、
方法。 - 請求項61に記載の方法において、
前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
方法。 - 請求項66に記載の方法において、
前記上流データ処理要素と関係付けられた前記関数を呼び出すプロセスは、前記下流データ処理要素と関係付けられた前記関数を呼び出すプロセスである、
方法。 - 請求項61に記載の方法において、
複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
方法。 - 請求項61に記載の方法において、
前記データ処理要素のそれぞれは、特定の並列処理段数を有する、
方法。 - 請求項69に記載の方法において、
前記データ処理要素のセット内の全てのデータ処理要素は、同一の並列処理段数を有する、
方法。 - 請求項61に記載の方法において、
前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
方法。 - 請求項71に記載の方法において、
前記データ処理要素のセット内のデータ処理要素のそれぞれは、同一の実行段階と関係付けられる、
方法。 - 請求項61に記載の方法において、
前記計算グラフを分析して、前記データ処理要素の特徴に基づく制約を用いて、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定するステップを更に含む、
方法。 - 請求項73に記載の方法において、
前記制約は、どのデータ処理要素が折畳み可能であり、どのデータ処理要素が折畳み不可能であるかの制約を含む、
方法。 - 請求項73に記載の方法において、
予備実行モジュールが、前記計算グラフを解析して、前記グラフ型計算が実行される前に、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定する、
方法。 - 請求項73に記載の方法において、
前記データ処理要素の各セットを決定するステップは、折畳み可能ルートデータ処理要素を決定するステップ、及び前記セット内に既にある折畳み可能データ処理要素から直接下流にあるどの折畳み可能データ処理要素も前記セット内にあるように、追加のデータ処理要素を決定するステップを含む、
方法。 - グラフ型計算を実行するためのコンピュータプログラムを格納するコンピュータ読み取り可能記憶媒体であって、前記コンピュータプログラムは、
データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るステップであって、リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられるステップ;
各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定するステップであって、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができないステップ;
前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割するステップであって、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含むステップ;
前記データ処理要素の各セットにコンピュータシステムの異なる計算リソースを割り当てるステップ;
前記計算グラフに従ってデータを処理するステップであって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含み、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にあるステップ;
を前記コンピュータシステムに実行させる命令を含む、コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記コンピュータプログラムは、少なくとも1つのデータ処理要素が折畳み可能であり、少なくとも1つのデータ処理要素が折畳み不可能であることを決定するための命令を更に含む、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記コンピュータプログラムは、前記データ処理要素の各セット内の各データ処理要素と関係付けられる個々のアクティビティ量を特徴付ける情報を格納するための命令を更に含む、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記データを処理するステップは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行するステップを含む、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
コンピュータ読み取り可能記憶媒体。 - 請求項82に記載のコンピュータ読み取り可能記憶媒体において、
前記上流データ処理要素と関係付けられた前記関数を呼び出すプロセスは、前記下流データ処理要素と関係付けられた前記関数を呼び出すプロセスである、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記データ処理要素のそれぞれは、特定の並列処理段数を有する、
コンピュータ読み取り可能記憶媒体。 - 請求項85に記載のコンピュータ読み取り可能記憶媒体において、
前記データ処理要素のセット内の全てのデータ処理要素は、同一の並列処理段数を有する、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記計算グラフの仕様は、複数の前記データ処理要素のそれぞれと関係付けられる実行段階を示す、
コンピュータ読み取り可能記憶媒体。 - 請求項87に記載のコンピュータ読み取り可能記憶媒体において、
前記データ処理要素のセット内のデータ処理要素のそれぞれは、同一の実行段階と関係付けられる、
コンピュータ読み取り可能記憶媒体。 - 請求項77に記載のコンピュータ読み取り可能記憶媒体において、
前記計算グラフを分析して、前記データ処理要素の特徴に基づく制約を用いて、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定するステップを更に含む、
コンピュータ読み取り可能記憶媒体。 - 請求項89に記載のコンピュータ読み取り可能記憶媒体において、
前記制約は、どのデータ処理要素が折畳み可能であり、どのデータ処理要素が折畳み不可能であるかの制約を含む、
コンピュータ読み取り可能記憶媒体。 - 請求項89に記載のコンピュータ読み取り可能記憶媒体において、
予備実行モジュールが、前記計算グラフを解析して、前記グラフ型計算が実行される前に、どのデータ処理要素がデータ処理要素の同一のセットに分割されるべきかを決定する、
コンピュータ読み取り可能記憶媒体。 - 請求項89に記載のコンピュータ読み取り可能記憶媒体において、
前記データ処理要素の各セットを決定するステップは、折畳み可能ルートデータ処理要素を決定するステップ、及び前記セット内に既にある折畳み可能データ処理要素から直接下流にあるどの折畳み可能データ処理要素も前記セット内にあるように、追加のデータ処理要素を決定するステップを含む、
コンピュータ読み取り可能記憶媒体。 - グラフ型計算を実行するためのシステムであって、
予備実行モジュールであって、
データ処理要素がリンク要素により連結される計算グラフの仕様を受け取り、リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられ、
各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定し、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができず、
前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割し、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含む、
ための電子回路を含む予備実行モジュールと、
実行モジュールであって、
前記データ処理要素の各セットに前記システムの異なる計算リソースを割り当て、
前記計算グラフに従ってデータを処理し、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含み、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にある、
ための電子回路を含む実行モジュールと、
を含むシステム。 - 請求項93に記載のシステムにおいて、
前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
システム。 - 請求項93に記載のシステムにおいて、
前記データを処理することは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行することを含む、
システム。 - 請求項93に記載のシステムにおいて、
前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
システム。 - 請求項93に記載のシステムにおいて、
複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
システム。 - グラフ型計算を実行するためのシステムであって、
データ処理要素がリンク要素により連結される計算グラフの仕様を受け取るための手段であって、リンク要素のそれぞれは、上流データ処理要素の出力から下流データ処理要素の入力へのデータの流れと関係付けられる手段;
各データ処理要素が折畳み可能であるか折畳み不可能であるかを決定する手段であって、全ての折畳み可能データ処理要素は、前記折畳み可能データ処理要素の対応する計算を呼び出すために使用され得る特徴を含み、全ての折畳み不可能データ処理要素は、前記特徴と互換性がなく、前記折畳み不可能データ処理要素の対応する計算を呼び出すために前記特徴を使用することができない手段;
前記折畳み可能データ処理要素をデータ処理要素の1つ以上のセットに分割する手段であって、前記データ処理要素のセットの少なくとも1つは、複数の前記折畳み可能データ処理要素を含む手段;
前記データ処理要素の各セットに前記システムの異なる計算リソースを割り当てる手段;及び
前記計算グラフに従ってデータを処理する手段であって、前記割り当てられた計算リソースを用いて、前記データ処理要素に対応する計算を実行することを含む手段であって、前記データ処理要素のセットの1つに割り当てられた前記計算リソースの1つは、第1の折畳み可能上流データ処理要素の出力からのデータの流れと関係付けられるワーク要素を、折畳み可能下流データ処理要素と関係付けられる関数を呼び出すことにより、該折畳み可能下流データ処理要素の入力へと通過させ、前記第1の折畳み可能上流データ処理要素及び前記折畳み可能下流データ処理要素は、前記データ処理要素の同一のセット内にある手段;
を含むシステム。 - 請求項98に記載のシステムにおいて、
前記データ処理要素のセットに割り当てられる計算リソースの少なくとも1つが1つのプロセスを含む、
システム。 - 請求項98に記載のシステムにおいて、
前記データを処理することは、前記データ処理要素のセットの少なくとも1つに対し、前記データ処理要素のセット内の前記データ処理要素を結合するリンク要素により定義されるシーケンスに従って、前記データ処理要素のセット内の前記データ処理要素と対応する計算を実行することを含む、
システム。 - 請求項98に記載のシステムにおいて、
前記下流データ処理要素と関係付けられた前記関数は、前記上流データ処理要素と関係付けられる関数により前記ワーク要素が書き込まれた格納場所から、前記ワーク要素を読み出す、
システム。 - 請求項98に記載のシステムにおいて、
複数の入力を有する各データ処理要素のセット内のどのデータ処理要素についても、当該データ処理要素の入力にリンクされる前記上流データ処理要素の全てが、前記データ処理要素のセット内にもある、
システム。
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)
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)
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 |
-
2006
- 2006-05-16 US US11/434,623 patent/US7870556B2/en active Active
-
2007
- 2007-05-15 CN CN2007800170903A patent/CN101443733B/zh active Active
- 2007-05-15 JP JP2009511202A patent/JP2009537908A/ja active Pending
- 2007-05-15 CA CA2650143A patent/CA2650143C/en active Active
- 2007-05-15 CN CN201310424248.6A patent/CN103778015B/zh active Active
- 2007-05-15 KR KR1020087030136A patent/KR101413049B1/ko active IP Right Grant
- 2007-05-15 EP EP07783766.4A patent/EP2021920B1/en active Active
- 2007-05-15 AU AU2007253862A patent/AU2007253862C1/en active Active
- 2007-05-15 WO PCT/US2007/068946 patent/WO2007137034A2/en active Application Filing
-
2009
- 2009-03-27 HK HK09102924.8A patent/HK1122627A1/zh unknown
-
2013
- 2013-09-27 JP JP2013201721A patent/JP5940503B2/ja active Active
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 |