Ottimizzazione dell'assembler x64 Ciclo MUL

Question

Scrivo codice matematico che deve moltiplicare rapidamente i numeri grandi. Si riduce alle moltiplicazioni di un array di numeri interi con un singolo intero. In C++ questa si presenta così (su di 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 
} 

ho srotolate questo ciclo manualmente, convertito a 64 bit e ha lavorato sull'uscita .asm compilatore per ottimizzare ulteriormente. Il ciclo .asm principale appare come segue:

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 

Quando ho benchmark questo, trovo che ci vogliono circa 6,3 cicli in media di marea per la moltiplicazione sulla mia Core2 Quad.

La mia domanda è: posso accelerare in qualche modo? Sfortunatamente, non vedo alcun modo per evitare una delle aggiunte e la moltiplicazione ha sempre bisogno di RDX: RAX, quindi ho bisogno di spostare i dati e non posso "moltiplicare in parallelo".

Qualche idea a qualcuno?

Aggiornamento: Dopo un po 'di più test, sono riuscito a portare la velocità fino a circa 5,4 cicli al 64-bit MUL (che include tutti aggiungere, spostare e spese generali loop). Immagino che questo sia il meglio che puoi ottenere su un Core2, dal momento che il Core2 non ha un'istruzione MUL molto veloce: ha un throughput di 3 e una latenza di 6 (o 7) cicli. Sandy Bridge sarà molto meglio con un throughput di 1 e una latenza di 3 (o 4) cicli.

Per quanto riguarda il numero molto inferiore per GMP: l'ho ottenuto dal loro codice sorgente e mi sembra che sia un numero teorico. Ma quello che è sicuro è che è un numero che è stato calcolato per una CPU AMD K9. E da quello che ho letto ho scoperto che le AMD hanno un'unità MUL più veloce rispetto ai (vecchi) chip Intel.

Answer 1

Sembra che la tua routine possa beneficiare di SSE. PMULLD e PADDD sembrano istruzioni pertinenti. Non sono sicuro del motivo per cui il tuo compilatore non produce SSE da quello.

Answer 2

Vorrei solo precisare che il conteggio dei cicli è piuttosto inutile in quanto le istruzioni verranno convertite in microcodice che verrà eseguito senza ordine o sospeso a seconda di qualsiasi altra cosa stia facendo la CPU. Se hai una routine veloce, cosa che fai, non è davvero fruttuoso cercare di sbarazzarti di un ciclo teorico a meno che tu non sappia che la tua routine funzionerà sempre in completo isolamento.

Answer 3

Una volta ho scritto un ciclo simile a questo, con una quantità minima di elaborazione su molti dati con il risultato che il ciclo era limitato dalla velocità della memoria.

mi piacerebbe provare prefetching a [i] e r [i]

se si utilizza gcc utilizzare la funzione __builtin_prefetch() o istruzione PREFETCHT0 in assembler

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

Quando questo funziona i risultati può essere drammatico. Fintanto che il ciclo dura un migliaio di iterazioni, mi piacerebbe prefetch un [i + 64] e r [i + 64] come punto di partenza e vedere quanta differenza fa sulla tua CPU. Potrebbe essere necessario provare a percorrere distanze di prefetch maggiori.

Answer 4

R contiene qualcosa di importante prima della chiamata?

Se lo fa, e ci stai accumulando sopra, quindi smetti di leggere ora.

Se non lo fa (cioè si accumula sempre su zeri) e supponendo che si stia invocando questa funzione su array significativamente più grandi delle dimensioni della cache, allora sarei in cerca di un modo per eliminare la necessità di leggere da r e convertire il "save result" MOV in un MOVNT (_mm_stream_ps in intrinseche).

Ciò può migliorare significativamente le prestazioni. Come ? Attualmente le cache recuperano le linee della cache da una, recuperando le linee della cache da r e scrivendo le linee della cache su r. Con i cosiddetti negozi in streaming si recuperano solo le linee della cache da una e direttamente dalla scrittura alla r: molto meno il traffico del bus. Se si guarda a qualsiasi implementazione di memcpy di CRT moderna, passerà all'utilizzo di negozi di streaming sopra una soglia relativa alla dimensione della cache (ed eseguirà almost twice as fast come memcpy usando le mosse convenzionali).