Acceler8 : Recherche de nombres premiers particuliers (Une solution au second problème)

Cet article vous présente la solution que Maxime Riviere et moi (Fabien Arcellier) avons mis en œuvre pour résoudre le second problème du concours acceler8.

Vous trouverez au bas de la page un fichier Zip contenant le code source de notre participation.

Objectifs du second problème:



Il consistait à développer une application en mode console capable de trouver 2 groupes formés de plusieurs nombres premiers consécutifs dont la multiplication des éléments du premier ensemble était égal à l'addition des éléments ensemble de l'autre à plus ou moins un delta près.

L'utilisateur configure 4 paramètres avant l'exécution:

  • la borne inférieure de l'espace de recherche des groupes de nombres premiers destinés à être multipliés entre eux,
  • la borne supérieure,
  • le nombre de nombres premiers consécutifs dans un groupe,
  • le delta accepté.
Par exemple, il écrit la commande suivante :
./cprime 1 10000 3 1

On recherche tous les groupes formés de 3 nombres premiers consécutifs dont le plus petit terme est supérieur ou égal à 1 et le plus grand terme impliqué dans une multiplication est inférieur ou égale à 10000. L'écart acceptable entre les 2 groupes est de 1 maximum.

Une des solutions que le programme doit trouver est la suivante (parmi 42) :

  • 9433 * 9437 * 9439 = 840252427019
  • 280084142333 + 280084142339 + 280084142347 = 840252427019
Notre programme doit répondre à 2 exigences :

  • Trouver toutes les solutions possibles en un minimum de temps,
  • Profiter au maximum des machines composées de plusieurs processeurs (La MTL mis à disposition par Intel en contient 32).

Résoudre le problème :



Notre première approche consistait à calculer, dans un premier temps, l'ensemble des groupes de nombres premiers consécutifs impliqués dans la multiplication et ensuite à construire un nouvel ensemble contenant l'ensemble des groupes de nombres premiers consécutifs dont l'addition était comprise entre la valeur minimum moins le delta et la valeur maximum moins le delta trouvé lors de la multiplication des termes du plus petit et du plus grand des groupes de multiplication.

Toutefois, le processus pour vérifier la primalité d'un nombre est couteux. Cette approche nécessiter de vérifier beaucoup de groupes inutiles. En l'utilisant, nous parcourions l'ensemble des groupes sans tenir compte de contraintes qui permettraient d'éliminer certaines possibilités.
Nous avons abandonné cette approche et cherché un algorithme permettant de réduire l'espace à parcourir.

Pour cela, nous avons décidé de partir des informations que nous possédions à l'issue de la première étape, c'est à dire après le calcul des multiplications.

Les contraintes que nous avons trouvées pour qu'un groupe soit solution sont :

  • La valeur de l'addition des termes d'un groupe doit être égale à la valeur de la multiplication des termes de ce groupe plus ou moins un delta,
  • Les groupes sont toujours composés du même nombre de termes,
  • L'ensemble des groupes est muni d'une relation d'ordre. Si les k termes qui composent un groupe sont ordonnés de façon croissante, alors un groupe dont le 1er terme est inférieur au 1er terme d'un autre groupe est inférieur à celui-ci.
  • Si la valeur d'addition des termes d'un groupe est inférieure à la valeur de la multiplication des termes d'un groupe donné plus ou moins un delta, alors tous les groupes inférieurs ne peuvent pas être solution en regard de celui ci,
  • Inversement si la valeur d'addition des termes d'un groupe est supérieure à la valeur de la multiplication des termes d'un groupe donné plus ou moins un delta, alors tous les groupes supérieurs ne peuvent pas être solution en regard de celui ci
Ces contraintes données, nous étions en mesure de borner l'ensemble des solutions possibles pour une valeur de multiplication donnée.

Ce concept est essentiel pour comprendre une des simplifications majeures. Nous pouvons borner une valeur de multiplication , seulement, nous pouvons travailler soit sur l'ensemble des groupes des groupes se trouvant à l'extérieur de l'espace borné, soit à l'intérieur. Le plus efficace, c'est de travailler dans l'ensemble borné, donc nous devions trouver un moyen permettant de trouver à partir de la valeur de multiplication les termes susceptibles de former un groupe appartenant à l'espace solution.

L'addition de i nombres ordonnés distincts donnant une valeur respecte la règle suivante:



alors :



A partir de là, nous divisons la valeur de la multiplication par le nombre de nombre premier dans un groupe. Nous savons que les groupes solutions auront au moins l'un de leur terme supérieur et inférieur à cette valeur.


Vérifier la primalité d'un nombre



