suite

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 41e628a97bc3cd8695dd4bed1ffea352591b5be5..19adf220330a1488041bf7d8286444738d40e069 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -71,26 +71,39 @@ 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
 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.
+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 

 
 

+The rest of this paper  is organised as follows. In Section~\ref{section:related
+  works}  we review  some GPU  implementions of  PRNG.  Section~\ref{sec:chaotic
+  iterations}  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.

 
 
 
 

-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 on GPU based PRNGs}
 
 
 \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
 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.
+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
 
 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).
+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
 
 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


@@ -99,6 +112,18 @@ 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.
 
 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}
 To the best of our knowledge no GPU implementation have been proven to have chaotic properties.
 
 \section{Basic Recalls}


@@ -326,7 +351,7 @@ $\mathds{B}^\mathsf{N}$ represents the memory of the computer whereas $\llbracke
 \rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance).
 
 \section{Application to Pseudo-Randomness}
 \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 
 \subsection{A First Pseudo-Random Number Generator}
 
 We have proposed in~\cite{bgw09:ip} a new family of generators that receives 


@@ -696,6 +721,7 @@ have $d((S,E),(\tilde S,E))<\epsilon$.
 
 
 \section{Efficient PRNG based on Chaotic Iterations}
 
 
 \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  order to  implement efficiently  a PRNG  based on  chaotic iterations  it is
 possible to improve  previous works [ref]. One solution  consists in considering


@@ -782,7 +808,8 @@ 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}.
 
 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{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,
 
 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,


@@ -925,6 +952,7 @@ chaotic iterations presented previously, and for this reason, it satisfies the
 Devaney's formulation of a chaotic behavior.
 
 \section{Experiments}
 Devaney's formulation of a chaotic behavior.
 
 \section{Experiments}

+\label{sec:experiments}

 
 Different experiments have been performed in order to measure the generation
 speed.
 
 Different experiments have been performed in order to measure the generation
 speed.


@@ -1056,7 +1084,7 @@ sets $A$ and $B$, an integer $n$ must satisfy $f^{(n)}(A) \cap B \neq
 
 
 \section{Chaos on the order topology}
 
 
 \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}
 \subsection{The phase space is an interval of the real line}
 
 \subsubsection{Toward a topological semiconjugacy}