Research And Design Of Energy Efficient Scheduling Algorithms For Embedded Systems

With the rapid growth of semi-conductor chip's technology, energy consumption has become an important design issue and performance metric in embedded systems. Some energy saving techniques such as dynamic voltage scaling, dynamic power management, adaptive body biasing and their combinations offer good opportunities to decrease energy consumption in embedded systems. Task scheduling and voltage selection play active roles in energy minimization. Therefore, the integration of energy saving techniques into the design of scheduling algorithms becomes very important for embedded systems to decrease energy consumption. In fact, data or control dependencies are pervasive in many applications while data dependencies or control dependencies have negative effects on energy conservation, which, therefore, are also required to be solved in the design of energy-efficient scheduling algorithms effectively. Considering retimed directed acyclic graphs can effectively overcome the effect of intra-iteration data dependencies so that more opportunities can be provided to decrease scheduling length and energy consumption, this thesis designed several energy efficient policies which take retimed directed acyclic graphs as scheduled objects to realize energy conservation.The main research work in this thesis can be summarized as follows:1. If a task scheduling is generated based on a retimed directed acyclic graph and all the tasks are executed with two performance modes, appropriately reordering both task order and performance mode order of each task can generate more slacks to decrease energy consumption. To provide more opportunities to lower energy consumption, a technique is proposed to reorder both task and performance mode that employ the character of only inter-iteration data dependencies of retimed directed acyclic graphs and the merit of performance mode reordering that has no effect on task execution. Firstly, the minimum voltage transition time is calculated for the given task set on a component when one task of the task set is set the first task to be executed.Then, selecting the smallest one from these minimum voltage transition time as the minimum voltage transition time for the given task set on the corresponding component.The corresponding task order and performance mode order are the final task order and performance mode order to be executed.2. Many processors, such as PXA255, AMD Mobile Athlon4, Transmeta's Crusoe are equipped with dyanic voltage scaling ability. In addition, multi-core architecture has dominated the market of embedded systems. In order to decrease energy consumption in multi-core systems with dynamic voltage scaling ability, an algorithm is proposed to minimize energy consumption of multi-core systems when voltage transition time is fixed or negligible. The proposed algorithm reduces both transition and dynamic energy consumption for applications including dependent tasks with common timing constraints considering transition overhead between performance modes and communication overhead between processor cores. First, the proposed algorithm achieves the minimum initial scheduling length by choosing reasonable task mapping and frequency assignment under given timing constraint. Then, it iteratively selects tasks to conduct frequency scaling so that the minimum energy consumption can be generated when decreasing the frequency of the chosen tasks to adjacent frequency and executing tasks in decreasing voltage levels on the processor core where the scaled tasks locate.3. The trend of increasingly shrunken feacture size will lead to leakage energy larger than dynamic energy consumption in the future. The combination of dynamic voltage scaling and adaptive body bias is an efficient method for joint dynamic and leakage enrgy reduction. In response to this trend, an algorithm is proposed to apply above two techniques to decrease energy consumption for applications with hard timing constraints on multi-core systems. First, the proposed method determines initial task order and frequency assignment to get the minimum initial scheduling length under given timing constraint. Then it iteratively selects candidate task and scales the frequency of the candidate task to achieve the maximum ratio of reduced energy to increased time. In order to achieve more slacks to decrease energy consumption, it reorders tasks on the processor core where candidate tasks locate after each frequency scaling.4. In recent years, new multi-core systems in which not only processor cores but also buses feature dynamic voltage scaling and adaptive body bias capabilities have been proposed as a promising solution to decrease energy consumption. An algorithm is proposed for such systems to decrease energy consumption of both processor cores and communication links by the combination of dynamic voltage scaling, adaptive body bias and dynamic power management. First, the proposed algorithm utilizes the choice of mapping algorithm to decrease volume of communication among processor cores. Then it achieves the maximum ratio of reduced energy to increased time by scaling frequencies of both candidate computation tasks and the bus. This operation is continued until further scaling will lead to violate given timing constraint.