In passato, la risposta a questa domanda era un solido, "no". Ma a partire dal 2017, la situazione sta cambiando.
Ma prima di continuare, il tempo per un po 'di sfondo terminologia:
- completa Word aritmetica
- parziale Word aritmetica
Full-Word Aritmetica:
Questo è la rappresentazione standard in cui è memorizzato il numero nella base 2 o 2 utilizzando una matrice di numeri interi a 32 o 64 bit. Molte librerie e applicazioni bignum (inclusa GMP) utilizzano questa rappresentazione.
Nella rappresentazione a parola intera, ogni numero intero ha una rappresentazione univoca. Operazioni come i confronti sono facili. Ma cose come l'aggiunta sono più difficili a causa della necessità di trasportare-propagazione.
È questa trasporta- zione che rende l'aritmetica dei bignum quasi impossibile da vettorizzare.
parziale-Word aritmetica
Questa è una rappresentazione meno utilizzato quando il numero usa una base inferiore della parola-size hardware. Ad esempio, mettendo solo 60 bit in ogni parola a 64 bit. O utilizzando la base 1,000,000,000 con una dimensione word a 32 bit per l'aritmetica decimale.
Gli autori di GMP chiamano questo "chiodi" dove il "chiodo" è la parte inutilizzata della parola.
In passato, l'utilizzo dell'aritmetica di parole parziali era principalmente limitato alle applicazioni che lavorano in basi non binarie. Ma al giorno d'oggi, sta diventando più importante in quanto consente di ritardare la propagazione del carry.
Problemi con Full-Word aritmetica:
Vettorizzazione full-parola aritmetica è stata storicamente una causa persa:
- SSE/AVX2 non ha il supporto per i carry-propagazione.
- SSE/AVX2 non ha aggiunta/sub di 128 bit.
- SSE/AVX2 ha integer 64 x 64 bit moltiplicare. *
* AVX512-DQ aggiunge un inferiore della metà 64x64 bit moltiplicano. Ma non ci sono ancora istruzioni per la parte superiore.
Inoltre, x86/x64 ha un sacco di specializzati scalari istruzioni per bignum:
- Add-con-Carry:
adc, adcx, adox.
- Multiplo di parola doppia: Single-operando
mul e mulx.
Alla luce di questo, sia Bignum-add e bignum-multiply sono difficili per SIMD a battere scalare su x64. Sicuramente non con SSE o AVX.
Con AVX2, SIMD è quasi competitivo con scalari bignum-moltiplicare se riorganizzare i dati per abilitare "vettorizzazione verticale" di 4 diversa (e indipendenti) moltiplica delle stesse lunghezze in ciascuno dei 4 corsie SIMD.
AVX512 punta le cose più a favore di SIMD assumendo nuovamente la vettorizzazione verticale.
Ma per la maggior parte, la "vettorizzazione orizzontale" di bignum è in gran parte ancora una causa persa a meno che non ne possiate molti (della stessa dimensione) e possano permettervi il costo di trasposizione per renderli "verticali".
Vettorizzazione di parziale-Word aritmetica
Con parziale parola aritmetica, i bit "unghie" extra consentono di ritardare carry-propagazione.
Quindi, finché non si eccede la parola, SIMD add/sub può essere eseguito direttamente. In molte implementazioni, la rappresentazione di parole parziali utilizza numeri interi con segno per consentire alle parole di diventare negative.
Poiché non è (solitamente) necessario eseguire il carryout, SIMD add/sub di parziali parole può essere eseguito in modo altrettanto efficiente su bignum sia verticalmente che orizzontalmente.
Portare su binari a vettori orizzontali è ancora economico in quanto basta spostare i chiodi sulla corsia successiva.Un carryout completo per cancellare completamente le punte delle unghie e ottenere una rappresentazione unica di solito non è necessario a meno che non sia necessario fare un confronto tra due numeri quasi identici.
La moltiplicazione è più complicata con l'aritmetica a parole parziali poiché è necessario gestire i bit dell'unghia. Ma come con add/sub, è comunque possibile farlo in modo efficiente su bignum a vettori orizzontali.
AVX512-IFMA (in arrivo con i processori Cannonlake) avrà istruzioni che forniscono i 104 bit completi di una moltiplicazione 52 x 52 bit (presumibilmente utilizzando l'hardware FPU). Ciò funzionerà molto bene con le rappresentazioni di parole parziali che usano 52 bit per parola.
Grandi moltiplicazione utilizzando FFT
Per davvero grandi bignum, moltiplicazione avviene in modo più efficiente utilizzando Fast-Fourier Transforms (FFTs).
FFT sono completamente vettorializzabili poiché lavorano su double s indipendenti. Questo è possibile perché fondamentalmente la rappresentazione che FFT usa è una rappresentazione parziale di parole.
Per riassumere, è possibile la vettorizzazione dell'aritmetica bignum. Ma i sacrifici devono essere fatti.
Se si prevede che SSE/AVX sia in grado di accelerare alcuni codici bignum esistenti senza modifiche fondamentali alla rappresentazione e/o al layout dei dati, è improbabile che ciò accada.
Tuttavia, l'aritmetica bignum è possibile per vettorizzare.
Disclosure:
Sono l'autore di y-cruncher che fa un sacco di grande numero arihmetic.
In attesa di MULX, ADCX, ADOX in Haswell/Broadwell ... –
Ottima risposta. Immagino di essere un altro dei tanti che hanno provato e fallito. –
Ma non capisco il punto su "Nessun numero intero a 128 bit add/sub". Perché questo è un problema? Anche i registri scalari/generali non hanno hardware per questo. Il modo per farlo è due store hi e low in registri SIMD separati. –