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

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

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

DYNAMIC ADAPTATION OF PARALLEL CODES: TOWARD SELF-ADAPTABLE COMPONENTS FOR THE GRID

Keywords: Grid computing, dynamic self-adaptation, parallelism, software component, reflexive programming

One of the challenges that come from the emergence of Grid architectures is to invent new programming techniques for these new platforms. As we explain in this article, we think that the architecture of the applications should reflect both the parallel and the distributed aspects of Grid architectures. It results in applications built as assemblies of parallel components. Since Grid architectures are known to be highly dynamic, using resources efficiently on such architectures is a challenging problem. Software must be able to react dynamically to the changes of the underlying execution environment. In order to help developers to create software for the Grid, we are investigating a model for the adaptation of parallel components. This paper focuses on the adaptation mechanisms that are provided as a meta-level for components. We describe how a generic platform can help to develop efficient Grid software. First experimental results show the gain that can be expected from the use of such a platform.

Introduction

Research in Grid computing mainly focuses on the development of middleware and services allowing applications to use various distributed resources. Infrastructures and toolkits such as OGSA [START_REF] Foster | The physiology of the grid: An open grid services architecture for distributed systems integration[END_REF] and previously Globus [START_REF]Globus toolkit[END_REF] provide tools allowing naming and discovery of resources; they also provide the necessary services for applications to deal with the underlying heterogeneity of the Grid. Those projects provide the users with useful tools for deploying and running applications without explicitly dealing with the various batch queues, communication libraries and so on, installed on the local sites.

Although resource allocation and scheduling are taken into account, these tools give no help for applications to make efficient use of the available Grid resources at run time. Due to the dynamic nature of the Grid, it is also very hard to design an application that fits well with any configuration of the Grid. Moreover, constraints such as the number of available processors, their respective load level, available memory and network bandwidth are not static. The bandwidth between sites running some parts of the same application may vary during the execution time or some processors may be requested by other applications. For example, the CPU manager described in [START_REF] Martorell | The NANOS resource management system[END_REF] may dynamically change the number of processors allocated to each application. We think that in many cases, application performance can be greatly improved when any part of an application can take into account varying resources eg. is able to adapt its behavior to "environmental changes".

Because Grid applications are also quite complex, many approaches now rely on service-oriented technologies such as OGSA [START_REF] Foster | The physiology of the grid: An open grid services architecture for distributed systems integration[END_REF] or on component-based approaches [START_REF] Szyperski | Component software: beyond object oriented programming[END_REF] such as CCM [START_REF] Omg | Corba components[END_REF]. This helps building reusable software. Within these programming techniques, one of the main issue is the so called "separation of concerns" paradigm. Entities implementing distinct functionalities should be located in different modules, objects, services or components. In the remaining of this paper, the term "component" stands for any of these kinds of pieces of application.

Our work focuses on the problem of adapting parallel codes encapsulated in components to varying constraints on resources. In this paper, we show how to combine parallel programming and adaptation techniques in a unified framework. As a first step, this paper focuses on the adaptation of the inner parallel code of a component. In section 1.2, we describe parallel objects and parallel components. Section 1.3 is devoted to the presentation of adaptation techniques in the context of scarce resources, putting the emphasis on the description of the ACEEL framework. Section 1.4 presents the application model we consider. Section 1.5 explains how we transpose adaptation models to the parallel case to build a unified framework. The results of our experiments are given in section 1.6. As a conclusion, we describe the main steps of our ongoing work.

Parallel distributed objects for the Grid

During the last decade, improvements have been made in terms of software reusability when object then component technologies appeared in many application fields other than high performance computing. Because Grid architectures are complex, heterogeneous and dynamic, they make the development of parallel applications more complex. Now, it becomes necessary for high performance applications to adopt technologies enforcing code reusability. Wellknown component models such as CCM or Enterprise Java Beans should be a good basis but they were not designed with performance and parallelism in mind, so they have not been able to take into account High Performance Grid applications.

In order to improve these environments, several projects have studied how parallel code could be encapsulated within objects or components. Projects such as PARDIS [START_REF] Keahey | PARDIS: A parallel approach to CORBA[END_REF] and PaCO++ [START_REF] Denis | Portable parallel CORBA objects: an approach to combine parallel and distributed programming for grid computing[END_REF] have focused on increasing performances of parallel distributed objects. They consider a parallel object as a set of identical sequential objects. The same definition also applies to GridCCM [START_REF] Pérez | A parallel corba component model for numerical code coupling[END_REF] within the component world.

Those projects allow to encapsulate SPMD code into so called "high performance CORBA objects/components". When a parallel object/component has to process a remote call, each process executes one part of the processing related to one part of the data set. The parallelism comes from the distribution of the parameters.

In order to get some performance out of high-speed networks, an enhanced request protocol has been defined among parallel objects/components: servers allow their clients to "see" their internal structure and distribution at run time. This allows parallel clients to send data directly from the source process to the target process: data do not need to be received/sent by a single master object. This multi-port communication mode allows to use the aggregated bandwidth, which can be higher than if only one centralized communication port was used.

These approaches have shown that it is now possible to use component-based techniques for programming high performance applications on the Grid without loosing performance. The next step is to be able to have components that are more flexible to allow the adaptation (not only the configuration) of parallel codes.

Dynamic adaptation of components

In the area of wireless computing and mobile environments where resources are a key issue, many techniques of dynamic adaptation have been developed: from the observation of the environment, codes can adapt their behavior to fit the resource constraints. This adaptation can be achieved in many different ways ranging from a simple modification of some parameters to the complete exchange of the running code with a new one that is more suited to the environment.

The adaptation could be achieved by designing ad hoc applications that take into account the specificities of the targeted environment. For example, this was done for the Web applications access protocol on mobile networks by defining the WAP protocol [START_REF]Wireless Application Protocol 2.0[END_REF]. A more general way to allow an application to evolve according to its environment is to provide mechanisms that permit dynamic self-adaptation by changing the behavior depending on the currently available resources. In many cases, this has been achieved by embedding the adaptation mechanism within the application code. For example, the AdOC compression algorithm [START_REF] Jeannot | Adaptive online data compression[END_REF] includes such a mechanism to change dynamically the compression level according to the available resources. However, it is desirable to separate the adaptation engine from the application code in order to make the code easier to maintain and to easily change or improve the adaptation policy. In this case, a framework that provides generic mechanisms for the adaptation process and for the definition of the adaptation rules is needed. This is the case for example of the ACEEL framework.

