Optimización del ensamblador x64 MUL loop

Question

Estoy escribiendo un código matemático que necesita multiplicar grandes números rápidamente. Se divide en multiplicaciones de una matriz de enteros con un solo entero. En C++ esto se parece a esto (el de signo):

void muladd(unsigned* r, const unsigned* a, unsigned len, unsigned b) { 
    unsigned __int64 of = 0; // overflow 
    unsigned i = 0; // loop variable 
    while (i < len) { 
     of += (unsigned __int64)a[i] * b + r[i]; 
     r[i] = (unsigned)of; 
     of >>= 32; 
     ++i; 
    } 
    r[i] = (unsigned)of; // save overflow 
} 

Desenrollé este bucle de forma manual, lo convirtieron a 64 bits y trabajaron en la salida asm compilador para optimizar aún más. El bucle principal asm ahora se ve así:

mov rax, rdi        ; rdi = b 
mul QWORD PTR [rbx+r10*8-64]    ; rdx:rax = a[i] * b; r10 = i 
mov rsi, QWORD PTR [r14+r10*8-64]  ; r14 = r; rsi = r[i] 
add rax, rsi 
adc rdx, 0 
add rax, r11        ; r11 = of (low part) 
adc rdx, 0 
mov QWORD PTR [r14+r10*8-64], rax  ; save result 
mov r11, rdx 

; this repeats itself 8 times with different offsets 

Cuando este punto de referencia, encuentro que se tarda unos 6,3 ciclos en avarage_nus por la multiplicación en mi Core 2 Quad.

Mi pregunta es: ¿puedo acelerar esto de alguna manera? Desafortunadamente, no veo forma de evitar una de las adiciones y la multiplicación siempre necesita RDX: RAX, así que necesito mover los datos y no puedo "multiplicar en paralelo".

¿Alguna idea a alguien?

Actualización: Después de algunas pruebas más, me las he arreglado para llevar la velocidad hasta alrededor de 5,4 ciclos por 64 bits MUL (que incluye todos los complementos, se mueven y los gastos generales de bucle). Supongo que esto es lo mejor que puedes obtener en un Core2, ya que el Core2 no tiene una instrucción MUL muy rápida: tiene un rendimiento de 3 y una latencia de 6 (respectivamente 7) ciclos. Sandy Bridge será mucho mejor con un rendimiento de 1 y una latencia de 3 (resp 4) ciclos.

En cuanto al número mucho menor para GMP: lo obtuve de su código fuente y me parece que es un número teórico. Pero lo que es seguro es que es un número que se calculó para una CPU AMD K9. Y por lo que he leído, los AMD tienen una unidad MUL más rápida que los chips Intel (más antiguos).

Answer 1

Parece que su rutina podría beneficiarse de SSE. PMULLD y PADDD parecen instrucciones relevantes. No estoy seguro de por qué su compilador no produce SSE a partir de eso.

Answer 2

Solo me gustaría señalar que el conteo cíclico es bastante inútil ya que sus instrucciones se convertirán en microcódigo que se ejecutará fuera de orden o en pausa, dependiendo de todo lo demás que esté haciendo la CPU. Si tiene una rutina rápida, que es lo que hace, no es realmente fructífero intentar eliminar un ciclo teórico a menos que sepa que su rutina siempre se ejecutará en completo aislamiento.

Answer 3

Una vez escribí un bucle que se parece bastante a esto, con una cantidad mínima de procesamiento en una gran cantidad de datos con el resultado de que el bucle estaba limitado por la velocidad de la memoria.

que iba a tratar la obtención previa a [i] y R [i]

si se utiliza gcc utilizar el __builtin_prefetch() la función o instrucción en ensamblador PREFETCHT0

http://gcc.gnu.org/onlinedocs/gcc-3.3.6/gcc/Other-Builtins.html

Cuando esto funciona los resultados puede ser dramático Siempre que el bucle tenga una longitud de mil iteraciones, preferiría un [i + 64] yr [i + 64] como punto de partida y vería cuánta diferencia hace en su CPU. Es posible que deba probar distancias de captación previa más grandes.

Answer 4

¿Hay algo importante antes de la llamada?

Si lo hace, y se está acumulando en él, entonces deje de leer ahora.

Si no es así (es decir, siempre se está acumulando en ceros), y suponiendo que está invocando esta función en matrices significativamente mayores que los tamaños de caché, entonces estaría buscando una manera de eliminar la necesidad de lea de ry para convertir el "resultado guardado" MOV en MOVNT (_mm_stream_ps en intrínsecos).

Esto puede mejorar significativamente el rendimiento. Cómo ? Actualmente, las memorias caché están obteniendo líneas de caché de a, recuperando líneas de caché de ry escribiendo las líneas de caché en r. Con las llamadas tiendas de transmisión de datos, obtendría líneas de caché de una y de escritura directa a r: mucho menos tráfico de bus. Si observas la implementación de memcpy de un CRT moderno, pasará a usar almacenes de transmisión por encima de un umbral relacionado con el tamaño de caché (y ejecutará almost twice as fast como memcpy usando movimientos convencionales).