Bart George
email: george@univ-ubs.fr

Régis Fleurquin
email: fleurqui@univ-ubs.fr

Salah Sadou
email: sadou@univ-ubs.fr

A Component Selection Framework for COTS Libraries

Component-based software engineering proposes building complex applications from COTS (Commercial Off-The-Shelf) organized into component markets. Therefore, the main development effort is required in selection of the components that fit the specific needs of an application. In this article, we propose a mechanism allowing the automatic selection of a component among a set of candidate COTS, according to functional and non-functional properties. This mechanism has been validated on an example using the ComponentSource component market.

Introduction

Component-Based Software Engineering allows developers to build a system from reusable pre-existing commercial off-the-shelf (COTS) components. The two immediate potential benefits for such an approach are reduced development costs and shorter time-to-market [START_REF] Voas | COTS software -the economical choice[END_REF]. For this reason, more and more software applications are built using COTS rather than being developed from scratch, as this is something that fewer and fewer companies can afford [START_REF] Ye | COTS product selection for safety-critical systems[END_REF]. However, due to the intrisic nature of COTS as "black-box" units put into markets by third party publishers, software development life-cycle must be rethought in depth [START_REF] Crnkovic | Component-based development process and component lifecycle[END_REF][START_REF] Tran | A procurement-centric model for engineering CBSE[END_REF]. In fact, COTS-based software development leads to constant trade-offs between requirement specification, architecture specification and COTS selection [START_REF] Brownsword | Developing new processes for COTSbased systems[END_REF]. In this context, it becomes impossible to specify requirements without asking if the marketplace provides COTS that can satisfy them. And one cannot specify an architecture without asking if there are COTS to integrate it.

In such a context, COTS selection becomes particularly important [START_REF] En | A brief literature review of enterprise software evaluation and selection methodologices: A comparison in the context of decision-making methods[END_REF]. So important that a bad requirements definition associated to a poor selection of COTS products can lead to major failures [START_REF] Maiden | Acquiring cots software selection requirements[END_REF]. There are also extra costs due to the investigation of hundreds of candidates disseminated into several different markets and libraries, not to mention the diversity of components' description formats. Finally, this phase can become so time-consuming that it may annihilate the initial promise of cost and time reductions [START_REF] En | A brief literature review of enterprise software evaluation and selection methodologices: A comparison in the context of decision-making methods[END_REF]. Therefore, the only solution to maintain these gains is to have a selection process [START_REF] Voas | COTS software -the economical choice[END_REF] that would be well-defined, repeatable, and as automated as possible.

In this paper, we propose a mechanism that allows application designers to select, among a vast library of candidates, the one that best satisfies a specific need, modeled by a virtual component called a "target component". Section 2 will detail existing approaches, as well as their limits. In section 3 we will present our own approach. Then, before concluding, in section 4 we will present a validation of this approach using ComponentSource [8] as a component marketplace.

COTS Selection Techniques

The issue is the following one: given a vast number of COTS components from all origins, disseminated in several different markets, how can the one that will best satisfy an application's specific need be chosen ?

Presentation of Current Selection Processes

Works in the field of component selection are trying to answer this fundamental question. C. Güngör En and H. Baraçli [START_REF] En | A brief literature review of enterprise software evaluation and selection methodologices: A comparison in the context of decision-making methods[END_REF] listed many of these works. This study shows that most selection processes provide at least the three following phases: evaluation criteria definition, prioritization of these criteria, and COTS candidates' evaluation according to these criteria. Usually, in order to achieve these phases, selection processes use multi-criteria decision making techniques (MCDM). The most used MCDM techniques are Weighted Scoring Method or WSM [START_REF] Mosley | How to assess tools efficiently and quantitatively[END_REF] and Analytic Hierarchy Process or AHP [START_REF] Saaty | How to make a decision: The analytic hierarchy process[END_REF]. WSM consists in using the following formula: score c =Σ n j=1 (weight j * score cj ), where weight weight j represents the importance of j-th criterion compared to the n-1 other evaluation criteria, and local score score cj evaluates the satisfaction level of the j-th criterion by candidate c. Thus, total score score c represents the global evaluation value for candidate c. Therefore, the best candidate is the one that has the highest total score. AHP is a technique that organizes the definition and prioritization of evaluation criteria. It consists in decomposing a goal in a hierarchical tree of criteria and sub-criteria whose leaves are available candidates. Inside each criteria-node, the importance of each sub-criterion is estimated compared to others. For example, the criterion "performance" can be divided in two sub-criteria "response time" and "resource consumption", the first sub-criterion having a weight twice higher than the second one. Then, one can use a formula such as WSM to evaluate each candidate c by aggregating local scores score cj1 , ..., score cjn inside each node j, and propagating all these sums to the root of the tree to get c's total score. Now, let us take a look at the contributions made by main works in the field of component selection. OTSO [START_REF] Kontio | A case study in applying a systematic method for COTS selection[END_REF] is considered as one of the first selection processes dedicated to COTS components. In addition to the three phases described above, it adds other ones such as pre-selection of COTS to identify potentially relevant candidates and limit their number (therefore it acknowledges the difficulty to manually evaluate too many candidates). PORE [START_REF] Maiden | Acquiring cots software selection requirements[END_REF] is a selection process that pleads in favor of a progressive selection. Candidates are filtered and their number decreases while the description of the needs becomes more accurate. DEER [START_REF] Cortellessa | Driving the selection of COTS components on the basis of system requirements[END_REF] is aimed at selecting single components, or assemblies of components, which satisfy requirements while minimizing costs. Other processes propose new steps in order to facilitate selection. For example, PECA [START_REF] Comella-Dorda | A process for COTS software product evaluation[END_REF] adds an extra phase : evaluation planning. It consists in choosing the people responsible for the evaluation of candidates and the techniques they will use. Other approaches focus on the definition of evaluation criteria [START_REF] Carvallo | Determining criteria for selecting software components: Lessons learned[END_REF]. For example, STACE [START_REF] Kunda | Applying social-technical approach for COTS selection[END_REF] proposes taking into account "socio-technical" criteria. Such criteria can be, for instance: product quality, product technology, business aspects (for example, supplier reputation on the marketplace), etc... BAREMO [START_REF] Lozano-Tello | Baremo: How to choose the appropriate software component using the analytic hierarchy process[END_REF] adapts AHP to COTS by defining a set of specific criteria and sub-criteria dedicated to these kind of components. COTSRE [START_REF] Martinez | COTSRE: A components selection method based on requirements engineering[END_REF] proposes to create reusable "criteria catalogs". And CAP [START_REF] Ochs | A COTS acquisition process: Definition and application experience[END_REF] proposes specific non-functional criteria inspired by ISO-9126 quality standard [19].

Limits of These Approaches

The main inconvenience of these processes is their lack of automation. Even if candidates' total scores are calculated with an automated formula such as WSM, local scores score cj are estimated manually by evaluators for each candidate c. Coming back to the example of sub-criteria "response time" and "resource consumption", it is clear that if we want a precise evaluation, it would be much better to measure them automatically with the help of metrics instead of letting a user enter arbitrary local scores. Furthermore, even if we limited ourselves to only one market, or a particular section of a market, we would face more than one hundred candidates anyway. For instance, the single ComponentSource's "internet communication" section [8] contains more than 120 candidates. Therefore, it is important to automate local score measurements as much as possible. It is not only a matter of precision, but also an efficient way to deal with a huge amount of information. A high number of candidates becomes quickly fastidious in the case of a manual evaluation [START_REF] Ncube | The limitations of current decision-making techniques in the procurement of COTS software component[END_REF].

