\chapter{Software development}
\label{chap:SoftwareDevelopment}

In the previous chapter we defined the Parallel Selfish Gene Algorithm (PSG). Stepping away momentarily from the field of problems and algorithms, we cross into the field of software engineering to take a closer look at the development process by which PSG was implemented.

Development was split up into three \emph{phases}; at the end of each phase, a fully functional application was delivered. The phases themselves were based on traditional ``waterfall'' cycles consisting of requirements, design, implementation, and testing. In some phases the implementation and testing cycles were further divided into \emph{iterations}, each iteration comprising both implementation and thorough testing. Care was taken to deliver functional, tested code at the end of each iteration: doing so reduces the risk of bugs being carried over from one iteration into the next. \autoref{fig:Gantt} shows a Gantt chart for the whole development process. The chart is highly simplified for reasons of space.

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[width=\textwidth]{miscfigs/sw_gantt-chart}
		\caption{Simplified Gantt chart of the PSG software development process.}
		\label{fig:Gantt}
	\end{center}
\end{figure}

\section{Phase 1: SCP-SG}
\label{sec:DevPhase1}

Phase 1 started as a homework assignment for a course on \emph{Softcomputing} (SCP). The assignment was to develop an evolutionary algorithm for solving the Vertex Cover Problem (see \autoref{sec:VertexCoverProblem}). Thus the following (self-imposed) requirements were set for phase 1:
\begin{itemize}\compactlist
	\item Implement the Selfish Gene Algorithm for solving the Vertex Cover Problem.
	\item The design shall be modular, making it easy to add functionality.
	\item The implementation shall feature an abstract interface for problem domains, making it easy to adapt the algorithm to new problems.
	\item It will be possible to compile and execute the application on a Linux computing cluster.
\end{itemize}

SCP-SG was implemented in ISO C++ \cite{iso14882}. At the end of phase 1, the project contained 922 lines of source code in 24 files. SCP-SG has the following structure:
\begin{itemize}\compactlist
	\item The class \texttt{SgEngine} is the heart of the program. It can load a problem instance, execute a number of generations, and keep track of the best solution found.
	\item	The class \texttt{ProblemDomain} is an abstract representation of a problem domain. Because it is an abstract representation, the fitness function is undefined.
	\item	The class \texttt{VertexCoverProblem} is derived from ProblemDomain and contains the fitness function described in \autoref{sec:VertexCoverProblem}.
	\item	The classes \texttt{AdjacencyList} and \texttt{AdjacencyMatrix} are used by \texttt{VertexCoverProblem} to access the problem instance's graph.
	\item	The class \texttt{Population} contains the virtual population. This class also handles the selection of individuals for the purpose of fitness evaluation.
	\item	The class \texttt{StoppingConditions} implements a mechanism for determining when to stop computation. Three kinds of stopping criteria are defined: stopping after a specific number of generations, stopping after a specific number of seconds of wall-clock time have elapsed, and stopping when a specific number of alleles has converged.
	\item	The class \texttt{Parameters} is a singleton class storing runtime parameters such as the mutation rate and the convergence threshold.
	\item	The class \texttt{Random} is an abstract interface to a pseudo-random number generator.
	\item	The classes \texttt{StdRandom} and \texttt{BoostRandom} are derived from \texttt{Random} and respectively use the standard C library and the Boost C++ libraries \cite{wboost} for generating random numbers.
\end{itemize}

\section{Phase 2: P-SCP-SG}
Phase 2 constituted the biggest effort. The goal of phase 2 was to extend SCP-SG and create a parallel implementation called P-SCP-SG. During the requirements and design phases the system architecture of PSG, described in \autoref{sec:SystemArchitecture}, was determined along with the communication protocol and the self-adaption mechanism.

Functional requirements for phase 2 are largely described in the previous chapter. Additionally one non-functional requirement was added, specifying the Message Passing Interface (MPI) \cite{wmpi} as the communications library to use.

