Metodologia di ottimizzazione del codice basata su macroistruzioni per processori con parallelismo a livello di istruzione

2 1. Processori RISC e Instruction Level ParallelismNei processori con architettura a stack, gli operandi di un'istruzionesono memorizzati in uno stack; un'istruzione che utilizza un solo operandolo preleva dalla cima dello stack e deposita il risultato sempre in cima allostack; un'istruzione che utilizza due operandi li preleva dalle prime dueposizioni e deposita il risultato sulla cima dello stack2.I processori con architettura ad accumulatore contengono un registrodetto accumulatore che, implicitamente, e la destinazione di tutte le istru-zioni. Inoltre, quando un'operazione ha due operandi uno e sempre l'ac-cumulatore mentre l'altro e un riferimento in memoria; non ci sono cioeregistri interni per memorizzare dati intermedi. Un esempio di macchinaad accumulatore e il processore Zilog Z80 che, benche dotato di alcuniregistri interni oltre all'accumulatore, questi venivano utilizzati tutti perscopi speciali come contatori, indirizzi per accesso alla memoria, ecc. .Nell'architettura registri-memoria il processore possiede dei registri in-terni per la memorizzazione dei dati intermedi ma e comunque ancora pos-sibile (ed anzi spesso necessario) che un'operando di un'istruzione vengaprelevato dalla memoria. Ad esempio l'architettura x86, cos chiamata dalnome del primo processore che l'ha implementata, l'Intel 8086, e un'ar-chitettura registri-memoria. Molti dei registri interni dei processori x86hanno ancora un uso specico come nello Zilog Z80, ma al contrario delprocessore Z80 molte istruzioni hanno come destinazione registri qualsiasi.Nei processori con architettura registri-registri gli operandi di tutte leistruzioni, tranne quelle che accedono alla memoria, devono essere registriinterni. Per questo motivo, in generale, i processori con questa architetturahanno molti registri interni. Un esempio di macchina registri-registri e ilprocessore MIPS R4000.Per quanto riguarda le funzionalita oerte dall'instruction set, vi sonodue architetture.Nell'architettura CISC (Complex Instruction Set Computer) l'insiemedelle istruzioni oerte dal processore e molto vasto e vi sono istruzioni chesvolgono operazioni molto complesse. Questo tipo di architettura nacquedalla necessita di tradurre, nel modo piu semplice possibile, i linguaggi ad2Questo modello di calcolo si puo rappresentare con la notazione con operatori postssi(notazione polacca inversa) ed e stato utilizzato ampiamente nelle macchine calcolatrici.
1.2. Una misura della velocita di esecuzione del codice 3alto livello in codice macchina quando la tecnologia dei compilatori nonera molto avanzata. La complessita della traduzione dei linguaggi si epero spostata dalla fase di compilazione alla fase di esecuzione del codicemacchina. L'architettura x86 e l'esempio piu importante di architetturaCISC presente oggi.Nell'architettura RISC (Reduced Instruction Set Computer) ci sono unnumero limitato di istruzioni ma soprattutto le istruzioni svolgono opera-zioni \semplici". L'architettura RISC nasce dall'idea che se le istruzionisvolgono operazioni semplici allora verranno eseguite dal processore moltopiu velocemente delle complesse istruzioni di un processore CISC. Certoa parita di \compito" dovranno essere eseguite piu istruzioni RISC cheistruzioni CISC ma il vantaggio in velocita di esecuzione e tale che e co-munque conveniente l'approccio RISC. Inoltre il fatto che le operazionisvolgono operazioni semplici, rende possibile l'applicazione delle tecnichedi riorganizzazione del codice che verranno trattate nel seguito. In eet-ti quest'idea si e rivelata esatta dato che ad oggi tutti i nuovi processoriimplementano architetture RISC. Anche gli ultimi processori dell'archi-tettura x86 come il Pentium Pro e l'Amd K6 hanno al loro interno un\cuore" RISC: le istruzioni dell'architettura x86 vengono infatti tradottein istruzioni piu semplici (applicando la \losoa" RISC) prima di essereinviate all'hardware dedicato all'esecuzione.Nel seguito si descriveranno le varie evoluzioni che l'iniziale architet-tura RISC ha avuto e che ne hanno decretato l'indubbio successo comearchitettura di riferimento per i processori della nuova generazione.1.2 Una misura della velocita di esecuzione del codicePoiche nel seguito si descriveranno alcune evoluzioni dell'architetturaRISCe importante avere un parametro numerico che ne rappresenti le prestazioniin termini di velocita di esecuzione. Poiche i processori che qui interessanosono macchine sincrone (funzionano con un clock ssato), una misura deltempo impiegato per l'esecuzione di un programma eT = N 
-1
4 1. Processori RISC e Instruction Level Parallelismove N e il numero di cicli di clock richiesti e -1 e la durata di un ciclo diclock3.Inoltre, denotato con I il numero di istruzioni del codice, si puo calcolareil numero medio di cicli di clock per istruzione4CPI = NIda cui si puo esprimere il tempo T comeT = I 
 CPI 
 -1:Dall'equazione precedente si vede che il tempo di esecuzione T di unprogramma dipende da I il numero di istruzioni del programma; CPI il numero medio di cicli di clock per istruzione; -1 la durata di un ciclo di clock.Poiche T e direttamente proporzionale alle tre precedenti quantita, permigliorare il tempo di esecuzione si puo cercare di ridurre I, CPI o -1.Sfortunamente tali quantita sono strettamente correlate e quindi non epossibile una modica indipendente delle stesse.Le architetture CISC tendono a ridurre I; infatti, avendo istruzionicomplesse, il numero di istruzioni utilizzate, in media, e minore di unaarchitettura RISC. Le architetture RISC tendono a ridurre CPI e -1;infatti, il periodo di clock puo essere ridotto con l'uso di logica sempliceper l'esecuzione delle istruzioni, mentre il parametro CPI viene ridottoutilizzando la pipeline e altre tecniche descritte in seguito.3Indicato con -1 poiche in genere la frequenza di clocke indicata con .4Clock cycles Per Instruction, CPI.
1.3. Il concetto di pipeline e di parallelismo a livello di istruzione 51.3 Il concetto di pipeline e di parallelismo a livello diistruzioneIl concetto di pipeline e alla base dei processori RISC di prima generazio-ne (processori pipelined) ed e un componente importante delle successivegenerazioni (processori superpipelined e superscalar).Per pipeline si intende una sequenza di passi, dette fasi o stadi dellapipeline, che vengono eseguiti in successione, cioe l'ingresso di uno stadioe l'uscita dello stadio precedente, per produrre un risultato. Il concetto dipipeline non e specico della teoria dei microprocessori; la struttura a pipe-line, ad esempio, e applicata con successo nei processi produttivi. Possiamoaermare che ovunque vi sia un processo con del parallelismo intrinseco, sipuo applicare il concetto di pipeline. Il concetto di parallelismo a livello diistruzione rende utile l'applicazione della pipeline all'esecuzione di codicesu microprocessore.1.3.1 PipelineConsideriamo ad esempio un processo costituito da 4 fasi indipendenti, cioeche non hanno nessuna interazione tranne all'ingresso e all'uscita. Imma-giniamo di porre all'ingresso del primo stadio un oggetto e che il prodottodella pipeline esca all'uscita della fase 4. Un esempio pratico5 di questo pro-cesso potrebbe essere la produzione di un'oggetto smaltato a partire dallamateria prima. Le fasi potrebbero essere stampaggio, forno, smaltatura,asciugatura. Supponiamo, inoltre, che ogni fase della pipeline abbia duratacostante e uguale a t istanti temporali. Vi sono due modi di produrre og-getti utilizzando questa struttura. Nel primo modo si introduce la materiaprima al tempo 0 e si attende il tempo 4t in cui l'oggetto prodotto escedall'ultima fase prima di introdurre altra materia prima. Questo modo,rappresentato in gura 1.1 corrisponde all'utilizzare la struttura come un\blocco unico", cioe considerando il processo come indivisibile. Nel secon-do modo si introduce la materia prima al tempo 0 e si attende che termini5tralasciando il campo dei microprocessori che verra analizzato molto in dettaglio nelseguito.
6 1. Processori RISC e Instruction Level Parallelism
Stampaggio Forno Smaltatura Asciugatura
6t
t
2t
3t
4t
5t
Tempo
Fasi
Figura 1.1: Produzione di un oggetto
la fase di stampaggio, al tempo t. A questo punto l'oggetto stampato entranel forno e libera la fase di stampaggio che, puo essere utilizzata per unnuovo oggetto. Quindi al tempo t viene anche introdotta altra materiaprima nella prima fase. Si puo procedere in modo analogo al tempo 2t enei tempi successivi, come rappresentato in gura 1.2.Cos facendo nel primo metodo si produce un oggetto ogni 4t istantitemporali. Utilizzando il metodo pipeline, dopo un ritardo iniziale di 3tistanti, si produce un oggetto ogni t istanti temporali.Questo semplice esempio e utile per comprendere quella che viene co-munemente chiamata equazione della pipelinep(k)=kntn +(n- 1)t = kt+(n- 1)t (1.1)ove p(k) e il tempo a cui viene prodotto l'oggetto k-esimo, n e il numerodi stadi della pipeline e t e la durata di uno stadio. Si vede quindi, che,
1.3. Il concetto di pipeline e di parallelismo a livello di istruzione 7
Stampaggio Forno Smaltatura Asciugatura
6t
t
2t
3t
4t
5t
Tempo
Fasi
Figura 1.2: Produzione pipelined di un oggettodopo un ritardo iniziale di durata (n- 1)t, viene prodotta un'uscita ogni tistanti.Questa semplice struttura viene applicata ai microprocessori scompo-nendo l'esecuzione di un'istruzione in fasi che possono essere svolte in pa-rallelo. Come si vedra in seguito la struttura della pipeline utilizzata neiprocessori RISC eunpopiu complessa di quella ora vista, poiche gli ingres-si di uno stadio di pipeline possono essere le uscite di stadi successivi relativiad un'istruzione precedente. E necessario quindi introdurre degli istanti distallo6 in cui una parte della pipeline viene bloccata per \sincronizzare" glistadi. Prima di esaminare l'uso della pipeline nei microprocessori vediamoun'altra nozione fondamentale per le architetture RISC.
6pipeline bubble, pipeline stall.
8 1. Processori RISC e Instruction Level Parallelism1.3.2 Parallelismo a livello di istruzionePer parallelismo a livello di istruzione7 si intende la proprieta di un bloccodi codice per cui alcune istruzioni, non essendo \dipendenti" fra di loro pos-sono essere eseguite in parallelo. Vediamo cosa si intende per dipendenzafra istruzioni. Si possono trovare tre tipi di dipendenze fra istruzioni data dependence (o 
ow dependence); name dependence; control dependence.Si parla di Data dependence8 quando due istruzioni sono legate da un'ef-fettivo scambio di dati. Ad esempio nel codice1. ADDL GR3, GR4, GR52. ADDL GR5, GR6, GR7l'istruzione 2 ha come operando il registro GR5,mentre l'istruzione 1 ha taleregistro come destinazione. E chiaro quindi, che l'istruzione 2 puo essereeseguita solo quando l'istruzione 1 ha prodotto il risultato.Si denisce latenza di una istruzione, il numero di cicli di clock chebisogna attendere per poter utilizzare la sua destinazione.Per Name dependence si intende una dipendenza che non deriva dalloscambio di informazioni, ma solo dall'uso da parte delle istruzioni dellostesso \nome" cioe dello stesso identicatore di registro (o stesso indirizzo dimemoria). Diciamo che c'e una antidependence9 quando il nome utilizzatoe destinazione della prima istruzione e sorgente della seconda. Ad esempionel blocco di codice1. LDW x(0, GR0), GR52. ADDL GR5, GR6, GR73. SUB GR6, GR3, GR57ILP, Instruction Level Parallelism8Chiamate anche RAW, Read after Write.9WAR, Write after Read
1.3. Il concetto di pipeline e di parallelismo a livello di istruzione 9c'e una antidipendenza fra l'istruzione 3 e l'istruzione 2 in quanto l'istru-zione 3 scrive il registro GR5 che viene letto dall'istruzione 2.Diciamo che c'e una output-dependence10 quando il nome utilizzato edestinazione di entrambe le istruzioni. Prendendo come esempio il codiceprecedente, si vede che l'istruzione 3 e output dependent dall'istruzione 1poiche entrambe hanno il registro GR5 come destinazione.Come si vedra in seguito le name dependence possono essere eliminatee cio aumenta il grado di parallelismo del blocco di codice, cioe il numeromedio di istruzioni che possono essere eseguite in parallelo.Per Control dependence si intende una dipendenza che deriva dalla strut-tura del 
usso di esecuzione del codice. Queste dipendenze sono generatedalla presenza di istruzioni di salto condizionato o istruzioni che condizio-nano l'esecuzione o meno di altre istruzioni11. Ad esempio nel blocco dicodice1. LDW x(0, GR0), GR52. LDI 0, GR63. COMIB,= 0, GR5, next4. ADDIL 1, GR6, GR6next. . . .l'istruzione 4 viene eseguita solo se l'istruzione 3 non eettua il salto; quindi4 e control dependent da 3.Anche le control dependence possono essere in parte eliminate come sivedra in seguito.In [16] si aerma che il grado di parallelismo all'interno di un basic-block12 raramente supera 3 (calcolato su un insieme rappresentativo diprogrammi). Si sono quindi sviluppate tecniche, descritte in seguito, peraumentare tale valore. Infatti, nelle implementazioni dei processori super-pipelined e superscalar, per ottenere buone prestazioni e necessario avereun alto grado di parallelismo nel codice.10WAW, Write after Write11Nell'architettura HP PA-RISC moltissime istruzioni hanno la possibilitadiannullare(nullify) l'esecuzione dell'istruzione che le segue in funzione dell'esito dell'istruzione stessa.12Unbloccodicodiceche non ha ne punti di entrata (destinazioni di branch o jump)ne punti di uscita (branch o jump).
10 1. Processori RISC e Instruction Level Parallelism1.4 Processori pipelined e superpipelinedL'idea che sta alla base dei processori RISC, come abbiamo accennato,e rendere semplici le istruzioni da eseguire in modo che possano essereelaborate a velocita elevate. Una prima conseguenza di questo approccio,che dierenzia i processori CISC dai processori RISC, e che le istruzionisono codicate tutte con parole di codice della stessa lunghezza13. Ciorende molto piu semplice la decodica e l'identicazione degli operandi.Un'altra conseguenza e che si vuole che la maggior parte delle istruzionivenga eseguita in un solo ciclo di clock. Cio ha portato all'adozione dellapipeline come elemento centrale del processore.1.4.1 Processori pipelinedNei processori pipelined l'esecuzione di un'istruzione viene suddivisa in fasi,il numero delle quali e detto profondita della pipeline. Per esemplicarel'uso della pipeline nel seguito si descrivera un semplice processore (similea quello che si trova in [14]); nel seguito si dara una descrizione sommariadel processore MIPS R4000.Supponiamo che le fasi della pipeline siano: Instruction Fetch (IF); Instruction Decode (ID); Execute (EX); Memory access (MEM); Write back (WB).Nella fase di Instruction Fetch un'istruzione viene prelevata dalla memo-ria. Nei processori reali questa fase in genere viene suddivisa in due o piu13Tipicamente 32 o 64 bits. Per confronto, la lunghezza di un'istruzione per il processoreIntel 80386 varia da 8 a 136 bits.
1.4. Processori pipelined e superpipelined 11
fasi perche si utilizzano memorie cache per velocizzare gli accessi in me-moria e quindi e necessario trattare il caso in cui l'istruzione richiesta none presente nella cache.La fase di Instruction Decode serve per decodicare l'istruzione; in par-ticolare viene identicato il tipo di istruzione, gli operandi sorgente e ladestinazione. Essendo ssa la lunghezza della parola di codice che rap-presenta l'istruzione, se la posizione dei bits che codicano gli operandi esempre la stessa, gli operandi possono essere letti dai registri interni con-temporaneamente alla decodica. Se successivamente si vede che il tipodi istruzione non prevedeva l'uso, ad esempio, del secondo operando, lalettura eettuata e stata inutile ma, comunque, non \dannosa"14.La fase di Execute e quella in cui gli operandi vengono utilizzati perprodurre la destinazione. Per ora consideriamo un processore con un'u-nita ALU15 intera come unico elemento di questa fase. In particolare, peristruzioni di calcolo, l'ALU viene utilizzata per svolgere l'operazione richie-sta; per le istruzioni di accesso alla memoria, l'ALU viene utilizzata per ilcalcolo dell'indirizzo eettivo cui si vuole accedere. Nei processori reali inquesta fase l'esecuzione passa ad una delle varie unita funzionali del pro-cessore (ALU intera, ALU virgola mobile, unita di accesso alla memoria,ecc.).Nella fase di Memory Access si accede, in lettura o in scrittura, alla me-moria. Nei processori reali, come nella fase di instruction fetch, questa fasee spesso suddivisa in piu fasi per controllare l'accesso alla cache memory.Nella fase di Write back si scrive la destinazione di un'istruzione, oradisponibile, nel registro interno corrispondente.Uno schema di questa pipeline e visibile in gura 1.3.Le barrette scure tra uno stadio e l'altro rappresentano dei registri latchche mantengono i segnali di comunicazione fra gli stadi ad ogni istante diclock.14Cioevero nei processori che non cercano di leggere e decodicare piu di una istruzioneper ciclo di clock. Nei processori superscalar, il fatto di leggere gli operandi anche quandonon servono implica l'uso di piu porte di lettura (due per ogni istruzione) che non semprepossono essere disponibili.15Arithmetical Logical Unit.
12 1. Processori RISC e Instruction Level Parallelism
RegDM
A
L
U
IM Reg
Decode Execute Memory Write Back
t
4210 5
Fetch
3Figura 1.3: Una semplice struttura a pipeline1.4.2 Data dependences e pipeline forwardingAbbiamo visto come si applica la struttura a pipeline ai microprocessori.Vediamo ora un potenziale problema, risolto con la tecnica del forwarding,con un esempio.Supponiamo che il processore deva eseguire il blocco di codice1. ADD GR5, GR6, GR72. ADD GR7, GR8, GR9ove il registro GR7 e destinazione dell'istruzione 1 e sorgente dell'istruzione2 (vi e una data dependence). Poiche gli operandi di un'istruzione vengonoletti nella fase di instruction decode (ID), mentre i risultati vengono scrittinella fase di write back (WB), si presenta la situazione di gura 1.4 ove, laseconda istruzione deve \aspettare" che la prima istruzione superi la fase diWB prima di poter completare la fase di ID con la lettura degli operandi.Si ha quello che viene chiamato stallo.Questo problema, che limita di molto la velocita di esecuzione del co-dice, puo essere brillantemente risolto con la tecnica del forwarding. Perforwarding si intende la capacita della pipeline di \passare" l'uscita di unostadio agli stadi precedenti. Questo fatto va contro la struttura semplicedi pipeline denita in 1.3.1 ma e reso necessario dalla struttura utilizzata.Nell'esempio precedente, il risultato dell'istruzione 1 e disponibile giaall'uscita dello stadio di execute (EX), quindi non e necessario attenderelo stadio WB per poterlo utilizzare. Passando il risultato dello stadio diEX all'ingresso dello stadio stesso si riesce ad utilizzarlo nell'istruzioneimmediatamente seguente.
1.4. Processori pipelined e superpipelined 13
S
S
S
IF
ID
EX
MEM
WB
IF
ID
EX
Tempo
flusso istruzioni
I2
I1
Figura 1.4: Pipeline: esempio di stallo
Il forwarding aumenta in modo considerevole la complessita dei datapath16 all'interno del processore e richiede l'inserimento di logica per lascelta di quale data path utilizzare ad ogni stadio. E chiaro, pero, chel'incremento di prestazioni e notevole. Il forwarding potrebbe essere evitatose il codice eseguito fosse ad alto grado di parallelismo: se ci fossero pochedipendenze fra le istruzioni esse causerebbero pochi stalli.L'interazione ALU-ALU non e l'unica causa di possibili stalli. Si pensial caso in cui due istruzioni necessitano l'accesso contemporaneo ai registri,16I collegamenti fra le varie unita per lo scambio di dati.
14 1. Processori RISC e Instruction Level Parallelismgeneralmente contenuti in un blocco hardware chiamato register le ,unain lettura (fase ID) e l'altra in scrittura (fase WB). Per ovviare a questoproblema, in generale, la scrittura nel register le viene eettuata nella pri-ma meta della fase di WB, mentre la lettura viene eettuata nella secondameta della fase ID. Cos si ottengono valori corretti anche nel caso in cui ilregistro letto e scritto sia lo stesso.In gura 1.5 sono rappresentati i livelli di forwarding necessari nellastruttura nora discussa per ottenere le migliori prestazioni possibili. Comesi puovedere dalla gura, c'e del forwarding anche \di secondo livello" cioefra istruzioni che distano due istanti di clock.
A
L
U
ID
A
L
U
IDIF
A
L
U
IDIF
IF MEM
MEM
MEM WB
WB
WB
Figura 1.5: Pipeline forwarding.1.4.3 Control dependences e delayed branchingNel paragrafo precedente si e discusso come limitare il degrado di prestazio-ni quando ci sono delle data dependence fra le istruzioni. Un'altro problemae causato dalle istruzioni di salto condizionato (branch) e, in modo simi-le, dalle istruzioni di salto incondizionato (jump). Un'istruzione di saltocondizionato fa cambiare il 
usso dell'esecuzione del codice in dipendenzadell'esito di una condizione. Supponiamo che nella struttura presentata
1.4. Processori pipelined e superpipelined 15
la condizione venga valutata nella fase di EX17 ove viene anche calcola-to l'indirizzo eettivo di salto, condizionato o meno. Inoltre il ProgramCounter18 viene aggiornato al termine della fase EX. Nel seguito si trattasolo il caso delle istruzioni di salto condizionato poiche una istruzione dijump e equivalente ad un'istruzione di branch con condizione sempre ve-ra19. Vi sono quindi due cicli di clock (ID e EX dell'istruzione di branch)in cui il processore non conosce la prossima istruzione che dovra eseguire.Quindi, se ad esempio si considera il blocco di codice1. ADDL GR1, GR5, GR52. LDI 0, GR63. COMIB,= 0, GR5, 54. ADDIL 1, GR6, GR65. ADD GR5, GR6, GR76. SUB GR1, GR3, GR9si puo presentare la situazione di gura 1.6 in cui il processore deve atten-dere due cicli di clock se il branch viene eettuato (taken branch) oppureun ciclo di clock se il branch non viene eettuato (not taken branch). In-fatti, durante la fase di ID dell'istruzione di branch, viene fatta la fase diIF dell'istruzione successiva (la 4). Se il branchetaken questa fase e statainutile e quindi corrisponde ad uno stallo; se il branch e not taken si puocontinuare con la fase di ID.Per ridurre, almeno in parte, questo problema molte architetture adot-tano quello che viene comunemente chiamato delayed branch20. Si decideche, a prescindere dall'esito dal test della condizione dell'istruzione di sal-to, un certo numero (ssato) di istruzioni, che costituiscono il delay slot,vengono eseguite in ogni caso. Il processore, quindi, puo cos continuarel'elaborazione del codice. Naturalmente sta al compilatore o al program-matore di codice macchina, inserire dopo il branch istruzioni utili. Spesso17Per condizioni semplici, tipo test di zero, si potrebbe spostare la valutazione dellacondizione nella fase di decode18Il registro che indica qual'e la prossima istruzione da eseguire19Almeno per le architetture in cui la condizione di branchvienevalutata al piu tardicontemporaneamente all'indirizzo eettivodibranch.20Salto ritardato.