pouet

[prng_gpu.git] / prng_gpu.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fullpage}
\usepackage{fancybox}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{moreverb}
\usepackage{commath}
\usepackage[standard]{ntheorem}

% Pour mathds : les ensembles IR, IN, etc.
\usepackage{dsfont}

% Pour avoir des intervalles d'entiers
\usepackage{stmaryrd}

\usepackage{graphicx}
% Pour faire des sous-figures dans les figures
\usepackage{subfigure}

\newtheorem{notation}{Notation}

\newcommand{\X}{\mathcal{X}}
\newcommand{\Go}{G_{f_0}}
\newcommand{\B}{\mathds{B}}
\newcommand{\N}{\mathds{N}}
\newcommand{\BN}{\mathds{B}^\mathsf{N}}
\let\sur=\overline


\title{Efficient generation of pseudo random numbers based on chaotic iterations on GPU}
\begin{document}
\maketitle

\begin{abstract}
This is the abstract
\end{abstract}

\section{Introduction}

Interet des itérations chaotiques pour générer des nombre alea\\
Interet de générer des nombres alea sur GPU
...

\section{Chaotic iterations}

Présentation des itérations chaotiques



\section{The phase space is an interval of the real line}

\subsection{Toward a topological semiconjugacy}

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. 

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}$.


\begin{definition}
The function $\varphi: \mathcal{S}_{10} \times\mathds{B}^{10} \rightarrow \big[ 0, 2^{10} \big[$ is defined by:
$$
\begin{array}{cccl}
\varphi: & \mathcal{X}_{10} = \mathcal{S}_{10} \times\mathds{B}^{10}& \longrightarrow & \big[ 0, 2^{10} \big[ \\
 & (S,E) = \left((S^0, S^1, \hdots ); (E_0, \hdots, E_9)\right) & \longmapsto & \varphi \left((S,E)\right)
\end{array}
$$
\noindent where $\varphi\left((S,E)\right)$ is the real number:
\begin{itemize}
\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$.
\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}.$ 
\end{itemize}
\end{definition}



$\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:


\begin{definition}
\label{def:e et s}
Let $x \in \big[ 0, 2^{10} \big[$ and:
\begin{itemize}
\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}$.
\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: 
$\displaystyle{x = \lfloor x \rfloor + \sum_{k=0}^{+\infty} s^k 10^{-k-1}}$.
\end{itemize}
$e$ and $s$ are thus defined as follows:
$$
\begin{array}{cccl}
e: & \big[ 0, 2^{10} \big[ & \longrightarrow & \mathds{B}^{10} \\
 & x & \longmapsto & (e_0, \hdots, e_9)
\end{array}
$$
\noindent and
$$
\begin{array}{cccl}
s: & \big[ 0, 2^{10} \big[ & \longrightarrow & \llbracket 0, 9 \rrbracket^{\mathds{N}} \\
 & x & \longmapsto & (s^k)_{k \in \mathds{N}}
\end{array}
$$
\end{definition}

We are now able to define the function $g$, whose goal is to translate the chaotic iterations $\Go$ on an interval of $\mathds{R}$.

\begin{definition}
$g:\big[ 0, 2^{10} \big[ \longrightarrow \big[ 0, 2^{10} \big[$ is defined by:
$$
\begin{array}{cccl}
g: & \big[ 0, 2^{10} \big[ & \longrightarrow & \big[ 0, 2^{10} \big[ \\
& \\
 & x & \longmapsto & g(x)
\end{array}
$$
\noindent where g(x) is the real number of $\big[ 0, 2^{10} \big[$ defined bellow:
\begin{itemize}
\item its integral part has a binary decomposition equal to $e_0', \hdots, e_9'$, with:
$$
e_i' = \left\{
\begin{array}{ll}
e(x)_i & \textrm{ if } i \neq s^0\\
e(x)_i + 1 \textrm{ (mod 2)} & \textrm{ if } i = s^0\\
\end{array}
\right.
$$
\item whose decimal part is $s(x)^1, s(x)^2, \hdots$
\end{itemize}
\end{definition}

\bigskip


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}}.$$

\subsection{Defining a metric on $\big[ 0, 2^{10} \big[$}

Numerous metrics can be defined on the set $\big[ 0, 2^{10} \big[$, the most usual one being the Euclidian distance recalled bellow:

\begin{notation}
\index{distance!euclidienne}
$\Delta$ is the Euclidian distance on $\big[ 0, 2^{10} \big[$, that is, $\Delta(x,y) = |y-x|^2$.
\end{notation}

\medskip

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:



\begin{definition}
Let $x,y \in \big[ 0, 2^{10} \big[$.
$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:
\begin{center}
$\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}}$.
\end{center}
\end{definition}

\begin{proposition}
$D$ is a distance on $\big[ 0, 2^{10} \big[$.
\end{proposition}

\begin{proof}
The three axioms defining a distance must be checked.
\begin{itemize}
\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$.
\item $D(x,y)=D(y,x)$.
\item Finally, the triangular inequality is obtained due to the fact that both $\delta$ and $\Delta(x,y)=|x-y|$ satisfy it.
\end{itemize}
\end{proof}


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''.
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.


\begin{figure}[t]
\begin{center}
  \subfigure[Function $x \to dist(x;1,234) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien.pdf}}\quad
  \subfigure[Function $x \to dist(x;3) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien2.pdf}}
\end{center}
\caption{Comparison between $D$ (in blue) and the Euclidian distane (in green).}
\label{fig:comparaison de distances}
\end{figure}




\subsection{The semiconjugacy}

It is now possible to define a topological semiconjugacy between $\mathcal{X}$ and an interval of $\mathds{R}$:

\begin{theorem}
Chaotic iterations on the phase space $\mathcal{X}$ are simple iterations on $\mathds{R}$, which is illustrated by the semiconjugacy of the diagram bellow:
\begin{equation*}
\begin{CD}
\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
    @V{\varphi}VV                    @VV{\varphi}V\\
\left( ~\big[ 0, 2^{10} \big[, D~\right)  @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right)
\end{CD}
\end{equation*}
\end{theorem}

\begin{proof}
$\varphi$ has been constructed in order to be continuous and onto.
\end{proof}

In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \big[$.




\section{Efficient prng based on chaotic iterations}

On parle du séquentiel avec des nombres 64 bits\\

Faire le lien avec le paragraphe précédent (je considère que la stratégie s'appelle $S^i$\\

In  order to  implement efficiently  a PRNG  based on  chaotic iterations  it is
possible to improve  previous works [ref]. One solution  consists in considering
that the  strategy used $S^i$  contains all the  bits for which the  negation is
achieved out. Then instead of applying  the negation on these bits we can simply
apply the  xor operator between  the current number  and the strategy  $S^i$. In
order to obtain the strategy we also use a classical PRNG.

\begin{figure}[htbp]
\begin{center}
\fbox{
\begin{minipage}{14cm}
unsigned int CIprng() \{\\
  static unsigned int x = 123123123;\\
  unsigned long t1 = xorshift();\\
  unsigned long t2 = xor128();\\
  unsigned long t3 = xorwow();\\
  x = x\textasciicircum (unsigned int)t1;\\
  x = x\textasciicircum (unsigned int)(t2$>>$32);\\
  x = x\textasciicircum (unsigned int)(t3$>>$32);\\
  x = x\textasciicircum (unsigned int)t2;\\
  x = x\textasciicircum (unsigned int)(t1$>>$32);\\
  x = x\textasciicircum (unsigned int)t3;\\
  return x;\\
\}
\end{minipage}
}
\end{center}
\caption{sequential Chaotic Iteration PRNG}
\label{algo:seqCIprng}
\end{figure}

In Figure~\ref{algo:seqCIprng}  a sequential  version of our  chaotic iterations
based PRNG  is presented.  This version  uses three classical 64  bits PRNG: the
\texttt{xorshift},  the \texttt{xor128}  and the  \texttt{xorwow}.   These three
PRNGs  are presented  in~\cite{Marsaglia2003}.   As each  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}. This version
sucesses   the   BigCrush   of    the   TestU01   battery   [P.   L’ecuyer   and
  R. Simard. Testu01].

\section{Efficient prng based on chaotic iterations on GPU}

On parle du passage du sequentiel au GPU

\section{Experiments}

On passe le BigCrush\\
On donne des temps de générations sur GPU/CPU\\
On donne des temps de générations de nombre sur GPU puis on rappatrie sur CPU / CPU ? bof bof, on verra


\section{Conclusion}
\bibliographystyle{plain}
\bibliography{mabase}
\end{document}