From: couturie Date: Sun, 22 Sep 2013 08:52:16 +0000 (+0200) Subject: ch17 X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/commitdiff_plain/cf0ee588a0ef05623f955938e81be1aa96c33f46?ds=inline ch17 --- diff --git a/BookGPU/Chapters/chapter14/biblio14.bib b/BookGPU/Chapters/chapter14/biblio14.bib index 8ad0aaa..0dab7ef 100644 --- a/BookGPU/Chapters/chapter14/biblio14.bib +++ b/BookGPU/Chapters/chapter14/biblio14.bib @@ -1,7 +1,7 @@ @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}, } diff --git a/BookGPU/Chapters/chapter14/ch14.tex b/BookGPU/Chapters/chapter14/ch14.tex index e5c2daa..65177f4 100755 --- a/BookGPU/Chapters/chapter14/ch14.tex +++ b/BookGPU/Chapters/chapter14/ch14.tex @@ -252,7 +252,7 @@ For the D3Q19 model, this reduces the volume of data traffic from 19 to 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} @@ -773,7 +773,7 @@ keep the entire problem resident on the device. - +\clearpage \section{Summary} \label{ch14:sec:summary} @@ -967,6 +967,7 @@ by UK EPSRC under grant EV/J007404/1. % 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} diff --git a/BookGPU/Chapters/chapter16/biblio16.bib b/BookGPU/Chapters/chapter16/biblio16.bib index 1252282..f9fe2c1 100644 --- a/BookGPU/Chapters/chapter16/biblio16.bib +++ b/BookGPU/Chapters/chapter16/biblio16.bib @@ -2,8 +2,8 @@ @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" } @@ -86,7 +86,7 @@ @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 } @@ -163,7 +163,7 @@ @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}, diff --git a/BookGPU/Chapters/chapter16/ch16.tex b/BookGPU/Chapters/chapter16/ch16.tex index e7ba3ba..ac52b32 100644 --- a/BookGPU/Chapters/chapter16/ch16.tex +++ b/BookGPU/Chapters/chapter16/ch16.tex @@ -52,21 +52,22 @@ \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. @@ -74,7 +75,7 @@ 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} diff --git a/BookGPU/Chapters/chapter16/ef.tex b/BookGPU/Chapters/chapter16/ef.tex index 1cc747b..812c97a 100644 --- a/BookGPU/Chapters/chapter16/ef.tex +++ b/BookGPU/Chapters/chapter16/ef.tex @@ -133,7 +133,7 @@ In summary, the envelope-following method is fundamentally 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}} diff --git a/BookGPU/Chapters/chapter16/exp.tex b/BookGPU/Chapters/chapter16/exp.tex index 6fd3eb9..8e5894d 100644 --- a/BookGPU/Chapters/chapter16/exp.tex +++ b/BookGPU/Chapters/chapter16/exp.tex @@ -64,19 +64,19 @@ marked.} 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 @@ -106,14 +106,14 @@ Boost-2 & 1093 & 729.5 & 720.8 & 71.0 & 8.5 & 9.9$\times$ \\ 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 diff --git a/BookGPU/Chapters/chapter16/gpu.tex b/BookGPU/Chapters/chapter16/gpu.tex index 623ac81..bdd4ad0 100644 --- a/BookGPU/Chapters/chapter16/gpu.tex +++ b/BookGPU/Chapters/chapter16/gpu.tex @@ -5,7 +5,7 @@ In this section, we explain how to efficiently 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. @@ -225,7 +225,7 @@ Hence, in consideration of the serial nature of the trianularization, 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$. diff --git a/BookGPU/Chapters/chapter16/intro.tex b/BookGPU/Chapters/chapter16/intro.tex index dda1808..4cbc91f 100644 --- a/BookGPU/Chapters/chapter16/intro.tex +++ b/BookGPU/Chapters/chapter16/intro.tex @@ -42,7 +42,7 @@ In those switching power converters, it is the envelope, 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. @@ -54,7 +54,7 @@ clock cycle to get the accurate details of the carrier. For 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 diff --git a/BookGPU/Chapters/chapter17/biblio.bib b/BookGPU/Chapters/chapter17/biblio.bib index 52aa327..65926f7 100644 --- a/BookGPU/Chapters/chapter17/biblio.bib +++ b/BookGPU/Chapters/chapter17/biblio.bib @@ -3,8 +3,8 @@ @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}, @@ -18,7 +18,7 @@ @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}, @@ -119,13 +119,13 @@ @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}, @@ -137,7 +137,7 @@ } @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}, @@ -198,7 +198,7 @@ @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}, @@ -502,7 +502,7 @@ pages = {517-527} } @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}, @@ -522,7 +522,7 @@ address = {Heidelberg, FRG} @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}, diff --git a/BookGPU/Chapters/chapter17/ch17.tex b/BookGPU/Chapters/chapter17/ch17.tex index 93204ce..6cab2e3 100755 --- a/BookGPU/Chapters/chapter17/ch17.tex +++ b/BookGPU/Chapters/chapter17/ch17.tex @@ -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} @@ -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, @@ -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