Performance Analysis of Power-Aware Task Scheduling Algorithms on Multiprocessor Computers with Dynamic Voltage and Speed

Task scheduling on multiprocessor computers with dynamically variable voltage and speed is investigated as combinatorial optimization problems, namely, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems where timing constraint is a major requirement. These problems emphasize the tradeoff between power and performance and are defined such that the power-performance product is optimized by fixing one factor and minimizing the other. It is found that both problems are equivalent to the sum of powers problem and can be decomposed into two subproblems, namely, scheduling tasks and determining power supplies. Such decomposition makes design and analysis of heuristic algorithms tractable. We analyze the performance of list scheduling algorithms and equal-speed algorithms and prove that these algorithms are asymptotically optimal. Our extensive simulation data validate our analytical results and provide deeper insight into the performance of our heuristic algorithms.     

Power and performance management for parallel computations in clouds and data centers

We address scheduling independent and precedence constrained parallel tasks on multiple homogeneous processors in a data center with dynamically variable voltage and speed as combinatorial optimization problems. We consider the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on multiple processors. Our approach is to use level-by-level scheduling algorithms to deal with precedence constraints. We use a simple system partitioning and processor allocation scheme, which always schedules as many parallel tasks as possible for simultaneous execution. We use two heuristic algorithms for scheduling independent parallel tasks in the same level, i.e., SIMPLE and GREEDY. We adopt a two-level energy/time/power allocation scheme, namely, optimal energy/time allocation among levels of tasks and equal power supply to tasks in the same level. Our approach results in significant performance improvement compared with previous algorithms in scheduling independent and precedence constrained parallel tasks.     

Energy efficient scheduling of parallel tasks on multiprocessor computers

In this paper, scheduling parallel tasks on multiprocessor computers with dynamically variable voltage and speed are addressed as combinatorial optimization problems. Two problems are defined, namely, minimizing schedule length with energy consumption constraint and minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor and multicore processor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems and environments where timing constraint is a major requirement. Our scheduling problems are defined such that the energy-delay product is optimized by fixing one factor and minimizing the other. It is noticed that power-aware scheduling of parallel tasks has rarely been discussed before. Our investigation in this paper makes some initial attempt to energy-efficient scheduling of parallel tasks on multiprocessor computers with dynamic voltage and speed. Our scheduling problems contain three nontrivial subproblems, namely, system partitioning, task scheduling, and power supplying. Each subproblem should be solved efficiently, so that heuristic algorithms with overall good performance can be developed. The above decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. A unique feature of our work is to compare the performance of our algorithms with optimal solutions analytically and validate our results experimentally, not to compare the performance of heuristic algorithms among themselves only experimentally. The harmonic system partitioning and processor allocation scheme is used, which divides a multiprocessor computer into clusters of equal sizes and schedules tasks of similar sizes together to increase processor utilization. A three-level energy/time/power allocation scheme is adopted for a given schedule, such that the schedule length is minimized by consuming given amount of energy or the energy consumed is minimized without missing a given deadline. The performance of our heuristic algorithms is analyzed, and accurate performance bounds are derived. Simulation data which validate our analytical results are also presented. It is found that our analytical results provide very accurate estimation of the expected normalized schedule length and the expected normalized energy consumption and that our heuristic algorithms are able to produce solutions very close to optimum.     

基于HVACSIM+和MATLAB的空调系统仿真研究

研究了空调系统的仿真及一定温度要求下的最小能耗优化控制。介绍了大型空调系统仿真软件HVACSIM+;以某大厦一层中央空调系统的空气处理系统以及空调房间为仿真对象,进行HVACSIM+系统仿真;建立了表冷器的能耗与冷冻水流速之间的函数关系,将此作为目标函数,在MATLAB环境下,应用改进的变量轮换法优化控制器参数,经HVACSIM+再次仿真运行,计算冷源向空调系统提供的能耗。仿真结果表明,优化参数下的仿真系统运行稳定,与优化前相比,经表冷器消耗的能量大大减少。     

一种基于关键路径分析的CPU-GPU异构系统综合能耗优化方法

