Rafael Accorsi
email: accorsi@iig.uni-freiburg.de

Thomas Stocker
email: stocker@iig.uni-freiburg.de

Discovering Workflow Changes with Time-based Trace Clustering

This paper proposes a trace clustering approach to support process discovery of configurable, evolving process models. The clustering approach allows auditors to distinguish between different process variants within a timeframe, thereby visualizing the process evolution. The main insight to cluster entries is the "distance" between activities, i.e. the number of steps between an activity pair. By observing non-transient modifications on the distance, changes in the original process shape can be inferred and the entries clustered accordingly. The paper presents the corresponding algorithms and exemplifies its usage in a running example.

Introduction

Process discovery aims to reconstruct process models from execution logs. Specifically: given a log, each of the cases (i.e. execution traces) is analyzed, eventually producing a (Petri net) model of the process. The reconstructed model provides a basis for other process mining techniques, e.g. conformance checking and case prediction. Such techniques are not only useful for process designers, but essential tools for auditors analyzing process-aware information systems (PAIS).

However, process discovery techniques have problems with regard to the quality of produced models. Especially the emerging trend of PAIS to allow for configurable process models whose structure changes along time poses a challenge for their precision. Roughly speaking, process discovery consolidates all the different process instances into a single model which produces a coarse view of the underlying process.

Trace clustering techniques act as a preprocessing step for process mining [START_REF] De Medeiros | Process mining based on clustering: A quest for precision[END_REF][START_REF] Greco | Discovering expressive process models by clustering log traces[END_REF][START_REF] Song | Trace clustering in process mining[END_REF], thereby allowing for a fine-grained set of models. The idea is to group traces according to different characteristics and, subsequently, mine a particular set of clusters. While clustering allows for the selective reconstruction of traces, it still fails to mine the complete "history" (i.e. evolution provenance) of a business processes, identifying their diverse "tenancies" and how they differ.

This paper presents an approach for time-oriented log-clustering that is able to directly reflect the dynamics of a process's structure. The goal is to cluster the cases belonging to one process structure, while different clusters mean that the process structure varies. The variation happens, e.g., when activities are added to (or deleted from) the process model or when the order of activities is changed. Thinking of process logs as sequential records of triggered activities, these variations are reflected in the log as modifications on the "distance" (i.e. number of entries) between pairs of activities. For instance, if an activity C is inserted between the activities A and B, then the distance between them increments by 1. Our approach clusters traces according to the time point where process variants have been introduced. In doing so, we obtain a chronological ordering of process tenancies which allows an auditor to appreciate the evolution of the original process. Fig. 1 depicts our approach consisting of two steps. Firstly, the distance between the activities is measured. Secondly, the traces with similar "distance" behavior are clustered, so that process discovery techniques can be applied. Identified clusters can then serve as input for arbitrary discovery algorithms to construct process models for further analysis, e.g. [START_REF] Accorsi | Auditing workflow executions against dataflow policies[END_REF][START_REF] Accorsi | Strong non-leak guarantees for workflow models[END_REF].

Altogether, this paper provides the following contributions:

-It introduces the "activity distance" as a basis for trace clustering (Sec. 2).

-It provides a clustering method and the corresponding algorithms (Sec. 3).

-It reports on tests employing the approach and discusses the results (Sec. 4).

The overall goal is to devise techniques powerful and scalable enough to cope with industry-size data. The current implementation of the technique is a standalone application. In future, the technique is going to be added to ProM [START_REF] Van Dongen | The ProM framework: A new era in process mining tool support[END_REF] and be part of the Security Workflow Analysis Toolkit (SWAT) [START_REF] Accorsi | SWAT: A security workflow toolkit for reliably secure process-aware information systems[END_REF], thereby making it possible for people to experiment with it.

Extracting Activity Distances

This section introduces the shape of logs taken into account, introduces the concept of "distance", and defines algorithms to extract the distances.

Logs and Distances

We assume that log entries have a timestamp and are chronologically ordered. Fig. 2 shows a workflow as a Petri net with a corresponding log. Adding the

Trace Activities 1 A B C D 2 A C B D 3 A C B D 4 A B C D 5 A B C F D 6 A E F B D 7
A B E F D Fig. 2. Workflow net and corresponding log.

dashed edges leads to another version of this workflow with the two additional activities E and F . Traces (also called cases) related to the new workflow structure appear in the log below the dashed line. Petri nets are often used as a meta-model to describe workflow models. They consist of transitions (rectangles) that stand for workflow activities and places (circles) that can contain tokens used to model the control flow. The execution of activities is modeled in terms of "firing" transitions. Transitions fire if they are "enabled" which means that there is at least one token in each input place. Upon firing, they take one token from each input place and put one token in each output place. The net in Fig. 2 contains a single enabled transition which is A. See [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF] for details on Petri nets. Process logs and traces are defined as follows:

Definition 1. Let A be a set of activities of a process. σ ∈ A * is a log trace and L = {σ 1 , ..., σ n } ∈ P(A * ) is a process log. The order of traces is given by the starting time of the corresponding instance and reflected on the indexes σ i .

Loops in process models can cause activity names to occur several times within the same trace. For the sake of simplicity, we do not consider loops. The distance between any two process activities within a trace is defined as the number of intermediate activities. Considering the first trace of the log in Fig. 2, the distance between A and D is 2. Formally distance is defined as follows: Definition 2. Let σ = {a 1 , ..., a n } be a trace containing activities a i . The distance between any two subsequent trace-activities a i , a j ∈ σ, j>i is defined as d σ (a i , a j ) := j -i -1.

