Sophie Mercier
email: sophie.mercier@univ-pau.fr

I T Castro

Two imperfect repair models for a gamma deteriorating system: A comparison

 in the context of recurrent events: the ARA1 model assumes that a repair reduces the age accumulated by the system since the last maintenance action, in a given proportion. An ARD1 repair hence lowers the deterioration level, without rejuvenating the system. On the contrary, by an ARA1 repair, the system is put back to the exact situation where it was some time before, which entails the lowering of both its deterioration level and (virtual) age. The two models may hence correspond to different maintenance actions in an applicative context. This presentation focuses on the comparison between the two models, from a probabilistic point of view (moments and stochastic ordering). An application in a maintenance optimization context is also provided, for illustration purpose. A specific case is analyzed, where the two repair models provide identical expected deterioration levels at maintenance times ("equivalent" case). The comparison results can help understanding which among the two models is the best adapted in an applicative context.

INTRODUCTION

Many systems suffer a physical degradation before they fail. This degradation is a complex process as it depends of many factors (material, stress loads, temperature, ...). To mitigate the effect of the system degradation and to extend the system lifetime, a large volume of maintenance models have been proposed in the literature, with different maintenance actions. Most of these models are limited to perfect repairs [START_REF] Huynh | On the use of mean residual life as a condition index for condition-based maintenance decision-making[END_REF][START_REF] Caballé | A condition-based maintenance of a dependent degradation-threshold-shock model in a system with multiple degradation processes[END_REF], Hong et al. 2014 among others). However, imperfect maintenance actions describe more realistic situations than perfect repairs. Some advances have been made to include imperfect repairs in a degrading system. Alaswad & Xiang 2017 classified the impact of the maintenance actions over the maintained system into three types. The first type assumes that the maintenance actions return the system to a previous stage of deterioration. In the second type, the imperfect maintenance reduces the degradation level of the maintained system [START_REF] Castro | Performance measures for a deteriorating system subject to imperfect maintenance and delayed repairs[END_REF]. The third approach is based on the idea that the maintenance action changes the rate of degradation of the system [START_REF] Zhang | Degradation-based maintenance decision using stochastic filtering for systems under imperfect maintenance[END_REF]. However, as [START_REF] Zhang | Degradation-based maintenance decision using stochastic filtering for systems under imperfect maintenance[END_REF] claimed, the issue of treating imperfect maintenance in the context of degrading systems remains widely open nowadays.

Following the spirit showed in [START_REF] Mercier | On the modelling of imperfect repairs for a continuously monitored gamma wear process through age reduction[END_REF] and [START_REF] Castro | Performance measures for a deteriorating system subject to imperfect maintenance and delayed repairs[END_REF], two models of imperfect repair are here proposed and compared for a system accumulating deterioration over time. The first model, called the Arithmetic Reduction of Deterioration of order 1 (ARD1), assumes that the repair removes the proportion ρ of the degradation accumulated by the system from the last maintenance action (with ρ ∈ (0, 1)). The second model, called Arithmetic Reduction of Age of order 1 (ARA1), refers

T 2T 3T 0 Y t X (1) t X (2) t X (3) t X (4) t
Figure 1: Illustration of the ARD1 policy for ρ = 0.5 to the virtual age models proposed by [START_REF] Kijima | Some results for repairable systems with general repair[END_REF]) and further studied by [START_REF] Doyen | Classes of imperfect repair models based on reduction of failure intensity or virtual age[END_REF] in the context of recurrent events: the ARA1 model assumes that the repair removes the proportion ρ of the age accumulated by the system since the last maintenance action. An ARD1 repair hence lowers the deterioration level, without rejuvenating the system. On the contrary, by an ARA1 repair, the system is put back to the exact situation where it was some time before, which entails the lowering of both its deterioration level and (virtual) age. The two models may hence correspond to different maintenance actions in an applicative context.

For a better understanding of the differences between the two models, this paper focuses on their comparison, from a probabilistic point of view. Assuming that the degradation of the system is modeled by a non homogeneous gamma process, stochastic comparisons of both location and spread of the two resulting processes are given. Moreover, a specific case is analyzed, where the two models provide identical expected deterioration levels at repair times ("equivalent" case). Finally, an illustration of the two models is provided, by including them in a global maintenance policy, with replacement of the system when it is too deteriorated.

The paper is organized as follows: The two models of imperfect repair are described in Section 2. The comparison results are given in Section 3 (including the "equivalent" case). Section 4 deals with the application to the global maintenance strategy and concluding remarks are provided in Section 5, together with possible extensions.

THE TWO MODELS OF IMPERFECT REPAIRS

f a,b (x) = b a Γ (a)
x a-1 e -bx , ∀x > 0.

The corresponding mean and variance are a b and a b 2 , respectively.

A system is considered with degradation modeled by a non homogeneous gamma process (X t ) t≥0 with parameters A(•) and b, where A(•) : R + -→ R + is continuous and non-decreasing with A (0) = 0, and b > 0. We recall that (X t ) t≥0 is a process with independent increments such that X 0 = 0 almost surely and such that each increment X t+s -X t is gamma distributed Γ(A(t + s) -A(t), b) for all s, t > 0.

The system is periodically and instantaneously repaired each T units of time. For modeling purpose, we set X (i) , i ∈ N * to be i.i.d. copies of X = (X t ) t≥0 , where X (i) describes the evolution of the deterioration level between the i-th and (i + 1)-th maintenance actions. For each imperfect repair model, the maintenance efficiency is measured by an Euclidian parameter ρ ∈ (0, 1).

First model: Arithmetic Reduction of Deterioration of order 1 (ARD1)

In this model, the maintenance action instantaneously removes the proportion ρ of the degradation accumulated by the system from the last maintenance action (or from the origin). We set (Y t ) t≥0 be the process that describes the degradation level of the maintained system under this model of repair. The ARD1 model is sketched in Figure 1 for ρ = 0.5. It is developed as follows: At the beginning, the system deteriorates according to X (1) . It is first maintained at time T , where the proportion ρ of the accumulated deterioration since the origin is removed. This provides: Between T and 2T , the system deteriorates according to X (2) . The age of the system is unchanged at time T and we have

Y t = X (1) t t < T, Y T = (1 -ρ) X (1) T . T 2T 3T 0 Z t X (1) t X (2) t X (3) t X (4) t
Y t = Y T + X (2) t -X (2) T
for all T ≤ t < 2T . At the second maintenance time 2T , the proportion ρ of the degradation accumulated between T and 2T is removed, which provides:

Y 2T = Y T + (1 -ρ) X (2) 2T -X (2) T .
More generally, we have:

Y t = Y nT + X (n+1) t -X (n+1) nT
for all nT ≤ t < (n + 1) T , where

X (n+1) t -X (n+1) nT is gamma distributed Γ(A (t) -A (nT ) , b) and Y (n+1)T = Y nT + (1 -ρ) X (n+1) (n+1)T -X (n+1) nT .
This provides

Y nT = (1 -ρ) n i=1 X (i) iT -X (i) (i-1)T with Γ A (nT ) , b
1-ρ as distribution. When ρ → 1 -, then Y nT → 0 + and the system is renewed at time nT (As Good As New repair: AGAN). When ρ → 0 + , the repair is ineffective and it is As Bad As Old (ABAO).

Except for the case ρ → 0 + , if t mod T = 0 , Y t is the sum of two independent and gamma distributed random variables (r.v.s) with different scale parameters, and it is not gamma distributed. Its expectation and variance are given by:

E (Y t ) = A (t) -ρ A (nT ) b , (1)
var

(Y t ) = A (t) -ρ (2 -ρ) A (nT ) b 2 , ( 2
)
for nT ≤ t < (n + 1) T .

It is easy to check that E (Y t ) and var (Y t ) are decreasing with respect to ρ, that is, the more efficient the repair, the smaller the expectation and variance of the deterioration level. In this way, the expectation and variance are minimal when ρ → 1 -that is when the repair is AGAN, and maximal when ρ → 0 + that is when the repair is ABAO.

Second model: Arithmetic Reduction of (virtual) Age of order 1 (ARA1)

As told in the introduction, the ARA1 model is based on the notion of virtual age, which is reduced by each maintenance action: each repair removes the proportion ρ of the age accumulated by the system since the last maintenance action (or from the origin). This means that, at each maintenance action, the system goes back into its past: the deterioration level is hence reduced (just as for the ARD1 model) but the system is also rejuvenated at the same time (it becomes younger). In case of an increasing deterioration rate (A(•) convex), the rate of deterioration is hence reduced by the repair together with the deterioration level. We set (Z t ) t≥0 be the process that describes the degradation level of the maintained system under this model of repair. The ARA1 model is sketched in Figure ?? for ρ = 0.5. It is developed as follows: At the first maintenance time T , the (virtual) age of the system is suddenly reduced of ρT , so that it becomes T -ρT = (1 -ρ)T . This provides:

Z t = X (1) T for t < T, Z T = X (1)
(1-ρ)T .

For T ≤ t < 2T , the age of the system is (1 -ρ)T + (t -T ) = t -ρT . We get:

Z t = Z T + X (2) t-ρT -X (2)
(1-ρ)T .

At time 2T -(just before the repair), the age of the system is 2T -ρT which is reduced of ρT at time 2T .

The age hence is 2(1 -ρ)T at time 2T . This provides:

Z 2T = Z T + X (2) 2(1-ρ)T -X (2)
(1-ρ)T .

More generally, for nT ≤ t < (n + 1) T , the virtual age of the system at time t is t -ρnT (which is just the same as for an ARA1 model for recurrent events, see [START_REF] Doyen | Classes of imperfect repair models based on reduction of failure intensity or virtual age[END_REF]). We obtain:

