\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}
\section{Introduction}
Random numbers are used in many scientific applications and simulations. On
-finite state machines, like computers, it is not possible to generate random
+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.
+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). In this paper we propose a faster
-version which is also proven to be chaotic with the Devaney formulation.
+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 image, they are nowadays commonly used in many scientific
+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 in a GPU when a scientific application runs in a GPU. That is why we
-also provie 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
-
-
-\section{Related works}
-
-In this section we review some GPU based PRNGs.
-\alert{RC, un petit state-of-the-art sur les PRNGs sur GPU ?}
+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. Such devices
+allows us to generated almost 20 billions of random numbers per second.
+
+In order to establish that our PRNGs are chaotic according to the Devaney's
+formulation, we extend what we have proposed in~\cite{guyeux10}. Moreover, we define a new distance to measure the disorder in the chaos and we prove some interesting properties with this distance.
+
+The rest of this paper is organised as follows. In Section~\ref{section:related
+ works} we review some GPU implementions of PRNG. Section~\ref{section:BASIC RECALLS} gives some basic recalls on Devanay's formation of chaos and
+chaotic iterations. In Section~\ref{sec:pseudo-random} the proof of chaos of our
+PRNGs is studied. Section~\ref{sec:efficient prng} presents an efficient
+implementation of our chaotic PRNG on a CPU. Section~\ref{sec:efficient prng
+ gpu} describes the GPU implementation of our chaotic PRNG. In
+Section~\ref{sec:experiments} some experimentations are presented.
+Section~\ref{sec:de la relativité du désordre} describes the relativity of
+disorder. In Section~\ref{sec: chaos order topology} the proof that chaotic
+iterations can be described by iterations on a real interval is established. Finally, we give a conclusion and some perspectives.
+
+
+
+
+\section{Related works on GPU based PRNGs}
+\label{section:related works}
+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. When authors mention the number of random numbers generated per second
+we mention it. We consider that a million numbers per second corresponds to
+1MSample/s and than a billion numbers per second corresponds to 1GSample/s.
+
+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
+3.2MSample/s 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.
+
+
+Authors of~\cite{conf/fpga/ThomasHL09} have studied the implementation of some
+PRNGs on diferrent computing architectures: CPU, field-programmable gate array
+(FPGA), GPU and massively parallel processor. This study is interesting because
+it shows the performance of the same PRNGs on different architeture. For
+example, the FPGA is globally the fastest architecture and it is also the
+efficient one because it provides the fastest number of generated random numbers
+per joule. Concerning the GPU, authors can generate betweend 11 and 16GSample/s
+with a GTX 280 GPU. The drawback of this work is that those PRNGs only succeed
+the {\it Crush} test which is easier than the {\it Big Crush} test.
+\newline
+\newline
+To the best of our knowledge no GPU implementation have been proven to have chaotic properties.
\section{Basic Recalls}
\label{section:BASIC RECALLS}
\rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance).
\section{Application to Pseudo-Randomness}
-
+\label{sec:pseudo-random}
\subsection{A First Pseudo-Random Number Generator}
We have proposed in~\cite{bgw09:ip} a new family of generators that receives
\section{Efficient PRNG based on Chaotic Iterations}
+\label{sec:efficient prng}
In order to implement efficiently a PRNG based on chaotic iterations it is
possible to improve previous works [ref]. One solution consists in considering
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].
-
-\section{Efficient prng based on chaotic iterations on GPU}
+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 PRNGs based on chaotic iterations on GPU}
+\label{sec:efficient prng gpu}
In order to benefit from computing power of GPU, a program needs to define
independent blocks of threads which can be computed simultaneously. In general,
Devaney's formulation of a chaotic behavior.
\section{Experiments}
+\label{sec:experiments}
Different experiments have been performed in order to measure the generation
-speed.
-\begin{figure}[t]
+speed. In Figure~\ref{fig:time_gpu} we compare the number of random numbers generated per second.
+
+\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=.7]{curve_time_gpu.pdf}
\end{center}
\caption{Number of random numbers generated per second}
-\label{fig:time_naive_gpu}
+\label{fig:time_gpu}
\end{figure}
\section{Chaos on the order topology}
-
+\label{sec: chaos order topology}
\subsection{The phase space is an interval of the real line}
\subsubsection{Toward a topological semiconjugacy}