If two activities happen sequentially within a process, their distance remains constant over time, otherwise the distance varies in fixed boundaries conditioned by a minimum and maximum distance. Consider the activity pair (A, D) in Fig. 2: d(A,D Structural changes in the process cause interval variations for activity-pair distances. Fig. 3 shows the distance progress for the activity pair (B, D) in Fig. 2. Within the first four traces the distance remains inside the interval [0, 1], but with trace 5 this interval is enlarged to [0, 2]. Depending on the number

Trace Activities Distances (A,B) (A,C) (A,D), (B,C) (B,D) (C,B) (C,D) 1 A B C D 0 1 2 0 1 - 0 2 A C B D 1 0 2 - 0 0 1 3 A C B D 1 0 2 - 0 0 1 4 A B C D 0 1 2 0 1 - 0 intervals [0;1] [0;1] 2 0 1 0 [0;1]
Fig. 4. Distance matrix for the upper part of the log in Fig. 2.

and position of inserted or removed workflow activities and links between them, distance intervals are enlarged, reduced or moved (same value range, but different starting point, i.e. [START_REF] Accorsi | On the exploitation of process mining for security audits: The conformance checking case[END_REF][START_REF] Accorsi | Strong non-leak guarantees for workflow models[END_REF] → [START_REF] Accorsi | Auditing workflow executions against dataflow policies[END_REF][START_REF] Accorsi | SWAT: A security workflow toolkit for reliably secure process-aware information systems[END_REF]).

Extracting Activity Distances

Algorithm 1 constructs a distance matrix containing distances of activity-pairs as a preprocessing step for the clustering procedure presented in Sec. 3. For every pair of subsequent activities, this matrix contains their distance within every trace of the log. Fig. 4 shows the distance matrix for the traces 1-4 in Fig. 2. Inserted "null" values (denoted -) stand for the fact that not all the traces contain all possible activitiy-pairs. This ensures that the distance lists have equal sizes, which is required by the clustering algorithm. Alg. 1 shows how the distance matrix is built.

Algorithm 1 Build distance matrix procedure BuildDistanceMatrix(workflow log L = {σ1, σ2, ...}) for all k = 1, |L| do for i = 1, |σ k | -1 do for j = i, |σ k | do D σ k [i],σ k [j] [k] ← (j -i -1
) end for end for insert null for all other activity-pairs. end for end procedure

Clustering Log Traces

Our trace clustering approach is interactive and consists of two phases. The first phase determines the cluster cuts for every observed activity pair (a , a ), i.e. the time-points (trace numbers) at which distance interval changes of (a , a ) suggest to end one cluster and to begin a new one. The second phase merges these individual results by counting the number of activity pairs at time point i that would cut the log at that position. As a result, one can browse through a chart showing these counts and, starting with a rather low window size, check how changing this parameter affects the accumulated cluster cuts.

Determining Cluster Cuts

Sequentially processing traces according to their timestamp (in this case, trace index), the clustering algorithm uses samples to determine the typical workflow behavior in terms of boundaries for the minimum and maximum observed value of activity distances. Such a behavior is determined on the basis of a parameter w (window size) that defines the minimum number of traces used as "training" data (sample size) and the minimum number of traces grouped as a cluster. Note that such a step is required since "change" always relates to typical behavior that has to be defined or measured first. The initial sample contains the first w traces of the log. As long as following traces show typical behavior, they are clustered together, otherwise a new sample of size w is created and used as a basis to determine the "new" typical behavior. The following defines these notions:

Definition 4. Let W s,t = {σ s , ..., σ t } ⊆ L be a sample of a log L = {σ 1 , ..., σ n } with size |W s,t | ≥ w.
The minimum and maximum distances of any two activities a , a within W are defined as min a ,a (W s,t ) := min(d σs (a , a ), ..., d σt (a , a )) and max a ,a (W s,t ) := max(d σs (a , a ), ..., d σt (a , a )). The corresponding distance interval is defined as [min a ,a (W s,t ); max a ,a (W s,t )]. The projection of a distance list on a sample is defined as: D a ,a |W s,t := {d σs(a ,a ) , ..., d σt(a ,a ) } ⊆ D a ,a . Definition 5. The support of a distance γ between (a , a ) within a window W is defined as: supp a ,a (W s,t , γ) Considering a sample W s,i-1 that holds all traces accumulated so far, for every (a , a ) of the next trace σ i it is checked if the actual distance value of (a , a ) changes the corresponding distance interval in D a ,a |W s,i-1 . To distinguish between momentary and persistent changes, the clustering method uses a w-size lookahead W i,i+w-1 . Fig 5 shows the possible cases of distance interval changes. In detail there are four different types of interval changes that introduce new clusters:

:= |{d σ (a , a ) ∈ W | d σ (a , a ) = γ}|.
1. (C1) Interval border outrun. The actual distance of (a , a ) outruns its typical distance interval within the sample (cases in Group 1 in Fig. 5).

To check the persistency of this change, the support of the new distance d σi (a , a ) within the lookahead is checked, using a threshold τ . case condition:

d σi (a , a ) > max(W s,i-1 ) ∨ d σi (a , a ) < min(W s,i-1 ). persistency condition: supp a ,a (W i,i+w-1 , τ ) ≥ τ .
2. (C2) Smaller interval. The actual distance of (a , a ) remains inside the typical interval but persistently reduces the size of the corresponding distance interval (cases in Group 2 in Fig. 5). case condition: d σi (a , a ) ≥ min a ,a (W s,i-1 ) ∧d σi (a , a ) ≤ max a ,a (W s,i-1 ) persistency condition: (min a ,a (W i,i+w-1 ) > min a ,a (W s,i-1 ) ∧ max a ,a (W i,i+w-1 ) ≤ max a ,a (W s,i-1 ))∨ (max a ,a (W i,i+w-1 ) < max a ,a (W s,i-1 ) ∧ min a ,a (W i,i+w-1 ) ≥ min a ,a (W s,i-1 )) 3. (C3) Distance observations from here. While there are no distance observations for (a , a ) within W s,i-1 , the actual trace σ i provides a distance value (case j in Group 4 in Fig. 5). case condition: obs(D a ,a |W s,i-1 ) = 0 ∧ d σi (a , a ) = null 4. (C4) No distance observations from here. While there were distance observations for (a , a ) in W s,i-1 , the actual trace σ i contains a phase where no distance values for (a , a ) are observed (Case k in Group 4 in Fig. 5). case condition: obs(D a ,a |W s,i-1 ) = 0 ∧ obs(D a ,a |W i,i+w-1 ) = 0

As long as the distances of observed traces do not introduce new distance intervals, they are put in the same cluster. Once a new interval is detected, the typical behavior is calculated again by choosing a new sample on the basis of the next w traces. This approach allows the identification of modifications and the time point from which they hold, thereby allowing time-based clustering. If distance values were observed both for (a , a ) and (a , a ) within the actual cluster W s,i-1 , the activities a and a are likely to be in parallel. Since there typically are lots of interval changes within the same process model for parallel activities, distance interval changes for such activity pairs are not considered as indicators for workflow changes.

Consolidating Cluster Cuts

After determining the cluster cuts for every observed activity pair individually, the suggested cut positions are combined by counting the number of activity pairs for every time point (trace number) that have a cluster cut at this position and visualized as cluster cut graphs. With the help of a prototypical implementation it is possible to generate such graphs for different window sizes on the fly which gives auditors the chance to identify promising log regions for change point detection in an interactive and intuitive manner.

Besides high peaks -which clearly indicate a workflow change -, regions with an accumulation of smaller peaks are interesting, too. Not in every case a process change affects a large number of activity pairs at once, but rather progressively over a set of traces. For the same reason, peaks or accumulations occur slightly shifted with respect to the actual changing point, especially in case of minor process changes and when "old" traces are still executable within the new model.

Besides the peaks indicating structural process changes, there may be other smaller peaks. They occur if within the same model a set of paths is preferred Fig. 6. Combined cluster cuts for an example log of the nets in Fig. 2.

for a while and can be interpreted as "intra-model changes". Depending on the chosen window size and structure of considered workflow models the number of peaks strongly varies. The smaller the window size, the more changes are detected. Considering a smaller number of traces limits the typical behavior which causes the probability of observing unseen/unknown behavior to grow. An interesting characteristic of cluster cut graphs is, that in most cases the peaks for "real" changes seem to be more stable with varying window sizes.

Fig. 6 shows the resulting graph after applying Algorithm 2 to a log containing 30 randomly generated traces for the first net followed by 30 traces of the second net in Fig. 2. Using a window size of 11, the cluster cut graph shows some high peaks around trace 30 which means that a high number of activity pairs experienced "change" in this region. This is in fact the region where the underlying model for the generated log traces changed. From the point on where the lookahead contains less traces than the window size, more changes are detected because the persistency of changes is based on a smaller number of traces than it is the case before. Simply combining the last w traces to one cluster or unifying them with the last detected cluster is a rather strict approach. We decided keep the cut information and mark the "critical region" (gray area within the graph) to give auditors the chance to decide on its usefulness. Alg. 2 provides the method to determine cluster cuts for particular activity pairs.

Testing the Clustering Approach

The clustering method is tested using the non-trivial process shown in Fig. 7. It contains 15 different activities that are composed using parallel and conditional branches. Its size and structural complexity is not exceeded by the vast majority of industrial processes. In order to show the detection rate of workflow changes, a set of process variants was generated, based on the change patterns by Weber et al. [START_REF] Weber | Identifying and evaluating change patterns and change support features in process-aware information systems[END_REF]. Using process simulation techniques, test logs containing traces for each variant are generated, serving as input for the change point detection method. Algorithm 2 Determine cluster cuts for specific activity pair Instead of focusing on simple operations (add/remove activities), we consider more complex operations to allow for a more intuitive understanding and interpretation of the change types that can be successfully detected. See [START_REF] Weber | Identifying and evaluating change patterns and change support features in process-aware information systems[END_REF] Successively applying these patterns to the original process M 0 in Fig. 7 results in a set of 13 models M 0 , ..., M 12 . Each model M i was created by applying pattern (Ci) to the previous model M i-1 . Due to space limitations the process variants are not explicitly depicted in this paper, but Fig. 8 exemplary shows how some of the variants are formed. All process variants have been modeled with PNML and simulated with a proprietary simulation module of SWAT [START_REF] Accorsi | SWAT: A security workflow toolkit for reliably secure process-aware information systems[END_REF]. In total, we create a process log with 13.000 traces. The flog in Fig. 9 contains different numbers of traces for different process variants successively.

To evaluate the effectiveness of our clustering method we first check if it successfully detects the change points between the different process variants. Fig. 10 shows the resulting cluster cut graph for the log in Fig. 9 in the clusteringapplication prototype. With the chosen window sizes, most of the change points are clearly identifiable by considering the highest peaks. It should be mentioned that using other window sizes does not significantly change the shape of the resulting graphs but simply results in a higher or lower number of additional peaks around change points.

However there are peaks which are not caused by model changes and/or cannot be directly obtained by graph analysis because they do not produce noticeable peaks, e.g. the model M 10 and M 11 . Taking a deeper look at this specific change reveals that the only difference between the two models is that an execution condition is added to a mandatory process fragment of M 10 which additionally allows traces where the fragment does not occur. In contrast to the removal of a process fragment which is obtainable by the absence of distance observations for affected activity pairs in following traces, in this case the detection fails because the fragment may or may not occur and so there are no activity pairs whose distance is persistently altered by the change.

Another change that is not clearly identifiable is from M 4 to M 5 (see Fig. 8(c)) by moving the last activity (H) out of a conditional branch the corresponding join. Since changes between parallel activity pairs are omitted by the clustering method and only 2 sequential activities are affected by this change (namely E and F) the low peak at trace 4.800 is hardly surprising. The more locally constrained changes are and the less activities are affected, the harder their detection. This also applies to the change from M 5 to M 6 which is caused by swapping the nearby activities N and P. Although in this case the change is still identifiable within the graph in Fig. 10. Still, the cluster cut graphs provide valuable information for the identification of process changes which shows the appropriateness of monitoring activity pair distances for this purpose.

Change Localization. Besides the detection of change points, another goal of time-based trace clustering is change localization [START_REF] Bose | Trace alignment in process mining: Opportunities for process diagnostics[END_REF]. For this, the regions of change in the process models are of interest. In our approach, the region of change is obtained by considering the corresponding activity pairs for the peaks in the cluster cut graph. Zooming in on trace 600 in Fig. 10, e.g., reveals two high peaks, one in trace 601 with 18 related activity and another in trace Table 1. Activity pairs for the peaks around trace 600 in Fig. 10. 603 with 11 related pairs. The resultant set of activity pairs for these two peaks is depicted in Table 1 and shows that most activity pairs refer to the activities {P, N, O}. Considering the change from Model M 0 to model M 1 in Fig. 8(a), this set contains the newly inserted activity P being the most referenced activity (it is contained in 15 out of 29 activity pairs), plus its successors.

Discussion

While our experiments show that time-based clustering is feasible for different types of changes, some general observations wrt the window-based apply.

There are various parameters that influence change point detection; the window size seems to be the most important one. Depending on this parameter, changes may become undiscoverable. This can either happen when the window size is too small which results in a higher number of peaks and "real" changes become indistinguishable from momentary changes (diffusion), or when changes are masked due to the inability of detecting clusters whose sizes are smaller than the window size itself (this is an inherent disadvantage of window-basing). Instead of relying on an optimal window size, our approach solves this problem by allowing users to identify changes by analyzing the variance of cluster cut graphs with respect to different window sizes. To the best of our knowledge, this is the first approach allowing such kind of interactive change point detection.

Besides the window size, the variance of cluster sizes also plays a role. If the number of traces relating to different process variants significantly differ, there is no window size that can uncover all change points without masking or diffusing others. In case of similar trace numbers, the precision of change point detection is proportional to the average number of traces relating to the process variants. The more traces can be taken into account on determining the typical process behavior, the more precisely the process characteristics can be captured.

Another insight is that the difficulty to to detect changes strongly depends on the number of affected activities. For most patterns, structural characteristics of the original and the resulting process have influence on the ability to detect change points. Due to the observations we did so far, the number of activities that are affected by a change and the structural complexity of the underlying process (degree of parallelity) seem to exert the highest influence. However there are change patterns, that are generally hard to detect independent of these structural characteristics such as (C11).

Related Work

Trace clustering approaches aim to group process traces according to some criteria. One of the first attempts in this area is multi-phase process mining [START_REF] Van Dongen | Multi-phase process mining: Building instance graphs[END_REF][START_REF] Dongen | Multi-phase process mining: Aggregating instance graphs into EPCs and Petri nets[END_REF]. Initially generating a process model for each individual process instance/case, these instance graphs are stepwise aggregated based on their similarity to introduce more general models. Greco et al. [START_REF] Greco | Discovering expressive process models by clustering log traces[END_REF] propose a clustering technique in form of a stepwise refinement of a set of workflow schemas modeling specific usage scenarios. Starting with a single workflow schema describing the behavior of the overall process, in each refinement step the model with the lowest "soundness value" is selected for being refined. While "completeness" measures the covering rate of a model with respect to a process log, "soundness" is able to decide on over-generalization by measuring the percentage of enactments of the mined model that find some correspondence in the log [START_REF] Greco | Discovering expressive process models by clustering log traces[END_REF].

Instead of iteratively checking the appropriateness of mined models to decide on further clustering, some approaches operate at trace level and focus on trace-similarity. Utilizing k-means for clustering, Song et al. [START_REF] Song | Trace clustering in process mining[END_REF] use features to characterize sets of traces. Trace-similarity is measured by distances of featurevectors (i.e. the number of activities of a trace). Bose et al. [START_REF] Bose | Trace alignment in process mining: Opportunities for process diagnostics[END_REF] map the problem of multiple sequence alignment in bioinformatics on the trace-clustering problem to identify groups of similar traces. In [START_REF] Lakshmanan | Detecting changes in a semi-structured business process through spectral graph analysis[END_REF] Lakshmanan et al. utilize spectral graph analysis to compute the difference of cluster-graphs to identify changes. Obtained models reflect different process characteristics but are loosely coupled with each other, hence failing to show the change of process models along time.

Recent mining approaches consider change in workflows [START_REF] Günther | Using process mining to learn from process changes in evolutionary systems[END_REF]. In [START_REF] Lakshmanan | Detecting changes in a semi-structured business process through spectral graph analysis[END_REF] Lakshmanan et al. utilize spectral graph analysis to compute the difference of clustergraphs to identify changes. However by using fixed cluster sizes, this approach is rather imprecise. Workflow dynamics in the sense of context changes can be characterized as concept drift, which is a well-studied paradigm in the data mining area. Bose et al. [START_REF] Bose | Handling concept drift in process mining[END_REF] provide methods to handle concept drift in process mining by showing that workflow changes are indirectly reflected in workflow logs and change point detection is feasible by examining activity relations.

In contrast to [START_REF] Bose | Handling concept drift in process mining[END_REF], our approach does not consider ordering relations (follows/precedes) but variations on the distance of activity pairs within a trace (the number of intermediate activities) as structural property. Sequentially processing traces according to time, traces whose structure differs from the typical trace structure so far are treated as indicators for new clusters. Proceeding this way ensures that a log file is partitioned into chronologically subsequent clusters, whose sizes depend on the frequency of changes in process structure. However, we do not identify the kind of change, but focus on the identification of time points of permanent process changes.

Summary and Further Work

This paper presents a trace clustering approach to support process discovery of configurable, evolving process models. The clustering approach allows users to distinguish between different process variants within a timeframe, thereby visualizing the process evolution. The main insight to cluster entries is the "distance" between activities, i.e. the number of steps between an activity pair. The evaluation shows that the approach is promising. Still, there are several issues that remain to be addressed. The following presents the most important issues:

1. Loop support. The clustering method at this point does not support workflow models containing loops which definitely is its biggest disadvantage as it limits its applicability. We are confident that an enhancement in this direction is straightforward and can be done without negatively influencing the effectiveness of the method. 2. Identification of change patterns. Although our experiments convey an impression of the identifiability of change patterns, a more systematic approach is needed to provide a well-founded basis for their effective detection. 3. Feature set. So far our approach solely relies on the activity pair distance metric, but incorporating additional metrics may enable more precise change point detection. For change patterns like (C11) where the identification of change points is not straightforward, additionally considering the length of log traces of subsequent samples may be useful. 4. Change localization. As mentioned before, the proposed clustering method provides sufficient information for the localization of change within workflow models. Here, automatic mechanisms for the extraction of change regions from a set of affected activity pairs are envisioned.

Fig. 1 .

 1 Fig. 1. Approach overview.

  ) = 2 holds within the first 4 traces, whereas the distance d(B, D) ranges in the interval [0; 1].

