From ab8b9d20e04e131eb774c30874380721ca122b86 Mon Sep 17 00:00:00 2001
From: couturie <couturie@carcariass.(none)>
Date: Sun, 18 Sep 2011 20:00:44 +0200
Subject: [PATCH] ajout courbe
---
curve_time_gpu.pdf | Bin 0 -> 7239 bytes
curve_time_gpu.plot | 20 ++++++++++++++++++++
prng_gpu.tex | 37 +++++++++++++++++++++++++------------
time_gpu.txt | 13 +++++++++++++
4 files changed, 58 insertions(+), 12 deletions(-)
create mode 100644 curve_time_gpu.pdf
create mode 100644 curve_time_gpu.plot
create mode 100644 time_gpu.txt
diff --git a/curve_time_gpu.pdf b/curve_time_gpu.pdf
new file mode 100644
index 0000000000000000000000000000000000000000..bbc37162bd350fbb775d0078d233a3c68d1e4eb5
GIT binary patch
literal 7239
zcmb_hdpwle*Y8xP%Q&S-h2l}krFiCU+$Q(r9->^*n0c7V+?shXq;x9ulT_$NA}6|t
zl1rB<T}UZHh$5vTLW!bMdG|A@PM!CCe}9~LKAFAOUhBKov)0;c_FieaSlQ?i^vO8Q
zTiv@ea1;m+3H;aNOiW-0gdd2qAu6D_!ZsW(iijZChRZ+^D}*UvA#^%UjEWEj4<|Xi
zZ@;}@p}~ypZ~B)=nxV!u#nHQiwp=?8b**wTpT0Jzo3?{>hO1?}c~hhB<6~th(4OBd
z+xoQ5oy^tvc(d`LvOOGj)zm>fH~(Vfk;9Zorw2ZcH*FN{$T266RlFM1*`FD!EOvah
zdHv@v@1p2-aG2Ee;F}O$o&RA2sdTEMq2m2+SDnSBhRKf^;epMca&n$@Z%!$G;;0_h
zqM%r*I@^N?SFDbhdBFCi&+Mekv;L%|^xEqlnJaXssgfhIp1US3K1t?Q_a0g+QcpQ{
z|EzgQppnuU@`_Bxw&*JKo)ag*u4K}*w9a#@$3(Kv-)HT&D`}_h9PWIkCLPGu3kj+9
zSN}BUnroI)%FbD7odpxec<p`0;BzUuj;@@>^w$1`t%u_)UDa`o4m+y~LRB;X7N%ew
zrDEy6=xHkSjszp$`|0*7Xw78JQq9hM2OuU%ZuM(vpYiyx&0mkRYR<)wm6)5|{y38n
zy>qeS=AxbQWkbc0jRUnW(H6r)Nyv+UYc~rrOos@s;>%pwAyLtjQoYV>U#vrxT3Bwo
z$LuyKyBElOnV)wzA!(GDn^(IiD!`M?&bq=Aq_5c;E$3BGO$oWQA~R?nIjB0fp;Ey&
zdI`D9eyDr>!EAfMkcmpqfmx`3g6m=_kwCt))Ps3_M3Zk~QG8}~H*Q)b%HB7%Qi1GK
zongK)W#5P*IbZwZL7k}Hwp>$@28%bz{^&y`6%{m2MQ*=E{t_~|1F3UV*d^1XI)7`L
zuj;_*njVWi;c1q^D$Dn~YD$SP+4JGouJ^GP0Qq58y7~FXo}7dcSz1{<vs*$9F;U&9
zd_Xh70uGewlRFC7(W`Nlxz*L_`S6zo?Gz<p@bW>VnzB2{`!!k#4B7DVfJs6}e|y0-
zLop+bc}M)=RMp4qk_C@4k$V9GrzKDHI)gW9K6^K8;F#QPTKTHS$00Z$=BcMEpAp0l
z-P&eYtVTa`JWza9t)aH^?j-~DivI8+NwXVa(*)g<spKB%K2hXT=R>!Q`}?{$R~{})
zX?QtMQx#cw)l>Zbx%0c$!MqB3b<y+ZK9&4sSBzUsKIbJLuYKFnyzI(A+t=pVk95gb
z3(5x~o)6IPhs_-?@D2WxuN7eIYS$YfDx7ZEH6d*!Z+64ir=+L?$Ed;1qFsiM1nfEY
z-sx!?J=j!$&MAsNpEYoe=ACC)aN8*5ExtCjM!%xY_UjGL{MGDvDW7<LLC^M|u6?|Q
zQ}Rk_diI=0IV<0s4S!hjsy;MmssHLtdL^&yRXqIGoG%++6@V(u?|9I*vU`o_ZnyS>
zT+<1Mvu+(f5K~g}M9*wEA@2O4UOsCpnb?{-O$GO+E8}Rd#^h;H@-^$VOJ54ke{`~}
zi8ynV{V+!b*ZNVF`)IwkiW_;BBb?$QT-oF<<TbhXR)g=%CU@@1m4j3zpRZJ<%dtG&
zBIYg%&+WQ>Q`T0`4~v!Rw(-B*Dt^D=)8siMrCNl~8m&ZNgjFxBW?|n10)>bhrIEi^
zHuo?g0=qB*5!ex7aTpc?3FM6j%M?5rB2n?aIIt)}_$WleY99`EMZ|(&5fc%Es^}sT
zFx?Q;8wPa~g541b3fQeB=yEp{R7Qw^;Q$dE0T3q;WD`&*VM{Ovh++sUu&y{j8Z`@3
zF;Z{=8n6qJ8778cdk#wsdE+p%U2(n;KnTVle-OpcM{D(nq$LAoa0P*55Tn*RA}E6e
zRv^L%;k#~wzXN=K4IJ$3;s_Dw^id;aZ#AmQ)c}XdxqgR{z2?{|4M+R?DmEQmv|xx4
z%rUULmBShj+a<OLHv~aBOoq%|R*0A>;s{ZJ2r|SVWbTly0C#dkV$_n&5J4m&?7$cu
z6Np6Elfy#UVs9ML08{kqL!n_F#2&zbqfn?2_HT^u`}{{LSjCNTjC>pXgl<420v;+A
z^Mq{t!}s4MF{Cjq6#VxwX73oCh@r_I8i_PUmD!4iNEijked7mX?2%#Nv0Sz0gI{9~
zKM=TrZ_XEUzRlf&{ZTB_vE%@;9LqS&xj&@MPrjE;ofteI_D?~w0Gq{Ij|S-x2{g!n
zN`wr^1Yhh_5GV$r!NKNYCbn?^734faXp3+H*`re|zStTjii1~xROK+u`GH&ncoKF)
z5uOLwFk~F;$PtUd>&OBt3mUw76ox`F1gIbjzy{QYm%~o53+xK7f*G(s%!FAm0tdi>
zFdOE;JeUvjIeY{bzyk1B2n)HvVps%=VKEYd@L@4W0*ko}F&h>O8B7F5;b1rf4uiwt
za6}}~kvRbzc@Pprz(Vt5vSag6_l+EiemoO_7x~fYmScw~B9%a<)4v^;R;`kASM*dl
zGM7lw&0xiyU@P#fU6Nwb$G2%HY~`C-o3ETTbAgMc*_5i-u54YOlQ}o_ZZ2P-3pIJv
zJ<DEw-LpQ{Y^Pn_xJhSgGNmC6kB8fvB_UcD9`mXWkpf?*ZhZ5x_|5R^;i=j&j3hH?
z?##>wFS3J`b;<|!YK160T~X4@YIVve+|1HbaLjU#N!x7^Z}FnT#gy}cOhAoGj@G!)
zq7`rxquN%<<)7OrBHq6rEE>GfxKE7~82&Y~Obdd{ijQ_QEbE&R%(qGQcwH9xBAc@2
z;i2_8`nJV;{Bmko$8Oh>tsiz??0Zq?9(-z(cf>iHD=X9v9WB3o@7|pQQuy7Tq414E
z70>*>5|j_A_KDi=CKg^4?KAO6-G6+=y^oI<S+8^}So6^EqMh&B&3(}sNzdx$zAww<
zbml2<IJCBfE^g}|AK+T2uwJJy&dVt$z4;_f_lVbuC^xy2_3jf3qg`Frx-ZH+7I8v*
z{Y*-XmqTTy{|Q18Ni)kw`!~vwWLra5w=fNz<R>n6hkhrTAKLPV+&mBbX*-&y#Egv|
zY(IOaHNo;Kd+!N%G_A$VlXNdmKK~F0nbc@T-OEFoV%$pdqa$(eZ(pBkpxXDg%xS}N
zPh0tjx}F<rjLw?h2!8m7Y4z>TUE#O#AC%47m-JbxdRMvsSr^~+o<f`gu^~Et(;rv8
z8=_356OUI`b7$X}8sTM;HRPl@b5VvsS90y$pA9o6?fm@JJmAhil<is{d5!0{JCN&Z
z^O@2u6W&hy%Q|3L>5jm;H}yiMJW2MwkUKkL-@9uoK3Vv<@m2k=7phO3F>&TseB5o;
zVa@S3`F6Vk)MM~2rxQNE^My7nUdSAO1@UP(j5x0&#}$7(=G;E9O2S_<RNC|Ty1tJ<
znz~w=+BkKRsmUWW_w|b!#kA(;TLVPRHt7J*a%qEV43+DpSW*1qWX~r1o^#3}2csl}
zkc6Z!zF~=R7E3pTJ5v^>6O_tWcjBT9>`(RY4ZrcK{!PpoH&3;@2lzRk&aMxgU>wup
zY*VPWt=#0#x2A(@l@sq>6<f?k-NS4*{y}m0&>pd==}YY+r8ZZsu9c}%2a?mv78S4i
zZ9?-D{6!%(X#9TL+q=fy)=4kFa47%w_TN`h4m8*|_|zxYjFY?Lw{Bv^q}Ig7HQ}B1
z;iL<SF>4jJN7PvOa-W&pR9RqA8l`D;(BZO1>zUoEYQs>@5sgdM#^zUY6|2~ak<+EN
zc)xy6;g*In^_EoUmR&Ai*Cp1zJx+Sl`MyoP!Or*~Z{zv>o3=C-^h{P|nH`z7>WX5J
zT<PE?Mr3HCWebTGId2fB+Mc*1F5==1!OFgiQrC)#^A|~*2lo%(@XnH>)RPPITSI*J
z{x+xMcVWQ1(>Ev8EKR=9wDmvpCikbMpHsFP=r^8~+9<VeW=GqpJ+c1$a&dY5eN(o9
zf1$d2YSMLHS;l3HMMqCvu0uKefq{zq`?&I(o(_?MZA$6f3cEdR1Z~sEyBVph()}5x
zDMe*3*a~|S+Hj`c2R`Q)UcA({KS?@wxV*f1c0<XDbC=u4**BZ%n6EM3DMmjN9m}HS
zJ*4^`4F-NeCwk5#z26kVisWe;vmPi-I!(0Lv9`Gne_A!SFTPTc7hu=IBKo{786t<$
z+kNtjYL$*nfVK*!yp41`Cg%x`RQt^5PvDnAd6x^hX!@YwOYERRPPvf>eC_#1(H;)f
znK*M}Yy`)p@svU3lS_GL7tMG4uuxYAepD4rhzXt7BL1U3{ZcG5#z`&5DCERUyVFk3
zhhH{_w-lv3-N&jr-&Cx9!am5gKB~VZ^_lfNTiR5$JtgkK&7WtKsU=nZW#69T9B+2I
zAvOj-$;T_M%2=N}Wf?nWyHTFo@e67(jV5Qa<r?A-^fq#HTZMbu!&hWiuACKZY4o4H
zt&dtan%KSD80D1Qx_)r$WPKk(OSye1rBdrw=ezc{LY&&2MScq)b1TN;@dp<?kBzkQ
zT(954T&RveHdm{E=VboGx5Qmuv&pxXwCm9RtnE2og*ZLfb$i{eYB{y{3{G0L(cWdD
z@s$=$hx4po3@px<AFPoi<v71fR(s_<qkht6-)CZ4ZB|(O4MxO_BD?BD`Ku2_)aPre
zSIMjGXj-~95w9>1fpeIA>oqlf+U3QUZkHBl&)WT9e$^!x;rfP?=d!tBDKD-)&5@e!
zpgdmn=|IN)bFRgeb^Y-kMSlhz|1c%;sD-4&|AXS0gtY&BwTpaF@#k)rhbuY8ZWkh(
ziv3HYPdnlgKk6pUFDm69W(OQTz4rDvzm)VFizNI%znW{Dcp5)3wnMe!S!=$ZFD>*P
z@lw@|7uWRra+3-!mlsqw*8ipp9qAOTRh%{JYFR^z)qjd69PWv7ZrIsX(Hrc{J|H(Z
zcVoYqg)+a_sqfS!ZBOF$n6ryYuX=5un}<+4KeY#)Q1U%>rTI<(N!$O{rwHDWfK4^J
z$83}*2QSBEhiopE9!a(Lyb!7vRdajC>$DH&_O_{|4P~8DvT-im`ElC{Mgc3`FzLdK
zmlvuHTb4wt3<Wc<&R2vh&Z%p-!yO&%CDx4u)c(@2>QV~DxTquZ)=v5M^j+OeTRPo*
zQ;OE5zLw9<6vis+l6{ERHzzjw|K=U}G+k~`#s6vX#E_bKulcrb_wLiP>7qNHsyI9@
zW4+Or54nk%+mNTLC7-UqYhD+2HqUty;ym%~#-11Rbvo5uonDU{(%5}5)~V;TK5ehx
zN4lN=mqgdcnNE93Zbcm(*N2;!V`_2mx}3q2fR3!3L(}`S2C7ZwrIzc~%Z2Mnwp;H=
zkr0b;WefeMDytoE4_n}y?BU(KB{%PaKXsXN^Kj?ya?q^kE8`4wa-VjZd~mD_Xi}fU
z7i#m;9$A)`np_Hz_T2M)rL7az-_<+NS!X?<airq%4(Y3-w)gxld7Zj=B*Lfsczyc#
zoX3})ZqnCD<h>L>9Puh;E@*nfo#Xo#LmDjY;AK-)et$VRonbbm@WI6L1qD{p4euYZ
zQ(wB6bVpdwdbcYtF6L@Nl|wpjH+GgSu@CxdhH7_jU!Q}5{e#@pHiGfnz#TCk?!tc4
z>+6%DEmfbk_bTfjXuLCYdg|S|(`L@%Y9z+4sdurM+gg;@)LWr_p<4ds<n0mz=YqM7
z)gcx~*Bx`w%1&4y_j$%%h}dV#{_B-P_xxQoN8WFXoS+;xm^Z^IZ^6b)uOj)`KErpH
zpp#Rbzxb5*eYxg$zv*&aZD{$kYg;;sUT%8wnA-H_srUIW+}S=iyfo+)iiMmn_~nV~
z`WTBg?AFrkmix4H*1HnB-feN`Q|I~b5+1h~23(t-r`&EgU2$OLBA3gxk+lBzk9YQj
zlg3Zoy4QMl!kes?9l7%D(x|SuPAi)-`HJYg!IXGE>7peI<@Q&hmNo1z4-=@f%bpEt
zW*OVTR}Zp>FTOp$c6vnU8&KxlY&&LLyFOhbck-3($IN249@{hP_uezppT-m<=BlW^
zn~~$Ws<v$Am4&<1jg1C8Xz>{*hR3zI@AAZs?|;AL%I<SNp5(`Fdf!i>s~sK2j-UiG
z)$rR9)MS|ioO^>16!J#`Ieb&CH`1$G5Qk-|<w<eGI|?lkHpezxgt&z}xiiCqn1(E^
zWptd$G6uL_BYF~sP%l8%5EMh;P;a`x($&Fc0mdLPlJJB)aN&d`JT6~sBr(;Ji5P(~
zMuxQ@84DU@s<qnD1wsV^ZV(5Bi28>51U&+2DHI?AcaKnkC<r3xQ?&r3h!tSu3hvq?
zfM8~-#YRz~5e$chhU$ls^aY|om|$pV2;+$`k*Eha^u%F&lp)dMix&cYGDA44zlrh1
z`ZAmJnF1cnSq&5P@$i_Uu{$V7z=tr!41Yl|YN|z{Ap~*&!$6O~ATjj_1ca%F2Om8u
zgJQr!m<%F=$r#fl{K3M%sR9c?7YVokjEq1ZffdX|M5bEHT^yk0Y=IaZx&A^leFK6P
zJo@JUf<Yi6|NQPCjH54a0(guZ!7VZ%%nEcd=x)J$NY4$?6GH9;nh``WGBl#ljEo47
z3H%c$2sse71Z`l@7XB|pf8hK<R3LH(i9iqJ2Mf6Z6e8=BAt3{0vbo^0#)a@BT4kc6
zoF*_9ogbX@FS?5%baec`9meBfd5rNHSqYfIJaDUBVf9~T$-fv_7W12#!e9|swh>rN
z7~vwAMPd+J0<e?CGzt)icnpxn451L*xfv+PZW!dC7Tp9aq8yZq&}G}qoQsYOxEyTT
z7;zc=KvOM=9t#Oz1ana>y0*@U<GCFA$Ur6me@6i$CYB2V(Fl+mvSAF7&IDU2Sj0ho
zf{?Lb5Z?sBm^Io90+#*?G?pe<uKaIce*^f3WRa0TSpj(ie=Aya9P}@J{ym`Yl^WE4
zQ>{>}4*&8?@Iy~xtgdMPQ(4gg?Gr3Kz^&M3)yDR@8zO{2FNYx8;zR;O#1jaB4^#sg
zi<J>Zz#9^11VajqNL+#^YT@x(V@Lv#_E<Q6-nD?m9m_3kFaTYV^#~LF#*2jxkj;Zp
zHb5B544rQcM~Mgt0F5)y4#Mi}$OocQC?pCL0FBbX4;pB{VIPP;Mx#;;f1we`c+eXB
zJ0F2a`GpUUCxGVc&wQj`_y`md@b^!ARM4jTiAKbeK<n`*K8nFFd;}`~7aEa7`9%i>
zPXQg@F+5bn0R1Tu_>VdWcH@MD&NCT;T?L?e%9_p)yn-JffUv{>-RKookhh5yo?vZ3
zGoaX5TNoNrNd^{{22^W2#lXhE+``hFXioqCIefA1vlwNFP+5SeG&~ijscG$OgZm$L
CBw1nr
literal 0
HcmV?d00001
diff --git a/curve_time_gpu.plot b/curve_time_gpu.plot
new file mode 100644
index 0000000..4326e12
--- /dev/null
+++ b/curve_time_gpu.plot
@@ -0,0 +1,20 @@
+# Analysis description
+set encoding iso_8859_1
+set terminal x11
+set size 1,0.5
+set term postscript enhanced portrait "Helvetica" 12
+#set title "Performance on homogeneous cluster"
+set ylabel "Random numbers generated / second"
+set xlabel "Number of threads used by the GPU"
+#set nologscale;
+set logscale x;
+set logscale y;
+#set label "Taille" at -0.002,2.1 right
+#set label "file" at -0.003,2 right
+#set key 1500,1600
+#set xrange [20:200]
+#set yrange [0:300]
+#set offsets 0,0,2,2
+set key left top
+plot 'time_gpu.txt' using 1:2 t "naive prng gpu" with linespoints lt 2 lw 2 ps 0 pt 5,\
+'time_gpu.txt' using 1:3 t "optimized prng gpu" with linespoints lt 1 lw 2 ps 0 pt 5
diff --git a/prng_gpu.tex b/prng_gpu.tex
index fa71e5b..d1fb7a6 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -674,7 +674,7 @@ achieved out. Then in order to apply the negation on these bits we can simply
apply the xor operator between the current number and the strategy. In
order to obtain the strategy we also use a classical PRNG.
-Here is an example with 16-bits numbers showing how the bit operations are
+Here is an example with 16-bits numbers showing how the bitwise operations are
applied. Suppose that $x$ and the strategy $S^i$ are defined in binary mode.
Then the following table shows the result of $x$ xor $S^i$.
$$
@@ -738,17 +738,18 @@ unsigned int CIprng() {
-In listing~\ref{algo:seqCIprng} a sequential version of our chaotic iterations
-based PRNG is presented. The xor operator is represented by \textasciicircum. This function uses three classical 64-bits PRNG: the
-\texttt{xorshift}, the \texttt{xor128} and the \texttt{xorwow}. In the
-following, we call them xor-like PRNGSs. These three PRNGs are presented
-in~\cite{Marsaglia2003}. As each xor-like PRNG used works with 64-bits and as our PRNG
-works with 32-bits, the use of \texttt{(unsigned int)} selects the 32 least
-significant bits whereas \texttt{(unsigned int)(t3$>>$32)} selects the 32 most
-significants bits of the variable \texttt{t}. So to produce a random number
-realizes 6 xor operations with 6 32-bits numbers produced by 3 64-bits PRNG.
-This version successes the BigCrush of the TestU01 battery [P. Lâecuyer and
- R. Simard. Testu01].
+In listing~\ref{algo:seqCIprng} a sequential version of our chaotic iterations
+based PRNG is presented. The xor operator is represented by
+\textasciicircum. This function uses three classical 64-bits PRNG: the
+\texttt{xorshift}, the \texttt{xor128} and the \texttt{xorwow}. In the
+following, we call them xor-like PRNGSs. These three PRNGs are presented
+in~\cite{Marsaglia2003}. As each xor-like PRNG used works with 64-bits and as
+our PRNG works with 32-bits, the use of \texttt{(unsigned int)} selects the 32
+least significant bits whereas \texttt{(unsigned int)(t3$>>$32)} selects the 32
+most significants bits of the variable \texttt{t}. So to produce a random
+number realizes 6 xor operations with 6 32-bits numbers produced by 3 64-bits
+PRNG. This version successes the BigCrush of the TestU01 battery [P. Lâecuyer
+ and R. Simard. Testu01].
\section{Efficient prng based on chaotic iterations on GPU}
@@ -835,6 +836,8 @@ 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.
+This version also succeed to the BigCrush batteries of tests.
+
\begin{algorithm}
\KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs in global memory\;
@@ -863,10 +866,20 @@ tab1, tab2: Arrays containing permutations of size permutation\_size\;}
\caption{main kernel for the chaotic iterations based PRNG GPU efficient version}
\label{algo:gpu_kernel2}
\end{algorithm}
+
+
+
\section{Experiments}
Differents experiments have been performed in order to measure the generation speed.
+\begin{figure}[t]
+\begin{center}
+ \includegraphics[scale=.5]{curve_time_gpu.pdf}
+\end{center}
+\caption{Number of random numbers generated per second}
+\label{fig:time_naive_gpu}
+\end{figure}
First of all we have compared the time to generate X random numbers with both the CPU version and the GPU version.
diff --git a/time_gpu.txt b/time_gpu.txt
new file mode 100644
index 0000000..843bf09
--- /dev/null
+++ b/time_gpu.txt
@@ -0,0 +1,13 @@
+#threads naive nb rand/s opti
+10240 1958396000.03 13162317203.28
+20480 2607152000.80 17544514829.35
+30720 2932438000.82 19734780759.37
+51200 2787838000.25 18772978895.58
+76800 2926940000.81 19718338110.60
+102400 2778762000.41 18800512068.39
+153600 2927902000.36 19692840251.08
+512000 2905399000.83 19605898582.49
+768000 2826752000.70 19717903047.22
+1048576 2717620000.40 19625932346.26
+2097152 2720592856.85 19571418202.69
+5242880 2542399000.19 19497621662.45
--
2.39.5