(57)【要約】      （修正有）【課題】コンピューティングプラットフォーム上のタスクの実行をスケジューリングし、編成する方法を提供する。【解決手段】臨界時間区間を連続的に識別すること、および識別された臨界時間区間の各々に対するタスク実行をスケジューリングし、編成することを含む。実行されるタスクは、それらの実行完了期限に部分的に基づいて実行されるようにスケジューリングされる。タスクの編成は、プラットフォームの凸エネルギー速度包絡線にある複数の動作速度を用いてプラットフォームの仮想動作モードを選択することを含む。動作モードを切替えることによるタスク内遅延を考慮する。【選択図】図１
2010250802.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティングデバイスが目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成する方法であって、各タスクは出現時間および実行完了期限を有しており、前記目標のコンピューティングプラットフォームは各動作モードが動作速度およびエネルギー消費量を有する複数の動作モードを有しており、前記方法は、
タスク出現時間およびタスク実行完了期限によって規定される臨界時間区間を決定することであって、前記決定することは１つ以上の実行可能な時間区間に対する前記目標のコンピューティングプラットフォームの平均動作速度の１つ以上のそれぞれの下限に少なくとも部分的に基づき、特定の実行可能な時間区間に対する前記目標のコンピューティングプラットフォームの平均動作速度は、前記特定の実行可能な時間区間中に１つ以上の実行されるタスクの実行を完了するために前記特定の実行可能な時間中に必要とされる前記目標のコンピューティングプラットフォームの前記平均動作速度に対応し、前記臨界時間区間は前記１つ以上のそれぞれの下限のうちの最も大きいものを有する、ことと、
前記１つ以上のタスクの前記実行完了期限に従って前記臨界時間区間中の前記１つ以上の実行されるタスクをスケジューリングおよび／または編成することであって、前記臨界時間区間中に実行のための２つより多いタスクがスケジューリングされている場合、より早い実行完了期限を有するタスクが後の実行完了期限を有するタスクの前に実行のためにスケジューリングされている、ことと
を含む、方法。
【請求項２】
１つ以上のスケジューリングおよび／または編成される残りのタスクがあるか否かを決定することをさらに含む請求項１に記載の方法であって、１つ以上のスケジューリングおよび／または編成される残りのタスクがある場合、
前記１つ以上の実行可能な時間区間から前記臨界時間区間を論理的に除去することと、
前記１つ以上の実行可能な時間区間からの前記決定された臨界時間区間の前記論理的除去を反映させるために前記１つ以上のスケジューリングおよび／または編成される残りのタスクの前記出現時間および前記実行完了期限を更新することと、
除去されていない実行可能な時間区間のうちの１つを新しい臨界時間区間として決定し、前記新しい臨界時間区間中の１つ以上の実行されるタスクの実行をスケジューリングおよび／または編成するために前記決定すること並びに前記スケジューリングおよび／または編成することを繰り返すことと
を行う、請求項１に記載の方法。
【請求項３】
１つ以上のスケジューリングおよび／または編成される残りのタスクがあるか否かを決定することをさらに含む請求項２に記載の方法であって、１つ以上のスケジューリングおよび／または編成される残りのタスクがある場合、
全てのタスクがスケジューリングおよび／または編成されるまで前記１つ以上のスケジューリングおよび／または編成される残りのタスクをスケジューリングおよび／または編成するために前記論理的除去すること、前記更新すること、および前記決定すること並びに前記スケジューリングおよび／または編成することを繰り返すことを１回以上繰り返すことを行う、請求項２に記載の方法。
【請求項４】
前記１つ以上の実行可能な区間の前記平均動作速度の前記１つ以上のそれぞれの下限の各々を決定することをさらに含む、請求項１に記載の方法。
【請求項５】
前記スケジューリングおよび／または編成することは、動作モードを切替えることによるタスク内遅延に少なくとも部分的に基づいて前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの動作モードを選択することを含む、請求項１に記載の方法。
【請求項６】
前記スケジューリングおよび／または編成することは、動作モードを切替えることによるタスク内遅延に少なくとも部分的に基づいて前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの仮想動作モードを選択することを含んでおり、前記仮想動作モードは前記目標のコンピューティングプラットフォームの少なくとも２つのそれぞれの動作モードで前記臨界時間区間の少なくとも２つの部分を動作することによって効果的に形成される、請求項１に記載の方法。
【請求項７】
前記仮想動作モードを選択することは、前記臨界時間区間の前記少なくとも２つのそれぞれの部分に対して前記目標のコンピューティングプラットフォームの前記少なくとも２つの動作モードを選択することを含み、前記２つのそれぞれの動作モードは前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線にある、請求項６に記載の方法。
【請求項８】
前記コンピューティングデバイスは前記目標のコンピューティングプラットフォームを含む、請求項１に記載の方法。
【請求項９】
目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成する装置であって、各タスクは出現時間および実行完了期限を有しており、前記目標のコンピューティングプラットフォームは各動作モードが動作速度およびエネルギー消費量を有する複数の動作モードを有しており、前記装置は、
プロセッサと、
前記プロセッサに結合された記憶媒体であって、前記プロセッサによって実行されるように構成された複数のプログラミング命令が前記記憶媒体に記憶されており、前記プロセッサによって実行された場合、前記プログラミング命令は、
タスク出現時間およびタスク実行完了期限によって規定された臨界時間区間を決定することであって、前記決定することは１つ以上の実行可能な時間区間に対する前記目標のコンピューティングプラットフォームの平均動作速度の１つ以上のそれぞれの下限に少なくとも部分的に基づき、特定の実行可能な時間区間に対する前記目標のコンピューティングプラットフォームの平均動作速度は、前記特定の実行可能な時間区間中に実行されるタスクの実行を完了するために前記特定の実行可能な時間中に必要とされる前記目標のコンピューティングプラットフォームの前記平均動作速度に対応し、前記臨界時間区間は前記１つ以上のそれぞれの下限のうちの最も大きいものを有する、ことと、
前記タスクの前記実行完了期限に従って前記臨界時間区間中の前記実行されるタスクをスケジューリングおよび／または編成することであって、１つより多いスケジューリングされるタスクがある場合、より早い実行完了期限を有するタスクが後の実行完了期限を有するタスクの前に実行のためにスケジューリングされている、ことと
を前記装置にさせる、記憶媒体と
を含む、装置。
【請求項１０】
請求項９に記載の装置であって、実行された場合、前記プログラミング命令は、１つ以上のスケジューリングおよび／または編成される残りのタスクがあるか否かを決定することをさらに前記装置にさせ、１つ以上のスケジューリングおよび／または編成される残りのタスクがある場合、
前記１つ以上の実行可能な時間区間から前記臨界時間区間を論理的に除去することと、
前記１つ以上の実行可能な時間区間からの前記決定された臨界時間区間の前記論理的除去を反映させるために前記１つ以上のスケジューリングおよび／または編成される残りのタスクの前記出現時間および前記実行完了期限を更新することと、
除去されていない実行可能な時間区間のうちの１つを新しい臨界時間区間として決定し、前記新しい臨界時間区間中の実行されるタスクの実行をスケジューリングおよび／または編成するために前記決定すること並びに前記スケジューリングおよび／または編成することを繰り返すことと
を行う、請求項９に記載の装置。
【請求項１１】
請求項１０に記載の装置であって、実行された場合、前記プログラミング命令は、１つ以上のまだスケジューリングおよび／または編成される残りのタスクがあるか否かを決定することをさらに前記装置にさせ、１つ以上のまだスケジューリングおよび／または編成される残りのタスクがある場合、
全てのタスクがスケジューリングおよび／または編成されるまで前記１つ以上のスケジューリングおよび／または編成される残りのタスクをスケジューリングおよび／または編成するために前記論理的除去すること、前記更新すること、および前記決定すること並びに前記スケジューリングおよび／または編成することを繰り返すことを１回以上繰り返すことを行う、請求項１０に記載の装置。
【請求項１２】
請求項９に記載の装置であって、実行された場合、前記プログラミング命令は、前記実行可能な区間の前記平均動作速度の前記１つ以上のそれぞれの下限の各々を決定することをさらに前記装置にさせる、請求項９に記載の装置。
【請求項１３】
請求項９に記載の装置であって、実行された場合、前記プログラミング命令は、前記スケジューリングおよび／または編成の一部として、動作モードを切替えることによるタスク内遅延に少なくとも部分的に基づいて前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの動作モードを選択することをさらに前記装置にさせる、請求項９に記載の装置。
【請求項１４】
請求項９に記載の装置であって、実行された場合、前記プログラミング命令は、前記スケジューリングおよび／または編成の一部として、動作モードを切替えることによるタスク内遅延に少なくとも部分的に基づいて前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの仮想動作モードを選択することをさらに前記装置にさせ、前記仮想動作モードは前記目標のコンピューティングプラットフォームの少なくとも２つのそれぞれの動作モードで前記臨界時間区間の少なくとも２つの部分を動作することによって効果的に形成される、請求項９に記載の装置。
【請求項１５】
請求項１４に記載の装置であって、実行された場合、前記プログラミング命令は、前記仮想動作モードの前記選択の一部として、前記臨界時間区間の前記少なくとも２つのそれぞれの部分に対して前記目標のコンピューティングプラットフォームの前記少なくとも２つの動作モードを選択することをさらに前記装置にさせ、前記２つのそれぞれの動作モードは前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線にある、請求項１４に記載の装置。
【請求項１６】
前記装置は前記目標のコンピューティングプラットフォームを含む、請求項９に記載の装置。
【請求項１７】
装置に目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成させる複数のプログラミング命令を前記装置に提供するための製造物品であって、前記プログラミング命令が前記装置のプロセッサによって実行された場合、前記物品は、
有形のコンピュータ読取可能媒体と、
前記有形のコンピュータ読取可能媒体に記憶された複数のプログラミング命令であって、装置に提供されて実行された場合、前記プログラミング命令は前記目標のコンピューティングプラットフォーム上の前記１つ以上のタスクの実行をスケジューリングおよび／または編成することを前記装置にさせ、各タスクは出現時間および実行完了期限を有しており、前記目標のコンピューティングプラットフォームは各動作モードが動作速度およびエネルギー消費量を有する複数の動作モードを有しており、前記装置は、
タスク出現時間およびタスク実行完了期限によって規定された臨界時間区間を決定することであって、前記決定することは１つ以上の実行可能な時間区間に対する前記目標のコンピューティングプラットフォームの平均動作速度の１つ以上のそれぞれの下限に少なくとも部分的に基づき、前記複数の実行可能な時間区間のうちの特定の１つに対する前記目標のコンピューティングプラットフォームの平均動作速度は、前記複数の実行可能な時間区間中に前記実行されるタスクの実行を完了するために前記複数の実行可能な時間のうちの特定の１つ中に必要とされる前記目標のコンピューティングプラットフォームの前記平均動作速度であり、前記臨界時間区間は前記１つ以上のそれぞれの下限のうちの最も大きなものを有する、ことと、
前記１つ以上のタスクの前記実行完了期限に従って前記臨界時間区間中の１つ以上の実行されるタスクをスケジューリングおよび／または編成することであって、１つより多いスケジューリングおよび／または編成されるタスクがある場合、より早い実行完了期限を有するタスクが後の実行完了期限を有するタスクの前に実行のためにスケジューリングおよび／または編成されている、こととによって前記実行をスケジューリングおよび／または編成する、複数のプログラミング命令と
を含む、物品。
【請求項１８】
請求項１７に記載の物品であって、前記プログラミング命令は、実行された場合、１つ以上のスケジューリングおよび／または編成される残りのタスクがあるか否かを決定することをさらに前記装置にさせ、１つ以上のスケジューリングおよび／または編成される残りのタスクがある場合、
前記１つ以上の実行可能な時間区間から前記臨界時間区間を論理的に除去することと、
前記１つ以上の実行可能な時間区間からの前記決定された臨界時間区間の前記論理的除去を反映させるために前記１つ以上のスケジューリングおよび／または編成される残りのタスクの前記出現時間および前記実行完了期限を更新することと、
除去されていない実行可能な時間区間のうちの１つを新しい臨界時間区間として決定し、前記新しい臨界時間区間中の１つ以上の実行されるタスクの実行をスケジューリングおよび／または編成するために前記決定すること並びに前記スケジューリングおよび／または編成することを繰り返すことと
を行う、請求項１７に記載の物品。
【請求項１９】
請求項１８に記載の製造物品であって、前記プログラミング命令は、実行された場合、１つ以上のスケジューリングおよび／または編成される残りのタスクがあるか否かを決定することをさらに前記装置にさせ、１つ以上のスケジューリングおよび／または編成される残りのタスクがある場合、
全てのタスクがスケジューリングおよび／または編成されるまで前記１つ以上のスケジューリングおよび／または編成される残りのタスクをスケジューリングおよび／または編成するために前記論理的除去すること、前記更新すること、および前記決定すること並びに前記スケジューリングおよび／または編成することを繰り返すことを１回以上繰り返すことを行う、請求項１８に記載の製造物品。
【請求項２０】
前記装置は前記目標のコンピューティングプラットフォームを含む、請求項１７に記載の物品。
【請求項２１】
コンピューティングデバイスが目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成する方法であって、前記目標のコンピューティングプラットフォームは各動作モードが動作速度を有する複数の動作モードを有しており、前記方法は、
１つ以上の臨界時間区間を連続的に識別することであって、各臨界時間区間は前記目標のコンピューティングプラットフォームの平均動作速度の下限を有し、臨界時間区間の前記目標のコンピューティングプラットフォームの前記平均動作速度は、前記臨界時間区間中に前記実行されるタスクを実行するために必要とされる前記目標のコンピューティングプラットフォームの前記平均動作速度であり、臨界時間区間の識別の各々は前記臨界時間区間の前記目標のコンピューティングプラットフォームの前記平均動作速度の前記下限に少なくとも部分的に基づいている、ことと、
各臨界時間区間が識別されるにつれて、前記臨界時間区間中の１つ以上の実行されるタスクの実行をスケジューリングおよび／または編成することと
を含む、方法。
【請求項２２】
各識別された臨界時間区間は、前記臨界時間区間の前記目標のコンピューティングプラットフォームの前記平均動作速度の前記下限が考慮される実行可能な区間の前記目標のコンピューティングプラットフォームの前記平均動作速度の全ての他の下限より大きいということに少なくとも部分的に基づいている、請求項２１に記載の方法。
【請求項２３】
目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成する装置であって、前記目標のコンピューティングプラットフォームは各動作モードが動作速度を有する複数の動作モードを有しており、前記装置は、
プロセッサと、
前記プロセッサに結合された記憶媒体であって、前記プロセッサによって実行されるように構成された複数のプログラミング命令が前記記憶媒体に記憶されており、実行された場合、前記プログラミング命令は、
１つ以上の臨界時間区間を連続的に識別することであって、各臨界時間区間は前記目標のコンピューティングプラットフォームの平均動作速度の下限を有し、前記臨界時間区間の前記目標のコンピューティングプラットフォームの前記平均動作速度は、前記臨界時間区間中の１つ以上の実行されるタスクを実行するために必要とされる前記目標のコンピューティングプラットフォームの前記平均動作速度であり、臨界時間区間の識別の各々は前記臨界時間区間の前記目標のコンピューティングプラットフォームの前記平均動作速度の前記下限に少なくとも部分的に基づいている、ことと、
各臨界時間区間が識別されるにつれて、前記臨界時間区間中の前記１つ以上の実行されるタスクの実行をスケジューリングおよび／または編成することと
を前記装置にさせる、記憶媒体と
を含む、装置。
【請求項２４】
請求項２３に記載の装置であって、前記プログラミング命令は、実行された場合、前記臨界時間区間の前記目標のコンピューティングプラットフォームの前記平均動作速度の前記下限が考慮される実行可能な区間の前記目標のコンピューティングプラットフォームの前記平均動作速度の全ての他の下限より大きいということに少なくとも部分的に基づいて臨界時間区間を識別することを前記装置にさせる、請求項２３に記載の装置。
【請求項２５】
コンピューティングデバイスが臨界時間区間中の目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成する方法であって、各タスクは出現時間および実行完了期限を有しており、前記目標のコンピューティングプラットフォームは異なる動作速度の複数の動作モードを有しており、前記臨界時間区間はタスク出現時間およびタスク実行完了期限によって規定されており、前記方法は、
前記タスクの前記実行完了期限に従って前記臨界時間区間中の１つ以上の実行されるタスクの実行をスケジューリングおよび／または編成することであって、１つより多いスケジューリングおよび／または編成されるタスクがある場合、より早い実行完了期限を有するタスクが後の実行完了期限を有するタスクの前に実行のためにスケジューリングおよび／または編成されている、ことと
動作モードを切替えることによるタスク内遅延に少なくとも部分的に基づいて前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの動作モードまたは仮想動作モードを選択することであって、前記仮想動作モードは複数の動作モードによって効果的に規定されている、ことと
を含む、方法。
【請求項２６】
前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの前記仮想動作モードを選択することは、前記臨界時間区間の前記少なくとも２つのそれぞれの部分に対して前記目標のコンピューティングプラットフォームの前記少なくとも２つの動作モードを選択することを含み、前記２つの動作モードは前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線にある、請求項２５に記載の方法。
【請求項２７】
前記目標のコンピューティングプラットフォームの前記凸エネルギー速度包絡線を生成することをさらに含む、請求項２６に記載の方法。
【請求項２８】
臨界時間区間中の目標のコンピューティングプラットフォーム上の１つ以上のタスクの実行をスケジューリングおよび／または編成する装置であって、各タスクは出現時間および実行完了期限を有しており、前記目標のコンピューティングプラットフォームは異なる動作速度を有する複数の動作モードを有しており、前記臨界時間区間はタスク出現時間およびタスク実行完了期限によって規定されており、前記装置は、
プロセッサと、
前記プロセッサに結合された記憶媒体であって、前記プロセッサによって実行されるように構成された複数のプログラミング命令が前記記憶媒体に記憶されており、実行された場合、前記プログラミング命令は、
前記１つ以上のタスクの前記実行完了期限に従って前記臨界時間区間中の１つ以上の実行されるタスクの実行をスケジューリングおよび／または編成することであって、１つより多いスケジューリングされるタスクがある場合、より早い実行完了期限を有するタスクが後の実行完了期限を有するタスクの前に実行のためにスケジューリングおよび／または編成されている、ことと
動作モードを切替えることによるタスク内遅延に少なくとも部分的に基づいて前記臨界時間区間に対する前記目標のコンピューティングプラットフォームの動作モードまたは仮想動作モードを選択することであって、前記仮想動作モードは複数の動作モードによって効果的に規定されている、ことと
を前記装置にさせる、記憶媒体と
を含む、装置。
【請求項２９】
前記プログラミング命令は、実行された場合、前記臨界時間区間の前記少なくとも２つのそれぞれの部分に対して前記目標のコンピューティングプラットフォームの前記少なくとも２つの動作モードを選択することによって前記仮想動作モードを選択することを前記装置にさせ、前記２つの動作モードは前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線にある、請求項２８に記載の装置。
【請求項３０】
前記プログラミング命令は、実行された場合、前記目標のコンピューティングプラットフォームの前記凸エネルギー速度包絡線を生成することをさらに前記装置にさせる、請求項２９に記載の装置。
【請求項３１】
コンピューティングデバイスが目標のコンピューティングプラットフォーム上のタスクの実行を編成する方法であって、前記目標のコンピューティングプラットフォームは異なる動作速度の複数の動作モードを有しており、前記方法は、
前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線を生成することであって、前記凸エネルギー速度包絡線は前記異なる動作モードのうちの選択されたものを含む、ことと、
タスクの実行を編成することであって、前記目標のコンピューティングプラットフォームの仮想動作モードを選択することを含んでおり、仮想動作モードは複数の動作モードによって効果的に規定され、選択することは前記目標のコンピューティングプラットフォームの前記少なくとも２つの動作モードを選択することを含み、前記２つの動作モードは前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線にある、ことと
を含む、方法。
【請求項３２】
前記凸エネルギー速度包絡線を生成することは、前記目標のコンピューティングプラットフォームの下限凸曲線関連のエネルギーおよび速度を生成することを含む、請求項３１に記載の方法。
【請求項３３】
目標のコンピューティングプラットフォーム上のタスクの実行を編成する装置であって、前記目標のコンピューティングプラットフォームは異なる動作速度を有する複数の動作モードを有しており、前記装置は、
プロセッサと、
前記プロセッサに結合された記憶媒体であって、前記プロセッサによって実行されるように構成された複数のプログラミング命令が前記記憶媒体に記憶されており、実行された場合、前記プログラミング命令は、
前記目標のコンピューティングプラットフォームの凸エネルギー速度包絡線を生成することであって、前記凸エネルギー速度包絡線は前記異なる動作モードのうちの選択されたものを含む、ことと、
タスクの実行を編成することであって、少なくとも２つの動作モードによって効果的に規定された前記目標のコンピューティングプラットフォームの仮想動作モードの選択を含んでおり、前記２つの動作モードは前記凸エネルギー速度包絡線にある、ことと
を前記装置にさせる、記憶媒体と
を含む、装置。
【請求項３４】
前記プログラミング命令は、実行された場合、前記目標のコンピューティングプラットフォームの下限凸曲線関連のエネルギーおよび速度を生成することによって前記凸エネルギー速度包絡線を生成することをさらに前記装置にさせる、請求項３３に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]  現代のポータブル電子および無線システムを今日の超大規模集積（ＶＬＳＩ）回路設計で設計することにおいて、エネルギー消費は最も重要なパラメータのうちの一つとしてよく認識されている。異なる抽出レベルにおける様々な低電力技術のうち、ダイナミック・ボルテージ・スケジューリング（ＤＶＳ）はシステム動作中の電力およびエネルギー消費を減らすためによく用いられる技術である。ＤＶＳの目的は、動作周波数および回路供給電圧を縮小することによって動的／静的電力消費を減らすことである。動的エネルギーの節約が適応ボディバイアスを介して供給電圧（Ｖｄｄ）および閾値電圧（Ｖｔ）を同時に変化させることによって達成することができることが立証されている。動的エネルギー減少を達成するためにＤＶＳ対応システム上のタスクスケジューリングを解決するためにいくつかの研究が行われた。例えば、ヒューリスティックス(heuristics)がマルチプロセッサにおける周期タスクのために提案されている。
【０００２】
[0002]  エネルギー消費に対する最新の研究では、漏れエネルギーがますます注目されている。技術的製造性の進歩によってデバイスのサイズが縮小し続けるにつれて、漏れエネルギー散逸がより一層重要になりつつある。７０ｎｍプロセスでは漏れ電力は動的電力より小さく、５０ｎｍプロセスでは漏れ電力と動的電力は同程度になる一方、３５ｎｍプロセスでは漏れ電力は動的電力より大きい。したがって、十年以内には漏れ電力はどのエネルギー消費考察においても中心的になるであろうことが多く予測されている。
【０００３】
[0003]  しかしながら、低電力研究は、従来、電力消費とプロセッサ速度との関係が凸状である電力モデルに注目してきた。凸性は、可変電圧戦略を用いてエネルギーが最小限にされた場合、多数の問題を有する。主な問題としては、エネルギー消費に対しては、一定のスピードで動作する実行プロセッサを用いてタスクを実行することが最適であるという仮定であり得る。しかしながら、いくつかの技術的集積回路、構造的動作システムおよびアプリケーション要素の組み合わせは、実行の速さ（つまり、１つの周期を完遂し動作を実行するために必要とされる時間の逆数）および一動作毎のエネルギー消費（ＥＳ）からのマッピングは非凸状であるシステムをさらに作り出している。非凸状のエネルギー速度モデルは、現在および未来のエネルギー感応性システムの幅広い範囲は独占するであろう。例えば、チップ上の異種のマルチプロセッサ・マルチコアシステムでは、異なるコアは異なるＥＳ機能を有し、プロセッサ速度と一動作ごとのエネルギーとの総合的関係は凸状ではない。同様に、漏れおよび動的エネルギーの合計はプロセッサ速度と凸関係を有していない。なぜならプロセッサ速度を上げるために閾値電圧が低下された場合に漏れ電流が増加するからである。新しい高帯域幅オンチップ相互接続技術、例えばナノワイヤ、ＲＦ、フォトニック結晶ベースの光相互接続、および熱管理を必要とするプラズモニクス通信ネットワークの組み入れは、非凸ＥＳ関係に対してさらに問題を有するであろう。命令レベル平行性および有効的速度も高い非凸および非継続機能を有する。したがって、ＤＶＳ問題に取り組むための従来のアプローチで想定される簡略化された凸エネルギーモデルはもはや効果的ではないことがある。
【０００４】
[0004]  エネルギー消費減少を達成するための非凸方法を発展させるための試みがなされた。二次方程式論電力モデルに対する離散電圧レベルの存在におけるＤＶＳ技術が提案された。しかしながら、これらの数々のアプローチは最適なものとして現れず複雑であり、実質的な計算を必要とすることが本開示は明らかにした。さらに、本開示は、電力消費を減少させるために供給電圧をスケーリングすることは回路遅延に対して、したがって動作周波数に対して副次的な影響を与えることと理解する。プロセッサの供給電圧を切り替える度に、変更は特定量の余分なエネルギーおよび時間を必要とする。したがって、本開示は、移行オーバーヘッドは考慮されるべきもう一つの重要な問題であるが、従来の電圧スケーリング技術では無視されていると特定している。
【０００５】
[0005]  主題は、本明細書の終結部において特定され、かつ明瞭にクレームされる。本開示の上述した特徴および他の特徴は、添付の図面を用いて説明される、以下の記載および添付の請求の範囲から、さらに明らかになるであろう。これらの図面は、単に本開示にかかるいくつかの実施形態を示すものであり、したがって本開示の範囲を限定するものとみなされるべきではないことを理解されたい。以下、本発明の開示を、添付の図面を用いてさらに具体的かつ詳細に説明する。様々な実施形態は、同様の参照符号が同様の構成要素を示す添付図面を参照して説明される。
【図面の簡単な説明】
【０００６】
【図１】図１は、様々な実施形態による、目標のコンピューティングプラットフォーム上のタスク実行をスケジューリングおよび／または編成する方法を示す。
【図２】図２ａ〜図２ｂは、様々な実施形態によって、プロセッサがどのように任意の仮想動作速度で動作できるかを示す。
【図３】図３は、様々な実施形態による、エネルギー速度ドメインに対する低凸曲線を示す。
【図４】図４は、様々な実施形態による、モード切替によるタスク内エネルギーオーバーヘッドを考慮したエネルギー速度ドメインに対する変更された低凸曲線を示す。
【図５】図５は、様々な実施形態の実行に適した例示的コンピュータシステムである。
【図６】図６は、本開示によって全てが構成された命令を有するコンピュータプログラム製品を有する例示的製造物品である。
【発明を実施するための形態】
【０００７】
[0006]  以下の説明では、クレームされた主題が完全に理解されるように、具体的な詳細とともに多様な例を記載する。しかし、クレームされた主題は、本明細書中に開示される具体的な詳細のいくつかまたはそれ以上を用いずとも実施され得ることが当業者には理解されるであろう。さらに、クレームされた主題が不必要に不明瞭になることを避けるために、状況によっては、周知の方法、処理手順、システム、構成要素、および／または回路について、詳細な説明をしていない。以下の詳細な説明では、本明細書の一部を成す添付の図面を参照する。図面中、文脈上特段の指示がない限り、同様の符号は、通常同様の構成要素を指す。詳細な説明、図面および請求の範囲に記載される例示的な実施形態は限定を意図したものではない。本明細書中に開示される主題の精神または範囲を逸脱することなく、他の実施形態を使用してもよく、また他の変更を加えてもよい。本明細書中に一般的に記載され、かつ図面中に示される本開示の態様は、様々な異なる構成で配置され、置き換えられ、組み合わされ、設計されることができ、それらの全ては明細書において示唆され、かつ本開示の一部を成すことが容易に理解されるだろう。
【０００８】
[0001]  以下の説明では、コンピューティングシステム内、例えばコンピュータおよび／またはコンピューティングシステムメモリ内に保存されるデータビットおよび／または２値デジタル信号に対する動作のアルゴリズムおよび／または記号表示が提示され得る。アルゴリズムは、一般的に、一連の自己無撞着の動作および／または所望の結果をもたらす同様の処理とみなされ、ここで、動作とは、保存、転送、組み合わせ、比較、および／またはその他操作が可能な電気的、磁気的、および／または電磁的な信号の形を取り得る物理量の物理的操作を含み得る。多様な文脈において、そのような信号は、ビット、データ、値、要素、記号、文字、項、数、数表示等と呼ばれ得る。しかし、そのような用語が物理量を示すのに使用され得ることが、当業者には認められるであろう。よって、本説明において「保存」、「処理」、「検索」、「計算」、「決定」などの用語が使用される場合、当該用語は、コンピュータまたは同様の電子計算デバイス（携帯電話など）などのコンピューティングプラットフォームの動作を指し得る。ここで、コンピューティングプラットフォームは、当該コンピューティングプラットフォームのプロセッサ、メモリ、レジスタ等内の電子量および／または磁気量を含む物理量として表現されるデータを操作および／または変換するものである
【０００９】
[0007]  本開示は、とりわけ、目標のコンピューティングプラットフォーム上のタスク実行をスケジューリングすることに関する方法、装置、システムおよびコンピュータプログラム製品に関する。
【００１０】
[0008]  図１は、本開示の様々な実施形態による、目標のコンピューティングプラットフォーム上のタスク実行をスケジューリングおよび／または編成する方法１００を示している。以下でさらに詳細に説明されるが、方法１００は、目標のコンピューティングプラットフォーム上のタスクの実行を最適にスケジューリングすることができ、タスクを実行するために消費されるエネルギー量を減少または最小限にする。本開示の目的のために、実行のためにスケジューリングされるタスクのセットはJ＝｛τ１，...，τｎ｝で表されてもよい。各タスクはτｉ＝（ａｉ，ｂｉ，Ｒｉ，Ｃｉ）によって特徴付けられてもよく、ここで：
・ａｉはタスクｉの出現時間であり；
・ ｂｉはタスクｉの実行完了期限（または単に、期限）であり；
・ Ｒｉはタスクｉを処理または実行するための目標のコンピューティングプラットフォームの所要クロック周期であり；
・ Ｃｉはタスクｉの目標のコンピューティングプラットフォームの平均切替容量である。
【００１１】
[0009]  目標のコンピューティングプラットフォームはその動作モード１（本開示では、「供給電圧」または「速度」よりも「動作モード」という用語が用いられており、その理由としては、最新の技術は供給電圧の変更のみではなくバイアス電圧を減少させることによってもエネルギー散逸を減少させることができるからである）
【数１】
2010250802.tif 000003
によって特徴付けられてもよい。ここで、各モードは一対ｍｊ＝（ｅｊ，ｓｊ）であり、ここで：
・ｅｉはｊｔｈモードにおける一クロック周期毎のエネルギー消費であり、
・ ｓｉはｊｔｈモードで走っているときのプロセッサ速度である。
【００１２】
[0010]  したがって、目標のコンピューティングプラットフォーム上でタスクのセットの実行を最適にスケジューリングし、タスクのセットを実行するために消費されるエネルギー量を減少または最小限にすることによる問題は、以下の問題としてみなされ得る：
【数２】
2010250802.tif 000004
ここで、Ｐ（  ）は電力消費関数であり、ξ（ｔ）は時間ｔにおけるプロセッサモードおよびスケジューリングされたタスクを規定するマッピング関数である。
【００１３】
[0011]  式（１）はタスクを実行するために必要とされるクロック周期の量の見地から言い換えることができる、すなわち、
【数３】
2010250802.tif 000005
【００１４】
[0012]  したがって、問題を解決することは、時間ｔにおけるスケジューリングされたタスクを規定するマッピング関数χ（ｔ）を見出すこととみなされてもよく、それによって[０，Ｔ]期間中の全エネルギー消費は所望のレベルに最小化または減少される。
【００１５】
[0013]  本開示の実施形態によると、方法１００はブロック１０２、１０４および／または１０６に図示される１つ以上の機能または処理動作を含んでもよい。示されるように、処理は臨界時間区間(critical time interval)を識別することであるブロック１０２で開始することができ、ここでは［０，Ｔ］期間の臨界時間区間［ａ，ｂ］が識別される。方法１００はブロック１０２から、臨界時間区間に対するタスク実行をスケジューリングすることであるブロック１０４へと進むことができ、ここでは臨界時間区間中に実行されるタスクがスケジューリングおよび／または編成される（以下、単に「スケジューリング」という）。方法１００は、ブロック１０４から、更なるタスクをスケジューリングする場合に識別およびスケジューリングを繰り返すことであるブロック１０６へと進むことができる。ブロック１０６では、方法１００は、依然としてスケジューリングされていない更なるタスクがあるか否かを決定することができ、その場合、方法１００はブロック１０２および１０４を繰り返す。プロセスは全てのタスクがスケジューリングされるまで続くことができる。
【００１６】
[0014]  様々な実施形態では、図示されるように、ブロック１０２で臨界時間区間を識別することは、最も大きい下限平均動作速度を有する実行可能な時間区間を臨界時間区間として選択することであるブロック１１２を含んでもよい。様々な実施形態では、［０，Ｔ］期間は複数の実行可能な時間区間を有するものとしてみなされてもよく、臨界時間区間を識別すること１０２はこれらの実行可能な時間区間のうちの１つを選択することを含む。様々な実施形態では、実行可能な時間区間の各々は平均動作速度を有しており、平均動作速度とは、実行可能な時間区間中に実行されるタスクを実行するために必要な平均動作速度である。さらに、実行可能な時間区間の各々は下限平均動作速度を有しており、これは以下でより詳細に説明する。さらに、選択することはこれらの下限に少なくとも部分的に基づいてもよく、より詳細には、最も大きい下限平均動作速度を有する実行可能な時間区間が臨界時間区間として選択され得る。
【００１７】
[0015]  図１を引き続き参照すると、臨界時間区間に対するタスク実行をスケジューリングすることであるブロック１０４は、最も早い期限でタスクをスケジューリングすることであるブロック１２２、および実動作モードまたは仮想動作モードを選択することであるブロック１２４を含んでもよい。ブロック１２２では、方法１００は、タスクの実行完了期限の順序によって臨界時間区間中に実行されるタスクをスケジューリングしてもよく、すなわち、より早い実行完了期限を有するタスクは遅い実行完了期限を有する別のタスクより前に実行のためにスケジューリングされる。ブロック１２４では、方法１００は、臨界時間区間に対して実動作モードまたは仮想動作モードのいずれかを条件的に選択してもよい。様々な実施形態では、実動作モードまたは仮想動作モードは以下のように選択されてもよい：
【数４】
2010250802.tif 000006
【数５】
2010250802.tif 000007
ここで、
ｓ１およびｓ２は、２つの動作モードの２つのそれぞれの動作速度であり；
ｓ＊は、ｔ１およびｔ２の間それぞれｓ１およびｓ２で動作することによって達成される仮想動作速度であり；
δｉｊは、コンピューティングプラットフォームが動作モードｉから動作モードｊに切り替わるときにスケジューリングされたタスクが停止することによって生じる遅延であり；
ｓ＊δは、δｉｊを考慮した仮想動作速度である。
以下でより詳細に説明するように、様々な実施形態では、ｓ１およびｓ２は、目標のコンピューティングプラットフォームのエネルギーと速度の関係の凸包絡線（凸エネルギー速度包絡線と呼んでもよい）上の２つの動作モードの２つのそれぞれの動作速度であってもよい。
【００１８】
[0016]  図１をさらに参照すると、更なるタスクをスケジューリングする場合に識別およびスケジューリングを繰り返すことであるブロック１０６は、臨界時間区間を除去して出現時間および実行完了期限を調整することであるブロック１３２を含んでもよい。ブロック１３２では、方法１００は（現在スケジューリングされている区間中に実行されるタスクを有する）直近に識別された臨界時間区間を[０，Ｔ]期間から除去し、直近に識別された臨界時間区間の除去を反映させるために出現時間および実行完了期限を調整して別のイテレーションのために問題を効果的に再公式化してもよい。一例として、［０，Ｔ］が６０分間にわたり、直近に識別された臨界時間期間が４１から４５分と識別されていた場合、それらのタスクがスケジューリングされた後、４１から４５分区間は［０，Ｔ］から除去され、４５分の後のタスク出現時間および／または実行完了期限は１５分早くなるように更新され、問題を４５分にわたる［０，Ｔ］期間を有する問題として効果的に再公式化する。
【００１９】
[0017]  したがって、方法１００はχ（ｔ）を最適にだけではなく効率的に解くことができ、χ（ｔ）は、［０，Ｔ］期間中の全エネルギー消費が所望のレベルに最小化または減少されるように時間ｔにおけるスケジューリングされたタスクを規定する。さらに、方法１００は、目標のコンピューティングプラットフォームのエネルギーと速度の関数関係と無関係であり得る。言い換えると、目標のコンピューティングプラットフォームのエネルギーと速度の関数関係が非凸状または凸状であることに関わらず、方法１００はχ（ｔ）を最適および効率的に解くことができる。方法１００が最適であり、かつエネルギーと速度の関数関係と無関係であることができる理由は以下で説明する。理解を容易にするために、一般性（および目標のコンピューティングプラットフォームへの適用性）を失うことなく、プロセッサの観点から説明する。
【００２０】
[0018]  さらに、説明をする前に、方法１００はここまで複数のタスクをスケジューリングすると記載されたが、それは方法１００を多数（２つ以上）のタスクをスケジューリングすると限定しているように解釈するべきではない。方法１００は単一のタスクをスケジューリングするために実行されてもよい。単一のタスク状況においては、（単一のタスクの出現および期限によって規定される）１つの時間区間しかなく、定義によると、時間区間は唯一の臨界時間区間である。
【００２１】
[0019]  まず、動的スケジューリング技術によるいくつかの比較的重大なオーバーヘッドは遅延およびエネルギーオーバーヘッドであることを想起する。特に、タスクが実行中であるときにプロセッサの動作モードが変化している場合、このオーバーヘッドは、メモリアクセスおよびリカバリーから生じる遅延およびエネルギー散逸によりさらに重大になる。したがって、各対の動作モードに対しては、２つのオーバーヘッド測定法がある：∈ｉｊおよびδｉｊ、∈ｉｊはモードｉからｊに切り替わるときのエネルギーオーバーヘッドである。前述したように、δｉｊはスケジューリングされたタスクが停止した時間の間の動作モードの切り替えによる遅延である。
【００２２】
[0020]  モード切り替えが供給（Ｖｄｄ）およびボディバイアス電圧（Ｖｂｓ）変化の結果であった場合、遅延およびエネルギーオーバーヘッドは以下として述べることができる：
【数６】
2010250802.tif 000008
【数７】
2010250802.tif 000009
【００２３】
[0021]  上記の式では、Ｃｒは電力レール容量(power rail capacitance)を表し、Ｃｓは基板全体およびウェル容量(well capacitance)である。ＶｄｄおよびＶｂｓに対する移行時間は異なるため、２つの定数ｐｖｄｄおよびｐｖｂｓは両方の時間オーバーヘッドを別々に計算するために使用される。状態切り替えにおける何か他のオーバーヘッドが存在した場合、追加の項が式（５）および式（６）に追加されてもよい。
【００２４】
[0022]  したがって、期間［ａ，ｂ］の強度、すなわち、期間中にタスクを実行するために必要とされるクロック周期の数は、以下のように規定されてもよい：
【数８】
2010250802.tif 000010
【００２５】
[0023]  上記の式は期間Ｉ内の全てのタスクを実行するために必要とされる平均速度である。したがって、統一切替容量に関して、ｇ（Ｉ）は期間Ｉにおける平均速度の下限である。不統一切替容量に関して、ｇ（Ｉ）は不統一性を反映させるために適宜修正されてもよい。理解を容易にするために、説明は統一切替容量を仮定とする。
【００２６】
[0024]  したがって、最適なスケジューリングを見出すためには、プロセッサが動作する平均速度が最適な解決策をもたらすエネルギー消費を有するｇ（Ｉ）より少なくならないように構成されてもよい。したがって、このスケジューリング問題を解決することは、［０，ｓｍａｘ］（ｓｍａｘはプロセッサが走ることができる最大可能速度である）における速度対エネルギーの仮想主観的マッピングを妥協なしで行うことである。そのような曲線を用いることによって、プロセッサは任意の速度で仮想的に走るとしてみなすことができる。
【００２７】
[0025]  図２a〜図２ｂは、本開示の様々な実施形態によって、プロセッサがどのように任意の仮想動作速度で動作できるかを示す。プロセッサが図２ａに図示されるように２つの動作モードｓ１およびｓ２を有すると仮定する。プロセッサを所定の期間［ａ，ｂ］に対して速度ｓ＊（ｓ１＃ｓ＊＃ｓ２）で走らせるために、プロセッサはｔ１秒の間ｓ１で走り、ｔ２秒の間ｓ２で走ってもよく、ｔ１およびｔ２の意味は以下に示す：
【数９】
2010250802.tif 000011
【数１０】
2010250802.tif 000012
【００２８】
[0026]  上記の式では、ｓ１およびｓ２は２つの動作モードの２つのそれぞれの動作速度であり、ｓ＊は時間ｔ１およびｔ２の間それぞれｓ１およびｓ２で動作することによって達成される仮想動作速度であり、ｓ＊は仮想動作速度である。
【００２９】
[0027]  したがって、プロセッサは図２ａのグラフ２０２で図示されるように任意の仮想動作速度で動作してもよく、ｔ１およびｔ２は上記の式を用いておよび図２ｂにおけるグラフ２０４で図示されるように決定されてもよい。
【００３０】
[0028]  したがって、δｉｊである遅延が、プロセッサが動作モードｉから動作モードｊへと切り替わるときにスケジューリングされたタスクが停止することによって生じた場合、ｓ＊、ｓ１、ｓ２、ｔ１およびｔ２の間の関係は上述したように式（３）および（４）で示される。式（４）は、切替遅延オーバーヘッドにより仮想速度がｓ２より大きく、したがってプロセッサは一部の時間のみｓ２で走る場合を示す。
【００３１】
[0029]  図３は、本開示の様々な実施形態による、エネルギー速度ドメインに対する低凸曲線を示す。図示されるように、エネルギー／速度動作モードのセットを有するコンピューティングプラットフォームに対しては、エネルギー速度の関数関係が非凸状または凸状であることに関わらず、最も低い動作速度に対するエネルギー消費が最も低い公知の動作速度に対する公知のエネルギー消費と同じであると想定して、すなわち、曲線３０２に示されるように、速度軸全体を覆うように左下側の曲線を延在することによって、低凸曲線（凸エネルギー速度包絡線とも呼ばれる）を作成することができる。
【００３２】
[0030]  曲線３０２における点は、ｓ’１に対して非減少順序で分類されるＭ＝｛(ｅ’１，ｓ’１)，…，(ｅ’ｑ，ｓ’ｑ)｝で表されてもよい。結果として生じるエネルギー速度曲線３０２は以下の通り示すことができる：
【数１１】
2010250802.tif 000013
【００３３】
[0031]  図４は、本開示の様々な実施形態による、モード切替によるタスク内エネルギーオーバーヘッドを考慮したエネルギー速度ドメインに対する修正された低凸曲線を示す。図示されるように、モード切替によるタスク内エネルギーオーバーヘッドを考慮するためには、εｊ（ｓ）における各線分［(ｅｉ，ｓｉ)，（ｅｊ，ｓｉ）］は［(ｅｉ，ｓｉ)，（ｅｊ，ｓｉ）＋∈ｉｊ］で置き換えられ、∈ｉｊは正規化切替オーバーヘッドであり、この関数をε’ｊ（ｓ）と呼ぶ。単調曲線あてはめを適用することによって、曲線４０２で図示されるようなε’ｊ(ｓ)を以下の通り作り出すことができる：
【数１２】
2010250802.tif 000014
【００３４】
[0032]  εｖ(ｓ)は、低凸曲線の構成の結果として無視されたところに新しい点をエネルギー速度ドメインに潜在的に導入することができる。例えば、ｍ’は、エネルギーオーバーヘッドの考慮の結果、より良い性能を達成するために用いることができる点である。したがって、エネルギー速度曲線は
【数１３】
2010250802.tif 000015
として修正される（ｍ＊のような新しい点を考慮する）。以下、この仮想エネルギー速度曲線をεｖ(ｓ)と呼ぶ。
【００３５】
[0033]  区間Ｉ＊は、ｇ（Ｉ＊）が［０，Ｔ］における全ての可能な区間に対して最大であった場合に臨界であるとされている。Ｒ＊はＩ＊の中にある全てのタスクを実行するために必要とされるクロック周期の数である。したがって、いくつかのタスクｉおよびｊに対してはＩ＊＝［ａｉ，ｂｊ］である。
【００３６】
[0034]  
【数１４】
2010250802.tif 000016
とする。Ｉ＊中に最小エネルギー消費を達成するためには、Ｉ＊内の（１つまたは複数の）タスクは（α１，…，αｐ）の時間割合に対してそれぞれＳ＝{ｓ＊１，...，ｓ＊ｐ}で走ると仮定する（Σαｉ＝１００％）。本開示によると、動作モードはεｖ(ｓ)では連続的である。
【００３７】
[0035]  
【数１５】
2010250802.tif 000017
の継続時間を＝Ｔとし、ｓｑ∈Ｓと仮定する。ここで、
【数１６】
2010250802.tif 000018
であり（ｊ−ｉ）は最小である。言い換えると、ｓｑはＳでは２つの動作速度の間にあり、全ての中間速度はＳにはない。ｓｑをＳに足すことは、Ｉ中の全エネルギー消費を減少することができる。
【数１７】
2010250802.tif 000019
であるため、
【数１８】
2010250802.tif 000020
になるようにβおよびγが存在する。
【００３８】
[0036]  一般性を失わずに、αｉ≦αｊと仮定する。したがって、
【数１９】
2010250802.tif 000021
中の正規化されたエネルギー消費（すなわち、クロック周期毎）は以下の通り述べることができる：
【数２０】
2010250802.tif 000022
【００３９】
[0037]  これは、プロセッサがｓｑで走った場合、プロセッサが
【数２１】
2010250802.tif 000023
で走ったときのｓｑの仮想速度中のエネルギー消費を減少し得ることを意味する。したがって、Ｓは連続動作モードをεｖ(ｓ)に含んでもよい。
【００４０】
[0038]  ｓ＊＝ｇ（Ｉ＊）とする。Ｉ＊中の最小エネルギー消費がＩ＊内のタスクを連続速度で走ることを必要とした場合：
時間割合（α１，...，αｐ）にそれぞれに対して
【数２２】
2010250802.tif 000024
そしてｐ≦２である。
【００４１】
[0039]  
【数２３】
2010250802.tif 000025
と仮定する。全ての
【数２４】
2010250802.tif 000026
に対して、上記の主張におけるアプローチをここで適用することができ、必要に応じてαｉおよびαｉ＋１を増加させてＩ中の全電力消費を減少させることによって
【数２５】
2010250802.tif 000027
における演算を消去する。
【００４２】
[0040]  最後に、最適スケジューリングでは、臨界区間Ｉ＊はｅ(ｇ(Ｉ＊))，ｇ(Ｉ＊)の仮想モードで走る。εｖ(ｓ)が凸曲線であった場合、最適性を従うことができる。εｖ(ｓ)は原則として凸状ではないが、凸性質を有していることが証明されている。εｖ(ｓ)が視覚的に凸状ではない理由としては、εｖ(ｓ)が条件付きグラフであるという事実のためである。言い換えると、各速度が１つまたは２つの動作モードを介して仮想的に達成された場合、εｖ(ｓ)は異なる速度における最小エネルギー消費である。
【数２６】
2010250802.tif 000028
【００４３】
[0041]  式（１４）の解釈は、速度αｓ１＋（１−α）ｓ２におけるエネルギー消費は、プロセッサがαｓ１および（１−α）ｓ２で走っている場合の重み付けされたエネルギー消費より少ない場合があるということであり得る。したがって、オーバーヘッドエネルギーε１２を考慮に入れる必要がある。式（１１）によると
【数２７】
2010250802.tif 000029
【００４４】
[0042]  式（１５）は、請求項の正確さおよび使用中のεｖの凸性を立証する。したがって、図１の方法１００は、特に、目標のコンピューティングプラットフォームの凸エネルギー速度包絡線における動作モードを用いて仮想動作モードが解釈された場合、最適な解決策をもたらすことができる。
【００４５】
[0043]  図５は、本開示の様々な実施形態による例示的コンピューティングデバイスを示す。非常に基本的な構成５０１では、コンピューティングデバイス５００は、典型的には、１つ以上のプロセッサ５１０およびシステムメモリ５２０を含む。プロセッサ５１０とシステムメモリ５２０との間の通信のためにメモリバス５３０を用いてもよい。
【００４６】
[0044]  所望の構成によって、プロセッサ５１０はマイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、デジタル信号プロセッサ（ＤＳＰ）またはそれらのあらゆる組み合わせを含むあらゆる種類のものであってもよいが、それらに限定されない。プロセッサ５１０は、レベル１キャッシュ５１１およびレベル２キャッシュ５１２等の１つより多いレベルのキャッシング、プロセッサコア５１３、レジスタ５１４を含んでもよい。例示的プロセッサコア５１３は、演算論理装置（ＡＬＵ）、浮動小数点装置（ＦＰＵ）、デジタル信号処理コア（ＤＳＰコア）またはそれらのあらゆる組み合わせを含んでもよい。例示的メモリコントローラ５１５は、プロセッサ５１０と用いられてもよく、または一部の実施ではメモリコントローラ５１５はプロセッサ５１０の内部であってもよい。
【００４７】
[0045]  所望の構成によると、システムメモリ５２０は、揮発性メモリ（例えばＲＡＭ）、不揮発性メモリ（例えばＲＯＭ、フラッシュメモリ等）またはそれらのあらゆる組み合わせを含むあらゆる種類のものであってもよいが、それらに限定されない。システムメモリ５２０は、オペレーティングシステム５２１、１つ以上のアプリケーション５２２およびプログラムデータ５２４を含んでもよい。アプリケーション５２２は、目標のコンピューティングプラットフォームに対する１つ以上のタスクのためのタスク実行の上述したスケジューリングを実施するために論理を提供するプログラミング命令５２３を含んでもよく、特に、目標のコンピューティングプラットフォームに対する凸エネルギー速度包絡線にある動作モードを用いた仮想動作モードの選択を含む。プログラムデータ５２４は、スケジューリング動作または命令実行に関連した適用可能データ５２５を含んでもよい。
【００４８】
[0046]  コンピューティングデバイス５００は、追加の特徴または機能性、および基本構成５０１と任意の要求されたデバイスおよびインターフェースとの間の通信を容易にするために追加のインターフェースを有してもよい。例えば、バス／インターフェースコントローラ５４０は、記憶インターフェースバス５４１を介する基本構成５０１と１つ以上のデータ記憶デバイス５５０との間の通信を容易にするために用いられてもよい。データ記憶デバイス５５０は、リムーバブル記憶デバイス５５１、非リムーバブル記憶デバイス５５２またはそれらの組み合わせを含んでもよい。一部を挙げると、リムーバブル記憶および非リムーバブル記憶デバイスとしては、フレキシブルディスクドライブおよびハードディスクドライブ（ＨＤＤ）等の磁気ディスクデバイス、コンパクトディスク（ＣＤ）またはデジタル多目的ディスク（ＤＶＤ）ドライブ等の光ディスクドライブ、ソリッドステートドライブ（ＳＳＤ）およびテープドライブが挙げられる。例示的コンピュータ記憶媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュールまたは他のデータ等の情報の保存のためにあらゆる方法または技術において実施される揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含んでもよい。
【００４９】
[0047]  システムメモリ５２０、リムーバブル記憶装置５５１および非リムーバブル記憶装置５５２は全てコンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）または他の光記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶デバイス、あるいは所望の情報を保存するために使用され、かつコンピューティングデバイス５００によってアクセスされてもよい他のあらゆる媒体を含むが、それらに限定されない。そのようなあらゆるコンピュータ記憶媒体はデバイス５００の一部であってもよい。
【００５０】
[0048]  コンピューティングデバイス５００は、様々なインターフェースデバイス（例えば、出力インターフェース、周辺インターフェースおよび通信インターフェース）からバス／インターフェースコントローラ５４０を介する基本構成５０１への通信を容易にするためのインターフェースバス５４２を含んでもよい。例示的出力デバイス５６０は、グラフィックスプロセシングユニット５６１およびオーディオプロセシングユニット５６２を含み、これらは１つ以上のＡ／Ｖポート５６３を介してディスプレイまたはスピーカ等の様々な外部デバイスと通信するように構成されてもよい。例示的周辺インターフェース５７０は、シリアルインターフェースコントローラ５７１またはパラレルインターフェースコントローラ５７２を含み、これらは１つ以上のＩ／Ｏポート５７３を介して入力デバイス（例えば、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイス等）または他の周辺デバイス（例えば、プリンタ、スキャナ等）などの外部デバイスと通信するように構成されてもよい。例示的通信デバイス５８０は、ネットワークコントローラ５８１を含み、これは１つ以上の通信ポート５８２を介するネットワーク通信リンクを通じる１つ以上の他のコンピューティングデバイス５９０との通信を容易にするように構成されてもよい。
【００５１】
[0049]  ネットワーク通信リンクは通信媒体の一例であり得る。通信媒体は、典型的には、コンピュータ読取可能命令、データ構造、プログラムモジュール、あるいはキャリア波または他の位相機構等の変調されたデータ信号内の他のデータによって組み入れられてもよい。「変調されたデータ信号」は、その特徴の１つ以上が信号内の情報を符号化するように設定または変化されている信号であってもよい。一例として、通信媒体としては、有線ネットワークまたは直接有線接続等の有線媒体、および音響、無線周波数（ＲＦ）、マイクロ波、赤外線（ＩＲ）および他の無線媒体等の無線媒体を含んでもよいが、それらに限定されない。本明細書中に使用されるコンピュータ読取可能媒体という用語は、記憶媒体および通信媒体の両方を含んでもよい。
【００５２】
[0050]  コンピューティングデバイス５００は、携帯電話、個人情報端末（ＰＤＡ）、パーソナルメディアプレーヤデバイス、無線ウェブウォッチデバイス、パーソナルヘッドセットデバイス、特定用途デバイスまたは上記の機能のうちのいずれかを含むハイブリッドデバイス等のスモールフォームファクタポータブル（またはモバイル）電子デバイスの一部として実行されてもよい。コンピューティングデバイス５００は、ラップトップコンピュータおよびラップトップではないコンピュータ構成を含むパーソナルコンピュータとして実行されてもよい。
【００５３】
[0051]  図６は、本開示の様々な実施形態によるコンピュータプログラム製品を有する例示的製造物品を示す。例示的コンピュータプログラム製品６００は、コンピュータ読取可能記憶媒体６３２およびコンピュータ読取可能媒体６３２に記憶された複数のプログラミング命令６３４を含んでもよい。これらの実施形態のうちの様々な１つにおいては、プログラミング命令６３４は臨界時間区間を識別するための命令を含んでもよい。様々な実施形態では、プログラミング命令６３４は、識別された臨界時間区間中に実行される１つ以上のタスクの実行をスケジューリングするための命令を含んでもよい。実行は目標のコンピューティングプラットフォーム上で行われる。様々な実施形態では、スケジューリングは、上述した凸エネルギー速度包絡線上にある動作モードから構成される仮想動作モードの選択を含んでもよい。更なる他の実施形態では、プログラミング命令６３４は、スケジューリングされることが残っているタスクに対して識別およびスケジューリングを繰り返すための命令をさらに含んでもよい。
【００５４】
[0052]  実施形態は図６に示される命令の一部またはその全てを有してもよい。コンピュータプログラム製品６００の実施形態は、本明細書中に説明される実施形態による他の命令を有してもよい。コンピュータ読取可能媒体６３２は、コンパクトディスク（ＣＤ）、デジタル多目的ディスク（ＤＶＤ）、ソリッドステートドライブ、ハードドライブ等の揮発性および永続性メモリを含むがそれらに限定されない様々な形態であってもよい。実施形態はどの（１つまたは複数の）種類のコンピュータプログラム製品にも限定されない。
【００５５】
[0053]  クレームされた主題は、その範囲について、本明細書に記載する特定の実施に限定されない。例えば、１つのデバイスまたは複数のデバイスの組み合わせ上で動作するように採用されるなどしたハードウェアにおける実施もあり得る一方、ソフトウェアやファームウェアにおける実施もあり得る。同様に、クレームされた主題は、この点において、その範囲が限定されるものではなく、いくつかの実施は、１つの記憶媒体または複数の記憶媒体など１つ以上の物品を含み得る。ＣＤ−ＲＯＭ，コンピュータディスク、フラッシュメモリ等の記憶媒体には、例えば、コンピュータシステム、コンピューティングプラットフォーム、または他のシステムなどのシステムにより実行されると、例えば上述した実施のうちの１つのような、クレームされた主題に従ったプロセッサの実行をもたらす指示が保存され得る。１つの可能性として、コンピューティングプラットフォームは、１つ以上の処理部またはプロセッサと、ディスプレイ、キーボードおよび／またはマウスなどの１つ以上の入力／出力デバイスと、静的ランダムアクセスメモリ、動的ランダムアクセスメモリ、フラッシュメモリおよび／またはハードドライブなどの１つ以上のメモリと、を含み得る。
【００５６】
[0054]  システムの態様のハードウェア実施とソフトウェア実施との間に区別はほとんどない。ハードウェアまたはソフトウェアの使用は、一般的に（一定の背景においては、ハードウェアとソフトウェアとの間の選択は重要になることもあるため、常にではないが）費用対効果の兼ね合いを表す設計選択である。本明細書に記載するプロセスおよび／またはシステムおよび／または他の技術を実現させ得る様々な媒体が存在し（例えば、ハードウェア、ソフトウェア、および／またはファームウェア）、好ましい媒体は、当該プロセスおよび／またはシステムおよび／または他の技術が展開される背景によって異なるだろう。例えば、速度と精度が優先される場合、実施者は、ハードウェアまたはファームウェアの媒体を主に選択し得るし、柔軟性が優先される場合は、実施者は主にソフトウェアによる実施を選択し得る。あるいは、実施者はハードウェア、ソフトウェアおよび／またはファームウェアの所定の組み合わせを選択し得る。
【００５７】
[0055]  一部の実施形態では、本明細書に記載する主題のうちいくつかの部分は、特定用途向け集積回路（ＡＳＩＣ）、書き換え可能ゲートアレイ（ＦＰＧＡ）、デジタル信号プロセッサ（ＤＳＰ）、または他の統合された形式を介して実施可能である。しかし、本明細書に開示される実施形態のうちいくつかの態様は、全部または一部において、１つ以上のコンピュータ上で実行する１つ以上のプログラムとして（例えば、１つ以上のコンピュータシステム上で実行する１つ以上のプログラムとして）、１つ以上のプロセッサ上で実行する１つ以上のプログラムとして（例えば、１つ以上のマイクロプロセッサ上で実行する１つ以上のプログラムとして）、ファームウェアとして、あるいはそれらの実質的にあらゆる組み合わせとして、集積回路において同等に実施することができること、また、ソフトウェアおよび／またはファームウェアのために回路を設計することおよび／またはコードを書くことは、本開示を考慮すると、十分に当業者の技術の範囲内であることが、当業者には認められるであろう。加えて、本明細書に記載する主題のメカニズムは、多様な形態のプログラム製品として頒布可能であること、また、当該頒布を実際に行うために使用される信号伝達媒体の特定の種類に関わらず、本明細書に記載する主題の例示的な実施形態が該当することが、当業者には理解されるであろう。信号ベアリング媒体の例としては、フロッピー（登録商標）ディスク、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）、デジタルテープ、コンピュータメモリなどの書き込み可能な媒体や、デジタルおよび／またはアナログ通信媒体などの伝送媒体（例えば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）が挙げられるが、これらに限定されない。
【００５８】
[0056]  本明細書で使用される実質的にあらゆる複数のおよび／または単数の用語について、当業者は、文脈および／または用途に応じて適切に、複数の用語を単数に、および／または単数の用語を複数に置き換えることができる。本明細書では、明確性を目的として、多様な単数／複数の置き換えが明記され得る。
【００５９】
[0057]  本開示は上記で示された実施形態に関して説明してきたが、同じ目的を達成するために当てられた広い範囲の別のおよび／または同等の実施が本開示の範囲から逸脱することなく、示されかつ説明された実施形態のために置き換えられてもよいことが当業者に理解されるであろう。本開示による実施形態が非常に広い範囲の実施形態で実施されてもよいことが当業者にすぐに理解されるだろう。本記載は限定的ではなく例示的であることを意図している。
【図１】
2010250802.tif 000030
【図２】
2010250802.tif 000031
【図３】
2010250802.tif 000032
【図４】
2010250802.tif 000033
【図５】
2010250802.tif 000034
【図６】
2010250802.tif 000035
【外国語明細書】
2010250802000001.pdf