Che cos’è la Branch Prediction

di Lorenzo Neri
0 commento 101 visualizzazioni

In differenti linguaggi di programmazione, se calcolassi il tempo necessario a processare un array ordinato e uno non ordinato, noterai che nel secondo caso ci vorrà più tempo.

A prescindere dalla dimensione dell’array e del suo contenuto, il motivo sta nella “branch prediction”.

Cerchiamo di capire cosa mai vorrà dire questa definizione con meno #tecnichese possibile 🙂

All’interno di un computer abbiamo un circuito digitale che ha il compito di capire quale ramo di un “if”, quindi branch in inglese, deve eseguire prima ancora che si sappia in via definitiva.

Ci arriviamo a lui, a questo famoso circuito!

Ma prima di tutto: perché mai dovrebbe essere necessaria una cosa del genere?

Pensiamo un attimo alla classica struttura di un “if-then-else”: abbiamo due rami con all’interno del codice da eseguire.

Il primo ramo verrà eseguito se la condizione viene verificata, diversamente verrà eseguito il secondo.

E qui, dobbiamo fare un piccolo passo indietro: i salti condizionati.

Erano molto in voga quando si programmava con il famoso codice spaghetti 😀

Per fartela molto breve, i salti condizionati funzionano così: abbiamo un punto del codice in cui scriviamo la nostra condizione, quella dell’if per intenderci.

Se questa viene verificata, il programma “salta” direttamente alla porzione di codice che dev’essere eseguita: in altre parole, quella che viene scritta all’interno dell’if stesso.

Diversamente, se la condizione non viene verificata, il programma NON salta alla porzione di codice dell’if ed esegue subito quella scritta nelle righe successive al salto.

In altre parole funziona come il classico if-then-else ma ribaltato!

Per nostra sfortuna però, il processore non sa immediatamente cosa deve fare: non è così tanto intelligente come può sembrare!

Infatti, deve aspettare che il salto condizionato venga calcolato e quindi interrompe l’esecuzione del programma finché non sa la risposta!

Il processore dice a se stesso: “Bene, aspettiamo che venga calcolata questa condizione del salto, poi provvedo ad eseguire il codice dell’if oppure dell’else”.

Non ci possiamo permettere una tale attesa, immagina a ragionare in questi termini con un array da un milione di celle!

Ed è qui che subentra l’alleato del processore: il branch predictor.

Il branch predictor non è nient’altro che il circuito digitale di cui parlavamo poco fa.

Chi è il Branch Predictor, cosa fa e a cosa serve

Torniamo al problema del processore: vede il branch, ma non sa come gestirlo.

Cosa facciamo? Stoppiamo l’esecuzione ed aspettiamo di essere sicuri che la condizione sia verificata oppure no?

Assolutamente no! Immagina quanto spreco di tempo!

Il branch predictor è un po’ come un mago indovino.

Fa una predizione in questo modo:

“Secondo me questo if è verificato”: il branch predictor azzecca la previsione e si prosegue ad eseguire il codice.

Oppure succede che non ci azzecca, si torna momentaneamente indietro per eseguire l’altro ramo del nostro if-then-else.

È come tirare una moneta: avrò sempre il 50% di probabilità di azzeccarci!

Per nostra fortuna no!

Il branch predictor non è così stupido: gode di buona memoria sulle previsioni che ha fatto in passato, ve lo dicevo che era un mago.

Ogni volta che deve fare una previsione e capire quale ramo eseguire, prima ancora di annunciare la sua “visione”, guarda alla storia passata e si confronta con se stesso.

In questo modo, il branch predictor, almeno in quelli moderni usati oggigiorno, può raggiungere una probabilità di successo maggiore del 90%.

Potrebbero interessarti

Lascia un commento

Questo sito potrebbe fare uso di cookie e siccome l'UE mi obbliga a fartelo presente, eccoti il classico banner dove puoi decidere come gestirli. Accetta Leggi di più