From 136b4f47b57133edcd5627342c6c721c861d507e Mon Sep 17 00:00:00 2001 From: couturie Date: Sun, 11 Dec 2011 17:20:29 +0100 Subject: [PATCH] petites corrections --- prng_gpu.tex | 80 +++++++++++++++++++++++++--------------------------- 1 file changed, 39 insertions(+), 41 deletions(-) diff --git a/prng_gpu.tex b/prng_gpu.tex index c646316..4feac7c 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -7,7 +7,7 @@ \usepackage{amscd} \usepackage{moreverb} \usepackage{commath} -\usepackage{algorithm2e} +\usepackage[ruled,vlined]{algorithm2e} \usepackage{listings} \usepackage[standard]{ntheorem} @@ -856,7 +856,9 @@ $$ -\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label=algo:seqCIPRNG} + +\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iteration\ +s},label=algo:seqCIPRNG} \begin{lstlisting} unsigned int CIPRNG() { static unsigned int x = 123123123; @@ -876,7 +878,6 @@ unsigned int CIPRNG() { - In Listing~\ref{algo:seqCIPRNG} a sequential version of the proposed PRNG based on chaotic iterations is presented. The xor operator is represented by \textasciicircum. This function uses three classical 64-bits PRNGs, namely the @@ -1008,18 +1009,18 @@ array\_comb1, array\_comb2: Arrays containing combinations of size combination\_ o2 = threadIdx-offset+array\_comb2[offset]\; \For{i=1 to n} { t=xor-like()\; - t=t $\wedge$ shmem[o1] $\wedge$ shmem[o2]\; + t=t\textasciicircum shmem[o1]\textasciicircum shmem[o2]\; shared\_mem[threadId]=t\; - x = x $\wedge$ t\; + x = x\textasciicircum t\; store the new PRNG in NewNb[NumThreads*threadId+i]\; } store internal variables in InternalVarXorLikeArray[threadId]\; } -\caption{main kernel for the chaotic iterations based PRNG GPU efficient -version} -\label{algo:gpu_kernel2} +\caption{Main kernel for the chaotic iterations based PRNG GPU efficient +version\label{IR}} +\label{algo:gpu_kernel2} \end{algorithm} \subsection{Theoretical Evaluation of the Improved Version} @@ -1248,13 +1249,13 @@ very slow and only usable for cryptographic applications. The modulus operation is the most time consuming operation for current GPU cards. So in order to obtain quite reasonable performances, it is -required to use only modulus on 32 bits integer numbers. Consequently +required to use only modulus on 32-bits integer numbers. Consequently $x_n^2$ need to be lesser than $2^{32}$, and thus the number $M$ must be lesser than $2^{16}$. So in practice we can choose prime numbers around -256 that are congruent to 3 modulus 4. With 32 bits numbers, only the +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 indistinguishable bits is lesser than or equals to -$log_2(log_2(M))$). In other words, to generate a 32 bits number, we need to use +$log_2(log_2(M))$). In other words, to generate a 32-bits number, we need to use 8 times the BBS algorithm with possibly different combinations of $M$. This approach is not sufficient to be able to pass all the TestU01, as small values of $M$ for the BBS lead to @@ -1273,9 +1274,9 @@ character \& is for the bitwise AND. Thus using \&7 with a number gives the last 3 bits, providing so a number between 0 and 7. \item Secondly, after the generation of the 8 BBS numbers for each thread, we -have a 32 bits number whose period is possibly quite small. So +have a 32-bits number whose period is possibly quite small. So to add randomness, we generate 4 more BBS numbers to -shift the 32 bits numbers, and add up to 6 new bits. This improvement is +shift the 32-bits numbers, and add up to 6 new bits. This improvement is described in Algorithm~\ref{algo:bbs_gpu}. In practice, the last 2 bits of the first new BBS number are used to make a left shift of at most 3 bits. The last 3 bits of the second new BBS number are add to the @@ -1296,7 +1297,7 @@ variable for BBS number 8 is stored in place 1. in global memory\; NumThreads: Number of threads\; array\_comb: 2D Arrays containing 16 combinations (in first dimension) of size combination\_size (in second dimension)\; - +array\_shift[4]=\{0,1,3,7\}\; } \KwOut{NewNb: array containing random numbers in global memory} @@ -1307,19 +1308,21 @@ array\_comb: 2D Arrays containing 16 combinations (in first dimension) of size o1 = threadIdx-offset+array\_comb[bbs1\&7][offset]\; o2 = threadIdx-offset+array\_comb[8+bbs2\&7][offset]\; \For{i=1 to n} { - t<<=4\; + t$<<$=4\; t|=BBS1(bbs1)\&15\; ...\; - t<<=4\; + t$<<$=4\; t|=BBS8(bbs8)\&15\; - //two new shifts\; - t<<=BBS3(bbs3)\&3\; - t|=BBS1(bbs1)\&7\; - t<<=BBS7(bbs7)\&3\; - t|=BBS2(bbs2)\&7\; - t=t \^{ } shmem[o1] \^{ } shmem[o2]\; + \tcp{two new shifts} + shift=BBS3(bbs3)\&3\; + t$<<$=shift\; + t|=BBS1(bbs1)\&array\_shift[shift]\; + shift=BBS7(bbs7)\&3\; + t$<<$=shift\; + t|=BBS2(bbs2)\&array\_shift[shift]\; + t=t\textasciicircum shmem[o1]\textasciicircum shmem[o2]\; shared\_mem[threadId]=t\; - x = x \^{ } t\; + x = x\textasciicircum t\; store the new PRNG in NewNb[NumThreads*threadId+i]\; } @@ -1330,24 +1333,19 @@ array\_comb: 2D Arrays containing 16 combinations (in first dimension) of size \label{algo:bbs_gpu} \end{algorithm} -In Algorithm~\ref{algo:bbs_gpu}, $n$ is for the quantity -of random numbers that a thread has to generate. -The operation t<<=4 performs a left shift of 4 bits -on the variable $t$ and stores the result in $t$, and -$BBS1(bbs1)\&15$ selects -the last four bits of the result of $BBS1$. -Thus an operation of the form $t<<=4; t|=BBS1(bbs1)\&15\;$ -realizes in $t$ a left shift of 4 bits, and then puts -the 4 last bits of $BBS1(bbs1)$ in the four last -positions of $t$. -Let us remark that to initialize $t$ is not a necessity as we -fill it 4 bits by 4 bits, until having obtained 32 bits. -The two last new shifts are realized in order to enlarge -the small periods of the BBS used here, to introduce a kind of variability. -In these operations, we make twice a left shift of $t$ of \emph{at most} -3 bits and we put \emph{exactly} the 3 last bits from a BBS into -the 3 last bits of $t$, leading possibly to a loss of a few -bits of $t$. +In Algorithm~\ref{algo:bbs_gpu}, $n$ is for the quantity of random numbers that +a thread has to generate. The operation t<<=4 performs a left shift of 4 bits +on the variable $t$ and stores the result in $t$, and $BBS1(bbs1)\&15$ selects +the last four bits of the result of $BBS1$. Thus an operation of the form +$t<<=4; t|=BBS1(bbs1)\&15\;$ realizes in $t$ a left shift of 4 bits, and then +puts the 4 last bits of $BBS1(bbs1)$ in the four last positions of $t$. Let us +remark that to initialize $t$ is not a necessity as we fill it 4 bits by 4 bits, +until having obtained 32-bits. The two last new shifts are realized in order to +enlarge the small periods of the BBS used here, to introduce a kind of +variability. In these operations, we make twice a left shift of $t$ of \emph{at + most} 3 bits, represented by \texttt{shift} in the algorithm, and we put +\emph{exactly} the \texttt{shift} last bits from a BBS into the \texttt{shift} +last bits of $t$. It should be noticed that this generator has another time the form $x^{n+1} = x^n \oplus S^n$, where $S^n$ is referred in this algorithm as $t$: each iteration of this -- 2.39.5