Accession Number : ADA440911


Title :   Pruning-Based, Energy-Optimal, Deterministic I/O Device Scheduling for Hard Real-Time Systems


Descriptive Note : Journal article


Corporate Author : DUKE UNIV DURHAM NC DEPT OF ELECTRICAL AND COMPUTER ENGINEERING


Personal Author(s) : Swaminathan, Vishnu ; Charabarty, Krishendu


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a440911.pdf


Report Date : Feb 2005


Pagination or Media Count : 28


Abstract : Software-controlled (or dynamic) power management (DPM) in embedded systems has emerged as an attractive alternative to inflexible hardware solutions. However, DPM via I/O device scheduling for hard real-time systems has received relatively little attention. In this paper,we present an offline I/O device scheduling algorithm called energy-optimal device scheduler (EDS). For a given set of jobs, it determines the start time of each job such that the energy consumption of the I/O devices is minimized. EDS also ensures that no real-time constraint is violated. The device schedules are provably energy optimal under hard real-time job deadlines. Temporal and energy-based pruning are used to reduce the search space significantly. Since the I/O device scheduling problem is Nu/Rho-complete, we also describe a heuristic called maximum device overlap (MDO) to generate near-optimal solutions in polynomial time. We present experimental results to show that EDS and MDO reduce the energy consumption of I/O devices significantly for hard real-time systems.


Descriptors :   *ALGORITHMS , *SOFTWARE ENGINEERING , *REAL TIME , *SCHEDULING , *OFFLINE SYSTEMS , *INPUT OUTPUT DEVICES , COMPUTER PROGRAMS , POLYNOMIALS , ENERGY CONSERVATION , EMBEDDING , HEURISTIC METHODS , JOBS , PERFORMANCE(ENGINEERING) , INPUT OUTPUT PROCESSING , RELIABILITY


Subject Categories : Computer Programming and Software
      Computer Hardware


Distribution Statement : APPROVED FOR PUBLIC RELEASE