bbs

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index e5b80cc94aa90c5eaa6dd82c2962c3350f16e94c..6e063fd1f07d19932c823816b8961c14b2868580 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -962,6 +962,8 @@ 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.
 
 $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}
 
 \section{Experiments}
 \label{sec:experiments}
 


@@ -971,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.
 
 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
 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


@@ -989,7 +993,7 @@ should be of better quality.
 \begin{center}
   \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
 \end{center}
 \begin{center}
   \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
 \end{center}

-\caption{Number of random numbers generated per second with the xorlike based prng}
+\caption{Number of random numbers generated per second with the xorlike based PRNG}

 \label{fig:time_xorlike_gpu}
 \end{figure}
 
 \label{fig:time_xorlike_gpu}
 \end{figure}
 


@@ -998,16 +1002,22 @@ In  comparison,   Listing~\ref{algo:seqCIprng}  allows  us   to  generate  about
 138MSample/s with only one core of the Xeon E5530.
 
 
 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}
 
 \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}
+\caption{Number of random numbers generated per second with the BBS based PRNG}

 \label{fig:time_bbs_gpu}
 \end{figure}
 
 \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}
 
 
 %% \section{Cryptanalysis of the Proposed PRNG}


@@ -1662,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
 
 
 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}
 \bibliography{mabase}
 \end{document}