Charlie Vanaret

François Gallard

Joaquim R R A Martins

On the Consequences of the "No Free Lunch" Theorem for Optimization on the Choice of MDO Architecture

Multidisciplinary Design Optimization (MDO) based on high-fidelity models is challenging due to the high computational cost of evaluating the objective and constraints. To choose the best MDO architecture, a trial-and-error approach is not possible due to the high cost of the overall optimization and the complexity of each implementation. We propose to address this issue by developing a generic methodology that applies to any (potentially expensive) design optimization problem. The methodology consists in generating a scalable analytic replacement function that can be quickly computed, yet captures the structure and behavior of the original high-fidelity problem. One crucial characteristic of this replacement model is that the number of inputs and outputs can be set independently, making the problem scalable. This facilitates the evaluation of MDO architectures for the original MDO problem. The methodology is applied to two academic MDO test cases: a supersonic business jet design problem and a propane combustion problem. Well-known architectures (Multidisciplinary Feasible (MDF) and Individual Disciplinary Feasible (IDF)) are benchmarked on various instances to demonstrate the dependency between the performance of the architecture and the dimensions of the problem. The results show that the "no free lunch" theorem of optimization, which states that no particular optimization algorithm holds an advantage over another when considering all possible problems, also applies to the choice of the best suited MDO architecture for an MDO problem with scalable dimensions.

Nomenclature

N

Number of disciplines x i

Local design variables of discipline i x 0 Shared (global) design variables y = (y 1 , . . . , y N )

Coupling variables y t = (y t 1 , . . . , y t N ) IDF target coupling variables y j =i

Coupling variables computed by all disciplines but the ith y i (x i , x 0 , y j =i ) Disciplinary analysis of discipline i f Objective function g

Physical inequality constraints [x, x]

Bounds on a variable x φ i i-th component of a vector-valued function φ ∂φ ∂x

Partial derivative of a function φ with respect to a variable x dφ dx

Total derivative of a function φ with respect to a variable x n x

Common dimension for all inputs of a scalable problem n y

Common dimension for all outputs of a scalable problem N x

Total input dimension of a scalable problem N y

Total output dimension of a scalable problem 1. Introduction

Motivation

MDO is the application of numerical optimization to the design of systems dependent on multiple disciplines. The multiple disciplines arise in a system that is intrinsically governed by multi-physics models, consists of multiple components, or both. MDO strives to account for the multiple disciplines at two distinct levels: the analysis level and the design level. At the analysis level, we need to ensure that all the interdisciplinary couplings are considered in a system analysis. At the design level, we need to make sure that the optimization problem is formulated such that there is enough information to perform optimal multidisciplinary design tradeoffs. Coupling variables capture the interactions between the various disciplines ; a given discipline has a subset of these coupling variables as inputs, and another subset as outputs. The sole coupled analysis however is not sufficient to achieve tradeoffs. First, the objective function must reflect the performance that we want to maximize, and the appropriate contributions to the objective from each discipline are correctly accounted for. Second, the design variables must include the variables that drive the design from each discipline. Design variables that directly affect at least two disciplines are called global variables, while design variables that directly affect only one discipline are local to that discipline. Finally, various constraints are required to obtain meaningful designs. Constraints can also be local or global, depending on whether they depend directly on variables from one or more disciplines, respectively. The general Simultaneous Analysis and Design (SAND) optimization problem 1 is: min

x,y f (x, y) subject to g(x, y) ≤ 0 (1)

R i (x i , x 0 , y) = 0, ∀i ∈ {1, . . . , N }
where N is the number of disciplines, f is the objective function, g are design constraints, x i are the local design variables of discipline i, x 0 are global (shared) design variables, x denotes (x 0 , x 1 , . . . , x N ), y are coupling variables, R i (x i , x 0 , y) := y i (x i , x 0 , y j =i ) -y i denotes the i-th disciplinary residual and y i (x i , x 0 , y j =i ) are disciplinary analyses in explicit form. For the sake of simplicity, equality constraints are rewritten as two inequalities constraints, and state variables (outputs of the disciplines) have not been written explicitly, since they can be considered as extensions of the coupling variables. In addition, a discipline that is formulated using residuals (R i (x i , x 0 , y) = 0) can be equivalently expressed in explicit form (y = y(x i , x 0 )), thanks to the implicit function theorem. In the following, we formulate the disciplines in explicit form; however, the present methodology could also be applied to disciplines in residual form. MDO architectures reformulate the original SAND problem by generating one or multiple MDO optimization problems, whose definitions may include multiple coupled simulations and additional constraints. MDO architectures aim at lowering the overall computational cost of the optimization, enabling the use of dedicated algorithms to the discipline subproblems, or both. Since all MDO architectures are derived from the original SAND problem, they should provide identical solutions.

For instance, architectures based on a Multidisciplinary Analysis (MDA), such as MDF 2 or Bilevel Integrated System Synthesis (BLISS), [START_REF] Sobieszczanski-Sobieski | Bi-Level Integrated System Synthesis (BLISS)[END_REF] solve the coupled simulation at each optimization iteration, while others, such as IDF, 2 decouple the analyses and thus only guarantee the consistency between the simulations at the convergence of the optimization.

When using high-fidelity models, the most efficient architecture is the one that requires the fewest disciplinary evaluations, since the high-fidelity model evaluations dominate the computational cost. The most efficient architecture for a particular MDO problem is not known a priori. Furthermore, an architecture that proves efficient for a particular problem may exhibit mediocre performance for a problem with different properties. This phenomenon was described in the context of optimization algorithms by Wolpert and Macready. [START_REF] Wolpert | No free lunch theorems for optimization[END_REF] They proved that on all possible optimization problems, all optimization algorithms perform the same on average. The choice of an appropriate optimization algorithm is thus instance-dependent. This is a well known issue in applied optimization: the choice of the best algorithm depends on the application, making the development of optimization algorithm an active subject of research.

Since different MDO architectures generate different optimization problems for a given SAND problem, one can expect that the same optimization algorithm will have a different performance on these problems. Therefore, the performances of MDO architectures cannot be measured independently from the performances of optimization algorithms. This makes MDO architectures subject to the "no free lunch theorem".

An analytical scalable problem was introduced by Martins and Tedford [START_REF] Martins | An object-oriented framework for multidisciplinary design optimization[END_REF][START_REF] Tedford | Benchmarking Multidisciplinary Design Optimization Algorithms[END_REF] to highlight the influence of the problem dimensionality on the performance of architectures. This analytical problem has a quadratic objective function and linear inequality constraints, and the governing equations consist of a linear system. The user may tune the number of disciplines, the number of output coupling variables associated with each discipline, the number of local design variables associated with each discipline, the number of global design variables, and the strength of coupling between the disciplines. Figure 1 compares the performance of MDO architectures on various dimensions of the local design variables and the coupling variables. This scalable problem provides an insight into the performance of MDO architectures with respect to the number of design variables or coupling variables. However, the study is limited to a simple analytical problem with a fixed structure, and is not inspired from a physical problem. In the context of high-fidelity MDO based on computational fluid dynamics (CFD) and computational structural mechanics (CSM), the disciplinary simulations typically run for a duration of several minutes to hours. An MDO problem may require hundreds of simulations, which could ultimately add up to several weeks for an optimization. A trial-and-error approach is therefore not suitable to find the best MDO architecture, or optimization algorithm, for a high-fidelity MDO problem.

Furthermore, the numerical simulations in CFD or CSM typically involve meshes with variable discretizations, depending on the desired refinement of the models. These models, when coupled, have various dimensions for the coupling variables (typically, the loads and displacement vectors in aeroelastic problems are computed from the simulation meshes). The geometry description may also vary from a study to another, impacting the number of design variables, as well as the constraints (for instance, stress limits depend on the number of structural elements in CSM models). This paper illustrates how the numbers of design and coupling variables impact the resolution of optimization problems generated by MDO.

