From: couturie Date: Sun, 6 Nov 2011 18:56:21 +0000 (+0100) Subject: suite X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/9000a5dc19eb61806daa88858a42b7a433da0c5d suite --- diff --git a/mabase.bib b/mabase.bib index 59c6666..3bba177 100644 --- a/mabase.bib +++ b/mabase.bib @@ -4231,3 +4231,25 @@ pages = {5278--5288}, } + + +@comment {regarder : Pseudo-Random Number Generation for Brownian Dynamics and Dissipative Particle Dynamics Simulations on GPU Devices} +@comment {CL Phillips, JA Anderson… - Journal of Computational Physics, 2011 - Elsevier} + +@InProceedings{conf/fpga/ThomasHL09, + title = "A comparison of {CPU}s, {GPU}s, {FPGA}s, and massively + parallel processor arrays for random number + generation", + author = "David B. Thomas and Lee W. Howes and Wayne Luk", +booktitle = "Proceedings of the {ACM}/{SIGDA} 17th International + Symposium on Field Programmable Gate Arrays, {FPGA} + 2009, Monterey, California, {USA}, February 22-24, + 2009", + bibdate = "2010-06-29", + publisher = "ACM", + year = "2009", + editor = "Paul Chow and Peter Y. K. Cheung", + ISBN = "978-1-60558-410-2", + pages = "63--72", + URL = "http://doi.acm.org/10.1145/1508128.1508139", +} \ No newline at end of file diff --git a/prng_gpu.tex b/prng_gpu.tex index 41e628a..19adf22 100644 --- 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 -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} - +\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 -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 -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 @@ -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. + +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} @@ -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} - +\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 @@ -696,6 +721,7 @@ have $d((S,E),(\tilde S,E))<\epsilon$. \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 @@ -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}. -\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, @@ -925,6 +952,7 @@ chaotic iterations presented previously, and for this reason, it satisfies the Devaney's formulation of a chaotic behavior. \section{Experiments} +\label{sec:experiments} 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} - +\label{sec: chaos order topology} \subsection{The phase space is an interval of the real line} \subsubsection{Toward a topological semiconjugacy}