QoS Control Strategies for High-Quality Video Processing

QoS Control Strategies for High-Quality Video Processing Clemens C. W¨ust ([email protected])

Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands

Liesbeth Steffens ([email protected])

Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands

Wim F.J. Verhaegh ([email protected])

Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands

Reinder J. Bril ([email protected])

Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

Christian Hentschel ([email protected])

Brandenburg University of Technology Cottbus, P.O. Box 10 13 44, 03013 Cottbus, Germany Abstract. Video processing in software is often characterized by highly fluctuating, contentdependent processing times, and a limited tolerance for deadline misses. We present an approach that allows close-to-average-case resource allocation to a single video processing task, based on asynchronous, scalable processing, and QoS adaptation. The QoS adaptation balances different QoS parameters that can be tuned, based on user-perception experiments: picture quality, deadline misses, and quality changes. We model the balancing problem as a discrete stochastic decision problem, and propose two solution strategies, based on a Markov decision process and reinforcement learning, respectively. We enhance both strategies with a compensation for structural (non-stochastic) load fluctuations. Finally, we validate our approach by means of simulation experiments, and conclude that both enhanced strategies perform close to the theoretical optimum. Keywords: soft real time, overload, multimedia, Quality of Service (QoS), Markov decision process, reinforcement learning.

1. Introduction Software video processing is often characterized by highly fluctuating, data dependent, resource requirements. This is especially true for codecs and algorithms that contain motion estimation, such as Natural Motion (Braspenning et al., 2002) or MPEG encoding (Mietens et al., 2004), or motion compensation, such as MPEG decoding. For example, Figure 1 shows the decoding times for a sequence of MPEG-2 frames. Typically, there is a large gap between the worst-case and average-case processing times. Moreover, there is a clear distinction between short-term (or stochastic) and long-term (or structural) load fluctuations. Due to high pressure on cost, resource allocation will have to be close to average-case. Hence, to prevent overload, some form of load reduction is inevitable.

2 40

processing time (ms)

35 30 25 20 15 10 5

1

100

200

300 400 frame number

500

600

Figure 1. The decoding times for a sequence of MPEG-2 frames, showing both stochastic and structural load fluctuations.

Quality of Service (QoS) is defined as ‘the collective effect of service performance which determine the degree of satisfaction of a user of the service’ (ITU-T Recommendation E.800-Geneva 1994). The QoS abstraction provides a means to reason about and deal with heterogeneous soft timing requirements for tasks with fluctuating load (e.g. acceptance of occasional deadline misses (Buttazzo, 1997), or an average-case response time requirement (Klein et al., 1993)), and heterogeneous adaptive capabilities (e.g. approximate computing (Audsley et al., 1995; Zhao et al., 1995), or job skipping (Koren and Shasha, 1995)), in a unified manner. In this paper, we focus on QoS control for a single-threaded, soft real-time, video processing task, with load fluctuations as shown in Figure 1. We assume that the task has to operate within a given processing-time budget, which is less than the worst-case requirement of the task. To prevent deadline misses as much as possible, we apply two techniques. First, we use a scalable video algorithm, which can trade picture quality for resource usage at the level of individual frames, by providing a limited number of quality levels that can be chosen for each frame (Hentschel et al., 2001). Second, we assume that the task is asynchronous and works ahead to even out the load in time (Sha et al., 1986). An asynchronous task starts processing the next frame immediately upon completing the previous one, provided that the input data is available. If there is no input data, the task will block. The extent to which working ahead can be applied is determined by latency and buffer constraints (Isovi´c et al., 2003). Given the combination of scalable processing and working ahead, the QoS specification for high-quality video combines three elements, which have to be balanced: processing quality, deadline misses, and quality changes. The QoS control strategies presented in this paper are able to accommodate two types of load fluctuations: stochastic and structural. To control the stochastic load fluctuations, we model our control problem as a Markov

3 Decision Process, which is a general approach for solving discrete stochastic decision problems. We present a static solution based on off-line optimization (Puterman, 1994), as well as a dynamic solution based on Reinforcement Learning (Sutton and Barto, 1998). To deal with structural load fluctuations, we use budget scaling. The remainder of this paper is organized as follows. First, in Section 2 we sketch the context from which this work originates. In Section 3 we discuss related work. Next, in Section 4 we describe the real-time processing model that we apply. In Section 5 we describe our approach to designing QoS control strategies, and we discuss how structural load fluctuations can be handled using budget scaling. In Section 6 we evaluate the developed strategies in simulation experiments, and compare the on-line performance to an off-line computed theoretical upper bound. Finally, in Section 7 we conclude the paper. 2. Context The work described in this paper was initiated in the context of a larger effort, which defines and builds a framework for QoS resource management for high-quality video (QoS RM). This framework (Bril et al., 2001; Garc´ıa Valls et al., 2002; Hentschel et al., 2001; Otero P´erez et al., 2003) specifically aims at maintaining the properties of robustness and cost-effectiveness, and is based on resource reservation, i.e. resource budgets are granted to tasks consisting of one or more threads. Resource reservation, with temporal protection (Rajkumar et al., 1998), allows to dissect the overload management problem for heterogenous soft-real time systems into sub-problems that can be addressed separately. Given resource reservation, two responsibilities remain to be addressed in the QoS RM framework: deciding which task receives what budget (capacity reserve in Rajkumar et al. (1998)), and adjusting the load of each task to its assigned budget. The first responsibility is global, and requires a unified QoS measure; see for example Lee et al. (1999). The second responsibility is local, and may use task-specific QoS adaptation. To do this QoS adaptation, a task is equipped with a local QoS controller. In the QoS RM framework, the local and global responsibilities are linked to one another in a hierarchical way (Otero P´erez et al., 2003). A global QoS manager allocates budgets to the different tasks. In case of a structural load increase, the local QoS controller will request a budget increase from the global QoS manager. Even though the work was positioned in the abovementioned context, it was a clear goal from the beginning that the results would also be applicable in case of a single media application, running on a processor that does not

4 have sufficient CPU capacity (= budget) to support the worst-case workload of that application. For a stand-alone application, the local QoS controller is the only QoS controller in the system, and must therefore be able to address structural load fluctuations as well as stochastic load fluctuations.

