Riepilogo Esame di Calcolatori Elettronici - Architetture

Esame

Teoria per Esercizi

Tipologie

Traduzione da C a Assembler → fare esercizi

#istruzioni aritmetiche

add rd, rs, rt

sub rd, rs, rt

addi rd, rs, cost

subi rd, rs, cost

addu

subu

addiu

subiu

mult rs, rt #registro di destinazione implicito

div rs, rt # """"

or rd, rs, rt

and rd, rs, rt

ori

andi

nor rd, rs, rt

sll rd, rs, cost

srl rd, rs cost

#istruzioni di trasferimento dati

lw $s1, 100($s2)

sw $s1, 100($s2)

mfhi rd

mflo rd

#per costanti a 32 bit:

lui $t0, cost

ori $t0, $t0, cost

#per lo scambio atomico:

ll $t1, 0($s1)

sc $t1, 0($s1)

#istruzioni di salto

beq r1, r2, L1

bne r1, r2, L1

j L1

jr r31

jal L1

slt $s1, $s2, $s3

sltu

slti

sltiu

#pseudo istruzioni

blt $s1, $s2, L1

#equivale a:

slt $sat, $s1, $s2

Esame 1

bne $at, $zero, L1

bgt

ble #in queste due c'è anche l'uguale

bge

move $t0, $t1 #equivale a un'addizione con zero

mul $s0, $t1, $t2 #metto il risultato dell'operazione direttamente dentro a $s0, prendendolo da 'lo'

Riassunto istruzioni

Registri

Esame 2

Esame 3

Traduzione di costrutti base

#scorrimento di array

A[0] -> $s3

A[1] -> $s3 + 4

...

A[i] -> $s3 + 4i

#sommare una costante a un elemento dell'array a indice costante

A[12] = h + A[8];

con h -> $s2

e A[0] -> $s3

lw $t0, 32($s3)

add $t0, $s2, $t0

sw $t0, 48($s3)

#indirizzamento elemento generico

g=h+A[i]

g, h, i in $s1, $s2, $s4, A[0] in $s3, quindi A[i] in $s3 + 4i

muli $t1, $s4, 4 #metto 4i nel registro temporaneo l'alternativa è lo shift a sx di una potenza di due (sll)

add $t1, $t1, $s3

lw $t0, 0($t1)

add $s1, $s2, $t0

#struttura if...then

if (i==j) f=g+h

con f,g,h,i,j associate a $s0 ... $s4

ristrutturazione codice:

if (i!=j) goto Label;

f=g+h;

Label:

bne $s3, $s4, Label

add $s0, $s1, $s2

Label:

Esame 4

#struttura if...then...else

if(i==j) f=g+h;

else f=g-h;

con registri utilizzati come prima

bne $s3, $s4, Else

add $s0, $s1, $s2

j End

Else: sub $s0, $s1, $s2

End:

#ciclo do while

do {

g=g+A[i]

i=i+j;

}

while (i!=h);

g,h,i,j,A[0] in $s1....5

il codice C diventa:

Ciclo: g=g+A[i];

i=i+j;

if (i!=h) goto Ciclo;

Loop: muli $t1, $s3, 4

add $t1, $t1, $s5

lw $t0, 0($t1)

add $s1, $s1, $t0

add $s3, $s3, $s4

bne $s2, $s3, Loop

#ciclo while

while (A[i]==k)

i=i+j;

Ciclo: if (A[i]!=k) goto Fine;

i=i+j;

goto Ciclo;

Fine:

i,j,k, A[0] in $s3, $s4, $s5, $s6

Loop: muli $t1, $s3, 4

add $t1, $t1, $s6

lw $t0, 0($t1)

bne $t0, $s5, Exit

add $s3, $s3, $s4

j Loop

Exit:

#funzioni ricorsive

