X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/2e8e9b41154df43b7a17bb19733abea069a7f20e..c1ba143536007ddfded6ec4043d1a77536e27d75:/prng_gpu.tex?ds=inline diff --git a/prng_gpu.tex b/prng_gpu.tex index 5431409..6409faf 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -34,7 +34,7 @@ \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}} -\title{Efficient generation of pseudo random numbers based on chaotic iterations +\title{Efficient Generation of Pseudo-Random Bumbers based on Chaotic Iterations on GPU} \begin{document} @@ -44,26 +44,52 @@ Guyeux\thanks{Authors in alphabetic order}} \maketitle \begin{abstract} -This is the abstract + \end{abstract} \section{Introduction} +Random numbers are used in many scientific applications and simulations. On +finite state machines, like computers, it is not possible to generate random +numbers but only pseudo-random numbers. In practice, a good pseudo-random number +generator (PRNG) needs to verify some features to be used by scientists. It is +important to be able to generate pseudo-random numbers efficiently, the +generation needs to be reproducible and a PRNG needs to satisfy many usual +statistical properties. Finally, from our point a view, it is essential to prove +that a PRNG is chaotic. Devaney~\cite{Devaney} proposed a common mathematical +formulation of chaotic dynamical systems. + +In a previous work~\cite{bgw09:ip} we have proposed a new familly of chaotic +PRNG based on chaotic iterations (IC). In this paper we propose a faster +version which is also proven to be chaotic with the Devaney formulation. + +Although graphics processing units (GPU) was initially designed to accelerate +the manipulation of image, they are nowadays commonly used in many scientific +applications. Therefore, it is important to be able to generate pseudo-random +numbers in a GPU when a scientific application runs in a GPU. That is why we +also provie an efficient PRNG for GPU respecting based on IC. + + + + Interet des itérations chaotiques pour générer des nombre alea\\ Interet de générer des nombres alea sur GPU -\alert{RC, un petit state-of-the-art sur les PRNGs sur GPU ?} -... +\section{Related works} + +In this section we review some GPU based PRNGs. +\alert{RC, un petit state-of-the-art sur les PRNGs sur GPU ?} + \section{Basic Recalls} \label{section:BASIC RECALLS} This section is devoted to basic definitions and terminologies in the fields of topological chaos and chaotic iterations. -\subsection{Devaney's chaotic dynamical systems} +\subsection{Devaney's Chaotic Dynamical Systems} In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$ denotes the $i^{th}$ component of a vector $V$. $f^{k}=f\circ ...\circ f$ -denotes the $k^{th}$ composition of a function $f$. Finally, the following +is for the $k^{th}$ composition of a function $f$. Finally, the following notation is used: $\llbracket1;N\rrbracket=\{1,2,\hdots,N\}$. @@ -89,7 +115,7 @@ necessarily the same period). \end{definition} -\begin{definition} +\begin{definition}[Devaney's formulation of chaos~\cite{Devaney}] $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and topologically transitive. \end{definition} @@ -119,7 +145,7 @@ possible and occur in an unpredictable way. -\subsection{Chaotic iterations} +\subsection{Chaotic Iterations} \label{sec:chaotic iterations} @@ -135,7 +161,7 @@ denoted by $\llbracket 1, \mathsf{N} \rrbracket^\mathds{N}.$ \label{Def:chaotic iterations} The set $\mathds{B}$ denoting $\{0,1\}$, let $f:\mathds{B}^{\mathsf{N}}\longrightarrow \mathds{B}^{\mathsf{N}}$ be -a function and $S\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ be a strategy. The so-called +a function and $S\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ be a ``strategy''. The so-called \emph{chaotic iterations} are defined by $x^0\in \mathds{B}^{\mathsf{N}}$ and \begin{equation} @@ -155,7 +181,7 @@ $\left(f(x^{n-1})\right)_{S^{n}}$ can be replaced by $\left(f(x^{k})\right)_{S^{n}}$, where $k0$. To +prove that $G_f$ is regular, it is sufficient to prove that +there exists a strategy $\tilde S$ such that the distance between +$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that +$(\tilde S,E)$ is a periodic point. + +Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the +configuration that we obtain from $(S,E)$ after $t_1$ iterations of +$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ +and $t_2\in\mathds{N}$ such +that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. + +Consider the strategy $\tilde S$ that alternates the first $t_1$ terms +of $S$ and the first $t_2$ terms of $S'$: $$\tilde +S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It +is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after +$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic +point. Since $\tilde S_t=S_t$ for $t