Dipendenza dai dati
Da Wikipedia, l'enciclopedia libera.
La dipendenza dai dati in informatica è una situazione che si verifica quando un'istruzione richiede per essere eseguita dei risultati di operazioni che non sono ancora terminate. Queste situazioni sono indicate anche come data hazard e ignorare questi problemi può portare a condizioni di errore nell'esecuzione dei dati. La teoria che analizza e risolve questi problemi è chiamata analisi delle dipendenze.
Indice |
[modifica] Esempio di dipendenze dei dati
Vi sono tre tipi di data hazard o di dipendenze dai dati
- RAW - Read After Write
- WAR - Write After Read
- WAW - Write After Write
Alcune di queste dipendenze possono sembrare strane ma si deve ricordare che i processori moderni implementano quasi sempre l'esecuzione fuori ordine delle istruzioni e quindi non è detto che l'ordine delle istruzioni deciso dal programmatore venga rispettato.
[modifica] RAW - Read After Write
La dipendenza RAW si riferisce al caso in cui un'istruzione richieda un dato non ancora calcolato. Per esempio:
i1. R2 <- R1 + R3
i2. R4 <- R2 + R3
La prima istruzione calcola la somma di R1 ed R3 e pone il risultato in R2. la seconda istruzione invece calcola la somma di R2 e R3 e pone il sisultato in R4, ma ovviamente non può eseguire la somma fino a quando la prima istruzione non è completa. Quindi si ha una dipendenza dai dati. Un'eventuale esecuzione fuori ordine non è possibile.
[modifica] WAR - Write After Read
La dipendenza WAR si verifica allorquando un'istruzione legge un dato che si trova in una locazione in cui un'istruzione successiva sta per salvare un altro dato. Per esempio:
i1. r1 <- r2 + r3
i2. r3 <- r4 x r5
La prima istruzione somma R2 a R3 e pone il risultato in R1, mentre la seconda istruzione moltiplica R4 con R5 e pone il risultato in R3. Per ottenere l'esecuzione corretta del programma bisogna garantire che la prima istruzione legga il valore da R3 prima che la seconda istruzione aggiorni il valore in R3.
[modifica] WAW - Write After Write
La dipendenza WAW si riferisce al caso in cui più istruzioni utilizzino simultaneamente gli stessi registri. Per esempio:
i1. r2 <- r1 + r3
i2. r2 <- r4 x r7
Entrambi le istruzioni vogliono salvare il loro risultato nel registro R2 e quindi bisogna garantire che la prima istruzioni salvi il risultato prima della seconda.
Nota: il risultato della prima istruzione viene cancellato dalla seconda istruzione. Se le due istruzioni sono consecutive, la prima istruzione è totalmente inutile. Anche se potrebbe nascondere un errore di programmazione, l'operazione non causa errori.
[modifica] Soluzioni
La soluzione di queste dipendenze può essere demandato al compilatore che può inserire un numero adeguato di istruzioni NOP per risolvere le dipendenze. I processori moderni comunque implementano al loro interno delle unità specializzate che riordinano lo istruzioni in modo da eliminare le dipendenze. Alcune dipendenze vengono risolte tramite la rinominazione dei registri e altre tecniche.
Le dipendenze vengono risolte anche tramite degli algoritmi implementati nei processori come lo scoreboarding e l'algoritmo di Tomasulo.
