From a9f4a14a06edf88832d058ec85346ff66bd171b4 Mon Sep 17 00:00:00 2001 From: couturie Date: Sun, 17 Feb 2013 18:20:14 +0100 Subject: [PATCH 1/1] new --- BookGPU/BookGPU.tex | 26 ++++----- BookGPU/Chapters/chapter16/ch16.aux | 4 +- BookGPU/Chapters/chapter18/biblio.bib | 68 ++++++++++++++---------- BookGPU/Chapters/chapter18/ch18.aux | 76 ++++++++++++++------------- BookGPU/Chapters/chapter18/ch18.tex | 16 +++++- BookGPU/Makefile | 22 ++++---- 6 files changed, 120 insertions(+), 92 deletions(-) diff --git a/BookGPU/BookGPU.tex b/BookGPU/BookGPU.tex index 92b09d1..0b7f5cf 100755 --- a/BookGPU/BookGPU.tex +++ b/BookGPU/BookGPU.tex @@ -138,19 +138,19 @@ \setcounter{page}{1} \part{This is a Part} -\include{Chapters/chapter1/ch1} -\include{Chapters/chapter2/ch2} -\include{Chapters/chapter3/ch3} -\include{Chapters/chapter5/ch5} -\include{Chapters/chapter6/ch6} -\include{Chapters/chapter7/ch7} -\include{Chapters/chapter8/ch8} -\include{Chapters/chapter9/ch9} -\include{Chapters/chapter11/ch11} -\include{Chapters/chapter14/ch14} -\include{Chapters/chapter15/ch15} -\include{Chapters/chapter16/ch16} -\include{Chapters/chapter18/ch18} +%%\include{Chapters/chapter1/ch1} +%% \include{Chapters/chapter2/ch2} +%% \include{Chapters/chapter3/ch3} +%% \include{Chapters/chapter5/ch5} +%% \include{Chapters/chapter6/ch6} +%% \include{Chapters/chapter7/ch7} +%% \include{Chapters/chapter8/ch8} +%% \include{Chapters/chapter9/ch9} +%% \include{Chapters/chapter11/ch11} +%% \include{Chapters/chapter14/ch14} +%% \include{Chapters/chapter15/ch15} +%% \include{Chapters/chapter16/ch16} + \include{Chapters/chapter18/ch18} \bibliographystyle{hep} %%%\bibliography{biblio} diff --git a/BookGPU/Chapters/chapter16/ch16.aux b/BookGPU/Chapters/chapter16/ch16.aux index f3f5e6a..27e999a 100644 --- a/BookGPU/Chapters/chapter16/ch16.aux +++ b/BookGPU/Chapters/chapter16/ch16.aux @@ -69,12 +69,12 @@ \@writefile{toc}{\contentsline {section}{\numberline {13.6}Glossary}{304}} \@writefile{toc}{\contentsline {section}{Bibliography}{304}} \@setckpt{Chapters/chapter16/ch16}{ -\setcounter{page}{305} +\setcounter{page}{306} \setcounter{equation}{9} \setcounter{enumi}{2} \setcounter{enumii}{0} \setcounter{enumiii}{0} -\setcounter{enumiv}{0} +\setcounter{enumiv}{22} \setcounter{footnote}{0} \setcounter{mpfootnote}{0} \setcounter{part}{1} diff --git a/BookGPU/Chapters/chapter18/biblio.bib b/BookGPU/Chapters/chapter18/biblio.bib index f3b0ccc..911369e 100644 --- a/BookGPU/Chapters/chapter18/biblio.bib +++ b/BookGPU/Chapters/chapter18/biblio.bib @@ -1,35 +1,47 @@ -@misc{ch1:cuda, - author = {{NVIDIA Corporation}}, - keywords = {CUDA}, - note = {Version 4.0}, - title = {{NVIDIA CUDA C} Programming Guide}, - year = 2011 +@BOOK{devaney, + title = {An Introduction to Chaotic Dynamical Systems}, + publisher = {Addison-Wesley}, + year = {1989}, + author = {Devaney, R. L.}, + address = {Redwood City, CA}, + edition = {2nd} } -@Article{ch1:Buck:2004:BGS, - author = "I. Buck and T. Foley and D. Horn and J. - Sugerman and K. Fatahalian and M. Houston and P. - Hanrahan", - title = "{Brook} for {GPUs}: stream computing on graphics - hardware", - journal = "ACM Transactions on Graphics", - volume = "23", - number = "3", - pages = "777--786", - month = aug, - year = "2004", +@ARTICLE{Marsaglia2003, + author = {G. Marsaglia}, + title = {Xorshift RNGs}, + journal = {Journal of Statistical Software}, + year = {2003}, + volume = {8(14)}, + pages = {1--6}, + timestamp = {2009.10.28} } - -@article{ch1:CMR:12, - author = "B. Cloutier and B. K. Muite and P. Rigge", - title = "A comparison of CPU and GPU performance for Fourier pseudospectral simulations of the Navier-Stokes, Cubic Nonlinear Schrödinger and Sine Gordon Equations", - journal = "Computational Physics (physics.comp-ph)", - year = "2012", - archivePrefix = "arXiv", - eprint = "1206.3215", - primaryClass = "physics.comp-ph", +@Article{LEcuyerS07, + title = "Test{U01}: {A} {C} library for empirical testing of + random number generators", + author = "P. L'Ecuyer and R. J. Simard", + journal = "ACM Trans. Math. Softw", + year = "2007", + number = "4", + volume = "33", + bibdate = "2007-11-06", + bibsource = "DBLP, + http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07", + URL = "http://doi.acm.org/10.1145/1268776.1268777", } +@manual{Nvid10, + author = {Nvidia}, + title = {Cuda cublas library}, + year = {2011}, + Note = {Version 4.0}, + } - +@InProceedings{Jenkins96, + author = "R. J. Jenkins", + title = "{ISAAC}", + booktitle = "IWFSE: International Workshop on Fast Software + Encryption, LNCS", + year = "1996", +} \ No newline at end of file diff --git a/BookGPU/Chapters/chapter18/ch18.aux b/BookGPU/Chapters/chapter18/ch18.aux index f9f97ae..d4decdf 100644 --- a/BookGPU/Chapters/chapter18/ch18.aux +++ b/BookGPU/Chapters/chapter18/ch18.aux @@ -2,46 +2,48 @@ \@writefile{toc}{\author{Rapha\IeC {\"e}l Couturier}{}} \@writefile{toc}{\author{Christophe Guyeux}{}} \@writefile{loa}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {chapter}{\numberline {14}Pseudo Random Number Generator on GPU}{305}} +\@writefile{toc}{\contentsline {chapter}{\numberline {1}Pseudo Random Number Generator on GPU}{3}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\newlabel{chapter18}{{14}{305}} -\@writefile{toc}{\contentsline {section}{\numberline {14.1}Introduction}{305}} -\@writefile{toc}{\contentsline {section}{\numberline {14.2}Basic Recalls}{306}} -\newlabel{section:BASIC RECALLS}{{14.2}{306}} -\@writefile{toc}{\contentsline {subsection}{\numberline {14.2.1}Devaney's Chaotic Dynamical Systems}{306}} -\@writefile{toc}{\contentsline {section}{\numberline {14.3}Toward Efficiency and Improvement for CI PRNG}{306}} -\newlabel{sec:efficient PRNG}{{14.3}{306}} -\@writefile{toc}{\contentsline {subsection}{\numberline {14.3.1}First Efficient Implementation of a PRNG based on Chaotic Iterations}{306}} -\newlabel{algo:seqCIPRNG}{{14.1}{306}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {14.1}C code of the sequential PRNG based on chaotic iterations}{306}} -\@writefile{toc}{\contentsline {subsection}{\numberline {14.3.2}Efficient PRNGs based on Chaotic Iterations on GPU}{307}} -\newlabel{sec:efficient PRNG gpu}{{14.3.2}{307}} -\@writefile{toc}{\contentsline {subsection}{\numberline {14.3.3}Naive Version for GPU}{307}} -\@writefile{loa}{\contentsline {algocf}{\numberline {12}{\ignorespaces Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations\relax }}{308}} -\newlabel{algo:gpu_kernel}{{12}{308}} -\@writefile{toc}{\contentsline {subsection}{\numberline {14.3.4}Improved Version for GPU}{308}} -\newlabel{IR}{{13}{309}} -\@writefile{loa}{\contentsline {algocf}{\numberline {13}{\ignorespaces Main kernel for the chaotic iterations based PRNG GPU efficient version\relax }}{309}} -\newlabel{algo:gpu_kernel2}{{13}{309}} -\@writefile{toc}{\contentsline {subsection}{\numberline {14.3.5}Chaos Evaluation of the Improved Version}{309}} -\@writefile{toc}{\contentsline {section}{\numberline {14.4}Experiments}{310}} -\newlabel{sec:experiments}{{14.4}{310}} -\@writefile{lof}{\contentsline {figure}{\numberline {14.1}{\ignorespaces Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG\relax }}{311}} -\newlabel{fig:time_xorlike_gpu}{{14.1}{311}} -\@writefile{lof}{\contentsline {figure}{\numberline {14.2}{\ignorespaces Quantity of pseudorandom numbers generated per second using the BBS-based PRNG\relax }}{312}} -\newlabel{fig:time_bbs_gpu}{{14.2}{312}} +\newlabel{chapter18}{{1}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {1.1}Introduction}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {1.2}Basic Recalls}{4}} +\newlabel{section:BASIC RECALLS}{{1.2}{4}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.1}Devaney's Chaotic Dynamical Systems}{5}} +\@writefile{toc}{\contentsline {section}{\numberline {1.3}Toward Efficiency and Improvement for CI PRNG}{5}} +\newlabel{sec:efficient PRNG}{{1.3}{5}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.1}First Efficient Implementation of a PRNG based on Chaotic Iterations}{5}} +\newlabel{algo:seqCIPRNG}{{1.1}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {1.1}C code of the sequential PRNG based on chaotic iterations}{5}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.2}Efficient PRNGs based on Chaotic Iterations on GPU}{5}} +\newlabel{sec:efficient PRNG gpu}{{1.3.2}{5}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.3}Naive Version for GPU}{6}} +\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations\relax }}{6}} +\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}} +\newlabel{algo:gpu_kernel}{{1}{6}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.4}Improved Version for GPU}{7}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.5}Chaos Evaluation of the Improved Version}{7}} +\newlabel{IR}{{2}{8}} +\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Main kernel for the chaotic iterations based PRNG GPU efficient version\relax }}{8}} +\newlabel{algo:gpu_kernel2}{{2}{8}} +\@writefile{toc}{\contentsline {section}{\numberline {1.4}Experiments}{8}} +\newlabel{sec:experiments}{{1.4}{8}} +\@writefile{lof}{\contentsline {figure}{\numberline {1.1}{\ignorespaces Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG\relax }}{9}} +\newlabel{fig:time_xorlike_gpu}{{1.1}{9}} +\@writefile{lof}{\contentsline {figure}{\numberline {1.2}{\ignorespaces Quantity of pseudorandom numbers generated per second using the BBS-based PRNG\relax }}{10}} +\newlabel{fig:time_bbs_gpu}{{1.2}{10}} +\@writefile{toc}{\contentsline {section}{Bibliography}{11}} \@setckpt{Chapters/chapter18/ch18}{ -\setcounter{page}{313} +\setcounter{page}{12} \setcounter{equation}{0} -\setcounter{enumi}{2} +\setcounter{enumi}{0} \setcounter{enumii}{0} \setcounter{enumiii}{0} -\setcounter{enumiv}{0} +\setcounter{enumiv}{5} \setcounter{footnote}{2} \setcounter{mpfootnote}{0} \setcounter{part}{1} -\setcounter{chapter}{14} +\setcounter{chapter}{1} \setcounter{section}{4} \setcounter{subsection}{0} \setcounter{subsubsection}{0} @@ -50,7 +52,7 @@ \setcounter{figure}{2} \setcounter{table}{0} \setcounter{numauthors}{0} -\setcounter{parentequation}{4} +\setcounter{parentequation}{0} \setcounter{subfigure}{0} \setcounter{lofdepth}{1} \setcounter{subtable}{0} @@ -58,14 +60,14 @@ \setcounter{lstnumber}{15} \setcounter{ContinuedFloat}{0} \setcounter{AlgoLine}{14} -\setcounter{algocfline}{13} -\setcounter{algocfproc}{13} -\setcounter{algocf}{13} -\setcounter{proposition}{1} +\setcounter{algocfline}{2} +\setcounter{algocfproc}{2} +\setcounter{algocf}{2} +\setcounter{proposition}{0} \setcounter{theorem}{0} \setcounter{exercise}{0} \setcounter{example}{0} \setcounter{definition}{0} -\setcounter{proof}{1} +\setcounter{proof}{0} \setcounter{lstlisting}{1} } diff --git a/BookGPU/Chapters/chapter18/ch18.tex b/BookGPU/Chapters/chapter18/ch18.tex index 3808995..b4401c9 100755 --- a/BookGPU/Chapters/chapter18/ch18.tex +++ b/BookGPU/Chapters/chapter18/ch18.tex @@ -50,7 +50,21 @@ Furthermore, authors of such chaotic generators often claim their PRNG as secure due to their chaos properties, but there is no obvious relation between chaos and security as it is understood in cryptography. This is why the use of chaos for PRNG still remains marginal and disputable. - +Let us finish this paragraph by noticing that, in this paper, +statistical perfection refers to the ability to pass the whole +{\it BigCrush} battery of tests, which is widely considered as the most +stringent statistical evaluation of a sequence claimed as random. +This battery can be found in the well-known TestU01 package~\cite{LEcuyerS07}. +More precisely, each time we performed a test on a PRNG, we ran it +twice in order to observe if all $p-$values are inside [0.01, 0.99]. In +fact, we observed that few $p-$values (less than ten) are sometimes +outside this interval but inside [0.001, 0.999], so that is why a +second run allows us to confirm that the values outside are not for +the same test. With this approach all our PRNGs pass the {\it + BigCrush} successfully and all $p-$values are at least once inside +[0.01, 0.99]. +Chaos, for its part, refers to the well-established definition of a +chaotic dynamical system defined by Devaney~\cite{Devaney}. The remainder of this paper is organized as follows. A COMPLETER diff --git a/BookGPU/Makefile b/BookGPU/Makefile index e3aa930..d23f8c5 100644 --- a/BookGPU/Makefile +++ b/BookGPU/Makefile @@ -5,17 +5,17 @@ all: pdflatex ${BOOK} pdflatex ${BOOK} bibtex bu1 - bibtex bu2 - bibtex bu3 - bibtex bu4 - bibtex bu5 - bibtex bu6 - bibtex bu7 - bibtex bu8 - bibtex bu9 -#don't put chapter 14, refs are included - bibtex bu11 -# bibtex bu12 +# bibtex bu2 +# bibtex bu3 +# bibtex bu4 +# bibtex bu5 +# bibtex bu6 +# bibtex bu7 +# bibtex bu8 +# bibtex bu9 +# #don't put chapter 14, refs are included +# bibtex bu11 +# bibtex bu12 makeindex ${BOOK}.idx pdflatex ${BOOK} -- 2.39.5