Moazzam Islam Tiwana
email: moazzamislam.tiwana@orange-ftgroup.com

Zwi Altman
email: zwi.altman@orange-ftgroup.com

Berna Sayrac
email: berna.sayrac@orange-ftgroup.com

Enhancing RRM optimization using a priori knowledge for automated troubleshooting

Keywords: ICIC, Statistical learning, logistic regression, automated troubleshooting, LTE

The paper presents a methodology that combines statistical learning with constraint optimization by locally optimizing Radio Resource Management (RRM) or system parameters of poorly performing cells in an iterative manner. The statistical learning technique used is Logistic Regression (LR) which is applied on the data in the form of RRM-KPI (Key Performance Indicator) pairs. LR extracts closed form (functional) relations, known as the model, between KPIs and RRM parameters. This model is then processed by an optimization engine which proposes a new RRM parameter value. The RRM parameter value is reinserted in the network/simulator to generate corresponding KPI vector constituting generated RRM-KPI pair. First, only the a priori RRM-KPI pairs which are based upon the a priori model information are used for the model extraction. Then, as the optimization iterations progress, the generated pairs are given more importance in model extraction and the model is iteratively refined. The use of the a priori knowledge has the advantage of avoiding wrong initial models due to noisy data, allows much faster convergence and makes it more suitable for the off-line implementation. The proposed method is applied to troubleshoot an Inter-Cell Interference Coordination (ICIC) process in a LTE network which is based on soft-frequency reuse scheme.

I. INTRODUCTION

Next generation radio access networks (RAN) aim at increasing bandwidth for future services and applications with high quality of service (QoS) provisioning. The RAN landscape will become more and more heterogeneous with coexisting and co-operating technologies and deployment scenarios (macro, micro, pico and femto cell structures). In this context network management becomes strategic for operators that need to assure efficient use of available resources while limiting the cost of operation.

Troubleshooting is a central activity of network management. It comprises of three functionalities [START_REF] Barco | System for automatic diagnosis in cellular networks based on performance indicators[END_REF][2]:

• fault detection, i.e. detecting failures or poor performance as soon as they occur; • fault-diagnosis, i.e. determining the cause of failure or of poor performance, and • fault recovery or healing, i.e. repairing the problem. Efficient troubleshooting allows fast reaction to problems, reduction of infrastructure equipment down-time and period of poor QoS provisioning. Hence troubleshooting is an important activity for the operator, and has a direct impact on churn reduction and on operator revenues. This paper focuses on automated fault recovery or automated healing. It is assumed that the fault cause has been diagnosed, and is related to bad RRM parameter settings. The automated healing is of local character, and aims at adjusting the RRM parameter of a base station (BS) or eNodeB (eNB) using Key Performance Indicators (KPI) from the eNB and its neighbours. Previous works have studied the problem of local type (or steered) optimization (see for example [START_REF] Ben Jamaa | Steered Optimization Strategy for Automatic Cell Planning of UMTS Networks[END_REF], [START_REF] Ben Jamaa | Quality indicator matrices and their contribution to WCDMA network design[END_REF]). These works propose solutions based on the use of network simulator or automatic cell planning tool that combines the interference matrix with optimization heuristics. In certain cases, solutions fully based on network measurements are required. Such solutions are carried out off-line using data from the Operation and Management Center (OMC) or from capture tools.

In a typical troubleshooting process, the optimization expert analyzes KPIs and then proposes a new RRM parameter which is applied to the problematic BS. The BS operates with the new parameter during a period long enough, typically a day, to have statistically significant results that allow to assess the BS performance. This optimization process is reiterated during several days, typically between one to two weeks. Hence a (near) optimal solution should be reached in a small number of iterations. The difficulty for devising automated healing algorithms are twofold. First, optimization heuristics often require hundreds of iterations and more time to converge. Second, measured counters and KPIs are inherently noisy. Noise can originate from limited measurement accuracy, but also from traffic fluctuations, varying propagation conditions etc. The effect of RRM parameter modification on KPIs can be masked partially by unobserved effects thus introducing uncertainty in the relation between KPIs and RRM parameters.

To overcome the above two difficulties, a novel approach for automated troubleshooting based on statistical learning has been recently introduced ([5], [START_REF] Tiwana | Statistical approach for automated troubleshooting: application to LTE interference mitigation[END_REF]), and denoted in [START_REF] Tiwana | Statistical approach for automated troubleshooting: application to LTE interference mitigation[END_REF] as Statistical Learning Automated Healing (SLAH). This approach assumes that the model describing the functional relations between KPIs and RRM parameters is simple (i.e. is not described by a multi-modal function) and can be described using statistical regressions derived from the measured data. In [START_REF] Tiwana | Troubleshooting of 3G LTE mobility parameters using iterative statistical model refinement[END_REF], linear regression has been assumed whereas in [START_REF] Tiwana | Statistical approach for automated troubleshooting: application to LTE interference mitigation[END_REF], Logistic Regression (LR) has been used. The merit of logistic regression is that it can account for saturation effects that often appear in communication network KPIs such as blocking WNC3 2010 rate, dropping rate etc. The automated healing algorithm is iterative. In each iteration, a new data point comprising of a RRM parameter and a corresponding KPI vector is introduced. The data point is used to update the statistical model and improve its precision. Then the updated statistical model is introduced into the optimization engine to calculate the next RRM parameter. Hence the optimization algorithm does not directly process data points but rather closed form functions in the form of regressions, allowing the model to converge rapidly with a small number of iterations.

The purpose of the present paper is the following. The initial estimated model is very sensitive to noise because it is derived using very few data points. The first data points used by the SLAH may mislead the algorithm due to the noisy data and produce a bad initial statistical model (e.g. KPIs with wrong tendencies / slopes). As a result, several additional iterations are required for the SLAH algorithm to converge. It is recalled that due to operational constraints, the automated healing needs to converge in a few days, namely with a few number of iterations. Furthermore, we need to obtain the initial model behaviour over a wide range of RRM parameter values. So, we need to calculate the KPIs corresponding to RRM parameter values that may not be very practical for an operating network. Hence, the purpose of this paper is to show how can wrong statistical model be avoided due to noisy data in the first iterations of the SLAH algorithm. To this end, a priori knowledge is introduced. A priori knowledge is presented in the form of a small set of data points, typically between three to five, that produces an acceptable statistical model (regression functions), with the expected tendencies according to expert knowledge. Such data points can be obtained in different manners: from a database produced by other BSs using previous troubleshooting experience; from a network simulator; or simply from data points produced artificially by the network expert. After the initial model estimation and with the progression of optimization iterations, the a priori data points are assigned lesser and lesser weight in the model estimation as compared to generated data points i.e., data points generated by network/simulator. The incorporation of the a priori knowledge to the logistic regression and to the full SLAH algorithm, in order to achieve fast convergence and robustness, is presented. The method is applied to the problem of troubleshooting of Inter-Cell Interference Coordination (ICIC) of a LTE network.

Throughout the paper, the terms eNB and base station can be used interchangeably. Similarly, the terms mobile and user have the same meaning. The rest of the paper is organized as follows: Section II presents the system model for automated healing. The incorporation of the a priori knowledge to the automated healing algorithm is described in Section III. The Section IV explains the ICIC System Model. The adaptation of the SLAH to the problem of ICIC in a LTE network is summarized in Section V, followed by numerical results in Section VI. Section VII concludes the paper.

II. SYSTEM MODEL FOR AUTOMATED HEALING

This section describes the system model for the automated healing. It is assumed that the initial two steps of the troubleshooting process, namely fault detection and fault diagnosis, have already been done. Let's suppose that the fault cause has been diagnosed as a RRM parameter whose value has degraded the performance of the eNodeB (eNB). The purpose of the SLAH algorithm is to devise a robust mechanism which using local information from an eNB and its neighbors, can iteratively optimize the value of the RRM parameter that has caused the degraded performance of the cell. The block diagram of the proposed algorithm is presented in Figure 1

Statistical Learning block

The Statistical Learning block processes the data comprising RRM-KPIs pairs to extract closed form (functional) relations relating the KPIs to the RRM parameters. These functional relations constitute the statistical model or for brevity, the Model.

In the case of the a priori knowledge incorporation, the Model is estimated from the data points, taking into account the weight assigned to each point according to its importance in the model estimation process.

Optimization block

The Optimization block calculates the optimal RRM value using the current statistical model. It minimizes a cost function of certain KPIs under constraints imposed on other KPIs. The automated healing model assumes that the KPIs are well behaved functions, namely they are not multi-modal functions of the RRM parameter. This assumption allows to capture the functional form of the KPIs using regression techniques. The automated healing process is iterative. At each new iteration, on the average, the model precision improves and is used by the optimization block to find a better value for the RRM parameter. In the following, the Statistical Learning and the Optimization blocks are described in detail.

A. Statistical Learning

The statistical learning approach used in the automatedhealing is based on Logistic Regression (LR) [START_REF] Montgomery | Introduction to Linear Regression Analysis[END_REF] [START_REF] Hosmer | Applied Logistic Regression[END_REF]. The LR Model belongs to a category of models known as the Generalized Linear Models (GLM) [START_REF] Mccullagh | Generalized Linear Models, Second Edition[END_REF]. The LR establishes the statistical model by extracting the functional relations between the KPIs and the RRM parameter. LR fits the data into the functional form of logistic f unction denoted as f log

f log (z) = 1 1 + exp -z (1)
where z can vary from -∞ to ∞ and f log (z) from 0 to 1 (see Figure 2). One can see from Figure 2 that f log (z) can describe saturation effects at its extremities as often encountered in KPIs in communication networks. In our work, the KPI is a dependent variable denoted as y and the RRM parameter is an explanatory variable denoted as x. The KPIs chosen in our work are mean Block Call Rate (BCR) of mobiles accessing an eNB and mean File Transfer Time (FTT) of mobiles attached to an eNB over full simulation period for a given value of x.

Let y m,i denote the i th sample value of the m th dependent variable y m (i.e. the m th KPI) corresponding to the i th sample value x i of the explanatory variable x (i.e. the RRM parameter). LR models y m,i as follows:

y m,i = f log (η m,i ) + i (2)
where η m,i = x i β m , given that

x i = [1 x i ] and β m = [β m,0 β m,1 ] T . η m,i
is the linear predictor representing the contribution of the explanatory variable sample x i , i is the residual error and βs are the regression coefficients whose values are estimated using maximum likelihood estimation as described in Section III. Let there be n sample values for y m corresponding to n values of x. In order to write (2) in the matrix notation, let

Y m = [y m,1 y m,2 ..y m,i .. y m,n ] T and X = [x 1 x 2 ..x i .. x n ]
T . Hence, we may write

Y m = f log (Xβ m ) + Y m = f log (η m ) + Y m = Ŷm + where Ŷm = f log (Xβ m ) (3)
Here, Ŷm represents the estimated Y m using LR. It is noted that the dependent variables in the LR are between 0 and 1. Hence, Y m is normalized between 0 and 1 before the application of LR. The calculated Ŷm values can be subsequently denormalized.

It follows from (3) that functional relation between ŷm i.e., y m estimated by LR, and x can be written as

ŷm = f log (x β m ) (4)
where x = [1 x].

B. Optimization

The aim of the optimization problem is to determine x i.e., the value for a RRM parameter x that minimizes a cost function of a set of KPIs denoted as the optimization set A o , subject to constraints on a second set of KPIs denoted as the constraint set A c . The cost function U is given as

U = m∈Ao w m ŷm (5)
where

• ŷm has the functional relation form as in (4).

• w m is the weight given to ŷm . The optimization problem is formulated as follows:

x = argmin x U (x) (6) subject to ŷh (x) < th h ∀ h ∈ A c
where th h is the threshold for ŷh .

III. A PRIORI KNOWLEDGE INCORPORATION

If we have the a priori knowledge about the expected behaviour of the model in the form of a priori data points (RRM-KPI pairs), this knowledge can be incorporated into the troubleshooting algorithm to derive the initial model. However, the a priori information may not be exact and can be erroneous because of scaling and translation errors w.r.t functional relations in the exact model. Therefore, as the iterations of the troubleshooting process start and progress, the newly generated data points are assigned more weight during the β m parameters estimation of the refined model calculation, as compared to the a priori data points. The process continues until the assigned weight to the initial a priori points becomes very small, hence, canceling out the effect of the initial a priori data points.

A priori knowledge incorporation into LR model is defined as follows: We follow the same notation for Y m and X as in previous section. The β m vector is estimated using Maximum likelihood Estimation (MLE). MLE endeavors to find the most "likely" values of the unknown distribution parameters that maximize the "likelihood function" for a given set of data sequence. The likelihood function is the probability for the occurrence of a sample sequence given that the probability density function of given data sequence for the the unknown parameters is known.

In order to find the maximum likelihood estimation of β m,b where b = {1, 2}, the derivative of the likelihood function l with respect to β m,b is taken [START_REF] Jong | Generalized Linear Models for Insurance Data[END_REF] and equated to 0:

∂l ∂β m,b = 0 (7)
After simplification as explained in [START_REF] Jong | Generalized Linear Models for Insurance Data[END_REF], we get the equation

∂l ∂β m,b = n i=1 (y m,i -ŷm,i )X ij var ŷm,i ∂ ŷm,i ∂η m,i = 0 for b = 1, 2 (8)
where η m,i = x i β m and ŷm,i = f log (η m,i ). Equation ( 8) can be expressed in the matrix notation as

X T V m (Y m -Ŷm ) = 0 (9)
V m is a diagonal matrix with

1 var ŷm,i ∂ ŷm,i ∂ηm,i as its i th diagonal element.
The matrix equation ( 9), contains equations which are nonlinear functions of the β m vector, denoted as f (β m ) = 0. Generally, it is not possible to solve f (β m ) explicitly in terms of β m . Hence, we solve the set of non-linear equations f (β m ) = 0 iteratively using the Newton-Raphson method. In this method, we take the linear approximation of f (β m ) in the neighbourhood of a point β t m using Taylor series as below:

f (β t m ) + ∂f (β t m ) ∂β T m (β m -β k m ) ( 10
)
where t is the iteration index. Equating [START_REF] Jong | Generalized Linear Models for Insurance Data[END_REF] to zero, we can approximate β t+1 m as follows:

β t+1 m = β t m - f (β t m ) ( ∂f (β t m ) ∂β T m ) (11)
Starting from an initial β 0 m and iteratively solving equation [START_REF] Nasri | Handover Adaptation for Dynamic Load Balancing in 3GPP Long Term Evolution Systems[END_REF], β m converges to a solution. The term -∂f (βm)

∂β T m = -∂ 2 l(βm) ∂βm∂β T m
is known as the Fisher information [START_REF] Jong | Generalized Linear Models for Insurance Data[END_REF] and is usually replaced by its expectation

I(β) = E ∂l(β m ) ∂β m ∂l(β m ) ∂β T m = E[X T V m (Y m -Ŷm ) X T V m (Y m -Ŷm ) T ] = X T W m X (12)
where

W m = V m (cov Y m )V m is a diagonal matrix with diagonal elements [W m ] ii = 1 var ŷm,i ( ∂ ŷm,i ∂ηi ) 2 = nt i * ŷm,i * (1 -ŷm,i ),
where nt m,i is the number of Bernoulli trials for the i th data point. Hence, [START_REF] Nasri | Handover Adaptation for Dynamic Load Balancing in 3GPP Long Term Evolution Systems[END_REF] becomes.

β t+1 m = β t m + (X T W t m X) -1 X T V t m (Y m -Ŷm t )
which takes the final form as

β t+1 m = S t m X T W t m z t m ( 13
)
where

S t m = (X T W t m X) -1 z t m = Xβ t m + U t m (Y m -Ŷm t ) and U t m = (W t m ) -1 V t m is a diagonal matrix with elements [U m ] t ii = ∂η t m,i ∂µ t m,i = 1 ŷt m,i (1-ŷ t m,i ) .
As mentioned earlier, during the a priori knowledge incorporation process, different weights are assigned to the a priori and generated data points. This can be achieved by using

H t m = W t m * A instead of W t m in (13)
where A is a diagonal weight matrix with A ii being the weight assigned to the i th data point. However, we don't alter U t m by replacing its W t m matrix because U t m only scales the residual error.

A priori diagonal weight matrix A calculation

Let N 1 be the number of the a priori data points in matrix Y . Initially, A ii = x% if y i is a generated data point and

A ii = 100-(n-N 1)x N 1
% if y i is an a priori data point. However, in the case (n -N 1)x exceeds a certain threshold W th , meaning that the generated data points have become more important than the a priori data points, we assign greater overall weight of W new % to newly generated data points. Hence, A ii = Wnew (n-N 1) % if y i is the generated data point and

A ii = 100-Wnew N 1
% if y i is an a priori data point. The complete, a priori knowledge incorporated, system model or β m estimation algorithm is given as

Initialization: 1. X ← values X ij 2. Y m ← values y m,i 3. z m ← f -1 log (y m ) 4. b m ← (X T X) -1 X T z m Repeat until b m converges: 5. η m ← Xb m 6. µ m ← f log (η m ) 7. [U m ] ii = 1 ŷm,i(1-ŷm,i) 8. [W m ] ii = nt m,i * ŷm,i * (1 -ŷm,i ) 9. z m ← Xb m + U m (Y m -Ŷm ) 10. S m ← (X T H m X) -1 11. b m ← S m X T H m z m End Repeat
b m is the matrix containing the estimated values of β m IV. ICIC SYSTEM MODEL Consider an ICIC scheme for downlink transmissions that combines two resource allocation mechanisms: Physical Resource Block (PRB) allocation to frequency subbands and coordinated power allocation. In the soft-reuse one scheme, the total available bandwidth is reused in all the cells while the transmitted power for a portion of the bandwidth of a cell can be adapted to resolve interference related QoS problems. Figure 3 presents the power-frequency allocation model in a seven adjacent cell layout.

The frequency band is divided into three disjoint subbands. One subband is allocated to mobiles with the worst signal quality and is denoted interchangeably as a protected band or as an edge band with transmit power P . A user with poor radio conditions is often situated at the cell edge, but could also be closer to the base station and experience deep shadow fading. The remaining two frequency subbands are denoted as centre bands with transmit power reduced by a factor α, namely αP . The interference produced by an eNB to its neighbours can be controlled by the parameter α of this eNB. The main interference in the system originates from eNB transmissions on the centre band (of centre cell users) which interfere with neighboring cell edge users utilizing their edge (protected) band. When an eNB strongly interferes with its neighbours, the ICIC mechanism allows to reduce the transmission power for the centre band.

Resource block allocation is performed based on a priority scheme for accessing the protected subbands. A quality metric q u is generated using pilot channel signal strengths

q u = P r su j =s P r ju + σ 2 z , (14)
where s stands for the serving eNB of user u, P r ju denotes the mean pilot power received by the user u of a signal transmitted by the eNB j, and σ 2 z is the noise power spectral density. q u is similar to the Signal to Interference plus Noise Radio (SINR) with the difference that in the present ICIC scheme, the data channels used to calculate the SINR are subject to power control. The q u metric is calculated for all users which are then sorted according to this metric. Users with the worst q u are allocated resources from the protected band and benefit from maximal transmission power of the eNB. When the protected subband is full, the resource block allocation continues from the centre band.

V. TROUBLESHOOTING MODEL

