On using Tra er Driver for External Dynami
Pro ess Observation ⋆ (extended abstra t)

arXiv:cs/0701106v1 [] 17 Jan 2007

Pierre Deransart

Inria

Ro quen ourt, BP 105, 78153 Le Chesnay Cedex, Fran e
Pierre.Deransartinria.fr

Abstra t
One is interested here in the observation of dynami

pro esses starting from the

tra es whi h they leave or those that one makes them produ e. It is

onsidered

here that it should be possible to make several observations simultaneously, using
a large variety of independently developed analyzers.
For this purpose, we introdu e the original notion of full tra e to

apture

the idea that a pro ess

an be instrumented in su h a way that it may broad ast

all information whi h

ould ever be requested by any kind of observer. Ea h

analyzer

an then nd in the full tra e the data elements whi h it needs. This

approa h uses what has been

alled a "tra er driver" whi h

ompletes the tra er

and drives it to answer the requests of the analyzers.
A tra er driver allows to restri t the ow of information and makes this
approa h tra table. On the other side, the potential size of a full tra e seems to
make the idea of full tra e unrealisti .
In this work we explore the

onsequen es of this notion in term of potential

e ien y, by analyzing the respe tive workloads between the (full) tra er and
many dierent analyzers, all being likely run in true parallel environments.
To illustrate this study, we use the example of the observation of the resolution of

onstraints systems (proof-tree, sear h-tree and propagation) using so-

phisti ated visualization tools, as developed in the proje t OADymPPaC (20012004).
The pro esses
approa h

1

onsidered here are

omputer programs, but we believe the

an be extended to many other kinds of pro esses.

Introdu tion

One is interested here in the observation of dynami

pro esses starting from the

tra es whi h they leave or those that one makes them produ e. It is

onsidered

here that it should be possible to make several observations simultaneously, using
a large variety of independently developed analyzers.
When one wants to observe a pro ess, the pra ti e is to instrument it for
ea h type of observation whi h one wants to make on it. One thus implements a
⋆

This work has been partly supported by OADymPPaC [1℄, a Fren h RNTL proje t.

new "ad ho " tra er for ea h analyzer, or one adapts and
one. Su h a work
approa h whi h

ompletes an existing

an be largely avoided if one adopts from the start a general
onsists to instrument it su h that it produ es what we

all a

"full tra e". This unique tra e will be useful then for all the later observations
whi h one

an plan to make. Ea h analyzer

an then nd in the full tra e the

data elements whi h it needs. This approa h uses what was
driver" whi h

alled a "tra er

ompletes the tra er and drives it to answer the requests of the

analyzers.
This approa h is parti ularly tempting in pra ti e as the full tra e never needs
to be

ompletely expressed (the ex hanges of information remain limited) and

the work of the tra er implementation and of its driver is made on e for all. The
evaluation in terms of feasibility and performan e remains however problemati .
In fa t, this approa h allows to redu e the size of the tra e emitted to a
useful bare minimum and thus to speed up the whole pro ess. In
it allows to

onsider very large full tra es. This has also a

the size of the tra e. Beyond a

ompensation,

ost whi h grows with

ertain size, the produ tion

ost of the tra e is

likely to be ome prohibitory. It is pre isely the question in whi h one is interested
here. Until where

an one go in this approa h on a pra ti al level without slowing

down a pro ess ex essively and how? To get a more pre ise idea, one must take
into a

ount not only the time of tra e produ tion, but also how the tra e will

be used.
In [2℄ and [3℄ the notion of tra er driver is presented and experimented is the
ontext of nite domain

onstraint resolution [4℄. But the question of the nature

of the tra e whose emission is

ontrolled by the tra er driver is not dire tly ta k-

led. In this work we explore the

onsequen es of this notion in term of potential

e ien y, by analyzing the respe tive workloads between the (full) tra er and
many dierent analyzers, all being likely run in a true parallel environment.
In this work, we introdu e the notion of full tra e to
pro ess
whi h

apture the idea that a

an be instrumented in su h a way that it may broad ast all information
ould ever be requested by any kind of observer. We then analyze the

nature of the work of the tra er and the driver, and the distribution of the
fun tions between the tra er and its driver on the one hand, and the analyzers
on the other hand. This allows us to better estimate how powerful, useful and
e ient the

on ept of full tra e

ar hite ture of all involved

an be, provided it is a

ompanied by the right

omponents.

To illustrate this study, one will take the example of the observation of the
resolution of

onstraints systems (proof-tree, sear h-tree and propagation) us-

ing sophisti ated tools for visualization, a

ording to the method developed in

the proje ts DiSCiPl (1997-2000) [5℄ then OADymPPaC (2001-2004) [1℄. This
eld is of parti ular interest be ause the tra es in lude the representations of
ompli ated and potentially bulky obje ts, and the

omputations (evolution of

the domain of the variables) are at the same time logi al and sto hasti . The
onstraints systems, be ause of the
to true

omplex systems.

omplexity of their resolution, are very

lose

In this extended abstra t we present su

essively the

on epts of full tra e

and its in remental  ompressed version, then the question of their semanti s.
We analyze nally the problem of the distribution of work between a driven
tra er and external analyzers whi h work only with the useful tra e ow whi h
is provided to them by their requests.

2

Full Tra e

We introdu e here the
pro ess

on ept of

full tra e.

By denition the full tra e of a

ontains all one may like to know about it during its exe ution (this

in ludes likely a des ription of the pro ess itself ) . A pro ess is
at a given moment

t

by a state

St .

hara terized

It does not enter in the framework of this

arti le to dene what is exa tly su h a state. It will be supposed only that it
an be des ribed by a nite set of parameters
for its value at moment
A

t.

The

pn

for the

nth

parameter, and

pn,t

on ept of "moment" will be spe ied hereafter.

urrent state will be denoted by the list of the values of its parameters. It is

also assumed that the transformation of a state into another is made by "steps"
hara terized by an a tion

a. The set of a

tions performed at moment

t is labelled

at .
So dened, the

on ept of full tra e seems not to have any appli ation. In

pra ti e, there are only approximations; but the important thing here, is to admit
that, whatever is the level of details with whi h one wishes to observe a pro ess,
there is always a threshold whi h makes it possible to dene su h a tra e. One
an

onsider that in the

ase of a program, it a ts of a more or less thorough

instrumentation whi h produ es a tra e, in other words a program augmented
with a tra er.

Denition 1 (Virtual Full Tra e).
sequen e of tra e events of the form

. An virtual full tra e is an unbounded

et : (t, at , St+1 )

omprising the following

elements:

 et : unique identier of the event.
 t: hrono. Time of the tra e. It only

varies by unit values and is always

in reasing. To distinguish from the time of the observed pro esses or of the
analyzers whi h may not be monotonous

ompared to the

hrono.

 St = p1,t ..., pn,t : parameters at hrono t. In a tra e event the parameters
are alled attributes and St the full urrent state. The parameters may
St is the last
urs. The parameters (or attributes)

des ribe obje ts or a tions performed to rea h the new state.
observed state before the event

et

orrespond to the new rea hed state

o

St+1 .

 at : a tion an identier of the set of a
state

St

to the state

tions

hara terizing the step from the

St+1 .

Any tra e ee tively produ ed by a pro ess

an be regarded as a partial full

tra e. In pra ti e, one "sees" only partial tra es whi h start after the moment
0 where the pro ess observed is in a presumably initial state

S0 .

We will limit

ourselves in this summary to only a single example of tra e: the tra e of the
proof-trees in Prolog systems based on standard Prolog [6℄. This tra e is far
from being a full tra e (many useful information, even easily available at any
moment are not represented there). Here is an extra t:

1
2
3
3
4
4
5
....

1
2
3
3
3
3
3

Call:
Call:
Call:
Exit:
Call:
Exit:
Call:

'$ all$'(ben h(2))
ben h(2)
2>0
2>0
_182 is 2-1
1 is 2-1
ben h(1)

This is a Byrd's tra e [7℄, adopted in the majority of the Prolog systems. The
moment "0"
event

orresponds to the laun hing of the resolution of a goal. Ea h tra e

orresponds to a stage in its resolution. An event

ontains the following

information: two attributes whi h are indi ation of depths (the rst, the depth
in the sear h-tree and the se ond in the proof-tree), a "port" whi h

orresponds

to the a tion whi h made it possible to rea h this stage. Thus the port
orresponds to a
goals to solve, and
total of 5 in the

all

all to the indi ated subgoal and the installation of the sub-

exit

to the su

ess of the subgoal. There are other ports (a

ase of GNU-Prolog) not detailed here. The rst " all" denes

the laun hing of the rst goals (if there is only one of them). If the resolution
terminates, the tra e is nite, unbounded otherwise. The last attribute gives
the subgoal to solve. This tra e does not
hrono

omprise identiers nor

hrono; the

orresponds to the sequential order of emission of the tra e events and

the resulting

hrono plays the role of an identier.

It is interesting to note that the obje tive of su h a tra e is to display all the
steps of evolution of a proof-tree until obtaining all the possible proofs (the port

fail

orresponds to a failure and

redo

to a nondeterministi

goal where a new

resolution will be tried), and to some extend to des ribe also the sear h-tree.
However, the (partial) proof-tree is never expli itly des ribed (not more than
the sear h-tree). This tra e thus does not provide the parameters of interest dire tly (the partial proof-tree). This brings us to the following observation. The
parameters of the full state are not given expli itly in this tra e, but only some
attributes (port and goal) whi h possibly make it possible to nd it. We will
re onsider this point later. These attributes thus give only an in remental information whi h makes it possible to obtain the new proof-tree after a resolution
step. We will say that the tra e is "in remental". This leads us to dene the
following parti ular tra es whi h we dene here without more details.

Denition 2 (Dis ontinuous, Ee tive, In remental Full Tra e).
A tra e is dis ontinuous if it is a (full) tra e whi h ontains su
events whose variation of the

.
essive

hrono may be higher than a unit. There are "holes"

in it, either be ause the emission is dis ontinuous, or be ause the observing proess "listens" only o

asionally to it. Noti e that the dis ontinuity

on erns only

the tra e emission and not its extra tion; in other words moment 0

orresponds

to the a tivation of the tra er.
A tra e is

ee tive if it is a (full) tra

starting from the knowledge of

(St , At )

e of the form

one

an dedu e

et : (t, At ) and
(at , St+1 ). At

su h that,
denotes a

set of attributes. The ee tive tra e is the tra e emitted by a tra er, that whi h
is a tually visible. The virtual full tra e is a parti ular
where the attributes
parti ular

At

are the a tion label

at

ase of ee tive tra e

and the parameters

St .

Another

ase is the full in remental tra e.

A tra e is

in remental if the attributes are su

h that only the

urrent state are noted. It has the form

et : (t, Deltat +)

hanges ae t-

Deltat +
ontains the des ription of the a tions whi h modify the values of the parameters

ing the

where

of the moment t. To remain a full tra e, this tra e must satisfy the following
dition: starting from the knowledge of

(St , Deltat +)

one

an dedu e

on-

(at , St+1 ).

In this extended summary, when the distin tion is not absolutely ne essary,
one will not distinguish between virtual and ee tive tra es, and one will speak
indierently about parameters or attributes.
Pra ti ally all the tra es are in remental (thus it uses attributes), as the
pre eding example illustrates it well, be ause the emission of a full state in ea h
tra e event would be obviously prohibitive. In fa t the size whi h would take the
events would be mu h too high and the tra e would be extremely redundant.
The

ondition imposes simply that one

an retrieve the full tra e starting from

the transmitted attributes and from the pre eding full state. In pra ti e the
observed pro esses will produ e partial tra es only. In this

ase the retrieval of

the full state is impossible. If one wants to nd a full tra e, or at least a more
omplete one, it will be ne essary "to ask" the tra er to provide at least one full
state. If the observing pro ess needs to take into a
that

an be su ient to enable it to maintain a

ount only a partial state,

onsistent partial state. On the

other hand if it needs, at a given moment, to know a full state, or at least a
more
full

omplete state, it will have to ask the tra er to provide him at least a
urrent state or a part of it.

Pra ti ally all the tra es are dis ontinuous, even if often ea h part of them
(ne essarily nite)

an be regarded as a nite single tra e. This also raises the

problem of the knowledge of the initial state

S0

in whi h the observed pro ess

was at the moment of the initial tra e event ( hrono equals to 0) and thus of the
ommuni ation to the analyzers of the full initial state

S0 ,

before any event of

tra e.
These two reasons justify that one is interested in the manner of obtaining
su h a state. The urrent value of a parameter may exist just as it is in the pro ess
and requires only a small

omputation to extra t it. On the other hand it may

not exist and should require a partial re-exe ution of the pro ess (this
is used in the analyzers of the CHIP environment of Cosyte

apa ity

[5℄ or CLPGUI

[1℄). This obliges to stop the exe ution of the observed pro ess (at least when
that is possible), and to give the ability to the observing pro ess to stop and
resume the observed pro ess. This leads to the idea sket hed in the introdu tion
of syn hronization primitives between pro esses, a kind "image freezing" whi h

makes it possible to

omplete the information at any moment, a

need. This also results in the need for a fun tion "a

ess to the

ording to the
urrent state".

It is important to note that with an ee tive or in remental tra e, keeping
a full

urrent state is then in

harge of the observing pro ess and not of the

observed pro ess. This assumes however that the observed pro ess
least re overy points in whi h full

ontains at

urrent state will be maintained and a

essible,

so as to allow the observing pro ess to resume the tra e and to be able to restart
from a full

urrent state. It is important to note that with a full ee tive tra e,

dierent from the full virtual tra e, to keep a full
pro ess will be an additional

urrent state in the observing

harge of this pro ess itself, be ause the tra er of

the observed pro ess then does not have any more obligation to

al ulate the

requested parameters expli itly (only the requested attributes are
This supposes however that the observed pro ess
points in whi h a full

omputed).

ontains at least re overy

urrent state will be preserved and a

essible. This may

allow the observing pro ess to resume the tra e and to be able to restart from a
full

urrent state. This aspe t is not treated here.

3

Observational Semanti s

One is interested in this se tion in the semanti s of the full tra e,

alled here

"observational semanti s".
The tra e does not explain anything. It is only a

olle tion of fa ts. The

question arises however to understand the tra e. For that one needs two levels of
semanti s. The rst level

orresponds to the des ription of the a tions and ob-

je ts appearing in the parameters and attributes of the tra es, i.e. a semanti s of
the observed data. The se ond level

orresponds to a kind of tra e explanation,

i.e. a semanti s des ribing how the values of the parameters at the moment
are derived from the values of the parameters of the moment
a tions
whi h a

at

t−1

t

and how the

are sele ted. Clearly this means that one has a model of the pro ess
urately des ribes the evolution of the tra e between two events. The

form of this semanti s is the subje t of another work in progress.
To read a tra e, one needs only the rst level of semanti s. Only the relations
between the parameters in the same state or attributes in the emitted tra e
events must be known. In the example of the Prolog tra e, the properties of the
obje t "proof-tree" must be known to understand the relation between the depth
of the tree and the tree itself. The semanti s of the tra e (full and/or in remental)
thus

ontains the des ription of the relations between the parameters whi h

relates the semanti s and the produ ed attributes. But to understand the tra e
omprehensively, it is ne essary to go further in the knowledge of the pro ess
itself.
What we

all here "observational semanti s" (OS) is the semanti s of the

tra er (the rst semanti s, although being part of the OS,

an be seen like a

semanti s of the tra e). It uses the semanti s of the obje ts and a tions of the
full tra e and

an be seen as an abstra t semanti s in the sense of Cousot [8℄. It

l ∈ dom(Σ) ∧ choice-point(Σ(l))
N ← l, S ← Σ(l)

ba k to

Fig. 1. A rule of the abstra

t model of Prolog Proof-Tree displayed in [13℄

is a kind of natural semanti s [9℄ whi h

an be expressed by a nite set of rules

of the form

a : Condition(S) → S ′ = a(S)
su h that any event of tra e et : (t, at , St+1 ) an be obtained starting from
the state St and the a tion at by appli ation of the rule a of the OS. The (set
of ) a tions a performed at hrono t is denoted at . This semanti s an take the
form of a stru tural operational semanti s [10℄ or of an evolving algebra [11℄
and being more or less rened, "big-step" or "small-step" [12℄. It is in fa t very
tempting to have a

omplete semanti s for the tra er in order to allow a

lear

implementation of it.
Coming ba k to the example of Prolog, a tra er augmented with the tra e
of

onstraints resolution (proof-tree, sear h-tree, labeling-tree and propagation),

alled Codeine, has been implemented in this manner on GNU-Prolog [13℄. An
abstra t model has been dened [14℄, whi h has been then implemented on several solvers [1℄. This made it possible to meet two prin ipal obje tives: portability
of the analyzers whose input data are based on the full tra e, and robustness of
the tra ers whose implementation is guided and improved by a good methodologi al approa h [15℄ based on a pre-spe ied rigorous semanti s.
It is useful however to note that a
would be a

omplete semanti s of the tra e, whi h

omplete formalization of the observed pro ess, is almost impossible

in pra ti e, be ause of the degree of renement that would imply. For example,
an attribute in luded in many tra es is the CPU time

onsumed by the pro ess

sin e the "beginning" of the tra e emission. To formalize its variations, in fa t
issued from the host system, would amount introdu ing into the observational
semanti s a model of the system in whi h the pro ess is exe uted.
Finally an OS should not be

onfused with a

whi h would make it possible to re all the
the sole initial state and its rules. The

omplete operational semanti s

ourse of the pro ess starting from

urrent full state is not su ient to

know whi h rule may apply. For example, the model developed for nite domain
onstraints resolution des ribed in [13℄
as at least one rule

ontains a set of operational rules su h

an be applied at ea h state, but whose

always pre ise enough to de ide how it

onditions are not

an be applied. So is the

ba k to

rule,

depi ted in the Figure 1.
It

ontains a

the new

ondition

l ∈ dom(Σ)

whi h must be satised, meaning that

urrent node belongs to the sear h-tree, but nothing says whi h node

must be sele ted. The sole knowledge of the full

urrent state (whi h in ludes the

urrent sear h-tree) is not su ient. The knowledge of the

urrent tra e event

is ne essary to know whi h is this new node and thus to know how this rule is
in fa t instantiated.

4

Tra er Driver and Evaluation

The idea to use a tra er driver was proposed by M. Du assé and J. Noyé sin e
the origin of Prolog [16℄ in the

ontext of logi

programming, then regularly de-

veloped and tested in various environments [17℄. The originality of this approa h
onsists in proposing that the full tra e should not be

ommuni ated in its in-

tegrity to an analyzer, but that this one re eives only the part of the tra e whi h
relates to it. Instead of broad asting "urbi et orbi" a full tra e that any analyzer
would have the task to lter, ltering is performed at the sour e level, i.e. by
the observed pro ess whi h behaves then like a server of tra es. The analyzer
is a

lient whi h restri ts himself to indi ate to the observed pro ess the tra e

whi h it needs indeed. The
pro esses then brings to
information: the

omplete separation of the observed and observing

onsider an ar hite ture server/ lient with ex hanges of

lient indi ates to the server the tra e it needs and the server

provides him only what it requires. The ltering of the tra e is no longer

arried

out by the analyzer, but by the observed pro ess. It is the task of the tra er
driver to perform all requested ltering and to dispat h the tra es requested by
the

lients. This ar hite ture as well as the ex hanges between the pro esses have

been des ribed in parti ular in [1℄ and [2℄. We will not go more into the details in
this extended abstra t. In addition, only the aspe ts related to the possibilities
of modulating the tra es emitted a
be

ording to the needs of the analyzers will

onsidered; the possibility previously mentioned to syn hronize the pro esses

will not be

onsidered here.

This approa h allows to redu e the size of the tra e emitted to a useful bare
minimum and thus to speed up the whole pro ess. In
to

onsider very large full tra es. This has also a

of the tra e. Beyond a

ompensation, it allows

ost whi h grows with the size

ertain size, the produ tion

ost of the tra e is likely to

be ome prohibitory. It is pre isely the question in whi h one is interested. Until
where

an one go into this approa h on a pra ti al level without slowing down

a pro ess ex essively and how? To get a more pre ise idea, one must take into
a

ount not only the time of tra e produ tion, but also how the tra e will be

used.
One ould think at rst sight that the fa t, for the observed pro ess, to have to
produ e a full tra e makes this approa h unrealisti . The server is indeed slowed
down by the simple fa t of having to

ompute a great number of parameters

whi h will perhaps never be used. This approa h would be thus very penalizing
for the pro ess instrumented with an expensive tra er whenever only a weak
portion of the full tra e would be used. On another side, and pre isely in this
ase, a

onsiderable e onomy is realized be ause of ltering at the sour e, and

the transmission of a limited tra e whose

osts of

oding and diusion are then

extremely redu ed. The idea is that in pra ti e the fa t of emitting only one
small part of the tra e, ltered at the sour e,

ompensates for the over

ost of

work mainly related to the updates of all the parameters of the full tra e in the
analyzed pro ess.

On the other hand, if many analyzers are a tivated simultaneously and use
at a given moment a tra e equivalent to a full tra e, the problem to produ e or
not the full tra e does not arise any more (it must in any

ase be produ ed), and

the question about the interest of using a tra er driver is worth to be posed. We
show that even in this

ase the driver

an save time.

Additionally another type of e onomy must be

onsidered whi h is

omple-

mentary to the previous one: the use of an in remental tra e as an ee tive tra e
instead of the virtual full tra e. In this

ase there is no loss of information (the

equivalent of the full tra e is still transmitted), but there is a redu tion of the
amount of data transmitted (a kind of data

ompression is used in order to

limit the size of the emitted data ow). In this later

ase the tra er performs a

kind of  ompression and the analyzer a kind of de ompression and both task
must be taken into a

ount in the analysis of the workloads. It will be shown

that the performan es of the tra er and the analyzers

an be inuen ed more by

this kind of load rather than by the size of the full tra e.
In order to be more pre ise, it is ne essary to analyze the repartition of work
within the various pro esses.
The times to take into a

ount for a detailed performan es analysis are times

on erning the pro ess itself, its tra er and its pilot on the one hand, and times
on erning one analyzer on the other hand (one must suppose here that, if there
are several analyzers, they are running with true parallelism):

Pro ess
Tra er and Driver
--------------- ------------------------------------|
| |
|
T_prog + T_ ore + T_ ond + T_extra t + T_en ode-and- om
Analyser
-----------------------------------------|
|
T_filter + T_de ode + T_rebuild + T_exe
From the side of the pro ess, tra er and driver:

 Tprog :

time devoted to the exe ution of the not instrumented program (or

instrumented but with dea tivated tra er).

 Tcore: additional exe

ution time of the pro ess on e instrumented to produ e

the full tra e and with a tivated tra er. It is a time devoted to the

onstru -

tion of the elements ne essary to a likely later extra tion of the parameters of
the

urrent state. This time is largely inuen ed by the size of the full tra e.

At this stage all
approa h, one

omputations must be performed be ause, in the presented

onsiders that it must be possible to produ e the full

state at any moment (in

urrent

ase in parti ular of dis ontinuous tra e). This time

is related to the form of the full tra e only and does not depend on what
will be emitted. If all the parameters of the full tra e are already part of the
pro ess, this time is just null.

 Tcond :

time of

he king of the

onditions dening the tra es to be emitted

for ea h analyzer (ltering). This time is null if there is no ltering (emission
of the full tra e).

 Textract : omputing time of the parameters requested during or after ltering.
 Tencode−and−com : time for formatting the tra e (en oding), possible ompression and emission.
Time spe i

Textract

and

to the driver

Tencode−and−com

Tcond .

orresponds to

Other times, namely,

Tcore ,

an be regarded as times related to the tra er.

It should be noti ed here that, in this approa h, the driver a ts only on
the

hoi e of the parameters and the attributes to be

tra e, i.e. on the

ontained in the ee tive

ommuni ated information. It does not have the possibility of

inuen ing the form of the attributes, for example the degree of  ompression
of the information. In fa t, this  ompression is

oded here in the form of the

attributes. The nature of the attributes (in remental information or not) is part
of the tra er and it

annot be modied or adapted through the tra er driver.

On the other side any additional

ompression algorithm used to redu e the size

of the information ow belongs to the stage of en oding. Generalizing this
idea, one

ould also

onsider the possibility to put into the tra e more abstra t

attributes, adapted to some more spe i
a redu ed size. The

use, su h that the whole tra e has

orresponding attribute

omputation time would thus be

related to the extra tion stage. This generalization is not studied here.
From the side of the analyzer:

 Tf ilter :

time of ltering by an analyzer. This time is null if ltering is per-

formed at the sour e (the tra e events sent to a parti ular analyzer

an

indeed be tagged at the sour e). In fa t by pre aution but mainly be ause of
la k of implemented tra er driver, many external analyzers will lter again
the tra e. However it is not ne essary to

 Tdecode:

ir umvent, as the time of
well. It must be
not be

onsider this

ase here.

time of de oding of the re eived tra e. This time is impossible to
oding and

ompared with the

ompletely eliminated. If

used, it is be ause it is

Tencode−and−com as
Tencode−and−com. It an-

ommuni ation

encode

part of

ompression/de ompression algorithms are

onsidered that, even if both times are

umulated,

one will save a substantial amount of time over the transmission.

 Trebuild :

time of rebuilding the full tra e starting from the ee tive tra e

( omputation of the urrent parameters starting from the emitted attributes).
This time must be
tributes. It is

ompared with

Textract ,

equilibrates most favorably with the

 Texec :

the

omputation time of the at-

onsidered that su h a time, even if

umulated with

Textract ,

ost of tra e emission.

exe ution time of the proper fun tions of the analyzer. With very

sophisti ated analyzers (as those used for data analysis for example), this
time

an be ome so important that it makes negligible the one

orresponding

to the tra e produ tion.
Example: Codeine, des ribed in [13℄, implements the generation of a full tra e
for the analysis of

onstraints resolution, as an extension of GNU-Prolog. The

urrent state

St

ontains (among other attributes): proof-tree, sear h-tree,

straints state and variables with their domains. For a
the full tra e see [1℄ ( alled in this proje t "generi
not generate a full tra e (as full as it

on-

omplete des ription of

tra e"). Even if Codeine does

ould be possible), the Codeine tra e is

onsiderably ri her than the simple Byrd's tra e of GNU-Prolog whi h is stri tly
ontained. Only an in remental tra e is generated, and only the proof-tree and
the

onstraints and variables states

urrent state of the pro ess (the

an be rebuilt later starting just from the

ost of extra tion is redu ed to the

proper data management realized by the tra er). To obtain the

ost of the

urrent sear h-

tree the pro ess would have to be re-exe uted partially, therefore it would be
ne essary to freeze its
nently a

urrent exe ution. The

ost of management of a perma-

essible sear h-tree at any moment would be

of its size. On the other hand an analyzer

learly intra table be ause

an, using the produ ed in remental

tra e, maintain all these obje ts permanently (obtaining
useful for it). Codeine also

St

or those parameters

ontains a tra er driver su h that the denitions of

the tra es to be emitted (spe i ation of the emitted tra e) are stored in a data
le whi h must be provided before the pro ess starts.
Times are distributed as follows:
From the side of the pro ess, tra er and driver:

 Tprog : exe
part of

 Tcore:

ution time of GNU-Prolog with "swit hes" of the tra er (a small

Tcore

of negligible duration in general).

time of

onstru tion of the parameters of the full Codeine tra e ( ol-

le ting of all data useful to extra t the full tra e); a kind of GNU-Prolog
plug-in.

 Tcond : time of ltering the full tra e to sele
 Textract : omputing time of the attributes

t all the requested tra es.
orresponding to the parameters

requested during ltering.

 Tencode−and−com :

omputing time of the attributes

orresponding to the re-

quested parameters, en oding (XML format or Prolog term) of the emitted
tra e, and emission time of the in remental tra e.
From the side of the analyzers: experiments in the framework of the OADymPPaC proje t with sophisti ated analyzers (intensive visualization of graphs,
visual data analyses) revealed the following

 Tf ilter

and

Tdecode :

osts.

both times are intri ate in a synta ti

(XML) of the full tra e. Re-ltering, a part of whi h
But the driven tra er approa h

analysis module

ould have been avoided.

ould not be taken into a

ount in the

analyzers built during this proje t.

 Trebuild :

time of

onstru tion of the parameters of the full tra e (variables

domains, a tive

onstraints set, sear h-tree ...). This time grows (non esti-

mated fa tor) a

ording to the size of the data, sometimes related to the size

of the tra e, with a

onsiderable slow down of the analyzer during the read-

ing of the tra e . The low speed of an analyzer may

ause, in the

ase of

analysis of the tra e on the y, a strong slow down of the observed pro ess.

 Texec :

time of

onstru tion of the obje ts to be visualized (graphs, data

tables). These times

an grow exponentially a

The e ien y of the used algorithms is

ording to the size of the data.

ru ial here. This

an also

ause a

slow down of the pro ess, and pleads in favor of a preliminary treatment
of information before transmission (for example, sele tion of distinguished
nodes to put in the tra e to redu e the size of a drawn graphs, or to

olle t

groups of variables as a unique attribute to redu e the number of lines in a
matrix).
It was been shown experimentally in [3℄ that the behavior of the Codeine
tra er with the full tra e above

ompares favorably with the behavior of GNU-

Prolog with the Byrd's tra e only. Furthermore, the ltering realized by the
tra er driver does not prejudi es the performan es.
We give here a theoreti al justi ation to this result, showing that this approa h, already justied experimentally,

an also be justied theoreti ally.

In [2℄ L. Langevine observes that ltering the tra es all together is more
ee tive than to lter them one after the other. This

omes from the fa t that

running several automata together may be more e ient than running one only.
Indeed the essen e of ltering relates to simplied
sele t rst the tra e events

ner additional ltering will be thus
of events mu h more redu ed. One
a tra e whose language
to

onditions whose role is to

ontaining the ports requested by an analyzer. A
arried out thereafter but on a number

an admit that this rst ltering relates to

orresponds to a regular language. It is then possible

onsider that ea h lter is itself a regular expression whose re ognition on

the full tra e
Filtering

an be done using a non deterministi

nite-state automaton.

orresponds then to the re ognition task by a union of as many nite-

state automata than there are a tive analyzers requesting a tra e. However the
resulting automaton, on e optimized,

an be mu h more e ient than the most

e ient of the automata asso iated with a single analyzer (the union of the
automata

an be more e ient in terms of

omputation steps than only one of

them [18℄). As these operations of ltering are extremely frequent, be ause they
apply to all the tra e events, the speed up

an be

onsiderable.

We are now in position to analyze the respe tive workloads.
First observe that respe tive times of both sides may be

onsidered as

u-

mulative or not, depending whether the respe tive pro ess are run sequentially
or with true parallelism. In the later
essors (a situation whi h

an be

ase, if all pro ess are run on dierent pro-

onsidered with su h an approa h), only the

slowest pro ess must be taken into a

ount to evaluate the exe ution time of the

whole system.

 Tprog

and

Tcore

These times

on one side,

Texec

on the other side.

orrespond to times spe i

to the tra er and the analyzers (the

slowest analyzer has the main inuen e on the exe ution time). These times

Tcore
Tf ilter

are in ompressible and

 Tcond

on one side and

depends only on the size of the virtual tra e.
on the other side.

At least one of these times must be null, and, if the ltering is at the sour e,
the performan e

an be improved. In any

whatever is the size of the full tra e,

 Textract

on one side and

These times

Trebuild

ases this time appears negligible,

ompared with the other times.

on the other side.

orrespond respe tively to the

omputation of the attributes

from the parameters and re ipro ally. If one

an redu e the extra tion time

thanks to the ltering ( onsidering the low number of sele ted tra e events
and attributes, and the fa t that the most of the parameters
work is already in luded in

Tcore ),

the time of rebuilding

omputation

an be very im-

portant and will probably be signi antly greater than the extra tion time.

 Tencodea ndc om

on one side and

These times

Tdecode

on the other side.

an be important, but the interest lies in the fa t that the

prots realized on the
ompensates the

ommuni ation time (redu ed emitted volume) largely

oding/de oding times.

To summarize, the tra er and the slowest analyzer are the main fa tors inuen ing the whole performan e and they
sides

an in rease the workload of both

onsiderably. However the use of a tra er driver and of te hniques of tra e

ompression make it possible to

ompensate partially, but sometimes in very

ee tive manner, the over- osts related to the use of a full tra e.

5

Con lusion

We introdu ed the

on ept of full tra e in order to take into a

possibilities of analysis of a dynami

ount the multiple

pro ess. The analyzed pro ess is instru-

mented with, in addition to its tra er, a tra e driver, and the analyzers have
the possibility of addressing orders to the driver. An ar hite ture
then

lient/server is

onsidered to des ribe the intera tions between the pro esses analyzers and

the analyzed pro ess. This enabled us to ta kle the problem of the evaluation of
this approa h in terms of e ien y.
We tried to appre iate how the introdu tion of a tra er driver
the global e ien y of the analysis of a dynami

ould improve

pro ess using several analyzers

observing the pro ess in a simultaneous way. We initially observed that a full
tra e

ould be parti ularly expensive to produ e, but that part of this

ould be transferred, without loss of

apa ity of analysis (the full tra e

retrieved by the analyzers), on the analyzers. The most unfavorable
of e ien y

ost

an be

ase in term

orresponds to the situation where the equivalent of a full tra e must

be built, extra ted and emitted. In this

ase, the full tra e is in fa t a union of

all the redu ed tra es requested by several analyzers. We showed that, even in
this

ase, a ltering realized by a tra er driver was able to bring an important

bene e. Our observations, during the proje ts DiSCiPl [5℄ and OADymPPaC
[1℄, using very sophisti ated analyzers as powerful tools for visualizations as well
([19℄ [20℄), also showed that the limits of performan e
analyzers that tra er, even with a full tra e.
This study opens nally on a series of questions:

ame often more of the

 How deep is it possible to implement a very broad full tra e?
ourse the limits of the approa h are obvious: the

Of

on ept of full tra e is

meaningful only with regards to a family of possible analyses, well known
and sele ted in advan e. Nothing guarantees a priori that an additional instrumentation of the observed pro ess will never be ne essary. But beyond
this aspe t, the interesting question relates to the feasibility of the implementation of a very ne grained full tra e. On one side indeed, one will be
able to

ompensate for

ertain produ tion

osts of su h large tra e, by emit-

ting an ee tive tra e of limited size; but on the other side, the analyzers
(whose use

an be temporary or ex eptional) will be loaded with most of

time of development/re-building of the full tra e (ne essary, even if it uses
only a part of it) and will o

asionally slow down the observed pro ess.

 Whi h intera tion language to use and whi h dialogue between
the driver and the analyzers? This question has been little ta kled
here and mainly remains out of the s ope of this arti le. The tenden y however is with the use of a language like XML. It is the way

hosen by the

OADymPPaC proje t, and the possibility of redu ing the ow of tra e to its
bare minimum en ourages this. Nevertheless our experiments showed that
the
data

ommuni ation needed to be optimized by
ompression with spe i

tra e

ombining usual methods of

ompression like using in remental at-

tributes, but also by introdu ing more abstra t attributes in the tra e. This
leads to the idea that the dialogue between the involved pro esses, limited
here to the

hoi e of the tra e events and the attributes in the tra e, and

apa ities of syn hronization, must be extended su h that it allows also to



inuen e the design of the attributes themselves.
Finally a

ru ial question related to the

omprehension of the tra e.

to understand a tra e, or how to des ribe its semanti s ?

How
If the

semanti s of the tra e (and of the tra er), or at least a large part of it, is
given a priori (be ause one has a model for the observed pro ess), then the
omprehension of the tra e as well as the implementation of the tra er are
largely fa ilitated. In the opposite
or arti ial

ase - and it is the

ase for many natural

omplex pro esses - one has only vast tra es to study. Even in

the elds of programming languages where semanti s seems better

ontrolled

a priori, one tries to analyze a program behavior by trying to understand its
tra es. Thus one sees stinging the usefulness of general te hniques based on
data mining [21℄ or on Web mining [22℄ for su h purposes. However one must
re ognize that any full tra e will probably always in lude portions es aping
any kind of des ription based on formal semanti s.

Referen es
1. Deransart, P., & al: Outils d'Analyse Dynamique Pour la Programmation par
Contraintes (OADymPPaC). Te hni al report, Inria Ro quen ourt and É ole des
Mines de Nantes and Insa de Rennes and Université d'Orléans and Cosyte and
ILOG (2004) Projet RNTL. http:// ontraintes.inria.fr/OADymPPaC .

2. Langevine, L., Du assé, M.: A Tra er Driver for Hybrid Exe ution Analyses. In
Press, A., ed.: Pro eedings of the 6th Automated Debugging Symposium. (2005)
3. Langevine, L., Du assé, M.: A Tra er Driver for Versatile Dynami Analyses of
Constraint Logi Programs. In Serebrenik, A., Muñoz-Hernandez, S., eds.: Pro eedings of the 15th Workshop on Logi -based Methods in Programming Environments
(WLPE'05), a pre- onferen e workshop of ICLP'05, Sitges, Spain (2005) Computer
Resear h Repository s.SE/0508105.
4. Langevine, L., Du assé, M.: A Tra er Driver for CLP: Debugging, Monitoring and
Visualization of an Exe ution from a Single Tra er. In Demoen, B., Lifs hitz, V.,
eds.: Pro . of the 20th Int. Conf. on Logi Programming, (ICLP'04). Number 3132
in LNCS, Saint-Malo, Fran e (2004) 462463
5. Deransart, P., Hermenegildo, M., Maªuszy«ski, J., eds.: Analysis and Visualisation
Tools for Constraint Programming. Number 1870 in LNCS. Springer Verlag (2000)
6. GNU-Prolog: A CLP(FD) System Based on Standard Prolog (ISO) developed by
D. Diaz (2003) http://gprolog.sour eforge.net/ Distributed under the GNU li ense.
7. Byrd, L.: Understanding the ontrol ow of Prolog programs. Logi Programming
Workshop (1980)
8. Cousot, P.: Abstra t Interpretation. Te hnique et S ien e Informatiques 19 (1994)
19
9. Kahn, G.: Natural Semanti s. In Brandenburg, F.J., Vidal-Naquet, G., Wirsing,
M., eds.: Pro eedings of STACS, Springer (1987) also INRIA, RR 416, Natural
Semanti s on the Computer.
10. Plotkin, G.: A Stru tural Approa h to Operational Semanti s. TR DAIMI FN 19,
Computer S ien e Department, Aarhus University, Aarhus, Denmark (1981)
11. Gurevit h, Y.: Evolving algebras, a tutorial introdu tion. Bulletin of the European
Asso iation for Theoreti al Computer S ien e 43 (1991) 264284
12. Lu as, S.: Observational Semanti s and Dynami Analysis of Computational Proess. RR 00/02, E ole Polyte hnique, Laboratoire d'Informatique, LIX, Palaiseau
(Fran e) (2000)
13. Langevine, L., Du assé, M., Deransart, P.: A Propagation Tra er for GNU-Prolog:
from Formal Denition to E ient Implementation. In Palamidessi, C., ed.: Proeedings of the 19th International Conferen e on Logi Programming, ICLP'03,
Mumbai, India (2003)
14. Langevine, L., Deransart, P., Du assé, M.: A Generi Tra e S hema for the
Portability of CP(FD) Debugging Tools. In Apt, K., Fages, F., Rossi, F., P.,
S., Van za, J., eds.: Re ent Advan es in Constraints. Number 3010 in Le ture
Notes in Arti ial Intelligen e. Springer Verlag (2004) Sele ted papers of the Joint
ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint
Logi Programming.
15. Du assé, M., Langevine, L., Deransart, P.: Rigorous design of tra ers: an experiment for onstraint logi programming. In Ronsse, M., Boss here, K.D., eds.:
Pro eedings of the 5th International Workshop on Automated and Algorithmi
Debugging, AADEBUG'03, Ghent, Belgium (2003) Computer Resear h Repository s.SE/0310042.
16. Du assé, M., Noyé, J.: Logi Programming Environments: Dynami Program Analysis and Debugging. The Journal of Logi Programming 19/20 (1994) 351384
17. Du assé, M.: Tra e S hemata for (Multi-language) Dynami Analysis. In Choi,
J.D., Ryder, B., Zeller, A., eds.: Dagstuhl Seminar 03491, "Understanding Program
Dynami s", Saint-Malo, Fran e, Dagstuhl, Germany (2003)
18. Hop roft, J.E., Ullman, J.D., eds.: Introdu tion to Automata Theory, Languages,
and Computation. Computer S ien e. Addison-Wesley (1979)

19. Baudel, T., & al: Visual CP, Referen e Manual (2004) Manufa tured and distributed by Ilog, http://www2.ilog. om/preview/Dis overy/ .
20. Ghoniem, M., Jussien, N., Fekete, J.D.: VISEXP: Visualizing Constraint Solver
Dynami s Using Explanations. In Barr, V., Markov, Z., eds.: Pro . of the 17th Int.
of the Florida Arti ial Intelligen e Resear h So iety Conferen e (FLAIRS'04),
AAAI Press (2004)
21. Denmat, T., Du assé, M., Ridoux, O.: Data Mining and Cross-Che king of Exe ution Tra es. A reinterpretation of Jones, Harrold and Satsko test Information
Visualization. RI 1743, IRISA, Rennes (Fran e) (2005)
22. Zaidman, A., Calders, T., Demeyer, S., Paredaens, J.: Applying Webmining Te hniques to Exe ution Tra es to Support the Program Comprehension Pro ess. In
So iety, I.C., ed.: Pro eedings of the 9th European Conferen e on Software Maintenan e and Rengineering (CSMR 2005), Man hester, UK (2005) 134142

