Swaminathan and Chakrabarty address the issue of optimal job scheduling in a hard real-time computer system, via the use of a novel, off-line dynamic power management (DPM) scheme for computer system input/output (I/O).

The paper elaborates briefly on the multiple application domains in which embedded systems are utilized, and the well-known benefits of reducing power consumption. Subsequently, it discusses static (leakage) and dynamic (switching) power in the context of integrated circuits. The authors then introduce the concept of dynamic power management, which allows a system to make runtime decisions to take advantage of periods of inactivity and computational demands. The authors very correctly point out that DPM, at the operating system (OS) level, has been used extensively since 1997 via the advanced configuration and power interface (ACPI). Furthermore, they discuss present-day computer systems, and identify (quite correctly) both the central processing unit (CPU) and the I/O on desktop computer systems as being extremely important systems for power optimization. The introductory section concludes with a brief mention of the contributed, nondeterministic polynomial time (NP) complete algorithm, energy-optimal device scheduler (EDS), and the implementation of a polynomial-time maximum device overlap (MDO) heuristic to significantly reduce I/O device power consumption.

The “Prior Work” section in the paper sets the scene for the contributed EDS algorithm, and I/O DPM is classified as timeout-based, predictive, and stochastic. Mention is made of the very important (and reasonably recent) development in the embedded microprocessor industry, dynamic voltage scaling (DVS). The authors then introduce notation and formalize the problem, and demonstrate that it is NP-complete. They introduce their methodology, based on energy pruning, through a very informative example section that takes the reader through the EDS algorithm; I found this section to be particularly useful and informative in my understanding of the work. EDS tries to find an optimal solution for an NP-complete problem, which potentially leads to very long runtimes and excessive memory requirements. The authors therefore introduce a heuristic method to generate near-optimal solutions in polynomial time, which they call MDO. Unfortunately, MDO does not address the issue of blocking, but the authors do mention that resource allocation by an algorithm such as the stack resource policy (SRP) will prevent this from arising. In any case, MDO is a significant step in computing a provably NP-complete problem in polynomial time.

The experimentation section discusses two experiments, with the first consisting of three devices: a network interface card, a digital signal processor (DSP), and a hard disk drive (HDD) with multiple sleep states. The EDS algorithm in this case arrives at an optimal 33 percent energy reduction (presumably with respect to keeping all three devices powered up all the time). The heuristic-based MDO arrives at a solution that is only four percent worse than the optimal (EDS) solution, clearly demonstrating the strength of the heuristic method.

Overall, I found the work to be very satisfactory and informative. There are very interesting synergies between I/O DPM and CPU DVS, and I hope the authors will pursue a study on that front in a forthcoming contribution.