An analysis of system level power management algorithms and their effects on latency

Abstract—The problem of power management for an embedded system is to reduce system level power dissipation by shutting off parts of the system when they are not being used and turning them back on when requests have to be serviced. Algorithms for this problem are online in nature; the algorithm must operate only with access to data that it has seen so far and without access to the com-plete data set or its characteristics. In this paper, we present on-line algorithms to manage power for embedded systems and dis-cuss their effects on system latency. We introduce competitive analysis as a formal framework for the evaluation of various power management algorithms. Compet-itive analysis does not depend on the distribution of interarrival times of requests. In this context, we present a nonadaptive on-line algorithm, analyze its behavior, and show that it is optimal. In this paper, we also present a lower bound on the competitivenes