ARCHITETTURE PARALLELE DELLA CPU

Architetture parallele delle CPU L’obiettivo comune dei progettisti è quello di migliorare l’efficienza della funzionalità del computer e in particolare della CPU. Il miglioramento dell’efficienza segue due strade: • l’eliminazione dei colli di bottiglia; • l’Instruction Level Parallelism (ILP). Per eliminare i colli di bottiglia, sono state introdotte le cache di primo livello, solitamente interne al microprocessore, e le cache di secondo livello, poste tra il microprocessore e il banco di memoria.

L’ILP consiste nell’aggiungere ulteriori risorse hardware all’interno della CPU allo seguire simultaneamente più istruzioni. Le risorse hardware possono essere registri e unità funzionali (ALU, shifter, floating point unit). Un esempio classico di ILP è la tecnica del pipelining mediante aggiunta di registri e hardware di controllo. La tecnica del parallelismo ha portato a implementare le architetture pipelined, superscalari e vettoriali. Architettura pipelined In un microprocessore con architettura pipeline a ogni ciclo di clock viene eseguita una istruzione (CPI = 1), se non si verificano stalli e conflitti. Nelle CPU tradizionali le istruzioni vengono eseguite in maniera sequenziale, come indicato nella figura a lato. Nei microprocessori senza pipeline ogni istruzione si compone di due fasi: fetch ed execute. Nei microprocessore con pipeline ogni istruzione è suddivisa in quattro fasi: • fetch, prelievo; • decode, decodifica; • operate, elaborazione; • write, scrittura risultati.

La struttura a pipeline, utilizzata abbondantemente nei processori RISC, ha come modello la catena di montaggio: durante l’esecuzione di un’istruzione è possibile prepararsi a prelevare l’istruzione successiva. L’idea del pipelinig consiste nell’inserire tra le unità che svolgono le operazioni di fetch e di execute un buffer di memoria, come indicato in figura (a) a lato. Il buffer, che consente alle due unità di comunicare tra loro costituisce l’elemento di pipelining. Le caratteristiche di tale struttura sono le seguenti: • ogni istruzione è eseguita in un ciclo completo di clock, come nelle CPU tradizionali; • aumenta notevolmente il throughput, ovvero il numero di istruzioni al secondo. Dalla figura (b) si nota che durante la fase di execute della prima istruzione si esegue la fase di fetch della seconda istruzione. Tuttavia la struttura pipelined presenta alcuni problemi: • tutti gli stadi devono funzionare in sincronismo, quindi la frequenza del clock deve essere dimensionata sullo stadio più lento; • se il dato da prelevare è nella cache, la latenza è estremamente bassa, ma se il dato deve essere prelevato dalla memoria, perché è qui residente o per problemi di cache miss, sono necessari vari cicli di clock per eseguire l’operazione.

Uno dei metodi per aumentare il livello di parallelismo è quello di aumentare la profondità della pipeline con un conseguente aumento del throughput. Il throughput è la frequenza massima con cui le istruzioni escono dalla pipeline. Tuttavia un elevato livello di parallelismo comporta due problemi: • presenza di hazard (alee) nella pipeline a causa del read-before-write, ovvero la necessità per una istruzione di attendere il risultato di un’altra istruzione a livello superiore; tale problema porta a uno stallo della pipeline; • effetto negativo sul funzionamento della pipeline per la presenza di salti nel programma. Nei microprocessori attualmente in commercio la profondità si aggira tra i 10 e i 15 buffer.

Facendo riferimento ala soprastante figura, il primo stadio preleva l’istruzione, il secondo decodifica e preleva gli operandi, il terzo esegue l’operazione e il quarto scrive i risultati. Con questo tipo di struttura ogni stadio compie operazioni più elementari consentendo di aumentare la frequenza del clock. Con quattro stadi, come nelle fgure (a) e (b) aumenta la latenza ma aumenta anche il throughput. Le prestazioni della pipeline dipendono fortemente dalla presenza degli hazard. Si verifica un hazard quando uno stadio non può eseguire un’istruzione in quel dato ciclo di clock. Gli hazard possono essere di tre tipi: • strutturali; • di dato; • di controllo Gli hazard mandano in stallo la pipeline. Più elevata è la frequenza degli hazard peggiore sarà la prestazione della pipeline. Compito del progettista è quello di ridurre al minimo le probabilità di hazard. Un hazard è strutturale quando due stadi devono condividere la stessa risorsa hardware, ad esempio devono accedere entrambi alla ALU. Un altro problema che si presenta frequentemente nella pipeline è il data dependency (hazard di dato). Per esempio, se l’istruzione I2 utilizza un risultato dell’istruzione I1, in questo caso il compilatore, che deve essere in grado di riconoscere il problema di data dependency, per evitare lo stallo, introduce cicli di NOP tra le due istruzioni. Un metodo per eliminare il data dependency è l’uso dei registri virtuali. Nei registri della pipeline, i posti riservati per memorizzare gli operandi delle istruzioni possono essere visti come registri virtuali che possono essere raggiunti direttamente. Quando un’istruzione sta aspettando i dati di una istruzione non ancora eseguita, effettua la lettura nel registro virtuale evitando l’operazione più lunga di lettura in memoria. Quando l’istruzione, che deve generare il risultato atteso anche dall’istruzione in parallelo, ha terminato il lavoro, memorizza il risultato nel proprio registro virtuale, nel registro virtuale dell’altra istruzione e in memoria. L’eliminazione della lettura in memoria migliora la prestazione del microprocessore. Un hazard di controllo si presenta quando il micro non sa dove trasferire il controllo perché non è ancora stato determinato se e dove saltare. Un esempio di hazard si presenta anche quando si verifica la cache miss. Il problema può essere risolto complicando l’hardware della CPU, ma in generale i progettisti preferiscono mantenere un hardware semplice, per avere una frequenza di clock quanta più elevata possibile, e demandare il problema al software. Per evitare conflitti tra i vari stadi viene implementata all’inizio della pipeline una cache dedicata alle istruzioni. Un altro problema che può causare lo stallo della pipeline è relativo al salto, poiché alcuni stadi possono eseguire istruzioni indesiderate. Allo scopo di limitare i problemi di stallo, la pipeline viene dotata di una unità che preleva (prefetching) una certa quantità di istruzioni e, dopo aver riconosciuto i salti, le ordina in coda in modo opportuno . L’unità di dispatch preleva le istruzioni dalla testa della instruction queue e le invia allo stadio di esecuzione. È importante avere una coda abbastanza lunga perché si può avere stallo: • nella pipeline ma l’unità di fetch può continuare a caricare altre istruzioni; • nell’unità di fetch, in questo caso la pipeline può continuare a eseguire le istruzioni. La branch delay instruction è l’istruzione immediatamente successiva a una istruzione di salto condizionato. Tale branch delay instruction viene eseguita anche se non si verificano le condizioni per il salto. Nelle architetture pipeline la posizione di questa istruzione è definita branch delay slot. Il branch delay slot è chiaramente un effetto indesiderato della pipeline che può essere riempito in due modi: • si affida al compilatore il compito di riordino in modo tale da eseguire quelle istruzioni che comunque vanno eseguite perché non dipendenti dal salto; • si applica la tecnica di branch prediction, ovvero si cerca di prevedere l’esito del salto condizionato; poiché non è certo che quanto predetto sarà valicato successivamente, si definisce speculativa questa architettura.

Pipeline a 4 stadi (a); pipelining delle istruzioni (b).

Con la predizione e l’esecuzione speculativa è possibile utilizzare in modo più efficiente la maggior parte degli slot presenti nella pipeline limitando gli stalli dovuti alle istruzioni di salto. I microprocessori più moderni sono dotati di una Branch Prediction Unit che consiste in una unità che ha il compito di prevedere l’istruzione successiva da eseguire quando si prese- -ntano salti condizionati. L’unità di predizione conferisce al microprocessori una notevole accelerazione, ma anche il rischio di un restart della pipeline in caso di predizione errata. Il funzionamento dell’unità di branch prediction si basa su un algoritmo misto, statico e dinamico. L’algoritmo dinamico valuta la storia delle predizioni precedenti di quella istruzione. Se l’istruzione si presenta per la prima volta, si basa sull’algoritmo statico. L’algoritmo statico basa la sua valutazione su decisioni prefissate. L’evoluzione del pipelining ha portato a progettare un’architettura superscalare.

Architettura superscalare Per aumentare il livello di parallelismo, si può, in alternativa all’aumento della profondità, adottare la strategia della tecnica multiple issue. Questa tecnica consiste nell’aumentare le unità indipendenti di esecuzione delle istruzioni, con l’obiettivo finale di avere CPI < 1, ovvero meno di un ciclo di clock per ogni istruzione. L’architettura superscalare (letteralmente oltre (super) unidimensionale (scalare)), nata in ambiente RISC, consiste nell’implementare più pipeline in parallelo. Le pipeline possono essere uguali o differenti. Quando le pipeline sono tutte uguali, condividono gli stessi registri, con probabilità molto elevata di conflitti e dipendenze. In questo caso per limitare i problemi, tutte le pipeline devono vedere registri virtuali. Un micro di questo tipo è l’ALPHA della DEC. Nella maggior parte dei microprocessori invece vi sono pipeline differenti perché ognuna è specializzata nell’eseguire operazioni differenti. Per esempio alcune operano in floating point e altre elaborano numeri interi. In questo caso le pipeline prelevano solo le istruzioni che possono eseguire, non sono soggette alla dipendenza tra loro e utilizzano risorse (registri) differenti. Le unità di fetch e di dispatch (vedi la soprastante figura) operano su più istruzioni contemporaneamente. I microprocessori con questo tipo di architettura sono in grado di eseguire più di una istruzione per ciclo di clock. Una particolare importanza riveste il ruolo dell’unità di dispatch che è più sofisticata in quanto deve essere in grado di scegliere e smistare le istruzioni sulle varie pipeline. I processori superscalari operano nel seguente modo: • prelevano istruzioni dalla memoria; • prelevano e decodificano molte istruzioni alla volta dal flusso di istruzioni ricevute; • contemporaneamente valutano i risultati dei branch condizionali in anticipo in modo tale da assicurare alle pipeline un flusso ininterrotto di istruzioni. L’architettura scalare utilizza l’ILP dinamico per individuare le istruzioni da eseguire parallelamente. In questo tipo di architettura la presenza degli hazard può essere molto più grave rispetto alla pipeline semplice. I vantaggi dell’architettura superscalare sono i seguenti: • la struttura è compatibile con qualunque ISA, ed è utilizzabile sia dai CISC sia dai RISC; • la programmazione assembly e il compilatore vedono un codice sequenziale come nelle CPU scalari. Gli svantaggi invece si possono così riassumere: • hardware di controllo abbastanza complesso perché il livello di parallelismo grava esclusivamente sull’hardware; • lo scheduling delle istruzioni è a run-time; • out-of-order execution, conseguenza dell’ILP dinamico • ciclo di clock più lungo. Lo scheduling delle istruzioni consiste nel riordino delle istruzioni in modo tale che possano essere eseguite senza gli stall. Lo scheduling è a run-time (o dinamico) quando viene eseguito durante l’esecuzione delle istruzioni, mentre è a compile time quando viene realizzato in fase di programmazione

Architettura VLIW L’architettura VLIW (Very Long Instruction Word) è una struttura nella quale il parallelismo delle istruzioni (ILP) è di tipo statico e quindi demandato al compilatore. Con la tecnica VILW, come con la superscalare, si può ottenere CPI < 1, ovvero eseguire una istruzione in un tempo inferiore a un ciclo di clock. Lo scheduling delle istruzioni è a compile-time. Al compilatore viene descritto l’hardware del processore in modo tale da impacchettare in un’unica Very Long Instruction Word una serie di istruzioni che si possono eseguire parallelamente. Il compilatore crea un POE (Plan Of Execution) formato da serie di istruzioni molto lunghe. Affinché possa assolvere al compito di schedulare in modo corretto le operazioni all’interno delle very long instruction, il compilatore deve: • conoscere il numero e il tipo di unità funzionali per stabilire quali istruzioni e di quale tipo si possono inserire nella stessa word; • conoscere la latenza delle operazioni per sapere quanti cicli di clock servono per eseguire le operazioni. Le unità funzionali, che sono associate alle operazioni da eseguire, sono: • la ALU in FP (Floating Point); • la ALU per integer (per elaborare i numeri interi); • l’unità load/store che provvede a leggere e scrivere i dati dai registri alla memoria.

L’hardware di questi processori è molto semplice perché si deve limitare a eseguire il POE deciso dal compilatore. Le istruzioni VLIW sono lunghe da 256 a 1024 bit. I vantaggi dei processori VLIW sono i seguenti: • semplificazione dell’hardware di controllo con conseguente diminuzione della potenza e dell’aumento del clock; • la modifica dello scheduling software del compilatore è più facile della modifica dell’hardware di controllo; • il sistema è scalabile perchè si può aumentare il livello di parallelismo aumentando la issue-width (numero massimo di slot-operazioni) in un bundle (pacchetto di istruzioni). • il codice VLIW è più compatto rispetto ad altre soluzioni. Gli svantaggi sono: • in presenza di eventi quali cache miss hanno un comportamento meno flessibile dei superscalari; • il software per processori VLIW deve essere ricompilato per essere esportato su altri processori; ad esempio una word che richiede tre unità funzionali FP e che ha una certa latenza non può essere riproposta in modo identico per altri processori con due unità FP; • i processori EPIC, evoluzione dei VLIW, non sono compatibili tra loro e con i precedenti VLIW.

Raffigurato a lato è riportato un confronto tra le architetture di una CPU classica e di quella VLIW

Architettura EPIC L’architettura EPIC (Explicitly Parallel Instruction Computing), è nata per superare i limiti della VLIW. Il limite più evidente dell’architettura VLIW è quello di essere strettamente collegata al tipo di hardware implementato in quella classe di microprocessore. Cambiando tipologia di micro è necessario ricompilare il codice sul nuovo hardware. La richiesta degli utenti è invece proprio quella di mantenere il software con CPU differenti. Allo scopo di superare questi problemi della VLIW, alcune case costruttrici hanno sviluppato soluzioni alternative una di queste è la EPIC. L’architettura EPIC, nata alla fine degli anni ’90 come evoluzione della VLIW, sviluppata da Intel e HP, ha portato alla struttura IA-64 utilizzata nei processori Itanium e Itanium2. La EPIC ha 2 caratteristiche che la differenziano dalla VLIW: • una spiccata collaborazione tra hardware e software; • un numero più elevato di registri.

Confronto tra l’architettura di una CPU classica e di una VLIW.

Le istruzioni vengono raggruppate in word, come nell’architettura VLIW, ma sono integrate con informazioni sul parallelismo tra le varie word. In questo modo anche se varia l’hardware interno, i microprocessori possono utilizzare ugualmente lo stesso codice. Le unità di decodifica, che possono essere anche circuitalmente semplici poiché lo scheduling è effettuato dal compilatore, utilizzano le informazioni sul parallelismo in modo efficiente. Per migliorare le prestazioni, nel micro EPIC sono state aggiunte: • alcune centinaia di registri per non implementare l’unità di ridenominazione dinamica dei registri, visibili al compilatore; • alcune istruzioni predicative per evitare lo svuotamento delle pipeline; • alcune soluzioni innovative che consentono di velocizzare i cambi di contesto tra le subroutine e per migliorare la gestione della cache.

Naturalmente l’aggiunta di altri registri a quelli già esistenti (generali, predicativi, float, re-naming e stack) porta i transistor a un totale di 1,72 miliardi.

ILP dinamico e statico L’ILP dinamico è una tecnica circuitale che consente di individuare le istruzioni che si possono eseguire in modo parallelo. Pertanto il livello di parallelismo è affidato esclusivamente all’hardware. L’ILP dinamico si realizza in vari modi: • out-of-order; • predizione dei branch; • esecuzione speculativa; • rinominazione dei registri. Quando si utilizza la struttura a pipeline non tutte le istruzioni possono essere eseguite parallelamente. Infatti una istruzione può utilizzare dati che si ottengono come risultati da istruzioni precedenti. Ad esempio: L’istruzione necessita del risultato della prima istruzione per essere eseguita. La pipeline che esegue la deve essere mandata in stallo. Dalla lista delle istruzioni si nota che la non dipende dalle altre due, quindi inviando nella pipeline nell’ordine si evita di introdurre gli stalli. La sequenza nell’esecuzione delle istruzioni porta però all’out-of-order ovvero a un fuori ordine nella generazione dei risultati rispetto allo sviluppo del programma. In presenza di un salto un’unità di predizione esamina i casi precedenti che si sono verificati con lo stesso tipo di istruzione e valuta se il salto avverrà o meno. Se la predizione è esatta la pipeline non viene bloccata, in caso contrario viene svuotata per ripartire nuovamente. Basandosi su una statistica dei casi precedenti di salto, il processore esegue in modo speculativo il salto ottenendo dei risultati. Se tali risultati risultano esatti il micro ha guadagnato tempo, se invece l’esecuzione speculativa si rivela errata, i risultati vengono annullati. Alcune istruzioni pur essendo indipendenti possono utilizzare lo stesso registro per la memorizzazione del risultato. Il microprocessore utilizza altri registri per memorizzare temporaneamente i dati e allocarli successivamente nello stesso registro e nella stessa sequenza indicata dal programma.

In presenza di un salto un’unità di predizione esamina i casi precedenti che si sono verificati con lo stesso tipo di istruzione e valuta se il salto avverrà o meno. Se la predizione è esatta la pipeline non viene bloccata, in caso contrario viene svuotata per ripartire nuovamente. Basandosi su una statistica dei casi precedenti di salto, il processore esegue in modo speculativo il salto ottenendo dei risultati. Se tali risultati risultano esatti il micro ha guadagnato tempo, se invece l’esecuzione speculativa si rivela errata, i risultati vengono annullati. Alcune istruzioni pur essendo indipendenti possono utilizzare lo stesso registro per la memorizzazione del risultato. Il microprocessore utilizza altri registri per memorizzare temporaneamente i dati e allocarli successivamente nello stesso registro e nella stessa sequenza indicata dal programma. Con l’ILP statico il parallelismo delle istruzioni viene deciso nella fase di compilazione del codice. Infatti il compilatore, dopo aver analizzato il programma, rileva le istruzioni che si possono eseguire simultaneamente. Il micro esegue le istruzioni già organizzate dal compilatore, quindi è molto più semplice da un punto di vista dell’hardware. L’ILP statico è utilizzato nei microprocessori embedded per problemi di spazio, consumi e costi perché i micro con ILP dinamico hanno un hardware molto complesso. I processori Itanium della Intel utilizzano l’ILP statico.