(57)【要約】  ニューラルネットワークの実行の順序を決定するためのシステムおよび方法が提供される。たとえば、ニューラルネットワークを示すデータおよび制限されたメモリ空間における利用可能なメモリの量を示すデータが取得され得る。ニューラルネットワークは、複数の演算子を含むことができる。次いで、ニューラルネットワークに関連する実行の順序が決定され得る。実行の順序は、複数の演算子の各々を実行する順序を指定する。実行の順序は、制限されたメモリ空間における利用可能なメモリに少なくとも部分的に基づいて決定される。特に、実行の順序を取得するために、ニューラルネットワークを表すグラフに対して1つまたは複数のグラフ探索アルゴリズムが実行され得る。
2019501451.tif 000002
【特許請求の範囲】
【請求項１】
ニューラルネットワークの実行の順序を決定するコンピュータ実装方法であって、
1つまたは複数のコンピューティングデバイスによって、ニューラルネットワークのグラフを記述するデータを取得するステップであって、前記ニューラルネットワークは複数の演算子を含む、ステップと、
前記1つまたは複数のコンピューティングデバイスによって、制限されたメモリ空間における利用可能なメモリの量を示すデータを取得するステップと、
前記1つまたは複数のコンピューティングデバイスによって、前記制限されたメモリ空間における利用可能なメモリの前記量を上回らないメモリ使用を生じさせる、前記複数の演算子の実行の順序を決定するために、前記グラフに対して少なくとも1つのグラフ探索アルゴリズムを実行するステップと
を含む方法。
【請求項２】
前記1つまたは複数のコンピューティングデバイスによって、前記複数の演算子の各演算子に関する第1のメモリアドレスを決定するステップであって、各第1のメモリアドレスは、対応する演算子の出力データを記憶すべき、前記制限されたメモリ空間におけるロケーションを指定する、ステップと、
前記1つまたは複数のコンピューティングデバイスによって、前記複数の演算子のうちの少なくとも1つの演算子に関する第2のメモリアドレスを決定するステップであって、各第2のメモリアドレスは、対応する演算子の実行に関連する一時的データを記憶すべき、前記制限されたメモリ空間におけるロケーションを指定する、ステップと
をさらに含む、請求項1に記載のコンピュータ実装方法。
【請求項３】
前記第1のメモリアドレスおよび前記第2のメモリアドレスは、前記ニューラルネットワークの前記決定された実行の順序に少なくとも部分的に基づいて決定される、請求項2に記載のコンピュータ実装方法。
【請求項４】
前記1つまたは複数のコンピューティングデバイスによって、前記少なくとも1つのグラフ探索アルゴリズムを実行するステップは、
前記1つまたは複数のコンピューティングデバイスによって、前記ニューラルネットワークの実行の1つまたは複数の候補順序を識別するステップと、
前記1つまたは複数のコンピューティングデバイスによって、実行の各候補順序に従って、前記ニューラルネットワークの実行に関連するメモリ要件を決定するステップと、
前記1つまたは複数のコンピューティングデバイスによって、前記決定されたメモリ要件に少なくとも部分的に基づいて、実行の順序を選択するステップと
を含む、請求項1から3のいずれか一項に記載のコンピュータ実装方法。
【請求項５】
前記1つまたは複数のコンピューティングデバイスによって、前記少なくとも1つのグラフ探索アルゴリズムを実行するステップは、
第2の演算子が実行されたときに、前記ニューラルネットワークの実行に関連するピークメモリ消費が増えないような、第1の演算子と前記第2の演算子との間の移行を示す1つまたは複数の強制的移行を、前記1つまたは複数のコンピューティングデバイスによって識別するステップと、
前記1つまたは複数のコンピューティングデバイスによって、前記実行の順序に前記強制的移行のうちの少なくとも1つを追加するステップと
を含む、請求項4に記載のコンピュータ実装方法。
【請求項６】
前記ニューラルネットワークの実行の前記順序は、少なくとも部分的に、主要メトリックとして全時間ピークメモリ使用を使用する最短経路アルゴリズムを使用して決定される、請求項1から5のいずれか一項に記載のコンピュータ実装方法。
【請求項７】
前記1つまたは複数のコンピューティングデバイスによって、前記少なくとも1つのグラフ探索アルゴリズムを実行するステップは、前記1つまたは複数のコンピューティングデバイスによって、前記ニューラルネットワークに1つまたは複数の追加の演算子を追加するステップを含む、請求項1から6のいずれか一項に記載のコンピュータ実装方法。
【請求項８】
前記1つまたは複数のコンピューティングデバイスによって、前記1つまたは複数の追加の演算子を追加するステップは、前記1つまたは複数のコンピューティングデバイスによって、前記制限されたメモリ空間に関連するデフラグ演算子、移動演算子、または並べ替え演算子のうちの少なくとも1つを追加するステップを含む、請求項7に記載のコンピュータ実装方法。
【請求項９】
前記制限されたメモリ空間は、前記ニューラルネットワークを実行するように構成されたプロセッサを伴うオンチップであるスクラッチバッファを含む、請求項1から8のいずれか一項に記載のコンピュータ実装方法。
【請求項１０】
前記1つまたは複数のコンピューティングデバイスによって、1つまたは複数の演算子の実行に必要とされるデータの量が前記制限されたメモリ空間における利用可能なメモリの前記量を上回るときにエラーを決定するステップをさらに含む、請求項1から9のいずれか一項に記載のコンピュータ実装方法。
【請求項１１】
前記1つまたは複数のコンピューティングデバイスによって、前記決定された実行の順序を記憶して、前記ニューラルネットワークの将来の実行が前記記憶された実行の順序に従って発生するようにするステップをさらに含む、請求項1から10のいずれか一項に記載のコンピュータ実装方法。
【請求項１２】
前記1つまたは複数のコンピューティングデバイスによって、前記ニューラルネットワークを実行するように構成されたウェアラブル画像キャプチャデバイスに、前記決定された実行の順序を提供するステップをさらに含む、請求項1から11のいずれか一項に記載のコンピュータ実装方法。
【請求項１３】
前記1つまたは複数のコンピューティングデバイスによって、前記少なくとも1つのグラフ探索アルゴリズムを実行するステップは、
前記実行の順序の1つまたは複数のメモリ要件を必然的に減少させる前記グラフ内の1つまたは複数の強制的移行を識別するステップと、
前記識別された1つまたは複数の強制的移行に少なくとも部分的に基づいて、前記グラフの一部分の探索をプルーニングするステップと
を含む、請求項1から12のいずれか一項に記載のコンピュータ実装方法。
【請求項１４】
前記グラフは、複数のノード、およびそれぞれ前記複数のノードをそれぞれ接続する複数の弧を含み、
前記複数のノードは、複数の探索状態をそれぞれ表し、各探索状態は、演算子の第1のセットおよび演算子の第2のセットを含み、演算子の前記第1のセットは、完了していて、維持される必要がある少なくとも1つの出力を有する演算子を含み、演算子の前記第2のセットは、完了していないが、すべての必要とされる入力が利用可能である演算子を含み、
前記複数の弧は、前記複数の探索状態の間の候補移行をそれぞれ表す、請求項13に記載のコンピュータ実装方法。
【請求項１５】
前記1つまたは複数のコンピューティングデバイスによって、前記少なくとも1つのグラフ探索アルゴリズムを実行するステップは、
所与のノードに関して、そのようなノードのための複数の利用可能な弧のうちの少なくとも1つを、そのような弧が強制的移行を表すかどうかを判断するために分析するステップであって、強制的移行は、使用されるピークメモリを増やさず、強制的移行は、使用される現在のメモリを増やさない、ステップと、
前記利用可能な弧のうちの1つが強制的移行を表すとの判断に応答して、
前記所与のノードのために前記強制的移行としてそのような利用可能な弧を選択するステップ、および
前記グラフの探索空間から他の利用可能な弧をプルーニングするステップと
を含む、請求項14に記載のコンピュータ実装方法。
【請求項１６】
前記1つまたは複数のコンピューティングデバイスによって、前記少なくとも1つのグラフ探索アルゴリズムを実行するステップは、
前記複数の探索状態の複数の調査される探索状態の各々に関する指紋を決定するステップであって、各調査される探索状態に関する前記指紋は、完了した演算子の第3のセットを一意に識別する前記調査される探索状態の1つまたは複数のフィールドへのハッシュ関数の適用の結果である、ステップと、
2つ以上の調査される探索状態が等しい指紋を有するときを検出するステップと、
等しい指紋を有する2つ以上の調査される探索状態の検出に応答して、等しい指紋を有する前記2つ以上の調査される探索状態のそれぞれの前記メモリ要件の比較に基づいて、等しい指紋を有する前記2つ以上の調査される探索状態のうちの1つを選択するステップと
を含む、請求項15に記載のコンピュータ実装方法。
【請求項１７】
前記ニューラルネットワークの前記複数の演算子の各々に関する少なくとも1つの注釈を提供するステップであって、前記複数の演算子の各々に関する前記少なくとも1つの注釈は、第1のメモリアドレスおよび第2のメモリアドレスを含み、前記第1のメモリアドレスは、前記演算子の出力データが記憶されるべき第1のメモリロケーションを記述し、前記第2のメモリアドレスは、前記演算子の一時的バッファが記憶されるべき第2のロケーションを記述する、ステップ
を含む、請求項1から16のいずれか一項に記載のコンピュータ実装方法。
【請求項１８】
少なくとも1つのプロセッサと、コンピューティングシステムに請求項1から17のいずれか一項に記載の方法を実行させるように前記少なくとも1つのプロセッサによって実行可能な命令を記憶する少なくとも1つのコンピュータ可読記録媒体とを含むコンピューティングシステム。
【請求項１９】
少なくとも1つのプロセッサによって実行されると、前記少なくとも1つのプロセッサに動作を実行させる命令を記憶するコンピュータ可読記録媒体であって、前記動作は、
ニューラルネットワークを示すデータを取得することであって、前記ニューラルネットワークは複数の演算子を含む、取得することと、
制限されたメモリ空間における利用可能なメモリの量を示すデータを取得することと、
それぞれ前記ニューラルネットワークの前記複数の演算子の間の複数の依存性を記述するグラフを作成することと、
前記ニューラルネットワークに関する実行の順序を決定するために、少なくとも1つのグラフ探索アルゴリズムを実行することであって、前記実行の順序は、前記複数の演算子の各々を実行する順序を指定し、前記実行の順序は、前記制限されたメモリ空間における前記利用可能なメモリに少なくとも部分的に基づいて決定される、実行することと
を含み、
少なくとも1つのグラフ探索アルゴリズムを実行することは、
前記実行の順序の1つまたは複数のメモリ要件を必然的に減少させる前記グラフ内の1つまたは複数の強制的移行を識別することと、
前記識別された1つまたは複数の強制的移行に少なくとも部分的に基づいて、前記グラフの一部分の探索をプルーニングすることと
を含む、コンピュータ可読記録媒体。
【請求項２０】
前記少なくとも1つのプロセッサに、前記少なくとも1つのグラフ探索アルゴリズムを実行させる前記命令は、前記少なくとも1つのプロセッサに、主要メトリックとしてピークメモリ使用を使用する少なくとも1つの最短経路アルゴリズムを実行させる、請求項19に記載のコンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ニューラルネットワークの実行に関し、より詳細には、制限されたメモリ空間において使用するニューラルネットワークの実行の順序を決定することに関する。
【背景技術】
【０００２】
近年、コンピュータビジョンおよび他の機械学習アプリケーションがますます人気になってきている。たとえば、そのようなアプリケーションは、ますます多くの設定および環境において実装されている。そのようなアプリケーションは、人気が高まるにつれて、複雑性も高まっている。このようにして、限られたメモリリソースを有するモバイルデバイス上に実装されたコンピュータビジョンアプリケーションは、そのような限られたメモリリソースによって制限され得る。
【０００３】
そのような限られたメモリ設定では、メモリアプリケーションおよびメモリ効率が非常に重要になり得る。たとえば、モバイルデバイスによるコンピュータビジョンおよび/または他の機械学習アプリケーションの実行に必要とされるメモリの量を限定することが有利であり得る。
【０００４】
一例として、いくつかの制限されたメモリ環境では、ニューラルネットワークの実行中に、制限されたメモリを適切に割り振ることができない場合、悲劇的となり得、たとえば、ニューラルネットワークを実行しているデバイスの完全な再ブートが必要になり得る。別の言い方をすれば、ニューラルネットワークの実行に必要とされるメモリが、メモリの最大利用可能分を上回る(たとえば、制限を上回る)場合、ある種のデータは失われるか、あるいは記憶できないことがあり、ニューラルネットワークの実行が失敗することがある。
【発明の概要】
【課題を解決するための手段】
【０００５】
本開示の実施形態の態様および利点は、部分的に以下の説明に記載され、または説明からわかることがあり、または実施形態の実践を通じてわかることがある。
【０００６】
本開示の1つの例示的な態様は、ニューラルネットワークの実行の順序を決定するコンピュータ実装方法を対象とする。本方法は、1つまたは複数のコンピューティングデバイスによって、ニューラルネットワークのグラフを記述するデータを取得するステップを含む。ニューラルネットワークは、複数の演算子を含む。本方法は、1つまたは複数のコンピューティングデバイスによって、制限されたメモリ空間における利用可能なメモリの量を示すデータを取得するステップをさらに含む。本方法は、1つまたは複数のコンピューティングデバイスによって、ニューラルネットワークに関連する実行の順序を決定するために、グラフに対して少なくとも1つのグラフ探索アルゴリズムを実行するステップをさらに含む。実行の順序は、複数の演算子の各々を実行する順序を指定する。実行の順序は、制限されたメモリ空間における利用可能なメモリの量を上回らないメモリ使用を生じさせる。
【０００７】
本開示の別の例示的な態様は、コンピューティング装置によって実行されると、本明細書で説明または特許請求される方法をコンピューティング装置に実行させる機械可読命令を含むコンピュータプログラムを対象とする。
【０００８】
本開示の別の例示的な態様は、ニューラルネットワークの動的に割り振られた実行を静的に割り振られた実行に変換するコンピューティングシステムを対象とする。コンピューティングシステムは、少なくとも1つのプロセッサと、少なくとも1つのプロセッサによって実行可能な命令を記憶する少なくとも1つの非一時的コンピュータ可読媒体とを含む。命令の実行により、コンピューティングシステムは、ニューラルネットワークのグラフを記述するデータを取得する。ニューラルネットワークは、複数の演算子を含む。命令の実行により、コンピューティングシステムは、制限されたメモリ空間における利用可能なメモリの量を記述するデータを取得する。命令の実行により、コンピューティングシステムは、制限されたメモリ空間における利用可能なメモリの量を上回らないメモリ使用を生じさせる、ニューラルネットワークの複数の演算子に関する実行順序を決定するために、グラフに対して少なくとも1つのグラフ探索アルゴリズムを実行する。命令の実行により、コンピューティングシステムは、決定された実行順序を記憶し、ニューラルネットワークの将来の実行は、記憶された実行順序に従って発生する。
【０００９】
本開示の別の例示的な態様は、命令を記憶する非一時的コンピュータ可読媒体を対象とする。命令は、少なくとも1つのプロセッサによって実行されると、少なくとも1つのプロセッサに動作を実行させる。動作は、ニューラルネットワークを示すデータを取得することを含む。ニューラルネットワークは、複数の演算子を含む。命令は、制限されたメモリ空間における利用可能なメモリの量を示すデータを取得することをさらに含む。命令は、それぞれニューラルネットワークの複数の演算子の間の複数の依存性を記述するグラフを作成することをさらに含む。命令は、ニューラルネットワークに関する実行の順序を決定するために、少なくとも1つのグラフ探索アルゴリズムを実行することをさらに含む。実行の順序は、複数の演算子の各々を実行する順序を指定する。実行の順序は、制限されたメモリ空間における利用可能なメモリに少なくとも部分的に基づいて決定される。少なくとも1つのグラフ探索アルゴリズムを実行することは、実行の順序の1つまたは複数のメモリ要件を必然的に減少させるグラフ内の1つまたは複数の強制的移行(forced transition)を識別することと、識別された1つまたは複数の強制的移行に少なくとも部分的に基づいて、グラフの一部分の探索をプルーニングする(pruning)こととを含む。
【００１０】
本開示の他の例示的な態様は、ニューラルネットワークに関連する探索グラフに関する実行の順序を決定するためのシステム、装置、有形、非一時的コンピュータ可読媒体、ユーザインターフェース、メモリデバイス、および電子デバイスを対象とする。
【００１１】
様々な実施形態のこれらおよび他の特徴、態様および利点は、以下の説明および添付の特許請求の範囲を参照して一層理解されよう。本明細書に組み込まれ、本明細書の一部となる添付の図面は、本開示の実施形態を示しており、説明とともに、関連する原理を説明する働きをする。
【００１２】
当業者を対象とする実施形態の詳細な説明は、本明細書に記載されており、以下の添付の図を参照する。
【図面の簡単な説明】
【００１３】
【図１】本開示の例示的な実施形態による、例示的な探索グラフを示す図である。
【図２】本開示の例示的な実施形態による、探索グラフの実行に関連する例示的なメモリ割振りを示す図である。
【図３】本開示の例示的な実施形態による、探索グラフに関連する実行の順序を決定する例示的な方法の流れ図である。
【図４】本開示の例示的な実施形態による、1つまたは複数の候補移行を使用して探索グラフに関連する実行の順序を決定する例示的な方法の流れ図である。
【図５】本開示の例示的な実施形態による、1つまたは複数の強制的移行を使用して探索グラフに関連する実行の順序を決定する例示的な方法の流れ図である。
【図６】本開示の例示的な実施形態による、例示的なシステムを示す図である。
【発明を実施するための形態】
【００１４】
ここで、実施形態が詳細に言及され、その1つまたは複数の例が図面に示される。各例は、本開示の限定ではなく、実施形態の説明として提供される。実際、本開示の範囲または趣旨から逸脱することなく、実施形態に対して様々な修正および変更が行われてよいことが、当業者には明らかであろう。たとえば、一実施形態の一部として図示または説明される特徴は、またさらなる実施形態をもたらすために、別の実施形態とともに使用されてよい。したがって、本開示の態様がそのような修正および変更をカバーすることが意図されている。
【００１５】
本開示の例示的な態様は、演算子のグラフによって表される計算タスクのための静的メモリ割振りを決定するためのシステムおよび方法を対象とする。たとえば、演算子のグラフは、たとえば、畳み込みニューラルネットワーク、長期短期記憶ニューラルネットワークなどのような、様々な適切なタイプのニューラルネットワークに関連付けられ得る。特に、本開示のシステムおよび方法は、制限されたメモリ空間内のニューラルネットワークの実行に関連する様々なメモリ制限を満たすニューラルネットワークに関する実行順序を決定することができる。本開示のシステムおよび方法はまた、様々なメモリ制限を満たすようにニューラルネットワークの実行中に入力データ、出力データ、および一時的実行データが記憶され得るメモリアドレスの名簿を提供することができる。さらに、本開示の態様は、説明のために畳み込みニューラルネットワークを参照して以下で説明するが、本開示のシステムおよび方法は、複数の相互接続された演算子を含む他の形態のニューラルネットワークまたは他の計算タスクに等しく適用可能である。
【００１６】
本開示の態様の1つの例示的な適用では、畳み込みニューラルネットワークのグラフを記述するデータおよび制限されたメモリ空間における利用可能なメモリの量を示すデータが取得され得る。畳み込みニューラルネットワークは、相互接続された複数の演算子を含むことができ、グラフは、そのような複数の演算子およびそれらの関連するそれぞれの依存性を記述することができる。複数の演算子に関する実行の順序が、制限されたメモリ空間における利用可能なメモリの量に少なくとも部分的に基づいて決定され得る。たとえば、実行の順序は、畳み込みニューラルネットワークを実行するために必要とされるピークメモリ消費を最小化または低減するように決定され得る。特に、本開示のシステムおよび方法は、実行順序を決定するために、1つまたは複数のグラフ探索アルゴリズム(たとえば、主要メトリックとしてピークメモリ消費を有する最短経路アルゴリズム)を実行することができる。本開示は、1つまたは複数のグラフ探索アルゴリズムの効率的な演算を可能にする様々な加速技法をさらに提供する。
【００１７】
より詳細には、畳み込みニューラルネットワークを示すデータは、畳み込みニューラルネットワークにおける複数の演算子の1つまたは複数の接続(たとえば、入力/出力依存性)を記述するグラフ(たとえば、有向非巡回グラフまたは他のグラフ)を含むことができる。たとえば、畳み込みニューラルネットワークにおける各演算子は、入力データを消費することおよび/または出力データを生成することができる。いくつかの実装形態では、入力データは、1つまたは複数の入力データバッファまたは入力テンソルを含むことができ、出力データは、1つまたは複数の出力データバッファまたは出力テンソルを含むことができる。特に、演算子の実行は、出力データを生成することができる。出力データは、消費された入力データに少なくとも部分的に基づいて決定され得る。例示的な実装形態では、出力データは次いで、1つまたは複数の後続演算子にフィードされてよく、その結果、出力データが1つまたは複数の後続演算子のための入力データになる。このようにして、演算子は、演算子の実行に必要とされる入力データを提供する演算子の各々が実行されるまで、実行できない。畳み込みニューラルネットワークにおける演算子は、畳み込み演算子、プーリング演算子、および/または様々な他の適切な演算子を含むことができる。
【００１８】
制限されたメモリ空間は、たとえば、畳み込みニューラルネットワークを実行するように構成されたプロセッサを伴う静的バッファオンチップを含む、任意の制限されたメモリ空間であり得る。各演算子の実行は、メモリ空間の一定の量を必要とし得る。たとえば、演算子の実行に必要とされるメモリ空間の量は、演算子によって消費される入力データの量、演算子によって生成される出力データの量、および/または演算子の実行に必要とされる一時的メモリ空間の量に少なくとも部分的に依存し得る。さらに、利用可能なメモリ空間の量は、まだ実行されていない1つまたは複数の後続演算子の実行になお必要とされる他の演算子の出力データによってさらに制限され得る。
【００１９】
本開示の例示的な態様によれば、畳み込みニューラルネットワークの実行の順序が、制限されたメモリ空間に少なくとも部分的に基づいて決定され得る。特定の実装形態では、実行の順序は、畳み込みニューラルネットワークの実行に必要とされるメモリのピーク量を最小化または低減するように決定され得る。たとえば、いくつかの実装形態では、畳み込みニューラルネットワークの実行のあらゆる可能な順序に関して、ピークメモリ要件が決定され得る。このようにして、最低ピークメモリ要件を有する実行の順序が選択され得る。
【００２０】
例示的な実装形態では、実行の順序は、少なくとも部分的に、1つまたは複数のグラフ探索アルゴリズムを実行することによって決定され得る。たとえば、1つまたは複数のグラフ探索アルゴリズムは、ダイクストラアルゴリズム、フロイド-ワーシャルアルゴリズム、ジョンソンアルゴリズム、ビタビアルゴリズム、および/または様々な他の適切な最短経路アルゴリズムなど、1つまたは複数の最短経路アルゴリズムを含むことができる。最短経路アルゴリズムは、主要メトリックとして実行順序のピークメモリ使用を使用することができる。
【００２１】
いくつかの実装形態では、追加の探索グラフ中の各ノードは、探索状態に対応し得る。各ノードは、対応する探索状態からの1つまたは複数の候補移行に対応する、そこから延びる弧を有することができる。グラフ中の第1の探索状態からグラフ中の第2の探索状態への移行は、たとえば、畳み込みニューラルネットワークの演算子のうちの1つの実行を含むことができる。したがって、いくつかの実装形態では、探索状態間の各移行は、現在実行可能である特定の演算子の実行に関連付けられ得る。特に、演算子は、演算子によって消費される入力データの各インスタンスが、演算子による使用に利用可能である場合、現在実行可能であり得る。
【００２２】
より詳細には、いくつかの実装形態では、探索グラフは、複数のノードおよびそれぞれ複数のノードをそれぞれ接続する複数の弧を含む。複数のノードは、複数の探索状態をそれぞれ表すことができる。いくつかの実装形態では、各探索状態は、完了した演算子のすべてに対応する演算子のセットによって定義され得る。各探索状態はさらに、完了したすべての演算子からなるセットに関連する全ピークメモリ消費によって定義され得る。
【００２３】
いくつかの実装形態では、各探索状態は、「関連」演算子からなる1つまたは複数のより小さいセットによって定義され得る。たとえば、そのような実装形態では、各探索状態は、演算子の第1のセットおよび演算子の第2のセットによって定義され得る。演算子の第1のセットは、完了していて、1つまたは複数の後に実行される演算子による使用のために維持される必要がある少なくとも1つの出力を有する演算子を含むことができる。演算子の第2のセットは、完了していないが、すべての必要とされる入力が利用可能である演算子を含むことができる。複数の弧は、複数の探索状態の間の候補移行をそれぞれ表すことができ、探索状態から移行することは、演算子の第2のセットに含まれる演算子のうちの1つを実行することを含む。この方式での「関連」演算子のより小さいセットの使用により、探索状態が必要とする記憶が少なくなり、処理の高速化が可能になる。
【００２４】
さらなる実装形態では、探索状態は、たとえば、現在のメモリ使用、そのような探索状態の過去および現在におけるピークメモリ消費、親探索状態の指紋、ならびに親探索状態から現在の探索状態に移行するために実行された最後の演算子のインデックスを含む追加情報によっても定義され得る。現在のメモリ使用など、この追加情報の一部は、各探索状態に関して提供された他の情報に基づいて再計算され得るが、各探索状態に関するそのような追加情報の記憶により、そのような再計算を実行する必要がなくなる。さらに、親状態の指紋および実行された最後の演算子のインデックスなど、探索状態に関する「引き返し(backtrack)」情報を含めることで、再帰引き返し(recursive backtrack)および所与の探索状態につながった演算の完全な逆シーケンスの作成が可能になる。より詳細には、すべての演算子の完了に対応する「最終」探索状態に達したとき、そのような再帰引き返しは、演算の完全な逆シーケンスを生じさせることができ、次いで、シーケンスは、ニューラルネットワークの将来の実行に望ましい実行順序を取得するために反転させられ得る。
【００２５】
例示的な実装形態では、探索状態ごとに、実行されるべき後続演算子を決定するために、1つまたは複数の候補移行が分析され得る。たとえば、候補移行のうちの1つが選択され、実行の順序に追加され得る。候補移行は、候補移行に対応する演算子の実行に関連するメモリ要件に少なくとも部分的に基づいて選択され得る。たとえば、候補移行は、各候補移行のメモリ要件を比較し、メモリ空間の最も少ない量を必要とする候補移行を選択することによって、選択され得る。
【００２６】
いくつかの実装形態では、実行の順序は、1つまたは複数の強制的移行に少なくとも部分的に基づいて決定され得る。いくつかの実装形態では、強制的移行は、第1の探索状態から第2の探索状態への移行であってよく、関連する移行演算子の実行は、必要とされるメモリのピーク量を増やさず、さらに、現在必要とされるメモリの量を増やさない。そのような実装形態では、強制的移行が識別されたとき、第1の探索状態からの1つまたは複数の他の候補移行は、除外あるいは探索空間からプルーニングされてよく、その結果、1つまたは複数の除外された候補移行が、実行の順序を決定する際にグラフ探索アルゴリズムによって考慮されなくなる。このようにして、グラフ探索アルゴリズムのパフォーマンスに関連する計算時間を大幅に減らすことができる。
【００２７】
別の例として、いくつかの実装形態では、本開示のシステムおよび方法は、各調査される探索状態に関する指紋を決定することができる。各調査される探索状態に関する指紋は、実行されたか完了した演算子のセットを一意に識別する調査される探索状態のフィールドへのハッシュ関数の適用の結果であり得る。いくつかの実装形態では、上記のように、親探索状態の指紋および実行された最後の演算子のインデックスが、再帰引き返しおよび所与の探索状態につながった演算の完全な逆シーケンスの作成のために使用され得る。このようにして、「最終」探索状態(たとえば、実行されるべき最後の演算子に対応する探索状態)に達すると、最終探索状態につながった演算の完全なシーケンスが決定され得る。さらに、本開示のシステムおよび方法は、2つ以上の調査される探索状態が等しい指紋を有するときを検出し、等しい指紋を有する2つ以上の調査される探索状態の検出に応答して、等しい指紋を有する2つ以上の調査される探索状態のそれぞれのメモリ要件の比較に基づいて、等しい指紋を有する2つ以上の調査される探索状態のうちの1つを選択することができる。したがって、いくつかの実装形態では、2つの等しい探索状態のうちの「最良のもの」のみが、最良探索状態に指紋をマッピングする辞書において維持される。
【００２８】
さらに別の例として、いくつかの実装形態では、畳み込みニューラルネットワークを表す探索グラフが、演算子ごとにトラバースされ得、各演算子の実行に必要とされるメモリが、(たとえば、演算子の実行をシミュレートすることによって)監視あるいは追跡され得る。強制的移行が識別されたとき、強制的移行は、実行の順序に追加され得る。
【００２９】
本開示の別の態様によれば、畳み込みニューラルネットワークにおける各演算子の実行に関連する制限されたメモリ空間のメモリ割振りが、さらに決定され得る。たとえば、メモリ割振りは、畳み込みニューラルネットワークの実行の前に決定される静的メモリ割振りであり得る。このようにして、1つまたは複数のメモリアドレスが、畳み込みニューラルネットワークにおいて生成される出力データに割り当てられ得る。メモリ割振りは、決定された実行の順序に少なくとも部分的に基づいて決定され得る。たとえば、決定された実行の順序での畳み込みニューラルネットワークの実行に従って、データが制限されたメモリ空間に記憶され、かつ/または制限されたメモリ空間から解放されるように、メモリ割振りが決定され得る。
【００３０】
特に、各演算子は、制限されたメモリ空間内の1つまたは複数のメモリアドレスを割り当てられ得る。たとえば、各演算子は、演算子の実行によって生成された出力データが記憶され得る出力アドレスを割り当てられ得る。メモリアドレスは、メモリアドレスを指定する注釈として表され得る。さらに、1つまたは複数の演算子は、実行のために、一時的バッファなどの一時的メモリ空間を必要とし得る。必要に応じて、一時的データメモリアドレスがさらに割り当てられ得る。上記のように、畳み込みネットワークにおける演算子は、1つまたは複数の後に実行される演算子のための入力データになる出力データを生成し得る。このようにして、畳み込みネットワークにおいて1つまたは複数の後に実行される演算子の実行に必要とされる入力データの各インスタンスは、1つまたは複数の後に実行される演算子の各々が実行されるまで、制限されたメモリ空間にとどまることができる。1つまたは複数の後に実行される演算子の各々が実行されたとき、制限されたメモリ空間から入力データが解放され得る。このようにして、本開示の例示的な実装形態によれば、後続データは解放されたデータにとって代わり得る。
【００３１】
例示的な実装形態では、メモリ割振りに少なくとも部分的に基づいて畳み込みニューラルネットワークが修正または編集され得る。たとえば、メモリ割振りに少なくとも部分的に基づいて、畳み込みニューラルネットワークに1つまたは複数の追加の演算子が追加され得る。1つまたは複数の追加の演算子は、畳み込みニューラルネットワークの実行に関係する制限されたメモリ空間の使用の効率を改善するように構成され得る。たとえば、1つまたは複数の追加の演算子は、デフラグ演算子、移動演算子、並べ替え演算子、および/または制限されたメモリ空間におけるメモリの割振りに関連する様々な他の適切な演算子を含み得る。制限されたメモリ空間および決定された実行の順序に少なくとも部分的に基づいて、望ましい場合に畳み込みニューラルネットワークに追加の演算子が挿入され得る。
【００３２】
決定されると、畳み込みニューラルネットワークの実行の順序および/または畳み込みニューラルネットワークの実行に関連するメモリ割振りを示すデータが、畳み込みニューラルネットワークの将来の実行において使用するために記憶され得る。一例では、そのようなデータは次いで、畳み込みニューラルネットワークを実行するように構成されたリモートコンピューティングデバイスに提供され得る。たとえば、リモートコンピューティングデバイスは、畳み込みニューラルネットワークを実行するように構成されたウェアラブル画像キャプチャデバイスであり得る。
【００３３】
本開示のさらなる実装形態では、本開示のグラフ探索技法が、一連の強制的移行または強制的移行のセットを識別することによって加速し得る。たとえば、いくつかの例では、特定の探索状態が、強制的移行である候補移行を有しないことがある。一方、基準のセットを満たすそのような探索状態からのいくつかの移行からなるセットを識別することが可能であり得る(たとえば、セット内の移行のすべてからなる組合せが「完全に良好」であると言われ得る)。
【００３４】
だが、考慮すべき移行の潜在的セットの数が飛躍的に増えるので、少数の「良好な」移行セット候補のみが調査されるように、この加速技法がヒューリスティックに使用され得る。一例として、それぞれの依存タスクがすべて実行可能であるすべての保留出力Oに関して、本開示のシステムおよび方法は、Oに依存するすべての実行可能タスクを実行する移行のセットを特に考慮し得る。
【００３５】
本開示の別の態様によれば、本明細書で説明するグラフ探索技法は、強制的移行の識別に関連する制限または基準を緩和あるいは一般化することによって、さらに加速し得る。したがって、「最適な」解答を返す探索アルゴリズムを必要とする代わりに、「良好そうな」解が代わりに許容可能であり得る。別の言い方をすれば、強制的移行の識別に関連する基準を緩和すると、完全に最適ではない結果が返され得るが、より多くの強制的移行の識別が生じ、それによって、探索を実行するために必要とされる時間量が大幅に減る。
【００３６】
ここで図を参照して、本開示の例示的な実施形態について、さらに詳細に説明する。たとえば、図1は、本開示の例示的な実施形態による、例示的な探索グラフ100を示す。特に、探索グラフ100は、複数の相互接続された演算子102〜118を有する有向非巡回グラフである。様々な他の適切なグラフが使用されてよいことが諒解されよう。探索グラフ100は、演算子が一度に1つ実行される直列グラフ、または複数の演算子が同時に実行され得る並列グラフであり得る。探索グラフ100は、本開示のいくつかの態様を説明するのを助けるために、1つの単純化された例として提供されている。本開示のシステムおよび方法は、探索グラフ100よりもかなり複雑である探索グラフに適用可能である。
【００３７】
探索グラフ100は、畳み込みニューラルネットワークもしくは長期短期記憶ネットワークなどのニューラルネットワークに対応することができ、またはグラフ100は、相互接続された演算子の様々な他のネットワークに対応し得る。各ノード(たとえば、ノード102、104、106、108、110、112、114、116、および118)は、畳み込みニューラルネットワークの演算子に対応し得る。複数の演算子に関連する接続(たとえば、矢印)は、複数の演算子の1つまたは複数の入力/出力依存性を示す。たとえば、接続101は、演算子104が演算子104の実行のために演算子102の出力を必要とすることを表す。このようにして、演算子104は、演算子102が実行されるまで実行できない。
【００３８】
例示的な実装形態では、探索グラフ100の実行の順序を決定するために、探索グラフ100に対して探索アルゴリズムが実行され得る。実行の順序は、探索グラフ100の実行に関連する制限されたメモリ空間における利用可能なメモリの量に少なくとも部分的に基づいて決定され得る。たとえば、実行の順序は、探索グラフ100の実行に必要とされるピークメモリ消費を最小化または低減するように決定され得る。特に、実行の順序は、少なくとも部分的に、主要メトリックとしてピークメモリを有するグラフ探索アルゴリズムを使用して決定され得る。たとえば、グラフ探索アルゴリズムは、ダイクストラアルゴリズムまたは他の最短経路アルゴリズムなどの最短経路アルゴリズムであり得る。
【００３９】
上記のように、例示的な実装形態では、実行順序は、実行のあらゆる可能な順序をトラバースし、実行の所望の順序(たとえば、最低ピークメモリ要件を有する実行の順序)を選択することによって決定され得る。
【００４０】
いくつかの実装形態では、実行の順序は、1つまたは複数の探索状態に対応するノードおよびそれぞれの探索状態の間の候補移行に対応する弧を有する追加のグラフを分析する(たとえば、追加のグラフに関するグラフ探索アルゴリズムを実行する)ことによって決定され得る。示されているように、探索状態は、演算子の第1および第2のセットに少なくとも部分的に基づいて定義され得る。たとえば、演算子の第1のセットは、実行されたが(たとえば、実行のために出力を必要とする後続の演算子に起因して)出力が維持される必要がある1つまたは複数の演算子を含むことができる。演算子の第2のセットは、実行されていないが現在実行可能である(たとえば、必要とされる入力のすべてが利用可能である)1つまたは複数の演算子を含むことができる。そのような実施形態では、各探索状態は、現在実行可能な演算子の実行に対応する1つまたは複数の候補移行を有し得る。たとえば、1つの例示的な探索状態が、少なくとも部分的に、完了した演算子102および104ならびに現在実行可能な演算子106および110によって定義され得る。このようにして、例示的な探索状態は、現在実行可能な演算子106および110のそれぞれの実行に関連する2つの候補移行を有し得る。たとえば、その場合に各候補移行が分析され得、候補移行のうちの1つが選択され、実行の順序に追加され得る。たとえば、候補移行は、移行に関連する演算子の実行に必要とされるメモリの量に少なくとも部分的に基づいて選択され得る。移行が選択されると、選択された移行に少なくとも部分的に基づいて、新しい探索状態が決定され得る。
【００４１】
代替実装形態では、探索状態に関連する1つまたは複数の強制的移行が決定され得る。強制的移行は、そのような移行に関連する演算子の実行がピークメモリ消費の量を増やさず、現在必要とされるメモリの量を増やさない移行であり得る。強制的移行が決定あるいは識別されると、強制的移行は、実行の順序に追加され得る。このようにして、探索状態に関連する1つまたは複数の他の候補移行が、実行の順序を決定する際の考慮から除外され(たとえば、探索空間からプルーニングされ)得る。たとえば、演算子104の出力に対応する探索状態に関する例を続けると、演算子106の実行に関連する候補移行が強制的移行であると判断された場合、強制的移行は、実行の順序に追加され得、演算子110の実行に関連する候補移行は、考慮から除外されるか、あるいは探索空間からプルーニングされ得る。このようにして、演算子110の実行に関連する候補移行を分析することなく、実行の順序に強制的移行が追加され得る。いくつかの実施形態では、探索状態が複数の強制的移行を有する場合に、決定論的移行が選択されるように、決定論的順序で候補移行が分析され得る。
【００４２】
いくつかの実装形態では、探索状態に関連する強制的移行セットが決定され得る。たとえば、強制的移行セットは、その探索状態から追加の探索状態からなるセットへの複数の連続的な移行からなるセットであってよく、その場合に移行のセットは、ピークメモリ消費を増やさず、現在のメモリ消費を増やさない。いくつかの実装形態では、強制的移行セットは、強制的移行セットを決定するために各候補移行を分析することによって決定され得る。このようにして、ピークおよび/または現在のメモリ消費を、1つの個別の移行は増やすことがあり、強制的移行セットは全体として増やさない。そのような実施形態では、実行の順序に強制的移行セットが追加され得る。
【００４３】
いくつかの実装形態では、探索状態は、現在必要とされるメモリの量、探索状態の過去および現在に使用されるメモリのピーク量、実行された最後の演算子のインデックス、ならびに/または親探索状態の指紋によってさらに定義され得る。
【００４４】
探索状態の指紋は、探索状態を定義する1つまたは複数のパラメータへのハッシュ関数の適用の結果であり得る。たとえば、各探索状態に関する指紋は、実行されたかまたは完了した演算子のセットを一意に識別する調査される探索状態のフィールドへのハッシュ関数の適用の結果であり得る。いくつかの実装形態では、1つまたは複数の探索状態は等しいものであり得る。等しい探索状態は、少なくとも部分的に探索状態の指紋から決定され得る。上記のように、等しい探索状態が識別されたとき、等しい探索状態のうちの1つが選択され、「最良」探索状態を指紋にマッピングする辞書において維持され得る。
【００４５】
上記のように、探索グラフ100の実行に関連するメモリはさらに、たとえば、探索グラフ100の実行の順序を決定することに関連して(たとえば、探索グラフ100によって表される畳み込みニューラルネットワークの実行の前に)静的に割り振られ得る。たとえば、図2は、本開示の例示的な実施形態による、探索グラフの実行に関連する例示的なメモリ割振り方式200を示す。特に、図2は、演算子102、104および106をその順序で実行することに関連する制限されたメモリ空間のメモリ割振りを示す。
【００４６】
メモリ割振り202は、演算子102のための入力データ(INPUT)、出力データ(conv0)、および一時的データ(temprary0)に関連するデータバッファまたはテンソルを示す。より詳細には、演算子102は、入力データを消費し、入力データに少なくとも部分的に基づいて出力データ(conv0)を生成する畳み込み演算子であり得る。演算子102の実行は、一時的データ(temprary0)をさらに必要とし得る。
【００４７】
探索グラフ100の演算の順序を決定するとき、各演算子の実行に必要とされるデータのために、1つまたは複数のメモリロケーションまたはアドレスが決定され得る。このようにして、各演算子のためのメモリ割振りが、決定された実行の順序に少なくとも部分的に基づいて決定され得る。たとえば、メモリ割振り202は、入力データ、出力データ、および一時的データのためのメモリロケーションを含むことができる。メモリ割振り202は、演算子102が実行されるときに、割振り202によって示されるアドレスを実行中のデバイスが提供されるように、実行順序内での演算子102への注釈が付けられ得る。
【００４８】
上記のように、演算子が実行されるとき、その演算子の実行に必要とされる入力データが、(たとえば、他のまだ実行されていない演算子が実行のために同じ入力データを必要としない限り)メモリ空間から解放され得る。たとえば、メモリ割振り204は、演算子104の実行に関連するメモリ割振りを示す。図示のように、メモリ割振り202の入力データが解放されており、メモリ割振り202の入力データを以前記憶したメモリは利用可能であるが、割振り204によるデータ記憶のためにアクティブに割り振られていない。演算子102の出力データは、(図1の接続101によって証明されているように)演算子104の実行のための入力として必要とされるので、conv0データは、制限されたメモリ空間内で割り振られたままである。さらに、演算子102に関連する一時的データが解放され得る。図示のように、演算子104に関連する出力データ(たとえば、maxpool0)の一部分が、temporary0データが以前割り振られたロケーションに割り振られている。
【００４９】
メモリ割振り206は、演算子106の実行に関連付けられる。図1に示すように、演算子106の実行は、演算子102および104からの入力を必要とする。このようにして、演算子102のconv0データおよび演算子104のmaxpool0データが、演算子106による使用のために制限されたメモリ空間において維持される。演算子106の実行は、出力データ(conv1)を生成し、一時的データ(temporary1)を必要とする。演算子106の実行後、演算子102からの出力データ(たとえば、conv0)は、さらなる演算子のための入力として必要とされないので解放され得る。
【００５０】
例示的な実施形態では、探索グラフ100および/または関連する実行順序が、追加の演算子を追加するために編集され得る。たとえば、追加の演算子は、メモリ割振りに関連する演算子を含むことができる。特に、追加の演算子は、デフラグ演算子、移動演算子、並べ替え演算子、および様々な他の適切な演算子を含むことができる。そのような追加の演算子は、制限されたメモリ空間に少なくとも部分的に基づいて、グラフに追加され得る。たとえば、連続するメモリ空間の量を増やすために、探索グラフ100中の様々な位置において1つまたは複数の追加の演算子が追加され得る。このようにして、メモリ割振りの効率が改善され得る。
【００５１】
一例として、ニューラルネットワークは、将来の演算子のために維持される必要がある入力/出力データ(たとえば、入力/出力テンソル)からなる2〜3個の比較的大きいセットを、入力/出力データからなるいくつかのより小さいセットに加えて有することが多い。制限されたメモリ空間では、そのようなシナリオは、望ましくない量のフラグメンテーションを生じさせ、この状況では、解放されたメモリが十分あるが、かかるメモリが、それぞれ小さすぎる部分に細分化されている。したがって、本明細書で説明するデフラグ演算子を含めることで、そのようなフラグメンテーションを除去あるいは低減して、ニューラルネットワークの実行を可能にすることができる。いくつかの実装形態では、デフラグ演算子が、次の所望の演算子の実行を可能にするために必要とされる各場合において、実行の順序に追加され得る。たとえば、探索状態または演算子の間の各移行において、次の所望の演算子の実行を可能にするためにデフラグ演算子の追加が必要とされるかどうかが判断され得る。
【００５２】
図2に含まれるメモリの視覚表現を全般的に参照すると、1つの例示的なデフラグ演算子は、データの各ブロックを、データの左端のブロックから、できるだけ表現の左側に(たとえば、メモリからメモリへのコピーによって)動かすための移動命令を含むことができる。
【００５３】
図3は、本開示の例示的な実施形態による、探索グラフに関連する実行の順序を決定する例示的な方法(300)の流れ図を示す。方法(300)は、図6に示すコンピューティングデバイスうちの1つまたは複数など、1つまたは複数のコンピューティングデバイスによって実施され得る。さらに、図3は、図示および説明の目的で特定の順序で実行されるステップを示す。当業者は、本明細書で提供する開示を使用して、本明細書で説明する方法のうちのいずれかのステップが、本開示の範囲から逸脱することなく様々な方法で適合、再配置、拡大、省略、または修正されてよいことを理解されよう。
【００５４】
(302)において、方法(300)は、探索グラフを示すデータを取得するステップを含む。探索グラフは、複数の相互接続された演算子を有する畳み込みニューラルネットワークまたは他のネットワークのグラフに対応し得る。たとえば、演算子は、1つまたは複数の入力バッファを消費し、1つまたは複数の出力バッファを出力し得る。出力バッファは、入力バッファに少なくとも部分的に基づいて決定され得る。次いで、演算子によって生成された出力バッファがフィードフォワードされ、1つまたは複数の後続演算子のための入力バッファになり得る。
【００５５】
いくつかの実装形態では、(302)において取得されたデータは、演算子を表すノードおよび演算子間の入力/出力依存性を表す弧を含む有向非巡回グラフを示し得る。そのような実装形態のうちのいくつかでは、方法(300)は、有向非巡回グラフに基づいて追加の探索グラフを作成するステップをさらに含むことができる。たとえば、追加の探索グラフは、探索状態を表すノードおよびそれぞれの探索状態の間の候補移行を表す弧を有することができる。他の実装形態では、(302)において取得されたデータは、探索状態を表すノードとともに追加の探索グラフを示し得る。
【００５６】
(304)において、方法(300)は、制限されたメモリ空間における利用可能なメモリの量を示すデータを取得するステップを含むことができる。たとえば、制限されたメモリ空間は、たとえば、畳み込みニューラルネットワークを実行するように構成されたプロセッサを伴う静的バッファオンチップを含む、任意の制限されたメモリ空間であり得る。制限されたメモリ空間は、畳み込みニューラルネットワークの実行に関連するデータを記憶するように構成され得る。制限されたメモリ空間は、ニューラルネットワークを実行するように構成されたプロセッサを伴うオンチップであるスクラッチバッファを含み得る。
【００５７】
(306)において、方法(300)は、探索グラフ(たとえば、畳み込みニューラルネットワーク)の実行の順序を決定するステップを含むことができる。いくつかの実装形態では、実行の順序は、探索グラフの実行に関連するピークメモリ消費が制限されたメモリ空間におけるメモリの量を上回らないように決定され得る。たとえば、ピークメモリが制限されたメモリ空間におけるメモリの量を上回るとき、利用可能なメモリを上回っていることを示すエラーが決定され得る。
【００５８】
さらなる実装形態では、実行の順序は、探索グラフの実行に関連するピークメモリ消費を低減または最小化するように決定され得る。たとえば、いくつかの実装形態では、実行の可能な各順序が、実行の各順序のピークメモリ消費を決定するためにトラバースされ得る。最低ピークメモリ消費を有する実行の順序が選択され得る。
【００５９】
他の実装形態では、1つまたは複数の探索状態を分析することによって、実行の順序が決定され得る。上記のように、各探索状態は、完了した演算子のすべてに対応する演算子のセットによって定義され得る。各探索状態はさらに、完了したすべての演算子からなるセットに関連する全ピークメモリ消費によって定義され得る。
【００６０】
いくつかの実装形態では、各探索状態は、「関連」演算子からなる1つまたは複数のより小さいセットによって定義され得る。たとえば、そのような実装形態では、各探索状態は、少なくとも部分的に、実行されたがメモリ空間において維持される必要がある出力を有する1つまたは複数の演算子に対応する演算子の第1のセットによって定義され得る。探索状態はさらに、少なくとも部分的に、まだ実行されていないが現在利用可能である1つまたは複数の演算子に対応する演算子の第2のセットによって定義され得る。
【００６１】
図4および図5に関してより詳細に説明するように、1つまたは複数の探索状態から1つまたは複数の候補移行が決定され得る。実行の順序は、候補移行に関連するメモリ消費要件に少なくとも部分的に基づいて決定され得る。
【００６２】
(308)において、方法(300)は、探索グラフ中の各演算子に関連するメモリ割振りを決定するステップを含むことができる。メモリ割振りは、決定された実行の順序に少なくとも部分的に基づいて決定され得る。このようにして、メモリ割振りは、実行の順序に従って各演算子の実行中に制限されたメモリ空間において利用可能となるメモリ空間の量に少なくとも部分的に基づいて決定され得る。いくつかの実装形態では、メモリ割振りは、実行の順序の決定に関連して決定され得る。メモリ割振りは、演算子の実行に関連するデータを記憶すべき、制限されたメモリ空間における1つまたは複数のメモリロケーションを指定することができる。
【００６３】
メモリ割振りは、制限されたメモリ空間におけるメモリ空間要件に従って、1つまたは複数の追加の演算子を含むように、グラフおよび/または実行順序を修正または編集するステップをさらに含み得る。上記のように、そのような追加の演算子は、デフラグ演算子、移動演算子、並べ替え演算子などを含むことができる。
【００６４】
(310)において、方法(300)は、畳み込みニューラルネットワークの将来の実行のために、実行の順序およびメモリ割振りを記憶するステップを含むことができる。(312)において、方法(300)は、畳み込みニューラルネットワークを実行するように構成されたリモートコンピューティングデバイスに、実行の順序および/またはメモリ割振りを示すデータを提供するステップを含むことができる。たとえば、リモートコンピューティングデバイスは、スマートフォン、タブレット、ラップトップコンピュータ、デスクトップコンピュータ、ウェアラブルコンピューティングデバイスなどのユーザデバイスであり得る。実行の順序および/またはメモリ割振りを示すデータを受信すると、リモートコンピューティングデバイスは、実行の順序およびメモリ割振りに従って畳み込みニューラルネットワークを実行することができる。
【００６５】
上記のように、1つまたは複数の候補移行を分析することによって、実行の順序が決定され得る。たとえば、図4は、本開示の例示的な実施形態による、ニューラルネットワークに関する実行の順序を決定する例示的な方法(400)の流れ図を示す。(402)において、方法(400)は、1つまたは複数の候補移行を識別するステップを含むことができる。候補移行は、現在実行可能な演算子の潜在的実行に対応し得る。いくつかの実施形態では、1つまたは複数の候補移行は、探索状態に関連付けられ得る。このようにして、候補移行は、(たとえば、特定の演算子の実行を通じた)そのような探索状態から新しい探索状態への潜在的移行にそれぞれ対応し得る。
【００６６】
(404)において、方法(400)は、各候補移行に関連するメモリ要件を決定するステップを含むことができる。特に、候補移行に関連するメモリ要件は、候補移行に関連する演算子が実行される場合に使用されることになるメモリ空間の量を指定することができる。このようにして、探索状態からの各候補移行が、各候補移行のメモリ要件を決定するために分析され得る。
【００６７】
いくつかの実装形態では、(404)における各候補移行に関連するメモリ要件を決定するステップは、候補移行ごとに、デフラグ演算子の追加が、そのような候補移行の実行を可能にするために必要とされる(たとえば、そのような候補移行に関連する特定の演算子の実行を可能にするために必要とされる)かどうかを判断するステップをさらに含むことができる。デフラグ演算子が必要とされる場合、(406)においてそのような候補移行が最終的に選択される場合に、そのようなデフラグ演算子が探索グラフおよび/または実行の順序に追加され得る。
【００６８】
(406)において、方法(400)は、選択移行として候補移行を選択するステップを含むことができる。候補移行は、各候補移行に関連する決定されたメモリ要件に少なくとも部分的に基づいて選択され得る。いくつかの実装形態では、選択移行は、最低メモリ要件を有する候補移行であり得る。他の実装形態では、選択移行は、様々な他の所望のメモリ特性に基づいて選択され得る。
【００６９】
(408)において、方法(400)は、実行の順序に選択移行を追加するステップを含むことができる。このようにして、探索グラフの実行の順序は、演算子ごとに、1つまたは複数の候補移行に少なくとも部分的に基づいて決定され得る。たとえば、実行の順序に選択移行が追加された後、選択移行に関連する演算子の出力を含む新しい探索状態が決定され得る。
【００７０】
いくつかの実施形態では、探索グラフの実行の順序は、1つまたは複数の強制的移行に少なくとも部分的に基づいて決定され得る。たとえば、図5は、本開示の例示的な実施形態による、探索グラフの実行の順序を決定する例示的な方法(500)の流れ図を示す。(502)において、方法(500)は、1つまたは複数の候補移行を識別するステップを含むことができる。たとえば、上記のように、候補移行は探索状態に関連付けられ得る。
【００７１】
(504)において、方法(500)は、候補移行のうちの少なくとも1つに関するメモリ要件を決定するステップを含むことができる。(506)において、方法(500)は、強制的移行を識別するステップを含むことができる。上記のように、強制的移行は、メモリ消費のピーク量および/またはメモリ消費の現在の量を増やさない探索状態からの移行であり得る。いくつかの実装形態では、候補移行は、候補移行のうちの1つが強制的移行として識別されるまで分析され得る。
【００７２】
(508)において、方法(500)は、実行の順序に強制的移行を追加するステップを含むことができる。たとえば、強制的移行を識別したことに応答して、実行の順序に強制的移行が追加され得る。このようにして、強制的移行が識別されると、まだ分析されていない探索状態に関連する候補移行を分析する必要なしに、実行の順序に強制的移行が追加され得る。これにより、実行の順序を決定することに関連する計算の時間およびリソースを節約することができる。
【００７３】
図6は、本開示の例示的な態様による、方法およびシステムを実装するために使用され得る例示的なコンピューティングシステム600を示す。システム600は、ネットワーク640を介して1つまたは複数のクライアントデバイス630と通信するサーバ610を含むクライアントサーバアーキテクチャを使用して実装され得る。システム600は、単一のコンピューティングデバイスなど、他の適切なアーキテクチャを使用して実装されてよいことが諒解されよう。
【００７４】
システム600は、ウェブサーバなどのサーバ610を含む。サーバ610は、本明細書で説明する技法による畳み込みニューラルネットワークに関する実行の順序を決定するように構成された静的アナライザをホストすることができる。サーバ610は、任意の適切なコンピューティングデバイスを使用して実装され得る。サーバ610は、1つまたは複数のプロセッサ612と、1つまたは複数のメモリデバイス614とを有し得る。サーバ610はまた、ネットワーク640を介して1つまたは複数のクライアントデバイス630と通信するために使用されるネットワークインターフェースを含むことができる。ネットワークインターフェースは、たとえば、送信機、受信機、ポート、コントローラ、アンテナ、または他の適切な構成要素を含む、1つまたは複数のネットワークとインターフェースするための任意の適切な構成要素を含むことができる。
【００７５】
1つまたは複数のプロセッサ612は、マイクロプロセッサ、マイクロコントローラ、集積回路、論理デバイス、または他の適切な処理デバイスなど、任意の適切な処理デバイスを含むことができる。1つまたは複数のメモリデバイス614は、限定はしないが、非一時的コンピュータ可読媒体、RAM、ROM、ハードドライブ、フラッシュドライブ、または他のメモリデバイスなど、1つまたは複数のコンピュータ可読媒体を含むことができる。1つまたは複数のメモリデバイス614は、1つまたは複数のプロセッサ612によって実行され得るコンピュータ可読命令616を含む、1つまたは複数のプロセッサ612によってアクセス可能な情報を記憶することができる。命令616は、1つまたは複数のプロセッサ612によって実行されると、1つまたは複数のプロセッサ612に動作を実行させる命令の任意のセットであり得る。たとえば、命令616は、順序アナライザ620およびメモリアロケータ622を実施するために1つまたは複数のプロセッサ612によって実行され得る。たとえば、順序アナライザ620は、本開示の例示的な実施形態に従って、探索グラフに関連する実行の順序を決定するように構成され得る。メモリアロケータ622は、探索グラフの実行に関連する制限されたメモリ空間内のメモリ割振りを決定するように構成され得る。
【００７６】
図6に示すように、1つまたは複数のメモリデバイス614はまた、1つまたは複数のプロセッサ612によって取り出され、操作され、作成され、または記憶され得るデータ616を記憶することができる。データ616は、たとえば、探索グラフデータ、メモリデータ、および他のデータを含むことができる。データ616は、1つまたは複数のデータベースに記憶され得る。1つまたは複数のデータベースは、高帯域LANもしくはWANによってサーバ610に接続されてよく、またはネットワーク640を通じてサーバ610に接続されてもよい。1つまたは複数のデータベースは、複数の場所に位置するように分割され得る。
【００７７】
サーバ610は、ネットワーク640を介して1つまたは複数のクライアントデバイス630とデータを交換することができる。いくつかの実施形態では、サーバ610は、たとえば、ワイヤード接続を介して、1つまたは複数のクライアントデバイス630とデータを直接交換することができる。図6には2つのクライアントデバイス630が示されているが、ネットワーク640を介してサーバ610に任意の数のクライアントデバイス630が接続されてよい。クライアントデバイス630の各々は、汎用コンピュータ、専用コンピュータ、ラップトップ、デスクトップ、モバイルデバイス、ナビゲーションシステム、スマートフォン、タブレット、ウェアラブルコンピューティングデバイス、ウェアラブル画像キャプチャデバイス、1つもしくは複数のプロセッサを有するディスプレイ、または他の適切なコンピューティングデバイスなど、任意の適切なタイプのコンピューティングデバイスであり得る。
【００７８】
サーバ610と同様に、クライアントデバイス630は、1つまたは複数のプロセッサ632とメモリ634とを含むことができる。1つまたは複数のプロセッサ632は、1つまたは複数の中央処理装置(CPU)、効率的に画像をレンダリングするか他の特殊な計算を実行する専用のグラフィックス処理ユニット(GPU)、および/または他の処理デバイスを含むことができる。メモリ634は、1つまたは複数のコンピュータ可読媒体を含むことができ、1つまたは複数のプロセッサ632によって実行され得る命令636およびデータ638を含む、1つまたは複数のプロセッサ632によってアクセス可能な情報を記憶することができる。
【００７９】
たとえば、メモリ634は、畳み込みニューラルネットワークを実行するための命令636を記憶することができる。特に、サーバ610はクライアントデバイス630に、畳み込みニューラルネットワークに関する実行の順序と、実行の順序での各演算子のための入力バッファ、出力バッファ、および/または一時的バッファに関するメモリアドレスを提供する1つまたは複数のメモリ割振りとを含む命令636を提供することができる。クライアントデバイス630は、実行の順序および1つまたは複数のメモリ割振りに従って畳み込みニューラルネットワークを実施することができる。
【００８０】
図6のクライアントデバイス630は、タッチスクリーン、タッチパッド、データ入力キー、スピーカー、および/または音声認識に適したマイクロフォンなど、ユーザからの情報を提供および受信するための様々な入力/出力デバイスを含むことができる。たとえば、クライアントデバイス630は、本開示の例示的な態様に従って、意味上の場所の名前(semantic place name)を表示するユーザインターフェースを提示するためのディスプレイデバイス635を有し得る。
【００８１】
クライアントデバイス630はまた、ネットワーク640を介して1つまたは複数のリモートコンピューティングデバイス(たとえば、サーバ610)と通信するために使用されるネットワークインターフェースを含むことができる。ネットワークインターフェースは、たとえば、送信機、受信機、ポート、コントローラ、アンテナ、または他の適切な構成要素を含む、1つまたは複数のネットワークとインターフェースするための任意の適切な構成要素を含むことができる。
【００８２】
ネットワーク640は、ローカルエリアネットワーク(たとえば、イントラネット)、ワイドエリアネットワーク(たとえば、インターネット)、セルラーネットワーク、またはそれらの何らかの組合せなど、任意のタイプの通信ネットワークであり得る。ネットワーク640はまた、クライアントデバイス630とサーバ610との間の直接接続を含むことができる。一般に、サーバ610とクライアントデバイス630との間の通信は、ネットワークインターフェースを介して任意のタイプのワイヤードおよび/またはワイヤレス接続を使用して、様々な通信プロトコル(たとえば、TCP/IP、HTTP、SMTP、FTP)、符号化もしくはフォーマット(たとえば、HTML、XML)、および/または保護方式(たとえば、VPN、セキュアなHTTP、SSL)を使用して行われ得る。
【００８３】
本明細書で説明する技術は、サーバ、データベース、ソフトウェアアプリケーション、および他のコンピュータベースのシステム、ならびに講じられる措置およびそのようなシステムとの間で送られる情報に言及している。当業者は、コンピュータベースのシステムの固有の柔軟性が、構成要素間のタスクおよび機能の多種多様な可能な構成、組合せ、および分割を実現することを認識されよう。たとえば、本明細書で説明するサーバプロセスは、単一のサーバまたは共同して動作する複数のサーバを使用して実施され得る。データベースおよびアプリケーションは、単一のシステム上に実装されること、または複数のシステムに分散されることがある。分散された構成要素は、連続的に、または並行して動作し得る。
【００８４】
本主題は、その特定の例示的な実施形態に関して詳細に説明されているが、当業者は、前述の内容の理解を得ると、そのような実施形態の改変形態、変更形態、および等価物を容易に生成し得ることが諒解されよう。したがって、本開示の範囲は、限定としてではなく例としてのものであり、本開示は、当業者には直ちに明らかになるように、本主題に対するそのような修正、変更および/または追加を含めることを妨げない。
【００８５】
特に、本開示のシステムおよび方法は、畳み込みニューラルネットワークに関する静的な割振りおよび実行順序に関して説明されているが、本開示は、他の形態のニューラルネットワークまたは他の多層モデルに等しく適用可能で有用である。特に、本開示の態様は、様々な入力バッファ、出力バッファ、および一時的バッファのメモリ要件を有する複数の相互接続された演算子を含む任意の計算プロセスを表すグラフに適用され得る。
【符号の説明】
【００８６】
100  探索グラフ
101  接続
102  演算子、ノード
104  演算子、ノード
106  演算子、ノード
108  演算子、ノード
110  演算子、ノード
112  演算子、ノード
114  演算子、ノード
116  演算子、ノード
118  演算子、ノード
200  メモリ割振り方式
202  メモリ割振り、割振り
204  メモリ割振り、割振り
206  メモリ割振り
300  方法
400  方法
500  方法
600  システム
610  サーバ
612  プロセッサ
614  メモリデバイス
616  コンピュータ可読命令、命令、データ
620  順序アナライザ
622  メモリアロケータ
630  クライアントデバイス
632  プロセッサ
634  メモリ
635  ディスプレイデバイス
636  命令
638  データ
640  ネットワーク
【図１】
2019501451.tif 000003
【図２】
2019501451.tif 000004
【図３】
2019501451.tif 000005
【図４】
2019501451.tif 000006
【図５】
2019501451.tif 000007
【図６】
2019501451.tif 000008
【国際調査報告】
2019501451.tif 000009
2019501451.tif 000010