Fig. 3 .

 3 Fig. 3. Distance graph of the activity pair (B,D).

Definition 3 .

 3 Let L = {σ 1 , ..., σ n } be a log and A the set of activities in L. A distance matrix M L holds for every a , a ∈ A a distance list D a ,a := [d σ1(a ,a ) , ..., d σn(a ,a ) ]. Distances for a specific index k ∈ [1; n] are represented by D a ,a [k] := d σ k (a ,a ) . The number of observations within a set D a ,a ⊆ D a ,a is defined as: obs(D a ,a ) := |{d σ(a ,a ) ∈ D | d σ(a ,a ) = null}|.

Fig. 5 .

 5 Fig. 5. Possible changes for distance intervals.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Process for generating process variants and trace clustering.

Fig. 9 .

 9 Fig. 9. Log with different trace numbers for each process variant.

Fig. 10 .

 10 Fig. 10. Resulting cluster cut graph for the log in Fig. 9.

  N) (A,O) (A,P) (P,N) (P,O) (C,P) (B,N) (B,O) (B,P) (D,P) (E,N) (E,O) (E,P) (G,P) (F,N) (F,O) (F,P) (H,P) (I,N) (I,O) (I,P) (L,P) (J,N) (J,O) (J,P) (M,P) (K,N) (K,O) (K,P)