Z t = Z nT + X (n+1) t-ρnT -X (n+1) (1-ρ)nT , for all nT ≤ t < (n + 1) T , where X (n+1) t-ρnT -X (n+1) (1-ρ)nT is gamma distributed Γ (A (t -ρnT ) -A ((1 -ρ) nT ) , b) and Z (n+1)T = Z nT + X (n+1) (1-ρ)(n+1)T -X (n+1) (1-ρ)nT . Hence Z nT = n i=1 X (i) (1-ρ)iT -X (i) (1-ρ)(i-1)T and it is gamma distributed Γ(A ((1 -ρ)nT ) , b).
Here, Z t is the sum of two independent gamma distributed r.v.s which share the same scale parameter b and it is gamma distributed Γ(A(t -ρnT ), b). Also:

E (Z t ) = A (t -ρnT ) b , var (Z t ) = A (t -ρnT ) b 2 (3)
for all nT ≤ t < (n + 1)T .

Here again, it is easy to check that E (Z t ) and var (Z t ) are decreasing with respect to ρ. Also, the cases ρ → 1 -and ρ → 0 + correspond to AGAN and ABAO repairs, respectively.

COMPARISON RESULTS

Comparison of the moments

We now come to the main object of the paper, which is the comparison between the two models of imperfect repairs. Note that, in an applicative context, there is no reason why the estimated repair efficiency should be the same when the impact of the maintenance is modeled by an ARD1 or ARA1 model. Considering two different efficiency parameters ρ i , i = 1, 2, our point here is to compare Y

(1) t and Z

(2) t , where exponent (i) refers to ρ i for i = 1, 2. We begin with the comparison of their respective means and variances.

Due to the reduced size of the paper, results on the comparison of moments are provided only in case of a power-law shape function for the gamma process. The interested reader will find general results in an extended version of the paper (Mercier and Castro, submitted), as well as proofs for all the results of the paper. (2) t with respect to t for

A (t) = t 3 , b = 1, ρ 1 = 0.95, ρ 2 = 0.5, T = 1 Proposition 1 Let A(t) = αt β with α, β > 0. Assume β ≤ 1. 1. We have E Z (2) t ≥ E Y (1) t , ∀t > 0 if and only if (1 -ρ 2 ) β ≥ (1 -ρ 1 ) .
2. We have

V ar Z (2) t ≥ V ar Y (1) t , ∀t > 0 if and only if (1 -ρ 2 ) β ≥ (1 -ρ 1 ) 2 .
If β ≥ 1, all results are valid with reversed inequalities.

For illustration purpose, we consider A (t) = t 3 , b = 1, T = 1 and ρ 2 = 0.5. As a first case, we take ρ 1 = 0.3 so that the conditions of the previous proposition are fulfilled for both expectation and variance. As expected, Figure 3 shows that E Y

(1) t and E Z

(2) t are ordered in the same way on the whole real line, the same for the variance. As a second case, we take ρ 1 = 0.95 so that the conditions are not fulfilled neither for expectation and variance. Figure 4 shows that E Y

(1) t and E Z

(2) t are not ordered in the same way on the whole real line, the same for the variance.

Technical reminders

Before providing stochastic comparison results between Y

(1) t and Z

(2) t , we here recall a few definitions and results from the literature.

As a first step, let us recall that given two non negative random variables X and Y with probability distribution functions f X and f Y , and survival functions FX and FY , respectively, then: (2) t with respect to t for

A (t) = t 3 , b = 1, ρ 1 = 0.95, ρ 2 = 0.5, T = 1 1. X is said to be smaller than Y in the usual stochastic order (X ≺ sto Y ) if FX ≤ FY ; 2. X is said to be smaller than Y in the likelihood ratio order (X ≺ lr Y ) if f Y f X is non-decreasing; 3. X is said to be smaller than Y in the convex (concave) order (X ≺ cx(cv) Y ) if E (ϕ (X)) ≤ E (ϕ (Y )
) for all convex functions ϕ (provided the expectations exist); 4. X is said to be smaller than Y in the increasing convex (concave) order (X

≺ icx(icv) Y ) if E (ϕ (X)) ≤ E (ϕ (Y )
) for all increasing convex (concave) functions ϕ (provided the expectations exist).

The usual stochastic order and the likelihood ratio order compare the locations of random variables whereas increasing convex (concave) orders also compare their variability:

X ≺ icx (≺ icv )Y roughly means that E(X) ≤ E(Y ) (location condition) plus the fact that X is less (more) "variable" than Y , in a stochastic sense. Also, X ≺ cx (≺ cv )Y is equivalent to X ≺ icx (≺ icv )Y plus E(X) = E(Y ).
The likelihood ratio order is known to imply the usual stochastic order, which itself implies both increasing convex and concave orders, see [START_REF] Müller | Comparison methods for stochastic models and risks[END_REF][START_REF] Shaked | Stochastic Orders[END_REF] for more details.

We finally review known results on the comparison of gamma distributions in the following lemma, see (Müller & Stoyan 2002, p. 62) for instance.

Lemma 1 Let X and Y be gamma distributed random variables with parameters (a 1 , b 1 ) and (a 2 , b 2 ), respectively, where a i , b i > 0 for i = 1, 2. Then:

1. If a 1 ≤ a 2 and b 1 ≥ b 2 , then X ≺ lr Y ; 2. If a 1 ≥ a 2 and a 1 /b 1 ≤ a 2 /b 2 , then X ≺ icx Y ; 3. If a 1 ≤ a 2 , b 1 ≤ b 2 and a 1 /b 1 ≤ a 2 /b 2 , then X ≺ icv Y .
The previous lemma is the basis for deriving the stochastic comparison results between the different imperfect repair models given in the next subsection.

Stochastic comparison results

As a first step, the influence of the efficiency parameter ρ on the deterioration level is studied for each imperfect repair model.

Proposition 2 We have:

1. Y nT decreases with respect to ρ in the sense of the likelihood order: If

ρ 1 < ρ 2 , then Y (2) nT ≺ lr Y (1)
nT ; 2. Y t decreases with respect to ρ in the sense of both increasing convex and concave orders:

If ρ 1 < ρ 2 , then Y (2) t ≺ icx Y (1) t and Y (2) t ≺ icv Y (1)
t ; 3. Z t decreases with respect to ρ for the likelihood ratio order (and hence also for both increasing convex and concave orders): If

ρ 1 < ρ 2 , then Z (2) t ≺ lr Z (1)
t . In each case, we can see that as expected, the more efficient the maintenance action is (namely the larger ρ is), the smaller the deterioration level is. Note however that, based on the fact that the likelihood ratio order is stronger than both increasing convex and concave orders, the results for the ARA1 model are stronger than for the ARD1 one. (Counter-examples can be found, which show that that Y

(1) t and Y

(2) t are not comparable for the likelihood ratio order in a general setting).

We now come to the stochastic comparison between the two models.

Theorem 1 If A (•) is concave and A ((1 -ρ 2 )t) ≥ (1 -ρ 1 )A(t) for all t (4) (which is true if ρ 1 ≥ ρ 2 ), then Y (1) t ≺ icx Z (2) t for all t ≥ 0. If A (t) is convex with a reversed inequality in (4), then Z (2) t ≺ icv Y (1) t for all t ≥ 0. As a specific case, if ρ 1 = ρ 2 = ρ, then Y t ≺ icx Z t for all t ≥ 0 if A(•) is concave, and Z t ≺ icv Y t for all t ≥ 0 if A(•) is convex.
The concavity/convexity of the shape function A(•) of the underlying gamma process hence deeply infers on the comparison results between the two models: When A(•) is convex, the rejuvenation included in a ARA1 model leads to a lower deterioration level than for an ARD1 model.

Specific results are now summarized in the classical case of a homogeneous gamma process for both moments and stochastic comparisons.

Corollary 1 Assume that A(t) = αt for all t ≥ 0, where α > 0. We have the following results:

1. If ρ 1 ≥ ρ 2 , then Y (1) t ≺ icx Z (2) t
and hence

E(Y (1) t ) ≤ E(Z (2) t ) for all t ≥ 0; 2. If ρ 1 ≤ ρ 2 , then Z (2) t ≺ icv Y (1) t and hence E(Z (2) t ) ≤ E(Y (1)
t ) for all t ≥ 0;

3. If ρ 1 = ρ 2 , then Y (1) t ≺ cx Z (2) t and Z (2) t ≺ cv Y (1) t and hence E(Z (2) t ) = E(Y (1) t ) for all t ≥ 0; 4. V ar Z (2) t ≥ V ar Y (1) t for all t > 0 if and only if 1 -ρ 2 ≥ (1 -ρ 1 ) 2 .

Mostly equivalent imperfect repair models

In an applied context, parameters ρ 1 and ρ 2 for ARD1 and ARA1 models, respectively, will be estimated from feedback data, which will be typically gathered at maintenance times iT , i ≥ 1. As a consequence, we can expect that the estimated parameters ρ1 and ρ2 should be such that the corresponding expected deterioration levels should be very similar at maintenance times, namely such that E Y

(1) iT E Z

(2) iT for all i ∈ N * . Equivalently, the estimated parameters should be such that

(1 -ρ1 ) A (iT ) b A ((1 -ρ2 ) iT ) b , for all i ≥ 1.
There hence is a specific interest for the applications to compare the ARD1 and ARA1 models under the condition