-context + Interface() -context + Interface() Behavior3 Behavior1 -context Meta-level
ACEEL [START_REF] Chefrour | Développement d'applications en environnements mobiles à l'aide du modèle de composant adaptatif aceel[END_REF] is a generic framework for self-adaptable components that allows the developer to focus on the implementations of the functionalities of his component and on its adaptation policy: it separates the adaptability aspect from the functional part of the component, as shown by the architecture of an ACEEL component on figure 1. Based on the Strategy design pattern [START_REF] Gamma | Design Patterns: elements of reusable object-oriented software[END_REF], the component offers a set of possible implementations, called behaviors. At any time, only one behavior is active: the one that processes the incoming requests. The generic adapter meta-object decides which of the available behaviors the best to use according to the environment is. To help the adapter object to decide, the component developer provides a policy as a set of event-based rules: each rule is a triggering change of the environment associated with a reaction, which might be either the activation of another behavior or the tuning of some parameters. When a change in the characteristics or availability of a resource happens, the monitoring engine notifies the adapter of the components that depend on this resource for their adaptation policy. The context holds the state of the component. Separating the state from the implementation makes it easier to replace dynamically the implementation of the component.

A programming model for Grid applications

The applications we target in our project are "Grid applications"; they may be composed of several parallel codes, so in our model, an application is considered to be built as an assembly of components. Each component is deployed on a site that is a parallel machine such as a cluster. As a first step, we focus on the deployment and execution of one component and we do not investigate the relations between components. In our model, each component is both parallel and adaptable.

A component is parallel: this means that it is composed of a number of internal processes working together to execute a given service. These processes communicate between each other using a communication library such as PVM or MPI or through a distributed shared memory. Here, we do not require specifying how those processes are encapsulated within the component: this aspect relies on constraints of existing components platforms such as GridCCM.

A component is adaptable: the platform where components are deployed can monitor the resources of the deployment site and allow any component to react to any change in the state of the resources.

We think that it makes sense to allow one single component to adapt itself dynamically in most Grid environments for two main reasons. First, one characteristic of Grid architectures is that sites are administrated independently one from another and of the users of the Grid. It is thus possible that the site into which the component is deployed is modified while the component is running. Secondly, in a longer term, we can consider component migration as a special case of adaptation. Because the sites implied in the migration may have different characteristics, the adaptation of the component will be needed.

Adaptation of parallel components

A parallel self-adaptable component is a component that is composed of several processes working together and that is able to change its behavior according to the changes of the environment.

Structure of the components

The structure of parallel self-adaptable components includes an adaptation policy, a set of available implementations, called behaviors, and a set of reaction steps.

The purpose of the adaptation policy is to define when the adaptation mechanism should be triggered and what should be the associated reactions. It is mostly a set of event-based rules. Each rule associates a reaction to a specific event. Events represent any change in the state of the environment. For example, an adaptation policy can include the rule: "if the number of nodes is increased, spawn new processes and redistribute arrays". This rule shows both the trigger event and the associated reaction.

Behaviors are implementations of the component. Each behavior differs from the others in the way it uses resources and/or in the algorithm used. Each behavior of a component implements the whole interface of the component; they just use different ways. The active behavior is the one used to process the incoming requests. The expression "functional code" denotes any code that is productive and that resides in the behaviors.

Reaction steps are the means by which the component adapts itself. It can be for example the replacement of the active behavior, the tuning of some parameters, or the redistribution of arrays. These pieces of code are dynamically inserted in the execution flow when the component adapts itself. Reactions must ensure that they leave the component in such a consistent state that the execution can resume and lead to the same result than if no reaction has been executed.

Because reactions must enforce the consistency of the component, reaction steps cannot be inserted at any time in the execution flow. In order to specify the places at which the component is able to adapt itself safely, we define the notion of adaptation point.

Semantic of adaptation points

An adaptation point is an annotation in the code that indicates where the component can be safely modified. The developer indicates that the behavior is able to suspend in a consistent state and to resume from this state at an adaptation point, no matter which behaviors and reaction steps combination leads the component to that state.

The platform enforces the mutual exclusion between the functional code and reactions: it ensures that reactions might only be executed when the functional code is suspended at an adaptation point. Adaptation points are thus the moments at which reaction steps can be inserted in the execution flow.

Reaction steps must ensure that if the state of the component is consistent, it remains consistent after the execution of the whole reaction. The scope of this consistency includes both the variables of the component and the active behavior. This means that the functional code should not be able to determine whether a particular reaction step has been executed at a particular adaptation point. Adaptation points are almost invisible to the functional code.

An adaptation point is said active when a reaction is scheduled at that adaptation point. Otherwise, the adaptation point is said inactive.

Introducing global adaptation points

Because several processes may collaborate during a single reaction, they need to be synchronized and coordinated. As for global consistent states in distributed systems, some of the combinations of adaptation points do not represent valid states at which the component is able to adapt itself.

Adaptation points are local to each process; so are the annotated states. For that reason, adaptation points are not sufficient to specify states at which the whole behavior can be modified. This is why the developer has to give explicitly a compatibility relationship between the adaptation points of each process of the behavior in order to allow the platform to find consistent states. The platform enforces the fact that reactions can only be executed when all the processes are suspended on adaptation points that are compatible with each other. Those global adaptation points specify global states at which the component is able to adapt itself, global states at which the developer permits the adaptation mechanism to be executed. Our model only specifies the semantic of global adaptation points: the developer should place them to indicate the global states at which he thinks the adaptation can occur safely.

Building a host platform

We consider that modern programming techniques should conform to the "separation of concerns" paradigm. For this reason, we think that adaptability should be a service given by the platform that hosts the component is deployed. Figure 2 shows the overall architecture of a platform hosting a parallel selfadaptable component.

The platform mainly provides two kinds of objects: the decider and the coordinators. The decider is the object that makes the decisions: it decides when (events to watch) and how (reactions to execute) the component should adapt itself according to the adaptation policy. It bases its decisions on the reports given by the monitors that are interfaced with the platform. The monitors are daemons that track and report changes in the state of the environment.

