Jérémie Bourdon
email: jeremie.bourdon@univ-nantes.fr

Mireille Régnier
email: mireille.regnier@inria.fr

Large deviation properties for patterns

Keywords: Pattern matching, statistics, Large deviation

Deciding whether a given pattern is overrepresented or under-represented according to a given background model is a key question in computational biology. Such a decision is usually made by computing some p-values reflecting the "exceptionality" of a pattern in a given sequence or set of sequences. In the simplest cases (short and simple patterns, simple background model, small number of sequences), an exact p-value can be computed with a tractable complexity. The realistic cases are in general too complicated to get such an exact p-value. Approximations are thus proposed (Gaussian, Poisson, Large deviation approximations). These approximations are applicable under some conditions: Gaussian approximations are valid in the central domain while Poisson and Large deviations approximations are valid for rare events. In the present paper, we prove a large deviation approximation to the double strands counting problem that refers to a counting of a given pattern in a set of sequences that arise from both strands of the genome. Here dependencies between a sequence and its complement plays a fundamental role. General combinatorial properties of the pattern allow to deal with such a dependency. A large deviation result is also provided for a set of small sequences.

Introduction

Counting random words [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] and calculating probabilities is an old and extensively studied problem in theoretical computer science for various applications in bioinformatics including finding motifs [TLB + 05, NBM + 11] and calculating p-values [START_REF] Touzet | Efficient and accurate p-value computation for position weight matrices[END_REF]. Rare or overrepresented words are commonly assumed to be the hint in the genomes of some biological functions.

An exact derivation of the distribution of pattern occurrences is theoretically solved [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] but its computation is expensive, not to mention accuracy and numerical issues. Classical approximations of the distribution (Gaussian, Poisson) are known not to be applicable [START_REF] Marino-Ramirez | Statistical analysis of over-represented words in human promoter sequences[END_REF]. Indeed, distribution convergence are valid in the central domain, while rare events are studied in the tail domain. Simulations on biological data are presented in [START_REF] Marino-Ramirez | Statistical analysis of over-represented words in human promoter sequences[END_REF]. This point is extensively discussed in [START_REF] Régnier | Comparison of statistical significance criteria[END_REF].

Large deviation properties are the properties in the tail domain. One typical result in this case lies in mathematically proving a so-called Large Deviation principle that consists in providing a big-O bound on the tail distribution. In this paper, we prove that combinatorial properties of words allow to go further by providing an explicit and tractable formula for the tail distribution. A survey can be found in [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF] in the context of word occurrences. Still, very few results are known. One may also cite [START_REF] Régnier | Rare events and conditional events on random strings[END_REF] and [START_REF] Nuel | Ld-spatt: Large deviations statistics for patterns on markov chains[END_REF]. The latter compares several methods for proving the exceptionality of a single pattern including Gaussian approximation, compound Poisson approximation and large deviation approximation.

Recently, new sequencing methods appear requiring to push away our knowledge on pattern occurrences statistics in order to obtain more precise results while keeping the complexity of the computations under control. Our goal is to obtain some probabilistic results adapted to datasets containing a huge number of sequences (typically reads from a high throughput sequencing) possibly coming from a pair end sequencing. In this case, patterns and their complementaries have to be considered at the same time (in the sequel, this case is referred as the "double strands" counting problem). The main problem here is to take properly into account the dependencies between a DNA sequence and its complement.

We consider here two cases. Large sequences are addressed in Section 3 when one counts occurrences of words from a finite set H, under a Bernoulli model. Large deviation results were obtained for a single word in [START_REF] Régnier | Rare events and conditional events on random strings[END_REF]. The case where H admits two overlap classes [START_REF] Regnier | A Word Counting Graph[END_REF] is solved here. This case is fundamental, as it allows to address double strand counting. Short sequences are addressed in Section 4. Large deviation results have been known for long for random independent trials in the case of identical distributions [START_REF] Dembo | Large deviations techniques and applications[END_REF] and [START_REF] Waterman | Introduction to Computational Biology[END_REF]. Non-identical distributions are considered here.

It is shown that these formula are quite effective. Not only computation is easy with a low complexity, but tightness is ensured. We discuss a possible extension to a larger number of overlap classes.

Preliminaries

In this section, we present the basic definitions and framework necessary to understand our work.

. Given two words w and h, we note w h (resp. w h) when w is a prefix (resp. a suffix) of h. When w h, the word e(w, h) that satisfies h = w • e(w, h) is called the extension of w into h. Prefix and suffix relations are order relations. An equivalence relation on H has been defined in [START_REF] Regnier | A Word Counting Graph[END_REF] that is stable for prefix and suffix relations.

Definition 1. Given a set H, the overlap set is the set of words that are prefix and suffix of two (possibly equal) words in H. It is denoted OV(H).

Two words f and g are said overlap equivalent iff

max {w∈OV(H)} {w f } = max {w∈OV(H)} {w g} (1) max {w∈OV(H)} {w f } = max {w∈OV(H)} {w g} (2)
Definition 2. A set H is called a k-set if the quotient set admits exactly k classes.

Let G denote an overlap class. Given a prefix w of a member of G that belongs to OV(H), this word is a prefix of any word in G and one notes e(w, G) = ∪ g∈G {e(w, g)} .

. A probability model on words steadily extends to overlap classes by a summation of members probabilities. This allows an extension to such patterns of classical generating functions for words [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF].

Definition 3. Given an overlap class F, one denotes H F (z) the probability generating series

H F (z) = f ∈F P rob(f )z |f | . (3)
Given two overlap classes F and G, the probability matrix H(z) is defined as

H(z) = H F (z) H G (z) H F (z) H G (z) . ( 4
)
Given two overlap classes F and G, the correlation polynom A F,G (z) is defined as

A F,G (z) = f ∈F,g∈G w f,w g P rob(e(w, g))z |e(w,g)| , (5)
and the correlation matrix A(z) is defined as

A(z) = A F,F (z) A F,G (z) A G,F (z) A G,G (z) . ( 6
)
Definition 4. Given an integer n, one denotes X n the random variable that counts the number of H-occurrences in a random text of size n. Given an integer k, the generating function for k-occurrences is defined as

L k (z) = n≥0 P rob(X n = k)z n . (7)
The computation of L k (z) for a finite set of words was addressed in [Rég00, RD04], and derived formula depend on matrices of dimensions |H|. Overlap classes allow for a reduction of these formula that makes use of 2-dimensional matrices.

Proposition 1. The generating function for k-occurrences is

L k (z) = (H F (z), H G (z)) • D -1 (z) • M(z) k-1 • D -1 (z) 1 1 , (8)
where

D(z) = (1 -z)A(z) + H(z) (9)
M(z) = I + (z -1)D -1 (z) . (10)
Our proofs rely on the saddle point method and provide an approximate expression for probabilities P rob(X n = k). Section 4 makes use of Large powers Theorem that is proved in [START_REF] Flajolet | Analysis of Algorithms[END_REF] [chapter 8]. In Section 3, problem is reduced to a variant. This theorem rewrites, according to our notations Theorem 1. Large powers: Let A(z) and B(z) be two analytic functions with non-negative coefficients. Let ρ A and ρ B denote their radius of convergence. Assume that B is a-periodic and that ρ B < ρ A . For any real number a, saddle point Equation az a B (za)

B(za) = 1 has a unique positive root. Moreover [z n ]A(z)B(z) na = e -nI(a) A(z a ) √ 2πnz a (1 + o(1)) (11)
where

I(a) = a log B(z a ) -log z a .
Detailed examples for Bernoulli, Poisson or normal distributions can be found in [START_REF] Vandenbogaert | Algorithmes et mesures statistiques pour la recherche de signaux fonctionnels dans les zones de régulation[END_REF], where the classical Large Deviation results [START_REF] Dembo | Large deviations techniques and applications[END_REF] are derived by a generating function approach. The saddle point method was used in [START_REF] Régnier | Rare events and conditional events on random strings[END_REF] for a single word and extended to deal with conditional probabilities. An extension to several words or overlap classes is addressed in the next section.

Large sequences

The main result of this section is Theorem 2 that addresses the case of 2-sets. It is presented in 3.1 and the proof is given in 3.2, 3.3 and Appendix.

Example 1. A typical example is the so-called RY-element

H = ∪ X∈{AT,AG,T T,GT,T G,T A} {X • GCAT GCA} .
It is a 2-set, where OV(H) reduces to {A}. The two overlap equivalence classes are

F = ∪ X∈{T T,GT,T G,T A} {X • GCAT GCA} , G = ∪ X∈{AT,AG} {X • GCAT GCA} .
Example 2. Two strands counting provides an other important example. A Transcription Factor Binding Site, h, is usually searched on two DNA strands, that are not independent. Nevertheless, this search is equivalent to the search of H = {h, h}, where h is the complementary word of h.

