From: couturie 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?ds=sidebyside;hp=50092af11c4cbab1c3048d46875f66476118537c 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]\; }