The coordinators execute the directives given by the decider: they serve as intermediaries between the code of the component and the platform. Their role is to synchronize the adaptation mechanism with the functional code and to coordinate the execution of the reactions. When a monitor detects a change in the state of the resources it watches, it notifies the decider. The decider then interprets the given adaptation policy. During this step, the decider might query the monitors for a detailed report on the state of the resources. If it concludes that there is no need to adapt, it stops the adaptation process until the next notification from a monitor; otherwise, it broadcasts its decision to the coordinators, which decide collectively when the reaction is effectively executed. This is done by selecting a global adaptation point -and activating the corresponding adaptation point of each process. Once a process reaches an active adaptation point, its coordinator executes the reaction chosen by the decider.

Experimental results

In order to validate the feasibility of our approach, we have built a prototype platform that partially implements the model we have proposed.

Test platform

The test platform we developed implements a subset of the model. It concentrates on SPMD applications. The adaptation points we implemented allow to execute user-defined reaction.

Although the application we use in our tests seems simple, it is sufficient to show that our adaptation model works well with parallel applications without significant performance degradation. Our application is a generic vector iteration that distributes its vectors using a block scheme. It uses MPI for its communications. Its adaptation policy is to use as many nodes as the monitor reports: it spawns new processes when nodes are added to the system and terminates the processes that use nodes reclaimed by the system. Because the MPI implementation we use cannot dynamically spawn or terminate processes, the application starts with a fixed number of processes, but uses only the reported number. For this reason, we simulate the monitoring of the number of available processors; this also allows us to have full-control over the adaptation mechanism. We place one adaptation point between iterations.

Gain of the adaptation

In this experience, once the application has been started, the number of available nodes is increased from 4 to 6. Figure 3 shows the elapsed time at the end of the iterations. The execution of the reaction occurs between iterations 12 and 13; this appears as a break on the curve. This figure shows that several iterations are needed in order to balance the cost of the execution of the reaction.

In the long term, the gain of the adaptable version over the original application is substantial. The amount of iterations needed before the adaptable version becomes effectively better depends on the reaction that has been executed and on the component itself.

Overhead of the adaptation platform

We compared the execution time of the original application and of its adaptable version in a totally static environment. The difference linearly depends on the number of encountered adaptation points. It shows the time needed to initialize the platform and the execution time lost in adaptation points. The execution time overheads are shown in table 1, depending on the number of encountered adaptation points. This measure is very noisy. The execution time lost in each adaptation point seems constant at about 0.2 milliseconds.

Ease of use

Our prototype assumes that the application is iterative and that adaptation points only reside between iterations. The reason is that it makes it easier to build the state of spawned processes. However, our model does not impose such a restriction.

One of the hardest questions to answer to when using the platform is the placement of adaptation points and their frequency. For our experiments, we arbitrarily place one adaptation point per iteration, but there was no a priori reason for doing so. Having many adaptation points makes the application more reactive to environmental changes at the cost of an increased overhead.

Conclusion

In this paper, we have shown that the idea of combining a dynamic adaptation framework with parallelism and distribution is a promising way for efficiently programming the Grid. We have built a prototype that extends the ACEEL adaptation engine to take into account the parallelism that can reside in components. This allowed us to experiment our ideas.

Our model complies with the separation of concerns paradigm, since it completely separates the adaptation mechanism from the functional code of the component. Moreover, it provides a basis for the dynamic adaptation of parallel code, whereas many projects have focused on their configuration at startup. This separation allowed us to experiment our idea without integrating a fullfeatured component platform. However, we expect that building application using a component infrastructure help doing the adaptation. Indeed, containers offered by the component infrastructures are a privileged place into which non-functional services (such as security or adaptation) should reside. Those containers also help doing the adaptation with their introspection ability.

In our ongoing works, we plan to define more formally the properties that the component is required to satisfy in order to be able to adapt itself. This includes the properties of global states where an adaptation can occur. The constraints on behavior replacement should also be investigated. The goal of those studies is to help the developer when establishing constraints on the adaptation. We expect this will allow to detect automatically valid adaptation points or at least to check that the points specified by the developer are correct.

Studying the relationship between fault tolerance systems that use checkpointing and adaptation in the context of Grid computing is an important perspective. Firstly, finding shared properties between checkpoints and adaptation points would be of great help in establishing properties and constraints on adaptation point placement. Secondly, fault tolerant systems suppose that the execution environment is dynamic since any fault results in changes in the environment. Keeping in mind fault-tolerance related works seems a natural approach since they share with adaptation the need to find "special points" at which the execution can resume. However, fault tolerance systems try to repair faults rolling-back the execution, whereas adaptation does its best until the code is able to react.

By the time, we have only studied the overall architecture for the adaptation of parallel codes. Our work is currently focusing on how to choose the global adaptation point at which the reaction steps should be executed. This work is going to lead to the definition of an algorithm to suspend the execution in a well-defined point without rollback.

We have no precise idea of the overhead required from the developer to make a component able to adapt itself using a generic framework. However, several examples exist of parallel codes made dynamically adaptable in an adhoc way and we expect that having a generic framework simplifies the task of the developer. In order to have a reasonable opinion about this subject, we plan to study how several parallel and distributed codes can be made self-adaptable. In particular, we think of how parallel discrete event simulators can be modified to adapt itself to the execution environment. We expect from these experiments to get a measurement of the work such a goal needs.

Figure 1 .

 1 Figure 1. Architecture of an ACEEL component

Figure 2 .

 2 Figure 2. Overall architecture of a parallel self-adaptable component

Figure 3 .

 3 Figure 3. Execution time of an adaptable application

Table 1 .

 1 Execution time for several iterations count

	Adaptation points Overhead (ms)
	50	264.9
	100	295.6
	150	304.3
	200	376.4
	250	278.5


Franc ¸oise André

Jérémy Buisson

Jean-Louis Pazat

Dynamic adaptation of parallel and distributed components on Grid environments

Wireless communication based applications always need adaptation techniques because the bandwidth and the resources of the network often change during the execution of an application. These applications are characterized by a low bandwidth, small data sets and low-end machines. At the opposite of the spectrum, Grid applications use powerful supercomputers, high bandwidth networks and process large amount of data. However, during an application run, both the bandwidth of the network and the computing resources may also vary. In this paper, we show than despite the difference between these kinds of applications, Grid applications can benefit from adaptation techniques primarily designed for wireless applications.

Introduction

In wireless applications, resources are a key issue. An application cannot even work if it is not able to take into account the constraints of dynamic resources. An application have to be able to modify its behavior according to the state of the environment which is reported by some hardware or software monitors. The adaptation of the behavior may be a fairly simple operation such as the adjustment of some parameters (level of data compression for example) or can be a dramatic change in the application such as the replacement of the whole code of the application. If adaptation mechanisms are embedded into the application code, it may result in the writing of an awkward and unmanageable code. Moreover, each time a new application is designed, the whole adaptation mechanism have to be though again, written and tested.

In order to separate the adaptation aspect from the application code itself the ACEEL framework [START_REF] Chefrour | Développement d'applications en environnements mobiles à l'aide du modèle de composant adaptatif aceel[END_REF] which provides mechanisms for adaptation policies description and implementation will be used as a basis for our study.

In most Grid applications, performance is a key issue. If an application "works" but does not take advantage of the available resources, its overall performance will be very low in many cases. Because application execution time are critical in these environments, applications are often scheduled to the best machines at start-up, but if new computing resources become available during run-time nothing is done to take profit of this fact. This is due to the fact that Grid application are parallel codes and the design of a parallel code is so difficult by itself that programmer would not like to add adaptation mechanism. However, if an adaptation platform is used as a complement of a Grid infrastructure such as OGSA [START_REF] Foster | The physiology of the grid: An open grid services architecture for distributed systems integration[END_REF] which provides tools for distributed and parallel computing, the overall performance of codes may increase dramatically.

This paper describes a way to handle the problem of adapting parallel codes to varying constraints on resources based on an adaptation framework primarily designed for wireless applications.

Dynamic adaptation of sequential components

Wireless applications need to be able to adapt their behavior to heterogeneous and volatile resources. A clear separation between the adaptation engine and the application code makes programs easier to maintain and allows one to easily change or improve the adaptation policy. In this section we describe the ACEEL framework [START_REF] Chefrour | Développement d'applications en environnements mobiles à l'aide du modèle de composant adaptatif aceel[END_REF] that provides generic mechanisms for the adaptation process and for the definition of the adaptation rules. This framework has been developed in our laboratory as a successor of the MolèNE project [START_REF] Segarra | Une plate-forme à composants adaptables pour la gestion des environnements sans fil[END_REF].

ACEEL has been designed as a generic framework for adaptable components. It separates the adaptive aspect from the functional part of the component, as shown on figure 1.

Each ACEEL component is separated in two different levels: the base level and the meta level.

The base level contains a set of implementations called behaviors among which only one is active at a time and processes the incoming requests. Within this level, the context holds the component's state in order to make easier the change of behavior. The context is also used as the only visible interface of the component in order to be able to use implementations with different interfaces.

Each behavior have specific resource needs, so a policy has also to be provided as a set of event-based rules: each rule is a condition on the state of the environment and is associated with a reaction which might be either the activation of another behavior or the adjustment of some parameters of the active one. The policy is used at the meta level by a generic meta-object called the adapter which decides which of the available behaviors should be used according to the environment changes.

A monitoring engine is used by the platform to merge the observations of different resources of the environment. When a change in the characteristics or

Parallelism and components

One of the main issues of today's programming techniques including parallel programming is to build reusable software. Current approaches rely on object oriented programming [START_REF] Meyer | Object-Oriented Software Construction[END_REF] and many developments now focus on component technologies [START_REF] Szyperski | Component software: beyond object oriented programming[END_REF] such as CORBA CCM [START_REF] Omg | Corba components[END_REF] or Enterprise Java Beans [START_REF] Mclaughlin | Java Enterprise Applications[END_REF]. Within these programming techniques, one of the main issues is the so called "separation of concerns" paradigm. Entities implementing distinct functionalities should be located in different modules, objects, services or components.

We think that the adaptation of a parallel program should be considered as a service for a component provided by a component server such as it is the case for transactions. The first step of this approach is to find or build a parallel component middleware/framework/architecture because the well known standard component architectures such as EJB or CORBA do not take into account the fact that an object may be implemented as a parallel code. The worst case is the EJB architecture which considers explicitly that beans cannot be multithreaded. The CORBA architecture allows to encapsulate parallel codes in CORBA objects but this leads to performance degradations: the inability of the platform to take into account the existence of several concurrent units in the component forces the platform to serialize the communications between parallel components. Some projects, such as PARDIS [START_REF] Keahey | PARDIS: A parallel approach to CORBA[END_REF], PaCO++ [START_REF] Denis | Portable parallel CORBA objects: an approach to combine parallel and distributed programming for grid computing[END_REF] and GridCCM [START_REF] Pérez | A parallel corba component model[END_REF], have focused on getting better performances out of a CORBA architecture. Those projects are aimed at efficiently encapsulating SPMD code into high performance CORBA objects or components. They consider a parallel object as a set of identical sequential objects. When a parallel object has to process a request, each object executes the part of the computation related to the data elements it is in charge of. Parallelism comes from the distribution of the parameters of the request. In order to rise the efficiency, an enhanced request protocol has been defined: the server allows the clients to see its internal structure and distribution. This allows the clients to send directly the data to the right sequential objects: data do not transit via a single master object anymore. This multi-port communication mode allows to efficiently use the aggregated bandwidth of the network which could not be used if only one centralized communication port was used.

These projects show that it is possible to include parallel codes into a component architecture without losing performance. In the remainder of this paper we will focus on the problem of using a generic adaptation mechanism to control and adapt parallel programs. Some practical component aspects will not be detailed but the whole framework is designed in order to be included in an existing or new component platform.

Modifying an adaptation platform for the Grid

The challenge is to use an adaptation framework devoted to wireless applications for parallel Grid components. The main difference is that the applications we consider are both parallel and distributed whereas wireless applications are mainly restricted to the client-server paradigm. The Grid applications considered here are built as an assembly of software components, each component being a set of communicating processes running on a cluster of workstations or on a parallel computer. We work here at the component level and we try to adapt one parallel component to environment changes; we do not consider yet the global adaptation of the whole application.

