Information Technology Reference
In-Depth Information
a
b
c
d
e
f
Fig. 4.
Intra- and inter-path interference among vertices
the use of function
F
which may not represent correct system's behaviour. Com-
puting function
F
with high accuracy is desirable because even a small reduction
in overhead will have large benefit in the long run of a monitor.
For the rest of this paper, let
CFG
=
V,v
0
,A,w,v
f
,
be a control-flow
graph corresponding to a program
P
. Each vertex corresponds to a critical basic
block containing one critical instruction. The definitions of
V
,
v
0
,
A
,
w
,and
v
f
correspond to the Definition 1 (see Figure 3(b) for an example).
F
3.4 The Optimization Problem as an Integer Linear Program
The ILP problem is of the form:
⎧
⎨
Minimize
c.
z
⎩
Subject to
A.
z
≥
b
where
A
(a rational
m
n
matrix),
c
(a rational
n
-vector) and
b
(a rational
m
-vector) are given, and
z
is an
n
-vector of integers to be determined. In other
words, we try to find the minimum of a linear function over a feasible set defined
by a finite number of linear constraints. It can be shown that a problem with
linear equalities and inequalities can always be put in the above form, implying
that this formulation is more general than it might look.
×
Objective Function.
The objective function for our ILP model is:
minimize
(
C
event
+
C
switch
+
C
sample
)
(4)
We now describe how we map the optimization objective (Equation 4) by in-
troducing ILP variables and computing each of three costs in terms of these
variables and given elementary costs for a CFG.
