CUDA : cours    travaux pratiques

Sommaire

Travaux dirigés et pratiques

7. TD/TP Nombres Auto-Descriptif

7.1. Introduction

Un nombre auto-descriptif se définit comme un entier naturel ayant pour propriété que chacun de ses chiffres repéré par son rang indique combien de fois ce rang apparaît en tant que chiffre dans l'écriture de ce nombre. On parle aussi de nombre autobiographique ou de nombre qui se décrit lui-même. Le premier nombre auto-descriptif est $1210$. En effet :

Il en va de même pour $2020$, $21200$. Ces nombres sont très rares, on en compte 7 dont la liste figure table suivante :

 n   a(n) 
 1   1_210 
 2   2_020 
 3   21_200 
 4   3_211_000 
 5   42_101_000 
 6   521_001_000 
 7   6_210_001_000 
Nombres auto-descriptifs

7.2. Version CPU

Ecrire un programme C++ qui permet de rechercher les nombres autodescriptifs entre 0 et 522_240_000 ($= 510 * 1024 * 1000$). On utilisera la fonction suivante pour déterminer si un nombre est ou n'est pas auto-descriptif :

  1. #include <stdint.h>
  2. #include <iostream>
  3. #include <sstream>
  4. #include <cstdlib>
  5. #include <iomanip>
  6. using namespace std;
  7.  
  8. // ------------------------------------
  9. // definition of types
  10. // ------------------------------------
  11. typedef uint8_t u8;
  12. typedef int32_t i32;
  13. typedef uint32_t u32;
  14.  
  15. /**
  16.  * Version C - is_autod_32b
  17.  * - on convertit l'entier non signé en chaine avec sprintf
  18.  * - on compte les occurrences de chaque chiffre
  19.  * - on compare les occurrences avec les chiffres de la chaine
  20.  * - on travaille avec un tableau d'etniers non signés ***
  21.  *
  22.  */
  23. bool is_autod_32b( u32 x ) {
  24.     u32 counts[ 10 ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  25.     u32 digits[ 10 ];
  26.    
  27.     if (x == 0) return false;
  28.    
  29.     i32 i = 0;
  30.     while (x) {
  31.         u32 u = x % 10;
  32.         digits[ i++ ] = u;
  33.         ++counts[ u ];
  34.         x = x / 10;
  35.     }
  36.    
  37.     i32 j;
  38.     for (j = 0, --i; i >= 0; --i, ++j) {
  39.         if (digits[ i ] != counts[ j ]) return false;
  40.     }
  41.    
  42.     return true;
  43.    
  44. }

Afin de pouvoir paralléliser le traitement et le comparer à une implantation CUDA, nous allons créer un tableau de 522_240_000 booléens nommé is_autod dont le ième élément sera vrai si $i$ est un nombre auto-descriptif.

Une fois le traitement terminé, on parcourra le tableau afin d'afficher les nombres auto-descriptifs.

Quel temps d'exécution séquentiel sur CPU obtient-on ?

7.3. Version CPU Parallèle

Paralléliser le code en utilisant OpenMP.

Quel temps d'exécution parallèle sur CPU obtient-on ?

Faire varier le nombre de coeurs utilisés pour la résolution parmi 2, 4 et 8, voire 16 si vous disposez d'un octo-core avec SMT.

7.4. Version GPU 1

Ecrire une version CUDA dans laquelle le kernel is_autod_32b prend en paramètre le tableau de booléens is_autod et met à vrai is_autod[ i ] si i est un nombre auto-descriptif.

Quel temps d'exécution parallèle sur GPU obtient-on ?

7.5. Version GPU 2

Que se passe t-il si on procède en plusieurs fois ? Plutôt que d'utiliser un tableau de 522_240_000 éléments, on effectue 510 fois le calcul de 1_024_000 éléments.