--- /dev/null
+\contentsline {fm}{List of Figures}{xi}
+\contentsline {fm}{List of Tables}{xvii}
+\contentsline {fm}{Preface}{xxi}
+\contentsline {part}{I\hspace {1em}Presentation of GPUs}{1}
+\author {Rapha\IeC {\"e}l Couturier}{}
+\contentsline {chapter}{\numberline {1}Presentation of the GPU architecture and of the CUDA\hfill \penalty -\@M environment}{3}
+\contentsline {section}{\numberline {1.1}Introduction}{3}
+\contentsline {section}{\numberline {1.2}Brief history of the video card}{4}
+\contentsline {section}{\numberline {1.3}GPGPU}{4}
+\contentsline {section}{\numberline {1.4}Architecture of current GPUs}{5}
+\contentsline {section}{\numberline {1.5}Kinds of parallelism}{7}
+\contentsline {section}{\numberline {1.6}CUDA multithreading}{8}
+\contentsline {section}{\numberline {1.7}Memory hierarchy}{9}
+\contentsline {section}{\numberline {1.8}Conclusion}{11}
+\author {Rapha\IeC {\"e}l Couturier}{}
+\contentsline {chapter}{\numberline {2}Introduction to CUDA}{13}
+\contentsline {section}{\numberline {2.1}Introduction}{13}
+\contentsline {section}{\numberline {2.2}First example}{13}
+\contentsline {section}{\numberline {2.3}Second example: using CUBLAS }{16}
+\contentsline {section}{\numberline {2.4}Third example: matrix-matrix multiplication}{18}
+\contentsline {section}{\numberline {2.5}Conclusion}{21}
+\contentsline {part}{II\hspace {1em}Image processing}{23}
+\author {Gilles Perrot}{}
+\contentsline {chapter}{\numberline {3}Setting up the environment}{25}
+\contentsline {section}{\numberline {3.1}Data transfers, memory management}{25}
+\contentsline {section}{\numberline {3.2}Performance measurements}{28}
+\author {Gilles Perrot}{}
+\contentsline {chapter}{\numberline {4}Implementing a fast median filter}{31}
+\contentsline {section}{\numberline {4.1}Introduction}{31}
+\contentsline {section}{\numberline {4.2}Median filtering}{32}
+\contentsline {subsection}{\numberline {4.2.1}Basic principles}{32}
+\contentsline {subsection}{\numberline {4.2.2}A naive implementation}{33}
+\contentsline {section}{\numberline {4.3}NVIDIA GPU tuning recipes}{35}
+\contentsline {section}{\numberline {4.4}A 3$\times $3 median filter: using registers}{37}
+\contentsline {subsection}{\numberline {4.4.1}The simplest way}{37}
+\contentsline {subsection}{\numberline {4.4.2}Further optimization}{38}
+\contentsline {subsubsection}{\numberline {4.4.2.1}Reducing register count }{39}
+\contentsline {subsubsection}{\numberline {4.4.2.2}More data output per thread}{42}
+\contentsline {section}{\numberline {4.5}A 5$\times $5 and more median filter }{44}
+\contentsline {subsection}{\numberline {4.5.1}A register-only 5$\times $5 median filter }{44}
+\contentsline {subsection}{\numberline {4.5.2}Fast approximated $n\times n$ median filter }{47}
+\author {Gilles Perrot}{}
+\contentsline {chapter}{\numberline {5}Implementing an efficient convolution operation on GPU}{53}
+\contentsline {section}{\numberline {5.1}Overview}{53}
+\contentsline {section}{\numberline {5.2}Definition}{54}
+\contentsline {section}{\numberline {5.3}Implementation}{54}
+\contentsline {subsection}{\numberline {5.3.1}First test implementation}{55}
+\contentsline {subsection}{\numberline {5.3.2}Using parameterizable masks}{58}
+\contentsline {subsection}{\numberline {5.3.3}Increasing the number of pixels processed by each thread}{59}
+\contentsline {subsection}{\numberline {5.3.4}Using shared memory to store prefetched data}{62}
+\contentsline {section}{\numberline {5.4}Separable convolution}{65}
+\contentsline {section}{\numberline {5.5}Conclusion}{69}
+\contentsline {part}{III\hspace {1em}Software development}{71}
+\author {Stefan L. Glimberg, Allan P. Engsig-Karup, Allan S. Nielsen, and Bernd Dammann}{}
+\contentsline {chapter}{\numberline {6}Development of software components for heterogeneous many-core architectures}{73}
+\contentsline {section}{\numberline {6.1}Software development for heterogeneous\hfill \penalty -\@M architectures}{74}
+\contentsline {subsection}{\numberline {6.1.1}Test environments}{76}
+\contentsline {section}{\numberline {6.2}Heterogeneous library design for PDE solvers}{76}
+\contentsline {subsection}{\numberline {6.2.1}Component and concept design}{77}
+\contentsline {subsection}{\numberline {6.2.2}A matrix-free finite difference component}{77}
+\contentsline {section}{\numberline {6.3}Model problems}{81}
+\contentsline {subsection}{\numberline {6.3.1}Heat conduction equation}{82}
+\contentsline {subsubsection}{\numberline {6.3.1.1}Assembling the heat conduction solver}{84}
+\contentsline {subsubsection}{\numberline {6.3.1.2}Numerical solutions to the heat conduction problem}{86}
+\contentsline {subsection}{\numberline {6.3.2}Poisson equation}{87}
+\contentsline {subsubsection}{\numberline {6.3.2.1}Assembling the Poisson solver}{89}
+\contentsline {subsubsection}{\numberline {6.3.2.2}Numerical solutions to the Poisson problem}{91}
+\contentsline {section}{\numberline {6.4}Optimization strategies for multi-GPU systems}{91}
+\contentsline {subsection}{\numberline {6.4.1}Spatial domain decomposition}{93}
+\contentsline {subsection}{\numberline {6.4.2}Parareal--parallel time integration}{95}
+\contentsline {subsubsection}{\numberline {6.4.2.1}The parareal algorithm}{96}
+\contentsline {subsubsection}{\numberline {6.4.2.2}Computational complexity}{98}
+\contentsline {section}{\numberline {6.5}Conclusion and outlook}{100}
+\author {Sylvain Contassot-Vivier}{}
+\author {Stephane Vialle}{}
+\author {Jens Gustedt}{}
+\contentsline {chapter}{\numberline {7}Development methodologies for GPU and cluster of GPUs}{105}
+\contentsline {section}{\numberline {7.1}Introduction}{106}
+\contentsline {section}{\numberline {7.2}General scheme of synchronous code with computation/communication overlapping in GPU clusters}{106}
+\contentsline {subsection}{\numberline {7.2.1}Synchronous parallel algorithms on GPU clusters}{106}
+\contentsline {subsection}{\numberline {7.2.2}Native overlap of CPU communications and GPU computations}{108}
+\contentsline {subsection}{\numberline {7.2.3}Overlapping with sequences of transfers and computations}{110}
+\contentsline {subsection}{\numberline {7.2.4}Interleaved communications-transfers-computations overlapping}{115}
+\contentsline {subsection}{\numberline {7.2.5}Experimental validation}{118}
+\contentsline {section}{\numberline {7.3}General scheme of asynchronous parallel code with computation/communication overlapping}{120}
+\contentsline {subsection}{\numberline {7.3.1}A basic asynchronous scheme}{122}
+\contentsline {subsection}{\numberline {7.3.2}Synchronization of the asynchronous scheme}{126}
+\contentsline {subsection}{\numberline {7.3.3}Asynchronous scheme using MPI, OpenMP, and CUDA}{130}
+\contentsline {subsection}{\numberline {7.3.4}Experimental validation}{137}
+\contentsline {section}{\numberline {7.4}Perspective: a unifying programming model}{140}
+\contentsline {subsection}{\numberline {7.4.1}Resources}{141}
+\contentsline {subsection}{\numberline {7.4.2}Control}{142}
+\contentsline {subsection}{\numberline {7.4.3}Example: block-cyclic matrix multiplication (MM)}{142}
+\contentsline {subsection}{\numberline {7.4.4}Tasks and operations}{145}
+\contentsline {section}{\numberline {7.5}Conclusion}{146}
+\contentsline {section}{\numberline {7.6}Glossary}{146}
+\contentsline {part}{IV\hspace {1em}Optimization}{151}
+\author {Imen Chakroun and Nouredine Melab}{}
+\contentsline {chapter}{\numberline {8}GPU-accelerated tree-based exact optimization methods}{153}
+\contentsline {section}{\numberline {8.1}Introduction}{154}
+\contentsline {section}{\numberline {8.2}Branch-and-bound algorithm}{156}
+\contentsline {section}{\numberline {8.3}Parallel branch-and-bound algorithms}{157}
+\contentsline {subsection}{\numberline {8.3.1}The parallel tree exploration model}{158}
+\contentsline {subsection}{\numberline {8.3.2}The parallel evaluation of bounds model}{158}
+\contentsline {section}{\numberline {8.4}The flowshop scheduling problem}{159}
+\contentsline {subsection}{\numberline {8.4.1}Definition of the flowshop scheduling problem}{159}
+\contentsline {subsection}{\numberline {8.4.2}Lower bound for the flowshop scheduling problem}{160}
+\contentsline {section}{\numberline {8.5}GPU-accelerated B\&B based on the parallel tree exploration (GPU-PTE-BB)}{161}
+\contentsline {section}{\numberline {8.6}GPU-accelerated B\&B based on the parallel evaluation of bounds (GPU-PEB-BB) }{162}
+\contentsline {section}{\numberline {8.7}Thread divergence}{164}
+\contentsline {subsection}{\numberline {8.7.1}The thread divergence issue}{164}
+\contentsline {subsection}{\numberline {8.7.2}Mechanisms for reducing branch divergence}{165}
+\contentsline {section}{\numberline {8.8}Memory access optimization}{168}
+\contentsline {subsection}{\numberline {8.8.1}Complexity analysis of the memory usage of the lower bound }{169}
+\contentsline {subsection}{\numberline {8.8.2}Data placement pattern of the lower bound on GPU}{170}
+\contentsline {section}{\numberline {8.9}Experiments}{172}
+\contentsline {subsection}{\numberline {8.9.1}Parameters settings}{172}
+\contentsline {subsection}{\numberline {8.9.2}Experimental protocol: computing the speedup}{172}
+\contentsline {subsection}{\numberline {8.9.3}Performance impact of GPU-based parallelism}{174}
+\contentsline {subsection}{\numberline {8.9.4}Thread divergence reduction}{176}
+\contentsline {subsection}{\numberline {8.9.5}Data access optimization}{176}
+\contentsline {section}{\numberline {8.10}Conclusion and future work}{178}
+\author {Malika Mehdi}{}
+\author {Ahc\`{e}ne Bendjoudi}{}
+\author {Lakhdar Loukil}{}
+\author {Nouredine Melab}{}
+\contentsline {chapter}{\numberline {9}Parallel GPU-accelerated metaheuristics}{183}
+\contentsline {section}{\numberline {9.1}Introduction}{184}
+\contentsline {section}{\numberline {9.2}Combinatorial optimization}{184}
+\contentsline {section}{\numberline {9.3}Parallel models for metaheuristics}{185}
+\contentsline {section}{\numberline {9.4}Challenges for the design of GPU-based metaheuristics}{187}
+\contentsline {subsection}{\numberline {9.4.1}Data placement on a hierarchical memory}{188}
+\contentsline {subsection}{\numberline {9.4.2}Threads synchronization}{189}
+\contentsline {subsection}{\numberline {9.4.3}Thread divergence}{189}
+\contentsline {subsection}{\numberline {9.4.4}Task distribution and CPU/GPU communication}{190}
+\contentsline {section}{\numberline {9.5}State-of-the-art parallel metaheuristics on GPUs}{190}
+\contentsline {subsection}{\numberline {9.5.1}Implementing solution-based metaheuristics on GPUs}{191}
+\contentsline {subsection}{\numberline {9.5.2}Implementing population-based metaheuristics on GPUs}{193}
+\contentsline {subsection}{\numberline {9.5.3}Synthesis of the implementation strategies}{198}
+\contentsline {section}{\numberline {9.6}Frameworks for metaheuristics on GPUs}{201}
+\contentsline {subsection}{\numberline {9.6.1}PUGACE: framework for implementing evolutionary computation on GPUs}{201}
+\contentsline {subsection}{\numberline {9.6.2}ParadisEO-MO-GPU}{202}
+\contentsline {subsection}{\numberline {9.6.3}libCUDAOptimize: an open source library of GPU-based metaheuristics}{202}
+\contentsline {section}{\numberline {9.7}Case study: accelerating large neighborhood LS method on GPUs for solving the Q3AP}{203}
+\contentsline {subsection}{\numberline {9.7.1}The quadratic 3-dimensional assignment problem}{204}
+\contentsline {subsection}{\numberline {9.7.2}Iterated tabu search algorithm for the Q3AP}{205}
+\contentsline {subsection}{\numberline {9.7.3}Neighborhood functions for the Q3AP}{206}
+\contentsline {subsection}{\numberline {9.7.4}Design and implementation of a GPU-based iterated tabu search algorithm for the Q3AP}{207}
+\contentsline {subsection}{\numberline {9.7.5}Experimental results}{208}
+\contentsline {section}{\numberline {9.8}Conclusion}{210}
+\author {Xavier Meyer}{}
+\author {Bastien Chopard}{}
+\author {Paul Albuquerque}{}
+\contentsline {chapter}{\numberline {10}Linear programming on a GPU: a\nobreakspace {}case\nobreakspace {}study}{215}
+\contentsline {section}{\numberline {10.1}Introduction}{216}
+\contentsline {section}{\numberline {10.2}Simplex algorithm}{217}
+\contentsline {subsection}{\numberline {10.2.1}Linear programming model}{217}
+\contentsline {subsection}{\numberline {10.2.2}Standard simplex algorithm}{217}
+\contentsline {subsection}{\numberline {10.2.3}Revised simplex method}{219}
+\contentsline {subsection}{\numberline {10.2.4}Heuristics and improvements}{221}
+\contentsline {section}{\numberline {10.3}Branch-and-bound algorithm}{224}
+\contentsline {subsection}{\numberline {10.3.1}Integer linear programming}{224}
+\contentsline {subsection}{\numberline {10.3.2}Branch-and-bound tree}{224}
+\contentsline {subsection}{\numberline {10.3.3}Branching strategy}{225}
+\contentsline {subsection}{\numberline {10.3.4}Node selection strategy}{226}
+\contentsline {subsection}{\numberline {10.3.5}Cutting-plane methods}{227}
+\contentsline {section}{\numberline {10.4}CUDA considerations}{228}
+\contentsline {subsection}{\numberline {10.4.1}Parallel reduction}{228}
+\contentsline {subsection}{\numberline {10.4.2}Kernel optimization}{228}
+\contentsline {section}{\numberline {10.5}Implementations}{229}
+\contentsline {subsection}{\numberline {10.5.1}Standard simplex}{229}
+\contentsline {subsection}{\numberline {10.5.2}Revised simplex}{232}
+\contentsline {subsection}{\numberline {10.5.3}Branch-and-bound}{236}
+\contentsline {section}{\numberline {10.6}Performance model}{237}
+\contentsline {subsection}{\numberline {10.6.1}Levels of parallelism}{238}
+\contentsline {subsection}{\numberline {10.6.2}Amount of work done by a thread}{238}
+\contentsline {subsection}{\numberline {10.6.3}Global performance model}{239}
+\contentsline {subsection}{\numberline {10.6.4}A kernel example: \textit {steepest-edge}}{239}
+\contentsline {subsection}{\numberline {10.6.5}Standard simplex GPU implementation model}{240}
+\contentsline {section}{\numberline {10.7}Measurements and analysis}{241}
+\contentsline {subsection}{\numberline {10.7.1}Performance model validation}{241}
+\contentsline {subsection}{\numberline {10.7.2}Performance comparison of implementations}{241}
+\contentsline {section}{\numberline {10.8}Conclusion and perspectives}{245}
+\contentsline {part}{V\hspace {1em}Numerical applications}{249}
+\author {Allan P. Engsig-Karup, Stefan L. Glimberg, Allan S. Nielsen, and Ole Lindberg}{}
+\contentsline {chapter}{\numberline {11}Fast hydrodynamics on heterogeneous many-core hardware}{251}
+\contentsline {section}{\numberline {11.1}On hardware trends and challenges in scientific applications}{253}
+\contentsline {section}{\numberline {11.2}On modeling paradigms for highly nonlinear and dispersive water waves}{255}
+\contentsline {section}{\numberline {11.3}Governing equations}{256}
+\contentsline {subsection}{\numberline {11.3.1}Boundary conditions}{260}
+\contentsline {section}{\numberline {11.4}The numerical model}{260}
+\contentsline {subsection}{\numberline {11.4.1}Strategies for efficient solution of the Laplace problem}{261}
+\contentsline {subsection}{\numberline {11.4.2}Finite difference approximations}{262}
+\contentsline {subsection}{\numberline {11.4.3}Time integration}{263}
+\contentsline {subsection}{\numberline {11.4.4}Wave generation and absorption}{266}
+\contentsline {subsection}{\numberline {11.4.5}Preconditioned Defect Correction (PDC) method}{267}
+\contentsline {subsection}{\numberline {11.4.6}Distributed computations via domain decomposition}{269}
+\contentsline {subsection}{\numberline {11.4.7}Assembling the wave model from library components}{271}
+\contentsline {section}{\numberline {11.5}Properties of the numerical model}{276}
+\contentsline {subsection}{\numberline {11.5.1}Dispersion and kinematic properties}{276}
+\contentsline {section}{\numberline {11.6}Numerical experiments}{277}
+\contentsline {subsection}{\numberline {11.6.1}On precision requirements in engineering applications}{277}
+\contentsline {subsection}{\numberline {11.6.2}Acceleration via parallelism in time using parareal}{282}
+\contentsline {subsection}{\numberline {11.6.3}Towards real-time interactive ship simulation}{286}
+\contentsline {section}{\numberline {11.7}Conclusion and future work}{288}
+\contentsline {section}{\numberline {11.8}Acknowledgments}{289}
+\author {Gleb Beliakov and Shaowu Liu}{}
+\contentsline {chapter}{\numberline {12}Parallel monotone spline interpolation and approximation on GPUs}{295}
+\contentsline {section}{\numberline {12.1}Introduction}{295}
+\contentsline {section}{\numberline {12.2}Monotone splines}{298}
+\contentsline {subsection}{\numberline {12.2.1}Monotone quadratic splines}{298}
+\contentsline {subsection}{\numberline {12.2.2}Monotone Hermite splines}{302}
+\contentsline {section}{\numberline {12.3}Smoothing noisy data via parallel isotone regression}{303}
+\contentsline {section}{\numberline {12.4}Conclusion}{308}
+\author {Lilia Ziane Khodja, Rapha\IeC {\"e}l Couturier, and Jacques Bahi}{}
+\contentsline {chapter}{\numberline {13}Solving sparse linear systems with GMRES and CG methods on GPU clusters}{311}
+\contentsline {section}{\numberline {13.1}Introduction}{311}
+\contentsline {section}{\numberline {13.2}Krylov iterative methods}{312}
+\contentsline {subsection}{\numberline {13.2.1}CG method}{313}
+\contentsline {subsection}{\numberline {13.2.2}GMRES method}{314}
+\contentsline {section}{\numberline {13.3}Parallel implementation on a GPU cluster}{317}
+\contentsline {subsection}{\numberline {13.3.1}Data partitioning}{317}
+\contentsline {subsection}{\numberline {13.3.2}GPU computing}{317}
+\contentsline {subsection}{\numberline {13.3.3}Data communications}{319}
+\contentsline {section}{\numberline {13.4}Experimental results}{321}
+\contentsline {section}{\numberline {13.5}Conclusion}{327}
+\author {Lilia Ziane Khodja, Rapha\IeC {\"e}l Couturier, Jacques Bahi}{}
+\author {Ming Chau}{}
+\author {Pierre Spit\IeC {\'e}ri}{}
+\contentsline {chapter}{\numberline {14}Solving sparse nonlinear systems of obstacle problems on GPU clusters}{331}
+\contentsline {section}{\numberline {14.1}Introduction}{331}
+\contentsline {section}{\numberline {14.2}Obstacle problems}{332}
+\contentsline {subsection}{\numberline {14.2.1}Mathematical model}{332}
+\contentsline {subsection}{\numberline {14.2.2}Discretization}{333}
+\contentsline {section}{\numberline {14.3}Parallel iterative method}{334}
+\contentsline {section}{\numberline {14.4}Parallel implementation on a GPU cluster}{337}
+\contentsline {section}{\numberline {14.5}Experimental tests on a GPU cluster}{345}
+\contentsline {section}{\numberline {14.6}Red-black ordering technique}{348}
+\contentsline {section}{\numberline {14.7}Conclusion}{352}
+\author {Alan Gray and Kevin Stratford}{}
+\contentsline {chapter}{\numberline {15}Ludwig: multiple GPUs for a complex fluid lattice Boltzmann
+application}{355}
+\contentsline {section}{\numberline {15.1}Introduction}{355}
+\contentsline {section}{\numberline {15.2}Background}{357}
+\contentsline {section}{\numberline {15.3}Single GPU implementation}{360}
+\contentsline {section}{\numberline {15.4}Multiple GPU implementation}{361}
+\contentsline {section}{\numberline {15.5}Moving solid particles}{364}
+\contentsline {section}{\numberline {15.6}Summary}{367}
+\contentsline {section}{\numberline {15.7}Acknowledgments}{367}
+\author {Rachid Habel}{}
+\author {Pierre Fortin, Fabienne J\'ez\'equel, Jean-Luc Lamotte}{}
+\author {Stan Scott}{}
+\contentsline {chapter}{\numberline {16}Numerical validation and performance optimization on GPUs of an application in atomic physics}{371}
+\contentsline {section}{\numberline {16.1}Introduction}{372}
+\contentsline {section}{\numberline {16.2}2DRMP and the PROP program}{373}
+\contentsline {subsection}{\numberline {16.2.1}Principles of $R$-matrix propagation}{373}
+\contentsline {subsection}{\numberline {16.2.2}Description of the PROP program}{375}
+\contentsline {subsection}{\numberline {16.2.3}CAPS implementation}{376}
+\contentsline {section}{\numberline {16.3}Numerical validation of PROP in single precision}{377}
+\contentsline {subsection}{\numberline {16.3.1}Medium case study}{378}
+\contentsline {subsection}{\numberline {16.3.2}Huge case study}{380}
+\contentsline {section}{\numberline {16.4}Towards a complete deployment of PROP on GPUs}{381}
+\contentsline {subsection}{\numberline {16.4.1}Computing the output $R$-matrix on GPU}{382}
+\contentsline {subsection}{\numberline {16.4.2}Constructing the local $R$-matrices on GPU}{384}
+\contentsline {subsection}{\numberline {16.4.3}Scaling amplitude arrays on GPU}{385}
+\contentsline {subsection}{\numberline {16.4.4}Using double-buffering to overlap I/O and computation}{385}
+\contentsline {subsection}{\numberline {16.4.5}Matrix padding}{386}
+\contentsline {section}{\numberline {16.5}Performance results}{387}
+\contentsline {subsection}{\numberline {16.5.1}PROP deployment on GPU}{387}
+\contentsline {subsection}{\numberline {16.5.2}PROP execution profile}{389}
+\contentsline {section}{\numberline {16.6}Propagation of multiple concurrent energies on GPU}{391}
+\contentsline {section}{\numberline {16.7}Conclusion and future work}{392}
+\author {Xuexin Liu, Sheldon Xiang-Dong Tan}{}
+\author {Hai Wang}{}
+\author {Hao Yu}{}
+\contentsline {chapter}{\numberline {17}A GPU-accelerated envelope-following method for switching power converter simulation}{395}
+\contentsline {section}{\numberline {17.1}Introduction}{395}
+\contentsline {section}{\numberline {17.2}The envelope-following method in a nutshell}{398}
+\contentsline {section}{\numberline {17.3}New parallel envelope-following method}{400}
+\contentsline {subsection}{\numberline {17.3.1}GMRES solver for Newton update equation}{400}
+\contentsline {subsection}{\numberline {17.3.2}Parallelization on GPU platforms}{402}
+\contentsline {subsection}{\numberline {17.3.3}Gear-2 based sensitivity calculation}{404}
+\contentsline {section}{\numberline {17.4}Numerical examples}{406}
+\contentsline {section}{\numberline {17.5}Summary}{410}
+\contentsline {section}{\numberline {17.6}Glossary}{410}
+\contentsline {part}{VI\hspace {1em}Other}{413}
+\author {Guillaume Laville, Christophe Lang, B\IeC {\'e}n\IeC {\'e}dicte Herrmann, Laurent Philippe}{}
+\author {Kamel Mazouzi}{}
+\author {Nicolas Marilleau}{}
+\contentsline {chapter}{\numberline {18}Implementing multi-agent systems on GPU}{415}
+\contentsline {section}{\numberline {18.1}Introduction}{416}
+\contentsline {section}{\numberline {18.2}Running agent-based simulations}{417}
+\contentsline {subsection}{\numberline {18.2.1}Multi-agent systems and parallelism}{417}
+\contentsline {subsection}{\numberline {18.2.2}MAS implementation on GPU}{418}
+\contentsline {section}{\numberline {18.3}A first practical example}{420}
+\contentsline {subsection}{\numberline {18.3.1}The Collembola model}{420}
+\contentsline {subsection}{\numberline {18.3.2}Collembola implementation}{421}
+\contentsline {subsection}{\numberline {18.3.3}Collembola performance}{423}
+\contentsline {section}{\numberline {18.4}Second example}{424}
+\contentsline {subsection}{\numberline {18.4.1}The MIOR model}{424}
+\contentsline {subsection}{\numberline {18.4.2}MIOR implementation}{425}
+\contentsline {subsubsection}{\numberline {18.4.2.1}Execution mapping on GPU}{426}
+\contentsline {subsubsection}{\numberline {18.4.2.2}Data structures translation}{427}
+\contentsline {subsubsection}{\numberline {18.4.2.3}Critical resources access management}{428}
+\contentsline {subsubsection}{\numberline {18.4.2.4}Termination detection}{430}
+\contentsline {subsection}{\numberline {18.4.3}Performance of MIOR implementations}{430}
+\contentsline {section}{\numberline {18.5}Analysis and recommendations}{434}
+\contentsline {subsection}{\numberline {18.5.1}Analysis}{434}
+\contentsline {subsection}{\numberline {18.5.2}MAS execution workflow}{435}
+\contentsline {subsection}{\numberline {18.5.3}Implementation challenges}{435}
+\contentsline {subsection}{\numberline {18.5.4}MCSMA}{436}
+\contentsline {section}{\numberline {18.6}Conclusion}{437}
+\author {Rapha\IeC {\"e}l Couturier and Christophe Guyeux}{}
+\contentsline {chapter}{\numberline {19}Pseudorandom number generator on GPU}{441}
+\contentsline {section}{\numberline {19.1}Introduction}{441}
+\contentsline {section}{\numberline {19.2}Basic reminders}{443}
+\contentsline {subsection}{\numberline {19.2.1}A short presentation of chaos}{443}
+\contentsline {subsection}{\numberline {19.2.2}On Devaney's definition of chaos}{443}
+\contentsline {subsection}{\numberline {19.2.3}Chaotic iterations}{444}
+\contentsline {section}{\numberline {19.3}Toward efficiency and improvement for CI PRNG}{445}
+\contentsline {subsection}{\numberline {19.3.1}First efficient implementation of a PRNG based on chaotic iterations}{445}
+\contentsline {subsection}{\numberline {19.3.2}Efficient PRNGs based on chaotic iterations on GPU}{446}
+\contentsline {subsection}{\numberline {19.3.3}Naive version for GPU}{446}
+\contentsline {subsection}{\numberline {19.3.4}Improved version for GPU}{447}
+\contentsline {subsection}{\numberline {19.3.5}Chaos evaluation of the improved version}{448}
+\contentsline {section}{\numberline {19.4}Experiments}{449}
+\contentsline {section}{\numberline {19.5}Summary}{450}
+\author {Bertil Schmidt and Hoang-Vu Dang}{}
+\contentsline {chapter}{\numberline {20}Solving large sparse linear systems for integer factorization on GPUs}{453}
+\contentsline {section}{\numberline {20.1}Introduction}{453}
+\contentsline {section}{\numberline {20.2}Block Wiedemann algorithm}{454}
+\contentsline {section}{\numberline {20.3}SpMV over GF(2) for NFS matrices using existing formats on GPUs}{455}
+\contentsline {section}{\numberline {20.4}A hybrid format for SpMV on GPUs}{459}
+\contentsline {subsection}{\numberline {20.4.1}Dense format}{459}
+\contentsline {subsection}{\numberline {20.4.2}Sliced COO}{460}
+\contentsline {subsection}{\numberline {20.4.3}Determining the cut-off point of each format}{464}
+\contentsline {section}{\numberline {20.5}SCOO for single-precision floating-point matrices}{465}
+\contentsline {section}{\numberline {20.6}Performance evaluation}{466}
+\contentsline {subsection}{\numberline {20.6.1}Experimental setup}{466}
+\contentsline {subsection}{\numberline {20.6.2}Experimental results of SpMV on NFS matrix}{466}
+\contentsline {subsection}{\numberline {20.6.3}Experimental results of SpMV on floating-point matrices}{467}
+\contentsline {subsubsection}{\numberline {20.6.3.1}Performance comparison to existing GPU formats}{467}
+\contentsline {subsubsection}{\numberline {20.6.3.2}Performance comparison to a CPU implementation}{469}
+\contentsline {section}{\numberline {20.7}Conclusion}{470}
+\contentsline {chapter}{Index}{473}
--- /dev/null
+\begin{thebibliography}{10}
+
+\bibitem{CUDA_Zone}
+{CUDA} community showcase.
+\newblock \url{http://www.nvidia.com/}.
+
+\bibitem{ngspice}
+{NGSPICE}.
+\newblock \url{http://ngspice.sourceforge.net/}.
+
+\bibitem{AMDMC'06}
+{AMD Inc.}
+\newblock Multi-core processors---the next evolution in computing ({W}hite
+ {P}aper), 2006.
+\newblock \url{http://multicore.amd.com}.
+
+\bibitem{streamSDK}
+{AMD Inc.}
+\newblock {AMD} {S}team {SDK}.
+\newblock \url{http://developer.amd.com/gpu/ATIStreamSDK}, 2011.
+
+\bibitem{Feldmann:ICCAD'96}
+P.~Feldmann and J.~Roychowdhury.
+\newblock Computation of circuit waveform envelopes using an efficient,
+ matrix-decomposed harmonic balance algorithm.
+\newblock In {\em Proc. ICCAD}, pages 295--300, Nov. 1996.
+
+\bibitem{Gear:book'71}
+C.~W. Gear.
+\newblock {\em Numerical Initial Value Problems in Ordinary Differential
+ Equations}.
+\newblock Prentice-Hall, Englewood Cliffs, NJ, 1971.
+
+\bibitem{gpgpu}
+D.~G\"{o}ddeke.
+\newblock General-purpose computation using graphics hardware.
+\newblock \url{http://www.gpgpu.org/}, 2011.
+
+\bibitem{Golub:Book'96}
+G.~H. Golub and C.~Van Loan.
+\newblock {\em Matrix Computations}.
+\newblock The Johns Hopkins University Press, 3rd edition, 1996.
+
+\bibitem{IntelMC'06}
+{Intel Corporation}.
+\newblock Intel multi-core processors, making the move to quad-core and beyond
+ ({W}hite {P}aper), 2006.
+\newblock \url{http://www.intel.com/multi-core}.
+
+\bibitem{Kato:COMPEL'06}
+T.~Kato et~al.
+\newblock Envelope following analysis of an autonomous power electronic system.
+\newblock In {\em IEEE COMPEL'06}, pages 29--33, July 2006.
+
+\bibitem{openCL}
+{Khronos Group}.
+\newblock Open {C}omputing {L}anguage ({O}pen{CL}).
+\newblock \url{http://www.khronos.org/opencl}, 2011.
+
+\bibitem{Kirk:Book'10}
+D.~B. Kirk and W.-M. Hwu.
+\newblock {\em Programming Massively Parallel Processors: A Hands-on Approach}.
+\newblock Morgan Kaufmann Publishers Inc., San Francisco, CA, 2010.
+
+\bibitem{Krein:book'97}
+P.~Krein.
+\newblock {\em Elements of Power Electronics}.
+\newblock Oxford University Press, 1997.
+
+\bibitem{Kundert:ICCAD'88}
+K.~Kundert, J.~White, and A.~Sangiovanni-Vincentelli.
+\newblock An envelope following method for the efficient transient simulation
+ of switching power and filter circuits.
+\newblock In {\em Proc. ICCAD}, pages 446--449, Oct. 1988.
+
+\bibitem{LiuTan1:DATE'12}
+X.-X. Liu, S.~X.-D. Tan, H.~Wang, and H.~Yu.
+\newblock A {GPU}-accelerated envelope-following method for switching power
+ converter simulation.
+\newblock pages 1349--1354, March 2012.
+
+\bibitem{CUDASDK}
+{NVIDIA}, 2011.
+\newblock \url{http://developer.nvidia.com/cuda-toolkit-40}.
+
+\bibitem{nvidia}
+{NVIDIA Corporation}, 2011.
+\newblock {h}ttp://www.nvidia.com.
+
+\bibitem{cuda}
+{{NVIDIA} Corporation}.
+\newblock {CUDA} ({C}ompute {U}nified {D}evice {A}rchitecture), 2011.
+\newblock \url{http://www.nvidia.com/object/cuda_home.html}.
+
+\bibitem{Telichevesky:DAC'95}
+R.~Telichevesky, K.~Kundert, and J.~White.
+\newblock Efficient steady-state analysis based on matrix-free
+ {K}rylov-subspace methods.
+\newblock pages 480--484, 1995.
+
+\bibitem{Trzynadlowski:Book'10}
+A.~M. Trzynadlowski.
+\newblock {\em Introduction to Modern Power Electronics},
+\newblock second edition, Wiley, 2010.
+
+\bibitem{Vlach:Book'94}
+J.~Vlach and K.~Singhal.
+\newblock {\em Computer Methods for Circuit Analysis and Design}.
+\newblock Van Nostrand Reinhold, New York, NY, 1995.
+
+\bibitem{White:TPE'91}
+J.~White and S.~Leeb.
+\newblock An envelope-following approach to switching power converter
+ simulation.
+\newblock {\em IEEE Trans. Power Electron.}, 6(2):303--307, Apr. 1991.
+
+\end{thebibliography}
