Soutenance mémoire
Les dépassements de capacité
Comme tous les formats de représentation finie de nombres, il est uniquement possible de coder des nombres entre une valeur minimale et maximale. Si un calcul doit produire une valeur supérieure à la valeur maximale représentable, alors le résultat sera la valeur spéciale ±∞. Il est donc impossible de calculer au-delà de la valeur maximale fixée par le format de représentation utilisé. Ce problème est le problème d’overflow. Il est à noter qu’une fois qu’un calcul à produit dans une de ses opérations la valeur spéciale ±∞ alors toutes les autres opérations utilisant cette valeur comme paramètre produiront la valeur ±∞ (ou NaN, par exemple dans le cas d’une multiplication par zéro). Inversement, il existe le problème d’underflow qui se présente lorsque l’on rencontre une valeur comprise entre zéro et la plus petite valeur représentable par le format de représentation utilisé. Dans ce cas, c’est le type d’arrondi choisi qui fixe le comportement à suivre. Un des risques posés par ce problème est la possibilité que la valeur soit arrondi à zéro, entraînant une annulation en cascade (à travers une suite de produits) ou au contraire produire la valeur spéciale ∞ dans le cadre d’une division.
Les phénomènes d’absorption et d’élimination catastrophique
L’absorption est due à l’arrondi du résultat d’une addition ayant pour opérandes deux nombres flottants très éloignés. Soit aˆ et bˆ deux nombres flottants tels que aˆ est bien supérieur à bˆ, une partie de bˆ sera perdue dans le résultat de l’addition. On parle d’absorption catastrophique quand tous les chiffres de bˆ sont perdus lors de l’addition. Dans ce cas, l’opération f l(aˆ + bˆ) sera égale à aˆ alors que bˆ aura été entièrement absorbé par aˆ. La figure 1.4(a) illustre ce phénomène. L’élimination survient lors de la soustraction de nombre très proches. À chaque opération il faut renormaliser le résultat en ajoutant des zéros à la mantisse car les chiffres de poids fort s’éliminent. Le résultat peut être très différent du résultat exact, et de plus représenter une valeur totalement erronée due aux imprécisions possibles des opérandes. On parle d’élimination catastrophique lorsqu’il ne reste que quelques chiffres significatifs dans le résultat. La figure 1.4(b) illustre ce phénomène. Combinées, ces erreurs peuvent par exemple, provoquer le résultat suivant : f l((aˆ+bˆ)− aˆ) = 0 au lieu du résultat exact bˆ.
Analyser la propagation des erreurs d’arrondi
L’analyse de la propagation des erreurs d’arrondi présentée ici, est une méthode qui cherche à mesurer l’écart entre le résultat calculé et la solution exacte. Cette méthode est appelée analyse directe ou encore analyse a priori. Nous présentons ici la Running Error Bound [Hig02], qui permet de calculer une borne d’erreur relative de façon dynamique au sein d’algorithmes numériques. Soit aˆ = a +α et bˆ = b +β où α et β sont les erreurs absolues entachant aˆ et bˆ. À partir du modèle standard (1.4) on dérive des bornes d’erreurs notées σ◦ pour chaque opération élémentaire ◦ ∈ {+,−,×,÷,p } décrit à la table 1.3. La borne d’erreur est calculée en même temps que l’évaluation des opérations l’algorithme. Les erreurs se propagent alors d’opération élémentaire en opération élémentaire jusqu’à fournir une borne pour le résultat du calcul. Remarquez que dans la table 1.3, chaque borne d’erreur est composée d’un terme d’erreur u| · | lié à l’opération arithmétique ◦, tandis que le reste de l’expression propage simplement les erreurs de l’entrée vers la sortie de l’opérateur. Cependant, l’utilisation du terme d’erreur u| · | présente les inconvénients suivants qui peuvent conduire à une surapproximation de la borne d’erreur : la borne est toujours calculée même si l’opération arithmétique ne provoque pas d’erreur, et peut de plus, être deux fois plus grande que l’erreur réelle. Il est possible de contourner ce problème en utilisant des méthodes plus précises pour évaluer l’erreur commise lors de l’opération arithmétique. Dans [ZL10], les auteurs utilisent, par exemple, les registres flottants 80 bits de la FPU (Floating-Point Unit) des processeurs modernes afin de calculer plus finement la borne. Néanmoins, l’analyse directe n’est pas la seule analyse disponible. J. WILKINSON a popularisé, dans les années 60, l’analyse indirecte aussi appelée analyse a posteriori [Wil63]. Enfin, pour une introduction générale à l’analyse numérique voir [Hil87].
Évaluer les performances d’un algorithme
Évaluer les performances d’un algorithme est une chose ardue. Au chapitre 2, nous avons utilisé deux méthodes différentes afin de caractériser les performances des algorithmes. En premier lieu, il est possible de compter le nombre d’instructions caractéristiques, c’est-à-dire, dans notre cas, le nombre d’instructions flottantes (flop) utilisées par l’algorithme. Il est aussi possible de caractériser les performances d’un algorithme en mesurant le temps nécessaire à la résolution de ses opérations. Comme le confirment les résultats des mesures du tableau 2.3, il existe des nuances importantes entre ces deux moyens de mesures. En effet, on constate que la mesure du nombre d’opérations flottantes indique un ratio de 1, 43 entre SUMDD et SUM2, c’est-à-dire, que selon ce critère, SUM2 est 1, 43 fois plus rapide que SUMDD. Cependant, les mesures de temps d’exécution exhibent que SUM2 est entre 3 et 4 fois meilleurs que SUMDD. Ces différences s’expliquent par des niveaux de parallélisme différents entre ces deux algorithmes. On constate même que la machine ne parvient pas à tirer entièrement partie du potentiel de parallélisation de SUM2. De plus, nous verrons à la section 3.3 que ces mesures ne sont pas reproductibles. Certains auteurs affirment même qu’une part de hasard accompagne ces mesures de performances [LPGP12]. Dans son article [Rum09] S. RUMP écrit : Measuring the computing time of summation algorithms in a high-level language on today’s architectures is more of a hazard than scientific research. dans son article intitulé : « Ultimately Fast Accurate Summation ». D. BAILEY écrit de plus un article sur les mesures de performances intitulé : « Twelve Ways to Fool the Masses When Giving Performance Results on Parallel Computers » [BLW11, chapitre 1]. Un moyen fiable d’évaluer les performances consiste à étudier le niveau de parallélisme d’instruction (ILP, voir définition 3.2.2) d’un algorithme sur une machine idéale (voir définition 3.2.1).
|
Table des matières
I État de l’art
1 Arithmétique flottante IEEE 754 et précision numérique
1.1 Introduction
1.2 Représentation des nombres
1.2.1 Les formats
1.3 Comportements de l’arithmétique flottante
1.3.1 Les modes d’arrondi
1.3.2 Les sources d’erreurs
1.4 Analyse d’erreur de la précision numérique
1.4.1 Notions utilisées
1.4.2 Les fonctions ulp et ufp
1.4.3 Analyser la propagation des erreurs d’arrondi
1.5 Conclusion
2 Transformations sans erreur, compensation et expansion
2.1 Introduction
2.2 Les transformations sans erreur
2.2.1 L’addition
2.2.2 La multiplication
2.2.3 La division et la racine carrée
2.2.4 Utilisation
2.3 Les compensations
2.4 Les expansions
2.4.1 Le double-double
2.5 Compensation versus double-double
2.5.1 Comparaison entre SUM2 et SUMDD
3 Manipulation de programmes et mesure des performances
3.1 Introduction à la transformation de code
3.1.1 Compilation
3.1.2 Synthèse de code
3.2 Évaluer les performances d’un algorithme
3.3 La non reproductibilité des mesures
3.4 Une application de mesure des performances : PAPI
3.5 Vers des mesures reproductibles : PERPI
3.6 Conclusion
II Vers des compromis performance – précision
4 Cas de la somme : Étude des relations entre performance et précision
4.1 Introduction
4.2 Présentation de l’approche
4.2.1 Une combinatoire importante
4.2.2 Des données représentatives
4.3 Résultats expérimentaux
4.3.1 Approche générale
4.3.2 Étude étendue
4.4 Incidence des compromis en pratique
5 Amélioration automatique de la précision
5.1 Introduction
5.1.1 Notations
5.2 Automatisation de la compensation
5.2.1 Le principe de l’automatisation
5.2.2 Compensation automatique de la somme et du produit
5.2.3 Compensation automatique de la division et de la racine carrée
5.2.4 Utilisation
5.3 Résultats expérimentaux
5.3.1 La somme
5.3.2 L’évaluation polynomiale
5.3.3 Synthèse des résultats
5.4 Conclusion
6 Stratégies d’optimisation multi–critères
6.1 Introduction
6.2 Modèle de représentation de programme
6.3 Compensation automatique
6.3.1 Propagation des erreurs
6.4 Transformation de boucle
6.4.1 Par répartition simple
6.4.2 Par répartition intermittente
6.5 Sélection par précision
6.6 Résultats expérimentaux
6.6.1 Exemples de programmes C transformés automatiquement
6.6.2 Résultats expérimentaux entre performances et précision
6.7 Conclusion
7 Synthèse de code : recherche d’un compromis temps–précision
7.1 Introduction
7.2 Synthèse de code
7.2.1 Spécifications ou attentes d’un utilisateur
7.2.2 Espace de recherche
7.2.3 Technique de recherche
7.3 Outils de transformation et de synthèse
7.3.1 CoHD : transformation de code source à source
7.3.2 SyHD : synthèse de code
7.4 Conclusion
8 Résultats expérimentaux
8.1 Introduction
8.1.1 Définitions et rappels des notations
8.2 Synthèse de code avec compromis
8.2.1 Cas de la somme
8.2.2 Évaluations polynomiales
8.2.3 Récapitulatif des résultats et conclusion
8.3 Résolution de systèmes linéaires et raffinement itératif
8.3.1 Résolution de systèmes linéaires
8.4 Conclusion
Conclusion et perspectives
III Annexes
A Environnements et ressources de travail
B Détails des mesures de performances relatives au chapitre 3
C Codes sources et mesures relatifs au chapitre 5
D Mesures complémentaires relatives au chapitre 8
Liste des figures
Liste des tableaux
Liste des algorithmes
Liste des codes
Bibliographie
Télécharger le rapport complet
