1

Calcolatori Elettronici

ISA di riferimento:MIPS

Massimiliano Giacomin

2

DOVE CI TROVIAMO…

ISA

Livellofunzionale

Livellologico

Livellocircuitale

Livellodel layout

Reti logiche: registri, ALU, MUX…

Porte logiche: NOT, AND, …

TransistorModelli fisici: si parla didimensioni fisiche,materiali, ecc.

Modelli elettronici:si parla ditensioni, correnti, ecc.

Modelli logici:si parla di variabili,valori… binari!

Organizzazione dicomponenti per implementare ISA

istruzioni macchina, …REQUISITI

3

Componenti: registri, ALU, bus, memorie, …Instruction Set Architecture (ISA)

LIVELLODEI CIRCUITI

LIVELLODEL LAYOUT

LIVELLODELLA LOGICA

LIVELLOFUNZ.LE (RTL)

LIVELLOSIST. OP.

LIVELLO LING. ASSEMBLY

Strutture: transistor, resistenze, capacità…Componenti: materiali (Si, AsGa, …)

LIVELLO APPLICAZIONI

Componenti: transistor, resistenze, capacità…Strutture: porte logiche, flip-flop, …

Componenti: porte logiche, flip-flop, …Strutture: registri, ALU, bus, memorie, …

ISAApplication Binary Interface (ABI)

Application Binary Interface (ABI)Programmi assembly

Programmi assemblyProgrammi applicativi

LIVELLI INTERESSATI NELLA LEZIONE…

4

Architettura MIPS

• Architettura sviluppata da John Hennessy nel 1981• Usata da NEC, Nintendo, Silicon Graphics, Sony• Caratteristica fondamentale: semplicità ed “eleganza”

• Il processore MIPS è a 32 bit:- tutti i registri sono a 32 bit- gli indirizzi per accedere in memoria sono a 32 bit

• Il numero di registri visibili al programmatore è 32 (identificati da un numero 0-31: servono 5 bit)

5

Nome Codifica

$zero 0

$at 1

$v0-$v1 2-3

$a0-$a3 4-7

$t0-$t7 8-15

$s0-$s7 16-23

$t8-$t9 24-25

$k0-$k1 26-27

$gp 28

$sp 29

$fp 30

$ra 31

I registri del MIPS visibili al programmatore

vale sempre 0

utilizzato dalla jal

• NB: ad eccezione di $zero e $ra, i nomi riflettono pure convenzioni sull’utilizzo• Tutti i registri possono essere usati indifferentemente come operandi

6

Tipologie di istruzioni

• Istruzioni aritmetiche e logiche• Istruzioni di trasferimento:

- lw- sw

• Istruzioni di controllo:- salti condizionati- salti incondizionati (includono la chiamata a una procedura e l’istruzione di ritorno)

7

Istruzioni aritmetico-logiche

add $s0, $t1, $t2 # $s0 = $t1 + $t2

VARIANTE B) 2 operandi registro e 1 “immediato”

addi $s0, $t1, -4 # $s0 = $t1 + (-4)

destinazionesorgente

sorgente

destinazionesorgente

sorgente

VARIANTE A) 3 operandi registro

8

Specchio riassuntivo (vale per istruzioni aritmetiche e logiche)

• Tutte le istruzioni hanno 3 operandi:- un operando destinazione- due operandi sorgente

• Gli operandi sorgente possono essere:- due registri (es: istruzione add) - un registro e un operando sorgente costante (a 16 bit):istruzione indicata con suffisso i (es: istruzione addi)

• In assembly, l’operando destinazione appare come primo operando

• Come registro sorgente/destinazione può essere usato uno qualunque dei 32 registri disponibili (anche $zero come destinazione)

9

Istruzioni aritmetiche

NB: subi non presente (non serve!)

add r1, r2, r3 # r1 = r2 + r3

sub r1, r2, r3 # r1 = r2 – r3