In our model, adaptation is a service that the platform gives to the components it hosts. Figure 2 shows the overall architecture of the platform hosting a parallel adaptable component.

Platform objects

The platform mainly provides two kinds of objects: the decider and the coordinators. The decider is the object that makes the decisions (the initiative of the adaptation and the choice of the reaction). It bases its decisions on the reports given by the monitors that track any change in the state of the environment.

There is no major difference between a decider for wireless applications and for Grid applications, except that the set of decision rules may be more complex in the case of Grid applications.

The coordinators execute the directives given by the decider: they serve as intermediaries between the code of the component and the platform. Whereas there is no need for coordinators in the wireless case, they are of major (importance) for parallel codes. Their role is to synchronize the adaptation mechanism with the functional code and to coordinate the execution of the reactions.

Components parts

In return for the adaptation service it provides, the platform expects from the component to conform to a given structure. A component is separated in two parts : a functional part and a meta-level part.

At the functional level, a parallel adaptable component should provide to its clients services specified by the interface such as an ordinary component. In addition, an adaptable component should include a set of behaviors allowing the component to be well suited for most environment changes. Each behavior contains a complete implementation of the component. Contrarily to wireless applications, each behavior might be either a sequential or a parallel implemen-tation. At any time, one and only one behavior is active, the one that processes the incoming requests. A behavior is a stateless object making it easier to keep the state in a separate place of the component. This is useful to switch easily from one behavior to another.

At the meta-level of the component, reaction steps should be provided by the programmer as the means given to the platform to modify the component: to react to a change in the environment, the component can execute on demand a sequence of reaction steps. Our model does not give any special semantic to these reaction steps except that it provides a way to modify a behavior or switch between behaviors.

The component must provide the platform with an adaptation policy, which is the component-specific counterpart of the decider. The purpose of the adaptation policy is to define when the adaptation mechanism should be triggered and what should be the associated reaction. It is mostly a set of event-based rules. Each rule associates a reaction to a specific event. Events are conditions on the state of the environment. For example, an adaptation policy can include the rule: "if the number of nodes is increased, spawn new processes and redistribute arrays".

The behavior can be safely modified at anytime while the component is inactive, whereas it is not the case while the component is processing a request. It must be suspended in such a state that it remains consistent after the execution of the reaction. Since this consistency completely depends on the component and on its implementations, the developer has to explicitly specify those states. The developer should provide the adaptation points which indicate states at which the execution of reaction steps preserves the consistency of the component. Reaction steps must guaranty that those states of the component remains consistent. Adaptation points define states through which the processes of a behavior run. For a given component, several behaviors may run through a common state. In such a case, the component can resume its execution with any of these behaviors. The existence of those common states defines the semantic correctness of behavior replacement.

In the case of a parallel program, the previous definition of Adaptation points can be used as local Adaptation points to each process. They are thus not sufficient to specify global states at which the behavior can be modified. This is why the developer has to explicitly specify global adaptation points through a correspondence relationship between the local adaptation points of each process of the behavior.

Coordination of the reactions

Because behaviors can be parallel and state distributed, the reactions cannot be executed by a single central object. Each process of the active behavior and of the state must participate to the execution of the reactions. If the reactions are executed independently by each process, the consistency of the component cannot be guaranteed. The component can also lock itself if processes are not coordinated, trying to reach unreachable states that do not correspond to any global adaptation point. This can be for example the case of an SPMD code like the one shown on figure 3. Say that when they receive a request to adapt the com- Fig. 3. Case where a component can dead-lock itself if the processes are not coordinated ponent, one of the processes have already executed the adaptation point i and the second have not. Without a coordination mechanism, the first process never reach another adaptation point because the second is waiting at the adaptation point i, executing the reaction. The component is thus dead-locked. This is why coordinators have been introduced in the model. Their purpose is to coordinate the action of every processes for the execution of the reactions.

Coordinators are the intermediaries between the adaptation mechanism, the functional part of the component and the reaction. They are totally passive objects: their activity comes from both the meta-level and the functional part of the component. They can be seen as a three part object: one part is directly plugged in each process of the functional part and implements adaptation points; the second part is more or less a singleton that is connected to the decision maker of the component, that is to say the decider; the third drives the execution of the reactions.

Sketch of an adaptation

When a monitor reports some interesting change in the environment, for example the presence of new available nodes, it notifies the decider, which in turn broadcasts an adaptation initiative to the coordinators. If one suppose that the active behavior is a SPMD behavior, the coordinators choose the adaptation points before the next operation to be executed. At the end of the current operation, the coordinators execute the reaction: they spawn a new process on the new node, then redistribute the data. The functional code can then resume its execution and benefit from the presence of the new node.

Conclusion

A first experiment based on a generic SPMD code shows that the overcost of the adaptation is very low and that better performance can thus be gained through adaptation. Our application is a generic vector iteration ; vectors are distributed with a block scheme ; communications use MPI. The adaptation policy is to use as many nodes as the monitor reports, spawning new processes when nodes are inserted in the system. We placed an adaptation point between each iteration. In order to evaluate the gain obtained by the adaptation, we increased the number of nodes from 4 to 6 while the test application was running. The figure 4 shows the elapsed time at the end of each iteration. The execution of the reaction oc-Fig. 4. Execution time of an adaptable application curred between iterations 12 and 13 ; this appears as a break on the curve. This figure shows that the adaptable version of the application needs some iterations after the reaction has been executed to become effectively better than the original one. This is due to the cost of the data redistribution and is not due to the platform itself. If the adaptation takes place early during the execution of the program there is a dramatic gain of performance.

This work is a first step toward the integration of a dynamic adaptation framework into a component based platform for Grid applications. In this paper, we have shown that it was possible to reuse the ideas developed for the adaptation of wireless application in a different application world. Our current prototype uses the ACEEL framework but is not yet included in a component infrastructure.

To our knowledge this is one a the first attempt to separate the adaptation mechanism from the functional code in the context of Grid applications. We think that it makes it far easier to build efficient applications for not only wireless or Grid environments but any environment with unknown and/or dynamic characteristics.

