Perchè un ennesimo articolo sulle pipeline? In rete si trova già molto materiale, e anche qui su Appunti Digitali Yossarian ha già scritto almeno due articoli al riguardo (qui e qui).
Tuttavia, avendo in programma di scrivere una serie di articoli sull’architettura di processori superscalari out-of-order, è necessario avere ben chiari alcuni concetti sulle pipeline in-order, per capirne funzionamento, prestazioni e limiti, e comprendere quindi cosa ha spinto i computer architect a cimentarsi con qualcosa di così complesso come i processori out-of-order.
In questo articolo farò un ripasso delle pipeline in-order, partendo da una visione “idealizzata” e andando poi a rimuovere queste idealità. Nel prossimo articolo vedremo come si costruisce una pipeline “reale”, che sia cioè non solo corretta ma anche veloce, e ne investigheremo i limiti.
Pipeline: una catena di montaggio
La tecnica di pipelining è la più vecchia, semplice ed efficace per aumentare le prestazioni di un processore. Il numero di stadi di una pipeline può variare moltissimo a seconda del periodo storico, del costo del processore, e dell’ambito di utilizzo: in applicazioni consumer si è andati dai soli 3 stadi di certi ARM ai 31 stadi della famigerata architettura NetBurst (nella sua ultima versione, quella del Prescott), mentre per certe applicazioni particolari vengono usate pipeline anche molto più lunghe (ad esempio il mostruoso migliaio di stadi del processore di rete Xelerated X10q).
Il concetto base è semplice: supponiamo di avere un processore single-cycle, ovvero che esegue una e una sola istruzione completa (dal fetch al ritiro) in un ciclo di clock. Evidentemente, c’è un grosso spreco nell’utilizzo della logica: dopo che l’istruzione è stata caricata ed è stata avviata all’unità di esecuzione, la logica di fetch sta a girarsi i pollici fino alla fine del ciclo; allo stesso modo, dopo che l’istruzione ha lasciato l’unità di esecuzione e si avvia alla fase di ritiro (ad esempio, aggiornare il valore di un registro), anche l’unità di esecuzione attende, senza produrre lavoro utile.
Molto più efficiente sarebbe applicare anche qui il principio della catena di montaggio: dopo che una istruzione lascia il fetch, subito cominciare il fetch della prossima, e così via. Per farlo, è necessario “spezzare” il processore in più sezioni indipendenti, che lavorano, nello stesso momento, su istruzioni diverse; le diverse sezioni sono isolate l’una dall’altra tramite buffer (nel caso più semplice, dei banchi di flip-flop (registri) che mantengono lo stato dell’istruzione man mano che essa procede lungo la pipeline).
Il ritardo di questi buffer si aggiunge al tempo di esecuzione dell’istruzione: il tempo per eseguire la singola istruzione è più alto, ma il throughput del sistema (che equivale alla performance) è maggiore, perchè più istruzioni vengono “lavorate” contemporaneamente.
Quanti stadi?
Appurato che suddividere il circuito in più stadi è vantaggioso, la domanda successiva è ovvia: quanti stadi? Un semplice modello che studia il tradeoff tra costo e performance (dovuto a Peter Kogge, 1981) è quello illustrato in figura:
Si parta dal processore single-cycle (cioè senza pipeline), con un ritardo di propagazione T (e quindi un throughput di 1/T) e un costo hardware G. Ogni stadio di pipeline aggiunge dei registri, che hanno un ritardo S e un costo L. Il throughput e il costo del processore pipelined a k stadi è mostrato in figura, cosi’ come il punto ottimo.
La formula per k_opt è intuitiva: il ritardo e il costo dei registri stanno al denominatore, cioè più i registri costano poco, più conviene aggiungere stadi. All’inizio, aggiungendo pochi stadi si ottengono grossi incrementi prestazionali con poco costo. Man mano che si aggiungono stadi, il miglioramento prestazionale diventa via via sempre più piccolo (ormai gli stadi sono così piccoli che il tempo di ritardo è dominato dai registri di pipeline), mentre il costo hardware continua ad aumentare.
E’ importante ricordare che questa analisi non tiene conto dell’energia consumata dal processore: dato che l’energia cresce indicativamente col cubo della frequenza (a causa dell’aumento di tensione necessario a sostenere frequenze più elevate), pipeline con molti stadi diventano rapidamente svantaggiose, perchè non è possibile aumentare la frequenza oltre limiti ormai “bassi” (pochi Ghz).
Un semplice modello di pipeline ideale
Un modello generico è la pipeline a 6 stadi così costruita:
- Instruction Fetch (IF): la nuova istruzione viene caricata dalla memoria (generalmente, la cache L1 per le istruzioni) per cominciarne l’esecuzione
- Instruction Decode (ID): l’istruzione viene decodificata: bisogna capire che tipo di istruzione è, di quali unità funzionali avrà bisogno, che registri andrà a leggere e/o scrivere, se dovrà accedere alla memoria, eccetera
- Operand Fetch (OF): l’istruzione accede al register file per caricare gli operandi di cui ha bisogno
- Instruction execute (EX): l’istruzione viene “eseguita”: questo può voler dire utilizzare la ALU (se è un’istruzione aritmetico/logica), oppure calcolare un indirizzo di memoria (se è un load/store, o un branch), eccetera
- Memory Access (MEM): se l’istruzione è un load o uno store, in questo stadio accede alla memoria (generalmente, la cache L1 dati)
- Writeback (WB): se l’istruzione deve aggiorare il registro, lo fa adesso; dopodichè, l’istruzione ha terminato
Nella classica pipeline MIPS a 5 stadi, ID e OF sono fusi in un’unico stadio: la decodifica dell’istruzione RISC è così veloce che è possibile accedere subito al register file nello stesso ciclo di clock..
Idealmente, una volta che la pipeline e’ stata riempita e macina istruzioni a ritmo continuo, essa ha questo “aspetto”:
Ogni istruzione prende 6 cicli di clock per completare, uno per stadio, e attraversa tutti gli stadi in ordine. In ogni istante, tutti gli stadi sono occupati, ognuno con un “frammento” diverso di 6 diverse istruzioni.
Come vedremo, però, questa visione idilliaca è ben lontana dalla realtà.
Rimozione delle idealità
Fino a questo punto sono state fatte alcune ipotesi implicite sull’idealità della pipeline. Esse sono:
- sotto-operazioni uniformi: le operazioni del processore possono essere arbitrariamente suddivise in sotto-operazioni di identica durata
- ripetizione di operazioni identiche: le stesse operazioni vengono ripetute identiche su un grande numero di input diversi
- ripetizione di operazioni indipendenti: tutte le operazioni, e tutti gli stadi, sono indipendenti tra loro (cioè non esiste alcuna dipendenza tra i dati, e nessuna scarsezza di risorse)
Sfortunatamente, tutte queste ipotesi sono false:
- le sotto-operazioni non sono uniformi: non è possibile “tagliare” i circuiti in punti arbitrari, ma solo ai confini delle unità funzionali (o di loro sottocomponenti) o, al massimo, delle porte logiche; è necessario far sì che i diversi stadi siano il più simili possibile, per evitare che gli stadi più veloci sprechino tempo per aspettare quelli più lenti (in quanto il clock deve essere tanto lungo quando lo stadio più lento)
- le operazioni non sono identiche: una ISA ha nell’ordine delle centinaia di diverse istruzioni; costruire una pipeline “multifunzionale” capace di eseguirle tutte vuol dire avere degli stadi dedicati a certe istruzioni, che dovranno essere attraversati (inutilmente) da altre istruzioni che non ne fanno uso; è necessario minimizzare il numero di questi stadi
- le operazioni non sono indipendenti: il più delle volte un’istruzione dipende dal risultato di una precedente (ad esempio, l’istruzione numero i genera un operando per l’istruzione i+1); è fondamentale scoprire e risolvere tutte queste dipendenze, pena l’esecuzione errata del programma
I primi due punti ci dicono qualcosa riguardo le prestazioni della pipeline. Rendere le sotto-operazioni il più uniforme possibile (dal punto di vista temporale) significa poter spingere il clock fino al limite massimo (esempio: se si divide un circuito che prende 1 ns in .3 ns e .7 ns, il clock dovrà per forza andare a .7 ns, cioè 1.4 GHz; ma se si riesce a spezzarlo in due stadi da .5 ns, allora si riuscirà a spingerlo fino a 2 GHz). Inoltre, minimizzare gli stadi “idle” per certe istruzioni significa rendere disponibili prima i loro risultati, risultati che saranno utilizzati dalle istruzioni successive.
Ma il terzo punto ci dice qualcosa di diverso: se non teniamo conto delle dipendenze tra le istruzioni, il programma non sarà lento, ma sbagliato! Il problema è che l’ISA ci dice di assumere che una e una sola istruzione sia in esecuzione in un dato istante, e che ogni istruzione deve essere completata (che significa aver eseguito e aver aggiornato tutti i registri e le locazioni di memoria che le competono) prima che l’istruzione successiva cominci l’esecuzione. In una pipeline, questo non è vero: per accelerare, cominciamo ad eseguire l’istruzione i+1 quando l’istruzione i non ha ancora finito. Se non ne teniamo conto, l’istruzione i+1 accederà ai dati sbagliati, lo stato della macchina verrà distrutto, e il programma fallirà.
Conclusioni
In questo articolo abbiamo ripassato le basi della tecnica di pipelining, e abbiamo visto le sue non-idealità in termini molto qualitativi. Nel prossimo articolo mostrerò le tecniche impiegate per costruire una pipeline “reale”: interlock e stalli per garantire il corretto funzionamento, e forwarding per spremere al massimo le prestazioni.
Complimenti a pleg che riesce a rendere ben comprensibili degli argomenti abbastanza “spinosi”, senza però smarrire i contenuti.
Sarò ripetitivo, ma è un piacere leggerti e ogni venerdi attendo sempre il tuo post!
Interessante il punto di collegamento tra pipeline e Ghz il che mi porta ad una domanda probabilmente sciocca degna da Frankestein Junior: dal momento che la frequenza del processore è determinata “di peso” dal quarzo che si monta sulla scheda madre (il quale con i vari moltiplicatori produrrà la velocità che ci aspettiamo) cosa succederebbe se cambiassimo quel quarzo e ne montassimo uno in grado di portare una frequenza maggiore ?
@ D
Succede che non funziona piu’ il processore :)
L’uscita del quarzo va in ingresso a qualche PLL, che ha le sue tolleranze. Se gli cambi la frequenza d’ingresso potrebbe non funzionare piu’. E se anche funzionasse, se alzi la frequenza oltre quella massima che il circuito puo’ sopportare, semplicemente non funzionera’ piu’. Come overcloccare troppo.
Grande articolo, come sempre (Ormai aspetto ogni settimana Te CdMauro e Yossarian con soddisfazione! :) )
Se penso che nel mio libro di superiori per illustrare il concetto di pipeline usavano 3 stadi…(coincidenti con IF, ID e EX) qua addirittura di arriva con i 31 del Pentium 4! :O
Aldilà della complessità intrinseca, quali vantaggi avrebbe mai potuto avere una tale catena? Insomma, cosa veniva fatto per ogni stadio? Senza contare che da come dici te, all aumentare degli stessi aumenta il costo hw ed il problema del ritardo dovuto ai registri.
Ultima cosa, non ho afferrato bene l’esempio di quando dividi il ns in .3 e .7. Aldilà della cifra in se, cosa intendevi?
@ReNeSiS
Se le sotto-operazioni non sono uniformi quella più lenta fa da collo di bottiglia al clock che si vede obbligato a viaggiare a 1/0.7ns = 1.4 GHz. Questo indipendentemente dal fatto che l’altra sotto-operazione impiega soltanto 0.3ns. L’altra operazione (che abbiamo detto impiega 0,3ns) potrebbe impiegare da 0 fino a 0.7 ns e non cambierebbe assolutamente niente dal punto di vista del clock massimo.
@pleg
Un bel mini ripasso di calcolatori mi serviva proprio. ;-)
Ora è ok, mi stavo perdendo su dettagli..
Dividendolo in 2 nell esempio lavoro a 1,4ghz in quanto viene chiaramente tenuto conto del tempo più altro per completare un operazione.
Quindi se impiegassero lo stesso tempo, le 2 parti lavorerebbero ambedue a 2ghz, rispetto al chip che prima della divisione avrebbe potuto lavorare solo ad 1 Ghz.
Corretto?
Un buon compilatore in teoria dovrebbe fare in modo che il codice eseguibile risulti composto per la maggior parte di parti “veloci” dico bene ?
@ ReNeSiS
Semplicemente, avere piu’ stadi (cioe’ suddividere il circuito in parti piu’ fini) significa poter aumentare la frequenza, e quindi (in genere) le prestazioni. E’ vero che aumenta il costo e la complessita’… ci sono compromessi da fare tra prestazioni e tutto il resto (ti rimando ai miei due articoli precedenti, dove metto proprio l’accento sui “compromessi” che vanno fatti nella progettazione delle CPU).
Per quanto riguarda “cosa si fa ad ogni stadio”: pensa a quei 6 stadi, e suddividili. Ad esempio il fetch prende 2–3 stadi (cioe’ 2–3 cicli di clock), perche’ non riesci ad accedere alla cache L1 in un solo ciclo di clock (di fatto, la cache e’ essa stessa pipelinizzata!).
Il decode anche prende parecchi stadi (magari anche 5… non so dirti il numero preciso), questo e’ vero per l’architettura x86 perche’ e’ cosi’ complessa (il “decode” di fatto deve prendere x86 e “trasformarlo” in una specie di RISC che poi viene eseguito internamente).
L’esecuzione stessa puo’ essere spezzata: ad es. potresti non riuscire a fare operazioni aritmetiche a 64 bit in un terzo di nanosecondo (quello che ti serve se vai a 3 GHz), e quindi devi spezzare le ALU su due o tre cicli di clock (ma ci puo’ essere una grossa penalita’ se lo fai perche’ non puoi piu’ eseguire le istruzioni aritmetiche back-to-back: di questo ne parlo nel prossimo articolo).
Eccetera.
Per la questione delle tempistiche, ha gia’ risposto Emanuele. Vorrei solo aggiungere che quando si progetta il circuito che va in ogni singolo stadio, questo non deve essere troppo lento (pena l’abbassamento del clock massimo)… ma neanche troppo veloce :) questo e’ piu’ difficile da capire, e’ una ragione strettamente circuitale (in termini tecnici: dipende dalla violazione del tempo di hold dei registri).
PS: si’ esatto, il punto del pipelining e’ poter aumentare la frequenza. Un altro modo di vederla, come cercavo di rendere pittoricamente nelle immagini, e’ sfruttare il “parallelismo temporale”, cioe’ piu’ istruzioni in-flight nello stesso istante.
@ D
Si’, l’interazione col compilatore e’ cruciale. Il compilatore cerca di creare un eseguibile che vada al meglio su una particolare architettura, se gli setti le flag opportune.
Ad esempio, per x86, si traduce nell’usare istruzioni semplici e usare il meno possibile tutte quelle istruzioni giganti (che vengono dalla preistoria di x86) che seguirebbero molto lentamente (perche; sono ad es. molto lente da decodificare).
Ma un compilatore in grado di realizzare un codice capace di lavorare egregiamente con una pipeline molto lunga è praticamente un prototipo di intelligenza artificiale. In altre parole troppi stadi di pipeline oltre ad essere costosi rischiano pure di non essere sfruttati a dovere
@ D
Si fa quel che si puo’ :)
Ci sono varie tecniche per tenere la pipeline piu’ piena possibile. Ovviamente il compilatore non puo’ fare miracoli (ad es. non puo’ sapere quanto ci mettera’ un load a restituire il dato, perche’ questo dipende da dove il dato si trova nella gerarchia di memoria, e questo non e’ noto a compile-time). Ma puo’ evitare di mettere le istruzioni in posti che _sicuramente_ creano bolle nella pipeline.
“(ad es. non puo’ sapere quanto ci mettera’ un load a restituire il dato, perche’ questo dipende da dove il dato si trova nella gerarchia di memoria, e questo non e’ noto a compile-time)”
Neanche se la macchina è super ottimizzata e quindi sono note le tempistiche di ogni componente ?
La compilazione con profiling può aiutare a conoscere le tempistiche di esecuzione delle istruzioni. Inoltre può migliorare l’esecuzione del codice nel caso di salti.
In certi casi si’, e’ possibile. Non si tratta di ottimizzazione, quanto di costruire l’intera processore in un certo modo. Ad esempio un processore potrebbe non avere cache ma avere solo DRAM on-chip, con una latenza di accesso fissa: in questo caso il compilatore potrebbe sapere quando un certo dato diventera’ disponibile, e regolarsi di conseguenza (mi vengono in mente certi media processors, e forse, se ricordo bene, il Cell).
Un’altra possibilita’ e’ che le cache possano essere (parzialmente) controllate dal programma stesso. Ad esempio Itanium ha delle istruzioni che danno dei “suggerimenti” al processore su dove dovrebbero venir messi certi dati (ad es. in L1, L2, L3, oppure sono dati che vengono usati una sola volta e possono essere buttati fuori dalla cache subito dopo essere stati usati, eccetera). In questo caso il compilatore non sa esattamente dove staranno i dati (il processore, a run-time, puo’ non rispettare quei “suggerimenti”) ma ha una buona probabilita’ di azzeccarci, e quindi fare ottimizzazioni.
@ olivobestia
Vero, se si fa branch prediction. In questo articolo non ho parlato della predizione perche’ sto facendo un ripasso dei concetti base. Ne parlero’ in futuro.
In Cell sono le SPE ad avere tempi di accesso al “Local Storage” ben definiti. La PPE, invece, no.
Grazie della precisazione.
Domanda probabilmente sciocca: ma internamente i vari stadi usano solo un ciclo di clock? Cioè sono in grado di leggere i dati dal buffer riempito dallo stadio precedente, fare l’elaborazione e scrivere il risultato nel buffer dello stadio successivo tutto in un solo ciclo?
@ Nessuno
Puo’ essere un po’ una questione di definizioni… ma diciamo di si’. Potremmo quasi dire che quella e’ la definizione di “stadio”: quello che fai in un ciclo di clock.
Prendiamo ad esempio la pipeline a 6 stadi che ho descritto prima. La ALU sta nello stadio di esecuzione, e in un ciclo di clock quello che succede (dal punto di vista circuitale) e’:
* i dati partono dai registri tra OF ed EX, un tempo di propagazione dopo l’arrivo del clock
* i dati arrivano alla ALU, insieme ai segnali di controllo che dicono alla ALU che operazione deve fare
* la ALU fa la computazione
* il risultato arriva ai registri tra EX e MEM, almeno un tempo di setup prima del prossimo clock
Se questo non e’ sufficiente, si puo’ ad esempio spezzare la ALU (anzi, tutto lo stadio EX) in due: adesso avremo due “sotto-stadi”, EX1 e EX2, ognuno dei quali esegue in un singolo ciclo di clock. Questo si chiama “super-pipelining”, nel senso che andiamo a spezzare su piu’ “stadi fisici” (cioe’ su piu’ cicli di clock) quello che sarebbe un singolo “stadio logico”.
Grazie della risposta, però mi sfugge come decoder e unità di storing possano fare tutto in un ciclo di clock.
Cioè, il decoder deve prendere l’istruzione, andare a recuperare gli operandi (se come detto gli stadi DC e OF sono insieme) prendere il risultato di questi, metterli al disposizione dello stadio EX e generare i relativi segnali di controllo.
Viceversa l’unità di storing deve prendere i dati + la destinazione, computare l’indirizzo relativo, mettere tali valori sui bus e attendere che l’operazione completi (ovviamente quest’ultimo passo è a carico del gestore di memoria/bus).
Così come sa possibile fare una moltiplicazione in un ciclo di clock (magari anche con ADD supplementare annessa).
Ovviamente spezzando è tutto possibile, ma a questo punto non si più parlare di “stadio” singolo, ma gli stadi di una pipeline diventano 8-10-12 anche solo per il modello “teorico a 5 stadi” come l’hai descritto tu…
Quindi la domanda è: è realmente possibile creare una pipeline a 5 stadi che faccia F,D,OF,EX,MA con ciascun passo (o stadio) eseguito in un solo ciclo di clock?
E’ una cosa che mi sono sempre chiesto e l’unica soluzione che ho trovato è che lo stadio deve essere fisicamente grande per fare tutto (tante parti che lavorano in parallelo con registri collegati da molti bus, si pensi solo al Program Counter che deve essere aggiornato mentre lo stadio OF e Memory Access operano contemporaneamente), cosa che certamente fa a botte con il fatto che queste pipeline “compatte” sono usate su micro piccoli.
Cercando in rete non ho trovato molta documentazione riguardo a questi concetti. E’ possibile avere qualche fonte che approfondisca la questione?
Grazie infinite
Dipende tutto da quanto e’ lungo, quel ciclo di clock :)
Se vuoi costruire una CPU che va a 4 GHz, allora certo devi spezzare ogni operazione su molti stadi (credo che il pentium4 avesse bisogno di circa 5 stadi solo per fare il fetch e la decodifica). Ma se vai piu’ lento, il tuo ciclo e’ abbastanza lungo da permetterti di fare tutto in un solo stadio. Quindi, dato che i micro in genere vanno a frequenze molto piu’ basse delle CPU, il loro ciclo e’ abbastanza da fare tutto.
Inoltre, devi considerare che la scala di integrazione di oggi e’ tale che una pipeline semplice come quella descritta occupa davvero poco spazio. A 40 nm posso mettere piu’ di 1 milione di transistor per millimetro quadrato, e vecchi processori (semplici come quello descritto) occupavano meno di centomila transistor… la dimensione non e’ assolutamente un problema.
Per venire ai tuoi esempi: il Fetch significa accedere (in genere) alla L1 istruzioni, quindi dipende da quanto e’ veloce la tua cache. La decodifica puo’ variare moltissimo: nel caso illustrato, con una ISA RISC, la decodifica e’ semplice (tutte le istruzioni sono lunghe uguali, il formato e’ uniforme) e si sbriga in fretta; accedere al register file vuol dire in pratica attivare i decoder che porteranno in uscita i dati richiesti; a quel punto i registri OF-EX devono solo latchare il valore.
Per le operazioni aritmetiche, e’ stato fatto talmente tanto lavoro negli ultimi 50 anni che sono note soluzioni estremamente complesse, astute e veloci. Ad esempio:
http://www.computer.org/portal/web/csdl/doi/10.1109/ARITH.1995.465374
http://arith.stanford.edu/snap.html
15–20 anni fa (!) gia si parlava di operazioni aritmetiche in meno di un nanosecondo, e oggi sono la norma.
Per lo store… quello e’ il punto piu’ critico. Se scrivi nella L1 dati, potresti cavartela in un ciclo di clock (se e’ abbastanza lento), ma se devi andare off-chi sicuramente ci metterai molto di piu’. Puoi risolvere con uno store buffer (tecnica usatissima), se no devi stallare la pipeline fino a che lo store non ha completato.
Considera comunque che il calcolo dell’indirizzo puoi eseguirlo nello stadio EX, e in MEM accedi direttamente alla cache, quindi si puo’ fare.