Emilie Balland

Paul Brauner

Term-graph rewriting in Tom using relative positions

In this paper, we present the implementation in Tom of a de Bruijn indices generalization allowing the representation of term-graphs over an algebraic signature. By adding pattern matching and traversal controls to Java, Tom is a well-suited environment for defining program transformations or analyses. As some analyses, e.g. based on control flow, require graph-like structures, the use of this formalism is a natural way of expressing them by graph rewriting.

Introduction

Program transformation and graph rewriting are strongly related [START_REF] Lacey | Imperative program transformation by rewriting[END_REF]. Indeed, although the structure of a program may be represented by a tree, informations about its execution like data dependencies or control flow are naturally expressed by data-structures inherently using cycles or subterms sharing, in other words by graphs. More precisely, since these graphs are oriented and labelled over an algebraic signature, such transformations are described within the framework of term-graphs [START_REF] Plump | Handbook of Graph Grammars and Computing by Graph Transformation[END_REF]. There exists several definitions of term graph rewriting, category-theory oriented [START_REF] Kennaway | On graph rewritings[END_REF][START_REF] Löwe | Algebraic approach to single-pushout graph transformation[END_REF], equationally oriented [START_REF] Ariola | Equational term graph rewriting[END_REF] or implementation-oriented [START_REF] Barendregt | Term graph rewriting[END_REF].

Since 2001, the Protheo team is developing the Tom system [START_REF] Moreau | A Pattern Matching Compiler for Multiple Target Languages[END_REF], whose main originality is to be built on top of an existing language Java. Tom provides pattern matching facilities to inspect objects and retrieve values. Moreover, the rewriting steps can be controlled using a powerful strategy language. The main application of the language being program transformation and code analysis, we were interested in extending the Tom language for supporting term-graph transformations.

In this paper, we introduce the notion of relative position inspired from the de Bruijn indices as a way to express paths between two subterms. Then we present an implementation of term-graphs based on this formalism. As Tom provides rewriting strategies, integrating such structures in the language offers strategic graph rewriting for free. After introducing the notion of relative positions, we will explain how the language can be extended to offer facilities for strategic graph rewriting. Finally, we will illustrate the use of this extension by an implementation of lambda-calculus normalization.

Term-graph representation

Our goal is to represent term-graphs on top of the term rewriting theory with the fewer possible modifications to this formalism to take advantage of the existing result and tools, namely Tom. The main idea of this paper is to raise the notion of position to the level of first-order terms by extending algebraic signatures with an infinite set of constants representing positions. This allows for the description of terms containing some "pointers" to subterms of themselves. As an example, the term s(a, 1) defined over such a signature denotes a term whose second child references the first-one.

The main issue of this representation is that it is context sensitive. For instance, the position 1.2 references the subterm a in f (s(1.2, a)), but s(1.2, a) in f (f (s(1.2, a)))). This raises the idea of relative positions describing paths inside a term to the referenced subterms. The previous example would then be written f (s(a, -1.1)), where -1 indicates one backward step inside the term. This can be seen as a generalization of de Bruijn indices extended to the count of all function symbols, not only abstractions.

In this section, we define more formally this notion of relative position and terms with references before we present an implementation aimed to be used by Tom. We finally discuss the relation between this formalism and term-graphs as well as the associated technical solution.

Terms with references

As usual, a position is a finite sequence of natural numbers. The subterm u of a term t at position ω is denoted t |ω , where ω describes the path from the root of t to the root of u. To emphasize the difference with relative positions, we will sometimes refer to positions as absolute positions.

Let us first define relative positions along with their meaning. We note n, p the elements of Z * and ω r , ω ′ r , . . . the elements of Rpos. Definition 2.2 (Referenced subterm) Given an absolute position ω and a relative position ω r , the absolute position accessed by ω r from ω is written pos(ω, ω r ) and is defined as follows:

• if ω r = Λ, then pos(ω, ω r ) = ω
• else, there exists p ∈ Z * and ω ′ r ∈ Rpos such that ω r = p.ω ′ r and 2

• if p > 0, then pos(ω, ω r ) = pos(ω.p, ω ′ r ) • if p < 0 and if there exists ω ′ and ω ′′ such that ω = ω ′ .ω ′′ and |ω ′′ | = -p, then pos(ω, ω r ) = pos(ω ′ , ω ′ r ) It is undefined everywhere else.

We note t |ω,ωr the term t |pos(ω,ωr) for every ω and ω r such that pos(ω, ω r ) and t |pos(ω,ωr) are defined. We name it the subterm of t referenced by ω r from ω.

Intuitively, ω r describes a path back and forth inside t from ω to t |ω,ωr . For example, the relative positions -1.1 and -2.1.2.-1.1 reference the same subterm a of f (s(a, b)) from the position 1.2.

We can now define the notion of first-order terms with references. It only consists in extending an algebraic signature with an infinite set of constants denoting relative positions.

Definition 2.3 (Term with references)

For every set of first-order terms T (F, X ), the corresponding set of terms with references T ref (F, X ) is the set T (F ∪ Rpos, X ) where elements of Rpos have arity 0.

As an example, f (s(a, -1.1)) is a term with references of T ref ({f, s, a}, ∅). By abuse of notation, we will say that "-1.1 references a in f (s(a, -1.1))", without specifying it occurs at position 1.2.

Problems will inevitably occur when considering undefined relative positions. We define therefore validity as follows. We also forbid terms containing relative positions referencing relative positions. Definition 2.4 (Term with references validity) A term with references t ∈ T ref (F, X ) is valid if for every leaf ω r = t |ω such that ω r ∈ Rpos, t |ω,ωr is defined and is not in Rpos.

Implementation of terms with references

Let us now see how this formalism can be transposed to the Tom language. One characteristic of Tom is its data-structure independence. A term can be represented by any Java object as long as the user provides a mapping to see these objects as trees. For easier development, it comes up with a language called Gom [START_REF] Reilles | Canonical abstract syntax trees[END_REF] which automatically generates from a signature the Java implementation and the mapping. The resulting implementation is efficient in space and time (constant time terms equality test) because of maximal subterm sharing. Readers must pay attention to the difference between the maximal sharing and the notion of sharing in term-graphs. In our case, the maximal sharing is only at implementation level and does not lead to sharing at the term level. A Gom signature contains sorts and their constructors. For example, the signature below defines two sorts A and B along with their constructors.

A = a() B = g(A) | f(A) | s(A,A)
With this signature, we can construct the terms a(), f(a()) or g(f(a())) for instance. From this description, Gom generates a Java class hierarchy attaching an abstract class to each sort, and a class extending this sort class to each constructor.

Our goal is to generate an extended signature for terms with references from an initial Gom one. To achieve this, for every sort T of a Gom module, we generate a new constructor of rank posT(int*). The notation * is the same as in [3, Section 2.1.6] and can be seen as a family of constructors with arities in [0, ∞[. The previous example is extended in this way:

A = a() B = g(A) | f(A) | posB(int*) | s(A,A) | posA(int*)
As an example, we can now build the extended term s(-1.2.1, f (a)) with the following syntax: s(posA(-1,2,1),f(a())). Then posA(-1,2,1) references a() in the term s(posA(-1,2,1),f(a())).

This type of terms with references using explicit relative positions constitutes a first extension of a Gom signature. In order to ensure type-preservation and reference correctness, a second representation level consists in expressing references with the help of labels. This notion of labelling can be seen as an implementation of the addressed terms presented in [START_REF] Dougherty | Addressed term rewriting systems: Application to a typed object calculus[END_REF]. We have added new constructors to facilitate the use of labels and functions to transform a term with labels into the low-level representation. For every sort T, we generate two constructors. The constructor labT(String,T) enables the user to label a term with a string and refT(String) to reference a labelled term. Thus the term s(refA("l"),f(labA("l",a()))) corresponds to the lowlevel term s(posA(-1,2,1),f(a())). This notion of labels can be seen as syntactic sugar for hiding positions to users in order to avoid bad manipulations. Thereby, the constructors posT should be private so that users can only construct terms with references by label usage. We provide functions which generate the corresponding low-level terms after verifying that each refT corresponds to a labT of identical sort. This transformation is itself described using strategic rewriting introduced in 4.

Correspondence with term-graphs

Let us see now how a representation of term-graphs can be obtained from the terms with references introduced above. To ensure a bijection between termgraphs and their representations, we need to establish equivalence classes between terms with references. For example, s(a, -1.1) and s(-1.2, a) should be equivalent. They both correspond to the term-graph rooted by s whose two children correspond to the shared subterm a. Moreover, we noticed that several relative positions may reference the same subterm from a given position. Hence, we define canonical relative positions. Definition 2.5 (Canonical relative position) Let ω 1 , ω 2 be two absolute positions, the canonical relative position cpos(ω 1 , ω 2 ) from ω 1 to ω 2 is the smallest relative position with respect to the length such that pos

(ω 1 , cpos(ω 1 , ω 2 )) = ω 2 .
Let us remark that cpos(ω 1 , ω 2 ) = q.ω ′ where ω ′ ∈ (N * , .) and q ∈ Z * ∪{Λ}. We can now define the canonical form of terms with references using an order on absolute positions.

Definition 2.6 (Canonical term with references)

Let ω 1 = n 1 .ω ′ 1 or Λ and ω 2 = n 2 .ω ′ 2 or Λ be two absolute positions, ω 1 < Ω ω 2 ⇔      ω 1 = Λ or n 1 < n 2 or n 1 = n 2 and ω ′ 1 < Ω ω ′ 2
A term t with references is then canonical if and only if t is valid and for every leaf ω r = t |ω such that ω r ∈ Rpos, ω r is canonical and pos(ω, ω r ) < Ω ω.

Typically, contrary to s(-1.2, a), the term s(a, -1.1) is a canonical representation of a term-graph.

The formalism presented all along this section has been implemented through a plugin for Gom which generates an extended signature with new constructors for positions and construction functions which offer different levels of abstractions (from terms with explicit positions to term-graphs with labels). As illustrated by the Figure 1, a user may provide a labelled representation which is not a canonical form and use the provided construction function to normalize it. Whatever the favored level of the user,

s s s f f a a s s s f f a a ref A ref A labA labA "l 1 " "l 1 " "l 2 " "l 2 "
Fig. 1. An example of term-graph and its representation as a labelled term.

the in-memory representation is always based on explicit relative positions. Moreover, due to Gom design and in particular to the maximal sharing, the efficiency in time and space is ensured. For example, the term-graph presented Figure 1 is automatically translated during the construction into the low-level term with positions depicted in Figure 2. The principle of Balland,Brauner maximal sharing is also illustrated by a schematic representation of the heap. After defining terms with references rewriting, we will exhibit in the next two sections how the Tom language offers strategic rewriting of these structures.

Term-graph matching

The originality of the previous approach is that pattern matching on terms with references build upon T (F, X ) is simply defined as pattern matching on terms of T ref (F, X ). There is therefore no need to extend the notion of rewriting, which allows us to reuse existing results and rewriting tools. However, the questions raised by this formalism are situated at another level: we would like the rewrite system to rewrite only valid terms. Giving some non-trivial criterion on rewrite rules implying this property remains an open question for the moment. The next sections of this paper therefore focus on technical aspects of the pattern matching problem implementation.

After introducing the Tom language, we discuss various presentations of graph with references rewriting in this system. Although we cannot statically check that patterns ensure the validity of matched terms, we also propose several solutions to check this property at runtime.

Tom pattern matching

The first mechanism offered by the Tom language is pattern matching on algebraic terms. This feature is similar to the constructs proposed by functional languages like OCaml or Haskell. It is enabled by the %match keyword which allows us to match a subject against some pattern and to get the values of the pattern variables into Java ones:

A term = 's(f(a()),a()); %match(term) { s(x,y) -> { System.out.println( "First child: " + 'x + ", second child: " + 'y ); return 'f(x); } } A subject is then any Java object which is an instance of a class whose description has been provided to Tom via a mapping. This mapping indicates to the Tom compiler how to match some class against a pattern, and how to create new algebraic terms implemented by this class via the ' construct. Here we are using the classes generated by Gom along with their mappings. Tom also supports associative matching, a.k.a. list matching, as well as antipatterns [START_REF] Kirchner | Anti-pattern matching[END_REF] and non-linear matching.

