Jérémy Buisson

Françoise André

Jean-Louis Pazat

Dynamic adaptation for Grid computing

As Grid architectures provide resources that uctuate, applications that should be run on such environments must be able to take into account the changes that may occur. This document describes how applications can be built from components that may dynamically adapt themselves. We propose a generic framework to help the developpers of such components. In the case of a component that encapsulates a parallel code, a consistency model for the dynamic adaptation is dened. An implementation of a restricted consistency model allowed us to experiment our ideas.

Introduction

Grid architectures dier from classical execution environments in that they are mainly built up as a federation of pooled resources. Those resources include processing elements, storage, network, and so on; they come from the interconnection of 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 during the execution of the applications. Moreover, resources may be allocated then reclaimed and reallocated as applications start and terminate on the Grid. Thus, resource usage by applications cannot be static; neither can changes in resource allocation be considered as faults. Grid-enabled application designers must keep in mind that resources and resource management are highly dynamic within Grid architectures.

Dynamic adaptation is a way to support evolving execution environments. It aims at allowing applications to modify themselves depending on the available resources. The key idea is that when the environment changes, the application should also change to t with it. To react softly, the application can negotiates with its execution environment about resources, instead of undergoing the decisions of the execution environment. Because taking adaptation into account should not burden too much the application developpers, it is necessary to provide them adequate frameworks and mechanisms. That is our main research objective.

Section 2 makes a tour of existing researches in areas close to adaptation.

Section 3 exposes how we model the dynamic adaptation of an application.

Section 4 shows the architecture we are currently building as a support to make adaptable applications. Section 5 describes the consistency model we introduced for the adaptation of components that encapsulate parallel codes. Section 6 presents the state of the experiments we have done with our consistency model.

Adaptation through existing works

Several projects use the word adaptation to describe themselves. As this section presents, all of those projects have dierent views of what adaptation is, what it consists in and why it should be used. Basically, the only common point is that adaptation consists in changing some things in applications. This asks four major questions: why adaptation should be done (section 2.1); where is it done in the execution (section 2.2); how can it be done (section 2.3); when should it be done (section 2.4). As the section shows, the several projects that exist have dierent answers to these four questions.

Goal of the adaptation

With existing projects, two main views of what the goal of adaptation could be opposed. In [START_REF] Aldinucci | Components for high performance grid programming int the grid[END_REF], the Grid.It project and its ASSIST [START_REF] Aldinucci | Assist as a research framework for high-performance grid programming environments[END_REF] programming model present adaptation as a way to achieve a specied level of performance. An application should modify its structure or change the resources it has allocated when performance contracts are not satised.

On the other hand, projects such as SaNS [START_REF] Dongarra | Self-adapting numerical software for next generation application[END_REF], GrADS [START_REF] Kennedy | Toward a framework for preparing and executing adaptive grid programs[END_REF] and PCL [START_REF] Adve | Language and compiler support for adaptive distributed applications[END_REF] consider that applications should adapt themselves to optimize themselves. Adaptation is a way for application to provide a best eort strategy. In this case, the application chooses the best implementation given the allocated resources and the properties of input data.

Location of the adaptation

Many projects such as SaNS, GrADS and GrADSolve [START_REF] Vadhiyar | GrADSolve: RPC for high performance computing on the grid[END_REF] do the adaptation upon invokation: when a function, method, procedure is called, the best algorithm is chosen. Although this is not as static as the automatic optimization such as for ATLAS [START_REF] Whaley | Automated empirical optimizations of software and the ATLAS project[END_REF], adaptation is not possible once the adaptable software has started its execution. This approach is realistic only if the adaptable softwares are negrained enough. In the case of SaNS, the targeted softwares are libraries of numerical kernels. In this case, it is sucient to adapt only at invokation time. Some projects such as Grit.It and PCL allows dynamic adaptation (namely, adaptation of a software that is executing). This is necessary when the execution time of the adaptable software is high. Moreover, the PCL project denes in [START_REF] Ensink | Coordinating adaptations in distributed systems[END_REF] a consistency model for the adaptation of parallel codes.

Means of the adaptation

When the adaptation is done exclusively at invokation time, adaptation is simply the selection of one implementation of several that are available. This is what is done with SaNS and GrADSolve.

In the case of dynamic adaptation, this is not sucient. Adaptation either involves parameterizable softwares or reexive programming. For example, within the ASSIST model of the Grid.It project, the parmod skeleton exposes several parameters such as the degree of parallelism that can be changed dynamically; the PCL project denes a framework for reexive programming in distributed and parallel applications. Dynamic aspect weavers (such as Arachne [START_REF] Ségura-Devillechaise | Web cache prefetching as an aspect: Towards a dynamic-weaving based solution[END_REF]) may also be used as an alternative to reexive programming to dynamically adapt the software.

Decisions to adapt

Several approaches can be used to decide when a software should adapt itself and what it should do. Within the ASSIST model, since adaptation is a way to achieve the contracted performance level, adaptation is mostly triggered from feedback control. On the other side, within the PCL project, the trigger is the reception of external events generated by external monitors. The projects SaNS and GrADSolve use performance models and a database of empirical measures to choose the right implementation to use.

Model of dynamic adaptation

Our model for dynamic adaptation considers that dynamic adaptation should occur in order to maximize the adequation between the application and its execution environment. Namely, this means that the purpose of dynamic adaptation is to optimize the application whenever its execution environment changes. To do so, it may use whatever means the developper is willing to.

The gure 1 shows the two kinds of curves for the progress of an adaptive software. The two cases correspond to an adaptation that causes the execution to slow down 1(a) and one that makes the application accelerates 1(b). The discontinuity reects the cost of the adaptation. Although the adaptation optimizes the application, the application may slow down. Indeed, this occurs when the execution environment reclaims some resources. Even if the application slows down, it is optimized compared to its execution if it has not been adapted: in such a case, the application could even have crashed.

The application can adapt itself anywhere in the execution path. It can be either at a past state or at a state in the future. The gure 2 shows how the overall completion time conceptually behaves depending on the current state and the one at which the adaptation is done. This curve directly translates that the adaptation optimizes the application. Thus, in the future, the sooner it is done, the better the completion time is. It reduces the time during which the application is suboptimal. By symmetry, in the past, the earlier in the application lifetime the adaptation is done, the bigger the computations to be redone are.

Adapting just after now is better than just before now because of the overhead of restoring a past state.

(a) Execution that is slowing down (b) Execution that is speeding up Fig. 1. Progress of an adaptive software Fig. 2. Completion time depending on the state at which the adaptation is done Adapting in the past has the advantage over adapting in the future that the adaptation can occur immediatly once the decision has been made. Thus, there is no transition during which the execution is suboptimal. Moreover, it does not require the prediction of a point in the future of the execution path, which is an undecidable problem in the general case.

On the other hand, adapting in the future does not require any instruction to be reexecuted; neither it has the overhead due to checkpoint-taking. [START_REF] Kennedy | Toward a framework for preparing and executing adaptive grid programs[END_REF] Architecture of adaptable software Applications are considered to be built as assemblies of software components.

Each of those components can encapsulate sequential or parallel codes. Moreover, each component can adapt itself. To do so, the component is supported by a framework. Indeed, it appears that some of the mechanisms involved in adaptation are independant of the component itself. • Behavior. This is the implementation of the services provided by the component. An adaptable component is allowed to contain several behaviors that are alternative implementations.

Component-specic part of the adaptation framework.

• Reaction. This is a code that modies the behavior that is being executed by the component. A component can include several reactions.

The reactions can change some parameters of the behavior; replace the behavior with another one; modify the behavior with the help of reexive programming or dynamic aspect weaving.

• Policy. This provides all the necessary information that are specic to the component to make decisions concerning the adaptation. It eddicts on which events the component should adapt and which reaction it should use.

Component-independant part of the adaptation framework.

• Coordinator. The coordinator is responsible for choosing where the reaction is going to be executed within the execution path of the behavior.

