From: couturie Date: Wed, 18 Sep 2013 14:47:48 +0000 (+0200) Subject: new X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/commitdiff_plain/8fc4c8914177b38f8042870c31065ea619b900ec new --- diff --git a/BookGPU/Chapters/chapter8/ch8.tex b/BookGPU/Chapters/chapter8/ch8.tex index d131b53..fddebe9 100644 --- a/BookGPU/Chapters/chapter8/ch8.tex +++ b/BookGPU/Chapters/chapter8/ch8.tex @@ -88,7 +88,7 @@ Set the Best\_Solution to $\emptyset$; \\ Thanks to the bounding operator, B\&B allows the significant reduction of the computing time needed to explore the whole solution space. However, finding an optimal solution for large instances remains impractical using a sequential B\&B. Therefore, parallel processing of these algorithms has been widely studied in the literature. In \cite{ch8:MelabHDR_2005}, a taxonomy of the various existing parallel paradigms used to parallelize the B\&B algorithm is presented. -This taxonomy based on the classification proposed in \cite{ch8:Gendron_1994} identified several models to accelerate the B\&B search. The first model we consider in this chapter is called ``parallel tree exploration model'' and belongs to the ``tree-based'' strategies that aim to build and explore the B\&B tree in parallel. The second model called ``parallel evaluation of bounds model'' (evaluation of bounds in parallel) belong to the parallelization approach called ``node-based''. This strategy aims to accelerate the execution of a particular operation at the node level. +This taxonomy based on the classification proposed in \cite{ch8:Gendron_1994} identified several models to accelerate the B\&B search. The first model we consider in this chapter is called ``parallel tree exploration model'' and belongs to the ``tree-based'' strategies that aim to build and explore the B\&B tree in parallel. The second model called ``parallel evaluation of bounds model'' (evaluation of bounds in parallel) belong to the parallelization approach called ``node-based''. This strategy aims to accelerate the execution of a particular operation at the node level.\eject \subsection{The parallel tree exploration model} @@ -115,7 +115,8 @@ Node-based strategies introduce parallelism when performing the operations on a The parallel evaluation of bounds \index{parallel!evaluation of bounds} model, as shown in Figure \ref{ch8:bounds_parallel}, allows the parallelization of the bounding of subproblems generated by the branching operator. This model is used in the case where the bounding operator is performed several times after the branching operator. Compared to the sequential B\&B, the model does not change the order and the number of explored subproblems in the parallel B\&B algorithm. -\begin{figure} +\clearpage +\begin{figure}[t!] \begin{center} \includegraphics[scale=0.5]{Chapters/chapter8/figures/parallel_bounding.eps}% @@ -237,7 +238,7 @@ In the following, we present how we dealt with the thread/branch divergence issu During the execution of an application on GPU, one or more thread block(s) are assigned to each GPU multiprocessor to execute. Those threads are partitioned into warps that get scheduled for execution. For each instruction of the flow, the multiprocessor selects a warp that is ready to be run. A warp executes one common instruction at a time, so full efficiency is realized when all threads of a warp agree on their execution path. In this chapter, the G80 model, in which a warp is a pool of 32 threads, is used. If threads of a warp diverge via a data-dependent conditional branch, the warp serially executes each branch path taken. Threads that are not on the taken path are disabled, and when all paths are complete, the threads converge back to the same execution path. This phenomenon is called thread/branch divergence\index{GPU!thread divergence} and often causes serious performance degradations. Branch divergence occurs only within a warp; different warps execute independently regardless of whether they are executing common or disjointed code paths. -This section discusses thread divergence issues encountered when computing the bounds by GPU. The thread divergence occurs for two main reasons, namely, the locations of nodes in the search tree and the control flow instructions within the bounding operator. +This section discusses thread divergence issues encountered when computing the bounds by GPU. The thread divergence occurs for two main reasons, namely, the locations of nodes in the search tree and the control flow instructions within the bounding operator. \\ \noindent \textbf{Divergence related to the location of nodes}\\ @@ -427,6 +428,7 @@ In addition, in order to avoid relaunching the Johnson's algorithm for each coup To reduce the computation time cost of the term $\min\limits_{(i,j)\in \jmath^2, i \neq j}(r_{i,k}+q_{j,l})$ in the LB expression, two matrices are defined, namely RM and QM. They are used to store, respectively, the lowest starting and latency times of all the jobs on each machine. Their dimension is $m$ and, are accessed $ m \times (m-1)$ times and $ \frac{m \times (m-1)}{2}$ times, respectively. +\clearpage \begin{table} \centering \begin{tabular}{|c|c|c|} diff --git a/BookGPU/Chapters/chapter9/biblio9.bib b/BookGPU/Chapters/chapter9/biblio9.bib index eaa44b1..e24ab45 100644 --- a/BookGPU/Chapters/chapter9/biblio9.bib +++ b/BookGPU/Chapters/chapter9/biblio9.bib @@ -152,7 +152,7 @@ pages = {1097 - 1100} @incollection{luong2012ppsn, author={T. V. Luong and E. Taillard and N. Melab and E-G. Talbi}, -title={Parallelization Strategies for Hybrid Metaheuristics Using a Single GPU and Multi-core Resources}, +title={Parallelization Strategies for Hybrid Metaheuristics Using a Single {GPU} and Multi-core Resources}, isbn={978-3-642-32963-0}, booktitle={Parallel Problem Solving from Nature - PPSN XII}, series={Lecture Notes in Computer Science}, @@ -260,7 +260,7 @@ year={2006} @inproceedings{tsutsui, author = {S. Tsutsui and N. Fujimoto}, title = {{ACO with tabu search on a GPU for solving QAPs using move-cost adjusted thread assignment}}, - booktitle = {{Proceedings of the 13th annual conference on Genetic and Evolutionary Computation}}, + booktitle = {{Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation}}, series = {GECCO '11}, pages = {1547--1554}, year = {2011} @@ -268,7 +268,7 @@ year={2006} @inproceedings{tsutsuiGAQAP, author = {S. Tsutsui and N. Fujimoto}, - title = {{Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study}}, + title = {{Solving quadratic assignment problems by genetic algorithms with GPU computation: A Case Study}}, booktitle = {Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers}, series = {GECCO '09}, pages = {2523--2530}, @@ -298,7 +298,7 @@ year={2010} @inproceedings{maitre2009, author = {O. Maitre and L. Baumes and N. Lachiche and A. Corma and P. Collet}, title = {{Coarse grain parallelization of evolutionary algorithms on GPGPU cards with EASEA}}, - booktitle = {Proceedings of the 11th Annual conference on Genetic and evolutionary computation}, + booktitle = {Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation}, series = {GECCO '09}, pages = {1403--1410}, year = {2009} @@ -327,7 +327,7 @@ pages={1051-1059} @inproceedings{li2007, author = {J. M. Li and X. J. Wang and R. S. He and Z. X. Chi}, - title = {An Efficient Fine-grained Parallel Genetic Algorithm Based on GPU-Accelerated}, + title = {An Efficient Fine-grained Parallel Genetic Algorithm Based on {GPU}-Accelerated}, booktitle = {Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshops}, series = {NPC '07}, year = {2007}, @@ -458,7 +458,7 @@ pages={24-30} @inproceedings{Wong_2009, title={Parallel multi-objective evolutionary algorithms on graphics processing units}, author={M.L. Wong}, - booktitle={Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers}, + booktitle={{Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers}}, pages={2515--2522}, year={2009}, organization={ACM} @@ -575,7 +575,7 @@ title={{Grid’5000 French nation-wide grid. https://www.grid5000.fr}}, @book{garey, author = {M. R. Garey and D. S. Johnson}, - title = {{Computers and Intractability; A Guide to the Theory of NP-Completeness}}, + title = {{Computers and Intractability: A Guide to the Theory of NP-Completeness}}, year = {1990}, isbn = {0716710455}, publisher = {W. H. Freeman \& Co.}, diff --git a/BookGPU/Chapters/chapter9/ch9.tex b/BookGPU/Chapters/chapter9/ch9.tex index 4ad0d6f..2d44381 100644 --- a/BookGPU/Chapters/chapter9/ch9.tex +++ b/BookGPU/Chapters/chapter9/ch9.tex @@ -36,7 +36,7 @@ remarks are given in Section~\ref{ch8:conclusion} 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} @@ -44,7 +44,7 @@ A combinatorial problem $P=(S,f)$ can be defined by \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} @@ -73,7 +73,7 @@ quality solutions in reasonable computation time compared to exact 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 @@ -90,7 +90,7 @@ annealing}\index{metaheuristics!simulated annealing}~\cite{Kirkpatrick1983SA}, \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 @@ -105,7 +105,7 @@ Optimization problems, whether real-life or academic, are more 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 @@ -130,7 +130,7 @@ high-performance computing. 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}} @@ -187,7 +187,7 @@ consuming. Unlike the two previous parallel models, the 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} @@ -226,12 +226,12 @@ threads and the corresponding metaheuristic elements (one neighbor 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 @@ -294,7 +294,7 @@ the different threads degrading the performance of the application 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 @@ -313,7 +313,7 @@ perform a careful analysis on the serial code of the 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 @@ -328,7 +328,7 @@ therefore, the whole execution time of the metaheuristic. 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 @@ -339,7 +339,7 @@ of EAs on graphics processing cards and the work by Catala et al. in~\cite{catal 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 @@ -377,7 +377,7 @@ Nevertheless, small neighborhoods may lead to nonoptimal 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, @@ -393,10 +393,10 @@ efficiently map the different neighborhoods on the device memory, 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 @@ -410,7 +410,7 @@ be stored on the global memory, while the exploration of a single 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 @@ -437,7 +437,7 @@ implemented on the quadratic assignment problem (QAP) using CUDA. 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). @@ -450,7 +450,7 @@ However, even though their experiments report that the use of GPU 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 @@ -470,7 +470,7 @@ associated to one CPU core and used to accelerate the 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 @@ -499,7 +499,7 @@ involved in the evaluation of a single move. Experimentations are 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} @@ -515,7 +515,7 @@ colony optimization (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 @@ -526,7 +526,7 @@ models based on the use of one population disposed (generally) on 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 @@ -550,7 +550,7 @@ advantage of the per block approach resides in the use of shared 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 @@ -571,7 +571,7 @@ during the experiments: a benchmark mathematical function and 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 @@ -580,7 +580,7 @@ per-block is used (one individual perblock) when the acceleration 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 @@ -596,7 +596,7 @@ stored on shared memory of each block. Nevertheless, because 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 @@ -614,7 +614,7 @@ QAP benchmarks from the QAPLIB~\cite{burkard1991qaplib}. The GPU 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 @@ -629,7 +629,7 @@ same algorithm in order to assess statistical efficiency. 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 @@ -637,7 +637,7 @@ almost natural and it allows the use of shared memory to store 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 @@ -663,7 +663,7 @@ threads used to accelerate the recombination operators especially 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 @@ -687,7 +687,7 @@ communications, 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} @@ -698,7 +698,7 @@ State-of-the-art works on parallelizing 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 @@ -720,7 +720,7 @@ update, several GPU techniques are also used to increase the data 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 @@ -753,7 +753,7 @@ performed on standard QAP benchmarks showed that the GPU 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 @@ -776,7 +776,7 @@ best of each particle), the GPU threads are mapped to the \emph{N} 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 @@ -790,7 +790,7 @@ Indeed, even though the parallelization models used in most works 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 @@ -802,7 +802,7 @@ the evaluation step. Nevertheless, because of the particularity of 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 @@ -820,7 +820,7 @@ models are implemented on GPU. This classification focuses only on 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}} @@ -843,7 +843,7 @@ associated to a block of threads. A second level of parallelism is 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} @@ -851,7 +851,7 @@ require the use of very large neighborhoods or populations.\\ 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 @@ -875,7 +875,7 @@ memory. %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}: @@ -893,7 +893,7 @@ parallelized on GPU using per-thread mapping strategy (one thread 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 @@ -906,7 +906,7 @@ advantage of this hierarchical implementation is that it allows 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} @@ -918,7 +918,7 @@ on GPUs. Although the works on this subject are not yet mature and 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}, @@ -950,7 +950,7 @@ etc.). Different problem encoding is also supported. The framework 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 @@ -964,7 +964,7 @@ probability of application which may give different results from 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 @@ -1002,7 +1002,7 @@ parallelization techniques and deployment on GPUs. The framework 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}} @@ -1054,7 +1054,7 @@ iteration which starts from a disrupted local optima reached by 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 @@ -1101,7 +1101,7 @@ optimization community due to its wide range of practical 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 @@ -1155,7 +1155,7 @@ where $\pi_1$ and $\pi_2$ are permutations over the set $\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 @@ -1176,7 +1176,7 @@ escape local optima. However, this strategy may generate cycles, 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} @@ -1220,7 +1220,7 @@ The neighborhood function is a crucial parameter in any local 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 @@ -1262,7 +1262,7 @@ algorithms~\cite{Ahuja:2007:VLN:1528422.1528438}. However, for 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 @@ -1299,7 +1299,7 @@ management\index{GPU!memory management} and the 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 @@ -1403,7 +1403,7 @@ optima reached by the current TS process and reconsidering it as 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 @@ -1413,7 +1413,7 @@ of an Intel Xeon E5620 CPU and a NVIDIA Tesla Fermi M2050 (448 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 @@ -1428,7 +1428,7 @@ evaluation function of the parallel GPU version have been 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 @@ -1491,7 +1491,7 @@ This chapter has presented state-of-the-art GPU-based parallel 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 diff --git a/BookGPU/Chapters/chapter9/figures/classification.pdf b/BookGPU/Chapters/chapter9/figures/classification.pdf index a0b78ad..4271061 100644 Binary files a/BookGPU/Chapters/chapter9/figures/classification.pdf and b/BookGPU/Chapters/chapter9/figures/classification.pdf differ diff --git a/BookGPU/sunil.cls b/BookGPU/sunil.cls index 2be566f..9d42511 100755 --- a/BookGPU/sunil.cls +++ b/BookGPU/sunil.cls @@ -789,7 +789,7 @@ \@ifstar{\@ssection}{\@trplarg{\@section}}} \def\@ssection#1{% \if@ChapterTOCs - \myaddcontentsline{\@chaptoc}{chapsection}{\protect\ssubnumberline{\thesection}#1}\fi + \myaddcontentsline{\@chaptoc}{chapsection}{\protect\ssubnumberline{\ }#1}\fi \@startsection{section}{1}{\z@}{30\p@}{6\p@}{\sec@rule\nopagebreak\vskip13.5\p@\nopagebreak\SectionHeadFont}*{#1}} \def\@section[#1][#2]#3{% \if@ChapterTOCs