Acceler8 : Solution au problème des Smallbrain Numbers

Dans cet article, nous, Fabien ARCELLIER et Maxime RIVIERE, allons vous décrire notre solution afin de répondre au premier problème proposé par Intel dans le cadre du concours Acceler8.


Vous trouverez au pied de cet article une archive reprenant le code source de notre programme ainsi que le ReadMe associé à notre livrable.



Introduction


La finalité de ce problème était de trouver les nombres Narcissiques ou nombres d'Armstrong (ici appelés Smallbrain Numbers) entre 1 et 263 -1 (= 9223372036854775807). Un nombre narcissique étant un nombre dont la somme de ces chiffres élevés à une puissance N est le nombre lui même (considérant N comme le nombre de chiffres composant le nombre).


L’utilisateur configure ici deux paramètres à l’exécution :

- la borne inférieure de l’espace de calcul

- la borne supérieure de l’espace de calcul

 

Il exécute donc par exemple la commande :

./Smallbrain 1 371


On recherche donc ici tous les smallbrain number entre 1 et 371.


Une des solutions est 370, répondant à l’équation suivante :


Exemple_calcul.JPG


Notre programme doit répondre à 2 exigences :

- Trouver toutes les solutions valides sur l’intervalle en un minimum de temps,

- Profiter au maximum d’une machine multiprocesseurs (la MTL mise à disposition par Intel en contient 32)


Les languages Fortran et C++ nous étant totalement inconnus, nous nous sommes dirigés vers un langage dans lequel nous étions plus à l'aise, c'est à dire le C. Nous savions que nous pourrions être limités par l'impossibilité d'utiliser certaines librairies C++ telles que TBB mais l'apprentissage du C++ dans un délai si court ne nous semblait pas envisageable.



I. Première Approche

 

Afin d’étudier la faisabilité du programme, nous nous sommes tout d’abord lancés dans une approche totalement naïve du problème. Après un code rapide rédigé en une paire d’heures, nous nous sommes aperçus que mathématiquement les opérations à réaliser étaient élémentaires mais nombreuses. Il était donc impossible de garder cette approche, sous peine de devoir attendre un demi-siècle avant la totale résolution du problème.

 

C’est alors que nous avons pu réfléchir aux premières simplifications mathématiques et algorithmiques.

 

 

Existence de Collisions :


Considérant un nombre comme un tableau d’éléments, on remarque que lorsque l’on permute ces éléments, on fabrique un nombre différent dont la somme des chiffres élevés à la puissance est égale à celle du nombre d’origine. Par conséquent, nous pouvons diminuer considérablement le nombre de combinaisons à tester sur la totalité de l'espace de recherche.


Exemple avec les chiffres 3, 7, 1 :

exemple_combinaisons.JPG



Mise en place de cache de puissances:


Afin de ne pas réaliser en permanence des calculs de puissance identiques, impliquant une lourde charge au processeur, nous fabriquons lors du lancement du programme un cache des puissances de 0 à 9 pour tous les exposants correspondant à notre besoin.


A la suite de ces simplifications le principe était de naviguer entre les combinaisons uniques et ainsi vérifier si celle-ci répond à l’équation suivant définissant un Smallbrain Number :


equation_smallbrain.JPG

 

 

II. Difficultés pour paralléliser et optimisation trouvée


Suite à cette approche, nous avons souhaité tester le code en le parallélisant et en l’exécutant sur la MTL.


Nous avons alors été confrontés à un problème de taille, plus on rajoutait de processeurs pour exécuter notre programme plus il mettait de temps à s’exécuter. Cela était dû à des tâches de poids différents  et donc de très petits calculs étaient parfois faits dans un thread dédié. Nous avions donc plus de temps de fabrication de thread que d’exécution de celui-ci.


Afin de résoudre ce problème nous avons décidé de réaliser les opérations suivantes.



Mise en cache des combinaisons uniques :


On fabrique à l’exécution du programme un cache contenant l’ensemble des combinaisons uniques sur l'espace de recherche récupéré en paramètre. De cette façon, nous allons pouvoir naviguer dans celui-ci à l’aide d’une simple boucle for.

 

