MIPS - INSTRUCTION SET ARCHITECTURE

(1)

CORSO DI ARCHITETTURE E SISTEMI OPERATIVI

PROF. MASSIMO DE SANTO

(2)

MIPS ISA MDS 2016

ISTRUZIONI & CPU

• Compito della CPU: eseguire istruzioni

• Le istruzioni costituiscono le operazioni primitive

eseguibili dalla CPU

CPU diverse implementano differenti insiemi di

istruzioni. L’insieme di istruzioni che una particolare CPU implementa è detto Architettura dell’Insieme di Istruzioni (Instruction Set Architecture - ISA)

• Esempi : Intel 80x86 (Pentium 4), IBM/Motorola

PowerPC (Macintosh), MIPS, Intel IA64, ...

(3)

STRTEGIE DIVERSE PER L’ISA

• CISC (Complex Instruction Set Computing)

- Istruzioni sempre più numerose e complesse in modo da poter

eseguire operazioni complesse: il VAX aveva un’istruzione per moltiplicare i polinomi !

• RISC (Reduced Instruction Set Computing)

- Mantenere il set di istruzioni piccolo e semplice: ciò rende più

facile costruire hardware veloce

- Non implementare operazioni complesse (e raramente eseguite)

tramite istruzioni dirette, ma realizzarle via software, componendo istruzioni più semplici

(4)

INSTRUCTION SET

• Capire il linguaggio dei componenti hardware è la

chiave per la comprensione dell'interfaccia hardware / software

• Un programma (ad es, in C) viene compilato in un

eseguibile che si compone di istruzioni macchina ed è importante che possa essere eseguito su macchine

diverse (anche su quelle che ancora non esistono). Soluzioni:

✦ ogni processore Intel accetta le stesse istruzioni x86, ma ogni

processore le gestisce in modo diverso

✦ I programmi Java sono convertiti in bytecode portatile che viene

convertito in istruzioni macchina durante l'esecuzione (compilatore just-in-time)

(5)

PRINCIPI DI PROGETTAZIONE

mantenere l’hardware semplice 

il chip dovrebbe implementare solo primitive base ed eseguirle molto velocemente

mantenere le istruzioni regolari 

semplificare la decodifica e la pianificazione dell’esecuzione delle istruzioni

5

Quali sono i più importanti principi di progettazione nella definizione dell'ISA?

(6)

CLASSI DI ISTRUZIONI

Istruzioni aritmetiche e logiche

Istruzioni di spostamento dati

Istruzioni di confronto

Istruzioni per il controllo di flusso

(7)

MIPS:

Microprocessor without Interlocking Pipe Stages

• Una delle prime architetture RISC commerciali • Studieremo il MIPS in qualche dettaglio

• Perchè MIPS invece di (ad es.) Intel 80x86?

✦ L’architettura e l’ISA del MIPS sono molto più semplici ed

eleganti

✦ Il MIPS è largamente utilizzato in applicazioni “embedded”,

contrariamente all’INTEL 80x86 che è praticamente limitato al solo segmento del personal computer

(8)

ARCHITETTURA DEL MIPS

• Architettura Load/Store con istruzioni aritmetiche

registro-registro a 3 operandi

• Istruzioni di 32bit - 3 Formati (R, I, J)

• 32 registri generali di 32 bit (R0 contiene 0, R31

riceve l’indirizzo di ritorno) (+ HI, LO)

• Modi d’indirizzamento: Register, Immediate, Base

+Offset, PC-relative

• Immediati a 16-bit + istruzione LUI

(9)

ARCHITETTURA DEL MIPS (2)

• Supporto per interi in complemento a 2 di  

8 (byte), 16 (halfword) e 32 (word) bit e, con

coprocessore opzionale, per numeri floating-point IEEE 754 singola e doppia precisione

• Controllo di flusso semplice (Salti e Diramazioni) • Delayed branch (l’istruzione dopo il salto viene

comunque eseguita) e Delayed load (l’istruzione dopo una load non deve usare il registro caricato), senza interlock

(10)

COPROCESSORI

• Fino a 4 coprocessori,

numerati da 0 a 3

