An Online Power-Efficient Scheduling Algorithm for Multiprocessor Systems

您当前的位置：

首页 >

文章列表页 >

An Online Power-Efficient Scheduling Algorithm for Multiprocessor Systems

更新时间：2025-07-09

- An Online Power-Efficient Scheduling Algorithm for Multiprocessor Systems
- Vol. 44, Issue 8, Pages: 15-19(2010)
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP301
- Online First：10 August 2010，
  
  Published：2010
- 稿件说明：
移动端阅览
An Online Power-Efficient Scheduling Algorithm for Multiprocessor Systems[J]. 2010, 44(8): 15-19.
DOI：

An Online Power-Efficient Scheduling Algorithm for Multiprocessor Systems[J]. 2010, 44(8): 15-19. DOI：

摘要

针对当前多处理器系统中的散热瓶颈问题

基于处理器动态速度调节技术

提出了一种在线低功耗调度算法(PEQUI).PEQUI以动态均衡算法(EQUI)为基础

公平地分配处理器资源

依据处理器功耗与运行速度间存在非线性关系

以正比于系统任务数的方式调节处理器运行速度.与传统低功耗调度算法相比

PEQUI仅基于当前待调度任务的信息进行决策

决策参数少.以能量消耗与任务执行流时间为评价算法性能的指标

利用在线竞争分析方法证明了PEQUI算法与最优离线算法相比可达到常数竞争比(<10).模拟结果表明

PEQUI比最近到达处理器共享算法(LAPS)和恒速EQUI算法能更好地优化系统整体性能和能量消耗.在相同负载情况下

与LAPS相比

PEQUI在降低功耗的同时系统平均运行时间也降低了近7%.

Abstract

Aiming at addressing the bottleneck problem of heat dissipation in multiprocessor systems

an online power-efficient scheduling algorithm PEQUI is proposed based on the dynamic speed scaling technique. PEQUI is capable of fairly allocating processor resources by applying the dynamic partitioning strategy(EQUI). Moreover

PEQUI adjusts processor speeds in proportion to the number of active jobs by taking the non-linear relationship between processor's power consumption and its execution speed into account. Compared with traditional power-efficient algorithms

PEQUI is able to make irrevocable decisions by using only information of the current active jobs

and needs fewer decision-making parameters. Online competitive analysis and a comparison with the optimal offline algorithm show that PEQUI achieves a constant competitive ratio with respect to the total execution time and energy. Simulation results show that PEQUI achieves better performance and lower power consumption than algorithms such as the latest arrival processor sharing(LAPS)and EQUI-based strategies with constant speed. A comparison with LAPS under the same workloads shows that PEQUI effectively reduces power consumption while the execution time reduces near 7%.

关键词

Keywords

references

YAO F, DEMERS A, SHENKER S. A scheduling model for reduced CPU energy[C]∥Proceedings of FOCS. Piscataway, NJ, USA: IEEE, 1995:374-382.

KWON W C, KIM T. Optimal voltage allocation techniques for dynamically variable voltage processors [J]. ACM Transactions on Embedded Computing Systems, 2005, 4(1):211-230.

IRANI S, SHUKLA S, GUPTA R. Algorithms for power savings [J]. ACM Transactions on Algorithms, 2007, 3(4):41-64.

ALBERS S, FUJIWARA H. Energy-efficient algorithms for flow time minimization [J]. ACM Transaction on Algorithms, 2007, 3(4):49-66.

BANSAL N, PRUHS K, STEIN C. Speed scaling for weighted flow time [C]∥Proceedings of SODA. New York, USA: ACM, 2007:805-813.

LAM T W, LEE L K, TO I, et al. Speed scaling functions for flow time scheduling based on active job count [C]∥Proceedings of ESA. Berlin, Germany: Springer, 2008: 647-659.

CHAN Ho-Leung, EDMONDS J, LAM T W, et al. Nonclairvoyant speed scaling for flow and energy [C]∥Proceedings of STACS, Berlin, Germany: Springer, 2009: 409-420.

EDMONDS J. Scheduling in the dark [C]∥Proceedings of STOC. New York, USA: ACM, 1999:179-188.

PRUHS K. Competitive online scheduling for server systems [J]. ACM SIGMETRICS Performance Evaluation Review, 2007, 34(4):52-58.

CAO Yangjie, SUN Hongyang, SHU Wenjing, et al. Malleable-lab: a tool for evaluating adaptive online schedulers on malleable jobs [C]∥Proceedings of PDP. Piscataway, NJ, USA: IEEE, 2010:11-18.

DOWNEY A B. A parallel workload model and its implications for processor allocation [C]∥Proceedings of HPDC. New York, USA: ACM, 1997:112-124.

CIRNE W, BERMAN F. A comprehensive model of the supercomputer workload [C]∥Proceedings of 4th Workshop on Workload Characterization. New York, USA: ACM, 2001: 140-148.

利用投影时序逻辑的多内核进程调度建模与验证. 西安交通大学学报,2010,44(3):52-57.

基于反馈的片上多处理器系统层次负载平衡算法. 西安交通大学学报,2008,42(2):179-183.

曙光5000A天体大规模数值模拟软件性能测试. 西安交通大学学报,2009,43(10):71-75.

自适应大规模服务器集群监控系统的构建. 西安交通大学学报,2008,42(4):399-403.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Competitive Analysis about Online Problem of Kidney Transplantation Acceptance Decision-Making

Online Exchange Mechanism of Organ Network

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

A Structure-Semantics-Residual Collaborative Image Compression Framework：Towards Privacy Protection and High-Fidelity Reconstruction

Mechanism and Optimal Control Strategy for Hysteresis in Rapid Dehumidification Response of Indirect Thermal Systems in Electric Vehicles

Related Author

王嘉寅 1

许晓雯 2

许晓雯 1

王嘉寅 3

唐佩佳 4

王玉珏 5

Related Institution

西安交通大学管理学院

西安交通大学过程控制与效率工程教育部重点实验室

⁰