(57)【要約】  アプリケーションプログラムが、モバイルデバイス内の汎用アプリケーションプロセッサおよび補助プロセッサ(たとえば、DSP、GPUなど)によって実行されるためにどのように区分されオフロードされ得るかを自動的に判定するための方法、デバイス、およびシステム。モバイルデバイスは、有向非巡回グラフ(DAG)のパターンマッチングに基づいて補助プロセッサ上で実行するのに最も適したアプリケーションコードの一部分を判定することができる。具体的には、モバイルデバイスは、コード内、特にコードのデータフローグラフ内の1つまたは複数のパターンを特定し、特定された各コードパターンを、補助プロセッサ（たとえば、DSP）上で実行される際、ある利益を有することが既知である既定のグラフパターンと比較することができる。モバイルデバイスは、補助プロセッサ上でコードの一部分を実行するコストおよび/または利益を判定することができ、補助プロセッサに関連する、低いコストおよび/または高い利益を有する部分をオフロードすることができる。
2016531366.tif 000002
【特許請求の範囲】
【請求項１】
入力コードの一部分を補助プロセッサに好適であると自動的に判定する際に、コンピューティングデバイスが前記補助プロセッサ上で実行するために前記一部分を第1のプロセッサからオフロードするための方法であって、
有向非巡回グラフ(DAG)を含む、前記入力コードのグラフベースの中間表現を生成するステップと、
各ノードまたはノードの組合せを、既定の文法内の1つまたは複数のパターンと比較するステップであって、各パターンは、DAGパターンであり、コストメトリックに関連付けられる、ステップと、
前記各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を部分的にカバーするパターンのセットを特定するステップと、
最良の累積効果を有するパターンの前記特定されたセットの文法パターンの組合せに関連付けられた前記入力コードのセグメントを前記第1のプロセッサから前記補助プロセッサにオフロードするステップと
を含む、方法。
【請求項２】
各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較するステップが、前記各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較するステップを含む、請求項1に記載の方法。
【請求項３】
前記コンピューティングデバイスが、システムオンチップを含むデバイスである、請求項1に記載の方法。
【請求項４】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項1に記載の方法。
【請求項５】
前記既定の文法内の前記1つまたは複数のパターンが、前記補助プロセッサに好適であると知られている、請求項1に記載の方法。
【請求項６】
前記最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項1に記載の方法。
【請求項７】
前記各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成するステップをさらに含む、請求項1に記載の方法。
【請求項８】
有向非巡回グラフ(DAG)である、入力コードのグラフベースの中間表現を生成するための手段と、
各ノードまたはノードの組合せを、既定の文法内の1つまたは複数のパターンと比較するための手段であって、各パターンは、DAGパターンであり、コストメトリックに関連付けられる、手段と、
前記各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を完全にカバーするパターンのセットを特定するための手段と、
最良の累積効果を有するパターンの前記特定されたセットの文法パターンの組合せに関連付けられた前記入力コードのセグメントを第1のプロセッサから補助プロセッサにオフロードするための手段と
を含む、コンピューティングデバイス。
【請求項９】
各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較するための手段が、前記各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較するための手段を含む、請求項8に記載のコンピューティングデバイス。
【請求項１０】
前記コンピューティングデバイスがシステムオンチップを含む、請求項8に記載のコンピューティングデバイス。
【請求項１１】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項8に記載のコンピューティングデバイス。
【請求項１２】
前記既定の文法内の前記1つまたは複数のパターンが、前記補助プロセッサに好適であると知られている、請求項8に記載のコンピューティングデバイス。
【請求項１３】
前記最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項8に記載のコンピューティングデバイス。
【請求項１４】
前記各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成するための手段をさらに含む、請求項8に記載のコンピューティングデバイス。
【請求項１５】
メモリと、
第1のプロセッサと、
補助プロセッサと
を含む、コンピューティングデバイスであって、
前記第1のプロセッサは、前記メモリおよび前記補助プロセッサに結合され、演算を実行するためにプロセッサ実行可能命令とともに構成され、前記演算が、
有向非巡回グラフ(DAG)である、入力コードのグラフベースの中間表現を生成することと、
各ノードまたはノードの組合せを、既定の文法内の1つまたは複数のパターンと比較することであって、各パターンは、DAGパターンであり、コストメトリックに関連付けられる、比較することと、
前記各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を完全にカバーするパターンのセットを特定することと、
最良の累積効果を有するパターンの前記特定されたセットの文法パターンの組合せに関連付けられた前記入力コードのセグメントを前記第1のプロセッサから前記補助プロセッサにオフロードすることと
を含む、コンピューティングデバイス。
【請求項１６】
前記第1のプロセッサは、各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較することが、前記各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較することを含むように、演算を実行するためにプロセッサ実行可能命令とともに構成される、請求項15に記載のコンピューティングデバイス。
【請求項１７】
前記コンピューティングデバイスがシステムオンチップを含む、請求項15に記載のコンピューティングデバイス。
【請求項１８】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項15に記載のコンピューティングデバイス。
【請求項１９】
前記既定の文法内の前記1つまたは複数のパターンが、前記補助プロセッサに好適であると知られている、請求項15に記載のコンピューティングデバイス。
【請求項２０】
前記最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項15に記載のコンピューティングデバイス。
【請求項２１】
前記第1のプロセッサは、前記各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成することをさらに含む演算を実行するためにプロセッサ実行可能命令とともに構成される、請求項15に記載のコンピューティングデバイス。
【請求項２２】
入力コードの一部分を第1のプロセッサから補助プロセッサにオフロードするための演算をプロセッサに実行させるように構成されたプロセッサ実行可能ソフトウェア命令を記憶した非一時的プロセッサ可読記憶媒体であって、前記演算が、
有向非巡回グラフ(DAG)である、前記入力コードのグラフベースの中間表現を生成することと、
各ノードまたはノードの組合せを、既定の文法内の1つまたは複数のパターンと比較することであって、各パターンは、DAGパターンであり、コストメトリックに関連付けられる、比較することと、
前記各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を完全にカバーするパターンのセットを特定することと、
最良の累積効果を有するパターンの前記特定されたセットの文法パターンの組合せに関連付けられた前記入力コードのセグメントを前記第1のプロセッサから前記補助プロセッサにオフロードすることと
を含む、非一時的プロセッサ可読記憶媒体。
【請求項２３】
前記記憶されたプロセッサ実行可能ソフトウェア命令は、各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較することが、前記各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較することを含むように、前記プロセッサに演算を実行させるように構成される、請求項22に記載の非一時的プロセッサ可読記憶媒体。
【請求項２４】
前記記憶されたプロセッサ実行可能ソフトウェア命令が、システムオンチップを含むコンピューティングデバイス上で実行されるように構成される、請求項22に記載の非一時的プロセッサ可読記憶媒体。
【請求項２５】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項22に記載の非一時的プロセッサ可読記憶媒体。
【請求項２６】
前記既定の文法内の前記1つまたは複数のパターンが、前記補助プロセッサに好適であると知られている、請求項22に記載の非一時的プロセッサ可読記憶媒体。
【請求項２７】
前記最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項22に記載の非一時的プロセッサ可読記憶媒体。
【請求項２８】
前記記憶されたプロセッサ実行可能ソフトウェア命令は、前記各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成することをさらに含む演算を前記プロセッサに実行させるように構成される、請求項22に記載の非一時的プロセッサ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
異種のプロセッサコア上でのコード区分および実行を可能にする効率的な有向非巡回グラフパターンマッチングに関する。
【背景技術】
【０００２】
モバイル電子デバイス(たとえば、携帯電話、時計、ヘッドフォン、遠隔制御装置など)は、かつてよりも複雑になり、今や一般的に、多重プロセッサ、システムオンチップ(SoC)、およびモバイルデバイスユーザが彼らのモバイルデバイス上で複雑で電力消費の多いソフトウェアアプリケーション(たとえば、ビデオストリーミング、ビデオ処理など)を実行することを可能にする他のリソースを含む。複雑さおよび電力消費量のこの増加に伴い、モバイルデバイスのリソースおよび能力をより良く利用する新しい改善された処理技術が出現し始めている。
【０００３】
これらの出現している技術は、コードがデジタル信号プロセッサ(すなわち、DSP)などの補助プロセッサ上で実行するのに適するように、汎用アプリケーションプロセッサ上で実行するために設計されたコードをコンパイルすることができるシステムを含む。具体的には、アプリケーションプログラムは、ユニットまたはチャンクに区分される場合があり、ユニット/チャンクは、処理構成要素(たとえば、DSP、グラフィックス処理ユニット、またはGPUなど)についての特定された効率/機能に基づいて様々な処理構成要素に分配される場合がある。これにより、主処理ユニットすなわち中央処理ユニット(CPU)またはアプリケーションプロセッサは、電力を節約し、かつ/または性能を改善するために、その演算のうちのいくつかを補助プロセッサにオフロードすることが可能になる。
【０００４】
しかしながら、アプリケーションプログラムがどのように区分されるべきか、およびどんな区分が補助プロセッサ上で実行するのに最も適しているかを判定することは、難しい設計作業であることが多い。すなわち、演算を補助プロセッサにオフロードすることは、所与のコードセグメントを認識し、所与のコードセグメントを様々なタイプのコアまたは処理ユニットにおいて実行するのに好適な構成要素に区分する効率的な方法が存在する限り、モバイルデバイスの性能および電力消費特性を改善することができる。
【０００５】
既存の技術は、コードを特定し、かつ/またはコードを処理するための様々な技法を利用し得る。いくつかの技法は、自動コード区分を利用することができ、固有の並行処理および既知の通信コストを使用する、コードを区分するためのプログラム依存グラフによってアプリケーションコードを表し得る。これらの技法は、デジタル信号プロセッサ(DSP)などの特定の処理ユニットに役立つことが知られている可能性がある既定のパターンを利用しない。他の技法は、コード(または、バイナリ)内のイディオム(すなわち、命令の既知/既定のセット)を検出し、これらのイディオムをハードウェア支援命令(すなわち、複合命令セットコンピューティング命令または「CISC」命令)に置き換え得る。これらの技法は、通常、限定された粒度(大部分は、命令の直線)と、厳格なパターンまたは限定された自由度のいずれかなどの簡単なパターンとを扱うにすぎない場合がある。加えて、高水準のソースコードを使用して、重複コードを見つけ出し、クローンを検出するためのいくつかの技法が存在する。さらに、データベースシステムには、グラフパターンマッチングが使用されてきた。
【０００６】
低コスト命令を含むようにコードを調整するためにツリーパターンマッチングを利用する命令選択アルゴリズムを使用する他の技法が存在する。具体的には、最良のコストの命令のセット(すなわち、ツリー全体をカバーし、さらに最低のコスト/最高の利益をもたらす命令の組合せ)を見出すために入力コードに関連する入力ツリー内の様々なサブツリーを反復的にマッチングすることによって入力コード(たとえば、アプリケーション、ルーチンなど)に関する最良の命令セットを判定するために、ボトムアップ書換えシステム(または、BURS(bottom-up rewrite system))アルゴリズムが使用され得る。パターンマッチングに基づいて、コンピューティングデバイス上で実行するための新しい改善された命令セットが生成され得る。
【０００７】
しかしながら、既知の技法は、グラフベースの表現を使用して複雑なコードの一部分をオフロードするときには適していない場合がある。言い換えれば、既存の技法は、異種のマルチコアまたは分散システムのための最良のオフロードを特定するために、コードの有向非巡回表現をマッチングするコンパイラのバックエンドソリューションを使用しない場合がある。
【発明の概要】
【課題を解決するための手段】
【０００８】
様々な態様において、コンピューティングデバイスは、入力コードの一部分が補助プロセッサに好適であると自動的に判定され得るとき、その一部分をCPUまたはアプリケーションプロセッサ(「第1のプロセッサ」)から補助プロセッサにオフロードするための方法を実行することができる。態様の方法は、有向非巡回グラフ(DAG)であり得る、入力コードのグラフベースの中間表現を生成するステップと、各ノードまたはノードの組合せを、各パターンがDAGパターンでありコストメトリックに関連付けられ得る、既定の文法内の1つまたは複数のパターンと比較するステップと、前記比較に基づいて入力コードのグラフベースの中間表現を部分的にカバーするパターンのセットを特定するステップと、最良の累積効果を有するパターンについての特定されたセットの文法パターンの組合せに関連付けられた入力コードのセグメントを第1のプロセッサから補助プロセッサにオフロードするステップとを含み得る。一態様では、各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較するステップは、各ノードまたはノードの組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較するステップを含み得る。一態様では、コンピューティングデバイスは、システムオンチップを含み得る。一態様では、補助プロセッサは、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つであり得る。一態様では、既定の文法内のパターンは、補助プロセッサに好適であると知られている場合がある。一態様では、最良の累積効果は、最低の累積コストおよび最高の累積利益のうちの1つであり得る。一態様では、本方法は、各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較することに基づいて補助プロセッサに対して設定することができる入力コードのセグメントを示す、開発者に提示するための情報を生成するステップをさらに含み得る。
【０００９】
別の態様では、入力コードの一部分が補助プロセッサに好適であると自動的に判定され得る際にその一部分をオフロードするように構成されたコンピューティングデバイスは、上述の態様の方法の機能を実行するための手段を含み得る。
【００１０】
別の態様では、入力コードの一部分が補助プロセッサに好適であると自動的に判定され得る際にその一部分をオフロードするように構成されたコンピューティングデバイスは、メモリ、補助プロセッサ、ならびにメモリおよび補助プロセッサに結合されたプロセッサを含み得るが、このプロセッサは、上述の態様の方法の演算を実行するためのプロセッサ実行可能命令とともに構成され得る。
【００１１】
別の態様では、プロセッサ実行可能ソフトウェア命令を記憶した非一時的プロセッサ可読記憶媒体は、プロセッサに、入力コードの一部分が補助プロセッサに好適であると自動的に判定され得る際にコンピューティングデバイスがその一部分をオフロードするための演算を実行させるように構成され、記憶された演算は上述の態様の方法の演算を含む。
【００１２】
本明細書に組み込まれ、本明細書の一部分をなす添付の図面は、本発明の例示的な態様を示し、上記で与えられた全般的な説明および下記で与えられる発明を実施するための形態とともに、本発明の特徴を説明するのに役立つ。
【図面の簡単な説明】
【００１３】
【図１】有向非巡回グラフ(DAG)パターンマッチングに基づいて実行用のコードをCPUまたはアプリケーションプロセッサから補助プロセッサにオフロードするための態様の方法を示すプロセスフロー図である。
【図２】有向非巡回グラフ(DAG)パターンマッチングに基づいて実行用のコードをCPUまたはアプリケーションプロセッサから補助プロセッサにオフロードするための別の態様の方法を示すプロセスフロー図である。
【図３】様々な態様とともに使用するのに適した例示的な文法/コード入力DAGを示す図である。
【図４】DAGパターンマッチングに基づいて実行用のコード部分をCPUまたはアプリケーションプロセッサから補助プロセッサにオフロードするための態様の方法を示すプロセスフロー図である。
【図５】様々な態様とともに使用するのに適した例示的な文法/コード入力DAGを示す図である。
【図６】様々な態様とともに使用するのに適したスマートフォンスタイルモバイルコンピューティングデバイスの構成要素ブロック図である。
【発明を実施するための形態】
【００１４】
様々な態様について、添付の図面を参照して詳細に説明する。可能な場合はいつでも、同じまたは同様の部分を指すために図面全体を通して同じ参照番号が使用される。特定の例および実施態様に行われる参照は、例示目的のためであり、本発明の範囲および特許請求の範囲を限定することを意図していない。
【００１５】
「例示的」という言葉は、本明細書では「一例、事例、または実例として役立つ」ことを意味するように使用される。「例示的」として本明細書で説明する任意の実装形態は、必ずしも他の実装形態よりも好ましいか、または有利であると解釈されるべきではない。
【００１６】
本明細書では「モバイルコンピューティングデバイス」または「コンピューティングデバイス」という用語は、セルラー電話、スマートフォン(たとえば、iPhone(登録商標))、ウェブパッド、タブレットコンピュータ、インターネット対応セルラー電話、WiFi対応電子デバイス、携帯情報端末(PDA)、ラップトップコンピュータ、パーソナルコンピュータ、ならびに少なくとも1つのアプリケーションプロセッサ(または汎用プロセッサ)および補助プロセッサ(たとえば、デジタル信号プロセッサ、コプロセッサ、システムオンチップ上の別のプロセッサなど)を装備された同様の電子デバイスの任意の1つまたはすべてを指すために使用される。
【００１７】
様々な態様は、コードを表すパターンマッチング有向非巡回グラフ(DAG)に基づいて、コンピューティングデバイス内で実行用の入力コードの一部分をCPUまたはアプリケーションプロセッサ(本明細書では全体的に「第1のプロセッサ」と呼ぶ)から補助プロセッサにオフロードするための方法を提供する。コンピューティングデバイスは、特定のタイプのコア(たとえば、DSP、GPUなど)を用いて処理するのに都合が良いことが既知である、コード内の注目するパターンを自動的かつ効率的に検出するための態様の方法を実行することができる。コンピューティングデバイスは、入力コードの入力データフローグラフを部分的にカバーするDAGパターンのセットを自動的に認識することができ、補助プロセッサ上で実行されるときに最小コストに関連付けられたコードの一部分をオフロードするか、またはさもなければオフロードから最高の利益を提供することができる。これらの態様の方法は、一般的な入力コード(たとえば、一般的なJava(登録商標)言語ソースコード)を用いて演算するコンピューティングデバイスにおいて実装される場合があり、したがって、コード開発者による任意の特別な前処理またはフォーマット(たとえば、手作業で加えられたインジケータ、APIコール、既定のコードフォーマットなど)を必要としない場合がある。様々な態様を実装するコンピューティングデバイスは、補助プロセッサにオフロードするのに好適なコードの一部分を自動的に特定し、そのような特定された好適なコードを伝送し、転送し、またはさもなければそのコードのオフロードを実行するための従来の機構を使用することができる。
【００１８】
様々な態様の方法は、DAGのノードを、DAGも含む既定の文法パターンと比較するパターンマッチングアルゴリズムを利用する。様々な態様の方法は、コードの中間表現(IR)を判定し、パターンマッチングアルゴリズムを介して処理され得るDAG表現を生成するためにコンピューティングデバイスによって実行され得る。そのようなアルゴリズムは、コードのDAG表現におけるパターンを、補助プロセッサ上で実行するのに好適であると知られている、メモリ内に記憶されたDAGパターン(「文法」と呼ばれる)とマッチングしようと試みることができる。DAG表現は、巡回がないようにトリミングされ得る。たとえば、文法内のDAGパターンは、デジタル信号プロセッサ(DSP)上で効率的に実行するいくつかの簡単な関数に対応する場合がある。コンピューティングデバイスは、入力コードにおけるコードループまたは方法を表すDAGなどのDAG全体をカバーする文法パターンを特定することができ、文法パターンに関連付けられたコスト(または利益)に基づいて最良のマッチングするパターンを特定することができる。たとえば、入力コードの特定のDAGは、文法内のいくつかのパターンにマッチングされる場合があるが、マッチングするパターンのうちの1つは、補助プロセッサ上で関連のコードを実行するのに比較的低コストである場合がある。コンピューティングデバイスは、既定の文法内の複数の既知のDAGパターンが入力IRコード内で直ちに検出されるようにパターンマッチングを実行することができる。様々な態様において、コンピューティングデバイスの演算は、たとえば、実行時(JIT)コンパイラと組み合わせてランタイムに実行され得る。言い換えれば、入力コードと関連付けられたノードおよびエッジのグラフ(すなわち、エッジ方向およびノードタイプを分離することができないDAG)を用いれば、コンピューティングデバイスは、グラフ内のノード/エッジと文法内のパターンとの正確なマッチング部を見つけ出すためにパターンマッチング演算を実行することができる。マッチングするパターン自体は、いずれかのノードタイプという意味ではフレキシブル(たとえば、パターン内のある位置におけるタイプAまたはタイプB)である場合がある。正確なマッチングは、入力コードの部分グラフにわたる完全なパターンに関するものである。したがって、コンピューティングデバイスは、各々が入力を部分的にカバーしながら入力の部分グラフを完全にカバーする文法から、パターンを見つけ出すことができる。
【００１９】
一態様では、入力コードのDAG内の各ノードに関して、コンピューティングデバイスは、既定の文法のマッチングルール/パターンとともに(BURSソリューションにおいて同様に行われ得るように)ノードにマッチングするすべての考えられる「タイプ」のテーブルを計算することができる。コンピューティングデバイスは、(BURSソリューションにおいて同様に行われ得るように)各ノードにルートを持つパターンの累積コストを自動的に特定および/または記憶することもできる。コンピューティングデバイスは、(BURSソリューションにおいて同様に行われ得るように)ルートを持つDAGからボトムアップパスを実行することもできる。しかしながら、コンピューティングデバイスがあるノードを既定の文法内の既知のパターンとマッチングするとき、コンピューティングデバイスは、テーブルを再計算することなく、そのパターンに関する以前計算された結果を使用する場合がある。加えて、あるノードが文法内の特定のパターンとマッチングするときはいつでも、コンピューティングデバイスは、DAG内の(または、有向エッジを介して共有する)ノード間の接続がマッチングルールまたはパターンにおいて同様に表されるかどうかを確認することができる。たとえば、関数(たとえば、「store」関数)に対応するノードが文法パターンまたはルールにマッチングするとき、コンピューティングデバイスは、マッチングする文法パターンがパターンノード間の同様の関係を示すかどうか(たとえば、「load」および「store」演算が、それぞれ同じアレイデータ構造に対して読み書きの双方を行っているかどうか、など)を判定するために共有(または他のノード間の接続)をチェックする場合がある。態様の方法は、通常のツリーパターンマッチングを実行するのと同じ時間計算量で入力コードの中間表現および既定の文法内のDAGパターンをマッチングするためにコンピューティングデバイスによって実行される場合がある。
【００２０】
一態様では、コンピューティングデバイスは、パターンを表現するのに適したパターン記述言語(PSL)またはPSL技法を利用することができる。たとえば、コンピューティングデバイスは、コード表現と比較され得る、文法内のパターンを規定するためにPSLを使用することができる。さらに、コンピューティングデバイスは、入力コードのデータフローグラフに基づいてPSLを使用してコードを自動的に生成することができる。PSLを使用することによって、コンピューティングデバイスは、入力コードにおける厳格なパターンと「緩い(relaxed)」パターンの両方を表現することを可能にされ得る。たとえば、緩いパターンは、何らかの一般的な算術計算が何であるべきかを実際には指定することのないその算術計算を含むパターンである場合がある。言い換えれば、PSLを使用することは、コンピューティングデバイスによって結合的なまたは可換のパターンマッチングを可能にすることができる。一態様では、PSLは、緩いパターンを用いて「アフィン配列アクセスを含むループ」も表現するために使用される場合がある。
【００２１】
現在、多くのソフトウェア開発者は、彼らのアプリケーションを実行するコンピューティングデバイス内の様々な処理ユニットまたはコアの機能を理解していない場合があり、したがって、彼らのアプリケーションの一部分がこれらの様々なコアを効果的に使用するように対象設定され、またはさもなければ設計され得るかどうかを把握していない場合がある。一態様では、コンピューティングデバイスは、DSPまたはGPUなどの特定の補助プロセッサまたはコアのために最適化または構成され得る彼らのアプリケーション(または、ソースコード)内のコードの一部分(または、セグメント)を特定する際にそのようなソフトウェア開発者を助ける開発者ツールキットを有効にするように構成され得る。自動的にオフロードされるコード部分を特定するために以下に説明する演算と同様の演算を使用して、コンピューティングデバイスは、文法内の既定のDAGパターンに対応するコードの一部分を特定するためにコードを処理および評価し、評価されたコードのいくつかの部分がどのコアに好適であり得るかを示す有益な情報またはヒントを生成するように構成され得る。コンピューティングデバイスはまた、生成された有益な情報を提示する(たとえば、ソフトウェア開発者への有益な情報の提示をレンダリングする)ように構成され得る。そのような有益な情報は、コンピューティングデバイス上で実行される際に総合コード効率を増加させるために開発者がコンパイラおよび/または手動設定動作を用いて使用するために目指し得るコードの一部分を示す示唆を含み得る。したがって、この技術を用いれば、ソフトウェア開発者は、特定のプロセッサの詳細を理解する必要がない場合があるが、代わりに、彼らの好ましい高水準言語においてコードを簡単に書く場合があり、コンピューティングデバイスは、そのコードの様々な部分とともに使用するための適切なプロセッサを示す情報を特定し提示する場合がある。
【００２２】
図3および図5に関連する以下の図および説明において、様々な態様の方法および実装形態を例示するために、例示的な文法(ルールおよびコストを有する)および入力構造(たとえば、入力DAG)を示し説明する。そのような例は、内部に含まれる任意の特定の値、演算、関数、または構造と同様に、例示のためのものにすぎず、特許請求の範囲に記載された新規の態様の方法およびデバイスの範囲を限定するものではない。具体的には、特定の関数、ルール、または構造に関連付けられた数値「コスト」などの、そのような例に示された特定の例示的な値は、任意のものであり、単に例示のために提供される場合があり、実際のコストまたは実際の関数もしくは構造の利益とは何の関係もない場合がある。
【００２３】
図1は、コンピューティングデバイスが、DAGパターンマッチングに基づいてCPUまたはアプリケーションプロセッサから補助プロセッサ(たとえば、DSP、GPUなど)にオフロードするためのコードを選択するための態様の方法100を示す。態様の方法100は、DAGパターンを含む既知の文法(すなわち、既知のDAGパターンならびに関連のコストおよび/または利益のライブラリ)に対するパターンマッチングを実行するためにコンピューティングデバイス(たとえば、ラップトップ、スマートフォンなど)によって実行され得る。
【００２４】
様々なBURSアルゴリズムは、命令を組み合わせ、各命令/ノードに関連付けられたコストモデルを、命令の考えられる各組合せのコストと比較することによってコードセグメントの機能を達成するための命令の最良のセットを見つけ出すことができる。したがって、BURS命令選択方法は、DAGに適用されるとき、元の入力コードの目的を達成するために命令の最良のセットを見つけ出すように元の入力コードのコピーを作成する可能性を探索する必要があり、したがって、「np完全」問題を解いている。以下に説明する方法100および他の態様の方法は、入力コードのための新規の命令(または、代替の命令)を生成しないが、代わりに、CPUまたはアプリケーションプロセッサをDSPなどの補助プロセッサにオフロードするのに好適な、DAG内の各ノードまたはノードの組合せに関する複数のパターンを自動的に特定する。言い換えれば、態様の方法は、複数のパターンを特定し、オフロードするための最もコスト効果的なコードを選択し、したがってBURSアルゴリズムよりもはるかに簡単な問題を解くための非指数時間アルゴリズムとしてコンピューティングデバイスによって実行され得る。
【００２５】
ブロック102では、コンピューティングデバイスは、入力コードの有向非巡回グラフ(DAG)中間表現を生成することができる。たとえば、DAGは、1つの方法、方法のセット、またはアプリケーション全体のソースコードに基づいて生成され得る。そのようなグラフベースの中間表現は、データフローグラフとして知られ得る。一般に、コードの中間表現は、入力コード(たとえば、ソフトウェアアプリケーションプログラムまたはソフトウェアプログラムの一部分)を構文解析し、コードの構造のグラフィカルマッピングまたは記号マッピングを判定することによって生成され得る。たとえば、ある方法に関する入力コードのDAGなどの中間表現は、コード内のシンタックスおよび他の関数要素または演算要素を示す場合がある。中間表現は、プログラムを分析および構成するために動的コンパイラまたは実行時(JIT)コンパイラによって使用され得るアノテーションなどの追加の情報を含み得る。
【００２６】
DAG中間表現は、エッジと呼ばれ得る単方向の接続部とともにノード(頂点と呼ばれることもある)を含み得る。DAGノード間のそのような接続部は、ノード間の論理的関係を表し得る。たとえば、リーフノードとルートノードとの間の接続部は、リーフノードが関数のオペランドであることを示す場合がある。さらに、DAGは、コードループの表現などのサイクルを含まない場合がある。具体的には、生成されたDAGは、入力コード内の固有の任意のループまたはサイクルにかかわらず、中間表現内にサイクルが存在しないようにトリミングまたは調整され得る。様々な態様において、コンパイラルーチン、モジュール、命令、または他の構成要素が、アプリケーションの入力コード(たとえば、ソースコード、バイナリコードなど)を、接続されたリーフおよび/またはノードのDAG構造に変換するためにコンピューティングデバイスによって利用され得る。
【００２７】
DAGは、BURSアルゴリズムにおいて使用され得るように、入力ツリー(またはシンタックス入力ツリー)と同じでないことに留意されたい。たとえば、様々なBURSの実装形態では、入力コードは、様々なリーフノードおよびサブツリーを含み任意のリーフノードからルートノードへ単一方向に移動し得る表現入力ツリーに変換され得る。態様の方法は、ツリーよりも多い、ノード間の接続部に関する情報を含むDAGを生成することができる。DAGノードは、様々な方向に、および/または複数の接続部と接続される場合があり、したがって、以下に説明するように、ノードを評価しパターンマッチングをするための追加の演算を必要とする。
【００２８】
ブロック104では、コンピューティングデバイスは、生成されたDAGの各ノードまたはノードの組合せを、文法内の1つまたは複数の既定のDAGパターンと比較することができるが、各パターンはコストメトリックに関連付けられる。言い換えれば、コンピューティングデバイスは、文法パターンを用いてマッチング部を検出するために生成されたDAGのノードを横断することができる。コンピューティングデバイスは、ボトムアップで生成されたDAGの各ノードを訪問することができ、基本的に、あるノード自体を訪問する前にそのノードの子(すなわち、リーフノード)を訪問する。コンピューティングデバイスがノードを訪問するとき、コンピューティングデバイスは、そのノードにマッチングするすべてのDAGパターン(または、サブパターン)を探索し、そのノードがそれらの有効化パターンルール識別子および関連のコスト(たとえば、そのノードにルートを持つDAGパターンのコスト)を用いてマッチングされ得る、すべての考えられるタイプ(たとえば、文法内の「非終端」)のテーブルを更新することができる。生成されたDAGのルートにおいて、コンピューティングデバイスは、文法からのパターンルールを用いて生成されたDAGの各ノード(または、ノードの組合せ)をカバーする低コストの方法を見つけ出すことができる。
【００２９】
様々な態様において、文法は、関連の情報とともに既定のDAGパターンを記憶するデータ構造であるにすぎない場合がある。たとえば、文法は、特定のアーキテクチャ上のいくつかの方法、効率、またはコスト、デバイス、オペレーティングシステムなどにおいて実行されることが知られている命令に関連付けられたDAGパターン(または、構造)のリストである場合がある。他の技法と異なり、態様の方法は、文法内に、ツリーではなく、複数の規定のDAGパターンを記憶することができる。たとえば、記憶された既定のパターンは、ルートを持つDAGのセットとして表現される場合があり、パターンの各々は、関連のパターンに関するコストおよび/または利益メトリックを含み得る。様々な態様において、文法は、モバイルデバイス内のDSPまたはGPUなどの特定のコアに好適であると知られているDAGパターンを含み得る。そのような態様文法の非限定的な例について以下で説明する。
【００３０】
ブロック104における演算は、オフロードするのに好適なコードを任意の開発者に手作業で示すように要求することなく、そのような好適なコードを自動的に判定することができる。様々な態様において、ブロック104における演算についての比較は、ノードの特定もしくはタイプ(たとえば、特定の演算に対応するリーフなど)およびノード構成、接続部、または配置(たとえば、特定のノード間の有向接続部)に基づいて文法パターンがDAGノードにマッチングするかどうかを判定することを含み得る。これらの比較を行うとき、コンピューティングデバイスは、DAG内のノードの向き、接続部、および依存性を判定することができる。たとえば、コンピューティングデバイスは、生成されたDAG内のノードのサブグループが、2つのレジスタリーフ(たとえば、レジスタ内に記憶された整数値)と、ある数学演算(たとえば、加算、乗算など)に対応するルートノードとを含むと判定することができる。一態様では、ノードと文法との比較は、生成されたDAGの各ノードまたはノードの組合せを、ヒューリスティックテーブル内に記憶されたパターン情報と比較することを含み得る。
【００３１】
ブロック106では、コンピューティングデバイスは、前記比較に基づいて生成されたDAGを部分的にカバーする文法パターンのセットを特定することができる。言い換えれば、ブロック104の演算における比較に基づいて、コンピューティングデバイスは、DAGのすべてのノード(したがって、入力コードのすべての要素)に関連またはリンクする文法内に規定された様々なDAGパターンを認識することができる。たとえば、特定された文法パターンのセットは、生成されたDAGにおいて表される各変数および関数に関連付けられた文法パターンを含み得る。様々な態様において、この特定されたセットは、生成されたDAGの特定の要素に関する2つ以上の文法パターンを含み得る(たとえば、関連するコスト/利益を有する複数の記憶されたパターンは、生成されたDAGの特定のノードまたはノードの組合せにマッチングし得る)。
【００３２】
ブロック108では、コンピューティングデバイスは、特定された最良の累積効果を有するパターンについての特定されたセットの文法パターンの組合せに関連付けられた入力コードのセグメントをオフロードすることができる。これは、文法パターンについての特定されたセットのコストおよび利益を判定し、最低コストを有するパターンについての特定された組合せに関連付けられたコードのセグメントをCPUまたはアプリケーションプロセッサから補助プロセッサ(たとえば、DSP、GPUなど)にオフロードすることによって達成され得る。様々な態様において、これらのセグメントは、最低の累積コスト(または、最高/最大の累積利益)が既定のしきい値を超えるとオフロードされ得る。たとえば、入力コード(または、入力コードのセグメント)は、文法パターンについての特定されたセットがCPUまたはアプリケーションプロセッサからDSPに有益なオフロードに関する最大コストしきい値を超えないコストの組合せに関連付けられると、DSPにオフロードされ得る。
【００３３】
図2は、コンピューティングデバイスが、DAGパターンマッチングに基づいて補助プロセッサ(たとえば、DSP、GPUなど)にオフロードするためのコードを選択するための態様の方法250を示す。方法250は、DAG内に規定されたノード間の同じ接続部を含むマッチングするパターンを確認するためにパターンを再評価するための明示的な演算を方法250が含むことを除けば、上述の方法100と同様である。ブロック102では、コンピューティングデバイスは、上述のように、入力コードの有向非巡回グラフ(DAG)中間表現を生成することができる。ブロック104では、コンピューティングデバイスは、生成されたDAGの各ノードまたはノードの組合せを、文法内の1つまたは複数の既定のDAGパターンと比較することができるが、各パターンはコストメトリックに関連付けられる。ブロック252では、コンピューティングデバイスは、ノードまたはノードの組合せが文法内のパターンにマッチングするとき、追加のパターンおよび累積コストを特定するためにDAGを再評価することができる。言い換えれば、DAGがノード間の有向エッジすなわち接続部を含むとき、コンピューティングデバイスは、文法の任意のマッチングされたパターンが、生成されたDAG内のノード構成とノードに関連付けられたエッジの任意の方向の両方に確実にマッチングするように確認評価パスを実行する(たとえば、DAGを再横断する)ように構成され得る。ブロック106では、コンピューティングデバイスは、前記比較に基づいて生成されたDAGを部分的にカバーする文法パターンのセットを特定することができる。たとえば、DAGの横断および再横断に基づいて、コンピューティングデバイスは、DAGの構成、ノードタイプ、およびエッジをマッチングするために確認される文法パターンのセットを特定することができる。ブロック108では、コンピューティングデバイスは、最良の累積効果を有するパターンについての特定されたセットの文法パターンの組合せに関連付けられた入力コードのセグメントをオフロードすることができる。
【００３４】
図3は、様々な態様とともに使用するのに適した、入力コードに関連する例示的な文法300および入力DAG320を示す。文法300は、各々がルール識別子(たとえば、「[r]」、「[r']」など)、非終端シンボル、ルールに関連付けられたコスト(または、コストメトリック)、およびルールに関連付けられたDAGパターン(たとえば、DAGパターンまたは整数などの終端ノードを形成するノードのセット)を含む、ルール304〜306を含み得る。ルールによって示されたコストおよび/または利益は、文法のDAGパターンに関連付けられた演算を実行することに関連する、コンピューティングデバイスおよび/または補助プロセッサに対する労力、料金、時間、または値の一般的な表現である場合があり、処理サイクル、利用されたリソース、またはその実行を定量化するための他のメトリックの近似値である場合がある。たとえば、ルールのコストは、プロセッササイクルの数、時間、バッテリー寿命、または個々のルールに関連付けられた命令を実行するのに必要な他のリソースを表す場合がある。テンプレートアイテム302は、文法300内のルールの構造を示すことができる。様々な態様において、非終端シンボルは、項、シンボル、あるいはレジスタまたは関数もしくは表現の名称などの、構造または終端値に関連付けられ得る他の情報を含み得る。
【００３５】
一般に、デバイスは、レジスタ内にすでに記憶された値にアクセスするか、またはその値を処理するために任意のリソースを消費することを要求されない場合がある。したがって、様々な態様文法は、レジスタを参照し、コスト0に関連付けられる(すなわち、そのような文法ルールはコストを有しない場合がある)か、またはコスト0に関連付けられない場合があるルールを含み得る。様々な態様において、DAGリーフノードは、通常、終端(たとえば、整数)または非終端であり得る。
【００３６】
ルール304〜306の各々は、DSPなどの補助プロセッサ上で実行するのに好適であり得る方法または他の演算に関連付けられ得る。たとえば、第1のルール304(すなわち、「[r]」ルール)は、DSP上で実行されるとき、あるコストを有する「array_copy」演算に関連付けられ得る。そのような演算は、配列データ内の特定のインデックスに記憶された整数などの値を、その配列データ構造の別のインデックスにコピーするための機能またはルーチンであり得る。第2のルール306(すなわち、「[r']」ルール)は、配列データ構造と組み合わせて使用される整数インデックス値などのインデックス表現に関連付けられる場合があり、別の関連のコストを有する場合がある。
【００３７】
上述のように、入力コードは、様々な機能を含む、ソースコードまたはバイナリコードなどのソフトウェア命令であり得る。たとえば、入力コードは、別のレジスタ内に記憶するための、レジスタ内に記憶された2つの値を加算する演算などの数学演算を含み得る。図3に関して、文法300とともに使用するための例示的な入力コードは、配列の要素をあるインデックスから別のインデックスにコピーするために機能するコード(すなわち、配列コピー機能)であり得る。たとえば、入力コードは、「A[6]=A[5]」によって表される演算である場合があり、ここで、「A」は配列変数名であり得る。この配列割当て関数を認識するためのパターンは、入力コードの特定の要素が2つ以上の他のノード(たとえば、共有ノード)に接続され得るとき、簡単なツリーとして表現されない場合がある。したがって、入力コードは、入力DAGによって表され得る。一態様では、パーサ機能は、「A[6]=A[5]」演算を、次の演算セットすなわち、array_copy=store(array_base,index_expr,load(array_base,index_expr))に変換することができるが、ここで、「array_copy」は既知の関数であり、「store」は特定の位置(たとえば、ある配列インデックスに関連付けられたメモリ位置)における値を記憶または保存する既知の関数であり、「array_base」は配列データ構造に関連するメモリ位置を表し、「index_expr」は配列インデックスがアドレス指定される指示であり、「load」は記憶された値をレジスタ内に配置することなどによって記憶された値をアクセス可能にし得る既知の関数である。コンピューティングデバイスは、そのような例示的な入力コードを入力DAG320に変換することができる。
【００３８】
入力DAG320は、入力コードを完了するのに必要とされるパーサによって認識される演算および要素のセットを表すノード322〜330を含み得る。具体的には、入力DAG320は、第1の「index_expr」要素を表す第1のノード324(たとえば、配列インデックス「5」)、第2の「index_expr」要素を表す第2のノード326(たとえば、配列インデックス「6」)、「array_base」要素を表す第3のノード322(たとえば、コンピューティングデバイスメモリ内の「A」配列の位置)、「load」関数を表す第4のノード328、および「store」関数を表す第5のノード330を含み得る。第3のノード322は、第4のノード328と第5のノード330の両方への接続部(すなわち、エッジ)を有するとき、共有ノードであり得る。言い換えれば、「A[6]=A[5]」の例示的な入力コードに関して、個々の「load」および「store」関数はどちらも、それぞれ、値をローディングおよび記憶するための配列「A」にアクセスするように要求され得る。
【００３９】
入力DAG320は、上述のように、文法300と比較され得る。具体的には、コンピューティングデバイスは、第1のノード324が第2のルール306(すなわち、「r'」)にマッチングし、第2のノード326も第2のルール306(すなわち、「r'」)にマッチングし、入力DAGのパターン全体(すなわち、すべてのノード322〜330)が第1のルール304(すなわち、「r」)にマッチングすることを特定することができる。様々な態様において、入力DAG320要素と文法300とのマッチングは、ノードタイプおよびノード間の接続部をもマッチングする(すなわち、要素間の正しい共有を確認する)ことを含み得る。これらのマッチング部に基づいて、コンピューティングデバイスは、入力DAG320の要素の累積効果、したがって補助プロセッサ上で実行される入力コードのコストまたは利益を判定することができる。図3の任意のコスト値に基づく非限定的な説明目的で、コンピューティングデバイスは、第2のルール306にマッチングする2つのノードが各々コスト1に相当し、入力DAG320全体のマッチングがコスト10に相当し、総コストが12になると判定することができる。
【００４０】
図4は、コンピューティングデバイスが、DAGパターンマッチングに基づいてCPUまたはアプリケーションプロセッサから補助プロセッサにオフロードするためのコードを選択するための態様の方法400を示す。方法400は、図1〜図2に関して上述した態様の方法の詳細な実装形態と見なされ得る。
【００４１】
ブロック402では、コンピューティングデバイスは、補助プロセッサ(たとえば、DSP、GPUなど)に好適であると知られている関数に関連する文法を規定することができる。文法は、非終端に相当するルールの記憶されたセット、テーブル、もしくはデータベース、オペランド、および/または関連のコストメトリックを有するDAGパターンを含み得る。たとえば、文法は、コストメトリックまたは利益メトリックを含むルールと、DSPに好適であると知られている高速フーリエ変換(FFT)関数に関係付けられた関連のDAGパターンとを含み得る。そのような文法は、あらかじめ決定され、コンピューティングデバイス上にローディングされるか、またはさもなければ記憶され得る。
【００４２】
ブロック404では、コンピューティングデバイスは、入力コードの次の部分のDAG中間表現を生成することができる。たとえば、コンピューティングデバイスは、アプリケーション内の方法に関するDAGを生成することができる。方法400が最初に実行されるとき(すなわち、第1の反復)、次の部分は、入力コード内のコードの第1の部分である場合がある。一態様では、コンピューティングデバイスは、入力コードを方法または演算コードの他のブロックに区分するために、モジュール、ルーチン、ソフトウェア、または他の命令を利用することができる。さらに、コンピューティングデバイスは、たとえば、入力コードがループであるとき、生成されたDAGからサイクルを除去するための演算を実行することができる。様々な態様において、コンピューティングデバイスは、DAGが演算ループ(たとえば、「for」ループなど)のコードを表すように入力コードを区分することができる。たとえば、コンピューティングデバイスは、入力コードの方法内のループが補助プロセッサ上での実行に好適であるかどうかを判定するために方法400を実行するにすぎない場合がある。
【００４３】
ブロック406では、コンピューティングデバイスは、マッチング部を特定するために、生成されたDAGのノードを既定された文法パターンと比較することができる。たとえば、コンピューティングデバイスは、コンピューティングデバイスのレジスタ内に記憶される生成されたDAGの入力値(たとえば、整数値、浮動小数点値など)を、文法のルールに規定された構造と比較することができる。比較されたノードは、生成されたDAG内のリーフノード、ルートノード、および他のノードの組合せであり得る。様々な態様において、方法400の各ループにおいて比較されるノードは、生成されたDAGのサブセット、生成されたDAGの所定の数のノード、またはエッジを介して接続されたノード(たとえば、生成されたDAG内で表されるサブルーチンまたはサブファンクションに関連するノード)の組合せである場合がある。たとえば、ブロック406において演算と比較されるノードは、「load」関数または「store」関数に対応する生成されたDAGのノード(たとえば、配列を表すノード、インデックス表現を表すノード、および「load」関数ノード)のセットである場合がある。あるいは、この比較は、ノード単位のベースで行われ得る(たとえば、リーフノードを文法内の個々のノードパターンと比較する、など)。
【００４４】
さらに、DAGがノード間の有向接続部(たとえば、ノード間の有向エッジ)を利用するので、マッチングするパターンを特定することは、生成されたDAGのノードが、同じノード構成(たとえば、別のタイプの別のノードに接続されたあるタイプの2つのリーフノード)とノード間の同じ方向のエッジの両方を有する文法のパターンにマッチングするときにだけ起こり得る。言い換えれば、パターンマッチングは、生成されたDAGおよび文法のノードタイプと接続部の両方が同じときに起こり得る。したがって、コンピューティングデバイスは、対応するノードに関して同じエッジ方向を含む任意のマッチングする文法パターンを確認するために、生成されたDAG内のノードが共有される(すなわち、このノードが2つ以上のノードに至る入力である)際にエッジ方向を比較することもできる。たとえば、コンピューティングデバイスは、生成されたDAGからのノードの組合せおよび文法内のマッチングするパターンがマッチングするノード間で同じエッジ方向を共有するかどうかを判定することができる。これは、比較されたノードに関して生成されたDAGを再横断するものと見なされ得る。
【００４５】
ブロック406の演算は、図1および図2を参照しながら上述したブロック104および252の演算と同様であり得る。たとえば、コンピューティングデバイスは、規定された文法のパターンと生成されたDAG内のリーフノード(たとえば、整数ノード、レジスタノードなど)との間に任意のマッチング部が存在するかどうかを特定することができる。さらに、ブロック406の演算は、コード開発者によって提供される任意のマニュアル指示を必要としない場合がある(すなわち、比較は自動であり得る)。
【００４６】
判定ブロック412では、コンピューティングデバイスは、比較に基づいて生成されたDAGのノードと既定された文法パターンとの間に任意のマッチング部が存在するかどうかを判定することができる。たとえば、コンピューティングデバイスは、生成されたDAGのリーフノードが文法のルール内の任意のパターン/ノードタイプにマッチングするかどうかを判定することができる。上述のように、文法は、様々な構成を表す一方でさらにDAG内のある演算および/または様々な演算(たとえば、shift、loadなど)にマッチングし得る複数のパターン(たとえば、リーフおよびルートノード)を含み得る。たとえば、コンピューティングデバイスは、DAG(または、DAGのサブセット)を文法と比較し、マッチングする、文法内のいくつかのDAGパターンを特定することができる。
【００４７】
比較に基づいてマッチング部が存在しない(すなわち、判定ブロック412=「No」)場合、コンピューティングデバイスは、判定ブロック416の演算に続くことができる。
【００４８】
任意の態様では、比較に基づいてマッチング部が存在しない(すなわち、判定ブロック412=「No」)場合、コンピューティングデバイスは、判定ブロック426の演算に続くことができる。言い換えれば、任意のノードまたはノードの組合せが規定された文法内のパターンにマッチングされ得ないとき、コンピューティングデバイスは、入力コードの現在の部分を補助プロセッサにオフロードすることができないと判定する場合があり、もしあれば、次の部分に続く場合がある。
【００４９】
しかしながら、比較に基づいて少なくとも1つのマッチング部が存在する(すなわち、判定ブロック412=「Yes」)場合、ブロック414において、コンピューティングデバイスは、最良の利益またはコストを有するマッチングするパターンを選択することができる。言い換えれば、生成されたDAGの現在のノードまたはノードのサブセットが文法内の複数のDAGパターンにマッチングするとき、コンピューティングデバイスは、最低のコストまたは最高の利益を有するマッチングする文法パターンを選択することができる。たとえば、コンピューティングデバイスは、パターンマッチング部に関連付けられ文法内に規定されたコストを比較することができ、最低のコストを有するパターンを選択することができる。あるいは、規定された文法内の情報に基づいて、コンピューティングデバイスは、マッチングするパターンに関連付けられた任意の利益を評価することができ、他のマッチングするパターンのうちのいずれかのコストを上回る利益を有するパターンを選択することができる。たとえば、コンピューティングデバイスは、DAGのノードの構成による極めて低いコストまたはいくつかの追加の利益を有するパターンなどの、補助プロセッサに特に好適であると知られているマッチングするパターンを選択することができる。上述のように、文法内のパターン(または、ルール)のコストまたは利益は、リレーショナルデータベースまたは他のデータ構造内などに各パターンに関して記憶され得る。一態様では、コンピューティングデバイスは、ブロック418の演算においてアクセスされ使用され得る、マッチングするパターンの識別情報、命令のコスト、または他の識別情報をデータ構造内に記憶することなどによって、最良の効果を有する選択されたマッチングするパターンを示す情報を記憶することができる。
【００５０】
判定ブロック416では、コンピューティングデバイスは、生成されたDAG全体が評価されたかどうかを判定することができる。たとえば、ブロック406の演算を用いて、生成されたDAGのノードのサブセットのみが文法と比較されてきたとき、コンピューティングデバイスは、コードの全部分が評価されるまで生成されたDAGを横断し続ける場合がある。様々な態様において、生成されたDAGのルートノードは、DAGを生成するのに使用される入力コード内の最後のまたは最終的な演算、ステップ、命令、または結合子を表すことができる。
【００５１】
生成されたDAG全体が評価されなかった(すなわち、判定ブロック416=「No」)場合、コンピューティングデバイスは、ブロック406において、生成されたDAGのさらなるノードを文法パターンと比較することによってコードの一部分の残りを評価し続けることができる。このように、コンピューティングデバイスは、入力コードの一部分に関する生成されたDAGのノードのすべてを反復的に評価することができる。
【００５２】
生成されたDAG全体が評価された(すなわち、判定ブロック416=「Yes」)とき、ブロック418において、コンピューティングデバイスは、補助プロセッサ用に入力コード部分の累積効果(たとえば、利益またはコスト)を特定することができる。たとえば、コンピューティングデバイスは、DAGにマッチングされた文法の個々のパターンのコストメトリックに基づいて組み合わせられたコストを判定することができる。コンピューティングデバイスは、生成されたDAG内の各個々の部分に関して特定されたコストおよび/または利益を加えることによって累積効果を特定することができ、ブロック418の演算は、ブロック414の演算中に記憶されたデータにアクセスし、これらのデータを組み合わせることを含み得る。判定ブロック420では、コンピューティングデバイスは、累積効果が補助プロセッサ(たとえば、DSP、GPUなど)に適しているかどうかを判定することができる。一態様では、コンピューティングデバイスは、ブロック418において特定された累積利益またはコストを、コンピューティングデバイス内に記憶された既定のしきい値と比較することができる。別の態様では、コンピューティングデバイスは、生成されたDAGが完全にカバーされるとき、入力コードの一部分が補助プロセッサに適していると判定することができる。言い換えれば、コンピューティングデバイスは、現在のDAG内のすべてのノードまたはノードの組合せが規定された文法内のパターンにマッチングされるとき、関連のコード部分がオフロードするのに適していると判定することができる。累積効果が補助プロセッサに適している(すなわち、判定ブロック420=「Yes」)場合、ブロック424において、コンピューティングデバイスは、入力コードの一部分をCPUまたはアプリケーションプロセッサから補助プロセッサにオフロードすることができる。
【００５３】
累積効果が補助プロセッサに適していないとコンピューティングデバイスが判定する(すなわち、判定ブロック420=「No」)場合、または部分がオフロードされた場合、コンピューティングデバイスは、判定ブロック426において評価すべきコード部分がさらに存在するかどうかを判定することができる。たとえば、コンピューティングデバイスが方法単位のベースで入力コードを構文解析するように構成されるとき、コンピューティングデバイスは、入力コード全体が評価されるまでブロック404〜424の演算を反復的に実行することができる。入力コードの部分がさらに存在する(すなわち、判定ブロック426=「Yes」)場合、コンピューティングデバイスは、ブロック404の演算に続くことができる。入力コードの部分がこれ以上存在しない(すなわち、判定ブロック426=「No」)とき、方法400は終了し得る。
【００５４】
図5は、様々な態様とともに使用するのに適した、入力コードに関連する例示的な文法500および入力DAG550を示す。図5の例示的な文法500は、様々なパターンおよび入力DAG550のノードにマッチングされ得る、いくつかのルール504〜514を含む。テンプレートアイテム502は、文法500内のルールの構造を示すことができる。第1のルール504(すなわち、「[r0]」ルール)はDAGパターン「S」によって表されるノードまたはノードの組合せに関連付けられる場合があり、第2のルール506(すなわち、「[r1]」ルール)はDAGパターン「A」によって表されるノードまたはノードの組合せに関連付けられる場合があり、第3のルール508(すなわち、「[r2]」ルール)はDAGパターン「B」によって表されるノードまたはノードの組合せに関連付けられる場合があり、第4のルール510(すなわち、「[r3]」ルール)はDAGパターン「C」によって表されるノードまたはノードの組合せに関連付けられる場合があり、第5のルール512(すなわち、「[r4]」ルール)はDAGパターン「D」によって表されるノードまたはノードの組合せに関連付けられる場合がある。ルール504〜512に関連付けられたDAGパターンは、様々なノードタイプおよび/または演算(たとえば、整数、レジスタ、「load」、「store」、「add」など)を表すことができる。加えて、ルール506〜512は各々、第1のコストを有する場合があり、ルール504は、第2のコストを有する場合がある。
【００５５】
しかしながら、第6のルール514(すなわち、「[r']」ルール)は、ルール506〜512に対するDAGパターンの組合せ(たとえば、DAGパターン「A」、「B」、「C」、および「D」の組合せ)であるDAGパターンに関連付けられる場合がある。たとえば、第6のルール514は、特定のコードループ(たとえば、「loop_a」)に対応する場合がある。第6のルール514はこれらのDAGパターンのすべてを含むが、第6のルール514に関するコストは、極めて低い(すなわち、「A」、「B」、「C」、および「D」に関する個々のルールに関連付けられたコストの組合せよりも低い)場合がある。これは、補助プロセッサが演算のある組合せを特にうまく実行する場合である可能性があり、したがって、入力コードがその組合せを含むとき、多大な利益が享受される。
【００５６】
入力DAG550は、DAG要素にマッチングされた最良のルールを示すアノテーションを示す。具体的には、コンピューティングデバイスが図1、図2、または図4を参照しながら上述した態様の方法を実行するとき、ノード552、562、および564は各々、第1のルール504(すなわち、「[r0]」)にマッチングされ得る。しかしながら、ノード554、556、558、および560は、まとめて、第6のルール514(すなわち、「[r']」)にマッチングされ得る。言い換えれば、ノード554〜560は個々に、ある累積コストに関するルール506〜512にマッチングされ得るが、コンピューティングデバイスは、ノード554〜560が、より低いコスト（またはより高い利益）の第6のルール514のパターンにマッチングするように組み合わせられ得ると特定する場合がある。図5の任意のコスト値に基づく非限定的な説明目的で、ノード552、562、および564に関連付けられた第1のルール504のコストは、第6のルール514のコストと組み合わせられ、入力DAG550の総コスト10を見つけ出すことができる。
【００５７】
図6は、様々な態様とともに使用するのに適したスマートフォンタイプモバイルコンピューティングデバイス600のシステムブロック図である。スマートフォンモバイルコンピューティングデバイス600は、内部メモリ602と、ディスプレイ603と、スピーカ654とに結合されたプロセッサ601を含み得る。スマートフォンモバイルコンピューティングデバイス600は、デジタル信号プロセッサすなわちDSP606などの補助プロセッサをさらに含み得る。様々な態様において、DSP606およびプロセッサ601は、たとえば、内部バスを介して、またはシステムオンチップ設計の一部として接続され得る。加えて、スマートフォンモバイルコンピューティングデバイス600は、プロセッサ601に結合されワイドエリアワイヤレス通信ネットワークを介して通信することができる、セルラーネットワークもしくはWiFi無線などの、ワイヤレスデータリンクおよび/または長距離ワイヤレス信号送受信機605に接続され得る、電磁放射を送信および受信するためのアンテナ604を含み得る。一態様では、アンテナ604も、DSP606に結合され得る。スマートフォンモバイルコンピューティングデバイス600は、他のモバイルコンピューティングデバイスと通信するか、またはペアリングすることができる別個の短距離無線送受信機624を含み得る。スマートフォンモバイルコンピューティングデバイス600は、通常、ユーザ入力を受信するためのメニュー選択ボタンまたはロッカースイッチ608も含み得る。加えて、スマートフォンモバイルコンピューティングデバイス600は、プロセッサ601および/またはDSP606に結合された、加速度計610、ジャイロスコープ611、およびGPS受信機チップ614を含み得る。一態様では、スマートフォンモバイルコンピューティングデバイス600は、プロセッサ601および/またはDSP606に結合された、マイクロフォン612およびカメラ613も含み得る。別の態様では、スマートフォンモバイルコンピューティングデバイス600は、グラフィックス処理ユニット(図示せず)などの他の補助プロセッサも含み得る。
【００５８】
プロセッサ601および606は、上述の様々な態様の機能を含む、種々の機能を実行するためのソフトウェア命令(アプリケーション)によって構成され得る、任意のプログラマブルマイクロプロセッサ、マイクロコンピュータ、または1つもしくは複数の多重プロセッサチップであり得る。様々なデバイスにおいて、プロセッサ601および606は、特定の命令、ソフトウェア、コマンド、または他の使用法に専用である場合がある。たとえば、あるプロセッサはワイヤレス通信機能専用である場合があり、あるプロセッサは他のアプリケーションを実行すること専用である場合がある。通常、ソフトウェアアプリケーションは、それらがアクセスされ、プロセッサ601および606にロードされる前に、内部メモリ602内に記憶され得る。プロセッサ601および606は、アプリケーションソフトウェア命令を記憶するのに十分な内部メモリを含み得る。多くのデバイスでは、内部メモリは、揮発性メモリ、もしくはフラッシュメモリなどの不揮発性メモリ、または両方の混合であり得る。本明細書では、メモリへの一般的な言及は、様々なデバイスに差し込まれる内部メモリまたはリムーバブルメモリと、プロセッサ601および606内のメモリとを含む、プロセッサ601および606によってアクセス可能なメモリを指す。
【００５９】
上記の方法の説明およびプロセスフロー図は、単に説明のための例として提供され、様々な態様のステップが提示された順序で実行されなければならないことを要求または意味するものではない。当業者によって諒解されるように、上記の態様におけるステップの順序は、いかなる順序でも実行され得る。「その後」、「次いで」、「次に」などの単語は、ステップの順序を限定するものではなく、これらの単語は、単に、方法の説明を通して読者を案内するために使用される。さらに、たとえば、冠詞「a」、「an」または「the」を使用する単数形での請求要素への任意の言及は、その要素を単数に限定するものとして解釈されるべきではない。
【００６０】
本明細書で開示された態様に関して記載された様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装される場合がある。ハードウェアおよびソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップが、全般にそれらの機能に関して上述されている。そのような機能がハードウェアとして実装されるか、またはソフトウェアとして実装されるかは、具体的な適用例およびシステム全体に課される設計制約に依存する。当業者は、記載された機能を具体的な適用例ごとに様々な方法で実装することができるが、そのような実装の決定は、本発明の範囲からの逸脱を生じるものと解釈されるべきではない。
【００６１】
本明細書において開示した態様に関して説明する様々な例示的な論理、論理ブロック、モジュール、および回路を実装するために使用されるハードウェアは、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別のハードウェア構成要素、または、本明細書で説明する機能を実施するように設計されたそれらの任意の組合せで、実装または実施される場合がある。汎用プロセッサは、マイクロプロセッサであり得るが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであり得る。プロセッサを、コンピューティングデバイスの組合せ、たとえばDSPおよびマイクロプロセッサの組合せ、複数のマイクロプロセッサ、DSPコアに関連する1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成として実装する場合もある。あるいは、いくつかのステップまたは方法は、所与の機能に固有の回路網によって実行され得る。
【００６２】
1つまたは複数の例示的な態様では、説明した機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せで実施され得る。ソフトウェアに実装される場合、機能は、1つもしくは複数の命令もしくはコードとして、コンピュータ可読媒体上に記憶されるか、または、コンピュータ可読媒体を介して送信される場合がある。本明細書において開示した方法またはアルゴリズムの動作は、非一時的プロセッサ可読記憶媒体またはコンピュータ可読記憶媒体上に記憶され得るプロセッサ実行可能ソフトウェアモジュール(または、プロセッサ実行可能命令もしくはプロセッサ実行可能ソフトウェア命令)において具現化され得る。非一時的プロセッサ可読記憶媒体は、コンピュータまたはプロセッサによってアクセスされ得る任意の使用可能な媒体であり得る。限定ではなく例として、非一時的コンピュータ可読/プロセッサ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気記憶デバイス、または、命令もしくはデータ構造の形式で所望のプログラムコードを記憶するために使用されコンピュータによってアクセスされ得る任意の他の媒体を含む場合がある。本明細書において使用される、ディスク(disk)およびディスク(disc)は、コンパクトディスク(CD)、レーザーディスク(登録商標)、光ディスク、デジタル多用途ディスク(DVD)、フロッピー(登録商標)ディスクおよびブルーレイディスクを含み、この場合、ディスク(disk)は、通常、磁気的にデータを再生し、ディスク(disc)は、レーザを用いてデータを光学的に再生する。上記の組合せも、非一時的コンピュータ可読/プロセッサ可読媒体の範囲に含まれるべきである。加えて、方法またはアルゴリズムの動作は、コンピュータプログラム製品に内蔵される場合がある、有形の非一時的機械可読媒体および/またはコンピュータ可読媒体上のコードおよび/または命令の1つもしくは任意の組合せ、またはそのセットとして存在する場合がある。
【００６３】
開示した態様の上記の説明は、任意の当業者が本発明を作製または使用することができるように提供される。これらの態様に対する様々な修正は、当業者には容易に明らかであり、本明細書で定義された一般的な定義は、本発明の要旨または範囲から逸脱することなく、他の態様に適用され得る。したがって、本発明は、本明細書に示されている態様に限定されることを意図しておらず、以下の特許請求の範囲、ならびに、本明細書で開示されている原理および新規な特徴と一致する最も広い範囲を与えられるべきである。
【符号の説明】
【００６４】
600  スマートフォンモバイルコンピューティングデバイス
601  プロセッサ
602  内部メモリ
603  ディスプレイ
604  アンテナ
605  長距離ワイヤレス信号送受信機
606  デジタル信号プロセッサ(DSP)
608  メニュー選択ボタン、ロッカースイッチ
610  加速度計
611  ジャイロスコープ
612  マイクロフォン
613  カメラ
614  GPS受信機チップ
624  短距離無線送受信機
654  スピーカ
【図１】
2016531366.tif 000003
【図２】
2016531366.tif 000004
【図３】
2016531366.tif 000005
【図４】
2016531366.tif 000006
【図５】
2016531366.tif 000007
【図６】
2016531366.tif 000008
【手続補正書】
【提出日】平成27年7月27日(2015.7.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力コードの一部分を補助プロセッサに好適であると自動的に判定する際に、コンピューティングデバイスが前記補助プロセッサ上で実行するために前記一部分を第1のプロセッサからオフロードするための方法であって、
有向非巡回グラフ(DAG)を含む、前記入力コードのグラフベースの中間表現を生成するステップと、
前記生成されたグラフベースの中間表現内の各ノードまたはノードの組合せを、前記補助プロセッサに関連付けられた、既定の文法内の1つまたは複数のパターンと比較するステップであって、各パターンは、DAGパターンであり、前記補助プロセッサ上でのその実行に関連するコストメトリックに関連付けられる、ステップと、
各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を部分的にカバーするパターンのセットを特定するステップと、
パターンの前記特定されたセットの他の組合せの累積効果よりも良く、前記補助プロセッサの既定のしきい値内である、累積効果を有するパターンの前記特定されたセットのパターンの組合せに関連付けられた前記入力コードのセグメントを前記第1のプロセッサから前記補助プロセッサにオフロードするステップであって、前記既定の文法内の前記1つまたは複数のパターンが前記補助プロセッサに好適であると知られている、ステップと
を含む、方法。
【請求項２】
各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較するステップが、各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較するステップを含む、請求項1に記載の方法。
【請求項３】
前記コンピューティングデバイスが、システムオンチップを含むデバイスである、請求項1に記載の方法。
【請求項４】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項1に記載の方法。
【請求項５】
最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項1に記載の方法。
【請求項６】
各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成するステップをさらに含む、請求項1に記載の方法。
【請求項７】
有向非巡回グラフ(DAG)である、入力コードのグラフベースの中間表現を生成するための手段と、
前記生成されたグラフベースの中間表現内の各ノードまたはノードの組合せを、補助プロセッサに関連付けられた、既定の文法内の1つまたは複数のパターンと比較するための手段であって、各パターンは、DAGパターンであり、前記補助プロセッサ上でのその実行に関連するコストメトリックに関連付けられる、手段と、
各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を完全にカバーするパターンのセットを特定するための手段と、
パターンの前記特定されたセットの他の組合せの累積効果よりも良く、前記補助プロセッサの既定のしきい値内である、累積効果を有するパターンの前記特定されたセットのパターンの組合せに関連付けられた前記入力コードのセグメントを第1のプロセッサから前記補助プロセッサにオフロードするための手段であって、前記既定の文法内の前記1つまたは複数のパターンが前記補助プロセッサに好適であると知られている、手段と
を含む、コンピューティングデバイス。
【請求項８】
各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較するための手段が、各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較するための手段を含む、請求項7に記載のコンピューティングデバイス。
【請求項９】
前記コンピューティングデバイスがシステムオンチップを含む、請求項7に記載のコンピューティングデバイス。
【請求項１０】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項7に記載のコンピューティングデバイス。
【請求項１１】
最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項7に記載のコンピューティングデバイス。
【請求項１２】
各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成するための手段をさらに含む、請求項7に記載のコンピューティングデバイス。
【請求項１３】
メモリと、
第1のプロセッサと、
補助プロセッサと
を含む、コンピューティングデバイスであって、
前記第1のプロセッサは、前記メモリおよび前記補助プロセッサに結合され、演算を実行するためにプロセッサ実行可能命令とともに構成され、前記演算が、
有向非巡回グラフ(DAG)を含む、入力コードのグラフベースの中間表現を生成することと、
前記生成されたグラフベースの中間表現内の各ノードまたはノードの組合せを、前記補助プロセッサに関連付けられた、既定の文法内の1つまたは複数のパターンと比較することであって、各パターンは、DAGパターンであり、前記補助プロセッサ上でのその実行に関連するコストメトリックに関連付けられる、比較することと、
各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を部分的にカバーするパターンのセットを特定することと、
パターンの前記特定されたセットの他の組合せの累積効果よりも良く、前記補助プロセッサの既定のしきい値内である、累積効果を有するパターンの前記特定されたセットのパターンの組合せに関連付けられた前記入力コードのセグメントを前記第1のプロセッサから前記補助プロセッサにオフロードすることであって、前記既定の文法内の前記1つまたは複数のパターンが前記補助プロセッサに好適であると知られている、オフロードすることと
を含む、コンピューティングデバイス。
【請求項１４】
前記第1のプロセッサは、各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較することが、前記各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較することを含むように、演算を実行するためにプロセッサ実行可能命令とともに構成される、請求項13に記載のコンピューティングデバイス。
【請求項１５】
前記コンピューティングデバイスがシステムオンチップを含む、請求項13に記載のコンピューティングデバイス。
【請求項１６】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項13に記載のコンピューティングデバイス。
【請求項１７】
最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項13に記載のコンピューティングデバイス。
【請求項１８】
前記第1のプロセッサは、各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成することをさらに含む演算を実行するためにプロセッサ実行可能命令とともに構成される、請求項13に記載のコンピューティングデバイス。
【請求項１９】
入力コードの一部分を第1のプロセッサから補助プロセッサにオフロードするための演算をプロセッサに実行させるように構成されたプロセッサ実行可能ソフトウェア命令を記憶した非一時的プロセッサ可読記憶媒体であって、前記演算が、
有向非巡回グラフ(DAG)である、前記入力コードのグラフベースの中間表現を生成することと、
前記生成されたグラフベースの中間表現内の各ノードまたはノードの組合せを、前記補助プロセッサに関連付けられた、既定の文法内の1つまたは複数のパターンと比較することであって、各パターンは、DAGパターンであり、前記補助プロセッサ上でのその実行に関連するコストメトリックに関連付けられる、比較することと、
各ノードまたはノードの前記組合せと、前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記入力コードの前記グラフベースの中間表現を完全にカバーするパターンのセットを特定することと、
パターンの前記特定されたセットの他の組合せの累積効果よりも良く、前記補助プロセッサの既定のしきい値内である、累積効果を有するパターンの前記特定されたセットのパターンの組合せに関連付けられた前記入力コードのセグメントを前記第1のプロセッサから前記補助プロセッサにオフロードすることであって、前記既定の文法内の前記1つまたは複数のパターンが前記補助プロセッサに好適であると知られている、オフロードすることと
を含む、非一時的プロセッサ可読記憶媒体。
【請求項２０】
前記記憶されたプロセッサ実行可能ソフトウェア命令は、各ノードまたはノードの組合せを既定の文法内の1つまたは複数のパターンと比較することが、各ノードまたはノードの前記組合せをヒューリスティックテーブル内に記憶されたパターン情報と比較することを含むように、前記プロセッサに演算を実行させるように構成される、請求項19に記載の非一時的プロセッサ可読記憶媒体。
【請求項２１】
前記記憶されたプロセッサ実行可能ソフトウェア命令が、システムオンチップを含むコンピューティングデバイス上で実行されるように構成される、請求項19に記載の非一時的プロセッサ可読記憶媒体。
【請求項２２】
前記補助プロセッサが、デジタル信号プロセッサ(DSP)およびグラフィックス処理ユニット(GPU)のうちの1つである、請求項19に記載の非一時的プロセッサ可読記憶媒体。
【請求項２３】
最良の累積効果が、最低の累積コストおよび最高の累積利益のうちの1つである、請求項19に記載の非一時的プロセッサ可読記憶媒体。
【請求項２４】
前記記憶されたプロセッサ実行可能ソフトウェア命令は、各ノードまたはノードの前記組合せと前記既定の文法内の前記1つまたは複数のパターンとの前記比較に基づいて前記補助プロセッサに対して設定することができる前記入力コードのセグメントを示す、開発者に提示するための情報を生成することをさらに含む演算を前記プロセッサに実行させるように構成される、請求項19に記載の非一時的プロセッサ可読記憶媒体。
【国際調査報告】
2016531366.tif 000009
2016531366.tif 000010
2016531366.tif 000011