• Il coprocessore di controllo

del sistema (coprocessore 0) è integrato nel chip e gestisce la memoria e le eccezioni • Il coprocessore floating-point (coprocessore 1) opzionale ha 32 registri di 32-bit ($f0 - $f31), di cui sono utilizzabili quelli di posto pari in semplice o doppia precisione

(11)

REGISTRI DEL

MIPS E

CONVENZIONE

DI USO

• 32 REGISTRI GENERALI DA 32 BIT • REGISTRI SPECIALI ✦ PC ✦ HI ✦ LO 11

(12)

GESTIONE DEGLI INDIRIZZI DI

MEMORIA

• Spazio di indirizzi di 232 byte (4 Gigabyte, con i 2

superiori riservati al S.O.), ossia 230_word

• L’indirizzamento è al byte (incremento di 4 per

passare da una word alla successiva)

• L’indirizzo di una word è quello del suo primo byte

(byte di indirizzo minore)

(13)

GESTIONE DEGLI INDIRIZZI DI

MEMORIA (2)

• Negli accessi, l’indirizzo di un dato di s byte deve

essere allineato, ossia A mod s = 0 (esistono istruzioni per accedere a dati disallineati)

• L’ordinamento dei byte in una word può essere sia

big-endian (il primo byte è quello più significativo) che little-endian (il primo byte è quello meno

significativo), in dipendenza del valore logico su di un pin

(14)

SPIEGHIAMOCI MEGLIO

• può una word essere

memorizzata in qualunque indirizzo della memoria ?

14 Memoria Parola allineata Parole disallineate 3 3 0 1 2 1 2 0

byte 0 little endian

byte 0 big endian

lsb msb

• come si distribuiscono gli

indirizzi dei byte appartenenti alla word ?

Big Endian (IBM 360/370, Motorola 68k, Sparc, HP PA)

Little Endian (Intel 80x86, DEC Vax, DEC Alpha)

indirizzabile al byte ma or ganizza ta in wor d

(15)

15

(16)

UNA ISTRUZIONE MIPS

ELEMENTARE

codice C : a = b + c ;

• codice Assembly: (istruzioni macchina

human-friendly)

add a, b, c # a è la somma di b e c

• codice Macchina: (istruzioni macchina hw-friendly) 00000010001100100100000000100000

16

(17)

17

individua in maniera mnemonica l’indirizzo

dell’istruzione

si riferisce alle modalità di reperimento degli operandi

(18)

ESEMPIO

Tradurre il seguente codice C in assembly:  

a = b + c + d + e;

18

Una singola linea di codice C è convertita in molte linee assembly

add a, b, c

add a, a, d

add a, a, e

add a, b, c

add f, d, e

add a, a, f

Istruzioni semplici: numero fisso di operandi

(diversamente dal C)

NOTA: Esistono diverse soluzioni ma alcune sequenze sono migliori di altre…

la seconda sequenza richiede una variabile (temporanea) f in più

oppure

(19)

OPERANDI DELLE ISTRUZIONI

• Finora abbiamo usato uno “pseudocodice”

• In C, ogni “variabile” è una locazione di memoria

• In hardware, gli accessi in memoria sono costosi – se una data

variabile a viene utilizzata di frequente, è conveniente spostarla in una area interna del chip (i registri) e lavorare su questa sorta di “taccuino per gli appunti”

• Per semplificare la realizzazione delle istruzioni, richiediamo che

ogni istruzione di calcolo lavori solo con i registri

• Nota: il numero di operandi (variabili) in un programma C è

molto grande; il numero di operandi in assembly è fisso… e c’è un numero limitato di registri!

(20)

REGISTRI

• L’ISA del MIPS ha 32 registri (x86 ha 8 registri)  – Perchè non di più? Perché non di meno? • Ogni registro è ampio 32-bit (le architetture

contemporanee a 64-bit hanno registri da 64-bit) • Un gruppo di 32-bit (4 byte) viene chiamato word • Per rendere il codice più leggibile i registri sono

suddivisi in $s0-$s7 (C/Java variables), $t0-$t9 (variabili temporanee)…

20

