last version

[book_gpu.git] / BookGPU / Chapters / chapter17 / ch17.tex

diff --git a/BookGPU/Chapters/chapter17/ch17.tex b/BookGPU/Chapters/chapter17/ch17.tex
index f468214485991ed5d3db66b9bdf3a93c00c895fb..8d3c8d7685e6f6f383c836ad6018aaec107f290e 100755 (executable)
--- a/BookGPU/Chapters/chapter17/ch17.tex
+++ b/BookGPU/Chapters/chapter17/ch17.tex
@@ -13,7 +13,7 @@
   \setlength\hangindent{\mylen}%
   \hspace*{\mylen}#1\\}
 
   \setlength\hangindent{\mylen}%
   \hspace*{\mylen}#1\\}
 

-\chapter{Implementing Multi-Agent Systems on GPU}
+\chapter{Implementing multi-agent systems on GPU}

 \label{chapter17}
 
 
 \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.
 
 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
 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}
 
   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
 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}.
 
 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.
 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}
 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.
 
 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
 \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
 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,
 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}
 \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}
 
 \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
 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
 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}
 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
 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
 
 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
 \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}
   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
 
 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,
 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
 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]
 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
 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
 
 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
 \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
   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 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}
   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$
 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$
 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.
 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}
 \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}
 
 \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
 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
 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.
 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
 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
 
 \begin{itemize}
 \item A high-level library, composed of modules regrouping classes of