(57)【要約】  様々な実施形態は、動作状態データに基づいてワークスティーリング決定を行うことによって、マルチプロセッサコンピューティングデバイスの複数の処理ユニット間で作業負荷を事前対処的にバランスさせる。実施形態の方法は、犠牲者プロセッサおよび犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得するステップと、プロセッサの各々に関する動的特性データを取得するステップと、取得されたデータに基づいて、プロセッサの各々のための優先度値を計算するステップと、計算された優先度値に基づいて、犠牲者プロセッサに割り当てられたいくつかの作業項目を勝利作業準備完了プロセッサに転送するステップとを含む。いくつかの実施形態では、方法は、共有データ構造のための確率的ロックの制御を獲得するステップと、勝利作業準備完了プロセッサに転送される作業項目の数を示すために、共有データ構造を更新するステップとを含んでもよい。
2018531450.tif 000002
【特許請求の範囲】
【請求項１】
動作状態データに基づいてワークスティーリング決定を行うことによって複数の処理ユニット間で作業負荷を事前対処的にバランスさせる、マルチプロセッサコンピューティングデバイスのプロセッサによって実施される方法であって、
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得するステップと、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得するステップと、
前記取得されたデータに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算するステップと、
前記計算された優先度値に基づいて、前記犠牲者プロセッサに割り当てられたいくつかの作業項目を勝利作業準備完了プロセッサに転送するステップと
を備える方法。
【請求項２】
前記作業準備完了プロセッサが、それぞれの割り当てられた作業項目を完了する前記作業準備完了プロセッサに応答して、前記犠牲者プロセッサから前記作業項目を盗む準備ができる、請求項1に記載の方法。
【請求項３】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データが、使用される技術、前記マルチプロセッサコンピューティングデバイスのトポロジ内の位置、および製造者データを示すいずれかのデータを含む、請求項1に記載の方法。
【請求項４】
前記静的特性データが、前記マルチプロセッサコンピューティングデバイスの製造時に、前記マルチプロセッサコンピューティングデバイスの各起動時に、定期的に、またはそれらの任意の組合せにおいて取得される、請求項1に記載の方法。
【請求項５】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のローカル測定値を含む、請求項1に記載の方法。
【請求項６】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、温度、電力消費、および周波数に関連する値を含む、請求項1に記載の方法。
【請求項７】
前記取得されたデータに基づいて前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための前記優先度値を計算するステップが、以下の式、
Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi
を使用して前記優先度値を計算するステップを備え、
iが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのためのインデックスを表し、Piが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのための前記インデックスに関連付けられた処理ユニットのための計算された優先度値を表し、αiが、温度に関するグローバル係数を表し、fiが、前記処理ユニットに関する前記温度についてのローカル係数を表し、Tempiが、前記処理ユニットに関するローカル温度測定値に対する式を表し、βiが、電力消費に関するグローバル係数を表し、giが、前記処理ユニットに関する前記電力消費についてのローカル係数を表し、Poweriが、前記処理ユニットに関するローカル電力消費測定値に対する式を表し、γiが、周波数に関するグローバル係数を表し、hiが、前記処理ユニットの前記周波数に関するローカル係数を表し、Freqiが、前記処理ユニットに関するローカル周波数測定値に対する式を表す、請求項1に記載の方法。
【請求項８】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データを取得するステップが、前記温度に関するグローバル係数と、前記電力消費に関するグローバル係数と、前記周波数に関するグローバル係数とを取得するステップを備える、請求項7に記載の方法。
【請求項９】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得するステップが、前記処理ユニットに関する前記温度についての前記ローカル係数と、前記処理ユニットに関する前記ローカル温度測定値と、前記処理ユニットに関する前記電力消費についての前記ローカル係数と、前記処理ユニットに関する前記ローカル電力消費測定値と、前記処理ユニットに関する前記周波数についての前記ローカル係数と、前記処理ユニットに関する前記ローカル周波数測定値とを取得するステップを備える、請求項7に記載の方法。
【請求項１０】
前記犠牲者プロセッサおよび前記勝利作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する作業項目の数を計算するステップをさらに備える、請求項1に記載の方法。
【請求項１１】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を計算するステップが、以下の式、
Ni=K*(Pi/(Pi+Pj))
Nj=K-Ni
を使用して、転送する前記作業項目の数を計算するステップを備え、
iが、前記犠牲者プロセッサに関連する第1のタスクインデックスを表し、jが、前記勝利作業準備完了プロセッサに関連する第2のタスクインデックスを表し、Kが、盗む前に前記犠牲者プロセッサによって処理されるために残っている作業項目の総数を表し、Pjが、前記犠牲者プロセッサの計算された優先度値を表し、Piが、前記勝利作業準備完了プロセッサの前記計算された優先度値を表し、Niが、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を表し、Njが、前記犠牲者プロセッサに残る作業項目の数を表す、請求項10に記載の方法。
【請求項１２】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々が、前記複数の処理ユニット内の異なる処理ユニットに関連付けられる、請求項1に記載の方法。
【請求項１３】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々が、前記複数の処理ユニットのうちの1つにおいて実行される異なるタスクに関連付けられる、請求項1に記載の方法。
【請求項１４】
前記作業項目が、並列ループルーチンの異なる反復である、請求項1に記載の方法。
【請求項１５】
前記複数の処理ユニットが、2つ以上の第1の中央処理装置(CPU)と、グラフィックス処理ユニット(GPU)と、デジタル信号プロセッサ(DSP)とを含む、請求項1に記載の方法。
【請求項１６】
前記マルチプロセッサコンピューティングデバイスが、異種マルチコアコンピューティングデバイス、同種マルチコアコンピューティングデバイス、分散コンピューティングサーバのうちの1つである、請求項1に記載の方法。
【請求項１７】
前記勝利作業準備完了プロセッサを介して、前記勝利作業準備完了プロセッサの計算された優先度値に基づいて、共有データ構造のための確率的ロックの制御を獲得するステップと、
前記勝利作業準備完了プロセッサを介して、前記確率的ロックの制御を獲得することに応答して、前記勝利作業準備完了プロセッサに転送される作業項目の数を示すために、前記共有データ構造を更新するステップと
をさらに備える、請求項1に記載の方法。
【請求項１８】
メモリと、
複数の処理ユニットのプロセッサと
を備えるコンピューティングデバイスであって、前記プロセッサが、前記メモリに結合され、
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得することと、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得することと、
前記取得されたデータに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算することと、
前記計算された優先度値に基づいて、前記犠牲者プロセッサに割り当てられたいくつかの作業項目を勝利作業準備完了プロセッサに転送することと
を備える動作を実行するようにプロセッサ実行可能命令を用いて構成される、コンピューティングデバイス。
【請求項１９】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データが、使用される技術、前記コンピューティングデバイスのトポロジ内の位置、および製造者データを示すいずれかのデータを含む、請求項18に記載のコンピューティングデバイス。
【請求項２０】
前記静的特性データが、前記コンピューティングデバイスの製造時に、前記コンピューティングデバイスの各起動時に、定期的に、またはそれらの任意の組合せにおいて取得される、請求項18に記載のコンピューティングデバイス。
【請求項２１】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のローカル測定値を含む、請求項18に記載のコンピューティングデバイス。
【請求項２２】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、温度、電力消費、および周波数に関連する値を含む、請求項18に記載のコンピューティングデバイス。
【請求項２３】
前記取得されたデータに基づいて前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための前記優先度値を計算することが、以下の式、
Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi
を使用して前記優先度値を計算することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成され、
iが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのためのインデックスを表し、Piが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのための前記インデックスに関連付けられた処理ユニットのための計算された優先度値を表し、αiが、温度に関するグローバル係数を表し、fiが、前記処理ユニットに関する前記温度についてのローカル係数を表し、Tempiが、前記処理ユニットに関するローカル温度測定値に対する式を表し、βiが、電力消費に関するグローバル係数を表し、giが、前記処理ユニットに関する前記電力消費についてのローカル係数を表し、Poweriが、前記処理ユニットに関するローカル電力消費測定値に対する式を表し、γiが、周波数に関するグローバル係数を表し、hiが、前記処理ユニットの前記周波数に関するローカル係数を表し、Freqiが、前記処理ユニットに関するローカル周波数測定値に対する式を表す、請求項18に記載のコンピューティングデバイス。
【請求項２４】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データを取得することが、前記温度に関するグローバル係数と、前記電力消費に関するグローバル係数と、前記周波数に関するグローバル係数とを取得することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項23に記載のコンピューティングデバイス。
【請求項２５】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得することが、前記処理ユニットに関する前記温度についての前記ローカル係数と、前記処理ユニットに関する前記ローカル温度測定値と、前記処理ユニットに関する前記電力消費についての前記ローカル係数と、前記処理ユニットに関する前記ローカル電力消費測定値と、前記処理ユニットに関する前記周波数についての前記ローカル係数と、前記処理ユニットに関する前記ローカル周波数測定値とを取得することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項23に記載のコンピューティングデバイス。
【請求項２６】
前記プロセッサが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する作業項目の数を計算することをさらに備える動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項18に記載のコンピューティングデバイス。
【請求項２７】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を計算することが、以下の式、
Ni=K*(Pi/(Pi+Pj))
Nj=K-Ni
を使用して、転送する前記作業項目の数を計算することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成され、
iが、前記犠牲者プロセッサに関連する第1のタスクインデックスを表し、jが、前記勝利作業準備完了プロセッサに関連する第2のタスクインデックスを表し、Kが、盗む前に前記犠牲者プロセッサによって処理されるために残っている作業項目の総数を表し、Pjが、前記犠牲者プロセッサの計算された優先度値を表し、Piが、前記勝利作業準備完了プロセッサの前記計算された優先度値を表し、Niが、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を表し、Njが、前記犠牲者プロセッサに残る作業項目の数を表す、請求項26に記載のコンピューティングデバイス。
【請求項２８】
前記プロセッサが、
前記勝利作業準備完了プロセッサを介して、前記勝利作業準備完了プロセッサの計算された優先度値に基づいて、共有データ構造のための確率的ロックの制御を獲得することと、
前記勝利作業準備完了プロセッサを介して、前記確率的ロックの制御を獲得することに応答して、前記勝利作業準備完了プロセッサに転送される作業項目の数を示すために、前記共有データ構造を更新することと
をさらに備える動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項18に記載のコンピューティングデバイス。
【請求項２９】
コンピューティングデバイスの複数の処理ユニットのプロセッサに、
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得することと、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得することと、
前記取得されたデータに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算することと、
前記計算された優先度値に基づいて、前記犠牲者プロセッサに割り当てられたいくつかの作業項目を勝利作業準備完了プロセッサに転送することと
を備える動作を実行させるように構成されたプロセッサ実行可能命令が記憶された非一時的プロセッサ可読媒体。
【請求項３０】
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得するための手段と、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得するための手段と、
前記取得されたデータに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算するための手段と、
前記計算された優先度値に基づいて、前記犠牲者プロセッサに割り当てられたいくつかの作業項目を勝利作業準備完了プロセッサに転送するための手段と
を備えるコンピューティングデバイス。
【発明の詳細な説明】
【背景技術】
【０００１】
データ並列処理は、複数の処理ユニットにわたる計算並列化の一形態である。データ並列処理は、分割され、複数の処理ユニットによって同時に実行され得る作業負荷を実行するためにしばしば使用される。たとえば、1000回の反復を有する並列ループルーチンを実行するために、4つの異なる処理ユニットが、各々、並列ループルーチンの250の異なる反復(または異なるサブ範囲)を実行するように構成され得る。データ並列処理の文脈では、タスクは、典型的には実行時に決定される動的ワーキングサイズを有し得る逐次計算作業の抽象を表すことができる。たとえば、プロセッサは、並列ループルーチンのサブ範囲を処理するタスクを実行することができる。場合によっては、タスクは、第1のプロセッサ上で動作するスレッドによって作成され、第2のプロセッサ上で別のスレッドを介して処理されるようにディスパッチされ得る。
【０００２】
異なるタスクは、マルチコアまたはマルチプロセッサコンピューティングデバイス(たとえば、異種システムオンチップ(SoC))の様々な処理ユニットに割り当てられ得る(またはオフロードされ得る)。典型的には、タスクベースの実行時システム(またはタスクスケジューラ)は、どの処理ユニットにタスクが割り当られ得るのかを決定する。たとえば、スケジューラは、複数の処理ユニット上で同時実行タスクのセットを起動することができ、各ユニットは、並列ループルーチンのためのデータに対する動作を異なって実行することができる。
【０００３】
マルチプロセッサ(またはマルチコア)システムは、しばしば、応答性で高性能なソフトウェアを提供するために、データ並列化技法を実装するように構成される。たとえば、データ並列処理能力について、マルチコアデバイスは、一般に、負荷分散を達成するために、異なる処理ユニット上でいくつかの動的タスクを起動する。並列作業負荷は、様々な処理ユニット間でアンバランスになることがある。たとえば、複数の処理ユニットは、最初に並列ループルーチンの等しいサブ範囲を得ることができるが、実行時間の不均衡が生じることがある。作業負荷の不均衡は、作業項目あたりの作業量が一定でない(たとえば、いくつかの作業項目が他の作業項目よりも少ない作業を必要とし得る、など)、異種処理ユニットの能力が異なることがある(たとえば、big.LITTLE CPUコア、CPU対GPUなど)、特に、(一般にそうであるように)放熱が均一でない場合、温度上昇がいくつかの処理ユニットにおける周波数を他の処理ユニットよりも抑圧することがある、および、他の負荷がいくつかのプロセッサをより遅れさせる(たとえば、他のアプリケーションからの負荷、システム割込みのサービス、および/またはOSスケジューリングの影響など)などの多くの理由のために発生することがある。
【０００４】
データ並列処理を行いながら性能を改善するために、マルチプロセッサシステムは、タスクまたは処理ユニットが他のタスクまたは処理ユニットに最初に割り当てられた作業項目を便宜的に受け取り実行するように構成され得るワークスティーリング(work-stealing)技法を用いることができる。たとえば、第1の処理ユニットまたはタスクが共有作業負荷(たとえば、並列ループルーチン)の割り当てられたサブ範囲を完了すると、第1の処理ユニットは、共有作業負荷のそれぞれの割当てを処理するのに依然として忙しい他の処理ユニット/タスクから作業の追加のサブ範囲を盗むことができる。負荷の不均衡がしばしば発生する可能性があるので、ワークスティーリング動作は、システム処理リソースの利用を改善し、並列作業を完了する時間を短縮する動的負荷分散を可能にし得る。
【発明の概要】
【課題を解決するための手段】
【０００５】
様々な実施形態は、動作状態データに基づいてワークスティーリング決定を行うことによって複数の処理ユニット間で作業負荷を事前対処的にバランスさせる、マルチプロセッサコンピューティングデバイスのための方法、デバイス、システム、および非一時的プロセス可読記憶媒体を提供する。マルチプロセッサコンピューティングデバイスのプロセッサによって実行される実施形態の方法は、犠牲者(victim)プロセッサおよび犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了(work-ready)プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得する動作と、犠牲者プロセッサおよび作業準備完了プロセッサの各々に関連する動的特性データを取得する動作と、取得されたデータに基づいて、犠牲者プロセッサおよび作業準備完了プロセッサの各々のための優先度値を計算する動作と、計算された優先度値に基づいて、犠牲者プロセッサに割り当てられたいくつかの作業項目を勝利作業準備完了プロセッサに転送する動作とを含んでもよい。
【０００６】
いくつかの実施形態では、作業準備完了プロセッサは、それぞれの割り当てられた作業項目を完了する作業準備完了プロセッサに応答して、犠牲者プロセッサから作業項目を盗む準備ができていてもよい。いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々に関連する静的特性データは、使用される技術、マルチプロセッサコンピューティングデバイスのトポロジ内の位置、および製造者データを示すいずれかのデータを含んでもよい。いくつかの実施形態では、静的特性データは、マルチプロセッサコンピューティングデバイスの製造時に、マルチプロセッサコンピューティングデバイスの各起動時に、定期的に、またはそれらの任意の組合せにおいて取得されてもよい。いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々に関連する動的特性データは、犠牲者プロセッサおよび作業準備完了プロセッサの各々のローカル測定値を含んでもよい。いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々に関連する動的特性データは、温度、電力消費、および周波数に関連する値を含んでもよい。
【０００７】
いくつかの実施形態では、取得したデータに基づいて犠牲者プロセッサおよび作業準備完了プロセッサの各々のための優先度値を計算することは、以下の式を使用して優先度値を計算することを含んでもよい。
Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi
ここで、iは、犠牲者プロセッサおよび作業準備完了プロセッサのうちの1つのためのインデックスを表してもよく、Piは、犠牲者プロセッサおよび作業準備完了プロセッサのうちの1つのためのインデックスに関連付けられた処理ユニットのための計算された優先度値を表してもよく、αiは、温度に関するグローバル係数を表してもよく、fiは、処理ユニットに関する温度についてのローカル係数を表してもよく、Tempiは、処理ユニットに関するローカル温度測定値に対する式を表してもよく、βiは、電力消費に関するグローバル係数を表してもよく、giは、処理ユニットに関する電力消費についてのローカル係数を表してもよく、Poweriは、処理ユニットに関するローカル電力消費測定値に対する式を表してもよく、γiは、周波数に関するグローバル係数を表してもよく、hiは、処理ユニットの周波数に関するローカル係数を表してもよく、Freqiは、処理ユニットに関するローカル周波数測定値に対する式を表してもよい。いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々に関連する静的特性データを取得することは、温度に関するグローバル係数と、電力消費に関するグローバル係数と、周波数に関するグローバル係数とを取得することを含んでもよい。いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々に関連する動的特性データを取得することは、処理ユニットに関する温度についてのローカル係数と、処理ユニットに関するローカル温度測定値と、処理ユニットに関する電力消費についてのローカル係数と、処理ユニットに関するローカル電力消費測定値と、処理ユニットに関する周波数についてのローカル係数と、処理ユニットに関するローカル周波数測定値とを取得することを含んでもよい。
【０００８】
いくつかの実施形態では、方法は、犠牲者プロセッサおよび作業準備完了プロセッサの計算された優先度値に基づいて、勝利作業準備完了プロセッサに転送する作業項目の数を計算することをさらに含んでもよい。
【０００９】
いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの計算された優先度値に基づいて、勝利作業準備完了プロセッサに転送する作業項目の数を計算することは、以下の式を使用して、転送する作業項目の数を計算することを含んでもよい。
Ni=K*(Pi/(Pi+Pj))
Nj=K-Ni
ここで、iは、犠牲者プロセッサに関連する第1のタスクインデックスを表してもよく、jは、勝利作業準備完了プロセッサに関連する第2のタスクインデックスを表してもよく、Kは、盗む前に犠牲者プロセッサによって処理されるために残っている作業項目の総数を表してもよく、Pjは、犠牲者プロセッサの計算された優先度値を表してもよく、Piは、勝利作業準備完了プロセッサの計算された優先度値を表してもよく、Niは、勝利作業準備完了プロセッサに転送する作業項目の数を表してもよく、Njは、犠牲者プロセッサに残る作業項目の数を表してもよい。
【００１０】
いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々は、複数の処理ユニット内の異なる処理ユニットに関連付けられてもよい。いくつかの実施形態では、犠牲者プロセッサおよび作業準備完了プロセッサの各々は、複数の処理ユニットのうちの1つにおいて実行される異なるタスクに関連付けられてもよい。いくつかの実施形態では、作業項目は並列ループルーチンの異なる反復であってもよい。いくつかの実施形態では、複数の処理ユニットは、2つ以上の第1の中央処理装置(CPU)と、グラフィックス処理ユニット(GPU)と、デジタル信号プロセッサ(DSP)とを含んでもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、異種マルチコアコンピューティングデバイス、同種マルチコアコンピューティングデバイス、または分散コンピューティングサーバのうちの1つであってもよい。
【００１１】
いくつかの実施形態では、方法は、勝利作業準備完了プロセッサを介して、勝利作業準備完了プロセッサの計算された優先度値に基づいて、共有データ構造のための確率的ロックの制御を獲得することと、勝利作業準備完了プロセッサを介して、確率的ロックの制御を獲得することに応答して、勝利作業準備完了プロセッサに転送される作業項目の数を示すために、共有データ構造を更新することとをさらに含んでもよい。
【００１２】
さらなる実施形態は、上記で説明した方法の動作を実行するためのプロセッサ実行可能命令を用いて構成されたコンピューティングデバイスを含む。さらなる実施形態は、コンピューティングデバイスに上記で説明した方法の動作を実行させるように構成されたプロセッサ実行可能命令が記憶された非一時的プロセッサ可読媒体を含む。
【００１３】
本明細書に組み込まれ、本明細書の一部を構成する添付図面は、例示的な実施形態を示し、上記で与えた一般的な説明および以下に与える詳細な説明とともに、特許請求の範囲の特徴を説明する役割を果たす。
【図面の簡単な説明】
【００１４】
【図１】いくつかの実施形態での使用に適した例示的な異種マルチプロセッサコンピューティングデバイス(たとえば、異種システムオンチップ(SoC))のタスクキューおよび処理ユニットを示す構成要素ブロック図である。
【図２Ａ】いくつかの実施形態によるマルチプロセッサコンピューティングデバイスによる例示的なワークスティーリング動作を示す構成要素ブロック図である。
【図２Ｂ】いくつかの実施形態によるマルチプロセッサコンピューティングデバイスによる例示的なワークスティーリング動作を示す構成要素ブロック図である。
【図２Ｃ】いくつかの実施形態によるマルチプロセッサコンピューティングデバイスによる例示的なワークスティーリング動作を示す構成要素ブロック図である。
【図２Ｄ】いくつかの実施形態によるマルチプロセッサコンピューティングデバイスによる例示的なワークスティーリング動作を示す構成要素ブロック図である。
【図３】いくつかの実施形態による、共有メモリとワークスティーリングデータ構造とを有するマルチプロセッサコンピューティングデバイスによる例示的なワークスティーリング動作を示す構成要素ブロック図である。
【図４Ａ】動作状態データに基づいてワークスティーリング決定を行うことによって、複数の処理ユニット間で作業負荷を事前対処的にバランスさせるためにマルチプロセッサコンピューティングデバイスによって実行される実施形態の方法を示すプロセスフロー図である。
【図４Ｂ】動作状態データに基づいてワークスティーリング決定を行うことによって、複数の処理ユニット間で作業負荷を事前対処的にバランスさせるためにマルチプロセッサコンピューティングデバイスによって実行される実施形態の方法を示すプロセスフロー図である。
【図５】いくつかの実施形態での使用に適したコンピューティングデバイスの構成要素ブロック図である。
【発明を実施するための形態】
【００１５】
様々な実施形態について、添付図面を参照して詳細に説明する。可能な限り、同じ参照番号は、図面全体にわたって同じまたは同様の部分を指すために使用される。特定の例および実装形態になされる参照は、例示的な目的のためであり、実施形態の範囲および特許請求の範囲を限定するものではない。
【００１６】
「例示的」という語は、本明細書では、「例、事例、または例示として役立つ」ことを意味するために使用される。本明細書で「例示的」として記載されている任意の実装形態は、必ずしも他の実装形態よりも好ましいまたは有利であると解釈されるべきではない。
【００１７】
「コンピューティングデバイス」という用語は、本明細書では、少なくともマルチコアプロセッサを備える電子デバイスを指すために使用される。コンピューティングデバイスの例としては、モバイルデバイス(たとえば、セルラー電話、ウェアラブルデバイス、スマートフォン、ウェブパッド、タブレットコンピュータ、インターネット対応セルラー電話、Wi-Fi(登録商標)対応電子デバイス、携帯情報端末(PDA)、ラップトップコンピュータなど)、パーソナルコンピュータ、およびサーバコンピューティングデバイスがあり得る。様々な実施形態では、コンピューティングデバイスは、様々なメモリおよび/またはデータストレージ、ならびに、ワイドエリアネットワーク(WAN)通信(たとえば、セルラーネットワーク接続など)および/またはローカルエリアネットワーク(LAN)接続(たとえば、Wi-Fi(登録商標)ルータなどを介するインターネットへの有線/ワイヤレス接続)を確立するように構成されたネットワークトランシーバおよびアンテナなどのネットワーキング能力によって構成され得る。
【００１８】
「マルチプロセッサコンピューティングデバイス」および「マルチコアコンピューティングデバイス」という用語は、本明細書では、2つ以上の処理ユニットで構成されたコンピューティングデバイスを指すために使用される。マルチプロセッサコンピューティングデバイスは、2つ以上の処理ユニットを使用して様々な演算(たとえば、ルーチン、関数、タスク、計算、命令セットなど)を実行してもよい。「同種マルチプロセッサコンピューティングデバイス」は、作業負荷を実行するように各々が構成された複数の同じタイプの処理ユニットを有するマルチプロセッサコンピューティングデバイス(たとえば、システムオンチップ(SoC))であってもよい。「異種マルチプロセッサコンピューティングデバイス」は、特殊なおよび/または汎用の作業負荷を実行するように各々が構成され得る異なるタイプの処理ユニットを有するマルチプロセッサコンピューティングデバイス(たとえば、異種システムオンチップ(SoC))であってもよい。マルチプロセッサコンピューティングデバイスの処理ユニットは、様々なプロセッサデバイス、コア、複数のコアなどを含んでもよい。たとえば、異種マルチプロセッサコンピューティングデバイスの処理ユニットは、アプリケーションプロセッサ(たとえば、中央処理装置(CPU))、ならびに/または、グラフィックス処理ユニット(GPU)およびデジタル信号プロセッサ(DSP)などの特殊処理デバイスを含んでもよく、そのいずれも1つまたは複数の内部コアを含んでもよい。別の例として、異種マルチプロセッサコンピューティングデバイスは、大型コアおよび小型コアの混合クラスタ(ARM big.LITTLEアーキテクチャなど)と、様々な異種システム/デバイス(たとえば、GPU、DSPなど)とを含んでもよい。
【００１９】
「作業準備完了プロセッサ」という用語は、本明細書では一般的に、ワークスティーリングポリシーによって1つまたは複数の作業負荷を受け取る準備ができている処理ユニットおよび/または処理ユニット上で実行されるタスクを指すために使用される。たとえば、「作業準備完了プロセッサ」は、他の処理ユニットまたは他の処理ユニット上で実行されるタスクから個々の作業項目を受け取ることができる処理ユニットであってもよい。同様に、「犠牲者プロセッサ」という用語は、本明細書では一般に、1つまたは複数の作業準備完了プロセッサに転送され得る1つまたは複数の作業負荷(たとえば、個々の作業項目、タスクなど)を有する処理ユニットおよび/または処理ユニット上で実行されるタスクを指すために使用される。「作業準備完了タスク」という用語は、本明細書では、処理ユニット上で実行されるタスクである作業準備完了プロセッサを指すために使用される。「作業準備完了処理ユニット」という用語は、処理ユニットである作業準備完了プロセッサを指す。「犠牲者タスク」という用語は、本明細書では、処理ユニット上で実行されるタスクである犠牲者プロセッサを指すために使用される。「犠牲者処理ユニット」という用語は、処理ユニットである犠牲者プロセッサを指す。しかしながら、そのような用語は、任意の実施形態または特許請求の範囲を特定のタイプの作業準備完了プロセッサまたは犠牲者プロセッサに限定することを意図していない。
【００２０】
一般に、ワークスティーリングは、並列処理コンピューティングシステムの性質に応じて、様々な方法で実施され得る。たとえば、共有メモリマルチプロセッサシステムは、処理ユニットにわたる作業のサブ分割を表すために、共有データ構造(たとえば、作業サブ範囲のツリー表現)を用いてもよい。そのようなシステムでは、スティーリングは、ロック動作またはアトミック動作を介して共有データ構造に同時にアクセスし更新するために、作業準備完了タスクを必要とすることがある。別の例として、処理ユニットは、キューが空であるときに、処理ユニットが別の処理ユニットから作業項目を盗むことができ、盗まれた作業項目を第1の処理ユニットの作業キューに追加することができるように、関連する作業キューを利用してもよい。同様に、別の処理ユニットは、第1の処理ユニットの作業キューから作業項目を盗んでもよい。従来のワークスティーリング方式は、1つの処理ユニットが犠牲者処理ユニットから均等に分割された範囲の作業負荷を共有する(または盗む)ことを単に可能にするなど、しばしばむしろ単純化されている。
【００２１】
従来、ワークスティーリングは、有益であるとみなされてきた。しかしながら、多くの状況において、従来のワークスティーリングは、厳しい電力制約および/または熱制約の下で、コンピューティングデバイスに対して逆効果で最適ではない結果をもたらす可能性がある。たとえば、第1のタスクが、作業を受け入れる(または盗む)準備ができているが、既に熱的限界に近いプロセッサ上で実行している場合、多すぎる作業(たとえば、並列ループタスクの多すぎる反復)を盗むことは、共有作業負荷の全体的な性能に役立たたない可能性がある。いくつかの従来のワークスティーリング技法は、コンピューティングデバイスの近い将来の状態への影響を考慮することなく、即時の状態のみを見る「反応的」手法を用いることがある。たとえば、従来のアドホック電力管理/サーマルスロットリングは、マルチプロセッサシステムにおける熱問題を軽減するために反応的に使用され得る。さらに、いくつかの従来のワークスティーリング技法は、作業項目を作業準備完了プロセッサ(たとえば、盗むことを要求するか、または盗む準備ができている第1の処理ユニット)に与えるために、浅い「先着順(first-come, first-serve)」方式をしばしば用いる。他の技法は、1つの作業準備完了プロセッサのみが何らかの作業を引き継ぐことに成功することができるように、競合する作業準備完了プロセッサ間のデータ競合を解決するために、アトミック動作を使用することがある。
【００２２】
そのような従来のワークスティーリング技法は、異なる電力を大量消費する処理ユニットに対してスケジュールされた動的タスクが、しばしば異なる電力消費状態および熱状態に遭遇することを認識することができず、そのことは、プロセッサ間で作業を転送することによって達成される利益に影響を及ぼす可能性がある。たとえば、従来の電力管理技法は、電力状況および熱状況の実行時評価と、オペレーティングシステム/アーキテクチャにおいて集中的に収集されたデータとの間の情報ギャップを有する可能性があり、並列スケジューリング状況において優先度付けおよび負荷分散を最適ではなくする。
【００２３】
様々な実施形態は、マルチプロセッサコンピューティングデバイス(たとえば、異種システムなど)におけるデータ並列化および負荷分散を改善するためにタスクベースの実行時システムからのデータを使用するための方法、デバイス、システム、および非一時的プロセス可読記憶媒体を提供する。一般に、マルチプロセッサコンピューティングデバイスは、タスクを実行する異なる処理ユニットの動作状態データを識別することができる。動作状態は、処理ユニットに関する静的デバイス情報および/または最新の測定値(たとえば、温度、周波数、電力消費)を含んでもよい。マルチプロセッサコンピューティングデバイスはまた、処理ユニットの温度、周波数、および/または電力消費レベルなどを示す係数などの、処理ユニットの動作状況に関連する他の情報を維持または他の方法で計算してもよい。様々な動作状態データを用いて、マルチプロセッサコンピューティングデバイスは、包括的なワークスティーリング決定を可能にするために使用され得る優先度値を計算してもよい。たとえば、作業準備完了プロセッサが犠牲者プロセッサから作業項目を受け取るために使用可能であるとき、マルチプロセッサコンピューティングデバイスは、作業項目を再分配する最も適切な方法を決定するために、様々なタスクの計算された優先度を使用してもよい。少なくとも現在の電力消費状況および熱状況に基づいて作業を割り当てることによって、マルチプロセッサコンピューティングデバイスは、データ並列処理における動的タスクのサイズを調整することができ、電力消費問題およびホットスポット問題を事前対処的に緩和することができる。
【００２４】
様々な実施形態では、マルチプロセッサコンピューティングデバイスは、様々なタイプの測定データまたはサンプルデータを使用して、各処理ユニット(および/または関連するタスク)のための優先度値を計算してもよい。処理ユニット間の相対的な優先度を比較または作成するために、マルチプロセッサコンピューティングデバイスは、各処理ユニットに固有の動作状態データ(すなわち、ローカルデータ)、ならびに、すべての処理ユニットに適用可能な情報(たとえば、グローバルデータ)を利用してもよい。言い換えれば、マルチプロセッサコンピューティングデバイスは、所与の時間における優先度を計算するために、すべての処理ユニットの状態のグローバルな認識を利用してもよい。
【００２５】
様々な実施形態では、マルチプロセッサコンピューティングデバイスは、タスクを優先度付けするために使用され得る動的にサンプリングされたデータを利用してもよい。たとえば、タスクを実行する各処理ユニットは、現在の熱出力、電力使用(または電力消費率)、および/または動作周波数を示す測定データを実行時システム(またはスケジューラ)に定期的に提供してもよい。そのようなデータは、各処理ユニット(または関連するタスク)のための電力プロファイル内に記憶されてもよい。
【００２６】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、特性を確立するために、または動作状態データを処理ユニットおよび/もしくはタスクと他の方法で関連付けるために、タスクが処理ユニット上で実行を開始したとき、状態問い合わせ文を使用してもよい。そのような状態問い合わせ文(たとえば、APIコール)を実行することは、処理ユニットに様々なローカル特性(たとえば、周波数、漏れ電流、または有効電力)のデータを返させることができる。たとえば、タスクがDSPにディスパッチされ、並列ループルーチン(または作業負荷)の作業項目を実行する準備ができているとき、マルチプロセッサコンピューティングデバイスは、その後の優先度評価に使用するための電力消費、周波数、および熱の動作状態データをタスクにタグ付けするために、状態問い合わせ文を使用してもよい。
【００２７】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、優先度値を計算し、したがって、犠牲者プロセッサから作業項目を受け取る作業準備完了プロセッサを識別するために、決定論的手法を使用してもよい。具体的には、マルチプロセッサコンピューティングデバイスは、異なるタスク特性を強調する(たとえば、より低い漏れ電力を有する、またはバッテリー寿命を最大化するためにより低い有効電力を有するタスクを優先するなど)方式など、様々な決定論的優先度式を使用してもよい。そのような決定論的手法は、通信オーバーヘッドを低減することができ、システムの他の動作状態と作業効率を最良にバランスさせる作業準備完了プロセッサを識別することによって、ローカル電力状況/熱状況をバランスさせることができる。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、以下の決定論的式を使用して、作業項目を盗むための各個別の処理ユニットのための優先度値を計算してもよい。
Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi    式1
式1において、iは、動的タスクを実行するように構成された処理ユニットのアイデンティティ(またはインデックス)を表し、Piは、(他の処理ユニットの盗難優先度と比較して)処理ユニットの全体的な盗難優先度を表し、αiは、温度に関するグローバル係数を表し、fiは、処理ユニットに関する温度(または温度値)についてのローカル係数を表し、Tempiは、処理ユニットに関するローカル温度測定値を組み込む項/式を表し、βiは、電力消費に関するグローバル係数を表し、giは、処理ユニットに関する電力消費(または電力消費値)についてのローカル係数を表し、Poweriは、処理ユニットに関するローカル電力消費測定値を組み込む項/式を表し、γiは、周波数に関するグローバル係数を表し、hiは、処理ユニットに関する周波数(または計算レート)についてのローカル係数を表し、Freqiは、処理ユニットに関するローカル周波数測定値を組み込む項/式を表す。式1を使用して生成されるより大きい数値は、より高い優先度を示してもよい。
【００２８】
式1のグローバル係数(すなわち、αi、βi、γi)は、ローカル測定値(すなわち、Tempi、Poweri、Freqi)の重要性または影響を均一にバランスさせるために、式1において寄与してもよい。加えて、各態様(たとえば、温度、電力、および周波数)について、グローバル係数は、ユニットiとユニットjとの間の区別を(たとえば、αi対αjを調整することによって)可能にし得る。具体的には、グローバル係数は、ユニット間を区別するために、処理ユニットの静的特性を組み込んでもよい。たとえば、グローバル係数は、静的プロセス技術の変動(たとえば、big.LITTLEなどのコアごとに使用される異なるプロセス、異なる漏れ、周波数など)、パッケージング、および/または熱放散に影響し得るトポロジ(たとえば、どのコアが急速に加熱または冷却し得るのか、など)を反映するように生成されてもよい。別の例として、グローバル係数は、様々な命令ミックスおよび異種性(たとえば、CPU対DSP対GPU)による温度変化率などの、処理ユニットの作業負荷固有の変動を反映するように生成されてもよい。別の例として、グローバル係数は、関連するまたは近い処理ユニットの優先度を下げるために、ビジー状態または高温になっている構成要素(たとえば、モデムなど)のデータを提供することなどによって、システム使用(またはシステムトポロジ認識)を反映するように生成されてもよい。いくつかの実施形態では、グローバル係数は、処理ユニットが特定のタイプの作業負荷(たとえば、「大きい」アーキテクチャに関する命令対「小さい」アーキテクチャに関する命令、浮動小数点演算など)に適しているかどうかを示してもよい。このようにして、グローバル係数は、並列作業負荷の特性に基づいて処理ユニット間を区別してもよい。
【００２９】
いくつかの実施形態では、グローバルスケジューラは、グローバル係数値を調整し得る比較のために、マルチプロセッサコンピューティングデバイスのすべての処理ユニットにわたって情報を収集するように構成されてもよい。さらに、グローバル係数値は、様々な処理ユニットにわたる比較を組み込んでもよい。たとえば、マルチプロセッサコンピューティングデバイスは、各プロセッサのためのαi、βi、γiを生成するために、処理ユニット間の関連因子を評価および/または組み込んでもよい。たとえば、マルチプロセッサコンピューティングデバイスは、インデックス「i」を有する非常に高温のプロセッサが、インデックス「j」を有するより低温のプロセッサと比較してより小さいαiを有する(たとえば、αi<αj)と計算してもよい。
【００３０】
いくつかの実施形態では、グローバル係数を生成するために使用されるデータは、処理ユニットから周期的フィードバックを介して取得されてもよく、および/または処理されるべき作業負荷の特性を示すコンパイル時データから取得されてもよい。いくつかの実施形態では、グローバル係数は、グローバルスケジューラ機能(たとえば、OSレベルのスレッドなど)を介するなどして、マルチプロセッサコンピューティングデバイスの起動時に、および/または定期的に、オフライン(たとえば、製造時など)で設定、調整、および/または他の方法で決定されてもよい。
【００３１】
式1のローカル係数(すなわち、fi、gi、hi)は、各処理ユニットに局所的な推定(たとえば、各処理ユニットに関するローカルスケジューラによって典型的に行われる推定)に基づいて決定された係数であってもよい。具体的には、fi、gi、hiは、処理ユニットによって局所的に測定されたデータに基づいてマルチプロセッサコンピューティングデバイスによって生成されたタスク固有の(または処理ユニット固有の)値であってもよい。たとえば、ローカル係数は、特定の処理ユニットのローカル特性と、作業項目がその処理ユニット上で実行されているときに示される特性とに基づいてもよい。ローカル係数(すなわち、fi、gi、hi)は、以前のいくつかの作業項目にわたって観測された平均スループット、観測された温度傾向に関するいくつかの推定値、および/または一連の作業項目にわたる命令ミックスなどの、時間の期間にわたるローカル処理ユニット特性の推定値であってもよい。いくつかの実施形態では、ローカル係数は、各個別の処理ユニットに関連するデータのみに基づいて、ローカルスケジューラ機能によって個別に調整されてもよい。
【００３２】
いくつかの実施形態では、fi係数は、計算限界の浮動小数点の重い作業項目がCPU上で実行される場合など、作業負荷に基づいて急速に加熱することが予想される特定の処理ユニットに関して小さい値になるように計算されてもよい。処理ユニットに関するアプリケーションコードについての命令ミックスのコンパイル時の知識は、そのような情報を提供する場合がある。作業項目が以前の作業項目と同様であると観測または予想される場合、以前の作業項目の実行は、後続の作業項目のためのよりよいfiを推定するのに役立つ場合がある。gi係数は、特定の処理ユニットに関する作業項目あたりの推定エネルギーに反比例する場合がある。たとえば、より高い周波数を有する第1のCPUコアは、より低い周波数を有する第2のCPUコアと比較して、1つの作業項目を処理するのにより多くのエネルギーを利用する場合があり、したがって、それが望ましい目標である場合、第1のCPUコアは、より低いgi値を有し、電力効率を優先するのを助けてもよい。ローカルスケジューラは、(「i」のインデックスが付けられた)処理ユニットにおける最近の一連の作業項目にわたって推定された作業項目あたりのエネルギーに基づいてgiを計算し、作業項目の特性に特有であるように調整されたgiを作成してもよい。hi係数は、特定の処理ユニットにおける作業項目のスループット(または計算速度)に比例してもよい。いくつかの実施形態では、hi係数値が高いほど、タスクまたは処理ユニットに関して計算された優先度が高くなってもよい。いくつかの実施形態では、GPUは、性能に関してより高い優先度を有するように計算されてもよいが、DSPは、省電力に関してより高い優先度を有するように計算されてもよい。
【００３３】
様々な実施形態では、ローカル係数、(fi、gi、hi)は、各処理ユニット(たとえば、インデックス「i」を有する処理ユニット)上で実行される、またはその処理ユニットに関する位置情報を使用するローカルスケジューラによる「ローカル」決定を表してもよい。
【００３４】
式1のローカル測定値(すなわち、Tempi、Poweri、Freqi)は、個々の処理ユニットにおける現在の動作状況の正規化測定値に対する式であってもよい。一般に、ローカル測定値(またはコアごとに測定されたメトリック)は、ローカルスケジューラよりも速い調整を可能にし得る。正規化は、典型的には、いくらかの最高温度限界、電力レベル、または許可された周波数設定に関するものであってもよい。いくつかの実施形態では、処理ユニット(またはタスク)の優先度は、ローカル温度がより高いとき、より低くてもよい。たとえば、特定の処理ユニットに関する全体的な優先度計算は、所与の時間における処理ユニットの測定温度がより高いとき、より低くてもよい。式1のローカル測定値(すなわち、Tempi、Poweri、Freqi)は、様々な動作状況の瞬時の測定値に基づいてもよい。
【００３５】
いくつかの実施形態では、ローカル測定値は、以下の式を使用して生成されてもよい。
Tempi=1-(Ti/ThermalLimiti)    式2
ここで、Tiは、推定または測定された温度を表し、ThermalLimitiは、インデックスiを有する処理ユニットにおける最高温度(または限界)を表す。
Poweri=1-(Pi/PowerLimiti)    式3
ここで、Piは、推定または測定されたコア電力バーンを表し、PowerLimitiは、インデックスiを有する処理ユニットにおける最大電力消費レベル(または限界)を表す。
Freqi=Fi/MaxFreqi    式4
ここで、Fiは、推定または測定された周波数状態を表し、MaxFreqiは、インデックスiを有する処理ユニットにおける最大周波数(または限界)を表す。作業項目が電力消費にどのように寄与しているかにかかわらず、Poweriは、処理ユニット(インデックス「i」)の瞬時の電力測定値に基づいてもよい。
【００３６】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、優先度を計算するとき、作業項目ごとの推定を利用してもよい。たとえば、マルチプロセッサコンピューティングデバイスは、特定の処理ユニットにおける作業項目ごとのスループットを推定してもよく、各処理ユニットに関する作業項目の測定された完了率が、各処理ユニットに関する最大周波数に正規化されてもよい。作業項目ごとのスループット推定は、評価された作業項目が実行時に類似しているとき、全体的な優先度計算に有益であり得る。作業項目ごとのスループット推定は、作業項目が類似していないときも有益である場合があるが、変動は、作業項目の反復空間全体に均等に分散される。いくつかの実施形態では、そのような推定は、処理ユニットのローカルスケジューラによって実行されてもよく、ローカル係数hiにおいて反映されてもよい。
【００３７】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、特定の処理ユニットにおける作業項目あたりのエネルギーを推定してもよい。そのような実施形態では、観測された命令ミックス(たとえば、実行されるべき命令のタイプ、浮動小数点演算の量など)は、電力消費および/または温度に対する潜在的な影響(たとえば、より多くの浮動小数点演算は、熱レベルをより速く増加させ得るなど)を推定するために、コンパイル時または実行時に識別されてもよい。
【００３８】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、温度測定値、電力消費測定値、および/または周波数測定値に重み付けするか、または他の方法でバイアスしてもよい。たとえば、特定のワークスティーリング決定について、マルチプロセッサコンピューティングデバイスは、性能(たとえば、周波数)に基づいて、複数の作業準備完了プロセッサのための優先度を計算してもよいが、作業準備完了プロセッサに関連する電力消費および/または温度に関連するデータを完全には利用しなくてもよい。言い換えれば、優先度は、温度、電力消費、および/または周波数に関連する係数の任意の組合せおよび/または程度を使用して計算されてもよい。いくつかの実施形態では、温度係数、電力消費係数、および周波数係数は、特定の処理ユニットに高度に相関されてもよく、優先度値を計算するために十分な係数のサブセットのみの使用を可能にする。
【００３９】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、確率論的手法を使用して、ワークスティーリングのための作業準備完了プロセッサ(「勝利した」作業準備完了プロセッサ)を選択してもよい。具体的には、マルチプロセッサコンピューティングデバイスは、対応する優先度値に基づいて作業準備完了プロセッサによってアクセスされ得る1つまたは複数の「確率的ロック」を利用してもよい。一般に、いくつかの並列処理実装形態では、マルチプロセッサコンピューティングデバイスは、共有メモリを利用してもよい。典型的な場合には、共有メモリ内の特定のデータへのアクセスを制限するために、ロックが用いられてもよい。そのような場合、ワークスティーリングプロトコルは、勝利作業準備完了プロセッサが犠牲者プロセッサから作業を直接盗むことを可能にするために、共有ワークスティーリングデータ構造を利用してもよい。ワークスティーリングデータ構造(たとえば、ワークスティーリングツリーデータ構造など)は、特定の共有タスク(または計算)の作業項目のどの範囲を担当するプロセッサを説明してもよい。
【００４０】
いくつかの実施形態では、作業準備完了プロセッサは、共有データ構造における確率的ロックを獲得するために並列に競合してもよく、典型的には、一度に1つの勝利処理ユニットが成功し、盗む。確率的ロックを獲得することは、競合する作業準備完了プロセッサの優先度に基づいてもよい。たとえば、上記の式1によって計算されるような最も高い優先度を有する作業準備完了プロセッサは、より低い優先度値を有する他の作業準備完了プロセッサに対してロックを獲得するより高い優先度を有してもよい。言い換えれば、確率的ロックに対して同時に競合している2つの作業準備処理ユニット(たとえば、インデックス「i」を有する処理ユニットおよびインデックス「j」を有する別の処理ユニット)は、それぞれ優先度PiおよびPjによって決定された確率的ロックを獲得する確率を有してもよい。確率的ロックを獲得する作業準備完了プロセッサは、犠牲者プロセッサから作業を盗んでいる作業準備完了プロセッサと、どれくらい多くの作業項目が盗まれているのかとを反映するように、ワークスティーリングデータ構造のデータを更新することなどによって、共有ワークスティーリングデータ構造内のデータを検査し、修正する排他的アクセスを有してもよい。確率的ロックが解除されると、追加の作業準備完了プロセッサが、確率的ロックを獲得する機会を得てもよい。確率的ロックの実施形態は、作業準備完了プロセッサ間の競合または「レース」を効果的に作成することができるが、対応する実施形態の技法は、優先順位がグローバル係数およびローカル係数に基づいて計算され、特定のワークスティーリングフレームワークに依存しないので、反応性ではない場合がある。
【００４１】
いくつかの実施形態では、確率的ロックを獲得することは、処理ユニットの計算された優先度値(たとえば、Pi)を受け入れる機能を使用する(または呼び出す)処理ユニットを含んでもよい。いくつかの実施形態では、処理ユニットが確率的ロックを獲得することを再試行することができるレートは、優先度値に基づいてもよい。たとえば、処理ユニット「i」は、優先度Piに基づく間隔でロック獲得機能を呼び出すことが許可されてもよい。
【００４２】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスによる作業負荷分配の決定は、勝利作業準備完了プロセッサを決定する第1の決定と、勝利作業準備完了プロセッサにどれくらい多くの作業を分配するのかを決定する第2の決定の二重であってもよい。勝利作業準備完了プロセッサが決定されると、マルチプロセッサコンピューティングデバイスは、勝利作業準備完了プロセッサおよび犠牲者プロセッサの相対的優先度に基づいて、勝利作業準備完了プロセッサに再割り当てされ、転送されるべき作業の量(または、どれくらい多くの作業項目か)を決定してもよい。たとえば、マルチプロセッサコンピューティングデバイスは、決定が行われたときの相対的な電力状態/熱状態に基づいて、犠牲者タスクと勝利作業準備完了タスクとの間の作業の割合または分割を決定してもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、盗まれ得る/保持され得る利用可能な作業項目の数または割合を識別するために、犠牲者プロセッサおよび勝利作業準備完了プロセッサの優先度を計算してもよい。たとえば、本明細書で説明する式を使用して計算された優先度値に基づいて、マルチプロセッサコンピューティングデバイスは、2つのタスクの相対速度に基づいて、勝利タスクが犠牲者タスクに対してわずかな優先度しか持たないため、犠牲者タスクが利用可能な作業項目のセットの大部分を保持すべきであることを決定してもよい。
【００４３】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、犠牲者プロセッサと勝利作業準備完了プロセッサとの間の作業項目の割り振りを計算するために、以下の式を使用してもよい。
Ni=K*(Pi/(Pi+Pj))    式5
Nj=K-Ni    式6
式6および式7において、iは、第1のタスクインデックス(またはID)を表し、jは、第2のタスクインデックス(またはID)を表し、Niは、第1のタスクに与えられる作業項目の数を表し、Njは、第2のタスクに与えられる作業項目の数を表し、Kは、盗む前に犠牲者プロセッサによって処理される残りの作業項目の総数を表し、Pjは、第2のタスクの優先度を表し、Piは、第1のタスクの優先度を表す。様々な実施形態では、作業準備完了プロセッサによって盗まれる作業項目の数は、式1によって計算された優先度に比例してもよい。
【００４４】
例示的な式8〜式10を使用する非限定的な例示として、犠牲者プロセッサ(すなわち、インデックスiを有する処理ユニットまたはタスク)および作業準備完了プロセッサ(すなわち、インデックスjを有する処理ユニットまたはタスク)は、並列ループルーチンに関する作業項目を実行するように構成されてもよい。所与の時点で、作業準備完了プロセッサは、犠牲者プロセッサから作業項目を盗む準備ができている他の作業準備完了プロセッサに対して勝利作業準備完了プロセッサとして識別される場合がある。そのとき、並列ループルーチンのために犠牲者プロセッサによって処理されるために残っている10の反復(すなわち、Kの作業項目=10)が存在する場合がある。さらに、犠牲者プロセッサは、第1の優先度(Pi=1)をタグ付けされる場合があり、勝利作業準備完了プロセッサは、第2の優先度(Pj=2)をタグ付けされる場合がある。結果として、マルチプロセッサコンピューティングデバイスは、被害者プロセッサが並列ループルーチンの3までの反復を保持してもよいこと(すなわち、式5により、Ni=〜3.33=10*(1/(1+2)))と、勝利作業準備完了プロセッサが並列ループルーチン7までの反復を割り振られること(すなわち、式6により、Nj=〜6.67=10-3.33)とを計算してもよい。
【００４５】
いくつかの実施形態では、複数の作業準備完了プロセッサが、犠牲者プロセッサからの作業項目を割り振られてもよい。そのような場合、マルチプロセッサコンピューティングデバイスは、式5〜式6を参照して本明細書で説明するように、割り振りの割合を決定するために、同様の手法を利用してもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、作業準備完了待ち行列内のいくつかの作業準備完了タスクを集合的に調査し、盗まれた作業項目を、それぞれの優先度に比例して複数の作業準備完了プロセッサにわたって分散させてもよい。
【００４６】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、より遅い処理ユニットおよび/またはタスク(たとえば、DSPなどの、よりエネルギー効率のよい勝者作業準備完了プロセッサ)により多くの作業項目を割り当てるように構成されてもよい。そのような設定では、より遅いエネルギー効率のよいプロセッサは、より大きいβi係数またはgi係数を有することにより、より速いプロセッサよりも高い優先度を割り当てられる。このようにして、バッテリー寿命を最大化するために、より低い電力漏れまたはより低い有効電力を有する処理ユニットおよび/またはタスクが好まれる場合があり、エネルギー効率ポリシーは、異なる処理ユニットにわたるグローバル係数値および/またはローカル係数値の適切な選択によって単に実施される。
【００４７】
様々な実施形態では、マルチプロセッサコンピューティングデバイスは、スケジューリングタスクまたはディスパッチタスクのための様々な動作を実行するために、1つまたは複数の実行時機能(たとえば、実行時サービス、ルーチン、スレッド、または他のソフトウェア要素など)を実行してもよい。そのような1つまたは複数の機能は、一般に、本明細書では「実行時機能」と呼ばれることがある。実行時機能は、オペレーティングシステム、サービス、および/または他のシステム関連ソフトウェアを実行するように構成された汎用プロセッサまたはアプリケーションプロセッサなどの、マルチプロセッサコンピューティングデバイスの処理ユニットによって実行されてもよい。たとえば、アプリケーションプロセッサ上で実行される実行時機能は、1つまたは複数の処理ユニット上で実行されるタスクの優先度を計算するように構成されてもよい。個々の処理ユニットにおけるタスクを処理するための専用機能などの他の実行時機能が使用されてもよい。
【００４８】
マルチプロセッサコンピューティングデバイスの処理ユニットは、各々が1つまたは複数の処理項目に関連付けられ得る1つまたは複数のタスクを実行するように構成されてもよい。いくつかのタスクは、共通のデータ並列処理作業に参加するように構成されてもよい。たとえば、GPUは、DSPおよびCPUによっても共有される並列ループルーチン(または作業負荷)の作業項目(または反復)のセットを処理するための特定のタスクを実行するように構成されてもよい。しかしながら、本明細書で説明する実施形態の技法は、複数の処理ユニットにおけるそのような共通データ並列処理作業負荷を改善するために、マルチプロセッサコンピューティングデバイスによって明らかに使用されてもよいが、様々な処理ユニットで共有され得る任意の作業負荷が、実施形態の技法によって改善され得る。たとえば、本明細書で説明するように優先度計算に基づくワークスティーリングポリシーは、複数の処理ユニットにおいて離散的に実行され得るマルチバージョンタスクまたは汎用計算のマルチプロセッサコンピューティングデバイスの全体的な性能を改善するために使用されてもよい。
【００４９】
作業準備完了プロセッサは、様々な方法で「作業準備完了」(たとえば、犠牲者プロセッサから作業項目を盗む準備が完了している)として決定されてもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、他の処理ユニットから作業項目を受け取る準備ができている処理ユニットおよび関連タスク(すなわち、作業準備完了プロセッサ)を継続的に(または定期的に)識別するように構成されてもよい。作業準備完了プロセッサの識別は、盗む準備ができていることを示す実行時機能への処理ユニットからのアプリケーションプログラミングインターフェース(API)呼び出しの検出、処理ユニットに関連するシステム変数の設定、全体的なワークスティーリングリストへの処理ユニットの識別子の入力、割込みの送信などの、様々な方法において成し遂げられてもよい。共有メモリを利用するいくつかの他の実施形態では、マルチプロセッサコンピューティングデバイスの各処理ユニットは、(たとえば、処理ユニットが、最初に割り当てられた作業項目がもうないことを検出したとき)それぞれの作業準備完了状態を独立して実現してもよく、本明細書で説明するように作業項目を盗む(たとえば、確率的ロックを獲得するなど)ために、共有ワークスティーリングデータ構造にアクセスする動作を同時に実行してもよい。
【００５０】
簡単にするために、タスク待ち行列から作業項目を受信する準備ができているとして識別された作業準備完了プロセッサのリストであり得る「作業準備完了プロセッサ待ち行列」に参照がなされてもよい。そのような作業準備完了プロセッサ待ち行列または他のデータ構造は、マルチプロセッサコンピューティングデバイス内の特定の処理ユニットに関連付けられてもよく、作業準備完了プロセッサが作業項目を与えられると更新されてもよい。たとえば、タスク待ち行列からの転送が成功したとき、勝利作業準備完了タスクに関連するデータは、作業準備完了プロセッサ待ち行列からポップ、デキュー、または他の方法で除去されてもよい。図2A〜図2Dに関して示したように、作業準備完了プロセッサ待ち行列は、別の処理ユニットから作業項目を受け取るために利用可能な任意の処理ユニット(または関連するタスク)に関する識別データを追跡するために使用され得るメモリ内に記憶されたデータ構造(たとえば、アレイ、待ち行列、リンクリストなど)であってもよい。
【００５１】
しかしながら、そのような作業準備完了プロセッサ待ち行列への参照は、1つまたは複数の作業準備完了タスクを識別および/または他の方法で管理するための任意の特定の実装形態に実施形態または特許請求の範囲を限定することを意図していない。たとえば、共有メモリ環境では、処理ユニットは、ワークスティーリングデータ構造へのアクセスについて単に競合してもよい。いくつかの実施形態では、実行時機能は、任意の特定の処理ユニットから作業項目を受け取る準備ができている作業準備完了タスクを識別するための作業準備完了プロセッサ待ち行列および/または任意の他の同様の機構を管理するように構成されてもよい。たとえば、作業準備完了プロセッサ待ち行列を使用する代わりに、処理ユニットは、連続する作業項目の集合(たとえば、ループにおける反復)を管理するために、様々なデータ構造、データコンテナ、および/または他の記憶されたデータを利用してもよい。
【００５２】
実施形態の技法は、作業負荷分配を決定し、マルチプロセッサシステム(たとえば、ARMのbig.LITTLEアーキテクチャを使用するモバイルデバイス)における電力消費と熱放散とを事前対処的にバランスさせるために、動的タスクに関する動作状態(たとえば、電力消費、周波数、温度)にタグ付けするか、または他の方法でアクセスする。これらの改善は、並列プログラム実行と、アーキテクチャ/OSレベルの電力および熱管理との間のギャップを埋めるために働き、したがって、電力消費と、熱放散と、他の動作パラメータもバランスさせるワークスティーリング解決策を提供する。(たとえば、中央権限または実行時システムによる)様々な実施形態の技法は、作業負荷分配を事前対処的にバランスさせるために、様々なタスク/処理ユニットの電力消費状態、周波数状態、および熱状態に関するデータを使用してもよい。実施形態の技法は、処理ユニット全体からの状態情報を利用するローカル値、グローバル値と、ローカルコアデータ(たとえば、メトリック、サンプリングされたデータ)を有するローカルスケジューラなどの、所与の時間におけるローカル測定値の両方を含む、きめの細かい包括的な優先度を計算する。
【００５３】
いくつかの従来の温度管理方式は、許容できない温度(たとえば、所定のしきい値を超える温度)を検出することに応答して、熱状況を緩和する動作を取る。実施形態の技法は、作業項目が処理され得る場所を特定するために、処理ユニットおよび/またはタスクの温度(および他の動作状態データ)を使用するワークスティーリング技法により、許容できない状況に遭遇する前に、熱問題を防止する。さらに、従来の技法は、様々なタスクまたは動作に関する予め定義された優先度を利用する場合がある。実施形態の技法は、タスクの動的な動作状態に基づいて、相対的な優先度を識別するために、任意のタスクについてのきめ細かいデータを利用する。
【００５４】
したがって、様々な実施形態は、マルチコアプロセッサコンピューティングデバイスにおいてワークスティーリング技法により性能と電力とを効率的にトレードオフする事前対処的なタスク管理技法を提供する。様々な実施形態は、様々なプロセッサの実行速度状態、温度状態、および/または電力状態を考慮する方法で全体的な負荷分散を達成するために、犠牲者プロセッサから作業項目を受け取る作業準備完了プロセッサを選択するためのインテリジェントな方法を提供する。
【００５５】
様々な実施形態は、よりインテリジェントなワークスティーリング決定を行うために、処理ユニット全体からのグローバル状態情報と、各処理ユニットにおけるローカル情報とを使用してもよい。そのような実施形態の技法は、様々なワークスティーリング技法を実施することができる異なるコンピューティングシステムにおける負荷の不均衡による性能を改善するために用いられてもよい。たとえば、実施形態の方法は、異種マルチコアコンピューティングデバイス、同種マルチコアコンピューティングデバイス、分散処理のために構成されたサーバまたはシステム(たとえば、分散コンピューティングサーバ)などにおける性能を改善するために使用されてもよい。様々な実施形態の方法は、任意のタイプの並列化システムおよび/または実装形態に特有ではなく、代わりに、実時間がワークスティーリングを実施することができる方法に関係なく、様々なワークスティーリング決定に優先度を追加する方法を提供する。したがって、任意の特定のタイプまたは構造のマルチプロセッサコンピューティングデバイス(たとえば、異種マルチプロセッサコンピューティングデバイスなど)、および/または本明細書で説明する一般的なワークスティーリング実装形態への参照は、単純化のために使用されているだけであり、実施形態および特許請求の範囲を限定することを意図していない。
【００５６】
図1は、様々な実施形態とともに使用するのに適した例示的な異種マルチプロセッサコンピューティングデバイス101の様々な構成要素を示す図100である。異種マルチプロセッサコンピューティングデバイス101は、第1のCPU102(図1では「CPU_A」102と呼ばれる)、第2のCPU112(図1では「CPU_B」112と呼ばれる)、GPU122、およびDSP132などの複数の処理ユニットを含んでもよい。いくつかの実施形態では、異種マルチプロセッサコンピューティングデバイス101は、「ARM big.LITTLE」アーキテクチャを利用してもよく、第1のCPU102は、比較的高い性能の能力を有するが、比較的高い電力要件も有する「大きい」処理ユニットであってもよく、第2のCPU112は、比較的低い性能の能力を有するが、第1のCPU102と比較して比較的低い電力要件も有する「小さい」処理ユニットであってもよい。
【００５７】
異種マルチプロセッサコンピューティングデバイス101は、様々な処理ユニット102、112、122、132の間の、並列処理、「作業共有」、および/または「ワークスティーリング」をサポートするように構成されてもよい。具体的には、処理ユニット102、112、122、132の任意の組合せは、実行するための個別のタスクを作成および/または受け取るように構成されてもよい。
【００５８】
処理ユニット102、112、122、132の各々は、処理ユニット102、112、122、132によって実行されるべきタスク(および/またはタスクに関連するデータ)を一時的に記憶し、編成するための1つまたは複数の待ち行列(またはタスク待ち行列)を利用してもよい。たとえば、第1のCPU102は、第1のCPU102によるローカル実行のためにタスク待ち行列166、168、176からタスクおよび/またはタスクデータを取り出してもよく、他のデバイスによる実行のために待ち行列170、172、174内にタスクおよび/またはタスクデータを配置してもよい。第2のCPU112は、第2のCPU112によるローカル実行のために待ち行列174、178、180からタスクおよび/またはタスクデータを取り出してもよく、他のデバイスによる実行のために待ち行列170、172、176内にタスクおよび/またはタスクデータを配置してもよい。GPU122は、待ち行列172からタスクおよび/またはタスクデータを取り出してもよい。DSP132は、待ち行列170からタスクおよび/またはタスクデータを取り出してもよい。いくつかの実施形態では、いくつかのタスク待ち行列170、172、174、176は、いわゆるマルチプロデューサ、マルチコンシューマ待ち行列であってもよく、いくつかのタスク待ち行列166、168、178、180は、いわゆるシングルプロデューサ、マルチコンシューマ待ち行列であってもよい。いくつかの実施形態では、タスクは、特定の計算を分割する作業負荷のプログラマによる指定などの、コード内のインジケータに基づいて生成されてもよい。
【００５９】
いくつかの実施形態では、実行時機能(たとえば、実行時エンジン、タスクスケジューラなど)は、処理ユニット102、112、122、132にタスクをディスパッチするための宛先を決定するように構成されてもよい。たとえば、処理ユニット102、112、122、132のいずれかにオフロードされ得る新しい汎用タスクを識別することに応答して、実行時機能は、タスクを実行するのに適した処理ユニットを識別し、それに従ってタスクをディスパッチしてもよい。そのような実行時機能は、第1のCPU102などのアプリケーションプロセッサまたはメインプロセッサ上で実行されてもよい。いくつかの実施形態では、実行時機能は、1つまたは複数のオペレーティングシステム対応スレッド(たとえば、「メインスレッド」150)を介して実行されてもよい。たとえば、実行時機能の決定に基づいて、メインスレッド150は、タスクデータを様々なタスク待ち行列166、170、172、180に提供してもよい。
【００６０】
図2A〜図2Dは、様々な実施形態による異種マルチプロセッサコンピューティングデバイス101によるワークスティーリング動作の非限定的な例を示す。図1を参照して説明したように、異種マルチプロセッサコンピューティングデバイス101は、第1のCPU102(すなわち、図2A〜図2DにおけるCPU_A)と、第2のCPU112(すなわち、図2A〜図2DにおけるCPU_B)と、GPU122と、DSP132とを含む複数の処理ユニットを含んでもよい。処理ユニット102、112、122、132の各々は、タスクおよび関連データ(たとえば、作業項目)を管理するためのタスク待ち行列220a〜220dに関連付けられてもよい。たとえば、第1のCPU102は、第1のタスク待ち行列220aに関連付けられてもよく、第2のCPU112は、第2のタスク待ち行列220bに関連付けられてもよく、GPU122は、第3のタスク待ち行列220cに関連付けられてもよく、DSP132は、第4のタスク待ち行列220dに関連付けられてもよい。
【００６１】
処理ユニット102、112、122、132の各々は、タスクおよび関連データを管理するための作業準備完了プロセッサ待ち行列240a〜240dに関連付けられてもよい。たとえば、第1のCPU102は、第1の作業準備完了プロセッサ待ち行列240aに関連付けられてもよく、第2のCPU112は、第2の作業準備完了プロセッサ待ち行列240bに関連付けられてもよく、GPU122は、第3の作業準備完了プロセッサ待ち行列240cに関連付けられてもよく、DSP132は、第4の作業準備完了プロセッサ待ち行列240dに関連付けられてもよい。
【００６２】
作業準備完了プロセッサ待ち行列240a〜240dの各々は、特定のタスク待ち行列から作業項目を受け取るために現在待機している処理ユニット(および/または関連タスク)のアイデンティティを示すために使用されてもよい。たとえば、第1の作業準備完了プロセッサ待ち行列240a内の処理ユニットアイデンティティ(またはインデックス)は、第1のCPU102に関連する第1のタスク待ち行列220aから作業項目を受け取るのを現在待機している/競合している処理ユニットを示してもよい。
【００６３】
いくつかの実施形態では、作業準備完了プロセッサ待ち行列240a〜240dは、個々の処理ユニット102、112、122、132に直関連付けられなくてもよい様々なデータ源または構造(たとえば、システム変数、アレイなど)内に記憶されてもよい。たとえば、作業準備完了プロセッサ待ち行列240a〜240dは、現在他のタスクから作業項目を受け取る準備ができている任意の処理ユニットまたはタスクを編成するために使用される同じ待ち行列タイプのデータ構造によって表されてもよい。いくつかの実施形態では、タスク待ち行列220a〜220dおよび/または作業準備完了プロセッサ待ち行列240a〜240dは、処理ユニット102、112、122、132および/または様々なメモリユニット(たとえば、システムメモリ、共有メモリ、仮想メモリなど)内のメモリの範囲に対応する個別の構成要素(たとえば、メモリユニット)であってもよい。
【００６４】
いくつかの実施形態では、異種マルチプロセッサコンピューティングデバイス101は、オペレーティングシステム(OS)レベルのプロセス、サービス、アプリケーション、ルーチン、命令セット、またはアプリケーションプロセッサ(たとえば、CPU_A 102)によって実行されるスレッドなどの、実行時機能モジュール210を含んでもよい。実行時機能モジュール210は、少なくとも、異種マルチプロセッサコンピューティングデバイス101内のワークスティーリングポリシーを管理するための動作を実行するように構成されてもよい。たとえば、実行時機能モジュール210は、タスク待ち行列220a〜220dが空であることの決定に応答して、作業準備完了プロセッサ待ち行列240a〜240dから識別子を追加および/または除去し、ならびに、動作状態を評価する動作と、処理ユニットおよび/または関連するタスク間の相対的優先度を決定する動作とを実行するように構成されてもよい。
【００６５】
図2Aは、異種マルチプロセッサコンピューティングデバイス101における例示的なワークスティーリング動作を示す図200を示す。任意の第1の時間において、第1のCPU102に関するタスク待ち行列220aは、複数の作業項目230aを有し、DSP132に関するタスク待ち行列220dは、複数の作業項目230dを有する。しかしながら、第2のCPU112(すなわち、図2A〜図2DにおけるCPU_B)とGPU122の両方は、それぞれのタスク待ち行列220b、220c内に作業項目を持たず、したがって、第2のCPU112およびGPU122は、他の処理ユニットから作業項目を受け取る準備ができている(または適格である)。たとえば、処理ユニット102、112、122、132が、各々、並列ループルーチンの反復を処理するために作業項目を割り当てられているとき、第2のCPU112およびGPU122は、割り当てられた反復を既に完了している場合があり、第1のCPU102および/またはDSP132から反復を受け取る準備ができている場合がある。他の処理ユニットから作業項目を受け取る準備ができると、第2のCPU112およびGPU122を識別するデータが、処理されるのを待っている作業項目を有する他の処理ユニットの作業準備完了プロセッサ待ち行列に入力されてもよい。たとえば、第2のCPU112に関する識別データ(すなわち、データ242a)およびGPU122に関する識別データ(すなわち、データ252a)が、第1のCPU102の作業準備完了プロセッサ待ち行列240a内に配置されてもよい。
【００６６】
様々な実施形態では、作業項目を受け取る準備ができている作業準備完了プロセッサは、システムの処理ユニットの複数のタスク待ち行列のうちの1つから作業項目を受け取るために競合する場合がある。言い換えれば、所与の時間において2つ以上の潜在的な犠牲者プロセッサが存在する場合がある。たとえば、第1のCPU102のタスク待ち行列220aから作業項目を受け取るために競合する代わりに、第2のCPU112およびGPUは、DSP132の作業プロセッサ待ち行列240d内に入れられることによって、代わりにDSP132のタスク待ち行列220dから作業項目を受け取るために競合してもよい。別の例として、第1のCPU102のタスク待ち行列220aから作業項目を受け取るために競合する代わりに、第2のCPU112は、第1のCPU102の作業準備完了プロセッサ待ち行列240a内に入れられてもよく、GPU122は、DSP132の作業準備完了プロセッサ待ち行列240d内に入れられてもよい。しかしながら、様々な実施形態では、作業準備完了プロセッサは、任意の所与の時間において1つの作業準備完了プロセッサ待ち行列内で競合するだけでもよい。さらに、様々な実施形態では、犠牲者プロセッサのタスク待ち行列から作業項目を受け取るための複数の作業準備完了プロセッサ間の競合の結果は、同じ犠牲者プロセッサおよび/または他の犠牲者プロセッサに関する後続の競合の結果に影響を与えない場合がある。たとえば、第2のCPU112が、第1の時間においてGPU122を介して第1のタスク待ち行列220aから作業項目230aを与えられた場合、第2のCPU112は、第2の時間において、GPU122を介して第4のタスク待ち行列220dから作業項目230dを割り当てられる必要はなくてもよい。
【００６７】
図2Bは、図2Aの第1の時間の後の第2の時間におけるワークスティーリング動作の一例を示す図260を示す。第2の時間において、実行時機能モジュール210は、(たとえば、温度、電力消費、および/または周波数に基づく)本明細書で説明する優先度計算に基づいて、第1のCPU102のタスク待ち行列220aからGPU122のタスク待ち行列220cに作業項目230a'を転送してもよい。たとえば、第2のCPU112およびGPU122が両方とも第1のCPU102から受け取る準備ができていることを検出する(すなわち、第1の作業準備完了プロセッサ待ち行列240a内のデータ242a、252aを識別する)ことに応答して、実行時機能モジュール210は、各処理ユニット112、122に関する温度、電力消費、および/または周波数に対処する(またはそれらに少なくとも部分的に基づく)第2のCPU112とGPU122との間の相対的優先度を計算してもよい。実行時機能モジュール210は、第2の時間におけるGPU122に関するより高い優先度値に基づいて、GPU122が第2のCPU112に対する勝利作業準備完了プロセッサであると決定してもよい。したがって、図示の例では、第2のCPU112が盗む目的に関してより低い優先度を有すると計算されるので、第2の時間において作業タスクは第2のCPU112のタスク待ち行列220bに転送されない場合がある。しかしながら、盗み優先度計算の動的性質のために、第2のCPU112が他の時間においてGPU122よりも高い盗み優先度を有する可能性があり得る。
【００６８】
GPU122が勝利作業準備完了プロセッサと決定されると、実行時機能モジュール210は、GPU122に再割り当てされる作業の量に関する決定を行ってもよい。たとえば、実行時機能モジュール210は、本明細書で説明するように第1のCPU102およびGPU122の相対的優先度を計算してもよい。これらの相対的優先度に基づいて、実行時機能モジュール210は、第1のCPU102のタスク待ち行列220a内の元の4つの保留中の作業項目230aのうちの2つがGPU122のタスク待ち行列220cに転送されてもよいことを決定してもよい。
【００６９】
作業項目の転送(または再割当て)の後、実行時機能モジュール210は、第1のCPU102の作業準備完了プロセッサ待ち行列240aから勝利作業準備完了プロセッサ(すなわち、GPU122)に関連する識別データ252aを除去してもよい。いくつかの実施形態では、実行時機能モジュール210は、作業項目230a'を転送することに応答して、すべての作業準備完了プロセッサ待ち行列240a、240dから勝利作業準備完了プロセッサに関連するすべての識別データを除去してもよい。いくつかの実施形態では、任意の競合する作業準備完了プロセッサに関するすべての識別データ242a、252a、242d、252dは、勝利作業準備完了プロセッサに作業項目を与えることに応答して、作業準備完了プロセッサ待ち行列240a、240dから除去されてもよく、したがって、作業準備完了プロセッサに作業項目を受け取る準備を再主張させる。たとえば、GPU122が実行時機能モジュール210による優先度計算に基づいて作業項目230a'を勝ち取った後、第2のCPU112は盗むために利用可能な作業項目を有する処理ユニット102、132の作業準備完了プロセッサ待ち行列240a、240dに新しい識別データ242a、242dを入力してもよい。
【００７０】
図2Cは、図2Bの第2の時間の後の第3の時間における例示的なワークスティーリング動作を示す図270を示す。第3の時間において、実行時機能モジュール210は、第1のCPU102のタスク待ち行列220aから第2のCPU112に作業項目230a"を転送してもよい。言い換えれば、作業項目230a'をGPU122に最初に渡した後、実行時機能モジュール210は、作業準備完了プロセッサ待ち行列240a、240d内の残りの作業準備完了プロセッサが作業項目を渡され得るかどうかを決定するために、後続のワークスティーリング計算を実行してもよい。たとえば、第1のCPU102の作業準備完了プロセッサ待ち行列240a内の第2のCPU112の識別データ242aを検出することに応答して、実行時機能モジュール210は、競合していない第2のCPU112が作業項目230a"を受信し得ることを決定するために、処理ユニット102、112の相対的優先度を計算してもよい。
【００７１】
図2Dは、実行時機能モジュール210が、優先度計算に基づいて第1のCPU102のタスク待ち行列220aから第2のCPU112に任意の作業項目230aを渡さない場合がある、第3の時間におけるワークスティーリング動作の代替的な結論を示す図280を示す。たとえば、実行時機能モジュール210は、電力消費、温度、および/または周波数に基づく優先度計算を実行し、第2のCPU112に作業項目を提供しない作業項目230aを再割り振りするための比を決定してもよい。この場合、優先度に基づいて、第2のCPU112は、第1のCPU102から作業項目230aを獲得するより低い確率を有していた場合がある。したがって、実行時機能モジュール210は、第2のCPU112に作業項目230aを転送することを拒否してもよい。たとえば、第2のCPU112における高い現在の温度に基づいて、実行時機能モジュール210は、第1のCPU102が、タスク待ち行列220a内に残っている作業項目230aを完了するために第2のCPU112よりもよいオプションであると決定してもよい。
【００７２】
異なるワークスティーリング実装形態は、説明した実施形態の優先度計算から利益を得ることができる。たとえば、(たとえば、図2A〜図2Dに示すような)待ち行列を使用するいくつかのコンピューティング環境は、作業準備完了プロセッサの優先度と、タスク待ち行列からの作業項目の関連する割り振りとを計算するための実施形態の技法を用いてもよい。別の例として、共有メモリ環境において、マルチプロセッサコンピューティングデバイスは、共有メモリの様々なセグメントに関連する作業項目に対応するワークスティーリングデータ構造を使用して並列処理作業負荷の再割り振りを管理するように構成されてもよい。図3は、いくつかの実施形態による、共有メモリ306とワークスティーリングデータ構造304とを有するマルチプロセッサコンピューティングデバイス301による例示的なワークスティーリング動作を示す。図2A〜図2Dに示す例示的なシステムとは異なり、図3のマルチプロセッサコンピューティングデバイス301は、待ち行列を使用せず、代わりに、共有タスクの様々な作業項目へのアクセスを制御する共有ワークスティーリングデータ構造304を使用する、ワークスティーリングの高性能な実装形態であり得る。
【００７３】
図3に示すように、処理ユニットが共有タスクに関する割り当てられた作業負荷を完了したときはいつでも、処理ユニットは、他の処理ユニットから盗む準備ができているようになってもよい(たとえば、作業準備完了プロセッサになってもよい)。たとえば、第2のCPU112とGPU122の両方は、それ自体が「盗む準備ができている」と独立に決定してもよい。第2のCPU112およびGPU122は、次いで、共有タスクの元の作業項目を依然として処理している第1のCPU102またはDSP132のいずれかから作業項目を盗むために競合(レース)してもよい。いくつかの実施形態では、第2のCPU112とGPU122の両方は、優先度ベースの確率的ロック機構302を介してワークスティーリングデータ構造304に対する制御を獲得するために競合してもよい。処理ユニット112、122のいずれかが優先度ベースの確率的ロック機構302に対する制御を得る確率は、それぞれの優先度(たとえば、説明したように式1によって計算された値)に依存する場合がある。確率的ロックに対する制御を得る1つの処理ユニットは、したがって、「勝利作業準備完了プロセッサ」としてワークスティーリングデータ構造304への変更アクセスを得ることができる。ワークスティーリングデータ構造304内のデータを更新または他の方法で変更するためのアクセスにより、勝者作業準備完了プロセッサは、他の処理ユニット(たとえば、第1のCPU102、DSP132)からの作業項目を再割り当てし、次いで、共有メモリ306から直接作業項目を取り出してもよい。
【００７４】
図4Aは、動作状態データに基づいてワークスティーリング決定を行うことによって複数の処理ユニット間で作業負荷を事前対処的にバランスさせるための方法400を示す。説明したように、マルチプロセッサコンピューティングデバイス(たとえば、図1〜図2D、図3におけるマルチプロセッサコンピューティングデバイス101、301)は、電力消費、温度、および/または周波数動作状態データに関する作業準備完了プロセッサおよび犠牲者プロセッサの優先度を計算することによって、改善されたワークスティーリングを可能にするように構成されてもよい。1つまたは複数の作業準備完了プロセッサが犠牲者プロセッサから作業項目を盗む準備ができていると識別されると、マルチプロセッサコンピューティングデバイスは、関係する処理ユニット(たとえば、作業準備完了タスクの処理ユニットおよび犠牲者タスクの処理ユニット)の静的特性と、処理ユニットの動的動作状況とを評価することによって優先度を計算してもよい。そのような包括的な優先度値は、作業準備完了プロセッサ間の相対的なランク付け、ならびに、勝利作業準備完了プロセッサへの作業項目の分配を決定するために使用されてもよい。このようにして、マルチプロセッサコンピューティングデバイスは、動的なワークスティーリング決定を指示し、システムの効率および性能を改善するために、異なる処理ユニットおよび関連するタスクについてのきめの細かい動作データを用いてもよい。
【００７５】
様々な実施形態では、方法400は、マルチプロセッサコンピューティングデバイスの各処理ユニットに対して実行されてもよい。たとえば、マルチプロセッサコンピューティングデバイスは、各処理ユニットのタスクに対するワークスティーリングを処理するために、方法400の1つまたは複数のインスタンス(たとえば、方法400を実行するための1つまたは複数のスレッド)を同時に実行してもよい。いくつかの実施形態では、方法400の様々な動作は、(たとえば、アプリケーションプロセッサ、図1〜図2Dのマルチプロセッサコンピューティングデバイス101のCPU102などを介して)マルチプロセッサコンピューティングデバイスの処理ユニットにおいて実行される実行時機能(たとえば、図2A〜図2Dの実行時機能モジュール210)によって実行されてもよい。
【００７６】
方法400を参照すると、マルチプロセッサコンピューティングデバイスは、決定ブロック402において、第1の処理ユニットおよび/または関連するタスクから転送または「盗まれる」ために利用可能な任意の作業項目が存在するかどうかを決定してもよい。言い換えれば、マルチプロセッサコンピューティングデバイスは、第1の処理ユニットおよび/または関連するタスクが、所与の時間において犠牲者プロセッサとして処理されるべきかどうかを決定してもよい。たとえば、マルチプロセッサコンピューティングデバイスは、第1の処理ユニットおよび/もしくは関連するタスクが、他の場所で実行され得る作業項目(たとえば、並列ループルーチンの反復)を実行しているかどうか、ならびに/または、第1の処理ユニットがまだ処理していない(または、近い将来に処理するようにスケジュールされている)任意の作業項目が存在するかどうかを決定してもよい。そのような決定は、現在保留中の作業項目の数および/またはタイプを問い合わせることなどによって、第1の処理ユニットのタスク待ち行列を評価することによって、マルチプロセッサコンピューティングデバイスによって行われてもよい。いくつかの実施形態では、第1の処理ユニットおよび/または関連するタスクは、対応するタスク待ち行列内の保留中の作業項目の数がしきい値を超えたときにのみ、犠牲者プロセッサであってもよい。たとえば、マルチプロセッサコンピューティングデバイスは、第1の処理ユニットから別の処理ユニットへの作業項目の任意の移動を有利にするために必要な作業項目の最小数を特定してもよい。そのようなしきい値は、第1の処理ユニットにおいて局所的に計算を実行する(たとえば、特定の数の作業項目を処理する)ために必要な推定された第1の時間と、別の処理ユニットにおける計算を実行するために必要な推定された第2の時間との比較に基づいて計算されてもよい。
【００７７】
いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、第1の処理ユニットおよび/または関連するタスクが盗まれる可能性があるかどうかを決定するために、上記で説明したように優先度を計算してもよい。たとえば、第1の処理ユニットの相対的優先度が他の処理ユニットよりも高いとき、マルチプロセッサコンピューティングデバイスは、他の処理ユニットが、作業項目の利用可能性にかかわらず、第1の処理ユニットから盗むことができないと決定してもよく、したがって、時間間隔の間、第1の処理ユニットからのワークスティーリングを可能にするために、任意のさらなる動作を控えてもよい。
【００７８】
第1の処理ユニットおよび/または関連するタスクから盗まれるために利用可能な作業項目がないことを決定するために(すなわち、決定ブロック402=「No」)、第1の処理ユニットおよび/または関連するタスクは、現時点において犠牲者プロセッサではない可能性があり、したがって、マルチプロセッサコンピューティングデバイスは、決定ブロック402において、犠牲者プロセッサ決定動作を続けてもよい。いくつかの実施形態では、決定ブロック402の犠牲者プロセッサの決定は、直ちに、または予め定義された時間の期間の後(たとえば、所定の待機期間の経過後)に実行されてもよい。
【００７９】
第1の処理ユニットおよび/または関連するタスクから盗まれるために利用可能な少なくとも1つの作業項目が存在することを決定することに応答して(すなわち、決定ブロック402=「Yes」)、第1の処理ユニットおよび/または関連するタスクは、現時点において犠牲者プロセッサであると決定されてもよい。オプションのブロック404において、マルチプロセッサコンピューティングデバイスは、犠牲者プロセッサから作業項目を受け取る準備ができている任意の作業準備完了プロセッサ(たとえば、作業準備完了処理ユニット、作業準備完了タスク)を識別してもよい。たとえば、マルチプロセッサコンピューティングデバイスは、1つまたは複数の作業準備完了プロセッサが犠牲者プロセッサからの作業項目を要求しているか、または犠牲者プロセッサからの作業項目を割り当てられる準備ができていることを示す、様々なAPIコール、割込み、および/または記憶されたデータ(たとえば、システム変数、作業準備完了プロセッサ待ち行列内のデータなど)を評価してもよい。オプションのブロック404における動作は、本明細書で説明するように、「作業準備完了待ち行列」に依存する実施形態に適用されてもよいため、オプションであってもよく、したがって、オプションのブロック404の動作は、説明したように共有メモリとワークスティーリングデータとを利用する他の実施形態には適用できない可能性がある。
【００８０】
いくつかの実施形態では、作業準備完了プロセッサは、特定の犠牲者プロセッサから作業項目を受け取ることを特に要求してもよく、および/または任意の利用可能な犠牲者プロセッサから受け取ることを要求してもよい。たとえば、準備できている作業準備完了プロセッサが、特定の処理ユニットに関する作業準備完了プロセッサ待ち行列(たとえば、GPUの作業準備完了プロセッサ待ち行列など)内に配置されてもよい。別の例として、準備できている作業準備完了プロセッサが、任意の処理ユニットの任意のタスク待ち行列から作業項目を受け取るために汎用待ち行列内に配置されてもよい。
【００８１】
マルチプロセッサコンピューティングデバイスは、決定ブロック406において、犠牲者プロセッサから作業項目を受け取る準備ができている1つまたは複数の作業準備完了プロセッサが存在するかどうかを決定してもよい。犠牲者プロセッサから受け取る準備ができている作業準備完了プロセッサが存在しないことを決定することに応答して(すなわち、決定ブロック406=「No」)、マルチプロセッサコンピューティングデバイスは、決定ブロック402における犠牲者プロセッサ決定動作を続けてもよい。
【００８２】
犠牲者プロセッサから受け取る準備ができてきる少なくとも1つの作業準備完了プロセッサが存在することを決定することに応答して(すなわち、決定ブロック406=「Yes」)、マルチプロセッサコンピューティングデバイスは、ブロック408において、犠牲者プロセッサおよび1つまたは複数の作業準備完了プロセッサに関連する静的特性データを取得してもよい。そのような静的特性は、作業準備完了プロセッサおよび犠牲者プロセッサに対応する処理ユニットの属性/能力を記述する情報を含んでもよい。たとえば、各作業準備完了プロセッサおよび犠牲者プロセッサに関する静的特性データは、使用される技法(たとえば、アーキテクチャ、特殊能力、動作仕様、および/またはしきい値など)、マルチプロセッサコンピューティングデバイスのトポロジ内の位置(たとえば、モデムの近くなど)、および/または製造者データ(たとえば、年数/設置日など)を示すデータを含んでもよい。いくつかの実施形態では、静的特性データは、様々な処理ユニットまたはマルチプロセッサコンピューティングデバイスの製造時に一回、マルチプロセッサコンピューティングデバイスの各起動時に、周期的に(たとえば、毎日、毎週、毎月など)、またはそれらの任意の組合せにおいて取得されてもよい。いくつかの実施形態では、静的特性を取得することは、上記で説明したように式1(すなわち、Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi)において使用されるグローバル係数(たとえば、αi、βi、γi)に関する値を識別することを含んでもよい。
【００８３】
ブロック410において、マルチプロセッサコンピューティングデバイスは、犠牲者プロセッサおよび1つまたは複数の作業準備完了プロセッサに関連する動的特性データを取得してもよい。動的特性データは、様々な処理ユニットにおける動作の現在の、最近の、および/または過去の実行に関する情報を含んでもよい。たとえば、動的特性は、犠牲者プロセッサおよび1つまたは複数の作業準備完了プロセッサに関連する様々な処理ユニットに関する電力消費、周波数、および/または温度に関する平均値、最小値、最大値、現在値、および/または予想値を含んでもよい。いくつかの実施形態では、動的特性を取得することは、上記で説明したように、式1(すなわち、Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi)において使用されるローカル係数(たとえば、fi、gi、hi)および/またはローカル測定値(たとえば、Tempi、Poweri、Freqi)に関する値を特定することを含んでもよい。
【００８４】
ブロック412において、マルチプロセッサコンピューティングデバイスは、取得されたデータに基づいて、犠牲者プロセッサおよび1つまたは複数の作業準備完了プロセッサに関する優先度を計算してもよい。たとえば、マルチプロセッサコンピューティングデバイスは、上記で説明したように、式1(すなわち、Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi)を使用して各々についての相対的優先度値を計算するために、犠牲者プロセッサおよび1つまたは複数の作業準備完了プロセッサの様々な処理ユニットに関連するグローバル係数、ローカル係数、およびローカル測定値に関する取得された値を使用してもよい。言い換えれば、マルチプロセッサコンピューティングデバイスは、犠牲者プロセッサおよび1つまたは複数の作業準備完了プロセッサの相対的優先度を計算するために、動作状態のデータ(たとえば、温度係数、電力消費係数、および周波数係数)をバランスさせてもよい。
【００８５】
決定ブロック414において、マルチプロセッサコンピューティングデバイスは、2つ以上の作業準備完了プロセッサが犠牲者プロセッサから作業項目を受け取るために競合しているかどうかを決定してもよい。たとえば、2つ以上の作業準備完了プロセッサが存在するとき、結果として生じる犠牲者プロセッサの作業項目に関する競合は、犠牲者プロセッサから作業項目を受け取ることができる勝利作業準備完了プロセッサの選択または決定を必要とする場合がある。
【００８６】
2つ以上の作業準備完了プロセッサが存在することを決定することに応答して(すなわち、決定ブロック414=「Yes」)、マルチプロセッサコンピューティングデバイスは、ブロック416において、計算された優先度値に基づいて、複数の作業準備完了プロセッサの中から勝利作業準備完了プロセッサを識別してもよい。たとえば、マルチプロセッサコンピューティングデバイスは、最も高い値(すなわち、最も高い優先度)を見出すために、計算された相対的優先度値を単純に比較してもよい。計算された特性を用いて勝利作業準備完了プロセッサを決定することは、ランダム性またはタイミング(たとえば、複数の作業準備完了プロセッサが盗む準備ができるようになる時間)に依存しなくてもよい。代わりに、勝利作業準備完了プロセッサは、システムの様々な動作状況を与えられた作業項目を処理するプロセッサの能力に基づいて決定されてもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、第1の勝利作業準備完了処理ユニットおよび第2の勝利作業準備完了処理ユニットなどの、2つ以上の勝利作業準備完了プロセッサを識別してもよい。犠牲者プロセッサが盗むために利用可能な多数の作業項目を有するとき、作業準備完了プロセッサの計算された優先度が互いの特定のしきい値内にあるとき、および/または所与の時間において作業項目の複数の受取先を可能にする他の要因のとき、複数の勝利作業準備完了プロセッサが可能であってもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、優先度に比例して作業項目を割り当てることができる説明した式5〜式6を使用することなどによって、勝利作業準備完了プロセッサに対する割り振りの割合を決定してもよい。
【００８７】
1つの作業準備完了プロセッサが存在することを決定することに応答して(すなわち、決定ブロック414=「No」)、またはブロック416において識別動作を実行することに応答して、マルチプロセッサコンピューティングデバイスは、ブロック418において、犠牲者プロセッサおよび勝利作業準備完了プロセッサ(または唯一の作業準備完了プロセッサ)の計算された優先度に基づいて、勝利作業準備完了プロセッサ(または唯一の作業準備完了プロセッサ)に転送する作業項目の数を計算してもよい。たとえば、犠牲者プロセッサが盗まれるために利用可能な複数の作業項目を有するとき、マルチプロセッサコンピューティングデバイスは、犠牲者処理ユニットによる実行のために残っている可能性がある複数の作業項目の第1の数と、作業準備完了プロセッサに転送され得る作業項目の第2の数とを決定してもよい。いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、上記で説明したように、式5〜式6を使用して、勝利作業準備完了プロセッサに転送される作業項目の数を計算してもよい。
【００８８】
ブロック420において、マルチプロセッサコンピューティングデバイスは、犠牲者プロセッサから勝利作業準備完了プロセッサ(または唯一の作業準備完了プロセッサ)に計算された数の作業項目を再割り当てしてもよい。たとえば、マルチプロセッサコンピューティングデバイスは、犠牲者プロセッサのタスク待ち行列から勝利作業準備完了処理ユニットのタスク待ち行列に1つまたは複数の作業項目および/または関連するデータを転送してもよい。別の例として、マルチプロセッサコンピューティングデバイスは、以前に犠牲者プロセッサに割り当てられた共有メモリ内の作業項目がここで勝利作業準備完了プロセッサに割り当てられることを示すために、勝利作業準備完了プロセッサが共有ワークスティーリングデータ構造内のデータを調整することを可能にしてもよい。いくつかの実施形態では、タスク待ち行列間の作業項目の再割当ては、共有メモリユニットに対するチェックアウトまたは割当て手順などを介する、待ち行列間のデータ転送および/または特定のデータへのアクセスの割当てを含んでもよい。
【００８９】
マルチプロセッサコンピューティングデバイスは、決定ブロック402において犠牲者プロセッサから盗まれるために使用可能な任意の作業項目が存在するかどうかを決定することに再び戻る、連続的または周期的ループにおいて方法400の動作を実行してもよい。各反復では、作業準備完了であるプロセッサユニットおよび犠牲者プロセッサは、各処理ユニットの作業負荷が時間とともに変化するにつれて変化する場合がある。したがって、ある時間における作業準備完了処理ユニットは、その作業項目の待ち行列が増加するにつれて、後に犠牲者プロセッサになる場合がある。
【００９０】
説明したように、実施形態の方法は、様々なワークスティーリングおよび/またはデータ並列フレームワークにおいて実施されてもよい。たとえば、割り当てられた作業項目を管理するためにタスク待ち行列を利用し、および/または共有メモリにアクセスする処理ユニットのために、実施形態の優先度計算が利用されてもよい。図4Bは、共有メモリおよび共有ワークスティーリングデータ構造の実装形態を利用するマルチプロセッサコンピューティングデバイスのための動作を含む実施形態の方法450を示す。
【００９１】
方法450のいくつかの動作は、方法400と同様であってもよく、マルチプロセッサコンピューティングデバイスの各処理ユニットに対して実行されてもよい。たとえば、ブロック402、406〜418の動作は、図4Aを参照して上記で説明した同じ番号付けされたブロックの動作と同様であってもよい。さらに、いくつかの実施形態では、マルチプロセッサコンピューティングデバイスは、各処理ユニットのタスクに関するワークスティーリングを処理するために、方法450の1つまたは複数のインスタンス(たとえば、方法400を実行するための1つまたは複数のスレッド)を同時に実行してもよい。いくつかの実施形態では、方法450の様々な動作は、(たとえば、図1〜図2Dのマルチプロセッサコンピューティングデバイス101のCPU102などのアプリケーションプロセッサを介して)マルチプロセッサコンピューティングデバイスの処理ユニットにおいて実行される実行時機能(たとえば、図2A〜図2Dの実行時機能モジュール210)によって実行されてもよい。
【００９２】
一般に、タスク(または関連する処理ユニット)が共有タスク/作業負荷の元々割り当てられた作業項目を完了することによって自由になったときはいつも、その処理ユニット(作業準備完了プロセッサ)は、共有ワークスティーリングデータ構造を更新することによって、作業項目を盗むことを競ってもよい。犠牲者プロセッサは、そのようなアクセス/修正プロセスの一部として、ワークスティーリングデータ構造から特定されてもよい。様々な実施形態では、複数の作業準備完了処理ユニットによる共有データ構造への同時アクセスを扱うために、確率的ロック(またはアトミック)が使用されてもよい。
【００９３】
図4Bを参照すると、決定ブロック414(すなわち、決定ブロック414=「No」)またはブロック416の動作を実行することに応答して、マルチプロセッサコンピューティングデバイスは、ブロック452において、勝利プロセッサを介して、勝利作業準備完了プロセッサの計算された優先度値に基づいて、共有データ構造に対する確率的ロックの制御を獲得してもよい。ブロック454において、マルチプロセッサは、勝利プロセッサを介して、確率的ロックの制御を獲得することに応答して、勝利作業準備完了プロセッサに転送される作業項目の数を示すように共有データ構造を更新してもよい。
【００９４】
ブロック456において、マルチプロセッサは、勝利プロセッサを介して、確率的ロックの制御を解除し、したがって、他の処理ユニットによって潜在的にアクセスされるワークスティーリングデータ構造を解放してもよい。マルチプロセッサコンピューティングデバイスは、次いで、決定ブロック402における決定動作を続けてもよい。
【００９５】
パーソナルコンピュータ、モバイルデバイス、およびラップトップコンピュータを含む様々な形態のコンピューティングデバイスが、様々な実施形態を実装するために使用されてもよい。そのようなコンピューティングデバイスは、典型的には、例示的なマルチプロセッサモバイルデバイス500を示す図5に示す構成要素を含んでもよい。様々な実施形態では、モバイルデバイス500は、タッチスクリーンコントローラ504および内部メモリ502に結合されたプロセッサ501を含み得る。プロセッサ501は、一般的なまたは特定の処理タスクのために設計された複数のマルチコアICを含んでもよい。いくつかの実施形態では、他の処理ユニット(たとえば、GPU、DSPなど)もプロセッサ501に含まれ結合されてもよい。
【００９６】
内部メモリ502は、揮発性および/または不揮発性メモリであってもよく、セキュアおよび/もしくは暗号化メモリ、または非セキュアおよび/もしくは非暗号化メモリ、またはそれらの任意の組合せであってもよい。タッチスクリーンコントローラ504およびプロセッサ501はまた、抵抗感知タッチスクリーン、静電容量感知タッチスクリーン、赤外線感知タッチスクリーンなどのタッチスクリーンパネル512に結合されてもよい。モバイルデバイス500は、互いに結合され、かつ/またはプロセッサ501に結合された、送受信のための、1つまたは複数の無線信号トランシーバ508(たとえば、Bluetooth(登録商標)、ZigBee(登録商標)、Wi-Fi(登録商標)、RF無線)、およびアンテナ510を有し得る。トランシーバ508およびアンテナ510は、様々なワイヤレス送信プロトコルスタックおよびインターフェースを実装するために、上述した回路とともに使用され得る。モバイルデバイス500は、セルラーネットワークを介する通信を可能にし、プロセッサ501に結合されたセルラーネットワークワイヤレスモデムチップ516を含んでもよい。モバイルデバイス500は、プロセッサ501に結合された周辺デバイス接続インターフェース518を含んでもよい。周辺デバイス接続インターフェース518は、1つのタイプの接続を受け入れるように単独で構成されてもよく、または、USB、FireWire、Thunderbolt、またはPCIeなどの、一般的なまたは独自仕様の様々なタイプの物理的接続および通信接続を受け入れるように多様に構成されてもよい。周辺デバイス接続インターフェース518はまた、同様に構成された周辺デバイス接続ポート(図示せず)に結合されてもよい。また、モバイルデバイス500は、音声出力を提供するためのスピーカー514を含むことも可能である。モバイルデバイス500はまた、本明細書で論じる構成要素のすべてまたは一部を収容するための、プラスチック、金属、または材料の組合せで構成されたハウジング520を含んでもよい。モバイルデバイス500は、使い捨てまたは充電可能なバッテリーなどの、プロセッサ501に結合された電源522を含む場合もある。充電可能なバッテリーはまた、モバイルデバイス500の外部のソースから充電電流を受けるために、周辺デバイス接続ポートに結合されてもよい。
【００９７】
本明細書で説明する様々なプロセッサ(または処理ユニット)は、本明細書で説明する様々な実施形態の機能を含む様々な機能を実行するようにソフトウェア命令(アプリケーション)によって構成され得る任意のプログラム可能なマイクロプロセッサ、マイクロコンピュータ、または複数のプロセッサチップであってもよい。様々なデバイスでは、ワイヤレス通信機能専用の1つのプロセッサおよび他のアプリケーションを実行する専用の1つのプロセッサなどの、複数のプロセッサが設けられてもよい。典型的には、ソフトウェアアプリケーションは、それらがアクセスされてプロサッサにロードされる前に、内部メモリ内に記憶されてもよい。プロセッサは、アプリケーションソフトウェア命令を記憶するのに十分な内部メモリを含み得る。多くのデバイスにおいて、内部メモリは、揮発性メモリ、またはフラッシュメモリなどの不揮発性メモリ、または両方の混合物であってもよい。この説明の目的のために、メモリへの一般的な言及は、内部メモリ、または様々なデバイスに差し込まれたリムーバブルメモリと、プロセッサ内のメモリとを含む、プロセッサによってアクセス可能なメモリを指す。
【００９８】
前述の方法の説明およびプロセスフロー図は、単に例示的な例として提供され、様々な実施形態の動作が提示された順序で実行されなければならないことを必要とするまたは暗示することを意図していない。当業者によって理解されるように、前述の実施形態における動作の順序は、任意の順序で実行されてもよい。「その後」、「次いで」、「次に」などの単語は、動作の順序を限定するものではなく、これらの単語は単に、方法の説明を通じて読者を導くために使用される。さらに、たとえば、冠詞「a」、「an」、または「the」を使用する単数形でのクレーム要素へのいかなる参照も、要素を単数形に限定するものとして解釈すべきではない。
【００９９】
本明細書で開示する実施形態に関連して説明した様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズム動作は、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装されてもよい。ハードウェアおよびソフトウェアのこの互換性を明確に説明するために、様々な例示的な構成要素、ブロック、モジュール、回路、および動作について、上記でそれらの機能性の点で一般的に説明してきた。そのような機能性がハードウェアまたはソフトウェアのどちらとして実装されるのかは、特定のアプリケーションと、システム全体に課される設計制約とに依存する。当業者は、説明した機能性を、特定のアプリケーションごとに様々な方法で実装してもよいが、そのような実装の決定は、本特許請求の範囲からの逸脱を引き起こすものとして解釈されるべきではない。
【０１００】
本明細書で開示する実施形態に関連して説明した様々な例示的なロジック、論理ブロック、モジュール、および回路を実装するために使用されるハードウェアは、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラム可能な論理デバイス、ディスクリートゲートもしくはトランジスタロジック、ディスクリートハードウェア構成要素、または、本明細書で説明した機能を実行するように設計されたそれらの任意の組合せを用いて実装または実行され得る。汎用プロセッサは、マイクロプロセッサであり得るが、代替において、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であり得る。プロセッサはまた、コンピューティングデバイスの組合せ、たとえば、DPSおよびマイクロプロセッサの組合せ、複数のマイクロプロセッサ、DSPコアと組み合わせた1つまたは複数のマイクロプロセッサ、または任意の他のそのような構成として実装され得る。代替的には、いくつかの動作または方法は、所与の機能に特有の回路によって実行されてもよい。
【０１０１】
1つまたは複数の例示的な実施形態では、説明した機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せにおいて実装され得る。ソフトウェアにおいて実装される場合、機能は、1つまたは複数の命令またはコードとして、非一時的なハードウェア可読、コンピュータ可読、もしくはサーバ可読の媒体、または非一時的プロセッサ可読記憶媒体上に記憶され得、またはそれを介して送信され得る。本明細書で開示する方法またはアルゴリズムの動作は、非一時的コンピュータ可読記憶媒体、非一時的サーバ可読記憶媒体、および/または非一時的プロセッサ可読記憶媒体内に存在し得るプロセッサ実行可能ソフトウェアモジュール、またはプロセッサ実行可能ソフトウェア命令において具体化され得る。様々な実施形態では、そのような命令は、記憶されたプロセッサ実行可能命令または記憶されたプロセッサ実行可能ソフトウェア命令であり得る。有形の非一時的コンピュータ可読記憶媒体は、コンピュータによってアクセスされ得る任意の利用可能な媒体であり得る。例として、限定はしないが、そのような非一時的コンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気データ記憶デバイス、または、命令もしくはデータ構造の液体で所望のプログラムコードを記憶するために使用され得、コンピュータによってアクセスされ得る任意の他の媒体を備えてもよい。ディスク(disk)およびディスク(disc)は、本明細書で使用されるとき、コンパクトディスク(CD)、レーザディスク、光ディスク、デジタル多用途ディスク(DVD)、フロッピーディスク、およびBlu-rayディスク(登録商標)を含み、ここで、ディスク(disk)は通常、データを磁気的に再生し、ディスク(disc)は、データを、レーザを用いて光学的に再生する。上記の組合せも、非一時的コンピュータ可読媒体の範囲内に含まれるべきである。加えて、方法またはアルゴリズムの動作は、コンピュータプログラム製品に組み込まれ得る、有形の非一時的プロセッサ可読記憶媒体および/またはコンピュータ可読媒体上に、コードおよび/または命令の1つまたは任意の組合せもしくはセットとして存在し得る。
【０１０２】
開示された実施形態の前述の説明は、当業者が特許請求の範囲の実施形態の技法を製作または使用することを可能にするために提供される。これらの実施形態に対する様々な変更は、当業者には容易に明らかであり、本明細書で定義される一般的な原理は、特許請求の範囲から逸脱することなく、他の実施形態に適用され得る。したがって、本開示は、本明細書において示される実施形態に限定されるものではなく、以下の特許請求の範囲ならびに本明細書において開示された原理および新規の特徴に一致する最大の範囲を与えられるものである。
【符号の説明】
【０１０３】
100  図
101  異種マルチプロセッサコンピューティングデバイス
102  第1のCPU、処理ユニット
112  第2のCPU、処理ユニット
122  GPU、処理ユニット
132  DSP、処理ユニット
150  メインスレッド
166  タスク待ち行列
168  タスク待ち行列
170  待ち行列、タスク待ち行列
172  待ち行列、タスク待ち行列
174  待ち行列、タスク待ち行列
176  タスク待ち行列、待ち行列
178  待ち行列、タスク待ち行列
180  待ち行列、タスク待ち行列
200  図
210  実行時機能モジュール
220a  第1のタスク待ち行列
220b  第2のタスク待ち行列
220c  第3のタスク待ち行列
220d  第4のタスク待ち行列
230a  作業項目
230a'  作業項目
230a"  作業項目
230d  作業項目
240a  第1の作業準備完了プロセッサ待ち行列
240b  第2の作業準備完了プロセッサ待ち行列
240c  第3の作業準備完了プロセッサ待ち行列
240d  第4の作業準備完了プロセッサ待ち行列
242a  データ、識別データ
242d  識別データ
252a  データ、識別データ
252d  識別データ
260  図
270  図
280  図
301  マルチプロセッサコンピューティングデバイス
302  確率的ロック機構
304  ワークスティーリングデータ構造
306  共有メモリ
500  マルチプロセッサモバイルデバイス、モバイルデバイス
501  プロセッサ
502  内部メモリ
504  タッチスクリーンコントローラ
508  無線信号トランシーバ、トランシーバ
510  アンテナ
512  タッチスクリーンパネル
514  スピーカー
516  セルラーネットワークワイヤレスモデムチップ
518  周辺デバイス接続インターフェース
520  ハウジング
522  電源
【図１】
2018531450.tif 000003
【図２Ａ】
2018531450.tif 000004
【図２Ｂ】
2018531450.tif 000005
【図２Ｃ】
2018531450.tif 000006
【図２Ｄ】
2018531450.tif 000007
【図３】
2018531450.tif 000008
【図４Ａ】
2018531450.tif 000009
【図４Ｂ】
2018531450.tif 000010
【図５】
2018531450.tif 000011
【手続補正書】
【提出日】平成30年3月26日(2018.3.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
動作状態データに基づいてワークスティーリング決定を行うことによって複数の処理ユニット間で作業負荷を事前対処的にバランスさせる、マルチプロセッサコンピューティングデバイスのプロセッサによって実施される方法であって、
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得するステップと、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得するステップであって、前記取得される動的特性データが周波数に関連する値を含む、ステップと、
前記取得された静的特性データと前記取得された動的特性データとに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算するステップと、
前記計算された優先度値に基づいて、勝利作業準備完了プロセッサとして前記複数の処理ユニットの中からプロセッサを選択するステップと、
前記犠牲者プロセッサに割り当てられたいくつかの作業項目を前記勝利作業準備完了プロセッサに転送するステップと
を備える方法。
【請求項２】
前記作業準備完了プロセッサが、それぞれの割り当てられた作業項目を完了する前記作業準備完了プロセッサに応答して、前記犠牲者プロセッサから前記作業項目を盗む準備ができる、請求項1に記載の方法。
【請求項３】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データが、使用される技術、前記マルチプロセッサコンピューティングデバイスのトポロジ内の位置、および製造者データを示すいずれかのデータを含む、請求項1に記載の方法。
【請求項４】
前記静的特性データが、前記マルチプロセッサコンピューティングデバイスの製造時に、前記マルチプロセッサコンピューティングデバイスの各起動時に、定期的に、またはそれらの任意の組合せにおいて取得される、請求項1に記載の方法。
【請求項５】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のローカル測定値を含む、請求項1に記載の方法。
【請求項６】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、温度および電力消費に関連する値をさらに含む、請求項1に記載の方法。
【請求項７】
前記取得されたデータに基づいて前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための前記優先度値を計算するステップが、以下の式、
Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi
を使用して前記優先度値を計算するステップを備え、
iが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのためのインデックスを表し、Piが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのための前記インデックスに関連付けられた処理ユニットのための計算された優先度値を表し、αiが、温度に関するグローバル係数を表し、fiが、前記処理ユニットに関する前記温度についてのローカル係数を表し、Tempiが、前記処理ユニットに関するローカル温度測定値に対する式を表し、βiが、電力消費に関するグローバル係数を表し、giが、前記処理ユニットに関する前記電力消費についてのローカル係数を表し、Poweriが、前記処理ユニットに関するローカル電力消費測定値に対する式を表し、γiが、周波数に関するグローバル係数を表し、hiが、前記処理ユニットの前記周波数に関するローカル係数を表し、Freqiが、前記処理ユニットに関するローカル周波数測定値に対する式を表す、請求項1に記載の方法。
【請求項８】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データを取得するステップが、前記温度に関するグローバル係数と、前記電力消費に関するグローバル係数と、前記周波数に関するグローバル係数とを取得するステップを備える、請求項7に記載の方法。
【請求項９】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得するステップが、前記処理ユニットに関する前記温度についての前記ローカル係数と、前記処理ユニットに関する前記ローカル温度測定値と、前記処理ユニットに関する前記電力消費についての前記ローカル係数と、前記処理ユニットに関する前記ローカル電力消費測定値と、前記処理ユニットに関する前記周波数についての前記ローカル係数と、前記処理ユニットに関する前記ローカル周波数測定値とを取得するステップを備える、請求項7に記載の方法。
【請求項１０】
前記犠牲者プロセッサおよび前記勝利作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する作業項目の数を計算するステップをさらに備える、請求項1に記載の方法。
【請求項１１】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を計算するステップが、以下の式、
Ni=K*(Pi/(Pi+Pj))
Nj=K-Ni
を使用して、転送する前記作業項目の数を計算するステップを備え、
iが、前記犠牲者プロセッサに関連する第1のタスクインデックスを表し、jが、前記勝利作業準備完了プロセッサに関連する第2のタスクインデックスを表し、Kが、盗む前に前記犠牲者プロセッサによって処理されるために残っている作業項目の総数を表し、Pjが、前記犠牲者プロセッサの計算された優先度値を表し、Piが、前記勝利作業準備完了プロセッサの前記計算された優先度値を表し、Niが、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を表し、Njが、前記犠牲者プロセッサに残る作業項目の数を表す、請求項10に記載の方法。
【請求項１２】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々が、前記複数の処理ユニット内の異なる処理ユニットに関連付けられる、請求項1に記載の方法。
【請求項１３】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々が、前記複数の処理ユニットのうちの1つにおいて実行されるそれぞれの異なるタスクに関連付けられる、請求項1に記載の方法。
【請求項１４】
前記作業項目が、並列ループルーチンの異なる反復である、請求項1に記載の方法。
【請求項１５】
前記複数の処理ユニットが、2つ以上の第1の中央処理装置(CPU)と、グラフィックス処理ユニット(GPU)と、デジタル信号プロセッサ(DSP)とを含む、請求項1に記載の方法。
【請求項１６】
前記マルチプロセッサコンピューティングデバイスが、異種マルチコアコンピューティングデバイス、同種マルチコアコンピューティングデバイス、分散コンピューティングサーバのうちの1つである、請求項1に記載の方法。
【請求項１７】
前記勝利作業準備完了プロセッサを介して、前記勝利作業準備完了プロセッサの計算された優先度値に基づいて、共有データ構造のための確率的ロックの制御を獲得するステップと、
前記勝利作業準備完了プロセッサを介して、前記確率的ロックの制御を獲得することに応答して、前記勝利作業準備完了プロセッサに転送される作業項目の数を示すために、前記共有データ構造を更新するステップと
をさらに備える、請求項1に記載の方法。
【請求項１８】
メモリと、
複数の処理ユニットのプロセッサと
を備えるコンピューティングデバイスであって、前記プロセッサが、前記メモリに結合され、
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得することと、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得することであって、前記取得される動的特性データが周波数に関連する値を含む、取得することと、
前記取得された静的特性データと前記取得された動的特性データとに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算することと、
前記計算された優先度値に基づいて、勝利作業準備完了プロセッサとして前記複数の処理ユニットの中からプロセッサを選択することと、
前記犠牲者プロセッサに割り当てられたいくつかの作業項目を前記勝利作業準備完了プロセッサに転送することと
を備える動作を実行するようにプロセッサ実行可能命令を用いて構成される、コンピューティングデバイス。
【請求項１９】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データが、使用される技術、前記コンピューティングデバイスのトポロジ内の位置、および製造者データを示すいずれかのデータを含む、請求項18に記載のコンピューティングデバイス。
【請求項２０】
前記静的特性データが、前記コンピューティングデバイスの製造時に、前記コンピューティングデバイスの各起動時に、定期的に、またはそれらの任意の組合せにおいて取得される、請求項18に記載のコンピューティングデバイス。
【請求項２１】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のローカル測定値を含む、請求項18に記載のコンピューティングデバイス。
【請求項２２】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記動的特性データが、温度および電力消費に関連する値をさらに含む、請求項18に記載のコンピューティングデバイス。
【請求項２３】
前記取得されたデータに基づいて前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための前記優先度値を計算することが、以下の式、
Pi=αi*fi*Tempi+βi*gi*Poweri+γi*hi*Freqi
を使用して前記優先度値を計算することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成され、
iが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのためのインデックスを表し、Piが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサのうちの1つのための前記インデックスに関連付けられた処理ユニットのための計算された優先度値を表し、αiが、温度に関するグローバル係数を表し、fiが、前記処理ユニットに関する前記温度についてのローカル係数を表し、Tempiが、前記処理ユニットに関するローカル温度測定値に対する式を表し、βiが、電力消費に関するグローバル係数を表し、giが、前記処理ユニットに関する前記電力消費についてのローカル係数を表し、Poweriが、前記処理ユニットに関するローカル電力消費測定値に対する式を表し、γiが、周波数に関するグローバル係数を表し、hiが、前記処理ユニットの前記周波数に関するローカル係数を表し、Freqiが、前記処理ユニットに関するローカル周波数測定値に対する式を表す、請求項18に記載のコンピューティングデバイス。
【請求項２４】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する前記静的特性データを取得することが、前記温度に関するグローバル係数と、前記電力消費に関するグローバル係数と、前記周波数に関するグローバル係数とを取得することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項23に記載のコンピューティングデバイス。
【請求項２５】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得することが、前記処理ユニットに関する前記温度についての前記ローカル係数と、前記処理ユニットに関する前記ローカル温度測定値と、前記処理ユニットに関する前記電力消費についての前記ローカル係数と、前記処理ユニットに関する前記ローカル電力消費測定値と、前記処理ユニットに関する前記周波数についての前記ローカル係数と、前記処理ユニットに関する前記ローカル周波数測定値とを取得することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項23に記載のコンピューティングデバイス。
【請求項２６】
前記プロセッサが、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する作業項目の数を計算することをさらに備える動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項18に記載のコンピューティングデバイス。
【請求項２７】
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの前記計算された優先度値に基づいて、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を計算することが、以下の式、
Ni=K*(Pi/(Pi+Pj))
Nj=K-Ni
を使用して、転送する前記作業項目の数を計算することを備えるように、前記プロセッサが動作を実行するようにプロセッサ実行可能命令を用いて構成され、
iが、前記犠牲者プロセッサに関連する第1のタスクインデックスを表し、jが、前記勝利作業準備完了プロセッサに関連する第2のタスクインデックスを表し、Kが、盗む前に前記犠牲者プロセッサによって処理されるために残っている作業項目の総数を表し、Pjが、前記犠牲者プロセッサの計算された優先度値を表し、Piが、前記勝利作業準備完了プロセッサの前記計算された優先度値を表し、Niが、前記勝利作業準備完了プロセッサに転送する前記作業項目の数を表し、Njが、前記犠牲者プロセッサに残る作業項目の数を表す、請求項26に記載のコンピューティングデバイス。
【請求項２８】
前記プロセッサが、
前記勝利作業準備完了プロセッサを介して、前記勝利作業準備完了プロセッサの計算された優先度値に基づいて、共有データ構造のための確率的ロックの制御を獲得することと、
前記勝利作業準備完了プロセッサを介して、前記確率的ロックの制御を獲得することに応答して、前記勝利作業準備完了プロセッサに転送される作業項目の数を示すために、前記共有データ構造を更新することと
をさらに備える動作を実行するようにプロセッサ実行可能命令を用いて構成される、請求項18に記載のコンピューティングデバイス。
【請求項２９】
コンピューティングデバイスの複数の処理ユニットのプロセッサに、
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得することと、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得することであって、前記取得される動的特性データが周波数に関連する値を含む、取得することと、
前記取得された静的特性データと前記取得された動的特性データとに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算することと、
前記計算された優先度値に基づいて、勝利作業準備完了プロセッサとして前記複数の処理ユニットの中からプロセッサを選択することと、
前記犠牲者プロセッサに割り当てられたいくつかの作業項目を前記勝利作業準備完了プロセッサに転送することと
を備える動作を実行させるように構成されたプロセッサ実行可能命令が記憶された非一時的プロセッサ可読記憶媒体。
【請求項３０】
犠牲者プロセッサおよび前記犠牲者プロセッサから作業項目を盗む準備ができている複数の処理ユニット(作業準備完了プロセッサ)のうちの1つまたは複数の各々に関連する静的特性データを取得するための手段と、
前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々に関連する動的特性データを取得するための手段であって、前記取得される動的特性データが周波数に関連する値を含む、手段と、
前記取得された静的特性データと前記取得された動的特性データとに基づいて、前記犠牲者プロセッサおよび前記作業準備完了プロセッサの各々のための優先度値を計算するための手段と、
前記計算された優先度値に基づいて、勝利作業準備完了プロセッサとして前記複数の処理ユニットの中からプロセッサを選択するための手段と、
前記犠牲者プロセッサに割り当てられたいくつかの作業項目を前記勝利作業準備完了プロセッサに転送するための手段と
を備えるコンピューティングデバイス。
【国際調査報告】
2018531450.tif 000012
2018531450.tif 000013
2018531450.tif 000014