Detección de desbordamiento en suma

8

Supongamos que me dan una serie de norte enteros de ancho fijo (es decir, caben en un registro de ancho w), una1,una2,...unanorte. Quiero calcular la sumaS=una1+...+unanorte en una máquina con aritmética de complemento a 2, que realiza adiciones módulo 2wcon semántica envolvente. Eso es fácil, pero la suma puede desbordar el tamaño del registro, y si lo hace, el resultado será incorrecto.

Si la suma no se desborda, quiero calcularla y verificar que no haya desbordamiento, lo más rápido posible. Si la suma se desborda, solo quiero saber que sí, no me importa ningún valor.

Agregar ingenuamente números en orden no funciona, porque una suma parcial puede desbordarse. Por ejemplo, con registros de 8 bits,(120,120,-115) es válido y tiene una suma de 125, aunque la suma parcial 120+120 desborda el rango de registro [-128,127].

Obviamente, podría usar un registro más grande como acumulador, pero supongamos el caso interesante en el que ya estoy usando el tamaño de registro más grande posible.

Existe una técnica bien conocida para agregar números con el signo opuesto como la suma parcial actual . Esta técnica evita desbordamientos en cada paso, a costa de no ser amigable con el caché y no aprovechar mucho la predicción de rama y la ejecución especulativa.

¿Existe una técnica más rápida que tal vez aproveche el permiso para desbordar sumas parciales y sea más rápida en una máquina típica con un indicador de desbordamiento, un caché, un predictor de rama y ejecución y cargas especulativas?

(Este es un seguimiento de la suma segura de desbordamiento )

Gilles 'SO- deja de ser malvado'
fuente
¿Por qué la solución de Dave no funciona bien con cachés y tuberías en su opinión? Si hace algo similar a la partición Quicksort in situ con pivote virtual0 0, trata bien los cachés durante la partición y la siguiente suma. No sé acerca de las predicciones erróneas de las ramas durante la partición, pero la fase de suma también debería funcionar bien en ese sentido.
Raphael
@Raphael En mi aplicación, el desbordamiento es el caso excepcional. Condicionales correspondientes a "¿esto se desborda?" Por lo tanto, están bien servidos por la predicción de rama. Condicionales correspondientes a "¿es este número positivo?" No se puede predecir. El efecto de caché es leve, ya que tiene dos cursores en lugar de uno.
Gilles 'SO- deja de ser malvado'

Respuestas:

3

Puedes añadir norte números de tamaño w sin desbordamiento si está utilizando Iniciar sesiónnorte+wbits aritméticos. Mi sugerencia es hacer exactamente eso y luego verificar si el resultado está en el rango. Los algoritmos para la aritmética de multiprecisión son bien conocidos (consulte la sección 4.3 de TAOCP si necesita una referencia), a menudo hay soporte de hardware para la adición ( bandera de transporte y agregar con instrucciones de transporte ), incluso sin dicho soporte puede implementarlo sin salto dependiente de datos ( que es bueno para los predictores de salto) y solo necesita una pasada de los datos y puede visitar los datos en el orden más conveniente (que es bueno para el caché).

Si los datos no caben en la memoria, el factor limitante será el IO y qué tan bien logra superponer el IO con el cálculo.

Si los datos se ajustan en la memoria, probablemente tenga Iniciar sesiónnortew(La única excepción que se me ocurre es un microprocesador de 8 bits que generalmente tiene 64K de memoria), lo que significa que está haciendo aritmética de doble precisión. La sobrecarga sobre un bucle haciendow-la aritmética de bits puede ser solo dos instrucciones (una para firmar extender, la otra para agregar con carry) y un ligero aumento de la presión de registro (pero si estoy en lo cierto, incluso el registro hambriento x86 tiene suficientes registros para que el único acceso de memoria en el bucle interno puede recuperar los datos). Creo que es probable que un procesador OO pueda programar las operaciones adicionales durante la latencia de carga de memoria, por lo que el bucle interno se ejecutará a la velocidad de la memoria y, por lo tanto, el ejercicio será uno de maximizar el uso del ancho de banda disponible (prefetch o técnicas de intercalado podrían ayudar dependiendo de la arquitectura de la memoria).

Considerando el último punto, es difícil pensar en otros algoritmos con mejor rendimiento. Los saltos dependientes de los datos (y por lo tanto no predecibles) están fuera de discusión al igual que varios pases en los datos. Incluso tratar de usar los diversos núcleos del procesador actual sería difícil ya que el ancho de banda de la memoria probablemente estará saturado, pero podría ser una forma fácil de implementar el acceso intercalado.

Un programador
fuente
No puedo aumentar el tamaño de los registros en mi máquina. Supongamos que ya estoy usando el tamaño de registro más grande posible.
Gilles 'SO- deja de ser malvado'
@Gilles, los procesadores que sé que tienen la bandera de desbordamiento que desea que aprovechemos también tienen un carry y un complemento con instrucciones de carry . Incluso para aquellos que no lo hacen (¿algo más que MIPS?), La aritmética de multiprecisión sería un candidato serio (solo tiene un pase de datos, bueno para el caché), accede secuencialmente, bueno para el relleno previo de caché, -, y puede implementarse sin salto dependiente de datos - bueno para predictores de salto).
Programador
¿Qué quiere decir con "aritmética de multiprecisión"? Pensé que te referías al punto flotante. Pero muchas arquitecturas no tienen registros de punto flotante lo suficientemente grandes, si los hay. Digamos que estoy agregando enteros de 64 bits en amd64, o enteros de 32 bits en ARM sin VFP.
Gilles 'SO- deja de ser malvado'
@Gilles, quise decir lo que se describe en la sección 4.3 de TAOCP: el uso de varias palabras para representar valores que no se pueden contener en una palabra. Bignum es una variante donde el número de palabras se ajusta dinámicamente, supongo que aquí puede determinar un límite máximo para el número de palabras necesarias (es decir, 2 si sus datos están en la memoria; si no lo hace, trabajando en superponer el IO con cómputo será el primer punto de acción, estará obligado a IO) y solo utilícelo, será lo suficientemente bajo como para que manejar un número variable de palabras sea más costoso.
Programador
Ah ok ¿Podría aclarar esto en su respuesta? ¿Tiene referencias con tiempos y comparaciones con otros métodos?
Gilles 'SO- deja de ser malvado'
1

En una máquina donde los tipos enteros se comportan como un anillo algebraico abstracto [básicamente significa que se envuelven], uno podría calcular las sumas de los ítems [i] y (ítem [i] >> 16) para hasta aproximadamente 32767 ítems. El primer valor daría los 32 bits más bajos de la suma correcta. El último valor produciría los bits 16-47 de algo cercano a la suma correcta, y el uso del valor anterior puede ajustarse fácilmente para obtener los bits 16-47 de la suma exacta exacta.

El seudocódigo sería algo como:

Sum1=0 : Sum2 = 0
For up to 32768 items L[i] in list
  Sum1 = Sum1 +L[i]
  Sum2 = Sum2 +(L[i] >> 16) ' Use sign-extending shift
Loop
Sum1MSB = Sum1 >> 16 ' Cannot use division of numbers can be negative--see below
Sum2Mid = Sum2 and 65535
Sum2Adj = Sum1MSB - Sum2Mid
If Sum2Adj >= 32768 then Sum2Adj = Sum2Adj - 65536
Sum2 += Sum2Adj

Después del código anterior, Sum2 y Sum1 juntos deberían producir la suma correcta, independientemente de los desbordamientos intermedios. Si es necesario sumar más de 32768 números, se pueden dividir en grupos de 32768, y después de calcular Sum2 para cada grupo, se puede agregar a una "gran suma" de dos variables para todos los grupos en su conjunto.

En algunos idiomas, el operador de desplazamiento a la derecha podría ser reemplazado por una división por 65536. Eso generalmente funciona cuando se calcula Sum2, pero no cuando se extrae Sum1MSB. El problema es que algunos idiomas redondean las divisiones hacia cero, mientras que aquí es necesario realizar un redondeo de división al siguiente número más bajo (hacia el infinito negativo). Los errores de cálculo de Sum2 se corregirían más adelante, pero los errores de cálculo de Sum2LSB afectarían el resultado final.

Tenga en cuenta que nada en los resultados finales indicaría si alguno de los cálculos que involucran Sum1 se ha "desbordado", pero si se garantiza que los valores se ajustarán limpiamente, el código no debería tener que preocuparse por si se produjo algún desbordamiento.

Super gato
fuente