Let us elaborate on the mapping mechanism. It provides an algebraic view of some Java object (e.g. seeing integers as Peano natural numbers, or seeing an XML tree as a term). It is divided into two parts: the destructive part and the constructive one. The destructive part is used by the matching algorithm and its main function is to describe how to query a term about its head symbol and how to get its n th child. For instance, the mapping between integers and Peano naturals would be similar to the following schematic code:

is_zero(n) { n == 0 } is_successor(n) { n > 0 } get_successor_child(n) { n -1 }
On the other hand, the constructive part is used by the compiler to build an algebraic term. It usually consists in calling the constructor of the Java class implementing the term. Although our goal is to work as much as possible on top of classes and mappings generated by Gom, we will punctually adapt some mapping to our needs.

Matching terms with references

Given these language constructs and the terms described in Section 2.2, there are many ways to express matching against patterns with references. As for term construction, patterns can be expressed at low-level using directly positions or by a syntax based on labelling. In each case, it refers to a stated subterm whose position is well-known. To compare two references by value instead of references, we will introduce a deref operator in patterns implemented using Tom mappings.

The simplest way to handle Gom terms with references is to consider the extended signature and perform some standard pattern-matching on it. Since the posT(int*) constructors generate matchable terms, it is possible to write patterns where relative positions are explicitly given. As an example, the Balland,Brauner term represented Figure 3 matches against the pattern s(a(),pos(-1,1)). Notice that this type of pattern denotes exactly the structure of the term: e.g. s(pos(-1,2),a()) would not match the same term. This method allows us to match against any position, even those pointing to an upper term as shown Figure 4. This may still be relevant in case of a procedure carrying some contextual information or fetching the position to perform some computation later. It may also be useful to compare two positions, without knowing the value of the subterms they are referencing. Figure 5 illustrates this situation. Notice however that this is only possible if the two variables have the same height in the term, as we are comparing relative positions. This solution presents two issues: the main one, depicted by Figure 6, is that a relative position may be undefined. These patterns should therefore be considered as a kind of unsafe assembly language for matching terms with references. The second one is that the explicit notation of positions is not mandatory and may be easily avoided with some syntactic sugar.

Thereby we propose to slightly modify the Tom compiler to address them. The first change consists in integrating labels capturing and denoting positions of subterms into the patterns syntax in order to avoid any explicit position matching. As an example, the term represented on Figure 3 would match against the pattern s(x:a(),x). The translation of this kind of patterns to the former one is trivial: each occurrence of a label lab is replaced by the relative position from its position to the position of the subterm labelled by lab.

The second modification aims at reinforcing the patterns safety. As explained in section 2.2, we do not want the user to be able to recover a position by matching the term of figure 3 against s(_,x) for instance.

Balland,Brauner

This can be achieved by inhibiting the generation of mappings for position constructors, so that the matching algorithm fails on such patterns. Another less restrictive way of dealing with the undefined relative positions problem would be to have the patterns similar to s(_,x) match only valid terms. This could be achieved by checking at runtime that every relative position in x references an accessible term. This is easily done with the help of strategies presented in section 4. In both cases, we cannot avoid some modification of the pattern-matching algorithm, thus of the compiler.

The two previous kinds of patterns focus on the positions themselves as matchable objects. Another approach would be to have the patterns express constraints about the value of the referenced subterms. The mapping mechanism presented in Section 3.1 offers the necessary features to achieve this via the writing of an ad hoc destructor. We wrote this deref destructor which acts like a proxy between the pattern matching algorithm and the destructor of the value referenced by a position. As an example, the term represented by It is important to note that the patterns are now an abstraction of the term so we do not match the graph structure anymore. For instance, the two terms of Figure 7 match against the same pattern s(a,s(f(deref(a())),_)). In particular, it is not possible anymore to use non-linear pattern matching in order to check that two positions are referencing the same sub-term, as depicted by Figure 8 which shows the ambiguity of the s(s(deref(x),deref(x)),_) pattern. Again, matching terms with references in this way is not safe. Indeed the s s s s s Fig. 8. deref(x),deref(x) ambiguity subject may contain positions referencing terms above its root. However Balland,Brauner this time, checking the validity of a term does not require any change to the compiler since the test can be transfered to the destructor. The later aborts the matching process by returning false if accessing the pointed term raises an exception.

Matching term-graphs

Contrary to Gom terms with references, the usual term-graph definition does not differentiate two types of children. Therefore, it may be convenient to have the patterns s(x:a(),x) and s(x,x:a()) match either s(a(),pos(-1,1)) or s(pos(-1,2),a()). The normal form mentioned in Section 2.2 enables such a feature: it is sufficient to maintain normalization of both terms at runtime and patterns at compile time to ensure this behavior. It requires some minor changes of the Tom compiler though.

As recalled in Section 2.2, one main application of term-graphs is the representation of subterms sharing in the purpose of gaining space and computation time. However, this structure (the sharing) does not reflect the structure of the represented term (typically a λ-term) and it is therefore desirable to manipulate it modulo this encoding. The basic idea is to interweave deref constructors inside the patterns, so that s(a(),a()) is translated into deref(s(deref(a()),deref(a()))) and thus matches the graph of figure 3. It only requires to confer some lazy behavior to the deref destructor, which should act as if not existing in case of a direct subterm (not a position).

Even if the classical [START_REF] Barendregt | Term graph rewriting[END_REF] representation of term-graphs by a labelled graph is similar to ours, the conditions on rewrite rules are more restrictive (the lefthand side of a rule is limited to trees). For now, term-graph rewriting in Tom is expressed by syntactic term rewriting. Contrary to [START_REF] Barendregt | Term graph rewriting[END_REF], there is no garbage collection phase and referenced subterms can disappear or change, leading to invalid terms. One solution would be to integrate this garbage collection phase in the Tom matching. An other attractive approach would be to implement the formalism presented in [START_REF] Echahed | Narrowing data-structures with pointers[END_REF] where the right-hand side of the rewriting rules consists in a set of actions on the pointers.

Strategic programming with term-graphs

Tom provides a powerful strategy language inspired by ELAN and Stratego. The purpose of strategies is to describe how transformation rules should be applied. In case of terms with references, the strategy language must be extended in such a way that we can traverse them as graphs.

Tom strategy language

Elementary strategies are composed of the two basic strategies Identity() and Fail() as well as type-preserving user-defined rewrite rules specializing Balland,Brauner their behaviour:

%strategy Eval() extends Fail() { visit A { s(x,a()) -> { return 'f(x); } s(x,y) -> { return 'y; } } }
When applied to a node of sort A, a transformation is performed if one of the patterns matches the node. Otherwise, the default Fail strategy is applied.

More complex strategies can be built on top of elementary ones, involving basic combinators introduced in ELAN [7] and extended in [START_REF] Visser | A core language for rewriting[END_REF]: Sequence(s1,s2), Choice(s1,s2), All(s), One(s), etc. We can therefore build strategies such as 'Choice(Eval(),Identity()) which tries to apply Eval() to the current node and returns it unchanged if Eval() failed (i.e. none of the patterns matched the current node).

Besides, the strategy language allows the declaration of recursive parametrized strategies, enabling the definition of higher-level constructs.

For example, the fix-point operator can be expressed by Repeat(s) △ = µx.Choice(Sequence(s,x), Identity()), where µ denotes a recursion operator, x a variable, and s a parameter of the strategy. In Tom, we raised the recursion operator to the object level, allowing the definition of complex strategies in a truly algebraic manner:

Strategy Repeat(Strategy v) { return 'mu(MuVar("x"), Choice(Sequence(v,MuVar("x")),Identity())); } Finally, Gom generates a congruence strategy _f for each constructor f of an algebraic signature. Using the notation s[t] to express the application of the strategy s to the term t, f(s 1 ,...,s n )[f(c 1 ,...,c n )] returns f(s 1 [c 1 ],...,s n [c n ]) and fails if the head symbol of the subject is not f. This allows to perform pattern matching "on the fly" during term traversal.

One noticeable property of strategic programming with Tom is that it is possible to get the current absolute position inside the visited term during a traversal. This allows for instance to collect in one pass the set of reduced forms of a term for a given rewrite system. In our case, we will make use of this feature in the next section to collect the positions of bounded variables occurences under an abstraction.

Extension of Tom strategy language

In order to traverse terms with references, we enrich the strategy language of Tom with one new strategy combinator Ref whose semantics is defined as Balland,Brauner follows:

Ref(s)[t] =    s[t'] if t' is the term referenced by t s[t] otherwise
This new basic combinator can be used everywhere in a composed strategy. One important characteristic of the Tom strategy language is that every composed strategy is itself a term and therefore can be traversed and rewritten. Adapting a strategy term for graphs with references consists in weaving the Ref combinator ahead every elementary strategy inside a strategy term. For example, Sequence(s1,s2) where s1 and s2 are elementary strategies will be rewritten into Sequence(Ref(s1),Ref(s2)).

Application to the lambda-calculus

Let us see now some application of our programming framework through the implementation of a basic λ-calculus interpreter. The graph with references will encode variable bindings, acting as de Bruijn indices, while the strategy language will translate the usual evaluation strategies of λ-calculus.

We work with a minimalist Gom signature:

LT = App(LT, LT) | Abs(LT)
The chosen representation of λ-terms makes use of terms with references by replacing variables with positions pointing to the corresponding binder.

For instance, the term λf.λx.(f x) will be encoded by the Gom term Abs(Abs(App(posLT(-3),posLT(-2)))). This encodes a kind of de Bruijn indices counting not only abstractions but also every node in the syntactic tree of the λ-term.

Let us write a beta strategy wich performs one β-reduction step on a redex. As mentioned in the previous section, it is possible to get the current position inside a visited term during its traversal by a strategy. Thereby, knowing the position of λ inside the visited redex (λx.f a) will allow us to find all the occurences of x in f , i.e. relative positions pointing to λ. The beta strategy then simply consists in four steps when applied to an application (λx.f a):

(i) collecting the position of λ;

(ii) collecting a;

(iii) replacing all the occurences of relative positions pointing to λ by a in f ;

(iv) replacing the redex by the modified f . Assuming we have a mutable structure info (a Java class here) which can store both informations of the first and second steps, this is achieved by the following strategy:

Strategy beta = 'Sequence( _App(Identity(),collectTerm(info)), _App( Sequence( collectPosition(info), _Abs(µx.Choice(substitute(info),All(x)))), Identity()), clean());

We can notice the presence of four user defined strategies: collectTerm, collectPosition, substitute and clean. They respectively perform the four steps described above. Their code is obvious and one line long, except for the substitute strategy which has to compute the absolute position referenced by the current term to compare it with the position of λ stored in info. Then it performs the necessary shifts on bounded variables (relative positions) inside a before returning it. The whole strategy itself is an overlapping of congruence strategies. The µx.Choice(substitute(info),All(x)) construct means that we do not go down further inside the term if the substitution succeeded.

We shall now apply this beta strategy on a λ-term with some evaluation strategy until we reach a fixpoint. beta being a strategy, it can be combined with other strategies to perform reductions. In particular, the TopDown and Innermost strategies respectively encode call-by-name and call-by-value evaluation strategies modulo some fixpoint computation encoded by the provided RepeatId strategy. They are themselve expressed using elementary strategies: TopDown(s) = µx.Sequence(s,All(x)); Innermost(s) = µx.Sequence(AllRL(MuVar(x)),Try(Sequence(s,x)))

Where AllRL applies s to all the childs of the current node from right to left. Substituting s by beta inside one these enables the expected evaluation behaviour.

Let us finally see how a typical use of term-graphs, namely subterms shared evaluation, can be implemented by a slight modification of the previous example.

We now assume that many bounded variables are represented by shared subterms where "shared" is meant in the sense of term-graphs semantics. For example, the λ-term λx.(x x) will be represented by Abs(App(posLT(-2),posLT(-1,1))) instead of Abs(App(posLT(-2),posLT(-2))). The previous beta strategy is then still mainly valid since this modification only affect the situations where the second child of an application is a variable, i.e. a relative position. Hence, changing the line _App(Identity(),collectTerm(info)) by

Conclusion

To the best of our knowledge, we have presented here a new way of representing terms with references which presents strong similarities with the term-graph formalism. Using the Tom language as a programming background, we have discussed the various advantages and drawbacks of such an approach at different levels: memory representation, pattern matching and strategic traversal. We finally presented an application of this framework via the writing of a simple λ-calculus interpreter making an heavy use of strategies.

Although a major part of the presented propositions has been implemented, the solutions requiring a modification of the compiler as described in section 3.2 are still theoretical. The syntactic sugar constituted by the labelled notation is a matter of few lines of code. On the other hand it may be interesting to look closely at an efficient way of checking the validity of references contained by a given subterm at runtime. Another field of investigation would be the writing of Ref strategies aborting infinite loops appearing during the traversal of a graph with cycles. This could be achieved by some map associating counters to visited nodes.

As shown by the last section, this model has interesting applications and opens promising perspectives in terms of program transformation and code analysis. Besides, the normal form described in section 2.2 makes it a solid basis for experimenting transformations on term-graphs in a concise and expressive manner.

c

  2007 Published by Elsevier Science B. V.

Definition 2 . 1 (

 21 Relative position) The set Rpos of relative positions is the monoid (Z * , .) with neutral element Λ where Z * = Z \ {0}.

2 Fig. 2 .

 22 Fig. 2. Generation of relative positions from the labelled representation and maximal subterm sharing in memory.

Fig. 3 .Fig. 4 .

 34 Fig. 3. s(a(),pos(-1,1))

  s

Fig. 5 .Fig. 6 .

 56 Fig. 5. s(x,x)

Fig. 7 .

 7 Fig. 7. deref(a()) ambiguity

Figure 3

 3 Figure3matches against the pattern s(a(),deref(a())). It is important to note that the patterns are now an abstraction of the term so we do not match the graph structure anymore. For instance, the two terms of Figure7match against the same pattern s(a,s(f(deref(a())),_)). In particular, it is not possible anymore to use non-linear pattern matching in order to check that two positions are referencing the same sub-term, as depicted by Figure8which shows the ambiguity of the s(s(deref(x),deref(x)),_) pattern. Again, matching terms with references in this way is not safe. Indeed the

  (),Ref(collectTerm(info))) suffices to adapt the strategy to the new λ-terms representation. This modification is of course relevant in case of a call-by-name strategy.The discussed implementation is available in the Tom subversion repository 1 , under the examples/termgraph path.

Compilation instructions are detailed in the Tom documentation at http://tom.loria. fr/docs.php


Leo Cazin
email: leo.cazin@mines-paristech.fr

The Art of Making Do and the Science of Organizing in Future Health Care

Keywords: French public hospitals, inter-organizational restructuration, Regional Health Agencies, Making do, Regulation

Introduction

For a few years, public hospitals in France and in most of developed countries have had to deal with major issues. New legislations have recently been introduced, such as a prospective payment system (PPS: hospitals are reimbursed depending of the amount of services they provide), which aims at developing "business-like" management models, according to the New Public Management principles (Osborne & Gaebler 1994). Therefore, the dominant institutional logic in healthcare organizations is shifting, sometimes in very short periods of time, from "medical professionalism" to "business-like healthcare" [START_REF] Reay | The recomposition of an organizational field: health care in Alberta[END_REF]. The PPS is a pro-competitive trigger, since hospitals are encouraged to develop their activity in order to generate more income by gaining market shares [START_REF] Moisdon | De l'incitatif économique à la machine de gestion : le cas des établissements de santé[END_REF].

What is more, public hospitals often have to cope with a major problem of medical workforce shortages [START_REF] Kroezen | Recruitment and retention of health professionals across Europe: A literature review and multiple case study research[END_REF], which threatens the existence of some activities in a lot of institutions, particularly in remote areas.

Furthermore, the evolution of medical practices, for instance the ambulatory turning point which consists in reducing, when possible, patient stay in hospitals to less than 24 hours, brings about a series of organizational concerns, as hospitals will be asked to cooperate with different stakeholders about healthcare pathways.

All in all, as in many developed countries, hospitals are pressurized into providing better care at an affordable cost, in a dynamic and uncertain environment, with potentially clashing demands.

In order to generate a transformation of the French public hospitals territory organization, and so as to meet the challenges mentioned above, the French government has implemented a set of tools aiming at fostering restructuration between neighbouring hospitals, thanks to cooperation and merger processes. For instance, a law voted in 2009 provided hospitals with the possibility to cooperate in Territory Hospital Communities.

Private clinics have been dramatically restructured in the past two decades amongst integrated networks, but public hospitals, which have been used to working relatively autonomously, have not followed this process to the same extent in France [START_REF] Delas | L'hôpital public, un nouvel acteur territorial entre aménagement sanitaire et rivalités stratégiques[END_REF]. The results that the government was calling for have not been rather mixed so far. Given this relative failure, the State has decided to step up a gear by making cooperation mandatory. By the end of 2016, all hospitals will have to be part of a Territory Hospital Group. Territory organization of healthcare providers is regulated by Regional Health Agencies (RHA), whose mission is to promote restructuration leading to a better access to healthcare at an affordable cost.

The purpose of this paper is to contribute to the management literature about organizational change implementation in the case of inter-hospital reorganization, by analysing restructuring processes under way in France. The empirical material collected will be used to answer the following research questions:

1. To what extent are inter-hospital restructuring strategies an answer to uncertainty (such as the lack of medical resources) and pro-competitive triggers (e.g. the PPS) they have to cope with? 2. Is the transformation of the French public hospitals territory organisation led thanks to a regulated restructuration process, or is it the result of "making do" bottom-up strategies (sometimes partially unsuccessful) between hospitals?

The study was carried out thanks to two different case studies that analysed interorganizational restructuration strategies in two French public hospital groups. Qualitative data was collected mainly by carrying out 30 semi-structured interviews with different stakeholders involved in the processes.

This paper shows that even though the necessity of performing inter-hospital restructuration in globally accepted by the different stakeholders, the conditions to implement this process raise a number of concerns. The role and missions of the regulatory institutions is not always clearly defined. Moreover, because of multiple factors that will be presented, it may be observed that inter-hospital restructuration is more often the result of "making do" bottom-up strategies, with uneven results, rather than that of a rational and wider regulation.

Literature review

Organizational change in Healthcare systems has been the focus of many research articles in the past few years. Several scientific authors account for the strong systemic inertia by pointing out professional group logics, which often are obstacles to the implementation of organizational change in healthcare, characterized by shifts in dominant institutional logics imposed by new legislations. For instance [START_REF] Reay | The recomposition of an organizational field: health care in Alberta[END_REF] analyse the restructuration of the Health Care field in Alberta Canada, after a reform that promoted "business-like" management models at the expense of the "medical professionalism" logic that used to be dominant. [START_REF] Battilana | Change Agents, Networks and Institutions : A Contingency Theory of Organizational Change[END_REF] explain the conditions that foster the adoption of change based on the examples of the transfer of clinical tasks from physicians to nurses and of policies challenging the dominance of hospitals over different healthcare providers, in the British National Health Service.

Inter-hospital restructuration (from cooperation to more radical change such as mergers) has been analysed in European countries, with divergent conclusion about their impact on reducing expenditure [START_REF] Kristensen | Economies of scale and scope in the Danish hospital sector prior to radical restructuring plans[END_REF], Bengt 2008). In France, the failure of public hospitals mergers in the 1990s encouraged the government to promote cooperation, as a softer restructuring process that is more easily accepted by stakeholders [START_REF] Louazel | Coopérations hospitalières : entre incitation réglementaire et intérêt stratégique à agir[END_REF].

However, corporatization of public healthcare providers observed in the past two decades [START_REF]Full-cost pricing rules within the National Health Service internal market accounting choices and the achievement of productive efficiency[END_REF] which was implemented in order to foster performance, also produced undesired effects such as a difficulty to cooperate among providers, who turned out to be competitors. In order to make up for this, spheres of cooperation such as inter-hospital networks have been created, thus resulting in coopetition situations. This concept of coopetition, describing the coexistence of cooperative and competitive strategies, was developed by [START_REF] Nalebuff | Coopetition: A Revolutionary Mindset That Combines Competition And Cooperation[END_REF] and has been observed between neighbouring hospitals [START_REF] Baretta | The functioning of co-opetition in the health-care sector: An explorative analysis[END_REF] as well as between hospital networks [START_REF] Peng | The Coexistence of Competition and Cooperation between Networks: Implications from Two Taiwanese Healthcare Networks[END_REF]. Some research has been carried out in order to analyse the role of regulatory bodies on inter-hospital restructuring. For instance, Mur-Veeman et al. (1999) analysed the ineffective role of the Dutch government in implementing integrated care in local contexts. [START_REF] Reay | The recomposition of an organizational field: health care in Alberta[END_REF] observed the new dominant role of Regional Health Agencies in restructuring healthcare in Alberta. The focus of this paper is to contribute to this topic by analysing, in the case of inter-hospital reorganization processes in France, the interplay between regulation bodies and hospital stakeholders.

Methodology

The empirical analysis is based on two case studies. Two groups of public hospitals, relatively advanced in terms of inter-organization reorganization, have been studied in two different French regions.

The first one is a Territory Hospital Community located in southern France, in a region unevenly populated on the territory, with remote hospital facing serious medical workforce shortages. This community has gathered since 2011 5 hospitals, 2 of which having merged since then.

The second one is a three-hospital group based in the densely populated periphery of a major city. These hospitals are managed by the same team and are working on a merger project in the short term.

Studying of both situations makes it possible to draw comparative elements with regard to the implementation of inter-hospital reorganization in two different contexts, characterized by different levels of integration (from inter-organizational cooperation to mergers). Both hospital groups are composed of a core hospital, relatively large and in a decent financial situation, and of periphery hospitals, smaller and more prone to economic difficulties and medical resources shortages.

The qualitative material collected is mainly based on 30 semi-structured interviews with different stakeholders involved in the inter-organizational restructuration processes: hospital managers, doctors, as well as members of the Regional Health Agencies.

In order to complete data collection, the analysis of internal documents dealing with this issue, and the observation of a working group about a project of hospital merger, have been carried out.

Data analysis helped the author to identify in the stakeholders' words the reasons mentioned to justify the necessity to perform inter-hospital restructuration, the hardships to this movement, as well as the different roles (regulation performed by the RHA as well as bottom-up initiatives) and points of view of the actors.

Results

Stakeholders see inter-hospital restructuring as a way of dealing with medical workforce shortages in some medical specialties (e.g. anaesthesia and surgery), and also as a means of building a stronger visibility and thus competitive position in market areas where private clinics are leaders. This is particularly interesting since hospital incomes directly depend on their activity and therefore on their market shares. Restructuring in both fields is mostly carried out in a soft way by mutualizing teams between the core hospital (relatively attractive and autonomous in terms of medical workforce) and periphery hospitals facing recruitment and retention concerns. This strategy brings about a better access to public healthcare on the territory, as well as the construction of medical networks from primary to secondary care between periphery hospitals and the core hospital. It also helps to achieve better quality services thanks to teamwork between young physicians and experienced professionals.

Thanks to the data collected, it can be inferred that inter-hospital restructuring in both situations results from "making do" bottom-up strategies, rather than top-down rational regulation, because of the three following factors:

1. The means of action used by hospital stakeholders coping with uncertain and dynamic environment are limited. For instance, investments granted by RHAs are restricted, and therefore cooperation or merger processes cannot always be implemented with the construction of a new building or with the purchase of a new expensive piece of equipment. Similarly, he lack of medical resources problem is only partially, locally and temporarily dealt with, thanks to teams mutualisation which sometimes appear to be stopgap measures: what is needed according to hospital managers is a national policy to regulate the distribution of physicians on the French territory, as well as national improvements to the attractiveness of public hospitals (vs. private clinics): "There is no clear vision of medical demography in the future in our region" (Hospital manager).

2. Some stakeholders are reluctant to promote inter-hospital restructuring because they see this as a threat, as a potential loss of power. Hospital leaders in favour of change therefore have to make do with these positions that may slow down and reduce the scope of integration processes. For instance city mayors still play an important role in decision-making processes of this kind [START_REF] Delas | L'hôpital public, un nouvel acteur territorial entre aménagement sanitaire et rivalités stratégiques[END_REF]. Medical communities in periphery hospitals may see restructuring and cooperative processes as threats to the independence of their institution ("We do not want to be absorbed by the core hospital", doctor in a periphery hospital). Restructuring strategies, when carried out, are therefore defensive strategies, they are implemented because no alternative solution can be considered, with a certain level of distrust amongst stakeholders.

3. RHAs surprisingly enough do not always play a leading role in inter-hospital restructuring, although they do have some tools, such as the ability to impose the creation of a Territory Hospital Community. There turns out to be uncertainty about the definition of leading stakeholders supposed to run the restructuring project.

Hospitals therefore also have to make do with this situation when implementing interorganizational change: "The RHA does not want to do the first step, to take the lead in the process. They are extremely unadventurous and want to let us decide how to sort things out" (General Hospital Manager). This conclusion applies to both hospital groups analysed, for instance with regard to the perimeter definition of the hospitals to be involved in each reorganization process.

Discussion/Conclusion

In this paper we showed that inter-hospital restructuring strategies could be seen by stakeholders as positive ways to meet the challenges that French public hospitals are facing.

However, these processes are often conducted with a bottom-up "making do" approach, with uncertainty with regard to the regulation role that RHAs should play and the autonomy that hospitals should have.

The implementation of Territory Hospital Groups in the near future in the whole country, by the end of 2016, is a milestone showing the government's willingness to speed up restructuring processes thanks to a stronger territory regulation led by the RHAs. It might nevertheless prove unsuccessful if some regulation policies on the national scale are not implemented, such as policies aiming at softening strong differences in the distribution of medical resources on the territory, as was the case in other countries such as Germany.


V N Pilipchuk
email: pylyp@me1.eng.wayne.edu

Impact modes in discrete vibrating systems with rigid barriers

Keywords: Normal modes, Impact systems, Non-linear localization, Non-smooth transformations

A class of strongly non-linear vibrating systems composed of linear elastic structures under absolutely rigid constraints condition is considered. Impact mode exact solutions are expressed through a saw-tooth time argument and, as a result, represented in a closed unit form. Based on this special representation, su$cient conditions of existence and also non-existence for the impact modes are formulated and interpreted on the spectral axes. In particular, it was shown that impact modes exist when their basic frequencies are shifted into the right small neighborhood of any natural frequency of the linearized (no barriers) system. The frequencies of the localized impact mode solutions are located at the right of the linear spectrum and have no upper b oundary.

Introduction

In many practically important cases, the displacements of a vibrating mechanical system can be spatially bounded by rigid barriers. This can be caused by the system design and/or some gained clearances due to deterioration of joints. Both situations were considered by many investigators. The related engineering applications were summarized in research monographs quite completely, see for example [1}3]. If the total energy of the system is su$cient to reach the barriers, the system immediately becomes strongly non-linear even when the di!erential equations of motion between the barriers are linear. As a result, even structurally simple models can perform a very complex dynamical behavior [START_REF] Shaw | The transition to chaos in a simple mechanical system[END_REF][START_REF] Lenci | Controlling nonlinear dynamics in a two-well impact system. Parts I and II[END_REF]. This is why general analytical solutions for many degrees of freedom vibroimpact systems are rather impossible. However, an analytical insight into the multidimensional impacting systems can be reached by imposing certain restrictions on the class of motions. In this paper, we consider special vibrating regimes when all the system's particles synchronously vibrate as a single oscillator. In linear cases, such assumption leads to the normal mode solutions, and hence, gives a complete information about vibrating systems due to the linear superposition principle. In non-linear cases, this principle does not work, however, special non-linear normal mode solutions appear to be very important. An overview of the related analytical methods as well as some original material can be found in [START_REF] Vakakis | Normal Modes and Localization in Non-linear Systems[END_REF]. An important physical feature is that non-linear modes frequently perform a `trenda to spatial localization [START_REF] Ja!e | Local and normal modes: a classical perspective[END_REF]. From the point of view of applied mechanics, a literature survey and an overview of di!erent analytical methods can be found in [START_REF] Vakakis | Normal Modes and Localization in Non-linear Systems[END_REF][START_REF] Manevitch | Method of Normal Vibrations for Essentially Non-linear Systems Moscow[END_REF] Spatial symmetries, stability, and localization of non-linear modes in the two-and three degrees of freedom systems with bilateral perfectly rigid barriers were considered in [START_REF] Vedenova | Normal oscillations of a string with concentrated masses on nonlinearly supports[END_REF] combining the special transformation of coordinates [START_REF] Zhuravlev | A method for analyzing vibration-impact systems by means of special functions[END_REF] and the idea of averaging. Recently, the non-linear normal modes concept was also adapted for two degrees of freedom non-linear systems with nonlinear regular (polynomial) and singular (potential barriers) components in [START_REF] Yu | Direct and inverse problems encountered in vibro-impact oscillations of a discrete system[END_REF].

If clearances between the barriers are su$ciently small, the di!erential equations of motion between the barriers can be assumed linear. Although the system still remains strongly non-linear due to the constraints condition, one can employ the temporal symmetry of the periodic motion in order to match di!erent pieces of the linear solution between the barriers, and thus, obtain some kind of exact normal mode solutions [START_REF] Zevin | Localization of periodic oscillations in vibroimpact systems[END_REF]. Exact unit-form periodic solutions were obtained in recent work [START_REF] Manevitch | Exact solutions for a discrete systems undergoing free vibroimpact oscillations[END_REF] for a two degrees of freedom `vibroimpacta system. In principal, the methodology of work [START_REF] Manevitch | Exact solutions for a discrete systems undergoing free vibroimpact oscillations[END_REF] is based on the saw-tooth transformation of time adapted for a class of impulsively excited systems [START_REF] Pilipchuk | Application of special non-smooth temporal transformations to linear and nonlinear systems under discontinuous and impulsive excitation[END_REF] (see Conclusion for related remarks).

In certain sense, the present work combines the ideas of works [START_REF] Zevin | Localization of periodic oscillations in vibroimpact systems[END_REF][START_REF] Manevitch | Exact solutions for a discrete systems undergoing free vibroimpact oscillations[END_REF]. As a result, exact unit-form analytical solutions for a multidegrees of freedom system with rigid barriers are obtained. In particular, conditions of existence and localization of impact modes, and also their physical meaning are considered. The unit form solutions could be suitable for analytical manipulations with them in different perturbations schemes, including averaging techniques.

In this work, the impact modes of a discrete vibrating system with bilateral rigid barriers are periodic motions when some or may be all particles of the system interact with the barriers twice per one period.

It will be shown that the case of unilateral constraints can be considered as well.

An introductory example

Let us consider a one degree of freedom free harmonic oscillator between two absolutely rigid barriers. A mechanical model of the oscillator can be represented as a massive particle attached to the free end of a massless cantilever beam as it is shown in Fig. 1a.

The interaction with the barriers at x"$ is assumed to be perfectly elastic, and the system is represented in the form xK #

x"0, "x")

Since the normal mode regimes are periodic by their dexnition, the reaction of constraints can be treated as a periodic series of external impulses acting on the masses of the system.

Applying this remark to the one degree of freedom system as it is shown in Fig. 1, the related A periodic series of points, + : ( )"$1,, at which "rst derivative ( ) has a step wise discontinuity, may give an exemption. However, it is not important because the di!erential equations of motion must be treated in terms of distributions whenever the Dirac -function is involved in the equations (see [START_REF] Filippov | Di!erential Equations with Discontinuous Right-hand Sides[END_REF]). di!erential equation of motion is written in the linear form xK #

x"2p

I\ [ ( t#1!4k# ) ! ( t!1!4k# )]"p ( t# ) (2)
where ( ) is Dirac function; 2p, , and will be kept as arbitrary constants; ( ) is a standard sawtooth sine

( )" ,!1) )1 ! #2,1) ) 3
( ) +K " ( #4) (3)
This piece-wise linear periodic function can be also represented in the unit form ( )" (2/ )arcsin sin( /2). The related amplitude and the period are normalized in such a manner that the expression [ ( )]"1 holds at least for almost all 3(!R, R). For further convenience, the right-hand side of Eq. ( 2) is expressed through second-order generalized derivative of the saw-tooth sine, where the derivative is taken with respect to the whole argument, t# . The parameter will be called a frequency parameter; though the standard circular frequency is expressed as "( /2) . In this paper, both parameters, and , will be used.

In contrast to system (1), the auxiliary system (2) is linear. Representing unknown steady-state periodic solution in the form,

x"X( ), " ( t# )

one obtains the boundary value problem with no singular terms,

X( )# X( )"0, X( )" O! "p \ (5)
and the related solution is represented in the sawtooth time form [START_REF] Pilipchuk | Application of special non-smooth temporal transformations to linear and nonlinear systems under discontinuous and impulsive excitation[END_REF] x" p

sin[( / ) ] cos( / ) . ( 6
)
This solution can be veri"ed by direct substitution of expression (6) into the equation of motion [START_REF] Dimentberg | Statistical Dynamics of Nonlinear and Time-Varying Systems[END_REF].

A connection between solution (6) and vibration of the original system with the rigid constraints is established by imposing the conditions (Fig 1):

E The impulses at the right-hand side of Eq. ( 2) must act at those time instances at which the mass is in contact with the constraints, i.e.,

x"$ when "$1 O0

E The system cannot penetrate through the barriers, i.e.,

"x") for all 3[!1, 1]. ( 8
)
Substituting solution (6) into condition [START_REF] Ja!e | Local and normal modes: a classical perspective[END_REF], one determines the impulses parameter p, p" cot( / ) [START_REF] Vedenova | Normal oscillations of a string with concentrated masses on nonlinearly supports[END_REF] for which solution (6) takes the "nal form

x" sin[( / ) ( t# )] sin( / ) . (10)
Solution [START_REF] Zhuravlev | A method for analyzing vibration-impact systems by means of special functions[END_REF] satis"es condition (7) automatically. The related parameter p (9) will further be treated as an `eigen-valuea of the non-linear (impact) problem.

The parameters, and , can be expressed through the initial conditions. Let us assume that x(0)"0, i.e., "0, and hence, the total energy of the oscillator per unit mass is expressed through the initial velocity as E"[x (0)]/2. Substitution [START_REF] Zhuravlev | A method for analyzing vibration-impact systems by means of special functions[END_REF] into the last equality gives expression for the frequencies ratio,

"$ 1 2 arccos 1! E #k , k"0, 1, 2 (11)
The right-hand side gives a sequence of real numbers when the total energy, E, is su$ciently large, E*E H " /2, so that the oscillator can reach the constraints.

Generally speaking, not all the magnitudes of the parameter given by sequence [START_REF] Yu | Direct and inverse problems encountered in vibro-impact oscillations of a discrete system[END_REF] lead to real motions of the original system with rigid barriers. Indeed, since the auxiliary system of type (2) does not have any constraints for the coordinate, x(t), hence condition [START_REF] Ja!e | Local and normal modes: a classical perspective[END_REF] does not guarantee that this coordinate will remain inside the admissable region, "x") , during the whole period of vibration. That is why another condition (8) must be veri"ed as well. Such a veri"cation implemented for solution [START_REF] Zhuravlev | A method for analyzing vibration-impact systems by means of special functions[END_REF] shows that condition ( 8) is satis"ed only for the smallest root in set [START_REF] Yu | Direct and inverse problems encountered in vibro-impact oscillations of a discrete system[END_REF]. Fig. 2 illustrates the temporal mode shapes corresponding to the "rst two roots / . It is seen that the second solution, which is shown in fragment (b), violates condition [START_REF] Manevitch | Method of Normal Vibrations for Essentially Non-linear Systems Moscow[END_REF], although it satis"es condition [START_REF] Ja!e | Local and normal modes: a classical perspective[END_REF]. Such `phantoma solutions, however, can be provided with a certain physical meaning if we imagine removable barriers appearing periodically twice per one period and re#ecting the particle into the exterior of the region "x") .

In this paper, the case of unilateral barriers will not be considered specially. The related investigation could be implemented, however, in the same way. Let us remove, for example, the left barrier and consider the oscillator (1) under the unilateral constraint condition x) . In this case, the boundary conditions in (5) should be modi"ed as X( )"

O! "$p \. Such periodic change of sign e!ectively switches the directions of positivepulses to opposite at the right-hand side of Eq. ( 2).

As a result, the solution takes the form,

x" cos[( / ) ( t# )] cos( / ) (12)
where the period of the solution, x(t), and the related basic frequency will be ¹"2/ and " , respectively, due to evenness of cosine. Analysis of the temporal mode shapes for di!erent frequency ratio / is not a di$cult task.

Impact modes

Let us consider N-degrees of freedom conservative system described by the coordinates vector x"(x , 2 , x , )23R,. We suppose that one of the system coordinates, say the ath one, is restricted as "x ? ") ? . In the vector notation, this can be rewritten as

"I2 ? x") ? ( 13
)
where I ? is the ath vector of the basis of the system coordinates, I ? "(0, 2 , 1 ?

, 2 , 0)2.

Inside the domain ( 13), the di!erential equations of motion are assumed to be linear, where M and K are respectively constant mass and sti!ness N;N-matrices.

MxK #Kx"0 (14)
A mass-spring model of the system ( 13) and ( 14) is shown in Fig. 3.

Note that the form of matrix equation ( 14) does not suppose the system to be necessarily a massspring chain, see Example 1 later.

To obtain an explicit analytical solution for the impact modes, the essentially non-linear system ( 13) and ( 14) is replaced by an impulsively forced linear system under no constraints condition

MxK #Kx"pI ? ( t# ) ( 15
)
where p is an unknown `eigenvaluea, the constants and are going to be kept as arbitrary parameters. Thus one seeks a two parameter family of periodic solutions.

A family of periodic solutions of the period 4/ can be found as a linear superposition of solutions [START_REF] Vakakis | Normal Modes and Localization in Non-linear Systems[END_REF] for each of the N modes of system ( 14) with a relevant replacement of the parameters [START_REF] Pilipchuk | Application of special non-smooth temporal transformations to linear and nonlinear systems under discontinuous and impulsive excitation[END_REF] ( H when i(j. The impulses must act at those time instances when the ath mass interacts with the constraints. Such spatially-temporal `location of the impactsa can be assigned by condition

I2 ? x"$ ? when "$1. (17)
Substituting ( 16) into [START_REF] Zevin | On Stability of Periodic Motions with a Presence of Inter-Impacting Masses[END_REF], one obtains the related `eigenvalue,a p" ? ,

H (e2 H I ? ) tan( H / ) H \ ( 18
)
where e2 H I ? is simply the ath component of the jth linear mode vector. Substituting ( 18) into ( 16) gives a two parameter family of the periodic solutions for the impact modes. The parameter is an arbitrary phase shift, whereas the frequency parameter implies some restrictions due to condition [START_REF] Manevitch | Exact solutions for a discrete systems undergoing free vibroimpact oscillations[END_REF].

Proposition 1. Suzcient conditions for the impact modes existence can be summarized as follows:

E The basic frequency of the vibration, "( /2) , pertains to a suzciently small right neighborhood of any frequency H of the linear spectrum, i.e.,

" H /(1! ), 0( ;1 (19)
E For all G such that iOj the linear frequencies ratios G

/ H are not odd numbers, G / H O2k!1 (k"1, 2, 2 ).
Under these conditions, solution ( 16), [START_REF] Pilipchuk | A transformation of vibrating systems based on a non-smooth periodic pair of functions[END_REF], satis-"es inequality [START_REF] Manevitch | Exact solutions for a discrete systems undergoing free vibroimpact oscillations[END_REF], and hence, describes a two parameter family of the real impact mode regimes, x"x(t; , ).

An idea of the proof is to "nd out such cases when x is a monotonic function of on the interval !1) )1, and hence condition [START_REF] Zevin | On Stability of Periodic Motions with a Presence of Inter-Impacting Masses[END_REF] at the boundaries guarantees that inequality (13) holds inside the whole interval as well, see Appendix for further details of the proof. The above conditions are suzcient but not necessary. Namely, if the conditions are true then the impact mode exists. Existence of an impact mode does not guarantee, however, that the conditions hold. For example, some impact modes can exist in the resonance case G / H "2k!1, when the parameter,

"(e2 G I ? /e2 H I ? )/(2k!1) (20)
is su$ciently small. This parameter shows a relative weight of the non-monotonic term which appears in the expression due to the resonance (see appendix). Example 2 below shows that the impact modes may possess a quite complicated spectral structure. Thus, the global investigation is needed to formulate necessary and suzcient conditions. On the other hand, a suzcient condition of non-existence can be formulated by making use the physical meaning of the impact interaction parameter p. Proposition 2. If an impact mode exists then the inequality p( )'0 holds.

Proof. The parameter p (18) cannot be negative for any real impact vibrating regime as a reaction of constraint, because it cannot be directed to a barrier. Thus impact modes cannot exist when p( )(0.

The above Propositions 1 and 2 are illustrated below on special examples.

Example 1. The top mass m of a free doublependulum (see Fig. 4) oscillates between the two absolutely rigid constraints providing small angle amplitude of the top pendulum to the vertical, " ") ;1.

Assuming that another angle, , is su$ciently small as well, one can take the di!erential equations of motion between the barriers in the linear form

K # K # "0, K # K # "0,
where "1#m /m , overdot denotes di!erentiation with respect to a new time parameter, tM "(g/l)t, and l is the length of the rods.

In this case, the linear modes and natural frequencies are, respectively, e " 1

(2 ( #1)

1 , e " 1
(2 ( !1)

1 ! and " #1 , " !1
where the modal vectors satisfy the orthogonality condition, e2 H Me G " HG , with respect to the mass matrix

M" 1 1 1 .
Taking into account that I ? "I , ? " , and N"2, the formal solution ( 16) and ( 18) for the angle coordinates is reduced to

" [tan( / )#( / )tan( / )]\ ; 1 sin[( / ) ( t# )] cos( / ) # ; 1 ! sin[( / ) ( t# )] cos( / ) .
Let us take the parameter such that

" #1 !1 "2k!1.
In this case, the parameter given by expression (20) is evaluated exactly as "1. This value is relatively small (see appendix) so that the existence of impact modes is not a!ected, if condition [START_REF] Pilipchuk | Non-smooth spatio-temporal transformation for impulsively forced oscillators with rigid barriers[END_REF] holds.

It is important to note that the "rst impact mode basic frequency must be su$ciently close to the "rst linear frequency , so that it is not approaching the left neighborhood of the next frequency, . Since there are no more frequencies after , hence its right `neighborhooda has no upper boundary Note that this is just a suitable notation since the (N#1)th frequency does not physically exist. and can be extended to in"nity, ( (R. As a result, the highest impact mode becomes spatially localized when the parameter is growing. The localization can be estimated explicitly by asymptotic ( \P0) expansion

O " tan 2 ! tan 2 tan 2 # tan 2 " ! # 1# 6( # ) \ #O( \) "!1! 12 \!O( \).
It is seen that ( / )" O P!1 as PR, i.e., the horizontal displacement of the bottom mass becomes negligibly small whereas the impacting mass oscillates between the barriers. Fig. 5 represents the related trend of the mode shape.

Example 2. Let us consider a mass-spring chain of N identical particles

xK L # k m (!x L\ #2x L !x L> )"0, (21)
n"1, 2 , N; x "x ,> "0 under the bilateral constraints condition (see Fig. 3),

"x ? ") ? ( 22
)
where k and m are sti!ness of the springs and mass of the particles, respectively. A set of no impact modes and frequencies can be found explicitly, since the system can be viewed as a "nite element model of a continuous string. The jth mode vector and related frequency of the linear system are given by the expressions

e H " 4 N#1 sin j N#1 , 2 , sin N j N#1 2 and H " ,> sin j 2(N#1) (23)
where notation ,> "2(k/m has been introduced, the basis vectors are normalized such that e2 H e G " HG . The ath component of the jth normal mode vector is

e2 H I ? " 4 N#1 sin a j N#1 . ( 24
)
Let us show that the impact mode periodic solution ( 16) and ( 18) becomes localized as the frequency parameter is in"nitely growing, PR. First, replacing the trigonometric functions by their asymptotic expansions as sin ( In this particular example, the sums can easily be evaluated. Taking into account expression (24) and the standard trigonometric sums [START_REF] Gradshteyn | Table of Integrals, Series, and Products[END_REF], one obtains , H (e2

H I ? )(e2 H I @ )" 16 (N#1) , H sin a j N#1 sin b j N#1 " 8 N#1 ?@ . ( 26
)
Later on, we will need also the sum

, H (e2 H I ? )(e2 H I @ ) H " 4 ,> N#1 (! ?@\ #2 ?@ ! ?@> ). (27)
Substituting (26) into the asymptotic expression (25), one obtains

x @ & ? ?@ ( t# ) as PR. ( 28
)
This expression shows that the ath particle of the chain vibrates according to the saw-tooth temporal mode shape with an in"nitely large frequency, whereas all other particles remains at rest. Thus, the impact mode becomes spatially localized as PR. The localization tendency of the impact modes is illustrated by Fig. 5a. Fig. 6 provides Propositions 1 and 2 with some additional illustration on the spectral axes of the chain consisting of N"5 particles. The "gure represents diagrams of the impulsive force parameter, p, as a function of the basic circular frequency of vibration, "( /2) , for di!erent masses under the constraints, a"1, 2, and 3. It is seen that each of the frequencies of the linear spectrum possesses its right neighborhood where the parameter p is positive, and hence the impact modes can exist (see fragments (a)}(c)). At the same time, the parameter p is not necessarily negative on the left of the frequencies , 2 , as it is seen from the fragments (b) and (c) (see, respectively, the frequency and the frequencies and ). The diagrams structure depends on the particle under the constraint condition. An interesting feature of the diagrams is that they are more complicated around the lowest frequency. The parameter p can change its sign many times in the domain between the "rst two frequencies, ( ( .

Systems with multiple impacting particles

Let us consider the case of two constrained particles. It will be seen that a generalization on multiple constrained particles is a quite trivial task. For example, let us put the constraints condition on the ath and bth coordinates (aOb) of the general linear system [START_REF] Pilipchuk | Application of special non-smooth temporal transformations to linear and nonlinear systems under discontinuous and impulsive excitation[END_REF]. These conditions are "x ? ") ? and "x @ ") @ or in the vector notations

"I2 ? x") ? and "I2 @ x") @ . ( 29
)
In this case, the impulsive excitation on the right-hand side of auxiliary equation must act on the both ath and bth particles, so that the equation takes the form MxK #Kx"(p ?

I ? #p @ I @ ) ( t# ) ( 30
)
where p ? and p @ are parameters to be determined. The related solution includes some items related to p ? and p @ , and can be represented in the form

x" ,

H p ? ( e2
H I ? )e H #p @ (e2 H I @ )e H H sin( H / ) cos( H / ) . ( 31
)
Following the normal modes ideology, we assume that the impact mode periodic regime is accompanied by synchronous impact interactions of the both impacting particles with the constraints according to conditions I2 ?

x"$ ? and I2 @ x"$ @ when "$1.

(32) Substitution (31) into (32) gives linear algebraic equations with respect to p ? and p @ in the form

k ?? p ? #k ?@ p @ " ? , k @? p ? #k @@ p @ " @ , ( 33
)
where

k ?@ " , H (e2 H I ? )(e2 H I @ ) H tan H . ( 34
)
Expressions ( 31) and (33) give a formal impact mode solution. The impact mode (31) exists for those frequencies at which the determinant of system (33) is non-zero, and also condition (29) holds. Solution (31) can be viewed as a strongly non-linear superposition of the two simplest impact modes with a single impact pair. The result of the superposition is shown in Figs. 5b andc for two di!erent magnitudes of the frequency, .

Let us consider the higher frequency domain for the above example of mass}spring system, when < , . In this case, one has tan( H / )'0 for all j"1, 2 , N, and hence, the coe$cients k ?@ (34) create the Gram matrix with non-zero determinant [START_REF] Bellman | Introduction to Matrix Analysis[END_REF]. The asymptotic estimation below con"rms this conclusion. Indeed, for < , all ratios H / are small and thus an asymptotic expansion holds as

sin[( H / ) ] cos( H / ) " H # 1 2 H ! 3 #O( \). (35)
Substituting this expression into solution (31) and coe$cients (34), one obtains the asymptotic solution for arbitrary cth particle in the form

x A "(P ? ?A #P @ @A ) ! 16 ,> ! 3 ;[P ? ( ?A\ !2 ?A # ?A> ) #P @ ( @A\ !2 @A # @A> )]#O( \) (36)
where x A "x2I A and " (2 t/ # ). The impact interaction parameters, P ? and P @ , are given by the linear algebraic system K ?? P ? #K ?@ P @ " ? , K @? P ? #K @@ P @ " @ , (

with the coe$cients

K ?@ " ?@ ! 24 ,> ( ?@\ !2 ?@ # ?@> ) #O( \). (38)
I.e., it gives zero contribution into the related integrals of the theory of distributions.

The parameters and the coe$cients have been rescaled as follows:

+P ? , P @ ," 2 (N#1) +p ? , p @ ,, +K ?? , K ?@ , K @? , K @@ ," (N#1) 2 +k ?? , k ?@ , k @? , k @@ ,.
It is seen that K ?@ P ?@ as PR, and Eqs. (37) give the solution P ? " ? and P @ " @ . In this limit, according to (36), the vibration becomes localized on the two particles which vibrate between the barriers performing the saw-tooth temporal shape,

x A &( ? ?A # @ @A ) 2 t# as PR.
This is the leading-order asymptotic approach. All other particles, cOa and cOb, are at rest. However, they oscillate with small amplitudes of di!erent orders of \ when the parameter is bounded. Asymptotic expansion (36) includes the terms of order \. It is seen that the particles numbered c"a$1 and c"b$1 have the amplitudes of the lowest order, \. These particles are the nearest to the impacting ones. Some analysis of expansion (36) shows that the temporal mode shapes of the impacting particles, c"a and c"b, are non-smooth and close to the saw-tooth sine wave as it is expected to be due to the interactions with the constraints. On the other hand, the temporal mode shapes of the nearest particles, c"a$1 and c"b$1, are estimated by the combination of the saw-tooth sine, ! /3, with the "rst two continuous derivatives with respect to time, t. These are

d dt ! 3 " 2 (1! ) 3C(R) and d dt ! 3 " 2 [!2 ( )#(1! ) ] "! 2 2 3C(R),
respectively. The prime denotes di!erentiation with respect to the whole argument of the saw-tooth sine, ,d /d(2 t/ # ).

In the above expressions, one should take into account that the -type singularities of second derivative, , are `locateda at those points +t,, where "$1. As a result, the underlined above term is zero.

Thus the temporal mode shapes of the particles with no constraints are smooth functions of time, although they are expressed through the saw-tooth sine.

Conclusion

A class of strongly non-linear many degrees of freedom vibrating systems including bilateral rigid barriers was considered. Exact analytical periodic solutions were expressed through the saw-tooth temporal argument. The conditions of existence and non-existence for impact mode regimes were formulated based on the exact unit-form solutions. More precisely, Proposition 1 gives a su$cient condition of existence of impact modes, whereas Proposition 2 gives a su$cient condition of their non-existence. These two propositions do not compose any necessary and su$cient condition of existence for the impact modes. Namely, one cannot indicate all the cases when impact modes exist, and also all the cases when they do not. A certain exemption is given only by the high frequency vibration ' , , when the impact modes become localized spatially and always exist. The examples clearly showed that a complete investigation presents a global geometrical problem. This, however, can be done at least numerically, since the exact expressions have been obtained in terms of trigonometric sums. The problem of stability can be considered by evaluating the eigenvalues of the Jacobian matrix for known periodic solutions as it was done, for example, in [START_REF] Zevin | On Stability of Periodic Motions with a Presence of Inter-Impacting Masses[END_REF]. The systems above considered are strongly non-linear due to barriers only. In some cases, the system displacements must be signi"cant in order to provide an interaction with barriers, and hence, linearization of the equations of motion between the barriers may become doubtful. In general terms, however, the proposed formulation remains applicable. For example, Eq. ( 2) can be generalized as

xK #f (x, x , t)"p ( t)
provided that the function f (x, x , t) is periodic (¹"4/ ) with respect to time, and the condition "x") holds. In this case, the saw-tooth temporal argument can be introduced by using the twocomponent representation for periodic solutions [START_REF] Pilipchuk | Application of special non-smooth temporal transformations to linear and nonlinear systems under discontinuous and impulsive excitation[END_REF][START_REF] Pilipchuk | A transformation of vibrating systems based on a non-smooth periodic pair of functions[END_REF].

x(t)"X( ( t))#>( ( t)) ( t).

This results into the coupled non-homogeneous boundary-value problem with respect to unknown functions X( ) and >( ),

X( )#R D (X, >, X, >, )"0, X( )" O! "p \, >( )#I D (X, >, X, >, )"0, >" O! "0,
where functions R D and I D are obtained by substitution of the above representation for periodic solutions into the equation of motion. Such a kind of boundary value problems admit approximate analytical solutions in the power series form with respect to the new temporal argument, , since it automatically accounts for the periodicity of the motion. Unfortunately, the related solutions may appear to be so complicated that it will be either di$cult or even impossible to separate real and `phantoma solutions.

To this end, the above manipulations with the sawtooth temporal variable, should not be confused with the method of non-smooth transformation of the con"guration space coordinates for the systems with rigid barriers [START_REF] Zhuravlev | A method for analyzing vibration-impact systems by means of special functions[END_REF]. These two methods are mutually antithetic in its physical meaning as well as in its mathematical implementation. For example, being applied to system (1), the method of work [START_REF] Zhuravlev | A method for analyzing vibration-impact systems by means of special functions[END_REF] would give a non-linear oscillator (compare with (5)), sK # (s) (s)"0 where s(t) is a new positional variable, such that x" (s) ; the result is written in the notations of present work for the reason of comparison. The later transformation does not require the motions to be periodic. Unfortunately, this advantage brings essential non-linearity of the transformed di!erential equations. Further comparison of these two techniques as well as their composition can be found in [START_REF] Pilipchuk | Non-smooth spatio-temporal transformation for impulsively forced oscillators with rigid barriers[END_REF].

Substituting (A.2) into (A.1) and taking the ath component of the vector x, one obtains an estimation in the form

x ? "x2I ? " ? sin[ (2n!1! ) /2] sin[(2n!1! ) /2] #O( ). (A.3)
In this expression, the leading term is monotonic on the interval !1) )1 and its absolute value does not exceed ? if only n"1 and the parameter is positive and su$ciently small. In this case expression (A.2) can be rewritten in the form [START_REF] Pilipchuk | Non-smooth spatio-temporal transformation for impulsively forced oscillators with rigid barriers[END_REF], corresponding to the "rst condition of Proposition 1. To complete this part of the proof, however, one has to specially investigate a small neighborhood of the boundary points "$1. The neglected terms O( ) in (A.3) may become signi"cant when is close to any of the two boundaries and the impacting mass coordinate in the range "x ? ! ? "& or "x ? # ? "& . Let us consider a small neighborhood of the boundary "1, were "1! (0) ;1). Substituting this expression for and also the frequency given by ( 19) into the exact solution (A.1), and keeping the leading order terms with respect to and , gives the estimation

x ? "x2I ? " ? 1! 4 , H (e2 H I ? ) (e2 H I ? ) .
Since the coe$cient of the product is negative, it is seen that condition (13) holds, i.e., the coordinate x ? remains inside the domain "x ? ") ? provided that the values and are su$ciently small. Now, let us check whether or not the sums involved in the exact solution (A.1) possess any poles di!erent than (19) as P0. First, taking into account expression [START_REF] Pilipchuk | Non-smooth spatio-temporal transformation for impulsively forced oscillators with rigid barriers[END_REF], one obtains

(2k!1)! G "(2k!1)! G H (1! ) "(2k!1)! G H #(2 ! ) G H . (A.4)
It is seen that this value goes to zero as P0 when k"1 and i"j. This is the above considered case. However, one may have another zero limits when the frequencies ratio is an odd number, i.e., when G / H "2k!1. In this cases the sums in (A.1) will have more the one term, and one cannot guarantee the monotonicity of x ? as a function of . So we eliminate these cases from consideration by the second of the above two su$cient conditions. The proof is completed.

The above expression `one cannot guaranteea does not determine those cases when the second condition of Proposition 1 is really signi"cant. To investigate this point, let us suppose that the frequency ratio is odd number, i.e., the resonance ratio where the parameter (20) depends on the system parameters and also numbers i, j, k and a.

The "rst term of expression is of the same structure as (A.3) and appears to be monotonic for !1) )1 and 0( ;1. The second term arises due to condition (A.5), and it is not a monotonic function of for k*2. Thus, under the resonance condition (A.5), it is not known whether the function x ? ( ) reaches its absolute maximum and minimum at the ends of the interval !1) )1. Fig. 7 shows, however, that the answer essentially depends on the parameter .

The three fragments of this "gure represent solution (A.6) for the impacting mass as a function of the two arguments, x ? "x ? ( , \), for two di!erent odd frequency ratios, / "3 and 5. An inverse scale has been chosen for the parameter in order to better visualize the regimes of the `phantoma solutions associated with large magnitudes of this parameter.

In Fig. 7, the `phantoma solutions correspond to those \ at which solutions, shown by the meshed surface, intersect the horizontal (non-meshed) planes, x ? / ? "$1. These planes represent the two barriers. As follows from expressions (A.6) and [START_REF] Filippov | Di!erential Equations with Discontinuous Right-hand Sides[END_REF], the parameter determines a contribution of the ith (resonating) mode into the solutions and thus is an important characteristic of the system. Namely, the ith mode is responsible for violation of the condition "x ? / ? ")1. Fig. 7 also shows that increasing the frequency ratio / and thedistance from the basic frequency will expand the \-region of non-existing `phantoma solutions.

Fig. 1 .

 1 Fig. 1. The oscillator with bilateral rigid barriers (a) is replaced by the oscillator under the periodic series of external impulses (b).

Fig. 2 .

 2 Fig. 2. Real (a) and `phantoma (b) solutions corresponding to the "rst (smallest) and second roots respectively, ( / ) "1.1502 and ( / ) "!1.1502# . The total energy level is E"1.2E H .

Fig. 3 .

 3 Fig. 3. Mass}spring model of a discrete elastic system with bilateral barriers.

Fig. 4 .

 4 Fig. 4. Double pendulum with bilateral constraints.

Fig. 5 .

 5 Fig. 5. Localized impact modes of the mass}spring chain (n"25) for (a) single constrained particle (b) two constrained particle and the same frequency " #0.01. The same case of two constrained particles when increasing the frequency is illustrated by (b) and (c) " #0.2.

Fig. 6 .

 6 Fig. 6. The impulsive force parameter, p, as a function of the trigonometric frequency, , for the "rst (a), second (b), and third (c) mass under the constraint condition. The chain consists of N"5 masses. For all cases the clearance parameter is "0.5, and ,> " "1.

  1 for certain k*2 (A.5) holds. In this case, the terms of order O(1) on the right-hand side of expression (A.4) disappear. Then, substituting (19) and (A.4) into the exact solution (A.1), one obtains estimation x ?

Fig. 7 .

 7 Fig. 7. Family of solutions (shown by meshed surfaces) for di!erent odd frequency ratios, / , and -distances from the basic frequency, . The horizontal planes represent the barriers, \ is a parameter of the family.

  ,

	x"p	, H	(e2 H	I ?	)e H H	sin[( H cos( H / ) ] / )	(16)
	where " ( t# ) is the sawtooth temporal argu-
	ment, e H natural frequency of linear system (3.2). The linear are the jth normal mode and the and H
	normal modes are normalized as e2 H is the Kronecker symbol. We suppose Me G , " HG where HG that G

Acknowledgements

The author would like to thank Professor A.A. Zevin from TRANSMAG Research Institute of Academy of Sciences of Ukraine for complete text of reference [12], and a very helpful discussion.

Appendix A

Proof of Proposition 1. On the "rst stage, taking into account the expansion [15, p. 43

for " H / , one can represent solution ( 16) and (18) in a more convenient for our purposes form

x" ? HL

Generally speaking, it is di$cult to conclude whether this function of is monotonic or not, since it is composed of many oscillating terms. However, when H / &2n!1 for certain , H and n, then the only one term is expected to be dominating in each of the two sums involved in solution (A.1). In this case, the result can be explicitly estimated by considering the neighborhood of the related pole of the numerator and denominator

where the parameter shows how the both parts of ratio (A.1) are close to their pole.


Denis Becker
email: denis.becker@st.com

Matthieu Moy
email: matthieu.moy@imag.fr

Jérôme Cornet
email: jerome.cornet@st.com

SycView: Visualize and Profile SystemC Simulations

Keywords:

come

I. INTRODUCTION

SystemC is a hardware modeling C++ library standardized by IEEE. It enables a designer to simulate concurrent processes, and thanks to the use of C++, provides an easy way to simulate mixed software/hardware systems. For this reason, it is mostly used for systems-on-chip (SoC) modeling. It has been designed so that it can be used at different levels of abstraction, thus at different steps of the design workflow.

The increasing complexity of models and components has led to the need to speed up such simulations. The natural method to optimize a program, SystemC or not, is first to analyze it in order to find the bottleneck and then to apply an optimization on the corresponding part of the program. Since SystemC is a C++ library, usual profilers for C++ like gprof or valgrind+kcachegrind can be used. They will however miss important aspects of the execution of a SystemC program, like: how much time is spent in the SystemC kernel as opposed to the user-written parts, perprocess statistics, simulated time based visualization. To the best of our knowledge, there is no turnkey application available to get these information from a SystemC simulation. Also, as the complexity of models grows, it becomes necessary to visualize executions at a high abstraction level to get a better understanding of the system synchronization.

In this paper, we present SycView, a tool for visualization and profiling of SystemC simulations. Our purpose is to provide SystemC users with a tool to get SystemC-aware information about the execution of their simulations. The underlying motivation of the tool is to increase the understand-ability of complex SystemC models and to help the set up of optimizations and/or parallelization.

II. BACKGROUND

In this paper, the term wall-clock time refers to the time spent by the execution of the simulation on the host machine, and the term simulated time to the virtual time spent by the model during the execution (i.e. what the real hardware will be supposed to spend). We call a transition any portion of code in SC_METHODs or SC_THREADs that is executing atomically from the point of view of SystemC. As an example, the following code will produce 3 transitions:

void compute() { // declared

III. PROPOSED TOOL

The principle of SycView is simple: it consists in trace recording during simulation (III-A) and then trace visualization (III-B). In order to print traces, we instrumented the SystemC kernel, based on the ASI (formerly OSCI) implementation. For the visualization we developped a graphical user interface (GUI) written in Java.

A. Trace Recording

The trace recording consists in printing data at interesting points. For instance, we print a trace each time a transition yields to the kernel, containing:

• The SystemC process which triggered this transition.

• The type and arguments of the wait performed.

• The wall-clock time duration of the transition.

When the simulation ends, we store those information on text files. Then for example, we are able to find which SystemC process (or group of processes) globally consumes most of the time. We can also use statistical metrics to get the average execution time of a process and compare it with the number of executions to highlight how each process spends its time.

We also keep track of the number of runnable processes at the beginning of each delta cycle. More precisely, what we get is the maximal number of runnable processes at the beginning of each immediate notification cycle within each delta cycle. We have implemented a GUI providing six different views, which can be split in two main categories.

The first category is plotting the scenario of an execution (order and duration of transitions) as a function of either wallclock time or simulated time. For example, Figure 1 shows the screenshot of a wall-clock time plot. On this plot we can see that there seems to be a chain triggering of the processes executing in one order on the left part, and in the reverse order on the right part. The width of a rectangle is proportional to the wall-clock time duration of the corresponding SystemC transition. This view, as illustrated by this little example, can be used to identify patterns in the executions of transitions, and can highlight which transitions are particularly timeconsuming. Such information could hardly be identified by a static code analysis, because of its complexity. On the other hand on Figure 2 we can see an example of a simulated time plot. The processes are also represented on the left part, and on the right part, a vertical stroke is placed for each process execution, in the simulated time it occured. Note that what appears to be black rectangles are strokes close together. The blue rectangles represents time ranges in which the transition may have occured, based on loosely-timed information on the model. Note that time ranges are not part of the SystemC kernel so we added that when we instrumented the kernel because it was part of our industrial context.

The second category consists in giving statistical metrics about the platform execution. We display the wall-clock time consumption per process (with statistical metrics), as on Figure 4. We can see that the first process uses almost 13 % of the time in 10111 transitions, while the third process uses almost 8 % of the time in only 14 transitions. That makes a huge difference in the mean execution time, and we can deduce that optimizing the third process may be more efficient than the first one. We also show the number of runnable SystemC processes at each delta cycle, shown in Figure 3. This table can also be displayed for SC_THREADs or SC_METHODs only.

IV. RELATED WORK

We have found that most of the litterature about SystemC visualization focus on the model description. For example, the Figure 3: Number of runnable processes tools presented in [START_REF] Große | Efficient Automatic Visualization of SystemC Designs[END_REF], [START_REF] Berner | SystemCXML: An Exstensible SystemC Front end Using XML[END_REF], [START_REF] Donlin | Performance Analysis and Visualization of SystemC Models[END_REF], [START_REF] Albrecht | A Loosely-Coupled Graphical User Interface for Run-Time Control of SystemC Simulation Models[END_REF], [START_REF] Genz | Visualization of SystemC Designs[END_REF] and more recently [START_REF] Stoppe | Towards a Multi-dimensional and Dynamic Visualization for ESL Designs[END_REF] gives access to the visualization of the hierarchical architecture of a platform, as well as the exploration of the components behaviour. Such information are precious and these tools are complementary with our tool especially when it comes to understanding a design. But what we found missing in these tools is a software point of view, in order to understand the model not as the representation of an SoC, but as a piece of software. Besides, some of the above mentioned tools need to instrument the model, which is generally not possible in the case of huge and complex models.

V. EXAMPLE USAGE SycView is not only a software engineering tool, the information given are also useful to characterize a model theoretically. Initially, this tool was made to help the set up of a parallel SystemC kernel on an existing industrial model. We have used SycView outputs in [START_REF] Becker | Challenges for the Parallelization of Loosely-Timed SystemC Programs[END_REF] to illustrate the fact that the existing parallelization approaches are not applicable in the case of a loosely-timed TLM model, based on the analysis of the profile of our industrial test case.

VI. CONCLUSION

In this paper, we have presented SycView, for visualization and profiling of SystemC simulations. The main advantage of However the tool can be extended to add data collection about transactions or event processing for example, that could also be interesting for analysis purposes.

From the data gathered during the execution of a simulation, the tool can display the following views: The views of the first item are helpful to understand the sequence of transitions for a simulation. The two other ones presented in this list can quickly identify which parallelization approach is likely to work efficiently, and which one cannot be efficient.

Figure 1 :

 1 Figure 1: Wall-clock time axis

Figure 2 :

 2 Figure 2: Simulated time axis

•

  Simulation timing diagram indexed by either wall-clock or simulated time. • Wall-clock time consumption per SystemC process. • Partition of delta cycles depending on the number of runnable processes.

Figure 4 :

 4 Figure 4: Wall-clock time usage of SystemC processes