(57)【特許請求の範囲】
【請求項１】
コンピュータが、サービスリクエストを、そのサービスと関連付けられていて渡されるレコードのデータフローを表すリンクによって接続されるノードを含む計算グラフに従って処理するステップを含む方法であって、この処理するステップは、
サービスクライアントから前記計算グラフのための複数のレコードを受信するステップと、
前記複数のレコードの各々を前記計算グラフのパーティションノードに提供するステップと、
前記パーティションノードで、各レコードに対して規定されるアクションの種類に基づいて、前記複数のレコードを複数のセットにパーティション化するステップと、
前記複数のセットの各々に対して、前記計算グラフに含まれるサブグラフの１つを割り当てるステップであって、前記サブグラフの各々は、前記計算グラフの前記ノード及び前記リンクの少なくとも一部を含む、ステップと、
前記複数のレコードの各レコードに対して、利用可能であると識別されたインスタンスのプールから、前記レコードを含む前記セットに割り当てられた前記サブグラフの前記ノードに関連付けられたプロセスのインスタンスを割り当てるステップと、
前記計算グラフの前記サブグラフから出力を受け取るステップと、
前記サービスクライアントに前記出力を提供するステップと、を含む方法。
【請求項２】
前記複数のレコードを受信するステップは、
前記サービスクライアントからのカプセル化されたリクエストから前記複数のレコードを抽出するステップを含み、および
前記計算グラフに前記複数のレコードの各々を提供するステップは、
リクエスト識別子を前記サービスリクエストと関連付けるステップと、
前記複数のレコードの各々に含まれるワーク要素を前記計算グラフへ提供するステップと、
前記リクエスト識別子を前記ワーク要素と関連付けるステップと、
前記リクエスト識別子と前記ワーク要素との関連付けを出力ノードに通信するステップとを含む、請求項１の方法。
【請求項３】
前記出力を受け取るステップは、
前記計算グラフからの出力を含むワーク要素を受け取るステップと、
前記ワーク要素と関連付けられるリクエスト識別子を識別するステップと、を含み、
前記サービスクライアントへ出力を提供するステップは、
前記リクエスト識別子が識別する前記サービスリクエストと対応するカプセル化された応答内に前記出力を組み込むステップを含み、前記カプセル化された応答は前記ワーク要素に含まれる前記出力を含む、請求項１の方法。
【請求項４】
前記サービスクライアントに前記出力を提供するステップは、カプセル化されたＳＯＡＰ応答内に前記出力を組み込むステップを含む、請求項１の方法。
【請求項５】
前記複数のレコードの各々は、１つ以上のワーク要素を含む、請求項１の方法。
【請求項６】
前記複数のレコードの各々は、カプセル化されたＳＯＡＰレコードに含まれる、請求項１の方法。
【請求項７】
各レコードを、それぞれ割り当てられた前記サブグラフのインスタンスを用いて、他のレコードに対して任意の順序で処理するステップを更に含む、請求項１の方法。
【請求項８】
前記複数のレコードの１つに対して、前記複数のレコードの別の１つが前記サブグラフからの出力として受信される前に、前記サブグラフの前記インスタンスの１つが割り当てられる、請求項１の方法。
【請求項９】
前記計算グラフ内の異なるサブグラフの少なくとも１つは、外部サービスとして呼び出される、請求項１の方法。
【請求項１０】
前記計算グラフは、前記サービスクライアントで動作しているクライアント計算グラフにノードとして参加する、請求項１の方法。
【請求項１１】
前記計算グラフは有向データフローグラフであり、前記計算グラフの頂点は、データ又はプロセスに対応するノードを表し、前記計算グラフのリンクは、ノード間のデータの流れを示し、前記計算グラフの各サブグラフは、前記計算グラフの前記ノード及び前記リンクの全てより少ないサブセットを含む、請求項１の方法。
【請求項１２】
前記複数のレコードは、前記サービスクライアントからのリクエストを処理するウェブサービスプラグインによって受信される、請求項１の方法。
【請求項１３】
第２のサービスクライアントから前記計算グラフのための前記複数のレコードを受信するステップと、
前記第２のサービスクライアントからの前記複数のレコードを前記計算グラフに提供するステップと、
前記計算グラフの前記サブグラフから第２のサービスリクエストに対する第２出力を受け取るステップと、
前記第２のサービスクライアントに前記第２出力を提供するステップと、により、前記計算グラフに基づいて前記第２のサービスリクエストを処理するステップと、
前記計算グラフにおいて、前記サービスクライアントからの前記複数のレコードと、前記第２のサービスクライアントからの前記複数のレコードとを並列に処理するステップと、を更に含む請求項１の方法。
【請求項１４】
前記サービスクライアントからの前記複数のレコードと、前記第２のサービスクライアントからの前記複数のレコードとを並列に処理するステップは、
前記サービスクライアントからの前記複数のレコードを前記計算グラフの第１サブグラフで処理するステップと、
前記第２のサービスクライアントからの前記複数のレコードを前記計算グラフの第２サブグラフで処理するステップと、
前記第１サブグラフから第１出力を受け取るステップと、
前記第２サブグラフから第２出力を受け取るステップと、を含み、
前記第１サブグラフおよび前記第２サブグラフは、同時に実行される、請求項１３の方法。
【請求項１５】
前記サービスクライアントからの前記複数のレコードと、前記第２のサービスクライアントからの前記複数のレコードとを並列に処理するステップは、
サブグラフの第１インスタンスを利用可能であると識別するステップと、
前記サブグラフの前記第１インスタンスで前記サービスクライアントからの前記複数のレコードを処理するステップと、
前記サブグラフの第２インスタンスを利用可能であると識別するステップと、
前記サブグラフの前記第２インスタンスで前記第２のサービスクライアントからの前記複数のレコードを処理するステップと、
前記第１インスタンスから第１出力を受け取るステップと、
前記第２インスタンスから第２出力を受け取るステップと、を含み、
前記サブグラフの前記第１インスタンスおよび前記サブグラフの前記第２インスタンスは、同時に実行される、請求項１３の方法。
【請求項１６】
サービスと関連付けられる計算グラフに従ってサービスリクエストを処理するためのシステムであって、前記計算グラフが、ノード間で渡されるレコードのデータフローを表すリンクによって接続されるノードを含み、
サービスクライアントから前記計算グラフのための複数のレコードを受信するための手段と、
前記複数のレコードの各々を前記計算グラフのパーティションノードに提供するよう構成されるプロセッサと、
前記パーティションノードで、各レコードに対して規定されるアクションの種類に基づいて、前記複数のレコードを複数のセットにパーティション化する手段と、
前記複数のセットの各々に対して、前記計算グラフに含まれるサブグラフの１つを割り当てる手段であって、前記サブグラフの各々は、前記計算グラフの前記ノード及び前記リンクの少なくとも一部を含む、手段と、
前記複数のレコードの各レコードに対して、利用可能であると識別されたインスタンスのプールから、前記レコードを含む前記セットに割り当てられた前記サブグラフの前記ノードに関連付けられたプロセスのインスタンスを割り当てる手段と、
前記計算グラフの前記サブグラフから出力を受け取るための手段と、
前記サービスクライアントに前記出力を提供するための手段と、を含むシステム。
【請求項１７】
サービスと関連付けられる計算グラフに従ってサービスリクエストを処理するためのコンピュータ読み取り可能媒体に格納されたコンピュータープログラムであって、前記計算グラフが、ノード間で渡されるレコードのデータフローを表すリンクによって接続されるノードを含み、
前記コンピュータープログラムは、
サービスクライアントから前記計算グラフのための複数のレコードを受信するステップと、
前記複数のレコードの各々を前記計算グラフのパーティションノードに提供するステップと、
前記パーティションノードで、各レコードに対して規定されるアクションの種類に基づいて、前記複数のレコードを複数のセットにパーティション化するステップと、
前記複数のセットの各々に対して、前記計算グラフに含まれるサブグラフの１つを割り当てるステップであって、前記サブグラフの各々は、前記計算グラフの前記ノード及び前記リンクの少なくとも一部を含む、ステップと、
前記複数のレコードの各レコードに対して、利用可能であると識別されたインスタンスのプールから、前記レコードを含む前記セットに割り当てられた前記サブグラフの前記ノードに関連付けられたプロセスのインスタンスを割り当てるステップと、
前記計算グラフの前記サブグラフから出力を受け取るステップと、
前記サービスクライアントに前記出力を提供するステップと、をコンピュータに実行させる命令を含む、コンピュータープログラム。
【請求項１８】
前記複数のレコードを受信するステップは、
前記サービスクライアントからのカプセル化されたリクエストから前記複数のレコードを抽出するステップを含み、および
前記計算グラフに前記複数のレコードの各々を提供するステップは、
リクエスト識別子を前記サービスリクエストと関連付けるステップと、
前記複数のレコードの各々に含まれるワーク要素を前記計算グラフへ提供するステップと、
前記リクエスト識別子を前記ワーク要素と関連付けるステップと、
前記リクエスト識別子と前記ワーク要素との関連付けを出力ノードに通信するステップとを含む、請求項１７のコンピュータープログラム。
【請求項１９】
前記出力を受け取るステップは、
前記計算グラフからの出力を含むワーク要素を受け取るステップと、
前記ワーク要素と関連付けられるリクエスト識別子を識別するステップと、を含み、
前記サービスクライアントへ出力を提供するステップは、
前記リクエスト識別子が識別する前記サービスリクエストと対応するカプセル化された応答内に前記出力を組み込むステップを含み、前記カプセル化された応答は前記ワーク要素に含まれる前記出力を含む、請求項１７のコンピュータープログラム。
【請求項２０】
前記サービスクライアントに前記出力を提供するステップは、カプセル化されたＳＯＡＰ応答内に前記出力を組み込むステップを含む、請求項１７のコンピュータープログラム。
【請求項２１】
前記複数のレコードの各々は、１つ以上のワーク要素を含む、請求項１７のコンピュータープログラム。
【請求項２２】
前記複数のレコードの各々は、カプセル化されたＳＯＡＰレコードに含まれる、請求項１７のコンピュータープログラム。
【請求項２３】
各レコードを、それぞれ割り当てられた前記サブグラフのインスタンスを用いて、他のレコードに対して任意の順序で処理するステップを前記コンピュータに実行させる命令を更に含む、請求項１７のコンピュータープログラム。
【請求項２４】
前記複数のレコードの１つに対して、前記複数のレコードの別の１つが前記サブグラフからの出力として受信される前に、前記サブグラフの前記インスタンスの１つが割り当てられる、請求項１７のコンピュータープログラム。
【請求項２５】
前記計算グラフ内の異なるサブグラフの少なくとも１つは、外部サービスとして呼び出される、請求項１７のコンピュータープログラム。
【請求項２６】
前記計算グラフは、前記サービスクライアントで動作しているクライアント計算グラフにノードとして参加する、請求項１７のコンピュータープログラム。
【請求項２７】
前記計算グラフは有向データフローグラフであり、前記計算グラフの頂点は、データ又はプロセスに対応するノードを表し、前記計算グラフのリンクは、ノード間のデータの流れを示し、前記計算グラフの各サブグラフは、前記計算グラフの前記ノード及び前記リンクの全てより少ないサブセットを含む、請求項１７のコンピュータープログラム。
【請求項２８】
前記複数のレコードは、前記サービスクライアントからのリクエストを処理するウェブサービスプラグインによって受信される、請求項１７のコンピュータープログラム。
【請求項２９】
第２のサービスクライアントから前記計算グラフのための前記複数のレコードを受信するステップと、
前記第２のサービスクライアントからの前記複数のレコードを前記計算グラフに提供するステップと、
前記計算グラフの前記サブグラフから第２のサービスリクエストに対する第２出力を受け取るステップと、
前記第２のサービスクライアントに前記第２出力を提供するステップと、により、前記計算グラフに基づいて前記第２のサービスリクエストを処理するステップと、
前記計算グラフにおいて、前記サービスクライアントからの前記複数のレコードと、前記第２のサービスクライアントからの前記複数のレコードとを並列に処理するステップと、を前記コンピュータに実行させるための命令を更に含む請求項１７のコンピュータープログラム。
【請求項３０】
前記サービスクライアントからの前記複数のレコードと、前記第２のサービスクライアントからの前記複数のレコードとを並列に処理するステップは、
前記サービスクライアントからの前記複数のレコードを前記計算グラフの第１サブグラフで処理するステップと、
前記第２のサービスクライアントからの前記複数のレコードを前記計算グラフの第２サブグラフで処理するステップと、
前記第１サブグラフから第１出力を受け取るステップと、
前記第２サブグラフから第２出力を受け取るステップと、を含み、
前記第１サブグラフおよび前記第２サブグラフは、同時に実行される、請求項２９のコンピュータープログラム。
【請求項３１】
前記サービスクライアントからの前記複数のレコードと、前記第２のサービスクライアントからの前記複数のレコードとを並列に処理するステップは、
サブグラフの第１インスタンスを利用可能であると識別するステップと、
前記サブグラフの前記第１インスタンスで前記サービスクライアントからの前記複数のレコードを処理するステップと、
前記サブグラフの第２インスタンスを利用可能であると識別するステップと、
前記サブグラフの前記第２インスタンスで前記第２のサービスクライアントからの前記複数のレコードを処理するステップと、
前記第１インスタンスから第１出力を受け取るステップと、
前記第２インスタンスから第２出力を受け取るステップと、を含み、
前記サブグラフの前記第１インスタンスおよび前記サブグラフの前記第２インスタンスは、同時に実行される、請求項２９のコンピュータープログラム。
【請求項３２】
コンピュータが、データフローを表すリンクによって接続されるノードを含む計算グラフに従って、複数のワーク要素を含むレコードを処理する方法であって、
前記計算グラフのパーティションノードで、各ワーク要素で実行される処理の種類に基づいて、前記複数のワーク要素を複数のセットにパーティション化するステップと、
前記複数のセットのうちの第１セットの第１ワーク要素に対して、利用可能であると識別されたインスタンスのプールから、前記計算グラフのサブグラフのノードに関連付けられたプロセスの第１インスタンスを割り当てるステップであって、前記サブグラフは、前記計算グラフの前記ノード及び前記リンクの少なくとも一部を含み、前記インスタンスは、前記サブグラフの前記ノード及び前記リンクを含む、ステップと、
前記サブグラフの前記第１インスタンスによって、前記レコードの前記第１ワーク要素を処理するステップと、
前記複数のセットのうちの前記第１セットの第２ワーク要素に対して、利用可能であると識別された前記サブグラフの前記インスタンスの前記プールから、第２インスタンスを割り当てるステップと、
前記サブグラフの前記第２インスタンスによって、前記レコードの前記第２ワーク要素を処理するステップと、
前記第１インスタンスから第１出力ワーク要素を受け取るステップと、
前記第２インスタンスから第２出力ワーク要素を受け取るステップと、
前記第１出力ワーク要素を前記レコードと関連付けるステップと、
前記第２出力ワーク要素を前記レコードと関連付けるステップと、を含み、
前記サブグラフの前記第１インスタンスおよび前記サブグラフの前記第２インスタンスを少なくとも部分的に同時に実行する方法。
【請求項３３】
前記計算グラフは有向データフローグラフであり、前記計算グラフの頂点は、データ又はプロセスに対応するノードを表し、前記計算グラフのリンクは、ノード間のデータの流れを示し、前記サブグラフは、前記計算グラフの前記ノード及び前記リンクの全てより少ないサブセットを含む、
請求項３２の方法。
【請求項３４】
データフローを表すリンクによって接続されるノードを含む計算グラフに従って、複数のワーク要素を含むレコードを処理するためのシステムであって、
前記計算グラフのパーティションノードで、各ワーク要素で実行される処理の種類に基づいて、前記複数のワーク要素を複数のセットにパーティション化するための手段と、
前記複数のセットのうちの第１セットの第１ワーク要素に対して、利用可能であると識別されたインスタンスのプールから、前記計算グラフのサブグラフのノードに関連付けられたプロセスの第１インスタンスを割り当てるための手段であって、前記サブグラフは、前記計算グラフの前記ノード及び前記リンクの少なくとも一部を含み、前記インスタンスは、前記サブグラフの前記ノード及び前記リンクを含む、手段と、
前記複数のセットのうちの前記第１セットの第２ワーク要素に対して、利用可能であると識別された前記サブグラフの前記インスタンスの前記プールから、第２インスタンスを割り当てるための手段と、
前記サブグラフの前記第１インスタンスによって、前記レコードの前記第１ワーク要素を処理し、前記サブグラフの前記第２インスタンスによって、前記レコードの前記第２ワーク要素を処理するよう構成された第１プロセッサと、
前記第１インスタンスから第１出力ワーク要素を受け取るための手段と、
前記第２インスタンスから第２出力ワーク要素を受け取るための手段と、
前記第１出力ワーク要素を前記レコードと関連付け、前記第２出力ワーク要素を前記レコードと関連付けるよう構成された第２プロセッサと、を含み、
前記第１プロセッサは、前記サブグラフの前記第１インスタンスおよび前記サブグラフの前記第２インスタンスを少なくとも部分的に同時に実行するよう構成されている、システム。
【請求項３５】
データフローを表すリンクによって接続されるノードを含む計算グラフに従って、複数のワーク要素を含むレコードを処理するためのコンピュータ読み取り可能媒体に格納されたコンピュータープログラムであって、
前記コンピュータープログラムは、
前記計算グラフのパーティションノードで、各ワーク要素で実行される処理の種類に基づいて、前記複数のワーク要素を複数のセットにパーティション化するステップと、
前記複数のセットのうちの第１セットの第１ワーク要素に対して、利用可能であると識別されたインスタンスのプールから、前記計算グラフのサブグラフのノードに関連付けられたプロセスの第１インスタンスを割り当てるステップであって、前記サブグラフは、前記計算グラフの前記ノード及び前記リンクの少なくとも一部を含み、前記インスタンスは、前記サブグラフの前記ノード及び前記リンクを含む、ステップと、
前記サブグラフの前記第１インスタンスによって、前記レコードの前記第１ワーク要素を処理するステップと、
前記複数のセットのうちの前記第１セットの第２ワーク要素に対して、利用可能であると識別された前記サブグラフの前記インスタンスの前記プールから、第２インスタンスを割り当てるステップと、
前記サブグラフの前記第２インスタンスによって、前記第２ワーク要素を処理するステップと、
前記第１インスタンスから第１出力ワーク要素を受け取るステップと、
前記第２インスタンスから第２出力ワーク要素を受け取るステップと、
前記第１出力ワーク要素を前記レコードと関連付けるステップと、
前記第２出力ワーク要素を前記レコードと関連付けるステップと、をコンピュータに実行させる命令を含み、
前記命令が、前記サブグラフの前記第１インスタンスおよび前記サブグラフの前記第２インスタンスを、コンピュータに少なくとも部分的に同時に実行させるコンピュータープログラム。
【請求項３６】
前記計算グラフは有向データフローグラフであり、前記計算グラフの頂点は、データ又はプロセスに対応するノードを表し、前記計算グラフのリンクは、ノード間のデータの流れを示し、前記サブグラフは、前記計算グラフの前記ノード及び前記リンクの全てより少ないサブセットを含む、
請求項３５のコンピュータープログラム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
優先権主張
本願は、２００６年８月１０日出願の特許仮出願第６０／８３６，７４５号の優先権を主張し、その全文を引用して本明細書に組み込む。
【０００２】
技術分野
本発明はグラフ型計算の分散サービスに関する。
【０００３】
発明の背景
複雑なビジネスシステムでは多くの段階でデータ処理するのが典型的であり、ある段階で得られた結果は次の段階に送られる。このようなシステムを通る情報の全体の流れは、有向データフローグラフとして記述することができ、そのグラフの頂点はコンポーネント（データファイルまたはプロセッサのいずれか）を表わし、グラフのリンクつまり、「辺」はコンポーネント間のデータフローを示す。
【０００４】
グラフを用いて、計算を直接呼び出すこともできる。マサチュセッツ州ＬｅｘｉｎｇｔｏｎのＡｂ  Ｉｎｉｔｉｏ  Ｓｏｆｔｗａｒｅ  Ｃｏｒｐｏｒａｔｉｏｎが提供するグラフ開発環境（ＧＤＥ）による「ＣＯ＞ＯＰＥＲＡＴＩＮＧ  ＳＹＳＴＥＭ（登録商標）」は、このようなシステムを具現化している。このシステムにより作成されるグラフは、グラフコンポーネントにより表される個々のプロセスの入出力情報を取得して、プロセス間で情報を移動させ、そしてプロセスの実行順序を定義するための方法を提供する。このシステムは、プロセス間の通信法を選択するアルゴリズム、およびプロセス実行をスケジュール化するアルゴリズムを含み、グラフ実行の監視も提供する。
【０００５】
分散型サービスのアーキテクチャにより、コンピュータープログラムは、例えば、ワールドワイドウェブ等のネットワークインターフェースを通じて他のプログラムの機能にアクセスすることができ、他のプログラムの機能を自身のオペレーティングコードに組み込む必要がなくなる。
【０００６】
発明の概要
全体として、一態様では、サービスリクエストは、サービスクライアントからの計算グラフの入力を受信するステップ、その入力をデータフローのレコードとして計算グラフに提供するステップ、計算グラフから出力を受け取るステップ、およびサービスクライアントにその出力を提供するステップにより、そのサービスと関連する計算グラフに基づき処理される。
【０００７】
実装には以下の特徴の内の一つ以上が含まれる。
【０００８】
入力を受信するステップは、サービスクライアントからのサービスリクエスト内の入力を識別するステップを含み、計算グラフにその入力を提供するステップは、リクエスト識別子をサービスリクエストと関連付けるステップ、計算グラフへの入力を含むワーク要素を提供するステップ、リクエスト識別子をワーク要素と関連付けるステップ、およびリクエスト識別子とワーク要素との関連付けを出力ノードに通信するステップを含む。入力を識別するステップは、カプセル化されたリクエストから入力を抽出するステップを含む。カプセル化されたリクエストはＳＯＡＰリクエストを含む。出力を受け取るステップは、計算グラフからの出力を含むワーク要素を受け取るステップ、およびワーク要素と関連付けられるリクエスト識別子を識別するステップを含み、サービスクライアントへ出力を提供するステップは、リクエスト識別子が識別するサービスリクエストと対応するサービス応答を生成するステップを含み、サービス応答はワーク要素に含まれる出力を含む。サービス応答を生成するステップは、カプセル化された応答内に出力を組み込むステップを含む。カプセル化された応答はＳＯＡＰ応答を含む。
【０００９】
第２のサービスリクエストは、第２のサービスクライアントから計算グラフの第２入力を受信するステップ、第２入力を第２データフローのレコードとして計算グラフに提供するステップ、計算グラフから第２出力を受け取るステップ、および第２のサービスクライアントに第２出力を提供するステップにより計算グラフに基づいて処理され；計算グラフでは、第１入力および第２入力を並列処理する。第１入力および第２入力を並列処理するステップは、第１入力に適用可能な第１サブグラフを識別するステップ、第１入力を第１サブグラフで処理するステップ、第２入力に適用可能な第２サブグラフを識別するステップ、第２入力を第２サブグラフで処理するステップ、第１サブグラフから第１出力を受け取るステップ、および第２サブグラフから第２出力を受け取るステップを含み、第１サブグラフおよび第２サブグラフを同時に実行する。第１入力および第２入力を並列処理するステップは、サブグラフの第１インスタンスを利用可能であると識別するステップ、サブグラフの第１インスタンスで第１入力を処理するステップ、サブグラフの第２インスタンスを利用可能であると識別するステップ、サブグラフの第２インスタンスで第２入力を処理するステップ、第１インスタンスから第１出力を受け取るステップ、および第２インスタンスから第２出力を受け取るステップを含み、サブグラフの第１インスタンスおよびサブグラフの第２インスタンスを同時に実行する。
【００１０】
一般に、一態様では、データフローは、データフローの第１レコードに適用可能な第１グラフを識別するステップ、第１レコードの第１ワーク要素に適用可能な第１サブグラフを識別するステップ、第１サブグラフ内で第１ワーク要素を処理するステップ、第１レコードの第２ワーク要素に適用可能な第２サブグラフを識別するステップ、第２サブグラフ内で第２ワーク要素を処理するステップ、第１サブグラフから第１出力ワーク要素を受け取るステップ、第２サブグラフから第２出力ワーク要素を受け取るステップ、第１出力ワーク要素を第１レコードと関連付けるステップ、および第２出力ワーク要素を第１レコードと関連付けるステップにより、グラフ型計算で処理され、第１サブグラフおよび第２サブグラフを少なくとも部分的に同時に実行する。
【００１１】
一般に、一態様では、データフローは、データフローの第１レコードに適用可能な第１グラフを識別するステップ、サブグラフの第１インスタンスを利用可能であると識別するステップ、サブグラフの第１インスタンス内で、第１レコードの第１ワーク要素を処理するステップ、サブグラフの第２インスタンスを利用可能であると識別するステップ、サブグラフの第２インスタンス内で、第１レコードの第２ワーク要素を処理するステップ、第１インスタンスから第１出力ワーク要素を受け取るステップ、第２インスタンスから第２出力ワーク要素を受け取るステップ、第１出力ワーク要素を第１レコードと関連付けるステップ、および第２出力ワーク要素を第１レコードと関連付けるステップにより、グラフ型計算で処理され、サブグラフの第１インスタンスおよびサブグラフの第２インスタンスを少なくとも部分的に同時に実行する。
【００１２】
本発明の他の特徴および利点は、本説明およびクレームから明らかとなろう。
【図面の簡単な説明】
【００１３】
【図１Ａ】分散型サービスシステムの略図を示す。
【図１Ｂ】サービスを呼び出すためのプロセスのフロー図を示す。
【図２】分散型サービスシステムの略図を示す。
【図３ａ】分散型サービスを提供するためのグラフを示す。
【図３ｂ】分散型サービスを提供するためのグラフを示す。
【図４】分散型サービスを提供するためのグラフを示す。
【図５ａ】分散型サービスを提供するためのグラフを示す。
【図５ｂ】分散型サービスを提供するためのグラフを示す。
【００１４】
発明の説明
実施例によっては、グラフ型計算を分散型サービスと相互作用させる二つの方法がある。実施例によっては、グラフがサービスを「呼び出し」、そのサービスがあたかもグラフ内のノードであるかのように、そのサービスと関連付けられる。他の実施例では、アプリケーションがグラフと関連付けられて、そのグラフがサービスを「提供する」。これら二つの事例は同時に実行することができる。例えば、あるアプリケーションにサービスを提供しているグラフが、別のサービスをそれ自体で呼び出して、その計算の一部を実行することができる。あるグラフが呼び出すサービスを別のグラフが提供できるので、第１グラフが、例えば、サブグラフとして第２グラフを含むのではなく、第２グラフを呼び出すことができるようになる。
【００１５】
実施例によっては、図１Ａに示すように、グラフ型計算１００のサービスノード１０２は、分散型サービス指向のアーキテクチャでサービスを呼び出すことにより動作する。すなわち、サービスノード１０２を実行する場合、グラフ１００の外部にあるサービス１０８をサービスのクライアントとして呼び出す。例えば、サービスノード１０２は、ＳＯＲＰ、ＨＴＴＰ、ＸＭＬ、ＷＳＤＬ等の内の一つ以上の組み合せを用いてウェブサービスにアクセスし、アプリケーションサーバ１０６上でホストされるウェブサービスプラグイン１０４と通信し、外部サービス１０８に到達することができる。外部サービス１０８は、以下に説明するように、それ自体をグラフ型計算とすることができる。このサービスは、多様な分散型計算タスクの方法のどれかを用いた分散様式で実装することができる。
【００１６】
サービスノード１０２は、他のグラフノード、例えば、ノード１１２から、Ａｂ ＩｎｉｔｉｏのＤＭＬのようなデータ記述言語で記述されたレコード等の、グラフ型計算１００の本来のフォーマットで入力１１０を受け取る。次いで、ノード１０２は、その入力１１０を、ＳＯＡＰまたは他の形式のカプセル型リクエスト等の、そのノードが使用するウェブサービスの形式に適合するフォーマットに変換し、サービスリクエスト１１４をアプリケーションサーバ１０６に送信する。リクエスト１１４内のＵＲＬは、そのリクエストを送信するアプリケーションサーバ１０６、プラグイン１０４、およびサービス１０８がどれであるかを指示する。リクエスト１１４は、ＨＴＴＰおよびＲＰＣ（リモート手続き呼出し）を含む様々な方法で送信することができる。サーバ１０６上のプラグイン１０４は、入ってくるリクエスト１１４を適切に再フォーマットし、外部サービス１０８に、適切な呼出し１１６を送信する。
【００１７】
サービス１０８は呼び出された操作が何であれそれを実行してから、プラグイン１０４に出力１１８を戻す。プラグイン１０４は、サービス１０８の出力１１８を適切なサービス応答１２０に再フォーマットして、サービスノード１０２に戻す。サービスノード１０２は応答１２０を適切な出力フォーマットに再フォーマットして、下流のグラフノード、例えばノード１２２、に出力１２１を渡す。他のグラフノード１１２、１２２、１２４、１２６の観点からは、分散サービスノード１０２は他のノードと同様、グラフ計算１００に参加することができる。プラグイン１０４の、性質およびサービス１０８への通信方法（または、例えば、プラグイン１０４がそもそも使用されるのかどうか）等の、サーバ１０６の構造および編成は、予測している形式の応答１２０をサービスノード１０２が受信する限り、グラフノードにとって重要ではない。サーバ１０６、プラグイン１０４、およびサービス１０８は、後述するように、それら自体をそれぞれグラフ型計算のサーバ、プラグイン、およびグラフとすることができる。
【００１８】
実施例によっては、グラフ１００はパイプライン化されるが、その意味は、パイプラインの各シーケンス段において、規模の大きな入力レコードフローの内の別々のレコード、または別々のレコードセットに、各ノードが作用するということである。所与の段階で、後続のノードはそれぞれ、前のノードから受け取ったレコードまたはレコードのセットに作用し、一方、前のノードは、入力フロー内の次のレコードまたはレコードのセットに作用する。サービスノード１０２は、追加されるレコードを受け取り、追加レコードそれぞれが要求するワークをサービス１０８に発送することによりこれを修正した後に、前回受信しているサービスリクエストに対する応答を行う。これは、例えば、サービス１０８が複数の並列リクエストを処理する能力がある場合に可能である。レコードは、レコードについて説明したように、各パイプライン段で取り扱うことができる別々のワーク要素または別々にできるワーク要素で構成することができる。
【００１９】
様々なリクエスト１１４の処理時間量が異なる場合、サービスノード１０２はその入力を受け取った順序と異なる順序でその応答を受信してもよい。これにより、異なる処理時間を有する多数のサービスに、単一のノード１０２がアクセスすることができるようになる。１０２のようなサービスノードは、その入力１１０を受け取った順序と異なる順序で、その出力１２１を提供するようオプションで構成できる。サービスノード１０２にマルチスレッドプロセスを使用せずに、しかもリクエスト１１４それぞれにグラフ１００の全体の状態を記述するデータ（リクエストが返されたときに記述データを使用できるように）を含めずに、このような並列処理を可能にするために、サービスノード１０２は、どのリクエスト１１４が未処理であるかの追跡を続け、入ってくる応答１２０と未処理リクエストを一致させる。実施例によっては、一つのノードがそれぞれのレコードまたはワーク要素を一度に取り扱い、別のノードが別のレコードまたはワーク要素を取り扱うように、グラフをパイプライン化するが、多数のレコードまたはワーク要素を、任意の所定の時間に単一のサービスノード１０２に配置することができる。
【００２０】
パイプライン化したグラフでは、サービスノード１０２は、それぞれのレコード、例えば、データフローのそれぞれのレコードを個々のトランザクションとして扱う。対応するリクエストはその単一の入力レコード内のフィールドに基づいて生成される。幾つかのフィールドはＵＲＬ等のリクエスト属性を定義することができ、その他のフィールドは組み込みデータとして渡される。
【００２１】
実施例によっては、図１Ｂのプロセス１５０で示すように、リクエスト１１４と応答１２０との関連は、サービスノード１０２がアクセスできるメモリ内で追跡される。このメモリは、ベクトル、テーブル、ファイル等のそのようなデータ構造とすることができる。入力レコード１１０が受領されると１５２、レコード１１０のコピーがメモリ１５１に格納される１５４。次いで、サービスノード１０２はリクエスト１１４を生成し１５６、そのリクエストをそのサービスに送り１５８、リクエストのＩＤをメモリに書き込み１６０、それをレコード１１０の格納されたコピーと関連付ける。応答１２０が受信されると１６２、それには、未処理リクエストの内の一つと対応するＩＤが含まれている。サービスノード１０２は、そのＩＤをメモリ内のＩＤと一致させ１６４、対応する入力レコード１１０のコピーを読み出す１６６。そのレコードを応答１２０により更新し１６８、出力１２１を生成する。利用可能な順序で出力を生成するようサービスノード１０２を構成する場合（入力を受け取った順序と同じとは限らない）、出力１２１は次のノード１２２に提供される１７０。サービスノード１０２がその入力と同じ順序で結果を生成するように構成されている場合は、前回のレコードと対応する全ての出力が書き込まれるまで１２１、出力をメモリ内に保持することができ１７１、その時点で書き込むことができる１２１。
【００２２】
実施例によっては、グラフ型計算がネットワークサービスとして提供される。本発明者らは、プロバイダーグラフとしてネットワークサービスを提供するグラフに言及する。図２に示すように、グラフ計算であってもよいが任意の他の種類のアプリケーションでもよいクライアントシステム２０２上で実行されるプロセス２００は、プロバイダーグラフ２０６の使用を要求する計算リクエスト２０４をアプリケーションサーバ２０８に送信する。リクエスト２０４は、ＳＯＡＰ、ＨＴＴＰ、またはＲＰＣリクエストのようなウェブサービスまたは他のネットワークサービスに適したフォーマットで送信される。リクエスト２０４は、アプリケーションサーバ２０８のサービスインターフェース内で、アプリケーションサーバ２０８上で実行されているウェブサービスプラグイン２１０の命令（ＳＯＡＰまたはＨＴＴＰリクエストの）に従って、受信される。
【００２３】
ウェブサービスプラグイン２１０は、ウェブサービスクライアントとそのサービスを提供するグラフとの間のリクエストおよび応答を処理するアプリケーションである。プラグイン２１０はアプリケーションサーバ２０８にインストールされ実行される。ウェブサービスプラグインは、一セットの幾つかのウェブサービスプロバイダーグラフと通信できる。グラフはそれぞれ、プラグインからアクセスされるサービスリストに含まれる。プラグインはＵＲＬを、例えば、クライアントのＨＴＴＰリクエストメッセージ内で用いて、リクエストを特定グラフに誘導する。
【００２４】
プラグイン２１０は、グラフを処理するために、サービスリクエスト２０４をＲＰＣリクエスト等の適切なリクエスト２１２にフォーマットし、このリクエスト２１２をグラフ２０６をホストしているグラフサーバ２１４に送る。実施例によっては、ＲＰＣ呼出しは、クライアント２００からプロバイダーグラフ２０６へ直接行われる。グラフサーバ２１４で、リクエスト２１２に含まれる入力２１６がグラフ２０６に提供され、出力２１８を生成するために実行される。グラフサーバ２１４は、ＲＰＣ応答等の、グラフ出力２２０に適した形式で、出力２１８をアプリケーションサーバ２０８およびそのウェブサービスプラグイン２１０へ送信する。プラグイン２１０は、グラフ出力２２０を元のリクエスト２０４に対して相補的なフォーマットでウェブサービス応答２２２へ再フォーマットする。その出力は、適切なネットワークサービスの通常の方法で、そのサービスを呼び出したクライアントまたは他のエンティティに戻される。次いで、クライアントシステム２０２上のプロセスは、それが、どれか他のウェブ型サービスまたはネットワークサービスの応答であるかのように、その応答を扱う。
【００２５】
グラフは、パイプライン並列処理、コンポーネント並列処理、およびデータ並列処理の何れかまたは全てを使用して入力を処理することができる。すなわち、多数の入力セットを受信して、ことによるとパーティションした後に、これら入力セットをパイプライン段でインターリーブしたり、または異なるコンポーネントグループにより並列処理したりすることができる。
【００２６】
実施例によっては、プロバイダーグラフへの公衆インターフェースまたは外部インターフェースが、ＷＳＤＬ（ウェブサービス記述言語）ファイルにより定義される。ＷＳＤＬファイルは、プロバイダーグラフと相互作用するのに必要な全てのメッセージおよび操作のＸＭＬベース記述を含む。ＷＳＤＬファイルは、組織、業界、または何らかの他の団体が、その集団と関連するウェブサービスにアクセスするために定義してもよい。ＷＳＤＬファイルは特定の実装ではカスタム化してもよい。実施例によっては、ＷＳＤファイルはプロバイダーグラフと関連するサブグラフ内のレコードフォーマットおよびコンポーネントの形式定義から生成される。実施例によっては、単一のプロバイダーグラフは、別々のサービスを実行する多数のサブグラフを含む。そのようなサブグラフから創成されたＷＳＤＬファイルにより、クライアントは、プロバイダーグラフのサブグラフが提供するサービスそれぞれにアクセスできるようになる。
【００２７】
プロバイダーグラフ内で、入ってくるサービスリクエスト入力は、サービスを提供するサブグラフの内部言語に変換される。例えば、図３に示すように、ＳＯＡＰリクエスト等の、入ってくるメッセージ３０６は、メッセージ内で規定されたアクションによる処理が必要なデータペイロード３０８を含む。ペイロード３０８は、例えば、アクションプロセッサ３００ａ、３００ｂ内でグラフが処理すべきＤＭＬ記述レコードでもよい。インターフェースレイヤ３０１は、入ってくるメッセージがどのフォーマットで入ってくるかを構文解析し、グラフノードが要求しているフォーマットで、適切なメッセージをグラフノードに提供する。出力側では、インターフェースレイヤ３０１は逆に作用する。
【００２８】
メッセージ３０６が翻訳されると、アクション型ノード３０２によるパーティションは、メッセージ３０６内で規定されるアクションを解釈し、データペイロード内のレコード３０８を、適切なアクションプロセッサ３００ａまたは３００ｂに送る。実施例によっては、前回のレコード３０８の作業結果がアクションプロセッサ３００ａまたは３００ｂから出力されたということを、収集ノード３０４がパーティションノード３０２に報せるまで、パーティションノード３０２は次に入ってくるメッセージ３０７を受け取らない。
【００２９】
実施例によっては、メッセージ、例えばサービスリクエスト、を取り扱う際の並列性を達成するために、そのサービスリクエストと対応するアクションレコードをパーティション化するようパーティションノード３０２を構成する。これにより、同一のアクションプロセッサが要求されない場合、多数のリクエストを同時に取り扱うことができる。例えば、第１レコード３０８がアクションプロセッサ３００ａを要求し、第２レコード３１０がアクションプロセッサ３００ｂを要求する場合、第１レコード３０８の処理完了を収集ノード３０４が報せるのを待たずに、パーティションノード３０２は第２レコード３１０をアクションプロセッサ３００ｂに送る。
【００３０】
収集ノード３０４は、処理されたレコード３０８および３１０をアクションプロセッサ３００ａまたは３００ｂから受け取り、処理されたレコード３０８’または３１０’をデータペイロードとして含む応答メッセージ３１２および３１３にそれらを編成する。多数のレコードを一度に処理できるように、パーティションノード３０２がトランザクションをパーティション化する場合、対応するリクエストメッセージ３０６および３０７の受信順序と異なる順序で、処理されたレコード３０８’または３１０’を収集ノード３０４により受信することが可能である。パーティションノード３０２と収集ノード３０４との間のインターフェース３１５により、収集ノードは、出力レコード３０８’、３１０’を、対応する入力３０８、３１０と関連させることができるので、回答メッセージ３１２および３１３を正しいクライアントに送り返すことができる。
【００３１】
アクションプロセッサ３００ａ、３００ｂは、任意の形式とすることができる。上記注釈のように、レコード３０８、３１０は任意のフォーマット、例えば、ＤＭＬ記述されたフォーマットとすることができる。その場合には、インターフェースレイヤ３０１は、ＳＯＡＰ等の、入ってくる言語をアクションプロセッサが使用するＤＭＬフォーマットに翻訳する。実施例によっては、中間言語を用いて、インターフェースレイヤ３０１と、パーティションノードおよび収集ノード３０２、３０４との間の両入力を表すことができる。
【００３２】
実施例によっては、到着順でレコード３０８’および３１０’を受け取るよう収集ノード３０４を構成する場合、図３ｂのアクションプロセッサ３００ｂで示すように、アクションプロセッサ内でアクションのプロセスをさらにパーティション化することができる。アクション型ノード３０２によるパーティションは、リクエストメッセージ３０６および３０７を受け取り、これらのレコード３０８および３１０を適切なアクションプロセッサ３００ａまたは３００ｂに経路決定する。アクションプロセッサ３００ｂ内で、プールを横切ってレコードをパーティション化する別のパーティションノード３５２が、レコードを受け取る。プールは、アクションプロセッサ３００ｂのプロセスを実行するサブグラフ３５０の、多数のインスタンス３５０ａ、３５０ｂ、３５０ｃを参照する。各インスタンスは、異なるレコードを他のインスタンスと並列に処理することができる。異なるレコード３０８、３２０を、異なるインスタンスにパーティション化することにより、アクションプロセッサ３００ｂは多数のレコードを並列に取り扱うことができるので、パーティションノード３０２は、前のレコード３０８の結果が出てくる前に、次のレコード３２０をアクションプロセッサに送ることができる。収集ノード３５４は、ノードがインスタンス３５０ａ、３５０ｂ、３５０ｃのどれが使用中であるかを追跡し、可能なら動作していないインスタンスを使用して、並列性および性能が向上するように、パーティションノード３５２と対になって組み合される。収集ノード３０４は、アクションプロセッサ３００ａ、３００ｂの出力３０８’、３１０’をさらに受け取り、インターフェースレイヤ３０１を通じて適切な出力メッセージ３１２、３１３をクライアントに供給して戻す。
【００３３】
出力レコード３０８’、３１０’および出力メッセージ３１２、３１３は、入力リクエスト３０６、３０７を受け取った順序と異なる順序で戻すことができる。例えば、入力レコード３１０にレコード３０８より少ないワーク要素（後述する）しか含まれていなかった場合、出力応答３１３は、それが、後から受け取ったリクエスト３０７と対応するにもかかわらず、最初に戻すことができる。処理の複雑さ、または他の要因に応じてレコードを違う順序で処理したり、異なるレートで処理したりする方法で、アクションプロセッサ３００ａ、３００ｂが作業する場合、入力データの複雑さに基づいて出力の順序を変化させることができる。
【００３４】
実施例によっては、図４に示すように、単一のサービスリクエストのレコード４０６は、データフローとして、すなわち、順にグラフを通過して移動する多数のワーク要素４０８ａ〜４０８ｅとして、プロバイダーグラフが処理するデータを含む。アクションプロセッサ３００ａ（レコードがそれ以上パーティション化されていない場合）またはサブグラフ３５０（レコードがさらにパーティション化されている場合）は、個々のワーク要素４０８ａ〜４０８ｅに入力レコード４０６を分解するアンラップ（unwrap）ノード４０２を含み、ワーク要素をサービス提供サブグラフ４００に適宜送り出す。対応するラッピング（wrapping）ノード４０４は、出力ワーク要素４０８ａ’〜４０８ｅ’のフローを単一応答４１２へ再結合して、リクエスト４０６を送信したクライアントに返す。
【００３５】
実施例によっては、アクションがパーティション化され、ワーク要素にアンラップされると、ワーク要素も、図５ａに示すように並列に処理される。図３ａのレコードと同様に、パーティションノード５０２は、ワーク要素４０８ａ〜４０８ｅの種類、すなわち、ワーク要素プロセッサ５００ａまたは５００ｂのどちらがそれぞれを処理するのに必要か、によってこれらをパーティション化する。ワーク要素が処理される順序が問題になる場合、パーティションノード５０２は、ワーク要素４０８を一つずつプロセッサ５００ａおよび５００ｂに送り（場合により両方のプロセッサを使用するために各ワーク要素をパーティション化する）、それぞれの出力ワーク要素４０８’を受け取ったときに、収集ノード５０４がそれを報せるのを待つ。実施例によっては、プロセスの順序は重要ではなく、そのワーク要素が異なるプロセッサを必要としていると想定される場合は、パーティションノードは、一つのワーク要素を各プロセッサ５００ａおよび５００ｂに送る。
【００３６】
ワーク要素４０８ａ‘〜４０８ｅ’が、プロセッサ５００ａ、５００ｂを出ると、収集ノード５０４がそれを蓄積する。一つのレコード４０６からのワーク要素を全て収集すると、結合して出力レコード４１２に戻される。パーティションノード５０２と収集ノード５０４の間の通信５１５は、どのワーク要素プロセッサが追加のワーク要素を利用できるかをパーティションノード５０２に追跡させる。
【００３７】
多数の並列データフローを扱う技法は、２００３年６月２４日発行の米国特許第６，５８４，５８１号、２００３年１１月２５日発行の米国特許第６，６５４，９０７号にも記載され、その全内容を引用して本明細書に組み込む。
【００３８】
図５ｂは、ワーク要素プロセッサ５００ｂが動作する様子、および図５ａのサブグラフが、プロバイダーグラフ５０１を形成する図３ａ、図３ｂ、および図４の高位ノードの幾つかと関連する様子の詳細を示す。実施例によっては、図５ｂに示すように、ワーク要素プロセッサ５００ｂは、サブグラフ５５０の多数のインスタンス５５０a、５５０ｂ、５５０ｃにより、ワーク要素が動作するようにパーティション化する。インスタンス５５０ａは、サブグラフ５５０内のグラフノードと関係するプロセスの利用可能インスタンスのプールから選択される。最初に、ワーク要素４０８ｉがパーティションノード５５２により受け取られる。ノード５５２は、サブグラフ５５０の幾つかのインスタンス５５０ａ、５５０ｂ、５５０ｃにアクセス権を有する。各インスタンスの出力は収集ノード５５４により受け取られる。次いで、サブグラフ５５０は、サービスまたは他のサブグラフ等の、外側プロセスのノードによるワークの取扱いを遅くする外側プロセスを順に呼び出すことができる。
【００３９】
前のシステムでは、ノード５５２と類似のパーティションコンポーネントが、単一のワーク要素５１４を別々のコンポーネントにパーティション化し、インスタンス５５０ｉ（ここでｉはａ、ｂ、またはｃ）それぞれに一つのコンポーネントを送っていた。収集ノード５５４は、各インスタンスが出力を返すまで待ってから、出力をそのワーク要素の単一の出力に組み合せていたので、並列処理の可能性を失っていた。パイプラインを維持するために、パーティションノードは、ワーク要素の後に各インスタンスを通じて区切り文字を送っておくことができ、そうしておけば、収集コンポーネントは、区切り文字を各インスタンスから受け取ったときに、そのワーク要素が完了したことが分かる筈である。実施例によっては、パイプラインの所定の段階で所定のノードが取り扱う多数のワーク要素のセットの後に、区切り文字を送る。
【００４０】
対照的に、プールノード５５２によるパーティションは、処理のためにワーク要素４０８ａの全体を単一インスタンス５５０ａに送る。収集ノード５５４は、その一つのインスタンス５５０ａからの、そのワーク要素の出力４０８ａ’を待つように構成される。待っていた出力４０８ａ’を受け取ると（実施例によっては、区切り文字が続く）、収集ノード５４４は、次のノード５０４へ出力を提供する。収集ノード５５４は、他のインスタンス５５０ｂおよび５５０ｃからのワーク要素コンポーネントまたは区切り文字を待たない。これにより、ワーク要素プロセッサ５００ｂは、所定のワーク要素に実際に必要とされるインスタンス５５０ｉだけを使用することができる。図３ｂのプールによるトランザクションレコードのパーティションと同様に、プールによるワーク要素のパーティション化により、多数のワーク要素を並列処理できるようになる。第１のワーク要素４０８ａが処理を終了し、そのインスタンス５５０ａから出てくるのを待つのではなく、パーティションノード５５２は、上流ノード５０２から別のワーク要素入力４０８ｃを受け取り、それを次の利用可能なインスタンス５５０ｂに送る。こうして、パーティションノード５５２をマルチスレッドにしなくても、多数のワーク要素４０８ａ、４０８ｂを同時に処理する。実施例によっては、ワーク要素がそれぞれのインスタンス内にあることについて、パーティションノード５５２が通信リンク５６０を通じて収集ノード５５４に報せるので、それによって収集ノード５５４は待っているものについて認識し、出力要素４０８ａ´、４０８ｃ´を入力ワーク要素４０８ａ、４０８ｃと関連付けることができる。
【００４１】
プール間のワーク要素をパーティション化することにより、出力要素４０８ａ´、４０８ｂ´、４０８ｃ´は、入力４０８ａ、４０８ｂ、４０８ｃに対してずれた順序で結果を返すことができる。例えば、インスタンス５５０ｂがワーク要素４０８ｃを処理するのにかけるプロセスより、ワーク要素４０８ａ内のデータが、そのワーク要素を処理するのにインスタンス５５０ａに長いプロセスをかけさせる場合、収集ノード５５４は、出力４０８ｃ’を受け取ってから、出力４０８ａ’を受け取る。二つのワーク要素４０８ａおよび４０８ｃは互いに独立しているので、収集ノード５５４は、出力４０８ａ’を待たずに、出力４０８ｃ’を次のノード５０４に送ることができる。これは、他の段（例えば、パーティション／収集の対５０２／５０４およびアンラップ／ラップの対４０２、４０４）が、ワーク要素プロセッサ５００ｂ内のワーク要素の順序の変化に適合するよう構成されていると仮定している。実施例によっては、順序を維持することが必要であったり、望ましいこともあるので、出力４０８ａ’を受け取るまで収集ノード５５４は出力４０８ｃ’を保持し、次のノード５０４に所定の順序で放出する。インスタンス５５０ａ、５５０ｂ、５５０ｃが幾つかのワーク要素を同時に処理できるので、このような計算法の利点はさらに増す。これは例えば、サブグラフ５５０の処理時間が他のノードまたはサブグラフより長い場合に有用である。
【００４２】
アクション型およびプールによるトランザクションのパーティション化、ならびに種類およびプールによるワーク要素のパーティション化の全てにより、グラフは、内部並列処理、すなわち、異なる処理要素による関連または無関連のワーク要素の並列処理により動作できるようになる。
【００４３】
リクエストおよびそのワーク要素を並列処理するプールによるパーティション化、種類によるパーティション化、および他の方法は、グラフが提供するサービスが、それ自身で並列入力を取り扱うことができるように、プロバイダーグラフ内に実装することができる。例えば、図５ｂのグラフ５０１は、最初のノード５７０が加入ノードであり、最後のノード５７２が加入ノード５７０と対をなす発行ノードである場合、プロバイダーグラフとして動作する。加入ノード５７０は入力４０６を含むリクエスト５７４を受信し、その入力４０６をパーティションノード４０２に送る。加入ノード５７０は、発行ノード５７２と協調して、出力４１２を入力４０６と一致させ、それを適切な応答５７６にパッケージ化する（すなわち、呼び出したクライアントに、各応答が確実に行くようにする）。グラフ５０１は、並列レコードおよび並列ワーク要素を取り扱うので、加入ノード５７０は、発行ノード５７２が出力４１２を受け取るのを待たずに、入力リクエスト５７４を連続して受け取ることができる。アクションの種類に従ってリクエストをパーティション化するサブグラフを使用すると、単一のプロバイダーグラフ５０１が多数のサービスを提供できるようになる。
【００４４】
実施例によっては、加入ノードおよび発行ノード５７０および５７２は、個々のリクエスト５７４が独立で、応答５７６が返される順序が重要でないと仮定しているので、グラフ５０１内のパーティションノードおよび収集ノード４０２、４０４は、順序付けをしないよう構成されている。順序が重要である場合は、加入ノード５７０および発行ノード５７２のどちらかまたは両方が、対応する入力５７４を受け取ったのと同じ順序で応答５７６を確実に返すことができる。
【００４５】
他の実装は、本出願人が権利を有する以下のクレームおよび他のクレームの範囲内にある。
【図１Ａ】
0005894724.tif 000002
【図１Ｂ】
0005894724.tif 000003
【図２】
0005894724.tif 000004
【図３ａ】
0005894724.tif 000005
【図３ｂ】
0005894724.tif 000006
【図４】
0005894724.tif 000007
【図５ａ】
0005894724.tif 000008
【図５ｂ】
0005894724.tif 000009