The possible locations are called candidate points; the chosen one is the adaptation point.

• Decider. The decider decides when the component should adapt itself and chooses which reaction should be executed. To do so, it relies on the information given by the policy.

The coordinator and the decider both make decisions regarding the adaptation. However, they encapsulate separate concerns. The decider encapsulates the goal of the adaptation and the criterium that is going to be optimized; whereas the coordinator focuses on the mechanisms for enforcing the consistency of the dynamic adaptation.

Scenario of the adaptation of a component

From time to time, the decider decides that the component should adapt itself with one reaction. This may come from an external event (specied in the policy of the component); this may be a spontaneous decision (as a result of feedback control for example). Once the decision to adapt is made, the decider orders the coordinator to execute the chosen reaction. Then, the coordinator chooses one candidate point in the execution path of the behavior. It also starts to monitor the execution of the behavior. When it reaches the adaptation point, the coordinator suspends the execution of the behavior and gives the execution control to the reaction. Once the reaction has nished, the behavior resumes its execution.

In addition, the behavior of a component can be a parallel code. In this case, The decider relies on the policy to make its decisions. The policy may contain an explicit set of rules: this can help the decider to choose the events to subscribe to. The policy may also contain performance models to help to choose the right reaction. Those performance models are parameterized with the content of the contracts describing the quality of the used services and resources.

Consistency of the adaptation within parallel components

When the component encapsulates a parallel code, the coordinator must choose a global point. However, the result of the execution of the adapted component must be semantically equivalent to the one of the component that does not adapt itself.

Thus, the chosen point should be consistent with respect to a given property that garanties this semantic equivalence. The adaptation is said consistent if the reaction is executed from such a point.

A simple example illustrates this: if the component does not dead-lock in normal executions, it must not dead-lock when it adapts itself. Thus, choosing the point at which the reaction can be executed requires to be aware of the communications that occur in the behaviors and reactions of the component.

Consistency model

The global point is R-consistent if and only if it satises the R relation. It is a n-ary relation if the parallel behavior is composed of n concurrent threads. This relation is dened over the n sets of local points. It is specic to each component.

In our example about dead-lock, this R relation encapsulates the required knowledge about communications within the component.

Classes of parallel components

Depending on the properties of the R relation, the parallel components can be classied. There is four major classes of parallel components.

SPMD components. If the R relation is id the identity, a global point is consistent if all the threads are locally at the same point. Regarding to the points, this means that all the threads share the same set of points. This case corresponds to the SPMD class of parallel applications.

Quasi-SPMD components. We consider that the R relation holds the following property:

(R (p 1 , p 2 , . . . , p n ) ∧ R (q 1 , q 2 , . . . , q n )) ⇒ (p 1 ≺ q 1 ∧ p 2 ≺ q 2 ∧ . . . ∧ p n ≺ q n ) ∨ (q 1 ≺ p 1 ∧ q 2 ≺ p 2 ∧ . . . ∧ q n ≺ p n ) ∨ (q 1 = p 1 ∧ q 2 = p 2 ∧ . . . ∧ q n = p n )
The ≺ symbol denotes the strict precede relation over the sets of local points.

In the execution paths, this is a total order relation.

If this property is satised, the local points can be renamed such that R becomes the identity relation. Thus, the component behaves like SPMD components.

Synchronous MPMD components. We suppose that the R relation satises the following property:

(R (p 1 , p 2 , . . . , p n ) ∧ R (q 1 , q 2 , . . . , q n ))

⇒ (p 1 q 1 ∧ p 2 q 2 ∧ . . . ∧ p n q n ) ∨ (q 1 p 1 ∧ q 2 p 2 ∧ . . . ∧ q n p n )
The symbol denotes the reexive precede relation over the sets of local points. In the execution paths, this is a total order relation.

In this case, the global points are still totally ordered in the execution path by a precede relation. This reects the synchronization of the threads within the component. However, a local point can participate to several global points.

Those components can be rewritten as quasi-SPMD components by duplicating such local points. This transformation restricts the consistency model.

Pessimistic parallel discrete event simulators belong to this class of components.

Asynchronous MPMD components. If none of the preceding properties is satised, the precede relation over global points in execution path is not a total order relation.

This class of components includes in particular master-slaves codes.

Comparison with other consistency models

The model dened by PCL in [START_REF] Ensink | Coordinating adaptations in distributed systems[END_REF] says that the adaptation is consistent if all the threads reach the i-th point (same i for all the threads) in the execution path. Although it seems similar, this is not equivalent to our id-consistency.

Indeed, our model identies points by name (identier in the model of the code augmented with indices in iteration spaces) whereas PCL explicitly uses the rank of the point in the execution path.

Thus, our model accepts that the threads have dierent dynamic behaviors.

The threads are not expected to execute the same number of iterations or to choose the same branch of conditional instructions. On the other hand, PCL supposes that all the threads remain in sync.

Realisation

By the time, we have designed and implemented an algorithmic solution for the coordinator. Our work restricts the model to the id-consistency in the case of SPMD parallel components. The candidate global points are exclusively looked for in the future of the execution path of the threads.

We have chosen to restrict to candidate points in the future. We worked around the impossibility of predicting the next point in the future of the execution path by introducing several strategies: the postpone strategy delays the prediction until the conditional instruction is executed; the skip strategy ignores the candidate points within the branches of the conditional instruction.

Figure 4 compares these two strategies. This experiment has been done with the NPB 3.1 [START_REF]Nas parallel benchmark[END_REF] FFT code on a 4 PCs cluster running PadicoTM [START_REF] Padicotm | [END_REF], which permits us to mix several middlewares such as MPI and CORBA within a single application. Only the coordinator has been implemented: the reaction is empty (no real adaptation); the decider is simulated by a trigger provided to the user.

The encapsulation within a component has not been done as it has no inuence for this experiment if we consider that the whole FFT code is within a single component.

Each dot of gure 4 represents one trigger of the adaptation. It appears on gure 4(a) that the postpone strategy generally chooses adaptation points that come sooner than the skip strategy. On the other hand, the gure 4(b)

shows that the postpone strategy suspends more frequently the functional code than the skip strategy. Indeed, we observe that most of the experiments with the skip strategy causes no suspension (high density of dots at 0 s), whereas the functional code is frequently suspended with the postpone strategy (high density of dots up to about 0.5 s). These two observations exhibit the trade-o between the precision of the prediction and the risk of suspending the functional code. In this paper we have shown that adaptation of parallel components can be achieved using our framework. Such an adaptation process needs to develop a consistency model and an algorithm to enforce this consistency before adaptation: the id-consistency model we developped shows the relevance of our consistency model for the adaptation of SPMD parallel codes.

We have shown through the FFT example that there is a trade-o between the precision of the choice of the point (best theoretical result) and the risk of uselessly suspending the execution of the functional code.

Futur works around the coordinator will consist in extending our implementation of the consistency model for non-SPMD components.

We plan to fully implement our framework, including a smart decider. This decider will be organized as a rule-based system. We will study how to represent usefull information for decision-making, such as states or changes of the environment. The representation of the adaptation policy have also to be dened. For this work we plan to rely on previous works on monitoring such as Delphoi [START_REF] Maassen | Middleware adaptation with the delphoi service[END_REF] or SAJE/RAJE [START_REF] Guidec | Towards resource consumption accouting and control in java: a practical experience[END_REF] and on our previous works on adaptation for mobile computing [START_REF] Chefrour | Développement d'applications en environnements mobiles à l'aide du modèle de composant adaptatif aceel[END_REF].

Another direction of our work is the study of the adaptation of assemblies of components for complete Grid applications. It is clear that in many applications, one component will not be able to adapt itself without taking into account the other components of the application. The role of the decider will be extended to include negotiation with deciders of other components of the application.