per capirlo dovremo ragionare sulle istruzioni

macchina

questa è una convenzione (non è imposta dall’hardware)

(21)

I REGISTRI (2)

• Ecco uno schema a blocchi

per un banco di registri generali (2k × n)

— Se Write = 1, il dato D viene memorizzato all’indirizzo D. — E’ possibile leggere due registri alla volta, fornendo in input gli indirizzi di A e B. Le

uscite si presentano sugli output dati A e B.

• I Registri sono dispositivi

sequenziali tempificati

— Si può leggere dal banco di registri in ogni momento 

— I dati sono scritti solo sul

fronte di salita del clock. _{January 27, 2003} _{Basic MIPS Architecture} ₆

Register file review

Here is a block symbol for a general 2k × n register file.

— If Write = 1, then D data is stored into D address.

— You can read from two registers at once, by supplying the A address

and B address inputs. The outputs appear as A data and B data. Registers are clocked, sequential devices.

— We can read from the register file at any time.

— Data is written only on the positive edge of the clock.

D data Write D address A address B address A data B data 2k × n Register File k k k n n n

costruiremo la nostra macchina MIPS con schemi come questo

(22)

I REGISTRI (3)

I nomi dei registri nel MIPS cominciano con $.   Ci sono due convenzioni di nomenclatura

✦ per numero

$0 ,$1, $2, … $31

✦ per nome

$a0…$a3, $s0…$s7, $t0…$t9, $sp, $ra

Non tutti sono registri generali e bisogna scegliere con attenzione i registri quando di programma in assembler

(23)

OPERAZIONI ARITMETICHE

ELEMENTARI

• Le operazioni aritmetiche elementari del MIPS

includono:

add sub mul div

• cui si aggiungono alcune operazioni logiche:

and or xor

• tutte richiedono sempre 3 operandi:

add $t0,$t1,$t2 # $t0 = $t1 + $t2 sub $t0,$t1,$t2 # $t0 = $t1 - $t2

Per espressioni complesse occorre ricorrere a operazioni multiple a livello dell’ISA

(24)

ESEMPIO

Quindi, nell’esempio precedente, potremmo assumere:

$t0 a, $t1 b, $t2 c, $t3 d, $t4 e

24

add a, b, c

add a, a, d

add a, a, e

add $t0, $t1, $t2

add $t0, $t0, $t3

add $t0, $t0, $t4

Sol 1 (pseudocodice)

se volessimo la Sol 2 ci vorrebbe un registro in più: $t5 f

l’unica espressione C:

a = b + c + d + e;

diventa

(25)

PROBLEMI DI SPAZIO

• I registri sono veloci e convenienti ma ne abbiamo

solo 32 da 32 bit

✦ certamente non bastano per strutture dati tipo gli array ✦ potremmo avere singoli dati più ampi di 32 bit

• dobbiamo usare la Memoria Centrale

✦ la MC è più economica ed ha una maggiore densità dei registri ✦ ma la MC è più lenta, quindi i registri vanno usati il più

possibile

• Il lavoro di allocazione dei dati nei registri

✦ nel passato era un compito del programmatore ✦ oggi è esclusivamente condotto dal compilatore

(26)

OPERANDI IN MEMORIA

• i Valori devono essere prelevati dalla memoria

prima che le istruzioni (add e sub) possano utilizzarli

Load word

lw $t0, memory-address

Store word

sw $t0, memory-address

• Come viene determinato l’indirizzo di memoria?

26

Register Memory

(27)

INDIRIZZI DI MEMORIA

• Il compilatore organizza i dati in memoria…

conosce la posizione di ogni variabile (salvata in

una tabella)… ed è in grado di fornire l’indirizzo di memoria appropriato alle istruzioni load-store

int a, b, c, d[10]

27

Memory

…

(28)

LA MEMORIA

• il segnale CS (Chip Select) abilita o disabilita la memoria

• ADRS indica la locazione cui accedere

• WR seleziona l’operazione di lettura / scrittura

✦ per leggere dalla memoria WR = 0.  

OUT riporterà il valore di n-bit immagazzinato all’indirizzo ADRS

✦ per scrivere nella memoria WR =1.  

