Combinatorial optimization (CO) is a branch of applied and discrete mathematics.
It consists in finding optimal configuration(s) among a finite set of possible configurations
-(or solutions) of a given combinatorial optimization problem (COP). The set of all possible solutions noted $S$ is called solution space or search space. Each solution in $S$ is defined by its real cost calculated by an objective function. COPs are generally defined as follows~\cite{blumMeta}:\\ %(Definition~\ref{def:cops})
+(or solutions) of a given combinatorial optimization problem (COP). The set of all possible solutions noted $S$ is called solution space or search space. Each solution in $S$ is defined by its real cost calculated by an objective function. COPs are generally defined as follows~\cite{blumMeta}: %(Definition~\ref{def:cops})
%\begin{minipage}{0.5\linewidth}
\begin{itemize}
\item a set of decision variables $X$,
\item an objective function $f$ to optimize (minimize or maximize) over the set $S$,
-\item subject to constraints on the decision variables.\\
+\item subject to constraints on the decision variables.
\end{itemize}
%\end{minipage}
methods but with no guarantee to find optimal or even bounded
solutions. This is due to the nature of the search process adopted
by these approaches which consists of performing a
-search in a subset of the whole search space.\\
+search in a subset of the whole search space.
Regarding the number of solutions considered at each iteration in
the search process, two classes of metaheuristics can be
\emph{tabu search}~\cite{Glover1989TS}, \emph{iterated local
search\index{metaheuristics!iterated local
search}}~\cite{stutzle2006ILSforQAP}, and \emph{variable
-neighborhood search}~\cite{HansenMladenovic1997VNS}.\\
+neighborhood search}~\cite{HansenMladenovic1997VNS}.
Unlike s-metaheuristics, p-metaheuristics start with a population
of solutions and implement an iterative process that evolves the
often NP-hard and CPU time and/or memory consuming. Metaheuristics
allow the significant reduction of the computational time of the search
process but remain time-consuming particularly when it comes
-dealing with large-sized problems. \\
+dealing with large-sized problems.
The use of parallelism in the design of metaheuristics is a relevant
approach that is widely adopted by the combinatorial optimization
From the granularity of parallelism point of view, three major parallel
models for metaheuristics can be distinguished~\cite{talbi2009mfdti}: \emph{algorithmic-level}\index{metaheuristics!algorithmic-level parallelism},
-\emph{iteration-level}\index{metaheuristics!iteration-level parallelism}, and \emph{solution-level} as illustrated in Figure~\ref{ch8:fig:paraMeta}. \\
+\emph{iteration-level}\index{metaheuristics!iteration-level parallelism}, and \emph{solution-level} as illustrated in Figure~\ref{ch8:fig:paraMeta}.
\begin{figure}[h!]
\centerline{\includegraphics[width=0.6\textwidth]{Chapters/chapter9/figures/paraMeta.pdf}}
solution-level\index{metaheuristics!solution-level parallelism}
parallel model is problem-dependent.}
\end{itemize}
-
+\clearpage
\section{Challenges for the design of GPU-based metaheuristics}
\label{ch8:sec:challenges}
per thread, one individual per thread, single population per
threads block, one ant per thread, etc.) must be defined to ensure
a maximum occupancy of the GPU and
-to cover CPU/GPU communication\index{GPU!CPU/GPU communication} and memory access times.\\
+to cover CPU/GPU communication\index{GPU!CPU/GPU communication} and memory access times.
According to the used metaheuristic and to the handled problem, the data
values may have different types and different ranges of their values. The data
types should then be chosen carefully and the ranges of the data values should
-be analyzed to minimize the amount of occupied memory space.\\
+be analyzed to minimize the amount of occupied memory space.
In addition to the size and latency of GPU memory issues, the
memory access pattern is another important issue to be dealt with
in terms of execution time. The challenge here is then to revisit
the traditional irregular metaheuristic codes to eliminate these
divergences.
-
+\clearpage
\subsection{Task distribution and CPU/GPU communication}
The performance of GPU-based metaheuristics in terms of execution
metaheuristic, identify the compute-intensive tasks (e.g.,
exploration of the neighborhood, evaluation of individuals), and
then offload them to the GPU, while the remaining
-tasks still run on the CPU in a serial way. \\
+tasks still run on the CPU in a serial way.
The CPU/GPU communication is done through the global
memory which is a slow memory making the memory transfer between
After more than two decades of research by the combinatorial optimisation
community devoted to developing adequate parallel metaheuristics for different types of
parallel architectures (clusters, supercomputers and grids), the actual developement
-of General Perpose GPU (GPGPU) brings new challenges for parallel metaheuristics on SIMD architectures.\\
+of General Perpose GPU (GPGPU) brings new challenges for parallel metaheuristics on SIMD architectures.
The first works on metaheuristic algorithms implemented on GPUs
started on old graphics cards before the appearance of modern GPUs
is implemented on old GPU architectures. Yu et al.~\cite{yu2005} and
Li et al.~\cite{li2007} proposed a full parallelization of genetic
algorithms on old GPU architectures using
-shader libraries based on Direct3D and OpenGL.\\
+shader libraries based on Direct3D and OpenGL.
Such architectures are based on preconfigured pipelined stages
used to accelerate the transformation of 3D geometric primitives
occupation of the CUDA threads which may lead in turn to an
overhead due to the communication and memory latencies. Therefore,
large neighborhoods are necessary for efficient implementation of
-local searches on GPUs.\\
+local searches on GPUs.
Luong et al.~\cite{luong2010large} proposed efficient
mappings for large neighborhood structures on GPUs. In this work,
more explicitly, how to calculate the memory index of each
solution associated to each CUDA thread's \textit{id}.
%For 1-Hamming neighborhoods, as there is exactly n solutions in the neighborhood, the mapping of this neighborhood to CUDA threads is obvious: the CPU host offloads to GPU exactly $n$ threads, and each thread id is associated to one index in the binary vector. In the case of 2-Hamming and 3-Hamming neighborhoods, each thread id should be mapped respectively to two and three indexes in the candidate vector.
-The three neighborhoods are implemented and experimented on the Permuted Perceptron Problem (PPP) using a tabu search\index{metaheuristics!tabu search} algorithm (TS). Accelerations from $9.9 \times$ to $18.5 \times$ are obtained on different problem sizes.\\ % The experiments are performed on an Intel Xeon 8 cores 3GHz coupled with an NVIDIA GTX 280 card.\\
+The three neighborhoods are implemented and experimented on the Permuted Perceptron Problem (PPP) using a tabu search\index{metaheuristics!tabu search} algorithm (TS). Accelerations from $9.9 \times$ to $18.5 \times$ are obtained on different problem sizes. % The experiments are performed on an Intel Xeon 8 cores 3GHz coupled with an NVIDIA GTX 280 card.\\
In the same context, Deevacq et al.~\cite{audreyANT}
-proposed two parallelization strategies inspired by the multi-walk
+proposed two parallelization strategies inspired by the multiwalk
parallelization strategy, of a 3-opt iterated local
search algorithm (ILS)
over a CPU/GPU architecture. In the first strategy, each Local
solution at a time in the second strategy allows the use of the
shared memory to store the related data structures. The two
strategies have been experimented on standard benchmarks of
-the Traveling Salesman Problem (TSP) with sizes varying from $100$ to $3038$ cities. The results indicate that increasing the number of solutions to be explored simultaneously improves the speedup in the two strategies, but at the same time it decreases final solution quality. The greater speedup factor reached by the second strategy is $6 \times$.\\
+the Traveling Salesman Problem (TSP) with sizes varying from $100$ to $3038$ cities. The results indicate that increasing the number of solutions to be explored simultaneously improves the speedup in the two strategies, but at the same time it decreases final solution quality. The greater speedup factor reached by the second strategy is $6 \times$.
The same strategy is used by Luong et al.
in~\cite{luongMultiStart} to implement multistart parallel local
The acceleration rates obtained for the
algorithmic-level with usage of texture memory rise from $7.8\times$ to
$12\times$ (for different
-QAP benchmark sizes). \\
+QAP benchmark sizes).
Janiak et al.~\cite{Janiak_et_al_2008} implemented two
algorithms for TSP and the flow-shop scheduling problem (FSP).
speedups the serial execution almost $16 \times$, the mapping of
one thread with one tabu search
requires a large number of local search algorithms to
-cover the memory access latency. The same mapping policy is adopted by Zhu et al. in~\cite{zhu_et_al_2008} (one thread is associated to one local search) solving the quadratic assignment problem but using the CUDA toolkit instead of shader libraries.\\
+cover the memory access latency. The same mapping policy is adopted by Zhu et al. in~\cite{zhu_et_al_2008} (one thread is associated to one local search) solving the quadratic assignment problem but using the CUDA toolkit instead of shader libraries.
Luong et al.~\cite{luong2012ppsn} proposed a GPU-based
implementation of hybrid metaheuristics on heterogeneous parallel
neighborhood calculation of several S-metaheuristics at the same
time.
In order to efficiently exploit the remaining CPU cores, a load-balancing heuristic is also proposed in order to decide on the number of additional
-S-metaheuristics to launch on the remaining CPU cores relative to the efficiency of the GPU calculations. The proposed approach is applied to the QAP using several instances of the Fast Ant Colony Algorithm (FANT)~\cite{taillardFant}. \\
+S-metaheuristics to launch on the remaining CPU cores relative to the efficiency of the GPU calculations. The proposed approach is applied to the QAP using several instances of the Fast Ant Colony Algorithm (FANT)~\cite{taillardFant}.
All the previously noted works exploit the same parallel models
used on CPUs based on the task parallelism. A different
done on standard QAP instances from the
QAPLIB~\cite{burkard1991qaplib}. Speedups up to $10 \times$ are
achieved by the GPU implementation compared
-to the same sequential implementation on CPU using SA-matrix.\\
+to the same sequential implementation on CPU using SA-matrix.
\subsection[Implementing population-based metaheuristics\hfill\break on GPUs]{Implementing population-based metaheuristics on GPUs}
(ACO), and particle
swarm optimization\index{metaheuristics!particle swarm
optimization} (PSO).
-
+\clearpage
\subsubsection*{Evolutionary algorithms}
Traditional parallel models for EAs are classified in three main
a toroidal grid.
The three traditional models have been implemented on GPUs by several researchers for different
-optimization problems. The main chalenges to be raised when implementing the traditional models on GPUs concern (1) the saturation of the GPU in order to cover memory latency by calculations, and (2) efficent usage of the hierarchical GPU memories.\\
+optimization problems. The main chalenges to be raised when implementing the traditional models on GPUs concern (1) the saturation of the GPU in order to cover memory latency by calculations, and (2) efficent usage of the hierarchical GPU memories.
In~\cite{kannan}, Kannan and Ganji present a CUDA implementation
of the drug discovery application Autodock (molecular docking
memory instead of global memory to store all the information
related to each individual. The obtained speedups range from $10
\times$ to $47 \times$ for population sizes
-ranging from $50$ to $10000$. \\
+ranging from $50$ to $10000$.
Maitre et al.~\cite{maitre2009} also exploited the
master-slave parallelism of EAs on GPUs using EASEA. EASEA is a
real problem (molecular structure prediction). In order to
maximize the GPU occupation, very large populations are used (from
$2000$ to $20000$). Even though transferring such large
-populations from the CPU to the GPU device memory at every generation is very costly, the authors report important speedups on the two problems on a GTX260 card: $105 \times$ is reported for the benchmark function while for the real problem the reported speedup is $60 \times$. This may be best explained by the complexity of the fitness functions. Nevertheless, there is no indication in the paper about the memory management of the populations on GPU.\\
+populations from the CPU to the GPU device memory at every generation is very costly, the authors report important speedups on the two problems on a GTX260 card: $105 \times$ is reported for the benchmark function while for the real problem the reported speedup is $60 \times$. This may be best explained by the complexity of the fitness functions. Nevertheless, there is no indication in the paper about the memory management of the populations on GPU.
The master-slave model is efficient when the fitness function is
highly time intensive. Nevertheless, it requires the use of
of the fitness function itself is possible. The use of many
subpopulations of medium sizes is another way to obtain a maximum
occupation of the GPU. This is coarse-grained parallelism (island
-model).\\
+model).
The coarse-grained model is used by Pospichal et al.
in~\cite{pospichal10} to implement a parallel genetic
interblock communications are not possible on the CUDA
architecture, the islands evolve independently in each block, and
migrations are performed
-asynchronously through the global memory. That is, after a given number of generations, selected individuals for migration from each island are copied to the GPU global memory part of the neighbor island and then to its shared memory to replace the worst individuals in the local population. The experiments are performed on three benchmark mathematical functions. During these experiments, the island sizes are varied from $2$ to $256$ individuals and island numbers from $1$ to $1024$. The maximum performance is achieved for high number of islands and increasing population sizes.\\
+asynchronously through the global memory. That is, after a given number of generations, selected individuals for migration from each island are copied to the GPU global memory part of the neighbor island and then to its shared memory to replace the worst individuals in the local population. The experiments are performed on three benchmark mathematical functions. During these experiments, the island sizes are varied from $2$ to $256$ individuals and island numbers from $1$ to $1024$. The maximum performance is achieved for high number of islands and increasing population sizes.
The same strategy is also adopted by Tsutsui and Fujimoto
in~\cite{tsutsuiGAQAP} to implement a coarse-grained genetic
implementation reached speedups of $2.9\times$ to $12.6 \times$
compared to a single core implementation of a coarse-grained
genetic algorithm on a
-Intel i7 processor.\\
+Intel i7 processor.
Nowotniak and Kucharski~\cite{nowotniak} proposed a GPU-based
implementation of a Quantum Inspired Genetic Algorithm (QIGA). The
populations are stored in the shared memory, the data matrix used
for fitness evaluation is placed in read only constant memory, and
finally seeds for random numbers generated on the GPU are stored
-in the global memory.\\
+in the global memory.
In coarse-grained parallelism, the use of the per-block approach
to implement the islands (one subpopulation per thread block) is
the subpopulations. Fine-grained parallel models for EAs (cellular
EAs) have been used by many authors to implement parallel EAs on
GPUs. Indeed, the fine-grained parallelism of EAs fits perfectly
-to the SIMD architecture of the GPU. \\
+to the SIMD architecture of the GPU.
Pinel et al. in~\cite{pinel2012JPDC} developed a highly
parallel synchronous cellular genetic
when dealing with large instances of the problem. In addition to
the recombination operators, the rest of the CGA steps are also
parallelized on GPU (fitness evaluation, mutation, and
-replacement).\\
+replacement).
A similar work is proposed by Vidal and Alba in~\cite{albaCGAGPU}
where a CGA using a toroidal grid is completely implemented on
synchronization, and access to global memory. Finally, an
interesting review on GPU parallel computation in bio-inspired
algorithms is proposed by Arenas et al.
-in~\cite{arenas2011}. \\
+in~\cite{arenas2011}.
\subsubsection*{Ant colony optimization}
ACO focus on
accelerating the tour construction step performed by each ant by
taking a task-based parallelism approach, with pheromone
-deposition on the CPU.\\
+deposition on the CPU.
In~\cite{cecilia}, Cecilia et al. present a GPU-based
implementation of
bandwidth of the application mainly by the use of precalculated
matrices that are easily updated by several threads (one thread
per matrix entry). The achieved speedups are $21 \times$ for tour
-construction and $20 \times$ for pheromone updates.\\
+construction and $20 \times$ for pheromone updates.
In another work, Tsutsui and Fujimoto~\cite{tsutsui} propose a
hybrid algorithm combining
implementation using MATA obtained a speedup of $19 \times$
compared to the CPU implementation, compared with a speedup of
only $5 \times$
-when MATA is not used. \\
+when MATA is not used.
\subsubsection*{Particle swarm optimization}
In~\cite{zhou2009} Zhou and Tan propose a full GPU implementation
particles of the swarm one to one. Experiments done on four
benchmark functions show speedups ranging from $3.7 \times$ to
$9.0 \times$ for swarm sizes
-ranging from $400$ to $2800$.\\
+ranging from $400$ to $2800$.
\subsection{Synthesis of the implementation strategies}
\label{ch8:sec:synthesis} After reviewing some works dealing with
for GPUs are derived from the traditional parallel models of each
metaheuristic (on CPU), their implementation could take a
different way and sometimes it may result in new parallel models
-customized for GPUs.\\
+customized for GPUs.
Traditional parallel models for metaheuristics are based on an
intuitive task parallelism: the independent tasks of the
the GPU architecture, some authors have used new implementation
techniques to enhance the data parallelism in the sequential
algorithms in order to increase the data throughput of the
-application.\\
+application.
From this observation we propose the following classification
based on 2 levels: design level and implementation level as
the mapping strategies between the GPU threads and the
parallelized tasks (neighborhood evaluation, solution
construction, and so on). The different implementation strategies
-are explained in the following sections.\\
+are explained in the following sections.
\begin{figure}[h]
\centerline{\includegraphics[width=1\textwidth]{Chapters/chapter9/figures/classification.pdf}}
used inside each block to parallelize the fitness evaluation of a
single solution. This kind of mapping allows the use of shared
memory to store the data structures of the solution and does not
-require the use of very large neighborhoods or populations.\\
+require the use of very large neighborhoods or populations.
%data parallelism in SA-matrix to parallelize
\subsubsection*{GPU thread mapping for iteration-level parallelism}
Iteration-level parallelism consists of parallelizing the tasks
performed independently on different solutions. Different mapping
strategies are adopted in the reviewed works to implement these
-models.\\
+models.
In Figure \ref{ch8:fig:classification}, the first example of
iteration-level
%pheromone update data parallelism matrices
\subsubsection*{GPU thread mapping for algorithmic-level parallelism}
-Algorithmic-level parallelism consists of launching several self-contained algorithms in parallel. In the previously reviewed works two algorithmic-level models have been used: the multistart model and the island model (parallel EAs).\\
+Algorithmic-level parallelism consists of launching several self-contained algorithms in parallel. In the previously reviewed works two algorithmic-level models have been used: the multistart model and the island model (parallel EAs).
The implementation of the multistart model is based on two
different mapping strategies~\cite{luongMultiStart, audreyANT}:
per solution). This consists of a hierarchical parallel model
combining algorithmic-level parallelism (multistart) with
iteration-level
-parallelism (master-worker).\\
+parallelism (master-worker).
In the island model, the same mapping is used in all the reviewed
works~\cite{tsutsuiGAQAP, nowotniak, maitre2009}: each
the occupation of a large number of threads even for medium
population sizes. The second advantage consists of using shared
memory to store subpopulations to benefit from the low latency of
-shared memory.\\
+shared memory.
\section{Frameworks for metaheuristics on GPUs}
\label{ch8:sec:frameworks}
do not cover the main metaheuristic algorithms, we will present
the only three works to our knowledge, which propose open source
frameworks for developing
-metaheuristics on GPUs.\\
+metaheuristics on GPUs.
The three frameworks reviewed in this section are
PUGACE\index{GPU-based frameworks!PUGACE}~\cite{pugace},
is organized as a set of modules in which the different
functionalities are separated as much as possible in order to
facilitate the extension of the framework. All
-the functions and procedures that execute on GPU are implemented in the same file kernel.cu. \\
+the functions and procedures that execute on GPU are implemented in the same file kernel.cu.
The implementation strategy adopted on the GPU is as follows.
Population initialization is done on the CPU side and the
one thread to the other), the decision of whether to apply a
crossover is taken at the block level and applied to all the
individuals within the block. It is the decision on the choose
-of the cutting point for the crossover.\\
+of the cutting point for the crossover.
The framework is validated on standard benchmarks of the QAP. Speedups of $15.44 \times$ to $18.41
\times$ are achieved compared to a CPU implementation of a cEA
allows one to efficiently manage the hierarchical organization of
the memories (latencies and sizes) of the GPU and its
communication with the CPU as well as the minimizing of the user
-involvement in its management.\\
+involvement in its management.
\begin{figure}[h]
\centerline{\includegraphics[width=0.8\textwidth]{Chapters/chapter9/figures/paradiseoGPU.pdf}}
the previous local search process. The disruption heuristic is a
performance parameter of an ILS algorithm and should be
judiciously defined. A template of an
-ILS algorithm is given by the Algorithm~\ref{ch8:ils_algorithm_template}.\\
+ILS algorithm is given by the Algorithm~\ref{ch8:ils_algorithm_template}.
\begin{algorithm}[H]
\SetAlgoLined
applications (site planning, schedule problem, computer-aided
design, etc.) and to its computational challenges since it is
considered as one of the most computationally difficult
-optimization problems.\\
+optimization problems.
The Q3AP was first introduced by William P. Pierskalla in
1967~\cite{Pierskalla1967Q3AP} and, unlike the QAP, the Q3AP is a
$\left\lbrace 0,1,\ldots,n-1\right\rbrace$. According to this
formulation, minimizing the Q3AP consists of finding a double
permutation $(\pi_1,\pi_2)$ which minimizes the objective function
-(\ref{Q3APPermutationBasedFormulation}).\\
+(\ref{Q3APPermutationBasedFormulation}).
The Q3AP is proven to be an NP-hard problem since it is an
extension of the quadratic assignment problem and of the axial
i.e., previous moves can be selected again. To avoid cycles, the
TS manages a short-term memory that contains the moves that have
been recently performed. A TS
-template is given by Algorithm \ref{TS_pseudo_code}.\\
+template is given by Algorithm \ref{TS_pseudo_code}.
%
% \begin{algorithm}
% \label{TS_pseudo_code}
search algorithm. Indeed, if the neighborhood function is not
adequate to the problem and/or does not consider the targeted
computing framework, any local search algorithm will fail to reach
-good quality solutions of the search space.\\
+good quality solutions of the search space.
Regarding the Q3AP, many neighborhood structures can be
considered. A basic neighborhood was proposed and investigated in
such a neighborhood, the generation/evaluation step of an LS
becomes a time-consuming task and may dramatically increase the
computational time of the LS process. This
-justifies the use of intensive data-parallelism provided by GPUs where all neighboring solutions may be concurrently evaluated. \\
+justifies the use of intensive data-parallelism provided by GPUs where all neighboring solutions may be concurrently evaluated.
The considered large-sized neighborhood consists of swapping two
positions in both permutations $\pi_1$ and $\pi_2$. This
capacity constraints of GPU memories, and the thread
synchronization. All these issues must be regarded when designing
parallel LS models to allow
-solving of large scale optimization problems on GPU architectures.\\
+solving of large scale optimization problems on GPU architectures.
To go back to our problem (i.e., Q3AP), we propose in
Algorithm~\ref{ch8:algoITS} an iterated tabu
initial solution of the following TS process. Regarding our
algorithm, the applied perturbation is a random number $\mu $ of
swaps in either the first or the second permutation where $\mu \in
-[2:n]$ ($n$ is the instance size).\\
+[2:n]$ ($n$ is the instance size).
Experiments have been carried out on a node of the Chirloute
cluster of the Lille site. This is one of the 10 sites that
cores) GPU type. The number of ILS iterations and the number of TS
iterations were set respectively to 20 and 500. The tabu list size
has been initalized to $\frac{m}{4}$, $m$ being the size of the
-neighborhood set.\\
+neighborhood set.
Table \ref{ch8:ITSQ3APResults} reports the obtained results for
the GPU-ITS using our large-sized neighborhood structure. The
measured. The number of successful tries (hits) and the average
number of ILS iterations to converge to the optimal/best known
value are also represented. The associated standard deviation for
-each average measurement is shown in small type characters.\\
+each average measurement is shown in small type characters.
\begin{table}
%\tiny
metaheuristics and
a case study on implementing large neighborhood local search
methods on GPUs for solving large benchmarks of the quadratic
-three-dimensional assignment problem (Q3AP). \\
+three-dimensional assignment problem (Q3AP).
Implementing parallel
metaheuristics on
