Cosa ogni programmatore dovrebbe sapere sul funzionamento delle moderne CPU

Comprendere il funzionamento interno delle CPU moderne è un argomento affascinante e di fondamentale importanza per i programmatori che mirano a scrivere codice efficiente. In un suo recente intervento, uno sviluppatore di gran fama come Matt Godbolt, noto per aver sviluppato Compiler Explorer, eccellente strumento per verificare l’output di diversi compilatori, ha offerto una dettagliata analisi esplorando buona parte delle architetture CPU contemporanee, in particolare quelle prodotte negli ultimi 15 anni.

La pipeline della CPU: un modello semplificato

Una CPU moderna può essere concettualmente vista come una pipeline, una sorta di catena di montaggio in cui le istruzioni entrano da un’estremità e progrediscono attraverso diverse fasi, ognuna delle quali esegue un compito specifico su ciascuna istruzione.

Come osserva Godbolt, il modello accademico classico (fetch, decode, execute, retire) non descrive più completamente la realtà, poiché le architetture moderne sono molto più sofisticate. Il funzionamento di un processore odierno si discosta quindi dal modello storicamente noto.

Le CPU attuali presentano tipicamente una parte front-end che opera “in-order” (in ordine) e una parte back-end che opera “out-of-order” (fuori ordine).

Front-end

Il front-end processa le istruzioni una dopo l’altra nell’ordine in cui sono state scritte nel codice sorgente. Le fasi iniziali includono il fetching dei byte delle istruzioni dalla memoria attraverso le cache e la decodifica di questi byte nelle istruzioni effettive.

La decodifica è particolarmente complessa per architetture come x86, in cui la lunghezza delle istruzioni può variare significativamente (da 1 a 15 byte), rispetto ad architetture come ARM con lunghezze fisse (2 o 4 byte).

Un processo chiave che avviene nel front-end è il register renaming: lo spazio disponibile internamente nel chip è utilizzato per memorizzare risultati intermedi, creando di fatto centinaia di registri temporanei virtuali per evitare dipendenze dai pochi registri architetturali visibili al programmatore e permettere l’esecuzione parallela di operazioni che altrimenti userebbero lo stesso registro.

Back-end

Il back-end, come evidenziato in precedenza, è la parte “out-of-order“. Qui, la CPU esegue un tracciamento delle dipendenze tra le varie istruzioni.

Le istruzioni sono eseguite in un ordine che soddisfa le loro dipendenze e che non corrisponde necessariamente con l’ordine in cui sono state fornite. Lo scopo principale dell’esecuzione fuori ordine è sfruttare il tempo in cui alcune istruzioni sono bloccate, ad esempio in attesa di accessi alla memoria o del completamento di operazioni complesse come moltiplicazioni o divisioni.

Trovando altro lavoro da eseguire mentre attende la conclusione delle altre operazioni in essere, la CPU può aumentare il lavoro concluso per unità di tempo.

Le unità di esecuzione (execution units) sono molteplici (moltiplicatori, addizionatori, unità floating-point,…), consentendo l’esecuzione parallela di diverse operazioni purché non dipendano l’una dall’altra o non utilizzino le stesse risorse hardware contemporaneamente.

Un singolo core può eseguire tra cinque e otto istruzioni per ciclo di clock nell’unità di esecuzione. Questo parallelismo a livello di istruzione è una delle ragioni per cui le performance single-core sono aumentate negli anni recenti, nonostante l’incremento della frequenza di clock si sia stabilizzato.

Retirement

Infine, c’è lo stadio di retirement (ritiro), che avviene nuovamente in-order. Indipendentemente dall’ordine in cui le istruzioni sono state eseguite, esse sono ritirate esattamente nella sequenza del programma originale.

Questo approccio garantisce che gli effetti visibili esternamente (cambiamenti nello stato del programma, scritture in memoria, eccezioni) appaiano come se il programma fosse stato eseguito in-order.

Predizione di salto (Branch Prediction)

La pipeline della CPU è lunga, con decine di cicli che trascorrono tra il fetching di un’istruzione e la sua disponibilità per l’esecuzione.