The appropriate architecture is crucial for a particular high-fidelity based design optimization. We believe that generating a scalable analytic replacement of the physical problem that is easily computed is a step toward a better grasp of MDO architectures. Thus, we propose a methodology that transforms an expensive physical model into a model based on analytical replacements that is cheap to evaluate. The original problem is then replaced by the cheap problem, in order to benchmark MDO architectures.

The replacement function is not to be confused with a surrogate model, since it is not meant to provide an actual approximation of the original model. Instead, the replacement function is just meant to mimic the trends of the original problem. The replacement problem should therefore preserve the mathematical structure of the original one. Additionally, the replacement model is scalable, that is, the dimensions of the design variables and the coupling variables may be varied independently, which allows performance comparisons of the architectures with respect to the dimensions. The generated problems illustrate the variations in performance of the architectures and algorithms, showing that there is "no free lunch" for MDO architectures.

The proposed methodology, presented in Section 2, first builds an interpolated model for each discipline of the original problem with a limited number of evaluations, then extrapolates the interpolated model to an arbitrary dimension. Our methodology preserves the interface of the original problem, that is, the names of the inputs (design variables) and the outputs (coupling and state variables). Any high-fidelity discipline of the original problem may therefore be replaced by a cheap scalable component generated by our methodology. The interpolated models are not meant to be surrogate models, in that they do no accurately approximate the values of the original functions, they merely emulate the same mathematical structure and properties.

In Section 3, we demonstrate mathematical properties guaranteed by the methodology: the existence of solutions to the coupling problem and to the MDO problem, and the existence of bounds on the coupling variables. This last property is particularly important for IDF. Finally, in Section 4 we apply the methodology to two well-known benchmark problems in the MDO literature: the Supersonic Business Jet (SSBJ) problem of Sobieski et al., [START_REF] Sobieszczanski-Sobieski | Bi-Level Integrated System Synthesis (BLISS)[END_REF] and the propane combustion problem. 6, 7

MDO architectures

MDO architectures reformulate the original SAND problem into one or multiple optimization problems, and possibly coupling problems.

MDF

MDF is an architecture that guarantees an equilibrium between all disciplines at each iterate x of the optimization process. Consequently, should the optimization process be interrupted, the best known solution has a physical meaning. MDF generates the smallest possible optimization problem, in which the coupling variables and the state variables are removed from the set of optimization variables. The residuals, which are associated with the state variables, are removed from the set of constraints. MDF can be stated as:

min x f (x, y(x)) subject to g(x, y(x)) ≤ 0 (2)
The coupling variables y(x) are computed at equilibrium via an MDA. This amounts to solving a system of (possibly nonlinear) equations using fixed-point methods (Gauss-Seidel, Jacobi) or root-finding methods (Newton-Raphson, quasi-Newton). A prerequisite for invoking MDF is the existence of an equilibrium for any values of the design variables x encountered during the optimization process. The MDF workflow is shown in Figure 2.

Gradient-based optimization algorithms require the computation of the total (coupled) derivatives dφ dx of φ(x, y(x)), where φ ∈ {f, g}:

dφ dx = ∂φ ∂x + ∂φ ∂y dy dx (3)
Linearizing the MDA at equilibrium, we obtain

dR dx = 0 = ∂R ∂x + ∂R ∂y dy dx . (4)
Inserting the solution for dy/dx into Equation (3) leads to the expression of the total derivatives:

dφ dx = ∂φ ∂x - -ψ T φ ∂φ ∂y -dy dx ∂R ∂y -1 ∂R ∂x . ( 5
)
The product of the three matrices in this equation can be obtained in two ways. Using the direct method, the term dy/dx is obtained by solving the linear system:

∂R ∂y dy dx = - ∂R ∂x , (6)
which is independent of the function φ and must be solved for every design variable in the vector x. The total derivative is then given by Equation ( 3). The adjoint method consists in solving Equation ( 5) for the adjoint vector ψ T φ , obtained by solving the linear system: ∂R ∂y

T ψ φ = - ∂φ ∂y T , (7)
which is independent of the design variables x and must be solved for each function φ. The total derivative is then given by:

dφ dx = ∂φ ∂x + ψ T φ ∂R ∂x . (8)
Given the equations above, it is more efficient to compute coupled derivatives using the adjoint method when the number of variables is larger than the number of functions. Conversely, the direct method is more efficient when the number of functions is larger than the number of variables.

x (0) MDA        y 1 (x 1 , x 0 , y j =1 ) . . . y N (x N , x 0 , y j =N ) objective and constraints min x f (x, y(x)) s.t. g(x, y(x)) ≤ 0 y(x) f, df dx g, dg dx x Figure 2: MDF 1.2.2. IDF
IDF handles the disciplines in a decoupled fashion: all disciplinary analyses are performed independently and possibly in parallel. The coupling variables y t (called targets) are driven by the optimization algorithm and are inputs for all disciplinary analyses y i (x i , x 0 , y j t =i ), ∀i ∈ {1, . . . , N }. By comparison, MDF handles the disciplines in a coupled manner: the inputs of the disciplines are outputs of the other disciplines. IDF can be stated as:

min x,y t f (x, y t ) subject to g(x, y t ) ≤ 0 y i (x i , x 0 , y t j =i ) -y t i = 0, ∀i ∈ {1, . . . , N } (9)
Additional consistency constraints y i (x i , x 0 , y t j =i ) -y t i = 0, ∀i ∈ {1, . . . , N } ensure that the coupling variables computed by the disciplinary analyses coincide with the corresponding inputs y t of the other disciplines. This guarantees an equilibrium between all disciplines at convergence. The IDF workflow is shown in Figure 3.

x (0) , y t (0)
objective and constraints analysis 1

y 1 (x 1 , x 0 , y t j =1 ) . . . analysis N y N (x N , x 0 , y t j =N ) consistency constraints min x,y t f (x, y t ) s.t. g(x, y t ) ≤ 0 c i : y i (x i , x 0 , y t j =i ) -y t i = 0, ∀i y(x, y t ) f, df dx , df dy t g, dg dx , dg dy t c i , dci dx , dci dy t , ∀i
x, y t

Scalable analytic replacement function

The proposed approach consists in automatically developing a cheap scalable analytic replacement of an expensive physical model. The function is meant to capture the trends of the original physical model (monotonicity, convexity) and preserves the interface as well (number and names of inputs and outputs), as shown in Figure 4. It is not meant to approximate the actual values of the original model.

Table 1 details the sequence of operations that transform the original model (a coupling or a constraint) φ : R n → R m into the scalable analytic function. The second and third columns represent the functional notation of the function before and after the transformation, respectively. The evaluation cost of the resulting function is listed in the fourth column. In the following sections, we detail each of these operations. n x denotes the size of each design vector (such as x 0 in Figure 4), n y denotes the size of each coupling vector (such as y 12 ) and N x represents the total size of the design space.

→ R m φ (1d) : [0, 1] → R m expensive Interpolation φ (1d) : [0, 1] → R m φ (int) : [0, 1] → [0, 1] m cheap Extrapolation φ (int) : [0, 1] → [0, 1] m φ (ext) : [0, 1] Nx → [0, 1] ny cheap 2.1. One-dimensional restriction
The original model φ is restricted to a one-dimensional function

φ (1d) : [0, 1] → R m by evaluating it along a diagonal line in the domain [x 1 , x 1 ] × . . . × [x n , x n ]: φ (1d) (t) = φ(x 1 + t(x 1 -x 1 ), . . . , x n + t(x n -x n )) (10)
As an example, consider the original physical model φ(x 1 , x 2 ) = sin( x 2 1 + x 2 2 ) over the domain [-5, 5] 2 , show in Figure 5. The one-dimensional restriction of this function along the domain's diagonal is shown in Figure 6.

Interpolation

Let T be a set of samples in [0, 1] with cardinality |T |, on which φ (1d) : [0, 1] → R m is evaluated. For any component i ∈ {1, . . . , m} of φ (1d) , we define the direct image:

φ (1d) i (T ) := {φ (1d) i (t) | t ∈ T }. (11)
The minimal and maximal elements of this function are given by:

m i := min φ (1d) i (T ) M i := max φ (1d) i (T ), (12)
The set of scaled images is defined as:

φ (s1d) i (T ) := φ (1d) i (t) -m i M i -m i | t. ∈ T (13)
Each component i of the function φ (1d) is then approximated by a scaled polynomial interpolation φ (int) i (e.g., a third-order spline) over the data T, φ

(T ) . Note that the derivative of a one-dimensional interpolation is generally provided by interpolation libraries. Figure 7 shows a scaled third-order polynomial interpolation φ (int) of φ (1d) for our example function.

(x 1 , x 2 ) = sin( x 2 1 + x 2 2 ) Figure 6: One-dimensional restriction φ (1d) of φ(x 1 , x 2 ) = sin( x 2 1 + x 2 2 )
Figure 7:

Scaled one-dimensional interpolation φ (int) of φ(x 1 , x 2 ) = sin( x 2 1 + x 2 2 )

Extrapolation

Based on a vector of one-dimensional interpolations φ (int) i

, i ∈ {1, . . . , m} that are fast to compute, the extrapolation step generates a function φ (ext) whose input and output sizes vary independently. The way inputs and outputs of arbitrary sizes are handled is determined by two data structures: one that establishes the dependency of the outputs of the scalable function φ (ext) with respect to its inputs (described in Section 2.3.1), and the other that defines the correspondence between the interpolations φ (int) i and the components of the scaled function φ (ext) (described in Section 2.3.2).

Input-output dependency

Within a discipline, the dependency of scalable functions (with n y components each) with respect to their inputs (each of size n x ) may be fixed by constructing a sparse dependency matrix S. Each block row of S represents a function of the problem (constraint or coupling), and each block column represents an input (design variable or coupling). A nonzero element represents the dependency of a particular component of a function with respect to a particular component of an input.

The matrix S is randomly generated with a given density factor d, which determines the degree of dependency of outputs with respect to inputs for the original model. Figure 8a illustrates the dependency matrix of the SSBJ problem (see Section 4.4). The variables x shared (block column on the right) are global design variables, shared by all disciplines. The three remaining blocks in the matrix correspond to the three disciplines (aerodynamics, structures, and propulsion). Figure 8b shows the dependency matrix, generated at random, of the scalable SSBJ problem with the same dimensions as the original problem, and density factor d = 0.4. Figure 8c shows the dependency matrix, generated at random, of the scalable SSBJ problem with dimensions n x = 4 and n y = 4, and density factor d = 0.4.

In order to generate a family of consistent problems, we first generate a large random dependency matrix S, which is then restricted to the desired dimensions (Figure 9). This approach guarantees that the dependency of a given output with respect to its inputs does not change when their sizes change. Figure 9a and Figure 9b represent restrictions of the large matrix in Figure 9c (for which the inputs and outputs are scaled independently), for (n x = 2, n y = 2) and (n x = 3, n y = 3), respectively. Note that the constraints g i have the same size n x = 10 as the x i design variables.

Figure 10 illustrates various density factors of the dependency matrix. The density increases with this coefficient, from 0.2 in Figure 10a up to a full dependency matrix in Figure 10c. It is not desirable to use

Component dependency

Each component of the extrapolated function φ (ext) depends on a unique component of the one-dimensional interpolation φ (int) . The correspondence between the m original components and the n y extrapolated components may be established by picking for each extrapolated component i a random number k i in {1, . . . , m} that represents the index of the selected original component. Figure 11 illustrates a random mapping between m = 3 components of the interpolation and n y = 8 components of the extrapolated function. The first component (in purple) is selected four times (components 2, 5, 6 and 8), the second component (in orange) is selected twice (components 1 and 7) and the third component (in green) is selected twice (components 3 and 4). The function φ (ext) : [0, 1] Nx → [0, 1] ny extrapolates φ (int) to n y dimensions. The i-th component (i ∈ {1, . . . , n y }) of φ (ext) is given by:

φ (ext) i (x) = 1 |S i• | j∈Si• φ (int) ki (x j ). ( 14
)
where S i• represents the nonzero elements of the i-th row of the dependency matrix S, and

|S i• | their number. The function φ (int) ki
is detailed in Section 2.3.2 and its arguments are explained in Section 2.3.1.

Inequality constraints

By construction, the scaled constraints take their values in [0, 1], which is incompatible with the original constraints g i ≤ 0. We propose to translate a scaled constraint gi by a threshold

τ i ∈ [0, 1] as follows gi -τ i ≤ 0. ( 15
)
The thresholds (τ i ) i are computed such that the initial point is always feasible. It activates a given percentage p ∈ [0, 1] of the constraints, while the rest of the constraints are initially satisfied but inactive.

A threshold τ i is given by:

τ i = g(0) i if U (0, 1) ≤ p (active) α i + (1 -α i )g (0) i otherwise (satisfied) (16)
where U (0, 1) is a random number picked in [0, 1] with uniform probability, g

i is the constraint evaluated at the initial point, and α i ∈ [0, 1] determines to what extent inactive constraints are satisfied. Figure 12 illustrates the effect of the threshold τ i on the feasibility of the constraint gi -τ i ≤ 0 at the initial point.

τ i 0 1 g(0) i α + (1 -α)g (0)
i active violated satisfied Figure 12: Effect of τ i on the feasibility of the constraint gi -τ i ≤ 0 at the initial point

Theoretical properties

As previously mentioned, the proposed methodology aims at creating an analytical replacement function that preserves the functional characteristics of the physical model, and thus captures the properties that drive the optimization performance. For instance, if the objective function of the problem is linear or convex, the objective function of the scalable problem should also be linear or convex.

Assumptions on the interpolation

The interpolation φ (int) i should be continuous for any value of the generated samples. This is the case of many standard one-dimensional interpolation methods, such as cubic splines.

Existence of a solution to the coupling problem

We show that the explicit definition of the coupling variables in the methodology guarantees that a solution to the coupling problem between all disciplines always exists, for any value of the design variables. This result is based on Brouwer's fixed point theorem. [START_REF] Brouwer | ber abbildung von mannigfaltigkeiten[END_REF][START_REF] Park | Ninety years of the Brouwer fixed point theorem[END_REF] Theorem 1 (Brouwer's Fixed Point (1912)). Every continuous function from a convex compact subset K of an Euclidean space to K itself has a fixed point. Figure 13 illustrates Theorem 1 in one dimension. The function x → cos(x) is continuous and maps [0, 1] to itself. Therefore, cos has a fixed point x such that cos(x) = x. Graphically, this implies that the curves of cos and x → x necessarily intersect.

Theorem 2 states the existence of a solution to the coupling problem for any value of the design variables, which is a prerequisite for benchmarking MDF. However, the theorem does not guarantee that a unique solution exists, or that any numerical method (fixed-point method or root-finding algorithm) will converge.

Theorem 2 (Existence of a solution to the coupling problem). An equilibrium between all disciplines exists for any value of the design variables x, that is there exists couplings at equilibrium y (eq) such that:

y i (x i , x 0 , y (eq) j =i ) = y (eq) i , ∀i ∈ {1, . . . , N } (17)
Proof. Let us define the function µ that takes coupling variables as arguments and computes the disciplinary analyses in explicit form for fixed values of the design variables x:

µ : [0, 1] N → [0, 1] N y → µ(y) =     y 1 (x 1 , x 0 , y j =1 ) . . . y N (x N , x 0 , y j =N )     (18)
By construction of the one-dimensional restriction whose inputs and outputs are scaled in [0, 1] (see Table 1), µ is continuous and maps [0, 1] N into itself. From Theorem 1, µ has a fixed point, and therefore there exists a solution to the coupling problem for any value of x.

Preservation of the ratio of original components

We now show that the ratio of components of the interpolation φ (int) is preserved in the extrapolation φ (ext) .

