Print indd

4.2
Results
While the estimated time is deterministic for each run using the same config-
uration options, the required simulation time is variable due to running the
simulation on a computer with a preemptive operating system. Therefore, each
configuration was measured ten times on the same computer with no additional
load and the average simulation time was calculated.
The raw data used for calculating the metric can be seen in Figs.
4
and
5
.
The latter shows the simulation time required for each iteration while the first
one depicts the estimated time. As a reference, the TS and O3 values are also
drawn. The plots confirm the previously stated behavior differences. While the
estimated runtime of the radar algorithm converges fast and does not change

---

94
S. Rachuj et al.
Fig. 2. Plot with the two nor-
malized values used for the
axes that shows when a quo-
tient of the values is consid-
ered better or worse than the
TS and O3 reference
Fig. 3. The value for the metric of both real
world algorithms depending on the amount of
accurately executed iterations. The reference
value is depicted in gray.
much from 500 accurately analyzed iterations upwards, the HEVC algorithm
has two points where the estimated runtime decreases tremendously. On the
other hand, the simulation time increases in this range while the radar has only
small fluctuations which can be traced back to the behavior of the host operating
system. It has to be remarked that the estimated time of radar algorithm further
increases when using more accurate iterations. However, this means a number of
several tens of thousands and is not shown in the figures. The simulation time
only rises moderately in this range. For comparison, the total iteration count of
the longest loop within our example radar scenario is around 740,000 meaning
that only a very small part of the actual runtime was analyzed accurately.
Figure
3
shows the final values of the metric presented in the previous section.
The numbers of the different algorithms depending on the number of iterations a
loop was executed accurately before switching to the instruction accurate model
are depicted. For the radar algorithm the new methodology converges really fast,
since it already reaches its maximal accuracy per time with just 500 accurate
iterations of the outer-most loops. On the other hand, for the HEVC algorithm,
the technique performs worse than the O3 and TS model when only running less
than 3000 iterations accurately. However, with 3000 exact iterations, the value
rises above the reference. This can be explained by certain loops within the
HEVC which have a different runtime characteristic above a certain threshold.
When executing iteration 2657 the loop exhibits a greater processing time than
all iterations before which results in a dramatic increase in estimated accuracy.
Cases like this having a loop displaying a huge difference in runtime between
two iterations are only correctly analysable with the methodology when a more
detailed examination of the CFG is performed. Due to the rising simulation time
when emulating the loop iterations with the greater runtime, the metric results
get worse again and approach the reference while still staying slightly above.
The loop having the greatest iteration count of the HEVC algorithm spins is
executed more than 114,000 times.

---

A Hybrid Approach for Runtime Analysis
95