Fig. 3 .

 3 Fig. 3. Overall architecture of an adaptable component

  the candidate points and the chosen adaptation point are global and represent global states. A global point is composed of one local point for each concurrent thread of the parallel behavior. Local points are identied by both their name in a model of the functional code and the indices in the iteration spaces.

  Fig. 4. Comparison of the postpone and the skip strategies


Marco Aldinucci
email: aldinuc@di.unipi.itcampa@di.unipi.itcoppola@di.unipi.itmarcod@di.unipi.itzoccolo@di.unipi.it

Sonia Campa

Massimo Coppola

Marco Danelutto

Corrado Zoccolo

Françoise André
email: fandre@irisa.fr

Jérémy Buisson
email: jbuisson@irisa.fr

Francoise André

An abstract schema modeling adaptivity management

Keywords: Abstract schema, component adaptivity, Grid parallel component application. 1

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

AN ABSTRACT SCHEMA FOR ADAPTATION

Adaptivity is a concept that recent framework proposals for Computational Grid take into great account. In fact, due to the unstable nature of the Grid (nodes that disappear because of network problems, changes in user requirements/computing power, variations in network bandwidth, etc.), even assuming a perfect initial mapping of an application over the computing resources, the performance level could be suddenly compromised and the framework has to be able to take reconfiguring decisions in order to keep the expected QoS.

The need to handle adaptivity has been already addressed in several projects (AppLeS [START_REF] Berman | Applicationlevel scheduling on distributed heterogeneous networks[END_REF], GrADS [START_REF] Vadhiyar | Self adaptability in grid computing[END_REF], PCL [START_REF] Ensink | Program control language: a programming language for adaptive distributed applications[END_REF], ProActive [START_REF] Baude | On hierarchical, parallel and distributed components for Grid programming[END_REF]). These works focus on several aspects of reconfiguration, e.g. adaptation techniques (GrADS, PCL, ProActive), strategies to decide reconfigurations (GrADS), and how to modify the application configuration to optimize the running application (AppLes, GrADS, PCL). In these projects concrete problems posed by adaptivity have been faced, but little investigation has been done on common abstractions and methodology [START_REF] Mcilhagga | Towards a design methodology for adaptive applications[END_REF].

In this work we discuss, at a very high level of abstraction, a general model of the activities we need to perform to handle adaptivity in parallel and distributed programs.

Our intention is to start drawing a methodology for designing adaptive component environments, leaving in the meanwhile a high degree of freedom in the implementation and optimization choices. In fact, our model is abstract with respect to the implemented adaptation techniques, monitoring infrastructure and reconfiguration strategy; in this way we can uncover the common aspects that have to be addressed when developing a programming framework for reconfigurable applications. Moreover, we will validate our abstract schema by demonstrating how two completely different approaches to adaptivity fit its structure. We will discuss the Dynaco/AFPAC [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF] approach and the ASSIST [START_REF] Aldinucci | Dynamic reconfiguration of Grid-aware applications in ASSIST[END_REF] approach and we will show how, despite several differences in the implementation technologies used, they can be firmly abstracted by the schema we propose.

Before demonstrating its suitability to the two implemented frameworks, we exemplify its application in a significant case study: component-based, highlevel parallel programs. The adaptive behavior is derived by specializing the abstract model introduced here. We get significant results on the performance side, thus showing that the model maps to worthwhile and effective implementations [START_REF] Aldinucci | Dynamic reconfiguration of Grid-aware applications in ASSIST[END_REF].

This work is structured as follows. Sec. 2 introduces the abstract model. The various phases required by the general schema are detailed with an example in Sec. 3. Sec. 4 explains how the schema is mapped in the Dynaco/AFPAC framework, where self-adapting code is obtained by semi automated restruc-

¡ ¢ £ ¤ ¢ ¤ ¥ ¦ § ¨© ¦ ¥ ¡ ¨ ¢ © ¥ © ¨¦ ¥ ¦ ¥ ¤ ¨ ¢ ¨ ¢ § ! " # ¤ $ ¢ § ¥ ¥ ¥ § % & ' ( ) 0 1 2 3 4 ) 5 ) 4
6 3 0 3 7 ) 4 8 2 2 9 ) 4 ( @ ) & 0 1 2 3 4 ) 5 ) 4 A ' 2 9 3 ' 3 0 @ ( @ ) & 0 1 2 3 4 ) 5 ) 4
Figure 1 Abstract schema of an adaptation manager.

turing of existing code. Sec. 5 describes how the same schema is employed in the ASSIST programming environment, exploiting explicit program structure to automatically generate autonomic dynamicity-handling code. Sec. 6 summarizes those two mappings of the abstract schema.

ADAPTIVITY

The abstract model of dynamicity management we propose is shown in Fig. 1, where high-level actions rely on lower-level actions and mechanisms. The model is based on the separation of application-oriented abstractions and implementation mechanisms, and is also deliberately specified in minimal way, in order not to introduce details that may constrain possible implementations. As an example, the schema does not impose a strict time ordering among its leaves. The process of adapting the behavior of a parallel/distributed application to the dynamic features of the target architecture is built of two distinct phases: a decision phase, and a commit phase, as outlined in Fig. 1. The outcome of the decide phase is an abstract adaptation strategy that the commit phase has to implement. We separate the decisions on the strategy to be used to adapt the application behavior from the way this strategy is actually performed. The decide phase thus represents an abstraction related to the application structure and behavior, while commit phase concerns the abstraction of the run-time support needed to adapt. Both phases are split into different items. The decide phase is composed of: trigger -It is essentially an interface towards the external world, assessing the need to perform corrective actions. Triggering events can result from various monitoring activities of the platform, from the user requesting a dynamic change at run-time, or from the application itself reacting to some kind of algorithm-related load unbalance. policy -It is the part of the decision process where it is chosen how to deal with the triggering event. The aim of the adaptation policy is to find out what behavioral changes are needed, if any, based on the knowledge of the application structure and of its issues. Policies can also differ in the objectives they pursue, e.g. increasing performance, accuracy, fault tolerance, and thus in the triggering events they choose to react to. Basic examples of policy are "increase parallelism degree if the application is too slow", or "reduce parallelism to save resources". Choosing when to re-balance the load of different parts of the application by redistributing data is a more significant and less obvious policy. In order to provide the decide phase with a policy, we must identify in the code a pattern of parallel computation, and evaluate possible strategies to improve/adapt the pattern features to the current target architecture. This will result either in specifying a user-defined policy or picking one from a library of policies for common computation patterns. Ideally, the adaptation policy should depend on the chosen pattern and not on its implementation details.

In the commit phase, the decision previously taken is implemented. In order to do that, some assessed plan of execution has to be adopted.

plan -It states how the decision can be actually implemented, i.e. what list of steps has to be performed to come to the new configuration of the running application, and according to which control flow (total or partial order). execute -Once the detailed plan has been devised, the execute phase takes it in charge, relying on two kinds of functionalities of the support code -the different mechanisms provided by the underlying target architecture, and -a timing functionality to activate the elementary steps in the plan, taking into account their control flow and the needed synchronizations among processes/threads in the application. The actual adapting action depends on both the way the application has been implemented (e.g. message passing or shared memory) and the mechanisms provided by the target architecture to interact with the running application (e.g. adding and removing processes to the application, moving data between processing nodes and so on). The general schema does not constrain the adaptation handling code to a specific form. It can either consist in library calls, or be template-generated, it can result from instrumenting the application or as a side effect of using explicit code structures/library primitives in writing the application. The approaches clearly differ in the degree of user intervention required to achieve dynamicity.

EXAMPLE OF THE ABSTRACT DECOMPOSITION

We exemplify the abstract adaptation schema on a task-parallel computation organized around a centralized task scheduler, continuously dispatching works to be performed to the set of available processing elements. For this kind of pattern, both a performance model and a balancing policy are well known, and several different implementations are feasible (e.g. multi-threaded on SMP machines, or processes in a cluster and/or on the Grid). At steady state, maximum efficiency is achieved when the overall service time of the set of processing elements is slightly less than the service time of the dispatcher element.