addi r1, r2, const # r1 = r2 + const

Nota: r1, r2, r3 indicano registri quasiasi, const una costante indicatanell’istruzione soggetta a vincoli specifici.

10

Esercizio

Effettuare $s1 + $s2 – $s3 + $s4 e porre il risultato in $s0

11

Esercizio

Effettuare $s1 + $s2 – $s3 + $s4 e porre il risultato in $s0

add $s0, $s1, $s2 # $s0 = $s1 + $s2

sub $s0, $s0, $s3 # $s0 = $s1 + $s2 – $s3

add $s0, $s0, $s4 # $s0 = $s1 + $s2 – $s3 + $s4

12

Istruzioni logiche

And “bit a bit”

and r1, r2, r3 # r1 = r2 & r3 NB: utile per applicareuna “maschera”andi r1, r2, const # r1 = r2 & const

Or “bit a bit”

or r1, r2, r3 # r1 = r2 | r3 NB: utile per porre a 1determinati bitori r1, r2, const # r1 = r2 | const

Nor “bit a bit”

nor r1, r2, r3 # r1 = ~(r2 | r3) NB: NOT si ottiene connor r1, r2, r2

o nor r1, r2, $zero(NB: nori non disponibile, utilizzo raro)

NB: per le istruzioni immediate, la costante viene estesa a 32 bit completandola con un opportuno numero di zeri

13

Istruzioni di shift

Shift left logical

sll r1, r2, const # r1 = r2<<const

Shift right logical

srl r1, r2, const # r1 = r2>>const

NB: inseriti zeri a destra, utile per moltiplicare per 2const

NB: inseriti zeri a sinistra, utile per dividere numeri positivi per 2const

Shift right arithmetic

sra r1, r2, const # r1 = r2>>const

NB: inserite a sinistra copie del bit di segno, utile per dividere numeri positivi e negativi per 2const

(in realtà numeri negativi dispari divisi e arrotondati per difetto)

14

Istruzioni di trasferimento dati

• Permette di trasferire una parola di memoria (32 bit, 4 byte) in un registro• Sintassi:

lw r1, const(r2) # r1 = M[r2+const]

• Permette di trasferire il valore di un registro in una parola di memoria• Sintassi:

sw r1, const(r2) # M[r2+const] = r1

load word (lw)

store word (sw)

Registro base

spiazzamentoRegistro destinazione

Registro base

spiazzamentoRegistro sorgente

15

Esercizio con array di interi (allocato in memoria)

00000000

11110000

A

…

A+4*i

A+4Indirizzo base del vettore Acontenuto in un registro base

ES: l’indirizzo di h sia $s2 e il registro base del vettore A sia $s3Traduzione di A[12] = h + A[8]

…

h

16

Esercizio con array di interi (allocato in memoria)

00000000

11110000

A

…

A+4*i

A+4Indirizzo base del vettore Acontenuto in un registro base

ES: l’indirizzo di h sia $s2 e il registro base del vettore A sia $s3Traduzione di A[12] = h + A[8]

lw $t0, 32($s3) # carica in $t0 il valore A[8]lw $t1, 0($s2) # carica in $t1 il valore di hadd $t0, $t1, $t0 # somma h + A[8]sw $t0, 48($s3) # memorizza la somma in A[12]

…

h

17

Istruzioni di controllo: salti incondizionati (j, jr e jal)

j L1Vai incondizionatamente all’istruzione etichettata con L1(j = jump)

jr r1 Vai incondizionatamente all’istruzione di indirizzo contenuto nel registro specificato(jr = jump register)

jal L1Vai incondizionatamente all’istruzione etichettata con L1e salva l’indirizzo dell’istruzione successiva in $ra- cfr. procedure (jal = jump and link)

18

CHIAMANTE…jal Proceduraadd $s0, $s1, $s2……………

Procedura: add $t0, $t1, $t2……jr $ra

