Titre: Génération de nombres pseudo-aléatoires suivant une distribution non-uniforme par circuits intégrés programmables

Auteurs: TAREK OULD BACHIR

Ecole/Université: UNIVERSITÉ DE MONTRÉAL

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éfis, principalement dus aux difficultés que posent l’évaluation de fonctions transcendentales telles que le logarithme, l’exponentielle et les fonctions trigonométriques. Les technique qui ont cours aujourd’hui tentent de câbler les algorithmes connus et d’optimiser leur implémentation sur FPGA par des artifices de calcul tels que l’interpolation polynomiale, 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 distributions 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 comportement 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.

Extrait du sommaire: Voir le document

Cours accéleration matérielle (14)

Télécharger le fichier PDF: Génération de nombres pseudo-aléatoires suivant une distribution non-uniforme par circuits intégrés programmables