Sylvain Durand

Anne-Marie Alt

Daniel Simon
email: daniel.simon@inria.fr

Nicolas Marchand

Energy-aware Feedback Control for a H.264 Video Decoder

Keywords: Feedback scheduling, QoS, Energy-performance trade-off, Fast predictive control, H.264 video decoder

Embedded devices using highly integrated chips must cope with conflicting constraints, while executing computationally demanding applications under limited energy storage. Automatic control and feedback loops appear to be an effective solution to simultaneously accommodate for performance uncertainties due to the tiny scale gates variability, varying and poorly predictable computing demands and limited energy storage constraints. This paper presents the example of an embedded video decoder controlled by several feedback loops to carry out the trade-off between decoding quality and energy consumption, exploiting the frequency and voltage scaling capabilities of the chip. The inner loop controls the Dynamic Voltage and Frequency Scaling (DVFS) through a fast predictive control strategy. The outer loop computes the scheduling set-points needed by the inner loop to process frames decoding. The feedback loops have been implemented on a stock PC and experimental results are provided.

Framework and related works

The upcoming generations of embedded devices are integrating more and more multimedia and telecommunication applications, such as PDAs, mobile phones and tablets, thus requiring increasing on-board computing power. On the other hand, they become even more miniaturised (which means with limited energetic resources) while needing increased autonomy. These constraints are clearly conflicting, therefore technological evolutions are needed to improve their power consumption, computational efficiency and fabrication yield. In this paper, we propose the use of feedback control loops as a possible solution. The approach is applied to an embedded video decoding device whose requirements can be categorised in three main points : a) Energy saving requirements : In current CMOS integrated chips, Dynamic Voltage and Frequency Scaling (DVFS) can be used to efficiently manage the energy consumption of a device. It results in simultaneously managing the frequency and the voltage (note that scaling down the voltage increases signals delays along the paths through electronic gates, thus needing to decrease its clock frequency as well, and inversely [START_REF] Chandrakasan | Minimizing Power Consumption in Digital CMOS Circuits[END_REF], [START_REF] Flautner | An Energy Efficient SoC with Dynamic Voltage Scaling[END_REF], [START_REF] Varma | A Control-Theoretic Approach to Dynamic Voltage Scheduling[END_REF])). In many cases, the only performance requirement is that the tasks meet their deadline. Such cases create opportunities to run the processor at a lower computing level and achieve the same perceived performance while consuming less energy.A closed-loop DVFS approach is hence a good solution for energy saving. Classically, each task is considered independently, running at a constant voltage whose value is set to meet the deadline, and even selecting a small number of voltage levels leads to a drastic energy reduction [START_REF] Ishihara | Voltage Scheduling Problem for Dynamically Variable Voltage Processors[END_REF], Pouwelse et al. (2001)).

b) Process variability requirements : Systems on Chip (SoC) integrate extremely small scale CMOS manufacturing, e.g. silicon foundries currently target 32 nm or even smaller (22 nm) gates. A nasty consequence of this very high integration is the variability in the silicon process : although a circuit is designed to run at a nominal clock frequency, the fabricated chip may vary by far from the expected performance [START_REF] Romanescu | Reducing the Impact of Process Variability with Prefetching and Criticality-Based Resource Allocation[END_REF]). Moreover, some cores may behave differently inside the same chip [START_REF] Fesquet | Controlling Energy and Process Variability in System-on-Chips: Needs for Control Theory[END_REF]). Actually, this phenomenon is one of the leading causes for chip failures and delayed schedules at a sub-micrometric scale.

To take full benefit of the potentially available computing power, hence it is needed that each computing node (or cluster of nodes) can be driven up to its maximal clock frequency. A common solution is the use of a Globally Asynchronous Locally Synchronous (GALS) architecture, e.g. [START_REF] Ferringer | VLSI Implementation of a Fault-Tolerant Distributed Clock Generation[END_REF] : by removing the globally distributed clock, such circuits provide a cost effective solution for large SoC design. In practice, several nodes sharing a common frequency domain are gathered in a cluster, and clusters working at different frequencies are linked via an Asynchronous Network on Chip (ANoC) [START_REF] Thonnart | Design and Implementation of a GALS Adapter for ANoC Based Architectures[END_REF]). A GALS architecture can mitigate the impact of process and temperature variations, because a globally asynchronous system does not require that a global common frequency is dictated by the longest path delay of the whole chip, i.e. the critical path. In this case, the clock in each frequency domain is only determined by the slowest path in its domain. Furthermore, GALS techniques allow each locally synchronous island to be set independently, making DVFS more convenient than with the standard synchronous approach [START_REF] Zakaria | Integrated Asynchronous Regulation for Nanometric Technologies[END_REF]).

