Synchronization-Aware Energy-Efficient Scheduling Algorithm In VFI-Based Multicore Real-Time Systems

Multicore processors, which integrate many processing units/cores into a single chip,have emerged to be the popular and powerful computing engines to address the increasingperformance demands and energy efficiency requirements of modern real-timeapplications. Voltage and frequency island (VFI) was recently adopted as an effectiveenergy management technique for multicore processors.There are usually global shared resources in multicore systems, such as shared dataobjects and I/O channels. Therefore, the task execution needs to consider synchronization,which will result in synchronization overhead. However, the majority of the existing workon multicore energy-efficient scheduling does not take the task synchronization intoaccount. If those strategies were applied directly to the real-time systems with globalshared resources, some tasks may miss their deadlines due to the synchronizationoverhead. In this paper, for a set of periodic real-time tasks that access shared resourcesrunning on a VFI-based multicore system with dynamic voltage and frequency scaling(DVFS) capability, we study both static and dynamic synchronization-aware energymanagement schemes.In the synchronization-aware multicore system, if a task tries to access a globalresource which is already locked by some other task on another processor, according tothe original MSRP(multiprocessor stack resource policy), the task will perform a spin lock(or busy waiting) until the resource is released and the task is authorized to visit thisresource. This spin lock based policy may lead to high synchronization overhead in thesystem with tasks’ long resource waiting time. As a result, the efficiency of the processoris reduced since a large percentage of its time is in idle status. Hence, we extend theoriginal MSRP in this research. According to our enhanced policy, if a task fails to accessits resource, the scheduler will suspend the task’s execution and let the corresponding corerun the non-critical sections of other tasks in its ready job queue, so as to improve thesystem performance.Based on the enhanced MSRP resource access protocol with a suspension mechanism,we devise a synchronization-aware energy-efficient task mapping heuristic, SA-WFD(Synchronization Aware Worst-Fit Decreasing), for partitioned-EDF scheduling. Theheuristic algorithm considers the synchronization cost cased by the tasks’ accessing resources and those overhead are incorporated into the pessimistic estimated utilization(PEU) of each task. Then, SA-WFD maps tasks to the processing cores in thenon-increasing order of their PEUs. Further, SA-WFD assigns tasks that access similar setof resources to the same core to reduce the synchronization overhead and thus improveschedulability.After the task-core mapping is determined, the schedulability of the real-time tasksset is analysed and the schedulable condition under the EDF-based scheduling is presented.Then, based on the feasible mapping, the static schemes that assign uniform and differentscaled frequencies for tasks on different VFIs are studied.As the actual execution time of the real time task is usually less than its WCET, thesystem will dynamically generate slack. In order to further exploit dynamic slack for moreenergy savings, we propose an integrated synchronization-aware slack managementframework, SA-DVFS (Synchronization Aware DVFS), which utilizes the wrapper-jobschema to manage the slack time, to appropriately reclaim, preserve, release and stealslack at runtime to slow down the execution of tasks subject to the commonvoltage/frequency limitation of VFIs and timing/synchronization constraints of tasks.Taking the additional delay due to task synchronization into consideration, the newscheme allocates slack in a fair manner and scales down the execution of both non-criticaland critical sections of tasks for more energy savings.Simulation results show that, the synchronization-aware task mapping scheme cansignificantly improve the schedulability of tasks. The energy savings obtained by the staticscheme with different frequencies for tasks on different VFIs is close to that of an optimalINLP (Integer Non-Linear Programming) solution. Moreover, compared to the simpleextension of existing solutions for uniprocessor systems (i.e., USFI, DSDR, and FL-PCPscheduling algorithms), our dynamic scheme can obtain much better energy savings (up to40%) with comparable DVFS overhead.