In our future works, we are planning to define more formally the properties that the component is required to satisfy in order to be able to adapt itself. This includes the properties of global states in which the adaptation is allowed to occur and the relation between fault tolerance and adaptation techniques. The constraints on behavior replacement should also be studied.

Fig. 1 .

 1 Fig. 1. Architecture of an ACEEL component

Franc ¸oise André, Jérémy Buisson, and Jean-Louis Pazat


Françoise André

Hinde Lilia Bouziane

Jérémy Buisson

Jean-Louis Pazat

Christian Pérez
email: christian.perez@irisa.fr

Hinde Andre

Jeremy Bouziane

Jean Buisson

TOWARDS DYNAMIC ADAPTABILITY SUPPORT FOR THE MASTER-WORKER PARADIGM IN COMPONENT BASED APPLICATIONS

Keywords: Software components, Grid, Master-worker, Dynamic evolution, Adaptability framework

When executing scientific applications, resources that may be used can vary from multi-core processors to grids. Therefore, abstracting the programming model enables portability on various resource infrastructures. Furthermore, software component technology appears to be a very promising approach to deal with the growing complexity of scientific applications. Hence, we proposed a model to improve the support of master-worker paradigm in component models. Capitalizing on our experience of adaptability frameworks, we propose to enhance our model so that master-worker applications can adapt at runtime to varying conditions. This paper studies how to transparently introduce adaptability in our model for master-worker applications, what impact it has on the model, and what requirements it expects from the adaptability framework.

Introduction

While computing grids are becoming more and more common, the question of their programmability is raising attention. The underlying motivation not only stems from the high complexity of grids that shall be hidden to programmers but it also comes from the increasing complexity of applications. In order to take advantage of the huge possibilities of grids, more complex applications like code coupling applications are getting popular.

Software component technology appears very promising to handle the complexity of both grids and applications. Code reuse enables to build complex applications based on validated building blocks while component composition provides a mechanism to support complex relationships independently of the architecture of the execution platform.

An example of such a relationship is the master-worker paradigm. While it is an algorithmic concept, its implementation varies quite a lot depending on the execution platform. Hence, we defined a high level master-worker relationship between components [START_REF] Bouziane | Modeling and executing master-worker applications in component models[END_REF][START_REF] Antoniu | Combining data sharing with the master-worker paradigm in the common component architecture[END_REF]. While it provides a model close to the abstract concept to the programmers, it can be configured by the execution environment to fit to the actual resources. However, this previous work did not consider dynamic adaptation. For example, the number of workers may change depending on the number of incoming requests or the number of available machines. The goal of this paper is to study how to introduce adaptability support in a master-worker paradigm and to evaluate the impact on adaptation frameworks.

The paper is organized as follows. Section 2 summarizes our model to handle master-worker (M-W) relationship between components as well as an analysis of various levels of adaptability. Section 3 presents our adaptability framework. Section 4 discusses different strategies to introduce adaptability within the M-W relationship. An example and its impact on the M-W model are analyzed in Section 5. Section 6 concludes the paper and presents some future works.

A high-level master-worker composition model

We proposed in [START_REF] Bouziane | Modeling and executing master-worker applications in component models[END_REF] to increase the abstraction level of component models with respect to the master-worker (M-W) paradigm. Our motivation is twofold. First, we aim to relieve programmers from dealing with resource dependencies, such as the number of workers to instantiate or request transport concerns. Second, we target to reuse existing master-worker environments, like DIET [START_REF] Caron | A Scalable Approach to Network Enabled Servers[END_REF], as they implement advanced request transport and scheduling algorithms.

The proposal defines a generic model, which we have projected to specific component models like Fractal [START_REF] Bouziane | Modeling and executing master-worker applications in component models[END_REF], Ccm and Cca [START_REF] Antoniu | Combining data sharing with the master-worker paradigm in the common component architecture[END_REF]. In this paper, we present it according to the Fractal formalism.

Overview

The model is based on the concept of collection, which is defined as a set of exposed ports, bound to some internal component type ports. A collection behaves like a component: it can be connected to other components. However, such a composition is done by an abstract architecture description, which represents the user's view of the application. Ideally, at deployment time, a collection is turned into a composite by defining an initial number of internal component instances and by selecting a request transport pattern. A pattern represents a request transport algorithm that may be used between master and worker components. It is a composite whose implementation should be done by some experts and can or can not be based on software components, such as DIET [START_REF] Caron | A Scalable Approach to Network Enabled Servers[END_REF]. Request transport patterns are defined independently of a collection. Figure 1 presents an overview of the concepts of the proposed model.

Need for dynamic behavior

The proposed model dealt with building a static master-worker application because the translation of the abstract collection to a concrete composite fixes the number of workers as well as a pattern at deployment time. However, such choices have to be dynamic to take into account modifications of the application behavior and/or of the resources. The application behavior encompasses collection level behaviors like the frequency and the kind of incoming requests, the number of requests waiting for a worker, or the number of connected masters. It also comprises application's level behavior when there are several collections within an application. Resource behaviors are made of standard considerations like availability, end of a resource reservation, etc.

For a collection, there are three elements that may be dynamically modified: 1) the number of workers, 2) the used pattern and 3) the tuning of the pattern.

For example, let consider an increase of the number of waiting requests. If the pattern is not the bottleneck, the solution is to add more workers if there are available resources. However, if the pattern is the bottleneck, either the pattern may by optimized or it has to be replaced by a more scalable one.

In order to help decision making, validity constraints may be attached to a pattern. For instance, a round-robin pattern can be adequate for one or a few connected masters, for equivalent request load and for homogeneous processors. If at least one of these conditions is not met, another pattern should be considered, like for example a load-balancing pattern or DIET.

A collection can also be modified to optimize resources usage. For instance, if there is a lot of workers compared to the number of requests, it can be suitable to remove some workers to release resources. Last, more complex situations occur when an application contains several instances of the master-worker paradigm. In such a case, re-structuring a collection should be coordinated in order not to be to the detriment of other collections.

A framework for adaptability

In a previous work [START_REF] Aldinucci | An abstract schema modelling adaptivity management[END_REF][START_REF] Buisson | Afpac: Enforcing consistency during the adaptation of a parallel component[END_REF], we have studied how to make applications suit varying conditions relying on the notion of adaptability. This work led us to develop a generic component framework for adaptability, Dynaco. Benefiting from a joint work with the university of Pisa [START_REF] Aldinucci | An abstract schema modelling adaptivity management[END_REF], this framework splits adaptability into four sub-functionalities: 1) the framework has to be able to observe characteristics of the environment in order to trigger adaptability; 2) when a change is detected, the framework has to decide an adaptation strategy according to observed measures; 3) once a strategy has been decided, the framework has to plan actions to implement it; at last, 4), planned actions have to be executed synchronously with the execution of applicative code. On the left of Figure 2, each sub-functionality is captured by a Fractal component.

Rather than reimplementing the components of the framework specifically to each application, developers are encouraged to focus on application-specific issues, thanks to the reuse of existing generic engines. For instance, we have experimented 3 generic engines for the decide component: 1) a Java virtual machine, such that the decision procedure is implemented with a general-purpose language, allows easy implementations of intuitive decision procedures; 2) the Jess [START_REF]the rule engine for the java platform[END_REF] expert system, such that the decision procedure is expressed with a domain-specific rule language (i.e. as a collection of ordered rules that looks like the following statement: "decide a given strategy when an associated con-dition becomes true"), allows efficient implementations of complex rule-based decision procedures; and 3) a genetic algorithm, such that the decision procedure is expressed as a function to optimize (e.g. the performance model of the application), allows to implement straightforwardly decision procedures when the application's behavior is well formalized, possibly with a higher runtime cost. As described, each engine proposes a different trade-off.

The same applies to the plan and execute components. For the former, for instance, a pattern matching based mapping from strategies to predefined plans suits well simple cases; while more sophisticated formalisms such as Strips [START_REF] Nilsson | STRIPS: a new approach to the application of theorem proving to problem solving[END_REF] (developers only declare the collection of possible actions as preand post-conditions) may be relevant when developers cannot predefine plans by hand. Similarly, synchronizing adaptation actions with the applicative code depends mostly on the applicative programming model: we have proposed an algorithm (Afpac [START_REF] Buisson | Afpac: Enforcing consistency during the adaptation of a parallel component[END_REF]) for any SPMD application. Other algorithms could be used such as Assist [START_REF] Aldinucci | Dynamic reconfiguration of grid-aware applications in assist[END_REF] when using its parmod skeleton programming model.

The observe component does not adhere to the same design: monitors are facilities provided by the environment itself that are wrapped into adapter components, which gather, aggregate and preprocess raw measures and events to their expected formats. The whole observe component is almost independent from the application and does not need any particular specialization.

As on the right of Figure 2, application-specific code is captured in policy, guide and a collection of actions, which respectively specialize the decide, plan and execute components. Using generic engines in that way is what makes Dynaco highly generic and open, while it encourages effective code reuse.

Design choices for adaptability in the M-W paradigm

This section studies how to make use of an adaptability framework such as Dynaco in the master-worker paradigm. It analyzes two major design choices we have identified: the choice of the adaptability strategy and of the architecture. The discussion is done with respect to three criteria: modularity, accuracy, and scalability. Modularity measures the possibility to compound strategies such as at the collection level and at the pattern level. Accuracy stands for the kinds of allowed adaptations while scalability refers to the number of components in the collection.

Strategy level

The first choice concerns the way to logically design the adaptation strategy, which can be monolithic, independent or coordinated.

Considering a single monolithic strategy, the global strategy should handle any possible situation and adaptation for the whole collection. Especially, it should consistently handle the adaptation at the levels of the collection, the pat-tern and the pattern implementation. For instance, observing that the request queue lengthens, instantiating new workers may increase the heterogeneity of processors, such that the pattern should be replaced by a more suited one (e.g. switching from round-robin to DIET). A monolithic strategy is able to handle those two adaptations at once. Assuming now that the bottleneck is the pattern, which may not be able to perform better, not even with a different implementation nor with additional resources. Being aware of all of the implemented patterns, a monolithic strategy has sufficient knowledge to detect such a situation and prevent useless workers. Therefore, high accuracy is provided. However, the major drawback is poor modularity. Indeed, the tight entanglement between adaptations makes it particularly difficult to add incrementally the support for new patterns, as well as to maintain the strategy, as any local modification may have an impact on the whole strategy. Worse, in the case of a multi-collection application, adaptations for all of the collections have to be handled by a single strategy at the level of the whole application.

Rather than designing the strategy as a whole, it may be better to decompose it such that the specification of the strategy for each adaptation is close to what is adapted. Basically, in order to allow good modularization, 3 sub strategies would be designed: the first one, attached to the collection composite, adapts the number of workers; the second one, attached to the pattern, selects a convenient pattern; and the last one, attached to the pattern implementation, optimizes the pattern. Two alternatives can be derived from this compound strategy. Each sub strategy may be independent or otherwise it may be coordinated. In the former case, independence means that no explicit interaction occurs from one sub strategy to the others. The latter case allows explicit interactions between sub strategies such that they can coordinate the adaptations of the elements of the collection. Any technique can be used to implement the coordination, such as triggering adaptations from other adaptations (propagating adaptations) or running a negotiation protocol (agreeing on adaptations).

Focusing on the independent approach, let us consider first the above example of adding worker instances that increase heterogeneity, which may result from different processors or from different implementations. Independence implies that the pattern switches its implementation on its own when it observes that heterogeneity increases, once the collection (independently) has instantiated new workers. Thus, despite their independence, the sub strategies achieve together the same adaptations as the single monolithic strategy. However, that way of observing effects of adaptations is not always enough to implement accurate adaptations. Consider that the queue lengthens. An accurate strategy does not instantiate new workers if the pattern would not be able to dispatch requests at a sufficient pace; and it does not optimize the pattern if there can't be enough workers to handle requests. However, independence of the sub strategies prevents the collection from knowing whether the pattern would be able or not to dispatch requests to additional workers; and it prevents the pattern from knowing whether the collection would be able to instantiate new workers.

In such a situation, this strategy would desperately preserve the status quo, even if the collection would be able to perform better; while lowering accuracy may lead to instantiate useless workers or to over-optimize the pattern. Last, the coordinated strategy promises to bring the advantages of the two other strategies without their drawbacks (Figure 3). It preserves compound strategies for modularity and scalability while letting a global vision to be built for accuracy. However, several adaptation modules have to be interconnected.