GPU强大的计算性能使得CPU-GPU异构体系结构成为高性能计算领域热点研究方向.虽然GPU的性能/功耗比较高,但在构建大规模计算系统时,功耗问题仍然是限制系统运行的关键因素之一.现在已有的针对GPU的功耗优化研究主要关注如何降低GPU本身的功耗,而没有将CPU和GPU作为一个整体进行综合考虑.文中深入分析了CUDA程序在CPU-GPU异构系统上的运行特点,归纳其中的任务依赖关系,给出了使用AOV网表示程序执行过程的方法,并在此基础上分析程序运行的关键路径,找出程序中可以进行能耗优化的部分,并求解相应的频率调节幅度,在保持程序性能不变的前提下最小化程序的整体能量消耗.     

一种满足可靠性和能效的云工作流调度方法

为了同步解决云工作流调度时的失效和高能耗问题,提出一种基于可靠性和能效的工作流调度算法.算法为了在截止时间的QoS约束下最大化系统可靠性并最小化调度能耗,将工作流调度过程划分为四个阶段:计算任务优先级、工作流任务聚簇、截止时间子分配和任务调度.算法在满足执行次序的情况下对任务进行拓扑排序,并以通信代价最小为目标对任务进...     

风电介入下的多区域互联电力系统分布式经济模型预测负荷频率控制

针对风电介入下的多区域互联电力系统,提出一种分布式经济模型预测负荷频率控制策略.通过将大规模互联电力系统分解成若干个动态耦合的子系统,这些子系统能够利用网络交流并共享信息,使得各区域的控制器实现各自优化问题的求解.同时,在满足状态约束和控制输入约束的前提下,遵循传统火力发电优先、风力发电配合的原则,通过在线求解优化问题,实现风电介入下的多区域互联电力系统的负荷频率控制.为了提高系统整体运行经济性,所提出的分布式经济模型预测控制器将负荷调频成本、燃料消耗成本以及风力发电成本等经济性指标考虑在内.仿真结果表明,在阶跃负荷扰动下,所设计的控制器不仅可以满足调频要求,在降低计算负担和提高经济性能方面也具有一定优势.     

Reactive control of overall power consumption in flexible manufacturing systems scheduling: A Potential Fields model

In recent years, designing “energy-aware manufacturing scheduling and control systems” has become more and more complex due to the increasing volatility and unpredictability of energy availability, supply and cost, and thus requires the integration of highly reactive behavior in control laws. The aim of this paper is to propose a Potential Fields-based flexible manufacturing control system that can dynamically allocate and route products to production resources to minimize the total production time. This control system simultaneously optimizes resource energy consumption by limiting energy wastage through the real-time control of resource states, and by dynamically controlling the overall power consumption taking the limited availability of energy into consideration. The Potential Fields-based control model was proposed in two stages. First, a mechanism was proposed to switch resources on/off reactively depending on the situation of the flexible manufacturing system (FMS) to reduce energy wastage. Second, while minimizing wastage, overall power consumption control was introduced in order to remain under a dynamically determined energy threshold. The effectiveness of the control model was studied in simulation with several scenarios for reducing energy wastage and controlling overall consumption. Experiments were then performed in a real FMS to prove the feasibility of the model. The superiority of the proposition is its high reactivity to manage production in real-time despite unexpected restrictions in the amount of energy available. After providing the limitations of the work, the conclusions and prospects are presented.     

Analyzing GPU-controlled communication with dynamic parallelism in terms of performance and energy

Graphic Processing Units (GPUs) are widely used in high performance computing, due to their high computational power and high performance per Watt. However, one of the main bottlenecks of GPU-accelerated cluster computing is the data transfer between distributed GPUs. This not only affects performance, but also power consumption. The most common way to utilize a GPU cluster is a hybrid model, in which the GPU is used to accelerate the computation, while the CPU is responsible for the communication. This approach always requires a dedicated CPU thread, which consumes additional CPU cycles and therefore increases the power consumption of the complete application. In recent work we have shown that the GPU is able to control the communication independently of the CPU. However, there are several problems with GPU-controlled communication. The main problem is intra-GPU synchronization, since GPU blocks are non-preemptive. Therefore, the use of communication requests within a GPU can easily result in a deadlock. In this work we show how dynamic parallelism solves this problem. GPU-controlled communication in combination with dynamic parallelism allows keeping the control flow of multi-GPU applications on the GPU and bypassing the CPU completely. Using other in-kernel synchronization methods results in massive performance losses, due to the forced serialization of the GPU thread blocks. Although the performance of applications using GPU-controlled communication is still slightly worse than the performance of hybrid applications, we will show that performance per Watt increases by up to 10% while still using commodity hardware.     

