Relecture jusqu'à la page 9.

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 24d5fc615f1756e251c216a886b5bdef39009155..84efafa5443f23f4504a723320ec63e7c2f36b49 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -109,7 +109,7 @@ Let us finish this paragraph by noticing that, in this paper,
 statistical perfection refers to the ability to pass the whole 
 {\it BigCrush} battery of tests, which is widely considered as the most
 stringent statistical evaluation of a sequence claimed as random.
 statistical perfection refers to the ability to pass the whole 
 {\it BigCrush} battery of tests, which is widely considered as the most
 stringent statistical evaluation of a sequence claimed as random.

-This battery can be found into the well-known TestU01 package.
+This battery can be found into the well-known TestU01 package~\cite{LEcuyerS07}.

 Chaos, for its part, refers to the well-established definition of a
 chaotic dynamical system proposed by Devaney~\cite{Devaney}.
 
 Chaos, for its part, refers to the well-established definition of a
 chaotic dynamical system proposed by Devaney~\cite{Devaney}.
 


@@ -118,7 +118,7 @@ In a previous work~\cite{bgw09:ip,guyeux10} we have proposed a post-treatment on
 as a chaotic dynamical system. Such a post-treatment leads to a new category of
 PRNGs. We have shown that proofs of Devaney's chaos can be established for this
 family, and that the sequence obtained after this post-treatment can pass the
 as a chaotic dynamical system. Such a post-treatment leads to a new category of
 PRNGs. We have shown that proofs of Devaney's chaos can be established for this
 family, and that the sequence obtained after this post-treatment can pass the

-NIST, DieHARD, and TestU01 batteries of tests, even if the inputted generators
+NIST~\cite{Nist10}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} batteries of tests, even if the inputted generators

 cannot.
 The proposition of this paper is to improve widely the speed of the formerly
 proposed generator, without any lack of chaos or statistical properties.
 cannot.
 The proposition of this paper is to improve widely the speed of the formerly
 proposed generator, without any lack of chaos or statistical properties.


@@ -173,7 +173,7 @@ A million numbers  per second will be simply written as
 In \cite{Pang:2008:cec}  a PRNG based on  cellular automata is defined
 with no  requirement to an high  precision  integer   arithmetic  or to any bitwise
 operations. Authors can   generate  about
 In \cite{Pang:2008:cec}  a PRNG based on  cellular automata is defined
 with no  requirement to an high  precision  integer   arithmetic  or to any bitwise
 operations. Authors can   generate  about

-3.2MSample/s on a GeForce 7800 GTX GPU, which is quite an old card now.
+3.2MSamples/s on a GeForce 7800 GTX GPU, which is quite an old card now.

 However, there is neither a mention of statistical tests nor any proof of
 chaos or cryptography in this document.
 
 However, there is neither a mention of statistical tests nor any proof of
 chaos or cryptography in this document.
 


@@ -182,30 +182,35 @@ based on  Lagged Fibonacci 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} battery of TestU01. 
 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} battery of TestU01. 

-However the evaluations of the proposed PRNGs are only statistical.
+However the evaluations of the proposed PRNGs are only statistical ones.

 
 
 Authors of~\cite{conf/fpga/ThomasHL09}  have studied the  implementation of some
 
 
 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.
-
-Cuda  has developped  a  library for  the  generation of  random numbers  called
-Curand~\cite{curand11}.        Several       PRNGs        are       implemented:
-Xorwow~\cite{Marsaglia2003} and  some variants of Sobol. Some  tests report that
-the  fastest version provides  15GSample/s on  the new  Fermi C2050  card. Their
-PRNGs fail to succeed the whole tests of TestU01 on only one test.
+PRNGs on  different computing architectures: CPU,  field-programmable gate array
+(FPGA), massively parallel  processors, and GPU. This study is of interest, because
+the  performance  of the  same  PRNGs on  different architectures are compared. 
+FPGA appears as  the  fastest  and the most
+efficient architecture, providing the fastest number of generated pseudorandom numbers
+per joule. 
+However, we can notice that authors can ``only'' generate between 11 and 16GSamples/s
+with a GTX 280  GPU, which should be compared with
+the results presented in this document.
+We can remark too that the PRNGs proposed in~\cite{conf/fpga/ThomasHL09} are only
+able to pass the {\it Crush} battery, which is very easy compared to the {\it Big Crush} one.
+
+Lastly, Cuda  has developed  a  library for  the  generation of  pseudorandom numbers  called
+Curand~\cite{curand11}.        Several       PRNGs        are       implemented, among
+other things 
+Xorwow~\cite{Marsaglia2003} and  some variants of Sobol. The  tests reported show that
+their  fastest version provides  15GSamples/s on  the new  Fermi C2050  card. 
+But their PRNGs cannot pass the whole TestU01 battery (only one test is failed).

 \newline
 \newline
 \newline
 \newline