Achitecture level

The second design choice concerns the architecture of the adaptability. Two alternatives are identified: centralized and distributed.

A centralized architecture locates the whole adaptability management into a single location. With respect to the model presented in Section 2, it has to be into the membrane of the collection. Bindings are, nevertheless, present to enable it to control the whole collection. The centralized approach is compatible with all adaptation strategies described in Section 4.1. It also simplifies the implementation of the coordinated strategy as the communication between the different strategies may be embedded into the same adaptation framework. However, it raises an issue for the compound strategies with respect to the composition of components: the adaptation part of sub components needs to be injected into the adaptation part of the collection. Hence, the connection operator of the component model turns out to be more complex. As far as we know, there is no standard component models that permits it.

With a distributed architecture, the adaptability management is spread over the whole collection, and in particular in the membranes of the collection, of the pattern and of the pattern implementation components. The distributed architecture is not straightfowardly compatible with the monolithic strategy. However, it perfectly fits with the counpound strategies provided that the communications of the coordinated strategy are quite simply done through some ports. Considering the advantages of the coordinated strategy, we conclude that this strategy with a distributed architecture appears to be the best choice to deal with dynamic change in a collection.

Positionning

Only a couple of adaptability frameworks address the problem of coordinating and distributing adaptations. Dynaco is neutral as it does not prevent policies to coordinate on their own, but it does not provide any specific support.

Among the other frameworks, Aceel [START_REF] Chefrour | Plate-forme de composants logiciels pour la coordination des adaptations multiples en environnement dynamique[END_REF] and Plasma [START_REF] Layaida | Designing self-adaptive multimedia applications through hierarchical reconfiguration[END_REF], are fairly close to the constructive approach defended here, i.e. building global adaptations as the collaboration of individual local adaptations. With our previous framework Aceel, each component contacts other components before adapting, in order to ensure consistent and synchronized adaptation of the whole assembly. With Plasma, components impose their adaptations to the other ones through a simpler propagation mechanism. The contract-driven approach of Assist [START_REF] Aldinucci | Autonomic qos in assist grid-aware components[END_REF] is different: considering a hierarchical component model, composite components divide their contract in order to assign recursively subcontracts to their sub components. Coordination of adaptation is enforced by the submission of contracts that are consistent with another. However, this approach requires composite components to have precise understanding of the composition of their immediate subcomponents, in order to devise subcontracts.

Those frameworks are however tied to the programming models for which they have been specifically designed, often restricted to a fixed collection of predefined adaptations; while focusing only on adaptability, Dynaco integrates gracefully to any programming model. Dynaco also allows to design more specific and adequate solutions for each programming paradigm than other general approaches. Hence, Dynaco is a better start point.

Adapation example for a master-worker application

Based on the preceding analysis, this section discusses a design example for adaptability of a master-worker application. As outlined in Section 2.2, the adaptation aims at preventing the request queue from unacceptably growing, while making the queue contain enough requests to feed continuously the workers. In order to enforce that objective, we propose the following intuitive compound strategy, using the coordinated approach:

• at the level of the collection: if the request queue lengthens beyond a threshold, if the pattern is able to increase its dispatch rate accordingly and if there are available resources, then instantiate new workers; if the request queue shortens under a threshold, then terminate some workers.

• at the level of the pattern: if the number of masters or the variability of request durations increases above a threshold, or if the heterogeneity of workers increases beyond a threshold, then switch to the DIET pattern; otherwise, under a threshold switch to round-robin.

In this strategy, coordination (as it appears on Figure 4) occurs before the collection instantiates new workers. It actually asks the pattern whether it would be able to dispatch requests at a sufficient rate, for instance involving a contract renegotiation protocol. The length of the request queue cannot always be observed directly; lengthenings and shortenings can nevertheless be deduced from the comparison between arrival and service rates. Other observations are almost obvious. The example shows that the coordinated and distributed design suits well and that the necessary monitoring does not breach encapsulation. Now that an adaptation strategy is designed, the issue is to consider the impact on the proposed M-W model. Achieving the objective of transparent dynamic management, there is no need to modify the model at the user view level. The collection instantiation process seems to be more appropriate to introduce an adaptability framework. A collection implementation, in particular the collection and pattern membranes, are determined at this stage. Adding adaptability framework as controllers in appropriate membranes appears to be straightforward. Then, only the implementation of collection and pattern components are concerned by the use of an adaptability framework. However, the diversity of resource infrastructures and resource management systems lead to various adaptability policies. For instance, a policy can be more constrained by resource availability when resource sharing is privileged, otherwise it can be more constrained by application requirements. As a consequence, similarly as for patterns, the framework has to do a selection from a set of adaptability implementations. Fortunately, the specificity of Dynaco to be componentbased allows the use of different implementations. The master-worker model extended with adaptability support is presented in Figure 4.

Conclusion

The paper analyses how to design dynamic adaptability support for component-based master-worker applications. Among the discussed possibilities, coordinating several distributed adaptations appears to be the best-suited solution with regard to modularity, scalability and accuracy. In addition, integrating adaptability at the level of the master-worker abstraction achieves the goal of hiding the management of execution resources from the developers' sight.

Figure 1 .

 1 Figure 1. Overview of the master-worker model from the user and framework points of view.

Figure 2 .

 2 Figure 2. Dynaco as an assembly of Fractal components and their dependencies.

Figure 4 .

 4 Figure 4. Introducing dynamic management in the master-worker model.

  Summarized features of each alternative for the strategy level.

	Strategy		Accuracy	Modularity Scalability
		Collection Application
	Monolithic	High	None	None	Low
	Independent	Low	Low	High	High
	Coordinated	High	High	High	High
	Figure 3.

Among adaptability frameworks, none fully meets the requirements of our proposal. Its genericity and openness make Dynaco be the best start point. Based on the experience we gained in our previous work on Aceel [8][9], we plan to extend Dynaco with specific support for the coordination of distributed adaptations, so that it meets the requirements. We will also evaluate the proposed model on synthetic master-worker benchmarks as well as the possibilities to write generic adaptation policies at the collection and application levels.