fma(a,b,c) equivale a a*b+c tranne che non arrotonda il risultato intermedio.Quali algoritmi traggono maggiormente vantaggio dall'aggiunta moltiplicata fusa?
Potresti fornirmi alcuni esempi di algoritmi che non tragicamente traggono vantaggio dall'evitare questo arrotondamento?
Non è ovvio, poiché l'arrotondamento dopo le moltiplicazioni che evitiamo tende ad essere meno problematico dell'arrotondamento dopo l'aggiunta che non è così.
taw colpito su un esempio importante; più in generale, FMA consente agli scrittori di librerie di implementare in modo efficiente molte altre operazioni in virgola mobile con arrotondamenti corretti.
Ad esempio, una piattaforma che dispone di un FMA può utilizzarlo per implementare correttamente diviso arrotondato e radice quadrata (PPC e Itanium ha preso questo approccio), che consente l'FPU essere fondamentalmente una macchina FMA single-purpose. Peter Tang e John Harrison (Intel) e Peter Markstein (HP) hanno alcuni documenti che spiegano questo uso se siete curiosi.
L'esempio taw fornito è più ampiamente utile del solo rilevamento dei limiti di errore. Permette di rappresentare il prodotto di due numeri in virgola mobile come somma di due numeri in virgola mobile senza alcun errore di arrotondamento; questo è abbastanza utile nell'implementazione delle funzioni di libreria a virgola mobile correttamente arrotondate. Il libro di Jean-Michel Muller oi documenti su crlibm sarebbero dei buoni punti di partenza per saperne di più su questi usi.
FMA è anche ampiamente utile nella riduzione degli argomenti nelle routine di stile della libreria matematica per determinati tipi di argomenti; quando si fa la riduzione dell'argomento, l'obiettivo del calcolo è spesso un termine del modulo (x - a*b), dove (a*b) è quasi uguale a x stesso; in particolare, il risultato è spesso nell'ordine dell'errore di arrotondamento nel termine (a*b), se questo è calcolato senza un FMA. Credo che anche Muller ne abbia scritto qualcosa nel suo libro.
Fuori della parte superiore della mia testa - La moltiplicazione di matrici, la regola di Newton, la valutazione polinomiale, metodi numerici
Il vantaggio principale di FMA è che può essere due volte più veloce. Piuttosto che prendere 1 ciclo per il multiplo e poi 1 ciclo per l'add, la FPU può emettere entrambe le operazioni nello stesso ciclo. Ovviamente, la maggior parte degli algoritmi trarrà vantaggio da operazioni più veloci.
Alcuni esempi: prodotti punto vettoriale. Trasformate di Fourier. Elaborazione del segnale digitale. Polinomi. Ogni sorta di cose.
È una questione di ottimizzazione e sfruttamento dell'hardware più che altro. Una somma di prodotti è un requisito molto comune nei metodi numerici, e in questo modo ti permette di dare un'istruzione esplicita al compilatore su come fare una cosa veloce e magari con un po 'più di precisione. A meno che non mi sbagli, il compilatore è libero di sostituire a = b * c + d con un'istruzione FMA, ma è anche libero di non farlo. (a meno che lo standard non chieda l'arrotondamento, ma i compilatori del mondo reale violano regolarmente gli standard in piccoli modi).
Il compilatore non può legalmente sostituire b * c + d con una FMA, a meno che tu non specifichi espressamente al compilatore che è OK (con -ffast-math o qualcosa di simile), perché perturba i risultati. –
@StephenLin: Supponendo che la valutazione di 'b',' c' e 'd' non muta lo stato o abbia altri effetti collaterali, in che modo una tale ottimizzazione dell'ottimizzazione" perturba i risultati "? – stakx
@stakx: molte delle istruzioni composite in un set di istruzioni a virgola mobile esistono perché l'errore di arrotondamento potrebbe sommergere il risultato. Esempio: se prendi e^(vicino allo zero) il risultato è vicino a uno, ma ciò limita notevolmente la tua precisione. Se hai un'istruzione che rappresenta e^epsilon-1, allora l'hardware può dare una precisione molto maggiore. Qualsiasi specifico linguaggio di alto livello può essere definito in modo da offrire l'accesso alle istruzioni più precise o riscrivere l'albero delle espressioni in circostanze riconoscibili. Il primo è più prevedibile. – Ian
L'unica cosa che ho trovato finora sono "trasformazioni senza errori". Per eventuali errori di numeri in virgola mobile da a+b, a-b e a*b sono anche numeri a virgola mobile (in modalità round to nearest, supponendo overflow/underflow ecc. Ecc.).
L'errore di aggiunta (e ovviamente sottrazione) è facile da calcolare; se abs(a) >= abs(b), l'errore è esattamente b-((a+b)-a) (2 flop o 4-5 se non sappiamo quale è più grande). L'errore di moltiplicazione è banale da calcolare con fma - è semplicemente fma(a,b,-a*b). Senza fma ci sono 16 flop di codice piuttosto antipatico. E l'emulazione completamente generica di arrotondata correttamente fma è ancora più lenta di quella.
Extra 16 flop di tracciamento degli errori per flop di calcolo reale è un enorme overkill, ma con solo 1-5 flop compatibili con la pipeline è abbastanza ragionevole, e per molti algoritmi basati su quel 50% -200% di overhead del tracking degli errori e la compensazione produce un errore piccolo come se tutti i calcoli fossero fatti in due volte il numero di bit che erano, evitando in molti casi maltrattamenti.
È interessante notare che, fma non è mai usato in questi algoritmi per calcolare i risultati, solo per trovare gli errori, perché trovare l'errore di fma è un lento come trovare errori di moltiplicazione è stato senza fma.
Le parole chiave pertinenti da cercare sarebbero "schema Horner compensato" e "prodotto punto compensato", con lo schema Horner che beneficia molto di più.
Mi chiedo come il costo dell'hardware di FMA sui valori "float" possa essere confrontato con il costo hardware di un'operazione che ha aggiunto il prodotto a precisione completa di due valori "float" a un 'double'. A mio modo di vedere, l'hardware di costo di un multiplo 'double' è più di quattro volte quello di un' float' ugualmente veloce che produce un risultato a precisione piena, e per molte operazioni come dot-product è necessario mantenere i valori intermedi con più precisione rispetto agli operandi o al risultato finale. L'uso di un multiplo e di una fma potrebbe funzionare, ma l'uso di un'operazione f * f + d sembrerebbe due volte più veloce. – supercat
E 'stato abbastanza ben spiegato sul Wikipedia entry for FMA che gli algoritmi che hanno a che fare con accumulo di prodotti di beneficio più usare i FMA:
A fast FMA can speed up and improve the accuracy of
many computations that involve the accumulation of products:
* Dot product
* Matrix multiplication
* Polynomial evaluation (e.g., with Horner's rule)
* Newton's method for evaluating functions.
domanda riguarda l'impatto di arrotondamento, non si tratta di questo. La tua risposta è anche errata in quanto fma richiede 3 unità in virgola mobile in ingresso invece di 2 ingressi standard, porta aggiuntiva in file di registro in virgola mobile e generatori in virgola mobile più larghi Questo non è gratuito, è un compromesso tra supporto fma al costo di alcuni altro hardware. – taw
taw: hai chiesto quali algoritmi traggono vantaggio da FMA e per alcuni esempi in cui l'arrotondamento è un vantaggio non banale. Ho risposto alla prima parte, il che è il vantaggio della maggior parte degli algoritmi. – Gabe