\section{Results}


\begin{figure}[!t]
%\renewcommand{\baselinestretch}{0.5}
\noindent
{\scriptsize
\begin{tabular}{c l @{} c }
\multicolumn{3}{c}{Attainment: Overall} \\\hline
Rank & Algorithm & 50\% \\
\hline
\rowcolor[rgb]{0.8,0.8,0.8}1& K2-OPT & \boxplot{100.000000}{0.000000}{100.000000}{0.000000}{100.000000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}1& K1-OPT & \boxplot{99.400000}{0.600000}{100.000000}{0.000000}{100.000000} \\
1& KEYS2 & \boxplot{99.400000}{0.600000}{100.000000}{0.000000}{100.000000} \\ 
1& KEYS & \boxplot{99.500000}{0.500000}{100.000000}{0.000000}{100.000000} \\ 
\hline
\multicolumn{3}{c}{Attainment: Largest Model} \\\hline
Rank & Change & 50\% \\
\hline
\rowcolor[rgb]{0.8,0.8,0.8}1& K2-OPT & \boxplot{100.000000}{0.000000}{100.000000}{0.000000}{100.000000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}1& K1-OPT & \boxplot{99.400000}{0.600000}{100.000000}{0.000000}{100.000000} \\ 
1& KEYS2 & \boxplot{99.400000}{0.600000}{100.000000}{0.000000}{100.000000} \\ 
1& KEYS & \boxplot{99.500000}{0.500000}{100.000000}{0.000000}{100.000000} \\ 
\end{tabular}
}
\caption{Attainment: Maximum attainment achieved at lowest cost (normalized 0..100\%):  optimizations are shaded.}
\label{fig:att}
\end{figure}


\begin{figure}[!t]
\renewcommand{\baselinestretch}{0.5}
\noindent
{\scriptsize
\begin{tabular}{c l @{} c }
\multicolumn{3}{c}{Cost: Overall} \\\hline
Rank & Algorithm & 50\% \\
\hline
1& KEYS & \boxplot{0.000000}{0.600000}{0.600000}{9.400000}{10.000000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}2& K1-OPT & \boxplot{0.000000}{1.900000}{1.900000}{11.300000}{13.200000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}3& K2-OPT & \boxplot{0.000000}{2.100000}{2.100000}{15.000000}{17.100000} \\ 
3& KEYS2 & \boxplot{0.000000}{2.100000}{2.100000}{15.300000}{17.400000} \\ 
\hline
\multicolumn{3}{c}{Cost: Largest Model} \\\hline
Rank & Change & 50\% \\
\hline
1& KEYS & \boxplot{1.700000}{6.500000}{8.200000}{1.800000}{10.000000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}2& K1-OPT & \boxplot{1.400000}{8.900000}{10.300000}{2.900000}{13.200000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}3& K2-OPT & \boxplot{10.700000}{2.700000}{13.400000}{3.700000}{17.100000} \\ 
3& KEYS2 & \boxplot{1.300000}{12.000000}{13.300000}{4.100000}{17.400000} \\ 
\end{tabular}
}
\caption{Cost: Minimum cost to achieve maximum attainment (normalized 0..100\%):  optimizations are shaded.}
\label{fig:cost}
\end{figure}


\begin{figure}[!t]
%\renewcommand{\baselinestretch}{0.5}
\noindent
{\scriptsize
\begin{tabular}{c l @{} c }
\multicolumn{3}{c}{Runtime: Overall} \\\hline
Rank & Algorithm & 50\% \\
\hline
\rowcolor[rgb]{0.8,0.8,0.8}1& K2-OPT & \boxplot{0.000000}{20.200000}{20.200000}{79.800000}{100.000000} \\ 
2& KEYS2 & \boxplot{0.000000}{23.700000}{23.700000}{76.300000}{100.000000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}3& K1-OPT & \boxplot{0.000000}{36.700000}{36.700000}{13.300000}{50.000000} \\ 
4& KEYS & \boxplot{0.000000}{97.200000}{97.200000}{2.800000}{100.000000} \\ 
\multicolumn{3}{c}{Runtime: Largest Model} \\\hline
Rank & Change & 50\% \\
\hline
\rowcolor[rgb]{0.8,0.8,0.8}1& K2-OPT & \boxplot{8.300000}{0.100000}{8.400000}{0.100000}{8.500000} \\ 
2& KEYS2 & \boxplot{1.700000}{6.900000}{8.600000}{0.000000}{8.600000} \\ 
\rowcolor[rgb]{0.8,0.8,0.8}3& K1-OPT & \boxplot{2.900000}{33.200000}{36.100000}{1.100000}{37.200000} \\ 
4& KEYS & \boxplot{7.500000}{90.500000}{98.000000}{2.000000}{100.000000} \\ 

\end{tabular}
}
\caption{Runtime: Time to produce a solution (normalized 0..100\%):  optimizations are shaded.}
\label{fig:time}
\end{figure}

