(57)【特許請求の範囲】
【請求項１】
計算グラフを表すデータを取得するステップであって、前記計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として前記各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続する、ステップと、
複数のデバイスにわたる前記計算グラフの割当てを識別するデータを取得するステップであって、前記割当ては、前記計算グラフ内の各ノードを前記複数のデバイスの各デバイスに割り当て、前記計算グラフの割当てを識別するデータを取得することが、１つまたは複数のマシンに含まれるハードウェア・リソースにわたる前記計算グラフの割当てを識別するデータを取得することを含む、ステップと、
前記計算グラフ内の１つまたは複数のクロス・デバイス有向エッジを識別するステップであって、各クロス・デバイス有向エッジは、各第１のノードを前記割当てにおいて前記各第１のノードと異なるデバイスに割り当てられた各第２のノードに接続する、ステップと、
各クロス・デバイス有向エッジに対して、
前記各第１のノードおよび前記各第２のノードの間の送信ノードを前記計算グラフに挿入するステップと、
前記送信ノードおよび前記各第２のノードの間の受信ノードを前記計算グラフに挿入するステップであって、前記送信ノードおよび前記受信ノードのペア内の各ノードは、各ハードウェア・リソースと送信ノードおよび受信ノードの前記ペアが割り当てられるマシンとに基づくプロトコルに従って通信される前記ペア内の他のノードにより表される前記動作の出力を、入力として受信する動作を表す、ステップと、
前記送信ノードを前記各第１のノードと同一のデバイスに割り当て、前記受信ノードを前記各第２のノードと同一のデバイスに割り当てるように前記割当てを修正するステップと、
前記修正された割当てに従って、前記計算グラフ内の前記ノードにより表される前記動作を前記複数のデバイスに割り当てるステップと、
を含む、コンピュータ実行型の方法。
【請求項２】
前記送信ノードは、（ｉ）入力として、前記各第１のノードにより表される前記動作の出力を受信し、（ｉｉ）前記各第１のノードにより表される前記動作の前記出力を、出力として、前記受信ノードに提供する動作を表し、
前記受信ノードは、（ｉ）入力として、前記送信ノードにより表される前記動作の前記出力を受信し、（ｉｉ）前記送信ノードにより表される前記動作の前記出力を、出力として、前記各第２のノードに提供する動作を表す、
請求項１に記載の方法。
【請求項３】
前記各第１のノードにより表される前記動作の前記出力はテンソルである、請求項２に記載の方法。
【請求項４】
前記受信ノードにより表される前記動作はさらに、（ｉｉｉ）前記送信ノードにより表される前記動作の出力に対する要求を、出力として、前記送信ノードに提供し、
前記送信ノードにより表される前記動作はさらに、（ｉｉ）前記各第１のノードにより表される前記動作の前記出力を、出力として、前記受信ノードに前記受信ノードから受信された１つまたは複数の要求に応答して提供する、
請求項２または３に記載の方法。
【請求項５】
前記各第１のノードおよび前記各第２のノードの間の送信ノードを前記計算グラフに挿入するステップはさらに、各クロス・デバイス有向エッジに対して、前記送信ノードおよび前記各第１のノードの間に有向エッジを挿入するステップを含み、
前記送信ノードおよび前記各第２のノードの間の前記受信ノードを前記計算グラフに挿入するステップはさらに、各クロス・デバイス有向エッジに対して、前記受信ノードおよび前記各第２のノードの間に有向エッジを挿入するステップを含む、
請求項１乃至４の何れか一項に記載の方法。
【請求項６】
データが、送信ノードおよび受信ノードのペア内の各ノードにより表される動作の間で独立に交換される、請求項１乃至５の何れか一項に記載の方法。
【請求項７】
前記複数のデバイスによる前記計算グラフにより表される前記動作の実行の間に、送信ノードおよび受信ノードの各ペアにより表される前記動作は、前記複数のデバイスが、前記複数のデバイスにおけるデバイスにわたる計算グラフ内の他のノードにより表される動作の入力および出力を独立に通信できるようにする、請求項１乃至６の何れか一項に記載の方法。
【請求項８】
モデル入力を受信するステップと、前記修正された計算グラフにより表される動作に従って前記モデル入力を処理するステップとをさらに含む、請求項１乃至７の何れか一項に記載の方法。
【請求項９】
請求項１乃至８の何れか一項で定義された方法により取得された修正された計算グラフに対応する機械学習モデルを提供するステップと、前記機械学習モデルを用いて、モデル入力を処理するステップとを含む、方法。
【請求項１０】
前記計算グラフは機械学習モデルの表現である、請求項１乃至９の何れか一項に記載の方法。
【請求項１１】
１つまたは複数のデータ処理装置と、
前記１つまたは複数のデータ処理装置により実行されたとき、前記１つまたは複数のデータ処理装置に、
計算グラフを表すデータを取得するステップであって、前記計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として前記各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続する、ステップと、
複数のデバイスにわたる前記計算グラフの割当てを識別するデータを取得するステップであって、前記割当ては、前記計算グラフ内の各ノードを前記複数のデバイスの各デバイスに割り当て、前記計算グラフの割当てを識別するデータを取得することが、１つまたは複数のマシンに含まれるハードウェア・リソースにわたる前記計算グラフの割当てを識別するデータを取得することを含む、ステップと、
前記計算グラフ内の１つまたは複数のクロス・デバイス有向エッジを識別するステップであって、各クロス・デバイス有向エッジは、各第１のノードを、前記割当てにおいて前記各第１のノードと異なるデバイスに割り当てられた各第２のノードに接続するステップと、
各クロス・デバイス有向エッジに対して、
前記各第１のノードおよび前記各第２のノードの間の送信ノードを前記計算グラフに挿入するステップと、
前記送信ノードおよび前記各第２のノードの間の受信ノードを前記計算グラフに挿入するステップであって、前記送信ノードおよび前記受信ノードのペア内の各ノードは、各ハードウェア・リソースと送信ノードおよび受信ノードの前記ペアが割り当てられるマシンとに基づくプロトコルに従って通信される前記ペア内の他のノードにより表される前記動作の出力を、入力として受信する動作を表す、ステップと、
前記送信ノードを前記各第１のノードと同一のデバイスに割り当て、前記受信ノードを前記各第２のノードと同一のデバイスに割り当てるように前記割当てを修正するステップと、
前記修正された割当てに従って、前記計算グラフ内の前記ノードにより表される前記動作を前記複数のデバイスに割り当てるステップと、
を含む動作を実施させる命令を格納した、コンピュータ可読記憶デバイスと、
を備える、システム。
【請求項１２】
前記送信ノードは、（ｉ）入力として、前記各第１のノードにより表される前記動作の出力を受信し、（ｉｉ）前記各第１のノードにより表される前記動作の前記出力を、出力として、前記受信ノードに提供する動作を表し、
前記受信ノードは、（ｉ）入力として、前記送信ノードにより表される前記動作の前記出力を受信し、（ｉｉ）前記送信ノードにより表される前記動作の前記出力を、出力として、前記各第２のノードに提供する動作を表す、
請求項１１に記載のシステム。
【請求項１３】
前記各第１のノードにより表される前記動作の前記出力はテンソルである、請求項１２に記載のシステム。
【請求項１４】
前記受信ノードにより表される前記動作はさらに、（ｉｉｉ）前記送信ノードにより表される前記動作の出力に対する要求を、出力として、前記送信ノードに提供し、
前記送信ノードにより表される前記動作はさらに、（ｉｉ）前記各第１のノードにより表される前記動作の前記出力を、出力として、前記受信ノードに前記受信ノードから受信された１つまたは複数の要求に応答して提供する、
請求項１２または１３に記載のシステム。
【請求項１５】
データが、送信ノードおよび受信ノードのペア内の各ノードにより表される動作の間で独立に交換される、請求項１１乃至１４の何れかに記載のシステム。
【請求項１６】
前記複数のデバイスによる前記計算グラフにより表される前記動作の実行の間に、送信ノードおよび受信ノードの各ペアにより表される前記動作は、前記複数のデバイスが、前記複数のデバイスにおけるデバイスにわたる計算グラフ内の他のノードにより表される動作の入力および出力を独立に通信できるようにする、請求項１１乃至１５の何れかに記載のシステム。
【請求項１７】
コンピューティング・デバイスにより実行されたとき、前記コンピューティング・デバイスに、
計算グラフを表すデータを取得するステップであって、前記計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として前記各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続する、ステップと、
複数のデバイスにわたる前記計算グラフの割当てを識別するデータを取得するステップであって、前記割当ては、前記計算グラフ内の各ノードを前記複数のデバイスの各デバイスに割り当て、前記計算グラフの割当てを識別するデータを取得することが、１つまたは複数のマシンに含まれるハードウェア・リソースにわたる前記計算グラフの割当てを識別するデータを取得することを含む、ステップと、
前記計算グラフ内の１つまたは複数のクロス・デバイス有向エッジを識別するステップであって、各クロス・デバイス有向エッジは、各第１のノードを前記割当てにおいて前記各第１のノードと異なるデバイスに割り当てられた各第２のノードに接続する、ステップと、
各クロス・デバイス有向エッジに対して、
前記各第１のノードおよび前記各第２のノードの間の送信ノードを前記計算グラフに挿入するステップと、
前記送信ノードおよび前記各第２のノードの間の受信ノードを前記計算グラフに挿入するステップであって、前記送信ノードおよび前記受信ノードのペア内の各ノードは、各ハードウェア・リソースと送信ノードおよび受信ノードの前記ペアが割り当てられるマシンとに基づくプロトコルに従って通信される前記ペア内の他のノードにより表される前記動作の出力を、入力として受信する動作を表す、ステップと、
前記送信ノードを前記各第１のノードと同一のデバイスに割り当て、前記受信ノードを前記各第２のノードと同一のデバイスに割り当てるように前記割当てを修正するステップと、
前記修正された割当てに従って、前記計算グラフ内の前記ノードにより表される前記動作を前記複数のデバイスに割り当てるステップと、
を含む動作を実施する命令を格納したコンピュータ可読記憶デバイス。
【請求項１８】
前記送信ノードは、（ｉ）入力として、前記各第１のノードにより表される前記動作の出力を受信し、（ｉｉ）前記各第１のノードにより表される前記動作の前記出力を、出力として、前記受信ノードに提供する動作を表し、
前記受信ノードは、（ｉ）入力として、前記送信ノードにより表される前記動作の前記出力を受信し、（ｉｉ）前記送信ノードにより表される前記動作の前記出力を、出力として、前記各第２のノードに提供する動作を表す、
請求項１７に記載の記憶デバイス。
【請求項１９】
前記各第１のノードにより表される前記動作の前記出力はテンソルである、請求項１８に記載の記憶デバイス。
【請求項２０】
前記受信ノードにより表される前記動作はさらに、（ｉｉｉ）前記送信ノードにより表される前記動作の出力に対する要求を、出力として、前記送信ノードに提供し、
前記送信ノードにより表される前記動作はさらに、（ｉｉ）前記各第１のノードにより表される前記動作の前記出力を、出力として、前記受信ノードに前記受信ノードから受信された１つまたは複数の要求に応答して提供する、
請求項１８または１９に記載の記憶デバイス。
【請求項２１】
前記複数のデバイスによる前記計算グラフにより表される前記動作の実行の間に、送信ノードおよび受信ノードの各ペアにより表される前記動作は、前記複数のデバイスが、前記複数のデバイスにおけるデバイスにわたる計算グラフ内の他のノードにより表される動作の入力および出力を独立に通信できるようにする、請求項１７乃至２０の何れか一項に記載の記憶デバイス。
【請求項２２】
複数のデバイスを用いて計算グラフに従ってモデル入力を処理するための方法であって、前記計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として前記各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続し、前記方法は、前記複数のデバイスの第１のデバイスに対して、
前記第１のデバイスに割り当てられた前記計算グラフのサブグラフを表すデータを受信するステップであって、前記サブグラフは前記計算グラフからの複数のノードおよび有向エッジを含む、ステップと、
前記サブグラフ内の前記ノードにより表される前記動作を実施するステップであって、
（１）前記サブグラフ内の各第１のノードにより表される動作を実施して第１の出力を生成するステップと、
前記第１のノードが有向エッジにより前記サブグラフ内の送信ノードに接続されると判定するステップと、
前記送信ノードにより表される前記動作を実施して、前記各第１のノードにより表される前記動作の前記第１の出力をプロトコルに従って前記複数のデバイスの別のデバイスに送信するステップ、および／または、
（２）前記サブグラフ内の受信ノードにより表される動作を実施して、前記複数のデバイス内の別のデバイスに割り当てられた第２のノードにより表される動作から前記プロトコルに従って第２の出力を取得するステップと、
前記受信ノードが有向エッジにより前記サブグラフ内の第３のノードに接続されると判定するステップと、
前記第３のノードにより表される動作を、入力として前記取得された第２の出力を用いて実施するステップと、
を含む、実施するステップと、
を含み、
前記プロトコルは、前記送信ノードおよび前記受信ノードのペアが割り当てられるデバイスの特性に基づく、方法。
【請求項２３】
計算グラフに従ってモデル入力を処理するためのシステムであって、前記計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として前記各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続し、前記システムは複数のデバイスを含み、前記複数のデバイスの第１のデバイスは、
前記第１のデバイスに割り当てられた前記計算グラフのサブグラフを表すデータを受信するステップであって、前記サブグラフは前記計算グラフからの複数のノードおよび有向エッジを含む、ステップと、
前記サブグラフ内の前記ノードにより表される前記動作を実施するステップであって、
（１）前記サブグラフ内の各第１のノードにより表される動作を実施して第１の出力を生成するステップと、
前記第１のノードが有向エッジにより前記サブグラフ内の送信ノードに接続されると判定するステップと、
前記送信ノードにより表される前記動作を実施して、前記各第１のノードにより表される前記動作の前記第１の出力をプロトコルに従って前記複数のデバイスの別のデバイスに送信するステップ、および／または、
（２）前記サブグラフ内の受信ノードにより表される動作を実施して、前記複数のデバイス内の別のデバイスに割り当てられた第２のノードにより表される動作から前記プロトコル従って第２の出力を取得するステップと、
前記受信ノードが有向エッジにより前記サブグラフ内の第３のノードに接続されると判定するステップと、
前記第３のノードにより表される動作を、入力として前記取得された第２の出力を用いて実施するステップと、
を含む、実施するステップと、
を含む動作を実施するように構成され、
前記プロトコルは、前記送信ノードおよび前記受信ノードのペアが割り当てられるデバイスの特性に基づく、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、ニューラル・ネットワークを表す計算グラフの修正および／またはモデル入力を処理するための修正された計算グラフの利用に関する。
【背景技術】
【０００２】
ニューラル・ネットワークは、１つまたは複数のモデルのレイヤを使用して、受信された入力に対する出力、例えば、１つまたは複数の分類を生成する機械学習モデルである。幾つかのニューラル・ネットワークは、出力レイヤに加えて１つまたは複数の隠れレイヤを含む。各隠れレイヤの出力は、当該ネットワーク内の次のレイヤへの入力、即ち、当該ネットワークの次の隠れレイヤまたは出力レイヤとして使用される。当該ネットワークの各レイヤは、当該レイヤに対する夫々の１組のパラメータの現在値に従う受信された入力から出力を生成する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ニューラル・ネットワークのレイヤを個々のデバイスにより処理することができる。当該デバイスは、動作を実施、例えば、レイヤでの出力を入力から生成し、当該動作からの出力をメモリに格納するプロセッサを有することができる。当該ニューラル・ネットワーク内の出力を生成するための多数のおよび大きなサイズの一般的に要求された動作のため、１つのデバイスは、当該ニューラル・ネットワークのレイヤを処理するのに大幅な時間を要することがある。
【課題を解決するための手段】
【０００４】
一般に、本明細書は、ニューラル・ネットワークおよび他の機械学習モデルを表す計算グラフを修正するためのシステムを説明する。
【０００５】
本明細書で説明した主題の特定の実施形態を、以下の利点の１つまたは複数を実現するために実装することができる。ニューラル・ネットワークの動作、例えば、入力から推論を生成するかまたは当該ニューラル・ネットワークをトレーニングするための動作を、ノードおよび有向エッジからなる計算グラフとして表すことができる。システムはこの計算グラフ表現を処理して、当該ニューラル・ネットワークの動作を効率的に実施する。例として、当該計算グラフのサブグラフを、その各々が当該各サブグラフ内の動作を実施する一意なデバイスに割り当て、当該ニューラル・ネットワークの動作を実施するために要求される総時間を削減することができる。当該計算グラフの異なるサブグラフの動作を実施する一意なデバイスの間の通信を、送信ノードおよび受信ノードを各サブグラフに挿入することで効率的に扱うことができる。実行時に、これらの送信ノードおよび受信ノードが表す動作により、一意なデバイスのペアは、自己満足的に互いと通信を行うことができる。これは、通信の協調の負荷を当該バックエンドからシフトし、この計算グラフ表現を処理するシステムに、デバイスがサブグラフを実行している間に１つまたは複数の他のプロセスを実施する機会を与える。送信ノードおよび受信ノードは、かかるサブグラフにより表されるニューラル・ネットワークまたはニューラル・ネットワークの一部を１つのデバイス上でトレーニングし、後に別のデバイスに割り当てられることを可能とするようにサブグラフを区分ける役割を果たす。少なくともこれらの理由のため、送信ノードおよび受信ノードのペアを含むように計算グラフを修正するステップは、計算グラフを分散方式で処理するのに必要なネットワーク通信の時間コストと量を削減するのを支援しうる。
【０００６】
１態様では、本明細書で説明した主題は、計算グラフを表すデータを取得するステップであって、当該計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続する、ステップと、複数のデバイスにわたる当該計算グラフの割当てを識別するデータを取得するステップであって、当該割当ては、当該計算グラフ内の各ノードを当該複数のデバイスの各デバイスに割り当てる、ステップと、当該計算グラフ内の１つまたは複数のクロス・デバイス有向エッジを識別するステップであって、各クロス・デバイス有向エッジは、各第１のノードを当該割当てにおいて各第１のノードと異なるデバイスに割り当てられた各第２のノードに接続する、ステップと、各クロス・デバイス有向エッジに対して、各第１のノードおよび各第２のノードの間の送信ノードを当該計算グラフに挿入するステップと、当該送信ノードおよび各第２のノードの間の受信ノードを当該動作グラフに挿入するステップと、当該送信ノードを各第１のノードと同一のデバイスに割り当て、当該受信ノードを各第２のノードと同一のデバイスに割り当てるように当該割当てを修正するステップと、当該修正された割当てに従って、当該計算グラフ内の当該ノードにより表される当該動作を当該複数のデバイスに割り当てるステップとからなるアクションを含みうる方法で具現化されてもよい。当該方法はコンピュータ実行型の方法であってもよい。
【０００７】
１実装において、当該方法はさらに、モデル入力を受信するステップと、当該修正された計算グラフにより表される動作に従って当該モデル入力を処理するステップとを含む。
【０００８】
別の態様において、本明細書で説明した主題は、第１の態様の方法により取得された修正された計算グラフに対応する機械学習モデルを提供するステップと、当該機械学習モデルを用いて、モデル入力を処理するステップとからなるアクションを含みうる方法で具現化されてもよい。当該処理は当該機械学習モデルのトレーニングを構成してもよく、または、当該モデル入力から推論を生成するステップを構成してもよい。
【０００９】
別の態様において、本明細書で説明した主題は、複数のデバイスにより、第１の態様の方法により取得された修正された計算グラフを実行するアクションを含みうる方法で具現化されてもよい。
【００１０】
これらの態様において、当該計算グラフは、例えば、ニューラル・ネットワークのような機械学習モデルの表現であってもよい。
【００１１】
別の態様において、本明細書で説明した主題は、複数のデバイスを用いて計算グラフに従ってモデル入力を処理するステップであって、当該計算グラフは複数のノードおよび有向エッジを含み、各ノードは各動作を表し、各有向エッジは各第１のノードを、入力として各第１のノードにより表される動作の出力を受信する動作を表す各第２のノードに接続する、ステップを含みうる方法で具体化されうる。当該方法は、当該複数のデバイスの第１のデバイスに対して、第１のデバイスに割り当てられた当該計算グラフのサブグラフを表すデータを受信するステップであって、当該サブグラフは当該計算グラフからの複数のノードおよび有向エッジを含む、ステップと、（１）当該サブグラフ内の各第１のノードにより表される動作を実施して第１の出力を生成するステップと、第１のノードが有向エッジにより当該サブグラフ内の送信ノードに接続されると判定するステップと、当該送信ノードにより表される当該動作を実施して、各第１のノードにより表される当該動作の第１の出力を当該複数のデバイスの別のデバイスに送信するステップ、および／または（２）当該サブグラフ内の受信ノードにより表される動作を実施して、当該複数のデバイス内の別のデバイスに割り当てられた第２のノードにより表される動作から第２の出力を取得するステップと、当該受信ノードが有向エッジにより当該サブグラフ内の第３のノードに接続されると判定するステップと、第３のノードにより表される動作を、入力として当該取得された第２の出力を用いて実施するステップとを含む、当該サブグラフ内の当該ノードにより表される当該動作を実施するステップとを含む。当該態様において、当該計算グラフは本発明の別の態様の方法により取得されてもよい。
【００１２】
この態様および他の態様の他の実装は、コンピュータ記憶デバイス（非一時的記憶デバイスであってもなくてもよい）で符号化された方法のアクションを実施するように構成された対応するシステム、装置、およびコンピュータ・プログラムを含む。１つまたは複数のコンピュータからなるシステムを、動作において当該システムに当該アクションを実施させるシステムにインストールされたソフトウェア、ファームウェア、ハードウェア、またはそれらの組合せによりそのように構成することができる。１つまたは複数のコンピュータ・プログラムは、データ処理装置により実行されたとき、当該装置に当該アクションを実施させる命令によりそのように構成することができる。
【００１３】
これらの他のバージョンは各場合によっては以下の特徴の１つまたは複数を含んでもよい。例えば、当該送信ノードは、（ｉ）入力として、各第１のノードにより表される当該動作の出力を受信し、（ｉｉ）各第１のノードにより表される当該動作の出力を、出力として、当該受信ノードに提供し、当該受信ノードは、（ｉ）入力として、当該送信ノードにより表される当該動作の出力を受信し、（ｉｉ）当該送信ノードにより表される当該動作の出力を、出力として、各第２のノードに提供する動作を表してもよい。幾つかの実装では、当該受信ノードにより表される当該動作はさらに、（ｉｉｉ）当該送信ノードにより表される当該動作の出力の要求を、出力として、当該送信ノードに提供してもよく、当該送信ノードにより表される当該動作はさらに、（ｉｉ）各第１のノードにより表される当該動作の出力を、出力として、当該受信ノードから受信された１つまたは複数の要求に応答して当該受信ノードに提供してもよい。幾つかの例では、各第１のノードにより表される当該動作の出力が、テンソルを含んでもよい。
【００１４】
幾つかの実装では、当該複数のデバイスにわたる当該計算グラフの割当てを識別するデータを取得するステップが、１つまたは複数のマシンに含まれるハードウェア・リソースにわたる当該計算グラフの割当てを識別するデータを取得するステップを含んでもよい。これらの実装において、送信ノードおよび受信ノードのペア内の各ノードは、例えば、入力として、各ハードウェア・リソースおよび送信ノードおよび受信ノードのペアが割り当てられるマシンに対応するプロトコルに従って通信される当該ペア内の他のノードにより表される当該動作の出力を受信する動作を表してもよい。
【００１５】
幾つかの例では、各第１のノードおよび各第２のノードの間の送信ノードを当該計算グラフに挿入するステップがさらに、各クロス・デバイス有向エッジに対して、当該送信ノードおよび各第１のノードの間に有向エッジを挿入するステップを含んでもよい。さらに、当該送信ノードおよび各第２のノードの間の受信ノードを当該動作グラフに挿入するステップがさらに、各クロス・デバイス有向エッジに対して、当該受信ノードおよび各第２のノードの間に有向エッジを挿入するステップを含んでもよい。
【００１６】
幾つかの実装では、当該複数のデバイスによる当該計算グラフにより表される動作の実行の間に、送信ノードおよび受信ノードの各ペアにより表される動作は、当該複数のデバイスが、当該複数のデバイスにおけるデバイスにわたる計算グラフ内の他のノードにより表される動作の入力および出力を独立に通信できるようにしてもよい。幾つかの例では、データを、送信ノードおよび受信ノードのペア内の各ノードにより表される動作の間で独立に交換してもよい。
【００１７】
本明細書の主題の１つまたは複数の実施形態の詳細を添付図面および以下の説明で説明する。当該主題の他の特徴、態様、および利点は詳細な説明、添付図面、および添付の特許請求の範囲から明らかになろう。態様および実装を組み合わせることができ、１態様のコンテキストで説明した特徴または実装を他の態様または実装のコンテキストで実装できることは理解される。
【図面の簡単な説明】
【００１８】
【図１Ａ】計算グラフとして表されたニューラル・ネットワークに対する動作を分散するための計算グラフ・システムの１例を示す図である。
【図１Ｂ】システム内の計算グラフとして表されたニューラル・ネットワークに対する動作を分散するための例示的なフレームワークのための概念図である。
【図２Ａ】例示的な計算グラフの図である。
【図２Ｂ】例示的な計算グラフの図である。
【図２Ｃ】例示的な計算グラフの図である。
【図３】計算グラフに含まれる例示的な送信ノードおよび受信ノードの実行を通じて提供された例示的なプロセスの流れ図である。
【図４Ａ】デバイスに割り当てられた計算グラフの例示的な部分の図である。
【図４Ｂ】デバイスに割り当てられた計算グラフの例示的な部分の図である。
【図５】計算グラフを修正するための例示的なプロセスの流れ図である。
【発明を実施するための形態】
【００１９】
様々な図面における同様な参照番号および指定は同様な要素を示す。
【００２０】
本明細書は一般には、分散方式で計算グラフにより表される動作を実施する計算グラフ・システムを説明する。特に、本明細書は、デバイスの間のシームレスな通信を可能とする方式で計算グラフを修正するための技術を説明する。かかる技術は、各計算グラフが複数のデバイスにより迅速かつ効果的な方式で集合的に実行されるのを保証するのを支援してもよい
【００２１】
当該計算グラフは有向エッジにより接続されたノードを含む。当該計算グラフ内の各ノードは動作を表す。ノードへの入ってくるエッジは、当該ノードへの入力のフロー、即ち、当該ノードにより表される動作への入力を表す。ノードから出るエッジは、別のノードにより表される動作への入力として使用されるべき、当該ノードにより表される動作の出力のフローを表す。したがって、当該グラフ内の第１のノードを当該グラフ内の第２のノードに接続する有向エッジは、第１のノードにより表される動作により生成された出力が、第２のノードにより表される動作への入力として使用されることを示す。
【００２２】
一般的に、当該計算グラフ内の有向エッジに沿って流れる入力および出力はテンソルである。テンソルは、当該アレイの次元に対応する特定の次元を有する、数値または他の値、例えば、文字列の多次元アレイである。例えば、スカラ値は０次テンソルであり、数値のベクトルは１次テンソルであり、行列は２次テンソルである。
【００２３】
幾つかの実装では、当該計算グラフで表される動作は、ニューラル・ネットワーク動作または異なる種類の機械学習モデルに対する動作である。ニューラル・ネットワークは、非線形ユニットの１つまたは複数のレイヤを使用して、受信された入力に対する出力を予測する機械学習モデルである。幾つかのニューラル・ネットワークは、出力レイヤに加えて１つまたは複数の隠れレイヤを含むディープニューラル・ネットワークである。各隠れレイヤの出力は、当該ネットワーク内の別のレイヤ、即ち、別の隠れレイヤ、出力レイヤ、またはその両方に対する入力として使用される。当該ネットワークの幾つかのレイヤは、夫々の１組のパラメータの現在値に従って出力を受信された入力から生成し、当該ネットワークの他のレイヤはパラメータを有さなくてもよい。
【００２４】
例えば、当該計算グラフにより表される動作は、当該ニューラル・ネットワークが推論を計算、即ち、当該ニューラル・ネットワークのレイヤを通じて入力を処理し当該入力に対するニューラル・ネットワーク出力を生成するのに必要な動作であってもよい。別の例として、当該計算グラフにより表される動作は、ニューラル・ネットワーク・トレーニング手続きを実施して当該ニューラル・ネットワークのパラメータの値を調節、例えば、当該パラメータのトレーニングされた値を当該パラメータの初期値から決定することで、当該ニューラル・ネットワークをトレーニングするのに必要な動作であってもよい。幾つかのケースでは、例えば、当該ニューラル・ネットワークのトレーニングの間に、当該計算グラフにより表される動作は、当該ニューラル・ネットワークの複数のレプリカにより実施される動作を含むことができる。
【００２５】
例として、入力を以前のレイヤから受信するニューラル・ネットワーク・レイヤは、パラメータ行列を使用して当該パラメータ行列と当該入力の間の行列乗算を実施することができる。幾つかのケースでは、この行列乗算を、当該計算グラフ内の複数のノードとして表すことができる。例えば、行列乗算を複数の乗算および追加動作に分割でき、各動作は当該計算グラフ内の異なるノードにより表されることができる。各ノードにより表される動作は有向エッジ上で後続のノードに流れる夫々の出力を生成することができる。最終ノードにより表される動作が当該行列乗算の結果を生成した後、結果が、有向エッジ上で別のノードに流れる。当該結果は、当該行列乗算を実施するニューラル・ネットワーク・レイヤの出力と等価である。
【００２６】
幾つかの他のケースでは、当該行列乗算は当該グラフ内の１つのノードとして表される。当該ノードにより表される動作は、入力として、第１の有向エッジおよび重みテンソル上の入力テンソル、例えば、第２の有向エッジ上のパラメータ行列を受信することができる。当該ノードは、例えば、当該入力および重みテンソルの行列乗算を実施して、第３の有向エッジに、当該ニューラル・ネットワーク・レイヤの出力に等価な出力テンソルを出力することができる。
【００２７】
当該計算グラフ内のノードにより表されうる他のニューラル・ネットワーク動作は他の数学的動作、例えば、差、商、および勾配計算と、行列演算、例えば、連結、スプライス、分割、または順位付けと、ニューラル・ネットワーク・ビルディング・ブロック演算、例えば、SoftMax、Sigmoid、整形線形ユニット（ReLU）、または畳込みを含む。
【００２８】
ニューラル・ネットワークを計算グラフとして表すステップは、特に当該ニューラル・ネットワークに対する動作が異なるハードウェア・プロフィールを有する複数のデバイスにわたって分散されている場合に、当該ニューラル・ネットワークを効率的に実装するための柔軟で粒度の細かい方法を提供する。
【００２９】
図１Ａは、計算グラフとして表されたニューラル・ネットワークに対する動作を分散するための計算グラフ・システム１００の１例を示す。システム１００は、１つまたは複数の位置における１つまたは複数のコンピュータ上のコンピュータ・プログラムとして実装されるシステムの例であり、以下で説明されるシステム、コンポーネント、および技術を実装することができる。
【００３０】
クライアント１０２のユーザは、ニューラル・ネットワークを表す計算グラフで動作を実施するように要求することができる。クライアント１０２はコンピュータで実行されるアプリケーションであることができる。
【００３１】
当該要求の一部として、クライアント１０２は、計算グラフを識別するデータをシステム１００に提供し、当該計算グラフに実施すべき動作のタイプを指定する。
【００３２】
例えば、当該要求は、特定のニューラル・ネットワークに対する推論を表す計算グラフを識別でき、当該推論を実施すべき入力を識別することができる。
【００３３】
別の例として、当該要求は、特定のニューラル・ネットワークに対するトレーニング手続きを表す計算グラフを識別でき、当該トレーニングを実施すべきトレーニング・データのような入力を識別することができる。この例において、トレーニング手続きを表す計算グラフを処理するための要求を受信すると、システム１００は、当該計算グラフの１つまたは複数のエッジに対するパラメータの修正された値を、例えば、従来の後方伝播または他のニューラル・ネットワーク・トレーニング技術を用いて決定することができる。システム１００は当該修正されたパラメータをデバイスのメモリに格納でき、実行器１０６は、システム１００で、修正された重みのアドレスを取り出し、格納することができる。推論、トレーニング、または当該修正された重みを要する他の動作に対するクライアント１０２からのさらなる要求に応じて、システム１００は当該アドレスを用いて当該修正された重みにアクセスすることができる。
【００３４】
幾つかのケースでは、当該要求は当該要求に応答して送信されるべき応答を指定してもよい。例えば、ニューラル・ネットワーク・トレーニング要求に対して、クライアント１０２は、要求されたニューラル・ネットワーク・トレーニング動作が完了したとの指示、場合によっては、当該ニューラル・ネットワークのパラメータのトレーニングされた値または当該トレーニングされた値にそこからクライアント１０２によりアクセスしうるメモリ位置の指示を要求することができる。別の例として、ニューラル・ネットワーク推論要求に対して、クライアント１０２は、推論動作を表す出力値を当該計算グラフの１つまたは複数の特定のノードに要求することができる。
【００３５】
システム１００は、当該計算グラフにより表される動作を複数のデバイス１１６乃至１２２にわたって分割することで当該特定の出力を生成するための動作を実施する。システム１００は当該動作を複数のデバイス１１６乃至１２２にデータ通信ネットワーク１１４、例えば、ローカル・エリアネットワーク（ＬＡＮ）または広域ネットワーク（ＷＡＮ）上で分割する。デバイス１１６乃至１２２は当該動作を実施し、適用可能な場合、夫々の出力または指示をシステム１００に返し、システム１００は当該要求された出力または指示をクライアント１０２に返すことができる。
【００３６】
ニューラル・ネットワーク動作を実施する任意のデバイス、例えば、デバイス１１６乃至１２２は、命令およびデータを格納するためのメモリ、例えば、ランダム・アクセスメモリ（ＲＡＭ）および格納された命令を実行するためのプロセッサを含むことができる。一般的に、各デバイスは、他のデバイスと独立に動作を実施するハードウェア・リソースである。例えば、各デバイスはその処理ユニットを有することができる。当該デバイスはグラフィカル処理ユニット（ＧＰＵ）または中央演算装置（ＣＰＵ）であることができる。例として、１つのマシンは１つまたは複数のデバイス、例えば、複数のＣＰＵおよびＧＰＵをホストすることができる。かかるデバイスおよびマシンの例を図１Ｂに見いだすことができる。
【００３７】
図１Ｂは、システム１００における計算グラフとして表されたニューラル・ネットワークに対する動作を分散するための例示的なフレームワークの概念図である。次に図１Ｂを参照すると、マシンの例が、コンピューティング・デバイス１２６、パーソナル・コンピュータ１２８、モバイル・デバイス１３０、およびサーバ１３２を含んでもよい。各マシンは、例えば、ＧＰＵ１１６およびＣＰＵ１１８のような１つまたは複数のデバイスを含んでもよい。
【００３８】
各デバイスはまた、夫々の計算能力を有することができる。即ち、デバイスは異なる量のメモリ、処理速度、または他のアーキテクチャ特性を有することができる。したがって、幾つかのデバイスは他のデバイスができない動作を実施することができる。例えば、幾つかの動作は特定のデバイスのみを有する或る量のメモリを要求し、または、幾つかのデバイスは、特定のタイプの動作、例えば、推論動作のみを実施するように構成される。
【００３９】
図１Ａを再度参照すると、システム１００内のセッション・マネージャ１０４は、当該計算グラフの動作がその間に実施されるセッションを開始する要求をクライアント１０２から受信してもよい。セッション・マネージャ１０４は、当該計算グラフの動作を実施できる１組のデバイス、例えば、デバイス１１６乃至１２２を管理し、動作を実施するために利用できるプレーサ１０８を当該１組のデバイスに提供することができる。
【００４０】
プレーサ１０８は、当該計算グラフで実施されるべき動作ごとに、当該動作を実施する夫々のターゲット・デバイス、例えば、デバイス１１６、および幾つかの実装では、当該夫々のターゲット・デバイスが当該動作を実施するための時間を決定する。幾つかの動作を並列に実施でき、他の動作は、当該計算グラフ内の以前の動作を完了すること、例えば、他の動作が、入力として、当該以前の動作の出力を処理することを要求する。
【００４１】
当該デバイスがプレーサ１０８により割り当てられた動作を実施して出力を生成した後、実行器１０６は当該出力を取り出すことができる。実行器１０６は、当該要求に対する適切な応答、例えば、当該処理が完了したとの出力または指示を生成することができる。ついで、実行器１０６は当該応答をクライアント１０２に返すことができる。
【００４２】
セッション・マネージャ１０４はまた、当該計算グラフで実施すべき動作のセットを実行器１０６に提供する。実行器１０６は、動作のグラフ実行に関するランタイム統計値をデバイス１１６乃至１２２から定期的に取り出す。実行器１０６は当該ランタイム統計値をプレーサ１０８に提供し、プレーサ１０８はさらなる動作の配置とスケジューリングを再最適化することができる。
【００４３】
動作において、システム１００は計算グラフを処理するための要求をクライアント１０２から受信してもよい。例えば、当該要求は、上述のように、当該計算グラフにより表されるニューラル・ネットワーク推論を指定された入力で実施する要求、当該計算グラフにより表されるニューラル・ネットワーク・トレーニング動作を指定された１組のトレーニング・データで実施する要求、または当該計算グラフにより表される他のニューラル・ネットワーク動作を実施する要求であることができる。
【００４４】
当該要求を受信すると、システム１００は当該計算グラフを表すデータを取得してもよい。幾つかのケースでは、当該データが当該クライアントからの要求とともに送信される。他のケースでは、当該要求は当該計算グラフを識別し、システム１００は、当該識別されたグラフを表すデータをメモリから取り出す。例として、当該グラフを表すデータは当該グラフ内のノードのアレイであることができる。各ノードは、動作タイプを示す情報、名前、および当該ノードに対する入ってくるエッジおよび当該ノードから出ていくエッジのリストを含むことができる。
【００４５】
システム１００は、要求された動作を実施するための複数の利用可能なデバイスを識別してもよい。デバイスを、当該デバイスが現在他の動作を実施しておりさらに動作を割り当てることができないかまたはグラフ処理動作を実施するのに利用できない場合に、ビジーであると考えてもよい。当該デバイスを、当該デバイスにさらなる動作を割り当てられうる場合、例えば、当該さらに動作を当該デバイスによる動作のために待ち行列に入れることができる場合に、利用可能であると考えてもよい。
【００４６】
システム１００は当該計算グラフを複数のサブグラフに分割してもよい。各サブグラフは当該計算グラフ内の１つまたは複数のノードを含む。システム１００は、幾つかの例において、互いに隣接するが異なるデバイスに割り当てられる当該計算グラフ内のノードのペアを分解することで、これらのサブグラフを取得してもよい。
【００４７】
システム１００は、サブグラフごとに、当該サブグラフ内の当該１つまたは複数のノードにより表される動作を夫々の利用可能なデバイスに割り当ててもよい。幾つかの実装では、システム１００は、各サブグラフを、当該サブグラフ内のノードにより表される動作を実施するのに必要な計算能力を有するデバイスに割り当ててもよい。幾つかの実装では、当該クライアントからの要求は、特定のノードに対する動作を実施する特定のタイプのデバイスを識別するユーザにより指定されたデータを含む。
【００４８】
したがって、システム１００は、当該計算グラフ内の各ノードを当該複数のデバイスの各デバイスに割り当てる複数のデバイスにわたる当該計算グラフの割当てを生成する。各サブグラフは、当該計算グラフ内の１つまたは複数のノードの所与のグループを含み、これは上述のように同一のデバイスに割り当てられてもよい。デバイス・マッピングに対する例示的なサブグラフを図１Ｂに見いだすことができる。この例において、計算グラフ１４０の例示的なサブグラフ１４０Ａおよび１４０ＢがそれぞれＧＰＵ１１６およびＣＰＵ１１８に割り当てられてもよい。ＧＰＵ１１６およびＣＰＵ１１８はマシン１２６乃至１３２のうち異なるまたは同一のものに存在してもよい。動作において、ＧＰＵ１１６およびＣＰＵ１１８はシステム１００がそれらに割り当てた当該サブグラフに含まれるノードにより表される動作を実施してもよい。
【００４９】
システム１００は当該デバイスに、それぞれ当該デバイスに割り当てられた当該サブグラフに含まれるノードの動作を実施させてもよい。幾つかの実装では、システム１００は各デバイスに要求を送信して、当該各デバイスに割り当てられた当該サブグラフに含まれるノードの動作を開始してもよい。かかる要求をシステム１００から受信したことに応答して、各デバイスは、当該デバイスに割り当てられた当該サブグラフに含まれるノードの動作を実施することに進んでもよい。
【００５０】
様々な依存性が当該計算グラフ内のノードおよびノードのグループの間に存在するとすると、かかるデバイスが当該計算グラフを集合的に実行できるようにするために様々なデバイスの間の通信を強調する必要があることになる。例えば、第１のデバイスで実行されている動作を表すノードは、入力として、第２の、遠隔に配置されたデバイス上で実行されている動作を表す別のノードの出力を受信してもよい。この例において、他のノードにより表される動作の出力の、第２のデバイスから第１のデバイスへの通信を、当該計算グラフの正確でタイムリな実行を保証するために効果的に協調する必要があってもよい。
【００５１】
幾つかの例では、当該デバイスが、入力および出力の互いとの交換を必要に応じて協調してもよい。これらの例において、当該デバイスの間の通信をシステム１００と独立に行ってもよい。即ち、システム１００は、その各サブグラフの動作を実行する要求を各デバイスに送信してもよく、当該要求に応答して、各デバイスはシステム１００の要求に応答してその各サブグラフの動作を実行することに進んでもよく、それが、システム１００による追加の介入なしに他のデバイスとの通信を協調することを含んでもよい。
【００５２】
幾つかの実装では、当該デバイスがシステム１００と独立に通信できるようにするために、システム１００は当該計算グラフを、それがノードの間の通信動作を表す追加のノードを含むように、修正する。特に、デバイスの各サブグラフが、当該デバイスにより実行されたとき、当該デバイスがシームレスに相手の動作を実行している別のデバイスと通信できるようにする動作を表すノードを含んでもよい。受信されたモデル入力がついで、修正された計算グラフにより表される動作に従って処理されてもよい。
【００５３】
具体的には、システム１００は「送信」および「受信」ノードを当該計算グラフに挿入してもよい。各送信ノードは動作を表し、テンソルのようなデータが、当該送信ノードのデバイスと異なるデバイスに割り当てられる受信ノードに中継される。システム１００は、当該グラフ内の任意のクロス・デバイス有向エッジを識別することで送信ノードおよび受信ノードのペアを挿入する当該グラフ内の位置を決定してもよい。クロス・デバイス有向エッジは、２つの異なるデバイスに割り当てるべき当該計算グラフ内のノードを接続する当該計算グラフ内の有向エッジである。システム１００は、当該計算グラフの当該割当てを決定する間またはその後に、かかるクロス・デバイス有向エッジを識別してもよい。当該グラフに含まれる各クロス・デバイス有向エッジを識別すると、システム１００は、各クロス・デバイス有向エッジを分割し、当該クロス・デバイス有向エッジの代わりに送信ノードおよび受信ノードのペアを挿入することで当該計算グラフを修正してもよい。この修正プロセスを、図２Ａ乃至Ｃを参照して以下でさらに説明する。
【００５４】
図２Ａ乃至Ｃは例示的な計算グラフを示す。例として、計算グラフ・システム、例えば、図１のシステム１００Ａは、所与の１組の入力が与えられたとき、計算グラフ２００Ａを用いて推論を計算する要求をクライアントから受信することができる。計算グラフ２００Ａは入力を例示的なソース２０１から受信し、出力を例示的なシンク２１５に提供してもよい。例示的なソース２０１およびシンク２１５は、例えば、当該計算グラフの１つまたは複数の他のノードであってもよい。
【００５５】
当該システムは、例えば、３つの異なるデバイスにわたって計算グラフ２００Ａを割り当てると決定してもよい。この決定を行うため、当該システムは計算グラフ２００Ａを分析して、サブグラフに分割し利用可能なデバイスに割り当てうる１つまたは複数のノードを識別してもよい。例えば、当該システムは、ノード２０４、２１２および２１４により形成された第１のチェーンを第１のデバイスに割り当て、ノード２０６、２０８、および２１０により形成された第２のチェーンを第２のデバイスに割り当て、ノード２０２を第３のデバイスに割り当てると決定してもよい。ノードの他の可能なチェーンが可能であるが、当該システムはサブグラフの数を最小化するチェーンを選択することができる。
【００５６】
この特定の割当てのもとで、当該システムは有向エッジ２２０Ａおよび２３０Ａをクロス・デバイス有向エッジとして識別してもよい。即ち、当該システムは、有向エッジ２２０Ａおよび２３０Ａがそれぞれ、当該システムが割り当てるとして決定したノードを異なるデバイスに接続すると認識してもよい。例えば、有向エッジ２２０Ａはノード２０２をノード２０８に接続し、当該システムはそれらをそれぞれ第３のデバイスおよび第２のデバイスに割り当てると決定していることが分かる。同様に、有向エッジ２３０Ａは、第２のデバイスに対応するノード２０８を第１のデバイスに対応するノード２１２に拡張することでデバイス境界と交差する。
【００５７】
計算グラフ２００Ａに含まれる各クロス・デバイス有向エッジを識別したことに応答して、当該システムは、計算グラフ２００Ａを修正して、修正された計算グラフ、例えば、図２Ｂに示された修正された計算グラフ２００Ｂを生成することに進んでもよい。さらに、当該システムは、ノード２０２および２０８の間の送信ノードおよび受信ノードのペアを有向エッジ２２０Ａの代わりに挿入してもよい。同様な方式で、当該システムはまた、ノード２０８および２１２の間の送信ノードおよび受信ノードのペアを有向エッジ２３０Ａの代わりに挿入してもよい。有向エッジは各送信ノードまたは受信ノードとかかる送信ノードまたは受信ノードに隣接する各ノードとの間に挿入されることが分かる。
【００５８】
次に図２Ｂを参照すると、修正された計算グラフ２００Ｂは、当該システムにより修正された計算グラフ２００Ａのバージョンを表し、送信ノードおよび受信ノードの２つのペアを含むことが分かる。特に、第１の送信ノードＳ１はノード２０２および２０８の間に挿入されており、対応する第１の受信ノードＲ１が第１の送信ノードＳ１およびノード２０８の間に挿入されている。これらの挿入により、当該システムは、第１の送信ノードＳ１をノード２０２と同一のデバイス（即ち、第３のデバイス）に割り当て、第１の受信ノードＲ１をノード２０８と同一のデバイス（即ち、第２のデバイス）に割り当てる。双方向ブリッジ２２０Ｂは第１の送信ノードＳ１を第１の受信ノードＲ１に接続する。ブリッジ２２０Ｂを、第１の送信ノードＳ１および第１の受信ノードＲ１の間の通信チャネルを表すとみなすことができる。
【００５９】
実行時に、第１の送信ノードＳ１および第１の受信ノードＲ１により表される動作は、第２のおよび第３のデバイスが所定の方式で通信できるようにする。例えば、かかる動作の実行が、特定の通信プロトコルに従う第２のおよび第３のデバイスを含んでもよい。各デバイスにより実行される各デバイスおよび／またはノードのアドレス情報がまた、これらの動作に組み込まれてもよい。このように、第１の送信ノードＳ１および第１の受信ノードＲ１は、それらの各サブグラフが満足に実行されるように第２のおよび第３のデバイスの間で実施される必要がありうる全ての通信プロセスをカプセル化してもよい。これらの通信プロセスを、図３および４ＡおよびＢを参照して以下でさらに説明する。
【００６０】
同様に、第２の送信ノードＳ２がノード２０８および２１２の間に挿入されており、対応する第２の受信ノードＲ２が第２の送信ノードＳ２およびノード２１２の間に挿入されている。これらの挿入により、当該システムは第２の送信ノードＳ２をノード２０８と同一のデバイス（即ち、第２のデバイス）に割り当て、第１の受信ノードＲ１をノード２０８と同一のデバイス（即ち、第１のデバイス）に割り当てる。双方向ブリッジ２３０Ｂは第２の送信ノードＳ２を第２の受信ノードＲ２に接続し、第２の送信ノードＳ２および第２の受信ノードＲ２の間の通信チャネルを表すとみなすことができる。第１の送信ノードＳ１および第１の受信ノードＲ１のように、第２の送信ノードＳ２および第２の受信ノードＲ２は通信を、第２のおよび第１のデバイスの間で容易に協調させることができる。
【００６１】
図２Ｃにおける修正された計算グラフ２００Ｃにより示されるように、システム１００は、各送信ノードが１つの各サブグラフに割り当てられ、各受信ノードが別の各サブグラフに割り当てられるように、割当てを修正してもよい。例えば、第１の送信ノードＳ１が、当該システムが第３のデバイスに割り当てたサブグラフ２４０の一部として、ノード２０２とともに、マシン１３０に含まれる第３のデバイスに割り当てられてもよい。同様に、第１の受信ノードＲ１および第２の送信ノードＳ２が、当該システムが第２のデバイスに割り当てたサブグラフ２４６の一部として、ノード２０６、２０８、および２１０とともに、マシン１２６に含まれる第２のデバイスに割り当てられてもよい。さらに、第２の受信ノードＲ２が、当該システムが第１のデバイスに割り当てたサブグラフ２４２の一部として、ノード２０４、２１２、および２１４とともに、マシン１３２に含まれる第１のデバイスに割り当てられてもよい。
【００６２】
実行時に、第１の送信ノードＳ１により表される動作が、ノード２０２の出力を第１の受信ノードＲ１に中継するステップを含んでもよい。この交換が、例えば、マシン１３０および１２６がアクセスを有するネットワーク２１５上のチャネル２２０Ｂにより発生してもよい。ネットワーク２１５は、図１と関連して上述したようにネットワーク１１４と同様であってもよい。この通信を行うために利用されるプロトコルが、送信ノードおよび受信ノードＳ１およびＲ１の第１のペアにより表される動作に反映されてもよく、サブグラフ２４０および２４６の実行に関連付けられたデバイス、マシン、ノード、およびネットワークの１つまたは複数の特性に依存してもよい。第１の受信ノードＲ１により表される動作は、それが第１の送信ノードＳ１から受信するノード２０２により表される動作の出力を入力としてノード２０８に渡すステップを含んでもよい。
【００６３】
同様に、第２の送信ノードＳ２により表される動作が、ノード２０８により表される動作の出力を第２の受信ノードＲ２に中継するステップを含んでもよい。この交換が、例えば、マシン１３２および１２６がアクセスを有するネットワーク２１５上のチャネル２３０Ｂにより生じてもよい。この通信を行うために利用されるプロトコルが、送信ノードＳ２および受信ノードおよびＲ２の第２のペアにより表される動作に反映されてもよく、サブグラフ２４６および２４２の実行に関連付けられたデバイス、マシン、ノード、およびネットワークの１つまたは複数の特性に依存してもよい。第２の受信ノードＲ２により表される動作は、それが第２の送信ノードＳ２から受信するノード２０８により表される動作の出力を入力としてノード２１２に渡すステップを含んでもよい。
【００６４】
図３は、計算グラフに含まれる例示的な送信ノードおよび受信ノードの実行を通じて提供された例示的なプロセス３００の流れ図である。簡単のため、プロセス３００を、１つまたは複数の位置に配置された１つまたは複数のコンピュータのシステムにより実施されているとして説明する。プロセス３００と関連して説明した計算グラフおよび動作は上述したものであってもよい。例えば、プロセス３００を、図１と関連して上述したシステム１００により提供される計算グラフの１つまたは複数の部分の実行を通じて実施してもよい。
【００６５】
上述のように、送信ノードおよび受信ノードにより表される動作が、それらが割り当てられているデバイス間の双方向通信を生み出してもよい。それぞれ送信ノードＳ３および受信ノードおよびＲ３により表される動作３３０および３４０が、最初にかかる双方向通信（３３２および３４２）に対して使用するための通信プロトコルの決定を含んでもよい。送信ノードおよび受信ノードのペアにより表される動作により利用される通信プロトコルが、手元の当該サブグラフの実行に関連付けられたデバイス、マシン、ノード、およびネットワークの１つまたは複数の特性に依存してもよい。この決定プロセスを、図４ＡおよびＢを参照して以下でさらに説明する。
【００６６】
送信ノードＳ３により表される動作３３０はついで、上流ノード３１０の動作の出力が提供されているかどうかを判定するように動作してもよい（３１０）。かかる出力が、割り当てられたデバイスによるノード３１０および送信ノードＳ３を含むサブグラフの実行により生成されたテンソルを含んでもよい。いったん提供されると、送信ノードＳ３により表される動作３３０が、ノード３１０により表される動作の出力を入力として受信ノードＲ３により表される動作３４０に提供するように動作してもよく、動作３４０が、ノード３２０により表される動作への入力と同一のものを提供するように動作してもよい。
【００６７】
受信ノードＲ３により表される動作３４０の実行は、１つまたは複数のメッセージを対応する送信ノードＳ３に送信するステップを含んでもよい（３４４）。かかるメッセージが、受信ノードＲ３が属するサブグラフが対応する送信ノードＳ３の実行により入力を受信する準備ができているとの指示としての役割を果たしてもよい。このように、これらのメッセージを、１つまたは複数の上流動作によりデータ出力を受信する要求とみなすことができる。図３の例において、受信ノードＲ３により表される動作３４０が、ノード３１０により表される動作の出力を含む入力を送信ノードＳ３から受信してもよい。
【００６８】
実行時に、送信ノードＳ３により表される動作３３０が、かかるメッセージの受信に応答してデータを中継することを含んでもよい。幾つかの例では、送信ノードＳ３により表される動作３３０は、かかるメッセージが受信されるまで、ノード３１０の出力により表される動作を中継しなくてもよい（３３６）。このように、デバイスの間の情報のフローを、テンソルの交換が成功することを保証するように規制してもよい。これらの例において、ノード３１０により表される動作の出力を、送信ノードＳ３を実行しているデバイスにローカルな１つまたは複数のメモリ領域にキャッシュまたは格納してもよい（３３７）。幾つかの実装では、当該動作のこの出力を、当該デバイスが属するマシン、または１つまたは複数のネットワークアクセス可能デバイス上のどこかに格納してもよい。受信ノードのメッセージが受信されると、当該動作の格納された出力を、受信ノードＲ３に関連付けられたパーティに通信し（３３６乃至３３８）、続いてメモリからフラッシュまたは削除してもよい。送信ノードＳ３により表される動作からの出力が入力として受信されると判定すると（３４６）、受信ノードＲ３により表される動作は、かかる出力を入力として下流ノード３２０により表される動作に提供するように動作してもよい（３４８）。
【００６９】
それぞれ送信ノードＳ３および受信ノードおよびＲ３により表される動作３３０および３４０の実行を通じて、関連付けられたサブグラフに対応するニューラル・ネットワークまたは他の機械学習モデルの一部の実行（これは簡単のため「関連付けられたサブグラフの実行」と称される）に対して要求された全てのデータ交換を、当該デバイスが当該サブグラフを実行することにより協調し実行してもよいことが分かる。動作３３０および３４０を実行しているデバイスのペアに提供される通信オートノミーが、協調通信の負荷をバックエンドからシフトする役割を果たしてもよい。このように、システム１００のような計算グラフ・システムは、かかるデバイスの間の通信をアクティブに規制するのではなく、デバイスがサブグラフを実行している間に１つまたは複数の他のプロセスを実施できてもよい。少なくともこの理由のため、送信ノードおよび受信ノードのペアを含むように計算グラフを修正することで、計算グラフを分散方式で処理するのに必要なネットワーク通信の時間コストと量を削減するのを支援してもよい。
【００７０】
幾つかの実装では、送信ノードＳ３および受信ノードおよびＲ３により表される動作３３０および３４０を、所与のデバイスの全ての入ってくるおよび／または出ていく通信を扱う際に利用してもよい。例えば、受信ノードＲ３により表される動作３４０は、入ってくる通信を送信ノードＳ３により表される動作３３０から、ならびに１つまたは複数の他の送信ノードにより表される動作から、受信するように動作してもよい。同様に、受信ノードＳ３により表される動作３３０は、出ていく通信を入力として受信ノードＲ３により表される動作３４０、ならびに１つまたは複数の他の受信ノードにより表される動作に提供するように動作してもよい。このように、送信ノードＳ３および受信ノードおよびＲ３により表される動作３３０および３４０は、ハブ風の関数をそれらが割り当てられたデバイスに提供するように動作してもよい。
【００７１】
送信ノードＳ３および受信ノードおよびＲ３は、かかるサブグラフにより表されるニューラル・ネットワークまたはニューラル・ネットワークの一部を１つのデバイスでトレーニングし、のちに別のデバイス割り当てることを可能とする方式でサブグラフを区分ける役割を果たしてもよい。送信ノードＳ３および受信ノードおよびＲ３はまた、１つまたは複数のサブグラフにより表されるニューラル・ネットワークまたはニューラル・ネットワークの部分を新たな方法でトレーニングまたはテストできるようにしてもよい。例えば、受信ノードＲ３により表される動作３４０は、受信ノードＲ３から下流の計算グラフの１つまたは複数の部分をトレーニングするために、ノード３１０により表される動作により出力されているテンソルをシミュレートする入力をノード３２０により表される動作に提供してもよい。幾つかの実装では、図１を参照して上述したクライアント・デバイス１０２のようなクライアント・デバイスが、受信ノードＲ３にかかる入力を提供するために利用されてもよい。これらの実装において、当該クライアント・デバイスは、所定のテンソルを出力として動作３３０に提供する特殊ノードにより表される動作を実行してもよく、動作３３０が当該クライアント・デバイスで実行されてもよい。かかる特殊ノードを、計算グラフの上流にあるノードの受信ノードＲ３およびノード３２０からの置き換えとみなすことができる。このように、ユーザが、特殊ノードおよび動作３３０により表される動作をそれらのクライアント・デバイスで実行することで、１つまたは複数の下流サブグラフにより表されるニューラル・ネットワークまたはニューラル・ネットワークの一部を遠隔にテストおよび／またはトレーニングできてもよい。このタイプの特殊ノードにより表される動作によるテンソル出力が、例えば、手元の当該サブグラフの実行に関連付けられたデバイス、マシン、ノード、およびネットワークの１つまたは複数の特性に基づいて静的な、ユーザ定義された、ランダムに生成された、または決定されたものであってもよい。
【００７２】
幾つかの実装では、送信ノードＳ３および受信ノードおよびＲ３と関連してデバイスの間で交換されるデータが圧縮されてもよい。即ち、送信ノードＳ３により表される動作３３０は、ノード３１０により表される動作の出力に対して１つまたは複数の圧縮プロセスを実施するように動作してもよい。同様に、受信ノードＲ３により表される動作３４０が、送信ノードＳ３により表される動作３３０の実行による出力として提供される圧縮されたデータへの１つまたは複数の解凍プロセスを実施するように動作してもよい。実施される当該圧縮動作が、当該２つのデバイスの間のデータを送信するのに適した任意の従来の圧縮アルゴリズムを含んでもよい。例えば、当該デバイスの間で交換されるデータに下方変換、切詰め、またはそれらの組合せを行ってもよい。同様に、かかるデータが運搬するデータはまた、確率的丸めを受けてもよい。かかる圧縮動作が、手元の当該サブグラフの実行に関連付けられたデバイス、マシン、ノード、およびネットワークの１つまたは複数の特性に基づいて選択されてもよい。例えば、圧縮動作が、機械学習モデルの雑音耐性に基づいて選択されてもよい。圧縮を動作３３０および３４０と関連して説明したが、かかる動作が、様々な信号処理および条件付け技術の何れかを利用してもよいことは理解されるべきである。
【００７３】
上述のように、送信ノードおよび受信ノードのペアにより表される動作により利用される通信プロトコルは、手元の当該サブグラフの実行に関連付けられたデバイス、マシン、ノード、およびネットワークの１つまたは複数の特性に依存しうる。図４ＡおよびＢは、送信ノードおよび受信ノードを含みデバイスに割り当てられる計算グラフ４００Ａおよび４００Ｂの２つの部分を示す。計算グラフ４００Ａに含まれる送信ノードがデバイス４１２Ａに割り当てられており、この例ではそれはＧＰＵであり、計算グラフ４００Ａに含まれる受信ノードがデバイス４１４Ａに割り当てられており、この例でもそれがＧＰＵであることが分かる。この例において、ＧＰＵ４１２ＡおよびＧＰＵ４１４Ａは同一のマシン４１０Ａ内に存在する。計算グラフ４００Ａの送信ノードおよび受信ノードを送信するデバイスは両方ともＧＰＵであり両方とも同一のマシン４１０Ａ内に存在するので、それらの交換を、リモート・プロシージャ・コール（ＲＰＣ）または他の局所化された要求／応答プロトコルのもとで行うのが有利であるかもしれない。
【００７４】
幾つかの実装では、使用される当該特定の通信プロトコルが、サブグラフ割当ての後に送信ノードおよび受信ノードにより表される動作の実行を通じて決定されてもよい。かかる決定を、例えば、これらの動作に既知なアドレス情報に基づいて行ってもよい。この例において、ＧＰＵ４１２ＡおよびＧＰＵ４１４Ａは当該２つのデバイスが両方ともマシン４１０Ａ内に存在することを示す送信ノードおよび受信ノードに関連付けられた動作を実行してもよく、続いてＲＰＣの下での通信を協調する。他の実装において、通信プロトコルが、それらの挿入時に各送信ノードおよび受信ノードにより表される動作内であらかじめ決定され、示されてもよい。これらの実装において、各通信プロトコルを、上述したものと同様に決定してもよい。
【００７５】
計算グラフ４００Ｂに含まれる送信ノードがデバイス４２２Ｂに割り当てられ、これがＣＰＵまたはＧＰＵであってもよいこと、計算グラフ４００Ｂに含まれる受信ノードがデバイス４４２Ｂに割り当てられ、これがＣＰＵまたはＧＰＵであってもよいことが分かる。デバイス４２２Ｂがマシン４２０Ｂと存在してもよく、デバイス４４２Ｂがマシン４４０Ｂと存在してもよい。通信プロトコルが、上述したのと同様な技術の使用を通じてこれらのデバイスに対して決定されてもよい。この例において、デバイス４２２Ｂおよび４４２Ｂの間の交換がリモート直接メモリアクセス（ＲＤＭＡ）プロトコルのもとで行われてもよい。このプロトコルは、それが各デバイスに関連付けられたオペレーティング・システムを含むことなく通信を実施できるという点で、２つの異なるマシンのデバイスに対して有利であるかもしれない。この例において、デバイス４２２Ｂおよび４４２Ｂは、当該２つのデバイスが異なるデバイスに存在することを示す送信ノードおよび受信ノードに関連付けられた動作を実行し、続いてＲＤＭＡのもとで通信を協調してもよい。
【００７６】
図５は、送信ノードおよび受信ノードを含むように計算グラフを修正するための例示的なプロセス５００の流れ図である。簡単のため、プロセス５００を、１つまたは複数の位置に配置された１つまたは複数のコンピュータのシステムにより実施されるとして説明する。例えば、適切にプログラムされた計算グラフ・システム、例えば、図１の計算グラフ・システム１００がプロセス５００を実施することができる。
【００７７】
当該システムは、複数のノードおよび有向エッジを含む計算グラフを表すデータを取得してもよい（５０２）。例えば、計算グラフは、要求を１つまたは複数のクライアント・デバイスから受信した後に、計算グラフ・システムにより取得されてもよい。幾つかの例では、当該計算グラフ内の各ノードは動作のインスタンスである。
【００７８】
当該システムは複数のデバイスにわたる当該計算グラフの割当てを識別するデータを取得してもよい（５０４）。例えば、計算グラフ・システムは、取得された計算グラフに含まれる各ノードがどのように複数の利用可能なデバイスにわたって割り当てられるかを判定してもよい。幾つかの実装では、これが、１つまたは複数のマシンに含まれるハードウェア・リソースにわたる当該計算グラフの割当てを識別するデータを取得するステップを含んでもよい。
【００７９】
当該システムは、異なるデバイスに割り当てられたノードを接続する当該計算グラフ内の１つまたは複数の有向エッジを識別してもよい（５０６）。例えば、計算グラフ・システムは１つまたは複数のクロス・デバイス有向エッジを識別してもよい。
【００８０】
当該システムは、識別された有向エッジにより接続されたノードのペアの間に送信ノードおよび受信ノードを挿入してもよい（５０８）。例えば、計算グラフ・システムは、各識別されたクロス・デバイス有向エッジを、双方向ブリッジにより接続された送信ノードおよび受信ノードのペアで置き換えてもよい。そうする際、当該システムはさらに、有向エッジを当該送信ノードおよび各第１のノードの間に挿入し、有向エッジを当該受信ノードおよび各第２のノードの間に挿入してもよい。
【００８１】
幾つかの実装では、データを、送信ノードおよび受信ノードのペア内の各ノードにより表される動作の間で独立に交換されてもよい。幾つかの事例では、送信ノードおよび受信ノードのペア内の各ノードは、入力として、送信ノードおよび受信ノードのペアが割り当てられている各ハードウェア・リソースとマシンに対応するプロトコルに従って通信される当該ペア内の他のノードにより表される動作の出力を受信する動作を表してもよい。上述のように、かかるプロトコルは、例えば、ＲＰＣおよびＲＤＭＡを含んでもよい。
【００８２】
各送信ノードは、例えば、入力として、各第１のノードにより表される動作の出力を受信し、各第１のノードにより表される動作の出力を、出力として、受信ノードに提供する動作を表してもよい。各第１のノードにより表される動作の出力は例えば、テンソルであってもよい。同様に、各受信ノードは、入力として、当該送信ノードにより表される動作の出力を受信し、当該送信ノードにより表される動作の出力を、出力として、各第２のノードに提供する動作を表してもよい。幾つかの実装では、当該受信ノードにより表される動作はさらに、当該送信ノードにより表される動作の出力の要求を、出力として、当該送信ノードに提供してもよい。これらの実装において、当該送信ノードにより表される動作は、各第１のノードにより表される動作の出力を、出力として、当該受信ノードから受信された１つまたは複数の要求に応答して当該受信ノードに提供してもよい。
【００８３】
当該システムは、割当てを修正して送信ノードおよび受信ノードをデバイスに割り当ててもよい（５１０）。例えば、計算グラフ・システムは、各送信ノードを当該送信ノードから上流のノードと同一のデバイスに割り当ててもよく、同様に各受信ノードを当該受信ノードから下流のノードと同一のデバイスに割り当ててもよい。
【００８４】
当該システムは、当該ノードにより表される動作を当該複数のデバイスに当該修正された割当てに従って割り当ててもよい（５１２）。例えば、計算グラフ・システムは、複数のデバイスの各々が各サブグラフに含まれる動作を実施することを要求してもよい。幾つかの実装では、当該システムは当該計算グラフを複数のサブグラフに分割してもよい。
【００８５】
本明細書で説明した主題および当該機能的動作の実施形態をデジタル電子回路で、有形に−具現化されたコンピュータソフトウェアまたはファームウェア、当該構造開示された本明細書およびそれらの構造的な均等物で、またはそれらの１つまたは複数の組合せでを含めて、コンピュータ・ハードウェアで実装することができる。本明細書で説明した主題の実施形態を、１つまたは複数のコンピュータ・プログラム、即ち、コンピュータ可読プログラム・キャリア、例えば、データ処理装置により実行するためのまたはその動作を制御するための有形非一時的プログラム・キャリアで符号化されたコンピュータ・プログラム命令の１つまたは複数のモジュールとして実装することができる。あるいはまたはさらに、当該プログラム命令は、データ処理装置により実行するための適切な受信機装置に送信するための情報を符号化するために生成される、人工的に生成された伝播信号、例えば、マシン生成された電気的、光学的、または電磁気信号で符号化されることができる。当該コンピュータ記憶媒体は、マシン可読記憶デバイス、マシン可読記憶基板、ランダムまたはシリアル・アクセス・メモリデバイス、またはそれらの１つまたは複数の組合せであることができる。当該コンピュータ記憶媒体は、しかし、伝播信号ではない。
【００８６】
「データ処理装置」という用語はデータを処理するための全ての種類の装置、デバイス、およびマシンを包含し、例としてプログラム可能プロセッサ、コンピュータ、または複数のプロセッサまたはコンピュータを含む。当該装置は特殊目的論理回路、例えば、ＦＰＧＡ（フィールドプログラム可能ゲートアレイ）またはＡＳＩＣ（特殊用途向け集積回路）を含むことができる。当該装置はまた、ハードウェアに加えて、問題の当該コンピュータ・プログラムに対する実行環境、例えば、プロセッサファームウェア、プロトコル・スタック、データベース管理システム、オペレーティング・システム、またはそれらの１つまたは複数の組合せを構成するコードを生成するコードを含むことができる。
【００８７】
コンピュータ・プログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、モジュール、ソフトウェアモジュール、スクリプト、またはコードと称するかまたはそれとして説明されてもよい）は、コンパイル型またはインタプリタ型言語、または宣言型または手続型言語を含む任意の形態のプログラミング言語で書かれることができ、スタンドアロンプログラムまたはモジュールとして、コンピューティング環境で使用するのに適したコンポーネント、サブルーチン、または他のユニットとしてを含めて、任意の形態で展開されることができる。コンピュータ・プログラムはファイルシステム内のファイルに対応してもよいがその必要はない。プログラムを、他のプログラムまたはデータを保持するファイルの一部、例えば、マークアップ言語ドキュメントに格納された１つまたは複数のスクリプトに、問題となっているプログラム専用の単一のファイルに、または複数の協調ファイル、例えば、１つまたは複数のモジュール、サブプログラム、またはコードの部分を格納するファイルに、格納することができる。コンピュータ・プログラムは、１つのコンピュータで実行されるか、または、１つのサイトに配置されるかもしくは複数のサイトにわたって分散し通信ネットワークにより相互接続される複数のコンピュータで実行されるように展開されることができる。
【００８８】
本明細書で使用される際、「エンジン」、または「ソフトウェアエンジン」は、入力と異なる出力を提供する、ソフトウェアで実装された入出力システムである。エンジンは、ライブラリ、プラットフォーム、ソフトウェア開発キット（「ＳＤＫ」）、またはオブジェクトのような機能の符号化されたブロックであることができる。各エンジンを、１つまたは複数のプロセッサおよびコンピュータ可読媒体を含む、任意の適切なタイプのコンピューティング・デバイス、例えば、サーバ、モバイル・フォン、タブレットコンピュータ、ノートブックコンピュータ、音楽プレイヤ、電子書籍リーダ、ラップトップまたはデスクトップコンピュータ、ＰＤＡ、スマートフォン、または他の静的またはポータブルデバイスで実装することができる。さらに、２つ以上の当該エンジンを同一のコンピューティング・デバイス、または異なるコンピューティング・デバイスで実装してもよい。
【００８９】
本明細書で説明した当該プロセスおよび論理フローを、入力データで動作し出力を生成することで機能を実施するための１つまたは複数のコンピュータ・プログラムを実行する１つまたは複数のプログラム可能コンピュータにより実施することができる。当該プロセスおよび論理フローはまた、特殊目的論理回路、例えば、ＦＰＧＡ（フィールドプログラム可能ゲートアレイ）またはＡＳＩＣ（特殊用途向け集積回路）により実施でき、装置を特殊目的論理回路、例えば、ＦＰＧＡ（フィールドプログラム可能ゲートアレイ）またはＡＳＩＣ（特殊用途向け集積回路）として実装することもできる。
【００９０】
コンピュータ・プログラムの実行に適したコンピュータは、例として、汎用目的または特殊目的マイクロプロセッサまたはその両方、または任意の他種の中央演算装置を含み、または、それに基づくことができる。一般的に、中央演算装置は、読取専用メモリまたはランダム・アクセスメモリまたはその両方から命令およびデータを受信する。コンピュータの本質的な要素は、命令を実施または実行するための中央演算装置および命令およびデータを格納するための１つまたは複数のメモリデバイスである。一般的に、コンピュータはまた、データを格納するための１つまたは複数の大容量記憶デバイス、例えば、磁気、磁気光ディスク、または光ディスクを含むか、またはデータを送受信するようにそれらに動作可能に接続される。しかし、コンピュータはかかるデバイスを有する必要はない。さらに、コンピュータを、幾つか例を挙げると、別のデバイス、例えば、携帯電話、パーソナルデジタルアシスタント（ＰＤＡ）、モバイル・オーディオまたはビデオ・プレイヤ、ゲーム・コンソール、全地球測位システム（ＧＰＳ）受信機、またはポータブル記憶デバイス、例えば、ユニバーサル・シリアル・バス（ＵＳＢ）フラッシュ・ドライブに埋め込むことができる。
【００９１】
コンピュータ・プログラム命令およびデータを格納するのに適したコンピュータ可読媒体は、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュ・メモリデバイスと、磁気ディスク、例えば、内部ハード・ディスクまたは取外し可能ディスクと、磁気光ディスクと、ＣＤＲＯＭおよびＤＶＤ−ＲＯＭディスクにより、例示的な半導体メモリデバイスを含む、全ての形態の不揮発性メモリ、媒体およびメモリデバイスを含む。当該プロセッサおよび当該メモリは特殊目的論理回路により補完するかまたは当該回路に組み込むことができる。
【００９２】
ユーザとの対話を提供するために、本明細書で説明した主題の実施形態を、ディスプレイデバイス、例えば、ＣＲＴ（カソード・レイ・チューブ）モニタ、ＬＣＤ（液晶ディスプレイ）モニタ、または、情報を当該ユーザに表示するためのＯＬＥＤディスプレイ、ならびに入力を当該コンピュータに提供するための入力デバイス、例えば、キーボード、マウス、または存在センシティブディスプレイまたは他のサーフェスを有するコンピュータで実装することができる。他種のデバイスをユーザとの対話を提供するためにも使用でき、例えば、当該ユーザに提供されるフィードバックは、センサフィードバック、例えば、視覚的フィードバック、可聴フィードバック、または触覚フィードバックからなる任意の形態であることができ、および当該ユーザからの入力を音響、会話、または触覚入力を含む任意の形態で受信することができる。さらに、コンピュータは、リソースを当該ユーザにより使用されるデバイスと送受信することで、例えば、ユーザのクライアント・デバイス上のウェブ・ブラウザに当該ウェブ・ブラウザから受信された要求に応答してウェブ・ページを送信することで、ユーザと対話することができる。
【００９３】
本明細書で説明した主題の実施形態を、バックエンドコンポーネントを、例えば、データサーバとして含むか、またはミドルウェアコンポーネント、例えば、アプリケーションサーバを含むか、またはフロントエンドコンポーネント、例えば、ユーザがそれを通じて本明細書で説明した主題の実装と対話できるグラフィカルユーザ・インタフェースまたはウェブ・ブラウザを有するクライアントコンピュータ、または１つまたは複数のかかるバックエンド、ミドルウェア、またはフロントエンドコンポーネントの任意の組合せを含むコンピューティング・システムで実装することができる。当該システムのコンポーネントは任意の形態または媒体のデジタルデータ通信、例えば、通信ネットワークにより相互接続されることができる。通信ネットワークの例はローカル・エリアネットワーク（「ＬＡＮ」）および広域ネットワーク（「ＷＡＮ」）、例えば、インターネットを含む。
【００９４】
当該コンピューティング・システムはクライアントおよびサーバを含むことができる。クライアントおよびサーバは一般に互いから離れており、一般に通信ネットワークを通じて対話する。クライアントおよびサーバの当該関係は、当該夫々のコンピュータ上で実行され互いに対してクライアントサーバ関係を有するコンピュータ・プログラムにより生ずる。
【００９５】
本明細書は多数の具体的な実装詳細を含むが、これらを、クレームされうるもの任意の発明の範囲に対する制限として解釈すべきではなく、特定の発明の特定の実施形態に固有でありうる特徴の説明として理解すべきである。別々の実施形態の文脈において本明細書で説明した特定の特徴をまた、単一の実施形態における組合せで実装することができる。反対に、単一の実施形態の文脈で説明した様々な特徴をまた、複数の実施形態で別々にまたは任意の適切な部分的組合せで実装することができる。さらに、特徴は特定の組合せで動作するように上述され最初にそのようにクレームされているかもしれないが、クレームされた組合せからの１つまたは複数の特徴を幾つかのケースでは当該組合せから実施してもよく当該クレームされた組合せは部分的組合せまたは部分的組合せの変形に関連してもよい。
【００９６】
同様に、動作を図面において特定の順序で説明したが、これは、所望の結果を実現するために、かかる動作を示した特定の順序でまたは逐次的順序で実施されること、または全ての示された動作が実施されることを要求するものと理解されるべきではない。特定の環境において、マルチタスキングおよび並列処理が有利であるかもしれない。さらに、上述の実施形態における様々なシステムモジュールおよびコンポーネントの当該分離は、全ての実施形態においてかかる分離を要求するものと理解されるべきではなく、当該説明されたプログラムコンポーネントおよびシステムを一般に単一のソフトウェア製品に統合するかまたは複数のソフトウェア製品にパッケージ化できることは理解されるべきである。
【００９７】
当該主題の特定の実施形態を説明した。他の実施形態は添付の特許請求の範囲内にある。例えば、特許請求の範囲で記載した動作を異なる順序で実施して、依然として所望の結果を実現することができる。１例として、添付図面に示したプロセスは、所望の結果を実現するために示した特定の順序、または逐次的順序を必ずしも要求しない。特定の実装において、マルチタスキングおよび並列処理が有利であるかもしれない。
【符号の説明】
【００９８】
１００  計算グラフ・システム
１０２  クライアント
１０４  セッション・マネージャ
１０６  実行器
１０８  プレーサ
１１４  ネットワーク
１１６  デバイス
１１８  デバイス
１２０  デバイス
１２２  デバイス
【図１Ａ】
0006636630.tif 000002
【図１Ｂ】
0006636630.tif 000003
【図２Ａ】
0006636630.tif 000004
【図２Ｂ】
0006636630.tif 000005
【図２Ｃ】
0006636630.tif 000006
【図３】
0006636630.tif 000007
【図４Ａ】
0006636630.tif 000008
【図４Ｂ】
0006636630.tif 000009
【図５】
0006636630.tif 000010