+
+
+
+
+
+\lstset{language=C,caption={C code of the sequential chaotic iterations based
+PRNG},label=algo:seqCIprng}
+\begin{lstlisting}
+unsigned int CIprng() {
+ static unsigned int x = 123123123;
+ unsigned long t1 = xorshift();
+ unsigned long t2 = xor128();
+ unsigned long t3 = xorwow();
+ x = x^(unsigned int)t1;
+ x = x^(unsigned int)(t2>>32);
+ x = x^(unsigned int)(t3>>32);
+ x = x^(unsigned int)t2;
+ x = x^(unsigned int)(t1>>32);
+ x = x^(unsigned int)t3;
+ return x;
+}
+\end{lstlisting}
+
+
+
+
+
+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~\cite{LEcuyerS07}.
+
+\section{Efficient PRNGs based on chaotic iterations on GPU}
+\label{sec:efficient prng gpu}
+
+In order to benefit from computing power of GPU, a program needs to define
+independent blocks of threads which can be computed simultaneously. In general,
+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. In the CUDA~\cite{Nvid10} environment, threads have a local
+identificator, called \texttt{ThreadIdx} relative to the block containing them.
+
+
+\subsection{Naive version for GPU}
+
+From the CPU version, it is possible to obtain a quite similar version for GPU.
+The principe consists in assigning the computation of a PRNG as in sequential to
+each thread of the GPU. Of course, it is essential that the three xor-like
+PRNGs used for our computation have different parameters. So we chose them
+randomly with another PRNG. As the initialisation is performed by the CPU, we
+have chosen to use the ISAAC PRNG~\cite{Jenkins96} to initalize all the
+parameters for the GPU version of our PRNG. The implementation of the three
+xor-like PRNGs is straightforward as soon as their parameters have been
+allocated in the GPU memory. Each xor-like PRNGs used works with an internal
+number $x$ which keeps the last generated random numbers. Other internal
+variables are also used by the xor-like PRNGs. More precisely, the
+implementation of the xor128, the xorshift and the xorwow respectively require
+4, 5 and 6 unsigned long as internal variables.
+
+\begin{algorithm}
+
+\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{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*threadIdx+i]\;
+ }
+ store internal variables in InternalVarXorLikeArray[threadIdx]\;
+}
+
+\caption{main kernel for the chaotic iterations based PRNG GPU naive version}
+\label{algo:gpu_kernel}
+\end{algorithm}
+
+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
+PRNGs\footnote{we multiply this number by $2$ in order to count 32-bits numbers}
+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, 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
+PRNGs, so this version is easily usable on a cluster of computer. The only thing
+to ensure is to use a single ISAAC PRNG. For this, a simple solution consists in
+using a master node for the initialization which computes the initial parameters
+for all the differents nodes involves in the computation.
+\end{remark}
+
+\subsection{Improved version for GPU}
+
+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 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.
+
+This version also succeeds to the {\it BigCrush} batteries of tests.
+
+\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 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 including shared memory\;
+ offset = threadIdx\%permutation\_size\;
+ o1 = threadIdx-offset+tab1[offset]\;
+ o2 = threadIdx-offset+tab2[offset]\;
+ \For{i=1 to n} {
+ t=xor-like()\;
+ t=t$\oplus$shmem[o1]$\oplus$shmem[o2]\;
+ shared\_mem[threadId]=t\;
+ x = x $\oplus$ t\;
+
+ store the new PRNG in NewNb[NumThreads*threadId+i]\;
+ }
+ store internal variables in InternalVarXorLikeArray[threadId]\;
+}
+
+\caption{main kernel for the chaotic iterations based PRNG GPU efficient
+version}
+\label{algo:gpu_kernel2}
+\end{algorithm}
+
+\subsection{Theoretical Evaluation of the Improved Version}
+
+A run of Algorithm~\ref{algo:gpu_kernel2} consists in three operations having
+the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative
+system of Eq.~\ref{eq:generalIC}. That is, three iterations of the general chaotic
+iterations are realized between two stored values of the PRNG.
+To be certain that we are in the framework of Theorem~\ref{t:chaos des general},
+we must guarantee that this dynamical system iterates on the space
+$\mathcal{X} = \mathcal{P}\left(\llbracket 1, \mathsf{N} \rrbracket\right)^\mathds{N}\times\mathds{B}^\mathsf{N}$.
+The left term $x$ obviously belongs into $\mathds{B}^ \mathsf{N}$.
+To prevent from any flaws of chaotic properties, we must check that each right
+term, corresponding to terms of the strategies, can possibly be equal to any
+integer of $\llbracket 1, \mathsf{N} \rrbracket$.
+
+Such a result is obvious for the two first lines, as for the xor-like(), all the
+integers belonging into its interval of definition can occur at each iteration.
+It can be easily stated for the two last lines by an immediate mathematical
+induction.
+
+Thus Algorithm~\ref{algo:gpu_kernel2} is a concrete realization of the general
+chaotic iterations presented previously, and for this reason, it satisfies the
+Devaney's formulation of a chaotic behavior.
+
+\section{Experiments}
+\label{sec:experiments}
+
+Different experiments have been performed in order to measure the generation
+speed. We have used a computer equiped with Tesla C1060 NVidia GPU card and an
+Intel Xeon E5530 cadenced at 2.40 GHz for our experiments and we have used
+another one equipped with a less performant CPU and a GeForce GTX 280. Both
+cards have 240 cores.
+
+In Figure~\ref{fig:time_gpu} we compare the number of random numbers generated
+per second. The xor-like prng is a xor64 described in~\cite{Marsaglia2003}. In
+order to obtain the optimal performance we remove the storage of random numbers
+in the GPU memory. This step is time consumming and slows down the random number
+generation. Moreover, if you are interested by applications that consome random
+numbers directly when they are generated, their storage is completely
+useless. In this figure we can see that when the number of threads is greater
+than approximately 30,000 upto 5 millions the number of random numbers generated
+per second is almost constant. With the naive version, it is between 2.5 and
+3GSample/s. With the optimized version, it is approximately equals to
+20GSample/s. Finally we can remark that both GPU cards are quite similar. In
+practice, the Tesla C1060 has more memory than the GTX 280 and this memory
+should be of better quality.
+
+\begin{figure}[htbp]
+\begin{center}
+ \includegraphics[scale=.7]{curve_time_gpu.pdf}
+\end{center}
+\caption{Number of random numbers generated per second}
+\label{fig:time_gpu}
+\end{figure}
+
+
+In comparison, Listing~\ref{algo:seqCIprng} allows us to generate about
+138MSample/s with only one core of the Xeon E5530.
+
+
+
+
+
+\section{The relativity of disorder}
+\label{sec:de la relativité du désordre}
+
+In the next two sections, we investigate the impact of the choices that have
+lead to the definitions of measures in Sections \ref{sec:chaotic iterations} and \ref{deuxième def}.
+
+\subsection{Impact of the topology's finenesse}
+
+Let us firstly introduce the following notations.
+
+\begin{notation}
+$\mathcal{X}_\tau$ will denote the topological space
+$\left(\mathcal{X},\tau\right)$, whereas $\mathcal{V}_\tau (x)$ will be the set
+of all the neighborhoods of $x$ when considering the topology $\tau$ (or simply
+$\mathcal{V} (x)$, if there is no ambiguity).
+\end{notation}
+
+
+
+\begin{theorem}
+\label{Th:chaos et finesse}
+Let $\mathcal{X}$ a set and $\tau, \tau'$ two topologies on $\mathcal{X}$ s.t.
+$\tau'$ is finer than $\tau$. Let $f:\mathcal{X} \to \mathcal{X}$, continuous
+both for $\tau$ and $\tau'$.
+
+If $(\mathcal{X}_{\tau'},f)$ is chaotic according to Devaney, then
+$(\mathcal{X}_\tau,f)$ is chaotic too.
+\end{theorem}
+
+\begin{proof}
+Let us firstly establish the transitivity of $(\mathcal{X}_\tau,f)$.
+
+Let $\omega_1, \omega_2$ two open sets of $\tau$. Then $\omega_1, \omega_2 \in
+\tau'$, becaus $\tau'$ is finer than $\tau$. As $f$ is $\tau'-$transitive, we
+can deduce that $\exists n \in \mathds{N}, \omega_1 \cap f^{(n)}(\omega_2) =
+\varnothing$. Consequently, $f$ is $\tau-$transitive.
+
+Let us now consider the regularity of $(\mathcal{X}_\tau,f)$, \emph{i.e.}, for
+all $x \in \mathcal{X}$, and for all $\tau-$neighborhood $V$ of $x$, there is a
+periodic point for $f$ into $V$.
+
+Let $x \in \mathcal{X}$ and $V \in \mathcal{V}_\tau (x)$ a $\tau-$neighborhood
+of $x$. By definition, $\exists \omega \in \tau, x \in \omega \subset V$.
+
+But $\tau \subset \tau'$, so $\omega \in \tau'$, and then $V \in
+\mathcal{V}_{\tau'} (x)$. As $(\mathcal{X}_{\tau'},f)$ is regular, there is a
+periodic point for $f$ into $V$, and the regularity of $(\mathcal{X}_\tau,f)$ is
+proven.
+\end{proof}
+
+\subsection{A given system can always be claimed as chaotic}
+
+Let $f$ an iteration function on $\mathcal{X}$ having at least a fixed point.
+Then this function is chaotic (in a certain way):
+
+\begin{theorem}
+Let $\mathcal{X}$ a nonempty set and $f: \mathcal{X} \to \X$ a function having
+at least a fixed point.
+Then $f$ is $\tau_0-$chaotic, where $\tau_0$ is the trivial (indiscrete)
+topology on $\X$.
+\end{theorem}
+
+
+\begin{proof}
+$f$ is transitive when $\forall \omega, \omega' \in \tau_0 \setminus
+\{\varnothing\}, \exists n \in \mathds{N}, f^{(n)}(\omega) \cap \omega' \neq
+\varnothing$.
+As $\tau_0 = \left\{ \varnothing, \X \right\}$, this is equivalent to look for
+an integer $n$ s.t. $f^{(n)}\left( \X \right) \cap \X \neq \varnothing$. For
+instance, $n=0$ is appropriate.
+
+Let us now consider $x \in \X$ and $V \in \mathcal{V}_{\tau_0} (x)$. Then $V =
+\mathcal{X}$, so $V$ has at least a fixed point for $f$. Consequently $f$ is
+regular, and the result is established.
+\end{proof}
+
+
+
+
+\subsection{A given system can always be claimed as non-chaotic}
+
+\begin{theorem}
+Let $\mathcal{X}$ be a set and $f: \mathcal{X} \to \X$.
+If $\X$ is infinite, then $\left( \X_{\tau_\infty}, f\right)$ is not chaotic
+(for the Devaney's formulation), where $\tau_\infty$ is the discrete topology.
+\end{theorem}
+
+\begin{proof}
+Let us prove it by contradiction, assuming that $\left(\X_{\tau_\infty},
+f\right)$ is both transitive and regular.
+
+Let $x \in \X$ and $\{x\}$ one of its neighborhood. This neighborhood must
+contain a periodic point for $f$, if we want that $\left(\X_{\tau_\infty},
+f\right)$ is regular. Then $x$ must be a periodic point of $f$.
+
+Let $I_x = \left\{ f^{(n)}(x), n \in \mathds{N}\right\}$. This set is finite
+because $x$ is periodic, and $\mathcal{X}$ is infinite, then $\exists y \in
+\mathcal{X}, y \notin I_x$.
+
+As $\left(\X_{\tau_\infty}, f\right)$ must be transitive, for all open nonempty
+sets $A$ and $B$, an integer $n$ must satisfy $f^{(n)}(A) \cap B \neq
+\varnothing$. However $\{x\}$ and $\{y\}$ are open sets and $y \notin I_x
+\Rightarrow \forall n, f^{(n)}\left( \{x\} \right) \cap \{y\} = \varnothing$.
+\end{proof}
+
+
+
+
+
+
+\section{Chaos on the order topology}
+\label{sec: chaos order topology}
+\subsection{The phase space is an interval of the real line}
+
+\subsubsection{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{equation}
+ \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}
+\end{equation}
+where $\varphi\left((S,E)\right)$ is the real number:
