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

在线问题平均竞争比分析

• 批准号: 04J00740
• 负责人: 藤原 洋志
• 金额: $ 1.22万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-04J00740/
• 关键词: オンラインアルゴリズム; 競合比; スケジューリング; スピードスケーリング

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

The development of information technology, long-term rapid development and the effect of power consumption control focus In recent years, the development of smart computers has become increasingly popular and available in a wide range of applications. This is a very important issue. The power consumption is low, and the input is low. In the future, the research will be completed by setting the time limit for the consumption of electricity. The time required for the QoS response is ignored. We have a deadline, a deadline The power supply and response time should be considered. We design the PHASEBAL for the consumption of electricity and the increase in the time of the unit, and for the maintenance of a certain ratio of the unit to the time of the unit. The ratio of power consumption to total delay time is constant, and the ratio of power consumption to total delay time is infinite. The result of analysis, PHASEBAL, is the most important evaluation. For example, if the future investment is determined, the project will be designed according to the requirements of the project. This is a simple, polynomial time algorithm. The results were presented at the international conference STACS2006.