X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/blobdiff_plain/d62bf95f0be0f7fb4d47af9d48c1da6be3d8f132..HEAD:/BookGPU/Chapters/chapter17/ch17.tex diff --git a/BookGPU/Chapters/chapter17/ch17.tex b/BookGPU/Chapters/chapter17/ch17.tex index f468214..8d3c8d7 100755 --- a/BookGPU/Chapters/chapter17/ch17.tex +++ b/BookGPU/Chapters/chapter17/ch17.tex @@ -13,7 +13,7 @@ \setlength\hangindent{\mylen}% \hspace*{\mylen}#1\\} -\chapter{Implementing Multi-Agent Systems on GPU} +\chapter{Implementing multi-agent systems on GPU} \label{chapter17} @@ -48,7 +48,7 @@ and grids are often identified as the main solution to increase simulation performance but GPUs are also a promising technology with an attractive performance/cost ratio. -Conceptually a MAS\index{Multi-Agent System} is a distributed system +Conceptually a MAS\index{multi-agent system} is a distributed system as it favors the definition and description of large sets of individuals, the agents, that can be run in parallel. As a large set of agents could have the same behavior, a Single Instruction Multiple @@ -157,7 +157,7 @@ For that, three major approaches can be identified: resources (multi-threading, GPU, and so on) \cite{Aaby10}. \end{enumerate} -In the first case, experiments are run independently of each other and +In the first case, experiments are run independent of each other and only simulation parameters are changed between two runs so that a simple version of an existing simulator can be used. This approach does not, however, allow to run larger models. In the second and the @@ -169,12 +169,11 @@ based on the explicit use of threads using shared memory~\cite{Guy09clearpath} or cluster libraries such as MPI~\cite{Kiran2010}. -Parallelizing a multi-agent simulation is however complex due to space +Parallelizing a multi-agent simulation is, however, complex due to space and time constraints. Multi-agent simulations are usually based on a synchronous execution: at each time step, numerous events (space data modification, agent motion) and interactions between agents happen. -Distributing the simulation on several computers or grid nodes thus -implies to guarantee a distributed synchronous execution and +Distributing the simulation on several computers or grid nodes to guarantee a distributed synchronous execution and coherency. This often leads to poor performance or complex synchronization problems. Multicore execution or delegating part of this execution to others processors such as GPUs~\cite{Bleiweiss_2008} @@ -298,7 +297,7 @@ collembolas in fields and forests. It is based on a diffusion algorithm which illustrates the case of agents with a simple behavior and few synchronization problems. -\subsection{The Collembola model\index{Collembola model}} +\subsection{The Collembola model\index{collembola model}} \label{ch17:subsec:collembolamodel} The Collembola model is an example of multi-agent system using GIS @@ -308,7 +307,7 @@ version of this model has been developed with the Netlogo framework by Bioemco and UMMISCO researchers. In this model, the biodiversity is modeled by populations of athropod individuals, the Collembola, which can reproduce and diffuse to favorable new habitats. The simulator -allows us to study the diffusion of collembola, between plots of land +allows us to study the diffusion of Collembola, between plots of land depending on their use (artifical soil, crop, forest, etc.) In this model the environment is composed of the studied land, and collembola are used as agents. Every land plot is divided into several cells, @@ -329,7 +328,7 @@ Figure~\ref{ch17:fig:collem_algorithm}: \begin{figure}[h] \centering \includegraphics[width=0.6\textwidth]{Chapters/chapter17/figs/algo_collem.pdf} -\caption{Evolution algorithm of Collembola model.} +\caption{Evolution algorithm of the Collembola model.} \label{ch17:fig:collem_algorithm} \end{figure} @@ -346,14 +345,14 @@ assimilated to a reduction operation on all the population cells associated to one plot to obtain its population. The {\bf diffusion} stage simulates the natural behavior of the -collembola that tends toward occupying the whole space over time. This +Collembola that tends toward occupying the whole space over time. This stage consists in computing a new value for each cell depending on the population of the neighbor cells. This process can be assimilated to a linear diffusion at each iteration of the population of the cells across their neighbors. These two processes are quite common in numerical computations so that -the collembola model can be adapted to a GPU execution without much +the Collembola model can be adapted to a GPU execution without much difficulty. \subsection{Collembola implementation} @@ -488,7 +487,7 @@ Multiple implementations of the MIOR model have already been realized, in Smalltalk and Netlogo, in 2 or 3 dimensions. The last implementation, used in our work and referenced as MIOR in the rest of the chapter, is freely accessible online as -WebSimMior~\footnote{http://www.IRD.fr/websimmior/}. +WebSimMior\footnote{http://www.IRD.fr/websimmior/}. MIOR is based around two types of agents: (1) the Meta-Mior (MM), which represents microbial colonies consuming carbon and (2) the @@ -500,7 +499,7 @@ The Meta-Mior agents are characterized by two distinct behaviors: \item \emph{breath}: this action converts mineral carbon from the soil to carbon dioxide ($CO_{2}$) that is released into the soil and \item \emph{growth}: by this action each microbial colony fixes the - carbon present in the environment to reproduce itself (augments its + carbon present in the environment to reproduce itself (augment its size). This action is only possible if the colony breathing needs are covered, i.e., enough mineral carbon is available. \end{itemize} @@ -567,7 +566,7 @@ the simulation each on its own GPU core. The usage of one work-group for each simulation allows the easy execution of multiple simulations in parallel, as shown on -figure~\ref{ch17:fig:gpu_distribution}. By taking advantage of the +Figure~\ref{ch17:fig:gpu_distribution}. By taking advantage of the execution overlap possibilities provided by OpenCL, it then becomes possible to exploit all the cores at the same time, even if an unique simulation is too small to use all the available GPU cores. However, @@ -623,7 +622,7 @@ optimized representation of this matrix based on~\cite{Gomez-Luna:2009:PVS:1616772.1616869}, as illustrated in Figure~\ref{ch17:fig:csr_representation}. This compact representation considers each line of the matrix as an index list, and only stores -accessible agents compactly, to reduce the number of non-productive +accessible agents compactly, to reduce the number of nonproductive accesses. \begin{figure}[h] @@ -658,7 +657,7 @@ of MIOR as well as for other ABM, to ensure that each work-item is not too constrained in its execution. \pagebreak -\lstinputlisting[caption=main MIOR kernel,label=ch17:listing:mior_kernels]{Chapterbis/chapter17/code/mior_kernels.cl} +\lstinputlisting[caption=main MIOR kernel,label=ch17:listing:mior_kernels]{./Chapters/chapter17/code/mior_kernels.cl} From the sequential algorithm (Algorithm~\ref{ch17:seqalgo}) where all the agents share the same data, we have developed a parallel algorithm @@ -725,7 +724,7 @@ performance indicator. \begin{itemize} \item The \textbf{GPU 1.0} implementation is a direct implementation of the existing algorithm and its data structures where data - dependencies were removed, and it uses the non-compact topology + dependencies were removed, and it uses the noncompact topology representation described in Section~\ref{ch17:subsec:datastructures} \item The \textbf{GPU 2.0} implementation uses the previously described compact representation of the topology and remains @@ -736,7 +735,7 @@ performance indicator. \item The \textbf{GPU 4.0} implementation is a variant of the GPU 1.0 implementation but allows the execution of multiple simulations for each kernel execution. -\item the \textbf{GPU 5.0} implementation is a multi-simulation +\item The \textbf{GPU 5.0} implementation is a multisimulation version of the GPU 2.0 implementation, using the execution of multiple simulations for each kernel execution as for GPU 4.0. \end{itemize} @@ -753,11 +752,11 @@ one is representative of the kind of hardware which is available on HPC clusters. It is a cluster node dedicated to GPU computations with two Intel X5550 processors running at $2.67$GHz and one Tesla C1060 GPU device running at $1.3$GHz and composed of $240$ cores ($30$ -multi-processors). The second platform illustrates what can be +multiprocessors). The second platform illustrates what can be expected from a personal desktop computer built a few years ago. It uses an Intel Q9300 CPU, running at $2.5$GHz, and a Geforce 8800GT GPU running at $1.5$GHz and composed of $112$ cores ($14$ -multi-processors). The purpose of these two platforms is to assess the +multiprocessors). The purpose of these two platforms is to assess the benefit that could be obtained when a scientist has access either to specialized hardware as a cluster or tries to take advantage of its own personal computer. @@ -786,12 +785,12 @@ performance. \begin{figure}[!h] \centering \includegraphics[width=0.7\linewidth]{Chapters/chapter17/figs/mior_perfs_8800gt.pdf} -\caption{CPU and GPU performance on a personal computer with a Geforce 8800GT} +\caption{CPU and GPU performance on a personal computer with a Geforce 8800GT.} \label{ch17:fig:mior_perfs_8800gt} %end{minipage} \end{figure} -\b The charts show that for small problems the execution times of all +The charts show that for small problems the execution times of all the implementations are very close. This is because the GPU execution does not have enough threads (representing agents) for an optimal usage of GPU resources. This trend changes around scale $5$ where GPU @@ -948,7 +947,7 @@ data structures when these situations occur. Both approaches require trending either memory or performance and are not always practical. Another limitation is the impossibility to store pointers in data -structures, since OpenCL only allows one dimension static arrays. This +structures, since OpenCL only allows one-dimension static arrays. This precludes the usage of structures such as linked-list, graphs or sparse matrices not represented by some combination of static arrays, and can be another source of memory or performance losses. @@ -1000,7 +999,7 @@ MCSMA~\cite{lmlm+13:ip} is a framework developed to provide to the MAS designer those basic data structures and the associated operations, to facilitate the portage of existing MAS on GPU. Two levels of utilization are provided to the developer, depending on its usage -profile:²< +profile: \begin{itemize} \item A high-level library, composed of modules regrouping classes of