Alfredo Goldman

Yanik Ngoko

Optimizing resource sharing on cooperative execution of algorithms 1

Keywords: XXX [XXX]: XXX-XXX, XXX [XXX]: XXX-XXX, XXX [XXX]: XXX-XXX Algorithms, Experimentations, Performances resource sharing, algorithm portfolio, concurrent execution, cooperative problem solving

Solving hard combinatorial problems has always been a challenge. The constant progress in algorithm design and the emergence of powerful large-scale parallel platforms allow to solve a larger number of instances of such problems. As a consequence, many efficient algorithms are available for solving the same problem. However, none of them strictly dominates the others on all the instances.

An important problem is to determine an adequate selection of algorithms for solving a given set of instances in order to minimize the total completion time. However, little is known in cooperation between algorithms for an improved global objective. The execution model of algorithms portfolio is a nice framework for studying this question. It consists in executing all the available algorithms concurrently and interrupt them as soon as a solution is found. This model of execution raises however the question of the resources repartition among the algorithms. Interesting directions in this way have been proposed through parallel algorithms portfolio problem. The idea is that it is possible to learn about the resource sharing based on the observation of executions of the algorithms on a set of instances. Parallel algorithms portfolio problems are generally intractable and thus, many heuristics have been proposed to solve them. However, these solutions do not take into account the possibility of sequential algorithms or unknown speed-ups.

We propose in this paper a two phases approach for learning resource sharing in the context of a portfolio. The first phase consists in estimating what may be the optimal useful execution workload for each algorithm. This estimation is done through a clustering approach inspired by the resolution of the set cover problem. The second phase consists in minimizing the estimated workload by optimal resource allocation. We propose for this purpose a solution based on dynamic programming.

This approach is evaluated experimentally on two settings. In the first setting we simulate the concurrent execution of sequential SAT algorithms. In the second case, we implement a parallel algorithm for CSP based on algorithms portfolio. The experiments clearly exhibit that the proposed approach is suitable for defining an efficient concurrent model of execution.

INTRODUCTION

This work focuses on the resolution of hard computational problems. Following the advances in algorithms design and the evolution of computing platforms, there exist many heuristics that can be used for solving the same problem. Such heuristics usually have their own characteristics on the execution time depending on the target instances and they behave differently. It is commonly well-admitted that on most problems, no single algorithm dominates all the others (this is for instance the case in scientific contests like the SAT competition3 ). Thus, a possible approach for efficient implementation consists in performing concurrent executions of algorithms [START_REF] Huberman | An economics approach to hard computational problems[END_REF][START_REF] Gomes | Algorithm portfolios[END_REF]. For example in such executions, all the algorithms run on an instance and are stopped as soon as a solution is found. Obviously, there is an overhead to pay for the wasted time lost while computing on the whole set of heuristics, however, redundancy might still be interesting. Positive applications of this idea can be found in cooperative search techniques [START_REF] El-Abd | A taxonomy of cooperative search algorithms[END_REF]. Moreover, the idea of concurrent-cooperative executions is particularly suitable in the context of new parallel architectures (large scale multi-core machines). However, it implies a smart resource sharing beyond the algorithms (memory, processor, bandwidth) that is not easy to determine because of resource limitations and the behaviors of the algorithms that depend on the amount of allocated resources. In this paper, we propose to study efficient strategies for the resource sharing problem in this context. We target two basic problems, namely SAT (Satisfiability problem) and CSP (Constraint Satisfaction Problem).

Related works

The idea of using multiple algorithms for solving a problem has been formalized inside various techniques for designing algorithms. Beyond them, we distinguish between algorithms selection, algorithms cascading and algorithm portfolio techniques. In algorithm selection [START_REF] Houstis | PYTHIA-II: a knowledge/database system for managing performance data and recommending scientific software[END_REF][START_REF] Burke | Iterated local search vs. hyper-heuristics: Towards general-purpose search algorithms[END_REF] the idea is to deal with the choice in a short amount of time of the best algorithm among a set of known algorithms for solving an instance. In algorithm cascading [START_REF] Matteo Frigo | FFTW: An adaptive software architecture for the FFT[END_REF], the problem is expressed by a generic recursive algorithm whose recursive calls can be muted in call to another algorithm. The best choice of these mutations is the key point of the technique and it depends mainly on the sizes of the sub-problems. We focus in this work on algorithms portfolio [START_REF] Huberman | An economics approach to hard computational problems[END_REF]] which proposes to run concurrently the different algorithms. Moreover, we consider parallel computing platforms for running these algorithms with various relative amount of resources.

Two types of concurrencies can be considered: The first one (resource sharing) consists in fixing the number of processors shared between the algorithms while the second (time sharing) assumes that the resource sharing might change and can be adapted during the execution. The optimization of time sharing has mainly been studied in [START_REF] Platzner | Design and implementation of a parallel constraint satisfaction algorithm[END_REF][START_REF] Streeter | Combining multiple heuristics online[END_REF]] in a theoretical perspective and in [START_REF] Xu | Satzilla: Portfolio-based algorithm selection for sat[END_REF][START_REF] Bhowmick | The role of multi-method linear solvers in pde-based simulations[END_REF] where it is applied to the resolution of the SAT problem and on solving non-linear numerical systems. We focus in this work on the first type of concurrency. For optimizing resource sharing, the main idea proposed in [START_REF] Platzner | Design and implementation of a parallel constraint satisfaction algorithm[END_REF]] is to learn it from a finite set of executions on a given testbed. It is formalized as the Resource Sharing Scheduling Problem (RSSP) which consists in determining the best proportion of resources to allocate to each algorithm for solving a finite set of instances as fast as possible. In this model, all the algorithms are executed (with an allocation that has to be determined) on all the instances concurrently until an algo-rithm finds a solution. The complexity of the problem relies on the combinatorics of the various resources allocation which have different completion times for each instance. The usage of a testbed for defining resource sharing is particular well-suited for solving hard computational problems where the algorithm performance on a set of hard instances is a well accepted qualitative metric. The original model defined in [START_REF] Platzner | Design and implementation of a parallel constraint satisfaction algorithm[END_REF]] assumes a fractional number of processors. Fractional resources sharing is hard to implement in practice. Alternative solutions based on discrete resources have then been proposed in [START_REF] Bougeret | Approximating the discrete resource sharing scheduling problem[END_REF]Ngoko and Trystram 2009b]. The study proposed in this paper is based on these works.

However, it improves the two following aspects: the first aspect is that until now, the resource sharing has been studied excluding sequential algorithms or the possibility to not select a resource to execute an algorithm. The second aspect is that the resource sharing has generally been studied assuming linear speed-up on parallel algorithms (or quasi-linear speed-up). This might not always be the case in practice. Moreover, increasing resources in a parallel algorithm might even deteriorate the execution time.

Contributions

In this work, we propose a general solution for designing algorithms portfolio which takes into account the new features described at the end of the previous section. The construction is based on a two phases approach. In a portfolio execution, there is one algorithm that leads to the interruption of the others. The first phase corresponds to an estimation of the leading algorithms, giving a set of instances. This is achieved by using a heuristic inspired by the resolution of the set cover problem. The second phase consists in assigning the right amount of resources to the algorithms in order to minimize the cost induced by the leading algorithm repartition. We show that this later problem is similar to the search of the shortest path in a graph [START_REF] Cormen | Introduction to algorithms[END_REF]]. We propose an efficient solution based on dynamic programming for solving it. Then, we present a quantitative assessment on two settings through a series of experiments. In the first setting, we simulate the concurrent execution of actual sequential SAT algorithms. In the second one, we implement a parallel algorithm for CSP based on algorithm portfolio. Experimental evaluations show that with representative testbeds, the proposed approach is suitable for defining a concurrent model of execution.

Paper organization

The paper is organized as follows: Section 2 is devoted to introduce the model of resource sharing and the description of the portfolio approach. Section 3 presents the algorithms for solving the resource sharing problem. Section 4 consists in applying the resource sharing algorithms for the construction of parallel solvers for the SAT and CSP problems. We conclude and briefly discuss some extensions of this work in Section 5.

MODEL

Parallel portfolio problem

For defining the resource sharing, we consider a setting where there are a finite set of candidates composed of algorithms and a shared-memory parallel homogeneous architecture (typically a multi-core machine). We assume a representative set of instances that captures the behavior of the candidate algorithms. In this setting the construction of an optimal resource sharing has been formalized through the dRSSP problem introduced in [START_REF] Bougeret | Combining multiple heuristics on discrete resources[END_REF]]. We recall below the formal definition of the decision version of this problem: discrete Resource Sharing Scheduling Problem (dRSSP) Instance: A finite set of instances I = {I 1 , . . . , I n }, a finite set of algorithms A = {A 1 , . . . , A k }, a set of m identical computing resources, a cost C(A i , I j , p) ∈ R + for each I j ∈ I, A i ∈ A and p ∈ {1, . . . , m}, a real value T ∈ R + .

Question: Is there a vector S = (S 1 , . . . , S k ) with S i ∈ {0, . . . , m} and 0

< k i=1 S i ≤ m such that n j=1 min 1≤i≤k {C(A i , I j , S i )|S i > 0} ≤ T ?
In order to illustrate the interest of this problem, suppose that we want to solve two instances (I 1 , I 2 ) of the same problem. There are two available parallel algorithms (namely, A 1 , A 2 ) that have each a linear speed-up. Let suppose that we have 2 resources and that the following execution cost matrix gives the execution times of each algorithm on the entire set of resources. C = 2 10 10 1 .

Observe that instance I 1 is solved in 10 time units by algorithm A 2 and in 2 time units by A 1 . Instances I 2 is solved in 1 time unit by A 2 and 10 time units by A 1 . Thus, if we consider only I 1 to solve, we can just execute A 1 . However, if A 1 is again used for solving I 2 , the total cost is 12. Now, if we give one resource to both algorithms A 1 and A 2 , the total time required becomes 4 + 2 = 6 ≤ 12.

dRSSP is derived from the original problem proposed by [START_REF] Platzner | Design and implementation of a parallel constraint satisfaction algorithm[END_REF]] adapted to a parallel homogeneous context. The NP-completeness and inapproximability of dRSSP has been proved in [START_REF] Bougeret | Combining multiple heuristics on discrete resources[END_REF]]. In the following, we will use following simplified notations:

C * (I j ) = min 1≤i≤k C(A i , I j , 1) and C(A i , I j , 1) = C(A i , I j )

Discussion about dynamic setting and cooperation

We can make at least two criticisms to dRSSP: this model suggests a static resource sharing between the algorithms, it does not take into account the fact that while executing some algorithms during a few steps, it is possible to identify some algorithms that should not lead quickly to a solution. Another criticism about dRSSP is that it does not take into account cooperation between the algorithms (for instance, for removing redundant computations).

About the static character of dRSSP, we can notice that it can be used for defining a dynamic resource sharing model. An example of this usage was suggested in [Ngoko and Trystram 2009a;[START_REF] Gebruers | Using cbr to select solution strategies in constraint programming[END_REF][START_REF] Gagliolo | Algorithm selection as a bandit problem with unbounded losses[END_REF] where a benchmark of instances is considered. For each incoming instance I to solve, using a learning mechanism, we determine the subset of benchmark instances I ′ ⊆ I whose behavior might a priori be close to that of I. Then, we can use the resource sharing given by the dRSSP solution for the instances I ′ to solve I.

About the lack of cooperation, we can remark that even if we assume that the different algorithms can share informations about their executions. The resource sharing defined by dRSSP can be used as an approximation for optimizing resources exploitation.

SOLVING ALGORITHM PORTFOLIO

As previously said, dRSSP can not be approximated within a constant factor. This suggests that we should deal with heuristics for designing polynomial time solutions.

In dRSSP, we are searching for a fixed allotment to define an optimal concurrent execution of algorithms for a set of known instances. All the algorithms with at least one resource are run until a solution is found. The resolution of an instance with this model comprises useful executions (those that lead to determine a solution for an instance) and useless ones (that will be interrupted without providing a solution). We will formalize useful executions through the notion of workload distribution. The ob-jective of such a distribution is to determine which algorithm should solve the various instances in the concurrent setting. Then, it provides an approximation for each algorithm of the load to optimize in the resource sharing. Based on this analysis, our methodology decomposes the dRSSP resolution into two phases: the prediction of the workload distribution and the resource allocation. We will present in the next section a more detailed point of view on the workload distribution.

Workload distribution

We define a workload distribution by an injection σ : I -→ A. In this application, each instance is assigned exactly to one algorithm. There can be an algorithm for which there is no assigned instance. Given a distribution σ and an instance I j , σ(I j ) gives the algorithm that has a useful execution on I j . In this definition, we suppose that there is just one algorithm with a useful execution per instance. This choice is natural since we stop the concurrent execution of algorithms on any instance as soon as one algorithm ends.

Given a workload distribution σ, we define the workload denoted by

A i as W (σ, A i ) = Ij ∈σ -1 (Ai)
C(A i , I j ). It captures the sum of sequential execution times that A i can take for solving instances assigned to it from the σ distribution. The ignorance of algorithm workload is one point that makes dRSSP different from the other classical load balancing problems. Indeed, they generally assume the knowledge of the load for each algorithm in a sequential context. For dRSSP the workload is certainly a good estimation of charges. The next section deals with its estimation.

Workload estimation

We organize the workload estimation in two parts. We first fix the objectives that must be pursued by the optimal distribution and based on them, we propose an algorithm.

Defining workload estimation problem.

Let us denote by D the set of all possible workload distributions. We formulate the problem of finding the optimal workload distribution through the Workload Estimation Problem (WEP) defined in Figure 1.

Minimize n j=1 W (σ, I j ), |A + | t 1. σ ∈ D 2. A + = {A i ∈ A|σ -1 (A i ) = ∅} Fig. 1. Workload Estimation Problem (WEP)
The various objectives of WEP are motivated as follows: it is well-known that for achieving optimal performance in parallel, the sequential execution time should also be minimized. Given a distribution σ, the sum n j=1 W (σ, I j ) is the minimal amount of time needed for solving instances in a sequential setting. By reducing this amount, one can expect to reach good performances for the resource sharing. The reduction of the sequential execution time here must not ignore that the more there are algorithms such that σ -1 (A i ) = ∅, the fewer there are resources to share per algorithm. Thus, we will have less benefit from the parallelism perspective. Indeed, if all the algorithms have a positive workload in a distribution, it is sure that n j=1 W (σ, I j ) will be minimal. However, this must not help if for example on all resources, there is an algorithm that completely dominates the other on each instance.

We formulated the search of the optimal workload as a bi-objective problem. Many concepts can be used for defining the solution for a such problem. We will use here the pareto front concept [START_REF] Dutot | Multi-objective scheduling[END_REF]] ( an illustration is provided in Figure 2). From the NP completeness result of dRSSP in [START_REF] Bougeret | Combining multiple heuristics on discrete resources[END_REF], one can easily show that this problem is NP-complete and inapproximable if the second criteria is fixed. Then, we intend to approximate optimal solutions for WEP in the next section.

A 1 A 2 A 3 {A 3 } {A 2 } {A 1 } {A 2 , A 3 } {A 1 , A 3 } {A 1 , A 2 } {A 1 , A 2 , A 3 } Fig. 2
. Illustration of possible distributions. We denote each distribution by a subset A + such that instances are assigned to algorithm in order to minimize the workload. For instance, the minimal workload for solving all the instances with {A 1 , A 3 } is 2 + 1 + 3 = 6. The sets that are circled correspond to Pareto dominant solutions

Set cover Formulation.

For solving bi-objective problems, a common approach consists in fixing one objective as a constraint and optimizing the second one. In our case, this approach is adequate since possible values of the second criteria (min{|A + |}) are discrete and finite. Let us now suppose that we are looking for the optimal workload where at most r algorithms (1 ≤ r ≤ min{k, m}) have a positive workload. The estimation of the optimal workload distribution for a fixed r can be stated as a set covering problem from the following observation : For a distribution σ, the inverse σ -1 is given by σ

-1 (A 1 ), . . . , σ -1 (A k ) where each σ -1 (A i ) ⊆ I is a subset of instances. Since σ is an injection, 1≤i≤k σ -1 (A i ) = I.
The obtention of the minimal workload can be done in selecting between all possible subsets for each σ -1 (A i ), the ones leading to the minimal workload.

For approximating σ -1 , we do the following steps: We generate all possible subsets σ -1 (A i ) for each algorithm A i . Since each of these subsets is included in I, we have a total of k.2 n sets G = {G 1 , . . . G k.2 n } that are partial assignments of instances to algorithms. Let suppose that for each subset G u , alg(G u ) is the algorithm to which we refer in the assignment (for example the subset G 1 can refer to a possible assignment for alg(G 1 ) = A 1 ). Given G, we choose between all possible selections Sel(G) ⊆ G such that For determining the complete Pareto front approximation, we repeat the set cover process with different values of r. At the end, only the solutions that are not Pareto dominated are considered.

The formulation above is based on a set cover representation of the distribution function. It proposes to solve min{k, m} problems of covering for approximating the workload distribution. However, the number of sets is exponential: thus, we have to reduce this number.

Approximating cover.

To reduce the number of sets, we observe that each set G u ∈ G gives a partial assignment for a workload distribution in which the sequential resolution time of an instance I j ∈ G u is C(alg(G u ), I j ). This time is not necessary the optimal possible sequential time C * (I j ) if we consider the time of all algorithms on I j . We will say that in the set G u , the distance at which the instance I j is solved is

C(alg(Gu),Ij ) C * (Ij )
.

For each set, there is a maximal distance value g m = max

Ij ∈Gu { C(alg(Gu),Ij ) C * (Ij )
}. This is the biggest distance at which an instance of the set is solved. From a depreciative evaluation of the quality, let us emphasize that if a partial assignment leads to solve one instance at the maximal distance g, it can also handle the possibilities of solving any other instances at g. In this way, the number of sets is restricted to g-OPT sets. A g-OPT set is an element of G that contains any instances that it can solve at a given maximal distance value. More precisely, a g-OPT set G g i corresponds to a set G u such that alg(G u ) = A i and contains all instances I j such that C(alg(G u ), I j ) ≤ gC * (I j ) (i.e. the instances that are solved with a distance at most g ∈ [1 +∞[).

The idea of g-OPT sets is to consider that in the optimal solution, if there is an algorithm that might not solve one instance optimally, this can be the case for many other instances. Thus, it is not necessary to consider all the possible partial assignments. The advantage of this restriction is that we just need to consider a polynomial number of sets. This remark is summarized in the following proposition. PROPOSITION 3.1. We can restrict distance values g m for defining all g-OPT sets

G i gm = {I j |C(A i , I j ) ≤ g m C * (I j )} to factors C(Ai,Ij ) C * (Ij )
. This result is straightforward from the definition of g-OPT sets. One of its consequence is that the number of g-OPT sets is at most ((n -1)k + 1)k.

Let us now formalize the selection of sets. For this purpose, we adopt a solution inspired on the greedy algorithms for solving the set cover problem. A dynamic price is associated to the sets at each step. Throughout the execution, the sets are selected with the most interesting price and then the covered elements are removed from the remaining sets. The algorithm ends when we have a number of sets corresponding to r distinct algorithms or a set cover. For adapting this algorithm to our case, we have to define precisely the notion of price.

Pricing sets : For pricing sets, we propose to promote sets which have an optimal solution on heavy instances (i.e. the instances with a big C * (I j )). Indeed, the impact of a non-optimal resolution of the heaviest instances might be in general more important in the workload than the non-optimal resolution of other instances. We use this observation to fix the price of a g-OPT set G g i as

P g i = I j ∈G g i C * (Ij ) g
. The price in this definition takes into account the minimal workload processed in the set but also the quality (g). One might think that for having high price, we simply need to have many instances or heavy instances in the set. However, we take into account the quality in introducing g in the price. Thus, the prices advantage the sets that solve a lot of instances optimally

ALGORITHM 1: HIF(r) G ← Generate gOPTsets() S ← ∅ C ← ∅ for G g i ∈ G do P g i ←   I j ∈G g i C * (I j ) g   end while (|S| < r and |C| < n) do (X r , Z r ) ← {(Ai, G g i ) / ∈ S|P g i is maximal} for G g i ∈ G do G g i ← G g i \Z r P g i ←   I j ∈G g i C * (I j ) g   end S ← S ∪ (X r , Z r ) C ← C ∪ Z r end (in these cases Ij ∈G g i C * (I j
) is big and g minimal). One advantage of the adopted pricing strategy is that since set corresponds to algorithms, we will be inclined to select algorithms in function of the set of instances on which they have a good execution time. This suggest the complementary of the selected algorithms.

Deriving the greedy algorithm: the problem here is to select r sets corresponding to different algorithms with minimal workload. We give in the algorithm 1 the greedy solution (called HIF for Heaviest Instances First) derived from the previous pricing strategy assuming that there are at most r sets corresponding to different algorithms to select.

At the beginning of the algorithm, the set of partial assignments (G) is initialized and prices are computed. At each step, HIF(r) selects a set corresponding to a g-OPT set and then, it removes this set from the sets of partial assignments. Then, it removes the instances covered by this set from the other sets and then, it recomputes the prices. S is the main output of HIF(r). It contains sets of instances with associated algorithm reference.

There are two conditions that might end the execution of HIF(r). The first is that r distinct algorithms have been selected. The second is that we have a workload distribution covering all the instances (|C| = n). It is important to notice that these criteria are not necessarily inclusive.

On two different steps u < v of HIF(r), some selections (X u , Z u ) and (X v , Z v ) where X u = X v can occur. We then have a selection of a set Z v associated to an algorithm that is already included in S. In such cases, by making the operation: S ← S ∪ (X r , Z r ), we will just add the set Z r to Z u in the pair (X u , Z u ) ∈ S.

At the end of HIF(r), we have a solution (X 1 , Z 1 ), . . . (X r , Z r ) where each X u corresponds to an algorithm of I associated to a set of instances Z u belonging to G. For the purpose of notations, let suppose that for each algorithm A i the set associated is G i . If an algorithm A u is not selected, we set G u to ∅. The workload of each algorithm A i can be computed as follows:

W (HIF(r), A i ) =    0 if A i is not selected in S Ij ∈Gi C(A i , I j ) otherwise.
The computed workload distribution given by the pairs (A i , G i ) might not cover all the instances. However, the strategy of prioritizing sets solving heavy instances has the advantage of leading to a distribution for instances that are the most important for the resource sharing. Moreover, we propose to complete it by adding all the non-covered instances I j to the set G i such that W (HIF(r), A i ) > 0 and C(A i , I j ) = min

Au∈A,W (HIF(r),Au) =0

C(A u , I j ) (this place I j in the set of minimal workload for it between the selected sets). Finally, we make vary r to obtain a Pareto front approximation of the workload distribution. At the end of HIF(r), S contains the estimated workload distribution.

Resource allocation

We now deal with the question of resource allocation. At this level, HIF(r) produced a distribution which associates a set of instances G i for each algorithm A i . The available resources must be allocated to all algorithms in order to minimize the time required to process the sets of instances G i . Considering a limited number of resources m, the decision version of this problem can be stated as follows:

Instance: A finite set of k instances subsets = {G 1 , . . . , G k }, a finite set of algorithms A = {A 1 , . . . , A k }, a set of m identical resources, a cost C(A i , I j , p) ∈ R + for each I j ∈ G i , A i ∈ A and p ∈ {1, . . . , m}, a real value T ∈ R + .
Question: Is there a vector S = (S 1 , . . . , S k ) with S i ∈ {0, . . . , m} and 0

< k i=1 S i ≤ m such that k i=1 Ij ∈Gi {C(A i , I j , S i )} ≤ T ?
The objective function is explained as follows: on the chosen distribution, attributing S i resources to A i leads to a processing time of Ij ∈Gi {C(A i , I j , S i )} for processing instances G i . The sum of these processing times must be minimized taking into account that there are m resources. Obviously, if S i = 0 and G i = ∅ then C(A i , I j , S i ) = +∞. This formulation differs from dRSSP because we fixed the right execution for solving the instances. We present how to solve this allocation problem in the next section.

Dynamic programming for the allocation problem.

The determination of the minimal resource allocation is similar to the search of a shortest path in a weighted graph. We consider each graph node at depth u as a partial allocation (A 1 , S 1 ), . . . , (A u , S u ). It has a weight denoted by Cost(u, m u ) = u i=1 Ij ∈Gi {C(A i , I j , S i )}. One can notice that nodes at depth k correspond to a complete allocation. The edges between nodes at depth u and u + 1 have a weight which corresponds to the amount of resources assigned for A u+1 from the a partial allocation (A 1 , S 1 ), . . . , (A u , S u ) to (A 1 , S 1 ), . . . , (A u , S u ), (A u+1 , S u+1 )) . Our objective is to find the path that leads to the node of smallest weight at depth k.

We adapt the Dijkstra algorithm [START_REF] Cormen | Introduction to algorithms[END_REF] to the resource allocation as follows: We consider k steps where each step u consists of choosing any assignment for the algorithm A u that leads to a total utilization of 0 to m resources and will have a minimal load. The cost at step u for a total utilization of u resources is denoted by Cost(u, m u ). This function obeys the following equations:

Cost(u, m u ) =      min 0≤mu-1≤mu {Cost(u -1, m u-1 ) + Ij ∈Gu C(A u , I j , m u -m u-1 )} if u > 1 Ij ∈G1 C(A 1 , I j , m 1 ) if u = 1.
The relations above can be easily derived for the the case u = 1 . The explanation of the case where u > 1 is that if we have m u resources already assigned at step u, they have been totally or partially assigned on steps 1, . . . , u. Then, the minimal cost that we can be obtained with m u resources assigned at step u is derived by considering all possible assignments at the previous step added to the workload induced by the assignment of remaining resources to A u .

It is easy to establish that the optimal allocation is determined by computing the previous relations all the possible values Cost(u, m u ), 1 ≤ u ≤ k, 0 ≤ m u ≤ m and then, choosing the resource allocation corresponding to min 1≤u≤m {Cost(k, u)}.

Finally, to find the optimal resource allocation, we proceed in generating all the Pareto solutions from HIF. For each of these solutions, we compute the optimal resource sharing, estimate its cost and then select the resource sharing with the smallest cost.

Complexity analysis

In this part, we proceed at a theoretical evaluation of our approach. We have the following result: PROPOSITION 3.2. The two phases approach proposed has a complexity in O(min{k, m}(n 2 k 2 + km 2 )) PROOF. In algorithm HIF(r), the key operation is the reinitialization of g-OPT sets prices. Since a g-OPT set has at most n instances, we can compute its price in O(n). Assuming that there are n g g-OPT sets, the reinitialization of prices in HIF(r) can be done in O(r.n g .n). Since we have n g = ((n -1)k + 1)k from proposition 3.1, we deduce that the complexity of HIF(r) is in O(r(nk) 2 ).

For the resource allocation, we construct a matrix Cost of size (m + 1) × k. From the recurrence equation of Cost, we deduce that computing C(u, m u ) requires m u comparisons. This implies that each column of the matrix yields to m(m+1) 2 comparisons. Thus, the computation of the whole matrix requires k m(m+1) 2 comparisons. Since for estimating the workload with HIF we make vary the size r in HIF(r), we obtain the result.

APPLICATIONS

For assessing the proposed approach, we consider two case studies. The first deals with the construction of a portfolio of sequential algorithms solving the well-known satisfiability problem (SAT). In this case, we did not implement a real concurrent execution of sequential algorithms, but a simulator based on the executions of actual algorithms. The interest of this study is to evaluate how close the workload distribution function issued from HIF is to the optimal. In the second case, we used our solution for defining a parallel algorithm for the Constraint Satisfaction Problem (CSP).

Designing a parallel algorithm for SAT

Given a set of clauses expressed as disjunction of boolean variables, the SAT problem consists of deciding if there is an assignment of boolean values to variables that satisfies all the clauses (makes all them true). There exist many sequential algorithms for solving this problem. We used our approach here for the development of a parallel solver based on concurrent execution of sequential algorithms and simulate the performance that could be expected.

The data for building the portfolio come from a SAT database (SatEx [START_REF] Simon | SATEx: a web-based framework for SAT experimentation[END_REF] 4 ) which gives the CPU time for the execution of a set of 23 sequential heuristics (SAT solvers) on 1303 SAT instances.

4.1.1. Brief description of the database. We present here a brief description of the benchmark and refer to [START_REF] Simon | SATEx: a web-based framework for SAT experimentation[END_REF] for a more exhaustive one. The 1303 instances of the SatEx database are issued from many domains where SAT is encountered. Some of them are: Logistic planning, formal verification of microprocessors, Scheduling. Some instances are also issued from many challenging benchmarks for SAT which are used in one of the most popular annual SAT competition5 4.1.2. SAT solvers. The SatEx database contains three main SAT solvers families:

-The DLL family with the following heuristics: asat, csat, eqsatz, nsat, satgrasp, posit, relsat, sato, sato -3.2.1, satz, satz -213, satz -215, zchaf f , -the DP family with : calcres, dr, zres, -the randomized DLL family with : ntab, ntabback, ntab -back2. relsat -200 It contains also some other algorithms: heerhugo, modoc, modoc -2.0 non classified in a family above. Beyond the set of algorithms and instances, the algorithm that solves all the instances in minimum time is zchaf f . Our goal is to show that we can do better with a parallel portfolio.

Experiments plan and results.

The general setting of our experiments on SAT is the following: we consider a multi-core parallel machine with p cores. A parallel SAT algorithm can be designed by running on each core one of the 23 sequential SAT solvers and stop when an algorithm finds a solution. In a multi-core context, the necessary synchronization for stopping all algorithms can be easily implemented by using the shared memory. The question is to know which algorithm to choose when p ≤ 23. As claimed in this paper, this choice can be learnt with a benchmark of SAT instances. Since the SAT solvers are all sequential algorithms, an optimal execution of concurrent algorithms on the benchmark can be derived from the optimal workload distribution where we have at most p SAT solvers to which an instance is assigned. We do not need to use the resource sharing phase of our approach since solvers are sequential.

This setting allows us to evaluate the first part of our two phases approach (HIF vs Optimal distribution). We associate in the evaluation other meaningful choices of distributions; Mainly:

-The Winners distribution (WIN) which assigns a positive workload only to the first (p) fastest algorithms. In this distribution, each instance is solved by the algorithm with the smallest sequential execution time between the p selected ones. It is obvious that the workload of this distribution is better than those of the best single algorithm; -The Random distribution (RAND) which arbitrarily assigns a positive workload to (p) algorithms. As for the previous one, each instance is solved by an algorithm with the smallest sequential execution time.

We use the 1303 SatEx instances as a benchmark and we assume that the execution time provided by each algorithm for each instance in SatEx is what we will have in executing the same algorithm on a single processor on the parallel system.

In the setting described above, we run two series of experiments. In the first one, we make vary p in order to compare the distributions on workload and the execution times. In the second one, we select multiple SAT solvers from the 23 available and build multiple distribution functions from them. The objective is to make a more large evaluation of the quality of the distribution function produced by HIF. The size of selected SAT solvers in these experiments vary between 1 and 20. For each size k m , we select 5(k m -2) distinct subset of SAT solvers. For each subset of size k m , we build a distribution function for values of p between 1 and k m -2. We can notice that if p = k m -1 or p = k m , the construction of a distribution is trivial.

Figure 3 depicts the workload given by the different distributions on the SatEx instances when we select p solvers among the 23 available ones. For the random distribution, the workload is estimated over 100 experiments. The figure shows that an increase on p improves any distribution. Since this is the case even for the random distribution, we conclude that the complementarity between solvers in SatEx is such that even in taking any subsets of solvers and run them concurrently, the resulting parallel solver could have a better performance that sequential ones on which it is based.

On all SAT solver selections, the HIF distribution is better that the WIN and RAND distributions. An explanation is suggested by the change between HIF and WIN workloads from p = 1 to p = 2. For selecting two solvers, HIF will choose first the best solver like WIN. While for the second solver WIN will select the one that performs well in the remaining ones, HIF will look more for a solver that is complementary with what was already chosen. In Table I we give a better view of the differences between HIF and WIN through the ratio between their workloads and the optimal distribution. HIF Optimizing resource sharing on cooperative execution of algorithms 1:13 is near-optimal when p ≥ 10. In some cases, for smaller values of p its ratio to the optimal solution can reach 2.34. This is because HIF does not adapt dynamically its selection mechanism depending on the value of p. Indeed, while with p = 1, one must give a positive workload to the best solver, when p = 2 the best solver is not necessarily the one that could be combined with a second one for having the best solution. By the same way, some solvers selected when p = 2 might not be taken when p > 3 for having optimal performances. HIF does not lead to the optimal distribution always. However, its provides a much more shorter time. This is reported in Table II which gives the optimal distribution with the optimal algorithm of [START_REF] Knuth | The Art of Computer Programming[END_REF]] for computing the different possibilities of choosing p algorithms beyond 23. These measures are taken from executions on a 4 cores hyperthreaded architectures where each core has a frequence of 2661M Hz. A schematic view of the memory organization of this architecture is given at Figure 7.

