optimization - que - Optimizando el bucle MUL del ensamblador x64

que es una directiva en ensamblador

Question

Estoy escribiendo código de matemáticas que necesita multiplicar números grandes rápidamente. Se desglosa en multiplicaciones de una matriz de enteros con un solo entero. En C ++ esto se ve así (en unsigned):

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 manualmente, lo convertí a 64 bits y trabajé en la salida del compilador .asm para optimizarlo 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 comparo esto, encuentro que toma aproximadamente 6.3 ciclos en promedio por multiplicación en mi Core2 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, por lo que necesito mover los datos y no puedo clasificarlos como "multiplicar en paralelo".

¿Alguna idea a alguien?

Actualización: Después de algunas pruebas más, logré llevar la velocidad a aproximadamente 5.4 ciclos por MUL de 64 bits (que incluye todos los gastos generales de adición, movimiento y bucle). Supongo que esto es lo mejor que puede 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 ciclos (resp. 7). Sandy Bridge será mucho mejor con un rendimiento de 1 y una latencia de 3 (resp. 4) ciclos.

Con respecto 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, reconozco que los AMD tienen una unidad MUL más rápida que los chips Intel (más antiguos).

Answer 1

¿Contiene r algo importante antes de la llamada?

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

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

Esto puede mejorar significativamente el rendimiento. Cómo ? Actualmente, sus cachés están recuperando líneas de caché de a, recuperando líneas de caché de r y escribiendo líneas de caché de nuevo en r. Con las tiendas de transmisión de llamadas, solo obtendrías líneas de caché de una y escritas directamente a r: mucho menos tráfico de bus. Si observa cualquier implementación de memcpy de CRT moderna, cambiará a usar almacenes de transmisión por encima de un umbral relacionado con el tamaño del caché (y se ejecutará casi el doble de rápido que un memcpy usando movimientos convencionales).

Answer 2

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

Answer 3

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

Answer 4

Una vez escribí un bucle que se ve así, 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.

Intentaría obtener una [i] y r [i]

Si utiliza gcc, use la función __builtin_prefetch () o la instrucción PREFETCHT0 en el ensamblador

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

Cuando esto funciona, los resultados pueden ser dramáticos. Siempre que el bucle tenga alrededor de mil iteraciones, prefiero obtener a [i + 64] yr [i + 64] como punto de partida y ver cuánta diferencia hace en su CPU. Es posible que deba intentar distancias mayores de captación previa.