Accelerare x64 assembler ADD loop

Question

Sto lavorando su aritmetica per la moltiplicazione di interi molto lunghi (circa 100.000 cifre decimali). Come parte della mia biblioteca, aggiungo due lunghi numeri.

Il profilo mostra che il mio codice viene eseguito fino al 25% del tempo nelle routine add() e sub(), quindi è importante che siano il più veloci possibile. Ma non vedo molto potenziale, ancora. Forse puoi darmi un aiuto, consigli, idee o idee. Li metterò alla prova e tornerò da te.

Finora la mia routine di add fa un po 'di messa a punto e quindi utilizza un 8 volte ciclo srotolato:

mov rax, QWORD PTR [rdx+r11*8-64] 
mov r10, QWORD PTR [r8+r11*8-64] 
adc rax, r10 
mov QWORD PTR [rcx+r11*8-64], rax 

altre 7 blocchi con diversi offset seguono e poi loop.

Ho provato a caricare i valori dalla memoria in precedenza, ma ciò non ha aiutato. Immagino che sia a causa del buon prefetching. Io uso una CPU Intel i7-3770 Ivy Bridge a 4 core. Ma mi piacerebbe scrivere un codice che funzioni bene su qualsiasi CPU moderna.

Modifica: ho eseguito alcuni tempi: aggiunge 1k parole in circa 2,25 cicli/parola. Se rimuovo l'ADC, quindi rimangono solo i MOV, ci vogliono ancora circa 1,95 cicli/parola. Quindi il collo di bottiglia principale sembra essere l'accesso alla memoria. Una libreria memcpy() funziona in circa 0,65 cicli/parola, ma ha solo un input, non due. Eppure, è molto più veloce a causa del suo uso di registri SSE, immagino.

Alcune domande:

• È utile usare "carico, carico, aggiungere, negozio di" struttura o sarebbe un "carico, add-a-memoria" aiutare? Finora i miei test non hanno mostrato alcun vantaggio.
• Come al solito, non è previsto alcun aiuto da SSE (2,3,4)?
• L'indirizzamento (indice scalato più base più offset) ha un impatto negativo? Potrei usare ADD r11, 8 invece.
• E il ciclo di svolgimento? Ho letto che lo srotolamento era negativo per l'architettura Sandy Bridge (Agner Fog http://www.agner.org/optimize/). È preferibile o evitato?
• (Modifica) Posso utilizzare i registri SSE per caricare e archiviare parole in blocchi più grandi dalla memoria e scambiare in modo efficiente parole con registri di uso generale e registri SSE?

Apprezzo molto qualsiasi commento.

Answer 1

Provare a prefetch prima i dati (si potrebbe provare prima a leggere più blocchi di dati in registri x64 quindi eseguire i calcoli), verificare se i dati sono allineati correttamente nella memoria, inserire il codice loop all'etichetta allineata a 16, provare a rimuovere SIB affrontare

Si potrebbe anche provare ad accorciare il codice per:

mov rax, QWORD PTR [rdx+r11*8-64] 
adc rax, QWORD PTR [r8+r11*8-64] 
mov QWORD PTR [rcx+r11*8-64], rax 

Answer 2

la dipendenza più difficile è la propagazione del carry tra ogni blocco di memoria; Proverò a mettere in primo piano un metodo per affrontarlo.

Il seguente frammento simula la propagazione del carico, ma con il "vantaggio" di non utilizzare il flag di trasporto. Questo può essere messo in parallelo per tre o quattro thread separati, ciascuno dei quali produce una mezza trasporta circa 25000 cifre decimali (o 10000 byte) a parte.Quindi la probabilità che quelli portino influenza solo un byte, parola, dword, ecc. Raggiungerà asintoticamente zero.

long long carry=0; 
for (int i=0;i<N;i++) { 
    carry += (long long)*a++ + (long long)*b++; 
    *c++ = carry; carry>>=32; 
} 

Secondo la mia profiling, carryless Inoltre utilizzando XMM avrebbe preso ~ 550ms (parole 1E9), il riporto simulato avrebbe preso ~ 1020ms e 4 vie versione parallelizzato prenderebbero ~ 820ms (senza alcuna ottimizzazione assemblatore).

Le ottimizzazioni architettoniche potrebbero includere l'uso di un sistema di numeri ridondanti, in cui il carry non deve essere continuamente propagato e dove la valutazione del carry può essere posticipata quasi all'infinito.

Answer 3

Sono abbastanza sicuro memcpy è più veloce perché non ha una dipendenza da dati di essere recuperati prima di poter eseguire l'operazione successiva.

Se si può organizzare il codice in modo che si fa qualcosa di simile:

mov rax, QWORD PTR [rdx+r11*8-64] 
mov rbx, QWORD PTR [rdx+r11*8-56] 
mov r10, QWORD PTR [r8+r11*8-64] 
mov r12, QWORD PTR [r8+r11*8-56] 
adc rax, r10 
adc rbx, r12 
mov QWORD PTR [rcx+r11*8-64], rax 
mov QWORD PTR [rcx+r11*8-56], rbx 

Io non sono sicuro al 100% che l'offset di -56 è il diritto per il codice, ma il concetto è " destra".

Vorrei anche prendere in considerazione di cache-hits/cache-collisioni. Per esempio. se hai tre blocchi di dati [che sembrerebbe quello che fai], assicurati che NON siano allineati allo stesso offset nella cache. Un cattivo esempio potrebbe essere se si allocano tutti i blocchi in un multiplo della dimensione della cache, dalla stessa posizione nella cache. Sovrallocazione e realizzazione SURE che i diversi blocchi di dati siano sfalsati di almeno 512 byte [quindi allocare il sovrametallo 4K e arrotondare fino all'indirizzo di confine 4K, quindi aggiungere 512 al secondo buffer e 1024 al terzo buffer]

Se i dati sono sufficientemente grandi (più grandi della cache L2), è possibile utilizzare MOVNT per recuperare/archiviare i dati. Ciò eviterà di leggere nella cache - questo è SOLO di vantaggio quando si hanno dati molto grandi, in cui la prossima lettura causerà semplicemente qualcos'altro che si potrebbe trovare "utile" per essere cacciato dalla cache, e non si otterrà back to it prima di averlo buttato fuori dalla cache in ogni caso - quindi memorizzare il valore nella cache non aiuta effettivamente ...

Modifica: Utilizzare SSE o simili non aiuterà, come spiegato qui: Can long integer routines benefit from SSE?