prng_gpu.tex

   1 \documentclass{article}
   2 \usepackage[utf8]{inputenc}
   3 \usepackage[T1]{fontenc}
   4 \usepackage{fullpage}
   5 \usepackage{fancybox}
   6 \usepackage{amsmath}
   7 \usepackage{amscd}
   8 \usepackage{moreverb}
   9 \usepackage{commath}
  10 \usepackage[standard]{ntheorem}
  11
  12 % Pour mathds : les ensembles IR, IN, etc.
  13 \usepackage{dsfont}
  14
  15 % Pour avoir des intervalles d'entiers
  16 \usepackage{stmaryrd}
  17
  18 \usepackage{graphicx}
  19 % Pour faire des sous-figures dans les figures
  20 \usepackage{subfigure}
  21
  22 \newtheorem{notation}{Notation}
  23
  24 \newcommand{\X}{\mathcal{X}}
  25 \newcommand{\Go}{G_{f_0}}
  26 \newcommand{\B}{\mathds{B}}
  27 \newcommand{\N}{\mathds{N}}
  28 \newcommand{\BN}{\mathds{B}^\mathsf{N}}
  29 \let\sur=\overline
  30
  31
  32 \title{Efficient generation of pseudo random numbers based on chaotic iterations on GPU}
  33 \begin{document}
  34 \maketitle
  35
  36 \begin{abstract}
  37 This is the abstract
  38 \end{abstract}
  39
  40 \section{Introduction}
  41
  42 Interet des itérations chaotiques pour générer des nombre alea\\
  43 Interet de générer des nombres alea sur GPU
  44 ...
  45
  46 \section{Chaotic iterations}
  47
  48 Présentation des itérations chaotiques
  49
  50
  51
  52 \section{The phase space is an interval of the real line}
  53
  54 \subsection{Toward a topological semiconjugacy}
  55
  56 In what follows, our intention is to establish, by using a topological semiconjugacy, that chaotic iterations over $\mathcal{X}$ can be described as iterations on a real interval. To do so, we must firstly introduce some notations and terminologies.
  57
  58 Let $\mathcal{S}_\mathsf{N}$ be the set of sequences belonging into $\llbracket 1; \mathsf{N}\rrbracket$ and $\mathcal{X}_{\mathsf{N}} = \mathcal{S}_\mathsf{N} \times \B^\mathsf{N}$.
  59
  60
  61 \begin{definition}
  62 The function $\varphi: \mathcal{S}_{10} \times\mathds{B}^{10} \rightarrow \big[ 0, 2^{10} \big[$ is defined by:
  63 $$
  64 \begin{array}{cccl}
  65 \varphi: & \mathcal{X}_{10} = \mathcal{S}_{10} \times\mathds{B}^{10}& \longrightarrow & \big[ 0, 2^{10} \big[ \\
  66  & (S,E) = \left((S^0, S^1, \hdots ); (E_0, \hdots, E_9)\right) & \longmapsto & \varphi \left((S,E)\right)
  67 \end{array}
  68 $$
  69 \noindent where $\varphi\left((S,E)\right)$ is the real number:
  70 \begin{itemize}
  71 \item whose integral part $e$ is $\displaystyle{\sum_{k=0}^9 2^{9-k} E_k}$, that is, the binary digits of $e$ are $E_0 ~ E_1 ~ \hdots ~ E_9$.
  72 \item whose decimal part $s$ is equal to $s = 0,S^0~ S^1~ S^2~ \hdots = \sum_{k=1}^{+\infty} 10^{-k} S^{k-1}.$
  73 \end{itemize}
  74 \end{definition}
  75
  76
  77
  78 $\varphi$ realizes the association between a point of $\mathcal{X}_{10}$ and a real number into $\big[ 0, 2^{10} \big[$. We must now translate the chaotic iterations $\Go$ on this real interval. To do so, two intermediate functions over $\big[ 0, 2^{10} \big[$ must be introduced:
  79
  80
  81 \begin{definition}
  82 \label{def:e et s}
  83 Let $x \in \big[ 0, 2^{10} \big[$ and:
  84 \begin{itemize}
  85 \item $e_0, \hdots, e_9$ the binary digits of the integral part of $x$: $\displaystyle{\lfloor x \rfloor = \sum_{k=0}^{9} 2^{9-k} e_k}$.
  86 \item $(s^k)_{k\in \mathds{N}}$ the digits of $x$, where the chosen decimal decomposition of $x$ is the one that does not have an infinite number of 9:
  87 $\displaystyle{x = \lfloor x \rfloor + \sum_{k=0}^{+\infty} s^k 10^{-k-1}}$.
  88 \end{itemize}
  89 $e$ and $s$ are thus defined as follows:
  90 $$
  91 \begin{array}{cccl}
  92 e: & \big[ 0, 2^{10} \big[ & \longrightarrow & \mathds{B}^{10} \\
  93  & x & \longmapsto & (e_0, \hdots, e_9)
  94 \end{array}
  95 $$
  96 \noindent and
  97 $$
  98 \begin{array}{cccl}
  99 s: & \big[ 0, 2^{10} \big[ & \longrightarrow & \llbracket 0, 9 \rrbracket^{\mathds{N}} \\
 100  & x & \longmapsto & (s^k)_{k \in \mathds{N}}
 101 \end{array}
 102 $$
 103 \end{definition}
 104
 105 We are now able to define the function $g$, whose goal is to translate the chaotic iterations $\Go$ on an interval of $\mathds{R}$.
 106
 107 \begin{definition}
 108 $g:\big[ 0, 2^{10} \big[ \longrightarrow \big[ 0, 2^{10} \big[$ is defined by:
 109 $$
 110 \begin{array}{cccl}
 111 g: & \big[ 0, 2^{10} \big[ & \longrightarrow & \big[ 0, 2^{10} \big[ \\
 112 & \\
 113  & x & \longmapsto & g(x)
 114 \end{array}
 115 $$
 116 \noindent where g(x) is the real number of $\big[ 0, 2^{10} \big[$ defined bellow:
 117 \begin{itemize}
 118 \item its integral part has a binary decomposition equal to $e_0', \hdots, e_9'$, with:
 119 $$
 120 e_i' = \left\{
 121 \begin{array}{ll}
 122 e(x)_i & \textrm{ if } i \neq s^0\\
 123 e(x)_i + 1 \textrm{ (mod 2)} & \textrm{ if } i = s^0\\
 124 \end{array}
 125 \right.
 126 $$
 127 \item whose decimal part is $s(x)^1, s(x)^2, \hdots$
 128 \end{itemize}
 129 \end{definition}
 130
 131 \bigskip
 132
 133
 134 In other words, if $x = \displaystyle{\sum_{k=0}^{9} 2^{9-k} e_k +  \sum_{k=0}^{+\infty} s^{k} ~10^{-k-1}}$, then: $$g(x) = \displaystyle{\sum_{k=0}^{9} 2^{9-k} (e_k + \delta(k,s^0) \textrm{ (mod 2)}) +  \sum_{k=0}^{+\infty} s^{k+1} 10^{-k-1}}.$$
 135
 136 \subsection{Defining a metric on $\big[ 0, 2^{10} \big[$}
 137
 138 Numerous metrics can be defined on the set $\big[ 0, 2^{10} \big[$, the most usual one being the Euclidian distance recalled bellow:
 139
 140 \begin{notation}
 141 \index{distance!euclidienne}
 142 $\Delta$ is the Euclidian distance on $\big[ 0, 2^{10} \big[$, that is, $\Delta(x,y) = |y-x|^2$.
 143 \end{notation}
 144
 145 \medskip
 146
 147 This Euclidian distance does not reproduce exactly the notion of proximity induced by our first distance $d$ on $\X$. Indeed $d$ is finer than $\Delta$. This is the reason why we have to introduce the following metric:
 148
 149
 150
 151 \begin{definition}
 152 Let $x,y \in \big[ 0, 2^{10} \big[$.
 153 $D$ denotes the function from $\big[ 0, 2^{10} \big[^2$ to $\mathds{R}^+$ defined by: $D(x,y) = D_e\left(e(x),e(y)\right) + D_s\left(s(x),s(y)\right)$, where:
 154 \begin{center}
 155 $\displaystyle{D_e(E,\check{E}) = \sum_{k=0}^\mathsf{9} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{D_s(S,\check{S}) = \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
 156 \end{center}
 157 \end{definition}
 158
 159 \begin{proposition}
 160 $D$ is a distance on $\big[ 0, 2^{10} \big[$.
 161 \end{proposition}
 162
 163 \begin{proof}
 164 The three axioms defining a distance must be checked.
 165 \begin{itemize}
 166 \item $D \geqslant 0$, because everything is positive in its definition. If $D(x,y)=0$, then $D_e(x,y)=0$, so the integral parts of $x$ and $y$ are equal (they have the same binary decomposition). Additionally, $D_s(x,y) = 0$, then $\forall k \in \mathds{N}^*, s(x)^k = s(y)^k$. In other words, $x$ and $y$ have the same $k-$th decimal digit, $\forall k \in \mathds{N}^*$. And so $x=y$.
 167 \item $D(x,y)=D(y,x)$.
 168 \item Finally, the triangular inequality is obtained due to the fact that both $\delta$ and $\Delta(x,y)=|x-y|$ satisfy it.
 169 \end{itemize}
 170 \end{proof}
 171
 172
 173 The convergence of sequences according to $D$ is not the same than the usual convergence related to the Euclidian metric. For instance, if $x^n \to x$ according to $D$, then necessarily the integral part of each $x^n$ is equal to the integral part of $x$ (at least after a given threshold), and the decimal part of $x^n$ corresponds to the one of $x$ ``as far as required''.
 174 To illustrate this fact, a comparison between $D$ and the Euclidian distance is given Figure \ref{fig:comparaison de distances}. These illustrations show that $D$ is richer and more refined than the Euclidian distance, and thus is more precise.
 175
 176
 177 \begin{figure}[t]
 178 \begin{center}
 179   \subfigure[Function $x \to dist(x;1,234) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien.pdf}}\quad
 180   \subfigure[Function $x \to dist(x;3) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien2.pdf}}
 181 \end{center}
 182 \caption{Comparison between $D$ (in blue) and the Euclidian distane (in green).}
 183 \label{fig:comparaison de distances}
 184 \end{figure}
 185
 186
 187
 188
 189 \subsection{The semiconjugacy}
 190
 191 It is now possible to define a topological semiconjugacy between $\mathcal{X}$ and an interval of $\mathds{R}$:
 192
 193 \begin{theorem}
 194 Chaotic iterations on the phase space $\mathcal{X}$ are simple iterations on $\mathds{R}$, which is illustrated by the semiconjugacy of the diagram bellow:
 195 \begin{equation*}
 196 \begin{CD}
 197 \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
 198     @V{\varphi}VV                    @VV{\varphi}V\\
 199 \left( ~\big[ 0, 2^{10} \big[, D~\right)  @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right)
 200 \end{CD}
 201 \end{equation*}
 202 \end{theorem}
 203
 204 \begin{proof}
 205 $\varphi$ has been constructed in order to be continuous and onto.
 206 \end{proof}
 207
 208 In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \big[$.
 209
 210
 211
 212
 213 \section{Efficient prng based on chaotic iterations}
 214
 215 On parle du séquentiel avec des nombres 64 bits\\
 216
 217 Faire le lien avec le paragraphe précédent (je considère que la stratégie s'appelle $S^i$\\
 218
 219 In  order to  implement efficiently  a PRNG  based on  chaotic iterations  it is
 220 possible to improve  previous works [ref]. One solution  consists in considering
 221 that the  strategy used $S^i$  contains all the  bits for which the  negation is
 222 achieved out. Then instead of applying  the negation on these bits we can simply
 223 apply the  xor operator between  the current number  and the strategy  $S^i$. In
 224 order to obtain the strategy we also use a classical PRNG.
 225
 226 \begin{figure}[htbp]
 227 \begin{center}
 228 \fbox{
 229 \begin{minipage}{14cm}
 230 unsigned int CIprng() \{\\
 231   static unsigned int x = 123123123;\\
 232   unsigned long t1 = xorshift();\\
 233   unsigned long t2 = xor128();\\
 234   unsigned long t3 = xorwow();\\
 235   x = x\textasciicircum (unsigned int)t1;\\
 236   x = x\textasciicircum (unsigned int)(t2$>>$32);\\
 237   x = x\textasciicircum (unsigned int)(t3$>>$32);\\
 238   x = x\textasciicircum (unsigned int)t2;\\
 239   x = x\textasciicircum (unsigned int)(t1$>>$32);\\
 240   x = x\textasciicircum (unsigned int)t3;\\
 241   return x;\\
 242 \}
 243 \end{minipage}
 244 }
 245 \end{center}
 246 \caption{sequential Chaotic Iteration PRNG}
 247 \label{algo:seqCIprng}
 248 \end{figure}
 249
 250 In Figure~\ref{algo:seqCIprng}  a sequential  version of our  chaotic iterations
 251 based PRNG  is presented.  This version  uses three classical 64  bits PRNG: the
 252 \texttt{xorshift},  the \texttt{xor128}  and the  \texttt{xorwow}.   These three
 253 PRNGs  are presented  in~\cite{Marsaglia2003}.   As each  PRNG  used works  with
 254 64-bits and as  our PRNG works with 32 bits, the  use of \texttt{(unsigned int)}
 255 selects the 32 least  significant bits whereas \texttt{(unsigned int)(t3$>>$32)}
 256 selects the 32  most significants bits of the  variable \texttt{t}. This version
 257 sucesses   the   BigCrush   of    the   TestU01   battery   [P.   L’ecuyer   and
 258   R. Simard. Testu01].
 259
 260 \section{Efficient prng based on chaotic iterations on GPU}
 261
 262 On parle du passage du sequentiel au GPU
 263
 264 \section{Experiments}
 265
 266 On passe le BigCrush\\
 267 On donne des temps de générations sur GPU/CPU\\
 268 On donne des temps de générations de nombre sur GPU puis on rappatrie sur CPU / CPU ? bof bof, on verra
 269
 270
 271 \section{Conclusion}
 272 \bibliographystyle{plain}
 273 \bibliography{mabase}
 274 \end{document}