Come funziona la previsione delle branchie, se è ancora necessario verificare le condizioni?

28

Stavo leggendo la risposta popolare su Branch Prediction dal link , e c'è qualcosa che mi confonde:

  • If you guessed right, it continues on.
  • If you guessed wrong, the captain will stop, back up, and yell at you to flip the switch. Then it can restart down the other path.

If you guess right every time, the train will never have to stop.

If you guess wrong too often, the train will spend a lot of time stopping, backing up, and restarting.

Ma questo è quello che non capisco: a sapere se la tua ipotesi è giusta o sbagliata, devi fare una verifica della condizione comunque . Quindi, come funziona anche la previsione dei branch, se in entrambi i casi stai ancora eseguendo lo stesso controllo condizionale?

Quello che sto cercando di dire è che la predizione di ramo non è esattamente la stessa cosa di non avere alcuna previsione di branch perché stai facendo lo stesso controllo condizionale comunque? (ovviamente mi sbaglio, ma non capisco)

    
posta Omega 02.03.2015 - 18:59
fonte

5 risposte

18

Ovviamente la condizione viene controllata ogni volta. Ma quando viene controllato, è molto in alto nella pipeline della CPU. Nel frattempo, anche altre istruzioni sono entrate nella pipeline e sono in varie fasi di esecuzione.

Di solito, una condizione viene immediatamente seguita da un'istruzione di ramo condizionale, che si dirama se la condizione restituisce TRUE o se la condizione viene valutata su FALSE. Ciò significa che ci sono due diversi flussi di istruzioni che possono essere caricati nella pipeline dopo l'istruzione di condizione e l'istruzione di ramo, a seconda che la condizione valuti su VERO o FALSO. Sfortunatamente, subito dopo aver caricato l'istruzione di condizione e l'istruzione di salto, la CPU non sa ancora a quali condizioni valuterà la condizione, ma deve comunque continuare a caricare roba nella pipeline. Quindi seleziona uno dei due gruppi di istruzioni in base a un'ipotesi su quale sarà la condizione a cui valuterà.

Successivamente, mentre l'istruzione sulla condizione si sposta lungo la pipeline, è il momento di essere valutata. A quel tempo, la CPU scopre se la sua ipotesi è giusta o sbagliata.

Se l'ipotesi si rivela corretta, il ramo si è spostato nella posizione corretta e le istruzioni corrette sono state caricate nella pipeline. Se si scopre che l'ipotesi è sbagliata, tutte le istruzioni che sono state caricate nella pipeline dopo l'istruzione del ramo condizionale sono errate, devono essere eliminate e il recupero delle istruzioni deve riprendere dal punto giusto.

Emendamento

In risposta al commento di StarWeaver, per dare un'idea di cosa deve fare la CPU per eseguire una singola istruzione:

Considera qualcosa di semplice come MOV AX,[SI+10] che noi umani pensiamo ingenuamente come "carica AX con la parola a SI più 10". Approssimativamente, la CPU deve:

  1. emette il contenuto del PC (il "registro del contatore del programma") sul bus indirizzo;
  2. legge l'opcode dell'istruzione dal bus dati;
  3. incrementa PC;
  4. decodifica l'opcode per capire cosa fare con esso;
  5. emette il contenuto del PC sul bus indirizzo;
  6. legge l'operando delle istruzioni (in questo caso 10) dal bus dati;
  7. incrementa PC;
  8. alimenta l'operando e SI al sommatore;
  9. emette il risultato dell'adder sul bus indirizzo;
  10. legge AX dal bus dati.

Questo è un enorme 10 passi. Alcuni di questi passaggi saranno ottimizzati anche in CPU non pipeline, ad esempio la CPU incrementerà quasi sempre il PC in parallelo con il prossimo passo, operazione semplice perché il PC è un registro molto, molto speciale che è mai usato per nessun altro lavoro, quindi non c'è possibilità di contesa tra diverse parti della CPU per accedere a questo particolare registro. Tuttavia, ci rimangono 8 passaggi per un'istruzione così semplice, e si noti che sto già assumendo un certo grado di sofisticazione per conto della CPU, ad esempio presumo che non ci sarà bisogno di un intero passo in più per sommatore per eseguire effettivamente l'aggiunta prima che il risultato possa essere letto da esso e presumo che l'output dell'adder possa essere inviato direttamente al bus indirizzo senza dover essere memorizzato in un registro di indirizzamento interno intermedio.

