¿Cómo pueden hacerse deterministas los cálculos de punto flotante?

10 minutos de lectura

¿Como pueden hacerse deterministas los calculos de punto flotante
MetálicoSacerdote

El cálculo de coma flotante no es asociativo ni distributivo en los procesadores. Entonces,

(a + b) + c no es igual a a + (b + c)

y a * (b + c) no es igual a a * b + a * c

¿Hay alguna forma de realizar un cálculo de punto flotante determinista que no dé resultados diferentes? Sería determinista en uniprocesador, por supuesto, pero no sería determinista en programas de subprocesos múltiples si los subprocesos se suman a una suma, por ejemplo, ya que podría haber diferentes intercalados de los subprocesos.

Entonces, mi pregunta es, ¿cómo se pueden lograr resultados deterministas para los cálculos de punto flotante en programas de subprocesos múltiples?

  • Buena pregunta. Aunque la respuesta probablemente sea “no se puede” o “usar aritmética de precisión arbitraria”, es legítimo preguntarlo.

    – Alejandro C.

    9 de septiembre de 2011 a las 18:18

  • Además, ¿para qué tipo de campo necesitas esto? Hay disciplinas en las que esto es un problema real (la geometría computacional, por ejemplo) y otras para las que no hay problema con los cálculos de coma flotante tal como son (la mayoría de los campos en realidad, con algunas soluciones en las que esto realmente importa).

    – Alejandro C.

    9 de septiembre de 2011 a las 18:19


  • a + (b*c) no es igual a a*b + a*c“- ¿Alguna vez son iguales?

    -Austin Salonen

    9 de septiembre de 2011 a las 18:20


  • Alexander, lo necesito para la ejecución determinista, es decir, si ejecuto mi programa varias veces, da el mismo resultado. Esto facilita la depuración.

    – Sacerdote Metálico

    9 de septiembre de 2011 a las 18:20

  • Austin, sí lo corrigió ahora :)!

    – Sacerdote Metálico

    9 de septiembre de 2011 a las 18:21

¿Como pueden hacerse deterministas los calculos de punto flotante
Esteban Canon

Punto flotante es determinista Las mismas operaciones de coma flotante, ejecutadas en el mismo hardware, siempre producen el mismo resultado. No hay magia negra, ruido, aleatoriedad, fuzzing ni ninguna de las otras cosas que la gente suele atribuir al punto flotante. El hada de los dientes no aparece, tome las partes bajas de su resultado y deje un cuarto debajo de su almohada.

Ahora, dicho esto, ciertos algoritmos bloqueados que se usan comúnmente para cálculos paralelos a gran escala están no determinista en términos del orden en que se realizan los cálculos de punto flotante, lo que puede dar como resultado resultados no exactos en bits en las ejecuciones.

¿Qué puedes hacer al respecto?

Primero, asegúrese de que realmente no puede vivir con la situación. Muchas cosas que podría intentar para hacer cumplir el orden en un cómputo paralelo perjudicarán el rendimiento. Así es como es.

También me gustaría señalar que aunque los algoritmos bloqueados pueden introducir cierta cantidad de no determinismo, con frecuencia ofrecen resultados con menor errores de redondeo que los ingenuos algoritmos seriales desbloqueados (¡sorprendente pero cierto!). Si puede vivir con los errores producidos por un algoritmo serial ingenuo, probablemente pueda vivir con los errores de un algoritmo paralelo bloqueado.

Ahora, si realmente necesita una reproducibilidad exacta en las ejecuciones, aquí hay algunas sugerencias que tienden a no afectar demasiado el rendimiento:

  1. No utilice algoritmos de subprocesos múltiples que puedan reordenar los cálculos de coma flotante. Problema resuelto. Esto no significa que no pueda usar algoritmos de subprocesos múltiples, simplemente que debe asegurarse de que cada resultado individual solo sea tocado por un solo subproceso entre los puntos de sincronización. Tenga en cuenta que esto en realidad puede mejorar rendimiento en algunas arquitecturas si se hace correctamente, al reducir la contención D$ entre núcleos.

  2. En las operaciones de reducción, puede hacer que cada subproceso almacene su resultado en una ubicación indexada en una matriz, esperar a que finalicen todos los subprocesos y acumular los elementos de la matriz en orden. Esto agrega una pequeña cantidad de sobrecarga de memoria, pero generalmente es bastante tolerable, especialmente cuando la cantidad de subprocesos es “pequeña”.

  3. Encuentre formas de izar el paralelismo. En lugar de calcular 24 multiplicaciones de matrices, cada una de las cuales usa algoritmos paralelos, calcule 24 productos de matrices en paralelo, cada uno de los cuales usa un algoritmo en serie. Esto también puede ser beneficioso para el rendimiento (a veces enormemente).

Hay muchas otras maneras de manejar esto. Todos ellos requieren pensamiento y cuidado. La programación paralela generalmente lo hace.

  • Sin embargo, solo es determinista a nivel de código de máquina. Un programa en C compilado dos veces puede dar resultados diferentes.

    – Antimonio

    02/09/2012 a las 18:53

  • @ Antimony Estoy bastante confundido, parece que tú y Stephen están diciendo cosas diferentes. ¿Entonces a+b+c es o no es lo mismo que b+c+a?

    – Herman Toothrot

    06/09/2016 a las 23:20

1647682813 365 ¿Como pueden hacerse deterministas los calculos de punto flotante
R.. GitHub DEJAR DE AYUDAR A ICE

Editar: Eliminé mi respuesta anterior porque parece que no entendí bien la pregunta de OP. Si quieres verlo puedes leer el historial de edición.

Creo que la solución ideal sería cambiar a tener un acumulador separado para cada subproceso. Esto evita todos los bloqueos, lo que debería marcar una diferencia drástica en el rendimiento. Simplemente puede sumar los acumuladores al final de toda la operación.

Alternativamente, si insiste en usar un solo acumulador, una solución es usar “punto fijo” en lugar de punto flotante. Esto se puede hacer con tipos de punto flotante al incluir un término de “sesgo” gigante en su acumulador para bloquear el exponente en un valor fijo. Por ejemplo, si sabe que el acumulador nunca excederá 2 ^ 32, puede iniciar el acumulador en 0x1p32. Esto lo bloqueará con 32 bits de precisión a la izquierda del punto de base y 20 bits de precisión fraccionaria (suponiendo que double). Si eso no es suficiente precisión, podría usar un sesgo más pequeño (suponiendo que el acumulador no crecerá demasiado) o cambiar a long double. Si long double es un formato extendido de 80 bits, un sesgo de 2^32 daría 31 bits de precisión fraccionaria.

Luego, cada vez que desee “usar” el valor del acumulador, simplemente reste el término de sesgo.

  • Está hablando de escenarios como este: tiene dos subprocesos, cada uno de los cuales agrega un valor de punto flotante al mismo acumulador. Si no controla el orden en que ocurren las adiciones, puede obtener (accumulator + thread A value) + thread B value o (accumulator + thread B value) + thread A valueque puede no ser igual debido al redondeo.

    – Esteban Canon

    09/09/2011 a las 19:00

  • OK, la pregunta no estaba muy clara entonces. De todos modos, me parece que cada subproceso debería tener su propio acumulador, y todos se pueden sumar al final.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de septiembre de 2011 a las 19:06

  • Eso también evitaría el bloqueo del acumulador, lo que casi seguramente hace que todo el proceso sea un orden de magnitud más lento que si fuera solo un subproceso…

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 sep 2011 a las 19:10

  • @Stephen: Reemplacé mi respuesta con algunas ideas nuevas.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de septiembre de 2011 a las 19:18

Incluso el uso de un tipo de datos de punto fijo de alta precisión no resolvería el problema de hacer que los resultados de dichas ecuaciones sean deterministas (excepto en ciertos casos). Como Keith Thompson señaló en un comentario, 1/3 es un contraejemplo trivial de un valor que no se puede almacenar correctamente en una representación de coma flotante estándar de base 10 o base 2 (independientemente de la precisión o la memoria utilizada).

Una solución que, dependiendo de las necesidades particulares, puede solucionar este problema (todavía tiene límites) es utilizar un Número racional tipo de datos (uno que almacena tanto un numerador como un denominador). Keith sugirió BPF como una de esas bibliotecas:

GMP es una biblioteca gratuita para aritmética de precisión arbitraria, que opera en enteros con signo, numeros racionalesy números de punto flotante. No hay límite práctico para la precisión…

Si es adecuado (o adecuado) para esta tarea es otra historia…

