Information Technology Reference
In-Depth Information
Moreover, each of the algorithms performed state estimation using the same HMM that
was used to generate the traces in the first place (i.e., the HMM of Figure 4). In this
way, we eliminated the imprecision that might have occurred as a result of re-learning
an HMM from the traces, thereby giving each algorithm the opportunity to perform state
estimation as accurately as it can. The fact that we used a predefined HMM to drive the
micro-benchmark from which we collected the traces allowed us to also log the current
state of the HMM and the DFA along with each emitted observation symbol.
6.1
Execution Time and Memory Usage
We conducted experiments aimed at understanding how the number of particles affects
the execution time and memory usage of the RVPF algorithm, and how RVPF compares
to RVSE and AP-RVSE in terms of these performance measures. For all our experi-
ments, we used both the original HMM (Figure 4) and an additional 10-state HMM
learned from the micro-benchmark-generated traces using the Baum-Welch algorithm.
One of our first tests was to measure the execution time of AP-RVSE for different gap
lengths (GLs) and gap frequencies (GFs). As expected, in all cases, AP-RVSE always
had nearly the same execution time, and was faster than RVPF and RVSE. This was true
even when there were no gaps and only two particles were used by RVPF.
The speed of AP-RVSE, however, comes at a price of high memory usage, which is
several orders of magnitude higher than that of RVSE and RVPF.
Ta b l e 1 .
Memory consumption in bytes of RVSE, AP-RVPF (with accuracy parameter
=0
.
1)
and RVPF (for 150 and 350 particles)
RVP F (
N
p
=150
)
RVP F (
N
p
= 350
)
Algorithm
RVS E
AP-RVSE
Original 5-state HMM
480
361,240
3,380
6,580
Learned 10-state HMM
960
764,560
5,960
9,160
As Table 1 shows, RVSE uses a relatively small amount of memory, only for storing
the HMM and DFA matrices. For RVPF, the amount of required memory is a linear
function of the number of particles
N
p
and was measured to be 16
·
N
p
+ 980 bytes
in case of the original 5-state HMM and 16
N
p
+ 3560 bytes in case of the learned
10-state HMM. In case of the original HMM, with 150 particles RVPF requires around
100 times less memory than AP-RVSE. For the learned HMM and 350 particles, the
memory consumption of RVPF is still around 80 times lower than that of AP-RVSE.
We also compared the speed of RVPF to the speed of RVSE. Instead of reporting abso-
lute execution times, we used the execution time of RVSE as the basis for the comparison
and determined the number of particles for which RVPF runs exactly as fast as RVSE.
For varying GFs and GLs 1-3, we first measured the execution time of RVSE. We then
measured the execution time of RVPF with an increasing number of particles until we
found the number of particles for which RVPF is exactly as fast as RVSE.
Figure 5 shows that the execution time of RVPF relative to RVSE improves mono-
tonically with respect to the GF, leveling off and reaching a maximum value at a GF of
·
