Research On Energy Efficient Task Scheduling Algorithm For Heterogeneous Multi-core Computing System

With the development of VLSI design and semiconductor technology,more and more embedded systems begin to use heterogeneous multi-core processors.However,most embedded systems are battery-powered mobile devices.Under the current situation that battery technology is not developing as fast as semiconductors,It is of great value to study an energy-saving task scheduling algorithm that can reduce system energy consumption without losing real-time performance of the system.Aiming at the energy-saving task scheduling problem on heterogeneous multi-core computing systems,this thesis proposes two partition-based energy-saving task scheduling algorithms,which are used to schedule frame-based tasks and periodic tasks respectively.In addition,an energy-saving scheduling scheme that applies the algorithm to the actual system is designed.The main work of this thesis is as follows:1.A two-level optimization frame-based task scheduling algorithm with convex optimization theory is proposed.Aiming at the problem that similar algorithm's long running time and may cause missed deadlines,the algorithm sets up a two-level optimization.The simulation results show that the feasibility of the task assignment obtained by the algorithm is higher than the existing algorithms.When scheduling mediumload tasks,the energy consumption of the algorithm is 21% ? 40% lower than the existing heuristic algorithm,and only 2.6% higher than the theoretical optimal energy consumption;the algorithm running time is reduced by 58% compared with similar algorithm which has the similar energy saving effects.2.Based on the frame-based task scheduling algorithm,a multi-stage periodic task scheduling algorithm with convex optimization theory is proposed.The algorithm uses a heuristic algorithm to pre-allocate some tasks to reduce the scale of subsequent problems.A judging strategy is designed to take advantage of the short running time of heuristic algorithms while avoiding the adverse effects of such algorithms on the real-time performance of the system.Simulation experiments show that while the energy saving effect is close to the theoretical optimization,the running time is about 76% lower than similar algorithms.When scheduling ultra-high load periodic tasks,the feasible task assignments are more than 8 times that of similar algorithms.3.Aiming at the application of the algorithm to the actual system,this thesis also studies the power consumption model based on actual system.Based on this model,the application scheme of energy-saving task scheduling algorithm is proposed,including task scheduling algorithm,frequency selection module and task assignment module.This scheme can apply the two algorithms proposed in this thesis to the actual system power consumption model.Simulation experiments show that the two algorithms proposed in this thesis still maintain a good energy saving effect and low running time on the actual system model.Compared with similar algorithms,the task assignments generated by the proposed algorithms are the most feasible.