-To the best of our knowledge no GPU implementation have been proven to have chaotic properties.
+We can finally remark that, to the best of our knowledge, no GPU implementation have been proven to be chaotic, and the cryptographically secure property is surprisingly never regarded.

 
 \section{Basic Recalls}
 \label{section:BASIC RECALLS}
 
 \section{Basic Recalls}
 \label{section:BASIC RECALLS}

+

 This section is devoted to basic definitions and terminologies in the fields of
 topological chaos and chaotic iterations.
 \subsection{Devaney's Chaotic Dynamical Systems}
 This section is devoted to basic definitions and terminologies in the fields of
 topological chaos and chaotic iterations.
 \subsection{Devaney's Chaotic Dynamical Systems}


@@ -426,10 +431,11 @@ As $G_f$, defined on the domain   $\llbracket 1 ;  \mathsf{N} \rrbracket^{\mathd
 \rightarrow \mathds{B}^\mathsf{N}$, we can preserve the theoretical properties on $G_f$
 during implementations (due to the discrete nature of $f$). It is as if
 $\mathds{B}^\mathsf{N}$ represents the memory of the computer whereas $\llbracket 1 ;  \mathsf{N}
 \rightarrow \mathds{B}^\mathsf{N}$, we can preserve the theoretical properties on $G_f$
 during implementations (due to the discrete nature of $f$). It is as if
 $\mathds{B}^\mathsf{N}$ represents the memory of the computer whereas $\llbracket 1 ;  \mathsf{N}

-\rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance).
+\rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance, in PRNG, or a physical noise in TRNG).

 
 \section{Application to pseudorandomness}
 \label{sec:pseudorandom}
 
 \section{Application to pseudorandomness}
 \label{sec:pseudorandom}

+

 \subsection{A First pseudorandom Number Generator}
 
 We have proposed in~\cite{bgw09:ip} a new family of generators that receives 
 \subsection{A First pseudorandom Number Generator}
 
 We have proposed in~\cite{bgw09:ip} a new family of generators that receives 


@@ -475,7 +481,7 @@ return $y$\;
 
 
 This generator is synthesized in Algorithm~\ref{CI Algorithm}.
 
 
 This generator is synthesized in Algorithm~\ref{CI Algorithm}.

-It takes as input: a function $f$;
+It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation   des   IC   chaotiques};

 an integer $b$, ensuring that the number of executed iterations is at least $b$
 and at most $2b+1$; and an initial configuration $x^0$.
 It returns the new generated configuration $x$.  Internally, it embeds two
 an integer $b$, ensuring that the number of executed iterations is at least $b$
 and at most $2b+1$; and an initial configuration $x^0$.
 It returns the new generated configuration $x$.  Internally, it embeds two


@@ -500,7 +506,7 @@ We have proven in \cite{bcgr11:ip} that,
   if and only if $M$ is a double stochastic matrix.
 \end{theorem} 
 
   if and only if $M$ is a double stochastic matrix.
 \end{theorem} 
 

-This former generator as successively passed various batteries of statistical tests, as the NIST tests~\cite{bcgr11:ip}.
+This former generator as successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07}.

 
 \subsection{Improving the Speed of the Former Generator}
 
 
 \subsection{Improving the Speed of the Former Generator}