CHIAMATO

$ra

Chiamata di una procedura

19

CHIAMANTE…jal Proceduraadd $s0, $s1, $s2……………

Procedura: add $t0, $t1, $t2……jr $ra

CHIAMATO

e ritorno

20

Chiamata di una procedura

• Istruzione jal (jump-and-link): è l’istruzione apposita per le procedure, che salta a un indirizzo e contemporaneamente salva l’indirizzo di ritorno nel registro $ra

jal IndirizzoProcedura

• In pratica jal salva il valore di PC+4 nel registro $ra, che contiene l’indirizzo della prossima istruzione: questo crea un “collegamento” all’indirizzo di ritorno dalla procedura

• L’indirizzo di ritorno è necessario perché la stessa procedura può essere richiamata in più parti del programma

Ritorno da una procedura chiamata

• L’istruzione per effettuare il salto di ritorno èjr $ra

In questo modo il chiamato restituisce il controllo al chiamante

21

Istruzioni di controllo: salti condizionati (beq, bne)

beq r1, r2, L1Vai all’istruzione etichettata con L1 se il valore contenuto nel registro r1 è uguale al valore contenuto nel registro r2(beq = branch if equal)

bne r1, r2, L1Vai all’istruzione etichettata con L1 se il valore contenuto nel registro r1 è diverso dal valore contenuto nel registror2 (bne = branch if not equal)

22

Esercizio: if-else

• Frammento di codice C:

if (i = = j) f = g + h; else f = g - h ;Supponendo che f, g, h, i, j siano mantenute nei registri $s0, $s1, $s2, $s3, $s4, scrivere la versione assembly

23

Esercizio: if-else

• Frammento di codice C:

if (i = = j) f = g + h; else f = g - h ;Supponendo che f, g, h, i, j siano mantenute nei registri $s0, $s1, $s2, $s3, $s4, la versione assembly è:

bne $s3, $s4, Elseadd $s0, $s1, $s2j Esci

Else: sub $s0, $s1, $s2Esci:

24

Versione alternativa equivalente

• Frammento di codice C:

if (i = = j) f = g + h; else f = g - h ;Supponendo che f, g, h, i, j siano mantenute nei registri $s0, $s1, $s2, $s3, $s4, la traduzione è la seguente

beq $s3, $s4, Ifsub $s0, $s1, $s2j Esci

If: add $s0, $s1, $s2Esci:

25

• Oltre a testare uguaglianza o diseguaglianza, talvolta è necessario effettuare un confronto di maggioranza e beq, bne non bastano!

• E’ prevista un’altra istruzione per confrontare due variabili: sltslt r1, r2, r3

poni a 1 il valore del registro r1 se il valore del registro r2 è minore del valore del registro r3, altrimenti r1 è posto a 0 (slt = set on less than)

• Esiste anche la versione immediate: slti r1, r2, immediate

• Esempio (salta a Minore se $s0<$s1):

slt $t0, $s0, $s1 # $t0 diventa 1 se $s0 < $s1

bne $t0, $zero, Minore # vai a Minore se $t0 ¹ 0

Istruzioni di controllo: l’istruzione set on less than (slt)

26

• Frammento di programma C:

for (i=0; i<k; i++) f = f + A[i];

siano i, k, f mantenute nei registri $s1, $s2, $s3, supponendo che l’indirizzo base di A in $s4. Scrivere la versione assembly

Esercizio: ciclo for

27

• Frammento di programma C:

for (i=0; i<k; i++) f = f + A[i];

siano i, k, f mantenute nei registri $s1, $s2, $s3, supponendo che l’indirizzo base di A in $s4. La versione assembly è:

add $s1, $zero, $zero #i=0Ciclo: slt $t0, $s1, $s2 # poni $t0 a 1 se i < k