Ora, considera che esistono modi di indirizzamento più complicati, come MOV AX, [DX+SI*4+10] , e anche istruzioni molto più complicate, come MUL AX, operand che effettivamente eseguono loop all'interno della CPU per calcolare il loro risultato.

Quindi, il mio punto qui è che la metafora del "livello atomico" è lungi dall'essere adatta al livello di istruzione della CPU. Potrebbe essere adatto per il livello di passaggio della pipeline, se non si vuole andare troppo in basso fino al livello effettivo della porta logica.

    
risposta data 02.03.2015 - 20:47
fonte
25

Pensa ad un viaggio senza GPS. Arrivi a un incrocio e pensi di dover girare, ma non ne sei completamente sicuro. Quindi fai il giro, ma chiedi al tuo passeggero di controllare la mappa. Forse sei a tre miglia lungo la strada quando finisci di discutere di dove sei. Se avessi ragione, sei a tre miglia più lontano di quanto saresti stato se ti fossi fermato e litigato prima di voltarti. Se ti sbagliavi, devi girarti.

Le pipeline della CPU funzionano allo stesso modo. Nel momento in cui possono verificare le condizioni, sono già in un certo senso in fondo alla strada. La differenza è che non devono guidare le tre miglia indietro, perdono solo la partenza iniziale. Ciò significa che non c'è nulla di male nel provare.

    
risposta data 02.03.2015 - 21:25
fonte
2

Da quanto ho capito, la previsione delle diramazioni è molto utile quando la condizione che devi controllare richiede il risultato di qualcosa che è costoso o ancora in corso, e altrimenti cambierai i pollici aspettando che il valore valuti la condizione.

Con operazioni come l'esecuzione fuori sequenza, è possibile utilizzare la previsione filiale per iniziare a riempire i punti vuoti nella pipeline che altrimenti non sarebbe possibile utilizzare. In una situazione in cui non ci sono, per qualche motivo, cicli di inattività nella pipeline, quindi sì, non c'è un guadagno nella previsione dei rami.

Ma la chiave qui è che la CPU sta iniziando il lavoro per uno dei rami previsti perché non può valutare ancora la condizione stessa.

    
risposta data 02.03.2015 - 20:57
fonte
1

Forma abbreviata:

Alcune CPU possono iniziare a lavorare su una nuova istruzione prima di terminare quella vecchia. Queste sono le CPU che usano la previsione del ramo.

Un esempio di pseudocodice:

int globalVariable;
int Read(int* readThis, int* readThat)
{
    if ((globalVariable*globalVariable % 17) < 5)
       return *readThis;
    else
       return *readThat;
}

Il codice precedente controlla una condizione e in base all'esito è necessario restituire il valore memorizzato nella posizione di memoria addThis o il valore memorizzato in readThat . Se la previsione del ramo prevede che la condizione sia true , la CPU leggerà il valore memorizzato nella posizione di memoria addThis mentre esegue il calcolo necessario per valutare l'istruzione if . Questo è un esempio semplificato.

    
risposta data 04.03.2015 - 10:40
fonte
1

Sì, la condizione è verificata in entrambi i modi. Ma il vantaggio della previsione delle filiali è che puoi lavorare anziché attendere il risultato del controllo delle condizioni.

Diciamo che devi scrivere un tema e può riguardare l'argomento A o l'argomento B. Sai dai saggi precedenti che il tuo insegnante ama l'argomento A meglio di B e lo sceglie più spesso. Invece di aspettare la sua decisione, puoi iniziare a scrivere il tema sul primo argomento. Ora ci sono due possibili risultati:

  1. Hai iniziato il tuo saggio sull'argomento sbagliato e devi lasciare ciò che hai scritto finora. Devi iniziare a scrivere sull'altro argomento ed è lo stesso sforzo di tempo che avevi aspettato.
  2. Hai indovinato e hai già lavorato.

Le CPU moderne sono al minimo la maggior parte del tempo perché sono in attesa di risposte IO o del risultato di altri calcoli. Questa volta può essere usato per fare del lavoro futuro.

Anche se devi respingere ciò che stai facendo in questo tempo di inattività, è più probabile che sia più efficace se hai la possibilità di indovinare quale percorso sceglierà il programma. E le moderne CPU hanno questa capacità.

    
risposta data 04.03.2015 - 12:00
fonte

Leggi altre domande sui tag