\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}
\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. Devaney~\cite{Devaney} proposed a common mathematical
+formulation of chaotic dynamical systems. Concerning the statistical tests,
+TestU01the is the best-known public-domain statistical testing packages. So we
+use it for all our PRNGs, especially the {\it BigCrush} which is based on the largest
+serie of tests.
+
+In a previous work~\cite{bgw09:ip} we have proposed a new familly of chaotic
+PRNG based on chaotic iterations (IC). In this paper we propose a faster
+version which is also proven to be chaotic with the Devaney formulation.
+
+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.
+
\section{Basic Recalls}
\label{section:BASIC RECALLS}
This section is devoted to basic definitions and terminologies in the fields of
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:
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}
\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}
\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.
