From: couturie <couturie@carcariass.(none)>
Date: Sun, 18 Sep 2011 08:19:23 +0000 (+0200)
Subject: amelioration de la description des algos
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/3c253b8871482ed4e74d60ab23edaf08052e7c72

amelioration de la description des algos
---

diff --git a/prng_gpu.tex b/prng_gpu.tex
index dc91965..fa71e5b 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -758,7 +758,8 @@ the larger the number of threads is,  the more local memory is used and the less
 branching  instructions are  used (if,  while, ...),  the better  performance is
 obtained  on  GPU.  So  with  algorithm  \ref{algo:seqCIprng}  presented in  the
 previous section, it is possible to  build a similar program which computes PRNG
-on  GPU. 
+on  GPU. In  the CUDA  [ref] environment,  threads have  a  local identificator,
+called \texttt{ThreadIdx} relative to the block containing them.
 
 
 \subsection{Naive version for GPU}
@@ -782,22 +783,23 @@ variables.
 \KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like PRNGs in global memory\;
 NumThreads: Number of threads\;}
 \KwOut{NewNb: array containing random numbers in global memory}
-\If{threadId is concerned} {
-  retrieve data from InternalVarXorLikeArray[threadId] in local variables\;
+\If{threadIdx is concerned by the computation} {
+  retrieve data from InternalVarXorLikeArray[threadIdx] in local variables\;
   \For{i=1 to n} {
     compute a new PRNG as in Listing\ref{algo:seqCIprng}\;
-    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]\;
 }
 
 \caption{main kernel for the chaotic iterations based PRNG GPU naive version}
 \label{algo:gpu_kernel}
 \end{algorithm}
 
-According to  the available  memory in the  GPU and  the number of  threads used
-simultenaously, the number of random numbers that a thread can generate inside a
-kernel     is     limited,      i.e.      the     variable     \texttt{n}     in
+Algorithm~\ref{algo:gpu_kernel}  presents a naive  implementation of  PRNG using
+GPU.  According  to the available  memory in the  GPU and the number  of threads
+used simultenaously,  the number  of random numbers  that a thread  can generate
+inside   a    kernel   is   limited,   i.e.    the    variable   \texttt{n}   in
 algorithm~\ref{algo:gpu_kernel}. For example, if  $100,000$ threads are used and
 if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)}
 then   the  memory   required   to  store   internals   variables  of   xor-like
@@ -806,7 +808,8 @@ and  random  number of  our  PRNG  is  equals to  $100,000\times  ((4+5+6)\times
 2+(1+100))=1,310,000$ 32-bits numbers, i.e. about $52$Mb.
 
 All the  tests performed  to pass the  BigCrush of TestU01  succeeded. Different
-number of threads have been tested upto $10$ millions.
+number of threads, called \texttt{NumThreads} in our algorithm, have been tested
+upto $10$ millions.
 
 \begin{remark}
 Algorithm~\ref{algo:gpu_kernel}  has  the  advantage to  manipulate  independent
@@ -820,27 +823,37 @@ for all the differents nodes involves in the computation.
 
 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. using  less than 3 xor-like  PRNGs. The solution consists  in comuting only
-one xor-like PRNG  by thread, saving in into shared  memory and accessing result
-of some other threads in the same block of threads.
+i.e. using less  than 3 xor-like PRNGs. The solution  consists in computing only
+one xor-like PRNG by thread, saving  it into shared memory and 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 permutation array which
+contains  the indexes  of  all threads  and  for which  a  permutation has  been
+performed.  In Algorithm~\ref{algo:gpu_kernel2}, 2 permutations 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}
+which represent the indexes of the  other threads for which the results are used
+by the  current thread. In  the algorithm, we  consider that a  64-bits xor-like
+PRNG is used, that is why both 32-bits parts are used.
 
 \begin{algorithm}
 
 \KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs in global memory\;
 NumThreads: Number of threads\;
-tab1, tab2: Arrays containing permutations\;}
+tab1, tab2: Arrays containing permutations of size permutation\_size\;}
 
 \KwOut{NewNb: array containing random numbers in global memory}
 \If{threadId is concerned} {
   retrieve data from InternalVarXorLikeArray[threadId] in local variables\;
-  offset = threadId\%32;
+  offset = threadIdx\%permutation\_size\;
+  o1 = threadIdx-offset+tab1[offset]\;
+  o2 = threadIdx-offset+tab2[offset]\;
   \For{i=1 to n} {
     t=xor-like()\;
     shared\_mem[threadId]=(unsigned int)t\;
-    x = x$\oplus$ (unsigned int) t\;
-    x = x$\oplus$ (unsigned int) (t>>32)\;
-    x = x$\oplus$ shared[tab1[offset]]\;
-    x = x$\oplus$ shared[tab2[offset]]\;
+    x = x $\oplus$ (unsigned int) t\;
+    x = x $\oplus$ (unsigned int) (t>>32)\;
+    x = x $\oplus$ shared[o1]\;
+    x = x $\oplus$ shared[o2]\;
 
     store the new PRNG in NewNb[NumThreads*threadId+i]\;
   }