Triggers are activated, for instance, when (1) the average inter-arrival time of task incoming is much lower/higher than the service time of the system, (2) on explicit user request to satisfy a new performance contract/level of performance, (3) when built-in monitoring reports increased load on some of the processing elements, even before service time increases too much.

Assuming we care first for computation performance and then resource utilization, the adaptation policy could be like the following: i) when steady state is reached, no configuration change is needed; ii) if the set of processing elements is slower than the dispatcher, new processing elements should be added to support the computation and reach the steady state iii) if the processing elements are much faster than the dispatcher, reduce their number to increase efficiency.

Applying this policy, the decide phase will eventually determine the increase/decrease of a certain magnitude in the allocated computing power, independently of the kind of computing resources.

This decision is passed to the commit phase, where we must produce a detailed plan to implement it (finding/choosing resources, devising a mapping of application processes where appropriate).

Assuming we want to increase the parallelism degree, we will often come up with a simple plan like the following: a) find a set of available processing elements {P i }; b) install code to be executed at the chosen {P i } (i.e. application code, code that interacts with the task scheduler and for dinamicity handling) ;c) register with the scheduler all the {P i } for task dispatching; d) inform the monitoring system that new processing element have joined the execution. It is worthwhile that the given plan is general enough to be customized depending on the implementation, that is it could be rewritten/reordered on the basis of the desired target.

Once the detailed plan has been devised, it has to be executed and its actions have to be orchestrated, choosing proper timing in order that they do not to interfere with each other and with the ongoing computation.

Abstract timing depends on the implementation of the mechanisms, and on the precedence relationship that may be given in the plan. In the given example, steps 1 and 2 can be executed in sequence, but without internal constraint on timing. Step 3 requires a form of synchronization with the scheduler to update its data, or to suspend all the computing elements, depending on actual implementation of the scheduler/worker synchronization. For the same reason, execution of step 4 also may/may not require a restart/update of the monitoring subsystem to take into account the new resources.

We also want to point out that in case of data parallel computation (as a fast Fourier transformation, as instance), we could again use policies like i)-iii and plans like a-d.

DYNACO/AFPAC: A GENERIC FRAMEWORK FOR DEVELOPERS TO MANAGE ADAPTATION

Dynaco is a framework allowing developers to add dynamic adaptability to software components without constraining the programming paradigms and tools that can be used. While Dynaco aims at addressing general adaptability problems, AFPAC focuses on the specific case of parallel components.

DYNACO: GENERIC DYNAMIC ADAPTATION FRAMEWORK

Dynaco provides the major functional decomposition of dynamic adaptability. It is the part that is the closest from the abstract schema described in section 2. Its design has benefited from the joint work about the abstract schema. As depicted by Fig. 2, Dynaco defines 3 major functions for dynamic adaptability: decision-making, planning and execution. Coarsely, those decision-making and execution functions match respectively the decide and commit phases of the abstract schema.

For the decision-making function, the decider decides whether the component should adapt itself or not. If it should, a strategy is produced that describes the configuration the component should adopt. The framework states that the decider is independent from the actual component: it is a generic decisionmaking engine. It is specialized to the actual component by a policy, which plays the same role as its homonym in the abstract schema. While the abstract schema reifies in trigger the events triggering the decision-making, Dynaco does not: the decider only exports interfaces to the outside of the component. Monitoring engines are considered to be external to the component and to its adaptability, even if the component can bind to itself in order to be one of its monitors.

The planning function is implemented by the planner. Given a strategy that has been previously decided, it aims at determining a plan that indicates how to adopt the strategy. The plan matches exactly its homonym of the abstract schema. Similarly to the decider, the planner is a generic engine that is specialized to the actual component by a guide.

While not being a phase in the abstract schema, planning has been promoted to a major function within Dynaco, at the same level as decision-making and execution. As a consequence, Dynaco introduces a planning guide in order to specialize the planning function in the same way that there is a policy that specializes the decision-making function. On the contrary, the abstract schema exhibits a plan which actually links the decide and commit phases. This vision is consistent with the goal of not constraining possible implementations. Dynaco is one interpretation of the abstract schema, while another would have been to have the decide phase directly produce the plan, for example.

The execution function is realized by the executor that interprets the instructions of the plan. Two kinds of instructions can be used in plans: invocations of elementary actions, which match the mechanisms of the abstract schema; and control instructions, which match the timing functionality of the abstract schema. While the former are provided by developers as component-specific entities, the latter are implemented by the executor in a component-independent manner.

AFPAC: DYNAMIC ADAPTATION OF PARALLEL COMPONENTS

As seen by AFPAC, parallel components are components that encapsulate a parallel code, such as GridCCM [START_REF] Pérez | A parallel corba component model for numerical code coupling[END_REF] components: they have several processes that execute the service they provides. AFPAC is depicted by Fig. 3. It is a specialization of Dynaco's executor for parallel components. Through its coordinator component, which partly implements the timing functionality of the abstract schema, AFPAC provides an additional control instruction for expressing plans. This instruction makes all of service processes execute an action in parallel. Such an action is labeled parallel action on Fig. 3. This kind of instruction is particularly useful to execute redistribution in the case of data-parallel applications.

AFPAC addresses the consistency problems of the global states from which the parallel actions are executed. Those problems have been discussed in [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF]; we have proposed in [START_REF] Buisson | Enforcing consistency during the adaptation of a parallel component[END_REF] an algorithm that chooses the next upcoming consistent global state. To do so, it relies on adaptation points: a global state is said consistent if every service process is at such a point. It also requires control structures to be annotated thanks to aspect-oriented programming in order to locate adaptation points as the execution progresses. The algorithm and the consistency criterion it implements suits well to SPMD codes such as the ones using MPI.

Fig. 4 shows the sequence of actions when a data-parallel code working on matrices adapts itself thanks to AFPAC. In this example, the application spawns 2 new processes in order to increase its parallelism degree up to 4. Firstly, the timing phase of the abstract schema is executed by the coordinator component concurrently to the normal execution of the parallel code. During this phase, the coordinator takes a rendez-vous with every executing service process at an adaptation point. When service processes reach the rendez-vous adaptation point, they execute the requested actions. Once every action of the plan has been executed, the service resumes its normal execution. This experiment shows well that most of the overhead lies in incompressible actions like matrix redistribution.

ASSIST: MANAGING DYNAMICITY USING LANGUAGE AND COMPILATION APPROACHES

ASSIST applications are described by means of a coordination language, which can express arbitrary graphs of (possibly) parallel modules, interconnected by typed streams of data. A parallel module (parmod) coordinates a set of concurrent activities called Virtual Processes (VPs). Each VP execute a sequential function (that can be programmed using standard sequential languages e.g. C, C++, Fortran) on input data and internal state.

Groups of VPs are grouped together in processes called Virtual Processes Manager (VPM). VPs assigned to the same VPM execute sequentially, while different VPMs run in parallel: therefore the actual parallelism exploited in a parmod is given by the number of VPMs that are allocated.

Overall, a parmod may behave in a data-parallel (e.g. SPMD/for-all/applyto-all) or task-parallel way (e.g. farm, pipeline), and it can nondeterministically accept from one or more input streams a number of input items, which may be decomposed in parts and used as function parameters to activate VPs. A parmod may also exploit a distributed shared state, which survives between VP activations related to different stream items. More details on the ASSIST environment can be found in [START_REF] Vanneschi | The programming model of ASSIST, an environment for parallel and distributed portable applications[END_REF][START_REF] Aldinucci | ASSIST as a research framework for high-performance grid programming environments[END_REF].

An ASSIST module (or a graph of modules) can be declared as a component, which is characterized by provide and use ports (both one-way and RPC-like), and by Non-Functional ports. The latter are responsible of specifying those aspects related to the management/coordination of the computation, as well as the required performance level of the whole application or of the single component. As instance, among the non-functional interfaces there are those related to QoS control (performance, reconfiguration strategy and allocation constraints).

Each ASSIST module in the graph encapsulated by the component is controlled by its own MAM (Module Adaptation Manager), a process that coordinates the configuration and adaptation of the module itself. The MAM dynamically decides the number of allocated VPMs and their mapping onto the processing elements acquired through a retargetable middle-ware, that can be adapted to exploit clusters as well as grid platforms.

Hierarchically, the set of MAMs is coordinated by the Component Adaptation Manager (CAM) that manages the configuration of the whole component. At a higher level, these lower-level entities are coordinated by a (possibly distributed) Application Manager (AM), to pursue a global QoS for the whole application.

The starting configuration is determined at load time by hierarchically splitting the user provided QoS contract between each component and module. In case of a QoS contract violation during the application run, managing processes react by issuing (asynchronous) adaptation requests to controlled entities [START_REF] Aldinucci | Dynamic reconfiguration of Grid-aware applications in ASSIST[END_REF]. According to the locality principle, violations and corrective actions are detected and issued as near as possible to the leaves of the hierarchy (i.e. the modules with their MAM). Higher-level managers are notified of violations when lower-level managers cannot handle them locally. In these cases, CAMs or the AM can coordinate the actions of several MAMs and CAMs (e.g. by renegotiating contracts with them) in order to implement a non-local adaptation strategy.

B C D E E F C D G H F C I P Q F R F Q D S D T G U F V W X T D H D G E W T X D Q D F S Y `V F Q a H D T G U F V W X T D H D G E b F Q c P G D S b S Y d e f g h e i i p q p i p r p f g s t u v w u x v y u y u w y v w w w v y w v u x w v y v y u y y y v w u y y u y u t v X P G v v u u w u x w y v w
Figure 5 ASSIST framework.

The corrective actions that can be undertaken in order to fulfill the contracts, eventually lead to the adaptation of component configurations, in terms of parallelism degree, and process mapping [START_REF] Aldinucci | Dynamic reconfiguration of Grid-aware applications in ASSIST[END_REF].

Reconfiguration requests to the adaptation mechanism are triggered by new QoS needs or by monitoring feedbacks. Such requests flow in an autonomic manner through the AM to the lower level managers of the hierarchy (or vice versa). If the contract is broken a new configuration is defined by evaluating the related performance model. It is then applied at each involved party (component or module), in order to reach a state in which the contract is fulfilled.

The adaptation mechanisms adopted in ASSIST completely instantiates the abstract schema provided above by organizing its leafs, left to right in an autonomic control loop (see Fig. 5). The trigger functionality is represented by the collection of the stream of monitoring data. Such data come from the running environment and can cause a framework reaction if a contract violation is observed. A component performance model is evaluated (policy phase) on the basis of the collected monitoring data, according to a selected goal (currently, in ASSIST we implemented two predefined policies, pursuing two different goals; for special needs, user-defined policies can be programmed).

If the QoS contract is broken, a decision has to be taken about how to adapt the component: such decision could involve a single component or a compound component. In the latter case, the decision has to flow through the hierarchy of managers in order to harmonize the whole application performance. The decision phase uses the policies in order to reach the contract requirements. Examples of policies are: reaching a desired service time (as seen above, it could happen if one VPM becomes overloaded), or realizing the best effort in the performance/resource trade-off (by releasing unused PE, as instance). The decision phase result is a target for the commit phase (increasing of computing Figure 6 MAM's reaction to a contract violation power, as an example). Such target is represented by a plan provided by the homonymous phase that lists the actions (e.g. add or remove resource to/from computation and computation remapping, with associated data migration and global state consolidation) to be taken. Finally, the execute functionality exploits support code statically generated by the ASSIST compiler, and coordinates it with services provided by the component framework to interface to the middle-ware (e.g. for resource recruiting), according to the schedule provided by timing functionality.

Timing functionality is related to the so-called reconf-safe points [START_REF] Aldinucci | Dynamic reconfiguration of Grid-aware applications in ASSIST[END_REF], i.e. points in the application code where the distributed computation and state are known to be consistent and can be efficiently synchronized. Each mechanism that is exploited to reconfigure the application at run time can take advantage (e.g. can be optimized) of reconf-safe points to appropriately orchestrate synchronizations in a transparent manner. Moreover, the generated code is tailored for the given application structure and features, exploiting the set of concrete mechanisms provided by the language run-time support. For instance, no state migration code is inserted for stateless computations, and depending on the parallelism pattern (e.g. stream versus data parallel), VPMs involved in the synchronization can be a subset of those within the component being reconfigured.

Our experiments [START_REF] Aldinucci | Dynamic reconfiguration of Grid-aware applications in ASSIST[END_REF] show that the adaptation mechanisms do not introduce overhead with respect to non-adaptive versions of the same code, when no configuration change is performed, and that issued adaptations are achieved with minimal (of the order of milliseconds) impact on the ongoing computation.

Fig. 6 shows the behavior of an ASSIST parallel application with adaptivity managers enabled, run on a collection of homogeneous Linux workstations interconnected by switched Fast Ethernet. In particular, it shows the reaction of a MAM to a sudden contract violation with respect to the number of VPMs. The application represents a farm computing a simple function with fixed service time on stream items flowing at a fixed input rate. In this scenario, a contract violation occurs when one of the VPMs becomes overloaded, causing the VPMs aggregated power to decrease. The MAM reacts to such decrement by mapping as many VPMs as needed to satisfy the contract (only one in this case) onto fresh computing resources.

In this example, when a new VPM mapping occurs because of the overloading of one (or more) of the allocated ones, removing the overloaded one does not lead to a contract violation. Therefore the MAM, that is also responsible to manage over-dimensioned resource usage, removes the overloaded PE almost immediately. The MAM can reduce resource usage also (not shown in this example) when the incoming data rate decreases or the contract requirements are weakened.

A COMPARATIVE DISCUSSION

As it is clear from the previous presentations, Dynaco (and its parallelcomponent specialization AFPAC) and ASSIST fit the abstract schema proposed in Section 2 in different manner. The frameworks have been developed independently with each other but both aim at offering a platform to handle dynamically adaptable components. Dynaco can be seen as a pipelined implementation of the abstract schema feeded by an external monitoring engine. In particular, the three major functions (decision-making, planning and execution) are specialized by componentspecific sub-phases. On the other hand, ASSIST provides a circular implementation of the schema leafs, while decision and commit can be seen as macro-steps of the autonomic loop. The decision-making functionalities are triggered by the external monitoring engine in Dynaco, while in ASSIST the concept of performance contract is exploited in order to specify the performance level to be guaranteed. In ASSIST the code related to the execution phase is automatically generated at compile time, while the Dynaco developer is asked to provide the code for policy, guide and action entities. Both the frameworks offer the possibility to configure certain points of the code as "safe-points" from which recovery/reconfiguration is possible. In Dynaco such points are defined by aspectoriented technologies, while in ASSIST they are defined by the language semantics, and determined by the compiler.

From the discussion above, it is clear that each framework affords the adaptivity problem by means of individual solutions. What we want to point out in this work is that, despite their technological diversity, both solutions can be inscribed in the general abstract schema presented in Section 2. Such schema is general enough to abstract from any kind of implementative solution but it is also sufficiently strong to catch the salient aspects a model has to consider while designing adaptive component frameworks. By summing up, it can be seen as a reference guide for modeling adaptable environments independently from the implementations, technologies, languages, constraints or architectures involved.

CONCLUSIONS

We have described a general model to provide adaptive behavior in Gridoriented component-based applications. The general schema we have shown is independent of implementation choices, such as the responsibility for inserting the adaptation code (either left to the programmer, as it happens in the Dynaco/AFPAC framework, or performed by exploiting knowledge of the high level program structure, as it happens in the ASSIST context). The model also encompasses user-driven as well as autonomic adaptation.

The abstract model helps in separating application and run-time programming concerns of adaptation, exposing adaptive behavior as an aspect of application programming, formalizing the concerns to be addressed, and encouraging an abstract view of the run-time mechanisms for dynamic reconfiguration.

This formalization gives the basis for defining a methodology. The given case study provide with valuable clues about how to solve different concerns, and how to identify common parts of the adaptation that can be generalized in support frameworks. The model can be thus also usefully applied within other programming frameworks, like GrADS, which do not enforce a strong separation of adaptivity issues into design and implementation.

We expect that such a methodology will lead to more portable and understandable adaptive applications and components, and it will also promote layered software architectures for adaptation, simplifying implementation of both the programming framework and the applications.

Figure 2

 2 Figure 2 Overall architecture of a Dynaco component.

Figure 3

 3 Figure 3 Architecture of AFPAC as a specialization of Dynaco.

Figure 4

 4 Figure 4 Scenario of an adaptation with AFPAC

Acknowledgments

This research work is carried out under the FP6 Network of Excellence CoreGRID funded by the European Commission (Contract IST-2002-004265), and it was partially supported by the Italian MIUR FIRB project Grid.it (n. RBNE01KNFP) on High-performance Grid platforms and tools.


Ga Ëtan Vaysse
email: gaetan.vaysse@irisa.fr

Franc ¸oise Andr
email: francoise.andre@irisa.fr

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

Using Aspects for Integrating a Middleware for Dynamic Adaptation

Keywords: D.3.3 [Programming Languages]: Language Constructs and Features, D.1 [Programming Techniques]: Miscellaneous, D.2.11 [Software Engineering]: Software Architectures dynamic adaptation, aspect-oriented programming, middleware integration

Middlewares are designed to hide common concerns in software development. One of the challenges in middleware development is to conceive how they can be integrated into applications in an efficient manner and at an acceptable cost for developers. This article reports results of practical experiences of integrating Afpac, a middleware for dynamic adaptation, thanks to aspect-oriented programming. Using current techniques, places where applications and middlewares can interact are limited to boundaries of application entities. In the case of Afpac, this is not sufficient. This paper details the issues that arise when integrating Afpac and proposes a set of features an aspect weaver should have to be usable in that case. As usual weavers do not provide those features, a weaver has been developed in order to demonstrate the feasability of this approach.

INTRODUCTION

In this paper, we consider that applications are assemblies of components built on top of middlewares. The word "component" abusively stands here for building block without any further detail. Integrating the use of middlewares into components requires a lot of code. Usually, this code is generic and disseminated. It explains why aspect oriented development is investigated in middleware development. Indeed, aspects provide means to introduce code at given places inside an application. In addition, the notion of aspect is very close to the one of concern. A concern can be seen as a set of behaviours responding to certain environment criteria. This notion takes an important place in middleware development as middlewares usually aim at extracting secondary concerns (such as security, distribution, and so on) from components. In that way, implementation details of those concerns are hidden to application developers. Aspect orientation can thus be used for the integration of middlewares with components. This allows developers to see middlewares as black boxes. They can then focus on the effective code instead of bothering with the integration code.

Afpac [START_REF] Buisson | Enforcing consistency during the adaptation of a parallel component[END_REF] is a middleware that captures the concern of dynamic adaptation. In order to use it, the developer has to introduce into his code some particular statements named adaptation points, which indicate where the middleware is allowed to make the component react to changes of its environments. The integration of Afpac requires the component to notify its middleware each time it enters control structures. In that way, Afpac knows the actual progress of the execution and can identify upcoming adaptation points.

The huge amount of statements to add makes manual integration of Afpac unpracticable. This paper focuses on how this integration can be hidden to developers. Section 2 describes how middleware integration is usually done. Section 3 details how Afpac must be integrated to a client code. It shows in what techniques described in section 2 are not sufficient in the case of Afpac. Section 4 depicts the features we propose for an aspect weaver to integrate Afpac. Section 5 shows how the integration of Afpac can be realized with such a weaver. A comparison with existing weaving techniques is given in section 6. Endly, section 7 gives some perspectives this case study opens to aspect oriented programming.

MIDDLEWARE INTEGRATION TOOLS

Middlewares aim at easing application development by providing high-level abstractions. Lying in the middle between applications and operating systems, low-level implementation details of those abstractions are completely hidden to the developers. For instance, usual abstractions provided by middlewares are communicating entities such as objects, components and services. Such middlewares mask as much as possible the implementation details of the communications between the entities.

Whatever the provided abstractions, middlewares have to be integrated into applications in an easier way than if the abstractions were reimplemented specifically for the application. Otherwise, middlewares are useless. Tools for easing middleware integration are thus of primary importance.

Interceptors

An interceptor is an element of a chain of responsability that can modify a given message. If messages are considered as reified method invocations, interceptors allow to alter the semantic of method invocation. For example, an interceptors can be used to execute code before and after invocations. They can also be used to implement transparently remote invocation to the component.

Services integration

A service is a communicating software entity that performs some expected task. It interacts thanks to message exchange. In order to be effectively integrated with services, an application often needs to have glue code directly written into it. This glue code has the responsability of managing interactions with services for example by generating and parsing messages.

Several services may be expected to perform semantically the same task. However, those services may assume distinct schemas for messages. When such services are integrated, the glue code is required to be duplicated for each possible schema. Letting the developer writes many versions of the glue code by its own is not acceptable.

One solution to this problem consists in adding an adapter to the code of the client. This adapter can be seen as an interceptor inserted between the client and the service. It depends on the service that the client connects to. This approach separates the concern of integrating the service from the application itself. If this adapter is built automatically as it is done with the WSML [START_REF] Cibran | Automatic service discovery and integration using semantic descriptions in the web services management layer[END_REF] project, the developer would not have to consider creating code for each possible schema.

If in addition the adapter is inserted dynamically, this approach makes the client able to benefit from service discovery services to select the best service independently of the schema it expects. Dynamic aspect weaving permits such a dynamic insertion. As described in [START_REF] Verheecke | Aop for dynamic configuration and management of web services in client-applications[END_REF], WSML does so: it redirects client requests to the right service. These redirection aspects, described in [START_REF] Verheecke | Aspect-oriented programming for dynamic web service monitoring and selection[END_REF], are plugged dynamically thanks to the JAsCo [START_REF] Cibran | Jasco for linking business rules to object-oriented software[END_REF] dynamic aspect weaver.

Whereas WSML targets web services, the same ideas apply to other kinds of entities when several semantically equivalent entities export syntactically different interfaces.

Container

In many component middlewares such as CCM [START_REF]The Corba Component Model specification[END_REF] or EJB, components are isolated from their outside world by containers. This entity is commonly used for handling life cycle and dependencies of the contained component like PicoContainer [START_REF]PicoContainer related[END_REF] does. Dependency concern can be solved using dependencies injection, i.e. outsourcing to an external entity the management of bindings. When a component explicitly describe its dependencies, its container can transparently resolve its bindings.

As interactions with the contained component are made exclusively through its container, the container is a natural placeholder for interceptors. In fact, the container itself may be seen as an interceptor. For example, CCM defines in its architecture portable interceptors to hook the control flow between components while it is within the middleware. Such a mechanism allows for example to implement the access control concern without any impact on the source code of the component.

Mixins

Alternatively to intercepting the interactions of the component, the middleware can be integrated by mixing the building blocks of the middleware with those of the component. For example, in an object-oriented environment, classes could be mixed. When two classes are mixed together, their functionalities are merged. This approach is in particular the one used in the implementation Julia of the Fractal [START_REF] Bruneton | Recursive and dynamic software composition with sharing[END_REF] component model to integrate controllers to the component.

Concretely, a mixin class can be seen as a declaration of the differences between a class and its specialization. However, as the general class is not specified, the specialization is generic and can thus be applied to many classes. Projects such as Jam [START_REF] Ancona | Jam -a smooth extension of java with mixins[END_REF] provide tools to apply mixins to classes.

Aspects

Aspect oriented programming aims at providing solutions to integrate concerns in applications where classical approaches such as object or component oriented fail. Aspects are particularly well suited for concerns that literally crosscut applications, i.e. concerns that do not fit well with the natural decomposition. It can be observed that the concerns taken in charge by middlewares commonly crosscut applications. This makes aspect oriented programming a promising mean to integrate middlewares.

Techniques used to weave aspects are various. The language can be domain-specific as with AspectJ or JAsCo. Alternatively, as with Jac [START_REF] Pawlak | Jac : An aspect-based distributed dynamic framework[END_REF], aspects can be better integrated into the user code if expressed with the same language as user code. Aspects can be woven at compile-time (AspectJ) or load-time (Jac). Most aspect languages are designed for object-oriented environments. However, the concept of aspect can be applied to other paradigms. For example, Aspectual Caml [START_REF] Tatsuzawa | Aspectual caml: an aspect-oriented functional language[END_REF] implements aspect weaving for functional languages.

Relations between tools

Interceptors are software elements placed between the client that invokes a method and the component targeted by the invocation. Installing an interceptor can thus be seen as weaving an aspect around the invocation and/or the method. In fact, the cited example of WSML uses aspect-oriented techniques to install its interceptors. Containers, as placeholders for interceptors, may be useful to implement the weaving process around those join points. Conversely, as containers intercept interactions with contained components, aspect-oriented programming can be used to generate containers. The former approach is similar to [START_REF] Eterovic | Managing components adaptation using aspect oriented techniques[END_REF]; the latter is the approach of Jac that relies on aspect weaving to generate customized containers.

As for specialization in object-oriented design, a mixin class is allowed to redefine methods of the base class. In that case, mixin is one way to install an element in the responsability chain for the invocation of the method. Mixins thus seem to provide a superset of the interceptor features.

Mixins have been described as a declaration of generic specializations of classes. At a very low level of abstraction, an aspect can be seen as a declaration of a transformation of a software entity. In fact, specializing a class consists in introducing and redefining attributes and methods. This kind of transformation is usual in aspect-oriented programming. Mixins may thus be considered as a subset of aspects.

INTEGRATION OF AFPAC

Afpac is a middleware made to simplify the development of dynamically adaptable components. As its role is not related to interactions between components, it is integrated mostly inside components, instead of between them.

Requirements

As the core of its interactions with the component, Afpac introduces the notion of adaptation points, i.e. places in the control flow where the component behaviour can be modified to handle changes in the environment. For instance, in the context of grid computing, when new processors are added, the middleware may decide to make the component adapt itself so it takes the new nodes into account. In that case, adaptation points denote states at which data are not transient and can thus be redistributed.

To make its decision, the Afpac middleware needs to know precisely the state of the component. That is to say: for conditional instructions, which branch has been entered; for loops, what is the current iteration; and so on. These information are checked against a control flow graph that is given to Afpac. Thanks to this static model, the middleware can predict the next adaptation points in the execution. Those points are the one allowed to execute the adaptation.

Annotations

In order to allow the Afpac middleware to track the execution, the middleware has to be notifed by the component of its dynamic behavior upon each control structure. Figure 1 shows how the code of the component must be annotated to perform this notification.

1 i n t f ( i n t i ) { 2 F u n c t i o n E n t e
r ( " i n t f ( i n t ) " ) ; 3 i n t r e s u l t ; Interestingly, the presence of annotations does not depend whether it is the first or second branch of the conditional instruction that is chosen, but if at least one of them contains an adaptation point. It does not depend either on any run-time context. Annotations can thus be added statically. Moreover, the manner the code has to be annotated remains constant and seems automatic.

In addition, any function that contains an adaptation point must be considered as an adaptation point itself. In the given example, any function calling "f" should thus be annotated in the same way. On the other side, control structures and functions that do not contain any adaptation point should not be modified as Afpac does not need to track the progress of their code. Not annotating those structures lowers the overhead. During the integration, the transitive closure of the call graph is required to determine precisely which control structures and functions should be modified.

Control flow graph

In addition to annotations for tracking the execution of the component, the Afpac middleware requires a static representation of the control flow graph of the component. Afpac expects this structure to be a tree view of the hierarchical task graph in order to preserve high level constructs such as loops. This structure can be obtained by modifying the source code of the component. Figure 2 shows the modified code of figure 1 for the control flow graph, where comments recall the original source code. Although the resulting source code differs from the one for annotations, the criteria for deciding whether a control structure or a function should be modified are the same in both cases.

1 // i n t f ( i n t i ) { 2 F u n c t i o n * f = new F u n c t i o n ( " i n t f ( i n t ) " ) ; 3 // i f ( i > 0) 4 C o n d i t i o n a l * c = new C o n d i t i

Integration

As Afpac aims at capturing the concern of dynamic adaptation, developers of components should not bother about it. Figure 3 shows the highest level of intrusion that can be acceptable to use a middleware for dynamic adaptation: developers only have to put adaptation points. They should not have their view of the code polluted by additional statements. Tools described in section 2 are useless in the case of Afpac. Indeed, those tools focus on integrating functionalities between components, whereas dynamic adaptation is internal to each component.

1 i n t f ( i n t i ) { 2 i f ( i > 0 ) { 3 g ( ) ;
Nevertheless, the two required modifications can be easily seen as transverse functionalities as they are disseminated through the whole code of component. Aspect thus seems a particularly well suited concept for expressing the integration of Afpac to components.

FINE GRAIN WEAVER

Our static weaver, called Taco, focuses on the features required to weave the use of Afpac to a component, while remaining usable in other contexts. It weaves C++ codes.

Join points

Join points weaved by Taco are the control structures. Internally to the weaver, they are organized as a tree that is close to the abstract syntax tree of the target source code. Join points are reified as triples containing:

• One type: loop; conditional instruction; call; unconditional branch instruction; and so on.

• Some parameters: for example a boolean expression for a conditional instruction; two instructions and a boolean expression in the case of a for loop.

• Some bodies: two for a conditional instruction; one for a loop; none for a unconditional branch instruction.

Advices

Aspects are declared with a domain-specific declarative language. They associate cuts, subsets of join points, to advices. However, manipulating control structures with the required expressiveness would require so much language constructs in a purely domain-specific language that it would be too complex. For this reason, in addition to quoting C++ code, advices are given the ability to perform static manipulations of the join points they are applied to. Those manipulations are expressed through commands within advices thanks to a general purpose language.

While it permits an easier integration of the elements of the reified join points inside the inserted code, commands can be used to generate code depending on the context of the join point. They can be used for instance to transform a for loop into a while loop without having to create specialized constructs. Figure 4 shows an advice that does that modification. Commands are used to access and paste the different elements of the for structures.

. $) braces

The weaver exposes to commands the reified form of join points. As commands are executed statically, no support for reflexivity in neither the target program nor the target language is required.

Commands can also be used to generate additional data that can be seperated from the woven source code. Such data may even be perssitent, and used during another weaving process. They can also be used to generate source code. For example, it could be used to generate new symbols while enforcing their uniqueness.

Pointcuts

The pointcuts of that weaver are patterns that comes in the form of boolean expressions. Some operators offered for these expressions can be used to access the environnement of the current join point, i.e., the preceding or following join points, and its parents or children. There is the possibility to check the environnement of the current node against certain conditions. A join point may be a cut depending on the result of such a check. As Taco weaves statically, pointcuts are evaluated statically. For this reason, tests available for writing pointcut expressions check static properties of the join points. For example, Taco provides test operators on the current point, (is it a for ), its parent, or other indirect ancestors (is it within a for ), and its inner points (does it contain a for ).

Like the advice system, the pattern system allows to issue commands to the weaver. The aspect developer can then create custom check operators. He can also maintain internal state structures to use during the tests. Those structures can persist and be used through the whole weaving process.

Implementability

Weaving control structures means modifying recursive structures, because a control structure body can contain other control structures. Thus, a join point can contain other join points of the same kind. Working on a recursive view of the program is more difficult than working on non-recursive view. For example, it could prevent the weave operation to terminate if introduced code is allowed to be weaved. In addition, modifications made on a point may discard its inner points or modifications made on them. That can happen if the current join point is replaced by some other code without using parts of the former version. The parts that were not put back are then lost for the result of the weaving process, possibly preventing some cuts to be satisfied. It then raises the question whether those parts should be weaved.

Instead of answering these questions, it was decided that the weaving process would work bottom-up. A point is always weaved before its surrounding control structure. That way, if the surrounding control structure is only partially reintroduced, the inner points have already been weaved, whether they will be cut or not. That maximizes the numbers of weaved points. As a sequence of statements is always weaved from first to last, it creates a partial order for weaving join points.

As commands allow to pass data from a join point check or advice application to another one through global variables, aspect designers are given an internal state of the weaving process. Having a constant and known sequence of the weaving process helps developing aspects taking profit of it.

INTEGRATION OF AFPAC WITH TACO

Inserting the annotations shown in figure 1 can be done using the same construct than the example of figure 4. Calls to Afpac can be inserted at the requested points of the control structures. Thanks to commands, a unique identifier can be generated to create a variable to hold the parameter value of the return statements. Thanks to this, the return statement can be moved to the end of the function in order to ensure its uniqueness. Making global the variable used in commands for this identifier allows to modify consistently all return statements.

The criteria for deciding whether a control structure should be annotated or not can be implemented thanks to the environnement checking capabilities: inner join points can be checked against certain conditions, such as the presence of an adaptation point. Moreover, instead of computing for each call the transitive closure of the call graph, the internal state of the weaver offered by commands can be used to maintain a database of functions containing adaptation points.

Endly, the extraction of the control flow graph has been done thanks to the capabilities of the general-purpose language embedded in the aspect language. For simplicity reasons, the aspect does not actually modify the source code of the component; it generates the modified form to an alternate output stream. Using data transiting from one point to the other allows to generate links between the different nodes. The strong assumptions it makes on the weave order and its unusual behavior for aspects make this application of Taco on the borderline between aspects and program transformation.

DISCUSSION

Most code weavers are used in object oriented languages. They usually focus on the call graph or dataflow of the application allowing the user to modify the code where a function is called, or directly at the beginning or the end of that function. They also often allow to introduce new members or methods to classes. Their view of the program is more macroscopic than the one of Taco.

Differences in the weaving level

The reason why so few projects interest in fine grain weaving may be the lack of applications of this weaving level. In many applications built by making objects interacting with each others, the global behaviour of the application is obtained thanks to those interactions even if object methods retain particular functionality. Changing the behaviour is most easily done by changing the interactions. Modifying the implementation of the methods could be seen as being too close to the program working, whereas in some cases like Afpac, it is necessary.

Another reason for fine grain weaving to be neglected is that slicing the code offers similar possibilites. Instead of weaving a loop, the loop and its body can be separated from the surrounding code in new methods. Modifying the behaviour of the loop body can be done by weaving the corresponding method. The same applies for the loop itself. This concept can be brought further, by encapsulating control structures in objects. Control structures can then be manipulated directly without using a weaver, but it would make writing code harder and unnatural. For instance, writing a conditional would requires to creates an object with two methods, one for each branch. A pro of this method is that it would add a low level reflexivity to the control structures of the program, presenting them in an already reified form, like Taco does.

Nonetheless, some efforts are made to integrate some control structures in aspect oriented languages. University of Manchester proposes in [START_REF] Harbulot | A join point for loops in aspectj[END_REF] a solution to add a loop join point in AspectJ. Their approach differs from ours as the loop detection occurs after compilation. It also takes the iteration space into account. In this case, the detection has to be done on bytecode, which is more difficult than detecting it on the source code, as lesser information are available. The ability to detect loops is strongly dependent on optimizations made by the compiler. In some cases of nested loops, it may even be not possible to weave around the inner loops.

On the other hand, by working before compilation, Taco is insensitive to compiler optimizations. However, relying on high-level constructs of the language, Taco misses loops built manually by the developer thanks for example to the "goto" statements.

Command system

As the user has to work on a closer view of the modified code, the langage used to modify it becomes wider. There is more control structures and parameters for them in a language like C++ or Java, than there is constructs for specifying objects. Each of loops, jump tables or conditional instructions has its own set of parameters. On the other hand, constructs like interfaces, classes and operations, have lesser parameters. That would make a purely domain specific language too restrictive or too complex to be a good choice for aspects at the level of control structures. This is why commands have been integrated to the aspect language.

A command system has been integrated to allow more interactions with the control structure parameters, it can also be used to modify the aspect behaviour. The commands can be used to collect information on the weaved code, and to pass them from a pointcut pattern operation or an advice to an other one. Those information can also be stored, offering ways to use it after the weaving process finished. This present the user with new possibilities.

One of them is the possibilities to make aspect adapt to the context of its execution. Command variables scope can be larger than a particular join point. It can be the whole weaving process. It can be used to make the weaving process global to the source file, not weaving each join point independently.

But because of this approach, the current implementation of the model extraction aspect works mostly as a stack automaton that takes as inputs the constructs that have to be weaved. This is required to generate links between related nodes of the generated graph as they involve pairs of objects created from distinct join points. For example, the link indicating that a statement belongs to a loop requires the model of the statement created at the statement join point and the model of the loop created at the loop join point. If the weaver permitted the aspect to associate attributes to adviced join points, the aspect would be able to avoid any global variable, and thus any assumption over the weaving process. One counterpart of commands seems to be the temptation for aspect developers to forsake the declarative part of aspects and perform compile-time reflection.

OPEN ISSUES AND PERSPECTIVES

As it has been previously said, the aspect used to extract the control flow for Afpac may be nearer from program transformation programs than aspects. This result can be explained by the following points.

Firstly, despite the presence of statically interpreted commands in advices, Taco appeared unable to modify enough the structure of the weaved source code. This aspect would indeed require to be able to transform any construct of the C++ language into the creation of an instance. For example, it should be able to replace the declaration of a class by the declaration of a variable. In that case, it could even be questioned whether the result of weaving an aspect has to be syntactically correct with regard to the language of the input source code. For example, the control flow graph aspect might have resulted in an XML document instead of a C++ program that instantiates the graph objects.

Secondly, extracting the control flow graph from a program can be questioned whether it belongs or not to the definition of aspect weaving. Surely this is a concern that crosscuts programs. In addition, in the case of the integration of Afpac, pointcuts are interestingly the same for choosing the structures to reify in the control flow graph and those to annotate. For this reason, it is strongly desirable to perform both tasks with the same tool.

Whereas other aspect weavers forsake control flow primitives as join points, it could be used in other context than Afpac. For example, diffenciating automatically a program requires to reverse the order of the instructions. Thus, it requires to modify the control flow. Currently this kind of modification is done by ad-hoc tools such as TAPENADE [START_REF] Hascoët | The tapenade ad tool[END_REF]. It would be valuable to express them as aspects, which would permit to separate the manipulation of program from the differenciation. Similarly, weaving aspects at the level of control structures may allow to declare loop parallelization as an aspect. Again, this would avoid the need for specialized tools.

4 5i

 4 f ( C o n d i t i o n a l E n t e r ( i > 0 ) ) { 6 g ( ) ;

7 a 9 } e l s e 10 r 14 }Figure 1 :

 7910141 Figure 1: Adaptable code

4 a 6 } e l s e 7 return h ( ) ; 8 }Figure 3 :

 46783 Figure 3: Almost original code

1 r 2 $ 4 $ ( 5 echoFigure 4 :

 12454 Figure 4: Transforming a control structure, commands are in $( . . . $) braces

  o n a l ;

	5	//	{
	6	//	a d a p t a t i o n P o i n t ( ) ;
	7	c->i f T r u e ()->append (new A d a p t a t i o n P o i n t ) ;
	8	//	} e l s e {
	9	//	}

10 f ->append ( c ) ; 11 // } Figure 2: Control flow graph