(1 -ρ 1 ) A (iT ) = A ((1 -ρ 2 ) iT ) for all i ≥ 1, (5)
which will lead to equivalent deterioration levels at maintenance times. However, the previous requirement (5) does not seem to have a solution for a general shape function A (•). We hence restrict the study to the power-law case A (t) = αt β (with α, β > 0), for which (5) is just equivalent to

1 -ρ 1 = (1 -ρ 2 ) β .
A homogeneous gamma process corresponds to a power-law shape function with β = 1. Then the equivalent case just means that the two models share the same efficiency parameters (ρ 1 = ρ 2 ).

In case of a general power-law shape function, note that the "equivalent" case has a similar spirit to that detailed in (Doyen & Gaudoin 2004, Property 4), where the authors match the minimal wear intensities of two imperfect repair models for recurrent events, based on the reduction of either virtual age or failure intensity.

The results for the equivalent case are summarized in the following proposition.

Proposition 3 Assume that A (t) = αt β (with α, β > 0) and that 1 -

ρ 1 = (1 -ρ 2 ) β . Then: 1. Z (2) nT ≺ cv Y (1) nT and Y (1) nT ≺ cx Z (2) nT (which both en- tail that var Z (2) nT ≥ var Y (1) nT ) for all n ≥ 1. 2. If β ≤ (≥) 1, then Y (1) t ≺ icx ( icv ) Z (2) t (which entails that E Y (1) t ≤ (≥) E Z (2) t
) for all t ≥ 0.

If

β ≤ 1, then V ar Z (2) t ≥ V ar Y (1) t for all t ≥ 0.

APPLICATION

For illustration purpose of the previous results, the system is now supposed to provide some reward per unit time, which decreases when the deterioration level of the system increases. Based on classical functions used in the insurance literature ((Rolski, Schmidli, Schmidt, & Teugels 1998)), we assume that the reward function is of the shape

g(x) = (b 1 -k 1 e α 1 x ) 1 {0≤x≤c} + (b 2 -k 2 e α 2 x ) 1 {c<x} , (6) with b 1 , b 2 , α 1 , α 2 , k 1 , k 2 , c > 0.
The reward function is supposed to be continuous and positive on [0, c), which implies that

b 2 -k 2 e α 2 c = b 1 -k 1 e α 1 c > 0. (7)
Also, we assume that α 1 ≤ α 2 and k 1 ≤ k 2 so that level c appears as a critical level, from which the system becomes less performing. With the previous assumptions, it is easy to check that g is a concave function and that g(x) > 0 if and only if

x < L = ln(b 2 /k 2 ) α 2
. Level L hence appears as a critical threshold, from where the unitary reward becomes negative.

An example of reward function is plotted in Figure 5 with parameters α 1 = 0.1, b 1 = 11 monetary units (m.u.), α 2 = 0.25, k 1 = 1 (m.u.), k 2 = 1 (m.u.), c = 4, and b 2 obtained through (7). With this dataset L 10.01.

The system is assumed to be preventively repaired each T units of time according to an ARD1 or ARA1 model, with efficiency parameters ρ 1 and ρ 2 , respectively. The accumulated reward on a time interval

[0, t] hence is R (1) ARD1 (t) = E t 0 g(Y (1) s )ds = t 0 E g(Y (1) s ) ds
with a similar expression for the accumulated reward R

(2) ARA1 (t) in the ARA1 case. Considering for instance the equivalent case (A (t) = αt β and 1 -ρ 1 = (1 -ρ 2 ) β ) with β ≤ 1, we easily derive from point 2 in Proposition 3 that

E g(Y (1) s ) ≥ E g(Z (2) s )
for all s ∈ [0, t], using the fact that -g is an increasing convex function. This immediately entails that R

(1)

ARD1 (t) ≥ R (2)
ARA1 (t) for all t ≥ 0.

As a consequence, even if the "equivalent" case provides similar expected levels at maintenance times, they do not provide the same accumulated rewards on some given time interval. They may hence lead to different decisions in an applied context, for instance for optimizing maintenance strategies.

To better illustrate this difference, we now consider a preventive maintenance strategy, which we next optimize. The assumptions are the following:

• The unitary reward of the system per unit time is given by the reward function g provided in (6). We recall that L = ln(b 2 /k 2 ) α 2 stands for a "critical" level, from where the reward becomes negative.

• The system is preventively repaired each T units of time according to an ARD1 or ARA1 model (respective efficiency parameters: ρ 1 and ρ 2 ), up to the first maintenance time KT where the deterioration level is observed to be beyond a given preventive threshold M (with M < L). In that case, instead of an imperfect repair (ARA1 or ARD1), a replacement is performed at time KT with cost C c m.u. when the level is beyond L (corrective replacement) and C p m.u. when it is between M and L (preventive replacement).

The successive (corrective or preventive) replacements of the system appear as the points of a renewal process, and the long time (operating) profit rate per unit time is given by

C ARD (T, M ) = 1 E(K)T E KT 0 g Y (1) s ds -C r (E(K) -1) -C p P M ≤ Y (1) KT < L -C c P L ≤ Y (1) KT
for the ARD1 model with a similar expression for the ARA1 model (C ARA (T, M )). Due to the complexity of the model, there is not hope here to find conditions that ensure the dominance of one of the two functions C ARD (T, M ) or C ARA (T, M ) on the other. The comparison is hence made on a numerical example.

The degradation is modeled by a homogeneous gamma process with parameters A(t) = 1.3t and b = 0.8. The parameters of the reward function g are α 1 = 0.4, α 2 = 0.5, b 1 = 800 m.u., k 1 = 1.05 m.u., k 2 = 1.07 m.u., c = 8, which implies b 2 832.66 m.u. and L 13.31. The repair efficiencies of the ARD1/ARA1 repairs are ρ 1 = ρ 2 = 0.9, which corresponds to an equivalent case (homogeneous gamma process and ρ 1 = ρ 2 ). Their common cost is C r = 200 m.u.. The cost of a preventive replacement is C p = 1 000 m.u. whereas it is C c = 1300 m.u. for a corrective one. Figures 6a and6b show the profit rates for the maintained system under ARD1 and ARA1 repairs, respectively. These figures have been computed considering a grid of 10 points for T from 1.14 to 4 and a grid of 13 points for M from 1 to L and 10 000 simulations for each pair of points. For both ARD1 and ARA1 cases, the optimal maintenance strategy corresponds to T opt 3.05. However, the corresponding optimal maintenance levels are M opt ARD 9.21 and M opt ARA 10.24, and the optimal unitary rewards C opt ARD 673.94 and C opt ARA 684.34 m.u. per unit time, respectively. There hence is a difference of about 10% between the two optimal preventive levels, which may entail inappropriate decision in an applicative context, when considering one imperfect repair model or the other, whereas the effective behavior of the maintained system is closer to the other one.

CONCLUSIONS AND FURTHER EXTENSIONS

Two imperfect repair models for a degrading system have been proposed and compared in this paper. One is based on the reduction of the single deterioration level at maintenance times (ARD1), the other one on the reduction of both deterioration level and age (ARA1). They hence correspond to different maintenance actions, in an applicative context. The comparison of both location and spread have been made in terms of moments and stochastic ordering of the two resulting processes. It has been seen that the concavity/convexity of the shape function of the underlying gamma wear process plays a central role in the comparison results. This corresponds to intuition as a convex shape function (for instance) induces some increasingness property in the rate of deterioration over time. Hence, rejuvenating the system as in an ARA1 one action will decrease the rate of deterioration together with the deterioration level.

As for the stochastic comparison results, the paper focuses on the likelihood ratio order, which is well-known in reliability theory, but also on the (increasing/decreasing) convex/concave orders, which come from the insurance literature and seem a little less common in papers devoted to reliability theory. Clearly, other stochastic orders might be considered such as Laplace transform order or Excess Wealth order for instance. Other questions of interest concern the comparison of remaining lifetimes, considering the system as failed (or too degraded) when its deterioration level is beyond a fixed failure (critical) threshold. From a theoretical point of view, this seems a difficult issue in a general setting. One could then look at partial results on specific models.

Furthermore, the paper made an attempt for comparing the two types of imperfect repair including them in a global maintenance policy. Clearly, this subject requires further investigation for a better understanding of the practical consequences on the optimal policy of choosing one model of imperfect repair or the other, and typically, this would require a numerical study at a larger scale. Of course, it would also be of interest to consider other types of global maintenance policy (among the numerous ones developed in the literature, e.g. see van Noortwijk 2009), including one model of imperfect repair or the other.

Finally, a gamma deterioration model has been assumed in this paper. The stochastic comparison results between the two imperfect repair models deeply rely on the comparison properties of the gamma distribution, as summed up in Lemma 1. As noted by the referee, a question of interest would be to revisit the comparison between the two imperfect repair models considering other deterioration models (such as Wiener processes with trend or other subordinators).

2. 1

 1 The intrinsic deterioration and notations For a, b > 0, let us first recall that the gamma distribution Γ (a, b) with parameters (a, b) admits the follow-ing p.d.f. (probability distribution function):

Figure 2 :

 2 Figure 2: Illustration of the ARA1 policy for ρ = 0.5

Figure 3 :

 3 Figure 3: Mean and variance of Y (1) t and Z

  Figure 4: Mean and variance of Y (1) t and Z

Figure 5 :

 5 Figure 5: The reward function g for α 1 = 0.1, b 1 = 11 m.u., α 2 = 0.25, k 1 = 1 m.u., k 2 = 1 m.u., c = 4.

Figure 6 :

 6 Figure 6: Operational profit rates, ρ 1 = ρ 2 = 0.9


Stephen J Mellor

John R Wolfe

Campbell Mccausland

Why Systems-on-Chip Needs More UML like a Hole in the Head