Theorem 3 (Preservation of ratio). When n y approaches +∞, the ratio of components of the original functions is preserved.

Proof. The n y components of the extrapolation φ (ext) are randomly drawn with uniform probability from the m original components of the interpolation φ (int) . φ (ext) i is linear with respect to the interpolation function φ (int) ki . As n y approaches +∞, all draws become equally possible with probability 1 m , which preserves the proportions.

Existence of a feasible solution to the scalable problem Theorem 4 (Existence of a minimum).

There exists a feasible solution to the scalable problem, for any dimension of inputs and outputs.

Proof. By construction:

• The initial point is feasible with respect to the bound constraints and the nonlinear constraints. A translation is applied to the nonlinear inequality constraints, so that their value on the initial point is nonpositive (see Section 2.4). The feasible set is therefore nonempty ;

• By construction of the one-dimensional restriction and because the interpolations are continuous, the objective function is continuous and bounded from below on a closed set.

Existence of derivatives

Since the interpolation method generates continuously differentiable (C 1 ) one-dimensional interpolations, which is the case of standard methods such as splines, the scalable replacement functions are also C 1 . This is required for gradient-based optimization.

Theorem 5 (Existence of derivatives). The scalable extrapolations are continuously differentiable with respect to their inputs.

Proof. The extrapolation φ (ext) i is linear with respect to the interpolation functions, which are assumed to be C 1 (see Section 2.3.3). Therefore φ

(ext) i is also C 1 .

Existence of bounds on the target coupling variables

All inputs and outputs belong to [0, 1], which ensures that all optimization variables are bounded, in particular coupling variables in IDF.

Numerical results

We apply the methodology presented in Section 2 to two benchmark problems: the Supersonic Business Jet problem proposed by Sobieski et al., [START_REF] Sobieszczanski-Sobieski | Bi-Level Integrated System Synthesis (BLISS)[END_REF] and a propane combustion problem. [START_REF] Padula | MDO Test Suite at NASA Langley Research Center[END_REF] The aim is to produce a benchmark plot of architectures performances, similar to Figure 1. [START_REF] Martins | An object-oriented framework for multidisciplinary design optimization[END_REF] For our numerical experiments, we use the best practices for comparing methods on random problems recommended by Johnson. [START_REF] Johnson | A theoretician's guide to the experimental analysis of algorithms[END_REF]

Comparison criterion

The computational time alone is not relevant to compare the variety of architectures on a particular instance of the scalable problem: since the original (expensive) disciplines have been replaced by analytic functions that are quickly evaluated, the total time gives no indication on the execution time of the initial problem.

We define a criterion equivalent to an effort in terms of disciplinary evaluations. This criterion aggregates the following factors:

1. n evali : number of disciplinary analyses performed (possibly in parallel) in IDF over all disciplines i ; 2. n lini : number of linearizations (partial derivatives) over all disciplines i ;

+ MDA c MDA n MDA ( 19
)
where c lin represents the time ratio between a linearization and an analysis, c LU represents the time ratio between an LU factorization and an analysis, and c MDA represents the time ratio between an MDA and an analysis. These time ratios can be estimated on the original problem.

Convergence criterion of the optimization algorithm

According to Johnson, 10 the optimum value (within a given tolerance) known a posteriori is not a valid termination criterion for the optimization algorithm, since it cannot be applied in practice on real problems.

Figure 14 portrays the evolution of the residual on the iterates of MDF and IDF for a scalable instance (n x , n y , d) = (2, 8, 0.4) of the SSBJ problem (see Section 4.4) with the iterations. It highlights the presence of oscillations around the optimal solution for IDF, probably due to the difficulty to numerically satisfy equality constraints at convergence. The history of the objective function may therefore exhibit undesired plateaus at the end of convergence, which biases the comparison between architectures. Figure 14: Evolution of the residual on the optimization iterates of MDF and IDF with the iterations Our approach to address this is twofold. First, we impose strict relative and absolute tolerances (equal to 10 -12 on both the solution and its objective value), so that the optimization algorithm converges towards identical values for both architectures on a given instance. Then, we perform an a posteriori filtering of the optimization histories by removing any later iterations that do not improve the solution by at least 10 -6 . This eliminates undesired plateaus at the end of the convergence. The corresponding number of evaluations, linearizations, and MDAs are truncated accordingly.

Implementation of the architectures

The MDO architectures and test cases are implemented in the MDO platform of the MDA-MDO project at IRT Saint Exupéry. [START_REF] Gazaix | Towards the Industrialization of New MDO Methodologies and Tools for Aircraft Design[END_REF] In particular, GEMS (Generic Engine for MDO Scenarios), an in-house Python framework, is used to generate the optimization processes and host the present methodology.

MDF

The strongly and weakly coupled disciplines are computed via analysis of the coupling graph (see Figure 15 illustrating the SSBJ problem). Tarjan's algorithm 12 identifies the strongly connected components of the coupling graph, that is the subgraphs in which every vertex is reachable from every other vertex. A coupling problem is then created for each strongly connected component. The graph (see Figure 16 illustrating the SSBJ problem) represents the sequential evaluation of an MDA (equilibrium between the strongly coupled disciplines) and a weakly coupled discipline. The weakly coupled discipline is therefore not evaluated within the MDA.

IDF

The initial values of the coupling variables y t that are driven by the optimization algorithm have a considerable influence on the convergence. We initialize y t at equilibrium by computing an MDA for the initial design variable values, y t (0) = y(x (0) ). Consequently, the equality consistency constraints (Section 1.2.2) are satisfied at the initial point.

Supersonic Business Jet

Problem description

The Supersonic Business Jet (SSBJ) MDO problem was introduced in the first publication on the BLISS architecture, [START_REF] Sobieszczanski-Sobieski | Bi-Level Integrated System Synthesis (BLISS)[END_REF] and is now a benchmark for MDO methods. The problem consists in maximizing the range of an SSBJ subject to various constraints. It is composed of three disciplines (structure, aerodynamics, and propulsion) based on semi-empirical and analytical models. [START_REF] Anderson | Determination of the Characteristics of Tapered Wings[END_REF][START_REF] Raymer | Aircraft Design: A Conceptual Approach (Education Series)[END_REF] All disciplines depend on local design variables, shared design variables and coupling variables, and compute disciplinary constraints. A fourth discipline, which is weakly coupled to the others, computes the range using the Breguet-Leduc formula. The dimensions of the inputs and outputs of the disciplines are fixed, and lower than 15. Table 2 provides the initial design and the solution of the SSBJ problem. For a comparison and qualitative validation of the methodology, Figure 19 represents samplings of the original SSBJ functions when varying a single input in its full range of variation. A subset of these numerous (150) figures has been selected, among the representative ones in terms of variations, linearity, etc. Besides, all the constant outputs have been removed. Figure 18 and Figure 19 are qualitatively similar, demonstrating that the methodology conserves the functional characteristics: magnitude of variations, linearity, smoothness, and multimodality. Two specific functions in Figure 19 can cause problems to gradient-based algorithms: y 23 = f (y 12 ) and y 24 = f (y 12 ), since they are constant on a certain range, and then quadratic. Since we want to use gradient-based algorithms in the next experiments in order to address optimization problems with nearly 1000 design variables, we reduced the input range of these functions, to crop the ranges where the functions are constant. This preserves the original solution, which is not in these ranges. The present methodology could be used with the original intervals, but then, suitable optimization algorithms should be used, which may not scale up to such high dimension. And finally, the aim of this work is not to benchmark optimization algorithms but to compare MDO architectures, which justifies this choice. Figure 20 shows the evolution of the objective history with the optimization iterations for IDF and MDF, for a particular instance (n x , n y ) = (6, 16). The density factor d is set to 0.4, which is similar to that of the Jacobian matrix of the original SSBJ problem. The fixed-point algorithm invoked to converge the MDA in MDF is the Gauss-Seidel method. Figure 21 and Figure 22 display the constraint histories on the same instance for IDF and MDF, respectively. They represent the evolution of the values of the physical inequality constraints with the optimization iterations. Red indicates that a constraint is violated, green indicates that a constraint is satisfied and inactive, and white indicates that a constraint is active.

