オンライン問題に対する平均的競合比の解析

モバイル情報機器の開発において、長時間バッテリ駆動のための消費電力の効果的な制御が注目を集めている。近年、動的にスピード変更なプロセッサが幅広く用いられるようになっている。ここで重要となってくるのがスピードスケーリング問題である。すなわち、総消費電力量を低く抑えるには、逐次投入されるジョブをどのようなスピードで実行するのが最適な戦略であろうか。従来の研究では、各ジョブに処理完了期限が設定されたうえで消費電力を抑えるモデルが考えられてきた。しかしこれではジョブは期限以前であればいつ完了しても許されるので、重要なQoSの要素であるジョブの応答時間を無視していることになる。我々は、ジョブ完了期限を一切なくした上で、ジョブの滞在時間と消費電力の和をコストと考えるモデルを提案する。このことにより電力量と応答時間のトレードオフを考慮したスケジュールを得ることが可能である。我々は、単位時間当たりの消費電力量と総滞在時間の増分に着目し、これらの比をある一定の比に維持するフェーズバランシングアルゴリズムPHASEBALを設計した。このアルゴリズムでは単位時間当たりの消費電力量と総滞在時間の増分の比が一定に保たれることにより、消費電力量と総滞在時間のどちらか一方が無限大に発散するリスクが回避される。解析の結果、PHASEBALが最悪評価において有界な競合比を持つことを証明した。さらにオフラインケース(将来のジョブ投入予定が既に分かっている場合)に対し、最適なスケジュールを得るアルゴリズムを設計した。このアルゴリズムは動的計画法に基づいたもので、多項式時間で計算可能である。この結果は国際会議STACS2006で発表した。

モバイル情報機器の開発において、長時間バッテリ駆動のための消費電力の効果的な制御が注目を集めている。近年、動的にスピード変更なプロセッサが幅広く用いられるようになっている。ここで重要となってくるのがスピードスケーリング問題である。すなわち、総消費電力量を低く抑えるには、逐次投入されるジョブをどのようなスピードで実行するのが最適な戦略であろうか。従来の研究では、各ジョブに処理完了期限が設定されたうえで消費電力を抑えるモデルが考えられてきた。しかしこれではジョブは期限以前であればいつ完了しても許されるので、重要なQoSの要素であるジョブの応答時間を無視していることになる。我々は、ジョブ完了期限を一切なくした上で、ジョブの滞在時間と消費電力の和をコストと考えるモデルを提案する。このことにより電力量と応答時間のトレードオフを考慮したスケジュールを得ることが可能である。我々は、単位時間当たりの消費電力量と総滞在時間の増分に着目し、これらの比をある一定の比に維持するフェーズバランシングアルゴリズムPHASEBALを設計した。このアルゴリズムでは単位時間当たりの消費電力量と総滞在時間の増分の比が一定に保たれることにより、消費電力量と総滞在時間のどちらか一方が無限大に発散するリスクが回避される。解析の結果、PHASEBALが最悪評価において有界な競合比を持つことを証明した。さらにオフラインケース(将来のジョブ投入予定が既に分かっている場合)に対し、最適なスケジュールを得るアルゴリズムを設計した。このアルゴリズムは動的計画法に基づいたもので、多項式時間で計算可能である。この結果は国際会議STACS2006で発表した。