int fattoriale (int n){

if (n<1) return 1;

else return (n*fattoriale(n-1))

fattoriale:

addi $sp, $sp, -8 #bisogna incrementare lo stack pointer (far crescere verso il bassso) per far posto a due registri:

#il reg. di ritorno e il registro $a0 per l'argomento n

sw $ra, 4($sp) #salvo in $ra il programma chiamante

sw $a0, 0($sp) #salvo argomento

slti $t0, $a0, 1 #se n<1 in t0 metto 1 altrimenti 0

beq $t0, $zero, L1 #se n>= 1 salto a L1

addi $v0, $zero, 1 #se n<1 continuo e fattoriale restituisce 1

addi $sp, $sp, 8 #libero spazio nello stack

jr $ra #ritorno al programma chiamante, dato che $ra e $a0 non cambiano quando n<1, possiamo eliminarli

#senza caricarli in memoria

L1:

addi $a0, $a0, -1 #n diventa n-1

jal fattoriale #chiamata a fattoriale con n-1

lw $a0, 0($sp) #indirizzo linkato dalla jal:ripristino n perchè mi serve per la moltiplicazione del valore di ritorno

lw $ra, 4($sp) #ripristino registro di ritorno

addi $sp, $sp, 8 #liberiamo spazio dallo stack

mul $v0, $a0, $v0 #restituisce n*fattoriale (n-1)

jr $ra #ritorno alla funzione chiamante

Esame 5

Esercizio esplicativo su ciclo for:

for (i=0; i<a; i++)

for (j=0; j<b; j++)

D[4*j]= i+j;

//a,b,i,j in $s0,1 e $t0,1 e D[0] in $s2

i=0;

Ciclo1: j=0;

i=i+1;

if (i<a) goto Ciclo2;

j Fine

Ciclo2: if (j<b){ D[4*j] = i+j;

j=j+1;

goto Ciclo2;}

else goto Ciclo1;

Fine:

addi $t0, $zero, 0 #i=0

Loop1:

addi $t1, $zero, 0 #j=0

slt $t2, $t0, $s0 #se i<a t2=1

beq $t2, $zero, Esci #se i<a t2!=0, quindi si va a loop2

Loop2:

#check su j

slt $t3, $t1, $s1 #se j<b t3=1

beq $t3, $zero, Else #se j>=b vado a Else

#corpo in del ciclo in caso j<b

add $t4, $t1, $t0 #i+j

muli $t3, $t1, 4 #4*j in t3 (lo posso sovrascrivere)

add $t2, $t3, $s2 #in t2 metto D[0]+4*j = indirizzo di D[4*j] (t2 lo posso sovrascrivere)

sw $t4, 0($t2) #metto in memoria (all'indirizzo calcolato in t2) il valore di i+j, ovvero $t4

addi $t1, $t1, 1 #j++

j Loop2 #per ricominciare il Loop2 dopo aggiornamento di j

Else:

addi $t1, $t1, 1 #aggiorno i e rinizio dal ciclo esterno

j Loop1

Esci:

#DIVERSO DALLLA SOLUZIONE DEL LIBRO, MA DOVREBBE FUNZIONARE

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/79b905797f10493198a67c6d5493dc0

4/Fattoriale_ed_es_Baglietto.pdf

Pipeline → preparato

Senza ottimizzazioni

Operazioni aritmetiche e logiche

Esame 6

Il registro che contiene il risultato è aggiornato nel WB

Hanno bisogno dei registri che contengono gli operandi nello stato ID

Operazioni di trasferimento dati

la lw scrive il dato nella WB

la sw preleva il dato da mettere in memoria nello stato ID

Istruzioni di salto

nelle branch l'indirizzo di salto viene calcolato nello stato MEM

anche per le jump sappiamo con certezza l'indirizzo a cui saltare solo nello stato MEM

Con ottimizzazioni (cosa cambia)

Operazioni aritmetiche e logiche

Il risultato dell'operazione si ha già nella fase EX

Gli operandi si possono mandare anche nello stesso ciclo del ID perché i registri possono essere letti e scritti

nello stesso ciclo

Operazioni di trasferimento dati

nella lw, il dato prelevato dalla memoria è già disponibile nello stato MEM

Istruzioni di salto

Nelle branch il calcolo dell'indirizzo viene deciso nello stato ID

Per le jump anche c'è l'anticipazione

Scenari possibili

Nelle operazioni aritmetiche si possono mandare in forward i dati se servono a istruzioni successive, ma solo

nei seguenti stadi: da EX posso andare a EX o da MEM a EX, ma non nello stesso ciclo di clock, perché

l'hardware di propagazione è aggiunto all'inizio dell'ALU e basta

Da WB a ID solo nel caso in cui però si abbia l'ottimizzazione sui registri che permettano lettura e scrittura

nello stesso clock

Le sw danno problemi solo se non hanno i dati disponibili nello stadio ID qui si agisce con stalli o con

l'aggiunta di hardware di forwarding da MEM a MEM (caso Memory-to-Memory copy)

Esame 7

Memoria → preparato

Mappatura diretta

A ogni locazione della memoria principale corrisponde una sola locazione di memoria cache

 Per trovare un blocco devo cercare l'INDICE nella cache: l'indice corrisponde agli n bit (esclusi i due meno

significativi, che servono per i byte) meno significativi dell'indirizzo della memoria principale: se ho una cache

di 4 blocchi devo guardare i 2 bit (esclusi i primi due) meno significativi per sapere la locazione in cache di un

certo indirizzo della memoria principale corrispondente a un parola (in generale un per una cache di 2^n

blocchi ho bisogno di n bit per l'indice). NB qui ho considerato blocchi di una parola.

 Guardare l'indice non basta, perché più parole della memoria condividono lo stesso blocco di cache: serve un

altro campo della cache denominato TAG esso contiene i restanti bit che non sono compresi nel campo

indice.

 Guardare il bit di validità, che dice se un blocco di cache contiene un valore valido o no, perché in certe

situazioni il campo tag può contenere un valore non valido, ad esempio all'avvio del processore, oppure

quando un blocco della cache rimane vuoto in esecuzione.

Per trovare il blocco corrispondente a un indirizzo della memoria principale si fa l'operazione:

→ Indirizzo blocco)MOD(numero blocchi cache) dove Indirizzo blocco = Indirizzo in byte/byte per blocco

Calcolo delle dimensioni di una cache a mappatura diretta:

Esame 8

sul libro esempio di estrazione di numero di blocco dato indirizzo in byte (p. 339.

Rappresentazioni:

Blocco di una parola

Blocco di 4 parole

Esame 9

Cache set associativa

Un blocco della memoria può essere associato a n posizioni alternative → cache set-associativa a n vie

 La cache è formata da un certo numero di linee ciascuna contenente n blocchi. Un blocco di memoria può

essere scritto solo in una linea (individuata dal campo INDICE, ma può essere scritto in uno qualsiasi dei

blocchi contenuti nella linea. In sostanza ogni blocco di memoria viene associato direttamente a una linea, poi

si devono confrontare tutti i blocchi della linea per cercare il blocco che ci serve (se c'è).

 La ricerca nei vari blocchi della linea deve essere fatta confrontando i campi TAG di tutti i blocchi in parallelo.

Poi è necessario un MUX con n ingressi per selezionare il dato di uno degli n blocchi.

 Più bit ci sono per il campo tag più la cache è associativa perché significa che più blocchi di memoria possono

stare nella stessa linea. Inoltre avendo meno bit per l'indice ho meno linee. E viceversa.

Per trovare la linea nella quale risiede un indirizzo della memoria principale si fa l'operazione:

→ Numero blocco)MOD(numero di linee della cache) con Numero blocco= indirizzo in byte/numero byte per

blocco

Rappresentazione cache a 4 vie:

Esame 10

Nelle cache set associative quando serve sostituire un blocco degli n costituenti una linea si usa la politica LRU,

ovvero si sostituisce il blocco usato meno di recente: con una set associativa a 2 vie basta un bit per dire qual è il

meno recente,

Datapath → preparato

Unità di controllo

Tutti i segnali possono essere decisi solo guardando il campo OPCODE, tranne PCSrc, che viene determinato

dall'AND tra BRANCH e l'uscita ZERO dell'ALU. Ai segnali dell'unità di controllo bisogna aggiungere i due

segnali di controllo dell'ALU, i due ALUOp.

Esame 11

RegDst entra in gioco nelle operazioni aritmetiche 1 e logiche e nelle lw 0

RegWrite comanda il WB nel register destination comandato dal RegDst e dice se scrivere o no

ALUSrc entra in gioco nelle operazioni di tipo R 0 e in tutte quelle di tipo I 1 tranne le branch 0, ma

non è decisionale nel caso delle jump: per le R e la branch legge il secondo registro, per le altre di tipo I

legge il campo immediate presente nell'istruzione estesa di segno

PCSrc decide se nel PC mettere PC4 o il risultato del sommatore che calcola l'indirizzo nel caso delle

branch

Memead serve solo per le lw perché invia il dato letto all'uscita della memoria e dentro al MUX alla fine

dello stato WB

MemWrite serve solo per le sw perché mette all'ingresso della memoria il dato da scrivere letto dal registro

MemtoReg entra in gioco nelle operazioni aritmetiche e nelle lw: dice quale dato scrivere nel registro

indicato dalla RegDst: si scrive quello ceh esce come risultato dall'ALU (operazioni R 0 o quello

prelevato dalla memoria (lw 1

Branch dice se ho una branch in lettura e serve per l'AND che determina il segnale PCSrc

JUMP (non nella tabella): serve per pilotare un altro MUX messo dopo il MUX che decideva se prendere

PC4 o il salto della branch. Il MUX aggiunto sceglie l'indirizzo della jump o il dato selezionato dal primo

MUX.

Per le jump i segnali vanno messi come quelli della branch

Quando si implementa la pipeline ci serve anche un'altro segnale, IF.Scarta. Il segnale è asserito quando si

ha una branch che determina in salto: in quel momento però ho già un'altra istruzione nello stato di IF/ID,

che però deve essere scartata, mettendo a zero tutti i campi dell'istruzione appena decodificata e salvata

nel registro di pipeline ID e creando così un'istruzione che non fa nulla.

Nella gestione delle eccezioni si introducono altri segnali che azzerano i segnali di controllo salvati nei

registri di pipeline così da annullare le istruzioni negli stadi ID e EX prima che scrivano dati sbagliati nei

registri. Questi nuovi segnali sono ID.Scarta e EX.Scarta.

Segnali di controllo dell'ALU → gua