Our experiments with KEYS, KEYS2, and their optimizations are
summarized in Figures~\ref{fig:cost}, \ref{fig:att}, and \ref{fig:time}.
In those figures:
\bi
\item All results are normalized to run 0..100, 0..max, where max is 
calculated by running the model with all mitigations set. 
\item Each row shows the 25\% to 75\% quartile range of the normalized 
scores collected during the simulation. 
\item The median result is shown as a black dot. 
\item All the performance scores  get {\em better} when the observed 
scores get {\em smaller}.
\item The ``none'' row comes from Monte Carlo simulations of the
current ranges, without any changes. 
\item The top sumarizes the performance of the algorithms across all
fifteen randomly-generated models, giving us a general indication of
their performance on small and large models.
\item The bottom part of each
figure depicts the performance of each algorithm specific to their
execution on the largest of our models, model5\_16.c (see
Figure~\ref{fig:ddpModels}).  
\item ``K1-OPT'' and ``K2-OPT'' denote the runs of
the optimized version of KEYS and KEYS2 respectively.
\ei

In each figure, the rows are sorted by the number of times an
algorithm scores below ({\em looses} to) another. In order to assess
number of {\em losses}, we used the Mann-Whitney test at 95\%
confidence (this test was chosen due to (a) the random nature of Monte
Carlo simulations which results in non-paired tests; and (b) ranked
tests make no assumption about the normality of the results). Two rows
have the same rank if there is no statistical difference in their
distributions.  The shaded rows in Figures~\ref{fig:cost},
\ref{fig:att}, and \ref{fig:time} identify our latest optimizations.

In terms of attainment, Figure~\fig{att} shows that it is consistently
maximized across all algorithms with no significant differences among
them. They all achieve (very close to) the maximum possible attainment
indicating that our new version of the algorithms do not affect the
performance on this aspect. It is important to note that achieving
maximum requirements attainment simplifies our analysis because it
reduces the dimensionality of the resuls such that we can concentrate
on the other two aspects of this study, cost and runtime reduction.

The first differences among algorithms start to appear when we look at
cost reduction. Not surprisingly, \fig{cost} shows the
original KEYS as the best algorithm to reduce costs. What strikes us a
surprising is that our K1-OPT has a slightly lower performance than
KEYS given that both select their {\em keys} based on the same number
of simulations. We expected to see a tie similar to the performances
of KEYS2 and K2-OPT. They perform, on average, very close to each
other, but K2-OPT is more stable (lower variance). This phenomenon may
be explained by the fact that at each era K2-OPT is selecting {\em
  keys} from half of the same instances from which the previous {\em
  key} was selected. That might also explain the slim decrease in
average cost minimization performance by K1-OPT, but it needs further
study.


\begin{figure}
\begin{center}
\includegraphics[width=3in]{modszvsrt.png}
\end{center}
\caption{Runtime (secs) Vs. model size increase (LOC\%)}
\label{fig:RTvsSz}
\end{figure}

The third and main aspect of our study is the runtimes. The main goal
of our study is the reduction of the optimization runtimes so that
results can be obtained in near real-time. \fig{time} shows
results very close to our expectations. Overall, applying our
optimization improving technique on both KEYS and KEYS2 for the
largest model results in shorter runtimes. In the case of KEYS, K1-OPT
reduces the average execution time to 36.5 seconds from 99 seconds. A
63\% runtime speedup. K2-OPT also improves KEYS2 runtime on the
largest model but not as much. KEYS2 takes on average 8.7 seconds
while K2-OPT takes 8.5 seconds. A speedup of 2.3\%.

A more clear view of the speed gains achieved by our improvement
technique can bee seen in \fig{RTvsSz}. Note the big difference in the
KEYS and K1-OPT slopes. Following the trend, the bigger the model the
more KEYS beneffits from our improvement. The same applies to KEYS2 and
K2-OPT, but at the model sizes we are running our experiments it is barely
apparent.

Although our technique's gain for KEYS2 is not as large as it is for
KEYS, it is statistically significant at 95\% confidence level and we
believe it increases as the models become even larger. Furthermore,
applying our simple speed up technique is easy and maintains the
performance of the other aspects of the model-optimization algorithms
within acceptable margins.