Large deviation property for a 2-set

Results will be expressed as a function of the following parameters Notation:

K(z) = det(A(z))(1 -z + T race(HA -1 (z)) (12) θ(z) = (1 -z)T race(A(z)) + T race(H(z)) . ( 13
)
Remark 1. Generating function K occurs whenever a fixed finite number of occurrences k is counted. When the set H reduces to one word h, K(z) reduces to (1 -z)A(z) + P (h)z |h| that can be found in numerous works [START_REF] Guibas | String overlaps, pattern matching, and nontransitive games[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]. Generalization of function K for a set of words was introduced in [BCRV05] .

Definition 5. Given a real a, the fundamental equation is the equation:

K(z)ψ 2 (z) + θ(z)ψ(z, a)φ(z, a) + (1 -z)φ 2 (z) = 0 ( 14
)
where

ψ(z, a) = az[K(z) + K (z)(1 -z)] + K(z)[2(1 -z) -θ(z)] (15) φ(z, a) = az[K (z)θ(z) -K(z)θ (z)] -K(z)[2K(z) -θ(z)] . (16)
Lemma 1. Fundamental equation admits a real positive root. The real positive root of smallest modulus is called the fundamental root and denoted z a .

Theorem 2. Given a real number a = P rob(H), let z a be the fundamental root of the fundamental equation. The number of occurrences of words from a given 2-set H satisfies a large deviation property

lim n→∞ P rob(X n ≥ na) = I(a) (17)
where

I(a) = -a log(1 - ψ(z a , a) φ(z a , a) ) + log z a ( 18
)
Function I is called the rate function.

Remark 2. When a = H F (1) + H G (1) = P rob(H), z a = 1 is the fundamental root and λ(1) is 1. Therefore, I(a) = 0. According to the central limit theorem [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF], this is the expected value in the central domain.

Algebraic properties and eigenvalues derivation

Equation (8) allows for a reduction of our problem to an application of Large Powers Theorem. Intuition is as follows. M(z) is similar to matrix λ(z) 0 0 µ(z) and

M k (z) is similar to λ(z) k 0 0 µ(z) k . Therefore, L k (z) rewrites as A 1 (z)λ(z) k + A 2 (z)µ(z) k . When |µ(z)| < α|λ(z)|, with α < 1, the dominating part of the integrand reduces to A 1 (z)λ(z) k .
In a first step, M is rewritten as a function of K and θ in Proposition 2. The technical proof is deferred to the Appendix.

Proposition 2. Matrix M(z) rewrites M(z) = I -A -1 (z)(I - HA -1 (z) 1 -z + T race(HA -1 (z)) ) ( 19
)
When its dimension is 2, it satisfies

T race(M(z)) = 2 - θ(z) K(z) (20) det(M(z)) = (1 -z) + K(z) -θ(z) K(z) . (21)
In a second step, we proceed to the search of the eigenvalues of matrix M(z). According to spectral Theorem, eigenvalues are the roots of the characteristic polynom

X 2 -T race(M(z))X + det(M(z)) .
Let T (z) denote K(z)T race(M(z)) and D(z) denote K(z)det(M(z)). When K(z) = 0, eigenvalues are the roots of the polynom P defined as

P (X) = K(z)X 2 -T (z)X + D(z) . ( 22
)
Let λ(z) and µ(z) denote the two eigenvalues. Deriving P (λ(z)) with respect to z yields a functional equation to be satisfied by λ(z) and λ (z),

K (z)λ 2 (z) + 2K(z)λ(z)λ (z) -T (z)λ (z) -T (z)λ(z) + D (z) = 0 . ( 23
)
The same equation is satisfied by µ(z) and µ (z).

In a third step, we show that one of the two eigenvalues admits a saddle point that is given by the fundamental equation.

Saddle point equation rewrites azλ (z) -λ(z) = 0. Plugging this equation into Equation 23 yields Q(λ(z)) = 0 where

Q(X) = (2K(z) + azK (z))X 2 -(T (z) + azT (z))X + azD (z) . (24)
Eigenvalue λ(z) being a common root of P and Q, it is a root of GCD(P, Q). Computing this GCD and substituting T (z) and D(z) expressions yields:

GCD(P, Q) = -Xφ(z, a) -ψ(z, a) + φ(z, a) .
This GCD has a single root 1 -ψ(z,a) φ(z,a) . It is a common root of ( 22) and (24) iff it is a root of either one. Substituting 1 -ψ(z,a) φ(z,a) to X in P leads to the fundamental equation (14).

Saddle point

Finally, we show that the saddle point provides the main contribution to the integrand. Property below is shown in Appendix 2. It generalizes a result established for a single word [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]. Lemma 1 and 2 are shown in Appendix. Proposition 3. Equation K(z) = 0 admits a root ρ that is real positive. Moreover, ρ > 1 and ρ is the root of smallest modulus.

Exists h > 0 such that any other root σ satisfies |σ| > |ρ| + h.

Lemma 2. Fundamental root z a satisfies 0 < z a < ρ .

Roots λ and µ satisfy µ(z a ) < λ(z a ) < 1 .

Proposition 3 and Lemma 2 allow for an application of Large Power Theorem. One computes [z n ]A 2 (z)µ k (z) by integration on the contour z = z a . As |µ(z)| < |µ(|z|)|, this is upper bounded by e -naµ(za) that is exponentially smaller than e -naλ(za) = e -nI(a) . This yields Equations 17 and 18.

Remark 3. This scheme should extend to several words. The degree of the characteristic polynom, determinant(M(z) -λ(z)I) can be reduced to the number p of overlap classes [START_REF] Regnier | A Word Counting Graph[END_REF]. The fundamental equation becomes Resultant(P, Q) = 0, that is a polynom of degree p -1. Although no close formula can be given here, a numerical approximation should be computable and I(a) follows whenever GCD(P, Q) can be efficiently computed.

Short sequences

Studying short sequences statistics is of great interest too. Here, "short" means that sequences do not contain enough symbols to enter in an asymptotic behavior (the sequence length is in the order of hundreds of symbols). In computational biology, this is the case when one searches for cis-acting elements in regulatory sequences [NBM + 11] that may be known, for example from ChIP-chip or ChipSeq experiments, as being under a similar regulatory control. Formally, this can be viewed as the search of common similar motifs in short random sequences. The particularity of this case is that first, the probability that a sequence contains an occurrence can be precisely computed but second, the number of sequences is huge allowing asymptotic statistics to be derived.

Let H denote the set of admissible motifs. In the sequence number model, a sequence is considered as positive if it contains at least one H-occurrence.

One assumes below that M random sequences are given. Their lengths may be different but are usually similar, due to experimental constraints. The probability to find one (or k) motifs from a set H in sequence i actually depends on (the symbol composition of) sequence i. Let us be more formal. Definition 6. Given a set of M random sequences, let p i be the probability to find one H-occurrence in a sequence with number i. One notes

µ(u) = M i=1 [p i (u -1) + 1] . ( 25
)
Remark 4. When all probabilities p i are equal, say p i = p, and M is large, φ(t) = µ(e t ) = (p(e t -1) + 1) M converges to the probability generating function of the Gaussian law, and large deviation results are known [START_REF] Dembo | Large deviations techniques and applications[END_REF] or, in the context of computational biology [START_REF] Waterman | Introduction to Computational Biology[END_REF][START_REF] Régnier | Comparison of statistical significance criteria[END_REF]. It is worth noticing that Large Power Theorem steadily applies. Our goal is to focus on the case when the p i 's are different, meaning, in a biological sense, that each sequence may comes from distinct region of the genome with different nucleotide compositions.

Remark 5. Equation (25) can easily be turned into a recurrence formula that permits to design a dynamical programming algorithm for computing µ(u) in an efficient way (with a complexity of order O(M 2 )), In fact, our goal is to obtain the k-th coefficient of polynom µ(u) that equals the probability that exactly k sequences out of M sequences contains one H-occurrence. Indeed, denoting µ n (u) = M i=1 [p i (u -1) + 1], there exists a trivial recurrence relation relating the coefficients of µ n (u), that is

[u k ]µ n (u) = (1 -p n )[u k ]µ n-1 (u) + p n [u k-1 ]µ n-1 (u) with [u 0 ]µ 1 (u) = (1 -p 1 ) and [u 1 ]µ 1 (u) = p 1 .
Its computation is then straightforward.

In the following section, we give a novel approximation formula for computing [u k ]µ n (u) in a constant time.

Large deviations formulae

Our aim here is to provide an approximate computation that relies on large deviations [START_REF] Dembo | Large deviations techniques and applications[END_REF]. Our aim is the derivation of the probability to have at least k positive sequences out of M , where a = k M is (significantly) greater, or smaller, than the expectation.

Notation: One denotes, for each integer j,

σ j = i=M i=1 p j i , τ j = σ j M . (26)
Remark 6. It follows from Equation (25) above, generating functions properties and general probability theory that the expected size of a positive cluster is σ 1 and its variance is σ 1 -σ 2 .

Theorem 3. The distribution of the number of positive sequences in a set of sequences satisfies a large deviation property. Let K be the number of positive sequences and a some real number satisfying M a = σ 1 and 0 < a < 1. lim

M →∞ 1 M log(P rob(K ≥ M a) = -I(a) (27)
where

I(a) = at a + ∞ j=1
(-1) j τ j (e ta -1) j .

I(a) can be approximated as

a ta -τ 1 a -τ 1 τ 1 -τ 2 . ( 29
)
Proof. Large Power Theorem extends for φ(t) = µ(e t ). Let h a (t) be the function

ta = log[1 + a -τ 1 τ 1 -τ 2 + (a -τ 1 ) 2 (τ 2 -τ 3 ) (τ 1 -τ 2 ) 3 ] . (30)
Proof.

h a (t) = 1 M log φ(t) -at = 1 M M i=1 log[p i (e t -1) + 1] . (31)
and a, 0 < a < 1 is real. Namely, h a (t) = 0 leads to

1 -a = 1 M M i=1 1 -p i p i (e t -1) + 1 . (32)
A Taylor expansion of (32) yields

M (a -1) = - i (1 -p i )[1 + j≥1 (-1) j p j i (e t -1) j ] = -M (1 -τ 1 ) + M j (-1) j+1 (τ j -τ j+1 )(e t -1) j
Under the two conditions that p i (e t -1) is small (p i is small) and that |(σ j -σ j+1 )(e t -1) j | are upper bounded by some number smaller than 1, -a condition to be checked in the computations -, we get to Equation below where X stands for e t -1.

0 = (τ 1 -a) + (τ 1 -τ 2 )X -(τ 2 -τ 3 )X 2 .
One choses among the smallest among the two solutions. This yields (30). It satisfies t a = 0 when a = τ 1 .

Expanding φ(t) as an analytic series steadily yields (28) for h a (t). Substituting the approximate value ta for t a in (30) yields (29).

Experiments and computational precision

We provide here some evidences allowing to compare the results obtained by our large deviation approximation against an exact computation1 of the same quantity. and by the large deviation approximation. Our goal is to assess the tightness of our approximation, in the domain where an exact computation remains feasible in order to justify large deviation results in the domains that are beyond this scope. Indeed, the required numerical precision in order to obtain some rigorous and exact results is proportional to the number of sequences, making the computation tricky for huge sets of sequences.

We used a set of 3000 sequences, The probability (p-value p i ) to find the motifs in each sequence is reported. It ranges between between 0.0009 and 0.0000001027. The mean σ 1 was 0.0002262 and the variance 0.0002263. The corresponding values for σ 1 , σ 2 and σ 3 are σ 1 = 0.679, σ 2 = 3.5.10 -4 , σ 3 = 2.2.10 -7 . For small values, a little difference arises. It is due to the fact that, using (only) I(a) we neglected a second order term in the development of the p-value. A drift occurs for k occurrences when k is larger than 100. This is due to the approximation done on ta and I(a). Notice that pushing a little bit further the computations, tighter approximations for I(a) and ta can be obtained ("pumping method"). For instance, a tighter approximation of I(a) is given as

I(a) ∼ a ta -τ 1 a -τ 1 τ 1 -τ 2 + (a -τ 1 ) 2 (τ 1 -τ 2 ) 2 (τ 1 τ 3 -τ 2 2 ) . (33)

Further work and conclusion

We have captured important properties and combinatorial constraints for multiple pattern statistics in this paper. Two different cases have been considered. First, asymptotic behaviors for the number of occurrences of patterns in a set containing a small number of very large sequences. We notably proved that several results holding in the case of single word counting extends to multiple patterns providing explicit relations that allow to get large deviation results and precise formulas for the tail distribution of the number of occurrences of multiple patterns. We applied the obtained properties to the double strands counting problem for huge sequences. This problem combines two major difficulties of the actual datasets at disposal. First, dealing with huge sets of sequences implies that exact and precise computations are unrealistic. Second, dependencies implied by a double strands counting cannot be neglected. Here, we solved the first issue by furnishing tractable formulas for computing the p-values in the large deviations domain. The second issue is solved by considering combinatorial properties of sets of patterns, including a correlation between sets of words property that is crucial in the study.

Second, we derive results for the asymptotic behavior of the number of pattern occurrences in a huge number of small sequences. This latter case is important in the context of biological sequence analysis since it corresponds to several realistic cases such as ChIP-chip or ChIP-seq experiments.

Notice that our framework should quite easily extend to multiple sets counting, the case of two sets having a particular interest in our opinion since it provides a solution to the double strands counting problem.

Proof. Functions log(λ(z)) and log(z) are defined and analytical in ]0.ρ]. Therefore. the same property holds for function h a (z). As Proof. M(z) and I -M(z) = A -1 (z)(I -B) represent the generating function of languages. Therefore, all coefficients are positive. Consequently, for z real and positive in the disk of convergence, eigenvalues λ(z) and µ(z) are real positive and their modulus is smaller than 1.

