Research On Energy-Efficient Techniques For Unipreocessor And Multiprocessor Systems

With the significant increasement of digitalization, the energy efficiency problem for all kinds of computing systems becomes more and more crucial. Enery-efficient techniques determine not only the lifetime of battery-operated embedded systems but also the electicity cost of large scale systems, like server farms and Internet Data Center. In order to expand embedded systems’lifetime and reduce the operating cost of large scale systems, there is lots of researching effort on energy-efficient techniques in both software and hardware level. For hardware techniques, most modern processors are enabled to support dynamic voltage/frequency scaling (DVS) where processors can run on different voltage/frequency levels. Meanwhile, nearly all types of off-chip devices are equipped with dynamic power management (DPM) where devices can work at different operating modes. For software techniques, adjusting the operating frequencies of processors for the workload, task partition and scheduling, regulating devices’s working mode are widely-used approaches to reduce energy consumption. Nowadays, as the number of off-chip devices grows and multicore architectures become even more popular, the multi-resource and multicore systems’ energy-efficient problem have been drawing more and more attention from both academic and industry communities.This dissertation studies the energy-efficient problems for uniprocessor systems with multi-resource and multicore systems when considering timing constraints. For uniprocessor systems, according to the ratio of the processor power consumption to the devices’power, different approaches are proposed to solve the problem effectively. For multicore systems, different approaches are proposed to deal with systems with different cluster partitions and different executing models accordingly. To be specific, the dissertation contributes in the following points:(1) For a uniprocessor system where the processor power dominates the system power or the power of devices is negligible or constant, several improvements for ES-RHS algorithm are proposed by taking account of both the schedulability test and the time/energy overhead due to processor mode switching. A new schedulability test condition which heavily reduces the pessimism is first presented. Then, the power consumption can be reduced by merging the tasks together and eliminating the idle mode of processor, thus decreasing greatly the number of mode switching acts. Furthermore, the constraint on the sleeping time of the processor in every harmonic period is relaxed and the proposed approaches are applicable to more types of processors in comparison to ES-RHS.(2) For a uniprocessor system where some device’s power dominates the system power or the power of other components is negligible or constant, the dissertation studies the energy-efficient problem in wireless sensor networks (WSNs). WSNs have been widely deployed and it is crucial to properly control the energy consumption of the sensor nodes to achieve the maximum WSNs’operation time (i.e., lifetime) as they are normally battery powered. In this paper, for sensor nodes that are utilized to monitor oil pipelines, we study the linear sensor placement problem with the goal of maximizing their lifetime. For a simple equal-distance placement scheme, we first illustrate that the result based on the widely used ideal power model can be misleading (i.e., adding more sensor nodes can improve WSN’s lifetime) when compared to that of a realistic power model derived from Tmote Sky sensors. Then, we study equal-power placement schemes and formulate the problem as a MILP (mixed integer linear programming) problem. In addition, two efficient placement heuristics are proposed. The evaluation results show that, even with the Tmote power model, the equal-power placement schemes can improve the WSN’s lifetime by up to29%with properly selected number of sensor nodes, the distance between them and the corresponding transmission power levels. Moreover, one heuristic scheme actually obtains almost the same results as that of MILP, which is optimal. The real deployment in one oil field is also discussed.(3) For a uniprocessor system where the processor power and the devices’power are in the same order or comparable, the dissertation addresses the problem of minimizing multi-resource energy consumption concerning both CPU and devices. A system is assumed to contain a fixed number of real-time tasks scheduled to run on a DVS-enabled processor, and a fixed number of offchip devices used by the tasks during their executions. We will study the non-trivial time and energy overhead of device state transitions between active and sleep states. Our goal is to find optimal schedules providing not only the execution order and CPU frequencies of tasks, but also the time points for device state transitions. We adopt the frame-based real-time task model, and develop optimization algorithms based on0-1Integer Non-Linear Programming (0-1INLP) for different system configurations. Simulation results indicate that our approach can significantly outperform existing techniques in terms of energy savings.(4) While much work has addressed the energy-efficient scheduling problem for uniprocessor or multiprocessor systems, little has been done for multicore systems. We study the multicore architecture with a fixed number of cores partitioned into clusters (or islands), on each of which all cores operate at a common frequency. We develop algorithms to determine a schedule for real-time tasks to minimize the energy consumption under the timing and operating frequency constraints. As technical contributions, we first show that the optimal frequencies resulting in the minimum energy consumption for each island is not dependent on the workload mapped but the number of cores and leakage power on the island, when not considering the timing constraint. Then for systems with timing constraints, we present a polynomial algorithm which derives the minimum energy consumption for a given task partition. Finally, we develop an efficient algorithm to determine the number of active islands, task partition and frequency assignment. Our simulation result shows that our approach significantly outperforms the related approaches in terms of energy saving.(5) While much work has addressed energy-efficient scheduling for sequential tasks where each task can run on only one processor at a time, little work has been done for parallel tasks where an individual task can be executed by multiple processors simultaneously. In this paper, we develop energy minimizing algorithms for parallel task systems with timing guarantees. For parallel tasks executed by a fixed number of processors, we first propose several heuristic algorithms based on level-packing for task scheduling, and then present a polynomial-time complexity energy minimizing algorithm which is optimal for any given level-packed task schedule. For parallel tasks that can run on a variable number of processors, we propose another polynomial-time complexity algorithm to determine the number of processors executing each task, task schedule and frequency assignment. To the best of our knowledge, this is the first work that addresses energy-efficient scheduling for parallel real-time tasks. Our simulation result shows that the proposed approach can significantly reduce the system energy consumption.To sum up, the dissertation studies the energy-efficient problem for uniprocessor systems with multi-resource and different approaches are proposed for the processor power dominated systems, devices’power dominated systems and systems with comparable power consumptions between the processor and devices. Moreover, some novel methods are also proposed for VFI-based multicore systems and parallel real-time tasks.