(57)【要約】  本発明は、マルチプロセッサシステム用のエネルギ消費のオンライン管理のための方法に関し、この方法が、タスク（１、Ｔｉ）のチャート（１０）に従って少なくとも１つのアプリケーションを実行し、前記方法が、各アプリケーション用に、    −  タスクの実行の潜在的な並列処理速度の変動を時間の関数としてオフラインで特徴付けるための第１の段階であって、この特徴付けが、最悪の場合のタスク実行時間ＷＣＥＴに基づいている第１の段階と、  −  不活性期間および潜在的な時間の超過をオンラインで検出および利用するための第２の段階であって、ＤＰＭ技術が、最悪の場合において特徴付けられた潜在的な並列処理速度に従って、プロセッサが不活性のままである可能性がある期間を決定することを可能にする第２の段階と、を含むことを特徴とする。  本発明は、バッテリの寿命制約がますます重要になりつつある新世代の組み込みマルチプロセッサシステムに特に適用される。したがって、本発明は、例えば、マルチメディアまたは電気通信用途のための組み込みシステムに特に適用される。
2011519452.tif 000002
【特許請求の範囲】
【請求項１】
タスク（１、Ｔｉ）のチャート（１０）に従って少なくとも１つのアプリケーションを実行するマルチプロセッサシステムのエネルギ消費を管理するための方法であって、前記方法が、各アプリケーション用に少なくとも、
−  前記タスクの実行の潜在的な並列処理速度の変動を、時間の関数としてオフラインで特徴付けるための第１の段階（４１）であって、この特徴付けが、前記タスクの最悪の場合の動作に基づいている第１の段階（４１）と、
−  潜在的な不活性期間をオンラインで検出および利用するための第２の段階（４２）であって、関係するプロセッサが不活性のままで到達する可能性がある時間が、オフラインで特徴付けられた前記最悪の場合の潜在的な並列処理速度によって得られ、適切なアイドルモードが、前記プロセッサが活性のままで到達する可能性がある時間に従って、計算および活性化される第２の段階（４２）と、
を含むことを特徴とする方法。
【請求項２】
前記オンライン段階（４２）が、最悪の場合の動作の実行時間に対して、実際の実行中に前記タスクによって生成された時間の超過（８４、８５）の検出および利用を実行し、タスクによって生成された前記時間の超過が、同じプロセッサ上で直後に割り当てられたタスクに割り当てられて、その実行速度を低減し、前記実行速度のこの低減が、所定の電圧および周波数から、より低い電圧および周波数へ前記プロセッサを切り替えることによって得られることを特徴とする、請求項１に記載の方法。
【請求項３】
前記第２の段階（４２）において、前記不活性期間の検出および前記アイドルモードのインプリメンテーション（ＤＰＭ）に加えて、前記時間の超過（８４、８５）を検出して、前記プロセッサの前記電圧および前記周波数を動的に調整すること（ＤＶＦＳ）を特徴とする、請求項１または２に記載の方法。
【請求項４】
前記オフライン特徴付け段階（４１）が、少なくとも、
−  連続するタスクが、ラベルの下でグループ化されるタスクラベリング段階（５１）と、
−  大域的なラベルスケジューリング段階（５２）と、
−  前記様々なラベルの実行開始時間、および各時間において必要なプロセッサ数を記憶するための段階（５３）であって、前記記憶が、データ構造（７１、７２）において実行され、前記構造が、前記タスクの前記最悪の場合の並列性を特徴付ける段階（５３）と、
を含むことを特徴とする、請求項１または３に記載の方法。
【請求項５】
プロセッサが不活性のままで到達する可能性がある前記時間が、オフラインで決定された前記最悪の場合の動作の、前記並列処理速度を増加させる次のラベルの到達時間に対応することを特徴とする、請求項４に記載の方法。
【請求項６】
前記オフライン特徴付け段階（４１）が、前記アプリケーションの実行に必要な前記プロセッサ用の機能開始モードを決定するための段階（５４）を含み、前記機能モード（７３）が、前記第１のラベルの到達時間に従って決定されることを特徴とする、請求項４および５のいずれか一項に記載の方法。
【請求項７】
ラベル（６１、Ｌｎ）の構造が、次のルール、
−  前記チャートにおける収束（６２）のレベルにおいて、ラベルの構造が、前記収束タスクの前で停止されることと、
−  前記チャートの拡散レベルにおいて、ラベルの構造が、ブランチに沿って継続され、他のラベルが、他のブランチ用に構成されることと、
−  タスクが、単一のラベルにのみ属することと、
を満たすことを特徴とする、請求項４〜６のいずれか一項に記載の方法。
【請求項８】
ラベル（６１）が、前記チャートの同一のブランチの最大数のタスクを含むことを特徴とする、請求項４〜６のいずれか一項に記載の方法。
【請求項９】
所与のプロセッサ上で実行されたタスクＴｉによって生成された前記時間の超過が、同じプロセッサに割り当てられた次のタスクＴｉ＋１に割り当てられることを特徴とする、請求項２または３のいずれか一項に記載の方法。
【請求項１０】
異なるタスクによって得られた前記時間の超過（８４、８５）が、より低い電圧および周波数ペアリングを活性化するために十分に長い時間が得られるまで集約され、時間の超過が、それだけで考えられた場合に、それがより低い電圧および周波数ペアリングへの切り替えを可能にしない場合には、別の時間の超過と集約されることを特徴とする、請求項２または３のいずれか一項に記載の方法。
【請求項１１】
前記時間の超過が、実行の全体にわたって集約され、前記ラベルの終点タスクに割り当てられることを特徴とする、請求項２または３のいずれか一項あるいは請求項９または１０のいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッサシステム用のエネルギ消費を管理するための方法に関する。この方法は、バッテリの寿命制約がますます重要になりつつある新世代の組み込みマルチプロセッサシステムにおけるエネルギ要件に特に適用される。したがって、この方法は、例えばマルチメディアまたは電気通信用途のための組み込みシステムにとくに適用される。
【背景技術】
【０００２】
マルチプロセッサシステムは、計算および記憶性能レベルの向上を要求するますます複雑で多様化したアプリケーションを組み込んでいる。かかる性能レベルの向上は、一方では常に増加する動作周波数によって、他方ではプロセッサおよびメモリ回路数の増加によって反映されるが、ますます高いエネルギ消費に帰着する。
【０００３】
計算素子、典型的にはプロセッサのセットによるアプリケーションの並列処理は、このアプリケーションが、タスクと呼ばれる多数の処理ブロックに細分化されることを必要とする。これらのタスクは、連続して並列に実行される。この細分化の目的は、特に、個々の計算タスクを並列に実行し、したがって、計算速度を上げることであり、並列タスクは、多数のプロセッサに割り当てられる。この種の並列処理を利用する、マルチプロセッサアーキテクチャと呼ばれるアーキテクチャは、計算能力の点で大きな動作柔軟性および優れた性能を提供する。実際には、これらのアーキテクチャは、タスクレベルで強い並列性を有するアプリケーションと同様に、多数のアプリケーションを並列で実行することができる。向上する記憶能力および計算能力を有する並列アプリケーションの実行を可能にする、これらのマルチプロセッサアーキテクチャは、多量のエネルギを消費し、この消費の適切な管理を必要とする。
【０００４】
実時間の文脈では、これらのアーキテクチャは、サポートされるアプリケーションおよび順守すべき時間制約に従って、最悪の場合に備えた大きさにされることが多い。大きさ決定段階は、最悪の場合の実行時間ＷＣＥＴによって各タスクを特徴付けることに存する。ひとたび様々なタスクのＷＣＥＴが計算されると、並列性の利用および時間制約順守の保証を可能にする多数のプロセッサが、最悪の場合において設定される。このプロセッサ数は、タスク間の依存性を順守しながらタスクの実行優先度を設定するために実行されるスケジューリングの選択に強く依存する。あるプロセッサの不活性期間が、あるタスク同期点で発生する可能性があるが、これらの不活性期間は、アプリケーションの潜在的な並列処理速度の変動ゆえであり、最悪の場合の実行挙動に従って特徴付けてもよい。これらの不活性期間が、実際の実行中に同じように発生する場合には、アイドルモードを、オフラインで決定し、かつ実行中にオンラインで実行して、消費エネルギを低減してもよい。残念にも、最悪の場合の実行時間ＷＣＥＴに対する、タスクの実際の実行時間ＡＥＴの変動によって、タスクの順序および起動時間が変更される。したがって、これらの不活性期間のオフラインでの予測は、困難になる。この困難ゆえに、実行中に発生する消費エネルギを低減するために、これらの機会を利用することが制限される。最悪の場合の挙動と実際の挙動との間の差異は、データ依存性であり、かつ多くの制御を伴うアプリケーションではますます重要になる。
【０００５】
しかしながら、これらの差異は、消費を最適化するための大きな可能性を提供する。実際には、最悪の場合の実行時間と比較したタスク実行時間の変動は、時間の超過を明らかにする。これらの時間の超過は、後続タスクの実行速度を減速し、したがって、実時間制約を順守する一方で消費を局所的に低減するために利用してもよい。
【０００６】
大域スケジューリングの文脈では、困難は、時間制約を破ることなくエネルギを効果的に低減するために、実行中に得られる時間の超過を分配するレベルで発生する。
【０００７】
資源レベルで消費管理問題に対処する解決法が知られている。これらの解決法は、いわゆるＤＰＭ（動的電力管理）および／またはＤＶＦＳ（動的電圧周波数制御）技術に基づくことによって、組み込みシステムにおける計算資源（プロセッサ）により消費されるエネルギを低減することを目的とする。ＤＰＭ技術は、所定の期間にわたって使用されない資源をアイドルモードへ切り替えることによって、不活性期間を利用することに存する。ＤＶＦＳ技術は、どちらかといえば、時間の超過を利用して、ある資源の周波数および電圧を局所的または大域的に低下させることを目的とする。
【０００８】
第１の非最適な変形は、Ａ．Ｉｒａｎｌｉ  ａｔ  ｅｔ  ａｌ：  “Ｓｙｓｔｅｍ−ｌｅｖｅｌ  Ｐｏｗｅｒ  Ｍａｎａｇｅｍｅｎｔ  ?  Ａｎ  Ｏｖｅｒｖｉｅｗ”，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｏｕｔｈｅｒｎ  Ｃａｌｉｆｏｒｎｉａ，  Ｄｅｐｔ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  Ｅｎｇｉｎｅｅｒｉｎｇ，  Ｌｏｓ  Ａｎｇｅｌｅｓによる文献Ｄ１に特に説明されているように、資源の不活性期間のオフライン予測に基づいてＤＰＭ技術だけを実行する全ての方法を組み合わせる。しかしながら、最悪の場合の実行時間ＷＣＥＴに対する実際のタスク実行時間の変動は、タスクの順序および起動時間をオンラインで変更する。したがって、これらの不活性期間のこれらの到達時間および長さのオフライン予測は、非常に困難になる。
【０００９】
予測に基づくＤＰＭ技術のインプリメンテーションは、ある場合、すなわちアプリケーションの実行プロファイルが多かれ少なかれ決定論的である場合には、興味ある結果になる可能性がある。到達時間が知られていない多数のインスタンスを備えた多数の用途の一般的な文脈では、これらの技術の実行は、非常に扱いにくいままである。実際には、不十分な予測を用いると、これらの技術は、時間制約を破る追加の遅延時間を導入する可能性がある。
【００１０】
第２の変形は、ＤＶＦＳ技術だけを実行する全ての方法を組み合わせる。この変形は、Ｄ．Ｚｈｕ  ｅｔ  ａｌ：  “Ｓｃｈｅｄｕｌｉｎｇ  ｗｉｔｈ  Ｄｙｎａｍｉｃ  Ｖｏｌｔａｇｅ／Ｓｐｅｅｄ  Ａｄｊｕｓｔｍｅｎｔ  Ｕｓｉｎｇ  Ｓｌａｃｋ  Ｒｅｃｌａｍａｔｉｏｎ  ｉｎ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ”，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．１４，  Ｎ°７，  Ｊｕｌｙ２００３による文献Ｄ２、およびＮ．Ｖｅｎｔｏｕｘ：  “Ｃｏｎｔｒｏｌｅ  ｅｎ  ｌｉｇｎｅ  ｄｅｓ  ｓｙｓｔｅｍｅｓ  ｍｕｌｔｉｐｒｏｃｅｓｓｅｕｒｓ  ｈｅｔｅｒｏｇｅｎｅｓ  ｅｍｂａｒｑｕｅｓ  −  ｅｌａｂｏｒａｔｉｏｎ  ｅｔ  ｖａｌｉｄａｔｉｏｎ  ｄ’ｕｎｅ  ａｒｃｈｉｔｅｃｔｕｒｅ”，  ｄｏｃｔｏｒａｌ  ｔｈｅｓｉｓ  ｄｅｆｅｎｄｅｄ  ｏｎ  １９  Ｓｅｐｔｅｍｂｅｒ  ２００６  ａｔ  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｒｅｎｎｅｓ  １による文献Ｄ３に特に説明されている。これらの技術は、オンラインと同様にオフラインで実行してもよい。オフラインアプローチでは、様々なプロセッサ用のペアリング（電圧、周波数）は、（アプリケーションの大域的な時間制約またはデッドラインに従って）大域的な減速係数を計算することにより大域的に、または（アプリケーションのクリティカルパスに対するタスクの寄与に従って）各タスクに対して局所的な減速係数を計算することによって局所的に、調整してもよい。オンラインアプローチでは、これらの技術は、タスクの実際の実行時間の変動による時間の超過を検出し、それらを利用して、時間制約の順守を保証しながら消費エネルギを低減することを目的とする。
【００１１】
困難は、大域スケジューリングと共存できている最適消費管理方法の準備レベルで明白に現れる。実際には、上述の文献Ｄ２およびＤ３で提示されているような大域スケジューリングの文脈では、著者は、時間制約を順守するために、次善の超過分配方法で間に合わせている。文献Ｄ２において、実行中に得られた時間の超過は、タスクがそれらの時間制約を順守できるようにするために、異なる資源に割り当てられたタスク間で共有される。この方法では、時間の超過の一部は、最悪の場合の実行時間ＷＣＥＴ、および最長タスクを最初に実行する大域スケジューリング方針（Ｌａｒｇｅｓｔ  Ｔａｓｋ  Ｆｉｒｓｔ、ＬＴＦ）に基づくことにより、アプリオリに設定されたタスク制御順序を順守するために、無視される可能性がある。文献Ｄ３において、方法は、実行中に得られた時間の超過を、先行チャートにおける次のタスクに割り当てる。データ依存性または制御依存性に従って超過を分配するためのこの方法は、大域スケジューリング方針と極めて相性がいいが、しかしそれは、例えば、様々な収束ブランチによって生成された全ての超過を利用することは可能にしない。実際には、様々なブランチによって生成された超過のうち最小の超過だけが、消費エネルギを低減するために実行される。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明の１つの目的は、特に、上述の欠点を克服し、マルチプロセッサおよび大域スケジューリングの文脈において消費エネルギの著しい低減を可能にすることである。
【課題を解決するための手段】
【００１３】
この目的のために、本発明の主題は、タスク（Ｔｉ）のチャートに従って少なくとも１つのアプリケーションを実行するマルチプロセッサシステムのエネルギ消費を管理するための方法であり、前記方法は、各アプリケーション用に少なくとも、
−  タスクの実行の潜在的な並列処理速度の変動を時間の関数としてオフラインで特徴付けるための第１の段階であって、この特徴付けが、タスクの最悪の場合の挙動に基づいている第１の段階と、
−  潜在的な不活性期間をオンラインで検出および利用するための第２の段階であって、関係するプロセッサが不活性のままで到達する可能性がある時間が、オフラインで特徴付けられた最悪の場合の潜在的な並列処理速度によって得られ、適切なアイドルモードが、プロセッサが活性のままで到達する可能性がある時間に従って、計算および活性化される第２の段階と、
を含む。
【００１４】
有利なことに、オンライン段階は、例えば、最悪の場合の挙動の実行時間に対して、実際の実行中にタスクによって生成された時間の超過の検出および利用を実行し、タスクによって生成された時間の超過は、同じプロセッサ上で直後に割り当てられたタスクに割り当てられて、その実行速度を低減するが、この実行速度の低減は、所与の（電圧、周波数）ペアリングから、より低いペアリングへプロセッサを切り替えることによって得られる。
【００１５】
別の可能なインプリメンテーションでは、第２の段階において、不活性期間の検出およびアイドルモードのインプリメンテーション（ＤＰＭ）に加えて、時間の超過は、プロセッサの電圧および周波数を動的に調整する（ＤＶＦＳ）ために検出される。
【００１６】
オフライン特徴付け段階は、例えば、少なくとも、
−  連続するタスクが、ラベルの下でグループ化されるタスクラベリング段階と、
−  大域的なラベルスケジューリング段階と、
−  様々なラベルの実行開始時間、および各時間に必要なプロセッサ数を記憶するための段階であって、記憶が、データ構造において実行され、前記構造が、タスクの最悪の場合の並列性を特徴付ける段階と、
を含む。
【００１７】
プロセッサが不活性のままで到達する可能性がある時間は、例えば、オフラインで決定された最悪の場合の挙動において並列処理速度を増加させる次のラベルの到達時間に対応する。
【００１８】
オフライン特徴付け段階には、アプリケーションの実行に必要なプロセッサ用の機能開始モードを決定するための段階を含んでもよく、前記機能モードは、第１のラベルの到達時間に従って決定される。
【００１９】
ラベルの構成は、例えば、次のルールを満たす。
−  チャートの収束レベルにおいて、ラベルの構成は、収束タスクの前で停止される。
−  チャートの拡散レベルにおいて、ラベルの構成は、ブランチに沿って継続され、他のラベルは、他のブランチ用に構成される。
−  タスクは、単一のラベルにのみ属する。
【００２０】
ラベルには、例えば、チャートの同一ブランチの最大数のタスクが含まれる。
【００２１】
別の可能なインプリメンテーションにおいて、所与のプロセッサ上で実行されたタスクＴｉによって生成された時間の超過は、同じプロセッサに割り当てられた次のタスクＴｉ＋１に割り当てられる。
【００２２】
異なるタスクによって得られた時間の超過は、例えば、より低いペアリング（電圧、周波数）を活性化するために十分に長い時間が得られるまで集約されるが、時間の超過は、それだけで考えた場合に、より低いペアリング（電圧、周波数）への切り替えを可能にしない場合には、別の時間の超過と集約される。
【００２３】
時間の超過は、実行の全体にわたって集約し、ラベルの最終タスクに割り当ててもよい。
【００２４】
本発明の他の特徴および利点は、添付の図面に照らして提供される、以下の説明から明らかになろう。
【図面の簡単な説明】
【００２５】
【図１】アプリケーションの実行用のタスクの関連を示す例示的なチャートである。
【図２】２つのプロセッサによる実行の場合における、前の図にあるチャートモデルの最悪の場合の実行挙動の例である。
【図３】２つのプロセッサによる実際のタスクの実行挙動の例である。
【図４】本発明による方法のインプリメンテーション用の２つの可能な段階の表現である。
【図５】並列処理速度のオフライン特徴付け用の段階であり、かつ方法の第１の段階を構成する可能なサブ段階の表現である。
【図６】図１のチャートにおけるラベリングの例である。
【図７】並列処理速度を特徴付けるデータ構造の表現である。
【図８】アプリケーションの実行中における、オンラインによる時間の超過の分配例の実例である。
【発明を実施するための形態】
【００２６】
図１は、タスクＴｉセットの結合およびそれらの間に存在する先行関係を説明する例示的なチャート１０を示す。この種のモデリングにおいて、タスクは、ノード１によって表され、データ依存性は、アーク２によって表される。タスクＴｉをタスクＴｊに連結するアーク２は、タスクＴｊが、タスクＴｉの実行の終了後にのみ、その実行を開始できることを意味する。前に示したように、タスクへのこの細分化は、アプリケーションに存在できる計算の並列性を表し、かくして、性能制約を満たすように並列タスクを多数のプロセッサへ割り当てることによって、計算の速度を上げることを目的とする。かかるアーキテクチャは、かなりの量のエネルギを消費する。実時間の文脈では、一般に、この種のアーキテクチャは、特に最悪の場合の実行時間により各タスクを特徴付けることによって、サポートされるアプリケーションおよび順守すべき時間制約に従って最悪の場合に備えた大きさにされる。図１の表現モードにおいて、ペア（ＷＣＥＴ、ＡＥＴ）は、その第１の成分による最悪の場合の実行時間ＷＣＥＴ、およびその第２の成分による実際の実行時間ＡＥＴを各タスクＴｉ用に示す。
【００２７】
図２は、例として、２プロセッサのアーキテクチャ用に、いわゆるＥＤＦ（ｅａｒｌｉｅｓｔ  ｄｅａｄｌｉｎｅ  ｆｉｒｓｔ）スケジューリング方針に従って、図１に示したチャートモデルの最悪の場合の実行挙動を示す。以下で提示する本発明による方法は、この方針に、および特にいわゆるＬＬＦ（ｌｅａｓｔ  ｌａｘｉｔｙ  ｆｉｒｓｔ）およびＥＬＬＦ（ｅｎｈａｎｃｅｄ  ｌｅａｓｔ  ｌａｘｉｔｙ  ｆｉｒｓｔ）方針などの他のスケジューリング方針に適用してもよい。したがって、図２は、２つのプロセッサによる、図１のタスクの並列実行を提示する。これらのタスクは、図１のチャート１０によって説明した依存性に従って、２つのプロセッサＰＥ０およびＰＥ１において連続して実行される。タスクの開始時間および実行時間は、時間の関数として表される。
【００２８】
並列処理速度の変動による不活性期間２１は、例えば、第２のプロセッサＰＥ１用の時間４０および６０ならびに第１のプロセッサＰＥ０用の時間６５におけるある同期点で発生する可能性がある。これらの不活性期間が、実際の実行中に、同じ長さで同じ時間に同じプロセッサで同じように発生する場合には、アイドルモードをオフラインで計算してオンライン中に実行し、消費エネルギを低減することが可能である。残念にも、前に示したように、タスクの最悪の場合の実行時間ＷＣＥＴに対する実際のタスク実行時間の変動は、タスクの順序および起動時間を変更する可能性がある。したがって、不活性期間２１の到達時間および長さのオフライン予測は、非常に困難になる。この困難によって、タスクの実行中に発生する可能性がある、消費エネルギを低減するための機会を利用することが制限される。
【００２９】
図３は、２つのプロセッサＰＥ０およびＰＥ１による実際のタスク実行挙動を示す。この図３はまた、図２が示す最悪の場合の挙動と、実際の挙動との間にあり得る差異を示す。最悪の場合の実行時間に対するタスク実行時間の変動は、時間の超過３１を明らかにする。これらの時間の超過は、実時間制約を順守しながら、後続タスクの実行速度を減速し、したがって、消費を低減するために利用してもよい。例えば、時間３０で始まるタスクＴ９は、最悪の場合に備えて５つの時間単位に設定されたその実行時間のうちの２つの時間単位しか消費しなかったが、このタスクＴ９は、最悪の場合には時間３０と３５との間で実行される。この文脈では、タスクＴ９から回復された、３単位に等しい時間の超過３１は、後続タスクの１つに割り当てて、その実行速度を減速してもよい。タスクの実行速度の減速は、ある周波数−電圧ペアリングから、新規のより低いペアリング、すなわちより低い動作周波数およびより低い電圧への、このタスクを処理するプロセッサの切り替えに特に反映され、消費エネルギの低減を可能にする。実際には、プロセッサによって消費される電力は、動作速度の低減によって低減され得る電源電圧に２次的に依存する。次の関係は、消費電力Ｐｄｙｎａｍｉｃのこの依存性を説明する。
【数１】
2011519452.tif 000003
ここで、
−  αは、各クロックサイクルに対してハイ状態からロー状態への遷移の平均数に対応する活性係数を表す。
−  ＣＬは、遷移中に充電される静電容量を表す。
−  Ｖｄｄは、電源電圧を表す。
−  ｆｃｌｋは、回路のクロック周波数を表す。
−  Ｖｔｈは、閾値電圧を表す。
−  Ｋは、回路の特性に依存する定数である。
【００３０】
大域スケジューリングの文脈では、時間制約を破らずにエネルギを効果的に低減するために、実行中に得られた時間の超過の分配を利用することは困難である。
【００３１】
図４は、本発明による方法のインプリメンテーション用の２つの可能な段階を示す。特に、方法には、オフライン特徴付け段階４１および後続するオンライン検出および利用段階４２が含まれる。オフライン段階４１において、本方法は、所与のアプリケーションにおける潜在的な並列処理速度の経時的な傾向を特徴付ける。並列処理速度は、所与の瞬間において、アーキテクチャにおいて利用可能なプロセッサ数においてアクティブなタスク数に対応する。オフライン特徴付けから得られた情報は、続いてオンライン段階４２で用いられ、実行中に発生するであろう不活性期間の継続時間を決定する。したがって、これらの継続時間および対象プロセッサの特性に従って、アイドルモードを決定および活性化してもよい。アイドルモードのオンラインインプリメンテーションに加えて、本方法は、この段階で、タスクによって生成される全ての時間の超過を検出し、プロセッサの電圧および周波数を動的に調整して、消費をさらに低減する。
【００３２】
図５は、次の連続するサブ段階に従って、オフライン特徴付け段階４１の例示的な実施形態を提示する。
−  タスクラベリング段階５１。
−  タスクスケジューリング段階５２。
−  異なるラベルの実行開始時間および各時間において必要なプロセッサ数を記憶するための段階５３であって、記憶が、タスクの並列性を特徴付けるデータ構造において実行される段階５３。
−  アプリケーションの実行に必要なＮプロセッサ用の機能開始モードを決定するための段階５４。
【００３３】
図６は、ラベリング段階５１を示す。この段階では、本発明による方法は、アプリケーションのタスク１のチャートをラベル６１に分割する。したがって、ラベルＬｎは、逐次的に実行されそうな１つまたは複数の相互依存のタスクＴｉを組み合わせる。図６は、かかるラベリングを示す。９つのラベルＬ１、．．．Ｌ９が、１７のタスクＴ１、．．．Ｔ１７を組み合わせる。ラベルＬｎ用の構成原理は、特に、次のルールに対応する。
−  ラベルは、最大数のタスクを組み合わせる。
−  収束６２のレベルにおいて、ラベルの構成は、収束タスクの前で停止される。
−  拡散６３のレベルにおいて、ラベルの構成は、例えばブランチＬ０に沿って継続され、他のラベルは、例えば他のブランチＬ１またはＬ２用に構成される。
−  タスクは、単一のラベルにのみ属する。
【００３４】
このように、ラベルは、ただ１つに制限できるタスクの組み合わせであり、並列処理速度における１だけの増加を識別できるようにする。この増加は、このラベルのタスクを処理する追加プロセッサを必要とする可能性がある。したがって、ラベリング５１は、このラベルの最終タスクの実行の終わりに、並列処理速度の１だけの低減を同じように識別できるようにする。
【００３５】
アプリケーションのチャートが、ひとたびラベルに分割されると、チャートの大域スケジューリング５２は、オフラインで実行される。このスケジューリングは、例えば、ＥＤＦ−ＬＴＦ（最早タスクファースト−最大タスクファースト）方針によって、またはＥＬＬＦ（拡張最小余裕ファースト）方針で定義されるような静的または動的優先度に基づいてもよい。前の図２は、最悪の場合の実行時間ＷＣＥＴおよびＥＤＦ−ＬＴＦ方針に基づくことによって、チャートのかかるオフラインスケジューリングを説明している。このようにして、ひとたび最悪の場合の実行挙動が得られると、異なるラベルＬｎの実行開始時間、および各時間に必要なプロセッサの数が、データ構造に記憶される５３。
【００３６】
図７は、潜在的な最悪の場合の並列性を特徴付けるこのデータ構造を示す。開始時間７１、例えば時間０、１０、２０、３５、４０、４５、５０、５５、６０、６５およびこれらの時間のそれぞれにおいて必要なプロセッサ数７２は、連続的な記憶場所に記憶される。例えば、時間０において、ラベルＬ１のルートタスクとも呼ばれる開始タスクであるタスクＴ１だけが存在し、その実行を開始する。したがって、このタスクを処理するためには、１つの単一プロセッサが必要である。したがって、数１は、タスクの実行に必要なプロセッサ数７２として示される。例えば、時間３５において、２つのラベルＬ３およびＬ５が、それらの実行を同時に開始し、２つのプロセッサ（ここでは数２が示されている）を必要とする。２つの到達時間は、データ構造に別々に記憶される。
【００３７】
潜在的な並列性が、このように特徴付けられた後で、本方法は、アプリケーションの実行に必要なＮプロセッサ用の機能開始モードを決定する５４。これらの機能モードの全ては、以下では開始応答と呼ばれる。この応答は、潜在的な並列度を増加させる第１のＮラベルの到達によって決定される。これらは、特に図６および７によって示した前の例において、開始応答７３を設定する２つのラベルＬ０およびＬ１である。実際には、ラベルＬ０の第１のタスクＴ１を実行するために、時間０、すなわちラベル０の出現の時間から、時間１０、すなわちラベルＬ１の出現の時間まで、単一の活性プロセッサが必要とされる。
【００３８】
したがって、潜在的な並列処理速度の変動に関するかかる情報を用いれば、次のように開始応答を設定することが可能である。
−  第１のプロセッサＰＥ０は、活性である。
−  ラベルＬ１の到達時間が、「スタンバイ」状態から活性状態へ切り替わるために必要な時間より大きい場合には、第２のプロセッサＰＥ１は、「スタンバイ」タイプの不活性状態（アイドルモード）である。
【００３９】
あるモードから他のモードに切り替わる時間は、資源の特性である。それは、メーカによって供給される、資源の電力状態機械（ＰＳＭ）から得てもよい。この状態機械は、資源によってサポートされる様々なアイドル（非機能）モード、各モードに関して消費される電力、ならびにそれらの時間およびエネルギコスト伴う可能な遷移を説明する。潜在的な並列度および開始応答に関する情報が、ひとたび決定されると、消費のオンライン管理は、次の段階４２で実行してもよい。
【００４０】
次の段階４２の間に、本発明による方法は、実行中に発生する全ての不活性期間をオンラインで検出するが、これらの期間は、並列処理速度の低下のせいである。この低下は、アーキテクチャにおける活性プロセッサの数より少ない多数のアクティブタスクにおいて、所与の瞬間に反映される。ひとたび不活性期間が検出されると、本方法は、適切なＤＰＭモードを決定および活性化する。
【００４１】
実際には、プロセッサは、ペアリング（電圧、周波数）、および例えば「スタンバイ」または「スリープ」などのアイドルモードにより定義される所与の数の動作点によって特徴付けられる。ある動作点から別の動作点への資源の切り替えは、時間遅延を導入し、少なからぬ追加エネルギを必要とする。時間制約の順守、およびある動作点から別の動作点への切り替えの費用対効果を保証するために、本発明による方法は、資源をスリープにする各決定において、これらの時間およびエネルギコストプレミアム（ｅｎｅｒｇｙ  ｃｏｓｔ  ｐｒｅｍｉｕｍｓ）を考慮する。
【００４２】
アプリケーションの並列処理速度の実際の変動をオンラインで監視することによって、本発明は、同時にアクティブなラベル数の低下によるどんな不活性期間も検出する。並列処理速度のこの変動に依存して、１つまたは複数のプロセッサを、並列処理速度の潜在的増加までアイドルモードに設定してもよい。実行中に、不活性期間が、最悪の場合のモデルにおいて予測されたその出現時点より早く発生する可能性があることに留意されたい。この現象は、特に、推定された最悪の場合の実行時間ＷＣＥＴに対する、実際の実行時間ＡＥＴの変動のせいである。ひとたび不活性期間が検出されると、本発明は、プロセッサが不活性のままで到達する可能性がある時間を、オフラインで構成されたデータ構造７１および７２によってオンラインで決定する。この時間は、並列処理速度を増加させる次のラベルの、最悪の場合における到達時間に対応する。
【００４３】
アイドルモードの管理に加えて、本発明による方法によって、様々なプロセッサの電圧および動作周波数を実行中に動的に調整することが可能になる。この管理は、実行中に得られた時間の超過「余分な時間」を利用することによって実行される。これらの超過は、最悪の場合の実行時間ＷＣＥＴに対する、タスクの実際の実行時間ＡＥＴの変動のせいである。本発明によれば、これらの時間の超過は、時間制約を破らずに消費エネルギを低減するために、資源依存性に関連して後続タスクに割り当てられる。本発明による方法は、最悪の場合の実行時間に対する、タスクの実際の実行時間の変動による全ての時間の超過をオンラインで検出する。ひとたび時間の超過が検出されると、適切なペアリング（電圧、周波数）が決定および活性化される。アプリケーションの実際の実行挙動を最悪の場合の実行挙動に収束させ、かつ潜在的な並列性を特徴付けるデータを最もよく利用するために、時間の超過は、資源依存性に従って分配される。したがって、プロセッサＰｊ上で実行されるタスクＴｉによって生成された時間の超過は、プロセッサＰｊに割り当てられた後続するタスクＴｉ＋１に割り当てられる。
【００４４】
したがって、本発明には、２つのオンライン消費管理技術、すなわちＤＶＦＳタイプの技術、および別々にまたは同時に適用できるＤＰＭタイプの第２の技術が含まれる。ここで、アイドルモードの管理（ＤＰＭ）のないＤＶＦＳ技術のインプリメンテーションが、オフライン解析段階４１を必要としないことに留意されたい。実際には、時間の超過の検出および利用は、オンラインで実行される。
【００４５】
図８は、前の図によって示した場合に適用される、本発明によるＤＰＭおよびＤＶＦＳの技術の例示的なインプリメンテーションを示す。不活性期間８１が、時間３５の後でプロセッサＰＥ０において発生する。より具体的には、不活性期間を囲む領域８０を拡大することによって、不活性期間が、図２に示すように最悪の場合で計算された時間４０ではなく、時間３８で発生するように思われる。領域８０は、最悪の場合においてオフラインで計算された不活性期間８２、およびオンラインで得られた追加期間８３を示すが、追加期間８３は、時間の超過を構成する。２つの時間単位のオフセットは、図６に示すラベルＬ５の最終タスクＴ１１によって生成された時間の超過のためである。この時間の超過は、特に、関連する資源、すなわちプロセッサＰＥ０に割り当てされるタスクがこれ以上存在しないとすると、ＤＶＦＳ技術によって利用することができない。本発明によれば、この超過は、オンラインで計算された不活性期間において考慮される。この不活性期間は、オフラインで予測された不活性期間８２より長いことが多い。したがって、このオンライン利得を用いれば、オフラインで決定されたよりも意味のあるアイドルモードを実行可能である。適切なアイドルモードを決定するために、例えば、Ｓ．Ｉｒａｎｉ：  “Ｏｎｌｉｎｅ  Ｓｔｒａｔｅｇｉｅｓ  ｆｏｒ  Ｄｙｎａｍｉｃ  Ｐｏｗｅｒ  Ｍａｎａｇｅｍｅｎｔ  ｉｎ  Ｓｙｓｔｅｍｓ  ｗｉｔｈ  Ｍｕｌｔｉｐｌｅ  Ｐｏｗｅｒ−Ｓａｖｉｎｇ  Ｓｔａｔｅｓ”，  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｅｍｂｅｄｄｅｄ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ，  Ｖｏｌ．２，  Ｎ°３，  Ａｕｇｕｓｔ  ２００３，  ｐａｇｅｓ  ３２５−３４６による文献Ｄ４に特に説明されているいわゆるＬＥＡ（ロウアーエンベロープアルゴリズム（ｌｏｗｅｒ  ｅｎｖｅｌｏｐｅ  ａｌｇｏｒｉｔｈｍ））アルゴリズムを用いることが可能である。実際には、このアルゴリズムは、時間制約の順守を保証するために、資源をスリープにして復活させることに関して時間およびエネルギコストプレミアムを考慮するように拡張することができる。
【００４６】
図８はまた、実行中に得られた時間の超過の例示的な分配を示す。例えば、タスクＴ９によって生成された時間の超過８４は、タスクＴ１０がタスクＴ９の直後に実行されるとすると、同じプロセッサＰＥ１上でタスクＴ１０によって消費される。最悪の場合の実行挙動では、タスクＴ９の終了は、時間３５と推定されたのに対して、その実際の実行は、時間３２で終了する。したがって、３つの時間単位の時間の超過がある。同様に、タスクＴ７によって生成された、２つの時間単位に等しい時間の超過８５は、同じプロセッサＰＥ０上で次のタスクＴ１１に割り当てられる。また、このタスクＴ１１（図７で示すような収束タスクである）のレベルにおいて、時間の超過が失われないことが明らかに分かる。
【００４７】
得られた超過８４および８５は、適切なＤＶＦＳモードに従って、この超過を生成したタスクを処理するプロセッサを、あるペアリング（周波数、電圧）から新規のより低い電力ペアリングに切り替え、かくして、消費エネルギの低減を可能にするように用いられる。図８は、オフラインで推定された不活性期間８２における利得に加えられる、オンラインで得られた電力利得８６、８７および８３を明らかに示す。
【００４８】
実際には、ちょうど実行されたタスクが、同じプロセッサ上の次のタスクがＤＶＦＳモードを活性化するには不十分な時間の超過を生成することがあり得る。この文脈では、超過は、ＤＶＦＳモードを活性化するために十分に長い超過が得られるまで集約される。この解決法はまた、最適化の理由で実行してもよい。実際には、別々に考慮される超過によって活性化されるようなモードより有利なＤＶＦＳモードを後で活性化するために、多数の時間の超過を資源上に集約してもよい。この場合には、時間の超過は、ラベルによって指定された並列ブランチの実行全体にわたって集約される。様々なプロセッサにおいて集約された時間の超過は、それらを最終タスク（ラベル最後のタスクである）に割り当てることによって、収束の前に利用される。
【００４９】
オンライン消費管理は、ＤＰＭおよびＤＶＦＳ技術の両方を組み合わせることによって有利に実行可能である。この組み合わせによって、本発明は、収束における異なるブランチによって生成された超過を含む全ての時間の超過を例外なしに利用することが可能になる。それは、タスクによって生成された超過を、同じ資源に割り当てられた次のタスクに割り当てながら、最悪の場合の実行挙動を再現する。超過を分配するためのこの方法は、実行中に、オフラインで予測された時間における各不活性期間を明らかにする。この期間に加えて、本発明は、この不活性期間を延長しそうなどんな時間の超過も検出する。この超過は、同時にアクティブなラベル数の低下によるこの不活性期間の発生の直前に実行されるラベル最後のタスクによって生成される。前に示したように、不活性期間の直前に発生する時間の超過は、ＤＶＦＳタイプの技術によって利用することができない。この限界は、ＤＰＭ技術を用いることにより本発明によって取り除かれる。したがって、ひとたび不活性期間が検出されると、適切なアイドルモードが、オンラインで決定および活性化される。
【００５０】
本発明に従って実行されるオンライン消費管理は、非周期的および周期的なアプリケーションの文脈において適用可能である。アプリケーションの終わりに様々なプロセッサの、到達応答と呼ばれる到達機能モードを定義することで十分である。この到達応答に基づいて、最後のＮラベルの各最終タスクの実行の終わりに、資源が設定され得る適切なアイドルモードが、オンラインで決定される。例えば、図６および８のそれぞれのタスクＴ１６およびＴ１７を備えた最後の２つのラベルＬ８およびＬ９の終わりは、２つのプロセッサの解放を示す。図８は、時間６０において、ラベルＬ８が、タスクＴ１６の終わりでその実行を終了し、プロセッサＰＥ０を解放することを示す。同様に、時間６５において、タスクＴ１７の終わりで実行を終了するのはアプリケーションＬ９の最終ラベルである。したがって、これらのラベルのそれぞれにおける実行の終わりに、検出された不活性期間８８、８９に従って、アイドルモードを決定することができる。
【００５１】
周期的なアプリケーションに対して、アプリケーションの様々な繰り返しにおけるＤＰＭモードの管理は、第１の繰り返しに対応するラベルの到達時間および潜在的な並列度を記述する同じデータ構造を用いることによって、有効なままである。各繰り返し用にラベルの到達時間を更新することで十分である。順序ｊ＋１の繰り返しにおけるラベルｉの到達時間は、繰り返しｊにおけるその到達時間＋アプリケーションの周期Ｔに等しい。この場合には、到達応答に対応するアイドルモードが、各繰り返しの終わりにオンラインで計算される。これらのモードは、次の繰り返しの第１のＮラベルの到達時間の関数として計算される。
【００５２】
マルチアプリケーションおよび同一のアプリケーションのマルチインスタンスの文脈では、潜在的な並列性は、各アプリケーション用の最悪の場合において特徴付けられる。時間制約を保証するために、アーキテクチャは、それがサポートしなければならないアプリケーションの数およびアプリケーションのそれぞれにおけるインスタンスの数に従った大きさにされなければならない。この場合には、資源は、アプリケーションおよび／またはインスタンスの数に従って増加される。例えば、システムが、２つのプロセッサを必要とする所与のアプリケーション、および３つのプロセッサを必要とする、別のアプリケーションの２つのインスタンスを並列に実行することを目的とする場合には、アーキテクチャは、８つのプロセッサを組み込まなければならない。この場合には、消費管理を備えた２つのスケジューリングバージョンの１つを実行してもよい。
【００５３】
様々なアプリケーションおよび／またはインスタンスから来るタスクの大域スケジューリングを用いた資源の全体共有に基づいた第１のバージョンを用いてもよい。このバージョンを用いれば、資源依存性に従う超過の分配は、有効なままである。したがって、所与のアプリケーションから来るタスクによって生成された時間の超過は、別のアプリケーションから来るタスクに（これらの２つのタスクが同じ資源に割り当てられている限り）、割り当ててもよい。ＤＰＭモードの管理に関しては、様々なアプリケーションおよびそれらのインスタンスの潜在的な並列処理速度のモデリングに対応する、異なるデータ構造のオンライン結合を含む動作が、適所に入れられる。この結合は、特に、各アプリケーションおよび／またはインスタンスのラベルの到達時間を更新し、それらを昇順に結合することに存する。結果としての構成は、単一のアプリケーション文脈の構成と同じように利用される。
【００５４】
第２のバージョンは、タスクレベルにおける大域スケジューリングを用い、かつアプリケーションレベルにおける区分化によって、各アプリケーションおよび／またはインスタンス用に資源を確保しておくことに基づいている。より具体的には、各アプリケーション／インスタンスのタスクの実行は、大域スケジューリングおよび各アプリケーション／インスタンス用に確保された資源に制限された割り当てに基づいて実行される。この場合には、時間の超過の分配は、資源依存性に関するのと同じ方法で管理される。アプリケーションによる資源の分配を用いれば、所与のアプリケーションのタスクによって得られた時間の超過は、同じアプリケーションの他のタスクによって利用される。したがって、時間の超過は、２つの異なるアプリケーション間では共有されない。ＤＰＭモードは、それぞれ別々に考慮される異なるアプリケーションから得られる、潜在的な並列性を特徴付けるデータに基づくことによって、別々に管理される。
【図１】
2011519452.tif 000004
【図２】
2011519452.tif 000005
【図３】
2011519452.tif 000006
【図４】
2011519452.tif 000007
【図５】
2011519452.tif 000008
【図６】
2011519452.tif 000009
【図７】
2011519452.tif 000010
【図８】
2011519452.tif 000011
【国際調査報告】
2011519452.tif 000012
2011519452.tif 000013
2011519452.tif 000014
2011519452.tif 000015
2011519452.tif 000016
2011519452.tif 000017