One now studies the difference λ(z) -µ(z).

Clearly ψ 2 (z a ), φ 2 (z a ) and (z a -1) are greater than 0. As λ(z a ) < 1, the same property holds for φ(z a )ψ(z a ). As z a < ρ, the same property holds for K(z a ) and inequality µ(z a ) < λ(z a ) is established.

1M

  log φ(t) -at. One searches for the roots of smallest modulus of Equation h a (t) = 0. They are described in Proposition 4, Proposition 4. The root of smallest modulus of Equation h a (t) = 0 is real. It is called the fundamental root. It can be approximated by ta where

  lim z→0 h a (z) = lim z→ρ h a (z) = +∞ , this function admits in this interval a root z a . It follows from P and Q definitions that λ(z a ) isa root of fundamental equation. This establishes Lemma 1.

  λ(z) -µ(z) = 2λ(z) -θ(z) = 2ψ(z)K(z) + θ(z)φ(z) φ(z)K(z) . (35) Equation 14 at point z a yields λ(z a ) -µ(z a ) = ψ 2 (z a )K(z a ) -(1 -z a )φ 2 (z a ) φ(z a )ψ(z a )K(z a ).

Table 1 :

 1 Table1synthesized the obtained results. It thus illustrates the tightness of the large deviation approximation. Large deviations (LD) versus exact computations: log. p-value for different number k of occurrences. The value M I(a) that is the logarithm of the p-value (multiplied by -1) is displayed. Relative error is also given showing an asymptotic convergence of the LD formula to the exact value.

	k	10	15	20	30	50	100	200	500	1000
	LD	17.6 32.3 48.6	85	167.5 407.1 965.9 2962.4 6860.7
	Exact	19.7 34.5 50.9 87.3 169.4 406.9 956.9 2907.8 6746.2
	Relative error (%) 10.6	3.1	6.4	2.6	1.1	< 0.1 < 0.1	< 0.1	< 0.1

the exact computations are performed by a companion software available on request.

Appendix 1

In this appendix, we prove that Proposition 1 can be established from equations (10) and (9) by using simple algebraic manipulations.

Matrix A(z) is regular for z around 0 [START_REF] Régnier | Rare events and conditional events on random strings[END_REF]. Equation (9) leads to

The rank of matrix H being 1, the rank of matrix B = HA -1 (z) is 1, too. For any integer k, equation

B holds and

Equation (10) steadily rewrites into (19).

This rewriting allows for a computation of the trace and the determinant of matrix M(z). Trace computation makes use of technical property (34). Given two 2 × 2 matrices, M and N, the rank of N being 1, it is easy to establish that

Using (34) for A -1 (z)HA -1 (z) yields

As T race(A -1 (z)) = T race(A(z)) • det(A -1 (z)), this yields

. We now observe that det(M) = det(M -I) -1 + T race(M). Using it for the singular matrix

and (21) follows from (20).

Appendix 2

Here is a sketch of the proof of saddle point approach. The aim is to show that the contribution is given by the root λ that traverses saddle point (z a , λ(z a )).

We proceed to the proof of Lemma 1 and 2


Generoso Pagano
email: generoso.pagano@inria.fr

Vania Marangozova-Martin

SoC-Trace Infrastructure

Keywords: Traces d'exécution, débogage, proling, systèmes embarqués, multi-c÷ur, source libre, gestion de traces, infrastructure, modèle de données, base de données, format de trace, SoC Execution traces, debugging, proling, embedded systems, multi-core, open source, trace management, infrastructure, data-model, database, trace formats, SoC

Les traces d'exécution sont largement utilisées pour la mise au point et l'optimisation des applications embarquées. Dans ce contexte, le projet SoC-Trace a pour objectif de fournir une infrastructure logicielle ouverte, capable d'exploiter de manière ecace les traces provenant d'exécutions de systèmes embarqués multi-c÷ur. Ce rapport décrit l'architecture système et logicielle du premier prototype de l'infrastructure. Ce prototype comprend, d'une part, un modèle de données qui représente les concepts intervenant lors de l'analyse de traces. D'autre part, il fournit une implémentation de ce modèle pour les bases de données relationnelles, ainsi qu'une interface logicielle pour son exploitation. Les utilisateurs peuvent travailler avec des traces de formats différents, les accéder à travers une interface uniée et, après analyse, stocker les résultats dans la base de données. En fournissant des mécanismes partagés et réutilisables, l'architecture permet la collaboration de plusieurs outils d'analyse de traces, facilitant ainsi la création de chaînes d'analyse de traces innovantes et complexes.

1

SoC-Trace Project Execution traces are a powerful instrument for analyzing embedded systems behavior. They are used for understanding particular behaviors of a system, for debugging, for proling and for optimization. The research on trace management is currently raising more and more interest in both industrial and academic world [START_REF] Prada-Rojas | Summarizing Embedded Execution Traces through a Compact View[END_REF] [START_REF] Hedde | A non intrusive simulation-based trace system to analyse Multiprocessor Systems-on-Chip software[END_REF].

The main objective of the SoC-Trace project [START_REF] Santana | Présentation du Projet SoC-Trace[END_REF] is the development of a generic trace management infrastructure and a set of tools able to exploit multi-core embedded-systems execution traces. The infrastructure should be able to store and analyze multiple traces of dierent formats whose size can be huge (i.e. of the order of TB). The infrastructure is to be open source, generic and ecient. The nal goal is to have dierent tools, built on top of the infrastructure and providing new analysis methods, like data mining analysis, probabilistic analysis, richer visualization techniques, etc.

The trace management infrastructure, described in this document, has a critical importance in the whole project, since it denes the interfaces to access trace data and analysis results, thus being an integration point for the dierent analysis tools.

Infrastructure Objectives

The main objectives of the infrastructure are :

• The management of several traces in a database, using a shared generic data-model.

• The management of dierent tools able to work on traces.

• The management of the analysis results produced by the various tools.

The infrastructure shall be generic, since its usage must not be limited to a single trace format or a specic tool. Its data-model shall be able to reect dierent trace formats and dierent analysis results. The infrastructure, being open source, shall provide extensible and reusable mechanisms. At the same time it shall be able to manage external black-box tools.

The infrastructure shall be ecient, being in charge of dealing with huge amount of data : an execution trace, in fact, can easily exceed the size of several GBs or almost TBs. Finally, the infrastructure shall be complete, meaning that all the required functional and non functional requirements described so far shall be accomplished.

The following sections of this document are organized as follows. Section 3 presents the system architecture, with emphasis on the data-model. Section 4 provides some details on the infrastructure software architecture, with the description of the main modules. Section 5 describes two external tools developed to work with the infrastructure. Section 6 shows some rst performance evaluation results obtained with the infrastructure prototype. Section 7 describes the future works we are planning. Finally, section 8 concludes.

System Architecture

The SoC-Trace infrastructure is built on top of the Eclipse Platform [5], which has been chosen because it is easily extensible and well designed in order to be used as an integration point for dierent applications. In order to take the greatest advantage of the Eclipse Platform capabilities, the Java programming language has been chosen. The general architecture of the SoC-Trace infrastructure is shown in Figure 1.

The elements strictly belonging to the SoC-Trace infrastructure are :

• The Multi-Trace DB : a database able to store (meta)information about traces, trace analysis tools and analysis results. The traces can be of dierent formats, the tools can provide dierent types of analyses and the results may be of various types. The database stores also references to external les, in order to make it possible to organize the dierent les related to a trace.

• The SoC-Trace Library : a software library composed by a set of Eclipse plugins, providing a convenient interface to deal with the database and the entities of the data-model.

• The SoC-Trace Management Tool : a simple front-end tool used to graphically execute basic management operations on the whole system.

The infrastructure source code is written in Java, since the use of this language is, at the moment being, mandatory to write Eclipse plugins. However, the infrastructure is able to manage both Java and non-Java tools. The latter have the possibility to access directly the database and the external les, without necessarily passing through the SoC-Trace Library. The database management system (DBMS) we have chosen is MySQL [6]. The main motivations are its scalability and exibility, its good performance and its open source license. In the following sections we describe in detail the three main blocks of the SoC-Trace infrastructure.

3.1 Multi-Trace DB

Conceptual model

The conceptual model of the SoC-Trace Multi-Trace DB has been designed with the aim of capturing the most signicant concepts concerning the area of execution traces management and analysis. We have organized these concepts in three groups :

• Trace General Information : here we will typically gather information about the tracing conguration and the les related to a trace.

• Raw Trace Data : this includes the registered-execution data, i.e. the events and their format, as well as the information about their producer.

RT n°427

• Analysis Data : this concerns the meta-data about the used analysis tools and the dierent analysis results.

We can nd these three groups, with their corresponding entities, in the Crow's Foot diagram shown in Figure 2.

PROCESSED_TRACE

Fig. 2 Conceptual Model

The system manages several execution traces (TRACE), which can be related to one or more les (FILE) (e.g. conguration les, raw trace les, IP-XACT [START_REF]IP-XACT[END_REF] hardware description les).

Each trace is composed by several events (EVENT), an event being some change in the state of the traced system. An event is caused to happen by a single active entity we call an event producer (EVENT_PRODUCER). Examples of event producers are typically processes or threads. An event producer can generate several events and there can be a hierarchy among event producers (e.g. a process creating son processes).

The model also integrates information about the tools performing operations on traces (TOOL).

Tools may save the results of their analyses (ANALYSIS_RESULT) in order to avoid their (possibly expensive) re-computation. In the current model, an analysis result involves a single trace.

In the diagram, the concept of analysis result is modeled as an abstract entity, which has its concrete realizations in specic kinds of analysis results. We have dened namely :

• Searching/Filtering (SEARCH) Result : a result of a searching/ltering operation, which can be performed over the events or over the event producers of a trace.

• Custom File (RESULT_FILE) Result : this models a result which is stored in a custom le outside of the infrastructure. The database contains only the reference to the le, the semantics of the le content being understandable by the tool that produced the le.

• Grouping (GROUP) Result : a result structured in terms of groups of model entities (events, types of events or types of event parameters), possibly dening a hierarchy among such groups.

• Generic Annotation (ANNOTATION) Result : an annotation is an analysis result which describes itself (it uses the Self-Dening Pattern, discussed in section 3.1.3). It allows the tool to dene both the structure and the value of the result.

• Processed Trace (PROCESSED_TRACE) Result : this result is a trace produced after treating another trace through, for example, adding additional information.

A detailed description of each kind of analysis result is provided in section 3.1.3.

By dening a standard interface for analysis results, the infrastructure enables the cooperation among dierent tools. For example, using the analysis result provided by the data-model, it is possible for a tool A to retrieve the results of a tool B, perform other elaborations and nally Inria produce another result. Furthermore, a shared set of analysis result types is also a base brick for the denition of complex workows among dierent tools.

Database architecture

The Multi-Trace DB is designed as a two-level hierarchy of databases, as shown in Figure 3.

• Traces general information We have chosen such distributed architecture mainly for simplicity of implementation, scalability and eciency. Indeed, the database schema of each Trace DB is simpler compared to a centralized solution. Yet, it is still possible to perform multi-trace (multi-DB) queries with MySQL. Other points that would impact the performance in a centralized solution are the space overhead to store a trace id in all rows of almost all tables, the time overhead to perform queries in presence of the above mentioned trace id and the presence of huge tables, which can lead to the necessity of table partitioning [START_REF]MySQL Table Partitioning[END_REF].

This distributed architecture leaves the place for extensions. In particular, if in the future multi-trace analyses will be performed, the System DB schema will be accordingly extended to support the storage of such multi-trace analysis results.

Database schema

Before explaining in detail the System DB and Trace DB table structures, we present the concept of Self-Dening Pattern which is used in several places.

RT n°427

Self-Dening Pattern

In both System DB and Trace DB, we have used a Self-Dening Pattern (SDP) in order to achieve the greatest genericity of representation. A SDP, as the name suggests, allows the representation of both values and their structure (type) information.

In order to illustrate this pattern, let us consider an Element (Figure 4). The SDP represents the Element concept using 4 tables.

An Element (ELEMENT) has a type (ELEMENT_TYPE) which is described by a given set of parameter types (ELEMENT_PARAM_TYPE). The values of these parameters for a given Element are stored in the ELEMENT_PARAM table. So the right part of the SDP describes the type of an Element (type and related parameter types), while the left part contains the values (the Element predened attributes and parameters values). Each table contains the IDs (primary keys or foreign keys) necessary to perform the join with the other tables.

The Self-Dening Pattern is used in the DB schema to model the concepts of Trace, Event and Annotation. In the following, when talking about a generic concept modeled using the SDP, we will often use the name Element to identify such generic concept.

System DB and Trace DB schema The System DB stores general information about traces and the tools registry. There are numerous trace formats, including KPTrace [START_REF]KPTrace Trace Format[END_REF], OS21 [START_REF]OS21 Trace Format[END_REF], Pajé [START_REF] Chassin | Paje : An Extensible Environment for Visualizing Multi-Threaded Program Executions[END_REF] or Open Trace Format (OTF) [START_REF] Knüpfer | Introducing the Open Trace Format (OTF)[END_REF]. As the infrastructure should be able to store traces having dierent formats, we RT n°427 have used the SDP for the representation of the Trace concept. In this case a trace type identies a particular kind of trace (e.g. KPTrace trace) and the parameter types can be conveniently used to model specic conguration parameters, necessary to describe the environment where that trace has been produced (e.g. version of a driver, version of the tracing API, etc.). On the other hand, in the TRACE table, we store some attributes common to all kinds of trace (whatever trace type), like the date the trace has been produced and the number of CPUs.

The Tool concept is described by its name, its type and its launching command. The supported types of tools are currently : IMPORT and ANALYSIS. The rst group concerns the tools in charge of importing raw traces into the infrastructure : the idea is to have a specic importer for each kind of trace format, which acts as an adapter from the specic format details to the SoC-Trace data-model. The second group of tools is quite large and includes all the tools able to perform whatever kind of analysis on a trace : pattern mining analysis, probabilistic analysis, etc.

Note that there is no explicit link between the TOOL table and the trace SDP tables, since this link passes through the Trace DB (whose name is one of the predened attributes stored in the TRACE table). The Trace DB stores the link between the result of one analysis performed on the trace and the ID of the tool performing such analysis.

The Trace DB stores the raw trace data and the trace analysis results. For the ease of explanation, we can separate the Trace DB schema in two parts, the one related to the raw trace and the one related to the analysis results.

Trace DB : raw trace data In Figure 6 we can see the raw trace data section of the Trace DB schema. This part of the Trace DB stores information about raw events of dierent types, event producers and les related to the trace. As a trace may contain dierent types of events (e.g. context switch events, memory allocations, etc.), we have represented the event concept using the SDP. Thus we can store in the EVENT table the attributes common to all event types (e.g. the timestamp or the CPU where the event has been produced), and use the other tables to describe the parameters typical of a Inria specic event type (e.g. a context switch event could be described by the new PID and the old PID). An event producer is described by its type (e.g. process, thread, etc.), its local identier (e.g. the PID, if the producer considered is a process) and its name. The EVENT_PRODUCER table contains also a parent ID, intended to allow an importer tool to build a hierarchy among sources, while parsing the trace (e.g. threads created by a process). A le (FILE table) is simply described by its path and a custom textual description.

Example Let us consider how an event related to a context switch (name CS) could be mapped to the model. The event is traced with the following format :

<timestamp> CS <oldpid> <newpid>

A concrete event could be the following :

CS 0 21

This line can be imported into the database lling the four Event-SDP tables as shown in Figure 7. Trace DB : analysis result data Fig. 8 Trace DB : analysis result data

EVENT

In Figure 8 we can see the analysis result part of the Trace DB schema. This part allows the representation of dierent analysis results produced by analysis tools. The entry point to understand this part is the ANALYSIS_RESULT table. Each analysis result is described by a unique identier (ID), the identier of the tool that performed the analysis (TOOL_ID), the type of analysis result produced (TYPE), the date of the analysis (DATE) and a custom description (DESCRIPTION). Considering the TYPE eld, the data-model currently allows ve dierent kinds of results to be stored in the DB :

Custom result le This result type is represented using the RESULT_FILE table, which stores the analysis result ID, the le ID (a result can contain more than one le) and the le path.

Grouping A grouping is composed by several groups of entities of the data-model (for the moment being it is possible to create groups of events, of event types or of event parameter types). A grouping can be possibly organized as a hierarchy of groups. For each group of a grouping it is possible to dene several structural properties. First of all you specify the target entity being grouped (EVENT, EVENT_TYPE or EVENT_PARAM_TYPE) and the grouping operator (AND, OR). Then you specify if there is a total ordering among Inria the entities grouped (TRUE, FALSE). Finally it is possible to specify a sequence number, meaningful if the parent group is ordered. This result type is represented using two tables :

• GROUP : it stores the analysis result ID, the group ID (a grouping result can of course involve several groups), an optional parent ID (used to build hierarchies), the group name, the target entity name, the grouping operator, the ordered ag and the sequence number.

• GROUP_MAPPING : this table links each group (GROUP_ID) with the target entity instances belonging to that group (TARGET_ENTITY_ID). In a hierarchy, only leaf groups (the ones actually containing entity instances and not containing only other groups) are present here. The key of the table contains both the group identier and the entity identier, thus making it possible to have more entities in a given group and the same entity in more than one group.

Searching/Filtering A searching or a ltering of entities of the data-model produces as output a list of such entities. Currently it is possible to save the searching/ltering output related to events or event producers. This result type is represented using two tables :

• SEARCH : it stores the analysis result ID, the custom command used to perform the search/ltering operation (tool dependent) and the target entity name.

• SEARCH_MAPPING : this table lists the IDs of the entity instances being the result of the search/ltering operation.

Annotations This result type is intended to be as generic as possible, leaving to the analysis Processed trace This result type is actually a link to another trace, being created starting from the current trace (the trace corresponding to the current Trace DB) and performing some kind of processing. The result type is saved in the PROCESSED_TRACE table that, in addition to the analysis result ID, simply contains the processed trace ID. In practice, the processed trace is stored in another Trace DB, thus being a completely normal trace : the single particular to consider is that in the TRACE table of that Trace DB, the PROCESSED ag shall be set to TRUE.

As anticipated above, the precise denition of common analysis result types is a powerful enabler for the cooperation among dierent analysis tools. For example, being the grouping result type format dened, a tool A can reuse a grouping dened by a tool B, in order to perform its elaboration. Let's imagine that the tool B identies a pattern (saved as a group of event types) : the tool A can take into account this pattern denition to perform a ltering of the event instances for that pattern in order to do further analysis.

SoC-Trace Library

The SoC-Trace Library is a software library written in Java, providing a convenient interface to the Multi-Trace DB. The library is composed by a group of Eclipse plugins and allows Java external tools and the SoC-Trace Management Tool to interact with the database in a convenient RT n°427

way. In fact it provides an object oriented vision of the data-model and several mechanisms to deal with the objects of the model without caring about SQL and databases low level issues.

More details about this software library are given in section 4.1.

SoC-Trace Management Tool

This management tool is implemented in Java as a group of Eclipse plugins. Currently, the following functionalities are implemented.

• The creation of the SoC-Trace System DB (Figure 9). The system DB has a predened name (SOCTRACE_SYSTEM_DB) and is created on localhost.

Software Architecture

The entire SoC-Trace infrastructure is written in Java, using JDBC [13] to interface with the MySQL database management system. The code is organized as a group of Eclipse plugins. In Inria

Model

The data-model is implemented in the plugin com.inria.soctrace.lib.model, which provides an object oriented representation of the DB schema. For all the tables of the DB (excluding some of the tables related to the concrete realization of specic analysis result, as explained below) there is a Java class that directly maps to it. These classes are implemented according to the following principles :

• The class stores all the attributes of the corresponding table, with the exception of the foreign key IDs (the IDs allowing the join with other tables) : in this case a reference to the corresponding foreign object is stored.

• Considering the SDP tables, an Element class always stores its ElementParam references, and an ElementType class always stores its ElementParamType references. See for example Figure 12, which shows the high level UML diagram related to the Event SDP object oriented implementation.

The plugin denes four Java interfaces :

• IModelElement

This interface is implemented by all the classes strictly modeling entities of the model. • The class for the analysis result entity (AnalysisResult) All these classes have an ID getter and can accept an IModelVisitor (see below).

• ISearchable

This interface is implemented by all the classes that model entities that can be the target of a searching/ltering analysis. Currently Event and EventProducer classes implement this interface.

• IGroupable

This interface is implemented by all the classes that model entities that can be the target of a grouping analysis. Among the classes already mentioned, currently Event, EventType and EventParamType classes implement this interface. This interface is implemented also by the class Group, which models a group of IGroupable objects (Composite pattern [START_REF] Gamma | Design Patterns : Elements of Reusable Object-Oriented Software[END_REF]).

Actually the Group class is abstract and has two concrete implementations : OrderedGroup and UnorderedGroup.

• IModelVisitor

This is the interface for all the visitors (see Visitor pattern [START_REF] Gamma | Design Patterns : Elements of Reusable Object-Oriented Software[END_REF]) for the classes implementing IModelElement interface. Currently, the Visitor pattern is used to save the dierent objects of the data-model into the DB (see section 4.1.2).

The analysis result part of the data-model deserves more explanations. Figure 13 shows a high level UML diagram of this part.

As we said, the AnalysisResult class implements the IModelElement interface. This class contains a reference to an AnalysisResultData, which is an abstract class whose concrete implementations store the necessary information for the dierent types of analysis result. Currently we have the following concrete classes :

• AnalysisResultProcessedTraceData It contains the references to the source Trace and the processed Trace objects.

• AnalysisResultGroupData It contains the reference to the root node of the grouping.

• AnalysisResultSearchData It contains a list of ISearchable objects.

• StoredProcedures

It contains the SQL code for some stored procedures that can be used for manually inspecting the database content.

• DBInitializer

It contains the Java code to create the various SoC-Trace tables.

• SystemDBObject and TraceDBObject

These classes allow the user to deal with the System DB and the Trace DB respectively.

Both classes derive from the abstract DBObject class and allow the user to :

• Create a new DB of the given type.

• Open/Close a connection to an existing DB. The connection can then be used to give SQL commands to the DB using JDBC statements.

• Commit/Rollback the current DB transaction (auto-commit mode is OFF for eciency reasons).

• ModelElementCache

It is a generic cache for objects belonging to classes implementing the IModelElement functionalities common to all the visitors that work on the DB, dealing with model objects.

For the moment being, only the ModelSaveVisitor class has been implemented, in order to save the model objects into the DB. Each of the DBObject concrete class oers a save() method, that accepts an object implementing the IModelElement interface and calls the accept() method on such object passing an instance of the ModelSaveVisitor. This way, the interface to save a model object into the DB is very easy for the library-user. For example, to save a list of Event objects into the DB, you have to write only the code shown in Figure 14, where events is a list of Event objects and traceDB is the reference to a TraceDBObject.

Query

The com.inria.soctrace.lib.query plugin contains classes used to perform generic queries on the objects of the model. The plugin provides both query-classes and condition-classes. The basic idea is that to perform a query on an element of the model, you instantiate the specic query-class for that element and add to such query-object the required conditions to be fullled.

Both query and condition classes are described in the following.

Condition-classes

To understand how query-classes work, rst we describe the conditions that can be attached to them. We can have two kinds of condition-classes :

• The condition-classes implementing the ICondition interface, used to specify conditions for simple attributes of a generic table.

• The condition-classes implementing the IParamCondition interface, used to specify conditions on Element-SDP parameters. We remind that, here and in the following, by Element we identify a generic concept modeled as SDP.

Both kinds of condition-classes are built using the same design pattern (Composite [START_REF] Gamma | Design Patterns : Elements of Reusable Object-Oriented Software[END_REF]), as shown in Figure 15 For the classes implementing ICondition interface, <name> refers to the name of an attribute of a specic table and <value> refers to the value of this attribute. An example of SQL condition produced using ICondition and referring to the EVENT table could be the following :

( ( TIMESTAMP > 1000 ) AND ( CPU = 0 ) )

For the classes implementing IParamCondition, <name> refers to the value of the attribute 'NAME' in the ELEMENT _PARAM_TYPE table and <value> refers to the value of the attribute 'VALUE' in the ELEMENT _PARAM table. So, in this case the actual SQL condition is more complicated, since it requires information from the two tables above mentioned, plus the ELEMENT _TYPE table. However this complexity is hidden by the IParamCondition class, so the nal SQL condition can be safely put in the WHERE clause of a query performed on the ELEMENT table.

RT n°427

Query-classes

A query-class is a class that can be used to perform queries on database tables, possibly using the condition-classes described above. The com.inria.soctrace.lib.query plugin denes three main abstract classes for query-classes :

• ElementQuery This class provides the basic functionalities to perform generic queries on simple (non-SDP) DB tables. For this kind of queries, only ICondition classes are used. The concrete classes implementing this abstract class are :

• AnalysisResultQuery • EventParamTypeQuery • EventProducerQuery • EventTypeQuery • FileQuery • ToolQuery
Note that the AnalysisResultQuery does not retrieve from the DB the analysis result data (AnalysisResultData abstract class). For this purpose, you should use the AnalysisResult-DataQuery (see below) class explicitly. This is done for eciency reasons : rst you perform the query to get the AnalysisResult objects respecting some conditions, then you load the AnalysisResultData only into those objects that actually are of interest for you. A common use case is in fact to browse into analysis results, just to see the type or the date of the analysis itself, without being interested in loading the analysis result data (potentially a huge amount of data).

• SelfDeningElementQuery

This class extends the ElementQuery class, adding the support for IParamCondition. The class is in fact designed to be the base class of query-classes for SDP elements. The concrete classes implementing this abstract class are :

• EventQuery • TraceQuery • AnalysisResultDataQuery
This class is designed to be the base of all the classes that are used to retrieve an analysis result from the DB, specifying the analysis result ID. This class does not support ICondition or IParamCondition, since the only purpose is to retrieve from the DB the analysis result data produced in a given analysis. Once the data is retrieved, it can be set in the corresponding AnalysisResult object. The concrete classes implementing this abstract class are :

• AnalysisResultProcessedTraceDataQuery • AnalysisResultGroupDataQuery • AnalysisResultSearchDataQuery • AnalysisResultAnnotationDataQuery • AnalysisResultFileDataQuery
Example Figure 16 shows an example of usage of the EventQuery class. In this example we want to nd all the context switch events (CS) produced after the timestamp 1000000 on CPU 0, where the old PID is 1205 and the new PID diers from 0.

As the example shows, this query interface is quite powerful and generic, but has the drawback of being not so straightforward to use. Query-classes and condition-classes are therefore used to build a simplied higher-level query interface, described in section 4.1.4. • Requests to get one or more Tool objects, respecting the given criteria :

Inria

• Get the tool with a given name.

• Get all the tools of a given type. • Requests to get one or more Trace objects, respecting the given criteria :

• Get the trace corresponding to a trace DB name.

• Get all the traces produced between two dates.

• Get all the traces where a given application has been traced.

• Get all the traces produced on a given board.

• Get all the traces produced on a given operating system.

• Get all the traces produced on a given number of CPUs.

• Get all the traces captured using a given output device.

• Get all the traces having a given description.

• Get all the traces of a given type.

• Get all the traces whose type is among the ones specied.

• Get all the traces of a given type, for which given parameters have given values.

• Get all the traces (processed or not).

• Get all the raw traces (non-processed traces).

• Get all the processed traces. • Request to get the File objects related to a given trace • Requests to get the EventProducer objects belonging to a given trace, respecting the given RT n°427 criteria :

• Get the event producer, given the type and a local identier.

• Get the all the event producers of a given type.

• Requests to get the Event objects belonging to a given trace, respecting the given criteria :

• Get all the events of a given CPU.

• Get all the events of a given type.

• Get all the events whose type is among the ones specied.

• Get all the events with a given producer.

• Get all the events whose producer is among the passed ones.

• Get all the events whose timestamp is included in the specied interval.

• Get all the events whose timestamp is included in one of the specied intervals.

• Get all the events of a given type, for which given parameters have given values.

• Get all the events of a given type, for which given parameters have given values and whose timestamp belongs (at least) to one of the intervals specied.

• Get all the events whose type is among the ones specied, whose timestamp belongs (at least) to one of the intervals specied and whose producer is among the one specied.

• Requests to get the AnalysisResult objects related to a given trace :

• Get all the analysis results produced by a tool.

• Get all the analysis results produced by a tool and of a given type. • Request to get the AnalysisResultData object related to a given analysis result.

Example Figure 17 shows an example of usage of the ITraceSearch interface. In this example rst we get the Trace object corresponding to a given DB name. Then we search for all the context switch events of this trace, where the old PID is 1203 and the new PID is 1205.

Fig. 17 Search interface usage example

The com.inria.soctrace.lib.search plugin oers also an utility class (Printer) providing methods to print collections of data-model objects, as returned by the search interface methods.

The Printer class oers also a method (selectResult()) to interactively browse the analysis results saved in the database, in order to visualize them in a simple, textual form. The analysis result browsing is performed according to the following steps :

• First select the trace where the analysis has been performed (e.g. trace imported on date x ). • Then select the tool performing the analysis (e.g. analysis tool y).

• Then select the type of result produced by that tool (e.g. searching, grouping, etc.).

• Finally select the result instance of that type (e.g. grouping performed on date z ). Inria

Utilities

The com.inria.soctrace.lib.utils plugin provides some utility classes, useful for developing client applications interacting with the SoC-Trace Library. The classes currently present are the following :

• IdManager : this class can be used to manage sequential IDs for model entities. In fact the burden of setting the ID values to the elements of the model (for the storage with the relational database representation) is currently up to the library-user : at the application level is in fact convenient to be aware of the IDs in order to manage objects eciently (e.g. using maps of objects).

• Conguration : this is a Singleton [START_REF] Gamma | Design Patterns : Elements of Reusable Object-Oriented Software[END_REF] that wraps the SoC-Trace infrastructure conguration le (.soctrace.conf, located in the user directory). The class provides an enumerate (SoCTraceProperty) which contains the dierent properties dened in the conguration le and a getter method that allows the user to access such properties.

• Portability : this class provides some basic functionalities to ensure the portability of the infrastructure on both Unix and Windows systems.

• DeltaManager : simple class that can be used to measure time intervals, for example to monitor execution times.

• HeapMonitor : utility class providing facilities to measure the size of the used heap in a Java application.

• History : utility class that can be used to log runtime events in a thread-safe way, useful to debug multithreaded Java code without perturbating too much the execution.

Management Tool

The SoC-Trace Management Tool is implemented by two dierent plugins :

• com.inria.soctrace.management.core • com.inria.soctrace.management.ui

The tool implementation is split over this pair of plugins in order to decouple what is related to visualization (UI) from what is related to functionality. Currently both plugins are very simple because of the prototype-nature of the tool itself.

Core

The core plugin (com.inria.soctrace.management.core) provides basic functionalities to the UI plugin. It encapsulates the SoC-Trace Library functionalities needed to provide services to the end user. For the moment being the main classes provided are :

• SoCTraceManagementConstants : it stores system level constants.

• SoCTraceManager : it provides the implementation of the operations accessible from the UI.

• ToolExecutionManager : it provides a simple interface to launch an external command as an Eclipse Job.

Ui

The UI plugin (com.inria.soctrace.management.ui) provides the graphical elements that form the SoC-Trace infrastructure user interface. For the moment being it contains classes for :

• UI constants • The JFace [START_REF] Jface | [END_REF] actions and dialogs for the operations described in section 3.3.

RT n°427 External Tools

In order to test and use the infrastructure with real use cases, we developed some external tools. First of all, to import real-life traces into the infrastructure, we wrote a parser for the KPTrace format (see section 5.1). Then, to test the dierent functionalities of the infrastructure, we developed also a simple test tool, described in section 5.2.

KPTrace Importer

This parser is simpler than the one provided by STMicroelectronics [16], since it contains very little semantics and is written using several simplications. Typically, only a subset of event types is supported and no link is created between sibling events. Nevertheless the tool is useful since it allows the storage of traces with a real-life format into the SoC-Trace infrastructure and shows a possible usage of the SoC-Trace Library in order to write a Java importer.

Parser architecture

The KPTrace Importer is written as a normal Java program, using the SoC-Trace Library. This tool (KpParserTool) can be exported as an executable jar in order to be registered to the infrastructure tool registry. In the following the main classes of the tool are described.

• KpParserArgs : class containing the command line parameters necessary to the parser.

• KpRecord : simple class to store the raw information contained in a single raw-trace line.

• KpConstants : KPTrace parser constants (e.g. event producer types).

• KpParser : it is the actual parser class, which performs the parsing of all trace les in order to put them in the DB format. It uses the following utility classes to perform its job : • KpEventProducerManager : manages EventProducer objects, for KPTrace specic event producer entities.

• KpTraceInfoManager : manages the Trace element SDP, providing the predened Tra-ceType with the predened trace parameter types. It provides also parsing functionality to ll the corresponding Trace and TraceParam objects.

• KpParserLauncher : open the System DB, creates the new Trace DB and launches the KpParser. At the end of parsing operations, commits all the changes to the databases.

• KpParserTool : it is the class containing the main method of the parser. This method simply handles command line arguments, checking them and then traslating them into an instance of the KpParserArgs class, which is then passed to the KpParserLauncher.

Inria

Test Tool

In order to test and debug the SoC-Trace infrastructure, we developed a Test Tool, which provides several batteries of tests for the dierent functionalities. Basically the tool provides several classes, each providing dierent methods to test a specic part of the infrastructure. The main class of the tool allows the user to set up a working environment (creation of the System DB and import of sample traces) and to enable or disable the dierent tests on such environment.

Currently we developed test classes for the following macro-areas of the infrastructure :

• low level queries using the com.inria.soctrace.lib.query plugin • high level search requests using the com.inria.soctrace.lib.search plugin • analysis results saving • simple trace processing

In addiction to the possibility to produce and save sample analysis results, the Test Tool allows the user to interactively browse through the analysis results saved into the database, using the result browsing method provided by the Printer class (see 4.1.4). We nally observe that the source code contained in the Test Tool, besides oering testing functionalities, provides also a rich set of code snippets, useful for application developers aiming to add a tool to the SoC-Trace infrastructure.

RT n°427 Performance Evaluation

In this section we present the rst performance evaluation results we obtained on the SoC-Trace infrastructure prototype implementation. To get these results we used both the KPTrace Importer (section 5.1) and some simple ad-hoc programs, written to test specic features of the SoC-Trace Library (section 4.1). The machine used to perform our performance evaluation tests has the following characteristics :

• RAM : 4 GB @ 1066 MHz • CPU : dual-core @ 2.40 GHz • OS : Fedora 16, 64 bit

The MySQL database is used with the InnoDB engine, with auto-commit disabled and all the other conguration parameters left with their default values. The version of Eclipse used is the 4.2.0 (Juno).

Trace DB size

First of all we studied the relation between the size of the raw trace and the corresponding Trace DB, in order to see how much overhead is added by the relational representation of data.

We used raw traces (KPTrace format) whose size ranges from 10 kB to 100 MB and we computed an increase factor as the ratio between the Trace DB size and the raw trace size. Figure 18 shows the Trace DB size obtained, while Figure 19 shows the above mentioned increase factor. From the second histogram, we can note that, as expected, for small traces the overhead is huge, with the DB size more than 35 times bigger than the raw trace. Increasing the raw trace size, the overhead decreases until it reaches an asymptotic value, with an increase factor included between 3 and 4 times. We note that for all trace size values the greatest percentage of time is spent in writing into the database. We observe that for smaller traces the parsing time percentage is higher compared with the parsing time percentage of bigger traces, since there is a certain amount of time spent parsing the processes (event producers) created during the execution traced : being this number of processes constant for all traces, the time spent for this parsing operation has a bigger weight on smaller traces. Being the write operation the most expensive one, we shall investigate the problem in order to improve writing performance.

Buered reading

We studied the eect of a buered reading to retrieve the events from the database. In each experiment we measured the time needed to retrieve from the database a total of 100000 events, using the EventQuery class (section 4. Continuing to increase the page size the time needed to retrieve the events does not change signicantly.

Complex parameters queries

Finally we performed complex queries using the ITraceSearch interface (section 4.1.4), in order to see how increasing the number of SDP-parameter-conditions involved in the queries aects requests duration. For this purpose, we used a trace containing 100000 events, performing queries concerning the Event-SDP tables, with a variable number of SDP-parameter-conditions (parameter = value) linked by the AND logical operator. The number of events of the result is always the same for each conguration (for each number of dierent parameter-conditions). The number of parameter-conditions used ranges from 1 to 50. We note that the amount of time needed to perform the requests increases linearly with the number of parameter-conditions, meaning that there is no visible issue in memory management and the system scales well. It will be interesting to try to optimize the system in order to decrease the slope of the curve, for example using custom DB indexes on the SDP tables.

Future Works

The SoC-Trace infrastructure described in this document is a rst prototype which will evolve in the near future. In this section some of the main works that we are planning are described.

Database architecture

As described in section 3.1.2, currently the database has a distributed architecture, with a single System DB and several Trace DBs. This has been done basically for scalability reasons.

However, from a logical point of view, all Trace DBs have the same schema. Furthermore, each new trace added to the infrastructure needs the creation of a new database. These observations made us think about a centralized solution, with a single database that stores all the information, without suering from the single-DB issues discussed in 3.1.2. Instead of replicating all the database tables for each trace, we can simply replicate only the tables that contain specic-trace raw information : EVENT, EVENT_PARAM and EVENT_PRODUCER tables. Obviously, for each trace, these tables shall have a dierent name : for example there can be a sux with the trace ID in the name of the table (e.g. EVENT_1). Like this, when a new trace is imported into the infrastructure, only these three tables shall be created and not a whole database. This solution has the additional advantage that it is no longer necessary to rewrite the trace format description (EVENT_TYPE and EVENT_PARAM_TYPE table information) for each trace of a given type : it is enough to write the format once, then all the trace of that format can refer the same event type and event parameter types. For these reasons we started implementing Inria a centralized version of the database architecture, in order to better compare the pros and the cons of the two dierent solutions to nally choose the best one.

Analysis result

The current data-model is designed to support single-trace analysis results, however future analysis tools will be able to perform complex, multi-trace, analyses. For this reason, a crucial enhancement for the infrastructure will be the support for multi-trace analysis results. This enhancement can be done either keeping the distributed DB architecture or using the centralized DB architecture described in 7.1. In the former case, we can extend the System DB schema in order to save multi-trace analysis result. In the latter case, we simply need to add a new table, mapping the analysis results with the traces involved in the analysis. Furthermore, we are already thinking about adding new predened types of analysis result, like for example Graph Results, which could be useful to represent Bayesian networks.

Tool management

A possible point of improvement for the infrastructure is to enhance the tool management features. First of all, the SoC-Trace Management Tool should be enhanced in order to provide support for workow denition. It should be possible for a user to dene a trace-managementworkow in order to accomplish a specic goal. For example a possible workow could be the following : import a raw trace using this importer, perform a pattern mining analysis with this analysis tool and nally visualize the saved results with this visualization tool.

Then it will be interesting to explore the possibility to add specic support for tools written as plain Eclipse plugins and not necessarily as external applications. This will bring the advantage of making the tool integration easier and will let the tools use to the greatest extent Eclipse functionalities. As we said, now only generic external tools are managed, storing them into the TOOL table, which acts as a tool registry. Eclipse has actually a built-in registry mechanism for plugin management, that automatically recognizes and loads (if necessary) the requested plugins.

In order to have an integration between the two kinds of tools, we should be able to keep the advantages of Eclipse plugins automatic discovering and loading, while preserving the possibility to manage non-Eclipse tools.

Other improvements

We are planning to do some implementation enhancements in order to make the SoC-Trace Library richer and easier to test. First of all we plan to add new Visitor classes to the com.inria.soctrace.lib.storage plugin, in order to support other common DB operations, like the update or the delete of an existing data-model entity. Then we want to improve the test tool, making it easier to add new tests and possibly adding an installation-checking utility, able to check if the SoC-Trace infrastructure has been correctly installed.

Conclusions

In this document we described the rst prototype of the SoC-Trace infrastructure. After clarifying the objectives of the project and the infrastructure, we described both the system and the software architecture of the prototype, showing how the solutions are a solid starting point for the fulllment of the desired goals. We also described some external tools we developed in order to start using the prototype with concrete use cases. We provided some rst performance RT n°427

Fig. 1

 1 Fig. 1 SoC-Trace Infrastructure Architecture

Fig. 3

 3 Fig. 3 Multi-Trace DB architecture

Fig. 4

 4 Fig. 4 Self-Dening Pattern (SDP)

Figure 5 Fig. 5

 55 Figure 5 shows both System DB and Trace DB database schemas, using the Crow's Foot notation.

Fig. 6

 6 Fig. 6 Trace DB : raw trace data

  tool the freedom of dening a result format and saving the corresponding values. This kind of result is therefore implemented using the SDP. A tool can dene an annotation type, specifying the corresponding parameter types. Then the tool can create concrete annotation instances of such type, computing the parameters values. An analysis tool, in a single analysis, can dene several annotation types and for each type can save several concrete annotation instances. For example, a tool can dene an annotation type representing a memory statistic, being described by two parameter types : memory used by function X and memory used by function Y. Then the tool can compute for each CPU the values for such parameters and save them in dierent annotation instances (one for each CPU).

Fig. 9

 9 Fig. 9 Dialog for creating the System DB

Fig. 10

 10 Fig. 10 Dialog for registering a new tool to the infrastructure

Fig. 11

 11 Fig. 11 Dialog for importing a new trace into the infrastructure

4. 1

 1 Java interface to the DB

•••Fig. 12 Event

 12 Fig. 12 Event SDP UML diagram

  Fig. 13 Analysis results class diagram

  interface. The user can specify what kind of concrete classes is interested in storing in the cache and then he can save the objects of those classes. This cache is actually used in both DBObject concrete classes to store the ElementType and ElementParamType objects for Trace and Event SDP.• ModelVisitorThis class implements the IModelVisitor interface. It is an abstract class providing base RT n°427

Fig. 14 Saving

 14 Fig. 14 Saving Event objects into the DB

  Fig. 15 Condition-classes UML diagrams

Fig. 16

 16 Fig. 16 EventQuery example

•

  KpEventFormatManager : manages EventType and EventParamType objects for the specic KPTrace format. This class, starting from an intermediate description of the format, stored in the KpEventFormatDescription singleton, builds a map where each event type mnemonic is linked to the corresponding EventType object. The intermediate description stored in the KpEventFormatDescription singleton is a list of strings with the following format : <event_type_mnemonic> : <par0> <type0>, <par1> <type1>, [...] For example, for the context switch event it could be : CS : OLDPID INTEGER, NEWPID INTEGER The use of such generic intermediate format makes the importer code easily reusable for other trace formats.

  Fig. 18 Trace DB size

Fig. 19

 19 Fig. 19 Database overhead

Fig. 20 Fig. 21

 2021 Fig. 20 Time needed to import KPTrace traces into the infrastructure

1 . 3 )

 13 Fig. 22 Time needed to read a given number of events using dierent buer size

  For each conguration we performed 20 runs. The results are shown in Figure23.

Fig. 23

 23 Fig. 23 Time needed to perform a request varying the number of SDP-parameter-conditions

  CS and the corresponding ID is 3. This event type is described by two event parameter types, the OLDPID and the NEWPID, both typed INTEGER. So in the EVENT_PARAM_TYPE table we have the corresponding two lines, where the EVENT_TYPE_ID attribute is 3 and the specic IDs of the parameter types are respectively 14 and 15. Coming to the EVENT table, the <timestamp> value (227.537525) of the trace line is used to ll the predened attribute with the same name, the EVENT_TYPE_ID is again 3 and the ID is 9. The values given to the other attributes of the EVENT table depend on the context when the event was produced (what process, what CPU, etc.). Finally in the EVENT_PARAM table we nd two lines, corresponding to the two parameter types describing this event. Both lines have the EVENT_ID set to 9.

	EVENT_TYPE ID NAME .. .. 3 CS .. ..	ID .. 14 15 ..	EVENT_PARAM_TYPE EVENT_TYPE_ID NAME .. .. 3 OLDPID 3 NEWPID .. ..	TYPE .. INTEGER INTEGER ..
	ID EVENT_TYPE_ID	EVENT_PRODUCER_ID	TIMESTAMP CPU PAGE
	..	..			..	..	..
	9	3		54	227.537525	0	0
	..	..			..	..	..
				EVENT_PARAM
	ID	EVENT_ID		EVENT_PARAM_TYPE_ID	VALUE
	..	..		..		..
	37	9		14		0
	38	9		15		21
	..	..		..		..

Fig. 7 Example of event importing

The event type mnemonic (CS) is used to ll the EVENT_TYPE table : the NAME attribute is The line corresponding to the OLDPID has the EVENT_PARAM_TYPE_ID set to 14 and the RT n°427 VALUE set to 0, the other line (NEWPID) has the EVENT_PARAM_TYPE_ID set to 15 and the VALUE set to 21.

G.Pagano & V.Marangozova-Martin

This research is supported by the FUI Project [1]

evaluation results, useful to have a critical view on the technical choices done so far. Finally we discussed some of the future works we are planning to do in order to get an enhanced version of the infrastructure. The possibility to easily use the infrastructure with real-life traces, concrete analysis and result saving, showed that the proposed data-model, though being open to improvements, is actually generic enough to deal with arbitrary formats and non-trivial analyses. On the other side, performance evaluation results showed that there is room for enhancements in order to make the infrastructure more ecient. Our future eorts will be therefore on the improvement of both functionalities and performance.

Inria

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES