Research On Energy-efficient Scheduling With Reliability Constraint For Embedded Systems

With the rapid development of electronic and computer technologies,the structure of microprocessors has become increasingly complex which is accompanied by the significant improvement of computing capacity.However,as system performance improves,the energy consumption also increases.How to reduce energy consumption has become an important question in system design.In order to achieve the low-power design goal,dynamic voltage and frequency scaling(DVFS)technique has been widely employed in various application scenarios,which reduce the system energy consumption by scaling the voltage and frequency in runtime.Reliability is an important quality target of the system.For many systems,the reliability requirement must be satisfied,otherwise it may lead to disastrous consequences.As the number of circuits inside the chip increases and the size of the circuit is reduced,the ability of the chip to resist high-energy particle impact is reduced,so that the probability of failures occurring when the processor performs a task increases,which will affect the reliability of the system.The runtime faults can be categorized into transient faults and permanent faults,and the transient faults happen more frequently.Studies have shown that when the execution frequency of the processor is reduced,the probability of transient faults increase dramatically.As a result,the reliability of the system is rapidly weakened.In order to improve the reliability of the system or ensure the reliability of the system not to be lower than a predetermined goal,backward recovery and task replication techniques are often applied to improve task’s reliability.When applying the backward recovery technique,if the task has a fault,roll back to the previous checkpoint before the fault occurred,and then re-execute the task from the checkpoint.When applying task replication technique,the task is copied to multiple processors and executed simultaneously to tolerate faults during execution.In general,the energy consumption optimization and reliability optimization of the system are two conflicting objectives.On one hand,applying DVFS to reduce energy consumption of the system will lead to a decrease in reliability.On the other hand,applying backward recovery or task replication technique to improve the reliability of the system will increase the energy consumption.Therefore,this dissertation mainly studies the problems of system reliability and energy consumption optimization.The main contributions are as follows.(1)For periodic real-time tasks on single-processor systems,a mixed scheduling method based on earliest deadline as soon as possible(EDS)and earliest deadline as late as possible(EDL)strategies is proposed to improve energy efficiency while guaranteeing system’s reliability.The EDS strategy is used to execute tasks,and the EDL strategy is used to manage the processor idle time.Specifically,an energy-efficient scheduling algorithm with guaranteed reliability based on the worst-case execution time(WCET)is designed,in which the processor’s dynamic utilization is defined to determine the optimal execution frequency.Then,since the actual execution time(AET)may be less than WCET for many tasks,an energy-efficient scheduling algorithm with guaranteed reliability based on AET is designed,in which the statistical method is used to determine the optimal execution frequency.Experimental results demonstrate that the proposed algorithms have significant improvements in energy efficiency and system reliability.(2)The parallel tasks with precedence constraints are modelled as a directed acyclic graph(DAG).The problem of minimizing energy consumption with a reliability goal for DAG-based parallel application on heterogeneous embedded systems is studied.Two algorithms that minimize the system energy consumption while satisfying the reliability goal are proposed without applying task replication,namely non-DVFS energy-efficient scheduling algorithm with the reliability goal(NDERG)and DVFS energy-efficient scheduling algorithm with the reliability goal(DERG).Both NDERG and DERG algorithms transfer the reliability goal of the application into the reliability goal of each task at first,then use a heuristic approach to make the energy consumption as low as possible.Because the reliability goal transferred method is based on the highest reliability that the application can reach,when the reliability goal is less than or equal to maximum reliability of application,the processors that satisfy the reliability goal of the application can always be found.The performance of the proposed algorithms is validated by simulation experiments.(3)For DAG-based parallel applications on heterogeneous embedded systems,a two-phase algorithm framework is proposed to minimize energy consumption while satisfying reliability goal.The first phase is for the initial assignment and the second phase is for both satisfying the reliability goal and improving energy efficiency.Specifically,initial assignment is to find the processor with minimum energy consumption to execute the task without using DVFS technique.When the reliability of the application obtained in the first phase is lower than the reliability goal,the second phase starts where a reliability-enhanced algorithm is proposed to strengthen the reliability of the selected tasks.In this way,the reliability goal of the application can be satisfied.Otherwise,an energy-efficient algorithm with the DVFS technique is proposed to improve energy efficiency.(4)NDERG,DERG and two-phase algorithms do not consider the case of task replication,in some cases the system’s reliability goal requirements may be higher than the highest reliability that can be reached by non-task replication.In this case,the task must be replicated to make the system reliable.Therefore,two energy-efficient scheduling algorithms with constrained reliability goal based on task replication are designed.The algorithms use the average worst execution time of the task as a reference to determine the reliability goal for each task,and then the heuristic method is used to minimize the energy consumption of the system.Experimental results demonstrate that the proposed algorithms consume lower energy consumption compared with the existing algorithms.