Comparación de punto flotante irreproducibilidad

Question

Yo y mi Ph.D. un alumno ha encontrado un problema en un contexto de análisis de datos de física que podría utilizar para obtener información. Tenemos un código que analiza los datos de uno de los experimentos de LHC que brinda resultados irreproducibles. En particular, los resultados de los cálculos obtenidos del mismo binario, ejecutados en la misma máquina pueden diferir entre ejecuciones sucesivas. Somos conscientes de las muchas fuentes diferentes de irreproducibilidad, pero hemos excluido a los sospechosos habituales.

Hemos rastreado el problema hasta la irreproducibilidad de las operaciones de comparación de coma flotante (precisión doble) al comparar dos números que nominalmente tienen el mismo valor. Esto puede suceder ocasionalmente como resultado de los pasos previos en el análisis. Un ejemplo acabamos de encontrar un ejemplo que prueba si un número es menor que 0.3 (tenga en cuenta que NUNCA evaluamos la igualdad entre valores flotantes). Resulta que debido a la geometría del detector, era posible que el cálculo produjera ocasionalmente un resultado que sería exactamente 0.3 (o su representación de precisión doble más cercana).

Somos muy conscientes de las dificultades que existen al comparar los números de punto flotante y también con la posibilidad de que la precisión excesiva en la FPU afecte los resultados de la comparación. La pregunta que me gustaría responder es "¿por qué los resultados son irreproducibles?" ¿Es porque la carga de registro FPU u otras instrucciones FPU no están despejando los bits en exceso y, por lo tanto, los bits "sobrantes" de los cálculos anteriores están afectando los resultados? (Esto parece improbable) Vi una sugerencia en otro foro que el contexto cambia entre procesos o subprocesos también podría inducir un cambio en los resultados de comparación de coma flotante debido a que los contenidos de la FPU se almacenan en la pila y, por lo tanto, se truncan. Cualquier comentario sobre estas = u otras explicaciones posibles sería apreciado.

Answer 1

¿Qué plataforma?

La mayoría de las FPU pueden almacenar internamente más precisión que la doble representación de ieee, para evitar el error de redondeo en los resultados intermedios. A menudo hay un cambio de compilador para cambiar la velocidad/precisión - ver http://msdn.microsoft.com/en-us/library/e7s85ffb(VS.80).aspx

Answer 2

Supongo que lo que sucede es que tus cálculos normalmente se llevan a cabo con unos pocos bits adicionales de precisión dentro de la FPU, y solo redondean en puntos específicos (por ejemplo, cuando asigna un resultado a un valor).

Cuando hay un cambio de contexto, sin embargo, el estado de la FPU tiene que ser salvados y restaurados - y hay al menos una posibilidad bastante justo que esos bits adicionales son no siendo salvados y restaurados en el cambio de contexto. Cuando sucede, eso probablemente no causaría un cambio importante, pero si (por ejemplo) luego restas una cantidad fija de cada uno y multiplicas lo que queda, la diferencia también se multiplicará.

Para ser claros: dudo que los "sobrantes" bits sean los culpables. Más bien, sería la pérdida de bits adicionales que causan el redondeo en puntos ligeramente diferentes en el cálculo.

Answer 3

La FPU interna de la CPU puede almacenar puntos flotantes con mayor precisión que el doble o el flotante. Estos valores se deben convertir siempre que los valores en el registro se almacenen en otro lugar, incluso cuando la memoria se intercambia en caché (esto lo sé con certeza) y un cambio de contexto o interrupción del sistema operativo en ese núcleo suena como otra fuente fácil . Por supuesto, el momento de las interrupciones del sistema operativo o los cambios de contexto o el intercambio de memoria no caliente es completamente impredecible e incontrolable por la aplicación.

Por supuesto, esto depende de la plataforma, pero su descripción parece que se ejecuta en un escritorio moderno o servidor (por lo que x86).

Answer 4

Hice este:

#include <stdio.h> 
#include <stdlib.h> 

typedef long double ldbl; 

ldbl x[1<<20]; 