面向WSN的自适应模糊功率控制算法研究

在无线传感器网络环境中存在干扰以及网络的动态变化等原因,传输可靠性问题成为保障网络服务性能的重要挑战之一。现有的研究方法基本没有考虑网络的动态性,节点能耗较高。为此,我们提出了一种面向WSN的自适应模糊功率控制算法DAFPC。该算法采用自适应模糊理论,并基于“输入-输出-反馈”机制,根据接收到的链路质量参数信息自适应地调整控制器,快速地调节发射功率。研究仿真结果表明,DAFPC算法能很好地适应网络的动态变化,有效地提高WSN的抗干扰性和传输可靠性,延长了网络的生存时间。     

An energy-aware scheduling algorithm under maximum power consumption constraints

This research investigates the production scheduling problems under maximum power consumption constraints. Probabilistic models are developed to model dispatching-dependent and stochastic machine energy consumption. A multi-objective scheduling algorithm called the energy-aware scheduling optimization method is proposed in this study to enhance both production and energy efficiency. The explicit consideration of the probabilistic energy consumption constraint and the following factors makes this work distinct from other existing studies in the literature: 1) dispatching-dependent energy consumption of machines, 2) stochastic energy consumption of machines, 3) parallel machines with different production rates and energy consumption pattern, and 4) maximum power consumption constraints. The proposed three-stage algorithm can quickly generate near-optimal solutions and outperforms other algorithms in terms of energy efficiency, makespan, and computation time. While minimizing the total energy consumption in the first and second stages, the proposed algorithm generates a detailed production schedule under the probabilistic constraint of peak energy consumption in the third stage. Numerical results show the superiority of the scheduling solution with regard to quality and computational time in real problems instances from manufacturing industry. While the scheduling solution is optimal in total energy consumption, the makespan is within 0.6 % of the optimal on average.     

基于可靠性技术的智能温度控制器设计与实现

针对传统温度控制器存在可靠性低、经济性差、能耗高和智能化弱等问题,研究出一款基于可靠性设计技术实现的智能温度控制器.在阐述智能温控器总体设计思路的基础上,通过采用故障预测与健康管理技术设计了主控制模块,实现了温控器的故障检测、诊断和预测功能,应用可靠性技术设计了电源模块、人机交互模块、晶振模块、数据存储模块、接口模块等子系统,实现了对环境温度参数的自动控制和人工智能管理,满足了控制器的可靠性和测试性设计要求.智能温度控制器经测试和试生产,结果表明设计方案可行,具有良好的市场前景,达到了节约能源和节约管理人力、物力的要求,对促进同类控制器产品设计技术进步有着重要的借鉴意义.     

Constrained Markov control model and online stochastic optimization algorithm for power conservation in multimedia server cluster systems

This paper presents a novel Markov switching state space control model for dynamically switching resource configuration scheme to achieve power conservation for multimedia server cluster systems. This model exploits the hierarchical dynamic structure of network system and its construction is flexible and scalable. Using this analytical model, the problem of power conservation is posed as a constrained stochastic optimization problem with the goal of minimizing the average power consumption subject to the constraint on the average blocking ratio. Applying Lagrange approach and online estimation of the performance gradient, a policy iteration algorithm is proposed to search the optimal policy online. This algorithm does not depend on any prior knowledge of system parameters, and converges to the optimal solution. Simulation results demonstrate the convergence of the proposed algorithm and effectiveness to different access workloads.     

模型指导的多维GPU软件低功耗优化方法

作为众核体系结构的典型代表,GPU(Graphics Processing Units)芯片集成了大量并行处理核心,其功耗开销也在随之增大,逐渐成为计算机系统中功耗开销最大的组成部分之一,而软件低功耗优化技术是降低芯片功耗的有效方法.文中提出了一种模型指导的多维低功耗优化技术,通过结合动态电压/频率调节和动态核心关闭技术,在不影响性能的情况下降低GPU功耗.首先,针对GPU多线程执行模型的特点,建立了访存受限程序的功耗优化模型;然后,基于该模型,分别分析了动态电压/频率调节和动态核心关闭技术对程序执行时间和能量消耗的影响,进而将功耗优化问题归纳为一般整数规划问题;最后,通过对9个典型GPU程序的评测以及与已有方法的对比分析,验证了该文提出的低功耗优化技术可以在不影响性能的情况下有效降低芯片功耗.     

