X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/f8b9c6eb41cd165ad2c65d1a4571a41fdcd26ff5..0067ddaf35f9842d01238d6d0b1161e791e66f2e:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 1129a07..6e063fd 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -949,17 +949,20 @@ It is  possible to build a  cryptographically secure prng based  on the previous
 algorithm (algorithm~\ref{algo:gpu_kernel2}).   It simply consists  in replacing
 the  {\it  xor-like} algorithm  by  another  cryptographically  secure prng.  In
 practice, we suggest  to use the BBS algorithm~\cite{BBS}  which takes the form:
-$$x_{n+1}=x_n^2~ mod~  M$$ where M  is the product  of the prime  numbers. Those
+$$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers. Those
 prime numbers  need to be congruent  to 3 modulus  4. In practice, this  PRNG is
 known to  be slow and  not efficient for  the generation of random  numbers. For
 current  GPU   cards,  the  modulus   operation  is  the  most   time  consuming
 operation. So in  order to obtain quite reasonable  performances, it is required
 to use only modulus on 32  bits integer numbers. Consequently $x_n^2$ need to be
 less than  $2^{32}$ and the  number $M$  need to be  less than $2^{16}$.   So in
-pratice we can choose prime number around 256 that are congruent to 3 modulus 4.
-With 32 bits numbers,  only the 4 least significant bits of  $x_n$ can be chosen
-(the   maximum    number   of   undistinguishing   is   less    or   equals   to
-$log_2(log_2(x_n))$).
+pratice we can  choose prime numbers around 256 that are  congruent to 3 modulus
+4.  With  32 bits numbers,  only the  4 least significant  bits of $x_n$  can be
+chosen  (the   maximum  number  of   undistinguishing  is  less  or   equals  to
+$log_2(log_2(x_n))$). So  to generate a 32 bits  number, we need to  use 8 times
+the BBS algorithm, with different combinations of $M$ is required.
+
+Currently this PRNG does not succeed to pass all the tests of TestU01.
 
 \section{Experiments}
 \label{sec:experiments}
@@ -970,12 +973,14 @@ Intel  Xeon E5530 cadenced  at 2.40  GHz for  our experiments  and we  have used
 another one  equipped with  a less performant  CPU and  a GeForce GTX  280. Both
 cards have 240 cores.
 
-In Figure~\ref{fig:time_gpu}  we compare the number of  random numbers generated
-per second. The xor-like prng  is a xor64 described in~\cite{Marsaglia2003}.  In
-order to obtain the optimal performance  we remove the storage of random numbers
-in the GPU memory. This step is time consuming and slows down the random number
-generation.  Moreover, if you are interested by applications that consume random
-numbers  directly   when  they  are  generated,  their   storage  is  completely
+In  Figure~\ref{fig:time_xorlike_gpu} we  compare the  number of  random numbers
+generated per second with the xor-like based PRNG. In this figure, the optimized
+version use the {\it xor64} described in~\cite{Marsaglia2003}. The naive version
+use  the three  xor-like  PRNGs described  in Listing~\ref{algo:seqCIprng}.   In
+order to obtain the optimal performance we removed the storage of random numbers
+in the GPU memory. This step is time consuming and slows down the random numbers
+generation.  Moreover, if one is  interested by applications that consume random
+numbers  directly   when  they  are  generated,  their   storage  are  completely
 useless. In this  figure we can see  that when the number of  threads is greater
 than approximately 30,000 upto 5 millions the number of random numbers generated
 per second  is almost constant.  With the  naive version, it is  between 2.5 and
@@ -986,10 +991,10 @@ should be of better quality.
 
 \begin{figure}[htbp]
 \begin{center}
-  \includegraphics[scale=.7]{curve_time_gpu.pdf}
+  \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
 \end{center}
-\caption{Number of random numbers generated per second}
-\label{fig:time_gpu}
+\caption{Number of random numbers generated per second with the xorlike based PRNG}
+\label{fig:time_xorlike_gpu}
 \end{figure}
 
 
@@ -997,7 +1002,22 @@ In  comparison,   Listing~\ref{algo:seqCIprng}  allows  us   to  generate  about
 138MSample/s with only one core of the Xeon E5530.
 
 
+In Figure~\ref{fig:time_bbs_gpu}  we highlight the performance  of the optimized
+BBS based  PRNG on GPU. Performances are  less important. On the  Tesla C1060 we
+obtain approximately 1.8GSample/s and on the GTX 280 about 1.6GSample/s.
+
+\begin{figure}[htbp]
+\begin{center}
+  \includegraphics[scale=.7]{curve_time_bbs_gpu.pdf}
+\end{center}
+\caption{Number of random numbers generated per second with the BBS based PRNG}
+\label{fig:time_bbs_gpu}
+\end{figure}
 
+Both  these  experimentations allows  us  to conclude  that  it  is possible  to
+generate a  huge number of pseudo-random  numbers with the  xor-like version and
+about tens  times less with the BBS  based version. The former  version has only
+chaotic properties whereas the latter also has cryptographically properties.
 
 
 %% \section{Cryptanalysis of the Proposed PRNG}
@@ -1652,15 +1672,19 @@ proving that $H$ is not secure, a contradiction.
 
 
 In  this  paper  we have  presented  a  new  class  of  PRNGs based  on  chaotic
-iterations. We have proven that these PRNGs are chaotic in the sense of Devenay. 
+iterations. We have proven that these PRNGs are chaotic in the sense of Devenay.
+We also propose a PRNG cryptographically secure and its implementation on GPU.
+
+An  efficient implementation  on  GPU based  on  a xor-like  PRNG  allows us  to
+generate   a  huge   number   of  pseudo-random   numbers   per  second   (about
+20Gsample/s). This PRNG succeeds to pass the hardest batteries of TestU01.
+
+In future  work we plan to  extend this work  for parallel PRNG for  clusters or
+grid computing. We also plan to improve  the BBS version in order to succeed all
+the tests of TestU01.
 
-An efficient implementation on GPU allows us to generate a huge number of pseudo
-random numbers  per second  (about 20Gsample/s). Our  PRNGs succeed to  pass the
-hardest batteries of test (TestU01).
 
-In future  work we plan  to extend our  work in order to  have cryptographically
-secure PRNGs because in some situations this property may be important.
 
-\bibliographystyle{plain}
+\bibliographystyle{plain} 
 \bibliography{mabase}
 \end{document}