beq $t0, $zero, Esci # se $t0 = 0 vai a Escisll $t0, $s1, 2 # $t0 = i * 4add $t0, $t0, $s4 # $t0 = indirizzo di A[i]lw $t0, 0($t0) # $t0 = A[i]add $s3, $s3, $t0 # f = f + A[i]addi $s1, $s1, 1 # i = i + 1j Ciclo

Esci:

Esercizio: ciclo for

28

Caratteristiche dell’architettura

• Istruzioni load-store: le uniche che accedono alla memoria• Istruzioni aritmetiche:

- operandi registro e/o immediato (no accessi in memoria)- consentono di rappresentare due sorgenti e una destinazione

(usare i registri è più efficiente rispetto alla memoria; spilling dei compilatori)

LOAD-STORE

REGISTRI GENERAL PURPOSE

• Registri general-purpose (le istruzioni lavorano indifferentemente su tutti i registri)- fa eccezione $zero, che si può usare ma rimane comunque al valore nullo- $ra impostato con indirizzo di ritorno dall’istruzione jal

(ma può essere usato normalmente dalle istruzioni)

29

• Per le istruzioni di controllo, abbiamo visto che:- si sono mantenute al minimo le istruzioni di salto condizionato (beq e bne)- per effettuare salti basati su confronto, è necessario decomporre il salto

in più istruzioni, utilizzando slt> Questo non “pesa” nelle architetture che utilizzano il parallelismo> Permette però una semplificazione che porta in generale a maggiore efficienza

ad es. ad una diminuzione di Tclock

Evitare la proliferazione delle istruzioni (sono possibili compromessi). P.es.- subi non presente (si può usare addi) - NOT non presente (si può usare NOR + registro $zero)- NORI non presente (poco utilizzato, si può comunque usare or e “not con nor”)

RISC

30

• Istruzioni a lunghezza costante: 32 bit (una parola di memoria, un registro)• Suddivisione in diversi campi per definire il formato delle istruzioni

rispettando il principio della regolarità

Da quanto visto, le istruzioni esaminate si possono suddividere in 3 categorie:• istruzioni che devono indicare 3 registri (add, sub, and, slt, ecc.)• istruzioni che devono indicare due registri e una costante, in particolare:

- lw e sw - istruzioni che riferiscono un operando immediato (addi, andi, ori, ecc.)- salti condizionati (due registri per il confronto + costante per il salto)

• istruzioni di salto incondizionato, che non riferiscono alcun registro ma(presumibilmente) indicano una costante “con molti bit”…

Le tre categorie danno luogo a tre (semplici) formati, con cui si riescono a rappresentare tutte le istruzioni!

Linguaggio macchina: i formati delle istruzioni del MIPS

31

I 3 formati delle istruzioni MIPS

op rs rt rd shamt funct6 bit 5 bit 5 bit 5 bit 5 bit 6 bit

op rs rt16 bit6 bit 5 bit 5 bit

Op address31 26 25 0

6 bit 26 bit

const o address

TIPO-R

TIPO-I

TIPO-J

32

Perché si utilizza un formato che “divide il codice operativo” in due campi?

• Le istruzioni che hanno lo stesso codice operativo sono molto simili: p.es. per add, sub, and, or, slt l’implementazione può prevedere

- prelievo dei due operandi rs e rt- operazione ALU determinata dal campo funct- memorizzazione risultato in rd

Þ l’unità di controllo “fa la stessa cosa” se funct è in ingresso alla ALU

• In questo modo si riesce a rendere il Formato-R quanto più simile aidue successivi

Perché i due campi “sorgente” nel TIPO-R precedono il campo “destinazione”?

• Si aumenta la similarità con il Formato-I, garantendo che i registrisorgente (se presenti) siano sempre rappresentati negli stessi campi

33

Formato-R (register) [per istruzioni aritmetiche e logiche]

op rs rt rd shamt funct6 bit 5 bit 5 bit 5 bit 5 bit 6 bit

