\chapter{Parallel evolutionary algorithms}
\label{chap:PEAs}

When an evolutionary algorithm is adapted to utilize an arbitrary number of processors during execution, a \emph{parallel evolutionary algorithm} (PEA) is created. PEA's are the topic of this chapter.

In the first section, a brief introduction to the field of parallel systems and algorithms is given, to familiarize the reader with its definitions, its metrics and its challenges. The second section introduces PEA's proper, while the third section examines the different varieties of PEA architectures more closely. In the last section of this chapter we will outline some of the work that has been done on the numerical analysis of PEA's, and what that means for the development of the Parallel Selfish Gene Algorithm.

\section{Introduction to parallel systems}
\label{sec:IntroductionToParallelSystems}
A parallel system is a collection of processing elements (PE's) that communicate and cooperate to solve challenging problems. Parallel systems come in all sizes, from the multicore processors in modern PC's, to dedicated supercomputers such as \emph{BlueGene}, to distributed computing efforts organized over the internet. The term \emph{parallel system} often refers to both the actual physical machine, and the algorithm implemented on it. In other words, a parallel system is a parallel algorithm together with hardware supporting multiple PE's.

Parallel systems can be classified according to various taxonomies. One of the oldest taxonomies is the taxonomy according to instruction and data flow known as \emph{Flynn's taxonomy}, after Michael J. Flynn who proposed it in 1966. Flynn's taxonomy recognizes three types of parallel systems:
\begin{enumerate}
	\item \textbf{Single instruction, multiple data} (SIMD), where all PE's execute the same series of machine instructions in lockstep, each operating on a different data stream. This type of system was popular in the past but is now used only in specialized systems such as 3-D graphics processors (GPU's).
	\item \textbf{Multiple instruction, single data} (MISD), a rarely used form of parallel computing, where PE's receive the same data stream but execute different instructions on the data.
	\item \textbf{Multiple instruction, multiple data} (MIMD), where PE's execute different sets of instructions on different data streams. This is the most common type of parallel system in use today. It is further divided into two subcategories:
	\begin{enumerate}[label=\theenumi\alph*.]
		\item \textbf{Single program, multiple data} (SPMD), where the same program is executed on all PE's, but the PE's are free to follow a different execution path and use different data. The Parallel Selfish Gene Algorithm described in \autoref{chap:PSG} is SPMD.
		\item \textbf{Multiple program, multiple data} (MPMD), the most detached model, where the PE's are completely autonomous, running different programs working with different data sets. Distributed (web-based) systems based on a client-server architecture can be classified as MPMD.
	\end{enumerate}
\end{enumerate}

Another taxonomy in use is the taxonomy according to memory organization. This taxonomy divides parallel systems into two groups:
\begin{enumerate}
	\item \textbf{Shared memory} systems such as the multicore or multiprocessor systems which are in common use as PC's and servers. In these systems, the communication between PE's is done by reading and writing data blocks.
	\item \textbf{Distributed memory} systems such as the computing cluster used for the experiments in \autoref{chap:Experiments}. In these systems, the communication between PE's consists of sending and receiving messages.
\end{enumerate}

\subsection{Parallel performance metrics}
\label{sec:PPM}

Parallel systems are used for two purposes:
\begin{enumerate}\compactlist
	\item To solve a challenging problem faster than on a sequential system.
	\item To find certain ``better'' solutions to a problem that cannot be found by a sequential system in a reasonable amount of time.
\end{enumerate}

The first purpose is the one that is traditionally seen as the primary purpose; although the second one is also very important, especially where heuristic methods such as evolutionary algorithms are concerned, the focus of researchers and implementers is mainly on the time savings that can be obtained. In this context, two metrics are used: \emph{speedup} and \emph{scalability}.

The speedup $S$ of a parallel algorithm solving a certain problem is defined as the ratio of the running time $SU$ of the fastest known sequential algorithm and the running time $T$ of the parallel algorithm \cite{tvrdik99}.
\begin{equation}
	\label{eq:Speedup}
	S(n,p)=\frac{SU(n)}{T(n,p)}
\end{equation}
where $n$ is the dimensionality of the problem and $p$ the number of PE's. The goal of parallel system designers is to achieve linear speedups; that is, if we solve the problem using $k$ processors, we will find the result $k$ times faster than using a sequential system.
\begin{equation*}
	S(n,k)=\frac{SU(n)}{T(n,k)}=\frac{SU(N)}{\left(\frac{SU(N)}{k}\right)}=k
\end{equation*}
Formally, linear speedup is defined as follows, using ``big O'' notation:
\begin{equation}
	S(n,p)=\Theta(p)
\end{equation}

In the above equations, special attention must be paid to the definition of ``time.'' Some researchers measure speedup by measuring the CPU time consumed by the PE's. Others prefer measuring absolute ``wall-clock'' time. In recent years, commercial CPU's have reached astonishing throughput rates, whereas performance of interconnection equipment has progressed at a much slower pace. Together with clever mechanisms such as DMA transfers reducing the CPU's workload, this leads to a situation where the performance of a parallel system is all but defined by its communication system. For these and other reasons, wall-clock time will be used as the time measure in this document.

The holy grail of parallel systems is \emph{superlinear speedup}, defined as the case when a parallel algorithm on $p$ processors is more than $p$ times faster than the sequential algorithm.
\begin{equation}
	S(n,p)=\Omega(p)
\end{equation}
Superlinear speedup is a rare occurance, and is usually caused by certain factors that severely penalize the sequential algorithm. An example of this is a search algorithm that would, in a sequential implementation, require more memory than is available in the system, causing extensive swapping of virtual memory pages; when the search space is segmented for use in a parallel system, the memory requirements are lower, speeding up the execution. An example of an algorithmic penalty for the sequential solution relates to algorithms with pruning such as Branch \& Bound: the sequential implementation might traverse a large non-optimal branch of the search space that, in a parallel system, may get prematurely pruned by another processor.

Closely related to speedup are the notions of \emph{parallel cost}, denoted by $C$, and \emph{efficiency}, denoted by $E$.
\begin{equation}
	E(n,p)=\frac{SU(n)}{C(n,p)}=\frac{S(n,p) \cdot T(n,p)}{p \cdot T(n,p)}=\frac{S(n,p)}{p}
\end{equation}

Scalability is loosely defined as the ability to utilize increasing numbers of processors effectively \cite{tvrdik99}. A perfectly scalable algorithm is one where $E$ remains constant regardless of $n$ and $p$. In reality, parallel systems can only make good use of a large number of PE's if $n$ is sufficiently large. When more PE's are added to a small problem, the running time will stop decreasing at a certain point, and might even increase when the communications overhead starts consuming more and more of the system's resources. This phenomenon is called ``parallel slowdown'' and is similar in many ways to the phenomenon, seen in human resources management, that adding more manpower to a delayed project will often delay it further \cite{brooks75}.


\section{Overview of parallel evolutionary algorithms}
Parallel implementations of evolutionary algorithms have been around for many years. One of the first implementations was described by Albert Bethke in 1976 \cite{bethke76}, just one year after John Holland's pivotal work ``Adaptation in Natural and Artificial Systems'' \cite{holland75}, which introduced genetic algorithms to the world at large. One reason for the success and popularity of PEA's is the fact that the biological foundation behind evolutionary algorithms seems to suggest parallelization; after all, in nature each organism operates independently from the others, competing for shared resources in a manner similar to processing elements in a parallel system.

Another reason for the success and popularity of PEA's relates to the second and traditionally overlooked purpose of using a parallel system: the observation that a parallel implementation can often lead to better results that could not be obtained by sequential methods. In his review of PEA's \cite{tomassini99}, Marco Tomassini writes:
\begin{quote}
	Parallel evolutionary algorithms seem to be more in line with their natural counterparts and thus might yield algorithmic benefits besides the added computational power.~[\ldots]~In general, it has been found experimentally that parallel genetic algorithms, apart from being significantly faster, may help in alleviating the premature convergence problem and are effective for multimodal optimization.
\end{quote}

\subsection{Speedup and solution quality}
\label{sec:SpeedupAndSolutionQuality}
In the previous section, we introduced the definition of speedup (\autoref{eq:Speedup}). The problem with this definition is that it requires that both algorithms solve the same problem and reach the same solution. It is difficult to guarantee this second condition when heuristic methods such as evolutionary algorithms are used.

Many researchers measure the speedup of a PEA as the ratio of convergence times of the sequential and parallel implementations, i.e. the time needed for the population to become (mostly) homogeneous. While this is a useful metric, it is worth noting that, strictly speaking, such a ratio should not be called ``speedup,'' since the solutions reached cannot be guaranteed to be of the same quality.

Using this convergence-based approach for analyzing PEA's, superlinear speedup has frequently been claimed. Unfortunately many of these cases have the parallel algorithm reaching lower quality solutions than its sequential counterpart. Conversely, PEA's capable of impressive gains in solution quality display rather poor speedups.

Both Cant{\'u}-Paz \cite{cantupaz00} and Cao, et al.\ recognize that, as a general rule of thumb, ``reduction in execution time comes at the cost of a degraded solution quality.'' \cite{cao03} In other words, it appears that time savings and solution quality are inversely related to each other. If we want linear or even superlinear speedup, we must be prepared to sacrifice some solution quality; if we want to achieve high-quality solutions, we must accept that convergence-based speedup will be of the form $S(n,p)=O(p)$.

Another way of looking at speedup for a PEA involves measuring the time it takes the (sequential, parallel) algorithm to reach a solution of a certain quality. The feasibility of such an approach depends on the problem domain; if fitness values fall within a clearly defined range, let's say 0--100\%, then it is easy to set a fitness threshold somewhere along this range and measure how long it takes the algorithm to evolve a population where the average fitness exceeds the threshold. Other problem domains might distinguish between valid and invalid solutions.\footnote{A good example of this is the Knapsack Problem.} In this case, we may measure how long it takes until some proportion of the population represents valid solutions.


\section{Classes of PEA architectures}
PEA's can be classified according to their system architecture. There are five such classes:
\begin{enumerate}\compactlist
	\item Single-population master/slave
	\item Single-population fine-grained
	\item Multiple-deme coarse-grained, also known as the ``island model''
	\item Hierarchical hybrids
	\item ``Embarrassingly parallel'' evolutionary algorithms
\end{enumerate}

\subsection{Single-population master/slave PEA's}
This class of PEA's is the closest to sequential evolutionary algorithms. In the master/slave model, one processor (the master) maintains the population and performs the genetic operations such as mutation and recombination. The other processors (the slaves) are used solely for fitness evaluation. When the master generates a new individual, it sends this individual to one of the slaves; the slave executes the fitness function and sends the fitness value back to the master.
Since the population is maintained by only one processor, this algorithm reaches exactly the same solution as a sequential algorithm, albeit in a reduced time.

\subsection{Single-population fine-grained PEA's}
Fine-grained PEA's are commonly implemented on dedicated supercomputers where processors are arranged in a regular topology such as a toroid or hypercube. Each processing element represents one individual in the population. The algorithm is synchronous, with processors exchanging genetic material in lockstep with their immediate neighbors.

\subsection{Multiple-deme coarse-grained PEA's}
\label{sec:IslandModel}
Coarse-grained PEA's form the most popular class of PEA's \cite{alba99,cantupaz00}. In this algorithm, each processor is assigned a portion of the population, which is called a \emph{deme}. The demes evolve independently and from time to time some individuals migrate from one deme to another. This class is also known as the ``island model'' since it resembles the population genetics of an archipelago of islands. In fact, island model PEA's exhibit certain phenomena, occurring naturally in biological populations, that are not observed in single-population algorithms.

The biological rationale behind the island model is an evolutionary process known as \emph{allopatric speciation} \cite{dawkins04}. In plain terms, this means that a geographical separation between individuals in a population allows them to diverge from each other, creating new species.

A good example can be seen on the Gal\'{a}pagos Islands, where the narrow strips of ocean between the islands led to a wide diversity of small birds known collectively as ``Darwin's finches.'' \autoref{fig:DarwinFinches} shows the fourteen species that make up Darwin's finches; although similar, these are fourteen distinct species that all evolved from a single immigrant species that reached the Gal\'{a}pagos Islands from the South American mainland, just a few million years ago.

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[width=0.63\textwidth]{miscfigs/pea_darwin-finches}
		\caption[The fourteen species that make up Darwin's finches.]
		{The fourteen species that make up Darwin's finches. Adapted from \cite{grant99}.}
		\label{fig:DarwinFinches}
	\end{center}
\end{figure}


Implementations of the island model vary in their migration strategy and can be described as synchronous or asynchronous. In synchronous implementations migration occurs at specific time intervals, whereas in asynchronous implementations migration occurs when some internally measured level of convergence has been reached.

Cant{\'u}-Paz \cite{cantupaz00} states that an island model PEA performs optimally when migration occurs after demes have converged, implying that asynchronous implementations would be a better choice. Liu, et al.\ \cite{liu02} concur that the end-of-epoch barriers in a synchronous PEA result in considerable overhead. Tomassini \cite{tomassini99} notes that asynchronous migration is the preferred strategy for algorithms that follow the ``steady-state reproduction'' model, where a small number of offspring replace other individuals in the population as soon as they are produced instead of replacing the whole population after all the individuals have gone through a full generational cycle.

\subsection{Hierarchical hybrid PEA's}
This class of PEA's combines multiple demes with single-population PEA's. As the name suggests, they consist of more than one layer. At the upper level they are multiple-deme coarse-grained PEA's, while at the lower level they are single-population PEA's (either master/slave or fine-grained). This gives the algorithmic benefits of the island model along with the computational efficiency of single-population PEA's.

\subsection{``Embarrassingly parallel'' evolutionary algorithms}
There is also a class of ``embarrassingly parallel'' algorithms that are essentially multiple-deme PEA's without any migration. In other words, each processor executes a sequential evolutionary algorithm and the final solution is taken as the best solution among all processors. Not only are these algorithms trivial to implement, studies have shown that they lead to a poor solution quality \cite{grosso85}.

\section{Numerical analysis}
A comprehensive theoretical analysis of PEA's is given by Erick Cant{\'u}-Paz in his book ``Efficient and Accurate Parallel Genetic Algorithms'' \cite{cantupaz00}, which was based on his doctoral work under the supervision of evolutionary algorithms pioneer David Goldberg. The book introduces the classes of PEA architectures and, starting with the master/slave model, derives a set of equations for the optimal population size and the optimal interconnection network, among other things. The theoretical hypotheses are accompanied by experimental verification.

We will not reproduce the analysis here, since the equations are of limited use in a non-standard PEA like the Parallel Selfish Gene Algorithm. However, a few conclusions are of interest to us; first of all, the author argues that unless a dedicated supercomputer is available, an island model implementation is likely to give the best results.

Limiting ourselves to island model PEA's, we see that the topology of the interconnection network has very little effect on the behavior of the PEA. Rather, it is the degree of the network's graph that has a significant influence on the PEA's performance; the best (and fastest) results are obtained when the degree is approximately $p/2$, i.e. each deme has a direct connection with approximately half of the others.
