Energy-efficient Real-time Scheduling For Multi-core And Multiprocessor System

The actual needs of the real world promote the emergence and development ofreal-time systems. Meanwhile, with the rapid development of electronic and computertechnology, the application scope of real-time systems is also expanding. To meet theincreasingly complex and intellectual requirement for real-time systems, it needs toprovide more powerful, more flexible and higher cost-efficiency microprocessorsystems.With the rapid development of VLSI technology and the great increase ofapplication requirements, the multi-core chip and multi-processors on chip architecturedomain modern commercial processors. They have attracted more and more attention ofembedded real-time systems. However, the energy consumption of multi-core systemsbecomes increasingly prominent. Energy consumption is one of the most importantfactors considered by many embedded real-time systems, especially wireless andportable devices. Energy-efficient real-time scheduling research become one of the frontdomains and popular topics and attracts more and more attention of both academic andindustrial world. Furthermore, it becomes increasingly important with the proposal of"green computation".To solve the problem of energy consumption in real-time multi-core andmultiprocessor systems, this paper introduces energy-efficient technologies into thedesign of real-time scheduling algorithms, putting forward some proposals forenergy-efficient real-time scheduling. We start the research in terms the processormodel from multiprocessor systems to multi-core systems, the task model from sporadictasks to general tasks, the DVFS processor model from ideal to practicalmultidimensional limitation.1. We put forward an energy-efficient real-time scheduling algorithm for sporadictasks in multiprocessor platforms. The proposed method is based on LRE-TL which isan optimal real-time scheduling algorithm for sporadic tasks. With the schedulingalgorithm, LRE-TL, and the energy-efficient technology, independent DVFS and DPM,the voltage and frequency of active tasks is dynamically scaled at the initial time of eachTL plane and the release time of a sporadic task in each TL plane. Our proposalguarantees the optimal feasibility of sporadic tasks. Furthermore, the experimentalresults show that compared with existing algorithms, more energy savings can beachieved in all cases, especially up to30%in the case of high workloads.2. We propose to overcome the energy consumption problem of multi-corearchitecture for sporadic tasks, including two key technologies: TL-DVFS (Time Localremaining execution plane based Dynamic Voltage Frequency Scaling) and DSREM(Dynamic Slack Reclamation based Energy-efficient Multi-core real-time scheduling). TL-DVFS is an online real-time energy-efficient scheduling algorithm based on TLplane and adopts LRE-TL to perform real-time task scheduling. The voltage andfrequency are dynamically scaled at the initial time of each TL plane and the releasetime of a sporadic task in each TL plane, which is adaptive to the dynamic workload ofsporadic tasks and obtain more energy savings. Systematic mathematical analysis andextensive simulation results show that TL-DVFS can not only guarantee the optimalfeasibility of sporadic tasks, but also achieve more energy savings in all cases,especially in the case of high workloads. In addition, DSREM is proposed afterquantifying the characteristics that the actual execution time of tasks is usually less thantheir Worst-Case Execution Time (WCET) producing lots of dynamic slack time. Themain idea of the algorithm is to reclaim dynamic slack time, during which DVFStechniques can be used to reduce the execution frequency of future tasks to reduceenergy consumption. Experimental results show that DSREM can always save moreenergy than existing algorithms when the total workload of the system exceeds athreshold, and at the same time guarantees optimal schedulability. The performance willbe improved when the total workload is increased.3. This paper develops a Global EDF-based OnLine Energy-Aware SchedulingAlgorithm (GEDF-OLEASA) for hard real-time tasks in multi-core system.GEDF-OLEASA is based on the general task model and with no priori to tasks’properties. It can reduce the execution speed of task in multi-core system, and reach areasonable compromise between real-time constraints and energy savings, as itintroduces a speed scale factor for utilizing the slack time, and combines dynamicpower management with dynamic voltage/frequency scaling techniques. The resultsshow that the algorithm can be well applied to different kinds of dynamicvoltage/frequency scaling on chip, and compared with Global EDF algorithm, it gainmore energy savings in all cases, which can improve energy savings about15%to20%at most and about5%to10%at least.4. We propose an optimal energy-efficient real-time scheduling algorithm which isoverhead-aware. Recent optimal energy-efficient real-time scheduling ignores the timeand energy overhead of processor state switching. Thus it is no more optimal in actualplatforms. For multiprocessors with independent dynamic voltage frequency anddynamic power management, we propose an optimal energy-efficient real-timescheduling algorithm for frame-based tasks. The proposed optimal algorithm determinesthe system workload cases and the number of active processor cores in tems of criticalspeed. Then we can obtain the optimal scheduling according to the switching overhead.The algorithm allows tasks to arbitrarily migrate across processors during theirexecution at the cost of small computational complexity. Furthermore, it is easy to beimplemented. Systematic mathematical analysis shows that the algorithm is optimal.In this paper, we carried on the research from energy-efficient real-time scheduling techniques for sporadic task model in multiprocessor system, sporadic task model inmulti-core system, general task model, and practical processor overhead model. Themathematical analysis, simulation experiments and evaluation results of this paper showthat these energy-efficient real-time scheduling techniques are effective, can be used tosolve energy consumption problem of multi-core and multiprocessor real-time systems.