Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITÉ DE MONTRÉAL GÉNÉRATION DE NOMBRES PSEUDO-ALÉATOIRES SUIVANT UNE DIST

UNIVERSITÉ DE MONTRÉAL GÉNÉRATION DE NOMBRES PSEUDO-ALÉATOIRES SUIVANT UNE DISTRIBUTION NON-UNIFORME PAR CIRCUITS INTÉGRÉS PROGRAMMABLES TAREK OULD BACHIR DÉPARTEMENT DE GÉNIE ÉLECTRIQUE ÉCOLE POLYTECHNIQUE DE MONTRÉAL MÉMOIRE PRÉSENTÉ EN VUE DE L’OBTENTION DU DIPLÔME DE MAÎTRISE ÈS SCIENCES APPLIQUÉES (MICROÉLECTRONIQUE) AOÛT 2008 c ⃝Tarek Ould Bachir, 2008. UNIVERSITÉ DE MONTRÉAL ÉCOLE POLYTECHNIQUE DE MONTRÉAL Ce mémoire intitulé: GÉNÉRATION DE NOMBRES PSEUDO-ALÉATOIRES SUIVANT UNE DISTRIBUTION NON-UNIFORME PAR CIRCUITS INTÉGRÉS PROGRAMMABLES présenté par: OULD BACHIR Tarek en vue de l’obtention du diplôme de: Maîtrise ès sciences appliquées a été dûment accepté par le jury d’examen constitué de: M. DAVID Jean-Pierre, Ph.D., président M. SAWAN Mohamad, Ph.D., membre et directeur de recherche M. BRAULT Jean-Jules, Ph.D., membre iv Science is the belief in the ignorance of experts. – Richard Feynman v REMERCIEMENTS Les remerciements qui suivent s’adressent à toutes ces personnes qui, de près ou de loin, m’ont aidé à faire d’une idée griffonnée sur une feuille de papier un sujet de recherche sérieux. Aussi, une pensée particulière est adressée au professeur Sawan, mon directeur de recherche, qui m’a donné la liberté de poursuivre mes chimères avec l’assurance de sa patience, de son appui intellectuel et matériel. C’est grâce à son ouverture d’esprit aux idées nouvelles et grâce aux moyens dont dispose son laboratoire Polystim que ce travail a pu être mené à bien et je ne trouverai jamais les mots pour exprimer toute ma gratitude. J’aimerais aussi adresser mes remerciements aux professeurs Jean-Pierre David et Jean-Jules Brault qui, en plus d’accepter de payer de leur temps et de siéger sur mon jury, ont eu l’amabilité de me gratiﬁer de leurs conseils et suggestions durant la pour- suite de mes travaux. Leurs contributions informelles à elles seules sufﬁsent pour me laisser penser que le monde académique a encore pour lui la force du travail collégial qui manque tant à l’industrie. Qu’ils sachent à quel point j’ai pu estimer leur aide pré- cieuse et apprécié que nos discussions franches et honnêtes n’aient jamais été précédées par la signature de NDA... J’aimerais aussi remercier les étudiants stagiaires qui ont contribué par leurs efforts à donner chair à certaines technicalités de ce travail. Je pense particulièrement à Laurent Faniel, Majed Benmahfoudh, Jonathan Boisvert et Laurent Wacker. Leur aide a été sub- stantielle et les citer ici va de soi. J’aimerais remercier les étudiants du laboratoire Polystim qui ont su me faire une place dans le cercle des étudiants du GRM. Ils ont su créer une atmosphère propice à rendre moins gris les couloirs des bibliothèques et instaurer un climat de camaraderie chaleu- reuse de par leur vie sociale active. Je pense particulièrement à Jonathan Coulomb, dont l’érudition et l’articulation scientiﬁque m’ont plus que béniﬁcié, je pense à Amer-Elias Ayoub, lui qui garde le sourire en toutes les circonstances (et on sait parfois lesquelles !) vi et qui se les dore aujourd’hui à Antibes, je pense à Félix Chénier, lui qui n’a pas rechi- gné à aller se les geler pour accompagner sous la pluie un fumeur déshérité et ﬁnalement — bien sûr ! — Roula Ghannoum qui battra cette année le record des citations dans la section des remerciements. Je ne pourrais manquer de remercier les amis et les proches qui ont largement fait la preuve de leur indéfectible appui. À chacun d’eux revient une petite phrase qui ponctue mon parcours : Guillaume Pichenot qui préconisait « Fonce ! » au moment de faire le saut vers ce sujet de recherche, Imad Saﬁqui me raillait en me disant « Ça t’a pris trois ans et demi pour faire un bac et un Pierre Laurent pour faire ta maîtrise » , Kamila Belhocine et son interjection « Vous soutenez la maîtrise ? » et puis, ﬁnalement, ma petite Fanny Lalonde qui ne cachait pas son impatience avec son inoubliable « J’ai hâte que ça ﬁnisse ». À quoi j’espère répondre aujourd’hui : « Voilà, c’est ﬁni. » vii RÉSUMÉ L’accélération matérielle au moyen de la technologie FPGA connaît un intérêt croissant dans le domaine du calcul à haute performance. Cet intérêt est motivé par les possibilités dynamiques de ces dispositifs et par leur capacité à paralléliser les calculs. Dans le cas des méthodes de Monte Carlo, il a été démontré que les FPGA permettent d’accélérer les calculs par plusieurs ordres de grandeurs. Ce fait a stimulé l’activité de recherche portant sur les architectures matérielles des générateurs de nombres aléatoires issus de distributions non-uniformes qui, jusqu’alors, n’avaient été que marginales. La génération de distributions non-uniformes en matériel comporte plusieurs déﬁs, prin- cipalement dus aux difﬁcultés que posent l’évaluation de fonctions transcendentales telles que le logarithme, l’exponentielle et les fonctions trigonométriques. Les tech- niques qui ont cours aujourd’hui tentent de câbler les algorithmes connus et d’optimiser leur implémentation sur FPGA par des artiﬁces de calcul tels que l’interpolation poly- nomiale, le recours aux architectures Cordic ou encore l’approximation linéaire à base d’une segmentation non-linéaire. Le présent travail propose d’explorer un nouvel algorithme de génération des distribu- tions non-uniformes qui part du principe que la génération d’une variable aléatoire peut se faire un bit à la fois. Cette méthode prend tout son sens quand on songe que tous les bits peuvent être générés simultanément dans un circuit numérique. Nous posons alors le modèle mathématique associé à cet algorithme et mesurons l’étendue de ses capacités. De là, nous aboutissons à une architecture matérielle générale et universelle que nous déclinons pour les distributions normale et exponentielle. Nous étudions alors le com- portement empirique sur FPGA de ces générateurs, tant du point de vue des propriétés statistiques que des critères qualitatifs telle que la corrélation sérielle, le tout avec des résultats concluants. viii ABSTRACT Hardware acceleration by means of FPGA technology is of growing interest to the realm of High Peformance Computing. This interest is justiﬁed by the dynamic possibilities of these devices and their capacity to parallelize computation. Numerous work have been recently done providing positive insights that Monte Carlo methods can be enhanced by the resort to FPGAs – from a speed performance point of view. This fact has stimulated the research for hardware non-uniform variate generators which hitherto had only been marginal. Hardware non-uniform variates generation comprises several challenges, mainly the eva- luation of transcendental functions such as the logarithm, sine, cosine and the exponen- tial functions. The techniques suggested up to now try to wire the known algorithms and to optimize their implementation on FPGA by digital methods such as polynomial interpolation, Cordic implementation and non-linear segmentation. We rather suggest an investigation path towards an algorithm generating the non-uniform variate one bit at a time. The algorithm is hardware-dedicated since all bits can be gene- rated in parallel in a digital circuit. We thus introduce the mathematical model associated with this algorithm and measure the extent of its application. We then suggest a generic and universal architecture that we optimize for the normal and exponential distributions. The empirical behavior of our design is implemented on FPGA and considered as well from the statistical point of view as of qualitative criteria such as the serial correlation, the whole with conclusive results. ix TABLE DES MATIÈRES REMERCIEMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v RÉSUMÉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii TABLE DES MATIÈRES . . . . . . . . . . . . . . . . . . . . . . . . . . . ix LISTE DES FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii LISTE DES TABLEAUX . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv LISTE DES ANNEXES . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi LISTE DES NOTATIONS ET DES SYMBOLES . . . . . . . . . . . . . . . . xvii INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 CHAPITRE 1 NOTIONS DE BASE DES GÉNÉRATEURS ALÉATOIRES . 4 1.1 Préambule au propos . . . . . . . . . . . . uploads/Geographie/ generation-de-nombres-pseudoaleatoires.pdf