void hexdump(void* p, int N) { 
    for(int i=0; i<N; i++) printf("%02X", ((unsigned char*)p)[i]); 
} 

int main(int argc, char** argv) { 

    printf("sizeof(long double)=%i\n", sizeof(ldbl)); 

    if(argc<2) return 1; 

    int i; 
    ldbl a = ldbl(1)/atoi(argv[1]); 

    for(i=0; i<sizeof(x)/sizeof(x[0]); i++) x[i]=a; 

    while(1) { 
    for(i=0; i<sizeof(x)/sizeof(x[0]); i++) if(x[i]!=a) { 
     hexdump(&a, sizeof(a)); 
     printf(" "); 
     hexdump(&x[i], sizeof(x[i])); 
     printf("\n"); 
    } 
    } 

} 

compilado con IntelC utilizando/Qlong_double, de modo que produce esto:

;;;  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 

y comenzaron 10 instancias con diferentes "semillas". Como puede ver, compara los dobles de 10 bytes de la memoria con uno en la pila FPU, por lo que en el caso en que el sistema operativo no conserve la precisión total, seguramente veríamos un error. Y bueno, todavía se están ejecutando sin detectar nada ... lo cual no es realmente sorprendente, porque x86 tiene comandos para guardar/restaurar todo el estado de FPU a la vez, y de todos modos un sistema operativo que no conservará la precisión completa estar completamente roto.

Así que, o algunas de ellas únicas de su OS/cpu/compilador, o la comparación de resultados diferentes se producen después de cambiar algo en el programa y volver a compilar, o su un error en el programa, por ejemplo. un desbordamiento del búfer.

Answer 5

¿El programa tiene varios subprocesos?

En caso afirmativo, sospecho que se trata de una condición de carrera.

Si no, la ejecución del programa es determinista. El más probable para obtener diferentes resultados con las mismas entradas es el comportamiento indefinido, es decir, un error en su programa. Leer una variable no inicializada, un puntero obsoleto, sobrescribir los bits más bajos de algún número FP de la pila, etc. Las posibilidades son infinitas. Si está ejecutando esto en Linux, intente ejecutarlo en valgrind y ver si descubre algunos errores.

Por cierto, ¿cómo redujo el problema a la comparación FP?

(? Disparo: errores en el hardware Por ejemplo, en su defecto chip de memoria RAM podría ocasionar que los datos se leen de manera diferente en diferentes ocasiones sin embargo, que probablemente habría bloquear el sistema operativo con bastante rapidez..)

Cualquier otra explicación es plausible - - Los errores en el sistema operativo o HW no habrían desaparecido por mucho tiempo.

Answer 6

Voy a fusionar algunos de los comentarios de David Rodriguez y Bo Persson y hacer una conjetura desenfrenada.

¿Podría ser una tarea de cambio mientras se usan las instrucciones de SSE3? Basado en este Intel article on using SSE3 instructions, los comandos para preservar el estado de registro FSAVE y FRESTOR han sido reemplazados por FXSAVE y FXRESTOR, que deben manejar la longitud total del acumulador.

En una máquina x64, supongo que la instrucción "incorrecta" podría estar contenida en alguna biblioteca externa compilada.

Answer 7

Seguramente está tocando GCC Bug n°323, lo cual, como otros señalan, se debe a la precisión excesiva de la FPU.

Soluciones:

• Uso de SSE (o AVX, es ... 2016) para llevar a cabo sus cálculos
• Utilizando el interruptor -ffloat-store compilación. De los documentos de GCC.

No almacenar las variables de coma flotante en registros, e inhiben otras opciones que podrían cambiar si un valor de punto flotante se toma de un registro o memoria.
Esta opción evita el exceso de precisión indeseable en máquinas como la 68000 donde los registros flotantes (del 68881) mantienen más precisión de la que se supone que tiene un doble. Similarmente para la arquitectura x86. Para la mayoría de los programas, el exceso de precisión solo funciona, pero algunos programas se basan en la definición precisa del punto flotante IEEE. Use -ffloat-store para tales programas, después de modificarlos para almacenar todos los cálculos intermedios pertinentes en variables.