Architettura MIPS - Calcolatori elettronici

Calcolatori elettronici ISA (Instruction Set Architecture)

Miglior metrica tempo di esecuzione del programma

2 chiavi principali del Machine Design:

• Le istruzioni sono rappresentate come numeri e, come tali, sono indistinguibili dai dati.
• I programmi sono conservati in memorie alterabili (che possono essere lette o scritte) come i dati.

Concetto Stored-Program

I programmi possono essere spediti come files di numeri binari binary compatibility. I computers possono ereditare prodotti già pronti a condizione che l’ISA sia compatibile.

Principi di Design MIPS

• La semplicità favorisce la regolarità.
• Più piccolo è più veloce.
• Rendi più veloce il caso più comune.
• Un buon design richiede buoni compromessi.

Il registro file MIPS contiene 32 registri da 32 bits e ha 2 porte di lettura e una porta di scrittura. I registri sono:

• Più veloci della memoria primaria.
• Più semplici da usare per il compilatore.
• Migliorano la densità del codice (meno bits).

Alignment restriction l’indirizzo di memoria di una parola deve essere un multiplo di 4 nel MIPS-32.

Formati di indirizzamento

2 formati:

• Big Endian il byte più a sinistra è l’indirizzo della parola.
• Little Endian il byte più a destra è l’indirizzo della parola.

Formati istruzione R, I e J

Nell’ISA (Instruction Set Architecture) del processore MIPS composto da 32 registri a 32 bits abbiamo 3 formati per le istruzioni:

Formato R

OP RS RT RD SA FUNCT

• OP (6-bits): OPcode specifica l’operazione.
• RS (5-bits): Register Source indirizzo registro file del primo operando sorgente.
• RT (5-bits): Register T indirizzo registro file del secondo operando sorgente.
• RD (5-bits): Register Destination indirizzo registro file della destinazione del risultato.
• SA/SHAMT (5-bits): Shift AmounT per istruzioni di shift.
• FUNCT (6-bits): FUNCtion incrementa l’opcode.

Usato per:

• Istruzioni aritmetiche (add, sub, mud, div, ecc…).
• Operazioni di Shift (sll, srl, ecc…).
• Operazioni logiche (and, or, nor, ecc…).
• Supporto alle istruzioni di branch (slt, slti, sltu, sltiu, ecc…).

Formato I

OP RS RT IMMEDIATE

Usato per:

• Istruzioni per accesso alla memoria (lw, sw, lb, sb, ecc…).
• Istruzioni immediate (addi, slti, lui, ori, ecc…).
• Operazioni logiche (andi, ori, ecc…).
• Istruzioni condizionali di branch (beq, bne, ble, bgt, bge, ecc…).

Formato J

OP JUMP TARGET

Usato per:

• Istruzioni di salto/jump j.
• Istruzioni per procedure di chiamata jal.
• Istruzione per procedura di ritorno jr.

Istruzioni Load/Store

I dati sono scaricati (lw) in o caricati (sw) da un registro nel register file indirizzo a 5 bit. L’indirizzo di memoria, a 32 bit, è formato aggiungendo al contenuto dell’indirizzo base del registro il valore di offset. Per muovere i byte utilizziamo le istruzioni: lb e sb. Gli 8 bits presi in considerazione (scaricati o caricati) sono quelli più a destra.

Immediate

• Mettiamo una costante tipica nella memoria e scarichiamola da lì.
• Creiamo un registro apposito per la costante ($zero).
• Utilizziamo speciali istruzioni che contengono la costante (es. slt, stli).

Se volessimo utilizzare costanti a 32 bits dovremmo utilizzare due istruzioni:

• lui (load upper immediate) posiziona i primi 16 bits a sinistra.
• ori posiziona gli ultimi 16 bits a destra.

Operazioni di Shift

Abbiamo bisogno di operazioni che spostino pacchetti di 8-bit in parole da 32 bit:

• sll shift left.
• srl shift right.

Branch condizionali

Salti condizionati da una condizione bne, beq.

Come specificiamo la destinazione?

• Usiamo un registro a cui sommiamo 16 bit di offset Instruction Address Register (PC Program Counter).

Il suo uso è implicato automaticamente dall’istruzione e si aggiorna ad ogni ciclo di fetch così sa l’indirizzo della prossima istruzione. In supporto a queste istruzioni abbiamo l’assembler, che utilizzando un registro riservato ad esso ($at) permette di includere istruzioni speciali quali:

• ble be less than or equal to.
• bgt be greater than.
• bge be greater than or equal to.

Jump, Jump and Link e Jump Return

Salti incondizionati j, jal e jr ($ra return address).

Sei steps nell’esecuzione di una procedura

1. La Main (caller) posiziona i parametri dove la procedura (callee) può accedere ($a0, …, $a3).
2. La Main traferisce il controllo alla procedura.
3. La procedura prende le risorse di cui ha bisogno.
4. La procedura esegue l’istruzione richiesta.
5. La procedura posiziona i risultati dove la Main può accedere ($vo, …, $v1).
6. La procedura ripassa il controllo alla Main ($ra).

Se la procedura dovesse avere bisogno di più registri per allocare argomenti e ritornare valori allora useremo uno stack (LIFO Last In First Out) $sp (Stack Pointer):

• Push aggiungiamo dati nello stack.
• Pop rimuoviamo dati dallo stack.

Tipi di segmento dati

• Statico costanti statiche come gli arrays.
• Dinamico (heap) strutture che crescono e decrescono come le liste.

Il segmento dello stack che contiene i registri salvati della procedura e le variabili locali è il procedure frame: Il Frame Pointer ($fp) punta alla prima parola del frame della procedura e provvede ad un registro base stabile per la procedura. $fp è inizializzato usando $sp in chiamata e $sp è restaurato usando $fp in ritorno.

Special: Atomic Exchange

Scambia un valore in un registro con un valore in memoria automaticamente una sola istruzione. In alternativa possiamo utilizzare speciali istruzioni configurate:

• ll load linked.
• sc store linked.

Se il contenuto della locazione di memoria specificata da ll cambia prima che sc si verifichi allo stesso indirizzo, questo fallisce e ritorna zero.

Gerarchia Traduzione codice C

Programma in C → compilatore codice assembler → assembler codice oggetto (codice macchina) → linker + librerie (codice macchina) → eseguibile (codice macchina) → loader memoria (codice macchina).

Gerarchia Traduzione codice Java

Programma in Java → compilatore Class files (Java bytecodes) → compilatore Just In Time (JIT) + Macchina Virtuale Java (+ Librerie Java (codice macchina)) → Metodi Java compilati (codice macchina).

CPU Clocking Methodology

Definisce quando un dato in un elemento di stato è valido e stabile relativo al clock:

• Elementi di stato elemento di memoria come un registro.
• Edge triggered tutti i cambiamenti di stato si verificano sul bordo del clock.

Assumiamo che gli elementi di stato siano scritti su tutti i cicli di clock; se non è così, abbiamo bisogno di esplicitare il segnale di controllo write: la scrittura si verifica solo quando il segnale di controllo write è asserito e si verifica il bordo del clock.

Datapath senza Pipeline

Utilizzo del clock. Fasi:

Fetch (IF)

• PC (Program Counter) si aggiorna ad ogni giro di clock per l’istruzione successiva con un adder (PC+4).
• Memoria Istruzioni legge l’istruzione da eseguire.
• Il PC è aggiornato ad ogni ciclo di clock non ha bisogno di un segnale di controllo esplicito write.
• La lettura dalla Memoria Istruzioni è una attività combinatoria non ha bisogno di un segnale di controllo esplicito write.

Decoding (ID)

• Registro file vengono letti i registri RS, RT, RD e, in caso di load word, viene scritto il dato caricato dalla memoria. È controllato dell’ingresso RegWrite. In uscita vengono letti due valori.
• Unità di Controllo riceve l’opcode e controlla tutti i segnali necessari ad eseguire l’istruzione.

Executing (EX)

• ALU riceve i dati dal registro file ed esegue l’operazione. È controllato dalla ALU control che a sua volta riceve in ingresso il controllo ALUOp, dall’Unità di Controllo, e il segnale dell’istruzione [5-0]. L’uscita zero è utilizzata per le operazioni di branch. Nel caso di istruzioni di tipo R il risultato non entra nella Memoria Dati ma va oltre.
• Esegue l’operazione (op e funct) con i valori in rs e rt, carica il risultato nel Register File (nella locazione rd).
• Il Register File non è scritto ad ogni ciclo di clock, abbiamo bisogno di esplicitare un segnale di controllo esplicito write.
• Aggiungiamo al registro base i 16 bit di offset estesi a 32 con il Sign Extended calcoliamo l’indirizzo di memoria.
• Store valore store (letto dal Register File durante il decode) scritto nella Memoria Dati.
• Load valore load (letto dalla memoria Dati) scritto nel Register File.
• Branch compariamo gli operandi letti dal Register File durante il decode (zero ALU output) calcoliamo l’indirizzo di branch aggiungendo PC+4 ai 16 bit di offset estesi a 32 dal Sign Extended.
• Jump riposizioniamo i 28 bits inferiori del PC con i 26 bits inferiori della fetched instruction shiftata a sinistra di 2 bit.

Memory (MEM)

• Memoria Dati riceve in ingresso il risultato della ALU e, in caso di store word, il dato da caricare nella memoria. È controllata dai segnali di controllo MemWrite e MemRead.

Write Back (WB)

• Multiplexer con controllo MemToReg viene caricato il dato nella porta Write Data in ingresso al Registro File.

Altri componenti

• Sign Extended estende il segnale dell’istruzione [5-0] da 16 a 32 bits.
• MUX 1 riceve in ingresso i segnali dell’istruzione [20-16] e [16-11] ed è controllato dal segnale di controllo RegDst.
• MUX 2 riceve in ingresso i segnali dell’istruzione [15-0] estesa a 32 bits e la seconda uscita del Registro File ed è controllato dal segnale di controllo ALUSrc.
• MUX 3 riceve in ingresso il risultato della ALU e il dato in uscita della Memoria Dati ed è controllato dal segnale di controllo MemToReg.
• Shift left 2 sposta di due bit il segnale dell’istruzione [15-0] esteso a 32 bits.
• Adder 1 aggiorna il PC a PC+4.
• Adder 2 riceve il ingresso il segnale di controllo in uscita dallo Shift Left 2 e PC+4.
• MUX 4 riceve in ingresso PC+4 e il risultato dell’Adder 2 ed è controllato dal segnale di controllo PCSrc che è a sua volta prodotto da segnale di controllo Branch e dall’uscita zero della ALU.
• Shift left 2 Jump utilizzato per istruzioni di jump, riceve in ingresso il segnale dell’istruzione [25-0] passando da 26 a 28 bits e viene aggiornato in uscita con il segnale PC+4 [31-28] passando così da 28 a 32 bits.
• MUX 5 riceve in ingresso il segnale jump e l’uscita del MUX 4 ed è controllato dal segnale di controllo Jump.

Assembliamo i segmenti del datapath e aggiungiamo le linee di controllo e i multiplexors necessari

Single cycle design

• Fetch, decode e execute in un ciclo di clock.
• Nessuna risorsa del datapath può essere utilizzata più di una volta per istruzione; alcune dovranno essere duplicate.
• I multiplexors hanno bisogno di segnali di controllo per la selezione.
• Segnali di scrittura per controllare il Register File e la Memoria Dati.

Il tempo di clock è determinato dalla lunghezza del percorso più lungo.

Svantaggi

• Usiamo il ciclo di clock inefficientemente deve essere temporizzato per accomodare le istruzioni più lente.
• Spreco di area dobbiamo duplicare alcune unità funzionali (es. adders) poiché non possono essere condivise durante il ciclo di clock.

Vantaggio

• È semplice e facile da capire.

Datapath con Pipeline

Per velocizzare il Datapath andiamo ad utilizzare la Pipeline che ci permette di iniziare l’istruzione successiva senza che l’altra abbia eseguito tutte le fasi ma solo quella di Fetch. Facendo così, ottimizziamo la quantità di lavoro per unità di tempo (throughput) e la latenza dell’istruzione non è ridotta. Per alcune istruzioni non saranno necessari tutti gli stadi (wasted cycles). Posizioniamo degli State Registers tra ogni stage della pipeline per isolarli. Tutti i segnali di controllo sono determinati durante il Decode e sono mantenuti negli State Registers tra gli stages della pipeline.

Errori nella Pipeline

Incorriamo in 3 categorie di errori:

• Errori strutturali sono dovuti all’utilizzo della stessa risorsa da parte di due istruzioni differenti allo stesso tempo.
• Errori di dati dovuto all’utilizzo di un dato prima che sia pronto.
• Errori di controllo dovuto al prendere una decisione prima che la condizione sia stata valutata e che il nuovo target del PC sia stato calcolato (istruzioni di salto).

Soluzioni per Errori di dati

• Inserire degli stalli: fermiamo la pipeline fino a che non sarà possibile eseguire l’istruzione successiva senza errori. L’inserimento di stalli implica l’inserimento di una Hazard Unit all’interno del Datapath che controlla il Registro base IF/ID con il segnale IF/ID.Write, un MUX che riceve in ingresso un segnale proveniente dall’Unità di controllo e uno zero, e il PC con il segnale PC.Write.
• Forwarding: inoltriamo il dato in uscita all’istruzione dopo che necessita il suo utilizzo, senza aspettare che la prima esca fuori dalla pipeline. L’utilizzo del Forwarding implica l’aggiunta di un altro componente all’interno del Datapath, l’Unità di Forward, e di altri due Multiplexer, all’uscita del Registro File, che saranno gestiti da segnali di controllo della Forward Unit. Quest’ultima in ingresso riceve:
  • Segnale di Branch
  • Segnale MemToReg (?)
  • EX/MEM.RegisterRd
  • MEM/WB.RegisterRd
  • ID/EX.RegisterRt
  • ID/EX.RegisterRs
• Flush: rimpiazza un’istruzione nella pipeline con un no-op quando necessario.