Approximation algorithms for multiprocessor energy-efficient scheduling of periodic real-time tasks with uncertain task execution time
Journal
IEEE Real-Time and Embedded Technology and Applications Symposium
Pages
13-23
Date Issued
2008
Author(s)
Abstract
Energy-efficiency has been an important system issue in hardware and software designs for both real-time embedded systems and server systems. This research explores systems with probabilistic distribution on the execution time of realtime tasks on homogeneous multiprocessor platforms with the capability of dynamic voltage scaling (DVS). The objective is to derive a task partition which minimizes the expected energy consumption for completing all the given tasks in time. We give an efficient 1.13-approximation algorithm and a polynomial-time approximation scheme (PTAS) to provide worst-case guarantees for the strongly NP-hard problem. Experimental results show that the algorithms can effectively minimize the expected energy consumption. © 2008 IEEE.
SDGs
Other Subjects
Computer networks; Electric load forecasting; Embedded systems; Energy efficiency; Energy policy; Integrated circuits; Multiprocessing systems; Nuclear propulsion; Polynomial approximation; Probability distributions; Software design; Trees (mathematics); Voltage stabilizing circuits; Wireless telecommunication systems; Dynamic voltage scaling (DVS); Energy-efficient scheduling; Expected energy consumption minimization; Multiprocessor scheduling; Probability; Approximation algorithms
Type
conference paper