De ce coté là, aucune révolution. Nous avons utilisé l'approche naïve qui consiste à diviser un nombre k par l'ensemble des nombres entre 2 et la racine carrée de k. Pour réduire les calculs à effectuer, nous ne testions que les nombres impairs à l'exception de 2 (couramment appellé Algorithme d'Euclide).

Nous avions au départ couplé cette approche avec le test de composabilité de Rabin Miller permettant d'écarter les nombres composés (non premier) plus tôt. Ce type de test est utilisé pour déterminer la primalité d'un nombre mais l'on parle ici d'un test probabiliste dont l'usage dans ce problème était prohibé. C'est pourquoi nous devions toujours le compléter par l'approche naïve.

Lors de la validation finale, nous nous sommes rendu compte que cette approche n'offrait de bénéfices que pour les grands nombres hors des bornes calculables par notre programme. (Au delà de 2^64 bits) (Voir graphique ci dessous).

Effet du couple Euclide - Rabin-Miller pour la recherche de nombre premier



Les valeurs en abscisse correspondent à la valeur maximum d'un terme dans un ensemble de type multiplication.


Paralléliser notre programme



Notre algorithme se décompose en 3 phases. Nous nous sommes rendus compte que la 3 ème phase occupait plus de 90% des ressources de calculs. Pour paralléliser notre programme, nous avons décidé de nous focaliser sur cette partie.



Lors du premier problème, nous nous sommes rendu compte que les approches qui utilisent le découpage d'arbre binaire étaient parmi les plus faciles à contrôler et à mettre en oeuvre dans un contexte parallèle. Nous avons donc utilisé un algorithme de type Divide & Conquer.

A chaque étage de l'arbre, nous venions ouvrir un Thread sur la branche de droite. Nous laissons le thread courant continuer sur celle de gauche. A l'étage 2, nous avons 2 threads. Au 3, 8 Threads. Au 4, 16 threads ...Dans le cadre de la MTL, au delà de l'étage 7, nous n'ouvrions plus de nouveaux threads (Nous avions 64 threads ouverts).

Nous avons utilisé OpenMP 3.0 pour l'implémentation. Nous avons utilisé la fonctionnalité Task qui semblait être l'une des plus adapté au découpage de Thread lors du parcours récursif d'un arbre en nous basant sur l'article "Using the Tasking feature" écrit par Richard Friedman.

Pour que cette approche soit efficace, il était important que chaque sous région de l'arbre représente la même charge de travail.




Pour cela, nous avons affecté à chaque Noeud un poids correspondant à la charge de travail qu'il représentait en nous basant sur le théorème des nombres premiers. Le programme équilibre l'arbre lors de l'étape 2 à l'aide de cet attribut en effectuant une insertion à la bonne place.



Tester le programme



Pour tester le programme, vous devez travailler sous Linux. Cette limite ne vient pas du code mais du makefile qui est écrit pour cet OS.

  1. Téléchargez les sources
  2. Décompresser l'archive dans un dossier de travail.
  3. Allez dans le sous dossier scripts
  4. Tapez make Production TARGET=STATION COMPILATEUR=GCC
  5. Retourner dans le dossier racine
  6. Allez dans le sous dossier build
  7. tapez la commande ./cprime 1 100 2 1
Vous pouvez également préparer le programme pour la MTL. Pour cela, vous devrez remplacer la commande de l'étape 4 par la commande suivante :

make Production TARGET=MTL COMPILATEUR=GCC

Nous avons contrôlé le code produit à l'aide de tests automatiques. Il y'en a plus d'une centaine. Si vous souhaitez compiler pour le test, vous devrez remplacer la commande de l'étape 4 par la commande suivante.

make Tests TARGET=STATION COMPILATEUR=GCC

Dans le dossier build, tapez la commande ./tests.sh

Pour conclure



Grâce à cette solution, nous avons terminé 3ème. Elle répond aux objectifs du problème mais n'est pas optimale. Nous avons encore beaucoup à apprendre autant vis à vis du domaine mathématique que du parallélisme.
L'usage de la librairie Intel Threading Building Block à la place d'OpenMP aurait probablement permis d'obtenir de meilleurs performances vu le découpage que nous avons effectué.

Ce concours fut une expérience unique. A cette occasion, nous avons découvert l'univers de la programmation "parallèle" et enrichit nos connaissances. Tout au long de cette aventure, nous avons apprécié l'esprit de collaboration positive et de compétition saine entre les participants, ainsi que les efforts fournis par les organisateurs pour que ce soit une réussite.

Nous avons éprouvé un grand plaisir à participer et espérons qu'une nouvelle édition avec un défi renouvelé, peut être sur une autre thématique, sera organisée.
Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.
Étiquettes: