@Book{succi-book,
author = {Succi, S.},
- title = {The lattice {B}oltzmann {E}quation and {B}eyond},
+ title = {The {L}attice {B}oltzmann {E}quation and {B}eyond},
publisher = {Oxford University Press, Oxford},
year = {2001},
}
version, the necessary transfers are implemented in place using
a vector of MPI datatypes with appropriate stride for each direction.
-
+\clearpage
\section{Single GPU implementation}\label{ch14:sec:singlegpu}
-
+\clearpage
\section{Summary}
\label{ch14:sec:summary}
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
+\clearpage
\putbib[Chapters/chapter14/biblio14]
%\begin{thebibliography}{1}
@Book{Trzynadlowski:Book'10,
author = "A. M. Trzynadlowski",
title = "Introduction to Modern Power Electronics",
- publisher = "Wiley",
- edition = "Second",
+ publisher = "second edition, Wiley",
+OPTedition = "Second",
year = "2010"
}
@MISC{gpgpu,
author = {D. G\"{o}ddeke},
- title = {General-Purpose Computation Using Graphics Harware},
+ title = {General-Purpose Computation Using Graphics Hardware},
howpublished = {\url{http://www.gpgpu.org/}},
year = 2011
}
@conference{LiuTan1:DATE'12,
author={X.-X. Liu and S. X.-D. Tan and H. Wang and H. Yu},
-title={A {GPU}-accelerated envelope-following method for switching power converter simulation”},
+title={A {GPU}-accelerated envelope-following method for switching power converter simulation},
booktitle= date,
year={2012},
pages = {1349-1354},
\input{Chapters/chapter16/gpu.tex}
\input{Chapters/chapter16/exp.tex}
+\clearpage
\section{Summary}
\label{sec:summary}
-In this chapter, we present a new envelope-following method for
+In this chapter, we have presented a new envelope-following method for
transient analysis of switching power converters. First, the
-computationally expensive step, the solving of Newton update equation,
+computationally expensive step, the solving of the Newton update equation,
has been parallelized on CUDA-enabled GPU platforms with iterative
GMRES solver to boost performance of the analysis method. To further
-speed up the GMRES solving for Newton update equation, we have
+speed up the GMRES solving for the Newton update equation, we have
employed the matrix-free Krylov basis generation technique. The
proposed method also applies the more robust Gear-2 integration to
compute the sensitivity matrix. Experimental results from several
integrated on-chip power converters have shown that the proposed GPU
envelope-following algorithm can lead to about 10$\times$ speedup
compared to its CPU counterpart, and 100$\times$ faster than the
-traditional envelope-following methods while still keeps the similar
+traditional envelope-following methods while still keep the similar
accuracy.
\begin{Glossary}
\item[Envelope-Following] In transient simulation of switching power circuits,
nodal voltage waveforms in neighboring high frequency clock cycles are similar,
-but not exactly the duplicates. Envelope-following technique approximates
+but not exactly duplicates. Envelope-following technique approximates
the slowly changing transient trend over a lot of clock cycles
without calculating waveforms in all cycles.
\end{Glossary}
a boosted version of traditional transient analysis,
with certain skips over several periods and a Newton iteration
to update or correct the errors brought by the skips,
-as is exhibited by Fig.~\ref{fig:ef_flow}.
+as is exhibited by Figure~\ref{fig:ef_flow}.
\begin{figure}[!tb]
\centering
\resizebox{.7\textwidth}{!}{\input{./Chapters/chapter16/figures/ef_flow.pdf_t}}
We use several integrated on-chip converters as simulation examples
to measure running time and speedup. They include a Buck converter,
-a quasi-resonant flyback converter (shown in Fig.~\ref{fig:flyback}),
+a quasi-resonant flyback converter (shown in Figure~\ref{fig:flyback}),
and two boost converters.
Each converter is directly integrated with on-chip power grid networks,
-since the performance of converters should be studied with their loads and
+since the performance of the converters should be studied with their loads and
we can easily observe the waveforms at different nodes in a power
-grid (see Fig.~\ref{fig:pg} for a simplified power grid structure).
+grid (see Figure~\ref{fig:pg} for a simplified power grid structure).
-Fig.~\ref{fig:flyback_wave}
-and Fig.~\ref{fig:buck_wave}
-shows the waveform at output node of the resonant flyback converter
+Figure~\ref{fig:flyback_wave}
+and Figure~\ref{fig:buck_wave}
+show the waveform at output node of the resonant flyback converter
and the Buck converter.
Note that on the envelope curve, the darker
-dots in separated segments indicate the real simulation points were
+dots in separated segments indicate the real simulation points that were
calculated in those cycles, and the segments without dots are the
envelope jumps where no simulation were done.
It can be verified that the proposed Gear-2 envelope-following method
For the comparison of running time spent in solving
Newton update equation, Table~\ref{table:circuit} lists the time
-costed by direct method, explicit GMRES, matrix-free GMRES,
+cost by direct method, explicit GMRES, matrix-free GMRES,
and GPU matrix-free GMRES. All methods carry out the Gear-2 based
envelope-following method, but they handle the sensitivity and
equation solving in different implementation steps.
It is obvious that as long as the sensitivity matrix is explicitly formed,
-such as the cases in direct method and explicitly GMRES,
+such as in the cases of direct method and explicit GMRES,
the cost is much higher than the implicit methods.
-When matrix-free technique is applied to generate matrix-vector
+When the matrix-free technique is applied to generate matrix-vector
products implicitly, the computation cost is greatly reduced.
Thus, for the same example, implicit GMRES would be one order
of magnitude faster than explicit GMRES. Furthermore, our GPU parallel
use matrix-free GMRES to solve
the Newton update problems with implicit sensitivity calculation,
i.e., the steps enclosed by the double dashed block
-in Fig.~\ref{fig:ef_flow}.
+in Figure~\ref{fig:ef_flow}.
Then implementation issues of GPU acceleration
will be discussed in detail.
Finally, the Gear-2 integration is briefly introduced.
the small size of Hessenberg matrix,
and the frequent inspection of values by host, it is
preferable to allocate $\tilde{H}$ in CPU (host) memory.
-As shown in Fig.~\ref{fig:gmres}, the memory copy from device to host
+As shown in Figure~\ref{fig:gmres}, the memory copy from device to host
is called each time when Arnoldi iteration generates a new vector
and the orthogonalization produces the vector $h$.
which is the power voltage delivered,
not the fast switching waves in every cycle,
that is of interest to the designers.
-As shown in Fig.~\ref{fig:ef1}, the solid line is
+As shown in Figure~\ref{fig:ef1}, the solid line is
the waveform of the output node in a Buck
converter~\cite{Krein:book'97}, the dots are the simulation points
of SPICE\index{SPICE}, and the appended dash line is the envelope.
switching power converters, the waveform of the carrier in
consequent cycles does not change much, envelope-following method
is an approximation analysis method, which skips over several
-cycles (the dash line in Fig.~\ref{fig:ef2}), the so called
+cycles (the dash line in Figure~\ref{fig:ef2}), the so called
envelope step, without simulating them, and then carries out a
correction, which usually contains a sensitivity-based Newton
iteration or shooting until convergence, in order to begin the
@incollection{Odell:2003:RRD:1807559.1807562,
author = {Odell, J. J. and Van Dyke Parunak, H. and Fleischer, M.},
- chapter = {The role of roles in designing effective agent organizations},
- title = {Software engineering for large-scale multi-agent systems},
+ title = {The role of roles in designing effective agent organizations},
+ booktitle = {Software engineering for large-scale multi-agent systems},
editor = {Garcia, Alessandro and Lucena, Carlos and Zambonelli, Franco and Omicini, Andrea and Castro, Jaelson},
year = {2003},
isbn = {3-540-08772-9},
@INPROCEEDINGS{Aaby:2010:ESA:1808143.1808181,
author = {Aaby, B. G. and Perumalla, K. S. and Seal, S. K.},
- title = {Efficient simulation of agent-based models on multi-GPU and multi-core
+ title = {Efficient simulation of agent-based models on multi-{GPU} and multi-core
clusters},
booktitle = {Proceedings of the 3rd International ICST Conference on Simulation
Tools and Techniques},
@ARTICLE{Bleiweiss_2008,
author = {Bleiweiss, A.},
- title = {Multi Agent Navigation on the GPU},
+ title = {Multi Agent Navigation on the {GPU}},
journal = {GDC09 Game Developers Conference},
year = {2099}
}
@ARTICLE{C.Cambier2007,
- author = {C. Cambier, D. Masse, M. Bousso and E. Perrier},
+ author = {C. Cambier and D. Masse and M. Bousso and E. Perrier},
title = {An offer versus demand modelling approach to assess the impact of
micro-organisms spatio-temporal dynamics on soil organic matter decomposition
rates},
}
@ARTICLE{C.Cambier2006,
- author = {C. Cambier, D. Masse, M. Bousso and E. Perrier},
+ author = {C. Cambier and D. Masse and M. Bousso and E. Perrier},
title = {Mior, A spatially explicit, individual based modeling approach to
simulate soil microbial and organic matter processes},
journal = {Ecological Modelling},
@INPROCEEDINGS{Gomez-Luna:2009:PVS:1616772.1616869,
author = {G\'{o}mez-Luna, J. and Gonz\'{a}lez-Linares, J.-M.
and Benavides, J.-I. and Guil, N.},
- title = {Parallelization of a Video Segmentation Algorithm on {CUDAenabled}
+ title = {Parallelization of a Video Segmentation Algorithm on {CUDA-enabled}
Graphics Processing Units},
booktitle = {15th Euro-Par Conference},
year = {2009},
}
@Article{netlogo_home,
author = {Sklar, E.},
-title = {NetLogo, a multi-agent simulation environment},
+title = {{NetLogo}, a multi-agent simulation environment},
journal = {Artificial Life},
year = {2011},
volume = {13},
@INPROCEEDINGS{Guy09clearpath,
author = {S. J. Guy and J. Chhugani and C. Kim and N. Satish and M. C. Lin and D. Manocha and P. Dubey},
- title = {ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation},
+ title = {ClearPath: highly Parallel Collision Avoidance for Multi-Agent Simulation},
booktitle = {ACM Siggraph/Eurographics Symposium on Computer Animation},
year = {2009},
pages = {177--187},
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}
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,
\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
