Rappresentazione dell’informazione
•
•
•
•
•
•
•
•
Codifica dei numeri
Rappresentazioni in base 2, 8, 10 e 16
Rappresentazioni M+S, C1 e C2
Algoritmi di conversione di base
Algoritmi di somma, moltiplicazione e divisione
Overflow
Numeri in virgola fissa e mobile, standard IEEE754
Codifica ASCII
Istruzioni e linguaggio macchina
•
I linguaggi macchina sono composti da istruzioni macchina,
codificate in binario, con formato ben definito
• processori diversi hanno linguaggi macchina simili
• scopo: massimizzare le prestazioni
• veloce interpretazione da parte del processore
• efficace traduzione/compilazione di programmi ad alto
livello
•
Linguaggi molto più primitivi dei linguaggi ad alto livello
• controllo del flusso poco sofisticato (non ci sono for, while, if)
Linguaggi molto restrittivi
• istruzioni aritmetiche con numero fisso di operandi
•
Linguaggio macchina e astrazioni
Istruzioni macchina e codifica binaria
Le istruzioni macchina, ovvero il linguaggio che la
macchina (processore) comprende, hanno bisogno
anch’esse di essere codificate in binario
• Devono essere rappresentate in binario in accordo ad
un formato ben definito
Il linguaggio macchina è molto restrittivo
• il processore che studieremo sarà il MIPS, usato da
Nintendo, Silicon Graphics, Sony...
• l’ISA del MIPS è simile ad altre architetture di CPU
sviluppate dal 1980
• le istruzioni MIPS operano su particolari supporti di
memoria denominati registri, la cui lunghezza è di 32 bit
= 4 Byte
Informazione e memoria
L’informazione, opportunamente codificata, ha bisogno di essere
memorizzata nel calcolatore per essere utilizzata.
In particolare i programmi (e i dati) devono essere trasferiti nella
memoria principale del computer per l’esecuzione.
Organizzazione della memoria:
• sequenza di celle (o locazioni) di lunghezza prefissata
• ogni cella è associata con un numero (chiamato indirizzo)
• se un indirizzo è espresso come numero binario di m bit
• sono indirizzabili 2m celle diverse (da 0 a 2m -1)
• indirizzi consecutivi → celle contigue
• nelle memorie attuali, ogni cella di memoria è lunga
23= 8 bit = 1 Byte
(memoria indirizzabile al Byte)
Stored Program
•
•
•
•
•
•
Istruzioni sono stringhe di bit
Programmi: sequenze di istruzioni
Programmi (come i dati) memorizzati in memoria
La CPU legge le istruzioni dalla memoria (come i dati)
Ciclo macchina (ciclo Fetch – Decode – Execute)
• La CPU legge (fetch) l’istruzione corrente (indirizzata da un
registro Program Counter = PC), e la pone in un registro
speciale interno
• La CPU usa i bit dell’istruzione per "controllare" le azioni da
svolgere, e su questa base esegue l’istruzione
CPU determina la “prossima” istruzione e ripete il ciclo
Istruzioni Aritmetico/Logiche
•
•
•
•
•
•
Le istruzioni aritmetiche del MIPS permettono solo
operazioni elementari (add, sub, mult, div) tra coppie di
operandi a 32 bit
Le istruzioni logiche (and, or) sono bit a bit
Tutte le istruzioni hanno 3 operandi
L’ordine degli operandi è fisso
L’operando destinazione in prima posizione
Esempio
• Codice C: A = B + C
• Codice Assembler: add $9, $17, $18
• Il compilatore associa le variabili ai registri
Codifica in formato R-Type
esempio
add $9, $17, $18
semantica
$9 = $17 + $18
codifica
000000 10001 10010 01001 00000 100000
op
op:
rs
rt
rd
shamt
funct
operazione base dell’istruzione
rs: registro del primo operando
rt: registro del secondo operando
rd: registro destinazione, che contiene il risultato dell’operazione
shamt: utilizzato per istruzioni di shift; posto a zero per le altre istruzioni
funct: seleziona la specifica variante dell’operazione base definita nel campo op
Informazione e memoria
I Byte consecutivi sono organizzati in gruppi
• ogni gruppo è una Word (parola di memoria)
• processori a 64 bit (Word di 8 Byte) e a 32 bit (Word di 4
Byte)
• le istruzioni aritmetiche operano su Word
• la dimensione della Word stabilisce qual è il massimo
intero rappresentabile
Istruzioni di trasferimento dati
•
•
•
•
•
•
Leggere dalla memoria su registro: lw (load word)
Scrivere da registro alla memoria: sw (store word)
Esempio:
A è un array di
numeri interi
• Codice C: A[8] += h
• Codice Assembler: lw $15, 32($4)
add $15, $5, $15
sw $15, 32($4)
displacement
Indirizzo di memoria &A[8] → $4 + 32
Nota: sw ha la destinazione come ultimo operando
Nota: le istruzioni aritmetiche operano su registri, non su
celle di memoria.
Codifica in formato I-Type
esempio
lw $9, 32($18)
semantica
$9 = memory[$18] + 32
codifica
000000 10010 01001 0000000000100000
op
rs:
rs
rt
16-bit constant
registro della locazione di memoria
rt: registro destinazione
16-bit constant: operando immediato (displacement)
Questo formato codifica anche operazioni aritmetico-logiche
con valori immediati, i.e., costanti: add $15, $5, #66
Istruzioni di controllo del flusso
•
•
•
Il flusso di esecuzione è normalmente sequenziale
Le istruzioni di controllo cambiano la prossima istruzione
da eseguire
Istruzioni di salto condizionato
branch if equal
beq $4, $5, LABEL
•
Esempio
if (i == j)
h = i + j;
...
•
branch if not equal
bne $6, $5, LABEL
Formato I-Type
bne $4, $5, LABEL
add $19, $4, $5
LABEL: ...
Istruzioni di controllo del flusso
•
Salto non condizionato
j LABEL
•
Esempio
if (i != j)
h = i + j;
else
h = i – j;
...
•
LAB1:
LAB2:
beq $4, $5, LAB1
add $3, $4, $5
j LAB2
sub $3, $4, $5
...
Formato J-Type
op
26-bit constant
Istruzioni di controllo del flusso
•
•
Come facciamo a esprimere “Salta se minore o uguale di”?
In MIPS c’è un’istruzione aritmetica, set-if-less-than
Istruzione
slt $10, $4, $5
•
Formato R-Type
Significato
if ($4 < $5)
$10 = 1;
else
$10 = 0;
Riassunto
add $4, $5, $6
sub $4, $5, $6
lw $4, 100($5)
sw $4, 100($5)
bne $4, $5, LABEL
beq $4, $5, LABEL
j LABEL
slt $4, $5, $6
$4 = $5 + $6
$4 = $5 – $6
$4 = Memory[$5+100] Memory[$5+100] = $4
Se $4 ≠ $5, prossima istr. caricata dall’indirizzo LABEL
Se $4 = $5, prossima istr. caricata dall’indirizzo LABEL
Prossima istr. caricata dall’indirizzo LABEL
$4 = ($5 < $6) ? 1 : 0
Algebra e circuiti elettronici
•
•
•
I computer operano con segnali elettrici con valori di
potenziale discreti
Sono considerati significativi soltanto due potenziali (high/
low); i potenziali intermedi, che si verificano durante le
transizioni di potenziale, non vengono considerati
L’aritmetica binaria è stata adottata proprio perché i bit
sono rappresentabili naturalmente tramite elementi
elettronici in cui siamo in grado di distinguere i 2 stati del
potenziale elettrico (high/low)
Segnale binario
Algebra e circuiti elettronici
Il funzionamento dei circuiti elettronici può essere
modellato tramite l’Algebra di Boole
• solo 2 valori:
•
•
valore logico True (1 o asserted) → livello di
potenziale alto
•
valore logico Falso (0 o deasserted) → livello
di potenziale basso
operazioni logiche Booleane: somma (OR), prodotto (AND) e inversione
(NOT) logica
• OR (A+B): risultato uguale ad 1 (true) se almeno un input è 1 (true)
• AND (A∙B): risultato uguale ad 1 (true) solo se tutti gli input sono 1 (true)
•
NOT (~A): risultato uguale all’inverso dell’input (0 → 1 oppure 1 → 0)
Blocco logico
•
circuito elettronico con linee (fili) in input e output
•
possiamo associare variabili logiche con le varie linee in input/output
• i valori che le variabili possono assumere sono quelli dell’Algebra di Boole
I0
O0
blocco logico
I1
O1
•
il circuito calcola una o più funzioni logiche, ciascuna esprimibile tramite una
combinazione di operazioni dell’Algebra di Boole sulle variabili in input
•
Circuito combinatorio
•
•
senza elementi di memoria - produce output che dipende funzionalmente solo
dall’input
Circuito sequenziale
•
con elementi di memoria - produce output che dipende non solo dall’input ma
anche dallo stato della memoria
Tabelle di verità
•
•
•
Una funzione logica è completamente specificata tramite
la sua tabella di verità
Dati n input bit, il numero di configurazioni possibili degli
input, ovvero il numero di righe della tabella di verità, è 2n
per ogni bit in output, la tabella contiene una colonna,
con un valore definito per ognuna delle combinazioni dei
bit in input
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
D
1
0
1
0
0
0
1
0
E
0
1
0
0
0
0
1
0
Equazioni logiche
•
•
•
Una funzione logica completamente specificata tramite una equazione logica
dell’algebra di Boole
Esempio: E = ~A~BC + AB~C
• bit in input e output rappresentati tramite variabili logiche (con valori 0 o 1)
• input combinati tramite le operazioni di somma (OR), prodotto (AND) e
complementazione (NOT) logica dell’algebra di Boole
Proprietà
• Identità:
A+0=A
A∙1=A
• Nullo:
A+1=1
A∙0=0
• Idempotente:
A+A=A
A∙A=A
• Inverso:
A+(~A)=1
A∙(~A)=0
• Commutativa:
A+B=B+A
A∙B=B∙A
• Associativa:
A+(B+C)=(A+B)+C
A∙(B∙C)=(A∙B)∙C
• Distributiva:
A∙(B+C)=(A∙B)+(A∙C)
A+(B∙C)=(A+B)∙(A+C)
• DeMorgan:
~(A+B)=(~A)∙(~B)
~(A∙B)=(~A)+(~B)
Funzioni e tabelle AND, OR, NOT
•
•
•
OR (A+B): risultato uguale ad 1 (true) se almeno un
input è 1 (true)
AND (A∙B): risultato uguale ad 1 (true) solo se tutti gli
input sono 1 (true)
NOT (~A): risultato uguale all’inverso dell’input (0→1
oppure 1→0)