The measures of execution time reveal an explosion of the optimal distribution time when p ≥ 6 mainly due to the number of combinations that should then be taken into account. This explosion reaches a pic and then slows down when there are less combinations. The execution time of HIF is in general higher than those of the WIN or RAND distributions that are lower than 1. We explain this by the manipulation of g-OPT sets whose number is important when the number of instances is large. In our experiments, we limited the precision of maximal distance values (factors

C(Ai,Ij )
C * (Ij ) ) to 10 -3 . Even if this certainly contributed to reduce the execution time, better solutions might be envisioned.

Finally, in Table III, we report the main results of our second series of experiments. We present the ratio between the workload of different distributions with the optimal distribution for different selection of subsets of solvers. We group the ratio per size of subsets of solvers selected beyond the 23 available. This experiment confirms the fact that HIF is in general better than the other distributions (except the optimal). For each km we selected a total of 5(km -2) subsets

The experiments of this part show that the HIF distribution proposes an interesting compromise between the workload produced and the time required to compute it. We will see in the next section how it works while used for designing a portfolio of parallel solvers.

Designing a parallel algorithm for CSP

A binary Constraint Satisfaction Problem (CSP) is defined as a tuple CP = (V, D, C, I) where:

-V = {v 1 , . . . , v n } is a set of variables -D = {D(v 1 ), . . . , D(v n )} is the set of definition domains for each variable -C = {C 1 , . . . C m } is a set of constraints where each C i = (v 1 i , v 2 i ) ∈ V × V -N = {N 1 , . . . N m } is the set of incompatible assignments with each N i = {(d 1 i , d 2 i ) ∈ D(v 1 i ) × D(v 2 i )}
giving for C i the assignments that will lead to unsatisfiability. The objective is to find an assignment of values to the variables of V with no incompatible assignments. The CSP generalizes many other computational problems like SAT, graph coloring or the N queens. It is also important to notice that there exists a version of this problem where the objective is to find all the possible valid assignments. We do not consider this variant here. One of the most popular technique for solving CSP is backtracking which is presented below.

Backtracking for CSP.

The idea in backtracking is to progressively assign a value to the variables v 1 , v 2 , . . . , v n . At each level, we check if the partial assignment realized fulfills all the constraints. Let denote an assignment as a tuple:

(v 1 , f (v 1 )), . . . , (v n , f (v n ))
where v i are variables and f (v i ) are the assigned values. Given a partial assignment (v 1 , f (v 1 )), . . . , (v u , f (v u )), u < n, if it is impossible to assign a value f (v u+1 ) to v u+1 such that there is an incompatible assignment (f (v j ), f (v u+1 )), then we come back and reassign another value to v u . We proceed this way until a complete assignment is obtained.

The progressive checking of partial assignments in backtracking reduces the exploration of useless search space since a solution is not completely generated before being checked. However, it is important to have a good order for the assignment of values to variables. Such an order may reveal quickly incompatible assignments. This idea motivated the proposition of multiple ordering strategies for variables in backtracking.

We will restrict the study to 9 ordering heuristics:

-Lexicographic (lexicographic order on the variable names); -Degree ordering with: max-degree and min-degree (dual of max-degree). max-degree prioritizes variables that are the most involved in constraints. The degree of a variable is the number of constraints in which it is involved; -Forward degree ordering with: max-forward-degree(dynamically computes the maximum degree only for subset of non assigned variables), min-forward-degree (dual of max-forward-degree); -Domain ordering with: min-domain (prioritizes variables for which we have the less number of values that are not part of incompatible assignments), max-domain (dual of min ordering); -Domain/degree ordering with: min-domain/degree (prioritizes variables for which we have the smallest domain/degree), max-domain/degree (dual of min-domain/degree).

We illustrate some ordering strategies in Figure 4. We use there a bigraph representation of constraints. Edges between variables mean that there is an assignment of values that is not allowed for the variables. On this example, the will take v 1 as the first variable since its degree is the greatest one (4). max-forward-degree will put also v 1 at the first position but will differ on the position of v 5 .

In some orderings we might have situations where many variables can be selected for a same position (for example if they have the same degree). We applied the lexicographic order in these cases.

v 1 v 2 v 3 v 4 v 5 v 1 v 2 v 3 v 4 v 5 max-degree v 1 v 4 v 5 v 3 v 2 max-forward-degree v 1 v 6 v 6 v 6 v 4 v 2 v 5 v 3 v 6 v 2 v 3 v 5 v 6
All conflicts of v i = 4 are on value 1 All conflicts of v 4 are on values 1 and 2 For each of these sequential backtracking algorithms we provide a parallel implementation.

v 1 v 4 min-domain

Parallel Backtracking for CSP.

A common approach for parallelizing backtracking consists of distributing the search by splitting the domain of the first variable(v 1 ) [START_REF] Platzner | Design and implementation of a parallel constraint satisfaction algorithm[END_REF][START_REF] Habbas | Domain decomposition for parallel resolution of constraint satisfaction problems with openmp[END_REF]]. If D(v 1 ) is splitted in l subdomains, we obtain l sub-problems differing on the domain of the first variable. The parallel algorithm formulation is derived from the concurrent execution of a sequential algorithms on each sub-problem. This parallelization approach raises the question of efficient domain splitting for balancing the work among processors.

We address this question in a multithreaded context with shared memory. In this setting, concurrent executions for solving sub-problems are done with threads (each thread running a same sequential algorithm). As load balancing mechanism, we employ a dynamic work sharing beyond threads. When a thread does not have something to do, it steals a sub-problem x beyond the |D(v 1 )| that have not be considered by any thread. We proceed like this until a stopping criterion is reached (i.e. when a solution is found or when the exploration of all possibilities is complete). The search space is represented as a tree where the nodes correspond to a set of variable assignments. Each thread can steal a sub-tree where v 1 is already assigned.

From the approach described, multiple parallel backtracking can be derived for each ordering heuristic. In each of them, a thread executes a same sequential algorithm (corresponding to backtracking with an ordering heuristic) for solving a sub-problem. Since the threads have the same ordering strategy, they consider the same variable v 1 . This simplifies the distribution of the search space.

Parallel Portfolio Backtracking for CSP.

In a parallel portfolio of backtracking, we suppose that the different threads can implement different sequential backtracking algorithms in a same concurrent execution. On any instance to solve, all threads are executed until a stopping criterion is reached . We defined two versions of portfolio backtracking. The non-cooperative case where beyond threads of the same family (threads implementing the same sequential algorithms), one entire search space is shared and the cooperative case where there is a unique search space for all threads. In all theses cases the work is shared beyond threads using the dynamic work sharing principle described for parallel backtracking. For computing the resources allocation in the parallel portfolio, we used the dRSSP model with a benchmark of CSP instances. The interest of the non-cooperative case is to be more respectful of the solution suggested by dRSSP.

