X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/a6692cd736d836866212aae44ca8d787b63b1d01..3a4d92d48d8e34ab9e636f7eb092235bcfa0215d:/prng_gpu.tex diff --git a/prng_gpu.tex b/prng_gpu.tex index 2a27439..41e628a 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -34,7 +34,7 @@ \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}} -\title{Efficient Generation of Pseudo-Random Bumbers based on Chaotic Iterations +\title{Efficient Generation of Pseudo-Random Numbers based on Chaotic Iterations on GPU} \begin{document} @@ -44,17 +44,63 @@ Guyeux\thanks{Authors in alphabetic order}} \maketitle \begin{abstract} -This is the abstract + \end{abstract} \section{Introduction} +Random numbers are used in many scientific applications and simulations. On +finite state machines, as computers, it is not possible to generate random +numbers but only pseudo-random numbers. In practice, a good pseudo-random number +generator (PRNG) needs to verify some features to be used by scientists. It is +important to be able to generate pseudo-random numbers efficiently, the +generation needs to be reproducible and a PRNG needs to satisfy many usual +statistical properties. Finally, from our point a view, it is essential to prove +that a PRNG is chaotic. Concerning the statistical tests, TestU01 is the +best-known public-domain statistical testing package. So we use it for all our +PRNGs, especially the {\it BigCrush} which provides the largest serie of tests. +Concerning the chaotic properties, Devaney~\cite{Devaney} proposed a common +mathematical formulation of chaotic dynamical systems. + +In a previous work~\cite{bgw09:ip} we have proposed a new familly of chaotic +PRNG based on chaotic iterations (IC). We have proven that these PRNGs are +chaotic in the Devaney's sense. In this paper we propose a faster version which +is also proven to be chaotic. + +Although graphics processing units (GPU) was initially designed to accelerate +the manipulation of images, they are nowadays commonly used in many scientific +applications. Therefore, it is important to be able to generate pseudo-random +numbers inside a GPU when a scientific application runs in a GPU. That is why we +also provide an efficient PRNG for GPU respecting based on IC. + + + + Interet des itérations chaotiques pour générer des nombre alea\\ Interet de générer des nombres alea sur GPU -\alert{RC, un petit state-of-the-art sur les PRNGs sur GPU ?} -... +\section{Related works on GPU based PRNGs} + +In the litterature many authors have work on defining GPU based PRNGs. We do not +want to be exhaustive and we just give the most significant works from our point +of view. + +In \cite{Pang:2008:cec}, the authors define a PRNG based on cellular automata +which does not require high precision integer arithmetics nor bitwise +operations. There is no mention of statistical tests nor proof that this PRNG is +chaotic. Concerning the speed of generation, they can generate about 3200000 +random numbers per seconds on a GeForce 7800 GTX GPU (which is quite old now). + +In \cite{ZRKB10}, the authors propose different versions of efficient GPU PRNGs +based on Lagged Fibonacci, Hybrid Taus or Hybrid Taus. They have used these +PRNGs for Langevin simulations of biomolecules fully implemented on +GPU. Performance of the GPU versions are far better than those obtained with a +CPU and these PRNGs succeed to pass the {\it BigCrush} test of TestU01. There is +no mention that their PRNGs have chaos mathematical properties. + +To the best of our knowledge no GPU implementation have been proven to have chaotic properties. + \section{Basic Recalls} \label{section:BASIC RECALLS} This section is devoted to basic definitions and terminologies in the fields of @@ -410,7 +456,7 @@ use of more general chaotic iterations to generate pseudo-random numbers faster, does not deflate their topological chaos properties. \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations} - +\label{deuxième def} Let us consider the discrete dynamical systems in chaotic iterations having the general form: @@ -725,17 +771,16 @@ unsigned int CIprng() { In listing~\ref{algo:seqCIprng} a sequential version of our chaotic iterations -based PRNG is presented. The xor operator is represented by -\textasciicircum. This function uses three classical 64-bits PRNG: the -\texttt{xorshift}, the \texttt{xor128} and the \texttt{xorwow}. In the -following, we call them xor-like PRNGSs. These three PRNGs are presented -in~\cite{Marsaglia2003}. As each xor-like PRNG used works with 64-bits and as -our PRNG works with 32-bits, the use of \texttt{(unsigned int)} selects the 32 -least significant bits whereas \texttt{(unsigned int)(t3$>>$32)} selects the 32 -most significants bits of the variable \texttt{t}. So to produce a random -number realizes 6 xor operations with 6 32-bits numbers produced by 3 64-bits -PRNG. This version successes the BigCrush of the TestU01 battery [P. L’ecuyer - and R. Simard. Testu01]. +based PRNG is presented. The xor operator is represented by \textasciicircum. +This function uses three classical 64-bits PRNG: the \texttt{xorshift}, the +\texttt{xor128} and the \texttt{xorwow}. In the following, we call them +xor-like PRNGSs. These three PRNGs are presented in~\cite{Marsaglia2003}. As +each xor-like PRNG used works with 64-bits and as our PRNG works with 32-bits, +the use of \texttt{(unsigned int)} selects the 32 least significant bits whereas +\texttt{(unsigned int)(t3$>>$32)} selects the 32 most significants bits of the +variable \texttt{t}. So to produce a random number realizes 6 xor operations +with 6 32-bits numbers produced by 3 64-bits PRNG. This version successes the +BigCrush of the TestU01 battery~\cite{LEcuyerS07}. \section{Efficient prng based on chaotic iterations on GPU} @@ -881,7 +926,7 @@ Devaney's formulation of a chaotic behavior. \section{Experiments} -Differents experiments have been performed in order to measure the generation +Different experiments have been performed in order to measure the generation speed. \begin{figure}[t] \begin{center} @@ -903,6 +948,9 @@ Faire une courbe du nombre de random en fonction du nombre de threads, \section{The relativity of disorder} \label{sec:de la relativité du désordre} +In the next two sections, we investigate the impact of the choices that have +lead to the definitions of measures in Sections \ref{sec:chaotic iterations} and \ref{deuxième def}. + \subsection{Impact of the topology's finenesse} Let us firstly introduce the following notations.