This section describes the adaptation of the SLAH to interference mitigation in a LTE network by locally optimizing the parameter α of the interfering eNBs. Denote by eN B c (c standing for central ) an eNB with degraded performance. It is assumed that the cause of the degraded performance has been diagnosed and is related to excess of interference from neighbouring eNBs. The direct neighbours from the first tier of eN B c are denoted by eN B j , j ∈ N S1(c) where N S1(c) is the set of neighbouring eNBs in first tier of eN B c . The subscript c of the set N S1(c) will be omitted hereafter for sake of brevity. The specificity of the interference mitigation use case is the following: to troubleshoot eN B c the parameters α j of eN B j , j ∈ N S1 , are updated and optimised, while α c of eN B c remains unchanged. We use the notion of coupling between eNB j and c which is expressed in terms of the interference that eN B j produces on eN B c and can be written in terms of the interference matrix element I cj [3][4]. Hence the bigger I cj , the stronger the coupling between the two eNBs. In this work, the matrix element I cj is equal to the sum of interferences perceived by the mobile attached to eN B c and generated by eN B j .

The use of the SLAH to jointly optimize all the elements of the vector (α j ), j ∈ N S1, is not a simple task. Denote by s, s ∈ N S1, the index of the eNB which is the most coupled with eN B c , namely s = argmax j (I cj ), s ∈ N S1. To reduce the complexity of the SLAH process and to enhance its scalability, we propose to adjust the α j parameter according to the degree of coupling between eN B j and eN B c . To this end, we define a functional relation between α s and α j , α j = g j (α s ), that accounts for the coupling mentioned above:

α j = g j (α s ) = α i + (1 -α s )(1 - I cj I cs ) ( 15
)
Two KPIs are utilized in the SLAH process: the File Transfer Time (FTT) for FTP traffic and the Block Call Rate (BCR).

The SLAH aims at minimizing the FTT for eN B c and of its direct neighbours while verifying constraints on BCR j , j ∈ c ∪ N S. We define the cost function for the optimization:

U = F T T c + j∈N S1 ω j F T T j ( 16
)
It is noted that F T T j is a function of α j and hence, via equation ( 15), of α s . F T T j also depends on the interference from its neighbouring eN B j . The weighting coefficients ω j depend on the relative contribution of I cj with respect to the sum on all eNBs in N S1 and are given by

ω j = I cj k∈N S1 I ck (17)
satisfying the condition j∈N S1 ω j = 1. The optimization problem can now be formulated as follows

α s = argmin α s U (α s ) ( 18
)
subject to

BCR j < BCR th ; j ∈ c ∪ N S1
BCR th is the threshold for BCR j . The F T T and BCR indicators in equations ( 16) and ( 18) are given in the form of the LR function (4) obtained using the LR. In the case, BCR j > BCR th for all values of α s , it is impossible to determine α s value that minimizes the cost function (18). In this case, instead of (18) our optimization objective is given as

α s = argmax α s (BCR c |(BCR c = BCR j )) ; j ∈ N S1 (19
) Here, α s signifies the value for which BCR of eN B c and the BCR of eN B j having worst BCR value, become equal. Denote a data point p j n as the vector

p j n = (α j , F T T j , BCR j ) n ; j ∈ c ∪ N S1 (20)
In the SLAH algorithm, α c remains fixed and is not subject to optimization; α j , j ∈ N S1, satisfies the equation (15); and the set of n data points for an eN B j , j ∈ c ∪ N S1, is denoted by P j n . During each optimization iteration one data point is added, hence, n also denotes optimization iteration index.

The SLAH algorithm is written below: Initialization: 1. Identify the most coupled eNB s with eNB c among the neighbours in N S1 2. For each eN B j , j ∈ c ∪ N S1, choose an initial set of n data points P j n according to a priori information 3. Assign equal weight to all the diagonal elements of A. Repeat until convergence: 4. For each eN B j , compute statistical model using LR for F T T and BCR using the corresponding data points in P j n 6. Compute a new vector (α j ), j ∈ N S1 (using equations (15) and (18) or (19)) 7. Apply (α j ) in the network/simulator and observe (F T T j ) and (BCR j ), j ∈ c ∪ N S1. Compute new data point p j n+1 (equation (20)) 8. Update P j n+1 : P j n+1 = P j n ∪ p j n+1 9. n=n+1 10. calculate A End Repeat

VI. ICIC TROUBLESHOOTING USE CASE

A. Simulation Scenario

A LTE network comprising 45 eNBs in a dense urban environment is depicted in Figure 4. Downlink transmissions are considered here. The simulation parameters are listed in Table I. A MATLAB LTE simulator described in [START_REF] Nasri | Handover Adaptation for Dynamic Load Balancing in 3GPP Long Term Evolution Systems[END_REF] has been used. The simulator performs correlated Monte Carlo snapshots with a time resolution of a second to account for the time evolution of the network. The principles of a semidynamic simulator are described in [START_REF] Samhat | Fourestie: Semi-dynamic simulator for large scale heterogeneous wireless networks[END_REF].

For each new value of α the simulator runs for 2500 time steps (seconds) to allow the convergence of the processed KPIs. The BCR and FTT KPIs used by the SLAH algorithm are averaged at an interval varying from 500 to 2500 seconds while discarding the first heating time samples. It is noted that for a given traffic demand, the BCR provides a capacity indicator while the FTT is more related to the user perceived QoS. The interference matrix elements used in equations ( 15) and ( 17) are calculated once for the reference solution (see paragraph below) during a longer time interval varying from 500 to 7000 seconds to achieve higher accuracy.

Reference Solution: An optimal default value for α is chosen as 0.5 for all eNBs in the network and will serve as the reference (default) solution. This reference solution is chosen according to the results in [START_REF] Tiwana | Statistical approach for automated troubleshooting: application to LTE interference mitigation[END_REF] and will be used as a starting point for the automated healing process. The default α value is determined by simultaneously varying the α of all eNBs, uniformly from 0.0125 to 1, in the steps of 0.0125 and assessing the network performance in terms of mean BCR and mean FTT. In the α interval from 0.5 to 0.7 the mean BCR and mean FTT have minimum values. The value of α = 0.5 is selected due to the smaller inter-cellular interference and the minimum energy consumption in the network.

B. Troubleshooting Scenario

A problematic eNB with the worst performance in the reference network of Figure 4, namely eN B c=13 , is selected for troubleshooting using the SLAH algorithm. The eN B j , where j ∈ N S1 = {14, 15, 22, 23, 43, 45}, is one of the six first tier geographical neighbours of eN B c=13 . It is recalled that the SLAH modifies the α parameters of eN B j while leaving unchanged α c which is fixed to the reference default value of 0.

C. A priori knowledge assumption

As mentioned earlier, the a priori data points can be obtained from a data base of eNBs, from the network or produced artificially by the network expert. The a priori knowledge for an eNB is given as a set of KPI curves used by the SLAH algorithm. Extensive numerical experimentations have shown that the important features of the a priori curves are given by their tendency, namely the monotonous increasing or decreasing behaviour, following a typical behaviour of the KPI. It is noted that the effectiveness of the SLAH method empowered by the a priori knowledge is little affected by the amplitude of the a priori KPI curves, rendering more efficient the troubleshooting process. The same holds for small variations in the curves' shapes, as long as the correct monotonous property is used. In the troubleshooting scenario analyzed in this section, the a priori KPI curves have been taken from a different scenario with different eNBs studied in [START_REF] Tiwana | Statistical approach for automated troubleshooting: application to LTE interference mitigation[END_REF], as shown in Figures 5 and6 for BCR and FTT KPIs respectively. The four a priori data points from which these a priori curves can be reconstructed are given as in Table II. Here BCR neigh and F T T neigh denote the a priori curves used for each neighbour in N S1. The matrix A is recalculated before each optimization iteration. Let n be the number of data points at each optimization iteration. Initially, A ii = x% = 20% is the weight assigned to each generated data point and the weight assigned to each a priori data point is A ii = 100-(n-4)20 4 %. However, when total weight (n -4)x assigned to the generated data points exceeds W th = 75, this means that generated data points have become more important than a priori data points. Hence, the total overall weight of W new = 90% is assigned to the generated data points. Hence, the weight of A ii = 90 n-4 % is assigned to each generated data point. While weight of A ii = 100-90 4 % is assigned to each a priori data point.

D. Results

Table III shows the convergence of α s=45 after the application of the a priori incorporated SLAH. The initial value of α s = 0.55 is generated using the a priori knowledge. After 4 iterations of the troubleshooting algorithm, α s converges to value of α s = 0.59. Figure 7 compares the convergence of α s in the case of a priori incorporated (continuous line) SLAH with the one not using the a priori information (dashed line). It is apparent that less number of iterations are required in the former case as we don't need to do iterations in order to generate the data points for initial model estimation. Furthermore, this initial model is very sensitive to noise as it is derived from few points. Hence, using the noise free a priori data points for initial model estimation has resulted in a smoother and quicker convergence, as is evident from the blue curve. It is also apparent from Figure 7 that in the abscence of the a priori knowledge, the values of α s =0.05 and 0.95 may be very low or high for an operating network. The data points corresponding to these α s values are generated in order to get the exact behaviour of the initial model over whole α s range.