op: codice operativors: primo operando sorgente (registro)rt: secondo operando sorgente (registro)rd: registro destinazioneshamt: shift amount (per operazioni di scalamento)funct: seleziona una variante specifica dell’operazione base definita nel

campo op

Per esempio: campo funct per le istruzioni add, sub, and, or, sltADD: 100 000SUB: 100 010AND: 100 100OR: 100 101SLT: 101 010

op = 0

ES. add rd, rs, rt

34

op rs rt rd shamt funct

6 bit 5 bit 5 bit 5 bit 5 bit 6 bit

Esempi

add $t0, $s1, $s2

0 17 18 8 0 32

sll $t2, $s0, 4

0 0 16 10 4 0NON USATO

35

Istruzioni con due operandi registro e una costante.

P.es. le istruzioni lw e sw riferiscono: • due registri (rs e rt)• una costante da sommare a rt per calcolare l’indirizzo

Formato-I (immediate)

op rs rt const | address6 bit 5 bit 5 bit 16 bit

36

Codifica delle istruzioni immediate

op rs rt const

rs: registro sorgentert: registro destinazioneconst: costante da sommare a 16 bit

ES. addi rt, rs, const

6 bit 5 bit 5 bit 16 bit

addi $t0, $t1, 400

8 9 8 400

Esempio

37

• L’operando è una costante

• Usato dalle versioni “immediate” delle istruzioni aritmetiche (ad es. addi) che usano due operandi registro (sorgente e destinazione) e un operando immediato

• La costante è contenuta nel “immediate” nel formato-I

• Essendo un intero a 16 bit, ha valori da –215 a +(215-1) o, interpretatocome “unsigned”, da 0 a 216-1

Indirizzamento immediato

38

Codifica delle istruzioni di trasferimento

op rs rt const

rs: registro base al cui contenuto va sommato constrt: primo registro che compare nell’istruzione

(registro destinazione per lw e registro sorgente per sw)const: costante da sommare a 16 bit (-215 … +215 -1)

lw rt, const(rs) sw rt, const(rs)

6 bit 5 bit 5 bit 16 bit

lw $t0, 400($t1)

35 9 8 400

sw $t0, 400($t1)

43 9 8 400

Esempi

39

Indirizzamento tramite base o spiazzamento

L’operando è in memoria. P.es.

lw $t1, 32($t0)

- $t0 contiene un indirizzo base- 32 è uno spiazzamento da sommare al contenuto di $t0

NB: lo spiazzamento è espresso come intero con segno a 16 bit, quindi può valere da –215 a +(215-1)

40

Codifica delle istruzioni di salto condizionato

• Anche per le istruzioni beq e bne si usa il Formato-I

bne $s0, $s1, Esci # vai Esci se $s0 è diverso da $s1

16 17 Esci56 bit 5 bit 5 bit 16 bit

(dove 16 e 17 sono i numeri dei registri $s0 e $s1)

PROBLEMA: come viene codificata l’etichetta?Abbiamo a disposizione 16 bit…

41

Indirizzamento a byte e vincolo di allineamento delle istruzioni

10010001

11100000

00101000

11000000

11111111

00101010

00000000

11110000

01010101

10100011

11111111

11100000

01

23

4

Parola

Parola

Parola

8

567

910

11• Il MIPS indirizza il singolo byte• Una parola di memoria = 4 byteÞ Gli indirizzi delle parole

sono multipli di 4 (vincolo di allineamento)

• Ogni istruzione occupa una paroladi memoria (4 byte)Þ Gli indirizzi delle istruzioni

sono multipli di 4, ovvero hanno gli ultimi due bit a 0

42

• Se si codificasse direttamente l’indirizzo con 16 bit nessun programma potrebbe avere dimensioni maggiori di 216

Þ idea: specificare un registro da sommare all’indirizzo di salto, cioè:

Program counter = Registro + Indirizzo di salto

• Ma quale Registro di partenza usare?- Considerando che normalmente i salti condizionati vengono usati nei

cicli e nei costrutti if, i salti sono in genere ad istruzioni vicineÞ usare PC, che ha l’indirizzo dell’istruzione [successiva a quella] corrente

• Per sfruttare i 16 bit a disposizione, si può considerare l’indirizzo in istruzioniÞ a partire da PC si può saltare fino a una distanza di ±215-1 istruzioni

(basta moltiplicare per 4 la costante, ovvero concatenarla con ’00’) rispetto all’istruzione [successiva a quella] corrente

• L’indirizzamento PC-relative è usato nelle istruzioni di salto condizionato, mentre le istruzioni jump e jump-and-link (chiamata di procedure) utilizzano un altro modo di indirizzamento

Indirizzamento relativo al Program-Counter (PC-relative)

43

Esempio di indirizzamento PC-relative

• L’indirizzo PC-relative si riferisce al numero di parole che lo separano dalla destinazione, considerando che il PC contiene già l’indirizzo dell’istruzione successiva (viene infatti incrementato nella fase preliminare dell’esecuzione dell’istruzione corrente)

• Quindi l’offset è (52-20) / 4 = 8: l’istruzione bne somma 8x4=32 byte all’indirizzo dell’istruzione successiva (80020)

Supponiamo che alla locazione 80016 vi sia l’istruzione

bne $s0, $s1, Esci

16 17 858001680020 …… …

80052 …

44

Similarità tra i formati

op rs rt rd shamt funct

6 bit 5 bit 5 bit 5 bit 5 bit 6 bit

op rs rt const | address

16 bit

• Il codice op è nella stessa posizione• Il campo per i registri rs e rt è lo stesso:

p.es. nel caso un’istruzione debba usare il valore di due registri, questiregistri sono sempre indicati nei campi rs e rt!

6 bit 5 bit 5 bit

45

Formato-J (jump) [per istruzioni di salto incondizionato j e jal]

• Queste istruzioni non specificano alcun registro• I salti della jump e jal non sono in genere “locali”: abbiamo bisogno di un formato

che permetta di specificare una costante con più di 16 bit!

Op address31 26 25 0

• I 26 bit all’interno dell’istruzione jump contengono un indirizzo in parole, questi 26 bit vengono concatenati con i 4 bit più significativi del PC

• L’indirizzo in byte si ottiene poi moltiplicando per 4 (ovvero, concatenando altri due bit 00) per ottenere un indirizzo a 32 bit

indirizzo

6 bit

10000

op

2

26 bit

Indirizzamento pseudo-diretto (per i salti incondizionati):

j 10000 # vai alla locazione 10000 (espresso come indirizzo di parola)

46

Indirizzamento pseudo-diretto (per i salti incondizionati): schema

BLOCCO 0

BLOCCO 1

BLOCCO 2

4 bit

0000

0001

0010

…

PC

Op address0

:00

47

(rs)

Schema riassuntivo: i 5 modi di indirizzamento del MIPS

48

1. Indirizzamento immediato: l’operando è una costante specificata in un campo (16 bit) dell’istruzione

2. Indirizzamento tramite registro: l’operando è un registro specificato in un campo (5 bit) all’interno dell’istruzione

3. Indirizzamento tramite base o tramite spiazzamento: l’operando è in una locazione di memoria individuata dalla somma del contenuto di un registro e di una costante specificata nell’istruzione (16 bit)

4. Indirizzamento relativo al program counter (PC-relative addressing): l’indirizzo è la somma del contenuto del PC e della costante contenuta nell’istruzione (16 bit) moltiplicata per 4 (esprime uno scostamento in parole)

5. Indirizzamento pseudo-diretto: l’indirizzo è ottenuto concatenando i 26 bit dell’istruzione con i 4 bit più significativi del PC a sinistra e con i bit 00 a destra