Le istruzioni di salto (branch), che alterano il flusso sequenziale del programma (come gli if, for, while), rappresentano una sfida. Se la CPU processa le istruzioni linearmente e incontra un salto condizionale, non sa immediatamente quale percorso prendere.

Nelle CPU più vecchie, ciò causava una “bolla” nella pipeline: il lavoro speculativo (le istruzioni processate nel caso in cui il salto seguito non fosse questo giusto…) era scartato e la pipeline doveva essere riempita nuovamente dall’indirizzo di destinazione corretto. Con pipeline lunghe (12 cicli o più), questo costo diventa proibitivo.

Per mitigare questo problema, le CPU moderne utilizzano un predittore di salto (branch predictor). Questo sistema tenta di indovinare dove il flusso del programma si dirigerà prima ancora che l’istruzione di salto venga eseguita. In questo modo è possibile iniziare a riempire la pipeline con le istruzioni del percorso predetto, riducendo la probabilità di dover scartare lavoro.

Il predittore di salto utilizza una lookup table, spesso chiamata Branch Target Buffer (BTB). Quando il sistema di esecuzione completa un salto, informa il predittore dell’indirizzo del salto e della sua destinazione. Il predittore registra questa informazione, in modo che la prossima volta che incontra lo stesso indirizzo, può predire la destinazione.

Per i salti condizionali (es. un if), il predittore non solo deve indovinare la destinazione ma anche se il salto è verosimilmente corretto in una specifica esecuzione. Le tecniche esatte sono segreti industriali, ma si basano ampiamente sull’indirizzo dell’istruzione di salto e sulla storia recente dei salti (sia locali per il singolo salto che globali).

Il meccanismo funziona piuttosto bene, anche se esistono tecniche più sofisticate e a più livelli. Quando la predizione è corretta, il lavoro speculativo sulla pipeline è valido e può essere ritirato normalmente. Quando la predizione è errata (misprediction), il lavoro speculativo deve essere scartato nello stadio di retirement. Un elevato tasso di misprediction può quindi causare un significativo calo di performance.

L’impatto della predizione di salto: esempi pratici

Godbolt ha presentato alcuni esempi citando, per semplificare, codice Python. Nello specifico, ha mostrato un semplice esempio in Python che somma i numeri di una lista e, separatamente, somma solo quelli minori di 128.

Quando i numeri della lista erano casuali (non ordinati), l’if era imprevedibile. Era circa altrettanto probabile che fosse vero o falso ad ogni passo, quindi il sistema di predizione di salto indovinava male circa la metà delle volte. Ciò portava a molte previsioni sbagliate e rallentava l’esecuzione.

Quando i numeri erano ordinati, per la prima metà della lista l’if era sempre vero (i numeri erano tutti < 128), e per la seconda metà era sempre falso (i numeri erano tutti >= 128). Questa regolarità rende il salto molto prevedibile per la CPU.

Anche se abbiamo a che fare con codice Python (che ha complessità aggiuntive), la differenza era misurabile: il codice con dati ordinati era più veloce perché la predizione di salto funzionava molto meglio.

Gli strumenti di analisi hanno mostrato che, con dati casuali, c’erano molte più “mispredictions” (previsioni sbagliate) rispetto al caso con dati ordinati.

Esempio in C++ con dati casuali vs. dati ordinati

Godbolt ha poi preso in esame, nella sua trattazione, lo stesso tipo di codice usando il linguaggio C++. Contrariamente a quanto ci si potrebbe aspettare, la versione con dati casuali e quella con dati ordinati avevano prestazioni molto simili.

Perché? Non perché la predizione di salto sia meno importante in C++, ma perché il compilatore (il programma che trasforma il codice C++ in istruzioni comprensibili e direttamente gestibili dalla CPU) ha osservato un comportamento intelligente.

Invece di generare un vero e proprio “salto” condizionale per l’if, il compilatore ha usato una tecnica chiamata “conditional move” (CMOV). In pratica, ha calcolato entrambi i possibili risultati (sommare il numero o meno) in ogni caso, e poi ha usato un’istruzione speciale della CPU che sposta un valore in una certa posizione solo se una certa condizione è vera.

L’utilizzo di conditional move (CMOV)