Let's be clear from the outset: SoC can most certainly make use of UML; SoC just doesn't need more UML, or even all of it. The advent of model mappings, coupled with marks that indicate which mapping rule to apply, enable a major simplification of the use of UML in SoC.

The Need for an SoC Abstract Modeling Language

At the beginning of an SoC project, it is common for the hardware and software teams to work a specification in parallel. Invariably, the two components do not mesh properly. You can't verify understanding until you have something to execute; and once you have something that executes, it costs a lot to change the interface.

Once the prototype runs, it is possible to measure the performance, which may require changing the partition. Partition changes are expensive, and are difficult to do correctly. Moreover, the system is usually "specified" only in terms of implementation. We need a way to model a system at an appropriate level of abstraction that does not presume an implementation in software or hardware. SystemC and Handel-C are low-level, and presume too much implementation.

Executable and Translatable UML

The introduction of the Action Semantics enables execution of UML models. The Executable UML profile [START_REF] Mellor | Executable UML: A Foundation for Model-Driven Architecture[END_REF] defines a carefully selected streamlined subset of UML and defines an execution semantics for it.

The essential elements are a set of classes and objects with concurrently executing state machines. State machines communicate only by sending signals. On receipt of a signal, a state machine executes a set of actions that runs to completion before the next signal is processed. The actions in the destination state of the receiver execute after the action that sent the signal. This captures desired cause and effect.

A model can be executed independent of implementation. No design details or code need be added, so formal test cases can be executed against the model to verify that requirements have been properly met. Critically, Executable UML is structured to allow developers to model the underlying semantics of a problem without having to worry about whether it is to be implemented in hardware of software.

Them's the rules, but what is really going on is that Executable UML is a concurrent specification language. Rules about synchronization and object data consistency are simply rules for that language, just as in C++ we execute one statement after another and data is accessed one statement at a time. We specify in such a concurrent language so that we may translate it onto concurrent, distributed platforms; hardware definition languages; as well as fully synchronous, single tasking environments.

Marks

Marks describe models but they are not a part of them, rather like sticky notes. A mark is a lightweight, nonintrusive extension to models that captures information required for mappings without polluting those models. Mappings rules are applied to model elements that have been marked to indicate which rule to apply-hardware or software. An example is the mark isHardware, which may be associated with some element to be implemented in hardware. This allows for retargeting models to different implementation technologies as they change. Mappings and marks are described in [START_REF] Mellor | MDA Distilled: Solving the Integration Problem with the Model Driven Architecture[END_REF].

Model Mappings

At system construction time, the conceptual objects are mapped to hardware and software. Repeatable mappings are defined that produce compliable text (e.g., C, VHDL) according to a single consistent set of architectural rules. The mapping rules therefore guarantee that the interfaces are consistent. A model compiler interprets the mapping rules to maintain the desired sequencing specified in the models, which it may do any manner it chooses so long as the defined behavior is preserved.

The result is several text files of two (in this example) types. One is all the C that is to be implemented in software; the other is VHDL. The two halves are known to fit together because the interface was generated. Changing the partition is a matter of changing the placement of the marks.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

A Hole in the Head

Executable UML is a small, but powerful, subset of UML enabling abstract specification of behavior. Mappings enable interface definition in one place, so that consistency is guaranteed. Marks enable late decision making on the partition. That's all we need; we need more UML like a hole in the head.


Qiang Zhu

Ryosuke Oishi

Takashi Hasegawa

Tsuneo Nakata

Integrating UML into SoC Design Process

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Gh Bodean
email: gbodean@mail.md

D Bodean

A Labunetz

New Schemes for Self-Testing RAM

This paper gives an overview of a new technique, named pseudo-ring testing (PRT). PRT can be applied for testing wide type of random access memories (RAM): bitor word-oriented and single-or dual-port RAM's. An essential particularity of the proposed methodology is the emulation of a linear automaton over Galois field by memory own components.

Introduction