All local score calculations are not automatable the same way, though. Preselection phase usually uses a small number of general criteria, such as keywords. In this case, local score calculations are simple, but they can apply to a large number of candidates. Component search and retrieval techniques [START_REF] Mili | Reusing software: Issues and research directions[END_REF], whose goal is to formulate a specific query and then retrieve all the components matching this query, provide adapted algorithms for this kind of local scores, for instance, keyword search or facet-based classification [START_REF] Príeto-Diaz | Implementing faceted classification for software reuse[END_REF]. However, during detailed evaluation phase, there can be many complex criteria, each one concerning a specific property (signature matching, metric value comparison...). In this case, local score calculations are much more complex because they require the aggregation of many values of different nature, but they apply to a smaller number of candidates. Fine-grained comparisons such as signature subtyping [START_REF] Cardelli | A semantics of multiple inheritance[END_REF] fit this kind of comparison. And non-functional properties, in order to be evaluated, can be described with techniques such as quality of service contracts [START_REF] Frolund | QML: A language for quality of service specification[END_REF][START_REF] Beugnard | Concrete communication abstractions for distributed systems[END_REF][START_REF] Defour | Extra-functional contract support in components[END_REF] or COTS-based quality models [START_REF] Alvaro | A software component quality model: A preliminary evaluation[END_REF].

The mechanism we propose allows for the automation of these local score calculations by taking into account the need for flexibility on the criteria detail level. The originality of our approach consists in automating COTS selection by using existing works from other domains. All these techniques cohabitate into a unique concept: target component.

Component Selection

Our selection approach takes place in a component-based software development context, as defined in [START_REF] Crnkovic | Component-based development process and component lifecycle[END_REF]. In this context, a component-based application is built incrementally. When a component is added into the application, it brings its own constraints. Then, its required interfaces become part of the new requirements that must be satisfied by the next component to be integrated. Therefore, the application's current requirements are dictated, among other things, by components currently integrated in it.

We chose to model the application's requirements by virtual "target" components. A target component represents the "ideal" answer for a specific need, and has to be replaced by the closest "concrete" candidate component. Evaluation criteria are components' functional and non-functional properties. Such a representation allows the designer to have criteria that are closer to the application's true needs. It also allows for the use of many techniques dedicated to automatic component search and comparison. However, such a mechanism implies two problems: i) the choice of a description format for candidate components as well as target ones; ii) the definition of a comparison function for such component descriptions to measure their "similarity". In this section, we will successively present the solutions we propose to address these two problems.

Component Description Format

Nowadays, there is no consensus on component description format. Each market has its own way to document its components, often developed from several different models. For instance, ComponentSource stores ActiveX, JavaBeans or .NET components. However, all candidates must be compared to a target component according to a same description format. Furthermore, this format must be abstract enough to encompass concepts that are common to most existing models. This is why we defined our own format dedicated to COTS components. It is described with a UML model (figure 1), whose elements will be presented in the following pages.

Architectural artifacts. Three kinds of artifacts have been selected: components, interfaces, and operations. Components contain two sets of interfaces (provided and required), and interfaces are constituted by a set of operations. This representation is inspired by the standard definition used by many models such as UML 2.0 [START_REF]OMG: UML 2.0 superstructure final adopted specification[END_REF]. As COTS components are represented as "black-boxes", we will not take into account "composite" components.

For each (target) operation, we associate several signatures. It is useful to anticipate many to improve performance during the search for a specific service. A signature S = P aramT ypes → ResultT ype details parameters' types, Information associated to artifacts. Two sets of information are common to all artifacts: a set of its possible names, and a documentation. The first set is here because a same artifact can be proposed under several different names. For example, a download operation can be named Download or GetF ile. This is the case, respectively, for ComponentSpace's FTP component and Xceed 's, both being available on ComponentSource's website. The second set of information represents the artefact's documentation. Each one of the information elements included in this documentation is called "typed keywords". A keyword is typed because it positions its value in a specific interpretation domain called facet. For example, a component developed in EJB whose publisher is NBOS Inc. can be documented with two typed keywords: i) one that will have "Publisher" as facet, and "NBOS Inc." as value; ii) one that will have "Technology" as facet, and "EJB" as value.

It is possible to associate other information to artifacts, in particular behavioral information such as pre-and post-conditions. However, the primary goal of our approach is to bring a concrete answer to an industrial concern. To do so, consider the context of COTS component markets such as ComponentSource.

Unfortunately, in such markets, the documentation of components' behavior is very poor. This is why we currently do not address these aspects.

Non-functional Properties Associated to Artifacts

Each artifact can have a "quality field", i.e. a set of non-functional properties (N F P in figure 1). The idea that every architectural artifact can have nonfunctional properties is inspired by quality of service description languages such as QML [START_REF] Frolund | QML: A language for quality of service specification[END_REF] and QoSCL [START_REF] Defour | Extra-functional contract support in components[END_REF]. A non-functional property represents the result (result P ) obtained by measuring the "level" of a quality attribute on an artifact. This measure is made by a metric. Such a structure is inspired by quality models dedicated to COTS components [START_REF] Alvaro | A software component quality model: A preliminary evaluation[END_REF][START_REF] Bertoa | Quality attributes for COTS components[END_REF]. Such models extend ISO-9126 quality standard [19] by associating quality attributes and metrics to its characteristics and sub-characteristics. We chose metrics to represent and compare non-functional properites, because contrary to other methods focusing on one specific property or family of properties [START_REF] Defour | Extra-functional contract support in components[END_REF], metrics seem to be the simplest evaluation tool for quality in the largest sense.

There are several standards for metrics, such as IEEE 1061-1998 [START_REF]IEEE Standard for a Software Quality Metrics Methodology[END_REF], for which a same quality characteristic or sub-characteristic can be measured by several metrics, and conversely. However, there is a problem when a same quality attribute is measured by metrics of a different kind from one quality model to another. Let us take the example of two different quality models: Bertoa's and Vallecillo's model [START_REF] Bertoa | Quality attributes for COTS components[END_REF] and CQM [START_REF] Alvaro | A software component quality model: A preliminary evaluation[END_REF]. Sometimes, both models associate the same quality attributes to ISO-9126's sub-characteristics, but measure them with different metrics. For instance, the Controllability attribute, associated to sub-characteristic Security, is measured by a percent value in Bertoa's and Vallecillo's model, whereas it is measured by a boolean in CQM. But even though metrics measuring the same attribute may have the same type, it does not mean they are semantically comparable. And there are no systematic methods allowing one to compare values obtained for a same quality attribute with different kinds of metrics. Consequently, we will consider for our description format that one quality attribute can be measured by only one metric, even though a same metric can measure several quality attributes. We can use attributes and metrics from one existing quality model. It can either be an academic one, or one provided by a component market such as ComponentSource.

In any case, it must be the same for all components.