Afin de fabriquer les combinaisons uniques nous avons suivi une équation de la forme :


combinaisons_uniques.JPG

 

n représentant le nème digit d’un nombre. Par exemple, dans 371, 7 est le 2ème digit.


Cette équation nous permet donc de sans cesse construire la combinaison suivante sans jamais obtenir des combinaisons non uniques.


A travers cette création de combinaisons, l’on observe sur le graphique suivant une diminution considérable du nombre de combinaisons à traiter, au fur et à mesure que l'on augmente le nombre de digit.


temps_combinaisons.JPG



Vérification d’un nombre :


Afin de vérifier qu’un nombre est réellement un smallbrain number, nous réalisons l’intersection de notre combinaison avec le nombre génèré lors de la somme des puissances. L’intersection de ces deux tableaux doit être complète (tous les éléments sont présents dans chacun des tableaux) si l’on souhaite pouvoir affirmer que notre nombre est effectivement un smallbrain number.


Exemple :

La combinaison 1, 3, 7 génère le nombre 371.

L’on découpe le nombre 371 en tableau et on obtient la combinaison 3, 7, 1.

Après intersection des deux combinaisons 1,3,7 et 3,7,1, l’on retrouve chacun des éléments des deux côtés, 371 est donc un Smallbrain Number.



III. Performances et mise en parallèle


A l’aide des optimisations effectuées dans le paragraphe précédent, nous avons pu constituer une simple boucle « for » parcourant l’ensemble des combinaisons uniques de notre espace de recherche.


Nous avons alors mis en place une parallélisation de notre code très simple avec Open MP. Cette mise en parallèle, nous permet d’avoir en permanence des processus de même poids et l’on obtient alors une mise en parallèle efficace, comme nous le montre le graphique suivant, représentant le temps d’exécution sur le plus grand espace de recherche possible suivant le nombre de processeurs alloués au programme.



temps_processeurs.JPG

 

 

Nous sommes conscients que notre totale méconnaissance de la programmation parallèle nous a fortement desservi au cours de ce problème, puisque nous nous sommes dirigés vers ce qui nous semblait le plus simple pour paralléliser nos tâches plutôt que le plus efficace.


Avec le recul et l’expérience du second problème, nous aurions certainement adopté une autre approche plus adaptée et nous permettant de réduire notre temps d’exécution.


Par ailleurs, nous nous sommes aperçus au cours du dernier jour du concours d’un retard vis-à-vis des autres concurrents au niveau des temps d’exécution. La principale lourdeur de notre programme venait de la décomposition du nombre calculé en tableau, et nous avions trouvé une solution afin de contourner cela, que nous ne fûmes pas capable de produire le dernier soir.


Cette solution était alors de stocker les différentes puissances de 10 sous forme de combinaison et ainsi réduire grandement le nombre de divisions à réaliser lors de la décomposition de notre nombre. Par cette amélioration nous espérerions une division de notre temps d'execution par 1,5 ou 2.



IV. Tester le programme


Pour tester ce programme, vous devez impérativement travailler dans un environnement linux. Ce pré requis n’est nullement dû au code source mais au makefile qui est écrit pour cet OS uniquement.


1. Télécharger les sources

2. Décompresser l’archive dans un dossier de travail

3. Se rendre dans le sous dossier scripts

4. Exécuter la commande make Production

5. Retourner à la racine du dossier

6. Se rendre dans le dossier build

7. Exécuter la commande ./Smallbrain Borne_Inférieure Borne_Supérieure


Vous pouvez également tester l’ensemble des tests unitaires écrits pour ce programme, en exécutant la commande make Tests. L’ensemble des tests générés se trouvant dans le dossier build.



Conclusion


Grâce à cette solution, nous avons terminé à la 5ème place de ce problème. Celui-ci représentait nos premiers pas du côté de la programmation parallèle et nous avons encore beaucoup à faire avant d’être au point sur les différentes optimisations mathématiques, algorithmiques et de programmation parallèle.


Par ailleurs, nous avons été très heureux de pouvoir participer et échanger avec les autres participants à travers le forum et espérons pouvoir renouveler l’expérience à travers d’autres concours organisés par Intel.

Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.