Quando ho avuto un processore Haswell per la prima volta ho provato a implementare FMA per determinare il set Mandelbrot. L'algoritmo principale è questo:Ottimizza per moltiplicazione rapida ma aggiunta lenta: FMA e doppio raddoppia
intn = 0;
for(int32_t i=0; i<maxiter; i++) {
floatn x2 = square(x), y2 = square(y); //square(x) = x*x
floatn r2 = x2 + y2;
booln mask = r2<cut; //booln is in the float domain non integer domain
if(!horizontal_or(mask)) break; //_mm256_testz_pd(mask)
n -= mask
floatn t = x*y; mul2(t); //mul2(t): t*=2
x = x2 - y2 + cx;
y = t + cy;
}
Questo determina se n pixel sono Mandelbrot. Quindi per il doppio punto mobile viene eseguito su 4 pixel (floatn = __m256d, intn = __m256i). Ciò richiede 4 moltiplicazioni in virgola mobile SIMD e quattro aggiunte in virgola mobile SIMD.
Poi ho modificato questo per lavorare con FMA come questo
intn n = 0;
for(int32_t i=0; i<maxiter; i++) {
floatn r2 = mul_add(x,x,y*y);
booln mask = r2<cut;
if(!horizontal_or(mask)) break;
add_mask(n,mask);
floatn t = x*y;
x = mul_sub(x,x, mul_sub(y,y,cx));
y = mul_add(2.0f,t,cy);
}
dove mul_add chiama _mm256_fmad_pd e mul_sub chiamate _mm256_fmsub_pd. Questo metodo utilizza 4 operazioni SIMD FMA e due moltiplicazioni SIMD che sono due operazioni aritmetiche in meno quindi senza FMA. Inoltre, FMA e moltiplicazione possono utilizzare due porte e aggiungere solo una.
Per rendere i miei test meno precisi ho ingrandito una regione che è interamente nel set di Mandelbrot, quindi tutti i valori sono maxiter. In questo caso il metodo che utilizza FMA è circa il 27% più veloce. Questo è sicuramente un miglioramento, ma passare da SSE a AVX ha raddoppiato le mie prestazioni, quindi speravo di ottenere un altro fattore due con FMA.
Ma poi ho trovato this risposta per quanto riguarda FMA in cui si dice
L'aspetto importante della fusa multiply-add l'istruzione è il (quasi) infinita precisione del risultato intermedio. Questo aiuta con le prestazioni, ma non tanto perché due operazioni sono codificate in una singola istruzione - Aiuta con le prestazioni perché la precisione virtualmente infinita del risultato intermedio è talvolta importante e molto costosa da recuperare con la moltiplicazione e l'aggiunta ordinarie quando questo livello di la precisione è davvero ciò che il programmatore sta cercando.
e successivamente riportato un esempio di doppia * doppio per double-double moltiplicazione
high = a * b; /* double-precision approximation of the real product */
low = fma(a, b, -high); /* remainder of the real product */
Da questo, conclusi che ero implementando FMA non ottimale e così decisi di implementare SIMD doppia-doppia. Ho implementato il doppio doppio basato sulla carta Extended-Precision Floating-Point Numbers for GPU Computation. La carta è per il doppio float quindi l'ho modificata per il doppio doppio. Inoltre, invece di impacchettare un valore doppio doppio in un registro SIMD, impongo 4 valori double-double in un registro alto AVX e un registro basso AVX.
Per il set Mandelbrot ciò di cui ho veramente bisogno è la doppia moltiplicazione e l'aggiunta. In questo documento sono le funzioni df64_add e df64_mult. L'immagine seguente mostra l'assieme per la mia funzione df64_mult per software FMA (sinistra) e hardware FMA (destra). Questo dimostra chiaramente che l'hardware FMA è un grande miglioramento per la doppia moltiplicazione.
Così come l'hardware FMA eseguire in doppia-doppia di Mandelbrot set calcolo? La risposta è che è solo circa il 15% più veloce rispetto al software FMA. È molto meno di quanto speravo. Il calcolo doppio-doppio di Mandelbrot richiede 4 aggiunte doppio doppio e quattro moltiplicazioni doppio doppio (x*x, y*y, x*y e 2*(x*y)). Tuttavia, il 2*(x*y) multiplication is trivial for double-double così questa moltiplicazione può essere ignorata nel costo. Pertanto, la ragione per cui ritengo che il miglioramento usando l'hardware FMA sia così piccola è che il calcolo è dominato dalla lenta aggiunta doppia doppia (vedi l'assemblaggio sotto).
Una volta la moltiplicazione era più lenta dell'aggiunta (ei programmatori utilizzavano diversi trucchi per evitare la moltiplicazione) ma con Haswell sembra che sia il contrario. Non solo a causa di FMA ma anche perché la moltiplicazione può utilizzare due porte ma aggiunta solo una.
Così le mie domande (finalmente) sono:
- Come si fa a ottimizzare quando aggiunta è lento rispetto alla moltiplicazione?
- Esiste un modo algebrico per modificare il mio algoritmo per utilizzare più moltiplicazioni e meno aggiunte? So che ci sono metodi per fare il contrario, ad es.
(x+y)*(x+y) - (x*x+y*y) = 2*x*yche utilizzano altre due aggiunte per una moltiplicazione in meno. - C'è un modo per semplicemente la funzione df64_add (ad esempio utilizzando FMA)?
Nel caso in cui qualcuno si chieda, il metodo del doppio doppio è circa dieci volte più lento del doppio. Non è così male, penso che se ci fosse un tipo di hardware di precisione quadrupla probabilmente sarebbe almeno due volte più lento del doppio, quindi il mio metodo software è circa cinque volte più lento di quello che mi aspetterei per l'hardware, se esistesse.
df64_add assemblaggio
vmovapd 8(%rsp), %ymm0
movq %rdi, %rax
vmovapd 72(%rsp), %ymm1
vmovapd 40(%rsp), %ymm3
vaddpd %ymm1, %ymm0, %ymm4
vmovapd 104(%rsp), %ymm5
vsubpd %ymm0, %ymm4, %ymm2
vsubpd %ymm2, %ymm1, %ymm1
vsubpd %ymm2, %ymm4, %ymm2
vsubpd %ymm2, %ymm0, %ymm0
vaddpd %ymm1, %ymm0, %ymm2
vaddpd %ymm5, %ymm3, %ymm1
vsubpd %ymm3, %ymm1, %ymm6
vsubpd %ymm6, %ymm5, %ymm5
vsubpd %ymm6, %ymm1, %ymm6
vaddpd %ymm1, %ymm2, %ymm1
vsubpd %ymm6, %ymm3, %ymm3
vaddpd %ymm1, %ymm4, %ymm2
vaddpd %ymm5, %ymm3, %ymm3
vsubpd %ymm4, %ymm2, %ymm4
vsubpd %ymm4, %ymm1, %ymm1
vaddpd %ymm3, %ymm1, %ymm0
vaddpd %ymm0, %ymm2, %ymm1
vsubpd %ymm2, %ymm1, %ymm2
vmovapd %ymm1, (%rdi)
vsubpd %ymm2, %ymm0, %ymm0
vmovapd %ymm0, 32(%rdi)
vzeroupper
ret
Come Agner Fog rileva in alcune delle sue risorse di ottimizzazione (http://www.agner.org/optimize/ ma non ricordo l'esatto file o pagina), a volte FMA rende le cose più lente.Penso di ricordare che l'esempio era 'x * x + y * y', dove, per alcuni modelli di processori Intel, la latenza, se implementata come mul-fma, rende il timing peggiore di mul-mul-add, che contiene più parallelismo. –
@PascalCuoq, finora ho utilizzato [IACA] (https://stackoverflow.com/questions/26021337/what-is-iaca-and-how-do-i-use-it/26021338#26021338) e quindi guardando i tempi. Per il doppio è stato per lo più un gioco a indovinare poiché ci sono così tante permutazioni con FMA per il set Mandelbrot. Con il doppio doppio è abbastanza chiaro dove usarlo. Ma il problema principale è l'aggiunta con doppio doppio. È così lento rispetto alla moltiplicazione. Cosa si può fare? –
Un'aggiunta doppia doppia programmata correttamente comprende esattamente 20 operazioni di base in virgola mobile. Potresti incontrare versioni che usano meno istruzioni, tuttavia queste perdono la precisione proprio quando ne hai bisogno e la vuoi, che è la sottrazione effettiva di operandi quasi identici in grandezza. L'accelerazione dell'aggiunta doppia doppia richiede miglioramenti HW. Le operazioni di grandezza massima e di magnitudo minima aiutano un po 'e l'aggiunta a tre ingressi con arrotondamento singolo aiuta molto. Alcune architetture di processori offrono il primo, non ne conosco nessuna che offra il secondo, – njuffa