Mattia Natali
1 Reorder Buffer
• Disaccoppia l’esecuzione dalla conclusione di una operazione (commit). In questo modo abbiamo issue-in-order, execution-out-of-order e infine commit in-order.
• In questo modo siamo sicuri di mantenere il data flow originario (no RAW, WAW, WAR), abbiamo eccezioni precise ma contemporaneamente possiamo sfruttare il parallelismo.
• Possiamo effettuare data speculation e instruction speculation senza preoccuparci delle conseguenze dato che il commit avverrà solamente se la speculazione è stata eseguita correttamente.
• Nelle esecuzioni SMT il reorder buffer potrebbe essere sostituito eseguendo un altro th- read durante il periodo di stallo.
• Il ROB mantiene i risultati delle istruzioni che hanno fatto speculazione e non li salva finchè si è sicuri che le istruzioni andavano eseguite correttamente.
• Quando viene eseguita una speculazione le eccezioni non vengono scatenate subito ma solo in fase di commit per mantenere il data flow corretto.
• Scoreboard e Tomasulo avevano issue in-order ma esecuzione e completamento fuori ordine, con il ROB abbiamo il commit in ordine così da avere delle eccezioni precise.
• Le istruzioni vengono inserite nel ROB nell’ordine che rispecchia il data flow e viene fatto il commit eseguendo FIFO.
• Una voce del ROB contiene: indirizzo di destinazione, flag di esecuzione conclusa, risulta- to, PC, eccezioni.
• L’HW speculation si suddivide in:
◦ Dynamic branch prediction.
◦ Dynamic scheduling.
◦ Speculation.
• Dobbiamo stare attenti alla memory disambiguation per evitare RAW, per esempio se si fa store su un registro e subito dopo dobbiamo fare load in un altro registro bisogna verificare che i due registri non puntino allo stesso indirizzo di memoria
2 Multithreading
• Abbiamo quattro tipi di multithreading:
◦ Superscalare: esegue prima uno e poi un altro processo.
◦ A grana fine: ad ogni ciclo di clock cambia il thread in esecuzione, a causa dei nume- rosi cambi è impossibile immagineare un cambio di contesto. Abbiamo replicazione di registri e PC. Vantaggi: meno possibilità di avere dipendenze dati e quindi meno stalli, non perdiamo tempo nei branch e cache miss. Posso nascondere sia gli stal- li corti che lunghi. Svantaggi: l’esecuzione di un thread singolo viene rallentata per eseguire anche altri thread contemporaneamente. Siccome mando solo un flusso alla volta potrebbe capitare che non trovo istruzioni da mandare in fetch.
1
Mattia Natali
◦ A grana grossa: viene eseguito un thread finchè abbiamo uno stallo considerevole, quindi il processore effettua un cambio di contesto con un altro thread. Vantaggi: il singolo thread non viene rallentato. Svantaggi: se abbiamo degli stalli corti perdiamo il throughtput.
◦ Multiprocessing: separiamo il processore in due parti, così da aumentare il paralleli- smo
◦ SMT: è quello più adottato oggigiorno, abbiamo replicazione di PC e registri e per- mettiamo l’esecuzione di più thread in contemporanea così possiamo anche sfruttare meglio tutte le FU disponibili dato che raramente un processo le sfrutta tutte in una istruzione.
∗ L’unità di fetch deve essere in grado di fare più issue contemporaneamente. Per fare questo si usano delle memorie cache interleaved. Abbiamo la rinominazio- ne dei registri per thread. In questo modo lo spazio per i thread viene allocato dinamicamente.
∗ Il fecth decide quale thread mandare in esecuzione: meglio dei thread che non hanno dei data hazard in corso, con meno branch irrisolti, meno load misses, meno istruzioni in coda
3 Cache
• Politiche di scrittura in caso di write hit:
◦ Write back: si scrive solamente nella cache senza aver bisogno di scrivere nella me- moria principale, bisogna però avere un bit di controllo per sapere se il valore in cache è diventato l’originale (bit dirty) in modo tale che se c’è bisogno di quel blocco per un altro dato si scrive in memoria prima di cancellarlo. Vantaggi: minor uso di banda del bus per scritture ripetute su uno stesso dato (per il principio di località questa casistica capita spesso). Svantaggi: una read miss può provocare anche la scrittura di un dato in memoria.
◦ Write throught: più semplice da gestire, in caso di write si scrive direttamente in me- moria senza quindi avere delle incongruenze tra cache e memoria. In memoria abbia- mo quindi il dato sempre aggiornato. Vantaggi: architettura più semplice. Svantaggi:
il bus viene occupato se abbiamo numerose scritture sullo stesso dato, saturazione del bus.
∗ Meglio inserire un write buffer per non far stallare la CPU, scrivere in memoria si perde tempo. Se abbiamo una read bisogna anche controllare che non abbiamo il dato in questo buffer, altrimenti potremmo avere una RAW.
• In caso di cache miss:
◦ no write allocate.
◦ write allocate (fetch on write).
• Per una cache bisogna pensare a:
◦ Block placement: come assegnare i blocchi nelle varie celle. (Direct mapped, n-way set associative, fully associative).
◦ Block identification: come trovare un blocco.
◦ Block replacement: quale blocco rimpiazzare.
2
Mattia Natali
◦ Write strategy: cosa fare se effettuiamo una write.
• Casi in cui abbiamo una miss:
◦ Il dato non è mai stato caricato nella cache: compulsory. (Aumentare la dimensione di un blocco può diminuire questo tipo di miss).
◦ Spazio insufficiente: size miss (Aumentare dimensione della cache).
◦ Conflitto sul blocco: conflict (Aumentare il livello di associatività).
◦ Coerenza (invalidation).
3.1 Cache optimization
• Ridurre miss rate:
◦ Aumentare dimensione dei blocchi (compulsory).
◦ Aumentare la associatività (conflict).
◦ Introdurre la victim cache: cache in cui si mettono i blocchi scartati per la richiesta di altri blocchi con lo stesso index.
◦ Cache pseudo-associative: la direct-mapped cache è velocissima però è limitante.
Quindi si suddivide la cache in 2 così prima si guarda in una parte direttamente, se non lo si trova si prova nell’altra. Nel secondo caso abbiamo un pseudo-hit. In realtà non è associativo.
◦ HW prefetching di data o istruzioni: prende i blocchi contigui anche se non è stato esplicitamente richiesto
◦ Prefetching controllato dal compilatore.
◦ Il compilatore tenta di ridurre le miss adottando queste tecniche:
∗ Merging array: fondere due array che contengono dei dati correlati tra di loro, sostituire i due array con uno contenente delle struct.
∗ Loop interchange: modificare due loop innestati per avere il ciclo interno con meno elementi.
∗ Loop fusion: combinare due loop che lavorano sugli stessi dati.
∗ Blocking: aumentare la località del codice lavorando su blocchi e non scorrendo magari tutte le colonne o le righe di un array.
• Ridurre miss penalty:
◦ Priorità alle read misses: se abbiamo write back e dobbiamo leggere un dato e fa miss perchè c’è un blocco diverso con il bit dirty = 1, invece di fare prima la write e poi caricare in memoria il dato si fa il contrario per stallare di meno, la scrittura andrà nel write buffer. Con la politica write throught se abbiamo una miss in lettura non aspettiamo che il write buffer si svuoti prima di leggere, bensì scorriamo anche il write buffer per vedere se il nostro dato si trova lì oppure in memoria centrale.
◦ Subblock placement: non carichiamo un nuovo blocco per intero in una miss ma solo una parte. Ogni sottoblocco quindi deve avere un bit di validità
◦ Early restart & critical word first: primo caso passo il blocco direttamente alla CPU come arriva, secondo caso passo prima la parola che interessa e poi riempio il blocco con le altre parole
3
Mattia Natali
◦ Non blocking cache: servono delle cache interleaved così che possano gestire più miss contemporaneamente. Molto complesso da realizzare.
◦ Second level cache
• Ridurre hit time:
◦ Semplificare le cache: le direct mapped sono le più semplici e più veloci:
◦ Evitare la traduzione dell’indirizzo virtuale: aggiungere PID, oppure farlo in contem- poranea
◦ Pipeling writes:
◦ Way prediction: aggiungere bit per predirre in quale set si trova la parola giusta nelle set associative.
4