A metric can be numeric or ordinal. This distinction is inspired by the CLAR-IFI project [START_REF] Boegh | Certifying software component attributes[END_REF]. The domain of a numeric metric is a subset of real numbers (integers, percent values...). As the quality models we surveyed do not propose metrics with negative values, we take as a hypothesis that the domain of a numeric metric is always positive. About the domain of an ordinal metric, it is a finite and totally ordered set. A numeric metric has a supplementary attribute called "direction". This direction allows for the interpretation of a metric's result. Available directions are increasing and decreasing. This distinction is inspired by quality of service contract languages [START_REF] Frolund | QML: A language for quality of service specification[END_REF][START_REF] Defour | Extra-functional contract support in components[END_REF]. An increasing (resp. decreasing) direction means that the higher (resp. the lower) the metric's value, the better the corresponding quality. For example, an operation's execution time has a decreasing direction. An ordinal metric has one supplement attribute called "hierarchy". It gathers and ranks all the metric's possible values by associating a key to each one of them. This key, or rank, defines the total order relation on the metric's domain. When a value is "better" than another, the first one's rank is strictly superior than the second one's rank in the associated hierarchy. For example, if an ordinal metric M has {very bad, bad, average, good, excellent } as a domain, corresponding hierarchy is: Hierarchy(M )=[(0, very bad ), (1, bad ), (2, average), (3, good ), (4, excellent )].

Satisfaction Index between Components

Using the same description format given above for candidate and target components, we can address the problem of component comparison. In selection processes and multi-criteria decision making techniques, after total score calculations are performed, the candidate with the highest total score is selected as the best one. This is why we chose to define a satisfaction index based on the same principle. This index allows one to determine how much a candidate component fits the target one. That means, how many functional and non-functional properties this candidate has in common with the target component. First, we will present the principle and the general formula for this satisfaction index, before giving the details for some elements of the description format.

General definition.

A careful analysis of description format allows us to distinguish a hierarchical description. In this format, a component is described by a tree whose root is a component artifact and child nodes are potentially: Interf ace, Documentation, P ossibleN ames and QualityF ield. Among them, an Interf ace node can have the following child nodes: Operation, Documentation, P ossibleN ames and QualityF ield. Therefore, the satisfaction index must compare recursively two nodes from different trees by comparing their respective child nodes pair by pair, then "aggregate" the result of sub-nodes' comparisons to measure similarity score. This calculus is the same whatever the nature of the compared nodes is (as long as they are both of the same nature). Therefore, we will give a generic description of this calculus independently of their nature.

To each node, we associate a type and a weighting function. For example, a node can have Interf ace, Operation or Documentation as a type. Only two nodes of a same type can be compared, otherwise the satisfaction index between them will return 0. On the opposite, the maximum value for a satisfaction index is fixed to 1, which means the candidate element completely fits the target one. Weighting function W eight(E) allows the designer to associate to each node E a numeric value called "weight", which gives its importance compared to other nodes. General satisfaction index calculus for a target node E0 and a comparable candidate node E1 is described in figure 2. For each node e0, child of E0, we measure satisfaction indices with each child node of E1 that is comparable to e0 (respectively, index1, index2 and index3). The best result is the highest satisfaction index among them. This measurement is repeated for all E0's other child nodes. Finally, all these best indices, with their corresponding weight, are added Fig. 2. Satisfaction index between two elements to obtain a total satisfaction index between E1 and E0. In order to compare leaf nodes, we use a specific function to each kind of them.

Formally, the satisfaction index between a candidate element E 1 and a target one E 0 , denoted Index, is defined as follows:

Index(E 1 , E 0 ) = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 0 if T ype(E 1 ) = T ype(E 0 ). Comp(E 1 , E 0 ) if E 0 is a leaf node. Σ({W eight(e 0 ) * MAX({Index(e 1 , e 0 ) | e 1 ∈ E 1 }) | e 0 ∈ E 0 }) if E 0 is an inner node. (1)
Selection is performed by calculating satisfaction indices between each available candidate component and the target one, then choosing the candidate whose satisfaction index is the highest one.

Chosen weighting and comparison functions. Now that the general satisfaction index formula has been defined, we have to detail comparison functions we have chosen for each type of leaf node (NFPs, sets of possible names, typed keywords and operation signatures), as well as the weighting function we have chosen for every type of node.

Comparison function between NFPs:

Let A 0 be a target artifact, P 0 be an NFP belonging to A 0 's quality field, A 1 be a candidate artifact having the same type as A 0 , and P 1 be an NFP belonging to A 1 's quality field. P 1 is comparable to P 0 only if they measure the same quality attribute. In this case, the metric they both use will be denoted M . If M is numeric, comparison function will measure the similarity of P 1 's result value with P 0 's, with respect to M 's direction. If M is ordinal, the comparison function will measure the similarity of P 1 's result's rank with P 0 's result's rank, with respect to M 's hierarchy.

Formally, the comparison function between P 1 and P 0 is defined as follows:

Comp(P 1 , P 0 ) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if
With:

Comp inc (P 1 , P 0 ) = M IN ( result P1 result P0 , 1) (3
)

Comp dec (P 1 , P 0 ) = M IN ( result P0 result P1 , 1) (4
)

Comp ord (P 1 , P 0 ) = M IN ( rank(result P1 ) rank(result P0 ) , 1) (5)
Let us suppose that P 0 and P 1 both measure the "quality level" of a particular attribute with an ordinal metric whose domain is {very bad, bad, average, good, excellent }. If P 0 's result value is good, its rank is 3. If P 1 's result value equals bad, its rank equals 1 and the comparison function between P 1 and P 0 gives 1/3.

Comparison function between sets of possible names:

For simplicity reasons, we consider that for one candidate set of possible names N 1 and one target set possible names N 0 , Comp(N 1 , N 0 ) equals 1 if one of N 1 's names is contained in N 0 (i.e. there is at least one common element between N 1 's values and N 0 's), regardless of differences between uppercases and lowercases. In any other case, Comp(N 1 , N 0 )=0.