Development was divided into two iterations. In addition to a number of changes, iteration 1 added the following new modules:
\begin{itemize}\compactlist
	\item The class \texttt{Communication}, which contains all the code for sending and receiving messages from neighboring PE's. The different message types used in the system are described in-depth in \autoref{sec:GpmCommunication}.
	\item The class \texttt{Logger}, providing singleton access to the application's log files from anywhere in the source code.
	\item The classes \texttt{Statistics} and \texttt{GlobalStatistics}, providing singletons holding various runtime statistics such as the number of generations executed, etc.
\end{itemize}
Iteration 2 saw the implementation of the deterministic self-adaption mechanism, and integrated the new code from iteration 1 to create a stable build that could compile and execute without failure. At the end of phase 2, the project contained 2671 lines of source code in 40 files.

\section{Phase 3: PSG}
The final phase of software development had as its primary task the integration of a new problem domain: the Cellular Automata Problem, described in \autoref{sec:CellularAutomataProblem}. Implementation of the new problem domain was contained in the first iteration, with the remaining two iterations concentrating primarily on acceptance testing and small maintenance patches to ensure a stable codebase for the experiments described in \autoref{chap:Experiments}.

The following new modules were added:
\begin{itemize}\compactlist
	\item The class \texttt{CellularAutomaton}, providing the means to build cellular automata and extract test vectors from them.
	\item The class \texttt{TestVectors}, which facilitates checking coverage of test vectors and fault vectors.
	\item The class \texttt{BistProblem}, which implements the abstract problem domain interface developed in phase 1.
	\item The class \texttt{MessageStatistics}, one more addition to the group of modules collecting runtime statistics. In order to gain a meaningful insight into the performance of any algorithm, it is vital to collect comprehensive statistics while the program is running. \texttt{MessageStatistics}, along with its close cousins from phase 2, provides this.
\end{itemize}
With phase 3 complete, the application reached its final state. Following suspension of development, the project contained 3695 lines of source code in 61 files. The gradual growth of PSG through its three phases is indicated graphically in \autoref{fig:CodeSize}.

\begin{figure}%[hb]
	\sffamily
	\begin{center}
		\includegraphics[width=0.8\textwidth]{miscfigs/sw_code-size}
		\caption{Growth of the number of files and the number of lines of code during software development.}
		\label{fig:CodeSize}
	\end{center}
\end{figure}

\section{Dependencies}
Readers interested in compiling and executing PSG will be interested to learn what kind of dependencies the project has. First of all, it must be noted that one of the earliest requirements was that the application be designed for a Linux computing cluster, so no extra effort was taken to provide compatibility for other systems. However, since the source code strictly adheres to the ISO standard for the C++ programming language \cite{iso14882}, compatibility should not be an issue.

In particular, two libraries are needed to compile and execute PSG.
\begin{enumerate}
	\item The Boost libraries \cite{wboost} were used wherever the standard C++ libraries did not provide the necessary functionality. Boost libraries are available on all popular platforms and are thoroughly tested by the community.
	\item An implementation of the Message Passing Interface (MPI) \cite{wmpi} is needed, even for sequential operation. In an effort to guarantee compatibility, two leading MPI implementations were tested during development: MPICH and OpenMPI.
\end{enumerate}
The following development tools were used. Although they are not strictly necessary for compilation and execution, they are recommended.
\begin{enumerate}[resume]
	\item The \textbf{CMake} build system \cite{wcmake} was used to maintain the project's makefiles and to automate compilation. Building the application using other build tools requires the user to manually create makefiles.
	\item The \textbf{Darcs} revision control system \cite{roundy05} was used to maintain the project's repositories. Even in the case of a single developer, Darcs is an invaluable tool when source code is being developed and executed on several systems, each needing its own patches to the code. A web interface to the darcs repositories for all development phases is available at \url{http://dev.harpavieja.cz/darcsweb/}.
\end{enumerate}
