\chapter{Experiments}
\label{chap:Experiments}

In this chapter, the performance and behavior of PSG will be thoroughly analyzed and described. In the first section, the process of tuning the algorithm's parameters is discussed. With all but one of the parameters fixed at their optimal values, we show some general performance characteristics in the second section before moving on to the third section, where scalability and speedup are evaluated, the two most important characteristics of any parallel system. In the fourth section we compare the performance of PSG to that of a random search algorithm. Finally, the last section rounds off the chapter by evaluating the \emph{real} fault coverage obtained when cellular automata evolved by PSG are used as test pattern generators for BIST circuitry.

All experiments in this chapter were performed on the ``star'' computing cluster installed at the Department of Computer Science and Engineering of the Faculty of Electrical Engineering, Czech Technical University. The cluster gets its name from the topology of its interconnection network: the network uses a central switch and therefore resembles a star. The system falls into the ``cluster of workstations'' category of parallel systems: a collection of PC-based machines connected by a local network. Detailed parameters of the cluster are given in \autoref{tab:Star}.
\begin{table}[htb]
	\sffamily
	\begin{center}
		\begin{tabular}{|l|l|}
			\hline
				\textbf{Number of machines} 							& 8 \\
			\hline
				\textbf{Number of processors per machine} & 4 (two dual-core CPU's) \\
			\hline
				\textbf{Total number of CPU's} 						& 32 \\
			\hline
				\textbf{CPU type} 												& Opteron 2218 (AMD K8 architecture) \\
			\hline
				\textbf{Memory per machine} 							& 4 GiB \\
			\hline
				\textbf{Networking technology} 						& InfiniBand, 10 Gb\,s\textsuperscript{-1} \\
			\hline
				\textbf{Operating system} 								& Linux kernel 2.6.16, x86-64 ISA \\
			\hline
				\textbf{Communication library}						& OpenMPI version 1.2.5 \\
			\hline
		\end{tabular}
		\caption{Parameters of the ``star'' computing cluster.}
		\label{tab:Star}
	\end{center}
\end{table}



\clearpage
\section{Parameter tuning}
\label{sec:ParameterTuning}
Any evolutionary algorithm stands or falls with the choice of its parameters and selecting or \emph{tuning} the parameters is often the most time-consuming part of an algorithm design. In \autoref{sec:SelfAdaption} we saw that there are some methods by which one can reduce the number of parameters to be tuned, but the fact remains that there will always be some parameters that have to be tuned; there is no such thing as a ``tuneless'' algorithm.

In this section we will describe the process of parameter tuning for PSG. The following parameters were addressed:
\begin{enumerate}
	\item $\epsilon$, the probability reward and penalty given during tournaments.
	\item \texttt{convergenceThreshold}, the probability level at which convergence is determined for any allele.
	\item $X_0$, the number of alleles sent in the first migration event.
	\item $Y_0$, the number of alleles that must be converged in order to trigger the first migration event.
	\item $\mu$, the migrant mixing coefficient.
	\item $\gamma$, the epoch length modifier.
	\item \texttt{epochGenerationLimit}, the number of generations after which a migration event is triggered regardless of the number of converged alleles.
	\item \texttt{intervalCheckEpoch}, \texttt{intervalStoppingLocal} and \texttt{intervalStoppingGlobal}: the number of generations between consecutive checks of, respectively, the migration event conditions, the local stopping conditions and the global stopping conditions.
\end{enumerate}
Notably absent from this list is $\delta$, the degree of the communication network's graph. Due to its importance, this parameter will be examined in-depth, along with $p$, in \autoref{sec:ScalabilityAndSpeedup}. During the parameter tuning experiments, the degree was set to the value $\delta=\frac{p}{2}$, which is often found to lead to optimal results \cite{cantupaz00,cao03}.

In the interest of keeping the number of experiments within reasonable limits, only three problem instances were used for the parameter tuning phase, all of them from the set of ISCAS'85 benchmark circuits given in \autoref{tab:IscasCombProblemInstances} in the previous chapter.
\begin{enumerate}\compactlist
	\item \texttt{c6288}
	\item \texttt{c3540}
	\item \texttt{c5315}
\end{enumerate}

Parameter tuning was divided into two iterations; during the first iteration, related parameters were chosen two at a time. For each parameter, three to five different values were chosen. The set of experiment configurations was taken as the Cartesian product between the two sets of parameter values. The experiments were then executed for 20 minutes, once using $p=4$, once using $p=8$.

For each problem instance, the set of best fitness values found during the 20-minute run was rearranged by subtraction and multiplication to give a mean value of 0 and a variance of 1. The values were then plotted as four contour graphs: one graph for each problem instance, and one for the sum of the three sets of values. \autoref{fig:ParameterTuningColorbar} shows the color scale used in these contour graphs.

When the results were inconclusive, another grid of parameter values was picked intersecting the first, and the results were combined.

In the second iteration, parameter values were selected close to the local optima discovered during the first iteration. The process of running the experiments and processing the results was otherwise identical to that of the first iteration.

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[width=0.8\textwidth]{parameter_tuning/colorbar-num}
		\caption[Color scale for the contour graphs that show results of parameter tuning.]
		{Color scale for the contour graphs that show results of parameter tuning. The numbers on the scale represent the distance of a data point from the mean, in standard deviations.}
		\label{fig:ParameterTuningColorbar}
	\end{center}
\end{figure}








\subsection{Iteration 1}
\autoref{fig:ParameterTuningIter101} shows the results of tuning $\epsilon$ and \texttt{convergenceThreshold}. It can be clearly seen that low values of $\epsilon$ cause low fitness values. For \texttt{convergenceThreshold} there is also a local optimum, although it is not as distinct as with $\epsilon$.

In \autoref{fig:ParameterTuningIter102} the results of tuning $Y_0$ and $X_0$ are shown. A local optimum for both variables can easily be discerned.

\autoref{fig:ParameterTuningIter103} shows the results of tuning $\mu$ and $\gamma$. Unfortunately, a single local optimum does not exist here; a diagonal valley of low fitness values cuts across the graph. The larger local optimum, around $\mu=0.8$ and $\gamma=7$, was selected as the area for the second iteration.

The last graph, \autoref{fig:ParameterTuningIter104}, shows the results of tuning \texttt{epochGenerationLimit} and \texttt{intervalCheckEpoch}. From the graph it is evident that these parameters have a very subtle and rather unpredictable effect on the performance of the algorithm. Nevertheless, a small local optimum in the top-right corner of the graph was selected as the area for the second iteration.

%%% Begin figures for this section
\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter1-01}
		\caption[Parameter tuning of the parameters \(\epsilon\) and \texttt{convergenceThreshold}, iteration 1.]
		{Parameter tuning of the parameters \(\epsilon\) and \texttt{convergenceThreshold}. Values of \(\epsilon\) were chosen with geometric spacing in the range suggested by Corno et al.\ \cite{corno98} and are plotted logarithmically. Values of \texttt{convergenceThreshold} were chosen with linear spacing in the range suggested by Corno et al.}
		\label{fig:ParameterTuningIter101}
	\end{center}
\end{figure}

\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter1-02}
		\caption[Parameter tuning of the parameters \(Y_0\) and \(X_0\), iteration 1.]
		{Parameter tuning of the parameters \(Y_0\) and \(X_0\). Since there is a strong dependency between these parameters and the number of genes \(n\), the X-axis shows the ratio \({Y_0}/{n}\); on the Y-axis the ratio \({X_0}/{Y_0}\) is shown. Values of the two ratios were chosen with geometric spacing.}
		\label{fig:ParameterTuningIter102}
	\end{center}