In the cooperative case we need to define a policy for distributing the search tree because since different threads have different orderings, the first variable might not be the same for all of them. For managing this, the first variable is taken as the variable with max-degree (for promoting propagation of constraints at the first level).

Figure 6 depicts the differences between parallel, non-cooperative and cooperative backtracking.

Stopping criteria and synchronization.

For the considered CSP instances, we decide to stop the execution when a satisfiable assignment or a proof that the problem might not be satisfiable is obtained. This yields to the following conditions for stopping threads execution:

(1) A solution is found by one thread. In this case, we have a satisfiable assignment;

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Family1(5 threads) Family1 Family2 Family1 Family2
Parallel Back. Cooperative Back. Non cooperative Back. Fig. 6. In parallel backtraking, all threads are of the same family. It might not be the case in cooperative and non-cooperative backtracking. The difference between these two later algorithms is is that computations are not repeated in the cooperative algorithm (2) The exploration of the search space is completed without finding a solution. In this case, we have an unsatisfiable assignment; (3) For the special case of non-cooperative backtracking, it is not useful to wait for the end of all threads. If indeed a family of threads ends their execution without success, then we have an unsatisfiable assignment.

Because the execution of a thread interrupt the others, a synchronization policy must be defined. We used a shared memory variable accessed for writing in mutual exclusion and events counters. While the shared memory variable serves to indicate that a satisfiable or unsatisfiable assignment is obtained, events counters serve to count the number of threads per families that ended their execution without satisfiability (useful for non-cooperative cases).

Experiments settings. Benchmark:

For the experiments, we used a benchmark of Random CSP instances generated using the model B [START_REF] Gomes | Statistical regimes across constrainedness regions[END_REF]]. In this model, a CSP class of instances is characterized by a tuple < n, m, d, t >. n here is the number of variables, m the domain size, d the proportion of constraints (we have exactly d.⌊ n(n-1) 2 ⌋) and t the proportion of unsatisfiable assignments for each constraint (we have exactly ⌊t.d 2 ⌋ non authorized assignments per constraint). Using this benchmark, 9 classes of instances taken from the review of literature mainly of [START_REF] Petrovic | Random subsets support learning a mixture of heuristics[END_REF][START_REF] Gomes | Statistical regimes across constrainedness regions[END_REF]] and described in table IV have been considered.

These classes cover different structures of a CSP problem like the situations where there are many variables and relatively small domains or fewer variables but larger domains [START_REF] Petrovic | Random subsets support learning a mixture of heuristics[END_REF]. Moreover, the experiments show that some of them (like class H) are particularly easy to solve while some others (G for example) are hard to solve.

Architecture: We run the experiments on a parallel multi-core machine with 4 cores. The cores have a frequence of 2661M Hz and hyperthreading is used in each core. We give in Figure 7 a representation of the memory organization. This organization has three cache levels. At level L1 and L2, each core has its own cache. The cache of level L3 is however shared between the different cores.

Machine (5971MB) Socket #0 L3 #0 (8192KB) L2 #1 (256KB) L2 #0 (256KB) L2 #2 (256KB) L2 #3 (256KB) L1 #0 (32KB) L1 #1 (32KB) L1 #2 (32KB) L1 #3 (32KB) Core #0 Core #1 Core #2 Core #3 PU #0 PU #1 PU #2 PU #3 PU #4 PU #5 PU #6 PU #7
Fig. 7. processors and memory organization

According to the characteristics of this architecture, we consider that the number of concurrent threads that could be executed in parallel is fixed to 8. This is deduced from the theoretical limit of the benefit that can be expected from hyperthreading.

4.2.6. Experiments plan and results. The generation of the instances is based on a random generator6 . For each of class of instances (A, B ..), we generated 25 instances. Since there are 9 classes, we have a total of 225 instances. For each instance, we measured the execution time for the different parallel backtracking algorithms. Table V reports the total time needed by each algorithm for solving the 225 instances with p threads. Each parallel backtracking algorithm is executed in at most 30 seconds.

The max-degree algorithm dominates clearly on all classes of considered instances. An interesting aspect in this table is the increase of the time of max-degree between p = 5 and p = 6. This increase is due to the parallelism overhead on the resolution of some instances when the number of threads increases. Let suppose for example that during the execution we have d sub-trees that can dynamically assigned. If for a subtree x, we have a satisfiable assignment that is the easiest one to find for all sub-trees, then we have a fast solution with x threads. If the number of threads increases, we do not have any benefit from parallelism but we have to pay an additional time for its management. These times are particular expensive when hyperthreading is used (specially when p > 4). Finally, we present the speed-up achieved by the different algorithms in table VII. For each number of resources, the speed-up is defined as the ratio between parallel and sequential time. This table shows that it is possible to obtain at a speed-up greater than 8 (the number of threads). But, this is a common feature already observed on parallel backtracking algorithms [START_REF] Habbas | Domain decomposition for parallel resolution of constraint satisfaction problems with openmp[END_REF].

Experiments on CSP mainly showed that even on a hyperthreaded architecture with an algorithm that highly dominates the others, it is possible to build a combination of algorithms based on our two phases approach with better performances than any single algorithm taken alone. However, this approach can yield to poor performances when there are few resources and when the algorithms have a super linear speed-up. These experiments also show that in a search problem where an algorithm strongly dominates the others, it might be better to duplicate the work for the best algorithm in order to avoid situations where a weaker algorithm has a space containing a solution that the best algorithm can find much faster.

CONCLUSION

We have presented in this paper a new approach based on parallel algorithms portfolio for solving a set of instances of hard problems. This approach improves the other existing parallel portfolio approaches since it takes into account more features. It has been tested on two target problems, namely SAT and CSP. The obtained portfolios are better than any other algorithms. The main reason is that the proposed mechanism provides a learning process which can determine the complementary of the algorithms in the portfolio. For SAT, the experimental results are close to the lower bound corresponding to the best parallel solution based on the concurrent executions of sequential solvers. For CSP, we show how efficient distributions of the search space between multiple CSP algorithms can be designed. The corresponding portfolio has been implemented in a multi-threaded parallel multi-core machine on random instances. It is efficient and robust in the sense where the obtained results are good even in the case of a family where an algorithm dominates all the others.

Further improvements are possible. One promising direction is to take into account potential super-linear speed-ups (when the processing time of an algorithm can drastically decrease while the resources increase). This problem is closer to load balancing instead of resource sharing. Another issue is to incorporate some dynamicity in the solution proposed for the theoretical estimation of the loads in order to obtain a more precise approximation. Finally, the overheads induced by the concurrent execution of algorithms could be introduced into the definition of dRSSP for providing a more precise theoretical time estimation.

  Gj ∈Sel(G)= I and |A(Sel)| ≤ r where A(Sel) = {alg(G j )|G j ∈ Sel(G)}, the selection of subsets with minimal workload. The condition |A(Sel)| ≤ r ensures that we do not have more that r distinct algorithms.

  Fig. 3. Distribution workload on SatEx

Fig. 4 .

 4 Fig. 4. Example of heuristic ordering for 6 variables v i . The dual versions will give the reverse order

Fig. 5 .

 5 Fig.5. Illustration of Parallel Backtacking with n threads. The search space is represented as a tree where the nodes correspond to a set of variable assignments. Each thread can steal a sub-tree where v 1 is already assigned.

Table I .

 I Average ratio between HIF, Winners, Random and the optimal for different values of p

	p	HIF WIN	RAND
	1	1.00	1.00	32.64
	2	1.00	1.58	20.26
	3	1.11	2.22	10.98
	4	1.48	2.87	8.71
	5	2.34	3.93	10.15
	6	1.62	2.21	9.27
	7	1.63	2.29	8.15
	8	1.65	2.31	7.21
	9	1.61	2.08	6.57
	10	1.00	2.08	5.23
	11	1.00	2.08	4.92
	12	1.00	1.69	4.17
	13	1.00	1.69	3.66
	14	1.00	1.69	3.21
	15	1.00	1.69	2.80
	16	1.00	1.63	2.62
	17	1.00	1.61	2.39
	18	1.00	1.00	1.86

Table II .

 II Execution time of HIF and the optimal algorithm for different values of p (here k = 23)

		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
	HIF	6	6.4	6.4	6.4	6.6	6.4	6.8	6.4	6.6	6.8	6.8	6.8	7	7.4	7	7	7	7.2
	OPT	0.0	0.0	0.2	1.4	5.6	18	45.4	94.8	162	232.4	284.4	296.2	263.4	195.4	121.8	63	27	9.2

Table III .

 III Ratio between HIF, Winners and Random for different val-

	ues of km
	km	HIF	WIN	RAND
	4	1	1	8.99
	5	1.03	1.02	6.03
	6	1.16	1.304	7.76
	7	1.26	1.41	11.76
	8	1.23	1.45	5.21
	9	1.21	1.48	6.15
	10	1.25	1.43	7.24
	11	1.26	1.46	7.48
	12	1.18	1.38	6.21
	13	1.32	1.71	5.04
	14	1.34	1.60	5.68
	15	1.26	1.61	5.45
	16	1.33	1.76	5.86
	17	1.35	1.8	10.91
	18	1.28	1.87	6.03
	19	1.272	1.74	6.19
	20	1.28	1.75	7.26

Table IV .

 IV Classes of CSP instances

	class name Model B parameters
	A	< 30, 8, 0.31, 0.34 >
	B	< 30, 8, 0.18, 0.5 >
	C	< 20, 8, 0.315, 0.34 >
	D	< 25, 10, 0.26, 0.66 >
	E	< 8, 6, 0.72, 0.45 >
	F	< 25, 10, 0.105, 0.7 >
	G	< 50, 10.0, 0.138, 0.33 >
	H	< 22, 6.0, 0.6, 0.1 >