基于T-S模糊模型的转台鲁棒最优控制器设计

针对飞行器仿真转台系统的非线性以及不确定性问题,提出了基于T-S模糊模型的鲁棒最优控制器设计方法.首先,利用IF-THEN模糊规则将转台速度环系统的状态空间分成不同的区域,构建具有参数不确定性的T-S模糊模型;然后,根据给定的最优性能指标要求以及控制输入约束,通过求解一组线性矩阵不等式(LMIs)进行鲁棒最优控制嚣设计.仿真结果表明,该方法不仅具有比较好的控制效果,而且能有效地解决控制输入约束问题,并能很好地保证对参数变化的鲁棒稳定性.     

无线体域网低能耗功率控制与分布式调度算法

传输能耗在无线体域网的能耗中占比最大,降低传输能耗的核心是解决2个问题:传输时隙到来时选择哪个节点传输和所选节点以何种功率传输.针对前者现有调度算法忽视网络公平性要求的局限性,提出了一种包含公平性指数的分布式调度算法;针对后者当前功率控制算法采用固定函数模型的局限性,设计了一种基于比例—积分—微分的单输出神经网络(SPIDNN)自适应网络功率机制动态调整无线体域网中传感器节点的发射功率控制方法.仿真实验表明:相对其他方案,方案在保证网络公平性的前提下,降低了能量消耗.     

An efficient routing scheme with optimal power control in wireless multi-hop sensor networks

Power consumption is a critical problem in providing multimedia communications among wireless sensor nodes (WSNs). To reduce power consumption and satisfying QoS requirements, in this paper, we propose an efficient routing scheme with optimal power management and on-demand quality control for WSNs. Two cost functions are developed to minimize the transmitting power and maximize the link quality under the constraint that an end-to-end frame error probability should be met. The heuristic problem of minimizing power consumption under frame error constraints is formulated and resolved with a closed-form expression. With this closed-form expression, we can determine an optimal route rapidly by calculating the power requirement for each sensor node. Finally, our analytical results indicate that the proposed scheme is superior to a previous work with the same constraint and is also comparable to the results obtained from a heuristic simulation.     

一类模型不确定系统的最优跟踪性能

在内模控制(IMC)结构下，对控制能量存在约束时一类不确定系统所能达到的最优跟踪性能进行了探讨．首先针对一类相加模型误差的描述，定义了一个平均意义上的包含跟踪误差和控制能量的性能指标．然后通过谱分解极小化该性能指标，导出一个最优的控制器设计方法，可以兼顾模型不确定性和控制能量约束，在实际控制系统设计中可用来对最优跟踪性能和控制能量进行预估．     

A MAC layer power management scheme for efficient energy delay tradeoff in a WLAN

Energy efficient operation is of paramount importance for battery-powered wireless nodes. In an effort to conserve energy, standard protocols for WLANs have the provision for wireless nodes to “sleep” periodically. In this paper we first consider the problem of optimizing the timing and duration of the sleep state of a single wireless node (or user) with the objective of minimizing power consumption with respect to a QoS constraint. The QoS parameter that we have focused on is average packet delay. Using a Dynamic Programming formulation, coupled with a duality argument, we solve the optimization problem numerically. Using a branching process analysis, we were able to derive closed form expressions for the optimal sleep duration, as well as the associated minimal rate of power consumption. We show that the optimal power cost derived from the one-user Dynamic Programming (DP) formulation provides a lower bound to the average power consumption for the multiple user case. To gain better insight into the optimal sleep policy we also formulate and solve a two-user optimization problem, similar to the one user case. Although the complexity of the DP approach grows very quickly with the number of users, the insights gained from the DP approach led us to design a simple, centralized, adaptive algorithm for assigning the sleep duration of an arbitrary number of wireless nodes operating in an infrastructure mode served by a single Access Point (AP). Our algorithm adapts dynamically to the packet arrival rate and statistics, as well as the tolerable average packet delay. We describe two different service policies – the Round Robin scheme and the Shortest Sleep First (SSF) scheme. The Round Robin scheme is the preferred service policy when all wireless nodes in the system have the same packet arrival statistics and the same tolerable average delay. The SSF Scheme is designed mainly for a system where nodes are heterogeneous with different tolerable average packet delay. Simulation results show that the power efficiency of our algorithm is comparable to the bound on performance that is obtained from the one-user dynamic programming formulation.