March algorithms are commonly and widely used to test the units of random access memory (RAM). In [START_REF] Van De Goor | Testing Semiconductor Memories, Theory and Practice[END_REF] it is proposed a formal notation of the mathematical presentation of March-test algorithm. An example of such notation is the following: MarchA= {c(w0); ⇑(r0w1); ⇓(r1w0)}, where the symbols {⇑, ⇓, c} refer to traversing the address space of a memory (respectively up, down or don't care address order). The operations w d and r d refer to write or read logic value: d∈{0, 1}.

A new self-test RAM methodology (technique), named pseudo-ring testing (PRT), was proposed recently [START_REF] Gh | PRT: Pseudo-Ring Testing -a Method for Self-Testing RAM[END_REF]. In this paper a retrospectives and some new schemes of this technique for a wide type of RAM are presented. PRT schemes will be referred to bit-oriented (BOM) and wordoriented memory (WOM). The cell size m of the BOM is equal to 1 and for WOM is m>1. Some algorithmic features for single and multi-port memories also will be presented.

PRT-scheme for BOM and WOM

The PR-testing consists of some, so-called, π-test iterations. In particular case, such iteration can be shown by the equation:

( ) { } 1 2 1 2 0 , , iteration π + + + = = ⊕ = - i i i i i n i r r w r r c , ( 1
)
where {…} signifies a sub-iteration that performs the included operations. Index i refers to the address cell of a memory array. Symbol ⊕ signs the operation sum modulo In the next step first and second read-operations read from two neighboring memory cells and the third writeoperation writes the sum modulo 2 (XOR) of the read values to the next (third) memory array cell. Next set of operations will read second and third memory cells and writes results of its logical contains to the next, forth, memory cell, and so on. This enables an automatic generation of the test data background (TDB).

At the end of π-test iteration the final state Fin is compared with expected one Fin * . The state Fin * can be estimated a priori, because π-test iteration has an adequate linear automaton model. This model is well known as Linear Feedback Shift Register (LFSR). The LFSR can be bit-oriented, when the stage contains one bit, and wordoriented, when the stage contains more than one bit.

Structure of LFSR is defined by polynomial

∑ = = k i i i x a x g 0 ) ( ,
where k is the number of linear automaton register stages; a i are the Galois field (GF) elements.

The PRT technique can be illustrated as a transition of a (virtual) linear automaton in the space of the cells memory array. Figure 1 illustrates the expected states of the BOM and WOM cells after iterative execution of subiterations [START_REF] Van De Goor | Testing Semiconductor Memories, Theory and Practice[END_REF]. For the scheme of figure 1,b the wordoriented virtual LFSR is defined by polynomial g(x)=1+2x+2x 2 that is irreducible in the field GF(2 4 ); size of word m is equal to 4. In each sub-iteration (1) is performed the multiplication and sum modulo p(z), where Multiplication over Galois field extensions is a more complex operation. It's proposed an algorithm to design the optimal scheme of multiplication by a constant in GF.

Multiplier by a constant contains only XOR-gates and can be implemented inherently in the memory circuit.

If the memory array size is multiple by the period of LFSR then virtual automaton will return to the initial state at the end of the test iteration (see figure 1,b). So, the πtest quality will be estimated by comparing initial Init and final Fin states of LFSR.

For the WOM there are intra-word faults that can be tested by parallel application of a π-testing for BOM. In this case it is supposed that there are m independent bitoriented linear automatons. For all automatons the read and write operations are executed simultaneously. To detect the intra-word faults two different π-testing can be performed: (1) with parallel or (2) with random trajectories. The trajectory is controlled by a small hardware overhead that can be programmed externally.

Pseudo-ring test quality

The quality (faults coverage) of PRT RAM can be strongly estimated by mathematical analysis of LFSR behavior in the space of a memory array. Defects in memory array are (generally) due to shorts and opens in memory cells, address decoder and read/write logic. These defects can be modeled as single and multi-cell memory faults [START_REF] Van De Goor | Testing Semiconductor Memories, Theory and Practice[END_REF]. There are three factors that influence on π-test quality and they can be used to control the π-testing: 1 -LFSR structure that is determined by generator polynomial structure; 2 -initial values for the π-test iterations; and 3 -LFSR trajectory that can be random, where address of memory cells are randomly selected, or deterministic, where address cells are selected in an increasing or a decreasing mode.

Applying Markov chain analysis it was shown that πtest iteration has a high resolution for most memory faults. Also, the combinatorial analysis of RAM π-testing has shown that it is necessary at least 3 test iteration to cover all specified faults. In [START_REF] Gh | PRT: Pseudo-Ring Testing -a Method for Self-Testing RAM[END_REF] was proved that all single and multi-cell memory faults are detected in 3 π-test iterations with a specific TDB. This result is valid for bit-oriented as well as for word-oriented memories. The time complexity of π-test iteration for single port RAM is order O(3n).

This time can be reduced in the case of multi-port RAM PRT.

PRT-scheme for a multi-port RAM

Two-port (2P) memory has two independent ports. Each port has an address and control input and data input/output. The read-write operation can be performed simultaneously. To implement π-test technique for 2P memories an additional hardware overhead on RAM chip area is need: "conversion" of the existent address registers into counters and a specific XOR-logic. The ponder of the hardware overhead in comparison with the memory capacity is of an order <2 -20 .

When polynomial g(x) has 2 terms is recommended (see [START_REF] Gh | Pseudo-Ring testing scheme of word-oriented dual-port RAM[END_REF]) to implement the π-testing scheme, shown in figure 2. The scheme represents the evolution of 2-stages LFSR. Symbol ⊕ signs the sum modulo p(z). Output edge means the read operation, and input edgewrite operation. Edges on one side of the vertical axis, that pass through the cells c i (i= 0,…, n-1), are referred to operation on the same port. The read operations of the scheme of figure 2 are carried out simultaneously. Thus, the time complexity of a π-test iteration for the analyzed schemes is equal 2n.

More complex and sophisticated PRT schemes can be designed for the QuardPort DSE family. For this type of units can be designed a single or multi-LFSR schemes. Choose of the π-testing scheme depends on the fault models.

Generally, exists a high degree of mobility to control the π-test experiments. The distinct feature of the pseudoring testing can be declared by the paradigm: testing memory by its own components. In this test schemes the RAM components, namely the memory array cells, take an active part in the test experiments.

  polynomial over GF(2), b i ∈{0,1}. For given example p(z)=1+z+z 4 .

Figure 1 .

 1 Figure 1. A π-test iteration: (a) for a BOM and (b) for a WOM.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Mahmut Kandemir
email: kandemir@cse.psu.edu

Guilin Chen
email: guilchen@cse.psu.edu

Locality-Aware Process Scheduling for Embedded MPSoCs*

Utilizing on-chip caches in embedded multiprocessorsystem-on-a-chip (MPSoC) based systems is critical from both performance and power perspectives. While most of the prior work that targets at optimizing cache behavior are performed at hardware and compilation levels, operating system (OS) can also play major role as it sees the global access pattern information across applications. This paper proposes a cache-conscious OS process scheduling strategy based on data reuse. The proposed scheduler implements two complementary approaches. First, the processes that do not share any data between them are scheduled at different cores if it is possible to do so. Second, the processes that could not be executed at the same time (due to dependences) but share data among each other are mapped to the same processor core so that they share the cache contents. Our experimental results using this new data locality aware OS scheduling strategy are promising, and show significant improvements in task completion times.

Introduction

Today's embedded applications are very different from those in the past, in terms of both application complexity and dataset sizes. Consequently, it is not feasible any more to meet demands of embedded applications by using single core based systems. Instead, we observe a growing trend towards employing multiprocessor-system-on-a-chip (MPSoC) type of architectures, where multiple processor cores reside on the same chip, and share data through onchip memory and/or on-chip communication network. While hardware support for embedded MPSoCs is extremely important (and it is in fact an active research area), we believe that task mapping and scheduling at the OS level is an area that can significantly affect overall performance.

*This work is supported in part by NSF Career Award #0093082.

One of the critical issues in embedded MPSoCs is onchip memory performance. This is because if on-chip memory is not utilized appropriately, one can incur a significant number of off-chip references (accesses), which can be very expensive from both performance and power perspectives. Since it is possible to execute multiple tasks (each with multiple processes) on a given MPSoC, the behavior of on-chip memory components of an MPSoC is not only determined by data access patterns of individual processes but also through the interaction among access patterns of different processes. Consequently, to maximize utilization of on-chip memory, one needs to take into account this interaction as well.

To illustrate the problem, let us consider the following scenario. Suppose that we have 8 processor cores in our MPSoC, and each core can execute one process at any given time. Let us assume that a task called Task1 is scheduled across these cores and another task called Task2 is scheduled next across the same cores. Assume further that the scheduler schedules the processes of these tasks iteratively in an interleaved manner (i.e., Task1, Task2, Task1, Task2, Task1,…). In this case, the data brought by the processes of Task1 into on-chip caches in the MPSoC can be displaced by those brought by the processes of Task2, and vice versa. As a consequence, the next time Task1 (Task 2) is scheduled, its processes may experience a large number of cache misses, degrading overall performance.

There are at least two potential complementary solutions to this problem. First, the processes that do not share any data between them should be scheduled at different cores if it is possible to do so (in an attempt to minimize the conflicts between them). The second potential solution is that the processes that could not be executed at the same time (e.g., due to data and/or control dependences) but share data among each other should be mapped to the same processor core so that they share cache contents. Focusing on array-intensive embedded applications from image and video processing domains and a cache-based embedded MPSoC architecture, this paper presents an OS scheduling strategy that incorporates these two solutions. The basic idea behind our scheduler is to capture inter-process data sharing and utilize this information in scheduling processes across multiple cores. We also propose a data re-mapping strategy to reduce the number of conflict misses between the processes that do not share data.

We implemented our approach within a simulation environment and tested its effectiveness using a set of tasks (applications) under different execution scenarios. Our experimental evaluation indicates that the proposed data-aware scheduling strategy is very successful in practice. We also observe that our savings are consistent across several simulation parameters.

The rest of this paper is organized as follows. Section 2 explains how we capture data sharings between different processes. Section 3 gives the details of our OS scheduling scheme. Section 4 presents an experimental evaluation of the proposed scheduling strategy. Section 5 discusses the related work in this area, and Section 6 concludes the paper and outlines our planned future efforts along this direction.

Capturing Inter-Process Data Sharing

To represent sets of data elements shared among processes, we use Presburger arithmetic. Our approach can be best explained using an example. Consider the two program fragments, Prog1 and Prog2, shown in Figure 1, each representing a task. The iteration space of the first fragment can be represented using the following set:

IS 1 = {[i 1 ,i 2 ]: 0 ≤ i 1 < 8 && 0 ≤ i 2 < 3000}.
Suppose that this task is parallelized in such a fashion, over 8 cores, that each process receives a set of successive loop iterations. Therefore, the iteration set of process k (where 0 ≤ k ≤ 7) can be represented as:

IS 1,k = {[i 1 ,i 2 ]: i 1 = k && 0 ≤ i 2 < 3000}.
Consequently, the set of data elements accessed by the k th process is:

DS 1,k = {[d 1 ,d 2 ]: d 1 =i 1 *1000+i 2 && d 2 =5 && [i 1 ,i 2 ] ∈ IS 1,k }.
Using DS 1,k and DS 1,p , one can express the set of elements shared by processes k and p as follows: SS 1,k,p = DS 1,k ∩ DS 1,p Similar sets can be written for every processor pairs. Note that the impact of these data sharings depends on the order in which these processes are scheduled (executed). If the processes are scheduled at the same time (i.e., concurrently), these sharings can cause data being duplicated across multiple on-chip caches. In this case, there is nothing much that can be done to take advantage of these data sharing from the scheduler's perspective. On the other hand, if k and p are scheduled one after another (e.g., due to lack of sufficient resources to execute them in parallel), one would prefer that they execute on the same processor core if they share data, or in different cores otherwise.

For our running example, Figure 2(a) illustrates the sharings between the different processor cores, assuming that we have four cores to execute the processes. Each cell (k,p) in this table gives the amount of data shared between process k and process p. Now, let us assume that processes 0, 2, 4, and 6 are scheduled at time quantum 1 (T 1 ) and the remaining four are scheduled at time quantum 2 (T 2 ). From the data sharing viewpoint, the best processto-core mapping is as shown in Figure 2(b). Notice that, in this mapping, the processor pairs share significant amount of data, which should normally result in a very good onchip cache behavior. As comparison, the alternate mapping depicted in Figure 2(c) for example would not lead to any data sharing, and thus, is not preferable from the cache utilization perspective. Let us now focus on Prog2 and the data sharing among its processes. Note that formulations similar to those of Prog1 can be developed for this task (Prog2) as well. We observe that the processes of Prog2 accesses array D that is not used in the processes of Prog1. Depending on how the arrays A and D are laid in the main memory, there can be cache conflicts (due to limited associativity). Consequently, each time a process (of Prog1 or Prog2) is scheduled, it would have only little opportunity (if any at all) for data reuse. In the next section, we give the details of our task scheduling strategy that minimizes such conflicts and optimizes the reuse of on-chip data as much as possible.

for(i 1 =0; i 1 < 8; i 1 ++) for(i 2 =0; i 2 < 3000; i 2 ++) B[i 1 ] += A[i 1 *1000 + i 2 ][5] Prog1 Task[i 1 ] (i 1 = 0, 1, 2, …, 7): for(i 2 =0; i 2 < 3000; i 2 ++) B[i 1 ] += A[i 1 *1000 + i 2 ][5] for(i 1 =0; i 1 < 8; i 1 ++) for(i 2 =0; i 2 < 3000; i 2 ++) B[i 1 ] += D[i 1 *1000 + i 2 ][5] Prog2 Task[i 1 ] (i 1 = 0, 1, 2, …, 7): for(i 2 =0; i 2 < 3000; i 2 ++) B[i 1 ] += D[i 1 *1000 + i 2 ][5]
P 0 T 1 3 2 1 0 Core (b) (c)

Details of Data Reuse Oriented Scheduling

In our framework, each task is represented using a process graph (denoted PG). Each node in the process graph of task i corresponds to a process j, and is denoted using P i,j . A directed edge from P i,j to P i,k indicates that the latter is dependent on the former. That is, P i,k can execute only when P i,j finishes its execution. Note that, depending on how the tasks in the system are constructed, there may also be dependences between processes that belong to different tasks (e.g., from P i,k to P i',l where i ≠ i'). Therefore, we can talk about an extended process graph (denoted EPG) that involves these inter-task dependences as well (in addition to intra-task dependences). When we are discussing an EPG, we can assume that each process has a unique id, and thus we remove its task id when there is no confusion. Our scheduling problem can then be defined as one of scheduling a given EPG such that onchip (L1) data reuse is maximized to the greatest extent possible. In the following paragraphs, we discuss the details of our scheduling approach.

Our approach to the scheduling problem is a greedy heuristic that is based upon data sharing between the processes. A formal sketch of our algorithm is given in Figure 3. In the initialization step of this algorithm, we identify the independent processes (i.e., the processes without an incoming dependence edge in the EPG) that can be mapped to the cores. These processes are the candidates for the first round of scheduling. However, if we have a larger number of candidates than the number of available cores, we need to make a selection from these candidates such that the data sharing between them is kept at the minimum. This makes sense since these processes are independent of each other and they will be mapped onto different cores. Our greedy scheduling algorithm iteratively removes the candidates that have the maximum data sharing with the other candidates until the number of the remaining candidates is equal to the number of the cores.

After the initialization step, the main body of the algorithm is executed. At each iteration of the while loop shown, we select for each core the next process to be scheduled on it. Our selection criterion this time is to maximize the data reuse between the selected process and the one that was scheduled on the same core in the previous step (scheduling quantum). Mathematically, supposing that process i was the current process scheduled on a particular core, the next process (denoted j) to be scheduled on the same core is selected such that:

|SS i,j | ≥ |SS i,k | for any k≠j. This approach clearly tries to maximize the reuse of on-chip data for any given core. It should be noticed, however, that since the cores are processed (by the algorithm) in a specific order, it is possible that this algorithm does not generate the best results (from data reuse perspective) in all cases.

An important point to note here is that, while the algorithm shown in Figure 3 tries to maximize data reuse, it is still possible for two processes without any data sharing to be scheduled on the same processor core successively. When this happens, data locality can be very poor depending on the number of cache conflicts. Next, we discuss this issue in detail.

The purpose of data mapping is to assign elements of each array of an application to memory locations. However, our goal in this mapping is to minimize the cache conflicts between the array elements manipulated by different processes that are scheduled on the same core. )), where addrs(.) is a function that maps each array element to a main memory address, and map(.) is a function that maps a given memory address to a cache line. The function addr(.) is determined by the specification of the programming language or the implementation of compiler. The map(.) is determined by cache parameters (e.g., cache size, associativity, and block size). For a multiple-way associative cache, we cannot statically determine which cache line a memory address may be mapped to. In this case, map() maps each address to a set of cache lines.

The cache line into which an array element can be loaded is determined by both addr(.) and map(.). We usually do not have the flexibility to change map(.) since it is determined by the hardware. On the other hand, a compiler can change addr(.) by changing the layouts of the arrays to reduce the conflicts. Figure 4 illustrates how we re-layout two arrays K 1 and K 2 to avoid the conflicts between them. Let us assume that we have two processes, p 1 and p 2 , and that process p 2 is scheduled right after p 1 . Assume further that process p 1 iteratively accesses each element of both arrays K 1 and K 2 , and process p 2 accesses only K 2 . Figure 4(a) shows the original memory layout of the two arrays. Using such layout, the elements of K 1 and K 2 may be mapped to the same cache line, which can create severe conflicts. Figure 4(b) shows our optimized layouts for arrays K 1 and K 2 . Specifically, we divide each array into a set of chunks. The size of each chunk is equal a half of one cache page 1 . Further, the chunks of arrays K 1 and K 2 interleave with each other. Using such a layout, the elements of K 1 cannot be mapped to the same cache lines to which the elements of K 2 are mapped. The following formula shows how we calculate the new address of each array element: where addr'(.) and addr(.) are the optimized and the original main memory address mappings; C is the size of cache page; b is either 0 or C/2. Note that two arrays using different values of b can never conflict with each other. For example, in Figure 4(b), K 1 is mapped using b=0 while K 2 is mapped using b = C/2. By re-layouting K 1 and K 2 , we avoid the conflicts between them, which is beneficial to the performance of p 1 . Further, when p 2 is scheduled, many elements of K 2 are already in the cache, which also improves the performance of p 2 . In Figure 5, we give the sketch of a greedy heuristic algorithm that selects the arrays for re-layouting. Specifically, in the while loop of the algorithm, we iteratively select the pair of arrays with maximum number conflicts with each other. If these arrays are accessed by the same process or respectively accessed by a pair of processes that are scheduled successively on the same core, we try to relayout them to avoid cache conflict. It should be noted 1 Size of a cache page = cache size / cache associativity. that, if both the arrays have been re-layouted in a previous execution of the while loop, we do not attempt to relayout either of them since their layouts have been determined to avoid the conflicts whose conflict number is larger than the current one. The algorithm terminates when we cannot find a pair of arrays between which the conflict number is larger than the given threshold T. In our experiments, we set T to the average number of conflicts across all pairs of arrays.

Experimental Evaluation

In our experiments, we used six applications (tasks). A common characteristic of these applications is that they are all array-based embedded codes from the domain of image/video processing. The brief descriptions of these applications are given in Table 1. The numbers of processes of these benchmarks (tasks) vary between 9 and 37. We evaluate our scheduling approach using these applications in two different ways. First, we consider each application in isolation, i.e., we perform scheduling, assuming that only the processes of the application in question are running on the MPSoC. Then, we schedule processes from multiple applications when they execute concurrently.

We performed our experiments using Simics tool [START_REF]Virtutech Simics: a full system simulator[END_REF]. Simics runs operating systems, device drivers, and firmware in addition to the application code. This means that the applications executed on Simics will behave as they would on a real system, while executing just the userlevel application code will not reveal all properties of the system. In this work, we experimented with different schedulers implemented on top of Simics. The default simulation parameters used in the experiments are given in Table 2.

We tested four different process scheduling strategies: 1. Random Scheduling (RS): In this strategy, each process is assigned to an available core randomly without any concern for data reuse. Once scheduled, each process runs to completion (unless it needs to synchronize with another process).

2. Round-Robin Scheduling (RRS): This is a preemptive FCFS (first-come-first served) scheduling. Basically, we maintain a ready queue for processes (as FIFO). New processes are added to the tail of the queue, and the scheduler selects the first process from the ready queue, sets a timer, and schedules it. When the timer is off, the process relinquishes the core voluntarily, and the next one in the queue is scheduled. Note that all cores take their processes from a common ready queue.

3. Locality-Aware Scheduling without Data Mapping (LS): This is the scheduling strategy discussed in this paper, except that it does not include the data mapping part discussed in Section 3.

4. Locality-Aware Scheduling with Data Mapping (LSM): This is similar to LS except that it also includes the data mapping phase explained in Section 3.

The graph in Figure 6 gives the execution times of our applications when they are scheduled in isolation. One can make two major observations from these results. First, our locality-aware scheduling strategy generates much better results than both RS and RRS. This is because, in this isolated execution case, processes executing at a given time are from the same application. As a consequence, they share a lot of data, i.e., data reuse among them is high, and this makes cache locality behavior extremely important. Since neither RS nor RRS does anything special to exploit data locality, they perform poorly compared to both LS and LSM. The second observation is that the difference between LS and LSM it not too great. This is mainly because of the fact that the data sharing between processes dominates the cache conflicts (as the processes are from the same application).

Figure 7 shows the execution times under different workloads. On the x-axis, |T| gives the number of tasks (applications) running on the MPSoC. Therefore, as we move along this axis from left to right we keep introducing more tasks to the system (i.e., generate more pressure). More specifically, when |T|=1, we have only (processes of) Med-Im04 running on the MPSoC; when |T|=2, we introduce MxM in addition to Med-Im04, and they execute concurrently; and so on. Therefore, the execution time in this case means the overall completion time of the applications executing concurrently. When we compare these results with those given in Figure 6, the most striking difference is that here there is a larger difference between LS and LSM. The main reason for this is that, since processes scheduled on the same core in this case can come from different applications (and since these applications do not share data among them), they can create too many conflict misses, most of which are eliminated by LSM but not LS.

Discussion of Related Work

The prior work on process scheduling in the embedded systems area include works targeting instruction and data caches. [START_REF] Wolfe | Software-based cache partitioning for real-time applications[END_REF] and [START_REF] Lee | Analysis of cache related preemption delay in fixedpriority preemptive scheduling[END_REF] present scheduling strategies for instruction caches that try to reduce the number of conflict misses. Li and Wolfe [START_REF] Li | A task-level hierarchical memory model for system synthesis of multiprocessors[END_REF] propose and evaluate a model for estimating the performance of multiple processes sharing a cache. More recently Kadayif et al [START_REF] Kadayif | Locality-conscious process scheduling in embedded systems[END_REF] and Kandemir et al [START_REF] Kandemir | Data space oriented scheduling in embedded systems[END_REF] propose locality-conscious scheduling strategies for data caches. The main difference between our work and these two studies is that we focus on an MPSoC based architecture instead of a single processor based system. Riveral and Tseng [START_REF] Rivera | Data transformations for eliminating conflict misses[END_REF] discuss techniques that minimize the number of conflict misses by transforming data layouts. Their work is focused on single processor environment. Our work is different from theirs in that the focus of our work is to minimize the cache misses among the data elements accessed by different processes in an embedded MPSoC based system. Carr et al [START_REF] Carr | Compiler optimizations for improving data locality[END_REF] propose a cost model that computes both temporal and spatial reuse of cache lines to find desirable loop restructurings. Bershad et al [START_REF] Bershad | Avoiding Conflict Misses Dynamically in Large Direct-Mapped Caches[END_REF] propose a scheme that uses a hardwarebased Cache Miss Lookaside (CML) buffer to detect cache conflicts by recording and summarizing a history of cache misses. Whenever a large number of conflict misses is detected, a software policy (within the operating system) is invoked to remove the conflicts by dynamically re-mapping pages. Kharbutli et al [START_REF] Kharbutli | Using prime numbers for cache indexing to eliminate conflict misses[END_REF] present an in-depth analysis on the performance degradation due to the pathological behavior of cache hashing functions in an architecture that uses cache rehashing to reduce conflict misses. Based on their analysis, they propose two hashing functions (prime modulo and prime displacement) that are resistant to pathological behavior and yet are able to eliminate the worst-case conflict behavior in the L2 cache.

