Nella seconda parte di questa rassegna sui branch predictor ho illustrato i fondamentali e gli schemi di base, che pur nella loro semplicità possono ottenere prestazioni relativamente elevate (anche superiori al 90%). Tuttavia i processori in generale, e quelli superscalari in particolare, possono ottenere grossi benefici da predittori ancora più precisi: ogni aumento di precisione può far sia aumentare le prestazioni (perchè si può estrarre parallelismo tra istruzioni in più blocchi base diversi) che ridurre il consumo energetico (perchè si eseguono meno istruzioni nel ramo sbagliato).
La letteratura in merito è sterminata e la ricerca nel campo continua, proprio perchè l’argomento è così importante per costruire processori ad alte prestazioni. In questa terza parte mostrerò alcune tecniche avanzate che permettono di sfruttare certe regolarità che sfuggono (o non vengono sfruttate in modo efficiente) dai predittori visti la volta scorsa, senza scendere molto in dettaglio in ognuno (sia perchè non è il mio campo, sia perchè a voler scendere in dettaglio seriverebbero qualche decina di articoli dedicati!)
Gli esempi sono presi da Shen, Lipasti, “Modern processor design – Fundamental of superscalar processors”, uno dei testi di riferimento fondamentali per i Computer Architect.
Gshare Predictor
Il predittore gshare è una variante del predittore basato sulla storia globale del salto (Global History 2-Level Predictor) visto nello scorso articolo. Questo predittore ha avuto un grande successo, essendo stato utilizzato in una forma o nell’altra in processori progettati da Alpha, IBM, Intel e AMD (cioè più o meno tutti!).
Il Global History 2-Level Predictor contiene una tabella di macchine a stati che generano la predizione di salto (la Pattern History Table) che viene indicizzata tramite una concatenazione della storia globale del salto (BHR) con parte dell’indirizzo del salto stesso:
Con l’aumento della frequenza di funzionamento dei processori si ha a disposizione sempre meno tempo per generare la predizione, che va generata il più in fretta possibile. Idealmente vorremmo generare una predizione ogni ciclo di clock con una latenza di un ciclo di clock: per un processore che gira a 3-4 GHz significa accedere al PC e al BHR, concatenarli, usare il risultato per accedere alla PHT, estrarre il valore dalla PHT e “manovrare” i MUX nella direzione prevista… in un paio di centinaia di picosecondi! C’è ben poco tempo da scialare!
Dato che la PHT è il pezzo di memoria più grosso del predittore, per farla veloce è cruciale farla piccola (SRAM più piccole sono più veloci da accedere, sia perchè l’indirizzo da decodificare è composto da meno bit, sia perchè le linee di interconnessione all’interno della memoria sono più corte). Ma una PHT più piccola ha meno informazione sulla storia dei salti (che porta a predizioni meno precise) e aumenta l’aliasing tra i salti, con possibile aumento di intereferenze distruttive e ulteriore perdita di precisione.
Possiamo ottenere prestazioni migliori mantenendo inalterato quasi tutto il design e cambiando solo la funzione di “fusione” del BHR col PC: invece di una concatenazione, possiamo fare uno hash dei due (di fatto uno XOR, che è molto veloce):
Uno hash ci permette di creare un indice più “significativo”, cioè che contiene più informazione, rispetto ad una concatenazione, perchè in ingresso alla funzione di “fusione” abbiamo più bit (ad esempio, avendo N bit di indice possiamo prendere N bit di PC e N bit di BHR, invece che X bit di PC e (N-X) bit di BHR). Questa semplice modifica aumenta la probabilità di avere meno interferenza e ci dà quindi più precisione.
Bi-Mode Predictor
La Pattern History Table vista finora è in sostanza una cache direct-mapped, ma senza tag per differenziare gli indirizzi (ed è per questo che è soggetta ad aliasing). Come per tutte le cache, i miss possono essere divisi in 3 categorie:
- compulsory (o cold) miss: la prima volta che incontriamo un salto non abbiamo storia su cui basarci e quindi non possiamo generare una predizione; questo per fortuna succede molto di rado, visto che in genere i programmi restano a lungo in una certa sezione di codice
- capacity aliasing: questo succede se la PHT è troppo piccola per il working set corrente, cioè la sezione di codice su cui stiamo lavorando ha più branch di quanti ce ne stanno nella PHT
- conflict aliasing: quello che si ha quando diverse combinazioni di Program Counter e BHR generano lo stesso indice
Per i cold miss l’unica cosa da fare è aggiungere degli hint da compilatore, in modo che la prima volta che un branch esegue la CPU ha già un valore più probabile della direzione che prenderà; questo però richiede il supporto dell’ISA. Per i capacity miss la soluzione è aumentare la dimensione della PHT, ma come visto prima aumentare la dimensione rende la PHT più lenta, e il risultato finale potrebbe essere un processore più lento invece che più veloce.
Per i conflict aliasing la soluzione standard nelle cache è aumentare l’associatività. Avere dei set richiede però di avere delle tag per distinguere i set: se anche avessimo solo 2 bit di tag, dato che le FSM nella PHT hanno in genere 2 bit significherebbe raddoppiare la dimensione della PHT! A questo punto sarebbe probabilmente più conveniente abbandonare le tag e semplicemente raddoppiare il numero di entry disponibili, per ridurre sia i problemi di capacity che di conflict.
Ma dato che stiamo parlando di branch predictor e non di cache normali, abbiamo a disposizione più spazio di manovra: quello che in effetti ci interessa non è diminuire l’aliasing, ma diminuire l’aliasing distruttivo! Se due branch vanno nella stessa direzione (entrambi presi o non presi) il fatto che mappino nella stessa entry nella PHT non modifica la precisione del predittore: questo è un caso di interferenza neutra (se non addirittura costruttiva: nel caso in cui i due salti si comportino allo stesso modo, possono contribuire entrambi al training dei bit di predizione, popolando le tabelle con dati validi più in fretta). Quello che ci interessa ridurre quindi è semplicemente l’interferenza distruttiva, cioè due salti che vanno in direzioni opposte e che mappano sulla stessa entry.
Possiamo sfruttare questa intuizione per costruire un oggetto del genere:
Invece di una singola tabella ne abbiamo due, PHT0 e PHT1, con stessa dimensione e indicizzate in modo gshare. In più abbiamo un choice predictor che decide quale delle due tabelle usare per generare la predizione finale, indicizzato invece usando solo il Program Counter. L’idea è quella di mettere tutti i salti a predominanza taken in una tabella e quelli a predominanza non-taken nell’altra, in modo da ridurre l’interferenza distruttiva: quando si verifica aliasing tra due branch è probabile che i due salti vadano nella stessa direzione, e quindi la predizione sarà comunque corretta.
Le regole di aggiornamento delle tabelle sono più complesse, e seguono una politica di aggiornamento parziale:
- la PHT selezionata viene sempre aggiornata con la vera direzione del salto, una volta che questo è stato eseguito; questo è il normale comportamento di una PHT
- la PHT non selezionata non viene aggiornata (in modo da eliminare l’interferenza distruttiva)
- il choice predictor è aggiornato con la vera direzione del salto a meno che la sua scelta fosse errata ma la predizione finale si sia rivelata comunque giusta (in questo caso è non c’è abbastanza informazione per capire qual è il modo migliore di aggiornare le tabelle, e quindi è meglio non aggiornare nulla)
Nonostante la quantità di memoria presente nel predittore sia triplicata il predittore non è molto più lento di prima, perchè entrambe le PHT e il choice predictor possono essere accedute in parallelo: l’unico ritardo addizionale è dato dalle interconnessioni più lunghe e dal MUX finale, ma è certamente inferiore a quello di una singla PHT di dimensioni triple.
Questo trucco permette di aumentare le prestazioni ad un costo contenuto ed è piuttosto popolare: è usata ad esempio nell’ultima architettura Intel, Sandy Bridge.
Gskewed Predictor
Invece di minimizzare l’impatto dell’aliasing raggruppando nella stessa PHT i salti che vanno (perlopiù) nella stessa direzione, il predittore gskewed cerca di minimizzare direttamente l’aliasing ma senza ricorrere a tag. L’idea è quella di avere predittori multipli con indici diversi e un voto a maggioranza:
Ogni PHT è indicizzata tramite una funzione diversa; le funzioni sono costruite in modo tale che se due indirizzi generano aliasing in una PHT, essi non vanno in conflitto nelle altre PHT: nel caso di aliasing negativo, questo può essere ignorato dal voto a maggioranza se le altre due PHT generano la predizione corretta:
Ci sono due diversi modi di aggiornare le tabelle una volta che la direzione del salto è nota:
- aggiornamento totale: tutte le PHT vengono aggiornate col risultato del salto
- aggiornamento parziale: se uan PHT ha predetto sbagliato, ma la predizione finale era giusta, quella PHT non viene aggiornata; in questo modo si permette a quella PHT di fornire la predizione giusta ad un altro branch che mappa nella stessa entry
Esistono molte varianti di questo schema, alcune delle quali analizzate qui.
Agree Predictor
La maggior parte dei salti è fortemente polarizzata, il che significa che le macchine a stati presenti nelle entry delle PHT (in pratica dei contatori a saturazione) sono in genere o a 00 o a 11; in altre parole, i salti fortemente presi cercano sempre di aumentare il valore del contatore fino al valore massimo, mentre i salti fortemente non presi cercano di diminuirlo fino a 0. Quando due salti che vanno in direzioni opposte mappano sulla stessa entry, il rischio è che:
- uno dei due salti è più “forte” dell’altro (cioè eseguito più spesso) e quindi imporrà il valore al contatore: questo significa che lui otterrà la predizione giusta, mentre il salto “debole” otterrà la predizione sbagliata
- i due salti sono “forti uguali” (ad esempio se eseguono in alternanza, primo l’uno poi l’altro in un loop): questo caso può essere ancora peggio, perchè il contatore potrebbe continuare ad oscillare tra gli stati 01 e 10 col risultato che nessuno dei due salti ottiene la predizione corretta
L’agree predictor cerca di risolvere questo problema reinterpretando la PHT: invece di generare la predizione, la PHT dice se è d’accordo o meno con la predizione fornita da un biasing bit, che dice semplicemente se il salto è fortemente preso o non preso:
Il biasing bit dipende unicamente dal salto e può sia essere generato dinamicamente che essere fornito dal compilatore (magari assistito da un profiler). La PHT decide se bisogna prendere la direzione data dal biasing bit, oppure l’altra.
In questo modo due salti con direzione opposta possono mappare nella stessa entry della PHT e ottenere comunque la predizione corretta, se sono entrambi fortemente polarizzati. Dato che la maggior parte dei salti lo è, la probabilità di conflitto è più bassa rispetto al caso in cui la PHT fornisce direttamente la predizione di salto, portando a predizioni più accurate.
Questo schema è stato usato nel PA-RISC 8700, con un biasing bit determinato a compile-time.
YAGS predictor
Il Bi-Mode Predictor separa i salti in due tabelle (presi / non presi) per ridurre l’aliasing distruttivo, mentre l’Agree Predictor sfrutta il fatto che la maggior parte dei salti è fortemente polarizzata.
Il predittore Yet Another Global Scheme (c’è chi ha senso dell’umorismo :) usa entrambe queste idee: usa il choice predictor del predittore Bi-Mode sia per generare la predizione di salto “di default” (come il biasing bit dell’Agree predictor) sia per accedere a due tabelle (la Taken Cache e la Non-Taken Cache) che contengono i salti che NON sono in accordo con la predizione di default, in modo da usare lo spazio nelle tabelle in modo più efficiente. In altre parole, il choice predictor fornisce la “regola”, mentre le cache forniscono le “eccezioni alla regola”.
Per farlo, però, è necessario aggiungere alle tabelle delle tag (anche parziali) in modo da distinguere i salti tra loro: a parità di spazio, quindi, queste tabelle contengono molte meno entry rispetto alle PHT del Bi-Mode Predictor.
Il predittore funziona in questo modo: il choice predictor viene acceduto tramite il solo indirizzo di salto (perchè dipende dal salto, non dalla sua storia) e produce la predizione principale. Se questa PHT predice Taken, allora viene consultata la Non-Taken Cache, con un indice che dipende sia dal salto che dalla sua storia (in modo gshare). Se c’è un tag match, allora la predizione “di default” viene scartata e viene usata la predizione fornita dalla cache. Il sistema funziona in modo analogo per il caso opposto.
Una volta che il salto è eseguito, le tabelle vengono aggiornate con lo stesso schema parziale del Bi-Mode Predictor.
Branch Filtering
Anche questo predittore sfrutta il fatto che molti salti sono fortemente polarizzati costruendo un filtro che filtri via questi salti polarizzati dalla PHT, che viene quindi usata solo per predire i salti meno polarizzati, riducendo l’aliasing.
Per ogni salto c’è un contatore che tiene traccia di quante volte il salto è andato nella stessa direzione. Quando il contatore satura al massimo il salto smette di aggiornare la PHT e la sua predizione viene fornita dal contatore stesso. Se la direzione cambia, il contatore viene resettato e il processo di addestramento ricomincia.
Questo sistema è utile per filtrare tutti quei salti che non vengono mai presi in condizioni normali (come i check delle condizioni d’errore) o quasi mai presi (condizioni di terminazione di cicli molto lunghi), per lasciare spazio nella PHT a tutti gli altri salti dal comportamento più complesso.
Alloyed History Predictor
I predittori usano dei meccanismi di pattern-matching per identificare comportamenti ripetitivi nei salti (il cosiddetto “contesto”) in modo da applicarli in futuro nel caso lo stesso pattern dovesse ripresentarsi. Ma qual è il pattern migliore? Il salto dipende dalla storia globale o locale? O tutte e due? O dipende dal modo in cui hanno eseguito i salti vicino a lui? Quanti bit di storia bisogna mantenere?
I predittori visti finora cercano di ridurre il problema dell’aliasing negativo, ma usano tutti tecniche di global/local history o gshare per l’indirizzamento nella PHT. Altri predittori cercano di construire un contesto migliore accumulando più informazione di tipo diverso. Ad esempio, il predittore alloyed history utilizza sia la storia globale che la storia locale del salto (merged history) per generare l’indirizzo di accesso alla PHT:
Il meccanismo a due livelli è uguale a quello dei global/local history 2-level predictors, ma usando entrambi i tipi di storia del salto allo stesso tempo (forniti dal BHR per la storia globale e dal BHT per la storia locale). Schemi simili posso essere applicati per costruire predittori mshare (merged history gshare) o mskewed (merged history gskewed).
Path History Predictor
Esistono casi in cui percorsi di codice diversi condividono un tratto della stessa sequenza di istruzioni, compresi i branch e la loro storia, prima di tornare a divergere. Consideriamo questo esempio:
Il programma può raggiungere il salto nel blocco D sia attraverso il cammino ACD che attraverso il cammino BCD. A seconda del percorso seguito il salto valuterà in modo diverso, ma sia l’indirizzo che la storia di salto {taken, taken} sono gli stessi. Se i due percorsi mappano nella stessa entry nella PHT essi interferiranno distruttivamente, riducendo drasticamente l’efficienza di predizione del salto in D.
Per risolvere questo problema, il Path History Predictor mantiene nel suo Branch History Register (anzi, Path History Register) non il risultato degli ultimi n salti, ma k bit dell’indirizzo degli ultimi n salti, in modo da identificare il cammino seguito; questi vengono combinati con l’indirizzo del salto corrente per generare l’indice a cui accedere nella PHT e generare la predizione:
Ad ogni nuovo salto, i k bit del salto più vecchio escono dallo shift register e i k bit del salto più recente vengono accodati.
Se per generare l’indice vengono usati m bit dell’indirizzo del salto corrente, la PHT deve avere 2^(nk+m) celle: la memoria necessaria per la PHT cresce molto rapidamente coi valori di n, k e m. Per ridurre la dimensione della PHT, invece di usare la concatenazione possiamo usare un qualche tipo di hash (come per gshare) per comprimere il numero di bit e riportare la quantità di memoria usata a dimensioni accettabili.
Loop counting predictor
I loop sono una delle strutture di controllo più comuni e una buona parte di essi eseguono per lo stesso numero di iterazioni ogni volta che sono chiamati. Questo rende molti loop completamente prevedibili, eppure nessuno dei predittori visti finora fa un buon lavoro con essi. Il problema è che avendo a disposizione n bit di storia è possibile catturare solo loop che eseguono per n cicli o meno, e n deve essere piccolo altrimenti le dimensioni della PHT (che cresce come 2^n) diventano proibitive. Inoltre, il comportamento del loop è “spalmato” su molte entry nella PHT (fino ad n), che saranno soggette ad aliasing con altri branch, facendo perdere precisione nella predizione di qualcosa che è spesso molto regolare (e quindi predicibile al 100%).
Questo è vero a meno che non si usino quegli n bit per contare esplicitamente le iterazioni del loop: in questo caso, n bit possono contare fino a 2^n cicli; inoltre, se usiamo questo predittore per analizzare solo i loop e nient’altro, la probabilità di aliasing è molto ridotta. Un loop branch è definito come un branch che esegue per n volte in una direzione ed 1 volta nella direzione opposta, per poi ripetersi (assumendo che sia regolare). Questa struttura permette di catturarne il comportamento in modo efficiente:
Il campo limite contiene il numero di iterazioni che il loop ha eseguito la volta precedente; se il loop è regolare (come ad esempio negli algoritmi di moltiplicazione tra matrici, o in algoritmi di grafica dove la stessa operazione viene eseguita 4 volte per ogni pixel per le componenti {R, G, B, A}, e infiniti altri casi) e il numero di iterazioni è inferiore a 2^n, questo predittore avrà una precisione del 100%: è capace di predire tutte le volte che il loop è preso e anche la condizione di uscita.
Una cosa curiosa da notare è che, usando questo predittore, i loop eseguono… due volte! Consideriamo questo esempio:
for( int i = 0; i < n; ++i ) { ... }
Il loop aumenta ad ogni iterazione la variabile i: l’operazione viene eseguita nello stadio di esecuzione in una delle ALU intere, interessa i registri architetturali, ed è ovviamente visibile al software. Contemporaneamente, il predittore sta eseguendo lo stesso ciclo, aumentando la sua copia shadow del contatore i, ma in testa alla pipeline (intorno allo stadio di fetch) in modo nascosto al software. In un certo senso stiamo spostando l’operazione sul contatore del loop dallo stadio di esecuzione allo stadio di fetch, in modo da ridurre la latenza con cui la condizione di controllo del loop diventa nota alla logica che deve accedere alla cache per prelevare le istruzioni successive.
Questo predittore ha fatto al sua comparsa nelle CPU col Pentium-M. Dal Core2 Intel ha introdotto il Loop Stream Detector (LSD per gli amici :) che fonde l’idea del Loop Counting Predictor con una cache di microistruzioni già decodificate (come fanno certi DSP) col doppio fine di aumentare le prestazioni e ridurre il consumo di energia, spegnendo gli stadi di fetch e decode quando il processore può essere alimentato con u-ops direttamente dal LSD.
Questo predittore funziona molto bene per loop regolari, ma molto male per branch generici. È utile se usato non da solo ma insieme ad altri predittori.
Conclusione
In questo articolo abbiamo visto alcune tecniche più sofisticate che vengono utilizzate in processori reali per costruire branch predictor molto accurati. Nel prossimo articolo illustrerò dei meccanismi usati per combinare queste tecniche per costruire predittori ibridi ancora più precisi.
L’articolo è molto interessante, ma l’argomento è talmente complesso che poche righe per ciascun predittore non fanno giustizia.
Sono più i dubbi e le domande che le cose che ho realmente capito, quindi mi sa che comprerò un libro per approfondire la cosa :-)
Ovviamente non è colpa tua, ma del mezzo “blog” che è troppo stretto per contenere agevolmente la mole di contenuti e dettagli che sarebbe necessaria :-)
Articolo(/i) interessantissimo(/i), in effetti ero curioso su alcuni dettagli che non ho trovato sui libri che ho letto sull’architettura dei calcolatori.
PS: che programma usi per fare gli schemi? sembra LaTeX a vedere come vengono fuori, potrebbe tornare utile…
PPS: complimenti per il curriculum! Ci sono molte delle cose che piacerebbe fare anche a me… (studio Ingegneria Elettronica a Bologna).
Come sempre, un articolo semplice e interessante, grazie! :)
@ Arunax
Si’ uso TikZ e LaTeX, e’ pesante ma potente :)
@pleg:
Domanda: grazie “anche” ai tuoi articoli, mi sto appassionando sempre più all’elettronica digitale e sto costruendo una trainer board basata su Z80 per esercizio (e mi diverto come un bambino in un negozio di caramelle!).
Lo step successivo sarà implementare vari meccanismi complessi che, per forza di cose, non potrò costruire tramite logica cablata e componenti standard ma dovrò affidarmi ad un linguaggio di descrizione hardware (sto studiando il VHDL). Secondo te, per un hobbista come me con conoscenze basilari di elettronica e avanzate di informatica, quale sarebbe il grado di difficoltà nell’implementare un design completo di una CPU con caratteristiche diciamo “moderne”?
Mi spiego meglio: voglio studiare le architetture in modo approfondito, e per fare ciò vorrei anche implementare personalmente le varie tecniche studiate, appunto tramite una devboard basata su FPGA. Secondo te quale sarebbe il picco massimo di complessità che un hobbista potrebbe progettare in solitaria?
Intuitivamente mi butterei su una struttura RISC, sicuramente più semplice da progettare. Ad esempio i meccanismi che hai presentato, come l’esecuzione out-of-order o i sistemi avanzati di branch prediction, quanto sono complicati da implementare in concreto?
Forse sono domande un po’ strane e difficili da rispondere, ma io le butto lì, visto che domandare è gratis :-D
@Antonio
Guarda caso, ne sto costruendo uno anche io come progetto per la maturità :)
Se vuoi, sul forum di hwupgrade avevo aperto un thread dove discutevamo di una nuova architettura per cpu, ed eravamo andati avanti molto a parlare, con Cesare Di Mauro che aveva anche postato un’intero set di istruzioni :D
Interessante, magari gli butterò un occhio, anche se non amo particolarmente il forum di hwupgrade. Sono iscritto da tempo, ma ho smesso di partecipare attivamente perchè c’è (o almeno c’era, non so adesso) un po’ di “inquinamento” a causa di decine e decine di utenti completamente irrispettosi delle basilari regole della netiquette.
Nel forum di programmazione la netquitte viene sicuramente fatta rispettare; io, infatti, frequento soltanto quello ormai.
Anzi, occhio a non esagerare, perché rischi pure il ban (l’ultimo giusto ieri, se non ricordo male: uno aveva totalmente sbarellato augurando persino la morte agli altri utenti che “non l’avevano capito”. :asd: ).
Sorry per il ritardo nelle risposte, ero “in-flight” (come un’istruzione :)
@ TheKaneB
Son contento di stimolare interesse con questi articoli!
Implementare in concreto questi meccanismi puo’ essere estremamente complesso. Ad esempio, credo che nemmeno il progetto OpenRISC (http://opencores.org/openrisc,architecture) sia superscalare OoO. Serve un sacco di esperienza e di tempo per riuscire a costruire tutti i meccanismi nel modo giusto.
Io procederei per step: una volta scelta la tua ISA comincerei forse addirittura con un design non-pipelined, una istruzione che attraversa l’intera CPU in per ciclo di clock, e scriverei la prima versione di tutte le unita’ (datapath, memory management, cache, tlb, I/O, eccetera). Poi proverei a pipelinizzare il design, magari con una semplice pipeline a 5 stadi o qualcosa del genere. E solo una volta che tutti i blocchi sono ben chiari e l’architettura delineata comincerei a pensare come rifare la pipeline in modo superscalare OoO.
E’ qualcosa che avrei sempre voluto fare :) ma non ho mai avuto neanche lontanamente il tempo necessario.
Per il VHDL… non vorrei cominciare una guerra di religione :) ma a me il VHDL non piace, e’ mostruosamente verboso, preferisco il Verilog.
@ Z80Fan , Cesare
Ho letto tutto il thread… interessante, siete piu’ andati avanti? Avete preso in considerazione di progettare l’ISA in modo che sia possibile estenderla in seguito con istruzioni vettoriali (stile Larrabee ad esempio)?
Non siamo più andati avanti. Ho lasciato appositamente dello spazio (se non ricordo male 24 bit dell’opcode a 32 bit) proprio per poter aggiungere istruzioni per un’estensione SIMD, ovviamente in stile Larrabee visto che sono rimasto particolarmente affascinato dal progetto di Intel.
Ho lasciato anche da definire alcuni dettagli della modalità supervisore (anche se alcune istruzioni “classiche” sono presenti: RESET, BRKP, TRAP, RTE, ecc.), perché mi sono concentrato sullo user mode.
Seguendo il progetto Natami e le discussioni col progettista della CPU ho anche preso spunto per delle modifiche alla mia ISA, in modo da raddoppiare i registri dati (da 8 a 16; anche se i primi 8 sarebbero “più general purpose” rispetto agli altri 8), separandoli nettamente da quelli indirizzo (il cui utilizzo sarebbe limitato, appunto, a mantenere e manipolare puntatori, con apposite istruzioni ed eventuali semplici ALU dedicate).
Quindi in totale ci sarebbero:
– 16 registri dati;
– 8 registri indirizzo;
– PC, SP, SR, FP (Frame Pointer);
che sono un buon numero per un’architettura, penso in grado di soddisfare le esigenze più comuni, mantenendo al contempo un’elevata densità del codice.
Gli opcode più frequenti, infatti, sono a 16 bit; quelli più generali a 32 bit, ma entrambi con eventuali extension word multiple di 16 bit. In ogni caso la lunghezza totale dell’istruzione si può calcolare subito leggendo 32 bit, a differenza di 68000 e, soprattutto, x86, in modo da facilitare l’implementazione del decoder.
Ci sono alcune proprietà dell’ISA che ho voluto mantenere per singola istruzione:
– massimo 3 registri dati letti;
– massimo 2 registri indirizzi letti;
– una sola lettura per l’Effective Address (memoria o registro) sorgente;
– una sola scrittura per l’Effective Address di destinazione.
Non è possibile, quindi, leggere o scrivere due o più valori in memoria con la stessa istruzione (cosa che, invece, possono fare 68000 e x86).
Vediamo se in estate riesco a trovare un po’ di tempo per rivedere l’ISA aggiungendo quegli 8 registri dati. Così faccio anche contento Z80Fan, che voleva assolutamente almeno 16 registri dati. :D
Però per l’implementazione in Verilog o VHDL non se ne parla: non mi sono mai cimentato e mi mancano proprio le basi.
Al più posso realizzare un emulatore in Python, come ha fatto il buon Mirco col PDP-8, per verificare se l’ISA regge e poterci comunque smanettare un po’, scrivendo anche una batteria di test per verificare formalmente che il processore funzioni correttamente in tutte le sue parti.
Eh eh lo so’ ho nominato Larrabee apposta :) e devo dire che era sembrato molto interessante anche a me. Una ISA vettoriale molto pulita.
Per i registri in effetti 8 mi sembrano pochi, ma non ho esperienza diretta, parlo piu’ per sentito dire — quello che ho sentito e’ che ISA (specie RISC) piu’ moderne hanno una cifra di registri, anche 64, mentre Itanium ne ha 128 (che li usa in modo interessante, in modo wrap-around per cercare di non sovrascrivere i registri usati nelle funzioni precedenti a quella in azione, con un register spill automatico in hardware). Penso che almeno 16 siano una buona cosa.
Ho letto delle istruzioni a 16-32 bit e l’idea mi piace, io avevo pensato (per i fatti miei, un po’ di tempo fa) ad una codifica termometrica per codificare il numero di byte dell’istruzione in testa all’istruzione stessa, es:
10xxxxxx = istruzione a 1 byte
110xxxxxyyyyyyyy = istruzione a 2 byte
1110xxxxyyyyyyyyzzzzzzzz = istruzione a 3 byte
… eccetera, in modo da poter avere un numero qualsiasi di byte estendibile in qualsiasi momento successivo. Ma la tua idea mi piace, e’ piu’ semplice. Domanda: non ho capito, ma l’istruzione potrebbe avere campi addizionali al di fuori dei 32 bit? Es. se devo avere un indirizzo (o un immediate) a 64 bit, hai un’istruzione a 32 bit seguita dai 64 bit del campo? In modo da poter avere istruzioni piu’ lunghe, ma decodificabili leggendo sempre e soltanto 32 bit?
Per il resto, credo che comunque per una qualsiasi architettura sia necessario scrivere prima il simulatore (emulatore? boh non ho mai capito la differenza :) comportamentale per verificare la correttezza, che serve poi anche per verificare l’hardware (il codice RTL). Es. noi in azienda facciamo cosi’, prima la divisione Architecture scrive il modello funzionale di tutta la baracca in C++ (ogni minima feature), che poi si usa come modello contro cui verificare il codice RTL scritto dagli Hardware Guys.
Insomma, volevo dire, una volta che hai scritto il simulatore e definito tutti i dettagli, ti serve solo uno schiavetto che traduca in RTL :)
(la codifica termometrica ha il vantaggio che e’ esntensibile a qualsiasi numero di byte in un secondo momento, e che usa piu’ bit per le istruzioni piu’ lunghe e meno per quelle piu’ corte, salnado spazio la’ dove e’ necessario. Certo pero’ se hai istruzioni di 20 byte e devi decodificare 21 bit in testa all’istruzione per scoprirlo, potrebbe venirti un cono di logica un po’ grosso per essere davvero veloce :)
@Pleg: non mi interessa inventare una mia ISA, anche perchè non ne sarei capace. Preferisco prendere un’ISA esistente e progettarne l’implementazione. Come target per i primi esperimenti penso di implementare un qualche tipo di RISC, ad esempio un sottoinsieme dell’ISA di ARM (il solo Thumb per esempio) perchè lo conosco già nel dettaglio e so quali sono i suoi punti di forza e i suoi difetti.
Progettare “anche” l’ISA aggiungerebbe un’ulteriore livello di difficoltà che non mi sento di affrontare per un progetto hobbistico :-)
Per il resto seguirò il tuo consiglio: implementazione triviale all’inizio, pipeline in order in un secondo momento, ed eventualmente in seguito (se tutto dovesse funzionare) proverei ad andare ancora più a fondo con le tecniche più moderne.
ah… per quanto riguarda il VHDL vs Verilog, io sono un programmatore professionista, per me un linguaggio vale l’altro, non ho gusti di tipo religioso ma imparo a maneggiare gli strumenti che mi servono in relazione al tipo di lavoro che devo fare :-)
Al momento sto studiando il VHDL e mi sembra adeguato per lo scopo, quindi penso ormai di andare fino in fondo con questo linguaggio. Il Verilog lo studierò in un secondo momento.
Per quello che ho potuto vedere sin’ora, studiare un linguaggio HDL è relativamente semplice rispetto alla mole di linguaggi di programmazione veri e propri che ho studiato fin’ora, si padroneggiano in un tempo decisamente inferiore rispetto a mostri quali il C++, che tutt’oggi continuo a studiare nonostante abbia passato gli ultimi 4 anni a sfornare da .5k a 3k linee di codice C/C++ al giorno :D
Si’ i linguaggi HDL non sono difficili in se’, l’unica cosa e’ che bisogna capire quello che poi vanno a sintetizzare — come quando scrivi software devi tenere d’occhio quello che poi succedera’ sulla macchina vera e propria (utilizzo delle unita’ funzionali, pattern d’accesso alla memoria, eccetera) quando scrivi HDL devi tenere d’occhio l’hardware che poi il sintetizzatore andra’ a creare, es. fare una operazione floating point di tanto in tanto in un programma non costa niente, chiedere al sintetizzatore di generare un moltiplicatore floating point e’ la fine (non ce la fa nemmeno, in genere istanzia dei blocchi gia’ fatti… se ce li hai, e occupano una cifra di area di silicio!).
certo, il concetto è chiarissimo :-)
@pleg: infatti. La mia difficoltà non è imparare un nuovo linguaggio (qualche tempo fa ho anche dato un’occhiata al VHDL del Minimig, e mi sembra veramente molto semplice), ma… tutto il resto. :/
Purtroppo, pur avendo un diploma di automatica elettronica, l’elettronica non è mai stato il mio forte, a causa di un professore che me l’ha letteralmente fatta odiare (è stata l’UNICA volta nella mia vita che sono dovuto andare, in terza ITIS, per due mesi a lezioni private, da un professore che finalmente spiegava e mi faceva capire le cose).
Se mi parlate di analogica imbraccio il fucile a pompa di Doom. :D
Riguardo alla codifica termometrica (finalmente so come si chiama!), l’avevo tenuta in considerazione, ma non mi permette di sfruttare in maniera efficiente lo spazio degli opcode. La cosa mi fa un po’ sorridere, perché l’avevo utilizzata inconsapevolmente la prima volta quando, a 12 o 13 anni (adesso non ricordo bene), avevo progettato l’ISA del mio computer a 1024 bit… :D
Tornando agli opcode, forse è un retaggio del 68000, ma non parto mai da una dimensione di 8 bit: il taglio minimo che scelgo è 16 bit. A mio avviso rappresenta un buon compromesso, perché avere a che fare con un certo numero di registri ti costringe poi facilmente a dover ricorrere a byte addizionali da utilizzare, facendo allungare in ogni caso le istruzioni. Mi sembra che anche su x86 la dimensione media superi tranquillamente i 2 byte. Con 16 bit (e istruzioni allineate ai 16 bit) c’è anche il vantaggio di poter codificare i salti relativi in maniera più compatta (proprio perché spesso le istruzioni occupano 16 bit, avvicinandosi quindi alla media).
Riguardo alle tue domande, hai centrato perfettamente il punto. 16 o 32 bit sono la dimensione usuale dell’opcode, a cui possono seguire eventuali word a 16 bit per indicare una o più “extension word” (usate per specificare i dettagli degli indirizzamenti più complessi: registro indirizzi base, registro dati per l’indice, fattore di scala, e offset), indirizzi assoluti (a 64 bit, ma anche corti, a 32 bit), e valori immediati.
In ogni caso per determinare la dimensione totale dell’istruzione è sempre sufficiente leggere i primi 16 o 32 bit; anzi, diciamo che puoi leggere sempre i primi 32 bit e al più ignori gli altri 16 bit letti.
Questo vale in ogni caso, anche quando c’è un’istruzione che permette di indirizzare due valori in memoria (sorgente e destinazione): l’opcode porta sempre con sé tutte le informazioni necessarie per capire quante word a 16 bit sono eventualmente richieste per l’operando sorgente, e quante per quello di destinazione.
Col mio schema le istruzioni potrebbero, quindi, essere più lunghe di 16 byte (ad esempio, opcode a 32 bit + indirizzo assoluto a 64 bit + valore immediato a 64 bit), ma si potrebbe anche imporre un limite di 16 byte massimo. Non so quali problemi possa comportare avere istruzioni più lunghe di 16 byte (in realtà si lavora sempre per word di 16 bit; quindi le istruzioni occupano da 1 a 8 word; oppure fino a 10 word se non poniamo alcun limite alla loro lunghezza).
Sui registri, penso ci sia da fare qualche chiarezza. In realtà la mia prima ISA non ne aveva soltanto 8. 8 sono quelli per i dati, e altri 8 per i soli indirizzi. Quindi sono 16 in tutto, ma non “general purpose”, visto che sono strettamente specializzati. Poi ci sono PC, SP, SR e FP che sono separati e che, quindi, “liberano” gli altri 16 da funzionalità che in altri processori ne consumano, invece, qualcuno (vedi ARM, col PC, SP e FP; e con SR nel caso dell’architettura v1, “incorporato” nel PC).
La seconda versione che ho in mente permette di utilizzare un trucchetto per “liberare” 3 bit nella codifica dell’Effective Address, e poterli quindi utilizzare per mappare altri 8 registri dati. Quindi in totale ci sarebbero 16 registri dati (8 + 8) e 11 indirizzi/puntatori (8 + PC + SP + FP), che mi sembra un buon numero.
Si potrebbero anche aumentare i registri dati e indirizzi sfruttando il meccanismo delle register window di SPARC o Itanium, ma francamente la mia ISA è di tipo CISC e gli altri due sono di tipo RISC: non vorrei che venisse fuori un novello Frankenstein. :D
Anche perché si tratta di due filosofie completamente diverse; la mia ISA fa molto uso di indirizzamenti verso la memoria (e permette, quindi, di evitare molto l’uso dei registri o di trovare in ogni caso un “appoggio” nella memoria in caso ne servano di più, lasciando alla cache dati l’onere di ammortizzarne il costo rispetto al più veloce accesso al register file). SPARC, Itanium, e i RISC in generale funzionano in maniera diametralmente opposta, cercando di utilizzare quanto più possibile i registri.
Riguardo a simulatori ed emulatori, tante volte i due termini si usano in maniera intercambiabile (lo faccio spesso pure per semplificare il discorso). Il primo si usa quando l’applicazione è in grado di riprodurre esattamente il funzionamento del componente (anche dell’intera macchina), quindi compreso ciò che succede anche a livello della pipeline (quali risorse vengono utilizzate in un determinato momento, ma anche i cache miss, i data miss, branch miss, ecc.) e il tool riporta poi delle statistiche apposite.
Il secondo lo si usa quando questo livello di dettaglio viene ignorato; quindi, ad esempio, ci si occupa di eseguire l’istruzione LDA ($FE),Y ottenendo soltanto il risultato desiderato, senza badare di simulare al funzionamento del processore ciclo di clock per ciclo di clock durante tutta l’esecuzione dell’istruzione (al più si tiene conto di quanti cicli di clock avrebbe “consumato”).
Per problemi di compatibilità alcuni emulatori mettono a disposizione una modalità di esecuzione cosiddetta “cycle-exact”, che modella il funzionamento dell’intera macchina ciclo per ciclo, appunto, rendendoli simili ai simulatori. Qui il confine fra i due si assottiglia molto, ma a mio avviso la differenza rimane marcata perché un simulatore non deve soltanto riprodurre il comportamento (“input” e “output”, più che altro) della macchina ciclo per ciclo, ma raccogliere anche tutta una serie di statistiche che aiutano a capire come si sono comportate tutte le varie unità funzionali durante l’esecuzione di un particolare tipo di codice (ad esempio, è stata stressata di più la cache dati, o il register file, ecc.) e a “prendere provvedimenti” se necessario; tutte cose che non servono a un emulatore, il cui obiettivo rimane la compatibilità.
Comunque potremmo intavolare una serie di articoli sulla progettazione di un processore, partendo magari da uno molto semplice, e facendo vedere come dalla stesura dell’ISA si arrivi alla sintesi in VHDL o Verilog, e poi all’esecuzione in un simulatore, provando poi ad arricchirne l’implementazione mettendo via via in pratica quanto già scritto negli articoli su pipeline, cache, branch prediction, ecc. O:-)
@Pleg
Io non ho più risposto al thread per via di numerosi impegni (oltre al lavoro per gli esami di maturità) che mi hanno bloccato tutti i progetti a cui lavoravo; però ho sempre il file di testo con tutte le istruzioni sul desktop e di tanto in tanto aggiungo qualche istruzione :)
Visto che avete citato Larrabee, non ho presente il formato delle sue istruzioni, ma anche nella mia ISA (che, a differenza di quella di Cesare, ha sempre lunghezza minima di 32bit) c’è una quantità di spazio incredibile che faccio fatica a riempire ;)
Come simulazione io pensavo di usare l’ottimo simulatore Hades, che ha l’unico svantaggio di essere completamente visuale (si lavora come un CAD); implementare queste cose avanzate sarà un suicidio :D
@ Cesare
Capito. Limitare le istruzioni+estensioni a 16 byte (e allineate a 16 byte) puo’ essere comodo: le dimensioni delle cache line sono in genere nel range 16-64 byte, puoi prendere una cache line ed essere sempre sicuro che ci sia almeno un’istruzione e che l’istruzione parta sempre dall’inizio della CL, che semplifica il decoder (sia perche’ non devi prendere piu’ di uan cache line per decodicicare un’istruzione, sia perche’ sai per certo dove comincia e non la devi andare a cercare, come fa x86). Inoltre mi pare che le RAM rispondano con blocchi da 128 bit o quantita’ del genere, quindi se volessi implementare il tuo processore su una FPGA sei facilitato, sai che ogni accesso alla RAM ti resituitsce 16 byte, che e’ una cache line, che ha un’istruzione, che parte dall’inizio: piu’ facile di cosi’ :)
> la mia ISA fa molto uso di indirizzamenti verso la memoria
> (e permette, quindi, di evitare molto l’uso dei registri o
> di trovare in ogni caso un “appoggio” nella memoria in caso
> ne servano di più, lasciando alla cache dati l’onere di
> ammortizzarne il costo rispetto al più veloce accesso al
> register file).
Qui non sono sicuro di avere capito, immagino tu voglia utilizzare molti indirizzamenti verso la memoria per ridurre la dimensione del codice (per non dover avere istruzioni dedicate a fare il load e store esplicito tra memoria e registri) e per risparmiare registri architetturali, giusto? Perche’ alla fine pero’ quelle istruzioni dovranno essere “spezzettate” all’interno del core, e il decoder dovra’ generare una sequenza di microistruzioni per eseguirle. Esempio, una somma che prende due operandi dalla memoria e scrive il risultato in memoria dovra’ essere trasformata in due load, seguita da una istruzione alu, seguita da una store, facendo uso di qualche registro di appoggio interno tipo registri rinominati (trasparente all’ISA).
Inoltre, non so bene come si faccia a calcolare le dipendenze tra istruzioni nel caso i registri non siano scritti esplicitamente — e’ per questo che RISC usa load/store + molti registri, semplifica molto la vita (voglio dire, posso usare load forwarding, ma costa). Non vorrei dover dipendere troppo dalla cache a spese dei registri, perche’ la cache e’ gia’ in genere stressata di suo ed e’ anche piu’ lenta a rispondere, oltre al fatto che accedere alla cache costa piu’ energia che accedere ai registri.
Progettare una piccola CPU in RTL e’ qualcosa che mi ha sempre affascinato, ma al momento sto lavorando ad un altro progetto “hobbistico” che mi prende tutto il tempo disponibile… e ne avro’ ancora per qualche anno temo :) ma e’ qualcosa che prima o poi vorrei fare!
@ Z80Fan
Ho dato un’occhiata a Hades, il mio problema e’ che sono allergico alla roba visuale :) sono abituato ad avere C/C++ per l’architettura (simulatore/emulatore) e Verilog/VHDL per il resto, tenuto tutto insieme con Perl :) piu’ un altro set di linguaggi e tool per il flusso di design hardware (synthesis, physical design, verification, ECO, …)
Altro domandone da paura: Altera Quartus, Xilinx ISE, OrCAD (supporta il VHDL? boh), altro?
Credo che qualsiasi tool supporti sia VHDL che Verilog. Io qualche anno fa che ci avevo giocato all’universita’ avevo usato Xilinx ISE WebPack, era gratis e ti dava abbastanza tool per l’intero design flow. Immagino che anche Altera abbia qualcosa del genere, ma non conosco. Alla fin fine non credo che (dal punto di vista dell’ hardware) faccia molta differenza fra le due.
Io userei sempre il tool della casa di cui hai la FPGA, quindi no orcad (che tra l’altro non so nemmeno se possa fare una cosa del genere, l’ho sempre e solo visto usare per fare roba su scheda).
OrCAD lo userei per simulare appunto il resto della scheda, in caso di design che comprendano FPGA + periferiche di contorno.
Comunque, male che vada, posso sempre fare la sintesi del VHDL/Verilog con Xilinx Webpack ISE (oppure Quartus Altera), poi esportare la netlist sintetizzata, importarla in OrCAD come macroblocco funzionale e attaccarlo nel progetto della scheda.
Ovviamente se ci fosse qualcosa di più integrato sarebbe anche meglio, ma in assenza di ciò posso armarmi in questo modo :-)
Ma vuoi progettare anche la scheda !? Li’ si va sul pesante, eh :) quello che ti serve e’ che la scheda di sviluppo supporti un tot di bus e connettori standard, e poi connetti le periferiche a quelli (es. potrebbe avere gia’ dei connettori USB, ethernet, VGA/DVI per il monitor, i2s per l’audio, i2c che fa sempre comodo per tutto, spi, qualche GPIO, …). Poi si tratta di pilotare quei bus dall’interno della FPGA mandando i segnali sui pin d’uscita giusti (c’e’ un file apposta per elencare gli I/O). In alcuni casi ci sono blocchi prefabbricati, ma in genere costano (tipo comprare il controller ethernet, il controller video ecc. come “soft core”, che istanzi nel tuo design e vengono sintetizzati insieme al resto della tua roba).
Si, sto per comprare una scheda di sviluppo con tutto già integrato (modello medio-base con Xilinx Spartan 3 da 1200k gates, circa 200 euro di scheda), ma in seguito cercherò di andare oltre. Le cose mi piace studiarle bene :-)
Sono diventato un professionista del software studiando e lavorando sodo… adesso mi piacerebbe diventare un professionista dell’hardware :-)
@Pleg:
Sì, ma solo per operazioni “one shot”. Mi spiego meglio. Se devo effettuare un’operazione una sola volta e non m’interessa il risultato, non provvedo a caricare tutti gli operandi in memoria. Cerco di caricare solo quelli strettamente indispensabili, e il resto lo lascio all’unità di load e a quella di store.
Ad esempio, se in mezzo al codice trovo: a = b + c
e il valore di c e di a non verrà più toccato in quella funzione, mentre b sì, allora genererò qualcosa del tipo:
move.q b,r0
add.q c,r0,a
quindi senza “sporcare” un altro paio di registri.
Sì, chiaro. Magari per una prima implementazione senza core RISC si potrebbe evitare, ma per ottenere prestazioni migliori la strada degli x86 è obbligatoria, e lì qualche problema c’è per i dati “intermedi”, appunto.
E’ proprio per evitarlo che si fa uso di modalità d’indirizzamento verso la memoria.
Nell’esempio di sopra, con un RISC senza load forwarding avrei qualcosa del tipo:
load b,r0
load c,r1
add r0,r1,r2
store r2,a
Dove l’istruzione add risulta bloccata perché dipende da r0 ed r1, e la store dal risultato della add.
Il pezzo di codice della mia architettura ha, invece, una sola dipendenza. Una volta “sbloccata” quella, l’istruzione ha tutto ciò che le serve per essere eseguita e finalizzata. Inoltre c’è il vantaggio di aver usato un solo registro anziché 2 (e il codice rimane più denso: 4 + 8 byte contro i 16 normalmente richiesti da un’architettura RISC).
Col load forwarding a disposizione, con la mia ISA le due istruzioni potrebbero essere eseguite immediatamente (supponendo di avere a disposizione una superpipeline), mentre nel caso di un RISC soltanto per le prime 3 ciò sarebbe possibile (avendo una superpipeline in grado di eseguirne almeno 3, tra l’altro), mentre la quarta rimarrebbe in attesa del completamento della terza.
Chiaro, ma questo succederebbe soltanto se il numero di registri fosse esaurito; con un buon numero è difficile ciò accada. Già col 68000 e i suoi 8 (dati) + 7 (indirizzi) + SP + PC + SR era difficile, ma con la mia ISA ce ne sono molti di più, e mette a disposizione modalità d’indirizzamento e istruzioni che consentono di evitarne l’uso.