Abstract running on these systems. This paper presents a novel run-time approach to reduce the system-wide energy consumption for such systems using dynamic power management. In this paper, the applications are modeled using a popular weakly hard real-time model, i.e., the (m, k)-model, which  Energy conservation has come to be recognized as a critical issue in design of pervasive real-time embedded systems, particularly due to the proliferation of mobile systems with limited power resources. For the sake of mobility, these portable computing and communication devices require low energy consumption to maximize the battery lifetime. As VLSI technology continues its remarkable advances, the power consumption has been increased exponentially [2] . Current battery technology, with its 5% annual capacity increase [2] , cannot effectively address this problem. In addition, serious concerns are raised with regards to managing the heat dissipation from the rapidly elevated power consumption. Left unchecked, the power consumption will threaten to curtail the availability of the future high performance portable devices and advanced multimedia functionality on these devices. Power aware scheduling has been proven to be an effectively way to reduce the power consumption. Rooted in the traditional real-time scheduling technology, the power aware scheduling techniques change the system computing performance accordingly based on the dynamically varied computation demand. Two main types of power management mechanisms are reported in the literature. The first one is commonly known as the dynamic power down (DPD), i.e., to shut down a processing unit and save power when it is idle, and switch over to normal state when the idle time expired. The second one is to update the processor's supply voltages and working frequencies, which is usually referred as the dynamic voltage scaling (DVS). Thanks to the recent IC technology advancement, many modern processors can vary its voltage and working frequencies (and thus processing speeds) dynamically. For the past few years, we have seen extensive researches that employ a variety of real-time scheduling techniques to reduce the energy consumption. Most of them have been focused solely on reducing the energy consumption by the processor (e.g. [22, 25, 34] ). A typical portable device usually includes one or more core processors, memory, and peripheral devices such as network interface card, disk, and display. While the processor is one of the major power hungry units in the system, other peripherals such as network interface card, memory banks, disks also consume significant amount of power. The empirical study by Viredaz and Wallach reveals that the processor core consumes around 28.8% of total power when playing a video file on a hardware testbed [32] for handheld devices, while the DRAM consumes about 28.4% of the total power. Note that this testbed [32] lacks disk storage and wireless networking capability, which may contribute as much power consumption as the processor core if not more [35, 9] . This implies that the techniques that reducing the processor energy alone may not be overall energy efficient. A number of techniques (e.g. [11, 13, 38] ) have been published recently to deal with the power consumption for systems consisting of DVS processors and peripheral devices. A fundamental tradeoff that has to be made in these approaches is whether to apply DVS or DPD during the scheduling process. DVS techniques reduce energy consumption by lowering the processor speed. Unfortunately, it extends the execution times of real-time tasks and shrinks the idle intervals, which is not favorable for DPD. Kim and Ha [13] proposed a technique for hard real-time system, while scheduling decisions are made on a timeslot-by-timeslot basis. To facilitate a run-time mechanism, the processor speed for each task is determined by analyzing the energy savings based on a pre-determined set of execution times. Jejurikar and Gupta [11] introduced a heuristic search method to slow down the processor speed and optimize the energy usage by both the processor and peripheral devices. Zhuo and Chakrabarti [38] proposed a theoretical formulation of the optimal scaling factor and computed it numerically. Based on this factor, they introduced a dynamic scheduling technique that reduces the potential excessive preemptions among tasks to further reduce the system wide energy consumption. While DVS techniques can dramatically reduce the dynamic power consumption for the processor, DPD techniques seems to be more promising in reducing the system-wide overall energy consumption in the near future. As shown in the work by Zhuo and Chakrabarti [38] , when peripheral devices consume more power than the processor, the effectiveness of DVS techniques can be seriously degraded. Even for the processor itself, the energy efficiency of DVS is becoming limited as IC technology continue its evolution [36] , especially when the leakage power is increasing exponentially and will soon surpass the dynamic power consumption [10] . DPD, on the other hand, is one of the most intuitive and effective ways to control the leakage power consumption. Moreover, most peripheral devices do not support DVS at all. As a result, the research on employing DPD has regained its momentum to reduce the system-wide energy consumption. As a traditional energy-saving technique, DPD has been widely adopted in real-time scheduling. A majority of DPD techniques (e.g. [28, 23] ) have been proposed for soft real-time systems, where task deadlines can be missed albeit with reduced quality levels. There are also a number of papers (e.g. [7, 30, 31] ) deal with the power optimization for hard realtime systems, where a deadline miss is considered a system failure. A good survey on DPM related real-time scheduling research can be found in [4, 3] . Few real-time applications are truly hard real-time, i.e., missing one task deadline does not necessarily crash the entire application or system. Many real-time applications, such as multimedia and communication applications, can often tolerate occasional deadline misses, but too much deadline misses cannot satisfy user's perceived quality of service (QoS) requirement. While the statistic information such as the average deadline miss rate is commonly used to quantify the system performance, this metric can be problematic. Note that even a very low average miss rate tolerance cannot prevent a large number of deadline misses from occurring in a very short period of time. This may cause the loss of critical information which cannot be reconstructed and therefore severely degrade the service quality from user's perspective. The weakly hard real-time model is a more suitable real-time model for this type of applications. The weakly-hard realtime task has both a firm deadline (i.e., a task instance missing its deadline is utterly useless) and a throughput requirement (i.e., there should be sufficient task instances from the same task meeting deadlines in order to provide required quality levels). Several weakly-hard models have been introduced [26, 8, 14, 5, 33] . Ramanathan et. al. [26] proposed a so-called (m, k)−model, with a periodic task being associated with a pair of integers, i.e., (m, k), such that among any k consecutive instances of the task, at least m of the instances must finish by their deadlines for the system behavior to be acceptable. A dynamic failure occurs, which implies that the temporal QoS constraint is violated and the scheduler is thus considered failed, if within any consecutive k jobs more than (k − m) job instances miss their deadlines. Koren et. al. [14] proposed a 'skip-over' model, which is a special case of (m, k) model with m = k − 1. West et. al. [33] introduced another similar model, called the window-constrained model, which requires that within any non-overlapped and consecutive windows each of which containing k jobs, at least m of them can meet their deadlines. In this paper, we study the problem of employing DPD to reduce the system-wide energy consumption with guaranteed QoS for a weakly hard real-time system. Specifically, we adopt the (m,k)-model to capture the QoS requirement for the real-time application. A key challenge for this problem has to do with the definition of which jobs are mandatory, i.e., whose deadlines have to be met to guarantee no dynamic failure occur, and which jobs can be optional. This problem has shows to be NP-hard even without the considerations of the power conservation [24] . In our approach, we employ a run-time technique and dynamically choose and execute the mandatory jobs in such a way that facilitates the system shut down. Our experiments shows that by judiciously choosing and merging the mandatory jobs, our techniques can lead to significant energy savings while still guaranteeing the (m,k)-firm deadlines. The rest of the paper is organized as follows. We first introduce the system model, background, and motivations for our research in Section 2. Section 3 describes a feasibility condition to guarantee the (m,k)-firm deadlines in our approach when dynamically determining the mandatory/optional jobs. Section 4 presents two methods to delay the job execution to further extend the idle interval. Section 5 discusses how to judiciously execute the optional jobs and present the overall algorithm. Section 6 presents our experimental results. Section 7 draws the conclusions. In this section, we first introduce the system model and the related work on real-time scheduling with (m,k)-firm guarantee. We then present and discuss a motivation example.
To incorporate the energy of the peripheral devices into consideration, REF investigated the scheduling problem for a system that consists of a non-DVS processor and a single peripheral device.
System Wide Dynamic Power Management for Weakly Hard Real-Time Systems
J. Low Power Electronics
J. Low Power Electronics
Engineering Computer Science