c) Quality of Service (QoS) requirements : Highly integrated chips are expected to be used in many computing intensive fields, like in the present case of multimedia applications. Thanks to the important embedded computational power, many functions that were traditionally hardwired can now be implemented in software. This is for example the case for the radio communication receiving system, where components like filters, mixers and codecs can now be implemented with increased flexibility inside the programmable components of a Software Defined Radio (SDR) system. The extra computing power can also be used to decode video streams with high definition quality. However, high computing power has drawbacks in terms of energy consumption, especially for the case of mobile devices with limited embedded energy stored in battery. Consequently, trade-offs between measures of the multimedia application quality, available on-board energy and desired time to battery exhaustion must be managed, and may be translated into a control problem formulation. Trading performance and resources is relevant of QoS problems, which may be viewed as the management of some complex quality measures, assumed to provide an image of the satisfaction of application requirements. Indeed, QoS problem statements have been already used for energy-aware multimedia applications [START_REF] Chiang | Scalable Video Coding of H.264/AVC Video REFERENCES Streaming with QoS-based Active Dropping in 802.16e Networks[END_REF]), most often focusing on networking load and communication management rather than on computing itself. An approach stating video processing under computation power limitations as a QoS problem is reported in [START_REF] Wurst | QoS Control Strategies for High-Quality Video Processing[END_REF]. The QoS is evaluated via end-users perception criteria and enables tuning decoding parameters such as picture quality, deadline misses and quality level switches. Scalable processing is provided using several quality levels for frame decoding, each one associated with a corresponding computing cost.

Interaction between control and computing

Control and real-time computing are used together in embedded control systems since decades. However it has been recognised only quite recently (e.g., [START_REF] Cervin | Feedback-Feedforward Scheduling of Control Tasks[END_REF] and [START_REF] Lu | Feedback Control Real-Time Scheduling: Framework, Modeling and Algorithms[END_REF]) that more integrated co-design approaches between control and computing are likely to enhance both the performance and the robustness of real-time control systems. In particular it has been shown that digital objects, such as real-time schedulers and cyclic control tasks, can be efficiently managed through feedback loops. Therefore, they inherit the robustness and adaptivity properties brought by closed-loop control. Moreover, digital processes can often be modelled through simple dynamics, e.g. using fluid modelling, therefore leading to simple controllers with very small execution overheads [START_REF] Hellerstein | Feedback Control of Computing Systems[END_REF], [START_REF] Malrait | Experience with CONSER: A System for Server Control through Fluid Modeling[END_REF]). When applied to video codecs, feedback control has been mainly used for bit-rate management at the encoder side to accommodate the bandwidth of the communication link between the encoder and the decoder. For example, [START_REF] Sun | A Robust and Adaptive Rate Control Algorithm for Object-Based Video Coding[END_REF] combines prediction and PID control to simultaneously handle buffer occupancy and picture quality for an MPEG-4 video encoder. In other works, e.g. as reported in [START_REF] Brites | Evaluating a feedback channel based transform domain Wyner-Ziv video codec[END_REF], feedback channels are exploited in the coding process itself to enhance the compression rate and speed. Adaptive streaming can be post-processed on-the-fly, e.g. using a PI bit-rate controller in the server side as in De [START_REF] De Cicco | Feedback Control for Adaptive Live Video Streaming[END_REF] or a Markov Decision Process (MDP) based algorithm as in [START_REF] Xiang | Adaptive scalable video streaming in wireless networks[END_REF]. On the decoder side, using feedback is mainly motivated by energy consumption considerations, therefore considering the voltage and working frequency as control variables. For example, in Pouwelse et al. (2001) a feedforward/feedback heuristics on-the-fly selects a H.263 decoder clock frequency, based on frame length modelling. Following the ideas of previously cited works for the control of web servers [START_REF] Lu | Feedback Control Real-Time Scheduling: Framework, Modeling and Algorithms[END_REF]), a PI controller is used in [START_REF] Lu | Reducing multimedia decode power using feedback control[END_REF] to control a MPEG decoder's speed and storage buffers occupancy to reduce the power consumption while preserving some realtime guarantees (but only simulation results are provided). Finally, in the already cited [START_REF] Wurst | QoS Control Strategies for High-Quality Video Processing[END_REF] reference, the QoS specification of a MPEG-2 decoder is implemented on a single fixed frequency CPU, using different quality levels as control variables driven by a MDP based controller.

Guidelines

The work presented here uses two low-levels control loops. The first one is based on fast Model Predictive Control and controls the chip's DVFS and computing speed. The second one controls the scheduling of the video frames through a simple Proportional controller. This control architecture is expected to be supplemented by a high-level QoS loop, whose design is out of the scope of the present paper. Anyway, its framework is required for designing the two other loops.

The proposed control architecture is able to manage several clusters. However, even when considering a single CPU with constant processing power, the approach shows a very effective and flexible decoding adaptation capability. Such a closed-loop control scheme follows several steps. Control design first needs a definition of the control objectives and an analysis and modelling of the process to be controlled. Basically, control uses an error signal between the desired and the measured (or estimated) state or output of the system. The output signals, which are significant for control purpose, must be identified and the corresponding sensors implemented. Then various control algorithms can be used to cyclically compute commands to be applied to the process via actuators, which must also be identified and implemented.

Using a GALS approach offers an easy integration of different functional units. Notably, it allows to slow down some parts of the circuit for better energy savings since each part can easily have its own independent clock frequency and voltage. Hence, such an architecture appears as naturally enabling distributed power management systems as well as local DVFS. This is even better not only in terms of power and performance, but also in terms of accommodation against variability [START_REF] Marculescu | Energy Awareness and Uncertainty in Microarchitecture-Level Design[END_REF]). As a result, a feedback control loop can be used to adapt the voltage/frequency of each part in order to respect some real-time constraints of the application and the allocated energy budget. Relying on this low-level layer, another control loop is able to lighten the computing load of functionals unit by dealing with the QoS at the application level, coping with the limitation of processing power and/or channel of communication and with some constraints in energy consumption. The setup to control the embedded video decoding mechanism of our case study is based on such an architecture.

The paper is organised as follows. In section 2, the closed-loop multi-layer architecture for video decoding under computing resource and energy consumption constraints is sketched. The different control loops are then detailed in sections 3 for the DVFS layer and 4 for the frames rate controller. Some experimental results are finally given in section 5 using a short movie decoding as a support example, and a discussion concludes the paper.

Feedback scheduling setup for video decoding

Control design needs sensors and actuators to respectively monitor and drive the controlled process. In the particular case of feedback control of computing systems, sensors are provided by software probes used to build on-line indicators carrying out the processing activity. Actuators are provided by function calls, parameters tuning, or processing interruption/resume under control of an Operating System (OS). As the bitstream decoding quality is the object of control, models of the decoder quality (i.e. the control related model) as a function of various execution parameters (desired quality levels) are estimated from experiments. These models are further used to formalise the control objectives, e.g. using a QoS formulation. Besides data coming from the reported experiments, many ideas and assumptions are inspired by the work described in [START_REF] Wurst | QoS Control Strategies for High-Quality Video Processing[END_REF]. Let first briefly introduce how works the decoding mechanism of the present study case before detailing the feedback multi-layer architecture.

Features of H.264/SVC

H.264 is an international video coding standard, where a video sequence is made of three types of pictures : I pictures are reference pictures which are encoded independently of any other, P pictures are encoded using the previously encoded I picture, and B pictures are encoded using both the I and P previously encoded pictures. The order in which pictures are displayed is different from the order of the pictures encoding/decoding, hence there exist a systematic delay between decoding and display. For instance, if the display order is IBBBPBBBI then the encoding/decoding order will be IPBBBIBBB. The IPB pattern is defined at coding time and is invariant along all the video stream.