Figure 8 and Figure 9 show, the final BCR and FTT curves, respectively, after α s=45 convergence. The KPI curves for eN B c=13 , eN B j=15 , eN B j=22 and eN B j=43 are shown while the KPI curves for eN B j=14 and eN B s=45 are not shown as they show a similar trend. The points encircled in green show the a priori data points for the neighbouring eNBs. The points encircled in red show the a priori data points for the central eNB. It is evident from the KPI curves that in the end of the troubleshooting process, the effect of initially assumed a priori data points has almost disappeared, as the KPI curves follow the newly generated KPI data points and have shifted away from the initial a priori points. The convergence of α s=45 can be seen from the concentration of KPI points around α s=45 = 0.59 in the two figures. The BCR of eN B c=13 improves from 0.0528 to 0.0396 and its FTT decreases from 16.9362 to 15.1480. Figures 10(a) and 10(b) show, in descending order, the BCR and the FTT respectively for the reference (square) and the optimized (circle) eNBs in the evaluation zone. It is noted that the order of the stations in the two curves of each figure may not be preserved. The performance of the problematic eNB has been improved while the performance of the neighbouring eNBs in the evaluation zone has, on the average, improved. The average improvement of BCR is 25%, while that of FTT is 11.88%. The troubleshooting scenario has been repeated six times with and without the a priori knowledge incorporation. It has been observed that in the abscence of the a priori knowledge the mean number of iterations required for SLAH convergence is 19.6. With the use of a priori knowledge the number of iterations is reduced to 10.

VII. CONCLUSION

This paper shows how the a priori knowledge can be introduced into-and improve the performance of the Statistical Learning Automated Healing (SLAH) method presented in [START_REF] Tiwana | Statistical approach for automated troubleshooting: application to LTE interference mitigation[END_REF]. The statistical model describes the closed form relations between the RRM parameters and the KPIs, which are obtained from logistic regression. It has been shown that the a priori knowledge can avoid an initially bad statistical model, and hence accelerate the convergence of the SLAH algorithm. The improved SLAH algorithm can converge in a few iterations and is well suited for a real network implementation, e.g. in an OMC, as an off-line process. The automated healing approach has been successfully applied to heal an ICIC parameter of an eNB with degraded performance due to an excess of inter-cell interference in a LTE network.

Figure 1 .

 1 Figure 1. SLAH block diagram.

Figure 2 .

 2 Figure 2. The logistic function.

Figure 3 .

 3 Figure 3. ICIC System Model.

Figure 4 .

 4 Figure 4. LTE network layout with 45 eNBs.

5 .

 5 The set N S2 of the second tier neighbours of the problematic eNB consists of eN B 1 , eN B 10 , eN B 11 , eN B 16 , eN B 18 , eN B 24 , eN B 37 and eN B 44 . Denote by optimization zone the subnetwork comprising eN B c=13 and its first tier N S1, and by evaluation zone the subnetwork comprising the eN B c=13 and its first two tiers N S1 and N S2. The eN B s=45 is the eNB most coupled with eN B c=13 .

Figure 5 .

 5 Figure 5. A priori curves and data points for BCR as a function of α s=45 .

Figure 6 .

 6 Figure 6. A priori curves and data points for FTT as a function of α s=45 .

Figure 7 .

 7 Figure 7. Figure showing the convergence of α s=45 with and without a priori knowledge incorporated algorithm.

Figure 8 .

 8 Figure 8. Mean BCR values of eN B c=13 , eN B j=15 , eN B j=22 and eN B j=43 along with the corresponding regression curves as a function of α s=45 .

Figure 9 .Figure 10 .

 910 Figure 9. Mean BCR values of eN B c=13 , eN B j=15 , eN B j=22 and eN B j=43 along with the corresponding regression curves as a function of α s=45 .

Table II TABLE SHOWING a

 IISHOWING priori DATA POINTS

		αs	BCRc	BCR neigh	FTTc	FTT neigh
		0.1	0.03		0.08	14	23.5
		0.275	0.035		0.075	16	23
		0.725	0.7		0.045	21	13
		0.9	0.71		0.028	22	10
	α c=13	α j=14	α j=15	α j=22	α j=23	α j=43	α s=45
	0.50	0.79	0.61		0.84	0.95	0.71	0.55
	0.50	0.79	0.60		0.84	0.95	0.70	0.54
	0.50	0.87	0.76		0.90	0.97	0.83	0.73
	0.50	0.81	0.65		0.86	0.95	0.74	0.60
	0.50	0.81	0.64		0.85	0.95	0.74	0.59
	0.50	0.81	0.64		0.85	0.95	0.74	0.59
	0.50	0.81	0.64		0.85	0.95	0.74	0.59
	0.50	0.81	0.64		0.85	0.95	0.74	0.59

Table III SHOWS

 III THE α VALUES CALCULATED DURING OPTIMIZATION.


Jérémy Buisson

Franc ¸oise André

Jean-Louis Pazat

A framework for dynamic adaptation of parallel components

The emergence of dynamic execution environments such as Grids forces applications to take dynamicity into account. Whereas sudden resource disappearance can be handled thanks to fault-tolerance techniques, these approaches are usually not well suited when resource disappearance is announced in advance. However, this case occurs in particular for resource preemption due to resource sharing or maintenance operations. Similarly, fault-tolerance techniques commonly do not take into account resource appearance. On the other side, dynamic adaptation covers techniques for handling changes in the execution environment. This article presents a framework intended to help developers in the task of designing dynamically adaptable (but not fault-tolerant) components. This article puts the emphasis on an experimental evaluation of the cost of using such a framework.

Introduction

The increase of resource consumption by applications is a fact. This is what leads to the introduction of notions such as meta-then grid-computing. Those approaches, that can be coarsely seen as resource pooling, permit to increase significantly the number of resources available to applications. However, increasing the number of resources lowers the mean time between failures. In addition, resource pooling requires users to share the resources; and it prevents them from controlling maintenance operations as they can with their own resources. This makes execution environments dynamic. Applications executed on such environments must take into account the dynamicity of the environment. Otherwise, they would not be able to perform well, and may even not be able to complete.

Dynamic adaptatability is one approach that can be used to tackle the problem of the dynamicity of execution environments. It consists in the ability of applications to modify themselves during their execution according to some observations. If the application observes its execution environment, it thus adapts itself according to its environment.

This article presents a framework for easing building dynamically adaptable components. Section 2 provides a description of dynamic adaptation. Section 3 presents the architectural view of an adaptable component. Section 4 focuses on the problem of coordinating the execution of the adaptation with the execution of the component itself. Section 5 describes the experimental results we obtained with our prototype framework. Section 6 compares our proposal to existing related works.

Dynamic adaptation

Dynamic adaptation is an event-based approach for dealing with dynamicity during the execution. When the component observes a change that is significant enough, it decides to react to this change. For example, when a component observes that new processors become available, it may increase its parallel degree by spawning new processes. At an abstract level, dynamic adaptation requires that the component is able to make observations, take a decision and execute a reaction previously defined. What is exactly observed, how decision is made and which actions must be performed to execute the reaction are closely related to the component and to the goal given to dynamic adaptation. In the given example, the component observes processors because it is able to execute a parallel implementation of itself; the component decides to increase its parallel degree as it aims at executing as fast as possible; it does so by spawning new processes because it is its way of executing on a parallel environment. This shows that dynamic adaptation may not be done without the help of developers. Nevertheless, we can exhibit generic mechanisms and provide developers with a framework for both designing and programming dynamically adaptable components.

Framework for dynamic adaptation

The model for dynamic adaptability of software components we defined is divided into several functional "boxes" distributed in three levels as shown on figure 1.

At the functional level, the service provides an implementation of what the component is expected to do. If the component was not dynamically adaptable, it would contain only the service.

The component-independent level contains all mechanisms that can be defined independently of the content of the service functional box. The decider box is the start point of any adaptation. It decides whether the component should be adapted or not. To do so, it relies on incoming events and on some external probes. The connection to the external probes is modeled by the two ports exposed by the decider. The actual trigger of the decision-making process may either result from the reception of an event or be spontaneous. Once the decider has decided that the component should be adapted, it transmits a reaction to the planner. The reaction describes the kind of the adaptation that should be performed. Given this reaction, the planner establishes a plan for applying it. This plan is mostly a collection of action invocations connected by some control flow. This plan is given to the executor, which executes the invocations with respect to the provided control flow. To do so, it relies on coordinator which coordinates the invocations with the execution of the service. As section 4 details, several kinds of coordinators may be used.

The component-specific level is a placeholder for the developer to put specializations of the adaptation framework. The policy permits the developer to specialize the decider for the needs of its component. It describes how decisions can be made. The plan templates describe how the planner can build plans depending on the requested reaction and on the current execution environment. The actions are the elementary tasks that can be invoked from the plans. In order to simplify its task, the developer may be provided with a library of predefined actions. Endly, the relation between the service and the coordinator is weaved thanks to aspect-oriented techniques through the "adaptable" Figure 1. Architecture of an adaptable component aspect. This aspect is parameterized specifically to the component.

An example of specialization of the framework is given in section 5.1 that describes the demonstrative component used for experiments.

Coordination of the invocations of the actions

As it has been previously described in section 3, the purpose of coordinators consists in coordinating the invocations of the actions requested by the plan with the execution of the service. Several coordination policy can be identified and classified according to several concerns:

• Parallel degree. The action may be invoked in a sequential way. When the service contains a parallel code, the action may also be invoked with the same parallel degree as the service functional box.

• Context of execution. The action may be invoked from within the context of the threads of the service. Alternatively, it may be invoked from the context of the processes of the service. It may also be invoked from processes distinct from those of the service, possibly hosted by other machines.

• Synchronization. The action may be invoked asynchronously with regard to the service. It may alternatively require the service to suspend its execution in a special state.

The main purpose of the synchronization concern consists in ensuring that the adaptation does not change (at least semantically) the results produced by the component. Indeed, some actions may not be allowed to be invoked from any state of the service. For example, a matrix redistribution might not be done while the matrix is being modified. This is why the notion of "point" has been introduced. We call "points" the special states from which actions are allowed to be invoked. Points mostly consists in annotations in the source code of the service functional box; they are instantaneous statements placed by the developer at the locations at which he considers actions can be safely invoked. Given this context, solving the synchronization concern for a coordinator consists in choosing one point at which the action will be invoked.