Figure 23 and Figure 24 show the cost for both architectures with a wide range of dimensions. The cost is estimated using Equation (19), with coefficients c lin = 0.5, c MDA = 2, c LU = 2 that represent a typical aerostructural MDO problem. The abscissa represents the total size N y of the coupling variables, and the multiple curves represent the two architectures over various numbers N x of design variables. Similarly to the results obtained by Martins et al., [START_REF] Martins | An object-oriented framework for multidisciplinary design optimization[END_REF] IDF performs better for this problem, for the same dimension values. Table 3 shows the breakdown of the cost estimate.

Based on these results, we observe that on average, the cost increases with N x and N y , as expected. On average, IDF is more efficient than MDF, which is probably specific to the SSBJ problem. Particular instances, such as (N x = 20, N y = 160) and (N x = 80, N y = 120), seem harder than others, and do not satisfy the general trend. They prove that there is no free lunch for MDO architectures: a particular MDO architecture does not surpass other architectures on all instances. However, the performance of an MDO architecture depends on the dimensions of the design or coupling variables. The propane combustion problem was transcribed from the NASA MDO test suite. [START_REF] Padula | MDO Test Suite at NASA Langley Research Center[END_REF][START_REF] Tedford | Benchmarking multidisciplinary design optimization algorithms[END_REF] It describes the chemical equilibrium reached during the combustion of propane in air. The variables represent each of the ten combustion products as well as the sum of the products.

In the original problem, a system of eleven nonlinear equations must be solved. To obtain an MDO problem, the equations were divided into three components such that:

• coupling exists between the disciplines ;

• the evaluation of the objective function and constraints requires the solution of the coupled system of equations.

The problem has a single shared design variable (x 0 ∈ R) and invokes three disciplines, governed by 2, 2, and 3 residual equations, respectively:

Discipline 1    x 0 + y 1 -3 = 0 y 0 y 1 -x 0 y 2 = 0 Discipline 2    0.1x 0 -y 1 y 3 40 y6 = 0 0.1x 2 0 -y 2 1 y 5 40 y6 = 0 Discipline 3        2(y 0 + y 2 ) + x 2 + x 3 -8 = 0 2x 1 + y 4 -40 = 0 y 6 -x 0 -x 1 -x 2 -x 3 -y 0 -y 1 -y 2 -y 3 -y 4 -y 5 = 0 (20)
where y = (y 0 , y 1 , y 2 , y 3 , y 4 , y 5 , y 6 ) ∈ R 7 are coupling variables. The local design variables x = (x 1 , x 2 , x 3 ) ∈ R 3 are used only in the third discipline. The propane combustion optimization problem is defined as follows: minimize x,y f 2 (x, y) + f 6 (x, y) + f 7 (x, y) + f 9 (x, y) where f 2 (x, y) = 2x 0 + x 3 + y 0 + y 1 + y 3 + y 4 + 2y 5 -10

f 6 (x, y) = √ y 0 y 1 -x 2 40x0 y6 f 7 (x, y) = √ x 0 y 0 -x 3 40y1 y6 f 9 (x, y) = x 0 √ x 1 -y 1 y 4 40 y6 subject to 0 ≤ f 2 (x, y), 0 ≤ f 6 (x, y), 0 ≤ f 7 (x, y), 0 ≤ f 9 (x, y) 0 ≤ x residuals R 1 : x 0 + y 1 -3 = 0 R 2 : y 0 y 1 -x 0 y 2 = 0 R 3 : 0.1x 0 -y 1 y 3 40 y6 = 0 R 4 : 0.1x 2 0 -y 2 1 y 5 40 y6 = 0 R 5 : 2(y 0 + y 2 ) + x 2 + x 3 -8 = 0 R 6 : 2x 1 + y 4 -40 = 0 R 7 : y 6 -x 0 -x 1 -x 2 -x 3 -y 0 -y 1 -y 2 -y 3 -y 4 -y 5 = 0
The optimal solution is x * = (1.378887, 18.426810, 1.094798, 0.931214), and the minimum objective value is 0. All inequality constraints are active at this solution.

One dimensional restrictions

Similarly to Figure 18, the interpolated functions of the propane combustion problem are plotted in Figure 25. Again, for comparison, some samplings of the original propane combustion problem functions are plotted in Figure 26. A scalable problem based on the original propane combustion problem is generated. Figure 27 shows the cost estimates for IDF and MDF architectures for a wide range of dimensions for design and coupling variables. The density factor d is set to 0.7. The fixed-point algorithm invoked to converge the MDA in MDF is the Gauss-Seidel method. The cost coefficients are set to c lin = 0.5, c MDA = 4, c LU = 2, which approximate the relative costs of the original problem. We set c MDA = 4 since the disciplines are analytical and weakly coupled, so the MDA consists in the sequential execution of the four disciplines, which costs four times that of the execution of one discipline. On average, the cost increases with N x and (linearly with) N y , as expected. IDF proves more efficient than MDF for N y < 100, while MDF outperforms IDF for N y > 100. This attests that the performance of the architectures is use case dependent, since we obtained a different trend for the SSBJ test case. Similarly to the SSBJ test case, particular instances, such as (N x = 180, N y = 225), seem computationally harder than others and do not follow the general trend. Again, this proves that there is no free lunch for MDO architectures, and that a particular MDO architecture is not more appropriate than other architectures on all instances.

Conclusion and perspectives

A new method for deriving scalable analytic problems based on a given physical problem is proposed. The analytic replacement problems preserve the functional characteristics of the original problem and they proved useful in performing a rapid benchmarking of MDO architectures.

This approach is then used to construct two scalable problems: one based on the SSBJ problem, and another based on a propane combustion problem. Numerical experiments on these two problems showed that the choice of an MDO architecture for solving a particular problem, based on performance criteria, proved to be dependent on multiple parameters, such as the dimensions of the design variables and coupling variables. A modification of these parameters may alter the performance of the architectures, thus changing their relative ranks in a benchmark. Therefore, any comparison between MDO architectures should take into account multiple design variables dimensions, coupling variables dimensions, and multiple MDO problems.

For a particular MDO problem, the most appropriate MDO architecture may be chosen using our methodology. The set of available MDO architectures was limited to MDF and IDF in this paper, but may be extended to other architectures such as BLISS and CO, or even in-house architectures.

The proposed methodology provides insights on the scalability of MDO architectures with respect to the dimensions of the problem. This may be achieved without having to execute the MDO processes with the original models. Our methodology thus requires a limited number of evaluations of the original models that is independent of the desired dimensions of the design and the coupling variables of the scalable problem.

Glossary

  (a) Effect of the number of local design variables (b) Effect of the number of coupling variables

Figure 1 :

 1 Figure 1: Analytic scalable problem 5

Figure 3 :

 3 Figure 3: IDF

1 fFigure 4 :

 14 Figure 4: Example of disciplinary interface

Figure 5 :

 5 Figure 5: Surface of the function φ(x 1 , x 2 ) = sin( x 2 1 + x 2 2 )

Figure 8 :Figure 9 :

 89 Figure 8: Dependency matrix for the SSBJ problem

Figure 10 :

 10 Figure 10: Effect of the density factor on the dependency matrix of the SSBJ problem

Figure 11 :

 11 Figure 11: Component dependency between the interpolation and the extrapolation

Figure 13 :

 13 Figure 13: One-dimensional example illustrating Brouwer's fixed point theorem

3 .

 3 n LU : number of LU factorizations during the computations of the total derivatives in MDF ; 4. n MDA : number of MDAs in MDF. The comparison criterion is given by: C = i∈disciplines n evali analyses + linearizations c lin i∈disciplines n lini + c LU n LU LU factorizations

Figure 15 :Figure 16 :

 1516 Figure 15: Initial graph of the SSBJ problem

  Figure 17 and Figure 18 display the one-dimensional interpolations of the objective function and the outputs (constraints and couplings) of the problem.

Figure 17 :

 17 Figure 17: Interpolation of SSBJ objective function

(a) g 1 (b) g 2 (c) g 3 (

 123 Figure 18: Interpolations of the SSBJ functions

Figure 20 :

 20 Figure 20: Objective function history for MDF and IDF optimizations with (n x , n y , d) = (6, 16, 0.4)

Figure 21 :

 21 Figure 21: History of the constraints for IDF with (n x , n y , d) = (6, 16, 0.4)

Figure 24 :

 24 Figure 24: Estimated cost for MDF and IDF optimizations on the SSBJ test case with N x ∈ [80, 120] and N y ∈ [40, 200]

(a) y 1 (b) y 2 (c) y 3 (d) f 2 (e) f 6 (f) f 7 (g) f 9 (

 1232679

Figure 25 :

 25 Figure 25: Interpolations of the propane problem functions

Figure 27 :

 27 Figure 27: Estimated cost for MDF and IDF optimizations for the propane test case with N x ∈ [120, 200] and N y ∈ [15, 225]

Table 1 :

 1 Methodology steps

	Transformation From	To	Resulting function
	1D restriction	φ : R n

Table 2 :

 2 Reference results of BLISS architecture applied to the SSBJ problem Assisted by the methodology described in Section 2, we generated scalable analytic replacement functions based on the SSBJ problem.

	Variable	Initial value Optimum value
	Range (nm)	535.79	3,963.88
	λ	0.25	0.38757
	x	1	0.75
	C f	1	0.75
	T h	0.5	0.15624
	t/c	0.05	0.06
	h (ft)	45,000	60,000
	M	1.6	1.4
	AR	5.5	2.5
	Λ (deg)	55	70
	S W (ft 2 )	1,000	1,500
	4.4.2. One-dimensional restrictions

  BLISS Bilevel Integrated System Synthesis. 2 IDF Individual Disciplinary Feasible. 1, 2, 4, 5, 14, 15, 20-22, 27 MDA Multidisciplinary Analysis. 2, 4, 14-16, 20, 27 MDF Multidisciplinary Feasible. 1, 2, 4, 5, 13-15, 20-22, 27 SAND Simultaneous Analysis and Design. 2, 4


Bertrand Gaiffe

A Tool for Mixing XML Annotations

Keywords: CCS CONCEPTS, Software and its engineering → Extensible Markup Language (XML), • Information systems → Data XML, multiple hierarchies, parsing

XML documents, in particular critical editions are usually very heavily annotated. They usually represent abbreviations, variant readings, edition operations etc. Among such documents, only a part of the character contents of the file is the actual edition of the text. Very often, one wants to run automatic tools on this "simple" text and thereafter re-embed the result into the original file. The tool we present here is dedicated to this embedding of annotations. In order to achieve this, the tool sets the problem as an ambiguous input and parses that ambiguous input by the grammar of the XML language. It then proposes those solutions that are syntactically correct. In case there are none, the input is modified and reparsed until at least one solution is found.

The tool is available at https://github.com/bgaiffe/XMLMixer.

INTRODUCTION

When working on XML documents, in particular when using XML to produce complex editions, one faces very heavily encoded documents. For instance, we may have: <app> <lem>n'enp<ex>re</ex>sist</lem> <rdg wit="#P">n'e<ex>m</ex>preist</rdg> <rdg wit="#J">n'emprenist</rdg> <rdg wit="#H">n'emp<ex>re</ex>sist</rdg> </app> meaning that the form n'enp<ex>re</ex>sist (in the edition) appears as n'e<ex>m</ex>preist in manuscript P, as n'emprenist in manuscript J and as n'emp<ex>re</ex>sist in manuscript H. Moreover, in n'enp<ex>re</ex>sist, the 're' part of the word is abbreviated (this is what <ex> means).

Suppose now that you have a list of terms that should appear in a glossary ; among the forms is "enpresist", then, doing it by hand, you would produce (tagging <w> the words in the glossary): <app> <lem>n'<w corresp="EMPRENDRE1">enp<ex>re</ex>sist</w> </lem> <rdg wit="#P">n'e<ex>m</ex>preist</rdg> <rdg wit="#J">n'emprenist</rdg> <rdg wit="#H">n'emp<ex>re</ex>sist</rdg> </app> (the <w> has to be entierely into the <lem> because it is shorter).

What we want to do, however, is doing that automatically; it should be as simple as running a script that from a document in which you have "n'enpresist" would produce "n'<w corresp="EMPRENDRE1">enpresist</w> and then re-embed this annotation into the original document.

In order to do that, the steps are:

(1) extract the text of the edition and the extra ornaments (notes), so that you can re-embed the notes latter. In our case, your document becomes:

<app xml:id="someId"><lem>n'enp<ex>re</ex>sist </lem></app>

(2) extract the text of the document and produce an auxiliary file that will enable you to re-embed the tagging. The auxilliary file will look like1 : 0 11 <app xml:id=''someId''><lem> 5 7 <ex> which means "app and lem", in this order, enclose the characters from 0 to 11, "ex" encloses the characters from 5 to 7. (3) produce your new tagging ; to keep the explanation short it will be:

2 11 <w corresp="EMPRENDRE1"> (4) re-embed all but the notes:

<app xml:id="someId"><lem>n'<w corresp="EMPRENDRE1">enp<ex>re</ex>sist</w> </lem></app> [START_REF] Lang | The Structure of Shared Forests in Ambiguous Parsing[END_REF] and finally, put the extra readings (the ornaments) back in order to get the complete result.

Steps 1, 2 and 5 are easily produced by XSL stylesheets.

Step 3 is what the user produces, be it automatic or not. The mixing tool we describe in the remaining of the paper takes care of step 4. The tool takes two arguments: a XML file and a companion file and embeds the annotations from the companion file into the XML file.

In the remaining of the paper, we describe the problem (section 2) and we propose a two steps approach: first produce a Direct Acyclic Graph (DAG) that enumerates possible documents and a second parse that DAG in order to keep well formed XML documents only. Section 3 describe the production of the DAG and section 4 is dedicated to parsing. In section 5, we propose a solution when no well formed document is found in the DAG. The last sections give some details about the implementation and conclude.

FORMULATION OF THE PROBLEM

In our example, the constraints are summarized in table 1. In table 1, text positions are related to the text ("n'enpresist") as follows:

0 n 1 ' 2 e 3 n 4 p 5 r 6 e 7 s 8 i 9 s 10 t 11 . Therefore, the 5 th character (p) is betweens text positions 4 and 5. Table 1 1 The constraints of table 1 may as well be represented by a direct acyclic graph (DAG) that enumerates all possible documents that verify the constraints. The DAG, between state 9 and state 14 represents all total orders compatible with the contraint that </lem> is before </app> (this is the three last lines of table 1).

The DAG is a compact representation of documents. On this particular example, three documents are represented, that correspond to possible paths trough the DAG. The three documents are: <app><lem>n'<w>enp<ex>re</ex>sist</lem></app></w> <app><lem>n'<w>enp<ex>re</ex>sist</lem></w></app> <app><lem>n'<w>enp<ex>re</ex>sist</w></lem></app> However, only the third of these documents is a well-formed XML document. If we parse the DAG with the grammar of the XML language, only one of the three documents it represents remains, that is: <app><lem>n'<w>enp<ex>re</ex>sist</w></lem></app>

In order to build the tool proposed in the introduction, we thus need to be able to produce such DAGs as the one of figure 1. We also to need a parser that parses such DAGs by the grammar of the XML language. This will be described in sections 3 an 4. It may happen however that no document from the DAG is a well formed XML document. This happens when the constraints lead to such situations as ... .... We then have a parsing failure and we have to repair the DAG. We then get something like: ... next="#next"> ...... This is the subject of section 5.

PRODUCING THE DAG

Producing the DAG boils down to get all total orderings from a partial order. As the worst case complexity of the parsing is a function of the number of nodes of the graph, we have to minimize the number of states.

The algorithm proceeds by levels2 . For each node already produced it is associated the set of elements that remain to be sorted. If such a subset is already associated to a node, we reuse it. From a node, we build outgoing edges labeled by all minimal elements. In our previous example, this cooresponds to the graph of figure 2 Two remarks here:

• we simplify the order constraints so that relations that may be deduced by transitivity are removed (this simplifies the computation of the smallest elements at each node); • the general shape of the DAG representing the whole file is a string (around the text nodes) with lattices at some points. Somehow, the DAG looks like the diagram in Figure 3. The linear sections are made of text nodes (no textNode may appear in a non linear section) and non ambiguous tags. The parser will run left to right and step in parsing will be on textnodes.

PARSING

The parser implemented is an unoptimised Earley parser [START_REF] Earley | An efficient context-free parsing algorithm[END_REF]. The only requirement is that we need a parser that admits ambiguity in parsing (typically a chart parser). We parse the input by the following grammar of the XML language (see Figure 4) 4 .

Document -> Prolog Element LMisc Document -> Prolog Element Document -> Element LMisc Document -> Element LMisc -> Misc LMisc -> Misc LMisc Misc -> Comment Misc -> PI Misc -> S Element -> "Stag" Content "Etag" Element -> "Stag" "Etag" Content -> SContent Content -> Content SContent SContent -> "TxtNode" SContent -> Element SContent -> "Comment" SContent -> "PI" Prolog -> LMisc Element -> Stag(autoclose)

Figure 4: XML Grammar

Our terminals have parameters: tag names and attributes for "Stag", textual contents for "TxtNode", etc. They ressemble SAX events (and actually the serialization of the results is done through 'Streaming Api for XML' (StAX). However, we presuppose that our documents are well-formed except for tag crossings. We therefore do not care about characters authorized or not in XML, about attributes not being repeated etc. Our grammar is thus a real simplification of the grammar for the XML language.

The result of the parsing is a grammar (the grammar of the intersection language between the XML grammar and our DAG input [START_REF] Bar-Hillel | On formal properties of simple phrase structure grammars[END_REF]). This grammar's non terminals are non terminals from the original grammar together with indexes (states of the DAG) correponding to the part of the DAG covered by the analysis.

In practice, each use of the reduction rule in the earley parser produces a rule in the grammar that expresses the results [4, 5] 5 On our example, the result (part of the result because we only have an XML fragment) would be (indexes are these of figure 1):

From this result grammar, we extract a result (there may be more than one) when the parsing is successfull. It may happen

ERROR CORRECTION

The only kind of syntactic error we want to correct are these that correspond to elements that cross. Namely, this corresponds to such situations as: ...... In such a case, we want to produce a correction like: ......<bxml:id="repair">... That is, we close the tag that needs to be closed and we reopen it later. In order to do so, when the parser fails we need to choose what error to correct (even when the parsing is succesfull, there are a lot of parsing paths that fail). The next step, once the error to correct is choosen is of course to actually correct it.

Choosing the error to corect

When the parsing fails, this means that no parsing item is produced that scans the text. Errors are failed scans, that is items of the form [i,j, α → β • Etaд("a")γ ] with Etag("a") a closing node whereas we find at state j another closing node Etag("b"). This is illustrated by the following situation: The analysis fails with two items that fail scanning into the sub-DAG after state 3. Namely:

[2, 3, Element ::= Stag("c") Content • Etag("c")] fails in state 3 because it scans Etag("a") and [1, 4, Element :: Stag("b") Content • Etag("b")] fails in state 4 because it scans Etag("a").

The correction chosen is the second one because it happens in state 4 which is at level 1 in the sub-DAG whereas the first happens at level 0 in the sub-DAG.

Doing the correction

At states such as 3 in the previous example (see Figure 5), we keep the ordering chains, that is the ordering constraints, that were used to compute the sub-DAG (in this particular case, we have only </c> and  which means, these two elements and no order constraint). We must add [, ], [, ] and [, ]: we close b before we reopen it, and we have to close b before we close a and we reopen b after we close a. The sub-DAG computed with these new elements and constraints replaces the sub-DAG between state 3 and state 6 in Figure 5. With this new sub-DAG, the parsing succeeds on the path /c, /b, /a, b. In the general case, a sole correction may not suffice ; we thus perform corection until a parse is found.

SOME DETAILS ABOUT THE IMPLEMENTATION

Classes that represent the OpenElementNodes and CloseElementNodes contains non only a QName, a Namespace and attributes, but they also contain an ID in case the openElement and the closeElement come from the companion file 6 . The idea is that a closeElement node that comes from the companion file cannot close an openElement node coming from the XML file, and, more generally that in a companion file such as:

CONCLUSION AND PERSPECTIVES

We described a tool for inserting annotations into an XML file. This tool is developped in Java and takes as arguments: an XML file and a companion file that specifies the points in the PCDATA at which XML elements have to be inserted. The tool aims at avoiding unnessessary opening and closing of tags. This gives more readable files that are also much easier to process with such tools as XSLT.

In order to insert these annotations in the most readable manner, the tool parses a DAG describing all the XML documents that respect the contraints and a parser selects those that are compatible with the grammar of the XML language [START_REF] Dymetman | Chart-parsing techniques and the prediction of valid editing moves in structured document authoring[END_REF]; at the end of the process, one of the possible solutions is given. Eventually, some XML elements are split in order to get a weel formed solution.. Three important improvements are possible:

• the result of the program is one among some possible solutions; a context free grammar enumerates the results, but we could take a schema as a parameter and filter the possible solutions through this schema.

• the program may be used to combine annotations from two versions of an XML file, or to state it another way, two XML files on the same textual contents. A probably usefull tool would align textual contents so that the two XML files may differ sligthly (for instance on whitespaces). • the memory footprint of the program is quite hight (on big XML files, it is necessary to increase the Java machine's memory). As we have ambiguous parsing, the worst case in terms of memory used is in the square of the number of states of the DAG ; however, a huge lot could be spared by optimizing the parser.

  Figure 1

  Figure 2

Figure 3

 3 Figure 3

  Figure 5

Figure 6

 6 Figure 6

  then specifies that <app> has to appear at position 0 as well as <lem>. The constraint at the second line of the table specifies that <app> has to be before <lem>.

	texte pos. symbols constraints
	0	<app>
	0	<lem>	app < lem
	2	<w>
	5	<ex>
	7	</ex>
	11	</app>
	11	</lem>	</lem> < </app>
	11	</w>
		Table

This auxiliary file is inspired by the companion files Eric de la Clergerie designed for is project "Passage'[START_REF] Villemonte De La Clergerie | Large scale production of syntactic annotations for French[END_REF], the numbers are index of characters in the text.

Levels are the cardinality of the subset yet to be totally ordered.

(l, w, a) are abbreviations for </lem>, </app> and </w>

Among the differences with a full grammar of the XML languages, we do not consider CDATA.

The grammar is cleaned at the end of the parsing: all un-reachable rules are removed.

The parameters of the program are a XML file and a companion file with the intent that the annotations from the companion file are integrated into the XML file.


Abdulqawi Saif
email: abdulqawi.saif@loria.fr

Lucas Nussbaum
email: lucas.nussbaum@loria.fr

Ye-Qiong Song
email: ye-qion.song@loria.fr

Performance Evaluation of MongoDB I/O access patterns

only one way to query the data frequent need to create indexes on demand, on large-scale data! Performance Evaluation of MongoDB I/O access patterns 3 / 17 Performance Evaluation of MongoDB I/O access patterns 3 / 17

Context

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Figure -MongoDB scanning table Vs records order on the disk

Mismatch between the scanning table vs data stored on disk

Mismatch between the scanning table vs data stored on disk

⇒Figure⇒⇒

  Figurea) Spanned & b) Unspanned allocation

Figure -MongoDB scanning

  Figure -MongoDB scanning table Vs records order on the disk

Figure

  Figure -MongoDB scanning table Vs records order on the disk

  table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk Mismatch between the scanning table vs data stored on disk Figure -MongoDB scanning table Vs records order on the disk

Performance Evaluation of MongoDB I/O access patterns

store data; think how to use after! No schema ⇒ not


EMF requirements EMF requirements Vs related work MonEx EMF design Use case experiments of MonEx Grid'5000 and MonEx Conclusions onitoring Testbed Experiments with MonEx 4 / 13

  Target: torrent completion 100 peers & one seeder Dynamic growth of network → adding a peer after n sec Emulated bandwidth of peers Monitoring Testbed Experiments with MonEx 5 / 13 Target: torrent completion 100 peers & one seeder Dynamic growth of network → adding a peer after n sec Emulated bandwidth of peers Monitoring Testbed Experiments with MonEx 5 / 13 Target: torrent completion 100 peers & one seeder Dynamic growth of network → adding a peer after n sec Emulated bandwidth of peers Monitoring Testbed Experiments with MonEx 5 / 13 Target: torrent completion 100 peers & one seeder Dynamic growth of network → adding a peer after n sec Emulated bandwidth of peers Target: torrent completion 100 peers & one seeder Dynamic growth of network → adding a peer after n sec Emulated bandwidth of peers

-1First

  to 1 sec as a polling interval -A lot of data exporters e.g. node spec, specific app. -Fixed-interval polling InfluxDB -Suitable for pushing data -Variated interval measurements Create figures that respect publication aspects e.g. X-Y figures, Y-figures, multiple Y-figures, stack figures, . . . Make a usual experiment deployment 2 Communicate data with MonEx → Expose it for Prom. or push it into InfluxDB → Use or write your own exporter(s)

Experiment Monitoring Framework (EMF) requirements

	Vendetta → code modification is necessary
	OML→ def. of measurement points, compilation with
	OML code,
	Infrastructure monitoring tools e.g. Munin Infrastructure monitoring measurement services Testbed-provided tools e.g. Munin Testbed-provided measurement services Vendetta[1] Vendetta[1] OML[2] OML[2] Infrastructure monitoring tools e.g. Munin Testbed-provided measurement services Vendetta[1] OML[2]
	Experiment-focused Experiment-focused Independent of experiments	-	-+	-	-+	-	--	-	--
	Experiment-focused			Low impact
	Independent of experiments	Controllable by users
	Independent of testbed		Real-time monitoring
	services and man. frameworks [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. Publishable figures
	Scalable [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. Archival of experiments data
	onitoring Testbed Experiments with MonEx								6 / 13

[1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13 [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13

Infrastructure monitoring tools e.g. Munin Testbed-provided measurement services Vendetta[1] OML[2] Experiment-focused

	Inf. mon. → typical for 5-10 m measurements Inf. mon. & Testbed-provided services → only by
	Vendetta→ no info. about the measurement frequency infrastructure operators
		Infrastructure monitoring tools e.g. Munin Infrastructure monitoring tools e.g. Munin Infrastructure monitoring tools e.g. Munin Infrastructure monitoring tools e.g. Munin Infrastructure monitoring tools e.g. Munin Infrastructure monitoring tools e.g. Munin	Testbed-provided measurement services Testbed-provided measurement services Testbed-provided measurement services Testbed-provided measurement services Testbed-provided measurement services Testbed-provided measurement services	Vendetta[1] Vendetta[1] Vendetta[1] Vendetta[1] Vendetta[1] Vendetta[1]	OML[2] OML[2] OML[2] OML[2] OML[2] OML[2]
	Independent of experiments Independent of testbeds services Experiment-focused Independent of experiments Independent of testbeds services Scalability Experiment-focused Independent of experiments Independent of testbeds services Scalability Low impact Experiment-focused Independent of experiments Independent of testbeds services Scalability Low impact Easy deployment Experiment-focused Independent of experiments Independent of testbeds services Scalability Low impact Easy deployment Controllable Experiment-focused Independent of experiments Independent of testbeds services Scalability Low impact Easy deployment Controllable Real-time monitoring Experiment-focused Independent of experiments Independent of testbeds services Scalability Low impact Easy deployment Controllable Real-time monitoring Producing publication-quality figures	-+ + -+ + +--+ + +---+ + +--+ -+ + +--+ --+ + +--+ -+ -+ + +--+ -+ -	-+ + -+ + + -+ + + + -+ + + + --+ + + + ---+ + + + --+ -+ + + + --+ -	------+----+-----+--+ ---+--+ + ---+--+ + ----+--+ + --	--+ --+ + --+ + + --+ + + + --+ + + + + --+ + + + + ---+ + + + + --
	[1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007.
	[2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005.
	onitoring Testbed Experiments with MonEx				6 / 13

[1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13

Inf. mon. → some with heavy nature (threads, ...)

Vendetta→ parsing events in-place [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13 Testbed-provided services→ specific infrastructure [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13 [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13 [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13 Inf. mon. & Testbed-provided services → RRDtool [1] Rensfelt, O. et al. Vendetta-a tool for flexible monitoring and management of distributed testbeds. In TridentCom 2007. [2] Singh, M. et al. ORBIT Measurements framework and library (OML) : motivations, implementation and features. In TridentCom 2005. onitoring Testbed Experiments with MonEx 6 / 13

Monitoring Testbed Experiments with MonEx

Get data

curl -X GET 127.1:5000/exp/accessPattern -H "Content-Type: application/json" -d '"measurement":"ebpf","server":"influx", "database":"monex","type":"sample"' > d.csv

Draw-it!

./monex-draw -F d.csv -x "I/O request (sample)" -y "Offset (bytes)" -p -r "random"

Grid'5000 and MonEx


Abdulqawi Saif

Lucas Nussbaum

Ye-Qiong Song

MongoDB I/O Access Patterns are under the Microscope

MongoDB I/O access patterns are under the microscope

Abdulqawi Saif 1,2,3,4 , Lucas Nussbaum 1,2,3 and Ye-Qiong Song 1,2,3 {first name.last name}@loria.fr

  poorly done by MongoDB Every Shard uses a different plan for accessing data How to get the main raison behind these results? It is a recent dynamic tracing technique in Linux It could connect to all Linux data sources Very negligible overhead (4 ns per syscall) Fits with systems in production An eBPF tool is built to evaluate the I/O access patterns: A generic tool, could be used by other systems It traces all I/O requests It reports offsets, request latencies & data size Its results could be filtered by accessed files VI. I/O access patterns using eBPF I/O access pattern on standalone Tow shards I/O access patterns (Every shard has 50% of data VII. Conclusion A performance study on MongoDB I/O access pattern is done A generic eBPF tool for testing I/O access patterns is developed A new experimental method to go beyond benchmarking results is introduced Acknowledgment This work is partially funded by the Xilopix SAS, a French startup which is behind Xaphir search engine.

1 Université de Lorraine 2 Inria Nancy Grand Est 3 CNRS, LORIA -UMR 7503 4 Xilopix SAS I. Context

MongoDB is a document-based NoSQL database NoSQL databases store semi-structured and/or unstructured data We need to create indexes to optimize querying data Based on certain industry reports, MongoDB

takes unjustified time to create indexes over a pre-stored data Benchmarks report high-level results in

general, they also use synthetic data ( = in-production data)

II. Objectives Investigation on creating indexes by MongoDB Introducing new experimental methods that could go beyond benchmarking high-level results III. Experimental settings

	Experiments are performed
	on Grid'5000 testbed
	Ubuntu 14.04, Linux 4.9.13
	Tests are performed on one
	HDD per machine
	MongoDB V3.4, replicas
	are disabled, hash sharding,
	sharding on _id

A data set of 20 million doc. is created; about 71 GB s MongoDB storage engine (WT) stores each collection on a separate file Experimental scenarios