3. Related Work We compare our work with related work along different axes. The first axis is the control-based approach to the system-level overload problem. Lu et al. (1999; 2000) present a feedback control scheduling algorithm for unpredictable dynamic systems, based on EDF scheduling, using deadline-based metrics. Hamann et al. (2001) present an approach that is based on reservations and local adaptation, like ours, but use a single QoS metric, the fraction of completely executed optional parts for a periodic task. Both assume a homogeneous system with a single global QoS metric, as opposed to the heterogeneous systems with task-specific QoS metrics assumed in the QoS RM framework. The second axis is the analysis and control of a video processing task with limited resources, the subject of this paper. On this axis we found several papers, all addressing MPEG decoding. In our case, MPEG decoding was just a vehicle for research, because the only scalable algorithm available at the time was an MPEG decoder. Lan et al. (2001) describe a method to regulate the varying computation load of a scalable MPEG decoder, which is operated synchronously. Before decoding an MPEG frame, the required computational resources are estimated, and next the decoding is scaled such that it will not exceed a target computation constraint. In contrast to our approach, they only optimize the quality of the individual frames, and not the overall perceived quality over a sequence of frames. Hamann et al. (2001) and Isovi´c and Fohler (2004) focus on solutions that are applicable for non-scalable video, based on skipping frames. Hamann et al. (2001) model the MPEG decoding task according to the imprecise computation model (Zhao et al., 1995). The MPEG decoding task is modeled as a periodic task which decodes one group of pictures every period. The mandatory part of the computation consists of the I and P frames, and the optional part consists of the B frames. Their QoS metric is the percentage of optional parts that meet their deadlines. The disadvantage of their approach is the large latency it requires, which is unacceptable for a TV set and other interactive multimedia devices. Isovi´c and Fohler (2004) provide requirements that have to be met by frame skipping algorithms for MPEG decoding. Again, frame skipping alone is not always acceptable. A method similar to ours could use their quality metrics to make a dynamic decision.

5 4. Real-Time Processing Model For the remainder of the paper we consider a single-threaded, asynchronous, scalable video processing task, with an associated controller. The task can process frames at a (small) discrete number of quality levels. The task retrieves frames to be processed from an input queue, and places processed frames in an output queue. For convenience, we assume that the successive 

 frames are numbered . An input process (for example a digital video tuner) periodically inserts frames into the input queue, with a period  , and an output process (for example a video renderer) consumes frames from the output queue, with the same period  . Hence, we assume that the input and output frame rates are the same. The input process and the output process are synchronized with a fixed latency  , i.e. if frame  enters the input queue at time    , where  is an offset, then the frame is consumed from the output queue at time    . Before processing a frame, the controller selects the quality level at which the frame is to be processed. The processing time for a frame depends on both the selected quality level and the data complexity of the frame. On average, the task has to process one frame per period  . By choosing larger than , the task is given some space to even out its varying load by working ahead. This has to be compensated by adding input and output buffers (Sha et al., 1986). Figure 2 shows the basic system model.

Controller

Input Queue Input Process

...

Output Queue Video Task

...

Output Process

Synchronized

Figure 2. Basic system model.

Consider a frame  , which enters the input queue at time  . Clearly,  is the earliest start time for processing the frame, and      is the latest acceptable completion time, thus the deadline. The actual start time for frame  , the  -th start point of the task, is denoted by  . The actual completion time for frame  , the  -th milestone of the task, is denoted by ! . For convenience, we define a virtual deadline "# $%  . With a nonzero processing time for frames it holds that ! '&( . If ) *& , if -,.0/ , the  , the task has missed its deadline for frame  . For +& task is blocked from 1 -,. until  . During that time, the task waits for frame
,  32547698;: -,. =< .  to become available for processing. Hence, for $&

6 In this paper, we assume a work preserving approach, which means that a frame is not aborted if its deadline is missed, but is completed anyhow. The frame is then used for the next deadline. If deadline > is missed, the late frame is assigned a new deadline, " @?3. , and frame A is skipped. This procedure will be repeated until a deadline is met. As a consequence, at each start point  ,  CBDE -,. . Figure 3 illustrates the task’s processing behavior by means of two exam ple timelines, in which we assume F ,  , and .GHIHJ . In Figure 3A, deadline K is missed. The controller handles the deadline miss by using frame 2 at deadline "L , and by skipping frame 3. In Figure 3B, the task becomes blocked at milestone ML , because frame 4 is not present in the input queue ( NO K ). s1 A

m1=s2 1

e2=d0

0

e4=d2

1

s1 e2=d0

2

e3=d1

0

B

m2=s4

2

e3=d1 1

4

2

m1=s2 m2=s3 1

m4=s5

m3 3

e4=d2 2

e6=d4

3

s4

blocked

5

e5=d3

4

time

m4=s5 4

5

e5=d3

e6=d4

3

4

time

Figure 3. Example timelines, showing the processing behavior in case of a deadline miss (A), and in case of blocking (B).

Each frame is processed at a particular quality level. Let pt denote the processing time for frame  , and let P denote the quality level at which frame  is processed. If frame  is skipped, we define pt  pt -,. and P

