X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/26aa4e0cf2939580eae07e8bbad140d527f47234..80c5c05c07373d50d1af355c7a25a336a12f7d73:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 0279f03..00752c7 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -884,16 +884,19 @@ stringent BigCrush battery of tests~\cite{LEcuyerS07}.
 \section{Efficient PRNGs based on Chaotic Iterations on GPU}
 \label{sec:efficient PRNG gpu}
 
-In  order to take benefits  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, ...),  the better the performances on GPU is.  
-Obviously, having these requirements in mind, it is possible to  build a program similar to 
-the one presented in Algorithm  \ref{algo:seqCIPRNG}, which computes pseudorandom numbers
-on   GPU.  
-To do so, we must firstly recall that in
- the   CUDA~\cite{Nvid10}  environment,   threads  have   a  local
-identifier called \texttt{ThreadIdx}, which is relative to the block containing them.
+In order to  take benefits 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,  ...),  the  better the  performances  on  GPU  is.
+Obviously, having these requirements in  mind, it is possible to build
+a   program    similar   to    the   one   presented    in   Algorithm
+\ref{algo:seqCIPRNG}, which computes  pseudorandom numbers on GPU.  To
+do  so,  we  must   firstly  recall  that  in  the  CUDA~\cite{Nvid10}
+environment,    threads    have     a    local    identifier    called
+\texttt{ThreadIdx},  which   is  relative  to   the  block  containing
+them. With  CUDA parts of  the code which  are executed by the  GPU are
+called {\it kernels}.
 
 
 \subsection{Naive Version for GPU}
@@ -965,13 +968,13 @@ 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
 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 permutation array that
-contains  the indexes  of  all threads  and  for which  a  permutation has  been
+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 permutations arrays are used.
+In Algorithm~\ref{algo:gpu_kernel2}, two combination arrays are used.
 The    variable   \texttt{offset}    is    computed   using    the   value    of
-\texttt{permutation\_size}.   Then we  can compute  \texttt{o1}  and \texttt{o2}
+\texttt{combination\_size}.   Then we  can compute  \texttt{o1}  and \texttt{o2}
 representing the indexes of the  other threads whose results are used
 by the  current one. In  this algorithm, we  consider that a  64-bits xor-like
 PRNG has been chosen, and so its two 32-bits parts are used.
@@ -983,12 +986,12 @@ This version also can pass the whole {\it BigCrush} battery of tests.
 \KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs
 in global memory\;
 NumThreads: Number of threads\;
-tab1, tab2: Arrays containing permutations of size permutation\_size\;}
+tab1, tab2: Arrays containing combinations of size combination\_size\;}
 
 \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\;
-  offset = threadIdx\%permutation\_size\;
+  offset = threadIdx\%combination\_size\;
   o1 = threadIdx-offset+tab1[offset]\;
   o2 = threadIdx-offset+tab2[offset]\;
   \For{i=1 to n} {
@@ -1232,18 +1235,95 @@ prime numbers  need to be congruent  to 3 modulus  4. BBS is
 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 $x_n^2$ need to be
-less than  $2^{32}$ and the  number $M$  need to be  less 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  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(x_n))$). So  to generate a 32 bits  number, we need to  use 8 times
-the BBS algorithm with different combinations of $M$.
+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
+$x_n^2$ need  to be less than $2^{32}$  and the number $M$  need to be
+less 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
+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(x_n))$). So to generate a  32 bits number, we need to use
+8 times  the BBS  algorithm with different  combinations of  $M$. This
+approach is  not sufficient to pass  all the tests  of TestU01 because
+the fact  of having chosen  small values of  $M$ for the BBS  leads to
+have a  small period. So, in  order to add randomness  we proceed with
+the followings  modifications. 
+\begin{itemize}
+\item
+First we  define 16 arrangement arrays  instead of 2  (as described in
+algorithm \ref{algo:gpu_kernel2}) but only 2  are used at each call of
+the  PRNG kernels. In  practice, the  selection of  which combinations
+arrays will be used is different for all the threads and is determined
+by using  the three last bits  of two internal variables  used by BBS.
+This approach  adds more randomness.   In algorithm~\ref{algo:bbs_gpu},
+character  \& performs the  AND bitwise.  So using  \&7 with  a number
+gives the last 3 bits, so it provides a number between 0 and 7.
+\item
+Second, after the  generation of the 8 BBS numbers  for each thread we
+have a 32 bits number for which the period is possibly quite small. So
+to add randomness,  we generate 4 more BBS numbers  which allows us to
+shift  the 32 bits  numbers and  add upto  6 new  bits.  This  part is
+described  in algorithm~\ref{algo:bbs_gpu}.  In  practice, if  we call
+{\it strategy}, the number representing  the strategy, the last 2 bits
+of the first new BBS number are  used to make a left shift of at least
+3 bits. The  last 3 bits of the  second new BBS number are  add to the
+strategy whatever the value of the first left shift. The third and the
+fourth new BBS  numbers are used similarly to apply  a new left shift
+and add 3 new bits.
+\item
+Finally, as  we use 8 BBS numbers  for each thread, the  store of these
+numbers at the end of the  kernel is performed using a rotation. So,
+internal  variable for  BBS number  1 is  stored in  place  2, internal
+variable  for BBS  number 2  is  store ind  place 3,  ... and  internal
+variable for BBS number 8 is stored in place 1.
+\end{itemize}
+
+
+\begin{algorithm}
+
+\KwIn{InternalVarBBSArray: array with internal variables of the 8 BBS
+in global memory\;
+NumThreads: Number of threads\;
+tab: 2D Arrays containing 16 combinations (in first dimension)  of size combination\_size (in second dimension)\;}
+
+\KwOut{NewNb: array containing random numbers in global memory}
+\If{threadId is concerned} {
+  retrieve data from InternalVarBBSArray[threadId] in local variables including shared memory and x\;
+  we consider that bbs1 ... bbs8 represent the internal states of the 8 BBS numbers\;
+  offset = threadIdx\%combination\_size\;
+  o1 = threadIdx-offset+tab[bbs1\&7][offset]\;
+  o2 = threadIdx-offset+tab[8+bbs2\&7][offset]\;
+  \For{i=1 to n} {
+    t<<=4\;
+    t|=BBS1(bbs1)\&15\;
+    ...\;
+    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$\oplus$shmem[o1]$\oplus$shmem[o2]\;
+    shared\_mem[threadId]=t\;
+    x = x $\oplus$ t\;
+
+    store the new PRNG in NewNb[NumThreads*threadId+i]\;
+  }
+  store internal variables in InternalVarXorLikeArray[threadId] using a rotation\;
+}
+
+\caption{main kernel for the BBS based PRNG GPU}
+\label{algo:bbs_gpu}
+\end{algorithm}
+
+In algorithm~\ref{algo:bbs_gpu}, t<<=4 performs a left shift of 4 bits
+on the variable  t and stores the result  in t. BBS1(bbs1)\&15 selects
+the last  four bits of the result  of BBS1. It should  be noticed that
+for the two new shifts, we use arbitrarily 4 BBSs that have previously
+been used.
 
-Currently this PRNG does not succeed to pass all the tests of TestU01.
 
 
 \subsection{A Secure Asymetric Cryptosystem}
@@ -1263,8 +1343,7 @@ generate   a  huge   number   of  pseudorandom   numbers   per  second   (about
 20Gsamples/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.
+grid computing.
 
 
 