Comparison function between typed keywords: For a candidate typed keyword K 1 associated to a facet F 1 and a target typed keyword K 0 associated to a facet F 0 , Comp(K 1 , K 0 )=1 if F 1 's value equals F 0 's (unless F 0 's value is "", in this case facets are not compared) and if K 1 's value equals K 0 's. In any other case,

Comp(K 1 , K 0 )=0.

Comparison function between operation signatures:

To automate comparison between operation signatures, we chose to use signature subtyping, in particular contravariance and covariance rules [START_REF] Cardelli | A semantics of multiple inheritance[END_REF]. Therefore, we consider that a candidate signature S 1 =P aramT ypes Let us consider, for example, target signature S 0 : f loat → int. If S 1 = f loat → f loat, it will be a subtype of S 0 and the comparison function will give 1. However, if S1: boolean → int, the comparison function will give 0.

There are other existing techniques to compare operation signatures, in particular signature matching as defined by A. Zaremski and J. Wing [START_REF] Zaremski | Signature matching: a tool for using software libraries[END_REF] or S. Sadou et al. [START_REF] Sadou | Unanticipated evolution for distributed applications[END_REF][START_REF] Sadou | Abstracting services in a heterogeneous environment[END_REF]. However, all matching rules are not fully automatable, because they require a collaborative approach.

Weighting function: For every type of node, we will use "weighting by distribution". It consists, for the application designer, in giving a percent weight and sharing the totality of each node's weight between its direct child nodes, from the root (the component whose weight is 1) to the leaves. For example, an interface will share its weight between its set of possible names, its documentation, its operations and its quality field, so that the sum of all these nodes' weights will equal 100% of the interface's weight. The only exception is the set of possible signatures for an operation. As we look for only one correct signature among all the ones we propose, all of them will count for one. Let us suppose we described a target operation with three possible signatures and a quality field. If the quality field takes 40% of the interface's weight, then each signature will have a weight equal to 60% of the interface's weight.

Selection in ComponentSource

In this section, we present an experiment conducted on a concrete component market. This experiment shows practical feasability and interest of an automatic, multi-level, selection approach. We consider the following context: a designer needs for her/his application a component dedicated to FTP (File Transfer Protocol ) among all the candidates available in the ComponentSource component market's "internet communication" section1 . For each candidate we produced a description in our format. In particular, the quality model we used corresponds to the non-functional information available on ComponentSource web pages for each of its components. Then, we tested the selection mechanism on these translated descriptions, and produced the results presented in this section. Translation from original components' descriptions to our description format has been done using model transformation techniques. Because of article size, this work will not be presented in this paper, but it will be the subject of a future publication.

Non-negotiable Requirements

Let us consider the development of a component-based application. Some constraints are specific to the development context. They are often imposed and non-negotiable. For example, if the chosen development tool is Visual Studio, then the candidate components must have Visual Studio as a compatible container 2 . Therefore, we must filter candidates to keep only the ones that fit these technological constraints. We can model this filter with our framework. To do so, we can use this constraint on compatible containers as a property whose values are either "True" or "False". Then, we can specify a target component with an NFP corresponding to the compatibility with the Visual Studio container. Therefore, with only one constraint whose value is "True" or "False", the possible satisfaction index values are 1 or 0. Only the candidates whose satisfaction index equals 1 will be pre-selected. Thus, only 35 "compatible" candidates from ComponentSource remain. In the following pages, measurements will be performed only on these compatible candidates.

Initial Requirements

The application being in development, its current "concrete" architecture has requirements. That means, the designer needs to find a FTP component that provides operations whose signatures are required by "concrete" components already included in the architecture. Moreover, the application has security requirements, which imposes that the FTP component enables SSL protocol. It corresponds to quality attribute SecuritySSL, measured by an ordinal metric with a boolean domain (see figure 1). The target component that models all these requirements is shown in figure 3. From a functional point of view, it provides one interface containing 10 operations. Each one of them is dedicated to a specific FTP task (folder creation, login, download...), and has a signature imposed by the application's concrete architecture. However, it can have many possible names. From a non-functional point of view, the target component's quality field contains a unique NFP concerning the need of SSL protocol. This NFP represents quality attribute SecuritySSL with value T rue. We estimate that the provided interface takes 70% of the component's weight, while the quality field takes the remaining 30%. Therefore, provided interface and quality field weights equal respectively 0.7 and 0.3 (see figure 3). We also consider that all 10 operations are of equal importance, so each one's weight equals 0.1 in the context of the provided interface. Of course, this is only an example of possible weighting: other weights can be estimated according to the context of the application.

Results for Initial Requirements

Satisfaction indices have been measured for each of the 35 candidates on our tool Substitute3 . This tool takes as parameters XML files describing the chosen 1 shows the measurements for the 15 best candidates. First, there are 5 secure (SSL) and 4 non-secure (without SSL) versions of a FTP component provided by the IP*Works! component suite. These different versions are identified according to their language (C++), their framework (.NET, ActiveX) or the context they were developed for. For example, the .NET Compact Framework is made specifically for mobile phones, while the ASP/.NET version is better suited for Web applications. Then, there are the secure and non-secure ActiveX versions of a FTP component provided by PowerTCP component suite. There are also other FTP components provided by component suites Aspose Network, SocketTools and Xceed. At first, we ignored the candidates' development context. However, the first four candidates all have the same satisfaction index. The reason is that they all represent the same secure FTP component, but for different development contexts (ActiveX, .NEt...). Thus, they provide the same operations with the same signature. Then, we must consider a precise context, such as the development of a client/server application based on ActiveX. In order to choose between the remaining candidates, a more in-depth analysis of them is necessary.

Requirement Evolution

By focusing on a precise development context, thus removing the versions of a same component made for a different context, further exploration becomes conceivable on a remaining candidate. Thus, we can notice they have some properties which were not considered first, but may be very interesting. A good example of such unexpected properties is the tests performed on these components before they were brought to the market. As the application has security requirements, it would be better if the candidates were tested before being integrated. Indeed, ComponentSource provides for each component some information about the tests performed on it: installation test, uninstall test, antivirus scan, sample code review, etc... Therefore, it would be interesting to check the "test degree" of each candidate, i.e. the number of tests, among the eight ones recognized by ComponentSource, which were performed on it. This new requirement leads to a modification of the target component. Its quality field now contains a new NFP representing test degree and asking for the maximal value, 8. Provided interface and quality field weight do not change. However, inside the quality field, the weight of NFP representing SSL enabling must decrease a bit. It will equal 0.665 (two thirds of the quality field's weight), while the new NFP representing test degree will take the remaining 0.335.

Results for New Requirements

Satisfaction indices for the remaining candidates (i.e. those that are developed for ActiveX) have been calculated with Substitute. Table 2 shows the new measurements of satisfaction indices for the five best candidates. The new column, NFP TD, shows the results for NFP representing test degree. All the tests recognized by ComponentSource were performed on the IP*Works! and PowerTCP components in their secure and non-secure versions (index for NFP T D equals 1). The last candidate did not pass some of these tests, which decrease its satisfaction index. Finally, it seems obvious that, for the specified requirements, secure ActiveX/VB version of IP*Works! FTP component is the best candidate.

Usually, when we try to select the "best" candidate for an application's current requirements, we are limited by our initial knowledge. With a way to navigate through the library, it is possible to discover properties offered by the components which we did not originally think about. This is typically one of the trade-offs predicted by L. Brownsword et al. [5] between requirement specification and COTS selection. Our easy-to-use way to specify requirements and select good candidates makes this navigation possible.

Conclusion and Future Work

We proposed an approach that allows us to automate the component evaluation phase, including: i) a description format for COTS components' functional and non-functional properties; ii) a satisfaction index that measures the similarity level between a candidate component and a target one. This approach has been validated on ComponentSource component market with the help of a tool that measures local and global satisfaction indices for a whole library of candidate components. This study showed that an automated comparison improves the performance of selection process. It also showed the importance of weighting.

Such an automated mechanism is adapted to an incremental construction of a component-based software, because "back-tracking" is possible. Each target component's specification depends on the components already integrated into the application. So if the situation is blocking (i.e. there is no candidate that can satisfy current target component), we can go back to previous ones and choose other candidates for them. It will lead to modified requirements, which may be better satisfied by candidates.

This paper follows and improves a previous work [START_REF] George | A component-oriented substitution model[END_REF][START_REF] George | A methodological approach for selecting components in development and evolution process[END_REF], whose goal was to find how a component could substitute another one. At that time, we considered no particular context. Since then, we adapted and improved our framework by considering an industrial problem, such as selection in COTS markets. Therefore, the work we present in this paper is better suited to a concrete component-based development context. Considering this context, our description format is inspired by what we do (and do not) find in documentation provided by COTS publishers. For this reason, we have not yet dealt with some component properties, particularly behavioral ones. Because of the importance of these aspects, we plan to take them into account in future versions of our framework. However, in order to achieve this goal, these properties should be documented more explicitly in component markets.

Fig. 1 .

 1 Fig. 1. Description format for COTS components

Fig. 3 .

 3 Fig. 3. Example of target component

  P 1 and P 0 do not measure the same quality attribute. Comp inc (P 1 , P 0 ) if M is numeric with an increasing direction. Comp dec (P 1 , P 0 ) if M is numeric with a decreasing direction. Comp ord (P 1 , P 0 ) if M is ordinal, and if rank(result P0 ) > 0. 1 if M is ordinal, and if rank(result P0 ) = 0.

Table 1 .

 1 First satisfaction index measurements quality model and the set of all the component descriptions that will be used (the target component, and candidate ones). For target components, only needed properties are specified and weighted. Properties that are not specified take implicitly a null weight in our calculus. Once all XML component descriptions are loaded, Substitute returns satisfaction indices between each candidate of the library and the target component. Not only global indices, but also local ones for child nodes (interfaces, operations, NFPs...).Table

	Candidate name	Operations NFP SSL Total
	IP*Works! SSL v6 .NET	0.73	1.0	0.81
	IP*Works! SSL v6 ActiveX/VB	0.73	1.0	0.81
	IP*Works! SSL v6 .NET Compact Framework	0.73	1.0	0.81
	IP*Works! SSL v6 ASP/.NET	0.73	1.0	0.81
	PowerTCP SSL for ActiveX	0.65	1.0	0.75
	IP*Works! v6 .NET	0.73	0.0	0.51
	IP*Works! v6 ActiveX/VB	0.73	0.0	0.51
	IP*Works! v6 .NET Compact Framework	0.73	0.0	0.51
	IP*Works! v6 ASP/.NET	0.73	0.0	0.51
	PowerTCP FTP for ActiveX	0.65	0.0	0.45
	Aspose Network .NET	0.65	0.0	0.45
	IP*Works! SSL v6 C++	0.14	1.0	0.39
	SocketTools Secure Visual Edition	0.12	1.0	0.38
	SocketTools Secure .NET Edition	0.12	1.0	0.38
	Xceed FTP Library	0.52	0.0	0.36

Table 2 .

 2 New satisfaction index measurements

	Candidate name	Operations NFP SSL NFP TD Total
	IP*Works! SSL v6 ActiveX/VB	0.73	1.0	1.0	0.81
	PowerTCP SSL for ActiveX	0.65	1.0	1.0	0.75
	IP*Works! v6 ActiveX/VB	0.73	0.0	1.0	0.61
	PowerTCP for ActiveX	0.65	0.0	1.0	0.55
	Xceed FTP Library	0.52	0.0	0.88	0.45

For more information: http://www.componentsource.com/index.html

There may be other non-negotiable requirements and filters, but for reasons of simplicity and clarity, we will use only this one as an example.

Because of article size, we cannot give details of Substitute tool. However, interested readers can download it at the following address: http://www-valoria.univubs.fr/SE/Substitute/


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

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

Jean-Louis Pazat
email: pazat@irisa.fr

AFPAC: ENFORCING CONSISTENCY DURING THE ADAPTATION OF A PARALLEL COMPONENT

Keywords: dynamic adaptation, consistency, parallel computing

Grid architectures are execution environments that are known to be at the same time distributed, parallel, heterogeneous and dynamic. While current tools focus solutions for hiding distribution, parallelism and heterogeneity, this approach does not t well their dynamic aspect. Indeed, if applications are able to adapt themselves to environmental changes, they can benet from it to achieve better performance. This article presents Afpac, a model extending Dynaco for designing self-adaptable parallel components that can be assembled to build applications for Grid. This model includes the denition of a consistency criterion for the dynamic adaptation of SPMD components. We propose a solution to implement this criterion. It has been evalued using both synthetic and real codes to exhibit the behavior of several proposed strategies.

Introduction.

Grid is an architecture that can be considered as a large-scale federation of pooled resources. Those resources might be processing elements, storage, and so on; they may come from parallel machines, clusters, or any workstation. One of the main properties of Grid architectures is to have variable characteristics even during the lifetime of an application. Resources may come and go; their capacities may vary. Moreover, resources may be allocated then reclaimed and reallocated as applications start and terminate on the Grid. To sum up, Grid is an architecture that is at the same time distributed, parallel, heterogeneous and dynamic. This is why we think distributed assemblies of parallel self-adaptable components is a suitable model for Grid applications.

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

Section 2 presents our model of dynamic adaptation for parallel codes to set the context of this article up. Section 3 gives few mathematical denitions that are useful in the remaining text of this paper. Sections 4 and 5 describe how the future of the execution path is predicted to choose the adaptation point at which the adaptation code is inserted. Section 6 discusses the results obtained from our It also shows similarities with computation steering and fault tolerance. Finally, section 8 concludes this paper and presents some perspectives.

2. Model of self-adaptable components. The dynamic adaptability of a component is its ability to modify itself according to constraints imposed by the execution environment on which it is deployed. It aims at helping the component to give the best performance given its allocated resources. Moreover, it makes the component aware of changes in resource allocation. Resources may be allocated and reclaimed dynamically during the lifetime of the component.

2.1. Structure of a self-adaptable component. With our model of dynamic adaptation [START_REF] André | Dynamic adaptation of parallel codes: toward selfadaptable components for the grid[END_REF], parallel self-adaptable components can split in several functional boxes (some of them being independent of the component itself ). Figure 2.1 shows the architecture of a parallel self-adaptable component. A short description of the boxes follows.

The monitors provide the information service about the environment of the component. They should oer two interfaces: a subscription-based event source and a query interface. Monitors are not restricted to collect information about the outside world of the component: the component itself and its activity can be relevantly monitored (for example for estimating its current service rate). Furthermore, nothing prevents the component from being one of its own monitors.

The service of the component is the functionality it provides. The service can be implemented by several algorithms that might be used to solve a single problem.

Each of these algorithms uses dierently the resources; thus, there is one preferred algorithm for each conguration of the resources allocated to the component.

The actions are the ways to modify the component. They modify the way the service is implemented, replacing the algorithm with another one, adjusting its parameters or anything else. Typically, actions use reective programming techniques to aect the component.

A strategy is an indication of the way the component should behave: it states the algorithm that should be executed and the values that its parameters should adopt.

The decider makes the decisions about adaptability. It decides when the component should adapt itself and which strategy should be adopted. In order to decide, it relies on the policy and on information provided by monitors. The policy describes component-specic information required to make the decisions. For example, the policy can be an explicit set of rules or the collection of the performance models of the algorithms implemented by the component.

A plan is a program whose instructions are invocations of actions and control instructions. Thus, plans are programs that modify the component. The planner establishes an adaptation plan that makes the component adopt a given strategy. To do so, it relies on the guide. The guide gives component-specic information required to build plans. It can consist in predened plans; or in specications of how actions can be composed (their preconditions and postconditions for example).

The executor is the virtual machine that interprets plans. In addition to forwarding invocations to actions, it is responsible for concerns such as atomicity of plan execution. The executor embeds a coordinator for synchronizing the execution of the plan with the processes that execute the service. To do so, the coordinator chooses a point (an instantaneous statement that annotates a special state) within the execution path of the service in order to insert the action.

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

Our parallel adaptable components are split in 3 parts. The decider, planner and executor form the Dynaco framework (in blue): they provide the general functionalities of dynamic adaptation. The coordinator is part of the Afpac framework (in green) that is specic to parallel components. Finally, service, actions, policy and guide are specic to the component: they are not included in any framework.

Contracts between components. Because the quality of the services

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

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

2.3. Performance model. The goal of dynamic adaptation is to help the component to give the best performance. Thus, the model assumes that adaptation occurs when the component runs a non-optimal service given its allocated resources. This means that the completion time is worse than it could be. In a general way, the conceptual performance model of a single-threaded component that adapts itself is shown by gure 2.2. The x-axis is the execution ow of the component with adaptation points labelled from 1 to 5; the curve gives the expected completion time if the component adapts itself at the corresponding point in its execution ow. The lower the expected completion time is for a given adaptation point, the better that adaptation point is.

The adaptation can occur in either the future or the past of the current state. In the case of adapting in the past, it requires the restoration of a checkpoint (that has a cost r on the curve). At the extremes, adapting in the future is adapting once the execution has ended (or equivalently not adapting at all); while adapting in the past consists in restarting from the begining (purely static adaptation). It appears that whatever the search direction, the best point will always be the nearest one from the current state. In gure 2.2, the best adaptation point is the one labelled 3.

In the case of a parallel component, several curves are superimposed. Because the threads of the component are not necessarily synchronized, the curves are slightly shifted (the present time is not at the same distance of adaptation points for all threads). The global completion time is thus the maximum of the ones for all threads.

In this case, the best point can be in the future for some threads and in the past for some others.

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

2.4. Consistency model. In the case of a parallel service, the coordinator must enforce the consistency of the adaptation. We dened one consistency model, which we called the same state consistency model. In this model, the adaptation is said to be consistent if and only if all threads execute the reaction from the same state (this logical synchronization does not require an eective synchronization of the execution threads). This model only makes sense in the case of SPMD codes (parallel codes for which all threads share the same control ow graph). It has been further discussed in [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF].

2.5. Scenario of dynamic adaptation. From time to time, possibly due to some external event, the decider determines whether the component should adapt itself according to the policy. It thus orders the planner to nd a suitable plan for achieving the decided strategy. This plan is sent to the executor for execution. When the executor needs to execute an action in the context of the parallel execution of the service, it orders the coordinator to choose an adaptation point. This point is the next one in the future of the execution path. When the threads of the service reach that adaptation point, their control ow is hooked in order to insert the execution of the requested action.

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

3. Denitions. This section recalls few denitions about partial orders that are useful in understanding the remaining text of this paper. Definition 3.1 (poset). A poset (or partially-ordered set) is a pair (P, R) where P is a set and R is a binary relation over P that is (1) reexive, (2) antisymmetric and (3) transitive.

(1

) ∀x • (x ∈ P ⇒ xRx) (2) ∀x, y • x, y ∈ P 2 ⇒ ((xRy ∧ yRx) ⇒ x = y) (3) ∀x, y, z • x, y, z ∈ P 3 ⇒ ((xRy ∧ yRz) ⇒ xRz) Definition 3.2 (supremum).
Given a poset (P, R), the supremum sup (S) of any subset S ⊂ P of P is the least upper bound u of S in P such that: (1) u succeeds all elements of S and (2) u precedes any element v of P succeeding all elements of S (1

) ∀x • (x ∈ S ⇒ xRu) (2) ∀v • (v ∈ P ⇒ ((∀x • (x ∈ S ⇒ xRv)) ⇒ uRv)) Definition 3.3 (inmum).
Symmetrically to the supremum, given a poset (P, R), the inmum inf (S) of any subset S ⊂ P of P is the greater lower bound l of S in P such that:

∀x • (x ∈ S ⇒ lRx) ∧ ∀v • (v ∈ P ⇒ (∀x • (x ∈ S ⇒ vRx)) ⇒ vRl)
The inmum of S in the poset (P, R) is the supremum of S in P, R -1 . Definition 3.4 (lattice). A lattice L is a poset (P, R) such that for any pair x, y ∈ P 2 , both the supremum sup ({x, y}) and the inmum inf ({x, y}) exist. This denes two internal composition laws:

sup ({x, y}) = x ∨ y (join) inf ({x, y}) = x ∧ y (meet)
4. Computing the future. The coordinator needs to nd a global point such that it represents the same state for all threads. As it restricts consideration to points in the future of execution paths this point should be the rst one in the future for all threads, given the assumption on the performance model depicted in 2.3.

Local prediction of the next point.

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

4.1.1. General schema. An execution path can be seen as a path in the control ow graph that models the code. If loops are unrolled (for example by tagging nodes with indices in iteration spaces), the control ow graph denes a precedes partial order between the points of a code. Given this relation, each thread of the parallel component is able to locally predict its next point at least in trivial cases, when no conditional instruction is encountered (in this case, nodes in the control ow graph have at most one successor).

4.1.2. Uncertain predictions. In the general case, predicting the future of an execution path is undecidable due to conditional instructions: their behavior is unpredictable since it depends on runtime computations. This occurs for both conditions and loops, which appear as nodes having several successors in the control ow graph. Three strategies may be used when such a node is encountered during the computation of the adaptation point.

• Postpone. The computation of the adaptation point can be postponed until the eective behavior of the instruction is known. Once the unpredictable instruction has been executed, the computation of the adaptation point resumes with a new start point (the one that is being entered).

• Skip. The computation of the point can move forward in the control ow graph until all control subows merge. In this case, the prediction jumps over loops and conditions.

• Force. The behavior of the conditional instruction can be guessed when additional static information is available. With this strategy, one branch of the conditional instruction is assumed accordingly to some applicationdependent knowledge; then some application-level mechanism enforces that the execution path respects this assumption.

Two examples that follow illustrate the usage of the force strategy. Firstly, it is possible for some loops to insert unexpected empty iterations; in this case, it can be guessed that the conditional instruction will execute the branch that stays in the loop; this behavior can be enforced by making one more empty iteration ondemand. Secondly, if the code includes assertions to detect error cases, it could be reasonably assumed that those assertions hold; in this case, it can be guessed that the corresponding conditional instruction will execute the branch leading to errorfree cases. As mispredictions exactly match detected runtime errors, error handlers invoked upon assertion failures can be used to handle eects of mispredictions.

The above examples exhibit two interpretations of the force strategy. In the rst example, the coordinator changes the execution behavior of the component in order to t its requirements. The coordinator uses the static knowledge about the component to ensure that this change does not have any semantic impact on produced results. In the second example, the coordinator let the component execute its normal behavior and simply exploits static knowledge to make its prediction.

Characterization of the chosen global point. The point that should

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

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

Even if loops are unrolled, the control ow graph is not a lattice as it may contain patterns such as the one of gure 4.1(a). In this example, the supremum sup ({P 1, P 2}) does not exist. This pattern captures a subset of conditional instructions. The three strategies that has been identied for locally predicting the next point can be used to work-around non-existence of the supremum.

• Postpone. Postponing the computation of the adaptation point until the unpredictable instruction has been executed can be seen as inserting a special node that models that instruction in the control ow graph. For example, in gure 4. • Skip. Skiping the conditional block is equivalent to compute the supremum within the subset dened by:

{a|∀y • ((∀x • (x ∈ S ⇒ x y)) ⇒ (a y) ∨ (y a))}
This set contains the points that are related to all successors of all points in S. Those points are guaranteed to be traversed by any execution thread starting from any point in S. The denition of that set ensures that upper bounds of S in that set are totally ordered by . Consequently, the supremum of S in that set ordered by exists if at least one upper bound exists. In the given example, it restricts to compute the supremum sup ({P 1, P 2}) in {P 1, P 2, P 5}; this supremum exists.

• Force. Forcing one branch of a conditional instruction removes all out edges but one of the corresponding node. This is sucient to make the supremum exist. For example, on gure 4.1(c), the conditional instruction that follows P 1 has been forced such that it always leads to P 3.

Each conditional instruction may use a distinct strategy. In such a case, several strategies are combined. 5. Building an algorithm. In order to solve the problem of nding a point in the case of a parallel service, an algorithm has been designed. [START_REF] Buisson | Dynamic adaptation for grid computing[END_REF].1. Identication of the candidate points. Having a good identication system for the points is a key issue. Indeed, as 4.2 has shown, the case of parallel self-adaptable components requires the computation of the supremum of a set of points. This requires to be able to compare easily candidate points with respect to the precedes partial order. However, with naive point identication, deciding whether a candidate point precedes, succeeds, or is not related to another one requires the computation of the transitive closure of the control ow graph with unrolled loops.

The same apply for the join composition law. This is why a smarter identication system for the points is needed.

5.1.1. Description of the identication system. We think that the good representation to use is a tree view of the hierarchical task graph. • out edges of loop nodes are labelled with the value of the indice within the iteration space of the loop;

• out edges of condition nodes are labelled with either the symbol then (the condition is true) or the symbol else (the condition is false);

• other edges (out edges of block nodes) are labelled with the execution order number in the control ow.

An examplary algorithm

Considering the tree view of the hierarchical task graph, one can see that the nodes of the control ow graph are the leaves of the tree. Each candidate point is identied by the sequence composed of the labels of the edges traversed by the path from the root to the leaf corresponding to it. For example, the node P 3 is identied by 2 ; the node P 1 is identied by the sequence 1, (a, b) , 1, else, 1 .

Order on points.

The set of edge labels in the tree is E = N ∪ I ∪ {then, else}, where N is the set of execution order numbers (natural numbers) and I the iteration space partially ordered by an application-specic relation I . We dene the following partial order over the set E of edge labels of the tree:

∀x, y • x, y ∈ E 2 ⇒ x E y ⇔ x, y ∈ N 2 ∧ x ≤ y ∨ x, y ∈ I 2 ∧ x I y
Notably, the two constants then and else are set not comparable to other values and values in iteration spaces (such as (a, b) in the example) are partially ordered by an application-specic relation. The edges of the control ow graph (that represent the precedes partial order between points) are (graphically) transverse to those of the tree. Consequently, the lexicographical partial order n E on the sequences is equivalent to the partial order on points dened by the control ow graph. Thus, with this identication system, deciding whether a point precedes, succeeds, or is not related to another one can be computed as a direct lexicographical comparison (not requiring the computation of the transitive closure of the control ow graph anymore). Moreover, this ordering directly takes into account the loop indices in iteration spaces, whereas the control ow graph does not.

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

In the above description of the identication system, in the tree view of the hierarchical task graph, leaves are candidate points and internal nodes are sequence, loop and if control structures. This restricts the expressivity for writing programs.

Function calls can be represented as leaves that connect to the root the target function tree, as long as the function is bound statically. Thanks to that connection, the sequence identifying a point includes the complete call stack used to reach that point.

Problems arise with runtime function binding upon calls (for example calls through pointers) and with goto like instructions. In those cases, the proposed order relation does not respect the control ow graph. As programs can be rewritten in order to respect those restrictions, further discussion about control structures is beyond the scope of this paper.

Computation of the local adaptation point. Because we restricted

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

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

The instrumentation of the code consists in inserting some pieces of code at each node of the tree view of the hierarchical task graph as presented at the preceding section. The gure 5.4 shows an example of an instrumented algorithm.

Algorithm instrumented_gcd (a, b) :

enter_f unction (gcd (a, b)) enter_loop (a, b) loop until (leave_loop ((a mod b) = 0)) iteration_loop (a, b) if (enter_condition (a < b)) then candidate_point (P1) tmp ← a a ← b b ← tmp else candidate_point (P2) a ← (a mod b) end if leave_condition () end loop candidate_point (P3)
return (leave_f unction (b)) The process of inserting the instrumentation statements in the source code of the component can be largely automated using aspect-oriented programming (AOP [START_REF] Kiczales | Aspect-oriented programming[END_REF])

techniques. We have proposed in [START_REF] Vaysse | Using aspects for integrating a middleware for dynamic adaptation[END_REF] a static aspect weaver whose join points are the control structures. This weaver has been successfully used to insert the instrumentation statements. It relies on candidate points, which are placed by hand by the developer, to detect which control structures need to be instrumented (those that contain at least one candidate point).

Protocol for computing the supremum. Many trivial protocols might

be designed to compute this supremum (for example, centralized). Many already exist to compute a maximum (in particular for leader election); they can easily be modied to compute a supremum instead of a maximum. However, we think that a specic protocol suits better this case. to the other threads. These clues can be for example the root node of the subtree representing the conditional block. When a thread receives a proposition or a clue, it may take dierent actions depending on how it compares to its own proposition.

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

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

• If the two propositions are not comparable, the thread retracts its proposition and computes a new one that takes into account the two previous ones. The computation starts at the point at which the control subows merge (the supremum of the two points).

• If both propositions are the same, the thread agrees with the other one.

The protocol also progresses when an execution thread provides new information. For example when the functional thread executes a conditional instruction, it may retract its clue and propose some new information.

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

5.4.3. Anatomy of the protocol. We have designed a specic protocol to solve this problem. This protocol is based on a unidirectional ring communication scheme.

Each thread confronts its proposition with the one of its predecessor and sends it only to its successor in the ring. The end of the protocol, namely the reach of the agreement, is detected using a Dijkstra [START_REF] Dijkstra | Derivation of a termination detection algorithm for distributed computations[END_REF]-like termination algorithm. Our protocol distinguishes strong propositions (values that can be chosen by the agreement) from weak propositions (values that forbid the agreement to conclude, previously called clues). The protocol allows threads to retract their proposition. It strictly denes the criteria of the consistency of retraction.

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

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

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

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

6.2. Observations. Figures 6.1 and 6.2 show the results with the FFT code.

This experiment aims at comparing the postpone and skip strategies for conditional instructions within a main loop. The main loop has the force strategy so that the synchronization and communication statements induced by our algorithm are exclusively related to the inner instructions. This prevents distortions of the observations. Figure 6.1 shows that the postpone strategy tends to select an adaptation point that arrives sooner in the execution path than the skip strategy. Conversly, gure 6.2

shows that the postpone strategy tends to suspend the functional code for a longer time than the skip strategy. Indeed, the postpone strategy leads to higher density of samples up to about 0.5 s of functional code suspension. However, this observation has to be balanced as it appears that both strategies do not suspend the functional code in most of the samples. The observations are explained by the fact that the postpone strategy tends to delay the agreement in order to choose a more precise point (closer to the current state), in comparision to the skip strategy. It makes the postpone strategy increase the risk for other threads to reach that point before the agreement is made, and thus to suspend their execution. On the other side, the skip strategy tends to choose a point that is further in the future of the execution path; it results in a lower risk for other threads to reach that point before the agreement is made and thus to suspend their execution.

Consequently, if the time between a conditional instruction and the following point is large enough to balance the delay of the agreement, the postpone strategy should be preferred as it results in a sooner adaptation. Otherwise, the skip strategy should be used in order to avoid the suspension of the execution thread. [START_REF]Derivation of a termination detection algorithm for distributed computations[END_REF]. Related works and domains. 7.1. Other projects on dynamic adaptation of parallel codes. Most of the projects that faced the problem of dynamic adaptation such as DART [START_REF] Raverdy | DART : a reective middleware for adaptive applications[END_REF] do not consider parallelism. Other projects such as SaNS [START_REF] Dongarra | Self-adapting numerical software for next generation application[END_REF] and GrADSolve [START_REF] Vadhiyar | GrADSolve: RPC for high performance computing on the grid[END_REF] build adaptive components for Grid. Those projects target adaptation only at the time of component invocation. This supposes a ne-grain encapsulation in components; otherwise, if methods are too long, adaptation is defeated because it cannot occur during execution. Within the context of Commercial-O-The-Shelf (COTS) component concept, suciently ne-grained encapsulation for the dynamic adaptation to make sense only at invocation level does not appear valuable enough; whereas suciently coarse-grained encapsulation for valuable COTS components are not able to really dynamically adapt themselves if they do so only at each invocation. This is why we think that components should be able to adapt themselves not only at method calls, but also during the execution of methods.

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

PCL [START_REF] Adve | Language and compiler support for adaptive distributed applications[END_REF] focuses on the reective programming tools for the dynamic adaptation of parallel applications. This project considers dynamic adaptation as modications on a static task graph modeling the code and provides at runtime primitive operators on that graph. It gives a full framework for reective programming that is useful to implement reactions. The problem of the coordination of the reaction and the execution threads of the functional code has been studied with PCL in [START_REF] Ensink | Coordinating adaptations in distributed systems[END_REF]. Their approach to the problem of the coordination is similar to ours: the adaptation is scheduled to be executed at an adaptation point in the future of the execution path.

However, the problem of dealing with unpredictable conditional instructions is not addressed. Furthermore, the consistency model is dierent from ours. In PCL, each reaction is triggered at any point of the specied region. For example, on gure 7.1, tasks B and D are not distinguished. According to the consistency model, in a twothreads component, if one is executing A and the other C, a region in reaction targeting region RGN 1 is scheduled at the A → B edge for the rst thread and at the C → D edge for the second one. We think that it is a better consistency . One solution might be to put B and D in two dierent regions; but in this case, PCL fails specifying that the reaction can be scheduled either before B or before D, but at the same edge for all threads. Furthermore, PCL is unable to handle the case of thread desynchronization in loops (one thread doing more iterations than another does) for regions being in such a loop. The simple region counter is not sucient to solve this problem. 7.2. Resource management in Grid infrastructures. The dynamic characteristic of Grid architecture appears well accepted, as reected by the presence of monitoring services such as Globus MDS. On the other side, job management usually considers that the set of resources allocated to one job remains constant for the whole lifetime of the job. Approaches such as AppLeS [START_REF] Berman | Adaptive computing on the grid using apples[END_REF] and GridWay [START_REF] Huedo | The gridway framework for adaptive scheduling and execution on grids[END_REF] show that even Grid applications can benet from non-constant schedules. With those two projects, when the scheduler or the application detects that a better schedule can be found, the application checkpoints itself, then the job is cancelled and resubmitted with new resource constraints. Our approach is slightly dierent. We assume that the resource management system is able to modify job schedules without having to cancel and resubmit jobs. Thanks to this assumption, checkpointing and restarting the application is not required, potentially leading to lower cost for the adaptation in particular when the intersection before and after the rescheduling is not empty. 7.3. Computation steering. The problem of steering a parallel component is very close to our problem of adapting this component. Indeed, in both cases, we need to insert dynamically code at some global state. The EPSN project [10] aims at building a platform for online steering and visualization of numerical simulations.

In [START_REF] Esnard | A time-coherent model for the steering of parallel simulations[END_REF], the authors describe the infrastructure they built to do the steering. Their structured dates is similar to our candidate point identication system. Both systems are based on similar representations of the code. Moreover, steering like dynamic adaptation tries to nd the next candidate point in the future of the execution path. Thus, computation steering and dynamic adaptation may benet from fusionning in a single framework. 7.4. Fault tolerance. Fault tolerance might be seen as a particular case of dynamic adaptation. Indeed, it is the adaptation to the crash of some of the allocated resources. However, things are not that simple. Fault tolerance encompasses two dierent problems: the recovery of the fault and the adaptation to the new situation.

Only the second one really belongs to the problem of dynamic adaptation. Many strategies can be used to recover from faults. The closest one from dynamic adaptation is probably checkpointing in the sense it requires some global points. Whereas dynamic adaptation can look for a point in the future of the execution path, checkpointing requires a point in the past. Nevertheless, mechanisms required by dynamic adaptation may be useful to implement recovery strategies based on checkpointing.

The instrumentation of the code can be used as hooks at which checkpoints can be taken. Indeed, it implicitly statically coordinates the checkpoints of all threads, avoiding the problem of computing a global consistent state. Reciprocally, dynamic adaptation can take advantage of the techniques that have been developped to checkpoint and restart computations in the area of fault-tolerance. [START_REF] Dongarra | Self-adapting numerical software for next generation application[END_REF]. Conlusion. In this paper, we have briey described the overall model we introduced to build self-adaptable parallel components. This paper essentially focuses on the coordinator functional box of the Afpac framework. This coordinator is responsible for scheduling the reaction in the execution path of the several execution threads.

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

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

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

Figure 2 . 1 .

 21 Figure 2.1. Model of a parallel self-adaptable component

Figure 2 . 2 .

 22 Figure 2.2. Conceptual performance model of an adapting component

  1(b), a node C has been inserted to represent the conditional instruction. When such a node is chosen, a new round for nding a satisfying (a) Pattern which prevents the supremum from existing (b) Inserting nodes for conditionals (c) Removing branches of conditionals

Figure 4 . 1 .

 41 Figure 4.1. Example of control ow graph with non-existent supremum

4. 3 .

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

Figure 5 .

 5 [START_REF] Adve | Language and compiler support for adaptive distributed applications[END_REF] gives an example algorithm that has been annotated with candidate points; gure 5.2 shows the control ow graph between annotated points; gure 5.3 shows the corresponding tree view. The edges of the tree are labelled as follows:

  Algorithm gcd (a, b) : loop until ((a mod b) = 0) if (a < b) then // candidate point P 1 tmp ← a a ← b b ← tmp else //candidate point P 2 a ← (a mod b) end if end loop // candidate point P 3 return (b)

Figure 5 . 1 .

 51 Figure 5.1. An examplary algorithm

Figure 5 . 2 .

 52 Figure 5.2. Control ow graph of the algorithm 5.1 Figure 5.3. Tree view of the hierarchical task graph of the algorithm 5.1

Figure 5 . 4 .

 54 Figure 5.4. Instrumented version of the algorithm 5.1

5. 4 . 1 .

 41 Motivation for designing a specic protocol. The full set of the local adaptation points is not always necessary to compute the supremum. The idea is to superimpose the agreement protocol and the local computations of the next candidate point in order to exempt some of the execution threads from computing their local adaptation point. In particular, it is interesting to exempt those whose prediction is postponed due to conditional instructions. Indeed, it allows the computation of the local adaptation point to resume sooner with a start point that is further in the execution path. Moreover, superimposing the protocol and the computation evicts the earliest adaptation points sooner than if the whole set of local adaptation points must be computed. This avoids situations in which the execution thread tries to execute through a locally chosen point that has not been either conrmed or evicted yet. 5.4.2. Informal description of the protocol. The key idea of the protocol is to let the threads negotiate. Each thread can propose to the others its view of what the common adaptation point is, namely the point it has chosen locally. If it has not chosen one (because of unpredictable instructions such as conditions), it can give clues

Figure 6 . 2 .

 62 Figure 6.1. Density curve for adaptation delay

Figure 7 . 1 .

 71 Figure 7.1. Example of a region in a PCL static task graph

Acknowledgement. Experiments described in this paper have done with the Grid 5000 (http://www.grid5000.fr/) French testbed.