Problem formulation Modeling improvement Stochastic Arrow-Hurwicz algorithm Numerical results Satellite model and deterministic optimization problem Engine failure Stochastic formulation

Satellite model

dr dt = v , dv dt = -µ r r 3 + F m κ , (1a)
dm dt = - T g 0 I sp δ . (1b)
(1a) : 6-dimensional state vector (position r and velocity v ).

(1b) : 1-dimensional state vector (mass m including fuel).

κ involves the direction cosines of the thrust and the on-off switch δ of the engine (3 controls), and µ, F , T , g 0 , I sp are constants.

The deterministic control problem is to drive the satellite from the initial condition at t i to a known final position r f and velocity v f at t f (given) while minimizing fuel consumption m(t i ) -m(t f ).

Deterministic optimization problem

Using equinoctial coordinates for the position and velocity ; state vector x ∈ R 7 , and cartesian coordinates for the thrust of the engine ; control vector u ∈ R 3 , the deterministic optimization problem is written as follows:

min u(•) K x(t f ) (2a)
subject to:

x(t i ) = x i , • x (t) = f x(t), u(t) , (2b)
u(t) ≤ 1 ∀t ∈ [t i , t f ] , (2c) C x(t f ) = 0 . ( 2d
)

Engine failure

Sometimes, the engine may fail to work when needed: the satellite drift away from the deterministic optimal trajectory. After the engine control is recovered, it is not always possible to drive the satellite to the final target at t f .

By anticipating such possible failures and by modifying the trajectory followed before any such failure occurs, one may increase the possibility of eventually reaching the target. But such a deviation from the deterministic optimal trajectory results in a deterioration of the economic performance.

The problem is thus to balance the increased probability of eventually reaching the target despite possible failures against the expected economic performance, that is, to quantify the price of safety one is ready to pay for. The satellite dynamics in the stochastic formulation writes:

x ξ (t i ) = x i , • x ξ (t) = f ξ x ξ (t), u(t), v ξ (t

Stochastic formulation (2)

The problem is to minimize the expected cost (fuel consumption) w.r.t. the open-loop control u and the closed-loop strategy v, the probability to hit the target at time t f being at least p.

min u(•) E min v ξ (•) K x ξ (t f ) (3a)
subject to:

x ξ (t i ) = x i , • x ξ (t) = f ξ x ξ (t), u(t), v ξ (t) , (3b)
u(t) ≤ 1 ∀t ∈ [t i , t f ] , v ξ (t) ≤ 1 ∀t ∈ [t ξ p + t ξ d , t f ] , (3c) P C x ξ (t f ) = 0 ≥ p . ( 3d

Probability as an expectation

Let I(y ) = 1 if y = 0, 0 otherwise.

Then P C x ξ (t f ) = 0 = E I C x ξ (t f ) .
Thus, Problem (3) can (shortly) be written:

min u(•) E min v ξ (•) K x ξ (t f ) (4a) s.t. E I C x ξ (t f ) ≥ p . ( 4b
)
Formulation (4) opens the possibility to make use of a stochastic Arrow-Hurwicz algorithm in order to obtain the solution u (•). Missing the target should not contribute to the cost Whenever a failure occurred, setting v ξ ≡ 0 over [t ξ p + t ξ d , t f ] generally makes the satellite misses the target and does not contribute to the probability constraint, but it forces fuel consumption to its minimum and contributes to minimize the cost function. This yields an artificially good expected cost; however, one is not interested in what happens whenever the whole mission has failed. Therefore, a better formulation is to register only scenarios when the target is effectively hit; instead of the original expected cost in (4), we thus prefer to deal with a conditional expected cost:

E K x ξ (t f ) C x ξ (t f ) = 0 = E K x ξ (t f ) × I C x ξ (t f ) E I C x ξ (t f

Conditional expected cost

The problem is reformulated as

min u(•),v(•) E K x ξ (t f ) × I C x ξ (t f ) E I C x ξ (t f ) (5a) s.t. E I C x ξ (t f ) ≥ p . ( 5b
)
Such a formulation is however not well-suited for the stochastic Arrow-Hurwicz algorithm:

a ratio of expectations is not an expectation!

Problem formulation Modeling improvement Stochastic Arrow-Hurwicz algorithm

Numerical results

Probability as an expectation

Cost refinement Final formulation

Back to a cost in expectation

Finally, instead of ( 5) we aim at solving min

u(•),v(•) E K x ξ (t f ) × I C x ξ (t f ) (8a) s.t. E I C x ξ (t f ) ≥ p . ( 8b
)
The cost function again corresponds to a standard expectation! Final formulation and associated Lagrangian

min u(•) E min v ξ (•) K x ξ (t f ) × I C x ξ (t f ) s.t. µ p -E I C x ξ (t f ) ≤ 0 .
Assuming there exists a saddle point for the associated Lagrangian, we have finally to solve

max µ≥0 min u(•) µ p + E min v ξ (•) K x ξ (t f ) -µ ×I C x ξ (t f ) .
Remark: it is convenient to put apart the no-failure event, namely tp ≥ t f in the problem formulation. For the sake of simplicity, we do not present this last problem improvement. We will denote by π f the probability of this event.

µ p + E min v ξ (•) K x ξ (t f ) -µ × I C x ξ (t f ) W (u, µ, ξ)
.

that is, max

µ≥0 min u(•) µ p + E W (u, µ, ξ) ,
we use a stochastic Arrow-Hurwicz algorithm (see [2] and [3]). The deterministic optimal control has a "bang-off-bang" shape. Along the deterministic optimal path, the probability to recover a failure is: p det ≈ 0.94.

Parameters tuning

Gradient step length:

ε k = a b + k , ρ k = c d + k ,
usual for a stochastic gradient algorithm.

Smoothing parameter:

r k = α β + k 1 3
, MQE reduced by a factor 2000 in about 100.000 iterations.

Conclusion

Main conclusion

We are able to deal with probability constraints in the optimal control framework.

Future works

From the theoretical point of view:

existence of a saddle point for the constrained problem, smoothing process (results available only for inequality constraints).

From the numerical point of view:

efficient solver for the downstream problem, computer parallelization.

  Using normalized units:t i = 0.69 and t f = 8.73.

Figure : PFigure :

 :: Figure: Probability level p < π f P. Carpentier and SOWG Optimal control under probability constraint March 3, 2011 25 / 31

3 v ξ (•) denotes the control used after the end of the failure

  ; v ξ is defined over [t ξ p + t ξ d , t f ] (if nonempty) and corresponds to a closed-loop strategy v.

	Problem formulation Modeling improvement Stochastic Arrow-Hurwicz algorithm Numerical results	Satellite model and deterministic optimization problem Engine failure Stochastic formulation
	Stochastic formulation (1)
	A failure is modeled using two random variables:
	t p : random initial time of the failure,
	t d : random duration of the failure. For every realization (t ξ p , t ξ d ):
		p ]
	and corresponds to an open-loop control,
	2 the control is 0 in [t ξ p , t ξ p + t ξ d ],

1 u(•) denotes the control used prior to any failure ; u is defined over [t i , t f ] but implemented over [t i , t ξ

  ) .

	Problem formulation Modeling improvement Stochastic Arrow-Hurwicz algorithm Numerical results	Satellite model and deterministic optimization problem Engine failure Stochastic formulation
	P. Carpentier and SOWG	Optimal control under probability constraint	March 3, 2011	7 / 31

  : exponential distribution s.t. P t p ≥ t f = π f ≈ 0.58, t

	Interplanetary mission (Earth-Mars trajectory): Problem formulation duration of the mission: 450 days,
	t
	Modeling improvement
	Stochastic Arrow-Hurwicz algorithm
	Numerical results
	Brief description
	Results for different values of p
	The price of safety

p d : exponential distribution s.t. P 2 ≤ t d ≤ 7 ≈ 0.80.

March 3, 2011

An useful lemma

Using compact notation, Problem (5) is:

in which J and Θ assume positive values.

1 If u is a solution of ( 6) and if Θ(u ) = p, then u is also a solution of min u J(u) s.t. Θ(u) ≥ p .

(7)

2 Conversely, if u is a solution of (7), and if an optimal Kuhn-Tucker multiplier β satisfies the condition

then u is also a solution of (6).

Downstream closed-loop problem

Consider the inner optimization problem:

the best thing to do is to stop immediately: W ≡ 0. If reaching the target is possible but too expensive (that is K x ξ (t f ) ≥ µ), the best thing to do is again to stop immediately: W ≡ 0. Therefore, it must be checked that one can reach the target while maintaining fuel consumption below a threshold, and the corresponding optimal control v ξ * (•) must be computed. At every iteration k, we must evaluate function W as well as its derivatives w.r.t. u(.) and µ. But W is not differentiable! First difficulty: I is not a smooth function There are specific rules to drive r k to 0 as the iteration number k goes to infinity in order to obtain the best asymptotic Mean Quadratic Error of the gradient estimates (see [1]).

Second difficulty: solving the approximated problem

The approximated closed-loop problem to solve at each iteration is:

In this setting, we have to check if the target is reached up to r .

In practice, the solution of the approximated problem is derived from the resolution of two standard optimal control problems.


Let's focus on sublevels of T , or, equivalently, to reachable sets from the target for the reversed dynamics at time T (denoted by R T ).

Semiconvexity implies that sublevels of T satisfy a kind of external sphere condition, while semiconcavity implies they satisfy the same kind of internal sphere condition.

Definition. Let K ⊂ R n be closed set. We say that (a) K satisfies an external (uniform) sphere condition if ∃r > 0 such that ∀x ∈ K, there exists v ∈ N (x; K), v = 0, for which v, yx ≤ 1 2r v yx 2 ∀y ∈ K.

(1) (b) K has positive reach (Federer TAMS '59) (proximally smooth, proxregular, ϕ-convex, ...) if (1) holds for all v ∈ N (x; K). (c) internal sphere condition = external sphere condition for K c . Properties of sets (and epigraphs) with positive reach.

1. Proximal, Fr échet, Clarke normal cones to K do coincide. Moreover (Federer, TAMS (1959)), the set

K (k) = {x ∈ K : H -dim(N (x; K)) ≥ n -k}
is H k -rectifiable (analogous to a k-face of a convex set). In particular, the set of points where the normal cone has dimension ≥ 2 (i.e., where K has a "corner") is H n-2 -rectifiable.

2. (GC-Marigonda, Calc. Var. (2006)) Let K ⊂ R n be compact with positive reach. Then K has finite perimeter in R n and the De Giorgi outer normal coincides with the unit proximal normal . Under a natural nondegeneracy condition, the reduced boundary coincides H n-1 -a.e. with the topological boundary.

3. Let Ω ⊆ R n be open and let f : Ω → R ∪ {+∞} be continuous and assume that its epigraph has positive reach. Then (GC-Marigonda, Calc. Var. ( 2006)) for a.e. x ∈ Ω there esists δ x > 0 such that f is semiconvex in B(x, δ x ). In particular, f is a.e. differentiable in Ω, is locally BV in Ω and admits a second order Taylor expansion around a.e. x ∈ Ω. Moreover, (GC-Marigonda-Wolenski (2011)) a representation formula for the generalized gradient of f using limits of convex combinations of gradients, similar to the classical formula for Lipschitz functions, holds.

Therefore epi/hypof with positive reach is a reasonable substitute of semiconvexity/concavity.

Properties of sets (and epigraphs) with uniform external sphere condition.

Theorem. (Khai T. Nguyen, JMAA 2010) Let f : R n → R be continuous and such that its epigraph satisfies a (locally) uniform external sphere condition. Then the set of points x where N (epif ; (x, f (x)) is not pointed (= contains lines) is a closed set with Lebesgue n-dimensional measure zero.

Therefore, such functions enjoy essentially the same properties of functions whose epigraph has positive reach.

Results for the minimum time function.

Consider the controlled dynamics

ẋ = f (x) + g(x)u, x(0) = x x ∈ R n , u ∈ U ⊂ R m , U compact and convex.
We are given a closed target S.

Let T (x) be the minimum time to reach the target S from x.

Assumptions.

1) f and g are C 1,1 .

2) S satisfies an internal sphere condition with uniform radius ρ > 0.

3) T is continuous on S c (controllability + small time controllability).

Theorem. (Khai T. Nguyen, JMAA 2010). Under the above assumptions, the hypograph of T satisfies a locally uniform internal sphere condition.

Theorem. (GC-Khai T. Nguyen, SICON 2010) Assume furthermore that the normal cone to the hypograph of T is pointed. Then the hypograph of T has positive reach and we can compute the generalized gradient of T .

The result is perhaps natural: if the target satisfies an internal sphere condition and the dynamics is reasonably regular, than one can expect the sublevels of T to satisfy the same condition. In fact they are backwards reachable sets from the target, therefore they can be seen (essentially) as union of sets with internal spheres.

There is a lot of work in progress (Khai T. Nguyen, A. Marigonda, D. Vittone) for the case where the target satisfies a "uniform internal Fr échet normal condition". Similar results are being obtained, but with entirely different methods. This work will have applications to the regularity of T in the case of a C 1,α -dynamics, 0 < α < 1.

The case where the target is "fat" seems to be well understood.

We switch now to the "opposite" case: we take the target to be the origin.

Theorem. (G. C, A. Marigonda, P. Wolenski, SICON ( 2006)) Let the target S be convex and the dynamics be linear:

ẋ = Ax + Bu x(0) = ξ.
If T is continuous on S c , then epi(T ) has positive reach.

The proof uses a computation of the proximal subdifferential of T using normals to the target (transported using the adjoint equation), which give the direction, and the Hamiltonian, which gives the norm (see Wolenski-Yu, 1998). This is a generalization of the first result of this type, due to Cannarsa and Sinestrari (Calc. Var. '95), where semiconvexity of T is proved, provided T is locally Lipschtz.

Example 1 (rocket car).

Consider the problem of reaching in minimum time the origin subject to the dynamics

ẍ = u ∈ [-1, 1].
The minimum time function is:

T (x, y) =    y + 2 y 2 /2 + x for x ≥ -y|y|/2, -y + 2 y 2 /2 -x for x < -y|y|/2 -0.4 -0.2 0 0.2 0.4 -0.4 -0.2 0 0.2 0.4 0 0.5 1 1.5 2 -0.4 -0.2 0 0.2 0.4
Example 2 (Cannarsa and Sinestrari). Consider the problem of reaching in minimum time the origin subject to the dynamics

   ẋ = -y 2 + u 1 , u 1 ∈ [-1, 1] ẏ = u 2 , u 2 ∈ [-1, 1]. Example 3.    ẋ = y 2 + y ẏ = -y 2 + u, u ∈ [-1, 1].

Vari abl e Parameter

Sel ect the parameter T i n the defini ti on l i st to change i ts val ue. You can al so cl i ck on the tri angl e next to i t to start the ani mati on.

The linearization around the origin is:

Example 1.

x y

′ = 0 1 0 0 x y + 0 1 u Example 2.
x y

′ = 0 0 0 0 x y + 1 0 0 1 u 1 u 2
Example 3.

x y

′ = 0 1 0 0 x y + 0 1 u
The linear part in Example 2 is not strong enough.

Definition. The linear system

ẋ = Ax + Bu, x ∈ R n , u ∈ U ⊂ R m , (2)
where

B = (b 1 , . . . , b m ) ∈ M n×m is normal if for all i = 1, . . . , m rank b i , Ab i , . . . , A n-1 b i = n
(i.e., the system is controllable at the origin by using each control separately). Of course the linearized dynamics of Example 2 is not normal.

Classical (Hermes-LaSalle): the system (2) is normal iff the reachable set from the origin at time T is strictly convex (for all times T ).

A refinement of this classical result.

Theorem. (GC, Khai T. Nguyen). Assume that (2) is normal. Then for all T > 0 there exists γ > 0 (depending only on A, B, n, m, T ) such that for all x ∈ R T , for all v ∈ N (R T ; x) one has v, yx ≤ -γ v yx n ∀y ∈ R T .

Remark. The power n is optimal:

x (n) = u ∈ [-1, 1].
The proof is rather technical and has two main ingredients:

• an analysis of the zeros of the switching functions

g i (s) = e As b i , ζ , ζ ∈ R n
and of its derivatives (essentially the interval [0, T ] is split into n disjoint sets where one of g i , g ′ i , . . . , g (n-1) i is bounded away from zero; those sets are disjoint union of a finite [and computable] number of intervals);

• an integral inequality b a (t -a) k K(t) dt ≥ 1 k + 1 b a K(t) dt k+1 , where K ∈ L ∞ , 0 ≤ K ≤ 1, k ∈ N.
It is natural conjecturing that for a (smooth enough) nonlinear system

ẋ = F (x) + G(x)u, u ∈ U ⊂ R m , x ∈ R n such that • F (0) = 0
• the linearization at the origin is normal

• G(x) -G(0) = o( x n ) for x → 0
then the reachable set from the origin R T at any time T sufficiently small is strictly convex (or at least satisfies a uniform external sphere condition).

However, for the moment we can prove the following Theorem. (GC, Khai T. Nguyen) consider the dynamics

ẋ = F (x) + G(x)u, x ∈ R 2 , |u| ≤ 1. Assume F (0) = 0, DG(0) = 0, rank[G(0), DF (0)G(0)] = 2.
Then, for any T > 0 sufficiently small,

• R T is strictly convex;

• every x ∈ R T is optimal (i.e., there exists a time optimal trajectory passing through x; this requires extending the optimal control/adjoint vector after x);

• the epigraph of T has positive reach.

This result is obtained by linearization. We show that the switching function of the nonlinear problem is essentially the same as the switching function of the linearized (at the origin) problem.

The obstruction for obtaining a result in higher dimension is the approximation of the optimal trajectory with a suitable trajectory of the linearized system: we need a power n with respect to the distance between two final points, but we are able to obtain only a power 2. So n = 2 is OK.

Trying to obtain a similar result in higher dimension is the first open problem I would like to mention.

The second open problem is studying cases where both type of singularities may occur (upwards/downwards corners). This happens, e.g., for larger times, i.e., not too close to the origin.

This is wide open, both from the viewpoint of nonsmooth analysis and of control theory.

K

  Of course, K is convex if and only if r = ∞. Inward corners are forbidden.Well known facts:-if f : R n → R is semiconvex/semiconcave, then its epigraph/hypograph has positive reach; the epigraph of f (x) = |x| has positive reach, but f is not locally Lipschitz; -K has positive reach iff the metric projection onto K is a singleton in a neighborhood of K.In general, (a) and (b) are different. However (Nour-Stern-Takche, JCA (2009)) if K is epi-Lipschitz (= the normal cone is pointed), then (a) ⇔ (b).


Astos Solutions

FACTS AND FIGURES

Typical Optimal Control Applications

These are the typical applications for optimal control in the space segment at Astos Solutions:

• Performance analysis

Challenges of Space Applications

Applying non-linear optimization to space applications is often accompanied by one or more of the following challenges:

•large scale problems (>100,000 variables)

•several local minima

•non-smooth model data

•noise

•complex and/or "black box" models

•users are engineers and not mathematicians

DLR "Blackbox Solver" Research Activity

•Project Goals:

-Reduction of user interaction -Reduction of required user expertise -Increase of solver robustness •Automatic mesh refinement and generation

Link to SADCO?

Foreseen activities in cooperation with Uni. Bremen and SADCO fellow Sonja Rauski:

• Parametric sensitivity analysis based on KKT-matrix

• Limited memory BFGS (sparse BFGS for large scale problems)

Wrap-Up

•A small set of mathematical approaches (transcription method, NLP solver) is applied to a wide range of optimization problems and applications

•A robust solution is more desired than the real optimal

•Sensitivity analysis is required to get confidence on the robustness of the solution.

Industrial Workshop

Industrial



   Mission analysis  Safety analysis  GNC analysis Astos Solutions History Start of GESOP/ASTOS (former ALTOS) development at MBB (now Astrium ST) and DLR Oberpfaffenhofen. Continuation at new Institute of Flight Mechanics and Flight Control (IFR) at University of Stuttgart as prime under the lead of Prof. Klaus Well. Beginning of commercialization (1st customer Fiat Avio => VEGA launcher) Foundation of Astos Solutions GmbH Registered as SME Located in STEP (STuttgarter Engineering Park), Germany Enlargement of office to double size including laboratory University of Stuttgart, Faculty of Aerospace and Geodesy • Training courses in trajectory optimization with ASTOS in parallel to the lectures at iFR • Supervision of students in their master thesis work  Worldwide cooperation • Lectures and student workshops organized at several universities, especially in USA • Software used by app. 30 universities worldwide for master and PhD theses • Transcription methods: direct multiple shooting, direct collocation (also hybrid) with linear, constant or B-Spline control discretization • Several NLP solvers: SNOPT, WORHP, SPRNLP (SOCS), SLLSQP and global methods (Particle Swarm, genetic algorithms) • Jacobian approximated by finite differences, Hessian by BFGS updates or also by finite differences • Various propagation methods (RKF45, RKF78, RKN11, RKR15, ODEX2, SGP4) • Built-in batch processing tool, e.g. for Monte Carlo simulations • More than 100 predefined constraints and cost functions • Wide range of vehicle and environment models (no coding required GESOP/ASTOS Customers

•••

  Improved finite differences by means of adaptive variable perturbation Challenging because of: • Long mission duration • Local minima in case of interplanetary mission • Thrust vector control • Throttable engines and/or thrust restricted by power budget • Other mission constraints to be considered (safety aspects) Complex systems and subsystems • Several disciplines (propulsion, aerodynamics, TPS, structure, dynamics) • Various MDO techniques: AAO, IDF, BLISS, CO • Difficulties: computational time, convergence SQP is applied main task is to find best MDO strategy Multi-Mission Optimization and Design • Trajectory and stage optimization of a launcher family with different Model uncertainties -> in reality model parameters might be different from the ones assumed in the optimization Not an optimal but a robust solution is required!• Local sensitivity analysis based on KKT-matrix and/or• Trust region analysis in the regime of 1 sigma -> Monte Carlo• Sensitivity analysis with respect to optimizable variables and fixed parameters (e.g. assumed Isp of the engines) is required

  SADCO Workshop at Astos Solutions •Tentative date: 2-3 February 2012 •Industrial applications •"Learn about the engineer's perspective" •Hands-on software trainings •In direct neighbourhood of the University of Stuttgart •Global players with optimization demands are located in Stuttgart, e.g.

Optimal Control and Sensitivity Analysis for Space Applications An Aerospace Mission

	ESA projects with ASTOS
	Launch Vehicles
	Aero-Space Ariane 5 MLV Model Definition • Environment -Planet VEGA -Atmosphere VEGA 1 st flight -Wind -Solar System Electrical VEGA CTV • Vehicle Components Mars Ascent Vehicle • Aerodynamic Configurations CTV 2 • Propulsion Systems	Universities Europe Phase Configuration Berlin Stuttgart München Bremen Athens Greifswald FH Aachen Naples Cranfield Glasgow Madrid ETH Zürich Dresden Zaragoza Pisa • Initial State and Epoch • Multi-Phase Definition -Dynamic System -Aerodynamic Configuration -Active Propulsions -Jettisoned Components -Branching -Attitude Controls	North America California Stanford Seattle MIT Illinois Austin, Texas Carleton, Qu Edmonton, Al Toronto Minneapolis Maryland Iowa State UCLA Los Angeles Purdue Cincinnati Ryerson South America Pennsylvania State
	Socrates RLV Demonstrator Mission Definition Heavy Lift Launch Vehicle • Cost Function IXV launch vehicles -Maximum Payload		Cordoba, Ar Minas Gerais, Br Asia Yonsei, Seoul, Kr Nanjing
	Crew Exploration Vehicle • Constraints -Boundary Constraints Automotive -Path Constraints	Yogyakarta Australia Sydney Canberra
			Adelaide

© 2011 Astos Solutions GmbH SADCO Kick-Off Meeting

Aerospace Trajectory Optimization Software© 2011 Astos Solutions GmbH SADCO Kick-Off Meeting

SADCO Kick-Off Meeting © 2011 Astos Solutions GmbH 11

© 2011 Astos Solutions GmbH SADCO Kick-Off Meeting

Challenging Space Applications© 2011 Astos Solutions GmbH SADCO Kick-Off Meeting

• Daimler • Bosch • Behr • Thales ATM Chance for further networking © 2011 Astos Solutions GmbH SADCO Kick-Off Meeting

projects with ASTOS Re-entry, Exploration, Science X38/CRV Sphynx ACRV ARD JEP Beagle-2 &


Samaneh Chagheri
email: samaneh.chagheri@insa-lyon.fr

Catherine Roussey
email: catherine.roussey@liris.cnrs.fr

Sylvie Calabretto
email: sylvie.calabretto@insa-lyon.fr

Cyril Dumoulin
email: cyril.dumoulin@continew.fr

XML Document Classification using SVM

This paper describes a representation for XML documents in order to classify them. Document classification is based on document representation techniques. How relevant the representation phase is, the more relevant the classification will be. We propose a representation model that exploits both the structure and the content of document. Our approach is based on vector space model: a document is represented by a vector of weighted features. Each feature is a couple of (tag, term). We have expanded tf*idf to calculate feature's weight according to term's structural level in the document. SVM has been used as learning algorithm. Experimentation on Reuters collection shows that our proposition improves classification performance compared to the standard classification model based on term vector.

Introduction

The continuous growth in XML documents has caused different efforts in developing classification systems based on document structure. Document representation has to be done before the classification process. Vector space model is one of the most used methods for document representation, in which each document is represented as an N dimension vector of weighted features. N is the number of features in the document collection. The representation models can be divided into three groups: first, the models which do not consider the structure of document focus on representing the document content as a bag of words to classify them. Second are the models which take into account only structure of a document in order to classify them, and third are the models which try to consider both structure and text of XML documents in representation.

Mostly the classification systems use vector space model for document representation, the difference is based on selecting vector features and their weight computation. In [START_REF] Doucet | Naive Clustering of a Large XML Document Collection[END_REF] each vector feature can be a word or a tag of XML document. The tf*ief (Term Frequency * Inverse Element Frequency) is used for calculating the weight of words or tags in documents. In [START_REF] Vercoustre | Classification de documents XML à partir d'une représentation linéaire des arbres de ces documents[END_REF] a feature can be a path of the XML tree or a path contacting a word. The term weight is based on tf*idf. This allows taking into account either the structure itself or the structure and content of these documents. In [START_REF] Wisniewski | Classification automatique de documents structurés. Application au corpus d'arbres étiquetés de type XML[END_REF] RNTI -X -they are interested to only use the document structure for classification without considering the text. They use Bayesien model to generate the possible DTDs of a documents collection. A class represents a DTD. Ghosh [START_REF] Saptarshi Ghosh | Combining Content and Structure Similarity for XML Document[END_REF] has proposed a composite kernel for fusion of content and structure information. The paths from root to leaves are used as indexing elements in structure kernel weighted by tf*idf. The content and structure similarities are measured individually. A linear combination of these kernels is used finally for a content-structure classification by SVM.

In this article, we propose a method which is an extension of the vector model of Salton [START_REF] Salton | Search and retrieval experiments in real-time information retrieval[END_REF] adjusting the calculation of the tf*idf by considering the structural element instead of whole document. This representation allows a classification based on content and document structure like the work of Vercoustre, our vector features are different and for calculating their weight we have expanded tf*idf in structure level.

The rest of the article is organized as follows. We present our proposition in section 2 on using structure and content on document classification. Experimentation results are written in section 3. Section 4 presents the conclusion and further works.

General Overview of our Approach

In this article we have proposed a combination of the content and structure of XML document in the vector model for document representation. In our vector each feature is a couple of (tag, term). Tag corresponds to a structural element in XML document. XML document is represented as a tree. We apply a supervised classification on document collection using Support Vector Machine (SVM). SMV light [START_REF] Joachims | Making large-Scale SVM Learning Practical[END_REF] as an implementation of Support Vector Machine has been used for supervised classification.

Logical structure modeling

We consider the XML document as a tree in which the nodes are tagged by structural labels like title, chapter, etc. The arcs of this tree represent the inclusion relation between nodes, and the leaf nodes contain the document text. The depths of nodes in document tree are important. Thus we consider that two nodes with the same label localized at different depths are two different structural elements. The structural element represents a node type.

We modify document tree organization by aggregating the nodes with the same label and localized at the same depth. For example, all paragraphs in a section are aggregated to a single node "paragraph" which contains all terms of these paragraphs. We take into account only the leaf nodes which contain text for creating document vector. We assume that all documents have a homogeneous structure. There is no node with the same label and different depth. A label becomes an adequate identifier of the structural element.

Content and structure vector

After aggregating document nodes, we extract the terms in each node. For representing document content a series of linguistic analysis has been done. First the stop words are filtered. Secondly the lemmas of words are extracted using TreeTagger to replace the words. Also, we just keep the words in categories noun and verb which seem more representative. The result of such analysis are called term. Therefore, each feature is made by combining the RNTI -X -node label and the term, for example (title: technical) or (p: cleaning). Such feature represents the document structure and content.

For calculating the weight of features we use an extension of tf*ief in the document structure level instead of document level and we add the importance of the structural element inside the document. We assume that how deeper a node is in the document tree, less it will be important. So, the weight of feature will be as shown below:

ܹ ,,ௗ ൌ ܨܶ ,,ௗ כ ܨܧܦܫ ௗ, כ ܦܧܫ
i, e, and d represent respectively a term, a structural element type like a paragraph and a document in the collection.

The Term Frequency TF i,e,d is the number of occurrences of the term i in structural element type e inside the document d, normalized by the number of all terms in this node. The Inverse Document Element Frequency IDEF d,e is calculated by ݈݃ ௗ ,

with D e as the number of documents in the collection having a node of type e, and d e,i as the number of documents having node e containing the term i.

The Inverse Element Depth IED e represents the importance of a structural element e in the collection. It is calculated as ݈݃ ାଵ , with L d as the average depth of documents tree in the collection, and l d,e as the average depth of the node of type e in the collection.

After constructing documents vector, we apply SVM as classification algorithms for learning and classifying our collection.

Experimentation

Experiments were performed on the Reuters Corpus Volume 1 (RCV1) which includes over 800,000 English language news stories. The stories are formatted using a consistent XML schema. In this collection we use only header and paragraph of stories which are all in the same depth in all documents. Each story is annotated for topic, region and industry sector and they are multiclass. We have ignored unclassified documents and for mono classification we have selected the first class of topic category of each story. We have made a learning collection of 400 documents with 200 positive and 200 negative examples for a topic class called "GCAT" and a test collection with 400 documents. We made two experimentations using SVM. The first one called "content and structure" is an implementation of our proposition. The second one called "content only" uses a vector of simple terms weighted by standard tf*idf.

Conclusion and Perspectives

In this article we have proposed a model for XML document representation in order to classify them. We proposed a combination of structure and content in document representation by the vector model. Our features are couples of (tag: "term"), all weighted by an extension of tf*idf taking into account the terms position in the documents tree.

We have done our experimentation on Reuters XML news collection which is a particular collection with homogenous documents. In future works we are going to improve our proposition in order to do the test on a heterogeneous corpus like INEX evaluation campaign collection which contains a huge number of documents with heterogeneous structures.

  The results of the classifications are shown in table 1. The results demonstrate that including structure improves the classification accuracy.

		TAB1. Precision/Recall results on Reuter corpus
	Vector features	Precision	Recall	F-measure
	Content & structure	0.92	0.96	0.94
	Content only	0.93	0.83	0.88
	RNTI -X -


Alexandre Denis
email: alexandre.denis@inria.fr

A High Performance Superpipeline Protocol for InfiniBand

InfiniBand high performance networks require that the buffers used for sending or receiving data are registered. Since memory registration is an expensive operation, some communication libraries use caching (rcache) to amortize its cost, and copy data into pre-registered buffers for small messages. In this paper, we present a software protocol for InfiniBand that always uses a memory copy, and amortizes the cost of this copy with a superpipeline to overlap the memory copy and the RDMA. We propose a performance model of our protocol to study its behavior and optimize its parameters. We have implemented our protocol in the NewMadeleine communication library. The results of MPI benchmarks show a significant improvement in cache-unfriendly applications that do not reuse the same memory blocks all over the time, without degradation for cache-friendly applications.

Introduction

InfiniBand networks are nowadays the leading technology for high performance networks in clusters. Parallel applications usually exploit this network through an Mpi library that makes their usage seamless for the end-user. Under the hood the Mpi implementations access the InfiniBand network cards through an Api called verbs. Unlike Api used to program other networking technologies, the verbs Api is very low-level. It means that a lot of things have to be done by hand by the Mpi library programmer; on another hand, the programmer has a lot of control on how to exploit the network interface.

Network transfers are based on RDMA and are executed by the DMA engine on the network card. The card sees the system from the PCIe bus, thus works with physical addresses. The application, Mpi library, and InfiniBand software stack run in user space, with no system call involved thanks to OS bypass. Since they run in user space, they use virtual addresses. Thus, when sending data from user space through InfiniBand, translation has to be done from virtual address space to physical address space. The network card can do the translation if it has been told previously the mapping from virtual to physical space. This process is called memory registration and in InfiniBand it has to be performed explicitly by the user. Actually, the memory registration is comprised of both the communication of the translation table to the network card, and memory pinning to prevent swapping. All memory involved in sending and receiving operations in InfiniBand must be registered. Two approaches are possible to satisfy this constraint: register memory blocks on the fly; register a buffer at application startup, then copy data into this pre-registered buffer. Memory registration has a significant cost [START_REF] Mietke | Analysis of the memory registration process in the mellanox infiniband software stack[END_REF] and both approaches have an impact on the overall network performance.

In this paper, we present a software protocol for InfiniBand that copies data through a pre-registered buffer and amortizes the cost of the memory copy by using a superpipeline to overlap copy and RDMA transfer. We propose a performance model of our protocol to study its behavior and optimize its parameters.

The remainder of this paper is organized as follows. In Section 2 we analyze the performance of memory copy and registration. In Section 3 we present an analysis of a pipeline for memory copy. In Section 4, we describe our superpipeline protocol. Section 5 gives benchmarks results. Section 6 compares our work to related works. Section 7 concludes our paper.

Performance analysis

In this section, we analyze the performance of memory registration, memory copy, and network transfer, and we propose a performance model.

We run our tests on multiple InfiniBand clusters. Cluster graphene features ConnectX DDR (MT26418) cards on quad-core nodes equiped with Intel Xeon X3440. Cluster infini has ConnectX2 QDR (MT26428) cards on quad Intel Xeon X5570. To visualize closely what happens, all our graphs use a 5 % increment for message size (i.e. powers of 1.05), not only powers of 2 that hide a lot of details. to register a block of memory on several InfiniBand clusters. For example, the results obtained on cluster graphene are depicted in Figure 1, represented as a bandwidth. Let L the length of a given message, we can model the registration time in the form T reg (L) = λ reg + L Breg with λ reg the latency of memory registration, and B reg its bandwidth. On this cluster, we have measured λ reg = 68 µs. and B reg = 20 GB/s (actually, 200 ns per 4 KB page). We observe the same order of magnitudes on other DDR and QDR InfiniBand boards.

Performance of registration. Memory registration in

The cost of registration may have a huge impact on actual communication performance. A naive protocol to send a block of data would consist in dynamically registering the memory region, send the data on the network, then deregister the memory region; the receiver has to perform registration/deregistration too. The performance of such a protocol is depicted in Figure 2 for cluster graphene. We observe that the overhead introduced by memory registration lowers the bandwidth by as much as 60 % for packets of roughly 64 KB, and is far from negligible even for larger sizes of messages, with an apparent bandwidth converging asymptotically to

1 1 B net + 1

Breg

, which is 91 % of the network bandwidth on our cluster.

Performance of memory copy. Performance of a raw memcpy is depicted in Figure 1. The apparent bandwidth decreases when the size of data increases, as a result of cache effects. We can roughly model its behavior with four different bandwidth figures for L1, L2 and L3 caches, and memory. It would require to know actual cache policy and associativity to get a more precise model.

A naive copy-based protocol would copy data on the sender side into a registered memory zone, send the data, then copy the data from the registered memory zone into its final destination in the receiver side. Since memory copies are fast for small messages, this copy-based protocol is usually used for small messages sent eagerly. Larger messages are usually [START_REF] Liu | Design and implementation of mpich2 over infiniband with rdma support[END_REF] sent with a rendezvous protocol to avoid copies that would lower the available bandwidth.

The apparent bandwidth of the naive copy-based protocol is depicted in Figure 2, converging asymptotically to

1 1 B net + 2

Bcopy

, which is 57 % of the network bandwidth on our cluster.

Real behavior of rcache. To amortize the cost of memory registration, it has been proposed a pin-down cache [START_REF] Tezuka | Pin-down cache: a virtual memory management technique for zero-copy communication[END_REF], or as commonly called today, a registration cache (in short: rcache). It means that the sender does not unregister the memory zone after a message is sent, in case the same zone is sent again. However it requires a lot of care to be correct [START_REF] Ohio | Memory registration caching correctness[END_REF]. One must use malloc hooks, libc symbol interception through LD PRELOAD or kernel patches, to invalidate the cache (unregister memory) when memory is deallocated. These mechanisms are not quite portable and may break in subtle ways when interacting with various versions of libc, Fortran or OpenMP runtimes, or any runtime that supplies its own memory allocator.

It must be noted that rcache does not increase performance by itself. The first send exhibits the same performance as the naive registration-based protocol. Only the subsequent sends of the same memory zone will be faster, at the nominal speed of the network. The real world performance of rcache depends on the buffer reuse scheme of the application, and may obviously vary from one application to another. For example in NAS Parallel Benchmarks, SP and CG have 99 % cache hits, IS has less than 5 % cache hits, and LU sends mostly small messages not concerned by rcache. Our goal is to improve performance of IS without degrading performance of other benchmarks.

Pipelining memory copy

In this section, we study an InfiniBand software protocol which manages memory registration by copying data into a pre-registered buffer instead of dynamically registering data in place.

Since copy and RDMA may be overlapped, a pipeline may be used to amortize the cost of the memory copy. Both operations share the same memory bus, but experiments show that copies have a negligible impact on an overlapped RDMA -memory bandwidth is high these days -, while the copy is slowed down by no more than the bandwidth used by the network. As depicted in Figure 3, each message is divided into chunks of a given size. Then on the sender side, we overlap the RDMA transfer of one chunk with the memory copy of the next chunk. Since we use RDMA write, on the receiver side nothing has to be done to make the overlapping happen.

Cost analysis. Let L be the message length, and C the chunk size. For convenience, we assume L is a multiple of C. To model the network with multiple chunks and overlap, we use a model close to LogP [START_REF] Culler | Logp: towards a realistic model of parallel computation[END_REF] with the following notations. Let λ net be the network latency (the L of LogP) and B net the network bandwidth, then we have T net (L) = λ net + L/B net as end-to-end transfer time for a raw RDMA write, assuming data is already registered. Let g be the gap between messages, then we have

T net (L 1 , L 2 ) = λ net + L1
Bnet + g + L2 Bnet as transfer time for two packets of length L 1 and L 2 . Let o be the overhead for sending messages, namely the CPU time needed to initiate the RDMA operation, that will not be available for overlapping.

In Section 2, we have shown that memcpy bandwidth depends on message length. Let B copy (L) be the copy bandwidth for a message of length L. We must notice that since the bandwidth depends on cache effects, the length to take into account is the whole data set, namely L, not C. We assume λ copy = 0. Then we have T copy (L) = L/B copy (L) as time to copy data of length L.

Then the time for the full pipelined transfer is comprised of: copy of the first chunk:

C Bcopy(L) ; steady state with L C chunks copied and sent: L C × g + C Bnet ; the network latency: λ net ; copy of the last chunk: C Bcopy(L) . Therefore the total time of pipelined transfer is:

T pipeline (L, C) = 2 × C B copy (L) + L C × g + λ net + L B net (1)
Compared to a raw RDMA write, the overhead for the pipeline is 2×C Bcopy(L) + L C ×g. It is comprised of the copy of the first chunk on the sender side, the copy of the last chunk on the receiver side, and the gaps.

Optimal pipeline. We can find the optimal value for C the chunk size. When we draw a graph of C → T pipeline (L, C) for any fixed L and realistic values of B copy and g, we can see this function admits a minimum. If we assume C to be real instead of integer to make the function differentiable, the derivative with respect to C for a given message length L is:

T ′ pipeline (C) = 2 B copy (L) - L C 2 × g (2)
Let C opt be the the optimal chunk size for a given message length L. It corresponds to the zero of the derivative. We solve the equation and get: Using our performance models for network and copy, we estimate the performance of the pipeline with optimal chunk size, depicted in Figure 4. The performance increase compared to naive protocols is huge, but bandwidth is still lower than raw InfiniBand RDMA and may still be improved. We can see that for messages smaller than 16 KB, the naive copy-based protocol is faster than the optimal pipeline; when computing the optimal chunk size for these messages, we get an optimal with less than one chunk per message, which is wrong. Our hypothesis of C being real instead of integer works only for messages large enough.

C opt (L) = L × g × B copy (L) 2 (3)

Optimizations beyond pipeline: superpipeline

In this Section, we present various mechanisms to improve the performance of our protocol, beyond the vanilla pipeline with optimal chunk size presented in the previous Section.

Super-pipeline to lower the number of gaps. Memory copy has a higher bandwidth than RDMA write over the network, as measured in Section 2. Therefore, when pipelining, for each chunk memcpy finishes earlier than the RDMA write for the previous chunk. Thus we propose to increase the chunk size from chunk to chunk while the pipeline is running. We call this mechanism a superpipeline, like superpipelines in CPU architecture. This superpipeline mechanism is depicted in Figure 5. It is expected to have a lower number of gaps than the plain pipeline, thus reducing the overhead of the protocol. We must define a suitable progression rule for the chunk size. Let C i be the chunk size at step i. We may compute the sequence that enables a full overlap of memcpy and RDMA; such a sequence will have the fewest gaps. It is defined as:

C i+1 B copy (L) = C i B net + g -o (4)
in other words the time to copy chunk C i+1 may be as high as the time to send C i on the network, including g the gap between packets, but excluding the nonoverlapable overhead o, with o and g as defined in Section 3. Since o and g are of the same order of magnitude, go is at most in the order of 100 ns and may be neglected compared to the other terms when C i is several kilobytes. Then Equation 4 simplifies as

C i+1 = C i × Bcopy(L)
Bnet . Therefore, the general term of the sequence is:

C i = C 0 × q i with q = B copy (L) B net (5)
To compute the protocol overhead, we need to compute the number of gaps. Let n be the number of gaps for a given message of length L. Then L, as the sum of all chunks, is a finite geometric series:

L = n-1 i=0 C i = C 0 × n-1 i=0 q i = C 0 × 1 -q n 1 -q (6)
We then solve this equation to get n the number of gaps:

n = log q 1 + L C 0 (q -1) (7)
Therefore the total transfer time of our superpipeline protocol is:

T superpipeline (L) = C 0 + C n B copy (L) + n × g + λ net + L B net (8)
It is very similar to the cost of plain pipeline given in Equation 1, except that the number of gaps is O(L) for fixed-chunk pipeline, O( √ L) for pipeline with the optimal chunk size C opt as defined by Equation 3, and is lowered to O(log(L)) for superpipeline.

Sub-blocking to lower last chunk copy overhead. The transfer time for the superpipeline given in Equation 8 includes

Cn Bcopy(L) the time needed to copy the last chunk at the receiver side. Given the general term of the sequence given in Equation 5, C n is expected to be quite large.

To amortize the cost of the copy at the receiver side, we propose a sub-blocking mechanism -namely, a pipeline in the pipeline -to overlap the RDMA and the memcpy of the same chunk. Among the possible strategies [START_REF] Gupta | Efficient barrier using remote memory operations on via-based clusters[END_REF] of the receiver side to detect the arrival of RDMA data, we chose to poll a flag at a known memory location. The receiver sets it to zero; the sender writes a 1 through RDMA.

Our sub-blocking mechanism consists in dividing each chunk into blocks of a given size b. Every block is comprised of data payload and a flag indicating the presence of data. All the blocks that form a chunk are sent through a single RDMA write. The receiver is then able to detect and consume blocks as they arrive, only one block behind the one being written by the NIC.

With such a method, the cost of the copy at the receiver side is at most the copy of a block b Bcopy(L) . This methods adds flags in every blocks, which increases the size of packets sent on the network and must be taken into account. However, if we take for example b = 4 KB (page size and multiple of MTU) and a flag on a 64-bit word (to avoid atomicity issues depending on endianness), then the overhead is less than 0.2 %.

Overlap rendezvous to lower first chunk copy overhead. The overhead of our superpipeline protocol includes the cost of the memory copy for the first chunk C 0 . We propose to overlap this copy with the rendezvous to lower its impact on performance.

We have shown in Section 3 that the optimal number of chunks is 1 for small messages. The fastest option to send small messages is the naive copy-based protocol. It means that we will use pipeline (or superpipeline) protocols only for large messages, that are sent using a rendezvous mechanism to ensure that data is received in place. It must be noted that, although our protocol involves a copy, the rendezvous is still relevant because our protocol copies data on the fly and needs to know where to store data.

The cost of a rendezvous is twice the latency, namely 2 × λ net . We propose that the sender copies C 0 the first chunk of the message while the rendezvous round-trip takes place. If C0 Bcopy < 2 × λ net , then the copy of C 0 is free. To maximize overlap in the common case, we chose to use: C 0 = B copy × 2λ net . With common contemporary hardware, we get values from 8 KB to 16 KB for C 0 .

Pipeline folding using N-buffering. In our previous descriptions of our superpipeline, we have assumed that the preregistered buffer is as large as the message. However, registered memory is a finite resource and cannot be arbitrarily large. Therefore we fold our superpipeline to fit statically-allocated buffers. Since at any given time, one buffer is copied while another buffer is sent (or received), we can then make our superpipeline a double-buffering algorithm. A flow control mechanism is needed to make sender and receiver synchronize their buffer swaps. Since such synchronization through network has a significant latency, we loosen the coupling between the sender and the receiver with triple-buffering. Before it may send chunk C i , the sender does not have to wait for the C i-1 acknowledgment -that may arrive late because of network latency -but for the C i-2 acknowledgement. Moreover, folding the superpipeline in a smaller workspace than the full message length improves cache reuse, although the precise impact is hard to model and to predict.

With all the heuristics and optimizations applied, the total transfer time of our superpipeline protocol is:

T superpipeline (L) = b B copy (L) + g × log q 1 + L C 0 (q -1) + λ net + L B net (9)
The overhead for to copy of the last sub-block b is low, and the number of gaps is O(log(L)).

Discussion. The plain pipeline is easy to model and we have determined analytically its optimal chunk size, as we did in Section 3. However, the performance of superpipeline depends on a sequence, not a single value, which makes it difficult to solve analytically. Optimization depends on a lot of parameters, that's why we used heuristics (maximize overlap) to determine q and C 0 . Our model is not so precise and some behaviors are hard to predict (cache effects depend on cache policy, associativity, data alignment). The theoretical optimal is thus not necessarily optimal once implemented. However when we trace C 0 → T superpipeline (L, C 0 ) for a given L, variations are small around the optimal. We conclude that not-so-precise tuning works well with superpipeline, which is confirmed by experience. Hardwired C 0 =12 KB and q = 1.5 gives results almost as good as optimal values.

Benchmarks

In this Section, we present benchmarks of our superpipeline protocol and compare it against other protocols and implementations.

Raw protocol benchmark. We have implemented our superpipeline protocol in a test program to evaluate its behavior regardless of any other implementation artefact. The results of a ping-pong bandwidth test on clusters graphene and infini are depicted in Figure 6. We observe the superpipeline is much faster than naive registration and memcpy-based protocols, and is very close to the raw RDMA performance. The overhead compared to raw RDMA is 15 % for 16 KB messages, and less than 5 % for messages larger than 64 KB. However this test program does not implement rendezvous, thus cannot overlap C 0 copy and rendezvous; real-life overhead is then expected to be lower. MPI micro-benchmarks. We have then implemented our superpipeline protocol as a driver in our NewMadeleine has an rcache method for InfiniBand, and run Mpi benchmarks using its Mad-Mpi [START_REF] Trahay | Improving reactivity and communication overlap in mpi using a generic i/o manager[END_REF] interface. NewMadeleine has a 32 KB rendezvous threshold, and uses plain copy for small messages (no pipeline, no rcache). We compare Mad-Mpi against OpenMPI-1.4.3 and MVAPICH2-1.6rc2. The results of a MPI ping-pong bandwidth test on cluster graphene are depicted in Figure 7. The benchmarks performs 100 round-trips for each message size; we draw separate graphs for the first and for the best round-trip. We observe the superpipeline gets roughly the same performance as Mad-Mpi rcache best time, very similar to OpenMPI and MVAPICH2 best time. However, when we compare the performance of the first round-trip, we observe that Mad-Mpi rcache, OpenMPI and MVAPICH2 all get low performance because of registration, whereas Mad-Mpi superpipeline is unaffected. The superpipeline gets its best performance already at the first send; the others, relying on rcache, get poor performance on first send. MPI NAS Parallel Benchmarks. We have run some benchmarks from the NAS Parallel Benchmarks 3.3.1 on cluster graphene. On tests sp.B.8, lu.B.8 and cg.C.8, Mad-Mpi superpipeline and rcache get the same performance, 3 % slower than OpenMPI and MVAPICH2, explained by the fact that Mad-Mpi has a slightly higher latency. However, on is.C.8 Mad-Mpi superpipeline is 9 % faster than Mad-Mpi rcache (respectively 3.05 s and 3.32 s), but slightly slower than MVAPICH2 (3.01 s) and OpenMPI (2.92 s).

It means that superpipeline actually improves performance over rcache on IS which is cache-unfriendly, but some work has to be done in Mad-Mpi to improve latency for small message to get overall better performance.

Related works

People working on Mpi implementations and other communication libraries have already studied InfiniBand memory registration and proposed solutions to amortize its cost. Memory registration performance has been analyzed [START_REF] Mietke | Analysis of the memory registration process in the mellanox infiniband software stack[END_REF] and communication performance modeled [START_REF] Hoefler | Logfp -a model for small messages in infiniband[END_REF] without proposing solution to improve performance. Various caching strategies [START_REF] Tezuka | Pin-down cache: a virtual memory management technique for zero-copy communication[END_REF][START_REF] Bell | A new dma registration strategy for pinning-based high performance networks[END_REF][START_REF] Ohio | Memory registration caching correctness[END_REF] have been proposed, as well as protocols to overlap rendezvous and registration [START_REF] Ou | An efficient design for fast memory registration in rdma[END_REF] in case of cache miss; however, all these solutions exhibits the pitfalls of cache-based strategies.

It has been proposed in OpenMPI [START_REF] Woodall | High performance rdma protocols in hpc[END_REF] to pipeline registration; our model shows that pipelining copies gives better performance than pipelining registration. For the InfiniBand device for MPICH2 [START_REF] Liu | Design and implementation of mpich2 over infiniband with rdma support[END_REF] and the BCopy mode of SDP [START_REF] Goldenberg | Zero copy sockets direct protocol over infiniband -preliminary implementation and performance analysis[END_REF], it has been investigated to use a copy pipeline with fixed-size chunks. Performance was not convincing, because at that time memory bandwidth was not significantly higher than network bandwidth; our proposal goes further with a superpipeline rather than a flat pipeline, and our theoretical study shows that it works because B copy > B net , which has become the common case nowadays with contemporary CPUs and their integrated memory controlers.

Conclusion and future works

Memory registration has a major impact on performance for InfiniBand networks. In this paper, we have proposed performance models for InfiniBand network, copies, and registration, and used them to analyze and optimize the performance of a protocol that uses pipelined copy to bring data into registered memory. We have proposed an alternative called superpipeline that reduces the number of gaps, and some optimization mechanisms to reduce the cost of the first and last chunk copy. We have implemented and benchmarked our superpipeline protocol, and observed that it gets roughly the same performance as rcache-based protocol on cache-friendly communication patterns, and better performance on cache-unfriendly patterns.

As a future work, we will study adaptive strategies to automatically tune the protocol parameters to the machine it is running, and to monitor rcache misses/hits to dynamically choose between strategies depending on observed application behavior.

Fig. 1 .

 1 Fig. 1. Registration and memory copy performance comparison on cluster graphene.

Fig. 2 .

 2 Fig. 2. Impact of registration and memcpy on communication performance on cluster graphene.

Fig. 3 .

 3 Fig.3. Pipeline for memory copy: sender copies chunk 3 while sending chunk 4; receiver copies chunk 2 while receiving chunk 3.

Fig. 4 .Fig. 5 .

 45 Fig.4. Bandwidth model for pipeline using parameters from cluster graphene.

Fig. 6 .Fig. 7 .

 67 Fig.6. Raw superpipeline protocol performance on cluster graphene (left) and infini (right).

Acknowledgements. This work was supported in part by the ANR-JST project FP3C and the ANR project COOP. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).