(P

-,. . In each interval between two successive deadlines, the task is assigned a fixed processing-time budget Q (JRBSQTBS ). Based on this budget we introduce a measure called progress. The progress is measured at the start point of each frame, and is a measure for the processing time available for that frame until its deadline. A larger progress leads to a lower risk of missing the deadline. We define the progress as follows. Progress UV , at start point 

, is the total amount of processing time left till  -,. , divided by Q . Since  B  W,. , UX 2 J . Furthermore, the latency provides an upper bound UY[Z]\^ _ on progress. In Figure 3, we implicitly assumed QG` , which implies that the task runs on a private processor. In Figure 3A, the progress at the successive start ab dcb dcb points is given by U . (J , U K (J , UXN#(J , and UXe#J , respectively, ab ab and in Figure 3B by U;.1fJ , UK!HJ , ULM ,U N  , and U e HJ , respectively.

7 5. Controller Design 5.1. BASIC

APPROACH

As mentioned before, at each start point the controller has to select the quality level at which the new frame is to be processed. We are looking for a control strategy with very little run-time overhead that meets the following three objectives. First, because deadline misses and the accompanying frame skips result in severe artifacts in the output, deadline misses should be as sparse as possible. To prevent deadline misses, it may be necessary to process frames at lower quality levels. Second, to obtain a high output quality, frames should be processed at the highest possible quality level. Third, because (bigger) changes in the quality level may result in (better) perceivable artifacts, the number and size of quality-level changes should be as low as possible. Clearly, it is impossible to meet all three objectives at the same time, so we have to find an optimal balance. To each frame that has been processed, we assign a numerical revenue, which is composed of a penalty on the number of deadlines missed while the frame was being processed, a reward for the quality level at which the frame was processed, and a penalty if this quality level was different from the previously used quality level. Any control strategy that maximizes the average revenue over a sequence of frames will balance the three objectives. The average revenue provides a tunable QoS metric for the task. Tuning the QoS measure, i.e. determining appropriate values for the penalties and rewards on the basis of user-perception experiments, falls outside the scope of this paper. If the processing time for each frame and for each quality level is known in advance, finding a control strategy that maximizes the average revenue is easy. In that case, the optimal quality levels can be computed off-line using classical dynamic programming (Bellman, 1957). Obviously, this approach is not realistic, but we will use it to assess the performance of run-time strategies. As a first step towards a run-time strategy, we model the system as a Markov Decision Process (MDP) (Puterman, 1994). An MDP considers a set of states, and a set of actions for each state. At discrete moments in time, a controller observes the current state  of the system, and subsequently takes an action g . This action influences the system, and, as a result, the controller observes a new state 9h at the next discrete moment. This new state is not deterministically determined by the action and the previous state, but each

combination ij g  h@k has a fixed known probability. A numerical revenue

is associated with each ij g  hlk . The goal of the MDP is to find an actionselection strategy that maximizes the average revenue over all state transitions during the lifetime of the system.

8 For our system, the discrete moments in time are the start points E . The state naturally includes the task’s progress at the start point, UV . Because we penalize quality-level changes, the state also includes the quality level used for the preceding frame (the previous quality level P -,. ). Hence,  +
i-UX P

-,.mk . Finally, an action is the selection of a quality level P . In our first strategy, the MDP strategy, we solve the MDP off-line. This

implies that the state-transition probabilities n$oij g hlk and corresponding expected revenues are needed in advance. We measured the per-frame processing times for a number of representative video sequences, at the different quality levels, and used those traces to compute the state-transition probabilities and expected revenues. The MDP is then solved off-line for a particular value of the budget Q . This results in a (static) Markov policy, which is a set of
state-action pairs, in our case pairs i-U> P

-,.pqP rk . Figure 4 shows a graphical example of a Markov policy for a particular budget, for a scalable algorithm with four quality levels, s  (low) to sL (high). The horizontal axis represents the previous quality level. The vertical axis represents the progress at the start point. The figure has four columns, one for each previous quality level. In this figure, each state is represented by a particular progress value in a particular column. The gray scale indicates the action to be taken. For example, if the progress is 1 and the previous quality level is sX. , the action is s K . For mathematical details, we refer to W¨ust and Verhaegh (2004a). During run time, at each start point the controller decides its action by consulting the Markov policy, a simple table look-up. A table that represents a Markov policy has a column for each previous quality level. For each column, the table entries correspond to quality-level transitions. The total number of table entries in a column corresponds to the maximum number of quality-level transitions. If the policy is monotonic, i.e. a higher progress results in an equal or higher quality level action, at most nq entries per column are needed, where nq denotes the number of quality levels. 2

q3 progress

q2 q1

1

q0 0

q0

q

q

1 2 previous quality level

Figure 4. An example Markov policy for a particular budget.

q3

9 The MDP can also be solved at run time, by means of Reinforcement Learning (RL) (Sutton and Barto, 1998). An RL strategy starts with no knowledge at all, and has to learn optimal behavior from the experience it gains during run time. To this end it constructs and maintains a dynamic RL policy, which is a set of state-action values for a given set of states and a given set of actions. State-action values provide estimates of how good it is to select a particular action in a given state. To obtain a finite set of state-action values, the continuous progress must be made discrete. The number of state-action K values equals the number of discrete progress values multiplied by nq . An RL strategy does not require pre-determined probabilities of state transitions

n$oij g hlk and corresponding expected revenues; these probabilities and revenues are implicitly learned in the state-action values. At each start point, the state-action values are learned (updated) based on the processing time of the just-completed frame. As a learning algorithm, we used a modified version of the Q-Learning algorithm (Sutton and Barto, 1998). The modification enables the controller to update all state-action values instead of just one at each start point, which significantly speeds up convergence. The state-action values are applied to choose the quality level. Given the state, the quality level (= action) yielding the largest state-action value is chosen. We refer to this approach as the RL strategy. 5.2. L OAD FLUCTUATIONS The MDP and RL strategies implicitly assume that the processing times of successive frames are mutually independent. In many practical situations, however, there is a relation in the load of successive frames. This holds in particular for frames that are part of the same video scene or shot. As a result, the MDP and RL strategies may perform sub-optimal. In this section, we distinguish between stochastic and structural load fluctuations. This distinction is used in Section 5.3 to enhance the MDP and RL strategies. Stochastic load fluctuations are the normal per-frame load fluctuations. For MPEG decoding, stochastic load fluctuations are mainly caused by the difference in decoding complexity between I, P, and B frames (Isovi´c et al., 2003), and to a lesser extent by the varying content complexity of frames. We use the notion structural load to express the overall load over a window of frames that is sufficiently large to filter out the short-term load dependencies between frames, and to reveal the content-dependent load fluctuations. For the controller, the structural load can be an important source of information to estimate the processing time for a frame. A straightforward approach to compute the structural load is by applying a filter, such as a finite impulse response (FIR) filter or an infinite impulse response (IIR) filter (Oppenheim and Schafer, 1975). An FIR filter produces

10 a weighted average over the past  inputs. An IIR filter uses a feedback mechanism, which means that the filter’s output is implicitly based on all past inputs. An example of an IIR filter is the exponential recency-weighted average (Sutton and Barto, 1998). This filter weights recent inputs more heavily than long-past ones. Let tAu and vEu denote the w -th input and output of the filter, respectively. Given input tu , output vu is given by vEu^5vEu ,. xyi-t;uz_IvEu ,. k




where x is a fixed step-size parameter i{J / xTB k . Initial value v> is usually chosen equal to t3. . Using this filter, every input tA [i BROB|wk is assigned u , , which decreases exponentially as w increases. The a weight x}i _~x'k sum of these w weights is exactly one. The closer x approaches zero, the , the input stronger the filter takes past inputs into account. In case x and output of the filter are the same. Figure 5 shows the decoding times for a sequence of MPEG-2 frames, and the corresponding structural load (black line), computed using an exponential recency-weigthed average with x€  J .

processing time (ms)

40 35 30 25 20 15

1

200

400 600 frame number

800

1000

Figure 5. The decoding times for a sequence of MPEG-2 frames, and the corresponding structural load (black line), computed using an exponential recency-weigthed average with ƒ‚)„…‡† .

5.3. S CALED

BUDGET ENHANCEMENT

In this section, we compensate the MDP and RL strategies for not considering load dependencies by means of a scaled budget enhancement. This enhancement consists of two parts. First we track the structural load, by filtering out the stochastic load fluctuations, and compare it to a reference budget. Next, we compensate our original MDP and RL strategies for structural load fluctuations relative to this reference budget. Since the controller cannot adjust the allocated budget, it applies the policy derived for an inversely proportional budget, the scaled budget. We denote the enhanced strategies by MDP* and RL*, respectively.

A

processing time (ms)

11 40 30 20 10

1

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

3000

3500

4000

4500

5000

3000

3500

4000

4500

5000

frame number

B

complication

1.6 1.4 1.2 1 0.8 0.6

1

500

1000

1500

2000

2500

C

scaled budget (ms)

frame number 35 30 25 20

1

500

1000

1500

2000

2500 frame number

Figure 6. The decoding times for a sequence of MPEG-2 frames (A), the corresponding complication factors and running complication factors (B), and the corresponding scaled budget for ˆ ‚1‰mŠ ms (C).

At each start point  , we first determine complication factor cf , the ratio between the processing time of the just-completed frame, pt -,. , and the expected processing time for a frame processed at quality level P -,. , ept i{P

-,.k . Hence, cf  pt -,.‹ ept i{P

-,.Œk . For E. we define cf .  . The expected processing times have been derived off-line for each quality level. The gray graph in Figure 6A shows the decoding times for a sequence of 5000 MPEG2 frames, all processed at one quality level. The dashed line, at 25.4 ms, indicates the average processing time over the entire sequence. By using this average processing time as the expected processing time for the applied quality level, we obtain the gray graph of complication factors shown in Figure 6B. In our approach, we assume that the complication factor for a frame is more or less independent of the applied quality level: if the frame is processed at a different quality level, it should give roughly the same complication factor. We need this assumption because the controller can only measure the processing time for the quality level at which the completed frame has been processed, which is not necessarily the quality level selected for subsequent frames. We validated the assumption for the scalable MPEG-2 decoder we used in our experiments, and the results were positive. The complication factors provide a quality-level independent measure for the load. To determine the structural load of these complication factors, we apply a filter. In this way, for each complication factor cf we obtain a running complication factor rcf . The black graph in Figure 6B shows the running complication factors obtained by applying an exponential, recency-weighted b average with a step-size parameter xI(J J .

12 If rcf deviates from one (the dashed line in Figure 6B), it appears as if the processing budget available to the task deviates from its available budget a Q . If rcf  , a budget QŽJ ms appears as a budget of only 25 ms. If a‘ rcf J , that same budget appears as a budget of 37.5 ms. We therefore define a scaled budget sb as Q ‹ rcf . In Figure 6C, the dashed line at 27 ms indicates the budget Q . To obtain the scaled budgets, the black graph in Figure 6C, budget Q is divided by the running complication factors of Figure 6B. The MDP* strategy enhances the MDP strategy in the following way. First, the traces are normalized, i.e. for each quality level the structural load fluctuations are filtered out. The MDP is then solved for a set of selected scaled budgets, using state-transition probabilities and expected revenues that are computed based on the normalized traces. This results in a set of Markov policies, one for each scaled budget. This set can be viewed as a space with three dimensions. The first two dimensions are the scaled budget and the progress, and the third dimension is the previous quality level. Figure 7 shows an example set of Markov policies, resulting from 61 MDP instances with ab  scaled budgets J ms, J ms, , ’EJ ms. Because it is difficult to visualize the set of Markov policies in a 3-dimensional figure, we visualize four 2dimensional figures, one for each previous quality level. During run time, at each start point the controller first determines the state, which is given by the scaled budget, the progress, and the previous quality level. Next, the controller interpolates between the derived policies to select the quality level. For example, if the state is given by a scaled budget of 28.2 ms, a progress of 0.5, and a previous quality level s K , the controller interpolates between the policies derived for scaled budgets 28.0 ms and 28.5 ms, and selects quality level sK . This is indicated by a ‘+’ in the figure. For mathematical details on MDP*, we refer to W¨ust and Verhaegh (2004b). Note the anomaly in Figure 7 for previous quality level sK , the reappearance of s  at a scaled budget of 23.5 ms. A possible explanation for this anomaly is the following. At a scaled budget of 23.5 ms, quality level s K is beginning to be selected for high progress values. To compensate for the higher processing times required by sK , quality level s  reappears in the policy. In the RL* approach we add the scaled budget directly to the state, i.e. the scaled budget becomes a third dimension of the state space. At each start point, the controller selects the quality level that yields the largest state-action value for the current state (= progress, previous quality level, scaled budget). For MDP*, such a straightforward solution is not feasible, which is due to computational limitations.

13 previous quality level q1 2

1.5

1.5

q0

1

progress

progress

previous quality level q0 2

q1

0.5 0

10

15

20 25 30 35 scaled budget (ms)

10

1.5

1.5

q0

q1

q2

q3

0.5 0

q0 10

15

20 25 30 35 scaled budget (ms)

q2

15

20 25 30 35 scaled budget (ms)

40

previous quality level q3 2 progress

progress

previous quality level q2 2

1

q1

0.5 0

40

q0

1

40

q1

1

q2

q3

0.5 0

10

15

20 25 30 35 scaled budget (ms)

40

Figure 7. A set of Markov policies, resulting from 61 MDP instances with scaled budgets †“„ ms, †”„… • ms, …”…”… , – „ ms.

6. Simulation Experiments 6.1. E XPERIMENTAL

SET- UP

To assess the performance of the different run-time strategies, we have run simulation experiments. In these experiments, we first measured the per-frame processing times for decoding a number of MPEG-2 sequences, using a scal

able MPEG-2 decoder with four quality levels, s  s L , in order of increasing quality, running on a TriMedia 1300 (180 MHz) processor (Slavenburg et al., 1996). This decoder, which is based on IDCT pruning, was made available to us by colleagues at Philips Research (Peng, 2001; Zhong et al., 2002), and was integrated in a demonstrator annex research platform (Hentschel et al., 2003; Otero P´erez and Nitescu, 2002). For each sequence we produced four processing-time traces, one for each quality level. We used three 25 frames/s MPEG-2 sequences: a collection of tv shows (‘tv’), a movie (‘mov’), and a collection of soccer fragments (‘soc’). Hence, —˜’EJ ms. Table I shows for each sequence the number of frames,

and the average processing time per frame for quality levels s  s L . The traces were used for three purposes. First, to derive statistics for the MDP. Second, to determine expected processing time values for the different quality

14 levels; for this we use the average processing times from Table I. Finally, to simulate the behavior of the scalable decoder under different strategies. Table I. The number of frames and the average processing time for quality levels ™“š› …”…”… ›j™”œ , for the three used sequences. average processing time sequence

#frames

™qš

™m

™qž

™“œ

tv mov soc

230,936 162,900 138,987

23.2 ms 22.9 ms 21.3 ms

24.1 ms 23.7 ms 22.4 ms

25.4 ms 24.7 ms 23.3 ms

28.0 ms 28.0 ms 24.9 ms

In our setup, we ignore the different MPEG frame types (I, P, and B). The reason we do so is that in earlier experiments we took MPEG frame types explicitly into account in the MDP model, but found no significant effect on the results. We tested the strategies MDP( Ÿ ), MDP*(Ÿ ), and RL*( Ÿ ), where Ÿ denotes a trace (‘tv’, ‘mov’, or ‘soc’). In MDP( Ÿ ) and MDP*(Ÿ ), the state-transition probabilities and expected revenues are based on trace Ÿ . In MDP*(Ÿ ) and RL*(Ÿ ), the average processing times of Ÿ are used for the expected processing time values. For comparison, we also tested the simple strategies

 sL , respectively. MoreQ0, ,Q3, which always select quality level s over, for each trace we also computed the quality-level actions that would lead to a maximum average revenue, using classical dynamic programming (DP). The performance of the DP strategy cannot be met by any run-time strategy, because it requires complete knowledge of all future processing times. The closer a run-time strategy performs to DP, the better. Unless mentioned otherwise, we use 0Ž , which implies that the decoder can work ahead by at most two deadline periods. We determined the QoS parameters, or revenues, in consultation with video experts. For each deadline

sL we miss we gave a penalty of 10,000. For choosing quality level sE gave rewards of 4, 6, 8, and 10, respectively. For increasing the quality by one level we gave a penalty of 10, for two levels we gave a penalty of 100, and for three levels we gave a penalty of 1,000. For decreasing the quality level these penalties were multiplied by five. To track the structural load during run time, we applied an IIR filter, more precisely, an exponential, recency-weighted average with a step-size  parameter x HJ , based on the results described by W¨ust and Verhaegh (2004b). For each strategy and for each trace Ÿ , we performed 61 simulations, in which we simulate that trace Ÿ is processed under control of the strategy, for  budgets 10 ms, 10.5 ms, , 40 ms.

15 6.2. R ESULTS Figure 8 shows the average revenue that we measured for strategies Q3, MDP(tv), MDP*(tv), RL*(tv), and DP, applied in simulations on sequence ‘tv’, as a function of the budget. Figure 9 shows the corresponding number of deadline misses. 10 DP

average revenue

8

MDP*(tv) RL*(tv)

6

MDP(tv)

Q3

4 2 0 -2

26

28

30

32 34 budget (ms)

36

38

40

Figure 8. The average revenue for different strategies applied to sequence ‘tv’, as a function of the budget.

number of deadline misses

1200 1000 800 Q3

600 MDP*(tv) RL*(tv)

400 200

MDP(tv)

DP 0

26

28

30

32 34 budget (ms)

36

38

40

Figure 9. The number of deadline misses for different strategies applied to sequence ‘tv’, as a function of the budget.

For all strategies, the average revenue converges to 10 as the budget increases, which implies that no deadlines are missed and that almost all frames are processed at s L (ranging from 99.9% for RL*(tv) to 100% for Q3, at a budget of 38 ms). For comparison, the worst-case decoding time for the sequence ‘tv’ is 52.3 ms. Apparently, the work-ahead of two periods suffices to absorb the load fluctuations from a budget of 38 ms onwards. For smaller budgets, Q3 performs poorly due to the high penalty for deadline misses,

16 and is clearly outperformed by the other strategies. The strategies with budget scaling, MDP*(tv) and RL*(tv), perform close to the optimal strategy DP. Apparently, RL*(tv) learns fast, because its performance is very close to MDP*(tv). The performance dip of MDP(tv) is caused by an increased number of deadline misses in a budget area where the strategy increasingly selects quality levels higher than s9 . The deadline misses occur because the strategy is unable to reduce the quality level fast enough when the structural load suddenly increases. 6.2.1. Quality-level usage Figure 10 shows, for strategy RL*(tv) applied in simulations on sequence ‘tv’, for each quality level the percentage of times it was chosen. From the figure, we can observe that for lower budgets, quality level s is selected for most frames. As the budget increases, higher quality levels are selected more frequently. The quality levels sX. and sK are mainly used over a relatively small budget range. 100

percentage of usage

80

q0

q3

60 40

q2

20 0

q1 20

25

30 budget (ms)

35

40

Figure 10. The quality level usage for the RL*(tv) strategy applied to sequence ‘tv’, as a function of the budget.

Next, Table II shows the quality-level frequencies, the number of deadline misses, and the number of quality-level increases, for strategies DP, MDP*(tv), ‘ ¡ab J ms, and Qy and RL*(tv) applied to sequence ‘tv’, for Q+ ms. The number of quality-level decreases is about the same as the number of increases (maximum difference is three). If we choose a budget of 28.0 ms, the average-case processing time at s9L , the strategies DP, MDP*(tv) and RL*(tv) suffer from 34, 88, and 70 deadline misses, respectively, on a total of 230,936 frames. This boils down to approximately one to three missed deadlines every five minutes. At a slightly higher budget, 29.5 ms, the number of missed deadlines is almost negligible. RL*(tv) is a little more conservative than MDP*(tv), in the sense that it selects lower quality levels more often. Because this strategy also leads to

17 Table II. The quality-level frequencies, the number of deadline misses, and the number of quality-level increases, for DP, MDP*(tv), and RL*(tv) applied to sequence ‘tv’, for ˆ ‚1‰Œ¢… „ ms and ˆ ‚G‰£… • ms.

ˆ ‚1‰Œ¢… „ ms

DP

MDP*(tv)

RL*(tv)

5,254 18,957 52,037 154,654

34,668 9,625 59,277 127,278

70,145 47,102 53,715 32,904

deadline misses

34

88

70

quality-level increases

588

5,140

505

DP

MDP*(tv)

RL*(tv)

330 6,589 36,486 187,529

13,035 6,626 46,821 164,450

15,916 49,716 91,007 47,294

2

4

3

767

3,752

657

™š

™  ™qž ™“œ

ˆ ‚1‰Œ£… • ms ™š

™  ™ ž ™œ deadline misses quality-level increases

fewer quality-level changes, the overall effect in terms of average revenue is about the same as for MDP*(tv). If we compare these two strategies with DP, we observe that they both select quality level s more frequently than DP does. The main difference between DP and the other two strategies is that DP can prepare for structural load increases, whereas the others can only react to them. 6.2.2. Budget requirements Table III shows the budgets required to achieve different values of the average revenue, for strategies Q3, MDP(tv), MDP*(tv), RL*(tv) and DP applied to sequence ‘tv’. For example, to achieve an average revenue (= QoS value) of 8, DP requires a budget of 28.3 ms, which is very close to 28 ms, the average processing time for s L . MDP*(tv) and RL*(tv) require a budget of 29.5 ms and 29.8 ms, respectively. MDP(tv) requires 34.0 ms, which is only slightly better than the 35.4 ms of Q3 (frame skips only). 6.2.3. Gain time Figure 11 shows a graph for the average CPU consumption per period, as function of the budget, for strategy MDP*(tv) applied to sequence ‘tv’. Up to a budget of 25 ms, the task hardly produces any gain time, i.e. the task fully

18 Table III. The budget required to achieve a certain average revenue, for different strategies applied to sequence ’tv’. average revenue

Q3

MDP(tv)

MDP*(tv)

RL*(tv)

DP

0 1 2 3 4 5 6 7 8 9 9.9

34.2 ms 34.3 ms 34.4 ms 34.5 ms 34.6 ms 34.8 ms 35.0 ms 35.2 ms 35.4 ms 35.9 ms 36.8 ms

28.9 ms 29.0 ms 29.2 ms 29.5 ms 29.7 ms 32.7 ms 33.3 ms 33.7 ms 34.0 ms 34.7 ms 35.8 ms

27.7 ms 27.8 ms 27.9 ms 28.0 ms 28.1 ms 28.3 ms 28.5 ms 28.9 ms 29.5 ms 31.1 ms 35.0 ms

27.6 ms 27.7 ms 27.8 ms 28.0 ms 28.2 ms 28.4 ms 28.6 ms 29.0 ms 29.8 ms 31.3 ms 34.9 ms

27.0 ms 27.1 ms 27.2 ms 27.3 ms 27.4 ms 27.5 ms 27.7 ms 27.9 ms 28.3 ms 28.9 ms 33.1 ms

average CPU consumption per period (ms)

consumes the assigned budget. As expected, the average CPU consumption per period converges to 28.0 ms, which is the average processing time per frame for sequence ‘tv’ at quality level sL . 40

ge

35

m mu

usa

xi

ma

30

28.0 ms

25 20 15 10

10

15

20

25 budget (ms)

30

35

40

Figure 11. The average CPU consumption per period, as function of the budget, for strategy MDP*(tv) applied to sequence ‘tv’.

Next, Table IV shows the average CPU consumption per period to achieve a certain average revenue, for strategies Q3, MDP(tv), MDP*(tv) and RL*(tv), applied to sequence ‘tv’. Unfortunately, we have no data for the optimal strategy DP, which is due to limitations of the simulation framework. When comparing the results in this table with the results in Table III, we observe overall a significant difference between the required budget and the average CPU consumption. This difference is known as gain time. There is, however,

19 another way to look at these results. By controlling the quality of service, a significant reduction of gain time can be achieved. For example, to achieve an average revenue of 8, using RL*(tv) the task requires a budget of 29.8 ms, while its average CPU consumption is only 25.8 ms. This results in an average gain time of 4 ms, approximately 13% of the budget. For comparison, using Q3 the gain time is 7.4 ms, which is approximately 21% of the budget. QoS control is an effective way of reducing gain time. The remaining gain time can be put to good use by applying gain time reclamation. Table IV. The average CPU consumption per period to achieve a certain average revenue, for different strategies applied to sequence ’tv’. average revenue

Q3

MDP(tv)

MDP*(tv)

RL*(tv)

0 1 2 3 4 5 6 7 8 9 9.9

27.9 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms 28.0 ms

26.9 ms 26.9 ms 27.0 ms 27.1 ms 27.2 ms 27.8 ms 27.9 ms 27.9 ms 27.9 ms 28.0 ms 28.0 ms

25.9 ms 25.9 ms 26.0 ms 26.1 ms 26.1 ms 26.2 ms 26.4 ms 26.5 ms 26.8 ms 27.3 ms 27.9 ms

24.2 ms 24.3 ms 24.4 ms 24.4 ms 24.6 ms 24.7 ms 24.9 ms 25.2 ms 25.8 ms 26.8 ms 27.9 ms

6.2.4. Latency To study the influence of the latency on the performance of the control strate

Œc , and we gies, we have also computed strategy MDP*(tv) for ¤f’ have applied the resulting strategies in simulations on sequence ‘tv’ for corresponding values of the latency. Figure 12 shows the average revenue that we

Œc measured as function of the budget, for ¥~Ž . The higher the latency, the more space is given to the task to even out its varying load by working ahead. As a result, larger bursts in the load of frames can be handled without missing a deadline. For a given budget, a higher latency therefore results in an equal or higher average revenue. For increasing values of the latency, the increase in average revenue becomes smaller, as the numbers of bursts that cannot be properly handled decreases. A higher latency requires more input and more output frame buffers. For reasons of costs, we want to keep the number of frame buffers small. Moreover, it is not always possible to delay a video stream by a high latency. As

20 10

average revenue

8

δ=7

6

δ=3

4 2 0 -2

26

28

30

32

34

36

38

40

budget (ms)

Figure 12. The average revenue for strategy MDP*(tv) applied to sequence ‘tv’, as function of the budget, for ¦ ‚)§ › …”…“… › Š .

an example, when an audio stream and a corresponding video stream are processed using independent devices, there is no possibility to introduce an additional delay in the audio as well. Human perception studies show that a delay of 80 ms between audio and video (audio ahead of video, or video ahead of audio) is still acceptable, whereas a delay of 160 ms is generally considered unacceptable (Steinmetz, 1996). At a frame rate of 25 fps, a delay of 160 ms corresponds to four video frames. 6.2.5. Cross-trace experiments Finally, Table V gives the average revenues for all simulations we carried out for ¨Ž . Because we are interested in both a positive average revenue and a lower than worst-case resource allocation, for each sequence we first identified a ‘sensible’ budget range, the range for which DP results in an average revenue between 0 and 9.9. The entries of Table V give the average revenue over the specified budget range. We observe that Q0, Q1, Q2 and Q3 perform poorly. The MDP strategies perform better, but still bad compared to the MDP* and RL* strategies, which consistently perform much closer to optimum. If we compare the cross relations between statistics and simulations for the MDP strategies, we observe that the ‘tv’ statistics consistently yield better results. An explanation for this result is that the ‘tv’ statistics lead to a more conservative strategy: for a given budget, MDP(tv) selects lower quality levels more frequently than MDP(mov) or MDP(soc). Hence, fewer deadlines are missed in structurally hard scenes. For the MDP* strategies, we observe that the deviations are much smaller than for MDP, and that the ‘tv’ statistics are slightly outperformed by the ‘mov’ statistics in the ‘mov’ simulations. More importantly, the MDP* strategies are quite insensitive to using the statistics

21 of a different sequence. This is a favorable result, as in practice a strategy will be applied to video sequences with unknown statistics. For the RL* strategies, the cross relations between statistics and simulations are negligible. Since these strategies learn the statistics during run time, the only ‘statistics’ used are the expected processing time values for the different quality levels. We observe that the RL* strategies perform equally well as the MDP* strategies. Apparently they learn fast. Table V. The average revenue measured for different strategies applied to the three sequences, over a sensible budget range. sequence: sensible budget range:

tv 27.5–33 ms

mov 25–30.5 ms

soc 25–28.5 ms

DP

8.92

8.65

8.69

Q0 Q1 Q2 Q3

3.22 1.39 © 25.09 © 207.43

© 483.09

© 151.61

1.19 © 50.69 © 80.69

7.27 4.81 0.68

5.75 2.38 © 1.33

MDP*(tv) MDP*(mov) MDP*(soc)

7.24 6.46 6.99

7.39 7.53 7.06

7.00 5.94 6.83

RL*(tv) RL*(mov) RL*(soc)

7.15 7.09 7.17

7.54 7.46 7.41

6.51 6.46 6.59

MDP(tv) MDP(mov) MDP(soc)

3.53

2.89

© 2.35

© 1.85

© 46.92

© 24.27

7. Conclusion We presented an approach to control local QoS for a high-quality video processing task, with given resource constraints, to which we applied a combination of deadline relaxation, acceptance for occasional deadline misses, and approximate computation. We identified three elements in the QoS specification for high-quality video: processing quality, deadline misses, and quality changes. These tunable QoS parameters are based on video expertise, and are currently being validated in user-perception experiments. The aim of our work was to find control strategies that balance these three elements.

22 We first modeled the real-time processing behavior of a single-threaded soft real-time task. Next, we considered the problem of designing a controller as a discrete stochastic decision problem known as Markov Decision Process. We presented two solutions to this problem, a table-driven approach based on off-line optimization (MDP), and a run-time approach based on Reinforcement Learning (RL). We then enhanced both approaches to handle structural load fluctuations, by introducing a scaled budget extension. The two resulting strategies, MDP* and RL*, performed close to optimum in simulation experiments based on a scalable MPEG-2 decoder and three video sequences. We set the QoS parameters in such a way that deadline misses were heavily penalized. Given a close-to-average-case resource allocation with respect to the highest quality level, MDP* and RL* only showed incidental deadline misses. We esteem RL* to be the best strategy, because, in contrast to MDP*, it barely needs pre-determined processing-time statistics, which makes it more suitable to be applied to new sequences. We conclude that Reinforcement Learning can provide a powerful contribution to QoS control in dynamic real-time systems. Some issues remain to be addressed before the results can be used in a real product. First, in our experimental set-up it was very difficult to tune the QoS parameters and validate the resulting video sequences by means of user-perception experiments. We did some preliminary experiments in this direction, but a full-fledged investigation was out of scope. A sensitivity analysis on the QoS parameters can give an early indication of the relevance of parameter tuning. Second, we are aware that our real-time processing model is a simplification of a real-life system. The implications of a more realistic model would have to be investigated. Another issue is the overhead of the control strategies in relation to the amount of computation involved in processing frames. Because our experiments are simulations, we can only qualify the relative overhead of the control strategies. Assuming interlaced video with a picture resolution of 720x576 pixels, for each frame there is a total of 207,360 pixels to be computed. Using MDP, at each start point the controller has to determine the state, and to perform a simple table lookup. For MDP*, an additional step of linear interpolation is required. Hence, the computational overhead of MDP and MDP* is low. For RL*, the computational overhead is higher, because at each start point all state-action values are updated. In the simulation experiments, we achieved good results with a set of 252 state-action values. Updating a state-action value requires only a small constant number of steps. Hence, also for RL* the computational overhead is low. In the context of the QoS RM framework, two issues remain to be addressed: first, the cooperation with the global QoS manager, and second, the use of gain time. The QoS manager allocates budgets to tasks based on resource estimates. Our experiments illustrate that a sensible budget is content,

23 i.e. sequence, dependent. Hence, dynamic adaptation of budgets is needed. For example, the local controller of a task might request a larger budget if a certain threshold on the scaled budget is exceeded. The use of gain time would enhance the overall performance of the system. Effective re-allocation of spare capacity is an essential part of any approach that aims at optimizing systems with scarce resources. We are inclined to believe that the actual budget needs indicate a potential for refinements of existing resource reservation models, such as conditionally guaranteed budgets (Bril and Steffens, 2001; Bril, 2004). Acknowledgements We would like to thank Gerhard Fohler, Damir Isovi´c, Laurent¸iu P˘ap˘al˘au, Clara Otero P´erez, and Rob Wubben for their contributions to this work. We are also very grateful to the people who provided the scalable MPEG decoder, Yingwei Chen, Tse-Hua Lan, Sharon Peng, and Zhun Zhong. This work was supported by the IST 2000-30026 OZONE EC project (http://www.extra.research.philips.com/euprojects/ozone/).

References Audsley, N.C., Burns, A., Davis, R.I., and Wellings, A.J. 1995. Integrating unbounded software components into hard real-time systems. In S. Natarajan, editor, Imprecise and Approximate Computation, Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 63–86. Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Braspenning, R.A., de Haan, G., and Hentschel, C. 2002. Complexity scalable motion estimation. In Proc. SPIE, Vol. 4671, Visual Communications and Image Processing, San Jos´e, CA, pp. 442–453. Bril, R.J., and Steffens, E.F.M. 2001. User focus in consumer terminals and conditionally guaranteed budgets. In Proc. 9 ª « International Workshop on Quality of Service (IWQoS), Karlsruhe, Germany, Vol. 2092 of Lecture Notes in Computer Science (LNCS), Springer Verlag, pp. 107–120. Bril, R.J., Hentschel, C., Steffens, E.F.M., Gabrani, M., Van Loo, G.C., and Gelissen, J.H.A. 2001. Multimedia QoS in consumer terminals. In Proc. IEEE Workshop on Signal Processing Systems (SIPS), Antwerp, Belgium, pp. 332–343. Bril, R.J. 2004. Real-time scheduling for media processing using conditionally guaranteed budgets. PhD thesis, Technische Universiteit Eindhoven, The Netherlands. Buttazzo, G.C. 1997. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands. Garc´ıa Valls, M., Alonso, A., Ru´ız, J.F., and Groba, A. 2002. An architecture of a Quality of Service resource manager for flexible multimedia embedded systems. In Proc. 3 ¬®­ International Workshop on Software Engineering and Middleware (SEM), Orlando, FL, Vol. 2596 of Lecture Notes in Computer Science (LNCS), Springer Verlag, pp. 39–57.

24 Hamann, C.-J., L¨oser, J., Reuther, L., Sch¨onberg, S., Wolter, J., and H¨artig, H. 2001. Qualityassuring scheduling: using stochastic behavior to improve resource utilization. In Proc. 22 ¯ ­ IEEE Real-Time Systems Symposium (RTSS), London, UK, pp. 119–128. Hentschel, C., Bril, R.J., Gabrani, M., Steffens, L., Van Zon, K., and Van Loo, S. 2001. Scalable video algorithms and dynamic resource management for consumer terminals. In Proc. International Conference on Media Futures (ICMF), Florence, Italy, pp. 193–196. Hentschel, C., Bril, R.J., Chen, Y., Braspenning, R., and Lan, T.-H. 2003. Video Quality-ofService for consumer terminals: a novel system for programmable components. In IEEE Transactions on Consumer Electronics, 49(4):1367–1377. Isovi´c, D., Fohler, G., and Steffens, L. 2003. Timing constraints of MPEG-2 decoding for high-quality video: misconceptions and realistic assumptions. In Proc. 15 ª « Euromicro Conference on Real-Time Systems (ECRTS), Porto, Portugal, pp. 73–82. Isovi´c, D. and Fohler, G. 2004. Quality aware MPEG-2 stream adaptation in resource constrained systems. In Proc. 16 ª « Euromicro Conference on Real-Time Systems (ECRTS), Catania, Italy, pp. 23–32. Klein, M.H., Ralya, T., Pollak, B., Obenza, R., and Gonz´alez Harbour, M. 1993. A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Kluwer Academic Publishers, Dordrecht, The Netherlands. Koren, G. and Shasha, D. 1995. Skip-over: algorithms and complexity for overloaded systems that allow skips. In Proc. 16 ª « IEEE Real-Time Systems Symposium (RTSS), Pisa, Italy, pp. 110–117. Lan, T., Chen, Y., and Zhong, Z. 2001. MPEG2 decoding complexity regulation for a media processor. In Proc. Fourth IEEE Workshop on Multimedia Signal Processing (MMSP), Cannes, France, pp. 193–198. Lee, C., Lehoczky, J., Rajkumar, R., and Siewiorek, D. 1999. On Quality of Service optimization with discrete QoS options. In Proc. Fifth IEEE Real-Time Technology and Applications Symposium (RTAS), Vancouver, Canada, pp. 276–286. Lu, C., Stankovic, J.A., Tao, G., and Son, S.H. 1999. Design and evaluation of a feedback control EDF scheduling algorithm. In Proc. 20 ª « IEEE Real-Time Systems Symposium (RTSS), Phoenix, AZ, pp. 56–67. Lu, C., Stankovic, J.A., Abdelzaher, T.F., Tao, G., Son, S.H., and Marley, M. 2000. Performance specifications and metrics for adaptive real-time systems. In Proc. 21 ° ª IEEE Real-Time Systems Symposium (RTSS), Orlando, FL, pp. 13–23. Mietens, S., de With, P.H.N., and Hentschel, C. 2004. Computational-complexity scalable motion estimation for mobile MPEG encoding. In IEEE Transactions on Consumer Electronics, 50(1):281–291. Oppenheim, A.V., and Schafer, R.W. 1975. Digital Signal Processing. Prentice-Hall, Englewood Cliffs, NJ. Otero P´erez, C.M., and Nitescu, I. 2002. Quality of Service resource management for consumer terminals: demonstrating the concepts. In Proc. Work-in-Progress Session 14 ª « Euromicro Conference on Real-Time Systems (ECRTS), Vienna, Austria, pp. 29–32. Otero P´erez, C.M., Steffens, L., Van der Stok, P., Van Loo, S., Alonso, A., Ru´ız, J.F., Bril, R.J., and Garc´ıa Valls, M. 2003. QoS-based resource management for ambient intelligence. In T. Basten, M. Geilen, and H. de Groot, editors, Ambient Intelligence: Impact on Embedded System Design, Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 159–182. Peng, S. 2001. Complexity scalable video decoding via IDCT data pruning. In Digest of technical papers IEEE International Conference on Consumer Electronics (ICCE), Los Angeles, CA, pp. 74–75. Puterman, M.L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, New York.

25 Rajkumar, R., Juvva, K., Molano, A., and Oikawa, S. 1998. Resource kernels: a resourcecentric approach to real-time and multimedia systems. In Proc. SPIE, Vol. 3310, Conference on Multimedia Computing and Networking, San Jos´e, CA, pp. 150–164. Sha, L., Lehoczky, J.P., and Rajkumar, R. 1986. Solutions for some practical problems in prioritized preemptive scheduling. In Proc. Š ª « IEEE Real-Time Systems Symposium (RTSS), New Orleans, LA, pp. 181–191. Slavenburg, G.A., Rathnam, S., and Dijkstra, H. 1996. The TriMedia TM-1 PCI VLIW mediaprocessor. In Proc. Eight IEEE Symposium on High-Performance Chips (Hot Chips 8), Stanford, CA, pp. 171–177. Steinmetz, R. 1996. Human perception of jitter and media synchronization In IEEE Journal on Selected Areas in Communications, 14(1):61–72. Sutton, R.S., and Barto, A.G. 1998. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA. W¨ust, C.C., and Verhaegh, W.F.J. 2004a. Quality control for scalable media processing applications. In Journal of Scheduling, 7(2):105–117. W¨ust, C.C., and Verhaegh, W.F.J. 2004b. Dynamic control of scalable media processing applications. In W. Verhaegh, E. Aarts, and J. Korst, editors, Algorithms in Ambient Intelligence, Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 259–276. Zhao, W., Chew Lim, C., Liu, J.W.S., and Alexander, P.D. 1995. Overload management by imprecise computation. In S. Natarajan, editor, Imprecise and Approximate Computation, Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 1–22. Zhong, Z., Chen, Y., and Lan, T.-H. 2002. Signal adaptive processing in MPEG-2 decoders with embedded resizing for interlaced video. In Proc. SPIE, Vol. 4671, Visual Communications and Image Processing, San Jos´e, CA, pp. 434–441.