\setlength\hangindent{\mylen}%
\hspace*{\mylen}#1\\}
-\chapter{Implementing Multi-Agent Systems on GPU}
+\chapter{Implementing multi-agent systems on GPU}
\label{chapter17}
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
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
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}
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
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,
\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}
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}
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
\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}
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,
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]
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
\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
\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}
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.
\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
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.
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
