Dissertation > Excellent graduate degree dissertation topics show

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

Author: WuXiaoDong
Tutor: WangTianJiang; HanJianJun
School: Huazhong University of Science and Technology
Course: Applied Computer Technology
Keywords: real-time systems multicore scheduling algorithm energy-aware tasksynchronization
CLC: TM714
Type: PhD thesis
Year: 2012
Downloads: 16
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Design and Implementation of Automotive Can-Can Gateway,TP273
  2. Research on Algorithm of Parallel Copying Garbage Collection Based on Lisp 2 for Multicore System,TP332
  3. Design and Implementation of a Black Field Analysis Module of MPEG-2 Video Decoder,TP391.41
  4. The Design and Development of Real Time Operation System Base on Arm Processor,TP316.2
  5. Energy-aware Routing Algorithm for Ad Hoc Network Based on Ant Colony Optimization,TN929.5
  6. Research on Adaptive Grid Workflow Scheduling Based on Domain Trust Mechanism,TP311.52
  7. Research of Scheduling Algorithm in Telecom Business Supporting Based on Cloud Computing Platform,TP301.6
  8. A Study of Amdahl’s Law Performance Model on Asymmetric Multicore System,TP338.6
  9. Temperature limits based on multi-core systems saving scheduling algorithm,TP332
  10. Fibre Channel-based file-level data sharing system design and implementation,TP333
  11. DSP-based embedded controller onboard camera research,V445.8
  12. Based on multi-core SMP cluster environment parallel ray tracing simulation of satellite imagery and Implementation,TP391.41
  13. Multiprocessor rate monotonic scheduling algorithm,TP332
  14. Multi-core parallel cluster environment GeoComputation execution time prediction technology research,TP338.6
  15. Core temperature for the public perception of the Linux scheduler Research and Implementation,TP316.81
  16. The co-design of scheduling and control of the network control system with resource constraints,TP13
  17. The Design and Implementation of a Email System for On-line Reviewer,TP393.098
  18. Short-term Urban Traffic Forecasting Based on Multi-kernel SVM Model,U491.14
  19. FCM combines multi-resolution image cone multicore parallel image segmentation algorithm,TP391.41
  20. Congestion Control and Scheduling Algorithm Based on IEEE 802.11s Standard,TN929.5
  21. The Algorithm and Modeling Study of Ports Scheduling System,F224

CLC: > Industrial Technology > Electrotechnical > Transmission and distribution engineering, power network and power system > Theory and Analysis > Load analysis
© 2012 www.DissertationTopic.Net  Mobile