L’istruzione di “conditional move” presentata al precedente paragrafo non è un salto. Non c’è nulla da predire, quindi, per quella specifica operazione. Il codice risultante aveva un solo salto (quello della fine del ciclo for), che è altamente prevedibile durante il funzionamento del programma sulla CPU.

La morale è che il compilatore a volte può aggirare i problemi di predizione di salto trasformando il codice. Tuttavia, non può farlo sempre, specialmente se ci sono “side effects” (azioni collaterali come stampare qualcosa sullo schermo) all’interno dell’if.

In generale, la predizione di salto è un meccanismo cruciale per le CPU moderne. Quando i salti sono imprevedibili (come con dati casuali o logica complessa e irregolare), la CPU subisce un costo significativo a causa delle previsioni sbagliate, che può rallentare notevolmente il programma. A volte, i compilatori moderni possono mitigare questo problema con ottimizzazioni come le “conditional moves“.

Operazioni costose per la CPU: l’esempio delle divisioni

Come abbiamo spesso ricordato in altri nostri articoli (si pensi alla sfida, apparentemente semplice, legata all’ottimizzazione del calcolo anno bisestile), alcune operazioni aritmetiche sono intrinsecamente più lente di altre a livello di CPU. Le divisioni, in particolare, sono notoriamente lente.

A differenza delle moltiplicazioni o delle addizioni, che possono spesso essere gestite in pipeline (si può iniziare una nuova operazione ogni ciclo di clock anche se l’operazione stessa richiede più cicli per essere portata a conclusione), le divisioni spesso non sono assoggettabili al medesimo approccio. In altre parole, è possibile iniziare una nuova divisione solo dopo che la precedente è completamente terminata.

Le divisioni su numeri a 64 bit potevano richiedere tra 80 e 100 cicli di clock nelle architetture meno recenti (anche se le CPU Intel più recenti le hanno ridotte a decine di cicli).

Ciò può avere un impatto significativo sulle performance, come dimostrato in un esempio citato da Godbolt.

llvm-mca (Machine Code Analyzer)

Utilizzando uno strumento come llvm-mca, che simula l’esecuzione di un blocco di codice sulla pipeline della CPU basandosi sulla conoscenza che il compilatore ha dell’hardware, è possibile visualizzare l’impatto di ciascuna operazione.

Nella sua dimostrazione, Godbolt mostra le evidenti differenze in termini prestazionali tra un approccio non ottimale che introduce lunghe pause dovute all’istruzione di divisione (div), con il ciclo loop che richiede un numero elevato di cicli per iterazione (nell’esempio circa 150).

Un modo per evitare una divisione (o modulo) è quando il divisore è una potenza di due, spiega Godbolt. L’operazione val % size (restituisce il resto della divisione intera tra val e size) può essere sostituita con val & (size - 1) (chiamata operazione bitwise AND). Analizzando il codice con llvm-mca, la simulazione mostra un drastico miglioramento nei cicli necessari (da 148 a 33 nell’esempio) e una timeline molto più “sana” senza i lunghi blocchi causati dalla divisione.

Memoria e cache: i colli di bottiglia nascosti

La memoria principale (DRAM) è significativamente più lenta rispetto alla CPU. L’accesso alla memoria principale può richiedere tra 80 e 100 nanosecondi. Per mitigare questa latenza, le CPU utilizzano una gerarchia di cache più veloci e più piccole più vicine al core.

La cache L1 è la più veloce e piccola (es. 32KB), con latenza di circa 1 nanosecondo. La L2 è più grande (es. 256KB) e leggermente più lenta, con latenza maggiore della L1. Infine, La cache L3, condivisa tra i core, è ancora più grande e più lenta dell’L2.

L’efficienza del codice dipende in gran parte da quanto bene sfrutta questa gerarchia di cache, minimizzando gli accessi alla memoria principale.

Un esempio classico per dimostrare l’impatto della memoria è l’attraversamento di una lista concatenata. Seguire i puntatori di una lista concatenata richiede di leggere il puntatore dalla memoria per conoscere l’indirizzo dell’elemento successivo. Se gli elementi della lista sono sparsi casualmente nella memoria, ogni accesso a un nuovo elemento rischia di essere un cache miss, richiedendo di caricare una nuova linea di cache dalla memoria più lenta (fino alla DRAM).

Se confrontiamo l’attraversamento di una lista concatenata con l’attraversamento di un array, anche se i dati occupano lo stesso spazio in memoria e sono letti sequenzialmente, l’array è molto più veloce. Questo perché gli accessi agli elementi consecutivi di un array sono assolutamente prevedibili.

Le cache (L1, L2, L3) hanno dei prefetcher integrati che rilevano pattern di accessi detti strided, ad esempio quando in memoria gli indirizzi degli elementi successivi sono separati da un intervallo o “passo” fisso e regolare (come appunto avviene nel caso di un array).

Quando gli elementi della lista concatenata sono allocati in modo casuale in memoria, i prefetcher delle cache non possono prevedere la posizione dell’elemento seguente. Ogni accesso è quindi soggetto alla latenza completa del sistema di memoria.

Nel test mostrato da Godbolt, attraversare un array di 10 milioni di elementi richiede 11 ms, una lista concatenata allocata sequenzialmente (che beneficia del prefetching) richiede 24 ms (solo 2,12 volte più lenta), mentre una lista concatenata con puntatori randomizzati richiede 1,3 secondi, quasi 120 volte più lenta dell’array.

Strumenti per l’analisi delle performance

Per capire dove si annidano i colli di bottiglia a livello di codice, sono necessari strumenti specifici che sfruttano i contatori hardware integrati nelle CPU. Godbolt cita i seguenti software:

• perf (Linux): Un potente strumento da riga di comando che permette di configurare contatori hardware per misurare eventi specifici (i.e. branch encounter, branch misses). Può anche eseguire analisi più avanzate.
• vtune (Intel): Uno strumento con interfaccia grafica per Windows e Linux, che offre funzionalità simili a perf.
• llvm-mca: Come visto in precedenza, è un software utile per analizzare il comportamento di piccoli blocchi di codice sull’unità di esecuzione, simulando la pipeline.

Un approccio all’analisi delle performance reso possibile da strumenti come perf e similari è la cosiddetta Top-Down Analysis. L’approccio classifica le cause dei colli di bottiglia in alcune categorie principali:

• Retiring: Le istruzioni sono completate ed elaborate rapidamente (la CPU sta facendo il massimo lavoro utile). Se si parla di “retiring bound“, l’unico modo per andare più veloce è avere meno istruzioni da elaborare.
• Bad Speculation: La CPU spende tempo eseguendo lavoro speculativo che viene poi scartato (spesso a causa di branch misprediction).
• Front-end Bound: Il collo di bottiglia è nel front-end della pipeline (fetching e decoding delle istruzioni).
• Back-end Bound: Il collo di bottiglia è nel back-end (esecuzione, spesso in attesa di dati dalla memoria o completamento di operazioni lunghe).

Conclusioni

Le CPU moderne sono sistemi estremamente complessi, che utilizzano tecniche avanzate come pipeline, esecuzione fuori ordine, branch prediction sofisticata e gerarchie di cache multilivello per raggiungere prestazioni elevate.

Aspetti come la prevedibilità dei salti e i pattern di accesso alla memoria hanno un impatto profondo e misurabile sulla velocità di esecuzione, anche a livello di microarchitettura.

Fortunatamente, come ha sapientemente dimostrato Godbolt, i compilatori moderni sono molto “intelligenti” e sanno sfruttare gran parte di queste caratteristiche hardware, applicando ottimizzazioni (come la conversione di condizionali in CMOV o la sostituzione di divisioni per costanti con moltiplicazioni/shift) che spesso sollevano gli sviluppatori dalla necessità di pensare a questi dettagli a basso livello.

Tuttavia, quando si incontrano problemi di performance in codice critico, comprendere i principi di funzionamento della CPU e utilizzare strumenti di analisi (come perf, vtune, llvm-mca) diventa indispensabile per identificare i veri colli di bottiglia e apportare modifiche mirate al codice.

Va detto che la trattazione di Godbolt, che abbiamo voluto notevolmente semplificare, tocca solo la punta dell’iceberg focalizzandosi principalmente sul comportamento di un singolo core.