Arithmétique des ordinateurs (Présentation vulgarisée)

Reproductibilité numérique pour les systèmes

massivement parallèles

Chemseddine CHOHRAPhilippe LANGLOIS, David PARELLO

Université de Perpignan Via Domitia (UPVD)

16 Mai 2014

Chemseddine CHOHRAPhilippe LANGLOIS, David PARELLO (Université de Perpignan Via Domitia (UPVD))Reproductibilité numérique pour les systèmes massivement parallèles16 Mai 2014 1 / 25

Sommaire

1 Introduction

2 Les nombres sur machine

3 Problématique

4 Solution possible

5 Conclusion


Introduction

Sommaire

1 Introduction


3 Problématique

4 Solution possible

5 Conclusion


Introduction

Introduction

Qu'est-ce qu'un calcul mathématique ??

Une ou plusieurs opérations appliquées sur des grandeurs (+, -, *, /).

Comment faire des calculs ?


Introduction

Introduction





Introduction

Introduction





Introduction

Introduction


Introduction

Introduction


Introduction

Introduction


Introduction

Introduction


Introduction

Introduction

Les supercalculateurs sont capables de faire plus d'un million demilliards d'opérations par seconde.

Si un humain fais 1 opération par seconde ça va prendre 31 milliond'années.

Si toute l'humanité fait des calculs ça prends 40 heurs.

Mais est ce que ces calculs sont précis ??


Introduction

Introduction






Introduction

Introduction






Introduction

Introduction






Introduction

Introduction






Les nombres sur machine

Sommaire

1 Introduction


3 Problématique

4 Solution possible

5 Conclusion



Les nombres sur machineLes nombres réels

L'ensemble des nombres réels est un ensemble in�ni.

Les éléments ne sont pas écartés (ensemble continu).

Tout intervalle contient in�niment des éléments.

Il faut utiliser une approximation.
























Les nombres sur machineLes nombres �ottants

L'approximation la plus utilisée est les nombres �ottants.

L'équivalent informatique de la notation scienti�que (± M * 10e).

M est un nombre décimal dans l'intervalle [1, 10[.1 123456789 = 1.23456789 * 108.

2 123.456789 = 1.23456789 * 106.

3 0.0123456789 = 1.23456789 * 10−2.

Sur ordinateur on utilise la base 2 au lieu de la base 10 (± M * 2e).(1.23456789)10 = (1.011111111110011110000001)2;







2 123.456789 = 1.23456789 * 106.

3 0.0123456789 = 1.23456789 * 10−2.








2 123.456789 = 1.23456789 * 106.

3 0.0123456789 = 1.23456789 * 10−2.








2 123.456789 = 1.23456789 * 106.

3 0.0123456789 = 1.23456789 * 10−2.

Sur ordinateur on utilise la base 2 au lieu de la base 10 (± M * 2e).

(1.23456789)10 = (1.011111111110011110000001)2;







2 123.456789 = 1.23456789 * 106.

3 0.0123456789 = 1.23456789 * 10−2.



Problématique

Sommaire

1 Introduction


3 ProblématiquePrécision �nieArrondi et erreur d'arrondiNon associativité de l'additionNon-reproductibilité

4 Solution possible

5 Conclusion


Problématique Précision �nie

ProblématiquePrécision �nie

On ne peut pas présenter "exactement" les nombres non décimaux (π,√2, 1 / 3).

La mantisse contient seulement 7 chi�re signi�catifs en décimal (16pour des types étendus).

On ne peut pas présenter "exactement" les nombres décimaux quidemandent plus de chi�res.
















Avec 3 chi�res signi�catifs : 1.23456789 −→ 1.23.








Problématique Arrondi et erreur d'arrondi

ProblématiqueArrondi et erreur d'arrondi

Comment faire une addition ??

Exemple (4 chi�res signi�catifs).




Comment faire une addition ??

Exemple (4 chi�res signi�catifs).




















Problématique Non associativité de l'addition

ProblématiqueNon associativité de l'addition

A cause des erreurs d'arrondi, l'addition n'est plus associative.

A + (B + C) 6= (A + B) + C.

Exemple.





A + (B + C) 6= (A + B) + C.

Exemple.





A + (B + C) 6= (A + B) + C.

Exemple.























Problématique Non-reproductibilité

ProblématiqueNon-reproductibilité

Dans une architecture parallèle l'ordre des opérations n'est pastoujours le même.





















On pourrait obtenir des résultats di�érents pour plusieurs executionsde même programme.


Solution possible

Sommaire

1 Introduction


3 Problématique

4 Solution possibleRecupérer l'erreurSommes compensées

5 Conclusion


Solution possible

Solution possible

Une solution possible est de calculer la somme exacte qui est toujoursreproductible.

Mais comment ??


Solution possible

Solution possible

Une solution possible est de calculer la somme exacte qui est toujoursreproductible.

Mais comment ??


Solution possible Recupérer l'erreur

Solution possibleRecupérer l'erreur

Au lieu de calculer la somme nous calculons la somme et l'erreur.












Au lieu de calculer la somme nous calculons la somme et l'erreur.Mais ça coute 6 opérations de base.


Solution possible Sommes compensées

Solution possibleSommes compensées

























Coûte très cher en nombre d'opérations (6n fois plus cher pour nitérations).

Il y a de meilleurs algorithmes récents (certains assurent la sommationexacte et d'autres assurent seulement la reproductibilité).




Coûte très cher en nombre d'opérations (6n fois plus cher pour nitérations).

Il y a de meilleurs algorithmes récents (certains assurent la sommationexacte et d'autres assurent seulement la reproductibilité).


Conclusion

Sommaire

1 Introduction


3 Problématique

4 Solution possible

5 Conclusion


Conclusion

Conclusion

Le calcul fait par l'ordinateur n'est pas précis.

Calculer des sommes précises coûtent plus cher.

En exploitant le parallélisme sur les nouvelles architectures, est-ce quece coût est acceptable ??


Conclusion

Conclusion





Conclusion

Conclusion





Conclusion

Merci pour votre attention


Software

Arithmétique des ordinateurs (Présentation vulgarisée)