Concluding Remarks and Future Research

Performance of applications executing on embedded MPSoCs depends strongly on their on-chip cache behavior. Significant gains are possible from both performance and power angles by being careful in scheduling processes on embedded cores in such a fashion that data reuse among successively scheduled processes (on the same core) is maximized. This paper presents an OS process scheduling strategy based on this idea, and evaluates its effectiveness using a suite of six embedded applications. Our results clearly emphasize the importance of cache-conscious process scheduling. This work can be extended in several directions. First, we plan to compare it to other OS scheduling strategies as well using our benchmarks. Second, we want to implement it within an embedded Linux environment and test it. Third, we want to explore the interactions between OS scheduling and compiler-driven techniques and identify the potential mechanisms through which these two can communicate.

Figure 1 .

 1 Figure 1. Examples of parallelizing tasks over eight processes.

Figure 2 .

 2 Figure 2. (a) Data sharings between different processes. (b) Mapping and scheduling of the processes with good data reuse. (c) Mapping and scheduling of the processes with poor data reuse. We assume four processor cores.

Figure 3 .Figure 4 .

 34 Figure 3. Locality-aware process scheduling algorithm

Figure 5 .

 5 Figure 5. The algorithm for selection of the arrays to belayouted

  A cache conflict is said to occur if two array elements, A[d 1 , d 2 ] and B[d 3 , d 4 ], map to the same cache line. This can be expressed more formally as: map(addr(A[d 1 , d 2 ])) = map(addr(B[d 3 , d 4 ]

  addr'(A[x, y]) = 2addr(A[x, y]) -addr(A[x, y]) mod (C/2) + b

Figure 6 .Figure 7 .

 67 Figure 6. Execution times when applications are executed in isolation.

Table 1 . Applications used in this study.

 1

	Applications	Brief
	(Task)	Description
	Med-Im04	medical image reconstruction
	MxM	triple matrix multiplication
	Radar	radar imaging
	Shape	pattern recognition and shape analysis
	Track	visual tracking control
	Usonic	feature-based object recognition

Table 2 . Default simulation parameters used in this study.

 2

	Parameter	Value
	Number of processors	8
	Data/instruction cache per processor	8KB, 2-way
	Cache access latency	2 cycle
	Off-chip memory access latency	75 cycles
	Processor speed	200 MHz

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Thilo Streichert
email: streichert@cs.fau.de

Christian Haubelt
email: haubelt@cs.fau.de

Jürgen Teich
email: teich@cs.fau.de

Distributed HW/SW-Partitioning for Embedded Reconfigurable Networks *

In this paper, we propose a distributed online HW/SWpartitioning strategy for increasing fault tolerance in HW/SW-reconfigurable networked systems.

Introduction

Distributed and adaptive embedded hardware platforms are becoming more and more important for applications in the area of automotive, body area networks, ambient intelligence, etc. In order to be able to cope with different timevariant application demands or node defects, these systems must be adaptive and be able to react to unforeseen changing requirements. Due to the possibilities provided by the currently available technology, functionality implemented in hardware (HW) or software (SW) can be dynamically assigned to resources in the network.

We therefore propose a distributed two-step strategy for online HW/SW-partitioning, that consists of a HW/SW bipartitioning heuristic and a dynamic load balancing algorithm. All related work discusses either offline HW/SW partitioning algorithms [START_REF] López-Vallejo | On the Hardware-Software Partitioning Problem: System Modeling and Partitioning Techniques[END_REF] or load balancing approaches only but do not consider the online HW/SW partitioning problem. One publication [START_REF] Lysecky | A Configurable Logic Architecture for Dynamic Hardware/Software Partitioning[END_REF] in this field describes load balancing on a platform consisting of a microprocessor and reconfigurable HW, but without an extension for networked systems.

Problem Definition

There are two possible scenarios where a (re)partitioning of processes in a reconfigurable network becomes important or even necessary: The first is the possible failure of a computational node at a certain time. The second is for optimality reasons in case of changes of the computational demands of the running application due to either finishing tasks or yet unknown arriving tasks.

The HW/SW partitioning problem is defined as an assignment of each task to a resource as well as an indication whether the task is implemented in HW or SW. Here, we propose a distributed algorithm which solves this problem at runtime, leading to an online HW/SW partitioning problem. In the following, we will call the set of active resources at time t the allocation α(t) and the assignment of tasks to resources the binding β(t). Our approach to online HW/SW partitioning tries to find a binding that optimizes the current binding β(t) with respect to the following objectives:

1. load balance in the network: With this objective to be minimized, the load in the network is balanced between the nodes, whereas HW-and SW-tasks are treated separately:

max(max(w S i ) -min(w S i ), max(w H i ) -min(w H i ))∀i = 1..|N | with w S
i being the SW load on node i and w H i being the HW load on node i. |N | is the number of resource nodes.

2. hardware/software load balance: The load between the HW-and SW-resources has to be balanced, i.e., we minimize

|N | i=1 w S i - |N | i=1 w H i .

minimization of total load:

To avoid unnecessary high computational load in the network, we minimize

|N | i=1 w S i + w H i .
With these objectives, our online HW/SW-partitioning algorithm will then create most likely task assignments that enable a good load reserve on each active node which is important for achieving fast repair times in case of unknown future node failures. In this paper, we assume constant workload demands on each node, i.e., w S (p) = w S i (p)∀i = 1..|N | for a given process p. The SW workload w S i (p) on node n i of process p is the fraction of execution time to its period and the HW workload w H i (p) is defined as the fraction of required area and maximal available area, resp. configurable logic elements in case of FPGA implementations.

Online Hardware/Software Partitioning

In figure 1 we present our methodology for handling unexpected events. The goal of the fast repair phase is to reestablish the functionality of the network. This part is not covered in this paper. The second phase, the online HW/SW partitioning tries to find an optimal binding of processes to nodes so to optimize the above three objectives. This is achieved by an online HW/SW partitioning strategy consisting of a load balancing and a bi-partitioning phase. While the load balancing step tries to find good solutions with respect to the first objective, the local bi-partitioning tries to optimize the second and third objective. Note that this partitioning will run in a distributed and decentralized manner in the network for reasons of fault tolerance.

Load Balancing

For the load balancing, we apply a diffusion based algorithm which moves load entities along the links in the network to other nodes. Characteristic to a diffusion-based algorithm, introduced first by Cybenko [START_REF] Cybenko | Dynamic Load Balancing for Distributed Memory Multiprocessors[END_REF], is that iteratively, each node is allowed to move any size of load to each of its neighbors. Communication is only allowed along edges in the network. Although diffusion algorithms have received a considerable amount of attention throughout the last couple of years, see, e.g., [START_REF] Elsässer | Optimal and Alternating-Direction Loadbalancing Schemes[END_REF], they have two negative characteristica: They work with real-valued portions of load and they have alternating behaviour. Therefore, we proposed a diffusion scheme that migrates only full tasks between nodes. For this discrete diffusion algorithm we have proven that it does not exceed optimality constraints concerning the amount of migrated tasks in the continuous case and we are able to show theoretically maximal deviations with respect to the quality of the load balance, cf. [START_REF] Streichert | Online HW/SW-Partitioning in Networked Embedded Systems[END_REF].

Local Bi-Partitioning

The bi-partitioning algorithm first determines the load ratio between a HW and a SW implementation for each process: w H (p i )/w S (p i ). According to this ratio, the algorithm selects one task and implements it either in HW or SW. Due to such a local strategy, we can guarantee that the total load will be minimized, but to reach an optimal HW/SW balance, we calculate the total SW load and the total HW load on each node. If the total HW load is less than the total SW load, the algorithm selects a task which will be implemented in HW, and the other way round. Due to these competing objectives, tasks with a ratio larger than one can be assigned to hardware and tasks with a ratio less than one are assigned to software. In order to undo this suboptimal task assignment, we migrate these tasks at first in the diffusion step.

Experimental Evaluation

In the following evaluation, we are comparing the results obtained with our distributed approach with the results of a methodology which is based on an Evolutionary Algorithm In the first experiment, we are starting from a network which is in an optimal state, such that all tasks are implemented optimally according to all objectives. Now, we assume that new SW-tasks arrive on one node. Starting from this state, Figure 2a) shows how the algorithm performs for different load values. In the second experiment, the initial binding of tasks and load sizes were determined randomly. For this case, which is comparable to an initialization phase of a network, we generated process sets with 10 to 1000 processes, see Figure 2b). In this figure, we can clearly see that the algorithm improves the distribution of tasks already with the first iteration leading to the best improvement. Note that Figure 2 presents the distance after each bi-partition and diffusion step. We can see in Figure 2 that the failure of one node causes a high normalized error. Interestingly, the algorithm finds global optima but due to local information our online algorithm cannot decide when it finds a global optimum.

Figure 1 .

 1 Figure 1. Phases of HW/SW partitioning

  The run time complexity of this algorithm is O(|P j |log 2 (|P i | + |P j |)), where |P i | is the number of processes bound onto node n i and |P j | is the number of new processes on the same node.

Figure 2 .

 2 Figure 2. Shown is the distance d(s) to a reference solution over the iteration of the HW/SWpartitioner. a) Optimal partitioned tasks with a certain load on a node. b) Randomly distributed tasks in a network (EA) and possesses global knowledge, i.e., a centralized optimization strategy is used. Using the EA, we determine a set R of reference solutions and calculate the shortest normalized distance d(s) from the solution s found by the online algorithm to any reference solution r ∈ R.In the first experiment, we are starting from a network which is in an optimal state, such that all tasks are implemented optimally according to all objectives. Now, we assume that new SW-tasks arrive on one node. Starting from this state, Figure2a) shows how the algorithm performs for different load values. In the second experiment, the initial binding of tasks and load sizes were determined randomly. For this case, which is comparable to an initialization phase of a network, we generated process sets with 10 to 1000 processes, see Figure2b). In this figure, we can clearly see that the algorithm improves the distribution of tasks already with the first iteration leading to the best improvement. Note that Figure2presents the distance after each bi-partition and diffusion step. We can see in Figure2that the failure of one node causes a high normalized error. Interestingly, the algorithm finds global optima but due to local information our online algorithm cannot decide when it finds a global optimum.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Conclusions and Future Work

In this paper, we have presented a first approach to online HW/SW partitioning in networked embedded systems. The proposed two-level algorithm increases the load reserves on each node in order to compensate node defects. In the future work, we will try to find a sufficient termination criteria and will investigate real-time capabilities.

* Supported in part by the German Science Foundation (DFG) under contract TE 163/10-1, SPP 1148 (Rekonfigurierbare Rechensysteme)


W.-L Hung
email: whung@cse.psu.edu

Y Xie

N Vijaykrishnan

M Kandemir
email: kandemir@cse.psu.edu

M J Irwin

Thermal-Aware Task Allocation and Scheduling for Embedded Systems

  L'archive ouverte pluridisciplinaire

Introduction

Traditional allocation and scheduling routines use performance or power as the design metric in Hardware/software co-synthesis [START_REF] Xie | Allocation and scheduling of conditional task graph in hardware/software co-synthesis[END_REF]. As technology scales, temperature in modern high-performance VLSI circuits has moved up dramatically due to smaller feature sizes, higher packing densities and rising power consumptions. Temperature affects not only the reliability but also the performance, power, and cost of the embedded system. At sufficiently high temperatures, many failure mechanisms (such as electromigration and stress migration) are significantly accelerated, resulting in reduced system reliability; interconnect delay increases and MOS current drive capability decreases as chip temperature increases. The leakage power increases exponentially with the temperature increase; finally, the cost of cooling a hot chip increases as the hot spot temperature goes up.

Power-aware design alone is not able to address the temperature challenge, and many low-power techniques have insufficient impact on chip temperature because they do not directly target the spatial and temporal behavior of the operating temperature. Therefore, even though it is related to the power-aware design area, thermal-aware design itself is a distinct and important research area. In this paper, we investigate both power-aware and thermal-aware approaches for task allocation and scheduling. The experimental results show that thermal-aware approach outperforms the power-aware schemes in terms of maximal and average temperature reductions.

Tasks Allocation and Scheduling

For either platform-based or customized architecture, the task Allocation and Scheduling Procedures (ASP) is critical to get good solutions. The selection of PEs and the assignment of tasks This work was supported in part by grants from PDG, NSF CAREER Awards 0093082 and 0093085 and GSRC. are both guided by ASP. Our task allocation and scheduling procedure is similar to the one proposed by Xie and Wolf [START_REF] Xie | Allocation and scheduling of conditional task graph in hardware/software co-synthesis[END_REF]. The ASP takes the task graph and architecture (either predefined platform architecture or a customized architecture generated via co-synthesis) and a target library as input, and generates the task mapping and scheduling on the target architecture. The target library stores the worst case power consumptions (WCPC) and worst case execution times (WCET) for a task executed on different PEs.

The static criticality (SC) for each task is calculated as the maximum distance from current task to the end task in a task graph. This is similar to the priority ordering in some list schedulers. The dynamic criticality (DC) calculation is based on four different factors and will be defined in section 2.1.

The traditional allocation and scheduling algorithm is effective on finding the task mapping and scheduling that satisfy the deadline requirement. However, it neglects the temperature impacts during the process. To account for this problem, we introduce power/energy aware ASP and thermal-aware ASP.

Power-aware allocation and scheduling

Since temperature is closely related to the power density, in power-aware allocation and scheduling, the power/energy factor is involved in the process of calculating dynamic criticality. Therefore, the DC equation is defined as follows:

Pow task ready PE avl max PE task WCET task SC PE task DC i j j i i j i - - - = ) _ , _ . ( ) , ( ) ( ) , (
The first term stands for the static criticality of the task i ; the second term retrieves the WCET of this task i executed on PE j from the technology library, and the third term takes the maximum of PE j 's available time and task i 's ready time. The last term (Pow) captures the effect of power/energy which can be interpreted by the following three heuristics: Heuristic 1: minimize power consumption of current task Heuristic 2: minimize cumulative average power of processing element Heuristic 3: minimize energy of current task

Thermal-aware allocation and scheduling

The proposed thermal-aware ASP addresses the thermal issue by taking the temperature into consideration. The temperature of an embedded system depends on the power consumption of each processing element (PE), its dimension and relative location on the embedded system platform. The thermal modeling tool, HotSpot [START_REF] Skadron | Control-Theoretic Techniques and Thermal-RC Modeling for Accurate and Localized Dynamic Thermal Management[END_REF], is used to extract the temperature profile. Hotspot provides a simple compact model, where the heat dissipation within each PE and the heat flow among PEs are accounted for. HotSpot takes a system floorplanning and the power consumption for each function block as input, and generates accurate temperature estimation for each block.

For the thermal-aware ASP, we first pass the cumulating power consumptions of each PE along with the consuming power incurred by current scheduled task to the HotSpot. The temperatures returned from the HotSpot are averaged and then be used in calculating dynamic criticality as defined before. The newly added Avg._Temp substitutes out the Pow term and sets the goal of minimization of the average temperature. The goal also implies the reduction on the maximal temperature.

The flow of our thermal-aware co-synthesis framework is shown in Figure 1.a. The allocation and scheduling procedure executes and then activates the thermal-aware floorplanning [START_REF] Hung | Thermal-Aware Floorplanning Using Genetic Algorithms[END_REF] when considering assignment of a task on one specific PE. The HotSpot tool interacts with the floorplanning procedure to provide information of temperature. For the platform-based thermal-aware design, the target architecture and the task graph are given, and the HotSpot is activated by the modified ASP with thermal inquires. This flow is depicted in Figure 1

Experimental Results

The first experiment we conduct is to compare the temperature differences from different power heuristics when using the co-synthesis to decide the selection of PEs and when using the platform-based architecture (using four identical PEs). The experimental results are shown in Table 1. The three columns under the co-synthesis are the results of the traditional co-synthesis work, while the other three columns represent the results from the platform-based target architecture.

The very first row out of four rows' groups indicates the characteristics of each benchmark and is the baseline case that does not take the power into consideration. The following three rows represent three power heuristics. As can be seen from the table, when considering power only, the third power heuristic outperforms the other two heuristics and the baseline approach. This result indicates that minimizing the energy of a task executed on one specific PE achieves the best temperature result among all three heuristics. Thus, the third power heuristic will be used in the following experiments.

The second experiment is to demonstrate the effectiveness of our thermal-aware approach in terms of lowering the peak and the average temperatures. We take the best results of customized architecture and platform-based architecture from the first experiment for comparison. The power-aware and thermalaware customized architecture comparison is shown in Table 2. From the results, the customized architecture with thermalaware approach demonstrates that it can effectively reduce the total average temperature reduction by 10.9 o C and 6.95 o C for the maximal and the average, respectively. This result indicates that observing the average temperature of all using PEs while doing task scheduling is beneficial to control the temperature of an embedded system. As for the platform-based architecture, the proposed thermalaware approach outperforms the power-aware approach in both temperature attempts. As shown in Table 3, under thermalaware approach, both of the maximal and average temperatures are lower than those of in the corresponding power-aware approach and approximately by 9.75 o C and 5.02 o C, respectively. The results from Table 2 and 3 indicate that with the platform-based architecture, the thermal ASP can balance the workloads of all PEs, and thus delivery a lower peak and average temperatures task mapping than that of in customized architecture.

Figure 1 .

 1 Figure 1. The flows of the thermal-aware co-synthesis framework and thermal-aware platform-based system design

Table 1 . The comparisons of different power heuristics under co- synthesis arch. and platform-based target arch.

 1

	name/task/edge/		co-synthesis		Platform-based Arch.
	deadline	Total	Max	Avg	Total	Max	Avg
		Pow.	Temp.	Temp.	Pow.	Temp.	Temp.

Table 2 . The temperature comparisons of the power-aware and the thermal-aware approaches on co-synthesis architecture.

 2

		Power-aware co-synthesis	Thermal-aware co-synthesis
		Total	Max	Avg	Total	Max	Avg
	Bechmark	Pow.	Temp.	Temp	Pow.	Temp.	Temp.
	Bm1	15.56	113.29	104.49	12.48	87.11	86.13
	Bm2	28.27	112.82	105.42	24.64	106.38	99.84
	Bm3	28.2	109.96	100.15	26.51	102.08	96.28
	Bm4	43.34	118.68	109.87	42.41	106.32	102.48

Table 3 . The temperature comparisons of the power-aware and the thermal-aware approaches on platform-based architecture.

 3

		Power-aware platform Arch.	Thermal-aware platform Arch.
		Total	Max	Avg	Total	Max	Avg
	Bechmark	Pow.	Temp.	Temp	Pow.	Temp.	Temp.
	Bm1	10.40	85.88	75.58	6.37	65.71	61.16
	Bm2	24.09	106.63	97.40	22.37	96.33	93.47
	Bm3	25.20	103.95	94.69	24.98	103.03	94.59
	Bm4	41.64	100.42	89.24	38.54	94.85	85.76

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE