Information Technology Reference
In-Depth Information
program statements and instructions. The number of memory locations and variables
must be estimated. These problems become more challenging as the compiler puts
more and more effort into optimizing the program.
Some aspects of program performance can be estimated by looking directly at the
program. For example, if a program contains a loop with a large, fixed iteration bound,
or if one branch of a conditional is much longer than another, then we can get at least a
rough idea that these are more time-consuming segments of the program. However, a
precise estimate of performance also relies on the instructions to be executed because
different instructions take different amounts of time. The following snippet of code
30
is a data-dependent program path with a pair of nested if statements:
if
(
a
||
b
)
{
/
∗
test 1
∗
/
if
(
c
)
/
∗
test 2
∗
/
{
x
=
r
∗
s
+
t
;
/
∗
assignment 1
∗
/
}
else
{
y
=
r
+
s
;
/
∗
assignment 2
∗
/
}
z
=
r
+
s
+
u
;
/
∗
assignment 3
∗
/
}
else
{
if
(
c
)
/
∗
test 3
∗
/
{
y
=
r
t
;
/
∗
assignment 4
∗
/
}
}
One way to enumerate all the paths is to create a truth table structure in which the
paths are controlled by the variables in the if-conditions, namely, a, b, and c.
Results for all controlling variable values follow:
a
b
c
ath
0
0
0
test 1 false, test 3 false: no assignments
0
0
1
test 1 false, test 3 true: assignment 4
0
1
0
test 1 true, test 2 false: assignments 2, 3
0
1
1
test 1 true, test 2 true: assignments 1, 3
1
0
0
test 1 true, test 2 false: assignments 2, 3
1
0
1
test 1 true, test 2 true: assignments 1, 3
1
1
0
test 1 true, test 2 false: assignments 2, 3
1
1
1
test 1 true, test 2 true: assignments 1, 3
Notice that there are only four distinct cases: no assignment, assignment 4, assign-
ments 2 and 3, or assignments 1 and 3. These correspond to the possible paths through
the nested ifs; the table adds value by telling us which variable values exercise each of
these paths. Enumerating the paths through a fixed-iteration for a loop is seemingly
simple.
After the execution path of the program is calculated, the execution time of the
instructions executed along the path must be measured. The simplest estimate is to
30
http://www.embedded.com/design/multicore/201802850
Search WWH ::
Custom Search