When the service encapsulates a parallel code, the notion of "point" extends to the global dimension: a "global point" is a collection (one per thread of the service) of points. The choosability of a global point is restricted by a given consistency model. An example consistency model may intuitively assume that the parallel code consists in several parallel steps. Such a model would allow adaptation only between those steps. This model has been described in [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF]; a proposal for implementing it has been presented in [START_REF] Buisson | Enforcing consistency during the adaptation of a parallel component[END_REF] that restricts the choice to points in the future of the execution path. To do so, it relies on annotations of the code to track the progress of the execution and on a representation of the control flow graph to predict future states. Those annotations are the result of weaving the "adaptable" aspect described in section 3; whereas the points, placed manually by the developer, are the parameters that specialize this aspect for the component.

Experiments

The experiments we have made are based upon the NAS Parallel Benchmark [START_REF]NAS. Parallel benchmark[END_REF] 3.1 FFT code for MPI. This code computes the fast fourier transform of a 256 × 256 × 128 matrix from within an iteration. For the purpose of the experiments, it has been slightly modified to use the framework. The modifications are exclusively annotations for indicating adaptation points and for tracking the progress of the execution. Those annotations consist in calls to some functions of the framework.

Experiments have been done using a cluster of dual 2.4 Xeon PC. Each PC hosts at most one process with exactly one thread of the service. For the communications, the service of the component uses LAM-MPI [START_REF] Burns | LAM: An Open Cluster Environment for MPI[END_REF]; the framework uses OmniORB as an implementation of CORBA.

Specialization of the framework for the experiments

For the experiments, the FFT component has been made able to modify its parallel degree depending on the number of machines available in the cluster. The policy is given by figure 2. It states that when new machines become available, the component should spawn new processes; whereas when some machines are announced to disappear, it should stop the corresponding processes.

Algorithm policy () :

• upon new machines appear (machines) : spawn process (machines) • upon machines reclaimed (machines) :

terminate process (machines)

Figure 2. Policy for adaptable FFT Figures 3 and4 show the plan templates for both reactions. The prefix of actions in brackets gives the constraints for each of the coordination concerns listed in section 4.

In order to spawn new processes (reaction spawn process), the component have to be made available on the corresponding machines (action deploy on); then the processes must be created (action spawn process on); endly, the matrices have to be redistributed (action redistribute matrices).

Algorithm spawn process (new machines) :

[sequential, in distrinct process, asynchronously] deploy on (new machines) [parallel, in service threads, same point] spawn process on (new machines) [parallel, in service threads, same point] redistribute matrices ()

Figure 3. Plan template for spawning processes

Similarly, to terminate processes (reaction terminate process), the component have firstly to redistribute its matrices (action redistribute matrices); then the processes executed by the reclaimed machines must terminate their execution (action exit); endly, everything that was previously installed specifically for those machines has to be cleaned up (action cleanup).

Actions are implementations of the invocations requested in plans. Those implementations are dependent on the component and its implementation. For example, the deploy on action may transfer files and start required daemons; the spawn process on action uses of the M P I Comm spawn function as the FFT component uses the MPI communication library.

Timeline of an adaptation

This experiment aims at showing the actions of an adaptation and their timing. This would permit to show how the different phases of dynamic adaptation relates one to each others. This experiment consists in one run of the demonstration component with one adaptation that increases the number of processes from two to four. Figure 5 shows the execution trace near this adaptation. This trace shows that the choice of the adaptation point is done concurrently to the execution of the service. Then, the effective execution of the reaction is postponed to the chosen adaptation point, further in the future of the execution.

The plan begins by spawning new processes. Due to the MPI-2 specification, and in order to be able to stop each process independently of the others, each process has to be spawned individually. In order to simplify the manipulation of MPI communicators, spawned processes participate to the creation of the following processes. This is why one of the spawned processes has a call to M P I Comm spawn. Once processes have been spawned, some initialization is performed. This initialization action computes the values that depends on the set of processes, such as communicator objects. Then, matrices are redistributed among the new collection of processes. Endly, the execution of the FFT that was in progress resumes.

Overhead of the framework

In order to measure the overhead of the proposed framework, the demonstration component has been executed without any adaptation. This experiment permits to evaluate the overhead of the annotations required by the framework. For this experiment, the component executes 2000 iterations on a 16 machines cluster. Table 6 summerizes the execution time of each call to the framework in microseconds. The high maximum value for "function enter" appears to correspond to the first calls for each process. This can be explained by the absence of a complete warmup phase. Figure 7 shows the distribution of the measured times amongst the samples for the "adaptation point" function. This curves shows that two execution times have a high frequency: the lowest one corresponds to favorable cache situations; the highest one to defavorable cache situations. The same phenomenon appears with the other functions.

Given the number of calls per iteration for this sample component, the ratio of time lost because of the framework is under 0.05%. Given this result, it appears that the overhead of the framework can be considered as negligible for real world applications.

Scalability of the choice of the point

As our coordinator solves an agreement problem, the more processes are used, the more time it takes. In order to evaluate the scalability of the algorithm involved in our coordinator, the demonstration component has been executed and adapted with a parallel degree ranging from 2 to 32 processes. Figure 8 shows the time used for choosing the adaptation point at which the reaction is executed.

Care should be taken while interpreting the results. Indeed, the measured time depends not only on the number of processes, but also on the exact time at which the algorithm is triggered (and the execution time of the service code between adaptation points). Whereas we want to evaluate the former, the latter can not be controlled and scrambles the measures. Computing the minimum time for each number of processes eliminates most of the noise caused by the variation of the trigger time if enough measures are done.

On the figure, dots represent measures; minima for each number of processes are connected by a line. This line appears to evolve almost linearly with regard to the number of processes. This result could be expected as the actual implementation relies on a ring communication scheme.

Related works

Several works have proposed architectures for dynamic adaptation such as [START_REF] Aldinucci | Components for high performance grid programming in the grid.it project[END_REF][START_REF] David | Towards a framework for self-adaptive component-based applications[END_REF][START_REF] Ensink | Program control language: a programming language for adaptive distributed applications[END_REF][START_REF] Keeney | Chisel: a policy-driven, context-aware, dynamic adaptation framework[END_REF][START_REF] Raverdy | DART : a reflective middleware for adaptive applications[END_REF][START_REF] Segarra | A framework for dynamic adaptation in wireless environments[END_REF]. Despite different architectures and approaches, those projects rely on concepts and functionnalities similar to the ones of our approach. Whereas many projects have studied dynamic adaptation in the context of mobile computing, only few are interested in this problem in the area of parallel computing. As the problem described in section 4 of coordinating the execution of the actions appears mainly in the context of parallel computing, many projects did not study it.

Whereas our approach focuses on building adaptable components by extending standard components, the ASSIST [START_REF] Aldinucci | Components for high performance grid programming in the grid.it project[END_REF] approach for dynamic adaptation is based on high-level parallel language constructs. With this approach, the compiler itself is able to emit code for handling dynamicity. Whereas our approach gives full control of dynamic adaptation to the developer, the ASSIST approach permits some dynamic adaptation transparently to the developer. In addition, knowledge of the generated code can be used to specialize the runtime support for dynamic adaptation.

The PCL project [START_REF] Ensink | Program control language: a programming language for adaptive distributed applications[END_REF] aims at easing the construction of adaptable distributed applications. It focuses on how the application can be modified for dynamic adaptation thanks to a runtime providing some reflexive programming support. In order to support reflection, PCL introduces the notion of "adapt sites", which are special nodes in the control flow graph that contain collections of unordered (and potentially concurrent) tasks. Intercession operators allow modifications of the collection of tasks associated to each adapt site. In addition, PCL defines a language for expressing when and how the application should be adapted thanks to "adapt methods". Whereas PCL mixes in a single function probes query, decision-making and planning of the adaptation, which may ease the global understanding of the adaptation, our framework separates these concerns in distinct components, which may simplify the design and reuse of more complex adaptation strategies. Endly, PCL defines a model for synchronizing the adaptation [START_REF] Ensink | Coordinating adaptations in distributed systems[END_REF]. A comparison of the PCL model to ours is given in [START_REF] Buisson | Enforcing consistency during the adaptation of a parallel component[END_REF].

Future work

Although several projects address the problem of dynamic adaptation, only few of them provide developers with an abstract model of dynamic adaptation. Providing tools to design and reason about dynamically adaptable software is one of the upcoming challenges. A basis for a design methodology has been proposed in [START_REF] Mcilhagga | Towards a design methodology for adaptive applications[END_REF]. We are currently working with the team producing ASSIST [START_REF] Aldinucci | Components for high performance grid programming in the grid.it project[END_REF], which includes facilities for dynamic adaptation, in order to propose a common abstract model that could be mapped to our frameworks. It could be expected from such a work to provide conceptual tools to ease the design of dynamic adaptation independently of the concrete platform.

Resource disappearance can be dealt with fault-tolerance mechanisms. However, fault-tolerance focuses on sudden resource disappearance, whereas maintenance operations for example could be announced in advance. Such announcements should be used to anticipate resource disappearance instead of blindly waiting for a fault to occur. Moreover, fault-tolerance approaches fail to make the application benefit from appearing resources. On the other side, the event-based nature of dynamic adaptation makes it particularly suitable when changes are announced in advance. Fault-tolerance and our approach to dynamic adaptation are complementary in their way to address the dynamicity of the execution environment. Convergence of the two approaches within a single framework should be investigated. In particular, the synchronization concern of the coordinator functional box within dynamically adaptable components introduces the notion of "point". This notion can be compared to checkpoints that can be used to implement fault-tolerance. Although the two notions do not match exactly, they might rely on the same infrastructure, possibly leading to a unified framework.

Figure 4 .Figure 5 .

 45 Figure 4. Plan template for terminating processes

Figure 6 .Figure 7 .Figure 8 .

 678 Figure 6. Execution times (in microseconds)


Jérémy Buisson
email: jeremy.buisson@irisa.fr

Françoise André
email: francoise.andre@irisa.fr

Jean-Louis Pazat
email: jean-louis.pazat@irisa.fr

Enforcing consistency during the adaptation of a parallel component

Keywords: dynamic adaptation, consistency, parallel computing

As Grid architectures provide execution environments that are distributed, parallel and dynamic, applications require to be not only parallel and distributed, but also able to adapt themselves to their execution environment. This article presents a model for designing self-adaptable parallel components that can be assembled to build applications for Grid. This model includes the definition of a consistency criterion for the dynamic adaptation of SPMD components. We propose a solution to implement this criterion. It has been evalued on both synthetic and real codes to exhibit the behavior of the several proposed strategies.

I. INTRODUCTION

Grid is an emerging architecture that we consider as a largescale federation of pooled resources. Those resources might be processing elements, storage, and so on; they may come from parallel machines, clusters, or any workstation. One of the main properties of these resources is to have changing characteristics even during the execution of an application. Resources may come and go; their capacities may vary. Moreover, resources may be allocated then reclaimed and reallocated as applications start and terminate on the Grid. To sum up, Grid is an architecture that is at the same time distributed, parallel and dynamic. This is why we think that the right application model to use in order to benefit from such an environment should be distributed assemblies of parallel self-adaptable components.

In our context, we just see the component as a unit that explicitly specifies the services it provides ("provide ports") and the ones it requires ("use ports"). Required resources are one kind of required services. Service specifications can be qualitative (type specification); they can also be quantitative (quality of the provided or used services). A parallel component is simply a component that encapsulates a parallel code. For example, GridCCM [START_REF] Pérez | A parallel corba component model for numerical code coupling[END_REF] extends CORBA Component Model to support parallel components. A self-adaptable component is a component that is able to modify its behavior depending on the changes of the environment: it may use different algorithms that use services differently and provide different qualities of services. The choice of the algorithm is a component-dependant problem and cannot be solved in a general way at some middleware level. Nevertheless, some generic mechanisms exist in adaptable components that are independant of the component itself. Our research focuses on the design of an adaptation framework for parallel components that provides all those common mechanisms. One of the main problems consists in providing a mechanism for choosing a point in the execution to perform the adaptation in a consistent manner. This article aims at addressing this problem.

Section II presents our model of dynamic adaptation for parallel codes to set the context of this article up. Section III gives few mathematical definitions that are useful in the remaining of this paper. Sections IV and V describe how the future of the execution path is predicted to choose the adaptation point at which the adaptation code is inserted. Section VI discusses the results obtained from our experiments. Section VII compares our work to others in the area of dynamic adaptation. It also shows similarities with computation steering and fault tolerance. Endly, section VIII concludes this paper and presents some perspectives.

II. MODEL OF SELF-ADAPTABLE COMPONENTS

The dynamic adaptability of a component is its ability to modify itself according to the execution environment on which it is deployed. The goal is to help the component to give the best performance given its allocated resources. Moreover, it makes the component aware of changes in resource allocation. Resources may be allocated and reclaimed dynamically during the lifetime of the component.

A. Structure of a self-adaptable component

With our model of dynamic adaptation [START_REF] André | Dynamic adaptation of parallel codes: toward self-adaptable components for the grid[END_REF], parallel selfadaptable components can split in several functional boxes (some of them being independant of the component itself). A parallel self-adaptable components contains five major functional boxes: its service, reactions, policy, decider and coordinator. Figure 1 shows the connections between those boxes. A short description of them follows.

• Service. The service of the component is what it provides.

The service can be implemented by several algorithms that might be used to solve a single problem. Each of these algorithms uses differently the resources; thus, there is one preferred algorithm for each configuration of the resources allocated to the component. • Reactions. The reactions are the ways to modify the component. They modify the way the service is implemented, changing the algorithm with another one, adjusting its parameters or anything else. • Policy. The policy describes the component-specific information required to make the decisions. For example, the policy can be an explicit set of rules or the collection of the performance models of the algorithms. • Decider. The decider makes the decisions. It decides when and how the component should adapt itself. In order to decide, it relies on the policy ; it may also embed a feedback controller (for example to complement the performance models of the policy). • Coordinator. The coordinator synchronizes the service with the reaction. To do so, it chooses a point (an instantaneous statement that annotates a special state) within the execution path in order to insert the reaction chosen by the decider. Service, reactions and policy are specific to the component, whereas the decider and the coordinator are independant of the component. The decider and the coordinator should thus be parts of an adaptation framework.

In the context of parallel components, the service can be implemented either sequentially (exactly one execution thread) or a parallelly (several communicating execution threads). In the latter case, the coordinator must implement a parallel algorithm.

B. Contracts between components

Because the quality of the services used by a component is of greater importance to the adaptation, we attach to each port link a contract that describes the effective quality of the provided service. Moreover, for the sake of uniformity, our model abstracts resources as "provide ports" of some component called the environment. The execution environment of a component is thus completely described by the contracts attached to its "use ports". Consequently, any change in the execution environment is reflected by a change in those contracts, triggering the adaptation.

Contracts are dynamically negotiated and renegotiated: a component negotiates sufficient quality of service with its subcontractors in order to respect the contracts with its clients; it negotiates with its clients the quality of the provided services according to the ones contracted with its subcontractors. In that way, any renegotiation of one contract automatically propagates to the entire assembly of components (the application) to adjust the quality of all the provided services of all components. Consequently, it propagates the trigger of the adaptation to the components that require it.

C. Performance model

The goal of dynamic adaptation is to help the component to give the best performance. Thus, the model assumes that adaptation occurs when the component runs a non-optimal service given its allocated resources. This means that the completion time is worse than what it could be. In a general way, the conceptual performance model of a single-threaded component that adapts itself is shown by figure 2. The x-axis is the execution flow of the component; the curve gives the expected completion time if the component adapts itself at the corresponding point in its execution flow. The adaptation can occur in either the future or the past of the current state. In the case of adapting in the past, it requires the restoration of a checkpoint (that has a cost r on the curve). The limit of adapting in the future is adapting once the execution has ended (or equivalently not adapting at all); the limit of adapting in the past is to restart from the begining (purely static adaptation). It appears that whatever the search direction, the best point will always be the nearest one from the current state.

In the case of a parallel component, several curves are superimposed. Because the threads of the component are not necessarily synchronized, the curves are slightly shifted. The global completion time is thus the maximum of the ones for all threads. In this case, the best point can be in the future for some threads and in the past for the others.

In this paper, we arbitrarily chose to consider only the search direction that goes to the future of the execution. In the case of a parallel component, we look for a global point that is in the future of all threads.

D. Consistency model

In the case of a parallel service, the coordinator must enforce the consistency of the adaptation. We defined one consistency model we called the "same state" consistency model. In this model, the adaptation is said to be consistent if and only if all threads execute the reaction from the same state (this logical synchronization does not require an effective synchronization of the execution threads).

This model only makes sense in the case of SPMD codes (parallel codes for which all threads share the same control flow graph).

E. Scenario of dynamic adaptation

From time to time, possibly due to some external event, the decider decides according to the policy that the component should adapt itself. It thus orders the coordinator to execute a specified reaction. The coordinator then chooses a point in the future of the execution path at which the reaction can be executed. When the service is parallel, the point is a global state such that all threads are in the same state ("same state" consistency model). At this point, the coordinator suspends the service and executes the reaction.

In this paper, we will concentrate on the coordinator. Section IV describes how the point can be computed; section V depicts how an algorithm can be built. In the remaining of the document, we will call "candidate points" the points at which a reaction can be executed. The one that has been chosen by the coordinator will be called the "adaptation point".

III. DEFINITIONS Definition 1 (poset):

A poset (or partially-ordered set) is a pair (P, R) where P is a set and R is a binary relation over P that is (1) reflexive, (2) antisymmetric and (3) transitive.

(1

) ∀x • (x ∈ P ⇒ xRx) (2) ∀x, y • x, y ∈ P 2 ⇒ ((xRy ∧ yRx) ⇒ x = y) (3) ∀x, y, z • x, y, z ∈ P 3 ⇒ ((xRy ∧ yRz) ⇒ xRz) Definition 2 (supremum): Given a poset (P, R), the supre- mum sup (S) of any subset S ⊂ P of P is the least upper bound u of S in P such that: ∀x • (x ∈ S ⇒ xRu) ∧∀v • (v ∈ P ⇒ ((∀x • (x ∈ S ⇒ xRv)) ⇒ uRv)
) Definition 3 (infimum): Symmetrically to the supremum, given a poset (P, R), the infimum inf (S) of any subset S ⊂ P of P is the greater lower bound l of S in P such that:

∀x • (x ∈ S ⇒ lRx) ∧∀v • (v ∈ P ⇒ (∀x • (x ∈ S ⇒ vRx)) ⇒ vRl)
The infimum of S in the poset (P, R) is the supremum of S in P, R -1 .

Definition 4 (lattice): A lattice L is a poset (P, R) such that for any pair x, y ∈ P 2 , both the supremum sup ({x, y}) and the infimum inf ({x, y}) exist. This defines two internal composition laws:

sup ({x, y}) = x ∨ y (join) inf ({x, y}) = x ∧ y (meet)

IV. COMPUTING THE FUTURE

The coordinator needs to find a global point such that it represents the same state for all threads. As it restricts to points in the future of execution paths this point should be the first one in the future for all threads, given the assumption on the performance model.

A. Local prediction of the next point

For each thread, the coordinator needs to find the next candidate point in the future of the execution path. This point would be the one at which the coordinator is going to execute the reaction in the case of a single-threaded component.

1) General schema: An execution path can be seen as a path in the control flow graph that models the code. If loops are unrolled (for example by tagging nodes with indices in iteration spaces), the control flow graph defines a "precedes" partial order between the points of a code. Given this relation, each thread of the parallel component is able to locally predict its next point at least in trivial cases.

2) Uncertain predictions: Predicting the future of an execution path is undecidable due to conditional instructions: their behavior is unpredictable since it depends on runtime computations. This occurs for both conditions and loops, which appear as nodes having several successors in the control flow graph.

Three strategies may be used when such a node is encountered during the computation of the adaptation point.

• Postpone. The computation of the adaptation point can be postponed until the effective behavior of the instruction is known. Once the unpredictable instruction has been executed, the computation of the adaptation point resumes with a new start point (the one that is being entered). • Skip. The computation of the point can move forward in the control flow graph until all control subflows merge. In this case, the prediction jumps over loops and conditions. • Force. The behavior of the conditional instruction can be guessed when additional static information is available. With this strategy, one branch of the conditional instruction is assumed accordingly to some applicationdependant knowledge; then some application-level mechanism enforces that the execution path respects this assumption. The two following examples illustrate the usage of the "force" strategy. Firstly, it is possible for some loops to insert unexpected empty iterations; in this case, it can be guessed that the conditional instruction will execute the branch that stay in the loop; this behavior can be enforced by making one more empty iteration on-demand. Secondly, if the code includes assertions to detect error cases, it could be reasonably assumed that those assertions hold; in this case, it can be guessed that the corresponding conditional instruction will execute the branch leading to error-free cases.

B. Characterization of the chosen global point

The point that should be chosen is the supremum u, if it exists, of the set S of the next local points for each thread with respect to the "precedes" partial order (noted ). Indeed, the property ∀x • (x ∈ S ⇒ x u) guarantees that u is in the future of all threads; the property ∀v

• (v ∈ P ⇒ ((∀x • (x ∈ S ⇒ x v)) ⇒ u v)
) means that u is the first point amongst those in the future of all threads.

Even if loops are unrolled, the control flow graph is not a lattice as it may contain patterns such as the one of figure 3(a). In this example, the supremum sup ({P 1, P 2}) does not exist. This pattern captures a subset of conditional instructions. The three strategies that has been identified for locally predicting the next point can be used to work-around non-existence of the supremum. This set contains the points that are related to all successors of all points in S. Those points are guaranteed to be traversed by any execution thread starting from any point in S. In the given example, it restricts to compute the supremum sup ({P 1, P 2}) in {P 1, P 2, P 5}; this supremum exists. • Force. Forcing one branch of a conditional instruction removes all out edges but one of the corresponding node. This is sufficient to make the supremum exist. For example, on figure 3(c), the conditional instruction that follows P 1 has been forced such that it always leads to P 3.

Each conditional instruction may use a distinct strategy. In such a case, the several strategies are combined.

C. Comparison of the strategies

These three strategies have their own fall down. The "postpone" one shortens the time between choosing a point and reaching the chosen point. It may result in an increase of the risk that the execution thread tries to get through the locally chosen point before it has been globally either confirmed or evicted. The "skip" one chooses an adaptation point further in the future of the execution path (and possibly falls back on the end of the code). The "force" one modifies the code of the execution thread.

V. BUILDING AN ALGORITHM

In order to solve the problem of finding a point in the case of a parallel service, an algorithm has been designed.

A. Identification of the candidate points

Having a good identification system for the points is a key issue. Indeed, as section IV-B showed, the case of parallel self-adaptable components requires the computation of the supremum of a set of points. This requires to be able to compare easily candidate points with respect to the "precedes" partial order. However, with naive point identification, deciding whether a candidate point precedes, succeeds, or is not related to another one requires the computation of the transitive closure of the control flow graph. The same apply for the join composition law. This is why smarter identification system for the points is needed.

1) Description of the identification system: We think that the good representation to use is a tree view of the hierarchical task graph. Figure 4 gives an example algorithm that has been annotated with candidate points; figure 5 shows the control flow graph between annotated points; figure 6 shows the corresponding tree view. The edges of the tree are labelled as follows:

• out edges of loop nodes are labelled with the value of the indice within the iteration space of the loop; • out edges of condition nodes are labelled with either the symbol "then" (the condition is true) or the symbol "else" (the condition is false); • other edges (out edges of block nodes) are labelled with the execution order number in the control flow.

Algorithm gcd (a, b) : Considering the tree view of the hierarchical task graph, one can see that the nodes of the control flow graph are the leaves of the tree. Each candidate point is identified by the sequence composed of the labels of the edges traversed by the path from the root to the node corresponding to it. For example, the node "P 3"is identified by 2 ; the node "P 1" is identified by the sequence 1, (a, b) , 1, else, 1 . 2) Order on points: The set of edge labels in the tree is E = N∪I ∪{then, else}, where N is the set of execution order numbers (natural numbers) and I the iteration space partially ordered by an application-specific relation I . We define the following partial order over the set E of edge labels of the tree:

loop until ((a mod b) = 0) if (a < b) then // candidate point P 1 tmp ← a a ← b b ← tmp else // candidate point P 2 a ← (a mod b) end if end loop // candidate point P 3 return (b)
∀x, y • x, y ∈ E 2 ⇒ (x E y ⇔ x, y ∈ N 2 ∧ x ≤ y ∨ x, y ∈ I 2 ∧ x I y
Notably, the two constants "then" and "else" are set not comparable to other values and values in iteration spaces (such as (a, b) in the example) are partially ordered by an application-specific relation.

The edges of the control flow graph (that represent the "precedes" partial order between points) are (graphically) transverse to those of the tree. Consequently, the lexicographical partial order n E on the sequences is equivalent to the partial order on points defined by the control flow graph. Thus, with this identification system, deciding whether a point precedes, succeeds, or is not related to another one can be computed as a direct lexicographical comparison (not requiring the computation of the transitive closure of the control flow graph anymore). Moreover, this ordering directly takes into account the loop indices in iteration spaces, whereas the control flow graph does not.

3) Discussion: This identification system makes sense only in the case of a parallel component into which all threads are allowed to have different dynamic behaviors (different behavior of conditionnal instructions and loop indices desynchronization). Otherwise, a simple counting identification system is sufficient. Furthermore, in the case of a non-parallel component, no identification system is required.

B. Computation of the local adaptation point

Because we restricted to candidate points in the future of the execution path, the local adaptation point is the next point in the path. Computing this point simply consists in following the edges of the control flow graph. This corresponds to a depth-first traversal of the tree from the left to the right. This traversal begins at a start point that is at least the one being executed at the time of the computation.

C. Instrumentation of the code

In order to predict the next candidate point in the future of the execution path, the coordinator must be able to locate the actual execution progress in the space of the candidate points. As it must be able to build the sequence identifying the candidate point that is being executed by the execution thread, the coordinator requires an instrumentation of the code.

The instrumentation of the code consists in inserting some pieces of code at each node of the tree view of the hierarchical task graph as presented at the preceding section. The figure 7 shows an example of an instrumented algorithm. The process of inserting the instrumentation statements in the source code of the component can be largely automated using aspect-oriented programming (AOP [START_REF] Kiczales | Aspect-oriented programming[END_REF]) techniques. In this case, the join points are the nodes of the tree representation of the code previously described.

Algorithm instrumented_gcd (a, b) : enter_f unction (gcd (a, b)) enter_loop (a, b) loop until (leave_loop ((a mod b) = 0)) iteration_loop (a, b) if (enter_condition (a < b)) then candidate_point (P1) tmp ← a a ← b b ← tmp else candidate_point (P2) a ← (a mod b) end if leave_condition () end loop candidate_point (P3) return (leave_f unction (b))

D. Protocol for computing the supremum

Many trivial protocols might be designed to compute this supremum (for example, centralized). Many already exist to compute a maximum (in particular for leader election); they can easily be modified to compute a supremum instead of a maximum. However, we think that a specific protocol suits better this case.

1) Motivation for designing a specific protocol: The full set of the local adaptation points is not always necessary to compute the supremum. The idea is to superimpose the agreement protocol and the local computations of the next candidate point in order to exempt some of the execution threads from computing their local adaptation point. In particular, it is interesting to exempt those whose prediction is postponed due to conditional instructions. Indeed, it allows the computation of the local adaptation point to resume sooner with a start point that is further in the execution path. Moreover, superimposing the protocol and the computation evicts the earliest adaptation points sooner than if the whole set of local adaptation points must be computed. This avoids situations in which the execution thread tries to execute through a locally chosen point that has not been either confirmed or evicted yet.

2) Informal description of the protocol:

The key idea of the protocol is to let the threads negotiate. Each thread can propose to the others its view of what the common adaptation point is, namely the point it has chosen locally. If it has not chosen one (because of unpredictable instructions such as conditions), it can give clues to the other threads. These clues can be for example the root node of the subtree representing the conditional block. When a thread receives a proposition or a clue, it may take different actions depending on how it compares to its own proposition.

• If its own proposition is better (that is to say in the future of the received one), it rejects the received proposition.

• If the received one is better, it is adopted.

• If both are not comparable, the thread retracts its proposition and computes a new one that takes into account the two previous ones. The computation starts at the point at which the control subflows merge (the supremum of the two points). • If both propositions are the same, the thread agrees with the other one. The protocol also progresses when an execution thread provides new information. For example when the functional thread executes a conditional instruction, it may retract its clue and propose a new one.

The protocol ends when all threads agree with each other's and when the agreement is on a true proposition (not just a clue). This means that they all have adopted the same point.

3) Anatomy of the protocol: We have designed a specific protocol to solve this problem. This protocol is based on a unidirectional ring communication scheme. Each thread confronts its proposition with the one of its predecessor and sends it only to its successor in the ring. The end of the protocol, namely the reach of the agreement, is detected using a Dijkstra [4]-like termination algorithm. Our protocol distinguishes strong propositions (values that can be chosen by the agreement) from weak propositions (values that forbid the agreement to conclude, previously called clues). The protocol allows threads to retract their proposition. It strictly defines the criteria of the consistency of retraction.

Our protocol is pessimistic. If an execution thread tries to get through a point thought to be the chosen one, the algorithm refuses to speculate whether it should allow the execution thread to continue or execute the reaction. It rather suspends the execution thread until it gets certainty. As a result, because the "postpone" strategy eases such situations (as described in section IV-C), this strategy tends to increase the risk of suspending the execution thread.

VI. EXPERIMENTS

The experiments presented here aim at comparing the strategies described at section IV-A.2 with regard to functional code suspension and delay before the execution of the reaction. The goal is to exhibit and validate the expected behaviors described in section IV-C. This characterization would help developers to choose the right strategy depending on their code.

Three experiments has been made: synthetic loop code, synthetic condition code and NAS Parallel Benchmark 3.1 [START_REF] Nas | Parallel benchmark[END_REF] FFT code. Only the results of the latter will be presented and discussed.

A. Experimental protocol

The experimental protocol consists in trigerring adaptation many times at random intervals (with uniform distribution to avoid implicit synchronization between the functional code and the adaptation trigger) while the code is being executed by a 4 processors cluster. Experiments result in two data series: one indicates for each adaptation the time elapsed between the trigger and the effective execution of the reaction; the other gives the time during which the functional thread has been suspended while choosing the point at which to adapt. For each data serie, one curve is drawn that gives an approximate measure of the density of samples for each observed value.

B. Observations

Figures 8 and9 show the results with the FFT code. This experiment aims at comparing the "postpone" and "skip" strategies for conditional instructions within a main loop. The main loop has the "force" strategy so that the synchronization and communication statements induced by our algorithm are exclusively related to the inner instructions. This prevents distortions of the observations. Figure 8 shows that the "postpone" strategy tends to select an adaptation point that arrives sooner in the execution path than the "skip" strategy. Conversly, figure 9 shows that the "postpone" strategy tends to suspend the functional code for a longer time than the "skip" strategy. Indeed, the "postpone" Example of a region in a PCL static task graph strategy leads to higher density of samples up to about 0.5 s of functional code suspension. However, this observation has to be balanced as it appears that both strategies do not suspend the functional code in most of the samples.

C. Discussion

These results and those we obtained with synthetic codes confirm the behaviors we expected at section IV-C. Namely, the choice between the "postpone" and the "skip" strategies, is a trade-off between the precision of the prediction and the risk to uselessly suspend the functional code.

The observations are explained by the fact that the "postpone" strategy tends to delay the agreement in order to choose a more precise point (closer to the current state), in comparision to the "skip" strategy. It makes the "postpone" strategy increase the risk for other threads to reach that point before the agreement is made, and thus to suspend their execution. On the other side, the "skip" strategy tends to choose a point that is further in the future of the execution path; it results in a lower risk for other threads to reach that point before the agreement is made and thus to suspend their execution.

Consequently, if the time between a conditional instruction and the following point is large enough to balance the delay of the agreement, the "postpone" strategy should be preferred as it results in a sooner adaptation. Otherwise, the "skip" strategy should be used in order to avoid the suspension of the execution thread.

VII. RELATED WORKS AND DOMAINS

A. Other projects about dynamic adaptation of parallel codes

Most of the projects that faced the problem of dynamic adaptation such as DART [START_REF] Raverdy | DART : a reflective middleware for adaptive applications[END_REF] do not consider parallelism. Other projects such as SaNS [START_REF] Dongarra | Self-adapting numerical software for next generation application[END_REF] and GrADSolve [START_REF] Vadhiyar | GrADSolve: RPC for high performance computing on the grid[END_REF] build adaptive components for Grid. Those projects target adaptation only at the time of component invocation. This supposes a fine-grain encapsulation in components; otherwise, if methods are too long, adaptation is defeated because it cannot occur during an execution. Within the context of Commercial-Off-The-Shelf (COTS) component concept, sufficiently finegrained encapsulation for the dynamic adaptation to make sense only at invocation level does not appear valuable enough; whereas sufficiently coarse-grained encapsulation for valuable COTS components are not able to really dynamically adapt themselves if they do so only at each invocation. This is why we think that components should be able to adapt themselves not only at method calls, but also during the execution of methods.

The Grid.It project [START_REF] Aldinucci | Components for high performance grid programming in the grid.it project[END_REF] also faces the problem of dynamically adapting parallel components. The followed approach is based on structured parallelism provided by high-level languages. The compiler generates code for virtual processes that are mapped to processing elements at run-time. An adaptation consists in dynamically modifying this mapping. This adaptation can be done within language constructs transparently to the developper. In this case, the consistency enforcement mechanism can rely on assumptions on the overall structure of the program as it is generated by a compiler.

PCL [START_REF] Adve | Language and compiler support for adaptive distributed applications[END_REF] focuses on the reflexive programming tools for the dynamic adaptation of parallel applications. This project considers dynamic adaptation as modifications on a static task graph modeling the code and provides at runtime primitive operators on that graph. It gives a full framework for reflexive programming that is useful to implement reactions. The problem of the coordination of the reaction and the execution threads of the functional code has been studied with PCL in [START_REF] Ensink | Coordinating adaptations in distributed systems[END_REF]. Their approach to the problem of the coordination is similar to ours: the adaptation is scheduled to be executed at an adaptation point in the future of the execution path. However, the problem of dealing with unpredictable conditional instructions is not addressed. Furthermore, the consistency model is different from ours. In PCL, each reaction is triggered at any point of the specified region. For example, on figure 10, tasks B and D are not distinguished. According to the consistency model, in a two-threads component, if one is executing A and the other C, a "region in" reaction targeting region RGN 1 is scheduled at the A → B edge for the first thread and at the C → D edge for the second one. We think that it is a better consistency model to schedule the reaction at the C → D edge for both threads (our "same state" consistency). One solution might be to put B and D in two different regions; but in this case, PCL fails specifying that the reaction can be scheduled either before B or before D, but at the same edge for all threads. Furthermore, PCL is unable to handle the case of thread desynchronization in loops (one thread doing more iterations than another does) for regions being in such a loop. The simple region counter is not sufficient to solve this problem.

B. Computation steering

The problem of steering a parallel component is very close to our problem of adapting this component. Indeed, in both cases, we need to insert dynamically code at some global state. The EPSN project [START_REF]Epsn project[END_REF] aims at building a platform for online steering and visualization of numerical simulations. In [START_REF] Esnard | A time-coherent model for the steering of parallel simulations[END_REF], the authors describe the infrastructure they built to do the steering. Their structured dates is similar to our candidate point identification system. Both systems are based on similar representations of the code. Moreover, steering like dynamic adaptation tries to find the next candidate point in the future of the execution path. Thus, computation steering and dynamic adaptation may benefit from fusionning in a single framework.

C. Fault tolerance

Fault tolerance might be seen as a particular case of dynamic adaptation. Indeed, it is the adaptation to the "crash" of some of the allocated resources. However, things are not that simple. Fault tolerance encompasses two different problems: the recovery of the fault and the adaptation to the new situation. Only the second one really belongs to the problem of dynamic adaptation. Many strategies can be used to recover from faults. The closest one from dynamic adaptation is probably checkpointing in the sense it requires some global points. Whereas dynamic adaptation can look for a point in the future of the execution path, checkpointing requires a point in the past. Nevertheless, mechanisms required by dynamic adaptation may be useful to implement recovery strategies based on checkpointing. The instrumentation of the code can be used as hooks at which checkpoints can be taken. Indeed, it implicitly statically coordinates the checkpoints of all threads, avoiding the problem of computing a global consistent state. Reciprocally, dynamic adaptation can take advantage of the techniques that have been developped to checkpoint and restart computations in the area of fault-tolerance.

VIII. CONLUSION

In this paper, we have briefly described the overall model we introduced to build self-adaptable parallel components. This paper essentially focuses on the coordinator functional box. This coordinator is responsible for scheduling the reaction in the execution path of the several execution threads.

The protocol we designed follows an pessimistic approach with regard to the fact that the execution thread may go through a confirmed point. In the future of our work, we will study how optimistic approaches can be designed. For example, when the functional code reaches a point suspected to be chosen but not yet confirmed, it may continue its execution instead of waiting for the point to be either confirmed or evicted. If at the end that point is confirmed, the situation may be repaired by rolling-back the functional code. Moreover, our coordinator searches adaptation points exclusively in the future of the execution path. However, this is an arbitrary choice that has no other justification than simplifying algorithms. In the future, it would search in both directions (future and past) to find the best adaptation point. We will study how algorithms can be generalized.

Endly, our "same state" consistency model has to be extended to the case of non-SPMD components: we have already thought of another consistency model defined by a customizable correspondence relation between the candidate points of the threads.

As a longer term research, we are working on completing our architecture in order to build a platform. In particular, we are investigating protocols for adaptation within assemblies of components. We are also studying how a resource manager could take advantage of applications able to adapt themselves.

Fig. 1 .

 1 Fig. 1. Model of a parallel self-adaptable component

Fig. 2 .

 2 Fig. 2. Conceptual performance model of an adapting component

Fig. 3 .

 3 Fig. 3. Example of control flow graph with non-existent supremum

Fig. 4 .

 4 Fig. 4. An example algorithm

Fig. 5 . 1 Fig. 6 .

 516 Fig. 5. Control flow graph of the algorithm 4

Fig. 7 .

 7 Fig. 7. Instrumented version of the algorithm 4

Fig. 8 .Fig. 9 .

 89 Fig. 8. Density curve for adaptation delay