\end{figure}

\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter1-03}
		\caption[Parameter tuning of the parameters \(\mu\) and \(\gamma\), iteration 1.]
		{Parameter tuning of the parameters \(\mu\) and \(\gamma\). Values of \(\mu\) were chosen with semi-linear spacing in the range from 0 to 1. Values of \(\gamma\) were chosen with geometric spacing, with the added constraint that they had to be integers.}
		\label{fig:ParameterTuningIter103}
	\end{center}
\end{figure}

\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter1-04}
		\caption[Parameter tuning of the parameters \texttt{epochGenerationLimit} and \texttt{intervalCheckEpoch}, iteration 1.]
		{Parameter tuning of the parameters \texttt{epochGenerationLimit} and \texttt{intervalCheckEpoch}. Values of \texttt{epochGenerationLimit} were chosen with geometric spacing and are plotted logarithmically. Values of \texttt{intervalCheckEpoch} were also chosen with geometric spacing, but are plotted linearly. For each different value of \texttt{intervalCheckEpoch} the values of \texttt{intervalStoppingLocal} and \texttt{intervalStoppingGlobal} were also adjusted, but these are not shown on the graph.}
		\label{fig:ParameterTuningIter104}
	\end{center}
\end{figure}
%%% End figures for this section














\clearpage
\subsection{Iteration 2}
In the second iteration of parameter tuning, only five different combinations of parameter values were chosen, arranged like the \emph{pips} on the ``5'' face of ordinary playing dice, with the center pip representing the values chosen during iteration 1. Results from the second iteration of parameter tuning are shown in figures \ref{fig:ParameterTuningIter201}, \ref{fig:ParameterTuningIter202}, \ref{fig:ParameterTuningIter203} and \ref{fig:ParameterTuningIter204}.

The purpose of iteration 2 was primarily confirmation that the values from iteration 1 were really correct optima; the secondary goal was to perform tests in the area of the local optima at a resolution higher than in iteration 1. The results are straightforward: the five data points are shown along with a contour graph fitting these points. On the fourth quadrant of each figure, a black asterisk represents the final values of the parameters that were chosen. These values were then used in all further experiments with few exceptions. For reference, the exact values are given in \autoref{tab:ParameterTuningFinalValues}.

%%% Begin figures for this section
\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter2-01}
		\caption[Parameter tuning of the parameters \(\epsilon\) and \texttt{convergenceThreshold}, iteration 2.]
		{Parameter tuning of the parameters $\epsilon$ and \texttt{convergenceThreshold}. The black asterisk denotes the final parameter values chosen for further experiments.}
		\label{fig:ParameterTuningIter201}
	\end{center}
\end{figure}

\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter2-02}
		\caption[Parameter tuning of the parameters \(Y_0\) and \(X_0\), iteration 2.]
		{Parameter tuning of the parameters $Y_0$ and $X_0$. The black asterisk denotes the final parameter values chosen for further experiments.}
		\label{fig:ParameterTuningIter202}
	\end{center}
\end{figure}

\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter2-03}
		\caption[Parameter tuning of the parameters \(\mu\) and \(\gamma\), iteration 2.]
		{Parameter tuning of the parameters $\mu$ and $\gamma$. The black asterisk denotes the final parameter values chosen for further experiments.}
		\label{fig:ParameterTuningIter203}
	\end{center}
\end{figure}

\begin{figure}[p]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{parameter_tuning/iter2-04}
		\caption[Parameter tuning of the parameters \texttt{epochGenerationLimit} and \texttt{intervalCheckEpoch}, iteration 2.]
		{Parameter tuning of the parameters \texttt{epochGenerationLimit} and \texttt{intervalCheckEpoch}. The black asterisk denotes the final parameter values chosen for further experiments.}
		\label{fig:ParameterTuningIter204}
	\end{center}
\end{figure}
%%% End figures for this section

\begin{table}[htb]
	\sffamily
	\begin{center}
		\begin{tabular}{|l|l|}
			\hline
				\textbf{Parameter}								& \textbf{Value} \\
			\hline
				$\epsilon$												& 0.026 \\
			\hline
				\texttt{convergenceThreshold}			& 0.80 \\
			\hline
				${Y_0}/{n}$												& 0.107 \\
			\hline
				${X_0}/{Y_0}$											& 0.590 \\
			\hline
				$\mu$															& 0.71 \\
			\hline
				$\gamma$													& 6 \\
			\hline
				\texttt{epochGenerationLimit}			& 100\,000 \\
			\hline
				\texttt{intervalUpdateParameters}	& 10 \\
			\hline
				\texttt{intervalCheckEpoch}				& 170 \\
			\hline
				\texttt{intervalStoppingLocal}		& 1200 \\
			\hline
				\texttt{intervalStoppingGlobal}		& 1400 \\
			\hline
		\end{tabular}
		\caption{Final parameter values after iteration 2 of parameter tuning}
		\label{tab:ParameterTuningFinalValues}
	\end{center}
\end{table}











\clearpage
\section{General performance metrics}

Before moving on to the scalability experiments we will briefly demonstrate some general metrics of PSG's performance using the parameters found in the previous section. Section \ref{sec:GpmCommunication} shows what kinds of messages are exchanged between processors during a typical run of the algorithm, and in what proportions. In \autoref{sec:GpmSelfAdaption} we illustrate the deterministic self-adaption strategy introduced in \autoref{sec:SelfAdaptionPSG} by showing how the value of $\rho$ changes over time.

\afterpage{\clearpage}
\subsection{Communication}
\label{sec:GpmCommunication}
\autoref{fig:GpmCommunicationC3540} and \autoref{fig:GpmCommunicationC6288} show the communication characteristics for two runs of the algorithm. In these runs, the number of processors was set to 4 and the degree was set to 2. The problem instances were \texttt{c3540} and \texttt{c6288}, respectively. The bar graph in the bottom half of each figure shows the numbers of messages sent and received for each distinct message type used by the algorithm. These message types are:

\begin{description}
	\item[\texttt{ALLELES:}] The most important message of all, this is the message containing converged allele values, which is sent in a migration event. For each message sent, $\delta$ messages are received.
	\item[\texttt{LOCAL\_STOP:}] When a processor reaches its local stopping conditions, a \texttt{LOCAL\_STOP} message is sent to $p_0$.
	\item[\texttt{GLOBAL\_STOP:}] When $p_0$ reaches the global stopping conditions, this message is sent to all other processors.
	\item[\texttt{LOCAL\_SOLUTION:}] Upon receiving \texttt{GLOBAL\_STOP}, processors send their best individual found to $p_0$ inside a \texttt{LOCAL\_SOLUTION} message.
	\item[\texttt{TERMINATION\_TOKEN:}] When $p_0$ has received $(p-1)$ \texttt{LOCAL\_SOLUTION} messages, it sends out the \texttt{TERMINATION\_TOKEN} to all other processors, informing them it is safe to disconnect the message loop and terminate.
\end{description}

The algorithm states that only \texttt{ALLELES} and \texttt{LOCAL\_STOP} may be sent multiple times, all other messages are sent only once. In \autoref{fig:GpmCommunicationC3540}, no processors reach their local stopping conditions and thus no \texttt{LOCAL\_STOP} messages are sent. \autoref{fig:GpmCommunicationC6288} shows an interesting case where one processor, $p_1$, is lucky to reach its local stopping conditions early in the execution, and as a result it repeatedly sends \texttt{LOCAL\_STOP} messages to $p_0$.

%%% Begin figures for this section
\begin{figure}[p]%[h!]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{gpm/communication-c3540}
		\caption[Visualization of the amounts of messages of distinct types on \texttt{c3540}]
		{Visualization of the amounts of messages of distinct types exchanged in the system (with $p=4$). The tested problem file was \texttt{c3540} ($n=100$). The pie chart shows the aggregate amounts for all processors combined, the bar chart shows the individual amounts for each processor.}
		\label{fig:GpmCommunicationC3540}
	\end{center}
\end{figure}

\begin{figure}[p]%[h!]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{gpm/communication-c6288}
		\caption[Visualization of the amounts of messages of distinct types on \texttt{c6288}]
		{Visualization of the amounts of messages of distinct types exchanged in the system (with $p=4$). The tested problem file was \texttt{c6288} ($n=64$). The pie chart shows the aggregate amounts for all processors combined, the bar chart shows the individual amounts for each processor.}
		\label{fig:GpmCommunicationC6288}
	\end{center}
\end{figure}
%%% End figures for this section








\clearpage
\subsection{Self-adaption}
\label{sec:GpmSelfAdaption}
In \autoref{sec:SelfAdaption} we describe a strategy for deterministic self-adaption of the mutation probability $\rho$, given by \autoref{eq:PsgSelfAdaption}:
\begin{equation*}
	\rho(n,c,t)=\left(2+\frac{n-2}{n}c+\frac{\sqrt{t}}{n}\right)^{-1}
\end{equation*}
Considering that $n$ remains constant during execution of the algorithm, any changes in $\rho$ are related to changes in $c$, the number of converged alleles, and $t$, the number of generations in the current epoch, which in turn depends on $e$, the number of epochs.

\autoref{fig:GpmSelfAdaptionC3540} and \autoref{fig:GpmSelfAdaptionC6288} plot the value of $\rho$ along with $c$ and $e$, where $c$ is expressed as the percentage of genes that have converged to a specific allele. The figures refer to the same runs as described in \autoref{fig:GpmCommunicationC3540} and \autoref{fig:GpmCommunicationC6288} in the previous section.

In \autoref{fig:GpmSelfAdaptionC3540}, we see that $c$ does not always increase over time; it can happen that some demes are forced to abandon their local optima in favor of more promising areas found in other demes. This is a normal behavior for an island model PEA. When this happens, the decreasing value of $c$ leads to higher values of $\rho$, as can be seen from the graph.

\autoref{fig:GpmSelfAdaptionC6288} shows $p_1$ reaching its local stopping conditions early in the execution when $c$ approaches 100\%. The graph also shows the wide diversity that can occur between demes, with $p_0$ and $p_2$ never converging more than 50\% of their genes while the other demes appear to be more successful.

%%% Begin figures for this section
\begin{figure}[p]%[h!]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{gpm/self_adaption-c3540}
		\caption[Visualization of the number of epochs $e$, the number of converged alleles $c$, and the mutation probability $\rho$ on \texttt{c3540}.]
		{Visualization of the number of epochs $e$, the number of converged alleles $c$, and the mutation probability $\rho$ for each processor in the system (with $p=4$). The tested problem file was \texttt{c3540} ($n=100$).}
		\label{fig:GpmSelfAdaptionC3540}
	\end{center}
\end{figure}

\begin{figure}[p]%[h!]
	\sffamily
	\begin{center}
		\includegraphics[width=0.65\textwidth]{gpm/self_adaption-c6288}
		\caption[Visualization of the number of epochs $e$, the number of converged alleles $c$, and the mutation probability $\rho$ on \texttt{c6288}.]
		{Visualization of the number of epochs $e$, the number of converged alleles $c$, and the mutation probability $\rho$ for each processor in the system (with $p=4$). The tested problem file was \texttt{c6288} ($n=64$).}
		\label{fig:GpmSelfAdaptionC6288}
	\end{center}
\end{figure}
%%% End figures for this section





\clearpage
\section{Scalability and speedup}
\label{sec:ScalabilityAndSpeedup}

In this section we will examine the parallel speedup of the algorithm in order to evaluate its scalability. In \autoref{sec:SpeedupAndSolutionQuality} we highlighted some of the issues in measuring speedup for heuristic methods such as evolutionary algorithms, particularly the observation that when adopting a convergence-based approach to speedup, some PEA's might exhibit very poor speedups, with the convergence times sometimes even increasing as more PE's are added. However, such a PEA does make use of the extra resources, reflected by a higher solution quality. For such PEA's, we advocated the use of a solution-quality-based approach to speedup, measuring the time it takes different algorithm configurations to reach solutions of a certain quality.

Preliminary scalability testing revealed that PSG falls into this category; convergence-based speedup was virtually nonexistent, yet a correlation seemed to exist between the number of processors and the highest fitness found during execution. Therefore, in order to provide a more meaningful evaluation of PSG's scalability, a solution-quality-based approach to speedup was adopted.

Due to PSG's lack of an explicit population, a somewhat na{\"i}ve stopping condition was used: execution terminates after the first individual with a fitness exceeding a certain threshold has been constructed. This is not fundamentally different from the approach in explicit-population PEA's, where execution terminates when the population's average fitness exceeds a threshold: at any generation, an individual in PSG is largely constructed from high-frequency alleles and can thus be seen as an ``average'' individual with, we assume, an average fitness.\footnote{In real-world populations, the average individual does not always possess an average fitness; in many societies, a small minority of individuals holds a disproportionate amount of resources (food, breeding rights, money).}

In \autoref{sec:IntroductionToParallelSystems} we introduced \autoref{eq:Speedup}, the general formula for parallel speedup.
\begin{equation*}
	S(n,p)=\frac{SU(n)}{T(n,p)}
\end{equation*}
In other words, parallel speedup is a ratio of two values; taking this into account, the scalability experiments are split into two phases: in phase 1 we will find the numerator $SU(n)$, and in phase 2 we will find the denominator $T(n,p)$.

\subsection{Phase 1}
When using a solution-quality-based approach to speedup, the first task is to set the fitness target to such a level that a sequential implementation can reach it in a reasonable amount of time. To determine these levels, a sequential algorithm was executed on each problem instance for 30 minutes, or until the maximal fitness value was found. \autoref{fig:ScalabilityPhase1StoppingConditions} shows the highest fitness values found during each run, along with the highest level of convergence reached. The fitness targets for each problem instance were then set slightly below these highest fitness values, to prevent rounding errors from unnecessarily prolonging execution.\footnote{In the implementation, fitness values use a floating-point representation.} Problem instances where no alleles converged at all (\texttt{c499} and \texttt{c1355}) were excluded from the rest of the experiments.

\begin{figure}[htbp]
	\sffamily
	\begin{center}
		\includegraphics[width=0.8\textwidth]{scalability/phase1-stopping_conditions}
		\caption{The highest fitness values, and number of converged alleles found during a 30-minute run of the sequential algorithm.}
		\label{fig:ScalabilityPhase1StoppingConditions}
	\end{center}
\end{figure}

In order to find $SU(n)$ for each problem instance, the sequential algorithm was then executed once more, this time with the fitness target set as a local stopping condition. Taking the stochastic nature of the algorithm into account, each problem instance was run three times. The average wall-clock runtime of these three runs was taken as $SU(n)$. The results of these runs are displayed graphically in \autoref{fig:ScalabilityPhase1Runtimes}.

\begin{figure}[htbp]
	\sffamily
	\begin{center}
		\includegraphics[width=0.8\textwidth]{scalability/phase1-runtimes}
		\caption[The average time $SU(n)$ taken by a sequential configuration of PSG to reach the fitness targets shown in \autoref*{fig:ScalabilityPhase1StoppingConditions}.]
		{The average time $SU(n)$ taken by a sequential configuration of PSG to reach the fitness targets shown in \autoref{fig:ScalabilityPhase1StoppingConditions}.}
		\label{fig:ScalabilityPhase1Runtimes}
	\end{center}
\end{figure}



\afterpage{\clearpage}
\subsection{Phase 2}
\label{sec:ScalabilityPhase2}
In phase 2, the runtimes of the parallel implementation were measured. Letting $f_T$ denote the fitness target found in phase 1, the algorithm's stopping conditions were set as follows:
\begin{itemize}\compactlist
	\item Each deme had a local stopping condition of the form $f \geq f_T$; in other words, the deme starts sending out \texttt{LOCAL\_STOP} messages once an individual with a fitness exceeding the target is found.
	\item Processor $p_0$, responsible for checking the global stopping conditions, was set to initiate termination when at least one deme reaches its local stopping conditions. In other words, $p_0$ starts sending out \texttt{GLOBAL\_STOP} messages after the first \texttt{LOCAL\_STOP} message has been received. If no such message is received after some time limit (30 minutes) has elapsed, termination is initiated regardless.
\end{itemize}

In \autoref{sec:ParameterTuning} we left one parameter unaddressed: $\delta$, the degree of the interconnection network. The goal of the scalability experiments was to analyze the correlation between speedup $S(n,p)$ and $\delta$. A range of values for $\delta$ similar to the one used by Cao, et al.\ \cite{cao03} was chosen. Specifically, four degrees of connectivity were examined:
\begin{enumerate}\compactlist
	\item $\delta=\frac{p}{2}$, the value designated as ``usually optimal'' by Cant{\'u}-Paz \cite{cantupaz00}.
	\item $\delta=(p-1)$, or full connectivity; each deme sends migration packets to all others.
	\item $\delta=1$, the least connectivity; each deme sends a migratation packet to only one neighbor.
	\item $\delta=2$. Although differing only by one, this scheme is rather different from $\delta=1$; when $\delta=1$, any deme $p_i$ sends migration packets to $p_j$, where $j=(i+1)\bmod{p}$. This means that $p_j$ does not send migration packets to $p_i$. In the case of $\delta=2$, two neighboring demes do send migration packets to each other: any deme $p_i$ sends migration packets to $p_j$ and to $p_k$, where $j=(i+1)\bmod{p}$ and $k=(i-1)\bmod{p}$.
\end{enumerate}

The algorithm was executed on each of the nine ISCAS circuits from the first phase, using each of these four $\delta$ schemes. The number of processors $p$ ranged from 2 to 24; other runtime parameters were set to the values found during the parameter tuning experiments described in \autoref{sec:ParameterTuning}.

Wall-clock execution times were collected for each run. For each problem instance, these execution times were plotted as four series in the $(p,T)$-plane, one for each $\delta$ scheme. Dividing $SU(n)$, obtained in phase 1, by the values $T(n,p)$, speedup $S(n,p)$ was obtained. Speedups were again plotted as four series, this time with $S$ on the $y$-axis.

Figures showing $T(n,p)$ and $S(n,p)$ for each tested problem instance are reproduced in \autoref{app:Scalability}. Of special interest are the figures for \texttt{c17} shown in \autoref{fig:ScalabilityPhase2Comb01}: due to the simplicity of this circuit, execution never took more than two seconds. Since time measurement in the implementation is done with a resolution of 1 second, $T(n,p)$ could not be measured accurately, and the values of $S(n,p)$ are not very meaningful. The graphs are reproduced solely for the sake of completeness.

A general notion of scalability for PSG may be obtained by producing a graph of aggregate speedup: the average values of $S(n,p)$ for each distinct value of $p$. In computing these values, we excluded the results of \texttt{c17} and so aggregate speedup is the average speedup across eight problem instances, with values of $n$ ranging from 64 (\texttt{c6288}) to 466 (\texttt{c2670}). Aggregate speedup is shown in \autoref{fig:ScalabilityPhase2SpeedupAll}.

%%% Figure showing aggregate speedup
\begin{figure}[htb]
  \sffamily
  \begin{center}
    \includegraphics[width=0.8\textwidth]{scalability/phase2_speedup_all}
    \caption[Speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ for all ISCAS circuits tested.]
            {Speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ for all ISCAS circuits tested. The dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
    \label{fig:ScalabilityPhase2SpeedupAll}
  \end{center}
\end{figure}

The figure clearly shows that as more processors are added to the system, the algorithm finds a suitable individual in a reduced time. While speedup is not linear (in reality, it rarely is), it certainly is an increasing function for all $\delta$ schemes considered.

An interesting observation is the fact that optimal performance is often obtained when $\delta=1$. Furthermore, the significant difference between the performance of the $\delta=1$ and $\delta=2$ schemes leads to the conclusion that in PSG, the topology of the network appears to play a larger role than in canonical genetic algorithms. This conclusion is based on the fact that while the $\delta=1$ and $\delta=2$ schemes do not differ greatly in their degree, they do differ in topology: when $\delta=2$, a converged allele emigrating from any deme $p_i$ may migrate back to $p_i$ after just one epoch, whereas in the case of $\delta=1$ the allele must go through at least $(p-1)$ epochs before it finds its way back to $p_i$.





\clearpage
\section{Comparison with random search}
In this section we will examine how the algorithm performs when compared to a random search algorithm. Using terminology from evolutionary algorithms, a random search algorithm can be defined as an algorithm that, each generation, evaluates the fitness of a random individual. When execution terminates, the best individual found is returned.

PSG is a very flexible algorithm, and can be turned into a random search algorithm simply by setting $\epsilon$ to zero. This prevents the algorithm from adjusting the population's gene pool, leaving the VP in its initial state (all alleles are equally likely) for the length of the algorithm's execution. In \autoref{sec:SelfishGeneAlgorithm} we learned that when the Selfish Gene Algorithm constructs an individual, the individual's genotype will be made up of a combination of random and proportionate alleles. When the VP is in its initial state, there is no difference between a random and a proportionate allele, and all alleles are effectively random.

To make the comparison between PSG and random search meaningful, it was decided to let each algorithm execute for a fixed number of generations. For each problem instance, the generation target $g_T$ was calculated as follows:
\begin{enumerate}
	\item Execution reports from the scalability experiment were analyzed. The total number of generations executed was summed up and divided by the total number of seconds of wall-clock time. This gives the average number of generations per second $\bar{v}_g$.
	\item $g_T$ was set to $32\cdot \bar{v}_g$, rounded to the nearest integer.
	\item \texttt{intervalStoppingLocal} was set to $8\cdot\bar{v}_g$, rounded upwards to the nearest multiple of \texttt{intervalUpdateParameters}.
	\item \texttt{intervalStoppingGlobal} was set to $9\cdot\bar{v}_g$, rounded upwards to the nearest multiple of \texttt{intervalUpdateParameters}.
\end{enumerate}
By using this method, execution was expected to take around 32 seconds, with local and global stopping conditions being checked roughly every 8 and 9 seconds, respectively.

Further parameters of the experiment were as follows:
\begin{itemize}
	\item The number of processors $p=8$.
	\item For PSG, $\delta=\{1,2,4,7\}$.\footnote{This corresponds to the four $\delta$ schemes discussed in the previous section.} For random search $\delta$ is not relevant.
	\item For random search, $\epsilon=0$.
	\item Each deme received a local stopping condition of the form $g \geq g_T$.
	\item $p_0$ received a global stopping condition of the form $\Sigma g \geq p \cdot g_T$.
\end{itemize}

Eight problem instances were thus tested: the nine from the scalability experiments minus \texttt{c17}, since all configurations are capable of reaching 100\% fitness for \texttt{c17} within a few seconds. For each problem instance, one run of random search was performed, and four runs of PSG, each with a different value of $\delta$. The highest fitness values reached during execution were collected and are represented in \autoref{fig:RandomSearch} as ratios of solution quality.

%%% Figure showing comparison with random search
\begin{figure}[htb]
  \sffamily
  \begin{center}
    \includegraphics[width=0.69\textwidth]{miscfigs/randomsearch_fitness-ratio}
    \caption[Comparison of solution qualities of PSG and random search (RS).]
            {Comparison of solution qualities of PSG and random search (RS). The ratio $f_{PSG}/f_{RS}$ is shown, where $f_{PSG}$ and $f_{RS}$ are the best fitness values found by PSG and random search, respectively. Additionally, the number of inputs $n$ is shown for each problem instance.}
    \label{fig:RandomSearch}
  \end{center}
\end{figure}

The results are not as impressive as one would have hoped; PSG rarely outperforms random search, and if it does, it does so by only a few percent. However, it should be noted that for the problem instances considered, the time available for execution in this experiment (less than one minute) is far less than the time needed for PSG to converge and yield its greatest benefit. Moreover, Corno et al.\ already demonstrated that the Selfish Gene Algorithm behaves as a random search algorithm for its first phase of execution \cite{corno98}.

Summing up, the experiments in this section neither confirm nor deny the hypothesis that PSG can outperform a random search algorithm. For that, further experiments would be needed, where there is more time available for execution. Unfortunately, organizational limits imposed on the computing cluster prevented such experiments from being performed.





\clearpage
\section{Real fault coverage}
In this section, we will examine the \emph{real} fault coverage of the cellular automata that PSG evolves. In \autoref{sec:BIST} we described two methods of evaluating a TPG: full fault-simulation and fault vector covering. The latter method, which is the one used by PSG, is not as accurate as the former, since no fault simulation is performed. In this section, we will perform this fault simulation, using the cellular automata evolved by PSG as TPG's.

To determine the real fault coverage on the benchmark circuits, the first task is to find the cellular automata that are most likely to achieve the highest fault coverage. To find them, the results of the scalability experiments were analyzed; for each circuit, the ``winning'' cellular automaton was chosen as the individual yielding the highest fitness value. If multiple individuals all had the highest fitness value, the winner was chosen as the individual produced by the algorithm that achieved the highest level of convergence. For each circuit, the fitness value of the fittest individual is shown in \autoref{fig:RfcBestFitness}, along with the configuration of the algorithm that evolved this individual. At this point, it is worth repeating the definition of fitness in the Cellular Automata Problem: the fitness value of an individual refers to the percentage of fault vectors for the given circuit that are covered by test vectors from the cellular automaton.

%%% Figure showing best fitness found
\begin{figure}[htbp]
  \sffamily
  \begin{center}
    \includegraphics[width=0.8\textwidth]{rfc/best-fitness}
    \caption[Best fitness values found by PSG during scalability testing.]
            {Best fitness values found by PSG during scalability testing, along with the configuration that found the fittest individual.}
    \label{fig:RfcBestFitness}
  \end{center}
\end{figure}

Fault coverage was obtained by fault-simulating each circuit, using $I$ vectors extracted from the winning CA as the set of input vectors $V_T, \left|V_T\right|=I$. Due to computational constraints, the highest number of input vectors considered was one million ($I_{\max}=10^6$).

Denoting $\Sigma F$ as the total number of faults introduced by the fault simulator, and $F_{UD}$ as the lowest number of undetected faults, fault coverage $C_F$ was calculated according to the following formula.
\begin{equation}
	C_F = \frac{\Sigma F - F_{UD}}{\Sigma F}
\end{equation}

In addition to fault coverage, the minimal number of input vectors $I_C$ needed for achieving maximal fault coverage was also determined. $I_C$ is minimal in the sense that when the $I_C$'th element from $V_T$ is removed, more faults will go undetected.

Results from the fault coverage experiment are given in \autoref{tab:RfcFaultCoverage}. \autoref{fig:RfcFaultCoverage} shows this information graphically. Fault coverage is very high for all circuits, with two circuits, \texttt{c17} and \texttt{c880}, reaching 100\% fault coverage. For these circuits, we may compare the values of $I_C$ to the range of values presented in \cite{fiser04}.\footnote{It should be noted that these ranges were established using an LFSR as the test pattern generator.} For \texttt{c17}, $I_C$ is expected to fall within the range 2--33, with a statistical average of 4. Our value (12) is above the average, but still well within the range. For \texttt{c880}, the range is 2500--75\,000, with an average of 13\,000. Our value of 8868 is well below the average number of input vectors needed to fully test the circuit.

\vspace{\parskip}

\begin{table}[htb]
	\sffamily
	\begin{center}
		\begin{tabular}{|l|l|l|l|}
			\hline
				\textbf{Circuit name} & \textbf{Undetected faults $F_{UD}$} & \textbf{Fault coverage $C_F$} & \textbf{Minimal number of vectors $I_C$} \\
			\hline
				\texttt{c17}			& 0			& 100\%			& 12 \\
			\hline
				\texttt{c432}			& 4			& 99.2\%		& 826 \\
			\hline
				\texttt{c880}			& 0			& 100\%			& 8868 \\
			\hline
				\texttt{c1908}		& 9			& 99.5\%		& 3611 \\
			\hline
				\texttt{c2670}		& 137		& 93.9\%		& 946\,695 \\
			\hline
				\texttt{c3540}		& 137		& 96.0\%		& 20\,482 \\
			\hline
				\texttt{c5315}		& 59		& 98.9\%		& 2831 \\
			\hline
				\texttt{c6288}		& 50		& 99.4\%		& 70 \\
			\hline
				\texttt{c7552}		& 214		& 97.2\%		& 912979 \\
			\hline
		\end{tabular}
		\caption{Real fault coverage obtained by cellular automata evolved by PSG.}
		\label{tab:RfcFaultCoverage}
	\end{center}
\end{table}


%%% Figure showing fault coverage
\begin{figure}[htb]
  \sffamily
  \begin{center}
    \includegraphics[width=0.8\textwidth]{rfc/fault-coverage}
    \caption[Real fault coverage of the cellular automata evolved by PSG.]
            {Real fault coverage obtained by fault-simulating the ISCAS benchmark circuits, using cellular automata evolved by PSG as the TPG.}
    \label{fig:RfcFaultCoverage}
  \end{center}
\end{figure}

