From ccff43db77ed9a71b6d9fc52aaf03585104713ce Mon Sep 17 00:00:00 2001 From: couturie Date: Sat, 20 Jul 2013 21:03:33 +0200 Subject: [PATCH] ch18 --- BookGPU/Chapters/chapter17/ch17.tex | 2 +- BookGPU/Chapters/chapter18/biblio18.bib | 15 +- BookGPU/Chapters/chapter18/ch18.tex | 166 +++++++++--------- .../figures/curve_time_xorlike_gpu.pdf | Bin 8005 -> 8014 bytes 4 files changed, 94 insertions(+), 89 deletions(-) diff --git a/BookGPU/Chapters/chapter17/ch17.tex b/BookGPU/Chapters/chapter17/ch17.tex index f468214..f69219e 100755 --- a/BookGPU/Chapters/chapter17/ch17.tex +++ b/BookGPU/Chapters/chapter17/ch17.tex @@ -658,7 +658,7 @@ of MIOR as well as for other ABM, to ensure that each work-item is not too constrained in its execution. \pagebreak -\lstinputlisting[caption=main MIOR kernel,label=ch17:listing:mior_kernels]{Chapterbis/chapter17/code/mior_kernels.cl} +\lstinputlisting[caption=main MIOR kernel,label=ch17:listing:mior_kernels]{./Chapters/chapter17/code/mior_kernels.cl} From the sequential algorithm (Algorithm~\ref{ch17:seqalgo}) where all the agents share the same data, we have developed a parallel algorithm diff --git a/BookGPU/Chapters/chapter18/biblio18.bib b/BookGPU/Chapters/chapter18/biblio18.bib index a2d65e4..fe7bb5d 100644 --- a/BookGPU/Chapters/chapter18/biblio18.bib +++ b/BookGPU/Chapters/chapter18/biblio18.bib @@ -25,6 +25,7 @@ year = "2007", number = "4", volume = "33", + pages="22-40", bibdate = "2007-11-06", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07", @@ -32,8 +33,8 @@ } @manual{Nvid10, - author = {Nvidia}, - title = {Cuda cublas library}, + author = {{NVIDIA}}, + title = {CUDA CUBLAS library}, year = {2011}, Note = {Version 4.0}, } @@ -42,7 +43,11 @@ author = "Jenkins, R. J.", title = "{ISAAC}", booktitle = "IWFSE: International Workshop on Fast Software - Encryption, LNCS", + Encryption", +series={{Lecture Notes in Computer Science}}, +volume={1039}, + pages={41-49}, + publisher={Springer Verlag}, year = "1996", } @@ -57,11 +62,11 @@ @book{kellert1994wake, - title={In the wake of chaos: unpredictable order in dynamical systems}, + title={In the Wake of Chaos: Unpredictable Order in Dynamical Systems}, author={Kellert, S. H.}, isbn={9780226429762}, lccn={lc92030355}, - series={Science and its conceptual foundations}, + series={{Science and Its Conceptual Foundations}}, url={http://books.google.fr/books?id=CUpcgo8DqR4C}, year={1994}, publisher={University of Chicago Press} diff --git a/BookGPU/Chapters/chapter18/ch18.tex b/BookGPU/Chapters/chapter18/ch18.tex index d72e9a3..71d2b84 100755 --- a/BookGPU/Chapters/chapter18/ch18.tex +++ b/BookGPU/Chapters/chapter18/ch18.tex @@ -2,25 +2,25 @@ %\chapterauthor{Christophe Guyeux}{Femto-ST Institute, University of Franche-Comt\'{e}} -\chapter{Pseudorandom Number Generator on GPU} +\chapter{Pseudorandom number generator on GPU} \label{chapter18} \section{Introduction} Randomness is of importance in many fields such as scientific -simulations or cryptography. ``Random numbers'' can mainly be -generated either by a deterministic and reproducible algorithm called -a pseudorandom number generator (PRNG)\index{PRNG}, or by a physical non-deterministic +simulations or cryptography. Random numbers can mainly be +generated by either a deterministic and reproducible algorithm called +a pseudorandom number generator (PRNG)\index{PRNG}, or by a physical nondeterministic process having all the characteristics of a random noise, called a truly random number generator (TRNG). In this chapter, we focus on -reproducible generators, useful for instance in Monte-Carlo based +reproducible generators, useful for instance in MonteCarlo-based simulators. These domains need PRNGs that are statistically irreproachable. In some fields such as in numerical simulations, speed is a strong requirement that is usually attained by using parallel architectures. In that case, a recurrent problem is that a deflation of the statistical qualities is often reported, when the parallelization of a good PRNG is realized. This -is why ad-hoc PRNGs for each possible architecture must be found to +is why adhoc PRNGs for each possible architecture must be found to achieve both speed and randomness. On the other hand, speed is not the main requirement in cryptography: the most important point is to define \emph{secure} generators able to withstand malicious @@ -31,14 +31,14 @@ formulation, he or she should not be able (in practice) to predict the next bit of the generator, having the knowledge of all the binary digits that have been already released~\cite{Goldreich}. ``Being able in practice'' refers here to the possibility to achieve this attack in polynomial -time, and to the exponential growth of the difficulty of this +time and to the exponential growth of the difficulty of this challenge when the size of the parameters of the PRNG increases. Finally, a small part of the community working in this domain focuses on a -third requirement, that is to define chaotic generators~\cite{kellert1994wake, Wu20051195,gleick2011chaos}. -The main idea is to benefits from a chaotic dynamical system to obtain a -generator that is unpredictable, disordered, sensible to its seed, or in other word chaotic. +third requirement: to define chaotic generators~\cite{kellert1994wake, Wu20051195,gleick2011chaos}. +The main idea is to benefit from a chaotic dynamical system to obtain a +generator that is unpredictable, disordered, sensible to its seed, or in other words, chaotic. These scientists' desire is to map a given chaotic dynamics into a sequence that seems random and unassailable due to chaos. However, the chaotic maps used as a pattern are defined in the real line @@ -56,18 +56,18 @@ or cryptographically secure~\cite{bgw09:ip,bgw10:ip,bfgw11:ij,bfg12a:ip}. This f architectures in this chapter. -Let us finish this introduction by noticing that, in this paper, +Let us finish this introduction by noticing that, in this chapter, 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 in the well-known TestU01 package~\cite{LEcuyerS07}\index{TestU01}. More precisely, each time we performed a test on a PRNG, we ran it -twice in order to observe if all $p-$values were inside [0.01, 0.99]. In -fact, we observed that few $p-$values (less than ten) are sometimes +twice in order to observe if all $p$-values were inside [0.01, 0.99]. In +fact, we observed that few $p$-values (fewer than 10 out of 160) are sometimes outside this interval but inside [0.001, 0.999], so that is why a second run has allowed us to confirm that the values outside are not for the same test. With this approach all our PRNGs pass the {\it - BigCrush} successfully and all $p-$values are at least once inside + BigCrush} successfully and all $p$-values are at least once inside [0.01, 0.99]. Chaos, for its part, refers to the well-established definition of a chaotic dynamical system defined by Devaney~\cite{Devaney}. @@ -81,7 +81,7 @@ naive and improved efficient generators for CPU and for GPU. These generators are finally experimented in Section~\ref{sec:experiments}. -\section{Basic Remindees} +\section{Basic remindees} \label{section:BASIC RECALLS} This section is devoted to basic definitions and terminologies in the fields of @@ -89,21 +89,21 @@ topological chaos and chaotic iterations. We assume the reader is familiar with basic notions on topology (see for instance~\cite{Devaney}). -\subsection{A Short Presentation of Chaos} +\subsection{A short presentation of chaos} Chaos theory studies the behavior of dynamical systems that are perfectly predictable, yet appear to be wildly amorphous and meaningless. Chaotic systems\index{chaotic systems} are highly sensitive to initial conditions, which is popularly referred to as the butterfly effect. In other words, small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes, -rendering long-term prediction impossible in general \cite{kellert1994wake}. This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved \cite{kellert1994wake}. That is, the deterministic nature of these systems does not make them predictable \cite{kellert1994wake,Werndl01032009}. This behavior is known as deterministic chaos, or simply chaos. It has been well-studied in mathematics and +in general rendering long-term prediction impossible \cite{kellert1994wake}. This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved \cite{kellert1994wake}. That is, the deterministic nature of these systems does not make them predictable \cite{kellert1994wake,Werndl01032009}. This behavior is known as deterministic chaos, or simply chaos. It has been well-studied in mathematics and physics, leading among other things to the well-established definition of Devaney which can be found next. -\subsection{On Devaney's Definition of Chaos}\index{chaos} +\subsection{On Devaney's definition of chaos}\index{chaos} \label{sec:dev} Consider a metric space $(\mathcal{X},d)$ and a continuous function $f:\mathcal{X}\longrightarrow \mathcal{X}$, for one-dimensional dynamical systems of the form: \begin{equation} @@ -122,7 +122,7 @@ the following definition of chaotic behavior, formulated by Devaney~\cite{Devane \end{equation} Intuitively, a topologically transitive map has points that eventually move under iteration from one arbitrarily small neighborhood to any other. Consequently, the dynamical system cannot be decomposed into two disjoint open sets that are invariant under the map. Note that if a map possesses a dense orbit, then it is clearly topologically transitive. -\item Density of periodic points in $\mathcal{X}$\index{density of periodic points}. +\item Density of periodic points in $\mathcal{X}$\index{density of periodic points}: Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of periodic points of $f$. Then $P$ is dense in $\mathcal{X}$: @@ -130,17 +130,17 @@ Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of \overline{P}=\mathcal{X} . \end{equation} -The density of periodic orbits means that every point in space is closely approached by periodic orbits in an arbitrary way. Topologically mixing systems failing this condition may not display sensitivity to initial conditions presented below, and hence may not be chaotic. +The density of periodic orbits means that every point in space is closely approached by periodic orbits in an arbitrary way. Topologically mixing systems failing this condition may not display sensitivity to initial conditions presented below and, hence,may not be chaotic. \item Sensitive dependence on initial conditions\index{sensitive dependence on initial conditions}: $\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$ -Intuitively, a map possesses sensitive dependence on initial conditions if there exist points arbitrarily close to $x$ that eventually separate from $x$ by at least $\varepsilon$ under the iteration of $f$. Not all points near $x$ need eventually separate from $x$ under iteration, but there must be at least one such point in every neighborhood of $x$. If a map possesses sensitive dependence on initial conditions, then for all practical purposes, the dynamics of the map defy numerical computation. Small errors in computation that are introduced by round-off may become magnified upon iteration. The results of numerical computation of an orbit, no matter how accurate, may bear no resemblance whatsoever with the real orbit. +Intuitively, a map possesses sensitive dependence on initial conditions if there exist points arbitrarily close to $x$ that eventually separate from $x$ by at least $\varepsilon$ under the iteration of $f$. Not all points near $x$ need to be eventually separate from $x$ under iteration, but there must be at least one such point in every neighborhood of $x$. If a map possesses sensitive dependence on initial conditions, then for all practical purposes, the dynamics of the map defy numerical computation. Small errors in computation that are introduced by round-off may become magnified upon iteration. The results of numerical computation of an orbit, no matter how accurate, may bear no resemblance whatsoever with the real orbit. \end{itemize} \end{definition} -When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting Devaney: ``it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And, in the midst of this random behavior, we nevertheless have an element of regularity.'' Fundamentally different behaviors are consequently possible and occur in an unpredictable way. +When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting Devaney~\cite[p. 50]{Devaney}: ``it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And, in the midst of this random behavior, we nevertheless have an element of regularity.'' Fundamentally different behaviors are consequently possible and occur in an unpredictable way. @@ -180,15 +180,15 @@ f(x^{n-1})_{i} & \text{if}~ i \in S^n. \end{equation} \end{definition} -In other words, at the $n^{th}$ iteration, only the cells of $S^{n}$ are -``iterated''. +In other words, at the $nth$ iteration, only the cells of $S^{n}$ are +iterated. Chaotic iterations generate a set of vectors; they are defined by an initial state $x^{0}$, an iteration function $f$, and a chaotic strategy $S$~\cite{bg10:ij}. These ``chaotic iterations'' can behave chaotically as defined by Devaney, depending on the choice of $f$~\cite{bg10:ij}. For instance, chaos is obtained when $f$ is the vectorial negation. Note that, with this example of function, chaotic iterations -defined above can be rewritten as: +defined above can be rewritten as \begin{equation} \label{equation Oplus} x^0 \in \llbracket 0,2^\mathsf{N}-1\rrbracket,~\mathcal{S}^n \in \mathcal{P}\left(\llbracket 1,2^\mathsf{N}-1\rrbracket\right)^\mathds{N},~~ x^{n+1}=x^n \oplus \mathcal{S}^n, @@ -197,13 +197,13 @@ where $\mathcal{P}(X)$ stands for the set of subsets of $X$, whereas $a\oplus b$ is the bitwise exclusive or operation between the binary representation of the integers $a$ and $b$. Note that the term $\mathcal{S}^n$ is directly and obviously linked to the $S^n$ of -Eq.\ref{eq:generalIC}. As recalled above, such an iterative sequence +Eq.~\ref{eq:generalIC}. Such an iterative sequence satisfies the Devaney's definition of chaos. -\section{Toward Efficiency and Improvement for CI PRNG} +\section{Toward efficiency and improvement for CI PRNG} \label{sec:efficient PRNG} -\subsection{First Efficient Implementation of a PRNG based on Chaotic Iterations} +\subsection{First efficient implementation of a PRNG based on chaotic iterations} % %Based on the proof presented in the previous section, it is now possible to %improve the speed of the generator formerly presented in~\cite{bgw09:ip,guyeux10}. @@ -272,60 +272,59 @@ unsigned int CIPRNG() { In Listing~\ref{algo:seqCIPRNG} a sequential version of the proposed PRNG based on chaotic iterations is presented, which extends the generator family formerly presented in~\cite{bgw09:ip,guyeux10}. The xor operator is represented by -\textasciicircum. This function uses three classical 64-bits PRNGs, namely the +\textasciicircum. This function uses three classical 64-bit PRNGs, namely the \texttt{xorshift}, the \texttt{xor128}, and the \texttt{xorwow}~\cite{Marsaglia2003}. In the following, we call them ``xor-like PRNGs''. As each xor-like PRNG uses 64-bits whereas our proposed generator -works with 32-bits, we use the command \texttt{(unsigned int)}, that selects the +works with 32-bits, we use the command \texttt{(unsigned int)}, which selects the 32 least significant bits of a given integer, and the code \texttt{(unsigned int)(t$>>$32)} in order to obtain the 32 most significant bits of \texttt{t}. -Thus producing a pseudorandom number needs 6 xor operations with 6 32-bits numbers -that are provided by 3 64-bits PRNGs. This version successfully passes the -stringent BigCrush battery of tests~\cite{LEcuyerS07}. -At this point, we thus -have defined an efficient and statistically unbiased generator. Its speed is +Thus producing a pseudorandom number needs 6 xor operations with 6 32-bit numbers +that are provided by 3 64-bit PRNGs. This version successfully passes the +stringent {\it BigCrush} battery of tests~\cite{LEcuyerS07}. +At this point, we have defined an efficient and statistically unbiased generator. Its speed is directly related to the use of linear operations, but for the same reason, this fast generator cannot be proven as secure. -\subsection{Efficient PRNGs based on Chaotic Iterations on GPU} +\subsection{Efficient PRNGs based on chaotic iterations on GPU} \label{sec:efficient PRNG gpu} In order to benefit from the computing power of GPU, a program needs to have independent blocks of threads that can be computed simultaneously. In general, the larger the number of threads is, the more local memory is used, and the less branching instructions are -used (if, while, ...) and so, the better the performances on GPU are. +used (if, while, etc.) and so, the better the performances on GPU are. Obviously, having these requirements in mind, it is possible to build a program similar to the one presented in Listing \ref{algo:seqCIPRNG}, which computes pseudorandom numbers on GPU. To -do so, we must firstly recall that in the CUDA~\cite{Nvid10} +do so, we must first recall that in the CUDA~\cite{Nvid10} environment, threads have a local identifier called \texttt{ThreadIdx}, which is relative to the block containing -them. Furthermore, in CUDA, parts of the code that are executed by the GPU, are +them. Furthermore, in CUDA, parts of the code that are executed by the GPU are called {\it kernels}. -\subsection{Naive Version for GPU} +\subsection{Naive version for GPU} It is possible to deduce from the CPU version a quite similar version adapted to GPU. -The simple principle consists in making each thread of the GPU computing the CPU version of our PRNG. +The simple principle consists of making each thread of the GPU compute the CPU version of our PRNG. Of course, the three xor-like PRNGs used in these computations must have different parameters. In a given thread, these parameters are randomly picked from another PRNGs. The initialization stage is performed by the CPU. -To do this, the ISAAC PRNG~\cite{Jenkins96} is used to set all the +To do this, the Indirection, Shift, Accumulate, Add, and Count (ISAAC) PRNG~\cite{Jenkins96} is used to set all the parameters embedded into each thread. The implementation of the three xor-like PRNGs is straightforward when their parameters have been allocated in the GPU memory. Each xor-like works with an internal number $x$ that saves the last generated pseudorandom number. Additionally, the -implementation of the xor128, the xorshift, and the xorwow respectively require +implementation of the {\it xor128}, the {\it xorshift}, and the {\it xorwow}, respectively, require 4, 5, and 6 unsigned long as internal variables. @@ -344,7 +343,7 @@ NumThreads: number of threads\;} store internal variables in InternalVarXorLikeArray[threadIdx]\; } \end{small} -\caption{Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations} +\caption{main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations} \label{algo:gpu_kernel} \end{algorithm} @@ -353,35 +352,35 @@ NumThreads: number of threads\;} Algorithm~\ref{algo:gpu_kernel} presents a naive implementation of the proposed PRNG on GPU. Due to the available memory in the GPU and the number of threads used simultaneously, the number of random numbers that a thread can generate -inside a kernel is limited (\emph{i.e.}, the variable \texttt{n} in -algorithm~\ref{algo:gpu_kernel}). For instance, if $100,000$ threads are used and -if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)}, +inside a kernel is limited (i.e., the variable {\it n} in +Algorithm~\ref{algo:gpu_kernel}). For instance, if $100,000$ threads are used and +if $n=100$\footnote{In fact, we need to add the initial seed (a 32-bit number).}, then the memory required to store all of the internal variables of both the xor-like -PRNGs\footnote{we multiply this number by $2$ in order to count 32-bits numbers} +PRNGs\footnote{We multiply this number by $2$ in order to count 32-bit numbers.} and the pseudorandom numbers generated by our PRNG, is equal to $100,000\times ((4+5+6)\times -2+(1+100))=1,310,000$ 32-bits numbers, that is, approximately $52$Mb. +2+(1+100))=1,310,000$ 32-bit numbers, that is, approximately $52$Mb. -This generator is able to pass the whole BigCrush battery of tests, for all -the versions that have been tested depending on their number of threads -(called \texttt{NumThreads} in our algorithm, tested up to $5$ million). +This generator is able to pass the whole {\it BigCrush} battery of tests, for all +the versions that have been tested depend on their number of threads +(called NumThreads in our algorithm, tested up to $5$ million). -\subsection{Improved Version for GPU} +\subsection{Improved version for GPU} As GPU cards using CUDA have shared memory between threads of the same block, it is possible to use this feature in order to simplify the previous algorithm, -i.e., to use less than 3 xor-like PRNGs. The solution consists in computing only -one xor-like PRNG by thread, saving it into the shared memory, and then to use the results +i.e., to use fewer than 3 xor-like PRNGs. The solution consists in computing only +one xor-like PRNG by thread, saving it into the shared memory, and then using the results of some other threads in the same block of threads. In order to define which thread uses the result of which other one, we can use a combination array that contains the indexes of all threads and for which a combination has been performed. In Algorithm~\ref{algo:gpu_kernel2}, two combination arrays are used. The -variable \texttt{offset} is computed using the value of -\texttt{combination\_size}. Then we can compute \texttt{o1} and \texttt{o2} +variable offset is computed using the value of +combination\_size. Then we can compute o1 and o2 representing the indexes of the other threads whose results are used by the -current one. In this algorithm, we consider that a 32-bits xor-like PRNG has +current one. In this algorithm, we consider that a 32-bit xor-like PRNG has been chosen. In practice, we use the xor128 proposed in~\cite{Marsaglia2003} in which unsigned longs (64 bits) have been replaced by unsigned integers (32 bits). @@ -397,7 +396,7 @@ array\_comb1, array\_comb2: Arrays containing combinations of size combination\_ \KwOut{NewNb: array containing random numbers in global memory} \If{threadId is concerned} { - retrieve data from InternalVarXorLikeArray[threadId] in local variables including shared memory and x\; + retrieve data from InternalVarXorLikeArray[threadIdx] in local variables including shared memory and x\; offset = threadIdx\%combination\_size\; o1 = threadIdx-offset+array\_comb1[offset]\; o2 = threadIdx-offset+array\_comb2[offset]\; @@ -407,9 +406,9 @@ array\_comb1, array\_comb2: Arrays containing combinations of size combination\_ shared\_mem[threadId]=t\; x = x\textasciicircum t\; - store the new PRNG in NewNb[NumThreads*threadId+i]\; + store the new PRNG in NewNb[NumThreads*threadIdx+i]\; } - store internal variables in InternalVarXorLikeArray[threadId]\; + store internal variables in InternalVarXorLikeArray[threadIdx]\; } \end{small} \caption{Main kernel for the chaotic iterations based PRNG GPU efficient @@ -417,56 +416,64 @@ version\label{IR}} \label{algo:gpu_kernel2} \end{algorithm} -\subsection{Chaos Evaluation of the Improved Version} +\subsection{Chaos evaluation of the improved version} -A run of Algorithm~\ref{algo:gpu_kernel2} consists in an operation ($x=x\oplus t$) having +A run of Algorithm~\ref{algo:gpu_kernel2} consists of an operation ($x=x\oplus t$) having the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative system of Eq.~\ref{eq:generalIC}. That is, an iteration of the general chaotic iterations is realized between the last stored value $x$ of the thread and a strategy $t$ (obtained by a bitwise exclusive or between a value provided by a xor-like() call and two values previously obtained by two other threads). -To be certain that such iterations corresponds to the chaotic one recalled at the +To be certain that such iterations correspond to the chaotic one recalled at the end of Section~\ref{sec:dev}, we must guarantee that this dynamical system iterates on the space $\mathcal{X} =\mathds{B}^\mathsf{N} \times \mathcal{P}\left(\llbracket 1, 2^\mathsf{N} \rrbracket\right)^\mathds{N}$. The left term $x$ obviously belongs to $\mathds{B}^ \mathsf{N}$. -To prevent from any flaws of chaotic properties, we must check that the right -term (the last $t$), corresponding to the strategies, can possibly be equal to any +To prevent any flaws of chaotic properties, we must check that the right +term (the last $t$ in Algorithm~\ref{algo:gpu_kernel2}), corresponding to the strategies, can possibly be equal to any integer of $\llbracket 1, 2^\mathsf{N} \rrbracket$. -Such a result is obvious, as for the xor-like(), all the -integers belonging into its interval of definition can occur at each iteration, and thus the +Such a result is obvious; as for the xor-like(), all the +integers belonging to its interval of definition can occur at each iteration, and thus the last $t$ respects the requirement. Furthermore, it is possible to prove by an immediate mathematical induction that, supposing that the initial $x$ is uniformly distributed, %(it is provided by a cryptographically secure PRNG), -the two other stored values shmem[o1] and shmem[o2] are uniformly distributed too, +the two other stored values shmem[o1] and shmem[o2] are uniformly distributed too (this is the induction hypothesis), and thus the next $x$ is finally uniformly distributed. Thus Algorithm~\ref{algo:gpu_kernel2} is a concrete realization of the general chaotic iterations presented previously, and for this reason, it satisfies the -Devaney's formulation of a chaotic behavior. +Devaney's formulation of chaotic behavior. \section{Experiments} \label{sec:experiments} Different experiments have been performed in order to measure the generation -speed. We have used a first computer equipped with a Tesla C1060 NVidia GPU card +speed. We have used one computer equipped with a Tesla C1060 NVIDIA GPU card and an Intel Xeon E5530 cadenced at 2.40 GHz, and a second computer equipped with a smaller CPU and a GeForce GTX 280. All the cards have 240 cores. +\begin{figure}[htpb] +\begin{center} + \includegraphics[scale=0.65]{Chapters/chapter18/figures/curve_time_xorlike_gpu.pdf} +\end{center} +\caption{Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG.} +\label{fig:time_xorlike_gpu} +\end{figure} + In Figure~\ref{fig:time_xorlike_gpu} we compare the quantity of pseudorandom numbers generated per second with various xor-like based PRNGs. In this figure, the optimized -versions use the {\it xor64} described in~\cite{Marsaglia2003}, whereas the naive versions +versions use the xor64 described in~\cite{Marsaglia2003}, whereas the naive versions embed the three xor-like PRNGs described in Listing~\ref{algo:seqCIPRNG}. In order to obtain the optimal performances, the storage of pseudorandom numbers -into the GPU memory has been removed. This step is time consuming and slows down the numbers +to the GPU memory has been removed. This step is time-consuming and slows down the numbers generation. Moreover this storage is completely useless, in case of applications that consume the pseudorandom numbers directly after they have been generated. We can see that when the number of threads is greater -than approximately 30,000 and lower than 5 million, the number of pseudorandom numbers generated +than approximately 30,000 and less than 5 million, the number of pseudorandom numbers generated per second is almost constant. With the naive version, this value ranges from 2.5 to 3GSamples/s. With the optimized version, it is approximately equal to 20GSamples/s. Finally we can remark that both GPU cards are quite similar, but in @@ -475,13 +482,7 @@ should be of better quality. As a comparison, Listing~\ref{algo:seqCIPRNG} leads to the generation of about 138MSample/s when using one core of the Xeon E5530. -\begin{figure}[htbp] -\begin{center} - \includegraphics[scale=0.65]{Chapters/chapter18/figures/curve_time_xorlike_gpu.pdf} -\end{center} -\caption{Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG} -\label{fig:time_xorlike_gpu} -\end{figure} + @@ -499,8 +500,7 @@ In this chapter, a PRNG based on chaotic iterations is presented. It is prov chaotic according to Devaney. Efficient implementations on GPU using xor-like PRNGs as input generators have shown that a very large quantity of pseudorandom numbers can be generated per second (about 20Gsamples/s on a Tesla C1060), and -that these proposed PRNGs succeed to pass the hardest battery in TestU01, namely -the BigCrush. +that these proposed PRNGs succeed in passing the hardest battery in TestU01, namely, the {\it BigCrush}. diff --git a/BookGPU/Chapters/chapter18/figures/curve_time_xorlike_gpu.pdf b/BookGPU/Chapters/chapter18/figures/curve_time_xorlike_gpu.pdf index 2437d2e19e4bb599ec97bf0c340742815ccff97f..645e5e9def62a525a76a8cf71224439bd260f714 100644 GIT binary patch delta 5269 zcmb7HXHZmGw^fj+L=mOQNn&d!ph->6QIRM?GKl2VC~$=)2azl}gNh`{ARr@)Yu4J4I`4ok%BxsUNCEb35c!K+p_Tr78)_uo`+pCr@<9bf-Uf+_dIiRd&f zs~HC9%4-_u*#1t?HGJ)2-kEx^%un>&76@#wY6wjM60OiTz)}uF4CCpqWdbwV>wp;X ztmvo8RWbN$4X+Gp>}5ve5*gCX^77TaLr! zI`M_x7Cw+;QggKw5RV}GjG7m**;0)GFmgS5jU%h zEo(hAI;4Cz(@)B@D@t^Z z>%VSE?yr?JcZ?pi9Q)4#2UzyA6-*=gkoaux`+{NjN_d?EkCs1Unca{jM>iyyA<`~S&IoZV&zrkkB%AR_1kKt&c^25}KXxY7m8s(y4 z5DAUbm~`2_^U7txVi87oSyi!PY!Q`Hxm&-Hx&lquK}A8yq@%NU)i{f(%n(v~MWCVK zbZ{JD^`jTZ^a#5Fpgz`yd}?N*90El(Q7Fa08SrkCkI$be9wL*OC=b02x2`Es!x?I^ zx^A>yE2q~;;u@)xq-m5Ywh#X{8L|gT`p+Aol{yag{W8d=?AV?F!%{Vfg}HY$pzu~_^Y1tn zHuu%mQKXlQ6U(mw?eB9>G(cqb?moCN@r=x_ybZc=l+8?M(Bp3#kYUvjXZ5b&!}wh9t?P1qQ)I!u zfKf%EnneRv%Ho{pD11HM*2Tut%fr^vneum)h$W#Sh9gC*r%B#i0mM+Kzgp-_eS@nH z^bE&ZITvSyxW@3x4-jf)`sTd~y75H4%z-oH42pD|L?TyunFU`&)h2UG9CSY}qs%87 zawHL6AWlvlcq^-*xfGY-SzRWRGJrnUD>Is2Rz}4VKn%VZDCC-rC;&;zCl}#l>Y0+u3%(eWbr=SNLWz`dBSU zJ}o)xjqXxoUjSiP-BvkDO3OGiD_clMTT8zXBonP=00`Fgp23rtCMS(aJe=5>8>`+)L5%(RPtF50u+mUPww9fpn%s z)ckxM;|)zK7g`iDY@8HFN{H({KrSgO=|;a+6-+l#G1h}V5Wb<}r-yn#w4_m1a>`HE zn?sqK3A~mSj4;tA(JLRJ6pTsNGQLmrm|7$?T_sI#N4J_E+IeqGs)hjzG-R#QPmudi zlxIw&`&;iBIS817Ss>n`V9^%KD5c%}>HM2DRApA0w_J-O*R0K}sD-U^bfPm-AZ7Tk zU*An^HW>GLRj(Zm)5sFTYCmp`lAtx(8eDOnz^y|XV~-}3DR`cgYP19Q>9nA9XYwp1 ziB{lvg*FBLZLYlYzV=Gc0$dDTT@VvGb6I~Qp!CWFWrkWVi>zV@B9a5k!;-F~sMx_q zv?zp0BPaNAd38J;0uzNT?_ilfA7X+%O&rE4=MgAAPL0f)^cD+}O|(xQ^$?hih~@48 z0JqQkfb4{uX4y8PX-sSLmBNo{k+i<0-mt4@DN>f@BPSkJ=^$wVEPr0R>$+*J@@gn*`oxDLg*j3#qrUv;kp+yA5G`;Cxa(w@ zY7l{`3N1XXf6i<}${y1h&RORIe)B`SSkug_pr-he!18S#|IL!=I0eDvX+HJ>Lhp%B|L`O^MBykBh?)KU1K5ehdg;~{=5%$Zb zIy{mh`JXREZSI6$oCQA9>edqQg&y|78(9syaq&^#Fv7;yF4HIJ8zdxlv+LPCIY+b$ z8V%xRCXK{=6h)sB2tiHUdNyW;u?iz|#=P6NjNn(s{kj;vR^hy^0Gz4ZX6`c9j9hZI ze7&A%4H@x~S;}md_RWCGB;6a>Yx_sgHz}*d{LD??c4dyE+BgJb&&^QND?bM0P>_j4 zzX|h2O-xRn-NxIkhf(UogLs+Tp{NDoP0;d0xphvCV(shJy+tv5Z5HWct*c4v;N??x zPiFKtm(cNqfr>2xpl2Ci@=&!!Y+(9`B|>2LHrsa(Bl2oCnvc!lHbQGd$r%X&bQ_f} zmu4>aQ6KELj$voQWA5YyJ{i30@-dr~`H5}M!Ghb27$#ZFw6KxRWA@P<6O8mpWcvKm zc@-&zpR?pygP#uaYU6|(=}o&7KG&9Um8||eT$PZSNj~mZlm+mSIVt3G(oBYXv}R>3 z=(q#m^Go{7uk36)J}Z{#bZf16&P@TM=bc+61F`y!Z~4!qqKXRS&!lFyJuojszkZS! zT&PbgKqqyFLuFJ^N^@>(6EnN*WLrkD+Pzp?JDCne2>Z8o*af{dgg4-fR6n z?492^oABlRJT@S=)K7Eo^!hN-J>hR?!P43vo7>e((x*G=BY3QN~^Yz z&Ea$>=X+cdC3Tt`q#irhNZoZigqFycM_1FgAi6uf%~cuz7GO_5ehMDN*u*D!eZY=KeP@hHCU8{yj$sYDmGL!g5 z?GWDVa*@EB3$|D_vmCGdlhymvOD9i6G5)^Jg1SpWVmE*g2LA85GrRc(wiY{%j|_3i zV;DNf^*6vEW_Y%?690YQ@Wo7c+P)ja^%X;?de>A-1aI1n@3naM=|X?6H{CI)-H(c> zD;0urv$S^uKehG&W&45>0--Dmb*|Ow{8=`O@Q_H-6&L>A{pVku|rU63c z(rtJ>y7f@nvZo~og60UCMudlh^fGOh+8w@M+-3!OGOy-?B+f>*;m`Pb+dr)0!)L4T z%-CZYGv;)%1)66)C--5Zk(qb~YFU&gYZkavK+4Q*(K_jK)9oS?4KPP|YV^ANm%9vj zcE(^Z4PH>;fVOM^VbJ4^Z3eTu-=cOYZ6MuhD#$j# zd(xe95@j@X(C6euW~O>3@q7tBs}CDuv)o}}`|u51vvRyzHf3U6r?tCoST;v*K(Pz8 z78bnub?`IBe_7|9wVJ?5uuIq{Xaw=iFR$KC{@CLFq94uNjp@$IWJkLl7e7ufY&#ec zxAvhh8&TA>10QjG%GGnE5mRrRH7F?t6wzO~s{wB!@h<=?S!7a%Y@D7;lSp+)Xax_k zVZtefK4Gj}%OLFF9VBpL*_1k8I;et%q%Fn?t^Q$=tR5v5lz%^s-WI zmTa7BrmYyFL`6~$D}UTMH_C6kJ~v0txZcEdxZJn<@F;t4TsoA1y3DeEeS!3K!b=9# zU2XxMP8vcU4WX!t7}vcIGW}YewCUfhH=@>|eWpE_R8u+{eDymHc_&1I4bQ<){w<-B z6EP6@K8ydEJhGDPAyv+D5eN1H@LY%+0vmF#6VYv0{@Q!b8p*{hDqL%vLJ;~azqyop zmv7@a%KTEeN~qf{L)B|H3Vsn(mDR3l+2&=sp?GDs#I{;Dkac`jrz#$NuWQPOQqQ_?C2 zAGH^Cjt)>w|H}Eor~=Pmq|CBn#p@hzh$$`Qs1Ym-GsuY5G`twZ`xg%RlPaBEjU~^z znpnapPb7}0-e5#t7V!3Vw2`ocBJAKIHb^i`94QKhLTzoqklzaox3;mif(~jxR zWzocBChdRWMh24q7wmsENp%%Slt}%L7Z9MltML1;%*)Z$MbXmBmj93O)V-f@z#zZR zACp00zY8e*H&4se=1+>E#2)}e3Z!OqKJQD2ytj4f%P^Z_74fDn5gJKB#@$F|Bb<5NXUO z760=t&Hu_Sf`mX5-?2%V$;(3(;0R@iJVY4*QGgbae;HqL(SmXyYOXQ4*c#Wt348h9HdhC2=OQjFA;bBH zcI3*l+&?Jj^x9gsqoQdcICiMHC>y(VUiha6jnBLZiF4GZfBP7Tw|??>St zK9A{j7ql>4a&Xq~X^yS14!-Db16z78oo!pqeN%Q)@N%8joRwftzO}fu&;xvT& zq(7RTJ!ZljPBd3lPD~m`1}-x_&CwE(W)MOQ$q?t>zfz2>(OcN*vE~lDLi!Lxc-6ni z5wW?{SK4|WfXWEQbf-PaFW_DCxF97eWCF2GaE`fWA;|( z6@u0%mm_6WibK@?ENi1mdzkA)JH#VPQJ*!lZzh{(nnJ$XzPk_5E*dP1IAEMjywwe@ z(~4xQZPy7lsBKrmA*c3hH9Qk08It#M1AWAL`xf2O)w2UJpOpmEgdDIU^yNRn1*0ah zfAuP>e3dh}0O(6zz7|iWjdk`(V(hD^Qgwc<^E|u>6P6YyyI15>AdY4lQU#7h!yI0#N0Hz+BP zt1S+8cVM5^eD{C_{VU=D=gvLPbYorepnmg-rNkcg{uA?lPR5~IU8!QT@*K;q5yihm zXmu|!!)@J`^M$khqfi*;6mWX2-#5@}N|Cc~Wp}%EZe?kk{e5c( zBL$r?64aexm}}=p=vr8ez;1oH-bawl^K_=UnjC`P!I@@&$(y5VXEp^bCSe8}(cBvUh zy6#E6;A*E$?Sn7Ug_b``{Bysu5>pq9D->D=Rdoo5jxs?C8}e-SbG=c84|`2;^PK2k zJM0I*8t?;I*%nI7Z}(+m+D12+63ZQbDA+S?5bTOjlvwe#)y2_#Nsg_(b0>MUg474(uJnm1L$2N@UHP0ns6CBxKLhrufKYzGCFh{Ek{ew>iUt#RAx< zrq$rCBM&RSl+P7XCsUFtI!RmarBQ|nFm#g~nU)hYjJU$5vB*}_S;H+^*_2e|b@TuU zMUwGkQ}WnQ#_$yY<3kzBSMa|=*%el=pjw!%gfdkRepB&^1n%_BS+UUWb z6d26Z6FAkSF|=R$Rn&k2`)IlwS3`Un%`lec#44hKd++P@A~jAj4ZJ{Ghcq2lO&PB0 z`6!T$jLeyj52}4<9<%;^|895D?%bOcWeHatb)iQ}Oht8-`p4;jobrIe=TdJ<`qWL- z@+6$zQk##)zFCCK)-Vg!M%{m%QKd$W&qW|8(Mx=xfe(HneAeWQ8b)~kWh-~Gn=p_14@L~ z|5wbY83PeB!)CN{Bp|0ng2b;sKFF9ilq%|uXRz4rZS^^NE2 z=h08WQkg`A&rGdff))8;7zLrB>atEFLiuk*5;Sk<;xC>y+^Kk~$BscZ*dbCnTD<-%fDHl3l2=L>l-zm#rL;<;7IO;xe`fv;C^@o(v4Qxejv za|QF^GEfJUuZx-eN$oNPsk(sUIKxhS!OWVVaFl0uOTMZB5rZl|yD;BLIMhtnPak2x zzIfLy<4lnBb2=a+74!Z#;czn@V*R2o0O8mEVaciyLa&mwP4x&}sH75-)sytcwU|BfB3A4yOQ}R{ zQ6}2Yyllut=U4!`XMy) z#j(2axAIdl4S>*bBe$qyMYBa@ZfgJacBJbbQk{jo{`!aEQzJkLgEa0pmZ#x2oauCu zHJG81;o+h6L|w)t5ZbL>-{nxsoCib{ecw{#!q-WOmnsH}7+RbIbd=w~CHNZJ9;3M@ zny}lj5|ZcU7Z|lQ`%?veiCXz?S1_cd)y8xI_z<{Z^vj;{1Yg4{pGj*zM7CeatYPr| zN5(DjE|S3aQB>qR8i8E2klVd%O#3H3s`9=55lvk6CyO_4m;0cd*NXPmKSY(pqN&@k z)a*}RSl?hHCYi09G=1%7WRw!9b!-Slp$((mMt@N8-o}hqyqU2ky{{2ENAZ>Q>zk2a zlM>eJ1l7UCB8fCfQ6tA$U2fgnYj(OMFB!0k-^{d;aVwbx91b(zcftiE>5;R(VBzwo zj`9b;)Z6Pn+1z!{8NU%wOnWp!!3v-BX}IX^9fXruR(ba~ehJ)*Qr3(}%CZch%?yxTLjBZyHmx zSwyeT;kt6;hZFV$thKe&!{t2H5H)ezBInXHv^;M_yI&Bu(b`__RBvzV4!b-U(w-t@ z^*k+gi#b9~sL1>3G=!?iOBaS0Q#%aUB z@9~xRgnj8BFF!m~%DtA1Y*jPoH`Am?1(U|vQ3nA4D)C)TjRVD8a#SxLR6KlrxXE)- zsa^Ku+me%ntzkN+9B=S+l=yeyIA5V1>`0Cb#VbnP^v@@k5YDz&s_uAAf z^=%KAexAoMv|kvWn^|98>b~~gb+0QT*jxQwS8WkM~fwUTiMjM;_=Hypm6ks zMZ?U})(Vh|d97RCRl+l`dEj2X+vqF&3w~#(4X%3{enUz=lwJXc+XK3pW(HP|R#PAX zF>g=uh&A^Zy)N2kNYW~&zkgiVMaf+nVD6<)<-I@rS#z3p9mGG|W@k=CZZkGd;Coo& z%5PET>6Im6%P~gTBxgOD88kay+kRRy#Q!Bm?4+G?V#GQaFIr>C-f@a7*$It=!jw1I zdR0*+j*9mo<`QS&j^P(8*>iXXt-l5W-`6L%* z()ab+c%YNjB%+}Yx)nvWOi&QCP1cYh@7H2`^isWBRRv?^m$foTVBn)S)pL_`rlyg( zG>wgZtSj}L@PuMp1#T%fx-dsdY2ZXO;4LZ5O+-8s_Z#ikXmL)Di-!HPZcNWI0Xex5 zHC9z`cw1UU-A+XR{ZnRSVPJ6GlU@=>#QpW#qon0g5xNC8$5C@(HpNPJH$XlM9NV_l z5poe+qoihWH98^uX+@(!OtubvWESb@tkY$^uZyRyjKKkqJ^GCogt=4R+$ zbZR!vPB#^0h!m2x+T7C1CdIsKMA_7IE)}!aQA3vItY;;KDB_~3p3vR}i%g+v=4&;M zm-S*;0)IS<@V#Lf|Ga_Q@+>3}X9(V_+Zr9)n6(tb3n5aYE6el=;UAXItk?5qE+cR) zrbzJ6LyhaCQnqiYDC`OZL~CF)0BXLHu%BD^?69~(QD(Q3Zz0(%UKk|hqCfbwxF@LX>jZ$1j9s zel_ofpMD~2KDXhX*lEIp4Je0BC`RJR!~DPm19E1(Pm8^kkHTg(33FLhirLouP`TLx zAN3^gH=~wIl61nSk1+Qr8KR;+n3EXaKHNhmLq8T((|VUx+p;w37G7>#Lp76YSvJ`U z6@3p5+~cBtAv!;RO-T$8k(bhZ6M9^;>of3nQ=c$*VO=qyYJi`VCBc_qm*=E5+R8S_ zH`QP=-h{phH5tM+b<}-}_%wWu!T-8so|@ zYIwM!C1;yH^K$RyiEl8E;m?vZlj0e66HWFd+eQ1i0;K{HQv9{L-75R-Oct$W=2q7s z{gbfD%~y|k4i@p>UvPzlP55=d6uT3|-o@Nz?=L)A2-w4@EYe$+eZ%a-N{Elkth&x7 zayVEX*n86mJQrz9X~1)S@Xuqcc-2fidt!;uZg2A6rvvx_8(-g6eU5oX&O>)QFMZ49 zK2&w~{)gzz#0XV_FA5{@HEf+>y>_fid zhw%SZIW~c@$`f8O#($?XBHMmsCo0U;JJc2&@Kd+Y?he`MbNA5aAQNiwSVXSg);e$3 z{YbXX;Lgk_E??R0fi7q4#aOaeM-UJCK0PSu<4o|4U>7|ucdTb4UPlLTn5d4tTqW|1 zy_BV*6M{YC6!?lpA<4+CG)Rj0j!4`23oY2jPcks?@cVI5=2DA6Z1oHuT^vka<4`7t zgM)bSY%I%Wj6v&LC8d#S+AJRvZW*14^z&yw>bi8b6=&)v9^|V6l_cwzm)h#Ozj9M{ zIA+DK)A8_nbtE*`QBS$ZN_2njni8yQ7bJ3X7hkcNvp6fg?IqCE%nxnzR_*Oen6KJU zSS*%#0w@h6gwF`HQQi~c)`(qD$KJtmZK-f=-JRm8Vl_5YzLT4kY?KnMWqdg_6Ohvq zK%#oC7-^PfiA!KqCX|*bpJs#;@Y&eO$k>38(qd8|Teuhq3dhgF`+sj* zvxpNwaWO19|85WotMb1S{#)ziwXD*FnBUV10VGte{#R&c5BJ+PXa~XH^XPc^0Ksse z*Uv=ne$@QAold(vbh;K+@8Z z|KOw~WpD(Xw=nR3v;e{2(0|C`aH;>~z+joHnE!h`2oC;-4g{C_2M3mh!2UQ({Xe`* z!9g(GM^1SQFdQxofx@od6$GxPCZnVTmr(^t--f`Hlt5spk{Uw(|5aE35D0)5+Qt*@ U>*;_5z@%Vc06)K~t{ULK0N!(>od5s; -- 2.39.5