Cosa potrebbe causare un processo deterministico per generare errori in virgola mobile

Question

Avendo già letto questo question Sono ragionevolmente certo che un determinato processo che utilizza aritmetica in virgola mobile con lo stesso input (sullo stesso hardware, compilato con lo stesso compilatore) dovrebbe essere deterministico. Sto guardando un caso in cui ciò non è vero e cerco di determinare cosa potrebbe aver causato questo.

Ho compilato un file eseguibile e gli sto dando gli stessi dati esatti, in esecuzione su una singola macchina (non multithreaded) ma sto ricevendo errori di 3.814697265625e-06 che dopo aver cercato su Google ho trovato è in realtà pari a 1/4^9 = 1/2^18 = 1/262144. che è abbastanza vicino al livello di precisione di un numero in virgola mobile a 32 bit (circa 7 cifre secondo wikipedia)

Il mio sospetto è che abbia qualcosa a che fare con le ottimizzazioni che sono state applicate al codice. Sto usando il compilatore intel C++ e ho trasformato la speculazione in virgola mobile in rapida invece che sicura o severa. Questo potrebbe rendere un processo in virgola mobile non deterministico? Ci sono altre ottimizzazioni ecc. Che potrebbero portare a questo comportamento?

EDIT: Come suggerito da Pax, ho ricompilato il codice con la speculazione in virgola mobile trasformata in sicura e ora sto ottenendo risultati stabili. Questo mi permette di chiarire questa domanda - cosa fa realmente la speculazione in virgola mobile e in che modo ciò può causare lo stesso binario (cioè una compilazione, più esecuzioni) per generare risultati diversi se applicati allo stesso input identico?

@Ben Sto compilando utilizzando Intel (R) C++ 11.0.061 [IA-32] e sono in esecuzione su un processore Intel quadcore.

Answer 1

In quasi tutte le situazioni in cui vi è una modalità veloce e una modalità sicura, troverete un compromesso di qualche tipo. Altrimenti tutto funzionerebbe in modalità di sicurezza rapida :-).

E, se stai ottenendo risultati diversi con lo stesso input, il tuo processo è non deterministico, non importa quanto tu creda che sia (nonostante le prove empiriche).

Direi che la spiegazione è la più probabile. Mettilo in modalità sicura e verifica se il non determinismo scompare. Questo te lo dirà di sicuro.

Se ci sono altre ottimizzazioni, se si sta compilando sullo stesso hardware con lo stesso compilatore/linker e le stesse opzioni a quegli strumenti, dovrebbe generare codice identico. Non riesco a vedere altre possibilità oltre alla modalità veloce (o bit put nella memoria a causa dei raggi cosmici, ma è piuttosto improbabile).

In seguito alla vostra aggiornamento:

Intel ha un documento here che spiega alcune delle cose che non sono autorizzati a fare in modalità provvisoria, inclusi ma non limitati a:

• riassociazione: (a+b)+c -> a+(b+c).
• zero folding: x + 0 -> x, x * 0 -> 0.
• multiplo reciproco: a/b -> a*(1/b).

Mentre si afferma che queste operazioni sono definite in fase di compilazione, i chip Intel sono piuttosto intelligenti.Possono riordinare le istruzioni per mantenere le pipeline piene in configurazioni multi-CPU, quindi, a meno che il codice proibisca specificamente tale comportamento, le cose potrebbero cambiare in fase di esecuzione (non in fase di compilazione) per mantenere le cose a piena velocità.

Questo è coperto (brevemente) a pagina 15 di tale documento collegato che parla di vettorizzazione ("Problema: risultati diversi rieseguendo lo stesso binario sugli stessi dati sullo stesso processore").

Il mio consiglio sarebbe quello di decidere se avete bisogno di grugnito grezzo o riproducibilità totale dei risultati e quindi scegliere la modalità basata su questo.

Answer 2

Se il programma è parallelizzato, come potrebbe essere eseguito su un quad core, allora potrebbe non essere deterministico.

Immaginate di avere 4 processori che aggiungono un valore in virgola mobile alla stessa posizione di memoria. Poi si potrebbe ottenere

(((InitialValue+P1fp)+P2fp)+P3fp)+P4fp 

o

(((InitialValue+P2fp)+P3fp)+P1fp)+P4fp 

o uno qualsiasi degli altri ordinamenti possibili.

Heck, si potrebbe anche ottenere

InitialValue+(P2fp+P3fp)+(P1fp+P4fp) 

se il compilatore è abbastanza buono.

Sfortunatamente, l'aggiunta a virgola mobile non è commutativa o associativa. L'aritmetica del numero reale è, ma il punto in virgola mobile non lo è, a causa dell'arrotondamento, dell'overflow e del underflow.

A causa di ciò, il calcolo FP parallelo è spesso non deterministico. "Spesso", perché i programmi che sembrano

on each processor 
    while(there is work to do) { 
     get work 
     calculate result 
     add to total 
    } 

saranno non-deterministico, in quanto la quantità di tempo che ognuno prende può variare ampiamente - non è possibile prevedere l'ordine delle operazioni. (Peggio ancora se i thread interagiscono.)

Ma non sempre, perché ci sono stili di programmazione parallela che sono deterministici.

Ovviamente, a molte persone che si interessano del determinismo si lavora in un numero intero o in un punto fisso per evitare il problema. Sono particolarmente appassionato di superaccumulatori, numeri 512, 1024 o 2048 bit a cui è possibile aggiungere numeri in virgola mobile, senza subire errori di arrotondamento.

---

Come per un'applicazione a thread singolo: il compilatore può riorganizzare il codice. Compilazioni diverse possono dare risposte diverse. Ma ogni particolare binario dovrebbe essere deterministico.

A meno che ... non stiate lavorando in un linguaggio dinamico. Ciò comporta ottimizzazioni che riordinano i calcoli FP, che variano nel tempo.

O meno che ... davvero a lungo girato: Itanium aveva alcune caratteristiche, come l'ALAT, che rendevano anche non codificato il singolo threaded deterministico. È improbabile che tu possa essere influenzato da questi.