Calculs concrets de logarithme discret

Calculs concrets de logarithme discret

Calcul concret

 Cet effort est motivé par l’objectif de mener des calculs de logarithme discret rapides dans des groupes de plus en plus grands. Ceci nous a amené à réaliser deux implémentations de l’algorithme de Wiedemann par blocs : — une implémentation adaptée à un cluster de GPU NVIDIA ; — une implémentation adaptée à un cluster de CPU multi-cœurs. Les codes des deux implémentations permettent de calculer les étapes de Produits scalaires et Évaluation de l’algorithme de Wiedemann par blocs et s’appuient sur le logiciel CADO-NFS pour calculer l’étape Générateur linéaire.

 Implémentation GPU 

L’implémentation GPU est actuellement sous la forme d’un package publié à l’adresse http: //www.loria.fr/~hjeljeli/. Le code a été optimisé pour les GPU NVIDIA de compute capability 3.0 et a été développé en utilisant principalement les langages CUDA et PTX. Les routines de l’algèbre linéaire et les fonctions de traitement de la matrice et des vecteurs sont écrites en CUDA. Les briques d’arithmétique RNS sont écrites en assembleur PTX. Pour les communications multi-GPU, nous avons combiné les directives CUDA et les directives Cuda-aware MPI. 

Implémentation CPU 

L’implémentation CPU est aussi sous la forme d’un package téléchargeable depuis la même adresse. La partie du code correspondant à l’arithmétique RNS est en cours d’intégration dans la bibliothèque MPFQ [MPFQ] qui permet de générer du code en langage C adapté à un corps fini (travail d’intégration réalisé avec Vialla et Sanselme). Le code a été développé en utilisant le langage C et les directives MPI. L’implémentation fournit trois version possibles d’arithmétique : — une version basée sur l’arithmétique multi-précision qui utilise la couche mpn de GMP ; — une version qui implémente l’arithmétique RNS à travers les intrinsics SSE2 et qui nécessite un CPU qui supporte au moins le jeu d’instructions SSE4.2 ; — une version qui implémente l’arithmétique RNS à travers les intrinsics AVX2 et qui nécessite une CPU qui supporte au moins le jeu d’instructions AVX2.

Organisation du calcul d’algèbre linéaire 

Un calcul de Wiedemann ou de Wiedemann par blocs est organisé en 3 étapes (voir les sous-sections 3.5.2 et 3.5.3 pour Wiedemann et Wiedemann par blocs respectivement). La première étape, Produits scalaires, consiste à calculer la séquence de Krylov ou une sousséquence de Krylov s’il s’agit de la variante par blocs et que nous avons distribué le calcul sur autant de nœuds qu’il y a de séquences. Une itération typique d’un calcul de Wiedemann ou de Wiedemann par blocs, que nous indexons par j, correspond aux opérations suivantes : — v ← Av (SpMV) ; — aj ← txv (produit scalaire).La deuxième étape, Générateur linéaire, calcule le générateur linéaire de la séquence de sortie de l’étape Produits scalaires. La sortie de cette étape est le générateur F. La troisième étape, Évaluation, calcule l’évaluation du polynôme F en la matrice A, multipliée par un vecteur z. Nous utilisons un schéma de type Hörner, de sorte à ce qu’on effectue exactement deg F produits. Notons Fˆ le polynôme réciproque de F. Si nous initialisons le vecteur w avec le vecteur nul, une itération d’indice j est alors effectuée comme suit : — w ← Aw + ˆfjz. 

Gestion des erreurs et des pannes 

Les calculs que nous allons exécuter vont prendre des temps relativement longs, qui peuvent aller de quelques heures à quelques mois. Il est possible d’avoir des interruptions accidentelles du calcul. C’est pourquoi nous mettons en place des sauvegardes périodiques des résultats intermédiaires sur un support de mémoire de masse. Ces sauvegardes permettent de reprendre le calcul. La périodicité de ces sauvegardes dépend de la durée du calcul. Par exemple, pour un calcul qui dure quelques heures, nous faisons des sauvegardes toutes les 120 minutes. Pour un calcul qui dure des jours, on peut envisager des sauvegardes quotidiennes. Nous avons aussi observé des erreurs de calcul qui peuvent survenir avec un certain type d’architectures sur lesquelles nous effectuons les calculs, typiquement avec les cartes graphiques destinées pour les jeux vidéo. Ce qui nous a amené à mettre en place des vérifications périodiques pour pouvoir détecter et corriger une erreur survenue. Le calcul de chacune des étapes Produits scalaires et Évaluation est alors divisé en tranches, une vérification de la cohérence du calcul est effectuée après chaque tranche. Pour cela, nous avons besoin de stocker les données de la tranche précédente ; ainsi, si le calcul s’avère erroné, il suffit de reprendre le calcul à partir de la tranche précédente qui a été vérifiée avec succès. Une tranche du calcul est composé d’un certain nombre d’itérations, par exemple toutes les 1000 ou 10000 itérations. Nous notons k le nombre d’itérations qui composent une tranche et nous allons expliqué le procédé de la vérification pour chaque étape. Pendant l’étape Produits scalaires, nous vérifions la cohérence des vecteurs Aiy calculés. Supposons que nous sommes sûrs du résultat de Aiy, pour un i donné. Après k itérations, nous voudrions vérifier que le vecteur Ai+ky est correct. Admettons que nous avons deux vecteurs pré-calculés c0 et ck, tel que ck = (tA) k c0. Pour vérifier que Ai+ky est correct, il suffit de vérifier l’égalité t ckAiy = t c0Ai+ky. Ce test assure avec une bonne probabilité que le calcul de Ai+ky a réussi. Ce test ne nécessite que le pré-calcul des vecteurs c0 et ck et deux produits scalaires pour chaque vérification. Ainsi, il n’alourdit pas le calcul de l’étape. Pour l’étape Évaluation, la vérification des résultats intermédiaires s’effectue avec un schéma similaire à celui de l’étape Produits scalaires. Pour cela, nous choisissons un nombre positif petit δ (typiquement < 10). Nous avons aussi besoin que z s’écrive comme une certaine puissance de la matrice A multipliée par y. Par souci de simplicité, prenons z égal à y.