i et mon doctorat. L'élève a rencontré un problème dans un contexte d'analyse des données de physique que je pourrais utiliser quelques informations sur. Nous avons du code qui analyse les données de l'une des expériences de la LHC qui fournissent des résultats irréproductibles. En particulier, les résultats des calculs obtenus à partir du même binaire de la même binaire exécuté sur la même machine peuvent différer entre des exécutions successives. Nous sommes conscients des nombreuses sources d'irréproductibilité différentes, mais excluons les suspects habituels.
Nous avons suivi le problème jusqu'à l'irréproductibilité des opérations de comparaison de points flottants (double précision) lors de la comparaison de deux chiffres qui ont une valeur nominale de la même valeur. Cela peut arriver occasionnellement à la suite d'étapes préalables dans l'analyse. Un exemple Nous venons de trouver un exemple qui teste si un nombre est inférieur à 0,3 (note que nous ne testons jamais d'égalité entre les valeurs flottantes). Il s'avère que, en raison de la géométrie du détecteur, il était possible que le calcul produise occasionnellement un résultat qui serait exactement 0,3 (ou sa représentation de double précision la plus proche).
Nous sommes bien conscients des pièges en comparant les numéros de points flottants et le potentiel d'excès de précision dans la FPU pour affecter les résultats de la comparaison. La question que je voudrais avoir répondu est "Pourquoi les résultats sont-ils irréproductibles?" Est-ce parce que la charge du registre FPU ou d'autres instructions FPU ne nettoie pas les bits d'excédent et donc des bits «restes» des calculs précédents affectent les résultats? (Cela semble improbable) J'ai vu une suggestion sur un autre forum que le contexte des commutateurs entre processus ou threads pourrait également induire une modification des résultats de comparaison de points flottants en raison du contenu de la FPU étant stockée sur la pile et, donc, étant tronquée. Tous les commentaires sur ces = ou d'autres explications possibles seraient appréciés.
7 Réponses :
Quelle plate-forme?
La plupart des FPU peuvent stocker la plus grande précision que la double représentation de l'IEEE - pour éviter toute erreur d'arrondissement des résultats intermédiaires. Il y a souvent un commutateur de compilateur à la vitesse / précision commerciale - voir http : //msdn.microsoft.com/en-us/library/e7s85FFB (vs.80) .aspx
Et comment cela produirait-il des résultats non déterministes?
Commutateurs de contexte comme décrit par Jerry
À une conjecture, ce qui se passe est que vos calculs soient normalement effectués à quelques morceaux de précision supplémentaires à l'intérieur du FPU, et seulement arrondi à des points spécifiques (par exemple, lorsque vous attribuez un résultat à une valeur).
Lorsqu'il y a un changement de contexte, l'état de la FPU doit être sauvé et restauré - et il y a au moins une chance assez équitable que ces bits supplémentaires soient pas étant sauvés et restaurés dans le changement de contexte. Quand cela se produit, cela ne causerait probablement pas de changement majeur, mais si (par exemple), vous soustrayez ultérieurement un montant fixe de chacun de chacun et de multiplier ce qui reste, la différence serait également multipliée.
Pour être clair: je doute que les bits "restants" serait le coupable. Au contraire, ce serait une perte de bits supplémentaires causant des arrondies à des points légèrement différents dans le calcul.
Je parierais que le système d'exploitation utilise les instructions FSAVE / FRSTOR, qui décharge et restaure réellement tous les bits des états X87. Cela inclut les 80 bits des registres internes. En supposant un X86 avec un système d'exploitation 32 bits, lequel Brian a oublié de nous dire s'il utilise. :-)
@Bo Persson: Les registres PF ont 80 visible bits, mais la plupart ont au moins un ou deux "bits de garde" également, pour donner un LSB correctement arrondi dans les années 80 visibles.
Toutes ces conversions et ces états sauvegardent / restauration sont déterministes. L'état FP sauvegardé est une copie parfaite.
Le FPU interne de la CPU peut stocker des points flottants à une plus grande précision que le double ou le flotteur. Ces valeurs doivent être converties chaque fois que les valeurs du registre doivent être stockées ailleurs, y compris lorsque la mémoire est échangée dans le cache (ceci que je connais pour un fait) et un commutateur de contexte ou une interruption de système d'exploitation sur ce noyau sonne comme une autre source facile. . Bien entendu, le calendrier des interruptions de système d'exploitation ou des commutateurs de contexte ou l'échange de mémoire non chaude est totalement imprévisible et incontrôlable par l'application.
Bien sûr, cela dépend de la plate-forme, mais votre description vous semble telle que vous exécutez sur un bureau moderne ou un serveur (SO x86).
Nice essayer, mais toutes ces conversions sont déterministes . L'état FP est enregistré via des instructions dédiées et ce mécanisme de sauvegarde / restauration ne perd pas d'informations.
@zvrba: déterministe ne signifie pas sans perte. Une instruction déterministe ne se comporte pas de manière déterministe si elle est appelée non déterministe.
Hein? Toutes les instructions FP produisent exactement la même (même des bittes!) Résultats étant donné les mêmes intrants, peu importe dans quelles circonstances ils sont appelés. (Avec l'exception possible de l'un des arguments étant infini de Nan.)
J'ai fait ceci:
;;; for( i=0; i<sizeof(x)/sizeof(x[0]); i++ ) if( x[i]!=a ) {
xor ebx, ebx ;25.10
; LOE ebx f1
.B1.9: ; Preds .B1.19 .B1.8
mov esi, ebx ;25.47
shl esi, 4 ;25.47
fld TBYTE PTR [?x@@3PA_TA+esi] ;25.51
fucomp ;25.57
fnstsw ax ;25.57
sahf ;25.57
jp .B1.10 ; Prob 0% ;25.57
je .B1.19 ; Prob 79% ;25.57
[...]
.B1.19: ; Preds .B1.18 .B1.9
inc ebx ;25.41
cmp ebx, 1048576 ;25.17
jb .B1.9 ; Prob 82% ;25.17
est le programme multi-threadé?
Si oui, je soupçonnerais une condition de course.
Sinon, l'exécution du programme est déterministe. Le comportement indéfini, c'est-à-dire une réagissariat la plus probable pour obtenir des résultats différents étant donné que les mêmes entrées sont les mêmes intrants, c'est-à-dire un bogue dans votre programme. En lisant une variable non initialisée, un pointeur piquant, écrasant les bits les plus bas de certains numéros de PF sur la pile, etc. Les possibilités sont infinies. Si vous exécutez cela sur Linux, essayez de l'exécuter sous Valgrind et voyez s'il découvre des bugs.
BTW, comment avez-vous affaibli le problème à la comparaison FP?
(coup long: défaut du matériel? E.g., l'échec de la puce RAM pourrait entraîner une lecture différente des données à différentes occasions. cependant, cela plantait probablement le système d'exploitation plutôt rapidement.)
Toute autre explication est invraisemblable - les bugs dans le système d'exploitation ou le HW n'auraient pas disparu non découvert pendant longtemps.
Le programme n'est pas multi-threadé s'il est en cours d'exécution dans un contexte multi-processus. Et il a été traversé par la valgronnée (y compris Memcheck) sans problèmes. Dans la frustration de ne pas identifier la source de l'irréproductibilité, nous avons eu recours au débogage de la basse technologie - Dumping de la valeur étant comparée à une analyse "CUT" (0.3) à COUT. Deux exécutions distinctes imprimées à la fois de 0,3 à 15 chiffres de chiffres significatifs (... << STD :: SETW (15) << DR) Encore la ligne ultérieure qui effectue la comparaison de DR à 0.3 produit un résultat différent.
Pourquoi ne connectez-vous pas les décharges hexagonales de valeurs variables? LOG2 (10 ^ 15) est ~ 49.82, et il y a plus de bits de mantisse en double double.
Ok, bien que Valgrind ne détecte pas toujours toutes les problèmes. Je vous suggère de remplir votre débogage sur le niveau de code de la machine. Définissez un point d'arrêt sur la déclaration d'impression, exécutez l'instruction par instruction et inspectez l'état de tous les registres après chaque instruction. Assurez-vous également de regarder des registres XMM. Pouvez-vous coller le code en question ici (ce qui est autour de la déclaration d'impression et la comparaison elle-même)?
Je suis d'accord avec cette analyse. Je doute sincèrement que le changement de contexte change, sauf si je ne suis pas avéré bien sûr. Je ne crois pas que les états de registre sont poussés de manière incorrecte à la pile.
En 2016, si cela reste un problème, vous pouvez recompiler avec -fsanitize = non défini à la place. Cela devrait attraper plus d'erreurs arithmétiques que je pense.
Il pourrait également s'agir d'une partie du code ou d'une bibliothèque tiers qu'elle charge / liens avec étant mal élevé et laissant le mode d'arrondi à point flottant (ou une autre configuration de point flottant d'exécution) dans l'état non par défaut. Bien sûr, cette bibliothèque devra également faire quelque chose de non-déterministe (par exemple, des nombres aléatoires, des E / S ou une filetage), mais cela est possible.
Je vais simplement fusionner certains des commentaires de David Rodriguez et Bo Persson et faites une supposition sauvage.
pourrait-il être la commutation de tâche lors de l'utilisation des instructions SSE3? Basé sur cette Article Intel sur l'utilisation des instructions SSE3 Les commandes pour préserver l'état du registre FSAVE et FRESTOR ont été remplacées par FXSAVE et FXRESTOR, qui doivent gérer la pleine longueur de l'accumulateur.
sur une machine x64, je suppose que l'instruction "incorrecte" pourrait être contenue dans une bibliothèque compilée externe.
Ces instructions ne sont généralement pas utilisées par un programme de mode utilisateur et si le noyau Linux avait un tel bogue (c'est-à-dire à l'aide d'instructions erronées pour enregistrer / restaurer l'état FP), il aurait été trouvé il y a longtemps.
Oui, je crois que tu as raison. De l'autre côté, une bonne commutation de tâches ne doit pas laisser derrière les bits dans les registres, et une telle possibilité a été discutée dans les commentaires à la question. Je laisserai la réponse ici, comme référence pour une demande possible du côté de l'assemblage du problème.
Personne ici n'a encore prouvé que la commutation des tâches quitte des bits dans les registres. Les instructions matérielles destinées à la commutation d'état FP ne laissent certainement pas de déchets autour.
Vous avez certainement frappé bug de GCC n ° 323 , qui, Les autres points étant dus à la précision excédentaire du FPU.
Solutions:
Ne stockez pas de variables à virgule flottante dans des registres et inhiber d'autres options pouvant changer si une valeur de point flottante est extraite d'un registre ou d'une mémoire.
Cette option empêche l'excès de précision indésirable sur des machines telles que les 68000 où les registres flottants (du 68881) gardent plus de précision qu'un double est censé avoir. De même pour l'architecture X86. Pour la plupart des programmes, la précision excédentaire ne fonctionne que bien, mais quelques programmes reposent sur la définition précise du point flottant IEEE. Utilisez -ffloat-Store pour ces programmes, après les modifier pour stocker tous les calculs intermédiaires pertinents en variables.
Ce bogue seul n'expliquerait pas le non-déterminisme à travers différentes pistes du même binaire, sur la même machine, avec les mêmes intrants.
Pourriez-vous s'il vous plaît ajouter une référence à la suggestion sur les commutateurs contextuels? Bien que je puisse imaginer un processeur en mouvement des données d'accumulateur et jeter des bits, ce mécanisme ne me semble pas une bonne explication, et certains plus de détails pourraient être intéressants.
Peut-être utiliser différents drapeaux d'optimisation du compilateur pourraient résoudre ce problème.
@ Coffee sur Mars: Cela allait être ma suggestion, alors je pense que je peux expliquer :) La question est que le FPU peut utiliser un plus grand nombre de bits dans ses registres, dans certains processeurs récents jusqu'à 80 bits pour les doubles. . Maintenant, dans un environnement fileté unique, le FPU sera en mesure d'effectuer toutes les opérations avec cette précision et vous obtiendrez un résultat. Si vous ajoutez d'autres threads / processus au mélange, lorsque le système d'exploitation effectue le commutateur de contexte, il doit stocker la valeur du registre 80bit dans un double doublé de 64 bits, perdant une précision.
Être pas une réponse, mais une "supposition". Il serait plus sage du logiciel de travail s'il faisait la comparaison dans la forme entière du flotteur, comme, transformant le flotteur en la forme de signe-expoent-mantissa d'une longueur non signée. Cela implique également de stocker les valeurs de l'expérience sous cette forme, de sorte que vous n'avez pas de problèmes lorsque les chiffres sont trop proches les uns des autres.
Pour tester votre théorie des "bits excédentaires", je pourrais suggérer de déclarer et de définir une nouvelle variable avant la comparaison. Cela dégradera les performances et peut ne pas être une "solution" par aucun moyen mais ce serait un moyen intéressant de rejeter votre hypothèse.
De plus, votre programme est-il multiplié ou distribué? Les seuls cas où j'ai rencontré de telles divergences était avec des conditions de race (subtiles). Aussi MPI pourrait également être un coupable possible si vous l'utilisez.
@Matthew PK, une approche différente qui oblige le compilateur à écrire dans une ligne de cache (l'optimiseur pourrait supprimer la variable supplémentaire) que vous pouvez déclarer les variables
volatile . Cela dégradera un peu les performances, car il oblige à traverser la cache L1 (et s'il y a un faux partage, cela pourrait finir par aller au cache L2-L3)Désolé de négliger des informations importantes telles que la plate-forme et le système d'exploitation, car je devais terminer la soumission pressée. Les calculs sont effectués sur la plate-forme X86_64 et 64 bits Linux (Scientific Linux). Voici une partie de / proc / cpuinfo et / proc / version:
Proc / Version: Linux Version 2.6.18-238.1.1.EL5 Version GCC 4.1.2 20080704 (Rouge Hat 4.1.2-50) Notez que Scientific Linux est une variante de Redhat
@David Rodriguez: C'était la situation que je pensais, mais le problème que je pensais avoir vu, c'était que le processeur pouvait être censé sauver l'état exact des registres, par opposition à une conversion logique à son "majoré" état significatif "l'état le plus proche. Bo Persson, dans un commentaire ci-dessous, cite les instructions FSAVE / FRSTOR que je m'attendrais à être utilisées dans une situation de change de contexte.