On the other hand, the Scalable Video Coding extension (SVC) has been defined to provide scalability capabilities in H.264 [START_REF] Schwarz | Overview of the Scalable Video Coding Extension of the H.264/AVC Standard[END_REF]), this is expected to provide the actuators needed for QoS control. Three types of scalability are allowed : i) Spatial scalability enables to encode a video with several resolutions (i.e. number of pixels in a picture). ii) Temporal scalability enables to encode all or a part of the frames of the original video with different rates. iii) Quality scalability allows to encode the frames with several quantization steps which selectively cancels some information from the original video : its effect can be compared to a low-pass filter.

They can be combined to encode/decode a video stream. It is stated that the decoding process necessarily flows from lower to higher quality layers and, obviously, all the quality layers needed by the decoder must have been previously encoded by the decoder.

Control architecture

The various control objectives and timing scales lead to define a hierarchy of three control loops to manage the decoding quality. They are depicted in Figure 1.

i) At high level, the QoS controller manages the application performance according to the

frequency/voltage O p e r a t i n g s y s t e m s i d e

Layers

Computing

Speed energy monitoring

S i l i c o n s i d e

ReqCycles end of task max speed available resources and end-user's requirements. Ideally, the goal of this controller is to maximise the quality of the displayed video stream under constraint of energy consumption. Hence, according to an available computing budget, the video must be decoded with the lower possible quantization step, higher resolution and maximal rate. The allowed computing budget itself depends on the available on-board energy storage and desired operating life. This high-level controller works with long term objectives with a time scale slow compared with the time scale of frame processing. ii) At a lower level, decoding frames has basic deadlines related to the video display rate, typically 40 ms for frames displayed at standard television rate. However, the decoding computing load is subject to fluctuations due to the varying content-dependent computation duty of the successive frames. Therefore an on-line adaptation of the decoding parameters (quality layers) can be associated with the frequency scaling capabilities of the cluster to meet the requested video rate. The frame controller works at the picture stream time scale and tightly cooperates with the speed controller integrated in each cluster. iii) The computing speed controller manages the energy-performance trade-off in each cluster. It is integrated in the cluster's silicon, together with the voltage and frequency controllers which drive the power supply variables.

Controller

Quality of Service

Whereas the design of the QoS control loop is only sketched in this paper, the two lower levels controllers are detailed from bottom to top in the following sections.

Control of the energy-performance trade-off

The computing speed controller aims at minimising the energy consumption while ensuring the frames computational inside given deadlines. This is possible by scaling the supply power taking into account some time constraints. In the present case, a closed-loop controller monitors the activity of the processor (its computational speed, shortly denoted speed in the sequel, e.g. in number of instructions per second) and adapts its voltage and frequency levels (afterwards denoted V level and f level respectively) with respect to a computational load. The suggested control strategy (see [START_REF] Durand | Fully Discrete Control Scheme of the Energy-Performance Tradeoff in Embedded Electronic Devices[END_REF] for further details) consists in dynamically calculating an energy-efficient speed set-point that the system will have to track in order to satisfy the control objective. This set-point is based on the number of instructions Ω i and the deadline ∆ i (both provided by the frame controller), to process task execution T i which decodes video frame i. Λ i denotes the laxity of T i , i.e the remaining time to achieve the deadline of T i .

We consider here a voltage scalable device with two possible voltage values V high and V low . Let ω max and ω max respectively denote the maximal computational speeds when the system is running at V high and V low voltage. It follows that the high voltage level is necessary as soon as the average speed set-point of a task is higher than ω max in order to avoid missing a given deadline. An intuitive method consists in building the average speed set-point of each task (that is the ratio Ω i /∆ i ) in such a way that the number of instructions to do has been achieved at the end of the task (as depicted in Figure 2(a)). However, this method needs an infinite number of voltage and/or frequency levels (which is not possible in practice) and, anyway, is not energy-efficient since a whole task execution would be computed with the penalising high supply voltage, as highlighted in Figure 2(a) by t Vhigh for task execution T 2 .

Nevertheless, a solution consists in splitting the task executions into two parts as represented in Figure 2(b). Firstly, the chip begins to run at high voltage (if required) with the maximal available frequency in order to achieve the maximal possible speed ω max , hence running faster than the average as for T 2 from time t 2 to k. Then, the execution finishes at low voltage at a speed lower than ω max which, consequently, reduces the energy consumption. We propose to use only one possible frequency F high when running at V high whereas several frequency levels are possible at V low (F low1 and F low2 in the present study case with F low1 > F low2 ). The degree of freedom on the frequency allows to approach as much as possible the deadline. A key point in the control strategy is that the switching time to go from V high to V low has to be suitably calculated to ensure a good computational performance. However, k is not a priori known and therefore a predictive control law is used to dynamically calculate the switching time.

The presence of deadlines and input constraints to compute repetitive tasks naturally leads to a predictive control specification. Predictive control consists in finding a certain control profile over some time horizon to achieve a given control objective. The predictive issue can be formulated as a constrained optimisation problem : for each image i to decode, find the computational speed set-point which minimises the high voltage running time t Vhigh while guaranteeing that the executed instruction number fits the number of instructions to do, that is min t Vhigh s.t.

∆i(t) ω(t) dt = Ω i (1)
where ωdt corresponds to the executed number of instructions for the current image. In this particular case, the horizon is contractive : this means that the time to achieve the objective decreases with the laxity, hence the horizon is updated for each image to decode. However, this optimal criteria is associated to high computational cost, which is not acceptable in embedded systems with limited resources. The strategy adopted here is called fast predictive control and consists in taking advantage of the structure of the dynamical system to fasten the finding of the control profile [START_REF] Alamir | Stabilization of Nonlinear Systems Using Receding-Horizon Control Schemes: A Parametrized Approach for Fast Systems[END_REF]). Indeed, the closed-loop solution yields an easier and faster algorithm since only two parameters need to be known, i) the computational load to be processed Ω i and ii) the remaining time to achieve it Λ i .

The speed required to meet the deadline (denoted the predicted speed υ) is dynamically calculated at each sampling instant k (where the sampling interval is much smaller than the decoding duration of an image)

Ω(t k ) = Ω(t k-1 ) + T s ω(t k ) υ(t k+1 ) = Ω i -Ω(t k ) Λ i (t k ) (2)
average computational speed setpoint where Ω is the sum of the computational speed ω over past sampling instants, T s is the sampling period and t k , t k+1 and t k-1 are the current, next and previous sampling times respectively. For sake of simplicity, Ω(•), ω(•) and υ(•) are not indexed by the task execution number i. Note that here the processing load needed Ω i for the task execution number i is assumed constant during T i decoding, nevertheless it might be updated at any time during the execution of T i by the frame controller for the case where decoding milestones can be identified and used on the fly. The energy-efficient speed set-point is then directly deduced from the value of the predicted speed and so are the voltage and frequency levels. Indeed, the system has to run at V high and F high when the required speed is higher than the maximal speed at low voltage, otherwise the speed at low voltage is fast enough to finish to decode the image on time. Finally, the control decisions are

t V high voltage time Ω 2 ∆ 2 Ω 1 ∆ 1 Ω 3 ∆ 3 T 3 T 2 T 1 ω max ω max t 2 t 3 time t 1 V high V low t 2 t 3 t 1 (a) Intuitive average speed set-point. energy-efficient computational speed setpoint time voltage V high V low time t V high t 2 t 3 Ω 2 ∆ 2 Ω 1 ∆ 1 Ω 3 ∆ 3 T 3 T 2 T 1 ω max ω max t 2 t 3 k t 1 t 1 k (b) Energy-efficient speed set-point.
V level (t k+1 ) = V high f level (t k+1 ) = F high if υ(t k+1 ) > ω max V level (t k+1 ) = V low f level (t k+1 ) = F lown otherwise
A frequency control strategy is needed at low voltage to determine n, but the principle remains the same. Also, a last control decision is possible "deactivating" the clock of the circuit. This is called the clock-gating principle [START_REF] Kuzmicz | Static Power Consumption in Nano-CMOS Circuits : Physics and Modelling[END_REF]). In this case, the processor runs with the low voltage and a null frequency, which can be cost-effective when an image is decoded before its deadline. Furthermore, in order to be robust to manufacturing uncertainties, the maximal speeds ω max and ω max which are required in the control decision are estimated using a weighted average of the measured speed, details can be found in [START_REF] Durand | Fully Discrete Control Scheme of the Energy-Performance Tradeoff in Embedded Electronic Devices[END_REF].

The processing time t Vhigh at the highest voltage V high is minimum since the decoding of an image always starts with the penalising high voltage level (by construction of the predictive control law), ensuring that the low level will not be applied while the remaining computational load is large enough (higher than the maximum possible speed at V low ). The result is therefore structurally optimal. Furthermore, even if the voltage/frequency levels discretely vary, the setpoint to track is always higher (or equal) than required by construction.

The stability of the control scheme follows the Lyapunov approach stating that, if an energy function of the system continuously decreases near an equilibrium point, then this point is a stable equilibrium for the system. Here we consider the decrease of the amount of instructions to be processed for T i as x(t k ) = Ω i -Ω(t k ). A classical Lyapunov function candidate would be of the form V = x T x. V is continuously decreasing as the processor's speed can be only positive, therefore ensuring the decoding control system stability.

Frame control

The second control loop feeds the computing speed controller with estimations of the amount of computations to be performed (i.e. Ω i ) within an associated deadline (i.e. ∆ i ) for each image i to decode, as previously explained in section 3. This is developed in the sequel whereas a damping buffer is firstly introduced to store unprocessed data in case of missed deadlines.

Damping buffer provisioning

Typically, deadlines in video decoding are associated with the video rate, e.g. 40 ms are allocated to fully decode and display one image. However, even if the display video rate must be respected as far as possible, there are no strong synchronous constraints between the video source capture, encoding, decoding and display : latencies equivalent to several frames are allowed, hence there is room for scheduling flexibility at decoding time. Recall that the displayed order is different than the decoding order due to dependencies between images of different types I, P and B, as explained in subsection 2.1. Therefore, the displayed flow is inevitably delayed w.r.t. the incoming bitstream. Following the ideas in [START_REF] Wurst | QoS Control Strategies for High-Quality Video Processing[END_REF], an additional buffer is hence added to the frame decoding queue in such a way that decoding is performed several frames ahead of display. This added buffer is used to give space and accommodate for the vary-ing computing loads between frames. Measurements of decoding execution times were made to evaluate the profile and amplitude of computing load variations along a movie. Execution times measured from a 1000-frame long movie have been sorted according to the frame type (I, P or B) in Figure 3, where the bitstream has a unique layer with 624 × 352 pixel resolution and quantization step Q p = 28 (note that larger is the quantization step, from 0 to 51, lower is the quality). This video sequence contains a mix of quiet and action plans. It can be observed, especially for the reference I frames, that the decoding times are almost constants for quite long intervals, with abrupt changes between flat areas, and isolated high values. The observation of constant intervals enables to estimate the number of cycles with sufficient accuracy. The maximal value for these isolated peaks suggests that a three-frame deep control buffer would be able to damp most of the computing load variations.

Deadline and computing load control

The main goal of the frame controller is to provide the underlying computing speed controller with estimates of the number of cycles Ωi+1 to be processed for the next frame within a requested deadline ∆ ri+1 . According to [START_REF] Wurst | QoS Control Strategies for High-Quality Video Processing[END_REF] and to the measures plotted in Figure 3, an estimate of Ωi+1 can be often taken as the last Ω i reported by the computing speed controller, or by filtered values of the last executions, such as

Ωi+1 = α Ωi-1 + (1 -α)Ω i (3)
where 0 ≤ α ≤ 1 is a weight. Furthermore, considering a fixed ideal schedule {..., τ i-1 , τ i , τ i+1 , ...}, e.g. with equidistant intervals of 40 ms, a first basic feedback loop is aimed to regulate the requested deadlines ∆ ri to their ideal value τ i . However, due to the rough prediction of the computing load Ωi , the actual (measured) deadline deviates from its requested value, which yields ∆ i = ∆ ri + δ i . Assuming that the computing load is almost constant, the computing overshoot can then be driven to 0 if δ i+1 = (1 -β)δ i with 0 < β ≤ 1, leading to the elementary deadline controller

∆ i+1 = τ i+1 + (1 -β)δ i (4)
The resulting control loop may accommodate for short term variations of the computing load for each frame. From a stability point of view, system (4) has no dynamics and (for a constant load Ω) the successive values of δ results from a numerical suite which converges to 0 for 0 < β < 2 (in practice β ≤ 1 is chosen to avoid overshoots) : larger is β, faster is the decay of the deadline deviations δ, and larger is the noise. The capabilities of this controller can be exhausted in case of several successive peak loads able to overflow the three-frame ahead buffer. In that case, only the I frames will be fully decoded up-to the requested quality level, while the depending P and B frame decoding can be truncated up-to recovering enough buffer space. Thanks to the signals that are fed back by the decoder and by the computing speed controller, several control decisions can be considered, sorted by their expected increasing impact on the displayed quality : i) Truncation of the decoding process at a quality layer lower than the set-point can be done at any point for B and P frames. ii) A comparison between a reference decoding timing pattern and actual tags inserted in the decoder may help to anticipate overloads and abort useless steps rather than awaiting a deadline miss. iii) In case of accumulated overload peaks running beyond nominal control actions, skipping or aborting a frame decoding may be taken as an emergency action, allowing to reset the decoding stack. This action must be as far as possible avoided especially for I frames.

Experimental results

In this last section, we implement and test in practice our proposal for decoding a short video.

Implementation

A prototype of a H.264 decoding controller has been developed under the Linux operating system. It runs on a stock Linux kernel tuned for enhancing its real-time capabilities, i.e. compiled with the tick-less feature, high resolution timers and preemptive kernel options. In particular, these options ensure low latencies during task switching and allow for the very precise measurements of execution times (down to the hardware resolution) which are necessary to feed the feedback loops.

The tests have been executed on a standard Dell E6400 laptop, using a DuoCore2 processor. The test-bed uses the Symmetric Multi-Processing (SMP) capability of the kernel to allocate specified parts of the software to dedicated CPUs, e.g. the controllers run on one CPU and the decoder run on the other. To emulate the speed controller (which is assumed to be integrated in silicon in a future chip) the frequency scaling capabilities of the chipset have been used. At this end, the predictive controller of section 3 is implemented as a custom module of the cpufrequtils package, allowing to control the CPU frequency between 800 MHz and 2.535 GHz in several steps. On the other hand, the frame controller and decoder are encoded in Posix pthreads using the features of the Real-Time Posix library. The decoder itself is based on the reference implementation of the H.264 standard, namely the free and open source JSVM 1 software. This version is far to be optimised (compared with available versions such as the ffmpeg package) but it both implements all the features of the H.264/SVC and is open source, so that the source code can be easily instrumented to integrate the control features described in the previous sections. The counterpart w.r.t. optimised parallel versions is that only low resolution decoding can be achieve in real-time, anyway the set-up is able to demonstrate the efficiency of the approach.

Experimental results

