(57)【要約】  本開示の実施形態は、ノード間並列処理のためにDAG計算モデルを分割し、サブDAG計算モデルを構築するための技術を提供する。特に、複数のプロセッサがDAG計算をDAG計算モデルの各ノード内で複数の非相互依存サブノードに分割する方法が提供される。複数のプロセッサは、少なくとも2つの異なる処理ユニットタイプを含む。複数のプロセッサは、複数のサブDAG計算を構築し、各サブDAG計算は、DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む。複数のプロセッサは、複数のサブDAG計算のそれぞれを並列で処理する。
2022500755.tif 000002
【特許請求の範囲】
【請求項１】
有向非巡回グラフ（DAG）計算を処理するための方法であって、
複数のプロセッサによって、前記DAG計算を各ノード内で複数の非相互依存サブノードに分割するステップであって、前記複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を備える、ステップと、
前記複数のプロセッサによって、複数のサブDAG計算を構築するステップであって、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む、ステップと、
前記複数のプロセッサによって、前記複数のサブDAG計算のそれぞれの処理をスケジューリングするステップと、
前記複数のプロセッサによって、前記複数のサブDAG計算のそれぞれを並列で処理するステップと
を含む方法。
【請求項２】
前記複数のプロセッサによって、前記複数のサブDAG計算に中間共有メモリを割り当てるステップをさらに含む、請求項1に記載の方法。
【請求項３】
前記複数のプロセッサによって、各サブDAG計算の各サブノードの処理をスケジューリングするステップをさらに含む、請求項1または2に記載の方法。
【請求項４】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項1から4のいずれか一項に記載の方法。
【請求項６】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項1から5のいずれか一項に記載の方法。
【請求項７】
それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している、請求項1から6のいずれか一項に記載の方法。
【請求項８】
前記構築ステップは、手動で、または前記複数のプロセッサによって実行されるコンパイラによって自動的に行われる、請求項1から7のいずれか一項に記載の方法。
【請求項９】
前記DAG計算のための入力を受信するステップをさらに含む、請求項1から8のいずれか一項に記載の方法。
【請求項１０】
前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するステップをさらに含む、請求項1から9のいずれか一項に記載の方法。
【請求項１１】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項1から10のいずれか一項に記載の方法。
【請求項１２】
前記分割するステップは、均一な非相互依存サブノードを含む、請求項1から11のいずれか一項に記載の方法。
【請求項１３】
前記分割するステップは、不均一な非相互依存サブノードを含む、請求項1から11のいずれか一項に記載の方法。
【請求項１４】
前記分割するステップは、境界が重複する非相互依存サブノードを含む、請求項1から11のいずれか一項に記載の方法。
【請求項１５】
各サブノードは、前記DAG計算のそれぞれのノードに関連付けられたサブタスクである、請求項1から14のいずれか一項に記載の方法。
【請求項１６】
前記DAG計算の1つ以上のノードは階層的に分割される、請求項1から15のいずれか一項に記載の方法。
【請求項１７】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する、請求項1から16のいずれか一項に記載の方法。
【請求項１８】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である、請求項1から17のいずれか一項に記載の方法。
【請求項１９】
有向非巡回グラフ（DAG）計算を処理するためのコンピュータ実施方法であって、
複数のプロセッサによって、前記DAG計算を各ノード内で複数の非相互依存サブノードに分割するステップであって、前記複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を備える、ステップと、
前記複数のプロセッサによって、複数のサブDAG計算を構築するステップであって、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む、ステップと、
前記複数のプロセッサによって、前記複数のサブDAG計算のそれぞれの処理をスケジューリングするステップと、
前記複数のプロセッサによって、前記複数のサブDAG計算のそれぞれを並列で処理するステップと
を含むコンピュータ実施方法。
【請求項２０】
前記複数のプロセッサによって、前記複数のサブDAG計算に中間共有メモリを割り当てるステップをさらに含む、請求項19に記載のコンピュータ実施方法。
【請求項２１】
前記複数のプロセッサによって、各サブDAG計算の各サブノードの処理をスケジューリングするステップをさらに含む、請求項19または20に記載のコンピュータ実施方法。
【請求項２２】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項19から21のいずれか一項に記載のコンピュータ実施方法。
【請求項２３】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項19から22のいずれか一項に記載のコンピュータ実施方法。
【請求項２４】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項19から23のいずれか一項に記載のコンピュータ実施方法。
【請求項２５】
それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している、請求項19から24のいずれか一項に記載のコンピュータ実施方法。
【請求項２６】
前記構築ステップは、手動で、または前記複数のプロセッサによって実行されるコンパイラによって自動的に行われる、請求項19から25のいずれか一項に記載のコンピュータ実施方法。
【請求項２７】
前記DAG計算のための入力を受信するステップをさらに含む、請求項19から26のいずれか一項に記載のコンピュータ実施方法。
【請求項２８】
前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するステップをさらに含む、請求項19から27のいずれか一項に記載のコンピュータ実施方法。
【請求項２９】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項19から28のいずれか一項に記載のコンピュータ実施方法。
【請求項３０】
前記分割するステップは、均一な非相互依存サブノードを含む、請求項19から29のいずれか一項に記載のコンピュータ実施方法。
【請求項３１】
前記分割するステップは、不均一な非相互依存サブノードを含む、請求項19から29のいずれか一項に記載のコンピュータ実施方法。
【請求項３２】
前記分割するステップは、境界が重複する非相互依存サブノードを含む、請求項19から29のいずれか一項に記載のコンピュータ実施方法。
【請求項３３】
各サブノードは、前記DAG計算のそれぞれのノードに関連付けられたサブタスクである、請求項19から32のいずれか一項に記載のコンピュータ実施方法。
【請求項３４】
前記DAG計算の1つ以上のノードは階層的に分割される、請求項19から33のいずれか一項に記載のコンピュータ実施方法。
【請求項３５】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する、請求項19から34のいずれか一項に記載のコンピュータ実施方法。
【請求項３６】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である、請求項19から35のいずれか一項に記載のコンピュータ実施方法。
【請求項３７】
有向非巡回グラフ（DAG）計算を処理するためのコンピュータ命令を記憶する非一時的コンピュータ可読媒体であって、前記コンピュータ命令は、第1の処理ユニットおよび第2の処理ユニットを備える複数のプロセッサによって実行されたとき、
前記DAG計算を各ノード内で複数の非相互依存サブノードに分割するステップであって、前記複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を備える、ステップと、
複数のサブDAG計算を構築するステップであって、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む、ステップと、
前記サブDAG計算のそれぞれの処理をスケジューリングするステップと、
前記複数のサブDAG計算のそれぞれを並列で処理するステップと
を実行する、非一時的コンピュータ可読媒体。
【請求項３８】
複数のプロセッサによって動作されたとき、前記複数のサブDAG計算に中間共有メモリを割り当てるステップを実行する、請求項37に記載の非一時的コンピュータ可読媒体。
【請求項３９】
複数のプロセッサによって動作されたとき、各サブDAG計算の各サブノードの処理をスケジューリングするステップを実行する、請求項37または38に記載の非一時的コンピュータ可読媒体。
【請求項４０】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項37から39のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４１】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項37から40のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４２】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項37から41のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４３】
それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している、請求項37から42のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４４】
前記構築ステップは、手動で、または前記複数のプロセッサによって実行されるコンパイラによって自動的に行われる、請求項37から43のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４５】
前記複数のプロセッサによって動作されたとき、前記DAG計算のための入力を受信するステップを実行する、請求項37から44のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４６】
複数のプロセッサによって動作されたとき、前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するステップを実行する、請求項37から45のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４７】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項37から46のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４８】
前記分割するステップは、均一な非相互依存サブノードを含む、請求項37から47のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項４９】
前記分割するステップは、不均一な非相互依存サブノードを含む、請求項37から47のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項５０】
前記分割するステップは、境界が重複する非相互依存サブノードを含む、請求項37から47のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項５１】
各サブノードは、前記DAG計算のそれぞれのノードに関連付けられたサブタスクである、請求項37から50のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項５２】
前記DAG計算の1つ以上のノードは階層的に分割される、請求項37から51のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項５３】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する、請求項37から52のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項５４】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である、請求項37から53のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項５５】
有向非巡回グラフ（DAG）計算を処理するためのデバイスであって、
命令を含む非一時的メモリストレージと、
中央処理ユニット（CPU）およびグラフィック処理ユニット（GPU）を備える複数のプロセッサであって、前記複数のプロセッサは、前記非一時的メモリストレージと通信し、前記複数のプロセッサは、
前記DAG計算を各ノード内で複数の非相互依存サブノードに分割し、
複数のサブDAG計算を構築し、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含み、
前記複数のサブDAG計算のそれぞれの処理をスケジューリングし、
前記複数のサブDAG計算のそれぞれを並列で処理する
ために前記命令を実行する、複数のプロセッサと
を備えるデバイス。
【請求項５６】
前記複数のプロセッサは、前記複数のサブDAG計算に中間共有メモリを割り当てるために前記命令を実行する、請求項55に記載のデバイス。
【請求項５７】
前記複数のプロセッサは、各サブDAG計算の各サブノードの処理をスケジューリングするために前記命令を実行する、請求項55または56に記載のデバイス。
【請求項５８】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項55から57のいずれか一項に記載のデバイス。
【請求項５９】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項55から58のいずれか一項に記載のデバイス。
【請求項６０】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項55から59のいずれか一項に記載のデバイス。
【請求項６１】
それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している、請求項55から60のいずれか一項に記載のデバイス。
【請求項６２】
前記構築ステップは、手動で、または前記複数のプロセッサによって実行されるコンパイラによって自動的に行われる、請求項55から61のいずれか一項に記載のデバイス。
【請求項６３】
前記複数のプロセッサは、前記DAG計算のための入力を受信するために前記命令を実行する、請求項55から62のいずれか一項に記載のデバイス。
【請求項６４】
前記複数のプロセッサは、前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するために前記命令を実行する、請求項55から63のいずれか一項に記載のデバイス。
【請求項６５】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項55から64のいずれか一項に記載のデバイス。
【請求項６６】
前記分割するステップは、均一な非相互依存サブノードを含む、請求項55から65のいずれか一項に記載のデバイス。
【請求項６７】
前記分割するステップは、不均一な非相互依存サブノードを含む、請求項55から65のいずれか一項に記載のデバイス。
【請求項６８】
前記分割するステップは、境界が重複する非相互依存サブノードを含む、請求項55から65のいずれか一項に記載のデバイス。
【請求項６９】
各サブノードは、前記DAG計算のそれぞれのノードに関連付けられたサブタスクである、請求項55から68のいずれか一項に記載のデバイス。
【請求項７０】
前記DAG計算の1つ以上のノードは階層的に分割される、請求項55から69のいずれか一項に記載のデバイス。
【請求項７１】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する、請求項55から70のいずれか一項に記載のデバイス。
【請求項７２】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である、請求項55から71のいずれか一項に記載のデバイス。
【請求項７３】
有向非巡回グラフ（DAG）計算を処理するためのデバイスであって、
命令を含む非一時的メモリストレージと、
第1の処理ユニットおよび第2の処理ユニットを備える複数のプロセッサであって、前記第1の処理ユニットおよび前記第2の処理ユニットは、異なるプロセッサタイプであり、前記複数のプロセッサは、前記非一時的メモリストレージと通信し、前記複数のプロセッサは、
前記DAG計算を各ノード内で複数の非相互依存サブノードに分割し、
複数のサブDAG計算を構築し、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含み、
前記複数のサブDAG計算のそれぞれの処理をスケジューリングし、
前記複数のサブDAG計算のそれぞれを並列で処理する
ために前記命令を実行する、複数のプロセッサと
を備えるデバイス。
【請求項７４】
前記複数のプロセッサは、前記複数のサブDAG計算に中間共有メモリを割り当てるために前記命令を実行する、請求項73に記載のデバイス。
【請求項７５】
前記複数のプロセッサは、各サブDAG計算の各サブノードの処理をスケジューリングするために前記命令を実行する、請求項73または74に記載のデバイス。
【請求項７６】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項73から75のいずれか一項に記載のデバイス。
【請求項７７】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項73から76のいずれか一項に記載のデバイス。
【請求項７８】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項73から77のいずれか一項に記載のデバイス。
【請求項７９】
それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している、請求項73から78のいずれか一項に記載のデバイス。
【請求項８０】
前記構築ステップは、手動で、または前記複数のプロセッサによって実行されるコンパイラによって自動的に行われる、請求項73から79のいずれか一項に記載のデバイス。
【請求項８１】
前記複数のプロセッサは、前記DAG計算のための入力を受信するために前記命令を実行する、請求項73から80のいずれか一項に記載のデバイス。
【請求項８２】
前記複数のプロセッサは、前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するために前記命令を実行する、請求項73から81のいずれか一項に記載のデバイス。
【請求項８３】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項73から82のいずれか一項に記載のデバイス。
【請求項８４】
前記分割するステップは、均一な非相互依存サブノードを含む、請求項73から83のいずれか一項に記載のデバイス。
【請求項８５】
前記分割するステップは、不均一な非相互依存サブノードを含む、請求項73から83のいずれか一項に記載のデバイス。
【請求項８６】
前記分割するステップは、境界が重複する非相互依存サブノードを含む、請求項73から83のいずれか一項に記載のデバイス。
【請求項８７】
各サブノードは、前記DAG計算のそれぞれのノードに関連付けられたサブタスクである、請求項73から86のいずれか一項に記載のデバイス。
【請求項８８】
前記第1の処理ユニットおよび前記第2の処理ユニットのそれぞれは、中央処理ユニット（CPU）、グラフィック処理ユニット（GPU）、デジタル信号プロセッサ（DSP）、画像信号プロセッサ（ISP）、映像処理ユニット（VPU）、ニューラルネットワーク処理ユニット（NPU）、および表示処理ユニット（DPU）からなる群から選択される異なるプロセッサタイプである、請求項73から87のいずれか一項に記載のデバイス。
【請求項８９】
相互接続バスリンク、共有メモリユニット、メモリコントローラ、1つ以上のメモリユニット、もしくは周辺相互接続部のうちの少なくとも1つ、またはこれらの組み合わせをさらに備える、請求項73から88のいずれか一項に記載のデバイス。
【請求項９０】
前記DAG計算の1つ以上のノードは階層的に分割される、請求項73から89のいずれか一項に記載のデバイス。
【請求項９１】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する、請求項73から90のいずれか一項に記載のデバイス。
【請求項９２】
1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である、請求項73から91のいずれか一項に記載のデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2018年9月11日に出願された、「順次計算DAGのための異種スケジューリング」と題された米国仮特許出願第62／729，646号の優先権を主張し、そのすべての全体は、参照により組み込まれる。
【０００２】
本開示は、一般にノード間処理に関し、特定の実施形態では、異なる処理ユニットタイプ間のノード間並列処理用の有向非巡回グラフ（DAG）計算モデルを構築するためのシステムおよび方法に関する。
【背景技術】
【０００３】
一般に、順次ライントポロジを用いた有向非巡回グラフ（DAG）モデル化タイプの計算の処理は、ノード内並列処理を使用して実施される。ノード内並列処理では、中央処理ユニット（CPU）、グラフィック処理ユニット（GPU）、または他の特定用途向けプロセッサタイプの複数のコアがそれぞれ、DAGの各ノードを順次操作で処理する。DAGモデル化タイプの計算の各計算タスクは、個々のDAGノードに関連付けまたはマッピングされる。特定の計算では、計算タスクは、より小さなサブタスクに細分され得る。ノード内並列処理では、スケジューリング粒度は、単一ノード内に制限され、ノード間並列処理は、異なる処理ユニットを使用して、複数のDAGノード間または各DAGノード内で達成されない。
【発明の概要】
【０００４】
技術的利点は、一般に、異なる処理ユニットタイプ間のノード間並列処理のための有向非巡回グラフ（DAG）計算モデルの構築を説明する、本開示の実施形態によって達成される。
【課題を解決するための手段】
【０００５】
一実施形態によれば、有向非巡回グラフ（DAG）計算を処理するための方法が提供される。本方法は、複数のプロセッサによって、DAG計算を各ノード内で複数の非相互依存サブノードに分割することを含む。複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を含む。本方法は、複数のプロセッサによって、複数のサブDAG計算を構築することをさらに含む。各サブDAG計算は、DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む。本方法は、複数のプロセッサによって、複数のサブDAG計算のそれぞれを並列で処理することをさらに含む。一例では、本方法は、複数のプロセッサによって、複数のサブDAG計算に中間共有メモリを割り当てることをさらに含む。任意選択で、このような例または別の例では、本方法は、CPUまたはGPUによって、複数のサブDAG計算のそれぞれの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、スケジューリングは、DAG計算のそれぞれのサブノードのタスクタイプに従って、GPUのコアまたはCPUのコアによる各サブノードの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのサブDAG計算のサブノードの処理の完了は、それぞれのサブDAG計算の次のサブノードの処理の依存対象である。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している。任意選択で、上述の例のいずれか1つまたは別の例では、構築は、手動で、または複数のプロセッサによって実行されるコンパイラによって自動的に行われる。任意選択で、上述の例のいずれか1つまたは別の例では、本方法は、DAG計算のための入力を受信することをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、本方法は、DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力することをさらに含む。任意選択で
、上述の例のいずれか1つまたは別の例では、分割は、各ノードに関連付けられたタスクタイプおよび複数のプロセッサのメモリ能力に従う。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、不均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、境界が重複する非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、各サブノードは、DAG計算のそれぞれのノードに関連付けられたサブタスクである。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算の1つ以上のノードが階層的に分割される。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である。
【０００６】
別の実施形態によれば、有向非巡回グラフ（DAG）計算を処理するためのコンピュータ実施方法が提供される。本方法は、複数のプロセッサによって、DAG計算を各ノード内で複数の非相互依存サブノードに分割することを含む。複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を含む。本方法は、複数のプロセッサによって、複数のサブDAG計算を構築することをさらに含む。各サブDAG計算は、DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む。本方法は、複数のプロセッサによって、複数のサブDAG計算のそれぞれを並列で処理することをさらに含む。一例では、本方法は、複数のプロセッサによって、複数のサブDAG計算に中間共有メモリを割り当てることをさらに含む。任意選択で、このような例または別の例では、本方法は、CPUまたはGPUによって、複数のサブDAG計算のそれぞれの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、スケジューリングは、DAG計算のそれぞれのサブノードのタスクタイプに従って、GPUのコアまたはCPUのコアによる各サブノードの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのサブDAG計算のサブノードの処理の完了は、それぞれのサブDAG計算の次のサブノードの処理の依存対象である。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している。任意選択で、上述の例のいずれか1つまたは別の例では、構築は、手動で、または複数のプロセッサによって実行されるコンパイラによって自動的に行われる。任意選択で、上述の例のいずれか1つまたは別の例では、本方法は、DAG計算のための入力を受信することをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、本方法は、DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力することをさら
に含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、各ノードに関連付けられたタスクタイプおよび複数のプロセッサのメモリ能力に従う。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、不均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、境界が重複する非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、各サブノードは、DAG計算のそれぞれのノードに関連付けられたサブタスクである。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算の1つ以上のノードが階層的に分割される。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である。
【０００７】
さらに別の実施形態によれば、有向非巡回グラフ（DAG）計算を処理するためのコンピュータ命令を記憶する非一時的コンピュータ可読媒体が提供される。命令は、第1の処理ユニットおよび第2の処理ユニットを含む複数のプロセッサによって実行されたとき、複数のプロセッサによって、DAG計算を各ノード内で複数の非相互依存サブノードに分割するステップを実行し、複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を含む。命令は、実行されたとき、複数のプロセッサによって、複数のサブDAG計算を構築するステップを実行する。各サブDAG計算は、DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む。命令は、実行されたとき、複数のプロセッサによって、複数のサブDAG計算のそれぞれを並列で処理するステップを実行する。一例では、命令は、複数のプロセッサによって実行されたとき、複数のプロセッサによって、複数のサブDAG計算に中間共有メモリを割り当てるステップを実行する。任意選択で、このような例または別の例では、命令は、実行されたとき、CPUまたはGPUによって、複数のサブDAG計算のそれぞれの処理をスケジューリングするステップを実行する。任意選択で、上述の例のいずれか1つまたは別の例では、スケジューリングは、DAG計算のそれぞれのサブノードのタスクタイプに従って、GPUのコアまたはCPUのコアによる各サブノードの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、命令は、実行されたとき、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含むDAG計算のステップを実行する。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのサブDAG計算のサブノードの処理の完了は、それぞれのサブDAG計算の次のサブノードの処理の依存対象である。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している。任意選択で、上述の例のいずれか1つまたは別の例では、構築は、手動で、または複数のプロセッサによって実行されるコンパイラによって自動的に行われる。任意選択で、上述
の例のいずれか1つまたは別の例では、命令は、実行されたとき、DAG計算のための入力を受信するステップを実行する。任意選択で、上述の例のいずれか1つまたは別の例では、命令は、実行されたとき、DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するステップを実行する。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、各ノードに関連付けられたタスクタイプおよび複数のプロセッサのメモリ能力に従う。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、不均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、境界が重複する非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、各サブノードは、DAG計算のそれぞれのノードに関連付けられたサブタスクである。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算の1つ以上のノードが階層的に分割される。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である。
【０００８】
一実施形態によれば、有向非巡回グラフ（DAG）計算を処理するためのデバイスが提供される。本デバイスは、命令を含む非一時的メモリストレージと、中央処理ユニット（CPU）およびグラフィック処理ユニット（GPU）を備える複数のプロセッサとを含む。複数のプロセッサは、非一時的メモリストレージと通信し、DAG計算を各ノード内で複数の非相互依存サブノードに分割するために命令を実行する。複数のプロセッサは、複数のサブDAG計算を構築するために命令を実行する。各サブDAG計算は、DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む。複数のプロセッサは、複数のサブDAG計算のそれぞれを並列で処理するために命令を実行する。一例では、複数のプロセッサは、複数のサブDAG計算に中間共有メモリを割り当てるために命令を実行する。任意選択で、このような例または別の例では、複数のプロセッサは、CPUまたはGPUによって、複数のサブDAG計算のそれぞれの処理をスケジューリングするために命令を実行する。任意選択で、上述の例のいずれか1つまたは別の例では、スケジューリングは、DAG計算のそれぞれのサブノードのタスクタイプに従って、GPUのコアまたはCPUのコアによる各サブノードの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのサブDAG計算のサブノードの処理の完了は、それぞれのサブDAG計算の次のサブノードの処理の依存対象である。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している。任意選択で、上述の例のいずれか1つまたは別の例では、構築は、手動で、または複数のプロセッサによって実行されるコンパイラによって自動的に行われる。任意選択で、上述の例のいずれか1つまたは別の例では、複数のプロセッサは、DAG計算のための入力を受信するために命令を実行する。任意選択で、上述の例のいずれか1つまたは別の例では、複数のプロセッサは、DAG計算の出力データバッファ、出力画像バッファ
、出力画像ファイル、または出力特徴を出力するために命令を実行する。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、各ノードに関連付けられたタスクタイプおよび複数のプロセッサのメモリ能力に従う。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、不均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、境界が重複する非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、各サブノードは、DAG計算のそれぞれのノードに関連付けられたサブタスクである。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算の1つ以上のノードが階層的に分割される。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である。
【０００９】
別の実施形態によれば、有向非巡回グラフ（DAG）計算を処理するためのデバイスが提供される。本デバイスは、命令を含む非一時的メモリストレージおよび複数のプロセッサを含む。複数のプロセッサは、第1の処理ユニットおよび第2の処理ユニットを含み、第1の処理ユニットおよび第2の処理ユニットは、異なるプロセッサタイプである。複数のプロセッサは、非一時的メモリストレージと通信し、複数のプロセッサは、DAG計算を各ノード内で複数の非相互依存サブノードに分割するために命令を実行する。複数のプロセッサは、複数のサブDAG計算を構築するために命令を実行する。各サブDAG計算は、DAG計算の異なるノードからの非相互依存サブノードを少なくとも含み、複数のサブDAG計算のそれぞれを並列で処理する。一例では、複数のプロセッサは、複数のサブDAG計算に中間共有メモリを割り当てるために命令を実行する。任意選択で、このような例または別の例では、複数のプロセッサは、CPUまたはGPUによって、複数のサブDAG計算のそれぞれの処理をスケジューリングするために命令を実行する。任意選択で、上述の例のいずれか1つまたは別の例では、スケジューリングは、DAG計算のそれぞれのサブノードのタスクタイプに従って、GPUのコアまたはCPUのコアによる各サブノードの処理をスケジューリングすることをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのサブDAG計算のサブノードの処理の完了は、それぞれのサブDAG計算の次のサブノードの処理の依存対象である。任意選択で、上述の例のいずれか1つまたは別の例では、それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している。任意選択で、上述の例のいずれか1つまたは別の例では、構築は、手動で、または複数のプロセッサによって実行されるコンパイラによって自動的に行われる。任意選択で、上述の例のいずれか1つまたは別の例では、複数のプロセッサは、DAG計算のための入力を受信するために命令を実行する。任意選択で、上述の例のいずれか1つまたは別の例では、複数のプロセッ
サは、DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するために命令を実行する。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、各ノードに関連付けられたタスクタイプおよび複数のプロセッサのメモリ能力に従う。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、不均一な非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、分割は、境界が重複する非相互依存サブノードを含む。任意選択で、上述の例のいずれか1つまたは別の例では、各サブノードは、DAG計算のそれぞれのノードに関連付けられたサブタスクである。任意選択で、上述の例のいずれか1つまたは別の例では、第1の処理ユニットおよび第2の処理ユニットのそれぞれは、中央処理ユニット（CPU）、グラフィック処理ユニット（GPU）、デジタル信号プロセッサ（DSP）、画像信号プロセッサ（ISP）、映像処理ユニット（VPU）、ニューラルネットワーク処理ユニット（NPU）、および表示処理ユニット（DPU）からなる群から選択される異なるプロセッサタイプである。任意選択で、上述の例のいずれか1つまたは別の例では、本デバイスは、相互接続バスリンク、共有メモリユニット、メモリコントローラ、1つ以上のメモリユニット、もしくは周辺相互接続部のうちの少なくとも1つ、またはこれらの組み合わせをさらに含む。任意選択で、上述の例のいずれか1つまたは別の例では、DAG計算の1つ以上のノードが階層的に分割される。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノード出力に依存する。任意選択で、上述の例のいずれか1つまたは別の例では、1つ以上のサブDAG計算の1つ以上のサブノードは、複数のサブノードへの入力である。
【００１０】
本開示およびその利点のより完全な理解のために、次に、添付の図面と併せて以下の説明を参照する。
【図面の簡単な説明】
【００１１】
【図１】一実施形態の処理システムの図である。
【図２Ａ】3つのノードを有する例示的な有向非巡回グラフ（DAG）計算モデルである。
【図２Ｂ】DAGノードの例示的な階層的分割である。
【図３】2つのノードを有するDAG計算モデルの例であり、各ノードは、複数のサブノードを有する。
【図４】ノード間並列処理のためにDAG計算モデルを分割し、複数のサブDAG計算モデルを構築するための一実施形態の方法のフローチャートである。
【図５Ａ】画像処理アプリケーションで使用される3つのノードを有するDAG計算モデルの例である。
【図５Ｂ】複数のサブノードを有する、画像処理の例で使用される3つのノードを有するDAG計算モデルの例である。
【図５Ｃ】ノード間並列処理のために最適化された、元のDAG計算モデルに基づく複数の新しいサブDAG計算モデルを構築する例である。
【図５Ｄ】新しいサブDAG計算モデルを構築するためのメモリ割り当ての例示的なデータフローである。
【図６Ａ】ディープニューラルネットワーク処理アプリケーションで使用される3つのノードを有するDAG計算モデルの例である。
【図６Ｂ】各ノードの入力行列を複数の入力行列に分割する例である。
【図６Ｃ】ノード間並列処理のために最適化された、元のディープニューラルネットワークDAG計算モデルに基づく複数の新しいサブDAG計算モデルを構築する例である。
【図７】コンピュータビジョン処理アプリケーションで使用される複数のノードを有するDAG計算モデルの例である。
【図８】1対多マッピンググラフモデルを有するDAG計算モデルの例である。
【図９】一実施形態のワイヤレス通信ネットワークの図である。
【図１０】一実施形態の処理システムの別の図である。
【図１１】一実施形態のトランシーバの図である。
【発明を実施するための形態】
【００１２】
本開示は、多種多様な特定の状況で具体化され得る多くの適用可能な発明概念を提供する。特定の実施形態は、特定の構成の単なる例示であり、特許請求された実施形態の範囲を限定するものではない。特に断りのない限り、異なる実施形態からの特徴は、さらなる実施形態を形成するために組み合わされ得る。実施形態の1つに関して記載された変形または修正は、他の実施形態にも適用可能であり得る。さらに、添付の特許請求の範囲によって規定される本開示の精神および範囲から逸脱することなく、本明細書において様々な変更、置換、および改変が行われ得ることを理解されたい。本発明の態様は、主にグラフィック処理ユニット（GPU）および中央処理ユニット（CPU）の文脈で記載されているが、これらの本発明の態様は、有向非巡回グラフ（DAG）モデル計算でのノード間並列処理を提供するために他の処理ユニットにも適用可能であり得ることも理解されたい。
【００１３】
DAG計算の処理は、一般に、ノード内並列処理を使用して実施され、その場合、同じ処理ユニットの複数のコアが、DAGの各ノードを順次依存的に処理する。特に、DAG計算モデルの各計算タスクは、個々のノードに関連付けられているか、またはマッピングされており、特定の計算では、計算タスクは、より小さなサブタスクに分割され得る。ノード内並列処理では、スケジューリング粒度は、単一ノード内に制限され、異なる処理ユニットを使用する並列処理は、複数のノード間または各ノード内で達成されない。一例として、第1のノードに関連付けられたサブタスクは、CPUの複数のコアによって並列処理され得、第2のノードに関連付けられたサブタスクは、GPUの複数のコアによって並列処理され得る。しかしながら、第2のノードのGPUによる処理のスケジューリングは、第1のノードのCPUによる処理のスケジューリングが完了するまで開始されない。したがって、ノード内並列処理の各ノードは、特定の処理ユニットによって個別に順次計算される。これは、処理システムの無駄なリソース利用をもたらす。
【００１４】
本開示の実施形態は、ノード内並列処理に元々使用されていた元のDAG計算モデルに基づく、ノード間並列処理のための更新されたDAG計算モデルの構築およびスケジューリングを提供する。本開示の特定の実施形態は、好適には、複数のDAGノード間で達成される、異なる処理ユニットを使用する並列処理を可能にし得る。他の実施形態では、異なる処理ユニットを使用する並列処理は、好適には、元のDAG計算モデルの異なるノードのサブタスク内で達成され得る。特に、以前は単一のノードに関連付けられていた各サブタスクは、修正されたDAG計算モデルでは新しいノードとして表され得る。そのとき、複数の新しいサブノードへの元のノードの変換および複数の新しいサブノードに基づく新しいDAG計算モデルの配置は、複数のハードウェアリソース（すなわち、CPU、GPUなど）が新しいDAG計算モデルの計算で同時に利用されることを可能にし得る。結果として、処理システムは、例えばノード内並列処理を使用して以前に実行されていた速度よりも大幅に高速でより効率的な速度でDAG計算モデルを処理することができる。これらおよび他の詳細は、以下でより詳細に説明される。
【００１５】
図1は、本明細書に記載の方法を実行するための、一実施形態の処理システム100のブロック図を示しており、これは、ホストデバイスに組み込まれ得る。図示されているように、処理システム100は、中央処理ユニット（CPU）102および106と、グラフィック処理ユニット（GPU）110と、デジタル信号プロセッサ（DSP）114と、画像信号プロセッサ（ISP）118と、映像処理ユニット（VPU）122と、ニューラルネットワーク処理ユニット（NPU）126と、表示処理ユニット（DPU）130と、相互接続バスリンク134と、共有メモリユニット136と、メモリコントローラ138と、メモリユニット140および142と、周辺相互接続部144とを含み、これらは、図1に示されているように配置されてもよい（が、配置されなくてもよい）。処理システム100は、長期ストレージ（例えば、不揮発性メモリなど）などの、図1には示されていない追加のコンポーネントを含み得る。一部の実施形態では、処理システム100は、様々な処理ユニットの一部を含み得る。図1に示されている各コンポーネントの数は、説明を簡単にするために示されている。様々な実施形態において、さらなる数の同じコンポーネントタイプが考えられ得る。
【００１６】
一部の実施形態では、処理システム100の各コンポーネントは、単一のチップまたは回路、例えば、システムオンチップ（SoC）タイプの集積回路（IC）に配置され得る。他の実施形態では、処理システム100の各コンポーネントは、異なるチップまたは回路に配置され得る。一実施形態では、処理システム100の一部のコンポーネントは、同じチップまたは回路に配置され得、一方、一部のコンポーネントは、異なるチップまたは回路に配置され得る。
【００１７】
CPU102および106は、処理システム100における基本的な演算、論理、入力／出力（I／O）、および制御動作の命令のセットを実行するために使用され得る。GPU110は、処理システム100における効率的なコンピュータグラフィック計算および画像処理動作の命令のセットを実行するために使用され得る。DSP114は、処理システム100において、アナログ信号を効率的に測定、フィルタリング、もしくは圧縮するために、またはデジタル信号処理アルゴリズムを処理するために使用され得る。ISP118は、処理システム100において画像を効率的に処理するために使用され得る特殊なタイプのDSP114である。VPU122もまた、処理システム100において映像を効率的に処理するために使用され得る特殊なタイプのDSP114である。NPU126は、処理システム100においてニューラルネットワーキングを使用してデータを処理し、問題を解決するために使用され得る。DPU130は、処理システム100の表示に関連するデータを処理するために使用され得る。本開示の実施形態を使用して実施され得る、図1に示されていない他のタイプの処理ユニットの例は、アプリケーション処理ユニット（APU）、フィールドプログラマブルゲートアレイ（FPGA）、マイクロコントローラなどである。処理システム100の各処理ユニットは、効率的なまたは加速された方法で特定のタスクの非限定的なセットを実行するようにアーキテクチャ的に最適化および設計され得る。図1に示されている処理ユニットのリストは、タスク固有のプロセッサであって、それぞれが複数のコアを有する、タスク固有のプロセッサの非限定的な例である。一例として、GPU110は、CPU102および106よりも迅速かつ効率的にデータの大きなバッチに対して同じ操作を繰り返し行うようにアーキテクチャ的に最適化され得る。様々な処理ユニットのそれぞれは、より多くのキャッシュレベル（L1、L2など）の階層として編成されたハードウェアキャッシュ104、108、112、116、120、124、128、および132を個別に含み得る。各処理ユニットはまた、数千のスレッドを同時に処理し得る数個または数百個のコアを含み得る。
【００１８】
相互接続バスリンク134は、様々な処理ユニット、共有メモリ136、および周辺相互接続部144間でデータを転送するために使用される通信リンクまたはキャッシュコヒーレント相互接続部である。相互接続バスリンク134は、ソフトウェアもしくはハードウェアタイプの制御バス、アドレスバス、または複数の通信プロトコルにわたって動作するデータバスであり得る。相互接続バスリンク134は、マルチドロップ、デイジーチェーン、スイッチなどの種々のトポロジを有し得る。
【００１９】
共有メモリ136は、プログラミングおよび／または命令、ならびに処理ユニットのいずれかによる実行のための関連する入力／出力データおよび／または中間データを記憶するように適合されたコンポーネントまたはコンポーネントの集合であり得る。各処理ユニットは、相互接続バスリンク134を介して共有メモリ136にアクセスし得る。共有メモリ136は、非一時的コンピュータ可読媒体であり得る。非一時的コンピュータ可読媒体は、磁気記憶媒体、光記憶媒体、フラッシュ媒体、および固体記憶媒体を含むあらゆるタイプのコンピュータ可読媒体を含む。ソフトウェアは処理システム100にインストールされ得、処理システム100と共に販売され得ることを理解されたい。あるいは、ソフトウェアは、例えば、ソフトウェア作成者によって所有されているサーバから、またはソフトウェア作成者によって所有されていないが使用されているサーバからを含めて、物理媒体または配布システムを介してソフトウェアを取得することを含めて、取得されて処理システム100にロードされ得る。ソフトウェアは、例えば、インターネットを介した配布のためにサーバに記憶され得る。
【００２０】
メモリコントローラ138は、共有メモリ136に出入りするデータの流れを管理するために使用される。一部の実施形態では、メモリコントローラ138は、統合メモリコントローラ（IMC）であり得る。一部の実施形態では、メモリコントローラ138は、処理システム100の外部コンポーネントであり得る。メモリユニット140および142は、ダブルデータレート（DDR）タイプのメモリまたは低電力DDR（LPDDR）タイプのメモリであり得る。周辺相互接続部144は、処理システム100が他のデバイス／コンポーネントおよび／またはユーザと通信することを可能にするコンポーネントまたはコンポーネントの集合であり得る。一実施形態では、周辺相互接続部144は、プロセッサ100から、ホストデバイスおよび／またはリモートデバイスにインストールされたアプリケーションにデータメッセージ、制御メッセージ、または管理メッセージを通信するように適合され得る。別の実施形態では、周辺相互接続部144は、ユーザまたはユーザデバイス（例えば、パーソナルコンピュータ（PC）など）が処理システム100の様々な処理ユニットと相互作用／通信することを可能にするように適合され得る。
【００２１】
図2Aは、3つのノードN1 182、N2 184、およびN3 186を含む例示的なDAG計算モデル180である。DAG計算モデル180は、例えば画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションで使用されるグラフであり得る。特に、DAG計算モデル180は、複数の層に分割され得る、または同期された計算タスクを分離し得る任意のタイプのアプリケーション処理のグラフモデルであり得る。図2Aは、3つのノードを含むDAG計算モデル180を示しているが、DAG計算は、2より多くの任意の数のノードを有し得ることを理解されたい。この例では、各ノードN1 182、N2 184、およびN3 186は、DAG計算モデル180内の別々のタスクまたは計算ブロックに関連付けられる。
【００２２】
複数のプロセッサタイプを有する処理システムでは、処理ユニットは、ノードで遂行される必要がある特定のタスクに基づいて各ノードを特定の処理ユニットにスケジューリングする、または割り当てるために使用され得る。このタイプのスケジューリングは通常、異なる処理タイプに固有の最適化された処理を利用するために行われる。一例として、図1の処理システム100では、GPU110は、ノードN1 182を処理するように割り当てられ得、DSP114は、ノードN2 184を処理するように割り当てられ得、CPU102は、ノードN3 186を処理するように割り当てられ得る。次に、各ノードは、以下でさらに詳説されるように、複数のサブタスクまたは複数の計算ブロックに分割され得る。
【００２３】
異なる処理タイプが複数のコアを含む処理システムでは、ノード内の各サブタスクまたは計算ブロックは、処理ユニットのスケジューリングを使用して、特定の処理タイプの別個のコアによってノード内処理され得る。DAG計算モデル180のノード内並列処理では、ノードN2 184に関連付けられたタスクは、ノードN1 182に関連付けられたタスクが完了するまで開始されない。言い換えれば、ノードN1 182の出力188は、ノードN2 184への入力であり、ノードN2 182の出力190は、ノードN3 186への入力であり、他のノードについても同様である。
【００２４】
一般に、DAG計算モデル180の各ノードは、相互依存順次構成で配置されるため、DAG計算を処理するための合計時間は、各ノードを処理するための時間の累積である。一例として、ノードN1 182のすべてのサブノードを処理するのにT1時間がかかり、ノードN2 184のすべてのサブノードを処理するのにT2時間がかかり、ノードN3 186のすべてのサブノードを処理するのにT3時間がかかる場合、計算モデルを処理するための合計時間は、Ttotal＝T1＋T2＋T3である。時間T1の間、ノードN1 182に割り当てられた処理ユニットはアクティブ状態であり、一方、ノードN2 184およびノードN3 186に割り当てられた処理ユニットはアイドル状態である。時間T2の間、ノードN2 184に割り当てられた処理ユニットはアクティブ状態であり、一方、ノードN1 182およびノードN3 186に割り当てられた処理ユニットはアイドル状態である。時間T3の間、ノードN3 186に割り当てられた処理ユニットはアクティブ状態であり、一方、ノードN1 182およびノードN2 184に割り当てられた処理ユニットはアイドル状態である。本開示の実施形態は、異なる処理ユニットのアイドル時間を最小化するためにDAG計算モデル180を再構築する方法を提供する。
【００２５】
図2Bは、DAGノード183の例示的な階層的分割181を示している。階層の第1レベルでは、ノードA 183は、サブノードA1 185、A2 187、…、Ak 189に分割される。階層の第2レベルでは、サブノードA2 187は、サブノードA2−1 191、A2−2 193、…、A2−L 195に分割されることが示されている。ノードの分割は、第3層、第4層、および第5層など、さらなる階層で継続され得る。サブノードA2 187はさらなるサブノードに分割されることが示されているが、A1〜Ak 185〜189などの、Aの任意の数のサブノードがさらなる階層的サブノードに分割され得ることを理解されたい。各階層的分割におけるサブノードの数は、非限定的であり、DAGノード183が表されているDAG計算モデル内の対応するサブタスクに関連する適切な任意の数であってもよい。
【００２６】
図3は、それぞれが複数のサブノードを有する2つのノードN1 202およびN2 204を含む例示的なDAG計算モデル200である。DAG計算モデル200の文脈では、ノード2 204は、ノード1 202に依存する。図示されているように、ノードN1 202は、4（四）つのサブノードN1−1 206、N1−2 208、N1−3 210、およびN1−4 212を含む。ノードN2 204は、16（十六）のサブノードN2−1 214、N2−2 216、…、N2−15 242、およびN2−16 244を含む。ノードN1 202の4（四）つのサブノードおよびノード204の16（十六）のサブノードが示されているが、サブノードの数は、アプリケーションに依存し得、図示されているような、各ノードのサブノードの数は、説明を簡単にするためのものである。
【００２７】
一例では、ノード内並列処理に関して、ノードN1 202の各サブタスクは、CPU102のコアによって処理され得、ノードN2 204の各サブタスクは、GPU110のコアによって処理され得る。別の例では、やはりノード内並列処理に関して、ノードN1 202の各サブタスクは、GPU110のコアによって処理され得、ノードN2 204の各サブタスクは、DSP114のコアによって処理され得る。さらに別の例では、ノード内並列処理に関して、ノードN1 202の各サブタスクは、ISP118のコアによって処理され得、ノードN2 204の各サブタスクは、DPU130のコアによって処理され得る。別の例では、ノード内並列処理に関して、ノードN1 202の一部のサブタスクは、CPU102のコアによって処理され得、ノードN1 202の一部のサブタスクは、GPU110のコアによって処理され得る。この例では、ノードN2 204の一部のサブタスクは、DSP114のコアによって処理され得、ノードN2 204の他のサブタスクは、ISP118のコアによって処理され得る。各サブタスクは、特定のタイプの処理ユニットの異なるコアによって行われ得、特定の処理ユニットは、専用ハードウェアユニットで実施される利用可能な処理に基づいて計算の効率を改善するように選択され得ることに留意されたい。
【００２８】
DAG計算モデル200を計算するために使用されるノード内並列処理の実施態様では、ノード内の各サブタスクの遂行時に、DAG計算モデル200の次のノードは、前のノードのすべてのサブタスクが完了するまで、その次のノード内のサブタスクの処理を開始しない。これは、前のノードからの出力の完全なセットを受信することへの各ノードの依存関係という形で示される。したがって、2つの異なる処理ユニットがDAG計算モデル200を処理するために使用される例では、第1の処理ユニットが、アクティブ状態でノードN1 202を処理している間、第2の処理ユニットは、アイドル状態であり、第1の処理ユニットが計算を完了するのを待機し得る。同様に、第2の処理ユニットは、第1の処理ユニットがアイドル状態にある間、アクティブ状態でノードN2 204を処理する。
【００２９】
図4は、ノード間並列処理のためにDAG計算モデルを分割し、複数のサブDAG計算モデルを構築するための、処理システム100によって実行され得る、一実施形態の方法250のフローチャートである。DAG計算モデルは、各ノードが一連のノード内の前のノードから向けられるトポロジカル順序を有する。ステップ252で、処理システム100は、DAG計算モデル内の非巡回順次ノードのセットを識別する。
【００３０】
ステップ254で、処理システム100は、タスクタイプ、ならびに各サブノードおよび各ノードに対応する計算メモリ要求に基づいて、識別された各ノードを非相互依存サブノードに分割する。サブノードへのノードの分割は、均一であっても、不均一であっても、または重複していてもよい。ノードの均一な分割では、各サブノードまたはサブタスクは、均等なサイズを有し得、一方、ノードの不均一な分割では、各サブノードまたはサブタスクは、異なるまたは不均等なサイズを有し得る。ノードの重複分割では、一部のサブタスクは、1つ以上の他のサブタスクと重複し得るし、またはサブタスクは、別のサブタスクとのサブタスク境界に共通部分を有し得る。
【００３１】
一例として、画像処理およびノードの均一な分割に関して、画像は、より小さい均等なNかけるM（NxM）のセグメントに細分され得る。一例として、画像処理およびノードの不均一な分割に関して、画像は、より小さい不均等なNかけるM（NxN）のセグメントに細分され得る。一例として、画像処理およびノードの重複分割に関して、画像は、不均等なまたは均等な、より小さい重複するNかけるM（NxN）のセグメントに細分され得る。
【００３２】
ステップ256で、処理システム100は、元のDAG計算モデルの異なるノードからの複数の非相互依存サブノードを使用して複数のサブDAG計算モデルを構築する。サブDAG計算モデルは、2つの異なるノードからの非相互依存サブノードを少なくとも有するが、複数のサブDAG計算モデルの構築のバリエーションは、サブノードに関連付けられた計算タスクに基づいて異なり得ることを理解されたい。
【００３３】
一部の実施形態では、各サブDAG計算モデルは、元のDAG計算モデルの各ノードからの単一の非相互依存サブノードを有し得る。一部の実施形態では、各サブDAG計算モデルは、元のDAG計算モデルのいくつかのノードからの非相互依存サブノードを有し得る。他の実施形態では、一部のサブDAG計算モデルは、元のDAG計算モデルの各ノードからの非相互依存サブノードを有し得、一方、一部のサブDAG計算モデルは、元のDAG計算モデルのいくつかのノードからの非相互依存サブノードを有し得る。
【００３４】
複数のサブDAG計算モデルの構築は、手動で実行され得るし、またはコンパイラによって自動的に実行され得る。手動構築の例として、5未満のノードを有するDAG計算モデルでは、複数のサブDAG計算モデルの構築は、事前構成された静的マッピングテーブルによって実行され得る。事前構成された静的マッピングテーブルは、元のDAG計算モデルを複数のサブDAG計算モデルにマッピングするために使用され得る。
【００３５】
複数のDAGノードを有するより複雑なモデルに一般に適用可能な自動構築またはコンパイラ支援構築の例として、コンパイラは、実行時に元のDAG計算モデルを複数のサブDAG計算モデルに動的に変換するために使用され得る。一部の実施形態では、元のDAG計算モデルから複数のサブDAG計算モデルへの変換は、オフラインコンパイラを使用して事前にコンパイルされ得る。
【００３６】
ステップ258で、処理システム100は、中間共有メモリ（キャッシュ）136を使用して、複数のサブDAG計算にメモリを割り当てる。中間共有メモリ136は、同じサブDAG計算モデルの次のサブノードの入力として使用されるサブノード計算の出力の一時的な記憶場所として使用され得る。中間共有メモリは、バッファメモリとして機能し、外部のダブルデータレート（DDR）タイプのメモリなどのオフチップメモリ、または処理ユニット内のL1、L2などのキャッシュメモリに関連する読み出しおよび書き込み時間を短縮する。一部の実施形態では、DAG計算を分割するステップ（ステップ254）とメモリを割り当てるステップ（ステップ258）との間にリソース依存関係がない場合、これらのステップは同時に実行され得る。一部の実施形態では、サブDAG計算モデルを構築するステップ（ステップ256）とメモリを割り当てるステップ（ステップ258）との間にリソース依存関係がない場合、これらのステップは同時に実行され得る。一部の実施形態では、これらのステップは、異なる時間に行われ得る。
【００３７】
ステップ260で、処理システム100は、例えばCPU102または104を使用して、複数のサブDAG計算の各サブDAG計算に関連付けられた同期および動的タスクをスケジューリングする。一部の実施形態では、生成されたサブDAG計算モデルは、別の非相互依存サブDAG計算モデルとは異なり得る。最初に、リソースが、高レベルの複数のサブDAG計算モデルに割り当てられ、次に、処理システム100は、各サブタスクに関連付けられた、より低い処理レベルの各サブDAG計算内の各サブノードをスケジューリングする。
【００３８】
DAG計算モデルでは、各ノードは、前のノードの完了に制約される。同様に、サブDAG計算モデルに対応する各サブノードは、前のサブノードの完了に制約される。スケジューリングは、各サブタスクがサブDAG計算モデル内で実行される順序を提供する。言い換えれば、スケジューリングは、サブDAG計算モデル内のサブタスクのトポロジカルソートを提供する。
【００３９】
ステップ260でのスケジューリングは、処理ユニットタイプのうちの1つにわたるノード間および／またはノード内スケジューリングであり得る。トポロジカルソートは、タスクのセットおよび共有リソースの相互依存関係に基づいて各サブDAG計算モデル間および各サブDAG計算モデル内でタスクのセットを実行するための効率的な手段を提供する。スケジューリングの結果は、処理システム100内の異なる処理ユニットに関連するアイドル時間が少なくなるため、元のDAG計算モデルを処理するための合計期間が短縮されることである。
【００４０】
ステップ262で、処理システム100は、複数のサブDAG計算のそれぞれを処理し、関連する出力ファイルをコンパイルする。各複数のサブDAG計算モデルのノード間並列処理の完了時に、元のDAG計算モデルのノード内並列処理によって生成される最終出力と等しい最終出力が生成される。
【００４１】
図5A〜図5Dは、例えば画像処理アプリケーションにおいて処理システム100によって実行され得る、本開示の実施形態を使用する、DAG計算モデル300からの複数のサブDAG計算モデルの構築を示している。DAG計算モデルを使用してモデル化され得る画像処理アプリケーションの例は、ビデオゲーム、デモ、またはハイダイナミックレンジ（HDR）レンダリングに適用される画像ぶれである。これらのアプリケーションでは、画像ぶれまたはブルームシェーディングは、例えば実世界のカメラの画像効果を再現するために使用され得る。
【００４２】
図5AのDAG計算モデル300は、第1のノード（ノード1）302、第2のノード（ノード2）304、および第3のノード（ノード3）306の3つのノードを含む。さらなるノードも考えられ得ることに留意されたい。各ノードは、例えば画像処理アプリケーションの特定の計算タスクにマッピングされる。
【００４３】
一例として、第1のノード302は、入力画像の取得に対応し得、第2のノード304は、積分画像への入力画像の変換に対応し得、第3のノード306は、例えばガウスフィルタリングを使用する、積分画像からの出力画像の生成に対応し得る。
【００４４】
一実施形態では、出力ファイルは、出力データバッファであり得る。別の実施形態では、出力ファイルは、出力画像バッファであり得る。別の実施形態では、出力は、出力画像ファイルであり得る。また、一部の実施形態では、出力ファイルは、DAG計算モデルの出力特徴のセットであり得る。DAG計算モデル300における特定のノードの特定の配置は、本開示の主題ではなく、DAG計算モデル300は、他のアプリケーションでの新しいDAG計算モデルの構築を説明するための一般的なDAG計算モデルとして使用され得ることを理解されたい。
【００４５】
図5Bでは、DAG計算モデル300の各ノードは、複数のサブタスクまたはサブノードに細分され得る。第1のノード302は、サブノード1−1 308、サブノード1−2 310、サブノード1−3 312、およびサブノード1−4 314に細分される。第2のノード304は、サブノード2−1 316、サブノード2−2 318、サブノード2−3 320、およびサブノード2−4 322に細分される。第3のノード306は、サブノード3−1 324、サブノード3−2 326、サブノード3−3 328、およびサブノード3−4 330に細分される。
【００４６】
各タスク内のサブタスクの分割は、均一であっても、不均一であっても、または重複していてもよい。一例として、サブノード1−3 312およびサブノード1−4 314に関連付けられたサブタスクの分割332は、キャリーオンライン（carry＿on line）タイプであり得、サブノード2−3 320およびサブノード2−4 322に関連付けられたサブタスクの分割334は、境界に重複領域を有し得る。一部の実施形態では、2つの隣接するサブブロックを有するDAG計算モデルは、互いに相互依存関係を有し得る。一例として、サブノード2−4 322への入力は、サブノード2−3 320の出力であり得る。これらの実施形態では、交差領域内の各ラインは、隣接するサブノードの計算のキャリーオン結果の位置の指標であるキャリーオンラインであり得る。重複領域は、2つの隣接するサブブロック間の交差領域であり得、1つのラインまたは複数のラインであり得る。
【００４７】
各サブタスクは、それぞれのノードの特定の計算タスクに関連付けられた同じまたは異なる計算サブタスクにマッピングされ得る。DAG計算モデル300の並列内処理では、各サブタスクは、同じ処理ユニットの異なるコアに対してスケジューリングされ得る。このタイプの処理では、スケジューリング粒度は、単一のDAGノード内に制限される。したがって、DAGノード間またはDAG間ノード内で並列処理は達成されない。これは、現在のスケジューリングが完了するまで次のノードのスケジューリングが開始され得ないため、低いハードウェアリソース利用率をもたらす。
【００４８】
図5Cは、処理システム100によって計算され得る、複数のサブDAG計算モデルを含む、一実施形態のDAG計算モデル303を示している。DAG計算モデル303は、DAG計算モデル300の修正版である。DAG計算モデル303は、5（五）つのサブDAG計算モデル352、354、356、358、および360を含む。本説明のために、図5Cには、5（五）つのサブDAG計算モデルが示されているが、サブDAG計算モデルの総数は、1（一）より大きい任意の数であってもよい。
【００４９】
新しい配置では、ノード間並列処理ならびにノード間およびノード内並列処理を使用して、計算並列処理が達成され得る。サブノードの新しいDAG計算モデル303の配置では、複数のハードウェアリソース（例えば、処理ユニット）が、新しいサブDAG計算モデルを並列で計算するために利用され得る。各サブDAG計算モデルが他のサブDAG計算モデルから独立している実施形態では、合計処理時間は、T1＋T2＋T3から（T1＋T2）または（T2＋T3）のうちのより長い合計時間に短縮される。
【００５０】
各サブDAG計算モデル内の各サブノードは、すべてのノードのサブノード内でより最適化された依存関係モデルを有するように配置および構築される。これは、DAG計算モデル300の効率を改善し、処理時間を短縮するために行われる。各サブノードは、処理ユニットの異なるコアによって処理される。ただし、サブDAG計算モデル内のサブノードの配置は、新しく構築されたモデルのサブノードの処理間のより短いアイドル時間を可能にする。以前と同様に、各処理ユニットは、処理ユニットの特定の能力、およびサブノードに関連付けられたサブタスクに従ってサブノードに割り当てられる。
【００５１】
図示されているように、第1のサブDAG計算モデル352は、サブノード1−1 308に依存するサブノード2−1 316を含む。第2のサブDAG計算モデル354は、サブノード2−1 316に依存するサブノード3−1 324に加えて、サブノード1−2 310に依存するサブノード2−2 318を含む。第3のサブDAG計算モデル356は、サブノード2−2 318に依存するサブノード3−2 326に加えて、サブノード1−3 312に依存するサブノード2−3 320を含む。第4のサブDAG計算モデル358は、サブノード2−3 320に依存するサブノード3−3 328に加えて、サブノード1−4 314に依存するサブノード2−4 322を含む。最後に、第5のサブDAG計算モデル360は、サブノード2−4 330に依存するサブノード3−4 330を含む。
【００５２】
サブDAG計算モデル352の第1のサブノードの出力は、サブDAG計算モデル352の第2のサブノードの入力である。同様に、あるサブDAG計算モデルから別のサブDAG計算モデルへの依存関係が依然として存在し得る。しかしながら、第1のサブDAG計算モデル352に関連付けられたサブタスクの遂行時間は、DAG計算モデル300に関連付けられたタスク全体の遂行時間よりも短い。処理ユニットの他のコアは、同じまたは他のサブDAG計算モデル内の他のサブノードの実行のためにスケジューリングされ得る。したがって、処理ユニットがアイドル状態のままであり、別の処理ユニットによるタスクの完了を待機する期間が大幅に短縮される。
【００５３】
図5Dは、図5CのDAG計算モデル303への図5BのDAG計算モデル300の変換に対応する、処理システム100のメモリブロック内の例示的なデータフローを示している。DAG計算モデル300の各ノードは、均一に分割され得るし、または不均一に分割され得るより小さなサブノードまたはサブタスクに分割される。次に、第1のノード382の各サブブロック、第2のノード384の各サブブロック、および第3のノード386の各サブブロックに、メモリ内の場所が割り当てられる。次に、ブロック394において、各ノードの各サブブロックが、メモリにキューイングされ、キューイングのアドレス、サイズ、シェイプ、順序情報などに関連する情報が記録される。ブロック394に記憶された情報を使用して、スプリッタ395およびスケジューラ397は、新しいサブDAG計算モデルの新しいキューを生成する。ブロック398は、処理システム100の処理ユニットのそれぞれからアクセス可能な任意選択の中間メモリバンクを示している。中間メモリは、他の処理ユニットで使用するために、サブDAG計算モデル内およびサブDAG計算モデル間の出力結果を記憶するために使用され得る。
【００５４】
図6A〜図6Cは、例えばディープニューラルネットワーク（DNN）タイプのアプリケーションにおいて処理システム100によって実行され得る、本開示の実施形態を使用する、DAG計算モデル450からの複数のサブDAG計算モデルの構築を示している。ディープニューラルネットワークは、データ標本を使用する機械学習の一種であり、通常、複数の層、すなわち、入力層、中間層（すなわち、隠れ層）、および出力層を含む。各層またはノードは、画像の畳み込み、プーリング、正規化、フィーチャマップ生成など、他の層のいずれとも異なり得る関連機能を有する。
【００５５】
ディープニューラルネットワークDAG計算モデル450では、データは、ループバックすることなく、入力層または第1のノード（ノード1）452から出力層または第3のノード（ノード3）456に流れる。ディープニューラルネットワークDAG計算モデル450の第1のノード452および第2のノード454は、行列入力および対応する行列重みを含む。ディープニューラルネットワークDAG計算モデル450の出力ノード456は、例えばソフトマックス関数470を使用する正規化された指数表現である。ディープニューラルネットワークモデルは、第1の層および第2の層を有するが、さらなるノードも考えられ得る。
【００５６】
第1のノード452は、第1の行列入力462および第1の行列重み464を含む。第2のノード454は、第2の行列入力466および第2の行列重み468を含む。一般的なディープニューラルネットワークアプリケーションでは、各ノードの入力行列と重み行列が乗算され、0と1との間で関数出力表現が生成される。ディープニューラルネットワークは重みを調整し、特定のパターンが認識されるまでそれぞれの出力が評価される。
【００５７】
図6Bでは、各ノード452および454の各入力行列462および466は、4（四）つのサブ行列に細分される。この例の入力行列は4つのサブ行列に細分されるが、他の例では、細分は、1（一）より大きい任意の数であってもよい。
【００５８】
CAFFEまたはTensorFlowに見られるものなど、ノード内並列処理を使用するDAG計算でディープニューラルネットワークを解決するための一般的な解決策では、ノードに関連付けられた各計算タスクは層ごとにスケジューリングされる。各層内で、ノード内並列処理は、処理システム100の特定の処理ユニットの複数のコアによって達成され得る。ノード内並列処理では、第2のノード（入力2×重み2）のスケジューリングは、第1のノード（入力1×重み1）のスケジューリングが完了するまで開始されない。第1のノードの完了は、第1のノードの解決（すなわち、そのノードのそれぞれの入力ノードと重みを乗算し、パターン認識プロセスを完了すること）に対応する。
【００５９】
図6Cは、細分された入力行列および対応する重みに基づく修正されたDAG計算モデル455を示している。DAG計算モデル455は、4（四）つのサブDAG計算モデル510、520、530、および540を含む。本説明のために、図6Cには、4（四）つのサブDAG計算モデルが示されているが、サブDAG計算モデルの総数は、1（一）より大きい任意の数であってもよい。新しい配置では、ノード間並列処理ならびにノード間およびノード内並列処理を使用して、計算並列処理が達成され得る。サブノードの新しいDAG計算モデル455の配置では、複数のハードウェアリソース（例えば、処理ユニット）が、新しいサブDAG計算モデルを計算するために利用され得る。細分された各行列は、DAG計算モデル450のノード内のサブタスクに対応する。この修正されたモデルでは、元のモデルをより小さなサブタスクに分割し、DAG計算モデル450のタスク内から各サブDAG計算モデルのサブタスク内に依存関係を再配置することによって、ノード間並列処理が達成され得る。
【００６０】
各サブDAG計算モデル内の各サブノードは、すべてのノードのサブノード内でより最適化された依存関係モデルを有するように配置および構築される。これは、DAG計算モデル450の効率を改善し、処理時間を短縮するために行われる。各サブノードは、処理ユニットの異なるコアによって処理される。ただし、サブDAG計算モデル内のサブノードの配置は、新しく構築されたモデルのサブノードの処理間のより短いアイドル時間を可能にする。以前と同様に、各処理ユニットは、処理ユニットの特定の能力、およびサブノードに関連付けられたサブタスクに従ってサブノードに割り当てられる。
【００６１】
図示されているように、第1のサブDAG計算モデル510は、サブノード1−1 502に依存するサブノード2−1 504と、サブノード2−1 504に依存するサブノード3−1 506とを含む。第2のサブDAG計算モデル520は、サブノード1−2 512に依存するサブノード2−2 514と、サブノード2−2 514に依存するサブノード3−2 516とを含む。第3のサブDAG計算モデル530は、サブノード1−3 522に依存するサブノード2−3 524と、サブノード2−3 524に依存するサブノード3−3 526とを含む。また、第4のサブDAG計算モデル540は、サブノード1−4 532に依存するサブノード2−4 534と、サブノード2−4 534に依存するサブノード3−4 536とを含む。
【００６２】
図7は、コンピュータビジョンタイプのアプリケーションで使用される例示的なDAG計算モデル550を示している。コンピュータビジョンタイプのアプリケーションの例は、OpenVXグラフである。OpenVXグラフは、コンピュータビジョンアプリケーションのクロスプラットフォームアクセラレーションのためのオープンなロイヤリティフリーの標準的な方法である。OpenVXグラフは、エンドツーエンドの画像および／または映像計算のための複数のステップを含む。これらの個々のステップのいくつかの例は、色変換、チャネル抽出、画像ピラミッド、オプティカルフローなどである。
【００６３】
OpenVXグラフなどの、コンピュータビジョンタイプのアプリケーションの各ステップは、DAGノードによって表され得る。DAG計算モデル550は、OpenVXグラフの一例である。DAG計算モデル550は、色変換ノード552、チャネル抽出ノード554、画像ピラミッドノード556、ピラミッドノード558、オプティカルフローノード560、ハリスコーナーノード562、およびキーポイントノード564を含む。各ノードの特定の機能の理解は、ノード内並列処理のために配置されたモデルからノード間並列処理を可能にするモデルへのDAG計算モデル550の変換を理解するために必要ではない。この図は、一般的なコンピュータビジョンアプリケーションにおいて計算タスク（例えば、YUVフレームまたはグレーフレーム生成）がDAG計算モデルに配置され得ることを示すために使用されている。
【００６４】
本開示の実施形態は、DAG計算モデル550の各ノードを複数のサブタスクに分割する方法を提供する。そのとき、各サブタスクは、例えば図5A〜図5Cに示されるように、DAG計算モデル550の他のノードのサブタスクまたはサブノードを用いて、画像処理で前述された方法と同様に再配置され得る。新しいサブDAG計算モデルは、各ノード間および各ノード内のノード間処理を可能にする。結果として、新しいDAG計算モデルは、他の処理ユニットのより少ないアイドル処理時間と共により速い処理時間を可能にする。
【００６５】
画像処理、ディープニューラルネットワーク、および映像処理に関する上述の例は、非限定的な例であり、元のDAG計算モデルの分割および新しいサブDAG計算モデルの構築に関する対応する説明は、DAG計算モデルを使用して形成され得るすべてのアプリケーションに当てはまり得ることに留意されたい。
【００６６】
図8は、一実施形態のDAG計算モデル600、および処理システム100によって計算され得る、一対多マッピンググラフモデルを有する対応する構築された実施形態のDAG計算モデル620を示している。一般的なアプリケーション、例えば画像処理、映像処理、またはディープニューラルネットワーク処理では、対応するDAG計算モデルの各サブDAGは、2つ以上のサブノードを有し得る。この配置では、1つ以上のサブノードは、複数のサブノードの入力に依存し得る。また、1つ以上のサブノードは、複数のサブノードに入力を提供し得る。
【００６７】
DAG計算モデル600は、ノード1 602、ノード2 604、およびノード3 606の3つのノードを有するものとして示されている。より多くの数のノードを有するDAG計算モデルも考えられ得ることを理解されたい。しかしながら、説明を簡単にするために、3つのノードが示されている。
【００６８】
DAG計算モデル620は、DAG計算モデル600内の各ノードの、複数のサブノードへの分割、および複数のサブDAG計算モデルの構築を示している。ノード1 602は、サブノード1−1 632、サブノード1−2 634、サブノード1−3 636、およびサブノード1−4 638に分割される。ノード2 604は、サブノード2−1 640、サブノード2−2 642、サブノード2−3 644、およびサブノード2−4 646に分割される。ノード3 606は、サブノード3−1 648、サブノード3−2 650、サブノード3−3 652、およびサブノード3−4 654に分割される。
【００６９】
DAG計算モデル620の構築および1つ以上のサブノードの依存関係は、図8の1対多マッピンググラフモデルに対応する例示的な配置として示されている。図示されているように、サブノード2−1 640は、サブノード1−1 632に依存する。サブノード2−2 642は、サブノード1−2 634およびサブノード2−1 640からの入力に依存する。サブノード3−1 648は、サブノード2−1 640に依存する。サブノード2−3 644は、サブノード1−3 636に依存する。サブノード3−2 650は、サブノード1−3 636とサブノード2−2 642との両方からの入力に依存する。サブノード2−4 646およびサブノード3−3 652はそれぞれ、サブノード1−4 638とサブノード2−3 644との両方からの入力に依存する。サブノード3−4 654は、サブノード2−4 646に依存する。図8の例は、各サブノードに関して種々の依存関係を有することが示されているが、一部の実施形態では、依存関係の配置が異なり得ることを理解されたい。一例として、依存関係として単一の入力を有する一部のサブノードは、複数の依存関係を有し得る。一部の実施形態では、DAG計算モデル600の各サブノードのスケジューリングは、処理システム100のCPU102、106、GPU110、またはDSP114の処理ユニットによって実行され得る。
【００７０】
図9は、データを通信するためのネットワーク700の図である。ネットワーク700は、カバレッジエリア701を有する基地局710と、複数のUE720と、バックホールネットワーク730とを含む。図示されているように、基地局710は、UE720から基地局710におよびその逆にデータを搬送する役割を果たす、UE720とのアップリンク（破線）および／またはダウンリンク（点線）接続を確立する。アップリンク／ダウンリンク接続を介して通信されるデータは、UE720間で通信されるデータ、およびバックホールネットワーク730を経由してリモートエンド（図示せず）に／から通信されるデータを含み得る。本明細書で使用される場合、「基地局」という用語は、発展型ノードB（eNodeBまたはeNB）、agNB、送信／受信ポイント（TRP）、マクロセル、フェムトセル、Wi−Fiアクセスポイント（AP）、および他のワイヤレス対応デバイスなど、ネットワークへのワイヤレスアクセスを提供するように構成されたネットワーク側デバイスを指す。基地局は、1つ以上のワイヤレス通信プロトコル、例えば、第5世代新無線（5G NR）、LTE、LTEアドバンスト（LTE−A）、高速メッセージアクセス（HSPA）、Wi−Fi802．11a／b／g／n／acなどに従ってワイヤレスアクセスを提供し得る。本明細書で使用される場合、「UE」という用語は、モバイルデバイス、移動局（STA）、車両、および他のワイヤレス対応デバイスなど、基地局とのワイヤレス接続を確立することによってネットワークにアクセスするように構成された任意のユーザ側デバイスを指す。一部の実施形態では、ネットワーク700は、中継器、低電力ノードなどの様々な他のワイヤレスデバイスを含み得る。通信システムは、多数のUEと通信することができる複数のアクセスノードを用い得ることが理解されるが、簡単にするために1つの基地局710および2つのUE720のみが示されている。
【００７１】
図10は、本明細書に記載の方法を実行するための、別の実施形態の処理システム800のブロック図を示しており、これは、ホストデバイスに組み込まれ得る。図示されているように、処理システム800は、プロセッサ802と、メモリ804と、インターフェース806、808、810とを含み、これらは、図10に示されているように配置されてもよい（が、配置されなくてもよい）。プロセッサ802は、計算および／または他の処理関連タスクを実行するように適合されたコンポーネントまたはコンポーネントの集合であり得、メモリ804は、プロセッサ802による実行のためのプログラミングおよび／または命令ならびに関連データを記憶するように適合されたコンポーネントまたはコンポーネントの集合であり得る。一実施形態では、メモリ804は、非一時的コンピュータ可読媒体を含む。インターフェース806、808、810は、処理システム800が他のデバイス／コンポーネントおよび／またはユーザと通信することを可能にするコンポーネントまたはコンポーネントの集合であり得る。一実施形態では、インターフェース806、808、810のうちの1つ以上は、データメッセージ、制御メッセージ、または管理メッセージをプロセッサ802から、ホストデバイスおよび／またはリモートデバイスにインストールされたアプリケーションに通信するように適合され得る。別の実施形態として、インターフェース806、808、810のうちの1つ以上は、ユーザまたはユーザデバイス（例えば、パーソナルコンピュータ（PC）など）が処理システム800と相互作用／通信することを可能にするように適合され得る。処理システム800は、長期ストレージ（例えば、不揮発性メモリなど）などの、図10には示されていない追加のコンポーネントを含み得る。
【００７２】
一部の実施形態では、処理システム800は、電気通信ネットワークにアクセスするネットワークデバイスまたは電気通信ネットワークの一部であるネットワークデバイスに含まれる。一実施形態では、処理システム800は、電気通信ネットワーク内の基地局、中継局、スケジューラ、コントローラ、ゲートウェイ、ルータ、アプリケーションサーバ、または他のデバイスなど、ワイヤレスまたは有線電気通信ネットワーク内のネットワーク側デバイス内にある。他の実施形態では、処理システム800は、移動局、ユーザ機器（UE）、パーソナルコンピュータ（PC）、タブレット、ウェアラブル通信デバイス（例えば、スマートウォッチなど）、ワイヤレス対応車両、ワイヤレス対応歩行者、ワイヤレス対応インフラ要素、または電気通信ネットワークにアクセスするように適合された他のデバイスなど、ワイヤレスまたは有線電気通信ネットワークにアクセスするユーザ側デバイス内にある。
【００７３】
一部の実施形態では、インターフェース806、808、810のうちの1つ以上が、処理システム800と、電気通信ネットワークを介してシグナリングを送信および受信するように適合されたトランシーバとを接続する。図11は、電気通信ネットワークを介してシグナリングを送信および受信するように適合されたトランシーバ900のブロック図を示している。トランシーバ900は、ホストデバイスに組み込まれ得る。図示されているように、トランシーバ900は、ネットワーク側インターフェース902、カプラ904、送信機906、受信機908、信号プロセッサ910、およびデバイス側インターフェース912を備える。ネットワーク側インターフェース902は、ワイヤレスまたは有線電気通信ネットワークを介してシグナリングを送信または受信するように適合されたコンポーネントまたはコンポーネントの集合を含み得る。カプラ904は、ネットワーク側インターフェース902を介した双方向通信を容易にするように適合されたコンポーネントまたはコンポーネントの集合を含み得る。送信機906は、ベースバンド信号を、ネットワーク側インターフェース902を介した送信に適した変調された搬送波信号に変換するように適合されたコンポーネントまたはコンポーネントの集合（例えば、アップコンバータ、電力増幅器など）を含み得る。受信機908は、ネットワーク側インターフェース902を介して受信された搬送波信号をベースバンド信号に変換するように適合されたコンポーネントまたはコンポーネントの集合（例えば、ダウンコンバータ、低ノイズ増幅器など）を含み得る。信号プロセッサ910は、ベースバンド信号を、デバイス側インターフェース912を介した通信に適したデータ信号に、またはこの逆に変換するように適合されたコンポーネントまたはコンポーネントの集合を含み得る。デバイス側インターフェース912は、信号プロセッサ910とホストデバイス内のコンポーネント（例えば、処理システム1300、ローカルエリアネットワーク（LAN）ポートなど）との間でデータ信号を通信するように適合されたコンポーネントまたはコンポーネントの集合を含み得る。
【００７４】
トランシーバ900は、任意のタイプの通信媒体を介してシグナリングを送信および受信し得る。一部の実施形態では、トランシーバ900は、ワイヤレス媒体を介してシグナリングを送信および受信する。一部の実施形態では、トランシーバ900は、セルラープロトコル（例えば、ロングタームエボリューション（LTE）など）、ワイヤレスローカルエリアネットワーク（WLAN）プロトコル（例えば、Wi−Fiなど）、または他のタイプのワイヤレスプロトコル（例えば、ブルートゥース（登録商標）、近距離通信（NFC）など）などのワイヤレス電気通信プロトコルに従って通信するように適合されたワイヤレストランシーバであり得る。このような実施形態では、ネットワーク側インターフェース902は、1つ以上のアンテナ／放射要素を備える。一部の実施形態では、ネットワーク側インターフェース902は、単一のアンテナ、複数の別々のアンテナ、または多層通信用に構成されたマルチアンテナアレイ（例えば、単入力多出力（SIMO）、多入力単出力（MISO）、多入力多出力（MIMO）など）を含み得る。他の実施形態では、トランシーバ900は、有線媒体、例えばツイストペアケーブル、同軸ケーブル、光ファイバなどを介してシグナリングを送信および受信する。特定の処理システムおよび／またはトランシーバは、図示されているコンポーネントのすべてまたはコンポーネントの一部のみを利用し得、集積のレベルはデバイスごとに異なり得る。
【００７５】
説明が詳細に記載されてきたが、添付の特許請求の範囲によって規定される本開示の精神および範囲から逸脱することなく、様々な変更、置換、および改変が行われ得ることを理解されたい。同じ要素は、様々な図において同じ参照番号で示されている。さらに、本開示の範囲は、本明細書に記載の特定の実施形態に限定されることを意図されておらず、当業者は、既存のまたは後に開発されるプロセス、機械、製造、組成物、手段、方法、またはステップが、本明細書に記載の対応する実施形態と実質的に同じ機能を果たす、またはこれと実質的に同じ結果を達成し得ることを、本開示から容易に理解する。したがって、添付の特許請求の範囲は、このようなプロセス、機械、製造、組成物、手段、方法、またはステップをその範囲内に含むことを意図されている。したがって、本明細書および本図面は、添付の特許請求の範囲によって規定される本開示の例示として単に見なされるべきであり、本開示の範囲内に含まれるありとあらゆる修正、変形、組み合わせ、または均等物を包含すると考えられる。
【符号の説明】
【００７６】
802  プロセッサ
804  メモリ
806  インターフェース
808  インターフェース
810  インターフェース
902  ネットワーク側インターフェース
904  カプラ
906  送信機
908  受信機
910  信号プロセッサ
912  デバイス側インターフェース
【図１】
2022500755.tif 000003
【図２Ａ】
2022500755.tif 000004
【図２Ｂ】
2022500755.tif 000005
【図３】
2022500755.tif 000006
【図４】
2022500755.tif 000007
【図５Ａ】
2022500755.tif 000008
【図５Ｂ】
2022500755.tif 000009
【図５Ｃ】
2022500755.tif 000010
【図５Ｄ】
2022500755.tif 000011
【図６Ａ】
2022500755.tif 000012
【図６Ｂ】
2022500755.tif 000013
【図６Ｃ】
2022500755.tif 000014
【図７】
2022500755.tif 000015
【図８】
2022500755.tif 000016
【図９】
2022500755.tif 000017
【図１０】
2022500755.tif 000018
【図１１】
2022500755.tif 000019
【手続補正書】
【提出日】令和3年4月21日(2021.4.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
説明が詳細に記載されてきたが、添付の特許請求の範囲によって規定される本開示の範囲から逸脱することなく、様々な変更、置換、および改変が行われ得ることを理解されたい。同じ要素は、様々な図において同じ参照番号で示されている。さらに、本開示の範囲は、本明細書に記載の特定の実施形態に限定されることを意図されておらず、当業者は、既存のまたは後に開発されるプロセス、機械、製造、組成物、手段、方法、またはステップが、本明細書に記載の対応する実施形態と実質的に同じ機能を果たす、またはこれと実質的に同じ結果を達成し得ることを、本開示から容易に理解する。したがって、添付の特許請求の範囲は、このようなプロセス、機械、製造、組成物、手段、方法、またはステップをその範囲内に含むことを意図されている。したがって、本明細書および本図面は、添付の特許請求の範囲によって規定される本開示の例示として単に見なされるべきであり、本開示の範囲内に含まれるありとあらゆる修正、変形、組み合わせ、または均等物を包含すると考えられる。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
有向非巡回グラフ（DAG）計算を処理するための方法であって、
複数のプロセッサによって、前記DAG計算を各ノード内で複数の非相互依存サブノードに分割するステップであって、前記複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を備える、ステップと、
前記複数のプロセッサによって、複数のサブDAG計算を構築するステップであって、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む、ステップと、
前記複数のプロセッサによって、前記複数のサブDAG計算のそれぞれの処理をスケジューリングするステップと、
前記複数のプロセッサによって、前記複数のサブDAG計算のそれぞれを並列で処理するステップと
を含む方法。
【請求項２】
前記複数のプロセッサによって、前記複数のサブDAG計算に中間共有メモリを割り当てるステップをさらに含む、請求項1に記載の方法。
【請求項３】
前記複数のプロセッサによって、各サブDAG計算の各サブノードの処理をスケジューリングするステップをさらに含む、請求項1または2に記載の方法。
【請求項４】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項1に記載の方法。
【請求項５】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項1に記載の方法。
【請求項６】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項1に記載の方法。
【請求項７】
それぞれのノード内の非相互依存サブノードの処理は、同じそれぞれのノード内の別の非相互依存サブノードの処理から独立している、請求項1に記載の方法。
【請求項８】
前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するステップをさらに含む、請求項1に記載の方法。
【請求項９】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項1に記載の方法。
【請求項１０】
各サブノードは、前記DAG計算のそれぞれのノードに関連付けられたサブタスクである、請求項1に記載の方法。
【請求項１１】
有向非巡回グラフ（DAG）計算を処理するためのコンピュータ命令を記憶する非一時的コンピュータ可読媒体であって、前記コンピュータ命令は、第1の処理ユニットおよび第2の処理ユニットを備える複数のプロセッサによって実行されたとき、
前記DAG計算を各ノード内で複数の非相互依存サブノードに分割するステップであって、前記複数のプロセッサは、マルチコアグラフィック処理ユニット（GPU）およびマルチコア中央処理ユニット（CPU）を備える、ステップと、
複数のサブDAG計算を構築するステップであって、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含む、ステップと、
前記サブDAG計算のそれぞれの処理をスケジューリングするステップと、
前記複数のサブDAG計算のそれぞれを並列で処理するステップと
を実行する、非一時的コンピュータ可読媒体。
【請求項１２】
複数のプロセッサによって動作されたとき、前記複数のサブDAG計算に中間共有メモリを割り当てるステップを実行する、請求項11に記載の非一時的コンピュータ可読媒体。
【請求項１３】
複数のプロセッサによって動作されたとき、各サブDAG計算の各サブノードの処理をスケジューリングするステップを実行する、請求項11または12に記載の非一時的コンピュータ可読媒体。
【請求項１４】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項11から13のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項１５】
前記DAG計算は、画像処理、映像処理、またはディープニューラルネットワーク処理アプリケーションを含む、請求項11から14のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項１６】
それぞれのサブDAG計算のサブノードの処理の完了は、前記それぞれのサブDAG計算の次のサブノードの処理の依存対象である、請求項11から15のいずれか一項に記載の非一時的コンピュータ可読媒体。
【請求項１７】
有向非巡回グラフ（DAG）計算を処理するためのデバイスであって、
命令を含む非一時的メモリストレージと、
中央処理ユニット（CPU）およびグラフィック処理ユニット（GPU）を備える複数のプロセッサであって、前記複数のプロセッサは、前記非一時的メモリストレージと通信し、前記複数のプロセッサは、
前記DAG計算を各ノード内で複数の非相互依存サブノードに分割し、
複数のサブDAG計算を構築し、各サブDAG計算は、前記DAG計算の異なるノードからの非相互依存サブノードを少なくとも含み、
前記複数のサブDAG計算のそれぞれの処理をスケジューリングし、
前記複数のサブDAG計算のそれぞれを並列で処理する
ために前記命令を実行する、複数のプロセッサと
を備えるデバイス。
【請求項１８】
前記複数のプロセッサは、前記複数のサブDAG計算に中間共有メモリを割り当てるために前記命令を実行する、請求項17に記載のデバイス。
【請求項１９】
前記複数のサブDAG計算のそれぞれの前記処理をスケジューリングする前記ステップは、各サブDAG計算のそれぞれのサブノードのタスクタイプに従う、請求項18に記載のデバイス。
【請求項２０】
前記複数のプロセッサは、前記DAG計算の出力データバッファ、出力画像バッファ、出力画像ファイル、または出力特徴を出力するために前記命令を実行する、請求項17に記載のデバイス。
【請求項２１】
前記分割するステップは、各ノードに関連付けられたタスクタイプおよび前記複数のプロセッサのメモリ能力に従う、請求項17に記載のデバイス。
【国際調査報告】
2022500755.tif 000020
2022500755.tif 000021