Table V .

 V Cumulative execution times of parallel backtracking on p resources

	p	lex.	min-deg. max-deg. min-dom	max-dom	min-forward-deg.	max-forward-deg. min-dom/deg.	max-dom/deg
	1	3814	4696	526	3711	3679	3920	3346	3848	3653
	2	3513	4653	190	3493	3460	3798	2897	3505	3347
	3	3354	4653	70	3374	3318	3657	2438	3329	3190
	4	3263	4650	60	3312	3150	3576	2280	3210	3062
	5	3245	4650	53	3285	3146	3571	2214	3196	3061
	6	3268	4643	60	3307	3157	3513	2162	3272	3030
	7	3175	4643	65	3204	3129	3546	2113	3190	2980
	8	3170	4660	65	3190	3195	3645	2118	3129	2993

Table VII .

 VII Speed-up of different algorithms

	p	max-deg.	Theo. pred.	Non-Coop back.	Coop. Back.
	8	9.92	20.23	11.69	0.73
	7	8.09	14.61	9.07	0.70
	6	8.76	3.73	2.50	0.65
	5	9.92	1.30	1.14	0.65
	4	8.76	1.29	1.17	0.65
	3	7.51	1.24	1.13	0.65
	2	2.76	1.20	1.11	0.87

ACM Journal of Experimental Algorithmics, Vol. X, No. X, Article 1, Publication date: August 2011.

http://www.satcompetition.org ACM Journal of Experimental Algorithmics, Vol. X, No. X, Article 1, Publication date: August 2011.

http://www.lri.fr/~simon/satex/satex.php3

http://www.satcompetition.org ACM Journal of Experimental Algorithmics, Vol. X, No. X, Article 1, Publication date: August 2011.

available at http://www.lirmm.fr/˜bessiere/generator.html ACM Journal of Experimental Algorithmics, Vol. X, No. X, Article 1, Publication date: August 2011.

This work is supported by a FAPESP Grant at the University of S ão Paulo. Denis Trystram is partially supported by a Google research award. Permission to make digital or hard

Optimizing resource sharing on cooperative execution of algorithms 1:19 The factors give the overhead in comparison to theoretical previsions

The increase of the execution time for max-degree however suggests however a possible interesting situation. Indeed, we have an algorithm that does not need to use the total amount of possible threads. Thus, some of them can be devoted to the concurrent execution of another algorithm. The interest is that on instances where max-degree is not the best one, another algorithm may help to obtain a faster solution.

Using the benchmark data, we build cooperative and non-cooperative backtracking algorithms suggested by the resource sharing of our two phases approach. Table VI presents the execution time of these algorithms. After the resolution of dRSSP on p resources, we have a resource sharing R(p) whose estimated execution time is in column Theo. pred.. The estimation is given by the objective function of dRSSP on the allocation R(p). The execution times obtained from the real execution of the non-cooperative and cooperative backtracking algorithms with allocations R(p) are in columns Non-Coop. back and Coop. Back . The value factor in column Non-Coop. back is the ratio between the effective observed time for non-cooperative backtracking and the theoretical estimations.

The non-cooperative backtracking has a better execution time than the best algorithm on p = 7, 8 resources. This means that on some instances where max-degree is not optimal, we benefit from the execution of another concurrent algorithm. There is however an important overhead between the theoretical predicted time for the noncooperative backtracking and the real observed time. One explanation for this phenomenon is that theoretical measures do not take into account hyperthreading overhead. Indeed, the distance with theoretical estimations (factor) decreases when we reduce the number of threads (p) and it becomes more stable when there is no need to use hyperthreading.

However, when the number of resources is lower than 6 resources, the noncooperative backtracking does not perform as well as the the best algorithm. This is caused by wrong computations of the distribution function in situations of super linear speed-up. On some instances (mainly for class G), max-degree has a large time units for p = 1, 2 resources and then, its time is close to 0 when p = 3. Since the workload distribution is decided from the performance of the algorithm on the sequential case, we do not consider while computing resource sharing that max-degree can have a good execution time for the resolution of these instances. The consequence is that it has less charges and when p = 1, 2, 3, 4, 5, we assign just one resource to it. Then, this makes the time of the portfolio close to the time of max-degree with one resource.

In all the considered cases, the cooperative backtracking is worse than the other solutions. Dynamic work has a responsibility in this. Typically, there are situations where a thread will take a sub-tree on which it does not know how to find quickly a solution in comparison to another thread of a different family that is fast for the sub-tree.


François Cluzel
email: francois.cluzel@ecp.fr

Bernard Yannou

Efficiency assessment of an evolutive design system of car contours

Keywords: Interactive Genetic Algorithm, Evolutionary Design, user tests, similarity index, subjective evaluation

So as to create innovative car silhouettes, we propose in this paper a model based on an

Interactive Genetic Algorithm using an encoding of a design solution by a Fourier analysis approach. This model permits the designer to browse through generations of car profiles from an initial population of existing silhouettes. By qualitatively assessing each individual, the user converge towards solutions complying with his/her requirements and so potentially create novelty. We describe here tests for assessing the efficiency of this innovative design platform. These tests are based on a similarity matrix, a similarity measure being the perceived distance between two cars silhouettes. The results show a really satisfactory behavior of the model and open perspectives thanks to its flexible and extensible aspects.

Introduction

Novelty emergence is a priority for the style designer. So CAD tools that permit to help them in a creative way are really precious. However most of those existing tools often offer wide possibilities, but they are not really compatible with the human and sometimes artistic refinement process that leads to 2D sketches. In this field of study, the theory of Evolutionary Design (ED) seems to be very promising, and particularly Genetic Algorithms (GA) that were originally used for complex optimization problems [START_REF] Bentley | An introduction to creative evolutionary systems[END_REF] [START_REF] Renner | Genetic Algorithms in Computer Aided Design[END_REF].

GAs work as an analogy to the theory of Evolution. The structure and the apparent qualities of each design solution, called phenotype, are encoded in a genome. From an initial population of such individuals, a GA permits to create generations of individuals that are combinations of individuals of the previous generation. This operation is called crossing over. By assessing each individual the algorithm displays better and better design solutions.

The principle of an Interactive Genetic Algorithm (IGA) is the same, but the assessment is performed at each generation by the user himself [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF]. So an IGA is particularly adapted to the situation that we described above, when human decisions and aesthetics are essential.

So we propose in this paper a model based on such an algorithm to design car silhouettes. Different ways to encode the silhouette individuals exist, but they often have the disadvantage to be conceived for a given domain. Our encoding method is based on a Fourier analysis approach and can be applied to all possible objects represented by a 2D-closed-curve. We have chosen to work on car silhouettes.

In this way, innovative and new concepts are expected from the collaboration between a car designer and the IGA.

As the human aspects are really essential in this process, we need a way to validate the model by taking into account the user perception. We propose to use a similarity index, that is described in this paper, and which permits to automatically measure the perceived distance between two car profiles. Automatic and user tests have then been performed to characterize our model of shape emergence. They show a really satisfactory behavior in terms of convergence, diversity of satisfactory solutions and often interesting perspectives about the user perception.

We present in section 2 our model by detailing the encoding system and the IGA. Then in section 3 we present the construction of the similarity index and the different versions that have been tested to obtain an efficient tool. Section 4 describes the automatic test and the four user tests performed with this index to validate the model. Finally we conclude in section 5 with some remarks and perspectives.

Model description

This part has been developed in more details in a previous paper (see [START_REF] Yannou | Indirect encoding of the genes of a closed curve for interactively create innovative car silhouettes[END_REF]). However, the model description is necessary to understand the next parts of this paper.

Mathematic definition of the encoding of the silhouettes

The main difficulty when using genetic algorithms in automatic design is the encoding of the genome (see [START_REF] Nicaise | Indirect encoding of structures for evolutionary design[END_REF]). Different methods exist like direct encoding with geometrical dimensions [6; 7], tree structure [START_REF] Liu | Supporting evolution in a multi-agent cooperative design environment[END_REF] shape grammars [9; 10] or a set of predefined components [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF]. But the main disadvantage of these methods is that they are dependent from the context, that means they are conceived for a given design domain. So a difficult and time consuming process is necessary for each application.

We use here an encoding method for a 2D-closed-curve based on the works of McGarva [START_REF] Mcgarva | Harmonic representation of closed curves[END_REF], using development into Fourier series for coding the phenotype of the car silhouettes. We have personally already used this theory in [START_REF] Vasiliu | Dimensional Synthesis of Planar Mechanisms Using Neural Networks: Application to Path Generator Linkages[END_REF] for encoding a 2D-closed-curve into the five first Fourier harmonics of this decomposition. Numerous advantages are associated with such a method:

 Almost all possible 2D-closed-curves may be generated  Every detail may be represented (which is really important to stimulate emotions and create novelty)  The genomes have a constant length (which is simpler for the crossing over operation)  The Fourier harmonics are narrowly associated to apparent characteristics of the phenotype.

McGarva's theory of Fourier decomposition of a closed curve considers that the position of each point belonging to this curve can be expressed by a complex function in the complex plane:

( ) ( ) ( ) (1)
As z(t) is a closed curve, its function is periodic. The period is normalized with: z(t+1) = z(t). This function z(t) can be developed into a Fourier series, according to formula (2):

( ) ∑ ( ) (2)
where the complex Fourier coefficients can be calculated by formula (3):

∫ ( ) ( ) (3)
Coefficient a 0 is called fundamental, a 1 and a -1 represent the first harmonic, a 2 and a -2 the second harmonic, etc.

As we will see later, the function z(t) is not known as an explicit function from the beginning. Instead, we assume that the curve has been initially defined by a set of successive points z k (k=0,..,N) which belong to the curve. So, in order to calculate the a m coefficients (3) we need a numeric approximation. We obtain this approximation by dividing the curve into N segments connecting each point with its successor. We call t k the length of the curve between the first point z 0 and the point z k . Under these conditions the integral can be calculated by the trapezium formula:

∑ ( ( ( ) ( )) (4)
while z is a periodic function, (z N+1 = z 0 ). t k is defined by:

(

) 5
where the total length L is the sum of the lengths of all segments, L k is the length from the origin to the current point, with x N+1 = x 0 and y N+1 = y 0 .

To construct the genome of an object, we develop its silhouette into Fourier series and define the fundamental (the coefficient a 0 ) as gene number zero. The first harmonic (a 1 , a -1 ) will be called the first gene, the second harmonic the second gene, etc.

On the basis of the genome, the original shape of the individual can be reconstructed. Every point P k with the coordinates (x k , y k ) on the curve z * which approximates the silhouette of the car, can be calculated by formula [START_REF] Ang | Combining evolutionary algorithms and shape grammars to generate branded product design[END_REF].

( ) ∑ ( ) (6)
where t k (0≤t k ≤1) is the position on the curve and p fixes the number of harmonics used for the decoding. When p equals 1 for example, we use one harmonic to reconstruct the silhouette of the car. The more harmonics used for the decoding the more precise will be the approximation to the original curve. We call p the "precision" of decoding.

Creation of the initial car silhouettes

We divide the IGA process into two main phases (see Figure 1): the creation of an initial population, and the evolution of the population.

The initial population consists of silhouettes of several already existing car bodies. We programmed an interface in Java to border a silhouette from a photograph by clicking on the screen and to encode it into Fourier harmonics. In order to obtain a good quality, a sufficient amount of points should be used to represent as many details as possible (a number M of 60 to 80 points are needed).

However it is not sufficient to calculate a genome which is precise enough to allow a highly detailed decoding into the phenotype. Consequently we need to augment the number of points on the curve by smooth interpolations. We choose bicubic splines linking three successive points, because the result is very close to the original curve and few oscillations are noticed. We finally have a total number of N points with N>M. N has an influence on the precision of the Fourier coefficients.

The number p of harmonics used to decode the genome has a strong influence on the final result too. So it is necessary to determine a satisfactory balance between N and p. Some experiments give us an optimum for p=71 and N=1500. A last operation of normalization is necessary in order to obtain car silhouettes that are independent of a particular location or size.

Evolution of the population

Then the population can evolve (Phase 2 on Figure 1). During an operation called crossing over, the car silhouettes reproduce themselves to create new individuals. A fitness value f between 0 and 6 (where 0 is the worst and 6 the best evaluation) is assigned to each individual, according to the grade given by the user via an interface (see Figure 2). It is important to notice that the meaning of the scale is chosen by the user himself. No visual connection is given, which permits a high liberty in the design process. But it may sometimes have bad effects, because the user can change his/her own scale during the evaluations.

On the interface six individuals are displayed at a time and the user browses through all the individuals of a population (see Figure 2). He/she is supposed to evaluate all the individuals of a population. In order to permit novelty emergence and to optimize creativity, four operators have been implemented:

 Selection: decides which individuals will reproduce and create children according to the fitness values. The probability for an individual to be selected to be a parent is proportional to its fitness value (between 0 and 6).  Crossover: builds a child's genome from two selected genomes (called parents). A crossover weight W is chosen randomly between 0 and 100. A new gene g* is formed by calculating the weighted mean of the genes g m,1 and g m,2 of the parents after formula (7):

( ) (7)
 Mutation: changes in a random way a genome after the crossover.  Killing: decides which individuals from the parents' population survive and live on in the new generation. We chose a turnover rate of 0.7, in this way we do not lose potential good design solutions After choosing two individuals from the parents' population thanks to the selection operator, their genomes are combined into the genome of a child by applying the crossover and the mutation operators. Afterwards the two individuals are re-put into the parents' population. Indeed, an individual can be selected more than once by the selection operator.

Varying weight W between 0 and 1, we can obtain different new design solutions which continuously interpolate a silhouette between the two parents' silhouettes. With this interpolating crossover operator, children inherit from visual characteristics of their two parents and no ill-car is produced, but only a small space of possible solutions is explored. To enlarge the space of possible solutions and create more surprise and novelty for the designer we also apply a mutation operator.

Building of the similarity index

Is our system really capable to produce innovation and novelty? Is it possible for a user to design with the help of our system a new car body silhouette which was not part of the initial population?

To answer these questions, it could be useful to have a tool that permits to automatically measure the perceived difference between two car silhouettes and to prove that two car silhouettes are really close or not. So we propose to create a similarity index. Based on user assessments, it would permit to easily measure the difference between two car profiles. It would be a helpful tool to realize tests and prove results.

We propose here a description of the process to get this similarity index. Two different ways have been tested. The first is based on an exponential formula, and the second uses weights associated to genes.

Mathematic definition

We first define D(k,l) the distance between two genomes G k and G l . As the modifications on the ten first genes only are significant (modifications on other genes do not change anything on the car profile visual perception), the sum only consider those ten genes. And D(k,l) is:

( ) ∑ ( ) (8)
The factor ( ) is a weighting factor which should give more importance to some genes according to their participation in the modification of the silhouettes. Here g k,m is gene number m from genome k and g l,m is gene number m from genome l. One gene consists of two harmonics, called a m and a -m , which are complex numbers. So they can be written as:

a m = u m + i.v m .
Then we define:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (9)
where u max,k and u min,k (respectively v max,k and v min,k ) are the maximal and the minimal values of u k and v k on the whole initial population.

And we finally define the similarity index between two genomes k and l as:

( ) ( ) ∑ ( ) (10)
So with this definition, the similarity index in included between 0 and 100%, where 100% means that the two individuals are identical.

We now have to define the factor series ( ).

Exponential form

In this section we assume that ( ) can be written as an exponential expression which gives more importance to the first genes than to higher order genes, because a modification of the first genes impacts more the car silhouette than a modification of the last ones. So ( ) is expressed as:

( ) (11)
where a and b are two constant terms. So D(k,l) becomes:

( ) ∑ ∑ (12)
But now we need to find significant values of a and b.

We propose the following process to measure b:  Choose a genome, which is copied 3 times: G0, G1, G2.  Choose a gene i in G1 (better with a low weight to be significant): g1 i .  Choose a gene j (i ≠ j) in G2 (better with a low weight to be significant): g2 j .  Modify the gene g1 i of G1 in an arbitrary way.  Modify the gene g2 j of G2 in such a way that there is an iso-similarity (defined below) between G0 and G1 on the one hand, and G0 and G2 on the other hand.

We define the iso-similarity in this way:

Two couples of car silhouettes are iso-similar if the perceived level of similarity is the same for the two couples. For example, it would mean here that the level of similarity is the same between G0 and G1, and between G0 and G2. Practically, it means that the user has to modify the gene g2 j until the level of perceived similarity becomes the same between G0 and G1 as between G0 and G2. In that way, G2 and G1 are not identical, but their level of similarity according to G0 is the same.

Then we can write the following equality:

( ) ( ) (13)
And b is:

( ) (14)
By making n times this tests with different car profiles and different users, we get n different b values.

The final value of b adopted is the average.

The next step consists in measuring a. We propose the following process: for each of the previous comparison (between G0, G1 and G2), the user defines the level of similarity ("the similarity between G0 and G1 on the one hand and G0 and G2 on the other hand is 70%" for example). As it is very hard to express such a value, we propose to work with a 7 degrees scale; the user just chooses the level of similarity in the Table 1. So then it is possible to write:

∑ ( 15
)
where b is the average value of the previous tests.

And a is:

∑ ( ) (16)
We also obtain 2n different a. The average value is acceptable if the standard deviation is low.

The calculation of the similarity index is now completed.

Practically, we use a Java interface (see Figure 3) that permits to follow the processes described above by loading a population.

Weighted form

In the previous section, we assumed that ( ) should give more importance to the first genes that to the last ones and can be written as an exponential expression. But some experiments showed us that this assessment could be wrong when using the ten first genes only: the importance of these genes is not necessarily relative to their rank. Each ( ) is now associated to a given weight p m .

So D(k,l) becomes:

( ) ∑ (17)
To obtain the weights values, we follow the same process as with the exponential form. And we finally obtain the following expression:

(18)

By performing this test n times (n>10) with different values for i and j (to cover all the ten first genes), we have a system of n equations, that can easily be resolved with the logarithmic least square method.

The tests are performed with a modified version of the Java interface described in the previous section.

Performance comparison and choice of the index

To find out the best version of the similarity index, we perform the tests described in Figure 4. The same 30 car silhouettes are used to build the two similarity indexes. After that, the same 10 car silhouettes are used to validate it and permit to choose the best one. We obtain 2 similarity matrices, and we ask users to assess the same 10 profiles in a third matrix, according to the scale of the table. These three matrices permit to calculate two correlation coefficients.

Figure 4. Choice of the similarity index type

We obtain with the exponential form of the index a correlation coefficient of 0.45, and the value is 0.7 with the discrete weights form. So we choose this second form for the similarity index. We can now perform user tests to validate our model thanks to this similarity index.

Validation tests

To validate our model we first performed simple user tests without the similarity index, based on Kim works [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF]. These tests are described in details in [START_REF] Cluzel | User tests for the convergence of a car silhouette design model using an Interactive Genetic Algorithm[END_REF], so we just present here the important results that we obtained. The data were collected during a subjective evaluation workshop with 8 users and 2 semantic attributes (4 users worked with the word friendly, and 4 users with the word sportive). We asked the users to find out the best car silhouettes according to their semantic attribute, after 10 generations of 20 individuals and with non-hedonistic evaluations. Then we asked them to compare those best silhouettes with the best ones obtained in a basic way (profiles printed on paper, without genetic algorithm). Our conclusions are:

 The user satisfaction increases with the generations.  The results are globally better with the IGA than without.  However, some major differences can be noticed between the two semantic attributes. Indeed the user perception is really different from a user to another: sportive seems to be perceived in the same way by everyone, whereas each user has a different perception of friendly. So to confirm these observations we have proceeded to more sophisticated post-processing analysis, using the similarity index described in section 3.

Tests construction

We propose here five user tests that use the similarity index to process the same data (except the first one) as those used for the previous tests (see [START_REF] Vasiliu | Dimensional Synthesis of Planar Mechanisms Using Neural Networks: Application to Path Generator Linkages[END_REF]).

Test of "novelty emergence"

The goal of this test is to show that it is possible to reach a defined individual which is not part of the initial population.

A designer draws on a sheet of paper a car body silhouette which comes spontaneously to his/her mind and which is not part of the initial population. This car body silhouette is taken as "reference individual". By working with our system he should try to obtain in the end the silhouette he had drawn before on the paper. To cope with this, he is supposed to evaluate the car solutions which look close to the reference individual with higher grades and those who look different with lower grades. By counting the number of generations he needs to reach the reference individual, we can estimate the quality of our design system.

But this method is highly linked to the designer subjectivity, which would probably influence the results. Our objective is just to estimate the convergence ability of the model. If no automatic convergence is observed, there will probably not be a convergence with any user test. So we have preferred to perform an automatic test. The target individual is a car silhouette that has been removed from the initial population. The role of the designer is played by an algorithm, which automatically evaluates the individuals of a generation in terms of their similarity to the target individual, using the similarity index.

Test of "diversity lowering"

The aim of this test, called test of "diversity lowering" is to study:

 The evolution of the similarity index for each user along the ten generations.  The similarities that could exist between the individuals of the last generation of each designer.

The idea consists simply to calculate the similarity index between all the individuals of all the users and for all the generations of the previous workshop (see [START_REF] Cluzel | User tests for the convergence of a car silhouette design model using an Interactive Genetic Algorithm[END_REF]), and to group together the data to observe potential correlations.

A high value of similarity for the last generation would mean that the IGA converges towards a single individuals family, and so that there is a diversity lowering.

Test of "inter-designer convergence"

The goal of this test, called test of "inter-designer convergence" is to study the similarities that could exist between the last generations of all the users.

As in the previous test, the idea consists simply to calculate the similarity index between all the individuals of all the users and for all the generations of the previous workshop (see [START_REF] Cluzel | User tests for the convergence of a car silhouette design model using an Interactive Genetic Algorithm[END_REF]), and to group together the data to observe potential correlations.

Test of "superiority of the IGA model"

This test is called test of "superiority of the IGA model". Its goal is to show that our model obtains better results than without, in particular in terms of time and number of individuals.

It consists in comparing for each user the 3 best individuals of the IGA with the 3 best individuals obtained without the IGA (printed on paper, see [START_REF] Cluzel | User tests for the convergence of a car silhouette design model using an Interactive Genetic Algorithm[END_REF]) with the similarity index.

Test of 'attraction in the surroundings of initial individuals"

The last test proposed in this paper is called test of "attraction in the surroundings initial individuals".

It tries to answer the following question: is the user really able to design his/her own car silhouette, or are the final individuals influenced by the initial individuals and close to their genotypes?

Our solution to this problem is to compare the best individuals of the IGA with the 20 car silhouettes of the initial population.

Results analysis

Test of "novelty emergence"

For the test we used the car in Figure 6a as reference individual. The parameters for the Genetic Algorithm were the following: population of 100 individuals, turnover rate of 0.7 and mutation probability of 0.3. The mutation could change a gene in a range of ±(50%-200%). After 10 generations our system reached the car body silhouette in figure 4b which has a similarity index of 92%, which can be considered as a much satisfactory result.

The average fitness of the population converges over the generations to a high value (more than 95%), whereas the value of the best similarity index in the population (the fitness of the fittest individual) raises rapidly from relative low 44% to 92%.

So our system is able to automatically and quickly (less than 10 generations) converge towards a given car silhouette that is not in the initial population. It means that the space of possible solutions which can be reached by our system is large enough. This is necessary to be able to produce innovation and novelty.

Test of "diversity lowering"

These results concern the evolution of the similarity index of each user. The curves are shown on Figure 7 .The initial population has an average of 6.5% of similarity. In all the cases and for the two semantic attributes, the values increase quickly. At the 6 th generation (Generation #5 on the graph), the averages of all the users are above 40% similarity, and at about 75% for the last generation. The averages of each user (in italic in tables 4 and 5) are all included between 60 and 90% of similarity, which correspond to a level of very strong similarities.

It shows that for each user, the model converges towards a single family of car silhouettes, which are very close in terms of visual aspect. it means too that there is a real diversity lowering.

Test of "inter-designer convergence"

The results are displayed on Tables 2 and3. These matrices represent the averages of the similarity index for the two semantic attributes:

 Between all the users (in bold).  For each user (in italic). These values are treated in the previous test.

The values are really consistent with the visual aspect of the individuals. For the semantic attribute friendly, the values inter-designer (in bold) are not high, and the total average is only 9.21% similarity, whereas this total average is 50.83% for the attribute sportive. It means that the similarity between the last population of the users with the attribute sportive is very strong, and that there is no connection between those with the attribute friendly.

These results confirm rigorously that the perception of the word sportive is the same for all users (they all came to the same type of profiles), whereas each user has its own perception of the word friendly (they all have a different kind of car silhouettes at the end of the workshop). The maxima of similarity are shown in Table 4. For 5 users out of 8, the maximum is above 70% of similarity. For 2 users, the maximum is included between 20 and 30%. For the last one, it is only 2.67% of similarity.

These values mean that it is possible to obtain the same results with and without our model.

Test of 'attraction in the surroundings of initial individuals"

The results of this test are very interesting, but too sizeable to be displayed here. That is why only the case of user 2 is presented on Table 5.

This table shows that the best individuals of user 2 are very close to Individual #13 of the initial population (more than 50% of similarity). Individual #13 represents the silhouette of a Porsche 911. Two other minor influences can be noticed (with Individuals #2 and #8), but the values are below 20%, which is not significant. User 2 worked with the semantic attribute sportive, and it is important to notice that the same results are obtained with the 3 other users who worked with this attribute.

That means that they all came to the same type of profile (see section 5.1.2) which is very close to a Porsche 911. In other words, all the users perceived a sportive car as a Porsche 911.

For the semantic attribute friendly, the results are totally different. No car that influences all the users can be identified. In 2 cases out of 4, no significant influence of an initial individual is noticed. In the two other cases, such a car can be identified, with the scores of 40% of similarity, but this car is different for the two users (Porsche 911 for the one, Chevrolet Corvette C4 for the other). It shows again that this attribute is differently perceived.

Synthesis

Those five tests based on the similarity index permit to prove rigorously some results. Indeed in all cases the system turns out to converge towards a uniformized population. For the semantic attribute sportive, this profile is the same for any of the four users and is close to a Porsche 911. For the semantic attribute friendly, no similar influence from the initial population is identified, and the results really depend on the user. The perception of the attributes is really different from a user to another.

Moreover, our model converges quickly and with less individuals than without the model, which is really satisfactory.

However, some remarks can be formulated:

 The model always converges towards one profile family. Is it not possible to converge towards at least two different families?  What happens if the Porsche 911 or the other influencing cars are not in the initial population? Do the users even find them?  Why are there so many differences in the perception of the semantic attributes? Some concepts of Emotional Design could be introduced to develop a more powerful model.

Concluding remarks

From the user tests based on the similarity index that we have presented in this paper, we can say that our model is really satisfactory. Indeed we obtain very promising results: the users are satisfied and the results are better with our model than without. It also potentially creates novelty and the results are potentially different from a user to another; in fact those two assessments depend on the chosen semantic attributes, and some further works have to be done to elucidate them.

But this model is maybe not really realistic with car silhouettes, because cars are too complex to be perceived only with a profile. So some ways of improvement could permit to adapt it to obtain more realistic results. Indeed our design platform is really flexible and extensible, because it is not confined to a product field. We think that excellent results could be obtained with simple shapes. The ideal form would be a simple 2D-closed-curve from a solid of revolution, like stemmed glasses or vases. So this one way of improvement that can be studied.

Finally, it could be really interesting to allow a step of direct modifications by the designer during the genetic algorithm process, which means to modify a selected individual with a graphic tool and to reinject it in the current population.

Figure 1 .

 1 Figure 1. Diagrammatic plan of the IGA process.

Figure 2 .

 2 Figure 2. User Interface for the designer evaluation showing 6 individuals of a larger population. The designer can browse through the population by clicking on the arrow buttons.

Figure 3 .

 3 Figure 3. Java interface to calculate the parameters a and b

Figure 5 .

 5 Figure 5. Examples of best sportive (on the left) and friendly (on the right)car silhouettes (one from each user).

Figure 6 .

 6 Figure 6. Example of comparison between the reference silhouette (a) and the final resulting silhouette (b).

Figure 7 .

 7 Figure 7. Evolution of the similarity index along the generations for the two semantic attributes.

Table 1 . Scale of similarity for user assessments

 1

	Level of similarity	Value of similarity index
	0	5%
	1	30%
	2	50%
	3	65%
	4	80%
	5	90%
	6	100%

Table 2 . Similarity values between users for the semantic attribute friendly (in %).

 2

		User 5	User 6	User 7	User 8
	User 5	79,07	6,91	4,02	2,89
	User 6		89,65	20,65	8,81
	User 7			61,02	11,97
	User 8				74,16
		Total average		9,21

Table 3 . Similarity values between users for the semantic attribute sportive (in %).

 3

	100
		80
	Index	60
	Similarity	20 40	Friendly Sportive
		0
		0 1 2 3 4 5 6 7 8 9
		Generation

4 Test of "superiority of the IGA model"

Table 4 . maxima of similarity values between best individuals of the IGA and paper individuals (in %).

 4 5 users have found with the IGA at least one individual that is common or very close to one of the paper individuals. 400 individuals were proposed on paper. It took about 45 minutes for the user to evaluate them. Less than 200 individuals were used with the IGA (10 generations of 20 individuals, minus those who survive from one generation to the next one), during about 20 minutes. So we can say that our system seems to be able to bring the same results as without the model, more quickly and with fewer individuals.

		User 1	84,49
		User 2	21,26
	Sportive	User 3	80,92
		User 4	97,93
		Average	71,15
		User 5	2,67
		User 6	98,09
	Friendly	User 7	71,32
		User 8	26,94
		Average	49,75
	Total Average	60,45

Table 5 . Example of similarity values for the comparison between the best individuals of the IGA and the initial population (in %).

 5