The following decoding experiments use a 1000-frame video encoded with a IBBBPBBBI structure. Due to the low performance of the JSVM decoder only low resolution (624 × 352 pixels) is used. Two quality layers were considered, with or without post-processing filter. Indeed, an optional final processing is possible using a filter which, if applied, improves the final quality of the picture. The CPU frequency is controlled in three steps, with F 1 = 2535 MHz, F 2 = 1600 MHz and F 3 = 800 MHz. For this particular video sequence and CPU, the average decoding time for one frame is around 50 ms at the highest quality (including filter). The decoder has been tested with various requested frame deadline values between 40 and 60 ms. Therefore, the decoding process is stressed for the shorter requested values and it is expected that the control strategy is able to keep a high decoding quality despite the lack of computing resources. Also, for the slower requested decoding rates it is expected that the control strategy allows to save CPU cycles and energy compared with an uncontrolled decoder.

Frame deadline control

The first experimental results show the efficiency of the deadline controller while keeping the CPU frequency constant, using the extra three-frame buffer to damp the decoding overshoots with filtering gain α = 0.1 and damping gain β = 0.3. Figure 4 plots the evolution of the deadline overshoot δ for a requested frame deadline of 50 ms. In Figure 4(a), this is done without any control. The plot exhibits a continuously growing drift in the decoding overshoot, as deadline errors accumulate with time. Conversely, using the deadline controller of subsection 4.0.2 allows to quickly absorb the deadline overshoots due to peaks in decoding time and to keep the real decoding schedule close to the theoretic one, as shown in Figure 4(b).

Control over various requested deadlines

The following plots report experiments where the frame decoding deadlines are fixed with requested values ranging from 40 to 65 ms, by steps of 5 ms. The expected frame deadlines are represented in green, the observed deadlines are plotted in red and the CPU frequency is highlighted in blue. i) In Figure 5, no feedback controller is active and, consequently, the CPU frequency is always at the maximal value. This is clearly neither energy nor computing efficient since the highest frequency as well as decoding quality are always applied even for large requested deadlines. ii) In Figure 6, the speed controller introduced in section 3 is active and the deadlines are fixed. For the shortest requested deadlines, the frequency is always maximal but, anyway, the deadlines cannot be reached due to the performance of the particular system used for these experiments (recall that the average decoding time for one frame is 50 ms). On the other hand, the decoding is finished on time for the larger ones and low frequency levels are used (which means the energy consumption can be reduced, as explained in the sequel) especially when the deadline constraint is weak. iii) In Figure 7, the speed and frame controllers of section 4 are both active. In that case, the requested deadlines are always achieved thanks to the QoS control and damping buffer. Indeed, the final filter is activated only when possible (the filter is activated/deactivated when the plot is respectively 1/0 in Figure 7). As expected, this filter is most often used for weak decoding constraints.

Energy consumption

The energy specifically spent for decoding could not be directly measured with the laptop used for the experiments, as it is not possible to spot out the energy cost of the CPUs from the energy spent by the peripherals (e.g. the GPU). Nevertheless, using the process knowledge given in section 3, energy cost estimations can be carried out from the physical models.

First, there are two voltage levels with only one frequency level possible when the system is running at the maximal one and two possible levels for the lower voltage. Secondly, the low voltage level is defined as the half of the higher one (for simplicity). As a result, the energy consumption of the previous scenarii can be estimated as follows :

-When running at 2535 MHz, the supply voltage is V .

-When running at 1600 MHz, the supply voltage is V /2.

-When running at 800 MHz, the supply voltage is V /2. Moreover, it is assumed that the energy used for decoding is proportional to f clk × V 2 dd , as explained in [START_REF] Chandrakasan | Minimizing Power Consumption in Digital CMOS Circuits[END_REF]. Thus, the estimated energy consumption for a video sequence where the average frame decoding time (with the highest quality) is 50 ms can be summarised in Table 1 (normalised for each requested deadline with the consumption obtained without any control). These results call for several remarks : i) For deadlines shorter than the average, the two controllers should be active. In particular, the frame deadline controller is able to toggle the quality level and avoids using permanently the highest frequency level, thus saving energy. ii) For requested deadlines larger than the average, it is unlikely that a deadline can be missed and the speed controller alone is most often enough to decode on time the incoming frames. In that case, the frame deadline controller uselessly anticipates future overshoots and induces useless costly CPU cycles at high speed.

Decoding quality degradation

Finally, a penalty criterion based on video expertise (borrowed from [START_REF] Wurst | QoS Control Strategies for High-Quality Video Processing[END_REF]) has been applied to assess for the decoding quality degradation due to stressed decoding conditions. The following penalties are applied and accumulated along the decoding process of the test sequence :

-Skipping a frame : -10000 -Deadline achieved without filter : +5 -Deadline achieved with filter : +10 -Increasing quality level : -10 -Decreasing quality level : -50

The results are plot in Figure 8 only for the stressing deadlines (40, 45 and 50 ms), since longer deadlines are always achieved with no quality loss. Indeed, with the uncontrolled case, the decoding overshoots accumulate and finally induce quality level switches and even frame skips. The plot shows that using simple and cheap feedback controllers allows to increase the decoding quality while highly decreasing the computing and energetic costs.

Conclusion

In this paper a survey of problems related with very small scale integrated chips, running high computations demanding process on mobile devices, was first given. It appears that feedback control may provide solutions to fight against the silicon process variability, and to optimise a trade-off between the computation load and related energy cost in one hand and the application quality in the other hand. To support this statement a control architecture was proposed to target the particular case of an embedded video decoder. Several controllers are nested to meet the end-user's requirements in terms of quality of service and energy saving. The whole system finally runs minimising the energy consumption induced by computations while ensuring specified performances, which means that the video is decoded with a required resolution and rate while minimising the CPU consumption. An experimental validation of the proposal was set-up on a system using a single processor with different power modes for decoding. The results clearly show that up to 25 % energy saving can be achieved while keeping a specified video quality. As for other examples of integrated feedback control and computing systems (e.g. as in [START_REF] Lu | Feedback Control Real-Time Scheduling: Framework, Modeling and Algorithms[END_REF] and Hellerstein et al. ( 2004)), it is shown again that feedback loops can easily enhance the performance and robustness of a computing system for very moderate programming efforts and execution overheads.

Figure 1 .

 1 Figure 1. Proposed control architecture of an embedded video decoder.

Figure 2 .

 2 Figure 2. Different computational speed set-point buildings.

Figure 3 .

 3 Figure 3. Decoding times for I, P and B frames.

Figure 4 .

 4 Figure 4. Deadline errors when keeping the CPU frequency constant.

Figure 5 .

 5 Figure 5. Control over various requested deadlines without any feedback controller.

Figure 6 .

 6 Figure 6. Control over various requested deadlines with only speed control (the deadlines are constant).

Figure 7 .

 7 Figure 7. Control over various requested deadlines with speed and deadlines control (the computation load varies w.r.t. quantization and/or resolution layers).

Figure 8 .

 8 Figure 8. Decoding quality.

Table 1 .

 1 Energy consumption estimation.

	Deadline	Normalised energy consumption speed control only speed and frame control
	40	1	0.76
	45	1	0.81
	50	1	0.86
	55	0.92	1.01
	60	0.78	0.91
	65	0.65	0.77

http://ip.hhi.de/imagecom G1/savce/downloads/SVC-Reference-Software.htm

Acknowledgements

This research has been supported by ARAVIS, a Minalogic project gathering STMicroelectronics with academic partners, namely TIMA and CEA-LETI for micro-electronics, INRIA/LIG for operating system and INRIA/Gipsa-lab for control. The aim of the project is to overcome the barrier of sub-scale technologies (45nm and smaller).