From: Raphael Couturier Date: Wed, 23 Nov 2011 15:29:01 +0000 (+0100) Subject: new X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/8d3c5f7139485b7ef6336618316517861ac6a039 new --- diff --git a/mabase.bib b/mabase.bib index ae0a8d5..8162128 100644 --- a/mabase.bib +++ b/mabase.bib @@ -4267,6 +4267,14 @@ booktitle = "Proceedings of the {ACM}/{SIGDA} 17th International @manual{Nvid10, author = {Nvidia}, title = {Cuda cublas library}, - year = {2010}, - Note = {Version 3.1}, + year = {2011}, + Note = {Version 4.0}, } + +@manual{curand11, + author = {Nvidia}, + title = {Curand library}, + year = {2011}, + Note = {Version 4.0}, + } + diff --git a/prng_gpu.tex b/prng_gpu.tex index 150e434..2dfa78e 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -44,9 +44,9 @@ Guyeux\thanks{Authors in alphabetic order}} \maketitle \begin{abstract} -In this paper we present a new produce pseudo-random numbers generator (PRNG) on +In this paper we present a new pseudo-random numbers generator (PRNG) on graphics processing units (GPU). This PRNG is based on chaotic iterations. it -is proven to be chaotic in the Devany's formulation. We propose an efficient +is proven to be chaotic in the Devanay's formulation. We propose an efficient implementation for GPU which succeeds to the {\it BigCrush}, the hardest batteries of test of TestU01. Experimentations show that this PRNG can generate about 20 billions of random numbers per second on Tesla C1060 and NVidia GTX280 @@ -59,7 +59,7 @@ cards. Random numbers are used in many scientific applications and simulations. On 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 +numbers but only pseudo-random numbers. In practice, a good pseudo-random numbers 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 @@ -83,9 +83,7 @@ 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. +formulation, we extend what we have proposed in~\cite{guyeux10}. 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 @@ -95,10 +93,7 @@ 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. + Finally, we give a conclusion and some perspectives. @@ -134,6 +129,12 @@ 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. \newline \newline To the best of our knowledge no GPU implementation have been proven to have chaotic properties. @@ -413,7 +414,7 @@ It takes as input: a function $f$; 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 -\textit{XORshift}$(k)$ PRNGs \cite{Marsaglia2003} that returns integers +\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that returns integers uniformly distributed into $\llbracket 1 ; k \rrbracket$. \textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia, @@ -860,6 +861,9 @@ and random number of our PRNG is equals to $100,000\times ((4+5+6)\times All the tests performed to pass the BigCrush of TestU01 succeeded. Different number of threads, called \texttt{NumThreads} in our algorithm, have been tested upto $10$ millions. +\newline +\newline +{\bf QUESTION : on laisse cette remarque, je suis mitigé !!!} \begin{remark} Algorithm~\ref{algo:gpu_kernel} has the advantage to manipulate independent @@ -978,10 +982,10 @@ In comparison, Listing~\ref{algo:seqCIprng} allows us to generate about -\section{Cryptanalysis of the Proposed PRNG} +%% \section{Cryptanalysis of the Proposed PRNG} -Mettre ici la preuve de PCH +%% Mettre ici la preuve de PCH %\section{The relativity of disorder} %\label{sec:de la relativité du désordre} @@ -1515,6 +1519,18 @@ Mettre ici la preuve de PCH \section{Conclusion} + + +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. + +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} \bibliography{mabase} \end{document}