DATA è il valore di n-bit da immagazzinare nella locazione di indirizzo ADRS

(29)

LA MEMORIA DEL MIPS

• La memoria del MIPS è indirizzabile al byte

✦ ogni indirizzo di memoria referenzia 8 bit

• l’architettura del MIPS supporta 32 linee indirizzo

✦ 232 x 8 bit di RAM, 4GB RAM al Max

• L’ISA contiene istruzioni di load e store che utilizzano

l’accesso indicizzato

✦ l’operando indirizzo è una coppia costante / registro che viene

addizionata per ottenere l’indirizzo effettivo

29

lb $t0, 20($a0) # $t0 = Memory[$a0+20] sb $t0, 20($a0) # Memory[$a0+20] = $t0

(30)

ACCESSO INDICIZZATO E VETTORI

lb $t0, const($a0)

l’accesso indicizzato è molto utile per locazioni contigue di memoria (ad esempio array o strutture)

• la costante è l’indirizzo base dell’array • il registro indica l’elemento cui accedere

per esempio, se $a0 contiene 0

lb $t0, 2000($a0)

legge il primo byte di un array che inizia all’indirizzo 2000 se $a0 contiene 8, la stessa istruzione accede al nono byte (Ps. Ecco perché in C e Java gli indici degli array

cominciano da 0 e non da 1)

(31)

ACCESSO INDICIZZATO E VETTORI (2)

lb $t0, const($a0)

ovviamente si possono capovolgere i ruoli

• la costante diventa l’indice dell’array • il registro indica l’indirizzo base

per esempio, se $a0 contiene 2000

lb $t0, 0($a0)

legge primo byte di un array con indirizzo base 2000 se la costante diventa 8, accederemo al nono byte

lb $t0, 8($a0)

(32)

BYTE E PAROLE

• In realtà, sebbene la memoria sia accessibile al byte,

l’elemento base delle operazioni sui dati rimane la word:

lw $t0, 20($a0) # $t0 = Memory[$a0+20] sw $t0, 20($a0) # Memory[$a0+20] = $t0

32

0 1 2 3 4 5 6 7 8 9 10 11

word 1 word 2 word 3

Byte Indirizzo

• i Linguaggi di alto livello supportano molti dati a 32 bit

(33)

RITROVIAMO L’ALLINEAMENTO

• Come già visto l’architettura del MIPS richiede che

le word siano allineate in memoria; le word da 32-bit iniziano da un indirizzo che sia divisibile per 4:

✦ 0, 4, 8, 12 sono indirizzi di word validi

✦ 1, 2, 3, 5, 6, 7, 9, 10, 11 sono indirizzi non validi

✦ il tentativo di accesso a un indirizzo non allineato provoca un

errore sul bus

• Anche se questo può sembrare un limite, in effetti

ha pochissimo effetto sul lavoro del compilatore mentre da’ enormi vantaggi nel rendere più

semplice e veloce il processore 33

(34)

VETTORI E PAROLE

Rivediamo l’esempio precedente utilizzando le word

• poniamo il primo elemento dell’array all’indirizzo 2000

• il secondo elemento si troverà all’indirizzo 2004 e NON 2001

se $a0 contiene 2000

lw $t0, 0($a0)

legge la prima word di un array

se la costante diventa 8, accederemo alla terza parola e non alla nona

lw $t0, 8($a0)

(35)

CALCOLI E MEMORIA (LOAD & STORE)

• Riepilogando, per fare delle elaborazioni utilizzando dati

contenuti in memoria dobbiamo:

✦ Caricare i dati dalla memoria nel banco dei registri

✦ Fare i calcoli ricordandoci di salvare il risultato in un registro

✦ Conservare il valore del registro risultato in memoria (se necessario)

• Per esempio, assumiamo che un array di interi A sia

memorizzato a partire dall’indirizzo 4096 e traduciamo l’espressione A[2] = A[1] * A[1]

35

lw $s0, 4($t0) # $s0 = A[1] mul $s0, $s0, $s0 # A[1] * A[1]

sw $s0, 8($t0) # A[2] = A[1] * A[1]