Codificación feliz.

  • La inexactitud de 1.0/3.0 no tiene nada que ver con el no determinismo.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de septiembre de 2011 a las 19:53

  • Tiene mucho que ver con eso: si no fuera por eso, no importaría si tiene 1/3+1/3+1/3 o (1+1+1)/3, por lo que es una elección no determinista. entre esos dos métodos no haría que el resultado fuera no determinista.

    – Aleatorio832

    9 sep 2011 a las 20:53

  • @R.. ¡Me atrapó! 🙂 Lo usé allí para mostrar que no todos los números se pueden almacenar en un espacio finito usando la codificación estándar. Sin embargo, dado que no hay división en las preguntas, es menos útil de lo que podría ser como ejemplo. Suponiendo una precisión limitada, todavía es fácil encontrar ejemplos cuando el orden de las operaciones de FP es importante. + y *.

    usuario166390

    9 sep 2011 a las 20:53


  • Estaba tratando 1.0/3.0 como una cantidad atómica, no como una división.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 sep 2011 a las 21:30


  • @R.. Pero no es un exacto cantidad atómica en punto flotante exponente de mantisa estándar o punto flotante de precisión fija. Si hubiera una división, sería fácil argumentar el caso proporcionado por Random8321: los valores intermedios son simplemente no representable adecuadamente en esa forma con cualquier suma de memoria. Con solo la suma y la multiplicación, creo que el argumento debe reducirse a “para una precisión limitada”.

    usuario166390

    9 de septiembre de 2011 a las 21:59


1647682813 350 ¿Como pueden hacerse deterministas los calculos de punto flotante
keith thompson

Intente almacenar cada resultado intermedio en un objeto volátil:

volatile double a_plus_b = a + b;
volatile double a_plus_b_plus_c = a_plus_b + c;

Es probable que esto tenga efectos desagradables en el rendimiento. Sugiero medir ambas versiones.

EDITAR: El propósito de volatile es inhibir las optimizaciones que podrían afectar los resultados incluso en un entorno de subproceso único, como cambiar el orden de las operaciones o almacenar resultados intermedios en registros más amplios. No aborda problemas de subprocesos múltiples.

EDIT2: Otra cosa a tener en cuenta es que

Una expresión flotante puede ser contratadoes decir, evaluado como si fuera una operación atómica, omitiendo así los errores de redondeo implícitos en el código fuente y el método de evaluación de expresiones.

Esto se puede inhibir usando

#include <math.h>
...
#pragma STDC FP_CONTRACT off

Referencia: estándar C99 (PDF grande), secciones 7.12.2 y 6.5 párrafo 8. Esto es específico de C99; algunos compiladores podrían no admitirlo.

  • Todavía no es “determinista”. El orden de las operaciones, para cualquier número de almacenamiento finito, sigue siendo importante. (Sin embargo, usando un fijo alta precisión tipo puede ayudar.)

    usuario166390

    9 de septiembre de 2011 a las 18:20


  • pst, tipo fijo de alta precisión? ¿Qué quieres decir con eso?

    – Sacerdote Metálico

    9 de septiembre de 2011 a las 18:24

  • @Metallic Hay un nivel de precisión que un conjunto finito de memoria no puede almacenar.

    usuario166390

    9 de septiembre de 2011 a las 18:29

  • Un tipo decimal no ayudará si necesita calcular 1.0/3.0.

    –Keith Thompson

    9 de septiembre de 2011 a las 18:29

  • Decimal no hace nada para solucionar este problema. La no asociatividad no es exclusiva de los formatos binarios de punto flotante.

    – Esteban Canon

    9 de septiembre de 2011 a las 19:03

Utilizar decimal empaquetado.

  • Decimal no hace nada para solucionar este problema. La no asociatividad no es exclusiva de los formatos binarios de coma flotante.

    – Esteban Canon

    9 de septiembre de 2011 a las 19:03

  • Cada formato de coma flotante (incluso los formatos decimales) incurre en redondeo (la única alternativa sería usar un número ilimitado de dígitos).

    – Esteban Canon

    9 sep 2011 a las 21:32


  • Decimal no hace nada para solucionar este problema. La no asociatividad no es exclusiva de los formatos binarios de coma flotante.

    – Esteban Canon

    9 de septiembre de 2011 a las 19:03

  • Cada formato de punto flotante (incluso los formatos decimales) incurre en redondeo (la única alternativa sería usar un número ilimitado de dígitos).

    – Esteban Canon

    9 sep 2011 a las 21:32


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad